Masked diffusion models stop paying for sequence length: with latent structure, training samples grow only polynomially in hidden states

The sampling error of a masked diffusion model can now be accounted for as a whole, instead of treating parallel sampling error and finite-sample estimation error separately. Earlier theory either took the mask predictor as given or gave bounds scaling with the target support size or the full sequence-space size, which can stay exponential in sequence length even when the data admit a compact latent representation. The end-to-end guarantee folds the parallelization error and the finite-sample estimation error of the mask predictor into one KL upper bound, where the estimation term is governed by the predictor's parameter count over the sample size.

The guaranteed sample size is set by the latent structure of the data, not by the size of the sequence space. The data distribution is modeled through mixtures of hidden Markov trees, which capture latent dependence within components and heterogeneity across components, and the distribution need not belong to this class exactly. When the data distribution is approximated by such a mixture and the parallelization error is sufficiently small, the structural complexity is polynomial in sequence length, vocabulary size, number of hidden states, and number of components; when the latent space is small compared with vocabulary and length, the training samples needed for a given KL accuracy scale polynomially with the number of hidden states.

Neither the transformer mask predictor nor the parallel sampling procedure needs prior knowledge of the tree topologies or component parameters. The architecture depends only on the chosen budget parameters, not on the latent variables, trees, or probability tables, and one network class approximates the masked-token conditionals of every such distribution uniformly. Training uses only observed data, with the budget parameters trading approximation against estimation; for structures whose component trees have bounded height, a complementary construction replaces the complexity term with a height-dependent quantity and uses depth proportional to the tree height.

The guarantees concern discrete sequence data, use the same fixed-cardinality unmasking schedule for training and inference, and require the data distribution to be well approximated by a mixture of hidden Markov trees. The intended reader is a researcher studying the statistical behavior of discrete diffusion models and the approximation power of transformers. For structures whose component trees have bounded height, a complementary construction replaces the complexity term with a height-dependent quantity and uses depth proportional to the tree height.

The analysis assumes a predictor obtained by empirical risk minimization, whereas practical training performs finitely many parameter updates. The guarantee also requires the parallelization error to be sufficiently small, and that error depends only on the data distribution and the unmasking schedule used at inference. Extending the analysis to latent graphical models with cycles, to confidence-based unmasking, and to include optimization error is left open.