When a language model scores well on a public benchmark, we want to know how much of that score comes from having seen the questions during training. Current answers are point estimates with no stated error. Some come from comparing the model against a fleet of supposedly clean reference models. Others come from heuristic thresholds on how repetitive the model's sampled outputs are. This note proposes a statistic that answers a narrower question with a guarantee attached: at least what fraction of this benchmark's items does the model treat as special in their exact published wording? The idea is simple. Rewrite each item several times without changing its meaning or answer. Then check whether the model assigns lower loss (less "surprise") to the original wording than to the rewrites. If the model has never seen the item, nothing marks the original as privileged, so its rank among the rewrites should be uniformly random. Memorized items push the original toward rank one.
Across the benchmark, the observed ranks therefore form a mixture of a known uniform distribution and an unknown "memorized" distribution. A confidence band around the empirical cumulative distribution function (CDF, the fraction of items with rank at most $r$) turns this into a finite-sample, distribution-free lower bound on the memorized fraction. The method needs no reference models, no access to training data, and no repeated sampling.
Core Claim
The mechanism is taken from Estimating the Number and Effect Sizes of Non-null Hypotheses. That paper builds a Dvoretzky–Kiefer–Wolfowitz (DKW) band, a uniform band around an empirical CDF that holds with probability $1-\alpha$, around the distribution of 13,071 gene-level test statistics. It then solves for the smallest non-null proportion consistent with that band. It proved that at least 1,400 genes had real effects, where a Bonferroni-corrected test found 83. Its key requirement is a known null distribution for each statistic. Our contribution is to show that benchmark contamination supplies one for free: under exchangeability of phrasings, the within-item rank of the original wording is exactly uniform.
Concretely, for item $i$ with original text and $k$ meaning-preserving paraphrases, let $R_i \in \{1,\dots,k+1\}$ be the rank of the original's loss among the $k+1$ versions, where rank 1 means lowest loss. If a fraction $\pi$ of items is memorized and the rest have uniform ranks, the rank CDF satisfies $F(r) = (1-\pi)\,u_r + \pi\,G(r)$, where $u_r = r/(k+1)$ and $G$ is the unknown CDF of memorized items. Since $G(r) \le 1$, any lower band $F^-$ that holds uniformly in $r$ gives
$$ \pi \;\ge\; \hat\pi_{\text{low}} \;=\; \max_{r<k+1} \frac{F^-(r) - u_r}{1 - u_r}, $$
and this bound holds simultaneously over all $r$ with probability at least $1-\alpha$.
The bound is conditional on the fixed set of benchmark items. Its only randomness comes from independently drawn paraphrases, so it answers a question about this benchmark rather than about an imagined population of benchmarks. Contamination produces a shift concentrated at small ranks. That is exactly the lower-tail regime where Quantile Risk Control showed that inverting a one-sided truncated Berk–Jones statistic tightens bounds sharply. On MS-COCO it gave a CVaR bound of 0.419 where DKW gave a vacuous 1.0. We therefore use truncated Berk–Jones as the band, with DKW as the reference.
What Prior Work Does and Does Not Do
Three contamination methods motivate the gap. ConStat tests whether a model's accuracy on the original benchmark exceeds what its accuracy on a rephrased benchmark predicts. The prediction comes from a difficulty curve fitted on 20 reference models. This makes ConStat powerful, but it is only as trustworthy as the assumption that those reference models are clean, and its target is a mean gap. Our statistic compares each item only with its own paraphrases, under the same model, so no reference cohort is needed.
Generalization or Memorization detects contamination through a collapse in the diversity of sampled outputs (CDD) and discounts the peaked mode (TED). This requires many samples per prompt and a chosen edit-distance threshold. We use one forward pass per phrasing and no threshold. DCR combines probe scores through fuzzy rules into a multiplicative accuracy discount, which has no coverage guarantee.
Two papers constrain the design. Soft Contamination Means Benchmarks Test Shallow Generalization shows that semantic duplicates dominate some training corpora. A model trained only on a paraphrase may not prefer the original wording, so our quantity is by construction a lower bound that can miss this kind of contamination (the L1 level in DCR's taxonomy). We report it as such and measure how much it misses. The IID assumption stressed throughout the risk-control literature (Concentration Inequalities for Conditional Value at Risk, Distribution-Free Statistical Dispersion Control) becomes, in our setting, one checkable assumption: exchangeability of the original and its paraphrases for clean items.
Research Program
The central threat is paraphrase bias. Human-written originals may simply be more fluent than machine rewrites, which would make clean models prefer them too. We handle this in two layers.
First, we generate paraphrases by round-tripping the original as well. The "original" slot is then compared against rewrites of matched style, and we also report a version that uses the raw original.
Second, we replace the exact uniform null with an estimated null CDF $H$. We measure $H$ on items that postdate the model's training cutoff, drawn from LiveBench and CodeForces2305, and paraphrase them with the same pipeline. We split $\alpha$ between a band on the target ranks and an upper band $H^+$ on the null ranks, and substitute $H^+(r)$ for $u_r$ in the bound. The added assumption is that paraphrase bias transfers from post-cutoff items to the target benchmark. We test that assumption directly, by checking uniformity of the reference ranks on models released before those items existed.
Paraphrases must preserve the answer. We filter them with an answer-consistency check and discard items with fewer than $k$ surviving rewrites. We report how many items are discarded, because dropping items could bias the bound.
The loss is the negative log-likelihood of the reference answer, conditioned on the phrasing. For multiple-choice benchmarks this is the likelihood of the correct option. For GSM8K it is the likelihood of the reference solution. We also rank the loss of the question text itself, which targets data-level contamination (the question is seen without its answer) as distinct from label-level contamination (question and answer seen together).
Beyond the overall bound, we compute per-subject bounds on MMLU with simultaneous validity. We use a Bonferroni split across subjects for the per-subject bounds, and the convex program of Brennan et al. for the fraction of items whose rank shift exceeds a threshold. We also report an adjusted accuracy: the accuracy on items not attributable to the lower-bounded memorized mass, computed as a worst case over the band.
Baselines
The naive reference point is the raw accuracy gap between original and paraphrased items, together with the unbanded plug-in estimate $\max_r (F_n(r)-u_r)/(1-u_r)$. Neither carries any guarantee. The plug-in estimate shows how much of our bound's width is the price of validity.
The strongest existing method is ConStat. It reports detecting 98.4% of sample-specific contamination against 71% for the best baseline in ConStat, and it estimates inflation of roughly 8.3 points for Mistral-7b-v0.1 on GSM8K. We run ConStat with its published reference-model protocol on the same models and benchmarks. We give it the same paraphrase set as its rephrased reference benchmark, so that both methods see identical rewrites. ConStat produces a test and a point estimate of inflation, not a prevalence bound. The comparison is therefore on detection power at matched false-positive rate $\alpha = 0.05$, and on whether its point estimate stays consistent with injected ground truth. Beating it means matching its detection power when its reference models are clean. It also means remaining valid, and ConStat failing, when we deliberately contaminate a subset of its reference models with the same leaked items.
CDD from Generalization or Memorization is the second competitor. That paper reports a 21.8–30.2% relative improvement over prior detectors in accuracy and AUC on DETCON. We run CDD and our method on DETCON under a matched inference budget, measured in forward-pass tokens per item. Beating CDD means higher item-set AUC at equal or lower compute. DCR, whose adjusted accuracies are reported within 4% of uncontaminated baselines, is compared on SST-2 and LIAR2 adjusted accuracy against injected ground truth.
Two ablations isolate the key ingredient. The first swaps the exchangeable-rank null for the raw loss gap between original and paraphrase, whose null must then be estimated from reference items. This tells us whether ranks actually matter. The second swaps truncated Berk–Jones for DKW and for a single binomial test at rank one. This isolates what the band buys.
Why not just…?
Why not just run n-gram overlap against the training corpus? For proprietary models the corpus is unavailable, and even when it is available, Soft Contamination Means Benchmarks Test Shallow Generalization finds semantic duplicates for 78% of CodeForces problems in Olmo3 data that exact matching would miss. We do not treat corpus search as a competitor. We use it as partial ground truth. On Olmo3, the exact-duplicate rate (50% for ZebraLogic) is a quantity our lower bound should approach but never exceed.
Why not just use ConStat, which already detects contamination with a rephrased benchmark? When clean reference models exist, ConStat may well match our detection power. The case for our method rests on the reference-circularity experiment. If ConStat's difficulty curve absorbs contamination shared across the reference fleet, its gap estimate shrinks. Our within-model rank statistic cannot shrink in this way, because it never consults another model. If ConStat stays accurate even with contaminated references, our advantage narrows to providing a guaranteed prevalence bound, and we will say so.
Why not just count items where the original has the lowest loss and run a binomial test? This is a real threat. If memorization almost always sends the original to rank one, the binomial bound at $r=1$ is nearly as tight and much simpler. The band earns its place only when contamination shifts ranks partially, which is plausible for soft or single-exposure leaks. It also earns its place for the simultaneous per-subject and threshold statements. The injected-contamination grid below includes low-exposure and paraphrase-exposure conditions designed to tell these cases apart. If the binomial test wins everywhere, we will adopt it and keep the distribution-free framing.
Why not just measure output collapse with CDD? CDD needs many samples per prompt and a tuned distance threshold, and it yields a detection score rather than a bound. Our method needs log-probabilities, which some APIs do not expose. This is a genuine limitation, and for such models CDD remains the practical option. The matched-compute comparison on DETCON settles which is better when both are applicable.
Proposed Experiments
The decisive experiment is controlled injection with repetition. We fine-tune open models such as Mistral-7b and Qwen2.5-7B on random subsets of GSM8K and MMLU test items at fractions of 0%, 1%, 5% and 20%. We vary exposure between one and several epochs, and between exact text and paraphrased text. Each condition is repeated over ten seeds and ten independent paraphrase draws.
The method succeeds if $\hat\pi_{\text{low}}$ falls at or below the true exact-text fraction in at least 95% of runs, including the 0% condition, where it must be zero at rate $1-\alpha$. It must also recover a substantial share of the injected fraction at 5% and above. We report tightness as $\hat\pi_{\text{low}}/\pi$ as a function of the number of paraphrases $k$ and the number of items $n$. We expect it to improve roughly as $1/\sqrt{n}$, which is the width of a DKW band.
Negative controls are post-cutoff LiveBench and CodeForces2305 items. There the bound should be zero, and the reference ranks should pass a uniformity check. A failure here would mean paraphrase bias is not controlled, which would falsify the method's premise.
External validation compares Olmo3's bounds with its corpus-measured duplicate rates. Separately, we check that per-subject MMLU bounds line up with MMLU-CF's reported accuracy drops of about 14% on average. Here we expect the subjects with larger bounds to be those with larger drops.
Finally, we apply the method to publicly released models on GSM8K, ARC-Challenge, MMLU and HumanEval. We report bounds alongside ConStat's estimates, including the ~8.3-point GSM8K gap ConStat reports for Mistral-7b-v0.1 and the ~6.6-point ARC gap it reports for Llama-3-70b. Agreement in sign and ordering would corroborate both methods. A large ConStat gap alongside a zero bound would point to paraphrase-level contamination that our statistic is blind to.
References
- Estimating the Number and Effect Sizes of Non-null Hypotheses
- Quantile Risk Control: A Flexible Framework for Bounding the Probability of High-Loss Predictions
- ConStat: Performance-Based Contamination Detection in Large Language Models
- Generalization or Memorization: Data Contamination and Trustworthy Evaluation for Large Language Models
- DCR: Quantifying Data Contamination in LLMs Evaluation
- Soft Contamination Means Benchmarks Test Shallow Generalization
- Concentration Inequalities for Conditional Value at Risk
- Distribution-Free Statistical Dispersion Control for Societal Applications
- LiveBench: A Challenging, Contamination-Limited LLM Benchmark
- MMLU-CF: A Contamination-free Multi-task Language Understanding Benchmark