acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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.

Primary area:
applications to computer vision, audio, language, and other modalities
Keywords:
long-term memory, memory retrieval, graph-based retrieval

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_dz3xOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes MemTrace, a graph-based retrieval framework for long-term conversational memory. It addresses two limitations of existing methods: incomplete evidence discovery for complex queries and insufficient source-level evidence ranking. MemTrace uses adaptive query decomposition and independent PCST-based subgraph retrieval to improve evidence coverage, followed by provenance-aware source scoring that combines relation support with contextual semantic similarity. Experiments on LongMemEval-S and LoCoMo demonstrate improvements in retrieval and downstream QA, supported by ablation studies and controlled ranking comparisons.

Critical strengths

1. Clear problem formulation. The distinction between evidence discovery and source attribution is meaningful. It highlights an important limitation of graph-based retrieval: retrieving relevant graph structures does not necessarily identify the original memories containing the required evidence.

2. Convincing controlled experiments. The improvements on two benchmarks are encouraging. In particular, the fixed-candidate-pool experiments provide useful evidence that provenance-aware scoring improves source ranking beyond semantic similarity and PPR-based methods.

Critical weaknesses

1. Limited evidence of generalization across memory graphs.

MemTrace assumes a preconstructed memory graph, but the main comparisons involve different memory systems with their own graph construction pipelines. Consequently, the reported gains may partly reflect differences in graph quality or representation rather than the retrieval method itself. Although the controlled experiments isolate individual components within the proposed graph, they do not establish whether the complete retrieval framework remains effective across different graph construction approaches. This limits the generality of the claimed contribution.

2. Insufficient differentiation from existing GraphRAG techniques.

The proposed framework largely combines established techniques, including query decomposition, local graph retrieval, and source reranking. Similar mechanisms already exist in GraphRAG literature. For example, DRIFT Search [1] generates follow-up questions and performs iterative local retrieval, while Microsoft GraphRAG's local-search implementation [2] prioritizes source text units using their associated graph relationships. The paper also adopts the PCST retrieval formulation from G-Retriever.

While MemTrace introduces query-dependent weighted relation provenance scoring, its incremental contribution over existing graph-to-source ranking strategies remains insufficiently established.

[1] Whiting et al., Introducing DRIFT Search: Combining Global and Local Search Methods to Improve Quality and Efficiency. 2024, Microsoft Research.

[2] Edge et al., From Local to Global: A Graph RAG Approach to Query-Focused Summarization. 2024, arXiv:2404.16130.

Questions for authors

1. Cross-graph generalization: Can the authors evaluate MemTrace using a memory graph constructed by a different method? This would help establish whether the proposed retrieval and ranking mechanisms generalize beyond the particular graph representation used in this paper.

2. Incremental novelty: How does the proposed source evidence scoring differ substantively from existing GraphRAG source-ranking mechanisms? In particular, can the authors compare against an unweighted relation-count baseline under the same retrieved subgraphs and candidate pool to isolate the benefit of query-dependent provenance weighting?

4 comments
AuthorsOpenReview ↗

[W1, Q1] Does MemTrace generalize across graph construction methods?

Thank you for pointing out that the original evaluation does not sufficiently separate retrieval from graph construction. We additionally evaluate MemTrace on graphs constructed by GraphRAG, LightRAG, and MAGMA:

Graph and methodQA accuracyQA tokens
Native GraphRAG31.95%19,034,507
GraphRAG graph + MemTrace Top-546.17%7,895,302
Native LightRAG39.71%15,040,461
LightRAG graph + MemTrace Top-563.23%6,004,246
Native MAGMA54.68%2,588,113
MAGMA graph + MemTrace Top-357.25%5,015,801

The corresponding QA improvements are 14.22, 23.52, and 2.57 percentage points. These results support applicability across the tested graph constructions, while the varying gains and increased MAGMA token usage preclude a graph-independent quality or cost claim.

These are downstream QA pipeline comparisons, rather than isolated retrieval comparisons under fully matched context budgets. Our supplementary evaluation uses binary correctness judgments, which should not be directly mixed with published scores using partial credit. We will specify the reader, judge, evaluation set, and Top-k settings and limit the conclusions to the evaluated configurations.

AuthorsOpenReview ↗

[W2, Q2] What distinguishes the source score from existing GraphRAG source ranking, and does weighting outperform counting?

Thank you for highlighting existing source-ranking mechanisms in GraphRAG. We agree that provenance links and source prioritization are not new concepts, and do not claim query decomposition or PCST as techniques unique to our work.

The fundamental difference lies in how retrieved graph relationships are transformed into source-level relevance scores. In GraphRAG Local Search, retrieved entities serve as anchors for collecting associated relationships and source TextUnits. Each candidate TextUnit is prioritized according to the number of relationships associated with the retrieved entities. However, this counting strategy treats each qualifying relationship equally, without explicitly distinguishing its contribution to the current query. Consequently, a relationship-dense TextUnit may receive a higher ranking simply because it contains more entity-associated relationships, even when only a small subset provides direct evidence for the query. This makes relationship counts an imperfect proxy for the actual evidential relevance of a source.

MemTrace adopts a fundamentally different scoring procedure. For each decomposed query, PCST selects a query-conditioned relational subgraph, where individual edges retain their respective query-dependent prizes. Instead of counting the relationships associated with a source text, MemTrace traces each selected edge back to its originating dialogue turn through provenance mappings and accumulates its prize as evidence support for that turn. The resulting turn-level provenance score is normalized and combined with semantic similarity to determine source relevance. At the final stage, turn-level scores are aggregated at the session level to retrieve the corresponding conversational context.

Thus, while GraphRAG ranks TextUnits based on the number of relationships associated with retrieved entities, MemTrace explicitly models the individual evidential contributions of retrieved relations and attributes their query-dependent importance to their original dialogue turns. This allows relationships associated with the same entity to contribute differently to source ranking, enabling a turn containing fewer but more query-relevant relations to be prioritized over one containing a larger number of less relevant relations.To isolate weighting, we fix the PCST-selected relations, candidate turns, semantic scores, gold labels, normalization, and 0.8/0.2 fusion, replacing only positive-prize weights with 1:

Graph settingSource supportR@3R@5NDCG@5R@10NDCG@10
Original settingQuery-dependent prize weighting67.2874.5369.6783.7472.79
Original settingUnweighted relation counting65.6473.7268.7083.3472.13
GPT-constructed graphQuery-dependent prize weighting69.6676.5672.8086.3975.95
GPT-constructed graphUnweighted relation counting68.1675.4671.8385.9475.16

Weighting improves all five reported metrics in both settings, with R@3 gains of 1.64 and 1.50 percentage points. This supports an incremental benefit from query-dependent weighting after retrieval. Without uncertainty estimates, we do not describe these differences as statistically significant. This counting control also does not reproduce every detail of native GraphRAG source ranking, and we will limit the comparison accordingly.

Dear Reviewer dz3x,

Thank you for your feedback. We hope our response has clarified the points you raised. If any concerns remain, we would be happy to provide further details.

Best regards,
The Authors

Thank you for the author's response. I will consider maintaining my assessment. I hope the author will incorporate these comments into future revisions.

Reviewer_u44gOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

To improve the graph memory, this work introduces MemTrace, which uses adaptive auxiliary queries alongside the original query to retrieve complementary local subgraphs. Experiments on LongMemEval-S and LoCoMo show improvements in memory retrieval and downstream question answering.

Critical strengths

The system show consistent improvement on source retrieval and end-to-end qa performance.

Critical weaknesses
  1. The main contribution seems only to rewrite queries in the graphRAG, which seems a widely used trick in RAG.
Questions for authors
  1. How is the MemTrace's cost compared with other RAG baselines?
3 comments
AuthorsOpenReview ↗

[W1] Is the contribution more than query rewriting for GraphRAG?

Thank you for encouraging a more precise contribution statement. Query rewriting, decomposition, and graph retrieval are not themselves our novelty. Our focus is source ranking after graph retrieval: once relevant relations have been discovered, which original conversational turns provide evidence for the current query?

MemTrace traces query-dependent relation weights through provenance pointers to candidate turns, combines the resulting support with contextual semantic relevance, and restores session context. With PCST-selected relations, candidate turns, semantic scores, and fusion settings fixed, replacing query-dependent weights with unweighted counts reduces R@3 from 67.28 to 65.64 and NDCG@5 from 69.67 to 68.70. This supports an incremental contribution from source weighting, rather than establishing novelty for every component of the framework. We will center the contribution statement on this mechanism and explicitly acknowledge the existing techniques on which it builds.

AuthorsOpenReview ↗

[Q1] How does MemTrace's cost compare with other RAG systems?

Thank you for requesting a cost comparison. We provide the following breakdown for one LoCoMo conversation, conv-30, with 81 questions:

SystemConstruction unitsConstruction callsConstruction input/output tokensConstruction wall timeQuery-LLM input/output tokens
MemTrace369 turns369142,464 / 115,887236.68 s154,790 / 23,542
HippoRAG 219 sessions3837,299 / 5,03930.41 s235,215 / 3,904
LightRAG369 turns1,0782,243,795 / 594,9922,233.15 s54,484 / 2,551

In this case study, MemTrace's construction time is higher than HippoRAG 2's and lower than LightRAG's. The online timing boundaries differ, particularly because the available LightRAG measurement covers only keyword requests, so these values do not provide a direct comparison of complete online latency. We will present them as stage-specific cost measurements, rather than a standardized end-to-end QA benchmark.

The cross-graph experiments also show system-dependent cost trade-offs: QA tokens decrease for GraphRAG and LightRAG, but increase from 2,588,113 to 5,015,801 for MAGMA, approximately 93.8%. We therefore do not claim that MemTrace reduces costs across all graph systems.

We further examine downstream QA token consumption when applying MemTrace to different graph construction pipelines:

Graph and methodQA accuracyQA tokens
Native GraphRAG31.95%19,034,507
GraphRAG graph + MemTrace Top-546.17%7,895,302
Native LightRAG39.71%15,040,461
LightRAG graph + MemTrace Top-563.23%6,004,246
Native MAGMA54.68%2,588,113
MAGMA graph + MemTrace Top-357.25%5,015,801

Integrating MemTrace improves QA accuracy by 14.22, 23.52, and 2.57 percentage points on GraphRAG, LightRAG, and MAGMA graphs, respectively. Meanwhile, downstream QA token consumption decreases by 58.5% and 60.1% on GraphRAG and LightRAG, respectively, but increases by 93.8% on MAGMA.

These results indicate that MemTrace's impact on downstream QA cost depends on the underlying graph representation and retrieval configuration. While it does not uniformly reduce computational costs, it consistently improves QA accuracy across the three tested graph construction approaches. Together, the results demonstrate the applicability of MemTrace across different graph construction pipelines, while highlighting the trade-off between fine-grained provenance retrieval, QA quality, and computational cost.

Dear Reviewer u44g,

Thank you for your feedback. We hope our response has clarified the points you raised. If any concerns remain, we would be happy to provide further details.

Best regards,
The Authors

Reviewer_twGhOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper (MemTrace) retrieves past conversation memories from an LLM-built event graph, where every node and relation links back to the conversation turns it came from. It has two parts:

  1. Decomposition: an LLM splits complex questions into sub-queries, and each one runs its own subgraph search.
  2. Source scoring: each candidate turn is scored by the query-relevance of the selected relations it supports, mixed 80/20 with similarity of a ±2-turn context window.
  3. It reports session-level retrieval on LongMemEval-S of R@3 85.53 vs 78.51 for MemGAS, and a GPT-4o judge QA score of 68.2 vs 60.2.
Critical strengths
  1. A useful framing. It separates getting a memory into the candidate pool from ranking it above topically similar memories that lack the fact.
  2. The right control for the scorer. On an identical candidate pool, source scoring beats similarity by +5.4 R@3 and beats PageRank-based ranking. The gain is largest on multi-session questions (R@3 13.4 to 22.0).
  3. A thoughtful decomposition test against simply widening one search, including the single-session case where widening wins.
  4. Unusually candid. The authors say outright that α and the search budgets were swept on the test set and are not validated optima.
Critical weaknesses
  1. Most of the gain comes from the pipeline, not the contributions. The original-query-only row in Table 3 (no decomposition, no source scoring) already gets R@3 82.55, about 4 points above MemGAS's 78.51. The two contributions add +2.98 R@3, and decomposition alone slightly lowers R@3. The same pattern holds on LoCoMo (61.92 vs MemGAS 57.30).

  2. Baselines are copied from the MemGAS paper, not re-run. Question subsets differ between retrieval and QA (470/1,531 vs 500/1,986). Reader context is also unequal: on LoCoMo MemTrace feeds 3,963 tokens against MemGAS's 2,825.

  3. No reranker baseline. The obvious competitor for "which turn actually states the fact" is a cross-encoder or LLM reranker on the same pool. Only cosine similarity and PageRank are compared.

  4. The relation scores are themselves similarity scores. Each relation's weight is a similarity-rank prize, so the source score amounts to "similarity of the LLM-extracted facts of a turn". That is close to LongMemEval's own fact-augmented keys and to proposition-level indexing. A control that scores facts without the subgraph search is needed to show the graph matters.

  5. Scoring biases: Summing over relations favours turns that produced many extracted facts. Each sub-query's top turn gets full provenance credit however weak that sub-query is, and the max over sub-queries carries it through.

  6. "Fine-grained" is evaluated only at session level. LongMemEval-S R@10 is already 97%, and the turn-level protocol is defined but no results are reported.

  7. Key details are missing. The embedding model is never named, even though it is probably the most influential component. There are no confidence intervals or significance tests (+3.6 R@3 on 470 questions is about 17 questions). There is no cost or latency for the per-utterance graph building and per-query decomposition LLM calls.

  8. Decomposition's recall gain comes with a much larger candidate pool (about 110 candidates per multi-session question). It needs a comparison at matched pool size, and multi-query dense retrieval and HyDE baselines.

  9. The lexical QA metrics contradict the judge. Without the evidence filter, MemTrace is below MemGAS on F1, BLEU and ROUGE but 8 points higher on the judge. With the filter, the judge score drops while F1 rises.

Questions for authors

Address the points in weakness

10 comments
AuthorsOpenReview ↗

[W1] Are the gains mainly due to source ranking, rather than query decomposition?

Thank you for asking us to distinguish the contributions of the components more clearly. We agree that source ranking accounts for the main aggregate retrieval improvement in the reported ablation. As the Table 3 values highlighted in your review, adding source ranking alone improves R@3 by approximately 2.98 percentage points over the configuration without either component (82.55), whereas adding decomposition alone reduces aggregate R@3. We therefore will not present decomposition as the primary contribution or as uniformly beneficial across queries.

Our central problem is how to identify and rank the original conversational memories that support a query after relevant graph relations have been retrieved. Decomposition provides additional entry points for evidence discovery; source ranking maps query-relevant relational evidence back to the original memories. We will clarify this division of roles and explicitly discuss the aggregate limitations of decomposition alongside its motivation for questions with distributed evidence.

AuthorsOpenReview ↗

[W2] Are the comparisons with MemGAS fair under different evaluation subsets and reader contexts?

Thank you for identifying the protocol mismatch. Our evaluation notes record 30 abstention questions in LongMemEval-S and abstention questions in LoCoMo Category 5, and indicate that the MemGAS implementation skips abstention instances for the relevant reported metrics. Our retrieval evaluation excludes abstention questions without retrievable supporting evidence, whereas our QA evaluation includes abstention questions.

We agree that different question sets and reader contexts prevent a strictly controlled comparison. In particular, the 3,963 versus 2,825 reader-context tokens reported for LoCoMo constitute a material difference. We will distinguish cited results from our own runs and specify the evaluation subset, sample count, abstention policy, and reader-context length for each metric. Where a comparison has not been rerun with the same questions, reader, and context budget, we will state this limitation and avoid claiming an advantage under controlled conditions.

AuthorsOpenReview ↗

[W3] How does source ranking compare with a neural reranker?

Thank you for suggesting a neural-reranking baseline. We additionally compare against BGE-reranker-base:

Ranking methodSession R@3R@5NDCG@5R@10NDCG@10Ranking throughput (queries/s)
PPR59.0567.0860.4979.6964.9555.07
MemTrace Source Score67.5475.5170.5484.9173.61183.42
BGE-reranker-base70.4676.6874.7785.1777.484.17

BGE-reranker-base achieves higher ranking quality, while MemTrace has higher measured ranking throughput. MemTrace is 2.92 percentage points lower in R@3 but processes approximately 44 times as many queries per second in this ranking-stage measurement. This supports a quality–efficiency trade-off at the ranking stage, rather than superior ranking quality or an end-to-end speedup. We will specify the timing boundary and experimental conditions in the revision.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.