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