Search papers, labs, and topics across Lattice.
This paper analyzes the sampling efficiency of score-based discrete diffusion models under a continuous-time Markov chain (CTMC) formulation using τ-leaping samplers. It establishes sharp convergence guarantees in KL divergence for uniform and masking noising processes, demonstrating an iteration complexity of $\tilde O(d/\varepsilon)$ for uniform diffusion, improving upon existing bounds. For masking diffusion, the paper introduces a modified τ-leaping sampler whose convergence rate depends on the effective total correlation, enabling adaptation to low-dimensional structure.
Discrete diffusion models can now sample high-dimensional data with provable sublinear convergence rates, adapting to hidden structure without prior knowledge.
Diffusion models over discrete spaces have recently shown striking empirical success, yet their theoretical foundations remain incomplete. In this paper, we study the sampling efficiency of score-based discrete diffusion models under a continuous-time Markov chain (CTMC) formulation, with a focus on $τ$-leaping-based samplers. We establish sharp convergence guarantees for attaining $\varepsilon$ accuracy in Kullback-Leibler (KL) divergence for both uniform and masking noising processes. For uniform discrete diffusion, we show that the $τ$-leaping algorithm achieves an iteration complexity of order $\tilde O(d/\varepsilon)$, with $d$ the ambient dimension of the target distribution, eliminating linear dependence on the vocabulary size $S$ and improving existing bounds by a factor of $d$; moreover, we establish a matching algorithmic lower bound showing that linear dependence on the ambient dimension is unavoidable in general. For masking discrete diffusion, we introduce a modified $τ$-leaping sampler whose convergence rate is governed by an intrinsic information-theoretic quantity, termed the effective total correlation, which is bounded by $d \log S$ but can be sublinear or even constant for structured data. As a consequence, the sampler provably adapts to low-dimensional structure without prior knowledge or algorithmic modification, yielding sublinear convergence rates for various practical examples (such as hidden Markov models, image data, and random graphs). Our analysis requires no boundedness or smoothness assumptions on the score estimator beyond control of the score entropy loss.
CMU ML