Non-Asymptotic Convergence of Discrete Diffusion Models: Masked and Random Walk dynamics
This work addresses a significant gap in theoretical foundations for discrete diffusion models, which are less explored than continuous ones, providing rigorous convergence bounds that could impact generative modeling in discrete domains.
The paper tackles the theoretical understanding of discrete diffusion models (DDMs) by establishing sharp non-asymptotic convergence guarantees for three popular models—random walk, masking process, and drifted random walk on infinite spaces—under minimal data assumptions, showing computational complexity scaling linearly in dimension up to logarithmic factors.
Diffusion models for continuous state spaces based on Gaussian noising processes are now relatively well understood from both practical and theoretical perspectives. In contrast, results for diffusion models on discrete state spaces remain far less explored and pose significant challenges, particularly due to their combinatorial structure and their more recent introduction in generative modelling. In this work, we establish new and sharp convergence guarantees for three popular discrete diffusion models (DDMs). Two of these models are designed for finite state spaces and are based respectively on the random walk and the masking process. The third DDM we consider is defined on the countably infinite space $\mathbb{N}^d$ and uses a drifted random walk as its forward process. For each of these models, the backward process can be characterized by a discrete score function that can, in principle, be estimated. However, even with perfect access to these scores, simulating the exact backward process is infeasible, and one must rely on time discretization. In this work, we study Euler-type approximations and establish convergence bounds in both Kullback-Leibler divergence and total variation distance for the resulting models, under minimal assumptions on the data distribution. To the best of our knowledge, this study provides the optimal non-asymptotic convergence guarantees for these noising processes that do not rely on boundedness assumptions on the estimated score. In particular, the computational complexity of each method scales only linearly in the dimension, up to logarithmic factors.