State Machines Make AI Agents Predictable - Why Most Agent Designs Skip Them

Here is a claim that will annoy most people building agents right now: your agent does not have a bug, it has a state problem. The infinite loop, the duplicate refund, the “I already did that” confusion, the run that cannot be resumed after a crash - none of these are model failures. They are what happens when the only record of what an agent has done lives inside a growing pile of chat messages that nobody can query, restart from, or reason about.

The industry standard for an agent is a while loop around an LLM call. The model decides what to do next by reading the entire conversation history. That works in a demo and falls apart the moment you need to restart a run, audit a decision, or guarantee that a side effect happens exactly once. The fix is old and boring: model the agent as an explicit state machine. Most designs skip this, and it is the single largest reason agents are hard to operate in production.

The Loop Everyone Ships First

The naive agent is a reasoning loop. State is whatever is in messages.

def run_agent(task: str, max_steps: int = 15):
    messages = [{"role": "user", "content": task}]
    for _ in range(max_steps):
        resp = llm.generate(messages=messages, tools=TOOLS)
        if resp.stop_reason == "tool_use":
            result = execute_tool(resp.tool_call)   # side effect happens here
            messages.append(assistant(resp))
            messages.append(tool_result(result))
        elif "DONE" in resp.text:
            return resp.text
    return "gave up"

This is fine until it is not. The problems are not hypothetical. They show up in the same order for everyone.

The state is implicit. The only answer to “what has this agent done?” is “read all the messages and infer it.” There is no field you can check. To know whether the refund was issued, you parse tool-call history and hope the model did not summarize it away when the context got long.

The state is unbounded. Every step appends to messages. After a dozen tool calls the original task has been pushed toward the edge of the context window, so the model literally forgets the goal and starts wandering. Loops happen because the model cannot tell that calling search_orders a fourth time changed nothing.

The state is not restartable. The process crashes at step 9 of 12. What now? You cannot resume, because “step 9” is not a thing that exists anywhere - it is an emergent property of a message array that lived in RAM. So you start over, and the non-idempotent side effects from steps 1 through 8 run again. The customer gets refunded twice.

The state is not auditable. Compliance asks why the agent cancelled a subscription. Your answer is a 40-message transcript. Good luck putting that in a ticket.

Every one of these is the same root cause. The agent has state, but that state is invisible, infinite, and stuck inside the LLM’s context. You cannot operate what you cannot see.

The Reframe: An Agent Is a State Machine

Strip away the LLM for a second. What is an agent actually doing? It is moving through a set of situations, and in each situation a small number of things can happen next. That is a finite state machine. The LLM is not the machine - it is one component that picks transitions inside it.

A state machine gives you four things the loop cannot:

• A finite set of named states. At any instant the agent is in exactly one, and you can print its name.
• Explicit transitions. From state X you may go only to Y or Z. Everything else is illegal by construction, not by prompt.
• Terminal states. DONE, FAILED, NEEDS_HUMAN. The run is over when you reach one, and it is obvious that it is over.
• Serializable context. The data the machine carries between states is a plain object you can write to a database and load back.

The mental model flips. In the naive design the LLM drives and state is a side effect. In the state-machine design the machine drives and the LLM is a function you call to decide a transition or fill in a slot. The set of things that can happen is fixed by you, the engineer, at design time. The model gets to choose within those bounds, not invent new ones.

Here is the shape of a support agent as a machine.

                +-------------------+
   task ---->   |   CLASSIFY        |
                +---------+---------+
                          |
          +---------------+----------------+
          v               v                v
    +-----------+   +-----------+    +-------------+
    | GATHER    |   | RESOLVE   |    | NEEDS_HUMAN | (terminal)
    +-----+-----+   +-----+-----+    +-------------+
          |               |
          v               v
    +-----------+   +-----------+
    | RESOLVE   |   |  VERIFY   |
    +-----------+   +-----+-----+
                          |
                +---------+---------+
                v                   v
          +-----------+       +-----------+
          |   DONE    |       |  FAILED   |
          | (terminal)|       | (terminal)|
          +-----------+       +-----------+

Legal transitions are drawn on the graph. There is no arrow from CLASSIFY straight to DONE, so the agent cannot claim it finished without passing through VERIFY. That guarantee comes from the structure, not from a line in the system prompt begging the model to behave.

Building It

Start with the state and the context as data. The context is the entire memory of the run. If it is serializable, the run is restartable.

from enum import Enum
from dataclasses import dataclass, field, asdict

class State(str, Enum):
    CLASSIFY    = "classify"
    GATHER      = "gather"
    RESOLVE     = "resolve"
    VERIFY      = "verify"
    DONE        = "done"          # terminal
    FAILED      = "failed"        # terminal
    NEEDS_HUMAN = "needs_human"   # terminal

TERMINAL = {State.DONE, State.FAILED, State.NEEDS_HUMAN}

@dataclass
class AgentContext:
    run_id: str
    task: str
    state: State = State.CLASSIFY
    category: str | None = None
    facts: dict = field(default_factory=dict)
    actions_taken: list[str] = field(default_factory=list)  # idempotency ledger
    step: int = 0
    error: str | None = None

Legal transitions are a table, not scattered if statements. This table is the spec of the agent. You can review it, diff it, and hand it to someone in compliance.

TRANSITIONS = {
    State.CLASSIFY: {State.GATHER, State.RESOLVE, State.NEEDS_HUMAN},
    State.GATHER:   {State.RESOLVE, State.NEEDS_HUMAN, State.FAILED},
    State.RESOLVE:  {State.VERIFY, State.FAILED},
    State.VERIFY:   {State.DONE, State.RESOLVE, State.FAILED},
}

def transition(ctx: AgentContext, target: State) -> None:
    allowed = TRANSITIONS.get(ctx.state, set())
    if target not in allowed:
        raise IllegalTransition(f"{ctx.state} -> {target} not allowed")
    ctx.state = target

Each non-terminal state is a handler. The handler does the work for that state, then returns the next state. The LLM is called inside a handler to make a bounded decision - never to decide the whole plan.

def handle_classify(ctx: AgentContext) -> State:
    # LLM is a classifier here, not a driver. It picks one of a fixed set.
    choice = llm.classify(
        ctx.task,
        labels=["billing", "technical", "account", "unknown"],
    )
    ctx.category = choice
    if choice == "unknown":
        return State.NEEDS_HUMAN
    if choice == "billing":
        return State.GATHER      # billing needs account facts first
    return State.RESOLVE

def handle_resolve(ctx: AgentContext) -> State:
    action = plan_action(ctx)          # {"name": "refund", "args": {...}}
    key = idempotency_key(action)
    if key in ctx.actions_taken:       # already done in a previous attempt
        return State.VERIFY
    execute_tool(action)               # the only place side effects live
    ctx.actions_taken.append(key)      # record BEFORE we can crash again
    return State.VERIFY

The driver is dumb on purpose. It loops, dispatches to the current state’s handler, validates the returned transition, and persists context after every step. That last line is what makes crashes survivable.

HANDLERS = {
    State.CLASSIFY: handle_classify,
    State.GATHER:   handle_gather,
    State.RESOLVE:  handle_resolve,
    State.VERIFY:   handle_verify,
}

def run(ctx: AgentContext, max_steps: int = 25) -> AgentContext:
    while ctx.state not in TERMINAL and ctx.step < max_steps:
        ctx.step += 1
        handler = HANDLERS[ctx.state]
        try:
            nxt = handler(ctx)
            transition(ctx, nxt)
        except Exception as e:
            ctx.error = str(e)
            ctx.state = State.FAILED
        store.save(ctx.run_id, asdict(ctx))   # durable checkpoint per step
    if ctx.state not in TERMINAL:
        ctx.state = State.FAILED
        ctx.error = "max_steps exceeded"
        store.save(ctx.run_id, asdict(ctx))
    return ctx

Restart, Idempotency, and Audit for Free

Now the properties that were impossible in the loop fall out of the design.

Restart is a load. The process died at step 9. On restart you read the last checkpoint and keep going.

def resume(run_id: str) -> AgentContext:
    data = store.load(run_id)
    ctx = AgentContext(**data)
    if ctx.state in TERMINAL:
        return ctx                 # already finished, nothing to do
    return run(ctx)                # picks up from the saved state

Because actions_taken is part of the persisted context and handle_resolve checks it before acting, a resumed run does not re-issue the refund. The idempotency ledger is not bolted on; it is a field in the state. This is the difference between “we hope the retry is safe” and “the retry is safe because the record of what happened survived the crash.”

Audit is a query. Every checkpoint is a row. The state history of a run is a table you can SELECT from, not a transcript you have to read.

When compliance asks why a refund happened, you point at rows 3 and 4. When the agent misbehaves, you see the exact state it was in and the exact transition it took. Debugging stops being archaeology.

Bounded context. The LLM prompt in each handler gets only the context relevant to that state, not the whole history. handle_resolve needs the category and the facts, not the classification reasoning from step 1. This keeps prompts small, cheap, and focused, which also makes the model more accurate. The unbounded-message problem disappears because messages are no longer the state.

Naive Loop vs Explicit State Machine

Where This Does Not Fit

State machines are not free and they are not always right. Be honest about the cost.

The upfront design work is real. You have to enumerate the states and legal transitions before you write a line of handler code. For a genuinely open-ended task - “research this topic and tell me what is interesting” - you may not know the states in advance, and forcing a machine onto it produces a rigid agent that cannot follow a lead. That is exactly the case where a ReAct-style exploratory loop is the better tool. The rule of thumb: if you can draw the graph on a whiteboard, build the machine; if you cannot, you have an exploration problem, not a workflow problem.

There is also a middle path that most production systems land on, and it is worth naming: a state machine at the top level for the workflow structure, with a bounded reasoning loop living inside one or two states that genuinely need exploration. You get restartability and audit for the workflow, and flexibility where the task actually demands it. The GATHER state can run a small ReAct loop to collect facts, as long as it is capped and its output is written back into the serializable context before you transition out.

And a state machine does not make the LLM correct. The model can still classify wrong or plan a bad action. What the machine buys you is that a wrong decision happens inside a known state, gets recorded, and cannot silently corrupt the rest of the run. It converts “mysterious agent failure” into “the agent took transition X from state Y, and X was wrong,” which is a bug you can actually fix.

What To Actually Do

If you are shipping an agent that touches money, user data, or anything with a side effect, stop treating the message array as your state. Write down the states. Write down the legal transitions as a table. Put the run’s memory in a serializable object and checkpoint it after every step. Keep an idempotency ledger inside that object so retries are safe. Let the LLM decide transitions and fill slots, but never let it invent the structure at runtime.

The teams shipping agents you can actually operate are not the ones with the cleverest prompts. They are the ones who decided, before the model got involved, exactly what their agent is allowed to do and how they would know what it did. A state machine is just the most direct way to write that down.