PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Nikita Mehrotra, Ashish Tiwari, Priyanshu Gupta, Sumit Gulwani

arXiv:2609.32687v2cs.AI

TL;DR

Long-running agents must preserve information that later steps depend on, but available capacity alone does not ensure that the needed information remains accessible. The paper defines EIR, tests retention and recovery with LACUNA, and measures real-task dependencies with VESTIGE. Restoring missing results repairs affected recall answers, while failed software-agent runs show a steeper distance-related decline in solution-relevant rereading.

  • Problem

    Long-running agents may lack information required by later operations even when they have ample context capacity and can perform those operations.

    Source: §1 · p. 1

  • Method

    The paper defines EIR as a lower bound on accessible information, uses LACUNA to vary information demand and access independently of operation difficulty, and applies VESTIGE to execution traces.

    Source: §1 · p. 2, §2 · p. 2

  • Results

    100% of affected Store–Recall recall steps were answered correctly after restoring the required result across four models, versus 0% with equal-length irrelevant information and 11.3% without injection.

    Source: §4.1 · p. 6

  • Takeaways & Limitations

    EIR is a worst-case lower bound rather than a per-run failure predictor; outcomes also depend on retention, retrieval, and model capability.

    Source: §5 · p. 8

    LACUNA omits some realistic content priors and per-step difficulty, exact EIR requires a workload contract and assumes unrestricted encoding, and real traces mix memory, capability, exploration, and tool-use failures.

    Source: §5 · p. 8

Abstract

from arXiv · show

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.

1 INTRODUCTION

Long-running agents can fail when a later operation lacks information omitted from earlier context, even when they have ample capacity and can perform the operation. The paper defines EIR, tests missing-information effects with LACUNA, and measures dependencies in real tasks with VESTIGE.

1 INTRODUCTION

  • EIR defines a lower bound on information from earlier steps that must remain accessible for correct completion.It depends on what later steps may require and can access, not on how the agent represents that information.Source: §1 · p. 2
  • In 3,592 OpenHands executions, peak demand is not significantly associated with failure after adjustment for execution length and independently estimated task difficulty (OR 1.016 per demand doubling, p = .191).The paper frames EIR as a foundation for measuring required state and recovery cones as a way to describe reconstruction work.Source: §1 · p. 2
  • Across four frontier models, restoring the exact missing result raises affected-step accuracy to 100%, versus 0% for equal-length irrelevant information and 11.3% without injection.LACUNA varies information demand and access separately from individual-operation difficulty.Source: §1 · p. 2
  • Across 4,987 SWE-bench Verified runs, failed executions show a steeper distance-related decline in solution-relevant rereading, with an interaction rate ratio of 0.951 per token-distance doubling.VESTIGE builds semantic action graphs from execution traces to measure dependencies when tasks provide no dependency graph.Source: §1 · p. 2

2 EXECUTION INFORMATION REQUIREMENT

EIR measures the minimum information from a completed history that must remain accessible so the remaining work can produce correct outputs. It groups histories by whether they require the same future responses under the workload contract.

2 EXECUTION INFORMATION REQUIREMENT

  • EIR is the minimum information that must pass from earlier execution to the remaining work, preserving distinctions that can change required responses.It is a worst-case, zero-error requirement; any compression is permitted if it preserves those distinctions.Source: §2 · pp. 2–3
  • For the timezone example, six histories yield four distinct required answer pairs, so retaining which pair applies requires 2 bits.Different exploration paths can share a representation when they require the same file and datetime answer.Source: §2 · p. 2, Figure 2 · p. 3
  • The workload contract specifies possible histories, future inputs, required outputs, and information sources accessible after an execution cut.Histories are continuation-equivalent when every allowed future input requires the same output for either history.Source: §2 · p. 3
  • For a finite set of N_t continuation-equivalence classes, the minimum fixed-length binary representation is ⌈log2 N_t⌉ bits.A sufficient state must distinguish classes with different future responses; this information bound does not bound the computation needed to encode or use the state.Source: §2 · p. 3
  • Information pressure compares EIR with available storage capacity; pressure above 1 means storage cannot distinguish every required class, while pressure at or below 1 only makes sufficient storage possible.Success still requires preserving the right information and computing correctly.Source: §2 · p. 3

3 LACUNA: A FRAMEWORK FOR EVALUATING AGENT MEMORY

LACUNA generates multi-step tasks with known dependencies and varies information demand, retention, and recovery independently of individual-operation difficulty. Its controls distinguish information loss from computation and protocol errors.

3 LACUNA: A FRAMEWORK FOR EVALUATING AGENT MEMORY

  • LACUNA varies access to earlier results on a fixed task instance and tests whether restoring missing information repairs errors.The framework generates task instances with known correct outputs and dependencies.Source: §3 · p. 4

3.1 TASK CONSTRUCTION

  • Tasks are directed acyclic graphs whose nodes are operations and whose edges identify earlier results used by later steps.Six workloads span aggregation, state tracking, candidate maintenance, delayed retrieval, and interleaved memory update and recall; the settings do not define universal workload formulas.Source: §3.1 · pp. 4–5, Table 1 · p. 5

3.2 CONTROLLING INFORMATION AVAILABILITY AND RECOVERY

  • The framework distinguishes required state, retained state, and available state, and controls retention through either a recent-result window or agent-managed memory.Recovery conditions set budgets for direct retrieval and recomputation; dependencies needed to reconstruct a result form its recovery cone.Source: §3.2 · p. 5

3.3 EVALUATION CONTROLS

  • Full-information controls test computation capability, while restoration-versus-irrelevant-value comparisons test whether missing information causes an error rather than added prompt length.LACUNA distinguishes computation, state-supply, and cascade errors, and records both step and final-task accuracy; interface checks found no violations across 18,068 checks.Source: §3.3 · p. 6

4 RESULTS

The results show that unavailable required information can cause errors, while reconstruction cost, retention choices, and end-to-end system behavior shape whether agents recover. VESTIGE also measures distance-related rereading patterns across real software-agent runs.

4.1 RQ1: DOES UNAVAILABLE REQUIRED STATE PREDICT AND CAUSE EXECUTION ERRORS?

  • 100% of affected Store–Recall recall steps were answered correctly across four models after restoring the required result, versus 0% with an equal-length irrelevant value and 11.3% without added information.The Stepwise Maximum replication scored 1.000 with exact restoration, compared with 0.642 without restoration and 0.714 with irrelevant information.Source: §4.1 · p. 6, Figure 4 · p. 7

4.2 RQ2: WHAT DETERMINES RECONSTRUCTION COST?

  • 13.0, 38.5, and 45.3 node evaluations were the mean reconstruction work with reuse on tested chain, balanced, and bushy graphs; without reuse, bushy-graph work rose to approximately 1.1×10^10.In 88 agent-executed probes, all 69 successful recoveries used the minimum number of reads, while 19 stopped before reconstructing the target.Source: §4.2 · p. 7

4.3 RQ3: HOW DOES RETENTION BEHAVIOR CHANGE UNDER INFORMATION PRESSURE?

  • With Zipf-distributed queries and h = 4, Full Lookup hit rates were 0.493 for LFU, 0.438 for LRU, and 0.111 for the fixed policy; uniform queries showed no adaptive advantage.On Store–Recall, key–value storage improved accuracy over text scratch storage by 25.9–33.0 percentage points across four models, while model-directed scratch storage had mixed effects versus LRU.Source: §4.3 · p. 7

4.4 RQ4: HOW CLOSELY DO ARCHITECTURES APPROACH THE EIR FLOOR?

  • At h = 16, Stepwise Sum accuracy was 0.410 for LRU and 0.934 for exact-window retention; restoring LRU’s missing results raised its score to 0.934, versus 0.444 with irrelevant information.On Store–Recall, system-level results ranged from 1.000 for unbounded forced paging and Graphiti to 0.370 for Letta; these are not equal-capacity policy comparisons.Source: §4.4 · p. 7

4.5 VESTIGE: WHAT CAN BE MEASURED IN REAL TASKS?

  • Across 72,562 software-agent trajectories, failed runs had a steeper distance-related decline in solution-relevant rereading: the failed-versus-resolved reread-rate ratio was multiplied by 0.951 per token-distance doubling.VESTIGE constructs semantic action graphs from traces; adjusted peak demand was not significantly associated with failure in the 3,592-run OpenHands cohort (OR 1.016 per doubling, p = .191).Source: §4.5 · p. 8

5 DISCUSSION AND LIMITATIONS

EIR measures a worst-case information lower bound rather than predicting individual failures, while real-task demand estimates and memory-system outcomes have important scope limits. The discussion recommends task-aware retention and recovery while noting limitations in the controlled workloads and trace data.

EIR scope

  • EIR is a worst-case lower bound, not a per-run failure predictor; outcomes also depend on retention, retrieval, and model capability.LACUNA separates retention-policy errors from end-to-end failures involving model outputs, tool actions, or computation.Source: §5 · p. 8

Memory-system results

  • Memory-system scores combine each system’s interface, model decisions, and answer submission, so they do not establish a universal product ranking.The runs show that task-aligned retention and reliable access are measurable, and that storage availability alone does not ensure success.Source: §5 · p. 8

VESTIGE scope

  • VESTIGE measures observed goal-connected use across 72,562 SWE, 318 τ-Bench, and 166 Terminal-Bench trajectories, not the minimum demand of every correct solution.Exported logs cannot always establish whether clipped lines were required.Source: §5 · p. 8

Design implications and limitations

  • Memory systems should retain state by predicted future use, track what leaves resident memory, and price retrieval by dependency work.LACUNA omits some realistic content priors and per-step difficulty; exact EIR requires a workload contract, and capacity calibration is workload-specific.Source: §5 · p. 8

6 RELATED WORK

The related work motivates task-aware memory and identifies a gap in diagnosing unavailable required information. EIR and LACUNA address that gap by measuring task requirements and controlling information access.

Predictive and task-relevant state

  • EIR uses continuation-equivalence at a finite execution boundary to measure the states needed for correct continuation under a specified workload, without a distribution over prefixes.Unlike average-case mutual-information frameworks, the future computation determines which prefixes must remain distinct.Source: §6 · p. 9

Long-context evaluation and agent memory

  • Existing long-context and memory evaluations can localize some problems, but do not jointly identify required information at a failed step and test whether its absence caused failure.LACUNA controls what later steps need, what agents can access, and whether missing information can be reconstructed.Source: §6 · p. 9

Context compaction and task-aware memory

  • Context-compaction and decision-centric approaches study memory construction or size–performance trade-offs, while EIR specifies task-required information and LACUNA diagnoses state-unavailability errors.The framework holds trajectory length, graph structure, and per-step difficulty fixed.Source: §6 · p. 9

Recomputation and information lower bounds

  • Liveness, pebbling, and rematerialization motivate recovery-cost analysis, while streaming and communication lower bounds support EIR requirements for arbitrary labelled access, aggregation, and extremum workloads.Source: §6 · p. 9

7 CONCLUSION

The conclusion connects task information demand with retention, recovery, and failures in real agent executions.

7 CONCLUSION

  • EIR, LACUNA, and VESTIGE connect task demand to retention, recovery, and failures in real agent executions.Source: §7 · p. 9

REPRODUCIBILITY STATEMENT

The reproducibility statement describes an archive of code and validation materials, while the appendix proof section outlines exact EIR results and a finite-enumeration procedure with computational costs.

REPRODUCIBILITY STATEMENT

  • The supplementary archive includes LACUNA and trajectory-analysis code, tests, aggregate results, theory artifacts, figure scripts, checksums, and validation instructions.Raw public trajectories are not redistributed; the archive identifies public dataset sources and processing scripts.Source: REPRODUCIBILITY STATEMENT · p. 12

A PROOFS FOR EXACT EIR WORKLOADS

A.1 EXACT EIR BY FINITE ENUMERATION

  • Finite enumeration takes prefix states, future input sequences, fixed information, and a correct-output evaluator, then forms signatures from outputs across the sequences.Source: §A.1 · p. 12
  • The procedure returns log2 of the number of distinct signatures; it requires |Xt| |Ut| evaluations and can be computationally expensive.When enumeration is impractical, an exact result requires a continuation-sufficient representation and a matching lower bound on distinguishable context states.Source: §A.1 · p. 12

A.2 STEPWISE SUM

The workload contracts determine which earlier values must remain accessible: Stepwise Sum requires its eligible online window, while other workloads require only the state relevant to their future queries. The appendix also specifies the experimental configurations used for the controlled comparisons.

A.2 STEPWISE SUM

  • At saturated interior cuts, Stepwise Sum requires 16 log2(104) ≈ 212.603 bits, or 213 jointly coded bits; this bound assumes the declared online contract and no accessible prefix copy.The task reveals references only as each step arrives; 224 bits are needed if each scalar uses its own 14-bit slot. The theorem is a worst-case family-level bound, not the entropy of the finite seeded sample.Source: §A.2 · pp. 13–14

A.3 RUNNING MAXIMUM

  • For a suffix whose sole use of a prefix is its final maximum, the EIR is b bits because retaining the maximum suffices.Reversing the order gives the corresponding minimum result.Source: §A.3 · p. 14

A.4 STEPWISE TOP-K

  • Stepwise Top-k has no claimed numeric EIR or pressure: its continuation classes are characterized by bisimulation, but the evaluated state space is not directly enumerable.Exhaustive bisimulation is practical only for reduced alphabets and windows.Source: §A.4 · p. 14

A.5 STORE–RECALL

  • Store–Recall requires |Rt| log2 q bits under full support over eligible future recall ids, preserving the labelled STORE values that future recalls may select.Rt contains the earlier STORE ids eligible for the first future recall.Source: §A.5 · pp. 14–15

A.6 FULL LOOKUP

  • Full Lookup requires mb bits when m labelled coordinates vary independently and future queries may select any coordinate.A differing coordinate can be queried to distinguish any two prefix vectors.Source: §A.6 · p. 15

B EXPERIMENTAL CONFIGURATIONS AND SETTINGS

  • The appendix specifies 64-step, four-digit, modulo-104 tasks and registered grids; model comparisons reuse byte-identical seeded instances.The listed graph seeds are {1, 2, 3}; the grid identifies parameters including dependency window, retained records, task length, and fan-in.Source: B EXPERIMENTAL CONFIGURATIONS AND… · p. 15, §B.3 · pp. 16–17

B.1 MODELS AND DECODING

  • Model handles were provider-qualified; temperature zero was sent only when supported, while other decoding settings followed provider defaults.Top p, penalties, and output-token limits were not overridden.Source: §B.1 · p. 15, Table 2 · p. 15

B.2 TASK RUNTIME AND INTERFACES

  • The appendix records client, command, and task timeouts plus retention interfaces, retry limits, and action ceilings.Transport or command retries address timeouts, not incorrect model answers; Controlled Retention permits at most 20 recover/answer decisions per step.Source: §B.1 · p. 15, §B.2 · pp. 15–16

B.4 MEMORY ARCHITECTURES AND CAPACITY CONTRACTS

The appendix distinguishes equal-capacity memory comparisons from native systems with uncalibrated storage, and documents endpoints, validity checks, and exact EIR calculations. Full-information controls separate unaided computation limits from information-loss results.

B.4 MEMORY ARCHITECTURES AND CAPACITY CONTRACTS

  • Strict-panel policies enforce h complete answer records, but Belady sees future references and is an offline, non-causal upper bound.Native systems without auditable or enforceable record limits are reported separately rather than treated as equal-capacity comparisons.Source: §B.4 · p. 18
  • The retrieval-budget panel measures interface capacity, not total backend storage or each product’s eviction policy; its partial matrix is excluded from headline aggregates.Letta is excluded because its persistent agent can bypass the adapter-level retrieval gate; only 33 of 108 ledger rows were persisted.Source: §B.4 · p. 18

B.5 ENDPOINTS, AGGREGATION, AND UNCERTAINTY

  • The evaluation reports end-to-end accuracy and other behavioral endpoints; controlled results use stated model–seed summaries, while real-trajectory analyses use distinct observational models.Information-loss attribution excludes model–workload cells below the 0.75 full-information mean-accuracy floor.Source: §B.5 · p. 18

B.6 VALIDITY, EXCLUSIONS, AND PROVENANCE

  • A controlled result is excluded for specified provenance, graph, exposure, pricing, or infrastructure failures; the interface audit passed 18,068 checks across 100 instances.A bounded run with a valid terminal action record remains a behavioral outcome even if it reaches the action ceiling.Source: §B.6 · pp. 18–19

C.1 FULL-INFORMATION CAPABILITY CONTROL

  • 1.000 deterministic-calculator accuracy across every tested cell confirms that the listed exclusions reflect unaided execution capability, not information availability.All three stronger models clear the 0.75 floor in every tested family; Gpt41Mini falls below it on Stepwise Sum, both maximum workloads, and Stepwise Top-k, but clears Store–Recall.Source: §C.1 · p. 19, Table 5 · p. 19
  • Top-k computation-error rates are 22.4% (Haiku), 6.9% (Opus), and 8.2% (GPT-5.6), separating its full-information deficit from unavailable-state evidence.Cascade rates are at most 2.3%; the deterministic-calculator control removes the computation deficit.Source: §C.1 · p. 19

C.2 EXACT EIR CALCULATIONS BY WORKLOAD CONTRACT

  • Exact final-output EIRs are b bits for Running Maximum, graph- and cut-dependent for Stepwise Maximum, and about 212.6 bits for saturated Stepwise Sum.For Stepwise Maximum, full-window cuts range from 175.3 to 194.7 bits and peak EIR from 190.2 to 194.7 bits; Store–Recall peak interior EIR is 8b after odd cuts and 7b after even cuts.Source: §C.2 · p. 20
  • Exhaustive enumeration for reduced alphabets and windows matched the theorem class counts at every tested configuration, including dedicated Stepwise Sum cases.The enumeration suite covers q ∈ {2, 3, 4} and m ∈ {0, ..., 4}.Source: §C.2 · p. 20

C.3 RQ1: DOES UNAVAILABLE REQUIRED STATE PREDICT AND CAUSE EXECUTION ERRORS?

The RQ1 experiments vary retained information while holding tasks fixed, finding that missing required state predicts errors and that exact restoration repairs them. In Stepwise Sum, dependency structure then amplifies unrepaired misses into persistent downstream errors.

C.3 RQ1: DOES UNAVAILABLE REQUIRED STATE PREDICT AND CAUSE EXECUTION ERRORS?

  • Retention-ratio degradation was strictly monotone for Stepwise Sum and Store–Recall, while Stepwise Top-k was flat at low ratios before declining.The non-predictive retention-ratio null was rejected for Stepwise Sum and arbitrary-access at p < 0.001; Table 6 reports the evaluated accuracy settings.Source: §C.3 · p. 21, Table 6 · p. 21
  • Stepwise Maximum accuracy fell from 1.000 at h = 16 to 0.570 at h = 4, although a missing operand could be irrelevant when another available operand was already maximal.Its pooled intermediate accuracies were 0.836 at h = 12 and 0.770 at h = 8.Source: §C.3 · p. 21
  • Store–Recall’s observed accuracy generally exceeded its window-miss prediction, with paired model-cell end-to-end residual mean absolute error of 0.040.The comparison shows the prediction captures the pressure-response shape without implying exact equality.Source: §C.3 · p. 22, Figure 5 · p. 22
  • 1.000 accuracy on affected Store–Recall miss steps followed exact restoration, versus 0.000 with a length-matched sham and 0.113 without injection across four models.The oracle–sham repair effect was +1.000; the Stepwise Maximum replication also reached 1.000 full-trajectory accuracy with exact restoration, versus 0.642 control and 0.714 sham.Source: §C.3 · pp. 22–23, Table 8 · p. 23, Table 9 · p. 23
  • Stepwise Sum’s first divergence matched its first window miss in all 27 pressure trials, while alignment was 0.67 for Store–Recall and 0.18 for Stepwise Top-k.Missing values can sometimes be guessed or be irrelevant to a maximum; Top-k’s computation confound prevents attributing its first-error timing solely to information loss.Source: §C.3 · p. 23

C.3.1 HOW DO UNREPAIRED INFORMATION GAPS CASCADE?

  • At Pint=2, Stepwise Sum accuracy was 0.161 versus the no-cascade prediction of 0.36, as incorrect intermediates propagated to downstream steps.The resulting accuracy was approximately 1/2.2 of the no-cascade prediction.Source: §C.3.1 · p. 23, Figure 6 · p. 24
  • Matched at the operational ratio, Stepwise Sum exceeded Store–Recall accuracy gaps by 0.612 at m/h = 2 and 0.578 at m/h = 4; these cross-family differences are descriptive, not causal.Both workloads have comparable linear online requirements, but Stepwise Sum errors can propagate through later dependencies.Source: §C.3.1 · pp. 24–25
  • In one eligible h=12 Stepwise Sum trajectory, 19 of 64 steps were direct state-supply errors and 26 were downstream cascades, with no independent computation errors.The first error coincided with the first miss at t⋆=14.Source: §C.3.1 · p. 25

C.4 RQ2: WHAT DETERMINES RECONSTRUCTION COST?

RQ2 relates reconstruction work to the dependency cone, while agent-executed probes show successful traversal can be efficient but may stop before recovery finishes. RQ3 examines retention under pressure, finding that outcomes depend on model capability, storage medium, workload, and retrieval behavior.

C.4 RQ2: WHAT DETERMINES RECONSTRUCTION COST?

  • Recursive recovery cost equaled cone size: 13.0 node evaluations for chains, 38.5 for balanced graphs, and 45.3 for bushy graphs, independent of miss pressure.Atomic retrieval costs one step regardless of topology.Source: §C.4 · p. 25
  • Without memoization, reconstruction cost rose from 13 evaluations for chains to 4.4×10^4 for balanced graphs and 1.1×10^10 for bushy graphs, yielding 2.5×10^8 speedup in the bushy case.Shared-ancestor reuse makes the memoization benefit geometry-dependent.Source: §C.4 · p. 25, Figure 7 · p. 26
  • Cone size and depth dissociated: matched-size cones had depths 25 versus 40, while matched-depth cones had sizes 21 versus 48.Cost tracks cone size; depth bounds the critical path under parallel execution, while fully sequential latency tracks total work.Source: §C.4 · p. 25, Figure 7 · p. 26
  • In 88 recovery probes, every successful probe used exactly the oracle-minimum reads, while 19 probes stopped before reconstructing the target.The harness performed arithmetic, isolating traversal behavior; the observed failure was incomplete recovery rather than excess reads.Source: §C.4 · pp. 25–26, Table 11 · p. 26

C.5 RQ3: HOW DOES RETENTION BEHAVIOR CHANGE UNDER INFORMATION PRESSURE?

  • On Zipf Full Lookup at h = 4, LFU, LRU, and fixed retention had hit rates 0.493, 0.438, and 0.111; uniform streams showed no adaptive advantage.Mean query accuracy remained at least 0.998 in every cell because each miss received one atomic recovery read.Source: §C.5 · p. 27
  • Recovery-enabled Stepwise Maximum accuracy declined from 1.000 to 0.854 as m/h increased from 1 to 8, while mean recovery reads rose from 9.3 to 322.3.This adaptive-retrieval experiment differs from the no-recovery retention sweep.Source: §C.5 · p. 27
  • On the random-DAG Stepwise Maximum workload, pooled accuracy was 0.654 for the no-recovery floor, 0.223 for Scratch, 0.222 for LRU, and 0.072 for Scratch–LRU.Retrieval was predominantly just-in-time, but additional actions did not improve accuracy in this workload.Source: §C.5 · p. 27, Table 13 · p. 28
  • Model-driven retention helped capable models, but storage medium had a consistent advantage: K-V LRU exceeded text Scratch-LRU by about 0.29 across models.Haiku struggled with model-driven eviction, while Opus and Gpt56Reasoning outperformed floor control with Strategic Scratch.Source: §C.5 · pp. 27–28

C.6 RQ4: HOW CLOSELY DO ARCHITECTURES APPROACH THE EIR FLOOR?

In controlled tests, sufficient capacity did not guarantee that retention policies preserved required state, while restoring missing results closed the measured accuracy gap. VESTIGE uses execution traces to estimate task-relevant information demand, but its retrospective signal is not certified EIR.

C.6 RQ4: HOW CLOSELY DO ARCHITECTURES APPROACH THE EIR FLOOR?

  • At Pint=1.33 (h=12, m=16), FIFO misses on 38.2% of consuming steps while hindsight Belady misses on zero for the realized graphs.Belady uses future-reference information, so this result does not show that the same capacity suffices for every online continuation.Source: §C.6 · pp. 28–29
  • At h = 16, exact-window retention scores 0.934 versus LRU’s 0.410; correct restoration raises LRU to 0.934, while sham restoration reaches 0.444.The comparison uses the same managed-memory action loop; the table caption describes exact-window success at the h=16 requirement and LRU’s failure until overprovisioned.Source: Table 14 · p. 29, §C.6 · p. 29
  • At h=m=16, LRU incurs a 21.2% miss rate while FIFO has zero; across workloads, LRU closes little or none of the FIFO-to-Belady gap.The simulations attribute this pattern to recency failing to predict references within the sum-task span window.Source: §C.6 · p. 29, Table 15 · p. 30
  • The theory-informed policy matches Belady’s zero miss rate for Store–Recall at ρnom ≤2, while LRU does not improve on FIFO across the other workload families.Belady first exceeds 5% misses at ρ⋆ nom=1.6 for Stepwise Sum, 2.0 for Stepwise Top-k, 2.7 for Stepwise Maximum, and 4.0 for Store–Recall.Source: Table 15 · p. 30, §C.6 · p. 30
  • In Store–Recall, unbounded forced paging reaches 1.000, Mem0 0.996, FIFO 0.811, and Letta 0.370; the same ordering weakens but persists on Stepwise Top-k.On Stepwise Top-k, unbounded forced paging scores 0.501, the no-recovery floor 0.342, Mem0 0.289, and FIFO 0.283.Source: §C.6 · p. 30, Table 16 · p. 31

D VESTIGE: INFORMATION-DEMAND MEASUREMENT FOR REAL TASKS

  • VESTIGE constructs a semantic action graph from observed action–state dependencies and reference-patch sinks, then aggregates graph signals into task-demand profiles and per-run access measures.For software tasks, the trace identifies file states read, written, and later used; reference-patch files identify goal-connected actions.Source: D VESTIGE: INFORMATION-DEMAND… · p. 32, §D.1 · p. 32, Table 18 · p. 33

D.1 THE VESTIGE SEMANTIC ACTION GRAPH

  • VESTIGE’s retrospective graph identifies state used in the recorded continuation, not state necessary for every correct solution; zero measured demand can indicate missing graph coverage.The signal is based on observed reference-solution-connected activity rather than certified continuation classes.Source: D VESTIGE: INFORMATION-DEMAND… · p. 32, §D.1 · p. 33
  • Across 72,562 software-agent trajectories, retrospective demand alone is not a strong failure classifier, with failure AUCs of .541, .440, and .527 across the three datasets.In the OpenHands clipping cohort, demand’s adjusted association with failure was not significant (OR 1.016 per demand doubling, 95% CI [0.992, 1.041], p = .191).Source: §D.1 · p. 33

D.2 SOFTWARE-AGENT TRAJECTORIES: VERIFIED, CODERFORGE, AND OPENHANDS

VESTIGE reconstructs dependencies from real execution traces, where failed runs show a steeper distance-related decline in rereading solution-relevant files. Cross-domain adapters and execution traces illustrate distinct ways that missing information, unrecovered inputs, and early stopping can shape agent behavior.

D.2 SOFTWARE-AGENT TRAJECTORIES: VERIFIED, CODERFORGE, AND OPENHANDS

  • VESTIGE builds semantic action graphs from 4,988 SWE-bench Verified trajectories, using observed dependencies and reference-patch files as an operational demand estimate, not a universal requirement.The reference patch anchors one certified solution, not every possible correct continuation.Source: §D.2 · p. 33
  • Clipped views omitted specific gold-changed old lines, but those omissions do not establish that the lines were necessary or caused failure.The OpenHands clipping audit also finds output-level supply limits, not proof that clipping caused failures.Source: §D.2 · p. 34
  • In OpenHands, recovered runs had 48.5% raw success versus 35.8% for never-recovered runs, but the association was null after task adjustment (OR 0.89, 95% credible interval [0.67, 1.19]).Recovery is post-clipping behavior, so the adjusted estimates remain descriptive.Source: §D.2 · p. 34
  • After task-difficulty adjustment, VESTIGE demand was not associated with failure in the selected clipping cohort (OR 1.016, 95% CI [0.992, 1.041], p = .191), and available downstream measures supported no mediation mechanism.The demand estimate uses completed trajectories and is not a clean pre-run causal exposure.Source: §D.2 · p. 35
  • RR 0.951 per token-distance doubling: failed runs’ reread rate for gold-needed files falls an additional 4.9% relative to resolved runs and other files.Needed files are generally reread more often, so this is a relative attenuation, not an absence of retrieval.Source: §D.2 · p. 35, Table 20 · p. 36

D.3 CROSS-DOMAIN ADAPTERS: TRANSACTIONAL ENTITIES AND SHELL FILES

  • Adapters estimate later-used demand from 318 τ-Bench entity traces and 166 Terminal-Bench shell traces, but their native units remain separate from software-file token costs.The τ-Bench entity-count proxy is not exact EIR; Terminal-Bench demand is a realized trace audit, not normative demand.Source: §D.3 · p. 36

D.4 MECHANISTIC EVIDENCE ACROSS RQ1–RQ3

  • Traces distinguish continuing without visible recovery, recognizing a missing input but proceeding, and stopping during recovery; each can leave execution incomplete or incorrect.The examples show behavior, not what an agent internally recognized.Source: §D.4 · pp. 36–37
  • Once an incorrect result is retained, later steps can reproduce submitted answers from incorrect inputs, creating cascade errors even without a new missing input.The cross-workload comparison is consistent with this mechanism but is not itself a causal estimate.Source: §D.4 · p. 37

Related papers

Loading 2609.32687v2…