Kernel-based Interpolatory Methods for Context Compression of Attention Mechanisms

Michel Fabrice Serret; Laura Grigori

cs.LGOct 29, 2026

Kernel-based Interpolatory Methods for Context Compression of Attention Mechanisms

Authors: Michel Fabrice Serret, Laura Grigori

Organizations: Center for Scientific Computing, Theory and Data, Paul Scherrer Institute, Switzerland. · Institute of Mathematics, EPFL, Switzerland

Abstract

The bottleneck of attention mechanisms, which are the fundamental building block of modern language models, is their quadratic complexity in terms of context size. There has thus been an increasing interest in the compression of the context, also called KV-cache compression. In this article, we consider the problem of compressing the context of attention mechanisms by first formulating it in the Hilbert space associated with its kernel. In this formalism, attention can be represented as the ratio of two linear maps whose interpolant is also the ratio of interpolants, this allows us to consider the interpolation of the linear maps directly. We thus introduce two novel KV-cache compression methods which we call GAIM and Q-DAIM, based on the Generalized Empirical Interpolation Method (GEIM) and the Q-Discrete Empirical Interpolation Method (Q-DEIM), respectively. As the cost of these methods is quadratic in terms of context length, we propose surrogate models based on the Taylor series, the Performer and the Random Fourier Features method which allow the compression to be done in linear time. Finally, we extend this result to the streaming attention setting, providing new methods which allow one to penalize the selection of interpolation nodes based on the previously interpolated context and to update the previous interpolation based on new information. We then provide numerical results on the convergence of the residuals and the output error in future queries and preliminary results on the LongBench-E benchmark showing performance comparable to the state-of-the-art methods. These experiments suggest that the range revealed by our Q-DAIM method could help identify where information is concentrated in the KV cache, thus enabling an efficient compression.

Figures & tables

Projection method	$\mathcal{W}$	$A_{\mathcal{W}}$	$B_{\mathcal{W}}$
GAIM	$\Pi_{L_{\phi}}$	$\breve{E}_{LL}$	$\breve{E}_{LK}V^{\mathrm{aug}}_{\eta}$
PG least squares	$\Sigma_{K}$	$\breve{E}_{LK}\breve{E}_{KL}$	$\breve{E}_{LK}\breve{E}_{KK}V^{\mathrm{aug}}_{\eta}$
Q-DAIM revealed-range	$\mathcal{I}_{L}/\Pi_{U}$	$F_{P,:}F_{P,:}^{\mathsf{T}}$	$F_{P,:}F^{\mathsf{T}}V^{\mathrm{aug}}_{\eta}$
Least squares	-	$\breve{E}_{KL}$	$\breve{E}_{KK}V^{\mathrm{aug}}_{\eta}$
WildCat $\tau$ scaling	$P_{\tau}=L_{\phi}^{\mathsf{T}}E_{\tau^{-2}L,L}^{-1}L^{\tau^{-2}}_{\phi}$	$\breve{E}_{\tau^{-1}L,\tau^{-1}L}$	$\breve{E}_{\tau^{-1}L,\tau^{-1}K}V^{\mathrm{aug}}_{\eta,\tau}$

Table 1: Matrices and projectors associated with the different projection methods.

Deflation	$M$	$G$	$\breve{S}$	$R$
None	$\breve{K}_{\mathrm{seg},\phi}^{\mathsf{T}}V^{\mathrm{aug}}_{\mathrm{seg}}$	${V^{\mathrm{aug}}_{\mathrm{seg}}}^{\mathsf{T}}\breve{E}_{K_{\mathrm{seg}}K_{\mathrm{seg}}}V^{\mathrm{aug}}_{\mathrm{seg}}$	$\breve{E}_{K_{\mathrm{seg}}K_{\mathrm{seg}}}$	$\breve{E}_{K_{\mathrm{seg}}K_{\mathrm{seg}}}V^{\mathrm{aug}}_{\mathrm{seg}}$
Basis	$\Pi^{\perp}_{L_{\phi}}\breve{K}_{\mathrm{seg},\phi}^{\mathsf{T}}V^{\mathrm{aug}}_{\mathrm{seg}}$	${V^{\mathrm{aug}}_{\mathrm{seg}}}^{\mathsf{T}}\breve{S}_{L}V^{\mathrm{aug}}_{\mathrm{seg}}$	$\breve{S}_{L}$	$\breve{S}_{L}V^{\mathrm{aug}}_{\mathrm{seg}}$
Range	$\Pi^{\perp}_{U}\breve{K}_{\mathrm{seg},\phi}^{\mathsf{T}}V^{\mathrm{aug}}_{\mathrm{seg}}$	${V^{\mathrm{aug}}_{\mathrm{seg}}}^{\mathsf{T}}\breve{S}_{U}V^{\mathrm{aug}}_{\mathrm{seg}}$	$\breve{S}_{U}$	$\breve{S}_{U}V^{\mathrm{aug}}_{\mathrm{seg}}$

Table 2: Modified matrices for each deflation type.

Choice	Options
Key centering	Segment (c) / Global (g)	§ 4
(1) Deflation	None / Basis ( $\breve{S}_{L}$ ) / Range ( $\breve{S}_{U}$ )	§ 4
(2) Selection	GAIM / Q-DAIM	§ 3.1.2
features	Exact / Linear-Taylor / Performer / RFF	§ 3.1.5
residual	v1( $T_{1}$ ) / v2( $T_{1}{-}T_{2}$ ) / v3( $\tfrac{T_{1}-T_{2}}{T_{3}}$ ) / v4( $\tfrac{T_{1}-T_{2}}{h}$ ) / v5( $\phi[q]^{\mathsf{T}}M_{\Delta}$ )	§ 3.1.2
(3) Projection	Basis (Galerkin) / Range / PG least squares / least squares	§ 3.2

Table 3: Parameters for interpolation of streaming attention.

	Matrix	Size
Post-Compression
Nodes	$L$	$n\times d$
Weights	$W^{\mathrm{aug}}$	$n\times(d+1)$
Running mean	$\mu_{g}$	$d$
Range-correction weights	$\bar{W},\bar{W}_{\mathrm{Norm}}$	$d+1$
Sink	$(K,V)_{\mathrm{sink}}$	$2t_{\mathrm{sink}}d$

Table 4: Data in memory per head and per layer kept throughout the context compression.

Exact kernel
Selection	Residual instantiation	Selection	Residual update	Total
GAIM	$O(N_{\mathrm{seg}}^{2}d)$	$O(N_{\mathrm{seg}}n_{\mathrm{seg}}d)$	$O(N_{\mathrm{seg}}n_{\mathrm{seg}}(n_{\mathrm{seg}}+d))$	$O(N_{\mathrm{seg}}(N_{\mathrm{seg}}d+n_{\mathrm{seg}}^{2}))$
Q-DAIM †	$O(N_{\mathrm{seg}}d(N_{\mathrm{seg}}+d))$	$O(N_{\mathrm{seg}}(n_{\mathrm{seg}}+r))$	$O(N_{\mathrm{seg}}r\min(n_{\mathrm{seg}},r))$	$O(N_{\mathrm{seg}}d(N_{\mathrm{seg}}+d))$
Surrogate
GAIM-LIN	$O(N_{\mathrm{seg}}Dd)$	$O(N_{\mathrm{seg}}n_{\mathrm{seg}}d)$	$O(N_{\mathrm{seg}}n_{\mathrm{seg}}D)$	$O(N_{\mathrm{seg}}D(d+n_{\mathrm{seg}}))$
GAIM-LIN-O ∗	$O(N_{\mathrm{seg}}Dd)$	$O(N_{\mathrm{seg}}n_{\mathrm{seg}}d)$	$O(N_{\mathrm{seg}}n_{\mathrm{seg}}D+n_{\mathrm{seg}}^{3})$	$O(N_{\mathrm{seg}}D(d+n_{\mathrm{seg}})+n_{\mathrm{seg}}^{3})$

Table 5: Computational cost of each step, for a single head, per segment. The selection and residual update costs are summed over the

n_{\mathrm{seg}}

picks, and the surrogate costs assume

D\geq d

Layer	Variant	$n=32$	$n=128$	$n=512$	All
0	v2	23 (17)	22 (16)	20 (7)	17
7	v2	27 (10)	26 (10)	24 (8)	18
14	v2	28 (6)	28 (6)	26 (2)	23
21	v2	28 (7)	28 (8)	28 (4)	26

Table 6: Number of query heads per layer (out of

28

) on which range correction lowers the maximum error in

L^{\infty}

norm,

\max_{q\in Q}\|\operatorname{Att}(q,K,V)-\widetilde{\operatorname{Att}}_{L}(q,K,V)\|_{\infty}

. GAIM exact v2, nodes selected in the

L^{\infty}

score norm,

t_{\mathrm{sink}}=32

. In parentheses we give the heads for which the error decreases by more than

10\%

. Last column: heads improved under every variant and every budget.

Layer	$n=32$	$n=128$	$n=512$	All	$n=32$	$n=128$	$n=512$	All
	GAIM exact v4				Q-DAIM exact v5
0	9 (4)	9 (8)	8 (4)	6	25 (19)	25 (19)	16 (14)	15
7	20 (6)	22 (11)	24 (14)	18	21 (5)	24 (12)	25 (20)	19
14	25 (9)	24 (17)	21 (17)	19	25 (0)	28 (7)	28 (16)	25
21	25 (4)	21 (15)	22 (17)	17	28 (1)	28 (10)	26 (19)	26

Table 7: Number of query heads per layer (out of

28

) on which the temperature-scaled projection lowers the maximum error in

L^{\infty}

norm,

\max_{q\in Q}\|\operatorname{Att}(q,K,V)-\widetilde{\operatorname{Att}}_{L}(q,K,V)\|_{\infty}

. GAIM exact v4 with the nodes selected in the

L^{\infty}

score norm, and Q-DAIM exact v5,

t_{\mathrm{sink}}=32

, RC on, the projection is solved in the kernel rescaled as in [ SM26 ] ,

\tau\approx 2.04

. In parentheses we give the heads for which the error decreases by more than

10\%

. The last column is the number of heads that improved for all

n

Selection method	$N_{\mathrm{seg}}$	Deflation	RoPE Strip.	Centering	$\tau$	RC	Proj.	Qasper	MFQA	HotpotQA	2Wiki	GovRep	MultiNews	TREC	TriviaQA	SAMSum	PCount	PRetr	LCC	RepoB-P	Mean	% dense
Dense	–	–	–	–	–	–	–	54.9	61.8	57.1	60.8	34.7	26.9	72.0	86.7	46.7	16.0	100.0	68.6	65.6	57.84	100.0
GAIM exact [v3, $L^{\infty}$ ]	128	range	off	(c,c)	1	on	Gal.	45.8	58.4	48.2	36.0	31.1	23.2	64.0	85.5	41.3	4.0	80.0	52.7	56.1	48.18	83.3
GAIM-LIN [v1, $L^{\infty}$ ]	128 †	none	off	(c,c)	1	on	Gal.	48.8	59.3	52.2	36.4	30.0	22.7	64.0	88.8	41.2	8.0	84.0	47.2	53.0	48.88	84.5
	128 †	none	off	(c,c)	1	on	none	40.5	57.7	49.2	47.3	30.9	23.6	68.0	85.0	37.5	8.0	92.0	44.2	56.6	49.27	85.2
	128 †	none	off	(c,c)	1	off	Gal.	43.9	52.3	48.0	43.7	30.3	23.1	60.0	86.8	39.0	8.0	92.0	52.5	55.3	48.84	84.4
	128 †	none	off	(c,c)	1	off	none	46.5	54.3	45.8	38.5	31.1	23.2	68.0	84.9	37.8	4.0	80.0	51.4	61.4	48.23	83.4

Table 8: LongBench-E - 25 prompts per task at 25% context compression. Key centers are given as the tuple (selection, solve), c = segment mean, g = global mean. The Exact and CompressKV rows are the values reported in Table 4 of [ SM26 ] (25% compression) on the complete benchmark (compared to our 25 samples/task). For comparison, the percentages rows give, per task, our best method on average (Q-DAIM exact,

N_{\mathrm{seg}}{=}64

) and the best score per task relative to Dense, and CompressKV relative to Exact. Proj.: Galerkin/basis projection (Gal.), none (each node keeps its own value with a unit weight,

[V_{L}\,|\,1]

), or Q-DAIM’s revealed-range projection restricted to the revealed rank (range r ). Methods optionally use the

\tau

temperature scaled kernel for comparison with WildCat [ SM26 ] . RP-Cholesky corresponds to an implementation of the WildCat selection and projection on our harness. † : run on PyTorch 2.14, whose GPU (MPS) attention kernels round differently.

LLM Context Compression

See all 62 papers

Fast KV Compaction via Attention Matching
Feb 18, 2026Adam Zweiger, Xinghong Fu, Han Guo +1KV-Cache Management LLM Context Compression
Massachusetts Institute of Technology.
Beyond Sparse Weights: When Is Attention Compressible?
Aug 21, 2026Chiwun Yang, Xiaoyu LiKV-Cache Compression Memory Compression
City University of Hong Kong · University of New South Wales
Training Transformers for KV Cache Compressibility
May 7, 2026Yoav Gelberg, Yam Eitan, Michael Bronstein +2Long-Context Language Modeling KV-Cache Compression
University of Oxford · 2Technion – Israel Institute of Technology · 3AITHYRA +1

Feb 18, 2026J/K move · Enter open · S save

Fast KV Compaction via Attention Matching

Adam Zweiger, Xinghong Fu, Han Guo, Yoon Kim

Massachusetts Institute of Technology.

KV-Cache Management LLM Context Compression KV-Cache Compression Long-Context Language Modeling LLM Inference Acceleration

Open paper AskPDF arXiv

Scaling language models to long contexts is often bottlenecked by the size of the key-value (KV) cache. In deployed settings, long contexts are typically managed through compaction in token space via summarization. However, summarization can be highly lossy, substantially harming downstream performance. Recent work on Cartridges has shown that it is possible to train highly compact KV caches in latent space that closely match full-context performance, but at the cost of slow and expensive end-to-end optimization. This work describes an approach for fast context compaction in latent space through Attention Matching, which constructs compact keys and values to reproduce attention outputs and preserve attention mass at a per-KV-head level. We show that this formulation naturally decomposes into simple subproblems, some of which admit efficient closed-form solutions. Within this framework, we develop a family of methods that significantly push the Pareto frontier of compaction time versus quality, achieving up to 50x compaction in seconds on some datasets with little quality loss.

Abstract

LLM Context Compression

Explore similar work

Fast KV Compaction via Attention Matching

Beyond Sparse Weights: When Is Attention Compressible?

Training Transformers for KV Cache Compressibility