Absorb and Converge: Provable Convergence Guarantee for Absorbing Discrete Diffusion Models

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

Q1: Weakness and question on the value and significance of studying $\tau$-leaping and uniformization algorithms in the setting of absorbing discrete diffusion models.

A1: We respectfully disagree with the reviewer. The references cited by the reviewer do not appear to support the claim that the algorithms studied in our paper are not used very often in the setting of absorbing discrete diffusion models. In practice, $\tau$-leaping-like samplers—such as the Euler method and Tweedie $\tau$-leaping—have been employed in various works under absorbing settings (e.g., [3–4]), including the references [1] and [2] provided by the reviewer. Our reading of [1] and [2] suggests that sampling in those works is not performed in exactly $d$ steps, as asserted. In both papers’ discrete diffusion models, during each sampling step, there is a non-zero probability for a mask state to remain as mask, yielding the total number of steps (much) greater than $d$ (i.e., not “exact”). Such non-“exact-step” sampling is also indicated by their empirical experiments as well. For example, in [1, Table 3], the number of sampling steps reaches up to 4096, exceeding the window length of $d = 1024$. Similarly, in [2, Table 6], with a window size of $d = 1024$ tokens, the number of steps can go up to 10,000.

Comparison between exact samplers and $\tau$-leaping-like samplers: Since exact samplers are often in autoregressive-type masked language models, we refer to it as MLM in our following discussion, and use DDM to denote the discrete diffusion model with $\tau$-leaping type samplers. While MLMs offer certain advantages such as no discretization and initialization errors and a deterministic number of sampling steps (e.g., $d$ steps), there are several fundamental reasons why they may still underperform compared to DDMs in certain settings. (1) DDMs sample tokens iteratively based on a learned reverse process that models dependencies across all tokens and time steps. In contrast, MLMs often rely on shallow, single-step predictions for each masked token, limiting their ability to model long-range or high-order dependencies in a globally consistent manner. For example, [11] shows that DDMs can model structured sequences more effectively than autoregressive or MLM-type methods, due to the ability to revise and refine generations. (2) The deterministic $d$-step schedule in MLMs may not optimally align with the complexity of the generation task. DDMs allow adaptive generation paths, e.g., more steps for difficult tokens, enabling finer-grained control and potentially better outputs. [12] reveals that MLMs allocate separate representational dimensions to [MASK] tokens, limiting downstream expressiveness and overall performance.

Overall, the current literature continues to actively explore and compare exact samplers in MLMs and $\tau$-leaping-like samplers in DDMs. As far as we can tell, there is no conclusive evidence that one method consistently outperforms the other (e.g., [10, Table 3]). Therefore, we believe both sampling techniques offer valuable and complementary perspectives, and hence both warrant continued theoretical and empirical investigation.

Our another motivation: We further note that another motivation for us is to theoretically understand and justify the benefits of using absorbing rate over uniform rate, as empirically observed in [3]. To this end, we choose the same set of samplers ($\tau$-leaping and uniformization) as those typically used for the uniform rate. Overall, we show improved rates of these samplers on absorbing rates over uniform-rate counterparts.

A side note regarding [6]: [6] does not seem to have an explicit result that characterizes the dependence of $d$. It is unclear whether the sampling is in terms of $\tilde{O}(\sqrt{d})$ steps.

Q2.1: Question on the noise schedule.

A2.1: In our study, we follow many prior works (under the uniform rate) in assuming time-homogeneity (e.g., [7-9], which study uniform discrete diffusion models). This allows for a more direct comparison on the rate matrices by controlling for other parameter differences, such as the noise schedule. While it might be helpful to introduce a non-homogeneous noise schedule to tackle the initialization error, both the discretization error and the estimation error will be affected, which may possibly worsen the overall convergence rate.

Q2.2: Question on notation in Lem. 1.

A2.2: To clarify, our $q_{0|t}^j(y^j|x)$ in Lemma 1 is different from the “clean-data distribution” as in [1, Theorem 1]. While their “clean-data distribution” does not depend on $t$, ours is the posterior distribution of $x_0^j=y^j$ given that $x_t = x$ (notably, at time $t$), which obviously depends on $t$.

Now we argue that $q_{0|t}^j(y^j|x)$ must depend on $t$ in general in the following example. Suppose that the score function is well-defined at $t=0$ (i.e., finite for every pair of x and y having Hamming distance 1). (Necessarily, this implies that [MASK] exists in the training data.) Then, since the time-dependent coefficient $e^{-t}/(1-e^{-t})$ blows up as $t \to 0$, the other term in the multiplication must also depend on $t$ so that the overall product remains a finite quantity.

Q3: Question on score entropy loss.

A3: We will clarify this point in the revised draft. In particular, we will change the previous one to “training loss” and add the following sentence: “In practice, for tractable training, the denoising score entropy is usually used, which is a variant of the score entropy [9].”

Q4: Question on the lacking of clipping step in $\tau$-leaping discussed in Sec. 2.

A4: Indeed, in practice, an additional clipping step is necessary to avoid boundary crossing behaviors. As shown in [7], such a step does not affect the convergence rate given sufficiently small step-sizes (cf. [7, Remark A.13]). We will add this piece of clarification in the footnote when introducing the sampler.

Q5: Question on Assump. 4.

A5: To clarify, our main theoretical guarantees with early-stopping (i.e., Theorems 2–3) do not rely on Assumption 4 and thus remain broadly applicable. Early-stopping is often used in theoretical analysis to deal with practical difficulty. Thus, in practice, one can always rely on early-stopping for a small enough initial time $\delta$.

Our dependence on Assump. 4 comes only if we aim to obtain stronger theoretical guarantees to remove early stopping (which is generally regarded as very difficult and has been very rarely established in the literature). In fact, Assumption 4 can be justified as nearly necessary for the validity of the diffusion algorithm itself, as follows. By the second part of Lemma 2, if Assumption 4 is violated, the score function will (nearly) diverge around $t = 0$. Since the diffusion algorithm relies on the score function to make progress at each step, such divergence at $t = 0$ would render the algorithm itself invalid in that regime. We will make this point clear in our revised version.

Q6: Question on Lem. 2.

A6: As we pointed out in A2.2, our $q_{0|t}^j(y^j|x)$ in our Lemma 1 is not the “clean-data” distribution but the posterior distribution which depends on $t$. Meanwhile, our Lemma 1 is more general than [1, Theorem 1] by taking into account the possibility of masks in the data.

In Lemma 2, instead of providing a lower bound for this posterior distribution, we provide the bound directly for the score function through Bayes’ rule. Intuitively, if $q_t$ has full support for all $t > 0$ (necessarily, this also holds for $q_0$ due to continuity of measure), all possible states (including the mask) would have finite probability under $q_0$, which implies a finite lower bound for the score function. Otherwise, the score function will diverge, at the same rate of the time-dependent coefficient.

Q7: Reference related to "Jensen approach".

A7: Thank you for pointing this out! We will change the reference and further clarify this in the proof in Appendix D.

We thank the reviewer once again for your thoughtful comments. We hope our responses have addressed your concerns. In particular, we hope the reviewer could kindly consider the value of exploring absorbing diffusion models with stochastic sampling, which is still a meaningful and timely direction of study. If so, we would greatly appreciate it if you could kindly reconsider your evaluation and consider raising the score. We would be happy to address any further questions or clarifications you may have.

[1] Ou, Jingyang, et al. “Your Absorbing Discrete Diffusion Secretly Models the Conditional Distributions of Clean Data.”

[2] Sahoo, Subham Sekhar et al. “Simple and Effective Masked Diffusion Language Models.”

[3] Lou, Aaron, et al. “Discrete diffusion modeling by estimating the ratios of the data distribution.”

[4] Nisonoff, Hunter, et al. “Unlocking Guidance for Discrete State-Space Diffusion and Flow Models.”

[5] Ghazvininejad, Marjan et al. “Mask-Predict: Parallel Decoding of Conditional Masked Language Models.”

[6] Ren, Yinuo, et al. "Fast solvers for discrete diffusion models: Theory and applications of high-order algorithms."

[7] Ren, Yinuo, et al. “How Discrete and Continuous Diffusion Meet: Comprehensive Analysis of Discrete Diffusion Models via a Stochastic Integral Framework.”

[8] Zhang, Zikun, et al. “Convergence of Score-Based Discrete Diffusion Models: A Discrete-Time Analysis.”

[9] Chen, Hongrui and Ying, Lexing. “Convergence analysis of discrete diffusion model: Exact implementation through uniformization.”

[10] Shi, Jiaxin, et al. “Simplified and Generalized Masked Diffusion for Discrete Data.”

[11] Austin et al. “Structured denoising diffusion models in discrete state-spaces”

[12] Meng et al. “Representation deficiency in masked language modeling”

Dear Reviewer j85T,

As the author-reviewer discussion period will end soon, we would like to check whether our responses have properly addressed your concerns? If so, could you please kindly consider increasing your initial score accordingly? Certainly, we are more than happy to answer your further questions.

Thank you for your time and effort in reviewing our work!

Best Regards, Authors

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

Q1: The assumption of the bounded score estimate seems too strong. Could you give more justification?

A1: Definitely! Assumption 2 is commonly adopted in the previous studies for uniform-rate discrete diffusion models (e.g., [15] and [16]). In practice, this can be satisfied with score-clipping during training [16]. Indeed, the convergence error bounds in our main results only at most depend on $\log M$. In the revision, we will add these sentences after introducing Assumption 2.

Q2: A more detailed discussion of the dependence on M, along with a comparison to existing literature, would be appreciated.

A2: We thank the reviewer for raising this. As follows we divide the existing literature according to two types of sampling algorithms. First, for random-stepsize samplers, the uniformization algorithm in our paper does not depend on $M$ under the absorbing rate (with or without early-stopping). This result aligns with that under the uniform rate in [15]. For deterministic-stepsize samplers, the dependence on $M$ was initially shown to be $O(\sqrt{M})$ in [16] and was later improved to be $O(\log M)$ [15], both under the uniform rate. In comparison, our result has shown the same $O(\log M)$ dependence under the absorbing rate.

We sincerely appreciate the reviewer’s continued engagement. We hope our responses have fully addressed the concerns. We are also happy to provide further clarification if needed.

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

Q1: Practical Concern on Assumption 4: My primary concern lies with Assumption 4, used to establish convergence without early-stopping. While the paper acknowledges that previous works might make stronger assumptions, this particular condition still appears quite strict for practical distributions. It also seems that current absorbing discrete diffusion models do not typically rely on such an assumption when determining mask tokens, which might limit its immediate practical applicability.

A1: Even though it seems strict, Assumption 4 can be justified as nearly necessary for the validity of the diffusion algorithm itself (without early stopping), as follows. By the second part of Lemma 2, if Assumption 4 is violated, the score function will (nearly) diverge around $t = 0$. Since the diffusion algorithm relies on the score function to make progress at each step, such divergence at $t = 0$ would render the algorithm itself invalid in that regime. We have made this point clear after Assumption 4 in our revised draft.

Q2: Regarding Assumption 4 (for convergence without early-stopping), could you further elaborate on its practical implications and the types of data distributions for which it is most likely to hold? Specifically, how might practitioners determine if their specific setup satisfies this assumption, or what might be the consequences if it does not?

A2: Excellent question. Note that our main theoretical guarantees with early-stopping (i.e., Theorems 2–3) do not rely on Assumption 4 and thus remain broadly applicable. Thus, practitioners can always rely on early stopping for a small enough initial time $\delta$, which would make the approach practical. Specifically for Assumption 4, it can be satisfied when the probability of [MASK] is non-zero in the data. Also, as argued above, given that Assumption 4 is nearly necessary for the diffusion algorithm to be valid, the violation of it stops one from pushing too much towards $t=0$.

We thank the reviewer again for your comments. We hope that our responses resolved your concerns. Certainly, we are more than happy to answer your further questions if any.

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

Q1: Limitation: The paper lacks empirical evidence which supports the derived theory.

A1: Please see our response in A3.

Q2: There are some divergences which remain well-defined when the underlying distribution is a singleton or non a.c., e.g. the spread KL divergence. Do you think it is possible to use such divergence to get rid of the surrogate distribution?

A2: We agree that spread-type divergences present a promising direction for potentially bypassing the surrogate initialization. It is worth noting, however, that applying spread-type divergences introduces its own challenges, as their rate-of-change w.r.t. time becomes hard to capture in the reverse CTMC process. Yet, we view this as an intriguing avenue for future work and thank the reviewer for highlighting it.

Q3: While the theoretical contributions are strong, the paper currently lacks empirical verification or practical demonstrations showing how the proposed convergence bounds translate to real-world implementations. For instance, it would be valuable to see whether the improved convergence rates under absorbing rate matrices indeed yield faster or higher-quality sampling in practice. Some plots would be useful to support the theoretical argument.

A3: We appreciate the reviewer’s interest in empirical validation. To clarify, this submission is focused on closing a theoretical gap by providing the first non-asymptotic convergence guarantees for discrete diffusion samplers with absorbing rate matrices, which previously lacked such analysis. That said, prior works — including [1] and [2] — have empirically demonstrated that absorbing rate matrices often yield better performance than uniform ones. Our theoretical findings thus offer formal justification for this empirically observed advantage.

We thank the reviewer again for your comments. We hope that our responses resolved your concerns. Certainly, we are more than happy to answer your further questions if any.

[1] Austin, Jacob et al. “Structured denoising diffusion models in discrete state-spaces.”

[2] Lou, Aaron, et al. “Discrete diffusion modeling by estimating the ratios of the data distribution.”