Kernel Sketches of Training Corpora for Contamination Audits

When a benchmark leaks into a model's training data, its scores stop measuring generalization. Checking for leaks today requires access to the training corpus itself. For most models that corpus is private, so leaderboards such as the Massive Text Embedding Benchmark fall back on developers self-reporting which evaluation sets they trained on. This proposal borrows a trick that graph contrastive learning uses to escape its quadratic cost. There, the sum of similarities between one example and every other example in a dataset is approximated by a dot product between that example's random-feature vector and a single precomputed sum over the whole dataset. Applied to a training corpus, that precomputed sum becomes a compact "corpus sketch": a few kilobytes per shard of text. A data owner can publish it, and anyone can later query it to ask how much semantically similar material to a given benchmark item the corpus contained, without seeing a single document.

The core claim is concrete and testable. A set of sharded random-feature sketches, built once with a fixed public embedding model, should detect template-altered and paraphrased benchmark leakage that exact n-gram checks miss. It should come within a measurable margin of an exact embedding search over the full corpus, and it should need orders of magnitude less storage than current soft-matching indexes. The contribution is not a faster search for the data owner, who could already afford a brute-force scan. It is a portable, reusable audit artifact for third parties and for benchmarks that do not exist yet. What this proposal aims to establish is when such a sketch carries item-level signal at all, and how that depends on sketch size, shard size and kernel temperature.

Where the idea comes from

Contrastive learning trains an encoder by pulling two views of the same item together and pushing different items apart. Its standard loss, InfoNCE, divides each item's similarity to its positive by a sum of exponentiated similarities to all other items. That sum is what makes the method cost quadratic in dataset size. The field has three answers to that cost. The first drops negatives entirely, as Bootstrapped Representation Learning on Graphs does with a predictor and a moving-average target network. The second decorrelates feature dimensions instead of instances, as in From Canonical Correlation Analysis to Self-supervised Graph Neural Networks. The third keeps the sum but linearizes it. That is the route taken by Localized Contrastive Learning on Graphs, which approximates the exponential kernel with structured orthogonal random features and precomputes the pooled feature sum once. Only this third route preserves the quantity we need, a per-item estimate of total similarity mass against an entire collection. The first two discard it by design, so they serve here as method sources to reject rather than reuse.

The file also records a known weakness of this third route: the pooled sum "eliminates explicit mining of hard negatives." In a contamination setting that weakness becomes the central risk. A single leaked copy of a test question is exactly one hard, near-identical neighbor buried among billions of unrelated documents. The research question is therefore whether a pooled kernel sum can keep one needle visible, and under what settings.

The contamination literature supplies both motivation and constraints. SoftMatcha 2 shows that soft matching finds leaks that exact matching misses. It uncovered 36 previously undetected contaminated items in MMLU, GSM8K and MATH within FineWeb-Edu, at 81% manual precision. It also requires a 21.6 TB index for 1.4 trillion tokens and matches only word-by-word substitutions, not multi-word paraphrase. Maintaining MTEB defines a Zero-Shot Score that depends entirely on self-reported training sets, which is the trust gap this work targets. The taxonomy in Benchmark Data Contamination of Large Language Models: A Survey and DCR separates semantic-level, information-level, input-only and input-plus-label leakage. That split tells us which tiers a sketch can plausibly see: semantic and input-level leakage, yes; metadata leakage, probably not.

Understanding and Mitigating Data Contamination in Deep Anomaly Detection uses "contamination" to mean polluted training labels, not leaked test sets. It is still relevant for one reason: it argues that trained deep models behave like memory-based kernel machines over their training data. That motivates treating a kernel density over the training corpus as a proxy for what a model has seen.

The nearest existing work that pairs "contrastive" with "contamination" is Cultivar. It is contrastive only in the evaluation sense: it compares translation scores on original versus entity-swapped sentences, and it never touches the training corpus. Our proposal differs from it, and from SoftMatcha 2, by inspecting the corpus through a published, fixed-size kernel summary rather than through model behavior or a full index.

Core Claim

The setup fixes three things: a public audit encoder $e(\cdot)$ with unit-norm outputs, a temperature $\tau$, and a positive random-feature map $\phi$ with $m$ features such that $\phi(a)^\top\phi(b)\approx\exp(a^\top b/\tau)$. The corpus is split into $H$ shards. Shard $s$ holds passages $x_j$, and its sketch is the $m$-dimensional vector $S_s=\sum_{j\in s}\phi(e(x_j))$. For a benchmark item $q$, the estimated kernel mass in shard $s$ is

$$K_s(q)=\phi(e(q))^\top S_s \approx \sum_{j\in s}\exp\!\big(e(q)^\top e(x_j)/\tau\big),$$

and the contamination score is the largest standardized excess over matched control items $c$ that are known not to be in the corpus:

$$C(q)=\max_s \frac{\log K_s(q)-\mathbb{E}_c[\log K_s(c)]}{\mathrm{sd}_c[\log K_s(c)]}.$$

The controls are freshly written items, or items created after the corpus cutoff, drawn from the same benchmark domain.

Detectability comes down to one tradeoff. A single near-copy contributes roughly $e^{1/\tau}$ to its shard's mass. The unrelated bulk contributes roughly $n_s\,\mu(q)$, where $n_s$ is the shard size and $\mu(q)$ is the mean kernel value of $q$ against ordinary text. Lowering $\tau$ or shrinking $n_s$ makes the needle stand out. However, the variance of positive random-feature estimates grows exponentially as $1/\tau$ increases, which is the "approximation variance" limitation noted for kernelized contrastive methods. More features $m$ buy that variance back, while more shards $H$ buy back needle visibility, and the sketch size $H\cdot m$ pays for both.

The central empirical deliverable is a map of the smallest detectable leak multiplicity as a function of $(\tau, m, n_s)$. As a budget illustration, $10^5$ shards with 4,096 half-precision features each come to under a gigabyte for a trillion-token corpus. Whether that budget reaches single-copy detection is the open question the experiments settle.

Research Program

We first build sketches over progressively larger public corpora. These start with a 10-billion-token sample of FineWeb and extend to FineWeb-Edu, where SoftMatcha 2's findings provide real, independently verified leaks. Passages are chunked at a fixed length and embedded once. Sketches are computed with structured orthogonal random features, the construction used in the graph contrastive work, alongside plain Gaussian random features for comparison.

We then run planted-leak experiments. Items from MMLU, GSM8K, SST-2 and several MTEB retrieval and classification tasks are inserted into the corpus sample at controlled multiplicities from 1 to 100, across four tiers. The first tier is verbatim input with its answer. The second is input without the answer. The third is template-altered items, in which names and numbers are swapped in the manner of the rewrites used by Inference-Time Decontamination and the entity substitutions in Cultivar. The fourth is free paraphrase. Because the inserted copies are known, recall and false-positive rates can be measured exactly.

The third component is an analysis of what the sketch reveals beyond leak detection. An auditor can search for queries that maximize $K_s$, and this will expose the corpus's topic distribution. We quantify that leakage with inversion attacks against the sketch so data owners know what they give up by publishing it.

Finally, we use the score downstream. For open-data embedding models on MTEB, per-item scores $C(q)$ serve as a continuous regressor in the style of Recall Residualisation. Per-item correctness is regressed on $C(q)$ to estimate how much of a task score tracks corpus overlap. The result is an empirical counterpart to the self-reported Zero-Shot Score.

Baselines

The naive reference point is the MTEB Zero-Shot Score from Maintaining MTEB, which flags a task only if the developer declares it. It has no reported detection accuracy; no reported result found on Lacuna for its recall against undisclosed leakage. We simulate it as detecting nothing that was not declared, which gives zero recall on planted undeclared leaks by construction. Any sketch recall above that floor is informative.

The cheapest competitor with comparable publishability is an exact 13-gram Bloom filter over the same corpus. It is also a compact, shareable artifact, and it is the standard decontamination tool. It gets the same corpus, the same planted items and the same total storage in bytes, and its false-positive rate is set to match the sketch's. No reported recall on the planted tiers exists; no reported result found on Lacuna for n-gram Bloom recall on template-altered leakage. The sketch beats it if it achieves clearly higher recall on the template-altered and paraphrase tiers at a 1% false-positive rate, while giving up little on the verbatim tiers.

The strongest existing soft-matching system is SoftMatcha 2, run on FineWeb-Edu where its index is available. Its reported result is 36 newly found contaminated items across MMLU, GSM8K and MATH at 81% manual precision, with a 278.17 ms 95th-percentile soft-search latency, using a 21.6 TB index (SoftMatcha 2). The comparison asks what fraction of those 36 items land in the top of the sketch's ranking, and what the sketch finds that SoftMatcha 2 does not. Candidates for the second question are multi-word paraphrases, which the file says SoftMatcha 2 cannot match; we verify these manually under the same precision protocol. Beating it means recovering most of its 36 items at comparable precision while using roughly four orders of magnitude less storage. Surfacing additional verified leaks would count as a further win.

The upper-bound reference is an exact brute-force nearest-neighbor scan with the same audit encoder over the full embedded corpus. This is what the data owner could run privately. It isolates the cost of compression: the gap between sketch and oracle recall is exactly what publishability costs.

Two ablations isolate the key ingredient. The first computes exact kernel sums per shard, with no random features, which separates random-feature variance from the inherent weakness of summing rather than taking a maximum. The second replaces the per-shard sum with the per-shard maximum similarity, which cannot be sketched but shows how much hard-neighbor signal the pooled sum discards. A final ablation swaps the audit encoder for one trained with feature decorrelation in the style of CCA-SSG, to test whether the encoder's geometry, rather than the sketch, drives detection.

Why not just…?

Why not just publish an n-gram Bloom filter instead? It is compact, cheap and already understood, and it is the most serious competitor for verbatim leaks. We expect it to match or beat the sketch there. Its weakness is structural: SoftMatcha 2's 36 extra finds were all missed by exact matching, and DCR's semantic-level contamination bypasses lexical filters entirely. The planted-leak experiment decides this tier by tier. If the Bloom filter also catches template-altered items at comparable rates, the sketch has no reason to exist, and we would report that.

Why not just have the data owner run an exact embedding search and report the results? For a known benchmark this is computationally feasible, and it is our oracle, so compute is not the argument. The argument is trust and reuse. Self-reported search results carry the same weakness as the Zero-Shot Score. A published sketch lets anyone test benchmarks written years later without the owner re-running anything. If the gap to the oracle turns out large at feasible sketch sizes, then self-reported search remains the better option, and the experiments will show where that crossover lies.

Why not just probe the trained model directly for memorization, needing no data at all? Token-surprise probes such as the one used in Inference-Time Decontamination work on generative models. They are a real threat for language models, and the sketch should be seen as complementary to them. For embedding models evaluated on MTEB, however, there is no generation likelihood to probe. Model-side probes also cannot separate "saw this item" from "saw lots of similar text," whereas the sketch measures the second quantity directly and the control-standardized score targets the first. We will report agreement between the two on open-data models where both apply.

Why not just use dynamic benchmarks? DyVal and P⁴Bench remove the problem for formal tasks such as arithmetic, SAT and discrete logarithms. Neither extends to open-domain retrieval, sentiment or knowledge questions, which make up most static leaderboards. Those are the benchmarks audited here.

Proposed Experiments

The first decisive check is the detectability map. It measures single-copy and ten-copy recall at a 1% false-positive rate for each leak tier, across a grid of temperature, feature count and shard size, and plots it against total sketch bytes. The idea succeeds if some configuration under about one gigabyte per trillion tokens reaches substantially higher template-altered recall than the Bloom filter, and gets within a stated fraction of the brute-force oracle. It fails if needle visibility collapses before storage becomes competitive. In that case the honest conclusion is that pooled kernel sums cannot audit single leaks, only heavy contamination.

The second check is external validity on FineWeb-Edu: rank recovery of SoftMatcha 2's 36 verified items, plus manual verification of the sketch's top novel flags.

The third check tests whether sketch scores explain anything about model behavior. For MTEB tasks and open-data embedding models, we test whether items with high $C(q)$ are answered correctly more often than matched low-score items, and whether the residualized task score shifts model rankings. For reference on the size of such effects, Inference-Time Decontamination reports a 6.7% MMLU drop for Phi-3-mini under rewriting. That figure comes from a generative model, so it indicates plausible effect magnitude rather than a target for this setting.

The final check is the inversion attack. It measures how much topic and document information an adversary recovers from published sketches, so the privacy cost is reported next to the audit benefit.