One-sentence Summary

Researchers from Google LLC and Purdue University propose SKILL.state, a runtime architecture that replaces append-only conversational history with an explicit, mutable execution state, providing the model only the immutable skill specification, current structured state, and latest observation at each step while discarding intermediate reasoning after validated updates, thereby improving task accuracy and reducing cumulative token consumption across diverse datasets, models, and execution environments for scalable long-horizon agent skills.

Key Contributions

• Introduces SKILL.state, a runtime architecture that executes procedural skills via explicit structured execution state, discarding intermediate reasoning after each validated step to achieve a strictly bounded prompt footprint and linear cumulative token complexity.
• Presents SkillExecBench, a controlled benchmark for long-horizon procedural skill execution under scaling, noise, and state recovery, alongside evaluations on public benchmarks including InterCode CTF and Sierra τ-Bench.
• Demonstrates across multiple model families and execution horizons that state-centric execution maintains competitive task accuracy while substantially reducing prompt growth and cumulative token consumption relative to history-based and compression-based baselines.

Introduction

Large language models are increasingly used as autonomous agents that execute long-running procedural skills, such as software engineering or web interaction, by composing reusable behaviors. However, modern agent runtimes rely on a conversational execution model, where the model processes an ever-growing transcript of past reasoning, actions, and observations at every step. This causes prompt size to grow with execution length, inflating token consumption and inference cost, while forcing the model to reconstruct current facts from stale historical artifacts, which degrades correctness over long horizons.

Prior work addresses context growth through memory systems like summarization or retrieval, but these preserve the same semantics: decisions still depend on textual reconstructions of the past rather than an explicit representation of the current state. Frameworks such as LangGraph add auxiliary structured state for orchestration, yet they continue to use conversational transcripts as the primary reasoning substrate. This leaves execution state implicitly distributed across accumulated logs, requiring repeated world-model reconstruction and limiting scalability.

The authors introduce SKILL.state, a runtime architecture that reformulates procedural skill execution as explicit state transitions instead of history accumulation. At each step, the model receives only the immutable skill specification, a structured execution state, and the latest environment observation, discarding intermediate reasoning traces after producing a validated update. This yields a strictly bounded prompt footprint and linear cumulative token complexity. Evaluations on a new benchmark, SkillExecBench, plus InterCode CTF and Sierra tau-Bench, show that state-centric execution maintains competitive task performance while substantially reducing prompt growth and token consumption across multiple model families.

Dataset

The authors evaluate their system using two complementary benchmark categories: a controlled diagnostic testbed and public interactive benchmarks.

1. SkillExecBench (Controlled Diagnostic Testbed) This benchmark isolates execution mechanics from open-ended heuristic search by providing sequential procedural tasks with deterministic groundtruth world transitions. It includes two environments:

• Warehouse Management: A discrete physical inventory domain tracking 500 independent shelves. Actions include Store, Ship, Move, and Wait. This environment tests the model's ability to maintain independent, nonoverlapping state variables over extended horizons where early observations leave the context window.
• Software Repository: A deeply nested, relational graph of Git branches, commits, Pull Requests, and CI test statuses. Actions include CherryPick, Merge, RunTests, CreateRelease, and Rollback. This environment features dense dependencies where a single action (e.g., merging a PR) fundamentally alters the state of the target branch and dependent PRs, testing complex structural reasoning over an entangled graph.

2. Public Interactive Benchmarks To evaluate on real-world, nondeterministic tasks with complex search, generation, and tool use, the authors use two public benchmarks:

• InterCode CTF: A suite of 100 Linux bash Capture-The-Flag challenges spanning reverse engineering, forensics, cryptography, and binary exploitation. Agents execute bash commands in Docker containers and iteratively test hypotheses to discover hidden flags.
• Sierra τ-Bench: A benchmark for tool-agent-user interaction in enterprise customer service (Retail and Airline domains). Agents interact with simulated users, query relational SQLite databases via tool calls, and execute transactional actions (e.g., flight rebooking, refunds) under business policy constraints.

The SkillExecBench serves as a controlled setting to diagnose execution mechanics, while the public benchmarks test performance on realistic, nondeterministic tasks requiring search, generation, and tool use.

Method

Current LLM agent runtimes typically execute procedural skills by appending reasoning traces, actions, observations, and tool outputs to a growing conversational history. This approach implicitly represents the execution state within natural language, forcing the model to reconstruct the current world state from historical text at every interaction. As execution horizons lengthen, prompt size and obsolete information grow monotonically.

To address these limitations, the authors introduce SKILL.state, a runtime architecture that reformulates procedural skill execution as an explicit state transition process. Instead of relying on an append-only conversation, every execution step is defined by the tuple:

where $P$P is the immutable procedural specification, $\Sigma_t$Σt​ is the structured execution state at step $t$t, and $O_t$Ot​ is the latest observation from the environment. The language model never receives previous observations, actions, or reasoning traces.

As shown in the figure below:

The execution cycle operates by constructing a prompt from the current tuple, invoking the language model, validating the proposed state transition, updating the execution state, and executing the selected action. Unlike conversational runtimes, SKILL.state treats the execution state as a first-class runtime abstraction. The state contains only the information required for future execution and is represented using a structured schema defined for the domain. These schemas are authored once per domain rather than per task, allowing agents to reuse a single static schema across diverse challenge instances.

Reasoning is utilized strictly as an intermediate computation for producing state transitions and selecting the next action. Given the context $(P, \Sigma_t, O_t)$(P,Σt​,Ot​), the language model generates:

where $R_t$Rt​ denotes the multi-step Chain-of-Thought reasoning trace, $\Delta\Sigma_t$ΔΣt​ is a structured state update represented as a JSON dictionary of key mutations and deletions, and $a_t$at​ is the action to execute. While multi-step reasoning remains fully intact during generation to support complex deductive planning, the reasoning trace $R_t$Rt​ is permanently discarded once the state transition is validated and applied. The execution state is then updated according to:

where $\oplus$⊕ denotes the runtime dictionary merge operator with null-deletion semantics. This mechanism projects transient reasoning into persistent structured state, ensuring only information necessary for future execution survives across interactions.

This architectural shift yields significant improvements in computational complexity. For conversational runtimes, prompt length grows with accumulated history, resulting in a cumulative token complexity of $\mathcal{O}(T^2)$O(T2) over an execution horizon $T$T. In contrast, SKILL.state maintains a prompt size that is asymptotically bounded and independent of the number of previously executed turns:

Consequently, the cumulative prompt complexity grows strictly linearly with the execution horizon:

This runtime effectively shifts execution from reconstructing history toward maintaining an explicit, validated representation of the current execution state.

Experiment

The evaluation used SkillExecBench, a controlled testbed with warehouse and software repository environments, plus public benchmarks InterCode CTF and Sierra tau-Bench, measuring task accuracy, prompt size, and token cost. Across long-horizon scaling, noise robustness, and state recovery tests, SKILL.state matched or exceeded baseline accuracy while keeping prompt size flat, unlike history-appending baselines that suffered quadratic token growth and degraded under injected distractors or external state drift. On public benchmarks, it achieved the highest task completion rates with substantial token savings. Budget-matched compression controls failed catastrophically, confirming that gains come from structured state representation rather than shorter prompts. Open-weight model errors were mostly premature state overwrites, indicating structured output adherence issues rather than reasoning limits.

SKILL.state maintains a bounded prompt footprint and matches or exceeds baseline accuracy across long-horizon warehouse management tasks, while baselines suffer quadratic token accumulation. At longer horizons, SKILL.state uses substantially fewer total tokens than history-appending baselines while preserving high accuracy. SKILL.state keeps prompt size nearly flat (around 1,736-1,905 tokens) across horizons, whereas baselines grow quadratically. At T=200, SKILL.state achieves 0.94 accuracy with 122k total tokens, while the Memory baseline consumes 6.1M tokens. At T=100, SKILL.state uses 65,408 total tokens versus 1,062,387 for the Stateful baseline, a large reduction. At T=10 and T=25, SKILL.state matches or exceeds baseline accuracy while using the smallest average prompt and total tokens.

Under warehouse noise with a fixed horizon of 50, the standard Prompt runtime drops from 0.68 at low noise to 0.53 at high noise, while SKILL.state maintains task completion above 0.97 across all noise levels. This robustness is attributed to distractor filtering during state patch generation, which prevents irrelevant events from entering subsequent prompts. SKILL.state sustains high task completion across low, medium, and high noise levels, unlike the Prompt runtime which degrades sharply. The Prompt runtime's score falls from 0.68 at low noise to 0.53 at high noise, whereas SKILL.state remains above 0.97. Distractor events are filtered out during state patch generation, so they do not affect later prompts.

In warehouse state recovery tests, history-based baselines hallucinate for 5 to 8 consecutive turns after external state changes, while SKILL.state recovers immediately with zero recovery steps across all scenarios. The canceled order scenario fails for all runtimes, indicating a task-level limitation rather than a runtime-specific issue. History-based baselines require 5 to 8 recovery steps due to obsolete prompt facts overriding new observations. SKILL.state achieves zero recovery steps by relying on the current structured state, which updates instantly upon corrective alerts. The canceled order scenario is unsuccessful for all runtimes, suggesting an inherent task difficulty.

SKILL.state consistently outperforms all baselines across three public interactive benchmarks, achieving the highest task success rates while using substantially fewer tokens. Its structured state representation reduces prompt sizes and cumulative token consumption, particularly in complex tool-use and database-heavy tasks. SKILL.state achieves the highest pass rates on all three benchmarks, with notable gains on InterCode CTF and τ-Bench Retail. Prompt sizes are drastically reduced, especially on τ-Bench Airline where the prompt footprint stays flat at 2,800 tokens per step versus baselines exceeding 11,000. Cumulative token usage is cut by 40-66% compared to ReAct and Stateful baselines across the evaluated tasks.

When all baselines are restricted to the same token budget as SKILL.state, they suffer severe performance drops, while SKILL.state maintains a high score. This indicates that its gains come from structured state representation rather than simply using fewer tokens. Sliding-window truncation and LLMLingua compression both drop to scores below 0.25, while SKILL.state achieves 0.94. The failures of compression baselines are attributed to eviction of early critical allocations and removal of semantically vital slot identifiers. SKILL.state's structured state preserves relational dependencies that statistical compressors destroy.

SKILL.state maintains a bounded prompt footprint and matches or exceeds baseline accuracy across long-horizon warehouse tasks, avoiding the quadratic token growth of history-appending baselines while staying robust to noise through distractor filtering. It recovers instantly from external state changes, unlike history-based baselines that hallucinate for multiple turns, though a canceled-order scenario fails for all runtimes. Across public interactive benchmarks, SKILL.state achieves the highest task success rates with substantially lower token usage, and when baselines are given the same token budget, they drop sharply in performance, confirming that its gains stem from structured state representation rather than token efficiency alone.