MemDTG: Dynamic Temporal Memory Graphs for Evidence-Admissible Agent Memory

Abstract

Long-term agent memory is an online, non-monotonic retrieval problem. New interactions may reinforce, contradict, supersede, specialize, abstract, or expire earlier memories; the same fact can be a wrong current answer, a correct historical answer, or necessary transition evidence depending on query intent. Existing chunk, summary, and graph memories retrieve by semantic or graph relevance and treat time as post-hoc metadata, so they cannot determine whether a memory is observable, valid, lifecycle-admissible, and provenance-supported before it enters the candidate space. We propose MemDTG, a dynamic temporal memory graph that frames agent memory as temporal evidence admission. MemDTG separates immutable raw episodes from a mutable entity-state temporal graph and a memory-evolution graph over assertion versions. State slots localize mutable user and task states; an LLM-assisted slot-local resolver classifies semantic evolution only within bounded temporal histories; and deterministic commit rules update valid intervals, lifecycle states, and typed evolution edges. At read time, a query compiler instantiates observed-time, valid-time, version, edge-type, and role constraints before ranking, and QV-CTW retrieves evidence paths only inside the query-legal temporal subgraph. Evidence certificates record selected facts, sources, roles, and rejected stale or future alternatives, making retrieval auditable. On LongMemEval and LoCoMo, MemDTG achieves the best LLM-judge accuracy and Citation F1. Ablation and temporal error analyses confirm that provenance certificates and legal-subgraph pre-filtering are each essential for these gains, reducing stale-answer errors by 61.7% and future leaks by 80.1%.