acceptodds
Under review as a conference paper at ICLR 2027

No Universal Memory: Query-Aware Routing for Episodic Retrieval in LLM Agents

Abstract

Long-term LLM agents require episodic memory to reason over interaction histories spanning many sessions, yet no single retrieval strategy serves all query types equally well. Prior graph memory systems propose universal typed-edge topologies and report end-to-end improvements over flat retrieval-augmented generation (RAG), but none has tested whether a single topology generalizes across heterogeneous query classes. We introduce the Causal Temporal Episodic Graph (CTEG), a directed typed-edge memory graph evaluated through 11 ablation variants in the first per-component study at scale, to our knowledge (n=500, LongMemEval-S, full conversation haystack, McNemar significance tests). The central finding is that no fixed topology dominates: the full CTEG system loses to some ablation on every single question type; oracle routing over per-type optimal variants achieves 86.8% (+2.2 pp over the best fixed system), while the best structured memory variant outperforms flat RAG by 14.4 pp (p<0.001). These results establish memory retrieval as substantially query-type-dependent on this benchmark: cross-session CAUSAL BFS shows a directional precision penalty (−2.8 pp, p=0.022, non-significant after family-wise correction), a routing policy recovers most of the per-type gains (+10.0 pp on preference via LATEST dispatch), within 2.8 pp of the oracle ceiling.

Primary area:
foundation or frontier models, including LLMs
Keywords:
episodic memory, LLM agents, agent memory, graph retrieval, retrieval-augmented generation, temporal reasoning, long-term memory, LongMemEval, query routing

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_2u8SOpenReview ↗
Rating
2
Confidence
4
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies whether a single episodic-memory retrieval topology can serve all query types in long-term LLM agents. The authors introduce CTEG, a typed memory graph containing temporal, causal, and contradiction edges, and evaluate a collection of component ablations on LongMemEval-S.

The main empirical observation is that different query categories prefer different retrieval configurations. Based on this observation, the paper further introduces a three-way query router that selects among associative, precise, and latest-oriented retrieval policies. The study includes per-type analyses, significance tests, an oracle-routing upper bound, and a second evaluation on LoCoMo.

Critical strengths
  1. I appreciate the paper's diagnostic perspective. Rather than only proposing another graph-memory architecture, it asks when individual memory components help or hurt, and reports negative results rather than hiding them.

  2. The empirical analysis is relatively careful. The paper includes multiple ablations, per-question-type results, bootstrap confidence intervals, McNemar tests, multiple-comparison correction, and a second benchmark. I also appreciate that the authors explicitly report when effects are underpowered or fail to replicate.

Critical weaknesses
  1. The query-aware routing claim is not validated on a held-out routing setting.

The routing hypothesis and per-type policy preferences are established on the same 500-question LongMemEval-S evaluation set on which the router is subsequently reported. The paper itself notes that this is the full evaluation set rather than a held-out routing split.

This makes the routing result difficult to interpret as generalization. The oracle result is naturally post-hoc, but the practical router also lacks an independent test set for evaluating whether its query-to-policy decisions transfer beyond the data used to identify the per-type retrieval patterns.

This concern is amplified by the fact that the actual router reaches 84.0%, which is slightly below the best fixed policy at 84.6%. Thus, the current experiments demonstrate useful per-type heterogeneity more clearly than they demonstrate the effectiveness of query-aware routing itself.

  1. The central "no universal memory topology" conclusion is stronger than the evidence currently supports.

The numerical best variant differs across question types, but most of these differences are not statistically established. The paper states that temporal reasoning is the only adequately powered category with a detectable per-type CTEG effect; several other categories are underpowered or statistically indistinguishable.

More importantly, the topology effect does not replicate on LoCoMo, where all CTEG variants are within roughly 0.5 percentage points of one another. This suggests that query-type-dependent topology may be benchmark- or regime-dependent rather than a general property of episodic memory retrieval.

I also find the headline gain over flat RAG somewhat difficult to attribute to graph topology. On LongMemEval-S, removing BFS entirely still reaches 83.8%, compared with 70.2% for flat RAG, while the best temporal-only BFS system reaches 84.6%. The paper itself notes that most of this gain comes from the shared retrieval/reranking pipeline. Therefore, the evidence more strongly supports the value of the overall structured retrieval pipeline than the specific graph-topology claim.

Questions for authors
  1. How should the query-aware routing result be interpreted without a held-out routing split? Was the mapping between query types and retrieval policies fixed before inspecting the LongMemEval-S per-type results, or was it informed by those results?

  2. Do the authors have any independent evaluation of the router on a held-out set or another benchmark? This would materially affect my assessment of the routing contribution.

  3. Given that most per-type differences are underpowered or statistically non-significant, and that topology differences largely disappear on LoCoMo, would the authors consider narrowing the "no universal memory" claim to a benchmark- or regime-dependent retrieval heterogeneity claim?

  4. Could the authors clarify the LATEST policy on preference queries? The paper states that reducing the stale-node multiplier from 0.25 to 0.15 reduces false-staleness suppression, but numerically this appears to impose a stronger penalty on stale memories. I may be misunderstanding the scoring convention.

2 comments
AuthorsOpenReview ↗

Response to Reviewer 2u8S

We thank the reviewer for the careful, sympathetic reading and for valuing the diagnostic, negative-result framing. Your two bolded concerns - the held-out routing split and the strength of the "no universal memory" claim - are exactly right, and we have addressed both directly. A revised PDF is uploaded; changes are summarized in our top-level common response.

W1 / Q1–Q2 - No held-out routing split.

You are correct that the per-type policy mapping and the router were reported on the same n=500n{=}500 set. We add a held-out evaluation (Section 4.5, Table 4): we stratify the 500 questions by type, learn the per-type best-variant mapping on the training split only, and evaluate on the disjoint test split, over 200 random splits (50/50 and 60/40). On 60/40, held-out test accuracy is: best fixed system (selected on train) 83.8±2.083.8\pm2.0; train-derived routing 84.8±2.284.8\pm2.2; label-free router cm_router 84.1±1.884.1\pm1.8; test-set oracle (ceiling) 87.6±1.887.6\pm1.8.

On magnitude we are candid: out of sample the advantage over the best fixed system is small - about +1+1 pp, within the CIs - so we no longer claim routing as a performance contribution. But train-derived routing wins 80.5%80.5\% of paired held-out splits, which is exactly the evidence W1 asked for: the per-type structure is real and reproducible out of sample. Specifically:

  • (Q1) The mapping is recovered from training data alone: the full-set winning variant is the single most frequent train-split winner for every one of the six types (67–100% of resamples; temporal 94%, preference 81%, single-session-user 100%). So whether or not the mapping was fixed before we inspected the per-type table, resampling shows it is not an artifact of that choice.
  • (Q2) cm_router reads only the query text, never labels, so its evaluation is already out-of-sample; its held-out accuracy (84.1%) is statistically indistinguishable from its full-set value (84.0%).

We therefore reposition routing as a diagnostic instrument, and lead instead with the per-type characterization, which does not depend on the ≈1\approx 1 pp margin: the optimal topology inverts across query types - CONTRADICTS helps knowledge-update (93.6%) but harms preference (56.7%, below flat RAG); recency (cm_win) beats every graph variant on assistant queries (87.5%); CAUSAL BFS hurts temporal-reasoning while temporal-only BFS helps it.

W2 / Q3 - "No universal memory" is stronger than the evidence.

Agreed, and we now quantify it with a per-type power analysis (Appendix B, Table 6). Only temporal-reasoning (+5.3+5.3 pp, p=0.039p{=}0.039, power 0.560.56) and preference (+26.7+26.7 pp, p=0.008p{=}0.008, power 0.850.85) reach p<0.05p{<}0.05; the other four are directional but underpowered (p≥0.34p\geq0.34, needing n≈400n\approx400–11501150). Per Q3 we therefore narrow the claim to a benchmark/regime-dependent statement: on sparse, many-session LongMemEval-S no single topology is optimal across query types; on dense-coverage LoCoMo the effect attenuates (the seven graph variants cluster within ≈1.2\approx1.2 pp) - even as structured memory still beats flat RAG by +12.8+12.8 pp (95% CI [10.7, 15.6], p<0.001p{<}0.001). This regime-dependence is itself a measured, reproducible result, not a convenient account of a non-replication.

On attribution (removing BFS still reaches 83.8% vs 70.2% for flat RAG): we agree and now state it explicitly. Both cm_ng and flat RAG already include the reranker, so the +13.6+13.6 pp gap is the structured candidate pool and blended scoring - not the reranker, and not a single edge type. The gain over flat RAG is the structured-retrieval pipeline as a whole (Section 4.3), with topology re-allocating where it helps per type.

Q4 - LATEST contradiction-penalty direction.

Thank you - you read the numbers correctly; this was a presentation ambiguity. The penalty is a multiplier on a stale node's retrieval score (s←s×penaltys \leftarrow s \times \text{penalty}), so a lower value suppresses the stale node more strongly. LATEST tightens it from 0.250.25 to 0.150.15 = stronger suppression. We now define this convention at first use (Sections 3.2 and 3.5).

With the held-out split and per-type power analysis now in hand - the two soundness concerns you bolded - we believe the central claim is on firm, correctly-scoped footing, backed by reproducible evidence. If these changes address your soundness concern, we would be grateful if you would consider raising your score; we are also happy to run the LongMemEval-M scaling study during the discussion period if you would find it decisive.

Thank you for the revisions. The held-out results help, but routing does not clearly beat a fixed policy, and most topology effects remain uncertain or fail to replicate on LoCoMo. I maintain my score of 2

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

This paper investigates whether a universal graph topology can effectively support different query types in long-term LLM agent memory. The authors introduce CTEG and conduct systematic ablations of temporal, causal, and contradiction edges. The results reveal substantial performance differences across query types. The best fixed configuration achieves 84.6% accuracy on LongMemEval-S, while the proposed query-aware router achieves 84.0%.

Critical strengths
  • The paper investigates query-dependent memory retrieval and provides useful insights into the limitations of fixed graph topologies, that could be a meaningful research question.
  • Interesting empirical findings, the observation that additional graph edges can hurt retrieval performance provides useful guidance for memory system design.
Critical weaknesses
  • Limited novelty and contribution. Prior works such as Adaptive-RAG, MemFlow, AdaMem, and MemGuide have already explored query-aware retrieval and memory routing, limiting the novelty of this work.
  • Practical improvement is not significant, the proposed router achieves 84.0% accuracy, below the best fixed configuration at 84.6%.
  • Generalization of the evidence is also not enough. The topology-dependent performance differences observed on LongMemEval-S do not replicate on LoCoMo-10, where all CTEG variants achieve very similar results.
Questions for authors
  • Both the flat RAG baseline and the no-BFS variant use reranking. Could the authors clarify why the performance improvement is mainly attributed to the reranker and provide further analysis to isolate its contribution?
1 comment
AuthorsOpenReview ↗

Response to Reviewer KZro

We thank the reviewer, and we think we under-emphasized our actual contribution - which is not routing but a mechanistic per-type finding. We sharpen it here, then address W2, W3, and Q1.

W1 - Novelty vs Adaptive-RAG / MemFlow / AdaMem / MemGuide.

The single transferable lesson of our paper is one we have not found in any prior work: in typed-edge episodic memory, retrieval components have opposite-signed effects across query types - a mechanism that measurably helps one query type hurts another - so a fixed topology cannot be uniformly good. This is a per-component design rule, established by ablation with significance, not a routing method.

We fully agree the cited works establish query-aware routing, and we do not claim routing as our contribution (we state this explicitly in the revised Related Work, Section 2). Adaptive-RAG routes by question complexity; Self-RAG decides when to retrieve; MemFlow dispatches to one of three retrieval tiers; AdaMem conditions a retrieval route on the question over typed memories but reports aggregate end-task accuracy; MemGuide does intent-aligned slot selection. The two closest (MemFlow, AdaMem) route among retrieval strategies/tiers, not typed graph edges, and to our knowledge neither reports a per-edge-type ablation broken down by query type. Concretely, our sign-flips: CONTRADICTS helps knowledge-update (93.6%) but harms preference (56.7%, below flat RAG); a recency window beats every graph variant on assistant queries (87.5%); CAUSAL BFS hurts temporal-reasoning while temporal-only BFS helps it. We now lead with this.

W2 - Router (84.0%) below best fixed (84.6%).

You are right, and we have stopped framing the router as a performance win. Our new held-out analysis (summarized in our response to Reviewer 2u8S) is candid: out of sample the routing advantage over the best fixed system is small and within the confidence intervals (~+1+1 pp), and we do not claim it as a practical improvement - though it does generalize (routing beats best-fixed on 80.5% of held-out splits). The value of the routing analysis is diagnostic: it identifies which component to route on. The paper's contribution is the per-type characterization above, which stands independently of the ≈1{\approx}1 pp margin.

W3 - Topology effect doesn't replicate on LoCoMo.

We agree, and we now treat this as part of the finding (Section 4.6, Tables 11–12). On LoCoMo's 10 dense conversations topology barely moves the result (the seven CTEG graph variants cluster within ≈1.2{\approx}1.2 pp, 66.0–67.2%) - yet structured graph memory still beats flat RAG by +12.8 pp (95% CI [10.7,15.6][10.7, 15.6], p<0.001p{<}0.001; a cleaner, stronger, and fully reproducible result relative to submission). That dissociation - structure matters a lot, topology barely at all on dense data - is itself informative: it tells a practitioner exactly when the graph's edge design is worth the engineering cost (sparse, many-session histories) and when a flat structured store suffices (dense coverage). On LongMemEval-S's sparse haystacks, pool precision binds and topology matters.

Q1 - Isolate the reranker's contribution.

Done (Section 4.3), and the data support your intuition. cm vs cm_nr (reranker removed): 81.8% vs 82.2%, exact two-sided p=0.831p{=}0.831 - the reranker is not a significant aggregate driver at n=500n{=}500. And cm_ng (no BFS, with reranker) vs flat RAG (also with reranker) =+13.6= +13.6 pp: since both already include the reranker, that gap is the structured candidate pool and blended scoring. We now state explicitly that the aggregate gain over flat RAG comes from the structured-retrieval pipeline as a whole, with topology re-allocating where that gain lands per query type.

To summarize the shift: the paper's contribution is not "routing helps" (we agree the literature already has that) but the per-type sign-flip rule above - a concrete, transferable finding for anyone designing typed memory. We hope this reframing and the strengthened, reproducible LoCoMo result speak to the informativeness concern, and if they do, we would be grateful if you would reconsider your score. We are also glad to run the LongMemEval-M scaling study during discussion.

Reviewer_otjROpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

For epsodic memory, this work introduces the Causal Temporal Episodic Graph (CTEG), a directed typed-edge memory graph, with strict test on large scale. This work finds that is that no fixed topology dominates, and route queries to different strategies is necessary and effective.

Critical strengths
  1. The strategy to route different queries to different search strategies is simple and effective.
  2. The experiment include a large scale run.
Critical weaknesses
  1. The dataset only include LongMemEval-S and Locomo, which more real-world agentic settings are not included.
Questions for authors
  1. What if we use PPR instead of BFS?
1 comment
AuthorsOpenReview ↗

Response to Reviewer otjR

We thank the reviewer for recognizing the routing approach as simple and effective and for valuing the scale of the study. Your dataset-breadth question pushed us to make the coverage axis of our claim explicit; we address it (W1) and the PPR question (Q1) below.

W1 - Only LongMemEval-S and LoCoMo.

The two benchmarks were chosen to bracket opposite ends of the single axis our thesis concerns - memory-coverage density - and together they let us state and bound the central claim:

  • LongMemEval-S: sparse, many-session histories, where pool precision binds and per-type topology heterogeneity is real and significant (temporal-reasoning p=0.039p{=}0.039, preference p=0.008p{=}0.008).
  • LoCoMo-10: dense, few-conversation coverage, where the seven CTEG graph variants cluster within ≈1.2{\approx}1.2 pp - topology barely matters - though structured graph memory still beats flat RAG by +12.8 pp.

That contrast is central to what we report. We offer the coverage-vs-precision reading as an interpretation that needs both regimes to even formulate - one dataset could have shown the effect or its absence, never the contrast - rather than a proven law. We are explicit about the limit: LongMemEval-S and LoCoMo differ on axes beyond coverage (domain, session count, type taxonomy, length), so we cannot attribute the LoCoMo result to coverage alone. The clean test that isolates coverage - varying haystack length within a single fixed taxonomy - is a LongMemEval-M scaling study, which we name as future work and present as the experiment that would confirm or refute the coverage hypothesis.

In one line: the two datasets deliberately bracket the coverage axis our claim is scoped to; we report the contrast as a hypothesis to be tested by a context-length study, and we scope the firm claim to the sparse regime where it is significant. A third conversational-QA dataset would likely land in one of the two regimes we already bracket, adding coverage without adding a new axis; the higher-value extension is the context-length axis (LongMemEval-M), which we prioritize.

Q1 - PPR instead of BFS?

A good question. Personalized PageRank would traverse the same cross-session CAUSAL edges our ablation shows dilute precision (the cm vs cm_nca result: CAUSAL BFS costs −2.8-2.8 pp, p=0.022p{=}0.022 uncorrected), because PPR propagates probability mass along those edges rather than pruning them. We therefore expect PPR to inherit the precision penalty on temporal-reasoning; a query-gated edge weighting (fire CAUSAL expansion only when query–causal similarity is high) is the more promising direction, which we have added to the discussion (Future Work, Section 5).

We appreciate that you flagged dataset breadth - it pushed us to state the coverage axis explicitly and to commit to the LongMemEval-M scaling study as the decisive next experiment. If the scoped claim and the regime-bracketing design address your breadth concern, we would be grateful if you would consider raising your score.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Common response: summary of rebuttal changes

We are grateful to all three reviewers - the revision is materially stronger because of your concerns, and we think it now addresses the core issues directly. In response we have:

  1. Added a held-out routing evaluation (Section 4.5, Table 4; stratified train/test, 200 resamples) showing the per-type structure is out-of-sample, not an in-sample artifact.
  2. Added a per-type power analysis (Appendix B, Table 6) and narrowed the central claim to a benchmark/regime-dependent statement (abstract; Sections 4.2, 4.6) that matches exactly what the data support.
  3. Isolated the reranker (Section 4.3) and now state plainly that the aggregate gain over flat RAG is the structured-retrieval pipeline as a whole, with topology re-allocating where it helps per query type.
  4. Re-ran LoCoMo with corrected evaluation code (Section 4.6, Tables 11–12): structured graph memory now beats flat RAG by +12.8 pp (95% CI [10.7,15.6][10.7, 15.6], p<0.001p{<}0.001), reproducibly, while the seven graph variants cluster within ≈1.2{\approx}1.2 pp of one another.
  5. Clarified the LATEST contradiction-penalty convention (Sections 3.2, 3.5) and improved the exposition (sharper contribution framing, regime-scoping in the abstract).

No measured result changed in a way that weakens a finding - every revision scopes or strengthens an existing result. Per-reviewer responses follow. We would be glad to run additional analysis during the discussion period and hope the reviewers will consider the updated version.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.