acceptodds
Under review as a conference paper at ICLR 2027

Exploring the Boundary of Sparse Attention: Retrievability, Head Stability, and ANN Approximation

Abstract

Sparse attention is a promising way to reduce the cost of long-context inference, but it remains unclear when top- attention is accurate and whether practical approximate nearest neighbor (ANN) search can replace exact top- retrieval. We study these two questions separately—whether attention is retrievable by exact top-, and whether ANN indexes can find the keys it needs—across Llama-3.1-8B and Qwen3-8B on RULER, LongBench, and LongProc. Exact top- attention often approximates full attention well: across the 13 RULER tasks, the median number of keys needed to cover 90% of the attention mass grows far more slowly than the context, up to a model-specific length frontier. Its effectiveness nonetheless depends strongly on model, task, context length, and attention head. Retrieval-style tasks need significantly fewer keys than aggregation-style tasks, and fixed-budget top- attention degrades sharply at very long contexts, especially beyond a model's native context window. Head retrievability is structured and stable across inputs and decoding steps (held-out rank correlation ), and a head-aware budget calibrated once improves task scores by up to 7.3 points over a uniform budget of the same size. However, off-the-shelf ANN indexes such as IVF, HNSW, and PQ do not reliably recover enough attention mass under aggressive search budgets, and their set recall is not a reliable proxy for the mass they retain. These results suggest that sparse attention is useful but not universal: reliable deployment requires model- and task-aware strategies, adaptive budgets, and ANN methods tuned for attention mass rather than recall.

Primary area:
foundation or frontier models, including LLMs
Keywords:
sparse attention, top-k attention, approximate nearest neighbor search, attention retrievability, long-context language models, efficient NLP, model analysis

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_gjjCOpenReview ↗
Rating
3(+1)
Confidence
2(−1)
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper separates two questions in sparse attention: whether a small set of keys captures most attention mass, and whether ANN indexes can retrieve them. Experiments on two 8B models across RULER, LongBench, and LongProc show that concentration depends on context length, task, and head, while ANN recall can misrepresent retained mass. Held-out generation experiments support calibrated head-specific budgets.

Critical strengths
  • Separating attention concentration from ANN retrieval quality helps distinguish insufficient sparsity from search failures, making the findings useful for diagnosing sparse-attention systems.

  • Held-out rank correlations around 0.97 across prompts and decoding steps support predictable head-specific allocation, providing an empirical basis for offline calibration.

  • Frozen head-aware budgets improve task scores by up to 7.3 points over uniform allocation at matched budgets. This connects the attention measurements to practical generation quality.

Critical weaknesses
  • Without explicitly retaining attention sinks, it is unclear whether ANN’s low coverage reflects content-retrieval failures or merely missing a few fixed positions.

  • High coverage does not consistently preserve task performance, limiting support for the paper’s broader coverage-based design guidelines.

  • The paper recommends retrieving up to a target attention mass, but does not explain how to estimate coverage or stop searching without computing the full softmax denominator. Could the authors clarify this mechanism? The exact top-k generation experiments validate budget allocation, but leave the efficiency and practicality of this recommendation untested.

Questions for authors

See Weaknesses

3 comments

W1. Thanks for your comment! We added sink-preserved ANN attention evaluation here. Due to space limit, we show some selected datasets:

In each cell below: no sink → keeping sink.

2wikimqa

MethodK=32K=64K=128K=256K=512K=1024
HNSW0.633 → 0.7130.672 → 0.7560.710 → 0.7950.751 → 0.8360.794 → 0.8790.835 → 0.921
IVF256/160.494 → 0.7060.529 → 0.7450.561 → 0.7780.591 → 0.8090.609 → 0.8260.611 → 0.828
PQ0.690 → 0.7070.738 → 0.7520.784 → 0.7920.833 → 0.8350.879 → 0.8790.923 → 0.923

gov_report

MethodK=32K=64K=128K=256K=512K=1024
HNSW0.599 → 0.6970.632 → 0.7330.665 → 0.7670.702 → 0.8040.742 → 0.8450.784 → 0.887
IVF256/160.489 → 0.6920.519 → 0.7260.548 → 0.7560.577 → 0.7860.602 → 0.8120.610 → 0.821
PQ0.651 → 0.6960.706 → 0.7340.756 → 0.7700.803 → 0.8090.850 → 0.8520.896 → 0.896

hotpotqa

MethodK=32K=64K=128K=256K=512K=1024
HNSW0.581 → 0.6920.616 → 0.7300.648 → 0.7640.684 → 0.8000.724 → 0.8400.764 → 0.881
IVF256/160.480 → 0.6840.511 → 0.7190.539 → 0.7480.568 → 0.7770.595 → 0.8050.610 → 0.822
PQ0.615 → 0.6880.681 → 0.7270.736 → 0.7620.788 → 0.8000.838 → 0.8420.884 → 0.885

These provide a practical advice on the ANN attention. But this is not a common way in sparse attention to keep sinks, like DeepSeek v3.2 report[1] uses top-k without specifically retaining the sinks, so we do not evaluate this setting in this paper. We will include it in future work.

W2. Thanks for your comment! Figure 6 shows the correlation between coverage and task performance score. The Pearson correlation for 16K input is ~0.86 and for 32K is ~0.74. If we only calculate the sparse attention cases, the correlation coefficients are ~0.97 and ~0.98 for 16K and 32K. So the coverage does have significant correlation with the task performance, especially in TopK and ANN attention.

W3. Thanks for your comment! Section 8 introduces the mechanism: we select the parameter kk with a calibration query subset for each head. Specifically, on a subset of 20 separate prompts, each head receives the smallest k∈{64,128,…,4096}k\in \{64,128,\dots,4096\} whose step-averaged coverage (through dense decoding) reaches 90% on at least 80% of these prompts, or all visible keys if no k does. And these kks are then frozen in online inference. This mechanism relies on the head stability shown in Section 6. It adds no inference cost. In addition, there are existing online coverage estimation methods that can be used in our future work.

[1] Liu, Aixin, et al. "Deepseek-v3. 2: Pushing the frontier of open large language models." arXiv preprint arXiv:2512.02556 (2025).

Dear Reviewer,

This is a kind reminder that the discussion period will end in less than 24 hours. We would appreciate it if you could take a moment to review their responses and provide any further comments before the discussion period closes.

Thank you for your time and effort!

Thank you for the thorough rebuttal. The sink-preserved ANN tables, the coverage–performance analysis (including sparse-attention subsets), and the Section 8 calibration procedure address my main questions in W1–W3. I plan to increase my rating accordingly. Thank you again for the clarifications.

Reviewer_oGnVOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper presents an empirical study of sparse attention organized around two concepts, i.e., retrievability and searchability. Using Llama-3.1-8B and Qwen3-8B on RULER, LongBench, and LongProc, the paper studies the scaling of exact top-k coverage, the stability of retrievability across heads and decoding steps, and the behavior of IVF, HNSW, and PQ indexes.

The paper reports that the number of keys needed to retain 90% of the attention mass often grows sublinearly with context length, in contrast, retrievability is relatively stable at the head level and set recall is not a reliable proxy for retained attention mass.

Critical strengths
  • The retrievability/searchability decomposition is conceptually clear and useful for diagnosing why sparse attention fails.

  • The observation that set recall can disagree substantially with retained attention mass is practically relevant for evaluating ANN-based attention systems.

  • The head-level stability analysis and the heavy-tailed distribution of per-head budgets provide useful evidence for adaptive budget allocation.

Critical weaknesses
  • The central premise that exact TopK may be insufficient for attention approximation has already been established by existing works like MagicPIG. MagicPIG shows that exact TopK can have substantial estimation error and downstream degradation on aggregation and reasoning tasks, and that sampling can outperform deterministic TopK under the same budget.

  • The paper uses retained attention mass as its central metric and proves an upper bound on output error in terms of the missing mass. However, this bound is a loose worst-case bound and does not account for the geometry of the value vectors.

  • Exact TopK is computed using all query-key scores and is therefore an impracticaloracle. It is only useful for measuring an upper bound on retrievability, but it is not itself a practical sublinear attention implementation.

Questions for authors
  • What are the additional contribution of the paper relative to existing works like MagicPIG?

  • Please add sink-preserved and sink-removed baselines, since a large fraction of the reported mass is concentrated in the first few tokens.

2 comments

Thanks for your comments! Here are our responses:

Rather than proposing a new sparse-attention method, we systematically investigate the operating boundaries of exact top-k and generic ANN-based sparse attention across models, tasks, heads, context lengths, and budgets. Our contribution is a comprehensive and multi-dimensional evaluation and exploration for Top-K and ANN attention.

TopK attention is a standard and commonly used sparse attention implementation. For example, DeepSeek has used it widely in their multiple models after V3.2[1], where they calculate attention score with top-K key-values.

We add sink-preserved and sink-removed baselines here. Due to space limit, we show some selected datasets:

In each cell below: no sink → keeping sink.

2wikimqa

MethodK=32K=64K=128K=256K=512K=1024
HNSW0.633 → 0.7130.672 → 0.7560.710 → 0.7950.751 → 0.8360.794 → 0.8790.835 → 0.921
IVF256/160.494 → 0.7060.529 → 0.7450.561 → 0.7780.591 → 0.8090.609 → 0.8260.611 → 0.828
PQ0.690 → 0.7070.738 → 0.7520.784 → 0.7920.833 → 0.8350.879 → 0.8790.923 → 0.923

gov_report

MethodK=32K=64K=128K=256K=512K=1024
HNSW0.599 → 0.6970.632 → 0.7330.665 → 0.7670.702 → 0.8040.742 → 0.8450.784 → 0.887
IVF256/160.489 → 0.6920.519 → 0.7260.548 → 0.7560.577 → 0.7860.602 → 0.8120.610 → 0.821
PQ0.651 → 0.6960.706 → 0.7340.756 → 0.7700.803 → 0.8090.850 → 0.8520.896 → 0.896

hotpotqa

MethodK=32K=64K=128K=256K=512K=1024
HNSW0.581 → 0.6920.616 → 0.7300.648 → 0.7640.684 → 0.8000.724 → 0.8400.764 → 0.881
IVF256/160.480 → 0.6840.511 → 0.7190.539 → 0.7480.568 → 0.7770.595 → 0.8050.610 → 0.822
PQ0.615 → 0.6880.681 → 0.7270.736 → 0.7620.788 → 0.8000.838 → 0.8420.884 → 0.885

These provide a practical advice on the ANN attention. But this is not a common way in sparse attention to keep sinks, like DeepSeek v3.2 report[1] uses top-k without specifically retaining the sinks, so we do not evaluate this setting in this paper. We will include it in future work.

[1] Liu, Aixin, et al. "Deepseek-v3. 2: Pushing the frontier of open large language models." arXiv preprint arXiv:2512.02556 (2025).

Dear Reviewer,

This is a kind reminder that the discussion period will end in less than 24 hours. We would appreciate it if you could take a moment to review their responses and provide any further comments before the discussion period closes.

Thank you for your time and effort!

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

This paper presents an empirical study of retrieval-based sparse attention during decoding. It distinguishes retrievability, measured by the attention mass retained by exact top-kk selection, from searchability, measured by the mass recovered by approximate indexes. Using Llama-3.1-8B-Instruct and Qwen3-8B on RULER, LongBench, and LongProc, the authors investigate budget scaling with context length, head-level stability across prompts and decoding steps, and the behavior of IVF, HNSW, and PQ. The paper reports slowly growing attention budgets within certain length ranges, stable head rankings, and discrepancies between set recall and retained attention mass. Additional generation experiments evaluate frozen, head-aware budget allocation against uniform allocation at matched logical token budgets.

Critical strengths
  1. The experimental decomposition separates two sources of approximation error. Exact top-kk provides a reference for distinguishing insufficient attention concentration from imperfect retrieval. The profiling covers all 13 RULER tasks at five context lengths, with complementary measurements on natural documents and longer generations.

  2. Head stability is evaluated using a held-out protocol. Section 6 estimates rankings from early decoding steps and evaluates them on later steps of disjoint prompts across 36 model–task conditions, reporting rank correlations around 0.97. This provides stronger evidence of predictability than within-prompt stability alone.

  3. The budget-allocation experiments include relevant controls. Calibration and test prompts are separated; head-aware and uniform policies match total selected-key budgets at every layer and step; shuffled assignments and paired bootstrap confidence intervals are included. The paper also explicitly distinguishes logical sparsity from realized system efficiency.

Critical weaknesses

1. The empirical validation of coverage does not clearly evaluate the defined sparse-attention operator.

Section 3 defines the renormalized sparse output as oS=∑j∈SαjvjC(S),o_S=\frac{\sum_{j\in S}\alpha_jv_j}{C(S)}, whereas Figure 17 specifies the relative error of the unnormalized sum ∑j∈Sαjvj\sum_{j\in S}\alpha_jv_j. Unless this is a caption error, the reported correlation of ρ=−0.98\rho=-0.98 does not evaluate the sparse operator defined in the paper. The distinction is substantive: if all values equal the same nonzero vector, the renormalized output has zero error for any nonempty selection, while the unnormalized relative error equals 1−C(S)1-C(S).

This does not invalidate Proposition 1, but it leaves the empirical validation of normalized output approximation unresolved. Moreover, Appendix H shows that average coverage can reverse the ranking of allocation policies: on Qwen CWE at 32K and the 25% budget scale, uniform allocation retains 89.3% coverage versus 83.2% for head-aware allocation, yet scores 6 points lower. Although acknowledged, this limitation deserves greater prominence when deriving quality-oriented design guidelines from coverage.

2. The ANN experiments omit a critical control needed to interpret the mass-recovery gap.

Table 4 reports that the first four positions receive approximately 55% of attention mass in Llama’s full-model LongBench profiling. However, the ANN experiments do not evaluate the inexpensive alternative of always retaining these positions and retrieving only the remaining budget. Consequently, the experiments do not establish how much of the gap comes from missing fixed-position sinks versus difficulty finding content-dependent keys.

Additionally, IVF can return fewer than the requested kk keys, and the actual return counts were not logged. Thus, comparisons at the same requested budget can mix candidate underfill with retrieval errors. I appreciate the explicit restriction to generic indexes rather than complete retrieval-attention systems. Nevertheless, these controls are important for attributing the observed failure modes.

3. The practical interpretation of the length frontier is insufficiently controlled.

Appendix B states that Qwen’s 64K and 128K experiments use the released configuration without RoPE scaling, exceeding both its native window and its configured 40,960 positions. The observed loss of concentration may therefore reflect unsupported positional extrapolation rather than a boundary relevant to an appropriately extended model. Qwen’s official model documentation provides a YaRN configuration supporting contexts up to 131,072 tokens, making this a directly relevant comparison.

The authors appropriately describe the frontier as empirical rather than causal. Nevertheless, without this configuration control and corresponding dense task scores across the profiling lengths, it remains unclear how the attention-concentration boundary relates to ordinary model-capability degradation. The broader length-aware design interpretation should therefore remain explicitly configuration-specific.

4. Mass recovery does not fully demonstrate retrieval ability.

There exist a lot of circumstances where an important needle is inserted into a noisy context, and the corresponding block's attention mass is not guaranteed to be larger than other blocks.

Questions for authors
  1. Which output-error expression was actually implemented for Figure 17? If it used the unnormalized sum, does the reported advantage of coverage over recall persist when evaluating the renormalized sparse output defined in Section 3?

  2. How does the ANN–oracle gap change when the first four positions are always retained and ANN retrieves only the remaining budget? Please also report the actual number of valid returned keys to separate candidate underfill from retrieval errors.

  3. Does Qwen exhibit a similar length frontier under an appropriate YaRN configuration? How does the onset of attention diffusion compare with degradation in dense task performance under the same configuration and prompts?

3 comments

W1 and Q1: Thanks for your comment! It is a reporting error for Fig 17. We have updated the caption and re-draw Figure 17 with normalized output in PDF, and double checked other experiments to make sure there are no such mistakes.

W2 and Q2: Thanks for your comment! We evaluate the suggested method below, and keeping sinks effectively improve ANN attention quality. This provides a practical advice on the ANN attention. But this is not a common way in sparse attention to keep sinks, like DeepSeek v3.2 report[1] uses top-k without specifically retaining the sinks, so we do not evaluate this setting in this paper. We will include it in future work.

In each cell below: no sink → keeping sink.

2wikimqa

MethodK=32K=64K=128K=256K=512K=1024
HNSW0.633 → 0.7130.672 → 0.7560.710 → 0.7950.751 → 0.8360.794 → 0.8790.835 → 0.921
IVF256/160.494 → 0.7060.529 → 0.7450.561 → 0.7780.591 → 0.8090.609 → 0.8260.611 → 0.828
PQ0.690 → 0.7070.738 → 0.7520.784 → 0.7920.833 → 0.8350.879 → 0.8790.923 → 0.923

gov_report

MethodK=32K=64K=128K=256K=512K=1024
HNSW0.599 → 0.6970.632 → 0.7330.665 → 0.7670.702 → 0.8040.742 → 0.8450.784 → 0.887
IVF256/160.489 → 0.6920.519 → 0.7260.548 → 0.7560.577 → 0.7860.602 → 0.8120.610 → 0.821
PQ0.651 → 0.6960.706 → 0.7340.756 → 0.7700.803 → 0.8090.850 → 0.8520.896 → 0.896

hotpotqa

MethodK=32K=64K=128K=256K=512K=1024
HNSW0.581 → 0.6920.616 → 0.7300.648 → 0.7640.684 → 0.8000.724 → 0.8400.764 → 0.881
IVF256/160.480 → 0.6840.511 → 0.7190.539 → 0.7480.568 → 0.7770.595 → 0.8050.610 → 0.822
PQ0.615 → 0.6880.681 → 0.7270.736 → 0.7620.788 → 0.8000.838 → 0.8420.884 → 0.885

W3 and Q3: Thanks for your comment! We want to evaluate the original models rather than our modified models, so we did not evaluate with YARN. The results therefore reflect each model’s own behavior rather than that of a context-extended variant. For LongBench the 40K limit for Qwen almost never applies. We have updated Appendix B to remove the confusion.

[1] Liu, Aixin, et al. "Deepseek-v3. 2: Pushing the frontier of open large language models." arXiv preprint arXiv:2512.02556 (2025).

Dear Reviewer,

This is a kind reminder that the discussion period will end in less than 24 hours. We would appreciate it if you could take a moment to review their responses and provide any further comments before the discussion period closes.

Thank you for your time and effort!

I appreciate the authors' detailed responses and additional experiments, which have addressed some of my concerns. However, several concerns remain insufficiently resolved. In particular, Q3 regarding the interpretation of the length frontier remains open without appropriate context-extension controls. W4, concerning the distinction between attention mass recovery and actual retrieval ability, has not been directly addressed. Additionally, the attribution of the ANN search gap (W2) remains incomplete, especially regarding the effects of attention sinks and candidate underfill. Therefore, I will maintain my original score.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.