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

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 \url{https://ai-isl.github.io/dapd}

Many AI writing systems generate text one piece at a time, from left to right. A newer type, called a diffusion language model, starts with many blanks and gradually fills them in, so it could write faster by filling several blanks at once. The problem is that some blanks depend on each other: in “The capital of ___ is ___,” the two missing words must agree. If related blanks are filled together, the model may choose words that each look reasonable alone but do not fit together. We introduce Dependency-Aware Parallel Decoding (DAPD), a way to decide which blanks are safe to fill at the same time. DAPD looks at the model’s attention, which shows which parts of the sentence the model is using, and builds a simple map of which blanks seem connected. It fills groups of weakly connected blanks in parallel and waits on blanks that strongly depend on each other. In experiments, DAPD generated text in fewer steps while keeping answer quality strong, without training a new model or adding another system.