SKILL.state: Scalable Long-Horizon Agent Skills

AI summary

Authors: Sanket Badhe, Priyanka Tiwari (Google LLC), Jonghyun Chung (Purdue University) · arXiv:2608.26263v3 [cs.AI] · CC BY 4.0 · Published 2026-08-26

Overview

Research area: LLM agent runtimes and long-horizon procedural skill execution — context management, agent memory architecture, and inference cost scaling.

Technical level: Advanced. The paper mixes systems-architecture design, asymptotic complexity analysis of prompt growth, and multi-benchmark empirical evaluation, though the central idea is expressible in a single sentence.

Scope: The paper proposes a runtime that replaces append-only conversation history with an explicit, mutable structured execution state, and evaluates it across a custom controlled benchmark, InterCode CTF, and Sierra τ-Bench.

What This Paper Is About

LLM agents that execute long procedures typically work by appending every observation, action, and reasoning trace to an ever-growing conversation transcript that the model must re-read at every step. This makes prompts grow with execution length, inflates token cost, and forces the model to continually separate current facts from obsolete history — a failure the authors call context poisoning. SKILL.state instead treats execution as an explicit state transition problem: at each step the model sees only the immutable skill specification, the current structured execution state, and the newest observation, and its intermediate reasoning is thrown away once a validated state update is produced.

Key Contributions

1. The SKILL.state runtime architecture, which executes procedural skills through explicit structured execution state. Intermediate reasoning traces are discarded after each validated transition, yielding a strictly bounded O(1) prompt footprint and O(T) cumulative token complexity, versus O(T²) for history-appending runtimes.
2. SkillExecBench, a controlled diagnostic benchmark with two deterministic environments — Warehouse Management (500 independent shelves) and Software Repository (a nested graph of Git branches, commits, PRs, and CI statuses) — designed to isolate execution mechanics from open-ended search under scaling, noise, and state-recovery conditions.
3. Evaluation on public interactive benchmarks — InterCode CTF (100 Linux bash challenges) and Sierra τ-Bench (Retail and Airline) — alongside the controlled benchmark.
4. Demonstration across model families (Gemini-3-Flash, Gemma-4-31B-it, Qwen-3-8B-it) that state-centric execution keeps task performance competitive or better while substantially reducing prompt growth and cumulative token consumption, plus an error taxonomy for open-weight models.

Main Findings

• Flat prompt size under scaling: On the Warehouse environment (Gemini-3-Flash), SKILL.state's average prompt stays essentially constant as horizon grows — 1,775±74 characters at T=10, 1,736±49 at T=25, 1,773±53 at T=50, 1,905±93 at T=100, and 1,811±184 at T=200 — while baselines grow to tens of thousands of characters per call.

• Token reduction at T=100: The Stateful (LangGraph-style) baseline consumes 1,062,387 tokens versus 65,408 for SKILL.state, a 16.2 times reduction. SKILL.state reaches 0.94±0.01 accuracy at that horizon.

• Accuracy advantage at T=200: SKILL.state maintains 0.94±0.02 accuracy consuming 122,384±4,522 tokens, while the Memory baseline inflates to 6.1M tokens (6,175,509±294,089) and the Prompt baseline reaches 2,608,755±102,415 tokens at 0.74±0.14 accuracy.

• Noise robustness: At T=50 in the Warehouse with injected distractors, the Prompt runtime degrades from 0.68 (5 events) to 0.61 (20 events) to 0.53 (50 events). SKILL.state stays at 1.00, 0.97, and 0.98 respectively, because distractors are filtered during state patch generation and never enter later prompts.

• Zero-step state recovery: When the true world state is silently changed outside the agent's action loop (Secret Audit, Secret Barcode, Secret Move scenarios), history-based baselines hallucinate for 5 to 8, 6 to 8, and 5 to 8 consecutive turns respectively. SKILL.state requires 0 recovery steps in all three. A fourth scenario, "Canceled Order," fails for all runtimes.

• InterCode CTF gains: SKILL.state reaches 54.2% pass@1 with 813 average prompt characters and 387k tokens, versus 43.2%/1,909/977k for ReAct, 46.4%/1,797/1.03M for Memory, and 41.8%/1,946/1.13M for Stateful. That is +7.8 points over the strongest baseline and +12.4 points over Stateful, with 60.4% fewer tokens than ReAct and 65.9% fewer than Stateful.

• Sierra τ-Bench results: Retail — SKILL.state leads at 58.3% pass rate with the lowest total token cost (3.47M vs 4.48M ReAct, 4.24M Memory, 3.92M Stateful). Airline — SKILL.state achieves 32.4% pass rate with a flat ~2,800 tokens/step footprint while baseline prompts peak above 11,000 tokens/step, saving 40.5% tokens vs ReAct and 45.4% vs Stateful.

• Compression baselines collapse: Pinned to the same ~1,800-character budget at T=100 on Warehouse, sliding-window truncation scores 0.18, LLMLingua-based compression 0.22, and summary-capped 0.52, while SKILL.state scores 0.94. The authors attribute this to statistical compressors destroying exact relational dependencies and truncation evicting critical early inventory allocations.

• Open-weight model failure modes: On Gemma-4-31B at T=100 (score 0.42), failures split into premature state overwrite/deletion (68%), schema comprehension and type coercion (20%), and JSON syntax/formatting slips (12%) — suggesting degradation stems from structured output adherence rather than reasoning capacity.

• Additional model scaling (Appendix): On Gemma-4-31B-it Warehouse at 100 steps, SKILL.state and Stateful both score 0.42, while SKILL.state uses 2,105 characters and 65,480 tokens versus Stateful's 20,210 characters and 557,968 tokens. On Qwen-3-8B-it at 100 steps, SKILL.state scores 0.34 versus 0.31 Stateful, 0.18 Memory, and 0.15 Prompt.

• Software Repository scaling: At T=100, SKILL.state scores 0.78±0.08 at 2,545±471 characters and 90,200±2,792 tokens, versus 0.53±0.16/46,270/1,848,500 for Prompt, 0.57±0.05/71,100/2,752,700 for Memory, and 0.63±0.10/62,330/2,308,000 for Stateful.

• Schema reuse: A single static 5-field schema (discovered_flags, tested_hypotheses, active_files, working_dir, cmd_summary) is reused across all 100 InterCode CTF challenge instances, supporting the claim that schemas are authored per domain rather than per task.

• Statistical significance: Differences between SKILL.state and baselines at extended horizons (T ≥ 50) are reported as statistically significant by a paired t-test with p < 0.01, across 5 procedural generator seeds.

Methodology in Plain English

The researchers recast agent execution as a state machine rather than a chat log. At each step t, the runtime builds a prompt from exactly three things: the fixed skill instructions P, the current structured execution state Σ_t, and the newest environment observation O_t. The model responds with a reasoning trace, a structured state patch (a JSON dictionary of key mutations and deletions, where nulls delete keys), and the action to take. The runtime validates the patch, merges it into the state using a dictionary merge operator with null-deletion semantics, executes the action, and moves on — discarding the reasoning trace permanently so it never appears in a future prompt.

To test this, they built SkillExecBench with two deterministic environments (a 500-shelf warehouse with Store/Ship/Move/Wait actions, and a Git repository with CherryPick/Merge/RunTests/CreateRelease/Rollback actions) generated procedurally from a fixed seed of 42, so all baselines see an identical event sequence. They compared against six baselines: ReAct-style prompt appending, summarization-based memory with a rolling 3-step window, a LangGraph-style stateful runtime that still carries the full transcript, sliding-window truncation, summary-capped history, and ReAct with LLMLingua compression. Controlled experiments varied execution horizon (T = 10 to 200), injected irrelevant telemetry noise (5, 20, 50 events per turn), and simulated silent external state drift. They then validated on InterCode CTF and Sierra τ-Bench. All runs used temperature 0.0 and top-p 1.0 for deterministic reproducibility, and synthetic experiments were repeated across 5 seeds with mean ± sample standard deviation reported.

Why This Matters

Impact on research: The paper reframes long-horizon agent execution as a systems problem rather than a reasoning problem, and supplies a concrete complexity argument (O(1) prompt, O(T) tokens versus O(T²)) plus budget-matched controls showing that the gains come from structured state representation, not merely from shorter prompts. That distinction challenges a common assumption that context compression is a sufficient fix for context growth.

Real-world applications:

• Autonomous customer-service agents operating over enterprise databases under business policy constraints, where multi-turn history is long and transactional actions are irreversible.
• Security and penetration-testing agents running long terminal sessions, where tracking discovered flags and tested hypotheses prevents repeated failed commands.
• Software release automation agents that must track entangled Git branch, PR, and CI state across hundreds of steps.
• Warehouse or logistics automation with continuous background telemetry, where irrelevant sensor and robot logs must be filtered before they reach the decision model.

Industry relevance: Cost and latency are the practical bottlenecks for deployed agents. SKILL.state's token reductions (16.2 times versus the Stateful baseline at T=100 on Warehouse; 60.4% fewer tokens than ReAct on InterCode CTF) translate directly into inference cost. The explicit-state abstraction also provides a natural coordination substrate for multi-agent systems, where shared state could replace quadratic transcript exchange.

Future Directions

1. Grammar-constrained decoding for open-weight models, to eliminate the JSON syntax and formatting errors that account for 12% of Gemma-4-31B failures and let smaller models focus on semantic state transitions.
2. Dynamic schema discovery, for settings where no fixed state schema is known in advance and the relevant state structure must be inferred during execution.
3. Deferred relevance handling, for cases where a correct state update depends on an earlier observation whose relevance was not recognized when it was first seen and therefore was never committed to state.
4. Multi-agent extension with deterministic conflict resolution, since concurrent writes to a shared execution state require merge-operator semantics that the current single-agent setting does not exercise.

The paper also notes that tasks defined over the historical trajectory itself — auditing, debugging provenance, explaining past actions — remain outside the architecture's scope, since there the interaction history is the target output rather than operational overhead.

Target Audience

Agent-runtime and infrastructure engineers building production LLM systems who need to control context growth and inference cost; researchers working on agent memory, long-horizon planning, and context management; and applied scientists evaluating whether structured state or context compression is the right lever for their workload. Readers wanting only the headline result can read the abstract and Table 1; readers implementing a runtime will want Section 3 and the prompt templates in Appendix A.

Authors’ abstract

Large Language Models (LLMs) increasingly act as autonomous agents executing complex, long-running procedural skills. Existing agent runtimes maintain execution by continually appending observations, actions, and intermediate reasoning traces to an ever-growing conversation history, causing latency degradation and context-poisoning failures over long horizons. We present SKILL.state, a runtime architecture that replaces append-only conversational history with an explicit, mutable execution state. At each execution step, the model receives only the immutable skill specification, the current structured execution state, and the latest observation. Intermediate reasoning is discarded immediately after producing a validated state update, preventing prompt growth with execution history. Across diverse datasets, models, and execution environments, SKILL. state improves task accuracy while substantially reducing cumulative token consumption. Our results demonstrate that explicit execution state is an effective and architecture-agnostic abstraction for scalable long-horizon agent skills.