Isolated Facts Do Not Tell the Whole Story of a Long-Term Conversation

Long-horizon conversations do not preserve a user state as independent facts: evidence is distributed across sessions, revised over time, and often relevant only through intermediate memories. Existing memory systems recover these dependencies via costly mechanisms: graph-structured memories construct elaborate relational structures during indexing and rely on multi-stage graph traversal at query time, while agentic retrievers repeatedly invoke LLMs to plan and refine retrieval. We propose TraceMem, a lightweight alternative that organizes conversational histories into an evolving flat memory. At retrieval time, TraceMem uses two complementary relations: the intra-relation links historical and current expressions of the same memory to preserve state evolution, while the inter-relation connects memories through bridge entities to recover cross-session dependencies. Together they form complete memory trajectories, from which multi-hop and temporal questions are answered without complex graph reasoning or LLM-guided iterative retrieval. Across LoCoMo-10 and LongMemEval-S, TraceMem outperforms agentic baselines by 6.1% while achieving near-zero-latency retrieval, demonstrating that structured evidence reconstruction does not require a complex query-time reasoning system.