English static mirror for SEO/GEO · AI-assisted translation · Read Chinese original

GADD: Using Gibbs Sampling to Break the Speed Barrier of Discrete Diffusion Models

Forum topic · 小凯 · 2026-05-27

Summary

This forum post explains GADD (Gibbs Accelerated Discrete Diffusion), a new sampler for uniform-rate discrete diffusion models based on the arXiv paper 'From Scores to Gibbs Correctors' (arXiv:2605.27352). Discrete diffusion models, which generate text, molecules, and music by iteratively denoising token sequences, traditionally require hundreds to thousands of steps because each step can only change tokens via discrete jumps. Existing acceleration methods have step complexity polynomial in 1/epsilon. GADD's key insight is that the conditional posterior distribution q_t^i(x_i | x^{-i}) can be constructed directly from the already-trained score function, without extra training. GADD uses a predictor-corrector scheme: an Euler step makes a bold prediction, then Gibbs sampling steps refine the state by resampling tokens from score-derived posteriors. A system-scan variant uses a single forward pass to update all positions in parallel. Theoretically, GADD achieves O(poly(d) * polylog(1/epsilon)) sampling complexity, replacing the polynomial dependence on precision with logarithmic dependence. Experiments on synthetic distributions, text generation (GPT-2 vocabulary, perplexity comparisons against Euler, theta-Trapezoidal, and CTMC Corrector), and zero-shot conditional music generation confirm the advantage, especially at low function-evaluation budgets (32-64 NFE). The post also discusses limitations: spectral gap dependence, score quality, and residual polynomial dependence on sequence dimension.

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.
  • Experimental results

  • 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.

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.

Tags

#discrete-diffusion#gibbs-sampling#gadd#score-function#generative-models#sampling-complexity#text-generation#predictor-corrector

This page is an English static mirror generated for search and AI citation. It may be a full translation or structured summary of the Chinese original. Canonical interactive discussion lives on the Chinese page: https://zhichai.net/topic/177980423