Structured Denoising Diffusion Models in Discrete State-Spaces
Authors: Jacob Austin
Daniel D. Johnson
Jonathan Ho
Daniel Tarlow
Rianne van den Berg
Venue: NeurIPS 2021 Poster (2021)
Keywords: diffusion models
generative models
text generation
probabilistic models

Abstract: Denoising diffusion probabilistic models (DDPMs) [Ho et al. 2021] have shown impressive results on image and waveform generation in continuous state spaces. Here, we introduce Discrete Denoising Diffusion Probabilistic Models (D3PMs), diffusion-like generative models for discrete data that generalize the multinomial diffusion model of Hoogeboom et al. [2021], by going beyond corruption processes with uniform transition probabilities. This includes corruption with transition matrices that mimic Gaussian kernels in continuous space, matrices based on nearest neighbors in embedding space, and matrices that introduce absorbing states. The third allows us to draw a connection between diffusion models and autoregressive and mask-based generative models. We show that the choice of transition matrix is an important design decision that leads to improved results in image and text domains. We also introduce a new loss function that combines the variational lower bound with an auxiliary cross entropy loss.  For text, this model class achieves strong results on character-level text generation while scaling to large vocabularies on LM1B. On the image dataset CIFAR-10, our models approach the sample quality and exceed the log-likelihood of the continuous-space DDPM model.

Structured Denoising Diffusion Models in Discrete State-Spaces
Jacob Austin, Daniel D. Johnson, Jonathan Ho, Daniel Tarlow Rianne van den Berg'
Google Research, Brain Team
(jaaustin, het.:iindddonnssooooonttteeeeee dtarrll
dtarlow, gggearrooo..ammeeeeerggggooooo. com
Abstract
Denoising diffusion probabilistic models (DDPMs) have shown impressive results on image and waveform generation in continuous state spaces. Here, we introduce Discrete Denoising Diffusion Probabilistic Models (D3PMs), diffusion- like generative models for discrete data that generalize the multinomial diffusion model Hoogeboom al. [8]. by going beyond corruption processes with uni- form transition probabilities. This includes corruption with transition matrices that mimic Gaussian kernels in continuous space, matrices based on nearest neighbors in embedding space, and matrices that introduce absorbing states. The third al- lows us to draw a connection between diffusion models and autoregressive and mask-based generative models. We show that the choice of transition matrix is important design decision that leads to improved results image and text domains. We also introduce new loss function that combines the variational lower bound with an auxiliary cross entropy loss. For text, this model class achieves strong results character-level text generation while scaling large vocabularies LMIB. On the image dataset CIFAR-10, our models approach the sample quality and exceed the log-likelihood of the continuous-space DDPM model.
1 Introduction
Generative modeling is a core problem machine learning, useful both for benchmarking our ability to capture statistics of natural datasets and for downstream applications that require generating high-dimensional data like images, text, and speech waveforms. There has been a great deal of progress with the development of methods like GANs [14
large autoregressive and others, each with their own tradeoffs in terms of sample quality, sampling speed, logllikelshoods, and training stability.
B VAEs 22 32
neural network models 44
44 normalizing flows 31
ITI 21
Recently, diffusion models (36 have emerged compelling alternative for image 17
33 and au-
dio 7 2 generation, achieving comparable sample quality to GANs and log- ligliiilssoods comparable autoregressive models with fewer inference steps. diffusion model is parameterized Markov chain trained to reverse predefined forward process, which is a stochastic process constructed to gradually corrupt training data into pure noise. Diffusion models are trained using a stable objective closely related to both maximum likelihood and score matching [19 25 and they admit faster sampling than autoregressive models by using parallel iterative refinement
Although diffusion models have been proposed in both discrete and continuous state spaces 36 most recent work has focused on Gaussian diffusion processes that operate in continuous state spaces (e.g. for real-valued image and waveform data). Diffusion models with discrete state spaces have
35th Conference on Neural Information Processing Systems (NcurIPS 2021).
"Equal contributions
Now at Microsoft Research

---

data cample at 1=0
uniform (=T/22
Goussian (1=1/2)
absorbing (=T//2
q و (
forward process)
Po (20-11 (24))
(reverse process)
generated at t-0
t=1/4
t-
1-T (stationary)
Figure 1: D3PM forward and (learned) reverse process applied quantized swiss roll. Each dot represents 2D categorical variable. Top: samples from the uniform, discretized Gaussian, and absorbing state D3PM model forward processes, along with corresponding transition matrices Q. Bottom: samples from a learned discretized Gaussian reverse process.
been explored for text and image segmentation domains [8] but they have not yet been demonstrated as competitive model class for large scale text or image generation.
Our aim in this work is to improve and extend discrete diffusion models by using a more structured categorical corruption process to shape data generation, as illustrated in Figure I Our models do not require relaxing embedding discrete data (including images) into continuous spaces, and can embed structure or domain knowledge into the transition matrices used by the forward process. We achieve significantly improved results by taking advantage of this flexibility. We develop structured corruption processes appropriate for text data, using similarity between tokens to enable gradual corruption and denoising. Expanding further, we also explore corruption processes that insert [MASK] tokens, which let us draw parallels to autoregressive and mask-based generative models. Finally, we study discrete diffusion models for quantized images, taking inspiration from the locality exploited by continuous diffusion models. This leads to a particular choice of discrete corruption process that diffuses preferentially to more similar states and leads to much better results in the image domain.
Overall, we make number of technical and conceptual contributions. Beyond designing several new structured diffusion models, we introduce new auxiliary loss which stabilizes training of D3PMs and family of noise schedules based on mutual information that lead improved performance. We strongly outperform various non- non-autoregressive baselines for text generation on character- text generation, and successfully scale discrete diffusion models to large vocabularies and long sequence lengths. We also achieve strong results on the image dataset CIFAR-10, 10, approaching or exceeding Gaussian diffusion model from Ho et al. 17 on ligliiielsoooss and sample quality.
2 Background: diffusion models
Diffusion models 36 are latent variable generative models characterized by forward and reverse Markov process. The forward process q(#1:T I'- ( (z.-1) corrupts the data æo ((z)) into a sequence of increasingly noisy latent variables æı.r = Στ, Ø2,..., Tr. The learned reverse Markov process (o("))) = p(ær) IT_ (0; | gradually denoises the latent variables towards the data distribution. example, for continuous data, the forward process typically adds Gaussian noise, which the reverse process Ieams to remove.

---

In order to optimize the generative model po (2o) to fit the data distribution g(zo), we typically optimize a variational upper bound on the negative log- ne-likelihood:
T
Lvb Bg(w)o
D ( (o)))(((T +
Bylwe (wo)) DKLLl pe xD) 100
Lr
E Eggan (ma) llog po ( x1
When the number of time steps T' goes to infinity, both the forward process and the reverse process share the same functional form [36]]]]]]]] 12]. in the sense that the true posterior q(xx,_1<ze) becomes fully conditionally independent This motivates using a conditionally independent approximate reverse process (= (ax)) from the same class of distributions
that of the forward process.
Furthermore, for several choices of the forward process the distribution q( (zo) converges to a stationary distribution I (xx) in the limit t + oo independent of the value of Zo. When the number of time steps T' is large enough and we choose π (æ:) as the prior p(ær), ) we can guarantee that the Lr term in ① will approach zero regardless of the data distribution ((20)). (Alternatively, learned prior po (-)
can use
While ((-1) can in theory be arbitrary, efficient training of pe is possible when ((,,)x
Permits efficient sampling of x; from (( for an arbitrary time t, allowing us to randomly sample timesteps and optimize each LŞ-1 term individually with stochastic gradient descent,
2. Has tractable expression for the forward process posterior (1 vo), which allows to compute the KL divergences present in the Lt-1 term of
28 defines the forward and po N' (æ.-1|uo((;; (), Eo(x,, ()), respectively. The aforementioned properties hold in the case of these Gaussian diffusion models: the forward process q(æ,) (mo) converges to a stationary distribution, motivating the choice p(ær) N (00 (0, 7), and both q( ( (m)) and g( (0) are tractable Gaussian distributions for which the KL divergence can be computed analytically.
The majority of recent work in continuous spaces and reverse distributions q(
N (æ -, 1,11
Diffusion models for discrete state spaces
Diffusion models with discrete state spaces were first introduced by Sohl-Dickstein et al. 36), who considered a diffusion process over binary random variables. Hoogeboom et al. [ extended the model class to categorical random variables with transition matrices characterized by uniform transition probabilities. In their supplementary material, Song et al. 3i also derived this extension, although no experiments were performed with this model class. Here, we briefly describe a more general framework for diffusion with categorical random variables which includes these models as special cases
For scalar discrete random variables with K categories 2t, xt-1 E 1...., K the forward transition probabilities can be represented by matrices: [Qrlis qIx, f| = i). Denoting the one-hot version of x with the row vector æ, we can write
q Cat( zz- QQ)),
where Cat(#;;) p) is categorical distribution the one-hot row vector æ with probabilities given by the row vector p. and æ Qe is to be understood as a row vector-matrix product. We assume that Q: is applied to each pixel of an image or each token in a sequence independently. and that q factorizes over these higher dimensions as well; we thus write (x))) in terms of a single
Forr continuous state spaces and Gaussian g. the limit T' co corresponds stochastic differential equation 40). whereas for discrete state spaces corresponds to Markov jump process. "Our implementation of D3PM framework is available at https: //g thub. www.//oooll----oeerrr..oooo httgglooeeeeeerrreeeee//eaa/ee/e
3

---

element. Starting from Zu, we obtain the following t-step marginal and posterior at time - 1:
g( (2)) = Cat ( = x0Q4). with Q2 - Qs
0 x0)) = ( 0 mo 2o)g 120) = Cat 21-1;p= Q,Q, 20Q
(3)
q (2))
xe Q.
Note that due to the Markov property of the forward process g( [ m70) (2) As- suming that the reverse process pa (z) - is also factorized as conditionally independent over the image or sequence elements, the KL divergence between q and pa can be computed by simply summing over all possible values of each random variable; we thus satisfy criteria I and 2 discussed in Section 2 Depending on Qi, the cumulative products Q, can often be computed in closed form, or simply precomputed for all L. However, for large K and large T this may be prohibitive. In Appendix A.4 we discuss how to ensure Q, can still be computed efficiently in this case, allowing the framework to scale to a larger number of categories.
In the next section we discuss the choice of the Markov transition matrices Q: and corresponding stationary distributions. From here on, we refer to the general class of diffusion models with discrete state spaces as Discrete Denoising Diffusion Probabilistic Models (D3PMs).
3.1 Choice of Markov transition matrices for the forward process
An advantage of the D3PM framework described above is the ability to control the data coruuption and denoising process by choosing Q:, in notable contrast to continuous diffusion, for which only additive Gaussian noise has received significant attention. Besides the constraint that the rows of Q must sum to one to conserve probability mass, the only other constraint in choosing Q: is that the f when becomes large,
rows of Q, = Q1Q2... Q must converge to a known stationary distribution which can be guaranteed while imposing minimal restrictions on Q. (see Appendix A.
We argue that for most real-world discrete data, including images and text, it makes sense to add Nomain-dependiee structure to the transition matrices Q: as way of controlling the forward corruption process and the learnable reverse denoising process. Below we briefly discuss the uniform transition matrices that have been studied in prior work [8] along with set of structured transition matrices we have explored for our image and text dataset experiments; see Appendix A.. for more details on each matrix type. We also note that this set is not exhaustive, and many other transition matrices could also be used within the D3PM framework.
Uniform (Appendix A.2.1). Sohl-Dickstein et al. (36] considered simple 2 x transition matrix for binary random variables Hoogeboom et al. [X later extended this categorical variables, proposing a transition matrix Q; = (1 - B + 3 K 11" with 3, E [0. 1]. Since this transition matrix is doubly stochastic with strictly positive entries, the stationary distribution is uniform. Because the transition probability to any other state is uniform, in this paper we equivalently refer to this discrete diffusion instance as D3PM-uniform.
A Absorbing state (Appendix A.2.2). Motivated by the success of BERT 10 and recent work on Conditional Masked Language Models (CMLMs) in text, we consider transition matrix with an absorbing state (called [MASK]. such that each token either stays the same or transitions to [MASK] with some probability 3.. This does not impose particular relationships between categories, similar to uniform diffusion, but still allows corrupted tokens to be distinguished from original ones. Moreover, the stationary distribution is not uniform but has all the mass the [MASK] token. For images, we reuse the grey pixel as the [MASK] absorbing token.
Discretized Gaussian (Appendix A.2.3). Instead of transitioning uniformly to any other state, for ordinal data we propose imitating a continuous space diffusion model by using a discretized, truncated Gaussian distribution. We choose normalization such that the transition matrix is doubly stochastic, leading to a uniform stationary distribution. This transition matrix will transition between more similar states with higher probability, and is well suited for quantized ordinal data such images.
Token embedding distance (Appendix A.2.4). Textual data does not have ordinal structure, but there may still be interesting semantic relationships. For instance, in a word-level vocabulary
*If a stationary distribution is not known, we can introduce a leamed prior pe (o(x)): ): we note that this is equivalent to extending the forward process by appending a rank-one matrix Q that ignores ør and produces deterministic #1+1, +1. then learning the reverse step po (TT+1) po (o(x))

---

synonyms or closely related words (like "dog" or "cat") may be more similar than other tokens. As a demonstration of the generality of the D3PM framework, we explore using similarity in word embedding space to guide the forward process, and construct doubly-stochastie transition matrix that transitions more frequently between tokens that have similar embeddings while maintaining a uniform stationary distribution.
For uniform and absorbing-statee state diffusion, the cumulative products Q, can be computed in closed the remainder can be precomputed.
form (see Appendix A.4.1)
3.2 Noise schedules
We consider several different options for the noise schedule of the forward process. For discretized Gaussian diffusion, we explore linearly increasing the variance of the Gaussian before discretizing it. (Note that a linear schedule for Q₁ leads to a nonlinear amount of cumulative noise in Q2.) For uniform diffusion we use the cosine schedule which sets the cumulative probability of transition to a cosine function, as introduced by Nichol and Dhariwal [2 and adapted by Hoogeboom et al. [ For general set of transition matrices Q: (such as the one based on token embeddings), previously proposed schedules may not be directly applicable. We consider linearly interpolating the mutual information between Ft and Zo to zero, i.e. m() (1 + H (ma). Interestingly, for the specific case of absorbing-state D3PMs, this schedule reduces to exactly the (T - L + 1) schedule proposed by Sohl-Dickstein et al. 36 for a Bernoulli diffusion process. See Appendix A.7 for more details.
3.3 Parameterization of the reverse process
While it is possible to directly predict the logits of pa pa(2 using a neural network nng (n;));),
we follow Ho al. 17 and Hoogeboom et al. [ and focus on using neural network mng (xx))
to predict the logits of a distribution Pe (To (zz), which we combine with g( [æt, wo) and a
summation over one-hot representations of 2% to obtain the following parameterization
pa ( x Σ (1)) (2ol
(4)
We note that under this xo prrrammttttiiioioonn the KL divergence
xt, 2o) (0. 1
will be zero if Po (én ax,) places all of its probability mass on the original value æn. The decomposition of qxx (e, 2o in (3) also provides us with motivation for this parameterization. According to (3) in a given state zt. the optimal reverse process only takes into account transitions to states for which g( 11 non-zero. Therefore, the sparsity pattern of Q2 determines the sparsity pattern of the ideal reverse transition probabilities in po (z,-1 (z,). The parameterization in 4 automatically ensures that the learned reverse probability distribution Po (2x (x:) has the correct sparsity pattern dictated by the choice of the Markov transition matrix Q.. This parameterization also lets us perform inference with k steps at time, by predicting ( (x.) = Σ ( x Fo (2:))
Finally, when modeling ordinal discrete data, instead of predicting the logits of (To æx)) directly with the output of a neural net, another option is model the probabilities with truncated discretized logistic distribution (see Appendix A.8). This provides an extra ordinal inductive bias to the reverse model and boosts FID and log-like likelihood scores for images.
3.4
Loss function
While the original diffusion models introduced by Sohl-Dickstein et al. [66 were optimized with the negative variational lower bound Lub of ( more recent diffusion models are optimized with different objectives. For instance, Ho et al. [17] derive a simplified loss function (Lsampte) that reweights the negative variational bound, and Nichol and Dhariwal ( explore hybrid loss Laybrid = Lsimple + XL (using one term to learn the predicted mean and the other to learn predicted variance). Inspired by this recent work, we introduce an auxiliary denoising objective for the To parameterization of the reverse process, which encourages good predictions of the data æn at each time step. We combine this with the negative variational lower bound, yielding the following alternative loss function:
LA = -Lyb + À By(zo) B (20) |- log (o [z:)]
(5)
5

---

We note that the auxiliary loss resembles the cross entropy term Lo in ① at t = 1, and so one might expect that is a KL reweighting similar the one described by Ho al. [77. However, our L^ directly supervises the model output
This is in general stronger source of supervision than any reweighting of the terms in the lower bound ( which only provides supervision through the sum in ② To see this, note that for fixed Zo. both DKL (g (q(2;-1 [2, mo (Po)llaa(aaa (x; [æz)]] and Eig(a (mo) l- log Pa (2o [x]] are minimized when pa (2o (r)) ) has all its mass on the datapoint vo. but for some choices of y there may be different setting Ho + Do that induces the same distribution po(0;-1 (t). We find that training with this loss leads to improved quality of image samples.
4 Connection to existing probabilistic models for text
In this section we expand on interesting connections between the D3PM framework and several existing probabilistic and language modeling approaches.
One possible D3PM transition matrix is combination of uniform transition matrix and an absorbing state at the [MASK] token (i.e. Q = alle + +311"/
BERT is one-step diffusion model:
(1 a1-a- I, where em is one-hot vector on the [MASK] token). For one-step diffusion process in which ((2) (zp)) replaces 10% of tokens with [MASK] and 5% uniformly at random, this leads
precisely to the BERT denoising objective, i.c. Lb LT Eg((r1 [log po (o (1)) LBERT. since Lr is constant independent of 0 (assuming a fixed prior).
Consider diffusion process that deter- ministically masks tokens one-by-one in a sequence of length N = T: ((xr), 2n) = [xn]e if < N else [MASK]. This is a deterministic forward process, so (x: Z2) is delta distribution on the I₁ sequence with one fewer mask: q( (xt--1, [t, mD) = 0/..]. if + T T -t else 6[0o]: While this process not applied independently to each token, it can be recast as an independently-applie diffusion process on the product space [O...N] x V, where each token is tagged with its position in the sequence, V is the vocabulary, and Q is N x | N [V] sparse matrix.
Autoregressive models are (discrete) diffusion models:
Because all tokens except the one at position i = T - t have deterministic posteriors, the KL divergence Dxz (q( [x [ æo) pe([ [z))) is zero for all other positions. The only token for which this is not true is the token at position i, for which D D (9([xx-1)))) xo) (z))))=)))(z = 10-1op log po [axo]: (z:)), the standard cross entropy loss for an autoregressive model.
(Generative) Masked Language-Models (MLMs) are diffusion models: Generative Masked Lan- (477 are generative models that generate text from a sequence of [MASK] tokens. They are usually trained by sampling a sequence Wo, masking tokens according to some schedule, and learning to predict the masked tokens given context. It turns out that D3PM absorbing ([MASK)) model trained on the usual ELBO objective with the parparameteiiztioonn from 3.3 reduces to reweighted version of this MLM objective (see Appendix A.3 for detailed derivation).
guage Models (13)
5 Text generation
For text, we experiment with generation on two datasets: text8 (26] a character-level dataset extracted from eoglish-languagee Wikipedia, and the One Billion Word dataset (LMIB) 3 a large dataset of shuffled Boglish-languagg sentences. For both, we train a D3PM uniform model based on the work by Hoogehoom al. [18] (D3PM uniform) and a model that masks tokens (D3PM absorbing). We also consider model that transitions uniformly to nearest neighbors in a token embedding space (D3PM NN). We follow Hoogeboom et al. [[8] and use T = 1000 timesteps, although we are also
able to evaluate on fewer due to the parameterization in Section 3
5.1 Character-level generation on text8
text8 is a character-level text dataset consisting of small vocabulary of 27 tokens: the letters 'a'-'z' and the "whitespace token. We follow the convention of training and evaluating text8 in chunks of length 256 without any preprocessing [8. For nearest-neighbor D3PM, our nearest neighbor graph in character-space is shown in Appendix B D3PM uniform models were trained with cosine schedule from Hoogehoom et al. [8]] (ablations in Appendix B.2.T. while D3PM absorbing and D3PM NN models were trained with mutual information schedule.

---

Table 1 shows that for D3PM, the D3PM absorbing model performed the best, exceeding the uniform and NN diffusion models. We were able to improve upon the baseline result of [8] with hyperparameter tuning, and our uniform and NN results outperformed results from Hoogehoom et al. [18] across all inference steps, down to as few as 20. We found that I.x=0.01 worked best for D3PM absorbing, while Lub was better for D3PM uniform. Our model outperforms all non- autoregressive baselines except one, the Discrete Flow model [ (for which unfortunately no open-source implementations exist), and is also faster than all but one method, the IAF/SCF model [9]. It also nearly 20x faster than an autoregressive transformer of the same size. We note that while our 20-step D3PM models in Table T are much faster than a comparable autoregressive transformers, this table only shows timings for batch size 1 (per device). For larger batches, autoregressive caching allows transformers perform inference relatively more quickly. We include additional benchmarks and a plot of inference time as a function of iterations Appendix [..2 D3PM with the mask absorbing token was by far the best performing model, which lends credibility to the use of masks in denoising auto-encoders. Nearest-neighhor diffusion only narrowly improves upon a D3PM-uniform model: this was a surprising negative result for us, suggesting that not all notions of structure meaningful.
5.2 Text generation on LMIB
Text generation for large-scale text datasets and large vocabularies with discrete diffusion models has not been previously demonstrated. We include results from LMIB as a proof of concept, showing that these models indeed scale (as discussed in Appendix A.4). and that the D3PM absorbing model continues to excel. All models were trained and evaluated on packed sequences of length 128, using a sentencepiece vocabulary of size 8192.
Table 2 contains results from experiments on LMIB. Overall, mask diffusion (D3PM absorbing) does relatively well, approaching the performance of comparable autoregressive model of the same size, and scaling to far fewer steps, while uniform diffusion performs significantly worse. We find, surprisingly, that the D3PM NN model performs worse than the uniform model in terms of log likelihoods (although it demonstrates unique qualitative behavior). This suggests that word embedding similarity may not be meaningful kind of locality in a diffusion process. We found the the Lx=0.01 loss worked best for the mask absorbing model, but reduced performance for the other models. We note the surprising scaling in perplexity in Figure 2] achieving strong results with as few as 10 inference steps. We also show samples from our model and completions from corrupted samples.
Table I: Quantitative results on text8. NLL is reported on the entire test set. Sample times are for generating a single example of length 256. Results are reported on two seeds. All models are standard 12 12-layer transformers unless otherwise noted. i'Tranffrmme XL is a 24-layer transformer, using 784 context window. Results reported by 18 by running code from official repository.
Model
Model steps
NLL (bits/char) (L)
Sample time (6) (L)
Discrete Flow 3 (8 layors)
1.23
0.16
Argmax Coupling Flow [E]
1.80
0.40 + 0.03
TAF/ SCF 49]
1.88
0.04 + 0.0004
Multinomial Diffusion (D3PM uniform) IS
1000
1.72
26.6 + 2.2
D3PM uniform (ours)
1000
1.61 0.02
3.6 0.4
D3PM NN (Lvb) (ours)
1000
1.59 + 0.03
3,1474 = 0.0002
D3PM absorbing (Ixxzo 01) (ours)
1000
1.45 0.02
3.4 0.3
D3PM uniform 1R (ours)
256
1.68 0.01
0.5801 1 0.0001
D3PM NN (T.rb) (ours)
256
1.64 0.02
0.813 0.002
D3PM absorbing (Lx=oo.1) (ours)
256
1.47 + 0.03
0.598 + 0.002
Transformer decoder (ours)
256
1.37
0.3570 0.0002
Transformer decoder 11
256
1.18
Transformer XL
0
256
1.08
D3PM uniform B (ours)
20
1.79 + 0.03
0.0771 - 0.0005
D3PM NN (Lvb) (ours)
20
1.75 0.02
0.1110 0.0001
D3PM absorbing (Lx= (ours)
20
1.56 0.04
0.0785 0.0003
7

---

uniform mask
== 128 [NASK] [SBSK] [SASK] [MASK] [MASK] [HASK] ....
1100
union said [MASK] backflow fund [MAS]a would faon further inwestigatich
25
susporae
the denands [MASK] [MASK]V Rockwza
1000
900
rine.
Perploiity
800-
t In reaponse to the devanda the Community Workars union said the backflow fund nanagera would face Surther investigation and fine
700
500
400
Original: Caterpillar is cager to expand in Asia vaere it trails local competitoza auch as Beratau Ltd
200
Corrupted: Caterpillar is eager expand Ln [MSSK] [MASK] it [MASK] a local corpetitors auch as Koratsu Ltd
100
10
32
64
128
256
512
1926
Reconatructed: Caterpillar eager expand in China whara faces local compatitors auch as Xonatau ltd
of inffereeceeee steps
Figure 2: Left: perplexity v.s. sampling iterations for LMIB. Right: Using trained D3PM absorbing model for LMIB to (top) generate new sentences and (bottom) reconstruct corrupted examples.
Table 2: Quantitative results on LMIB. Perplexity reported on the test set. Results are reported on two seeds. All models have context window length 128 and 12 layers unless otherwise noted. *Transformer XL. is 24 layer transformer. 'rounded for readability, see Appendix B.2.2
Metrie:
Perplexity (4)
Sample time (L)
inference stops:
1000
128
64
1000
128
64
D3PM uniform
137.9 +: 2.1
139.2 + 1.2
145.0 1 1.2
1.82
0.21
0.08
D3PM NN
149.5 + 1.3
158.6 + 2.2
160.4
1.2
21.29
6.69
5.88
D3PM absorbing
76.9 + 2.3
80.1 # 1.2
83.6 : 6.1
1,90
0.19
0.10
Transformer (ours)
43.6
0.26
Transformer XL. D
21.8
6 Image generation
We evaluate the performance of several D3PM models on the task of unconditional image generation with the dataset CIFAR-10 25 We follow Ho et al. [7 and use T'= 1000 timesteps for all models and verify that for all models the forward process converges the stationary distribution within T steps, yielding a value of at most Lr R 10-5 bits per dimension. We train three versions of D3PM with different transition matrices: doubly stochastic matrices with uniform transition probabilities (D3PM uniform) [8 transition matrices with an absorbing state located at R. G and B values of 128 (D3PM absorbing) and doubly stochastic discretized Gaussian transition matrices (D3PM Gauss). For the D3PM uniform model we experimented with a linear 33 schedule as well as the cosine schedule as proposed in [Т. with the cosine schedule producing the best results. For D3PM absorbing we use the schedule 3t (T'-t)
- + 1) as also proposed in [36]. which corresponds to increasing the probability of being in the absorbing state linearly over time. For D3PM Gauss we use the same linear schedule as in [17. See Appendix B.] for more details on the experimental setup.
Table 3 shows that for D3PM models trained with the Lvb objective, D3PM Gauss performs better than D3PM absorbing and uniform on all metrics: Inception score (IS), Frechet Inception Distance (FID) and negative log-likelihood (NLL). The IS score of the uniform and absorbing D3PM models are comparable, while the FID score and NLL of the D3PM absorbing model are slightly better. We trained both D3PM absorbing and D3PM Gauss with the alternative loss function Lxx of (5) and we found À = 0.001 to work best. We have also experimented with larger values of X and a model trained only with the auxiliary denoising term in ( Although this led
more rapid increase in performance early on in training, the NLL leveled off at higher values for larger X and the FID even started inereasing again. The results show that the models trained with LA perform significantly better than their counterparts trained with Leb. One explanation for this boost in performance is that the cross entropy term leads to gradient noise that varies less with the time step t, which is in contrast to the large change in magnitude of the L,-1 terms in Lyb for smaller f, as demonstrated by Nichol and Dhariwal [28] Finally, we achieve our best results by combining D3PM Gauss trained on Lx with truncated logistic parameterization of the reverse process distribution po (0 (a:)) (D3PM Gauss + logistic). Figure g shows samples from our best model (D3PM Gauss + logistic), as well as the D3PM absorbing model.
8

---

Table 3: Inception scores (IS), Frechet Inception Distance (FID) and negative log-likehood (NLL) the image dataset CIFAR-10. 10. The NLL is reported on the test set in bits per dimension. We report our results as averages with standard deviations, obtained by training five models with different seeds.
Model
15 (1)
FID (4)
NLL (4)
Spurse Transformer
2.80
NCSN
25.32
NCSN+2 5U
8,40
0.07
10.87
StyleGAN2 ADA
AX
9.74 0.05
3.26
Diffusion (original). Lyb
65
< 5.40
DDPM Lvb
3.70
DDPM Latmple
11
9.46 1: 0.11
3.17
S 3.75
Improved F.u.
Improved DDPM Lahmple
2.90
3.37
DDPM++ cont
2.92
2.99
NCSN= 40
9.89
2.20
uniform
2.15
D3PM absorbing Libb
6.26
41.28 - 0.65
4.83
0.02
D3PM absorbing Lx=0.001
6.78 0.08
30.97 = 0.64
1.40
0.02
D3PM Gauss Lvb
7.75
15.30 + 0.55
3.966 0.005
D3PM Gauss Lx=0
8.54 0.12
8.34 1. 0.10
3.975 0.006
logistic Lx=0 001
0.10
7.31
3.435
7
Related Work
Diffusion generative models were first proposed by Sohl-Dickstein et al. 36 and have gained renewed attention recently due to strong results on image and waveform generation 77. Recent works have proposed improvements for diffusion model training, including importance sampling of the ELBO, better noise schedules [SS) and implicit diffusion models [37]. Several works have also
drawn connections to score matching 45 9 38 continuous-time limit
leading to improved sampling algorithms in the
While most works have considered continuous diffusion models, discrete diffusion-lit models were described in 36 and applied text generation and image segmentation data in [8] Some works have dealt with discrete data by embedding it in continuous space and leveraging Gaussian diffusion, but have not applied this to text. Seff al. 35 considered generation of discrete structured objects using a diffusioo-likk Markov corruption process. Goyal et al. [15] proposed diffusion-lit model for images with a more flexible family of learned corruption processes. Ho al. also draws connections between diffusion and autoregressive models for continuous data.
29 27
For text, denoising autoencoders have a long history both in representation learning recently as generative models 47 These closely resemble our absorbing state diffusion variants for
2 10 and more
Figure 3: Left: progressive sampling at f = 1000. 900, 800, 0 for D3PM absorbing (top) and D3PM Gauss + logistic (bottom), trained with L, loss on CIFAR-10 10. These samples were cherry picked. Right: (non cherry picked) samples from the D3PM Gauss + logistic model.

---

particular schedule and transition matrix (see Section although our framing allows us to compute log ee-liikelihooss and experiment with alternative transition matrices. Other works have considered non-autoregressive translation and speech transcription via insertion and deletion [16 3 masking
13 and -teffiively-refined sequence alignments 5 34
Discussion
We have presented D3PMs, class of models that improves diffusion models for discrete data by defining new kinds of discrete corruption processes. We achieve strong empirical results relative to previous work discrete diffusion models, even surpassing performance of continuous diffusion models in terms of log-likelihoode for image generation. While these results are promising, one limitation is
much other work non-autoregressive generative models our models still inferior to strong autoregressive models like Transformer XL for text generation, and continuous diffusion models still yield stronger results on image quality. We expect that D3PMs can benefit further from the rapid development of continuous diffusion models 440
28 For example, further research in alternative losses for D3PM's can take inspiration from the reweighted Leimple objective
used in [17]. or the resampled variational bound in Nichol and Dhariwal 23 Furthermore, D3PM's
might benefit from increasing the number of timesteps and more optimized noise schedule, as discussed in Nichol and Dhariwal [28]. Another limitation comes from the choice of evaluation metrics that we use (and that are standard for evaluation of generative models). Inception score and Frechet Inception Distance are based on neural networks that have been trained on particular distribution of data, which is not representative for all use-cases, and focusing on average quality metrics may not accurately reflect performance across the wide diversity of settings where these generative models may applied. This creates a risk of negative social impacts where advances tisproportionately favor subset of the population. Text generation models, including D3PMs, also present many challenges for responsible and reliable use. Prior works have highlighted the potential for misuse [24 4 bias [46,, and hallucination 4 neural language models. D3PMs, like autoregressive language models, should be carefully evaluated along these axes before being deployed in a production setting. Going forward, we excited about the space of possibilities that arise within the D3PM framework. We have found successes leveraging the flexibility that comes from defining discrete corruption processes for discrete data, but believe that there many more possibilities that make use of richer forms of structure to define even more powerful discrete diffusion models.
Acknowledgments and Disclosure of Funding
We would like to thank Hugo Larochelle for providing high-level feedback during the project, and Ben Poole for reviewing draft version of this manuscript. We would also like to thank Julia Kreutzer and Xavier Garcia for helpful conversations about language experiments, and Daniel Watson for early discussions about discrete diffusion. We, the authors, declare to have no competing interests. The research conducted for this paper was entirely supported by Google.
10

---

References
[1] Rami Al-Rfou, Dokook Choc, Noah Constant, Mandy Guo, and Llion Jones. Character- language modeling with deeper Self-Attention. arXiv preprint 1rXiv:1888.044 August 2018.
[2] Yoshua Bengio. Li Yao, Guillaume Alain, and Pascal Vincent. Generalized denoising Auto- Encoders as generative models. arXiv preprint arXiv: 1305.666,,, May 2013.
[3] Andrew Brock, Jeff Donahue, and Karen Simonyan. Large scale GAN training for high fidelity natural image synthesis. In International Conference on Learning Representatiinss 2019.
[4] Nicholas Carlini, Florian Tramer, Eric Wallace, Matthew Jagiclski, Ariel Herbert-Voss, Kather- ine Lee, Adam Roberts, Tom Brown, Dawn Song, Ulfar Erlingsson, Alina Oprea, and Colin Raffel. Extracting training data from large language models. December 2020.
[5] William Chan, Chitwan Saharia, Geoffrey Hinton, Mohammad Norouzi, and Navdeep Jaitly. Imputer: Sequence modelling via imputation and dynamic programming. In International Conference Machine Learning, pages 1413-1413. PMLR, 2020.
[6] Ciprian Chelba, Tomas Mikolov, Mike Schuster, Qi Ge, Thorsten Brants, Phillipp Koehn, and Tony Robinson. One billion word benchmark for measuring progress in statistical language modeling. arXiv preprint arXiv: 13 /2.3005, December 2013.
[7] Nanxin Chen, Yu Zhang, Heiga Zen, Ron J Weiss, Mohammad Norouzi, and William Chan. WaveGrad: Estimating gradients for waveform generation. arXiv preprint arXiv:2009.007 September 2020.
[8] Rewon Child, Scott Gray, Alec Radford, and Ilya Sutskever. Generating long sequences with sparse transformers. arXiv preprint arXiv:1904. 1050, 2019.
(9] Zihang Dai, Zhilin Yang, Yiming Yang, Jaime Carbonell, Quoc V Le, and Ruslan Salakhutdinov. Transformer-XL XL: Attentive language models beyond Fixed-Length context. arXiv preprint 1901::09900006000 January 2019.
[10] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04805. October 2018.
[11] Laurent Dinh, Jascha Sohl-Dickstein, and Samy Bengio. Density estimation using Real NVP. arXiv preprint arXiv: (605508803) 2016.
[12] W Feller. On the theory of stochastic processes, with particular reference applications. In Proceedings of the [First] Berkeley Symposium on Mathematical Statistics and Probability. The Regents of the University of California, 1949.
[13] Marjan Ghazvininejad, Omer Levy, Yinhan Liu, and Luke Zettlemoyer. Mask-Predict: Parallel decoding of conditional masked language models. arXiv preprint arXiv: April 2019.
[14] Ian Goodfellow, Jean Pouget-Abadie, Mchdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in Neural Information Processing Systems, pages 2672-2680, 2014.
[15] Anirudh Goyal, Nan Rosemary Ke, Surya Ganguli, and Yoshua Bengio. Variational walkback: Learning transition operator as a stochastic recurrent net. November 2017.
[16] Jiatao Gu, Changhan Wang, and Jake Zhao. Levenshtein transformer. 1905: 1006, May 2019.
arXiv preprint
[17] Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. In Advances in Neural Information Processing Systems, pages 6840-6851 2020.
[18] Emiel Hoogeboom, Didrik Nielsen, Priyank Jaini, Patrick Forré, and Max Welling, Argmax flows and multinomial diffusion: Towards non-autoregressive language models, arXiv preprint 2102v2210..05379, 2021.

---

[19] Aapo Hyvärinen, Juha Karhunen, and Erkki Oja. Independent component analysis, volume 46. John Wiley & Sons, 2004.
[20] Tero Karras, Miika Aittlla, Janne Hellsten, Samuli Laine, Jaakko Lehtinen, and Timo Aila. Training generative adversarial networks with limited data. arXiv preprint arXiv:2006. 06676v1, 2020.
[21] Diederik P Kingma and Prafulla Dhariwal. Glow: Generative flow with invertible 1x1 convolu- tions. In Advances in Neural Information Processing Systems, pages 10215-10224, 2018.
[22] Diederik P Kingma and Max Welling, Auto-encoding variational Bayes, arXiv preprint arXiv:1312.614 14, 2013.
[23] Zhifeng Kong, Wei Ping, Jiaji Huang, Kexin Zhao, and Bryan Catanzaro. Diffwave: A versatile diffusion model for audio synthesis. arXiv preprint arXiv:2009. 09761, 2020.
[24] Sarah Kreps, R Miles McCain, and Miles Brundage. All the news that's 's fit to fabricate: Al- Generated text as tool of media misinformation. Journal of Experimental Political Science, pages 1-14.
[25] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[26] Matt Mahoney. Text8 dataset. http:///aataaaaooeyyeeee//d/aats 2021-5-24.
2011. Accessed:
[27] Gautam Mittal, Jesse Engel, Curtis Hawthorne, and Ian Simon. Symbolic music generation with diffusion models, arXiv preprint arXiv:2103. 16091, March 2021.
[28] Alex Nichol and Prafulla Dhariwal. Improved denoising diffusion probabilistic models. arXiv preprint
2021.
[29] Chenhao Niu, Yang Song, Jiaming Song, Shengjia Zhao, Aditya Grover, and Stefano Ermon. Permutation invariant graph generation via score-based generative modeling. arXiv preprint arXiv:2003.00638, March 2020.
[30] George Papamakarios, Eric Nalisnick, Danilo Jimenez Rezende, Shakir Mohamed, and Balaji Lakshminarayanan. Normalizing flows for probabilistic modeling and inference. arXiv preprint arXiv:1912.02762, 2019.
[31] Danilo Rezende and Shakir Mohamed. Variational inference with normalizing flows. In International Conference on Machine Learning, pages 1530-1538, 2015.
[32] Danilo Jimenez Rezende, Shakir Mohamed, and Daan Wierstra. Stochastic backpropagation and approximate inference in deep generative models. In International Conference on Machine Learning, pages 1278-1288 1286, 2014.
[33] Laura Ruis, Mitchell Stern, Julia Proskurnia, and William Chan. Insertion-deletion transformer. arXiv preprint arXiv:2001.05540. 2020.
[34] Chitwan Saharia, William Chan, Saurabh Saxena, and Mohammad Norouzi. Non-autoregressive machine translation with latent alignments. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 1098-1108 2020.
[35] Ari Seff, Wenda Zhou, Farhan Damani, Abigail Doyle, and Ryan P Adams. Discrete object generation with reversible inductive construction. arXiv preprint arXiv: 1907.0828,, July 2019.
[36] Jascha Sohl-Diccsttei, Eric Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsuper- vised learning using nonequilibrium thermodynamics. International Conference on Machine Learning, pages 2256-2265 2015.
[37] Jiaming Song, Chenlin Meng, and Stefano Ermon. Denoising diffusion implicit models. In International Conference on Learning Representations, 2021.
12

---

[38] Yang Song and Stefano Ermon. Generative modeling by estimating gradients of the data distribution. In Advances in Neural Information Processing Systems, pages 11895-11907, 2019.
[39] Yang Song and Stefano Ermon. Improved techniques for training score-based generative models. arXiv preprini arXiv:2006.0001,, 2020.
[40] Yang Song, Jascha Sohl-Dickstein, Diederik P Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-based generative modeling through stochastic differential equations. arXiv preprint 2.Xiv:2011.13456. November 2020.
[41] Dustin Tran, Keyon Vafa, Kumar Agrawal, Laurent Dinh, and Ben Poole. Discrete flows: Invertible generative models of discrete data. In Advances in Neural Information Processing Systems, volume 32, 2019.
[42] Aaron van den Oord, Sander Dieleman, Heiga Zen, Karen Simonyan, Oriol Vinyals, Alex Graves, Nal Kalchbrenner, Andrew Senior, and Koray Kavukcuoglu. WaveNet: A generative model for raw audio. arXiv preprint arXiv: 03499, 2016.
[43] Aaron van den Oord, Nal Kalchbrenner, and Koray Kavukcuoglu. Pixel recurrent neural networks. International Conference on Machine Learning, 2016.
[44] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Informa- fion Processing Systems, pages 5998-6008, 2017.
[45] Pascal Vincent. connection between score matching and denoising autoencoders. Neural Computation,
2011.
[46] Eric Wallace, Shi Feng, Nikhil Kandpal, Matt Gardner, and Sameer Singh. Universal adversarial triggers for attacking and analyzing NLP. August 2019.
[47] Alex Wang and Kyunghyun Cho. BERT has a mouth, and it must speak: BERT as a markov random field language model. arXiv preprint 100,v:1902.04094, February 2019.
[48] Chunting Zhou, Graham Neubig, Jiatao Gu, Mona Diab, Paco Guzman, Luke Zettlemoyer, and Marjan Ghazvininejad. Detecting hallucinated content in conditional neural sequence generation. November 2020.
[49] Zachary M Ziegler and Alexander M Rush. Latent normalizing flows for discrete sequences. arXiv preprint arXiv: 10548, January 2019.
13


Reviews:
[{"review_id": "Xueqr2S94B", "reviewer": "Reviewer_gjLx", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\n**Clarity**: Paper is very clearly written and easy to follow.\n\n**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.\n\n**Quality**: \n\n1. 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.\n\n2. 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.\n\n**Post rebuttal**: Authors have addressed most of my concerns.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Authors have mentioned the negative societal impact and misuse of their approach, and I see no other obvious issues.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "I3DY5zLcNk", "reviewer": "Reviewer_uXUZ", "summary": "The paper introduce a novel method for discrete state space. The main contribution is as follows:\n\n1. propose new discrete diffusion process based on Markov transition matrices Qt. \n\n2. proposed multiple transition matrices  - Uniform, Absorbing state, Discretized Gaussian, Token embedding distance\n\n3. proposed new noise schedule for the forward process based on the mutual information between x_t to x_0\n\n4. introduce new auxiliary denoising objective, which improve the prediction of x_0\n\nThe paper also discuss the connection to other probabilistic models for text - BERT, AR, MLM.\nThe paper check the performance on two domains - text and images and show significant improvement over the previous diffusion model by Hoogeboom et al.\n\n\n", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper introduce a novel method. However, i have the following concerns:\n\n1. 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)\n\n2. Missing results for the proposed method (D3PM NN) on LM1B.\n\n3. 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?\n\n4. It will be interesting to see if you can learn the matrices Qt. The idea \"Token embedding distance\" is one step toward this.  \n\n\nAlthough 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.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, the author address the limitation of their work in sec8. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10 hours"}, "extra_text": {}}, {"review_id": "F2kTMgOraKu", "reviewer": "Reviewer_u96p", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality:\n- This paper generalizes multinomial diffusion model (Hoogeboom et al. 2021) and makes several nontrivial technical contributions to improve the model performance. \n- 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. \n- 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.\n\nQuality:\n- The submission is technically sound.\n\nClarity:\n- The paper is well written. The authors tried to elaborate the ideas in main text and left the technical details in appendix. \n\nSignificance:\n- The empirical result in text domain is compelling among other non-autoregressive models. But it is still far away from autoregressive models. \n- 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.\n\nDetailed comment:\n\n1, “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”\nCould 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?\n\n2, 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.  \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "7s6IOyZYR3S", "reviewer": "Reviewer_vMWp", "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.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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).\n\n__Clarity:__ The paper is well written and easy to read.\n\n__Specific Questions and Feedback:__\n\n1. 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.\n2. 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?\n3. 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?\n4. 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.\n5. 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?\n6. The connection between autoregressive models and diffusion models has been discussed before ([1], section 4.3). It would be appropriate to acknowledge that.\n\n__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.\n\n\n[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\"", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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.\n\n__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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

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)