Spectral Attention Coresets via Vector Balancing

The key–value (KV) cache is a major memory bottleneck in long-context inference. Attention coresets compress the cache to a small set of KV pairs while preserving the attention output within $\text{eps}$ of the full cache for every query of norm at most $\rho$. For keys and values in the unit ball of ${\mathbb{R}}^d$, the recent work of lak2026 establishes a coreset size of $O(\sqrt{d}{e}^{\rho +o(\rho )}/\text{eps})$. We extend this framework to matrix-valued values, measuring approximation error in operator norm, which uniformly controls all quadratic forms and eigenvalues of the retrieved matrix; for covariance-valued attention, these include every predicted variance. Our bound yields a coreset size of $O(e^{\rho }(\omega (W)+1+\sqrt{d_k\log (1+\rho )})/\text{eps})$, where $d_k$ is the key dimension and $\omega (W)$ is the spectral Gaussian width of the span $W$ of the values. Experiments with a practical greedy variant of the walk, which the online theorem does not cover, show $1.7\times$–$3.9\times$ lower maximum held-out-query error than uniform sampling on electroencephalography (EEG) covariance matrices for $\rho \le 4$, and $1.8\times$–$7.0\times$ fewer pairs to reach selected error targets on synthetic values.