From Scores to Gibbs Correctors: Accelerating Uniform-Rate Discrete Diffusion Models
arXiv:2605.27352v1 [cs.LG] 26 May 2026
Yuchen Liang Ness Shroff Yingbin Liang The Ohio State University 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 O(polylog(ε−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, zeroshot 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.
1
Introduction
Generative modeling is a central problem in deep learning, aiming to learn distributions that closely match observed data and enable high-quality sample generation. In recent years, diffusion models [1–3] have emerged as a powerful and flexible generative framework, achieving state-of-the-art performance across a wide range of applications. Among them, discrete diffusion models operate directly over discrete sample spaces and have proven highly effective for discrete-data domains. They have achieved strong empirical performance in natural language processing [4], graph generation [5, 6], musical note generation [7], and molecular and drug design [8, 9], among others. Despite their empirical success, diffusion models face a major bottleneck in generation efficiency. Unlike classical generative models such as GANs, diffusion models typically require a large number of iterative steps to generate a single sample. A substantial body of work has explored accelerated sampling methods for continuous diffusion models, including predictor-corrector schemes [10], Runge-Kutta methods [11], Hessianbased approaches [12], and, more recently, successive refinement techniques [13]. In contrast, relatively few studies have focused on accelerating discrete diffusion models (see Section 1.2 for details). Among the two canonical classes of discrete diffusion models, masked (i.e., absorbing-rate) diffusion models (MDMs) exhibit unique structure induced by the masking dynamics: once a token reaches the absorbing masked state it remains fixed thereafter, which facilitates the development of faster samplers through structured unmasking steps. This built-in structure can be exploited to design efficient samplers. For example, [14] showed that MDMs admit an analytic characterization of sampling times, requiring at most d steps to generate high-quality samples, and [15] exploited informed correctors that are specially designed for MDMs. In contrast, despite the strong language modeling performance of masked diffusion models (MDMs), uniform-rate discrete 1
diffusion models remain widely used in domains such as graph and molecule generation, where masking-based approaches can suffer from state-clashing and produce invalid structures (e.g., molecules violating chemical rules) [16, 17]. More recently, [18] showed that uniform-rate models augmented with predictor-corrector methods can outperform both autoregressive (AR) and mask diffusion models in few-step text generation. Despite promise, accelerating uniform-rate models is challenging and comparatively underexplored, since they lack the salient structure exploited by masking-based designs. From a theoretical perspective, random-step samplers (e.g., uniformization) can simulate the reverse process exactly up to score-estimation error, but their realized step counts can be unbounded. For deterministic-step samplers, existing total-variation complexity bounds scale only polynomially in ε, where ε is the target accuracy (see Table 1 for details): O(ε−1 ) for exact and τ -leaping methods [7, 19], O(ε−2 ) for Euler and Tweedie τ -leaping [20]. More recently, [21] proposed an accelerated approach achieving an improved rate of O(ε−1 ) by leveraging higher-order numerical solvers to more accurately approximate the reverse process, inspired by advances in higher-order numerical solvers [11]. Overall, existing samplers for uniform-rate models achieve only polynomial dependence on ε, which naturally raises the following question: Question: Can we break the O(poly(ε−1 )) barrier and achieve a logarithmic dependence, namely O(polylog(ε−1 )), for uniform-rate discrete diffusion models? Our study provides affirmative answer to this question.
1.1
Our Contributions
In this paper, we propose the first uniform-rate discrete-diffusion-based sampler that achieves O(polylog(ε−1 )) convergence rate. Our detailed contribution are as follows. Algorithmic Design: Our key contribution is to propose a novel Gibbs-based corrector, the Gibbs-Accelerated Discrete Diffusion (GADD) algorithm, for sampling from uniform-rate discrete diffusion models. Notably, leveraging properties of the existing concrete score function, our GADD algorithm does not need extra-training beyond the score functions. Instead, the posterior likelihood required for the Gibbs update can be directly obtained from the score estimator. Theoretical Analysis: We theoretically show that GADD achieves an overall sampling complexity of O(polylog(ε−1 )), improving upon existing diffusion-based sampling methods for uniform-rate discrete diffusion models. In comparison, all previous samplers only achieve the convergence rate of O(poly(ε−1 )). In particular, we show that the diffusion process naturally provides a warm-start to apply Gibbs correctors; such a warm-start simultaneously reduces both the Gibbs convergence error (under perfect per-step update) and the error from inaccurate score estimation. Numerical Experiments: We further conduct numerical experiments demonstrating the practical advantages of GADD across synthetic data, zero-shot unconditional text sampling, and zero-shot conditional music generation. These results corroborate our theoretical findings and show that GADD achieves superior efficiency and robustness compared to previous approaches. In particular, GADD consistently improves sample quality at the same NFE budget, performs well on challenging spiky target distributions, and yields favorable wall-clock efficiency in realistic discrete-generation settings. General Framework for Predictor-Corrector Sampling: Overall, we develop a general framework for analyzing predictor-corrector methods in discrete diffusion models, based on an induction argument that tracks error propagation across iterations while accounting for inaccurate corrector updates. By decomposing the error into initialization, mixing, and estimation components, the framework provides explicit conditions for controlling global error without stronger score accuracy requirements than in vanilla diffusion models. Beyond 2
Algorithm Exact τ -leaping
Euler Method and Tweedie τ -leaping
Number of steps √ d e O ε4 e d O ε2 e O dε2 e d2 O ε2 e d2 O ε
e O
DMPM (and its variants)
d ε4
† e poly(d) O 2ε 2 ) e O log ρ(d/ε ∗
θ-RK-2 and θ-Trapezoidal
GADD (ours)
Paper Reference [19] [7] [22] [23] [20] [24] [25] [21] (This paper, Thm 1)
Table 1: Summary of results for uniform-rate discrete diffusion samplers in terms of the number of steps needed to achieve O(ε) accuracy in TV(qδ , p̂T −δ ) (or, equivalently, O(ε2 ) for KL(qδ ||pT −δ )), where qδ is a perturbed distribution satisfying TV(q0 , qδ ) ≲ dδ . We only display those results having deterministic number of step-sizes. Here, d denotes the dimension (e.g., length of the generated sentence), and ρ∗ is the path-wise worst-case spectral gap for Gibbs samplers (which is ε-independent, and which is typically in the order Ω(d−1 ) for well-structured distributions). † The poly(d) dependence is what we infer, which is not provided in their paper. Overall, our result achieves the first O(polylog(ε−1 )) convergence rate, whereas all prior works achieve polynomial dependence on ε−1 . GADD, it also applies to the classical CTMC corrector [7], offering a unified view of its convergence under approximate updates.
1.2
Related Works
In this subsection, we focus on related works that provide convergence guarantees for uniform-rate discrete diffusion models. Please see Appendix A for additional related works. Convergence Theory on Uniform-Rate Discrete Diffusion Samplers. A growing body of work studies the number of steps required for samplers to achieve ε-TV guarantees (see Table 1). The earliest such result, [7], analyzed τ -leaping under the TV metric. Subsequent studies considered two classes of samplers. For random-step methods, [22, 26] established guarantees for the uniformization sampler, though the realized number of steps may be unbounded. For deterministic-step methods, [19] obtained strong guarantees under the assumption of access to a perfect per-step solver, while [24, 25] achieved low dependence on d via the DMPM sampler at the cost of a high ε dependence. [22, 23] further improved guarantees for τ -leaping, and more recently, [20] provided the first analysis of the Euler method and Tweedie τ -leaping. Notably, all these analyses of deterministic-step samplers yield O(poly(ε−1 )) convergence rates. Concurrent with our work, [27] derives an S -independent upper bound on the error under the assumption of exact simulation of the continuous-time sampling process; however, the corresponding step complexity when there is discretization remains unclear. Acceleration of Uniform-Rate Discrete Diffusion Samplers. Compared to the extensive literature on standard samplers, relatively few works study the acceleration of uniform-rate discrete diffusion samplers. Several empirical approaches have been proposed to accelerate discrete diffusion models. [7] first introduced a predictor-corrector scheme with a CTMC corrector that moves the particle toward the target distribution, 3
and [28] generalized this forward-backward idea and developed a unified corrector especially for discrete flow-matching. More recently, [18] developed a family of Ψ-samplers that achieve strong performance in both language and image modeling. Notably, the correctors in [18,28] are directly tied to the mean parameterization, in contrast to the score parameterization considered in our work. On the theoretical side, [21] accelerated discrete diffusion models using higher-order numerical methods based on Runge-Kutta schemes, and achieves a convergence rate of O(ε−1 ) in terms of the target accuracy ε.
2
Preliminaries
In this section, we review both discrete diffusion models and Gibbs samplers, the two major components in the work.
2.1
Discrete Diffusion Sampling
Discrete diffusion models are defined by a forward noising process and a corresponding reverse denoising process involving discrete data. The forward process is formulated as a continuous-time Markov chain (CTMC) on the discrete state space X = [S]d , where d denotes the number of tokens and each token takes values from a vocabulary of size S . Let x0 ∈ [S]d denote the initial data sample, distributed according to the probability d d mass function (p.m.f.) q0 . Let Rt ∈ RS ×S be the (time-dependent) rate matrix of the CTMC. For any two states x, y ∈ [S]d , the entry Rt (x, y) specifies the instantaneous transition rate from x to y at time t. The conditional distribution of the state at time t + ∆t given the state at time t satisfies qt+∆t|t (y | x) = 1 {y = x} + Rt (x, y) ∆t + o(∆t),
(1)
where P1 {·} denotes the indicator function. Validity of the CTMC requires that Rt (x, y) ≥ 0 for all x ̸= y and y Rt (x, y) = 0 for all x. Among the many choices of Rt , one typical choice is the “uniform-rate” matrix [29]. Specifically, the “uniform-rate” is defined as ( 1 if Ham (x, y) = 1 , Rt (x, y) = S 0 if Ham (x, y) ≥ 2 where Ham (x, y) denotes the Hamming distance between x and y . With such an Rt , the tokens would evolve independently and homogeneously for each token [7, 29]. Also, one can show that qT ≈ Uniform([S]d ) and the mixing speed is exponentially fast [19]. To sample from the diffusion model, one typical approach is to walk through the reverse process, which is defined as the exact time reversal of the forward CTMC with initial distribution equal to qT [7, 30]. By [7], the reverse process is itself a CTMC whose transition rate is R⃗t (x, y) := Rt (y, x)qt (y)/qt (x), which depends on the density ratio for all Hamming-distance-1 pairs (x, y), a quantity commonly referred to as the (concrete) score. Since this quantity is generally intractable, we estimate it using a neural network, with one popular choice of loss function: the score-entropy loss [29]. After we have obtained an approximate score, for practical sampling, we can discretize the continuous-time reverse process and employ approximate sampling methods for CTMC, such as the Euler method [29]. More specifically, define the estimated reverse rate as R̂t (x, y) := Rt (y, x)st (y, x). Upon initializing xtN ∼ Uniform([S]d ) (with tN = T ), the Euler method is given by, for each k = N − 1, . . . , 0, ( i a, w.p. R̂k+1 (xitk+1 , a)(tk+1 − tk ), ∀a ̸= xitk+1 xitk = , (2) i xitk+1 , w.p. 1 + R̂k+1 (xitk+1 , xitk+1 )(tk+1 − tk ) where i i (xi , xi ) := − R̂k+1 (xi , a) := R̂tk+1 (x, x−i ⊕i a), ∀a ̸= xi , and R̂k+1
X a̸=xi
4
i R̂k+1 (xi , a).
2.2
Random-Scan Gibbs Samplers
In the sampling literature, Gibbs sampling is among the most popular methods due to its simplicity, exactness of conditional updates, and ease of implementation. One typical Gibbs samplers is the (single-site) random-scan Gibbs sampler, where an update index is drawn randomly at each step. For a target distribution π supported on X , define the one-step Markov transition kernel for random-scan Gibbs sampler as ( wi π i (y i |x−i ) if y −i = x−i P (x, y) := . (3) 0 otherwise Here wi is some weight function over the indices that sums up to 1. For random-scan Gibbs samplers, such a kernel enjoys many regularity conditions of Markov operators. First, given its probabilistic nature, P is aperiodic. Also, if π(x) > 0 over the support, P is irreducible. Given these two properties, running such a Markov chain would yield a unique stationary distribution, which can be shown as π itself. For a full review of Gibbs samplers (Glauber dynamics), we refer readers to [31]. One way to characterize the convergence of such a Gibbs operator is through the Wasserstein-1 distance (associated with the Hamming metric), defined as: W1 (ν1 , ν2 ) :=
inf Γ∈Π(ν1 ,ν2 )
E(x,y)∼Γ Ham (x, y) ,
where Γ(ν1 , ν2 ) is the set of couplings of ν1 and ν2 . Under certain classical assumptions (cf. Theorem 14.6 in [31]), one can show that W1 (ν1 P, ν2 P ) ≤ (1 − ρ)W1 (ν1 , ν2 ). (4) Here ρ is also called the spectral gap, which depends on the structure of the underlying distribution. The Wasserstein distance is closely related to the total-variation distance, which is a typical metric to characterize convergence in diffusion models (e.g., [20, 22]), as follows (see [31, Proposition 4.7]): TV(ν1 , ν2 ) ≤ W1 (ν1 , ν2 ) ≤ d · TV(ν1 , ν2 ).
2.3
(5)
List of Notations
Let xi (1 ≤ i ≤ d) denote the i-th element of a vector x ∈ [S]d and x−i ∈ [S]d−1 denote the vector with the i-th element removed. Define Ham (x, y) as the Hamming distance between two vectors x and y . For a positive integer n, [n] := {1, . . . , n}.
3
Discrete Diffusion Sampling with Gibbs Correctors
In this section, we present and analyze a novel Gibbs corrector for sampling from the uniform-rate CTMC, which we call the Gibbs-accelerated Discrete Diffusion (GADD) sampler.
3.1
The GADD Algorithm
We have summarized our algorithm in Algorithm 1 below. Algorithm 1 comprises two components: an outer loop and an inner loop. The outer loop defines a sequence of target distributions qtk , each corresponding to a perturbed data distribution induced by the forward diffusion process. For each tk , the inner loop runs a Gibbs sampler for Lk steps targeting qtk . In practice, setting Lk = 0 corresponds to performing no correction at the current step. In particular, when Lk = 0 for all k and the Euler update is applied throughout, Algorithm 1 reduces to the standard Euler sampler defined in (2). We also note that the weights wi in the algorithm can be chosen in an informed manner, similar to [15]. Finally, we provide a variant of Algorithm 1 in Appendix B, which employs systematic-scan Gibbs updates rather than random-scan ones. 5
Algorithm 1: Gibbs-Accelerated Discrete Diffusion (GADD) Input: initialization xtN ∼ pinit = Uniform([S]d ), discretization points {tk }N k=0 (with tN = T and N t0 = δ ), estimated score st , correction steps {Lk }k=0 2 for k = N − 1 to 0 do 3 z0 = the output of the Euler update given xtk+1 (using (2)) ; 4 for ℓ = 1 to Lk do 5 Sample i w.r.t. weight wi over [d]; −i 6 Construct posterior q̂tik (·|zℓ−1 ) (e.g., using (6) or (8)); −i 7 Update zℓi ∼ q̂tik while fixing zℓ−i = zℓ−1 ; 8 end 9 xtk = zLk ; 10 end Return: xt0
3.2
Constructing Posterior Likelihood from Score
To utilize the Gibbs corrector for target qt (where t ∈ [δ, T ]), one needs to have access to qti (·|x−i ) for all t ∈ [δ, T ] and i ∈ [d]. Our key observation is that such information is readily available in the score function, which is the density ratio between all Hamming-distance 1 pairs. Notice that −1 P −1 P qti (y i |x−i ) qt (x−i ⊕i y i ) qti (xi |x−i ) = = . y i ∈[S] q i (xi |x−i ) y i ∈[S] qt (x) t
Thus, one example is to use the following estimator: P −1 −i ⊕ y i , x) q̂ti (xi |x−i ) = s (x . i y i ∈[S] t
(6)
With a slight abuse of notation, we define st (x, x) ≡ 1 (which does not require any estimation). We have provided more estimator candidates in Appendix B. To clarify, although the posterior estimator in (6) (and also those in Appendix B) requires a summation over [S], this does not necessarily require S forward calls to the score model. For example, with the implementation of SEDD, a single forward output of the score function is of size (B, d, S) (where B is the batch size), which contains all the corresponding scores (i.e., density ratios) used to aggregate. Thus, per Gibbs-step, we only need to call the score function once to get an estimate of the posterior. Such a construction enables direct evaluation of the posterior probabilities required by the Gibbs sampler, which does not require any extra-training and can be directly used for acceleration. In contrast, previous correctors that employ Metropolis-Hastings algorithms [32] require an additional estimator for the likelihood ratio between all pairs of (x, y), which is both computation- and memory-intensive given that x, y ∈ [S]d is high dimensional. With the estimator in (6), our Gibbs corrector avoids such auxiliary estimation and remains scalable to high-dimensional domains.
3.3
Convergence Analysis of GADD
We first define a few useful notations. Let pT −tk ,ℓ denote the sampling distribution at outer-loop step k = N − 1, . . . , 0 (with target qtk ) and at inner-loop step ℓ = 1, . . . , Lk , without estimation error. The following assumptions are needed for the score estimate. Assumption 1. Fix tk ∈ [δ, T ], i ∈ [d] and ℓ ∈ [Lk ]. Suppose that score estimate satisfies that X qtk (y) E x−i ∼p−i R (y, x) s (y, x) − ≤ εest . t t k k T −tk ,ℓ qtk (x) i −i x ∼qtk (·|x
) y:Ham(x,y)=1
6
Here we need a L1 -type score estimation error, which is different from the score-entropy error typically employed in the literature [19, 22]. This estimation error arises because our analysis directly controls the total variation distance (see Lemma 2), a choice that has also been adopted in prior works [7, 21]. Additionally, for technical reasons, we require the expectation to be taken with respect to p−i T −tk ,ℓ , which is a slightly perturbed −i version of the true target distribution qtk . This condition is, however, likely to be satisfied when using a warmed Gibbs corrector, as is the case for GADD. Assumption 2. Fix t ∈ [δ, T ]. Suppose that st (y, x) ∈ [M −1 , M ] for all x and y . The bound on st is quite typical in prior literature [19, 20]. Also, our main convergence result in Theorem 1 only depends logarithmically on M . With these assumptions, we are ready for the convergence guarantees of GADD. Theorem 1 (Convergence of GADD). Suppose that Assumptions 1 and 2 are satisfied. Let T ≍ −1 ρδ log(d(log S)/ε2 ), εest = O M ε , δ ≍ dε , and κ ≍ log log(d/ε2 ) . Then, choosing tk+1 − tk ≤ κ min {1, tk+1 }, the total number of steps to achieve ε TV error for Algorithm 1 suffices to have log(d/ε2 ) log d3 S/ε2 + d2 M/ε Ntotal ≲ , ρ∗ where ρ∗ := inf t∈[δ,T ] ρt . Note that we have omitted lower-order logarithmic factors. Theorem 1 provides the first convergence guarantee for diffusion-based algorithms to achieve O(polylog(ε−1 )) convergence rate, which shows the effectiveness of predictor-corrector schemes with Gibbs correctors. In particular, for sampling from well-structured target distributions (e.g., high-temperature Ising models) where the spectral gap satisfies ρ∗ = Ω(poly−1 (d)), the total number of sampling steps admits an explicit dependence on the dimension: Ntotal = O poly(d) polylog(ε−1 ) . This is a substantial improvement over prior acceleration methods with theoretical guarantees [21]. On a high level, the diffusion process and the Gibbs sampler benefit from each other in GADD. First, the Gibbs corrector, through its cascading updates, achieves an exponentially decaying error at each outer loop, reducing the total number of required steps from O(poly(ε−1 )) to O(polylog(ε−1 )). On the other hand, the diffusion process naturally provides a warm-start condition that enables the Gibbs sampler to converge more effectively (see Lemma 1). This also mitigates estimation errors arising from an inaccurate corrector, as fewer corrector steps are required to reach convergence (see Lemmas 2 and 3).
3.4
Proof Sketch of Theorem 1
Here we provide a proof sketch of Theorem 1 to describe the idea of our analysis approach. The full proof is provided in Appendix D. Overall, the main technical novelty is to involve inaccurate correctors in the analysis. Different from previous predictor-only approaches [12, 22, 23], here the total convergence error cannot be easily decomposed via Girsanov’s change-of-measure theorem. Rather, the backbone of our approach is an induction argument over the predictor steps. Such a predictor-corrector analysis can also be extended to other correctors, including the CTMC corrector as we show in Section 4 (see Theorem 2). Overall, the sources of error include the outer-loop and inner-loop initialization errors, as well as error propagation arising from imperfect score estimation during the inner-loop iterations. Among these, the √ outer-loop initialization error is straight-forward to derive, with TV(pinit , qT ) ≲ d log S · e−T /2 (see (9), cf. [19, 21]) . As follows, we focus on the inner-loop errors. Step 1: Bounding Inner-loop Initialization Error (Lemma 1). Assuming that the previous outer-loop step ends with a small error, our goal is to show that this can be propagated to the start of the corrector steps, 7
yielding a warm-up condition. Indeed, such an error can be decomposed as (see (14)) TV(pT −tk ,0 , qtk ) ≤ TV(p̂T −tk+1 ,Lk+1 , qtk+1 ) + TV(qtk+1 , qtk ) + TV(p̂T −tk+1 ,Lk+1 , pT −tk ,0 ) . | {z } | {z } | {z } error inherited from previous step
error from moving target
error from predictor step
In the above, the first term is small by our assumption. As long as the step-size vanishes as tk+1 −tk = κ = o(1), the second and third terms are also small since the true and estimated scores have non-diverging upper-bounds. Here unlike vanilla discrete diffusion samplers, our choice of κ does not need to scale as O(ε), which allows for significantly fewer outer-loop steps. Step 2: Bounding Inner-loop Estimation Error (Lemmas 2 to 4). We now turn to the second source of error, which arises from inaccurate correctors. This setting differs from standard analyses of Gibbs sampling, where the target posterior likelihood is typically known (see Appendix A for a survey). To study this effect, we first analyze error propagation in general random-scan Gibbs samplers with target distribution π (Lemma 2); this result may be of independent interest. We then specialize to diffusion-path distributions, using the posterior likelihood estimators in (6) or (8) (Lemmas 3 and 4). In both cases, the error can be upper-bounded provided the estimated scores satisfy suitable lower-bound conditions. Notably, the required form of score estimation closely matches that used in vanilla diffusion models [7, 33]. Step 3: Combining all parts together. We now combine the previous ingredients to establish the induction framework. Suppose that at the previous step tk+1 , we have already shown TV(p̂T −tk+1 ,Lk+1 , qtk+1 ) ≲ Lk+1 ε, where Lk+1 denotes the number of corrector steps in the preceding outer-loop iteration. Then, Lemma 1 provides an upper bound on the initialization error for the next corrector loop. We can further decompose the error accumulated within the corrector loop as TV(p̂T −tk ,Lk , qtk ) ≤ TV(pT −tk ,Lk , qtk ) + TV(p̂T −tk ,Lk , pT −tk ,Lk ) . | | {z } {z } error from pure Gibbs sampling
error from inaccurate Gibbs transitions
Here the second term can be bounded using Lemma 3 as TV(p̂T −tk ,Lk , pT −tk ,Lk ) ≲ Lk M εest . Since εest = results O(ε/M ), the inductive hypothesis is preserved. Meanwhile, by standard Gibbs sampling convergence 2 −1 d (cf. (4)), in order to achieve TV(pT −tk ,Lk , qtk ) ≤ ε, it suffices to take Lk ≲ ρtk log ε (M + Sδ −1 ) . Summing over k yields the desired total number of steps. Notably, our analysis introduces no additional hidden factors beyond those arising from pure Gibbs sampling.
4
Analysis of CTMC Corrector
In this section, we further apply the framework developed in Section 3.4 to other existing correction schemes for discrete diffusion models, thereby demonstrating the generality of our analysis. A common class of correctors in the literature is based on CTMC dynamics. Specifically, at outer-loop time tk , an additional CTMC with an appropriately chosen correction rate is simulated to target the distribution qtk . One example of such a correction rate is given by (cf. [7, Section 4.4]): Rkc (x, y) := Rtk (x, y) + R̂tk (x, y). (7) c Indeed, [7, Proposition 4] shows that the stationary distribution of Rk is correct. As follows, we analyze the non-asymptotic performance of such a corrector using the framework of Theorem 1. Theorem 2. Suppose perfect score estimation and that Assumption 2 holds. In order to achieve ε-TV error, the total number of steps needs to satisfy (ignoring log-dependencies) d2 M 2 Ntotal ≲ 2 2 , µ∗ ε where µ∗ := inf tk ∈[δ,T ] µt is the minimum modified log-Sobolev constant of the rate matrix Rkc . 8
The proof of Theorem 2 is provided in Appendix E. This result readily extends to the broader class of all CTMC correctors with the correct stationary distribution. In particular, Theorem 2 shows that, even in the absence of estimation error, achieving ε-accuracy in TV requires O(poly(ε−1 )) total steps. Compared to Theorem 1, this highlights the advantage of our proposed GADD sampler, which employs Gibbs correctors instead of CTMC-based ones. The proof of Theorem 2 closely parallels that of Theorem 1, relying on the same induction strategy to handle the evolving target distributions and to control the accumulation of corrector errors due to a finite number of corrector steps. Our analysis also sheds light on why CTMC correctors are inferior to Gibbs-based ones. Although the continuous-time CTMC converges to the target at an exponential rate, practical implementations require discretizing the continuous-time trajectory (as in [7, 28]). This discretization introduces a non-negligible error that significantly slows convergence, leading to an overall complexity of only O(poly(ε−1 )) (see Lemma 5).
5
Numerical Experiments for GADD
In this section, we evaluate the numerical performance of our GADD algorithm on three datasets. We include all experiment details in Appendix C.
5.1
Synthetic Experiment
We first numerically compare our GADD algorithm in Algorithm 1 on synthetic data against three baselines: (i) the Euler method, (ii) the Gibbs sampler, both of which are widely used and strong vanilla baselines for sampling from discrete data, and (iii) the θ-Trapezoidal method [21], a recently proposed accelerated sampler for uniform-rate discrete diffusion models.
Figure 1: Comparison of GADD on synthetic data against the Euler method, the θ-Trapezoidal algorithm (left), and the Gibbs sampler (right). We observe that, at the same number of function evaluations (NFEs), our GADD achieves a substantially smaller final error than both the Euler and θ-Trapezoidal methods. This empirical advantage aligns with our theoretical result in Theorem 1: to attain a final total variation error of ε, the required number of steps (and thus the NFE) scales as O(polylog(ε−1 )), which is significantly lower than that of existing samplers, whose complexity scales as O(poly(ε−1 )). We further find that our GADD performs particularly well on spiky target distributions. In such settings, the vanilla Gibbs sampler is known to suffer from poor mixing behavior [31]. In contrast, by leveraging the reverse 9
Method
NFE=32
NFE=64
NFE=128
NFE=256
Vanilla Euler [29] θ-Trapezoidal [21] CTMC corrector [7] GADD (ours)
356.0290 ± 20.519 (9s) 325.9064 ± 20.1654 (11s) 378.0972 ± 19.0272 (10s) 255.630 ± 42.2442 (6s)
285.1672 ± 35.1706 (19s) 267.6957 ± 30.701 (23s) 272.653 ± 10.6409 (21s) 192.1529 ± 35.0539 (13s)
283.0323 ± 24.3 (39s) 255.1958 ± 6.6874 (48s) 227.6811 ± 15.499 (44s) 161.5748 ± 26.1866 (26s)
275.3841 ± 41.248 (79s) 265.9823 ± 18.50979 (97s) 219.8395 ± 24.515 (89s) 149.6407 ± 17.4786 (53s)
Table 2: Zero-shot generative perplexity across different methods. Best result in bold.
Method
Hellinger
Perplexity
Next-tokens Pred Err
Conditional SEDD [29] + GADD (L = 2) + GADD (L = 5) + GADD (L = 50)
0.1759 ± 0.0061 0.0793 ± 0.0044 0.0780 ± 0.0061 0.0817 ± 0.0027
2.9255 ± 0.0553 2.8295 ± 0.0489 2.8108 ± 0.0565 2.8429 ± 0.0568
0.3608 ± 0.0141 0.3503 ± 0.0223 0.3373 ± 0.0159 0.3238 ± 0.0142
Table 3: Conditional generation qualities using Lakh pianoroll dataset [34]. Best result in bold. diffusion process, GADD remains effective and achieves strong performance even under these challenging conditions. This observation provides empirical support for the warm-start effect predicted by our theory, as discussed under Theorem 1.
5.2
Experiment on Text Data
We next consider sampling from text data. We first train a small SEDD Uniform model on the WikiText103 dataset using the suggested hyperparameters as in [29]. We then compare the zero-shot sampling performance of GADD against several predictors, including the vanilla Euler method and the θ-Trapezoidal method, as well as the CTMC corrector, which we analyze in Section 4. We follow the approach in [15] and fix the corrector score at each outer-loop, and we do not re-evaluate the score model within the corrector loop. In Table 2, we report the generative perplexity of the zero-shot generated outputs at fixed NFEs.1 Our proposed GADD method consistently achieves the best performance across all settings. In addition to this metric, we also report the actual wall-clock time. Notably, GADD exhibits lower wall-clock time compared to competing methods. This efficiency gain is likely due to differences in per-step computational cost: each Euler step updates all tokens simultaneously, whereas a random-scan Gibbs correction step updates only a single token per iteration. As a result, our method achieves a favorable trade-off between sample quality and computational efficiency. The superiority of GADD over the CTMC corrector further supports our theoretical result in Theorem 2. While the complexity of the CTMC corrector scales as O(poly(ε−1 )), our GADD requires only O(polylog(ε−1 )), which is much smaller.
5.3
Experiment on Monophonic Music Data
Beyond text data, we also conduct experiments on zero-shot conditional discrete diffusion models [29, 35] on monophonic music data, obtained from [34] and following the pre-processing steps in [7]. Different from unconditional sampling, the goal is to sample from the conditional distribution given part of the observable sequence, but in the zero-shot way without extra-training. In our setting, the goal is to complete a musical sequence given the first 100 notes. To evaluate the effect of correction, we compare: (i) the vanilla Conditional SEDD [29], a well-known zero-shot conditional discrete diffusion sampler, and (ii) the same model augmented 1 For example at NFE=32, the vanilla Euler method takes 32 predictor steps to complete, whereas GADD takes 16 predictor steps and 16 corrector loops.
10
with L Gibbs correction steps (where L ≡ Lk , ∀k ). We again fix the NFEs across all methods during evaluation. Also, in addition to standard metrics such as the mean Hellinger distance of the histogram [7] and the generative perplexity (for which we trained an autoregressive model to evaluate), we introduce an additional metric: the mean prediction error over the next F = 4 tokens, designed to capture the short-term temporal consistency in the generated sequences. From Table 3, incorporating Gibbs correction steps yields significant improvements across all considered metrics. This highlights the generality of our Gibbs corrector, extending effectively even to conditional generation settings. We also observe that increasing the number of correction steps improves generation quality when L is moderate. However, the gains diminish as L grows, becoming marginal for larger values of L.In fact, the sample quality may saturate and even degrade as L becomes large, due to stale correctors and accumulated random noise.
6
Conclusion
In this paper, we have developed an accelerated sampling algorithm for uniform-rate discrete diffusion models with provable convergence guarantees. Remarkably, our GADD algorithm achieved O(polylog(ε−1 )) convergence rate. The accelerated rates were achieved by a novel Gibbs-based corrector that constructs posterior conditionals directly from the score function, thus without requiring additional training. We also demonstrated the superiority of GADD over previous CTMC correctors, along with its effectiveness on real-data experiments. An interesting direction for future work is to develop a theoretical understanding of predictor-corrector methods for masked diffusion models.
Acknowledgements The work was supported in part by the U.S. National Science Foundation under the grants: NSF AI Institute (AI-EDGE) 2112471, ECCS-2413528, CNS-2312836, CNS-2223452, CNS-2225561, and was sponsored by the Army Research Laboratory under Cooperative Agreement Number W911NF-23-2-0225. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the Army Research Laboratory or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation herein.
References [1] Jascha Sohl-Dickstein, Eric Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsupervised learning using nonequilibrium thermodynamics. In Proceedings of the 32nd International Conference on Machine Learning, volume 37, pages 2256–2265, 2015. [2] Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. In Advances in Neural Information Processing Systems, volume 33, pages 6840–6851, 2020. [3] Jacob Austin, Daniel D. Johnson, Jonathan Ho, Daniel Tarlow, and Rianne van den Berg. Structured denoising diffusion models in discrete state-spaces. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, 2021. [4] Shen Nie, Fengqi Zhu, Zebin You, Xiaolu Zhang, Jingyang Ou, Jun Hu, Jun Zhou, Yankai Lin, Ji-Rong Wen, and Chongxuan Li. Large language diffusion models. In The Thirty-ninth Annual Conference on Neural Information Processing Systems, 2025. 11
[5] Clement Vignac, Igor Krawczuk, Antoine Siraudin, Bohan Wang, Volkan Cevher, and Pascal Frossard. Digress: Discrete denoising diffusion for graph generation. In The Eleventh International Conference on Learning Representations, 2023. [6] Chengyi Liu, Wenqi Fan, Yunqing Liu, Jiatong Li, Hang Li, Hui Liu, Jiliang Tang, and Qing Li. Generative diffusion models on graphs: methods and applications. In Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, 2023. [7] Andrew Campbell, Joe Benton, Valentin De Bortoli, Tom Rainforth, George Deligiannidis, and Arnaud Doucet. A continuous time framework for discrete denoising models. In Advances in Neural Information Processing Systems, 2022. [8] Amira Alakhdar, Barnabas Poczos, and Newell Washburn. Diffusion models in de novo drug design. Journal of Chemical Information and Modeling, 2024. [9] Hunter Nisonoff, Junhao Xiong, Stephan Allenspach, and Jennifer Listgarten. Unlocking guidance for discrete state-space diffusion and flow models. In The Thirteenth International Conference on Learning Representations, 2025. [10] Yang Song, Jascha Sohl-Dickstein, Diederik P. Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-based generative modeling through stochastic differential equations. In The Ninth International Conference on Learning Representations, 2021. [11] Yuhui Wu, Yuxin Chen, and Yuting Wei. Stochastic Runge-Kutta methods: Provable acceleration of diffusion models. arXiv preprint arXiv:2410.04760, 2024. [12] Yuchen Liang, Peizhong Ju, Yingbin Liang, and Ness Shroff. Broadening target distributions for accelerated diffusion models via a novel analysis approach. In The Thirteenth International Conference on Learning Representations, 2025. [13] Gen Li, Yuchen Zhou, Yuting Wei, and Yuxin Chen. Faster diffusion models via higher-order approximation. arXiv preprint arXiv:2506.24042, 2025. [14] Kaiwen Zheng, Yongxin Chen, Hanzi Mao, Ming-Yu Liu, Jun Zhu, and Qinsheng Zhang. Masked diffusion models are secretly time-agnostic masked models and exploit inaccurate categorical sampling. In International Conference on Learning Representations (ICLR), 2025. [15] Yixiu Zhao, Jiaxin Shi, Feng Chen, Shaul Druckmann, Lester Mackey, and Scott Linderman. Informed correctors for discrete diffusion models. In The Thirty-ninth Annual Conference on Neural Information Processing Systems, 2025. [16] Hyunjin Seo, Taewon Kim, Sihyun Yu, and SungSoo Ahn. Learning flexible forward trajectories for masked molecular diffusion. arXiv preprint arXiv: 2505.16790, 2025. [17] Xiaochen Zhang, Shuangxi Wang, Ying Fang, and Qiankun Zhang. Mg-diff: A novel molecular graph diffusion model for molecular generation and optimization. PLOS ONE, 2025. [18] Justin Deschenaux, Caglar Gulcehre, and Subham Sekhar Sahoo. The diffusion duality, chapter ii: ψ -samplers and efficient curriculum. arXiv preprint arXiv:2602.21185, 2026. [19] Zikun Zhang, Zixiang Chen, and Quanquan Gu. Convergence of score-based discrete diffusion models: A discrete-time analysis. In The Thirteenth International Conference on Learning Representations, 2025. 12
[20] Yuchen Liang, Yingbin Liang, Lifeng Lai, and Ness Shroff. Discrete diffusion models: Novel analysis and new sampler guarantees. In The Thirty-ninth Annual Conference on Neural Information Processing Systems, 2025. [21] Yinuo Ren, Haoxuan Chen, Yuchen Zhu, Wei Guo, Yongxin Chen, Grant M. Rotskoff, Molei Tao, and Lexing Ying. Fast solvers for discrete diffusion models: Theory and applications of high-order algorithms. In Frontiers in Probabilistic Inference: Learning meets Sampling, 2025. [22] 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. In The Thirteenth International Conference on Learning Representations, 2025. [23] Daniil Dmitriev, Zhihan Huang, and Yuting Wei. Efficient sampling with discrete diffusion models: Sharp and adaptive guarantees. arXiv preprint arXiv:2602.15008, 2026. [24] Giovanni Conforti, Alain Durmus, Le-Tuyet-Nhi Pham, and Gael Raoul. Non-asymptotic convergence of discrete diffusion models: Masked and random walk dynamics. arXiv preprint arXiv:2512.00580, 2025. [25] Le-Tuyet-Nhi Pham, Dario Shariatian, Antonio Ocello, Giovanni Conforti, and Alain Oliviero Durmus. Discrete Markov probabilistic models: An improved discrete score-based framework with sharp convergence bounds under minimal assumptions. In Forty-second International Conference on Machine Learning, 2025. [26] Hongrui Chen and Lexing Ying. Convergence analysis of discrete diffusion model: Exact implementation through uniformization. arXiv preprint arXiv:2402.08095, 2024. [27] Kelvin Kan, Xingjian Li, Benjamin J. Zhang, Tuhin Sahai, Stanley Osher, and Markos A. Katsoulakis. Dimension-free convergence of discrete diffusion models: Adjoint equations induce the right space. arXiv preprint arXiv:2605.17232, 2026. [28] Itai Gat, Tal Remez, Neta Shaul, Felix Kreuk, Ricky T. Q. Chen, Gabriel Synnaeve, Yossi Adi, and Yaron Lipman. Discrete flow matching. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. [29] Aaron Lou, Chenlin Meng, and Stefano Ermon. Discrete diffusion modeling by estimating the ratios of the data distribution. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 32819–32848, 2024. [30] Frank P. Kelly. Reversibility and Stochastic Networks. Cambridge University Press, 2011. [31] David A. Levin, Yuval Peres, and Elizabeth L. Wilmer. Markov Chains and Mixing Times (Second Edition). American Mathematical Society, 2017. [32] Xunpeng Huang, Difan Zou, Hanze Dong, Yi Zhang, Yian Ma, and Tong Zhang. Reverse transition kernel: A flexible framework to accelerate diffusion inference. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. [33] Yuchen Liang, Zhiheng Tan, Ness Shroff, and Yingbin Liang. Sharp convergence rates for masked diffusion models. arXiv preprint arXiv:2602.22505, 2026. [34] Hao-Wen Dong, Wen-Yi Hsiao, Li-Chia Yang, and Yi-Hsuan Yang. Musegan: Multi-track sequential generative adversarial networks for symbolic music generation and accompaniment. In Proceedings of the AAAI Conference on Artificial Intelligence, 2018. 13
[35] Yuchen Liang, Peizhong Ju, Yingbin Liang, and Ness Shroff. Theory on score-mismatched diffusion models and zero-shot conditional samplers. In The Thirteenth International Conference on Learning Representations, 2025. [36] Gen Li, Yu Huang, Timofey Efimov, Yuting Wei, Yuejie Chi, and Yuxin Chen. Accelerating convergence of score-based diffusion models, provably. In Proceedings of the 41st International Conference on Machine Learning, 2024. [37] Stuart Geman and Donald Geman. Stochastic relaxation, gibbs distributions, and the bayesian restoration of images. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1984. [38] Alireza Rezaei and Shayan Oveis Gharan. A polynomial time MCMC method for sampling from continuous determinantal point processes. In Proceedings of the 36th International Conference on Machine Learning, 2019. [39] Yves F. Atchadé. Approximate spectral gaps for markov chain mixing times in high dimensions. SIAM Journal on Mathematics of Data Science, 3(3):854–872, 2021. [40] Filippo Ascolani and Giacomo Zanella. Dimension-free mixing times of Gibbs samplers for Bayesian hierarchical models. The Annals of Statistics, 52(3):869 – 894, 2024. [41] Joseph Gonzalez, Yucheng Low, Arthur Gretton, and Carlos Guestrin. Parallel gibbs sampling: From colored fields to thin junction trees. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, 2011. [42] Jose Lezama, Tim Salimans, Lu Jiang, Huiwen Chang, Jonathan Ho, and Irfan Essa. Discrete predictorcorrector diffusion models for image synthesis. In The Eleventh International Conference on Learning Representations, 2023. [43] Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Language models are unsupervised multitask learners. OpenAI, 2019. [44] Wenda Chu, Zihui Wu, Yifan Chen, Yang Song, and Yisong Yue. Split gibbs discrete diffusion posterior sampling. arXiv preprint arXiv:2503.01161, 2025. [45] Hongrui Chen, Holden Lee, and Jianfeng Lu. Improved analysis of score-based generative modeling: user-friendly bounds under minimal smoothness assumptions. In Proceedings of the 40th International Conference on Machine Learning, 2023. [46] Sergey G. Bobkov and Prasad Tetali. Modified logarithmic Sobolev inequalities in discrete settings. Journal of Theoretical Probability, 19(2):289–336, 2006.
14
Appendix A Additional Related Works
15
B Variants of GADD and Posterior Likelihood Estimate
16
C Details of Numerical Experiments
17
C.1 Synthetic Experiment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
C.2 Text Experiment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
C.3 Music Experiment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
D Proof of Theorem 1
18
D.1 Step 1: Bounding Inner-loop Initialization Error . . . . . . . . . . . . . . . . . . . . . . . .
18
D.2 Step 2: Bounding Inner-loop Estimation Error . . . . . . . . . . . . . . . . . . . . . . . . .
19
D.3 Step 3: Combining all parts together . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
E Proof of Theorem 2
20
F Proofs of Auxiliary Lemmas
21
A
F.1
Proof of Lemma 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
F.2
Proof of Lemma 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
F.3
Proof of Lemma 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
24
F.4
Proof of Lemma 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
F.5
Proof of Lemma 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26
Additional Related Works
We present the most relevant related works in Section 1.2; additional references are now discussed below. Theory of Acceleration for Continuous Diffusion Samplers. A substantial body of theory has established accelerated convergence guarantees for continuous diffusion models, including both SDE and ODE solvers. Broadly, two main acceleration strategies have been explored. The first aims to more accurately approximate the continuous-time reverse process, for example by using higher-order numerical solvers such as RungeKutta methods or successive refinement (e.g., [11–13, 36]). The second acceleration strategy augments the diffusion process with a corrector step that steers particles toward the target distribution. This predictorcorrector paradigm has been widely adopted in empirical studies of both continuous and discrete diffusion models [7, 10]. From a theoretical perspective, [32] proposed the RTK-MALA and RTK-ULD algorithms, which incorporate Metropolis-Adjusted Langevin Algorithm (MALA) and Underdamped Langevin Dynamics (ULD) as correctors, respectively. Notably, RTK-MALA achieves a logarithmic convergence rate in ε−1 . 15
Theory on Gibbs Sampling. Since the seminal work of [37], Gibbs samplers have been shown to be effective across a wide range of applications, including sampling from graphical models, feasible sets of graph coloring problems [31], determinantal point processes [38], mixtures of densities [39], and Bayesian hierarchical models [40]. An orthogonal line of work studies the parallelization of Gibbs samplers under specific graph structures [41]. Notably, all of these works assume access to the exact posterior likelihood, whereas in diffusion-based settings the posterior must be estimated, introducing additional challenges that are not addressed by existing analyses. Empirical Studies on the Acceleration of Masked Diffusion Models. Beyond acceleration for uniform-rate models, several empirical studies have focused on masked diffusion models. [42] constructed a discrete MCMC transition path for correction and learns a separate corrector kernel. More recently, [15] proposed an informed correction strategy. Notably, these approaches are primarily empirical and do not provide theoretical convergence guarantees. We now discuss [15] in more detail. That work employs an informed Gibbs corrector specifically tailored to masked (i.e., absorbing-rate) diffusion models, whereas our work focuses on the uniform-rate setting. While both of their and our approaches utilize Gibbs-type correctors, uniform-rate diffusion models pose distinct algorithmic challenges. In particular, the score functions in uniform-rate models need to be estimated differently from those in masked diffusion, where the masked score (i.e., a time-scaled clean-data distribution) naturally facilitates Gibbs updates. In contrast, our method relies on posterior likelihood estimators specifically designed for uniform-rate models (e.g., (6) and (8)), enabling principled Gibbs corrections in this setting.
B
Variants of GADD and Posterior Likelihood Estimate
In this section, we provide some variants of both the GADD algorithm in Algorithm 1 and the posterior estimator in (6). We first provide a systematic-scan variant of Algorithm 1 as follows. Algorithm 2: GADD with Systematic-scan Gibbs Correctors Input: initialization xtN ∼ pinit , discretization points {tk }N k=0 (with tN = T and t0 = δ ), estimated score N s, correction steps {Lk }k=0 2 for k = N − 1 to 0 do 3 z0 = the output of the Euler update given xtk+1 (using (2)) ; 4 for ℓ = 1 to Lk do −i 5 Construct posterior q̂tik (·|zℓ−1 ) for each i ∈ [d] (e.g., using (6) or (8)); i i 6 Resample zℓ ∼ q̂tk for each i ∈ [d]; 7 end 8 xtk = zLk ; 9 end Return: xt0 Notably, since the score network outputs density-ratio scores for all i ∈ [d] in a single forward pass, this modification does not incur any additional NFE per corrector step. Next we provide variants of some posterior likelihood estimators. While (6) is one possible estimator for the posterior likelihood from the trained score, such a construction is not unique. Notice that, for any y i ∈ [S], qt (xi |x−i ) qt (x) qt (y i |x−i ) qt (x−i ⊕i y i ) i i −i . qt (x |x ) = P =P qt (xi |x−i ) qt (x) xi ∈[S] qt (y i |x−i ) xi ∈[S] qt (x−i ⊕i y i )
16
Here the last equality again follows from Bayes’ rule. Thus, another estimator is, by fixing any y i ∈ [S], st (x, x−i ⊕i y i ) , −i ⊕ y i ) i xi ∈[S] st (x, x
q̂ti (xi |x−i ) = P
or, with averaging, q̂ti (xi |x−i ) =
1 X s (x, x−i ⊕i y i ) P t . −i ⊕ y i ) S i i xi ∈[S] st (x, x
(8)
y ∈[S]
With a similar argument, another estimator is −i ⊕ y i ) i y i ∈[S] st (x, x P q̂ti (xi |x−i ) = P . −i ⊕i y i ) y i ∈[S] xi ∈[S] st (x, x
P
C
Details of Numerical Experiments
In this section, we provide more details on our synthetic and real-data experiments in Table 2. For the real-data experiments, we use a Google H100 GPU during training and L4 GPU during sampling.
C.1
Synthetic Experiment
For the left figure of Figure 1, we consider a synthetic autoregressive-type data model, where the likelihood of each token depends on the preceding h = 2 tokens. We choose the hyperparameters (e.g., Lk in GADD) such that the number of function evaluations (NFE) is the same across all methods. The final errors are averaged over 10000 Monte Carlo runs. For the right figure of Figure 1, we consider a mixed-point model in which the initial distribution is a sparse mixture of singletons, with support size on the order of O(d). Again, the final errors are averaged over 10000 Monte Carlo runs.
C.2
Text Experiment
The sequence length is d = 128 and the dictionary size is S = 50257. We adopt the small SEDD Uniform model [29] with σmin = 10−4 and σmax = 20. For optimization, we use Adam with a learning rate of 3 × 10−3 , β1 = 0.9, and β2 = 0.999, and apply a linear warm-up over the first 2500 steps. We train the model for a total of 111K steps. For evaluation, we use the typical GPT-2 model obtained from the HuggingFace library [43]. For sampling, we use the Euler method as the backbone across all methods. All reported results are averaged over 10 independent runs. For the θ-Trapezoidal method [21], we fix θ = 0.5. For the CTMC correctors [7], we apply one correction step with a step size set to 1.5× that of the Euler discretization, as suggested in their original paper. For GADD, we employ two techniques similar to those in [15]. First, we use parallel Gibbs sampling, where the score function is not re-evaluated after each token update. Specifically, we randomly select one token to update at each step, without re-evaluating the score. This significantly reduces NFEs, while incurring only a minor performance degradation when Lk is small. We choose Lk = 40 in our experiment. Second, we update only tokens whose estimated probabilities fall below a fixed threshold, which is set to 0.1 in our experiments.
C.3
Music Experiment
The sequence length is d = 256 and the dictionary size is S = 129. We use the dataset in [7] with the pre-trained SEDD Uniform model from [44]. 17
For sampling, we condition on the first 100 tokens of each sequence. We fix the number of function evaluations (NFE) to 16 across all methods. During sampling, the conditioned tokens are strictly enforced after each predictor and corrector step. For GADD, instead of randomly sampling from one token location, we use systematic update over all tokens. Again, we only perform correction when the current probability is below the threshold. For evaluation, we use the test set that consist of 200 music pieces. As in [7], the mean-histogram metric compares the Hellinger distance between the histograms from the true and generated samples. As an additional metric, we report the prediction error rate over the next F = 4 tokens to assess short-term temporal consistency. To compute sequence perplexity, we train a separate autoregressive (AR) model on the dataset in [7]. The model uses nhead = 8, with 6 Transformer layers. The feed-forward dimension is set to 1024, with dropout rate 0.1. The model is trained using a learning rate of 3 × 10−4 for 400 epochs.
D
Proof of Theorem 1
Overall, the error in Algorithm 1 arises from four distinct sources: 1. the outer-loop (or grand) initialization error at the start of the algorithm; 2. the inner-loop initialization error at the beginning of each Gibbs sampling phase; and 3. the inner-loop error resulting from imperfect score estimation. We analyze each of these error components separately and then combine them to derive the overall convergence guarantee for Algorithm 1. To begin, the following result gives us an upper bound on the grand (i.e., outer-loop) initialization error. From [19, Proposition 2] and [22, Theorem C.1], the initialization error satisfies that KL(q⃗0 ||p0 ) ≲ (d log S)e−T .
Thus, by Pinsker’s inequality, we have TV(pinit , qT ) ≲
D.1
p
(i) p
KL(pinit ||qT ) ≲
d log S · e−T /2 .
(9)
Step 1: Bounding Inner-loop Initialization Error
Our next result concerns the inner-loop initialization error. Specifically, we ask if the error at the end of the previous step is sufficiently small, how large the error will be at the start of the current step. Intuitively, this error remains small due to the smoothness of the diffusion process, which in turn yields a warm-up condition. Lemma 1. Fix adjacent steps s < t such that t − s = o(1). Suppose that TV(p̂T −t,L , qt ) ≤ ε. Then, for the uniform-rate CTMC, under Assumption 2 and with the Euler update, we have TV(pT −s,0 , qs ) ≲ (t − s)d(M + S max{1, s−1 }) + ε.
Proof. See Section F.1. Note that this result readily extends to predictors beyond the Euler predictor, provided that t − s = o(1) and the transition rates remain bounded. 18
D.2
Step 2: Bounding Inner-loop Estimation Error
Before we start to analyze the estimation error, we recall the triangle inequality for the TV distance: TV(qt , p̂T −t,L ) ≤ TV(qt , pT −t,L ) + TV(p̂T −t,L , pT −t,L ).
(10)
Here the second term is regarding the estimation error, which we analyze below. In particular, Lemma 2 considers the error propagation in general random-scan Gibbs samplers with target distribution π . Lemma 2. Recall the random-scan Gibbs sampler in (3). Given a mismatched Gibbs kernel π̂ that satisfies max Ei∼wi Ez∼pℓ TV(π̂ i (·|z −i ), π i (·|z −i )) ≤ ϵ,
ℓ=1,...,L
we have TV(p̂L , pL ) ≤ Lϵ.
Proof. See Section F.2. Now, we specialize Lemma 2 to the case of uniform-rate discrete diffusion models, with the estimator in (6) and under Assumption 1. Lemma 3. Fix t ∈ [δ, T ] and the target π = qt . Consider the estimator in (6). Consider the uniform-rate CTMC, and suppose that Assumptions 1 and 2 hold, then TV(p̂T −t,L , pT −t,L ) ≲ LM εest . Proof. See Section F.3. To show that our proof does not depend on the estimator in (6), we have the following result which uses instead the estimator in (8). Lemma 4. Under the same conditions as in Lemma 3, but instead consider the estimator in (8). Then, TV(p̂T −t,L , pT −t,L ) ≲ LM 2 εest . Proof. See Section F.4. Since the only difference is in the polynomial order of M , and the final dependence on M is only logarithmic, the same convergence rate will hold for the estimator in (8). For this reason, we will only focus on the estimator in (6) in the following.
D.3
Step 3: Combining all parts together
We are now ready to bring the pieces together. Suppose we choose T ≍ log(d(log S)/ε2 ), by (9), the grand initialization error satisfies TV(pinit , qT ) ≤ ε. −1 Also, when we choose κ ≍ log log(d/ε2 ) , the total number of outer-loop steps satisfies that (cf. [45]) N≍
T + log δ −1 ≲ log log(d/ε2 ) (log(d/ε2 ) + log δ −1 ). κ
Next we use an inductive argument by inducting on k = N − 1, . . . , 0. Suppose, for purpose of induction, that we already have TV(p̂T −tk+1 ,Lk+1 , qtk+1 ) ≲ Lk+1 ε. Then, at step k , by Lemma 1 and under Assumption 2, we have TV(pT −tk ,0 , qtk ) ≲ κd(M + S max{1, t−1 k }) + Lk+1 ε.
19
We now consider two sources of errors. The first is one that comes from the Gibbs sampling process. Following from standard analysis (cf. (4)), TV(pT −tk ,Lk , qtk ) ≤ W1 (pT −tk ,Lk , qtk ) ≤ (1 − ρtk )Lk W1 (pT −tk ,0 , qtk ) ≤ (1 − ρtk )Lk d · TV(pT −tk ,0 , qtk ).
Thus, in order for TV(pT −tk ,Lk , qtk ) ≲ ε, it suffices to have log dε · TV(pT −tk ,0 , qtk ) Lk ≍ ρtk ≲
log log
≲
−1 d ε · (κd(M + S max{1, tk }) + Lk+1 ε)
ρ tk
2
d −1 ε (M + Sδ )
. ρtk The second error comes from score estimation. From Lemma 3 and under Assumptions 1 and 2, we have TV(p̂T −tk ,Lk , pT −tk ,Lk ) ≲ Lk M εest .
Thus, the total error at step k is TV(p̂T −tk ,Lk , qtk ) ≤ TV(pT −tk ,Lk , qtk ) + TV(p̂T −tk ,Lk , pT −tk ,Lk ) ≲ ε + Lk M εest .
As long as εest = O(ε/M ), this verifies the inductive hypothesis. ρ Therefore, when εest = O Mt0 ε , we have TV(p̂T −δ,L0 , qδ ) ≲ ε. Meanwhile, the total number of steps satisfy (with δ ≍ dε ): 0 X
Ntotal = N +
Lk
k=N −1
≲
0 log X k=N −1
≲ log(d/ε2 )
3
d2 d ε2 S + ε M
ρtk 3 2 log dε2 S + dε M ρ∗
.
The proof is now complete.
E
Proof of Theorem 2
Fix the outer-loop step tk . Different from Gibbs sampling, the corrector CTMC is a (time-homogeneous) continuous-time process indexed by a continuous variable, denoted as τ (note that this is different from the outer-loop index t). Also, let the terminal time for the corrector CTMC be Tk , and let the corrector step-size be ηk . (Here we do not need to shrink step-sizes towards the end because the CTMC rate is regular.) Note that Lk = Tk /ηk . We write p̃T −tk ,τ as the (ideal and clean) continuous-time sampling probability at continuous-time τ . As before, the quantity of interest is TV(p̂T −tk ,Lk , qtk ). We first decompose the total error as TV(p̂T −tk ,Lk , qtk ) ≤ TV(p̃T −tk ,Tk , qtk ) + TV(p̂T −tk ,Lk , p̃T −tk ,Tk ).
20
(11)
Here the first term is the typical convergence error of a CTMC with time-homogeneous rate matrix. Classical results [46, Corollary 2.8] have established that, for any initial distribution pT −tk ,0 , TV(p̃T −tk ,Tk , qtk )2 ≤ 2 log
1 · e−2µk Tk ≲ d(log S)e−2µk Tk , minx qtk (x)
where µk is the modified log-Sobolev constant of the rate matrix Rkc . Since the reverse rate R⃗tk ultimately depends on the underlying target distribution qtk , µk is also data-dependent, but it is independent of the target accuracy ε. We now consider the second term in (11), which corresponds to the discretization error. The result is included in the following lemma. While we only consider the case without estimation error for simplicity, it can be easily adapted to the more general case with standard decomposition (e.g., [20]). Lemma 5. Suppose that there is no estimation error. Under Assumption 2 and using the τ -leaping or the Euler method, we have KL(p̃T −tk ,Tk ||pT −tk ,Lk ) ≲ ηk Tk d2 M 2 log(M S). Proof. See Section F.5. Therefore, continuing from (11), with perfect estimation, we have p p TV(pT −tk ,Lk , qtk ) ≲ d(log S)e−µk Tk + ηk Tk d2 M 2 log(M S). In order to have TV(pT −tk ,Lk , qtk ) ≲ ε, it suffices to have ! p d(log S) ε2 −1 , ηk = Θ̃ µk 2 2 , Tk = O µk log ε d M 2 2 which implies that Lk = O dµ2Mε2 . Then, with the same outer-loop step-sizes as in Theorem 1 and following k similar analyses, we have (ignoring log-dependencies) 0 X
Ntotal = N +
Lk ≲
k=N −1
d2 M 2 . µ2∗ ε2
Thus, even without estimation error, we have Ntotal = poly(ε−1 ).
F
Proofs of Auxiliary Lemmas
We provide proofs for all helping lemmas in this section.
F.1
Proof of Lemma 1
Write κ := t − s. We first note that when κ = o(1), qt|s (x|z) = 1 {x = z} + R(z, x)κ + o(κ).
Thus, we have qt (x) = qs (x) =
P
z qt|s (x|z)qs (z)
qs (x) P qs (x) + κR(x, x)qs (x) + κ z̸=x R(z, x)qs (z) + o(κ) qs (x)
21
(i) qs (x) + κR(x, x)qs (x) + κ
P
=
z:Ham(z,x)=1 R(z, x)qs (z) + o(κ)
qs (x)
X
= 1 + κR(x, x) + κ
R(z, x)
z:Ham(z,x)=1
qs (z) + o(κ). qs (x)
(12)
Here for (i) we note that R(z, x) = 0 if Ham (z, x) ≥ 2. Another helpful relationship is regarding the (Euler) update from p̂T −t,L to pT −s,0 , as follows. Indeed, Q such an update is coordinate-wise independent as pT −s|T −t (xs |xt ) = di=1 piT −s|T −t (xis |xit ). Further, from (2), piT −s|T −t (xis |xit ) = R̂Ti −t (xit , xis )(t − s) whenever xis ̸= xit . Thus, under Assumption 2, we have piT −s|T −t (xis |xit ) ≲ M S −1 (t − s). Also define the probability δ i (xis |xit ) = 1 only when xis = xit , and let Q δ(xs |xt ) = di=1 δ i (xis |xit ). Then, TV(pt , ps ) ≤ Ext ∼pt TV(δ(·|xt ), pT −s|T −t (·|xt )) " d # X ≤ Ext ∼pt TV(δ i (·|xit ), piT −s|T −t (·|xit )) i=1
≲ dM (t − s).
(13)
With the results above, we have TV(pT −s,0 , qs ) ≤ TV(qt , qs ) + TV(p̂T −t,L , qt ) + TV(p̂T −t,L , pT −s,0 ) qs (x) 1 − 1 + TV(p̂T −t,L , qt ) + TV(p̂T −t,L , pT −s,0 ) = Ex∼qt 2 qt (x) (ii) X qs (z) + ε + dM κ R(z, x) ≲ κ · max R(x, x) + x qs (x) z:Ham(z,x)=1
(iii)
≲ κd(M + S max{1, s−1 }) + ε,
(14)
where (ii) follows from (12), (13) and the error assumption at time t, and (iii) follows from the typical score upper-bound as in [20, Lemma 2]. The proof is now complete.
F.2
Proof of Lemma 2
First, note that with random-scan Gibbs sampler, for x and y which only differ on the i-th index, we have pℓ+1|ℓ (y|x) = wi π i (y i |x−i ),
p̂ℓ+1|ℓ (y|x) = wi π̂ i (y i |x−i ).
Thus, TV(p̂L , pL ) =
1X |p̂L (zL ) − pL (zL )| 2 z L
= ≤
1X X 2 z L 1 X 2 z ,z L
p0 (z0 ) p̂L|0 (zL |z0 ) − pL|0 (zL |z0 )
z0
p0 (z0 ) p̂L|0 (zL |z0 ) − pL|0 (zL |z0 ) ,
0
where the last line follows from Jensen’s inequality. Here the inner difference can be upper-bounded as p̂L|0 (zL |z0 ) − pL|0 (zL |z0 )
22
(i)
=
X
p̂L|1 (zL |z1 )p̂1|0 (z1 |z0 ) − pL|1 (zL |z1 )p1|0 (z1 |z0 )
z1
≤
X
X p1|0 (z1 |z0 ) p̂L|1 (zL |z1 ) − pL|1 (zL |z1 ) , p̂L|1 (zL |z1 ) p̂1|0 (z1 |z0 ) − p1|0 (z1 |z0 ) + z1
z1
{z
|
}
T1
{z
|
}
T2
where (i) follows because the Gibbs update step is Markov. Here note that for T2 , with Jensen’s inequality, X 1 X 1 X p0 (z0 )T2 = p0 (z0 ) p1|0 (z1 |z0 ) p̂L|1 (zL |z1 ) − pL|1 (zL |z1 ) 2 z ,z 2 z ,z z1 L 0 L 0 X 1 p0 (z0 )p1|0 (z1 |z0 ) p̂L|1 (zL |z1 ) − pL|1 (zL |z1 ) ≤ 2 z ,z ,z L 0 1 1 X p1 (z1 ) p̂L|1 (zL |z1 ) − pL|1 (zL |z1 ) = 2 z ,z L
1
which establishes a recursive relationship. For the first term, we use the following helpful relationship: for arbitrary functions q1 (x), q2 (x), a(x) such that a(x) ≥ 0, X
(q1 (x) − q2 (x)) a(x)
x
≤ =
X
(q1 (x) − q2 (x)) a(x) +
X
x:q1 ≥q2
x:q1 ≤q2
X
X
(q1 (x) − q2 (x)) a(x) +
x:q1 ≥q2
(q2 (x) − q1 (x)) a(x)
(q2 (x) − q1 (x)) a(x)
(since a(x) > 0).
x:q1 ≤q2
Thus, since p̂L|1 ∈ (0, 1], X 1 X 1 X p0 (z0 )T1 = p0 (z0 ) p̂L|1 (zL |z1 ) p̂1|0 (z1 |z0 ) − p1|0 (z1 |z0 ) 2 z ,z 2 z ,z z1 L 0 L 0 X 1 X ≤ p0 (z0 ) p̂L|1 (zL |z1 ) p̂1|0 (z1 |z0 ) − p1|0 (z1 |z0 ) 2 z ,z z1 :p̂1|0 ≥p1|0 L 0 X + p̂L|1 (zL |z1 ) p1|0 (z1 |z0 ) − p̂1|0 (z1 |z0 ) z1 :p̂1|0 ≤p1|0
=
1X 2 z
p0 (z0 )
X
p̂1|0 (z1 |z0 ) − p1|0 (z1 |z0 )
z1 :p̂1|0 ≥p1|0
0
X
+
p1|0 (z1 |z0 ) − p̂1|0 (z1 |z0 )
z1 :p̂1|0 ≤p1|0
=
1X 2 z ,z 0
p0 (z0 ) p̂1|0 (z1 |z0 ) − p1|0 (z1 |z0 ) .
1
23
Combining two terms and providing upper-bounds recursively, we get L−1 XX X 1 TV(p̂L , pL ) ≤ pℓ (zℓ ) p̂ℓ+1|ℓ (zℓ+1 |zℓ ) − pℓ+1|ℓ (zℓ+1 |zℓ ) 2 zℓ+1 ℓ=0 zℓ ! L−1 d XX X 1X i π̂ (a|zℓ ) − π i (a|zℓ ) = pℓ (zℓ ) wi 2 a z ℓ=0
(15)
i=1
ℓ
≤ Lεest .
The proof is now complete.
F.3
Proof of Lemma 3
We first fix i ∈ [d] and x−i . We have TV(q̂ti (·|x−i ), qti (·|x−i )) 1 X i = q̂t (a|x−i ) − qti (a|x−i ) 2 a∈[S] −1 X X 1 st (x−i ⊕i y i , x−i ⊕i a) − qti (a|x−i ) = 2 i y ∈[S]
a∈[S]
1 1 X i P qt (a|x−i ) i −1 −i 2 qt (a|x ) yi ∈[S] st (x−i ⊕i y i , x−i ⊕i a) a∈[S] −1 X X 1 X i 1 qt (a|x−i ) i − st (x−i ⊕i y i , x−i ⊕i a) st (x−i ⊕i y i , x−i ⊕i a) = 2 qt (a|x−i ) i i =
y ∈[S]
a∈[S]
(i)
≤ M S −1 ·
X 1 1 X i − st (x−i ⊕i y i , x−i ⊕i a) qt (a|x−i ) i −i 2 qt (a|x ) i y ∈[S]
a∈[S]
≤ M S −1 ·
y ∈[S]
1 X 2
a∈[S]
X qt (x−i ⊕i y i ) qti (a|x−i ) − st (x−i ⊕i y i , x−i ⊕i a) , −i ⊕ a) q (x t i i
(16)
y ∈[S]
where (i) follows because, for each a, −1
X
st (x−i ⊕i y i , x−i ⊕i a) ≥ M −1 S =⇒
X
st (x−i ⊕i y i , x−i ⊕i a)
≤ M S −1 .
y i ∈[S]
y i ∈[S]
With the above, we now specialize the condition of Lemma 2 to the case where estimation error arises from inaccurate diffusion scores. For each i ∈ [d] and ℓ ∈ L, we have Ex∼pT −t,ℓ TV(π̂ i (·|x−i ), π i (·|x−i )) X X qt (x−i ⊕i y i ) i −i ≲ M S −1 Ex−i ∼p−i q (a|x ) − st (x−i ⊕i y i , x−i ⊕i a) t −i ⊕ a) T −t,ℓ q (x t i i y ∈[S]
a∈[S]
= M · Ex−i ∼p−i Ea∼qt (·|x−i ) T −t,ℓ
X
Rt (y, x)
y i ∈[S]
24
qt (x−i ⊕i y i ) − st (x−i ⊕i y i , x−i ⊕i a) qt (x−i ⊕i a)
≤ M εest
where the last line follows from Assumption 1. The proof is now complete.
F.4
Proof of Lemma 4
The proof is very similar to Section F.3, except with a slightly different upper bound on the per-step posterior mismatch. We use the estimator from (8) such that 1 X s (x, x−i ⊕i y i ) P t q̂ti (xi |x−i ) = . −i ⊕ y i ) S i i xi ∈[S] st (x, x y ∈[S]
Also note that
qt (x) qt (x−i ⊕i y i ) . P qt (x) S i i −i i x ∈[S] qt (x ⊕i y ) y ∈[S]
1 qti (xi |x−i ) =
X
Again we fix i ∈ [d] and x−i . Then, we have TV(q̂ti (·|x−i ), qti (·|x−i )) 1 X i = q̂t (a|x−i ) − qti (a|x−i ) 2 a∈[S]
qt (x)
1 X 1 X s (x, x−i ⊕i y i ) q (x−i ⊕i y i ) P t ≤ −P t −i i qt (x) 2 i S i ⊕i y ) xi ∈[S] st (x, x i −i i x ∈[S]
≤
x ∈[S] qt (x
y ∈[S]
⊕i y )
1 X 1 X 1 st (x, x−i ⊕i y i ) P −P −i ⊕ y i ) 2 i S i i xi ∈[S] st (x, x i x ∈[S]
+
qt (x) x ∈[S] qt (x−i ⊕i y i )
y ∈[S]
1 X 1 X P 2 i S i i x ∈[S]
1
1
qt (x) x ∈[S] qt (x−i ⊕i y i )
y ∈[S]
st (x, x−i ⊕i y i ) −
qt (x) qt (x−i ⊕i y i )
X 1 X 1 st (x, x−i ⊕i y i ) P − qti (y i |x−i ) −i ⊕ y i ) 2 i S i s (x, x i t i x ∈[S]
(i) 1
=
x ∈[S]
y ∈[S]
1 X 1 X i i −i qt (x) + qt (y |x ) st (x, x−i ⊕i y i ) − 2 i S i qt (x−i ⊕i y i ) x ∈[S] y ∈[S] −1 X X (ii) 1 st (x−i ⊕i y i , x−i ⊕i a) − qti (a|x−i ) ≤ M 2 i y ∈[S]
a∈[S]
+
X 1 1 X i qt (x−i ⊕i y i ) · qt (a|x−i ) st (x−i ⊕i y i , x−i ⊕i a) − 2 S qt (x−i ⊕i a) i y ∈[S]
a∈[S]
(iii)
≤ M 2 S −1 ·
1 X 2
qti (a|x−i )
X qt (x−i ⊕i y i ) − st (x−i ⊕i y i , x−i ⊕i a) , −i ⊕ a) q (x t i i
y ∈[S]
a∈[S]
where (i) follows because 1 qt (x) xi ∈[S] qt (x−i ⊕i y i )
P
1
=P
qti (xi |x−i ) xi ∈[S] qti (y i |x−i )
25
= qti (y i |x−i ),
(ii) follows from Assumption 2 and by relabeling (xi , y i ) as (y i , a), and (iii) follows from the proof of Lemma 3 (see (16)). Compared with (16), the only difference is in the extra M constant (that arises from normalization). The rest of the proof follows in the same manner as that of Lemma 3, and the proof is complete.
F.5
Proof of Lemma 5
The proof follows similar to [20, Theorem 2], but with several key differences. In particular, [20, Theorem 2] is specialized to the predictor error in the outer-loop CTMC. In such a case, the analyzed reverse CTMC has a corresponding forward process that provides nice geometric properties (e.g., dimension-wise factorization used in [20, Lemma 2]). This is different from our case with the corrector CTMC, which does not have such nice properties. On the other hand, different from the time-inhomogeneous reverse CTMC, the corrector CTMC has a time-homogeneous rate that helps the analysis. We will omit all subscript k whenever obvious. Define R̂τc as the rate corresponding to the discretized sampling process at time τ . For τ ∈ [ηk ℓ, ηk (ℓ + 1)], given the current state xηk ℓ , we have R̂τc (xηk ℓ , ·) = Rηc k ℓ (xηk ℓ , ·). (Note that they are not equal for arbitrary state x within the time duration, cf. [20].) Also note that p̃T −tk ,0 = pT −tk ,0 . Recall the definition of Rc in (7). Under Assumption 2, a useful upper bound for Rc is that, ∀x ̸= y , Rc (x, y) = Rtk (x, y) + R̂tk (x, y) = Rtk (x, y) + Rtk (y, x)stk (y, x) ∈ S −1 (1 + M −1 ), S −1 (1 + M ) .
(17)
Also note that Rc (x, y) = 0 whenever Ham (x, y) ≥ 2. Since this bound is uniform over (x, y), from [7, Appendix B.5], we also have the same uniform upper bound for R̂τc (x, y) as R̂τc (x, y) ∈ S −1 (1 + M −1 ), S −1 (1 + M ) . Now, [20, Theorem 1] implies that KL(p̃T −tk ,Tk ||pT −tk ,Lk ) LX k −1 Z ηk (ℓ+1) c (x , y) X R τ dτ R̂τc (xτ , y) − Rc (xτ , y) + Rc (xτ , y) log ≤ Exτ ∼p̃T −tk ,τ c R̂ (x , y) τ τ ℓ=0 ηk ℓ y:y̸=xτ {z } | =:gτ (xτ )
(i)
=
LX k −1 Z ηk (ℓ+1) ℓ=0
ηk ℓ
E xτ ∼p̃T −tk ,τ [gτ (xτ ) − gτ (xηk ℓ )] dτ xηk ℓ ∼p̃T −tk ,ηk ℓ
where (i) follows because gτ (xηk ℓ ) = 0. Here note that E [gτ (xτ ) − gτ (xηk ℓ )] " # X = Exηk ℓ ∼p̃T −tk ,ηk ℓ p̃T −tk ,τ |ηk ℓ (xτ |xηk ℓ )gτ (xτ ) − gτ (xηk ℓ ) xτ
≲ Exηk ℓ ∼p̃T −tk ,ηk ℓ
" X
# c
(1 {xτ = xηk ℓ } + R (xηk ℓ , xτ )(τ − ηk ℓ)) gτ (xτ ) − gτ (xηk ℓ )
xτ
= (τ − ηk ℓ) · Exηk ℓ ∼p̃T −tk ,ηk ℓ
X
xτ :Ham(xτ ,xηk ℓ )=1
26
Rc (xηk ℓ , xτ )gτ (xτ )
(ii)
M · dM log(SM ), S where in (ii) we have used the uniform upper bound for Rc in (17) and that for gτ (x) as follows:
≲ (τ − ηk ℓ) · (dS) ·
X
|gτ (x)| =
R̂τc (x, y) − Rc (x, y) + Rc (x, y) log
y:y̸=x
X
≤
Rc (x, y) R̂τc (x, y)
R̂τc (x, y) + |Rc (x, y)| + |Rc (x, y)| · log
y:Ham(x,y)=1
≲ d(S − 1) ·
M log(SM ). S
Thus, KL(p̃T −tk ,Tk ||pT −tk ,Lk ) 2
≲ d SM log(SM ) ≲ d2 SM log(SM )
LX k −1 Z ηk (ℓ+1) ℓ=0 LX k −1 ℓ=0
2
2
= ηk Tk d M log(SM ).
The proof is now complete.
27
ηk ℓ
ηk2
(τ − ηk ℓ)dτ
Rc (x, y) R̂τc (x, y)