Cayley Graph Optimization for Scalable Multi-Agent Communication Topologies

Jingkai Luo; Yulin Shao

cs.NIApr 7, 2026

Cayley Graph Optimization for Scalable Multi-Agent Communication Topologies

Authors: Jingkai Luo, Yulin Shao

Organizations: Department of Electrical and Computer Engineering, The University of Hong Kong, Hong Kong, China

Abstract

Large-scale multi-agent communication has long faced a scalability bottleneck: fully connected networks require quadratic complexity, yet existing sparse topologies rely on hand-crafted rules. This paper treats the communication graph itself as a design variable and proposes CayleyTopo, a family of circulant Cayley graphs whose generator sets are optimized to minimize diameter, directly targeting worst-case information propagation speed. To navigate the enormous search space of possible generator sets, we develop a lightweight reinforcement learning framework that injects a number-theoretic prior to favor structurally rich generators, alongside a message-propagation score that provides dense connectivity feedback during construction. The resulting CayleyTopo consistently outperforms existing hand-crafted topologies, achieving faster information dissemination, greater resilience to link failures, and lower communication load, all while approaching the theoretical Moore bound. Our study opens the door to scalable, robust, and efficient communication foundations for future multi-agent systems, where the graph itself becomes optimizable rather than a fixed constraint.

Figures & tables

Fig. 1: Illustration of the exponential graph for

N=8

agents. Each agent connects to others at distances that are powers of two, resulting in a regular topology with diameter

\lceil\log_{2}(N-1)\rceil=3

Fig. 2: Information dissemination latency under degree budget $14$ : average rounds to $90\%$ ( $T90$ ) and $100\%$ ( $T100$ ) informed agents.

Fig. 3: Average dissemination delay ( $T90$ , rounds) versus link failure rate.

Topology	LCC@85%	Pr80-R	Pr80-D
CayleyTopo	84.27%	100%	100%
ExpoComm	83.12%	85%	0%
Fibonacci	69.22%	55%	0%
Simple Prime	74.99%	65%	0%
Broadcast Mode	14.10%	0%	0%

TABLE I: Robustness at

85\%

link failures: mean LCC size (% of agents) and

\Pr[\mathrm{LCC}\!\geq\!80\%]

under random (Pr80-R) and distance-biased (Pr80-D) removals.

Topology	Avg.	Std. dev.	Range
CayleyTopo	$140.7$	$16.1$	$76.8$
ExpoComm	$325.3$	$212.1$	$614.4$
Fibonacci	$271.3$	$188.7$	$599.0$
Simple Prime	$178.5$	$82.2$	$399.4$
Broadcast Mode	$768.0$	$0.0$	$0.0$

TABLE II: Per-step bandwidth consumption over

50

simulation time steps under the hybrid communication schedule (same scenario as Fig. 4 ). Values are scaled by

10^{-3}

relative to raw simulator counts. Lower average indicates lower overhead; standard deviation and range (max-min) quantify temporal variability.

Fig. 4: Cumulative communication-count over time. Lower values indicate fewer occupied transmission blocks.

Fig. 5: The graph diameter against the Moore bound under matched degree.

Fig. 6: Visualization of CayleyTopo on a reduced ring, where $N=20$ .

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
Graph-GRPO: Stabilizing Multi-Agent Topology Learning via Group Relative Policy Optimization
Mar 3, 2026Yueyang Cang, Xiaoteng Zhang, Erlu Zhao +7Communication Topology Optimization Multi-Agent Communication Topology
Tsinghua University · Donghua University
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

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

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

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