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

Bumjun Kim; Dongjae Jeon; Moongyu Jeon; Albert No

cs.LGMar 13, 2026

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

Authors: Bumjun Kim, Dongjae Jeon, Moongyu Jeon, Albert No

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

Abstract

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

Figures & tables

Panel of Figure 1 — Figure 1: Visualization of unmasking trajectories for DAPD (ours) and Fast-dLLM during the initial 50% of decoding steps. While DAPD processes independent questions simultaneously to maximize global parallelism, Fast-dLLM exhibits a highly sequential unmasking pattern. Other baselines demonstrate similar sequential behaviors (see Figs. 9 , 10 , 11 and 12 ). Detailed discussion is provided in Sec. 6 .

Figure 2: Illustration of synthetic MRF dataset.

Edge Detection		Degree Estimation
AUC $\uparrow$	Ratio (Edge/Non-edge) $\uparrow$	OVR $\downarrow$
0.928	2.204	0.04

Table 1: Metrics for edge detection and degree estimation. AUC and edge/non-edge attention ratio measure edge detection, and OVR measures degree estimation. Results are averaged over 100 random sampling paths and all decoding steps. Further step-wise and layer-choice results are in Tabs. 9 and 10 .

Figure 3: Accuracy–Steps trade-off of decoding strategies on two dLLMs. Top : LLaDA. Bottom : Dream. Left : Code tasks (HumanEval, MBPP). Middle : Math tasks (GSM8K, Math500). Right : Instruction-following task (IFEval). Markers denote decoding strategies. For LLaDA, baselines are shown with block decoding and EOS suppression settings (“4 Blocks” and “EOS-Inf”), while DAPD is evaluated in the single-block regime by default. For Dream, all methods are evaluated in the single-block regime. Colored lines indicate different tasks. The exact numerical values corresponding to this plot are provided in Tab. 3 .

Figure 4: Score–steps trade-off on ParallelBench using LLaDA. Exact numerical values are provided in Tab. 4 .

Figure 5: Left: Distribution of tokens unmasked during the initial 40% of decoding. Progress is normalized by total steps per sample and method. Heatmaps show the average unmasking trajectory, where lighter colors indicate earlier unmasking and white regions denote tokens remaining masked. Vertical color bars (labeled above) indicate average starting positions for the five questions; FD denotes Fast-dLLM. Right: Average number of isolated segments per decoding step, characterizing sequence fragmentation. Notably, DAPD exhibits a distinct unmasking pattern, whereas baselines show highly similar behaviors.

Method	Acc. $\uparrow$	Steps (Speedup) $\downarrow$
Original	52.64	256.0 (1.00 $\times$ )
Fast-dLLM	52.12	124.4 (2.06 $\times$ )
KLASS	52.2	177.4 (1.44 $\times$ )
EB-Sampler	51.2	131.3 (1.95 $\times$ )
DAPD (Ours)	52.08	66.2 (3.87 $\times$ )

Table 2: Accuracy and average decoding steps, with relative speedup measured against step-by-step LLaDA decoding strategy. “Original” denotes confidence-based token-by-token decoding.

Appendix figures & tables17 assets

Supplementary material from the paper’s appendix.

Appendix

	HumanEval		MBPP		GSM8K		Math500		IFEval
Method	Acc.	Steps	Acc.	Steps	Acc.	Steps	Acc.	Steps	Acc.	Steps
LLaDA
Fast-dLLM	37.2	92.1	20.6	41.5	76.8	72.8	28.0	95.6	58.3	100.0
EB-Sampler	37.2	110.4	19.4	52.6	76.1	86.9	28.2	113.2	57.0	136.3
KLASS	37.8	149.4	26.0	53.9	75.6	93.9	26.4	118.6	58.4	139.0
DAPD-Staged	36.6	45.2	40.4	37.6	71.7	48.9	29.0	58.8	62.0	50.1

Appendix

Table 3: Numerical results for the LLaDA and Dream experiments, including the settings visualized in Fig. 3 . For LLaDA, the baseline results (Fast-dLLM, EB-Sampler, and KLASS) are reported under four-block decoding, since their single-block variants suffer severe performance degradation due to EOS overflow. For Dream, all methods are evaluated under a unified single-block decoding setup. DAPD-Staged denotes the main variant that applies dependency-graph selection and, after the remaining mask ratio falls below 50%, admits positions with confidence

>0.9

into the independent-set selection procedure. DAPD-Direct denotes the optional acceleration variant that, at each decoding step, first commits positions with confidence

=1.0

and then applies dependency-aware independent-set selection to the remaining masked positions. EOS-suppressed single-block baseline results are reported separately in Tab. 5 .

	Words $\rightarrow$ Sentence		Paraphrase		Waiting Line		Puzzle
Method	Score	Steps	Score	Steps	Score	Steps	Score	Steps
Fast-dLLM	78.2	27.3	60.4	30.8	55.9	9.9	29.6	22.6
EB-Sampler	77.7	35.4	60.5	44.6	59.8	23.9	28.6	30.0
KLASS	78.0	34.9	60.7	39.8	57.2	20.5	30.1	29.6
DAPD-Staged	88.2	19.1	59.2	24.6	55.3	18.7	27.3	18.8
DAPD-Direct	86.5	17.9	59.4	18.9	54.8	10.8	23.4	20.1

Appendix

Table 4: Numerical results for ParallelBench, including the settings visualized in Fig. 4 .

		HumanEval		MBPP		GSM8K		Math500		IFEval
Method	Setting	Acc.	Steps	Acc.	Steps	Acc.	Steps	Acc.	Steps	Acc.	Steps
KLASS	1 block	11.0	97.3	19.8	43.3	26.3	72.6	3.0	83.4	40.1	96.5
	1 block + EOS-Inf	38.4	170.0	41.4	177.1	64.8	124.4	27.4	155.3	64.9	221.8
	4 blocks	37.8	149.4	26.0	53.9	75.6	93.9	26.4	118.6	58.4	139.0
Fast-dLLM	1 block	10.4	40.7	9.6	34.2	7.5	89.4	1.8	76.4	41.7	31.7
	1 block + EOS-Inf	37.2	107.9	40.4	153.1	68.5	110.0	27.8	132.9	64.7	178.4

Appendix

Table 5: Accuracy (%) and average decoding steps under single-block, EOS-suppressed single-block, and four-block decoding. Without EOS suppression, the single-block baselines suffer severe performance degradation due to EOS overflow ( Kim et al., 2026 ) . EOS-Inf mitigates this collapse, but typically requires substantially more decoding steps. The four-block setting is used for the main comparison.

Panel of Figure 6 — Figure 6: Analysis of $\tau_{\min}$ . Left: LLaDA. Right: Dream.

Method	Acc. $\uparrow$	Steps $\downarrow$	TPS $\uparrow$
DAPD	36.6	45.2	106.0
Fast-dLLM	37.2	92.1	51.4
EB-Sampler	37.2	110.4	39.2
KLASS	37.8	149.4	25.6
Original	39.0	256.0	20.4

Appendix

Table 6: End-to-end throughput comparison on HumanEval. Accuracy, average decoding steps, and tokens per second (TPS) are reported. “Original” denotes confidence-based token-by-token decoding.

Task	Length	Acc. $\uparrow$	Steps $\downarrow$	TPS $\uparrow$
HumanEval	256	36.6	45.2	106.0
	512	32.9	55.9	106.6
	1024	31.7	67.5	93.6
GSM8K	256	70.7	48.2	33.9
	512	72.8	68.4	39.0
	1024	70.7	79.9	45.8

Appendix

Table 7: Longer-generation evaluation of DAPD-Staged. Accuracy, average decoding steps, and tokens per second (TPS) are reported for different maximum generation lengths.

Method	Blocks	Acc. $\uparrow$	TPS $\uparrow$
	1	36.6	106.0
	4	37.8	57.1
	8	39.6	43.6
DAPD	16	41.5	34.6
Fast-dLLM	4	37.2	51.4
EB-Sampler	4	37.2	39.2

Appendix

Table 8: Block-wise decoding evaluation on HumanEval. Accuracy and tokens per second (TPS) are reported under different numbers of generation blocks.

Steps	Edge Detection		Degree Estimation
	AUC $\uparrow$	Ratio (Edge/Non-edge) $\uparrow$	OVR $\downarrow$
1	$0.923\pm 0.00$	$2.19\pm 0.00$	$0.00\pm 0.00$
2	$0.923\pm 0.02$	$2.21\pm 0.12$	$0.04\pm 0.01$
3	$0.919\pm 0.04$	$2.18\pm 0.23$	$0.05\pm 0.01$
4	$0.916\pm 0.04$	$2.17\pm 0.21$	$0.08\pm 0.02$
5	$0.937\pm 0.05$	$2.23\pm 0.24$	$0.05\pm 0.01$

Appendix

Table 9: Edge detection and degree estimation metrics across decoding steps, reported as mean

\pm

standard deviation over sampling paths.

Layer Selection	AUC $\uparrow$	Ratio (Edge/Non-edge) $\uparrow$	OVR $\downarrow$
Last 2 layers	0.93	2.20	0.04
Last 1 layer	0.92	2.16	0.06
Last 4 layers	0.90	2.06	0.08
All layers	0.87	1.95	0.15
First 4 layers	0.81	1.81	0.22
First 2 layers	0.78	1.72	0.29

Appendix

Table 10: Layer-selection ablation for attention-based dependency estimation on the synthetic MRF dataset.

Figure 7: Illustrative example of DAPD. Five independent questions (top) and their unmasked states across decoding steps.

Figure 8: Illustrative example of DAPD. Five independent questions (top) and their unmasked states across decoding steps.

Figure 9: Illustrative example of EB-Sampler. Five independent questions (top) and their unmasked states across decoding steps.

Figure 10: Illustrative example of EB-Sampler. Five independent questions (top) and their unmasked states across decoding steps.

Figure 11: Illustrative example of KLASS. Five independent questions (top) and their unmasked states across decoding steps.

Figure 12: Illustrative example of KLASS. Five independent questions (top) and their unmasked states across decoding steps.

Figure 13: Illustrative example of Fast-dLLM. Five independent questions (top) and their unmasked states across decoding steps.

Figure 14: Illustrative example of Fast-dLLM. Five independent questions (top) and their unmasked states across decoding steps.

Explore similar work

Dependency-Guided Parallel Decoding in Discrete Diffusion Language Models
Apr 2, 2026Liran Ringel, Ameen Ali, Yaniv RomanoDiffusion Language Model Decoding Diffusion Language Models
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
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
PSD: Pushing the Pareto Frontier of Diffusion LLMs via Parallel Speculative Decoding
May 15, 2026Shengyin Sun, Yiming Li, Renxi Liu +7Masked Diffusion Models Speculative Decoding for Diffusion Language Models
Department of Computer Science City University of Hong Kong · Huawei Technologies · City University of Hong Kong

Apr 2, 2026J/K move · Enter open · S save

Dependency-Guided Parallel Decoding in Discrete Diffusion Language Models

Liran Ringel, Ameen Ali, Yaniv Romano

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

Diffusion Language Model Decoding Diffusion Language Models Parallel Decoding Diffusion Model Inference Acceleration

Open paper AskPDF arXiv

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.

Abstract

Explore similar work

Dependency-Guided Parallel Decoding in Discrete Diffusion Language Models

DMax: Aggressive Parallel Decoding for dLLMs

PSD: Pushing the Pareto Frontier of Diffusion LLMs via Parallel Speculative Decoding