GADD: Accelerating Discrete Diffusion Models with Gibbs Sampling to Achieve Polylogarithmic Sampling Complexity

Forum topic · 小凯 · 2026-05-27

Summary

This post explains GADD (Gibbs Accelerated Discrete Diffusion), a sampler for uniform-rate discrete diffusion models that reduces the number of sampling steps from polynomial in 1/epsilon to polylogarithmic. The article first introduces why discrete diffusion (text, molecules, music) is slow: tokens cannot be perturbed continuously, so each step is a hard replacement, and vanilla Euler samplers on continuous-time Markov chains need hundreds to thousands of steps with complexity O(poly(epsilon^-1)). GADD's key insight is that the conditional posterior q_t^i(x_i | x^{-i}) over each token can be constructed directly from the already-trained score function, without extra training, enabling Gibbs-sampling corrector steps inside a predictor-corrector loop. A system-scan variant uses one forward pass per Gibbs sweep across all positions. Theoretically, exploiting exponential convergence of Gibbs sampling (spectral gap), GADD achieves total complexity O(log^2(d/epsilon^2)/rho*), versus polynomial-in-1/epsilon bounds for Euler, tau-leaping, and CTMC-corrector baselines. Experiments on synthetic distributions and GPT-2 perplexity evaluation with SEDD (d=128, vocabulary 50257) show GADD outperforming baselines especially at low numbers of function evaluations (NFE=32-64), plus zero-shot conditional music generation. Limitations include dependence on the spectral gap, score quality, and residual polynomial dimension dependence.

Overview

This forum post explains GADD (Gibbs Accelerated Discrete Diffusion), based on the paper *"From Scores to Gibbs Correctors: Accelerating Uniform-Rate Discrete Diffusion Models"* (arXiv:2605.27352, 2026). GADD accelerates uniform-rate discrete diffusion sampling to O(polylog(ε⁻¹)) steps — the first method to break the polynomial-in-1/ε barrier.

Key points

Why discrete diffusion is slow: Unlike images (continuous pixel values), text tokens cannot be "slightly adjusted" — every step is a hard replacement from a vocabulary of size S (e.g., 50257 for GPT-2). Uniform-rate discrete diffusion models model this with continuous-time Markov chains (CTMCs), where each token is independently replaced at rate 1/S, requiring hundreds to thousands of denoising steps.
The complexity gap: Existing samplers (Euler/Tweedie, τ-leaping, CTMC Corrector, θ-RK-2) all have step complexity with ε as a polynomial denominator, e.g. O(d/ε²) or O(d²/ε²). GADD achieves:

N = \tilde{O}\left(\frac{\log^2(d/\varepsilon^2)}{\rho^*}\right)

so improving precision by 10× costs only a logarithmic factor instead of a polynomial one.

Core insight: The score function s_t(y,x) ≈ q_t(y)/q_t(x), already trained, contains enough information to reconstruct the conditional posterior q_t^i(x_i | x^{-i}) over each token — no additional training, networks, or loss functions needed:

\hat{q}_t^i(x_i \mid x^{-i}) = \left(\sum_{y_i \in [S]} s_t(x^{-i} \oplus_i y_i,\, x)\right)^{-1}

Algorithm: GADD is a Predictor–Corrector scheme. The predictor is a bold Euler step; the corrector runs L_k Gibbs steps, resampling one (or, in the system-scan variant, all) positions from posteriors built from a single score-network forward pass. Unlike the CTMC Corrector, which discretizes a continuous process (inherently O(ε⁻²) even with perfect scores), Gibbs sampling is an exact discrete-time algorithm with exponential convergence governed by the spectral gap ρ.
Theory: An induction argument (rather than Girsanov) bounds the TV error per step. With well-structured targets (spectral gap ρ* = Ω(poly⁻¹(d))), total complexity is O(poly(d)·polylog(ε⁻¹)) — polynomial in d but only logarithmic in 1/ε.

Experiments

Synthetic data (autoregressive-like and sparse mixture distributions): GADD reaches lower final error than Vanilla Euler and θ-Trapezoidal at equal NFE, matching theory. GADD beats pure Gibbs sampling on spiky targets thanks to a warm start from the reverse diffusion trajectory.
Text generation (SEDD Uniform base, d=128, GPT-2 vocab 50257, evaluated by GPT-2 perplexity over 10 runs):

| Method | NFE=32 | NFE=64 | NFE=128 | |:---|:---|:---|:---| | Vanilla Euler | 356.03 | 285.17 | 283.03 | | θ-Trapezoidal | 325.91 | 267.70 | 255.20 | | CTMC Corrector | 378.10 | 272.65 | 227.68 | | GADD | best | best | best |

GADD's advantage is largest at low NFE (32–64) and also wins in wall-clock time due to the one-forward-pass-per-sweep system-scan variant.

Zero-shot conditional music generation: Using a text-trained model without music-specific training, demonstrating GADD's domain generality.

Limitations noted by the author

1. Dependence on the spectral gap ρ* — pathological (low-temperature, strongly multimodal) distributions may degrade efficiency. 2. Sensitivity to score-function quality. 3. Residual polynomial dependence on sequence length d. 4. Masked diffusion models (e.g., MDLM) may remain more practical for text; GADD shines mainly for uniform-rate settings like molecule and graph generation where masking is not natural.

Takeaway

GADD's significance is framed as a paradigm shift: discrete diffusion models can now, in theory, approach autoregressive models' efficiency while retaining parallel token update capability — an "insight victory" of reusing an existing score network in a new way, not a compute victory.

Reference

[3] Yuchen Liang, Ness Shroff, Yingbin Liang. *"From Scores to Gibbs Correctors: Accelerating Uniform-Rate Discrete Diffusion Models."* arXiv:2605.27352, 2026.