Dependency-Guided Parallel Decoding in Discrete Diffusion Language Models

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. When applied to dParallel, a block diffusion model, DEMASK also produces Pareto-optimal accuracy-step trade-offs across math and code benchmarks.