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

TL;DR Highlight

Random distinct peers each round plus a 3-round cutoff cut debate tokens by about 78% with similar accuracy.

Who Should Read

An agent developer running multi-LLM debate to boost accuracy who is struggling with token costs.

Core Mechanics

Pick two new distinct peers each round
- Each of the 8 agents reads answers from two distinct peers sampled at random from the others every round.
- Previously met peers can be drawn again, and no state estimation or learning is needed.
- The paper calls this Random-NoDup.
Complex routing showed no consistent gain
- Uncertainty-guided routing, stage-based switching, and AgentPrune-style learned edges were compared under matched conditions.
- At full rounds, Random-NoDup had higher macro accuracy than all of them.
- Some methods led on individual tasks, but the gains did not carry across tasks.
Short debate is enough
- Cutting at round 3 (two communication updates) kept accuracy similar while cutting tokens sharply.
- Macro accuracy was near its peak during rounds 2-5, and later rounds only added tokens.
- The paper says round 3 is an early reference point, not a uniquely optimal cutoff.
Adaptive stopping gave little benefit

Evidence

GPT-4o-mini, macro over 5 benchmarks, cost
- Round-3 Random-NoDup scored 77.33% macro accuracy at 12.36k tokens/question.
- Ring (Sparse MAD) scored 76.27% at 57.25k tokens/question.
GPT-4o-mini, full-round macro accuracy
- Random-NoDup reached 76.87% vs Ring 76.27%, uncertainty-guided routing 76.53%, and AgentPrune-style 76.27%.
- Tokens were 57.38k/question, close to Ring's 57.25k.
GPT-4o-mini, vs adaptive stopping
- Uncertainty-gated stopping got 77.20% at 18.60k/question, and majority-stability stopping 76.13% at 13.82k.
- Fixed round 3 (77.33%, 12.36k) was better on both accuracy and tokens.
Cross-model GPQA-Diamond accuracy change
- On GPT-4o-mini, round 3 got 48.67% vs 42.00% for full-round Random-NoDup.
- On GPT-5.6 Luna, GSM8K rose from 98.67% to 99.33%.

How to Apply

Try cutting your debate to 3 rounds
- If your MAD pipeline runs many rounds, compare 3 rounds against your current count on your eval set under identical conditions.
- Record accuracy and total tokens per question (input plus output).
Resample peers randomly every round
- If you use fixed neighbors, change it so each agent draws k distinct peers (the paper uses 2) uniformly from the others each round.
- Let previously drawn peers be eligible again.
Benchmark simple baselines before building a router
- If you are considering learned topologies or adaptive routing, first run random routing and short debate with the same prompts and temperature.
- If you see no gain, postpone building the router.
Validate the 3-round cutoff on your domain
- For tasks like math where longer debate may help, plot accuracy per round on your own eval set.
- Cost savings were consistent across models, but accuracy preservation varied by model and task.

Try It

copy & run

# Simplified version of the paper's method: Random-NoDup 3-round debate in Python (implement call_llm yourself)

import random

N, K, ROUNDS = 8, 2, 3

def call_llm(prompt):
    raise NotImplementedError  # replace with your LLM API call

def debate(question):
    answers = [call_llm(f"Question: {question}\nAnswer concisely.") for _ in range(N)]
    for _ in range(ROUNDS - 1):
        new = []
        for i in range(N):
            peers = random.sample([j for j in range(N) if j != i], K)
            msgs = "\n".join(f"Peer {p}: {answers[p]}" for p in peers)
            new.append(call_llm(f"Question: {question}\nYour previous answer: {answers[i]}\n{msgs}\nGive your updated final answer."))
        answers = new
    return max(set(answers), key=answers.count)

# Next: change ROUNDS between 3 and 14 and compare accuracy and token usage on the same question set.

Terminology

Multi-agent debate (MAD)Several LLM agents answer the same question, then read each other's answers and revise. It is like teammates reviewing each other's work to refine an answer.

Communication topologyThe wiring that decides who can see whose answers. Think of it as the reporting lines in a team.

Sparse communicationAgents see only some peers' answers instead of everyone's. It is like small pair reviews instead of an all-hands meeting.

Macro accuracyPer-task accuracies averaged with equal weight. Tasks with more questions do not dominate the score.

Majority-stability stoppingStop debating when the majority answer stops changing across consecutive rounds.

Related Papers

Original Abstract (Expand)

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.