Graphs and State Machines for Agents, Part 4: Agents as State Machines

An agent finishes a task and tells you it is done. It is not done. The tests it claimed to run never ran, the file it claimed to write is empty, and the reason it stopped is that somewhere in a long chain of tokens the model decided the job was complete and emitted the word “done.” You did not build a bug. You handed the single most important decision in the whole system, the decision of when to stop and what to do next, to the least reliable component you own. The model is a wonderful guesser and a terrible dispatcher, and you let it dispatch.

Part 3, “Building the Machine,” took the five-tuple from Part 2 and gave it the three things a diagram needs to actually run: context that rides along with the state, guards that decide whether a transition fires, and actions that run as you move. This part points all of that at the thing you are really trying to build. A planning, tool-calling, self-checking, sometimes-human-in-the-loop agent. And it makes one claim, flat and early.

That agent is a finite state machine whether you draw it or not. Drawing it on purpose is the entire difference between a hopeful loop and reliability by construction.

The shift: the agent graph already went cyclic, and nobody named it

Watch how agent architectures evolved and you can see the field reluctantly admitting what the work actually is.

First came the pipeline. Prompt into prompt into prompt, a straight line, the shape Part 1 opened on. It worked until the task needed to branch, and real tasks always branch. Then the field admitted agents fail and take different roads depending on what they find, and the line became a DAG: a directed acyclic graph, fan out to independent checks, fan in to a decision. Better. Still missing the one thing that makes an agent an agent. A DAG has no way to go back. And agents go back constantly, because the core motion of a real agent is not “do the steps.” It is “try, check, and if the check fails, try again, and keep looping through a human when the stakes are high.” The moment you admit that, the acyclic in DAG breaks. The graph grows a cycle.

So the honest drawing of an agent is a directed cyclic graph. And a directed graph whose edges are labeled with the events that trigger them has a name we have been circling for three parts. It is the finite state machine, and the mapping is exact, feature for feature.

Lay the agent graph next to the five-tuple from Part 2 and every piece lines up. The nodes (planning, executing, evaluating, waiting on a human, done, failed) are S, the set of states. The edge labels (a plan is ready, a tool errored, the result is verified, the result is unsafe) are Σ, the alphabet of events. The edges are δ, the transition function that says this event, from this state, lands you there. The entry point is s0. The terminal states, done and failed, are F. Nothing added, nothing left over. The agent graph is the machine.

Retry is a guarded edge, not a hopeful counter

Start with the most common thing an agent does: it retries. The naive version lives in a while loop with a counter somebody added under deadline and hoped they got right. while (attempts < 5), a break buried three branches deep, an off-by-one that lets it run six times, or worse, a condition that never trips and bills you for a thousand model calls at three in the morning. Runaway loops are the signature failure of hopeful agents, and they come from control flow that lives in scattered ifs nobody can see whole.

In the machine there is no counter to get wrong, because retry is not a loop. It is a guarded edge. A guard is a condition on a transition that decides whether the edge fires at all, and the retry edge from evaluating back to planning carries the guard rounds < maxRounds. When the model says the work is not good enough, the machine consults the guard. If retries remain, the edge to planning fires and the agent tries again. If they are exhausted, that edge is closed, and the only remaining move is the edge to failed. The bound is not a thing you remembered to check. It is a property of the graph, and a graph with no unguarded cycle back to the start cannot run forever. You proved termination by drawing it, not by testing it and praying.

Take control flow out of the model’s hands

Here is the load-bearing move of this whole part, and most teams get it exactly backwards. They let the model decide what happens next. The model outputs “I’ll now finish” or “let me try a different approach” or “this looks good,” and the code branches on that text. That is the dispatcher problem from the opening. LLM output is nondeterministic. Let it drive control flow and you get an agent that declares itself finished when it is not, skips the review step because the sentence came out slightly different this time, and takes an action it should have gated because nothing structurally stopped it.

The fix is a clean separation, and it is the same one every serious event-driven system uses. The model does not pick the next state. The model produces text. Then you classify that text into an event from a small, fixed alphabet: VERIFIED, NOT_GOOD_ENOUGH, UNSAFE. And then the machine, not the model, checks whether that event has a legal transition from the current state.

This is the difference between a suggestion and a decision. The model suggests, in the only currency it has, which is tokens. The machine decides, by looking up (state, event) in a table. And the table is where your safety lives.

Watch what this buys you. Suppose the model, hijacked by a prompt injection in a document it read, tries to skip straight to shipping. It emits confident text, you classify it, and the classifier returns SHIP_IT. But SHIP_IT is not in the alphabet, and even if it were, there is no edge labeled SHIP_IT out of evaluating. So the lookup returns nothing and the event goes nowhere. A hallucinated event with no matching edge is inert. It cannot move the machine, because movement happens only along transitions you defined, and you did not define that one. The same structure that killed the double-click bug in Part 2 kills the hijacked-agent bug here, and for the same reason: the illegal move has no name.

Now flip it to the route you want enforced. When the evaluation flags the output as unsafe, the classifier returns UNSAFE, and there is exactly one edge for UNSAFE out of evaluating: it goes to awaitingHuman. That route is not a line in the prompt that says “please ask a human if you’re unsure,” which the model obeys on a good day and forgets on a bad one. It is a hard edge in δ. Every unsafe classification, every time, no exceptions, lands in front of a human. The model cannot route around it because the model is not doing the routing.

// Illustrative. The machine is a table of states -> legal events -> targets.
const machine = {
  initial: "planning",
  states: {
    planning:  { on: { PLAN_READY: "executing" } },
    executing: {
      on: {
        TOOL_OK: "evaluating",
        TOOL_ERROR: [
          { target: "executing", guard: (ctx) => ctx.attempts < ctx.maxAttempts },
          { target: "failed" }, // retries exhausted: the only edge left
        ],
      },
    },
    evaluating: {
      on: {
        VERIFIED: "done",
        NOT_GOOD_ENOUGH: [
          { target: "planning", guard: (ctx) => ctx.rounds < ctx.maxRounds },
          { target: "failed" },
        ],
        UNSAFE: "awaitingHuman", // enforced route, no guard, no exceptions
      },
    },
    awaitingHuman: { on: { APPROVED: "executing", REJECTED: "failed" } },
    done:   { terminal: true },
    failed: { terminal: true },
  },
};

// The model produces text. Classification turns it into an event from the alphabet.
const event = classify(modelOutput); // -> "VERIFIED" | "NOT_GOOD_ENOUGH" | "UNSAFE" | string

function step(state, event, ctx) {
  const rule = machine.states[state].on?.[event];
  if (!rule) return { state, ctx };        // no edge for this event: nothing moves
  const target = resolve(rule, ctx);       // pick the first target whose guard passes
  return { state: target, ctx: advance(ctx) };
}

// A hijacked model emits "ship it now". classify() returns "SHIP_IT".
// machine.states["evaluating"].on["SHIP_IT"] is undefined, so the event is inert.

The pair (state, context) is one small serializable value, so agents become durable

A subtler payoff falls out of the same structure, and it is the one that makes long-running agents possible at all. At any instant the machine’s entire situation is two things: which state it is in, and the context that rides with it (the plan, the attempt counts, the accumulated findings). That pair, (state, ctx), is one small value. And one small value can be serialized.

Think about what that means for an agent that has to wait. A human approval that takes three days is not a three-day-long process you keep alive, holding a socket and a chunk of memory while nothing happens. When the machine reaches awaitingHuman, you write (awaitingHuman, ctx) into a database row, kill the process, and free everything. Three days later the approval webhook fires, you read the row back, rehydrate the machine at exactly the state and context you left, feed it the APPROVED event, and it continues as if no time passed. The agent did not wait. Its state waited, in a row, costing nothing.

This is not a clever trick I am proposing. It is the foundation of an entire category of infrastructure. Durable workflow engines are built on exactly this. Temporal persists workflow state so an execution can sleep for days and resume on the same line after a process restart. AWS Step Functions goes further and makes the shape mandatory: you write the state machine out as JSON, states and transitions and all, and the service runs it durably for you. The reason those products can offer “run a workflow that pauses for a week and survives a deploy” is that the workflow was a state machine the whole time, and a state machine’s present is a value you can put in a box.

Many agents: the machine plus the actor model

Everything so far describes one agent. Scale to many and you need a second, equally old idea to pair with the machine, because the failure mode of multi-agent systems is shared mutable state: two agents writing the same memory, stepping on each other, producing races nobody can reproduce.

The answer is the actor model. Each agent is an actor: it holds its own private state, touches no one else’s, and communicates only by sending and receiving messages. And here is the join that matters for this series. Each actor’s internal behavior is a state machine, and the events that drive its transitions are the messages arriving in its mailbox. A message comes in, the actor’s machine consults δ, it moves and maybe sends messages of its own. Private state plus message-passing plus a state machine per actor. That is the whole architecture of a fault-tolerant concurrent system, and a fleet of agents is a concurrent system whether you designed it as one or not.

This is not speculative. Erlang was built on exactly this pairing in the 1980s to run telephone switches, where downtime is measured in seconds per year and a crash cannot be allowed to take the system with it. Its OTP framework ships a state-machine actor primitive named gen_statem: an actor whose behavior you define as explicit states and event-driven transitions. Telecom infrastructure has run on that primitive for decades at uptime numbers most software never approaches. When you wire a fleet of agents as actors that each run a state machine, you are not inventing a pattern. You are applying the one that has already survived forty years of the most reliability-obsessed systems ever shipped.

Verifiers on the edges, cycles that actually converge

Two more pieces carry over from the graph-engineering discipline, and they are where the machine earns its reliability instead of just claiming it.

An edge does not have to passively carry data. It can interrogate it. Put a verifier on the edge before a finding is allowed downstream, whose only job is to try to kill it. Three shapes, in rising rigor. Adversarial verify spawns several skeptic nodes, each prompted to refute the finding rather than confirm it, and keeps it only if a majority fail to break it. You are inverting the default incentive, because a model asked “is this right?” tends to agree; ask “prove this wrong” instead. Perspective-diverse verify gives each verifier a distinct lens: one checks correctness, one checks security, one checks whether it actually reproduces. Identical checks miss the same blind spots every time; different lenses catch failures the others structurally cannot see. A judge panel runs several attempts, scores them with parallel judges, and synthesizes the winner while grafting the strong pieces of the runners-up.

Verifiers cost tokens, so put them on the edges where a false result is expensive (a finding that will page a human) and skip them where a later stage sanity-checks the value anyway. Verification is an edge property you tune, not a tax you pay everywhere.

Then the cycle. An agent that loops until it is satisfied needs a loop that provably ends, and the pattern that converges is loop-until-dry: keep spawning finder nodes until K consecutive rounds surface nothing new, then stop. The make-or-break detail is the deduplication key, and it is the single thing people get wrong. You must dedupe against everything you have ever seen, including the findings you already rejected, not just the ones you confirmed. Dedupe only against confirmed results and every rejected finding reappears next round, gets rejected again, reappears again, and the loop never runs dry. It is an infinite loop wearing a convergence costume. Key the dedupe on the union of confirmed and rejected, and the termination condition can actually be reached.

From one machine to a fleet

Go back to the handle this series turns on: a prompter asks a question; an architect draws a graph. Nowhere does the difference bite harder than here. The prompter builds a more reliable agent by writing a longer, more careful system prompt, adding another “please make sure to” the model will obey until it doesn’t. The architect builds a more reliable agent by drawing the states, the events, and the transitions, and moving every safety-critical route from a sentence the model may ignore into a table it cannot escape. One of them is negotiating with a nondeterministic component. The other made the decision structural.

That structural move is what makes the next step possible. An agent you can serialize into a row, replay from an event log, and reason about state by state is an agent you can run a thousand of at once without losing the plot, because each one is a small, inspectable value moving through a table you can check. Part 5, “Running the Fleet on Frontier and Open-Weight Models,” takes exactly this reliable machine and runs it as a fleet, fanning out across cheap open-weight executors and reserving the frontier model for the nodes where judgment lives.