Attention in large language models (LLMs) scores every query against every key with a full dot product. We investigate whether this dot product must be computed completely for attention to be effective. We propose Hidden Sparse Attention (HiSA), which keeps the query and key projections intact but only computes a partial dot product, following a static, parameter-free rule set by the token positions: attention becomes sparse in the hidden (feature) dimension, an axis much less explored than token sparsity, rather than over tokens as in almost all sparse attention methods. Based on the structure of rotary position embeddings (RoPE), we decompose keys and queries into parts which can be omitted when computing attention. By training LLMs from scratch with HiSA, we find that this partial dot product does not hurt but improves performance compared with the complete product while computing only about a third of the query-key products. During inference HiSA improves decoding speed and shrinks memory footprint. We also extend HiSA to FlashAttention-3 kernels for training and inference. Finally, we motivate our approach by showing that dense attention learns to suppress the attention score parts that HiSA drops. Code is available at https://github.com/ambroise-b/hisa.
Figures & tables
Figure 1: Dense attention computes every part (left); token-sparse attention drops whole keys (centre). HiSA keeps a part only while its rotation induced by RoPE is below an angle budget Φ : nearby keys are compared on all pairs, farther keys only on the slow ones, so attention becomes sparse in the hidden dimension rather than over tokens (right).
Figure 2: Which score parts HiSA keeps ( Φ=90∘ , d=64 ). Pair l contributes only while its RoPE rotation Δθl is below the angle budget, i.e. up to the distance Δmax,l=Φ/θl (shaded for b=104 ). Fast pairs see a few tokens, slow pairs thousands; raising the RoPE base b stretches every window.
Model
Val. loss
Loss by position
ρ (%)
0–512
512–2K
2K–4K
135M, b=104
Dense
2.906
3.170
2.920
2.830
100.0
HiSA
2.880
3.147
2.893
2.804
29.3
135M, b=2⋅104
Dense
2.908
3.177
2.923
2.829
100.0
HiSA
2.869
3.136
2.883
2.791
34.2
360M, b=104
Dense
2.587
2.823
2.598
2.519
100.0
Table 1: Dense attention vs. HiSA ( Φ=90∘ ) at 4K context: validation loss, loss by position, and percentage ρ of the dot product computed. 135M: 2.7B tokens; 360M: 7.24B tokens. Best in bold.
Figure 3: Exact rule and block rule, for one query (block). Rows: keys, nearest first; columns: RoPE pairs, fast to slow. The exact rule (left) drops pairs key by key. The block rule (right) groups keys into blocks (128 tokens) and pairs into chunks (8 pairs, 16 features); each block keeps the pairs of its nearest key, so a (block, chunk) tile of K is either skipped or multiplied, with the dropped pairs of the boundary chunk zeroed in Q .
Attention
Kernel
Val. loss
Tokens/s
ρ (%)
Dense
SDPA (FlashAtt. 2)
2.906
205k
100.0
Dense
FlashAtt. 3
2.904
236k
100.0
HiSA
Triton (exact rule)
2.880
119k
29.3
HiSA block rule
Triton
2.888
191k
34.8
Flash-HiSA
FlashAtt. 3
2.892
238k
34.8
Table 2: Implementations at 4K context ( b=104 , Φ=90∘ , S=128 , 135 M parameters): validation loss, training throughput on one H200, and percentage ρ of the dot product computed. Best in bold.
PG19 val. loss
OWT
ρ (%)
all
0–4K
4K–8K
8K–16K
val. loss
Dense
3.205
3.262
3.209
3.174
3.111
100.0
HiSA
3.170
3.226
3.174
3.140
3.071
20.2
Table 3: After the 16K extension ( b=2⋅104 ), exact rule: validation loss on PG19 (overall and by position) and OpenWebText, and percentage ρ of the dot product computed. Best in bold.
PG19 val. loss
OWT
ρ (%)
Tok/s
all
0–4K
4K–8K
8K–16K
val. loss
Dense (FA3)
3.212
3.270
3.216
3.181
3.115
100.0
143k
Flash-HiSA
3.190
3.248
3.194
3.159
3.099
21.7
135k
Table 4: After the 16K extension with FlashAttention-3 ( b=2⋅104 ): validation loss, percentage ρ of the dot product computed, and training throughput on one H200. Best in bold.
Batch 32
Batch 128
T
Attention
Tok/s
KV (GiB)
Tok/s
KV (GiB)
4K
Dense (FA3)
7.3k
2.8
20.4k
11.2
Flash-HiSA
7.8k
1.9
23.2k
7.7
16K
Dense (FA3)
4.7k
11.2
9.2k
45.0
Flash-HiSA
5.6k
7.3
13.0k
29.1
Table 5: Decoding with FlashAttention-3 at full context: throughput (tokens/s, one H200) and KV-cache memory, for batch sizes 32 and 128. 4K: b=104 ; 16K: b=2⋅104 , after the extension. Best in bold.
Model
Extra tokens
Val. loss
ρ (%)
Dense (start)
–
2.906
100.0
Dense → HiSA, no training
0
2.937
29.3
Dense, continued
1.35B
2.838
100.0
Dense → HiSA, continued
1.35B
2.836
29.3
Table 6: Converting the dense 135M model ( b=104 , 4K context) to HiSA: validation loss before and after continued training, and percentage ρ of the dot product computed. Best in bold.
Figure 4: Ereal/Enull in three layers of the dense 135M model at initialisation, after 1B tokens and at the end of training (2.7B tokens), and of the pretrained SmolLM-135M. In each panel, rows are frequency pairs (fast at the bottom) and columns distance bands (1 to 2048 tokens, log scale). Red: the true score part moves the head output more than one computed with an unrelated key; blue: less. Black line: Δθl=90∘ (right of it, HiSA drops the score part). All layers in Appendix E .
Figure 5: Share of the (layer, distance band) cells of the fast pairs ( l=0,…,7 ) below the uninformative reference ( Ereal<Enull ), by rotation angle, at initialisation, after 1B tokens and at the end of training of the dense 135M model, and for the pretrained SmolLM-135M (all 30 layers).
Appendix figures & tables19 assets
Supplementary material from the paper’s appendix.
Appendix
b
T= 2K
T= 4K
T= 16K
reach
45∘
90∘
180∘
360∘
45∘
90∘
180∘
360∘
45∘
90∘
180∘
360∘
( 90∘ )
104
29.3
36.9
44.4
51.9
21.8
29.3
36.8
44.4
8.1
14.3
21.8
29.3
11.8K
2⋅104
34.2
41.2
48.2
55.1
27.2
34.2
41.2
48.1
13.2
20.2
27.2
34.2
23.1K
5⋅104
39.6
46.0
52.4
58.8
33.2
39.6
46.0
52.4
20.4
26.8
33.2
39.6
56.0K
5⋅105
50.0
55.2
60.5
65.8
44.6
49.9
55.2
60.5
34.1
39.4
44.6
49.9
521.2K
Appendix
Table 7: Percentage of the dense query–key dot product computed by HiSA, ρ(T) ( Equation 5 ), for angle budgets Φ , RoPE bases b and context lengths T ( d=64 , causal attention), and the reach R at 90∘ ( Equation 4 ).
b
T= 2K
T= 4K
T= 16K
ρ
ρdec
κ
ρ
ρdec
κ
ρ
ρdec
κ
104
36.9
31.5
65.7
29.3
23.9
61.9
14.3
9.0
40.4
2⋅104
41.2
36.1
68.1
34.2
29.1
64.5
20.2
15.1
57.6
5⋅104
46.0
41.4
70.7
39.6
35.0
67.5
26.8
22.1
61.1
5⋅105
55.2
51.4
75.7
49.9
46.1
73.1
39.4
35.5
67.8
Appendix
Table 8: Percentage of the dense query–key product computed in a full causal pass, ρ(T) , and in one decoding step at context T , ρdec(T) , and KV-cache size relative to a dense cache, κ(T) (per pair), at Φ=90∘ ( d=64 ).
Model
Params
Layers
Width
MLP
Heads (q / kv)
d
Tokens
135M
134.5M
30
576
1536
9 / 3
64
2.7B
360M
361.8M
32
960
2560
15 / 5
64
7.24B
Appendix
Table 9: Model architectures and training budgets (about 20 tokens per parameter).
Table 11: Learning-rate selection on the dense model: validation loss after the given number of tokens, with the same number of warmup steps as the full run. For the 16K extension, the mean of the PG19 and OpenWebText validation losses.
Φ
Val. loss
ρ (%)
Reach
45∘
3.022
29.3
5.9K
90∘
3.020
36.9
11.8K
180∘
3.010
44.4
23.6K
360∘
3.039
51.9
47.1K
∞ (dense)
3.055
100.0
–
Appendix
Table 12: Angle budget Φ at 2K context ( b=104 , 135M): validation loss, percentage ρ of the dot product computed, and reach. Best in bold.
T
b
Dense
HiSA
Reach
2K
104
3.055
3.020
11.8K
2K
5⋅105 †
3.019
3.010
11.8K
4K
104
2.906
2.880
11.8K
4K
2⋅104
2.908
2.869
23.1K
Appendix
Table 13: RoPE base b ( Φ=90∘ , 135M): validation loss of dense attention and HiSA at the same base, and reach. † Rotation base 5⋅105 , HiSA windows computed with base 104 . Best in bold.
Figure 6: The FlashAttention implementation of HiSA (block rule, S=128 , Φ=90∘ , b=104 ). (a) Number of 16-feature chunks computed for each 128×128 tile of the causal score matrix (2K context): near the diagonal all four, far from it only the slowest chunk. (b) One tile of the training kernel: the matrix multiply runs only over the kept chunks, and the dropped pairs of the boundary chunk are zeroed in the query tile. (c) The decoding cache at 4K context: each key chunk has its own ring buffer, as long as the window of its slowest pair; the values are kept within the reach.
Figure 7: Relative influence Il,B of each pair (rows of a panel) at each distance band (columns) in three layers of the dense 135M model during training and of SmolLM-135M, each pair divided by its maximum over the distance bands. Black line: Δθl=90∘ .
Figure 8: Ereal/Enull per layer, pair and distance band, dense 135M model (4K, b=104 ) at initialisation. Black line: Δθl=90∘ .
Figure 9: Ereal/Enull per layer, pair and distance band, dense 135M model (4K, b=104 ) at step 2000. Black line: Δθl=90∘ .
Figure 10: Ereal/Enull per layer, pair and distance band, dense 135M model (4K, b=104 ) at step 4000. Black line: Δθl=90∘ .
Figure 11: Ereal/Enull per layer, pair and distance band, dense 135M model (4K, b=104 ) at the end of training (step 5149). Black line: Δθl=90∘ .
Figure 12: Ereal/Enull per layer, pair and distance band, pretrained SmolLM-135M. Black line: Δθl=90∘ .
Figure 13: Relative influence Il,B ( Equation 20 ) per layer, pair and distance band, dense 135M model (4K, b=104 ) at initialisation; each pair divided by its maximum over the distance bands. Black line: Δθl=90∘ .
Figure 14: Relative influence Il,B ( Equation 20 ) per layer, pair and distance band, dense 135M model (4K, b=104 ) at step 2000; each pair divided by its maximum over the distance bands. Black line: Δθl=90∘ .
Figure 15: Relative influence Il,B ( Equation 20 ) per layer, pair and distance band, dense 135M model (4K, b=104 ) at step 4000; each pair divided by its maximum over the distance bands. Black line: Δθl=90∘ .
Figure 16: Relative influence Il,B ( Equation 20 ) per layer, pair and distance band, dense 135M model (4K, b=104 ) at the end of training (step 5149); each pair divided by its maximum over the distance bands. Black line: Δθl=90∘ .
Figure 17: Relative influence Il,B ( Equation 20 ) per layer, pair and distance band, pretrained SmolLM-135M; each pair divided by its maximum over the distance bands. Black line: Δθl=90∘ .
At each decoding step a language model attends over the key-value (KV) cache of every earlier token, so at long context the attention call is bounded by memory bandwidth. Sparse attention reads only a subset of keys chosen by a cheap score estimate, and most methods give the unread tokens zero weight. The output then draws on only a small fraction of the KV cache, and accuracy drops at small budgets, most on tasks that aggregate information across the context. An inverted-file product-quantization (IVF-PQ) index over the cached keys computes an approximate score for every indexed token in order to rank them; after ranking, those scores approximate the attention logits of the tokens left out. PQ-HSA (hybrid sparse-approximate attention) attends the selected tokens with their original keys and values, and the unselected tokens, the background, enter the same softmax through those scores, summed per inverted list and multiplied by the list's mean value. At 128K and a 1-2% retrieval budget, PQ-HSA is more accurate than Quest and SnapKV on Llama-3.1-8B and Qwen3-30B-A3B and stays close to full attention in macro accuracy; with the same selector, the background term raises macro accuracy on the 8B model from 0.71 to 0.83. In the same 128K setting, inside vLLM on one NVIDIA H20, the decode attention call runs 1.6x faster than the FlashAttention-3 kernel; the speedup grows with context length, and a cost model fitted on 8B to 30B models gives the context length at which it begins. A vLLM plugin runs PQ-HSA on two engine versions without changes to the engine source; code is available at https://github.com/KunmingSHAO/pqhsa_release.
Kunming Shao, Jierun Chen, Yanli Wang +4
The Hong Kong University of Science and Technology · Huawei Technologies Ltd. · Sun Yat-sen University +1
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.
Autoregressive generation in Large Language Models (LLMs) is constrained by the memory and computational demands of attention mechanisms. Sparse attention methods mitigate this cost by selecting only high-probability entries of the attention matrix. We observe that in many such methods, this renders the probability-value multiplication negligible, shifting the bottleneck to the query-key step. Key heads can therefore be reduced to accelerate inference, while retaining more value heads preserves capacity with limited additional decoding cost. We introduce Sparse Asymmetric Group-Query Attention (SAGA), which decouples key and value head counts to exploit this principle, and pair it with approximate top-N (Atop-N) attention, a simple sparse attention method designed to study the interaction between sparsity and head-count asymmetry. We formalize the benefits of this asymmetry theoretically and validate them empirically through latency measurements and quality evaluations on models up to 1.5B parameters. Together, SAGA and Atop-N achieve end-to-end decoding speedups exceeding 2× over our full-attention GQA baseline at long contexts. Models trained from scratch with SAGA nearly match the quality of comparable GQA variants on the evaluated benchmarks. To facilitate adoption, we introduce an efficient fine-tuning method that converts pretrained models to the SAGA architecture, enabling practitioners to benefit from our approach without costly retraining.
Noam Elata, Itay Lamprecht, Mikey Shechter +3
Technion – Haifa, Israel · Intel, Israel · Corma +1