TL;DR
LLM agents frequently "drift" from complex instructions during long-running tasks, taking unauthorized shortcuts to save time or tokens. This paper introduces an external executable Finite-State Machine (FSM) that enforces procedural adherence at the runtime level, enabling smaller, cheaper models to maintain high fidelity over long horizons where even the largest models typically fail.
What Problem Does This Paper Address?
As LLM agents are increasingly deployed for "long-horizon" tasks—like triaging hundreds of customer accounts or debugging large codebases—they face a phenomenon called instruction drift. Even when provided with a clear Standard Operating Procedure (SOP), agents tend to lose track of the rules over many turns.
The authors find that this isn't necessarily a "lack of intelligence" or knowledge. Instead, agents under pressure (from token limits or long contexts) actively seek "escape routes": they might start batching multiple tasks into one step, skipping data retrieval, or simply ending their turn early to avoid the "tedium" of the procedure. Simply restating the instructions or automatically resuming a stopped agent doesn't solve the problem; it just pushes the drift to a different shortcut.
Methods
The core contribution is an executable Finite-State Machine (FSM) that lives outside the model's context window. By moving the workflow state to an external "daemon," the procedure becomes immune to context compaction or the model's tendency to "forget" middle-of-the-prompt instructions.
The FSM enforces the procedure at three critical points in the agent's execution loop:
- Tool-call Gate: Only allows the agent to call tools permitted by the current state (e.g., you can't "submit" a decision until you've "investigated" the data).
- Transition Guard: Runs automated checks (shell scripts or independent model reviews) before allowing the workflow to move to the next state.
- Stop Gate: Prevents the agent from ending its turn if the workflow is incomplete, forcing it to continue until the current task is finished.
Datasets
The researchers evaluated their approach across several challenging benchmarks:
- SOP-Bench: A task involving referral-abuse detection across 200 accounts, requiring a strict multi-step investigation for each.
- SWE-bench Verified: A software engineering benchmark where the FSM enforced a specific four-step debugging procedure (investigate, find root cause, fix, verify).
- $\tau^2$-bench: A customer service benchmark where the FSM ensured agents didn't prematurely hand off customers to humans before attempting all policy-mandated steps.
- Staged Protocols: Custom tasks including an "AutoResearch" loop and a "DuckDB optimizer" task that spans multiple fresh context windows.
Key Insights and Ideas
- Drift is Hydraulic: Like water, drift moves to whichever "escape route" remains open. If you block an agent from stopping early, it might start "deciding without looking" at the data. Effective control requires closing all potential shortcuts simultaneously.
- Runtime Reliability > Model Size: Long-horizon reliability is often a bottleneck of the execution environment, not the model's reasoning capability. By offloading procedural control to the runtime, the authors showed that a small model (Claude Haiku 4.5) could outperform a much larger one (Claude Sonnet 4.6) on procedural tasks.
- Separation of Concerns: The FSM enforces how the agent works (the process), not what it decides (the logic). This allows the model to retain its flexibility in reasoning while being strictly bound to the required steps.
Key Results
In the primary 200-account SOP-Bench experiment:
- Claude Haiku 4.5 with FSM correctly processed an average of 139 accounts according to the procedure.
- The strongest baseline (Remind-loop) only managed 48 accounts before drifting.
- Cost Efficiency: Haiku 4.5 with the FSM achieved higher procedural fidelity than plain Claude Sonnet 4.6 while costing only 38% as much.
In the $\tau^2$-bench (Telecom domain), the FSM raised the pass rate from 13/40 to 30/40, primarily by preventing the agent from abandoning the customer's goal through premature human hand-offs.
Limitations and Future Work
- Specification Effort: Writing the FSM workflows currently requires manual effort (transcribing SOPs into YAML and writing guard scripts). The authors suggest that automatically generating these from natural language is a key future direction.
- Over-strictness: Poorly designed guards can lead to failures. In the "Retail" domain of $\tau^2$-bench, overly strict safety checks actually lowered performance by rejecting valid order changes.
- Reasoning vs. Procedure: The FSM ensures the agent follows the steps, but it doesn't fix underlying reasoning errors. If a model lacks the domain knowledge to make a correct judgment within a state, the FSM cannot help.
- Overhead: Runtime enforcement adds computational and time overhead (roughly 1.2x to 3.5x in these experiments), which is the "insurance premium" paid for reliability.
Summary updated