Kernel-based Interpolatory Methods for Context Compression of Attention Mechanisms

Michel Fabrice Serret, Laura GrigoriarXiv 2026 · arXiv

TL;DR

This paper introduces two novel methods, GAIM and Q-DAIM, for compressing the KV-cache in Large Language Models by treating attention as an interpolation problem in a Reproducing Kernel Hilbert Space (RKHS). By representing attention as a ratio of linear maps, the authors achieve context compression that scales linearly with sequence length while maintaining performance comparable to state-of-the-art methods like WildCat.

What Problem Does This Paper Address?

The "KV-cache bottleneck" is the Achilles' heel of modern Transformers. As we feed models longer documents, the memory required to store key and value vectors grows linearly, but the computational cost of attention grows quadratically.

Existing solutions often rely on simple heuristics (like keeping only the most recent tokens or those with high attention scores) or low-rank approximations. However, these often lose the nuanced semantic relationships found in long-range context. The authors seek a more mathematically rigorous way to identify which "tokens" (or combinations of tokens) are truly essential to represent the entire history of a conversation or document.

Methods

The authors reframe the attention mechanism through the lens of kernel methods. Specifically, they show that the standard softmax attention can be written as a ratio of two linear maps in a high-dimensional feature space (RKHS).

  1. GAIM (Greedy Attention Interpolation Method): Inspired by the Generalized Empirical Interpolation Method (GEIM), this approach greedily selects "magic points" (interpolation nodes) from the context that best minimize the residual error of the attention output.
  2. Q-DAIM (Q-Discrete Attention Interpolation Method): Based on Q-DEIM, this method uses a "whitened" basis (via Cholesky factorization) to maximize the volume spanned by the selected nodes, effectively capturing the most informative directions in the feature space.
  3. Linear-Time Surrogates: Since exact kernel evaluations are $O(N^2)$, the authors introduce surrogate models using Taylor series, Random Fourier Features (RFF), and Performer (FAVOR+) features. these allow the selection process to scale linearly ($O(N)$) with context size.
  4. Streaming & Deflation: To handle real-time generation, they introduce "deflation" (removing redundancy from previously selected nodes) and "refit" (updating weights as new information arrives) to ensure the compressed cache stays coherent over time.

Datasets

The researchers evaluated their methods using:

  • Wiki-40b: A large-scale Wikipedia dataset used to measure how quickly the interpolation residuals converge as more nodes are added.
  • LongBench-E: A comprehensive benchmark for long-context understanding (including tasks like summarization, Q&A, and code completion).
  • Model: All experiments were conducted using the Qwen2.5-7B-Instruct model.

Key Insights and Ideas

  • The Ratio Property: A crucial "aha moment" is that if you interpolate the numerator and denominator of the attention ratio on the same basis, the ratio of those interpolants is itself a valid interpolant. This allows for approximating the complex attention function by approximating simpler linear maps.
  • Gaussian Stability: The standard exponential kernel used in Transformers is notoriously ill-conditioned. The authors found that reformulating the problem using a Gaussian kernel and centering the keys around their mean significantly improved numerical stability.
  • Selection > Projection: The experiments suggest that which tokens you choose to keep (Selection) is far more important for downstream task performance than how you mathematically project the values onto them (Projection).
  • Revealed Range: Q-DAIM reveals a specific "range" of the attention operator. The authors found that this range is a better indicator of information density than simple residual errors.

Key Results

  • Performance Retention: On the LongBench-E benchmark at 25% context compression, Q-DAIM retained 87.1% of the uncompressed model's performance.
  • Comparison: The methods performed comparably to (and in some tasks, slightly better than) WildCat, a recent state-of-the-art kernel-based compression method.
  • Efficiency: By using surrogate features (like RFF), the quadratic bottleneck of selection was successfully reduced to linear time, making the method practical for very long sequences.
  • Task Specificity: Q-DAIM showed particular strength in summarization tasks (GovRep, MultiNews), while GAIM-variants led in single-document Q&A (Qasper).

Limitations and Future Work

  • Initial Quadratic Cost: While surrogates help, the very first initialization of the Gram matrix for exact methods still carries a quadratic cost.
  • Key Dependency: Currently, the "revealed range" $U$ is still tied to the original keys. The authors suggest that future work should focus on representing $U$ directly to eliminate the need to store any original keys at all.
  • Clustering: The authors hypothesize that combining their interpolation methods with clustering (interpolating each cluster of tokens separately) could further improve local accuracy in the KV-cache.
  • Positional Encoding: The RoPE (Rotary Positional Encoding) used in modern LLMs interferes with kernel interpolation. The authors noted that "stripping" RoPE during selection helps, but a more integrated solution is needed.

Summary updated

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.
BibTeX
@misc{serret2026kernel,
  author = {Michel Fabrice Serret and Laura Grigori},
  title = {{Kernel-based Interpolatory Methods for Context Compression of Attention Mechanisms}},
  year = {2026},
  eprint = {2610.40943},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.40943},
}
Figure