# Dude, Where's My State? Execution Information Requirements for Stateful Agents

arXiv: https://arxiv.org/abs/2609.32687 · HTML: https://mlsanity.com/paper/2609.32687/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 24 of its 36 references that are in the map.
- First posted on arXiv 26 Sep 2026.

## Builds on (most cited first, 24 of 24)

- [Generative Agents: Interactive Simulacra of Human Behavior](https://mlsanity.com/paper/2304.03442/) (2023)
- [Lost in the Middle: How Language Models Use Long Contexts](https://mlsanity.com/paper/2307.03172/) (2023)
- [SWE-bench: Can Language Models Resolve Real-World GitHub Issues?](https://mlsanity.com/paper/2310.06770/) (2023)
- [τ-bench: A Benchmark for Tool-Agent-User Interaction in Real-World Domains](https://mlsanity.com/paper/2406.12045/) (2024)
- [MemGPT: Towards LLMs as Operating Systems](https://mlsanity.com/paper/2310.08560/) (2023)
- [RULER: What's the Real Context Size of Your Long-Context Language Models?](https://mlsanity.com/paper/2404.06654/) (2024)
- [Training Deep Nets with Sublinear Memory Cost](https://mlsanity.com/paper/1604.06174/) (2016)
- [LongMemEval: Benchmarking Chat Assistants on Long-Term Interactive Memory](https://mlsanity.com/paper/2410.10813/) (2024)
- [Terminal-Bench: Benchmarking Agents on Hard, Realistic Tasks in Command Line Interfaces](https://mlsanity.com/paper/2601.11868/) (2026)
- [Scaling Long-Horizon LLM Agent via Context-Folding](https://mlsanity.com/paper/2510.11967/) (2025)
- [ACON: Optimizing Context Compression for Long-horizon LLM Agents](https://mlsanity.com/paper/2510.00615/) (2025)
- [Michelangelo: Long Context Evaluations Beyond Haystacks via Latent Structure Queries](https://mlsanity.com/paper/2409.12640/) (2024)
- [MemoryArena: Benchmarking Agent Memory in Interdependent Multi-Session Agentic Tasks](https://mlsanity.com/paper/2602.16313/) (2026)
- [Memory-Efficient Backpropagation Through Time](https://mlsanity.com/paper/1606.03401/) (2016)
- [Memory as Action: Autonomous Context Curation for Long-Horizon Agentic Tasks](https://mlsanity.com/paper/2510.12635/) (2025)
- [Mem2ActBench: A Benchmark for Evaluating Long-Term Memory Utilization in Task-Oriented Autonomous Agents](https://mlsanity.com/paper/2601.19935/) (2026)
- [Remember When It Matters: Proactive Memory Agent for Long-Horizon Agents](https://mlsanity.com/paper/2607.08716/) (2026)
- [Your Agents Are Aging Too: Agent Lifespan Engineering for Deployed Systems](https://mlsanity.com/paper/2605.26302/) (2026)
- [Remember the Decision, Not the Description: A Rate-Distortion Framework for Agent Memory](https://mlsanity.com/paper/2605.10870/) (2026)
- [Toward a Theory of Hierarchical Memory for Language Agents](https://mlsanity.com/paper/2603.21564/) (2026)
- [What to Keep, What to Forget: A Rate--Distortion View of Memory Compaction in LLMs and Agents](https://mlsanity.com/paper/2607.08032/) (2026)
- [The Illusion of Procedural Reasoning: Measuring Long-Horizon FSM Execution in LLMs](https://mlsanity.com/paper/2511.14777/) (2025)
- [Context Compaction Theory](https://mlsanity.com/paper/2608.01326/) (2026)
- [World-Model Collapse as a Phase Transition](https://mlsanity.com/paper/2606.31399/) (2026)

## Abstract (arXiv)

Long-running agents must preserve information that later steps depend on. We introduce the Execution Information Requirement (EIR), a lower bound on the information that must remain accessible for correct completion under specified task and access conditions. We develop LACUNA, a framework that generates tasks with known dependencies and varies information demand, retention, and recovery separately from the difficulty of individual operations. Across four models, restoring a missing result raises accuracy on affected recall steps to 100%, compared with 0% for equal-length irrelevant information. Sufficient storage alone does not ensure success: retention policies can discard required results, errors can propagate through later computations, and agents can stop before recovery is complete. We also introduce VESTIGE, which uses agent execution traces to construct semantic graphs and measure information demand for real tasks. Across 72,562 software-agent trajectories, VESTIGE reveals a steeper distance-related decline in solution-relevant rereading for failed runs (RR 0.951 per distance doubling), while adjusted peak demand alone is not associated with failure. Together, these contributions support evaluating whether agents preserve and recover the information their tasks require.