Dependence Cost of Independent Updates in Masked Diffusion

Parallel token generation makes masked diffusion a useful approach to language modeling with fewer sequential sampling steps. However, sampling tokens independently can miss dependencies, and errors in the sampling trajectory can differ from errors in the final output distribution. We study progressive unmasking with distinct data and mask states, where masking decisions are independent across tokens and independent of their values. We express the smallest conditional approximation error exactly through the dependence among tokens revealed together, after conditioning on previously revealed tokens. For sequences built from independent pairs of correlated tokens, we analyze optimal schedules starting from the true fully masked distribution. We prove that the path error in relative entropy decreases inversely with the number of steps. For the sampler using exact conditional marginals, the output error in the same metric decreases with the inverse square of that number. For this family, exact representation by a finite mixture of product distributions requires exponentially many components as sequence length grows, while a suitable ordering permits exact sampling in two conditional rounds. Our results connect conditional dependence to sampling error and representation requirements.