ROC-n-Reroll: How Verifier Imperfection Affects Test-Time Scaling¶

会议: ICLR 2026
OpenReview: https://openreview.net/forum?id=3Gy5mmyuxn
代码: https://github.com/socialfoundations/roc-n-reroll
领域: LLM推理
关键词: 测试时扩展, 验证器, ROC曲线, 拒绝采样, Best-of-N

一句话总结¶

本文用经典的 ROC 曲线，给出"不完美验证器下 Best-of-N 与拒绝采样到底能扩展到多好"的精确理论刻画，并证明两个反直觉结论：固定算力下拒绝采样优于 Best-of-N，且无法从低算力表现外推高算力表现。

研究背景与动机¶

领域现状：测试时扩展（test-time scaling）是继预训练之后提升 LLM 性能的主流手段，自 OpenAI o1 之后爆火。其中"重采样"路线最直接：对同一个查询生成多个候选答案，再用一个验证器（verifier，给答案打分的机制）挑出最好的。两种最常见的重采样方法是 Best-of-N（BoN，采样 \(N\) 个取分数最高者）和拒绝采样（Rejection Sampling, RS，一直重采直到验证器分数超过阈值才停）。

现有痛点：以往的理论分析几乎都假设验证器是完美的（oracle verifier），此时 BoN 的准确率就等于 pass@N。但现实里完美验证器只在代码（单元测试）、数学（标准数值答案）等少数领域存在，而且即便这些领域也会漏判——不安全的代码能通过静态测试、错误的推理也可能凑出正确数字。更普遍地，人们越来越多地用"另一个 LLM 当验证器"，而这种验证器的准确率远谈不上完美。

核心矛盾：验证器的不完美程度，到底如何决定这两种方法的扩展曲线？这个关系一直没有理论。验证器有两类错误此消彼长：假阴性（拒绝正确答案）和假阳性（接受错误答案），它们之间的 trade-off 恰好就是分类问题里 ROC 曲线刻画的东西——但此前没人把测试时扩展和 ROC 曲线联系起来。

本文目标：对固定查询，精确刻画 RS 和 BoN 的"准确率 vs 算力"曲线如何依赖于验证器的不完美程度；并回答"能否用低算力下的观测外推高算力下的性能"。

核心 idea：把每个验证器在某个查询上的全部错误权衡，编码为它的 ROC 曲线 \(T(F)\)（真阳性率作为假阳性率的函数），然后证明 RS / BoN 的实例级准确率只通过"生成器初始准确率 \(\pi\) + 验证器 ROC 曲线"这两样东西依赖于具体实现——一切实现细节都被这条曲线吸收掉。

方法详解¶

整体框架¶

本文是一篇纯理论分析工作，不提新算法，而是给"验证器不完美 → 测试时扩展能到多好"建立精确数学刻画。整条论证链是：先用 ROC 曲线把验证器抽象出来（形式化设定），再分别推导 RS 和 BoN 的"准确率-算力"闭式表达式，最后从这两个表达式里读出三个结论——RS 在固定算力下占优、两者在无限算力下收敛到同一极限、性能无法从低算力外推。

形式化设定固定一个查询 \(q\) 和生成器 \(g_{\text{base}}\)，其单次采样正确率为 \(\pi := \text{ACC}(g_{\text{base}}) = P[y(X)=1]\)，其中 \(y(X)\in\{0,1\}\) 是未知的正确性标签。验证器是打分函数 \(f:X\mapsto[0,1]\)，对它阈值化得到分类器 \(h_\tau(X)=\mathbb{I}[f(X)\ge\tau]\)。每个分类器有真阳性率 \(T = P[h(X)=1\mid y(X)=1]\) 和假阳性率 \(F = P[h(X)=1\mid y(X)=0]\)，把所有阈值下"给定 \(F\) 时能达到的最大 \(T\)"连起来，就是这个验证器在该查询上的 ROC 曲线 \(T(F)\)。本文的所有结论都以这条曲线为唯一输入。

关键设计¶

1. ROC 曲线：把"验证器有多好"压缩成一条曲线

这是全文的根基。论文证明（Proposition 1、4）：对固定查询，RS 和 BoN 的准确率只依赖于生成器初始准确率 \(\pi\) 和验证器的 ROC 曲线 \(T(F)\)，对其余一切实现细节（验证器具体是哪个模型、怎么打分）都是不可知的（agnostic）。换句话说，两个验证器只要 ROC 曲线相同，它们带来的扩展行为就完全一样。这一步的价值在于把"验证器不完美"这个模糊概念，落到一个有几十年研究、几何性质清楚的对象上：ROC 曲线左下角（\(F\approx0\)，高阈值、几乎只接受高分答案，对应高算力）和右上角（\(F\approx1\)，低阈值、几乎全接受，对应低算力）分别编码了高/低算力两端的行为，而曲线是否凹（concave）则决定了扩展是否单调、会不会出现"算力越多反而越差"的过优化（overoptimization）。

2. 拒绝采样：精度和算力都由 ROC 的"局部斜率"决定

RS 一直重采直到验证器接受，因此它的准确率其实就是分类器 \(h_F\) 的精度（precision / 阳性预测值）\(P[y(X)=1\mid h_F(X)=1]\)。论文给出闭式：

\[\bar{A}_f(F) = \text{ACC}(g_{h_F}) = \frac{T(F)\cdot\pi}{T(F)\cdot\pi + F\cdot(1-\pi)}\]

而平均算力（期望采样次数）服从几何分布，为 \(C(F)=\dfrac{1}{T(F)\cdot\pi + F\cdot(1-\pi)}\)。把 \(F\) 换元成算力 \(C\)，就得到"准确率 vs 算力"曲线 \(A(C)\)。关键结论（Proposition 1）是：\(A(C)\) 的斜率正比于 ROC 曲线的斜率 \(T'(F)\)，因而ROC 曲线凹 ⟹ RS 扩展单调上升。更细地：低算力端（\(F\approx1\)，右上角）的扩展速度由 \(T'(1)\) 决定——\(T'(1)=0\) 时初始增速达到上界 \(\pi\)，\(T'(1)=1\) 时根本不涨；高算力极限（\(F\to0\)，原点附近）则由原点斜率 \(T'(0)\) 锁死（Proposition 2）：

\[\lim_{C\to\infty}A(C) = \frac{T'(0)\cdot\pi}{T'(0)\cdot\pi + (1-\pi)}\]

这意味着 RS 最终能爬到多高，完全取决于验证器在"原点附近还能不能可靠地把极少数正确答案挑出来"。

3. Best-of-N：性能是 ROC 曲线的"全局积分"，且固定算力下输给 RS

与 RS 由局部几何决定不同，BoN 取 \(N\) 个里分数最高的，其准确率依赖 ROC 曲线的全局形状。在分数分布的一个正则性假设下，论文把 BoN 准确率写成沿 ROC 曲线的积分（Proposition 4）：

\[\text{ACC}(g_N) = 1 - (1-\pi)^N\int_0^1 \psi(F)^{N-1}\,dF,\quad \psi(F)=(1-\pi)(1-F)+\pi(1-T(F))\]

完美验证器时 \(T(F)=1\)，公式退化为众所周知的 pass@N \(=1-(1-\pi)^N\)；该式还揭示：当 \(y\) 是二值标签时，只有 ROC 曲线非凹才可能出现过优化。两个进一步结论是本文最有用的实践指引：(i) 固定算力下 RS 占优（Proposition 5）——对凹 ROC 曲线，把 RS 阈值调到平均采样数等于 \(N\) 时，RS 准确率 \(\ge\) BoN；直觉上 BoN 从 Best-1 到 Best-2 的最大增速只有 \(\pi(1-\pi)\)，明显小于 RS 的 \(\pi\)。(ii) 但 无限算力下两者收敛（Theorem 1）：BoN 的高算力极限和 RS 一样，都等于 \(\frac{T'(0)\pi}{T'(0)\pi+(1-\pi)}\)，因为大 \(N\) 时积分被 \(\psi(F)\) 最大处（即小 \(F\)、原点附近）主导。这暗示这是不完美验证器下重采样性能的一个更根本的天花板，甚至可能延伸到 RL（RL 常被训练去模仿重采样分布）。

4. 外推不可能性：低算力表现锁不住高算力表现

这是最反直觉、也最有警示意义的结论。RS 的低/高算力分别由 ROC 的右上角斜率 \(T'(1)\) 和原点斜率 \(T'(0)\) 决定，而这两个角的几何互不约束——所以不知道 ROC 曲线全貌时，无法从低算力观测推断高算力性能（Proposition 3）：存在两个验证器 \(f_0,f_1\)，在算力预算 \(B\) 内观测到的准确率完全一致，却分别在极限处趋于 0 和 1。即便额外假设 ROC 凹，也只能保证不变差，仍区分不出"很快停滞"还是"最终接近完美"。BoN 也有完全对应的负结果（Proposition 6）：尽管 BoN 扩展更平滑，任何低算力下的早期趋势都同时兼容"极限为 0"和"极限为 1"。这直接否定了实践中常见的"画几个点拟合幂律再外推"的做法。

一个完整示例¶

以论文 Figure 1（GSM8K 第 58 题，生成器 Qwen3-1.7B）为例：用 Qwen3 的 32B / 14B / 4B 当验证器，三条 ROC 曲线在右上角几乎重合、在原点附近斜率不同。结果完全符合理论——低算力端三个验证器的 RS 和 BoN 曲线几乎贴在一起（BoN 在 \(N\le3\) 前基本一致），但算力上去后明显分叉，原点斜率大的验证器爬得更高。同一张图里还能直接看到 RS 用更少的平均算力就追平了 BoN 的准确率。这一个查询就同时演示了"低算力无法外推高算力"（设计 4）和"固定算力 RS 占优"（设计 3）。

实验关键数据¶

实验用 Qwen3 与 LLaMA 系列开源指令模型同时充当生成器和验证器，在 GSM8K 和 MATH500 上验证。生成用 5-shot、温度 \(t=1\)；验证让模型先做思维链再给 0–10 分，重复 5 次取平均归一化到 \([0,1]\) 作为 \(f(X)\)。对小批查询各采样 1000 个答案，用来同时模拟 RS/BoN 并估计 ROC 曲线，再用 Eq.(5)/Eq.(10) 预测准确率。

主实验：理论预测精度 + 聚合表现¶

实验	设置	关键结果
实例级预测	GSM8K Q58（Qwen3-1.7B 生成）	理论曲线与实测点几乎重合；低算力三验证器一致、高算力分叉
实例级预测	GSM8K Q2（LLaMA-3.2-3B 生成，单 CoT 验证器）	RS 一致优于 BoN；即便 ROC 略非凹，绝对预测误差 < 1 个百分点
聚合（难度启发式 RS）	GSM8K / MATH500	控制算力后 RS > BoN，但大算力时差距消失；GSM8K 上 4B 与 32B 验证器低算力同、高算力分叉
聚合（Capped RS）	GSM8K / MATH500	CRS 全程追平 Bo25，但所需平均采样数显著更少

关键发现¶

固定算力下 RS 稳定优于 BoN：单查询和聚合两个层面都复现，即使验证器 ROC 曲线存在一定非凹性也成立；但这个优势在高算力极限处消失，与 Theorem 1 一致。
低算力同、高算力分叉：GSM8K 上 Qwen3-4B 与 32B 验证器在低算力时表现相同，高算力时出现明显差距——直接印证"不能靠外推预测高算力性能"。
Capped RS（CRS）是好用的折中：固定阈值采样、最多采 25 次否则返回当前最高分，既保住了 RS 的算力优势（追平 Bo25 而采样更少），又规避了"难题阈值难定、可能无限采样"的实现痛点，比按难度调阈值的启发式更简单。
附录还在 GPQA（STEM 推理）和 HumanEval+（代码生成）上做了补充实验，结论一致。

亮点与洞察¶

把 ML 老工具 ROC 曲线接到 LLM 测试时扩展上，是非常漂亮的"old tool, new problem"：验证器的两类错误（假阴/假阳）本就是 ROC 的两个轴，套上去后所有实现细节都被一条曲线吸收，理论一下子变干净。
"局部 vs 全局"的对偶：RS 性能由 ROC 的局部斜率（右上角 \(T'(1)\) 管低算力、原点 \(T'(0)\) 管高算力）决定，BoN 由全局积分决定，但两者高算力极限相同。这个统一让人对"为什么不同方法最后殊途同归"有了机制级解释。
外推不可能性是可迁移的警示：任何想"低算力画几个点拟合幂律再外推预算曲线"的人都该读这一条——本文用构造性反例证明这在原理上不可靠，除非你已知 ROC 曲线原点附近的形状。
"过优化只发生在非凹 ROC" 给出了过优化现象一个干净的充要条件式判据，对设计验证器有直接指导意义。

局限与展望¶

理论结论严格成立于固定单一查询；聚合到整个数据集时是经验观察，没有同等强度的理论保证（不同查询的 \(\pi\) 和 ROC 分布如何影响结论，作者列为 future work）。
只分析了 RS 和 BoN 两种最简单的重采样方法，未覆盖多数投票、束搜索、过程奖励等更复杂的测试时策略。
ROC 曲线在实践中需要从有限样本估计，估计误差如何传播到预测尚未深入分析；本文实例验证用了每题 1000 个样本，成本不低。
把结论延伸到 RL（"RL 模仿重采样分布故极限可能相同"）目前只是直觉 + 附录的初步探讨，不是严格定理。
可延伸方向：作者明确提出"为不同测试时预算训练定制化验证器"——因为低/高算力依赖 ROC 不同区域，针对性优化原点或右上角或许能突破当前天花板。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次用 ROC 曲线完全刻画不完美验证器下 RS/BoN 的测试时扩展，视角干净且有力
实验充分度: ⭐⭐⭐⭐ 实例级预测误差 <1pp、聚合在 GSM8K/MATH500/GPQA/HumanEval+ 上复现，但都是开源模型自验证、规模有限
写作质量: ⭐⭐⭐⭐⭐ 命题层层递进、直觉与定理交替，理论论文里少见的好读
价值: ⭐⭐⭐⭐⭐ "不能外推""固定算力 RS 占优""Capped RS"三条对实践都有直接指导意义