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

Nikita Mehrotra; Ashish Tiwari; Priyanshu Gupta; Sumit Gulwani

cs.AISep 26, 2026

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

Authors: Nikita Mehrotra, Ashish Tiwari, Priyanshu Gupta, Sumit Gulwani

Abstract

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.

Figures & tables

Panel of Figure 1 — Figure 1: Missing information and task difficulty in real agent tasks. A: The agent edits a file without seeing a clipped line; the next test fails. Teal shows estimated information used later. B: Higher memory demand is associated with more failures, but the association is no longer statistically significant after accounting for task difficulty ( $p=.191$ ). Dots show failure odds ratios; bars show 95% confidence intervals. The dashed line at 1 means no association.

Panel of Figure 2 — Figure 2: Different histories can require the same information. The remaining task asks which file to edit and whether to return an aware or naive datetime. Histories with the same answers form one group; grey observations do not change either answer.

Panel of Figure 3 — Figure 3: LACUNA tests whether missing information causes errors. Fix a task instance (A), vary access to earlier results (B), and observe the agent when a required result is missing from context (C). Compare restoring that result with no added information and an equal-length irrelevant result (D).

Panel of Table 1 — Table 1: Controlled information-demand patterns. Descriptive labels precede formal workload identifiers. Rules and EIR are for the evaluated settings. Here $b=\log_{2}q$ for a value domain of size $q$ , and $\dagger$ marks EIR that depends on the dependency graph.

Figure 4: Missing inputs predict errors; restoring them repairs answers. A: Fraction of trials whose first missing dependency coincides with the first error. Bands show 95% confidence intervals. B: Restoring the required result repairs affected Store–Recall answers; adding an irrelevant value of the same length does not.

Appendix figures & tables27 assets

Supplementary material from the paper’s appendix.

Appendix

Paper name	Recorded provider identifier	Decoding
GPT-5.6 Reasoning	dev-gpt-56-reasoning	provider default †
Claude Opus 4.6	dev-anthropic-claude-opus-4-6	temperature 0
Claude Haiku 4.5	dev-anthropic-claude-haiku-4-5	temperature 0
GPT-4.1 Mini	dev-gpt-41-mini-04-14	temperature 0

Appendix

Table 2: Model and decoding configuration. Temperature zero was sent only when the endpoint advertised temperature support.

Study	Workloads and graph settings	Capacity, recovery, and policies	Models/seeds	Registered count
Capability control	Five families; $m\in\{4,8,16\}$ ; $n=64$ ; $f_{\rm in}=2$ except Running Maximum chain	Full information, $h=m$ ; no-tool primary plus deterministic-calculator control	Four models; seeds 1–3	180 primary; 72 tool-control
No-recomputation pressure	Store–Recall at $m\in\{8,16\}$ ; Stepwise Sum, Maximum, and Top- $k$ at $m=16$ ; $n=64$	Store–Recall $h\in\{2,4,\ldots,16\}$ for $m=16$ and $h\in\{2,4,6,8\}$ for $m=8$ ; other families $h\in\{4,8,12,16\}$ ; recovery prohibited	Four models for Store–Recall; three capability-eligible models otherwise; seeds 1–3	252
Store–Recall restoration	Store–Recall, $m=8$ , $h=4$ , $n=64$	No injection, exact missing result, or equal-length irrelevant result; recovery otherwise prohibited	Four models; seeds 1–3	12 trajectories per arm
Stepwise Maximum restoration	Random-DAG maximum, $m=8$ , $h=4$ , $n=64$ , $f_{\rm in}=2$	Control, exact unavailable operands, or length-matched sham	Four models; seeds 1–3	12 trajectories per arm
Recovery geometry	Sum DAG, $m=8$ , $n=64$ , $f_{\rm in}\in\{1,2,4\}$ ; nodes $t\geq 32$	Atomic retrieval versus memoized and naive recursive recomputation	Deterministic; seeds 1–3	99 cones/topology
Model recovery probes	Stepwise Sum, Maximum, and Top- $k$ recovery cones	Model selects reads; harness performs arithmetic; charged reads compared with oracle minimum	Evaluated model panel	88 probes

Appendix

Table 3: Controlled experiment configurations. Counts are attempted registered trials unless explicitly called deterministic analyses or probes.

Channel checked	Checks	Findings
Payload width	7,777	0
Identifier set	1,752	0
Occupancy	1,752	0
Ordering	1,752	0
JSON determinism	1,752	0
Message length at saturation	1,531	0

Appendix

Table 4: Controlled-retention interface audit.

Model	Stepwise Sum	Store–Recall	Running Max.	Stepwise Max.	Stepwise Top- $k$
Gpt56Reasoning	1.000	1.000	1.000	1.000	0.908
ClaudeOpus46	1.000	1.000	0.998	1.000	0.918
ClaudeHaiku45	1.000	1.000	1.000	1.000	0.754
Gpt41Mini	0.040	1.000	0.474	0.547	0.221

Appendix

Table 5: Full-information capability control. End-to-end accuracy at

h=m

, averaged over

m\in\{4,8,16\}

and three seeds (nine trials per entry). Shaded entries fall below the pre-registered

0.75

inclusion threshold.

$h$ retained	$m/h$	Store–Recall	Stepwise Sum	Stepwise Maximum	Stepwise Top- $k$
16	1.00	$1.000\pm 0.000$	$1.000\pm 0.000$	$1.000\pm 0.000$	$0.861\pm 0.246$
12	1.33	$0.875\pm 0.018$	$0.292\pm 0.058$	$0.836\pm 0.138$	$0.868\pm 0.089$
8	2.00	$0.773\pm 0.038$	$0.161\pm 0.029$	$0.770\pm 0.178$	$0.667\pm 0.223$
4	4.00	$0.667\pm 0.043$	$0.089\pm 0.007$	$0.570\pm 0.327$	$0.431\pm 0.311$

Appendix

Table 6: Less retained state lowers accuracy, especially for Stepwise Sum. End-to-end accuracy (higher is better) as the number of retained results

h

decreases, with

m{=}16

and recovery prohibited. Values are mean

\pm

standard deviation over three task seeds and three models (

3{\times}3{=}9

runs); shading marks accuracy below 0.75. The ratio

m/h

is a comparable pressure indicator across workloads, not a shared EIR formula.

$h$	$m/h$ (operational)	Query accuracy
16	1.00	0.997
14	1.14	0.865
12	1.33	0.781
10	1.60	0.675
8	2.00	0.498
6	2.67	0.382

Appendix

Table 7: Full Lookup pressure sweep. Query accuracy under fixed retention with recovery prohibited, pooled over four models and three seeds (

m=16

; 96 valid trials).

Figure 5: Store–Recall: theory vs. observed. Accuracy under the store/recall arbitrary-access workload compared with the no-lucky-guess prediction

0.5+0.5(1-\text{miss\_rate})

. Open symbols are model means over three seeds; solid lines are pooled means, dashed lines are predictions, and lower panels show signed pooled residuals. The close, mostly positive residuals show that window misses explain the trend without implying exact equality.

Model	No injection	Exact restoration	$\Delta_{\rm repair}$
Gpt56Reasoning	0.137	1.000	$+1.000$
ClaudeOpus46	0.176	1.000	$+1.000$
ClaudeHaiku45	0.000	1.000	$+1.000$
Gpt41Mini	0.140	1.000	$+1.000$
Mean	0.113	1.000	$+1.000$

Appendix

Table 8: RQ1 causal rescue. Accuracy at Store–Recall window-miss steps under no injection, the true missing result, or a length-matched sham (

m{=}8

h{=}4

; four models

\times

three seeds = 12 trajectories per arm). Each entry pools affected RECALL steps within those trajectories. The repair effect is

\Delta_{\rm repair}={\rm accuracy}_{\rm exact}-{\rm accuracy}_{\rm sham}

Model	Control	Sham	Exact
Claude Haiku 4.5	0.641	0.714	1.000
Claude Opus 4.6	0.641	0.714	1.000
GPT-5.6	0.646	0.714	1.000
Pooled mean	0.642	0.714	1.000

Appendix

Table 9: Exact state restoration rescues Stepwise Maximum. Full-trajectory accuracy under no injection, length-matched sham injection, and exact restoration at

m{=}8,h{=}4

. Each model–arm cell contains three seeds.

Panel of Figure 6 — Figure 6: Stepwise Sum error onset and propagation ( $m{=}16$ , recovery prohibited). A: Each row is one eligible model–seed trial; navy triangles mark the first window miss. Decreasing $h$ moves the error front earlier. B: Solid curves show $P(\text{wrong at }t)$ and dashed curves show $P(\text{direct window miss at }t)$ over the same nine trials per capacity; the lower panel shows their signed difference. Positive regions mean wrong answers are more prevalent than direct misses at that step, consistent with downstream cascade propagation. The 36 ledger-selected trajectories are reproduced from a checksummed artifact; the capability-control model is excluded.

Topology	Atomic	Memoized recompute	Naive recompute	Memoization speedup	Depth
Chain ( $f_{\rm in}{=}1$ )	1	13.0	$13$	$1\times$	13.0
Balanced ( $f_{\rm in}{=}2$ )	1	38.5	$4.4{\times}10^{4}$	$1.1{\times}10^{3}$	19.5
Bushy ( $f_{\rm in}{=}4$ )	1	45.3	$1.1{\times}10^{10}$	$2.5{\times}10^{8}$	30.3

Appendix

Table 10: Shared ancestors make naive reconstruction explode. Mean node evaluations needed to reconstruct one evicted result over three seeds (lower is better). Atomic retrieval always costs one read. Memoized recursion visits each required ancestor once, while naive recursion revisits shared ancestors; “speedup” is naive cost divided by memoized cost.

Figure 7: Dependency geometry determines recovery work and latency. Left: Extra work without memoization relative to the cone-size minimum (log scale, sum , deep nodes

t{\geq}32

). Repeated shared-ancestor traversal grows from

1\times

for chains to

2.5{\times}10^{8}

for bushy DAGs. Right: Cone size (total recompute volume) versus cone depth (longest sequential chain) for every non-leaf node. The chain lies on the diagonal, while balanced and bushy DAGs lie above it, dissociating volume from latency.

Model	Success rate $\uparrow$	Read overhead (successes; $1.0$ optimal)	Off-cone reads $\downarrow$	Early stops $\downarrow$
Gpt56Reasoning	100%	1.000	0	0
ClaudeOpus46	100%	1.000	0	0
ClaudeHaiku45	100%	1.000	0	0
Gpt41Mini	50%	1.000	1	2

Appendix

Table 11: Successful agents traverse efficiently; failures stop early. Model-executed reconstruction probes on sum DAGs. The harness performs arithmetic, so reads isolate traversal behavior. Read overhead is reads divided by the oracle minimum (1.0 is optimal; lower is not possible for a completed probe). Early stops count terminations before reconstructing the target.

Workload	Successful	Premature	Total
Stepwise Sum	32	8	40
Stepwise Maximum	18	6	24
Stepwise Top- $k$	19	5	24
Total	69	19	88

Appendix

Table 12: Expanded model-executed recovery probes. Successful probes reconstruct the target and use exactly the oracle-minimum reads; premature probes stop before the required cone is complete. Counts pool both registered fan-in conditions and all evaluated models.

Model	Architecture	Scored	Accuracy	JIT rate
GPT-5.6	No-recovery floor	6/6	0.755	–
	Scratch	6/6	0.315	1.000
	LRU	6/6	0.224	1.000
	Scratch–LRU	6/6	0.089	1.000
Claude Opus 4.6	No-recovery floor	6/6	0.804	–
	Scratch	6/6	0.274	0.963

Appendix

Table 13: Stepwise Maximum agent-managed behavior. Accuracy and just-in-time (JIT) retrieval rate pooled over

h\in\{2,4\}

. Every model–architecture row contains all six registered seed–capacity outcomes.

Policy	$h$	End-to-end accuracy	Self-consistent accuracy	Missing-reference steps
Exact window	16	$0.934\pm 0.187$	$0.997\pm 0.010$	$0.0$
LRU	16	$0.410\pm 0.126$	$0.788\pm 0.044$	$13.3$
LRU	20	$0.441\pm 0.145$	$0.903\pm 0.014$	$5.7$
LRU	32	$0.925\pm 0.185$	$0.995\pm 0.010$	$0.0$
LRU + correct restoration	16	$0.934\pm 0.187$	$0.997\pm 0.010$	$13.3$
LRU + sham restoration	16	$0.444\pm 0.063$	$0.790\pm 0.049$	$13.3$

Appendix

Table 14: RQ1 sufficient-capacity follow-up. Stepwise Sum with the three strong models (mean

\pm

population std over

3

models

\times

3

seeds). The exact-window and LRU agents use the same managed-memory action loop. Missing steps count steps with at least one required answer unavailable. Exact-window retention succeeds at the

h{=}16

requirement; LRU does not until overprovisioned to

h{=}32

, and correct restoration—unlike sham restoration—closes the gap.

Workload	Pressure $m/h$	FIFO	LRU	Theory-informed	Belady	LRU gap closed
Stepwise Sum	1.33	0.381	0.397	0.381	0.000	-0.04
	2.00	0.640	0.619	0.640	0.206	+0.05
	4.00	0.857	0.857	0.857	0.566	+0.00
Store–Recall	1.33	0.292	0.219	0.000	0.000	+0.25
	2.00	0.490	0.417	0.000	0.000	+0.15
	4.00	0.719	0.677	0.490	0.073	+0.06

Appendix

Table 15: Knowing future use matters more than recency. Miss rate (lower is better) by retention policy and pressure, averaged over three seeds with

m{=}16

. Belady is the future-aware optimum. “LRU gap closed” is the fraction of the FIFO-to-Belady gap removed by LRU:

1

matches Belady,

0

matches FIFO, and negative values are worse than FIFO. The theory-informed policy matches Belady for Store–Recall at the two sufficient-capacity settings, whereas LRU closes little or none of the gap across workloads.

Workload	Architecture	Scored	Accuracy
Store–Recall	Forced paging (unbounded)	24/24	1.000
	Mem0	24/24	0.996
	A-MEM	24/24	0.959
	Graphiti	24/24	1.000
	FIFO	24/24	0.811
	Letta	24/24	0.370

Appendix

Table 16: RQ4 architecture comparison. Agent-executed end-to-end accuracy at

m{=}8

, pooled over

h\in\{2,4\}

, four models, and three seeds. Every architecture row contains all 24 registered model–capacity–seed outcomes.

Workload	Architecture	Scored	Accuracy
Stepwise Sum	A-MEM	24/24	0.436
	Graphiti	24/24	0.767
	Letta	24/24	0.370
	Mem0	24/24	0.367
Stepwise Maximum	A-MEM	24/24	0.942
	Graphiti	24/24	0.934

Appendix

Table 17: Expanded external-memory workload coverage. Agent-executed end-to-end accuracy pooled over four models, three seeds, and the two registered capacities. All rows contain 24 effective outcomes. Running Maximum is a low-demand control, not a graded record-pressure workload.

Figure 8: One missing intermediate result can corrupt many later steps. A , Stepwise Sum degrades faster than Store–Recall at matched

m/h

. Panel A reports accuracy on scored dependency-consuming steps: all Stepwise Sum steps and RECALL steps only for Store–Recall. Table 6 instead reports Store–Recall accuracy over both STORE and RECALL steps. Bands show variation across three seed-pooled model means. B , one run has its first unavailable dependency at

t{=}14

, followed by 19 state-supply errors, 26 cascade errors, and no computation errors.

Figure 9: Reusing computed results avoids repeated recovery work. Reconstruction costs with and without reuse of shared ancestors, across 99 cones per graph type. Labels give mean cost ratios; the dashed line marks one-read retrieval. Pale bars show interquartile ranges, and error bars show bootstrap 95% confidence intervals.

Figure 10: When recovery succeeds it is read-optimal; the observed failures stop too soon. Read overhead is reads divided by the oracle minimum (1.0 is optimal). All 14 completed probes equal 1.0; crosses mark the two GPT-4.1 probes that issue Done before reading the full recovery cone. All 16 probes in the original Stepwise Sum subset are shown.

Figure 11: Future-aware retention can reduce misses. Simulated policy miss rates across workloads; Belady uses future requests. Table 15 reports the underlying values.

Figure 12: Architecture outcomes depend on both storage and execution. Agent-executed comparisons on Store–Recall, Stepwise Top- $k$ , and Full Lookup. Row labels report means and effective scored counts; crosses mark turn-limit outcomes. Equal-capacity controls and native systems are shown separately.

Cohort	Runs	Goal access	Mean peak demand	Failure AUC
Verified	4,988	92.0%	9,001	.541
CoderForge	500	99.0%	73,135	.440
OpenHands/Qwen3	67,074	57.4%	4,460	.527

Appendix

Table 18: VESTIGE semantic-action-graph results on completed software-agent runs. The graph combines observed dependencies with reference-patch sinks. Goal access is the fraction of runs with at least one such sink.

Benchmark	State entity	Goal or anchor
SWE-bench / SWE-rebench	versioned file	independent reference-patch file
$\tau$ -Bench	typed database entity	reference task state
Terminal-Bench 2.0	versioned shell path	realized trace only

Appendix

Table 19: Domain anchors for VESTIGE demand estimates. SWE uses the semantic action graph; benchmarks without a reference solution retain separate realized-state adapters and are not pooled with SWE token demand.

Test	Estimate	95% CI	$p$
Failed $\times\log_{2}$ distance	RR 1.02	[0.99, 1.05]	0.174
Failed $\times$ needed $\times\log_{2}$ distance	RR 0.951	[0.911, 0.992]	0.020
Fair-clock needed-file gap, per doubling	OR 1.18	[0.985, 1.43]	—

Appendix

Table 20: Recorded return rates differ by outcome and file relevance. The primary rate ratio comes from a task-fixed-effects Poisson model with log token exposure as offset, run-clustered errors, run-length and model controls. The fair-clock sensitivity ends at each run’s final edit of any file; its interval is a task-stratified run bootstrap.

Explore similar work

Oct 4, 2026cs.SE

StateWise: Diagnosing and Repairing Persistent Operational State Before Agent Actions

LLM agents combine reasoning, tool use, and persistent memory to support work across tasks by reusing stored operational records as premises for later actions. However, environmental or requirement changes can invalidate these records, while existing action review, provenance tracking, and clarification mechanisms may leave the underlying persistent state uncorrected. Our audit of coding-agent trajectories identifies candidate failure chains in which invalid records are reused, leading to task failures and unsafe modifications. We propose StateWise, a framework for diagnosing and repairing persistent operational state before action execution. StateWise uses record-level counterfactual replanning to identify decision-critical records, then establishes their current validity through reliability checks, read-only verification of machine-observable facts, and targeted clarification of developer-owned intent. Typed evidence grounding binds evidence to specific records and scopes, enabling persistent corrections with repair lineage. The agent then replans from the repaired state, followed by an independent state-action check before execution. We evaluate StateWise on 150 executable coding-agent cases across diverse runtime environments, workspace configurations, and repository settings, complemented by cross-model evaluations. Under corrupted persistent state, StateWise achieves 93.3% overall correctness, compared with 38.7% for the baseline agent, with no unsafe actions. Component ablations, multi-task experiments, and transfer evaluations further demonstrate effective recovery, persistent corrections, and transferability across repositories and tool interfaces.

Yongyuan Peng, Zhou Feng, Tongying Wu +5

Xi’an Jiaotong University, China · Zhejiang University, Hangzhou, China

Persistent State Automated Program Repair Agent Loop

Ask PDF

Sep 28, 2026cs.OS

Planarian: Managing Agent State with Statepoints

LLM agents solve complex tasks by iteratively changing files, invoking local tools, and interacting with remote services, which modifies state across their local environment and remote services. Today, agents and users must manage these changes explicitly, whether reverting exploratory actions or recovering from erroneous ones. Doing so safely requires coordinated actions, yet current agent harnesses lack unified abstractions and mechanisms for managing local and remote state consistently and efficiently. We describe Planarian, an agent runtime with state management that enables agents and users to recover from erroneous actions and explore alternative executions over consistent local and remote environment state. Planarian introduces the abstraction of agent statepoints, which are consistent, restorable point-in-time versions of the environment state. Planarian exposes three state-management primitives to agents and users: (i) snapshot creates a new statepoint spanning local and remote state without requiring external services to support checkpoints: it relies on efficient incremental process and file system snapshotting to capture local sandboxed state, and transparently records compensating actions to undo remote state changes; (ii) rollback restores the environment to a previous statepoint by reverting to a prior local checkpoint and replaying compensating actions for remote state changes; and (iii) fork creates multiple isolated branches from a statepoint, enabling the agent to explore alternatives in parallel. We show that Planarian enables agents to undo mistakes and explore alternatives in parallel, improving task quality by up to 15x, and allows users to recover from erroneous actions with only 3% overhead.

Jinnan Guo, Hao Mark Chen, Kapil Vaswani +2

Imperial College London · Indian Institute of Science Bangalore · Microsoft Security Response Center

State-Tracking Morphogenesis

Ask PDF

Jun 4, 2026cs.AI

Beyond Semantic Organization: Memory as Execution State Management for Long-Horizon Agents

LLM-based agents increasingly tackle long-horizon tasks with interdependent decisions, where each action reshapes future constraints and intermediate errors can cascade. Existing RAG and agent memory systems organize histories by semantic similarity, retrieving content-relevant entries at decision time. We argue that this design mismatches execution-state dependencies: it fragments decision trajectories and mixes valid and erroneous traces, hindering coherent state reconstruction and error isolation. We propose MAGE (Memory as Agent-Guided Exploration), an active execution-state manager that stores interactions in a hierarchical state tree. The agent derives its state from the active root-to-current path, combining subgoal summaries, recent traces, and hints from prior branches. Four coupled operations maintain the tree: Grow records new traces, Compress summarizes completed subgoals, Maintain validates summaries, and Revise restores a target boundary and resumes on a new branch. This design bounds context growth while preserving state integrity and isolating flawed segments from the active path. Experiments on MemoryArena show that MAGE improves the average task success rate by 7.8--20.4 pp over baselines, while reducing token consumption by 55.1%.

Yaoqi Chen, Haibin Lai, Yuru Feng +12

University of Science and Technology of China · Microsoft · University of California, San Diego +1

Long-Term Agent Memory Long-Horizon Agents Long-Horizon Task Planning Peak Memory

Ask PDF