MemTrace: Fine-Grained Source Evidence Retrieval for Long-Term Memory

Long-term memory enables LLM-based agents to reuse information from past interactions. One approach to organizing these memories is to connect information across interactions in a graph. Subgraph retrieval then locates graph regions relevant to the current query. However, retrieving the source memories needed for answering still presents two challenges. First, retrieval guided by the overall semantics of a complex query may produce subgraphs that omit regions containing evidence relevant to only part of the question. Second, even when the required memories are retrieved, semantic similarity or graph importance may favor related memories that lack the required evidence, leaving supporting memories ranked lower. To address these challenges, we introduce MemTrace, a fine-grained source memory retrieval framework. MemTrace uses adaptive auxiliary queries alongside the original query to retrieve complementary local subgraphs. It traces retrieved relations to their source memories and combines aggregated relation support with contextual semantic similarity to rank candidates. Experiments on LongMemEval-S and LoCoMo show improvements in memory retrieval and downstream question answering. Controlled experiments confirm improved coverage of distributed evidence and more effective source ranking within a fixed candidate pool.