End-to-End Guarantees for Masked Diffusion Models under Conditional Mixing

Masked diffusion models train a denoiser on masked cross-entropy and generate by unmasking many positions in parallel, but sampling bounds assume a perfect denoiser, and training bounds cover only the masking distribution on which the model was trained. We present the first end-to-end guarantee for a \textit{learned} denoiser under conditional mixing (CM): sources (order-$r$ Markov and two-sided-Doeblin hidden-Markov sources among them) for which editing distant visible tokens moves a masked token's posterior exponentially little in the distance with correlation length $\tau_c$. The masked cross-entropy minimizer attains per-token excess $\varepsilon'$ from $\varepsilon'^{-O(\tau_c\log|\mathcal{V}|)}$ training sequences, independent of sequence length $N$ and \textit{uniform} over masking distributions --- one sample budget serves every decoding schedule, each trained under its weighting. We further show via a matching minimax lower bound that the exponent's order $\Theta(\tau_c\log|\mathcal{V}|)$ is tight; polynomial rates require added structure. Finally, we show $\text{KL}(\pi\| p_{\mathrm{alg}})\leq \varepsilon+N\varepsilon'$ under a dilated schedule of $T=O(\tau_c\log(N|\mathcal{V}|/\varepsilon))$ denoising steps versus $\Omega(N)$ steps for random order on an explicit CM source, block-autoregressive samplers chain across blocks with no added error, and $\Lambda$-looped denoisers on order-$r$ sources achieve polynomial sample complexity with approximation error improving per loop until saturation at $\Lambda r\approx \tau_c\log(1/\varepsilon')$. Experiments on released and retrained models validate our results.