Workflow State Machine Design for Multi-Step Agents
Explicit state machines make multi-step agents reliable by enforcing control flow at runtime.

How reliable a multi-step agent is depends on where control flow lives. Workflow state machine design puts the LLM inside an explicit runtime rather than letting prompts or chain-of-thought govern the run. The central design principle is to make states, transitions, and failure paths enforceable, so the system can explain what happened and recover at the failed layer.
Why implicit control flow breaks multi-step agents in predictable ways
The same tool runs twice because nothing marked its previous call as complete. A retry replays the whole workflow because the system cannot identify the failed step. Human approval disappears because a sentence in a prompt stands in for an actual approval event. These failures look different at the output, but they share a structural cause. The workflow has a lifecycle without a runtime representation that controls it.
Once an agent spans more than one model call, previous actions constrain what may happen next. If those constraints exist only in prompt history or tool output, the model must reconstruct them while deciding what to do. Zhang et al.'s task-state study looks at how showing task state as text in the transcript can be unreliable. The authors cite prior work finding that compliance decays as instructions accumulate. A sentence such as “step 3 completed” is therefore not equivalent to a recorded completion that the runtime enforces.
A wrong tool call or invalid output may occur at a later step than the decision that made it possible. AgentDebugX identifies this gap between the step where an error appears and the step that caused it as a central debugging problem. The architectural response must therefore do more than improve the final answer. It must expose the decisions and dependencies that led there.
What an explicit state machine actually gives the agent runtime
A state is the current named phase of the workflow, such as intake, plan, or act. It identifies the obligations that apply now, rather than merely describing what the agent has said. An event is something that happened, such as TOOL_SUCCEEDED, TIMEOUT, or APPROVED. A transition is a legal move from one state to another, defined in advance. Together, these concepts separate a proposal about what should happen from evidence that something has happened.
A guard is the predicate that decides whether a transition is allowed. It evaluates context, which is the data carried with the run, including request ID, tool output, retry count, or approval status. The model can suggest the next transition, but the runtime decides whether that move is legal. If approve_payment is illegal from planning, the runtime rejects it regardless of the model's output. The LLM remains a decision-maker without becoming the authority over every execution rule.
Zhang et al. test four levels of state coupling, namely raw transcript, text checklist, directive gate, and enforcement gate. They find enforcement, where the runtime refuses state-violating actions, to be the most reliable level. As models become more capable, they do better at the lower levels, while performance with enforcement stays flat. Its benefit therefore does not depend on the model becoming more obedient.
A separate distinction matters when diagnosing the resulting system. Yue et al. distinguish an ACG template, the reusable specification, from the realized graph deployed for a run and the execution trace of its behavior. An error visible in the trace may originate in either the template or the realized graph. Keeping these objects distinct prevents runtime evidence from being mistaken for a complete explanation of the failure.
How to define states that carve the workflow at its real joints

States should mark phases where the obligations, the valid next actions, and the recovery logic change. They should not turn every action into a separate workflow phase. The useful boundary is a change in what the runtime must check or how it must respond to failure. A seven-state lifecycle provides a starting sketch, with states named intake, plan, act, validate, await_human, done, and failed. Engineers should prune or extend that sketch according to where recovery paths genuinely diverge.
The intake state normalizes input, validates its schema, and attaches metadata. Malformed input belongs on a rejection path here, before it propagates. The plan state then decides the next step, tool, or branch. This state needs a planning-loop cap and should exit quickly. The act state carries the tool, worker, or external API call, together with its timeout, idempotency key, and retry count.
The validate state checks the output against schema or business rules and marks a failure if the structure is invalid. Act and validate deserve separate treatment because that obligation differs from checking whether a tool call completed. The await_human state pauses for approval or clarification and needs a real transition event, an SLA timer, and an escalation owner. The done state is terminal and has no outgoing transitions. By contrast, failed may be terminal or lead to a controlled retry path, but it must record a structured reason, emit a trace, and clean up.
The design test is whether the failure path and validation step can be named before the tools. If they cannot, the workflow is not yet understood well enough to encode. Alderete et al. show that explicit typed state machines, or context graphs, account for the large majority of accuracy gain across trials within a fixed hypothesis space. Their separate monitoring layer handles cases where that space needs to grow.
Writing guards that enforce business rules without over-constraining the agent
Guards turn workflow rules into conditions the runtime can enforce. Guards make the system more reliable because a required condition still holds when the model proposes something else. A guard can block tool arguments that fail validation before they reach the API through PreToolUse hooks. It can also refuse a second call to a non-idempotent tool when context records that the first succeeded.
Task-scoped tool access applies the same principle to what the executor can attempt. The executor should receive only the tools needed for its current step. This keeps the blast radius small when a step goes wrong. Del Rosario et al. argue that separating planning from execution also provides resilience to indirect prompt injection through control-flow integrity, because an executor restricted to a pre-approved plan cannot be rerouted by an instruction in a retrieved document. Execution authority belongs in the runtime.
That authority is useful only when the guard's judgment is sound. Zhang et al. find that enforcement pays when failures are state-decidable and frequent, but hurts when the gate misclassifies a valid action as illegal. Guards should cover conditions the runtime can determine from recorded facts. When intent is unclear or inputs are new, the decision should go to model judgment or human escalation.
Step-level status tracking as the foundation for targeted failure recovery
A named workflow state does not, by itself, record the outcome of every step. Structured step-level status gives the runtime the evidence it needs to retry a failed step without replaying work that is done. Each record should carry the step ID, status, whether the exit condition was met, tool call and result payload, retry count, and transition event that fired. The status can be done, blocked, cancelled, or failed. These fields make completion and failure available to the runtime without requiring it to reinterpret prose logs.
Zhang et al. find that an unverified ledger the agent writes itself outperforms an accurate checklist shown to it. The distinction is between a prospective running record of the agent's work and a retrospective display it must read. This result helps explain why merely exposing state is not the same as making state part of the decision process. It does not make an agent-written ledger equivalent to runtime enforcement.
The resulting records make failure attribution more precise. When act fails again and again with the same tool arguments, the cause may be tool-schema drift or a bad API response. Repeated validate failures instead point toward prompt ambiguity or a schema mismatch. The OpenTelemetry GenAI export path gives step records a portable, typed representation that trace analysis tooling can consume without re-parsing agent-specific log formats.
Designing failure-recovery paths that target the layer that broke
A generic retry from failed is still a workflow-level response to a potentially local problem. Targeted recovery uses the failed state's typed reason payload and the step records to identify the responsible layer and route recovery accordingly. This is where state definitions, guards, and status tracking become one design. The state names the phase, the records supply evidence, and the guarded path constrains the response.
At the prompt layer, repeated validate failures with structurally valid tool calls indicate that the model is producing output the schema rejects. The appropriate fix is prompt revision. At the tool or schema layer, tool-schema drift may be the cause when act fails with argument-format errors or unexpected API error codes. Recovery there means updating the tool definition or the call arguments. The shared symptom of failure does not justify treating these two cases as interchangeable.
At the workflow layer, loop detection compares steps taken with the minimum needed and flags repeated identical actions. When the step or loop count exceeds its threshold, the response is a transition guard or planning-loop cap. This addresses the path through the workflow rather than changing a tool that may be behaving correctly. If the runtime cannot attribute the failure to a specific layer, or intent remains underspecified, the path should lead to await_human. Silent retries would substitute repetition for a missing diagnosis.
Del Rosario et al. describe dynamic re-planning loops where the planner changes the work still to be done after a step fails. That pattern requires the executor to be isolated from the original plan's assumptions and to receive a clean revised artifact.
Before promotion, a prompt, tool-schema, or guard change should be validated against historical traces of the failure. AgentDebugX organizes this discipline as a closed loop of Detect, Attribute, Recover, and Rerun. A structured failed state can go straight into that diagnosis pass. The broken run's trace then becomes input for generating and validating a fix.
Where static topology ends and in-execution graph editing begins
These principles concern static topology, where the graph is authored before the episode begins. Yue et al. distinguish graph determination time, including offline, pre-execution, and in-execution, from graph plasticity mode, including none, select, generate, and edit. Most production systems today are in the pre-execution or select range, while researchers are still exploring full in-execution editing. That frontier changes when the graph can change, but not the need to understand what its execution means.
A dynamic topology still needs step-level status records, typed failure payloads, and guard logic that can be verified. Without those foundations, editing a graph at runtime lacks the evidence and constraints needed to make the change safely. A well-instrumented static topology is therefore the right starting point for most production agents.
Sources
- Separable Pathways for Causal Reasoning: How Architectural Scaffolding Enables Hypothesis-Space Restructuring in LLM Agents
- How Strongly Should Task State Influence an LLM Agent?
- Architecting Resilient LLM Agents: A Guide to Secure Plan-then-Execute Implementations
- From Static Templates to Dynamic Runtime Graphs: A Survey of Workflow Optimization for LLM Agents
- AgentDebugX: An Open-Source Toolkit for Failure Observability, Attribution, and Recovery in LLM Agents


