Latency-Priced Few-Round Adaptive Testing for Contamination Audits

Large language models are now routinely trained on data that contains their own test questions, and the newest reasoning models make this hard to detect. After reinforcement-learning post-training, the usual detectors, which look for suspiciously low loss on test items, perform close to coin-flipping. A detection signal that survives this is behavioral: a contaminated model answers the published version of a problem much better than an equivalent version it has never seen, for example the same competition problem with different numbers. Measuring that gap reliably, however, means running long chain-of-thought generations on many paired items. The cheapest known way to measure a model with few items is adaptive testing, which picks each next question based on the previous answers. Adaptive testing asks one question at a time, and on a GPU that is close to the slowest possible way to spend a fixed number of questions.

This note proposes an adaptive contamination audit that asks its questions in a handful of rounds. Each round is a batch chosen to maximize information per measured GPU-second, not per question. The core observation is that for reasoning models, the wall-clock cost of a batch is set mostly by its longest generation, not by its item count. Selecting items for information alone can therefore produce batches whose latency is dominated by one 20,000-token straggler. We make that cost structure explicit and select batches under it, using thresholding ideas from parallel submodular optimization. We then ask whether such an audit can recover contamination that loss-based detectors miss, at a wall-clock budget smaller than simply running everything.

Core Claim

The claim is that contamination auditing for reasoning models has three properties that, taken together, have not been handled. It is best posed as joint estimation of a model's ability and its "contamination boost" on canonical (published) item forms. The estimate can be built in a small, logarithmic number of batched rounds without losing much accuracy relative to fully sequential testing. The right budget is measured latency, whose structure (a sum of prompt costs plus a maximum over generation lengths) admits a clean reduction to a few knapsack problems by grouping items into length buckets that grow geometrically.

Prior work covers pieces of this but not the combination. Psychometric adaptive testing for language models, in Efficiently Measuring the Cognitive Ability of LLMs: An Adaptive Testing Perspective, fits item response theory (a model of how question difficulty and test-taker ability set the chance of a correct answer). It reaches 0.90+ rank correlation with full leaderboards using 20% of items and flags contamination through anomalous answer patterns. It selects strictly one item at a time and counts items, not seconds. We keep its statistical core but change both the round structure and the unit of cost. Our contamination signal is also an explicit parameter estimated from paired item variants, rather than an anomaly read off a guessing term.

Research Program

Measurement model. Each benchmark item $i$ exists in a canonical form and in one or more fresh variants that are verified to be equivalent. For math these are numerically perturbed problems with programmatically checked answers, in the spirit of the objective scoring in LiveBench and the formal generation in A²RBench. For multiple-choice science questions they are reworded stems with shuffled options. We use the following model for the probability that a model with ability $\theta$ answers form $v$ of item $i$ correctly:

$$P(y_{iv}=1)=c_i+(1-c_i)\,\sigma\big(a_i(\theta-b_i)+\delta\,\mathbb{1}[v=\text{canonical}]\big).$$

Here $a_i$, $b_i$ and $c_i$ are the item's discrimination, difficulty and guessing level, calibrated on variant responses from a population of open models, $\sigma$ is the logistic function, and $\delta$ is the model's contamination boost. A per-item extension replaces $\delta$ with sparse item-level boosts.

The rewording-plus-shuffle variants are a deliberate choice. Rethinking Benchmark and Contamination for Language Models with Rephrased Samples shows that training on rephrasings lifts Llama-2-13B on MMLU from about 55 to about 86, so pure rewording may itself be "seen." That paper therefore constrains the variant design. The audit's contrast is between canonical forms and fresh, answer-changing variants.

Batch objective. At round $t$, with current estimates $(\hat\theta,\hat\delta)$, we score a candidate batch $B$ of (item, form) pairs by $f(B)=\log\det\big(I_0+\sum_{j\in B}J_j(\hat\theta,\hat\delta)\big)$. In this expression, $J_j$ is the 2×2 Fisher information that pair $j$ carries about $(\theta,\delta)$, and $I_0$ is the prior precision. This D-optimal design criterion is monotone and submodular. Pairing matters because a canonical item and its variant together are far more informative about $\delta$ than either is alone.

Latency-priced cost. For a batch run through a serving engine such as vLLM, we model round wall-clock as

$$T(B)\approx \alpha+\beta\sum_{j\in B}p_j+\gamma(|B|)\max_{j\in B}\ell_j.$$

Here $\alpha$ is fixed round overhead, $p_j$ the prompt tokens, $\ell_j$ the predicted output length, and $\gamma(|B|)$ the measured per-decode-step time at batch size $|B|$. $\gamma$ is nearly flat until the memory bandwidth saturates, and it is profiled per GPU. Output lengths are predicted from other models' recorded lengths on the same item, rescaled per model family.

The form of this cost comes from the FLOPs-latency literature, which motivates it. ShuffleNet V2 and Polyline Path Masked Attention for Vision Transformer show that operation counts mispredict runtime once memory traffic and dispatch overhead dominate. Threshold-Based Exclusive Batching for LLM Inference shows that the point at which mixed prefill/decode batching stops paying moves from 80% decode tokens on an H200 to 20% on a bandwidth-limited RTX PRO 6000. A single item-count budget therefore cannot be correct across hardware.

Batch selection. The max term makes the cost non-additive. We remove it by grouping candidates into length buckets $[2^m,2^{m+1})$. Within a bucket the max is known up to a factor of 2, so each bucket's subproblem is monotone submodular maximization under an additive knapsack. We solve it with a decaying-threshold rule: accept every candidate whose marginal gain per unit cost exceeds $\tau$, then shrink $\tau$ by $(1-\epsilon)$. This is the batching machinery that Breaking Barriers and Practical Parallel Algorithms for Non-Monotone Submodular Maximization develop for few-round optimization. We reuse it as a method source. Our objective is monotone, so the simpler monotone threshold analysis applies.

There are only $O(\log L)$ buckets for maximum length $L$, and we take the best one, or a small union under the round budget. The selection therefore loses at most a constant factor relative to the best latency-feasible batch, a guarantee we will state and prove. One distinction matters here. In those papers the expensive thing is evaluating $f$. Here $f$ is cheap CPU arithmetic, and the expensive thing is a round of model generations. The relevant notion of adaptivity is therefore the number of observation rounds. Results on stochastic submodular problems by Ghuge and colleagues, summarized in our source material, report that 6 to 7 rounds recover nearly all the value of fully sequential policies. That is the theoretical reason to expect few rounds to suffice.

Round schedule and stopping. Each round re-estimates $(\theta,\delta)$ and doubles the latency allowance of the next round. The audit stops when the posterior interval on $\delta$ excludes zero or falls below a target width. With a geometric schedule, the round count grows logarithmically in the total budget.

Baselines

The naive reference is uniform random sampling of item pairs, followed by a paired test of the canonical-versus-variant accuracy gap, at the same GPU-second budget. Its upper limit is running the entire paired pool in one maximally batched pass. That single-pass run is the oracle-quality answer and also the wall-clock ceiling any adaptive method must beat.

The strongest existing loss-based competitor is LiRA-style membership inference, evaluated as in On The Fragility of Benchmark Contamination Detection in Reasoning Models. That paper reports 89.1% AUROC before reinforcement learning, a drop of about 14% after one epoch of GRPO, and an average of 50–58% AUROC across ten detectors in its post-reasoning-model contamination stage. We run it with the same contaminated checkpoints and the same item sets. Beating it means exceeding its AUROC after GRPO at an equal or smaller GPU-second budget.

The strongest adaptive-testing competitor is the sequential item-response-theory test of Efficiently Measuring the Cognitive Ability of LLMs, reported at 0.90+ rank correlation with 20% of items. That paper gives no wall-clock figure, and we found no reported result on Lacuna for the wall-clock time of sequential adaptive testing of language models. We give it the identical two-parameter model, item calibration and variant pool, and change only the one-item rounds. Beating it means matching its final $\delta$ error and ranking quality in less wall-clock time.

Two active-testing baselines estimate accuracy rather than contamination, and they are adapted by applying them separately to canonical and variant pools. Scaling Up Active Testing to Large Language Models uses a small model's uncertainty to choose items for a large one and reports a median 32% reduction in risk-estimation error over random sampling. AcTracer clusters items by hidden activations and samples across clusters.

Two ablations isolate the key ingredient. The first, count-priced batching, uses the same rounds and objective but prices every item at 1. The second, bucketing off, prices by the additive part of the cost only. If the full method does not beat count-priced batching in wall-clock at equal estimation error, the latency model is not earning its place.

Why not just…?

Why not just run the whole paired pool in one batch? This is the most serious threat. It uses one round, saturates the GPU, and needs no estimation machinery. For short-answer benchmarks such as MMLU it will very likely win, and we will report that honestly. Our bet is restricted to long chain-of-thought evaluation over a pool expanded by variants. There, full-pool cost scales with pool size times typical generation length, while the audit needs only enough pairs to bound $\delta$. The decisive comparison is GPU-seconds to reach a fixed $\delta$ interval width. If the single batch matches us there, the adaptive part of the proposal fails.

Why not just batch the sequential test with a fixed batch size? This is the count-priced ablation, and it may capture most of the round-reduction benefit, since few rounds appear to suffice in stochastic settings. What it cannot do is avoid putting one very long generation into a batch of otherwise short ones. We will measure the fraction of round time spent waiting on the longest generation under both methods, on an L40S-class and an H200-class GPU. The exclusive-batching results suggest the gap should be larger on bandwidth-limited hardware.

Why not just use a better membership-inference detector? The fragility study tested ten detectors and found all near chance after reasoning post-training, and it attributes this to reinforcement learning shrinking the loss gap between seen and unseen questions. A new loss-based detector would have to overcome a mechanism, not just a tuning problem. We include LiRA so that the comparison is direct.

Why not just evaluate on fresh benchmarks like LiveBench and skip auditing? Fresh benchmarks avoid contamination going forward, but they do not tell you whether published scores on AIME or GPQA are inflated. They also carry ongoing curation cost. We treat LiveBench's post-cutoff, objectively scored items as a clean control pool: on them the audit should estimate $\delta \approx 0$.

Decisive Experiments

We follow the contamination protocol of the fragility study on AIME, AMC, GPQA Diamond, OlympiadBench and Minerva Math. We fine-tune on a known subset of canonical items, then run GRPO, using DeepSeek-R1-Distill-Llama-8B among other models, so that the ground truth for which models are contaminated is known. The reported pass@1 inflations (8.8% in the earlier stage, 11.7% in the later one) set realistic effect sizes. Clean checkpoints from the same recipe serve as negatives.

The primary metric is detection AUROC as a function of measured GPU-seconds. Secondary metrics are error in $\hat\delta$ against the measured canonical-minus-variant gap on the full pool, number of rounds, and wall-clock spent waiting on the longest generation in each round. A further check runs MMLU and GSM8K with short answers. There we expect the single-batch baseline to win, and confirming that marks the regime boundary honestly.

The proposal succeeds if three things hold. First, after GRPO the audit clearly exceeds the 50–58% AUROC band at less than a full-pool budget. Second, it reaches the sequential test's $\delta$ accuracy in a small fraction of that test's wall-clock using at most about ten rounds. Third, it beats count-priced batching on the bandwidth-limited GPU. Failing the third leaves a useful but smaller result: few-round paired auditing works, and pricing by latency does not matter.