- Rating
- 3(+1)
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper studies the space complexity of attention approximation under the assumption that every key-query cosine similarity lies in a small interval between a and b, meaning no query can align strongly with any key. It identifies two regimes: a uniform sampling regime, where the interval contains zero and is not too wide, and an importance sampling regime for everything else. For each regime it gives upper and lower bounds that match in the exponential rate, and it argues that the hard instances behind the lower bounds naturally reproduce the anisotropic key-query geometry observed in real transformers, supported by cosine statistics from three 8B models.
Critical strengths
- The problem is cleanly defined and turns an empirical observation into a tractable complexity question, which is a reasonable refinement of prior worst-case lower bounds where queries may align perfectly with keys.
- The two-regime structure is internally consistent, and in the uniform regime plain uniform sampling genuinely achieves the matching lower bound, which is a neat and somewhat surprising result.
- After re-deriving the main proofs, I found no mathematical errors in the exponential rates.
Critical weaknesses
- The paper claims that plain uniform sampling is nearly optimal in the uniform regime and uses this to support its practical relevance, but it provides no empirical validation of this claim.
- The attention sink is excluded rather than studied. All measurements remove the initial token, and the model itself cannot accommodate it, since the sink is precisely a key that many queries align with strongly, violating the paper's central assumption.
- There are no end-to-end experiments. The paper loads long-context benchmarks but only reports cosine statistics. It never tests whether uniform or importance sampling at any budget preserves downstream generation quality.
- The paper's own bounds can also be vacuous at the measured parameters: the required sample count vastly exceeds the context length, yet the constants are never evaluated, and the quantile-based interval estimates hide the tail of the cosine distribution.
Questions for authors
See Weaknesses.
3 comments
The addition in Appendix G.1 addresses my major concern, demonstrating that this theory can be applied to practical settings. I therefore decided to raise our rating to 3.
Dear Reviewer x6By,
Thank you for considering the added experiments and following up. We are glad they addressed your main concern, and we would be happy to address any further questions or concerns.
Best regards,
The Authors
Thank you for the comments. We address them below.
We added downstream experiments to evaluate performance of our algorithms on real instances. We also expanded the attention sink discussion and provided practical bound realizations.
Downstream comparison. We added the end-to-end comparison with SnapKV, see Figure 6. We evaluate Qwen2.5-7B-Instruct on LongBench, with 50 examples each from HotpotQA, MultiFieldQA-en 2WikiMQA, and Qasper. SnapKV, Random, and Sensitivity compress the context KV cache by 2×–10× before seeing the question. We report mean token-level F1 (%) over the same examples for all methods. An aggregated result is shown in the table below.
At 4× and 10× compression, sensitivity sampling exceeds SnapKV by 6.38 and 4.69 F1 points, respectively. At 2×, sensitivity sampling is slightly higher, by 0.17 F1 points.
Protected sink. Attention sinks are a well-established phenomenon: initial token receives a disproportionate share of attention across many queries [1]. Our goal is to evict as many tokens as possible while preserving attention. We therefore keep the first token unchanged and compress only the remaining context tokens. Evicting it would offer negligible additional memory savings while risking a substantial change in attention. Our similarity assumption and compression analysis thus apply to the remaining context tokens, with the sink handled separately.
[1] Guangxuan Xiao, Yuandong Tian, Beidi Chen, Song Han, and Mike Lewis. Efficient Streaming Language Models with Attention Sinks. ICLR, 2024.
Bounds vacuous at measured parameters. At its core our result shows that if the cosine similarities between keys and queries are 'concentrated', then sampling is nearly optimal and, surprisingly, the hard instances crucially exhibit anisotropy that has been observed in practice, suggesting a connection between these two empirically observed phenomena. We chose to formalize 'concentration' as 'cosine similarities fall in a small interval' to simplify presentation. However, a more robust formulation is possible, and this formulation uses a moment condition – please see Theorem 5 in Appendix F – it accounts for the tails without requiring every cosine similarity to lie in the quantile interval. This formulation also yields better bounds for practical instances, see Appendix G.2. We originally decided against it since our goal was the cleanest theoretical result, not the closest match to practice.
Regarding Figure 3, it uses the 0.001 and 0.999 cosine quantiles. These intervals contain 61.7% of attention mass on average, leaving 38.3% outside them, excluding attention sink. This illustrates, as you point out, that quantiles are not the most robust way of capturing concentration of random variables in practice. The above-mentioned Theorem 5 does not suffer from this issue, and yields sensible upper bounds on practical instances, see Appendix G.2.