Multi-Agent Coordination

Coordination is the allocation layer, not the conversation

Fix vocabulary first. A multi-agent system stacks several concerns: agents communicate (exchange messages in some protocol), sometimes negotiate or debate to resolve conflicting views, and must coordinate — agree on a division of labor and an execution order so the collective finishes the job. This article is about the third only.

Concretely, coordination answers scheduling and assignment questions — what are the sub-tasks, which agent takes each, what must finish first, who assembles the parts — none of which require an agent to hold an opinion or persuade anyone, the same questions a project manager or an OS scheduler faces. Treating it as its own layer lets you reason about speedup and overhead cleanly, without tangling it up in the harder problem of how agents agree on contested facts.

Decomposition: from one goal to a task graph

Coordination begins with decomposition: splitting a goal into sub-tasks small enough to hand out. The natural representation is a directed acyclic graph (DAG). Each node is a task; an edge A → B means B consumes A’s output, so B waits for A. Tasks with no path between them are independent and may run in parallel.

For example, ‘write a market report’ might decompose into gather_sources, three independent analyze_segment_i tasks, a synthesize depending on all three, and a proofread. The analyses form a parallel band; everything else is serial. The shape of this graph, not the number of agents, sets the parallelism ceiling: one long dependency chain has none to exploit however many agents you own. Decomposition quality — how well you expose genuinely independent work — is the single biggest lever on whether a multi-agent setup pays off.

The allocation problem, stated precisely

Given a set of tasks and a set of agents, allocation (or assignment) is choosing a mapping from tasks to agents. If every agent is identical, allocation is pure load-balancing; more realistically agents differ — a ‘researcher’ has web tools, a ‘coder’ a sandbox, a small local model is cheap but weak — so each task t has a cost c(t, a) depending on which agent a runs it. The clean formulation minimizes total cost (or makespan — the finish time of the last task) subject to the DAG’s ordering constraints. With independent tasks and one per agent this is the classic assignment problem, solved exactly by the Hungarian algorithm in O(n^3). Add precedence constraints and shared agents and it becomes DAG scheduling, NP-hard in general — exactly why real systems reach for heuristics and market mechanisms rather than optimal solvers.

Orchestrator/worker versus decentralized

The most common pattern in LLM agent systems is orchestrator/worker (manager/worker, supervisor). One privileged agent holds the task graph, decides the decomposition, hands sub-tasks to workers, collects outputs, and synthesizes the answer; workers are typically stateless toward each other. The appeal is control: allocation lives in one place, giving a single coherent view of progress, and assembly is easy because the orchestrator holds every piece. The cost is that it is a bottleneck and single point of failure whose context window must summarize a growing pile of worker output — the constraint on how many workers it can manage.

The alternative is decentralized coordination, where no agent owns the plan. A shared blackboard — a common workspace of tasks and partial results — is the classic realization: any idle agent claims a suitable task and posts its output for others to build on. This removes the bottleneck, survives an agent dying, and scales because no central context holds everything. The price is harder guarantees: two agents can claim the same task, a dropped task can go unnoticed, and detecting that the job is done becomes a distributed-termination problem. Centralization trades scalability for coherence; decentralization makes the opposite bet.

Role assignment and specialization

A middle layer between structure and allocation is role assignment: giving agents durable identities — planner, researcher, coder, critic — rather than treating them as interchangeable. Roles pre-constrain allocation: a task tagged ‘needs code execution’ routes to the coder without any per-task bidding, collapsing the assignment search space. Specialization also lifts quality, since a prompt, tool set, and context tuned for one role beats a generalist and keeps each agent’s context focused rather than bloated. The risk is rigidity and imbalance — if roles are too fine-grained, some specialists sit idle while others form a queue, and a task spanning two roles has no clean owner. Good role design mirrors the actual distribution of work: enough to route cheaply, not so much that specialists starve.

Contract-net and auction-based assignment

When agents are heterogeneous and you do not want a central planner computing an optimal assignment, let the agents bid. The Contract Net Protocol is canonical: a manager announces a task, capable agents respond with bids estimating their cost or suitability, and the manager awards the contract to the best bid — a market mechanism that distributes the assignment decision without giving up a final award step.

Auctions generalize this. In the simplest, each agent submits a private cost and the lowest bidder wins — a reverse auction that approximates the optimal assignment when agents bid true costs. Auctioning tasks one at a time gives a greedy allocation that is fast and often within a constant factor of optimal, avoiding the NP-hard global solve, and each agent needs only local knowledge of its own cost, so the mechanism scales and adapts as agents join or leave. The catch: greedy one-at-a-time awards can look good locally yet box in later assignments.

The overhead-versus-speedup tradeoff

Every coordination decision is judged against one question: did adding agents actually help? Parallel speedup is capped by the serial fraction of the work, and Amdahl’s law states it exactly. If a fraction p is parallelizable and (1 - p) is inherently serial, the best speedup with N agents is:

speedup(N) = 1 / ( (1 - p) + p/N )
as N → ∞:  speedup → 1 / (1 - p)

The serial part — planning, synthesis, the DAG’s dependency chain — sets a hard ceiling. But agents are worse than idealized processors, because coordination is not free: each handoff costs messages, each result costs tokens to summarize, contended tasks cost re-work. Model that as an overhead term o(N) that grows with the agent count, and the honest picture becomes time(N) = serial + parallel/N + o(N). Because o(N) rises while parallel/N falls, total time hits a minimum and then climbs — adding agents past that point makes the system slower.

A worked case: a 100-unit job with 20 units serial and 80 parallelizable (p = 0.8) has an Amdahl ceiling of 1/0.2 = 5×. Add o(N) = 3N units of coordination cost, so time(N) = 20 + 80/N + 3N: then time(4) = 52, time(6) ≈ 51.3, time(8) = 54. The optimum is near five or six agents; the eighth makes things worse.

Coordination pitfalls

Several failure modes recur regardless of pattern. Duplicated work: without exclusive task claims, two agents solve the same sub-task and produce conflicting outputs. Stragglers: a synthesis step waits on the slowest worker, so one badly balanced task erases the gains from every fast one — makespan is the last finisher, not the average. Deadlock or starvation: circular dependencies leave agents waiting forever, and over-narrow roles leave specialists idle while a queue builds. The most expensive quiet failure is context fragmentation: each worker sees only its slice, makes a locally reasonable choice, and the pieces do not fit — sections repeat or use incompatible assumptions. Coordination must budget for the reconciliation work of making independent parts cohere — precisely the serial cost Amdahl warns about. Most engineering is defense against these: idempotent task claims, timeouts for stragglers, cycle detection, and a synthesis step owning coherence.

Implications for CPU and small-model deployments

The math changes character when the agents are small models on CPU. Each is cheap, so launching many is tempting — but per-token throughput on CPU is low, which makes the serial parts (planning, synthesis) expensive in wall-clock terms and inflates o(N), since every handoff and summary is itself a slow model call. The Amdahl ceiling bites sooner and the optimum agent count is lower than on fast accelerators. Two levers help: keep the serial fraction tiny (a flat fan-out with thin synthesis beats a deep dependency chain), and prefer lightweight coordination such as static role routing over live auctions, since a bidding round is extra CPU-bound inference that buys little when tasks map obviously to roles. On constrained hardware the honest answer is often fewer agents than you could launch — enough for the genuinely parallel work and no more, because past the overhead minimum each extra small model is pure tax.