🤖 machine learning

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

本文介绍了 ADAP，一种自适应推理时间算法，它通过动态采样和排序候选项，在廉价奖励评分与昂贵验证之间实现高效平衡，在单调性假设下，于数学推理和代码生成等任务中实现了接近最优的成本性能。

原作者： Shaddin Dughmi, Mahdi Haghifam, Yusuf Hakan Kalayci

发布于 2026-05-19

📖 1 分钟阅读☕ 轻松阅读

原作者： Shaddin Dughmi, Mahdi Haghifam, Yusuf Hakan Kalayci

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象你是一名侦探，正试图破解一个谜团，但你手头有两种截然不同的工具，而且使用它们都需要花钱。

工具：

“直觉”（奖励模型）： 这是一种廉价、快速但有时不可靠的直觉。它可以审视嫌疑人并说：“这个人看起来有罪！”或者“这个人看起来无辜！”询问它的成本几乎为零，但它会犯错。
“测谎仪”（验证器）： 这是一种昂贵、缓慢但 100% 准确的测试。它能确切地告诉你嫌疑人是否有罪。但每次使用它，都需要花费巨资（就像一笔巨大的实验室检测账单）。

问题：
你有一份嫌疑人名单（由人工智能生成的候选答案）。你需要找出那个“有罪”的人（正确答案）。

如果你对每个人都使用测谎仪，你会破产。
如果你只相信直觉，你可能会抓错人。
旧的方法是采用固定规则：“我会让直觉评估 100 个人，然后对排名前 5 的人使用测谎仪。”
- 缺陷： 有些谜团很简单（有罪者显而易见），所以你浪费了钱去检查 100 个人。而有些谜团很难（有罪者深藏不露），只检查 5 个人是不够的，导致你失败了。你无法用同一条固定规则应对所有案件。

解决方案："ADAP"（自适应侦探）
这篇论文的作者创造了一种名为ADAP的智能策略。ADAP 不像死守固定规则，它更像是一位能边行动边学习的侦探。

以下是 ADAP 的工作原理，使用一个简单的类比：

“外壳”策略

想象你正在 haystack（干草堆）里找一根针，但你不知道干草堆有多大。

从小开始： ADAP 首先只让廉价的“直觉”评估少数几个嫌疑人。
排序： 它将它们从“最可能有罪”到“最不可能”进行排列。
首次检查： 它对排名第一的嫌疑人使用昂贵的“测谎仪”。
- 成功了吗？ 太好了！停止并庆祝。
- 失败了吗？ 好吧，排名第一的嫌疑人是无辜的。
“外壳”扩展： 由于第一次检查失败了，ADAP 意识到：“这个谜团比我想象的要难。”它不会放弃，而是加倍努力。
- 它让“直觉”评估更多的新嫌疑人。
- 它重新排列整个堆栈（旧的和新的）。
- 它对新的前几名嫌疑人使用测谎仪。
重复： 如果仍然失败，它就再次加倍努力。它不断以“外壳”（层）的形式扩大搜索范围，规模越来越大，直到找到答案。

为什么这很出色？

对于简单案例： 如果答案显而易见，ADAP 能迅速找到它，只需极少的检查。它节省了大量资金。
对于困难案例： 如果答案深藏不露，ADAP 会持续寻找直到发现它。它不会像固定规则那样过早放弃。
结果： 平均而言，ADAP 的花费比旧的“固定规则”方法少得多，同时仍能 100% 地找到正确答案。

“单调性”规则（秘密武器）

为了让 ADAP 发挥作用，有一个重要的假设：直觉必须大体上是正确的。
论文假设，如果直觉说某个嫌疑人“非常可能有罪”，那么他们实际上比直觉说“稍微可能”的人更可能有罪。它不需要完美，只需要大致顺序正确。如果直觉完全是随机的，ADAP 就无法工作。但在现实世界（数学问题和编程）中，直觉通常能相当好地对事物进行排序。

论文证明了什么

作者们不仅仅是猜测这会奏效；他们通过数学计算进行了证明。

理想场景： 他们首先设想了一位确切知道每个嫌疑人有罪概率的侦探。他们计算了解开谜团所需的绝对最低成本。
现实世界： 他们证明了 ADAP 在不知道未来的情况下，其成本可以控制在“完美”成本的常数倍以内。用通俗的话说：ADAP 几乎和拥有水晶球的侦探一样好，但它不需要水晶球。
结构的必要性： 他们还证明，如果直觉完全是混乱的（毫无规律），没有任何策略能高效运作。你需要那种“分数越高 = 越可能正确”的模式来节省资金。

现实世界测试

团队在两项困难的任务上测试了这种方法：

数学问题： 解决棘手的数学题。
编程： 编写能通过隐藏测试的计算机程序。

结果：

ADAP 100% 地找到了正确答案。
旧固定方法（检查固定数量的人）要么未能找到答案，要么为了获得相同的结果，花费了3 到 5 倍的资金。
即使与一种试图预先猜测问题难度的“智能”方法相比，ADAP 的表现也与之相当或更好，而且不需要任何先验知识。

总结

这篇论文介绍了一种使用人工智能的智能自适应方法。它不再盲目地生成固定数量的答案并检查固定数量的答案，而是根据具体问题的难度动态调整其投入。通过保持灵活性，它节省了巨大的计算能力（和资金），确保你不会在简单任务上过度支出，也不会在困难任务上投入不足。

技术摘要：自适应生成 - 排序 - 验证

问题表述

本文解决了大语言模型（LLM）中对推理时计算分配的成本敏感问题。现代推理流程通常采用“生成 - 排序 - 验证”范式：LLM 生成多个候选解决方案，一个廉价但含噪的奖励模型对其进行排序，随后一个昂贵的验证器（例如代码中的隐藏测试执行或数学中的精确答案匹配）对排名靠前的候选项进行验证。

核心挑战在于，计算资源（生成数量与验证数量）的最优分配是依赖于提示词（prompt）的。固定策略（例如生成 $N_{rew}$ 个样本并验证前 $N_{ver}$ 个）效率低下：它们对简单提示词过度消耗资源，而对困难提示词则投入不足。作者将此形式化为主动搜索（Active Search），这是一个序列决策问题，其中策略必须自适应地：

生成候选项并观察其奖励分数（成本 $c_{rew}$ ）。
验证选定的候选项以获取真实标签（成本 $c_{ver}$ ）。
仅在找到经验证正确的响应时停止。

目标是最小化期望总成本 $J = c_{rew}N_{rew} + c_{ver}N_{ver}$ ，同时确保 100% 的成功率（如果生成分布中存在正确答案，则必须找到它）。

方法论

1. 分布感知基准

作者首先假设策略对环境拥有完美知识，从而建立理论下界：

$D_x$ ：提示词 $x$ 的奖励分数分布。
$h^*_x(r)$ ：条件成功函数，表示得分为 $r$ 的候选项通过验证的概率。

定理 3.2 刻画了这种理想化设置下的最优策略。它证明最优策略是一个阈值规则：如果候选项的条件成功概率 $h^*_x(r)$ 超过特定的盈亏平衡阈值 $\tau^*$ ，则立即验证该候选项，否则将其丢弃。阈值 $\tau^*$ 是方程 $c_{ver} \mathbb{E}[\max\{h^*(R) - \tau^*, 0\}] = \tau^* c_{rew}$ 的唯一解。

2. ADAP 算法

在实践中， $D_x$ 和 $h^*_x$ 是未知的。作者提出了ADAP（自适应生成 - 排序 - 验证），这是一种分壳在线算法，它在无需预先知道分数分布或成功函数的情况下运行，仅依赖单调性假设（更高的奖励分数通过验证的可能性不低于较低分数）。

ADAP 机制：

分壳搜索：该算法在样本数量（ $m$ ）和验证数量（ $k$ ）的二进制尺度“壳”（shells）上进行搜索。每个壳 $s$ 对应成本范围 $[2^s c_{min}, 2^{s+1} c_{min})$ 。
渐进扩展：从较小的壳开始，ADAP 生成一批新候选项，将它们加入池中，并根据奖励分数对整个池进行排序。
验证：验证池中排名前 $k$ 的候选项。如果找到正标签，则停止。如果没有找到，则进入具有更大 $m$ 和 $k$ 的下一个壳。
基于池的效率：与丢弃未验证候选项的流式策略不同，ADAP 维护一个池。如果在早期壳中生成的高奖励候选项尚未被查询，它们在后续壳中仍可用于验证。

3. 理论保证

上界：在单调性假设下，定理 4.2 证明 ADAP 的期望成本在分布感知最优解 $J^*$ 的常数倍内（具体为 $\le 400$ ）。该保证对所有可行提示词和未知分布一致成立。
下界与结构必要性：作者证明结构假设是必要的。利用中心星数（centered star number） $s_0$ （一种学习理论复杂度度量），定理 6.2 表明，如果不假设分数与标签之间的关系（即如果 $s_0 = \infty$ ），则没有任何可靠的在线策略能在分布感知预言机面前实现常数倍的竞争比。最坏情况下的差距可扩展为 $\Omega(\min\{s_0, c_{ver}/c_{rew}\})$ 。

主要贡献

形式化：将生成 - 排序 - 验证流程形式化为成本敏感的主动搜索问题，将其与标准主动学习区分开来，后者需要在线生成候选项而非查询固定池。
最优基准：将分布感知最优策略刻画为基于盈亏平衡成功概率的简单阈值规则。
自适应算法（ADAP）：提出了一种实用的在线算法，可自适应地扩展生成和验证工作。在单调性假设下，它提供了相对于最优预言机的可证明常数倍保证。
学习理论极限：确立了结构假设（如单调性）不仅仅是技术上的便利，而是高效主动搜索的根本要求，并通过中心星数进行了形式化。
实证验证：在数学推理（HMMT）和竞争性编程（LiveCodeBench）任务上验证了该方法。

实验结果

作者将 ADAP 与以下方法进行了评估：

SampleAware：一个预言机下界，它回顾性地为每次特定试验选择最便宜的 $(N_{rew}, N_{ver})$ 。
DAPk：一种难度自适应基线，根据历史通过率将提示词划分为 $k$ 个难度类别，并为每个类别分配固定策略。
Uniform：一种固定策略，其平均成本与 ADAP 相匹配。

发现：

成本效率：在可行提示词的子集上，ADAP 实现了 100% 的成功率，其平均成本在数学任务上比最佳固定策略低2.9 倍，在编程任务上低5.5 倍。
与 DAPk 的比较：ADAP 匹配或优于 DAPk（即使 $k=10$ ），且无需历史难度标签或离线调整。在编程任务上，DAPk 从未胜过 ADAP；而在数学任务上，仅当 $k$ 足够大以近似每个问题的预言机时，DAPk 才接近 ADAP 的性能。
鲁棒性：随着验证成本（ $c_{ver}$ ）相对于生成成本（ $c_{rew}$ ）的增加，ADAP 相对于固定策略的优势也随之增加。

意义与主张

本文主张，对于推理时搜索，在线的、依赖于提示词的自适应优于静态或基于历史调整的策略。通过将问题视为主动搜索并利用奖励信号的单调性，ADAP 可以动态分配计算资源以匹配特定提示词的难度。

作者强调，他们的工作提供了：

可证明的保证：在不知道底层分布的情况下，实现最优成本的常数倍近似。
实际效率：显著降低高 stakes 推理任务的计算成本（延迟、GPU 小时数、API 支出）。
理论必要性：证明了关于奖励 - 验证器关系的结构假设是实现高效搜索的不可避免的要求，从而弥合了主动搜索与主动学习理论之间的差距。

本文结论指出，虽然扩展到可变成本和并行生成是未来的方向，但当前框架成功地解决了生成多样化候选项与验证最有希望的候选项之间的基本张力。