cs.LGMay 17, 2026

Vocabulary-size-independent Convergence of Discrete Diffusion Models: adjoint equations induce the right space

Authors: Kelvin Kan, Xingjian Li, Benjamin J. Zhang, Tuhin Sahai, Stanley Osher, Markos A. Katsoulakis

Abstract

Discrete diffusion has become a leading framework for generative modeling in various applications including language, vision, and biology. Existing convergence theory, however, exhibits fundamental limitations. KL-based analyses diverge under singular priors such as the masked distribution, while bounds in total variation (TV) depend on the vocabulary size SS and become vacuous for modern language tasks, where vocabularies contain hundreds of thousands of tokens. We develop a unified adjoint-equation-based framework that establishes vocabulary-size-independent convergence guarantees in any integral probability metric (IPM). To the best of our knowledge, our bounds are the first to be entirely free of SS and applicable to both masked and uniform priors. Importantly, our results can extend existing step complexity guarantees to any IPM. Also, our theory relies only on a single standard rate-matrix regularity assumption and applies to general priors. Five novel techniques drive our improvements: 1. working in the space of observables via adjoint equations rather than directly with probability measures; 2. a regularity analysis that yields bounds on any IPM; 3. a coupling argument that removes SS-dependence under uniform transitions; and 4. score-marginal cancellation and 5. exit-routing techniques that remove SS-dependence under masked transitions. Our framework thus sharply departs from prior analyses and avoids the shortcomings of pathspace-KL and existing TV-based approaches. Beyond convergence bounds, our framework provides a versatile toolkit for further theoretical study of discrete diffusion models, including principled choices of loss functions and vocabulary-size-independent step complexity.

Explore similar work

CardsList
Feb 16, 2026cs.LG

Efficient Sampling with Discrete Diffusion Models: Sharp and Adaptive Guarantees

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 O~(d/ε)\tilde O(d/\varepsilon), with dd the ambient dimension of the target distribution, eliminating linear dependence on the vocabulary size SS and improving existing bounds by a factor of dd; 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 dlog⁡Sd \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.
Daniil Dmitriev, Zhihan Huang, Yuting Wei
Score-Based Diffusion ModelDiscrete Diffusion ModelKullback-Leibler DivergenceMarkov
AskPDF
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/εk/\varepsilon (up to log factor), where ε\varepsilon is the precision in total variation distance and kk 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 ModelDenoising Diffusion Probabilistic ModelGenerative ModelsLow-Dimensional StructureLow-Rank AdaptationConvergence
AskPDF
Jun 15, 2026stat.ML

Diffusion Flow Matching: Dimension-Improved KL Bounds and Wasserstein Guarantees

Diffusion Flow Matching (DFM) has recently emerged as a versatile framework for generative modeling, yet its theoretical convergence properties remain only partially understood. In this work, we provide refined and novel convergence guarantees for Brownian motion based DFMs, focusing on the discretization error. Our analysis is conducted under the Kullback-Leibler (KL) divergence and the 2-Wasserstein distance. Under finite-moment conditions and a mild score integrability assumption, we derive KL convergence bounds with improved dimensional dependence compared to prior work, achieving, up to our knowledge, state-of-the-art scaling under minimal conditions. We further extend the analysis to the 2-Wasserstein distance: under an additional first-order score integrability assumption and a weak log-concavity condition, we obtain convergence guarantees with dimensional dependence consistent with the KL case.
Marta Gentiloni Silveri, Giovanni Conforti, Alain Durmus
Wasserstein Gradient FlowsGenerative ModelsStochastic Differential EquationsKullback-Leibler Divergence
AskPDF