acceptodds
Under review as a conference paper at ICLR 2027

Attention under Bounded Key–Query Similarity: Space Complexity and Transformer Anisotropy

Abstract

A growing body of work on KV-cache compression aims to reduce the memory requirements of autoregressive generation. These methods compress the stored context while approximately preserving attention computation, enabling generation with reduced memory consumption. Almost tight theoretical results on the worst case space complexity of attention have recently been obtained, but they are achieved by instances where queries can be perfectly aligned with keys. This directly contradicts the observed anisotropy of the key/query geometry in real transformers. In particular, it has been shown empirically that key/query cosine similarities are small even for most correlated pairs, i.e., near-perfect alignment of queries with keys does not happen in practice. In this paper, we study the space complexity of attention approximation under the assumption that key/query cosine similarities belong to a small interval around zero, i.e., a query cannot align too much with any key. We give a nearly space optimal algorithm and a corresponding space lower bound. Surprisingly, the distribution of key/query cosine similarities in our lower bound exhibits the anisotropy property empirically established and studied in the literature. Additionally, we show that the simple uniform sampling algorithm is nearly optimal for a typical range of parameters, supporting its surprising effectiveness on real datasets.

Primary area:
foundation or frontier models, including LLMs
Keywords:
KV-cache compression, attention approximation, transformer anisotropy, space complexity, token pruning, sensitivity sampling

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_x6ByOpenReview ↗
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
  1. 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.
  2. 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.
  3. After re-deriving the main proofs, I found no mathematical errors in the exponential rates.
Critical weaknesses
  1. 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.
  2. 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.
  3. 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.
  4. 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

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.

CompressionSnapKVRandomSensitivity
2×36.3135.2136.48
4×29.2428.1435.61
10×15.4614.8420.15

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.

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

Reviewer_QMHfOpenReview ↗
Rating
2
Confidence
2
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

The paper challenges the prior assumptions on query-oblivion widely used in the key-value cache approximation literature. Earlier bounds assume that queries align well with key vectors. The authors instead show that query-key cosine similarities fall within a fixed closed interval, which they also validated empirically. Under this observation, the paper shows that uniform sampling is close to optimal when the range is narrow, whereas, for wider range importance sampling is more optimal. Empirical evidences were shown for LLaMA, Qwen and Ministral models, all of 8B sizes.

Critical strengths
  • The main assumptions of the paper is grounded with experiments. The paper shows across three models, several layers, context lengths and benchmarks that real (a, b) values are small and sit in or near the uniform-sampling region.

  • The upper and lower bounds match, and the result gives a clean theoretical reason why random eviction does surprisingly well in recent empirical work.

Critical weaknesses
  • The computed bounds are still exponential and the paper does not show where the bound actually becomes useful.
  • There are no experiments that run uniform or importance sampling against the bound, or compare it end to end with methods like SnapKV.
  • All analyses were done on a single model scale, therefore, the model geometry assumptions still remain unverfied at higher/lower scales. Not much discussion happened around the scaling p.o.v.
Questions for authors
  • How can someone estimate the values of a and b without running any eviction experiment?
2 comments

Thank you for your constructive feedback.

We added more statistics on smaller/larger models. We also added downstream experiments to evaluate performance of our algorithm (importance sampling) on real instances and practical bound realizations.

Estimating the interval. Estimating the interval does not require an eviction experiment. One can collect key and query activations on calibration contexts and compute cosine extrema separately for each layer and head. Figure 9 illustrates similar distributions across the contexts. Note that uniform sampling at a fixed budget does not require knowledge of a and b.

Scaling with model size. We added the model size sweep to the Q/K similarity section, see Figure 11. A short conclusion is that the observed phenomenon persists across model sizes.

Downstream evaluation. 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.

CompressionSnapKVRandomSensitivity
2×36.3135.2136.48
4×29.2428.1435.61
10×15.4614.8420.15

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.

Bounds on real data. While our paper’s central contribution is theoretical, we added a practical refinement (Theorem 5, Appendix F), which accounts for the cosine tails without treating the quantile interval as a bound on every pair. Appendix G.2 evaluates this refinement on real caches. While we don’t optimize the exact constant, the retained token count proxy B shows compressibility patterns for several model-head configurations, for example Layers 4 and 16 of Llama 3.1 8B and Layer 24 of Ministral 3 8B.

Dear Reviewer QMHf,

We would appreciate hearing whether our rebuttal, including the added experiments and model-size analysis, addresses your concerns. We would be happy to answer any remaining questions.

Best regards,

The Authors

Reviewer_z9KROpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies attention approximation using query-oblivious, positively weighted subsets of KV pairs when all admissible key–query cosine similarities lie in an interval [a,b]. For constant approximation error and dimension growing faster than log n, it derives upper and lower bounds with nearly matching exponential dependence on the norm and similarity parameters. Uniform sampling achieves this dependence in a specified regime; elsewhere, the construction uses sensitivity bounds computed through norm partitioning and convex optimization. The lower-bound instances combine nearly orthogonal retrieval directions with common shifts that produce anisotropic key/query geometry. Measurements from three 8B model families motivate the restricted-similarity assumption. The main contribution is a theoretical characterization of worst-case retained-token complexity, with empirical geometry observations supporting the motivation.

Critical strengths
  1. The bounded-similarity setting provides a meaningful refinement of existing norm-only analyses. The resulting dependence on min{b−a, (1+b)/2} identifies how restricting key–query alignment changes the leading exponential term.
  2. The importance-sampling result contains identifiable technical work beyond applying a standard sampling theorem. Lemma 4 bounds total sensitivity, while Lemma 5 handles varying vector norms and the nonconvex admissible-query set through norm bins and convex relaxations.
  3. The lower-bound construction respects the prescribed cosine interval and shows that small key–query alignment can coexist with difficult retrieval instances. The argument correctly accommodates randomized summaries and the stated per-query success guarantee.
  4. The paper is clearly organized and explicitly distinguishes retained-token bounds from arbitrary compressed representations. The measurements across several model families also give the theoretical restriction a concrete empirical motivation.
Critical weaknesses
  1. The empirical intervals do not verify the theorem’s assumption. Figure 3 uses the 0.001 and 0.999 cosine quantiles, whereas Equation (4) requires bounds for every pair. Rare excluded pairs can carry substantial softmax mass. Removing the initial attention sink does not establish that the remaining exceptions are harmless.
  2. Practical optimality is not quantitatively established. At d=128 and n=8192, ξ≈0.682 makes the lower-bound conditions in Equations (6) and (21) vacuous. The upper bounds may also exceed the cache size: even rk=rq=15 and an exponent coefficient of 0.6 give approximately 152,000 tokens before accuracy factors. The paper does not instantiate both bounds for its measured configurations.
  3. Worst-case optimality does not establish competitiveness on actual caches. The theorem rules out a uniformly better exponent over the entire restricted class; it does not rule out substantially smaller summaries for structured model caches. The paper measures geometry but does not test whether membership in the proposed regime predicts uniform sampling’s approximation error relative to other policies.
  4. The anisotropy connection needs a narrower interpretation. In Equation (7), the common shift contributes the same −βR² to every logit and cancels in softmax. The construction therefore demonstrates compatibility between anisotropy and retrieval hardness, rather than identifying mean separation as a mechanism governing compression. Table 1 also shows that strong negative mean alignment is not shared by Qwen3.
Questions for authors
  1. For the intervals used in Figure 3, what fraction of each query’s attention mass lies outside the 0.001/0.999 cosine quantiles? Do the true extrema still place the measured heads in the same sampling regime?
  2. At d=128 and n=8192, your packing parameter is ξ≈0.682, so Equations (6) and (21) admit no m≥2. Can you provide a nontrivial finite-dimensional lower bound for these configurations, or explicitly limit the optimality interpretation to the asymptotic regime?
  3. Using the actual maximum key/query norms, valid cosine bounds, and a stated error tolerance, what retained-token counts do Lemma 1 and Algorithm 1 certify for the caches in Figure 3? Which configurations yield a count below n?
  4. On the same caches, how does uniform sampling’s held-out attention-output error compare with a query-oblivious nonuniform baseline at matched token budgets? Does the proposed regime classification predict the observed performance gap?
  5. Since the common shift in Equation (7) cancels exactly in softmax, what does mean-vector separation explain beyond compatibility with the lower-bound construction? How do the empirical intervals and resulting bounds change after centering the keys, which leaves attention outputs unchanged?
2 comments

Thank you for the detailed questions.

Our optimality result bounds the asymptotic space complexity of token pruning on instances with key–query cosine similarities being sharply concentrated and bounded away from 1 (i.e., no query is allowed to correlate with any key significantly). Empirical data support the assumptions on key-query geometry that we make, but our main result is asymptotic in nature and does not establish that uniform sampling is optimal on individual model caches. We added more statistics of model geometry, on larger models, and they support our assumptions. We also added downstream experiments to evaluate performance of our algorithm (importance sampling) on real instances.

  1. Cosine extrema and tail mass. 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.

  1. Finite-dimensional lower bound. Our current lower bound shows asymptotic optimality only. Thanks for pointing this out, it is an interesting future direction!
  2. Bounds on real data. We added a practical refinement (Theorem 5, Appendix F), which accounts for the cosine tails without treating the quantile interval as a bound on every pair. Appendix G.2 evaluates this refinement on real caches. While we don’t optimize the exact constant, the retained token count proxy B shows compressibility patterns for several model-head configurations, for example Layers 4 and 16 of Llama 3.1 8B and Layer 24 of Ministral 3 8B.
  3. Held-out attention error. We compared uniform and nonuniform sampling at the same 4x compression rate. We report NMSE (Normalized Mean Squared Error) over 32 evaluation queries and 16 seeds. | Model | Layer | Uniform sampling NMSE | Sensitivity sampling NMSE | |---|---|---|---| | Llama | 8 | 7.38e-3 | 1.71e-3 | | Llama | 16 | 2.68e-3 | 1.12e-3 | | Ministral | 8 | 6.51e-3 | 1.26e-3 | | Ministral | 16 | 3.07e-3 | 1.53e-3 | | Qwen | 8 | 5.49e-3 | 6.18e-4 | | Qwen | 16 | 7.35e-3 | 1.94e-3 | The reported results show lower attention-output error for the nonuniform policy in these configurations.

Also see Section G.1 for the end-to-end evaluation.

  1. Anisotropy and centering. We agree that the common shift in Equation (7) cancels in softmax. Recentering generally increases the spread of cosine similarities, but reduces radii. The former makes our upper bound weaker, the latter makes our upper bound stronger. Of course, the actual performance of importance sampling or uniform sampling is unchanged. We examine the net effect of these two changes on our upper bound empirically below. In most cases recentering improves the bound:
ModelLayerRadius shrinkage(b-a) spreadTotal change of the theoretical bound exponent
Llama 3.1 8B4-27.15%+11.12%-19.04%
Llama 3.1 8B8-21.79%+40.54%+9.92%
Llama 3.1 8B16-25.50%+19.95%-10.64%
Llama 3.1 8B24-28.42%+51.34%+8.34%
Qwen3 8B4-42.26%+29.27%-25.36%
Qwen3 8B8-57.48%+115.82%-8.24%
Qwen3 8B16-18.29%+5.31%-13.96%
Qwen3 8B24-16.76%+13.06%-5.88%
Ministral 3 8B4-25.01%+33.28%-0.05%
Ministral 3 8B8-22.35%+17.46%-8.80%
Ministral 3 8B16-23.64%+17.97%-9.93%
Ministral 3 8B24-18.73%+35.25%+9.92%

The table uses the mean radius shrinkage and 0.001-0.999 quantile bracket of cosine similarities, as in Figure 3.

Our construction shows that anisotropic key–query geometry can coexist with worst-case retrieval hardness. Although this does not explain why anisotropy emerges in trained models, it provides a theoretical connection that may guide further investigation into the relationship between anisotropy and retrieval difficulty.

Dear Reviewer z9KR,

Thank you again for your detailed feedback. Please let us know whether our rebuttal and added experiments address your concerns. We would be happy to clarify any remaining points.

Best regards,

The Authors

Comments on the paper

1 comment

Dear reviewers,

A reminder that the discussion period will end on November 18 at 11:59pm AoE. I encourage you to interact with the authors' rebuttal to clarify any remaining issue (and how well the rebuttal addressed your concerns) before the next phase.

Thanks, The AC

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.