acceptodds
Under review as a conference paper at ICLR 2027

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

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

Primary area:
learning theory
Keywords:
Discrete diffusion models, accelerated sampling, Gibbs sampling, predictor-corrector methods, sampling complexity.

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_B9NCOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

The paper proposes GADD, a Gibbs-based corrector for uniform-rate discrete diffusion models that uses an existing score model without additional training. It provides convergence guarantees under stated assumptions and evaluates the method on synthetic data, text generation, and conditional music generation.

Critical strengths
  • GADD improves sampling without additional training. The reported gains in both text perplexity and runtime make it a useful option for existing models.

  • The convergence analysis gives the method a solid theoretical motivation, with polylogarithmic dependence on target accuracy under the stated assumptions. Experiments on synthetic data, text, and music also support its usefulness.

Critical weaknesses
  • The text experiments use sequences of length 128. Although the appendix includes small synthetic dimension sweeps, these do not establish how the quality and runtime gains scale to longer text. Since Gibbs correction updates individual coordinates, increasing sequence length may change the correction budget needed to maintain quality and its efficiency relative to predictors that update all tokens. Evaluating sequences of 512 or 1,024 tokens, with both generation quality and measured runtime at comparable NFE budgets, would help assess whether the reported advantages persist.

  • Text evaluation relies mainly on generative perplexity, which may overlook reduced diversity. Could the authors also report token entropy or repetition rates at matched NFE?

Questions for authors

See weaknesses.

2 comments

We thank the reviewer for carefully reading our work and providing insightful feedback, which has led to several additions to the paper.

W2: On diversity

We agree that diversity should be evaluated alongside perplexity. The default GADD setting achieves the lowest perplexity but exhibits lower lexical diversity. This tradeoff can be adjusted through the correction parameters: reducing the number of correction updates from 40 to 20 and setting the threshold to 0.2 substantially recovers diversity. Compared with Campbell, this setting achieves 12.1% lower perplexity, with approximately lower token entropy and lower Distinct-2 rate, while mean 4-gram repetition rate remains low at 0.20%. These results demonstrate an adjustable quality–diversity tradeoff, with the ablation retaining a perplexity advantage while substantially reducing the diversity loss.

Results below are mean ± standard deviation across three seeds, with 128 generated sequences per method and seed. Perplexity and diversity are evaluated on the same samples.

NFEMethodPerplexity ↓Token entropy (nats) ↑4-gram repetition (%) ↓Distinct-2 ↑
256Euler288.57 ± 8.744.3486 ± 0.00610.1583 ± 0.05640.8131 ± 0.0031
256Campbell215.03 ± 5.194.3221 ± 0.00550.1542 ± 0.00720.7971 ± 0.0050
256Ren262.93 ± 3.654.3454 ± 0.00660.1938 ± 0.06610.8107 ± 0.0011
256GADD (paper default)163.94 ± 13.644.1028 ± 0.01320.6042 ± 0.11340.6961 ± 0.0063
256GADD (20 updates, threshold 0.2)188.91 ± 12.134.2359 ± 0.00380.2042 ± 0.02530.7586 ± 0.0035

W1: On longer text sequences

We thank the reviewer for suggesting experiments with longer sequences. We extended our text experiments from d=128d=128 to d=512d=512, comparing all methods using the same checkpoint at NFE=256. Results below report mean ± standard deviation across three seeds, with 128 generated sequences per method and seed. All methods additionally use one common final denoising evaluation.

MethodPerplexity ↓Token entropy (nats) ↑4-gram repetition (%) ↓Distinct-2 ↑
Euler213.08 ± 5.325.2091 ± 0.00860.4707 ± 0.04600.7026 ± 0.0030
Campbell167.14 ± 7.465.1922 ± 0.01450.4763 ± 0.05490.6941 ± 0.0017
Ren205.57 ± 3.375.1993 ± 0.00790.5367 ± 0.04990.6979 ± 0.0046
GADD (160, 0.05)90.33 ± 9.214.7419 ± 0.01451.9314 ± 0.16370.4735 ± 0.0069
GADD (80, 0.20)131.35 ± 9.064.9654 ± 0.01100.8508 ± 0.06740.5832 ± 0.0067

GADD retains its perplexity advantage at this longer sequence length, reducing perplexity by 46.0% relative to Campbell, the strongest baseline. The milder correction setting offers a different quality–diversity balance: it retains a 21.4% perplexity improvement, with 4.4% lower token entropy, 16.0% lower Distinct-2, and average 4-gram repetition below 1%. These results demonstrate that the perplexity benefit persists at four times the original sequence length, while also making the diversity trade-off explicit.

We hope that our response above has addressed your concern, and we would appreciate that you could raise your rating if your concern has been resolved.

Thanks for the comments. The additional results on diversity and longer sequences alleviate my concerns, though the wall-clock runtime comparison at 512 tokens is still missing. I maintain my original assessment.

Reviewer_bX54OpenReview ↗
Rating
2(+1)
Confidence
3
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper studies the query complexity of uniform diffusion sampling and gives the first algorithm to scale polylogarithmically in the target error, mirroring recent advances in the continuous diffusion setting by, e.g., Chen, Chewi, Daskalakis, and Rakhlin and Gatmiry, Chen, and Salim. The approach this paper takes is different: they use Gibbs sampling with respect to the noisy marginals as a corrector and argue that when Gibbs sampling has a spectral gap, the corrector can be used to bring the sampler closer to the true reverse trajectory and thus maintain polylogarithmic dependence on the target error. The only prior work towards achieving better error dependence for discrete diffusion was the work of Chen and Ying, which actually achieves exact sampling with no dependence on the target error albeit a randomized number of steps.

Critical strengths
  • The paper targets a fundamental question, namely achieving high-accuracy for discrete diffusion sampling, and gives some initial guarantees in this direction
  • There are some small-scale experiments comparing the method to more standard discretizations for uniform diffusion.
Critical weaknesses
  • The precise nature of the contribution is somewhat confusing. Given that the main result relies on Gibbs sampling to have a spectral gap, in principle one could just run Gibbs sampling instead of diffusion. So somehow this assumption feels too strong to be interesting. Note also that the spectral gap assumption is made uniformly along the entire trajectory, which is even stronger than what is needed for Gibbs sampling
  • Additionally, the paper claims that a shortcoming of the Chen and Ying result is that the number of steps is randomized. But the number of steps is Poisson distributed, so in principle one could just set a query budget and output "fail" if the sampler exceeds that number of steps, and by Poisson tail bounds one would get a deterministic dlog⁡(d/ϵ)d\log(d/\epsilon) rate without assuming anything about spectral gaps.
Questions for authors
  • How does the final result compare to just applying Chen and Ying's uniformization trick and stopping if the number of queries exceeds the desired amount?
  • Why is it reasonable to assume a bound on ρ∗\rho_*?
9 comments

We thank the reviewer for carefully reading our work and providing insightful feedback.

W1(a): On the contribution and comparison to Gibbs samplers

We agree that geometric convergence of fixed-target Gibbs sampling under a spectral-gap condition is classical, but applying Gibbs requires the knowledge of the Gibbs update kernel (the conditional distribution required for Gibbs updates) is not available a priori in our setting. Our contribution is rather to (1) construct Gibbs update kernels directly from learned diffusion scores without additional training, and (2) analyze their interaction with diffusion predictors across changing targets while controlling score-estimation errors. Such an analysis can be further extended to CTMC correctors, as we show in Appendix E.

Moreover, even with knowledge of the Gibbs update kernels, in Section 3.5 we establish an instance-specific advantage of GADD over Gibbs: for singleton targets, with exact scores and the same uniform initialization, GADD requires only O(log⁡(d/ε))\mathcal{O}(\log(d/\varepsilon)) sampling steps, whereas vanilla random-scan Gibbs requires Ω(dlog⁡(d/ε))\Omega(d\log(d/\varepsilon)) updates. The intuition is that the added diffusion path provides a concrete benefit, where predictors update coordinates in parallel and supply warm initializations for subsequent correctors. Our mixed-point experiment further demonstrates improved sampling where direct Gibbs mixes poorly.

W1(b)/Q2: Why is a positive lower bound on the path-wise spectral gap reasonable?

First, for a fixed target, we show that connected support (in terms of Hamming distance) guarantees a positive, ε\varepsilon-independent lower bound on ρ∗\rho_* (Corollary 1). For real-world data (say, text and music) modeling, this is an implicit modeling assumption with autoregressive models, where an unmasked softmax with finite logits assigns strictly positive probability to every next token, making the target well-connected (indeed, having full support in this case).

Also, in Theorem 2, under the stronger full-support condition 0<l≤q0(x)≤u0<l\leq q_0(x)\leq u with u/l=O(1)u/l=\mathcal{O}(1), we derive the explicit bound ρt≥1/(d(u/l))=Ω(d−1)\rho_t\geq 1/(d(u/l))=\Omega(d^{-1}) uniformly in time. We also relax the score-error assumption to an expectation under the true diffusion marginals and permit sampling to t=0t=0.

Please also see our response to Reviewer JQ7s, where we have included more practical examples and numerical verification on ρt\rho_t.

W2/Q1: On comparison to [1] (Chen and Ying)

Below, we show that our work still makes substantive new contributions beyond [1], given that the reviewer’s proposed truncation mechanism can be applied to [1] to obtain a deterministic budget with only a small additional TV error and thereby improve its deterministic complexity. We also emphasize that this truncation argument would still require a rigorous analysis.

(On the resulting rate) For the singleton target with exact scores, standard uniformization with a state-independent dominating rate still requires Θ(dlog⁡(d/ε))\Theta(d\log(d/\varepsilon)) expected Poisson events under the stopping choice δ≍ε/d\delta\asymp\varepsilon/d. In comparison, GADD achieves O(log⁡(d/ε))\mathcal{O}(\log(d/\varepsilon)) sampling complexity on this target, giving a factor-of-dd improvement. The reason for such an advantage is similar to the comparison with Gibbs: uniformization changes at most one token per event, whereas GADD’s Euler predictor updates all coordinates in parallel.

(Validation from experiment) We also compared the samplers on text generation with sequence length (d=128). At a matched sampling budget of 256 NFEs, truncated uniformization exhausted its budget before reaching the endpoint for every sampled trajectory and yielded generative perplexity of approximately 2.74×1052.74\times10^5, substantially worse than GADD. This demonstrates GADD’s practical advantage at this computational budget.

(On score-estimation error) The uniformization analyses in [1] require time-integrated score-estimation error control because scores are evaluated at random event times. Capping the event count does not change these evaluation times. In comparison, our Assumption 1 requires score-error control only at prescribed discretization points. under the clean sampling-path distributions. Moreover, under our full-support regularity condition, Assumption 2 instead measures score-entropy error under the true diffusion marginals at those grid points. Such a score error is more practical during training, whose discrete-average form is also typically employed in prior continuous diffusion works (say, [3,4]). Under such a discrete-average score-error assumption, prior works have only achieved a polynomial dependence on 1/ε1/\varepsilon [2,5,6].

(On the bounded-score assumption) Another distinction concerns assumptions on the learned scores. For uniformization, [1, Assumption 2] and [2, Assumption 4.4] explicitly impose boundedness conditions on the score estimator to control the rates used by uniformization. Our analysis does not require a separate bound on the learned scores. The reason is that the Euler predictor caps the total transition probability for each coordinate, whereas the Gibbs corrector normalizes scores into conditional probabilities. Note that such a bounded-score assumption has also been removed in [6], albeit with a different approach since our sampler is different from theirs.

[1] Hongrui Chen and Lexing Ying. Convergence Analysis of Discrete Diffusion Model: Exact Implementation through Uniformization. 2024.

[2] Yinuo Ren, Haoxuan Chen, Grant M. Rotskoff, and Lexing Ying. How Discrete and Continuous Diffusion Meet: Comprehensive Analysis of Discrete Diffusion Models via a Stochastic Integral Framework. ICLR, 2025.

[3] Hongrui Chen, Holden Lee, and Jianfeng Lu. Improved Analysis of Score-based Generative Modeling: User-Friendly Bounds under Minimal Smoothness Assumptions. ICML, 2023.

[4] Joe Benton, Valentin De Bortoli, Arnaud Doucet, and George Deligiannidis. Nearly d-Linear Convergence Bounds for Diffusion Models via Stochastic Localization. ICLR, 2024.

[5] Yuchen Liang, Yingbin Liang, Lifeng Lai, and Ness Shroff. Discrete Diffusion Models: Novel Analysis and New Sampler Guarantees. NeurIPS, 2025.

[6] Daniil Dmitriev, Zhihan Huang, and Yuting Wei. Efficient Sampling with Discrete Diffusion Models: Sharp and Adaptive Guarantees. COLT, 2026.

We hope that our response above has addressed your concern, and we would appreciate that you could raise your rating if your concern has been resolved.

Dear Reviewer bX54,

As the author-reviewer discussion period will end soon, we would be grateful if you could review our responses and let us know whether you still have any questions, so that we still have an opportunity to answer them. If our responses have resolved your concerns, we would also sincerely appreciate your kind consideration of a higher rating.

Thank you very much for your thoughtful review and the time and effort you have devoted to our paper.

Authors

Reviewer_JQ7sOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes GADD (Gibbs-Accelerated Discrete Diffusion), a new method for accelerating sampling from uniform-rate discrete diffusion models. GADD designs a Gibbs-based corrector that exploits the structure of the concrete score function to construct Gibbs posterior likelihoods directly, without requiring any additional training. The authors claim a sampling complexity of O(polylog(ε−1))O(\mathrm{polylog}(\varepsilon^{-1})), which is presented as the first such logarithmic rate for diffusion-based samplers of uniform-rate discrete diffusion models. The paper also introduces a new framework for analyzing predictor-corrector methods. Empirical evaluation is conducted in three settings: synthetic data, zero-shot text generation, and zero-shot conditional music generation.

Critical strengths
  • The proposed method is novel in that it constructs Gibbs posterior likelihoods directly from existing score estimators by leveraging the structure of the concrete score function, and it remains scalable to high-dimensional discrete spaces. Moreover, the convergence guarantees (Theorems 1 and 2) rely only on standard score-estimation assumptions (Assumptions 1 and 2) and do not impose stronger accuracy requirements than vanilla diffusion models. This ensures both practical applicability and theoretical soundness at the same time.

  • Beyond proposing the method, the paper presents an analytical framework that inductively tracks error propagation across predictor iterations. By decomposing the error into initialization, mixing, and estimation components, this framework applies not only to GADD but also to the classical CTMC corrector (Campbell et al., 2022) (Theorem 4, Appendix E), offering a unified view of convergence under approximate updates.

Critical weaknesses

The actual complexity in Theorem 1 is O(dρ∗−1log⁡2(dS/ε))O(d\rho_*^{-1}\log^2(dS/\varepsilon)), which is inversely proportional to the spectral gap ρ∗\rho_*. The paper is commendably explicit in Corollary 1 about the fact that this guarantee depends on the connectivity of supp(q0)\mathrm{supp}(q_0), and this transparency is appreciated. However, (i) the paper does not quantify how large ρ∗\rho_* is in the experimental domains (high-dimensional text with S=50257S=50257, music, and molecules), and (ii) the only example satisfying ρ∗=Ω(poly−1(d))\rho_* = \Omega(\mathrm{poly}^{-1}(d)), namely the high-temperature Ising model, is far removed from the experimental domains.

As a result, it is currently difficult to judge how meaningful the paper's central polylog guarantee actually is for the domains of interest, given the hidden 1/ρ∗1/\rho_* factor and the connectivity condition. This is not a fatal flaw that undermines the value of the paper, but it is a point where additional support would help clarify the practical implications of the theoretical claims.

Questions for authors

The following questions all relate to the points raised under Critical Weaknesses. If the authors can strengthen the validity of the theoretical premises through a discussion of the magnitude of ρ∗\rho_* or the connectivity of supp(q0)\mathrm{supp}(q_0), the paper would become even more valuable to the community. These are requests for clarification rather than suggestions for future work.

  1. For each experimental setting (especially the controllable synthetic data), can you empirically estimate or lower-bound ρ∗\rho_* (or a suitable proxy) and show that it is consistent with the theoretical complexity prediction?

  2. For the actual text and music data distributions, how reasonable is the connectivity (or conditional connectivity) assumption on supp(q0)\mathrm{supp}(q_0)? Also, if connectivity is partially violated, how gracefully does the polylog guarantee degrade?

  3. Besides the high-temperature Ising model, are there any distribution classes with properties closer to the experimental domains for which ρ∗=Ω(poly−1(d))\rho_* = \Omega(\mathrm{poly}^{-1}(d)) can be guaranteed?

2 comments

We thank the reviewer for carefully reading our work and providing insightful feedback, which has led to several additions to the paper.

W/Q1: ρ∗\rho_* for synthetic experiments

We computed the Gibbs spectral gap exactly along the diffusion path for both synthetic targets. Specifically, for computability, we employ d=S=4d=S=4 because exact eigendecomposition is infeasible at that size of the mixed-point experiment in Section 4.1 (88≈1.7×1078^8 \approx 1.7 \times 10^7 states). At each diffusion time tt, we compute the noised distribution qtq_t, explicitly construct its random-scan Gibbs transition matrix PtP_t, compute its eigenvalues, and then compute ρt=1−λ2(Pt)\rho_t = 1 - \lambda_2(P_t). The results are shown in the following table.

Diffusion time ttAR modelMixed-point model
00.123130
1e-6 (δ\delta)0.123131.44785e-7
1e-40.123151.4484e-5
0.0010.123371.4531e-4
0.010.125560.0014985
0.050.134690.0083151
0.10.145000.018084
0.30.177340.061884
10.230350.18256
20.247210.23916
80.250000.25000

For the AR model, the spectral gap remains bounded away from zero across the evaluated noise levels, with the observed minimum occurring at t=0t=0, consistent with Corollary 1. For the mixed-point model, the disconnected support yields ρ0=0\rho_0=0 (Lemma 7). Although the gap is positive but small at the experimental cutoff δ>0\delta>0, the diffusion path passes through smoother intermediate targets with substantially larger ρt\rho_t. Together with our sampling results, this supports the practical benefit of diffusion-based warm-starts for GADD on spiky multimodal targets, an effect not fully captured by our upper bound based on the worst-case gap ρ∗\rho^*.

Q2(a)/Q3: Connectivity for real-world data, and other distribution examples

We emphasize that connectivity is a modeling assumption rather than a verified property of the true data distribution. Nevertheless, it is implicit in many widely used text models. For example, autoregressive models with an unmasked softmax and finite logits assign strictly positive probability to every next token, yielding full support over fixed-length sequences. Our connectivity condition is weaker: connected support suffices for the polylogarithmic dependence on ε\varepsilon under our remaining assumptions, without requiring full support. For another example closer to text modeling, consider the hierarchical Latent Dirichlet Allocation (LDA) model [1], with fixed positive topic-word probabilities and fixed positive Dirichlet parameters α\alpha. For random-scan Gibbs sampling of its word-sequence distribution, our calculation gives ρt=Ω(d−2)\rho_t = \Omega(d^{-2}) uniformly along the diffusion path. This provides a concrete text-modeling example with a polynomial spectral-gap bound beyond the high-temperature Ising/Potts setting.

[1] Blei et al., Latent Dirichlet Allocation, JMLR, 2003.

Q2(b): What if connectivity is slightly violated?

When connectivity fails, as in the mixed-point example, uniform diffusion still produces full-support intermediate targets at every positive noise level. However, ρ∗\rho_* may decrease as the cutoff δ≍ε/d\delta \asymp \varepsilon/d approaches zero, introducing additional ε\varepsilon-dependence into the bound. Our numerical diagnostics show substantially larger gaps at smoother intermediate targets, and the sampling experiments for the mixed-point target demonstrate that GADD can still benefit from following the diffusion path in this setting.

We hope that our response above has addressed your concern, and we would appreciate that you could raise your rating if your concern has been resolved.

I thank the authors for their detailed and constructive response.

Regarding Q1, I appreciate the exact computation of the Gibbs spectral gap along the diffusion path for both synthetic targets. The results are consistent with Corollary 1 (AR model) and Lemma 7 (mixed-point model), and the behavior of the intermediate targets is clearly illustrated.

Regarding Q2, the clarification that connectivity is a modeling assumption, together with the explanation of how the bound degrades (through additional ε\varepsilon-dependence) when connectivity is partially violated, addresses my concern.

Regarding Q3, the hierarchical LDA example with ρt=Ω(d−2)\rho_t = \Omega(d^{-2}) provides a concrete distribution class closer to text modeling, beyond the high-temperature Ising/Potts setting.

Overall, my main concerns have been adequately addressed. I acknowledge that the numerical verification is conducted at a small scale and that the examples remain idealized rather than measured on the actual trained models, but these points fall within the scope of clarification I originally requested. I will therefore keep my current positive score.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.