Large language models (LLMs) increasingly need to process long documents and codebases, making long-context attention a major prefill bottleneck. Block sparse attention reduces computation by skipping unimportant blocks of the attention matrix, but scoring blocks accurately can itself be expensive. We propose Delta-Based Tile Scoring (DTS), a training-free, content-adaptive tile scoring method for sparse block attention. DTS selects query and key anchors according to local vector changes, using fewer representatives in redundant regions while retaining more detail in heterogeneous regions. To accelerate anchor selection, parallel delta packing partitions the query and key sequences into tile-aligned chunks and performs bounded local scans over these chunks concurrently. The selected tiles are then computed using the original query, key, and value vectors. On LLaMA-3.1-8B-Instruct, DTS keeps average RULER and LongBench scores within 0.10 percentage points of full attention, with RULER evaluated up to 128K tokens. At 128K tokens, DTS reduces measured scoring-pipeline latency by 38% compared with XAttention. On four NVIDIA H100 GPUs, it achieves a 3.3× prefill speedup over a PyTorch full-attention baseline using FlashAttention-2 at 512K tokens.
Figures & tables
Fig. 1 : Comparison of XAttention [ 8 ] and DTS. (a) XAttention samples strided antidiagonals at a fixed density. (b) DTS selects query and key anchors based on local vector changes, reducing redundant scoring in similar regions.
Fig. 2 : Mean cosine similarity of neighboring query ( Q ) and key ( K ) vectors in natural and shuffled order across context lengths. Results average all layers and heads over 50 PG-19 books and 50 WikiText-103 windows per model.
Fig. 3 : DTS workflow. Parallel delta packing selects query and key anchors. Their causal scores are summed by original tile indices to guide tile selection. Sparse attention uses the original Q,K,V .
Method
4K
8K
16K
32K
64K
128K
Avg
LLaMA-3.1 8B Instruct
Full attention
96.16
93.77
93.43
90.47
86.14
74.46
89.07
MInference
96.04
93.95
92.60
88.43
84.66
63.73
86.57
FlexPrefill
95.37
92.29
91.23
88.02
83.56
74.23
87.45
XAttn s=16
96.17
93.97
93.43
90.56
83.04
70.96
88.02
XAttn s=8
95.57
93.92
92.71
90.60
81.83
71.57
87.70
TABLE I : RULER accuracy (%) comparing delta-based tile scoring against baseline and block-sparse methods on LLaMA-3.1 8B Instruct and Qwen2.5-7B-Instruct-1M. Best and second-best scores are shown in bold and underlined .
Method
NQA
Qas
MFQ
HotP
2Wiki
Mus
GovR
QMS
MNews
TREC
TQA
SAM
PCnt
PassR
LCC
RepoB
Avg
LLaMA-3.1 8B Instruct
Full attention
31.91
43.06
56.25
54.87
47.97
34.88
34.47
25.27
27.15
67.00
89.47
44.56
7.58
99.00
51.94
45.12
47.53
MInference
31.74
42.25
56.50
54.70
50.17
31.80
34.51
25.27
27.13
67.00
89.69
44.09
5.00
94.00
52.14
47.32
47.08
FlexPrefill
26.02
39.00
55.19
55.11
38.53
28.73
33.44
25.53
26.93
67.00
89.29
44.58
2.00
83.00
54.02
48.07
44.78
XAttn s=16
31.01
37.56
56.65
53.35
48.37
32.71
34.83
24.37
26.46
67.00
89.80
45.42
5.33
92.00
53.94
44.74
46.47
XAttn s=8
29.84
41.08
54.43
53.23
47.59
31.01
34.49
26.37
26.46
67.00
89.77
44.53
4.00
93.00
52.67
48.61
46.50
TABLE II: LongBench scores on LLaMA-3.1 8B Instruct and Qwen2.5-7B-Instruct-1M. NQA = NarrativeQA, Qas = Qasper, MFQ = MultifieldQA-en, HotP = HotpotQA, 2Wiki = 2WikiMultiHopQA, Mus = MuSiQue, GovR = GovReport, QMS = QMSum, MNews = MultiNews, TREC = TREC, TQA = TriviaQA, SAM = SAMSum, PCnt = PassageCount, PassR = PassageRetrieval-en, LCC = LCC, and RepoB = RepoBench-P. Best and second-best scores are shown in bold and underlined .
Fig. 4 : Prefill efficiency and accuracy. (a)–(b) Prefill speedup relative to full attention across context lengths, measured using WikiText-103. (c)–(d) RULER accuracy versus prefill latency at 128K, measured on RULER, for LLaMA and Qwen, 100% corresponds to 17.33 s and 13.82 s, respectively.
Density (%)
Est. score (%)
Scoring pipeline (ms)
Context
XAttn
DTS
XAttn
DTS
XAttn
DTS
4K
66.1
55.5
6.25
4.41
19
45
16K
36.4
31.3
6.25
3.05
37
92
32K
27.6
24.9
6.25
2.77
141
206
64K
20.5
19.9
6.25
2.61
542
541
128K
17.1
17.6
6.25
2.26
2,571
1,592
TABLE III : Scoring-pipeline cost comparison between XAttention ( s=16 ) and DTS ( τ=0.72 ) on LLaMA-3.1-8B-Instruct. The scoring pipeline includes all stages required to construct the sparse tile mask and excludes block-sparse attention. Times are summed over all 32 layers.
τ
Speedup
Density
Est. score ratio (%)
Phase time (ms)
RULER
LongBench
Scoring
Attention
Full
1.00 ×
100%
–
–
–
91.52
39.54
0.70
2.08 ×
19.0%
1.6%
1,447
3,094
91.69
38.95
0.72
2.10 ×
17.6%
2.3%
1,592
2,853
91.51
39.21
0.75
2.09 ×
15.7%
3.8%
1,954
2,545
91.42
39.08
0.78
2.04 ×
14.2%
6.3%
2,445
2,284
91.80
39.15
TABLE IV : Cosine-threshold sweep on LLaMA-3.1-8B-Instruct. Latency results are measured at 128K.
Packing only
DTS attention pipeline
Context
Seq. (ms)
Par. (ms)
Speedup
Seq. (ms)
Par. (ms)
Speedup
8K
451.7
24.4
18.53×
540.5
110.4
4.90×
32K
1,782.4
76.4
23.34×
2,205.5
482.1
4.57×
64K
3,555.5
144.2
24.65×
4,700.3
1,271.1
3.70×
128K
7,128.5
295.8
24.10×
10,931.6
4,094.0
2.67×
TABLE V : Effect of parallel delta packing on LLaMA-3.1-8B-Instruct at τ=0.72 . Packing only measures delta packing, whereas the DTS attention pipeline includes delta packing, tile scoring, tile selection, and block-sparse attention. The sequential and parallel implementations differ only in the chunk-scan schedule. All times cover the 32 attention layers. Timings are profiled independently of Table IV .
Modern large language models increasingly require long contexts for reasoning and multi-document tasks, but attention's quadratic complexity creates a severe computational bottleneck. We present Block Sparse Flash Attention (BSFA), a drop-in replacement that accelerates long-context inference while preserving model quality. Unlike methods that predict importance before computing scores, BSFA computes exact query-key similarities to select the top-k most important value blocks for each query. By comparing per-block maximum scores against calibrated thresholds, we skip approximately 50% of the computation and memory transfers for pruned blocks. Our training-free approach requires only a one-time threshold calibration on a small dataset to learn the per-layer and per-head attention score distributions. We provide a CUDA kernel implementation that can be used as a drop-in replacement for FlashAttention. On Llama-3.1-8B, BSFA achieves up to 1.13x end-to-end speedup on LongBench with only a 1.1% accuracy drop, and up to 1.24x on Needle-in-a-Haystack retrieval at a 1% accuracy drop. The attention kernel itself accelerates by up to 1.38x. We compare BSFA against five recent sparse attention baselines (SpargeAttention, MInference, FlexPrefill, XAttention, and BLASST), and verify the method on Qwen2.5-7B and on A6000 and H100 GPUs. The implementation is available at https://github.com/Danielohayon/Block-Sparse-Flash-Attention.
Daniel Ohayon, Itay Lamprecht, Itay Hubara +3
Technion – Israel Institute of Technology, Haifa, Israel · Intel - Habana Labs · Intel – Habana Labs, Tel Aviv, Israel
We introduce a training-free sparse attention method that builds a prompt-specific key index to accelerate both prefill and decoding. The method clusters the keys into large semantic blocks that group tokens from noncontiguous positions. Each query position selects blocks by scoring their centroids and attends to the original keys and values within them. Queries that select the same block are processed together, so prefill stays fast even though each query chooses its own blocks. Large blocks make centroid scoring and this grouped processing cheap, so each query can attend to more tokens in the same time. Larger blocks with a larger token budget can thus be both faster and more accurate on long-context tasks than smaller blocks with a smaller budget. We evaluate two hybrid LLMs, Qwen3.5-4B and 35B-A3B, on one NVIDIA H200. Including the cost of building and using the index, whole-model wall-clock speedups over dense attention are 2.3-2.4x for prefill and 1.7-2.0x for decoding at 512K tokens, and 2.9-3.0x for prefill at 1M. The 35B-A3B model stays close to dense attention on five RULER tasks through 1M, on LongBench-v2 overall, and on MRCR through 256K. The 4B model loses accuracy mainly on multi-key retrieval, yet outperforms dense Qwen3.5-2B, whose latency is similar at 512K, on all three benchmarks.
Current hierarchical attention methods, such as NSA and InfLLMv2, select the top-k relevant key-value (KV) blocks based on coarse attention scores and subsequently apply fine-grained softmax attention on the selected tokens. However, the top-k operation assumes the number of relevant tokens for any query is fixed and it precludes the gradient flow between the sparse and dense stages. In this work, we propose DashAttention (Differentiable and Adaptive Sparse Hierarchical Attention), which leverages the adaptively sparse α-entmax transformation to select a variable number of blocks according to the current query in the first stage. This in turn provides a prior for the second-stage softmax attention, keeping the entire hierarchy fully differentiable. Contrary to other hierarchical attention methods, we show that DashAttention is non-dispersive, translating to better long-context modeling ability. Experiments with large language models (LLMs) show that DashAttention achieves comparable accuracy as full attention with 75% sparsity and a better Pareto frontier than NSA and InfLLMv2, especially in high-sparsity regimes. We also provide an efficient, GPU-aware implementation of DashAttention in Triton, which achieves a speedup of up to over FlashAttention-3 at inference time. Overall, DashAttention offers a cost-effective strategy to model long contexts.
Yuxiang Huang, Nuno M. T. Gonçalves, Federico Alvetreti +5
1Tsinghua University · 2Instituto Superior Técnico, Universidade de Lisboa. · 3Instituto de Telecomunicações. +6