Pre-training pipelines check for benchmark leakage by looking for exact runs of 8 to 13 words shared between web documents and test questions. That check costs almost nothing per word, but it misses rephrased leaks. Controlled pre-training experiments show that such leaks still inflate scores after standard n-gram filtering (Investigating Data Contamination for Pre-training Language Models). The paraphrase-robust alternative is to embed every chunk of a trillion-token crawl with a neural sentence encoder, which costs a transformer forward pass per chunk. We propose an option between these two. First, give each vocabulary word a set of randomized "meaning buckets", so that near-synonyms usually share a bucket. Then compute a fast set-resemblance signature over pairs of bucket ids instead of pairs of raw words. Paraphrases that swap words, rename entities, or reorder clauses keep most of their bucket-pairs. Because the word-to-bucket map is computed once for the whole vocabulary, scanning a document still costs a few table lookups per word.
The opportunity is urgent. An exact-match audit of 83TB of web text found GSM8K contamination reaching 74.2% of items in July 2025 crawls and 27.7% dirty MMLU entries in DCLM-baseline (Infini-gram mini). Those numbers are a lower bound, because that index only matches identical bytes. Nobody can currently say how much larger the true number is at a cost comparable to the exact audit.
Core Claim
A document similarity built from two pieces can recover a substantial share of paraphrased benchmark leaks that exact n-grams miss, at a per-word scanning cost within a small constant factor of exact n-gram hashing. The first piece is sign random Fourier features: one-bit hashes of a word's embedding vector whose collision probability rises with a Gaussian-kernel similarity. The second is densified one permutation hashing: a single-pass sketch that estimates set overlap. We also claim the recall of this combined signal is high enough that sending only its candidates to a neural encoder matches full-encoder recall at a fraction of the compute.
Concretely, fix a static word-embedding table. Draw $L$ independent sets of $b$ sign random Fourier features over it, so bucketing $\ell$ assigns each word one of $2^b$ bucket ids. Let $S_\ell(x)$ be the set of adjacent bucket-id pairs in text $x$ under bucketing $\ell$, with numbers mapped to a single class. The similarity we estimate is
$$s(x,y) = \frac{1}{L}\sum_{\ell=1}^{L} \frac{|S_\ell(x)\cap S_\ell(y)|}{|S_\ell(x)\cup S_\ell(y)|},$$
an averaged Jaccard overlap in which two words "match" with a probability that grows with their kernel similarity. Each Jaccard term is estimated with densified one permutation hashing using $K$ bins, which costs one pass over the document's pairs rather than $K$ passes.
Prior Work and Where This Sits
The sketching machinery is reused, not invented. One Permutation Hashing replaces $K$ independent permutations with one permutation split into $K$ bins, cutting signature cost from $O(KN)$ to $O(N)$. Short texts leave many bins empty, which breaks the estimator. The rotation and improved densification schemes (Densifying One Permutation Hashing via Rotation, Improved Densification of One Permutation Hashing) fix this by borrowing values from neighbouring bins while staying unbiased. This matters here because benchmark items are short (a GSM8K question has tens of words). The densification literature itself warns that heavy borrowing when items are much smaller than the bin count raises variance, which caps how large $K$ can usefully be. All of this work operates on raw token sets. Our contribution is to change the set, not the sketch.
The bucketing step comes from binary codes for shift-invariant kernels. Locality-sensitive binary codes from shift-invariant kernels thresholds random Fourier features into bits. SignRFF shows that taking the sign of the cosine feature ranks neighbours better than linear sign projections specifically when similarity is high (cosine above 0.8). That is the regime of near-synonyms and morphological variants, which is why we expect it to suit word-level bucketing. SignRFF evaluates static image retrieval. We apply it once to a vocabulary of roughly $10^5$ items, so its per-item cost disappears from the corpus scan entirely.
Deduplication practice motivates the work. FineWeb runs multi-hash MinHash over raw shingles, which by construction cannot see rephrasings. Its finding that global deduplication hurt quality is a reminder that matching thresholds have real costs. Over-aggressive soft matching could likewise delete legitimate educational text, so false positives are a first-class metric for us. Record-linkage work with densified hashing (Blocking Methods Applied to Casualty Records from the Syrian Conflict) shows that this sketch family already serves as a blocking stage in front of an expensive verifier. We use it in the same role.
Two results constrain the design. We considered the distributional route, which would sketch each crawl shard and test whether it is shifted toward a benchmark using random-feature two-sample tests (FastMMD) or count-array density sketches (Sub-linear RACE Sketches). We rejected it for two reasons. First, leakage is a needle problem: a few copies of a test item among billions of chunks. A fixed-size density sketch has additive error proportional to the total count, so it cannot see a handful of copies. Second, Computational-Statistical Trade-off in Kernel Two-Sample Testing with Random Fourier Features shows that a test with a fixed number of random features is not even consistent, so the sketch would have to grow with the data.
Model-side detectors answer a different question: whether an already-trained model memorized an item. These include output-distribution peaking (Generalization or Memorization), perturbation consistency (CAP), reference difficulty curves (ConStat), and internal-activation probes (RADAR). We work upstream on the corpus before training. Their test sets supply our ground truth.
Research Program
We will build a streaming scanner with four parts. The first is a precomputed table holding $L$ bucket ids per vocabulary word. The second is a single-pass routine that turns each 256-word window of crawl text into $L$ densified signatures of $K$ bins each. The third is a banded locality-sensitive index over signatures of the benchmark items; this index is small, since all major benchmarks together total around $10^5$ items. The fourth is a verifier stage that runs a sentence encoder only on windows whose estimated $s$ exceeds a threshold. Per-word cost is $L$ table lookups plus one hash per bucket-pair. The update is append-only, mergeable across workers, and needs no deletions.
The analysis has three parts. The first is how the bandwidth of the Gaussian kernel and the bit count $b$ trade synonym merging against spurious merging. The second is how $L$ and $K$ set the variance of $s$; densification theory gives the per-bucketing variance, and averaging over $L$ independent bucketings shrinks it further. The third is how short items interact with empty-bin borrowing. We will also characterize which rephrasing types the method structurally cannot catch. Deep restructuring and translation into another language are the obvious ones, and reporting this boundary is part of the contribution. Synthetic data that imitates a benchmark's style without copying items, as in TinyGSM, is a definitional grey zone. We report it separately rather than count it as leakage.
Baselines
The naive reference point is exact 13-gram matching after lowercasing, the filter whose failure Jiang et al. document. We also run a stronger normalized variant of it: numbers and named entities replaced by placeholder classes, stopwords removed, and 8-gram matching. This variant is the cheap fix a practitioner would try first. Both run on the same windows on the same CPU budget. For exact matching at scale, the reported reference is Infini-gram mini's 74.2% GSM8K contamination in July 2025 crawls and 27.7% dirty MMLU entries in DCLM-baseline. On our FineWeb sample, beating exact matching means finding verified leaks it misses while keeping precision above an agreed floor.
The strongest competitor on recall is full-encoder retrieval. Every window is embedded by an off-the-shelf sentence encoder, and its nearest benchmark items are found by brute-force inner product, which is cheap because the benchmark side is small. This is the gold standard for paraphrase recall and the main cost we aim to avoid. There is no reported result on Lacuna for encoder-based retrieval contamination recall on these benchmarks, so we will measure it ourselves. We give it the same windows and report recall and CPU/GPU-hours together. We count our cascade as winning if it reaches at least 90% of full-encoder recall at under 10% of its compute.
A third baseline is the practical cascade a reviewer would assemble without our ideas. Raw-token MinHash at FineWeb settings or BM25 retrieval against the benchmark proposes candidates, and the same encoder verifies them. It receives the same verifier budget, measured as candidates passed per million windows.
Ablations isolate each ingredient. We replace sign random Fourier features with linear sign random projections over the same embeddings, to test whether the kernel's high-similarity advantage reported in SignRFF transfers to words. We replace the randomized bucketings with a single k-means partition of the vocabulary, to test whether multiple random partitions beat one learned partition at matched table size. We set $L=1$ to measure the value of averaging over bucketings. We replace densified one permutation hashing with full $K$-permutation MinHash, to confirm that densification gives a speedup without losing accuracy on short items.
Why not just…?
Why not just normalize text harder and keep exact n-grams? Number and entity placeholders plus stopword removal will catch template-preserving edits, and we expect them to recover a real fraction of leaks. They do nothing for synonym substitution or clause reordering, which is the kind of rephrasing ConStat and the HumanEval_R construction rely on. This is a genuine threat on easy paraphrases, so the normalized filter is a full baseline, and we report recall broken down by rephrasing type. If it matches us on everything except deep rewrites, the method's value shrinks to that slice, and we will say so.
Why not just embed everything with a sentence encoder? At web scale, the forward pass per chunk is the dominant cost, not the comparison against benchmark items. That is why FineWeb-Edu's model-based scoring is run as an offline batch job and not as a filter at crawl time. The encoder stays in our system as the verifier. The question the experiments settle is whether the cheap stage loses many leaks before verification. The recall-versus-compute curve against full encoding answers it directly.
Why not just average static word vectors per window and compare cosines? This is also a few lookups per word, and it is the simplest kernel-free competitor. Averaging washes out the local word order that separates one GSM8K problem from another on the same topic, so we expect high false-positive rates within a benchmark's own domain. That expectation is untested, and this baseline could be competitive. We include it at equal cost and judge it on precision at matched recall.
Why not cluster the vocabulary once instead of using random features? A single hard partition misassigns words near cluster boundaries with no recourse. Random bucketings make the match probability a smooth function of kernel similarity, so averaging over $L$ of them gives a similarity with predictable variance. The k-means ablation tests whether this matters in practice.
Proposed Experiments
The first experiment measures detection on labelled pairs. The DETCON tasks from Generalization or Memorization cover explicit and implicit contamination, and the HumanEval/HumanEval_R pairs serve as positive rephrase pairs. We also generate paraphrases of MMLU, GSM8K, and ARC items in four controlled types: synonym swap, entity and number change, clause reordering, and full rewrite. We plant them into a FineWeb sample (HuggingFaceFW/fineweb) at known positions. Metrics are recall at fixed false-positive rate per million windows, precision on unplanted FineWeb windows judged by encoder plus human spot checks, and words per second per core.
The second experiment is a wild audit of FineWeb snapshots across years for MMLU, GSM8K, and ARC. We report how many verified non-exact leaks appear beyond those exact matching finds, and whether the growth over time parallels Infini-gram mini's exact-match trend.
The decisive check asks whether decontamination removes score inflation, not just whether matches are found. It follows the controlled protocol of Jiang et al.: pre-train GPT-2 models on a 3.3B-token Pile subset with paraphrased ground-truth contamination planted at 10 repetitions, then train copies on corpora filtered by each method. Jiang et al. report clean GPT-2 large at 22.8% MMLU versus 24.3% when contaminated, and 0.5968 versus 0.6996 on CNN/Daily Mail. If compute forces the 124M model, we first reproduce the clean-versus-contaminated gap at that size. The method succeeds if filtering with soft shingles closes most of the gap between the contaminated and clean models, while exact 13-gram filtering leaves most of it open. It must do so without removing significantly more clean tokens than the normalized n-gram baseline. If the gap closes only with the encoder cascade, the contribution is the cascade's cost saving. If even full encoding fails to close it, rephrased leakage is not detectable at the text level, and we will report that negative result.
References
- Does Data Contamination Make a Difference? Insights from Intentionally Contaminating Pre-training Data For Language Models
- Infini-gram mini: Exact n-gram Search at the Internet Scale with FM-Index
- One Permutation Hashing
- Densifying One Permutation Hashing via Rotation for Fast Near Neighbor Search
- Improved Densification of One Permutation Hashing.
- Locality-sensitive binary codes from shift-invariant kernels
- SignRFF: Sign Random Fourier Features
- The FineWeb Datasets: Decanting the Web for the Finest Text Data at Scale
- Blocking Methods Applied to Casualty Records from the Syrian Conflict.
- FastMMD: Ensemble of Circular Discrepancy for Efficient Two-Sample Test
- Sub-linear RACE Sketches for Approximate Kernel Density Estimation on Streaming Data.
- Computational-Statistical Trade-off in Kernel Two-Sample Testing with Random Fourier Features
- Generalization or Memorization: Data Contamination and Trustworthy Evaluation for Large Language Models
- CAP: Data Contamination Detection via Consistency Amplification
- ConStat: Performance-Based Contamination Detection in Large Language Models
- RADAR: Mechanistic Pathways for Detecting Data Contamination in LLM Evaluation
- TinyGSM: achieving >80% on GSM8k with small language models