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

会议: NeurIPS 2026
arXiv: 2610.19362
OpenReview: https://openreview.net/forum?id=g0h3FQFGch
论文: https://arxiv.org/abs/2610.19362
领域: 其他
关键词: Best-of-N采样, 极值理论, 推理时缩放, 奖励作弊, 尾部竞争

一句话总结¶

将可验证问题中的 Best-of-N 采样重构为正确与错误候选答案奖励分布的右端尾部竞争，借助极值理论刻画了四阶段标度相变，揭示了方差主导导致的奖励作弊（Reward Hacking），并提出了无监督尾部张力早停策略。

研究背景与动机¶

在大语言模型推理时计算扩展（Inference-Time Scaling）技术中，Best-of-N（BoN）采样凭借其简单与通用性成为了主流范式：给定输入问题，模型独立采样生成 $N$ 个候选解答，并交由判别奖励模型（Reward Model, RM）进行打分以选出最高分输出。已有关于测试时采样的理论分析（例如 Large Language Monkeys 等工作）多建立在 Oracle 选择器的理想假设下，得出只要单次采样成功率 $p>0$，候选中至少包含一个正确解的概率将随采样预算 $N$ 呈指数级收敛 $1 - e^{-np}$。然而在真实场景中，作为代理选择器的奖励模型通常并不完备，不仅使得经验性能收敛速度远落后于理论指数上界，更经常引发严重的「奖励作弊」（Reward Hacking）现象——即随着候选采样规模 $N$ 持续增大，模型在真实任务指标上的准确率非但不上升，反而呈现倒 U 形甚至单调下降趋势。

现有针对推理时奖励作弊的研究多局限于经验性的过度优化度量、KL 散度正则化或基于验证集经验调优的启发式缓解方案，缺乏对奖励模型误差与采样规模如何交互导致性能退化的底层数学解释。究竟是什么机制决定了不完备选择器下的标度率（Scaling Laws）？为什么在小样本下表现良好的奖励模型会在大 $N$ 采样时突然崩塌？这一核心矛盾在理论分析与实践应用间形成了认知鸿沟。

本文的切入角度是跳出对单一边缘奖励分布的宏观审视，将 BoN 选拔机制本质还原为微观层面的两两博弈：最终输出是否正确，仅取决于「正确解集合中的最大奖励值」是否压制了「错误解集合中的最大奖励值」。核心 idea：将 Best-of-N 采样建模为正确与错误解答在极端奖励尾部的极大值竞争（Tail Competition），利用极值理论（EVT）解析三类渐近稳态相与四种标度模式，证明当错误答案奖励方差大于正确答案时高尾优势必将在大 $N$ 时颠覆均值优势引发奖励作弊，并据此构建免标注的高斯混合尾部张力早停准则。

方法详解¶

整体框架¶

本文针对形式化推理、数学和代码等具备明确判定集合 $\mathcal{Y}^\star$ 的可验证问题（Verifiable Problems），将 BoN 分解为「生成」与「选择」两阶段。设模型生成单次正确率 $\text{Pass@1} = p$，当独立采样 $N$ 个候选时，正确响应数 $k$ 与错误响应数 $m = N-k$ 服从二项分布 $\text{Bin}(N, p)$。选择器成功的充分必要条件是正确集合的最大奖励值 $M_c(k) = \max_{i \in \text{correct}} r(x, y_i)$ 严格大于错误集合的最大奖励值 $M_w(m) = \max_{j \in \text{wrong}} r(x, y_j)$。在典型区域（Typical Region）$k_n = \lfloor Np \rfloor, m_n = N - k_n$ 下，BoN 准确率等价于两个极大值随机变量的胜负概率。

通过引入 Fisher-Tippett-Gnedenko 极值定理，作者对规范化极大值分布构建极值逼近，将离散的候选采样规模转化为连续尾部参数竞争，完整推导了有限样本下的代数标度律，并设计了仅依赖奖励分数的免标签在线早停机制。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入问题 x 与生成器采样<br/>生成 N 个独立候选响应"] --> B["典型区域极大值分解<br/>划分为 np 个正确解与 n(1-p) 个错误解"]
    B --> C["极端值尾部竞争建模<br/>极值定理逼近 Mc 与 Mw 尾部动态"]
    C --> D["四阶段标度相分类<br/>均值驱动初始方向 vs 方差驱动渐近终态"]
    D --> E["双高斯混合在线早停准则<br/>无监督拟合参数并在转折点 n* 触发截断"]
    E --> F["输出选拔响应 y_bon<br/>兼顾高精度并显著削减推理计算量"]

关键设计¶

1. 极值理论极大值近似与渐近相分类：以尾部分布主导替代传统单点度量

传统评价仅关注奖励模型的整体 ROC 或校准误差，无法反映极大值操作对极端右尾的敏感情形。根据极值理论（EVT），连续分布的样本极大值经位置尺度规范化 $(M(m)-b(m))/a(m)$ 后弱收敛至 Gumbel、Fréchet 或 Weibull 三大极值吸引子之一。本文通过尺度比率 $\alpha_n(x) := a_c(k_n; x) / a_w(m_n; x)$ 与位移优势比率 $\beta_n(x) := (b_c(k_n; x) - b_w(m_n; x)) / a_w(m_n; x)$，严谨定义了决定最终极限胜率 $A_n(k_n; x)$ 的三类渐近稳态： - 正确侧极值主导相（$\beta_n \to +\infty$，准确率趋于 1）； - 错误侧极值主导相（$\beta_n \to -\infty$，准确率趋于 0）； - 临界相（$\beta_n \to \beta \in \mathbb{R}$，准确率收敛于介于 0 与 1 之间的非平凡常数）。

在此基础上，结合从 $N=1$ 到 $N=2$ 的初始趋势 $\Pr(R_c > R_w \mid x) > 1/2$，论文划分了四种 $N$ 标度行为：单调上升（相 iA）、U 形延迟回升（相 iB）、倒 U 形奖励作弊（相 iiA）以及单调下降（相 iiB）。这一分类首次将奖励作弊明确界定为「两两对比的均值优势在小样本占优，但错误极端尾部在大样本逐步接管」的渐近相变。

2. 有限样本标度律推导：揭示不完备选择器下的多项式收敛阶

在理想 Oracle 条件下，未命中错误率随 $N$ 呈指数衰减 $e^{-np}$。本文在 EVT 逼近误差上界证明的基础上，推导了三大吸引子域在正确侧主导相下的有限样本代数标度律。以轻尾的典型代表高斯奖励分布 $\mathcal{N}(\mu_c, \sigma_c^2)$ 与 $\mathcal{N}(\mu_w, \sigma_w^2)$ 为例，正确解极大值优势项的增长率由 $b(m) \approx \mu + \sigma \sqrt{2 \log m}$ 决定。当 $\sigma_c > \sigma_w$ 时系统处于正向主导相，但其错误概率满足： $$1 - \tilde{A}_n(k_n; x) \approx \Gamma\left(1 + \frac{\sigma_c}{\sigma_w}\right) p^{-\frac{\sigma_c}{\sigma_w}} (1-p)^{2 - \frac{\sigma_c}{\sigma_w}} n^{-\gamma_n}$$ 其中指数主导项为 $\gamma_n \approx 2(\frac{\sigma_c}{\sigma_w} - 1)$（辅以 $\mathcal{O}((\log n)^{-1/2})$ 阶次修正项）。该结论严格证明了：即便奖励模型是有效的（能单调提升），不完备选择器也使得收敛速度从理想指数形式严重退化为关于 $N$ 的多项式级缓慢收敛。

3. 奖励作弊临界转折点解析：方差放大效应与翻转规模预估

当奖励模型满足 $\mu_c > \mu_w$（平均而言能给出正确的正向激励）但 $\sigma_w > \sigma_c$（对错误答案的打分波动显著更发散）时，系统处于相 iiA。在采样规模较小时，$N$ 较小，对数增长项 $\sqrt{2\log N}$ 幅度有限，均值差 $\mu_c - \mu_w > 0$ 起支配作用，表现为初始准确率上升；但随着 $N \to \infty$，$\sigma_w \sqrt{2\log(N(1-p))}$ 的增长斜率必然超越 $\sigma_c \sqrt{2\log(Np)}$，错误解的极端最大值终将压倒正确解的最大值，导致准确率彻底归零。通过令一阶极值期望相交 $\mu_c + \sigma_c \sqrt{2\log N} \approx \mu_w + \sigma_w \sqrt{2\log N}$，论文导出了表征奖励作弊转折尺度的解析解析解： $$n^\star(x) := \exp\left( \frac{(\mu_c - \mu_w)^2}{2(\sigma_w - \sigma_c)^2} \right)$$ 该公式表明，均值差距越小、方差差值越大，发生奖励作弊崩塌的临界样本数 $n^\star$ 越小。

4. 无监督尾部张力在线早停准则：免真实标签的计算量抑制与风险截断

在实际线上部署中，无法提前获得候选响应的正确性真值标签，因而无法直接计算 $\mu_c, \mu_w, \sigma_c, \sigma_w$。作者提出了轻量级在线高斯混合模型（GMM）拟合策略：在观测到前 $t$ 个候选奖励后，无监督拟合两组分混合高斯分布 $r \sim \pi_h \mathcal{N}(\mu_h, \sigma_h^2) + \pi_l \mathcal{N}(\mu_l, \sigma_l^2)$，利用充分训练奖励模型的保序性将高均值组分代理为正确类（$\mu_c \leftarrow \mu_h$）、低均值组分代理为错误类（$\mu_w \leftarrow \mu_l$）。若检测到低均值组分方差更大（$\sigma_l > \sigma_h$，存在尾部张力风险），则在线计算预估反转阈值 $\hat{n}^\star$。当采样量超过经验保底阈值 $n_{\text{th}} = 32$ 且满足 $t \geq \hat{n}^\star$ 时立即早停： $$\tau = \min \left\{ t \leq N : t \geq n_{\text{th}},\; \sigma_l > \sigma_h,\; \hat{n}^\star \leq t \right\}$$ 该机制不仅完全无需人工或真实判题标签，更在有效遏制作弊崩塌的同时大幅节约了昂贵的模型生成与奖励计算预算。

损失函数 / 训练策略¶

该工作属于推理时算法与理论分析研究，核心算法模块无需重新训练参数。其在线早停中的分布参数估计采用标准的期望最大化（EM）算法拟合二元一维高斯混合模型，计算开销在毫秒级，相比大型语言模型解码推理和奖励打分的前向传播计算量几乎可以忽略不计。

实验关键数据¶

主实验¶

实验基于开源的 Monkey Business 数据集构建的大规模 10,000 候选响应池（涵盖 MATH、GSM8K、MiniF2F、CodeContests 共 2,878 个问题-生成器对），使用 vLLM 部署当前 RewardBench 2 顶尖开源奖励模型（Skywork-Reward-V2 系列、Llama-3.1-8B-Instruct-RM-RB2、RAMO-Llama3.1-8B 等）评估 BoN 采样在不同预算下的真实轨迹。

下表展示在 RAMO-Llama3.1-8B 等模型上，尾部张力早停方法与标准 BoN（No-stop）在不同采样规模 $N$ 下的准确率及计算预算节省情况（截取具有显著代表性的样本尺度）：

奖励模型 / 评估子集	策略配置	$N=32$	$N=128$	$N=512$	$N=2048$	$N=8192$	计算开销节省
RAMO-Llama3.1-8B (全量)	标准 BoN (无早停)	0.316	0.327	0.334	0.337	0.336	基准 (0%)
RAMO-Llama3.1-8B (全量)	本文尾部张力早停	0.316	0.327	0.335	0.342	0.345	节省 20%~32%
Sky-Qwen-1.7B (作弊子集)	标准 BoN (无早停)	0.1576	0.1609	0.1576	0.1330	0.0366	基准 (0%)
Sky-Qwen-1.7B (作弊子集)	本文尾部张力早停	0.1576	0.1606	0.1593	0.1462	0.0792	节省 27.6%
RB2-Llama3.1-8B (作弊子集)	标准 BoN (无早停)	0.1902	0.1859	0.1736	0.1466	0.0568	基准 (0%)
RB2-Llama3.1-8B (作弊子集)	本文尾部张力早停	0.1902	0.1872	0.1814	0.1675	0.1161	节省 32.0%

消融实验与等算力基线对比¶

为了验证尾部张力早停准则在相同有效计算预算（Effective Compute Budget）下的优越性，作者与近期代表性在线早停基准 UCB 变体（Kalayci et al., 2025）进行了严格的同算力插值对比（以 MATH-Pythia-12B 配合 RB2 测试为例）：

有效计算预算 (Cost)	本文方法 (Ours)	UCB-t090	UCB-t095	UCB-t099	UCB-c1e-3	UCB-c2e-4
Cost = 32	0.316	0.317	0.317	0.316	0.318	0.318
Cost = 128	0.327	0.324	0.325	0.326	0.317	0.317
Cost = 512	0.335	0.322	0.323	0.324	0.316	0.315
Cost = 1024	0.339	0.321	0.321	0.322	N/A	0.315
Cost = 4096	0.345	N/A	N/A	N/A	N/A	N/A

真实奖励模型分布统计分析表明：绝大多数真实 RM（如 Skywork 系列、RAMO、allenai-RB2）在 GSM8K 与 MATH 上均表现出显著的 $\mu_c > \mu_w$ 且 $\sigma_w^2 > \sigma_c^2$。例如在 GSM8K 上，RAMO 的 $\sigma_w^2 = 1.4$ 远高于 $\sigma_c^2 = 0.49$；allenai-RB2 的 $\sigma_w^2 = 1.3$ 显著高于 $\sigma_c^2 = 0.37$。这强有力地佐证了现实中大规模采样时奖励作弊普遍存在的根本诱因。

关键发现¶

真实奖励模型的极端非对称方差：实验对多种前沿 RM 统计发现，几乎所有模型在错误解答上的得分方差均显著高于正确解答（甚至达 2~3 倍），直接证实了相 iiA（奖励作弊）并非极端人造特例，而是当前判别模型极其普遍的内在统计属性。
作弊阶段的性能逆转挽救：在发生严重作弊的子集上（如 $N=8192$ 时标准 BoN 准确率从 16% 断崖式跌落至 3.6%），尾部张力早停能够在翻转点附近及时截断，不仅挽救了超过 4.3%~6.0% 的绝对精度，同时整体减少了约 27%~32% 的无谓采样算力消耗。
渐近收敛速率的降级验证：合成数据与实测曲线均证实，不完备判别器下的 BoN 无法实现理论上的指数式收敛，其实际性能曲线在双对数坐标系下展现出与理论公式严格一致的多项式级慢速爬升。

亮点与洞察¶

极值竞争理论视角的范式统一：摆脱了以往从整体误差或散度界看待奖励作弊的模糊直觉，首次将 BoN 明确解构为右侧极大值统计量的尾部对抗，用简洁的极值参数相图统一解释了单调改善、U 形反转与倒 U 形崩塌。
均值与方差的尺度竞争机制：澄清了推理扩展中「小尺度看均值，大尺度看方差」的物理本质。这一洞见直接指导了奖励模型的微调方向——降低对负样本的不稳定高估（压制 $\sigma_w$）其重要性甚至高于单纯拉大平均分差（$\mu_c - \mu_w$）。
完全免标注的低成本在线落地：将复杂的连续极值理论通过高斯混合参数在线估计，转化为一个仅需几十行代码、计算开销为毫秒级的即插即用停止条件，工程落地极度优雅。

局限与展望¶

可验证问题假设约束：本文的理论建模核心依赖于解空间存在确切判定边界（正确与错误集合两分法），对于创意写作、开放式对话或主观文本摘要等无法严格定性真值的场景，尾部两两竞争假设的推广面临挑战。
高斯混合代理拟合的潜在失配：在极高难度题目下，若正确解本身单次生成概率极低（$\text{Pass@1} \approx 0$），GMM 的高均值组分可能会错误捕捉到异常偏高的幻觉噪声，导致组分误归属。
未来方向：探索结合多步推理链（Process Reward Models, PRM）的阶段级尾部极值聚合，并将尾部张力指标直接作为奖励模型训练阶段的正则约束。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次从极值理论极大值尾部竞争的角度完整剖析 Best-of-N 的标度相变与作弊机制。
实验充分度: ⭐⭐⭐⭐⭐ 涵盖合成高斯验证、前沿顶尖奖励模型统计审计、多项式标度拟合以及大规模在线早停对比。
写作质量: ⭐⭐⭐⭐⭐ 数学证明严谨完备，动机与物理直觉阐述清晰透彻，理论与实践落地闭环优良。
价值: ⭐⭐⭐⭐⭐ 为当前大模型推理时扩展理论和低成本工程落地提供了极具启发性的统一基石。