acceptodds
Under review as a conference paper at ICLR 2027

A Memory You Can’t Recall Is No Memory at All: MEMENTO for Query-Agnostic KV Cache Eviction in Multi-Turn Inference

Abstract

Multi-turn agentic inference requires a bounded KV cache to support information needs that change across user requests and tool interactions. Repeatedly evicting entries according to the current query can specialize memory to the task at hand: once discarded, evidence needed by a later turn cannot be recovered by rescoring the surviving cache. We argue that useful memory requires both availability and accessibility: a memory the model cannot recall cannot support its response. We propose **MEMENTO**, a training-free streaming compression method that lets the model reread: it re-feeds each completed context chunk, and the attention of the reread supplies query-agnostic retention scores, using the content itself to generate retrieval cues. MEMENTO interleaves rereading with subsequent decoding in isolated batch rows of the same forward pass, amortizing scoring latency while maintaining a persistent cache across turns. A geometric analysis interprets reread queries as witnesses of retrieval cells and bounds local attention error on the regions they cover. Under explicit coverage and value-separation conditions, the same analysis yields a lower expected future-query error than a cache specialized to the current query at the same retention budget.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
Multi-turn LLM Inference, Query-agnostic KV Cache Eviction

Reviews

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

The paper targets an important problem in KV cache compression or eviction in multi-turn agentic inference. The KV cache grows unboundedly as tool calls, model reasoning and outputs accumulate. To run under fixed memory budget, the engine must continuously evict KV entries before knowing what future turns or queries may ask.

Given the problem, the paper finds that two existing methods are insufficient to solve it. Query-dependent methods prioritize KV entries relevant to current query, potentially discarding entries needed by future turns. Query-agnostic methods are unreliable because they use static KV statistics to predict. The paper observes that, attention statistics of the query token during decoding, which is called Writer, cannot accurately reflect the attention dependence onto past memories, because it mixes attention of recent tokens, syntax checking and attention sinks in order to accurately predict next token. When completed tokens are re-fed (append the same tokens right after the completed tokens, called Readers), their attention concentrate on really relevant information. Based on this, the paper derives the MEMENTO design, a query-agnostic method that centers on re-reading based recall scoring.

In general, the paper gives in-depth analysis about availability and accessibility of KV eviction, identifies why decoding attention statistics fail to serve as retrieval signals and designs a rereading based recall scoring method that can adapt evolving context. Experiment results show that MEMENTO has higher task accuracy or pass rate than existing query agnostic methods on several agentic benchmarks.

Critical strengths
  1. The paper addresses KV retrieval problem in KV cache eviction. It gives a highly informative and detailed characterization of important challenge of accurately retaining relevant evicted KV entries without exactly knowing future queries. The paper first draws from concepts in cognitive psychology field, and maps them to the availability and accessibility of KV cache entries. It then identifies the root cause why query-dependent and query-agnostic ways are insufficient, especially the failure of static attention statistics of existing query-agnostic ways. Based on that, the paper gives their unique insight that rereading provides more accurate attention statistics onto the memories and can therefore serve the retrieval. These analysis give useful insight for query-agnostic KV eviction design.
  2. The paper also gives hardware-aware design to support efficient execution of their proposed scoring and computation mechanisms. The interleaved decoding executes rereading alongside the normal decoding to amortize additional computation overhead incurred.
Critical weaknesses
  1. Although the paper discusses query-dependent ways and consider them less effective compared to query-agnostic ways in multi-turn agentic scenarios, it should includes representative query-dependent methods, such as SnapKV, PyramicKV in the evaluations to justify and convince.
  2. The decoding speed experiment reports 3.17x over full KV cache, which mainly comes from the KV cache compression itself, rather than the interleaved decoding of MEMENTO. No other baselines are compared in decoding speed experiments. It's unclear how the system performs compared to existing works, and how interleaved decoding contributes to the overall throughput improvement of the system.
Questions for authors
  1. Could the authors report end-to-end results of representative query-dependent methods, which could make the paper more consistent and comprehensive?
  2. Could the authors report decoding throughput of other baselines, MEMENTO w/o interleaved decoding to justify the effectiveness of the system optimization? Also, Appendix C.6 reports results on H200 without considering host memory, I'm curious how retrieval would affect the performance under KV cache offloaded settings, i.e. evicted KV cache moved between GPU HBM and host memory.
Reviewer_cU6hOpenReview ↗
Rating
2
Confidence
4
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper proposes a new attention-based heuristic for KV cache eviction. The idea is that eviction/retention decisions for the KV cache should be based on what’s relevant for future queries (future turns) and not current queries (current turn). They propose MEMENTO, which tries to estimate KV that’s relevant to future queries, by re-feeding each completed chunk of tokens through the model (termed “re-read”) and using the attention the re-fed copies pay to cached entries as a score. The copies are then discarded, and an entry’s score is averaged over the rereads of its own chunk and all later chunks. Their insight is that the attention generated with this duplicated chunk of tokens is a better indicator of future relevance. They show improvements in the scores of agentic tasks under a fixed token budget compared to query-agnostic kv cache compression baselines.

Critical strengths

Strong results on realistic multi-turn agent benchmarks. For example, 71.5% vs. 73.5% (full cache) on SWE-bench Verified with about 23% of the cache, against 65.0% for the best baseline.

Critical weaknesses

The core claim is not directly validated. The paper never shows that rereading predicts future relevance better than attention the model already computes, from decoded tokens (H2O [1]) or from the latest input (SnapKV [2]). Tables 1 and 2 don’t report these. The one attention-based reference there, the “query-dependent” half-oracle, beats MEMENTO on next-turn overlap (61.1% vs. 56.1%). The paper’s assumption that upcoming turns resemble recent ones is also questionable for agentic workloads, which often change direction.

No end-to-end comparison with the methods the paper argues against. Section 4.1 states that “Query-dependent methods, which Section 3 argues against, are not compared end to end”. Yet Theorem 1 admits these methods can win when the current request predicts future needs. Without SnapKV [2], H2O [1] in the same streaming setup, the margins may reflect weak baselines.

Questions for authors
  1. How does MEMENTO compare end to end with SnapKV, H2O / TOVA, RocketKV [3] and R-KV [4] under the same budget?
  2. Can Tables 1 and 2 include scores built from decode-time attention of the original tokens? This is the most direct test of whether rereading helps.
  3. The Oracle uses only the next turn. Can you report overlap with attention over the full remaining trajectory?
  4. Why should attention from rereading recent content anticipate what a future, possibly divergent, state will need?
  5. Appendix C.6 reports a vLLM implementation but gives no detail on how per-head eviction and the reread’s separate mask fit vLLM’s paged KV cache. Can you please describe this?

References [1] Z. Zhang et al. H2O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Models. NeurIPS, 2023.
 [2] Y. Li et al. SnapKV: LLM Knows What You Are Looking for Before Generation. NeurIPS, 2024.
 [3] P. Behnam et al. RocketKV: Accelerating Long-Context LLM Inference via Two-Stage KV Cache Compression. ICML, 2025.
 [4] Z. Cai et al. R-KV: Redundancy-aware KV Cache Compression for Reasoning Models. NeurIPS, 2025.

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

MEMENTO compresses the KV cache during multi-turn inference by rereading completed chunks and using their attention to score cached entries. Scores are averaged across rereads, and rereading is batched with normal decoding to reduce overhead. The paper evaluates the method on three agent benchmarks and provides a geometric analysis of retrieval. Results are strong on the two larger models, with substantial improvements over the tested baselines.

Critical strengths
  • Strong results on realistic agent tasks. On Muse-Glimmer-30B, MEMENTO improves SWE-bench Verified from 65.0% to 71.5%. These are meaningful gains, and the paper reports paired significance tests.
Critical weaknesses
  • The theory does not match the implemented scoring rule. Eq.1 averages credits across rereads, while Eq. 4 analyzes maximum attention from an entry’s own reread. The proof relies on a single strong witness being enough to retain an entry. That need not hold under averaging, since later low scores can dilute the earlier contribution. As written, the analysis does not establish the claimed guarantee for the actual method.

The comparisons leave the source of the gains unclear. MEMENTO allocates its budget globally across layers and heads, while the four main baselines use a fixed budget per head. This makes it difficult to separate better scoring from better allocation. The paper also excludes query-dependent methods from the end-to-end evaluation, despite making their limitations a central motivation. The attention-overlap experiment is informative, but it does not replace a task-level comparison with a streaming baseline such as H2O.

Questions for authors
  • Can the theoretical argument be extended to the running-mean score actually used by MEMENTO? Which parts of the guarantee still hold?

  • How much of the gain remains with the same budget allocation for all methods? A comparison with an online attention-based baseline under that same allocation would also help.

  • Since own-reread credit is reportedly about 140× larger than later credit, could averaging mainly help by reducing older entries’ scores? How does it compare with simply dividing the own-reread score by the number of eligible rereads?

  • What are the end-to-end latency and peak memory on the actual agent workloads, including prefill rereading and turn-boundary draining? The separate long-generation throughput experiment does not fully answer this.

  • How does MEMENTO compared to learnable eviction methods like DBTrimKV [1]

[1] Bui, Ngoc, et al. "Make Each Token Count: Towards Improving Long-Context Performance with KV Cache Eviction." arXiv preprint arXiv:2605.09649 (2026).

Comments on the paper

2 comments
AuthorsOpenReview ↗

Summary of Reviewers' Feedback and Our Rebuttals

Dear AC

We thank the AC and all three reviewers for their engagement. During the discussion, we added end-to-end comparisons with query-dependent and online baselines, a controlled study separating scoring from allocation, a revised analysis matching the implemented scoring rule, a comparison with learned eviction (DBTrimKV), and a full systems characterization. JNdo has no further questions and keeps their positive score. rnb8 and cU6h raised narrower follow-up questions, which we answered on 18 Nov 2026; we are awaiting their replies. We provide a summary below for the convenience of the AC.

TL;DR of Our Work

Multi-turn agentic inference needs a bounded KV cache, but what later turns need changes across requests and tool calls. Query-dependent eviction specializes the cache to the current query and can permanently discard evidence a later turn needs, while static query-agnostic statistics are unreliable predictors of future retrieval. We argue that useful memory requires both availability and accessibility.

We propose MEMENTO, a training-free, query-agnostic method that lets the model reread: it re-feeds each completed chunk, and the attention of the reread supplies retention scores. Rereading is interleaved with decoding in the same forward pass to amortize its cost, and a geometric analysis bounds local attention error on the regions that reread queries cover and, under explicit coverage and value-separation conditions, yields a lower expected future-query error than a query-specialized cache at the same budget. On SWE-bench Verified with Muse-Glimmer-30B, MEMENTO reaches 71.5% using about 23% of the cache, vs. 65.0% for the best baseline and 73.5% for the full cache.

Reviewers' Recognition

We are glad to report that:

Reviewers acknowledge the strong empirical results on realistic agent tasks:

  • rnb8: "Strong results on realistic agent tasks. On Muse-Glimmer-30B, MEMENTO improves SWE-bench Verified from 65.0% to 71.5%. These are meaningful gains, and the paper reports paired significance tests."
  • cU6h: "Strong results on realistic multi-turn agent benchmarks. For example, 71.5% vs. 73.5% (full cache) on SWE-bench Verified with about 23% of the cache, against 65.0% for the best baseline."

Reviewers acknowledge the insight of our analysis:

  • JNdo: "It gives a highly informative and detailed characterization of important challenge of accurately retaining relevant evicted KV entries without exactly knowing future queries."
  • JNdo: "The paper gives in-depth analysis about availability and accessibility of KV eviction, identifies why decoding attention statistics fail to serve as retrieval signals and designs a rereading based recall scoring method that can adapt evolving context."
  • JNdo: "Based on that, the paper gives their unique insight that rereading provides more accurate attention statistics onto the memories and can therefore serve the retrieval. These analysis give useful insight for query-agnostic KV eviction design."

Reviewers acknowledge our hardware-aware system design:

  • JNdo: "The paper also gives hardware-aware design to support efficient execution of their proposed scoring and computation mechanisms. The interleaved decoding executes rereading alongside the normal decoding to amortize additional computation overhead incurred."

How We Addressed Reviewers' Concerns

1. Missing query-dependent baselines: added SnapKV, RocketKV, and H2O end to end; MEMENTO wins in all 8 settings (cU6h, rnb8, JNdo)

We added SnapKV, RocketKV, and H2O in the same streaming setup and budget, on BrowseComp-Plus and three τ²-bench domains with two models. MEMENTO is the best method in all eight columns, leading by up to 37.7 points over the best added baseline, and its gaps to H2O and SnapKV on BrowseComp-Plus hold in paired tests on both models (p ≤ 0.003). Query-dependent methods fail where our analysis predicts: on τ²-Telecom, where later requests need rules cached long before, they reach 13.2% to 18.4% vs. 75.4% and 76.3% for MEMENTO. In the follow-up, we clarified to cU6h that SnapKV and RocketKV use the configurations recommended by their original papers (RocketKV's from multi-turn SCBench), rescored at every eviction instant.

2. Does rereading predict future relevance? Yes: it beats H2O and SnapKV scores on every measure, and its lead over SnapKV grows over longer horizons and divergent turns (cU6h)

On the data of Tables 1 and 2, MEMENTO beats H2O and SnapKV scores on every measure, and its lead over SnapKV grows with the horizon (78.0% vs. 67.9% kept rate eight turns after eviction). It stays within 5.0 points of the half-oracle, which sees the next request, and keeps more than it once eviction repeats every turn (78.0% vs. 69.3% after eight turns). In the follow-up, we showed that the small single-selection gap compounds over dozens of irreversible evictions end to end (a median of 37 per session on τ²-Telecom), and that MEMENTO's lead over SnapKV is largest where the agent changes direction most (9.5 points in the high-shift tertile after eight turns; 95% CI [7.3, 11.6]).

3. Source of the gains: controlled ablations show the margin comes mainly from the reread score, not budget allocation (rnb8)

Under identical allocation (per-head or global), MEMENTO remains best in every column; global allocation helps MEMENTO consistently but not the baselines, so most of the margin comes from scoring. The reviewer's suggested aggregation (own credit ÷ number of rereads) reaches only 8.0% vs. 51.0% for the running mean on BrowseComp-Plus, showing that averaging works because later rereads act as new retrieval cues.

4. Theory vs. implementation: guarantees now proven for the implemented running-mean score (rnb8)

We restated the analysis for the implemented running mean. Proposition 1 and Theorem 1 hold with the same bounds and unchanged proofs, and a new Corollary 1 covers the refresh mechanism that Table 5 shows to be essential.

5. Learned eviction: training-free MEMENTO outperforms DBTrimKV, even with in-domain training (rnb8)

Without any training, MEMENTO outperforms DBTrimKV with in-domain gates (51.0% vs. 43.0% on BrowseComp-Plus, p = 0.009), and DBTrimKV falls to 9.5% when trained on its authors' math corpus. In the follow-up, we showed that more in-domain data does not help (47.0% / 43.0% / 40.0% for 100 / 200 / 400 rollouts) and added the requested pros-and-cons discussion to Appendix C.5.

6. Systems efficiency: small overhead on real agent sessions, 4.2x decoding throughput under a memory budget, compatible with KV offloading (rnb8, JNdo, cU6h)

On real agent sessions, prefill rereading, eviction, and turn-boundary draining add only 3.3% to wall time (interleaved rereads raise the decode step from 6.6 to 7.7 ms), while bounding the growing KV memory to 0.18x of the full cache. Replaying 24 BrowseComp-Plus sessions in vLLM, MEMENTO finishes them 1.94x sooner than the full cache. Interleaving reaches 87% of a scorer-free ceiling, is 1.66x faster than separate reread forwards, and avoids batch stalls; with exact-size CUDA graphs, MEMENTO reaches 4.2x the throughput of the full cache under the same memory budget (up from 3.17x), a gain that comes from the bounded cache, as JNdo noted. MEMENTO is also complementary to KV offloading, and we detailed the vLLM paged-cache implementation for cU6h. JNdo has no further questions.


We find our reviewers' feedback fair and constructive, and we believe we have faithfully addressed all raised concerns. We thank the AC for considering this summary.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.