Progressive Point Matching (8分钟阅读)

# 渐进式点匹配 来源：https://www.prestonfu.com/notes/ppm/ Preston Fu (https://www.prestonfu.com/) 2026年9月 当今的大语言模型（LLM）能够处理需要连续数小时甚至数天运行的超长周期任务。人类需要数天或数周完成的任务，可能需要包含数百万乃至数十亿token的语言模型轨迹。 这些能力得益于大规模强化学习（RL）。标准方法是采样完整轨迹，并为整个轨迹分配稀疏的结果奖励——根据轨迹是否成功给出0或1的奖励。经验表明，这种简单的方法在大规模训练中能带来稳定的性能提升，因为最优策略拥有一个*无偏*目标：它的训练目标是最大化任务成功的概率。 但随着我们持续扩展到更长运行时间的任务，稀疏结果奖励变得越来越低效。例如，一个在数十个子任务上取得进展但在最后一个任务失败的轨迹，会获得与毫无进展的轨迹相同的奖励。理论上，我们证明了稀疏结果奖励产生的策略梯度，其信噪比会随任务周期增长而*指数级*下降。 多种方法，如学习价值函数、过程奖励或自蒸馏，都引入了渐近*偏差*。这里的偏差是指，在替代目标下的最优策略，在结果奖励下可能并非最优。例如，过程奖励（奖励轨迹中每个片段的逻辑正确性）可能会激励模型说出与最终任务成功无关但逻辑正确的表述。 我们提出了**渐进式点匹配（PPM）**，一个简单且渐近无偏的部分信用分配框架。 **图1：** 为长周期推理分配部分信用的方法。稀疏结果奖励的收敛速度比分配部分信用的方法慢*指数级*。有偏的部分信用方法（如过程奖励）可能收敛到次优策略。 ## 框架 我们的核心见解是，解决推理问题可以被视为在*马尔可夫状态空间*中寻找路径。 推理轨迹很长，先前的推理可以被压缩为中间结果。例如，考虑定理证明任务，它可能还需要证明中间引理。一旦轨迹陈述了一个引理并完成了证明，后续的推理只需基于该引理进行，而无需引用其证明过程。我们将这些中间结果称为**推理点**。在实践中，我们从参考轨迹（如人工撰写的证明[1]）中获取推理点。根据压缩的本质，从参考轨迹中提取推理点成本低廉，但反向操作则并非如此，可能需要证明某些引理。这也意味着我们不需要完整的LLM推理痕迹。 因此，推理轨迹允许紧凑的状态表示：当前轨迹前缀所访问的*推理点集合*。我们可以将推理轨迹视为在目标导向的**推理马尔可夫决策过程（MDP）**状态空间中的路径，其目标状态必须包含目标点（例如最终答案）。每个动作代表向该集合添加新的推理点。此设置的一个推论是，该集合永远不会随时间缩小。也就是说，根据设计*进展永远不会被撤销*，这里的进展指该集合的大小。例如，如果轨迹随后转向错误，其推理状态保持不变，仍然可以回溯到该引理。 然而，这里存在一个问题。考虑一条成功的轨迹，它遵循与参考轨迹完全不同的策略达到了目标。根据我们的定义，它获得的进展非常低。另一方面，一条失败的轨迹，虽未达到目标但紧密遵循参考轨迹，可能获得较高的进展。因此，简单地优化进展是*有偏*的。 我们可以通过引入**快捷连接**机制来解决这个问题：如果一个点所依赖的所有点都已被到达，则该点也被视为已到达。特别地，任何成功的轨迹都将获得全额信用[2]。如图1所示，快捷连接也使得学习不同于参考轨迹的策略成为可能！这对于提高pass@k指标至关重要。在我们的论文中，我们证明了快捷连接产生的学习策略在结果奖励下是最优的！ **图2：** 在稀疏结果奖励的强化学习中，未达到目标gg的轨迹得不到任何部分信用。在渐进式点匹配中，快捷连接机制提供了部分进展奖励，（在特定情况下）对应于沿参考轨迹的*最远点*。 ## PPM可扩展至长周期推理任务 为了隔离任务周期的影响，我们考虑合成任务，这允许我们控制（i）子任务数量，（ii）推理MDP的“形状”。 直观地说，像PPM这样的信用分配方法在每个子问题独立，或等价地，推理点之间没有依赖关系时表现最佳。这使我们能在每个子任务上获得独立的策略梯度。在这种情况下，事实证明，随着我们增加子问题数量n，相比标准GRPO的实证训练加速比随n*指数级*增长！ **图3：** 在每个子任务独立的合成任务中，随着任务周期的增长，PPM相比稀疏结果奖励，指数级地提高了训练效率。 论文包含了许多额外实验来探索维度（ii）。例如，我们考虑了更困难的MDP，其中每个子问题只有在得到前一个子问题的正确答案后才能解决。在这种情况下，点的到达高度相关，我们从理论上证明了这会降低策略梯度的信噪比。我们还考虑了介于这两个极端之间的合成推理任务。如果您感兴趣，请查阅我们的论文！ ## PPM使得在近乎不可能的数学推理任务上训练成为可能 随着我们将算法扩展到更长周期的任务，直接在数百万token长的轨迹上训练变得不可行。相反，实际的强化学习系统在小token预算的“模拟”版本任务上进行训练，目标是提升在大得多的测试时token预算下的性能。 最近的工作，如Claude Code的`/effort ultracode`模式，旨在通过设计测试工具和多代理工作流来解决这个问题，以提升在极高测试时预算下的性能。但这些方法并不足够，且在前沿模型中，导致随着预算增加性能提升[不一致](https://cognition.com/blog/frontier-code-1.1)。因此，当今的强化学习算法仍然受限于其随测试时预算扩展的能力。 在这种情况下，任务在训练token预算内很少能被解决。这种场景的一个替代情况是包含极难数学问题的数据集，其中基础策略看到的结果奖励几乎总是零。在这种环境中，几乎不可能通过稀疏结果奖励的GRPO进行训练——24小时后，我们仍未能采样到足够的轨迹来填充单个训练批次。 当在该数据集上训练时，PPM显著优于次优方法。但或许更令人惊讶的是，我们发现长度4K的训练效果*与8K相当甚至更好*！ **图4：** 在极具挑战性的数学推理数据集上训练时，PPM在较大的测试时token预算下，无论以成功率还是pass@8衡量，都显著优于次优方法（POPE）。由于数据过滤，GRPO未能取得任何进展。 为什么会这样？我们发现这是由于输出长度的崩溃——在8K长度上训练的策略可能会贪婪地猜测答案并提前结束推理过程，而在4K长度上训练的策略由于在训练token预算内永远无法成功，因此优化目标是部分进展。因此，在这类任务中，存在一个较低序列长度训练反而*有益*的区间。更多讨论请查阅我们的论文！ ## 下一步是什么？ 我们围绕两个关键需求设计了我们的方法： 1. 该方法是无偏的，即PPM下的最优策略与结果奖励下的最优策略一致。 2. 奖励按朝向目标的进展比例分配。这里的进展是指从当前（推理）状态出发的期望终端回报。 如我们在论文中所示，PPM满足需求（1）。而在如图2或3的最小化设置中，当我们能轻松地将推理点定义为到达参考轨迹上的节点或解决范围清晰的中间子问题时，我们的方法满足需求（2）。 然而，通用的推理任务并不会自动带有清晰的子问题划分。在实践中，我们使用现成的LLM来生成推理点，这个生成过程需要大量迭代，才能在预测进展和蒙特卡洛回报之间产生强相关性。正如我们在论文中所示，按照我们提出的推理点评估标准，我们的方法优于朴素的评分标准基线。 这开启了许多激动人心的方向： - PPM可以很好地扩展到具有多个给定参考轨迹的设置，因为我们只需将每个轨迹的图合并即可构建推理图。但随着图变大，我们判定采样轨迹的成本和方差也会增加。我们能否高效地构建“元图”或设计新的奖励？ - PPM可以被视为模仿学习的一种近似，我们现在可以自由地以任何顺序访问参考轨迹中的推理点。一个由此产生的很好特性是，*任何*目标导向的任务都可以完全由一条参考轨迹和一个足够好的评判器来决定。因此，这个框架可能在不可验证的环境中同样享有好处。 - 实际上，理解PPM的训练动态，以及数据分布、训练token预算、轨迹分段程序等因素之间的关系，对于将基于模仿的方法扩展到极长周期任务可能至关重要。为了确保方法的简单性，我们重用了标准GRPO的超参数，但可能还有一些额外的技巧可以进一步稳定训练。 我们对这个连接模仿学习和强化学习的新方法领域非常兴奋，并希望能看到新的方法来应对具有挑战性的长周期领域！ ## 致谢 我要感谢Aviral (https://aviralkumar2907.github.io/)、Kevin (https://kvfrans.com/) 和 Oleg (https://olehrybkin.com/) 对本文提供的有益反馈。 ## 引用 `` @misc{fu2026longhorizonlanguagemodelreinforcement, title={通过渐进式点匹配实现长周期语言模型强化学习}, author={Preston Fu and Kevin Frans and Oleh Rybkin and Sergey Levine and Aviral Kumar}, year={2026}, eprint={2609.07303}, archivePrefix={arXiv}, primaryClass={cs.LG}, url={https://arxiv.org/abs/2609.07303}, } ``