Graph-GRPO: Stabilizing Multi-Agent Topology Learning via Group Relative Policy Optimization

本文提出了 Graph-GRPO 框架，通过引入组相对策略优化（Group Relative Policy Optimization）对多智能体通信拓扑进行相对性能评估，有效解决了传统强化学习方法中因任务难度差异导致的梯度方差大和信用分配困难问题，从而显著提升了基于大语言模型的多智能体系统的训练稳定性与通信拓扑学习效率。

要点

这篇论文介绍了一种名为 Graph-GRPO 的新方法，旨在解决“多智能体系统”（即一群 AI 助手一起工作）中如何安排它们之间的沟通网络这一核心难题。

为了让你更容易理解，我们可以把这群 AI 助手想象成一个正在解数学题的“学生小组”。

1. 背景：为什么需要“沟通网络”？

想象一下，老师（用户）给小组出了一道难题。

• 旧方法（静态网络）： 就像老师规定：“你们必须按 A→B→C→D 的顺序传纸条”或者“大家必须围成一圈，谁想说话就喊”。这种死板的规则，遇到简单题还行，遇到难题就乱了，要么信息传不过去，要么大家七嘴八舌吵成一团。
• 现有新方法（动态网络）： 现在的 AI 能自己决定“谁和谁说话”。比如，遇到数学题，A 和 B 讨论；遇到编程题，C 和 D 结对。这很灵活，但怎么训练它们学会“选对搭档”呢？

2. 痛点：以前的训练方法像个“糊涂老师”

以前的训练方法（叫 REINFORCE）就像这样一个糊涂老师：

• 场景一（题目太简单）： 老师出了一道"1+1=？”的题。不管学生怎么乱传纸条（甚至 A 和 D 直接吵架，B 和 C 发呆），最后只要有人答对了，老师就发糖（奖励=1）。
  • 后果： 老师分不清到底是“乱传纸条”帮了忙，还是“乱传纸条”纯属运气。于是，那些没用的、多余的沟通也被当成了“好行为”奖励了。这就像学生学会了“只要瞎折腾就能得奖”，导致沟通网络越来越乱，充满噪音。
• 场景二（题目太难）： 老师出了一道奥数题。不管学生怎么努力，最后都答错了（奖励=0）。
  • 后果： 老师觉得“你们全错了”，于是把刚才所有努力过的沟通方式都批评一顿。学生根本不知道哪一步走对了，哪一步走错了，只能感到迷茫，学不到东西。

核心问题： 以前的方法只给整个小组一个“总分数”，无法告诉每个具体的“沟通连线”（比如 A 传给 B 这条线）到底有没有用。这就是论文里说的**“信用分配问题”**（Credit Assignment Problem）。

3. 解决方案：Graph-GRPO —— “对比小组”教学法

Graph-GRPO 引入了一个聪明的策略，叫**“组相对策略优化”。我们可以把它想象成“对比实验班”**。

它的做法是这样的：
对于同一道题目，老师不再只让小组试一次，而是同时派出 16 个不同的小组（组内采样），让它们用完全不同的沟通方式去解题。

• 有的小组是“链式”沟通（A→B→C）。
• 有的小组是“网状”沟通（大家乱聊）。
• 有的小组是“核心式”沟通（只有 A 和 B 聊）。

关键步骤：

1. 算平均分： 老师看这 16 个小组，算出平均得分。
2. 找“优等生”连线： 老师不再看总分，而是盯着每一条具体的连线。
   • 如果某条连线（比如 A 传给 B）在那些得分高于平均分的小组里频繁出现，老师就会说：“这条线是功臣，要奖励！”
   • 如果某条连线在那些得分低于平均分的小组里频繁出现，老师就会说：“这条线是捣乱分子，要惩罚！”
3. 去噪： 如果题目太简单，大家全对了（平均分=100），那么任何一条线都算不上“比平均水平好”，所以没有任何一条线能获得额外奖励。这就自动过滤掉了那些“瞎折腾也能赢”的噪音。

比喻总结：
以前的方法是“只要全班及格，就奖励每个人”（导致滥竽充数）。
Graph-GRPO 的方法是“在同一个班级里，谁比平均表现好，就奖励谁；谁拖后腿，就批评谁”。这样，AI 就能精准地学会：“哦，原来在解这种题时，A 传给 B 是关键，而 A 传给 C 是多余的。”

4. 成果：既聪明又省钱

论文在多个测试（如数学推理、写代码）中证明了 Graph-GRPO 的效果：

• 更准： 它比以前的最先进方法（EIB-LEARNER）准确率更高，因为它学会了剔除噪音，只保留真正有用的沟通路径。
• 更省： 它自动学会了“做减法”。因为它知道哪些连线没用，所以生成的沟通网络非常精简（稀疏）。
  • 比喻： 就像它把小组里那些只会“闲聊”的无效沟通都剪掉了，只留下“干货”交流。这不仅让解题更快，还节省了大量的“ Token"（相当于 AI 的“脑细胞”或“话费”）。

5. 一句话总结

Graph-GRPO 就像一位高明的教练，它不只看比赛结果，而是通过让队伍进行“内部对抗赛”，精准地找出哪些队员的“配合动作”真正起了作用，从而训练出一支沟通高效、没有废话、能解决复杂问题的超级 AI 团队。

技术摘要

Graph-GRPO：基于组相对策略优化的多智能体拓扑学习稳定化框架

1. 研究背景与问题定义

背景：
基于大语言模型（LLM）的多智能体系统（MAS）在复杂推理、代码生成和决策任务中展现出强大的能力。系统的性能高度依赖于通信拓扑（Communication Topology），即智能体之间信息交换的结构框架。虽然现有研究（如 EIB-LEARNER）已从静态结构转向动态生成任务特定的拓扑，但其优化范式仍存在缺陷。

核心问题：
现有的拓扑优化方法主要依赖标准的强化学习（如 REINFORCE 算法），采用单样本估计和绝对奖励（如二元正确性：1 或 0）。这种范式面临两个根本性挑战：

1. 高梯度方差（High Gradient Variance）：
   • 简单任务：许多次优的拓扑结构也能偶然得到正确答案（奖励=1）。标准方法会 indiscriminately（不加区分地）强化这些冗余边，引入大量噪声。
   • 困难任务：无论拓扑如何，系统往往都会失败（奖励=0），导致梯度消失，无法提供学习信号。
2. 信用分配问题（Credit Assignment Problem）：
   • 当拓扑成功时，标准方法将奖励平均分配给图中的所有边。这无法区分哪些连接是真正起作用的（因果贡献），哪些是冗余的，阻碍了模型学习精确的结构模式。

2. 方法论：Graph-GRPO

为了解决上述问题，作者提出了 Graph-GRPO（基于图的组相对策略优化），将组相对策略优化（Group Relative Policy Optimization, GRPO）引入离散结构搜索领域。

2.1 核心思想

不再孤立地评估单个拓扑，而是针对每个查询采样一组（Group）多样化的通信图。通过计算组内平均性能作为基线（Baseline），评估特定边在组内的相对优势（Relative Advantage）。

2.2 具体流程

1. 策略网络架构：

   • 基于 G-Designer 设计，使用图神经网络（GNN）参数化通信拓扑。
   • 包含节点编码器（Node Encoder）和结构生成器（Structure Generator）。
   • 引入有向无环图（DAG）约束，确保信息流从早期智能体流向后期智能体，避免循环依赖。
   • 输出连接概率矩阵 $P_\theta$。

2. 组采样（Group Sampling）：

   • 对于每个查询，根据 $P_\theta$ 进行 $K$ 次独立的伯努利采样，生成 $K$ 个不同的拓扑结构 $\{G_1, ..., G_K\}$。
   • 执行这些拓扑并获取二元奖励（成功=1，失败=0）。

3. 边缘级信用分配（Edge-Level Credit Assignment）：

   • 边际成功率估计：计算每条边 $e_{ij}$ 的条件成功率 $S_{ij}$。即：在组内包含该边的样本中，成功的比例。
     $$S_{ij} = \frac{\sum I(e_{ij} \in G_k) \cdot r_k}{\sum I(e_{ij} \in G_k) + \epsilon}$$
   • 相对优势计算：利用 GRPO 思想，对 $S_{ij}$ 进行归一化，计算优势值 $A_{ij}$：
     $$A_{ij} = \frac{S_{ij} - \mu_S}{\sigma_S + \epsilon}$$
     其中 $\mu_S$ 和 $\sigma_S$ 是组内所有边得分的均值和标准差。
   • 机制优势：
     • 在简单任务中（组内平均成功率高），只有表现优于平均的边（更高效的结构）获得正优势，过滤掉“容易获胜”带来的噪声。
     • 在困难任务中，通过组内对比，识别出那些在失败组中依然表现相对较好的关键路径。

4. 目标函数：

   • 最小化损失函数，包含优势加权策略更新和 KL 散度正则化（防止策略偏离初始分布）：
     $$L(\theta) = \frac{1}{|E_{batch}|} \sum (-A_{ij} \log \pi_\theta(e_{ij}|Q) + \beta D_{KL}(\pi_\theta || \pi_{ref}))$$
   • 无需 Critic 网络：相比 PPO，该方法不需要额外的价值网络，降低了显存开销并提高了训练稳定性。

3. 主要贡献

1. 范式创新：首次将组相对策略优化（GRPO）应用于多智能体系统的离散拓扑搜索，解决了绝对奖励优化中的高方差问题。
2. 细粒度信用分配：提出基于边缘（Edge-Level）的评分机制，通过组内相对优势区分关键连接与冗余噪声，有效解决了离散结构学习中的信用分配难题。
3. 无 Critic 的稳定性：通过组内归一化替代价值网络，显著提升了训练过程的稳定性，特别是在任务难度波动较大的场景下。

4. 实验结果

作者在 6 个基准测试（MMLU, GSM8K, MultiArith, SVAMP, AQUA, HumanEval）上进行了广泛实验。

• 性能表现：

  • Graph-GRPO 在所有基准测试中均达到 SOTA（State-of-the-Art）水平，平均准确率达到 92.45%。
  • 相比之前的最强基线 EIB-LEARNER，在 GSM8K 上提升 0.9%，在 HumanEval 上提升 2.1%。
  • 相比固定拓扑（如全连接图、链式结构），性能提升显著，证明了动态拓扑优化的必要性。

• 消融实验（Ablation Study）：

  • 对比“边缘级 GRPO"与“图级 GRPO"（即对整个图赋予相同优势）。结果显示，图级优化导致平均性能下降 1.82%（HumanEval 下降 2.18%）。这证实了细粒度的边缘信用分配对于识别有效推理路径至关重要。

• 效率分析：

  • Token 效率：Graph-GRPO 在保持高准确率的同时，Token 消耗量与显式剪枝方法（如 AgentPrune）相当，远低于全连接图或辩论式方法。
  • 模型自然地收敛到稀疏且语义丰富的拓扑结构，实现了准确率与 Token 成本之间的帕累托最优（Pareto-optimal）。

5. 意义与局限性

意义：

• 理论突破：揭示了在离散结构优化中，相对优势比绝对奖励更能有效指导学习，解决了长期存在的信用分配和梯度噪声问题。
• 实际应用：提供了一种无需额外 Critic 网络即可稳定训练多智能体通信拓扑的方法，为构建大规模、自组织的智能体集群（Agent Swarms）奠定了基础。
• 效率提升：证明了通过优化通信结构而非单纯增加计算量，可以显著提升系统的“信号 - 令牌比”（Signal-to-Token Ratio）。

局限性：

1. 可扩展性：策略网络基于 GAT，复杂度为 $O(N^2)$。对于超大规模智能体群（如 $N > 100$），计算可能成为瓶颈，未来需探索分层或稀疏生成策略。
2. 动态适应性：当前框架为每个查询生成单一静态拓扑。对于多轮对话中通信结构需随轮次动态调整的场景，目前尚未支持更细粒度的轮次级拓扑调整。

总结：
Graph-GRPO 通过引入组相对优化机制，成功稳定了多智能体系统的拓扑学习过程，不仅提升了复杂推理任务的性能，还实现了高效的资源利用，是迈向更智能、更自适应多智能体系统的重要一步。