When a language model trains on a benchmark file, it learns the questions and answers, and it also learns the arbitrary order in which the benchmark authors happened to list the answer options. A clean model has no reason to prefer that particular order over a reshuffled one, apart from ordinary readability. A contaminated model does prefer it. We propose to audit contamination by asking a sharp question of each test item: is the released ordering of its options a local maximum of the model's likelihood over all orderings? The comparison is always between the same content in different orders. That makes the signal self-normalizing in a way that token-loss detectors are not, and we hypothesize that this is why it can survive the reinforcement-learning post-training that currently defeats nearly every detector.
The practical obstacle is that the space of orderings grows factorially. It has 24 points for a 4-option question and 3.6 million for the 10-option questions in MMLU-Pro, and every point costs a full forward pass through a large model. Differentiable permutation relaxation makes discrete orderings amenable to gradients by replacing them with "soft" permutation matrices whose rows and columns each sum to one, the so-called doubly stochastic matrices. We use it as the search engine. One backward pass at the released ordering estimates how much the likelihood would change under every possible swap at once, and a few gradient steps inside the space of soft permutations locate the model's preferred ordering. Exact forward passes then verify every candidate the relaxation proposes, so the relaxation affects only cost and search quality. It never changes the reported statistic.
Core Claim
The claim is empirical and falsifiable. Maximum-likelihood training on a benchmark file makes the released option ordering a strict local maximum in order space. In a controlled contamination setting where the released order is secretly randomized, the size of that maximum separates seen from unseen items. It keeps doing so after clean reinforcement learning, which drives loss-, LiRA- and Min-K%-style detectors toward chance.
This transplants the key insight of Min-K%++, which argues that training instances become local maxima of the model's distribution over token substitutions. We move it from token space to the space of orderings. There the "neighbors" of an item are its reorderings, not its token substitutions.
The motivation comes from two findings in the file. First, On The Fragility of Benchmark Contamination Detection in Reasoning Models shows that one epoch of clean GRPO (a reinforcement-learning method for reasoning models) after supervised contamination compresses the loss gap between seen and unseen items. LiRA falls from 89.1% AUROC by roughly 14 points and loss-based detection by roughly 16. Detectors applied to contaminated reasoning models land at 50–58% AUROC. Second, ABCD: All Biases Come Disguised observes that models assign lower perplexity to the canonical option order of MMLU-Pro than to permuted orders. Our work turns that observation into an audit, but ABCD's observation has a confound that we must remove. Benchmark authors often order options naturally, for example numbers ascending or "none of the above" last, so a perfectly clean model may also prefer the canonical order. Much of our design exists to separate memorized order from natural order.
The Statistic and How It Is Computed
For a test item with options $o_1,\dots,o_n$ released in order $\pi_0$, let $L(\pi)$ be the model's log-likelihood of the full prompt with options placed in order $\pi$. Let $\mathcal{N}(\pi_0)$ be the orderings reachable from $\pi_0$ by one transposition of two options. The order margin is
$$ Z(x) = \frac{L(\pi_0) - \max_{\pi \in \mathcal{N}(\pi_0)} L(\pi)}{\operatorname{sd}_{\pi \in \mathcal{N}(\pi_0)} L(\pi)} . $$
Here $Z(x)$ is positive when the released order beats all of its neighbors, and "sd" is the standard deviation of likelihood across those neighbors. Dividing by that spread plays the same role as the vocabulary normalization in Min-K%++. It makes items of very different difficulty comparable without any reference model. We also report a global version: whether $\pi_0$ is the best ordering the search can find anywhere.
Computing $Z$ exactly takes $n(n-1)/2$ forward passes per item, which is 45 for MMLU-Pro. Finding the global mode exactly is out of reach. We use the relaxation in two ways.
The first use is local. Each option is padded to a common slot length, and the input embedding of slot $k$ is written as $\sum_j P_{jk}\,\bar e_j$, where $\bar e_j$ is the padded embedding sequence of option $j$ and $P$ is a doubly stochastic matrix. At $P$ equal to the released permutation matrix, the forward pass is exactly the real text. A single backward pass gives $\partial L/\partial P$. This is a first-order estimate of how the likelihood changes when option $j$ moves into slot $k$, and it ranks all transpositions at once.
The second use is global. We run a handful of projected ascent steps using the temperature-controlled Sinkhorn operator of Gumbel-Sinkhorn Networks, which repeatedly rescales rows and columns until they sum to one. We anneal the temperature toward a hard permutation and round the result with the Hungarian algorithm. Every candidate that either stage proposes is scored with a true forward pass on real text.
The relaxation is therefore a proposal mechanism. Its known weaknesses stay contained: its memory cost grows as $n^2$ (noted for SoftSort), unrolled Sinkhorn iterations are unstable, and padded mixtures are off-manifold inputs. These can make the search worse, but they cannot bias the verified statistic. We choose Sinkhorn over row-stochastic argsort relaxations such as NeuralSort and SoftSort for a concrete reason. We are permuting whole text segments into slots, which is an assignment problem, not sorting a vector of scores. Differentiable extensions with rounding guarantees supplies the rounding theory we rely on when moving from soft to hard permutations.
Research Program
The program has three parts: a causal testbed, a naturalness control, and a post-training stress test.
Causal testbed. We contaminate open models of 1.5B to 8B parameters. Each benchmark item is shown in a secret, uniformly random option order, and half the items are held out as unseen. Because the injected order is random, a clean model has zero expected preference for it. This removes the naturalness confound by construction and gives exact ground truth. We vary three things. The first is exposure type: verbatim, paraphrase, shuffled-at-train-time (meaning the order signal should vanish), and answer-only, matching the injection hierarchy in When Is Benchmark Contamination Detectable?. The second is duplication count, since Data Contamination: From Memorization to Exploitation finds that duplication drives exploitation. The third is when during training the exposure happens.
Naturalness control. For audits of released models on released benchmarks, where no secret order exists, we estimate how strongly a clean model prefers the canonical order. We do this in two ways. First, we restrict the audit to items whose options carry no ordering cues, which we identify by a rule-based filter for numerals, "all/none of the above", and ordinal words. Second, we compare each model's $Z$ distribution against the same statistic on post-cutoff items of the same format. The gap between the two is the contamination estimate.
Post-training stress test. We follow the Stage I protocol of the fragility paper. A model is contaminated through supervised fine-tuning, then trained with one and three epochs of clean GRPO. We track the AUROC of $Z$ against the detectors that paper shows collapsing. Our mechanistic hypothesis concerns where GRPO applies its loss. GRPO optimizes likelihood on completions, not on prompt layout. Clipping compresses the absolute log-probability spread that loss detectors depend on. However, $Z$ compares the same prompt with itself under reorderings, so a global compression of spread should rescale numerator and denominator together. Stage II, which contaminates DeepSeek-R1-Distill-Llama-8B with chain-of-thought data, tests whether $Z$ still separates items when the model generalizes a reasoning template to unseen items.
Baselines
The naive reference point is ABCD-style raw canonical-order preference. It is the difference between the log-likelihood of the released order and the mean over a few random shuffles, with no neighborhood structure and no normalization. It represents the signal already observed in ABCD, for which the file reports no quantitative per-subject result. Beating it means higher AUROC on the causal testbed at the same forward-pass budget.
The strongest discrete competitor is exact local search. We compute $Z$ with all $n(n-1)/2$ transpositions by brute force and look for the global mode with greedy pairwise-swap hill climbing. On 4-option GPQA Diamond and ARC-Challenge, full enumeration of all 24 orders is feasible, which gives ground truth for the relaxed search. The relaxed method must reach the exact $Z$, with Spearman correlation above 0.9 on 10-option MMLU-Pro, at no more than a quarter of the forward-plus-backward compute. Otherwise we drop the relaxation and report the discrete statistic alone.
The strongest existing detectors are LiRA, loss thresholding and Min-K%++. The fragility paper reports 89.1% AUROC for LiRA under supervised contamination before GRPO, a drop of roughly 14 points after one clean GRPO epoch, and 50–58% AUROC for ten detectors in Stage II. For Min-K%++ the file reports only a relative gain of 6.2–10.5 AUROC points over Min-K% on WikiMIA. No absolute post-RL number for it was found on Lacuna, so we run it ourselves on identical checkpoints. All detectors see the same items, the same checkpoints and the same number of model evaluations per item. Hyperparameters, meaning $k$ for Min-K%++ and the neighborhood size for $Z$, are tuned on a held-out injection split. Beating these detectors means $Z$ keeps AUROC above 0.75 after clean GRPO where they fall below 0.6.
We also compare against two perturbation-based methods. CAP shuffles options and paraphrases, then measures the resulting performance-consistency ratio. The file reports no AUROC for CAP. ConStat reports detecting 98.4% of sample-specific contamination against 71% for the best prior baseline, using 20 clean reference models. We run ConStat with its reference pool and separately with a reference pool that we deliberately contaminate. The second condition tests whether $Z$ remains valid when clean references are unavailable.
Two ablations isolate the key ingredients. The first drops the neighborhood normalization. The second replaces the relaxed search with random proposals at equal budget, which shows whether the gradient adds anything.
Why not just…?
Why not just shuffle the options a few times, as CAP does? Random shuffles compare the released order with orderings that are mostly far away. They measure a global average rather than whether the released order is a peak. Shihab et al. find that shuffling-type signals have low behavioral separability. This matters because they bound detectability by $\alpha\rho\sqrt{m}$, where $\alpha$ is the contaminated fraction, $\rho$ is separability and $m$ is the number of audited items, so low separability forces large audit budgets. We estimate separability for both statistics on the testbed and run their two-stage planner to report the $m$ each requires. If random-shuffle z-scores reach the same separability, the neighborhood idea is unnecessary, and the ablation will show that.
Why not just brute-force the transpositions and skip the relaxation? This is a real threat, especially for 4-option benchmarks, where enumerating all 24 orders is trivial and the relaxation has no job. The relaxation earns its place only at large $n$ (MMLU-Pro, and permuted few-shot demonstration sets with 8 or more examples) and when auditing many models at scale. The equal-compute comparison in the Baselines section decides the question. If brute force matches at acceptable cost, we report the order-margin audit as the contribution and the relaxation as a negative result.
Why not just use paraphrase-based methods like ConStat? Paraphrasing tests whether the model generalizes beyond the surface form. The fragility paper shows that reasoning models trained on chain-of-thought contamination generalize the template to unseen items, which erases exactly that gap. Structural convergence detection finds that paraphrasing barely moves its detector, with AUC going from 0.72 to 0.71. ConStat also needs clean reference models. $Z$ needs neither a paraphraser nor references. The deliberately contaminated reference pool tests whether that independence matters in practice.
Why not just evaluate with Matched-and-Dashed? M&D is ABCD's evaluation protocol: it removes option letters, has the model generate the answer text, and matches the generation to an option by embedding similarity. It reduces order sensitivity at evaluation time, which is the opposite of our goal. We want to exploit order sensitivity as evidence of exposure to the benchmark file. The two are complementary. M&D protects scores from order bias, while $Z$ asks whether the benchmark was seen.
Proposed Experiments and Decisive Checks
We use GPQA Diamond and ARC-Challenge for exact validation of the search, MMLU-Pro for large-$n$ search, and CSQA as a check on generality across formats. The causal testbed uses these benchmarks with secret random orders. Post-training uses the fragility paper's Stage I and Stage II protocols. Metrics are AUROC and TPR at 5% FPR, both computed on held-out injections, plus estimated separability, the required audit size $m$, and compute per item. For comparison, structural convergence reports about 6.65 seconds per item.
Three results would be decisive. First, the statistic must be null where it should be: on the shuffled-at-train-time injection and on clean models with secret random orders, $Z$ must be indistinguishable from chance. Failing this means the statistic measures naturalness or format rather than exposure. Second, $Z$ must hold its AUROC through clean GRPO while LiRA, loss and Min-K%++ collapse on the same checkpoints. If it collapses too, the self-normalization hypothesis is wrong, and that is itself informative about what clipping erases. Third, on released models auditing released MMLU-Pro, the naturalness-controlled gap must line up with the direction ConStat flags on overlapping benchmarks. A caveat applies to scope: the method needs gradients, so for closed models only the discrete, forward-pass version of $Z$ is available. We report that version separately rather than overstating reach.
References
- Min-K%++: Improved Baseline for Pre-Training Data Detection from Large Language Models
- On The Fragility of Benchmark Contamination Detection in Reasoning Models
- ABCD: All Biases Come Disguised
- Learning Latent Permutations with Gumbel-Sinkhorn Networks
- SoftSort: A Continuous Relaxation for the argsort Operator
- Stochastic Optimization of Sorting Networks via Continuous Relaxations
- Differentiable extensions with rounding guarantees for combinatorial optimization over permutations
- Data Contamination: From Memorization to Exploitation
- CAP: Data Contamination Detection via Consistency Amplification
- ConStat: Performance-Based Contamination Detection in Large Language Models
- Detecting RLVR Training Data via Structural Convergence of Reasoning