Discrete diffusion need not pay for vocabulary size: masked and uniform noising both hit minimax rates on sparse data
Synopsis
Discrete diffusion models have lacked the statistical theory that continuous diffusion enjoys, and it was unclear whether they can exploit sparse structure in the data distribution. This analysis casts masked-diffusion score estimation as a per-context label-smoothed classifier and shows the smoothing is equivalent to regularizing with the score loss of the uniform distribution. On sparse distributions where at most k sequences have positive probability, the terminal laws of both masked and uniform noising attain the sparse minimax rate, and the smoothing level can be chosen adaptively from the number of distinct training sequences without knowing the sparsity parameter.
Interpretation
Discrete diffusion models can reach the minimax estimation rate for sparse distribution classes, so the error is governed by sparsity rather than by the exponentially large sequence state space. Earlier statistical bounds for discrete diffusion depended on the size of the diffusion state space and on density-ratio conditions, without quantifying adaptation to the support size of the clean distribution; continuous diffusion already had results exploiting low-dimensional structure. On the class of distributions where at most k sequences have positive probability, with no independence assumption on coordinates and no lower bound on positive probabilities, the terminal-law error of both masked and uniform noising attains the sparse minimax rate in expectation and with high probability.
The masked-diffusion score factorizes into a classifier predicting the token at a masked position times an explicit time-dependent factor, so label smoothing from classification can regularize it directly. Minimizing the empirical score-entropy objective directly yields a score that assigns zero probability to unobserved sequences, giving infinite forward KL divergence and no analyzable estimator. Adding a per-context smoothing term that varies with the number of observations makes the minimizer exactly the proper score induced by the smoothed empirical distribution; frequently observed contexts are barely smoothed and unseen contexts are predicted uniformly.
The same regularization extends to uniform noising: the minimizer of the mixed score-entropy loss is still the exact score of the smoothed empirical distribution, though it no longer corresponds to classifier label smoothing. The masked case relies on the context-wise factorization of the score, which a general noising kernel does not provide, so a separate argument is needed. Uniform diffusion has no fully masked initial state, so initializing the sampler at the uniform law adds an error that is shown to be absorbed, at the cost of a logarithmic lower bound on the time horizon.
Perspective
The analysis is confined to a finite sequence space, the class of sparse distributions where at most k sequences have positive probability, and the two standard mechanisms of uniform and masked noising; the masked case recovers the terminal law exactly from the fully masked state, while the uniform case needs a logarithmic lower bound on the time horizon. Experiments check the closed-form smoothed estimator on stationary laws of small sparse Markov chains and train a score network on the empirical n-gram law of text8, with a more practical high-dimensional ablation left for future work.
The bounds involve effective support and effective missing-support quantities that depend on the data distribution, and the admissible range of smoothing levels depends on the unknown sparsity parameter in general, requiring an adaptive choice based on the number of distinct observed sequences. The authors note that whether the gap between masked and uniform diffusion in practice comes from score approximation or optimization remains open, and rigorous empirical evaluation of the regularization methods is left for future work.