GADD: Finding the Shortcut in the Discrete Maze with Gibbs Sampling
This post introduces GADD, a new sampling algorithm for uniform-rate discrete diffusion models, based on the paper *"From Scores to Gibbs Correctors: Accelerating Uniform-Rate Discrete Diffusion Models"* (Yuchen Liang, Ness Shroff, Yingbin Liang, arXiv:2605.27352).
Key points
- The problem: Discrete diffusion models (for text, molecules, music notation) must make discrete token jumps with no intermediate states. Uniform-rate models based on continuous-time Markov chains (CTMCs) typically need hundreds to thousands of denoising steps, versus 20–50 steps for continuous image diffusion.
- The complexity gap: All existing acceleration methods (tau-leaping, Euler & Tweedie, DMPM, CTMC Corrector, etc.) have step complexity polynomial in 1/epsilon — e.g., O(d/epsilon^2) or O(d^2/epsilon^2). GADD achieves **O(log^2(d/epsilon^2) / rho*), where epsilon appears only inside a logarithm.
- Core insight: The conditional posterior q_t^i(x_i | x^{-i}) can be constructed directly from the trained score function s_t(y,x), with no additional training, networks, or data. Sampling tokens from these posteriors is exactly Gibbs sampling.
- Algorithm: A predictor-corrector scheme — an Euler step makes a bold prediction, then L_k Gibbs correction steps resample one token at a time from score-derived posteriors. A system-scan variant exploits that one neural forward pass outputs scores for all positions (shape B x d x S), so each Gibbs sweep needs only a single function evaluation.
- Theory**: Unlike CTMC correctors (which suffer discretization error and remain O(d^2 M^2 / (mu*^2 * epsilon^2)) even with perfect scores), GADD's Gibbs corrections are exact in discrete time. An inductive argument combined with exponential Gibbs convergence (controlled by the spectral gap rho*) yields polylog(1/epsilon) complexity for well-structured distributions.
- Synthetic experiments (autoregressive-type and sparse mixture models): GADD achieves lower error than Vanilla Euler and theta-Trapezoidal at equal numbers of function evaluations (NFE), and outperforms pure Gibbs samplers on spiky target distributions thanks to a warm start from the reverse diffusion process.
- Text generation: d=128, GPT-2 vocabulary (S=50257), base model SEDD Uniform, evaluated with GPT-2 perplexity (averaged over 10 runs). At NFE=32, baselines produce perplexities above 300 while GADD already yields coherent text; GADD stays ahead at NFE=64, 128, and 256, with favorable wall-clock time due to system-scan.
- Zero-shot conditional music generation: a text-trained uniform-rate discrete diffusion model generates music symbol sequences without task-specific training, demonstrating GADD's generality.
Experimental results
Why it matters
GADD is the first sampler for uniform-rate discrete diffusion with O(poly(d) * polylog(1/epsilon)) complexity. Combined with the inherent parallelism of diffusion (all tokens denoised jointly), this makes discrete diffusion theoretically competitive with autoregressive models (O(d) steps) for large-scale parallel text generation, molecular design, and code generation.
Limitations
1. Spectral gap dependence: for pathological distributions (low-temperature Ising, strongly multimodal), rho* may be exponentially small. 2. Score quality: GADD relies on accurate score estimation. 3. Residual dimension dependence: O(poly(d)) remains for very long sequences. 4. Masked-diffusion competition: for text specifically, masked diffusion models (e.g., MDLM) may be more practical; GADD's advantage is strongest for uniform-rate models used in graph and molecular generation where masking is unsuitable.
The takeaway: GADD doesn't make computers run faster — it makes the problem easier, turning a polynomial-in-precision step count into a logarithmic one through a hidden capability of a tool everyone already had.
Reference
[3] Yuchen Liang, Ness Shroff, Yingbin Liang. "From Scores to Gibbs Correctors: Accelerating Uniform-Rate Discrete Diffusion Models." arXiv:2605.27352, 2026.