Almost Linear Convergence under Minimal Score Assumptions: Quantized Transition Diffusion

Abstract

Continuous diffusion models have demonstrated remarkable generative performance across diverse domains but are often constrained by the computational cost of simulating reverse Ornstein–Uhlenbeck processes via SDE/ODE solvers. Existing theoretical results typically establish query complexities that scale polynomially with both the dimension d and the error tolerance ϵ (e.g., 𝒪̃(d/ϵ)). This mirrors the limitations of unadjusted Langevin algorithm, where standard first-order score solvers lack access to zeroth-order density information, precluding natural error-correction mechanisms and thus preventing the fast ln(1/ϵ) convergence attainable by Metropolis-adjusted methods. In this paper, we develop an improved generative modeling method by introducing Quantized Transition Diffusion (QTD), a framework that reformulates continuous diffusion into a discrete generation problem through spatial quantization and the parameterization of zeroth-order information (e.g., density ratios). To sample from this discrete target, we propose a truncated uniformization algorithm that simulates the underlying continuous-time Markov chain of the discrete diffusion process without discretization error, while eliminating the restrictive bounded-score assumption required by prior uniformization-based approaches. Consequently, QTD attains ϵ-accuracy in total variation distance with a query complexity of 𝒪(d ln^2(d/ϵ)), yielding a notable improvement in ϵ-dependence compared to existing continuous diffusion samplers. Crucially, our analysis capitalizes on a novel proof technique based on the infinitesimal chain rule of KL divergence, providing a fresh perspective on unifying continuous and discrete diffusion paradigms.