Research map / Learning theory and algorithms / Sample complexity
Absorb and Converge: Provable Convergence Guarantee for Absorbing Discrete Diffusion Models
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.
Provides the first finite-time convergence analysis for absorbing-rate discrete diffusion models, covering tau-leaping and uniformization samplers with and without early stopping.
Problem
Convergence guarantees and error bounds for discrete diffusion models with absorbing rate matrices are missing; existing theory covers only uniform rate matrices, where the absorbing stationary distribution is a singleton that makes KL divergence ill-defined.
Approach
Uses a surrogate initialization distribution near the absorbing singleton, a Jensen-based bound on forward-process KL (instead of log-Sobolev), and tight score upper/lower bounds exploiting that only mask-transitions have positive rate, yielding O(d/eps) tau-leaping steps and O(d log log(d/eps)) expected uniformization steps.
Key results
- Under absorbing rates, tau-leaping achieves KL accuracy eps with O~(d/eps) steps versus O~(d^2/eps) for uniform rates.
- Uniformization with absorbing rates needs expected O(d(log log(d/eps) + log delta^-1)) steps, improving on O(d(log(d/eps)+log delta^-1)) for uniform rates.
- Without early stopping, under a mask-frequency assumption with constant gamma, tau-leaping needs O~(d gamma^-1/eps) steps and uniformization needs E[N]=O(d(log log(d/eps)+gamma^-1)).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use an absorbing rather than uniform rate matrix | τ-leaping with early-stopping · Discrete diffusion, early-stopping | steps for ε KL-divergence accuracy: \widetilde{\calO}(d^2 / \eps) -> \widetilde{\calO}(d / \eps) | Helped |
| Use an absorbing rather than uniform rate matrix | Uniformization with early-stopping · Discrete diffusion, early-stopping | expected steps for ε KL-divergence accuracy: \calO(d (\log (d/\eps) + \log \delta^{-1})) -> \calO(d (\log \log (d/\eps) + \log \delta^{-1})) | Helped |
| Use an absorbing rather than uniform rate matrix | τ-leaping without early-stopping · Discrete diffusion, without early-stopping | steps for ε KL-divergence accuracy: \widetilde{\calO}(d^2 / \eps) -> \widetilde{\calO}(d \gamma^{-2}/ \eps) | Helped |
| Use an absorbing rate rather than a uniform rate matrix | Uniformization without early-stopping · Discrete diffusion, without early-stopping | expected steps for ε KL-divergence accuracy: N/A -> \mathrm{Pois}\Big(\calO\big(d \log \log(d/\eps) + d \gamma^{-1})\Big) | Helped |
Surprising findings
- The score for absorbing CTMCs decays as t^-1 for large t, unlike uniform rates where it is asymptotically constant, which lowers uniformization intensity.
Limitations
- Assumes bounded score estimates (log M) and score-estimation error assumptions; no experiments.
- Absence of early stopping requires a mask-frequency assumption (constant gamma) on the data distribution.
- Analysis covers unconditional generation only; conditional generation is left to future work.
Experimental setup
Metrics: KL divergence total variation distance expected number of steps
Baselines: uniform-rate tau-leaping analysis (Chen & Ying 2024) uniform-rate uniformization analysis
Builds on: tau-leaping uniformization score entropy Girsanov-based KL analysis for diffusion
Closest papers by meaning
- Convergence of Score-Based Discrete Diffusion Models: A Discrete-Time Analysis (ICLR 2025 · similarity 0.90)
- Towards Non-Asymptotic Convergence for Diffusion-Based Generative Models (ICLR 2024 · similarity 0.89)
- Your Absorbing Discrete Diffusion Secretly Models the Conditional Distributions of Clean Data (ICLR 2025 · similarity 0.89)
- O(d/T) Convergence Theory for Diffusion Probabilistic Models under Minimal Assumptions (ICLR 2025 · similarity 0.89)
- Fast Solvers for Discrete Diffusion Models: Theory and Applications of High-Order Algorithms (NeurIPS 2025 · similarity 0.89)
- Discrete Diffusion Models: Novel Analysis and New Sampler Guarantees (NeurIPS 2025 · similarity 0.88)
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.