Do We Need Complex Topology Control? Distinct-Peer Random Routing Improves Cost-Efficiency in Sparse Multi-Agent Debate

Boxuan Wang; Zhuoyun Li; Xiaowei Huang; Yi Dong

cs.AISep 22, 2026

Do We Need Complex Topology Control? Distinct-Peer Random Routing Improves Cost-Efficiency in Sparse Multi-Agent Debate

Authors: Boxuan Wang, Zhuoyun Li, Xiaowei Huang, Yi Dong

Organizations: School of Computer Science and Informatics, University of Liverpool, United Kingdom

Abstract

Multi-agent debate (MAD) has emerged as a promising paradigm for improving the reasoning accuracy of large language models (LLMs) through iterative peer interaction. Communication topology plays a central role in this process, motivating increasingly sophisticated mechanisms that learn, adapt, or dynamically reconfigure agent interactions to improve accuracy or reasoning reliability. Meanwhile, prior studies suggest that much simpler sparse communication can already achieve competitive performance at substantially lower cost. In this work, we take a closer look at sparse MAD and ask whether complex topology control is actually necessary to improve collective reasoning. We find that a simple random-without-replacement routing policy, which lets each agent debate with two distinct and newly sampled peers at every round, provides a surprisingly strong baseline and consistently improves the accuracy-cost trade-off of sparse MAD. Building on this observation, we further study deliberation stopping and show that lightweight stopping can substantially reduce inference cost while preserving competitive accuracy. Our results suggest that sophisticated topology control such as learned topology adaption should be evaluated against strong simple routing and stopping baselines before its additional complexity is justified.

Figures & tables

Figure 1: An overview of the study. (a) Homogeneous sparse debate as the starting point. (b) The dual-axis routing and stopping evaluation framework. (c) Observed accuracy-cost comparison.

A Reference routing and prior sparse topology
ID	Method	Metric	ARC- Challenge	ScienceQA- text	GSM8K	MMLU-Pro	GPQA- Diamond	Macro
A1	Ring / Sparse MAD	Acc. $\uparrow$	90.67 $\pm 1.15$	96.00 $\mathbf{\pm 0.58}$	90.67 $\pm 3.06$	63.33 $\pm 3.06$	40.67 $\pm 1.15$	76.27
A1		Tok. $\downarrow$	35.99 $\pm 0.35$	33.32 $\pm 0.11$	67.76 $\pm 0.10$	64.74 $\pm 0.14$	84.43 $\pm 0.58$	57.25
A2	Small-world-inspired	Acc. $\uparrow$	90.67 $\pm 1.15$	95.33 $\pm 1.15$	92.67 $\pm 1.15$	64.67 $\pm 2.31$	42.00 $\pm 0.00$	77.07
A2		Tok. $\downarrow$	35.90 $\pm 0.09$	33.15 $\pm 0.20$	68.00 $\pm 0.10$	65.10 $\pm 0.40$	85.46 $\pm 0.51$	57.52
A3	Random-NoDup, full deliberation	Acc. $\uparrow$	91.33 $\pm 1.15$	95.67 $\pm 1.15$	90.00 $\pm 3.46$	65.33 $\pm 3.06$	42.00 $\pm 3.46$	76.87

Table 1: Five-benchmark results. Accuracy (%) and tokens (k/question) are mean

\pm

std over five seeds; macro values are mean-only. Bold marks the best observed mean for each benchmark, not significance. Red numbers denote the best macro accuracy or token cost across methods.

Figure 2: Three reference routing rules with matched received degree. The example graphs share node positions; colored arrows highlight two inputs to receiver

i

. (a) Ring keeps both local peers. (b) Small-world-inspired routing keeps one local peer and resamples one non-local shortcut. (c) Random-NoDup resamples two distinct peers. Previously contacted peers remain eligible.

GPT-4o-mini
	ARC- Challenge		GSM8K		GPQA- Diamond
Method	Acc. $\uparrow$	Tok. $\downarrow$	Acc. $\uparrow$	Tok. $\downarrow$	Acc. $\uparrow$	Tok. $\downarrow$
Ring / [-1pt]Sparse MAD	90.67 [-1.0pt] $\pm$ 1.15	35.99 [-1.0pt] $\pm$ 0.35	90.67 [-1.0pt] $\pm$ 3.06	67.76 [-1.0pt] $\pm$ 0.10	40.67 [-1.0pt] $\pm$ 1.15	84.43 [-1.0pt] $\pm$ 0.58
Random-NoDup [-1pt](full rounds)	91.33 [-1.0pt] $\pm$ 1.15	35.69 [-1.0pt] $\pm$ 0.04	90.00 [-1.0pt] $\pm$ 3.46	67.95 [-1.0pt] $\pm$ 0.18	42.00 [-1.0pt] $\pm$ 3.46	85.04 [-1.0pt] $\pm$ 0.50
Random-NoDup [-1pt](round 3)	92.67 [-1.0pt] $\boldsymbol{\pm}$ 2.31	8.04 [-1.0pt] $\boldsymbol{\pm}$ 0.00	90.00 [-1.0pt] $\pm$ 0.00	13.12 [-1.0pt] $\boldsymbol{\pm}$ 0.03	48.67 [-1.0pt] $\boldsymbol{\pm}$ 5.03	19.26 [-1.0pt] $\boldsymbol{\pm}$ 0.12
Uncertainty-guided [-1pt]routing	90.67 [-1.0pt] $\pm$ 1.15	35.78 [-1.0pt] $\pm$ 0.23	93.33 [-1.0pt] $\boldsymbol{\pm}$ 1.15	67.78 [-1.0pt] $\pm$ 0.02	40.67 [-1.0pt] $\pm$ 3.06	84.81 [-1.0pt] $\pm$ 1.02

Table 2: Cross-model accuracy (%) and tokens (k/question): mean above

\pm

SD. Bold: best mean per model–task pair. Round 3 is a same-trajectory cutoff; other runs use full rounds.

Figure 3: Random-NoDup horizon analysis. (a) Accuracy versus token cost for cutoffs of the same trajectories; the shaded region covers rounds 2–5. (b) Per-task accuracy change from round 3 to round 14.

Explore similar work

RUMAD: Reinforcement-Unifying Multi-Agent Debate
Feb 27, 2026Chao Wang, Han Lin, Huaze Tang +2Multi-Agent Debate Multi-Agent Coordination
Tsinghua University, Shenzhen, China · Zhejiang University, Hangzhou, China
ARMOR-MAD: Adaptive Routing for Heterogeneous Multi-Agent Debate in Large Language Model Reasoning
Jun 11, 2026Fuqiang Niu, Bowen ZhangMulti-Agent Debate Multi-Agent Consensus
School of Cyber Science and Technology, University of Science and Technology of China, Hefei, China · School of Artificial Intelligence, Shenzhen Technology University, Shenzhen, China
When and Why Does Multi-Agent Debate Fail and Does It Really Underperform?
Oct 23, 2025Yongqiang Chen, Gang Niu, James Cheng +2Multi-Agent Debate Multi-Agent Collaboration
1The Chinese University of Hong Kong · 2RIKEN Center for Advanced Intelligence Project · 3Hong Kong Baptist University +1

Feb 27, 2026J/K move · Enter open · S save

RUMAD: Reinforcement-Unifying Multi-Agent Debate

Chao Wang, Han Lin, Huaze Tang, Huijing Lin+1

Tsinghua University, Shenzhen, China · Zhejiang University, Hangzhou, China

Multi-Agent Debate Multi-Agent Coordination Multi-Agent Communication RL for LLM Agents

Open paper AskPDF arXiv

Multi-agent debate (MAD) systems leverage collective intelligence to enhance reasoning capabilities, yet existing approaches struggle to simultaneously optimize accuracy, consensus formation, and computational efficiency. Static topology methods lack adaptability to task complexity variations, while external LLM-based coordination risks introducing privileged knowledge that compromises debate neutrality. This work presents RUMAD (Reinforcement-Unifying Multi-Agent Debate), a novel framework that formulates dynamic communication topology control in MAD as a reinforcement learning (RL) problem. RUMAD employs a content-agnostic observation scheme that captures high-level debate dynamics avoiding access to raw agent reasoning content. RUMAD uses a multi-objective reward to model solution quality, cohesion and efficiency. A PPO-trained controller dynamically adjusts edge weights in the communication graph, while a dual-threshold mechanism enables fine-grained control over both agent activation and information visibility. Experimental evaluation across MMLU, GSM8K, and GPQA benchmarks demonstrates that RUMAD achieves substantial efficiency gains, reducing token costs by over 80%, while still improving reasoning accuracy compared to single LLM model and multiple MAD baselines. Notably, RUMAD trained exclusively on MMLU exhibits robust zero-shot generalization to out-of-domain (OOD) tasks, indicating that the learned communication strategies capture task-independent principles of effective multi-agent coordination. These results establish RUMAD as a efficient and robust approach for deploying multi-agent reasoning application with practical resource constraints.

Abstract

Explore similar work

RUMAD: Reinforcement-Unifying Multi-Agent Debate

ARMOR-MAD: Adaptive Routing for Heterogeneous Multi-Agent Debate in Large Language Model Reasoning

When and Why Does Multi-Agent Debate Fail and Does It Really Underperform?