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 .
Long-context LLM inference is bottlenecked by quadratic attention computation and growing KV-cache costs. Existing sparse attention and KV-compression methods typically decide which tokens or heads to preserve from runtime attention scores, observation windows, calibration prompts, or learned gates, making head diagnosis input-dependent and costly to deploy. We propose Autonomy-of-Heads (AoH), a data-free method that identifies retrieval and streaming heads from the spectral geometry of query-key projections. AoH defines the kernel attention operator Mh=WKh⊤WQh and uses its effective-rank as a weight-space measure of head function: concentrated spectra indicate a small number of dominant query-key matching directions and are associated with retrieval heads, whereas diffuse spectra indicate the absence of a dominant global matching direction and are associated with streaming heads. We further derive an efficient dhead-dimensional computation that avoids constructing the full dmodel×dmodel matrix. We conducted extensive experiments across models demonstrating that at 50% sparsity, AoH retains 96.5% of Full Attention performance on average while reducing prefill and decode latency by up to 41.4% and 66.0%, respectively, and KV-cache memory by 50.0% at 256K tokens.
Yehan Yang, Junyuan Shang, Yang Li +3
Institute of Computing Technology, Chinese Academy of Sciences · University of Chinese Academy of Sciences · Baidu Inc. +1
As large language models (LLMs) process increasingly long sequences, attention becomes a major computational bottleneck. Sparse attention mostly targets inference, yet many methods still train densely or cannot support sparse training, and their added complexity makes sparsity hard to turn into wall-clock speedups, leaving dense attention widely used in practice. This paper introduces LazyFlash, a forward-dense, backward-sparse attention method built on the observation that attention training is dominated by the backward pass. LazyFlash keeps the forward pass exactly dense, so the trained model remains a standard dense model that existing systems such as vLLM can serve without any change. For the backward pass, LazyFlash proposes a gradient-aware block sparsification design that ranks query blocks by their attention-output gradient norms and skips those contributing negligibly to parameter updates, turning the dense backward into a block-sparse one. A gradient-mass budget adapts the amount of skipped computation to each head and training step, while importance sampling preserves the dense gradient in expectation. These designs are implemented inside the tiled FlashAttention backward kernel, where skipped blocks are never loaded or computed, translating gradient sparsity into real wall-clock acceleration. Experiments on long-context text and speech LLMs show that LazyFlash maintains downstream performance while achieving up to 5.7x attention-backward speedup over FlashAttention and 1.7x end-to-end training speedup.
Large Language Models (LLMs) achieve strong performance across many domains, but their efficiency is limited by the quadratic cost of attention with respect to prompt length. Sparse attention reduces this cost by retaining only a small fraction of query-key interactions to approximate the full attention matrix. However, existing methods are trapped in a mathematically wrong view: they simply keep large scalar entries or high-mass regions of the attention matrix. This treats the attention matrix as a bag of values, ignoring that it is used as a structured matrix whose entries jointly determine the attention output through multiplication with value vectors. We argue that this is the core conceptual issue: sparse attention should be formulated as matrix approximation, not as blindly choosing the largest values from a bag of entries. Based on this view, we propose Matrix Approximation Sparse Attention (MASA). MASA replaces raw attention-mass ranking with a closed-form score that measures how much each sparse unit reduces matrix-product approximation error. As a theory-grounded plug-in correction, MASA can be added to existing sparse attention frameworks without changing their sparse kernels or budgets. Extensive experiments across multiple sparse attention methods, benchmarks, and LLM backbones show consistent accuracy gains, supporting both MASA and the matrix-approximation view of sparse attention.