Sharp Convergence Rates for Masked Diffusion Models
cs.LG, stat.ML
Submitted: 2026-02-26
Updated: 2026-11-15
License: http://creativecommons.org/licenses/by/4.0/
The gist: Discrete diffusion models have achieved strong empirical performance in text and other symbolic domains…
Terminology
Abstract
Discrete diffusion models have achieved strong empirical performance in text and other symbolic domains, with masked (absorbing-rate) variants emerging as competitive alternatives to autoregressive models. Among existing samplers, the Euler method remains the standard choice in many applications, and more recently, the First-Hitting Sampler (FHS) has shown considerable promise for masked diffusion models. Despite their practical success, the theoretical understanding of these samplers remains incomplete. Many existing analyses are conducted in Kullback-Leibler (KL) divergence, which often yields loose parameter dependencies and requires strong assumptions on score estimation. Moreover, these guarantees do not cover recently developed high-performance sampler of FHS. In this work, we first develop a direct total-variation (TV)-based analysis for the Euler method that overcomes these limitations. Our results relax assumptions on score estimation, improve parameter dependencies, and establish convergence guarantees without requiring any surrogate initialization. Also for this setting, we provide the first convergence lower bound for the Euler sampler, establishing tightness with respect to all of the data dimension d, the vocabulary size S, and the target accuracy epsilon, up to logarithmic factors. Finally, we analyze the FHS sampler and show that it incurs no sampling error beyond that induced by score estimation, which we show to be tight with a matching lower error bound. Our analysis introduces two techniques that may be of independent interest: a comparison with a reference unmasking schedule for the Euler method and a pathwise argument exploiting the decoupling structure of FHS.
Sources
- On the $\epsilon$-Free Inference Complexity of Absorbing Discrete Diffusion
- Non-Asymptotic Convergence of Discrete Diffusion Models: Masked and Random Walk dynamics
- Convergence Analysis of Discrete Diffusion Model: Exact Implementation through Uniformization
- Efficient Sampling with Discrete Diffusion Models: Sharp and Adaptive Guarantees
- Almost Linear Convergence under Minimal Score Assumptions: Quantized Transition Diffusion
- Optimal Inference Schedules for Masked Diffusion Models
Related papers
- 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
- (Mis)generalization of Helpful-Only Fine-tuning