Designing AI Agent State Machines for Reliable Multi-Step Workflows

The demo agent works beautifully right up until the workflow has to wait. Wait for a tool to finish. Wait for a webhook. Wait for a human approval. Wait for a retry window to expire. Then the “simple agent loop” becomes a pile of flags in Redis, a prompt that says “please remember where you were,” and a support ticket asking why the customer got two refund emails.

Multi-step AI agents fail less often because the model is bad, and more often because the execution model is vague. The agent has memory, but no durable state. It has tools, but no transaction boundaries. It has retries, but no defined point from which retrying is safe.

An explicit state machine fixes this by making the workflow’s lifecycle a first-class artifact: current state, allowed transitions, pending actions, failure policy, compensation plan, and audit trail. The model still does the flexible reasoning, but the workflow itself stops being a vibe.

TL;DR: Treat a multi-step AI agent as a durable state machine, not as a chatbot with tools. Define explicit states for planning, execution, verification, approval, failure, and compensation. Persist transitions before side effects. Make events facts, not intentions. Put retries, timeouts, and escalations in code, not prompts. Checkpoint structured context instead of replaying the whole conversation. Test the machine like a distributed system.

📋 Table of Contents

1. The Agent Loop Is a Runtime, Not a Workflow
2. Design States Around Decision Points, Not API Calls
3. Events Should Be Facts, Not Intentions
4. Persist the Transition Before You Execute the Side Effect
5. Put Retries, Timeouts, and Escalation in the Machine
6. Verification States Are Where Reliability Actually Lives
7. Human Approval Needs Its Own Suspended State
8. Compensation Is a Workflow, Not a Function
9. Checkpoint Context, Do Not Replay the Whole Conversation
10. Test the State Machine Like a Distributed System
Choosing the Right Agent Workflow Shape

1. The Agent Loop Is a Runtime, Not a Workflow

Scenario: Your agent needs to process a customer escalation: classify the issue, fetch account data, propose a refund, get supervisor approval, execute the refund, and notify the customer. You implement it as a single ReAct-style loop with tools. It works until the approval step takes two hours, the process restarts, and the agent forgets that the refund was already proposed.

Why it matters: A basic agent loop is excellent for interactive problem solving, but it is not a durable workflow engine. The loop’s state lives in the model context, local variables, or temporary memory. If the process restarts, the state disappears. If the model hallucinates progress, there is no authoritative record to contradict it.

Solution: Separate the agent runtime from the workflow state machine.

The runtime can still be an LLM agent that proposes actions. But the workflow should have a typed state object and a transition function:

type WorkflowStatus =
  | "collecting_requirements"
  | "planning"
  | "awaiting_approval"
  | "executing_step"
  | "verifying_step"
  | "compensating"
  | "failed"
  | "completed";

interface WorkflowExecution {
  id: string;
  status: WorkflowStatus;
  version: number;
  input: unknown;
  plan?: Step[];
  currentStepId?: string;
  attempt: number;
  history: TransitionRecord[];
  result?: unknown;
  failure?: FailureInfo;
}

The LLM can influence the workflow by producing proposals: a plan, a tool call, a summary, a verification judgment. But the state machine decides whether those proposals are legal.

function transition(
  execution: WorkflowExecution,
  event: WorkflowEvent
): TransitionResult {
  switch (execution.status) {
    case "collecting_requirements":
      if (event.type === "requirements_collected") {
        return {
          nextState: { ...execution, status: "planning" },
          effects: [{ kind: "generate_plan", input: event.input }],
        };
      }
      break;

    case "planning":
      if (event.type === "plan_created") {
        return {
          nextState: {
            ...execution,
            status: "executing_step",
            plan: event.steps,
            currentStepId: event.steps[0]?.id,
            attempt: 0,
          },
          effects: [{ kind: "execute_step", stepId: event.steps[0]?.id }],
        };
      }
      break;

    // other transitions...
  }

  return { nextState: execution, effects: [] };
}

Why this works: The workflow becomes inspectable. You can answer questions like “What state is execution wf_123 in?” without reading a transcript. You can resume, retry, audit, and test it.

💡 Practical note: If your agent’s only source of truth is the conversation history, you do not have a workflow. You have a transcript with ambitions.

2. Design States Around Decision Points, Not API Calls

A common mistake is naming states after low-level actions: calling_search_api, waiting_for_llm_response, saving_to_database. Those states are brittle. They couple the workflow to implementation details and explode in number as soon as you add more tools.

Better states model the decision points and lifecycle phases of the work.

For a typical multi-step agent, a useful baseline looks like this:

collecting_requirements
  → planning
  → awaiting_approval
  → executing_step
  → verifying_step
  → executing_next_step | compensating | completed

Each state answers a different question:

State	Question it answers
`collecting_requirements`	Do we have enough input to proceed?
`planning`	What steps should happen, and in what order?
`awaiting_approval`	Does a human need to authorize this?
`executing_step`	Is a side-effecting action running?
`verifying_step`	Did the step produce an acceptable result?
`compensating`	What needs to be undone?
`failed`	Is the workflow terminally broken?
`completed`	Is the outcome final?

These states are deliberately broad. They do not say “call Stripe” or “query Postgres.” They say, “We are currently executing a step,” and the step metadata says which tool is involved.

interface Step {
  id: string;
  name: string;
  kind: "read_only" | "mutating" | "human_approval" | "notification";
  tool?: string;
  input: unknown;
  requiresApproval?: boolean;
  retryPolicy?: RetryPolicy;
  compensation?: CompensationAction;
}

Why this works: The state machine remains stable even when the agent’s tools change. You can swap a search tool, add a new verification model, or replace an email provider without rewriting the workflow graph.

⚠️ Gotcha: Avoid creating a separate top-level state for every tool. Use executing_step plus structured step metadata. If a step itself has complex substates, model that step as a nested state machine or sub-workflow.

3. Events Should Be Facts, Not Intentions

State machines become unreliable when events are ambiguous. user_wants_refund is an intention. refund_requested is closer to a fact. refund_executed is a fact. refund_execution_failed is also a fact.

AI agents are full of intentions: the model wants to call a tool, wants to ask a question, wants to finalize an answer. The state machine should only transition on events that represent something that happened or was decisively validated.

A practical event model looks like this:

type WorkflowEvent =
  | { type: "requirements_collected"; input: WorkflowInput }
  | { type: "plan_created"; steps: Step[] }
  | { type: "plan_rejected"; issues: string[] }
  | { type: "approval_requested"; stepId: string }
  | { type: "approval_granted"; stepId: string; approverId: string }
  | { type: "approval_denied"; stepId: string; reason: string }
  | { type: "step_started"; stepId: string; attempt: number }
  | { type: "step_succeeded"; stepId: string; output: unknown }
  | { type: "step_failed"; stepId: string; error: AgentError }
  | { type: "verification_passed"; stepId: string }
  | { type: "verification_failed"; stepId: string; issues: string[] }
  | { type: "timeout"; stepId?: string }
  | { type: "compensation_completed"; stepId: string }
  | { type: "compensation_failed"; stepId: string; error: AgentError };

The transition function should validate that the event matches the current state. A step_succeeded event for a workflow that is already completed should be ignored or logged, not allowed to resurrect the execution.

function canApplyEvent(
  execution: WorkflowExecution,
  event: WorkflowEvent
): boolean {
  if (
    event.type === "step_succeeded" &&
    execution.currentStepId !== event.stepId
  ) {
    return false;
  }

  if (
    execution.status === "completed" ||
    execution.status === "failed"
  ) {
    return false;
  }

  return true;
}

Why this works: The state machine becomes resilient to duplicate events, late callbacks, and confused model output. It also gives you a clean place to enforce authorization: an approval_granted event must carry an approver identity and must be validated against your permission system.

🔍 Why this matters: In agent systems, the model can suggest events, but it should not be allowed to forge them. Tool results, human actions, timers, and external systems are the trusted producers of state-changing events.

4. Persist the Transition Before You Execute the Side Effect

Here is the failure that hurts most: the agent sends an email, charges a payment, or creates a ticket, then crashes before recording that the action happened. On restart, it may perform the action again. Or worse, it may assume the action never happened and take a contradictory path.

The fix is to treat state transitions and side effects as a durability problem.

A useful pattern is:

Persist the intended transition or step record.
Execute the side effect with an idempotency key.
Persist the result.
Emit the event that moves the state machine forward.

Conceptually:

async function executeStep(
  execution: WorkflowExecution,
  step: Step
): Promise<void> {
  const idempotencyKey = `${execution.id}:${step.id}:${execution.attempt}`;

  const existing = await store.getStepResult(execution.id, step.id);

  if (existing?.status === "succeeded") {
    await eventBus.emit({
      type: "step_succeeded",
      stepId: step.id,
      output: existing.output,
    });
    return;
  }

  await store.markStepRunning(execution.id, step.id, {
    attempt: execution.attempt,
    idempotencyKey,
  });

  try {
    const output = await runTool(step, { idempotencyKey });

    await store.markStepSucceeded(execution.id, step.id, output);

    await eventBus.emit({
      type: "step_succeeded",
      stepId: step.id,
      output,
    });
  } catch (error) {
    await store.markStepFailed(execution.id, step.id, error);

    await eventBus.emit({
      type: "step_failed",
      stepId: step.id,
      error: classifyError(error),
    });
  }
}

The critical detail is the idempotency key. If the executor crashes after the tool succeeds but before the result is recorded, a retry with the same key should return the previous result instead of duplicating the side effect.

For external APIs that support idempotency keys, pass them through. For APIs that do not, you need a local deduplication record or a preflight check: “Has this step already produced an effect for this execution and attempt?”

Why this works: The workflow can survive restarts, duplicate events, and partial failures. Recovery becomes a matter of reading durable state and resuming from the last trustworthy transition.

🚨 Production warning: If a step mutates the real world and you cannot make it idempotent, mark it clearly and treat retries as dangerous. Sometimes the correct transition is not “retry,” but “escalate to a human.”

5. Put Retries, Timeouts, and Escalation in the Machine

Prompts are terrible places for retry logic. You can write, “Retry up to three times with exponential backoff,” and the model may follow that instruction sometimes. But “sometimes” is not a production retry policy.

Retry behavior belongs in the state machine or execution runtime.

Define retry policies per step:

interface RetryPolicy {
  maxAttempts: number;
  initialDelayMs: number;
  maxDelayMs: number;
  backoffMultiplier: number;
  retryOn: Array<"transient" | "rate_limited" | "timeout">;
  onExhausted: "fail" | "compensate" | "escalate_human";
}

Then encode the transition:

function handleStepFailed(
  execution: WorkflowExecution,
  event: Extract<WorkflowEvent, { type: "step_failed" }>,
  step: Step
): TransitionResult {
  const policy = step.retryPolicy ?? defaultRetryPolicy;

  const shouldRetry =
    execution.attempt < policy.maxAttempts &&
    policy.retryOn.includes(event.error.category);

  if (shouldRetry) {
    const delay = calculateBackoff(execution.attempt, policy);

    return {
      nextState: {
        ...execution,
        status: "executing_step",
        attempt: execution.attempt + 1,
      },
      effects: [
        {
          kind: "schedule_event",
          delayMs: delay,
          event: { type: "step_started", stepId: step.id, attempt: execution.attempt + 1 },
        },
      ],
    };
  }

  if (policy.onExhausted === "compensate") {
    return startCompensation(execution, event);
  }

  if (policy.onExhausted === "escalate_human") {
    return {
      nextState: {
        ...execution,
        status: "awaiting_approval",
        failure: {
          stepId: step.id,
          reason: event.error.message,
          needsHumanDecision: true,
        },
      },
      effects: [{ kind: "notify_human", executionId: execution.id }],
    };
  }

  return {
    nextState: {
      ...execution,
      status: "failed",
      failure: { stepId: step.id, reason: event.error.message },
    },
    effects: [{ kind: "emit_metric", name: "workflow_failed" }],
  };
}

Timeouts need the same treatment. Every state that can wait should have an expiration path:

executing_step + timeout → step_failed(category="timeout")
awaiting_approval + timeout → reminder, escalate, or deny
verifying_step + timeout → fail closed or route to human review

Why this works: The workflow’s temporal behavior becomes deterministic. You can reason about maximum duration, retry cost, and escalation paths without asking the model to be disciplined.

💡 Practical note: Distinguish transient failures from permanent failures early. A 429 or network timeout may be retryable. An invalid schema, missing permission, or malformed business input usually is not. Blind retries turn permanent errors into expensive loops.

6. Verification States Are Where Reliability Actually Lives

A lot of agent workflows make the same architectural mistake: they treat tool output as final output. The tool returns something, the model sees it, and the workflow moves on. But multi-step workflows usually need a verification phase.

Verification can be lightweight or strict depending on risk:

Schema validation for structured output
Business-rule checks
Policy checks
Deterministic assertions
A second model acting as a critic
Human review for high-risk changes

Model this explicitly:

case "executing_step":
  if (event.type === "step_succeeded") {
    return {
      nextState: {
        ...execution,
        status: "verifying_step",
      },
      effects: [
        {
          kind: "verify_step",
          stepId: event.stepId,
          output: event.output,
        },
      ],
    };
  }
  break;

case "verifying_step":
  if (event.type === "verification_passed") {
    return advanceToNextStep(execution);
  }

  if (event.type === "verification_failed") {
    return handleVerificationFailure(execution, event);
  }
  break;

The verification step should produce structured feedback, not just a boolean:

interface VerificationResult {
  passed: boolean;
  issues: Array<{
    code: string;
    message: string;
    severity: "warning" | "error";
  }>;
  suggestedAction?: "retry_step" | "replan" | "escalate_human" | "accept_with_warning";
}

This matters because LLM-generated actions often fail in subtle ways. The tool call may succeed technically, but the result may be semantically wrong. A refund might have the right currency but the wrong customer. A generated support response might be polite but violate policy. A database update might succeed but miss a required audit field.

Why this works: Verification gives the state machine a place to reject progress without crashing the whole workflow. The agent can replan, retry, or escalate based on structured failure reasons.

🧠 The important part: Do not verify everything with the same intensity. Read-only steps can use cheap validation. Mutating steps, financial actions, external communications, and privileged operations deserve stronger checks.

7. Human Approval Needs Its Own Suspended State

If your agent sometimes needs a human, “sometimes” must be represented as a state. Not a comment in the code. Not a note in the prompt. A state.

interface AwaitingApprovalState {
  status: "awaiting_approval";
  stepId: string;
  requestedAt: string;
  expiresAt: string;
  approverRoles: string[];
  decision?: {
    approverId: string;
    outcome: "approved" | "denied";
    reason?: string;
    decidedAt: string;
  };
}

The transition into this state should persist enough information for a human to decide safely:

function requestApproval(
  execution: WorkflowExecution,
  step: Step
): TransitionResult {
  return {
    nextState: {
      ...execution,
      status: "awaiting_approval",
      currentStepId: step.id,
    },
    effects: [
      {
        kind: "create_approval_request",
        executionId: execution.id,
        stepId: step.id,
        summary: describeStepForHuman(step),
        riskLevel: assessRisk(step),
        expiresAt: addHours(new Date(), 24).toISOString(),
      },
    ],
  };
}

Then handle the possible outcomes:

approval_granted → execute_step
approval_denied → compensate, fail, or replan depending on policy
approval_timeout → remind, escalate, or deny by default

This is also where authorization matters. The state machine should not accept an approval event unless it can verify the approver’s identity and permissions. If the approval came from a UI, the backend should enforce permissions before emitting the event. If it came from Slack or email, the integration still needs to authenticate the user and check their role.

Why this works: The workflow can pause for minutes, hours, or days without losing consistency. The agent does not need to keep a conversation alive just to wait for a person.

⚠️ Gotcha: Do not let the LLM decide that a human “probably approved” based on chat history. Approval must be an explicit, authenticated event from a trusted system.

8. Compensation Is a Workflow, Not a Function

Multi-step agents often perform actions that cannot be cleanly undone. You can void a payment, cancel a reservation, delete a draft, or send a correction email, but those are new actions with their own failure modes.

This is where saga-style compensation fits naturally.

When a mutating step succeeds, record how to compensate it if a later step fails:

interface CompletedStepRecord {
  executionId: string;
  stepId: string;
  output: unknown;
  compensation?: CompensationAction;
  completedAt: string;
}

interface CompensationAction {
  tool: string;
  input: unknown;
  description: string;
  requiresApproval?: boolean;
}

If a later step fails irrecoverably, the state machine enters compensating and works backward through the completed steps:

function startCompensation(
  execution: WorkflowExecution,
  event: Extract<WorkflowEvent, { type: "step_failed" }>
): TransitionResult {
  const completed = getCompletedStepsWithCompensation(execution);

  if (completed.length === 0) {
    return {
      nextState: {
        ...execution,
        status: "failed",
        failure: { stepId: event.stepId, reason: event.error.message },
      },
      effects: [],
    };
  }

  return {
    nextState: {
      ...execution,
      status: "compensating",
      failure: { stepId: event.stepId, reason: event.error.message },
    },
    effects: [
      {
        kind: "run_compensation",
        executionId: execution.id,
        compensationPlan: completed.reverse(),
      },
    ],
  };
}

Compensation needs its own failure handling. A compensation action can time out, fail validation, or be blocked by an external system. If compensation fails, do not silently mark the workflow as clean. Move to compensation_failed and alert someone.

compensating
  → compensation_completed
  → failed

compensating
  → compensation_failed
  → human_intervention_required

Why this works: You acknowledge that distributed workflows do not have magical rollback. Instead, you make the undo path explicit, observable, and testable.

💡 Practical note: For high-risk operations, compensation plans should be reviewed like code. “Send apology email” may be acceptable. “Delete customer account” probably needs approval, audit logging, and a very careful idempotency strategy.

9. Checkpoint Context, Do Not Replay the Whole Conversation

A naive recovery strategy is to feed the entire conversation history back into the model and ask it to continue. This works for short demos. It becomes expensive, slow, and unreliable for long workflows.

Long-running agents need structured checkpoints.

A checkpoint is not the whole transcript. It is the minimum context required to resume safely:

interface WorkflowCheckpoint {
  executionId: string;
  stateVersion: number;
  status: WorkflowStatus;
  currentStepId?: string;
  input: WorkflowInput;
  plan?: Step[];
  completedSteps: Array<{
    stepId: string;
    outputSummary: unknown;
    artifacts: ArtifactReference[];
  }>;
  openQuestions?: string[];
  constraints: PolicyConstraints;
  updatedAt: string;
}

The model can receive a compact summary generated from the checkpoint:

function buildAgentContext(checkpoint: WorkflowCheckpoint) {
  return {
    objective: checkpoint.input.objective,
    currentState: checkpoint.status,
    currentStep: checkpoint.currentStepId,
    completedWork: checkpoint.completedSteps.map(step => ({
      stepId: step.stepId,
      summary: summarize(step.outputSummary),
    })),
    constraints: checkpoint.constraints,
    nextAllowedActions: getAllowedActions(checkpoint.status),
  };
}

This has several benefits:

Lower token cost
Less drift from irrelevant conversation history
Cleaner separation between durable state and model reasoning
Easier auditing
Better ability to swap models mid-workflow

It also forces you to decide what matters. If a piece of information is required to continue the workflow, it belongs in the checkpoint. If it is only useful for explaining the past, it can stay in logs or transcripts.

Be careful with secrets. Do not store raw API keys, passwords, or sensitive tokens in workflow state. Store references that your runtime can resolve securely.

{
  "type": "secret_reference",
  "provider": "vault",
  "path": "payments/prod/api-key",
  "scope": "read-only"
}

Why this works: The agent can resume after restarts, delays, and handoffs without pretending the entire conversation is the only source of truth.

🔍 Why this matters: If your agent cannot resume without replaying thousands of tokens, you have not built a durable workflow. You have built an expensive memory test.

10. Test the State Machine Like a Distributed System

Prompt evaluation is important, but it is not enough. A multi-step agent has distributed-system problems: duplicate events, partial failures, timeouts, restarts, out-of-order callbacks, and race conditions.

You need at least four layers of testing.

Transition tests

These are deterministic unit tests for the state machine.

test("step_failed schedules retry when error is transient", () => {
  const execution = makeExecution({
    status: "executing_step",
    currentStepId: "step_1",
    attempt: 1,
  });

  const result = transition(execution, {
    type: "step_failed",
    stepId: "step_1",
    error: { category: "transient", message: "timeout" },
  });

  expect(result.nextState.status).toBe("executing_step");
  expect(result.nextState.attempt).toBe(2);
  expect(result.effects).toContainEqual(
    expect.objectContaining({ kind: "schedule_event" })
  );
});

Illegal-state tests

These verify that bad events do not corrupt the workflow.

test("approval_granted is ignored after workflow completed", () => {
  const execution = makeExecution({ status: "completed" });

  const result = transition(execution, {
    type: "approval_granted",
    stepId: "step_1",
    approverId: "user_123",
  });

  expect(result.nextState).toEqual(execution);
  expect(result.effects).toHaveLength(0);
});

Failure simulation tests

Simulate tool failures, slow tools, duplicate callbacks, and restarts.

Given the workflow is executing step 2
When the tool succeeds but the process crashes before recording success
And the executor restarts with the same idempotency key
Then the step result is reused
And no duplicate side effect occurs

Trace and eval tests

For the LLM-dependent parts, use trace-based evaluation:

Did the planner produce a valid plan?
Did the agent choose a tool allowed in the current state?
Did the verifier catch policy violations?
Did the model ask for missing information instead of guessing?

A useful test matrix:

Failure	What to test	Expected behavior
Tool timeout	Inject timeout event	Retry, escalate, or fail according to policy
Duplicate tool result	Send same `step_succeeded` twice	Second event is ignored or deduplicated
Invalid plan	Planner returns malformed steps	Replan with attempt cap or escalate
Human denies approval	Emit `approval_denied`	Stop, compensate, or choose alternate path
Process restart mid-step	Kill executor and resume	Resume from checkpoint safely
Compensation failure	Make compensation tool fail	Enter `compensation_failed` and alert

Why this works: You stop relying on the model to be the only safety mechanism. The workflow becomes testable independently of model nondeterminism.

🧠 The important part: Use LLM evaluation where judgment matters. Use deterministic tests where correctness matters. A reliable agent needs both.

Choosing the Right Agent Workflow Shape

Not every agent needs a full state machine. The right design depends on risk, duration, and side effects.

Pattern	Best for	Strength	Main risk
Free-form agent loop	Interactive assistants, read-only Q&A	Flexibility	Poor durability and auditability
Fixed DAG pipeline	Predictable batch workflows	Simplicity and observability	Limited adaptability
State machine with agent steps	Multi-step workflows with approvals, retries, and side effects	Reliability and control	More design work
Hierarchical state machine	Complex workflows with subtasks	Scales complexity	Can become over-engineered
Human-operated workflow with AI assistance	High-risk or legally sensitive actions	Safety	Slower throughput

My default is:

Use a free-form agent loop when the task is short, mostly read-only, and failure is cheap.
Use a DAG when the steps are known in advance and rarely change.
Use a durable state machine when the agent performs multi-step work that can pause, fail, retry, require approval, or mutate external systems.
Use human-in-the-loop states whenever the cost of a wrong automated action is high.
Avoid rigid state machines for open-ended exploration where the user is actively steering every move and no durable side effects occur.

The most reliable AI agent architectures are not the ones that give the model unlimited control. They are the ones that give the model enough freedom to be useful, while making the workflow’s progress explicit, recoverable, and auditable.

In other words: let the model reason, but make the machine remember.