Parallel and Distributed Multi-Agent Workflows

"I dispatched five researchers at once, told them to report back, and then stood at the barrier doing absolutely nothing until the slowest one returned. That wait, it turns out, was the whole job."

An Aggregator Agent at a Fan-In Barrier

In the previous section we gave each agent a role: a planner that decomposes the task, executors that carry out the steps, a critic that checks the result. Roles answer "who does what". This section answers "in what order, and what can happen at the same time". The answer is a graph. The planner's decomposition is not a flat list; it is a dependency structure in which some subtasks must wait for others and some are completely independent. Drawing that structure as a directed acyclic graph (DAG) of agent steps turns a vague picture of agents talking to each other into a concrete object we can schedule, parallelize, and reason about quantitatively. This is the genuinely distributed core of the chapter, because the moment two agent calls are independent, they can and should run on two machines at once.

The framing is not a metaphor borrowed loosely from systems work; it is the identical problem. A Spark job is a DAG of stages where each stage runs in parallel across partitions and shuffles synchronize the boundaries (Section 7.4); an ML training pipeline is a DAG of steps that a scheduler executes respecting data dependencies (Section 26.2). Swap the nodes from "transform a partition" to "call an LLM agent" and every scheduling lesson carries over. What changes is the unit cost: a node here is a multi-second, multi-cent network request to a model, not a microsecond of vectorized arithmetic, which makes the parallelism worth chasing and the critical path worth shortening.

1. The Agent Workflow as a Computation Graph Beginner

Model the workflow as a DAG $G = (V, E)$. Each node $v \in V$ is one agent step, almost always one LLM call: an input prompt plus the model's response. Each edge $(u, v) \in E$ means node $v$ consumes node $u$'s output, so $v$ cannot start until $u$ finishes. The graph is acyclic for the planning portion, which is what lets us talk about a well-defined order; loops, when present, are bounded iterations layered on top, and we treat them separately in Section 2. Once the workflow is a DAG, every question we care about has a precise answer. Which steps can run at once? Any set of nodes with no path between them. When must we wait? At any node whose inputs come from more than one predecessor. How fast can the whole thing finish, given unlimited machines? The length of the longest path from a source to a sink, which we make formal below.

The four topologies in Figure 32.4.1 are the building blocks from which real workflows are assembled. A sequential chain is a path: agent one's output is agent two's input, a pipeline where each stage refines the last (extract, then summarize, then translate). A parallel fan-out/fan-in is a node that branches into several independent children which later rejoin at a single successor: a planner spawns three researchers, each investigates a different subtopic with no dependence on the others, and an aggregator waits for all three and writes the synthesis. This is the map-reduce of agents, and the resemblance is exact: the fan-out is the map (independent work per shard), the aggregator is the reduce (combine the partial results), and the barrier between them is the same shuffle boundary that Section 6.2 builds the entire MapReduce model around.

The third topology is conditional routing: a lightweight router agent inspects the input and dispatches it to the appropriate specialist, so a billing question goes to the billing agent and a code question goes to the code agent. Only the chosen branch executes, which keeps cost down and lets each specialist carry a focused prompt and toolset. This is the agent-level cousin of the content-aware request routing that serving systems already do: a model server that sends each request to the replica holding the right cached prefix or the right expert shard is solving the same dispatch-by-content problem we met in distributed inference (Section 23.2). The fourth topology, the loop, runs an agent (or a small sub-DAG) repeatedly until a condition is met: draft, check, revise, check again, stop when the checker is satisfied or a step budget is exhausted. We will see loops in their fullest form as debate and reflection in Section 32.5; here they matter as the one structure that deliberately reintroduces serial dependence, and therefore lengthens the critical path on purpose.

2. Why Parallelism Pays, and What Bounds It Intermediate

Independent agent calls are embarrassingly parallel. When three researchers investigate three unrelated subtopics, running them one after another is a choice, not a requirement, and it is almost always the wrong choice. Each call is dominated by latency: the round trip to the model plus the token-by-token generation, typically seconds. If the three calls each take time $t$, running them serially costs $3t$ while running them concurrently costs about $t$, and the saving grows linearly with the fan-out width. Because each call is also an expensive, billable request, the structure of the graph decides not just how fast the workflow finishes but how much it costs and, through the number of agents and steps you can afford, how good the answer gets. More agents and more iterations generally raise quality, and they always raise cost and (along the serial chain) latency. That three-way tension among latency, cost, and quality is the scaling-efficiency theme of Chapter 3 reappearing at the agent layer: adding workers helps only up to the point where the part you cannot parallelize dominates.

That point has a name. Let the workflow have a portion that must run serially (the planning step, the final aggregation, any loop) taking total time $T_s$, and a portion that is perfectly parallel across $K$ agents taking $T_p$ when run on one machine. The wall-clock time on $K$ machines is

This is Amdahl's law (Section 3.5), and for agent workflows it has a vivid interpretation: the serial fraction is the critical path of the DAG, the longest chain of dependent agent calls from input to output. No amount of parallelism shortens it, because each call on it waits for the previous one's output. In the fan-out of Figure 32.4.1, the critical path is plan, then one researcher, then aggregate, three calls, regardless of whether there are three researchers or thirty. Widening the fan-out adds quality and cost but cannot push the latency below that three-call floor. Narrowing the critical path, by contrast (a faster planner, a cheaper aggregation, fewer loop iterations), lowers the floor for everyone. This is why the critical path, not the agent count, is the number to watch.

A synchronization point makes this concrete. The aggregator in a fan-in is a barrier: it cannot begin until every parallel agent has returned, so its start time is the maximum of the agents' finish times, not the average. One slow agent, a straggler, holds the barrier and therefore the whole workflow, exactly the straggler problem that haunts synchronous data parallelism (Section 3.5). The remedies are familiar in spirit: cap each agent with a timeout, return partial results when one branch fails, or speculatively re-issue a lagging call. An orchestrator that schedules a DAG of LLM calls is, structurally, the same scheduler that runs a Spark stage graph or an MLOps pipeline (Section 26.2); it tracks which nodes are ready, dispatches the ready ones to free workers, and blocks barriers until their inputs arrive.

3. Measuring the Speedup From Scratch Intermediate

The claim that fan-out parallelism collapses a workflow to its critical path is easy to state and easy to test. The code below builds a small fan-out/fan-in workflow with eight independent researcher agents and one aggregator. The LLM call is stubbed by a function that sleeps for a fixed latency, which is faithful in the way that matters: a real agent call is latency-bound and spends almost all its wall-clock waiting on the network and the model, so concurrent calls overlap their waits. We run the identical DAG two ways, sequentially and with a thread pool, and report the measured speedup against the critical-path floor of two call-latencies (one researcher layer plus the aggregator).

import time
from concurrent.futures import ThreadPoolExecutor

LLM_LATENCY = 0.30  # seconds per stubbed LLM call (I/O-bound, releases the GIL)

def llm_call(prompt):
    """Stub LLM request: latency-dominated, returns a short string."""
    time.sleep(LLM_LATENCY)
    return f"notes[{prompt}]"

def researcher(subtopic):
    return llm_call(subtopic)

def aggregator(notes):
    return llm_call("summarize(" + "+".join(notes) + ")")

SUBTOPICS = [f"subtopic-{i}" for i in range(8)]

def run_sequential():
    notes = [researcher(s) for s in SUBTOPICS]   # one researcher at a time
    return aggregator(notes)                       # then the fan-in

def run_parallel():
    with ThreadPoolExecutor(max_workers=len(SUBTOPICS)) as pool:
        notes = list(pool.map(researcher, SUBTOPICS))  # fan-out, concurrent
    return aggregator(notes)                            # fan-in barrier

def timed(fn):
    t0 = time.perf_counter(); fn(); return time.perf_counter() - t0

n = len(SUBTOPICS)
seq, par = timed(run_sequential), timed(run_parallel)
serial_floor = 2 * LLM_LATENCY   # fan-out layer + aggregator on the critical path
print(f"agents (fan-out width)   : {n}")
print(f"sequential wall-clock    : {seq:.2f} s")
print(f"parallel wall-clock      : {par:.2f} s")
print(f"speedup                  : {seq / par:.2f}x")
print(f"critical-path floor      : {serial_floor:.2f} s  (fan-out layer + aggregator)")
print(f"parallel within          : {par - serial_floor:+.2f} s of the floor")

agents (fan-out width)   : 8
sequential wall-clock    : 2.70 s
parallel wall-clock      : 0.60 s
speedup                  : 4.48x
critical-path floor      : 0.60 s  (fan-out layer + aggregator)
parallel within          : +0.00 s of the floor

The sequential run takes nine call-latencies, $9 \times 0.30 = 2.70$ seconds, because nothing overlaps. The parallel run takes the critical-path floor of $0.60$ seconds, the eight researchers collapsing into a single $0.30$-second layer plus the $0.30$-second aggregator, and it does not go below that no matter how many threads we give it. The measured $4.48\times$ speedup is exactly $T(1)/T(K)$ for this DAG: $2.70 / 0.60 = 4.5$. Note what would happen if we doubled the fan-out to sixteen researchers: the sequential time would climb toward seventeen call-latencies while the parallel time would stay pinned at two, so the speedup would grow, but the parallel latency would not improve at all, because the critical path is unchanged. That is the entire trade-off in one experiment. The aggregator's dependence on every researcher is the barrier; the floor of $0.60$ seconds is the Amdahl limit; widening the fan-out buys throughput and quality, never lower latency.

from langgraph.graph import StateGraph, START, END

g = StateGraph(dict)
for i in range(8):                                   # eight independent researchers
    g.add_node(f"research_{i}", make_researcher(i))
    g.add_edge(START, f"research_{i}")               # fan-out: all start together
    g.add_edge(f"research_{i}", "aggregate")         # fan-in: aggregate waits for all
g.add_node("aggregate", aggregator_node)
g.add_edge("aggregate", END)

app = g.compile()                                    # scheduler runs the DAG, parallel where it can
result = app.invoke({"topic": "scale-out AI"})

4. Composing the Topologies Into Real Workflows Advanced

Real systems nest these shapes. A customer-support workflow might begin with conditional routing (classify the ticket, dispatch to a specialist), expand into a fan-out (the specialist spawns parallel lookups against billing, shipping, and account-history tools), collapse at a fan-in (an agent synthesizes the lookups into a draft reply), and finish with a loop (a critic checks the draft for policy compliance and sends it back for revision until it passes). The composite is still a DAG with bounded loops, and its critical path is still the longest chain of dependent calls: route, one lookup, synthesize, and however many critic iterations the loop runs. Every design decision is a move on that path. Routing keeps the fan-out narrow by sending only relevant work; the fan-out hides the lookups behind their slowest member; the loop, deliberately, lengthens the path in exchange for quality, which is why bounding its iterations is not optional.

The orchestrator's job across all of this is unchanged from the data-pipeline schedulers of Part II: maintain the readiness of each node, dispatch ready nodes to available workers, respect barriers, and bound the loops. What is new at the agent layer is that nodes can fail in soft ways a Spark task cannot. An agent may return a malformed answer, hallucinate a tool call, or simply produce something the downstream node cannot use, so the orchestrator needs validation and retry at the node level, not only crash recovery. That richer failure model, and the question of how agents check each other's work, is the natural next subject: the loop topology, taken seriously, becomes debate, critique, and reflection across agents, which is where Section 32.5 goes.