acceptodds
Under review as a conference paper at ICLR 2027

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

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 constructs semantic graphs from agent execution traces to estimate information requirements retrospectively. Together, these contributions provide a basis for evaluating whether agents preserve and recover the information their tasks require.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Agent memory, context failures, stateful agents, information-theoretic evaluation, long-horizon reasoning.

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_zE7gOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper introduces the Execution Information Requirement (EIR), a lower bound on the information an agent must retain to guarantee correct continuation under a specified workload. It also presents LACUNA, a controlled framework for studying state loss and recovery, and VESTIGE, a retrospective estimator of relevant information in completed agent trajectories. The experiments show that restoring a missing result can repair errors and that retention and recovery behavior affect long-running execution.

Critical strengths
  1. The paper brings information requirements, state retention, and recovery into a coherent framework. Its comparison between restoring the exact missing result and supplying equally long irrelevant information supports the claim that unavailable required state can cause execution errors.
Critical weaknesses
  1. The connection between the theoretical definition and the practical estimate is insufficiently established. EIR measures the minimum information needed to guarantee correct continuation for every allowed future, whereas VESTIGE measures file states used later in one completed trajectory. The paper establishes neither a bound between these quantities nor another precise relationship.

  2. The experiments do not sufficiently validate VESTIGE as an estimator of required information. In the state-restoration experiments, the framework identifies the required result in advance and supplies it directly. These experiments demonstrate the effect of missing state, but they do not show that VESTIGE can accurately identify or quantify the information an agent needs.

  3. The presentation of key experimental results in the main text is insufficiently consolidated. Although the paper includes figures and tables in the appendix, results on recovery cost, retention policies, and architecture comparisons are mostly reported as numbers in prose. A summary figure or table comparing experimental settings, controls, and outcomes would make it easier to assess how each method is validated. The main text also exceeds nine pages by two lines: the conclusion continues onto page 10.

Questions for authors
  1. Is there a precise, testable relationship, such as an upper or lower bound, between VESTIGE's retrospective estimate and theoretical EIR?

  2. Can the authors evaluate VESTIGE's accuracy in identifying required state and estimating information demand on tasks for which the required information can be determined independently?

Reviewer_D6UCOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

This paper investigates the information requirements of long-horizon agents and examines how information loss affects task success rates. To this end, the authors first leverage Myhill–Nerode equivalence to introduce a novel measure called the Execution Information Requirement (EIR), along with a formal definition and a procedure for calculating it. The authors then develop LACUNA, a small-scale controlled benchmark consisting of mathematical problems with known state dependencies. Using LACUNA, they evaluate the effects of information loss under different memory capacities and retention policies. Furthermore, the authors propose VESTIGE, a framework for analyzing real-world agent trajectories. VESTIGE constructs an approximate dependency graph based on file read–write relationships and uses this graph to estimate EIR. The authors further investigate the correlation between the estimated EIR and task success rates.

Critical strengths

This paper leverages Myhill–Nerode equivalence to define and calculate EIR, which is an interesting and theoretically well-motivated approach. By grouping execution histories that exhibit equivalent future behavior into the same equivalence class, the authors provide an information-theoretic perspective on the minimum amount of information required to ensure correct future execution. This formulation goes beyond simpler measures such as context length or the size of historical data, offering a more principled way to characterize agent memory requirements. Overall, this provides a relatively rigorous theoretical foundation for studying agent memory requirements and offers a valuable formal perspective for further investigating memory capacity and information pressure.

Critical weaknesses
  • The dependency graph construction in VESTIGE lacks formal soundness and completeness guarantees.

The authors assume that each file write depends on the files that were previously read. However, this operation-order-based heuristic may not accurately capture the actual data dependencies in agent execution. In particular, it may introduce spurious dependencies while overlooking some genuine dependencies. Since the subsequent backward slicing and information requirement estimation rely heavily on the constructed graph, inaccuracies in this graph could affect the reliability of the resulting analysis. It would be helpful if the authors could provide a more thorough discussion or validation of the soundness and completeness of this approximation. This concern is particularly relevant given the rigorous theoretical definition of EIR presented earlier in the paper, as the lack of corresponding guarantees in VESTIGE may somewhat weaken the theoretical consistency of the overall approach.

  • The relationship between the EIR estimation in VESTIGE and its theoretical definition could be better established.

The theoretical EIR is defined in terms of continuation-equivalence classes, characterizing the minimum amount of information required to ensure correct future execution. In contrast, VESTIGE approximates this requirement by summing the token counts of relevant file versions. However, file size may not necessarily reflect the amount of information that needs to be retained. For example, a large file may contain only a small amount of information that is relevant to future tasks. While this approximation may be practical, the paper does not appear to establish a formal relationship between these two measures or provide sufficient empirical validation of the estimation accuracy. Consequently, there remains a gap between the theoretical formulation of EIR and its application to real-world agent trajectories. A more detailed justification or empirical assessment of this approximation would help strengthen the connection between the theoretical contribution and its practical implications.

Questions for authors

Please refer to the weakness comments.

Reviewer_kqi5OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

This paper studies the information requirements of long-horizon agents and how information loss causes execution failures. It introduces Execution Information Requirement (EIR) to quantify the minimum information needed for correct execution, LACUNA to evaluate information retention, recovery, and error propagation through controlled tasks, and VESTIGE to estimate information requirements from real agent trajectories. Experiments show that restoring missing information can recover accuracy, while sufficient storage alone does not guarantee success.

Critical strengths
  1. The paper distinguishes between required, retained, and accessible information, as well as computational capability. This helps explain why larger context windows or external memory do not necessarily improve task success and provides more diagnostic insights than final task accuracy alone.

  2. The paper compare no intervention, exact restoration, and length-matched irrelevant information, achieving 11.3%, 100%, and 0% accuracy on affected Store–Recall steps. In Stepwise Sum, restoring incorrectly evicted information improves LRU accuracy from 0.410 to 0.934, matching exact-window retention. These results highlight the importance of retention policies beyond storage capacity.

Critical weaknesses
  1. Limited validation. The evidence mainly comes from synthetic tasks with known dependencies and controlled information access. On real-world benchmarks, VESTIGE provides retrospective metrics and correlations with failure, but the paper does not demonstrate that it can accurately identify missing critical information or guide recovery to improve task success rates. Validating diagnosis-guided recovery on benchmarks such as SWE-bench, with measurable improvements in task success rates, would strengthen the framework’s practical relevance.

  2. Limited connection between theoretical EIR and empirical capacity. EIR allows unrestricted encodings, whereas the experiments mainly impose limits on fixed-width result records. Although acknowledged by the authors, this mismatch limits conclusions about how closely the evaluated systems approach the information-theoretic minimum. Comparisons across alternative representations under matched bit budgets would strengthen the connection between theory and practice.

  3. Inconsistencies in the paper. Some claims in the main text are inconsistent with the findings in the Appendix. For example, the Introduction highlights a 1.44× increase in failure odds, while Appendix C.2 acknowledges that this result may be inflated and should not be treated as confirmatory evidence.

Questions for authors

Could you explain what these statements in Appendix A.2 mean:

"The statement that Stepwise Sum has a 13-bit requirement and therefore fails despite ample intrinsic capacity is withdrawn. The proposed AGG-versus-ARB reversal of intrinsic EIR is also not established by comparing this online task with the offline final-aggregate contract."

"These are reported source checks, not an independent source inspection in this workspace."

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.