MemState: Dynamic Memory State Graph Construction and Agentic State Graph Retrieval

Existing long-term memory systems often assume that the latest value of a memory fully captures the relevant facts. However, this assumption does not hold for multi-hop retrospective reasoning and complex state queries. Questions such as “What happened before?”, “Why did things become this way?”, and “What was the final outcome?” require access to the complete trajectory of an evolving matter and its current state, rather than a single final value retained after earlier states have been overwritten. We propose MemState, a long-term memory management framework that replaces memory overwriting and deletion with a dynamic state graph. MemState comprises two core modules: Dynamic Memory State Graph Construction (DMSG) and Agentic State Graph Retrieval (ASGR). DMSG preserves successive states of the same matter and organizes them into a dynamic evolution graph through relations of different semantic strengths. This allows historical states, direct state transitions, and related context to coexist without being overwritten by subsequent information. ASGR treats retrieved memories as partial observations of the underlying state graph and enables an agent to actively trace historical paths, subsequent changes, and the latest state through multiple rounds of tool calls. It thereby transforms static similarity-based retrieval into an active retrieval process guided by state evolution. We evaluate MemState on long-term memory benchmarks including RHELM, LoCoMo, and LongMemEval, comparing it with vector retrieval, memory compression, and update-based memory management methods. The results show that MemState more reliably retrieves evidence of key state transitions and actual outcomes into the context, demonstrating stronger state retrieval capabilities under constrained retrieval budgets.