TL;DR
Best-of-$N$ (BoN) selection is a popular "free lunch" for improving LLM outputs, but it eventually succumbs to "inference-time reward hacking" where quality drops as the selection budget $N$ increases. This paper proves that this failure is driven by the tail calibration of the reward model—specifically, how the model behaves at extreme score quantiles—and introduces a practical audit to predict and prevent these failures.
What Problem Does This Paper Address?
Inference-time alignment via Best-of-$N$ (BoN) selection is simple: sample $N$ responses from a model, score them with a reward model (RM), and pick the winner. While this usually improves performance, pushing $N$ too high can lead to a "turnover" where the proxy reward keeps climbing, but the actual correctness of the output collapses.
The core challenge is that standard reward model metrics (like average accuracy or calibration) look at the entire distribution of scores. However, BoN is an extreme-value search; at $N=64$, half of the selection mass sits in the top 1% of scores. A reward model can look perfect on average but harbor a "defect" in its extreme tail that only manifests at high selection budgets. Practitioners currently lack a principled way to diagnose if a reward model is at risk or to determine the optimal budget $N$ before performance degrades.
Methods
The authors provide a theoretical and empirical framework to link BoN performance to the reward model's tail behavior:
- Quantile Representation: They show that the expected value of BoN is a Beta-weighted integral of the true reward over score quantiles. This proves that BoN depends only on the ranks of the scores, making it invariant to monotone rescaling.
- Hazard Trichotomy: Under an additive noise model ($S = R + \epsilon$), they categorize how the tail of the error distribution ($\epsilon$) dictates BoN scaling (see Figure 6):
- Gaussian tails: Quality improves indefinitely (monotone).
- Laplace tails: Quality reaches a plateau.
- Heavy tails (e.g., Student-t): Quality eventually returns to the prior mean (hacking).
- Tail Excess Statistic ($E_{tail}$): They introduce a simple diagnostic that measures the average true reward in the top quantile (e.g., the top 12.5% or 1%) relative to the prompt mean. A negative $E_{tail}$ indicates that the reward model is "fooled" by incorrect answers in its extreme tail.
- Cross-fitted Audit: A procedure where one half of a dataset is used to estimate $E_{tail}$ and pick a budget cap, and the other half validates whether that cap prevents hacking.
Datasets
The study validates its findings across three levels:
- Synthetic Pools: 162 different settings using various priors (Uniform, Binary, Gaussian) and error distributions to test the "Hazard Trichotomy."
- Controlled MATH-500/GSM8K: A custom dataset where Qwen2.5-7B-Instruct generated 256 answers per prompt. These were scored by four different reward models (Skywork, Llama-3.2, Tulu-3, Qwen3) under different input formats (e.g., QA vs. answer-only).
- Public Preference Evaluation (PPE): A large-scale validation using 65 learned task-RM cells across domains like MATH, GPQA, MMLU-Pro, MBPP+, and IFEval.
Key Insights and Ideas
- The Tail is Destiny: Whether hacking is possible depends entirely on the class of the error tail (e.g., heavy-tailed vs. light-tailed). Where the hacking appears (at what $N$) is determined by the correlation between the proxy and true reward.
- Scale Beats Shift: If a reward model has higher variance for low-quality answers (heteroskedasticity), BoN can actually perform worse than random selection at high $N$.
- Format Matters: In the MATH-500 study (Figure 1), the authors found that removing the question and providing only the answer to the reward model ("answer-only") triggered severe reward hacking that wasn't present in the standard QA format.
Key Results
- Hacking is Localized: In real-world models, tail failures are relatively rare but highly concentrated in code generation (MBPP+).
- Predictive Power: The tail risk statistic ($-E_{tail}$) is a highly reliable predictor of hacking, achieving an AUC of 0.983 in identifying cases where a budget cap would help (Figure 5).
- Effective Mitigation: The proposed calibration-selected budget cap is competitive with more complex baselines like Soft-BoN, particularly in the most severe hacking regimes.
Limitations and Future Work
- Requirement for Labels: The proposed audit requires ground-truth labels (verifiable correctness) to calculate $E_{tail}$, meaning it cannot be used on purely subjective tasks without human labels.
- Fixed Candidate Pools: The analysis focuses on selection from a fixed pool; it does not directly address iterative RLHF or PPO, though the authors suggest the "tail-first" explanation of hacking likely applies there too.
- Step-level Rewards: The study focuses on outcome-level reward models and does not evaluate Process Reward Models (PRMs), which are increasingly common in reasoning tasks.
Summary updated