Research map / Image generation / Fast diffusion sampling

How Discrete and Continuous Diffusion Meet: Comprehensive Analysis of Discrete Diffusion Models via a Stochastic Integral Framework

ICLR 2025 · Image generation › Fast diffusion sampling · approach: Diffusion theory and design space · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Builds a Lévy-type stochastic integral framework (Poisson random measure with evolving intensity plus change-of-measure) for discrete diffusion models and uses it to derive error bounds for tau-leaping (KL) and uniformization.

Problem

Error analysis of discrete diffusion models is underdeveloped; prior tau-leaping guarantees are in total variation and rely on algorithm-specific and strong assumptions, and there is no discrete analogue of Girsanov's theorem.

Approach

Generalize Poisson random measures to time-inhomogeneous, state-dependent intensities, express discrete diffusion forward/backward processes and tau-leaping/uniformization as stochastic integrals against these measures, and prove a change-of-measure theorem giving KL bounds via likelihood ratios.

Key results

• First KL-divergence error bound for tau-leaping for discrete diffusion models, with N = O(D^2 rho^2 log^2(...)/epsilon) steps, stronger than prior TV results.
• Uniformization achieves expected steps E[N] = O(D log(...)/rho), removing the quadratic truncation-driven dependence present in tau-leaping; for X=[S]^d this gives roughly O~(d) vs O~(d^2) dependence on dimension.
• Change-of-measure theorem for Poisson random measures with evolving intensity recovers the score-entropy loss as the KL divergence between path measures.

Surprising findings

• Uniformization's dimension dependence is conjectured to be optimal at O~(d), matching continuous diffusion, while tau-leaping is quadratic in d.

Limitations

• Analysis restricted to time-homogeneous symmetric rate matrices (time-inhomogeneous by rescaling only); asymmetric cases left to future work.
• Exponential convergence of the forward process requires a modified log-Sobolev constant lower bound that is non-trivial for general graphs.
• Tau-leaping quadratic dimension dependence conjectured to be improvable but not proven.

Experimental setup

Metrics: KL divergence bound number of steps N as function of dimension and epsilon

Baselines: tau-leaping total variation analysis (Chen & Ying 2024) continuous diffusion error bound

Builds on: Girsanov's theorem score entropy tau-leaping uniformization continuous diffusion error analysis (Chen et al. 2023)

Closest papers by meaning

• Convergence of Score-Based Discrete Diffusion Models: A Discrete-Time Analysis (ICLR 2025 · similarity 0.88)
• Lipschitz Singularities in Diffusion Models (ICLR 2024 · similarity 0.88)
• Fast Solvers for Discrete Diffusion Models: Theory and Applications of High-Order Algorithms (NeurIPS 2025 · similarity 0.87)
• Discrete Diffusion Models: Novel Analysis and New Sampler Guarantees (NeurIPS 2025 · similarity 0.87)
• Leveraging Drift to Improve Sample Complexity of Variance Exploding Diffusion Models (NeurIPS 2024 · similarity 0.87)
• O(d/T) Convergence Theory for Diffusion Probabilistic Models under Minimal Assumptions (ICLR 2025 · similarity 0.87)