GraphPO：面向推理模型的基于图策略优化

# GraphPO：基于图的策略优化用于推理模型

来源：https://arxiv.org/html/2606.18954

Yuliang Zhan1,∗ Xinyu Tang1,∗ Jian Li1 Dandan Zheng2 Weilong Chai2 Jingdong Chen2 Jun Zhou2 Ge Wu2 Wenyue Tang2 Hao Sun1

1中国人民大学高瓴人工智能学院
2蚂蚁集团

###### 摘要

带可验证奖励的强化学习（RLVR）已成为提升大型推理模型能力的标准范式。RLVR 通常独立采样响应并基于最终答案优化策略。该范式存在两个局限性。首先，独立响应往往包含相似的中文推理步骤，导致冗余探索和计算浪费。其次，稀疏的最终答案奖励使得难以识别有用的步骤。基于树的方法通过共享前缀并比较来自同一前缀的分支以提供细粒度信号，部分解决了这个问题。然而，树的分支仍然是独立展开的。当不同分支达到相似的推理状态时，它们无法共享信息并重复类似的探索。此外，基于树的方法忽略这种分散性，仅在独立分支内进行局部比较，这可能导致优势估计的方差更高。为了解决这一挑战，我们提出了GraphPO（基于图的策略优化），一种新颖的强化学习框架，它将展开过程表示为一个有向无环图，其中推理步骤作为边，从推理路径中总结出的语义状态作为节点。GraphPO 将语义等价的推理路径合并为等价类，使它们能够共享后缀，并将预算从冗余展开重新分配到多样化探索中。此外，我们为入边分配效率优势，为出边分配正确性优势，从而在从结果中推导过程监督的同时提高推理效率。理论上表明，GraphPO 降低了优势估计方差并提高了推理效率。在三个大型语言模型上的推理和智能体搜索基准实验表明，在相同 token 预算或响应预算下，GraphPO 始终优于基于链和基于树的基线方法。代码即将发布。

11脚注：共同第一作者。
22脚注：通讯作者。

## 1 引言

近年来，大型推理模型（LRMs）在智能体、编程和数学推理任务中取得了里程碑式的进展[7 (https://arxiv.org/html/2606.18954#bib.bib4),31 (https://arxiv.org/html/2606.18954#bib.bib11),39 (https://arxiv.org/html/2606.18954#bib.bib12)]。它们通常采用带可验证奖励的强化学习（RLVR），其中最终答案的正确性被用作二值奖励来优化策略[1 (https://arxiv.org/html/2606.18954#bib.bib6),47 (https://arxiv.org/html/2606.18954#bib.bib7),45 (https://arxiv.org/html/2606.18954#bib.bib5)]。有效的强化学习既需要准确的信度分配用于策略更新，也需要在采样过程中进行多样化探索。然而，当前的 RLVR 方法仍然在这两方面面临困难。首先，结果奖励本质上是稀疏的，这使得对贡献于最终答案的中间推理步骤进行信度分配变得困难[19 (https://arxiv.org/html/2606.18954#bib.bib10),27 (https://arxiv.org/html/2606.18954#bib.bib13)]。其次，RLVR 方法通常独立采样响应，不同响应中往往包含重复的中间推理步骤，这导致大量采样冗余并限制了探索多样性[42 (https://arxiv.org/html/2606.18954#bib.bib21),13 (https://arxiv.org/html/2606.18954#bib.bib14)]。

为了准确进行奖励信度分配，现有方法引入了步骤级信号。过程奖励模型（PRMs）[28 (https://arxiv.org/html/2606.18954#bib.bib15),33 (https://arxiv.org/html/2606.18954#bib.bib16),46 (https://arxiv.org/html/2606.18954#bib.bib46)] 对中间推理步骤进行奖励，帮助策略识别贡献于最终答案的步骤。然而，它们通常需要昂贵的步骤级标注，并且在不同领域之间泛化能力较差。此外，最近的一些方法避免使用显式的 PRMs，而是通过中间状态值估计，例如基于搜索的估计[2 (https://arxiv.org/html/2606.18954#bib.bib17),25 (https://arxiv.org/html/2606.18954#bib.bib18)] 和从结果奖励中提取过程信号[4 (https://arxiv.org/html/2606.18954#bib.bib19),5 (https://arxiv.org/html/2606.18954#bib.bib29)]。尽管这些方法通过提供更密集的监督信号缓解了奖励稀疏性问题，但它们仍然依赖于基于链的展开，无法捕捉独立展开之间的相似性（图1 (https://arxiv.org/html/2606.18954#S1.F1)a），这既限制了信度分配也限制了探索效率。

为了解决这一挑战，*基于树的强化学习方法* 将展开组织成树结构[42 (https://arxiv.org/html/2606.18954#bib.bib21),13 (https://arxiv.org/html/2606.18954#bib.bib14),44 (https://arxiv.org/html/2606.18954#bib.bib9),16 (https://arxiv.org/html/2606.18954#bib.bib20),32 (https://arxiv.org/html/2606.18954#bib.bib22),12 (https://arxiv.org/html/2606.18954#bib.bib23),8 (https://arxiv.org/html/2606.18954#bib.bib30)]，其中共享的前缀避免了重复推理，分支点提供了细粒度的监督（图1 (https://arxiv.org/html/2606.18954#S1.F1)b）。尽管有这些优点，树结构展开仍然存在三个局限性。第一，更深的树给了不确定的中间状态更多机会达到正确答案，但这种优化可能鼓励冗余的推理步骤并*降低推理效率*。第二，提前终止的路径提供有限的训练信号，*降低了利用效率*。第三，树只共享早期前缀。分支发散后，它们可能仍然达到相似的中间状态并独立展开，导致冗余探索并*限制探索效率*，如第3节 (https://arxiv.org/html/2606.18954#S3) 所述。这些局限性源于相同的结构约束：树将分支视为独立路径。因此，它们无法表示由不同路径达到的等价状态，无法比较这些路径的效率，也无法在这些状态之后重用后续推理。

基于这一观察，我们将展开建模为一个有向无环图，它显式地聚合了等价的推理状态。

参见说明

图1：展开策略的比较。(a) 链式展开采样独立轨迹。(b) 树式展开共享前缀。(c) 图式展开合并语义相似的状态。

基于这一见解，我们提出了GraphPO（基于图的策略优化），一个新颖的强化学习框架，它将推理展开表示为一个强化学习图，其中边表示生成的推理步骤，节点表示从初始提示的推理路径总结出的中间语义状态（图1 (https://arxiv.org/html/2606.18954#S1.F1)c）。在基于图的展开过程中，GraphPO 通过检测跨路径的语义相似状态，并将相似推理虚拟合并为等价类，逐步构建强化学习图。这些等价类使 GraphPO 能够通过路径比较、信号共享和冗余减少来*提高推理*、*利用*和*探索效率*。首先，达到等价类的路径解决了类似的子问题。因此，GraphPO 引入了一个路径级效率优势，奖励每个类内的较短路径，引导学习到的策略向更高效的推理发展。其次，同一等价类内的推理共享相同的语义状态，因此它们后续的正确性样本可以共享。因此，GraphPO 通过在相似推理之间共享后续正确性信号来提高利用效率，这产生了更密集的步骤级奖励。即使提前终止的分支也能从等价伙伴那里获得信度，提高了展开利用率并稳定了策略更新。第三，当一条路径到达一个已发现的等价类时，进一步的展开很可能是冗余的。GraphPO 减少其下一层预算，并将节省的计算重新分配给新颖的前沿状态，从而在相同 token 预算下鼓励更广泛的探索。如第3节 (https://arxiv.org/html/2606.18954#S3) 所述，这有效地提高了探索效率。

* 我们引入了 GraphPO，一种基于图的强化学习框架，它合并语义相似的推理以减少冗余探索，提高展开利用率，并获得步骤级奖励。
* 我们提出了一种双组图优势估计方法，通过在每个等价类内比较入边来提高推理效率，并通过在每个节点比较出边来提高推理性能。
* 大量的实验和理论分析表明，在相同的展开预算或响应预算下，GraphPO 取得了更好的性能。

## 2 相关工作

**带稀疏监督的强化学习。** RLVR 使用二值结果奖励驱动大型推理模型的后训练[7 (https://arxiv.org/html/2606.18954#bib.bib4),31 (https://arxiv.org/html/2606.18954#bib.bib11),45 (https://arxiv.org/html/2606.18954#bib.bib5)]，但这个信号对于关键的推理步骤信度分配来说过于稀疏[19 (https://arxiv.org/html/2606.18954#bib.bib10),35 (https://arxiv.org/html/2606.18954#bib.bib47)]。一个常见的补救措施是使用过程奖励模型来密集化监督[28 (https://arxiv.org/html/2606.18954#bib.bib15),33 (https://arxiv.org/html/2606.18954#bib.bib16),46 (https://arxiv.org/html/2606.18954#bib.bib46),48 (https://arxiv.org/html/2606.18954#bib.bib39)]，但它们在需要昂贵的标注并且在不同领域之间迁移效果差。最近的工作通过值估计[2 (https://arxiv.org/html/2606.18954#bib.bib17),25 (https://arxiv.org/html/2606.18954#bib.bib18)]、隐式奖励[4 (https://arxiv.org/html/2606.18954#bib.bib19),22 (https://arxiv.org/html/2606.18954#bib.bib49),9 (https://arxiv.org/html/2606.18954#bib.bib50)] 或分段级信度分配[27 (https://arxiv.org/html/2606.18954#bib.bib13),5 (https://arxiv.org/html/2606.18954#bib.bib29),8 (https://arxiv.org/html/2606.18954#bib.bib30)] 从结果中推导过程信号，减少了对标注的依赖。这些方法从独立展开中估计监督信号。因此，来自语义等价状态的结果无法相互支持。GraphPO 将这些状态合并为等价类，实现后缀共享，为信度分配提供更密集、方差更低的样本。

**用于强化学习的树搜索。** 树结构展开在扩展过程中共享前缀，使得它们能够在相同 token 预算下生成比传统 RLVR 方法更多的轨迹。这些轨迹中的分支点自然地提供了步骤级比较。[42 (https://arxiv.org/html/2606.18954#bib.bib21),44 (https://arxiv.org/html/2606.18954#bib.bib9),16 (https://arxiv.org/html/2606.18954#bib.bib20),12 (https://arxiv.org/html/2606.18954#bib.bib23)]。最近的变体通过重用公共前缀、将分支扩展调度到信息量大的状态、或通过前瞻扩展前沿分支，进一步提高了效率[13 (https://arxiv.org/html/2606.18954#bib.bib14),32 (https://arxiv.org/html/2606.18954#bib.bib22),38 (https://arxiv.org/html/2606.18954#bib.bib51),30 (https://arxiv.org/html/2606.18954#bib.bib56),14 (https://arxiv.org/html/2606.18954#bib.bib53)]。这些方法共享前缀，但它们的树拓扑仍然将发散的分支视为独立的，即使它们后来达到语义等价的状态。而 GraphPO 将这些状态合并成一个有向无环图，通过在每个等价类内进行长度比较、信号共享和预算重新分配，从而提高奖励利用和探索效率。

## 3 实证研究

在本节中，我们分析展开策略的推理冗余和探索效率。

**实验设置。** 遵循 PROS[13 (https://arxiv.org/html/2606.18954#bib.bib14)]，我们对每个提示采样 64 条推理轨迹。为了减少表达变异并更好地捕捉潜在语义，我们使用 Qwen2.5-7B-Instruct[41 (https://arxiv.org/html/2606.18954#bib.bib26)] 总结中间推理状态，并使用 SFR-Embedding-2-R[23 (https://arxiv.org/html/2606.18954#bib.bib25)] 测量摘要相似度，遵循 MIRB[18 (https://arxiv.org/html/2606.18954#bib.bib24)]。我们使用 MATH500[11 (https://arxiv.org/html/2606.18954#bib.bib27)]，并比较独立链式、树式和图式采样策略，使用 Qwen2.5-7B-Math[40 (https://arxiv.org/html/2606.18954#bib.bib34)] 进行采样。

参见说明

图2：语义冗余和探索效率的实证研究。(a) 跨前缀窗口大小的成对归一化编辑相似度。(b) 跨前缀窗口大小的语义相似度。(c) 不同采样策略下的探索效率。对于 (a) 和 (b)，每个小提琴图中较宽的区域表示成对分数分布更密集。

**链式和树式结构化采样包含大量语义冗余。** 为了展示不同采样策略产生的冗余，我们为每个提示提取不同窗口大小下的展开前缀。对于每个前缀，我们计算其与其他轨迹的较短前缀的语义相似度和 Rouge-L[21 (https://arxiv.org/html/2606.18954#bib.bib28)] 分数。图2 (https://arxiv.org/html/2606.18954#S3.F2)a 和 2 (https://arxiv.org/html/2606.18954#S3.F2)b 显示了在不同前缀窗口大小下成对语义相似度和 Rouge-L 分数的分布，其中许多前缀与其他路径的前缀高度相似（相似度 > 0.9）。这表明基于链和树的展开都经常访问相似的中间推理状态。具体而言，图2 (https://arxiv.org/html/2606.18954#S3.F2)a 显示链式采样产生了高度相似的较短前缀，表明早期推理步骤中存在大量冗余。基于树的采样通过共享前缀减少了这种早期冗余，从而在相同 token 预算下提高了探索多样性。然而，图2 (https://arxiv.org/html/2606.18954#S3.F2)b 显示树前缀仍然具有高语义相似度，相似度分数接近链式采样。这表明树结构通过共享祖先减少了部分重复计算，但它仍然独立地达到并展开语义相似的推理，导致冗余探索。特别是，当两个分支已经达到了语义相似的状态时，树结构仍然将它们视为独立节点并继续单独展开。

这些观察结果启发了一种基于图的展开结构。图不仅共享精确的前缀，还能跨不同分支连接语义相似的中间状态。这样，后续的展开可以重用来自相关状态的信息，并自适应地重新分配展开预算，而不是孤立地展开每个相似状态。这种图结构减少了冗余探索，并为跨推理步骤的信度分配提供了更细粒度的基础。

**图结构将语义冗余转化为探索效率。** 为了检验图结构化采样是否将冗余转化为有用的探索，我们在不同 token 预算下测量探索效率。随着预算增加，链式采样增加更多独立展开，而树式和图式采样增加分支因子和深度。对于当前的 n 条展开，设 S_n 表示所有推理步骤，设 |s| 表示 token