A Reparameterized Discrete Diffusion Model for Text Generation
Authors: Lin Zheng
Jianbo Yuan
Lei Yu
Lingpeng Kong
Venue: COLM (2024)
Keywords: discrete diffusion, text generation, non-autoregressive generation
TL;DR: This work develops a reparameterized discrete diffusion model that implies effective training and sampling algorithms and delivers significant performance improvements for text generation..

Abstract: This work studies discrete diffusion probabilistic models with applications to natural language generation. We derive an alternative yet equivalent formulation of the sampling from discrete diffusion processes and leverage this insight to develop a family of reparameterized discrete diffusion models. The derived generic framework is highly flexible, offers a fresh perspective of the generation process in discrete diffusion models, and features more effective training and decoding techniques. We conduct extensive experiments to evaluate the text generation capability of our model, demonstrating significant improvements over existing diffusion models.

Published as a conference paper at COLM 2024
A Reparameterized Discrete Diffusion Model for Text Gener- ation
Lin Zheng' Jianbo Yuan² Lei Yu² BByteDance Inc.
Lingpeng Kong'
The University of Hong Kong 1zheng20cs. hku. hk
'Google DeepMind
Abstract
This work studies discrete diffusion probabilistic models with applications natural language generation. We derive an alternative yet equivalent formulation of the sampling from discrete diffusion processes and leverage this insight develop a family of reparameterized discrete diffusion models.
The derived generic framework is highly flexible, offers a fresh perspec- tive of the generation process discrete diffusion models, and features more effective training and decoding techniques. We conduct extensive experiments to evaluate the text generation capability our model, demon- strating significant improvements over existing diffusion models.
1 Introduction
Diffusion-basse generative models (Sohl-Dickstein et al., 2015; Ho et al., 2020; Song et al., 2021b), or diffusion models for short, have achieved remarkable progress and shown great success in generating high-quality and photo-realistic images (Ramesh et al., 2022; Saharia et al., 2022; Rombach et al., 2022; Balaji et al., 2022; Peebles & Xie, 2022). Researchers have successfully extended diffusion models to various data modalities beyond 2D images, including audio (Kong et al., 2021), video (Ho et al., 2022), as well molécule generation (Hoogeboom et al., 2022b; Jo et al., 2022). There has also been a surge of interest in extending diffusion models natural languages (Hoogeboom et al., 2021; Austin al., 2021; Li al., 2022b; Dieleman et al., 2022). Diffusion-based language models are appealing in that the generation process is typically conducted in a non-autoregressive manner, which features in-parallel decoding by design and potentially faster runtime (Hoogeboom et al., 2021; Austin al., 2021). In addition, due to the iterative reconstruction process in diffusion- based models, it is often possible to refine the previously generated texts (Savinov et al., 2022). As a result, compared with the conventional auto-regressive models, diffusion-basse language models are more flexible and attain better trade-offs between generation quality and efficiency.
However, there are noticeably fewer success cases in employing diffusion models for large- scale text generation tasks. This is possibly due to the discrete nature of natural languages, while most conventional diffusion models focus continuous-values contents. To bridge the discrepancy, a recent line of work suggests conducting continuous diffusion processes over token embeddings (Li et al., 2022b; Gong et al., 2022; Strudel et al., 2022; Dieleman et al., 2022) or logits (Han et al., 2022; Richemond et al., 2022). Nevertheless, these approaches often require designing a well-crafted rounding scheme to convert the diffused continuous vectors to the actual discrete tokens. In addition, existing continuous diffusion models often require a large number of sampling iterations to achieve the desired performance. This issue is exacerbated in the case of modeling texts, as the diffusing steps over text embeddings are hard to be translated to significant movements of token states due to the rounding quantization. This results in a considerably slower runtime than auto-regressive models. For example, a recent continuous text diffusion model (DiffuSeq; Gong et al., 2022) runs several orders of magnitude slower than the autorregressive baseline of a similar scale, as shown in Figure 2b. Different from the above, another research direction focuses on diffusion processes that directly operate discrete state spaces (Sohl-Dickstein et al.,

---

Published as a conference paper at COLM 2024
2015; Hoogeboom et al., 2021; Austin et al., 2021, see $2). However, they relatively under-explored and often achieve inferior results in text generation.
In this work, we demonstrate that discrete diffusion models can serve as strong baselines for text generation. By re-examining the formulation, observe that sam- pling from discrete diffusion models admits a novel yet equivalent reparameterization (S3). Specifically, starting with a completely noisy sequence, the sampling pro- cedure in discrete diffusion model is equivalent the following ronte-and-denoise process where at each iteration, each token within the sequence either de- noised or reset to noisy states according to an under- lying stochastic routing mechanism (S3.2). The router assigns the same probability to the decision for each token, processing the sequence a uniform manner. Based on this insight, propose Reparameterized Discrete diffusion Models (RDMs; Figure 1), a new fam- ily of models that respects the reparameterization and formulates the routing process explicitly. RDMs enjoy
XO
X1
X2
X3
Conventional discrete diffusion.
X0
(b) Reparameterized discrete diffusion.
Figure 1: Graphical models of
backward diffusion processes.
appealing properties for both training ($4.2) and sampling ($4.3); (1) Simplified training. We demonstrate that the training objective for RDMs can be reduced to a re-weighted standard cross-entropy loss. Furthermore, the loss objective is invariant to different routing probabilities up to reweighting, indicating that the large family of RDMs with distinct routing processes can be trained with the same surrogate objective; (2) Flexible sampling. The shared training objective makes sampling highly flexible and allows more expressive routing processes. In particular, we develop an adaptive routing strategy that routes tokens to the denoised state only if the router outputs high scores instead of uniformly process- ing all the tokens, Equipped with such training and decoding schemes, we demonstrate that RDMs significantly improve vanilla discrete diffusion models across several standard text generation benchmarks (55). They also achieve much better performance than the continuous diffusion models while running several orders faster.
Our contributions can be summarized as follows:
We analyze existing discrete diffusion probabilistic models and derive a more compact formulation that generalizes various diffusion processes and reveals an internal routing mechanism for selectively denoising tokens;
We introduce reparameterized diffusion models (RDMs), a new model family that param- eterizes both routing and denoising processes. RDMs yield greatly simplified training objective and enable more flexible decoding algorithms for text generation;
We provide extensive results and analyses across several benchmarks to demonstrate the improved text generation quality of RDMs.
2 Background
Let x Pdata (Xo) denote a discrete random variable with K possible outcomes. To ease notation, we represent discrete variables as one-hot vectors in (0, 1), which is 0 everywhere except that the entry corresponding to the current state is 1. Discrete diffusion probabilistic models (Sohl-Dickstein et al., 2015; Hoogeboom et al., 2021; Austin et al., 2021) are usually defined as a class of latent variable models characterized by forward and backward pro- cess. The forward process gradually transforms input data to some noise distribution Inoise through T intermediate latent variables ,T, E {0, 1] with the forward transition (x; (x-)) = B,x,-1 + (1 B:oisse In this case, the distribution (xx12x) is available in closed form,
xxx1/x0) = 8:x1-1 + &' Jnoiser
(1)
where a; := IT B, is specified to decrease from to w.r.t t. Inoise characterizes different diffusion processes; for example, multinomial diffusion (Hoogeboom et al., 2021) adopts
2

---

Published as a conference paper at COLM 2024
uniform noise distribution over the vocabulary (1,2,...,KK) alternatively, absorbing diffusion specifies 9noise to be a point mass with all of the probability on an absorbing state (Austin et al., 2021).
The backward process (x; 1|2;) ) is the key ingredient for diffusion-based generative mod- eling, based which we can start with unstructured noise XT 9noise and perform ancestral sampling x ~ (xx--1xx)) to obtain new draws from Pdata Unfortu- nately, the backward transition (xx)-1[xx) is mostly intractable due to the marginaliza- tion over the entire data distribution. Therefore, we resort to approximating it with a parameterized distribution pa (1Xx-11xx;) at each step This results in a generative model pe (1, xI, = pa xx) [ Pe (x--11xx)) which can be trained by maximizing the evi- dence lower bound (ELBO) of log (xo)),
T log po(x)) (i( (.(0) + const.,
1=2
with (.) (g(x)(x)) (x) || (0(x)-1|xx))) For the case f = 1, we have (0) Eq(x; xo) Po x1 )]. The ELBO decomposes into sum of KL divergences between the conditional backward transition ((x4-1|21,xx)) and po(x;-1(x;) at each time step Note that (x,-1|x;,x0) & (x) can be calculated analytically for most discrete diffusion models. To define the distribution ( previous work (Hooge- boom al., 2021) suggests that it can be parameterized similarly qxx xx, xx) by letting po(x = -1x11111100 x fxx;; 0)), where neural network f(x;; 0) is adopted to predict Xo- Typically fxx;; 0) E (0, (0, is the model output normalized by a softmax function, representing the probability vector for each token. For text generation, each discrete text token within an input sequence is often assumed to be diffused independently. Thus to avoid cluttering the discussion, we focus initially on the diffusion process of a single token and address the entire sequence later in $4.2 and $4.3. A more detailed discussion about the related work and derivations about discrete diffusion models are provided in Appendices A and B, respectively.
3 Reparameterizing the Backward Processes
This section presents an in-depth study of discrete diffusion probabilistic models. We derive an alternative formulation for the backward process ($3.1) and devise reparameterized sampling scheme ($3.2), which paves the way for a more generic family of discrete diffusion models (54).
3.1 An Alternative Backward Formulation
We first elaborate how the conditional backward transition of existing discrete diffusion models can be written in a more compact formulation (see Appendix C for the proof).
Proposition 3.1. Let the forward transition of discrete diffusion be ((xe (x-1)) Bix, + (1 Bi)gnoise- Then the conditional backward transition (xx; 1 1|x,, xo) can be equioalently written
(1) x
(1-1()
Inoiser
if x X
9(2, 1001112),000
(2)
x + (1-1, 1 Inoise (x:),
(2)
if x * Xo-
Here 9noise (x,) Bixt + (1 gnoise denotes a noise distribution that interpolates between xt and 9naise (111) 1 (1- as Mnnnico (m= (u=xi) and x(2)
81 1- where 9noise (u xx) is
+1 (1- a; Anoise x:)
- at
the probability of the noise equal to Xi.
Intuitively, Equation reveals that the main mechanism of the backward process is to shuttle discrete tokens between fully noisy states and the ground truth state xn, conditioned the equality of x, and xp. If x; = xo, the current token state is possibly noise-free, and the model either remains noise-free by copying the state x, f- Xi, or resets the state to the
3

---

Published as a conference paper at COLM 2024
noise. x; xo, the current state is considered noisy, and the model opts denoise to xo or remains noisy otherwise. The probability of moving noisy tokens to ground truth states or turning denoised tokens back noise is governed by X x and 1 - - respectively.
3.2 Reparameterized Sampling
Next, we demonstrate that sampling from the backward transition can be conducted via an augmented path, leading to our full reparameterization. We make use of the simple fact that the mixture distribution Equation 2 can be sampled in two steps: first, randomly select component according to their weight, and then sample from the corresponding component distribution. Concisely, we have
b, = 1 -
0 Bernoulli
(1)
1 "
(1)
(1)
4noise
0 Bernoulli
(2)
(1 (2)
/--1),
u,
(2)
9noise (21)
- x o111)
u1
(1)]
+ + (1- bb))
(2)
x0 (1-
o/2) u, u!21
To simplify the notation, we denote 0;-1 0 1--100111
(2) and A,-1 [
(1) _ (2) This
reparameterized backward transition highlights underlying routing mechanism, where the model routes tokens to different distributions according to 0, given b, that discrimi-
nates which tokens are currently noisy, o/21 selects and denoises noisy tokens to recover the
ground truth xo, while o determines which denoised tokens revert to the noisy state.
4 Reparameterized Discrete Diffusion Models
In this section, we introduce our proposed diffusion models that reflect the reparameteriza- tion (64.1), which imply effective training (54.2) and sampling (54.3) algorithms.
4.1 Joint Diffusion Modeling
The routing mechanism in $3.2 works in a latent manner; that is, it is only active during the sampling process but marginalized when advancing the distribution of x;-1- To fully utilize the potential of the developed reparameterization, we propose to elevate the latent routing mechanism to the formulation explicitly and model the joint q( 1,, Pj- xx) =
(0):11)9(x1) 11-11116 Xt, Xo), where
q(o; 1) = Bernoulli (A, 1)
(1 - [21
(1)
0 +
Inoiser
if by = 1
q(x xn)
(4)
x
+
1 0 Anoise(x:))
by = 0.
Note that b, 1x;=x-- This can be considered standard discrete diffusion model augmented with step-wise routing indicators {v/-1)7 (see Figure 1). It closely relates to the conventional formulation (Equation 2) in that the original backward process amounts to marginalizing out D; at each time step: q(x; 1| xp) Ey((,,,) [9(x, D 1, x, xp)]. Since the distribution over 2,-1 is explicitly considered, this joint diffusion model offers improved flexibility and expressiveness. We refer to this class of models reparameterized discrete diffusion models (RDMs), as it yields an equivalent sampling process to the original formulation but via reparameterized path.
4

---

Published as a conference paper at COLM 2024
4.2 Training
Similar to previous diffusion models ($2), we define a joint generative process 10---10-1117, and optimize the ELBO via the following factorization,
1x0)( 2 (xx log Pe(x0.X1.7,
(i Σ ()) const. 1=2
g(x1,T, U1. xx)
Following standard practices in diffusion models (Hoogeboom al., 2021; Austin et al., 2021), we randomly sample time step and optimize 0 with respect to (;))). In our case, (0) = B xx) [log (xxx]xx]]] for > 1, L; decomposes into sum of two expected KL divergences over v, and x4 respectively (see Appendix D for the full derivation),
(0) E (g Po(o; 1)) + (qx 1/0, x,, po(x; 1/0; 1, xxx))) (5)
where the expectations are with respect to (xx;(x0) and (xx//))))(()))))))))))))))) (0))())))) respectively.
Parameterization. The decomposition in Equation suggests parameterizing each conditional of Po- xx) ( simplify the model representation, we constrain po(v(-1(x;)
Algorithm Training RDMs
Input: neural network f (), data distribution Pdata (No.1 J, and custom reweighting scalar 41-1- Output: model parameters repeat
be the same as (v)-1) that the first KL term vanishes. In terms of ((- it needs to approximate qxx; 1 17-1,80 X0) for both xo and b, = 1,,=x0- For the former, we approximate xo with a neural network output f(x;; 0) ($2); for the latter, it is circumvented via feacher-forcing approach. We leverage the fact that b, = xx is readily available during training and plug the oracle into pa(x; 1/0, x2),,, which works well empirically and yields interesting implications as presented below.
Draw X0.1: Fdata (xo.:N))):: Draw I É Uniform( (aniform((1,....... TT:
for n 1,2,..., do
Draw Xt,n ~ ((
Let bı = 1x,.-
end for (()) -- 1 b Minimize (()) with respect until converged
(Xtai 0);
Simplified Training Objectives. The discussion so far focuses on the diffusion process over single token. We now slightly abuse the term and denote the sequence of tokens at step f as X1,1NN = {- } where the joint distribution factorizes over each token, Xt,n is the nith token with being the sequence length. 1 We show that the training objective (0) for sequence X1,1:N at the f-th step can be reduced to surprisingly simple expression (see Appendix for the proof and its connection to previous works) as follows,
N
(0) E Patta (No,1)) ITY ( [Aqu)
Σ #=1
(1 btn Nx log (xe,i 0)
(6)
Based on this result, training RDMs is equivalent to optimizing the standard multi-class cross- entropy loss function, which is evaluated over noisy tokens and weighted by x E أ
This formulation is conceptually simpler than that of the original discrete diffusion, which requires evaluating the KL divergence between two complicated categoricals (Hoogeboom et al., 2021). Besides, this formulation establishes the discrete analog of reweighting training strategies, which are recognized as common practices for training continuous-domall dif- fusion models (Ho et al., 2020; Nichol & Dhariwal, 2021; Vahdat et al., 2021; Karras et al.,
2022). In particular, we can adjust the weight A (2) that it is more amenable for training.
,-1 to reweigh the cross-entropy function so
More importantly, we note that the training loss function can be invariant with respect to q 1) up to reweighting, where different q v; 1) lead to the same shared objective except
We sometimes use and xta interchangeably to represent single token when there is no ambiguity.

---

Published as a conference paper at COLM 2024
for the weight x This makes possible to train the neural network with one amenable distribution of v;-1 but share the trained model for sampling among a broad family of diffusion processes indexed by ((%-1))
4.3 Sampling
Decoding text from discrete diffusion processes usually starts with a sequence comprising only noisy tokens and proceeds by sampling (partially) denoised sequence x; 1,1,1:N from the previous step X1,1:N for each f.
Recursive Computation for by The key challenge in decoding is to compute b;,, 1x. X0x in Equation 4, which is intractable since we lack access to the ground truth N0,a as in training. We circumvent this issue by leveraging a recursive computation based on the functionality of V1-1n- Starting with bI, 0, we compute 1, as
b (btn
(1) V-LLn)
(2)
11-1n"
Intuitively, bI,IIN represents frontier set that stores the denoised tokens up to the previous
iteration. At the current iteration, we add new tokens to the set if (2) L, = 1 and remove
elements from the set if the corresponding of 1,n O. The updated set then read out to form 1, Note that the update does not add extra computational costs. Equipped with these results, we can efficiently execute the sampling algorithm without difficulties.
Generating 2 1- As shown in Equation 4, a naive approach of generating D;- is by drawing 0,-1n Bernoulli (A,-1) for each token n. However, this assigns equal rout- ing probability A to all tokens, which may be sub-optimal for routing different to- kens to distinct states. This observation mo- tivates us to employ a more discriminative routing mechanism, where only tokens with high confidence from neural networks are denoised (Ghazvininejad et al., 2019; Savi- nov et al., 2022; Chang et al., 2022). At each (1) step, assume 11,,, and v1-1,a are set to and 0 by default, respectively. We feed the noisy sequence XtN:N into the neural net- work and collect the output f(x,, 0) for each token n. After that, We obtain token scores St, by taking the maximum value of fx 0) E (0, 1)* which reflects the model confidence. 1,m is then set to 1 only when 8tn is among the largest scores. Formally,
Algorithm Sampling from RDMs
Input trained network f (v:0) and temperature r. Output: generated sample Xp-
for f = 1,2, N do Initialize N7,5 ~ qnoisei Initialize bT = 0; end for for t = T,...,, do do 1,2...., do
for n
Draw Kū Categorical (f(z) /T); Generate 11 according Equation 8; if ر1 1 then
Draw " 9noise/
(1) 11 E Jnn + (1- uigi
else
Draw v/.)) Gnoise (Xtn);
1t- = 1/ 1 Jon + (1 (1- (2)
-0 lu)
(2)
end
Let b/ = bLa A V V
end for end for Return X0.1.N-
SI,u max (I),ii))
IN Pt- arg tt.
o 1,x
(1)
1 ImEP,
(8)
1S/SK
1SHEN
where = i by and i = 2 otherwise. This strategy is more informative, as the router can compare token scores to determine their states. Note that v is now defined as function of model scores and its explicit probability distribution is possibly different from the one used training; however, thanks to $4.2, the diffusion model corresponding to this routing distribution can also be trained effectively with the shared surrogate objective, justifying the usage of the adaptive strategy.
lechhically, for certain noise distributions Jnoiser these logic operations A and V should also be noisy since they should compensate for the possibility that noises drawn from Anoise can also coincide with xp; however, for most diffusion processes considered in this work, such probability is either zero or small that it be safely ignored.
6

---

Published as a conference paper at COLM 2024
4.4 Implementation
Algorithms and 2 list the full pseudo-codes for training and sampling of RDMs, respec- tively. Note that the loop over the sequence length N is computed in parallel. The developed formulation of RDMs offers great flexibility for both training and sampling. For instance, we can pass a custom A,-1 to reweigh the loss for training, similar to continuous diffusion models. Besides, the denoised token states & during decoding can be obtained in vari- ous ways, such as sampling with annealed temperatures or simply taking the arg max of f (x),i 0). Please refer to Appendix F for the full implementation details.
Experiments
We evaluate our model on various text generation benchmarks, including machine transla- tion (55.1), open-ended text generation (Appendix H.3), question generation, and paraphras- ing ($5.2). Our implementation is based on FairSeq toolkit (Ott et al., 2019); more detailed experimental setup and analyses can be found Appendices and H, respectively.
5.1 Machine Translation
Setup. We conducted machine translation experiments on three standard benchmarks: IWSLT14 DE-EN (Cettolo et al., 2014), WMT1 EN-DE (Bojar et al., 2014), and WMT16 6 EN-RO (Bojar et al., 2016), consisting of around 160K 4.0M/3K /3K,, and /1OK/2K/22 train- ing/ vnggvvaiiationn teentinttttn sentence pairs, respectively. We operate on original data for all translation tasks and do not adopt knowledge distillation (Kim & Rush, 2016; Gu et al., 2018) that replaces the target side of training data with outputs generated by a pre-trained autoregressive Transformer.
Results. As seen from Table 1, existing discrete diffusion models usually perform badly on the translation task and do not scale well for large-sized datasets. In particular, multi- nomial diffusion achieves worse translation quality albeit with more iterations and fails to decode decently on WMT14 EN-DE dataset. The proposed reparameterization yields significant performance boosts (about 3-20 BLEU improvements) on both absorbing and multinomial diffusion across all datasets and iteration steps. We also observe that the performance gain much more significant for multinomial diffusion, which possibly due to the fix of its degenerated behavior (more details are in $5.4). Our approach effectively scales diffu- sion models to larger datasets, outperforming previous non-autoregressive baselines CMLM (Ghazvininejad et al., 2019), and achieves promising results even competitive with autore- gressive baselines. Besides, RDMs perform significantly better than continuous diffusion models CDCD (Dieleman et al., 2022) while running with more than 8x fewer iterations.
5.2 Question Generation and Paraphrasing
Setup. We also evaluate the performance of our model on general sequence-to-sequeee generation tasks, following Gong et al. (2022). Due to the limited computation budget, the tasks we focus on are 1) question generation (QG) using the Quasar-T dataset (Dhin- gra et al., 2017) with approximately 117K /2K/OK pairs for training/ beiniigg/validan /aalidaaiooon///// siiddatioo/testinn testing, and 2) paraphrasing with Quora Question Pairs (QQP) containing around 145K/2K/2..5 training/ validation/ testing question pairs.
Results. We report comparisons among discrete diffusion, continuous diffusion, and ruto-regressive baselines in Table 3. We observe that either variant of RDMs not only improves their vanilla counterparts by a large margin but also outperforms the strong continuous diffusion baseline DiffuSeq well as various auto-regressive baselines across several evaluation metrics. Besides, DiffuSeq needs 2000 steps to finish the decoding, while RDMs can produce higher-quality samples with 10 iterations, reducing runtime by over x.0 This implies that RDMs can attain a much better trade-off between generation quality and runtime. In addition, also investigate the effect of candidate sample size in Table 8.
7

---

Published as a conference paper at COLM 2024
Model
Iterations
Vanilla
INSLT14 DE-EN Reparam.
Vanilla
WMT16
Reparam,
Vanilla
WHT1 EN-DE
Reparam.
Continuous Diffusion
CDCD (Dieleman al,,
2000
20.0"
23.05
28.01
26.61
30.16
4.28
21.43
Multinomial Diffusion Hoogehoom et 2021)
21.26
24.24
32.23
30.57
25.25
27.81
33.00
31.70
4.31
6.94
25.63
24.05
20.59
32.98
24.36
33.11
Discrete Diffusion
25
20.06
32.84
23.94
33.31
3.69
26.04
25.24
27
27.24
30.72
16.46
21.00
Absorbing Diffusion
(Austin al,, 2021)
10
16
28.36
28.32
34.41
33.91
30.79
30.41
33.82
33.38
22.07
21.62
27.58
26.96
CMLM (Ghazvininejad al., 2019)
16
32.18
32,90
25.00
CMLM-SMART (Ghazvininejad al., 2020)
10
30.74'
32.71
25.10'
Non-aut Non-auuooregeessvve Models
Levenshtein Trensformer (tucetal, al, 2019)
Adaptive
25.20'
(Kasai et al., 2020)
DisCo
Adaptive
25.64
(Huang al, 2022)
CMLMC
34.28'
34.14
26.40'
Transformer-base (Vaswani et al., 2017)
Autoregressive Models
n.a
34.51
34.16
27.53
Table 1: BLEU score comparisons on IWSLT14 DE-EN, WMT14 EN-DE, and WMT16 EN-RO bench- marks. denotess results reported from previous work.
We notice that DiffuSeq benefits more from large sample sets (e.g., when the sample size increases from 1 to 10) than RDMs. We attribute this to the possibility that adding Gaussian noise to token embeddings in DiffuSeq might lead to more diverse samples. This helps make better of the MBR decoding, indicating that there might be room to improve RDMs to leverage multiple decodes. Nevertheless, RDMs still achieve better performance than DiffuSeq across both cases of single and multiple samples.
5.3 Analysis
On the Effect of Training and Decoding Strategies. This section explores the im- pact of improved training and decoding techniques developed for RDMs. Concern- ing the training aspect, compare the de- rived loss objective, which takes the form of reweighting cross-entropy function ($4.2), with that of traditional discrete diffusion models. As for decoding, we evaluate the effectiveness of the discriminative routing mechanism (54.3) against the vanilla strat- egy that randomly denoises tokens. The overall comparison is presented in Figure (as well as Figures 3a and 3b in Appendix H.4). The results indicate that adopting either the improved training decoding scheme leads to a significant performance boost over vanilla baselines, which can be further amplified by integrating both. In particular, we discover that the inferior performance of vanilla multino- mial diffusion stems from both inadequate training and ineffective decoding. Improving either the training or decoding process results in gains of over 10-20 BLEU points, allowing the model to scale well for more decoding steps. Besides, we also ablate the design choice of reweighting strategies (S4.2) in Table 2, and observe that linear heuristic proposed in (Bond-Taylee et al., 2022) yields large improvements in performance on IWSLT14 DE-EN. Therefore, this reweighting scheme is adopted by default unless specified otherwise.
Reweighting training scheme
Vanilla
Improved
Original (2/3) 4
28.32
30.64
Linear (A =1 -1
31.04
33.91
Constant (1 =1
29.75
32.57
Table 2: BLEU scores on IWSLT14 DE-EN with different reweighting schemes, evaluated un- der RDM-absorbing with 10 vanilla/improoed decoding steps.
On Decoding Speed. This section visualizes the performance-runting comparison among different text generation models. All models considered here have roughly the same
8

---

Published as a conference paper at COLM 2024
Absorbing Diffusion
Diffuston
15
Vanila
Inorowed Training
Inproved Decoding
litrades
Inarowed Traiiing & ng
10
Iteration
10
lteration
15
20
25
Spoed (santiaices aec)
(b)
Figure 2: Left: ablation study of improved training and decoding strategies on WMT14 EN-DE test set for absorbing and multinomial diffusion, respectively. Right: The quality-specd comparison among different models for QQP dataset. The number annotation indicates the iteration sleps except for GPT2-base and Transformer-base, which generate rugo-regressively and do not have fixed number of iterations. The horizontal axis is in log scale.
parameter counts (90-110M), and the speed is measured under the setting of 32 batch size on one NVIDIA GeForce RTX 3090 GPU, averaged by 30 runs. As shown in Figure 2b, there is clear trend that RDMs usually baseline GPT2 (Radford et al., 2019) or Transformer (Vaswani et al., 2017), while to achieve similar performance, continuous diffusion models are several orders of magnitude slower than these baselines. Furthermore, discrete diffusion models here are trained with 50 time steps in total but are able achieve satisfactory quality even with or 5 steps. In contrast, the continuous diffusion model DiffuSeq, trained with 2000 time steps, mostly generates non-meaningful sentences (BLEU scores getting close to zero) under down-sampled time steps, even equipped with advanced samplers like DDIM (Song et al., 2021a). This reveals the inherent difference between discrete and continuous diffusion, where discrete diffusion generalizes much better to various setups of iteration steps.
up to 10x faster than similar-sized auto-regressive
5.4 Examples
This section illustrates the samples generated by RDMs. We focus on the case of multinomi- nal diffusion and its reparameterized variant; a more comprehensive analysis can be found in Appendix H.5.
Multinomial Diffusion Does Not Decode Iteratively. As seen Table 4, we observe that across all text generation tasks, vanilla multinomial diffusion only generates the hypothesis at the first iteration and gets stuck in the same state thereafter. This means multinomial dif- fusion decodes in one shot and does not leverage the iterative process for further refinement. In Appendix H.5, we show that this abnormal behavior is primarily due its degenerated backward formulation, which can be neatly fixed by our reparameterization. The resulting behavior is much more expected and leads to better generation quality.
The Slow Convergence of Continuous Diffusion. We also demonstrate the down- sampled dynamics during the generation of DiffuSeq. In contrast to discrete diffusion models, where relevant tokens emerge within only a few steps, continuous diffusion hardly decodes meaningful tokens until the 1000-th iteration or later. This validates our hypothesis that the Gaussian diffusion over token embeddings is noisy and slow by design; further- more, many diffusing steps are required to emit a significant change over token states due to the rounding quantization (see Table 12 for an illustration).
Conclusion
This work presents an extensive analysis of discrete diffusion models. Based on the devel- oped understanding, we propose family of reparameterized discrete diffusion models (RDMs)

---

Published as a conference paper at COLM 2024
Tork
Model
BLBU
ROUGE-L
SERTScow
Dist-1
Source: how can one increnoe comontrration?
Trensformebbnn
0:1663
0.3441
01337
05049
Reference: how can improve conuntrattion?
GFT2 base FT"
0,741
02714
# Iber.
Decodes
GPTDdaagg
0.110
0.3215
0.36
skopptical coll #haam gasl erika calves wharf [unused991]
NAR-LavT
GPVAE-13
0.1251
0.3390
05581
1000
500
sihhrma 730 improeer berminuls
cesente
rewark 7 vensouelan repertationn 285 siwjjan??
DiffuSee"
01721
0.3665
06123
0.0066
1594)
howr do smpprooi concentration
Absoabing
6.1288
0.3505
06312
05095
2000
how do improve concestration
RDMahhorhing
0:121
0.3565
0639
0.200
ently clistances outimee iiterr khmer curvature question fidd
RD RDMemoltinmmial
Multtromial
0.1695
0.3802
0.3129
0.3550
06188
06310
09082
0,999
how imperve Jocus consentration
Jurn can improve focu- comantrativo
Transkemeshhne
GPT2-base FT"
0.1980
0.5212
08381
09716
howr improve
impeove
focus concentration:
0.3886
096888
Aidoown intersity cortes MMden udo oldies
0PP
Uiffubieq
NAB-laoT"
024113
0.5755
0.9880
0336
018077
0,7500
how trait abicaal my concentration devb
how traik incroase my consentration: ?
worker bounted /Wiaa caledoeia concentration Abvb
Absoebing
how trait increase my concentrationn
0.2510
how do inacnose my consontrationn
Multinomial
0:2000
0.3339
0,788
05375
RDMemushineeraal
0.2498
0.5885
0.8466
0.9617
Table 4: Qualitative samples of test para- phrases generated from different diffusion models on QQP dataset. & texts are truncated fit into the table. Words are in lower case.
Table 3: Comparisons among different text generators on QG and QQP. numbers are taken from Gong et al. (2022). All discrete diffusion models are run with 10 steps.
that significantly improve previous work in both training and decoding. We evaluate the proposed model family in various text generation benchmarks and demonstrate the boosted generation quality.
RDMs define a general framework for discrete diffusion processes and can be extended in several ways. For instance, RDMs are currently confined to generating fixed-length sentences and rely on an explicit length prediction module to propose the sequence length. It would be interesting to extend the model to enable variable-length sequence generation. Besides, our proposed adaptive routing mechanism (64.3) makes the initial attempt to unleash the expressiveness of RDMs; the shared training objective ($4.2) allows more advanced search methods to be incorporated into the sampling process for better generation quality. A further investigation into this direction is left future work.
Acknowledgements
We would like to thank the HKU NLP group, the Shark NLP group, and the anonymous reviewers for their valuable suggestions that greatly helped improve this work. We also thank Runhao Shi and Zijing Ou for the initial discussion This work is partially supported by the joint research scheme of the National Natural Science Foundation of China (NSFC) and the Research Grants Council (RGC) under grant number N_HKU714/21.
an earlier draft of this work.
References
Jacob Austin, Daniel D. Johnson, Jonathan Ho, Daniel Tarlow, and Rianne van den Berg. Structured denoising diffusion models in discrete state-spaces. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021. URL https: http///peneeiie.eeeeeerrrrrr//// net//forumiidtt--xxxo..
Yogesh Balaji, Seungjun Nah, Xun Huang, Arash Vahdat, Jiaming Song, Karsten Kreis, Miika Áittala, Timo Aila, Samuli Laine, Bryan Catanzaro, et al. ediffi: Text-to-image diffusion models with an ensemble of expert denoisers. arviv preprint arXiv:2211.013224 2022.
Ondfej Bojar, Christian Buck, Christian Federmann, Barry Haddow, Philipp Koehn, Johannes Leveling, Christof Monz, Pavel Pecina, Matt Post, Herve Saint-Amand, Radu Soricut, Lucia Specia, and Ales Tamchyna. Findings of the 2014 workshop on statistical machine translation. In Proceedings of the Ninth Workshop on Statistical Machine Translation, Pp. 12-58, Baltimore, Maryland, USA, June 2014. Association for Computational Linguistics. doi: 2..1115/v1/W14-300 URL https://aclannt http:://aclantthllgg... org/ 4- 3302.
10

---

Published as a conference paper at COLM 2024
Ondřej Bojar, Rajen Chatterjee, Christian Federmann, Yvette Graham, Barry Haddow, Matthias Huck, Antonio Jimeno Yepes, Philipp Koehn, Varvara Logacheva, Christof Monz, Matteo Negri, Aurélie Névéol, Mariana Neves, Martin Popel, Matt Post, Raphael Rubino, Carolina Scarton, Lucia Specia, Marco Turchi, Karin Verspoor, and Marcos Zampieri. Findings of the 2016 conference on machine translation. In Proceedings of the First Confer- ence on Machine Translation: Volume 2, Shared Task Papers, Pp. 131-198, Berlin, Germany, August 2016. Association for Computational Linguistics. doi: 10.18653 11186533/11W1662300 URL
org/W16 2301.
Sam Bond-Taylor Peter Hessey, Hiroshi Sasaki, Toby P Breckon, and Chris G Willcocks. Unleashing transformers: parallel token prediction with discrete absorbing diffusion for fast high-resolution image generation from vector- pector-quantizd codes. In European Conference on Computer Vision, pp. 170-188. Springer, 2022.
Andrew Campbell, Joe Benton, Valentin De Bortoli, Tom Rainforth, George Deligiannidis, and Arnaud Doucet. A continuous time framework for discrete denoising models. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022. URL DmT862YAieY.
Hanqun Cao, Cheng Tan, Zhangyang Gao, Guangyong Chen, Pheng-Ann Heng, and Stan Z Li. A survey on generative diffusion model. ar arv preprint ar 0ttt::22099026444 2022.
Mauro Cettolo, Jan Nichues, Sebastian Stüker, Luisa Bentivogli, and Marcello Federico. Report on the 11th IWSLT evaluation campaign. In Proceedings of the 11th International Workshop on Spoken Language Translation: Evaluation Campaign, pp. 2-17, Lake Tahoe, California, December 4-5 2014. URL 1.
hww.e/annntoloooooo/2222041 iwslt-evaluation.
Huiwen Chang, Han Zhang, Lu Jiang, Ce Liu, and William T Freeman. Maskgit: Masked generative image transformer. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 11315-11325, 2022.
Huiwen Chang, Han Zhang, Jarred Barber, AJ Maschinot, Jose Lezama, Lu Jiang, Ming- Hsuan Yang, Kevin Murphy, William T Freeman, Michael Rubinstein, et al. Muse: Text-to- image generation via masked generative transformers. arXio preprint ar XrXiv:2301.0074, 2023.
Ting Chen, Ruixiang Zhang, and Geoffrey Hinton. Analog bits: Generating discrete data using diffusion models with self-conditioning arXiv preprint SKKt::2208.02202 2022.
Florinel-Alin Croitoru, Vlad Hondru, Radu Tudor lonescu, and Mubarak Shah. Diffusion models in vision: A survey, arXiv preprint ar Xii::2209.04747 2022.
Jacob Devlin, Ming- Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume I (Long and Short Papers), pp. 4171-4186, Minneapolis, Minnesota, June 2019. Association for Computational Linguistics. doi: 10.18653/v1l N19-1423, URL https: / /ttp///aaaaaat......///.. wrg/N19-1 1423.
Bhuwan Dhingra, Kathryn Mazaitis, and William W Cohen. Quasar: Datasets for question answering by search and reading. arv preprint ar arXiv:1707.03904 2017.
Sander Dieleman, Laurent Sartran, Arman Roshannai, Nikolay Savinov, Yaroslav Ganin, Pierre H Richemond, Arnaud Doucet, Robin Strudel, Chris Dyer, Conor Durkan, et al. Continuous diffusion for categorical data. arviv preprint ar xrXiv:2211.1508,, 2022.
Patrick Esser, Robin Rombach, Andreas Blattmann, and Bjorn Ommer. Imagebart: Bidirec- tional context with multinomial diffusion for autoregressive image synthesis. Advances in Neural Information Processing Systems, 34:3518-333 003318-333,,,, 2021.
11

---

Published as a conference paper at COLM 2024
Zhujin Gao, Junliang Guo, Xu Tan, Yongxin Zhu, Fang Zhang, Jiang Bian, and Linli Xu. Difformer: Empowering diffusion model on embedding space for text generation. arviv preprint ar Xix:2222.009412, 2022.
Marjan Ghazvininejad, Omer Levy, Yinhan Liu, and Luke Zettlemoyer. Mask-predict Parallel decoding of conditional masked language models. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference Natural Language Processing (EMNL.P-JCCNLP), pp. 6112-6121, Hong Kong, China, November 2019. Association for Computational Linguistics. doi: 10.18653/vi /vl/ D19-1633. URL httphh:://cllatttlllleaeee ortp://91/..//011333333
Marjan Ghazvininejad, Omer Levy, and Luke Zettlemoyer. Semi-autoregressive training improves mask-predict decoding. arXiv preprint ar axXit:2001..8885, 2020.
Shansan Gong, Mukai Li, Jiangtao Feng, Zhiyong Wu, and LingPeng Kong. Diffuseq: Se- quence to sequence text generation with diffusion models. arXiv preprint arXiv:2210.08953,, 2022.
Jiatao Gu, James Bradbury, Caiming Xiong, Victor O.K. Li, and Richard Socher. Non- autoregressive neural machine translation. International Conference on Learning Represen- fations, 2018. URL httpps:/ net http::////ppperreeeeeeeee//rrord
Jiatao Gu, Changhan Wang, and Junbo Zhao. Levenshtein transformer. Advances in Neural Information Processing Systems, 32, 2019.
Shuyang Gu, Dong Chen, Jianmin Bao, Fang Wen, Bo Zhang, Dongdong Chen, Lu Yuan, and Baining Guo. Vector quantized diffusion model for text-to-image synthesis. In Proceedings of the TEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 10696-10706, 2022.
Kilian Konstantin Haefeli, Karolis Martinkus, Nathanaël Perraudin, and Roger Watten- hofer. Diffusion models for graphs benefit from discrete state spaces. ar preprint arXiv:2210.01549, 2022.
Xiaochuang Han, Sachin Kumar, and Yulia Tsvetkov. Ssd-Im: Semi-autoregressive simplex- based diffusion language model for text generation and modular control. Xiv preprint arXiv:2210.17332, 2022.
Zhengfu He, Tianxiang Sun, Kuanning Wang, Xuanjing Huang, and Xipeng Qiu. Diffu- sionbert: Improving generative masked language models with diffusion models. Xiv preprint ar arX::22211.1002 2022.
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural In- formation Processing Systems, volume 33, pp. 6840-6851, 2020. URL https::/ neurips. ceurips..c/papeeeee cc/pppppppe2/0/00 http://022//111eec5eefeeeee Leee/ccbbbefee55aaaaooori... 01 79ca4bbPaper..pp
Jonathan Ho, Tim Salimans, Alexey Gritsenko, William Chan, Mohammad Norouzi, and David Fleet. Video diffusion models. arXiv preprint a/Xto:2204.03458 2022.
Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi. The curious case of neural text degeneration. In International Conference on Learning Representations, 2020. URL https://openreeiiee net/forum
Emiel Hoogeboom, Didrik Nielsen, Priyank Jaini, Patrick Forré, and Max Welling. Argmax flows and multinomial diffusion: Learning categorical distributions. In A. Beygelzimer, Y. Dauphin, P. Liang, and Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021. URL
Emiel Hoogeboom, Alexey A. Gritsenko, Jasmijn Bastings, Ben Poole, Rianne van den Berg, and Tim Salimans. Autoregressive diffusion models. In International Conference on Learning Representations, 2022a. URL https:://pperree wtw..e/eorrruuiiinnann.........
12

---

Published as a conference paper at COLM 2024
Emiel Hoogeboom, Victor Garcia Satorras, Clément Vignac, and Max Welling. Equivariant diffusion for molecule generation in 3D. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp- 8867-8887. PMLR, 17-23 Jul 2022b. URL https: https://proceedingg. mlr. press/v162/ hoogeboom22a. html..
Minghui Hu, Yujie Wang, Tat-Jen Cham, Jianfei Yang, and Ponnuthurai N Suganthan. Global context with discrete diffusion in vector quantised modelling for image generation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 11502-11511, 2022a.
Minghui Hu, Chuanxia Zheng, Heliang Zheng, Tat-Jen Cham, Chaoyue Wang, Zuopeng Yang, Dacheng Tao, and Ponnuthurai N Suganthan. Unified discrete diffusion for simul- taneous vision-language generation. arXiv preprint arXio:2211.14842 2022b.
Xiao Shi Huang, Felipe Perez, and Maksims Volkovs. Improving non-autoregressive transla- tion models without distillation. In International Conference on Learning Representations, 2022. URL https: //tptree//ppeereieee.... wwwp:wwweeeeoeeeee wtte//orrmmmii12225aaree.
Jaehyeong Jo, Seul Lee, and Sung Ju Hwang. Score-based generative modeling of graphs via the system of stochastic differential equations. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 10362-10383. PMLR, 17-23 Jul 2022. URL https: httpss///ooceeedeeee www.mmr.ppee.. .pres// v162/jo22a. html.
Daniel D. Johnson, Jacob Austin, Rianne van den Berg, and Daniel Tarlow. Beyond in-place corruption: Insertion and deletion in denoising probabilistic models. In ICML Workshop on Invertible Neural Networks, Normalizing Flows, and Explicit Likelihood Models, 2021. URL 1Rn
https:///penreviiew wtwpreerrriiieeneeooruummmm meet/oormmid=cAAS
Rabeeh Karimi Mahabadi, Hamish Ivison, Jaesung Tae, James Henderson, Iz Beltagy, Matthew Peters, and Arman Cohan. TESS: Text-to-text self-conditioned simplex dif- fusion. In Proceedings of the 18th Conference of the European Chapter of the Associa- tion for Computational Linguistics (Volume 1: Long Papers), pp. 2347-2361, 2024. URL eacl-long. 144.
https: http://alanntollo.orrr/////// oag.caattooooo..rrr//////aaaaaad
Tero Karras, Miia Aittala, Timo Aila, and Samuli Laine. Elucidating the design space of diffusion-based generative models. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022. URL https://openreviie http::://ooenrrreeee..e..oorrooo seee//oorummidkkFFTOOme
Jungo Kasai, James Cross, Marjan Ghazvininejad, and Jiatao Gu. Non-autoregreesive machine translation with disentangled context transformer. In International conference on machine learning, pp. 5144-5155. PMLR, 2020.
Yoon Kim and Alexander M. Rush. Sequence-level knowledge distillation. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pp. 1317-1327, Austin, Texas, November 2016. Association for Computational Linguistics. doi: 10.18653/ #1/D16-1139 URL
.rr.i/oggo...g/eeeee org/D16-111 1139.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. Xiv preprint ar Xix: (ttt::412.698.. 2014.
Zhifeng Kong, Wei Ping, Jiaji Huang, Kexin Zhao, and Bryan Catanzaro. Diffwave: A versatile diffusion model for audio synthesis. In International Conference on Learning Representations, 2021. URL https:///opee ctttps://pperrevie..eet//// i
Wouter Kool, Herke Van Hoof, and Max Welling. Stochastic beams and where to find them: The gumbel-top-k trick for sampling sequences without replacement. In International Conference Machine Learning, pp.
PMLR, 2019.
13

---

Published as a conference paper at COLM 2024
Wouter Kool, Herke van Hoof, and Max Welling. Ancestral gumbel-top-k sampling for sampling without replacement. Journal of Machine Learning Research, 21(47):1-36, 2020. html.
URL htRp:///// http:///mmmor.rg/paeeeeeee wttpppppers//211111-----
Jason Lee, Elman Mansimov, and Kyunghyun Cho. Deterministic non-autoregressive
neural sequence modeling by iterative refinement. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pp. 1173-1182, Brussels, Belgium, October-November 2018, Association for Computational Linguistics. doi: 10.18653/ /v// D18-1149. URL httpt:::/s//ltttthhtht
org/D18 11449.
José Lezama, Huiwen Chang, Lu Jiang, and Irfan Essa. Improved masked image generation with token-critic. In European Conference Computer Vision, pp. 70-86. Springer, 2022.
Xiang Lisa Li, Ari Holtzman, Daniel Fried, Percy Liang, Jason Eisner, Tatsunori Hashimoto, Luke Zettlemoyer, and Mike Lewis. Contrastive decoding: Open-ended text generation as optimization. Xiv preprint arXio:2210.15097 2022a.
Xiang Lisa Li, John Thickstun, Ishaan Gulrajani, Percy Liang, and Tatsunori Hashimoto. Diffusion-LM improves controllable text generation. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022b. URL https: /openr/iiee//..e.e..e..ee... net met/forummddd33s91EEs]]]
Yifan Li, Kun Zhou, Wayne Xin Zhao, and Ji-Rong Wen. Diffusion models for non- autoregressive text generation: A survey. ar arv preprint ar Xiv::3033.06574, 2023.
Zhenghao Lin, Yeyun Gong, Yelong Shen, Tong Wu, Zhihao Fan, Chen Lin, Weizhu Chen, and Nan Duan. Genie: Large scale pre-training for text generation with diffusion model. Xiv preprint arXit:2212.1168) 2022.
Justin Lovelace, Varsha Kishore, Chao Wan, Eliot Shekhtman, and Kilian Weinberger. Latent diffusion for language generation. arXiv preprint ar XrXio:2212.09462, 2022.
Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. Pointer sentinel mixture models. arXiv preprint ar (0900.36,, 2016.
Alexander Quinn Nichol and Prafulla Dhariwal. Improved denoising diffusion probabilistic models. In International Conference Machine Learning, pp. 8162-8171. PMLR, 2021.
Myle Ott, Sergey Edunov, Alexei Baevski, Angela Fan, Sam Gross, Nathan Ng, David Grangier, and Michael Auli fairseq: fast, extensible toolkit for sequence modeling. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics (Demonstrations)) pp. 48-53, Minneapolis, Minnesota, June 2019. Association for Computational Linguistics. doi: 10.18653/va /1/119-409, URL https:
l/aclanthology.org www.ollooo..ogNN/... 00g.///9/y/rr//9-100500
Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. Bleu: method for automatic evaluation of machine translation. In Proceedings of the 40th Anmual Meeting of the Association for Computational Linguistics, pp. 311-113116 Philadelphia, Pennsylvania, USA, July 2002. Association for Computational Linguistics. doi: 10.3115/1077088.177733. URL https: / /atttto//allatthollogg.. org/po2-10444
William Peebles and Saining Xie. Scalable diffusion models with transformers. arXiv preprint ar arXit::212.09978,, 2022.
Krishna Pillutla, Swabha Swayamdipta, Rowan Zellers, John Thickstun, Sean Welleck, Yejin Choi, and Zaid Harchaoui. Mauve; Measuring the gap between neural text and human text using divergence frontiers. Advances in Neural Information Processing Systems, 34: 4816-4825 4828, 2021.
Matt Post. A call for clarity in reporting BLEU scores. In Proceedings of the Third Conference on Machine Translation: Research Papers, pp. 186-191, Brussels, Belgium, October 2018. Association for Computational Linguistics. doi: 00.18653/w1/W11-4 URL https:
/ //aclanthology.orr W
14

---

Published as a conference paper at COLM 2024
Lihua Qian, Mingxuan Wang, Yang Liu, and Hao Zhou. Diff-glat: Diffusion glancing transformer for parallel sequence to sequence learning arx preprint arXi::2212.10240, 2022.
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, al. Language models are unsupervised multitask learners. OpenAl blog, 1(8):9, 2019.
Aditya Ramesh, Prafulla Dhariwal, Alex Nichol, Casey Chu, and Mark Chen. Hierarchical text-conditional image generation with clip latents. Xiv preprint ar arXio:2004.06125, 2022.
Ricardo Rei, Craig Stewart, Ana C Farinha, and Alon Lavie. COMET: A neural framework for MT evaluation. In Proceedings of the 2020 Conference Empirical Methods in Natural Language Processing (EMNLP), PP. 2685-2702, Online, November 2020. Association for Computational Linguistics. doi: 10.18653 /v1 1e11//20..mmnlmmmaae aclanthology. org/2020. emnlp-main.21 213.
URL https://
Machel Reid, Vincent J Hellendoorn, and Graham Neubig. Diffuser: Discrete diffusion via edit-based reconstruction. Xr preprint arXiv:2210.16886 2022.
Pierre H Richemond, Sander Dieleman, and Arnaud Doucet. Categorical sdes with simplex diffusion. arXiv preprint ar arXiv:2210.14784, 2022.
Robin Rombach, Andreas Blattmann, Dominík Lorenz, Patrick Esser, and Björn Ommer. High-resolution image synthesis with latent diffusion models. In Proceedings of the IEÉE/CVF Conference on Computer Vision and Pattern Recognition, pp. 10684-10695, 2022.
Chitwan Saharia, William Chan, Saurabh Saxena, Lala Li, Jay Whang, Emily Denton, Seyed Kamyar Seyed Ghasemipour, Raphael Gontijo-Lopes, Burcu Karagol Ayan, Tim Salimans, Jonathan Ho, David J. Fleet, and Mohammad Norouzi. Photorealístic text-to-image diffusion models with deep language understanding, In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022. URL https: /operrvie/pereviie.. www.:eetooommmiddo88-------
Nikolay Savinov, Junyoung Chung, Mikolaj Binkowski, Erich Elsen, and Aaron van den Oord. Step-unrolled denoising autoencoders for text generation. In Infernational Conference on Learning Representations, 2022. URL https: www..eee/oorumiicceoppp211111111
Ari Seff, Wenda Zhou, Farhan Damani, Abigail Doyle, and Ryan Adams. Discrete object generation with reversible inductive construction. Advances in Neural Information Processing Systems, 32, 2019.
Rico Sennrich, Barry Haddow, and Alexandra Birch. Neural machine translation of rare words with subword units. In Proceedings of the 54th Anmual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp- 1715-1725, Berlin, Germany, August 2016. Association for Computational Linguistics. doi: URL httpsss/aaclanttoooo...rrrp
org/P16-1162
Jascha Sohl-Dickstein, Eric Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsupervised learning using nonequilibrium thermodynamics. In International Conference on Machine Learning, pp. 2256-2265. PMLR, 2015.
Jiaming Song, Chenlin Meng, and Stefano Ermon. Denoising diffusion implicit models. In International Conference on Learning Representations, 2021a. URL https:///penreevie... net/ giarcL
Yang Song, Jascha Sohl-Dickstein, Diederik P Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-based generative modeling through stochastic differential equations. In International Conference on Learning Representations, 2021b. URL https: //pnnr/vee.e....ee. net/forum?id-PXTTCC 2RRHS.
Mitchell Stern, William Chan, Jamie Kiros, and Jakob Uszkoreit. Insertion transformer: Flexible sequence generation via insertion operations. In International Conference on Machine Learning, pp- 5976-59985 PMLR, 2019.
15

---

Published as a conference paper at COLM 2024
Robin Strudel, Corentin Tallec, Florent Altché, Yilun Du, Yaroslav Ganin, Arthur Mensch, Will Grathwohl, Nikolay Savinov, Sander Dieleman, Laurent Sifre, et al. Self-conditioned embedding diffusion for text generation. arXio preprint ar
2022.
Yixuan Su and Nigel Collier. Contrastive search is what you need for neural text generation. arXiv preprint ar Xrxv::2200.1411 2022.
Haoran Sun, Lijun Yu, Bo Dai, Dale Schuurmans, and Hanjun Dai. Score-based continuous- time discrete diffusion models. arXiv preprint arXio:2211.16750 2022.
Zhicong Tang, Shuyang Gu, Jianmin Bao, Dong Chen, and Fang Wen. Improved vector quantized diffusion models. arviv preprint arXiv:2205.16007, 2022.
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. Llama: Open and efficient foundation language models. arXiv preprint arXio:2302.13971, 2023.
Arash Vahdat, Karsten Kreis, and Jan Kautz. Score-based generative modeling in latent space. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), Advances int Neural Information Processing Systems, 2021. URL https: http::///pppeeeeeeeeeeeeeeeeeeee P9TYG0j-wtG.
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 information processing systems, pp. 5998-6008, 2017.
Tim Vieira. 2014.
Gumbel-max trick and weighted reservoir sampling, URL http://timvieiin githgb.thhh... htt/boo//pos///0///000000 cumbel-max- wwi---ric----- bocck-and-welle wew.deeiigteeed-sssrrrr-r--aaaae
Clement Vignac, Igor Krawczuk, Antoine Siraudin, Bohan Wang, Volkan Cevher, and Pascal Frossard. Digress: Discrete denoising diffusion for graph generation. arxiv preprint ar Xiiv:2209.14734 2022.
Rose E Wang, Esin Durmus, Noah Goodman, and Tatsunori Hashimoto. Language modeling via stochastic processes. In International Conference on Learning Representations, 2022. URL https://openrevii
1ytf..
Tong Wu, Zhihao Fan, Xiao Liu, Hai-Tao Zheng, Yeyun Gong, Jian Jiao, Juntao Li, Jian Guo, Nan Duan, Weizhu Chen, et al. Ar-diffusion: Auto-regressive diffusion model for text generation. Advances in Neural Information Processing Systems, 36:39957-39974, 2023.
Ling Yang. Zhilong Zhang, Yang Song, Shenda Hong, Runsheng Xu, Yue Zhao, Yingxia Shao, Wentao Zhang, Bin Cui, and Ming-Hsuan Yang. Diffusion models: A comprehensive survey of methods and applications. Xiv preprint ar arXio:2209.00990 2022.
Zhilin Yang, Zihang Dai, Yiming Yang, Jaime Carbonell, Russ R Salakhutdinov, and Quoc V Le. Xlnet: Generalized autoregressive pretraining for language understand- ing. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Buc, E. Fox, and R. Gar- nett (eds.), Advances Neural Information Processing Systems, volume 32, pp. 5753-5763. Curran Associates, Inc., 2019. URL https: http:::/p/oceeediieei http///pppcee...cceo/e/ pdf.
Jiasheng Ye, Zaixiang Zheng, Yu Bao, Lihua Qian, and Mingxuan Wang. Dinoiser: Diffused conditional sequence learning by manipulating noises. arXiv preprint arXio:2302.10005, 2023.
Lijun Yu, Yong Cheng, Kihyuk Sohn, José Lezama, Han Zhang, Huiwen Chang, Alexander G Hauptmann, Miuan Yang, Yuan Hao, Irfan Essa, et al. Magvit: Masked generative video transformer. ar preprint arXiv:2212.05199, 2022.
Hongyi Yuan, Zheng Yuan, Chuanqi Tan, Fei Huang, and Songfang Huang. Seqdiffuseq: Text diffusion with encoder-decoder transformers. arXiv preprint arXio:2212.1083 2022.
16

---

Published as a conference paper at COLM 2024
Susan Zhang, Stephen Roller, Naman Goyal, Mikel Artetxe, Moya Chen, Shuohui Chen, Christopher Dewan, Mona Diab, Xian Li, Xi Victoria Lin, et al. Opt: Open pre-trained transformer language models. arXiv preprint arXiv:2205.01068, 2022.
Ye Zhu, Yu Wu, Kyle Olszewski, Jian Ren, Sergey Tulyakov, and Yan Yan. Discrete contrastive diffusion for cross-modal and conditional generation. arXiv preprint ar Xtir:22066.77711, 2022.
17

---

Published as a conference paper at COLM 2024
Appendices
A Related Work
A.1 Diffusion Models for Text Generation
Text Generation with Discrete Diffusion. Discrete diffusion processes have close connec- tions with previously developed language models. For instance, traditional auto-regressive language models can be seen as a special deterministic discrete diffusion process (A (Austin et al., 2021). In addition, D3PMs (Austin et al., 2021) also introduce an absorbing diffusion strongly linked to masked language models (Devlin et al., 2019). The diffusion formulation further generalized in various aspects, such as enabling editing-based operations (Johnson et al., 2021) or casting generic permuted language models (Yang et al., 2019) as a diffusion process (Hoogeboom al., 2022a).
The text generation performance of discrete diffusion processes is initially evaluated on language modeling tasks (Hoogeboom et al., 2021; Austin et al., 2021), despite limited success. Recent studies have improved the performance of discrete diffusion on various tasks by devising unrolling training strategies (Savinov et al., 2022), combining pre-trained models (He et al., 2022), incorporating autoregressive decoding with editing-baset refinements (Reid et al., 2022), or leveraging a more effective diffusion process over data modalities with advanced search algorithms (Qian et al., 2022).
Text Generation with Continuous Diffusion. There has been a surge of recent interest in adapting continuous diffusion models for text generation. This approach typically applies Gaussian diffusion over the embedding space, achieving impressive results (Li et al., 2022b; Gong et al., 2022; Dieleman 2022; Gao et al., 2022; Ye et al., 2023; Wu et al., 2023). Some studies convert discrete tokens to bit strings and model them as real values (Chen et al., 2022), or inject Gaussian noise into token logits instead of embeddings (Han et al., 2022; Karimi Mahabadi et al., 2024). Other studies focus on learning a latent continuous diffusion of pre-trained models (Wang et al., 2022; Lovelace et al., 2022). In contrast, RDMs do not rely on pretrained language model checkpoints and generate high-quality text with significantly fewer steps compared to continuous diffusion models. For detailed review of recent advances in diffusion models, we refer readers to Cao et al. (2022); Croitoru et al. (2022); Yang et al. (2022); Li al. (2023).
al., 2022; Strudel et al., 2022; Lin et al., 2022; Yuan et al.,
reggrsssee
A.2 Iterative Non-autoregressive Text Generation
Diffusion-based generative models are closely related to iterative non-autoregreesive gener- ation (Gu et al., 2018) in the context of machine translation. The generation process often involves iterative refinement (Lee et al., 2018; Ghazvininejad et al., 2019; Stern et al., 2019; Gu et al., 2019; Kasai et al., 2020; Ghazvininejad et al., 2020; Huang et al., 2022). Our adaptive routing mechanism (64.3) takes inspiration from the heuristic used in CMLM (Ghazvinine- jad et al., 2019), which refines the sequence by masking tokens with low model confidence. However, unlike CMLM, our approach only integrates the masking heuristic within the routing mechanism at each diffusion step, rather than relying entirely on it for decoding. This makes the decoding procedure governed by the formulated diffusion process and helps achieve better performance in practice.
B Extended Background about Discrete Diffusion Models
Discrete diffusion probabilistic models are first explored in Sohl-Dickstein et al. (2015) for Bernoulli data. Multinomial diffusion (Hoogeboom et al., 2021) later proposes a uniform corruption process for categorical variables, which are extended by D3PMs (Austin et al., 2021) to support general transition matrices, including an absorbing variant that draws close connections to masked language models (Devlin et al., 2019). Several recent works
18

---

Published as a conference paper at COLM 2024
push this line of research further in various aspects, such incorporating editing-based operations (Johnson et al., 2021; Reid et al., 2022), casting permuted language models (Yang et al., 2019) as diffusion models (Hoogeboom et al., 2022a), developing continuous-time framework (Campbell et al., 2022), as well as exploring an analog of score functions for learning the reverse process Sun al. (2022).
Applications. Discrete diffusion has been applied to a variety of tasks, including graph generation (Seff et al., 2019; Haefeli et al., 2022; Vignac al., 2022), image generation (Esser et al., 2021; Bond- et al., 2022; Gu et al., 2022; Tang et al., 2022; Hu et al., 2022a), vision- language generation (Hu et al., 2022b), and general multimodal conditional synthesis (Zhu et al., 2022). Lezama et al. (2022) draws connections between discrete diffusion processes and non-autoregressive Transformers for visual domains (Chang et al., 2022; Yu et al., 2022, Chang et al., 2023).
B.1
The derivation of ELBO
Discrete diffusion models are typically trained by maximizing a lower bound of its marginal log-likelihood, defined below,
log Po (x))
/ Pe x1, XI. xT)dxx ... -xx
= =log|
/
xT)
log
9(x1)..... q(x1...., xT xo)
9(2g ... g(2
xx) dxx
Po Xg... xT)
log Egixm.xxyxx
9x
xo)
log Po ... .
2 E Eq o (oo
(x xx)
log Po x1) xx)xxxpppp Po IT Po x/xx)
E xy 1o)
((xT(xx) (x0) I1 9 (x, Xt, xo)
T Σ log g(x, xx,
9(x (x0
E (x (o)
log (x
log po(xT)
po(x
Ey log (x(0)))))))
Σ (x pe (x)-1(xx))
KL(g(XT(x0) |l po(xT))
= (x)) [log (logpo(x)
Σ (xxx)))) (l( I| (x(xx-1xx))) +onst.
(9)
(0)
Li(
B.2
Parameterization
Recall that our objective is to minimize the KI. divergence between (x)-1|x;,>0) and a parameterized distribution (x(x==1xx; at each time step. widely adopted way is then defining Pe(x xx+) = ((x--1xx;,0)) where xn fx;; 0) is predicted by a Trans- former model. Austin al. (2021) considers an alternative parameterization by letting px(x;-1(x;) & Σx, (x;-1, (x)) where we learn (x(x)) similarly to f(x;; 0). These two approaches are different in general and define distinct generative processes in general; we follow the former method due to its simplicity and conciseness. More details can be found below.
B.3 Backward Transition Probabilities
This section provides separate derivations for the original backward transition formulation of various discrete diffusion processes.
19

---

Published as a conference paper at COLM 2024
Absorbing Diffusion. The absorbing diffusion (Austin et al., 2021) defines Markov chain where a token goes into an absorbing mask state denoted by [M] with some probability at each time step and stays the same thereafter. The forward transition probability is defined as (xx) x 1) = fix; + (1 Inoise where moise = M is the point mass with all of the probability an absorbing state (the mask state [M] is denoted as one-hot vector).
Regarding the conditional backward transition probability | xo), x can only stay in either state Xo or state [M]. If x; Xo, then x;-1 must also be in state xo since not absorbed yet; while if x = MMM] we have
[M]]x; xn) q(x; [M] [M) [M]
xxx11
9(x; = [M]
1. (1 at
1 at
241
1 ai
9(x1-1 = xo|x; (0), (xx = [M]]x;
xo xo)g(x; xolxx)
9(x:= [M]]x
(1 B:)a4-1 111-1
1 at
a:
The actual generative process is defined as po 1xx) x Exo xx) (xx)) where we predict the probability vector (3 == fxo (xx; 0) Austin et al. (2021), this formulation has a simple expression. Suppose k + [M] is one of the possible states. Note that
from a Transformer. As shown in
if x; = k + [M), then due to the joint (x, (o) there is only one entry that is non-zero within the sum (x;-1 = k, x; = k| = pe = k|x²). As a result, the reverse distribution becomes point mass over position
if x; [M], we have
Po (x+ 1 [M] x1
[M]) 0 Σ (x1 [M] 1 [M]]((x; 1 (ooo/)) xx)
Σ at 1)po(x)lxx)
%0
(1 at 1) Σ (o
A1-1i
Po(x k|x;, = [M] 0 Σ [x1 = [M] = k) k/
= -x(: = [M] k)g(x; = k/ā0 = po = k(xx)
(a;-1 - at Po = k/xx))
They can be easily normalized well,
Po(x; 1 = [M][x] = [M) = 1 1-441 a
1 ai
Po(x4-1 = k|x; = [M) (a: 1 a: ao)Po(Xo = k/xx)
Ri
This can be written in more compact way, where Po( k|x; = f& (x1; 0) and Jnoise
[M] is point mass with all the probability put over the absorbing state [M].
pe(x-1lxx))
( X,,
1- I R1
f(x:;0) 0)
+ I #:-1
Inoiser
if x: [M]
(10)
if x;; + [M].
We can also generalize this result for 0 < < f < T. For the forward transition, we have g Xx- xo) -i 8ix0 + (1 I Bi) qnoise a, xg
As-Ri
a. 9noise- Thus the
20

---

Published as a conference paper at COLM 2024
backward transition can be derived as well according to Bayes' rule,
x0 +
As T-a, Anoiser
if [M]
[x,)xx,,00)
(11)
X1,
if x: + [M].
as d:
I-ai ff fxx;;)) + 1-a. Inoiser
as
if x M
Po(xs(x1)
(12)
X1,
x + [M].
Multinomial Diffusion. In multinomial diffusion (Hoogeboom et al., 2021), the forward transition probability is defined as (xx x;-1) f1x; + (1 Be 9noise where fnoise = 1/K K uniform distribution over (1,2,..., Kj with a K-dimensional vector with all ones. The backward transition probability conditional on the original data Xo can be derived according to Bayes' rule and in closed form:
g(xe (03()xx-)991 (x9 (xO)
9
(Bix) + (1 - (i) 1) ④ (ap-1x0 + - (1-a+11)4 a2-1)k)
x, (R+20 + (1 az) k)
a;ai ④ XD + k a)-1)x; + k1 B1)a + K2 (1 BB) -x--1)
(13)
aix, xo + * (1-x))
Multinomial diffusion (Hoogeboom et al., 2021) learns a parameterized distribu- tion p0(x;-11 -1]=;) to approximate 1 xo) at each time step, which is defined as Po(x; 1xx:) = ((x &0) with &g = fxx;; 0) being the output by a Transformer model.
Po(x;-1(x;)
4:x: ② fx);0) + kB: as 1)x; + {1 (f)=;-1((x;0) + º² (1)(11 14 axx, (x + t1(1 24)
(14)
C Derivation for Proposition 3.1
In this section, we provide the derivation for Equation 2 based on Bayes' rule.
Proof. We denote RK*K as the probability transition matrix for the f-th step, where [Prlij p(x = j|xx-1 = i) and thus the probability distribution in the forward process can be described as q(x; x Categorical (x:; P, xx-1). It is then easy see that
g(x)1x0)
Σ
11 ... x1 (xo)
Categorical (x P. xo)
2
with P. = P.P.... ... P. Returning to our case where the forward transition takes the form
(xx:|x; x1- 1,x;11 + (1 Bi B:ogseese- The transition matrix can be represented by P:
I + (1 1-B,) - and thus P.P2 P. a + a4)19 1 Equipped with
21

---

Published as a conference paper at COLM 2024
these results, can proceed with the derivation as follows, (x1-11xx,,
9(xx/1x; x 1)9(x; 1|x0)
Pax; @ P
((xx(x0)
x P. X0
B + (1- xx) 1| + (ag -4--1X0 180 + (1 - Inoise]
a12; x0 + (1 23) )xx Inoise
1INI-1N-OX0+ (1 110--1,- -1 O + -1- +0- (110)(111110000 -x,1)0xx11 Inoise
212; X0 + )xx 9noise
BIAL-124 + Br(1 1ii11-a--1 21-1)xx, + Br xxxx + (1 (1- - Inoise
4xxx xo + (1 az)
Here we denote @ as element-wise product and x = Inoise (u = xt) to represent the probability of noise drawn from Anoise being equal to xj. The need to differentiate between X; and Xn emerges when we calculate X @ Xo, which would be an all-zero vector except that it would be one if x = Xo- Thus the computation of backward transition probabilities breaks down into two cases:
x; = xo, we have X ④ Xn = X1, X Xo and thus
g(x--1/21,x0)
B1a1-127 B+ 01 111-1 Jx
+ (1 B1)a 10x, + (1 -1) a1- Inoise
81 + (1 ax)xxx
Bran-1 + Bi(1 a1-1)00
+ (1 - 11)ax_10x, X
(1- a)-1)(xx,
Onoise
a; + (1 a4 (x)
at + +11 ax)(xx
If xı o xo, we have X1 ④ x0 = 0, x T = 0 and thus
(xx,) = (, - 0 a1-1)0xx, x + (1 -1) + (1 - -B:)(1 a;- xx
01 0x)(xxx
B,(1 - -- 1 )x1 + (1 - 81) -1 + (1 - -B) a4-1 Inoise
1 -
B:)a
B1 81-1)
X4 + (1- (1-Bi)(1 a1-1)
x0 +
anoise
1 at
1 1 at
1- az
(1 xo
Br)aa-1
1 1 111-1
[Bix: (1 [t)
1 at
0:
& 1-1 1 at +
1 a1 O'F
[B:x1 + (1 Bi) B:)gnoise]
1 at
Putting them together, we arrive at the resulting formulation,
(1)
x1
+
1 11)
gnoises if x =
(1x)_1x;,,00) =
(2)
x0
+ (1- x(9) Anoise (xi),
if xi # X0-
Here 1 =
(1 P:( a; Mnoose (u xi)
112
= R- di
T- and Inoise (x:) = Bix; + (1
Rt Rc++(1 R1 xt]anoisel (M (M=x
B:) gnoise denotes noise distribution that interpolates between X; and Anoise, both of which are possibly noisy.
Generalization. Similar to vanilla diffusion models, we can also derive backward transi- A₁. It can be easily
tion processes with gap A;; that is, we consider (xss xo) with seen that
1 xt + 1
Anoiser
if x; X
qxxs/xx,
(15)
1 x + (1 122) Gnoise (x:),
if i; xo,
22

---

Published as a conference paper at COLM 2024
with A! == (1- 2t (1-Aa) Anoose (u=x;) and A!
&t at Rmoise!! MM-xx Xx)
T-a
D Derivations for the ELBO of RDMs
The following provides the derivation for the loss objective of RDMs. Specifically,
log p(xo)
Po(xo, X1:T, v1:7) log ( U1.7 xx)
2 (urr
x1) P1 UT)
log Il: x0, XT, DT x0)
log (eppol + Σ log Po(x; 1, x1)
(1 + log p(xr, UT)
q qxI, DT xx)
= C Σ (e) + const.
Here we denote (0) = Fg(g) (m) {o and for 1 1, () Eg(x)(zg)
1, (/
x0),
We can push the decomposition of
(0) for time step >> further, (.(0)
= =Iq(xx(X0))
(L |l -,
log (x 8 X xo)
[x((((x
Σ
g(x1-1
(o 0/-1 xx)
11-100111
Σ g(x; 1/0; 1,x1, 1) log - 1o(xx-110-11,x7) Xi 18
+ +og 9(11-1) po(o
= -
E Derivation for Equation 6 and Discussions
Proof. We first consider the loss objective at each step for each token и-th position, which can be expanded as follows,
C ()) (g( (g(PI-La) (L(q(x:LLnl 1xx Xt,n, xox)
po(x; I. o 1mm x.m))]]
Typically draw a Monte Carlo sample Xt, ( xnx) to estimate the outermost ex- pectation above. For the inner term, recall that bιn = =x and q(x; Lnl 1 X1, X0,x) takes the form as
1 N + (1 (1- (1)
11-0;-1,1 Inoiser
if bI, = 1
g(x1-1xxl Vi- X Xox)
=
In + 0/ 1,2 Gnaise (moise(Xta))
b = O.
Since we use the teacher-forcing approach that employs the same oracle b for po(x; inlo, Im Xi,) as well, it can also be written in similar manner,
0 Ntn Ni, u + (1 (1-11//))) (1-1/-)m) 1/-1m) 9noiser
(1)
(1)
if b
( 11-1, Xtm))
(2)
inf inf 0) + (1 0f 1m Inoise (x),)),
(2)
if be 0.
The derivation then breaks down into two cases with respect to by.
23

---

Published as a conference paper at COLM 2024
If bm, 1. In this case, (x Pt-1, Xt, X0,n) X0m)) 1o(x1_1n10)-1,x>> Xtn) (1-0/-1n Inoise. Since these two distributions become identical, this leads to zero KL divergence irrespective of 1, so that (i) 0;
2 1-11, *tm +
If bt.n 0. In this scenario,
have (xxx Ni,n 1 (2)
o Xo, +
(1 (1-0,² (1-0
U 1,1 Gnoise (Xt,)) and 0 1n
(2)
1n f 0) + 1 0, 1, Inoise (xtm). We then enumerate
all the possible outcomes for , (2) of
1 t- Lu = 1, q() = (22) and
If
KL(g(xx11,nlD-- In Ny,, x0,)) Po(x Po(x--1,1 1n Xt,))) KL (x0,x ( 0)) - xo, log f (xi,ni 0)
If 1 1-1n 0, then (()-1,n)) = M and
WL In - Xtn) = (Lngnoeee (xtm) || 9noise (xta:)
0.
Putting them together, we have
E g(()-1a) LLL Nt,n, x0,n)
po(xi Ln /n| -
L Xtn))
= Non log (xt,ni 0) + 1 )
(2) T
= Jog (xt,ni 0).
Since each token is modeled conditionally independently, we can add all computed losses for each token, arriving at the final expression for the whole sequence,
N (1 Σ (0)
IE Pdata (No,::N) | T ((x Na..))
(2) 1
Σ (1 n-
) log (xt,ni 0)
Connections D3PMs. The derived simplified loss objective bears some resemblance to that of absorbing diffusion in D3PMs (Austin et al., 2021), which also takes the form of a cross-entropy function over masked positions. However, our derivation arises from the developed reparameterization perspective and thus stems from distinct motivation from D3PMs. In addition, our objective applies to wide range of discrete diffusion processes, including those with multinomial noise, absorbing noise, mixture of both. This constitutes non-trivial generalization of D3PMs, which only demonstrates that the cross-entropy representation is available for absorbing diffusion. Besides, our formulation explicitly elucidates the role of routing mechanisms in training, which provides insights into techniques that improve decoding quality.
Additional Implementation Details
This section describes the implementation details of our experiments.
E1 Tasks
Machine Translation. For experiments on machine translation, we consider three standard benchmarks:
IWSLT14 DE-EN (Cettolo et al., 2014), which contains around 160K sentence pairs for training, validation, and testing, respectively. We build joint vocabulary for the source and target language, resulting in 10152 Byte Pair Encoding (BPE; Sennrich et al., 2016) types.
24

---

Published as a conference paper at COLM 2024
Model
Iterations
Tokenized BLEU
sacreBLEU
COMET
Auto-regressive
27.53
26.5
0.8238
25.63
24.1
0.7808
RDM-multinomia
24.2
0.7937
26.96
25.2
0.8082
RDM-absorbing
27.58
26.2
0.8288
Table 5: Comparisons among different evaluation metrics on WMT1 1 EN-DE.
WMT14 EN-DE (Bojar et al., 2014) dataset consists of around 4.0M/3K/3K train- ing/validation/ saalidation/eestingg pairs. The preprocessing follows Ghazvininejad et al. (2019)
and yields a shared vocabulary with 40624 BPE types;
WMT16 EN-RO (Bojar et al., 2016). We use the same data split from Lee et al. (2018) that comprises around /10K/2K// /2KK pairs. The vocabulary is shared between the source and target sides with 34976 joint BPE types.
We operate original data for all translation tasks and do not adopt knowledge distillation (Kim Rush, 2016; Gu al., 2018) that replaces the target side training data with outputs generated by pre-trained autoregressive Transformer.
For evaluation, we report tokenized BLEU (Papineni et al., 2002) scores ap- plied with compound split post-processing to facilitate comparison. In addi- tion, we also compute sacreBLEU (Papineni et al., 2002; Post, 2018) (signature: nrefs: meeeeeeiieeeeeeee eff: nol tok: / smooth: veession 0.00 0) and COMET (Rei et al., scores on WMT14 EN-DE test set, presented in Table 5. It be seen that both SaCreBLEU and COMET reveal trend similar to that of tokenized BLEU scores.
2020) (with version 2. 0.0.0 and model
Question Generation and Paraphrasing. For both QG and QQP tasks, use the same data split pre-processed as in Gong et al. (2022):
Question Generation (QG) with the Quasar-T dataset (Dhingra et al., 2017), containing respectively.
around 117K /2/KKK pairs for
Paraphrasing with Quora Question Pairs (QQP). This dataset comprises around 145K/2K/2.5K training/ hatpg/vaaaidiioo/////ooaa ieliaatiionttttinngggg question pairs.
Following Gong et al. (2022), use WordPiece tokenization in BERT (Devlin et al., 2019) and obtain a vocabulary of size 30522 for both tasks.
E2 Architectures
We employ the Transformer-bar architecture (Vaswani et al., 2017) for WMT experiments, while for 1WSLT14 DE-EN,QG, and CQP tasks we use a smaller Transformer model. Note that all self-attention blocks with the model are bi-directional and do not causal masks.
We adopt length prediction module (Ghazvininejad et al., 2019) on top of the Trans- former encoder to propose target length candidates for the generated sequence. Given the source input, we first run the Transformer encoder to obtain the encoder's 's hidden representation, which is averaged and passed linear layer to output the length scores.
The timestep embedding is obtained by first projecting the input timestep with sinu- soidal encodings and then passing through a two-layer MIP.
We adopt concalenated instead of additive position encodings, which is shown to enhance the positional information and produce better performance in the context of machine translation (Huang et al., 2022).
The detailed configuration for the neural network is listed in Table 6.
25

---

Published as a conference paper at COLM 2024
Hyper-uurmmeer
Number
encoder
Number transoomme decoder layes
Hidden size
512
512
512
512
512
hidden size BFN
2048
2048
1024
1034
1024
Number of attention hoads
8
4
Maximum number tokurn in butch Maximum number of senteners in batch
128K
32K
4K
256
256
Number of taining steps
300K
120K
500K
70K
70K
Number of warm-up steps
10K
19K
30K
10K
10K
Weight decay rade
0.01
0.01
0.01
0.01
0,01
Deak Learnngg Bate
0.0005
00005
0.0055
0.0055
0.0005
Label Smoothing
0:1
0.1
0.1
Learning rate decay
Inveree square root
Inverse square root Adam
Inverse equare root
Inverse square root Aclmm
Invens square root
Optimizer
Adam
Drupout
Cradient Clipping
contiaarrteeettiiuuatttttttn Table 6: The hyper-parametee configuration for machine translation.
Conditioned training
Absorbing
Multinomial
RDM-absorbing
RDM-multinomial
x
28.32
21.28
33.73
31.99
29.67
23.58
33.91
32.23
Table 7: BLEU scores on IWSLT14 DE-EN test set with/without conditioned training. The results are evaluated under different diffusion models with decoding iterations. Default decoding strategies are adopted for these models: vanilla multinomial or absorbing diffusion uses vanilla decoding, while reparameterized discrete diffusion models adopt improved decoding.
F3
Training
We allocate large number of diffusion time steps for training, such as 50 100. We found the number of diffusion steps in training does not affect the performance too much. Note that decoding can be performed with arbitrary number of iterations by choosing the appropriate step size A > 1. That is, we can decode by sampling X At (x(x; xt), following a similar treatment Equation 15.
Modern Transformer models usually process input sequences that are associated with some special symbols, such the begin-of-sentencee symbol <bos>, eos-of-sentence symbol <eos>, padding symbol <pad>, and so on. We found beneficial to treat these special symbols normal tokens in vanilla/ vanilla/reparant reparameterized absorbing diffusion (and thus these symbols can be noised), but this treatment leads to much worse performance in vanilla reeerrpaaammmerizeed multinomial diffusion.
We also adopt conditioned training (details in Appendix G) to further improve the model, which leads to consistent improvements upon vanilla training. Its effect is ablated in Table In particular, conditioned training leads to almost 2 BLEU improvements over vanilla diffusion processes but the gain becomes marginal for reparameterized variants.
The detailed configuration for the optimization hyper-paramenn listed Table 6.
E4
Decoding
Note that we train a neural network f(;;0) to approximate Xo, which is a softmax- normalized probability vector. There are several ways to decode a token from the prob- ability vector, such simply taking its argmax position performing sampling with temperatures T. Empirically, we find low temperature 7 = 0.1, or simply the argmax works well across tasks, and the argmax approach by default; Nevertheless, the diversity of generated sentences can be improved by adopting larger temperature as well.
Like common diffusion models, we use an exponential moving average (EMA) to track the model parameters with decay rate of 0.9999. We also average model parameters among the five last checkpoints for generation, following standard practices in machine translation (Vaswani et al., 2017).
26

---

Published as a conference paper at COLM 2024
For translation experiments, we use 5 length candidates, decode them in parallel, and select the sequence with the highest model score as the final output. For question genera- tion and paraphrasing, we follow DiffuSeq (Gong et al., 2022) to use MBR decoding with 10 samples to ensure a head-to-heas comparison. The candidates in MBR decoding are generated in the following manner: first selecting 3 length candidates, and then sampling 3,3, and 4 additional sentences for each length size, resulting in 10 candidates in total.
We also investigate several components of the adaptive decoding algorithm (64.3) and provide more implementation details below:
The top-k selection mechanism in Equation 8, which is deterministic by design, can also be made stochastic. In particular, instead of directly selecting those tokens with top-k largest scores, we first add Gumbel noise to the score St, of each token, and then fetch the top-k tokens with the largest perturbed scores. This is inspired by previous work that aims to sample multiple items from set without replacement (Vieira, 2014; Kool et al., 2019; 2020); however, this simple approach brings several benefits in that the selection of k tokens from the sequence could involve extra randomness, and this might be helpful for exploration during decoding.
U111,n is to indicate whether the token can Recall that during decoding, the role of (1)
remain in the denoised state, while D is used to denoise the token that is cur- rently noisy. In Equation 8, both of them would be set to as long as the n-th to- (2)) ken belongs to the top-k set. However, we observe that f-1,x and v=-ix can also
(1)
be generated differently. For example, one might adopt a more conservative ap- proach, where already denoised tokens rarely or never turn back to the noise. We
implemented strategy to achieve this by imposing more constraints over of") Ln (1))
(i)
where we set 1 = only when its cor- responding token score is not in the top-k set and indeed becomes smaller than the previous iteration. Intuitively, this means the denoised tokens should remain as de- noised most time, except that the Transformer model becomes less confident and requires re-prediction. This is one of many possible approaches to achieving such control, as our framework allows us to do such conditioning flexibly; we find this strategy works sometimes better than the vanilla approach, especially on IWSLT14 DE-EN dataset.
1z = Mea
Another important hyper-parameter during decoding is k, the number of tokens to be in denoised states at each iteration for our discriminative routing mechanism ($4.3). To ensure that the degree of noise decreases as the generation process proceeds, we schedule to increase from 1 to N monotonically as the diffusion step goes from T to 1. We set k to follow either a (cosine, linear) scheme based on the development set performance. The cosine strategy yields k = cos æt! NJ. while the linear variant gives k k= k NJ..
2T
Based our preliminary experiments, we discerned that while these com components indeed have an influence on task performance, their impact is relatively minor compared to the primary improvements (e.g,, reweighted training and adaptive decoding), as elucidated in the main paper.
To perform conditional generation, we delegate the full task of conditioning to the encoder-decoder architecture. That is, instead of designing complicated guidance to condition the diffusion probabilistic process, we treat the conditioning information as the input of the Transformer encoder. This simple strategy is found to work well in practice.
G Extension: Improved Training with Conditioning
Training discrete diffusion models usually involves heavy amount of randomness. For instance, at each training iteration, one has to sample a time step and corrupt a ran- dom subset of sequence tokens for denoising. To control the introduced variance, we adopt a simple yet effective conditioning strategy that uses multiple samples to perform training. The key idea is conceptually simple: we start with sampling two i..d. time
27

---

Published as a conference paper at COLM 2024
steps s,t ~ Uniform (without the loss of generality, we assume f). After that, we draw x; ~ g(2) (n) as usual, but condition the sample at step s by drawing from (xx/(x0) = Eg(a,/aa (x)) [1, ~ (xx,/xx, xo)) The losses (Equation 6) at step and are then estimated individually and averaged to obtain the final training objective. In case t,
we simply drop the conditioning and sample ~ (xs instead.
This method utilizes multiple samples to estimate the loss objective while remaining unbi- ased. To see this, note that
(C, L+) By log 9(x,- 1 1 X0) x0)
+ +log (
po x(s)
px 1x+)
E ( 188 log axxs 1 X0)
+ +log g(,; 1 xxx,
po(xx-1(xx)
70(x4-1123)
log 9xss- (xs,
log 9 9 Xx,, x0), xa)
xx 1|x3s + E q 1x
po 11xx)
(g Xo) || po ( [xs)]]
F9(x))2)) [KI( x0) || Po(x; 1 [xx])]]-
This conditioned training brings several benefits. On the one hand, it introduces explicit coupling between X, and xt, which can be seen and constrains the degree of randomness while still maintaining unbiasedness; on the other hand, as we deal with samples from the simulated backward transition q |x,,x)) xx) instead of 9 (x, (xo), this formulation aligns better with the generation process. In practice, this technique can be applied to most existing diffusion processes, only amounts to double the batch size within single model forward pass, and consistently brings large empirical improvements over vanilla discrete diffusion baselines (Table 7). However, the gains become marginal when switched to our reparameterized variants. We hypothesize that this is due to insufficient training in vanilla discrete diffusion models, which is already alleviated in our improved training scheme.
application of Rao-blackwellization
H Additional Experimental Results
H.1 Additional Experiments For Question and Paraphrase Generation
Table presents the comparison between text diffusion models under different number of candidate samples. We notice that DiffuSeq benefits slightly more from large sample sets (e.g,, when the sample size m increases from 1 to 10) than RDMs. We attribute this to the possibility that adding Gaussian noise to token embeddings in DiffuSeq might lead to more diverse samples. This helps make better use the MBR decoding, indicating that there might be room to improve RDMs to leverage multiple decodes. Nevertheless, RDMs still achieve better performance than DiffuSeq across both cases of single and multiple samples. Note that due to the limited computation resources, our reproduction of DiffuSeq (Gong et al., 2022) adopts a smaller Transformer model with around 36M parameters (the same as our setting) and runs with a smaller batch size of 256, thus resulting in slightly worse results than those reported.
H.2 Additional Experiments for Runtime Comparison
Table 9 compares the decoding runtime between RDMs and prior non-autoregreesive baselines, namely CMLM (Ghazvininejad et al., 2019). Note that both CMLM and RDMs are implemented with the same codebase fairseq (Ott et al., 2019), and the statistics are calculated as the wall time to decode the entire WMT14 EN-DE test set on one NVIDIA GeForce RTX 3090 GPU with 50 batch size and 16 iteration steps, averaged by 10 runs. Under this setting, we observe that the primary factor affecting decoding runtime among autoregressive baselines and our diffusion models is the number of Transformer decoder calls.
28

---

Published as a conference paper at COLM 2024
Algorithm 3 Training RDMs with Conditioning
neural network f (-; 0), data distribution Paata (No,1:N), and specified reweighting scalar A, As-1. Output: model parameters 0. repeat
Input:
Draw X0,1:N ~ Pdata (X0,1:N);
Draw Uniform .,....,.
Draw f & Uniform (1....,) T));
Swap and if necessary that < t;
for = 1,2, ...,, do
Draw Xt, (00,)
Let ,1, -x
if = then
Draw Xs,1 ((5,, No.));
else
Draw Xs,1 ~ q(x,,n Ne No,a);
end if
Let bs,n 1 N
end for
(,) = - 12 1 (1 (1-b b 0 log f (Ni,ni 0);
N
2 x log (xs,ni 0); Compute C(0) 1 (0) + (0));
(3) = - E
Minimize (0)) with respect 0;
until converged
Task Model
BLEU
ROUCE-L1
BERTScore
Dist-11
Transformer base GPT2-base
0.1663
0.3441
0.6307
0.9309
GPT2-large FT
0.1110
0,3215
0.6346
0.9670
GPVAE-TS
0.1251
0.3390
0.6308
09981
Q6
DiffuSeq
0.1731
0.3665
0.6123
0.9056
DitfuSeq' (m
RDM-absorbing" (nu
0.1699
0.3517
0.6286
0.9098
RDM-multioomial (m 1)
0.1768
0.3539
0.6305
0.0811
DiffuSeq" (w 10)
0.1569
0.3561
0.5945
099622
RDM-absorbing (m=
0.1791
0.3565
0.6393
0.9202
RDM-muulinomiall 10)
Transformer-buse
0.2722
GPT2-base FT
0.1980
0.5212
0.8246
0.9798
GPT2-large FT
0.2089
0.54115
0.8363
0198199
GPVAE-15
NAR-LevT
0.2268
0.5793
0.8344
0.9790
DiffuSeq
0.2413
0.5680
0.8365
0.9807
COP
DiffuSeg" (m=1)
0.1845
0.5284
0.7936
0,9739
RDMMabbottbing' (m=
0.2336
0.5789
0.8374
0.9805
RDM multinomial (m 1)
0.2291
0.5725
0.8366
0.9802
DiffuSeg' (w 10)
0.2371
0.5835
RDM absorbing (m 10)
0.2510
0.5945
0.8472
0.9849
RDM--multnomial" (m 10)
0.2498
0.8466
0.9817
Table 8: Comparisons among different text generators on and QQP tasks. Numbers taken from Gong et al. (2022). denotes results due to our implementation. denotes the number of samples used for MBR decoding, RDM variants are run with 10 iterations.
H.3 Additional Experiments for Open-ended Text Generation
In this section, we further explore the generative capabilities of RDMs in open-ended text generation. In particular, we conduct experiments on the Wikitext-103 dataset (Merity et al., 2016) from the Wikipedia domain, and recruit the following metrics for automatic evaluation according to prior research open-ended text generation (Li et al., 2022a; Su & Collier,
29

---

Published as a conference paper at COLM 2024
CMLM
RDM-absorbing Runtime
RDM-multinomial Runtime
Iteration
BLEU
Runtime
BLEU
BLEU
2
19.73
13.4s
21.00
12.7s
21.43
14.4s
4
22.91
17.1s
24.26
18.2s
24.05
18.1s
10
24.89
32.2s
26.96
31.5s
25.63
34.7s
16
25.00
44.7s
27.58
44.9s
25.64
46.8s
Table 9: Decoding runtime comparison between the non-autoregressive baseline CMLM and RDMs.
Model
Iteration
Diversity(%)
MAUVE(%)
Coherence
Autoregressive LM
n.a.
94.07
95.71
-4.4
16
98.04
47.75
-7.04
Absorbing Diffusion
64
96.93
64.61
-6.59
100
97.01
75.70
-638
97.32
62.32
-6.04
RDM-absorbing
96.84
79.14
-5.68
100
96.80
91.66
-5.15
Table 10: Automatic evaluation eval results on Wikitext-103 with different text generation models.
2022): Diversity, which measures the generation repetition at different n-gram levels; 2) MAUVE (Pillutla et al., 2021), evaluating the distance of token distributions between the generated and human-written text on the test set; and 3) Coherence, calculating the average-token log likelihood under a well-trained language model, which is set to OPT-2.7B (Zhang et al., 2022). We refer readers to Su & Collier (2022) for more technical details of these metrics.
We train three different models for comparison: auto-regressive language models, vanilla discrete diffusion models, and our RDMs. All of these models have approximately 430M parameters and are trained with 100k steps on the Wikitext-103 training set. Both auto- regressive language models and discrete diffusion models here adopt the same decoder-only Transformers following the Llama architecture (Touvron et al., 2023), except that discrete diffusion models remove the use of causal masks self-attention blocks and introduce an additional lightweight time-step embedding for proper conditioning. During training, the maximum sequence length and the batch size are set to 256 and 128, respectively, where shorter sequences are packed together. The Adam (Kingma & Ba, 2014) optimizer is used, and the learning rate is set to 3e-4 with the cosine scheduler. To facilitate evaluation on open-ended generation, generation of different models on test prefix prompts with a fixed length of 32. We limit the maximum generation length to 256 and truncate the generated output for each test case to the first 128 tokens for subsequent evaluation. For diffusion models, we the initial sequence length to 256 and truncate all content after the first <eos> token upon the iterative process finishes. For all models, we generate samples at the temperature of 1.0 by nucleus sampling (Holtzman et al., 2020) with top-p 0.95. Table 10 demonstrates the comparison among autoregressive language models, vanilla discrete diffusion models, and our RDMs in the task of open-ended text generation. We observe that while discrete diffusion models generally lag behind auto-regressive LMs, RDMs effectively reduce the gap, scale well with the number of iterations, and achieve competitive performance with auto-regressive LMs while exhibiting greater generation variety. Generation examples can be found in Table 11.
follow previous practices (Li et al., 2022a) and condition the
H.4 Additional Ablation Study For Translation Tasks
This section presents additional plots (Figure 3) that visualize the effect of different compo- nents in our model.
30

---

Published as a conference paper at COLM 2024
Model
Decodes
The route of what became US was used as part of two Indian trails before European settlers came to the UP, and as part of the Michigan segments of the Great Northern Railway and Chicago Railway The various segments of the UP were later often referred to other western Ohio routes such as the Mid @-@ Continental Route, @-@ 280 and Western Interstate route, which went through eastern Ohio into eastern Ohio near Knolls Creek.
Autoregressive LM
The route of what became US 2 was used as part of two Indian trails before European settlers came to the UP, and as part of the Michigan segments When the current Detroit segment was completed, both in 1956 and 1973 and removed from the state. .
Absorbing Diffusion Steps
The route of what became US 2 used part of two Indian frails before European settlers came the UP, and as part the Michigan segments of this section, it is included in the 1930 State Highway construction portion that exceeds only generallyat 4 @ 5 million in 1935. In January 1936, another state highway was created. The Big Pine Highway flew by DVP was so named State Highway 7.
RDM-absorbing- 64 Steps
Table 11: Generation examples of open-ended text generation on Wikitext-100 with different text models. The underlined text denotes the prefix prompt for generation.
ty
35
22
24
Devnding
Decsding
Exrodien
Exradonn
(a) WMT16 EN-RO dataset.
(b) IWSLT14 DE-EN dataset.
Figure 3: The ablation study of improved training and decoding strategies for both absorbing diffusion and multinomial diffusion WMT16 EN-RO and IWSLT14 DE-EN test sets.
H.5 Extended Qualitative Analysis
This section provides more comprehensive qualitative analysis of different diffusion models, including several generated samples as in Tables 12 to 14.
Multinomial Diffusion Does Not Decode Iteratively. As presented in Tables 12 to 14, multinomial diffusion finishes the generation of most sentences the first iteration and remains unchanged afterward, despite multiple iteration steps being allocated.
This unexpected behavior is due the formulation of its original backward process, which is of the form as Equation 14 (copied here for convenience),
po(x; 1/x:)
a4x ① (( B1, a)-1)x + {1 Bf) + _ Bt) a1-1)
axx; f(x;:))))))))))))))))))))) + & a1)
Note that f(; is softmax probability vector output from Transformer model. At the initial iteration, a; is very close to zero, and the Transformer prediction f(:;0) has the chance to come into play and denoise to certain degree. But when the process moves onward, a; becomes larger, which will soon make the first term dominate significantly over the others since all the other terms scaled down by 1/K. Since the vocabulary size K is usually
31

---

Published as a conference paper at COLM 2024
Source: have only 2 months for my a ept examss how do prepere? Reference: want to crack ca qpt in months. how should ituuyy?
Decodes
<M> <M> <Ms <Ms cMs <M> <M> <M> <M> <M> eM> <M> eM> <M> <M>
Aboobing
<Ms <Ms <Ms eMs eMs ca eMs ca cMs cMs ca <M> <Ms <Ms <Ms
<Ms <Ms <Ms eMs <Ms eMo <M> <M> <M> <Ms <Ms <Ms
<M <Ms <Ms <Ms <Ms ca-ci qp <Ms oa <Ms <Ms exam <Ms
o cMs can <Ms prepare <Mo ca- ca q <Ms ca eMs til exam?
how prepare ca- qp
qp #itesam?
30M 1.M.mmddliommal Multioonial RUMabsoonng
<M>
<Ms <M> <M> <M> <M> <M>
how <M> i <M> <M> <M> <M> <M> <M> <M> <M> <M> <M>>
how <M>
for ca cMs tit <Mo <Mo <Mo <Ms eMo?
how <M> prepare for ep lift <M> eM> <M> months months?
how <M> prepare for ca op #tl exam two months <Ms>?
how con i prepare for ca qp hift exam in two months left?
glossy [unused4t8] raymond manga subjective questioning suriname mesonic listen explored
how prepare ca op lift months?
how can prepare for ca cp A# months?
how can prepare for
fift months?
how prepare for op iift months?
how can prepare ca qp att months?
consonants 49nin leading elegance 406 173 militant teams #tnin dyke thee seafood
how residues #4lighting sentences malaysian jenkins remembers transatlantic universite 48rp monarch?
how eyril malaysian jenkins geldberg transatlantic relationships pursuing? how can chu for ca fashionable #it exam in clerks months?
how can prepare for ca op lift exam in 2 months? ?
how prepare
op Aitt exam in 2 months? ?
defective therehy evaluation michaels fragments primal electrically aground hostilitiest
simulcast candidacy #sbner [unused106] #Biide subgenus dangerously sincerity resolving migrated menon #tlase*
100
westphalia #Stracted universite sterly releoned neglect showcased [unused/524] sladet
souze electronically compliant gerard priority lownships #ineo hidalgo [unused574]] ;
500
spikes peplide stales horneo makeshift mot rebelled neglect textual 1899 crasmus publishes
reduces griffin #Ruee bukit makeshitt moi #1slow mibridee how ministries?
1000
i [unused562] to gazing monterrey makeshift ca wastewater norton, how ministries can!
DXiluSeg
i [unused582] to gazing monterrey makeshift ista norten. how ministries 1
1002
0 [unused562] to gazing monterrey makeshift ca iata norton, how ministries can
[unused582] to gazing monterrey makeshift ca ista norten. how ministries
1004
0 [umused56]] to gazing monterrey makeshift ca iata norton, how ministries can norten. how ministries 0 [unused58]] to gazing monterrey makeshift ca iata norton, how ministries can
[unued5822 to gazing monterrey makeshift
1006
[nused5822 to gazing monterrey makeshift ista norten. how ministries 1 [unused562] to gazing monterrey makeshift ca iata norton, how ministries can 1
1008
1009
[unused582] to gazing monterrey makeshift lata norton, , how ministries can
1250
o want to prepare thcchi my ca glove heman rouen how synthesized can [umused2201] thyya exam?
1500
i want prepare for my ca
how transvall can warmed #Ayya exam?
1750
prepare for my ca ep exam i want to prepare for my ca op exam, how might can get exam?
yun can get
2000
Table 12: A snapshot of all iterations for qualitative samples of test paraphrases generated from different diffusion models on QQP dataset. & texts are truncated fit into the table. Words are in lower case. <M> stands for mask states, and ### denotes the sub-word tokeniza- tion artifacts.
large in text generation tasks (usually larger than 10K), this would make all the other terms very close to zero. In this case, the backward transition distribution degenerates to
(x(x)-1xx) axx; @ f(x;;) X1.
xxx f(x;; 0)
That is, what multinomial diffusion does after the initial steps is merely copying previous states, and hence the sequence mostly remains unchanged. The only chance for the multi- nomial diffusion processes to decode is the initial stage; after that, the model would get stuck in the current state and cannot escape. This explains why multinomial diffusion does not behave like typical iterative processes.
Our reparameterization does not suffer from these issues. Thanks to Equation 2, the developed reparameterized formulation alleviates the need to normalize all terms together, instead, it divides different terms into two cases, which are then normalized separately. This avoids the possibility that different terms are affected by their relative scales. The resulting behavior is much more expected and leads to better generation quality.
32

---

Published as a conference paper at COLM 2024
Source:
how can one increuse concentration?
Reference: how improve my concentration?
# Iter.
Decodes
<M> <M> <M> <Ms <M> <Ms <Ms <M>
Absorbing
<M> can increase <M> <M> <M> <M>
how can increase concentration <M> <M> <Ms
how can increase concentration in studying <M> how can increase concentration studying
how can increase concentration in studying?
RDM abcorbing
<M> <M> <M> <M> <M> <M> <Ms <M>
<M> <M> <M> <M> <M> concentration? ?
how <M> <M> <M> my concentration ?
how <M> <M> increase concentration?
how <M> increase my concentration?
how can increase my concentration?
#itly distances outline #icera khmer curvature question ##1l
3DM-multnmmma Mallinonial
how can improve focus in concentration?
how can improve focus concentration?
how can improve focus in concentration?
how improve focus concentration?
how can improve focus in concentration?
lungs #idown intensity cortes #eldenn oldies
worker blurted i @8kka caledonia concentration Hivb
how A#kal my concentration #Avb
how trait increase my concentration
increase my concentration
how do I increase my concentration? ?
skeptical coli #uzam gael crika calves wharf [umused791] #lpta vhí Htkley adoptive
encompassing hesse informally campos cosmopolitan postmaster stabilization realised F
100
thump haitian i #faanvv xiv 4#] norris illuminated #thad kilometers disagreed [unused730jt fatal currelated trenton i AWamov exhibits AH] scandinavia 1934 plaza leveled 910
250
500
cessna J perez newark? venezuelan regeneration 283 zhejiang #thectares [PAD]=
750
johanna cessna perez shriek [PAD] [PAD] [PAD] rahman [PAD] [PAD] [PAD] [PAD] postmaster!
1000
johanna 730 improve terminals?
DiffuSeq
johanna 730 improve terminals
1002
johanna 730
: improve terminals?
1003
Johanna 730 improve terminals
1004
johanna 730
improve terminals?
1005
johanna 730 improve terminals?
1006
johanna 730 : impruve terminalss
1007
Johanna 730 | improve terminals?
1008
johanna 730 improve terminals?
1009
Johanna 730 improve terminals?
1250
how do improve concentration
1500
how do improve concentration?
1750
how do I improve concentration? how do i improve concentration?
2000
Table 13: A snapshot of all iterations for qualitative samples of test paraphrases generated from different diffusion models on QQP dataset. & texts are truncated to fit into the table. Words are lower case. <M> stands for mask states, and ## denotes the sub-word tokeniza- tion artifacts.
The Slow Convergence of Continuous Diffusion. contrast to discrete diffusion models that can perform generation in 10 steps or fewer, continuous diffusion usually requires thousands of steps to decode a decent sample. We hypothesize that this is due to two reasons: (1) the noisy and slow Gaussian diffusion over token embeddings by design; (2) furthermore, many diffusing steps are required to emit a significant change over token states due to the rounding operation. We provide empirical evidence for our hypothesis by zooming in to inspect the generation process. As can be seen in Tables 12 and 13, many consecutive steps in continuous diffusion (1000-1009 iteration) do not modify the decode at all, even when it is not converged yet, leading to a potential waste of computation.
Vanilla Absorbing Diffusion Cannot Fix Previous Errors. While vanilla absorbing dif- fusion performs decoding more steadily, it also suffers from some issues. As shown in Tables 12 to 14, since all tokens are predicted independently conditional on the source input, there is some chance for the model to decode multiple identical tokens simultaneously. However, in vanilla absorbing diffusion, such decoding errors cannot be fixed. To see this, note that its backward transition formulation can be written as Equation 10, which is copied
33

---

Published as a conference paper at COLM 2024
Source: alleine dieser flughafen hat cine fääche von 100 quadratkilemetem. Reference: this airport alone covers more than 100 square kilometers.
Iter.
Decodes
<M <M> <M> <Ms <M> <M> <M> <Ms <M> <M> <M> <M> <M> <M>
<M> <M> <M> <M> <Ms has an an <M> <M> <M> miles <M>
2
5 <M> <M> <Ms <Ms <M> has an an <M> of <Ms <M> miles <M>
8 <>>> <Ms airi# <M> <M> an an <M>
<M> miles <M-
Abcorbing
4
9 <M> <M> airit <M> <M> has an an <M> of <M> square miles <M>
8 <M> this aiett port alone has
<Ms of <M> square miles <M> <M> <M> square miles <M> 9 <M> this sirtt port alone has an an <M> of <M> square miles.
5 this airlif port alone
7
8
<M> this nirtif port alone has
<M> 100 square miles.
9
<M> this airtt port alone has an an <Mo
square miles.
10
2 and this airti port alone has an arca of 100 square miles.
0
5 <M> <M> <M> <M> <M>
<M> <M> <M>
<M>
1
a <M> <M> aint <M> <M> <M> <M> <M> <M> <M> square <M> <M>
2
<M> <M> airtil <Ms <Mo <M> <M> <M> <Ms <M> square <M>
RDM RDM- absorbing
3
<M> <Ms aid <M> alone <M> <M> area <M> 100 square kilometers.
4
2 <Ms <Mo airtt port <M> <Ms an eMs of <M> square kilometers.
a <M>
aiti <M> <M> <M> <M>
of 100 square kilometers.
6
9 <M> this sirtit port <M> <M> an area of <M> square kilometers.
a <M> this aiett port alone <M> an area of 100 square kilometers.
a this sirlil part <M> has an area
square kilometers.
9
a <M> this zirti port alone has an area of 100 square kilometers.
10
this airit port alone has
100 square kilometers.
D
o cher spending deshf vagina drin production milibh invenitl primikti openitt fruiheit sit schliiswel search alone alone airte airft port has area of 100 square miles
2.
o alone alone airif airkt port has area of 100 square miles.
Multinomial
3.
o alone alone airl airli port has a area of 100 square miles.
4
alone alone airtel airtt port has
of 100 square miles.
alone alone air#t air#t port has a area of 100 square miles.
alone alone airtit airtil port has a area of 100 square miles-
alone alone aire airt# port has
of 100 square miles.
8
o alone alone airte airtil port has a area of 100 square miles
9
o alone alone airet air# port has a
of 100 square miles.
10
alone alone airk airk port has area of 100 square miles.
0
o beschreiben denkit architect mittleren words alism groutt hilft atoms pus hottt jahrittt entilt ballet generally o expe## standing nahme cled
katastropa* bares tion later colle## haufen 100 anstatt zy
2
a cognitive standing nattirlich cled ution ity bares an later austti informatt 100 cognitive standing llig port wieder oth has an later erhalten seal 100 square kilometers..
RDM-moltaenni
9 crime standing airth port spending imagth has area incredible
square prototypht..
5
o crime standing airé# port alone psychitl editt an area oder of 100 square prototyp#t
starke standing airli port alone psychit! armut
out of 100 square kilometers.
starke that airiit port alone psychiff armut area out of 100 square kilometers.
8
o starke that airhh port alome has armut an area out of 100 square kilometers. and that airtt port alone got
100 square kilomelers.
10 o and that airti port alone has got an area out of 100 square kilometers.
Table 14: A snapshot of all iterations for generated translates from different diffusion models on IWSLT14 DE-EN benchmark. Words are in lower case. <M> stands for mask states, and ## denotes the sub-word tokenization artifacts.
here for convenience,
(1 1-1--- f(x:)) +
1-at-1 T R; Inoiser
if [M]
px(x:-1
Xty
if x; # [M].
Under this backward formulation, once a token is decoded, it will stay in the state thereafter and does not have the chance to be re-predicted again. As result, vanilla absorbing diffusion processes cannot fix previously made errors.
This issue can be alleviated by RDMs, which employ more generic formulation as follows,
1 x + (1 (1- 1-2(2) 9noiser
pe( 0
if b; 1
=
1i fxx: 0) + (1-2,)) Inoise (x:), if b = 0.
(2)
Here by a binary variable indicating whether x; denoised or not, and 0 can be either 1 or 0, depending on the strategy ($4.3). Therefore, in RDMs, we can allow decoded tokens to be rolled back to noisy states by setting o("1 0 (e-g., these repetitive tokens might receive lower model scores than the others, which can be recognized as low-confidence outputs in Equation 8). An example can be found in Table 12, where the decoded repetitive tokens months months at 3-th iteration are then re-masked at the next iteration.
(1)
34


Reviews:
[{"review_id": "ZMq5t7Nsx5", "reviewer": "Reviewer_dJkk", "summary": "This paper presents a reparameterization of discrete diffusion that can be applied on top of existing diffusion architectures. In this work, the authors use it train diffusion language models. The primary contribution lies in rearranging the term q(x_{t-1} | x_t, x_0) that allows defining it as a sum of two terms: one involving staying at the current token with some probability if it is close to the target, and the other simply adding noise at the current step. Based on this observation, the authors redefine the training process, and derive a loss function which they show is similar to a cross-entropy based language modeling loss. The resulting sampling algorithm requires much fewer iterations than baselines.\n\nThe authors train with this approach, discrete diffusion models with two kinds of noise formulation (namely multinomial and absorbing). On translation, paraphrasing, and question generation. Analysis shows that this model is much faster than other diffusion-based baselines.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "Thank you for your thoughtful and constructive feedback on our paper! Below, we provide our responses to the points mentioned in the review:\n\n> Q1: Several diffusion-based baselines are missing [1,2]\n> \n\nA1: We appreciate the suggestion to include a broader set of baselines for comparison. However, the baselines referenced\n\n- [1] start fine-tuning from pretrained language models (e.g., RoBERTa) and use much more inference steps (e.g., 1000 steps), while our approach starts from scratch and decodes within 25 steps.\n- [2] generate a substantially higher number of samples (up to 50 to 500) for selection to evaluate the task performance, whereas our method uses at most 10 samples. These differences in setup make it challenging to perform a direct, fair comparison to these baselines.\n\nWe appreciate this feedback and will address these points in the revision.\n\n> Q2: There is no performance gain over autoregressive models.\n> \n\nA2: It is worth noting that most non-autoregressive text generation models (including most diffusion models) usually lag behind conventional autoregressive baselines a lot in terms of performance. However, our RDMs still exhibit promising results and effectively bridge this performance gap to auto-regressive models. In addition, the RDM family offers greater flexibility in text generation, such as faster generation with fewer decoding steps (Figure 2b) and non-autoregressive generation (e.g., Tables 4, 11, 12, 13, and 14).\n\n> Q3: In addition, a general weakness of discrete diffusion models is they do not allow adding control via guided diffusion.\n> \n\nA3: While it is true that discrete diffusion models currently do not allow adding gradient-based control, these control signals can be directly materialized into the context (similar to the approach used in DiffuSeq [3]). This is analogous to prompting in using instruct-tuned language models, with the added advantage of being insertable everywhere in the sequence thanks to the non-autoregressive nature of diffusion models.\n\n[1] Mahabadi, Rabeeh Karimi, et al. \"Tess: Text-to-text self-conditioned simplex diffusion.\" *arXiv preprint arXiv:2305.08379* (2023).\n\n[2] Wu, Tong, et al. \"Ar-diffusion: Auto-regressive diffusion model for text generation.\" *Advances in Neural Information Processing Systems* 36 (2024).\n\n[3] Gong, Shansan, et al. \"Diffuseq: Sequence to sequence text generation with diffusion models.\" *arXiv preprint arXiv:2210.08933* (2022).", "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": "1. All theoretic contributions are non-trivial and interesting: the reparameterization, the new training loss, cross-entropy formulation. They have clearly explained, the method section is easy to follow.\n2. The improved decoding speed owing to needing fewer iterations is a huge benefit of this approach as diffusion models are known to be super-slow for language generation.\n3. The improvements in performance over other considered diffusion models are significant.", "reasons_to_reject": "1. Several diffusion-based baselines are missing [1,2]. A quick skim through these papers shows that these baselines offer better performance on translation, QG, and QQT than the proposed method. These approaches, however, are not discrete and the reparameterization in its current form cannot be applied to them.\n2. There is no performance gain over autoregressive models. In addition, a general weakness of discrete diffusion models is they do not allow adding control via guided diffusion. \n\n[1] TESS: https://arxiv.org/pdf/2305.08379\n\n[2] AR-Diffusion: https://arxiv.org/pdf/2305.09515", "questions_to_authors": "1. The tasks the authors consider are of reasonably short length (256), will the speed improvements hold for longer sequences?", "extra_scores": {"ethics_concerns_details": "NA"}}, {"review_id": "HNQg0KMsk2", "reviewer": "Reviewer_6hQf", "summary": "This paper proposes to do discrete diffusion by explicitly modelling which tokens are noise and which tokens are correct.  At x_0 all the tokens are correct, and at x_T all the tokens are noise.  In between, they explicitly model the transitions to and from correct tokens and noise tokens (the v variables).  They derive a lot of math about these transition distributions and the associated token generation distributions, and show that it has some nice properties for training.  At generation time, they add an easy-first heuristic to decide which tokens should (stochastically) transition from noise to correct.\n\nOr, at least, that is how I understand it, which could be over-simplistic.  The paper is written in the opposite order, and I didn't read it backwards.\n\nThe empirical evaluations show consistent improvements when adding their methods to previous discrete diffusion models.  An ablation study shows that both the easy-first decoding strategy and the new loss function are responsible for improvements.", "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": "Thank you for your valuable feedback! We appreciate your positive remarks about the novelty and effectiveness of our approach. We also recognize the concerns raised regarding the presentation and clarity of our paper.\n\n- We will streamline Section 4 and add a more intuitive summary before detailing the formulated diffusion process. The discussion of training objectives will be moved to Section 4.2 to maintain a logical flow and avoid confusion.\n- Your note about the late mention of “diffusion over a single token” is well taken! We will fix the conflicts that lead to confusion and revise the wording to emphasize this concept earlier in the paper, providing a clear context before delving into the detailed description.\n- We will address the issue of scattered wording in the introduction of the main idea and rewrite this section to provide a more precise and intuitive explanation of our contributions.\n\nWe are committed to addressing these issues comprehensively in the camera-ready version. Thanks again for your feedback!", "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": "The idea is interesting and there are lots of nice derivations (which I didn't check).  Using an easy-first heuristic to do non-autoregressive generation is a good idea, and they propose a diffusion model which allows them to do that (which is not trivial).  They show strong improvements when they add this idea to other discrete diffusion models, and show that both the modified decoding strategy and the modified loss result in improvements, individually and together.", "reasons_to_reject": "It was very hard to follow the presentation of the model.  Diffusion is often complicated, but I think this was unnecessarily difficult to read.  Take for example section 4.3.  This section is supposed to be about decoding, but it spends a lot of time talking about training objectives.  Then it assumes that you know the ground truth.  Then it says that they compute the ground truth from the sampled v variables.  This is the second-to-last paragraph before the experiments, on page 6, and it was only at this point that I understood what they are trying to model.  Then I could go back and understand the paragraph before that (what I call the easy-first heuristic), at which point the paper started to make sense.\n\nAs another example of the poor presentation, on page 5 the paper says \"So far, we mainly consider the case of diffusing over a single token\", after 2.5 pages discussing the model without mentioning this fact.  At the end of section 2 they even say \"for each token\", while this section only makes sense \"for a given token\".\n\nGoing back to the introduction, I can see that there is a summary of the main idea.  But it is worded in such a vague ambiguous way that I couldn't understand it when I read the introduction.\n\nI think that the paper should really be rewritten before it is published.  It is possible to fix these issues for the camera-ready, but it would be a lot to expect.", "questions_to_authors": "Do you think that, in time for the camera-ready version, you can add a precise but intuitive explanation of each contribution before going into the details?", "extra_scores": {}}, {"review_id": "bWhiC3GxTC", "reviewer": "Reviewer_8R7A", "summary": "The authors suggest a reparameterized discrete diffusion model to improve the performance of diffusion models in natural language processing. The proposed reparameterization creates a more effective training as well as a more effective sampling of the model.\nThe authors evaluated the proposed method on machine translation, question generation and paraphrasing.\nUsing the proposed method, the authors could significantly improve the performance of existing diffusion models in terms of translation quality. However, the comparison to autoregressive models is lacking recent advances. The model is compared only to baseline transformer model from 2017 and not to state-of-the-art models (e.g. submitted to WMT).\nThe authors nicely investigate the influence of the different training and decoding methods independently. Also the influence on the speed is shown. However, it is unclear why the proposed model with 20 iterations is faster the baseline one with 10? Furthermore, the authors compared to a GPT-2 base model, but not to the compared transformer baseline from the qualitative results.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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": "Thank you for your valuable feedback! We appreciate the recognition of our work's potential in improving the quality of diffusion models for text generation.\n\n> Q1: However, it is unclear why the proposed model with 20 iterations is faster the baseline one with 10? Furthermore, the authors compared to a GPT-2 base model, but not to the compared transformer baseline from the qualitative results.\n> \n\nA1: The baseline with 10 steps is slower than our model with 20 iterations due to additional intermediate processing steps required by the baseline model (DiffuSeq). Additionally, we have compared our model to transformer baselines in our main translation results, as detailed in Table 1 of our paper.\n\n> Q2: The evaluation of the proposed should be improved with respect to the autoregressive baselines.\n> \n\nA2: We demonstrate that our discrete diffusion models (RDMs) not only achieve competitive performance compared to autoregressive baselines but also offer greater flexibility in text generation. Our experiments demonstrate faster generation with fewer decoding steps (Figure 2b), and support non-autoregressive generation (Tables 4, 11, 12, 13, and 14).\n\nIt is also worth noting that most non-autoregressive text generation models (including most diffusion models) usually lag behind conventional autoregressive baselines in terms of performance. However, our RDMs still exhibit promising results and effectively bridge this performance gap. \n\nWe hope these points effectively address the concerns raised and highlight the strengths and contributions of our work.", "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": "The authors present an interesting idea to improve the quality of diffusion models for text generation\nThe idea is evaluate on several tasks and shows good performance and significant improvements in quality", "reasons_to_reject": "The evaluation of the proposed should be improved with respect to the autoregressive baselines.", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: In this paper, the authors derive an alternative yet equivalent formulation for sampling from discrete diffusion processes, leading to a family of reparameterized discrete diffusion models. Extensive experiments on machine translation and text generation demonstrate significant improvements over existing diffusion models. The major concerns from the reviewers are: (1) a lack of comparison with several diffusion model baselines; (2) performance is not better than autoregression-based language models; and (3) the need for improved presentation. The authors have committed to making the necessary revisions to address all these concerns. I recommend acceptance, provided that all promised revisions are incorporated to address the concerns outlined above.
Decision: Accept