Error Analysis of Masked Discrete Diffusion under Low Complexity Structure

Masked Diffusion Models have emerged as a discrete analogue of continuous Gaussian diffusion. They provide a new framework for learning distributions on discrete spaces and an alternative to autoregressive models for text generation. Despite the strong empirical performance of these models, theoretical analysis has been limited, focusing primarily on score estimation error, sampling guarantees and studying the structure of its Markov kernel. In this paper, we take a step towards end-to-end error analysis, derive approximation and finite-sample statistical error bounds for a Transformer-based predictor, analogous to the corresponding theory of continuous diffusion models. Our analysis identifies structural conditions on the clean-data conditional distributions under which their logits can be efficiently approximated by Transformers, and combines this approximation guarantee with Transformer complexity bounds to control estimation error. We further test empirically whether these structural conditions are supported by some common discrete distributions. This provides the first approximation-estimation theory for Transformer-based Masked Diffusion Models trained with a continuous-time NELBO loss and a data-dependent scaling law for the Transformer's attention window.