Recall Before You Rank: Similarity-Guided Top-$K$ Reuse for Efficient Long-Context Attention

• URL: http://arxiv.org/abs/2607.27692v1
• Date: Thu, 30 Jul 2026 05:25:23 GMT
• Title: Recall Before You Rank: Similarity-Guided Top-$K$ Reuse for Efficient Long-Context Attention
• Abstract summary: ReTopK is a training-free method that accelerates dynamic Top-$K$ attention by reusing historical retrieval decisions.<n>At 128K with $K=512$, ReTopK incurs only a 0.50% perplexity increase over Exact Top-$K$ while accelerating attention computation by $3.07times$.
• Score: 4.6833133124119275
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Top-$K$ sparse attention reduces the cost of Softmax and value aggregation by attending to only a small subset of key--value (KV) entries. However, identifying this subset still requires scoring the current query against the full KV cache and performing global Top-$K$ selection, leaving selector cost linear in context length and limiting the practical efficiency of sparse attention for long-context decoding. In this paper, we introduce ReTopK, a training-free method that accelerates dynamic Top-$K$ attention by reusing historical retrieval decisions. ReTopK builds on the observation that similar queries often attend to overlapping supports and that partially overlapping supports can still preserve most of the Exact Top-$K$ attention mass. For each attention head, it maintains a bounded cache of historical query--support pairs, retrieves the most similar cached queries for each new query, unions their stored supports with a recent window, and reranks only the resulting compact candidate set using exact current-query scores. A similarity-based fallback invokes full-history Exact Top-$K$ when reuse is unreliable, while periodic exact refreshes limit cache drift. ReTopK retains the complete KV cache and reuses only selected indices, rather than historical scores, attention weights, or outputs. Across 16K--128K contexts, ReTopK achieves the lowest PG19 perplexity and the highest NIAH and LongBench scores among the evaluated approximate methods. At 128K with $K=512$, ReTopK incurs only a 0.50\% perplexity increase over Exact Top-$K$ while accelerating attention computation by $3.07\times$.

Related papers

• CEDAR: Error-Bounded Residual Routing for Efficient Long-Context Attention [19.273437346867595]
  Post-hoc sparse attention accelerates long-context prefill by routing each query to a small set of token-level interactions.<n>We introduce Coarse-to-fine Error-aware Dynamic Attention (CEDAR)<n>CEDAR is a coarse-to-fine method that keeps the language model frozen while preserving global coverage.
  arXiv  Detail & Related papers  (2026-09-07T08:56:47Z)
• CateKV: On Sequential Consistency for Long-Context LLM Inference Acceleration [67.17709877327232]
  Cate KV is a hybrid KV cache method that retains only critical token information for consistent heads.<n>Cate KV reduces memory usage by up to $2.72times$ and accelerates decoding by $2.18times$ in single-sample inputs.
  arXiv  Detail & Related papers  (2026-08-31T06:02:37Z)
• Back from the Future: Key-Value Cache Management by Counter-Causal Surprise [67.1056509495879]
  Key-value (KV) cache management through compression and eviction strategies has emerged as an important research direction in recent years.<n>We propose a simple yet effective KV eviction scheme motivated by the insight that past tokens which can be well-predicted from more recent tokens are redundant.<n>We evaluate our strategy on various open-source LLMs and benchmark datasets showing competitive or improved performance over other state-of-the-art methods.
  arXiv  Detail & Related papers  (2026-07-30T02:42:51Z)
• Make Each Token Count: Towards Improving Long-Context Performance with KV Cache Eviction [65.710271475739]
  We introduce a global retention-based KV eviction method that learns each token's future utility under a unified memory budget.<n>We show that our method substantially reduces KV memory while matching or surpassing full-cache inference.<n>These results suggest that learned, globally calibrated KV eviction is not only a compression technique, but also a mechanism for improving long-context reasoning.
  arXiv  Detail & Related papers  (2026-05-10T16:47:50Z)
• ProphetKV: User-Query-Driven Selective Recomputation for Efficient KV Cache Reuse in Retrieval-Augmented Generation [22.835149054167122]
  We propose Prophet KV, a user-query-driven KV Cache reuse method for RAG scenarios.<n> Prophet KV prioritizes tokens based on their semantic relevance to the user query.<n>Our evaluation results show that Prophet KV retains 96%-101% of full-prefill accuracy with only a 20% recomputation ratio.
  arXiv  Detail & Related papers  (2026-01-31T09:53:31Z)
• LLM Cache Bandit Revisited: Addressing Query Heterogeneity for Cost-Effective LLM Inference [87.57291812372848]
  We treat optimal cache selection as a knapsack problem and employ an accumulation-based strategy to balance computational overhead and cache updates.<n>We prove that the regret of our algorithm achieves an $O(sqrtMNT)$ bound, improving the coefficient of $sqrtMN$ compared to the $O(MNsqrtT)$ in Berkeley.<n>We also provide a problem-dependent bound, which was absent in previous works.
  arXiv  Detail & Related papers  (2025-09-19T01:39:08Z)
• Judge Q: Trainable Queries for Optimized Information Retention in KV Cache Eviction [53.83828564664595]
  Large language models (LLMs) utilize key-value ( KV) cache to store historical information during sequence processing.<n>Current methods for KV cache eviction typically utilize the last window from the pre-filling phase as queries to compute the KV importance scores for eviction.<n>We propose Judge Q, a novel training method which incorporates a soft token list.
  arXiv  Detail & Related papers  (2025-09-13T03:34:12Z)
• Lookahead Q-Cache: Achieving More Consistent KV Cache Eviction via Pseudo Query [48.52389201779425]
  KV cache memory usage grows substantially with longer text sequences.<n>Existing KV cache eviction methods prune tokens using prefilling-stage attention scores.<n>Lookahead Q-Cache generates low-cost pseudo lookahead queries to better approximate the true decoding-stage queries.
  arXiv  Detail & Related papers  (2025-05-24T10:34:38Z)
• Activation-aware Probe-Query: Effective Key-Value Retrieval for Long-Context LLMs Inference [56.71209737306054]
  We propose textbfActQKV, a training-free, textbfActivation-aware approach that dynamically determines probe-textbfQuery and leverages it to retrieve the relevant textbfKV pairs for inference.<n>Experiments on the Long-Bench and $infty$ Benchmarks demonstrate its state-of-the-art performance with competitive inference quality and resource efficiency.
  arXiv  Detail & Related papers  (2025-02-19T08:50:44Z)
• A$^2$ATS: Retrieval-Based KV Cache Reduction via Windowed Rotary Position Embedding and Query-Aware Vector Quantization [17.342214950859145]
  Long context large language models (LLMs) pose significant challenges for efficient serving due to the large memory footprint and high access overhead of KV cache.<n>Retrieval-based KV cache reduction methods can mitigate these challenges, typically by offloading the complete KV cache to CPU and retrieving necessary tokens on demand during inference.<n>This paper proposes A$2$ATS, a novel retrieval-based KV cache reduction method.
  arXiv  Detail & Related papers  (2025-02-18T09:11:51Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.