1 Introduction↩︎

Transformers have become the dominant architecture for processing and generating long sequences across various domains [1]–[4] due to their excellent ability to model complex interactions between tokens. During inference, these interactions are mediated through the key–value (KV) cache storing all previous tokens, and each new token is computed from this cache via softmax attention [5]. The KV cache therefore serves as the model’s working memory of the past. While this persistent access to past data makes Transformers powerful, it is also costly. As the sequence grows, the cache grows with it, and each new step must read from an increasingly large history. For long-context applications, this creates a major bottleneck in both memory use and runtime.

An attractive remedy is KV compression: replacing a long history of key–value pairs by a compact summary that approximately preserves the attention outputs of the original cache.² Such a summary is useful only if future attention cannot reliably distinguish the compressed cache from the full history. This makes it challenging to decide which distinctions in the past can be safely forgotten, because the importance of a token is not intrinsic to the token itself. A token that can be safely discarded in one context and for one set of future queries may be essential for another, while several distinct tokens may be interchangeable if attention uses them in the same way. Thus, compression is safe only to the extent that the summary preserves the context that future queries can actually use.

Despite its practical importance, KV compression lacks a systematic design theory and remains largely guided by empirical exploration [6]–[11], using heuristic proxies for future relevance such as recency, accumulated attention mass, and attention sinks. These methods show substantial compression is often possible, but they do not explain which properties of a cache make compression safe, how the achievable error should scale with the compression budget, or what an optimal summary should preserve. Conversely, theoretical results show that accurate KV compression can be impossible in the worst case [12], and identify structural assumptions under which compression is possible [13]–[15]. This leaves open the intermediate regime most relevant to practical algorithm design: caches that are not adversarial, but also not prescribed by a fixed model class.

To bridge this gap, we provide a graded account of KV cache compressibility in terms of the intrinsic interaction between a cache and future queries through softmax attention. Specifically, we characterize the minimax risk of KV compression, asking: for a fixed compression budget, how much error is unavoidable for the way a given cache can be probed by future queries? Beyond quantitative rates, this characterization identifies what an optimal summary must preserve. It captures the continuum between easy regimes, where many past tokens are effectively redundant and a small summary can preserve attention accurately, and hard regimes, where the cache contains many separately retrievable pieces of information and any small summary must lose something, and yields concrete design criteria for algorithms to attain minimax-optimal risk.

Concretely, we make the following contributions. (1) We recast KV compression as sparse approximation of a measure, strictly generalizing token eviction, and formalize its minimax risk. (2) We prove tight upper and lower bounds on this risk in terms of an intrinsic complexity measure capturing how future queries probe the cache, and show a sharp separation between algorithms with and without access to the future-query distribution. (3) We derive design principles for efficient KV compression during causally masked prefill and autoregressive decoding with minimax-optimal compression risk. (4) We instantiate these principles in a concrete KV compression algorithm and evaluate it through targeted experiments on LongBench, where it shows promising performance. Put together, our results advance KV compression towards practical methods with theoretical guarantees.

2 Related work↩︎

A large body of recent work reduces KV cache size by selecting tokens according to empirical proxies for future relevance. These proxies include recency and attention sinks [7], [8], accumulated or persistent attention mass [6], [7], [11], and attention patterns observed during prefill or across layers [9], [10]. The strong empirical performance of these methods suggests that real Transformer caches often contain substantial redundancy. At the same time, these proxies do not by themselves explain which properties of a cache make compression safe, how the achievable error should scale with the compression budget, or what information an optimal summary must preserve. Our work addresses this gap by studying the minimax risk of KV compression algorithms broadly, aiming to inform practical compression beyond empirical exploration.

Existing theory has mainly identified two endpoints: impossibility results for sharp token retrieval [12], [16], and positive approximation guarantees under additional structure [13]–[15], [17]. These results identify important limitations and tractable regimes, but they do not give a graded characterization from lossless compression to worst-case incompressibility. Our upper bounds require no a priori structural model of the data beyond bounded values, which is weaker than bounded keys and queries. Instead, we deliberately characterize the compression risk through the interaction between caches and softmax attention itself. Our lower-bound assumptions are close in spirit to the sharp-attention regimes considered in prior hardness results. However, we employ them to characterize when compression remains possible, even under sharp attention, not to establish impossibility alone.

Finally, we formalize the minimax risk of KV compression as sparse approximation of a measure. Measure-based views of softmax attention and Transformers are not new, and have led to useful perspectives in several settings [18], [19]. To the best of our knowledge, our recasting is new for KV compression, and it strictly generalizes token eviction from subset selection to sparse reweighting.

3 Problem setup↩︎

We study KV compression: the problem of replacing the context seen by a single softmax attention head with a compact summary while preserving its outputs on future queries, in order to reduce memory use and computational cost. Since softmax attention depends on the context only through the induced weighting of its key–value pairs, we formalize KV compression as sparse approximation of a probability measure over tokens. Our goal is to characterize the achievable error for this approximation problem as a function of the context’s intrinsic compressibility under a query distribution, which we formalize as a minimax risk in terms of a data-dependent complexity measure.

3.1 KV compression as sparse approximation of a probability measure↩︎

In their seminal work, [5] define softmax attention as \[\label{eq:attention-standard} \mathop{\mathrm{Att}}\bigl(q \mid k_1, \dots, k_n, v_1, \dots, v_n\bigr) = \frac{ \sum_{i=1}^n \exp\left(\left\langle q, k_i \right\rangle/\sqrt{d_k}\right) \, v_i }{ \sum_{i=1}^n \exp\left(\left\langle q, k_i \right\rangle/\sqrt{d_k}\right) },\tag{1}\] where \(q\in\mathcal{Q}\) is a query, \(k_i\in\mathcal{K}\) are keys, and \(v_i \in\mathcal{V}\) are values, in their respective spaces \(\mathcal{K},\mathcal{Q}\subseteq \mathbb{R}^{d_k}\) and \(\mathcal{V}\subseteq \mathbb{R}^{d_v}\). We write \(\mathcal{X}\mathrel{\vcenter{:}}= \mathcal{K}\times \mathcal{V}\) for the key–value space, and assume throughout that values are bounded in norm by a constant \(V > 0\), which is usually not restrictive in practice.

The collection \((k_i,v_i)_{i=1}^n\) of key–value pairs in 1 is called the KV cache. We study the problem of KV compression: finding a compact representation of this collection that approximately preserves the attention map in 1 . Since 1 depends on the KV cache only through a weighted combination, we represent the KV cache as a finitely supported probability measure \(P\) and define \[\label{eq:attention} \att*{q}{P} \mathrel{\vcenter{:}}= \int_{\mathcal{X}} a_k(q \mid P)\, v \, \mathop{}\!\mathrm{d}P(k,v), \qquad a_k(q \mid P) \mathrel{\vcenter{:}}= \frac{\kappa(q,k)}{\int_{\mathcal{X}} \kappa(q,k') \, \mathop{}\!\mathrm{d}P(k',v')}\tag{2}\] for a Gaussian kernel \(\kappa(q,k) \mathrel{\vcenter{:}}= \exp(-\|q-k\|_2^2 / (2\sqrt{d_k}))\) on \(\mathbb{R}^{d_k}\) with scale parameter \(\sqrt{d_k}\). This definition coincides with 1 whenever \(P \propto \sum_{i=1}^n \exp\bigl(\|k_i\|^2 / (2\sqrt{d_k})\bigr) \cdot \delta_{(k_i,v_i)}\). For the remainder of this paper, we work with attention as defined in 2 so that attention depends on the KV cache only through the context measure \(P\).

To formalize KV compression from this viewpoint, we introduce the notation \(\mathcal{P}(\mathcal{S})\) for the probability measures on a subset \(\mathcal{S} \subseteq \mathcal{H}\) of a Hilbert space \(\mathcal{H}\), and denote by \(\mathcal{P}_\mathrm{fin}(\mathcal{S})\) those with finite support and by \(\mathcal{P}_K(\mathcal{S})\) those supported on at most \(K\) points. KV compression then becomes the following problem.

[prb:kv-compression] strictly generalizes token eviction [6]–[10], which seeks a small, unweighted subset of \(K\) tokens that approximately preserve the attention map. In our setting, these tokens form the support of \(\hat{P}\). However, we allow arbitrary sparse reweightings of the cache, which, to the best of our knowledge, provides a new view on KV compression.

3.2 Capturing the intrinsic compressibility of a context↩︎

To understand when accurate compression is possible, we identify how changes to \(P\) affect softmax attention. Since \(P\) and \(\hat{P}\) are both probability measures, their difference \(\Delta \mathrel{\vcenter{:}}= \hat{P} - P\) is a signed, zero-mass measure. Compression can therefore be viewed as a reweighting of the original context, and its error is determined by how this reweighting perturbs the softmax numerator and normalizer.

Indeed, a direct computation shows that, for every query \(q \in \mathcal{Q}\), \[\label{eq:attention-reweighting} \att{q}{\hat{P}}-\att{q}{P} = \frac{ \int_\mathcal{X}a_k(q \mid P)\bigl(v-\att{q}{P}\bigr)\,\mathop{}\!\mathrm{d}\Delta(k,v) }{ 1+\int_\mathcal{X}\bigl(a_k(q \mid P)-1\bigr)\,\mathop{}\!\mathrm{d}\Delta(k,v) }.\tag{3}\] Thus, every compression perturbation enters attention through two linear functionals of \(\Delta\): a centered numerator term and a centered renormalization term. This identifies the pair of query-indexed coefficients with which each \((k,v) \in \mathcal{X}\) contributes to the compression-induced reweighting of tokens. We collect these coefficients with the following definition.

The first coordinate of \(\Gamma_P(k,v)\) records the token’s contribution to the centered numerator perturbation in 3 . The second coordinate records its contribution to the centered denominator perturbation, scaled by the value bound \(V\) so that both coordinates have the same units. The query distribution enters through the norm on \(\mathcal{H}_\nu\): Directions that matter on frequent queries are weighted heavily, while directions that matter only on rare queries are weighted lightly. Consequently, \(\Sigma_{P,\nu}\) measures the amount and geometry of query-visible variation in the context. While we do not claim that \(\Sigma_{P,\nu}\) is the only object to capture the intrinsic redundancy of a context, we argue that it is a meaningful choice. To substantiate this, we give three examples illustrating that the spectral decay of \(\Sigma_{P,\nu}\) tracks the intuitive difficulty of compression in several natural regimes.

3.3 Characterizing the achievable error of KV compression algorithms↩︎

Our goal in this paper is to characterize the fundamental limits of KV compression. Specifically, we seek minimax rates in terms of the intrinsic compressibility of a context by asking: What error does the best compression algorithm incur on its worst input \((P,\nu)\), as a function of \(\Sigma_{P,\nu}\)? To make this precise, we first specify what information a compression algorithm may use.

This definition allows compression algorithms to be randomized. It also allows the compressor to depend on the query distribution \(\nu\). We call this the query-aware setting. In many applications, however, the compressed summary must be formed before the future query distribution is known, which we call the query-agnostic setting, which we capture through the following restricted class.

We measure the performance of a class of compressors by its worst-case expected mean squared error over a prescribed family of contexts and query distributions.

Our objective is to characterize \(\mathfrak{R}\!\left(\compspace{K},\mathcal{F}\right)\) and \(\mathfrak{R}\!\left(\compspace{K}[ag],\mathcal{F}\right)\) through the response covariances \(\Sigma_{P,\nu}\) realized by \((P,\nu)\in\mathcal{F}\), and to use this characterization to identify what compressed summaries must preserve in order to attain minimax-optimal risk.

4 Minimax rates for KV compression↩︎

We now study the minimax risk of KV compression. 1 illustrates our approach: compressing a KV cache amounts to replacing the context measure \(P\) by a sparse reweighting, so that many tokens receive weight \(0\) while the remaining tokens are reweighted to preserve the effect of the full context on the attention map. To track this effect, we represent each key–value pair \((k,v)\in\mathcal{X}\) by its response profile \(\Gamma_P(k,v)\in\mathcal{H}_\nu\), which records the contribution of \((k,v)\) to the attention numerator and denominator under reweightings of \(P\). These individual contributions combine through their barycenter in \(\mathcal{H}_\nu\). As we show, reweightings causing small barycenter displacement also cause small attention error, recasting KV compression as a balancing problem in Hilbert space: given a context measure \(P\), reweight \(P\) so that its support is limited to at most \(K\) tokens while the barycenter of the response profiles remains nearly fixed. [prb:barycenter-sparsification] formulates this problem abstractly.

The rest of the section turns this reformulation into tight minimax bounds. 4.1 proves the transfer back to KV compression: a \(K\)-atomic reweighting whose squared barycenter displacement is at most \(\varepsilon\) incurs attention error at most \(C\varepsilon\), for a universal constant \(C>0\). 4.2 then proves two balancing bounds for [prb:barycenter-sparsification] and transfers them to the query-aware and query-agnostic minimax compression risk. Finally, 4.3 proves that these bounds are tight for sufficiently rich classes of contexts and query distributions. For that, we work in the regime where softmax attention can sharply retrieve individual tokens, formalized by the following assumption.

Condition [itm:richness:1] gives the minimal norm growth needed for sharp attention among \(K\) tokens: resolving one token against \(K\) competitors requires logit gaps of order \(\log K\), while radius-\(B\) keys and queries give gaps at most \(2B^2/\sqrt{d_k}\), forcing \(B\gtrsim d_k^{1/4}\sqrt{\log K}\). Condition [itm:richness:2] allows mild dimension growth with context length, and Condition [itm:richness:3] ensures that the value norm bound \(V\) is at the right scale.

4.0.0.1 Notation.

For a Hilbert space \(\mathcal{H}\) and a positive trace-class operator \(L\) on \(\mathcal{H}\), with eigenvalues \(\lambda_1(L)\ge\lambda_2(L)\ge\cdots\ge0\), multiplicities counted, set \(\mathop{\mathrm{tail}}_r(L)\mathrel{\vcenter{:}}=\sum_{j>r}\lambda_j(L)\). For \(x,y\ge0\), write \(x\lesssim y\) if \(x\le Cy\) and \(x\gtrsim y\) if \(x\ge cy\) for universal \(C,c>0\), and write \(x\asymp y\) if both hold.

All proofs and constructions for this section are in [apx:sparse-hilbert-approximation,apx:rates].

4.1 KV compression reduces to sparse balancing in Hilbert space↩︎

Recall from 3 that, for a fixed context measure \(P\) and query distribution \(\nu\), each token affects attention outputs under context reweightings through its response profile \(\Gamma_P(k,v) \in \mathcal{H}_\nu\). Having formalized the context as a measure, we can form the pushforward \(\mu_{P,\nu} \mathrel{\vcenter{:}}= P \circ \Gamma_P^{-1},\) which then describes the distribution of responses to the attention numerator and denominator under reweightings of \(P\). Moreover, every \(K\)-atomic measure \(\hat{\mu}\) approximating \(\mu_{P,\nu}\) while remaining supported on \(\mathop{\mathrm{supp}}(\mu_{P,\nu})\) can be pulled back to a \(K\)-atomic context measure \(\hat{P}\). Consequently, any solution of Problem [prb:barycenter-sparsification] for the measure \(\mu_{P,\nu}\) in \(\mathcal{H}_\nu\) directly yields a compressed KV cache. The following proposition shows that error bounds survive this pullback, so that upper bounds for sparse balancing in Hilbert space immediately transfer to bounds on the KV compression error.

4.2 Compression bounds from balancing bounds↩︎

By [pro:reduction], it suffices to bound the sparse balancing error in Hilbert space: prove a bound for balancing the barycenter of a probability measure in Hilbert space, and have the same bound apply pointwise to KV compression. Standard results on sparse convex optimization already provide basic balancing bounds. First, kernel herding and conditional-gradient methods give a bound of order \(B^2/K\) when \(\mathop{\mathrm{supp}}(\mu_{P,\nu})\) lies in a radius-\(B\) ball [20], [21]. This can be loose, however, because the radius is sensitive to worst-case response profiles and does not measure data-dependent redundancy. Second, independent sampling from \(P\) gives a bound of the form \(\mathop{\mathrm{tr}}(\Sigma_{P,\nu})/K\). This captures the total response variance but does not exploit potential anisotropy of \(\Sigma_{P,\nu}\), which can be significant when \(\nu\) concentrates on a few important directions.

4.2.1 Query-aware upper bound↩︎

Since query-aware compressors can explicitly adapt to anisotropic structure in the query distribution, we seek a bound in terms of the spectral decay of \(\Sigma_{P,\nu}\), which kernel herding and random sampling do not provide. Below, we provide such a bound, which is new to the best of our knowledge. The construction works by preserving the barycenter exactly on the leading eigenspace while simultaneously sparsifying the measure on the orthogonal complement. [pro:reduction] allows us to immediately transfer this bound to the minimax risk of query-aware KV compression.

Thus, when \(\nu\) is known, the compression budget can be spent on preserving the leading eigenspace of the response covariance, and the error is controlled only by the response variance outside that space.

4.2.2 Query-agnostic upper bound↩︎

The above approach relies on knowledge of the geometry of \(\Sigma_{P,\nu}\). In contrast, a query-agnostic strategy has no access to this geometry, since it depends on \(\nu\). A simple balancing strategy that does not rely on knowledge of the Hilbert space geometry is to sample \(K\) atoms independently from \(P\) and take their empirical measure, which corresponds to averaging \(K\) independent centered draws from \(\mu_{P,\nu}\) and yields the following, standard \(\mathop{\mathrm{tr}}(\Sigma_{P,\nu})/K\) bound for the query-agnostic minimax risk via [pro:reduction].

4.3 Compressors cannot beat the spectral barrier↩︎

We now show that the upper bounds from [cor:upper-bound-aware] and [thm:upper-bound-agnostic] are tight when attention can be sharp. In this regime, it is known that accurate KV compression, and fast approximate attention more broadly, is impossible in the worst case [12], [16]. We generalize these results by showing that sharpness alone does not determine whether a cache is compressible. Instead, the minimax compression risk is governed by the spectrum of \(\Sigma_{P,\nu}\) throughout a nontrivial range, from essentially loss-free compression to worst possible error scale under bounded values.

Concretely, we construct admissible contexts, together with query distributions, on which the error for any compression is calibrated to \(\mathop{\mathrm{tail}}_{K/3}(\Sigma_{P,\nu})\) and \(\mathop{\mathrm{tr}}(\Sigma_{P,\nu})\), respectively. Importantly, since an arbitrary finitely supported measure on \(\mathcal{X}\) need not be induced by actual KV caches, our lower-bound instances are chosen from the subclass \(\kvmeasures*[K] \subseteq \kvmeasures[K]\) of context measures induced by KV caches \((k_i,v_i)_{i=1}^K\). Moreover, the constructed contexts have length \(2K\), so that our lower bounds already apply when the original context is only a constant factor larger than the compression budget and do not rely on compressing extremely long contexts into tiny summaries.

4.3.1 Query-aware lower bound↩︎

When the compressor knows \(\nu\), we show that, at every scale \(R \in [0,V^2K]\), there exist instances with covariance \(\mathop{\mathrm{tail}}_{K/3}(\Sigma_{P,\nu}) \asymp R\), on which every \(K\)-atomic compressor incurs error at scale \(R/K\). Thus, the rate \(\mathop{\mathrm{tail}}_{K/3}(\Sigma_{P,\nu})/K\) governs the query-aware minimax risk throughout the full natural range, from exact compressibility at zero error to the maximum possible scale \(V^2\).

4.3.2 Query-agnostic lower bound↩︎

When the compressor does not have access to \(\nu\), it must choose a single summary to protect against many query distributions simultaneously. In this harder setting, we obtain a sharper lower bound. Specifically, at every scale \(T \in [V^2,V^2K]\), there exist instances with covariance \(\mathop{\mathrm{tr}}(\Sigma_{P,\nu}) \asymp T\), on which every \(K\)-atomic compressor incurs error at scale \(T/K\) on some query distribution. At the same time, for each individual query distribution, perfect compression of the same contexts is possible, witnessing a genuine separation of the two regimes. The price of hiding the query distribution is therefore the loss of access to anisotropic geometry in \(\Sigma_{P,\nu}\). Query-aware compressors can preserve the dominant directions and pay only for the tail, whereas query-agnostic compressors must in general pay for the full trace, which can be significantly worse.

5 Efficient KV compression algorithms with minimax-optimal risk↩︎

We now study how the abstract minimax rates from the previous section can be attained algorithmically during practical Transformer inference, focusing on the causally masked setting of autoregressive sequence models [5], [22], [23]. During prefill, the prompt is processed in parallel subject to causal attention. During autoregressive decoding, tokens arrive sequentially and attend to the full past. Our goal is to make efficient and minimax-optimal KV compression compatible with both regimes.

Since the future query distribution is typically unavailable at compression time, we work in the query-agnostic setting. Here, naive random sampling already achieves the minimax-optimal risk. Our objective is therefore to achieve this risk as a baseline, while improving on it under additional structure. Recall from 4 that the query-aware and query-agnostic minimax risks differ because the geometry of the response profile space \(\mathcal{H}_\nu\) depends on \(\nu\). A query-aware compressor can adapt to this geometry, whereas a query-agnostic compressor must choose its summary before \(\nu\) is known and hence hedge against all admissible geometries. We therefore restrict admissible query distributions to those whose response geometry is uniformly comparable to a data-independent reference geometry.

5.0.0.1 Desiderata.

We seek algorithms that

.

5.0.0.2 Notation.

We work with a stream \((k_i,v_i)_{i\ge 1}\) of key–value pairs. The first \(n\) pairs form the prompt; subsequent pairs arrive sequentially during decoding. Fix a chunk size \(K\), and assume \(n=MK\) with \(M\) a power of two. For any index set \(I \subseteq \mathbb{N}\), let \(P_{I}\) denote the context measure on the indexed tokens, and define its unnormalized mass \(w(I) \mathrel{\vcenter{:}}= \sum_{i\in I} \exp(\|k_i\|^2/(2\sqrt{d_k}))\). If \(P,Q \in \kvmeasures\) represent disjoint index sets \(I\) and \(J\), we write \[\textstyle P \oplus Q \mathrel{\vcenter{:}}= \frac{w(I)}{w(I)+w(J)}P + \frac{w(J)}{w(I)+w(J)}Q\] for their union, suppressing the dependence on \(I\) and \(J\) when clear from context.

All proofs and constructions for this section are in 10.

5.1 Efficient prefill and autoregressive decoding under causal masking↩︎

In causally masked prefill, token \(t\) may attend only to the prefix \(P_t \mathrel{\vcenter{:}}= P_{\{1,\dots,t\}}\), so compression must provide prefix summaries for each position \(t\). Since storing a separate summary for every prefix would defeat the purpose of compression, we summarize only at chunk boundaries. Specifically, we fix a chunk size \(K\), partition the stream into chunks \(I_1,I_2,\ldots\) of size \(K\), and maintain a \(K\)-atomic summary \(S_c\) of the prefix for each chunk \(c\). At position \(t \in I_c\), attention is then computed against \[\label{eq:summary} \hat{P}_t \mathrel{\vcenter{:}}= S_{c-1} \oplus P_{\{\min I_c,\dots,t\}},\tag{4}\] which keeps the local causal prefix exact and compresses only the long-range past. Hence, every attention computation uses at most \(2K\) atoms while respecting causal masking.

The summaries \(S_c\) are computed by recursively applying a randomized local reducer \(\mathop{\mathrm{\mathsf{REDUCE}}}: \mathcal{P}_{2K}(\mathcal{X}) \to \mathcal{P}_K(\mathcal{X})\). 2 implements this recursion as a parallel Blelloch scan over chunks, producing one \(K\)-atomic summary for each chunk prefix and one summary of the full prompt. 3 uses the same merge-reduce primitive online: starting from the prompt summary, it updates the compressed history during autoregressive decoding and emits a new \(K\)-atomic summary at each chunk boundary. Thus, both prefill and autoregressive decoding reduce to a small number of calls to \(\mathop{\mathrm{\mathsf{REDUCE}}}\) on inputs of size \(2K\). Consequently, if \(\mathop{\mathrm{\mathsf{REDUCE}}}\) can be implemented efficiently, the full compression scheme meets our efficiency desiderata, as the following proposition shows.

5.2 From local reducers to global risk guarantees↩︎

[alg:prefill-compression,alg:decoding-compression] lift any local compressor \(\mathop{\mathrm{\mathsf{REDUCE}}}:\kvmeasures[2K]\to\kvmeasures[K]\) to a global compression scheme for causally masked prefill and autoregressive decoding. It remains to identify conditions on \(\mathop{\mathrm{\mathsf{REDUCE}}}\) that yield global risk guarantees. We give such conditions below.

Such reducers exist. We give concrete instantiations satisfying the conditions for any bounded \(\Phi\) in 10, together with a natural choice of \(\Phi\) and illustrative examples in which [asp:common-geometry] holds for this \(\Phi\). When \(\mathop{\mathrm{\mathsf{REDUCE}}}\) satisfies these conditions, we recover the minimax-optimal query-agnostic trace bound without further assumptions, and obtain the spectral refinement of query-aware compression under [asp:common-geometry].

6 Experiments↩︎

We conduct a focused long-context evaluation of the compression scheme from 5 on the “long” subset of LongBench-v2 [24], a multiple-choice benchmark with contexts ranging from \(128\mathrm{k}\) to \(2\mathrm{M}\) words. We evaluate Qwen3-32B [25]. As a baseline, we use attention over the entire available KV cache, following the official truncation protocol of [24] whenever the full context exceeds the model’s context window. We compare the baseline against our compression scheme from 5 and against ScissorHands [6], SnapKV [9], and StreamingLLM [8] from the literature, each applied independently to each attention head.

Since ScissorHands and SnapKV do not provide efficient parallel inference methods for compressed prefill, we let the literature baselines (including StreamingLLM) use the full KV cache during prefill and only compress during decoding. In contrast, our compression algorithm is used during both prefill and decoding, so that each head only ever attends to a small subset of the tokens seen by the full-attention baseline.

We evaluate our compression scheme for two local reducers. The first is random sampling from the context measure \(Q\), which attains the query-agnostic minimax-optimal rate. The second protects the leading \(r\) directions of \(\Sigma_Q^\Phi\) and clusters tokens in the protected coordinates. This reducer attains the spectral guarantee of [thm:alg-risk] under [asp:common-geometry]. We elaborate on the design of the clustering reducer and the choice of feature map \(\Phi\) in 10. 11 has additional implementation details.

1 reports accuracy with standard error for a compression rate of approximately \(95\%\) relative to full context window. Random sampling already provides a strong query-agnostic baseline, consistent with its minimax optimality. Admissible clustering improves accuracy at \(r=64\), and matches the uncompressed baseline at \(r=128\). Furthermore, all our local reducers are competitive with the literature baselines [6], [8], [9] despite using significantly fewer tokens during prefill. While we emphasize that standard errors overlap and further validation is warranted, these results suggest that the algorithmic design principles developed in 5 hold promise for practical long-context compression at substantial KV budget reductions, during both decoding and prefill.

6pt

7 Conclusion↩︎

We posit KV compression as sparse balancing of a finite probability measure in Hilbert space, and characterize its minimax risk in terms of how a cache interacts with future queries through softmax attention. This yields tight rates under natural assumptions and identifies what compressed summaries must preserve. The same characterization reveals design principles for causal compression during prefill and autoregressive decoding, separating universal guarantees from structure-exploiting refinements. Together, our results provide a principled path toward practical KV cache compression with theoretical guarantees.

Appendix Contents↩︎

8 Sparse barycenter balancing in Hilbert space↩︎

This appendix records an upper bound for the abstract balancing problem in [prb:barycenter-sparsification].

While 1 only claims existence, we give a constructive proof with concrete algorithms. We later invoke this construction when we design KV compression algorithms in 10.

For our construction, we reduce sparsifying a finitely supported measure \(\mu = \sum_{i=1}^n p_i \,\delta_{x_i} \in \mathcal{P}_n(\mathcal{H})\) to a constrained rounding problem: Given a vector \((p_1, ..., p_n) \in [0,1]^n\), find a (random) rounded vector \((\hat{p}_1, ..., \hat{p}_n) \in [0,1]^n\) with at most \(m+2d+2\) fractional entries preserving the mass of \(p\) while satisfying linear constraints. As we show, mass preservation is sufficient to construct a sparse measure supported on at most \(m+2d+2\) points from such a constrained rounding procedure, and linear constraints are used to encode exact preservation of the barycenter in the subspace \(U\).

In 8.1, we first describe a general algorithm for constrained rounding with mass preservation. 8.2 then specializes this algorithm to sparsification of measures with a protected subspace, and 8.3 proves 1 from this.

8.1 Finite-dimensional constrained rounding↩︎

We first isolate a finite-dimensional constrained rounding procedure. Starting from a fractional weight vector, the goal is to round most coordinates while preserving mass and satisfying linear constraints. Such a procedure can be obtained as a straightforward application of the sub-isotropic rounding walk of [26]. Given a current point \(x\in[0,1]^n\), an alive set \(A\subseteq[n]\), and linear constraints, we write \[x^+ = \mathrm{\small SubIsoWalk}\!\left( x,A \;\middle|\; \sum_{s=1}^n z_s=m,\; \sum_{s=1}^n z_sc_s=0 \right)\] for the stopped phase of Bansal’s walk, restricted to the coordinates in \(A\), that returns a random point \(x^+\in[0,1]^n\) satisfying the constraints \[\sum_{s=1}^n x^+_s=m, \qquad \sum_{s=1}^n x^+_sc_s=0,\] and \(x^+_s=x_s\) for all \(s \not\in A\), such that at least one coordinate in \(A\) reaches \(0\) or \(1\). 4 simply applies this procedure iteratively until only \(2d+2\) fractional coordinates remain, which yields the following guarantees on the output.

8.2 Protected Hilbert rounding↩︎

We now apply the constrained rounding procedure to finitely supported measures on a Hilbert space. The linear constraints are chosen to preserve the barycenter in a protected subspace, and mass preservation forces small support.

8.3 Proof of 1↩︎

1 now follows by running ProtectedSparsify on the measure \(\mu\) and subspace \(U\), and taking one random realization on which the desired bound holds.

9 Minimax rates↩︎

This appendix proves our minimax rates for KV compression in the query-aware and query-agnostic settings. 9.1 proves upper bounds and 9.2 proves the matching lower bounds.

9.0.0.1 Notation.

We briefly recall the relevant notation from the main text. Given a context measure \(P \in \kvmeasures\), we write softmax attention as \[\att*{q}{P} = \int_{\mathcal{X}} a_P(q,k)\, v \, \mathop{}\!\mathrm{d}P(k,v), \qquad a_k(q \mid P) = \frac{\kappa(q,k)}{\int_{\mathcal{X}} \kappa(q,k') \, \mathop{}\!\mathrm{d}P(k',v')}\] and study the mean squared error of compressed context measures \(\hat{P} \in \kvmeasures[K]\) \[\err*{P}{\nu}{\hat{P}} = \mathop{\mathrm{\mathbb{E}}}_{q \sim \nu}\!\left\|\att*{q}{P} - \att*{q}{\hat{P}}\right\|_2^2\] under a fixed query distribution \(\nu \in \mathcal{P}(\mathcal{Q})\). The response profile of a key–value pair \((k,v) \in \mathcal{X}\) under \(P\) is \[\Gamma_P(k,v) : \mathcal{Q}\to \mathbb{R}^{d_v}\oplus\mathbb{R}, \qquad q \mapsto \Bigl( a_k(q \mid P)\bigl(v-\att{q}{P}\bigr), \; V\bigl(a_k(q \mid P)-1\bigr) \Bigr),\] with the corresponding covariance operator \[\Sigma_{P,\nu} = \int_\mathcal{X}\Gamma_P(k,v) \otimes \Gamma_P(k,v) \,\mathop{}\!\mathrm{d}P(k,v),\] where \(\Gamma_P(k,v) \otimes \Gamma_P(k,v)\) is understood as the rank-one operator \[h \mapsto \dotp{\Gamma_P(k,v)}{h}_{\mathcal{H}_\nu} \cdot \Gamma_P(k,v)\] and \(\mathcal{H}_\nu = L_2(\nu, \mathbb{R}^{d_v} \oplus \mathbb{R})\).

9.1 Upper bounds↩︎

We derive upper bounds on the minimax compression risk in the query-aware and query-agnostic settings from a shared Hilbert space representation. For fixed \((P,\nu)\), the response profile map \(\Gamma_P\) sends each token \((k,v)\) to an element of the Hilbert space \(\mathcal{H}_\nu\), and thereby pushes the context measure \(P\) forward to a finitely supported probability measure on \(\mathcal{H}_\nu\). This measure is centered and has covariance \(\Sigma_{P,\nu}\), and the attention error of a compressed context is controlled by the squared norm of the corresponding barycenter in \(\mathcal{H}_\nu\). The query-aware and query-agnostic regimes differ only in how this barycenter is approximated: in the aware regime, we may choose a sparse approximation after seeing \(\nu\), whereas in the agnostic regime we must rely on a query-independent approximation. Both regimes permit upper bounds on the sparse barycenter approximation problem, which we then translate back to bounds on the KV compression problem.

9.1.1 Reduction to barycenter sparsification↩︎

Recall the surrogate error definition \[\widetilde{\mathcal{E}}_{\mu}(\hat{\mu}) = \left\|\int_{\mathcal{H}} g \,\mathop{}\!\mathrm{d}\hat{\mu}(g)\right\|_{\mathcal{H}}^2\] between measures \(\mu\) and \(\hat{\mu}\) on a Hilbert space \(\mathcal{H}_\nu\). Our goal is to derive upper bounds on the compression error \(\mathcal{E}_{P,\nu}(\hat{P})\) from upper bounds on \(\widetilde{\mathcal{E}}(\hat{\mu})\) for the pushforward \(\mu_{P,\nu} = P \circ \Gamma_P^{-1}\) by pulling back a sparse approximation \(\hat{\mu} \in \mathcal{P}_K(\mathop{\mathrm{supp}}(\mu_{P,\nu}))\) of \(\mu_{P,\nu}\) to a sparse approximation \(\hat{P} \in \kvmeasures[K]\) of \(P\). 2 first shows that upper bounds on \(\widetilde{\mathcal{E}}\) indeed survive this pullback, and [pro:reduction] packages the full reduction principle.

9.1.2 Query-aware upper bound↩︎

In the query-aware regime, the compressor may depend on \(\nu\), and therefore on the geometry of \(\mathcal{H}_\nu\). After the reduction above, the problem is exactly to approximate the zero barycenter of the pushed-forward measure \(\mu_{P,\nu}\) by a \(K\)-atomic measure on \(\mathop{\mathrm{supp}}(\mu_{P,\nu})\). This is exactly the setting of [thm:sparse-hilbert-approximation-fixed-K], which provides a barycenter bound in terms of the spectral tail of its covariance, which here is \(\Sigma_{P,\nu}\). Pulling the resulting sparse measure back to \(\mathop{\mathrm{supp}}(P)\) then gives the desired compression bound for KV compression.

9.1.3 Query-agnostic upper bound↩︎

In the query-agnostic regime, the compressor cannot adapt to \(\nu\), so the sparse approximation argument from the aware case does not apply. A natural query-independent alternative is the empirical measure of \(K\) i.i.d. samples from \(P\). Under the Hilbert embedding, this corresponds to averaging \(K\) independent copies of the centered random response profile \(G=\Gamma_P(X)\). The mean remains zero, and the mean squared norm of the empirical average is of order \(\mathop{\mathrm{tr}}(\Sigma_{P,\nu})/K\). Using 2 from the reduction, this yields the trace upper bound.

9.2 Lower bounds↩︎

We now provide lower bounds on the query-aware and query-agnostic minimax compression risk matching the upper bounds from 9.1. Both bounds are derived from a shared, explicit construction of an instance of a context \(P\) and a query distribution \(\nu\) that are realizable from actual keys, queries, and values under [asp:richness]. This instance is constructed so that any significant compression of the context incurs large error over the chosen query distribution. We then specialize this construction to the query-aware and query-agnostic regime by calibrating the error incurred under compression against the spectrum of \(\Sigma_{P,\nu}\), obtaining lower bounds that faithfully match their corresponding upper bounds throughout the entire claimed range of redundancy levels captured by \(\mathop{\mathrm{tr}}(\Sigma_{P,\nu})\) and \(\mathop{\mathrm{tail}}_{K/3}(\Sigma_{P,\nu})\), respectively.

Throughout this section, fix universal constants \[\textstyle \rho_0\mathrel{\vcenter{:}}= \frac{99}{100} \qquad \text{and} \qquad \gamma_0\mathrel{\vcenter{:}}= \frac{9}{10}.\]

9.2.1 Hard instance construction↩︎

We begin by constructing a pair \(P,\nu\) that is impossible to compress significantly without incurring large error. The main idea is to use keys that can be sharply distinguished from each other, and have them carry almost orthogonal values. We call such an instance a lookup instance because querying a key of the context sharply retrieves the associated value. 5 formalizes the properties of a lookup instance formally, and 4 shows that such instances can indeed be constructed from actual keys, queries, and values under [asp:richness]. In particular, [asp:richness] provides enough ambient dimension to choose well-separated keys and values from Hamming packings, and enough key/query norm budget to address the keys sharply through softmax attention.

9.2.2 Approximating lookup instances requires almost the full context↩︎

We now show that lookup instances are hard to compress. Indeed, querying a key of such an instance retrieves the associated value almost perfectly, and the retrievable values are separated by a constant fraction of the value norm. As a consequence, compressing lookup instances to even half their context size incurs compression error at the maximum possible scale \(V^2\).

9.2.3 Query-aware lower bound↩︎

With the lookup instance established as hard to compress, we turn to the query-aware minimax lower bound. By itself, the lookup instance only gives the lower bound at the lowest redundancy scale, where \(\mathop{\mathrm{tail}}_{K/3}(\Sigma_{P,\nu})\) is of order \(V^2K\) and every \(K\)-atomic approximation incurs error of order \(V^2\). To show that \(\mathop{\mathrm{tail}}_{K/3}(\Sigma_{P,\nu})\) faithfully governs the minimax risk throughout all scales \(R\in[0,V^2K]\), we need the same obstruction at every intermediate such scale. We achieve this by diluting the lookup query distribution with the easy query distribution \(\delta_0\). The dummy query contributes only low-rank covariance, while the hard queries contribute both the \((K/3)\)-tail and the approximation error. Thus, the mixture \(p\nu_N+(1-p)\delta_0\) scales the relevant redundancy and the compression difficulty by the same factor \(p\), allowing us to tune both to the desired level \(R\).

9.2.4 Query-agnostic lower bound↩︎

We now prove the query-agnostic lower bound and simultaneously show a separation from the query-aware regime. We use the same hard lookup instance as before, but expose it through a family of query distributions of the form \(p\delta_k+(1-p)\delta_0\), one for each key \(k\in\mathop{\mathrm{supp}}(\nu_N)\). Each member of this family is easy for query-aware compression: once the query law is known, the compressor only has to match the output at \(0\) and at one key. At the same time, the family is hard for query-agnostic compression because a query-agnostic compressor must choose one \(K\)-atomic summary that protects against all active keys. Averaging over the active key then recovers the lookup query distribution \(\nu_N\), on which any compression to half the context size necessarily incurs large error.

As in the query-aware regime, dilution by the \(0\) query controls the error and redundancy scale. Each hard query contributes trace of order \(V^2K\), while the dummy query contributes trace of order \(V^2\). Thus, the mixture \(p\delta_k+(1-p)\delta_0\) tunes \(\mathop{\mathrm{tr}}(\Sigma_{P,\nu})\) to the target level \(T\in[V^2,V^2K]\), while the averaged error retains the corresponding fraction of the lookup compression error.

10 Algorithms↩︎

This appendix gives proofs and instantiations for the algorithmic framework of 5. 2 and 3 are parameterized by a local compression subroutine \(\mathop{\mathrm{\mathsf{REDUCE}}}\). Any choice for \(\mathop{\mathrm{\mathsf{REDUCE}}}\) compressing a context from \(2K\) to \(K\) points yields an efficient and parallel KV compression algorithm for causally masked prefill via 2 and autoregressive decoding via 3. Recall that we use the following design criteria for \(\mathop{\mathrm{\mathsf{REDUCE}}}\), under which we obtain guarantees on the compression quality.

When \(\mathop{\mathrm{\mathsf{REDUCE}}}\) satisfies these criteria, the global merge-reduce scheme matches the minimax-optimal query-agnostic trace risk, up to logarithmic degradation in time. To obtain stronger guarantees in the query-agnostic regime, additional structure is necessary. Recall that we capture such structure with the following assumption.

Under this assumption, there is a reference geometry induced by the feature map \(\Phi:\mathcal{X}\to\mathcal{H}\) that is comparable, on balanced reweightings of the current context, to the query-visible response geometry in \(\mathcal{H}_\nu\). Query-agnostic compressors can then use the geometry of \(\mathcal{H}\) as a \(\nu\)-independent proxy for \(\mathcal{H}_\nu\).

10.0.0.1 Roadmap.

This section is organized as follows. In 10.1, we discuss the choice of \(\Phi\) and give a natural softmax-attention instantiation for which [asp:common-geometry] holds in stylized but informative settings. In 10.2, we show that [def:admissible-reducer] can guide concrete algorithm design by constructing two local reducers satisfying the required criteria. 10.3 proves [thm:alg-risk], which lifts these local guarantees to the full prefill and decoding schemes, with a strengthened spectral bound under [asp:common-geometry]. Finally, 10.4 proves [pro:runtime] on the efficiency of the global merge-reduce scheme.

10.0.0.2 Notation.

We briefly recall the notation used throughout this section. We work with a stream \((k_i,v_i)_{i\ge1}\) of key–value pairs. For an index set \(I\subseteq\mathbb{N}\), we write \(P_I\) for the context measure associated with \((k_i,v_i)_{i\in I}\), and abbreviate \(P_t\mathrel{\vcenter{:}}= P_{\{1,\ldots,t\}}\). We also use the unnormalized mass \[w(I) \mathrel{\vcenter{:}}= \sum_{i\in I}\exp(\|k_i\|^2/(2\sqrt{d_k})),\] which comes from the Gaussian-kernel form of softmax attention in 2 . Finally, we fix a bounded feature map \(\Phi:\mathcal{X}\to\mathcal{H}\) for this appendix and use the notation \(\mu_P^\Phi\) and \(\Sigma_P^\Phi\) from [def:admissible-reducer] for context measures \(P \in \kvmeasures\).

10.1 Choice of feature map \(\Phi\)↩︎

The choice of feature map \(\Phi: \mathcal{X}\to \mathcal{H}\) determines which structure a query-agnostic compressor can exploit beyond random sampling. While there is no single choice that results in a good proxy for all query distributions, a natural query-agnostic choice is obtained from the two linear quantities that define attention before normalization: the unnormalized, value-weighted numerator and the scalar normalizer.

Concretely, we choose \[\label{eq:reference-features} \Phi:\mathcal{X}\to\mathcal{H}, \qquad (k,v)\mapsto \bigl(\kappa(\cdot,k)\otimes v,\;V\,\kappa(\cdot,k)\bigr),\tag{8}\] where \[\mathcal{H} \mathrel{\vcenter{:}}= \mathcal{H}_\kappa\otimes\mathbb{R}^{d_v} \oplus \mathcal{H}_\kappa\] is constructed from the feature space \(\mathcal{H}_\kappa\) of the Gaussian kernel \(\kappa\) from 3. As for the response profiles in ?? , the factor \(V\) puts the normalizer component on the same scale as the value component.

Intuitively, [asp:common-geometry] then requires that the query distribution sees the same context directions as the reference features. If a reweighting of the context substantially changes the numerator or normalizer of 2 , then this change should also be visible in the attention responses under queries \(q\sim\nu\), and, conversely, a reweighting that is small in these quantities should not produce a large response.

Formally, the response profile \(\Gamma_P\) measures the query-visible effect of a context reweighting after attention normalization and averaging over \(q\sim\nu\). For the reference features in 8 , [asp:common-geometry] requires that, on balanced reweightings of \(\mathop{\mathrm{supp}}(P)\), \[\left\|\int_{\mathcal{X}}\Phi\,\mathop{}\!\mathrm{d}\sigma\right\|_{\mathcal{H}}^2 \asymp \left\|\int_{\mathcal{X}}\Gamma_P\,\mathop{}\!\mathrm{d}\sigma\right\|_{\mathcal{H}_\nu}^2.\] Thus, large perturbations to the pre-normalization numerator or normalizer are exactly the perturbations that produce large query-visible changes in the attention response. When this is the case, a query-agnostic compressor can exploit \(\Phi\) as a hint at the \(\nu\)-dependent geometry, and beat the lower bound barrier of [thm:lower-bound-agnostic].

However, this assumption need not always hold. In particular, it fails on the hard instances of 9 used to prove lower bounds. The following examples illustrate when this comparison is a reasonable model of the attention head and when it should not be expected to hold.

10.2 Admissible reducers↩︎

We instantiate the abstract design criteria of [def:admissible-reducer] by giving two concrete local reducers. Both algorithms operate on a candidate context \(Q \in \kvmeasures[2K]\) through the reference feature map \(\Phi:\mathcal{X}\to\mathcal{H}\).

The first reducer is a constrained rounding procedure derived directly from the sparse barycenter approximation theorem in 8. It provides the cleanest theoretical guarantee: for every target rank \(r \le (K-3)/3\), it is \((\Phi,r,0)\)-admissible. Its drawback is that the constrained rounding step is inherently sequential in the protected dimension \(r\), making it poorly suited to modern parallel hardware.

To compensate for this, we also provide a more practical, clustering-based reducer. It maps efficiently to parallel hardware, but it is only \((\Phi,r,\tau)\)-admissible with a non-zero \(\tau\) term determined by the achieved clustering error.

Both reducers require an orthonormal basis of the top-\(r\) eigenspace of the centered covariance \(\Sigma_Q^\Phi\). For computational efficiency, practical implementations may replace this exact eigenspace by an approximate one, with the resulting loss absorbed into the tail condition of [def:admissible-reducer]. Finally, although both reducers are stated using the abstract feature map \(\Phi:\mathcal{X}\to\mathcal{H}\), they can be implemented using only inner products \(\langle \Phi(z),\Phi(z')\rangle_\mathcal{H}\). The framework therefore also covers infinite-dimensional feature spaces.

10.2.1 Perfect admissibility via constrained rounding↩︎

6 is a direct implementation of the Hilbert-space sparsification argument in 8. Given a context measure \(Q \in \kvmeasures[2K]\), the reducer preserves the features \(\Phi\) exactly in the leading eigenspace of \(\Sigma_Q^\Phi\), and sparsifies the measure only in the orthogonal complement. Because of that, the reducer is \((\Phi,r,0)\)-admissible.

10.2.2 Practical admissibility via clustering↩︎

7 provides an admissible reducer based on clustering. On a context measure \(Q\), the algorithm protects the principal directions of \(\Sigma_Q^\Phi\) by projecting the features onto the leading eigenspace of \(\Sigma_Q^\Phi\) and clustering them in these protected coordinates.

For the clustering step, any finite-dimensional clustering subroutine \(\mathrm{\small ClusterSlots}\) can be used, provided it produces a balanced latent-slot assignment. Concretely, using the notation of 7, the subroutine receives the weighted protected coordinates \((p_i,u_i)_{i\in L}\), where \(p_i=q_i/\rho\), and returns a matrix \(X \in [0,1]^{m\times |L|}\). Row \(a\) of \(X\) is the sampling distribution used by latent slot \(a\), while the column constraints ensure that each light atom receives the correct expected mass. Formally, \(X\) must satisfy \[\sum_{i\in L}X_{ai}=1 \qquad \text{and} \qquad \sum_{a=1}^m X_{ai}=p_i.\]

For example, one might use weighted k-means to group nearby protected coordinates and then sample representatives from those groups in proportion to their total mass, with \(X\) recording the resulting sampling probabilities.

Naturally, the quality of the compressed summary depends on the quality of the clustering. Using the notation of 7, define the clustering error of the call to ClusterSlots by \[\mathcal{C}(Q) \mathrel{\vcenter{:}}= \frac{1}{K} \sum_{a=1}^m\sum_{i\in L} X_{ai}\|u_i-\bar u_a\|_{\mathcal{H}}^2, \qquad \bar u_a \mathrel{\vcenter{:}}= \sum_{i\in L}X_{ai}u_i.\] If the light mass is zero, we set \(\mathcal{C}_{\mathrm{\small ClusterSlots}}(Q)=0\).

When this clustering error is small, ClusterReduce is admissible, as the following theorem shows.

10.3 Global risk guarantees↩︎

This section proves the risk guarantee of [thm:alg-risk] for the chunked prefill and decoding algorithms. Both schedules build summaries in a merge-reduce tree: starting from token chunks of \(K\) tokens, disjoint summaries are merged, their weighted union is compressed back to \(K\) atoms, and the unfinished current chunk is appended exactly. We show that, for admissible local compressors \(\mathop{\mathrm{\mathsf{REDUCE}}}\), the approximation error accumulates linearly with the depth of the merge-reduce tree, which then transfers to the claimed risk guarantees.

10.3.1 Geometry transfer↩︎

\(\mathop{\mathrm{\mathsf{REDUCE}}}\) is designed in the fixed reference geometry induced by \(\Phi: \mathcal{X}\to \mathcal{H}\). In contrast, the desired risk bound is expressed in the geometry induced by \(\Gamma_P: \mathcal{X}\to\mathcal{H}_\nu\), which depends on both the exact context \(P\) and the query distribution \(\nu\). We record here the transfer guarantees from the covariance \(\Sigma^\Phi_P\) in \(\mathcal{H}\) to the covariance \(\Sigma_{P,\nu}\) in \(\mathcal{H}_\nu\). Concretely, 10 shows that, under [asp:common-geometry], the spectral decay of \(\Sigma_P^\Phi\) is controlled by the spectral decay of \(\Sigma_{P,\nu}\) in the reference geometry of \(\Phi\).

10.3.2 Risk propagation through merge-reduce trees↩︎

We now turn the one-step guarantees of \(\mathop{\mathrm{\mathsf{REDUCE}}}\) into guarantees for full causal prefixes. To that end, we show that the design criteria in [def:admissible-reducer] for \(\mathop{\mathrm{\mathsf{REDUCE}}}\) — unbiasedness of the summary and second-moment control of its feature defect — propagate through the merge-reduce recursion. To express this invariant, we introduce the notion of a valid summary, which is a random context measure of a token block that satisfies the same criteria, with a parameter counting the number of reducer layers on its dependency path. Each node of the merge-reduce tree preserves validity, increasing this parameter by at most one. The global risk bound in [thm:alg-risk] then follows by recognizing the prefill and decoding summaries as outputs of such trees, whose depth is logarithmic in the number of completed chunks.

Note that this resembles directly the design criteria of a \((\Phi,r,\tau)\)-admissible reducer, as defined in [def:admissible-reducer]. In particular, if \(\mathop{\mathrm{\mathsf{REDUCE}}}\) is \((\Phi,r,\tau)\)-admissible and \(P_A \in \kvmeasures[2K]\) is the context measure of the tokens in \(A \subseteq \mathbb{N}\), then \(\mathop{\mathrm{\mathsf{REDUCE}}}(P_A)\) is \((1,r,\tau)\)-valid for \(A\).

We briefly record the following fact that we use repeatedly later on.

We now consider the operation at a single node in the merge-reduce tree. Given two summaries of two disjoint blocks of tokens, we form a compressed summary of their union by compressing their weighted combination using \(\mathop{\mathrm{\mathsf{REDUCE}}}\). When the two input summaries are \((d,r,\tau)\)-valid, the resulting summary is \((d+1,r,\tau)\)-valid, thereby propagating the guarantees up the merge-reduce tree.

Validity of a summary gives us the desired risk control, but only in terms of the fixed geometry of \(\mathcal{H}\). [pro:algorithm-risk] transfers this control to the attention error, which is measured in the geometry of \(\mathcal{H}_\nu\).

The final summary \(\hat{P}_t\) used as the compressed context for the token at position \(t\) is a combination of a compressed summary produced by the merge-reduce tree and an exact context measure of the tokens inside the same chunk as token \(t\). The next lemma shows that this is harmless for the validity of the resulting summary.

It remains only to count the validity depth of the summaries produced by [alg:prefill-compression,alg:decoding-compression]. The prefill scan and the decoding buckets both construct summaries by repeated binary merges of disjoint completed chunks. Along any dependency path there are only logarithmically many reducer calls, and the unfinished current chunk is appended exactly. Thus, if \(\mathop{\mathrm{\mathsf{REDUCE}}}\) is \((\Phi,r,\tau)\)-admissible, each resulting prefix summary \(\hat{P}_t\) is \((d,r,\tau)\)-valid, with \(d\) proportional to the depth of the tree, which is logarithmic in the number of tokens. The claimed risk guarantees then follow immediately from [pro:algorithm-risk].

The global guarantee therefore reduces entirely to the design of \(\mathop{\mathrm{\mathsf{REDUCE}}}\). Any concrete reducer satisfying the one-step trace and tail conditions of [def:admissible-reducer] inherits the same causal prefill and decoding guarantees through the merge-reduce schedules of [alg:prefill-compression,alg:decoding-compression], with only the logarithmic depth loss.

10.4 Computational cost of the global merge-reduce scheme↩︎

We prove [pro:runtime] from the main text.

11 Experimental details↩︎

This appendix describes the implementation of our experiments in 6. Detailed instructions for reproducing our experiments are provided with the code in the supplementary material.

11.0.0.1 Dataset and model.

We evaluate on the “long” subset of LongBench-v2 [24]. The dataset is available at https://longbench2.github.io/. We use the official LongBench-v2 evaluation protocol. We run all experiments on Qwen3-32B [25], using int4 quantization. We extend the context window to \(131\mathrm{k}\) tokens using YaRN RoPE scaling [27]. The model is available at https://huggingface.co/Qwen/Qwen3-32B. We disable chain-of-thought generation and use greedy decoding throughout. LongBench-v2 and Qwen3-32B are released under the Apache-2.0 license.

11.0.0.2 Computational resources.

All experiments were conducted on a single NVIDIA H100 GPU with \(95{,}830\) MiB VRAM. The full set of runs took approximately 100 GPU hours, including failed runs.

11.0.0.3 Implementation details.

For the full-attention baseline, we use the standard implementation of the Qwen3-32B model. For the compressed methods, we use the algorithms described in 5, with two additions. First, each token may attend to the first \(8\) tokens, following the attention-sink heuristic of [8]. Second, each token may attend to the \(K\) tokens immediately preceding its chunk boundary. Thus, each token attends to at most \(3K+8\) tokens. This is compatible with our theory and enjoys the same guarantees. We use \(K=2048\), corresponding to a compression rate of approximately \(95\%\) relative to the \(131\mathrm{k}\)-token context available to the full-attention baseline.

Many LongBench-v2 contexts exceed even the extended context window of Qwen3-32B. For such examples, we follow the official truncation protocol of [24] by removing the middle section of the prompt.

11.0.0.4 Local reducer instantiations.

We report results for two instantiations of \(\mathop{\mathrm{\mathsf{REDUCE}}}\): random sampling and protected clustering. All randomized methods are evaluated with a single run using a fixed random seed.

For random sampling, we sample i.i.d.from the context measure, i.e., proportionally to \[\label{eq:experiments:weights} \textstyle \exp\!\left(\|k\|_2^2/(2\sqrt{d_k})\right),\tag{11}\] as described in 3.

Protected clustering corresponds to 7, using the static feature map described in 10.1 with the value norm bound fixed to \(V^2=50\). We evaluate protected ranks \(r=64\) and \(r=128\). To compute the leading eigenspace, we use a randomized Nyström approximation with four-fold oversampling.

For ClusterSlots in 7, we use a sliced equal-mass clustering rule. After the heavy atoms have been retained exactly as in 7, the light atoms \(i\in L\) have normalized masses \(p_i=q_i/\rho\) satisfying \(\sum_{i\in L}p_i=m\). For each direction in a fixed bank of random directions in the protected coordinate space, we sort the light atoms by their one-dimensional projection and place intervals of length \(p_i\) consecutively on \([0,m]\). The \(m\) latent slots are the unit intervals of this line, and the assignment matrix \(X\) is given by the overlap of each atom interval with each unit slot. This construction satisfies the row and column constraints required in 7. We choose the direction with the smallest within-slot squared error in the protected coordinates and sample one representative from each slot by inverse-transform sampling.

For this method, we treat the initial context measure as uniform over the tokens rather than proportional to 11 , as this significantly improved numerical stability in the computation of the leading eigenspace.

11.0.0.5 Literature baselines.

We compare performance against ScissorHands [6], SnapKV [9], and StreamingLLM [8]. All three methods use a sliding window of the most recent \(4096\) tokens. The allocation of the remaining \(2056\) token budget is dictated by the respective method. StreamingLLM retains the initial \(8\) sink tokens and uses the rest of this budget to extend the recent-token window. SnapKV retains the top-ranked non-recent prompt tokens by attention score from the final prompt window, using average pooling with kernel size 5, as in the original paper [9]. ScissorHands retains the top-ranked non-recent tokens by cumulative pivotal-token counts.

References↩︎