Fast Sampling via De-randomization for Discrete Diffusion Models

Q4. Although the proposed DNDM model has an identical forward process, the corresponding approximate reverse process distribution isn't clearly explained; the authors instead jump straight to a sampling algorithm, and it's not obvious that optimizing the training objective will make this sampling algorithm match the forward process.

A4. We believe there is a misunderstanding regarding the reverse process by the reviewer. The identical forward process indicates an identical reverse process distribution. The approximate error does not come from the non-accurate reverse process distribution but from the approximation error of training the neural network.

To connect the training objective and our DNDM, we have added the training objective and the ELBO in Appendix B.3. Our analysis shows that optimizing the training objective will make this sampling algorithm match the forward process and this training objective aligns with previous discrete diffusion models up to a constant.

Q5. The authors note that their reverse sampler decodes predictions using "different decoding strategies including greedy decoding, top-k decoding and temperature decoding" and mentions that argmax decoding shows strong performance. I don't think this makes sense under a probabilistic view of the process; this feels just like a heuristic to improve results.

A5. This is again a misunderstanding regarding the decoding strategy and decoding type. The argmax decoding in our algorithm is different from the decoding strategies mentioned in "different decoding strategies including greedy decoding, top-k decoding and temperature decoding", where the latter refers to the decoding strategy in a traditional NLP task aimed to get $\hat{\mathbf{x}}\_0$, such as the decoding strategy used in Transformer. In contrast, the decoding type in Section 5 refers to the decoding scheme used in $p(\mathbf{x}\_{t-1} | \mathbf{x}\_t, \hat{\mathbf{x}}\_0)$ in the reverse sampling process.

Thank you for your constructive feedback.

Q1-1. Can the proposed approach be formalized as a probabilistically-sound variational model, and if so, how?

A1-1. The proposed approach can indeed be formalized as a probabilistically-sound variational model. We have added the mathematical formulation in Appendix B.3 for our DNDM with both finite sampling steps and infinite sampling steps (i.e., continuous time sampling).

Q1-2. I'm not convinced that the accelerated sampling algorithm that the authors propose is actually correct from a probabilistic standpoint. The authors motivate it by proving (in Theorem 3.1) that the transition times in the forward process are independent and follow a particular distribution based on the noise schedule. However, this is only proven for the forward process. … this property would have to also be true for the reverse process … after conditioning on the current value of, the transition times remain independent and have a tractable distribution.Relatedly, does the equivalent of Theorem 3.1 hold for the reverse process in general?

A1-2. We believe there is a misunderstanding here by the reviewer. Theorem 3.1 indeed holds for both the forward and reverse processes. More specifically, the independence of transition times $\tau_n$ follow from our definition of forward process in Eq. (4) and are not conditioned on $\mathbf{x}\_0$ or any other variables. In the forward process, we have $\mathbf{x}\_{t,n} = b_{t,n}\mathbf{x}\_{t-1,n} + (1-b_{t,n}) \mathbf{w}\_n$, and $\tau_{n} = t$ is equivalent to $b_{0,n} =1, \ldots, b_{t-1,n} = 1$ and $b_{t,n} = 0$. Since $\\{ b_{t,n} \\}\_{t=0}^T$ is independent for different $n$ by definition, each $\tau_n$ is also independent. Therefore, the corresponding reverse process also has independent transition time. We believe the reviewer's misunderstanding may stem from the pre-assumption that the transition of different tokens is dependent. However, we want to clarify that these transitions are, in fact, independent. This underscores the reason why transition time remains independent in both the forward and reverse processes.

Q2. The paper refers to the predictive model of $p_\theta\left( \mathbf{x}\_{t-1} \mid \hat{\mathbf{x}}\_0, x_t\right)$ as a "score network". For continuous diffusion, the "score" refers to the gradient of the marginal density with respect to the input. I don't think this is quite correct in the discrete case. Prior work on discrete diffusion models mostly doesn't seem to use "score network" terminology, or else uses it to refer to a very specific generalization of the continuous score

A2. We apologize for the misleading use of words in our previous version. We have changed all “score network” to “neural network” in our revision.

Q3. The assumptions being made about the "score network" are not clearly stated, although the paper later mentions "the possibility that WMT14 violates our assumption that the pre-trained score model is uniformly accurate for all time steps" in the experiments section. This seems important because the predictive model $p_\theta (\mathbf{x}\_{t-1} \mid \hat{\mathbf{x}}\_0, \mathbf{x}\_t )$ is never perfectly accurate. In particular, in the standard diffusion model setup $p_\theta$ makes independent predictions for all tokens, whereas those tokens may have a nontrivial joint distribution. Additionally it is only trained using a variational bound, so it seems likely to me that it would not be "uniformly accurate for all time steps". Relatedly, what assumptions are you imposing on the "score function"?

A3. Thank you for raising this point. First of all, we don’t make any stronger assumption (e.g., perfectly accurate model) on the pre-trained model than existing works on diffusion models. Instead, we adopt the common practice of assuming the pre-trained model to be sufficiently effective, aligning with the approach taken by other works in the field.

Second, in our paper, we employed a pretrained model checkpoint trained on 50 steps. This means the network was only familiarized with 50 distinct time steps during its training phase, and the timesteps during reverse sampling might have been mostly unseen, especially for timesteps 1000 or infinite timesteps. For example, the model trained on $t = 1, \ldots, 50$ might be asked to output at $t = 2.71$ during sampling. Therefore, we conjecture that the network can provide accurate estimates even for those steps which it was not explicitly trained on. However, for WMT14, the pretrained model checkpoint may not be able to generalize to unseen time steps effectively. We have now relocated this argument from the main text to an extended explanation in Appendix F.1 for clarity.

Q8. Unconditional generation samples (in the appendix) remain unimpressive relative to autoregressive model generation quality. This applies to previous work as well, of course, but I don't think the improvements in Table 3 translate to a noticeable increase in overall sample quality.

A8. Again, our contribution is on the sampling speed instead of the sample quality. Since our method is a training-free accelerated sampling algorithm, the performance of our method in terms of sample quality is contingent on the pre-trained models, which may not always be optimized for sample quality.

Q9. The proposed approach only applies to discrete diffusion models that have the form in Equation (1), but this is only a subset of the discrete diffusion models that have been considered in the literature. Austin et al. (2021) discusses a few alternatives that are not of this form (e.g. discreteized Gaussian, token-embedding-distance transitions, or hybrids of absorbing and other diffusion processes as discussed in the appendix). Another recent example is Blackout Diffusion (Santos et al. 2023).

A9. Eq. (1) has already included the most two widely used discrete diffusion models: multinomial diffusion and absorbing diffusions. Note that the discretized Gaussian diffusion and Blackout diffusion only outperform other discrete diffusion models for continuous data, while we focus on the generation of discrete data such as text. We leave the acceleration of other “discrete” diffusion models as a future work.

Q10. For the unconditional generation tasks, why don't you compare against RDM or absorbing diffusion? Also, how does your method do with a more realistic number of sampling steps (smaller than the sequence length), and how does it compare to an autoregressive model with the same compute budget?

A10. Based on our experiments, none of the discrete diffusion models exhibited satisfactory performance for unconditional generation tasks. As a result, we have opted to exclusively present the results of multinomial diffusion and its accelerated version to provide readers with a representative overview of these outcomes.

Q11. I'm not sure what is meant by "full de-randomization". The transition times and the sampled tokens are still random, are they not?

A11. The concept of 'full de-randomization' is introduced to contrast with the discrete diffusion model proposed by Song et al. (2020a). In their model, each $\mathbf{x}\_{t-1}$ relies on $\mathbf{x}\_0$, $\mathbf{x}\_t$, and an injected noise term $Cat(1_K)$, as detailed in Equation (18) of Song et al. (2020a). In contrast, our reverse process depends on $\mathbf{x}\_0$, $\mathbf{x}\_t$, and a random transition time $\tau$, but notably, it does not incorporate any injected noise (as all previous discrete diffusion models do). From the perspective of given $\mathbf{x}\_0$, $\mathbf{x}\_t$, and transition time, our approach achieves full de-randomization.

Q12. Section 2.2 mentions "the chain rule" but it's not obvious to me what this is referring to. The equation seems correct but I don't think the derivation involves a chain rule (?)

A12. Thank you for pointing out, this is indeed a typo. We were trying to explain how one can get $p(\mathbf{x}\_t | \mathbf{x}\_0)$ from the Markov chain characterized by $p(\mathbf{x}\_t | \mathbf{x}\_{t-1})$ and marginal distribution. We have revised our paper accordingly.

[1] Ghazvininejad, Marjan, et al. "Mask-predict: Parallel decoding of conditional masked language models." arXiv preprint arXiv:1904.09324 (2019).

[2] Lin, Xiao, et al. "Discrete Conditional Diffusion for Reranking in Recommendation." arXiv preprint arXiv:2308.06982 (2023).

[3] Song, Jiaming, Chenlin Meng, and Stefano Ermon. "Denoising diffusion implicit models." ICLR 2021.

[4] Austin, Jacob, et al. "Structured denoising diffusion models in discrete state-spaces." Advances in Neural Information Processing Systems 34 (2021): 17981-17993.

Q7. The baselines for the experiments seem fairly limited. The authors only compare against RDM and vanilla multinomial diffusion models, but seem to introduce additional heuristics into the decoding process to get better results for a fixed compute budget. It seems to me then that it would be fairer to compare to the much larger set of non-autoregressive generative models, for which similar heuristics are considered fair game and for which many ideas have already been proposed and evaluated. As one example, I believe Mask-Predict (Ghazvininejad et al. 2019) achieves higher BLEU scores on WMT14 (relative to this work) using only 10 model evaluations, by using argmax decoding and other heuristics. Many other examples are discussed in a survey by Xiao et al. (2023).

A7. We would like to emphasize that the main contribution of our work is to accelerate the sampling speed of multinomial diffusion-type discrete diffusion models. So the most important and relevant baselines are multinomial diffusion and absorbing diffusion without using our sampling technique, i.e., RDM and vanilla multinomial/absorbing diffusion.

Furthermore, we don’t introduce additional heuristics. In our decoding process, we strictly adhere to the same mechanisms employed by the algorithms we compare with, specifically those in RDM. The introduction of various decoding types in our study is not an arbitrary heuristic but rather a collection of existing decoding strategies used in RDM. This approach exactly ensures that our comparison with RDM is fair.

As per your recommendation, we have included a comparison with Mask-Predict, although it's important to note that our primary contribution does not center around surpassing Mask-Predict. A summary of these results is provided below for reference. On the WMT16 dataset, our model demonstrates uniformly superior performance than Mask-Predict.

On the WMT14 dataset, we encountered challenges in replicating the results reported in Mask-Predict due to a staled link of the data (This is also reported as an issue in their Github repo). We were able to run the algorithm but the performance does not match. Instead, we reference the result of 27.03 BLEU score reported in their paper. Our model, DNDM-k-Absorb, achieves a BLEU score of 27.18, which is better than their result. This performance was attained within 68.0 seconds, which is on par with 67.15 seconds reported for Mask-Predict on the same machine.

The performance comparison on WMT16 of DNDM with Mask-Predict

The performance comparison on WMT14 of DNDM with Mask-Predict

Q6. The authors motivate their approach based on accelerating generation speed, but I'm not convinced the gains are actually significant when compared to just using an autoregressive model. The authors seem to focus on accelerating sampling when there are more denoising steps than there are tokens (e.g. the 1000-step and $\infty$-step conditions for WMT, the 1000-step and 4000-step conditions for unconditional generation). But if you have more denoising steps than tokens, it seems like you may as well just use an ordinary autoregressive model. Indeed, in the "$\infty$-step" diffusion, the continuous-time reverse sampler requires one network evaluation per token generated, which is the same number of computation steps as an autoregressive model would use. I expect that an autoregressive model would have a better tradeoff between generation time and quality than the method proposed here.

A6. We respectfully disagree that our focus is on accelerating sampling when there are more denoising steps $T$ than the number of tokens $N$. While it is true that our method can get more significant improvement when T is larger, we care about the result for all sampling steps, including those much smaller than the number of tokens. Below is an example of our result shown in Table 5 of our revision.

As we can see from the table, our algorithm is 2-3 times faster even for small sampling steps (25). We have also proved that our algorithm can accelerate the discrete diffusion for all $N, T$ and included more discussion in Appendix D.

In addition, we agree that our infinite limit has the same NFE as the autoregressive diffusion. However, our method also supports finite step sampling, which is much faster than the autoregression diffusion in terms of NFE. Moreover, our primary objective and contribution revolve around expediting multinomial diffusion-type discrete diffusions. The comparison with autoregressive models does not contribute to substantiating our assertion regarding the acceleration of sampling speed.

Dear Reviewer B4eP,

We are grateful for your valuable feedback. In our rebuttal, we addressed your concerns, clarified misunderstandings, and incorporated additional theoretical and empirical results as per your suggestions. As the discussion deadline is approaching, we would like to hear your feedback and address any further questions you may have. Thank you!

Best regards, Authors

Q3. I think the paper may require more work on clarifying what are the new contributions of the proposed model and designing the experiments such that they clearly showcase these contributions (see also questions on ARDM). E.g., under what conditions exactly can we expect improvements in sampling speed?

A3. As we emphasized in the introduction, our main contribution is proposing a new sampling method for discrete diffusion models that reduces the generation time (i.e., NFE) while preserving the sample quality. Please see the table in A1 for details.

From the theoretical point of view, for discrete diffusion models, our method is guaranteed to achieve a reduction in NFE compared with the number of sampling steps. This is proved in Theorem D.1 in the newly added Appendix D. More specifically, Theorem D.1 shows that the NFE is reduced from $T$ to $(1- C_{D_{\tau}, T, N})T$, where $C_{D_{\tau}, T, N}$ is a constant with range $(0,1)$ that depend on $D_{\tau}, T, N$. The details of the discussion can be found in Appendix D.

Q4. It seems to me that there are quite a bit of (potentially subtle) similarities with the previous work, where the authors note a connection between absorbing diffusion models and order-agnostic autoregressive models. In particular, as pointed out in their Appendix C, the continuous-time limit of an absorbing diffusion model is effectively equivalent to their order-agnostic ARDM, which seems to be also equivalent to the infinite-time limit for absorbing diffusion presented in this paper. Would the authors of the submission agree, or maybe are there differences that I have overlooked? I do see that in the non-infinite-time case, the models do not exactly match, and the model is formulated from a different point of view, potentially allowing more flexibility in designing the generative process. But it would be good to give more elaboration on the differences to ARDM and maybe also provide direct numerical comparisons in the paper.

A4. Thank you for bringing our attention to the ARDM. We would like to emphasize that our method is a training-free fast sampling method for various discrete diffusion processes, including absorbing diffusion and multinomial diffusion. Such a fast sampling method enables us to tackle discrete diffusion models with a large number of sampling steps, or even infinite steps. While ARDM can be seen as the infinite-time limit of absorbing diffusion, it remains orthogonal to our training-free fast sampling method.

Q5. One downside of the paper as of now is that a method to estimate the data likelihood is not included. Perhaps it would be possible to create a lower bound by not having intermediate latents $x_t$ at all, and considering the transition times $\tau$ as latent variables? For instance, setting the inference distribution to $q(\tau_{1:T})\prod_{t=1}^k q(x_t^k|x_t^0)$, where $x_t^k$ is distributed according to Uniform({1,...,T}), and the corresponding generative process defined such that we first sample from the priors $p(x_T)$ and $p(\tau)$, and then generate the different dimensions according to the ordering of $\tau$. If I am not mistaken, this would be similar to what was done in the ARDM paper as well, and one could form an ELBO similar to theirs.

A5. Thank you for your valuable advice. We have provided the derivation of ELBO in Appendix B.3 which can estimate the data likelihood. The ARDM obtains their ELBO by decomposing with respect to the data dimension, which depends on the autoregressive nature of their model. Therefore, their method doesn’t apply to our model. Instead, we take the approach of classic diffusion models, especially the non-markovian continuous time diffusion model DDIM [3], and derive the ELBO for our model. Our ELBO is based on both intermediate latent $x_t$ and the transition time $\tau$.

Thank you for your helpful comments！

Q1. I think that the use of the phrase “sampling iterations” in the paper can be somewhat misleading, for instance on page 5, where it is indicated that the generation time increases sub-linearly with sampling iterations (as opposed to RDM). While technically true from the diffusion perspective, this also overlooks the fact that the relevant metrics are actually the amount of function evaluations (or the time taken for sampling). Similarly, comparisons with the same step counts to RDM in Table 1 & 2 seem suboptimal to me, and instead it should be (approximately) the same amount of function evaluations / wall clock time.

A1. Thank you for your suggestion. We have used “sampling steps” to replace “sampling iterations” in the revision. While the number of sampling steps is also a widely used metric as used in [1] and [2], we have also incorporated the NFE metric into our experiments to provide a more comprehensive comparison in our revision. Please refer to Tables 5 and 6 in Appendix D, where we list the average NFEs of both RDM and our method, under the same sampling steps. Below is an example of our result shown in Table 6 of our revision. We can see that the BLEU score achieved by our method with about 40 NFE outperforms the BLEU score of RDM with 50 NFE.

Q2. It would also be good to elaborate where exactly does the method provide an improvement over RDM, since they focused more on step counts <25, whereas the comparisons here are for step counts >25. In this sense, is the model even a direct competitor for RDM, or could the two methods be combined?

A2. Our model is not intended as a direct competitor to RDM but rather as a training-free accelerator in terms of sampling speed, which can be integrated with various discrete diffusion models in the form of (1), including RDM. Our approach addresses a key inefficiency inherent in existing sampling algorithms of discrete diffusion models. Specifically, in traditional diffusion models, including RDM, increasing the number of sampling steps leads to better sampling quality but at the cost of linearly increasing computational time, often with only marginal performance gains. In contrast, our method achieves a more favorable tradeoff between sampling time and quality. The improvement in efficiency is because our model significantly reduces the number of function evaluations (NFE), as our method. We have added Tables 5 and 6 in Appendix D with NFE as a performance metric. We can see that even for 1000 sampling steps, the effective number of sampling steps (NFE) is around 30-40. Therefore, with smaller NFE (30-40), our method can consistently achieve a higher BLEU score than RDM with 50 NFE. Please see the answer to A1 and Tables 5 and 6 in our revision for the detailed comparison in terms of NFE.

Q6. How is the evaluation with the BERT model done for the unconditional generation experiments, exactly?

A6. Thanks for pointing this out. We realized that BERT may not be a good model for evaluating the perplexity of unconditionally generated texts. We have reevaluated the perplexity scores (PPL) of the generated samples using the GPT2-large model. Our new evaluation results are as follows: the average perplexity score for the text samples generated from multinomial diffusion trained on enwik8 using vanilla sampling methods is 801.7817. Additionally, the average perplexity score for the text samples generated from multinomial diffusion trained on the text8 dataset via DNDM is 556.7812.

[1] Austin, Jacob, et al. "Structured denoising diffusion models in discrete state-spaces." Advances in Neural Information Processing Systems 34 (2021): 17981-17993.

[2] Zheng, Lin, et al. "A reparameterized discrete diffusion model for text generation." arXiv preprint arXiv:2302.05737 (2023).

[3] Song, Jiaming, Chenlin Meng, and Stefano Ermon. "Denoising diffusion implicit models." arXiv preprint arXiv:2010.02502 (2020).

Thank you very much for your positive feedback! We would like to clarify and elaborate more on the above points.

“ In the infinite-step limit, in practice the generation seems to decompose to the same thing: Since there is zero probability that two transitions are set on the same time, the generation ends up going through each data dimension separately, similarly to ARDM. ”

Answer: We partially agree. Note that in the infinite time limit ($N$ is fixed while $T \rightarrow \infty$), if the transition time distribution concentrates on several different points, there can still be several transitions happening at the same time. For example, let us consider a setting with two tokens. Assume the transition distribution for each token is the same: with probability $1/2$, $\tau = 1$, and with probability $1/2$, $\tau$ is uniform on $[0,1]$. In this case, the transition time of these two tokens can still be the same with probability 0.5*0.5 = 1/4, which is not zero probability.

“In any case, it seems to me still that discussion and positioning regards to it should be made clear in the paper”

Answer: Thank you for your suggestion. For our method, when $N$ is fixed while $T \rightarrow \infty$, the total NFE will reach $N$. On the other hand, when $T$ is fixed and $N \rightarrow \infty$, the NFE will reach $T$. Such observation can be rigorously inferred from our Theorem D.1. Therefore, our framework bridges two extremes of (fixed N, infinite T) and (infinite N, finite T). We summarize the NFE of our method under different regimes in the table below. As you can see, our method can accelerate sampling for both finite time-steps and infinite time. In contrast, ARDM is primarily focused on infinite timesteps. We have added a discussion in Section 3 in the revision.

"It is also worth pointing out that the ARDM paper also considers parallelizing the generation to fewer than N steps. "

Answer: Thank you for your suggestion. For infinite timesteps, ARDM proposed an advanced parallelizing technique that can reduce NFE according to the log-likelihood, which we haven’t considered in our DNDM-C. We have added it in Section 4.1 in the revision.

“Also, while ARDM does not apply to other forward processes than absorbing, it is also the case that here the other processes than absorbing do not exactly correspond to their original counterparts: In uniform diffusion, it is possible for a token to make many transitions during the diffusion process all the way to the end, while here the accelerated uniform diffusion seems to work closer to absorbing diffusion, where only one step is made for each token.”

Answer: We agree that in multinomial diffusion, it is possible for a token to make many transitions during the diffusion process all the way to the end during the forward process in Eq. (1) in our paper. However, we want to clarify that using our de-randomized technique, we can derive a new process in Eq. (4), where each token only has one transition. This new process has the same conditional probability flow $q(\boldsymbol{x}\_{t}|\boldsymbol{x}\_{0})$ as the original multinomial diffusion. We have also derived an ELBO for Eq. (4) and proved its equivalence to the original process in Section B.3.

To sum up, we have added a new paragraph in Section 4 to discuss the ARDM. You can find it in the revised paper.

Q5. Regarding the WMT14 results, the authors mention the weaker performance relative to the other datasets could be a sign that WMT14 "violates our assumption that the pretrained score model is uniformly accurate for all time steps" -- could you clarify what this means?

A5. Thank you for pointing this out. We apologize for any confusion caused by our initial argument. In our paper, we employed a pretrained model checkpoint trained on 50 steps. This means the network was only familiarized with 50 distinct time steps during its training phase, and the timesteps during reverse sampling might have been mostly unseen, especially for timesteps 1000 or infinite timesteps. For example, the model trained on $t = 1, \ldots, 50$ might be asked to output at $t = 2.71$ during sampling. Therefore, we conjecture that the network can provide accurate estimates even for those steps which it was not explicitly trained on. However, for WMT14, the pretrained model checkpoint may not be able to generalize to unseen time steps effectively. We have now relocated this argument from the main text to an extended explanation in Appendix F.1 for clarity.

Thank you for your strong support!

Q1. The experiments are promising, but the scope is a bit limited. For example, the claims of the paper could be strengthened with results on sequence-to-sequence generation tasks such as question generation and paraphrasing (1, 2).

A1. Thank you for your valuable suggestion. We have added Theorem D.1, which shows that the NFE of our method is provably reduced from $T$ to $(1- C_{D_{\tau}, T, N})T$. Therefore, our method is guaranteed to achieve a reduction in NFE compared with the number of sampling steps. We're currently in the middle of conducting experiments on sequence-to-sequence generation tasks. We will add these additional experiments to the final version.

Q2. An ablation of the choice to use Beta distribution to approximate the true transition time distribution (induced by the $$ \alpha_t $$schedule during training) would be clarifying. This is especially true in the case of the continuous time evaluation (Tables 1, 2), where it's slightly unclear whether the boosts to performance are due to the continuous time formulation or the choice of Beta distribution.

A2. Thank you for your valuable suggestion. We have conducted an ablation study on different choices of Beta distributions (Tables 7, 8, 9 in Appendix F.1). Specifically, when utilizing the same Beta distribution as those employed in continuous time, the discrete (finite step) version of DNDM does not achieve comparable performance as DNDM-C. Please refer to the following table and Table 9 in Appendix F.1.

BLEU scores of different sampling steps with the same transition time distribution $Beta(100, 4)$ on WMT16:

We note that, in the last column, although the performance of 1000 steps is slightly better than infinite steps, this aligns with the result of DNDM-absorb in Table 2, and therefore does not contradict our conclusion that the difference in Beta-distribution used does not significantly impact the performance comparison between 1000 steps and infinite steps. This suggests that the performance improvements are mainly attributed to the continuous time formulation itself.

Q3. How well does the model compare to RDM when the Beta distribution transition times are not used?

A3. We appreciate your insightful question. As detailed in the ablation study in Appendix C, we conducted experiments using various transition time distributions. The effect of different distributions can be seen as different schedules for selecting $\alpha_t$ in discrete diffusion models. In particular, In Table 4, $cosine^2$ schedule corresponds to the $\alpha_t$ schedule utilized in the RDM results. Overall, we observed a slight decrease in performance when not employing the Beta distribution. However, our approach still demonstrates superior performance compared to both RDM-absorbing and RDM-multinomial with comparable amounts of NFEs. Please refer to the following table and Table 4 in Appendix C for more details.

Q5. Also, I believe the authors also agree with, the proposed method does not outperform competitors in all shown cases. Sometimes the improvements are marginal.

A5. We agree. However, we want to clarify that the primary contribution of our method lies in its accelerated sampling speed. We use the term outperform to specifically refer to the enhanced sampling speed achieved by our method, as opposed to improvement in the overall generation performance (e.g., BLEU score). Instead, we show that under the same number of sampling steps, our approach attains a competitive BLEU score as RDM, with substantially faster generation. For example, for 1000 steps, RDM on WMT16 with k-absorb is slightly better than our 1000 steps, but is 20 times slower than our approach.

Q6. As a theoretical work, I appreciate the idea a lot, but the theoretical analysis is not that deep so I can safely vote for acceptance with no objection from the other reviewers and the AC. Deeper theoretical analysis related to sampling NFEs, approximation error with the original process, and techniques to further improve it could be much more appreciated.

A6. Thank you for your suggestion. In the appendix, we have added an analysis on the number of function evaluations (NFE). Specifically, in Theorem D.1, we have theoretically established that the NFE in our method will not exceed $(1 - (1 - \frac{1}{T})^{N})\cdot T$, as opposed to $T$ NFE for the original sampling method. This suggests that our method is more efficient in terms of NFE. Detailed proofs and discussions regarding NFE can be found in Appendix D.

Regarding the approximation error to the original process, we would like to clarify that there is no approximation error. In Appendix B.1, we have shown that our new process is equivalent to the original process in Eq.(1).

Q7. Algorithms like DPM-Solvers do not work in the language case? Please kindly tell me.

A7. The DPM-Solver [5] is exclusively designed for continuous diffusion applications. At the core of DPM-Solver is a specialized high-order ordinary differential equation (ODE) solver tailored for the semi-linear structure of continuous diffusion models (e.g., DDPM, VP-SDE and VE-SDE), employing methods such as Taylor expansions. It is unclear if DPM-Solver can be applied to discrete diffusion.

On the other hand, a lot of recent studies [6,7,8] have shown that continuous diffusion models do not work as well as GPT or discrete diffusion models for language generation.

[1] Hoogeboom, Emiel, et al. "Argmax flows and multinomial diffusion: Learning categorical distributions." Advances in Neural Information Processing Systems 34 (2021): 12454-12465.

[2] Austin, Jacob, et al. "Structured denoising diffusion models in discrete state-spaces." Advances in Neural Information Processing Systems 34 (2021): 17981-17993.

[3] Santos, Javier E., et al. "Blackout Diffusion: Generative Diffusion Models in Discrete-State Spaces." arXiv preprint arXiv:2305.11089 (2023).

[4] Ho, Jonathan, Ajay Jain, and Pieter Abbeel. "Denoising diffusion probabilistic models." Advances in neural information processing systems 33 (2020): 6840-6851.

[5] Lu, Cheng, et al. "Dpm-solver: A fast ode solver for diffusion probabilistic model sampling in around 10 steps." Advances in Neural Information Processing Systems 35 (2022): 5775-5787.

[6] Li, Xiang, et al. "Diffusion-lm improves controllable text generation." Advances in Neural Information Processing Systems 35 (2022): 4328-4343.

[7] Gong, Shansan, et al. "Diffuseq: Sequence to sequence text generation with diffusion models." arXiv preprint arXiv:2210.08933 (2022).

[8] Ye, Jiasheng, et al. "Diffusion Language Models Can Perform Many Tasks with Scaling and Instruction-Finetuning." arXiv preprint arXiv:2308.12219 (2023).

Thank you very much for your support! Below we address the questions.

Q1. This paper is not complete. First of all, it lacks ablation studies to demonstrate the influence of distributions of the transition time. With respect, I do not agree with that, all instances of transition times are equal in effect.

A1. Thank you for your suggestion. We have added several ablation studies regarding this matter. Specifically, in Table 4 of our revision, we present a comparison of the effects by different schedules of transition time on our algorithm's performance. For reference, we also provide the table of our ablation study here. We can see that our proposed Beta schedule outperforms previous schedules.

Additionally, Tables 7, 8, and 9 in our revision are dedicated to comparing the performance under various parameter choices in the Beta distribution.

Q2. Following up on the above point, why not the author study which instantiation of the transition time is the best for sampling, in the sense of quality and speed? Stopping at the distribution stage is not a good thought, I believe.

A2. If we understand your question correctly, it refers to a specific set of choices of transition times. The exploration of different transition times presents several practical challenges. First of all, the number of transition times equals N, corresponds to the length of a sentence, which is not fixed. Secondly, for long sequences with N=30, the total number of possible transition times is $T^{30} \geq 2^{30}$ . It is thus impractical to enumerate every possible instantiation. Therefore, we have focused our efforts on comparing the performance impacts of different distributions of transition times. Please see A1 for more details.

Q3. Another thing is the visualization of transition times, the $x_t$ at those times, and other related values. Letting me see that $x_t$ gets still after the transition time will make me more convinced of your method and creativity.

A3. In Figure 5 in Appendix G.3.1, we have included an entire generation trajectory of $x_t$ with respect to the transition time of each token. This trajectory shows how $x_t$ evolves over time following their respective transition times. In particular, $x_t$ gets still after $t=39$. We also provide a simplified trajectory in Figure 2(b).

Q4. Apart from that, the authors did not implement this work in image generation. I guess they may have a good reason for that, as diffusion is the dominating and most influential method in image generation. A method to improve diffusion sampling but not implemented on the image is strange. Are there anything barriers to the method to apply in images?

A4. Our paper primarily focuses on the acceleration of sampling for discrete diffusion models on discrete space, especially on models in the form of (1) in our paper, which includes multinomial diffusion [1] and absorbing diffusion [2]. Image generation, on the contrary, typically falls into the realm of continuous diffusion models due to the continuous nature of the image data. According to [1] and [3], the performance of discrete diffusion models for image generation, even the more sophisticated discretized Gaussian [2], or blackout models [3], is worse than the continuous diffusion models such as DDPM [4]. Therefore, we choose to prioritize evaluation of our models on discrete data generation tasks, as we don’t think discrete diffusion models can easily beat DDPM on image generation.

Dear Reviewer 7d5g, Thank you for increasing your score. We're glad that our rebuttal and revision have addressed your questions. Authors