Technical Summary: From Scores to Gibbs Correctors (GADD)

Problem Statement

Discrete diffusion models have demonstrated strong empirical performance in symbolic domains such as text, graphs, and molecular design. However, a significant bottleneck remains in generation efficiency, particularly for uniform-rate discrete diffusion models. Unlike masked (absorbing-rate) models, which possess a structure allowing for analytic sampling times, uniform-rate models lack such salient structure. Existing acceleration methods for uniform-rate models typically rely on training additional quantities or suffer from slow mixing, resulting in sampling complexities that scale polynomially with the inverse of the target accuracy, $\varepsilon$ (i.e., $O(\text{poly}(\varepsilon^{-1}))$).

The central question addressed by this work is whether it is possible to break the $O(\text{poly}(\varepsilon^{-1}))$ barrier and achieve a logarithmic dependence, specifically $O(\text{polylog}(\varepsilon^{-1}))$, for uniform-rate discrete diffusion models.

Methodology: Gibbs-Accelerated Discrete Diffusion (GADD)

The authors propose a novel algorithm, Gibbs-Accelerated Discrete Diffusion (GADD), which integrates a Gibbs-based corrector into the standard predictor-corrector framework for discrete diffusion.

Core Mechanism

1. Predictor-Corrector Structure: The algorithm operates in an outer loop that discretizes the reverse diffusion process. At each step $t_k$, an Euler update (predictor) generates a candidate state. This is followed by an inner loop of $L_k$ Gibbs sampling steps (corrector) targeting the distribution at $t_k$.
2. Score-Based Posterior Construction: A key innovation is the construction of the Gibbs posterior likelihoods directly from the existing concrete score function (the density ratio between Hamming-distance-1 pairs).
   • The posterior probability $q_t^i(x_i | x_{-i})$ is estimated using the score estimator $s_t$ without requiring any additional training or auxiliary estimators.
   • Specifically, the estimator is defined as $\hat{q}_t^i(x_i|x_{-i}) = \left(\sum_{y_i \in [S]} s_t(x_{-i} \oplus_i y_i, x)\right)^{-1}$.
   • This approach avoids the computational and memory overhead of Metropolis-Hastings correctors, which typically require estimating likelihood ratios for all pairs of states.
3. Warm-Start Condition: The diffusion process naturally provides a "warm start" for the Gibbs sampler. Because the predictor step moves the state close to the target distribution $q_{t_k}$, the Gibbs corrector requires fewer iterations to converge, and the error from inaccurate score estimation is mitigated.

Theoretical Framework

The paper introduces a new analytical framework for predictor-corrector methods in discrete diffusion that differs from the Girsanov change-of-measure technique used in continuous settings. Instead, it employs an induction argument that tracks error propagation across predictor iterations while explicitly accounting for inaccuracies in the corrector updates. The error is decomposed into:

• Initialization error (outer loop).
• Mixing error (inner loop Gibbs convergence).
• Estimation error (score approximation).

Key Contributions

1. Algorithmic Design (GADD): The proposal of the first uniform-rate discrete diffusion sampler that achieves an $O(\text{polylog}(\varepsilon^{-1}))$ convergence rate. The algorithm leverages the concrete score function to construct Gibbs updates without extra training.
2. Theoretical Guarantees:
   • Convergence Rate: The authors prove that GADD achieves a total sampling complexity of $O(\text{polylog}(\varepsilon^{-1}))$, a significant improvement over the $O(\text{poly}(\varepsilon^{-1}))$ rates of existing methods (e.g., Euler, $\tau$-leaping, and higher-order solvers).
   • Spectral Gap Dependence: For well-structured distributions where the spectral gap $\rho^*$ scales as $\Omega(d^{-1})$, the total steps scale as $O(\text{poly}(d) \cdot \text{polylog}(\varepsilon^{-1}))$.
   • Warm-Start Analysis: Theoretical demonstration that the diffusion process reduces both the Gibbs convergence error and the error from score estimation inaccuracies.
3. General Framework for Analysis: The development of an inductive framework for analyzing predictor-corrector methods that handles inaccurate corrector updates. This framework is shown to be applicable not only to GADD but also to existing CTMC correctors, providing a unified view of their convergence.
4. Comparative Analysis of CTMC Correctors: The paper provides a theoretical analysis showing that CTMC-based correctors (even with perfect scores) are limited to $O(\text{poly}(\varepsilon^{-1}))$ complexity due to discretization errors, highlighting the superiority of the Gibbs-based approach.

Experimental Results

The authors validate GADD through numerical experiments across three domains:

1. Synthetic Data: GADD achieves substantially lower final error compared to Euler, $\theta$-Trapezoidal, and vanilla Gibbs samplers at the same number of function evaluations (NFEs). It performs particularly well on "spiky" target distributions where vanilla Gibbs samplers suffer from poor mixing.
2. Zero-Shot Text Sampling: Evaluated on the WikiText103 dataset, GADD consistently outperforms baselines (Euler, $\theta$-Trapezoidal, CTMC corrector) in generative perplexity. Notably, it achieves superior wall-clock efficiency because random-scan Gibbs updates only modify a single token per iteration, whereas Euler updates all tokens simultaneously.
3. Zero-Shot Conditional Music Generation: Using the Lakh pianoroll dataset, GADD improves generation quality across Hellinger distance, perplexity, and next-token prediction error metrics. The results indicate that moderate correction steps ($L$) yield significant gains, though performance may saturate or degrade with excessive steps due to stale correctors.

Significance and Claims

The paper claims to provide the first uniform-rate discrete diffusion-based sampler with a provable $O(\text{polylog}(\varepsilon^{-1}))$ convergence rate. The significance of this work lies in:

• Breaking the Polynomial Barrier: It demonstrates that the $O(\text{poly}(\varepsilon^{-1}))$ barrier for uniform-rate models is not fundamental but can be overcome by leveraging the specific structure of the score function to enable efficient Gibbs corrections.
• Efficiency without Retraining: The method accelerates sampling using only the standard score estimator, requiring no additional training or complex auxiliary networks.
• Theoretical Insight: The proposed inductive analysis framework offers a new tool for understanding error propagation in discrete predictor-corrector schemes, which may be of independent interest for future research in discrete generative modeling.

The authors conclude that GADD offers a practical and theoretically grounded approach to accelerating discrete diffusion, achieving superior sample quality and wall-clock efficiency over standard baselines.