acceptodds
Under review as a conference paper at ICLR 2027

Spectral Attention Coresets via Vector Balancing

Abstract

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 of the full cache for every query of norm at most . For keys and values in the unit ball of , the recent work of lak2026 establishes a coreset size of . 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 , where is the key dimension and is the spectral Gaussian width of the span of the values. Experiments with a practical greedy variant of the walk, which the online theorem does not cover, show – lower maximum held-out-query error than uniform sampling on electroencephalography (EEG) covariance matrices for , and – fewer pairs to reach selected error targets on synthetic values.

Primary area:
optimization
Keywords:
spectral, attention, coresets, matrix

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_VzjbOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper extends attention coresets, which are small subsets of the KV cache that answer every query in a ball almost as well as the full cache, to symmetric-matrix values with error measured in operator norm. The motivating examples are attention outputs used as covariance estimates and attention-weighted second moments.

The main result bounds the value side of the coreset size by the spectral width of the value subspace, roughly the expected operator norm of a random matrix in it. This quantity never exceeds the factor that flattening the matrices gives, and for large generic matrices it is much smaller. A lower bound for values sharing a common range shows that the dependence on the range dimension cannot be improved in general. A causal version lets one chain of signings serve every prefix of the context, and a randomized self-balancing walk attains it online with high probability, up to polylogarithmic factors, for a sequence fixed in advance.

Experiments with a greedy version of the walk show that it beats uniform sampling on synthetic matrices, and uniform and stratified sampling on EEG covariance retrieval. On a real LLM the guarantees are vacuous, and the walk's per-layer errors are about equal to those of uniform sampling.

Critical strengths
  • I like the main theoretical idea. Testing the signed sums against rank-one directions improves the value-side bound for matrix values, and the lower bound shows that the dependence on the range dimension cannot be improved in general. The causal version, which serves every prefix with one chain of signings, is a nice extension.
  • I found the EEG results persuasive. On EEG covariance retrieval at small radius, where attention depends on the query, the walk beats uniform, time-stratified and value-stratified sampling, and in per-person caches it beats uniform sampling for most volunteers.
Critical weaknesses
  • My main reservation is that I don't think the experiments test the new bound.
    • The upper bounds of Theorems 1 and 3 are existential, and the constructive online guarantee loses polylogarithmic factors.
    • No theorem covers the greedy walk used in all experiments, and on synthetic data the walk setting that the theory covers barely beats uniform sampling.
    • Appendix C notes that the walk depends on the values only through Frobenius inner products. With the identity preconditioner used by default in the experiments, that makes it the same algorithm as on orthonormally flattened values, so the spectral improvement lies only in the guarantee.
    • The value-structure experiment in Appendix C varies the matrix size, but the paper notes that its common-range check cannot separate the spectral factor from the flattened one, and no experiment compares measured errors with the spectral-width prediction.
    • As I read them, the experiments show that balancing beats sampling at small radius when attention depends on the query.
  • I'm also not convinced by the KV-cache motivation.
    • Every whole-ball bound carries a factor exponential in the query radius, so the bounds are informative only for moderate radii.
    • Real LLM heads lie far outside that range, and on them the walk's per-layer errors are about equal to those of uniform sampling.
    • The end-to-end LongBench gain comes from a protocol chosen after a leakage problem appeared, and under another protocol the walk does not beat stratified sampling.
    • To me the application the paper supports is matrix-valued retrieval at small radius, such as EEG covariance estimation, and the framing would be stronger if it led with that.
Questions for authors
  • Remark 4 sketches a randomized polynomial-time route to the size in Theorem 1 without claiming it. Could you complete that argument, or give an analysis that covers the greedy walk used in the experiments?
Reviewer_7AhxOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies how to select a subset of the KV cache before any query is observed, whose attention output is within ϵ\epsilon of the full KV cache's given ∣∣q∣∣≤ρ||q||\leq \rho. It extends the framework of Liberty et al. (2026) and Cohen (2026) to the symmetric value matrix and measures the error in the operator norm. The main results include three existential theorems and a guarantee for the online walk. The experiments use a greedy variant of the walk, which is not covered by any theorem. They report the results on synthetic data, EGG and Qwen2.5.

Critical strengths
  • This paper presents a clean idea by changing the set of test directions and using the spectral norm instead of the Frobenius norm. It provides a complete theoretical chain.
Critical weaknesses
  • The experiments do not isolate or test the spectral improvement.
  • The theoretically guaranteed algorithm and the algorithm used in practice do not coincide. The experiments use the greedy limit c →\rightarrow 0, which no theorem covers.
  • The guarantees do not reach realistic LLM regimes. The median centred ρ\rho of Qwen2.5-7B heads is 53.7, so the guarantee is vacuous.
Questions for authors
  1. Since Algorithm 1 accesses the values only through the Frobenius inner product, is it exactly equivalent to the walk on flattened values? If so, could you test whether the spectral improvement is observable? Evidence of spectral scaling would change my assessment.
  2. What key centre is used in the causal experiment of E1? If the global mean is used, the walk depends on future keys, whereas uniform and time-stratified sampling do not depend on them. Please report the prefix errors with a causally available centre.
Reviewer_CTpqOpenReview ↗
Rating
4(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
3(+1)
Read review
Paper summary

The paper extends query-oblivious attention coresets (Liberty et al. 2026, Cohen 2026) to values that are symmetric matrices, with error measured in operator norm. Testing the signed sum against Φ₀(q) ⊗ (±uuᵀ) instead of the Frobenius sphere gives a size of e^ρ(ω(W) + 1 + √(d_k log(1+ρ)))/ε, where ω(W) is the spectral width of the value subspace (Theorem 1). A matching √r lower bound covers values that share a rank r range (Theorem 2). Theorem 3 makes one nested chain valid on every prefix, and Theorem 4 shows a self-balancing walk gets there online, up to polylog factors. The experiments run a greedy variant of the walk on synthetic matrix ensembles, EEG channel covariances, sector fund co-movements, and Qwen2.5-7B on LongBench Qasper.

Critical strengths

Theorem 3 is the part I’d actually use. Liberty et al. and Cohen only handle the full cache. BalanceKV controls a stream of queries fixed in advance, not the ball (Section 1). Here one signing serves every prefix and every dyadic budget (Corollary 4) at an additive √log n, which is what you’d want if this ever gets near decoding. Through the J embedding it covers vector values, so it doesn’t depend on the matrix story at all.

The value side bound is tight, and the proofs are careful enough to check. For a shared rank r range, Table 1 and Lemma 2(iii) give 2√r where flattening gives Θ(r), and Theorem 2 shows the √r can’t be improved in general. I went through the measure bookkeeping in Lemma 5, the denominator recursion in A.5, Proposition 1, and the union bound for Theorem 4, and found no errors. The constants are explicit throughout, which is the only reason checking was feasible.

Critical weaknesses

The experiments don’t isolate the spectral factor. Every run uses Λ = I (Section 3, Protocol; E4 says preconditioning raised the error), so Algorithm 1 only sees the values through Frobenius inner products. That’s the same walk you’d run on flattened values. Appendix C.1 admits the invariance check “does not separate” 2√r from √10. I’d expect at least one experiment where the two analyses predict different things. The gains over uniform in E1 and E2 (1.8x to 7.0x fewer pairs, 1.7x to 3.9x lower error) support balancing in general, not ω(W) in particular. It also bothers me that the greedy c → 0 walk used everywhere isn’t covered by Theorem 4 (Section 5). The covered walk at c ≈ 168 is only 1.01x to 1.18x better than uniform (E4).

The case that matrix values matter is thin. The clinical cache in Section 1 is explicitly hypothetical. On Qwen the census in Figure 13 finds the spectral factor beats 2√128 for 3 of 112 heads, with median centred ρ = 53.7. The F1 gains in Table 6 come from ρ = 4, which isn’t theory matched (at ρ* the walk collapses to one uniform token per dyadic block, Appendix C.4). They come from a protocol picked after a leakage bug, and in the third protocol the walk at ρ = 4 doesn’t beat stratified sampling (−0.04 F1, p = 0.97). The walk and uniform sampling tie on 107 of the 200 questions. The authors are upfront about all of it, which I appreciate. This leaves EEG and the fund experiments as the main evidence for the method’s ML relevance. Even for the fund data, the causal walk fails to outperform value-stratified sampling when ρ > 1 (Appendix C.3).

Questions for authors

(Clarification) Is there an instance where ω(W) and √(dim W) diverge sharply, say generic Sym(m) values that depend on the keys at large m, and where the measured error follows the spectral prediction? This is the experiment that would move me up.

(Clarification) How was ρ = 4 picked for the Qwen runs, and were other fixed values tried first? Given the post hoc protocol choice, this decides how much weight Table 6 can carry.

(Suggestion for future work) A concrete system, deployed or seriously proposed, where attention retrieves matrix values and operator norm error is what matters downstream. The Hopfield Jacobian link in Section 1 is interesting, but it isn’t a use case.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.