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

StateGraph keeps an agent's memory consistent when a fact changes: it tracks which beliefs, plans and pending actions rest on that fact, and withdraws only the ones that actually lose their support.

1. What the method is

StateGraph is a memory layer for long-running LLM agents. It records the facts an agent holds and also which beliefs, plans and pending actions depend on those facts. Each memory is a typed state with entity, attribute, value, time and condition scope, supporting evidence, confidence and a status: Current, Stale, Historical, Uncertain or Needs-Recompute. The states sit in a graph with three kinds of dependency edge: depends-on, derived-from and affects-action. When new evidence arrives, the system first revises the states it directly contradicts. It then follows verified edges to find the downstream states that have lost their support. The central technique is counterfactual verification. For each proposed edge, a model is asked whether the dependent state would still hold if its premise were removed, and the edge is graded Strict, Weak or None. The authors also release StateChangeBench, 50 hand-built cases labelled for this task.

2. Why the method was developed

Current memory systems such as Mem0, Zep/Graphiti, A-MEM, MemGPT and CUPMem merge facts, track how long facts are valid, or settle conflicts between them. When an upstream fact changes, they correct the memory it contradicts and leave its consequences in place. The paper's example: a user is free Friday afternoon, so a 3pm review is feasible, and a pending action schedules it. The user then mentions a Friday-afternoon flight. The availability memory is marked stale, but nothing directly contradicts the feasibility conclusion or the scheduling action, so the agent books a meeting that cannot happen. Invalidating everything connected to the changed fact goes too far, because some downstream states have independent support. Classic truth-maintenance systems solved this problem, but they assume the dependencies are given explicitly. In agent conversations the dependencies are only implied and must be recovered, and topical similarity is a poor stand-in for real dependence.

3. Who should care

The main audience is product and engineering teams building assistants that keep persistent state about customers, bookings, permissions or tasks. For them a stale downstream conclusion becomes a wrong action: a confirmed meeting, a shipped order, access that should have been revoked. Platform teams choosing or building an agent memory layer should note that the authors added the cascade step to Mem0 and CUPMem and it improved both, so it can be adopted as a component without replacing the whole stack. Risk, compliance and operations leaders get a recorded invalidation path that explains why an action was blocked or sent back for replanning. Owners of inference spend should note the cost: well below the strongest baseline, but several times a plain vector store. Teams buying vendor memory products gain a pointed question to ask: what happens to derived conclusions when a premise changes?

4. How the method works

Each observation is broken into atomic states. Direct revision matches these against existing states by canonical keys and classifies each pair as an update, a conflict, an implicit invalidation, a temporary exception, and so on. The invalidated states form the seed set. Discovery then proposes candidate dependency pairs from six bounded sources: shared entity or task, explicit derivation, tool-call provenance, action preconditions, shared time windows, and cue phrases such as 'because' or 'so we can'. Each model response may propose at most 64 pairs. Each pair is assigned a direction and type, then checked counterfactually. Propagation runs breadth-first over the verified edges under a conservative rule. A failed Strict edge with no surviving independent support makes the dependent Stale or Needs-Recompute. If independent support survives, the dependent stays Current, now grounded on that support. A failed Weak edge makes it Uncertain. Pending actions whose premises fail are blocked and returned for replanning. At query time, premises are checked against their status before use.

5. How it was evaluated

All experiments use a single model, DeepSeek-v4-Flash, with thinking disabled. The main test is StateChangeBench: 50 English cases written by the authors, seeded from LongMemEval interactions and split 10/15/15/10 across cascade depths 0, 1, 2 and 3+. It includes 17 hard negatives, cases where a downstream state should survive, and 36 cases with action consequences. Annotator agreement (Cohen's kappa) was 0.79 on post-update status, 1.0 on depth and 0.56 on dependency type, measured on a double-annotated subset whose size was not recorded. Baselines are vector RAG, time-decay RAG, summary memory, Mem0, Zep/Graphiti, A-MEM, a reimplemented CUPMem and full context, plus Mem0 and CUPMem with the cascade step added. Metrics are Impact-F1 on downstream invalidations, over- and under-invalidation rates, a closure violation rate, dependency-edge recovery, and tokens and latency per case. A supplementary run covers six public memory benchmarks, including LongMemEval, LoCoMo and STALE. The number of runs per configuration was not preserved.

6. How it performed

On direct revision StateGraph roughly matches CUPMem, with stale detection of 86.5% against 80.3%. On cascades its overall Impact-F1 is 79.5 against CUPMem's 64.3. The gap widens from 6.9 points at depth 1 to 26.0 at depth 3+ (75.1 versus 49.1). Only 5.2% of states that should survive are wrongly invalidated, and dependent states are left Current after a failed Strict edge in 7.6% of cases, against 35.1% for CUPMem. Each case costs 12.5K tokens and 92 seconds, against 90.6K tokens and 341 seconds for CUPMem and 3.5K tokens for vector RAG. Edge recovery itself is modest, with a final edge F1 of 61.7%. Removing verification raises wrong invalidations to 19.0%. On the public benchmarks StateGraph is comparable or better on five of six, without significance tests. The authors list their limits: a small benchmark they built themselves, one model, incomplete records, missing action-decision results, and correlated errors because one LLM both proposes and verifies edges. Our call: pilot the cascade step on our own agent memory before relying on it. (Source: arXiv 2611.02912, 2026)