End-to-End Guarantees for Masked Diffusion Models under Conditional Mixing
cs.LG
Submitted: 2026-10-29
Updated: 2026-10-29
Comments: Accepted at the NeurIPS 2026 Workshop on Diffusion Language Models: Foundations, Efficiency, and Reasoning (DiffuLM). 26 pages, 2 figures, 6 tables
License: http://creativecommons.org/licenses/by/4.0/
The gist: Masked diffusion models train a denoiser on masked cross-entropy and generate by unmasking many positions in parallel.
Terminology
Abstract
Masked diffusion models train a denoiser on masked cross-entropy and generate by unmasking many positions in parallel. Existing MDM sampling bounds assume an exact denoiser or leave its error uncontrolled while training bounds cover only the masking distribution on which the model was trained. We present an end-to-end guarantee for a learned denoiser under conditional mixing (CM): stationary sources (e.g. floored order- r Markov and two-sided-Doeblin hidden-Markov sources) for which revealing distant visible tokens moves a masked token's posterior on average exponentially little in the distance with correlation length τ c. We show the empirical risk minimizer trained under any masking distribution attains per-token excess epsilon' on that distribution from epsilon'-O(τ c V) training sequences, independent of sequence length N -- one sample budget serves every decoding schedule when each schedule's denoiser is trained under its own weighting. We further show that the exponent's order Θ(τ c V) is minimax-optimal up to constants; more efficient rates require added structure. With this, we bound the end-to-end KL as KL(π p alg) at most epsilon+N epsilon' under a dilated schedule of T= O(τ c (N V/epsilon)) denoising steps versus Ω(N) steps for a fixed random order on an explicit CM source. Finally, we show that block-autoregressive samplers chain across blocks with no added error and that a Λ-looped order- r message-passing class on order- r sources achieves polynomial sample complexity, with approximation error improving per loop until saturation at Λr about τ c (1/epsilon'). Experiments on released and retrained models support our results' qualitative predictions.
Related papers
- A Physics-Regulated Neural Framework for Learning 3D Grain Growth Dynamics
- FlexMoE: Learning One-for-All Multi-Budget Expert Pruning for Flexible MoE Deployment
- OptiMind: Improving Small Language Models for Optimization Modeling through Formulation Guidance and Multi-Turn Learning
- Staying in the Sweet Spot: Boost Reasoning Evolution via Responsive Rollout Difficulty Manipulation
- Examining the Impact of Data and Training Methods on Emergent and Subliminal Misalignment
- Rethinking Black-Box On-Policy Distillation: A Rubric-based Analysis