Block-wise diffusion language models (DLMs) refine multiple tokens in parallel, offering an alternative to token-by-token autoregressive decoding. Their long-context inference, however, remains bottlenecked by memory-bound attention: every denoising step repeatedly reads a growing historical key--value (KV) cache. Directly applying sparse attention does not fully solve this problem, because different queries can select different pages, inflating the block's collective read set, while repeated support construction adds overhead and permanent eviction can discard information needed later. We present RISA, a recoverable sparse-attention method with shared read plans for block-wise DLMs. RISA exploits the fact that historical KV remains fixed within a block while queries evolve across denoising steps. Newly generated history is organized into exact priority and recovery tiers; seed queries then build a protected, bounded read plan whose indices are reused across the block while attention is recomputed with fresh queries and current-block KV. This separates history preservation from repeated reading and amortizes sparse-support construction without changing the backbone or decoder. On DreamReasoner-8B, RISA retains comparable task performance. At 32K, the default configuration speeds up attention by 2.67× and fixed-trajectory requests by 1.36× over dense, and attention speedup reaches 5.53× at 128K. Across eight settings on three models, RISA decodes faster than the tested MAGE, QUEST, and LoSA budgets at matched KL.
Figures & tables
Figure 1: Dense rereads history; RISA reuses one bounded read plan. (a) Dense attention revisits the historical prefix at every denoising step. (b) Per-step top- k reduces each attention support but repeats scoring and selection. (c) RISA uses the seed forward to observe available history, admits aging KV, constructs one protected read plan, and reuses its historical indices for later steps while queries continue to evolve; finalization still reads the full legal prefix.
Figure 2: Low-priority history can remain useful. (a) Full-domain attention continues to revisit tokens after they have been demoted from the priority tier. (b) At a comparable read budget, retrieving from the recovery tier yields lower attention-output error than spending the same budget only on additional priority pages. Error bars in (a) resample requests.
Figure 3: Read sparsity and index reuse remove different work. (a) Attention mass changes across denoising, while a block-static execution can keep the same historical support. (b) Sparse execution reduces requested KV rows, and reusing the plan avoids repeatedly rebuilding that support. Counts include seed and mandatory work and should not be interpreted as direct HBM-traffic measurements.
Figure 4: Storage priority, read-plan composition, and execution. (a) Grace-window observations determine whether generated KV enters compact Hot or addressable Cold storage; both keep exact values. (b) Seed queries score page summaries, then protected HOT, selected HOT, recovered COLD, and mandatory recent rows form one read plan. (c) Later steps reuse the historical plan with new queries and current recent KV, combining all contributions under one softmax.
DreamReasoner-8B
SDAR-8B-Chat
Method
GSM8K
MATH-500
AIME25
LCB
HotpotQA
GSM8K
MATH-500
HotpotQA
Dense
85.0
88.2
58.3
50.0
40.2
88.5
65.4
53.6
QUEST
86.0
88.2
59.4
47.5
38.9
87.5
66.2
52.3
MAGE
85.5
89.0
59.2
42.5
35.2
88.0
66.2
51.4
RISA
86.0
88.8
60.4
50.0
39.9
89.5
66.8
53.4
Table 1: Benchmark accuracy with 32-token blocks (original configuration). Mathematics uses answer accuracy, LCB execution pass@1, and HotpotQA token F1; bold marks the best sparse method.
Figure 5: Quality–speed frontiers. Attention-latency speedup over dense (ms per denoising step on natively decoded 512-token requests, per-block work spread over dense’s steps per block) against KL to dense on dense’s states; lower right is better. Dashed line: dense ( 1× ). The two y regions use separate log scales. Color: method; shape: context; dotted lines: each method’s frontier; ring: RISA’s default; no point is clipped. At LLaDA2.2-mini 16K, MAGE’s 8K and RISA’s ρ=1.0 budgets are slightly slower than dense.
DreamReasoner-8B
SDAR-8B-Chat
LLaDA2.2-mini
Method
16K
32K
64K †
128K †
16K
32K
64K †
128K †
16K
32K
64K
128K
RISA
1.15
1.36
1.76
2.67
1.17
1.40
1.76
2.67
1.07
1.06
1.16
1.25
MAGE 8K
0.99
1.23
1.43
2.03
1.07
1.30
1.47
2.07
0.95
1.03
1.00
1.14
QUEST 8K
0.92
1.08
1.35
2.04
0.91
1.11
1.36
2.02
1.01
1.00
1.10
1.19
LoSA 4K
0.84
1.01
1.18
1.64
0.86
1.03
1.19
1.64
0.89
0.94
0.95
1.09
Table 2: Per-request speedup over dense (decode wall time; dense =1.00× ) for complete 512-token requests, with every method replaying dense’s denoising trajectory on the same documents; RISA’s default, MAGE and QUEST at 8,192 tokens, LoSA at 4,096. † Beyond DreamReasoner’s and SDAR’s configured 32K window (YaRN); execution only.
Figure 6: Efficiency across prefix lengths on both models. (a, c) Attention speedup over dense for DreamReasoner-8B and SDAR-8B-Chat (QUEST and MAGE at 1,024 tokens), from kernel profiles of 512-token requests with per-block work amortized over 15.6 or 10.3 steps per block. (b, d) Per-request speedup over dense, the values of Table 2 : complete 512-token decodes on dense’s fixed trajectory (MAGE and QUEST at 8,192 tokens, LoSA at 4,096). Dotted: dense ( 1× ). Gray: beyond the configured 32K window, execution only.
Figure 7: Attention latency breakdown. Attention-path kernel time per denoising step on an H200 NVL for a 512-token decode on a common prompt per model and prefix. Block work is amortized over dense’s 22.2, 12.3, and 15.2 steps for DreamReasoner, SDAR, and LLaDA2.2-mini. D/Q/M/L/R denote Dense, QUEST, MAGE, LoSA, and RISA. QUEST and MAGE use 8,192 tokens and LoSA uses 4,096. Index includes baseline selection and Top-k is RISA’s selector. Dense is the total. Gray marks execution with YaRN.
DreamReasoner
SDAR
Variant
Attn. (ms/step)
KV reads (%)
KL ( 10−3 )
Attn. (ms/step)
KV reads (%)
KL ( 10−3 )
Recovery and tiering
No COLD recovery
2.54
56
46.7
1.68
48
44.3
COLD reads spent on HOT
2.62
59
45.1
1.75
56
45.1
Flat retrieval
2.92
60
5.21
1.77
54
2.60
COLD quota of 16 pages
2.65
57
14.5
1.71
49
13.9
Table 3: Ablations on DreamReasoner and SDAR. Each variant changes one component of the final configuration. The workload uses a 16K prompt and 4,096 output tokens. Attention latency includes selection and amortized block work, profiled on one document per model (dense: 4.38 and 3.86 ms). KV reads are relative to dense and, with KL to dense, are measured on six documents using dense’s trajectories.
Appendix figures & tables13 assets
Supplementary material from the paper’s appendix.
Appendix
Rule
KL ( ×10−3 )
KV reads (%)
Mass + learned correction
8.60
75.9
Recency admission
10.08
76.2
Random admission
10.30
76.0
Flat retrieval
11.15
76.6
Mass only (RISA)
8.72
76.0
Appendix
Table 4: Admission and retrieval on AIME24. Seven DreamReasoner problems with a 16,384-token output cap. Each variant uses a 128-page COLD quota. KL to dense is measured on dense’s denoising states. Reads are realized historical KV reads relative to dense.
Figure 8: LLaDA2.2-mini at 16K–128K . (a) Attention latency in ms per denoising step for dense (dashed) and each method, measured as in Table 5 on 512-token requests with per-block work spread over dense’s steps per block; RISA’s attention-latency speedup over dense is printed above each length. (b) Per-request speedup over dense (dashed, 1× ) for complete 512-token requests replayed on dense’s denoising trajectory. RISA’s default, MAGE and QUEST at 8,192 tokens, and LoSA at 4,096 tokens.
Dense attn.
Attention-latency speedup
Per-request speedup (fixed trajectory)
Model
Context
(ms/step)
RISA
MAGE 8K
QUEST 8K
LoSA 4K
RISA
MAGE 8K
QUEST 8K
LoSA 4K
Read
DreamReasoner-8B
16K
3.27
1.59
1.10
0.67
0.62
1.15
0.99
0.92
0.84
0.54
32K
5.95
2.67
1.62
1.15
1.02
1.36
1.23
1.08
1.01
0.31
64K †
9.90
3.95
2.30
1.77
1.43
1.76
1.43
1.35
1.18
0.17
128K †
20.31
8.88
3.49
3.52
2.27
2.67
2.03
2.04
1.64
0.10
SDAR-8B-Chat
16K
3.17
1.72
1.38
0.69
0.64
1.17
1.07
0.91
0.86
0.54
Appendix
Table 5: Attention-latency and per-request speedup over dense at the default budgets (RISA’s default, MAGE and QUEST at 8,192 tokens, LoSA at 4,096), for every measured model, context, and method. Attention speedup is dense’s attention latency (ms per denoising step; the Dense attn. column) over the method’s, timed on 512-token requests in which each method decodes natively, with each method’s per-block work (seed step, planning, MAGE’s all-mask scoring, finalization) spread over dense’s steps per block in the same session. Per-request speedup is total dense wall time over total method wall time for complete 512-token requests replayed on dense’s denoising trajectory. Read is RISA’s KV read ratio. Bold marks the fastest method. † Beyond the configured window (YaRN); execution only.
Figure 9: Quality–latency Pareto frontiers for complete requests. Every budget of every method, placed by per-request speedup over dense and KL to dense; lower right is better. Speedup is total dense wall time over total method wall time for complete 512-token decodes replayed on dense’s denoising trajectory, and KL is measured on the same requests; the star at (1,0) is dense. Lines join each method’s Pareto budgets within the panel (no other budget of the same method is both faster and lower in KL), faded markers are budgets beaten by another budget of the same method, and the filled circle is RISA’s default. Points whose KL exceeds a panel’s range are drawn on its top edge at their measured speedup.
DreamReasoner-8B
SDAR-8B-Chat
LLaDA2.2-mini
Method
16K
32K
64K †
128K †
16K
32K
64K †
128K †
16K
32K
64K
128K
RISA
1.20
1.51
2.10
3.05
1.16
1.47
1.87
2.96
0.98
1.12
1.11
1.20
MAGE 8K
0.89
1.26
1.54
2.17
1.04
1.32
1.51
2.20
0.77
1.04
0.94
1.06
QUEST 8K
0.79
1.01
1.39
2.24
0.88
1.08
1.39
2.17
0.86
1.06
1.01
1.03
LoSA 4K
0.72
0.95
1.14
1.62
0.80
0.99
1.20
1.71
0.75
0.78
0.86
1.00
Appendix
Table 6: Per-request speedup under native decoding (decode wall time; dense =1.00× ). Each method, dense included, decodes its own 512-token trajectory on the same documents (DreamReasoner: 30 at 16K and 32K, six at 64K and 128K; SDAR: six; LLaDA2.2-mini: 12); speedup is total dense time over total method time. RISA’s default, MAGE and QUEST at 8,192 tokens, LoSA at 4,096. Bold: fastest sparse method per column. † Beyond DreamReasoner’s and SDAR’s configured 32K window (YaRN); execution only.
Baseline
Matched RISA
Model (dense s)
Budget
s
KL
Read
Budget
s
KL
Read
DreamReasoner-8B (4.09 s)
MAGE 1,024
3.18
43.9
0.14
4,096, ρ =0.5
2.95
28.4
0.19
MAGE 2,048
3.22
26.6
0.17
8,192, ρ =0.5
3.00
14.4
0.31
MAGE 4,096
3.28
14.2
0.23
16,384, ρ =1.0
3.10
5.6
0.55
MAGE 8,192
3.39
6.8
0.34
16,384, ρ =1.0
3.10
5.6
0.55
QUEST 1,024
3.44
326.5
0.09
1,024, ρ =0.5
2.91
79.3
0.10
Appendix
Table 7: Absolute per-request latency at matched fidelity, 32K. Every method follows dense’s fixed denoising trajectory on the same documents. Seconds are decode wall time for 512 tokens, excluding the warm-up document. KL ( ×10−3 ) and the KV read ratio include all paired documents. For each baseline budget, the matched RISA budget is the fastest one whose KL is not higher (HOT cap in tokens, read fraction ρ ). Dense’s seconds per request are given beside each model.
Attention (ms / step)
Request (s)
Block
Context
Dense
RISA
Speedup
Dense
RISA
Speedup
KL ( ×10−3 )
Reads (%)
Cap (%)
32
16K
3.19
1.84
1.73 ×
3.78
3.28
1.15 ×
5.3
54
0
32K
5.95
2.06
2.89 ×
4.14
3.06
1.36 ×
14.4
31
100
64
16K
3.36
2.60
1.30 ×
4.19
3.84
1.09 ×
6.9
52
0
32K
5.81
2.76
2.11 ×
4.31
3.38
1.28 ×
16.1
29
100
Appendix
Table 8: Block-size sweep on DreamReasoner-8B. An execution test of dense and RISA only, on DreamReasoner-8B at 16K and 32K with 12 documents per cell. DreamReasoner was trained and evaluated at blocks of 4–32 tokens, and 64-token blocks extend the range tested here. Request latency (decode wall time, s), KL, reads, and cap activity use 512-token decodes replayed on each block size’s own dense trajectory, with KL referenced to the dense run at that block size. Attention profiles cover output positions 320–511 and amortize block work over dense’s steps per block. Both block sizes use 16-token pages, an 8,192-token HOT cap, a 256-token grace window, a 128-page COLD quota, ρ=0.5 , and mass-only admission; the allocator preserves the admission rate and the reservoir size in tokens. Cap activity is the share of RISA’s sparse blocks whose reused plan hits the HOT cap.
Model, context
Dense
RISA
MAGE
QUEST
LoSA
DreamReasoner, 32K
1.00 / 1.00 5.8 / 77.1 / 795
2.69 / 1.55 3.7 / 77.1 / 771
1.50 / 1.27 4.6 / 79.2 / 778
1.36 / 1.16 5.0 / 81.2 / 758
1.24 / 0.89 6.5 / 75.0 / 882
SDAR, 32K
1.00 / 1.00 6.9 / 62.5 / 587
3.02 / 1.47 4.7 / 62.5 / 585
1.95 / 1.30 5.3 / 62.5 / 604
1.37 / 1.07 6.5 / 60.4 / 599
1.26 / 0.92 7.5 / 56.2 / 657
Appendix
Table 9: Native decoding on book-prefixed MATH-500. Each setting uses 48 paired problems and a 2,048-token output cap. Each method follows its own trajectory. Cells report attention and per-request speedup over dense (top), then mean decode seconds, answer accuracy (%), and mean output tokens (bottom). Attention speedups use one profiled request per method and setting. MAGE and QUEST use 8,192 tokens and LoSA uses 4,096.
Variant
DreamReasoner 16K
DreamReasoner 32K
SDAR 16K
SDAR 32K
cap Kmax = 128 pages (2,048 tokens)
1.26 × / 0.0292
1.52 × / 0.0575
1.21 × / 0.0138
1.51 × / 0.0167
cap Kmax = 256 pages
0.96 × / 0.0127
1.46 × / 0.0305
1.20 × / 0.0054
1.50 × / 0.0077
cap Kmax = 512 pages (default)
1.14 × / 0.0045
1.61 × / 0.0135
1.17 × / 0.0012
1.47 × / 0.0028
cap Kmax = 1,024 pages
1.14 × / 0.0045
1.40 × / 0.0052
1.12 × / 0.0004
1.39 × / 0.0008
no cap
1.14 × / 0.0045
1.40 × / 0.0052
1.12 × / 0.0004
1.30 × / 0.0004
ρ = 0.25
0.99 × / 0.0132
1.74 × / 0.0139
1.20 × / 0.0054
1.47 × / 0.0029
Appendix
Table 10: One-factor sensitivity around the default on three further documents. Each cell gives per-request speedup over dense under native decoding, where every method, dense included, decodes its own 512-token trajectory, followed by KL to dense measured separately on dense’s denoising states for the same documents. The default ρ is 0.5 on DreamReasoner and 1.0 on SDAR.
Method
DreamReasoner 16K
DreamReasoner 32K
SDAR 16K
SDAR 32K
Dense
46.9 / 92.7
43.8 / 93.8
6.2 / 51.0
18.8 / 68.8
RISA (default)
46.9 / 92.7
40.6 / 92.7
6.2 / 51.0
12.5 / 65.6
MAGE 4K
43.8 / 92.7
40.6 / 91.7
6.2 / 47.9
9.4 / 58.3
QUEST 4K
46.9 / 94.8
34.4 / 84.4
6.2 / 42.7
6.2 / 56.2
LoSA 1K
31.2 / 80.2
31.2 / 81.2
18.8 / 64.6
34.4 / 78.1
RISA KV reads (%)
53.8
29.7
53.1
29.1
Appendix
Table 11: Multi-needle retrieval in long prompts. Three needles with two distractors in 16 documents, two layouts ( n=32 per cell). Each cell gives in-order exact match (all three needles answered in order) / per-needle recall (share of the three needles retrieved), in %. The final rows give RISA’s realized KV reads relative to dense and the share of its sparse blocks whose reused plan hits the HOT cap, averaged over requests. MAGE and QUEST use 4,096 tokens and LoSA 1,024.
Figure 10: Recovery and retrieval under bounded reads. (a) Generated-history recovery: KL to dense ( ×10−3 ) after 4,096 generated tokens (six documents per model and context) for RISA, flat retrieval (one ranking over HOT and COLD), HOT-only (recovery reads spent on HOT pages), and no recovery. The first three use comparable read volumes where measured. (b) Prompt retrieval of three needles among distractors ( n=32 ; 12 on LLaDA2.2-mini): per-needle recall for dense and RISA (top, with gaps in percentage points) and RISA’s KV reads relative to dense (bottom; dark: HOT cap active in at least half of sparse blocks).
Method
HotpotQA
Long-context MATH-500
MATH-500
GSM8K
DreamReasoner-8B
RISA (default)
0.0087
0.0090
0.0031
0.0013
RISA, no recovery ( q=0 )
0.0141
0.0479
0.0232
0.0013
MAGE 8K
0.0055
0.0054
0.0003
0.0001
QUEST 8K
0.0071
0.0115
0.0005
0.0001
LoSA 1K
0.2101
0.1687
0.0456
0.0074
Appendix
Table 12: Fidelity on benchmark prompts : KL to dense along dense’s own generation. In long-context MATH-500, a MATH-500 problem follows a long document, so generated history ages into COLD before the answer is complete.
Method
16K
32K
64K
128K
Dense
3.201
5.438
9.829
18.763
QUEST
5.355
5.211
6.123
7.772
MAGE
2.785
2.954
5.280
10.159
RISA
2.135
2.348
2.799
3.394
Appendix
Table 13: Absolute efficiency results on DreamReasoner-8B. Attention latency in milliseconds per denoising step for the original configuration (QUEST and MAGE at 1,024 tokens), from one profiled source per context with block work amortized over 15.6 steps; 64K and 128K lie beyond the configured 32K window and measure execution only. Bold marks the fastest sparse method.
LLM inference acceleration develops algorithms and systems that reduce language-model latency, memory use, and serving cost while preserving output quality.
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
Diffusion Language Models (DLMs) enable globally coherent, bidirectional, and controllable text generation, offering advantages over traditional autoregressive LLMs, while scaling to ultra-long sequences remains costly. Many existing block-sparse attention methods select blocks by fixed sampling patterns over the high-resolution attention space, such as tail regions or anti-diagonal stripes. Such prior-driven sampling can miss salient tokens and introduce instability under distribution shifts. In this paper, we propose the Block Approximate Sparse Attention framework (BA-Att) with block-wise pre-downsampled operation, which identifies informative regions within a compact downsampled space, avoiding reliance on brittle positional priors. To analyze its theoretical behavior, we define an oracle post-downsample attention map and formalize the approximation error between pre- and post-downsample schemes. Based on this insight, we introduce a lightweight norm-sorting module and a covariance-compensated correction that approximates full covariance using diagonal QK variances, reducing computational complexity. Extensive experiments show that our operator achieves up to 6.95x acceleration over FlashAttention in attention computation, and maintains near full-attention performance at 50% sparsity across language models, multimodal language models, and video generation models, demonstrating strong efficiency and generalization.
Wenhu Zhang, Yiming Wu, Huanyu Wang +6
The Hong Kong University of Science and Technology · The University of Hong Kong · Zhejiang University +1
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.
Zhichen Zeng, Xichong Zhang, Junpan Wu +7
University of Washington · University of Waterloo · University of Wisconsin, Madison +3