Efficient Sampling with Discrete Diffusion Models: Sharp and Adaptive Guarantees

Daniil Dmitriev; Zhihan Huang; Yuting Wei

cs.LGFeb 16, 2026

Efficient Sampling with Discrete Diffusion Models: Sharp and Adaptive Guarantees

Authors: Daniil Dmitriev, Zhihan Huang, Yuting Wei

Organizations: Department of Statistics and Data Science, the Wharton School, University of Pennsylvania

Abstract

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.

Explore similar work

Jan 22, 2025stat.ML

Low-dimensional adaptation of diffusion models: Convergence in total variation

This paper investigates how diffusion generative models leverage (unknown) low-dimensional structure to accelerate sampling. Focusing on two mainstream samplers -- the denoising diffusion implicit model (DDIM) and the denoising diffusion probabilistic model (DDPM), we prove that their iteration complexities under exact score functions are at most the order of

k/\varepsilon

(up to log factor), where

\varepsilon

is the precision in total variation distance and

k

is some intrinsic dimension of the target distribution. We further extend these convergence guarantees to the setting in which the score functions are learned from data rather than known exactly, showing that the convergence performance degrades gracefully under suitable score estimation assumptions. We then show that these assumptions are attainable via kernel-based score estimators with finite-sample guarantees that also adapt to the low-dimensional structure. Our results apply to a broad family of target distributions without requiring smoothness or log-concavity. Our findings provide the first rigorous evidence for the adaptivity of the DDIM-type samplers to unknown low-dimensional structure, and improve over the state-of-the-art DDPM theory regarding total variation convergence.

Jiadong Liang, Zhihan Huang, Yuxin Chen

Score-Based Diffusion Model Denoising Diffusion Probabilistic Model Generative Models Low-Dimensional Structure Low-Rank Adaptation Convergence

Ask PDF

Jul 1, 2026cs.LG

Accelerating Discrete Diffusion Models with Parallel-In-Time Sampling

Discrete diffusion models are widely used for learning and generating discrete distributions. As the generation process is inherently sequential, the acceleration of sampling is of significant importance. In this work, we parallelize the mainstream

τ

-leaping algorithm for absorbing discrete diffusion in a Continuous-Time Markov Chain (CTMC) framework. By leveraging the continuous-time stochastic integral form of the

τ

-leaping algorithm and the Picard iteration method, we achieve parallel-in-time sampling acceleration and provide a proof of exponential-factorial convergence for our algorithm. We improve the overall time complexity of

τ

-leaping under absorbing settings from

{\mathcal{O}}(d \log S)

{\mathcal{O}}(\log (d\log S)\cdot \log d)

with respect to NFE. Empirically, our method shows consistent acceleration across synthetic and real-data settings. The new sampler achieves at most

7

9\times

runtime speedup for synthetic distribution, and maintains the same quality with

50\%

fewer NFE and

1.45

1.86\times

runtime speedups in image/text tasks on a single GPU. Our research expands the potential of discrete diffusion models for efficient parallel inference, with broader implications for applications such as molecular structure and language generation.

Yu Yao, Huanjian Zhou, Andi Han +2

Discrete Diffusion Model Parallel Markov

Ask PDF

May 8, 2026cs.LG

When Diffusion Model Can Ignore Dimension: An Entropy-Based Theory

Diffusion models perform remarkably well on high-dimensional data such as images, often using only a modest number of reverse-time steps. Despite this practical success, existing convergence theory does not fully explain why such samplers remain efficient in high dimensions. Many prior KL guarantees bound the discretization error in terms of the ambient dimension, while other improved results replace this dependence using intrinsic-dimensional or geometric structure assumptions. In this work, we develop an alternative information-theoretic perspective on diffusion sampler convergence. We prove that, for Gaussian mixture targets, the discretization error is controlled by the Shannon entropy of the latent mixture component rather than by the ambient dimension. Consequently, the leading step complexity scales linearly with latent entropy and depends only logarithmically on the second moment of the data. Our analysis also extends to discrete target distributions, where the relevant complexity is the entropy of the target rather than the dimension of the embedding space. These results suggest that diffusion sampling can remain efficient in high-dimensional spaces when the data distribution admits a compact latent representation, as is widely believed to be the case for natural images.

Ahmad Aghapour, Erhan Bayraktar

Diffusion Sampling High-Dimensional Data Gaussian Mixture Models Information-Theoretic Limits Theoretical Foundations

Ask PDF