From Scores to Gibbs Correctors: Accelerating Uniform-Rate Discrete Diffusion Models
2026-05-26 • Machine Learning
Machine Learning
AI summaryⓘ
The authors introduce a new method called GADD to speed up generating samples from discrete diffusion models, which are often slow when using traditional methods. GADD uses a Gibbs-based approach to improve sampling efficiency without needing extra training beyond usual steps. They show mathematically and through experiments that GADD produces better-quality samples faster than standard techniques in tasks like text and music generation. Additionally, the authors provide a new way to analyze these methods, which might help future research.
discrete diffusion modelsGibbs samplingscore functionsampling complexitypredictor-corrector methodsEuler methodCTMC correctorserror propagationpolylogarithmic rate
Authors
Yuchen Liang, Ness Shroff, Yingbin Liang
Abstract
Discrete diffusion models have achieved strong empirical performance in text and other symbolic domains, but, especially for uniform-rate models, they often require many steps to generate a single sample. Existing acceleration methods either rely on training additional quantities or suffer from slow mixing. In this work, we propose a novel Gibbs-based corrector for discrete diffusion models, termed Gibbs-Accelerated Discrete Diffusion (GADD). GADD leverages the structure of the concrete score function to construct Gibbs posterior likelihoods directly, without requiring any additional training beyond standard score estimation. We show that GADD achieves an overall sampling complexity of $\mathcal{O}(\mathrm{polylog} (\varepsilon^{-1}))$, yielding the first such rate for diffusion-based samplers for uniform-rate discrete diffusion models. We also conduct numerical experiments demonstrating the practical advantages of GADD across synthetic data, zero-shot text sampling, and zero-shot conditional music generation. These results corroborate the theory and show that GADD consistently improves sample quality and wall-clock efficiency over standard baselines, including vanilla Euler methods and CTMC correctors. Beyond this, our theoretical analysis introduces a novel framework for analyzing predictor-corrector methods in discrete diffusion models, which may be of independent interest. Unlike existing approaches that rely on the Girsanov change-of-measure technique, our method is based on an induction argument that tracks error propagation across predictor iterations while accounting for inaccuracies in the corrector updates.