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.