Sharp Bounds on the Winner's Bias under Independent and Nonnegatively Correlated Noise

Ivan Viakhirev; Kirill Borodin; Grach Mkrtchian

cs.LGOct 22, 2026

Sharp Bounds on the Winner's Bias under Independent and Nonnegatively Correlated Noise

Authors: Ivan Viakhirev, Kirill Borodin, Grach Mkrtchian

Organizations: lab260 (lab260.ru) · BitmanagerAI (bitmanager.ai)

Abstract

Reporting the best of $M$ noisy, unbiased scores overstates the winner's value by up to $c\sqrt{V}$ , where $V$ is the total noise variance and the sharp constant $c$ depends on how the noise is dependent. It was known only at the two extremes, arbitrary dependence ( $\sqrt{(M-1)/M}$ ) and i.i.d. noise. We determine it for two classes in between: for independent, not identically distributed noise it is $\sqrt{(M-1)/(2M)}$ , and for pairwise nonnegatively correlated noise it is $(M-1)/M$ ; for uncorrelated noise this answers the maximum version of an open question about the expected range. Explicit finite constructions attain both. As a corollary, the bias of the cross-validation estimator is bounded sharply within each class. All theorems are formally verified in Lean 4. Across 448 language-model and classifier selection pipelines, designs with per-candidate items realize a median 0.75 of the independent-class ceiling. At a fixed item budget, scoring all candidates on shared items is markedly less optimistic than giving each candidate its own items.

Figures & tables

dependence class	sharp constant	first proved	attainment
arbitrary	$\sqrt{(M-1)/M}$	Aven 1985 / Arnold–Groeneveld 1979	exact
pairwise $\operatorname{Cov}\geq 0$	$(M-1)/M$	this paper	exact
independent	$\sqrt{(M-1)/(2M)}$	this paper	exact
i.i.d.	$(M-1)/\sqrt{M(2M-1)}$	Gumbel 1954 / Hartley–David 1954	exact

Table 1: The graded family of sharp constants

\sup\mathbb{E}[\max_{i}Z_{i}]/\sqrt{V}

by dependence class. “Exact” means the supremum is attained at finite parameters.

$M$	arbitrary	$\operatorname{Cov}\geq 0$	independent	i.i.d. worst case	Gaussian i.i.d.
2	0.707	0.500	0.500	0.408	0.399
3	0.816	0.667	0.577	0.516	0.489
4	0.866	0.750	0.612	0.567	0.515
5	0.894	0.800	0.632	0.596	0.520
10	0.949	0.900	0.671	0.653	0.487
20	0.975	0.950	0.689	0.680	0.418

Table 2: Worst-case constants against the Gaussian value: the last column is

\mathbb{E}[\max_{i}Z_{i}]/\sqrt{V}

for i.i.d. standard Gaussian noise, the same comparator in every row; the other columns are the sharp constants of Table 1 . Entries are rounded to three decimals, and the percentages quoted in the text are computed from the exact values.

Figure 1: Configuration cells of Sec. 5 : one marker per population, pool size

M

, item budget and design; scores in accuracy points. (a) Measured

\mathbb{E}[\max_{i}Z_{i}]

against the class ceiling

c\sqrt{V}

, log–log. Solid: the ceiling, which no marker exceeds; dotted: half of it. (b) Optimism against total item budget

n

M=8

on MMLU-Pro, log–log; colour is the design, dashed lines are the matching ceilings. Per-candidate items (

n/8

each) lie above shared items throughout. (c) Measured optimism over that of a Gaussian model with matched covariance, against items per candidate (

n

shared,

n/M

per-candidate; log scale); below 1, the Gaussian model overstates. Only cells resolved to three standard errors are shown.

population	$N$	design	items	optimism		regret	$\mathbb{E}[\max_{i}Z_{i}]$	ceiling	$\rho$	Gaussian
MMLU-Pro	4000	shared	64	3.09 $\pm$	0.04	0.44	5.15	14.86	0.346	3.05
MMLU-Pro	4000	per-cand.	8	18.87 $\pm$	0.07	2.54	24.07	31.78	0.757	19.02
GSM8K	1319	shared	64	1.09 $\pm$	0.02	0.48	4.27	10.92	0.391	1.17
GSM8K	1319	per-cand.	8	6.87 $\pm$	0.02	0.45	17.59	23.34	0.754	8.90
ARC-Challenge	1172	shared	64	1.75 $\pm$	0.02	0.42	2.54	8.81	0.288	1.87
ARC-Challenge	1172	per-cand.	8	8.18 $\pm$	0.01	0.30	10.05	18.84	0.534	13.13

Table 3: Optimism and regret of best-of-

M

selection at

M=8

with a fixed budget of 64 items, under both evaluation designs: shared items (

\operatorname{Cov}\geq 0

class, 64 items per candidate) and per-candidate items (independent class, 8 items each; “per-cand.” in the table). Scores are percentage points of accuracy; 20,000 replications per cell. Optimism is

\mathbb{E}[\hat{a}_{I}]-\mu^{*}

, regret is

\mu^{*}-\mathbb{E}[\mu_{I}]

, the ceiling is

c\sqrt{V}

for the design’s class,

\rho

is the fraction of that ceiling realized by the measured

\mathbb{E}[\max_{i}Z_{i}]

, and the last column is the optimism a Gaussian model with the matched covariance predicts.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

paper	Lean	file
Lemma 1, bias ranges	Transfer.transfer , me_bias_mem , cv_bias_mem	Transfer
Theorem 1	Master.master_bound	Master
Corollaries 1a, 1b (bounds)	cor1a_bound , cor1a_eq_iff , cor1b_bound , cor1b_strict	Master
Corollaries 1a, 1b (attaining laws)	Attain1.Y_ratio , pair_ratio , shock_attains	Attain1
Theorem 2	theorem2 , theorem2_measure , theorem2_sup	Independent
Theorem 3	theorem3 , theorem3_measure , theorem3_sup	Independent

Appendix

Table 4: Paper results and the Lean theorems that verify them.

Cross-Validation

See all 16 papers

Holdout Best-of-N: Unbiased Evaluation and Its Cost
Oct 6, 2026Shrey Shah, Yinheng LiBest-of-N Sampling Policy Evaluation
Evaluator Ensembles Under Reward Hacking: Covariance Geometry and Finite-Search Guarantees
Aug 8, 2026Fariya Afrin, Ibne Farabi ShihabReward Hacking LLM Evaluation
Department of Computer Science, Kalinga Institute of Industrial Technology · Department of Computer Science, Iowa State University
When LLM Judge Scores Look Good but Best-of-N Decisions Fail
Mar 12, 2026Eddie LandesbergLLM Evaluation LLM-as-a-Judge

Oct 6, 2026J/K move · Enter open · S save

Holdout Best-of-N: Unbiased Evaluation and Its Cost

Shrey Shah, Yinheng Li

Best-of-N Sampling Policy Evaluation Minimax Estimation Reward Model Evaluation

Open paper AskPDF arXiv

Reusing the scores that select a Best-of-

N

winner can overstate its expected reward. We study evaluation from a fixed matrix of

K

independent scores per candidate for a policy that selects using

J

fresh scores. A single estimator based only on this matrix is exactly unbiased for expected judge reward under every independent, stable collection of candidate-specific score laws if and only if

J<K

, for every pool size

M\ge N\ge2

. At

J=K-1

, the selector deepens as

K

grows. For independent Gaussian scores with common variance and fixed

M\ge N\ge2

, the unbiased minimax risk in this regime is of order

σ^2/\sqrt K

, attained by Holdout; allowing bias improves the rate to

σ^2/K

. For two candidates, we derive the minimum-variance unbiased estimator at known variance and the sharp asymptotic unbiased minimax constant

1/(π\sqrt2)

, which Holdout attains without knowing the variance. The cyclic average over subsets and ties can be computed in

O(MK\log M)

operations. At fixed selector depth, cyclic evaluation of bounded scores has

O(K^{-1})

risk uniformly in pool size. The impossibility result concerns the fixed matrix: one additional fresh winner score permits unbiased evaluation of the all-

K

policy.

Abstract

Cross-Validation

Explore similar work

Holdout Best-of-N: Unbiased Evaluation and Its Cost

Evaluator Ensembles Under Reward Hacking: Covariance Geometry and Finite-Search Guarantees

When LLM Judge Scores Look Good but Best-of-N Decisions Fail