- 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
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.
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.
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:
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.