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

📄 arXiv: 2610.19362v1 📥 PDF

作者: Taro Yano, Yoichi Ishibashi, Masafumi Oyamada

分类: cs.CL, cs.AI, cs.LG

发布日期: 2026-10-14

备注: Accepted at NeurIPS 2026

💡 一句话要点

提出尾部竞争机制以解释可验证问题中的Best-of-N采样扩展

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: Best-of-N采样 奖励模型 极值理论 尾部竞争 自然语言处理 模型优化 决策系统

📋 核心要点

  1. 现有的Best-of-N采样方法在不完整奖励模型下的行为尚不明确，导致其在实际应用中的效果不稳定。
  2. 本文提出将Best-of-N采样视为正确与错误响应之间的尾部竞争，利用极值理论分析其成功条件。
  3. 实验结果表明，理论预测的渐近状态和扩展法则与实际数据一致，验证了尾部竞争的有效性。

📝 摘要（中文）

Best-of-N采样是一种用于大型语言模型的简单推理时间扩展策略，但在不完整奖励模型下的行为仍然不够明确。本文将Best-of-N视为正确与错误响应的极端奖励尾部之间的竞争，表明成功不仅依赖于采样正确响应的概率，还依赖于正确响应在上尾部的主导地位。通过极值理论，我们描述了三种渐近状态：正确尾部主导、错误尾部主导和临界状态，解释了单调增益和奖励黑客引起的降级。我们进一步推导了代表性奖励分布的有限样本扩展法则，显示在高斯奖励下，即使错误响应的均值奖励较低，具有足够大方差的错误响应也能主导选择。与oracle选择不同，不完整选择器的收敛可能是多项式而非指数级。最后，我们提出了一种轻量级的尾部张力标准，以估计额外采样何时可能变得有害。对合成数据和真实奖励模型分数的实验结果与理论预测一致，表明尾部竞争为可验证问题的Best-of-N采样提供了统一的视角。

🔬 方法详解

问题定义：本文旨在解决Best-of-N采样在不完整奖励模型下的行为不明确的问题。现有方法未能充分考虑正确与错误响应之间的竞争关系，导致效果不稳定。

核心思路：论文提出将Best-of-N采样视为正确与错误响应的极端奖励尾部之间的竞争，强调正确响应在上尾部的主导地位对成功的重要性。

技术框架：研究采用极值理论来描述三种渐近状态：正确尾部主导、错误尾部主导和临界状态，并推导出有限样本扩展法则。整体流程包括理论分析、模型构建和实验验证。

关键创新：最重要的创新在于引入尾部竞争的视角，揭示了在高斯奖励下，错误响应的方差如何影响选择，挑战了传统的oracle选择假设。

关键设计：论文设计了轻量级的尾部张力标准，以评估额外采样的潜在危害，并通过实验验证了该标准的有效性。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果显示，在高斯奖励分布下，具有较大方差的错误响应能够主导选择，即使其均值奖励较低。与传统的oracle选择相比，使用不完整选择器的收敛速度表现为多项式而非指数级，验证了理论预测的有效性。

🎯 应用场景

该研究的潜在应用领域包括自然语言处理、推荐系统和其他需要基于奖励模型进行决策的智能系统。通过优化Best-of-N采样策略，可以提高模型在实际应用中的表现和稳定性，具有重要的实际价值和未来影响。

📄 摘要（原文）

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.