Discrete Diffusion Models: Novel Analysis and New Sampler Guarantees
This work provides more robust theoretical foundations for discrete diffusion models, which are important for applications in natural language and graph data, though it is incremental in improving existing analysis methods.
The paper tackled the problem of analyzing discrete diffusion models by introducing a new analytical approach that removes restrictive assumptions and improves convergence guarantees for samplers like τ-leaping, achieving linear scaling with vocabulary size instead of quadratic.
Discrete diffusion models have recently gained significant prominence in applications involving natural language and graph data. A key factor influencing their effectiveness is the efficiency of discretized samplers. Among these, $τ$-leaping samplers have become particularly popular due to their theoretical and empirical success. However, existing theoretical analyses of $τ$-leaping often rely on somewhat restrictive and difficult-to-verify regularity assumptions, and their convergence bounds contain quadratic dependence on the vocabulary size. In this work, we introduce a new analytical approach for discrete diffusion models that removes the need for such assumptions. For the standard $τ$-leaping method, we establish convergence guarantees in KL divergence that scale linearly with vocabulary size, improving upon prior results with quadratic dependence. Our approach is also more broadly applicable: it provides the first convergence guarantees for other widely used samplers, including the Euler method and Tweedie $τ$-leaping. Central to our approach is a novel technique based on differential inequalities, offering a more flexible alternative to the traditional Girsanov change-of-measure methods. This technique may also be of independent interest for the analysis of other stochastic processes.