Search papers, labs, and topics across Lattice.
This paper introduces Gibbs-Accelerated Discrete Diffusion (GADD), a novel Gibbs-based corrector for accelerating uniform-rate discrete diffusion models by directly leveraging the concrete score function to construct Gibbs posterior likelihoods. GADD achieves a sampling complexity of $\mathcal{O}(\mathrm{polylog} (\varepsilon^{-1}))$, representing the first such rate for uniform-rate discrete diffusion samplers. Empirical results across synthetic data, text, and music demonstrate that GADD improves sample quality and efficiency compared to standard baselines.
Discrete diffusion models can now generate samples in polylogarithmic time, thanks to a novel Gibbs-based corrector that avoids costly retraining.
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.
