Robust, Scalable Detection of Text Containment in Large Web-Crawled Corpora

Technical Summary: FindMyText

Problem Statement
The paper addresses the challenge of text containment: determining whether a specific input text (query $q$) appears, either wholly or partially, within a large target corpus ($\mathcal{C}$). This task is critical for verifying the composition of Large Language Model (LLM) pre-training data, particularly for assessing copyright infringement and licensing violations.

Existing approaches face significant limitations in this context:

• Exact Matching: Fails because pre-training corpora undergo extensive preprocessing (OCR, boilerplate removal, normalization, segmentation), meaning the query text rarely matches the corpus text verbatim.
• Sequence Alignment (e.g., Smith-Waterman): While accurate for measuring similarity, these algorithms have quadratic computational complexity, making them infeasible for scaling to web-crawled datasets containing millions of documents.
• Near-Duplicate Detection (e.g., Jaccard similarity, MinHash, Dense Retrieval): These methods often measure global similarity or semantic proximity. They struggle to distinguish between documents that share a specific, contiguous text fragment (containment) and those that merely share similar vocabulary or ideas without containing the same passage.
• Membership Inference Attacks: Recent work suggests these attacks on black-box LLMs are unreliable for production models designed to avoid generating copyrighted content.

Methodology
FindMyText is an open-source Python toolkit designed to scale to large datasets while remaining robust to formatting discrepancies. The system operates in two stages:

1. Indexing (Preprocessing):

   • Winnowing: The system extracts $k$-grams (shingles) from documents and converts them to hashes. It applies a winnowing mechanism (Schleimer et al., 2003) to select representative fingerprints. By sliding a window of size $w$ and selecting the minimum hash in each window, the system drastically reduces the number of indices while guaranteeing that any shared substring of length $k+w-1$ yields at least one common fingerprint.
   • Inverted Index: Fingerprints are stored in a disk-based, memory-mapped inverted index mapping each hash to a list of (doc_id, position) pairs. This allows efficient retrieval of documents containing specific fingerprints.

2. Detection (Querying):

   • Fingerprint Matching: For a query $q$, the system extracts fingerprints and retrieves matching documents from the index.
   • Chain Identification (Core Innovation): Unlike standard methods that simply count shared fingerprints, FindMyText explicitly identifies chains of matching fingerprints.
     • It maps shared fingerprints to a 2D space defined by the position in the query ($p_q$) and the position offset ($\delta = p_d - p_q$) relative to the corpus document.
     • Shared text fragments manifest as geometrically coherent clusters in this space (slowly increasing $p_q$ with nearly constant $\delta$).
     • The system clusters these points using thresholds for position gaps ($\tau_{pos}$) and offset variations ($\tau_{off}$) to tolerate minor insertions or deletions.
     • Clusters smaller than a minimum size ($\kappa$) are discarded.
   • Scoring: The containment score is defined as the size of the largest valid fingerprint cluster, providing a robust measure of shared text length rather than just similarity.

Key Contributions

1. A Novel Chain-Based Method: The paper introduces a method to locate shared text fragments by clustering fingerprints based on positional coherence, distinguishing true containment from mere similarity.
2. A Synthetic Benchmark: The authors constructed a challenging benchmark using an "Oracle" based on the Smith-Waterman algorithm. This benchmark generates "positive" instances (texts with shared fragments subjected to realistic preprocessing edits) and "negative" instances (semantically similar texts with no shared fragments, created via permutation and paraphrasing).
3. Experimental Validation: The toolkit was evaluated on three diverse corpora: Wikipedia (1M articles), ArXiv papers, and generic web content (HPLT dataset, 50M+ texts).

Results
Experiments compared FindMyText against BM25, dense retrieval (using Qwen3-Embedding-4B), and a simple shared fingerprint count method.

• Performance: The chain-based approach achieved near-perfect results, with AUC-ROC scores of 0.998 (Wikipedia), 0.991 (ArXiv), and 0.999 (HPLT).
• Baseline Failure: Baseline methods (BM25, dense retrieval, and simple fingerprint counting) performed poorly (AUC-ROC often < 0.60 or near random chance). The baselines failed to distinguish between documents that were semantically similar but lacked shared text fragments versus those that actually contained the query text.
• Scalability: The system demonstrated efficient query times (10ms for Wikipedia, 450ms for the 50M-document HPLT corpus) despite the massive index size, thanks to disk-based storage and vectorized lookups.

Significance and Claims
The paper claims that FindMyText provides a robust, scalable solution for text containment specifically tailored for legal and transparency obligations (e.g., the EU AI Act).

• Legal Alignment: The authors emphasize that the tool targets "substantial similarity" in the legal sense—the reproduction of protected expression—rather than semantic similarity. This makes it suitable for identifying copyrighted material in pre-training datasets.
• Robustness: The method is explicitly designed to handle the "noisy" reality of web-crawled data, where formatting and segmentation changes obscure exact matches.
• Transparency: By enabling the verification of whether specific texts (like copyrighted books) are present in a corpus, the tool aids in data curation and model interpretability without requiring access to the LLM provider's internal data or black-box models.

The authors conclude that while the toolkit is currently focused on detection, future work includes releasing precompiled indexes for major public corpora like CommonCrawl.