Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper proposes Discrete Denoising Diffusion Probabilistic Models (*D3PMs*), a type of generative diffusion model for discrete and categorical data. It largely builds on previous frameworks but defines new transition kernels for the discrete Markov chain that perturbs the data. On top of the usual variational lower bound diffusion model objective, the paper also suggests to use an additional loss component in its training objective that corresponds to an additional reconstruction objective given perturbed data. Quantitatively, the proposed *D3PM* improves upon previous discrete denoising diffusion models, but its performance remains lower than standard autoregressive models in text generation and lower than continuous denoising diffusion models in image generation.
main_review: __Originality:__ Regarding the conceptual innovations, the paper builds on standard diffusion models [1] and their discrete generalizations [3,4], merely suggesting different transition kernels for the forward discrete diffusion. The additional reconstruction loss for model training is also not based on any novel or fundamental theory and can likely be interpreted as some sort of overall loss reweighting for different $t$, which has been discussed before. On the other hand, the idea to define transitions based on proximity in embedding space is interesting and the connections between the diffusion with absorbing states and masked language models are also insightful. Nevertheless, the paper overall feels incremental regarding its methodological innovations (more specific feedback below).

__Clarity:__ The paper is well written and easy to read.

__Specific Questions and Feedback:__

1. The paper says that the KL terms are estimated by simply summing over all categories (line 101). Does this potentially impact the scalability of the model or is it fine? Models such as GPT-2, for example, seem to have vocabulary sizes of up to 50.000.
2. The paper suggests new ways to parametrize the transition kernels Q. These are motivated heuristically. Could we potentially derive "optimal" Q's one way or another? Is there the possibility to somehow learn Q?
3. The paper suggests to define transitions based on proximity in an embedding space (D3PM-NN). While this is very interesting and makes intuitively sense, the paper remains a bit vague on it and I am thinking whether this idea has more potential. How exactly are the embeddings obtained? Can we learn them, maybe end-to-end?
4. In section 3.4 the paper proposes an additional loss function, a cross entropy term representing a reconstruction of $x_0$, given $x_t$. As the authors write, this is very similar to the diffusion's KL terms, which are similarly minimized when $p$ correctly predicts $x_0$ from $x_t$. Hence, we can interpret these KL terms in practice also as similar reconstruction objectives, just with different weightings for different $t$. I could imagine that this additional loss term therefore boils down to being an indirect way of reweighting the different reconstruction losses for different $t$, thereby specializing the model for different $t$ ranges. Such reweightings have been discussed before already [2]. These connections could be discussed better, I think.
5. In Section 4, the paper discusses connections between diffusion models and well-known models such as BERT and masked language models and autoregressive models more generally. It is pointed out that these can be interpreted as special diffusion models. With this interpretation, wouldn't we think that a more general diffusion model, as potentially defined in this paper, can outperform them (which is not the case)? How can we leverage these connections and insights specifically to construct diffusion models that indeed outperform these models?
6. The connection between autoregressive models and diffusion models has been discussed before ([1], section 4.3). It would be appropriate to acknowledge that.

__Conclusions:__ The conceptual contributions of the paper are incremental and the quantitative results are not impressive, improving upon previous discrete diffusions, but still being significantly behind standard autoregressive models for text generation and standard continuous diffusion models for image generation. In conclusion, I think the paper contains some interesting ideas, but does overall not quite meet the bar.


[1] Ho et al. "Denoising Diffusion Probabilistic Models", https://arxiv.org/abs/2006.11239; [2] Durkan and Song "On Maximum Likelihood Training of Score-Based Generative Models", https://arxiv.org/abs/2101.09258v1; [3] Hoogeboom et al. "Argmax Flows and Multinomial Diffusion: Learning Categorical Distributions"; [4] Sohl-Dickstein et al. "Deep Unsupervised Learning using Nonequilibrium Thermodynamics"
limitations_and_societal_impact: __(Negative) Societal Impact:__ Has been discussed very briefly, but in a satisfactory manner. Optionally, the authors could also mention the creation of fake texts and images, which indeed has been a concern for large-scale state-of-the-art image and text generation models.

__Limitations:__ The most important limitations have been pointed out appropriately. This is, on image generation the proposed model is inferior to continuous diffusion models, and on text generation the model is worse than typical autoregressive models.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper introduces diffusion models for discrete data which generalizes multinomial diffusion model (Hoogeboom et al. 2021) by going beyond corruption processes with uniform transition probabilities. To achieve that, it presents a set of corruption processes with structured transition matrices. The authors have also drawn a connection between their discrete diffusion models and autoregressive / mask-based language models. The proposed model outperforms previous non-autoregressive generative model in text domain. On the image dataset CIFAR-10, it achieves comparable results as Gaussian DDPM model.
main_review: Originality:
- This paper generalizes multinomial diffusion model (Hoogeboom et al. 2021) and makes several nontrivial technical contributions to improve the model performance. 
- The proposed structured transition matrices are interesting, although the domain-specific design may not work well in practice. For example, the token embedding distance doesn’t work well for text. 
- This makes me wonder the possibility of making a trainable transition matrix, although this will lead to a model more like a variational autoencoder instead of diffusion model.

Quality:
- The submission is technically sound.

Clarity:
- The paper is well written. The authors tried to elaborate the ideas in main text and left the technical details in appendix. 

Significance:
- The empirical result in text domain is compelling among other non-autoregressive models. But it is still far away from autoregressive models. 
- The D3PM Gauss can perform comparable as Gaussian DDPM for images, but it is just an imitation of Gaussian DDPM in discrete domain. I kind of miss the motivation of doing it here.

Detailed comment:

1, “When the number of time steps T goes to infinity, both the forward process and the reverse process share the same functional form [10], allowing the use of a learned reverse process from the same class of distributions as that of the forward process”
Could the authors elaborate this argument? If both the forward and reverse process are Gaussian, they share the same functional form anyway, even with finite T steps. Why does it matter here?

2, In Table 1 & 2, the D3PM results are much worse than autoregressive transformer (as expected). An important question would be: when the model sizes scale up, will the perplexity gap between D3PMs and autoregressive models increases or decrease? For sample, a 24-layer Transformer-XL reduces the perplexity than the 12-layer Transformer.  

limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper generalizes diffusion models from Bernoulli distributions to categorical distributions. The proposed method supersedes masked training in BERTS and autoregressive learning. Authors examined different designs of the transition matrices and demonstrated the proposed method in both language and image modeling. Additional tricks like auxiliary cross entropy loss function and carefully designed noise schedules further improve the performance.
main_review: **Significance**: Recent progress in image and audio generation has lead to renewed interest in diffusion models. However, most of those applications correspond to continuous distributions. It is therefore very interesting to see whether the principles of diffusion models can be competitive at modeling discrete distributions. This work has demonstrated that discrete diffusion models can be applied to text and image modeling. Although the performance on text generation is only lukewarm, the image generation experiments are encouraging and can send a strong message to the research community.

**Clarity**: Paper is very clearly written and easy to follow.

**Originality**: The submission has mediocre originality, since the formulation of discrete diffusion models is not new and can be traced back to [Sohl-Dickstein et al. 2015], and [Hoogeboom et al. 2021]. Authors' contributions are more on the side of improving practical performance, through designing effective transition matrices, loss functions, and noise schedules. The latter two are also directly inspired by previous work on continuous-space diffusion models. The interpretation of BERT and autoregressive models as special cases of the proposed method is neat, but it doesn't give many practical insights since the experimental performance of D3PM is still inferior to autoregressive counterparts especially on text modeling. Overall the contributions are a bit incremental.

**Quality**: 

1. Experimental results on character-level text generation is not very impressive. Discrete flows and transformers outperform D3PM significantly in terms of NLL. Authors highlighted the speed advantage of D3PM against transformers. However, I wonder whether authors have correctly cached states when sampling from transformers. I would expect that with the same number of model steps, sampling from transformers should be significantly faster than D3PM as the former can use caching to remove redundant computation for adjacent characters. In both Table 1 and Table 2 I found transformers to have comparable sampling time with D3PM under the same number of model steps, which seems to indicate that no caching was implemented for transformers.

2. The transition matrix designed with token embedding distance (D3PM NN) does not give convincingly better results than more naive alternatives. This says that incorporating structure in those transition matrices didn't help. Other than the experiment on text8, no other experiments demonstrate the importance of structures in D3PM. Therefore, the title "Structured Denoising Diffusion Models" is not very appropriate, since no structure is observed in most experiments, and incorporating structure didn't boost performance.

**Post rebuttal**: Authors have addressed most of my concerns.

limitations_and_societal_impact: Authors have mentioned the negative societal impact and misuse of their approach, and I see no other obvious issues.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper introduce a novel method for discrete state space. The main contribution is as follows:

1. propose new discrete diffusion process based on Markov transition matrices Qt. 

2. proposed multiple transition matrices  - Uniform, Absorbing state, Discretized Gaussian, Token embedding distance

3. proposed new noise schedule for the forward process based on the mutual information between x_t to x_0

4. introduce new auxiliary denoising objective, which improve the prediction of x_0

The paper also discuss the connection to other probabilistic models for text - BERT, AR, MLM.
The paper check the performance on two domains - text and images and show significant improvement over the previous diffusion model by Hoogeboom et al.



main_review: The paper introduce a novel method. However, i have the following concerns:

1. Although the paper improve by significant gap the previous diffusion based results. The results for text generations is very low. The results is comparable to 2016 BN-LSTM paper in text8 dataset, and for LM1B, simple RNN with 9gram get better results [https://arxiv.org/pdf/1312.3005v3.pdf]. Furthermore, for cifar10, the results is worse then previous diffusion process (DDPM++, DDIM)

2. Missing results for the proposed method (D3PM NN) on LM1B.

3. It seems that the Absorbing state idea is very similar to previous methods (BERT for example) model, since it change the [MASK] with some token each timestep. Can you explain why the proposed method is better than other AR model? Furthermore, the paper state "BERT is a one-step diffusion model". Why the performance of the proposed models is degraded comparing to transformer models?

4. It will be interesting to see if you can learn the matrices Qt. The idea "Token embedding distance" is one step toward this.  


Although the paper has the above drawbacks, i think that the paper is very interesting for the community since it is step toward making diffusion models suitable for NLP tasks. Therefore, i vote to accept the paper.

limitations_and_societal_impact: Yes, the author address the limitation of their work in sec8.
review_title: null

Meta-review: This paper presents a framework for learning denoising diffusion models in discrete space. Although there are valid criticisms around the novelty of the discrete denoising diffusion models and the inferior performance compared to the autoregressive models (in sampling time and NLL), the main novelty of this work is around the clever design of Markov transition matrices. Given the importance of both modeling distributions over discrete variables and text modeling without an autoregressive structure, I am recommending this paper for acceptance. 
Decision: Accept (Poster)