Discrete Diffusion Models: Novel Analysis and New Sampler Guarantees

We sincerely thank the reviewer for providing the highly valuable feedback. We greatly appreciate your time and effort in reviewing our paper.

Q1: One weakness of the paper is a missing discussion of how these new results can be interpreted for practitioners, when choosing the sampler for their diffusion model.

A1: We thank the reviewer for pointing out this important issue. Yes — one key motivation for our work is to inform the design and selection of samplers for discrete diffusion models based on theoretical guarantees. Our results suggest that Euler and Tweedie $\tau$-leaping samplers offer the same convergence rate in KL-divergence as vanilla $\tau$-leaping (Theorem 3), while requiring lower per-step sampling complexity by a factor of $O(S)$, where $S$ is the vocabulary size. This makes the former two samplers more scalable for large-vocabulary tasks. Overall, our findings indicate that Euler or Tweedie $\tau$-leaping may be preferable in practice — especially in settings where sampling efficiency is critical and the vocabulary size $S$ is large.

We also provided numerical experiments to validate our theoretical results and to support their practical implications discussed above. Table 1 demonstrates an approximately linear relationship between the estimated KL divergence and the vocabulary size $S$, validating our theoretical prediction of linear dependence on $S$. Table 2 compares the performance of the Euler method and Tweedie $\tau$-leaping against the standard $\tau$-leaping algorithm, highlighting their superior efficiency and practical advantage.

Table 1: Estimated KL-divergence between the target and the sampling distribution. The target is generated autoregressively over the dimensions. Here $d = 2$. We use the Euler method to obtain samples.

Table 2: Estimated total variation distance between the target and sampling distribution of different sampling methods. The same target is used, with $d=3$ and $S=8$.

Q2: Typo Line 76 practically

A2: Thank you for catching this typo! We will correct it in the revision.

Q3: Can these results point researchers in the right direction when choosing a sampler for their diffusion model?

A3: Please see our detailed response in A1. We believe our results suggest that Euler or Tweedie $\tau$-leaping may be more favorable in practice, particularly in scenarios where sampling efficiency is crucial and the vocabulary size $S$ is large.

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

I appreciate the author’s responses to my questions. Based on the clarifications provided, I will raise my score.

We sincerely thank the reviewer for providing valuable feedback and greatly appreciate your time and effort in reviewing our paper.

Q1: Presented limitations and wider discussion is very limited and perhaps too slim. For instance, the main results are derived for a special CTMC rate matrix (5). To what extent is this limiting? If it is, it should be emphasized. Can it be extended?

A1: We thank the reviewer for pointing this out. We agree that our latter theoretical results (namely Theorems 2 and 3) are derived under the commonly used rate estimator in (5), which ensures analytical tractability and aligns with prior work (e.g., [1-3]). However, our analytical framework — particularly Theorem 1 — is not limited to this specific reverse rate parameterization and applies to any CTMC as long as the reverse rate matrix is well-defined. Meanwhile, although we assume a particular parameterization for the reverse rate in Theorems 2 and 3, they can be easily extended for general reverse rates with slightly modified Assumptions 1 and 2 (which are then made on the estimated rates instead of the scores). We will discuss our current limitation on the uniform rate matrix under time-homogeneity and potential extensions to other rate matrices and under non-homogeneous noise levels in the revision. We will further discuss another limitation on using Bergman divergence to characterize the estimation error. It might be interesting to investigate other forms of estimation error, such as in $L_1$ or $L_2$.

Q2: The same goes for Assumptions 1 and 2. One of the claims of the paper is it alleviates difficulties with hard-to-check assumptions. It would be worth discussing or otherwise showing (experiments?) the new assumptions are easier to verify/meet.

A2: We appreciate the reviewer’s thoughtful comment. Both Assumptions 1 and 2 are easy to check/enforce. Assumption 2 can be easily enforced through score-clipping. In particular, during training we can clip those scores that are too small or large with a constant $M$ [4]. Also, note that our convergence result only depends on $\log M$. Assumption 1 requires bounding the score-entropy loss evaluated on the discretized grid, which is easy to check. In particular, we can take the average loss (up to some constant) on the selected grid. This is in contrast to those integrated loss functions [4, 5], where taking an integral is needed to evaluate the loss.

Just to clarify as a side note, both Assumptions 1 and 2 also occur in prior works (e.g., [3-4]).

Q3: Experiments/Ablation study. Despite its theoretical nature, supporting experiment(s) could increase accessibility and appeal for the paper. For instance, Main result (Th 2) is an asymptotic result (in T) in its nature. Could authors show in the experiment (or otherwise) for what ranges of T asymptotic behaviour prevails? Is it data/task dependent?

A3: To clarify, the asymptotic results are in terms of the final error $\epsilon$, which is affected, for example, by the number of steps chosen. We have included two tables to provide empirical support for our theoretical results. Table 1 demonstrates an approximately linear relationship between the estimated KL divergence and the vocabulary size $S$, validating our theoretical prediction of linear dependence on $S$, even for moderate number of steps (instead of asymptotically large ones). Please see our response to reviewer 1 for more details.

Table 2 compares the performance of the Euler method and Tweedie $\tau$-leaping against the standard $\tau$-leaping algorithm, highlighting their superior efficiency and practical advantage.

Table 1: Estimated KL-divergence between the target and the sampling distribution. The target is generated autoregressively over the dimensions. Here $d = 2$. We use the Euler method to obtain samples.

Table 2: Estimated total variation distance between the target and sampling distribution of different sampling methods. The same target is used, with $d=3$ and $S=8$.

In general, asymptotic results usually have a vanishing constant, which depends on other system parameters such as the data dimension, yielding the tightness of these theoretical bounds data/task dependent. Yet, our experiment above shows that such asymptotic behavior might occur very early (i.e., when the number of steps are still moderate). Also, our main result in Theorem 3 further shows the advantage of Euler and Tweedie $\tau$-leaping samplers, both of which are commonly used in practice.

Q4: Minor and typos

A4: We thank the reviewer for pointing these out. We will add the corresponding definitions and line numbers, and correct typos in the revised paper.

Q5: Could authors elaborate why $g_t$ is a Bregman divergence, whose non-negativity was used in proof (Appendix F)? Bregman div. is defined by $\phi(y)-\phi(x)-<y-x,\phi(y)>$, where $\phi$ is a strictly convex function (here negative entropy), if I am not mistaken. Could authors rewrite the presented relation to this form (or show it otherwise please?)

A5: Definitely. In our case, for each fixed $x_t$ and $y \neq x_t$, let $p_y := R_t(x_t,y), q_y := \\hat{R}_t(x_t,y).$

Also, let $\phi(p) := \sum_{y \neq x_t} p_y \log p_y$ (i.e., the negative entropy function, which is convex), and the corresponding Bregman divergence is $D_\phi (p, q) = \phi(p) - \phi(q) - \langle y-x,\phi(y) \rangle = \sum_{y \neq x_t} p_y \log p_y - q_y \log q_y - (p_y - q_y) (1 + \log q_y) = \sum_{y \neq x_t} p_y \log(p_y / q_y) - p_y + q_y,$ which is exactly $g_t$. We will add this part in Appendix F for clarification.

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

[1] Campbell, Andrew, et al. “A Continuous Time Framework for Discrete Denoising Models.”

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

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

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

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

[6] Pham, Le-Tuyet-Nhi et al. “Discrete markov probabilistic models.”

Dear Reviewer EBtu,

Thank you for your time and effort in reviewing the submissions and for providing valuable feedback to the authors.

If you haven’t already done so, we kindly remind you to review the authors’ rebuttals and respond accordingly. In particular, if your evaluation of the paper has changed, please update your review and explain the revision. If not, we would appreciate it if you could acknowledge the rebuttal by clicking the “Rebuttal Acknowledgement” button at your earliest convenience.

This step ensures smooth communication and helps us move forward efficiently with the review process.

We sincerely appreciate your dedication and collaboration.

Best regards, AC

We sincerely thank the reviewer for providing valuable feedback and greatly appreciate your time and effort in reviewing our paper.

Q1: One question for the authors is whether they considered numerical validation for the convergence rate with respect to vocabulary size $S$.

A1: Thank you for raising this point! We have included two tables to provide empirical support for our theoretical results. Table 1 demonstrates an approximately linear relationship between the estimated KL divergence and the vocabulary size $S$, validating our theoretical prediction of linear dependence on $S$. Table 2 compares the performance of the Euler method and Tweedie $\tau$-leaping against the standard $\tau$-leaping algorithm, highlighting their superior efficiency and practical advantage.

Table 1: Estimated KL-divergence between the target and the sampling distribution. The target is generated autoregressively over the dimensions. Here $d = 2$. We use the Euler method to obtain samples.

Table 2: Estimated total variation distance between the target and sampling distribution of different sampling methods. The same target is used, with $d=3$ and $S=8$.

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

Dear Reviewer ZqTY,

Thank you for your time and effort in reviewing the submissions and for providing valuable feedback to the authors.

If you haven’t already done so, we kindly remind you to review the authors’ rebuttals and respond accordingly. In particular, if your evaluation of the paper has changed, please update your review and explain the revision. If not, we would appreciate it if you could acknowledge the rebuttal by clicking the “Rebuttal Acknowledgement” button at your earliest convenience.

This step ensures smooth communication and helps us move forward efficiently with the review process.

We sincerely appreciate your dedication and collaboration.

Best regards, AC

We sincerely thank the reviewer for providing valuable feedback and greatly appreciate your time and effort in reviewing our paper.

Q1: The work is entirely theoretical and lacks any empirical validation to support its findings.

A1: We appreciate the reviewer’s concern. We have included two tables to provide empirical support for our theoretical results. Table 1 demonstrates an approximately linear relationship between the estimated KL divergence and the vocabulary size $S$, validating our theoretical characterization of linear dependence on $S$. Table 2 compares the performance of the Euler method and Tweedie $\tau$-leaping against the standard $\tau$-leaping algorithm (in terms of the estimated TV distance between the target and the sampling distribution), highlighting their superior efficiency and practical advantage.

Table 1: Estimated KL-divergence between the target and the sampling distribution. The target is generated autoregressively over the dimensions. Here $d = 2$. We use the Euler method to obtain samples.

Table 2: Estimated total variation distance between the target and sampling distribution of different sampling methods. The same target is used, with $d=3$ and $S=8$.

Please note that the empirical performance of these practical samplers like $\tau$-leaping, Euler, and Tweedie $\tau$-leaping have also been widely studied in many existing experimental works, e.g., [1-3].

Q2: The convergence rates maintain a quadratic dependence on data dimension $d$, which remains a practical limitation.

A2: We thank the reviewer for this thoughtful observation. Indeed, our convergence bounds scale quadratically in $d$, which is consistent with the prior work of [4]. While reducing this dependency remains an important open direction, our main contribution is the reduction of the dependence on vocabulary size $S$ from quadratic to linear — a critical improvement in NLP and sequence modeling where $S \gg d$. For example, in [1-2], $S$ is as high as 50257 while $d$ is only 1024.

Q3: Your results in Theorems 2 and 3 show that the Euler and Tweedie $\tau$-leaping samplers have the same asymptotic convergence rate as $\tau$-leaping, but with a significantly lower per-step sampling complexity. Does it suggest that there are larger hidden constants in the convergence bounds for these samplers that may impact their practical performance?

A3: In general, our results suggest $\tau$-leaping has the same convergence rate (in terms of number of iterations) as the Euler and Tweedie $\tau$-leaping samplers. Hence, with respect to the number of iterations, our results do not suggest large hidden constants in the convergence bounds. In particular, Lemma 7 establishes the asymptotic equivalency between Euler, Tweedie $\tau$-leaping, and the truncated $\tau$-leaping algorithms, where the last one is itself a rate-truncated version of the standard $\tau$-leaping algorithm. Thus, the convergence rate of Euler and Tweedie $\tau$-leaping samplers should be the same as vanilla $\tau$-leaping, without any hidden constants.

However, in practice, performance often corresponds more closely to the total number of samples taken—that is, the product of the number of samples per step and the total number of iterations. In this context, the Euler and Tweedie $\tau$-leaping samplers offer advantages over the vanilla $\tau$-leaping method due to their lower per-step sampling cost. In particular, new experimental result seems to suggest that these samplers differ in their constant-level performance, with the Euler method and Tweedie $\tau$-leaping exhibiting consistently smaller constants than vanilla $\tau$-leaping, likely due to their more efficient sampling in each iteration step.

Q4: Can your analysis extend to the high-order samplers as in [5]?

A4: The core idea of [5] is to better approximate the “middle” rate through a Runge-Kutta-like method designed for CTMC. With such a “middle” rate, [5] shows an accelerated convergence result (in terms of $\epsilon$) for the $\tau$-leaping algorithm. At a high level, it appears that our proof framework can be extended to [5] to investigate the “middle” rate for the truncated version of the vanilla $\tau$-leaping reverse rate and obtain an accelerated convergence result for Euler and Tweedie $\tau$-leaping samplers. However, this extension will involve the careful development of some detailed technical steps and would require a rigorous analysis.

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

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

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

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

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

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

Dear Reviewer qy7m,

Thank you for your time and effort in reviewing the submissions and for providing valuable feedback to the authors.

If you haven’t already done so, we kindly remind you to review the authors’ rebuttals and respond accordingly. In particular, if your evaluation of the paper has changed, please update your review and explain the revision. If not, we would appreciate it if you could acknowledge the rebuttal by clicking the “Rebuttal Acknowledgement” button at your earliest convenience.

This step ensures smooth communication and helps us move forward efficiently with the review process.

We sincerely appreciate your dedication and collaboration.

Best regards, AC

We sincerely thank the reviewer for providing valuable feedback, for the positive comments, and for recognizing our contributions. We greatly appreciate your time and effort in reviewing our paper.

Dear Reviewer ieBG,

Thank you for your time and effort in reviewing the submissions and for providing valuable feedback to the authors.

If you haven’t already done so, we kindly remind you to review the authors’ rebuttals and respond accordingly. In particular, if your evaluation of the paper has changed, please update your review and explain the revision. If not, we would appreciate it if you could acknowledge the rebuttal by clicking the “Rebuttal Acknowledgement” button at your earliest convenience.

This step ensures smooth communication and helps us move forward efficiently with the review process.

We sincerely appreciate your dedication and collaboration.

Best regards, AC