Identify Critical KV Cache in LLM Inference from an Output Perturbation Perspective

• URL: http://arxiv.org/abs/2502.03805v1
• Date: Thu, 06 Feb 2025 06:31:47 GMT
• Title: Identify Critical KV Cache in LLM Inference from an Output Perturbation Perspective
• Authors: Yuan Feng, Junlin Lv, Yukun Cao, Xike Xie, S Kevin Zhou,
• Abstract summary: We propose a perturbation-constrained selection algorithm to identify critical KV cache entries.<n>Our algorithm achieves lower output perturbations in over 92% attention heads in Llama model.
• Score: 19.447729423696096
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Large language models have revolutionized natural language processing but face significant challenges of high storage and runtime costs, due to the transformer architecture's reliance on self-attention, particularly the large Key-Value (KV) cache for long-sequence inference. Recent efforts to reduce KV cache size by pruning less critical entries based on attention weights remain empirical and lack formal grounding. This paper presents a formal study on identifying critical KV cache entries by analyzing attention output perturbation. Our analysis reveals that, beyond attention weights, the value states within KV entries and pretrained parameter matrices are also crucial. Based on this, we propose a perturbation-constrained selection algorithm that optimizes the worst-case output perturbation to identify critical entries. Evaluations on the Needle-in-a-Haystack test and Longbench benchmark show our algorithm enhances state-of-the-art cache eviction methods. Further empirical analysis confirms that our algorithm achieves lower output perturbations in over 92% attention heads in Llama model, thereby providing a significant improvement over existing methods.

Related papers

• ForesightKV: Optimizing KV Cache Eviction for Reasoning Models by Learning Long-Term Contribution [84.41751286055909]
  We develop a training-based KV cache eviction framework that learns to predict which KV pairs to evict during longtext generations.<n>We formulate cache eviction as a Markov Decision Process and apply the GRPO algorithm to mitigate the significant language modeling loss increase on low-entropy tokens.
  arXiv  Detail & Related papers  (2026-02-03T07:16:51Z)
• MixKVQ: Query-Aware Mixed-Precision KV Cache Quantization for Long-Context Reasoning [30.527521568636242]
  Long Chain-of-Thought (CoT) reasoning has significantly advanced the capabilities of Large Language Models (LLMs)<n>Existing low-bit quantization methods often exhibit severe performance degradation on complex reasoning tasks.<n>We propose MixKVQ, a novel plug-and-play method that introduces a lightweight, query-aware algorithm to identify and preserve critical key channels.
  arXiv  Detail & Related papers  (2025-12-22T09:44:26Z)
• SpecAttn: Speculating Sparse Attention [1.6921396880325779]
  We introduce SpecAttn, a novel training-free approach that seamlessly integrates with speculative decoding techniques.<n>Our key insight is to exploit the attention weights already computed by the draft model during speculative decoding to identify important tokens for the target model.<n>SpecAttn achieves over 75% reduction in key-value cache accesses with a mere 15.29% increase in perplexity on the PG-19 dataset.
  arXiv  Detail & Related papers  (2025-10-31T17:12:34Z)
• KVSink: Understanding and Enhancing the Preservation of Attention Sinks in KV Cache Quantization for LLMs [0.0]
  Key-Value ( KV) cache quantization has become a widely adopted optimization technique for large language models (LLMs) inference.<n>Recent studies have emphasized the importance of preserving the original precision of KVs for the first few tokens to ensure the protection of attention sinks.<n>We introduce textittextbf KVSink, a plug-and-play method that effectively predicts sink tokens with negligible overhead.
  arXiv  Detail & Related papers  (2025-08-06T09:40:09Z)
• SmallKV: Small Model Assisted Compensation of KV Cache Compression for Efficient LLM Inference [71.20542521694524]
  SmallKV is a small model assisted compensation method for KV cache compression.<n>We show that SmallKV achieves 1.75 - 2.56 times higher throughput than baseline methods.
  arXiv  Detail & Related papers  (2025-08-03T09:15:36Z)
• KV-Latent: Dimensional-level KV Cache Reduction with Frequency-aware Rotary Positional Embedding [72.12756830560217]
  Large language models (LLMs) based on Transformer Decoders have become the preferred choice for conversational generative AI.<n>Despite the overall superiority of the Decoder architecture, the gradually increasing Key-Value cache during inference has emerged as a primary efficiency bottleneck.<n>By down-sampling the Key-Value vector dimensions into a latent space, we can significantly reduce the KV Cache footprint and improve inference speed.
  arXiv  Detail & Related papers  (2025-07-15T12:52:12Z)
• AhaKV: Adaptive Holistic Attention-Driven KV Cache Eviction for Efficient Inference of Large Language Models [14.013793473739236]
  We propose Adaptive holistic attention KV (Aha KV) to address the bias of the accumulated attention score.<n>Aha KV successfully mitigates bias and retains crucial tokens across global context.
  arXiv  Detail & Related papers  (2025-06-04T09:25:53Z)
• AirCache: Activating Inter-modal Relevancy KV Cache Compression for Efficient Large Vision-Language Model Inference [11.73134417321505]
  We propose AirCache, a novel KV cache compression method aimed at accelerating LVLMs inference. We show that our method achieves comparable performance to the full cache while retaining only 10% of visual KV cache.
  arXiv  Detail & Related papers  (2025-03-31T11:13:18Z)
• AttentionPredictor: Temporal Pattern Matters for Efficient LLM Inference [51.1972443343829]
  We propose AttentionPredictor, which is the first learning-based critical token identification approach.<n> AttentionPredictor accurately predicts the attention score while consuming negligible memory.<n>We also propose a cross-token critical cache prefetching framework that hides the token time overhead to accelerate the decoding stage.
  arXiv  Detail & Related papers  (2025-02-06T13:41:46Z)
• More Tokens, Lower Precision: Towards the Optimal Token-Precision Trade-off in KV Cache Compression [71.42818367729573]
  In large language models (LLMs), the memory usage of KV cache has become a critical bottleneck during inference. The mainstream KV compression methods, including KV pruning and KV quantization, primarily focus on either token or precision dimension separately. In this paper, we comprehensively investigate the token-precision trade-off in KV cache compression.
  arXiv  Detail & Related papers  (2024-12-17T09:20:31Z)
• Cross-Self KV Cache Pruning for Efficient Vision-Language Inference [19.062950348441426]
  KV cache pruning has emerged as a promising technique for reducing memory and computation costs in long-context auto-regressive generation.<n>We propose decomposing attention scores into intra-modality attention (within the same modality) and inter-modality attention (across modalities)<n>Our final training-free method, textbfCross-textbfSelf textbfPruning (CSP), achieves competitive performance compared to models with full KV caches.
  arXiv  Detail & Related papers  (2024-12-05T22:47:17Z)
• PrefixKV: Adaptive Prefix KV Cache is What Vision Instruction-Following Models Need for Efficient Generation [65.36715026409873]
  Key-value (KV) cache, necessitated by the lengthy input and output sequences, notably contributes to the high inference cost. We present PrefixKV, which reframes the challenge of determining KV cache sizes for all layers into the task of searching for the optimal global prefix configuration. Our method achieves the state-of-the-art performance compared with others.
  arXiv  Detail & Related papers  (2024-12-04T15:48:59Z)
• Anchor Attention, Small Cache: Code Generation with Large Language Models [15.94784908771546]
  Current practices in NLP often use sparse attention which may, unfortunately, lead to substantial inaccuracies, or hallucinations, in code generation tasks. We propose a novel approach, AnchorCoder, which features token-wise anchor attention designed to extract and compress contextual information. It can consistently achieve a significant (at least 70%) reduction in KV cache requirements, while preserving the majority of model's performance.
  arXiv  Detail & Related papers  (2024-11-11T02:47:05Z)
• ThinK: Thinner Key Cache by Query-Driven Pruning [63.13363917871414]
  Large Language Models (LLMs) have revolutionized the field of natural language processing, achieving unprecedented performance across a variety of applications. This paper focuses on the long-context scenario, addressing the inefficiencies in KV cache memory consumption during inference. We propose ThinK, a novel query-dependent KV cache pruning method designed to minimize attention weight loss while selectively pruning the least significant channels.
  arXiv  Detail & Related papers  (2024-07-30T17:59:08Z)
• Ada-KV: Optimizing KV Cache Eviction by Adaptive Budget Allocation for Efficient LLM Inference [19.447729423696096]
  Large Language Models have excelled in various domains but face efficiency challenges due to the growing Key-Value (KV) cache.<n>Recent efforts aim to reduce KV cache size by evicting vast non-critical cache elements during runtime.<n>We propose Ada-KV, the first head-wise adaptive budget allocation strategy.
  arXiv  Detail & Related papers  (2024-07-16T09:53:32Z)
• CItruS: Chunked Instruction-aware State Eviction for Long Sequence Modeling [52.404072802235234]
  We introduce Chunked Instruction-aware State Eviction (CItruS), a novel modeling technique that integrates the attention preferences useful for a downstream task into the eviction process of hidden states. Our training-free method exhibits superior performance on long sequence comprehension and retrieval tasks over several strong baselines under the same memory budget.
  arXiv  Detail & Related papers  (2024-06-17T18:34:58Z)
• CORM: Cache Optimization with Recent Message for Large Language Model Inference [57.109354287786154]
  We introduce an innovative method for optimizing the KV cache, which considerably minimizes its memory footprint. CORM, a KV cache eviction policy, dynamically retains essential key-value pairs for inference without the need for model fine-tuning. Our validation shows that CORM reduces the inference memory usage of KV cache by up to 70% with negligible performance degradation across six tasks in LongBench.
  arXiv  Detail & Related papers  (2024-04-24T16:11:54Z)
• No Token Left Behind: Reliable KV Cache Compression via Importance-Aware Mixed Precision Quantization [31.806112535762367]
  Key-Value (KV) Caching has become an essential technique for accelerating the inference speed and throughput of generative Large Language Models(LLMs)
  arXiv  Detail & Related papers  (2024-02-28T06:34:54Z)

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.