Why Diffusion Language Models Struggle with Truly Parallel (Non-Autoregressive) Decoding?
Authors: Pengxiang Li, Dilxat Muhtar, Tianlong Chen, Lu Yin, Shiwei Liu
Organizations: The Hong Kong Polytechnic University, Hong Kong, China · ELLIS Institute Tübingen, Tübingen, Germany · Max Planck Institute for Intelligent Systems, Tübingen, Germany · Tübingen AI Center, Tübingen, Germany · The University of North Carolina at Chapel Hill, Chapel Hill, NC, USA · University of Surrey, Guildford, United Kingdom
Diffusion Language Models (DLMs) are often advertised as enabling parallel token generation, yet practical fast DLMs frequently converge to left-to-right, autoregressive (AR)-like decoding dynamics. In contrast, genuinely non-AR generation is promising because it removes AR's sequential bottleneck, better exploiting parallel hardware to reduce synchronization/communication overhead and improve latency scaling with output length. We argue that a primary driver of AR-like decoding is a mismatch between DLM objectives and the highly sequential structure of widely used training data, including standard pretraining corpora and long chain-of-thought (CoT) supervision. Motivated by this diagnosis, we propose NAP (Non-Autoregressive Parallel DLMs), a proof-of-concept, data-centric approach that better aligns supervision with non-AR parallel decoding. NAP curates examples as multiple independent reasoning trajectories and couples them with a parallel-forced decoding strategy that encourages multi-token parallel updates. Across math reasoning benchmarks, NAP yields stronger performance under parallel decoding than DLMs trained on standard long CoT data, with gains growing as parallelism increases. Our results suggest that revisiting data and supervision is a principled direction for mitigating AR-like behavior and moving toward genuinely non-autoregressive parallel generation in DLMs. Our code is available at https://github.com/pixeli99/NAP.
Figures & tables
Figure 1: Visualization of decoding dynamics. We plot the token position being unmasked (y-axis) against the decoding step (x-axis). (a, b) Despite using confidence-based Arbitrary Order (AO) decoding, standard DLMs (LLaDA and Dream) exhibit a strict linear diagonal pattern, revealing that their behavior collapses into autoregressive (left-to-right) generation. (c) Random decoding eliminates AR bias but lacks structure. (d) Our method (NAP) breaks the single-stream bottleneck, generating multiple reasoning trajectories simultaneously.
Figure 2: Performance on GSM8K (left) and MATH-500 (right). Forcing low-ARness behavior (Random decoding) generally causes reasoning performance to collapse. Notably, for LLaDA, we employ a constrained block-wise decoding strategy to ensure generation validity. This preserves local structural integrity, resulting in the Arbitrary Order (AO) decoding maintaining comparable performance, unlike the sharp drop observed in fully unstructured random decoding.
Figure 3: Sequential Dependence (SeqDep) Analysis on (a) OpenR1-Math and (b) FineWeb Datasets. The consistently high and rising SeqDep scores indicate that standard training corpora possess strong intrinsic sequentiality, driving models to internalize AR-like dependencies.
Model
AR Order
AO (Conf)
ARness
Acc
ARness
Acc
LLaDA-8B ( Nie et al., 2025c )
1.00
71.9
0.73
51.9
+ Fast-dLLM ( Wu et al., 2025 )
1.00
71.9
0.87
51.6
Dream-7B ( Ye et al., 2025 )
1.00
78.2
0.92
78.2
+ Fast-dLLM ( Wu et al., 2025 )
1.00
78.3
0.94
78.1
Table 1: Quantifying Autoregressive Bias (ARness) and Accuracy. Comparison of sequential bias and performance across different decoding strategies. While AR Order implies strict sequentiality (1.00), AO (Conf) maintains high ARness and competitive accuracy.
Model
Base (Pretrained)
Long-CoT (SFT)
Change
LLaDA-8B
0.73
0.81
↑ 0.08
Dream-7B
0.92
0.93
↑ 0.01
Table 2: Long-CoT Supervision Increases ARness. Comparison of Global ARness@1 scores (using AO decoding) before and after fine-tuning.
Figure 4: Long-CoT Supervision Increases ARness. The positive deltas show models converging toward strict left-to-right generation (1.0), confirming that current supervision methods actively discourage non-autoregressive parallel decoding.
Figure 6: Overview of the parallel-forced decoding framework . The model concurrently generates multiple independent reasoning paths within structured thinking blocks. These parallel trajectories are then synthesized into a result within a designated summary block.
Benchmark
Steps
Tok/Step
LLaDA 8B
LLaDA 8B (Long-CoT)
NAP-LLaDA 8B
Dream-7B
Dream-7B (Long-CoT)
NAP-Dream-7B
Mathematics & Scientific
GSM8K
256
4
46.4
54.1
56.1 (+2.0)
35.0
46.5
60.9 (+14.4)
336
3
54.4
60.9
63.3 (+2.4)
49.4
56.9
70.9 (+14.0)
512
2
62.0
82.0
82.6 (+0.4)
58.5
66.8
79.2 (+12.4)
1024
1
66.5
83.5
84.1 (+0.6)
68.9
78.0
83.6 (+5.6)
MATH-500
256
4
17.8
21.4
26.6 (+5.2)
8.8
16.2
23.8 (+7.6)
Table 3: Benchmark results on LLaDA-8B-Instruct and Dream-7B-Instruct under different step budgets. Tok/Step denotes the number of tokens decoded per decoding step; larger Tok/Step corresponds to higher decoding parallelism.
Training Data
Decoding
256
512
1024
Base (Pretrained)
AO
35.0
58.5
68.9
Base (Pretrained)
Parallel-Forced
31.0
52.6
60.2
NAP (Ours)
AO
57.4
78.9
85.1
NAP (Ours)
Parallel-Forced
60.9
79.2
83.6
Table 4: GSM8K accuracy using Dream-7B. Simply applying parallel decoding to a base model hurts performance; gains require aligned supervision.
Method
1 Path
2 Paths
3 Paths
NAP-Dream
75.4
78.9
83.6
NAP-LLaDA
79.4
82.6
84.1
Table 5: Accuracy on GSM8K with varying m . Total token budget is fixed.
Figure 7: SeqDep Analysis on Dparallel . We visualize the Sequential Dependence (SeqDep) of our curated parallel reasoning data against token length. The green curve (binned mean) shows that SeqDep remains stable and relatively low across varying lengths.