From Scores to Gibbs Correctors: Accelerating Uniform-Rate Discrete Diffusion Models

• URL: http://arxiv.org/abs/2605.27352v1
• Date: Tue, 26 May 2026 17:52:28 GMT
• Title: From Scores to Gibbs Correctors: Accelerating Uniform-Rate Discrete Diffusion Models
• Abstract summary: We propose a novel Gibbs-based corrector for discrete diffusion models, termed Gibbs-Accelerated Discrete Diffusion (GADD)<n>We show GADD achieves an overall sampling complexity of $mathcalO(mathrmpolylog (varepsilon-1)$, yielding the first such rate for diffusion-based samplers for uniform-rate discrete diffusion models.
• Score: 58.02657021435213
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Sharp Convergence Rates for Masked Diffusion Models [53.117058231393834]
  We develop a total-variation based analysis for the Euler method that overcomes limitations.<n>Our results relax assumptions on score estimation, improve parameter dependencies, and establish convergence guarantees.<n>Overall, our analysis introduces a direct TV-based error decomposition along the CTMC trajectory and a decoupling-based path-wise analysis for FHS.
  arXiv  Detail & Related papers  (2026-02-26T00:47:51Z)
• Efficient Sampling with Discrete Diffusion Models: Sharp and Adaptive Guarantees [9.180350432640912]
  We study the sampling efficiency of score-based discrete diffusion models under a continuous-time Markov chain (CTMC) formulation.<n>For uniform discrete diffusion, we show that the $$-leaping algorithm achieves an complexity of order $tilde O(d/varepsilon)$.<n>For masking discrete diffusion, we introduce a modified $$-leaping sampler whose convergence rate is governed by an intrinsic information-theoretic quantity.
  arXiv  Detail & Related papers  (2026-02-16T18:48:17Z)
• Inference-Time Scaling of Diffusion Language Models with Particle Gibbs Sampling [70.8832906871441]
  We study how to steer generation toward desired rewards without retraining the models.<n>Prior methods typically resample or filter within a single denoising trajectory, optimizing rewards step-by-step without trajectory-level refinement.<n>We introduce particle Gibbs sampling for diffusion language models (PG-DLM), a novel inference-time algorithm enabling trajectory-level refinement while preserving generation perplexity.
  arXiv  Detail & Related papers  (2025-07-11T08:00:47Z)
• Training-Free Stein Diffusion Guidance: Posterior Correction for Sampling Beyond High-Density Regions [46.59494117137471]
  Training free diffusion guidance provides a flexible way to leverage off-the-shelf classifiers without additional training.<n>We introduce Stein Diffusion Guidance (SDG), a novel training-free framework grounded in a surrogate SOC objective.<n>Experiments on molecular low-density sampling tasks suggest that SDG consistently surpasses standard training-free guidance methods.
  arXiv  Detail & Related papers  (2025-07-07T21:14:27Z)
• A Simple Analysis of Discretization Error in Diffusion Models [3.6042771517920724]
  Diffusion models, formulated as discretizations of differential equations (SDEs), achieve state-of-the-art generative performance.<n>We present a simplified theoretical framework for analyzing the the-preserving-Maruyama discretization of variance-preserving SDEs.<n>Our work bridges theoretical rigor with practical efficiency in diffusion-based generative modeling.
  arXiv  Detail & Related papers  (2025-06-10T01:46:42Z)
• Feynman-Kac Correctors in Diffusion: Annealing, Guidance, and Product of Experts [64.34482582690927]
  We provide an efficient and principled method for sampling from a sequence of annealed, geometric-averaged, or product distributions derived from pretrained score-based models.<n>We propose Sequential Monte Carlo (SMC) resampling algorithms that leverage inference-time scaling to improve sampling quality.
  arXiv  Detail & Related papers  (2025-03-04T17:46:51Z)
• Random Walks with Tweedie: A Unified View of Score-Based Diffusion Models [11.161487364062667]
  Diffusion models have emerged as powerful tools for generating realistic, synthetic signals.<n>We present a concise derivation for several influential score-based diffusion models that relies on only a few textbook results.
  arXiv  Detail & Related papers  (2024-11-27T19:13:20Z)
• Theory on Score-Mismatched Diffusion Models and Zero-Shot Conditional Samplers [49.97755400231656]
  We present the first performance guarantee with explicit dimensional dependencies for general score-mismatched diffusion samplers.<n>We show that score mismatches result in an distributional bias between the target and sampling distributions, proportional to the accumulated mismatch between the target and training distributions.<n>This result can be directly applied to zero-shot conditional samplers for any conditional model, irrespective of measurement noise.
  arXiv  Detail & Related papers  (2024-10-17T16:42:12Z)
• Stochastic Runge-Kutta Methods: Provable Acceleration of Diffusion Models [21.961189407928853]
  We propose and analyze a training-free acceleration algorithm for SDE-style diffusion samplers, based on the KL Runge-Kutta method. The proposed sampler provably attains $varepsilon2$ error -- measured in divergence -- using $widetilde O(d3/2 / varepsilon)$ score function evaluations.
  arXiv  Detail & Related papers  (2024-10-07T05:34:51Z)
• Convergence Analysis of Discrete Diffusion Model: Exact Implementation through Uniformization [17.535229185525353]
  We introduce an algorithm leveraging the uniformization of continuous Markov chains, implementing transitions on random time points. Our results align with state-of-the-art achievements for diffusion models in $mathbbRd$ and further underscore the advantages of discrete diffusion models in comparison to the $mathbbRd$ setting.
  arXiv  Detail & Related papers  (2024-02-12T22:26:52Z)
• Reflected Diffusion Models [93.26107023470979]
  We present Reflected Diffusion Models, which reverse a reflected differential equation evolving on the support of the data. Our approach learns the score function through a generalized score matching loss and extends key components of standard diffusion models.
  arXiv  Detail & Related papers  (2023-04-10T17:54:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.