CS Paper Radar

Keeping LLM Agents on Procedure: Executable Finite-State Control for Long-Horizon Instruction Fidelity

Yutao Sun, Haokun Li, Mingshuai Chen, Guanyan Li, Zhongyi Wang, Shengchao Qin, Jianwei Yin

cs.AI ·submitted 2026-11-07 18:09 UTC · v1

Abstract

Much of the automation handed to language-model agents is procedural: each step needs little intelligence, but a long unattended run must follow a skill or SOP stated once at the start. We show that agents drift from such procedures over long runs, and that restating the instructions or resuming a stopped agent only moves the drift to another shortcut. We study an executable finite-state machine (FSM) that keeps the workflow state outside the model's context and enforces it at three points: tool calls, state transitions and the end of the agent's turn. In a pre-registered experiment on 200-account SOP-Bench batches, Claude Haiku 4.5 with the FSM decided on average 139 accounts correctly and by the procedure, against 48 for the strongest baseline (95% CI of the difference [46, 130]), and kept this rate to the end; across three models, the gain tracked how much the plain agent drifted. Because the runtime, not the model, supplies this long-horizon reliability, the FSM can let small models carry procedural work: Haiku 4.5 with it averaged more such decisions than plain Claude Sonnet 4.6 at 38% of the cost. Analyses on SWE-bench Verified, $τ^2$-bench, and staged and cross-context workflows further suggest that reliable long-horizon automation can come from stronger execution control, not only stronger models.

Closest papers

Nearest neighbours by meaning across the whole index.

How Strongly Should Task State Influence an LLM Agent?

cs.AI cs.CLcs.LG ·2026-09-22 ·Chenyu Zhang, Wonbin Kweon, Jiawei Han
similarity 0.73
Abstract · Preprint. 43 pages

Long-horizon assigned work requires an LLM agent to track the state of a task: which steps are done, blocked, cancelled, or open to repetition. Agent systems either keep this state as text in the prompt and rely on the model to read that text, or move the state into a module that enforces it, and each system is evaluated as a whole, so no one knows how much reliability comes from the state being shown, told, or enforced. We fix the task rules, the model, and paired episodes and vary how strongly task state reaches the agent: a raw transcript, an exact checklist, per-turn directives from a state machine compiled from the brief and advanced only by execution receipts, or an enforcement gate on that machine that refuses state-violating actions; every episode is scored by exact payload matching against dynamic ground truth. Across three models, two reasoning regimes, and two domains, four findings hold without per-turn reasoning: displaying accurate state is unreliable, an unverified ledger the agent writes itself beats an accurate checklist it is shown, directives help in proportion to the model's obedience, and enforcement needs no obedience but is bounded by the correctness of its state and by the matcher that maps requests to steps; per-turn reasoning at a 235B agent compresses these separations without repairing the text rungs. The same gate, compiled from $τ^2$-bench's airline policy, raises a 235B agent's pass$^1$ from 0.39 to 0.54 and changes nothing for a 35B agent that rarely violates the policy; on PM-Bench, where acting turns on recognizing a cue rather than on state, showing the record is the best rung--matching or beating both gates and reversing the ledger-over-checklist finding--and enforcing the matcher's judgement drops a 35B agent below its raw transcript. Enforcement pays when failures are state-decidable and frequent, and hurts when the gate's judgement is wrong.

0.29

HEXIS: Compiling Agent Skills into Extended Finite State Machines

cs.AI ·2026-09-24 ·Minghao LI
similarity 0.69
Abstract

Agent skills provide instructions and reusable knowledge, yet agents have to frequently infer which action to take next. This skill's execution paradigm combines task reasoning with control decisions, which could cause the agent to act improperly or omit necessary steps. To improve agent compliance for skills, we introduce HEXIS, which compiles agent skills into extended finite state machines (FSM) that separate knowledge from control flow. Skill knowledge is incorporated into local instructions that guide reasoning and generation within states. The machine records execution progress and intermediate results, while explicit transition conditions determine subsequent operations. Our incremental compiler first maps skill clauses and tool interfaces to state operations, local instructions, data bindings, and transitions. It then aligns development traces with existing states to identify missing operations and dependencies. These are incorporated by adding or reusing states and refining their connections. Updates are accepted only after static checks and replay of the current and all previously accepted traces. Across four benchmarks and four executors, HEXIS improves success over Skill + ReAct by 16.2 percentage points on average. Qwen3.8-27B reduces execution tokens by 38.4-88.9% across benchmarks.

0.41

How Fast Do Agents Rot? An Empirical Study of Long-Horizon Degradation in LLM Agents for Production Decision-Making

cs.AI physics.soc-ph ·2026-08-31 ·Shubhra Mittal
benchmarkpositioncode/data similarity 0.69
Abstract

Production deployments of large language model (LLM) agents remain unreliable on long, multi-step workflows even as benchmark success rates climb steadily. We argue this gap is largely an artifact of task horizon: benchmarks are dominated by short-to-medium horizons where success remains high, while production workloads demand an order of magnitude more dependent steps. We measure the effect directly, characterizing the shape of agent degradation and disentangling its cause across a large controlled study spanning nine models, six open models from 1.2B to 671B parameters, and three deployed proprietary systems; four task families, including a genuinely agentic tool-use loop; five horizons; and three context regimes. Task success follows a geometric law governed by a single per-step reliability parameter, which rises with model scale but saturates well below 1 even for the strongest models, guaranteeing eventual collapse at sufficiently long horizons. The effect is sharpest on the agentic task, where every model tested, including widely deployed systems, falls from near-perfect success to near zero within sixteen steps of (n=10,664 analyzed trajectories. Degradation is driven by step count rather than context length: bounding the context window steepens decay rather than easing it (logit slope -0.69 vs. -0.44), p=3x10-6), contradicting a lost-in-the-middle explanation and warning against a common production shortcut. Projecting measured reliability onto representative benchmark horizons quantifies a substantial gap between benchmark and production conditions, from 0.42 at GAIA-length horizons to 0.24 at hundred-step production horizons. For teams responsible for agent orchestration and reliability at scale, these results argue for horizon-aware evaluation and reliability budgeting in place of aggregate pass-rate metrics. Code, prompts, seeds, and raw trajectories are released.

0.52

When "Must" Becomes "Maybe": Erosion of Workflow Constraints in LLM Agent Handoffs

cs.AI cs.MA ·2026-08-25 ·Yiheng Sun, Huifei Wang, Yancheng Zhu, Zhenyu Li, Zebin Zhao +1 more
similarity 0.69
Abstract · 16 pages, 4 figures. Revised title, abstract, and exposition; expanded discussion and reorganized appendix

Large language model (LLM) agents build on one another's work through summaries, plans, and other intermediate artifacts. These records let a downstream agent continue without revisiting the complete upstream context. We uncover a hidden loss in this process: handoffs can carry tasks forward while eroding judgments already established upstream. A requirement that must be satisfied before action becomes a caveat that the next agent may acknowledge and set aside. The issue remains visible, but its role has changed. We define operational state preservation as retaining an established judgment's role in constraining downstream action. Safety blockers provide a concrete instance: an unresolved prerequisite restricts the admissible actions until the condition is resolved. In our experiments, we confirm correct upstream detection, hold source permissions fixed, and vary the handoff supplied to a local-view executor. Direct-state controls preserve every blocker, whereas compression, plan assimilation, convergence, ownership deferral, and precedent substitution repeatedly weaken them. Ownership deferral produces 76.7% blocker deactivation; multihop compression produces 97.2%. Measuring the transmitted state separately from endpoint action exposes two routes to behavioral recovery. In fixed-artifact replays, restoring the full blocker description raises recognition from 6.2% to 99.2% and reduces forbidden action from 85.2% to 0.0%. An authorization-check prompt instead reduces forbidden action to 1.6% while leaving artifact deactivation at 95.3%. A successful endpoint can therefore conceal a damaged handoff. These findings make maintaining earlier judgments a core capability of reliable collaboration: each stage must carry forward both what earlier work established and what it requires of subsequent action. Semantic availability does not guarantee operational preservation.

0.50

Automata from Agent Traces: Failure and Next-Step Prediction

cs.AI cs.CLcs.LG ·2026-08-24 ·Seonglae Cho, Franklin Cardenoso Fernandez, Umar Mohammed, Zekun Wu, Kleyton Da Costa +2 more
highly cited similarity 0.69
Abstract

LLM-based agents execute multi-step tasks, but their behavioral structure remains opaque: long unstructured traces resist the safety auditing and runtime monitoring that deployment requires. Existing approaches operate per-trace or success-only, so they miss the cross-run topology that links next-step and failure prediction. To recover that shared structure, we collapse an entire trace corpus into a single, compact finite-state machine (FSM) that serves as a structural substrate for the otherwise unpredictable behavior of LLM agents. Across twelve public datasets, the FSMs are compact (7-43 states), replay held-out data at >=0.997 fitness with near-identical topology across splits, and build in milliseconds. This substrate addresses both prediction goals. For next-step prediction, FSM-state context outperforms Agent Workflow Memory on every ground-truth-matched dataset. For failure prediction, per-state behavioral features reach held-out AUROC up to 0.94, and an online monitor ranks failing runs above passing ones from a partial trace, triggering early stopping well before completion. Behavioral topology thus appears shaped more by the deployment harness than by the LLM, providing a model-agnostic structural primitive for safety auditing and runtime monitoring.

0.51

The Unreliable Progress Bar: Can LLM Agents Reliably Report Task Progress Throughout Execution?

cs.SE cs.AIcs.CL ·2026-09-08 ·Boyang Wang, Yunhan Wang, Yalun Wu
benchmark similarity 0.68
Abstract · 33 pages, 13 figures, 20 tables

Recent large language models can emit task-progress signals that agent frameworks use to decide whether a task should continue or stop, yet whether a model can reliably report its task progress at every stage of a task, and where and how its reports fail, has not been studied systematically. We evaluate this ability on the public benchmark $τ^2$-bench and on StageIF, a controlled testbed in which reporting checkpoints are placed across the task's lifecycle. Both settings require reports at multiple task stages. We find that reporting reliability depends on the stage a task has reached, and that almost every deployed model we test is reliable at some stages and unreliable at others. Where reporting breaks down is not the same everywhere. Most deployed models lose accuracy once work is under way and recover once the task is done. The newest generation closes that mid-task drop and instead grows conservative at the finish line. Our study exposes a capability gap in task-progress reporting and provides an evaluation protocol that spans the whole course of task execution for this ability on which agent operation depends. The findings indicate that agent frameworks should not control task flow on the strength of the model's state reports alone.

0.43

How Much Skill Orchestration Can LLM Agents Compile Away? Execution-Grounded Specialization for Token-Efficient Skill Use

cs.SE cs.AIcs.CLcs.LG ·2026-11-05 ·Jiayi Ni, Zac Wang, Alex Zhang, Zheng Liu, Roopa Prabhu
published similarity 0.68
Abstract · 35 pages, 20 figures, 16 tables. An earlier version has been selected for an oral/spotlight presentation at the AgenticOS workshop at NeurIP…

Reusable skills guide large language model (LLM) agents through recurring requests, but each invocation still requires the model to interpret the skill and reconstruct its orchestration. Can agents automatically compile this orchestration into an executable fast path without human intervention? We first study zero-shot skill specialization, which compiles without execution evidence, and find that despite the skill's procedural guidance, incorrect assumptions about runtime bindings can make generated plans brittle and recovery costly. This motivates SkillCache, a one-trace skill specialization method that compiles a completed invocation into a parameterized capsule of programs and natural-language steps, replays it before reuse, and drives it with a plan executor that returns control to the model only when needed, keeping the source skill for recovery. With the Claude Code harness, warm execution of the same request reduces tokens on 87 SkillsBench tasks by 81% with Claude Sonnet 4.6 and by 74% with Claude Opus 4.8 at comparable reward, and capsules stay effective under controlled request changes. Capsules also transfer across models, raising three open-weight models' mean reward by 12-25 percentage points while reducing their tokens by 72-81%, suggesting that execution-grounded compilation is a promising approach to efficient repeated skill use and cross-model transfer.

0.27

Safety Does Not Compose: Non-Decaying Loop State for Autonomous LLM Agents

cs.CR cs.AI ·2026-08-27 ·Chenhao Wu, Haoxuan Jia, Yang Liu, Yingguang Yang, Yuhan Lin +9 more
similarity 0.68
Abstract

Large language model agents are increasingly deployed as autonomous loops. Starting from one human goal, such a system repeatedly discovers work, plans, executes tool calls, verifies outcomes and persists state across many unattended iterations. The agent safeguards in wide use, however, are defined over a single trajectory, and their safety state is re-initialized when the next trajectory begins. We show that this is a failure of composition rather than an implementation detail. Our central result is a separation: against an attack whose evidence is fragmented across several iterations, every trajectory-scoped monitor has a true-positive rate equal to its false-positive rate, however expressive it is, because the evidence it would need never appears in the window it sees, whereas a monitor retaining cross-iteration state separates the two perfectly. We further show that the obvious repair of carrying a geometrically decaying risk score is insufficient, because the cooling-off period a patient adversary must wait is a constant that does not grow with the horizon $N$. We then present LoopHarness, which restores a persistent, non-decaying safety state at the loop level. Under mediated commits and an arbiter detection floor $δ_M$, it bounds the expected number of unauthorized irreversible actions by $B+m-1+m/δ_M$, a constant in $N$, of which the $B+m-1$ term is decided by a model-free rule and therefore survives a fully colluding verifier. We give a complete evaluation protocol on native Agent-SafetyBench tasks with paired clean and attacked episodes, an outer-state attack suite whose decisive evidence exists only across iterations, per-module ablations, and an adaptive white-box red team.

0.22