Tail competition shapes best-of-N sampling outcomes in AI models
Tail Competition Explains Scaling in Best-of-N Sampling for Verifiable Problems
Computation and LanguageArtificial IntelligenceMachine Learning
Summary
Best-of-N sampling is a way AI models pick the best answer by trying multiple times and choosing the highest-scored result. The authors found that success depends not only on how often correct answers appear, but also on how their top scores compare to incorrect answers' top scores. They identified three patterns explaining why adding more samples helps or sometimes hurts performance. Their findings help predict when more sampling is beneficial and when it could cause worse results. This understanding can improve how AI systems select answers when the reward for correctness is not perfect.
What this means in practice
- •For machine learning engineers: Optimize sampling strategies during AI inference to improve answer reliability when reward feedback is incomplete or noisy.
- •For automated verification teams: Estimate when additional sampling might reduce verification accuracy by using tail-tension criteria to detect harmful sampling regimes.
Authors
Taro Yano, Yoichi Ishibashi, Masafumi Oyamada
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.