Proving Train-Test Overlap Against a Committed Corpus

Language model developers now report benchmark scores without saying whether the benchmark questions were in their training data. An audit of 30 flagship models found that 21 give no meaningful information about train-test overlap. The protocol proposed to fix this asks developers to run a public overlap script on their private data and report the result, which leaves the number unverifiable. We propose to make that number checkable. The developer publishes a short cryptographic fingerprint of the set of word sequences in its training corpus, called a commitment: a value that pins down the corpus exactly but reveals nothing about it. The developer then produces a zero-knowledge proof, a certificate anyone can check that confirms a computation was done correctly without exposing its private inputs. The proof attests that the standard overlap statistics between that committed corpus and a given benchmark fall below a stated threshold. The corpus stays secret. When the benchmark is held privately, the benchmark stays secret as well.

The commitment then becomes a field in the dataset's documentation. Some sentences on a datasheet, such as "no MMLU test item appears in our pretraining data", stop being self-reported prose and become claims that can be checked. We are explicit about where this stops. A certificate over a committed corpus does not prove that the model was trained only on that corpus. A large part of the proposal is measuring how much of that remaining gap can be closed cheaply, and stating plainly how much cannot.

Core Claim

The training corpus can be committed as a sorted set of hashed $n$-grams (runs of $n$ consecutive tokens, with $n$ typically 13). Against that committed set, binary, Jaccard and token overlap with any benchmark can be proven in zero knowledge. The proving cost grows with the size of the benchmark times the logarithm of the corpus size, and does not grow with the corpus itself. The only cost that scales with the corpus is building the commitment once. That step is a single hashing pass, of the same order as the MinHash deduplication pass that pipelines like FineWeb already run.

This makes verifiable overlap reporting affordable at the scale of 15 trillion tokens today. Proving training or inference at that scale is not affordable. The new object is an overlap certificate: a proof tied to a documented corpus commitment that bounds benchmark contamination. Prior work offers neither piece. It has unverifiable overlap reports, and it has zero-knowledge machine learning proofs that never look at the training data's relationship to evaluation sets.

What exists and what it leaves open

The motivating evidence comes from documentation and contamination work. Datasheets for datasets and Model Cards for Model Reporting standardize what creators should disclose, but both are deliberately human-written and self-reported. Position: Language model developers should report train-test overlap shows that voluntary reporting largely fails. It defines the three 13-gram overlap statistics we adopt. It also proposes a protocol in which a trusted third party hosts the scripts and the developer runs them internally. We keep its metrics and its threat model, and we replace "trust the developer's output" with a proof.

Evidence that contamination matters comes from several directions. Models complete classic logic puzzles with near-zero surprise (Studying and improving reasoning in humans and machines). Web leakage lets models bypass commonsense reasoning on the Winograd Schema Challenge (Back to Square One). Performance collapses on post-cutoff causal scenarios (Unveiling Causal Reasoning in Large Language Models: Reality or Mirage?). Soft Contamination Means Benchmarks Test Shallow Generalization constrains our scope: lexical overlap misses paraphrased contamination, so we claim lexical and near-duplicate certificates only, not semantic ones.

The closest cryptographic work is P⁴Bench. It avoids contamination by having developers prove knowledge of answers to NP problems without revealing them. It certifies the answer, not the training data. Its authors note that it cannot tell whether the model or an external solver produced the answer, and it only covers problems that can be checked by a formal relation. Our certificate works on existing natural-language benchmarks such as MMLU and GSM8K, which P⁴Bench cannot express. It also says something about the training side, which P⁴Bench does not touch.

The method comes from scalable zero-knowledge machine learning. zkLLM introduced a GPU-parallel lookup argument, a way to prove that many values belong to a committed table using a sumcheck over multilinear polynomials. Set membership and intersection counting are exactly lookup problems, so we reuse this primitive for overlap rather than for neural network layers. OATH contributes the cut-and-choose idea: prove an aggregate fully, and prove expensive per-item integrity only on an auditor-chosen random sample. We apply that idea to binding the corpus to training.

Two lines of work constrain how strongly we can bind the corpus to the training run. Zero-knowledge proofs of training, zkDL and Experimenting with Zero-Knowledge Proofs of Training, work only for MLPs, small CNNs and logistic regression. Optimistic Verifiable Training by Controlling Hardware Nondeterminism verifies training by replay, but requires sharing weights with the auditor. Neither scales to frontier pretraining, and our design treats that as a fixed fact, not something to argue around.

Research Program

The commitment. The developer tokenizes the final post-filtering corpus and computes a hash of every 13-gram. A keyed hash would let the developer misreport hashes, so we use a public hash computed inside the proof. The developer then deduplicates, sorts, and builds a Merkle tree over the sorted hashes. A Merkle tree is a hash tree whose single root commits to every leaf, and it lets anyone check a single leaf with a logarithmic-length path. Sorting matters because it makes non-membership provable: two adjacent leaves bracketing the queried hash show that the hash is absent.

We also commit a second, smaller tree of MinHash signatures, computed per document under the same recipe FineWeb uses for deduplication (The FineWeb Datasets). This supports near-duplicate certificates in addition to exact matches.

The overlap proof. For a benchmark $B$ with test instances $x$, let $G(x)$ be the set of 13-gram hashes of $x$ and $C$ the committed corpus set. The binary statistic is the fraction of instances with any match:

$$ \mathrm{bin}(B, C) = \frac{1}{|B|} \sum_{x \in B} \mathbf{1}\left[\, G(x) \cap C \neq \emptyset \,\right], $$

and the developer proves $\mathrm{bin}(B,C) \le \epsilon$ for a published $\epsilon$. Jaccard and token overlap are proved the same way, with different counting.

Inside the proof, each benchmark $n$-gram is either matched to a committed leaf or bracketed by two adjacent leaves. The circuit hashes the benchmark text itself, so the developer cannot substitute different $n$-grams. It then sums the indicators and checks the inequality. The number of Merkle path checks is $|G(B)|\log|C|$; the logarithm comes from tree depth. That is millions of path checks for MMLU's test set, against a corpus of up to $10^{13}$ leaves.

For private benchmarks, the benchmark holder commits to $B$, and the proof runs as a two-party computation in which neither side sees the other's set. We prototype this case but treat public benchmarks as the main target.

Binding the corpus to training. This is the honest weak point, and we attack it in two tiers.

In the first tier, the data loader logs, for every training step, the corpus indices of the batch, chained by hash into a sequence committed alongside the model. An auditor later picks random steps. The developer then proves two things: that the batch's documents are leaves under the committed corpus root, which is cheap, and that the step's update used that batch. For models small enough, the second part uses zkDL-style proofs. Otherwise it uses optimistic replay by an auditor allowed to see the weights.

This catches a developer whose loader diverges from the commitment on a non-trivial fraction of steps. With $k$ audited steps out of $T$, contamination present on a fraction $f$ of steps escapes detection with probability about $(1-f)^k$, the usual sampling bound.

In the second tier, used for frontier-scale runs where step proofs are out of reach, only the loader log is committed. The certificate then means something weaker: the developer has bound itself to a specific data pipeline and must actively falsify a cryptographic record to cheat. We will say so on the certificate. Datasheets should state which tier applies.

Datasheet integration. We extend a machine-readable datasheet format in the spirit of Open Datasheets. It gains fields for the corpus root, the binding tier, and a list of overlap certificates, one per benchmark with its $\epsilon$ and metric. Composition fields that are counts over the committed set can carry proofs too, such as total tokens, documents per declared source, and the deduplication rate. Following Gebru et al., the reflective, qualitative sections stay human-written. We make the countable claims verifiable and leave the rest as it is.

Baselines

The naive reference point is the status quo measured in the position paper: no overlap report at all, or a self-reported number with no verification. Against this, the comparison is about guarantees, not cost. Every proposed configuration beats it on verifiability by construction. The question this baseline answers is what verifiability costs, so we report all overheads relative to doing nothing.

The strongest existing method is the trusted-script protocol of Position: Language model developers should report train-test overlap, run here as plaintext 13-gram overlap computation on the same corpus and benchmark. It is the strongest competitor because it is what the community has actually endorsed, it computes exactly our statistics, and it is cheap. We run it on identical corpora (FineWeb samples and The Pile), identical tokenization and identical benchmarks, on the same hardware.

Beating it means two things. First, our certified statistics match its plaintext outputs exactly on every benchmark. Second, total cost, meaning commitment plus all proofs, stays within a small constant factor of one plaintext overlap pass plus one deduplication pass. We will report that factor whatever it turns out to be. The file reports no cost figures for this protocol: no reported result found on Lacuna for the runtime of the position paper's overlap scripts.

The cryptographic baseline is a direct generic encoding: proving each benchmark $n$-gram's membership with a standard SNARK circuit, without batched lookups. This isolates the contribution of zkLLM-style lookup arguments. For reference, zkLLM reports proof generation for a 13B model in under 15 minutes with proofs under 200 kB and 1–3 s verification, but that figure concerns inference, not set membership. No reported result found on Lacuna for zero-knowledge set-intersection proofs over training corpora.

The key ablation removes zero knowledge entirely. The developer publishes the sorted Merkle root and plain, revealed non-membership paths for every benchmark $n$-gram. This tests whether zero knowledge is earning its place, and it is measured on leakage as well as cost.

The binding tier has its own baseline: black-box contamination detection. Here we prompt the trained model with benchmark prefixes and score memorization, with no access to data. Its detection rate on known injected contamination is compared with the spot-audit detection rate at matched auditor compute.

Why not just…?

Why not just publish a Merkle root with plain non-membership proofs, no zero knowledge? For public benchmarks this is a real threat to the need for zero knowledge, and the ablation is designed to settle it. Revealed paths expose the hashes of corpus $n$-grams that sit next to each queried hash, and the queries are adversarially chosen. A rights-holder could run many "benchmarks" built from its own texts and learn exact membership. The developer would then be forced to choose between not answering and leaking.

We will measure how many distinct corpus hashes a plain-path auditor learns as a function of query volume. We will also measure whether chosen-query attacks recover membership of planted documents. If leakage turns out negligible under rate limits, we will recommend the plain variant for public benchmarks and keep zero knowledge only for private benchmarks and aggregate composition claims.

Why not just let a trusted third party run the script, as the position paper proposes? That protocol checks nothing the developer does internally. The developer runs the script on data the third party never sees, so a filtered corpus or a fabricated number goes undetected. Our commitment at least makes the reported number a deterministic function of a published root. Combined with the first binding tier, that root is tied to training batches by sampling. The cost experiments show whether this guarantee is affordable. If commitment and proofs were orders of magnitude costlier than the plaintext pass, the trusted-party protocol would remain the practical choice, and we would report that.

Why not just detect contamination from model behavior, or use fresh benchmarks? Black-box membership tests are known to be fragile under fine-tuning and prompt engineering, as the contamination literature in the file notes. Our injection experiment measures their detection rate directly against ground truth. Fresh or procedurally generated benchmarks, such as P⁴Bench, A²RBench and the Cognitive Battery, sidestep contamination going forward. They say nothing about the MMLU and GSM8K scores that are still reported and compared. They are complements, not substitutes.

Why not just require full zero-knowledge proofs of training? Because they do not exist at relevant scale. zkDL reaches 0.8 s per step on a 10M-parameter MLP, and zkPoT covers logistic regression. Neither handles attention or billions of parameters. Our design uses them only inside the sampled audit tier, where they are feasible.

Proposed Experiments

Correctness and scaling. On FineWeb samples of increasing size, up to the largest our hardware allows, and on The Pile, we build commitments and certify binary, Jaccard and token overlap against MMLU and GSM8K. The FineWeb sample sizes are drawn from the FineWeb release, and the benchmarks are MMLU and GSM8K. We check exact agreement with plaintext computation. We fit commitment time against corpus size, where we expect linear growth, and proof time against benchmark size, where we expect growth proportional to the number of benchmark $n$-grams times log corpus size. We extrapolate to 15T tokens only if the fits are clean.

What $\epsilon$ means. A certificate threshold is useless unless we know how much contamination moves scores. We follow the FineWeb training recipe at small scale, for models of roughly 125M to 400M parameters. FineWeb reports 33% MMLU at 1.7B, so our models will sit near chance and we will rely on GSM8K-style and verbatim-recall signals where MMLU is uninformative. We inject benchmark test items at controlled rates in two forms, verbatim and rephrased. We then plot accuracy inflation against the certified overlap value.

The decisive outcome here cuts both ways. If rephrased injection inflates scores while the lexical certificate stays near zero, we will have measured exactly how far the soft-contamination limitation reaches, and that limit will be printed on the certificate. If it does not inflate scores, lexical certificates cover most of the practical risk at these scales.

Binding. For GPT-2-scale fine-tuning, the scale used in optimistic verifiable training, we train with an honest loader and with loaders that inject benchmark data on a fraction $f$ of steps. We measure spot-audit detection probability against audit budget $k$ and compare it with black-box detection at equal auditor compute.

The proposal's central bet survives if two conditions hold together. First, overlap certificates cost within a small factor of plaintext overlap computation. Second, sampled audits catch injected contamination where black-box tests miss it. If either fails, the result is still a clear measurement of what verifiable contamination reporting costs, and of which tier of guarantee the field can realistically demand.