PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Bumjun Kim, Dongjae Jeon, Moongyu Jeon, Albert No

arXiv:2603.12996v2cs.LG

TL;DR

Parallel decoding in dLLMs is challenging because token-wise marginals do not capture dependencies among simultaneously unmasked positions. DAPD uses self-attention to build a dependency graph and decode weakly coupled tokens together; on LLaDA and Dream, it improves the accuracy–steps trade-off over strong training-free baselines while shifting updates toward globally dispersed generation.

  • Problem

    dLLMs provide token-wise conditional marginals, but parallel unmasking requires accounting for inter-token dependencies to avoid joint–marginal mismatch.

    Source: §1 · p. 1

  • Method

    DAPD uses self-attention to estimate masked-token interactions, builds a dependency graph, and selects an approximately independent set for parallel unmasking.

    Source: §1 · pp. 1–2

  • Results

    Across LLaDA and Dream, DAPD improves the accuracy–steps trade-off over strong training-free baselines and shifts decoding toward globally dispersed, order-flexible generation.

    Source: §1 · p. 2, §7 · p. 9

  • Takeaways & Limitations

    Self-attention can serve as a lightweight dependency proxy that complements marginal confidence with cross-position interaction information for parallel decoding.

    Source: §7 · p. 9

    DAPD relies on heuristic graph-threshold and attention-layer choices, and its attention-based edge scores are practical proxies rather than exact conditional-independence tests.

    Source: D. Related Work, Discussion and… · p. 19

Abstract

from arXiv · show

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

1. Introduction

Parallel decoding in dLLMs must reconcile token-wise predictions with dependencies among masked positions. DAPD uses self-attention to construct a dependency graph, select weakly coupled tokens for parallel updates, and improve the accuracy–steps trade-off on LLaDA and Dream.

1. Introduction

  • Parallel unmasking from token-wise marginals alone ignores inter-token dependencies, risking outputs that are locally plausible but globally inconsistent.Marginal-based strategies can still decode confident yet dependent positions together, leaving joint–marginal mismatch unresolved.Source: §1 · p. 1
  • DAPD uses self-attention to estimate masked-token dependencies and represents significant interactions as graph edges.Controlled synthetic experiments support attention as a signal for recovering the ground-truth interaction structure.Source: §1 · p. 1
  • DAPD casts parallel decoding as dynamic graph coloring and selects an approximately independent set of masked-token nodes for each update.Its Welsh–Powell-inspired heuristic prioritizes high-degree hub tokens to simplify the residual graph.Source: §1 · p. 2
  • Across LLaDA and Dream, DAPD achieves a better accuracy–steps trade-off than state-of-the-art baselines.The introduction reports this as a consistent benchmark result.Source: §1 · p. 2
  • Unlike confidence-driven clustered updates, DAPD prioritizes independent regions across the sequence, producing more spatially dispersed unmasking.Figure 1 contrasts DAPD’s simultaneous processing of independent questions with Fast-dLLM’s sequential pattern during the initial 50% of decoding steps.Source: §1 · p. 2, Figure 1 · p. 2

2. Preliminaries

Masked diffusion models iteratively recover masked tokens from token-wise conditional distributions, with unmasking order affecting generation quality in practice. Parallel decoding can reduce dLLM forward passes, but selecting multiple positions from marginal predictions risks ignoring their dependencies.

2.1. Masked Diffusion Models

  • In masked diffusion models, tokens are progressively masked and the model learns to recover original tokens using conditional predictions at masked positions.The model iteratively unmasks tokens from a fully masked input sequence.Source: §2.1 · p. 2
  • Any unmasking permutation theoretically yields samples from the same distribution, but unmasking order affects generation quality in practice.Confidence-based sampling prioritizes masked positions with the highest maximum predicted probability.Source: §2.1 · p. 2
  • Semi-autoregressive variants generate within fixed-length blocks using diffusion while processing blocks sequentially from left to right.This approach enables block-level KV caching during inference.Source: §2.1 · p. 3
  • LLaDA and Dream are examples of large language models trained using masked diffusion approaches.The passage also notes that such models may be trained from scratch or through autoregressive initialization.Source: §2.1 · p. 3

2.2. Parallel Decoding of dLLMs

  • Parallel decoding can reduce the number of model forward passes, since each decoding step requires exactly one pass and total steps equal NFE.The number of steps is therefore a central computational efficiency target.Source: §2.2 · p. 3
  • Unmasking multiple positions simultaneously can produce errors because token-wise marginals do not capture the true joint distribution or dependencies among the positions.The discrepancy can accumulate when dependencies among simultaneously decoded tokens are not fully accounted for.Source: §2.2 · p. 3
  • Training-free baselines select parallel positions using marginal-based criteria, including confidence ranking, entropy bounds, confidence thresholds, or confidence plus stability.Other approaches use additional training, auxiliary models, or modified strategies, which can incur extra cost or depart from the ELBO-based formulation.Source: §2.2 · p. 3

3. Modeling Dependencies via Graphs

The paper models dependencies among masked tokens with an attention-induced Markov Random Field (MRF), then tests whether attention scores and aggregates reflect its structure. The validation finds strong edge/non-edge separation and close agreement between proxy and true degree orderings.

3. Modeling Dependencies via Graphs

  • DAPD represents masked-token dependencies as an MRF, using self-attention to define conditional-dependency structure and reducing parallel decoding to selecting an independent set.Edges represent stronger interactions; non-edges indicate negligible interactions.Source: §3 · p. 3, §3.1 · p. 4

3.1. Attention-Induced Markov Random Fields

  • Low attention between two positions motivates treating them as approximately conditionally independent given the remaining context.This links the attention-based non-edge construction to the MRF local Markov property.Source: §3.1 · p. 4

3.2. Validation of Graph Construction

  • AUC of 0.928 and an edge-to-nonedge score ratio of 2.204 indicate that attention scores separate MRF edges from non-edges; mean OVR is 0.04.The controlled toy validation uses length-9 sequences whose four local constraints form four triangles.Source: Table 1 · p. 4, §3.2 · pp. 4–5
  • The attention-sum proxy reliably orders nodes by true degree, with mean OVR = 0.04; lower OVR means better agreement with the true ordering.OVR measures the fraction of node pairs whose strict ordering under true degrees is reversed by proxy scores.Source: §3.2 · p. 5

4. Dependency-Aware Parallel Decoding

DAPD uses attention-induced dependencies to select masked tokens for parallel unmasking while limiting updates to tokens without direct graph edges. It treats decoding as coloring a changing graph and uses a degree-prioritized greedy strategy, refined by confidence and a late-stage threshold rule.

4. Dependency-Aware Parallel Decoding

  • DAPD selects masked-token batches as independent sets in the attention-induced graph, aiming to reduce joint–marginal mismatch and decoding steps.It uses pairwise non-adjacency as a practical relaxation: stricter separation would require more verification and yield smaller batches.Source: §4 · p. 5, §4.1 · p. 5

4.1. Independent Set Selection via Structural Relaxation

  • Pairwise non-adjacency is used instead of requiring no path between selected nodes, which would incur substantial verification cost and yield prohibitively small batches.The paper states that natural-language dependencies are predominantly captured by direct interactions.Source: §4.1 · p. 5

4.2. Parallel Decoding as Dynamic Graph Coloring

  • Because masked nodes and edges change after each decoding step, DAPD applies graph-coloring intuition dynamically to minimize the number of steps.Each color class is an independent set; covering all masked positions with few such sets corresponds to fewer decoding steps.Source: §4.2 · p. 5

4.3. Implementation via a Coloring Strategy

  • The Welsh–Powell-inspired procedure orders nodes by degree and greedily selects a maximal independent set, prioritizing high-degree nodes to simplify the residual graph.A maximal set need not be the largest possible at that step; the strategy aims to reduce future color classes and total decoding steps.Source: §4.3 · pp. 5–6
  • DAPD ranks nodes by confidence-weighted degree, multiplying proxy degree by marginal confidence to prioritize positions that are structurally influential and reliably predictable.The final implementation uses the maximum predicted token probability as marginal confidence.Source: §4.3 · p. 6
  • When the remaining mask ratio falls below 50%, DAPD unmasks all positions with confidence > 0.9 as the graph becomes sparse.The paper interprets this late-stage regime as one where most remaining nodes have near-zero degree.Source: §4.3 · p. 6

5. Experiments

Experiments compare DAPD with training-free baselines on LLaDA and Dream across code, math, instruction-following, and dependency-stress-test tasks. DAPD generally offers a more favorable accuracy–steps or score–steps trade-off, with evaluation settings differing between models.

Setup

  • The evaluation uses LLaDA-8B-Instruct and Dream-7B-Instruct, comparing DAPD with EB-Sampler, KLASS, and Fast-dLLM using reported best hyperparameters for the baselines.Tasks include GSM8K, Math500, MBPP, HumanEval, IFEval, and ParallelBench; generation is capped at 256 tokens.Source: §5 · pp. 6–7

Results

  • LLaDA baselines’ accuracy collapses under one-block decoding, primarily because of premature termination from EOS overflow, so the evaluation uses block-wise decoding or EOS suppression for them.DAPD is evaluated in the single-block regime by default.Source: §5 · p. 7, Figure 3 · p. 7
  • DAPD occupies the upper-left accuracy–steps region on LLaDA, improving accuracy on MBPP and IFEval over block-wise baselines and reducing steps at comparable accuracy on other tasks.Single-block decoding with EOS suppression reaches comparable accuracy but requires significantly more steps; Fig. 4 also shows a more favorable score–steps trade-off on most ParallelBench tasks.Source: §5 · p. 7, Figure 3 · p. 7, Figure 4 · p. 7
  • On Dream, evaluated with all methods in a unified single-block setup, DAPD maintains a superior accuracy–steps trade-off relative to baselines.The authors report that Dream does not support block-wise decoding or EOS suppression and does not show severe EOS overflow at a 256-token generation length.Source: §5 · p. 7
  • Figure 5 reports a distinct DAPD unmasking pattern, unlike the highly similar patterns of the baselines.The figure summarizes token unmasking during the initial 40% of decoding and average isolated-segment counts per step.Source: Figure 5 · p. 8

6. Analysis of Decoding Behavior

On prompts combining independent questions, DAPD distributes unmasking across distant regions, unlike marginal-confidence baselines that decode locally. The reported behavior accompanies substantial speedups while matching step-by-step LLaDA accuracy.

Setup

  • The setup bundles five independent TriviaQA questions into each prompt, allowing conditional independence to arise within one generation.It comprises 500 evaluation samples, or 2,500 individual questions.Source: §6 · p. 8
  • The analysis uses LLaDA with a 256-token generation budget and disables block-wise decoding to isolate decoding-strategy effects.The authors report no EOS overflow because the prompts are sufficiently short.Source: §6 · p. 8

Results

  • More than 1.8× speedup over competing strategies and 3.8× over step-by-step decoding accompany DAPD matching step-by-step LLaDA accuracy on bundled independent questions.The evaluation uses five randomly sampled TriviaQA questions per prompt, with 500 samples totaling 2,500 questions.Source: §6 · p. 8, Table 2 · p. 8

Sequential bottlenecks in baselines

  • Marginal-confidence baselines predominantly unmask adjacent tokens, keeping segment counts low and resolving independent queries sequentially.The authors characterize this as autoregressive-like behavior that limits throughput and use of dLLMs’ any-order flexibility.Source: §6 · p. 8

Spatially dispersed generation in DAPD

  • DAPD unmasking is spatially dispersed early across the five queries, forming multiple segments before they consolidate in later steps.The analysis describes partial context across queries as reducing uncertainty in remaining masked spans.Source: §6 · pp. 8–9

7. Conclusion

The conclusion presents DAPD as a training-free way to address joint–marginal mismatch by using self-attention to estimate dependencies among masked tokens. Its graph-based selection improves the accuracy–steps trade-off across LLaDA and Dream and yields more dispersed, order-flexible generation.

Conclusion

  • DAPD uses self-attention to estimate masked-token interactions, builds a dependency graph, and selects weakly coupled positions for parallel unmasking.The method is described as training-free and as directly targeting joint–marginal mismatch.Source: §7 · p. 9
  • Across LLaDA and Dream, DAPD improves the accuracy–steps trade-off over strong training-free baselines and shifts decoding toward globally dispersed, order-flexible generation.Source: §7 · p. 9
  • The paper frames self-attention as a lightweight dependency proxy that complements marginal confidence with cross-position interaction information.It casts parallel decoding as dynamic graph coloring guided by the evolving structure of inter-token dependencies.Source: §7 · p. 9

Impact Statement

The work aims to improve the efficiency of diffusion-based language-model inference. It seeks to reduce decoding steps without additional training or auxiliary models, with no direct societal impacts anticipated beyond those associated with language generation models.

Impact Statement

  • The stated goal is to improve the efficiency of diffusion-based language-model inference.Source: Impact Statement · p. 9
  • The proposed approach seeks to reduce decoding steps without additional training or auxiliary models.Source: Impact Statement · p. 9
  • The authors anticipate no direct societal impacts beyond those generally associated with language-generation models.Source: Impact Statement · p. 9

A. Details on Main Experiments

The appendix details the main experimental settings and reports additional results on accuracy, decoding steps, throughput, generation length, and block-wise decoding. It also motivates the attention-edge threshold schedule and describes the ParallelBench evaluation protocol.

Experimental Setup

  • Experiments use NVIDIA L40S GPUs, disable stochastic decoding parameters, and follow lm-eval defaults; LLaDA baselines use four blocks because single-block decoding suffers EOS-overflow degradation.The appendix also reports baseline hyperparameter sweeps and task-dependent linear τt schedules for DAPD.Source: A. Details on Main Experiments · pp. 12–14, Table 5 · p. 13

Results

  • DAPD-STAGED gives the most stable accuracy–steps trade-off while substantially reducing steps; DAPD-DIRECT usually reduces steps further with modest accuracy changes and occasional score gains.DAPD-STAGED is the default; DAPD-DIRECT is an optional latency-oriented variant.Source: A. Details on Main Experiments · p. 12

Threshold Analysis

  • For LLaDA and Dream at generation length 256, τmin values of 0.01 and 0.005 fall in the near-zero tail of observed edge scores, respectively.The authors report that lowering τmin further has little effect on the available low-dependency pairs.Source: Figure 6 · p. 13, A. Details on Main Experiments · p. 14

ParallelBench

  • ParallelBench evaluation covers task-specific instance sizes and generation lengths, with DAPD using shared linear τt schedules for its two variants.DAPD-Staged uses [0.01, 0.2] and DAPD-Direct uses [0.01, 0.05]; the baselines use default LLaDA hyperparameters.Source: A. Details on Main Experiments · p. 14

End-to-End Throughput

  • DAPD achieves the highest HumanEval throughput among compared methods, and TPS strongly aligns with the inverse of decoding steps.The authors attribute the small graph-processing overhead to reusing attention weights and avoiding extra model evaluations.Source: Table 6 · p. 14, A. Details on Main Experiments · p. 14

Longer Generation Lengths

  • At generation lengths of 256, 512, and 1024, DAPD maintains strong throughput as decoding steps grow moderately and TPS remains largely stable.The authors report that graph-processing overhead does not dominate inference cost.Source: Table 7 · p. 15, A. Details on Main Experiments · p. 15

Block-Wise Decoding

  • With 4, 8, or 16 blocks, DAPD remains compatible with block-wise generation and achieves competitive or better accuracy than baselines, while more blocks tend to reduce throughput.Independent sets are selected only within the current block, limiting parallelism across distant positions.Source: Table 8 · p. 15, A. Details on Main Experiments · p. 15

B. Details on Toy Experiments

The toy experiments evaluate attention-derived dependency estimates against synthetic MRF structure and examine which attention layers provide the most reliable signal. The reported layer-selection results favor later layers in the synthetic model.

Toy Experiment Setup

  • The synthetic experiments use 30 masked diffusion models trained for 20,000 steps on datasets constructed by the same MRF procedure.The models use an eight-block DiT architecture within RADD and the LLaDA training objective.Source: B. Details on Toy Experiments · p. 16

Dependency Scores

  • Dependency scores average attention from the final two of eight transformer blocks, with similar patterns observed using one, two, or three final blocks.This describes the synthetic-model score construction, not the large-model layer aggregation.Source: B. Details on Toy Experiments · p. 16

Evaluation Details

  • Metrics are computed through the seventh of nine decoding steps, averaged over 100 random sampling paths and 30 independently trained models.The final two-node edge is excluded from the reported step range.Source: B. Details on Toy Experiments · p. 16

Layer-Selection Ablation

  • The last two layers provide the most reliable dependency signal, with highest AUC and edge/non-edge attention ratio and lowest OVR; early layers substantially degrade all metrics.The authors apply the same upper-layer principle by averaging attention over the final 30% of layers in the large-model setting.Source: Table 10 · p. 16, B. Details on Toy Experiments · p. 16

C. Details and Additional Results on Analysis

The analysis appendix describes the independently aggregated question evaluation, including how its factual-recall dataset is curated and how generated answers are scored. It also reports the decoding visualizations and baseline hyperparameter selection procedure.

Dataset Construction

  • Sampled from TriviaQA, questions were filtered for concise, unambiguous factual recall, limited to single sentences of at most 120 characters and excluding Why/How queries; 12,380 remained before 500 five-question instances were sampled.Source: C. Details and Additional Results on… · p. 17

Evaluation Details

  • Accuracy is the fraction of questions whose parsed answer matches a ground-truth answer or alias, while average NFE measures decoding steps.Answers are extracted using bracketed markers and the phrase “Therefore, the answer is,” with a fallback phrase and then whole-segment matching.Source: C. Details and Additional Results on… · pp. 17–18

Hyperparameter Details

  • Baseline hyperparameters are swept on LLaDA, and each baseline is reported using the setting that yields the highest accuracy; DAPD uses a linear τt schedule over [0.01, 0.05].The sweeps cover EB-Sampler’s γ, confidence thresholds for Fast-dLLM and KLASS, and KL thresholds for KLASS.Source: C. Details and Additional Results on… · p. 18

Additional Qualitative Results

  • Additional unmasking-trajectory visualizations are provided for DAPD, EB-Sampler, KLASS, and Fast-dLLM.The appendix also describes the setup for analyzing decoding behavior on independently aggregated queries.Source: C. Details and Additional Results on… · pp. 17–18

D. Related Work, Discussion and Limitations

The discussion positions DAPD as an inference-time graph-selection approach that differs from related dependency methods and frames its MRF as an algorithmic conflict graph, not an exact inference procedure. It also distinguishes token confidence from cross-position dependence and identifies heuristic thresholds and attention-based dependence estimates as limitations.

Related Work

  • Unlike DAWN, which uses an attention graph to relax confidence thresholds around committed anchors, DAPD builds a graph over masked positions and selects an independent-set batch.The paper also contrasts DAPD’s fixed pretrained model with Li et al. (2026), which adds a probabilistic inference layer.Source: D. Related Work, Discussion and… · p. 18

Role of the MRF Formulation

  • The MRF is a conflict-graph formulation: masked positions are nodes, strong attention interactions are edges, and independent sets define candidate parallel batches.It is intended to make decoding a concrete graph-selection problem, not to perform exact probabilistic inference.Source: D. Related Work, Discussion and… · p. 18

Independence and Decoding Priority

  • DAPD separates token reliability, measured by confidence, from cross-position dependence, estimated by attention, to select larger low-conflict batches than confidence-only strategies.Degree-prioritized scheduling aims to simplify the residual graph over time; attention scores remain a lightweight proxy for dependence.Source: D. Related Work, Discussion and… · p. 18

Limitations

  • DAPD relies on heuristic threshold schedules and attention-layer choices, and attention-based edge scores are proxies rather than exact conditional-independence tests.The authors suggest more principled adaptive thresholds, layer aggregation, and dependency estimators may improve robustness across architectures and tasks.Source: D. Related Work, Discussion and… · p. 19

Related papers

Loading 2603.12996v2…