A State Change Is Local, Its Consequences Are Not: Dependency-Aware State Revision for Long-Term Agent Memory

Yiqi Wang, Tongyuan Zhao, Jiaqi Zhang, Yiqun Duan, Zhangkai Wu, Mingkai Zheng, Taotao CaiarXiv 2026 · arXiv

TL;DR

This paper introduces StateGraph, a memory system for AI agents that tracks how changes to one piece of information "ripple" through a web of dependent beliefs and plans. By using counterfactual reasoning to verify dependencies, StateGraph ensures that when a core fact changes, the agent correctly invalidates or flags all downstream consequences that no longer have support.

What Problem Does This Paper Address?

Long-lived AI agents need a persistent memory to track user preferences, schedules, and tasks. However, the world is dynamic. When a fact changes (e.g., "I am no longer available on Friday"), most current memory systems only update that specific "local" fact.

The problem is that a single change has non-local consequences. If you previously scheduled a meeting because you were available, and that availability changes, the meeting is no longer feasible. Standard systems often leave these "zombie" conclusions—beliefs or plans that have lost their logical support but remain active in memory. The authors call this challenge dependency-aware state revision.

Figure 1: A state change is local, but its consequences are not. The new observation contradicts only s1. Left: a system that revises only the contradicted memory marks s1 stale but retains s2, permitting the pending action a1 to confirm an infeasible meeting. Right: StateGraph propagates along verified dependency edges and returns the pending action for replanning.

Methods

The authors propose StateGraph, which maintains an evolving graph of dependencies between memory states. The pipeline consists of four main stages:

  1. Direct Revision: Identifying which specific memory items are directly contradicted by new evidence.
  2. Candidate Discovery: Finding potentially related states using structural cues (shared entities), linguistic markers ("because," "so"), and execution history.
  3. Counterfactual Verification: This is the core innovation. For every potential dependency (e.g., does $s_j$ depend on $s_i$?), the system asks an LLM: "If $s_i$ were no longer valid, would $s_j$ still hold?" This distinguishes between facts that are merely related and those that truly depend on one another.
  4. Conservative Propagation: The system follows the verified edges to update downstream states. Crucially, it checks for alternative support—if a conclusion has a second, independent reason for being true, it is preserved rather than deleted.
Figure 2: The StateGraph pipeline. (A) Direct revision settles what the observation itself contradicts, yielding the seed set It. (B) Dependency reasoning—this paper’s contribution—proposes candidates from six bounded sources, then verifies each counterfactually, so the verified graph is a subgraph of the candidate graph. (C) Conservative revision maps each verified edge to a status instead of invalidating everything reachable. (D) Premise and action gating turns status into behavior. Panels correspond to §4.1–§4.5.

Datasets

The authors introduce StateChangeBench, a controlled benchmark of 50 author-constructed cases. Each case is annotated with:

  • Cascade Depth: How many "hops" the dependency chain goes (from 0 to 3+).
  • Hard Negatives: Cases where a state is related but not dependent, or has alternative support.
  • Action Consequences: Whether a pending action should proceed, be revised, or require clarification.

They also evaluate StateGraph on six public long-term memory benchmarks, including LongMemEval, MemoryAgentBench, and STALE, to ensure that adding dependency tracking doesn't degrade standard performance.

Key Insights and Ideas

  • Relatedness $\neq$ Dependence: Just because two memory entries mention "Friday" doesn't mean one depends on the other. Counterfactual probing allows the agent to ignore topical associations and focus on logical warrants.
  • The "Zombie" Plan Problem: Without dependency tracking, agents often proceed with actions based on stale premises. StateGraph uses AFFECTS-ACTION edges to "gate" actions, forcing a replan if a prerequisite fails.
  • Alternative Support: A robust memory shouldn't be a house of cards. If a user says "I want to meet at 3pm because I'm free" and later says "I'm not free," but also previously said "3pm is the only time the room is available," the system must weigh whether the 3pm slot is still valid based on the remaining evidence.

Key Results

StateGraph significantly outperforms existing baselines, especially as the "ripple effect" gets deeper:

  • Impact-F1 Score: On StateChangeBench, StateGraph's margin over the strong CUPMem baseline grows from 6.9 percentage points at depth 1 to a massive 26.0 percentage points at depth 3+.
  • Precision and Safety: StateGraph achieved the lowest Over-invalidation rate (5.2%), meaning it is less likely to accidentally delete valid memories compared to simpler "delete everything reachable" strategies.
  • Standard Benchmarks: It maintained comparable or higher accuracy on all six public benchmarks, proving that specialized dependency tracking is a "value-add" that doesn't break general memory functions.
Figure 3: Impact-F1 versus cascade depth on State- ChangeBench (15/15/10 cases at depth 1/2/3+). All methods degrade on deeper chains; in these strata, State- Graph degrades least and its margin over the baselines is larger at greater depth.

Limitations and Future Work

  • Benchmark Size: StateChangeBench is currently small (50 cases). The authors note that larger, independent evaluations are needed to prove robustness across more diverse domains.
  • Self-Verification Bias: The current pipeline uses the same LLM to both propose and verify dependencies. This could lead to "hallucinated" dependencies that the model then confirms because of its own internal consistency.
  • Computational Cost: While more efficient than some complex baselines, StateGraph still requires more LLM calls and tokens than simple RAG systems. Future work could focus on making the verification step cheaper or more selective.

Summary updated

Abstract

Long-lived agents rely on persistent memory of users, tasks and decisions, and this memory must stay consistent with a world that keeps changing. When an upstream fact changes, however, memory systems can revise the contradicted memory itself while the beliefs, plans and actions derived from it remain accepted, even though they have lost their support. We therefore formulate dependency-aware state revision, which asks not only what changed but also which dependent states should no longer be trusted. To address it, StateGraph maintains an evolving state dependency graph whose edges are recovered from interaction histories. Its core design is counterfactual verification: each candidate edge is tested by asking whether the dependent state would survive the loss of its premise, which separates support dependence from semantic relatedness, and revision then invalidates a dependent state only when a strict dependency fails and no independent support path survives. To test this design, we introduce StateChangeBench, a controlled benchmark of 50 author-constructed cases annotated with cascade depth, hard negatives and action consequences. On it, StateGraph's Impact-F1 margin over a CUPMem reimplementation is 6.9 percentage points at depth 1 and 26.0 at depth 3+. On public long-term memory benchmarks, its point estimates are comparable to or higher than those of the evaluated baselines on most datasets. These results provide initial evidence that explicit dependency tracking can improve selective memory revision under changing conditions.
BibTeX
@misc{wang2026state,
  author = {Yiqi Wang and Tongyuan Zhao and Jiaqi Zhang and Yiqun Duan and Zhangkai Wu and Mingkai Zheng and Taotao Cai},
  title = {{A State Change Is Local, Its Consequences Are Not: Dependency-Aware State Revision for Long-Term Agent Memory}},
  year = {2026},
  eprint = {2611.02912},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.02912},
}
Figure