EMS: Adaptive Evict-then-Merge Strategy for Head-wise KV Cache Compression Based on Global-Local Importance

Yingxin Li, Ye Li, Yuan Meng, Xinzhu Ma, Zihan Geng, Zhi WangSubmission to ICLR 2025 · Rejected

TL;DR

Large language model (LLM) key-value (KV) cache compression often degrades under extreme compression ratios due to biased token-importance metrics and rigid, single-policy eviction or merging. EMS (Evict-then-Merge Strategy) introduces a balanced Global-Local importance score to remove positional and temporal selection biases, alongside an adaptive, head-wise evict-and-merge framework. By routing discarded tokens into a virtual "zero-class" center, EMS preserves head-wise parallelism and achieves state-of-the-art long-context performance even when retaining as little as 2% of the original KV cache.

What Problem Does This Paper Address?

During autoregressive generation, LLMs store Key-Value (KV) states across previous timesteps to avoid redundant calculations. As context windows scale to tens of thousands of tokens, the KV cache rapidly consumes tens of gigabytes of GPU memory, bottlenecking throughput and batch sizes.

Prior compression strategies suffer from two core limitations:

  1. Biased Token Importance: Global attention accumulation (e.g., $H_2O$) over-favors early tokens due to causal masking accumulation, while local window approaches (e.g., SnapKV) bias heavily toward recent tokens due to positional encoding attenuation.
  2. Coarse Compression Dynamics: Pure eviction permanently drops information, while pure merging accumulates representation errors across steps. Furthermore, attention heads exhibit vastly different levels of redundancy and sparsity across layers. Handling these differences per-head typically breaks the uniform tensor layouts required for parallel GPU computation.

Methods

EMS decouples KV cache management into hybrid token selection and a unified head-wise Evict-then-Merge pipeline:

Input Context Tokens
         │
         ▼
[Global-Local Importance Scoring] ──► Mean-aligns s_Glo and s_Loc, takes element-wise max
         │
         ▼
[3-Way Token Partitioning]
   ├── Local Tokens (K_loc, V_loc) ──► Retained intact
   ├── Important Tokens (N_imp)    ──► Form Class Centers
   ├── Sub-important Tokens (N_tbm)──► To-Be-Merged (TBM) candidates
   └── Irrelevant Tokens (N_irr)   ──► Level 1 Eviction
         │
         ▼
[Joint Key-Value Similarity Matching] ──► R_i,j = cos(k_i, k_j) * cos(v_i, v_j)
         ├── If similarity >= τ: Merge into Class Center (Attention-weighted)
         └── If similarity <  τ: Route to "Zero-Class Center" (Level 2 Eviction as Merge)
  • Global-Local Scoring: Prefilling and decoding phases compute both global accumulated attention ($s_{\text{Glo}}$) and sliding-window local attention ($s_{\text{Loc}}$). The scores are normalized via mean-alignment and fused using an element-wise maximum: $$s_{\text{Glo-Loc}} = \max\left( s_{\text{Glo}} \times \frac{\sum s_{\text{Loc}} / N}{\sum s_{\text{Glo}} / N}, \; s_{\text{Loc}} \right)$$
  • Joint Key-Value Redundancy: Cosine similarity is computed jointly across both keys and values ($R_{i,j} = \cos(k_i, k_j) \cdot \cos(v_i, v_j)$), avoiding the degradation caused by merging similar keys whose corresponding values differ significantly.
  • Unified "Zero-Class" Eviction & Merging: To-be-merged tokens are matched to the nearest class center token. If the similarity is above threshold $\tau$, they are merged via attention-weighted averaging; otherwise, they are assigned to a virtual "zero-class" center. This mathematical unification lets each attention head adaptively choose its own merge-to-evict ratio while preserving fixed cache shapes across heads for parallel GPU execution.
  • Shared Entry Expansion: During runtime execution of a given layer, the compact set of class centers expands back into runtime positions via a lightweight lookup table, minimizing memory footprint outside the active computation step.

Datasets

The authors evaluate EMS on three primary benchmarks across four open LLMs (LLaMA-2-7B-Chat, LLaMA-3-8B-Instruct, LongChat-7B-v1.5-32k, and Mistral-7B-Instruct-v0.2):

  • LongBench: 16 long-context tasks spanning multi-document QA, single-document QA, summarization, few-shot learning, code completion, and synthetic tasks.
  • Needle-in-a-Haystack: Stress-testing retrieval accuracy across 40 context lengths (up to 32k tokens) and 10 retrieval depth percentages.
  • PG19: Perplexity evaluation over continuous text sequences extended to 10× the original model pretraining length (up to 40,000 tokens).

(No new datasets were introduced.)

Key Insights and Ideas

  • Keys and values have distinct similarity distributions: Raw key embeddings naturally exhibit far higher cosine similarity than value embeddings. Pruning or merging based on key similarity alone corrupts value representations, explaining why earlier merge-only methods suffered from error compounding.
  • Earlier layers merge, deeper layers evict: Early Transformer layers exhibit heavy token redundancy, whereas deeper layers display pronounced sparsity. EMS adapts to this continuum naturally at the head level without requiring hand-crafted per-layer compression policies.
  • Eviction is just zero-class clustering: Treating eviction as assignment to a dummy zero center solves the classic GPU scheduling headache of heterogeneous ragged tensors across attention heads.

Key Results

  • LongBench Superiority: Under a strict budget of 256 tokens per head, EMS beats competitive baselines (StreamingLLM, CAM, $H_2O$, SnapKV) across all four tested models, lifting average scores by 1.28 to 17.64 points (most notably rescuing LongChat-7B from complete degradation, scoring 32.54 vs. 14.90 for SnapKV).
  • Needle-in-a-Haystack: On Mistral-7B-Instruct-v0.2 at 32k context, EMS retains 95.9% retrieval accuracy with a cache budget of 512 (under 2% of the context length), outperforming retrieval-specialized SnapKV (95.6%) and $H_2O$ (which collapses to 38.4%).
  • Language Modeling Perplexity: On PG19 at 2%, 5%, and 10% cache limits, EMS consistently records the lowest perplexity among all compression algorithms, whereas full-cache execution collapses past the 4k pretraining boundary.
  • Hardware Throughput: On dual NVIDIA RTX 4090 GPUs (4096 prompt + 8192 generation tokens), EMS enables up to 6.74× throughput improvements over uncompressed models by preventing out-of-memory (OOM) errors and accommodating larger batch sizes.

Limitations and Future Work

  • FlashAttention Compatibility: Global attention score calculation requires access to intermediate attention weight matrices, which standard FlashAttention fuses away. The authors rely on recomputation or probe sampling techniques (e.g., ZipCache/NACL), which adds minor overhead during prefill.
  • Threshold Sensitivity: The pipeline relies on two primary hyperparameters: the redundancy threshold $\tau$ (typically $\sim 0.6$) and the magnification factor $\gamma$ (typically 3–4). While ablations show reasonable robustness, optimal values may vary slightly depending on task type (e.g., precise retrieval vs. broad summarization).
  • Context Length Horizons: Evaluations were conducted up to 32k tokens; testing on ultra-long horizons (100k+ tokens) remains future work.

Summary updated

Abstract

As large language models (LLMs) continue to advance, the demand for higher quality and faster processing of long contexts across various applications is growing. KV cache is widely adopted as it stores previously generated key and value tokens, effectively reducing redundant computations during inference. However, as memory overhead becomes a significant concern, efficient compression of KV cache has gained increasing attention. Most existing methods perform compression from two perspectives: identifying important tokens and designing compression strategies. However, these approaches often produce biased distributions of important tokens due to the influence of accumulated attention scores or positional encoding. Furthermore, they overlook the sparsity and redundancy across different heads, which leads to difficulties in preserving the most effective information at the head level. To this end, we propose EMS to overcome these limitations, while achieving better KV cache compression under extreme compression ratios. Specifically, we introduce a Global-Local score that combines accumulated attention scores from both global and local KV tokens to better identify the token importance. For the compression strategy, we design an adaptive and unified Evict-then-Merge framework that accounts for the sparsity and redundancy of KV tokens across different heads. Additionally, we implement the head-wise parallel compression through a zero-class mechanism to enhance efficiency. Extensive experiments demonstrate our SOTA performance even under extreme compression ratios. EMS consistently achieves the lowest perplexity, improves scores by over 1.28 points across four LLMs on LongBench under a 256 cache budget, and preserves 95\% retrieval accuracy with a cache budget less than 2\% of the context length in the Needle-in-a-Haystack task.
BibTeX
@misc{li2024ems,
  author = {Yingxin Li and Ye Li and Yuan Meng and Xinzhu Ma and Zihan Geng and Zhi Wang},
  title = {{EMS: Adaptive Evict-then-Merge Strategy for Head-wise KV Cache Compression Based on Global-Local Importance}},
  year = {2024},
  eprint = {2412.08521},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2412.08521},
}
Figure