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

2610.19362 ↗ · 2026-10-14 · cs.CL, cs.AI, cs.LG

Taro Yano, Yoichi Ishibashi, Masafumi Oyamada

Accepted at NeurIPS 2026

The finding

Headline claim

Best-of-N sampling success is governed by a competition between the extreme reward tails of correct and incorrect responses: with an imperfect reward model, gains can converge polynomially rather than exponentially and can even decline at large N (reward hacking) whenever the incorrect-response tail is heavier, a behavior the paper characterizes theoretically and matches empirically with a label-free early-stopping rule.

The test

Theory plus experiments: extreme-value-theory derivations of three asymptotic regimes and finite-N scaling laws for representative reward distributions (Gaussian worked throughout), validated on synthetic data with Gaussian rewards and on real reward-model scores for verifiable problems; the tail-tension early-stopping criterion was tested against baselines with full results in appendices. The arXiv text provided gives no specific model names, task suites, sample sizes, or accuracy numbers.

Effect size & scope

Qualitative and structural rather than a headline effect: the Gaussian case shows selection is driven by variance differences at the tail (sigma_w > sigma_c can force success probability toward 0 despite mu_c > mu_w), and incomplete selection yields polynomial rather than exponential scaling in N. Scope conditions are strong: iid samples, continuous reward distributions, verifiable tasks with correctness labels for theory, and asymptotic analysis whose finite-N relevance is only sketchily demonstrated in the provided text.

Limitations

The authors concede the Gaussian case is an illustrative example and the critical phase occurs only when correct and incorrect distributions are identical, i.e., rarely; extreme value approximations are asymptotic in n; real reward-score distributions are only checked for consistency with the framework. Unstated limits: iid sampling ignores correlated errors from a single model, real reward scores may be non-Gaussian or heavy-tailed in unexamined ways, and the mixture-fit early-stopping rule depends on unsupervised two-component fitting that may fail when distributions overlap; no numbers on real-task performance are visible in the provided text.

Counterpoint

This is a clean theory paper whose empirical section is confirmation-style: synthetic Gaussian data will match Gaussian-derived theory almost by construction, and real reward-model experiments appear as consistency checks rather than head-to-head wins over existing early-stopping or selection baselines. iid sampling and continuous-distribution assumptions may not hold for actual LLM reranking pipelines, and practitioners already know reward hacking exists; the open question is whether the derived stopping rule beats simple heuristics in deployment.

Economy implication

Little or nothing yet for AI economics over the next 12 to 24 months. The practical relevance is indirect: if Best-of-N inference spend can be cut or capped by a principled stopping rule, it bears on inference-cost discipline, but this paper demonstrates mechanism and diagnostics, not measured cost savings at production scale.

Who this matters for

Technical Capability: Researchers and engineers doing inference-time scaling get an analytical account of why BoN gains can plateau or reverse, plus a label-free rule for when to stop sampling before budget hurts.

Bears on (advisory · papers never write evidence)

[1.4] Inference-time compute yields gains that don't saturate quickly on hard reasoning.

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.