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

Feb 18, 2026

Fast KV Compaction via Attention Matching

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.

Adam Zweiger, Xinghong Fu, Han Guo +1

Massachusetts Institute of Technology.

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

Ask PDF

Aug 21, 2026

Beyond Sparse Weights: When Is Attention Compressible?

KV-cache compression is often justified by attention maps with a few large weights. This is incomplete: large weights may not contain most of the mass, omitted values can cancel, and preserving the attention output may not preserve the task. We separate these questions. Global score gaps -- not threshold counts -- determine how many tokens are needed to retain a target mass. For a realized row, the weighted sum of omitted values is the exact missing statistic. A controlled retrieval--aggregation model explains when truncation helps and when it hurts. These results motivate CertKV, a training-free compressor that reserves one tail-summary slot per head and allocates the rest by value dispersion. Under matched budgets, CertKV is top-two in seven of nine LongBench-v2 settings, remains in the leading compressed tier on 128K RULER, and realizes a ten-fold cache budget in a packed Llama prototype. Compressibility depends on the mass, values, future queries, and task -- not on a sparse-looking map alone.

Chiwun Yang, Xiaoyu Li

City University of Hong Kong · University of New South Wales

KV-Cache Compression Memory Compression KV-Cache Pruning Sparse Attention

Ask PDF

May 7, 2026

Training Transformers for KV Cache Compressibility

Long-context language modeling is increasingly constrained by the Key-Value (KV) cache, whose memory and decode-time access costs scale linearly with the prefix length. This bottleneck has motivated a range of context-compression methods, from token-level summarization to recent optimization-based KV compression methods. These post-hoc methods operate on the KV cache of a fixed pretrained model, so their effectiveness is fundamentally limited by how well the model's internal representations can be compressed. In this work, we formalize the notion of KV compressibility and show that it is a property of the learned representations, rather than of the context alone. We prove that almost any sequence-to-vector function admits both highly compressible and inherently non-compressible transformer implementations, highlighting the need to guide transformers toward compressible representations during training. Motivated by this, we propose KV-Compression Aware Training (KV-CAT), a continued pretraining procedure that incentivizes the emergence of compressible representations. We introduce a train-time KV sparsification policy that masks KV slots during training. This forces the model to use fewer KV slots and encourages it to learn representations amenable to post-hoc compression. Empirically, we show that KV-CAT improves the quality-budget tradeoff of downstream compression methods across retrieval, long-context question answering, and perplexity-based evaluation of compressed-prefix continuation.

Yoav Gelberg, Yam Eitan, Michael Bronstein +2

University of Oxford · 2Technion – Israel Institute of Technology · 3AITHYRA +1

Long-Context Language Modeling KV-Cache Compression

Ask PDF

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