Research map / Optimization / Optimizers
Discrete Diffusion Models: Novel Analysis and New Sampler Guarantees
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.
Gives a differential-inequality analysis of discrete diffusion samplers that drops Girsanov regularity assumptions and yields KL convergence for tau-leaping linear in vocabulary size S, plus the first guarantees for Euler and Tweedie tau-leaping.
Problem
Existing convergence analyses of tau-leaping for discrete diffusion models rely on strong or hard-to-verify regularity assumptions and have quadratic or worse dependence on vocabulary size S; no guarantees exist for Euler and Tweedie tau-leaping samplers.
Approach
Bounds the rate of change of KL divergence between the true reverse process and the sampling process directly via Kolmogorov equations (a differential-inequality argument), giving a step-wise KL decomposition in terms of Bregman divergences of rate matrices, without Girsanov regularity conditions; the same decomposition applies to Euler and Tweedie tau-leaping through an asymptotically equivalent
Key results
- Tau-leaping achieves epsilon KL error with O~(d^2 S / epsilon) steps, improving the quadratic S dependence of prior Girsanov-based analyses by a factor of S.
- Euler method and Tweedie tau-leaping obtain the same O~(d^2 S / epsilon) step complexity as tau-leaping, with per-step sampling cost reduced from O(Sd) to O(d) categorical draws.
- Numerical simulations on a synthetic autoregressive target (d=2 for KL, d=3 and S=8 for TV) are reported to validate the theory.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed τ-leaping convergence analysis instead of the prior disc-sum guarantee | τ-leaping · Discrete diffusion [S]^d, ε-KL accuracy | number of steps: \calO\brc{\frac{d^2 S^2}{\eps}} -> \Tilde{O}\brc{d^2 S / \eps} | Helped |
| Replace τ-leaping with the Euler method | Discrete diffusion sampler · Discrete diffusion [S]^d, ε-KL accuracy | samples per step: \calO(S d) -> \calO(d) | Helped |
| Replace τ-leaping with Tweedie τ-leaping | Discrete diffusion sampler · Discrete diffusion [S]^d, ε-KL accuracy | samples per step: \calO(S d) -> \calO(d) | Helped |
| Replace τ-leaping with the Euler method | Discrete diffusion sampler · Discrete diffusion [S]^d, ε-KL accuracy | number of steps: \Tilde{O}\brc{d^2 S / \eps} -> \Tilde{O}\brc{d^2 S / \eps} | No clear effect |
| Replace τ-leaping with Tweedie τ-leaping | Discrete diffusion sampler · Discrete diffusion [S]^d, ε-KL accuracy | number of steps: \Tilde{O}\brc{d^2 S / \eps} -> \Tilde{O}\brc{d^2 S / \eps} | No clear effect |
Limitations
- Upper bounds carry the assumption of bounded score estimates s in [M^-1, M], with dependence on log M.
- Theory covers only the constant noise schedule and R_base of the form (1/S)11^T - I; extension to general rates is described as possible but not fully developed.
- Numerical validation is limited to small synthetic settings (d=2, 3; S=8).
Experimental setup
Metrics: KL divergence total variation distance iteration complexity
Baselines: uniformization Kolmogorov sampler DMPM tau-leaping analysis of Chen and Ying Girsanov-based tau-leaping analysis
Builds on: Girsanov change-of-measure analysis score-entropy loss tau-leaping differential-inequality analysis of continuous diffusion (Huang et al.)
Closest papers by meaning
- Fast Sampling via Discrete Non-Markov Diffusion Models with Predetermined Transition Time (NeurIPS 2024 · similarity 0.91)
- Breaking AR’s Sampling Bottleneck: Provable Acceleration via Diffusion Language Models (NeurIPS 2025 · similarity 0.90)
- Scalable Discrete Diffusion Samplers: Combinatorial Optimization and Statistical Physics (ICLR 2025 · similarity 0.89)
- Convergence of Score-Based Discrete Diffusion Models: A Discrete-Time Analysis (ICLR 2025 · similarity 0.89)
- Continuous Diffusion Model for Language Modeling (NeurIPS 2025 · similarity 0.89)
- Masked Diffusion Models are Secretly Time-Agnostic Masked Models and Exploit Inaccurate Categorical Sampling (ICLR 2025 · similarity 0.89)
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.