A State Change Is Local, Its Consequences Are Not: Dependency-Aware State Revision for Long-Term Agent Memory
Organizations: University of Southern Queensland · Jiangsu University · Uploading Inc. · The University of Sydney ·
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.
Figures & tables
| Revision errors | |||
|---|---|---|---|
| Method | Over-Inv. | Under-Inv. | CVR |
| Vector RAG | 31.4 | 73.5 | 78.2 |
| Time-decay RAG | 28.7 | 69.8 | 74.5 |
| Summary Memory | 19.8 | 48.4 | 56.1 |
| Mem0 | 17.2 | 44.1 | 51.8 |
| Zep / Graphiti | 15.6 | 40.8 | 46.3 |
| Memory revision | |||
|---|---|---|---|
| Configuration | All F1 | Over-Inv. | CVR |
| Full StateGraph | 79.5 | 5.2 | 7.6 |
| w/o Counterfactual Verification | 65.9 | 19.0 | 23.0 |
| w/o Alternative Support | 68.2 | 21.0 | 19.0 |
| w/o Conservative Revision | 62.8 | 25.0 | 28.0 |
| w/o Cascade Propagation | 45.6 | 7.0 | 51.0 |
Appendix figures & tables7 assets
Supplementary material from the paper’s appendix.
Appendix
| Method | SCB Update Acc. | SCB Stale Detection | STALE State Resolution | Ref. Tokens / Case | Ref. Latency / Case |
|---|---|---|---|---|---|
| Vector RAG | 22.4 | 38.1 | 15.0 | 3.5K | 45.0 |
| Time-decay RAG | 26.5 | 36.8 | 20.6 | 3.6K | 46.0 |
| Summary Memory | 70.0 | 68.4 | 20.9 | 8.8K | 100.0 |
| Mem0 | 74.3 | 72.7 | 10.3 | 34.4K | 166.1 |
| Zep / Graphiti | 76.8 | 74.0 | 6.5 | 40.6K | 220.0 |
| A-MEM | 78.1 | 76.6 | 10.8 | 2.6K | 38.0 |
| Method | Cand. Rec. | Type Rec. | Verif. F1 | Edge F1 |
|---|---|---|---|---|
| StateGraph | 62.5 | 47.0 | 55.5 | 61.7 |
| Method | D1 F1 | D2 F1 | D3+ F1 | All F1 | Over-Inv. | Under-Inv. | CVR | Tokens / Latency |
|---|---|---|---|---|---|---|---|---|
| Vector RAG | 20.8 | 10.6 | 5.4 | 13.1 | 31.4 | 73.5 | 78.2 | 3.5K / 45.0s |
| Time-decay RAG | 24.6 | 13.4 | 7.2 | 16.1 | 28.7 | 69.8 | 74.5 | 3.6K / 46.0s |
| Summary Memory | 61.8 | 43.7 | 27.9 | 46.5 | 19.8 | 48.4 | 56.1 | 8.8K / 100.0s |
| Mem0 | 65.1 | 47.2 | 30.8 | 49.8 | 17.2 | 44.1 | 51.8 | 34.4K / 166.1s |
| Zep / Graphiti | 67.4 | 50.3 | 34.6 | 52.8 | 15.6 | 40.8 | 46.3 | 40.6K / 220.0s |
| A-MEM | 68.9 | 51.6 | 35.7 | 54.1 | 14.9 | 39.2 | 44.6 | 2.6K / 38.0s |
| Method | LongMemEval | LME-V2 | MemoryAgentBench | Memora | STALE | LoCoMo |
|---|---|---|---|---|---|---|
| Mem0 | 51.3 | 14.1 | 19.0 | 23.9 | 6.2 | 56.7 |
| Zep / Graphiti | 50.8 | 19.5 | 22.9 | 24.1 | 4.0 | 55.3 |
| A-MEM | 39.5 | 11.7 | 43.1 | 28.6 | 3.1 | 38.4 |
| CUPMem | 47.3 | 15.2 | 28.1 | 25.5 | 51.7 | 50.8 |
| StateGraph | 53.9 | 22.7 | 36.6 | 31.8 | 52.0 | 58.0 |
| Configuration | D1 F1 | D2 F1 | D3+ F1 | All F1 | Over-Inv. | Under-Inv. | CVR |
|---|---|---|---|---|---|---|---|
| Full StateGraph | 82.7 | 79.3 | 75.1 | 79.5 | 5.2 | 10.8 | 7.6 |
| w/o Counterfactual Verification | 75.6 | 64.3 | 54.0 | 65.9 | 19.0 | 13.0 | 23.0 |
| w/o Alternative Support | 77.1 | 66.5 | 57.2 | 68.2 | 21.0 | 10.0 | 19.0 |
| w/o Conservative Revision | 74.3 | 60.5 | 49.0 | 62.8 | 25.0 | 9.5 | 28.0 |
| w/o Cascade Propagation | 71.2 | 38.4 | 17.9 | 45.6 | 7.0 | 58.0 | 51.0 |
| LLM-only Revision | 64.2 | 43.1 | 25.7 | 46.7 | 29.0 | 42.0 | 41.0 |
| Stratum | Cases | Share | Mean cascade size |
|---|---|---|---|
| Hard negatives | 17 | 34% | 1.882 |
| Depth 0 | 10 | 20% | 0.000 |
| Depth 1 | 15 | 30% | 1.000 |
| Depth 2 | 15 | 30% | 2.000 |
| Depth 3+ | 10 | 20% | 3.000 |
| Implicit dependency | 7 | 14% | 1.857 |
| Item | Before correction | After correction: observed result |
|---|---|---|
| 12 Elm Street; CURRENT | STALE direct root; (88 Oak Avenue) is the replacement | |
| : | Gold: STRICT DEPENDS_ON | Verified; invalidated at depth 1 |
| Courier label from Elm Street; CURRENT | STALE | |
| : | Gold: STRICT DERIVED_FROM | Verified; invalidated at depth 2 |
| Thursday estimate from label route; CURRENT | STALE | |
| : | Gold: STRICT AFFECTS_ACTION | Verified action dependency; invalidated the queued email at depth 3 |
Agent Memory
Agent memory lets AI systems retain, update, and use facts, experiences, and skills across sessions and long-horizon tasks.
See all 208 papers