When Agents Coordinate: Measuring Coordination in Multi-Agent AI Coding
Giuseppe Destefanis, Tomaso Aste
cs.AI, cs.SE
2026-08-18
Temporal networks over 1,902 multi-agent runs: quadratic messaging is mostly handshake, coordinators build no structure, file mandates cut output tokens 42% on message-heavy tasks.
Evaluations of multi-agent coding systems take one view: did the task pass, and what did the run cost. The division of labour, the messages, and the file sharing inside the team leave no trace in the final code, and two runs that pass the same tests can differ severalfold in messages, file activity, and tokens. A developer configuring such a system makes three decisions, team size, whether to name a coordinator, and whether coordination runs through direct messages or shared files, and has had little evidence to go on.
Two researchers at UCL make coordination itself the measured object: each run becomes a temporal network, collected across a controlled grid of 1,902 runs plus 244 sealed replication runs, all on Claude Code with the model pinned to claude-sonnet-4-6.
Agents and files are both nodes. A direct message is an agent-to-agent edge, a file write an agent-to-file edge, a file read a file-to-agent edge, each carrying a timestamp, a byte size, and a token cost. Making files first-class nodes is the load-bearing design choice: a file is written once and can be read by any number of agents in any order, a natural one-to-many channel, and only by putting it on the same timeline as direct messages can the two be compared. Instrumentation sits outside the agents, so any runtime that logs tool calls can feed the pipeline.
Three crossed factors: team size (1, 2, 4, 8, up to 16 in the scaling arms), structure (flat, or one agent's prompt naming it the coordinator), and file policy (forbidden, allowed, mandatory). Two task shapes: a distributed task deals four fragments of one specification to the team, which must reassemble it by coordinating; a chained task gives each agent consecutive steps of a pipeline, and the interfaces between owners must be negotiated. Ten runs per cell, eight hypotheses stated in advance (six fully pre-registered), Fisher and Mann-Whitney tests with Benjamini-Hochberg correction. The flat condition was collected twice to measure test-retest reliability, and two longer-chain scaling arms keep every agent busy at large team sizes.
| Observation | Value |
| Messages per run (distributed, allowed, 2/4/8 agents) | 6.1 / 28.5 / 71.3 |
| Chained-task messaging exponent | 1.92, replicating to two decimals across collections |
| 16-step chain, 8 to 16 agents message slope | 0.00, break significant (Δ=1.08) |
| Distributed, mandatory files @8 agents | output tokens down 42%; cache 10.5M to 6.6M |
| Chained task, same rule | output tokens up 17% (4 agents), 10% (8) |
| 16 agents, mandatory files | 578k vs 333k tokens, identical success (10/10 vs 20/20) |
| Sealed runs opening the test-file decoy | 80% of 244 |
The near-quadratic messaging growth is mostly an opening handshake. Messages per pair fall from about three at two agents to 1.27 at eight; the total rises only because there are more pairs. Past eight agents, named-peer messages drop from 34.6 to 12.2 per run while broadcasts rise from 12.3 to 34.0, and 12 of the twenty 16-agent runs coordinate by broadcast alone. The task sets the shape of the network: on the distributed task the mean sustained degree at eight agents is 5.47 against a clique line of 7, with clustering 0.81; the chained task sits at 2.99; the sixteen-step chain falls to 0.28 against 15, with only 8 of 20 runs carrying any named messaging. Neither shape has a hub: a disparity filter leaves none of the 1,170 channels at eight agents on the distributed task.
Naming a coordinator is the cleanest null of the three: no hub forms, no reliable success gain, and in the sealed replication flat and coordinator teams are level under every file policy. The sharpest failure has nothing to do with leadership: the eight-step chain passes 9/10 at two and four agents and 0/10 at eight, every failure on the same seam, step 7 (tax) and step 8 (formatting) each holding half of a rounding convention; all ten runs discussed rounding and none settled it.
Reliability is itself a finding: the chained task replicates across collections, while on the distributed task 13 of 27 cells differ after correction, message counts diverge by up to a factor of 15 at the same configuration, and the exponent moves from 1.76 to 2.44. A single run is one sample from the configuration's distribution. The main collection did not confine agents to their workspace: they opened the hidden test suite in 234 runs and read the reference solution in 77; when the sealed replication replaced the real files with marked placeholders, 80% of runs still reached for them, with no prompt ever mentioning these files.
The three configuration decisions get measured ground for the first time: budgets need not assume sustained all-to-all messaging; a coordinator title in a prompt builds no structure; the channel choice follows the task, where messaging dominates, mandating files saves about 42% of output tokens, and where files already carry the flow the rule only adds overhead. Methodologically, a single-run benchmark is shown to be a sample of size one, and the paper releases the dataset, generators, and analysis scripts. The answer-key seeking is a warning for every evaluation graded by hidden tests: without strict containment, scores are not trustworthy.
The authors are candid: two synthetic pure-function Python tasks, one runtime, one pinned model, and the specific values will not carry over; only the structural claims generalise. The channel decomposition mixes two token bases and shows direction only; run-level totals exclude cached context, the bulk of throughput, and subscription runs produced no real cost figures. The coordinator is a prompt clause with no enforced routing, so the null concerns nominal leadership; orchestrators with real scheduling power sit outside the result. Shell-issued file operations leave no edge, so file activity is undercounted, a conservative direction. At ten runs per cell a single cell's success rate carries a margin of roughly thirty percentage points. The pre-registered top-up rule flagged 93 cells and none were topped up, a deviation the authors record; intervals on the flagged hypotheses should be read with that in mind.