🤖 AI

Beyond the Frontier: Stochastic Backtracking for Efficient Test-Time Scaling

本文提出了一种基于历史前缀持久池的随机回溯方法，通过子池选择与幂律回溯序贯蒙特卡洛技术加以增强，旨在克服仅依赖前沿搜索的局限性，并显著提升语言模型在测试时扩展中的准确率与令牌效率之比。

原作者： Dao Tran, Duc Anh Le, Ngoc Luu, Quan Pham, Tung Pham, Hung Bui

发布于 2026-05-26

📖 1 分钟阅读☕ 轻松阅读

原作者： Dao Tran, Duc Anh Le, Ngoc Luu, Quan Pham, Tung Pham, Hung Bui

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

以下是用通俗易懂的语言和富有创意的类比，对论文《超越前沿：用于高效测试时扩展的随机回溯》的解释。

宏观图景：“智能探险家”难题

想象一下，你正派遣一支探险队（人工智能）进入一个巨大的黑暗洞穴（复杂的数学问题），去寻找隐藏的宝藏（正确答案）。

在过去，这些探险家使用一种称为“仅前沿”（Frontier-Only）的搜索策略。其运作方式如下：

团队分成若干小组，各自走不同的路径。
在每一个岔路口，一名向导（称为过程奖励模型，PRM）会审视路径并给出评分。“这条路看起来很有希望！那条路看起来像是死胡同。”
团队立即切断低分路径，只向高分路径投入更多人力。

问题所在： 向导并非完美无缺。有时，向导会因紧张而给一条实际上通向宝藏的路径打出低分。由于“仅前沿”规则规定“切断任何非当前最佳的路径”，团队便永远抛弃了那条路径。他们再也没有机会去验证那条“糟糕”的路径是否实际上是一座金矿。他们被困在一条看似美好却通向虚无的路径上，浪费了时间和能量。

新解决方案：“持久池”

这篇论文提出了一种名为“基于持久池的随机回溯”（Stochastic Backtracking over a Persistent Pool）的新策略。

团队不再只关注探险家的当前前线，而是保留一个持久池——一张记录了他们曾经尝试过的所有路径的巨幅地图，包括那些被放弃的路径。

这就像一位背包里装满旧地图的徒步者。即使他们此刻正走在路径 A 上，他们也会记得路径 B 之前看起来还不错，而路径 C 之所以被放弃，是因为向导那天状态不佳。

论文提出了两种具体利用这个“旧地图背包”来更快、更省力地找到宝藏的方法：

1. 子池选择（“彩票票”方法）

想象团队背包里有 1,000 条路径。如果他们仅仅根据向导的评分挑选前 10 条，可能会反复挑选那些相同的“虚假”高分路径。

解决方案： 团队不再查看整个背包，而是随机抓取一把 50 条路径（一个“子池”）。他们从这一把中选出最好的一条。

为何有效： 这给了“黑马”路径（那些被向导不公平地打出低分的路径）被选中的机会。这就像一种彩票，你不仅仅购买“热门”号码的彩票，而是购买随机混合的号码，让冷门号码也有获胜的机会。这防止了团队被困在单一被过度炒作的死胡同里。

2. 幂次回溯 SMC（“加权时光旅行”）

这是一种更数学化的说法，意为：“让我们回到过去，但要聪明地做。”

团队保留一份所有过往路径的清单。当他们决定下一步探索哪条路径时，并非随机挑选，而是使用一个特殊公式，该公式：

放大高分（让真正优秀的路径更加突出）。
保留旧路径在池中存活，以便日后重访。
平衡尝试新路径与重访旧路径之间的关系。

不妨将其想象成一位“时光旅行侦探”。如果侦探陷入僵局，他们不会只是一味地向前行走。他们会翻阅旧案卷（持久池），重新审视昨天被忽略的线索，并意识到：“等等，这实际上看起来很有希望！”然后，他们折返并跟随那条旧线索。

为何重要：“令牌”节省

在人工智能领域，“令牌”（tokens）就像燃料。人工智能思考得越多，消耗的燃料就越多。

旧方法： 为了得到正确答案，人工智能必须消耗大量燃料（生成许多令牌），因为它不断走入死胡同且无法回头。
新方法： 由于人工智能可以回看其“旧路径地图”并再次尝试，它能更快地找到宝藏。

结果： 论文表明，采用这些新方法后，人工智能可以用显著更少的燃料（更少的令牌）解决困难的数学问题，同时获得相同甚至更高的准确率，而旧方法则无法做到。这就像驾驶一辆每加仑行驶 50 英里的汽车，而不是 20 英里，却不需要更大的引擎。

总结

这篇论文修复了人工智能探索问题时的一个缺陷。新方法不再盲目跟随“当前最佳”路径并抛弃其他一切，而是保留所有路径的历史记录。它利用巧妙的技巧（随机子采样和智能的时光旅行）来重访那些可能曾被不公平拒绝的旧路径。这使得人工智能能够更快、更经济、更准确地解决难题。

技术摘要：超越前沿：用于高效测试时扩展的随机回溯

问题陈述

测试时扩展（TTS）旨在通过分配额外的推理时计算资源来探索多种解决方案轨迹，从而提升大语言模型（LLM）的推理能力。尽管过程奖励模型（PRM）已成为通过评分中间前缀来引导此类搜索的标准机制，但当前的最先进方法存在一个关键局限：仅前沿搜索。

在仅前沿方法（如标准束搜索、SMC）中，搜索状态被限制在每一步新生成的子节点上。先前生成的前缀会根据有噪声的 PRM 评分被不可逆地剪枝。这导致了一种“过早承诺”的失效模式：

不可逆决策：由于 PRM 噪声（或 PRM 的训练展开与部署的基础 LLM 之间的不匹配）而被错误评分较低的前缀会被永久丢弃，即使它存在正确的延续。
多样性崩溃：被过度评分的错误前缀主导了搜索，导致系统在无益的路径上浪费计算资源，同时丧失了对潜在正确历史状态的访问。
低效性：无法重新访问历史状态迫使模型花费过多的 token 来从早期的剪枝错误中恢复。

方法论

本文提出了基于持久池的随机回溯，这是一个维护历史前缀线性内存池的框架，允许搜索重新访问并扩展先前生成的状态，而不是局限于当前前沿。作者通过两种互补的算法实现了该框架：

1. 子池选择（SPS）

SPS 解决了贪婪选择中的“阻塞器问题”，即被过度评分的错误前缀永久性地阻断了访问那些正确但评分较低的历史前缀。

机制：SPS 不是从整个持久池中选择前 $M$ 个候选者（这会偏向高评分的阻塞器），而是从历史池 $P_{t-1}$ 中构建一个大小为 $K_t$ 的随机子池 $D_t$ 。
选择：随后，它严格在这个随机子池内选择前 $M$ 个候选者。
自适应比率：子池大小由自适应比率 $\rho_t$ 决定，该比率基于当前池的平均 PRM 评分计算得出。如果池的置信度较低（平均评分低），则子池较小，以避免高评分的错误前缀；否则，子池较大。
效果：这种随机采样让被“阻塞”的历史前缀有机会被选中并扩展，从而绕过被过度评分的前沿候选者的主导地位。

2. 幂次回溯序贯蒙特卡洛（PB-SMC）

PB-SMC 将序贯蒙特卡洛（SMC）方法扩展到持久池，实现了对早期剪枝决策的随机恢复。

持久池目标：与将粒子限制在当前前沿的标准 SMC 不同，PB-SMC 维护一个包含新生成的子节点和保留的历史前缀子集的池。
幂次 PRM 评分：该方法对 PRM 评分应用幂次 $\beta_t$ （即 $r_{PRM}(z)^{\beta_t}$ ）以锐化奖励分布，突出高评分前缀，同时降低低评分前缀的权重。
混合校正权重：该算法将搜索视为**多重要性采样（MIS）**问题。它定义了一个混合提议分布 $q_{mix}$ $q_{mi x}$ ，结合了：
- $q_{new}$ ：从上一步生成的新子节点。
- $q_{hist}$ ：从先前步骤保留的历史前缀。
加权：它推导出特定的权重 $W_t(z)$ 以校正混合提议，确保估计量收敛到目标幂次代理分布。这使得系统能够随机重采样先前被剪枝的历史粒子。

内存与计算效率

线性内存：持久池仅存储文本状态和 PRM 评分，而非完整的键值（KV）缓存。仅当选择某个历史前缀进行扩展时，才会重新计算 KV 缓存。
开销：论文认为，为回溯状态重新计算 KV 缓存的计算开销，与在准确性和 token 效率方面获得的收益相比，微不足道。

主要贡献

识别仅前沿失效模式：论文指出，不可逆的仅前沿选择是 PRM 引导的 TTS 中的主要失效模式，其中有噪声的评分导致正确解决方案路径的永久丢失。
持久池框架：引入了一种线性内存替代方案，使历史前缀保持对未来扩展的资格，将搜索资格与即时前沿解耦。
两种新颖算法：
- 子池选择（SPS）：一种贪婪搜索增强方法，利用随机子池绕过被过度评分的阻塞器。
- 幂次回溯 SMC（PB-SMC）：一种 SMC 扩展，利用幂次 PRM 评分和混合校正权重来实现随机回溯。
理论保证：证明了 PB-SMC 依概率收敛到由幂次 PRM 定义的代理目标，确保相对于代理目标的渐近正确性。

实验结果

该方法在四个数学推理基准（MATH500、AMC23、AIME24、Minerva Math）上进行了评估，使用了三种 LLM（Qwen2.5-7B、Qwen2.5-3B、Phi-4-mini）以及 Qwen2.5-Math-PRM-7B。

Token 效率：SPS 和 PB-SMC 均仅使用每步 $N=8$ 个候选者就达到了具有竞争力或更优的准确率，而强大的基线方法（束搜索、SMC、DVTS）需要 $N=32$ 。
- SPS：在提高准确率的同时，平均减少了 49.4% 的 token 消耗。
- PB-SMC：在提高准确率的同时，平均减少了 36.7% 的 token 消耗。
准确率提升：
- 在 Qwen2.5-7B-Instruct 上，SPS 实现了 54.66% 的平均准确率，优于 DVTS（51.40%）和束搜索（52.12%）。
- 在 Phi-4-mini-Instruct 上，PB-SMC 实现了最高的总体准确率（48.69%）。
消融研究：
- 回溯：在 SMC 中添加回溯（Backtrack SMC）将平均准确率从 49.11% 提升至 52.27%。
- 随机性：用子池选择（SPS）替换全局贪婪选择，将平均准确率从 51.61% 提升至 54.66%。
运行时间：尽管存在重新计算 KV 缓存的潜在开销，但由于候选集大小减少（ $N=8$ 对比 $N=32$ ），这些方法比束搜索快约 2.5 倍，与最接近的竞争性基线相比，运行时间惩罚可忽略不计（约 10%）。

意义与主张

论文声称，持久池随机回溯提供了一种简单有效的机制，以改善测试时扩展中的准确率与 token 权衡。其核心意义在于将优化重点从仅仅评分前缀转移到保留对它们的访问。通过允许搜索重新访问历史状态，这些方法减轻了有噪声的 PRM 评分和过早承诺带来的风险。

作者将其工作定位为资源受限部署的实用解决方案，证明了有效的测试时扩展并不需要计算能力的巨大增加，而是需要通过具有历史感知能力的搜索来更智能地分配现有计算资源。结果表明，历史访问是最大化 LLM 推理效率的一个关键但常被忽视的因素。