Beyond the Marginals: Dependence and Parallel Decoding in Masked Diffusion Language Models

Parallel decoding in masked diffusion language models commits multiple tokens simultaneously from a product of marginals, introducing an error governed by the unobserved conditional total correlation of the revealed set. We establish the fundamental limits of parallel decoding by characterizing the tightest dependence certificates across a hierarchy of available information, defined as the supremum of total correlation over all consistent joint laws. From marginal entropies alone, the excess-bit criterion is tightest whenever the vocabulary is large relative to the entropies; with full marginal vectors, the tightest certificate is attained by a minimum-entropy coupling and can improve upon the excess bits by an amount on the order of $\log |V|$ bits. Our main theoretical result characterizes the tightest certificate under truncated conditional queries: a residual coupling constrained by the marginals attains this certificate, and computable brackets decouple approximation slack from missing-information slack. On sources with known joint distributions, this formulation doubles the fraction of certified sets compared to discarding unqueried values, while for larger vocabularies missing query information accounts for most residual slack. Crucially, such query-based certificates presuppose that the denoiser outputs are conditionals of a single coherent joint law; truncation-aware tests on saved LLaDA-8B states reveal that real model outputs violate this precondition. Finally, we characterize the position left unconstrained by the excess-bit criterion, proving that anchoring it to the most uncertain position adds no parallelism and can paradoxically increase dependence.