Designing Core Multi‑Agent Systems: Task Decomposition and Dependency‑Graph Orchestration

How Multi‑Agent Systems Work

Multi‑agent systems aim to replicate human team workflows: each agent has a dedicated role, a tailored prompt, toolset, and evaluation criteria, reducing context noise and improving performance compared to a single monolithic agent.

agents = {
    "researcher": Agent(
        role="Research and gather information",
        tools=["web_search", "document_reader"],
        model="gpt-4o",
    ),
    "coder": Agent(
        role="Write and debug code",
        tools=["code_executor", "file_writer"],
        model="gpt-4o",
    ),
    "reviewer": Agent(
        role="Review code for bugs and improvements",
        tools=["code_reader", "linter"],
        model="gpt-4o",
    ),
}

Orchestration Layer

The orchestrator (often itself an agent) performs four core tasks: task decomposition, dependency‑graph construction, routing to appropriate specialized agents, and conflict arbitration. A typical orchestration loop looks like:

async def orchestrate(task: str, agents: dict, max_rounds: int = 10):
    """Core orchestration loop – decompose, delegate, validate, repeat."""
    plan = await agents["planner"].run(
        f"Break this into subtasks with dependencies: {task}"
    )
    results = {}
    for round in range(max_rounds):
        ready = [t for t in plan if t["id"] not in results and all(d in results for d in t["depends_on"])]
        if not ready:
            break
        parallel_results = await asyncio.gather(*[
            agents[t["agent"]].run(
                t["input"],
                context={did: results[did] for did in t["depends_on"]}
            )
            for t in ready
        ])
        for task_spec, result in zip(ready, parallel_results):
            validation = await agents["reviewer"].run(
                f"Validate this output for task '{task_spec['input']}': {result}"
            )
            if validation.approved:
                results[task_spec["id"]] = result
            else:
                plan.append({
                    "id": task_spec["id"],
                    "agent": task_spec["agent"],
                    "input": f"{task_spec['input']}
Feedback: {validation.reason}",
                    "depends_on": task_spec["depends_on"],
                })
    return results

The orchestrator never performs domain work itself; it manages the dependency graph and validation‑retry cycle, forming a self‑correcting feedback loop.

Communication Protocols

Structured message exchange determines coupling, debugging difficulty, and scalability. Four common protocols are:

Message passing – moderate latency, loose coupling, suited for async event‑driven workflows.

Shared memory ("draftbook") – low latency, tight coupling, good for rapid iteration but hard to debug.

Blackboard – moderate latency, moderate coupling, central knowledge store with explicit update rules (e.g., MetaGPT’s SOP‑driven approach).

Function calls – low latency, tight coupling, direct delegation.

Production systems typically use message passing. Example message schema:

@dataclass
class AgentMessage:
    sender: str          # "researcher"
    recipient: str       # "coder" or "orchestrator"
    msg_type: str        # "result", "error", "clarification_needed"
    content: dict        # payload
    parent_task_id: str  # link back to orchestrator plan
    timestamp: float

msg = AgentMessage(
    sender="researcher",
    recipient="orchestrator",
    msg_type="result",
    content={
        "findings": "Redis supports sorted sets for leaderboards...",
        "confidence": 0.92,
        "sources": ["redis.io/docs/data-types/sorted-sets/"],
    },
    parent_task_id="task-001",
    timestamp=time.time(),
)

Consensus and Validation

Cross‑validation dramatically reduces error rates. Three patterns are described:

Debate – two agents argue opposing positions, a judge agent decides.

Voting – multiple agents solve the same problem, majority answer wins.

Hierarchical review – higher‑level agents audit outputs of lower‑level agents.

State Management

Tracking global state across agents is a major operational challenge. A practical state manager handles concurrency, conflict detection, and rollback:

class AgentStateManager:
    def __init__(self):
        self.state = {}          # current shared state
        self.history = []        # append‑only log
        self.locks = {}          # per‑key write locks

    async def update(self, agent_id: str, key: str, value: any):
        """Optimistic‑lock write to shared state."""
        async with self.locks.setdefault(key, asyncio.Lock()):
            old_value = self.state.get(key)
            self.history.append({
                "agent": agent_id,
                "key": key,
                "old": old_value,
                "new": value,
                "timestamp": time.time(),
            })
            self.state[key] = value

    def rollback_agent(self, agent_id: str):
        """Undo all changes made by a specific agent (reverse order)."""
        agent_changes = [h for h in self.history if h["agent"] == agent_id]
        for change in reversed(agent_changes):
            self.state[change["key"]] = change["old"]
            self.history.remove(change)

    def get_agent_contributions(self, agent_id: str) -> list:
        """Audit trail of what the agent changed and when."""
        return [h for h in self.history if h["agent"] == agent_id]

Effective state management requires an append‑only log, agent‑scoped rollback, and strict token‑budget enforcement because uncontrolled loops can quickly exhaust API quotas.

When to Use Multi‑Agent Systems

Adopt multi‑agent architectures only when tasks truly need distinct capabilities, exceed a single agent’s context window, benefit from cross‑validation, or have parallelizable sub‑tasks. Start with a single agent, identify failure points, and incrementally add specialized agents after empirical validation.

Five Hidden Production Pitfalls

Agent deadlock: Circular waiting between agents consumes tokens. Fix by imposing call timeouts (30‑60 s) and having the orchestrator break cycles.

Conflict writes: Concurrent edits to the same file cause lost work. Resolve with resource‑level locks managed by the orchestrator or a round‑robin execution order.

Cost amplification: Each delegation multiplies token usage (e.g., 3 agents × 4 tool calls × verification = 12 LLM calls ≈ 60 000 tokens per request). Mitigate with token budgets, depth limits, caching, and cheaper models for verification.

Responsibility attribution: Without structured logs, tracing the root cause of a bug requires reading dozens of LLM interactions. Record every agent’s input, tool calls, and output as structured events with a shared trace_id (OpenTelemetry‑style spans).

State desynchronization: An agent may act on stale configuration read before another agent’s update. Use versioned shared state or optimistic concurrency control to detect and refresh stale reads.

Common Design‑Stage Errors

Using too many agents before proving a 2‑agent setup improves quality.

Lack of shared context leads to duplicated effort and wasted tokens.

Missing cost‑circuit‑breaker mechanisms cause runaway expenses.

Only evaluating agents in isolation; end‑to‑end quality is multiplicative (e.g., 90% × 85% × 80% ≈ 61%).

Tight‑coupled agent interfaces without explicit contracts; versioned JSON schemas or protobufs are recommended.

Framework Choices

LangGraph – graph‑based workflow, high maturity.

AutoGen – conversational architecture, high maturity.

CrewAI – role‑based teams, medium maturity.

MetaGPT – SOP‑driven coordination, medium maturity.

Swarm (OpenAI) – lightweight handoff, experimental/educational.

Conclusion

Multi‑agent systems transplant human team division of labor into AI, where role specialization, ordered handoffs, and cross‑checks overcome single‑agent context limits. The orchestration layer’s design—dependency‑graph scheduling, validation‑retry loops, and protocol selection—sets the system’s ceiling far above the capabilities of individual agents. Early‑stage engineering must address deadlock detection, concurrent write conflicts, cost explosion, fault attribution, and state consistency; otherwise remediation becomes prohibitively expensive.

Practical advice: begin with two clearly defined agents, validate quality gains with data, then expand. Prioritize cross‑validation (debate, voting, hierarchical review) as Microsoft Research shows measurable accuracy improvements on reasoning benchmarks. Enforce cost monitoring from day one to avoid 3‑5× LLM spend overruns.