Research map / Image generation / Fast diffusion sampling
Convergence of Score-Based Discrete Diffusion Models: A Discrete-Time Analysis
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.
Analyzes a discrete-time sampler for score-based discrete diffusion (CTMC with uniform rates on [S]^d) and gives KL and TV convergence bounds, with and without early stopping, nearly linear in dimension d.
Problem
Convergence theory for score-based discrete diffusion models in the CTMC framework over high-dimensional state spaces [S]^d is largely missing; existing analyses are restricted to the hypercube and use exact uniformization at random times.
Approach
A discrete-time sampler that freezes the rate matrix on fixed grid points and uses score estimators at predefined times, analyzed via a Girsanov-based path-measure argument with a discrete score movement bound; yields KL bounds nearly linear in d for the uniform forward rate on [S]^d.
Key results
- Without early stopping, KL(q_0 || p_T) is bounded by de^{-T} log S + C_2 kappa^2 S^2 h^2 T + C_2^2 epsilon_score, nearly linear in d.
- With early stopping delta = O~(S^{-2/3}), the iteration complexity is O~(max{(C_1 S^2 d/eps)^{1/3}/delta, (C_1 S^2 d/eps)^{1/2}}) steps for KL = O~(eps + C_1^2 eps_score).
- The forward marginal satisfies KL(q_t || pi^d) <= e^{-t} d log S via a modified log-Sobolev inequality with constant 2.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| discretize the reverse CTMC in time and use score estimates at fixed points | Score-based discrete diffusion in [S]^d · [S]^d, early stopping | KL divergence bound: de^{-T}\log S+\delta^{-3}C_1 S^2h^3 d+C_1 S^2 h^2 dT+C_1^2{\epsilon}_\mathrm{score} | Mixed |
| remove early stopping, assuming full support and a uniformly bounded data score (ablation) | Score-based discrete diffusion in [S]^d · [S]^d, no early stopping | KL divergence bound: de^{-T}\log S+C_2 S^2 h^2 \kappa^2 T+C_2^2{\epsilon} | Helped |
| use a smaller time step h | Discrete-time score-based diffusion · [S]^d | KL divergence bound: C_1 S^2 h^2 dT | Helped |
| use score clipping to bound the score estimator | Discrete-time score-based diffusion · [S]^d | KL divergence bound: C_1 =\frac{3S}{\delta}; C_2 =\frac{3}{2}L | Helped |
Surprising findings
- The KL bound without early stopping is tighter than with early stopping when the data distribution is balanced.
Limitations
- Discretization error becomes significant when delta is small or the data distribution has extreme probability values.
- Analysis is restricted to the uniform forward rate matrix.
- Assumes a uniform bound L on the data score that does not depend on d, which is strong.
Experimental setup
Metrics: KL divergence total variation distance
Baselines: Lou et al. score entropy discrete diffusion (uniformization-based bound) tau-leaping error bound
Builds on: Discrete Denoising Diffusion Probabilistic Models score entropy Girsanov-based convergence analysis for SDE diffusion models uniformization of CTMC
Closest papers by meaning
- O(d/T) Convergence Theory for Diffusion Probabilistic Models under Minimal Assumptions (ICLR 2025 · similarity 0.92)
- Unified Convergence Analysis for Score-Based Diffusion Models with Deterministic Samplers (ICLR 2025 · similarity 0.91)
- Accelerating Convergence of Score-Based Diffusion Models, Provably (ICML 2024 · similarity 0.91)
- Minimax Optimality of Score-based Diffusion Models: Beyond the Density Lower Bound Assumptions (ICML 2024 · similarity 0.91)
- Absorb and Converge: Provable Convergence Guarantee for Absorbing Discrete Diffusion Models (NeurIPS 2025 · similarity 0.90)
- Target Concrete Score Matching: A Holistic Framework for Discrete Diffusion (ICML 2025 · similarity 0.90)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.