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

arXiv: https://arxiv.org/abs/2610.08719 · HTML: https://mlsanity.com/paper/2610.08719/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 19 references that are in the map.
- First posted on arXiv 6 Oct 2026.

## Builds on (most cited first, 11 of 11)

- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [Let's Verify Step by Step](https://mlsanity.com/paper/2305.20050/) (2023)
- [Fine-Tuning Language Models from Human Preferences](https://mlsanity.com/paper/1909.08593/) (2019)
- [WebGPT: Browser-assisted question-answering with human feedback](https://mlsanity.com/paper/2112.09332/) (2021)
- [Agent-as-a-Judge: Evaluate Agents with Agents](https://mlsanity.com/paper/2410.10934/) (2024)
- [Helping or Herding? Reward Model Ensembles Mitigate but do not Eliminate Reward Hacking](https://mlsanity.com/paper/2312.09244/) (2023)
- [Adding Error Bars to Evals: A Statistical Approach to Language Model Evaluations](https://mlsanity.com/paper/2411.00640/) (2024)
- [Is Best-of-N the Best of Them? Coverage, Scaling, and Optimality in Inference-Time Alignment](https://mlsanity.com/paper/2503.21878/) (2025)
- [Inference-Time Reward Hacking in Large Language Models](https://mlsanity.com/paper/2506.19248/) (2025)
- [Soft Best-of-n Sampling for Model Alignment](https://mlsanity.com/paper/2505.03156/) (2025)
- [A Flexible Defense Against the Winner's Curse](https://mlsanity.com/paper/2411.18569/) (2024)

## Abstract (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≥ N≥2. At J=K-1, the selector deepens as K grows. For independent Gaussian scores with common variance and fixed M≥ N≥2, the unbiased minimax risk in this regime is of order σ2/√ 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/(π√2), which Holdout attains without knowing the variance. The cyclic average over subsets and ties can be computed in O(MKlog 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.