acceptodds
Under review as a conference paper at ICLR 2027

Attend at the Right Resolution: Head-Adaptive Sparse Attention via Query–Key Interaction Structure

21 views

Abstract

Attention is a major scalability bottleneck in large language models (LLMs), with its computational cost and key-value (KV) memory traffic becoming increasingly prohibitive as context length grows. Sparse attention addresses this bottleneck by restricting each query to a subset of the context, but its effectiveness hinges on identifying relevant regions both cheaply and reliably. Existing training-free methods primarily rely on runtime relevance estimates, with selection dimensionality and granularity typically governed by fixed heuristics rather than the intrinsic interaction structure of pretrained attention heads. We take a different perspective: the query–key operator of each pretrained head defines a characteristic response structure that determines the resolution needed for sparse selection, both across feature directions and across context tokens. Building on this insight, we propose Head-Adaptive Sparse Attention (HASA), a training-free sparse attention framework that jointly adapts selection resolution along these two dimensions. Along the feature dimension, the singular spectrum of each head's query–key operator determines an effective rank, yielding a compact, head-specific response space. Along the sequence dimension, neighboring regions are progressively merged according to the directional coherence of their token responses in this same space, while heterogeneous regions remain separate. Exact attention is then computed using the original full-dimensional KV states of the selected regions. HASA captures 88.1% of dense-attention mass and, compared with UNIQUE, a strong recent sparse-attention baseline, improves accuracy by up to 3.47 and 2.57 points on RULER and LongBench-Pro, respectively, and accelerates self-attention by up to 1.32 times, while achieving up to 14.07 times speedup over dense attention.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Large Language Models, Sparse Attention, Efficient Inference, Training-free Methods

Reviews

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

This paper uses the weight of the QK projection of attention (the spectrum of WQTW_Q^T, WKW_K) to determine the sparsification strategy for each head. The feature rank for routing and the block granularity are adapted per head, and exact attention is computed on the selected KV.

Critical strengths

This paper shows that we can find a sparsification strategy by analyzing the weight matrix of QK. The idea is simple and training-free, and the rank selection is done offline, so the runtime overhead is small.

The theoretical analysis of the routing error is a nice addition.

Critical weaknesses
  1. Tensor parallel (head parallel) imbalance. In HASA, both the rank r_h and the number of regions I_h differ across heads, and I_h is input-dependent. This makes the selection cost different per head, so under tensor parallelism the slowest GPU decides the latency. The paper does not discuss this at all, and the efficiency result (Fig. 4) is only single-kernel self-attention latency, with no hardware, batch size, multi-GPU, or end-to-end throughput.

  2. Novelty of head-adaptive sparsity. Allocating different sparsity across heads is not new. SEA (Lee et al., ICLR 2024) already selects top-k jointly across heads, so each head gets a different budget dynamically. FlexPrefill also adjusts the budget per head. The new part of this paper is only where the adaptation signal comes from (the QK weight spectrum). The authors should clarify the difference from these kinds of works.

  3. The baseline is too weak. We lack stronger baselines, such as FlexPrefill and MInference, which already allocate different sparsity per head.

Questions for authors

Please check weakness section to answer my concerns.

4 comments

We appreciate your positive assessment of HASA's unified head-adaptive design, its clear technical narrative, and its training-free nature, as well as your recognition of the value of our theoretical analysis. We welcome the opportunity to address your questions.

W1a: Workload Imbalance under Tensor Parallelism

Thank you for raising this question. Although HASA's adaptive feature and sequence resolutions introduce variations in routing workload across GPUs, the routing computation accounts for only a small fraction of the overall decoding cost. This is because the decode latency is dominated by costs that are uniform across heads (e.g., kernel launches, fixed-budget attention).

To evaluate its practical impact, we compare adaptive and fixed resolutions under 8-GPU tensor parallelism on NVIDIA V100 GPUs (batch size 16, 32K context length, and 512-token KV budget). As shown in Table R11, despite variations in per-GPU routing workload, the end-to-end decoding latency differs by only 0.15%, demonstrating that the practical impact is negligible under the evaluated configuration.

Table R11. Comparison of routing workload and decode latency between HASA and fixed resolution.

MetricHASA (Adaptive)Fixed Resolution
Per-GPU routing work (M MACs)2.3–3.02.8
Per-token decode latency (ms)32.0832.03

W1b: End-to-End Efficiency

Thank you for your suggestion. In addition to the evaluation protocol in Appendix C.1, all measurements use 8 NVIDIA V100 GPUs, batch size 16, KV budget 512, and FP16 precision.

Regarding end-to-end inference acceleration, we further measure full-model decoding latency and throughput, including kernel-launch overhead, non-attention layers, synchronization, and multi-GPU communication (Table R12). HASA achieves 1.78–5.94× end-to-end decoding speedup over dense attention and approximately 1.19× over UNIQUE from 8K to 32K contexts, while maintaining nearly constant decoding throughput (499–512 tokens/s).

We will incorporate these additional results and evaluation details into the revised manuscript.

Table R12. End-to-end decoding latency and throughput comparison across different context lengths.

ContextMethodLatency (ms) ↓Throughput (tok/s) ↑
8KDense55.64288
UNIQUE37.18430
HASA31.24512
16KDense93.74171
UNIQUE37.50427
HASA31.57507
32KDense190.5084
UNIQUE38.20419
HASA32.08499

W2: Novelty of Head-Adaptive Sparsity

Thank you for the opportunity to clarify our contribution. The key novelty of HASA is the joint adaptation of feature resolution and sequence resolution based on a unified characterization of the query–key interaction structure. By coupling these two dimensions, HASA achieves not merely higher accuracy or lower latency in isolation, but an advancement of the accuracy–latency Pareto frontier.

This fundamentally differs from SEA and FlexPrefill, which primarily adapt the sparse support, pattern, or budget across heads. While these methods adapt the outcome of sparse selection, HASA adapts the computational process of selection itself. Specifically, the QK spectrum determines the compact response space, which in turn changes the distinguishability of tokens and thus governs the appropriate sequence granularity. The QK spectrum is therefore not merely an alternative adaptation signal, but a unified structural basis that intrinsically connects both resolutions. In principle, HASA's resolution adaptation is complementary to adaptive sparsity allocation.

We will further clarify our distinction from FlexPrefill in the existing Related Work discussion and include an explicit discussion of SEA.

W3: Additional Competitive Baselines

Thank you for suggesting these additional baselines. We have expanded our evaluation to include FlexPrefill and MInference, as well as DHSA, in Tables R13 and R14, covering three KV budgets (512, 1024, and 2048). Across all evaluated budgets and model backbones, HASA consistently achieves the strongest overall performance among the considered sparse-attention methods. Among all evaluated baselines, UNIQUE from our original evaluation remains the strongest overall.

We will incorporate these results into the revised manuscript.

Table R13. Accuracy results on LongBench-Pro using Ministral-3-8B-Instruct-2512.

MethodBudgetOverallEnZhExtremeHardModerateEasy
Full attention--37.7035.8838.9631.1333.7231.6048.86
FlexPrefill204828.8728.3429.4017.0130.2823.2238.53
DHSA204832.2030.9433.4723.5232.3024.5441.27
MInference204830.6230.1831.0522.9130.4924.1938.59
UNIQUE204837.1135.5738.1531.2833.1831.0347.66
HASA (Ours)204837.6236.9038.2832.8034.1031.0147.25
FlexPrefill102422.5223.0022.0414.6421.3317.6530.41
DHSA102428.2826.8529.7117.9829.9423.3436.50
MInference102427.3027.7226.8818.7128.5819.4135.88
UNIQUE102436.7235.7737.9831.0232.7830.7548.34
HASA (Ours)102437.5336.6638.7432.1733.8332.2748.63
FlexPrefill51213.7514.5312.9710.9112.9110.7917.30
DHSA51223.4724.1022.8514.2424.8717.1031.74
MInference51225.7025.1926.2017.2727.8619.9732.82
UNIQUE51236.5835.2238.2330.8633.7530.3747.67
HASA (Ours)51237.4335.0240.1330.9134.2732.9448.46

Table R14. Accuracy results on RULER-32K using Ministral-3-8B-Instruct-2512.

MethodBudgetSG1SG2SG3MK1MK2MK3MVMQVTCWEFWEQA1QA2Avg.
Full attention--100.0099.6099.6099.40100.0099.8098.5599.0599.9688.4693.2775.8057.4093.15
FlexPrefill2048100.00100.00100.0070.0094.0069.0091.2596.0089.4043.6096.6757.0051.0081.38
DHSA2048100.00100.00100.0096.0093.0084.0094.5096.0099.8089.0096.0069.0057.0090.33
MInference2048100.00100.0099.0099.00100.0093.0095.50100.0099.6038.5093.6771.0061.0088.48
UNIQUE2048100.0099.8099.2099.60100.0099.8099.0099.1599.9682.2891.0775.6057.4092.53
HASA (Ours)2048100.00100.00100.00100.0099.0099.8098.5199.15100.0083.8690.4376.5357.4092.67
FlexPrefill1024100.00100.0098.0060.0076.0045.0073.5086.5036.409.5097.0031.0049.0066.30
DHSA1024100.00100.00100.0090.0085.0063.0089.7593.7597.2059.5097.6765.0051.0083.99
MInference1024100.00100.0099.0098.0097.0076.0089.5099.7593.8027.5095.3370.0052.0084.45
UNIQUE1024100.0099.8099.2099.60100.0099.8099.0099.1599.9675.3890.9675.1657.5691.97
HASA (Ours)1024100.00100.00100.00100.0099.0199.7998.5199.15100.0078.3990.2776.0957.5692.21
FlexPrefill51291.0090.0062.0028.0010.009.0038.5045.753.004.2086.3314.0026.0039.06
DHSA512100.00100.00100.0071.0073.0035.0078.0085.7579.0019.3098.6750.0045.0071.98
MInference512100.0099.00100.0097.0074.0035.0082.0099.5062.2021.2093.0050.0046.0073.76
UNIQUE512100.0099.8099.2099.80100.0099.6099.5599.3099.9662.9088.6773.6057.8090.78
HASA (Ours)512100.00100.00100.0099.80100.0099.20100.00100.00100.0066.3787.7374.5457.4091.16

Thank you again for your thoughtful review and constructive feedback. As the discussion period is drawing to a close, we wanted to briefly check in and see if our responses and additional results have addressed your concerns.

Please let us know if you have any remaining questions or if there is anything else we can clarify. We sincerely appreciate your time and consideration.

Thank you again for your thoughtful review and constructive feedback. As the discussion period is approaching its end, we would like to briefly highlight that we have provided additional evidence directly addressing the three concerns raised in your original review:

W1 (Tensor-parallel efficiency): We conducted an 8-GPU tensor-parallel evaluation showing only a 0.15% difference in end-to-end decoding latency between adaptive and fixed resolutions. We also reported full-model decoding measurements, demonstrating up to 5.94× speedup over dense attention and approximately 1.19× over UNIQUE.

W2 (Novelty): We clarified that HASA jointly adapts feature and sequence resolutions based on the QK interaction spectrum, distinguishing it from prior methods that primarily adapt sparsity patterns or budgets across heads.

W3 (Competitive baselines): We added comparisons against FlexPrefill, MInference, and DHSA across three KV budgets, with HASA consistently achieving the strongest overall performance among the evaluated sparse-attention methods.

Given these additional analyses and experiments, we would greatly appreciate your reassessment of whether the original concerns have been sufficiently addressed, particularly whether any remaining issues materially affect the technical soundness or overall contribution of our work.

Thank you again for your time and consideration.

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

This paper presents Head-Adaptive Sparse Attention, a training-free sparse attention method for long-context modeling. Its core insight is that query–key interaction patterns differ across attention heads; accordingly, sparse routing should not adopt a uniform feature dimension and sequence chunking granularity for all heads. The authors conduct experiments on Ministral-3-8B-Instruct-2512 and Qwen3-8B with LongBench-Pro and RULER-32K.

Critical strengths
  1. Unified and intuitively appealing head-adaptive design. The paper leverages a shared query–key response space to determine both feature rank and sequence chunking granularity, instead of treating low-rank routing and adaptive chunking as two independent heuristic components. This unified perspective carries some novelty and yields a relatively clear technical narrative.
  2. Low training overhead and comprehensive experimental coverage. The spectral analysis in HASA can be performed offline, without retraining or fine-tuning the model. The final attention over selected regions still uses the original KV, avoiding direct replacement of attention computation with low-rank representations. Evaluations are conducted across two models, two long-context benchmarks, and multiple KV budgets. Ablation studies and hyperparameter sensitivity experiments are provided, offering preliminary evidence for the complementarity of the two adaptive modules.
Critical weaknesses
  1. The core formulation does not account for RoPE, which may undermine the theoretical foundation of the method. The paper expresses the attention logit as a fixed bilinear operator hi⊤WQ⊤WKhth_i^\top W_Q^\top W_K h_t. However, for the experimental models equipped with RoPE/YaRN, the actual operator additionally includes position-dependent rotation terms WQ⊤Rt−iWKW_Q^\top R_{t-i} W_K, so WQ⊤WKW_Q^\top W_K is not fixed. The paper does not clarify whether low-rank routing is performed before or after positional rotation. This casts doubt on whether the claimed exact equivalence in Equation (1), the singular-spectrum interpretation, and the error bounds in the appendix hold for the actual models, constituting the primary soundness concern.

  2. There is no formal definition of how variable-length regions strictly adhere to a fixed KV-token budget. HASA selects top-KK regions, yet each region can vary in length from 8 up to Cmax⁡=512C_{\max}=512. A fixed number of regions therefore does not correspond to a fixed token count, even though the experiments claim matched budgets of 512, 1024, and 2048 tokens across all methods. The paper does not explain how over-budget regions are handled, whether local context counts toward the budget, and whether selection is based on raw scores, per-token scores, or other criteria. This directly compromises the fairness of the accuracy and efficiency comparisons.

  3. The definition of head-adaptive routing under GQA remains ambiguous. Both evaluated models adopt grouped-query attention, where multiple query heads share a single KV head. The paper at times defines MhM_h per attention head, while the figures present rank and block size per KV head. If each query head constructs its own routing space, separate key responses and region statistics must be stored. If routing is shared within a KV group, the paper must specify how multiple distinct WQW_Q matrices are reconciled. This ambiguity affects the method definition, memory overhead, and reproducibility.

  4. The efficiency evidence is insufficient to substantiate the main speedup claim. Only self-attention microbenchmark results are reported. Essential details such as hardware configuration, batch size, numerical precision, kernel implementation, and measurement variance are missing. It is also unspecified whether the timing includes low-rank projection, region updates, top-KK selection, KV gathering, and additional kernel launches. The memory footprint of the additional response cache and region statistics is likewise omitted. Consequently, the reported speedup of up to 14.07×14.07\times cannot be interpreted as end-to-end inference acceleration.

  5. The empirical gains are insufficient to demonstrate a substantial advance over prior work. Compared with the strongest baseline, UNIQUE, most improvements in the overall average scores in the main tables are only approximately 0.1–0.9 points. The highlighted gains of 3.47 and 2.57 points come from specific subtasks or difficulty subsets rather than aggregate metrics. Moreover, the paper does not report confidence intervals or statistical significance analyses, and it omits comparisons against closely related adaptive sparse-attention methods, including AB-Sparse, DHSA, and Tactic. The current experiments therefore do not establish whether the improvements are robust or whether HASA genuinely outperforms the most relevant prior work.

Questions for authors

Questions for Authors

  1. How does the formulation in Equation (1) handle RoPE/YaRN? Is low-rank routing performed before or after positional rotation? For the position-dependent operator (WQh)⊤Ri⊤RtWKh(W_Q^h)^\top R_i^\top R_t W_K^h, which reduces to (WQh)⊤Rt−iWKh(W_Q^h)^\top R_{t-i}W_K^h under standard RoPE, do the singular-spectrum interpretation and theoretical error bounds in the paper still hold?

  2. How does HASA strictly enforce a fixed KV-token budget when candidate regions have different lengths? How is a region handled if its inclusion would exceed the remaining budget? Does the additionally included local context count toward the reported 512/1024/2048-token budget?

  3. How is head-adaptive routing implemented under grouped-query attention (GQA)? Are MhM_h, the low-dimensional response space, and the region partition constructed per query head or per KV head? If the routing space is shared within the same KV group, how are the distinct WQhW_Q^h matrices reconciled?

  4. Does the reported latency include the full overhead of low-rank projection, region construction and updates, top-KK selection, KV gathering, and additional kernel launches? Please also provide the hardware configuration, batch size, numerical precision, kernel implementation details, and additional memory footprint.

  5. Given the comparatively modest gains on aggregate metrics, could the authors provide confidence intervals or statistical significance analyses and add comparisons with more closely related adaptive sparse-attention methods, such as AB-Sparse, DHSA, and Tactic?

6 comments

We appreciate your positive assessment of HASA's unified head-adaptive design, its novelty, and the clear technical narrative, as well as your recognition of its training-free nature and comprehensive experimental coverage. We are pleased to provide further clarification below.

W1/Q1: RoPE/YaRN Compatibility

Thank you for pointing this out. HASA deliberately uses the pre-RoPE query–key interaction structure for approximate region routing, rather than attempting to reproduce the exact position-aware attention logits. This allows the compact, head-specific routing space to be determined offline. Importantly, the final attention over selected tokens uses the original full-dimensional Q/K/V with the model's native RoPE/YaRN, so positional encoding is fully preserved in the actual attention computation.

The approximation error admits the following bound: ∥Mh,Δ−Mh,r∥2≤σr+1(Mh)+∥WQ∥2∥RΔ−I∥2∥WK∥2,\Vert M_{h,\Delta}-M_{h,r}\Vert_2 \leq \sigma_{r+1}(M_h) + \Vert W_Q\Vert_2 \Vert R_\Delta - I\Vert_2 \Vert W_K\Vert_2, This separates spectral truncation from positional mismatch; the original theoretical bounds concern the former. The effectiveness of this routing approximation is further supported by 88.1% dense-attention-mass recall and near-dense accuracy under native RoPE/YaRN inference. As discussed in our Limitations section, the fixed interaction operator provides an approximate characterization of runtime attention. We will further clarify how RoPE/YaRN positional effects fit within this approximation.

W2/Q2: Fixed KV-token Budget

Thank you for raising this important question. HASA strictly adheres to a fixed KV-token budget in all our experiments, including the local context. Given a token budget BB, HASA first accounts for the local context LqL_q, leaving Brem=B−∣Lq∣B_{\mathrm{rem}}=B-|L_q| for non-local regions. Candidate regions are ranked directly using the relevance score in Eq. (10) and selected subject to their token cost. A region CC is admitted if ∣C∣≤Brem|C|\leq B_{\mathrm{rem}}, with the remaining budget updated accordingly. If a merged region exceeds the remaining budget, HASA recursively evaluates its finer-grained constituent regions until they fit the available budget, down to the base granularity of S0=8S_0=8 tokens. If the remaining budget is smaller than S0S_0, HASA leaves the residual budget unused rather than exceeding the token limit.

This procedure is naturally supported by our bottom-up region construction, where larger regions are formed by progressively merging neighboring finer-grained regions. Adaptive sequence resolution determines how efficiently the candidate space is represented and searched, while the fixed token budget controls how much context can be retrieved. All methods are therefore evaluated under the same 512/1024/2048-token budgets, including local context, ensuring fair comparisons.

We will clarify this budget-constrained selection procedure in Sec. 3.3.

W3/Q3: Head-Adaptive Routing under GQA

Under GQA, HASA constructs a shared key-side routing space for each KV group while retaining query-head-specific routing decisions. Each KV head (g) is shared by (m=4) query heads, with distinct query projections WQg,jW_Q^{g,j} and a common key projection WKgW_K^g. We construct the corresponding interaction operators Mg,j=(WQg,j)⊤WKgM_{g,j}=(W_Q^{g,j})^\top W_K^g, and jointly characterize the group through the stacked operator [Mg=[Mg,1⋯Mg,m]=UgΣgVg⊤.][\mathcal{M}g=\begin{bmatrix}M{g,1}\cdots M_{g,m}\end{bmatrix}=U_g\Sigma_gV_g^\top.].

The singular spectrum of Mg\mathcal{M}_g determines a shared feature rank rgr_g. The right singular vectors VgV_g define a shared compact key-side response space, while the corresponding blocks of UgU_g enable query-head-specific projections and relevance scores.

This design naturally follows the sharing structure of GQA. In our evaluated models with 32 query heads and 8 KV heads, HASA maintains only 8 key-side routing spaces, region partitions, and sets of region statistics (as shown in Fig. 3(d)), avoiding redundant key-side storage across query heads while retaining individual routing decisions for all 32 query heads.

We will make this GQA formulation explicit in the methodology and implementation details.

W4/Q4: Efficiency Evaluation

Thank you for your questions. In addition to the evaluation protocol in Appendix C.1, all measurements use 8 NVIDIA V100 GPUs, batch size 16, KV budget 512, and FP16 precision. At 32K context, the additional HASA routing state occupies only 22.5 MB (0.52% of the original KV-cache size), while the original full-dimensional KV cache remains unchanged. We will include these additional details in the appendix.

Regarding end-to-end inference acceleration, we further measure full-model decoding latency, including kernel-launch overhead, non-attention layers, synchronization, and multi-GPU communication. HASA achieves 1.78–5.94$\times$ end-to-end decoding speedup over dense attention from 8K to 32K contexts, while maintaining nearly constant per-token decoding latency as context length increases.

Table R5. End-to-end decode latency and throughput comparison across different context lengths.

ContextMethodDecode Latency (ms) ↓Throughput (tok/s) ↑
8KDense55.64288
UNIQUE37.18430
HASA31.24512
16KDense93.74171
UNIQUE37.50427
HASA31.57507
32KDense190.5084
UNIQUE38.20419
HASA32.08499

To individually assess the runtime overhead of each component, we break down HASA's runtime into relevance estimation (low-rank projection, block merging, and scoring), top-K selection (KV gathering), and the sparse-attention kernel, as shown in the table below. HASA is implemented using custom CUDA kernels, and the reported attention-level latency includes all online overheads: low-rank projection, region construction/updates, relevance scoring, Top-KK selection, KV gathering, and associated kernel launches. The offline SVD and rank computation are performed once before inference and incur no runtime overhead. Across 8K/16K/32K contexts, the complete HASA attention path takes 74/146/299 μ\mus, compared with 470/1256/4203 μ\mus for dense attention. These results demonstrate that HASA's routing overhead remains small and that its attention-level savings translate into substantial end-to-end decoding gains.

Table R6. Runtime breakdown of HASA vs dense attention across different context lengths.

Context LengthRelevance Est. (µs)Top-K Sel. (µs)Attn. Kernel (µs)HASA Total (µs)Dense Attn. (µs)
8K2963974470
16K3091071461256
32K30152542994203

W5/Q5: Significance of Empirical Gains and Comparison with Prior Work

Thank you for suggesting these additional experiments. We would first like to emphasize that the key contribution of HASA is to advance the accuracy–latency Pareto frontier. While retaining or discarding more KV tokens can trade accuracy for efficiency or vice versa, HASA exploits the intrinsic query–key interaction structure of attention heads to improve both dimensions simultaneously. Its empirical gains should therefore be evaluated jointly across both dimensions, rather than through accuracy improvements alone.

1. Statistical Significance Analysis.

Following your suggestion, we compute 95% confidence intervals for the accuracy improvements over UNIQUE (our strongest baseline) across both benchmarks and all three KV budgets. As shown in Table R7, all six comparisons favor HASA. Notably, even when considering accuracy alone, the improvements are statistically significant across all three KV budgets on LongBench-Pro and at the 512-token budget on RULER-32K.

Table R7. Accuracy gains over UNIQUE with 95% confidence intervals.

KV BudgetLongBench-Pro GainLongBench-Pro 95% CIRULER-32K GainRULER-32K 95% CI
2048+0.51[+0.24, +1.42]+0.14[-0.37, +0.68]
1024+0.81[+0.18, +2.06]+0.24[-0.36, +1.00]
512+0.85[+0.18, +1.64]+0.38[+0.02, +1.14]

2. Additional Competitive Baselines.

We have expanded our evaluation to include FlexPrefill, DHSA, and MInference in Tables R8 and R9, covering three KV budgets (512, 1024, and 2048). Across all evaluated budgets and model backbones, HASA consistently achieves the strongest overall performance among the evaluated sparse-attention baselines, including these additional methods. In terms of efficiency (Table R10), these additional methods apply sparsity only during prefill and retain dense attention during decoding, whereas HASA substantially reduces decoding latency (Section 4.2, Figure 4).

We do not include AB-Sparse and Tactic because their implementations are not publicly available. These expanded comparisons provide further evidence that HASA advances the accuracy–latency Pareto frontier even when compared against a broader range of competitive sparse-attention methods.

We will incorporate the additional experimental results and statistical analysis into the revised manuscript.

Table R8. Accuracy results on LongBench-Pro using Ministral-3-8B-Instruct-2512.

MethodBudgetOverallEnZhExtremeHardModerateEasy
Full attention--37.7035.8838.9631.1333.7231.6048.86
FlexPrefill204828.8728.3429.4017.0130.2823.2238.53
DHSA204832.2030.9433.4723.5232.3024.5441.27
MInference204830.6230.1831.0522.9130.4924.1938.59
UNIQUE204837.1135.5738.1531.2833.1831.0347.66
HASA (Ours)204837.6236.9038.2832.8034.1031.0147.25
FlexPrefill102422.5223.0022.0414.6421.3317.6530.41
DHSA102428.2826.8529.7117.9829.9423.3436.50
MInference102427.3027.7226.8818.7128.5819.4135.88
UNIQUE102436.7235.7737.9831.0232.7830.7548.34
HASA (Ours)102437.5336.6638.7432.1733.8332.2748.63
FlexPrefill51213.7514.5312.9710.9112.9110.7917.30
DHSA51223.4724.1022.8514.2424.8717.1031.74
MInference51225.7025.1926.2017.2727.8619.9732.82
UNIQUE51236.5835.2238.2330.8633.7530.3747.67
HASA (Ours)51237.4335.0240.1330.9134.2732.9448.46
Reviewer_PfdnOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

This paper proposes Head-Adaptive Sparse Attention (HASA), a training-free sparse attention for pre-trained LLMs with full attention. HASA first uses singular value decomposition to obtain the low-rank representations for each head's KV cache. After that, the neighboring regions of KV caches are progressively merged based on the directional coherence. Exact attention is computed on the processed KV states. HASA achieves up to 14x speedup over dense attention.

Critical strengths
  1. The proposed method achieves the almost best performance compared with the other sparse baselines.
  2. The paper writing is good and easy to follow.
Critical weaknesses
  1. The proposed method is difficult to applied the cutting-edge LLMs, especially Deepseek models with sparse attention and Qwen, Kimi models with linear attention. These post-hoc sparse attention methods unavoidably damage the performance of the raw LLM due to the compression representation of KV caches and mismatch of the training and inference process.
  2. The paper lacks the empirical efficiency analysis of the proposed method, such as the time cost of the HASA process compared with raw attention. When HASA is more efficient, prefill or decode phase? How is the efficiency gap between HASA with raw attention method with different lengths of sequence?
  3. The method is evaluated on some typical long-sequence benchmarks, such as LongBench-Pro and RULER-32K, while lack more general evaluation dataset for model capability evaluation. What is the compression effect on other extensively-used evaluation datasets, such as math datasets (GSM8K, math500) and code dataset (humaneval, mbpp).
Questions for authors

See above weaknesses.

6 comments

Thank you for recognizing HASA's competitive performance, substantial speedup, and the clarity of our presentation. We are happy to answer your questions below.

W1(a): HASA's Applicability and Practical Value

Thank you for highlighting this important question. First, we believe that efficient softmax attention remains highly relevant to cutting-edge LLMs. Although recent models have introduced specialized sparse or linear attention mechanisms, these approaches have not displaced softmax attention. Notably, even cutting-edge hybrid architectures, such as Qwen3-Next and Kimi Linear, retain full-attention layers to balance efficiency and expressiveness [1, 2]. Moreover, such methods typically require architectural modifications and retraining, limiting its direct applicability to cutting-edge LLMs. Second, HASA addresses a complementary and practically important setting as a training-free method: it improves the inference efficiency of existing pretrained models without architectural redesign or retraining. This remains a critical and an actively advancing research direction, as demonstrated by Quest, StreamingLLM, and InfLLM. More importantly, HASA is not merely a plug-in inference optimization, but introduces a broader design principle: each head's query–key interaction structure jointly guides the feature resolution for relevance estimation and the sequence granularity for sparse selection. This principle could also inform the design of future training-based sparse or hybrid attention architectures.

To further validate HASA's applicability to cutting-edge LLMs, we additionally evaluate it on Llama-3.1-8B and Granite-3.3-8B across LongBench-Pro and RULER-32K (Table R1). Together with Ministral-3-8B-Instruct-2512 and Qwen3-8B, these experiments cover four modern LLM backbones. HASA retains 97.0–99.4% of dense-attention accuracy on the two additional models, while achieving up to 14.07× inference speedup over dense attention and 1.32× over the strongest sparse-attention baseline. These results demonstrate that HASA delivers substantial inference efficiency improvements while preserving near-dense accuracy across diverse modern pretrained LLMs, without retraining.

Table R1. Additional backbone evaluation. Δ\Delta denotes the change relative to dense attention.

BenchmarkModelDenseHASAΔ\Delta
RULER-32KGranite-3.3-8B80.7180.21-0.50
RULER-32KLlama-3.1-8B92.0289.66-2.37
LongBench-ProGranite-3.3-8B23.0422.80-0.24
LongBench-ProLlama-3.1-8B21.1020.47-0.63

W1(b): KV Compression and Performance Preservation

Thank you for raising this concern. First, we would like to clarify that HASA does not compress or modify the original KV representations. Instead, we use compact query–key representations exclusively for query-dependent, content-aware sparse selection, while computing attention over the original full-dimensional KV states of the selected regions. Second, we provide theoretical guarantees for this routing approximation in Appendix A. In Lemma 1, we establish an explicit bound on region-score approximation error in terms of the discarded singular spectrum. In Corollary 1, we further show that the Top-K selected regions are preserved, for a fixed set of candidate regions, when the selection margin exceeds twice the error bound. Finally, our experiments validate this design: we preserve 88.1% of dense-attention mass and achieve near-dense downstream accuracy without retraining. Together, these results show that HASA avoids KV representation compression errors while controlling the accuracy impact of sparse selection through principled routing. Finally, since the original KV representations and pretrained attention parameters remain unchanged, HASA introduces no representation-level training--inference mismatch.

References:

[1] Zhang, Y., et al. Kimi Linear: An Expressive, Efficient Attention Architecture, arXiv, arXiv:2510.26692, 2025.

[2] Qwen Team. Qwen3-Next: Towards Ultimate Training & Inference Efficiency. Qwen Official Blog, 2025.

W2: Efficiency Breakdown and Scaling

Thank you for your suggestion. First, we would like to emphasize that computational efficiency has been a key consideration in HASA's design from the outset. In particular, to avoid costly adaptive region partitioning, we employ additive region statistics that support incremental merging and summary updates without revisiting constituent tokens (Section 3.2 and Appendix B). Each candidate merge requires only O(rh)O(r_h) operations, independent of region size, ensuring that adaptive region construction remains efficient as context length increases.

To further substantiate this design with direct measurements, we provide a detailed runtime breakdown at 8K, 16K, and 32K context lengths (Table R2). Relevance estimation (which includes adaptive region construction) and Top-(K) selection take 35, 39, and 45 μ\mus, accounting for 7.45%, 3.11%, and 1.07% of dense-attention runtime, respectively. Including sparse-attention execution, HASA achieves 6.35$\times$, 8.60$\times$, and 14.07$\times$ attention-level speedups over dense attention. These results confirm that the relative overhead decreases and the efficiency advantage grows with context length.

Table R2. Runtime breakdown of HASA vs dense attention across different context lengths.

Context LengthRelevance Est. (μ\mus)Top-KK Sel. (μ\mus)Attn. Kernel (μ\mus)HASA Total (μ\mus)Dense Attn. (μ\mus)
8K2963974470
16K3091071461256
32K30152542994203

Regarding the inference phase, HASA primarily targets decoding, where each generated token attends to an expanding KV cache. Our additional end-to-end experiments on 8 V100 GPUs (batch size 16, KV budget 512) show 1.78×, 2.97×, and 5.94× decode speedups over dense attention at 8K, 16K, and 32K, respectively, and approximately 1.19× over UNIQUE (Table R3). These results demonstrate that the attention-level gains translate into practical long-context decoding improvements.

Table R3: End-to-end decode latency and throughput comparison across different context lengths.

ContextMethodDecode Latency (ms) ↓Throughput (tok/s) ↑
8KDense55.64288
UNIQUE37.18430
HASA31.24512
16KDense93.74171
UNIQUE37.50427
HASA31.57507
32KDense190.5084
UNIQUE38.20419
HASA32.08499

W3: General Capability Preservation

We appreciate your recommendation to broaden the evaluation. We additionally evaluate HASA on all four requested benchmarks—GSM8K, MATH-500, HumanEval, and MBPP—to assess its impact on mathematical reasoning and coding capabilities. As shown in Table R4, HASA closely preserves dense-attention performance at 25% KV-cache budget, achieving an average score of 78.3 versus 78.6 for dense attention (a decrease of only 0.3 points). It also outperforms other sparse-attention baselines, including UNIQUE (77.1) and Quest (76.7), across these tasks on average.

Together with our long-context results, these findings further demonstrate that HASA's head-adaptive design achieves an effective balance between computational efficiency and accuracy preservation, extending its benefits beyond long-context benchmarks.

Table R4. Performance comparison on additional math and code datasets.

ModelMethodGSM8KMATH-500HumanEvalMBPPAvg. (Δ\Delta vs dense)
Ministral-3-8BDense94.885.273.860.778.6
Quest92.982.672.059.176.7 (-2.0)
UNIQUE93.382.872.060.077.1 (-1.7)
Ours93.784.075.660.178.3 (-0.3)

Thank you again for your thoughtful review and constructive feedback. As the discussion period is drawing to a close, we wanted to briefly check in and see if our responses and additional results have addressed your concerns.

Please let us know if you have any remaining questions or if there is anything else we can clarify. We sincerely appreciate your time and consideration.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Common Response

We thank all the reviewers for their time and constructive feedback, and the Area Chair for overseeing the discussion and carefully considering our submission.

Following the rebuttal, we have incorporated additional theoretical analyses, experimental results, and technical clarifications into the revised manuscript. These revisions preserve the original methodology, technical contributions, and conclusions while providing further support for HASA's effectiveness and practical value. Rather than repeating the detailed point-by-point responses provided in the rebuttal, we summarize the major revisions below. All new and modified content is highlighted in blue in the revised manuscript.

Main Paper

Abstract, Introduction, and Conclusion

We refined the presentation of HASA's central contribution: advancing the accuracy–latency Pareto frontier through joint adaptation of feature and sequence resolutions. In particular, we clarified how the pre-trained query–key interaction structure provides a unified structural basis connecting both resolutions. We also incorporated the end-to-end decoding results to further demonstrate the practical benefits of HASA.

Related Work

We expanded the discussion of existing adaptive sparse attention methods, including SEA and FlexPrefill, and clarified the distinction between HASA's adaptation of the sparse selection process itself and existing approaches that primarily adapt sparse patterns, support, or budget allocation across heads.

Methodology

We provided further technical and algorithmic clarifications on:

  • The distinction between pre-positional spectral routing and exact sparse attention using the original KV representations and native positional encoding.
  • The formulation of head-adaptive routing under grouped-query attention (GQA).
  • The budget-constrained selection procedure for variable-sized candidate regions.
  • The deliberate design of the directional-purity criterion and additive region statistics to enable efficient incremental merging, with a per-merge computational cost independent of region size.

Experiments

We extended the empirical evaluation and incorporated the following results into the main paper:

  • Comparisons against three additional competitive baselines: FlexPrefill, DHSA, and MInference.
  • End-to-end decoding latency and throughput measurements, demonstrating up to 5.94× speedup over dense attention and 1.19× over UNIQUE.
  • An explicit accuracy–latency Pareto frontier comparison.
  • Supporting results from statistical significance analysis and runtime breakdown.

Limitations

We clarified the limitations of pre-positional spectral characterization and discussed the potential applicability of joint resolution adaptation to training-based sparse and hybrid attention architectures.

Appendix Additions and Extensions

Theoretical and Algorithmic Analysis

We added an approximation error bound accounting for positional transformations and a detailed mathematical formulation of HASA under GQA.

Evaluation Setup and Implementation Details

We expanded the descriptions of the competitive baselines, evaluation configurations, and efficiency measurement protocols to improve clarity and reproducibility.

Additional Backbone Evaluation

We extended the evaluation to Llama-3.1-8B and Granite-3.3-8B, bringing the total number of evaluated model backbones to four. HASA retains 97.0–99.4% of dense-attention accuracy on the two additional backbones.

Additional Experimental Analysis

We added further experimental analyses to validate HASA's accuracy, computational efficiency, and practical applicability:

  • Statistical significance: All six accuracy comparisons against UNIQUE favor HASA, with four showing statistically significant improvements at the 95% confidence interval.
  • General capability preservation: Across four mathematical reasoning and code generation benchmarks, HASA achieves an average score only 0.3 points below dense attention under a 25% KV-token budget.
  • Runtime breakdown: Online routing overhead accounts for only 1.07–7.45% of dense-attention latency across the evaluated context lengths.
  • Tensor parallelism: Adaptive and fixed resolutions exhibit only a 0.15% difference in end-to-end decoding latency under the evaluated 8-GPU configuration.
  • Memory overhead: The additional routing state occupies only 0.52% of the original KV-cache size at a 32K context length.

Collectively, these additional results reinforce our original findings and further establish the benefits of joint resolution adaptation in advancing the accuracy–latency Pareto frontier.

We appreciate your consideration of our responses and the revised manuscript and welcome any further questions or discussion.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.