Adaptive Generate-Rank-Verify: Inference-Time Search with Costly Verification¶

会议: NeurIPS 2026
arXiv: 2605.17609
OpenReview: https://openreview.net/forum?id=Tcux9XpSfo
代码: https://github.com/yhkalayci/efficient_query
领域: Reasoning
关键词: 推理期计算分配, 生成-排序-验证, 主动搜索, 成本敏感决策, 动态规划

一句话总结¶

针对大语言模型复杂推理中便宜奖励模型与昂贵形式化验证器并存的算力权衡问题，本文建立了主动搜索理论框架，并提出无需难度先验与奖励校准的壳层自适应策略 ADAP，在保证常数倍理论竞争比的同时将验证与采样综合成本降低数倍。

研究背景与动机¶

大语言模型在数学奥赛解题和竞赛级代码生成等前沿推理任务中，越来越依赖推理期搜索（Inference-Time Search）来弥补单次前向生成的不足。这类系统普遍采用“生成-评估-选择”的复合流水线：先由语言模型生成多个候选解，再通过计算开销较低的过程奖励模型或输出评分器进行粗筛，最后交由外部昂贵的确信验证器（如运行单元测试集、数学题目精确匹配或形式化定理证明器）进行最终正确性检验。然而，每一次候选生成、奖励打分与验证器执行都会消耗不可忽视的显存算力与时间延迟，如何在未知的题目难度下合理权衡采样规模与验证次数，成为了推理期算力分配的核心瓶颈。

现有工业界与学术界方案通常固定采样的候选数量与顶部验证数量，或者依赖离线数据训练一个题目难度预测器来分配测试期算力预算。这种做法在面对真实开放环境时面临严重矛盾：不同题目的难度分布极其分散，简单问题仅需 1 个生成样本与单次验证即可通过，而极其困难的题目往往需要成百上千次采样与多次试错；同时，在面对测试分布偏移（Distribution Shift）或未校准的奖励模型时，静态策略要么在简单题目上过度消耗验证资源，要么在难题上过早停止搜索导致彻底失败，而基于离线历史数据的难度分类器更会因校准失效而退化。

面对奖励分布未知且不可靠的现实约束，必须放弃对离线难度先验与全局分值校准的依赖，转向一种仅依靠当前题目即时反馈、在线自适应推进算力尺度的动态决策机制。核心 idea：将生成-排序-验证推理形式化为带代价的在线主动搜索问题，证明单调性假设下最优分布已知策略退化为固定阈值检验，并据此设计按几何开销壳层倍增候选池与验证深度的在线算法 ADAP，以理论常数竞争比摆脱离线难度预测。

方法详解¶

整体框架¶

在推理期主动搜索的形式化体系中，输入为一个待求解的 prompt $x$。生成器 $\pi(\cdot\mid x)$ 采样候选解 $Y$ 并调用便宜奖励模型给出打分 $R=\mathsf{RM}(x,Y)$，单次生成与评分成本为 $c_{\text{rew}}$；确信验证器 $\mathsf{Ver}(x,Y) \in \{0,1\}$ 提供最终黄金标签，单次调用成本为 $c_{\text{ver}}$。环境隐藏着由 prompt 诱导的奖励边际分布 $\mathcal{D}_x$ 以及基于分数的条件成功概率函数 $h_x^\star(r) = \Pr(V=1 \mid R=r)$。

算法不需要显式估计分布 $\mathcal{D}_x$ 或函数 $h_x^\star$，而是维护一个由历史生成但尚未检验的候选池 $\mathcal{P}$。算法按照指数递增的开销壳层（Shell）逐轮扩张搜索尺度：在壳层 $s$ 中，自适应计算当前允许的最大生成增量与验证上限，批量采样新候选加入候选池，随后将池中所有候选项按奖励分降序重排，依次对排名前列的样本调用高开销验证器，一旦遇到首个正确解立即终止。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入 Prompt x 与代价参数 (c_rew, c_ver)"] --> B["分布已知基准与阈值分析<br/>确定候选与验证二进尺度"]
    B --> C["壳层代价离散化与网格构建<br/>划分指数递增预算区间"]
    C --> D["池化样本维护与增量采样<br/>生成新解并按奖励分重排"]
    D --> E["贪心高分验证与提前终止<br/>调用昂贵验证器直至首个正例"]
    E -->|未命中正例| C
    E -->|验证器返回 1| F["输出验证通过的正确候选解"]

关键设计¶

1. 分布已知基准与阈值分析：确立最优序贯策略的结构极值

为了厘清在线自适应探索的理论下界，研究首先探究在完全掌握环境边际分布 $\mathcal{D}$ 与成功概率函数 $h^\star$ 的理想情况下如何决策。通过贝尔曼最优方程（Bellman Equation）建模继续采样与即时验证的边际收益差值，理论证明了最优全序贯策略具有严格的单阈值形式。定义延续价值 $J^\star(h^\star, \mathcal{D}) = c_{\text{ver}} / \tau^\star$，其中收支平衡阈值 $\tau^\star \in (0, 1)$ 是下列单调积分方程的唯一正根： $$c_{\text{ver}} \, \mathbb{E}_{R \sim \mathcal{D}}\left[\max\{h^\star(R) - \tau^\star, 0\}\right] = \tau^\star \, c_{\text{rew}}$$ 该设计揭示了关键洞察：当且仅当候选解的条件成功率 $h^\star(r) \ge \tau^\star$ 时进行验证才是划算的，而所有低于此阈值的解均应被立即永久丢弃；这也证明了在非递减单调奖励假设 $h^\star(r_1) \le h^\star(r_2)$ 下，最优分布已知策略等价于在最优奖励阈值 $t$ 上的即时二值过滤，其期望代价可精确写为 $J_t = (c_{\text{rew}} + c_{\text{ver}} q_t) / s_t$（其中 $q_t = \Pr(R \ge t)$ 为超阈值概率，$s_t = \Pr(R \ge t, V=1)$ 为超阈值且正确的联合概率）。

2. 壳层代价离散化与网格构建：基于二进尺度的无参化搜索空间

由于在线策略既不知道真实最优阈值 $t$，也无法知晓其对应的超阈值概率 $q_t \approx 2^{-a}$ 与成功质量 $s_t \approx 2^{-b}$，直接搜索连续阈值是不适定的。算法引入二进网格离散化，将搜索目标转化为匹配最佳离散指数对 $(a,b) \in \mathbb{Z}_{\ge 0}^2$（满足 $a \le b$）。为避免在未知难度网格中盲目震荡，算法以最小单步开销 $c_{\min} = \min\{c_{\text{rew}}, c_{\text{ver}}\}$ 为基准，构造指数递增的开销壳层： $$\mathcal{S}_s = \left\{(a, b) \in \mathbb{Z}_{\ge 0}^2 : a \le b,\; 2^s c_{\min} \le c_{\text{rew}} 2^b + c_{\text{ver}} 2^{b-a} < 2^{s+1} c_{\min}\right\}$$ 在每个壳层 $s$ 内部，策略提取该能量区间所能覆盖的最大生成步长 $b_s^\star = \max\{b : (a,b) \in \mathcal{S}_s\}$ 以及最大验证步长 $j_s^\star = \max\{b-a : (a,b) \in \mathcal{S}_s\}$，据此确定当前阶段应生成的增量样本数 $m_s = \lceil 2^{b_s^\star + 1} \rceil$ 与验证配额 $k_s = \lceil 6 \cdot 2^{j_s^\star} \rceil$。几何倍增的壳层设计确保了在到达与真实问题难度匹配的正确尺度前，前序所有壳层累计消耗的算力仅构成一个收敛的等比级数前缀，使得总开销牢牢锚定在当前难度的常数因子之内。

3. 池化样本维护与贪心高分验证：历史样本留存与单调排他校验

在多阶段自适应过程中，盲目抛弃此前壳层生成的候选会造成大量生成算力浪费，而无序验证又可能过早耗尽昂贵验证预算。ADAP 采取全局候选池机制，在每个壳层中向候选池 $\mathcal{P}$ 注入新生成的 $m_s$ 个候选对 $(y_i, R_i)$ 后，统一对池中全部尚未被验证的样本按奖励评分 $R$ 进行全局降序重排。随后，策略严格按照奖励从高到低的贪心顺序，消耗至多 $k_s$ 次验证器调用依次审查头部候选。

由于单调性假设保证了排名越高的候选解其真实正确率弱单调递增，将验证预算优先倾斜给未验证最高分候选能最大化单次验证的成功质量；即便当前壳层未能找到正确答案，已被验证失败的样本会被永久移出候选池，而未被验证的高分候选仍完好留存在池中，供后续更大规模的壳层继续探索。在数学证明中，通过联合 Chernoff 界与二项分布极值分析，当壳层尺度达到或超过匹配目标尺度的壳层 $s_\star + u$ 时，失败概率以双重指数 $\rho_u \le e^{-2^{u+1}} + e^{-2^u}$ 极速衰减，从而最终在全分布族上严格证明了 $\mathbb{E}[J(\mathcal{A}_{\text{Adap}})] \le 400 J^\star$ 的常数因子无界上界。

一个完整示例¶

以某道竞赛级编程题目为例，假设生成单解并打分成本 $c_{\text{rew}}=1$，完整执行测试用例成本 $c_{\text{ver}}=10$。 - 壳层 $s=0, 1$：开销预算较小，仅生成极少量样本（如 2~4 个），对最高分候选进行 1 次测试，验证未通过，失败用例移出池子，保留其余候选； - 壳层 $s=2, 3$：预算逐步升至数十单位，累计生成样本达 16~32 个，打分模型给出的最高分序列浮现出若干较优解，验证配额 $k_s$ 增加到 6 次，依次执行排名前 6 的代码，若全未通过全部隐藏测试，继续累积未测试候选； - 壳层 $s=4$：对应于该题真实通过率尺度的壳层触发，增量采样生成数十个新解入池并联合排序，此时池顶前 2 个候选中的某个算法解在边界条件上完全正确，首个验证返回 1，搜索立刻终止。全过程不仅没有在简单题上浪费过多用例测试，也避免了传统固定配置因采样不足直接宣布失败。

实验关键数据¶

主实验¶

实验在数学推理基准 HMMT（22 道可解难题，采用 Qwen2.5-Math-7B 与 Qwen2.5-Math-PRM-7B 打分，验证器为精确匹配）和代码竞赛基准 LiveCodeBench（83 道可解难题，采用 Qwen2.5-Coder-3B 与 CodeScaler-8B 打分，验证器为完整隐藏测试集子进程运行）上开展评估。代价设定基准为 $c_{\text{rew}}=1, c_{\text{ver}}=10$，每个配置评估 10 次随机置换。对比基线包括： - SampleAware：事后得知标签的理论开销下界（非实现在线策略）； - Uniform$_{C_{\text{Adap}}}$：在相同平均总预算下，能取得最高成功率的固定非自适应 $(N_{\text{rew}}, N_{\text{ver}})$ 策略； - $\text{DAP}_k$：按离线先验成功率将问题划分为 $k$ 个难度等级，并在每类内部动态规划搜索最优固定策略的难度自适应预言机。

任务 / 基准	策略	平均生成数 $\overline{N_{\text{rew}}}$	平均验证数 $\overline{N_{\text{ver}}}$	平均总代价	相比 ADAP 比例	成功率
数学 (HMMT)	SampleAware（下界）	103.7	29.5	398.9	$\times 0.28$	100.0%
	ADAP (本文)	219.6	120.2	1422.3	$\times 1.00$	100.0%
	Uniform$_{C_{\text{Adap}}}$	182.0	124.0	1422.0	$\times 1.00$	84.1%
	$\text{DAP}_1$（固定最优）	497.0	369.0	4187.0	$\times 2.94$	100.0%
	$\text{DAP}_2$	—	—	2164.8	$\times 1.52$	100.0%
	$\text{DAP}_5$	—	—	1477.3	$\times 1.04$	100.0%
	$\text{DAP}_{10}$	—	—	1169.4	$\times 0.82$	100.0%
代码 (LiveCodeBench)	SampleAware（下界）	92.4	8.7	179.9	$\times 0.24$	100.0%
	ADAP (本文)	140.4	60.5	745.3	$\times 1.00$	100.0%
	Uniform$_{C_{\text{Adap}}}$	414.0	33.0	744.0	$\times 1.00$	87.8%
	$\text{DAP}_1$（固定最优）	512.0	359.0	4102.0	$\times 5.50$	100.0%
	$\text{DAP}_2$	—	—	2162.1	$\times 2.90$	100.0%
	$\text{DAP}_5$	—	—	1194.3	$\times 1.60$	100.0%
	$\text{DAP}_{10}$	—	—	786.9	$\times 1.06$	100.0%

消融实验¶

论文在附录针对不同验证/采样代价比 $c_{\text{ver}}/c_{\text{rew}} \in \{1, 10, 20, 30\}$ 进行了系统鲁棒性消融测试（以下为 LiveCodeBench 代码竞赛任务的数据总结）：

验证成本比 $c_{\text{ver}}/c_{\text{rew}}$	策略	平均总代价	相比 ADAP 比例	成功率	说明
比值 = 1	ADAP (本文)	241.4	$\times 1.00$	100.0%	验证极其便宜，生成与验证开销对等
	Uniform$_{C_{\text{Adap}}}$	241.0	$\times 1.00$	79.0%	固定策略算力相同但成功率大幅下跌
	$\text{DAP}_1$	871.0	$\times 3.61$	100.0%	固定保底策略成本开销超 3.6 倍
	$\text{DAP}_{10}$	285.0	$\times 1.18$	100.0%	强难度预言机仍不如 ADAP 节省
比值 = 10	ADAP (本文)	747.6	$\times 1.00$	100.0%	主实验标准配置
	$\text{DAP}_1$	4102.0	$\times 5.49$	100.0%	固定策略开销劣势进一步扩大
比值 = 20	ADAP (本文)	1075.8	$\times 1.00$	100.0%	验证开销高昂
	Uniform$_{C_{\text{Adap}}}$	1074.0	$\times 1.00$	88.0%	预算相当仍有 12% 题目失败
	$\text{DAP}_1$	7692.0	$\times 7.15$	100.0%	开销膨胀至 ADAP 的 7.15 倍
比值 = 30	ADAP (本文)	1564.1	$\times 1.00$	100.0%	验证极度昂贵极端场景
	$\text{DAP}_1$	11282.0	$\times 7.21$	100.0%	固定保底策略成本极其昂贵
	$\text{DAP}_{10}$	1742.9	$\times 1.11$	100.0%	ADAP 持续稳健领先于 10 分类预言机

关键发现¶

在相同达到 100% 成功率的前提下，ADAP 展现出巨大的成本压缩能力：在 HMMT 上成本仅为最优全局静态策略 $\text{DAP}_1$ 的 $1/2.94$（节省近 66%），在 LiveCodeBench 上更是低至 $\text{DAP}_1$ 的 $1/5.50$（节省超 81%）。
算力匹配的固定策略（Uniform$_{C_{\text{Adap}}}$）在两项任务上分别出现了 15.9% 和 12.2% 的严重失败率，这确凿证实了推理期算力无法通过经验常数统一规划，个案自适应至关重要。
在代码任务中，即便是基于 10 个预设难度分段并采用动态规划联合优化的极强预言机 $\text{DAP}_{10}$，其代价（786.9~1742.9）依然高于完全不需要任何难度先验的 ADAP，说明代码任务的个例差异无法简单用宏观难度标签捕捉，在线排序验证机制优势显著。
代价消融表明，随着验证操作相对于生成的成本比从 1 升至 30，ADAP 对固定保底策略的开销缩减比率从 3.6 倍单调拉大到 7.2 倍以上，证明其在形式化证明等极高验证成本领域具备极高的部署价值。

亮点与洞察¶

严格的学习理论界定：摆脱了以往纯启发式的工程调度，首次将“生成-排序-验证”流水线严谨抽象为成本敏感的在线主动搜索（Active Search），从统计学习角度给出了最本质的数学刻画。
无需校准的单调性松弛：算法不强求奖励模型给出准确的概率标定，仅依赖“高分样本正确概率不低于低分样本”的弱单调假设，使算法能够无缝兼容各类未校准的开源 PRM 和代码判分模型。
中心星号（Centered Star Number）下界突破：论文证明了若无结构化归纳偏置，任何在线策略与预言机的最坏竞争比都会退化至 $\Omega(\min\{\mathfrak{s}_0, c_{\text{ver}}/c_{\text{rew}}\})$，在理论上完备证明了单调性假设是实现常数倍竞争比不可或缺的边界条件。

局限与展望¶

恒定开销简化假设：当前理论与实验均将单次采样与验证开销视为固定标量常数，然而在实际大模型长文本生成中，Token 长度的波动会导致采样与代码执行时间呈现动态变化。
非递减单调性依赖：在极端欺骗性问题（Adversarial/Jailbreak/Trick questions）上，奖励模型可能会遭遇严重幻觉，导致高分样本反而错误频发；一旦单调性被彻底破坏，贪心验证可能退化。
纯评分特征局限：算法目前仅通过标量奖励分数进行排序过滤，并未利用候选文本本身的语义表征（如语法树检查、语义去重聚类等手段），结合候选多样性调度的混合主动搜索是极佳的未来方向。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次建立结合便宜代理与昂贵确信验证器的生成式主动搜索学习理论，并提出常数竞争比的壳层自适应策略。
实验充分度: ⭐⭐⭐⭐ 覆盖数学与编程两大典型高验证开销场景，包含不同生成底座与代价比消融，但测试集规模受限于长序列验证成本略偏精炼。
写作质量: ⭐⭐⭐⭐⭐ 理论推导精湛自洽，从贝尔曼方程最优解到壳层二进网格分析层层递进，定理与引理结构清晰完备。
价值: ⭐⭐⭐⭐⭐ 为大模型测试期算力扩展（Test-Time Compute Scaling）提供坚实数学理论基石与实用轻量部署方案。