From a chain to a graph

A request flowing through a graph, super-step by super-step: nodes light up together, writes wait at a barrier, state flows along the edges, and a step lasts as long as its slowest node.

Loading the animation…

Concept

A chain calls one step after another: retrieve, draft, review. That is enough until a step has to loop (call a tool, look at the result, decide again), run beside another step, wait for a person, or survive a crash. An agent orchestrator such as LangGraph describes the work as a graph instead: nodes are functions of a shared state, edges say what runs next, and a conditional edge (a router) picks the next node from the state, which is how an agent loops until it is done.

The graph runs in super-steps, the bulk-synchronous model of Google's Pregel (Malewicz et al., SIGMOD 2010). In each super-step, every node that an edge triggered runs, and they all read the same snapshot of the state. None of them sees another's writes: the writes wait at a barrier until the last node of the step finishes, then they are applied to the state (chapter 2 shows how), a checkpoint is saved (chapter 3), and the edges out of the nodes that ran decide the next step's nodes. When no edge triggers anything, the run is done.

The animation plays this on four small graphs. Pick fan-out: a planner triggers two researchers, which run in the same super-step; a join edge (the bar at its arrow head) waits for both before compose runs. The step lasts as long as its slowest node, so the fan-out takes 3,260 ms in 4 super-steps against 4,475 ms one node at a time, a speed-up of 1.37×. The agent loop (a model node and a tools node, with a router that loops back until three turns are done) gains nothing from the graph's parallelism, 1.00×: what it gains is the loop itself, and the checkpoints and interrupts of the next two chapters. Loop + join puts a fan-out inside a loop: the join waits afresh in each round.

Every frame comes from the engine's runtime, which runs the same graphs in real LangGraph 1.2.14 in its CI and requires the same state after every super-step: 39 sessions, 71 operations, 232 checkpoints, all equal (the data page has the details).

Maths

Let $A_s$ be the set of nodes that run in super-step $s$ and $t_v$ the time node $v$ takes. Because a step ends at its barrier, the graph's time is the sum over steps of the slowest node, plus a checkpoint write $c$ per step, as in the equation above. Running the same node runs one at a time costs $\sum_v (t_v + c)$ , so the speed-up is at most the width of the widest step, and only when the parallel nodes take equal time; a step with one slow node and one fast one wastes the fast node's slack. This is the barrier's price for a simple, reproducible model: every node in a step sees the same state, whatever order the nodes finish in.

The next nodes are decided by the edges alone: node $u$ runs in step $s+1$ if an edge from a node in $A_s$ reaches it, or a join edge into it has now heard from every one of its sources. A node reached by two plain edges in different steps runs twice (the engine's no_join session shows it, as LangGraph does); a join edge makes it wait for both.

Code

The barrier's order and the next step's nodes, cut from the vendored engine (graph.ts). Writes are sorted by task before the reducers see them (edge-triggered tasks by node name, then any Send tasks in send order, chapter 6), and the next step is every node whose trigger fired, in the order the nodes were added to the graph:

const key: [number, string, number] = i >= 0 ? [1, "", i] : [0, t, 0];

keyed.sort((a, b) => cmpKey(a[0], b[0]));

const ready = decl(this.spec).filter((n) => trig.has(n));

The same graph built in real LangGraph by the conformance check (conformance/langgraph_graphs.py), edge by edge:

if "router" in e:
    g.add_conditional_edges(src, router_fn(e["router"]), [END if t == "__end__" else t for t in e["targets"]])
else:
    g.add_edge(src, END if e["to"] == "__end__" else e["to"])