Overview
Paper: Fast KV Compaction via Attention Matching (arXiv: 2602.16284, MIT)
In one line: use least-squares instead of gradient optimization to achieve 50x KV cache compression with a two-orders-of-magnitude speedup.
The Problem: Why LLMs' Memory Is So Expensive
Transformers must carry the Key-Value (KV) cache of every previous token when processing long sequences. In real workloads—legal document analysis, multi-turn customer service, long-running coding agents—a single request's KV cache can easily consume tens of GB of memory.
Existing approaches fall short:
| Method | Idea | Problem | |------|------|------| | Token dropping | Delete old tokens | Permanent information loss | | Token merging | Merge similar tokens | Quality collapses at high compression | | Text summarization | Summarize prior text | Highly lossy for downstream tasks |
Cartridges (Eyuboglu et al., 2025) was a breakthrough: it trains a compact KV cache in latent space with near-lossless performance at 50x compression—but the gradient optimization takes hours of GPU time per context, ruling out real-time use.
The MIT paper asks: can we match Cartridges' quality without gradient optimization?
Core Insight: Attention Matching
A compacted KV cache doesn't need to perfectly reconstruct original tokens—it only needs to make the attention mechanism "feel" the same. The authors derive two constraints:
Constraint 1 — Local attention output matching: the compacted weighted value sum ≈ the original weighted value sum.
Constraint 2 — Attention mass matching: the compacted total attention mass ≈ the original. Since compacting from T tokens to t (t << T) makes mass inherently mismatch, they introduce a scalar bias β, where each retained key can "represent" the mass of multiple original keys. Intuitively, β_j = log(w_j), where w_j indicates how many original keys this compact key stands in for.
Method: Three-Step Pipeline, Fully Closed-Form
No gradient descent anywhere—every step is closed-form linear algebra.
Step 1: Sample Reference Queries
The system needs to know "what the model will ask next":
- Repeat-prefill: have the model repeat the context and extract queries
- Self-study: have the model generate summaries/QA about the context and extract queries
- On-policy: compress layer-by-layer, using earlier compressed layers' outputs as reference queries
- A. Highest Attention Keys (fastest): rank keys by attention weight under reference queries (RMS-aggregated across queries); O(T) complexity
- B. OMP Keys (most accurate): Orthogonal Matching Pursuit greedily selects keys that minimize mass error, refitting weights with NNLS; O(t²) or higher, but better quality
- Extreme speed → Highest Attention Keys
- Extreme quality → OMP Keys
- Balance → variants in between
- Paper: arXiv:2602.16284 — Fast KV Compaction via Attention Matching
- Authors: Adam Zweiger, et al. (MIT)
- Related: Cartridges (Eyuboglu et al., 2025), H2O (Zhang et al., 2023), KIVI (ICML 2024), TurboQuant (ICLR 2026)
Step 2: Select Compact Keys (C_k)
Step 3: Fit β and Compact Values (C_v)
Given C_k, both β and C_v are direct least-squares solutions:
β via non-negative least squares:
C_v via ordinary least squares:
No SGD, no backprop, no learning-rate tuning. Pure linear algebra.
Non-Uniform Compression: Different Budgets per Head
Different attention heads have vastly different compression sensitivity, and this ranking is highly stable across inputs. "Local pattern matcher" heads tolerate heavy compression; "long-range dependency tracker" heads need more budget. Non-uniform per-head compaction yields better quality at the same total memory. Implementation requires kernels supporting variable-length sequences (e.g., FlashAttention), which already exist.
Results: A New Pareto Frontier
On Qwen3-4B with the QuALITY long-document QA task at 50x compression:
| Method | Compaction Time | QA Accuracy | |------|----------|-------------| | Token-dropping baseline | seconds | significant drop | | Cartridges (gradient-based) | hours | near-lossless | | Attention Matching (OMP) | seconds–minutes | exceeds Cartridges | | Attention Matching (HighestAttn) | seconds | close to Cartridges |
The methods form a clear Pareto frontier:
Even the fastest variant significantly outperforms traditional token dropping/merging baselines.
Why It Matters
1. Long-context agents' memory bottleneck is unlocked. Agents currently compress context by summarizing. Attention Matching is a faster, more accurate, near-lossless alternative—compression becomes possible every turn, not only when memory is nearly full. 2. No training or fine-tuning. Unlike Cartridges, this is zero-shot: given a model and context, compute directly. No weight changes, no user data needed. 3. Compatible with existing inference stacks. The scalar bias β integrates into PyTorch SDPA and FlexAttention without kernel changes; logical length stays at T so RoPE positions of new tokens are unaffected.
Limitations and Open Questions
1. Dependence on reference query quality: if sampled queries don't represent future queries, quality drops. Self-study is best but costliest. 2. OMP speed bottleneck: at million-token contexts, OMP's greedy + NNLS iterations can be slow; batch key selection + periodic refitting gives 4–8x speedup, but optimal algorithms remain open. 3. No multimodal memory: only text KV caches are studied; attention mass across modalities needs redefinition. 4. Orthogonality with quantization: this compresses token count (not precision), so it could compose with 2–4 bit quantization methods like KIVI or TurboQuant—an untested combination.
Bottom Line
MIT's Attention Matching reframes KV cache compression from a deep-learning optimization problem into a linear-algebra problem: retain a key subset, least-squares fit the bias, least-squares fit the values. No gradients, no training, 50x compression, completed in seconds.
Not an incremental improvement—a paradigm shift. Anyone working on long-context inference, agent memory, or large-scale LLM serving should read this paper closely.