The Probabilistic State Machine: Why Linear Chains Fail

A pipeline is a satisfying thing to build. Data enters at one end, transformations happen in sequence, results emerge at the other. The topology is a straight line — or more precisely, a Directed Acyclic Graph — and its acyclic property is a feature, not a constraint. In classical data engineering, cycles mean bugs.

Then Large Language Models arrived, and the straight line became a liability.

LLMs are probabilistic: every node in your pipeline is a dice roll. The output of Step B is not determined by the input — it is sampled from a probability distribution conditioned on the input. Chain three such steps together, each at 90% reliability, and system-level reliability collapses to 72.9%. Add a fourth and you are at 65.6%. This is a compounding bet, and the house always wins eventually.

The architecture that solves this is the Probabilistic State Machine — a cyclic graph that treats model failure not as an exceptional event, but as a predictable condition to be handled. The shift from chain to state machine is the single most consequential architectural decision in production AI engineering.

The Reliability Arithmetic Nobody Talks About

If each step in a sequential pipeline has reliability R, and steps are independent, system reliability is:

R_system = R₁ × R₂ × R₃ × ... × R_n

The table below is illustrative reliability math, not a benchmark. It assumes independent failures and clean retry conditions. Real systems often have correlated errors, which makes the boundary case more important rather than less important.

At 90% per step — a deliberately round example for complex reasoning — the numbers degrade fast:

The last row is the point. The chain asks: "Will the model succeed on every step, every time?" The state machine asks: "Will the model succeed on at least one attempt per step, given structured feedback?" The second question has a much better answer.

Under the independence assumption, a 3-step LLM chain operating at 90% per-step reliability produces a system that fails more than 1 in 4 requests.

Hallucination Inertia: The Physics of Getting Stuck

An LLM does not reason and then speak. It speaks its way into reasoning. Each token is conditioned on every preceding token in the context window. The model has no mechanism to "go back."

This creates Hallucination Inertia: once the model generates a factually or structurally wrong token, every subsequent token is conditioned on that error. The model's own output becomes evidence for the wrong conclusion. The probability of self-correction within a single generation pass approaches zero as the error propagates through the sequence.

The only way to break inertia is to break the generation pass — stop, evaluate the output externally with a deterministic check, and restart with the error made explicit in the new context. This is the correct architecture for a probabilistic system.

Hallucination Inertia is not a model quality problem — it is a topology problem. Linear chains have no structural mechanism to interrupt and correct a propagating error.

This connects directly to the broader argument in The End of Determinism: when your system's core component is probabilistic, every surrounding component must handle stochastic failure as a first-class concern.

The Architecture of the Probabilistic State Machine

A PSM has three structural components. Conflating them is the most common architectural mistake in production agentic systems.

The Generator is the LLM call. It attempts the task — produce a SQL query, generate a JSON payload, classify an intent. We do not ask it to be perfect. We ask it to be useful on most attempts, given good context.

The Validator is a deterministic function. It evaluates the Generator's output against a formal specification: a JSON schema, a regex pattern, an AST parser, a unit test suite. It emits a binary signal: PASS or FAIL. The Validator must never be another LLM call — using an LLM to validate LLM output reintroduces probabilistic failure at the one point where you need certainty.

The Transition Logic reads the Validator's signal and routes. On PASS, forward to the downstream node. On FAIL, inject the structured error back into the Generator's context and retry. When retries exceed a threshold, route to human escalation — the circuit breaker.

Implementation: State as Schema

The state object is where most implementations go wrong. Engineers default to passing raw message history as state — a flat list of strings with no structured surface for error information, no counter for the circuit breaker, and no separation between immutable goal and mutable scratchpad.

The correct approach uses Pydantic to define state as a typed schema:

from pydantic import BaseModel, Field
from typing import List, Optional
from enum import Enum

class AgentStatus(str, Enum):
    GENERATING = "generating"
    VALIDATING = "validating"
    ESCALATING = "escalating"
    COMPLETE = "complete"

class AgentState(BaseModel):
    # The Goal — set once at entry, never mutated
    user_query: str
    task_context: dict = Field(default_factory=dict)

    # The Scratchpad — append-only generation history
    messages: List[dict] = Field(default_factory=list)
    current_output: Optional[str] = None

    # The Circuit Breaker — mutation is the Validator's job
    retry_count: int = 0
    max_retries: int = 3
    last_error: Optional[str] = None
    error_history: List[str] = Field(default_factory=list)

    # The Status — drives routing logic
    status: AgentStatus = AgentStatus.GENERATING

    def record_error(self, error: str) -> "AgentState":
        """Immutable-style update: returns new state with error recorded."""
        return self.model_copy(update={
            "retry_count": self.retry_count + 1,
            "last_error": error,
            "error_history": self.error_history + [error],
            "status": AgentStatus.ESCALATING
            if self.retry_count + 1 >= self.max_retries
            else AgentStatus.GENERATING,
        })

Three design decisions matter. First, user_query and task_context are immutable by convention — the goal does not change regardless of retries. Second, error_history accumulates all prior errors; when injected into the Generator's context on retry, the model can see the pattern of its failures. Third, record_error encodes the circuit breaker directly — if retry_count + 1 >= max_retries, the status becomes ESCALATING, not GENERATING.

One critical implementation detail: make your error messages model-readable, not human-readable. "JSON schema violation at path 'parameters.where_clause': value is required but missing" gives the model a surgical target. Vague messages like "validation failed" produce vague corrections. In practice, precise error strings are one of the cheapest ways to reduce repeat failures on structured-output tasks because they tell the next attempt exactly what must change.

The Circuit Breaker: Knowing When to Stop

Every PSM needs a circuit breaker — a hard limit on retries that triggers deterministic escalation. Without it, a confused model loops indefinitely, burning tokens on a task it will never complete.

The pattern has three states, borrowed from electrical engineering. Closed: normal operation — Generator runs, Validator checks, failures loop back. Open: triggered when retry_count >= max_retries — the circuit routes to human escalation (Slack notification, support ticket, HITL review). The task is handed off, not abandoned. Half-Open: in long-running systems, a single probe attempt after a cooldown period tests whether the failure condition has resolved.

The circuit breaker is not a failure mode — it is a reliability feature. A PSM that escalates to a human after three structured failures is more reliable than a chain that silently returns a hallucinated result after zero checks.

For structured output (JSON, SQL, code), retries often recover failures when the error is precise and the task is within the model's capability boundary. Beyond a small retry budget, repeated failure usually means the request is malformed, the context is insufficient, or the model cannot do the task reliably. The Iron Triangle of Inference applies: more retries improve reliability but increase latency and cost.

From Pattern to Production

The PSM changes the fundamental contract with users. A linear chain implicitly promises: "We will give you an answer." A PSM explicitly promises: "We will give you a valid answer, or we will tell you why we could not."

Structured output tasks (JSON, SQL, function-call formatting) deliver the most immediate value because schema validation is a solved problem and the retry loop gives the system a way to recover from malformed outputs. Multi-step reasoning benefits because the Validator can run unit tests or consistency checks between steps, turning each node into a checkpoint. Tool-calling agents require PSMs as a safety layer — checking tool parameters against schemas before execution prevents the most common failure class: calling real APIs with hallucinated parameters (see Agentic Contract IDL). Human-in-the-loop workflows use the escalation path as a designed feature, routing structured explanations of failures to human reviewers rather than raw model output.

The question worth sitting with: every production system you build on LLMs will need a theory of failure. The PSM gives you one. The linear chain gives you hope. At 3 a.m. when the pipeline is down, which one do you want backing your SLA?

Related Reading

• Durable Execution: Why Python while Loops Are Not Production Ready — State machines as durable execution patterns
• The State Machine Is the Most Important Pattern in Agentic AI — Applied state machine patterns for agentic systems