Step-dLLM: Adaptive Step-aware Sparse Attention for Efficient Diffusion LLM Inference
Authors: Zhichen Zeng, Xichong Zhang, Junpan Wu, Yifei Zuo, Chi-Chih Chang, Jiayi Wang, Maohua Nie, Ji Liu, Ang Li, Banghua Zhu
Organizations: University of Washington · University of Waterloo · University of Wisconsin, Madison · Northwestern University · Cornell University · Meta AI
Diffusion large language models (dLLMs) generate tokens in parallel via iterative denoising, but their bidirectional attention prevents the KV caching used by autoregressive models and recomputes the full attention map at every step, incurring quadratic per-step cost. Existing sparse attention methods for dLLMs construct a sparse mask after an initial full-attention warm-up and reuse it for the remaining steps, while allocating the sparsity budget uniformly across heads. We argue both choices ignore key structural properties of attention in dLLMs: empirically, attention patterns are only locally consistent across steps and shift abruptly at certain transitions, and different heads concentrate their attention mass to very different extents. To this end, we design Step-dLLM, which periodically refreshes a block-sparse mask at anchor steps along the denoising trajectory and reuses it within each locally consistent interval, while employing a head-adaptive global budget that more aggressively compresses heads with concentrated attention. Backed by a fused IO-aware Triton kernel for block-sparse attention, Step-dLLM applies to pre-trained LLaDA-1.5 and Dream-7B-Instruct without retraining, achieving a 2.78x end-to-end speedup over dense FlashAttention on LLaDA-1.5 at 8K context with 256 denoising steps and 90% sparsity, while improving the accuracy-latency trade-off over prior sparse-attention methods.
Figures & tables
Figure 1: Attention pattern dynamics across denoising steps.
Figure 2: Attention pattern across different steps.
Figure 3: Head-wise heterogeneity in sparse attention.
Figure 4: Overview of Step-dLLM . At an anchor step, the fused attention pass produces the dense output and block-level saliency (Stage 1). For each query block, saliency entries compete across all heads and key blocks for a shared top- K budget; a minimum allocation yields head-specific sparse masks (Stage 2). The next Δ−1 steps reuse only these masks, recomputing Q,K,V and the attention weights from the current hidden states (Stage 3). A single query block per head is illustrated.
LLaDA-1.5
Dream-7B-Instruct
Sparsity
Method
GSM8K
Math
HEval
NIAH
RULER
GSM8K
Math
HEval
NIAH
RULER
Dense
81.04
37.20
40.24
100.00
76.78
77.41
45.60
59.12
95.06
81.33
50%
StreamingLLM
74.07
38.20
39.02
18.75
48.77
38.13
8.80
42.70
10.16
41.77
SparseD
80.59
37.40
42.68
100.00
74.86
70.50
43.60
56.10
94.78
80.44
Step-dLLM
81.65
40.00
42.68
100.00
75.05
71.80
44.00
58.54
94.81
79.75
80%
StreamingLLM
19.11
13.60
19.51
2.50
25.75
19.56
10.40
25.00
1.84
9.60
Table 1: Main results on LLaDA-1.5 and Dream-7B-Instruct (accuracy in %). NIAH and RULER columns are averaged across their sub-tasks; per-sub-task scores are in Appendix A . Within each sparsity block, bold marks the highest score per (backbone, metric). Step-dLLM rows are highlighted.
Figure 5: Kernel-level wall-clock speedup of the fused block-sparse attention kernel over the dense Flash Attention baseline.
Figure 6: End-to-end speedup of LLaDA-1.5-8B over dense FlashAttention at 8K context.
Interval
Method
Sparsity 50%
Sparsity 80%
Sparsity 90%
Sparsity 95%
G8K
MATH
VT
G8K
MATH
VT
G8K
MATH
VT
G8K
MATH
VT
f=1.0
SparseD
80.59
37.40
99.88
53.68
29.20
94.32
29.64
23.00
93.64
9.48
12.00
86.16
Step-dLLM
77.48
40.20
100.00
57.77
31.00
98.52
35.18
21.20
94.00
16.83
15.40
92.32
f=0.5
SparseD
81.50
40.60
100.00
64.37
31.20
95.12
29.72
22.20
97.04
6.29
13.80
95.40
Step-dLLM
81.27
40.60
100.00
68.23
32.00
96.64
40.64
22.60
96.56
16.98
16.00
95.36
f=0.3
SparseD
82.03
40.80
100.00
73.09
32.40
95.23
34.19
23.20
97.96
5.53
14.20
97.04
Table 2: Ablation on mask refresh interval. f=Δ/S ; lower f means more frequent refresh. For f<1 , SparseD denotes its refresh-augmented, uniform-budget variant. Accuracy in % on LLaDA-1.5, including 50% sparsity. G8K, VT denote GSM8K and RULER-VT; bold marks the better method within each configuration (ties included).
Block
Method
Sparsity 50%
Sparsity 80%
Sparsity 90%
Sparsity 95%
G8K
MATH
HE
G8K
MATH
HE
G8K
MATH
HE
G8K
MATH
HE
b=16
SparseD
80.59
37.40
42.68
53.68
29.20
36.59
29.64
20.00
30.49
9.86
9.40
20.12
Step-dLLM
81.65
40.00
42.68
77.56
36.40
38.41
61.79
26.20
34.76
18.80
16.60
23.17
b=32
SparseD
81.73
34.80
38.41
50.87
31.60
37.80
17.51
21.60
28.66
8.64
10.60
12.80
Step-dLLM
81.58
41.00
37.80
63.23
31.20
39.12
39.50
26.00
34.15
19.18
16.20
23.78
Table 3: Ablation on attention block size b . Accuracy in % on LLaDA-1.5, including 50% sparsity. G8K, HE denote GSM8K and HumanEval; bold marks the better method within each configuration (ties included).
Appendix figures & tables8 assets
Supplementary material from the paper’s appendix.
Appendix
Sparsity
Method
S_1
S_2
S_3
MK_1
MK_2
MK_3
MQ
MV
Dense
100.00
100.00
100.00
100.00
100.00
100.00
100.00
100.00
50%
StreamingLLM
20.80
20.20
18.40
21.20
20.40
15.40
19.20
14.40
SparseD
100.00
100.00
100.00
100.00
100.00
100.00
100.00
100.00
Step-dLLM
100.00
100.00
100.00
100.00
100.00
100.00
100.00
100.00
80%
StreamingLLM
5.00
2.40
1.40
3.40
3.60
0.00
2.10
2.10
SparseD
100.00
100.00
71.20
100.00
100.00
74.20
85.85
79.10
Appendix
Table 4: Per-sub-task NIAH results on LLaDA-1.5 (accuracy in %). The eight sub-tasks are single-needle (S_1, S_2, S_3), multi-key (MK_1, MK_2, MK_3), multi-query (MQ), and multi-value (MV). Within each sparsity block, bold marks the highest score per sub-task. Step-dLLM rows are highlighted.
Sparsity
Method
VT
CWE
FWE
QS
QH
Dense
100.00
52.40
64.20
91.30
76.00
50%
StreamingLLM
30.60
13.40
73.80
81.65
44.40
SparseD
99.88
52.26
61.40
83.17
77.60
Step-dLLM
99.60
53.16
60.87
83.03
78.60
80%
StreamingLLM
6.56
3.02
76.27
20.48
22.40
SparseD
94.28
57.80
45.40
83.48
77.80
Appendix
Table 5: Per-sub-task RULER results on LLaDA-1.5 (accuracy in %). The five sub-tasks are variable tracking (VT), common-word extraction (CWE), frequent-word extraction (FWE), single QA (QS), and hard QA (QH). Within each sparsity block, bold marks the highest score per sub-task. Step-dLLM rows are highlighted.
Sparsity
Method
S_1
S_2
S_3
MK_1
MK_2
MK_3
MQ
MV
Dense
100.00
100.00
91.00
98.00
99.80
77.60
97.70
96.40
50%
StreamingLLM
10.00
11.00
9.00
11.00
8.80
12.40
8.75
10.30
SparseD
100.00
100.00
90.20
98.00
99.40
75.80
97.45
97.40
Step-dLLM
100.00
100.00
90.50
97.80
99.80
75.60
97.25
97.50
80%
StreamingLLM
1.80
2.80
1.40
3.20
1.20
0.00
1.95
2.40
SparseD
100.00
99.80
47.20
98.80
99.80
46.80
60.05
69.30
Appendix
Table 6: Per-sub-task NIAH results on Dream-7B-Instruct (accuracy in %). Within each sparsity block, bold marks the highest score per sub-task. Step-dLLM rows are highlighted.
Sparsity
Method
VT
CWE
FWE
QS
QH
Dense
96.32
87.28
79.47
79.57
64.00
50%
StreamingLLM
13.40
43.34
37.73
81.40
33.00
SparseD
96.28
85.16
75.80
80.37
64.60
Step-dLLM
96.40
83.24
75.53
79.80
63.80
80%
StreamingLLM
0.36
4.54
4.33
19.18
19.60
SparseD
95.44
71.76
71.77
79.50
61.00
Appendix
Table 7: Per-sub-task RULER results on Dream-7B-Instruct (accuracy in %). Within each sparsity block, bold marks the highest score per sub-task. Step-dLLM rows are highlighted.
Step-dLLM
SparseD
Sparsity
Accuracy
ms/step
Accuracy
ms/step
50%
81.65
51.23
80.59
59.94
60%
82.34
50.21
74.68
59.53
70%
80.74
48.50
63.15
59.15
75%
78.92
48.19
62.02
58.53
80%
77.56
47.36
53.68
58.06
Appendix
Table 8: Joint accuracy–latency sweep on GSM8K (LLaDA-1.5, approximately 1K sequence length). Accuracy is in percent; lower ms/step is better. Dense FlashAttention reaches 81.04% at 50.39 ms/step.
Configuration
Accuracy (%)
Avg. mask refreshes
Periodic f=0.2
77.56
5
Adaptive key drift τ=0.02
82.03
24
Adaptive key drift τ=0.001
78.62
104.3
Appendix
Table 9: Periodic versus key-drift-triggered anchors on GSM8K ( S=256 , ρ=80% ). Refresh count is an overhead indicator, not a measured latency ratio.
Sparsity
50%
60%
70%
80%
90%
95%
Max − average
−2.43
−0.46
+0.76
+1.06
+0.83
+3.64
Appendix
Table 10: Reported accuracy difference between max and average pooling, in percentage points. Positive favors max pooling. These are differences, not absolute accuracy values.
Sparsity
Recompute ( f=0.2 )
With dual cache
Relative tokens/step
0%
81.04
81.43
3.80×
50%
81.65
80.06
3.51×
80%
73.01
70.74
2.71×
Appendix
Table 11: GSM8K accuracy (%) and decoding progress with dual caching. Relative tokens/step is the reported multiple of single-token progress, not wall-clock speedup. The 0% row uses the dense backbone.
Block-wise diffusion language models (DLMs) generate multiple tokens in any order, offering a promising alternative to the autoregressive decoding pipeline. However, they still remain bottlenecked by memory-bound attention in long-context scenarios. Naive sparse attention fails on DLMs due to a KV Inflation problem, where different queries select different prefix positions, making the union of accessed KV pages large. To address this, we observe that between consecutive denoising steps, only a small fraction of active tokens exhibit significant hidden-state changes, while the majority of stable tokens remain nearly constant. Based on this insight, we propose LOSA (Locality-aware Sparse Attention), which reuses cached prefix-attention results for stable tokens and applies sparse attention only to active tokens. This substantially shrinks the number of KV indices that must be loaded, yielding both higher speedup and higher accuracy. Across multiple block-wise DLMs and benchmarks, LOSA preserves near-dense accuracy while significantly improving efficiency, achieving up to +9 points in average accuracy at aggressive sparsity levels while maintaining 1.54x lower attention density. It also achieves up to 4.14x attention speedup on RTX A6000 GPUs, demonstrating the effectiveness of the proposed method.
Haocheng Xi, Harman Singh, Yuezhou Hu +9
University of California, Berkeley · FuriosaAI · ICSI +2
Inference in diffusion large language models (dLLMs) is computationally expensive, as full self-attention must be repeatedly executed at each step of the denoising process without KV cache. Recent sparse attention methods for dLLMs mitigate this cost via block-sparse computation, which is applied only in later iterations when model performance is less sensitive to coarse-grained sparse approximation, but yields limited improvements in computational efficiency and acceleration. This motivates a finer-grained sparsification strategy that can be applied from earlier iterations and leverages reusable sparsity patterns, enabling further efficiency gains. In this work, we introduce PulseCol, a periodically refreshed column-sparse attention method for accelerating diffusion language models. PulseCol replaces coarse block-level sparsity with a finer-grained column-sparse structure, allowing important attention interactions to be retained more precisely while exposing greater sparsity. Built on this column-level formulation, PulseCol further identifies sparse patterns at the early denoising step and reuses them across subsequent iterations, refreshing them only at a small number of intermediate steps to track the evolution of sparse attention patterns during denoising. Experiments show that PulseCol achieves higher sparsity and greater practical speedup than prior sparse attention methods for dLLMs, while maintaining model quality. Enabled by optimized GPU kernels for column-sparse attention, PulseCol delivers up to 1.95× end-to-end speedup over FlashAttention across several context lengths.
Diffusion language models apply bidirectional attention over the whole context at every denoising step, so a longer context makes each step substantially more expensive. Sparsifying only at inference leaves the pretrained weights unchanged, so the model is never trained under the sparse pattern it runs with. We propose Prefilling-dLLM v2, which continues training a diffusion language model so that it routes with its native mask token. One mask is appended at the end of each chunk, and a learned role offset marks it as a routing slot. On every fourth layer, a query keeps a bidirectional local window and the top-K chunks scored from that mask; the other layers use a bidirectional sliding window. Starting from Dream-v0-Base-7B extended to 16K with YaRN, we compare Prefilling-dLLM v2 with bidirectional NSA, DSA, and SWA under the same layout, key budget, and dense initialization, using the same Fast-dLLM decoder. With the YaRN factor scaled to the evaluation length, Prefilling-dLLM v2 leads the other sparse methods on all three RULER tasks from 16K to 128K. Its mean accuracy at 128K is 7.4 points above NSA, the next sparse model, while DSA and SWA remain near zero. At the same length, decoding is 172x faster than with full dense attention.