Dependency-Aware Masking for Parallel Decoding in Masked Diffusion Language Models

Masked Diffusion Language Models (MDLMs) offer a parallel alternative to autoregressive models by enabling parallel text generation. However, simultaneously unmasking multiple tokens relies on a strict conditional independence assumption. Standard training and sampling are both structure-agnostic, so strongly coupled syntactic pairs can be decoded jointly, introducing significant factorization errors that degrade text quality. To address this at training time, we propose Dependency-Aware Masking, a non-intrusive training formulation that utilizes linguistic dependency trees to replace the standard uniform noise schedule with a depth-aware soft prior. This biases the model to safely reconstruct conditionally independent peripheral modifiers before resolving the densely coupled syntactic core. At inference time, we pair it with a multi-token sampler that unmasks independent sets of an attention-derived interaction graph, avoiding the joint decoding of strongly coupled tokens. Extensive evaluations across MDLM and BD3-LM architectures demonstrate that our framework consistently outperforms uniform-masking baselines on unconditional generation, establishing a superior trade-off between generation quality and decoding efficiency.