Dependency-Guided Parallel Decoding in Discrete Diffusion Language Models

Liran Ringel; Ameen Ali; Yaniv Romano

cs.CLApr 2, 2026

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

Abstract

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 $\times$ 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

\hat{\mathbf{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.

Panel of Figure 3 — Figure 3: Dependency predictor architecture. Hidden states $\mathbf{H}$ from the frozen backbone are projected via learned $\mathbf{W}_{Q},\mathbf{W}_{K}$ , then combined via scaled dot-product and sigmoid to predict the pairwise dependency matrix $\hat{\mathbf{D}}$ .

Method	MMLU-Pro	GSM8K	HumanEval	MBPP	Avg
Entropy (1 tok)	43.9 $\pm$ 0.4 (1.0 $\times$ )	81.2 $\pm$ 1.1 (1.0 $\times$ )	53.7 $\pm$ 3.9 (1.0 $\times$ )	58.0 $\pm$ 2.2 (1.0 $\times$ )	51.8 (1.0 $\times$ )
Entropy (2 tok)	39.7 $\pm$ 0.4 (2.0 $\times$ )	76.7 $\pm$ 1.2 (2.2 $\times$ )	31.1 $\pm$ 3.6 (1.1 $\times$ )	43.8 $\pm$ 2.2 (1.3 $\times$ )	38.2 (1.5 $\times$ )
Top-1 (1 tok)	45.5 $\pm$ 0.4 (1.0 $\times$ )	81.2 $\pm$ 1.1 (1.0 $\times$ )	53.7 $\pm$ 3.9 (1.0 $\times$ )	58.0 $\pm$ 2.2 (1.0 $\times$ )	52.4 (1.0 $\times$ )
Top-1 (2 tok)	43.5 $\pm$ 0.4 (2.0 $\times$ )	76.7 $\pm$ 1.2 (2.1 $\times$ )	31.1 $\pm$ 3.6 (1.1 $\times$ )	43.8 $\pm$ 2.2 (1.4 $\times$ )	39.5 (1.5 $\times$ )
Token Order (1 tok)	45.7 $\pm$ 0.4 (1.3 $\times$ )	80.7 $\pm$ 1.1 (1.1 $\times$ )	55.5 $\pm$ 3.9 (1.3 $\times$ )	57.8 $\pm$ 2.2 (1.5 $\times$ )	53.0 (1.3 $\times$ )
Token Order (2 tok)	43.6 $\pm$ 0.4 (2.8 $\times$ )	73.8 $\pm$ 1.2 (2.1 $\times$ )	24.4 $\pm$ 3.4 (1.1 $\times$ )	40.8 $\pm$ 2.2 (1.5 $\times$ )	36.2 (1.8 $\times$ )

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

\mathrm{RHS}_{i}-\mathrm{LHS}_{i}

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|\geq 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 .

Explore similar work

DAPD: Dependency-Aware Parallel Decoding via Attention for Diffusion LLMs
Mar 13, 2026Bumjun Kim, Dongjae Jeon, Moongyu Jeon +1Parallel Decoding Diffusion Language Model Decoding
Department of Artificial Intelligence, Yonsei University, Seoul, Korea · Department of Computer Science, Yonsei University, Seoul, Korea
DOS: Dependency-Oriented Sampler for Masked Diffusion Language Models
Mar 16, 2026Xueyu Zhou, Yangrong Hu, Jian HuangLanguage Model Decoding Diffusion Language Model Decoding
Department of Data Science and AI The Hong Kong Polytechnic University, Hong Kong, China
DMax: Aggressive Parallel Decoding for dLLMs
Apr 9, 2026Zigeng Chen, Gongfan Fang, Xinyin Ma +2Diffusion Language Model Decoding Diffusion Language Models
National University of Singapore

Mar 13, 2026J/K move · Enter open · S save

DAPD: Dependency-Aware Parallel Decoding via Attention for Diffusion LLMs

Bumjun Kim, Dongjae Jeon, Moongyu Jeon, Albert No

Department of Artificial Intelligence, Yonsei University, Seoul, Korea · Department of Computer Science, Yonsei University, Seoul, Korea

Parallel Decoding Diffusion Language Model Decoding Diffusion Model Inference Acceleration

Open paper AskPDF arXiv

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

Abstract

Explore similar work

DAPD: Dependency-Aware Parallel Decoding via Attention for Diffusion LLMs

DOS: Dependency-Oriented Sampler for Masked Diffusion Language Models

DMax: Aggressive Parallel Decoding for dLLMs