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

Yueyang Cang; Xiaoteng Zhang; Erlu Zhao; Zehua Ji; Yuhang Liu; Yuchen He; Zhiyuan Ning; Chen Yijun

cs.CLMar 3, 2026

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

Authors: Yueyang Cang, Xiaoteng Zhang, Erlu Zhao, Zehua Ji, Yuhang Liu, Yuchen He, Zhiyuan Ning, Chen Yijun,

Organizations: Tsinghua University · Donghua University

Abstract

Optimizing communication topology is fundamental to the efficiency and effectiveness of Large Language Model (LLM)-based Multi-Agent Systems (MAS). While recent approaches utilize reinforcement learning to dynamically construct task-specific graphs, they typically rely on single-sample policy gradients with absolute rewards (e.g., binary correctness). This paradigm suffers from severe gradient variance and the credit assignment problem: simple queries yield non-informative positive rewards for suboptimal structures, while difficult queries often result in failures that provide no learning signal. To address these challenges, we propose Graph-GRPO, a novel topology optimization framework that integrates Group Relative Policy Optimization. Instead of evaluating a single topology in isolation, Graph-GRPO samples a group of diverse communication graphs for each query and computes the advantage of specific edges based on their relative performance within the group. By normalizing rewards across the sampled group, our method effectively mitigates the noise derived from task difficulty variance and enables fine-grained credit assignment. Extensive experiments on reasoning and code generation benchmarks demonstrate that Graph-GRPO significantly outperforms state-of-the-art baselines, achieving superior training stability and identifying critical communication pathways previously obscured by reward noise.

Figures & tables

Figure 1: Motivation Analysis: The Trap of Non-Informative Batches in Easy Queries. The figure illustrates a scenario where a task is simple enough that diverse sampled topologies (Samples 1–4, ranging from efficient chains to dense structures with redundant edges) all yield correct answers and identical rewards ( $R_{k}=1$ ). (Top Right) Standard policy gradient methods like REINFORCE use raw rewards. Since $R_{k}\equiv 1$ across the entire group, the gradient estimation indiscriminately reinforces all sampled edges, including noise and redundancies (e.g., extra edges in S3 & S4), leading to suboptimal convergence. (Bottom Right) Our proposed Graph-GRPO addresses this by incorporating a group baseline $\mu$ . In such uniform-reward scenarios, $\mu$ equals individual rewards, resulting in near-zero advantage ( $A_{ij}\approx 0$ ). This mechanism effectively blocks parameter updates from non-informative batches, preventing the model from learning redundant structures from noise.

Figure 2: The overall framework ofGraph-GRPO . (1) Policy Network & Construction: The module encodes agent roles and the task query using a GAT-based encoder to generate a probabilistic connectivity matrix $P_{\theta}$ , constrained by a DAG mask to ensure acyclic flow. (2) Group Sampling (Exploration): Instead of a single estimation, we generate a group of $K$ diverse topologies via independent Bernoulli sampling. This exploration captures various structural patterns, where successful topologies receive positive rewards (Reward=1) and failures (e.g., disconnected graphs) receive zero. (3) Edge-Level Graph-GRPO: The core optimization phase. We calculate a group baseline $\mu$ and estimate the specific advantage of each target edge $e_{ij}$ . Edges that result in a success rate higher than the baseline ( $A_{ij}>0$ ) are reinforced, iteratively updating the policy parameters $\theta$ .

Method	MMLU	GSM8K	AQuA	MultiArith	SVAMP	HumanEval	Avg.
Vanilla	80.39	82.30	71.06	93.09	86.55	71.39	80.80
CoT	81.69	86.50	73.58	93.25	87.36	74.67	82.84
SC (CoT)	83.66	81.60	75.63	94.12	88.59	79.83	83.91
Chain	83.01	88.30	74.05	93.27	87.17	81.37	84.53
Tree	81.04	85.20	71.23	93.68	88.91	80.53	83.43
Complete	82.35	80.10	72.95	94.53	84.01	79.03	82.16

Table 1: Performance comparison (%) on six benchmarks. The best results are highlighted in bold , and the second best are underlined . Baseline results are retrieved from Shen et al. (2025) .

Method	MMLU	GSM8K	HumanEval	Avg.
Graph-GRPO	90.12	96.10	91.25	92.49
Graph-Level GRPO	88.54	94.40	89.07	90.67
$\Delta$	-1.58	-1.70	-2.18	-1.82

Table 2: Ablation study on optimization granularity: Edge-Level vs. Graph-Level.

Figure 3: Token efficiency analysis on MMLU and GSM8K benchmarks. The bubble size represents the relative token consumption. Graph-GRPO (Red) achieves the highest accuracy (positioned furthest to the right) while maintaining a low token cost comparable to EIB-LEARNER (Purple) and G-Designer (Pink) . Our method effectively suppresses redundant edges without explicit pruning constraints, achieving a superior performance-efficiency trade-off compared to complete graphs (Blue) and debate-based baselines (Brown).

Communication Topology Optimization

See all 11 papers

GoAgent: Group-of-Agents Communication Topology Generation for LLM-based Multi-Agent Systems
Mar 20, 2026Hongjiang Chen, Xin Zheng, Yixin Liu +7Multi-Agent Communication Topology Multi-Agent Communication
School of Cyberspace, Hangzhou Dianzi University, Hangzhou, China · School of Computing Technologies, RMIT University, Melbourne, Australia · School of Information and Communication Technology, Griffith University, Goldcoast, Australia
Reward-Guided Autoregressive Graph Generation for Efficient Multi-Agent Communication Topology Design
Aug 20, 2026Poomphob Suwannapichat, Boonyarit Changaival, Caesar Wu +1Multi-Agent Communication Topology Graph Generation
University of Luxembourg, Luxembourg · King Mongkut’s University of Technology Thonburi, Thailand
Discovering Efficient and Explainable Communication Topologies for LLM-based Multi-Agent Systems via Causal Inference
Aug 13, 2026Junzhi Li, Peng He, Qirui Ji +3Multi-Agent LLM Systems Causal Attribution
University of Chinese Academy of Sciences · National Key Laboratory of Space Integrated Information System, Institute of Software, Chinese Academy of Sciences · Beijing University of Posts and Telecommunications

Mar 20, 2026J/K move · Enter open · S save

GoAgent: Group-of-Agents Communication Topology Generation for LLM-based Multi-Agent Systems

Hongjiang Chen, Xin Zheng, Yixin Liu, Pengfei Jiao+6

School of Cyberspace, Hangzhou Dianzi University, Hangzhou, China · School of Computing Technologies, RMIT University, Melbourne, Australia · School of Information and Communication Technology, Griffith University, Goldcoast, Australia

Multi-Agent Communication Topology Multi-Agent Communication Multi-Agent LLMs

Open paper AskPDF arXiv

Large language model (LLM)-based multi-agent systems (MAS) have demonstrated exceptional capabilities in solving complex tasks, yet their effectiveness depends heavily on the underlying communication topology that coordinates agent interactions. Within these systems, successful problem-solving often necessitates task-specific group structures to divide and conquer subtasks. However, most existing approaches generate communication topologies in a node-centric manner, leaving group structures to emerge implicitly from local connectivity decisions rather than modeling them explicitly, often leading to suboptimal coordination and unnecessary communication overhead. To address this limitation, we propose GoAgent (Group-of-Agents), a communication topology generation method that explicitly treats collaborative groups as the atomic units of MAS construction. Specifically, GoAgent first enumerates task-relevant candidate groups through an LLM and then autoregressively selects and connects these groups as atomic units to construct the final communication graph, jointly capturing intra-group cohesion and inter-group coordination. To mitigate communication redundancy and noise propagation inherent in expanding topologies, we further introduce a conditional information bottleneck (CIB) objective that compresses inter-group communication, preserving task-relevant signals while filtering out redundant historical noise. Extensive experiments on six benchmarks demonstrate the state-of-the-art performance of GoAgent with 93.84% average accuracy while reducing token consumption by about 17%.

Abstract

Communication Topology Optimization

Explore similar work

GoAgent: Group-of-Agents Communication Topology Generation for LLM-based Multi-Agent Systems

Reward-Guided Autoregressive Graph Generation for Efficient Multi-Agent Communication Topology Design

Discovering Efficient and Explainable Communication Topologies for LLM-based Multi-Agent Systems via Causal Inference