- 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?