acceptodds
Under review as a conference paper at ICLR 2027

LETHE: Forgetting Irrelevant Context for Efficient Prefill in RAG and Tool-Calling

Abstract

Agentic, retrieval-augmented generation (RAG), and tool-calling applications repeatedly process largely unchanged context, yet standard KV caching only applies when the reused context forms an identical prefix. We introduce LETHE, a training-free method for non-prefix KV reuse. Rather than caching chunks independently and later reconstructing missing cross-attention, LETHE builds a shared cache in which chunks already interact, then selectively corrects the influence of chunks excluded from the current request. An offline divergence analysis is performed once per chunk to identify tokens that should be recomputed at runtime, while the remaining tokens are reused from cache. The same mechanism applies to both retrieved text and tool definitions without modifying or fine-tuning the base model. Across Qwen3-8B, Qwen3-14B, and Llama-3.1-8B-Instruct, LETHE recomputes as little as 4.9% of context tokens and reduces full-prompt FLOPs by 50.7–87.5%. On HotpotQA, the best evaluated LETHE setting for each model is within 2.8 EM points of full recomputation and LETHE-K outperforms EPIC-16 by 7.1 EM points on average; on BFCL, the best LETHE setting is within 1.5 percentage points of full-recomputation function-call accuracy across all three models. With a fixed 10% recomputation budget, LETHE achieves 5.3–6.3× wall-clock prefill speedup at 10k context tokens on a single RTX A6000 GPU. Overall, across three models and both text retrieval and tool calling, LETHE preserves near-baseline task quality while substantially reducing computation, with long-context prefill speedups reaching about 6×.

Primary area:
foundation or frontier models, including LLMs
Keywords:
KV cache reuse, non-prefix caching, large language model inference, retrieval-augmented generation, tool calling, efficient inference

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

This paper proposes LETHE, a training-free method for non-prefix KV-cache reuse in RAG and tool-calling workloads. Instead of independently caching chunks, LETHE constructs a shared cache with existing cross-chunk interactions and selectively recomputes tokens affected by irrelevant context. Token selection is based on offline divergence between solo and shared-cache key representations, with adaptive or fixed recomputation budgets.

Critical strengths

S1. Interesting shared-cache formulation. LETHE approaches non-prefix KV reuse by correcting residual irrelevant interactions rather than reconstructing missing ones. This provides a useful alternative to independent-chunk caching.

S2. Efficient query-independent token selection. Offline divergence ranking avoids repeated importance estimation at inference time, while adaptive per-chunk budgets offer flexible accuracy--efficiency trade-offs.

S3. Encouraging empirical results. The method is evaluated on three models and two workloads, demonstrating substantial FLOP savings with relatively small accuracy degradation. The inclusion of measured prefill latency is also valuable.

Critical weaknesses

W1. Insufficient validation of divergence-based selection. The paper lacks comparisons against random, positional, or simpler importance-based token selection under matched budgets. It is therefore unclear how much improvement comes specifically from the proposed divergence metric.

W2. Limited analysis of query-dependent errors. Token rankings are computed once using the full shared cache, but actual interference depends on which chunks are removed. The paper does not sufficiently quantify sensitivity to different chunk subsets or omission patterns.

W3. Incomplete efficiency evaluation. The latency benchmark excludes query processing and decoding and uses a fixed randomly generated token ranking. Cache construction, solo forward passes, and divergence computation costs are not amortized in the reported comparisons.

W4. Limited baseline comparison. EPIC is compared on HotpotQA accuracy, but corresponding FLOPs and latency are omitted, making it difficult to establish the relative accuracy--efficiency advantage.

Questions for authors

Q1. How does divergence-based token selection compare with random selection, positional heuristics, and simpler importance metrics at identical recomputation budgets?

Q2. How sensitive is LETHE to the number, positions, and combinations of omitted chunks? Does the static token ranking remain effective across different query-specific subsets?

Q3. What are the preprocessing time and memory overheads of constructing shared and solo caches? How many cache reuses are needed to amortize these costs?

Q4. Can the authors provide end-to-end latency measurements including query prefill and decoding, using the actual divergence-based token selection?

Q5. Can LETHE and EPIC be compared under matched FLOP or latency budgets to demonstrate their relative accuracy--efficiency trade-offs?

2 comments
AuthorsOpenReview ↗

Additional Experiments and Clarifications on Token Selection, Cache Reuse, and End-to-End Efficiency

We thank the reviewer for the constructive feedback. We revised the manuscript and added new experiments in Appendices F and G. Our responses follow.

Q1. Divergence selection vs. simpler strategies

Appendix F adds controlled comparisons at matched recomputation budgets.

  • Top vs. least divergent: Selecting the most K-divergent tokens outperforms selecting the least divergent in all six comparisons (10% and 20% budgets, three models, 500 HotpotQA questions each; Table 13). For example, Llama-3.1-8B achieves 0.618 vs. 0.574 EM at 20%.
  • Random selection: On 100 Llama-3.1-8B questions, K-Top10 achieves 0.640 EM versus 0.599 mean EM for ten random seeds (range 0.580–0.620). All ten random runs perform worse.
  • K/V/hidden divergence: At matched 10% budgets, their performance is similar, with no representation consistently superior (Table 12).

These results support divergence-guided prioritization, although we do not claim superiority over every possible query-aware or attention-based selector. Offline ranking avoids additional query-time scoring.

Q2. Sensitivity to omitted chunks

LETHE's offline ranking compares each chunk's shared-context and solo representations, measuring the collective influence of preceding chunks. At runtime, it recomputes selected tokens against the retained context, preserving the original build order.

The ranking does not identify which particular omitted chunk caused the divergence. Consequently, it may unnecessarily correct tokens influenced by retained chunks or overlook tokens affected by specific omissions.

HotpotQA evaluates different query-specific subsets, but we have not systematically varied omitted-chunk counts and positions. We explicitly acknowledge this approximation in Section 6.

Q3. Offline construction and amortization

Appendix D reports total offline preparation times for approximately 200 chunks/20K tokens per pool: 34.8 s (Qwen3-8B), 31.8 s (Llama-3.1-8B), and 46.6 s (Qwen3-14B). Shared-cache construction takes 14.8/13.3/19.5 s, respectively; solo-cache construction and ranking take 20.0/18.5/27.1 s. These measurements include I/O and synchronization.

At runtime, LETHE retains the shared KV cache and per-chunk ranking metadata; solo caches are discarded. We have not separately measured peak construction memory. Preparation can be amortized across repeated requests, but the break-even reuse count depends on workload-specific latency savings and cache reuse frequency. Section 6 clarifies the cold-start and cache-management limitations.

Q4. End-to-end latency

We added Appendix G (Tables 14–15), measuring complete requests with actual offline K-divergence rankings, including cache retrieval, RoPE repositioning, selective recomputation, query prefill, and decoding.

We grouped HotpotQA supporting passages into reusable chunks of approximately 4.1K–6.7K tokens. Each model was tested on four representative requests with LETHE-P10, five warmups, and 30 timed repetitions. Both methods used identical contexts and questions.

Aggregate end-to-end speedups over full recomputation are 2.79× (Qwen3-8B), 2.88× (Llama-3.1-8B), and 3.08× (Qwen3-14B), with individual speedups of 2.51–3.39×. Approximate generated-token counts matched in all twelve comparisons, and query-plus-decoding latencies were nearly identical.

We also report a limitation: an exploratory 150-short-chunk request (14.8K tokens) achieves only 0.993×, indicating that per-chunk execution overhead can offset computational savings. These large-chunk results should not be generalized to arbitrary chunk sizes or production serving systems.

Q5. EPIC comparison at comparable budgets

EPIC-8/16 correct the first 8/16 tokens per applicable chunk, not 8%/16%. In our HotpotQA evaluation, EPIC-8 selects approximately 7.5–7.7% of eligible tokens, versus approximately 5–6% for LETHE-K.

Despite its smaller correction budget, LETHE-K achieves higher EM on all three models:

  • Qwen3-8B: 0.632 vs. 0.538 (EPIC-8)
  • Llama-3.1-8B: 0.594 vs. 0.526
  • Qwen3-14B: 0.610 vs. 0.518

LETHE-K also exceeds EPIC-16 by 7.1 EM percentage points on average, despite EPIC-16 using approximately twice EPIC-8's correction budget. This establishes an accuracy advantage at a lower token-correction budget, not a directly measured equal-FLOP or equal-latency EPIC comparison.

We appreciate the reviewer's suggestions. The revisions provide additional evidence while clarifying the limitations of offline ranking, cache preparation, and chunk-granularity-dependent latency.

Thank you to the authors for the detailed response and additional experiments. I appreciate the effort to address my concerns, and the new results help strengthen the paper. However, I still have some concerns about the robustness of the method across different chunk configurations, which has not been sufficiently evaluated. Therefore, I will maintain my original rating.

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

The paper introduce a training-free approach for reusing KVCache states when a request contains a non-prefix subset of previously processed chunks. LETHE compares a chunk’s KV states with and without the surrounding context to identify the tokens most affected by that context. At inference time, it adjusts the cached keys to their new positions and recomputes only those tokens. Experiments report substantial reductions in executed FLOPs and up to approximately 6x prefill speedup at 10000 reusable-context tokens.

Critical strengths
  1. It requires no additional training or modification of the base model

  2. It skips projections, attention-query computation, and feed-forward computation for reused token positions.

  3. On the evaluated Qwen models, some configurations remain close to full-recomputation accuracy while eliminating a large fraction of full prompt FLOPs.

  4. The paper acknowledges short-context slowdown, non-monotonic accuracy with increasing recomputation, weaker Llama performance, and the need for a model-specific identifier-refresh rule.

Critical weaknesses
  1. It can only assemble retrieved chunks in the relative order used to construct the shared cache. This prevents query-specific relevance ordering and may be problematic for chronological, contradictory, or multi-hop evidence

  2. Shared v.s. solo divergence measures the combined influence of all preceding chunks. It cannot identify which particular excluded chunk affected a token.

  3. The divergence ranking is not compared with random, positional, attention-based, hidden-state, or query-aware selection at the same recomputation budget.

  4. The evaluation includes only three models from two families, 500 HotpotQA questions, and 200 BFCL questions. BFCL contains only 2–4 candidate functions per query

  5. Every chunk must be processed in both shared and standalone contexts, but the paper does not report the number of queries required to compensate this construction cost.

Questions for authors
  1. How sensitive are accuracy and recomputation cost to the shared-cache build order? Please report results across multiple random, relevance-based, and reversed orders.

  2. Could the authors provide a more detailed analysis showing that key divergence predicts downstream output error better than value or hidden-state divergence?

  3. How does the proposed divergence ranking compare with random, positional, attention-based, or query-aware token selection under the same recomputation budget?

  4. Were K, M, P10, P20, and P30 selected using a separate validation set, or were the best configurations selected from the reported evaluation results?

2 comments
AuthorsOpenReview ↗

Additional Experiments and Clarifications on Cache Ordering, Divergence Ranking, and Configuration Selection

thank for the review questions.

Q1. Sensitivity to shared-cache build order

We evaluated a complete reversal of the original seeded-random chunk order. For each ordering, we rebuilt the shared and solo caches and reran Baseline, LETHE-M, LETHE-P20, and EPIC-16 on the same 500 HotpotQA questions across all three models. Importantly, Baseline used the corresponding passage order, ensuring an order-matched comparison.

ModelBaseline (original / reversed)LETHE-M (original / reversed)LETHE-P20 (original / reversed)
Qwen3-8B.634 / .644.632 / .616.626 / .622
Llama-3.1-8B.646 / .650.604 / .600.618 / .610
Qwen3-14B.616 / .642.614 / .634.602 / .626

Changing the order affects full recomputation itself, and LETHE exhibits additional order sensitivity. Nevertheless, both LETHE configurations outperform EPIC-16 under both evaluated orders. These results establish behavior under two substantially different orderings, not order invariance. Multiple independently shuffled or relevance-based orders remain untested.

The full results appear in Appendix E, Table 11.

Q2. Key versus value and hidden-state divergence

We compared three offline ranking signals: key (K), value (V), and normalized pre-QKV hidden-state (H) divergence. All use the same shared caches, requests, and recomputation implementation, with a fixed 10% per-chunk token budget.

ModelK-P10 EMV-P10 EMH-P10 EM
Qwen3-8B.632.626.632
Llama-3.1-8B.582.588.586
Qwen3-14B.608.608.606

The three signals achieve comparable accuracy, and K is not consistently superior. On a separate 200-chunk analysis, K and H top-10% selection sets overlap by approximately 80%; K and V show similar overlap.

We therefore retain K as a practical offline divergence signal, without claiming it predicts downstream output errors better than V or H. The results support substantial agreement in selected positions, but aggregate accuracy and ranking overlap do not establish a causal relationship with individual output errors.

See Section 3.2 and Appendix F, Table 12.

Q3. Comparison with alternative token-selection strategies

We performed two additional controlled comparisons.

First, we recomputed the most versus least K-divergent tokens at identical 10% and 20% budgets, using 500 HotpotQA questions per model.

ModelTop10 / Last10 EMTop20 / Last20 EM
Qwen3-8B.632 / .614.626 / .610
Llama-3.1-8B.582 / .566.618 / .574
Qwen3-14B.608 / .602.602 / .594

High-divergence selection performs better in all six comparisons, supporting the usefulness of prioritizing divergent positions.

Second, we evaluated 10 uniform-random seeds on the first 100 HotpotQA questions with Llama-3.1-8B, holding the recomputation budget at 10%. LETHE-Top10 achieves .640 EM, compared with .599 mean EM for random selection (range .580–.620) and .580 EM for least-divergent selection. LETHE outperforms all ten observed random trials. This is a controlled 100-question, single-model result, not a claim of universal superiority.

EPIC provides an existing positional-method comparison in our main evaluation, but differs from LETHE in cache construction; it is not a pure positional-selection ablation on the same shared cache at a strictly matched budget.

For attention-based and query-aware strategies, LETHE makes a deliberate design trade-off: query-dependent scoring can exploit request-specific relevance but can require additional inference-time work. LETHE instead computes and stores divergence rankings offline for reuse across requests. We do not claim an empirical accuracy advantage over these strategies at matched budgets without a direct experiment.

The new results and discussion appear in Appendix F, Tables 12–13, and Section 6.

Q4. Selection of K, M, P10, P20, and P30

No separate validation set was used to select these configurations. The five settings were chosen as representative operating points for two design families:

  • P10/P20/P30: Fixed 10%, 20%, and 30% recomputation budgets to examine the accuracy–computation trade-off.
  • K/M: Adaptive per-chunk budgets based on divergence thresholds of μ + 2σ and μ + σ, respectively.

These were not selected by searching for the highest accuracy on the reported evaluation questions. All five configurations evaluated in the primary study are reported; no additional budget configurations were tested and discarded based on their performance.

We have clarified this distinction in Section 4 (Experiments).

We appreciate the reviewer's suggestions. The additional experiments strengthen the evidence for divergence-guided recomputation while clarifying its limitations, particularly with respect to build-order sensitivity, query-independent token ranking, and the absence of universal superiority claims.

Thank you for your responses and the additional experiments. However, my concerns outlined in the Weaknesses section remain unaddressed. Therefore, I will maintain my original score.

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

This paper introduces LETHE, a training-free approach to KV-cache reuse for non-prefix chunks. The idea is that you keep a shared cache with chunks from many requests where the KV cache entries have interacted with their context, but then you selectively correct the influence of that context when you reuse the cache entry with a different context. In order to do this, every time a chunk enters the KV-cache, in addition to the cache itself, you also store a per-token divergence ranking. Then when you try to use the chunk, you recompute entries for the highest-divergence tokens. The authors propose a few schemes for recompilations that have different accuracy/cost tradeoffs.

Critical strengths

I think non-prefix KV cache reuse is an important topic, and although I can't claim an encyclopedic understanding of other techniques in this field, I've never seen a scheme like the one the authors propose. It's great to see that when using it, one can save significant compute cost during deployment.

Critical weaknesses

My biggest concern with the paper is that it has only been tested on two relatively simple benchmarks. I would expect it to be fairly straightforward to measure this approach on other benchmarks and show more convincingly that it generalizes. I'm also not entirely clear on the system-level interactions with KV-cache size and deployment cost. There are a lot of effects here: making the KV-cache large generally makes it necessary to perform inference on smaller batches, in order to fit everything in fast memory, which then lowers the efficiency of the compute platform.

Questions for authors

How are chunks evicted from the cache? How do you size the shared cache? It appears you benchmarked at BS=1 only, but how does this approach work for larger batch sizes? I'd expect the speedup to go down but did not see that in the paper.

1 comment
Area_Chair_7UX1OpenReview ↗

Does authors' response address your concerns?

Thank you for your review! Could you check the authors’ response and clarify whether it addresses your original concerns? Many thanks!

AC

Comments on the paper

2 comments
AuthorsOpenReview ↗

Cache Construction Overhead: Additional Measurements

We thank the reviewers for raising the concern about cache construction overhead. We have added an explicit measurement and discussion in Appendix D of the revised manuscript.

Construction cost. LETHE builds each shared KV-cache pool once, followed by solo-cache construction and divergence ranking. We measured the end-to-end preparation time for one HotpotQA pool containing 100 questions, 200 chunks, and approximately 20k tokens:

ModelShared cacheSolo cache + analysisTotal
Qwen3-8B14.8 s20.0 s34.8 s
Llama-3.1-8B13.3 s18.5 s31.8 s
Qwen3-14B19.5 s27.1 s46.6 s

These measurements include divergence ranking, I/O, and GPU synchronization.

Amortization and intended workloads. Cache construction is performed once per pool, not per inference request. It can be performed offline or asynchronously, allowing subsequent requests to reuse the prepared KV states and token rankings without repeating construction. LETHE primarily targets reuse-intensive workloads, such as RAG and agentic applications with recurring context or tool definitions.

We acknowledge that construction still consumes computational resources, particularly in online incremental scenarios, and that its amortized benefit depends on reuse frequency and working-set stability. We have clarified this trade-off in Section 6 (Limitations).

Thus, LETHE trades additional one-time preparation cost for substantially reduced online prefill computation across repeated requests.

AuthorsOpenReview ↗

Chunk Ordering: Additional Sensitivity Experiment

We thank the reviewers for raising the question of sensitivity to chunk ordering. We have added an additional experiment in Appendix E of the revised manuscript.

Original evaluation. As described in Sections 3.4 and 4, LETHE's original evaluation already uses a randomized build order within each shared-cache pool (fixed seed 42), rather than a manually optimized ordering. During inference, selected chunks preserve their relative build order to maintain consistency with the causal interactions encoded in the shared cache.

Additional order-reversal experiment. We reversed the entire original randomized pool order, rebuilt the caches, and reran the methods, including full recomputation, on the same 500 HotpotQA questions. The results below report EM accuracy:

ModelOrderBaselineLETHE-MLETHE-P20EPIC-16
Qwen3-8BOriginal.634.632.626.562
Reversed.644.616.622.566
Llama-3.1-8BOriginal.646.604.618.528
Reversed.650.600.610.552
Qwen3-14BOriginal.616.614.602.532
Reversed.642.634.626.544

Interpretation. Full-recomputation Baseline accuracy also changes with chunk order, indicating that some sensitivity originates from the underlying model rather than KV reuse. LETHE exhibits additional order-dependent approximation effects, but remains effective under both evaluated orderings and consistently outperforms EPIC-16 across all three models.

We do not claim that LETHE is order-invariant. Its shared-cache construction intentionally preserves causal interactions among chunks, which depend on build order. For workloads where a particular chunk ordering is important for accuracy or task requirements, LETHE can construct a separate shared-cache pool using that ordering. This allows the method to accommodate order-specific workloads without changing its reuse mechanism, at the cost of additional one-time cache preparation, as discussed in Section 3.4.

Overall, the experiment demonstrates that LETHE does not require a specially optimized ordering to remain effective, while acknowledging that order-sensitive applications may benefit from dedicated cache pools.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.