State Machine Verification for Multi-Step AI Pipelines

A common failure mode in production AI systems is the unconstrained agent loop. An LLM is given a broad system prompt, ten API tools, and a while (!done) cycle. The model is expected to autonomously plan, execute, and verify its own work. In prototypes, this feels like magic. In production, it creates silent deadlocks and data corruption.

When autonomous agents fail across multi-step jobs, they rarely throw clean stack traces. Instead, they exhibit semantic drift: executing database writes before verifying schema contracts, looping indefinitely when a third-party API returns a 429 status, or hallucinating intermediate values to force completion. Trying to fix this with prompt engineering — pleading with the model to 'think step by step before invoking Tool B' — treats an architectural defect as a phrasing issue.

The fix is architectural: model multi-step agent pipelines as formal Finite State Machines (FSMs). The non-deterministic LLM is never given control of the execution loop. Instead, the model acts as an isolated worker within bounded states, while a deterministic application engine validates transition invariants before advancing state.

The Seven Discrete Pipeline States

In classical systems engineering, state machines define discrete nodes where all transitions depend on explicit, verifiable inputs. Applying this to agentic pipelines establishes seven unambiguous boundaries:

• S0 — IDLE: The dormant entry state. Asserts that incoming job payloads and raw document buffers are non-empty and well-formed before allocating context memory.
• S1 — EXTRACT (LLM Worker): The probabilistic extraction step. An LLM agent parses raw text into typed entity fields. Tool access is strictly read-only; the agent cannot execute mutations or trigger external side effects.
• S2 — VALIDATE (Deterministic FSM Gate): A zero-LLM contract checker. Validates runtime schemas with strict type guards (e.g., Zod schemas, relational foreign keys, confidence score thresholds).
• S3 — REPAIR (LLM Worker): A targeted recovery state positioned directly above validation. If S2 catches schema violations, the repair agent receives the structured error array to correct specific fields without re-running the entire job.
• S4 — COMMIT (Deterministic Mutation): The downstream write stage. Executes database mutations and queue dispatches only after S2 validates with zero errors.
• DONE (Terminal Success): A classical double-circle terminal state confirming that records are safely persisted and audit trails are closed.
• ESCALATE (Terminal Fallback): The human-in-the-loop circuit breaker. If the repair cycle exceeds the retry budget (e.g., retries >= 3) or encounters fatal invariant breaches, execution halts and routes to an operational queue.

Type-Safe State Machine Implementation

The implementation separates core concerns into four modular files: foundational contracts, the pure invariant evaluator, the runtime state transition engine, and a complete usage script.

export type PipelineState =
  | "IDLE"        // S0: Initial dormant state
  | "EXTRACTING"   // S1: Probabilistic LLM agent extraction
  | "VALIDATING"   // S2: Deterministic invariant validation gate
  | "REPAIRING"    // S3: Bounded recovery retry loop (LLM agent)
  | "COMMITTING"   // S4: Downstream database persistence
  | "COMPLETED"    // Terminal Success State
  | "ESCALATE";    // Terminal Fallback State (Human Ops)

export interface ExtractionPayload {
  documentId: string;
  entities: Array<{ name: string; category: string; confidence: number }>;
  metadata: Record<string, unknown>;
}

export interface PipelineContext {
  jobId: string;
  rawInput: string;
  payload?: ExtractionPayload;
  validationErrors: string[];
  retryCount: number;
  maxRetries: number;
}

export type TransitionResult =
  | { success: true; nextState: PipelineState; context: PipelineContext }
  | { success: false; error: string; fallbackState: PipelineState };

End-to-End Walkthrough: Handling Drift and Automated Recovery

Consider what happens at runtime when an LLM agent produces a malformed payload — such as omitting a required foreign key or outputting an unmapped category enum. In an unconstrained loop, that invalid data cascades downstream until a database write fails abruptly.

Under state machine verification, the execution flow is fully governed:

• Step 1 — Extraction: The agent finishes S1 (EXTRACT) and requests a transition to S2 (VALIDATE).
• Step 2 — Invariant Check: The evaluateTransition function executes deterministic schema rules and registers any validation errors in the pipeline context.
• Step 3 — Rejection & Branching: If validation errors exist, the engine rejects transition to S4 (COMMIT) and transitions to S3 (REPAIR).
• Step 4 — Targeted Repair: The repair agent receives the structured error array to correct the malformed fields and returns the updated payload to S2.
• Step 5 — Resolution or Escalation: If the repaired payload passes validation, state advances to S4 (COMMIT) and finishes at DONE. If it fails repeatedly, the retry counter trips the circuit breaker and parks the job in ESCALATE.

Deterministic Replay and Audit Ledgers

When an agent operates in an unconstrained loop, diagnosing why it failed at step 7 is virtually impossible because transient memory is lost. By enforcing a formal state machine, every transition event — the prompt, the model response, the token count, and the exact state delta — is logged as an immutable record.

This enables deterministic replayability: during integration testing, engineers can seed the state machine with historical contexts, mock specific intermediate states, and unit test edge-case transitions without making costly end-to-end model calls.

Summary

AI models belong in the evaluation and extraction tier, not the orchestration tier. By wrapping LLMs in verified state machines with strict transition invariants, software teams eliminate non-deterministic loops, enforce data contracts, and build agentic systems capable of surviving real-world enterprise workloads.