Permutation Tests That Account for Picking the Best Run

A typical benchmark claim reads "our model beats the baseline by 0.8 points, p < 0.05." Behind that sentence there are usually many runs: several random seeds, prompt templates, checkpoints, or decoding settings. All of them were scored on the same test set, and only the best one was reported. The p-value treats that winner as if it had been fixed in advance. It was not, so the claim is biased in a predictable direction. The Leaderboard Illusion simulates this on Chatbot Arena and finds that submitting the best of 10 private variants inflates a score by about 100 rating points. Genomics met the same problem long ago. In The choice of null distributions for detecting gene-gene interactions in genome-wide association studies, an apparent interaction with $p = 4.2 \times 10^{-7}$ fell to $p = 0.148$ once the whole screen-then-select pipeline was re-run under shuffled labels.

This note proposes a simple test for "best of N beats baseline" claims on static benchmarks. It is a permutation test, meaning the reference distribution for "no real difference" is built by randomly swapping which system produced which output. Two design choices make it fit the problem. First, the thing being tested is the maximum improvement over all N variants that were tried, so the selection step is inside the test. Second, labels are swapped for whole groups of related test items at once, such as all questions about one passage or all samples drawn for one problem, so that correlated items do not fake significance. The test is exact when the per-item outputs of every variant are logged. When they are not, it falls back to a valid but weaker correction. That difference turns disclosure of discarded runs into a measurable gain in statistical power, which gives researchers a reason to report them.

Core Claim

Existing permutation-based tests for model comparison all fix both systems ahead of time. When LLMs get significantly worse uses exact McNemar tests and paired permutation tests to check whether an optimized model is worse than its parent. Reward Auditor runs paired permutation tests on reward-model confidence scores, with a Benjamini–Hochberg correction across perturbation scenarios. Follow the leader(board) with confidence pools two systems' responses to simulate the null for one pre-specified pair. None of them models the step in which the reported system was chosen, from many candidates, on the very test set used to evaluate it. We claim that a max-statistic permutation over the full set of tried variants gives Type I error control at the nominal level for post-selection claims, where naive tests do not. We further claim that because LLM variants are strongly correlated with one another, this test keeps much more power than Bonferroni correction, while needing no held-out split.

Here is the procedure. Let $s_{ij}$ be the per-item score (accuracy, reciprocal rank, ROUGE-L) of system $j$ on test item $i$, where $j = 0$ is the baseline and $j = 1, \dots, N$ are the variants that were tried. The observed statistic is

$$T = \max_{1 \le j \le N} \frac{1}{n} \sum_{i=1}^{n} (s_{ij} - s_{i0}),$$

the largest mean improvement over the $n$ test items. To build the null distribution, we draw one random permutation of the system labels $\{0, \dots, N\}$ for each cluster $c$ of related items, apply it to every item in $c$, and recompute $T$. After $B$ such draws, the p-value is the fraction of permuted statistics that are at least as large as the observed $T$, with the usual add-one correction.

The null hypothesis is that, within each cluster, the $N+1$ systems' outputs are exchangeable. In words: none of the variants differs in distribution from the baseline, so shuffling system labels would not change the joint distribution of scores. Under that null the test is exact in finite samples. When clusters are single items, the design reduces to the within-item swapping used by the degradation paper, extended from two systems to $N+1$. When clusters are larger, it becomes the blocked permutation that Multivariate classification of neuroimaging data with nested subclasses showed is needed when data has nested groups. That paper found an EEG decoder at 54.2% accuracy that looked significant until blocked permutation placed the true chance level at 50.9%.

Research Program

The work has three parts.

The first part builds a variant testbed with a known ground truth. We take open-weight models and generate N variants of each. Some variants are ones the degradation paper found to be statistically lossless (H100 versus A100 inference, FP8 quantization), so they serve as realistic null variants. Others are ordinary sources of researcher freedom: random seeds, prompt templates, few-shot orderings, and sampling temperatures. We score every variant per item on the Open LLM Leaderboard v2 tasks (BBH, GPQA, IFEval, MATH hard, MMLU-Pro, MuSR) and log the full score matrix. Clusters are defined in one of two ways. The first is items that share a source, such as MuSR questions about the same narrative or BBH items within a subtask. The second is repeated samples on the same MATH problem when outputs are stochastic. To test power, we add known true improvements, either by including one genuinely stronger checkpoint among the variants or by flipping a controlled fraction of wrong answers to correct, following the degradation paper's perturbation design.

The second part is measurement. We measure how correlated variants are, per item, on each task. This one quantity determines how much the max-statistic test gains over Bonferroni: if variants were independent, the max-statistic test would be no better than Šidák correction. If measured correlations turn out low, the power argument weakens, and we will say so. We also measure the "disclosure dividend," defined as the ratio of the fallback (Bonferroni) p-value to the max-statistic p-value, across realistic values of N. This quantifies what a researcher gains by releasing discarded runs, and it answers the incentive gap that BetterBench documents, where 14 of 24 benchmarks report no uncertainty at all.

The third part is a retrospective audit. On MS MARCO-style ranking (per-query reciprocal rank) and on model families where we can regenerate outputs, we re-examine published "best of several" claims. Significant Improvements over the State of the Art? found that it took five successive leaderboard leaders, an MRR gain of 2.4 points, before one was significantly better than the first, and that analysis used Wilcoxon tests with no adjustment for selection. We expect selection-aware testing to make that picture stricter. The size of that tightening is an open empirical question.

The computation is cheap. Because $T$ is a maximum of means, each permutation costs time proportional to $nN$. The binning method of Cheap Permutation Testing is designed for quadratic statistics and is only needed if the approach is extended to metrics that do not decompose per item.

Baselines

The do-nothing reference is the practice in current papers: a two-sided paired permutation test, or exact McNemar test for 0/1 scores, between the reported winner and the baseline, with the winner treated as fixed in advance. This is the degradation paper's method applied as if no selection had happened. We run it on the same score matrices and the same number of permutations $B$. We expect its false-positive rate in null testbeds to rise steadily with N. Its known strength is sensitivity: the degradation paper reports reliably detecting accuracy degradations as small as 0.3%, and reports that ignoring pairing inflates uncertainty by roughly 2.2x. That 0.3% figure is the power target our test should approach when N = 1, where the two tests coincide.

The strongest valid competitors are Bonferroni- or Šidák-corrected paired tests on the winner, and a held-out selection split, where the winner is chosen on one half of the test set and tested on the other half. Both control false positives, so the comparison is about power. All methods see the same items, variants, and permutation budget. We beat these competitors if, at matched nominal level (5%) and matched total test-set size, the max-statistic test detects injected improvements with higher power while its empirical false-positive rate stays within Monte Carlo error of 5%. We found no reported result on Lacuna for selection-corrected tests on LLM benchmarks, so these numbers will be produced here.

One ablation isolates the cluster ingredient: the same max-statistic test with item-level instead of cluster-level permutation, run on MATH with repeated sampling and on MuSR. If item-level swapping gives inflated false-positive rates only where clusters exist, that shows blocking is doing real work. A second ablation drops the max, testing only the winner under cluster permutation, to show that selection alone accounts for the inflation.

Why not just…?

Why not just apply Bonferroni over the N variants? It is valid, and it is the fallback we use when variant outputs are not disclosed. But it assumes nothing about correlation between variants. Seeds and prompt formats of the same model agree on most items; the degradation paper reports only 1.3% to 2.8% of answers flipping across hardware. When variants are that similar, Bonferroni with N = 20 charges for 20 independent chances when the effective number is far smaller. This is a real threat if measured correlations turn out low. The correlation measurement in part two settles the question: we report the power gap as a function of observed correlation, not just assert it.

Why not just hold out half the test set for confirmation? This is the cleanest competitor and is fully valid. It gives up half the test items, though, and benchmarks like GPQA are small, so halving them hurts. It also only works if researchers actually commit to the split before looking. Our power comparison at matched total n directly measures what the split costs. If the split's power is close to ours at realistic N, we will recommend it as the simpler practice.

Why not just report expected best-of-n performance or the average over seeds? A Boo(n) for Evaluating Architecture Performance proposes reporting the expected maximum over n runs, which honestly describes the selection lottery. It is a descriptive estimate, though, not a test against a specific baseline on a shared test set, and it gives no p-value for the claim authors actually make. The two are complementary: Boo(n) summarizes performance, and our test decides whether that performance beats the baseline.

Why not just bootstrap a confidence interval for the winner's gain? Resampling items and recomputing the maximum is known to behave badly for maxima and gives only approximate coverage. The Hitchhiker's Guide to Testing Statistical Significance in NLP groups bootstrap and permutation together as sampling-based options but does not address selection. We include the bootstrap-of-max as an extra arm in the null testbed. Its false-positive rate relative to 5% will show whether this concern matters in practice.

Decisive Checks

Three results would confirm or refute the proposal. First, in null testbeds with N ranging from 2 to 30, the max-statistic cluster test must hold false positives near 5%, while the naive test's rate must rise with N. If the naive rate does not rise, selection is not a practical problem at these effect sizes, and the project stops. Second, at matched test-set size, the max-statistic test must show meaningfully higher power than both Bonferroni and the held-out split for injected gains of around one point. Third, item-level permutation must inflate false positives on clustered tasks (MATH with repeated samples, MuSR) but not on unclustered ones. If that pattern fails to appear, the blocked design is unnecessary for these benchmarks and should be dropped from the recommendation.