Dependency-Guided Parallel Decoding in Discrete Diffusion Language Models
Authors: Liran Ringel, Ameen Ali, Yaniv Romano
Organizations: Department of Computer Science, Technion – Israel Institute of Technology · Department of Electrical and Computer Engineering, Technion – Israel Institute of Technology · Blavatnik School of Computer Science and AI, Tel Aviv, Israel
Discrete diffusion language models (dLLMs) accelerate text generation by unmasking multiple tokens in parallel. However, parallel decoding introduces a distributional mismatch: it approximates the joint conditional using a fully factorized product of per-token marginals, which degrades output quality when selected tokens are strongly dependent. We propose DEMASK (DEpendency-guided unMASKing), a lightweight dependency predictor that attaches to the final hidden states of a dLLM. In a single forward pass, it estimates pairwise conditional influences between masked positions. Using these predictions, a greedy selection algorithm identifies positions with bounded cumulative dependency for simultaneous unmasking. Under a sub-additivity assumption, we prove this bounds the total variation distance between our parallel sampling and the model's joint. Empirically, DEMASK achieves 1.7-2.2× speedup on Dream-7B while matching or improving accuracy compared to confidence-based and KL-based baselines.
Figures & tables
Figure 1: Accuracy vs. mean diffusion steps (forward passes) on GSM8K for DEMASK and KLASS. Each point represents a hyperparameter configuration; darker points indicate higher confidence thresholds. The Pareto frontier (dashed) shows DEMASK dominates across the efficiency-accuracy trade-off. Dream (1 TPF) denotes 1 token per forward pass with entropy selection.
Figure 2: Overview of DEMASK. (A) A lightweight dependency predictor attaches to the dLLM backbone and estimates pairwise dependencies D^ from hidden states in a single forward pass. (B) Greedy subset selection identifies positions with bounded cumulative dependency for parallel unmasking. (C) The iterative decoding cycle: each step performs a forward pass, selects positions, and samples them in parallel until all tokens are unmasked.
Figure 3: Dependency predictor architecture. Hidden states H from the frozen backbone are projected via learned WQ,WK , then combined via scaled dot-product and sigmoid to predict the pairwise dependency matrix D^ .
Method
MMLU-Pro
GSM8K
HumanEval
MBPP
Avg
Entropy (1 tok)
43.9 ± 0.4 (1.0 × )
81.2 ± 1.1 (1.0 × )
53.7 ± 3.9 (1.0 × )
58.0 ± 2.2 (1.0 × )
51.8 (1.0 × )
Entropy (2 tok)
39.7 ± 0.4 (2.0 × )
76.7 ± 1.2 (2.2 × )
31.1 ± 3.6 (1.1 × )
43.8 ± 2.2 (1.3 × )
38.2 (1.5 × )
Top-1 (1 tok)
45.5 ± 0.4 (1.0 × )
81.2 ± 1.1 (1.0 × )
53.7 ± 3.9 (1.0 × )
58.0 ± 2.2 (1.0 × )
52.4 (1.0 × )
Top-1 (2 tok)
43.5 ± 0.4 (2.0 × )
76.7 ± 1.2 (2.1 × )
31.1 ± 3.6 (1.1 × )
43.8 ± 2.2 (1.4 × )
39.5 (1.5 × )
Token Order (1 tok)
45.7 ± 0.4 (1.3 × )
80.7 ± 1.1 (1.1 × )
55.5 ± 3.9 (1.3 × )
57.8 ± 2.2 (1.5 × )
53.0 (1.3 × )
Token Order (2 tok)
43.6 ± 0.4 (2.8 × )
73.8 ± 1.2 (2.1 × )
24.4 ± 3.4 (1.1 × )
40.8 ± 2.2 (1.5 × )
36.2 (1.8 × )
Table 1: Comparison of DEMASK and KLASS on Dream-7B. Each cell shows accuracy (%) with speedup in parentheses, relative to Entropy (1 tok). Bold : best average accuracy (Avg excludes GSM8K).
Figure 4: Empirical CDF of the slack RHSi−LHSi stratified by subset size ∣S∣ , evaluated on Tulu 3 SFT Mixture with Dream-7B. The ∣S∣=1 curve (vertical line at zero) is trivially satisfied. For ∣S∣≥2 , positive slack indicates the sub-additivity bound holds.
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
DEMASK
KLASS
Benchmark
Acc (%)
Time (min)
Acc (%)
Time (min)
MMLU-Pro
47.6
89.6
45.7
126.7
GSM8K
83.7
10.1
82.6
14.3
HumanEval
58.5
5.8
54.3
4.1
MBPP
56.6
19.3
57.0
6.9
Appendix
Table 2: Results without EOS optimization. Runtime in minutes. Best accuracy per benchmark in bold .
Parallel decoding for Diffusion LLMs (dLLMs) is difficult because each denoising step provides only token-wise marginal distributions, while unmasking multiple tokens simultaneously requires accounting for inter-token dependencies. We propose Dependency-Aware Parallel Decoding (DAPD), a simple, training-free decoding method that uses self-attention to induce a conditional dependency graph over masked tokens. At each iteration, edges in this graph capture strong token interactions, while non-edges indicate weak dependence. Parallel decoding is then reduced to selecting an independent set on the graph and unmasking the selected tokens in parallel. This avoids co-updating strongly coupled tokens without auxiliary models or retraining. Experiments on LLaDA and Dream show that DAPD improves the accuracy-steps trade-off over existing methods and enables more globally distributed parallel updates that better exploit the any-order generation capability of dLLMs. The project is available at https://ai-isl.github.io/dapd
Bumjun Kim, Dongjae Jeon, Moongyu Jeon +1
Department of Artificial Intelligence, Yonsei University, Seoul, Korea · Department of Computer Science, Yonsei University, Seoul, Korea
Masked diffusion language models (MDLMs) have recently emerged as a new paradigm in language modeling, offering flexible generation dynamics and enabling efficient parallel decoding. However, existing decoding strategies for pre-trained MDLMs predominantly rely on token-level uncertainty criteria, while largely overlooking sequence-level information and inter-token dependencies. To address this limitation, we propose Dependency-Oriented Sampler (DOS), a training-free decoding strategy that leverages inter-token dependencies to inform token updates during generation. Specifically, DOS exploits attention matrices from transformer blocks to approximate inter-token dependencies, emphasizing information from unmasked tokens when updating masked positions. Empirical results demonstrate that DOS consistently achieves superior performance on both code generation and mathematical reasoning tasks. Moreover, DOS can be seamlessly integrated with existing parallel sampling methods, leading to improved generation efficiency without sacrificing generation quality.
Xueyu Zhou, Yangrong Hu, Jian Huang
Department of Data Science and AI The Hong Kong Polytechnic University, Hong Kong, China
We present DMax, a new paradigm for efficient diffusion language models (dLLMs). It mitigates error accumulation in parallel decoding, enabling aggressive decoding parallelism while preserving generation quality. Unlike conventional masked dLLMs that decode through a binary mask-to-token transition, DMax reformulates decoding as a progressive self-refinement from mask embeddings to token embeddings. At the core of our approach is On-Policy Uniform Training, a novel training strategy that efficiently unifies masked and uniform dLLMs, equipping the model to recover clean tokens from both masked inputs and its own erroneous predictions. Building on this foundation, we further propose Soft Parallel Decoding. We represent each intermediate decoding state as an interpolation between the predicted token embedding and the mask embedding, enabling iterative self-revising in embedding space. Extensive experiments across a variety of benchmarks demonstrate the effectiveness of DMax. Compared with the original LLaDA-2.0-mini, our method improves TPF on GSM8K from 2.04 to 5.47 while preserving accuracy. On MBPP, it increases TPF from 2.71 to 5.86 while maintaining comparable performance. On two H200 GPUs, our model achieves an average of 1,338 TPS at batch size 1. Code is available at: https://github.com/czg1225/DMax