The most reliable way to tell whether a language model has memorized a benchmark is also the most expensive one. You rewrite every test question so it means the same thing but reads differently, run the model on both versions, and check whether its score drops more than clean reference models' scores do. Cheaper detectors look at the probabilities the model assigns to the test text. These break on today's reasoning models: after reinforcement-learning post-training, they fall to near coin-flip accuracy. This note proposes spending the expensive rewrite-and-retest step only where it is likely to matter, chosen by cheap signals that survive post-training. The rewrite-and-retest results are then reweighted so that the benchmark-wide contamination estimate stays unbiased even when the cheap signals are wrong.
The design borrows from wrapper feature selection. That literature searches over feature subsets by retraining a model on each candidate, and it learned to put a cheap scoring stage in front of the expensive model-in-the-loop evaluation, as in the two-stage pipeline of Contribution Tracking Feature Selection (CTFS). It also documented the main weakness of that structure: the cheap filter can throw away exactly the items the expensive stage needed to see. We keep the screen-then-confirm structure and remove the weakness with a statistical device. Every item keeps a nonzero chance of being confirmed, and confirmed items are weighted by the inverse of that chance. In two sentences: rank benchmark items by cheap, post-training-robust suspicion scores, and confirm a random, suspicion-weighted sample by rephrased retesting. Inverse-probability weighting turns that sample into an unbiased estimate of the full-benchmark contamination gap at a fraction of the cost.
Core Claim
ConStat treats the model as a black box. It measures the performance gap $\delta$ between an original benchmark and a rephrased or synthetic version, and corrects for difficulty using a curve fit on clean reference models. In controlled experiments it detected 98.4% of sample-specific contamination, against 71% for the best prior baseline. Its cost grows linearly with benchmark size, though. Every item needs a verified rephrase, a target-model run, and runs from every reference model. With long chain-of-thought reasoning models, each run is thousands of tokens.
Contamination is often partial. The contamination survey reports levels between 1% and 45% across QA benchmarks. When contamination is partial, the per-item gap is concentrated on a minority of items, and uniform evaluation wastes most of its budget on items that contribute almost nothing to $\delta$. Our claim is that cheap behavioral signals can rank items by expected gap well enough to cut confirmation cost several-fold at matched detection power. These signals are computable from outputs alone and do not depend on token probabilities. The claim includes models where probability-based detectors have collapsed.
The estimator is standard survey sampling applied to a new problem. Let $N$ be the number of benchmark items. Let $g_i$ be item $i$'s difficulty-corrected gap: the target model's correctness on the original minus on the rephrase, minus the reference-predicted gap. Let $\pi_i$ be the probability that item $i$ is selected for confirmation, and $S$ the selected set. Then
$$\hat{\delta} = \frac{1}{N}\sum_{i \in S} \frac{g_i}{\pi_i}, \qquad \pi_i = \min\!\left(1,\; \max\!\left(\epsilon,\; B\,\frac{s_i}{\sum_j s_j}\right)\right),$$
where $s_i$ is the cheap suspicion score, $B$ is the expected confirmation budget, and $\epsilon$ is a floor. The estimate is unbiased for any scores, provided $\epsilon > 0$. Its variance is smallest when $\pi_i$ is proportional to the typical size of $|g_i|$. This is the classical result for sampling with unequal probabilities. Good suspicion scores therefore buy variance reduction, and bad ones cost only efficiency, never correctness. On top of this we add a sequential stopping rule: confirm items in batches and stop when a confidence interval on $\hat{\delta}$ that stays valid at every stopping point clears or includes zero. This mirrors early termination in accelerated wrapper search.
Research Program
The first component is a set of suspicion signals, chosen because they do not rely on the log-probability margins that On The Fragility of Benchmark Contamination Detection in Reasoning Models showed GRPO-style clipping erases. That paper motivates the whole proposal. It found that SFT contamination inflates pass@1 by 8.8% on average, and that one epoch of GRPO pushes many reference-free detectors toward 50% AUROC. On advanced reasoning models, nearly all ten detectors it tested averaged 50–58% AUROC.
The first signal is free. It is the target model's anomaly on the original item: correctness that an item-response model would not predict from the target's overall ability and the item's difficulty, with difficulty calibrated on reference models. This is the same machinery that adaptive testing for LLMs uses to choose informative items. We repurpose it to flag items a model solves "too easily."
The second signal is cheap deterministic perturbation that needs no auxiliary LLM. For multiple-choice items this means shuffling the answer options. For GSM8K-style items it means swapping numbers, with the answer recomputed programmatically. The third signal is short-output behavior: a correct answer with markedly less reasoning than the model's usual length at that difficulty.
Where logits are available, Min-K% Prob enters as a fourth signal. It averages the log-probabilities of the least likely tokens in the text and has worked well on pretrained models. We expect it to contribute little after reinforcement learning, which is itself a testable prediction. The signals are combined with a small logistic model trained on a held-out set of controlled-contamination runs. That model is then frozen for all evaluations.
The second component is the confirmation stage. It reuses ConStat's rephrase generation, its synthetic-sample generation, and its reference-model difficulty correction, applied only to sampled items. Reference models are also run only on sampled items, so the savings apply to both the target and the reference pool.
The third component is analysis of when the method should not help. If contamination covers the whole benchmark, gaps are spread evenly, suspicion carries no information, and the method reduces to uniform sampling. In that regime, though, few items are needed anyway. We will map the gain as a function of contamination fraction and of the rank correlation between suspicion and realized gap. The aim is to give practitioners a rule for when to use it.
Baselines
The naive reference point is uniform random subsampling with the same ConStat confirmation stage and the same budget $B$. In our estimator this corresponds to equal suspicion scores. It is the most important comparison because it isolates the single ingredient we add. Both methods use identical rephrases, reference models, and stopping rules. Beating it means reaching the same detection power, at a fixed 5% false-positive rate on clean models, with at least 2× fewer confirmed items when contamination is partial (20% or less), while remaining no worse when contamination is full.
The strongest existing method is full ConStat run on every item. Its reported 98.4% detection of sample-specific contamination is the reference ceiling. We rerun it ourselves on the same contaminated models rather than quoting the figure across setups. Matching its detection rate within statistical noise at 30% or less of its query and token cost would count as success.
The probability-based baseline is Min-K% Prob. It reports a 7.4% AUC improvement over prior baselines on WikiMIA and 12.2% on intentionally leaked benchmark data, and the fragility paper shows it near 50–58% AUROC after reinforcement learning. We run it on the same checkpoints as a standalone detector with no budget constraint. We also run PAC, which compares token confidence across perturbed copies of the text and improved AUC by 4.5% on WikiMIA and 5.9% on StackMIA. It shows whether probability-based calibration survives post-training better than raw likelihood.
The adaptive-testing baseline selects items by item information, the way CAT does. That paper reports matching full-benchmark precision with 20% of items and 0.90+ rank correlation with full leaderboards. We give this item set the same confirmation budget. It tests whether "informative for ability" items are also "informative for contamination."
A diversity baseline greedily maximizes a submodular coverage objective over item embeddings, in the spirit of submodular file selection and the near-optimal greedy guarantees cited for wrapper search. It represents the "obvious" intersection idea.
Two ablations complete the set. One sets $\epsilon = 0$, a hard filter, to measure the bias that pure screening introduces. The other drops each suspicion signal in turn.
Why not just…?
Why not just subsample uniformly, since ConStat's statistic is a mean? This is the real threat, and it is the comparison the experiments are built around. With full or diffuse contamination, uniform sampling is optimal and we expect no gain. The advantage exists only if suspicion predicts per-item gaps. If, across controlled runs at 1%, 5%, and 20% contamination, uniform subsampling reaches matched power within noise, the core claim is false and we will say so.
Why not just use item-response anomalies as the detector and skip rephrasing? An item a model solves "too easily" may reflect genuine specialization, such as a clean model that is strong at math, rather than memorization. The adaptive-testing paper models items with fixed parameters that do not depend on which model is answering, and the survey notes that memorized subsets violate exactly that assumption. We test this directly. We apply anomaly-only detection to clean, domain-specialized reference models and measure its false-positive rate against the confirmed method. Our expectation is that anomalies rank well but certify poorly.
Why not just use submodular diversity selection, the natural import from wrapper acceleration? Coverage objectives pick representative items, while partial contamination is a rare-event problem, so diversity spreads budget evenly by construction. Our guarantee is unbiasedness with reduced variance, not a $(1-1/e)$ coverage bound. The diversity baseline above measures the difference directly.
Why not just use n-gram matching or watermarked benchmarks? Training corpora of the audited models are usually closed, so n-gram matching cannot be run by a third party. Paraphrased leakage defeats surface matching, as the survey's EvoEval result shows: an average 39.4% drop across 51 models. Watermarking requires the benchmark's creator to act before release, so it cannot audit GSM8K or MMLU as they exist now.
Proposed Experiments
Controlled contamination follows two published protocols. In the ConStat-style protocol, we fine-tune open models on known fractions (1%, 5%, 20%, 100%) of the GSM8K, ARC-Challenge, Hellaswag, and MMLU test sets. In the fragility-paper protocol, we apply SFT contamination on AIME, AMC, OlympiadBench, Minerva Math, and GPQA Diamond, followed by GRPO, plus contamination of distilled reasoning models such as DeepSeek-R1-Distill-Llama-8B. Clean twins trained on matched non-benchmark data provide negatives.
The primary metric is detection power at a 5% false-positive rate as a function of confirmed items and total tokens. Secondary metrics are mean absolute error of $\hat{\delta}$ against full ConStat, and tokens consumed until the sequential stopping rule fires.
The decisive checks are three. First, at matched power, our method must use substantially fewer confirmations than uniform subsampling in the partial-contamination regime and no more in the full regime. Second, after GRPO, our behavioral suspicion signals must still correlate with realized per-item gaps, while Min-K% no longer does. Third, on public models, the method must recover ConStat's reported findings at a fraction of ConStat's cost. Those findings are Llama-3-70b on ARC with $\delta \approx 6.6\%$ and Mistral-7b-v0.1 on GSM8K with $\delta \approx 8.3\%$, and confidence intervals that cover those values would count as recovery. For MMLU and the reasoning benchmarks, we found no reported per-model ConStat gap on Lacuna, so there we compare against our own full-ConStat runs.
References
- Contribution Tracking Feature Selection (CTFS) Based on the Fusion of Sparse Autoencoder and Mutual Information
- ConStat: Performance-Based Contamination Detection in Large Language Models
- Benchmark Data Contamination of Large Language Models: A Survey
- On The Fragility of Benchmark Contamination Detection in Reasoning Models
- Efficiently Measuring the Cognitive Ability of LLMs: An Adaptive Testing Perspective
- Detecting Pretraining Data from Large Language Models
- Data Contamination Calibration for Black-box LLMs
- Combatting Dimensional Collapse in LLM Pre-Training Data via Submodular File Selection
- Detecting Benchmark Contamination Through Watermarking