Fast Sampling via Discrete Non-Markov Diffusion Models with Predetermined Transition Time
Authors: Zixiang Chen
Huizhuo Yuan
Yongqian Li
Yiwen Kou
Junkai Zhang
Quanquan Gu
Venue: NeurIPS 2024 poster (2024)
Keywords: discrete Diffusion
sampling acceleration
text generation
Primary area: diffusion_based_models

Abstract: Discrete diffusion models have emerged as powerful tools for high-quality data generation. Despite their success in discrete spaces, such as text generation tasks, the acceleration of discrete diffusion models remains under-explored. In this paper, we propose discrete non-Markov diffusion models (DNDM), which naturally induce the predetermined transition time set. This enables a training-free sampling algorithm that significantly reduces the number of function evaluations (i.e., calls to the neural network), making the sampling process much faster. Furthermore, we study the transition from finite to infinite step sampling, offering new insights into bridging the gap between discrete and continuous-time processes for discrete diffusion models. Extensive experiments on natural language generation and machine translation tasks demonstrate the superior performance of our method in terms of both generation speed and sample quality compared to existing methods for discrete diffusion models. Codes are available at \url{https://github.com/uclaml/DNDM}.

Fast Sampling via Discrete Non-Markov Diffusion Models with Predetermined Transition Time
Zixiang Chen Huizhuo Yuan Yonggian Li Yiwen Kou Junkai Zhang Quanquan Gu
Department of Computer Science
University of California, Los Angeles
Los Angeles, CA 90095 evankou, evankou,jjzhhngg qgubees wwwulees.ucla.ee... ucla.
{chenzx19, h22uan,,
Abstract
Discrete diffusion models have emerged as powerful tools for high-quality data generation. Despite their success in discrete spaces, such as text generation tasks, the acceleration of discrete diffusion models remains under-explored. In this paper, propose discrete non-Markov diffusion models (DNDM), which naturally induce the predetermined transition time set. This enables a training- free sampling algorithm that significantly reduces the number of function evaluations (i.e., calls to the neural network), making the sampling process much faster. Furthermore, study the transition from finite to infinite step sampling, offering new insights into bridging the gap between discrete and continuous-ting processes for discrete natural language generation and
diffusion models. Extensive experiments machine translation tasks demonstrate the superior performance of our method terms of both generation speed and sample quality compared to existing methods for discrete diffusion models. Codes are available at ltthhtt://// htops:///iit /ttptttttttttt//.//e/e/e.e com/ uclam1/DNDM
Introduction
Diffusion-bann based generative models, as first introduced by SSoh--Diccsstiin et al. (2015). have shown remarkable capabilities in generating high-quality samples across various domains, including im- ages (Ho et al. 2020, Song and Ermon (222)), audio (Chen et al.) 2020: Kong et al., 2020), and videos (Ho et al. 2022). The diffusion model utilizes an innovative approach comprising a forward process that gradually transforms training data into pure noise and reverse process that reconstructs clean data from the noise. Throughout the training phase, the model optimizes neural network by minimizing objective derived from maximum likelihood estimation. Once trained, the model can generate samples using various decoding strategies, including implicit dynamics (Song et al., 2020a), analytical processes (Bao et al. 2022). or differential equation solvers (Song et al. 2020b Liu et al.) 2022 Lu et al. 2022). In particular, Song et al. (2020a) introduced the denoising diffusion implicit model (DDIM), providing non-Markov and de-randomized version of the Denoising Diffusion Probabilistic Model (DDPM) (Sohl-Dickstein et al. 2015 Ho et al., 2020), which enables faster generation of high-quality samples.
Although diffusion models were initially introduced for both discrete and continuous-state spaces (Sohi-Dickstein et al., 2015), these studies have largely focused Gaussian diffusion processes in continuous-stee spaces. Recently, Discrete Denoising Diffusion Probabilistic Models (D3PMs) (Austin et al. 2)21) working in discrete-state spaces have gained increasing interest due to their applications in diverse areas such as text generation (Hoogeboom et al.) 2021b), medical record generation (Ceritli et al. 2023), and protein design (Gruver et al. 2024). These models, which are distinct from their Gaussian counterparts, employ discrete noises, such as the multinomial distribution, for diffusion processes. Very recently, Zheng et al. (2023) introduced reparameterized diffusion
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

model (RDM) that can improve sampling speed and sample quality in text generation tasks. However, their proposed algorithm is a training-basee approach. Compared with diffusion models using Gaussian noise, discrete diffusion models remain under-studied, especially regarding training-free sampling acceleration.
In this work, we introduce training-free approach aiming at enhancing the sampling speed of discrete diffusion models. This approach stems from a unique characteristic of discrete diffusion models: unlike continuous diffusion models, which typically employ Gaussian noise for data corruption (Ho) 2020b a). discrete diffusion models often use Austin et al. 2021 Zheng et al. 2023).
al. 2020 Song and Ermon 2020; Song et al.
categorical white noises (Hoogeboom et al. 2021b;
By delving into this spe- cial property, we develop a discrete non-Markov diffu- sion model, together with design of accelerated al- gorithm. Notably, this new sampling technique does not require any modifica- Non-Markov tions to the training objec- tive of diffusion models and is, therefore, training-free free. Our contributions are summarized as follows:
Table 1: Cross Comparison of Diffusion Models.
Continuous
Discrete
DDPM
D3PM
Markoy
(Sohl-Dickstein et al. 2015)
Austin et al. 2021)
DDIM
DNDM (Ours)
Song et al. 2020a
We propose discrete non-Markov diffusion models (DNDM), which naturally induces set of latent variables T, termed as the transition time set. This key feature enables us to develop a maining-free sampling algorithm that can accelerate a large family of discrete diffusion models. Importantly DNDM preserves the essential properties of the original discrete diffusion model: for any diffusion trajectory } starting from real data xo. provably maintains both the marginal distribution ((xx) and the conditional distribution q(xo ). Our method can accelerate the two most widely used discrete diffusion models: multinomial diffusion (Hoogeboom et al., 2021b) and absorbing diffusions (Austin et al., 202Tb. Similar to how DDIM introduces a de-randomized, faster sampling algorithm compared DDPM in continuous space. DNDM achieves acceleration through a predetermined transition time set in discrete space (See [able
Based on the predetermined transition time set T in DNDM, we design an accelerated sampling algorithm that reduces the required number of neural network function evaluations. In a standard T step discrete diffusion process, while D3PM, including Multinomial (Ho et al.] (020)) and absorbing state discrete sampling (Austin al. 2021), requires evaluating the neural network function T' times, our approach only requires [T[ function evaluations, where [T] is the cardinality of the transition set T. Moreover, [T] is provably less than T and approaches O(1) as T goes to infinity. We provide both theoretical analysis and empirical experiments showing that the improvement in the number of function evaluations (NFE) is significant. Notably, our algorithm is about 3x faster than baselines for = 50 and about 30x faster for = 1000 while preserving the sample quality.
To further illustrate the effectiveness of DNDM, we explore the limit as T - oo and introduce an infinite-step step sampling algorithm. With a pretrained neural network, can generate initial noise Xy and a transition time set T C [0, 1] with infinitesimal spacing, such that [T| = O(1). This enables the generation of the real data distribution with only [T] neural network evaluations. This study offers new insights into bridging the gap between discrete and continuous-time processes for discrete diffusion models.
Notation. We use [T] to denote the cardinality of the set T (excluding repeated elements). We use lowercase letters to denote scalars, boldface lowercase letters denote vectors, and boldface uppercase letters to denote matrices. The notation : N indicates the sequence from through N. The symbol q designates the real distribution in diffusion process, while p represents the distribution during sampling. With its success probability inside the parentheses, the Bernoulli distribution is denoted by Bernoulli-).. We further use Cat (x: p) to denote a categorical distribution over one-hot row vector x with probabilities given by the row vector p.
2 Background
In this section, we provide the background of discrete diffusion models. We begin by introducing the discrete Markov diffusion model, designed for handling categorical random variables. Specifically,

---

consider a diffusion model trying to generate distributions over discrete random variable x E R that is one-hot encoded with K categories, i..., can be chosen as one K categories, and for any k E [K] is categorized as k: if x aligns with the standard basis vector eμ: The sequence (xe represents how this random variable changes over time 0 S S T. starting from an X E IR. drawn from the real distribution qdata- In this paper, we focus on the two most widely used D3PMs: multinomial diffusion (Hoogeboom et al., b021b) and absorbing diffusions (Austin et al.) 2021).
Forward Process. During the forward process, the real distribution Qdata is gradually transformed into noise distribution named quoise. The transformation occurs through T steps, with T intermediate latent variables Xi.... Xr and update rules given by:
x = 1, + (1 by) We,
1 1=
Here b, is randomly drawn from a Bernoulli distribution with parameter 3r, denoted by by ~ (ernoulli(3)). and w, is randomly drawn from the noise distribution Quoises while for different / the samples are independent. In this work, we foeus on cases where the noise Queise can either a uniform distribution over the vocabulary {1, 2, ..,.,'K'' (Hoogeboom et al. 2021b), a point mass with all of the probability mass lying on an absorbing state (Austin et al. 2021]. Following this notation, the process in ① defines Markov process characterized by the transition kernel
(xx((x Cat Cat(xx; 3,x,-1 + (1 (u)iui
(2)
Moreover, the Markov chain property allows us to get samples Xox from Xy by multiplying the transition probabilities at each step as p(x xo) II: (xx It further leads to the following marginal distribution.
(xx x0) Cat (x 0x20 + (1 ar) Anoise)
where 02 = =1, determined by the sequence B, of our choice and decreases from
Reverse Process. Given the forward Markov process, the reverse process can be derived by Bayes' rule (Hoogeboom et al. 2021b Austin al., 202T Zheng et al. 2023). The conditional probabil- ity x Xo, x+) can be determined by g(,, Xg. x2) = g X X ( (xx)//(x)())))) Xxo). The reverse process be used for synthetic data generation by sampling from the noise distribution Inoise and repeatedly applying a learned predictor (neural network) pe (-1x,) parameterized by O:
Pe (XT)
Inoise (xT):
qo (x
2 g(xx-1|xe, Xo) (Ro) )dx
We note that the reverse process q(xx-1 Xo) is stochastic and thus requires function evaluation at every step.
Training the Neural Network. The neural network Pa (x) that predicts Ro is trained by maximizing the evidence lower bound (ELBO) (Sohl-Dickstein et al. 2015).
Po dx
log Po (x5) 2 E (g(x)r(x)) log
q(x1:r) (xo)
[x)) [log (xol x1
Σ t=2
EE Egt xx) (Xxe
By(xe mo) (L (xo) (oxo))llooo (xT()))),,
(5)
Here KL denotes Kullback-Liebler divergence and the last term Ey(xr (x,) KL(g(Xx) (xxoe////x)l///// (lmoise (x1)) ))
equals zero Building on this foundation, Aussin et al. (202T) introduced an auxiliary demoising objective, which refines the data predictions X. at each time step. Since this paper primarily focuses on reverse sampling, we leave detailed discussions of these losses to Appendix
3 Discrete Non-Markov Diffusion Models (DNDM)
3.1 Forward and Reverse Process
In this section, we introduce non-Markov process such that the joint distribution of (Xo: x,) remains the same as the one defined with Markov process in Section 2 The process aims to gradually
3

---

transform input data Qdata to the noise distribution Anoise through T' intermediate latent variables XI.... Xy with the following process:
X b + Jw,
(6)
where 6 is independently drawn from the Bernoulli distribution Bernoulli and is drawn from the noise distribution Inoise- The only difference between (6) and TT is that we replace we in T by w, which is time-invarian during the diffusion. Therefore, the process in ( becomes non-Markov since (x, Xi-1...... Xo) doesn't necessarily equals g (xx/\x,-1). The following theorem shows that the conditional distribution q (xx|xx) xx) remains unchanged.
Theorem 3.1. For the non-Markov process (6) we have
q(xe|x0) Cal (X:: - 0,Xo + (1 (noisn)))))
where == II 13g is specified to decrease from 1 to 0.
Using the Bayes' rule, we have q(xo|x,) [x,] x q(x, (x))) Consequently, the condtional distribution ((xo[xe) remains consistent with the one induced by the process process in (T). Therefore, neural network po (-)x)) trained by the Markov process in (T) remains applicable to our non-Markov
process (6) (see Appendix [ for detail).
Based on the discrete non-Markov diffusion model, we can give a simple characterization of the reverse process by introducing the transition time.
Definition 3.2. Transition time is the time that the token x, transition from Xo noise, i.e., 7 = min, (t]b,- =0 -}.
Remark 3.3. The concept of transition time has also been introduced in Hoogeboom et al. (202 Ia). However, Hoogeboom et al.) (2021a) restricts the transition time to be the first time of entering the absorbing state, which is only applicable to absorbing diffusion. Our definition is more general and applicable to discrete diffusion with various noise including multinomial diffusion.
Given the transition time r, the forward process reduces to:
X = 1(T > t)xo + 1(T S f)w,
which shows that the token will be a real token X before the time and will be the noise w after the transition time. Since token only get changed the transition time т, we can derive reverse process based on
x,- 11= t)x; ( # t)x:.
(
Therefore, the process in (8) de-randomized given transition time r. Specifically, after indepen- dently sampled transition times 7, X becomes deterministically known and fixed if we observe xo and x₁. It also worth noting that given Xo and т, the exact reverse process ( is Markovian, since
X solely depends Xo, Xy. Plugging
into 44) gives the generation process. We can prove the ELBO of the DNDM equivalent to the ELBO of the original process (5) up to some constant,
which further supports the neural network pe (-1 xx) trained by the Markov process in remains applicable to DNDM. (See Appendix B.3 for details).
Remark 3.4. 7 and 8 suggest that even though there are T distinct time steps, not every time in the range Tis crucial for capturing the process. Therefore, our primary focus should be on the most significant time step, i.e., the transition time enabling faster reverse sampling. We further note that although transition happens only at time t, the transition time is random, differs across runs, and covers the full range from 1 to T on average.
Remark 3.5. While [Song et al. 2020a) proposed non-Markov multinomial diffusion model in Appendix A, DDIM and DNDM are fundamentally different models when specialized to multinomial diffusion. DDIM'S discrete process remains stochastic at every step. even with deterministic noise scheduling. In contrast, DNDM achieves full de-randomization by pre-determined transition time т (Equation our paper). By sampling these transition times upfront, DNDM establishes predetermined transition time set that guides the sampling process, enabling deterministic evolution and faster sampling speed even under the same number of sampling steps, which not reported under DDIM framework. For detailed technical comparison, see Appendix B.

---

3.2 Accelerated Reverse Sampling
In this section, we demonstrate that sampling from DNDM can lead to accelerated reverse sampling. Although algorithm is quite general, we focus on text generation in the presentation.
In Section 3.1 we only consider the case of a single token x E R.K being one hot encoding of K' categories. In real applications, we are interested in generating a sentence with multiple tokens. So, we extend the terminology in Section 3.1 and we denote the sequence of tokens at t-th time step to be XtN I......... Xr,N] .]] where Xt,n is the n-th token and N is the sequence length. The noise will be added to each token sequence independently. Therefore, each token will have its own transition time defined in Definition 3.2 We denote the transition time for each token X,, to be Tn and further denote the transition time set T := [T Given the transition times Tn E T, our DNDM can now be extended to the sequence with multiple tokens
1,1 1 [T,, f) + 1 (T # t)x Vn [N].
(9)
Learning the Reverse Process. We first generate the transition times for E [M] then we follow (9) to generate the learned reverse process. Since X is unknown in the process, we use the neural network evaluation pe(-|x,) obtained in Section 3.1 to predict Xo.n. In detail, the noisy sequence X4,1:N is fed into Po (x,IN)) ) and the prediction tokens Xg.1.N (o are collected.
Transition time. Transition time, denoted by т. is crucial in our reverse process. This is because the reverse sampling becomes deterministic upon using (9). Each instance of transition time is random variable within the set {1, .,...... .T. Let's s assume it follows the distribution D,. Given the schedule {at 1 we can derive the distribution for D,.
Theorem 3.6. Each specific transition time Tn in Definition 3.2 is independent. Furthermore, they collectively adhere to the distribution D,, which obeys the rule PT, = t) = at-1 Qt--
discern that the nature of the diffusion model scheduler, or, clarifies the distribution of т. Take the linear schedule as an example, as given by Austin et al. (2021). the relationship is Ott a result, transition time distributes uniformly across each moment in the set (1...., T). Generally, if we express a as g(t/TT,, then we can simplify P(Tn, t) g((t 1)/T) gt/T"), which further refines to (1/T)) (t/T)) + o()TT). This indicates that transitions are more likely where (gll large.
From Theorem 3.6
I/T. This translates P(Tn = () = 1//T for every / in the range 1 to T. As
In practice, we observed that the shape of the transition time does not need to exactly match the theoretically predicted schedule Dr in Theorem 3.6 Algorithm [ works even if DD is unknown. In particu- lar, we can approximate the schedule with a Beta distribution by first sampling time t [0, 1] from Beta distribution, then ad- justing these samples to fit by multiplying by T and rounding the result obtain an integer.
Algorithm 1 Sampling From DNDM
Require: Trained prediction function po. Quoises Dr 1: for n = 1=...N. ...Noo do
2: Initiate each token XT,n Qnoise
3: Initiate the transition time Ty. ~ D,
4: end for
5: Collect transition time set T= [Tr 1N Inml
6: for t TT:==T... T... do
7: if T then
8:
Generate Xo,1:N from po(-Ixx,1.N) for n = 1.... ...NN do
Accelerated Sampling. According (9) a token X,- is updated only if step / is the transition time for the n-th token. If
9:
10:
Update x,- based condition of TM end for
11:
step / is not the transition time for any to- ken, the sentence from the previous step
12:
else
13:
Update X1-1,1:N = X1,1:N
14: end if
can be directly copied: X;-1.1:N = Xt,1-N-
As result, there is no need do fune- tion evaluation for the current step. Our attention, therefore, can be solely centered on the transition set T, necessitating function evaluations only for within T. For our method, when N fixed while - oo, the total NFE [T] will reach N. On the other hand, when is fixed and N - xo, the NFE T will reach T (See Theorem D. for detail). It is worth noting that the rego-segres diffusion model (ARDM) (Hoogeboom et al. 2021a) can also achieve at most N NFE when T = co. However, ARDM only focuses on infinite time steps, while our method here is
15:
end for
16: Return Xo.1:N
5

---

able to accelerate sampling for finite time steps. More detailed discussion and theoretical analysis can be found in Section[] where additional experiments also demonstrate that our DNDM achieves an NFE that is less than half of the original Markov sampling method for discrete diffusion.
By incorporating the forward process with different noises, Absorb, which accelerate the Multinomial and Absorbing sampling methods respectively. Recent works have demonstrated that the quality of samples can be enhanced by utilizing supplementary information derived from the neural network, (Ghazvininejad et al. 2019; Savinov et al. [02T]] Chang al. 2022 He al. 2022 Zheng et al. 2023). Our DNDM can also be improved using this idea. We call it a discrete non- non-Markov Diffusion Model with Top-k Transition Time (DNDM-k). Due to the limit of the pages, we leave the detailed Algorithm and discussion to Appendix
develop DNDM-Multi and DNDM-
3.3 Continous-time (Infinite Step) Reverse Sampling
In the context of continuous state spaces, continuous- taairuooou---eeeeee processes have been proposed to accommo- date algorithms that offer faster sampling speeds and enhanced sample quality Pollioeur-Martinng
iet al. [202]] Zhang and Chen 2022 Salimans and Ho [022 Chung et al. [022]] Song et al. [020bb] Dockhorn et all]2021) However. the application continuous time schemes discrete-state spaces remains largely unexplored. [Campblll et al. (2022) first developed a continuous framework for discrete-time diffusion for the Markovian process and randomized sampling. but not in our non- Markovian setting. In this section, we investigate the transition from finite to infinite step sampling, providing new insights into bridging the gap between discrete and continuous-time processes for discrete diffusion models.
Continuous-tinn Forward and Backward process. Recall that the forward process described in (6) can be sampled from X through the following process:
Xt, a + (1 aq Anoise
8
(10)
1=1
In the previous section, we are constrained to discrete time steps, where we must de- fine a maximum step, denoted by T. The values of x, are computed only for t
Algorithm 2 Sampling from DNDM-C
Require: Trained prediction function po. Quoises Dr 1: for n 1... do
1..... T. As a result, during the training process, it is only possible to predict Xo at these predetermined time steps. This constraint confines the computation of our reverse process exclusively to these fixed time stamps. To derive the continuous limit of (10). for each T we rescale (TO) to a diffusion process on [0, 1]. e.g.. XT 81.: Xu,n Xp, and Xt,n = Rt/T.n Therefore, when T > 00, Xt, represents the continuous process that has values at arbitrary& t [0.1]. 1]. If the choice of a for each T is scale-invariant, we can define a continuous function (tt) as the continuous a schedule of the discrete counterpar[] More specifically,
2: Initiate each token XT,n Qnoise
3: Initiate the transition time Tn ~ D, and order
them as Tn. < < Tny
4: end for
5: for k .... do
6: Generate Xu,1.N from po(-1xra, ( J:N; Tay)
7:
for = 1... do
8: Update Ximg-n based on condition of Tn
end for
10: end for
11: Return Xo.1-N
obtain
& = =())_0.. + (1 - a(t)) Qnoises 1 LE [0,
(11)
For the reverse-time process, we define the transition time set T := [ consistent with Theorem 3.6 and sample it from PTT, f) at'(t) (we always decreasing att)). With T defined, the updates to Xt,n only occur at {Ta ). Consequently, we arrange т, to obtain an ordered sequence Tug. where Tn, < Tng <... TAN- When omitting the infinitely many time steps between Tny and T 1 the resulting reverse process is then given by:
XTog n 1 = Tma-n No,n + 1 ( + TTg--1 XTa,,..
(12)
for all n E [N]. The detailed algorithm named DNDM-C is shown in Algorithm
2
If we represent with maximum step I' as (T()). the scale-invariin property states that ow = ax()). The simplest example of such an schedule is ar (1') - t/1', under which a(t) 1-

---

Remark 3.7. Autoregressive Diffusion Model (ARDM) (Hoogeboom et al., (021a) is discrete diffusion model built upon the autoregressive nature of data. ARDM is shown be equivalent to continuous-time absorbing diffusion model and thus provides a unique perspective for discrete diffusion. For continuous-time (? = oo) reverse sampling, both ARDM and our method achieve N NFES. Unlike ARDM which is limited to absorbing-ste
transitions, our method provides unified framework including both absorbing and multinomial diffusions, applicable to both finite time and continuous time diffusions. For infinite timesteps, [Hooeeboom et al. (2021a) also proposed an advanced parallelizing technique that can reduce NFE according to the log-likelihood, which we have not considered in DNDM-C.
4 Experiments
In this section, we evaluate DNDM and demonstrate its superior performance two types of tasks: conditional sequence-ro-sequenn
text generation (i.e., machine translation) and unconditional text generation. For the fairness of comparison, all the experiments conducted using single NVIDIA RTX A6000 GPU with 48 GB memory. Additional experiment details are provided in Appendix F
4.1 Conditional Text Generation
We evaluate DNDM's effectiveness on conditional text generation through machine translation tasks. Following Zheng al. (202)) we Byte Pair Encoding (BPE) (Sennrich et al. 2016) create shared vocabulary of words and subwords from both source and target languages. We implement our experiments using FairSeq (Ott et al.] 2019), which employs encoder-decoder architecture. The model uses bi-directional self-attention blocks without causal masking, allowing tokens to attend to both past and future positions during training and inference. The encoder processes the source text, while the decoder generates the target translation.
Datasets. We use the following three datascts to compare with the baselines for machine translation tasks: (1) IWSLT14 DE-EN (Cettolo et al. 2014), a dataset with German as the source language and English as the target language. It consists of 1 174272 examples (sentence pairs), and each of the validation set and the testing set accounts for 7283 and 6750 of the dataset; (2) WMT14 EN-DE (Bojar et al. (014)), which is an English-to- to---rman translation dataset consisting of 3967182 examples. Each of the validation set and the testing set accounts for 3000 and 3003 of the dataset; and (3) WMT16 EN-RO (Bojar et al.] 2016), which is English-to- to-Russian translation dataset consisting of 612317 examples. Each of the validation sets and the testing set accounts for 1999 and 1999 of the dataset. The vrain-vliidation-estt split is fixed across all experiments for all machine translation datasets to ensure fair comparison.
Performance Metrics. We use the BLEU score (Papineni et al., 2002) to evaluate the machine translation quality, where the BLEU score is calculated based on the similarity between the actual target sequence and the predicted target sequence. The sampling speed is measured by wall-clock time (in second).
The main baselines we are comparing with are RDM and RDM-k from Zheng et al. (2023). Here, we use RDM-k and RDM to denote the sampling method proposed in their paper with and without the usage of top-k selection for the token generation technique (see Appendix F for more details), respectively. RDM and RDM-k are applied to two previously proposed state-of- the-art discrete diffusion models: Multinomial Diffusion (Hoogeboom et al. 2021b) and Absorbing Diffusion (Austin et al. 2021).
Baselines.
Results and Discussion. Tables 2 and present the performance evaluations of our algorithms in machine translation tasks. Table presents results for multinomial diffusion, while Table 3 displays results for absorbing diffusion. Our reported time and BLEU scores are averaged over repeated experiments, except for the baseline RDM experimen""
From Tables 2 and 3 we observe that methods based on DNDM significantly accelerate the sampling process compared baseline diffusion models. This acceleration allows for greater flexibility in increasing the number of steps (up to infinity) without imposing a significant computational burden.
"Due to computational intensity, we did not repeat the 1000-step sampling for the RDM baseline. However, reproducing it was deemed unnecessary as the sampling time is largely stable across repeated experiments, and the precise averaged timing is not critical for demonstrating the speed improvement of DNDM.
7

---

In particular, more sampling steps lead to better generation quality (BLEU) at the expense of longer sampling time, as indicated in each column of Tables and 3] For RDM-based methods, generation time increases linearly with the number of sampling steps. On the contrary, for our DNDM-based -hased method, generation time only increases marginally (See Figure Section G.. As a result of the difference in the growing speed of sampling time with respect to sampling steps, the more sampling steps, the more speedup DNDM can obtain.
Continuous-ting time results, as the ultimate limit of increasing sampling steps, are presented in the last row of each dataset with the tag oc. Given that the results with 1000 steps consistently outperform those with 50 steps, we compare oo with 1000 steps in Table and 2an For IWSLT14 and WMT16, where the generation BLEU score relatively high, we observe consistent performance improvement of up to 0.3 in BLEU score when utilizing the DNDM-C algorithm, with the exception of a single case in the absorbing diffusion setting for WMT16 without the use of top-k selection. The performance gain of the continuous-time method on WMT14 is less significant, with both drops and gains. However, WMT14 itself has not reached a high level of performance, with BLEU score significantly lower than other datasets. In general, training WMT14 14 poses challenges across all diffusion models, including multinomial diffusion (Hoogeboom et al. 2021b), absorbing diffusion (Austin et al. 2021), and RDM diffusion (Zeeng et al. (2023), etc. We deter a more detailed discussion Finally, when compared with the results obtained with 50 steps, the performance of DNDM-C demonstrates improvement consistently. Furthermore, method (i.c., RDM or DNDM) employed, top-k token generation consistently outperforms vanilla methods. This approach enhances the BLEU score by approximately 1-2 points without introducing significant increases sampling time.
WMT14 to Appendix F.
note that regardless of the dataset the
Table 2: BLEU score comparison of multinomial diffusion machine translation benchmarks IWSLT14 DE-EN, WMT14 EN-DE, and WMT16 EN-RO. Below the dataset, we present the amount of data used to run the evaluation (sentences). The blue background highlights our algorithms, and the bold number indicates the best performance within each row and each setting (i.e., with or without top-k).
RDM-Multi
DNDM-Multi
RDM-K Multi
DNDM-&-Multi
Dataset
Steps
BLEU
Time (s)
BLEU
Time (s)
BLEU
Time(s)
BLEU
Time (s)
25
31.26
166.9
30.95
52.9
32.82
161.9
32.30
52.6
50
31.50
328.6
31.45
83.9
32.82
321.2
32.80
93.2
IWSLT14
1000
31.69
6308.9
31.82
191.3
32.64
6321.3
33.15
191.5
(6.75k)
00
31.89
225.2
33.44
228.1
25.25
237.3
25.01
90.7
26.03
230.9
25.98
90.5
50
25.75
466.1
25.33
138.4
26.14
500.2
26.37
138.3
WMT14
1000
25.66
8996.7
25.71
265.4
25.82
8991.7
26.88
265.5
(3k)
00
24.79
307.5
26.39
307.3
25
32.29
145.2
31.97
36.4
33.12
143.5
32.94
36.4
50
32.53
286.1
32,50
63.2
33.41
312,4
33.26
62.7
WMT16
1000
32.63
5588.9
32.86
171.4
33.67
5601.0
33.79
171.2
(2k)
32.91
196.4
33.86
196.3
Scaling Law in Sampling Speed. For illustrative purposes, we the example of IWSLT14 to visualize how the sample quality scales regarding sampling speed for different methods. In Figure] [ we observe the trend of the BLEU score in relation to computational time. Each line in the legend represents a different sampling algorithm, and a steeper slope indicates a larger marginal gain when sampling for longer periods. [ in BLEU score over the log of time, which is remarkable in contrast with the flat curve of the baseline. Particularly, for multinomial diffusion, the BLEU score increases by in less than 60 seconds of additional sampling time. For absorbing diffusion, DNDM outperforms RDM before RDM samples 50 steps. In Tables and Appendix we further use the average number of function evaluations (NFE) to measure the improved speed within the specified number of sampling steps. Additionally, in Figure 2.
that our algorithm displays nearly linear growth
we visualize how the BLEU score and the generated text change throughout the sampling process.
8

---

Table 3: BLEU score comparison of absorbing diffusion machine translation benchmarks IWSLT14 DE-EN, WMT14 EN-DE, and WMT16 EN-RO. Below the dataset, we present the amount of data used the evaluation (sentences). The blue background highlights algorithms, and the bold number indicates the best performance within each row and each setting (i.e., with or without top-k).
RDM-Absorb
DNDM-Absorb
RDM-k-Absorb
DNDM-k--bsorb
Dataset
Steps
BLEU
Time (s)
BLEU
Time (s)
BLEU
Time(s)
BLEU
Time (8)
25
31.58
116.3
32.43
67.2
34.50
108.9
34.14
67.3
50
31.80
227.2
32.63
95.9
34.58
213.9
34.34
96.2
IWSLT14
1000
31.91
4197.4
32,93
161.1
34.60
4205.9
34.56
162.3
(6.75k)
33.03
174.6
34.65
180.7
25
24.97
116.4
25.79
68.1
27.50
107.5
27.18
68.0
50
24.95
231.1
26.10
102.0
27.73
255.2
27.66
102.5
WMT14
1000
25.22
4169.4
26.43
178.3
27.75
4167.4
27.82
179.1
(3k)
DC
26.50
180.1
27.50
181.2
25
32.86
75.5
33.20
41.2
33.92
69.9
33.96
41.4
32,93
148.4
33.30
62.5
34.10
166.1
34.20
62.7
WMT16
1000
33.25
2951.7
33.60
121.3
34.44
2718.7
34.38
122.7
(2k)
00
33.42
121.8
34.41
121.9
30
BLE3 Scoiee
Computational 1930
10000
1000
Computattionl Time (5)
(a) Multinomial Diffusion
(b) Absorbing Diffuusion
Figure 1: Generation quality generation time comparison on IWSLT14. z-axis: computational time in seconds; y-axis: BLEU score.
4.2 Unconditional Text Generation
For unconditional text generation, evaluate approach on language modeling tasks, where the model learns to generate text that matches the statistical patterns of the training data. Unlike conditional generation, this task involves directly learning (xxo) x4) without conditioning any input text. We conduct experiments on the text8 and enwik8 datasets using a decoder-only architecture similar GPT models. Since unconditional generation does not require encoding input sequences, we employ a 12-layer Transformer decoder without an encoder component.
Datasets. The natural language generation task is evaluated on two language datasets following Hoogeboom et al. (2021b): text8 and enwik8. Both datasets are from Wikipedia, but their contents highly distinct. In text8, the plain text consists of English words (all the letters in lower case) and spaces, and it is tokenized into characters and one blank space, resulting in 27 categories. In contrast to the cleanness of text8, c8 preserves the original XML dump contents, and there exist various special symbols in its raw text, so its text is tokenized into Byte, resulting in 256 categories. We utilize textê dataset with sequence length 256 and enwik8 dataset with sequence length 320. The train/val/test splits are 9e7 be7/5e6) /566/55 for both text8 and enwik8.
Performance Metrics. Our evaluation of text generation quality relies on the perplexity score. When generating text8 data, we calculate perplexity scores using the GPT2 model, while for enwik8 data generation, employ the GPT2-large model. The sampling speed is measured in seconds.

---

t= 100 [noise] [noise] [noise] [noise] ...
= 75 [noise] ... [noise] and we [noise] [noise] govern[noise] [noise] year [noise]
= 67 [noise] [noise] fello [noise] [noise] [noise] and we them [noise] [noise] city govern[noise] every year.
Score
39 we choose some fellows every year and let them work with city governance every year.
= we choose some fellows every year and we let them work with city governance every year.
Time Raverse Process
(a) The BLEU Score in the Generation Process
(b) Text in the Generation Process
Figure 2: We demonstrate the 100-step generation process of DNDM-k-Multi as an example, where the left is the change of the BLEU score along the generation process, and the right is the text different time steps. As the time goes from 100 to O, noise gradually removed until the corresponding English text emerges. Since the transition time follows Beta distribution as described in Section 3.2
the majority of transitions occur near the starting time.
Baselines. We compare our proposed tion task with the vanilla Multinomial Results and Discussion. Table displays the performance of our algorithms in text generation tasks. We run the multinomial diffusion model on the text8 dataset for 1000 diffusion steps and the enwik8 dataset for 4000 diffusion steps. Our DNDM-based algorithms outperform the vanilla sampling algorithm used in Hooge- boom et al. (2021b) in terms of both sam- pling time and perplexity score. Specif- ically, for the text8 dataset, DNDM- based algorithms are times faster than the vanilla algorithm. For the enwik8 dataset, DNDM-based algorithms are 14 times faster than the vanilla algorithm.
DNDM on unconditional text genera- Diffusion (Hoogeboom et al., 2021b).
Table 4: Comparison of different sampling methods for unconditional text generation (multinomial diffusion) on textê and enwik8 benchmarks. Sampling time is computed by generating a single text sample of length 256 for text8 and length 320 for enwik8, averaged 10 runs. The blue background represents algo- rithms, and the bold number indicates the optimal value.
Vanilla
DNDM
Perplexity Time (s)
1,465.75 135.9
600.02
text8
31.1
Perplexity Time (s)
801.78 602.8
556.78
enwik8
47.4
5 Conclusion and Future Work
This paper presents a novel discrete non-Markov diffusion model (DNDM) accompanied by an accelerated sampling algorithm designed to boost sampling speed in discrete-state space. Our discrete diffusion model incorporates "transition time set" latent variables, establishing itself as an efficacious diffusion and data generation method. Thanks to acceleration technique, significantly decrease the number neural network function evaluations without sacrificing sample quality. We also introduce an infinite-stey step sampling algorithm, DNDM-C, which provides new insights into bridging the gap between discrete and continuous-ting time processes for discrete diffusion models. While this study focuses on text generation using non-autoregressive models, promising direction for future exploration is applying our method to other tasks, such as audio and image generation.
Acknowledgement
We thank the anonymous reviewers area chair for their helpful comments. ZC, HY, YL, YK, JZ. and QG are supported in part by the National Science Foundation CAREER Award 1906169, IIS- 100-2008981, and the Sloan Research Fellowship. The views and conclusions contained in this paper those of the authors and should not be interpreted as representing any funding agencies.
10

---

References
ALAIN, G., BENGIO, Y., YAO, L.,, YOSINSKI, J., THIBODEAU-LLUFERR, E., ZHANG, S. and VINCENT, P. (2016). Gsns: generative stochastic networks. Information and Inference: Journal of the IMA 5 210-249.
ALIAS PARTH GOYAL, A. G., N. R., GANGULI, S. and BENGIO, Y. (2017). Variational walkback: Learning a transition operator as a stochastic recurrent net. Advances in Neural Information Processing Systems 30.
AUSTIN, J., JOIINSO,, D. D., Ho, J., TARLOW, D. and VAN DEN BERG, R. (2021). Structured denoising diffusion models in discrete state-spaces. Advances in Neural Information Processing Systems 34 17981-17999
BAO, F., LI, C., ZnU, J. and ZHANG, B. (2022). Analytic-dpm: an analytic estimate of the optimal reverse variance diffusion probabilistic models. arXiv preprint SoXiv:220100503:
BENGIO, Y., LAUFER, E., ALAIN, G. and YOSINSKI, J. (2014). Deep generative stochastic networks trainable by backprop. In International Conference on Machine Learning. PMLR.
BOJAR, O.,, BUCK, C., FEDERMANN, C.,, HADDOW, B., KOEHN, P., LEVELING, J., MONZ, C., PECINA, P., POST. M., SAINT-AMAND, H., SORICUT, R., SPECIA, L. and TAMCHYNA, A. (2014). Findings of the 2014 workshop statistical machine translation. In Proceedings of the Ninth Workshop on Statistical Machine Translation. Association for Computational Linguistics, Baltimore, Maryland, USA.
BOJAR, O... CHATTERJEE, R., FEDERMANN, C., GRAHAM, Y., HADDOW, B., HUCK, M., J1- MENO YEPES, A., KOEHN, P., LOGACHEVA, V., MONZ, C., NEGRI, M., NÉVÉOL, A., NEVES, M., POPEI., M., POST, M., RUBINO, R., SCARTON, C., SPECIA, L., TURCHI, M., VERSPOOR, K. and ZAMPIERI, M. (2016). Findings of the 2016 conference on machine translation. In Proceedings of the First Conference on Machine Translation: Volume Shared Task Papers. Association for Computational Linguistics, Berlin, Germany.
BORDES, F., HONARI, S. and VINCENT, P. (2017). Learning to generate samples from noise through infusion training. arXiv preprint arXiv:1703.0669
CAMPBELL, A., BENTON, J., DE BORTOLI, V., RAINFORTI, T., DELIGIANNIDIS, G. and DOUCET, A. (2022). A continuous time framework for discrete denoising models. Advances in Neural Information Processing Systems 35 28266-22222 28279.
CERITLI, T., GHOSHEH, G. O., CHAUHAN, K., ZuU, T., CREAGH, A. and CLIFTON, D. A. (2023). Synthesizing mixed-type electronic health records using diffusion models. arXiv preprint arXIv:2302.14679.
CETTOLO, M., NIEHUES, J., STÜKER, S., BENTIVOGLI, and FEDERICO, M. (2014). Report on the 11th IWSLT evaluation campaign. In Proceedings of the I 11th International Workshop on Spoken Language Translation: Evaluation Campaign. Lake Tahoe, California.
CHANG, H., ZHANG, H., JIANG, L., LIU, C. and FREEMAN, W. T. (2022). Maskgit: Masked generative image transformer. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition.
CHEN, N., ZHANG, Y., ZEN, H., WEISS, R. J., NOROUZI, M. and CHAN, (2020). Wavegrad: Estimating gradients for waveform generation. arXiv preprint K009:0009.0713
CHUNG, H., SIM, B. and YE, J. C. (2022). Come-closer-diffe cetionser-dfffu-ffstttee Accelerating conditional diffusion models for inverse problems through stochastic contraction. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition.
DOCKHORN, T., VAHDAT, A. and KREIS, K. (2021). Score-based generative modeling with critically-damped langevin diffusion. arXiv preprint 12..0:21
DOCKHORN, T., VAHDAT, A. and KREIS, (2022). Genie: Higher-order denoising diffusion solvers. Advances in Neural Information Processing Systems 35 30150-30166.

---

GHAZVININEJAD, M., LEVY, O., LIU, Y. and ZETTLEMOYER, L. (2019). Mask-predictt Parallel decoding of conditional masked language models. arXiv preprint arXiv:/904.09524.
GRUVER, N., STANTON, S., FREY, N., RUDNER, T. G., HOTZEL, I., LAFRANCE- AAPRANCE-VANASSEL J.,
RAJPAL, A., CHO, K. and WILSON, A. G. (2024). Protein design with guided discrete diffusion. Advances in Neural Information Processing Systems 36.
HE, Z., SUN, T., WANG, K., HUANG, X. and QIU, X. (2022). Diffusionbert: Improving generative masked language models with diffusion models. arXiv preprint arXiv:221..15229
Ho, J.. CHAN, W., SAHARIA, C., WHANG, J., GAo, R., GRITSENKO, A., KINGMA, D. P., POOLE,
B., NOROUZI, M., FLEET, D. J. ET AL. (2022). Imagen video: High definition video generation with diffusion models. arXiv preprint arXiv:2210.02303.
Ho, J., JAIN, A. and ABBEEL, P. (2020). Denoising diffusion probabilistic models. Advances in neural information processing systems 33 1840-6851.
HOOGEBOOM, E... GRITSENKO, A.. BASTINGS, J., POOLE. B., BERG, D. and SALIMANS, T. (2021a). Autoregressive diffusion models. arXiv preprint arXiv:21100000037
HOOGEBOOM, E... NIELSEN, D., JAINI, P., FORRÉ, P. and WELLING, M. (2021b). Argmax flows and multinomial diffusion: Learning categorical distributions. Advances in Neural Information Processing Systems 34 2245-12465
JOLICOBUR-MARTNEEAUU A., LI, K., PICHI--AAILLEEER, R., KACHIANN T. and MITLIAGKAS, I. (2021). Gotta go fast when generating data with score-based models. arXiv preprint arXiv:2105.14080.
KARRAS, T., AITTALA, M., AILA, T. and LAINE, S. (2022). Elucidating the design space of diffusion-based generative models. Advances in Neural Information Processing Systems 35 26565-26577.
KoNG, Z. and PING, W. (2021). On fast sampling of diffusion probabilistic models. arXiv preprint 001:22
KONG, Z., PING, W., HUANG, J., ZHAO, K. and CATANZARO, B. (2020). Diffwave: versatile diffusion model for audio synthesis. arXiv preprint (0X9v:2009.09761
LIU, L.. REN, Y., LIN, Z. and ZHAO, Z. (2022). Pseudo numerical methods for diffusion models on manifolds. arXiv preprint 2222:2202.00778.
LU, C., ZHOU, Y., BAO, F., CHEN, J., LI, C. and ZHU, J. (2022). Dpm-solver: fast ode solver for diffusion probabilistic model sampling in around 10 steps. Advances in Neural Information Processing Systems 35 5775-5787.
LYU, S. (2012). Interpretation and generalization of score matching. arXiv preprint arXiv: 1205.2629
MOVELLAN, J. R. (2008). Contrastive divergence gaussian diffusions. Neural Computation 20 2238-2252.
NACHMANI, E., ROMAN, S. and WOLF, L. (2021). Non gaussian denoising diffusion models. arXiv preprint arXiv:2106.07588
NICHOL, A. Q. and DHARIWAL. P. (2021). Improved denoising diffusion probabilistic models. In International Conference on Machine Learning. PMLR.
OTT, M., EDUNOV, S., BAEVSKI, A., FAN, A., GROSS, S., NG, N., GRANGIER, D. and AULI, M. (2019). fairseq: fast, extensible toolkit for sequence modeling. arXiv preprint arXiv:190..0105:
PAPINENI, K., ROUKOS, S., WARD, T. and ZHU, W.-J (2002). Bleu: method for automatic evaluation of machine translation. In Proceedings of the 40th annual meeting of the Association for Computational Linguistics.
12

---

REID, M., HELLENDOORN, J. and NEUBIG, G. (2022). Diffuser: Discrete diffusion via edit-based reconstruction. arXiv preprint arXiv:2210.16886.
SALIMANS, T. and HO, (2022). Progressive distillation for fast sampling of diffusion models. arXiv preprint arXiv:2202.00512.
SAN-ROMAN, R., NACHMANI, E. and WOLF, L. (2021). Noise estimation for generative diffusion
models. arXiv preprint arXiv21004.02600
SAVINOV, N., CHUNG, J., BINKOWSKI, M., ELSEN, E. and OORD, A. V. D. (2021). Step-unrolled denoising autoencoders for text generation. arXiv preprint arXiv:2112.06749.
SENNRICH, R., HADDOW, B. and BIRCH, A. (2016). Neural machine translation rare words with subword units.
SOIIL-DICKSTEIN, J., BATTAGLINO, P. and DEWEESE, M. R. (2009). Minimum probability flow learning. arXiv preprint arXiv:0906.4779.
SOHL-DICKSTEIN, J., WEISS, E., MAHESWARANATHAN, N. and GANGULI, S. (2015). Deep unsupervised learning using nonequilibrium thermodynamics. In International conference machine learning. PMLR.
SoNG, J., MENG, C. and ERMON, S. (2020a). Denoising diffusion implicit models. arXiv preprint arXiv:2010.02502.
SONG, Y., DHARIWAL, P., CHEN, M. and SUTSKEVER, (2023). Consistency models. arXiv preprint arXiv:2303.01469.
SONG, Y. and ERMON, S. (2019). Generative modeling by estimating gradients of the data distribu- tion. Advances in neural information processing systems
SONG, Y. and ERMON, S. (2020). Improved techniques for training score-based generative models. Advances in neural information processing systems 33 14438-12443
SONG. Y., SOHL-DICKSTEIN J., KINGMA, D. P., KUMAR, A., ERMON, S. and POOLE, B. (2020b). Score-based generative modeling through stochastic differential equations. arXiv preprint arXiv:2011.13456
SUN, H., Yu, L.., DAI, B., SCHUURMANS, D. and DAI, (2022). Score-based continuous-time discrete diffusion models. arXiv preprint arXiv:2211.1675:
VAHDAT, A., KREIS, K. and KAUTZ, J. (2021). Score-based generative modeling in latent space. Advances in Neural Information Processing Systems 34 1287-11330.
WATSON, D., Ho, J., NOROUZI, M. and CHAN, W. (2021). Learning to efficiently sample from diffusion probabilistic models. arXiv preprint arX.v:2106.03800.
YE, J., ZHENG, Z., BAO, Y., QIAN, L. and Gu, Q. (2023). Diffussin language models can perform many tasks with scaling and instruction-finctuiigg arXiv preprint arXiv:2308.12219
ZHANG, Q. and CHEN, Y. (2022). Fast sampling of diffusion models with exponential integrator. arXiv preprint arXiv:2204.1 /3902.
ZHENG, L., YUAN, J., Yu, L. and KONG, L. (2023). A reparameterized discrete diffusion model for text generation. arXiv preprint arXhv:2302.05737.
13

---

Broader Impact
This paper presents work that aims to advance the field of diffusion models. We believe this work may enable future applications of synthetic data generation, which may lead to positive impacts. Our experiments demonstrate that the proposed method achieves state-of-the-ait performance in the acceleration of the generative model. However, proper controls may be needed whenever applying our method to tasks that involve sensitive data data. There may be other potential societal consequences of our work, none of which we feel must be specifically highlighted here.
Limitations
The scope of the empirical claims is limited to the text domain with non-auto regressive setting. The applicability and performance of DNDM for other tasks like audio and image generation, as well as with other architectures like auto-regressive GPT models, are not explored and left as future work.
While DNDM-C, the infinite-step sampling algorithm, offers new insights into bridging the gap between discrete and continuous-time processes for discrete diffusion models, the sample quality is not guaranteed be superior to the accelerated algorithm with 1000 steps. Some intuitions here: the assumption that the neural network can be optimally trained is an ideal case and is often not realized practice. There is an inherent estimation error associated with the training process. As the number of steps increases, these estimation errors can accumulate, potentially leading to degradation in performance. This cumulative estimation error might explain why using an infinite number of steps does not necessarily yield better results than finite number of steps like 1000 in the conditional generation experiments. How to further improve sample quality of infinite steps is interesting but beyond the scope of this paper.
This paper focuses on the comparison with discrete Markov diffusion models since it aims to propose an accelerated algorithm for discrete diffusion with DNDM. Other text generation models, such as continuous diffusion models or auto-regressive models, are not considered in this paper.
This paper focuses on acceleration while maintaining good sample quality. The hyper parameter regions with poor sample qualities are not explored in this paper.
By highlighting these limitations, this paper aims to clearly scope its contributions and spark future work on addressing these important challenges with discrete diffusion models for generative modeling.
A Related Work
Continous Diffusion Models. Generative modeling via continuous-tine stochastic process has been
investigated thoroughly series of work (Movellan) 2008; Lyu 2012 Sohl-Dickstein al. 2009
Bengio et al. 2014: Alain et al. [2116] ALIAS PARTH GOYAL et al. 2017; Bordes et al. 2017).
The two lines of probabilistic modeling, denoising diffusion probabilistic model Sihh--Diksttein
ct al. 2015 Ho et al. 2020) and score matching with Langevin dynamics (Song and Ermon 2019)
are unified by Song et al. (2020b) through introducing the SDE framework for SGM. Based on it, subsequent works (Dockhorn et al. 2021 Nachmani et al.) [021]] Vahdat et al.) (021)) introduced a more complex diffusion process improve the generation speed and quality. On the other hand, the score-based sampling process is time-consuming and has attracted much attention for improvements in speed -San-Roman et al. 2021 Watson et al. 2022 Kong and Ping 202T, Karras et al. 2022 Song et al. (002). "Gotta go fast" (GGF), an SDE solver ver with adaptive step size tailored to SGM, is proposed in Selicoeur-Martineer et al. (202I). Song et al. (2020a) introduced a non-Markov diffusion process that corresponds to deterministic sampling process, enabling the generation of high-quality samples more rapidly. Dockhorn et al. (2022); Liu cl al. (2022) proposed a high-order SDE/ODE solver to achieve lower discretization error. Lu et al. (2022); Zhang and Chen (2022) leveraged the semi-lineat structure of reverse ODE to reduce the discretization error and achieve state-of-the-we sampling speed.
Discrete Diffusion Models. Research on discrete diffusion models was initiated by (Sohi-Dickstein et al. 2015), who investigated diffusion processes over binary random variables. The methodology was expanded upon by [o al. (2020), integrating categorical random variables through transition matrices with uniform probabilities. Though [Song et al. (2020a) suggested a similar extension in
14

---

their supplementary content, they abstained from experimenting with this model type. Later on, Austin et al. (021) unveiled a more intricate framework for diffusion concerning categorical random variables, enhancing the discrete diffusion models by merging them with Masked language models (MLMs). Contemporary research has furthered this domain by introducing features like editing- based operations (Jolicoeur- Martineeu et al. 2021 Reid et al. (022), auto-regressive diffusion models (Hoogeboom et al., 222 la Ye et al. 2023), the evolution of a continuous-time structure (Campbell et al. 2022), and the exploration of neural network analogs for learning (Sun et al. (022). Additionally, Zheng et al. (2023) introduced a re-parameterized loss and an associated sampling technique, attaining commendable outcomes in fewer iterations. Our contributions run parallel to these aforementioned studies.
B
Additional details of Discrete Diffusion
In our paper, we treat all the x, Anoise as row vector and treat as column vector with all elements equal 1.
B.1
Comparison between D3PM and DNDM
we introduced two different diffusion processes, the Markov process in [I and the non-Markov process in (6). In this section, we explain why they are different but result in the same joint distribution of (Xo: xx) for every time step f. Since q(xo) keeps the same, we only need to prove that the conditional distribution q[x,|xx) xp) is the same for the two processes.
In Section 3.T
Markov Process. [ is Markov process since Wn is independent with x.- Xo. so x; is
independent of all the past states given the present state. This can also be inferred from the following distribution, which does not depend on Xo, ................................ Xr-2-
[(x:|x(-1) = Cal (x = 3,x1-1 + (1 Be) (eosse)
(13)
Denote Qi = -.+ +1+(111 -1 (t) Anoise. then we have that
x Q: Bxx-11 (1 B,)xx-1 quoise Bix1-1 (1 Be quoise:
where the last equality holds due to the fact that x,-1 is a one hot vector and thus x 1 = 1. Therefore, we can rewrite [3) as q(2, 11) Cat(xx: 1.). Then, it is Markov process
with transition kernel Qr. So q(x: Xo) Cat( p xo Qo ... Q:) (Austin al. 202 We can then have that
Qo
Q2
[ + Bb) quoisel ... [8.I+ + (1 3,) qnoise]
II 3 3,I + (1 -,,)) 1
qnoises
where the last equality holds since identity matrix I multiplying any vector equals the vector itself and quoise Quoise (quoise quoise Quoise- Therefore, we have that
(xx (xo) Cat((x; -
3,, (1 3 3niino Cat (xx; p 0g + ar quoise)
where the last equality holds due to the definition a; IT B This gives rise to why the Markov
process 1 results in conditional distribution (xx, (Xu) Cat Cat(x; 0xX0 (1 at quoise)
Non-Markov Process. Recall that our DNDM defined by
b + b,)w,
where is fixed for any time f. Therefore, w no longer independent with Xo. .t-1-- There- fore, we can't 't define the transition kernel and compute q(x, x,) by using the property of Markov. Therefore, we need advance the technique to calculate the conditional distribution.
Proof of Theorem 3.1 quence,
By 66) we can derive the following explicit expression for recursive se-
by ... beXo, Σ
bb)bbstt...b b.w
b 6ixo + (1 b:)
15

---

4:30 + (1 0t w,
where second equality is by cancellation of terms, the last inequality holds by defining a, bj bb- Since an either equals to 1 or O. Besides, as equals if and only by = b2 .... = by = 1, so we have that a, follows Bernoulli distribution Bernoulli(B, ... 3t) = Bernoulli(ar) where a₁ II Ss. Therefore, we can conclude that q(x: (Xo) the proof.
Cat (x:: X5:P P = ax + (1 ar) qnoise), which completes
Comparison between D3PM-Absorb and DNDM. Recall the forward processes of D3PM and DNDM as follows:
D3PM X; = -,,,111 + (1 be) We:
17 = 1
DNDM X; 6,
be) )ew, 4I. 1...T.
For absorbing diffusion where w [Mask], DNDM's forward process becomes equivalent to D3PM since w, = = [Mask] in this special case. However, for multinomial diffusion or other diffusion processes where W, & w, these two processes exhibit different behaviors. addition, even for absorbing diffusion, our proposed reverse sampling algorithm for DNDM is still different from that for D3PM.
To elucidate the key differences between the sampling algorithm in DNDM and that in D3PM for absorbing diffusion, let's directly compare the algorithms:
For the D3PM-Absorb algorithm: We begin with an all [Mask] sequence. At each time step t, sample Xo po (xx))xx, If x, [Mask], x transitions to [Mask] with probability as)). If If # [Mask]. it remains 1--0--1) ar) and to Xo with probability (at-1 - ox)((1 a.)). unchanged.
For the DNDM-Absorb algorithm: We also start with an all [Mask] sequence, but crucially. we first determine the transition time set. During sampling, x, = [Mask], the transition probabilities for X are identical to D3PM. However, we only sample (xoox));) when at least one token needs to change, as determined by our pre-computed transition set. This selective sampling the key to our algorithm's 's efficiency.
Therefore, you can see that DNDM will skip many steps during the sampling process to avoid function evaluation and save computational cost. Even though the forward process of DNDM is the same as that of D3PM for absorbing diffusion, our DNDM approach introduces an algorithm design in the sampling process by pre-computing the transition time set and selectively applying function evaluations. This distinguishes DNDM from D3PM algorithm, offering a more computationally efficient approach to inference in discrete diffusion.
Comparison between DDIM and DNDM for Multinomial Diffusion. While there similarities between DNDM and DDIM (Appendix A), they are fundamentally different models, and DNDM is not a special case of DDIM. DNDM introduces novel framework specifically designed for discrete spaces, while DDIM was originally developed for continuous diffusion models. The key differences for multinomial diffusion are as follows.
DDIM: Following Song et al. (200aa (eq. 19 in Appendix A), 1(xx-1xxxxxx xo) = Cat(a,
1-ac-1 the process remains (au-1 orax)xx + ((1 01-1) (1 ),) Even with d; 1-a.
stochastic: x X2, Xo) C1 )x)) This means at every step, there's 's probability of choosing Xo. regardless of whether it has transitioned to x or not. Unlike Absorbing discrete diffusion, no [Mask] exists in multinomial diffusion. Therefore, DDIM cannot distinguish whether already equals
not. In particular, although the sampling process becomes less stochastic in the DDIM setting, it will still be predicted Xy with high probability 1 - o, 1-as
0t-1-0
DNDM: Achieves full de-randomization using transition time where:
x 11 (T l)xo + (T ()x,, with P(T = () 0t-1 Oit-
(14)
This crucial difference allows DNDM achieve full de-randomization once 7 is sampled, leading to a deterministic evolution that DDIM cannot achieve.
While DNDM and DDIM are both non-Markov models for multinomial diffusion, their fundamental approaches to and achievements in dc-randomization differ significantly in discrete spaces.
16

---

B.2 Training Objective
Hoogeboom et al. (2021b) utilized L, derived from the negative variational bound. In detail,
1,- = (Ta((at(x:: 0 post (x:: xo) Cat(x:p O p (x,, Ro)):
(15)
where Ry ( post (3ix + (1 K @ (at-1Xu + (1 au-1)/K 1/K1] and This loss evolves KI. divergence
post (Bxx, 3.)/K 1 ) (at-180 (1 04-1)/
between two categorical distributions.
Building this foundation, Austin al. (2021) introduced auxiliary denoising objective to strengthen the data predictions Xo at each time step. detail, the auxiliary objective is as follows,
xx)) log po (Xx) (xx|xx))
where the auxiliary loss term is minimized exactly when po (-(x,) has all its mass on the data point Xp.
Furthering the advancements, Zheng et al. 2023) put forth a reparametrized loss L, that incorporates re-weighted parameter A The detailed loss is
L Exx 1xx1~9((1x0) (L [x,, xo) Pg (x,-1
This loss can be related to the standard multi-class class cross-entropy loss function, which is also simple and powerful. That's why we consider Zheng et al.) (2023) the baseline model.
In Section 3.3 we consider the continuous-tine forward and backward process. Based on that, we 1
were motivated to analyze the infinite limit of the average loss lim, T Σ Lt- We find that the new loss can provide a better checkpoint than the loss averaged on the finite step on some tasks.
B.3
Calculation of the Evidence Lower Bound
B.3.1
Finite Time DNDM
In this section, we derive the evidence lower bound (ELBO) for our model. The derivatives inspired by the reasoning in DDIM (Song et al. 2020a) Specifically, We denote the gener- (x:-1 Xt, Xt, T). Here, Po
ative process as po (Xo.r(T) = Pg (T) II
(T) the pure noise and
(t) (x:-1 |x,, 7) q(xx-1 [x, Xo, r), where &o is given by neural network po. i.e., So po t).
Pg
Notice that by Jensen's inequality.
log (x(o) log E.-D, (xooT]]] 2 ETwD, [log/((x|7T]]
(16)
The evidence lower bound inequality gives
log 2 E (x) log Po (XD:T(T)
(17)
q(x1:1 (xo,
Plugging
17 into (6) gives the following ELBO,
Po Px (T)
log pa (xo) 2 EYWDD Exxr log
gxx1T|X007 = ELBO.
We factorize the pe and q by
po px(xo_T(T) = (T) (xT(T) II
Pd (c) (xx-
T
qxx1r/X0 7) = q(xx Xu, 7) II
Xu,
2m2
Here & admits such decomposition due to definition of the diffusion process in introduce the following reverse process:
O). which
X-- 1(r t)xo 1(T t)x..
17

---

Therefore, X1.T is Markovian when conditioned on and т. Based on the factorization, we have
ELBO E BrwD, Bxi xxxx
log P9 (T) (XT/T) +
log Pa (4)
(x1-1 (x),))
t=1
log q(xT)) Xo. 7)
log g (x(x x X0, x0:7) 7)
T
(1)
Pg {x - X T)
ETND, Exi- (
log logp8 Pa (xo|x1,7) +
log
@l x x x,: X0,
1=2
Pe (xT IT)
(1)
+ log q(xT xo: T)
ETwD, Exinul- xo,r) log Po (1) x1,
Po (xt |xt, T)
(8)
Xx log ((x x4, x),
const
ETWD, (xirg(((xom) log (1) ( (xn (1.
21
E E Ex, Ex.- 1xx-11x--q KL (L Xx,, No. (x +const.
Ce
By slight abuse of notations q(x, Xx, xp), Pe (x (x indicate the distribution of the diffusion process defined in Zhenng et al. (2023). that is, the standard Markov discrete diffusion process. In particular, we have
(e)
{
(x) log Po (1) const,
(xo|>1))
E
T # 1.
C. xx KL(g (
(x-
T L
0,
T T t.
Thus, obtain that
ELBO =P(( = 1) Ex rgl (xx) log Po (xo (x1)
T
P(r = t) Ex 1oc-i x KL(g(x:- 1x,, xo)lob (x--
+ const.
Here C, matches the loss terms in Zheng et al. (2023). In the practical training process, Zheng et al. (2023) samples & from Unif[1, . in each iteration and optimizes X, Lt, where X 's weights. Thus, when we sample and optimize L,, our ELBO indeed leads to the same training objective as Zheng al. (202)) up reweighting. Since Zheng al. (2023) is parametrization of existing works (Austin et al. 2021 Hoogeboom et al. 2021b), our training objective indeed aligns with previous
discrete diffusion models.
B.3.2
Continous Time DNDM
In Section B.3 we derived an ELBO for DNDM and its accelerated algorithm defined in Section 3.]
and 3.2 While for finite sampling steps, we can decompose the diffusion process via the sampling steps 1,...,7 in (7)). it becomes intractable for continuous Time DNDM (Infinite steps T - xo). Therefore, we can formulate the ELBO of continuous time DNDM by decomposing the transition times. The idea of decomposition of transition times follows Hoogcboom al. (2021a). but their
18

---

proof is only applicable to absorbing discrete diffusion, while ours can deal with discrete diffusion with various noise Iuoise including multinomial diffusion.
In Section B.3 we only consider the case of single token x E R for simplicity as we decompose the transition time т. Therefore,
with the sampling steps T. In this section, decompose need to consider a sentence with multiple tokens X = [
Xt,N] [[,NN where Xt, is the n-th
token and N is the sequence length. Recall that we defined the transition time set T = [TnJn=) in
Section 3.2 We arrange Tn, to obtain ordered sequence Tug. where 0 Tno < Jng Tup < ....
Then conditioning on the transition time set T -.,,...., ,N we have that
Tny
Po 1:N pe( 11N (T)
pa I I:N, T); N.....1
II
1:N
where we omit the time superscript of for simplicity. Then, the evidence lower bound inequality gives
Po (o (T)
lo (X0,1.N (T) 2 Ex Ex.., T.NN (rai (T,,N/Xo, IN, log q(X,,, T.I.N Xo,1:N, T)
(18)
By Jensen's 's inequality, we have
log pe (Xo...):)) = log B (po(xo, B
~D plo
(19)
Plugging
18 into (1) gives the following ELBO,
po (Xn.T
= ELBO. log pa (x)1 2 E E Dr Bxr,y mm r (o. log q(x,,, iT Xo. T)
We factorize the pe and q by
pe (e(Xo.T.LN(T)) = pe (XT..IIN)TT)
II s=N
Po(Xin, Xrnn T),
((xT,, T.N NO.1NN T) = x(xT,1NN1800 T)
II =
qf ((TT I: XT X0,1:N, T).
Therefore, we have
ELBO E D, Exr,, T.nNo T.n Wa..No....N.T log
1:N, log po X N:N LIN, T) log C(.T.INNNNO...N
N
log g( (X (K 1 1:N (xn, I:N, X0,1:N T)
LIN,
#=2
E B DD, Ex.., I..i ( T.L. No.1I. T) (N0..:NNNX1111.11 T)
q(xT N:N X I:N, No.1,N, + log po PO (T)
pa (Xr 1:N X M:N,
log
q(xT,I:N XO.I:N T)
B Ex, ( log.oo(Xo,,oa.
I T)
N
p 1:N X 11:N 7)
Ex
No.1 No..N. log q(x,,, q(x,,, 1:N X 1:N, ,0,1:N,71 T)
const
E BunnoaaD ExI. NN.. log (x
N
E E D. Extoy J.N N.N X 1.NNag
(L 1:N XT., I:N; N0,1:N; T) Ip pX (XT I:N I T)) + const. (20)
Remark B.I. (20) represents the ELBO utilized by the DNDM-C architecture. As our transition times Tn are independently and identically drawn from the distribution Dr, we are unable to further decompose (20) into loss function related the position information N, as was accomplished by Hoogeeoom et al. (2021a).
19

---

C Choice of the Transition Time
Transition time 7 in Definition 3.2 plays an important role in DNDM. In this section, we provide deeper discussion the transition time. We first give proof of the Theorem 3.6
Proof of Theorem 3.6 By the definition of T, know that To L is equivalent to bo.- 1...., 11- and b 0. Since {b is independent for different by definition, each Ty is also independent. Therefore, we drop the subscript for simplicity. On the other hand Therefore, have that
bo ,,... - and 0 can also conclude that
P(T t) P(bo 1..... b 1. bt 0)
| (1)
-1 - 11
04-1 Otty
where the second equality is due to b.. 1, ..... t are independent random variable following Bernoulli(3,) distribution and the last equality is by the definition of a; -11--/80
Notice that o4 is decreasing sequence in the 0 to 1 range. Therefore, P((r 1) [0, for any
t fl..... T).
Besides P(T > (a.-1 ax) og aT 1. Therefore, the derived distribution is valid long the Or, is decreasing from 1 to O.
2,23
0.535
Varcition
3025
0.130
0.525
3.055
20020
2.02
3.05
0.06
0.000
(a) Og t/T
(b) a. cos * 2T)
2.023
Thans Bon Time
6.0
Volue
901 Inesped (8.501
(c) Cce cos (T t/21)
(d) Beta Distribution with Different Parameter
Figure 3: Different distribution of transition time for T 50. a). b) The transition time sampled IK times under the different a, schedule. d) The approximated transition time for t l,..., T using different hypter-parameters.
From Theorem 3.6 we discern that the nature of the diffusion model scheduler, a,, clarifies the distribution of T.
Linear a schedule. This is schedule studied in Austin al. 2202)) where a, 1 t/T. This will result in P(r,, = t) = 1/T for every in the range to T. As a result, transition time distributes uniformly across each moment in the set {1, (1,..., 7). This can be verified in a) of Figure 3
Cosine a schedule. This a schedule studied Hoogeboom et al. (0021)). where at cos(T t/2I). For numerical consideration of the noise, small offset added, i.c., at f(t)ff(0)
20

---

where f(t) = cos((stt/T)// 111111111 x/2). As shown in b) of Figure the transition time will concentrate more on the large? T.
Cosine square a schedule. This is schedule studied in Zheng et al. 2023 where a; = cos (I 1/27), which motivated Nichol and Dhariwal (2021). Again, for numerical consideration of the noise, small offset is added, i.e., 0r -(t)/ f(O) where f(t) cos (s- + (1 + s) +// As shown in c) of Figure 3 the transition time will concentrate more on the middle of the range.
Generally, if we express or g(l/T), then we can simplify to PP(r - () =((( 1)/T) g(//T),
which further refines to (ggg))/(((()))))) + o(/TT). This indicates that transitions are more likely where Ig'| is large. Such mathematical finding can match our observation in Figure 3
In practice, we find that the shape of the transition time doesn't 't need match the theoretical prediction schedule exactly. As we can see from d) in Figure 3 A reshaped Beta distribution can approximate all the transition time distributions in fixed range. We first extract time E [o. 1] from a Beta distribution, then adjust these samples to fit by multiplying T and round them to acquire the integer. Our experiment finds that a properly chosen Beta distribution (tuned on the validation set) makes DNDM perform better on the translation tasks. Specifically, the chosen Beta distributions and the searching method are reported Appendix F] The performance of the four transition time schedules mentioned above, including the reported Beta distributions for comparison, are listed in Table 5] where we find the other three schedules affect the performance, and most of their scores are lower than the scores of Beta distribution, but their scores are at least still close to the reported Beta distributions, especially for ONDM-K-absone and DNDM-absorb. The efficiencies (measured by NFE) also similar to another.
Additionally, the ablation study on a reasonable range of different Beta distributions with 50 and 1000 sampling steps are shown in Tables 10 a where the BLEU scores and NFE values on the test set of one of the three machine translation datasets, WMT16, are shown for demonstration. The range of Beta distributions covers our chosen Beta schedules based validation sets and variety of basic Beta distribution shapes. These results show that the different Beta distributions influence the performance, but most of these choices of parameters still achieve results close to the optimal. Since the Beta distributions of the reported results in Tables 2 and 3 are selected using the validation set, they do not always have the highest scores on the test set, but their scores still at least belong to the top tiers according to these tables.
Another view of the transition time. In Algorithm [ we only need to call the neural network when I E T, which can significantly speed up the sampling since we reduce the function call. Notice that after we get the prediction, we only update the for those tokens at the transition time. However, (7 implies that x, = Xg as long as 7 > Therefore, instead only updating the x, for those tokens at the transition time, i.e., 7 t. we also update those tokens with transition time 7 >= t. This motivates us to consider a variation presented as Algorithm 3 which keeps almost the same sampling time but will update the tokens several times rather than just once. Since the tokens now get the chance to be corrected over time. The new Algorithm 3 will be more robust than Algorithm
Table 5: The BLEU scores and average number of function evaluations (NFE) values of different distributions of transition time for 1000 sampling steps with batch size 100. The parameters of the Beta distributions in this table are the same as Tables and and are reported in Appendix FF
DNDM-multi
HNDMMabsorb
DNDM-k-mult
DNDM-k-abson
Datasets
Schedules
BLEU
Avg NFE
BLEU
Avg NFE
BLEU
Avg NFE
BLEU
Avg NFE
Cosine
31.72
31.71
32.71
31.21
32.91
31.71
34.50
31.21
Cosine
31.78
31.74
32.93
31.21
32.78
31.74
34.53
31.21
IMSLT14
Lincar
31.77
31.82
32.65
31.33
32.83
31.82
34.53
31.33
Beta (reported)
31.82
30.33
32.93
31.08
33.15
30.33
34.56
31.08
Cosine 25.80
39.61
26.54
39.18
26.63
39.61
27.81
39.18
Cosine?
25.52
39.48
26.53
39.18
25.01
39.48
27.95
39.18
W4
Linear
25.58
39,97
26.33
39,82
25.47
39.97
27.63
39.82
Beta (reported)
25.71
38.94
26.43
38.76
26.88
38.94
27.82
38.76
Cosine
32.71
40.50
33.56
40.45
33.46
40.50
34.37
40.45
32.73
40.50
33,51
40.45
33.44
34.24
40.45
16
Linear
32.85
40.36
33.46
40.36
33.47
40.36
33.88
40.36
Beta (reported)
32.86
38.46
33.60
38.27
33.
38.45
34.38
38.27
21

---

Table Comparison of left- left-to-right and right-to-left transition approaches across different datasets and step counts.
Steps
Direction
IWSLT14
WMT14
WMT16
Left-to-right
31.08
24.41
31.67
25
Right-to-left
30.54
23.33
31.33
Left-to-right
32.87
26.46
33.37
50
Right-to-left
32.47
25.18
32.78
Left-to-right 34.45
27.93
34.43
1000
Right-to-left 34.04
27.02
34.15
Impact Transition Order. We further evaluate the impact of transition order. Building upon the results in Table 3 we investigate how the model performance will change if the transition time is influenced by the position of the tokens: from left to right and from right to left. In the left-to-right approach, tokens positioned on the left are transitioned Xo earlier, and vice versa for the right-to- left approach. Our experiments show that the left-to-right approach consistently outperforms the right-to-left approach across all datasets and step counts, demonstrated in Table
This result suggests that the order of token transitions significantly influences the model's performance. with earlier transitions of left-side tokens leading to better generation quality.
D Discussion on the Number of Function Evaluations (NFE).
In this section, we discuss the number function evaluations (NFE) in DNDM. According to (9). the update of token X
solely at its designated transition time. Meanwhile, if step does not coincide with transition time for any token, we maintain the sentence from the preceding step algorithm removes the need of function evaluation unchanged: Xt,1:N Xt-1,1:N- Therefore, Given this structure, our analytical emphasis is on for steps outside the set of transition times. the transition T since function evaluations are required only times f that are members of T. Consequently, the NFE is precisely the cardinality of the transition set, denoted by [T]. In our main paper, we propose naive upper bound for [T] min NN, T). which effectively demonstrates the speed of our method when T > N. Next, we demonstrate that DNDM also reduces the NFE when T < N. by providing precise estimation of [T].
Theorem D.1. Suppose transition time follows distribution D,, and consider sequence of length N. Then, the cardinality of the transition set T == TN) satisfies:
1 IT| < min N,T).
E = CT,ND.. 1-11..111 where CI,ND, a constant in the range (0, 1). Furthermore,
Cr.N.D.
where p. IP(T for D,, and the equality holds if and only if Dr is uniform distribution.
Proof. The first statement is straightforward. For completeness, the proof is provided. Since there only N transition times (possibly repeated): T....., . TN, the distinct transition times must satisfy IT < N. Additionally, since T C (1,..., T), we also have |T| < T.
To prove the second statement, we decompose T and use the property of expectation. Note that T = - 1fi T). Thus,
T Σ l = Σ Pli T). E T
T
(21)
Assuming Pr, (T = Pr. and that Ta are i.i.d. draws from D,, we have
P(i E 7) = 1
= pt)
(22)
22

---

Substituting 22 into 21 yields
E (1 -p:) pa)
B Σ 1 (1 -1-1)
E
p.)
-T=
Cr.N.D.
where CT,ND,
) An upper bound for Cr.N.D, is given as
/T.
p1)" T [1
CT,NDD,
T
where the inequality holds if and only pt 1/T for all [T] ie., D, uniform distribution.
Remark D.2. Theorem D.I suggests that even when T' < N, method still provides significant improvement. Specifically, for that model requires most 0.77 2 4, we have Cr,ND = (1 11/N 2 0.3. This implies in the worst scenario where the number p; satisfying p; < c more than M, then we have Cr,NDD, > M(1 c)" <)^ / /T. indicating that with M sufficiently large and e sufficiently small, CT,ND, can be pretty close 1.
Moreover, if we consider special
Remark D.3. In practical applications of our model, we employ a beta distribution for D,, which typically exhibits a right-heavy tail. Therefore Cr.N.D, tends to be larger than that in the worst-case scenario. In Tables andd we list the average NFE each experiment we run $ These results demonstrate significant reduction in NFE compared to the original counts: for T = 25, the NFE is only about half of the original count; for T = 50, it is approximately one-third; and for T 1000, reduces to less than one-twentieth of the original count.
Remark D.4. By Bernoulli's inequality, (1 p) > 1 for p 0. Therefore, CT,N.D, > 1 - N/TT, implying that E| <. As + oo, assuming the transition time does concentrate
single point, the probability that transitions occur simultaneously zero. Consequently, the generation process will sequentially go through each token. Thus, the expected number of function evaluations (NFE). E[[ will be N. In contrast, when is finite, there is non-zero probability that multiple transitions happen at the same time. Hence, in this case, the NFE, [T], strictly less than N
Table 7: BLEU score and the average number of function evaluations (NFE) comparison of multino- mial diffusion machine translation benchmarks IWSLT14 DE-EN, WMT14 EN-DE, and WMT16 EN-RO. The blue background highlights our algorithms. The average NFE values are calculated by dividing the number of times calling the denoising function (neural network) during generation by the number
of batches, where the batch sizes of all experiments are 100.
RDM-Multi
DNDM-Multi
RDM-A-Multt
DNDM-k-Multt
Dataset
Steps
BLEU
Avg NFE
BLEU
Avg NFE
BLEU
Avg NFE
BLEU
Avg NFF
25
31.26
25
30.95
9.03
32.82
25
32.30
9.03
50
31.50
50
31.45
14.07
32.82
32.80
14.07
IWSLT14
1000
31.69
1000
31.82
32.64
1000
33.15
30.33
00
31.89
32.73
33.44
32.73
25
25.25
25
25.01
13.52
26.03
25
25.98
13.52
.50
25.75
50
25.33
20.58
26. 14
50
26.37
20.58
WMT14 14
1000
25.66
1000
25.71
38.94
25.82
1000
26.88
38.94
0c
24.79
40.67
26.39
40.67
25
32.29
25
31.97
8.5
33.12
25
32.94
8.5
.50
32.53
50
32.50
14.73
33.41
50
33.26
14.73
16
1000
32.63
1000
32.86
38.45
33.67
1000
33,79
38.45
00
32.91
41.64
33,86
41.64
E Discrete Non-Markov Diffusion Model with Top-k Transition Time (DNDM-K).
23

---

Table 8: BLEU score and the average number of function evaluations (NFE) comparison of absorbing diffusion on machine translation benchmarks IWSLT14 DE-EN, WMT14 EN-DE, and WMT16 EN-RO. The blue background highlights our algorithms. The average NFE values are calculated by dividing the number of times calling the denoising function (neural network) during generation by the number of batches, where the batch sizes of all experiments are 100.
RDM-Absorb
DNDM-Absorb
EDM----Aboorh
DNDM-I-Absorb
Dataset
Steps
BLEU
Avg NFE
BLEU
Avg NFE
BLEU
Avg NFE
BLEU
Avg NFE
25
31.58
25
32.43
13.81
34.50
25
34.14
13.81
50
31.80
50
32.63
19.24
34.58
50
34.34
19.24
IWSLT14
1000
31.91
1000
32.93
31.08
34.60
1000
34.56
31.08
00
33.03
32.07
34.65
32.07
25
24.97
25
25.79
15.09
27.50
25
27.18
15.09
50
24.95
50
26.10
22.45
27.73
50
27.66
22.45
W
1000
25.22
1000
26.43
38.76
27.75
1000
27.82
38.76
26.50
40.39
27.50
40.39
25
32.86
25
33.20
13.91
33.92
25
33.96
13.91
50
32.93
50
33.30
20.95
34.10
50
34,20
20.95
WMT16
1000
33.25
1000
33.60
38.27
34.44
1000
34.38
38.27
33.42
41.59
34.41
41.59
Algorithm 3 Sampling From DNDM (Version 2)
Algorithm Sampling From DNDM-K
Require: Trained prediction function pa, Qnoise
Input: Trained prediction function pa- Qnoise
D,
and D,
1: 1o... do
for n 1...N do
2: Initiate each token XT,, Qnoise
Initiate each token XT,x Quoise
3: Initiate the transition time Tn D,
Initiate the top K number Ke))
4: end for
Initiate an empty set U () which includes
5: Collect transition time set T = {
the index of the tokens that have been up- dated. end for for T do if K 1 > K, then Caleulate the p argtopx, x. ( Generate No.1:N from pe (+)
6: for = T do
7: if E then
8: Generate N0,1:N from po (-))
9: for n N...N do
Update 1,- 1. if Tn 11: end for
else
Update Xt-1,n Xy., for all in the set P but not in the set U (top score but not updated yet)
13:
Update X1-1,1:N = Xr,1:N
end if
15:
end for
Update the set U by appending the index of the updated tokens
Return X0.1:N
else
Update X;- = Xt,1:Ni
end if end for Return X0.1:N-
Recent works have demonstrated that the quality of samples can be enhanced by utilizing supplemen- tary information derived from the neural network (Ghazvininejad et al.) [2099] | Savinov al.] [02T] Chang et al. 2022. He et al. 2022). Very recently, Zheng et al. (2023) applied this idea in their RDM framework and can achieve significant performance improvement. Specifically, after decoding X I.N from transformer po (-([x,,1:N) the score corresponding to this decoded token from the transformer's last layer, also recorded and denote as 8t,a- Tokens with high scores are more likely to be selected for updates.

---

Inspired by Zheng et al. 2023). we introduce the discrete non- Markov discrete diffusion Model with top-K transition time (DNDM-K), K). Instead of directly determining which token gets updated step by first drawing transition time T ~ 'D., we employ two-step process.
1. We first compute K; = -E== 1(T, 2 t). ke represents how many tokens should be decoded at the current step.
2. Compare Ki-1 and KG, if Kt-1 K,- There is no transition time at time 4, we just update Xt-1,1:N = X1II:N- If K > K,, Then there exist transition time time 4, we calculate and select the indexes with top-K,-1 scores. Then we update those tokens if it hasn't been updated yet.
Subsequently, we will only update those tokens with the highest Kr score that hasn"t been changed yet. Since the function evaluation occurs only when K2 changes, DNDM-K can give accelerated sampling algorithm. The details are presented in Algorithm
F
Experiment details
F.1 Conditional Text Generation
Parameter choices. In all experiments, the batch size is chosen to be 100. For RDM and RDM-k, our hyperparameter settings follow the original paper (Zheng et al. 2023) except for the batch size. Before the sampling, we used the saved checkpoint of trained models provided by the authors for discrete sampling experiments, and we trained the corresponding models for continuous sampling experiments.
For finite-step DNDM, the transition times are determined by the schedule, and we approximate the schedule with Beta distribution Beta(o, (a. :3) (please refer to Section 3.22 for detailed explanation). The a and values are selected by applying grid search on the validation sets. Based on the BLEU the validation sets, have selected Beta(15,77 7) for Multinormial Diffusion (3 3) for Absorbing Diffusion on both IWSLT14 and WMT14, Beta(5, 3) for Multinormial Diffu- sion WMT14 and Absorbing Diffusion WMT16, and Beta for Multinormial Diffusion on WMT16.
IWSLT14,
For infinite-steps (continuous-stcct step) diffusion (DNDM-C), the transition timestamps sampled from Beta(a, 3), where the choice of (a, B) are chosen from (100.0, 4.0) or (17.0, 4.0), based on the performance comparison and Beta(100, 4) for WMT14 and WMT16.
the validation set. In the end we choose Beta(17, 4) for IWSLT14
We conduct a performance comparison based on varying configurations of the Beta and Alpha distributions. The results of these comparisons are presented in Tables and Furthermore, to evaluate the efficacy of discrete versus continuous step schemes, we also conduct an ablation study under the same set parameters (100, 4) in Table
Table 9: BLEU scores on dataset WMT16 from the ablation study of other different Beta(a, 3) distributions of the transition time with 1000 sampling steps.
Beta
Model
Alpha
3
5
7
11
13
15
17
19
21
33.47
33.67
33.62
33.77
33.87
33.64
33.73
33.60
33.68
33.56
DNDM-k-Muli
33.18
33.47
33.68
33.53
33.71
33.69
33.73
33.72
33.74
33.82
7
32.99
33.20
33.49
33.56
33.58
33.61
33.67
33.72
33.78
33.83
32.73
32.66
32.74
32.82
32.77
32.92
32.80
32.81
32.76
32.86
DNDM-Multi
32.32
32.62
32.70
32.80
32.83
32.83
32.90
32.95
32.91
32.87
32.35
32.35
32.53
32.67
32.75
32.78
32.86
32.80
32.86
32.88
34.19
34.38
34.34
34.22
34.21
34.24
34.07
34.31
344.42
34.36
DNDM-k-Absorb
5 32.15
33.99
34.29
34.30
34.29
34.40
34.40
34.24
34,30
34.22
27.67 7
32.87
33.94
34.28
34.27
34.38
34.31
34.29
34.38
34.40
3
33.53
33.60
33.67
33.71
33.71
33.70
33.58
33.63
33.53
33.54
DNDM-Absorb
5 32.70
33.33
33.52
33.60
33.66
33.73
33.70
33.74
33.72
33.74
7
30.56
32.65
33.28
33.37
33.51
33.52
33.61
33.67
33.63
33.67
25

---

Table 10: BLEU scores on dataset WMT16 from the ablation study of other different Beta(a, 3)
distributions of the transition time with 50 sampling steps.
Beta
Model
Alpha
5
13
19
21
3
33.31
33.47
33.39
33.48
33.29
33.23
33.25
33.27
33.11
33.17
DNDM-K-Multi
32.93
33.28
33.29
33.58
33.45
33.21
33.40
33.49
33.16
33.19
32.61
32.98
33.31
33.20
33.27
33.41
33.39
33.53
33.35
33.08
3
32.63
32.46
32.44
32.56
32.59
32.55
32.37
32.33
32.22
32.23
DNDM-Multi
5
32.31
32.43
32.66
32.64
32 68
32.55
32.55
32.44
32.35
32.30
31.95
32,11
32.22
32,26
32.54
32.52
32.50
32.58
32.48
32.41
3 34.05
34.2
34.31
34.37
34.15
34,05
34,06
33,77
33.81
33,84
DNDM-K-
5
32.30
34.08
34.30
34.38
34.26
34.23
34.09
34.06
34.02
34.13
27.39 7
32.64
33.71
34.18
34.02
34.33
34.31
34.17
34.12
34.19
3
33.26
33.30
33,29
33,24
33.23
32.97
33.06
32.85
32.89
32,63
DNDM-Absorb
5
32.47
33.08
33.31
33.22
33 41
33.25
33.15
33.27
33.04
32.98
7
30.34
32.27
33.27
33.03
33.16
33.14
33.27
33.11
33.11
33.07
Table 11: The BLEU scores on dataset WMT16 with Beta(100. as the transition time schedule for discrete sampling or the distribution to sample transition timestamps for continuous sampling.
Steps
DNDM-k m-multi DNDM-k-absee
DNDM-mult DNDM-absorb
50
31,60
31.74
30.39
29.69
1000
33.59
34.37
32.87
33.52
33.86
34.41
32.91
33.42
Continuous time discrete time diffusions. To test our hypothesis that the continuous- time sampler will produce more accurate results in reverse sampling if our estimator consistently approximates the true Xg over time, we conduct various sampling experiments using shared pre- trained neural network. For discrete-time sampling, we consider three cases: T 25, 50, 1000. In each case, we rescale the interval [o, T] to [0, 50] and divide into fractions. In contrast, for continuous time sampling, we directly sample from continuous distribution over the interval [0, 50] without any partitioning.
Training approach. In machine translation tasks, the neural network is designed to learn g(xo| Xr; 2). where z represents the embedding of the source text obtained using transformer encoder layers. For fair comparison, we employ the same neural network structure as our baseline, with detailed architecture specifications available in Section E.2 of oheng et al.) (2023). Furthermore, given that the primary focus of this paper is the speed and effectiveness of our sampling algorithm, we omit the training procedure and instead use state-of- -f-the-art diffusion- liffusiin-bbsed pretrained checkpoint from Zheng et al. (2023). In the Appendix, we present additional results of continuous sampling based on continuously trained checkpoint. In this setting, we rescale our network input the interval [0. 1] and uniformly sample from this interval. The rest of the architecture follows that of Zheng et al. (0233
Performance WMT14. Our work primarily focuses the sampling process, and for the training, we utilized a pretrained checkpoint trained on 50 steps. In our sampling experiments we noticed that our method does not work ideally on WMT14, this could be possibly attributed the fact that the training performance on WMT14 was not ideal. Specifically, when we performed sampling using 1000 steps. the network was trained with exposure only 50 time steps, specifically at intervals of 20 (0, 20, 40. .... 980, 1000). As result, when we apply our model to generation using 1000 steps, the checkpoint NN has only been explicitly trained on these intervals. While we generally assume that the network can still provide a good estimate for the untrained steps, this might not hold under some hard scenarios. Considering the longer training time and poorer performance WMT14, likely that the training performance is insufficient for us to rely on those unseen steps. In word, the model's s trained checkpoint may not be robust enough to effectively handle unseen steps, especially for timesteps 1000 infinite timesteps.
26

---

F.2 Unconditional Text Generation
Parameter choices. We recover the checkpoints of the multinomial diffusion model employing the provided code by Hoogeboom al. (2021b). We train 12-layer Transformers for both text8 and enwik8 datasets for 500 epochs with the cosine schedule. For the text8 dataset, we utilize a training batch size of 256, while for the enwik8 dataset, we use batch size of 128. During training, employ learning rate of 0.0001, a weight decay parameter of 0.99, and the Adam optimizer.
G Additional Experiments
In this section, present additional experimental results. We begin by plotting the relationship between computational time and the number of sampling steps, using the absorbing diffusion in IWSLT14 example. Figure displays the growth of computational time for absorbing diffusion (yellow and orange lines), RDM-absorbing diffusion, and our model DNDM-Absorb and DNDM-T- Absorb (green and blue lines). We see from Figure that previous algorithms, including absorbing
Absorb
4000
DNDM-Absorb
RDM-Absort
DNDM-T-Absorb
Computational Time (s)
3000
2000
1000
25
50
1000
# of Sampling Steps
Figure 4: The growth computational time with the increase of the sampling steps
diffusion and RDM-absorbing diffusion all suffer from linear growth of computational time.
G.1 Continuous Training
we introduce the DNDM-C algorithm, designed for continuous- time, over discrete- time algorithms. However, this algorithm assumes that we have learned a sufficiently accurate neural network at any timestamp / E [0, 1]. Using the checkpoint trained with 50 discrete time partitions might not suffice for the purpose continuous sampling. In this section, we investigate the performance of continuous sampling when training is also done continuously.
In Section 4.
Table 12: Continuous Training + Continuous Sampling
C-DNDM-Muli
C-DNDM Absorb
Dataset
Step scheme
Default
Top-k
Default
Top-k
IWSLT14
Continuous
32.07
33.57
32,80
34.52
WMT16
Continuous
33.48
33.71
33.50
34.36
27

---

In Table 12 we summarize the performance of DNDM-C based on a neural network estimated
continously during training time. This involves sampling time uniformly from [0, 1] during training. and the forward process follows (11) in Section 3.3 The training objective remains the same as in discrete-time training. In Table we list the result of IWSLT14 and WMT16 with continuous training followed by continuous sampling. In addition, we compare the value with the corresponding value during discrete training and continuous sampling in Section 4.] and mark every item that improves in bold. As demonstrated in Table [2 there is room for enhancement in the overall sampling scores by training the neural network in a complete space timestamps.
G.2 Comparison with more generative models
In our study, a key aspect of evaluating our fast discrete generative model involves comparisons with prior work known for speed in sampling with minimal steps. Specifically, we draw a direct comparison with the Mask-Predict (Ghazvininejad to generate high-quality results within just 10) iterations. The results are shown in Table 13 All experiments were conducted on the same GPU and within the same machine setup.
al., 2019), which is notable for its ability
Table 13: The performance comparison on WMT16 of DNDM with Mask-Predict (Ghazvininejad
al. 2019). We align the number of sampling steps used in Mask-Predict with similar number of function evaluations (NFE) in our DNDM algorithm. We see that our A Algorithm runs faster, with
better BLEU score.
Mask-Predict
DNDM-Abson
ONDM-K-Absoe
Steps
BLEU
Time
Steps
BLEU
Time
NFE
Steps
BLEU
Time
NFE
10
33.08
49.25
25
33.20
41.2
13.91
25
33.96
41.4
13.91
15
33.06
67.94
50
33.30
62.5
20.95
50
34.20
62.7
20.95
25
33.16
111.89
1000
33.60
121.3
38.27
1000
34.38
122.7
38.27
40
33.10
169.95
33.42
121.8
41.59
34.41
121.9
41.59
G.3
Samples from the multinomial text models
Conditional Generation. For DNDM-Multi trained IWSLT14, provide a full generation process with 100 steps in Figure 5 A token ending with 6e indicates it is incomplete word; it will be concatenated with the following token form a complete word. For example, "fel0e 1o68 ws" means "fellows". We can see that after = 39, the generate sentence converges.
28

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The contributions are summarized as three points at the end of the introduction. The scope is fast sampling via discrete non-Markov diffusion models, provided in the abstract.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We add limitation section in front of the Appendix.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point any strong assumptions and how robust the results violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
29

---

Answer: [Yes]
Justification: Theorems 3.1, 3.5, and D.I are clearly stated, well-organized with consistent numbering, and supported by rigorous proofs that establish their validity.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
The paper provides detailed information on the experimental setup, model
architecture, and training procedures. The authors have submitted their training code along with the main paper, which enables reproducibility the main results. The code and detailed instructions allow other researchers to replicate the key findings of the paper.
Guidelines: In addition to experiment and implementation details on appendix, we submit our training and evaluation codes when submtting our main paper.
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived
well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurlPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibiliity In the case of closed-source models, it may be that access to the model is limited in
30

---

some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: All the datasets are public and can be open accessed. Our codebase will be available public upon acceptance.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (nttps://nnis.cc)
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
7 //nips. /twpss.c/ppubiie. httpcc/pccccccueeeeeeeeeeeeeeeee wwwlic/guies///eC httph//gggiiees/eeeuubbiiiiii
for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We provide these details Appendix (D, F).
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Confidence intervals provided in the experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
31

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπτог rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We provided detailed information about the computation resources in Section 4: a single NVIDIA258 RTX A6000 GPU with 48 GB memory.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer:
[Yes]
Justification:
We have checked NeurIPS Code of Ethics. Our submission satisfies all the
requirement.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., s if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We provide Broader Impacts Section in the beginning of Appendix.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
32

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no related risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
All used code, data and models in this project are properly cited,
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URI.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
33

---

If assets are released, the license, copyright information, and terms of use in the thcode has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssit
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
34

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
35

---

t= 100
[noise] [noise] [noise] [noise] [noise] [noise] [noise] [noise] [noise] [noise] [noise] [noise] [noise] [noise]
[noise] [noise] [noise] [noise] [noise] [noise]
t 79
[noise] [noise] [noise] [noise] [noise] [noise] [noise] [noise] [noise] [noise] [noise] [noise] [noise] [noise]
[noise] [noise] [noise] year [noise]
t = 78
[noise] [noise] [noise] [noise] [noise] [noise] [noise] [noise] [noise] [noise] [noise] [noise] [noise] [noise]
[noise] [noise] [noise] year [noise]
t= 77
Inoise] [noise] [noise] [noise] [noise] [noise] [noise] [noise] and we [noise] [noise] [noise] [noise] [noise]
[noise] [noise] [noise] year [noise]
t 75
[noise] [noise] [noise] [noise] [noise] [noise] [noise] [noise] and we [noise] [noise] [noise] [noise] governce
[noise] [noise] year [noise]
t 74
we [noise] [noise] [noise] 1o00 [noise] [noise] [noise] and we [noise] [noise] [noise] [noise] governee [noise] [noise] year [noise]
we [noise] [noise] fel00 1o00 [noise] [noise] [noise] and we let [noise] [noise] [noise] [noise] governce [noise] [noise] year [noise]
==
[noise] [noise] felee 1o00 [noise] [noise] [noise] and let [noise] [noise] [noise] [noise] governeQ [noise] every year [noise]
t
we [noise] [noise] felee 1o00 [noise] [noise] [noise] and we let them [noise] [noise] city governee [noise] every year.
66
we [noise] [noise] fele0 lo00 ws [noise] [noise] and we let them work [noise] city governee [noise] every year.
t= 64
we [noise] [noise] fel0e 1o00 [noise] [noise] and let them work [noise] city governce ance every year.
t= 61
we [noise] [noise] fel00 lo00 wa [noise] [noise] and we let them work with city governea ance every year.
t 60
we [noise] [noise] fel00 1o00 ws [noise] year and we them work with city governcs ance every year.
=
we [noise] [noise] felde 1o00 every year and we let them work with city governda ance every year.
52
we [noise] some fele8 lo00 ws every year and we let them work with city governce ance every year.
=
we choose felc0 lo00 every year and let them work with city governance every year.
t=
we choose some felee 1o08 ws every year and we let them work with city governance every year.
Figure 5: Text in the Generation Process
36


Reviews:
[{"review_id": "rZg9TvKtrg", "reviewer": "Reviewer_Uw1Q", "summary": "The paper introduces a discrete non-Markov diffusion model (DNDM) aimed at accelerating the sampling process in discrete diffusion models. The proposed method reduces the number of neural network function evaluations to speed up the sampling process while maintaining sample quality. The paper explores the transition from finite to infinite step sampling, providing new insights into bridging the gap between discrete and continuous-time processes. Experiments on natural language generation and machine translation tasks illustrate the competitive performance of the method in terms of speed and quality compared to existing methods.", "questions": "Suggest to address concerns in the weakness section.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "* The introduction of a discrete non-Markov diffusion model (DNDM) provides a new method for accelerating the sampling process in discrete diffusion models in a training-free manner. It reduces the number of neural network function evaluations, enhancing the efficiency of the sampling process to speedup by 3x for 50 steps.\n* The authors conducted extensive experiments on natural language generation and machine translation tasks, demonstrating the effectiveness of the proposed method, for both multinomial and absorbing diffusions.", "weaknesses": "* The method involves a complex process that might be challenging to easily follow and implement. More details or visualizations on how the transition time distribution is determined and whether it can be adapted for different types of discrete diffusion models will be helpful for a better understanding of the motivation and methodology.\n* The comparison with other acceleration methods is not very convincing, especially at a practical smaller number of sampling steps. Instead of RDM baseline, how does the proposed method compare with other existing acceleration techniques for discrete diffusion models in terms of both efficiency and quality? \n* While the method is tested on natural language generation and machine translation tasks, its applicability to other modalities such as image or video generation is not unknown, which might limited the scope of the proposed method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your support. Below, we address the questions.\n\n*** \n\n**Q1**. The method involves a complex process that might be challenging to easily follow and implement. More details or visualizations on how the transition time distribution is determined and whether it can be adapted for different types of discrete diffusion models will be helpful for a better understanding of motivation and methodology.\n\n**A1**.  We thank the reviewer for their feedback. However, we respectfully disagree that our method is overly complex or challenging to implement. We have taken several steps to ensure clarity and ease of implementation:\n\n- Training-free approach: Our sampling method is designed to be training-free, making it straightforward to integrate with existing discrete diffusion models.\n\n- Detailed algorithms: We have already included comprehensive pseudo-algorithms in the paper (see Algorithms 1-4) to guide implementation.\n\n- Discussion about transition time distribution: We have provided a detailed explanation and ablation study in Appendix C, which thoroughly covers how the transition time distribution is determined and its impact on performance. Figure 3 in the paper provides clear visualizations of different distribution types (e.g., linear, cosine, Beta) to aid understanding.\n\n- Adaptability: Our method can be adapted to different types of discrete diffusion models, including the most popular multinomial and absorbing diffusions, the results of which are demonstrated in Sections 4.1 and 4.2.\n\n- Ease of implementation: Our method can be implemented in just a few lines of code. For example, the core sampling logic can be expressed in the following block, where the key intuition is the condition line: \"if t in transition_times:\". It determines whether to update tokens at a given time step, significantly reducing computation while maintaining quality. \n``` python\ndef sample(x_t, t, transition_times):\n    if t in transition_times:\n        x_0_pred = predict_x0(x_t, t)\n        x_{t-1} = update_tokens(x_t, x_0_pred, t, transition_times)\n    else:\n        x_{t-1} = x_t\n    return x_{t-1}\n```\n\nWe believe these points demonstrate that our method, while mathematically sophisticated, is conceptually simple and easy to implement. However, if the reviewer still finds additional clarification necessary, we are open to adding more visualizations or explanations in the revised version.\n\n***\n\n**Q2**. The comparison with other acceleration methods is not very convincing, especially at a practical smaller number of sampling steps. \n\n**A2**. Our method, DNDM, consistently shows acceleration across various step sizes, particularly for moderate to high step counts. For example, in Tables 2 and 3, we demonstrate significant speedups for 50 and 1000 steps across different datasets (IWSLT14, WMT14, WMT16). While the speed is 25 steps, we still see improvements in most cases. Below is an additional experiment for IWSLT14 with fewer sample steps in an absorbing generation process (additional results for Table 3 in our submission). As we can see from the table, when the sampling step is significantly less than 25, the quality of the generated examples does not match those with larger sampling steps  (By Table 3, when step counts of 25 or higher, performance remains consistently above $\\mathbf{31.5}$ BLEU for both RDM-Absorb and DNDM-Absorb). \n\n| Steps | RDM-Absorb BLEU | RDM-Absorb Time (s) | DNDM-Absorb BLEU | DNDM-Absorb Time (s) |\n|-------|-----------------|---------------------|-------------------|----------------------|\n| 5     | 29.92           | 27.36               | 30.30             | 24.1               |\n| 10    | 31.02           | 48.08               | 31.49             | 37.9                |\n| 15    | 31.26           | 69.22               | 32.13             | 50.0                |\n\n\nIt's important to note that performance in low-step settings poses a significant challenge for discrete diffusion models, which is beyond the scope of our current work. Our primary focus is on accelerating the algorithm while maintaining good performance—a crucial factor for numerous real-world applications that demand high-quality sample generation. Our comprehensive experiments demonstrate that DNDM offers competitive speed-quality trade-offs across a broad spectrum of step sizes, with its performance notably excelling as the number of steps increases. \n\n***\n\n**Q3**. Instead of RDM baseline, how does the proposed method compare with other existing acceleration techniques for discrete diffusion models in terms of both efficiency and quality?\n\n**A3**.  Our work introduces the first training-free acceleration technique specifically designed for finite-step discrete diffusion models such as D3PM and multinomial diffusion, filling a gap in the field.\n\nWe chose RDM as our primary baseline due to its state-of-the-art results in discrete diffusion. Given the novelty of our method in the context of finite-step discrete diffusion models, direct comparisons with other acceleration techniques are limited. Our focus was on developing and demonstrating the effectiveness of this training-free approach, which opens up new possibilities for accelerating discrete diffusion models.\n\n***\n\n**Q4**. The method's applicability to other modalities, such as image or video generation, is unknown, which might limit its scope.\n\n**A4**. While our current work focuses on text generation, DNDM's core principles have the potential for broader applicability. The method is designed for discrete data, which naturally suits text but can also apply to other modalities through appropriate discretization or quantization. Numerous follow-up studies can benefit from our fast sampling algorithm for tasks such as Electronic Health Record (EHR) data generation and protein sequence generation. These areas all involve discrete data structures that could benefit from our acceleration technique.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fnZAEWJie5", "reviewer": "Reviewer_JGuY", "summary": "This paper presents the non-Markov process for the discrete diffusion to reduce the sampling time. The authors present the transition time to de-randomize the sampling process and study the non-Markov processes from finite to infinite step sampling. The conditional text generation and unconditional text generation results demonstrate the effectiveness of the proposed method.", "questions": "1. In line 281~282, the authors denote RDM and RDM-k as the sampling method with and without top-k selection, is this a typo?\n\n2. In the experiment, do you use a pre-trained model or train it yourself?\n\n3. The authors claim that they use a model consisting of an encoder and a decoder. This is confusing, do you remove the causal mask in the transformer decoder? For the unconditional text generation, what is the input of the encoder?", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 1, "strengths": "1. The writing of the article is very clear and easy to understand.\n\n2. Compared with the image field, discrete diffusion is more noticeable in the text field. So I think the conditional text generation and unconditional text generation experiments are sufficient.", "weaknesses": "**W1**: The authors claim that Eq.(1) and Eq.(6) are different because $w_t$ in Eq.(1) is independently drawn from the noise distribution $q_{noise}$ and $w$ in Eq.(6) is time-invariant. But, $q_{noise}$ is a Dirac distribution for the absorbing diffusion and $w_t=w$ where $t=1, \\dots T$.  So Eq.(1) and Eq.(6) are equal for the absorbing diffusion, which means the proposed non-Markov process is the same as the Markov process.\n\n**W2**: Besides W1, we can further deduce that for the absorbing process, the proposed DNDM sampling algorithm is equivalent to the original sampling algorithm of the Markov process.\n\nFor the origin Markov process, given $x_t$，we first sample $x_0 \\sim p_{\\theta}(x_0|x_t)$ and sample $x_{t-1} \\sim q(x_{t-1}|x_t, x_0)$ as shown in Eq.(4). I use $[M]$ to represent the absorbing state.\n\\begin{align}\nq(x_{t-1}|x_t, x_0) = \\frac{q(x_t|x_{t-1}, x_0)q(x_{t-1}|x_0)}{q(x_t|x_0)} = \\frac{q(x_t|x_{t-1})q(x_{t-1}|x_0)}{q(x_t|x_0)}\n\\end{align}\n\nFirstly, if $x_t$ is not the absorbing state, we have that $x_{t-1}=x_t$ because $q(x_t =a| x_{t-1} \\neq a) =0$ where $a \\neq [M]$.\n\nSecondly, if $x_t$ is the absorbing state, based on that $q(x_{t-1}=[M]|x_0)=1- \\alpha_{t-1}$, $q(x_{t-1}=x_0]|x_0)=\\alpha_{t-1}$, $q(x_t=[M]|x_{t-1}=[M])=1$ and $q(x_t=[M]|x_{t-1} \\neq [M]) = 1 - \\beta_t = 1 - \\frac{\\alpha_t}{\\alpha_{t-1}}$, we can get:\n\n\\begin{align}\nq(x_{t-1}=[M]|x_t=[M], x_0) = \\frac{1- \\alpha_{t-1}}{1 - \\alpha_t}, q(x_{t-1}=x_0|x_t=[M], x_0) = \\frac{\\alpha_{t-1} - \\alpha_{t}}{1 - \\alpha_t}\n\\end{align}\n\nBased on the above analysis, the sampling process of the absorbing Markov diffusion can be simplified as: we sample starting from an all $[M]$ sequence, and during the sampling, we sample $x_0 \\sim p_{\\theta}(x_0|x_t)$. If $x_t=[M]$, $x_{t-1}$ will stay the $[M]$ state with probability $\\frac{1- \\alpha_{t-1}}{1 - \\alpha_t}$ and transfer to $x_0$ with probability $\\frac{\\alpha_{t-1} - \\alpha_{t}}{1 - \\alpha_t}$. If $x_t \\neq [M]$, it will stay unchanged.\n\nIn order to further illustrate the relationship with DNDM sampling, I denote the first time $x_t$ transitions from $[M]$to a non-$[M]$ state as $\\tau$ (consistent with the transition time in this paper). We can deduce that $p(\\tau=k) =\\frac{\\alpha_{k-1} - \\alpha_{k}}{1 - \\alpha_k}  \\prod_{t=T}^{t=k+1} \\frac{1- \\alpha_{t-1}}{1 - \\alpha_t}=\\alpha_{k-1} - \\alpha_{k}$. $p(\\tau=k)$ and Theorem 3.5. further verified that the proposed Non-Markov method is the same as the original Markov method for absorbing diffusion.\n\n**W3**: The proposed non-Markov method of multinomial diffusion is the same as the method in DDIM[1], Appendix A but with a different formulation. We can use the $p(\\tau=k)$ in W2 to further verify it. \n\nIn conclusion, this paper presents a non-Markov process for the multinomial diffusion and absorbing diffusion to accelerate the sampling of origin method with Markov processes, this is the main contribution of this paper. However, for the multinomial diffusion, the relationship with the DDIM[1] (Appendix A) is not clearly stated. For the absorbing diffusion, the non-Markov processes are the same as the Markov processes.\n\nIf I misunderstand your approach, please feel free to figure it out, and I will adjust my score.\n\n[1] DENOISING DIFFUSION IMPLICIT MODELS, ICLR2021", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive feedback. We have addressed your questions and provided clarifications below.\n\n***\n\n**Q1**. The authors claim that Eq.(1) and Eq.(6) are different, but they are equal for the absorbing diffusion, which means the proposed non-Markov process is the same as the Markov process. \n\n**A1**.  We appreciate the reviewer's observation. While Eq.(1) and Eq.(6) are indeed equivalent specifically for absorbing diffusion, we respectfully disagree that this equivalence undermines our method. For more general cases beyond absorbing diffusion, these equations are not equivalent, which is why we term our approach the Discrete Non-Markov Diffusion Models (DNDM) framework. The key innovation of our paper is sampling transition times upfront to develop fast sampling algorithms (Lines 5 and 7 in Algorithm 1).  Sampling transition times upfront allows the algorithm to skip function evaluations for steps that are not transition times. This reduces the number of neural network calls, leading to faster sampling. DNDM provides a unified framework to introduce the notion of transition time across various diffusion types, including but not limited to absorbing diffusion. In the revised version of our paper, we will add a remark to clarify this special case and highlight the broader applicability of our approach beyond this special case.\n\n***\n\n**Q2**. For the absorbing process, the proposed DNDM sampling algorithm is equivalent to the original sampling algorithm of the Markov process. \n\n**A2**. We believe this is a misunderstanding. While Eq.(1) and Eq.(6) are equivalent for absorbing diffusion, our DNDM algorithm is fundamentally different from the original sampling algorithm. As explained in Section 3, the key innovation of our approach is determining the transition times at the beginning of the algorithm. This significantly reduces the number of function evaluations from T (time steps) to the number of transition times, which is typically much smaller than T. In contrast, the original absorbing diffusion method [1] requires a function evaluation at every step, resulting in T function evaluations. This difference leads to substantial computational savings in our approach.\n\n[1] Austin et al. \"Structured denoising diffusion models in discrete state-spaces.\" NeurIPS 2021.\n\n\n***\n\n**Q3**. The proposed non-Markov method of multinomial diffusion is the same as the method in DDIM[1], Appendix A but with a different formulation. \n\n**A3**.  While the DDIM paper [1] proposed a model for discrete diffusion in its appendix, our approach differs significantly. DDIM's discrete process is still randomized, as whether $x_t = x_0$ or $x_{t-1}$ is controlled by some latent random variables (those random variables are actually analogous to the transition times $\\tau$ in DNDM). Our method, in contrast, offers full de-randomization using the transition time argument $\\tau$, with only one transition time occurring during our sampling process.\nCrucially, the introduction of transition time in our derandomized process allows DNDM to achieve faster sampling speed under the same number of sampling steps, a feature not reported in DDIM. Furthermore, our work is specifically designed for discrete spaces, providing a comprehensive framework and detailed theoretical analysis connecting finite and infinite step sampling.\nThese key differences underscore that our method is a novel and significant contribution to discrete diffusion models, distinct from DDIM's approach. We will add a remark to clarify the relationship between our approach and DDIM's, emphasizing our method's unique features and empirical advantages in the discrete diffusion setting.\n\n[1] Song et al. \"Denoising diffusion implicit models,\" ICLR2021.\n\n***\n\n\n**Q4**. In lines 281-282, the authors denote RDM and RDM-k as the sampling method with and without top-k selection. Is this a typo?\n\n**A4**. Thank you for pointing out this typo. We will fix it in the revision.\n\n\n***\n\n**Q5**. In the experiment, do you use a pre-trained model or train it yourself?\n\n**A5**. As detailed in Appendix F (Experiment details), our approach varied based on the experiment type. For conditional discrete sampling experiments, we utilized pre-trained models (saved checkpoints) provided by the original authors when available to ensure fair comparison [1]. For continuous sampling experiments, no pre-trained checkpoints were available, so we trained the corresponding models ourselves.\n\n[1] Zheng et al. \"A reparameterized discrete diffusion model for text generation.\" arxiv 2023.\n\n***\n\n\n\n**Q6**. The authors claim that they use a model consisting of an encoder and a decoder. This is confusing. Do you remove the causal mask in the transformer decoder? For unconditional text generation, what is the input of the encoder?\n\n**A6**. We use different model architectures for conditional and unconditional tasks, but all self-attention blocks within the models are bi-directional and do not use causal masks. This design choice allows each token to attend to both past and future tokens during both training and inference, differentiating discrete diffusion from standard autoregressive models. The use of bi-directional attention in the decoder means the model isn't constrained to generate tokens sequentially, allowing for more flexible and potentially faster generation. For conditional text generation tasks like machine translation, we employ an encoder-decoder architecture. The encoder processes the source text, while the decoder generates the target text. For unconditional text generation tasks like text8 and enwik8, we use a decoder-only architecture similar to GPT models, without an encoder since there's no input sequence to encode - thus, there is no encoder input for these tasks. The 12-layer Transformer mentioned for these experiments refers to this decoder-only model. We will add a more explicit explanation in the experiment settings to distinguish these architectures for different tasks.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "zIIHfy5rNS", "reviewer": "Reviewer_oHup", "summary": "This paper proposes a new formulation for discrete diffusion models whereby the corruption process is defined as a non-markovian process. At each point, a decision is made as to either stay in the current state or switch to a noise sample however crucially, this noise sample is constant throughout the process thereby only a single transition happens for each dimension. During generation, the model then just needs to step from transition time to transition time and can ignore superfluous simulation steps where no transition happens. The model is trained using an ELBO which the authors derive for their transition time conditional process. The authors test their model on machine translation examining quality versus sample speed and also on unconditional text generation with the text8 dataset.", "questions": "In the end, do you think it will be possible to move beyond the idea of a time variable altogether? Since the final sampling algorithm steps from transition to transition, it seems that the more important variable is which tokens become denoised, in what order, and how many in one go. This is decoupled from time through your algorithm so perhaps there is even more simplification to be made.\n\nDo you think it is possible to learn the transition times on a per dimension basis? This could be useful to train models that can generate tokens in an intelligent ordering rather than currently, the order of generation is completely decided before any tokens have been generated when the transition times are sampled and the ordering is completely uniform over all orderings of the dimensions.", "limitations": "The authors adequately discuss the limitations in the appendix.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The authors present an original and interesting idea, it is a benefit to the community to point out the fact that standard discrete corruption processes have unnecessary transitions in them and that the same $q(x_t | x_0)$ distribution can be obtained by simply switching between a data token and a noise token. The idea to condition on the transition time itself within the framework also enables some significant simplifications for general styles of corruption whereas in the past this advantage may have only been noticed for absorbing state processes.\n\nThe paper is well written, it is fairly easy to get a good understanding of the proposed method on a first read of the paper and this is helped by the fact that the authors move some nuances and complexity to the appendix. Effort has been made to make the main text readable and intuitive which is greatly appreciated.\n\nI believe the paper will have some impact in the community because it is a quick win when users implement a discrete diffusion model. Instead of the standard sampling procedure of calling the network T times, users can switch to the proposed (quite simple in reality) algorithm and step directly from transition to transition without needing to change much implementation and gain a lot of speed up over the naive algorithm.", "weaknesses": "I think there should be some discussion relating to quite a simple baseline that can be implemented for the absorbing state case. One can sample an absorbing state diffusion model in the same way as a standard discrete diffusion model, by stepping from each timestep to the next, however, instead of carrying out a forward pass of the neural network for every timestep, you first check if any tokens perform a transition and only if at least one token transitions, you then do the forward pass. This is possible in the absorbing state case because the unmasking rate is independent of the neural network output. Therefore, this simple algorithm would have the same stated advantages as your method where at most the neural network is called N times but if T is less than N, it will be called T times. I see that for other diffusion styles, your algorithm is fundamentally different due to conditioning on the transition time, however, in the absorbing state case, it seems very similar to this simple method.\n\nHow can you explain the fact that you have better performance in terms of sample quality than the baselines you compare to? In your method, you propose no methodological advancement that should improve sample quality as your method is to speed up sampling to make sure the neural network is only called an appropriate number of times. Especially for a large number of timesteps, in Tables 2 and 3, you get across the board improvement, but your algorithm should be very similar to a standard discrete diffusion model in this regime but simply with fewer network evals.\n\nFor your text8 experiment, you say you use a 9e7/5e6/5e5 train/val/test split however I believe this is incorrect because this only adds up to 9.55e7 tokens but the text8 dataset contains 1e8 tokens. This may be inherited from a typo in https://arxiv.org/pdf/2107.03006 pg.25 but in a more recent paper https://arxiv.org/pdf/2308.07037 pg 45, the test set is 5e6 tokens. Please confirm which size of test set you used.\n\nThe names of the method seem to be slightly confused, for example on Figure 1, a DNDM-T is referenced but this is never actually defined in the full text.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your support and valuable feedback. We address your major question as follows.\n\n---\n \n**Q1**. Think there should be some discussion relating to quite a simple baseline that can be implemented for the absorbing state case. $\\dots$, however, in the absorbing state case, it seems very similar to this simple method.\n\n**A1**. Thank you for your insightful observation and suggestion. In the absorbing state case, as you accurately pointed out, one could implement a sampling method where:\n\n- The process steps from each timestep to the next, similar to a standard discrete diffusion model.\n\n- Before performing a forward pass of the neural network, it first checks if any tokens perform a transition.\n\n- Only if at least one token transition a forward pass of the neural network is performed.\n\nThis method would indeed be a special case of our approach, potentially reducing the number of neural network calls to at most N (number of tokens), or T (number of timesteps) if T < N. When $T \\rightarrow \\infty$, the algorithm becomes ARDM [1] (as detailed in Section G.1). This simplification works for the absorbing state case due to the unmasking rate's independence from neural network output. For other diffusion styles, our framework differs fundamentally due to transition time conditioning.\nIn a revised version, we would include this discussion to provide a more comprehensive comparison and to help readers better understand the advantages of our approach across different diffusion scenarios.\n\n[1] Hoogeboom, et al. \"Autoregressive Diffusion Models.\" ICLR 2022.  \n\n***\n\n**Q2**. How can you explain the fact that you have better performance in terms of sample quality than the baselines you compare to? $\\dots$ but your algorithm should be very similar to a standard discrete diffusion model in this regime but simply with fewer network evals.\n\n**A2**. Thank you for this insightful observation. You're correct that our primary goal was to accelerate sampling rather than directly improve quality. The superior performance in terms of sample quality was indeed an unexpected but welcome outcome.\nWe hypothesize that this improvement may be attributed to the non-Markovian nature of our process. Similar to how DDIM [1] improved upon DDPM, our non-Markovian approach might lead to more coherent generation by allowing the model to leverage information from key timesteps throughout the entire sequence rather than just the immediately preceding step.\nAdditionally, the reduced number of network evaluations using our method might actually be beneficial. By focusing on key transition points, we may be avoiding unnecessary noise introduced by intermediate steps, leading to cleaner, more focused generations.\nWe will add this discussion to the paper in our revision. In future work, we plan to conduct a more in-depth analysis to elucidate the exact mechanisms behind this quality improvement as well as its relation with different types of transition times.\n\n[1] Song, J., Meng, C., & Ermon, S. (2020).  ICLR 2021.\n\n***\n\n**Q3**. Typos: 1) Possible incorrect data split for the text8 experiment. 2) Confusion in method naming (e.g., DNDM-T referenced but not defined).\n\n**A3**. Thank you for pointing out those typos. We'll revise the text8 experiment data split and correct DNDM-T to DNDM-k in our revision. We appreciate your attention to detail in helping us improve the clarity of our paper.\n\n***\n\n**Q4**. In the end, do you think it will be possible to move beyond the idea of a time variable altogether? \n\n**A4**. Thank you for this insightful suggestion. While our current approach still relies on a time variable, your idea of focusing solely on token denoising order and grouping could indeed lead to further simplification and efficiency. This aligns well with our goal of optimizing the sampling process. Below we present additional experiments. We explored the impact of transition times based on the position of the tokens: from left to right and from right to left. In the left-to-right approach, tokens positioned on the left are transitioned to 𝑥0 earlier, and vice versa for the right-to-left approach. As the table shows, the left-to-right approach consistently outperforms the right-to-left approach across all datasets and step counts, supporting the significance of the choice of the transition time.\n\n| Steps | Direction     | IWSLT14 | WMT14 | WMT16 |\n|-------|---------------|---------|-------|-------|\n| 25    | Left-to-right | 31.08   | 24.41 | 31.67 |\n| 25    | Right-to-left | 30.54   | 23.33 | 31.33 |\n| 50    | Left-to-right | 32.87   | 26.46 | 33.37 |\n| 50    | Right-to-left | 32.47   | 25.18 | 32.78 |\n| 1000  | Left-to-right | 34.45   | 27.93 | 34.43 |\n| 1000  | Right-to-left | 34.04   | 27.02 | 34.15 |\n\nWe'll discuss this promising direction for future research in our revision, as it could potentially take our work a step further. \n\n***\n\n**Q5**. Do you think it is possible to learn the transition times on a per-dimension basis? \n\n**A5**. Thank you for this insightful suggestion. Learning transition times on a per-dimensional basis is indeed an intriguing idea that could lead to more intelligent and efficient token generation. This approach could offer greater flexibility compared to our current method, where transition times are sampled uniformly before generation begins.\nThe key challenges in pursuing this promising avenue would be:\n\n- Designing an appropriate neural network structure for the predictor to learn the transition times on a per-dimension basis.\n\n- Formulating an effective training loss that incorporates the learned transition times.\n\nImplementing this could allow for adaptive ordering of token generation, potentially improving the quality and efficiency of the generated text. However, it would also increase the complexity of the model and training process. In our revision, we will discuss this idea as a direction for future research.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "On3t7jiseS", "reviewer": "Reviewer_em1Z", "summary": "The paper proposes an accelerated sampling method from standard discrete diffusion models like multinomial diffusion and absorbing-state diffusion, using a non-Markovian forward process where the stochasticity is modelled by sampling a single transition time for each token, after which the process is fully determined. The model is trained similarly as a standard discrete diffusion model, but the formalism allows for a different type of sampler: The transition times are sampled in advance in the beginning, and the denoiser neural network simply parameterizes the transitions that happen at those times in the reverse process. This allows to skip over redundant steps where no transition would occur in the standard discrete diffusion models, speeding up sampling significantly for large step counts. The model provides improved results and faster sampling speeds over a prior accelerated sampling method for sequence-to-sequence generation tasks, and similarly improved results for unconditional language modelling with the text8 and enwik8 data sets when comparing with a prior multinomial diffusion model.", "questions": "- Since the accelerated multinomial model now does only one step for each token, I suppose it is not quite equivalent to the standard multinomial diffusion, where multiple transitions per token can happen during the generative process? Could the authors clarify the similarities and differences?", "limitations": "Addressed.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "+ Clearly improves over a standard multinomial and absorbing-state schedule in sampling speed and results\n+ Improves over a previous published work in accelerating discrete diffusion models\n+ The framework could be a useful conceptual tool for people working with standard discrete diffusion models in the style of D3PM and want to accelerate sampling. Methods like ARDM from Hoogeboom et. al. and the tau-leaping of Campbell et al. are similar in function, but either require reframing the modelling problem differently or only allow for absorbing-state transitions in the case of ARDM. \n+ In contrast, this paper presents a method that allows changing a model in the D3PM framework to a faster one that skips over redundant steps, and shows how it is connected to the original model as a model with transition times as latent variables. \n+ The method is simple and easy-to-use", "weaknesses": "- The method is, in practice, somewhat similar to prior work (Campbell et. al. and Hoogeboom et. al.), and in that sense it would be more beneficial for the community if the paper went deeper into analysing potential speed improvements in discrete diffusion models or theoretical connections between their method and other work. \n- It would be useful if we had results from less steps in Table 3: Seems like the biggest time improvements are obtained with large step counts, but the BLEU scores are not drastically different from low step count BLEU scores. If both methods work quite well with low step counts already, then the results don't seem like the best showcase of the improvements due to increased step counts. Overall, it would be useful to have a clearer picture of the situations in which the method provides practical benefits. \n\n[1] \"A Continuous Time Framework for Discrete Denoising Models\", Campbell et. al. \n[2] \"Autoregressive Diffusion Models\", Hoogeboom et. al.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your support and insightful comment.\n\n***\n\n**Q1**. The method is, in practice, somewhat similar to prior work (Campbell et. al. and Hoogeboom et. al.), and in that sense it would be more beneficial for the community if the paper went deeper into analysing potential speed improvements in discrete diffusion models or theoretical connections between their method and other work.\n\n**A1**.   While there are some conceptual parallels with prior work, our method offers unique and significant contributions as follows:\n\n- Unified framework: Unlike ARDM [1], which is limited to absorbing-state transitions, our approach provides a unified framework applicable to both multinomial and absorbing diffusions.\n\n- Non-Markovian continuous-time framework: Different from Campbell et al.'s (2022) Markovian framework [2], we study the non-Markovian setting, offering new insights for discrete diffusion models.\n\n- Theoretical foundations: Our rigorous theoretical analysis (Theorems 3.1, 3.5, and D.1) establishes connections between our non-Markovian process and standard discrete diffusion models.\n\n- Bridging discrete and continuous processes: We investigate the transition from finite to infinite step sampling, providing new insights into bridging the gap between discrete and continuous-time processes.\n\n- Practical implementation and scalable efficiency: Our method allows for the seamless adaptation of existing multinomial and absorbing discrete diffusion models and demonstrates significant speed improvements, achieving a 30x speedup at 1000 steps while maintaining generation quality.\n\nRegarding your suggestion for deeper analysis, we agree this would be valuable. Due to page limitations, we had to place some of the detailed discussions and analyses in the appendix (like lines 845-853). We will incorporate these extended discussions into the extended page of the main paper in the camera-ready version if accepted, providing a more comprehensive comparison with ARDM and Campbell et al.'s work [1,2]. \n\n[1] Hoogeboom et al., \"Autoregressive Diffusion Models.\"  ICLR 2022. \n\n[2] Campbell et al, \"A Continuous Time Framework for Discrete Denoising Models\". NeurIPS 2022.\n\n***\n\n**Q2**. Lack of results from fewer steps in Table 3, making it unclear in which situations the method provides practical benefits.\n\n**A2**. We appreciate your feedback. Tables 2, 3, 6, and 7 highlight the practical benefits of our method across various step counts:\n\n- At 25 steps: Our method achieves approximately 2x speedup.\n\n- At 50 steps: We observe about a 3x speedup.\n\n- At 1000 steps: The speed increases significantly to around 30x.\n\nThese results show that our method offers benefits even at moderate step counts like 25, with the advantage becoming more significant as the number of steps increases. This scalability makes our approach particularly valuable for tasks requiring higher quality generation and more computational steps.\n\nBelow, we present additional results for IWSLT14 with fewer sampling steps in an absorbing generation process, complementing the experiment in Table 3 of our submission. As shown in the table, when the sampling step count is significantly reduced below 25, the quality of the generated examples decreases noticeably (By Table 3, when step counts of 25 or higher, performance remains consistently above $\\mathbf{31.5}$ BLEU for both RDM-Absorb and DNDM-Absorb). \n\n| Steps | RDM-Absorb BLEU | RDM-Absorb Time (s) | DNDM-Absorb BLEU | DNDM-Absorb Time (s) |\n|-------|-----------------|---------------------|-------------------|----------------------|\n| 5     | 29.92           | 27.36               | 30.30             | 24.1               |\n| 10    | 31.02           | 48.08               | 31.49             | 37.9                |\n| 15    | 31.26           | 69.22               | 32.13             | 50.0                |\n\nPerformance in low-step settings is a known challenge for discrete diffusion models, which falls outside the scope of our current work. Our primary focus is on accelerating the algorithm while maintaining high performance, which is a crucial factor for real-world applications requiring high-quality sample generation. Our comprehensive experiments demonstrate that DNDM provides a competitive speed-quality trade-off across a broad range of step sizes, with its performance particularly excelling as the number of steps increases.\n\n***\n\n**Q3**. Since the accelerated multinomial model now takes only one step for each token, is it not quite equivalent to the standard multinomial diffusion, where multiple transitions per token can happen during the generative process? Could the authors clarify the similarities and differences?\n\n**A3**. Thank you for your question. Our accelerated multinomial model, based on the DNDM framework, indeed performs only one transition per token. This approach is mathematically equivalent to the standard multinomial diffusion in terms of the final generated distribution, and it leads to the same training objective, as detailed in Appendix B.\nHere are the key similarities and differences:\n\nSimilarities:\n\n- Final Distribution: Both methods produce samples from the same learned distribution.\n\n- Training Process: The training process remains unchanged, allowing the use of the same neural network.\n\nDifferences:\n\n- Sampling Process: Our method pre-samples transition times, allowing more efficient sampling by skipping unnecessary steps.\n\n- Number of Transitions: While standard multinomial diffusion allows multiple transitions, our method consolidates these into a single, more efficient transition.\n\n- Computational Efficiency: Our approach significantly reduces the number of function evaluations, especially for large step counts, which leads to faster sampling.\n\nWe will include a detailed discussion of these points in our paper to clarify this important aspect.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The research presents a new approach called DNDM, designed to make sampling in discrete diffusion models faster. This is achieved by decreasing the number of times the neural network needs to be evaluated, thereby speeding up the process without sacrificing the quality of the generated samples. The paper is well written with thorough experiments showing the effectiveness of the proposed approach. The proposed method is an important contribution to the community.
Decision: Accept (poster)