Response to Reviewer 7sHz

Thank you for acknowledging our contributions. We have tailored our rebuttal to address the points you raised.

Weaknesses:

1. Problem Formulation: We will add more intuitive explanations and illustrations regarding the problem formulation. Below are the clarifications:

   • Intuition Behind the Absorbing Matrix $\mathbf{Q}^{\text{absorb}}$ (eq. (2.4)): In continuous-time Markov chains, the transition rate matrix $\mathbf{Q}_t = \sigma(t)\mathbf{Q}$ indicates the probabilities of moving from one state to another over an infinitesimally small time interval. For $\mathbf{Q} =\mathbf{Q}^{\text{absorb}}$, each state $i$ has a transition rate of 1 to the absorbing state (last state) and a rate of -1 on the diagonal representing leaving the original state. This ensures that once the system reaches the absorbing state, it remains there permanently.
   • Reason for DSE Loss Instead of Usual Score-Matching Objectives (e.g., MSE): MSE loss is derived under the assumption of Gaussian noise, which is not suitable for discrete data. It cannot guarantee that the concrete score remains positive, leading to poor performance. For more details, you can refer to Sections 2.2 and 3.1 in SEDD[1*].

2. Performance Verification of RADD:

   • We have updated the Table 2 to better demonstrate the effectiveness of RADD. See Table A in the overall response section for the updated results. After fixing the bug regarding to the ignored layernorm bias and hyperparameter tuning, it shows that two RADD models consistently outperform SEDD in all zero shot tasks for both model size.

Questions:

1. Kolmogorov's Forward Equation in Time-Dependent Settings:

   • Kolmogorov's forward equation holds generally for time-dependent settings. Its derivation is based on the Total Probability Theorem, making it applicable to both time-homogeneous and time-inhomogeneous Markov processes. For a detailed explanation, please refer to Section 4 in Feller [2*].

2. Intuition and alternative forms of $\mathbf{Q}$ :

   • The form of $Q^{\text{absorb}}$ is chosen to model states that transition into absorbing states where no further transitions occur. To the best of our knowledge, only the absorbing form and uniform form have been used in practice, with the absorbing form performing the best. Other forms may be inefficient in terms of computation and memory, as discussed in Section 3.3 of SEDD[1*].

[1*] Aaron Lou, Chenlin Meng, and Stefano Ermon. Discrete diffusion modeling by estimating the ratios of the data distribution, 2024

[2*] W Feller. On the theory of stochastic processes, with particular reference to applications. In Proceedings of the [First] Berkeley Symposium on Mathematical Statistics and Probability. The Regents of the University of California, 1949.

Response to Reviewer vbN2

Thank you for your extremely thorough review and constructive feedback on our paper. Below, we address your concerns and suggestions.

Correction of Theorem 2 and Corresponding Experiments

• Modification on Section 3.3: We acknowledge the error in Theorem 2. Eq.(C.14) in the proof is indeed a lower bound, as you correctly pointed out. To address this, we will remove the current Section 3.3 and replace it with a discussion on any-order auto-regressive models (AO-ARM) [1*,2*,3*] as suggested. Specifically, the revised section will discuss the equivalence between the absorbing discrete diffusion objective of DCE loss and any-order autoregressive training objective.

  Revised Proof Structure

  • Appendix C.1 and C.2: We will retain the first two steps corresponding to Appendix C.1 and C.2, which prove the equivalence between the DCE loss and Eq.(C.13): $d \mathbb{E}_ {k \sim U(\{1, \cdots, d\})} \frac{1}{k} \mathbb{E}_ {\tilde{\boldsymbol{x}} \sim U\left(\tilde{\mathcal{X}}_ k\right)}\sum_ {\tilde{x}^i=[\mathbf{M}]}-\log q_\theta\left(x_0^i | \tilde{\boldsymbol{x}}^{\mathrm{UM}}\right).$

  • Appendix C.3: In the last step in Appendix C.3, we will remove the unnecessary parts and directly reduce Eq.(C.13) to Eq.(C.19), which is the training objective of any-order autoregressive models: $d \mathbb{E}_ {k \sim U(\{1, \cdots, d\})} \frac{1}{k} \mathbb{E}_ {\pi \sim U\left(S_d\right)} \sum_{r=d-k+1}^d \log q_\theta\left(x_0^{\pi(r)} \mid x_0^{\pi(<d-k+1)}\right).$

• Modification of Table 2: We will make the corrections to Table 2 as suggested. Specifically:

  • We will remove the SEDD-S* line from Table 2, as it is based on the incorrect Theorem 2.
  • After fixing the bug mentioned in our overall response, we will update the DSE and DCE results for RADD-small and RADD-medium in Table 2, which show that RADD models outperform SEDD models.
  • We will also add baseline results of any-order autoregressive models (AO-ARM) trained on Eq.(C.19).

The complete revised table will be as follows:

Table B

Clarification on Figure 2 Perplexity with and without Cache

We appreciate your insightful analysis and the questions raised regarding the performance discrepancy between the RADD model with and without cache in Figure 2. Based on your suggestion, we have conducted additional entropy measurements for both SEDD and RADD models. We replicate the sampling 1024 times independently and compute the mean/std of the unigram entropy. The results are as follows:

Table C

Unigram Entropy for SEDD-small model

Table D

Unigram Entropy for RADD-small-dce model

It shows that your analysis is correct. Both the SEDD-small and RADD-small-dce models exhibit a decrease in unigram entropy as the number of sampling steps increases. This decrease suggests that the models generate simpler sentences with more sampling steps, which corresponds to the observed lower perplexity scores. Therefore, the perplexity doesn't converge in the limit of many steps.

The underlying cause of this phenomenon remains unclear and seems to be a common issue for masked language models. We will add the experiment and discussion in the revision. If you have further suggestions, we welcome your feedback.

[1*] Benigno Uria, Iain Murray, and Hugo Larochelle. A deep and tractable density estimator. ICML, 2014

[2*] Emiel Hoogeboom, Alexey A. Gritsenko, Jasmijn Bastings, Ben Poole, Rianne van den Berg, and Tim Salimans. Autoregressive diffusion models. ICLR, 2022.

[3*] Andy Shih, Dorsa Sadigh, and Stefano Ermon. Training and inference on any-order autoregressive models the right way. ICML, 2022.

Response to Reviewer 9MAq

Thank you for the detailed review and acknowledgment of our contributions. Below we address specific questions.

• Q1: Misleading speeds up declaration.

• A1: We apologize for any confusion caused by the initial claim of our speed-up results. We will revise our statement to emphasize that the speed-up is significant mainly in large steps (e.g., 4096), and the 3.5x speed-up does not generalize to all steps.

• Q2: Mistranslation between Figure 2 and Table 1

• A2: Sorry for the confusion regarding the discrepancy between Figure 2 and Table 1. The yellow line and the green line in Figure 2 represent the same perplexity results but with different x-axis. Specifically:

  • RADD Small without cache (yellow line), the x-axis represents NFE, equivalent to sampling steps in this context.
  • RADD Small with cache (green line), the x-axis represents E-NFE, which is less than the actual sampling steps due to the efficiency introduced by caching.

  For space constraints in the figure, we presented 8 data points for RADD Small without cache and 11 data points for RADD Small with cache. However, only 8 data points are shown in Table 1 to for consistency in the comparison. In the revised version, we will update the x-axis label in Figure 2 to 'NFE/E-NFE' and provide more detailed clarifications.

• Q3:The exact likelihood computation is never applied. I want table 2 to showcase this exact likelihood instead of just a bound.

• A3: We appreciate your feedback on the exact likelihood computation. Another reviewer pointed out an error in our proof in Theorem 2, which impacts the exact likelihood computation. As part of our response to Reviewer vbN2, we have acknowledged the error in Theorem 2 and committed to revising. Please refer to the first section of our response to Reviewer vbN2 for detailed corrections and updated experimental results.

• Q4: The improvements are marginal. The model size is only small. I want to see a similar improvement for the medium quality.

• A4: We have updated our results to demonstrate the effectiveness of RADD for both small and medium models. Please see the overall response section for updated results. It shows that our methods also apply to medium-sized models with consistent improvements over SEDD in all zero-shot tasks.