Tail Competition Explains Scaling in Best-of-N Sampling for Verifiable Problems

AI summary

Overview

Research area: Inference-time scaling for large language models, specifically the theory of Best-of-N (BoN) sampling under imperfect reward models, combining extreme value theory (EVT) with reward-model analysis.

Technical level: Advanced. The paper relies on the Fisher–Tippett–Gnedenko theorem, asymptotic regime classification, and finite-sample scaling laws that will be difficult to follow without a background in probability or statistics.

Scope: A theoretical and empirical study arguing that BoN success and failure are both governed by a competition between the upper reward tails of correct and incorrect responses, plus a label-free early-stopping rule derived from that view.

Note: the supplied paper content is truncated in the Related Work section, so the full related-work discussion is not summarized here.

What This Paper Is About

Best-of-N sampling generates several candidate answers with an LLM and keeps the one that scores highest under a reward model. Prior work shows that if you could always pick a correct answer, the probability of success rises exponentially with the number of samples — but real reward models are imperfect proxies, so BoN sometimes improves, sometimes saturates, and sometimes gets worse as you sample more (reward hacking). This paper asks when and why each of those behaviors happens, and answers it by treating BoN as a race between the extreme high-reward tail of correct responses and the extreme high-reward tail of incorrect responses.

Key Contributions

1. A tail-competition framing of BoN. The authors recast selection success as the event that the maximum reward among correct responses exceeds the maximum reward among incorrect responses, and use extreme value theory to classify behavior into three asymptotic regimes: correct-tail-dominant, incorrect-tail-dominant, and critical.

2. Finite-sample scaling laws. They derive explicit scaling laws for the Gumbel, Fréchet, and Weibull domains of attraction, showing that an incomplete selector can converge polynomially in n rather than exponentially, unlike oracle selection.

3. A label-free early-stopping rule. They propose "tail-tension early stopping," which fits a two-component Gaussian mixture to observed reward scores, uses the high-mean component as a proxy for correct responses and the low-mean component as a proxy for incorrect responses, and stops sampling before the planned budget when the incorrect tail is predicted to take over.

4. Empirical validation. They test the predicted phases, scaling laws, and the stopping rule on synthetic Gaussian data and on real reward-model scores from a 10,000-response-per-problem dataset.

Main Findings

• Reward hacking has a precise Gaussian signature. When correct responses have reward mean μ_c and variance σ_c² and incorrect responses have μ_w and σ_w², the hacking regime is μ_c > μ_w together with σ_w > σ_c. The mean difference favors correct answers at small n, while the larger incorrect variance takes over at large n.

• Behavior splits into four phases. The initial trend from n = 1 to n = 2 is governed by Pr(R_c > R_w | x) (equivalently S₂ > S₁, which is equivalent to that probability exceeding 1/2), while the asymptotic limit is governed by which tail dominates. This yields phase iA (monotonic improvement), iB (delayed improvement such as a U-shape), iiA (reward hacking, such as an inverted U-shape), and iiB (monotonic degradation). The Gaussian condition for S₂ > S₁ is Φ((μ_c − μ_w)/√(σ_c² + σ_w²)) > 1/2.

• The critical phase is practically rare. The critical regime occurs only when the correct and incorrect reward distributions are exactly the same — in the Gaussian case, σ_c = σ_w and μ_c = μ_w.

• A turnover scale for Gaussian rewards. The authors define n*(x) = exp((μ_c − μ_w)² / (2(σ_w − σ_c)²)), described as a leading-order extreme-value crossover scale indicating where the incorrect maximum catches up to the correct maximum, not as the exact optimizer of S_n(x).

• Incomplete selection converges polynomially. In the Gumbel domain of attraction with α_n → α < ∞ and β_n → ∞, the approximation gives Ã_n(k_n; x) = 1 − Γ(1+α)e^{−β_n} + o(e^{−β_n}). For Gaussian rewards this becomes roughly 1 − Γ(1 + σ_c/σ_w) p^{−σ_c/σ_w} (1−p)^{2−σ_c/σ_w} n^{−γ_n}, with γ_n = 2(σ_c/σ_w − 1) + ((μ_c − μ_w)/σ_w)√(2/log n) − (σ_c/σ_w − 1)(log(4π log n)/log n). This is polynomial rather than the exponential 1 − e^{−np} of oracle selection.

• Fréchet and Weibull analogues exist. In the Fréchet domain with shape parameters ρ_c, ρ_w, b_m(x) = 0 and α_n(x) → ∞, the result is Ã_n = 1 − Γ(1 + ρ_w/ρ_c) α_n(x)^{−ρ_w} + o(α_n(x)^{−ρ_w}). In the Weibull domain with ξ_c < 0, ξ_w < 0 sharing a common finite upper endpoint r_max, b_c(k_n) = b_w(m_n) = r_max and α_n(x) → 0, the result is 1 − Γ(1 + ξ_c/ξ_w) α_n(x)^{−1/ξ} + o(α_n(x)^{−1/ξ}).

• Finite-budget effects reduce to a typical region. Lemma 1 shows that if selection accuracy does not vary too rapidly near k_n = ⌊np(x)⌋, the overall success probability S_n(x) is dominated by A_n(k_n; x): limsup |S_n(x) − A_n(k_n, x)| ≤ 2e^{−2(M−1)²}. Lemma 2 bounds the EVT approximation error by ϵ_c(n) + ϵ_w(n).

• Real reward scores show the predicted mean–variance pattern. Across settings, correct responses had higher mean scores while incorrect responses often had larger variance (except for Sky-Qwen-4B), which the authors present as evidence that reward hacking is common in practice.

• Early stopping helps exactly where theory predicts. On RAMO-Llama3.1-8B, where reward hacking occurred particularly often, the proposed method outperformed standard BoN while substantially reducing the number of generated samples. On datasets with monotonic improvement, the method did not increase accuracy — consistent with the authors' statement that early stopping is in principle suboptimal there.

Methodology in Plain English

The authors begin by decomposing BoN into two stages: a generation stage, where roughly n·p(x) of n samples are correct, and a selection stage, where the highest-scoring candidate is chosen. They argue that under mild stability conditions, the overall success probability is well approximated by selection accuracy in this "typical region," and prove a bound on that approximation.

Next, they replace the exact distributions of the maximum rewards with extreme value approximations. By the Fisher–Tippett–Gnedenko theorem, any continuous reward distribution's sample maximum converges to a Gumbel, Fréchet, or Weibull distribution after suitable rescaling, so the analysis covers far more than the Gaussian case they use for illustration. Comparing the rescaled norms of the two maxima (through ratios they call α_n and β_n) yields the three asymptotic regimes and the four behavioral phases.

For the early-stopping rule, they fit a two-component Gaussian mixture to the reward scores of the samples observed so far. The high-mean component stands in for correct responses and the low-mean component for incorrect ones, giving estimated values of μ_c, σ_c, μ_w, σ_w, and p. Stopping is considered only when the low-mean component has larger variance (σ_l > σ_h), matching the predicted hacking condition. The stopping point is n̂* ≈ exp((μ_h − μ_l)² / (2(σ_l − σ_h)²)), and because the extreme-value approximation is unreliable at very small budgets, sampling never stops before a minimum budget n_th. An alternative beyond-leading-order version solves μ_h + σ_h√(2 log(nπ_h)) = μ_l + σ_l√(2 log(nπ_l)) numerically, though the authors report very little accuracy change and do not include it.

Experiments use a 10,000-response-per-problem dataset covering 2,878 problem–generator pairs across MATH, MiniF2F, GSM8K, and CodeContests. For each n, they sample n responses from the 10,000, simulate the process 1,000 times, and report the average. Reward models are drawn from top-ranked entries in RewardBench 2: Skywork-Reward-V2-Llama-3.1-8B, Skywork-Reward-V2-Qwen3-8B, Skywork-Reward-V2-Qwen3-4B, Skywork-Reward-V2-Qwen3-1.7B, Llama-3.1-8B-Instruct-RM-RB2, and RAMO-Llama3.1-8B. Inference used vLLM on NVIDIA L40S (48GB) GPUs. Distributional fits were evaluated with the Anderson–Darling test, log-likelihood, AIC, and BIC. Synthetic experiments used Gaussian correct/incorrect distributions with p = [0.05, 0.1, 0.3, 0.5], and n_th was set to 32 because the Gaussian EVT approximation has an average deviation of about 3–4% at n = 32.

Why This Matters

Impact on research. The paper offers a unified explanation for both monotonic gains and reward-hacking degradation in BoN, connecting two literatures — inference-time scaling laws that assume oracle selection, and work on reward-model error and overoptimization. It reframes the key practical question from "how many samples should I draw?" to "which tail is thicker?", and it shows that convergence with an imperfect selector can be polynomial rather than exponential, which is a meaningfully weaker guarantee than the oracle baseline. It also provides a diagnostic criterion that requires no correctness labels, which matters because labels are unavailable at inference time.

Real-world applications.

• Serving LLMs with verifiable tasks such as math and code, where stopping early under the tail-tension condition cuts both generation and reward-model inference cost.
• Monitoring reward models in deployment: a large gap between the high-mean and low-mean mixture components, with the low-mean component having larger variance, flags a setting where more sampling will hurt.
• Selecting or auditing reward models before deployment, since the mean–variance pattern of correct versus incorrect scores predicts whether a model will hack.
• Designing RLHF or reward-model training objectives to control the upper tail of incorrect responses, rather than only pushing their mean down.

Industry relevance. The overhead of the proposed rule is only a lightweight mixture fit plus the computation of n̂*, and the rule is online, so it saves generation and reward-model inference cost whenever it triggers early. That makes it attractive for any production stack already using BoN or verifier-based selection, where inference cost is a first-order constraint. Since the analysis does not assume a Gaussian reward, it applies to any reward model whose score distribution has a well-defined extreme value limit.

Future Directions

1. Reduce the cost of distributional validation. The authors' own evaluation used samples from a 10,000-response-per-problem dataset; whether the mixture-fit proxies hold when only a few dozen samples are available per query is an open question.

2. Handle proxy misassignment. The high-mean/low-mean component assignment is explicitly described as a proxy for correct and incorrect classes. The paper discusses potential issues in Appendix B.1 and a conservative guard, but the general reliability of that mapping across reward models is unresolved.

3. Move beyond leading-order corrections. The authors numerically solve a higher-order equation for the crossover point but report very little accuracy change and omit it. Whether such corrections matter in other regimes or at other budgets is not established.

4. Test EVT approximations further. The paper notes that convergence of the scaled Gaussian maximum to the Gumbel distribution is slow, and that the third-moment (skewness) term is non-negligible — the reported average deviation of about 3–4% at n = 32. Whether alternative reference distributions predict experimental results better remains open.

Target Audience

Researchers and engineers working on inference-time scaling, reward modeling, and RLHF evaluation. The theory sections suit readers comfortable with extreme value theory and asymptotic analysis, while the early-stopping method and the experimental protocol are accessible to practitioners building Best-of-N or verifier-based selection pipelines who want a concrete, label-free diagnostic for when more sampling will backfire.

Authors’ abstract

Best-of-N sampling is a simple inference-time scaling strategy for large language models, yet its behavior under incomplete reward models remains poorly understood. We study Best-of-N as a competition between the extreme reward tails of correct and incorrect responses. This view shows that success depends not only on the probability of sampling a correct response, but also on whether correct responses dominate incorrect ones in the upper tail. Using extreme value theory, we characterize three asymptotic regimes: correct-tail-dominant, incorrect-tail-dominant, and critical explaining both monotonic gains and reward-hacking-induced degradation. We further derive finite-sample scaling laws for representative reward distributions, showing that, under Gaussian rewards, incorrect responses with sufficiently large variance can dominate selection even when their mean reward is lower. Unlike oracle selection, convergence with an incomplete selector can be polynomial rather than exponential. Finally, we propose a lightweight tail-tension criterion to estimate when additional sampling may become harmful. Experiments on synthetic data and real reward model scores are consistent with the theoretically predicted regimes, scaling laws, and diagnostic behavior, suggesting that tail competition provides a unified lens on Best-of-N sampling for verifiable problems.