Tail Competition Explains Scaling in Best-of-N Sampling for Verifiable Problems
Best-of-N sampling improves LLM output quality by generating multiple candidates and selecting the highest reward, yet its scaling behavior under imperfect reward models is poorly understood. This paper recasts BoN as extreme-value competition between the upper tails of correct and incorrect reward distributions, yielding phase transitions that explain both monotonic gains and reward hacking. Using extreme value theory, the authors derive finite-sample scaling laws showing polynomial rather than exponential convergence, and propose a lightweight tail-tension criterion for label-free early stopping. The work matters because it replaces vague intuitions about reward hacking with precise, testable distributional conditions and a practical inference-time safeguard.
The paper provides a rigorous and elegant theory of BoN scaling under incomplete selectors. By framing selection as competition between the extreme upper tails of correct and incorrect reward distributions, the authors classify asymptotic behavior into three regimes—correct-tail-dominant, incorrect-tail-dominant, and critical—and derive four phases of $n$-dependence that unify monotonic improvement, delayed improvement, and reward hacking. The finite-$n$ scaling laws for Gumbel, Fréchet, and Weibull domains are novel, and the tail-tension early stopping criterion follows directly from the theory. However, the analysis rests on idealized assumptions—independent and identically distributed generations, continuous reward CDFs, and Gaussian mixture approximations—which may limit applicability to real LLM sampling.
The tail-competition framework is compelling because it yields crisp, testable predictions. For Gaussian rewards, the authors derive an exact reward-hacking condition, $\mu_c > \mu_w$ and $\sigma_w > \sigma_c$, with a closed-form turnover scale $n^\star$, and synthetic experiments show that observed BoN curves closely match the predicted iA, iiB, iiA, and iB phases. The EVT scaling law in Eq. (12) accurately describes finite-$n$ behavior, and the online early stopping rule demonstrably cuts computational cost in hacking regimes without requiring correctness labels.
Despite its elegance, the theory relies on assumptions that may not hold in practice. The extreme value approximation for Gaussian maxima converges notoriously slowly, yet the early stopping threshold is set at $n_{\mathrm{th}} = 32$, where the authors note an average deviation of about 3--4\%. The unsupervised Gaussian mixture fit assigns the high-mean component to correct answers, but the authors concede this is 'only a proxy,' and misassignment can trigger harmful early stopping in rare U-shaped regimes. Moreover, the real-world experiments use a static 10,000-response dataset, sidestepping online generation variance and response correlations. Finally, the claim that critical cases require exactly equal distributions brushes over near-critical settings where finite-$n$ behavior may diverge from the asymptotic prediction.
The synthetic evidence strongly supports the theory: Figure 4 confirms that Gaussian BoN trajectories match the predicted four phases, and the empirical optimum aligns with the theoretical $n^\star$. Real-score experiments across multiple reward models and benchmarks corroborate the key mean--variance tension, showing that incorrect responses often have larger variance and can dominate the upper tail. However, the real-data analysis remains largely correlational; the authors do not independently validate EVT domain membership or the exact polynomial exponent on live samples. Comparisons to related work are fair—oracle pass@$n$, KL-regularized selection, and Best-of-Tails are discussed—but the paper could more directly benchmark its early stopping against concurrent Bayesian optimal stopping methods rather than relegating that comparison to an appendix.
The experiments use a publicly available dataset (Monkey Business, 10,000 responses per problem) and several open reward models, which aids reproduction. Key hyperparameters—$n_{\mathrm{th}} = 32$, 1,000 simulation repeats, and vLLM inference on NVIDIA L40S GPUs—are stated. However, no code repository, random seeds, or mixture-fit hyperparameters are provided. Exact reproduction of the real-score analysis requires hosting the full pre-generated response bank. The early stopping rule is simple enough to implement from Eq. (17), but independent verification of EVT approximation errors at small $n$ would benefit from access to raw score arrays. Full reproducibility would be greatly improved by releasing inference scripts and fitted Gaussian parameters.
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.
Pick a starting point or write your own. Challenges run in the background, so you can keep reading while the AI investigates.
No challenges yet. Disagree with the review? Ask the AI to revisit a specific claim.