# Almost Linear Convergence under Minimal Score Assumptions: Quantized Transition Diffusion

arXiv: https://arxiv.org/abs/2505.21892 · HTML: https://mlsanity.com/paper/2505.21892/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Placed in Diffusion foundations and sampling, one of 14 directions in Diffusion models.
- Builds on 28 of its 32 references that are in the map.
- First posted on arXiv 28 May 2025.

## Placed in

- Diffusion models / [Diffusion foundations and sampling](https://mlsanity.com/diffusion/diffusion-foundations-and-sampling/)

## Builds on (most cited first, 28 of 28)

- [Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2006.11239/) (2020)
- [High-Resolution Image Synthesis with Latent Diffusion Models](https://mlsanity.com/paper/2112.10752/) (2021)
- [Deep Unsupervised Learning using Nonequilibrium Thermodynamics](https://mlsanity.com/paper/1503.03585/) (2015)
- [Generative Modeling by Estimating Gradients of the Data Distribution](https://mlsanity.com/paper/1907.05600/) (2019)
- [Improved Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2102.09672/) (2021)
- [Video Diffusion Models](https://mlsanity.com/paper/2204.03458/) (2022)
- [DiffWave: A Versatile Diffusion Model for Audio Synthesis](https://mlsanity.com/paper/2009.09761/) (2020)
- [Cascaded Diffusion Models for High Fidelity Image Generation](https://mlsanity.com/paper/2106.15282/) (2021)
- [Discrete Diffusion Modeling by Estimating the Ratios of the Data Distribution](https://mlsanity.com/paper/2310.16834/) (2023)
- [A Continuous Time Framework for Discrete Denoising Models](https://mlsanity.com/paper/2205.14987/) (2022)
- [Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions](https://mlsanity.com/paper/2209.11215/) (2022)
- [Grad-TTS: A Diffusion Probabilistic Model for Text-to-Speech](https://mlsanity.com/paper/2105.06337/) (2021)
- [Diffusion Probabilistic Modeling for Video Generation](https://mlsanity.com/paper/2203.09481/) (2022)
- [Diffusion probabilistic modeling of protein backbones in 3D for the motif-scaffolding problem](https://mlsanity.com/paper/2206.04119/) (2022)
- [Nearly d-Linear Convergence Bounds for Diffusion Models via Stochastic Localization](https://mlsanity.com/paper/2308.03686/) (2023)
- [Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Suffices](https://mlsanity.com/paper/1903.08568/) (2019)
- [Improved Analysis of Score-based Generative Modeling: User-Friendly Bounds under Minimal Smoothness Assumptions](https://mlsanity.com/paper/2211.01916/) (2022)
- [Concrete Score Matching: Generalized Score Matching for Discrete Data](https://mlsanity.com/paper/2211.00802/) (2022)
- [From Denoising Diffusions to Denoising Markov Models](https://mlsanity.com/paper/2211.03595/) (2022)
- [O(d/T) Convergence Theory for Diffusion Probabilistic Models under Minimal Assumptions](https://mlsanity.com/paper/2409.18959/) (2024)
- [Probability flow solution of the Fokker-Planck equation](https://mlsanity.com/paper/2206.04642/) (2022)
- [Fast Solvers for Discrete Diffusion Models: Theory and Applications of High-Order Algorithms](https://mlsanity.com/paper/2502.00234/) (2025)
- [Convergence Analysis of Discrete Diffusion Model: Exact Implementation through Uniformization](https://mlsanity.com/paper/2402.08095/) (2024)
- [Provable Acceleration for Diffusion Models under Minimal Assumptions](https://mlsanity.com/paper/2410.23285/) (2024)
- [Convergence of Score-Based Discrete Diffusion Models: A Discrete-Time Analysis](https://mlsanity.com/paper/2410.02321/) (2024)
- [Reverse Transition Kernel: A Flexible Framework to Accelerate Diffusion Inference](https://mlsanity.com/paper/2405.16387/) (2024)
- [ArchiSound: Audio Generation with Diffusion](https://mlsanity.com/paper/2301.13267/) (2023)
- [Diffusion Models in Bioinformatics: A New Wave of Deep Learning Revolution in Action](https://mlsanity.com/paper/2302.10907/) (2023)

## Built on by (most cited first, 6 of 6)

- [Discrete Diffusion Models: Novel Analysis and New Sampler Guarantees](https://mlsanity.com/paper/2509.16756/) (2025)
- [High-accuracy sampling for diffusion models and log-concave distributions](https://mlsanity.com/paper/2602.01338/) (2026)
- [Demystifying MaskGIT Sampler and Beyond: Adaptive Order Selection in Masked Diffusion](https://mlsanity.com/paper/2510.04525/) (2025)
- [Sharp Convergence Rates for Masked Diffusion Models](https://mlsanity.com/paper/2602.22505/) (2026)
- [Corrected Samplers for Discrete Flow Models](https://mlsanity.com/paper/2601.22519/) (2026)
- [On the ε-Free Inference Complexity of Absorbing Discrete Diffusion](https://mlsanity.com/paper/2509.21835/) (2025)

## Abstract (arXiv)

Continuous diffusion models have demonstrated remarkable performance in data generation across various domains, yet their efficiency remains constrained by two critical limitations: (1) the local adjacency structure of the forward Markov process, which restricts long-range transitions in the data space, and (2) inherent biases introduced during the simulation of time-inhomogeneous reverse denoising processes. To address these challenges, we propose Quantized Transition Diffusion (QTD), a novel approach that integrates data quantization with discrete diffusion dynamics. Our method first transforms the continuous data distribution p_* into a discrete one q_* via histogram approximation and binary encoding, enabling efficient representation in a structured discrete latent space. We then design a continuous-time Markov chain (CTMC) with Hamming distance-based transitions as the forward process, which inherently supports long-range movements in the original data space. For reverse-time sampling, we introduce a textittruncated uniformization technique to simulate the reverse CTMC, which can provably provide unbiased generation from q_* under minimal score assumptions. Through a novel KL dynamic analysis of the reverse CTMC, we prove that QTD can generate samples with O(dln2(d/ε)) score evaluations in expectation to approximate the d--dimensional target distribution p_* within an ε error tolerance. Our method not only establishes state-of-the-art inference efficiency but also advances the theoretical foundations of diffusion-based generative modeling by unifying discrete and continuous diffusion paradigms.