Whether or Where? Tail Calibration Signals Finite-Budget Reward Hacking in Best-of-N Selection

Cheng Gui, Yihua Shao, Lei Li, Jingcai Guo, Maolin WangarXiv 2026 · arXiv

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.
Table 1: Tail regimes for bounded rewards. The first three rows assume independent additive error (Theorem 3.3); Gaussian and Laplace monotonicity follows from Proposition A.5. The last row assumes a unique scale maximizer (Proposition 3.4). Rates and further families are given in Appendix A.7.

Datasets

The study validates its findings across three levels:

  1. Synthetic Pools: 162 different settings using various priors (Uniform, Binary, Gaussian) and error distributions to test the "Hazard Trichotomy."
  2. 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).
  3. 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.
Figure 2: MATH-500 input-format controls on a fixed candidate pool. Each panel holds the reward model and all 500×256 answers fixed while varying only the score input: QA (blue circles), answer-only (orange-red triangles), masked question (teal squares), or deterministically shuffled question (magenta diamonds). The thin horizontal dotted line is base correctness.

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.
Figure 3: External PPE validation. (a) Top-12.5% tail excess for 13 learned reward models across five tasks. Negative cells concentrate on MBPP+. (b) Calibration-fold tail risk versus held-out gain from the calibration-selected cap, with two folds per learned cell. Cell-clustered bootstrap intervals are reported in Table 3.

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

Abstract

Best-of-N (BoN) inference returns the candidate with the highest proxy reward, so a larger $N$ tests the proxy's extreme tail more than its average ranking quality. We show that the exact BoN value is a Beta-weighted integral of conditional true reward over within-prompt score quantiles. It follows that BoN depends on scores only through their ranks. It also follows that BoN can decline only if the calibration curve in the tail turns downward, and the budget where the decline appears depends on where that turn lies. Under a bounded additive model, the error tail sets the limit: Gaussian errors keep improving, Laplace errors reach a plateau, and heavy-tailed errors return to the prior mean. When error variance is largest at low true reward, even Gaussian noise can push BoN below random selection. Synthetic phase maps agree with this taxonomy. On real candidate pools spanning several verifiable domains, base policies, and learned reward models, tail failures are rare and all occur in code generation. A held-out tail calibration statistic reliably predicts where a cross-fitted budget cap helps. It does about as well as rank accuracy, and the cap is competitive with a Soft-BoN baseline. Tail calibration therefore does not replace ranking metrics. It is an audit that is unchanged by any monotone rescaling of the reward scores and shows which budgets are at risk.
BibTeX
@misc{gui2026whether,
  author = {Cheng Gui and Yihua Shao and Lei Li and Jingcai Guo and Maolin Wang},
  title = {{Whether or Where? Tail Calibration Signals Finite-Budget Reward Hacking in Best-of-N Selection}},
  year = {2026},
  eprint = {2610.34375},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.34375},
}
Figure