Multi-Agent Systems › Agent Coordination Mechanisms

Beyond communication protocols, agents need coordination mechanisms to handle dependencies and conflicts as well as failures. These mechanisms are what prevent a multi-agent system from devolving into chaos when things do not go according to plan.

Tasks often have dependencies: agent B's work depends on agent A's results. Explicit dependency tracking ensures agents do not start work they cannot complete.

One common approach models task dependencies as a directed acyclic graph (DAG). Each node represents a subtask, and a directed edge from node $A$ to node $B$ means task $B$ cannot start until task $A$ completes. The orchestrator traverses this graph to identify which tasks are currently eligible for execution.

Formally, a task $t$ is ready if all tasks in its dependency set $\text{deps}(t)$ have status $\text{completed}$:

$$\text{ready}(t) = (\text{status}(t) = \text{pending}) \;\land\; \forall\, t' \in \text{deps}(t) : \text{status}(t') = \text{completed}$$

where:

• $t$ is the task being checked
• $\text{status}(t)$ is the current execution status of task $t$ (pending, running, completed, or failed)
• $\text{deps}(t)$ is the set of tasks that must complete before $t$ can start
• $\land$ denotes logical AND
• $\forall$ means "for all tasks in the dependency set"

When task $A$ completes, it signals the orchestrator, which re-evaluates which tasks are now ready by checking the above condition for each pending task. The orchestrator maintains a status map (pending, running, completed, failed) for each subtask and updates it as agents report back.

Without explicit dependency tracking, an agent might try to write a summary before the research it depends on is complete, producing low-quality or hallucinated output. The DAG formulation also makes parallelism explicit: tasks with no unsatisfied dependencies can run simultaneously, and the critical path (the longest chain of dependent tasks) determines the minimum possible completion time.

Dynamic task discovery adds complexity. An agent executing a research task might discover that the user's question requires information from an additional source not anticipated in the initial task plan. Allowing agents to dynamically add tasks to the DAG enables more thorough exploration at the cost of making the system's execution time less predictable. Systems that support dynamic task addition need safeguards against unbounded expansion (e.g., depth limits, budget limits) to prevent runaway exploration.

The critical path concept from classical project management applies directly here. If the research tasks each take 10 seconds and must all complete before the analysis begins, and the analysis takes 15 seconds, and the writing takes 10 seconds, then the minimum completion time is roughly 35 seconds regardless of how many parallel agents you add to the research phase. Adding more research agents reduces the research phase to approximately 10 seconds (since they run in parallel), but the serial analysis and writing phases set an absolute floor. Understanding your system's critical path tells you exactly where parallelism will and will not help, which guides intelligent resource allocation.

When multiple agents independently address the same problem and produce different answers, the system needs a way to pick or synthesize a final answer. Several approaches exist:

Majority voting: Each of $k$ agents returns an answer from a discrete answer set $\mathcal{A}$, and the selected answer is the one appearing most often:

$$\hat{a} = \arg\max_{a \in \mathcal{A}} \sum_{i=1}^{k} \mathbf{1}[\text{answer}_i = a]$$

where:

• $k$ is the number of agents voting
• $\mathcal{A}$ is the set of candidate answers
• $\text{answer}_i$ is the answer produced by agent $i$
• $\mathbf{1}[\cdot]$ is the indicator function (1 if the condition holds, 0 otherwise)
• $\hat{a}$ is the plurality winner

This works well when answers are drawn from a finite set (for example, classification tasks) but poorly when answers are open-ended text, since two agents expressing the same idea in different words would count as distinct answers.

Self-Consistency prompting (Wang et al., 2023) applies a similar principle to a single model by sampling the model multiple times with temperature > 0 and taking the majority answer. Multi-agent voting generalizes this by using different agents (potentially with different prompts or models), which introduces diversity beyond sampling noise from a single model. The diversity is both the strength and the weakness: agents may disagree not because one is wrong but because they are each emphasizing different valid perspectives.

Judge agent: A designated judge agent receives all candidate answers and selects the best one, optionally explaining its reasoning. The judge's own biases become a concern, but the pattern works well in practice when the judge uses explicit evaluation criteria.

Synthesis: Rather than picking one answer, a synthesis agent combines the best elements from multiple candidate answers. This often produces better results than any individual answer when subagents cover different aspects of the problem.

Research on LLM debate (Irving et al., 2018; Du et al., 2023) has shown that having models argue for and against positions and then revise their answers based on the arguments improves final answer quality on reasoning tasks. The improvement comes from adversarial pressure forcing each model to address weaknesses in its own reasoning. Importantly, the agents must disagree over the answer: if agents are too agreeable (a known tendency of instruction-tuned LLMs), they will update toward each other's answers even when the other answer is wrong. Prompting agents to maintain positions unless presented with new evidence helps preserve the adversarial pressure.

The Condorcet jury theorem from political science provides a useful theoretical lens. The theorem states that if each juror independently has a better-than-random probability $p > 0.5$ of reaching the correct verdict, then a majority vote of $k$ jurors has a probability that approaches 1 as $k$ grows. Formally, the collective accuracy for an odd number of voters $k$ is:

$$P(\text{majority correct}) = \sum_{j = \lceil k/2 \rceil}^{k} \binom{k}{j} p^j (1-p)^{k-j}$$

This result has two critical implications. First, voting only improves accuracy when individual agents are better than chance. Second, the improvement has diminishing returns: the most significant gain is from moving from 1 to 3 agents, with each additional agent contributing less than the last. The practical consequence is that 5 to 7 agents is typically sufficient for majority voting; adding 20 agents instead of 7 provides marginal benefit at substantial cost.

Agents may produce conflicting outputs: two agents might claim different facts, recommend different actions, or produce code that contradicts design decisions made by another agent. Conflict resolution strategies include:

• Priority-based: A designated authority (orchestrator or specialist judge) resolves conflicts.
• Recency-based: The most recent agent output overrides older outputs (useful when task requirements have changed).
• Confidence-based: Agents express confidence in their outputs, and the higher-confidence output wins (with the orchestrator arbitrating ties).
• Human escalation: Conflicts that agents cannot resolve trigger a request for human input.

Confidence-based resolution requires agents to produce reliable confidence estimates, which is a hard problem for LLMs. Models tend to be overconfident (expressing high confidence in wrong answers) in a way that correlates imperfectly with actual accuracy. Calibration techniques (including those discussed in the Hallucination and Factuality part of this book) can improve this, but overconfidence remains a practical concern when using confidence to resolve disagreements between agents.

Human escalation deserves special attention as a design principle and a fallback. Well-designed multi-agent systems proactively identify categories of conflicts that should always involve a human rather than attempting fully automated resolution. Conflicts about high-stakes factual claims, about actions with irreversible consequences, or about requirements that depend on business context outside the system's knowledge are better escalated than resolved autonomously. Building clear escalation paths into the system architecture from the start prevents the common failure mode where automated resolution produces a confident but wrong answer on exactly the high-stakes decision where a human should have been consulted.

Agents fail. An API call might time out, a code execution might error out, or an agent might produce an output that downstream agents cannot process. Reliable multi-agent systems handle these failures gracefully:

• Retry logic: Failed subtasks are retried, potentially with modified parameters.
• Fallback agents: If the primary agent for a role fails, a backup agent with different characteristics (perhaps a simpler model) handles the task.
• Graceful degradation: If a non-critical subtask fails, the system produces a partial result rather than failing entirely.
• Dead letter queues: Failed tasks are logged for human inspection and potential manual resolution.

Fault tolerance requires the orchestrator to have a clear model of which subtasks are critical (failure is unacceptable) versus optional (failure is tolerable). Tagging tasks with criticality levels at decomposition time lets the orchestrator apply different retry budgets and escalation paths depending on the task. A failure in a verification subtask might trigger a retry with a different verifier model; a failure in an optional context-enrichment subtask might simply result in the enrichment being skipped.

The most subtle failure mode is silent success: an agent reports completion but produces incorrect or incomplete output that passes format validation. This is harder to detect than an explicit failure and more dangerous because it does not trigger retry logic. Output quality validation, separate from format validation, provides a second line of defense. Having a lightweight LLM-based evaluator check whether output content plausibly addresses the task specification catches many silent failures at modest cost.

Exponential backoff is a fault-tolerance best practice that deserves explicit attention. When an agent fails and is retried immediately, a transient infrastructure failure (e.g., a momentarily overloaded API endpoint) will likely produce another failure. Waiting between retries with exponentially increasing delays gives the underlying infrastructure time to recover, converts many transient failures into eventual successes, and prevents retry storms from amplifying system load precisely when the system is already under stress. A simple policy: wait 1 second after the first failure, 2 seconds after the second, 4 after the third, and cap at 30 seconds. This turns most transient failures into recoverable situations with minimal human intervention.