Do Communication-Graph Rankings for LLM Agent Teams Survive Real Networks?

Teams of language-model agents that argue toward an answer ("multi-agent debate") are now routinely wired into specific communication graphs, such as rings, trees, or automatically generated structures. Published papers rank these graphs against each other and report that sparse graphs beat all-to-all communication. Every one of these rankings was measured in a sandbox where each message arrives, arrives on time, and arrives complete. Real deployments behave differently. Agents run on different servers and hit rate limits. Long answers time out. Busy "hub" agents fall behind. This proposal asks whether the published rankings of communication graphs survive when the same agent teams run on real distributed infrastructure under a wall-clock deadline. It also asks whether a cheap fix to the sandbox can predict the real ranking: replaying recorded failure traces, rather than injecting random message drops.

The bet rests on one specific feature of LLM agent networks. Their failures are not independent coin flips. The messages most likely to be late or truncated are the long, uncertain ones, and those tend to come from hard problems. Messages also fail more often on edges attached to heavily loaded agents. A ring has exactly one path between neighbors, so losing a few edges turns it into a line and roughly doubles the number of hops information must travel. If failures cluster on the content that matters most, a sparse graph's advantage from delaying consensus may reverse. Independent random drop injection would hide that reversal.

Core Claim

We claim three things. First, the ordering of communication topologies measured in lossless, synchronous sandboxes changes measurably once the same agents run across real, heterogeneous serving infrastructure with a fixed time budget. Second, most of that change is caused by failures that correlate with message content and node load, not by the overall failure rate. Third, a sandbox that replays recorded failure traces, keeping those correlations, predicts deployed rankings much better than one that drops messages at random at the same rate. We also test a constructive corollary: adding a few long-range edges to a ring keeps most of its token savings and recovers its accuracy under failure. The long-range edges follow the power-of-two hop pattern of Exponential Topology-enabled Scalable Communication in Multi-agent Reinforcement Learning, which gives any team size a logarithmic diameter.

The motivating evidence comes from a different field. In cooperative driving perception, V2V4Real collected real two-vehicle data. It found that even 100 ms of communication asynchrony significantly degrades cooperative fusion. S2R-ViT split the sim-to-real drop into a "deployment gap" (latency, localization error) and a "feature gap." Its best model reached 44.1% [email protected] on real data, against 33.4% for CoBEVT, a standard fusion method. Both works stop at two agents and do not compare graph structures. We move their deployment-gap lens to LLM agent teams, where graphs of five to twenty nodes are the object of study and where the "physical" layer is serving infrastructure rather than radio.

Research Program

The work has three parts.

Deployed runs. We build a deployment harness in which each agent in a debate team is a separate process. Open-weight models are served on heterogeneous GPUs in different cloud regions, alongside commercial API endpoints with their own rate limits. Messages travel over ordinary network calls, each round has a per-round timeout, and the whole question has a fixed wall-clock deadline. Nothing is faked, and every drop, delay, truncation, or rate-limit rejection is logged. Each log entry records the message length, the sender's degree, the round number, the model's own answer confidence, and whether the question was ultimately solved. Our "real world" is real distributed serving, not physical robots, and we say so. This is the regime in which these systems are actually deployed.

Sandbox comparison. From those logs we fit three sandboxes of increasing fidelity. The first is the standard lossless synchronous sandbox. The second drops and delays messages independently, with the per-edge rate matched to the deployment. The third replays traces conditioned on the covariates above, preserving how failures cluster by message length, node load, and time.

Evaluation. We run a fixed set of topologies through the deployment and all three sandboxes. The set covers fully connected, ring, star, tree, the ring-plus-exponential-chords variant, and task-adaptive graphs chosen by existing selectors. For each sandbox we ask how well it predicts deployed accuracy and deployed ranking.

Secondary social-dynamics testbed. We repeat the analysis on the repeated Prisoner's Dilemma setting of Evolution of Cooperation in LLM Societies. That study ran 50 GPT-4o agents on nine graphs and found that scale-free networks sustain cooperation near 0.6–0.7 while star and complete graphs collapse. It relied on "cache mirroring," which assumes symmetric play and reuses one response for both players. It also assumed every interaction completes. We rerun a subset of its topologies without mirroring and with deployed message loss. The question is whether scale-free graphs keep their advantage when the messages that fail most are those from hubs, which carry the most traffic. This extension tests whether the correlated-failure effect generalizes beyond reasoning tasks.

Baselines

Naive reference. Each topology is evaluated only in the lossless synchronous sandbox, which is the protocol used by all prior topology papers. We simply carry the resulting ranking into deployment. This is the default practice the proposal challenges. We "beat" it if its Kendall rank correlation with deployed rankings is clearly below that of trace replay.

Strongest fixed-topology method. The sparse ring debate of Improving Multi-Agent Debate with Sparse Communication Topology replaces all-to-all debate with neighbor-connected rings. In its sandbox it reports a 2% accuracy improvement on MATH over the fully connected baseline, and input-token savings of over 40% on math and over 50% on alignment tasks (Anthropic-HH). The file gives no absolute MATH accuracy for it (no reported result found on Lacuna for absolute sparse-debate MATH accuracy). We therefore first reproduce its sandbox result with the same open-weight models. Only then do we deploy it, so the comparison isolates the environment change.

Strongest adaptive-topology methods. AMAS uses a small fine-tuned adapter to pick a graph per query. It reports 0.748 on HumanEval with Llama-3 8B, against 0.728 for GPTSwarm, and 0.485 against 0.447 on Crossword. ARG-DESIGNER generates the graph edge by edge. It reports a 92.78% average across its benchmarks against 90.04% for G-Designer, with 50% fewer tokens on GSM8K. Both selectors were trained in lossless sandboxes. We run them with their released settings on the same models, questions, and deadline. We give every method the same number of agents, the same per-question token cap, and the same tuning budget for timeouts. The ring-with-chords variant beats these methods if it matches their deployed accuracy at lower token cost, or exceeds their deployed accuracy at equal cost.

Key ablation. The ablation isolates the proposal's central ingredient. We shuffle the replayed traces so that each edge keeps its failure rate but loses its correlation with message length, confidence, and node load. If the shuffled replay predicts deployed rankings as well as full replay, the correlation claim is wrong.

Why not just…?

Why not just inject random message drops in the sandbox? This is the most serious competitor, because it is nearly free. The deployed runs settle it directly. The independent-drop sandbox at matched rate is one of the three sandboxes, and we compare it to trace replay on how well each predicts deployed rankings. If failures in practice are close to independent, independent injection will match trace replay and we will recommend it instead. The shuffled-trace ablation separates "rate matters" from "correlation matters." The only evidence we have that structure matters comes from outside LLMs. The driving-perception work above attributes its deployment gap to structured latency and localization error, not zero-mean noise. That is suggestive but not proof, so this remains an open empirical question.

Why not just retry until every message arrives? Retries do make any topology lossless, at the cost of time. Multi-round sparse debate already stacks sequential dependencies, and Staircase Streaming documents large blocking delays in chained LLM generation, cutting time-to-first-token by up to 93% by removing them. VIL2C goes further: rather than waiting for late messages, it stops waiting once an agent is confident enough. That is why our primary metric is accuracy at a fixed wall-clock deadline. We include "retry until delivered" as a condition. It may win when deadlines are loose, and we will report the deadline at which it stops winning.

Why not just use full connectivity, which is naturally redundant? A dense graph survives edge loss, but it pays the costs that motivated sparsity in the first place. The sparse-debate paper found that all-to-all debate converges prematurely on wrong answers and costs 40–50% more input tokens. ExpoComm reports that dense schemes become infeasible in memory beyond roughly 20 agents, in a reinforcement-learning setting. Full connectivity stays in the topology set. If it overtakes sparse graphs under deployment, that is itself a headline result that reverses prior guidance.

Why not just let an adaptive selector pick the graph? AMAS and ARG-DESIGNER adapt to question difficulty, not to network state. Their gains of about 0.02–0.04 were measured losslessly. We run both unchanged under deployment. We also run a variant of AMAS whose adapter is retrained on replayed-trace sandboxes. This tests whether the fix lies in better training environments rather than in a different graph.

Proposed Experiments

We evaluate on MATH, GSM8K, and Anthropic-HH, following the sparse-debate paper, and on HumanEval and Crossword, following AMAS. Teams have 6, 12, and 20 agents built on Llama-3 8B and 70B class models, with a commercial-API tier to create load heterogeneity. The primary metrics are four: accuracy at a fixed wall-clock deadline, input tokens per question, Kendall rank correlation between each sandbox's topology ranking and the deployed ranking, and the mean absolute error of each sandbox's predicted deployed accuracy.

The decisive checks are three. First, does the lossless sandbox's ranking disagree with the deployed ranking beyond seed noise? We estimate that noise by repeating deployed runs across days, since infrastructure conditions drift. Second, does full trace replay recover the deployed ranking clearly better than both independent drops and shuffled traces? Third, does the ring-with-chords graph recover the ring's lossless accuracy under deployment while keeping most of its token savings? The Prisoner's Dilemma extension reports cooperation rates by topology with and without mirroring and deployed loss, against the published 0.6–0.7 scale-free figure.

A null result on the first check would also be useful. It would tell practitioners that lossless topology rankings are safe to trust, which no current paper can claim.