How MIT’s Attention Matching Turns Linear Regression into Fast KV Compression

1. Theory Reconstruction: Hybrid Identity and Attention Matching

The authors start by formalizing the goal of compressing a token sequence of length N with original keys and values into a shorter KV pair while preserving attention behavior for any future token. They introduce a hybrid identity that expresses the output of a compressed attention block as a weighted mixture of local attentions, where the weights are determined by the attention mass of each block.

Two matching conditions are required: (1) matching the local attention outputs, and (2) matching the attention quality (mass). A per‑token scalar bias is added to compensate for the reduced physical length, acting as a multiplicative weight that aggregates the quality of discarded tokens. This bias incurs negligible memory overhead and almost no runtime cost.

2. Ultra‑Fast Compression: A Gradient‑Free Three‑Step Pipeline

The original joint optimization is intractable, so the authors decompose it into three sequential linear‑algebra steps.

Step 1 – Build Reference Queries: A set of query vectors is generated using Repeat‑prefill and Self‑study mechanisms to broaden the query distribution. An on‑policy strategy re‑uses the compressed model state from previous layers to extract queries, mitigating distribution shift.

Step 2 – Key Selection & Bias Fitting: Instead of iterative optimization, the method selects a representative subset of original keys. Besides a simple highest‑attention score heuristic, Orthogonal Matching Pursuit (OMP) is employed to greedily pick keys that minimize the residual of quality fitting. The selected keys lead to a non‑negative least squares (NNLS) problem for the scalar bias.

Step 3 – Value Fitting: With keys and bias fixed, the value matrix is solved as an ordinary least squares (OLS) problem, yielding the compressed values that minimize attention output error.

3. Architecture Adaptation & Long‑Context Engineering

To deploy the method, the authors address memory explosion and batch efficiency. They accelerate OMP by batching key selections (Top‑k) and delaying re‑fits, reducing key‑selection time from 565 s to 104 s in a 60k‑token scenario.

Two block‑compression strategies are compared: (a) Text‑based processing with RoPE phase offsets, and (b) KV‑based slicing after pre‑fill. Experiments show KV‑based retains cross‑block positional information better.

For hybrid models (e.g., Gemma‑3‑12B with a 5:1 global‑to‑window layer ratio), only global layers are compressed while sliding‑window layers remain untouched, preserving high compression without harming model architecture.

4. Non‑Uniform Compression Strategy & Ablation

Different attention heads exhibit varying sensitivity to KV budget reductions. The authors pre‑compute a non‑uniform compression schedule and apply a greedy exchange algorithm to allocate limited KV budget to the most sensitive heads first.

Ablation studies confirm that discarding the non‑uniform budget leads to a dramatic drop in reconstruction quality, highlighting the importance of head‑wise budgeting.

5. Experimental Evaluation: Speed, Accuracy, and Online Continuous Compression

Benchmarks on QuALITY and LongHealth demonstrate a Pareto frontier where the method achieves up to 50× compression with accuracy comparable to the Cartridges baseline.

When combined with a summarization front‑end, the pipeline reaches ~200× total compression while maintaining similar accuracy, offering an attractive solution for memory‑constrained deployments.

In an AIME 2025 online inference scenario, the model repeatedly compresses the KV cache (up to six times) while keeping inference accuracy on par with an uncompressed baseline, proving the method’s robustness for continuous long‑context tasks.

6. Conclusion

Attention Matching reframes context compression as a clear linear‑algebra problem, eliminating costly gradient descent while delivering mathematically rigorous and practically fast KV compaction. Precise local behavior matching and non‑uniform budgeting make it suitable for resource‑limited, long‑duration inference workloads.