HashEvict: A Pre-Attention KV Cache Eviction Strategy using Locality-Sensitive Hashing

• URL: http://arxiv.org/abs/2412.16187v3
• Date: Wed, 04 Jun 2025 22:37:29 GMT
• Title: HashEvict: A Pre-Attention KV Cache Eviction Strategy using Locality-Sensitive Hashing
• Authors: Minghui Liu, Tahseen Rabbani, Tony O'Halloran, Ananth Sankaralingam, Mary-Anne Hartley, Furong Huang, Cornelia Fermüller, Yiannis Aloimonos,
• Abstract summary: We introduce HashEvict, an algorithm that uses locality-sensitive hashing (LSH) to compress the KV cache.<n>HashEvict can compress the KV cache by 30%-70% while maintaining high performance across reasoning, multiple-choice, long-context retrieval and summarization tasks.
• Score: 33.85061974392119
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Transformer-based large language models (LLMs) use the key-value (KV) cache to significantly accelerate inference by storing the key and value embeddings of past tokens. However, this cache consumes significant GPU memory. In this work, we introduce HashEvict, an algorithm that uses locality-sensitive hashing (LSH) to compress the KV cache. HashEvict quickly locates tokens in the cache that are cosine dissimilar to the current query token. This is achieved by computing the Hamming distance between binarized Gaussian projections of the current token query and cached token keys, with a projection length much smaller than the embedding dimension. We maintain a lightweight binary structure in GPU memory to facilitate these calculations. Unlike existing compression strategies that compute attention to determine token retention, HashEvict makes these decisions pre-attention, thereby reducing computational costs. Additionally, HashEvict is dynamic - at every decoding step, the key and value of the current token replace the embeddings of a token expected to produce the lowest attention score. We demonstrate that HashEvict can compress the KV cache by 30%-70% while maintaining high performance across reasoning, multiple-choice, long-context retrieval and summarization tasks.

Related papers

• Cache What Lasts: Token Retention for Memory-Bounded KV Cache in LLMs [26.951325519894525]
  We propose a novel approach that learns each token's intrinsic importance at creation time via a lightweight retention gate.<n>We show that it consistently outperforms strong eviction and learnable retrieval baselines, especially in low-memory regimes.<n>It even surpasses full-cache models in some settings, showing that selective retention can serve as a form of regularization.
  arXiv  Detail & Related papers  (2025-12-03T00:20:35Z)
• KVReviver: Reversible KV Cache Compression with Sketch-Based Token Reconstruction [20.53279247581787]
  We propose KVReviver, a reversible KV cache compression method based on the sketch algorithm.<n>In 2k-length contexts, it requires only 10% of KV Cache budget while maintaining identical end-to-end inference accuracy.<n>For 32k-length contexts, it achieves equivalent or comparable accuracy 2% accuracy loss.
  arXiv  Detail & Related papers  (2025-12-01T03:59:20Z)
• SemShareKV: Efficient KVCache Sharing for Semantically Similar Prompts via Token-Level LSH Matching [0.8307668828380427]
  We propose textitSemShareKV, a KV cache sharing and compression framework for large language models (LLMs)<n>Instead of relying on exact token matches, SemShareKV applies fuzzy token matching using locality-sensitive hashing (LSH) on token embeddings and incorporates Rotary Position Embedding (RoPE) to better preserve positional information.<n> Experiments on diverse summarization datasets show up to 6.25$times$ speedup and 42% lower GPU memory usage with 5k tokens input, with negligible quality degradation.
  arXiv  Detail & Related papers  (2025-09-29T14:16:13Z)
• 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)
• Spotlight Attention: Towards Efficient LLM Generation via Non-linear Hashing-based KV Cache Retrieval [67.21678698740267]
  We introduce Spotlight Attention, a novel method that employs non-linear hashing functions to optimize the embedding distribution of queries and keys.<n>We also develop a lightweight, stable training framework using a Bradley-Terry ranking-based loss.
  arXiv  Detail & Related papers  (2025-08-27T10:11:27Z)
• Mustafar: Promoting Unstructured Sparsity for KV Cache Pruning in LLM Inference [2.0449242727404235]
  unstructured sparsity significantly improves KV cache compression for LLMs.<n>We find per-token magnitude-based pruning as highly effective for both Key and Value caches under unstructured sparsity.
  arXiv  Detail & Related papers  (2025-05-28T22:32:15Z)
• TokenButler: Token Importance is Predictable [8.514853311344458]
  Large Language Models (LLMs) rely on the Key-Value (KV) Cache to store token history, enabling efficient decoding of tokens. Prior research has shown that only a small subset of tokens contribute meaningfully to each decoding step. We introduce TokenButler, a high-granularity, query-aware predictor that learns to identify these critical tokens.
  arXiv  Detail & Related papers  (2025-03-10T16:41:14Z)
• ChunkKV: Semantic-Preserving KV Cache Compression for Efficient Long-Context LLM Inference [61.412894960600205]
  Large Language Models (LLMs) require significant GPU memory when processing long texts.<n>ChunkKV reimagines KV cache compression by treating semantic chunks as basic compression units.<n>Result: ChunkKV outperforms state-of-the-art methods by up to 8.7% in precision.
  arXiv  Detail & Related papers  (2025-02-01T03:49:47Z)
• HashAttention: Semantic Sparsity for Faster Inference [91.54218318798603]
  HashAttention is a principled approach casting pivotal token identification as a recommendation problem.<n>It efficiently identifies pivotal tokens for a given query in this Hamming space using bitwise operations.<n>It can reduce the number of tokens used by a factor of $1/32times$ for the Llama-3.1-8B model with LongBench.
  arXiv  Detail & Related papers  (2024-12-19T02:34:15Z)
• CSR:Achieving 1 Bit Key-Value Cache via Sparse Representation [63.65323577445951]
  We propose a novel approach called Cache Sparse Representation (CSR)<n>CSR transforms the dense Key-Value cache tensor into sparse indexes and weights, offering a more memory-efficient representation during LLM inference.<n>Our experiments demonstrate CSR achieves performance comparable to state-of-the-art KV cache quantization algorithms.
  arXiv  Detail & Related papers  (2024-12-16T13:01:53Z)
• ClusterKV: Manipulating LLM KV Cache in Semantic Space for Recallable Compression [10.003118268356017]
  Long context poses significant challenges for inference efficiency.<n>We introduce ClusterKV, which recalls tokens at the granularity of semantic clusters.<n>Experiment results show that ClusterKV attains negligible accuracy loss across various tasks with 32k context lengths.
  arXiv  Detail & Related papers  (2024-12-04T10:58:27Z)
• Compressing KV Cache for Long-Context LLM Inference with Inter-Layer Attention Similarity [24.118503938098307]
  textscPoD allocates memory according to token importance.<n>textscPoD reduces KV cache memory usage by up to 35% without compromising performance.
  arXiv  Detail & Related papers  (2024-12-03T08:29:27Z)
• Efficient Inference of Vision Instruction-Following Models with Elastic Cache [76.44955111634545]
  We introduce Elastic Cache, a novel strategy for efficient deployment of instruction-following large vision-language models. We propose an importance-driven cache merging strategy to prune redundancy caches. For instruction encoding, we utilize the frequency to evaluate the importance of caches. Results on a range of LVLMs demonstrate that Elastic Cache not only boosts efficiency but also notably outperforms existing pruning methods in language generation.
  arXiv  Detail & Related papers  (2024-07-25T15:29:05Z)
• ZipCache: Accurate and Efficient KV Cache Quantization with Salient Token Identification [19.985314022860432]
  KV cache stores key and value states from previous tokens to avoid re-computation. KV cache compression seeks to discern the saliency of tokens, preserving vital information while aggressively compressing those of less importance. We present ZipCache, an accurate and efficient KV cache quantization method for LLMs.
  arXiv  Detail & Related papers  (2024-05-23T07:37:16Z)
• Get More with LESS: Synthesizing Recurrence with KV Cache Compression for Efficient LLM Inference [78.65321721142624]
  We focus on a memory bottleneck imposed by the key-value ( KV) cache. Existing KV cache methods approach this problem by pruning or evicting large swaths of relatively less important KV pairs. We propose LESS, a simple integration of a constant sized cache with eviction-based cache methods.
  arXiv  Detail & Related papers  (2024-02-14T18:54:56Z)
• SubGen: Token Generation in Sublinear Time and Memory [48.35076900702408]
  Large language models (LLMs) have extensive memory requirements for token generation. In this work, we focus on developing an efficient compression technique for the KV cache. We have devised a novel caching method with sublinear complexity, employing online clustering on key tokens and online $ell$ sampling on values. Not only does this algorithm ensure a sublinear memory footprint and sublinear time complexity, but we also establish a tight error bound for our approach.
  arXiv  Detail & Related papers  (2024-02-08T22:17:40Z)
• KIVI: A Tuning-Free Asymmetric 2bit Quantization for KV Cache [67.9776980972508]
  We develop a tuning-free 2bit KV cache quantization algorithm named KIVI. KIVI can enable Llama, Falcon, and Mistral models to maintain almost the same quality while using $mathbf2.6times$ less peak memory.
  arXiv  Detail & Related papers  (2024-02-05T06:06:47Z)
• Reinforcing Short-Length Hashing [61.75883795807109]
  Existing methods have poor performance in retrieval using an extremely short-length hash code. In this study, we propose a novel reinforcing short-length hashing (RSLH) In this proposed RSLH, mutual reconstruction between the hash representation and semantic labels is performed to preserve the semantic information. Experiments on three large-scale image benchmarks demonstrate the superior performance of RSLH under various short-length hashing scenarios.
  arXiv  Detail & Related papers  (2020-04-24T02:23:52Z)

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.