Dependency-Aware Parallel Decoding via Attention for Diffusion LLMs
This addresses a bottleneck in speeding up generation for diffusion-based language models, though it is an incremental improvement over existing methods.
The paper tackles the challenge of parallel decoding in diffusion LLMs by proposing Dependency-Aware Parallel Decoding (DAPD), which uses self-attention to model token dependencies and enables more efficient unmasking, resulting in improved accuracy-steps trade-offs on datasets like LLaDA and Dream.
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.