Dependency-Aware Parallel Decoding via Attention
for Diffusion LLMs

Bumjun Kim1*, Dongjae Jeon2*, Moongyu Jeon1*, Albert No1†
1Department of Artificial Intelligence, Yonsei University
2Department of Computer Science, Yonsei University
* Equal contribution; † Corresponding author.
ICML 2026
Paper arXiv Code

TL;DR: DAPD uses self-attention to turn parallel decoding into a graph-coloring problem, selecting weakly coupled masked tokens for simultaneous unmasking. It is training free and reduces steps by up to 8.53×.

Single prompt with five independent questions. Compare how DAPD-Direct and Fast-dLLM generate the response.

  1. In which country were the settlers called Voortrekkers?
  2. What is the name of the alternative medicine that uses essential oils?
  3. In which country were the Mau-Mau a secret guerrilla movement?
  4. Which city used to be called Constantinople?
  5. What colour are tea leaves when they are picked?

Introduction

Diffusion Large Language Models (dLLMs), such as LLaDA and Dream, have emerged as a promising alternative to autoregressive models. A key point is parallel decoding: multiple masked tokens can in principle be unmasked at the same step, dramatically reducing the number of function evaluations (NFE) compared with strict left-to-right generation.

However, dLLMs are trained to model only token-wise conditional marginals, not joint distributions. Sampling several tokens at once from their marginals therefore breaks inter-token dependencies — the joint–marginal mismatch:

$$ p(x^{i_1},\dots,x^{i_k}\mid \mathbf{x}) \;\neq\; \prod_{j=1}^k p(x^{i_j}\mid \mathbf{x}). $$

Existing training-free methods sidestep this issue by ranking masked positions with marginal signals like confidence or entropy. But marginal scores are blind to inter-position interactions, yielding suboptimal decoding decisions.

We propose Dependency-Aware Parallel Decoding (DAPD): a training-free decoding algorithm that turns the model's own self-attention into a conditional dependency graph (Markov Random Field) over masked tokens, then frames parallel decoding as dynamic graph coloring. Following the Welsh-Powell heuristic, we order masked positions by descending degree and greedily admit each into the current independent set, anchoring the highest-degree positions first. Each step thus decodes many weakly-coupled tokens in parallel while effectively preserving the joint distribution.

Why Parallel Decoding Is Challenging

dLLMs are trained to model the marginal distribution over each masked token individually. Consider the prompt “The capital of [MASK] is [MASK].” The model may assign high marginal probability to France at the first position and to London at the second — each plausible in isolation, but jointly nonsensical. Decoding them in parallel from marginal signals can yield an invalid pair.

Existing baselines rank mask positions by marginal confidence, but DAPD asks a more direct question: which masked positions are conditionally independent given the current context, and therefore safe to update together? The model already encodes its dependency beliefs in self-attention: strong mutual attention between two masked positions signals that resolving one would shift the prediction at the other — precisely what we must avoid within a parallel batch.

Dependency-Aware Parallel Decoding (DAPD)

1. Attention → Markov Random Field

Our starting observation: the self-attention at the upper layers of a dLLM behaves like a conditional dependency graph over the masked tokens — precisely the Markov Random Field (MRF) over those positions.

To validate this empirically, we train a small MDM on a synthetic dataset with a known MRF structure (see Fig. 3) and compare attention scores against the ground-truth edges. Attention at the final layers recovers the true edges with AUC 0.928 and ranks node degrees with an order-violation rate of just 0.04, confirming that attention encodes the MRF. See the paper for details.

Synthetic MRF with four overlapping triangles used to validate that attention recovers the ground-truth dependency structure.
Figure 1. Synthetic MRF with four overlapping triangles. Attention at upper layers recovers the ground-truth edges.

What is Markov Random Field?

Markov Random Field. A collection of random variables $\{X_v\}_{v\in V}$ forms an MRF with respect to an undirected graph $G=(V, E)$ if it satisfies the pairwise Markov property:
$$ (u,v)\notin E \;\;\Longrightarrow\;\; X_u \perp\!\!\!\perp X_v \,\bigm|\, X_{V\setminus\{u,v\}}. $$
In words: missing edges → conditional independence — non-adjacent nodes carry no information about each other given the rest. In short, non-connected masked positions can be safely sampled together.

How do we relax this in practice?

The MRF demands global conditional independence (given all other variables), but self-attention only gives us a pairwise signal $a_{ij}$ — the direct weight from $i$ to $j$. We relax the definition by using low pairwise attention as a proxy for conditional independence:

$$ s_{ij} \;:=\; \tfrac{1}{2}(a_{ij} + a_{ji}), \qquad (i,j)\in E_t \;\Longleftrightarrow\; s_{ij} > \tau_t, $$

averaging over all heads in the final 30% of layers, where upper layers integrate more global context. Intuitively, if $j$ barely attends to $i$, then $j$ contributes little to the prediction at $i$ — so low pairwise attention serves as a reasonable proxy for pairwise independence.

2. Parallel Decoding as Dynamic Graph Coloring

Selecting tokens to unmask in parallel reduces to picking an independent set on $G_t$ — a set of pairwise non-adjacent nodes. Covering all masked positions with the fewest such sets is the classical graph coloring problem. (i.e., color the graph with the fewest colors s.t. no adjacent nodes share a color; each color class is an independent set.)

We adopt a Welsh–Powell–style greedy strategy: process high-degree “hub” tokens first to break the major dependency chains, simplifying the residual graph for later steps. In practice we sort by a confidence-weighted degree (i.e., effective degree of node $i$).

Algorithm (DAPD, per step $t$).
  1. Score. Read attention from the forward pass; compute $s_{ij}$ and $\tilde d_i = \sum_{j\neq i} s_{ij}$.
  2. Sort. Order masked positions by $\tilde d_i \cdot \mathrm{conf}_i$ in descending order.
  3. Greedy select. Scan the list; add $i$ to $S$ iff it has no edge to any node already in $S$ (i.e., $s_{ij}\le\tau_t$ for all $j\in S$).
  4. Unmask in parallel. All tokens in $S$ are sampled simultaneously.

Once the remaining mask ratio drops below 50%, the graph is mostly disconnected and DAPD switches on an aggressive confidence>0.9 rule — the disconnected regime makes parallel firing safe. We call this main variant DAPD-Staged.

An optional acceleration variant, DAPD-Direct, commits any position that reaches confidence 1.0 at every step, before independent-set selection. A position placing all its mass on one token is deterministic, and a deterministic variable is independent of every other position by definition, so committing it adds no joint–marginal mismatch while unlocking even fewer decoding steps.

3. What This Looks Like in Practice

We bundle five independent TriviaQA questions into a single prompt and compare how each decoder fills it in (see details below). DAPD spreads its early unmaskings across all five queries simultaneously. Fast-dLLM and other marginal confidence baselines instead move through the sequence almost autoregressively, resolving one query before moving to the next.

DAPD unmasking trajectory: tokens are unmasked across all five queries in a globally dispersed pattern.
Figure 2 (a). DAPD-Staged (Ours). Globally dispersed unmasking — multiple independent regions resolved in parallel.
Fast-dLLM unmasking trajectory: tokens are filled in contiguously, expanding from sequence boundaries inward.
Figure 2 (b). Fast-dLLM. Highly sequential, contiguous expansion — behaves like two-sided autoregressive decoding.

Experimental Results

1. Accuracy–Steps Trade-off on LLaDA & Dream

Table 1. Main accuracy–steps results on LLaDA and Dream. For LLaDA, baselines use four-block decoding (single-block baselines collapse due to EOS overflow); DAPD is evaluated in the single-block regime. For Dream, all methods use a unified single-block setup. Accuracy in %, Steps in number of decoding steps. Bold = best per column, underline = second-best.
Method HumanEval MBPP GSM8K Math500 IFEval
Acc.Steps Acc.Steps Acc.Steps Acc.Steps Acc.Steps
LLaDA
Fast-dLLM 37.292.1 20.641.5 76.872.8 28.095.6 58.3100.0
EB-Sampler 37.2110.4 19.452.6 76.186.9 28.2113.2 57.0136.3
KLASS 37.8149.4 26.053.9 75.693.9 26.4118.6 58.4139.0
DAPD-Staged 36.645.2 40.437.6 71.748.9 29.058.8 62.050.1
DAPD-Direct 37.222.7 37.220.8 70.932.5 27.245.9 57.342.9
Dream
Fast-dLLM 43.3112.2 30.667.7 47.790.2 17.5158.7 18.253.2
EB-Sampler 45.7155.4 30.6186.5 44.5127.6 13.0190.5 7.1115.2
KLASS 59.8133.3 34.460.8 45.1154.4 13.0204.2 7.1132.1
DAPD-Staged 42.1111.6 46.449.3 56.069.5 25.459.7 39.290.0
DAPD-Direct 43.3117.8 48.226.9 59.455.6 26.456.0 38.718.6
DAPD dominates the accuracy–steps frontier. DAPD-Direct uses the fewest decoding steps on every task — typically 2–4× fewer than the closest baseline and up to ~12× fewer than vanilla 256-step token-by-token decoding. DAPD-Staged trades a bit of that speed for the most stable accuracy, taking the top spot on most accuracy cells across both models. Together they form a clean fast vs. stable dial.

2. ParallelBench — Stress-Testing Dependencies

ParallelBench stress-tests parallel decoding with dependency-heavy prompts: Words→Sentence, Waiting Line, Paraphrase, and Puzzle. These tasks expose the weakness of naive parallel decoding samplers.

Fig. 3 shows that marginal confidence baselines require more decoding steps, while DAPD-Staged achieves a much better score and steps tradeoff by selecting non-conflicting tokens for parallel unmasking. For full results, including DAPD-Direct, see App. Table 4 in the paper.

Score-vs-steps scatter plots on four ParallelBench tasks for DAPD-Staged, DAPD-Direct, Fast-dLLM, EB-Sampler, and KLASS using LLaDA. DAPD variants dominate the upper-left across tasks.
Figure 3. Score–steps trade-off on ParallelBench (LLaDA).

Analysis of Decoding Behavior

To compare decoding trajectories, we bundle five independent TriviaQA questions into a single prompt (500 prompts, 2,500 questions in total; see the bundled prompt below). These questions are independent: for example, knowing where Keflavík Airport is does not help answer who Janet Jackson's brother was. Thus, a good parallel sampler should be able to resolve different questions concurrently without conflict. See App. C in the paper for details on the experimental setup.

Example of bundled prompt
  1. In which country is Keflavík Airport?
  2. In what year did Tony Blair become leader of the Labour Party?
  3. What is the name of Janet Jackson's deceased superstar brother?
  4. In which year did Barbados join the Commonwealth?
  5. In which year did Franco capture Madrid and win the Spanish Civil War?
The model receives all five questions at once and must produce five answers in a single response.
Left: heatmap of token unmasking trajectories over the first 40% of decoding for several methods. Right: average number of isolated unmasked segments per step.
Figure 4. Left: token unmasking heatmaps over the first 40% of decoding. Lighter = earlier; white = still masked. Right: average segment count per step. DAPD's segment count rises sharply mid-decoding (many independent regions opened in parallel) and then collapses as the disjoint segments merge. Baselines maintain a flat, low segment count — effectively decoding one region at a time.

Fig. 4 (left) shows a clear difference in decoding behavior. DAPD spreads its early unmaskings across all five questions, while baselines tend to fill the prompt in a more contiguous, almost autoregressive order.

The segment count (Fig. 4, right) makes this pattern quantitative. DAPD opens many disjoint regions early and merges them later, whereas the baselines keep the segment count low throughout decoding. This global unmasking behavior leads to a strong efficiency gain: DAPD matches step by step accuracy (52.08 vs. 52.64) while reducing decoding from 256 steps to 66.2, achieving a 3.87× speedup.

Table 2. Accuracy and decoding steps on the 5-question TriviaQA bundles (LLaDA, single block). Bold = best, underline = 2nd-best. DAPD achieves a strong accuracy–steps trade-off by maximizing parallelism, while baselines struggle to break out of a sequential decoding pattern.
Method Acc. ↑ Steps ↓ Speedup
Original52.64256.01.00×
Fast-dLLM52.12124.42.06×
KLASS52.20177.41.44×
EB-Sampler51.20131.31.95×
DAPD-Staged52.0866.23.87×

BibTeX

@inproceedings{kim2026dapd,
  title={DAPD: Dependency-Aware Parallel Decoding via Attention for Diffusion LLMs},
  author={Kim, Bumjun and Jeon, Dongjae and Jeon, Moongyu and No, Albert},
  booktitle={International Conference on Machine Learning},
  year={2026}
}