acceptodds
Under review as a conference paper at ICLR 2027

Relevance Is Not Sufficiency: What Actually Closes the Evidence Gap in Long-Term Memory QA

Abstract

LLM agents that interact with a user across many sessions accumulate histories that exceed their context window, so they store past interactions in an external memory and answer each question from a small set of retrieved records. Existing memory systems rank records by lexical or embedding relevance, yet the top-ranked memories can each be relevant while jointly omitting a complementary fact that the answer requires, especially for multi-session and temporal questions. Drawing on the distinction between relevance and sufficiency in legal evidence scholarship, we recast memory retrieval as constructing a sufficient memory set. To operationalize this view, we introduce a blinded LLM judgment over the retrieved set, together with Gold Hit and Turn Hit as evidence-coverage proxies. We then propose Budgeted Flat Reconstruction (BFR), which builds sufficient sets over a fixed flat memory store in two stages. Specifically, we first apply Formal Concept Analysis for Memory Selection (FCA-MS) to decompose the question into information requirements and select a compact candidate subset that jointly covers them. Then, we repeatedly acquire unseen records through deeper text search or complementary entity and session views, stopping when the budget is exhausted. Experiments on LoCoMo and LongMemEval-S show that BFR outperforms same-store adaptations of recent agent-memory systems in both answer quality and evidence coverage. Specifically, on LongMemEval-S it raises judged accuracy from 72.4% to 82.2% and Turn Hit to 91.4%.

Primary area:
applications to computer vision, audio, language, and other modalities
Keywords:
LLM Agents, Agentic Memory, Long-Term Memory, Active Memory Retrieval, Evidence Reconstruction

Reviews

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

The paper studies retrieval for long-term conversational memory QA and argues that ranking memories by per-item relevance can return sets that are individually relevant but jointly insufficient (e.g., an order date is retrieved but the matching arrival date is not). Borrowing the relevance/sufficiency distinction from legal evidence scholarship, it (i) defines set-level sufficiency, measured by a blinded, reference-conditioned LLM judgment (LLM-Suff@Set) alongside annotation-based proxies (Gold Hit, Turn Hit, ER, CER), and (ii) proposes Budgeted Flat Reconstruction (BFR).

Stage I (FCA-MS) retrieves an expanded pool of agent-memory notes (N=50), decomposes the question into requirements with an LLM, applies an FCA-based prefilter (P=20), asks an LLM for a minimal covering subset (mean 1.86 notes), and maps it to 10 source turns by token overlap. Stage II adds unseen turns under a fixed budget (3 rounds / 6 calls / 30 records). BFR-Text re-issues the same query to the text index; BFR-MV cycles text, entity (first person named in q), and session (session of the latest retained record) views. Stage II always stops at budget exhaustion.

With the store, an extractive answerer, and a gpt-5.5 judge held fixed, BFR-MV raises judged accuracy on LongMemEval-S (all 500 questions) from 72.4% (best same-store baseline) to 82.2% with 91.4% Turn Hit. On a 200-question LoCoMo development subset it raises judged accuracy from 64.5% to 70.5%.

Critical strengths

S1. A clear, useful framing with honest metric design. The paper draws a crisp line between item-level relevance and set-level sufficiency and grounds it in a real LongMemEval-S failure (Fig. 1). It also states explicitly that "at-least-one" hit metrics do not establish sufficiency (Table 1), and reports complete-recall and a set-level judgment alongside them. This is a good lens for analyzing multi-session and temporal retrieval failures, and it is the main reason I found the paper informative.

S2. Controlled and candid reporting. Store, answerer, and judge are fixed within each benchmark. LongMemEval-S was evaluated only after the protocol was frozen on LoCoMo (App. F), and the authors disclose that all LoCoMo conversations had development contact. They also report negative results: adaptive state control does not beat a fixed schedule (Table 18), learned residual completion underperforms (Table 21), and full CoM / full MRAgent outperform BFR on the overlap slice (App. C). This transparency makes the claims checkable.

Critical weaknesses

W1. The gains are confounded with evidence-set size, and the strongest variant amounts to deeper relevance ranking — the very thing the paper argues is insufficient.

BFR's final sets are 3–4x larger than the baselines'. FCA-MS hands Stage II 10 turns; BFR-Text C3 ends at 34.0 turns and BFR-MV C6 at 39.9 (Table 16). By contrast, CoM* uses 10.0 and MRAgent-Flat* 11.8 (Table 11), and the Mem0/A-Mem set sizes are not reported. Gold Hit, Turn Hit, ER, and CER all increase monotonically with set size, and a reference-conditioned LLM judge is plausibly more likely to label a larger set "sufficient."

Moreover, BFR-Text re-submits the original question to the text index and keeps the next 8 unseen hits per round (Sec. 4.4). That is essentially a deeper page of the same relevance ranking appended to 10 FCA-MS turns. The paper's own ablations point the same way: access, not state control, drives the gain (Table 18), and FCA-MS alone barely moves coverage (LoCoMo Gold Hit 50.0 -> 51.0).

The decisive missing control is a one-shot top-k baseline (BM25 and dense) with k matched to BFR's realized set size (k ≈ 34–40), plus a full-context / long-context reader on LongMemEval-S. If top-40 recovers most of the gain, the empirical message is "retrieve more records" rather than "construct sufficient sets," and the title's claim about what closes the evidence gap is not supported.

W2. Sufficiency is not operationalized in the method, the sufficiency-aware component does not help, and the sufficiency metric is unvalidated.

Stage I is the only part that reasons about requirements. Yet on its own it is worse than the BM25 baseline labelled "Mem0," both in answer quality (LoCoMo J 53.5 vs. 59.0; LongMemEval-S J 70.4 vs. 72.4) and in set-level sufficiency (LoCoMo LLM-Suff@Set 42.5% vs. 45.5%; LongMemEval-S 48.0% vs. 48.0%). Its minimal subset (1.86 notes) is then re-expanded to a fixed 10 turns by token overlap, so the "compact, complementary" property does not survive into E0.

The FCA component itself is a black box. The formal context, how incidence is decided, and whether the concept lattice is used at all are never specified, and there is no ablation against a simple requirement-coverage count. Stage II never checks sufficiency; it always spends the full budget. The conceptual contribution (sufficiency) and the empirical contribution (more budgeted retrieval) are therefore largely decoupled.

On evaluation:

  • LLM-Suff@Set has no human labels and no inter-judge agreement (App. M).
  • Judged answer accuracy exceeds LLM-Suff@Set by 15–31 points for every system on LongMemEval-S (e.g., A-Mem 68.6 vs. 38.0). The set-level metric and the deliberately lenient Mem0-style answer judge therefore measure quite different things.
  • The headline Turn Hit (91.4%) is an at-least-one indicator that would score the paper's own motivating failure (one of two required turns) as a success (Table 1).

Minor (presentation, not decisive): heavy notation (M~, phi, rho_FCA, kappa_pi) with limited operational payoff; C3/C6 used before being defined; Appendix A adds length but no operational content.

Questions for authors

(a) App. I states that BFR-Text − FCA-MS is +4.0 points (p=0.332), that BFR-MV − FCA-MS is 0.0 (p=1.000), and that no type-level difference is significant. But Table 15 (and Table 5) report overall LLM-Suff@Set gains of +19.5 / +21.0, including +27.5 on 109 Single-Hop questions. Which is correct? (b) The Conclusion says "human checks show that gold-free sufficiency estimates remain too unreliable," but App. M states that no human Suff@Set labels are reported. What human checks were performed? (c) In Table 3, A-Mem and CoM* have identical Judge scores in all four type columns and overall (54.1/87.1/57.1/33.3/68.6) but different Turn Hit. Is this a copy error, or do the two methods hand the answerer identical evidence? (d) Fig. 4's LoCoMo BFR-Text bar (50.0 + 23.5 = 73.5) does not match the 72.5 in Tables 4/17/21, and the two panels appear to mix C3 and C6 operating points.

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

This paper argues that memory retrieval for long-term conversational agents should build a sufficient evidence set, since records that are each relevant can together miss a fact the answer needs. The proposed Budgeted Flat Reconstruction (BFR) keeps a flat store of raw dialogue turns and works in two stages: Stage I (FCA-MS) retrieves 50 A-Mem notes, asks an LLM to decompose the question into requirements, filters the pool to 20 notes with a Formal Concept Analysis (FCA) prefilter, asks an LLM for the smallest covering subset (1.86 notes on average), and maps it to 10 source turns by token overlap; Stage II then adds unseen turns until a fixed budget (3 rounds, 6 calls, 30 new turns) is spent, either by repeating the question on the text index and keeping the next 8 hits (BFR-Text) or by cycling text, entity, and session views (BFR-MV). The paper also proposes LLM-Suff@Set, a set-level sufficiency label from two LLM judges who see the question, the reference answer, and the evidence, with a third model resolving disagreements. On a 200-question LoCoMo development subset and the 500 LongMemEval-S questions, with a shared extractive answerer and a gpt-5.5 judge, BFR raises judged accuracy over same-store adaptations of Mem0, A-Mem, CoM, and MRAgent (LoCoMo 70.5 vs. 64.5, LongMemEval-S 82.2 vs. 72.4).

Critical strengths
  1. The paper studies an important problem. The trade-off between the relevance of single records and the sufficiency of the retrieved set is a central issue for RAG and memory retrieval, and Figure 1 shows a real failure case.

  2. The paper reports its negative results openly: state-aware completion does not help (Table 18), a learned residual query is worse (Table 21), the full MRAgent is stronger (Tables 8 and 9), and all LoCoMo conversations were seen during development (Appendix F). This shows where the gains come from.

Critical weaknesses
  1. The method is a pipeline of many hand-designed components that are neither motivated nor tested, so it reads as engineering more than a principled solution to sufficiency.
  • Stage I works on A-Mem notes and chains LLM decomposition, an FCA prefilter, LLM subset selection, a fallback, and token-overlap grounding; Stage II works on raw turns with three views and a retention rule ("relevance and novelty") given without a formula.
  • Many choices are fixed without justification or sensitivity analysis: N=50, P=20, 10 grounded turns, k_keep=8, the 3/6/30 budget, an entity view that uses only the first person named in the question, and a fixed view order.
  • The FCA prefilter is not specified (what the objects and attributes are, how the lattice is used), and the legal-evidence mapping in Appendix A does not constrain any design choice.
  • Only stage-level ablations are reported, and the tested parts add little (FCA-MS +1.0 Gold Hit, state-aware control -0.5; Figure 4, Table 18). As a result, it is unclear which component, if any, addresses sufficiency.
  1. The central claim, that BFR helps by building sufficient sets, is not supported.
  • Evidence size is not matched: BFR passes 34 to 40 turns, the baselines 10 to 12 (Tables 11 and 16). BFR-Text re-issues the same query and skips seen turns, which equals a deeper top-k, and one extra call (18 turns) already beats every baseline (67.5 J on LoCoMo). A top-k baseline with k around 40 is missing.
  • Stage I does not help: at 10 turns, FCA-MS is below the BM25 "Mem0" and MRAgent-Flat in both LLM-Suff@Set (42.5 vs. 45.5 and 54.5) and LoCoMo J (53.5 vs. 59.0 and 64.5).
  • Sufficiency is never used: Stage II stops only on budget, and the requirement-aware and adaptive-stopping variants give no gain (Table 18). Together, the gains are explained by reading three to four times more turns.
  1. LLM-Suff@Set, listed as a contribution, is not validated. The judges see the reference answer, which may bias them toward "sufficient", and the paper reports no inter-judge agreement, adjudication rate, or human agreement (Appendix M). The RQ2 conclusion that Gold Hit and Turn Hit cannot replace a set-level judgment rests on this measure alone.
  2. The baselines are much weaker than their names suggest: "Mem0" is BM25-lite and "A-Mem" is dense top-k without note evolution (Appendix E). The full MRAgent reaches 95.1 J with 2.4 turns on the 81-question overlap, against 81.5 with 34 turns for BFR-Text (Tables 8 and 9).
  3. Question decomposition with iterative retrieval under a budget is close to IRCoT, Self-Ask, and FLARE, and sufficiency for RAG was introduced by Sufficient Context (Joren et al., ICLR 2025). None of these is discussed or compared.
Questions for authors
  1. Which model is the extractive answerer, and which LLM performs decomposition and subset selection?
  2. How many LLM calls, tokens, and seconds does BFR use per question, compared with the baselines?
Reviewer_DswUOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This is paper argues that retrieving individually relevant memories is not enough for long-term memory question answering: the retrieved set must contain all the evidence needed to answer the question. It proposes Budgeted Flat Reconstruction (BFR). First, FCA-MS decomposes a question into information requirements and selects a complementary subset from an expanded candidate pool. Then, BFR retrieves additional unseen records through either text search or text, entity, and session access, stopping when a fixed budget is exhausted. The paper evaluates answer quality and evidence coverage on LoCoMo and LongMemEval-S. BFR improves over the tested same-store baselines; on LongMemEval-S, its reported judged accuracy is 82.2%, compared with 72.4% for Mem0.

Critical strengths

The distinction between retrieving relevant records and retrieving a jointly sufficient set is important for questions whose answers depend on facts spread across sessions. The paper evaluates both final answers and evidence coverage, and its same-store comparisons help separate retrieval behavior from differences in memory representation. The budget sweep is also useful: it shows how answer quality changes as more retrieval calls are allowed.

Critical weaknesses
  1. The paper does not establish whether the accuracy gains justify the full cost of BFR. It reports retrieval calls and evidence-set sizes, but Stage1 also uses LLM-based requirement decomposition and subset selection, while Stage2 can add many records for the answerer to read. A retrieval-call count alone does not capture those costs. End-to-end comparisons should report LLM calls, input and output tokens, monetary cost, and latency for BFR and the baselines under the same setup. Accuracy should also be compared at matched total cost, not only at matched retrieval-call budgets.
  2. It is also difficult to tell how much of the improvement comes from the proposed selection method rather than broader evidence access. The paper’s own ablations show that completion accounts for much of the gain over FCA-MS alone. A stronger control would give a simple retrieval baseline the same total retrieval, token, and answer-context budgets as BFR, then compare both answer quality and evidence sufficiency.
  3. Finally, the results do not show whether the method works similarly with different LLMs. Requirement decomposition, subset selection, answering, and sufficiency assessment can all depend on model capability. Testing multiple LLMs in the method and answerer roles would clarify whether BFR’s gains are robust or depend on a particular model configuration.
Questions for authors
  1. What are the end-to-end latency, LLM-call count, token usage, and monetary cost per question for BFR and each baseline?
  2. How do answer quality and evidence sufficiency compare when methods are matched on total cost or latency, rather than retrieval calls alone?
  3. How much of BFR’s gain remains when a simple baseline receives the same retrieval and answer-context budgets?
  4. Do the results hold when different LLMs are used for requirement decomposition, subset selection, and answering?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.