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.32x, while achieving up to 14.07x speedup over dense attention.
Figures & tables
Figure 1: Motivation for HASA. Coarse-grained selection risks missing relevant tokens, while fine-grained selection increases selection overhead. HASA adapts selection granularity for each head.
Figure 2: Overview of HASA. (1) Each head’s pretrained query–key interaction structure determines its effective rank, yielding a compact head-specific response space. (2) In this compact response space, neighboring regions with coherent token responses are progressively merged, while heterogeneous regions remain separate. (3) Relevant regions are selected using compact region summaries, followed by exact attention over their original full-dimensional KV states.
Method
Budget
Overall
En
Zh
Extreme
Hard
Moderate
Easy
Full attention
–
37.70
35.88
38.96
31.13
33.72
31.60
48.86
Quest
2048
30.63
29.17
32.60
24.60
28.60
24.17
42.01
H2O
2048
33.02
31.77
34.42
27.51
31.08
26.56
43.33
InfLLM
2048
36.16
35.06
37.53
29.95
32.90
29.84
47.98
UNIQUE
2048
37.11
35.57
38.15
31.28
33.18
31.03
47.66
HASA (Ours)
2048
37.62
36.90
38.28
32.80
34.10
31.01
47.25
Table 1: Accuracy results on LongBench-Pro using Ministral-3-8B-Instruct-2512. The budget denotes the number of KV tokens available to each query during decoding; full attention is unrestricted.
Method
Budget
SG1
SG2
SG3
MK1
MK2
MK3
MV
MQ
VT
CWE
FWE
QA1
QA2
Avg.
Full attention
–
100.00
99.60
99.60
99.40
100.00
99.80
98.55
99.05
99.96
88.46
93.27
75.80
57.40
93.15
Quest
2048
100.00
98.80
97.00
99.20
99.80
97.60
99.45
99.30
99.88
77.80
90.67
75.00
57.20
91.67
H2O
2048
100.00
99.80
31.00
99.60
97.80
1.80
92.65
65.20
98.40
42.96
90.80
74.40
56.80
73.17
InfLLM
2048
100.00
94.00
85.20
95.20
99.80
96.40
93.00
88.45
94.08
22.10
83.80
74.60
57.20
83.37
UNIQUE
2048
100.00
99.80
99.20
99.60
100.00
99.80
99.00
99.15
99.96
82.28
91.07
75.60
57.40
92.53
HASA (Ours)
2048
100.00
100.00
100.00
100.00
99.00
99.80
98.51
99.15
100.00
83.86
90.43
76.53
57.40
92.67
Table 2: Accuracy results on RULER-32K using Ministral-3-8B-Instruct-2512. The budget denotes the number of KV tokens available to each query during decoding; full attention is unrestricted.
Figure 3: Head-specific resolution and attention recall. (a–b) High recall is achievable by adjusting feature rank and block size, with different heads requiring different resolutions. (c) Adaptive resolution improves normalized attention recall over fixed configurations across RULER-32K tasks. (d–e) HASA selects varying feature ranks and sequence granularities across layers and KV heads, confirming head-specific adaptation.
Figure 4: Self-attention efficiency at increasing context lengths. (a) Our method substantially reduces latency compared with dense attention. (b) Our method achieves higher self-attention speedup than Quest and UNIQUE.
Feature
Sequence
Acc. (%)
Norm. Recall (%)
Fixed
Fixed
91.18
91.60
Adaptive
Fixed
91.42
93.40
Fixed
Adaptive
91.50
94.00
Adaptive
Adaptive
92.21
100.00
Table 3: Ablation of adaptive feature and sequence resolution at 1024 KV budget, RULER-32K.
Appendix figures & tables3 assets
Supplementary material from the paper’s appendix.
Appendix
Method
Budget
Overall
En
Zh
Extreme
Hard
Moderate
Easy
Full attention
–
37.13
35.92
38.34
27.49
35.21
31.44
46.86
Quest
2048
35.02
33.49
36.55
25.62
33.29
29.33
44.51
UNIQUE
2048
36.12
35.03
37.22
27.15
33.49
29.85
45.99
HASA (Ours)
2048
36.64
35.77
37.50
27.62
34.32
30.06
46.53
Quest
1024
34.31
33.14
35.47
24.71
33.24
27.94
43.92
UNIQUE
1024
35.16
34.17
36.15
26.62
32.46
28.41
44.99
Appendix
Table 4: Accuracy results on LongBench-Pro using Qwen3-8B. The KV budget denotes the number of KV tokens available to each query during decoding; full attention is unrestricted.
Method
Budget
SG1
SG2
SG3
MK1
MK2
MK3
MV
MQ
VT
CWE
FWE
QA1
QA2
Avg.
Dense
–
100.00
100.00
100.00
100.00
97.00
95.00
99.75
99.75
99.80
84.10
94.67
75.00
50.00
91.93
Quest
2048
100.00
100.00
100.00
99.00
98.00
78.00
100.00
99.00
98.20
58.60
90.67
75.00
55.00
88.57
UNIQUE
2048
100.00
100.00
100.00
99.00
98.00
79.00
100.00
99.25
98.20
59.50
90.67
75.00
58.00
88.97
HASA (Ours)
2048
100.00
100.00
100.00
100.00
97.00
84.00
99.75
99.75
99.80
71.40
93.67
74.00
56.00
90.41
Quest
1024
100.00
100.00
100.00
100.00
96.00
44.00
99.75
99.25
100.00
61.00
93.67
71.00
53.00
85.97
UNIQUE
1024
100.00
100.00
100.00
99.00
97.00
62.00
98.75
99.75
96.80
48.10
88.67
72.00
56.00
86.01
Appendix
Table 5: Accuracy results on RULER-32K using Qwen3-8B. The KV budget denotes the number of KV tokens available to each query during decoding; full attention is unrestricted.
Hyperparameter
Value
Accuracy (%)
ϵmax
0.05
92.21
0.10
92.21
0.15
91.98
0.20
91.04
ρmin
0.50
90.82
0.60
91.73
Appendix
Table 6: Hyperparameter sensitivity on RULER-32K at a 1024-token KV budget. Each hyperparameter is varied independently while the remaining parameters are fixed to their best-performing values: ϵmax=0.10 , ρmin=0.70 , and Cmax=512 .