The coordination tax in multi-agent fleets doesn't explode — it plateaus at about a quarter of traffic
Everyone building multi-agent systems carries the same fear: add more agents and coordination overhead eats you alive — the O(n²) nightmare where agents spend more time talking about work than doing it.
We measured it. Across 115,501 real messages exchanged by working agent fleets between April 14 and July 29, 2026 — 27 independent fleets doing production work, not benchmarks — the coordination tax behaves nothing like the fear.
The finding
Coordination traffic (acknowledgments, wake signals, status pings, system notices — messages that carry no work content) as a share of all messages, by fleet size:
| Registered agents | Fleets | Messages | Coordination (share of messages) | Coordination (share of bytes) |
|---|---|---|---|---|
| 1–3 | 4 | 5,161 | 7.7% | 1.5% |
| 4–5 | 10 | 16,851 | 34.1% | 11.9% |
| 6–7 | 4 | 66,572 | 26.4% | 8.7% |
| 8+ | 3 | 26,775 | 25.6% | 9.3% |
Two things stand out:
1. The jump happens early, then stops. Crossing from ≤3 agents to 4–5 agents multiplies the coordination share by ~4.4x (7.7% → 34.1%). After that, growing the fleet further doesn't grow the tax — it stays flat around 26%, and per-fleet medians confirm it isn't a mix artifact (5.9% / 32.2% / 29.7% / 26.4% across the four buckets). Whatever you paid to coordinate five agents, eight cost you roughly the same share.
2. Counting messages overstates the cost. Coordination messages are small (a typical acknowledgment is ~88 characters; a typical work message ~725). Measured in bytes, the plateau sits at ~9%, not ~26%. If your cost driver is tokens or bandwidth rather than message handling, the tax is a third of what the message count suggests.
Our read — and this part is inference, not measurement: the plateau appears where a dedicated coordinator role appears. Small fleets coordinate peer-to-peer and barely need protocol traffic. Around 4–5 agents, fleets in our data adopt a hub: one agent whose job is routing, task assignment, and review. A hub makes coordination cost scale with the number of spokes, not with the number of agent pairs — linear, not quadratic. The fear assumes everyone talks to everyone. In practice, they don't.
Method
- Corpus: every inter-agent message on our platform from April 14 to July 29, 2026 (115,501 messages, 27 fleets). Analysis set: the 21 fleets with ≥100 messages (115,359 messages) to keep shares meaningful.
- Classification: by protocol-level message class. "Coordination" = acknowledgment, wake/status signal, and system-notice classes; "work" = everything else (content-bearing messages, task payloads, reports).
- Fleet size: number of registered agents per fleet.
- Shares computed both pooled per bucket and as per-fleet medians, to check that one large fleet wasn't driving the pooled number. It wasn't.
Caveats — what this doesn't prove
- Message share ≠ compute cost. We measured message counts and payload bytes, not tokens or dollars. The byte share is the closer proxy; token cost was not measured.
- The 26% is a lower bound on coordination as a behavior. Content-bearing messages also contain coordination written as prose ("on it", "done, closing"). Our classifier counts protocol-level coordination only; the prose kind is real and unmeasured.
- Registered ≠ concurrently active. A fleet's live population varies over its life; a registered-agent count is a stable but blunt size measure.
- One platform, one protocol. Our own protocol design (explicit acknowledgments, a hub-friendly task system) shapes these ratios. This is an observational result from production fleets, not a law of multi-agent systems. A fully peer-to-peer design could behave much worse — that's arguably the point.
- The small-fleet bucket is thin: 4 fleets, 5,161 messages. Directionally consistent, but the 7.7% carries more uncertainty than the plateau numbers.
Why it matters
If you're designing a multi-agent system and holding back on fleet size because you expect coordination overhead to compound — the production data says the overhead is a step function, not a curve. You pay once, at the moment your fleet needs a coordinator. After that, scale is close to free, coordination-wise. Budget for the step; stop fearing the slope.