AR-Diffusion: Auto-Regressive Diffusion Model for Text Generation
Authors: Tong Wu
Zhihao Fan
Xiao Liu
Hai-Tao Zheng
Yeyun Gong
yelong shen
Jian Jiao
Juntao Li
zhongyu wei
Jian Guo
Nan Duan
Weizhu Chen
Venue: NeurIPS 2023 poster (2023)
Keywords: text generation
diffusion model
auto-regression
sequential dependency
TL;DR: We introduce a superior and faster auto-regressive diffusion model leveraging sequential dependencies for text generation.

Abstract: Diffusion models have gained significant attention in the realm of image generation due to their exceptional performance. Their success has been recently expanded to text generation via generating all tokens within a sequence concurrently. 
However, natural language exhibits a far more pronounced sequential dependency in comparison to images, and the majority of existing language models are trained with a left-to-right auto-regressive approach.
To account for the inherent sequential characteristic of natural language, we introduce  Auto-Regressive Diffusion (AR-Diffusion). AR-Diffusion ensures that the generation of tokens on the right depends on the generated ones on the left, a mechanism achieved through employing a dynamic number of denoising steps that vary based on token position. This results in tokens on the left undergoing fewer denoising steps than those on the right, thereby enabling them to generate earlier and subsequently influence the generation of tokens on the right.
In a series of experiments on various text generation tasks, including text summarization, machine translation, and common sense generation, AR-Diffusion clearly demonstrated its superiority over existing diffusion language models and that it can be $100\times\sim600\times$ faster when achieving comparable results. Our code is available at https://github.com/microsoft/ProphetNet/tree/master/AR-diffusion.

AR-DIFFUSION: Auto-Regressive Diffusion Model for Text Generation
Tong Wul+t, Zhihao Fan Xiao Liu Hai-Tao Zheng!.8) Yeyun Gong Yelong Shen', Jian Jiao Juntao Li Zhongyu Wei Jian Guo Nan Duan Weizhu Chen Shezhen International Graduate School, Tsinghua University, 2 Fudan University,
Microsofft Research Asia, *Microsoft Azure AI, Microsoff, Soochow University, 'IDEA Research, *Pengcheng Laboratory {yegong, yeshe, nanduan, wzchen) @ microsoft.comm zheng.har hawg.oaaataooooo @ www.tsinghua.edu.co guo j ian @idea.edu.cn
Abstract
Diffusion models have gained significant attention in the realm of image generation due to their exceptional performance. Their success has been recently expanded to text generation via generating all tokens within sequence concurrently. How- ever, natural language exhibits far more pronounced sequential dependency comparison to images, and the majority of existing language models are trained with a left-to-right auto-regressive approach. To account for the inherent sequen- tial characteristic of natural language, introduce Auto- Reoo--Regesive Diffusion (AR- RR-DIFFUSION), AR -DIFFUSION ensures that the generation of tokens on the right depends the generated ones the left, mechanism achieved through employing a dynamic number of denoising steps that vary based on token position. This results in tokens the left undergoing fewer denoising steps than those the right, thereby enabling them to generate earlier and subsequently influence the generation of tokens the right. In series of experiments on various text generation tasks, including text summarization, machine translation, and common sense generation, AR- RR-DIFFUSION clearly demonstrated its superiority diffusion language models and that it can be 100x ~ 600x faster when achieving comparable results. Our code is available at this https URL
existing
Introduction
Text generation is fundamental task within the field of natural language processing (NLP). Pre- trained language models like GPT-4 [OpenA] 2023], LLaMA [Tuvron et al. 2023). and Alpaca TTaor et al. 2023) have garnered significant attention with their ability generate fluent and human- like textual content. These models utilize the auto-regressive (AR) Transformer decoders [Vaswani al., 2017] emit generated tokens one-by-one sequential order from left to right. By leveraging the power of position dependency, AR models are able to enhance the naturalness, coherence, and
adherence human language conventions in the generated text [rronn al. 2020
Recent studies have shown the remarkable performance of diffusion models image generation (Ho et al.
2020], motivating researchers extend diffusion to text generation (Li et al. 2022a Gong et al.
2022 Dieleman et al.) 2022 Yuan et al. 2022 Ye et al. 2023 By introducing timestep. these methods progressively regulate the interpolation between the original tokens and Gaussian noise, then iteratively denoise for text generation. At each timestep. the diffusion- text generator predicts
"Work done during an intersship at Microsoft Research Asia. "hhese authors contributed equally to this work.
$ *Corresponding author.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Timestep
Timestep
Timestop
T
T
T
KRy, Rose
10%,40
Knn.t)
vtmn, Ferfusa
Cos
x0R fess =
ROts, foxss) > Rass -4i
P0t, f, -
Position
(1,,t)) [00, 4.:)
(lote)) Position
Position
22
N
Rig
N
12g
Diffusion-LM LM
(b)
AR
(c) AR- AR-Diffusion
Forward Diftusion Process
Revarse Diffusion Process
Token-Level Diffusion Timestep Function
Figure 1: Model behaviors illustrated on two-dimensional coordinate system, where the horizontal
axis stands for the position and the vertical axis represents the diffusion timestep. In the inference
stage, different models will behave differently. (a) For the typical Diffusion-I-M [Li et al. 2022a].
each token share the identical movement speed o(11, 44 14+1) = v(ng, 44 (4+1) ) = |4 - 4 (b) For
AR from the perspective of diffusson models, the tokens have two states based on the degree of interpo-
lation between the original tokens and Gaussian noise: to be decoded (at timestep t = TT) and already
decoded (at timestep t = 0). Specifically, we have o(ni,t,, f441) 0 and u(n2, &4, f.-1) T. (c)
In AIF-DIFFUSOON, (me, te) is the coordinate of anchor point. Tokens in different positions exhibit varying movement speeds, such v(n1, t4, 1441) > u(22, ti, t++1) when n1 722-
all tokens simultaneously following Non-Auto- Non-Auto-Regression (NAR) [ewis et al. 2020 Qi et al. 2020
2021 Li et al., 2022b), leading to faster decoding speed compared to AR. However, it also inherits the drawback of NAR, namely the sacrifice of inter-token position dependency Li et al. 2022c and the drop of generation performance [Bao et al. 2021].
To conduct a comprehensive analysis, we introduce a two-dimensional coordinate system to track the diffusion timestep of tokens f()) positioned at various locations. As illustrated in Figure ! the system assigns the token position n E [1, N to the horizontal axis and the diffusion timestep E [o, T) to the vertical axis. Diffusion-L.M (Li et al. 2022a]. which is followed by existing diffusion-based text generation models, is shown in Figure I a). It assigns uniform timestep to all tokens. In contrast, tokens the AR model depicted in Figure Ib)) exhibit distinct timesteps within generation step (4;). For instance, the already decoded token at position has a timestep of O, while the to-be-decoded token at position n2 has timestep of T. This approach effectively captures the sequential dependency, Motivated by this observation, introduce AR-DIFFUSION, an auto-regressive diffusion method, for the disparity in token positions and the principle of sequential token identification.
In AR-DIFFUSION, we propose multi-level diffusion strategy that includes both sentence-level and token-level diffusion. We randomly choose a sentence-level timestep f, and assign dynamic movement speeds v(-) by determining position- seniiioo--esstivee token-level timestep f(n, f) for each token. This enables tokens at the left of a sentence to undergo faster movement from random Gaussian noise to token embedding, while those at the right of the sentence experience slower movement to better utilize information from previously denoised tokens. During inference, to reduce the significant number of inference steps (e.g.. 2,000) required in Diffusion-L_M [[i et al.) [2022a]. SeqDiffSSq (Yuan) ctt al. 2022] and GENIE [Lin et al. 2023], we introduce a skipping mechanism that collaborates with the multi-level diffusion strategy accelerate the process.
Experimental results across various text generation tasks, such as text summarization, machine translation, and common sense generation, have consistently demonstrated that AR- RR-FIFFUSION surpasses existing text diffusion models, including AR methods in terms of both quality and diversity. Moreover, our verification reveals that AR- DIFFIFUUSOON requires fewer resources during decoding while maintaining superior performance. It achieves 100x faster than SeqDiftSeq (Yuan et al. 2022 in machine translation and 600 faster than GENIE [Lin et al. 2023 in text summarization while delivering comparable results. Furthermore, demonstrates promising results even in a challenging scenario where decoding is limited to only two steps.

---

2 Preliminary
2.1
Conditional Generative Language Models
In the field of natural language generation, conditional generative models are commonly implemented using either auto-regressive (AR) or non-auto-regressiv (NAR) methods. In AR (asswan al. 2017). tokens on the right are predicted based on visible left tokens. The likelihood is given by PAR [- = I P(ys 11:4-1; æ), where y; denotes the i-th token of y. On the other hand, NAR [Gu al., 2017 assumes conditional independence among tokens and generates them uniformly without distinction during decoding, resulting in the likelihood PNAR (NAR(y|2) (y|z) = II p(yi (z). This parallel gen-
eration approach is of lower quality compared to AR, although it offers substantial speed advantage.
2.2 Diffusion Models for Text Generation
Recently, Li et al. 2022a] propose natural language generation model based the diffusion process, which is typically divided into a forward noising process and a reverse denoising process.
Specifically, the forward process is a fixed linear Gaussian model, which gradually perturbs the random variable 2o until it becomes the standard Gaussian distribution. This can be formalized as:
c(= zo; x) ((z; Va (1 a))
(1)
where, āg = I ag and at is a coefficient that monotonically decreases with timestep t, ze is the latent state at timestep I.
The reverse process is to initiate from standard Gaussian noise and progressively utilize the denoising transition po p0(2-11lz;; a)) for generation.
p=(z zc; æ) (2= (; .)) [e 4; x)),
where the mean μe and variance Eg are learned from the model. In particular, we follow Li al. [202aa] is approach of using predefined variance without trainable parameters.
To extend the continuous diffusion process to discrete text generation, Li et al. 2022a introduce an additional Markov transition from the discrete tokens y to the latent variable 2o. In practice, we
add an embedding step qo (y) = (=o; Emb(y), (1 al) in the forward process, and use
trainable rounding step which is parametrized by pa (3) zo; x) = I (o æ:) in the reverse process. In each timestep, utilize encoder-decoder model go Zt. L; ar) to approximate žn [Lin et al. 2023 in a NAR manner and then estimate (t (z i;)
In consequence, combined with maximizing the evidence lower bound (ELBO) of log (3(()) training objective of the conditional diffusion language model is:
C = Bag (#oer M)
log Po Po zo; x)
||0
go (x),
(3)
3 Methodology
3.1 Multi-Level Diffusion
In the typical diffusion process, every token in the text sequence has the same diffusion timestep. In order to leverage the sequential nature of language, we enable tokens to have different diffusion timesteps during the forward and reverse pass. To accomplish this, we propose a multi-level diffusson strategy that includes both sentence-level and token-level diffusion. Firstly, the sentence-level, follow Diffusion-LA. [Li et al., 2022a] to randomly select a timestep t. Secondly, at the token-level, we incorporate positional information n E [1] based on the sentence-level timestep to regulate the diffusion timestep for the current token. The procedure is illustrated as:
z (z)a,,> =, =NN.o).
(4)
where is the given target sentence length, z, is the sentence representation at timester 2 is the latent representation for the n-th token at sentence-level timestep I, and f(n, 1) is leven-
(n,,)
'llease note that if we talk about "timestep" without explicitly indicating that it is for token-level. it should be for sentence-level.
3

---

timestep function that denotes the token-level diffusion timestep determined by token position n and sentence-level timestep
We visualize the token-level timestep (n,, [n, 1)) onto a two-dimensional coordinate system as Fig- ure I which takes the token position the horizontal axis and the sentence-level timestep the vertical axis. Furthermore, to provide a more profound description of the characteristics of movement, we define the speed of movement the following equation.
v(n, fa f(+1) fmn,t+1) f(n,t,),
where 4, and 1++1 are the start and end sentence-level diffusion timesteps. can observed that tokens in Diffusion-LM share the same movement speed, while those in AR exhibit different speeds.
3.2 Token-Level Diffusion with Dynamic Movement Speed
Based on the speed of movement, propose fundamental principle, dynamic movement speed, for designing the token-level diffusion timestep function fnn t) to take advantage of AR in diffusion. Specifically, elements Gaussian noise to token embedding, while those on the right side experience lower movement speed, thereby they be generated in the later sentence-level timestep and utilize information from previously generated tokens more effectively.
the left side of sentence undergo higher movement speed from random
Algorithm Training Process of AR IR-IIFFUSION.
Input: Datasct {xx, y maximum timestep number 7 and maximum target length N.
Output: Optimized model parameters 0.
1:
Define an anchor point (Mey fe
2: repeat
3: Sample (æ, y) from the dataset and embed into za-
Sample sentence-level timestep from the interval [o, + T), then start point is determined by the following equation:
(na, 1a) (clip(N- 4, 0, N), clip(t N, N,O,T))
(6)
5: Use the point-slope linear function determine the token-level timestep f(n, t) in position
[nn () = clip( t. to (n n.) + 0,
nhe
6: Sample 20,,,y for each n in different positions with Gaussian reparameterizattin.
7: According to equation (3) and equation ( employ gradient descent to optimize the objective:
min
log (y
Zo; w)
+
go (10 zoll"]
(8)
8: until converged
Following the guidance of the principle, we develop token-level diffusion strategy with the linear function, which is shown in Figure [c). In particular, the procedure is illustrated in clamp all elements in into the range
Algorithm [ where clip(æ,, min, max) function [in, max]. Specifically, in the forward process of diffusion, the start point goes to the left from (N, 0) to (0,0) 0) along the horizontal axis and then moves up to (0,T) along the vertical axis. Therefore, the entire range of sentence-level timestep is extended to [0, N + T..
In the reverse diffusion process, the multi-level diffusion follows the formula:
go (ze, t; x) go ((3)o.0) f(, (f)a.) ((2.))) (NN
(9)
where (z ((m.)) fn, x)) denotes the n-th element.
In particular, the anchor point is set (2 x N,T' in our implementation. The impact of different choices of the anchor point is discussed in supplementary material

---

3.3 Inference with Skipping
Typically, the generation process needs to go through all the sentence-level timesteps from N to O. To reduce the decoding time, we introduce a skipping mechanism that allows us to traverse a subset of timesteps.
Algorithm 2 Inference Process of AR-DIFFUSION with the Skipping Mechanism.
Input: Source condition æz number of decoding steps M and model parameters 0.
Output: Predicted target embedding y.
1: Define an anchor point (Me,te). te)-
2: Uniformly select decreasing sequenee timesteps {t, Moo ranging from T N t.
3: Sample ttp ~ (0,
4: for = to M - do
5: Calculate the start point (n,, f.) using equation 6
6: Based the current sentence-level inference steps and the next one fi+1, assign token-level timesteps
f(n, 1.) and f(n,441) token position using equation 7
7: Reverse sample =t,-1 = =((N))11)) from po Zey; x)) with the
following formulas: po( (2,330) = π pe (#)(0)))))) ((mm)))s
(10)
NNZeemmn Amfimm) + ugoo (m)
(11)
9: Map y to the nearest emhedding ýj
In practice, we propose an algorithm for the inference, illustrated in Algorithm 2
B((0)))) (1 (((())))))
Af(mi444)
(1 - af(n,) -1--11--00 a
p== 1 (ff(n
(((())))
af((..)))
(12)
the conditional distribution Zi,+1 inferred by (2 | x), and then we decompose by positions due the independent forward process of elements different positions. From equation (1T) to equation (12). we establish the relationship between tokens at different timesteps, and the detailed derivation can be found in supplementary material
In equation (10
Experiments
4.1 Tasks and Datasets
Text Summarization This task involves taking long document input and generating concise sentence as output. This requires models with the ability to identify important content and rewrite in condensed form. In experiments,
the publicly available XSUM [Narayan al. 2018 and CNN/DAILYMAIIL Hermann et al. (2015) on GLGE which is also named as GLGE--asy.
Machine Translation Translation is a widely used sequence-to-sequenee task. The input is sequence of words in the source language, and the output is sequence of corresponding words in the target language. We choose the IWSLT 2014 dataset and the data processing method is to follow the scripts provided by fairseq"
Common Sense Generation In this task, the model is provided with concept set consisting of objects and actions as input. The objective to generate sentence that incorporates these concepts and describes realistic scenario. We use COMMONGENT dataset for evaluation.
https://inklab use wwcc.edddCoomoneee.
5

---

4.2 Main Results
The results on different datasets are shown in Table [ Table 2 Table 3 and Table 4 The best result is bolded and the second-best result is underlined. "k" indicates the number of generated candidate sample It can be seen from the results each table that AR-DIFFUSION achieves best performance.
During the inference process, utilize 20 inference steps and employ Minimum Bayes Risk (MBR) Kumar and Byree 2004) decoding to select the best sample, following [Li et al. 2022a]. We choose MBR instead of the selection approach in GENIE, as GENIE picks up the best sample by calculating the maximum score for each generated one using ground truth, which introduces unfaimess. To
ensure fair comparison, we re-implement GENIE using our configuration and perform inference with 20 steps. More experimental details can be found in the supplementary material B
Table Results on XSUM
The results of NAR and Semi-NAR are from Qi et al. 2021 and
the results of AR are from GLGE [Liu et al. 2021].
Methods
Pattern
ROUGE-1
ROUGE-2
ROUGE L
NAT Gu al.
2017
24.0
3.9
20.3
iNAT
Iece et al
2018
24.0
4.0
NAR
CMLM Ghazv va et al.
2019
23.8
3.6
20.2
LevT Gu et al.
2019
24.8
4.2
20.9
InsTT
Stemm ct al.
2019
17.7
5.2
16.1
iNAT Lee al.
2018
27.0
6.9
22.4
Semi-NAR
CMLM Ghazvinneead
2019
29.1
7.7
23.0
LevT
Gu al. 2019
25.3
7.4
LSTM Greff
2017
25.1
6.9
19,9
AR
Transformer Vaswani et al. 2017
30.5
10.4
24.2
GENIE [Lin
2023 (k = 50)
29.3
8.3
21.9
AR-DIFFUSION (A: 50)
Diffusion
31.7
10.1
24.7
RR-DIFFUSION (I: = 500)
32.2
10.6
25.2
Table Results on CNN/DAILYMAIL test set. The results of AR are from GLGE Liu et al. [022
Methods
Pattern
ROUGE-1
ROUGE-2
ROUGE L
LSTM [Greff et al.
2017
37.3
15.7
34.4
AR
Transformer
Vaswani
al. 2017
39.5
16.7
36.7
GENIE [Lin et al
2023
(A: 50)
34.4
12.8
32.1
AR- AR-DIFFUSION 30=
Diffusion
39.6
16.3
37.1
DIFFUUSUSON 500)
40.2
17.1
37.7
The results presented in Table 1 and Table demonstrate that AR- DIFFUSION outperforms the existing NAR and Semi-NAi approaches across all metrics. Moreover, AR- RR-DIFFUSION consistently achieves significant improvements over GENIE in terms of all indicators. Furthermore, in comparison to Transformer, AR-DIFFUSION outperforms it on both ROUGE-1 and ROUGE-L, while achieving comparable performance terms of ROUGE-2. Notably, when the sample number is 500, AR-DIFFUSION demonstrates superiority over Transformer across all the measures.
Text Summarization
Machine Translation Table 3 presents the BLEU score implemented by SeqDiffuSeq setting TR-DIFFUSION outperforms the ron-auuo--reressiin CNAT in greedy search for single sample, and achieves substantial gain. Moreover, the BLEU score of AR R-DIIFFUSION surpasses GENIE by a large margin and shows slightly better performance than the AR Transformer. Specially, AR- AR-DIFFSIOON DIFFFUSION achieves a more powerful result at 500.
9he relationship between sample number and results is discussed in supplementary material 10 Notably, although AR's search has small heam, the search space may larger than 50 even 500. We also report SacreBLEU in supplementary material C to compare with DINOISER.

---

Table 3: Results on IWSLT14 DE-+EN test set following the setting of SEQDIFFUSEQ. "NFE"
indicates the Number of Function Evaluations (Ye et al. 2023].
Methods
Pattern
BLEU
Steps
NFE (Stepsxk)
Transformer Vaswani et al.
2017
AR
34.74
CNAT [Bao et al.
2021
NAR
29.81
SeqDiffuSeq Yuan
2022
(k 1)
29.83
2,000
2,000 (2,000
Diffusion
AR-DDIFUSSÓN
30.19
20
(20
GENTE [Lin
2023
(h: 50)
30.08
20
1,000 (20 50)
AR-DIFFUSION (k 50)
Diffusion
34.95
1,000 (20 50)
AR- AR-DIIFUSSON (k 500)
35.62
20
10,000 (20 x 500)
Table 4: Results COMMONGEN dev set. Results of NAR and AR are from
Lin et al.
2020
Methods
Pattern
ROUGE-2 2/L
BLEU-3/4
METEOR
SPICE
Net
Gu et al.
2016
9.23
30.57
13.60
7.80
17.40
16.90
Trans- Conss Lin al 2020
AR
11.08
32.57
17.20
10.60
18.80
18.00
MeanPooling Pooling-CoppyNee
2020
11.36
34.63
14.80
8.90
19.20
20.20
LevT Gu al.
2019
12.22
35.42
23.10
15.00
22.10
21.40
NAR
ConstLeven Susanto al. 2020
13.47
35.19
21.30
12.30
25.00
23.20
GENIE Lin al. 2023
(k
50)
12.89
35.21
22.00
13.30
24.30
23,00
Diffusion
AR-DIFFUSION
13.93
37.36
25.60
16.40
25.00
24.20
Common Sense Generation As depicted in Table RR-DIFFUSION achieves superior perfor- mance compared the current AR, NAR, and other diffusion methods across all the metrics on the COMMONGEN dataset.
Table 5: Experimental results of GENIE and AR-DIFFUSION with inference steps of 2 and 3 on XSUM test set. Take k = 10 apply the MBR decoding strategy. (+) indicates the drop score compared to the 20-step.
Methods
Steps
NFE
ROUGE-1
ROUGE-2
ROUGE-L
AVG Drop
2,000
20,000
30.36
8.78
23.31
20
200
28.33
7.46
21.15
GENIE
3
30
25.03 (-3.30)
5.32 (-2.14)
18.17 (-2.98)
2.81
2
20
23.45 (-4.88)
3.95 (-3.51)
16.94 (-4.21)
4.20
20
200
30.99
9.32
23.95
AR-DIFFUSION
3
30
30.23 (-0.76)
8.68 (-0.64)
23.43 (-0.52)
0.64
20
29.28 (-1.71)
7.99 (-1.33)
22.98 (-0.97)
1.34
4.3 Inference Efficiency
First, we use the number of function evaluations (NFE) as a measure to compare inference effi- ciency (Ye et al. 2023 in machine translation. From Table 3, it is evident that even when the NFE reduced to 1% SeqfufeSee (equivalent to 100x faster), - AR-DIFFUSION still outperforms SeqDiffuSeq. Moreover, inereasing the number of generated candidate samples (k 500) leads to further performance improvements, albeit with increased time consumption.
Second, we conduct experiments with extremely limited number of inference steps (2 and 3 12 and compare the performance with that of GENIE in XSUM. The results are presented in Table 5 When reducing the number of steps 2, GENIE experiences significant decline, with an average score of 4.20 in the AVG Drop column, while AR- RR-DIFFUSION exhibits a comparatively smaller
1he time consumed each step in the inference process is exactly the same.

---

decrease of 1.34. Furthermore, with 3 steps, although the performance deterioration of GENIE is somewhat reduced, the average score still shows decline of 2.81. In contrast, AR-DIFFUSION maintains high performance level, with average score differing from the 20-step result by only 0.64. Notably, the results of AR-DIFFUSION at 3 steps are comparable to the results of GENIE at 2,000 steps. Therefore, compared to GENIE, the inference speed of AR-DIFFUSION can be accelerated by up to 600x.
Table 6: Diversity of 10 generated samples on XSUM test set and average of 10 results. The results of BART and GENIE are quoted from Lin al. [023].
Methods
BART
GENIE
AR- RR-DIFFUSION
Greedy
Beam Search
Diverse Beam Search
Typical Sample
Top-k Sample
Nucleus Sample
Sampling
Diffusion
Search
SELF-BLES J 100.0
93.4
75.6
76.9
80.2
79.1
29.3
30.4
4.4 Analysis
Diversity of Samples Diversity is key advantage of diffusion models. To measure the diversity of generated samples, We adopt the SELF-BLEU (Zhu et al. 2018 metric, in which lower score applied the pre- trained auto-regressive model BART As shown in Table AR-DIIFUSION achieves significantly higher diversity compared to the regrrregressive model. Furthermore, the diversity can be comparable to GENIE with better performance.
indicates higher diversity. In Lin al. [0233] various sampling methods
21.2
21.2
20
20.8
19
20.6
20.2
20.2
16
20.0
-
Alt-Ditfastoo wr ektpping
-
Ale Alt-Diffusion w skipping
skipping GENIE w/ DDIM
GENIE simpping
15
18.0
10
20
40
100
10
20
40
100
100
(8)
(b)
Figure 2: Ablation experiments XSUM and taking k 5. The horizontal axis is the number of inference steps and the vertical axis AVG-ROUGE (ROUGE-1 ROUGE-2 2 + ROUGE-L) / 3.
Ablation Study To demonstrate the effectiveness of our proposed method, we perform ablation experiments the XSUM dataset. Our results show that both our proposed multi-level diffusion and skipping mechanism are essential for achieving the high performance of A AR-DIFFUSION.
Maintaining the skipping inference method, remove the token-level diffusion during the training process, which degenerates to GENIE w/ skipping. The comparison results are shown in Figure 2(a) It can be observed that after removing, the AVG-ROUGE score is greatly lower after steps.
The performance of applying our proposed skipping mechanism and DDIM [Song al. 2021 to AR-DIFFUSION is shown in Figure 2 The results demonstrate that the skipping mechanism consistently outperforms DDIM various inference steps. Additionally, the skipping mechanism can be easily applied to GENIE. As depicted in Figure 2 DDIM suffers significant drop in performance when the number of inference steps is less than 40. In contrast, the skipping mechanism consistently maintains good performance across all inference steps.
Specitic details written in supplementary material G

---

operatives time #iv service #sloading [unused71] less ##1 मभेर cfl stravelling northern #en #** earlier failed
14.
govemment plan lift with #8-E getting thilse to 50 public È cleaning selangor shared intended dublin college
govemment plan petition with public than prices research and public leiden cleaningp selangor discovered
16.-
government plan to deal with public spending culs to research and public sectorcare figures obtained by the lala
20.-
a government plan to deal with public spending cuts to research and public sector, figures obtained by the
The intermediate state of AR-DIFFUSION gradually generating real text from standard Gaussian noise through 20 steps. The brightness of the color represents the magnitude of the logits, with darker colors indicating larger logits. More cases are shown in the supplementary materials H
Figure 3:
Case Study By mapping the state to the token with the highest logits, we visualize the intermediate states of A AR-DIFFUSION. As depicted in Figure DIFFUSSUOI undergoes denoising process, transforming the random Gaussian noise into a coherent sentence over 20 steps, and we present 5 of them. With the progression of each timestep, compared to the tokens on the right side the sentence, the tokens on the left side demonstrate faster determination and rapid increase in the corresponding logits. This behavior is consistent with our principle of dynamic movement speed from left to right.
Related Work
AR and NAR Language Models AR models have been the dominant approach for text generation
[OpenAl 2023 Touvron et al. [023] Dong et al. 2023). but their token- token-by-token by-token generation nature often leads to unsatisfactory inference speed. To address this issue, NAR models have been developed in recent years. The NAR method is initially proposed by Guu et al. [201]]. its objective is generate the entire output sequence in parallel, thereby improving generation speed and efficiency. Subsequently, LevT [Gu et al., 2019) adopts insertion and deletion to address the lack of flexibility in NAR generation, CMLM [GGazvininejad et af.) 2019] utilizes masked language model to improve the quality of NAR generation through constant number of iterations, and CNAT (Bao et al. [2021) introduces latent variables to represent the category information of the target word to make full use of the latent representation. However, these NAR methods are hard to model inter-token position dependency and deficient in generation performance.
Continuous Text Diffusion introduced by Li et al. [022a]. Through the embedding and rounding processes, the direct integration of continuous noise into word embeddings was accomplished. After that, more people attempt to adopt continuous text diffusion model to solve sequence-to-ssqqence tasks. DiffuSeq [Gong et al.) 2022) divides the input into two parts, utilizing one part condition, and perturbs the other part with noise. CDCD Dieleman et al.] 2022) proposes score interpolation and time warping to allow diffusion model and Euclidean embedding to share the same loss function for training. SeqDiffuSeq
The application of diffusion models to continuous text space is first
(Yuan et al. 2022). GENIE [Lin et al. 2023) and DINOISER (Ye et al., 2023) incorporate diffusion model into the encoder-decoder structure through cross-attention mechanisms.
important to highlight the differences between our method and both ARDMs [Hoogbboom et al. 2022 and TimeGrad (Rasul et al. 2021), despite the common references to autoregression and diffusion in all these. ARDMs employ an order-agnostic technique, leveraging masking and prediction for generation in arbitrary orders. On the other hand, TimeGrad integrates RNN and diffusion to model the conditional distribution of future steps of multivariate time series. In contrast, our research focuses implementing the diffusion process within continuous embedding space, with the primary aim of generating text in a left-to-right sequence.
6 Conclusion
This paper introduces AR-DIFFUSION, which exhibits AR-like generation behavior but enables efficient parallel decoding. Embracing the inherent sequential nature of language, we propose multi-

---

level diffusion model, consisting of sentence-level and token-level components, to assign dynamic movement speeds tokens. Consequently, compared to those on the right, the left tokens undergo fewer denoising steps and generate earlier to subsequently influence the later ones. Furthermore, we introduce a skipping mechanism to facilitate parallel generation within the multi-level diffusion framework. The experimental results across various tasks demonstrate that AR- RR-DIFFUSION surpasses existing diffusion models in terms quality while maintaining diversity, Additionally, compared to existing diffusion language models, AR-DIEFUSION achieves comparable results while being 100x ~ x faster.
7 Acknowledgements
This research is supported by National Natural Science Foundation of China (Grant 5o.62276154), Research Center for Computer Network (Shenzhen) Ministry of Education, the Natural Science Foundation of Guangdong Province (Grant No. 2023A 0223A15150122 5012914), Basic Research Fund of Shenzhen City (Grant No. JCYJ20210324 22001220002 and 108022210801 (44830254400007), the Major Key Project of PCL for Experiments and Applications (PCL202 and Overseas Cooperation Research Fund of Tsinghua Shenzhen International Graduate School (HW2021008).
References
OpenAl. GPT-4 technical report. CoRR, abs/2303.08772 2023, doi: 10.4850VarXxx.2230.8777 URL https://doi... org/ /0. 48550/arXiv 2303.08774
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, Aurélien Rodriguez, Armand Joulin, Edouard Grave, and Guillaume Lample. Llama: Open and efficient foundation language //doi models. CoRR, tabs/2302.13977 2023. doi: (0.485550arXx..2300..2222 13971. org/10. 4855000.855//000 arxiv 2302 13971
Rohan Taori, Ishaan Guirajani, Tianyi Zhang, Yann Dubois, Xuechen Li, Carlos Guestrin, Percy Liang, and Tatsunori B. Hashimoto. Stanford alpaca: An -oolloction-ollowiing llama model. _alpcca 2023.
https://gitthe
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, E. ukasz Kaiser, and Illia Polosukhin. Attention is all you need. In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, edi- tors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017. URL ttttps://proceedingg wewpssennurrppppp cc/ wwtpppprrfilleeeeeeeeeeeeeeeeeee htt.:/llle//ppe//11///1. #ffee44444raee1ftoo3ccccccooaaa3 Paper pdff
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models few-shot learners. Advances in neural information processing systems, 13:1877-1901, 2020.
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan- Tien Lin, editors, Advances Neural Information Processing Systems 33: Annual Con- ference Neural Information Processing Systems 2020, NeurlPS 2020, December 6- 12, 2020, virtual, 2020. URL
http://oocediing..eeerrrrrpppppp www..ip...cppppee////00/...0 wwtpccc/ppppppeeeeeeeeeeeeeeee happer/2200/hahhh
html
Xiang Lisa Li, John Thickstun, Ishaan Gulrajani, Percy Liang, and Tatsunori Hashimoto. Diffusion- LM improves controllable text generation. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022a. URL https://openrevier wwt:/ooommiid-eeeee 3r
Shansan Gong, Mukai Li, Jiangtao Feng. Zhiyong Wu, and Lingpeng Kong. Diffuseq: Sequence to sequence text generation with diffusion models. CoRR, abs/2210.0892 2022. doi: 10.48550/ 1r.0v.2210.08933. URL htttps://doi. org/ 48550/arXiv 2210.08993
10

---

Sander Dieleman, Laurent Sartran, Arman Roshannai, Nikolay Savinov, Yaroslav Ganin, Pierre H Richemond, Arnaud Doucet, Robin Strudel, Chris Dyer, Conor Durkan, et al. Continuous diffusion for categorical data, arXiv preprini Stti:22/11.50000 2022.
Hongyi Yuan, Zheng Yuan, Chuanqi Tan, Fei Huang, and Songfang Huang. Seqdiffuseq: Text diffusion with encoder-decoder transformers, 2022.
Jiasheng Ye, Zaixiang Zheng, Yu Bao, Lihua Qian, and Mingxuan Wang. Dinoiser: Diffused
conditional sequence learning by manipulating noises, 2023.
Mike Lewis, Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, Abdelrahman Mohamed, Omer Levy, Veselin Stoyanov, and Luke Zettlemoyer. BART: denoising sequence-to-sqquenee pre-training for natural language generation, translation, and comprehension. In Dan Jurafsky, Joyce Chai, Natalie Schluter, and Joel R. Tetreault, editors, Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, ACI. 2020, Online, July 5-10, 2020, pages 7871-7880. Association for Computational Linguistics, 2020. doi: 10.18653/v1/222..e. acl acl-aain. 703. URL https://doi. org/ 10. 1ww11/1661/10/// acl -11111111- maann. 703
Weizhen Qi, Yu Yan, Yeyun Gong, Dayiheng Liu, Nan Duan, Jiusheng Chen, Ruofei Zhang, and wow.nac-tt--Seuunneeeeeeeeeeeeee
In Findings of the Association for Computational Linguistics: EMNLP 2020, pages 2401-2410, Online, November 2020. Association for Computational Linguisties. doi: 10. 10.18653/v1/2220 wrg. findings-enninnn emmlp.mmlppp.. 217
Ming Zhou. ProphetNet: Predicting future n-gram for
findings-emll.2277. URL
Weizhen Qi, Yeyun Gong, Jian Jiao, Yu Yan, Weizhu Chen, Dayiheng Liu, Kewen Tang. Houqiang Li, Jiusheng Chen, Ruofei Zhang, al. Bang: Bridging autoregressive and non-autoregressive generation with large scale pretraining. In International Conference on Machine Learning, pages 8630-8639, PMLR, 2021.
Junyi Li. Tianyi Tang, Wayne Xin Zhao, Jian- Yun Nie, and Ji-Rong Wen. ELMER: A non- autoregressive pre-trained language model for efficient and effective text generation. In Yoay Goldberg, Zornitsa Kozareva, and Yue Zhang, editors, Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, EMNLP 2022, Abu Dhabi, United Arab Emirates, December 7-11, 2022, pages 1044-1058. Association for Computational Linguistics, 2022b. URL atttps://aclanthatt
acl
org/2022..... 2022. mmnlp-main... 68
Yafu Li, Leyang Cui. Yongjing Yin, and Yue Zhang. Multi-granularig optimization for non- autoregressive translation. In Yoav Goldberg, Zornitsa Kozareva, and Yue Zhang, editors, Proceed- ings of the 2022 Conference on Empirical Methods in Natural Language Processing, EMNLP 2022, Abu Dhabi, United Arab Emirates, December 7-11, 2022, pages org
Association for Com-
putational Linguistics, 2022c. URLpttps::/ htattts://aclanthol.og.
main..in.... 339
Yu Bao, Shujian Huang, Tong Xiao, Dongqi Wang, Xinyu Dai, and Jiajun Chen. Non-autoregreesivee translation by learning target categorical codes. In Proceedings of the 2021 Conference of the North
American Chapter of the Association for Computational Linguistics: Human Language Technolo-
giex, pages 5749-5759, Online, June 2021. Association for Computational Linguisties. doi: 10. 18653/v ma222..macc-mmin.455.. URL
org
2021. wwtp:22nnnnna..... - -ma.i.aiii.... 458
Zhenghao Lin, Yeyun Gong, Yelong Shen, Tong Wu, Zhihao Fan, Chen Lin, Nan Duan, and Weizhu Chen. Text generation with diffusion language models: A pre-training approach with continuous paragraph denoise, 2023.
Jiatao Gu, James Bradbury, Caiming Xiong, Victor OK Li, and Richard Socher. Non-autoregressive neural machine translation. arXiv preprint ar
2017.
Shashi Narayan, Shay B. Cohen, and Mirella Lapata. Don't give me the details, just the summary! topie-aware convolutional neural networks for extreme summarization. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pages 1797-1807, Brussels, Belgium, Oetoher-November 2018. Association for Computational Linguistics. doi: 10.18653/v 1/D18- 10-00100...... 1206. URL httpps://cclattholllaa www.olgg...gggD-o-- 1206

---

Karl Moritz Hermann, Tomas Kocisky, Edward Grefenstette, Lasse Espeholt. Will Kay, Mustafa Su- leyman, and Phil Blunsom. Teaching machines read and comprehend. C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems. volume 28. Curran Associates, Inc., 2015. URL httpps:/ httelttttt:///rootoo //pooceedgs/ heterssseerrppps cc/ccccpapa.. cc/paper_.. files/paper 2atp://///////f1fee/// http://eeeee.0001111000000000000
Paper pdf
Shankar Kumar and William Byme. Minimum bayes-risk decoding for statistical machine translation. Technical report, JOHNS HOPKINS UNIV BALTIMORE MD CENTER FOR LANGUAGE AND SPEECH PROCESSING (CLSP), 2004.
Dayiheng Liu, Yu Yan, Yeyun Gong, Weizhen Qi, Hang Zhang, Jian Jiao, Weizhu Chen, Jie Fu, Linjun Shou, Ming Gong, et al. Glge: A new general language generation evaluation benchmark. In Findings of the Association for Computational Linguistics: ACI-IJCNI,P 2021, pages 408-420, 2021.
Jason Lee, Elman Mansimov, and Kyunghyun Cho. Deterministic -atoorgrerssvvvee neural sequence modeling by iterative refinement. arXiv preprint arXiv: 2018.
Marjan Ghazvininejad, Omer Levy, Yinhan Liu, and Luke Zettlemoyer. Mask-predict: Parallel decoding of conditional masked language models. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pages 6112-6122 Hong Kong. China, URL
November 2019. Association for Computational Linguistics. doi:
https://aclanthoolggy wrgg 1633
Jiatao Gu, Changhan Wang, and Junbo Zhao. Levenshtein transformer. In Advances in Neural Information Processing Systems, pages 11181-11191, 2019.
Mitchell Stern, William Chan, Jamie Kiros, and Jakob Uszkoreit. Insertion transformer: Flexible
sequence generation via insertion operations. arXiv preprint arXiv: 2019.
Klaus Greff, Rupesh Kumar Srivastava, Jan Koutník, Bas R. Steunebrink, and Jürgen Schmidhuber. LSTM: A search space odyssey. IEEE Trans. Neural Networks Learn. Syst., 2210022222222 2017.
Bill Yuchen Lin, Wangchunshu Zhou, Ming Shen, Pei Zhou, Chandra Bhagavatula, Yejin Choi, and Xiang Ren. CommonGen: A constrained text generation challenge for generative commonsense reasoning. In Findings of the Association for Computational Linguistics: EMNLP 2020, pages 1823-1840, Online, November 2020. Association for Computational Linguistics. doi: 10. 18653/v11 1020.findinss-emlp...6. URL http:ttt///claaanooolooooo
org/ 2rgg/020... findings-ennnn eeaeiinnggeennpppppmmmm 165
Jiatao Gu, Zhengdong Lu, Hang Li, and Victor K. Li. Incorporating copying mechanism in sequence-to-sequeme learning. In ACL (1). The Association for Computer Linguistics, 2016.
Raymond Hendy Susanto, Shamil Chollampatt, and Liling Tan. Lexically constrained neural machine translation with levenshtein transformer. ACL, pages 3536-3543. Association for Computational Linguistics, 2020.
Yaoming Zhu, Sidi Lu, Lei Zheng, Jiaxian Guo, Weinan Zhang, Jun Wang, and Yong Yu. Texygen: A benchmarking platform for text generation models. In The 41st international ACM SIGIR conference on research development in information retrieval, pages 1097-1100, 2018
Jiaming Song, Chenlin Meng, and Stefano Ermon. Denoising diffuusion implicit models. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria. May 3-7, 2021. OpenReview.net, 2021. httLltttt/////peeeeeeie .ttt:/forrm..ddtttiiiaaaatttttt
Chenhe Dong, Yinghui Li, Haifan Gong, Miaoxin Chen, Junxin Li, Ying Shen, and Min Yang. A survey of natural language generation. ACM Comput. Surv., 55(8):173111173:33, 2023. doi: 10.1145/3554727. https:////o 10. 1445/3554727
Emiel Hoogeboom, Alexey A. Gritsenko, Jasmijn Bastings, Ben Poole, Rianne van den Berg, and Tim Salimans. Autoregressive diffusion models. In International Conference on Learning URL 2022.
Representations, 2022,
12

---

Kashif Rasul, Calvin Seward, Ingmar Schuster, and Roland Vollgraf. Autoregressive denoising diffusion models for multivariate probabilistic time series forecasting. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 8857-8868. PMLR, 18-24 Jul 2021. html
URL BRIlhttss: :tttpps://prooe http:/::///oceeeegs.... mmr. wwwpprresssviee.
Taku Kudo and John Richardson. SentencePiece: A simple and language independent subword tokenizer and detokenizer for neural text processing. In Proceedings of the 2018 Conference Empirical Methods in Natural Language Processing: System Demonstrations, pages 66-71, Brussels, Belgium, November 2018, Association for Computational Linguistics. doi: 10. 18.18353/v1/ D18-2012. B.t.bbtts://aclaanhollgg. orr//18-21//
Calvin Luo. Understanding diffusion models: A unified perspective. arXiv preprini www.i:2208..11900000 2022.
Yisheng Xiao, Lijun Wu, Junliang Guo, Juntao Li, Min Zhang, Tao Qin, and Tie- Yan Liu. A survey on non-autoregressive generation for neural machine translation and beyond. CoRR, abs/2204.09269, 2022.
Ashwin K. Vijayakumar, Michael Cogswell, Ramprasaath R. Selvaraju, Qing Sun, Stefan Lee, David J. Crandall, and Dhruv Batra. Diverse beam search: Decoding diverse solutions from neural sequence models. CoRR, abs/1610.02424, 2016.
Clara Meister, Tiago Pimentel, Gian Wiher, and Ryan Cotterell. Typical decoding for natural language generation. CoRR, abs/2202.00666, 2022.
Angela Fan, Mike Lewis, and Yann N. Dauphin. Hierarchical neural story generation. In ACL (1), pages 889-898. Association for Computational Linguisties, 2018.
Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi. The curious case of neural text degeneration. In ICLR. OpenReview.net, 2020.
13

---

A Limitation
primary limitation of our work lies in the requirement of generating a large number of candidate samples for optimal performance. As an illustration of CNN/DAILYMATI dataset, AR- DIFFUSION (k 50) achieves a 0.8 lower ROUGE-2 score compared to AR-DIFFUSION (k 500). We anticipate exploring more efficient sampling strategies to minimize the number of generated samples without performance drop.
B Experimental Details
Model Setup Our model configuration is implemented based on Transformer-Be [Vaswani et al. 2017]. In particular, For XSUM and CNN/DAILYMAIL, we set the diffusion embedding dimension to 128. For IWSLT14, we use 64-dimensional diffusion embedding, attention heads and 1024-dimensional feed-forward layers. For COMMONGEN, we adopt 64-dimensional diffusion embedding, 8 attention heads and 512-dimensional feed cor-ffoward layers.
Training and Inference In the training phase, we employ a square-root noise schedule and 2,000 diffusion steps [Li al. 2022a|. Specially, we use the tokenizer and vocabulary constructed by Byte Pair Encoding (BPE) Kudo and Richardson 2018 for translation tasks. For other tasks, we adopt the tokenizer and vocabulary of bert uncased.
Baselines
We set four groups of baselines:
2017]. iNAT [Le et al. 2018 NAR: NAT [Gu et al.
CMLM Ghazvininejad et al.
2019 LevT
Gu et al. 2019 and CNAT Bao et al.
2021];
Semi-NAR: InsT Stern et al. 2019 iNAT Lee et al.
2018 CMLM GGaavvininejad et al.
2019
and LevT Gu al.
2019]
AR: bRNN Guu et al.
2016). LSTM Greff et al.
2017 and Transformer Vaswani et al. 201
Diffusion: DiffusionL.M [L et al. 2022a
CDCD
Dieleman et al. 2022 SeqDiffuSeq Yuan
al. 2022 DINOISER Ye al. 2023 and GENIE
Lin et 2023
Metrics We follow the approach of Qi et al. 2020 13
to evaluate the ROUGE-1/2/L of the summarization task. For the evaluation of translation tasks, we adopt the setting of SeqDiffuSeq Yuuan
et al. 2022) to report BLEU score. In addition, we also calculate the SacreBLEU score according the setting of DINOISER YYe al., 2023 for comparison. For COMMONGEN, ROUGE-2/11 BLEU-3/4, /, METEOR and SPICE under the evaluation methods Lin et al. 2020 16
employ
Table 7:
Training Parameter Settings. Batch Size mini batch size x Nge x GPU number, Optimized Steps total steps/ / Nges and N₂ is gradient accumulation number.
Dataset
Lr & Schedule
Batch Size
Optimized Steps
Target Length
XSUM CANIDAILYMAIL
8e-4 & Cosine
128x3x8
80,000 3
50
8c-4 Cosine
80x5x8
100,000 /
180
IWSLT14 DE-
2e-3 & Cosine
192x2x8
160,000 2
90
IWSLT14 DE
1.8e-3 Cosine
768x x8
60,000
COMMONGEN
3e-4 & Constant
384x 1 x
40,000
54
Training Parameters Our training parameters on difffrrnt datasets are shown in Table 7 Our linear schedule warm up steps is 4,000 x N where Nge denotes gradient accumulation number. In addition, use the AdamW (weight decay 0.0) optimizer and dropout is 0.2. All experiments implemented on 8 Tesla V100-32G. It takes about 20 hours to train XSUM and CNN/DAILYMAIL, about 5 hours to train IWSLT14, 14, and about 2 hours to train COMMENGEN.
"We train bpe the training set, and follow the vocabulary size of MiSbirsee,WSSTTII is set to 10,000.
metrics
14

---

C More Results on IWSLT14
In Table 8 we give the SacreBLEU score according the setting of DINOISER. AR-DIFFUSION has notable improvements over non-auto-regressive CMLM. Besides, AR- ARRDIIFFUSINN achieves excellent performance among text diffusion models for both EN-+DE and DE-EE tasks. Specifically, ARR-DIFFUSION is far superior to GENIE and comparable to the newly proposed DINOISER at 50. Nevertheless, the performance stronger than DINOISER when 500
Table 8: SacreBLEU on the IWSLT14 test set. This result follows the setting of DINOISER.
IWSLT14
Methods
DE DE->N
EN-DE
Transformer (AR, beam 5)
Vaswani
2017
33.61
28.30
CMLM (NAR, k = 5)
Ghazvininejad al.
2019
29.41
24.34
DiffusionL.M (k- 50)
Li al. 2022a
29.11
22.91
DINOISER 50)
Ye al. 2023
31.61
26.14
GENIE 50) [Ln al.
2023
29.45
23.89
AR-DIFFUSION (A 50)
31.80
26.01
AR- RR-DIIFUSION (A: 500)
32.35
26.51
D Comparison of Runtime Speed
We also compare the runtime speeds of GENIE and AR-DIFFUSION by measuring the time taken for each sample generation, denoted as seconds per iteration (s/it). To ensure precision in our measurements, we sample 50 cases from the CNN/DAILYMAIL dataset. The generation process speed comprises two main components: function evaluation (FE, which is equivalent to the model forward computation) and MBR. All experiments are conducted on an A A100-40G GPU and 50 CPUs.
The results are presented Table 9 It is evident that for & < 50, the MBR duration is minimal and can be negligible relative to NFE. Furthermore, remains approximately twice as efficient as GENIE (k: = 10 and step = 2000).
when t 500 and step 20, AR- RR-DIFFUSION
Table 9: Comparison of inference speed between GENIE and AR- AR-DIFFUSION.
GENIE
AR-DIFFUSION
10
10
50
500
Steps
2000
20
20
20
Speed of NFE (s/it)
47.54
0.25
0.61
2.12
21.03
Speed of MBR (s/it)
0.02
0.02
0.02
0.08
7.14
Total Speed (s/it)
47.56
0.27
0.63
2.20
28.17
ROUGE-2 in XSUM
8.78
8.68
9.32
10.1
10.6
E Impact of Minimum Bayes Risk and Anchor Point
Minimum Bayes Risk To investigate the relationship between the number of generated candidate samples (k) and the quality of generation, we generate varying numbers of samples, ranging up to 1,000, on the IWSLT14 De- test set and present the results in Figure 4 The curve demonstrates an initial gain of approximately 0.5 SacreBLEU within the first 200 samples, after which the gain becomes insignificant with generating more samples.
We conduct experiments on AR- IR-DIFFUSION using different anchor points (ne; f.a). These anchor points vary in terms of nhe values, namely 1.0 x N. 2.0 N and 3.0 x N, where N denotes the target sentence length. Additionally, they share a common t. value of T', which represents
Anchor Point
DINOISER has shown in their Figure 4 that their method is not better with larger k.
15

---

the total time step of diffusion. We present the results in Table 10 and determine that the best result achieved (meg te) (2.0 N, T).
32.4
Table 10: Effect of anchor point at different po- sitions the IWSLT14 DE-EN test set. "N" indicates the target sequence length and "T" repre- sents the total time step of diffusion.
SacreBLEU
32.2
32.0
31.8
Le SacreBLEU
1.0 X
N
T
31.23
Sample Number (n)
2.0 X
N
T
31.80
Figure 4: Relationship between the number of candidate samples for applying MBR and SacreBLEU on IWSLT14 4 DE-+NN test set.
3.0 T
N
31.58
F Proof of Inference with Skipping
During the inference process, skipping strategy requires the model go to infer the state = at far-off timestep 4++1 compared to the current state 2,,² where 1,+1 < 4. In our model, due to the dynamic speed setting, token " with smaller timestep 4++1 S 4, which is closer to 44+1, and positions n1 S n2 can provide stronger auxiliary information than z!!. This reduces the difficulty of inferring states for tokens in the end, making our multi-level diffusion model particularly suitable for accelerating the generation process.
Through maximizing the evidence lower bound (ELBO) of p(zo), the training object is equivalent to minimize the divergence between (=z//z zo) and p=(===1/z; following [Luo] 2022
By converting the joint probability distribution into a conditional probability distribution, we obtain the following formula for g( (0),) 20).
(( |Rt, 20) g( 11, #t, 20) g( Rec 20)
q( [z zu) ( g(Zt441-1 2o)
q( |24-2, 20) g (( 12/241112/22--11 20) (( 11 20)
(13)
4-4441
0(5,,6//%,- 20)
Similarly, we reach the same conclusion regarding po 12t.)
Based on equation 13 which consists of q(>z|==-1, 20). and the interchangeability between
q(<g 2 20) and po 2 2z), we can decompose q( (( |2,,, 20) by incorporating 2t, and zo. and utilize our estimated to determine the expression of pa (...).
g(Ztmmn
2ty 20)
II
a ((n.ees)) 1=fone)) 25)
(14)
m=l
16

---

Next, we obtain the explicit expression q f(m.tr))))) ((m,e)) 20) between "/mm,)) and 26.
through linear interpolation
2( (( (6)))))) g(=7(ma)) 1) 25)9(27 =6)
((37(mn))) =8)
ag(mn)) (eBimnni osondit) Anneei (1 d /V
fmmtttt V va (1- ((dd4))))
N (T (ar() at,)1)
(3)6d))
(#)(m))))) vouus22) 20)
x xeep {-
2(1 as(miie41)
(((nit)))
af(m)tt1))
+ (z)())))) (a
1 (m.t)))))
a (1 a((((141)
- ās, W4 (11 a
2 2(
"stad41))
exp
27(0.1.)
2(1 3et11
af((,,)))
/ (ās((ntt-))))
As(me)))
20 *Mmmstti))
1 af(nitt)
(1 a(((41t))))
as(ns))
xN (f)
as(nitet)) 20.
5r, (11 - cxoz 1) 1)
acst1
āe;
= =N(efindee)) Aef(mnes) + Mas ol)
(15)
where we have the following notations for simplification.
afinit)) (1 11-0gpe (((ttt)))
af(n))))
(1 (1,ssss) (((()))))))
-ff(nt)
-ff(nee)))
af(nn)))))
Building upon equation 15
substitute =ij with go (27))))) (n, f); Φ),, yielding the final formula
for pe (2)().)441) ()(n,.) 2)) as the following equation.
po (2 =7(a))))) ~ (xftmean Aaminn + ugo (= f(n, t); x),
(16)
G Different Sampling Methods of BART
The sampling methods used by Lin et al. (2023) including Greedy Search, Beam Search Xiao et al.
2022). Diverse Beam Search(diversity strength 0.8) Vijayakumar al. (2016). Typical Sample
(T = 1.2) Meister et al. [2022). Top-k Sample (k 50) Fan et al. (0088 and Nucleus Sample (p
0.92) Holtzman al. [2020].
Specifically, greedy search is to select the token with the highest probability at each step. Beam search select the largest token from among the beams with higher probability at each step. Diverse beam search is to divide the beams into multiple groups at each step and ensure the difference between groups by calculating the diversity score between groups. Typical sampling selects samples through discrete random process. Top-k sampling is to randomly select one of the & candidate tokens with the highest probability each step. Nucleus sampling is to randomly select one token each step from the candidate tokens whose probability density is greater than
H More Cases
17

---

92-
#eft hmm northem hacker support by yells lion on [umused698] tennis bars named! #dis C? 1898 1682kz limp
14.0-
british soldier who killed by an amy 43 lifted losers requested ##ged prosecutor of verbell of rogers
british soldier who was killed by ammy in intersect has been named upon a pmseculor of deep ofise fo process.
a british soldier who was killed by an ammy in ash has been named by the ministry of crucial of championships
a british soldier who was killed by an army afghanistan been named by ministry of defence of moddra.
120
praxy oxidation #ih #ift a #Hilaonate ##winpuri saskatoon amplitude 1702 ##I è the servalstraße ##:
barcelona
plaque for spain 's first #dalis war amid been be in the histodc fleet of sorummik say, the #Hl of 2003 dso fee. #Hip
plaque for spain first world war has been added century city liverpool say, the britain in g
plaque for spain 's first world war has been be in the historic city of liverpool say, the amazing of serum in post..
200
plaque for spain 's first world war has been unveiled in the historic city of liverpool the first britain the years..
12.0
sis, angelicu6 breach #lbosttcc [unused557] fires sale why organizational interception originates Siniia #Mpp knots
china 's prime minister creators it conceming the 800 -Sin beach 1728 withdrowal [unused308]
#**e attending
china prime minister says is the 'ity emissions country 's [unused697] foundation
engine
china 's prime minister says is the emissions in the country 's lq ctsis the engine of R [unused887]
35.0
china 's prime minister says is the emissions in the country 's economic crisis, the engine of parlaamett
18


Reviews:
[{"review_id": "sT8bjjy2eb", "reviewer": "Reviewer_CQLg", "summary": "This work introduces left-to-right sequential characteristics into diffusion models, enhancing the text generation performance of diffusion models. By considering the AR model as a diffusion model with two states: to be decoded and already decoded, AR-Diffusion defines a continuous diffusion model with decreasing diffusion speeds from left to right. Experiments on various text generation tasks show that AR-Diffusion achieves improvements over existing diffusion models.", "questions": "  1. Which decoding method does the Transformer use, greedy search or beam search? If beam search is used, what is the beam search size of each reported Transformer result?", "limitations": "AR-Diffusion requires a large number of candidates to achieve better results. Although generating hundreds of samples has large generation overhead, AR-Diffusion achieves promising results with MBR decoding.  I think the large number of candidates is not a serious issue in the current stage.\n\nReference  \n[1] Gao, Z., Guo, J., Tan, X., Zhu, Y., Zhang, F., Bian, J., & Xu, L. (2022). Difformer: Empowering diffusion model on embedding space for text generation. arXiv preprint arXiv:2212.09412.\n\n[2] Ye, J., Zheng, Z., Bao, Y., Qian, L., & Wang, M. (2023). Dinoiser: Diffused conditional sequence learning by manipulating noises. arXiv preprint arXiv:2302.10025.\n\n[3] Qian, L., Wang, M., Liu, Y., & Zhou, H. (2022). Diff-glat: Diffusion glancing transformer for parallel sequence to sequence learning. arXiv preprint arXiv:2212.10240.\n\n[4] Post, M. (2018, October). A Call for Clarity in Reporting BLEU Scores. In Proceedings of the Third Conference on Machine Translation: Research Papers (pp. 186-191).", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "  1. The idea of introducing the left-to-right inductive bias into diffusion models for text generation is straightforward and reasonable.\n  2. By controlling the number of inference steps and generation candidates, AR-Diffusion can achieve tradeoff between quality and efficiency, which is more flexible than the Transformer.\n  3. Compared with the autoregressive model (BART), the generation of AR-Diffusion is more diverse", "weaknesses": "  1. I think the authors overclaim the decoding speedup. First of all, most diffusion baseline models in the paper have no advantage in both generation quality and efficiency compared with the Transformer. Thus, AR-Difffusion should compare with the Transformer for decoding efficiency. Besides, existing diffusion models can achieve competitive results with much fewer steps. For example, Difformer[1] and Dinoiser[2] can achieve competitive scores with 20 steps, and Diff-GLAT[3] can even generate high quality sequences with only 3 steps. Therefore, I think more comprehensive experiments should be conducted to claim decoding speedup.\n  2. Although the AR-Diffusion achieves better BLEU scores than that of the Transformer in Table 3,  the results in Table 8 of Appendix C shows that the Transformer is still better than AR-Diffusion. Why are the results in the two tables contradictory? As SacreBLEU is a more standard metric for machine translation[4], does the results indicate that AR-Diffusion still lags behind the Transformer with a certain gap？", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your careful review, and I will elaborate on each of your concerns below.\n\n**Q1: I think the authors overclaim the decoding speedup. First of all, most diffusion baseline models in the paper have no advantage in both generation quality and efficiency compared with the Transformer. Thus, AR-Difffusion should compare with the Transformer for decoding efficiency. Besides, existing diffusion models can achieve competitive results with much fewer steps. For example, Difformer[1] and Dinoiser[2] can achieve competitive scores with 20 steps, and Diff-GLAT[3] can even generate high quality sequences with only 3 steps. Therefore, I think more comprehensive experiments should be conducted to claim decoding speedup.**\n\nA1: \n\n1. We claim that AR-Diffusion achieves 100× faster than SeqDiffuSeq in machine translation and 600× faster than GENIE in line 58, this can be verified by NFE in Figure 3 (AR-Diffusion and SeqDiffuSeq) and Figure 5 (AR-Diffusion and GENIE). \n2. To compare the decoding efficiency between AR-Diffusion and AR (Transformer), we conduct additional experiments for them where they share the same model architecture and size. In comparison, we randomly select 50 samples from the CNN/Daily Mail test set. The beam size of AR (Transformer) is set to 5, which achieves the best performance. We also generate 50 candidate samples using AR-Diffusion with 20 inference steps. Additionally, the computation of MBR is also included in the time cost of AR-Diffusion. We use 1 A100-40G and 50 CPUs for the experiment. The running time of each case is averaged, and we report the time in seconds per case (s/it) for comparison. The results demonstrate that AR takes 5.30s, whereas AR-Diffusion only takes 2.18s. Therefore, it is evident that the speed of AR-Diffusion is faster than that of AR. \n3. We run DINOISER in CNN/Daily Mail and XSum, and you can check A1 in [Author Rebuttal by Authors](https://openreview.net/forum?id=0EG6qUQ4xE&noteId=vkeE6NZjqk) for more details. Through generating 50 candidate samples, the performance of DINOISER is worse than AR-Diffusion, even the AR-Diffusion with 2 steps and 10 candidate samples (Table 5). For Difformer, they do not release their code. \n4. Diff-Glat is not a continuous diffusion based language model. The main contribution of Diff-Glat is to develop a residual glancing strategy for NAR, and it is common for NAR model to generate sentence with 3 steps.\n\n**Q2: Although the AR-Diffusion achieves better BLEU scores than that of the Transformer in Table 3, the results in Table 8 of Appendix C shows that the Transformer is still better than AR-Diffusion.Why are the results in the two tables contradictory? As SacreBLEU is a more standard metric for machine translation[4], does the results indicate that AR-Diffusion still lags behind the Transformer with a certain gap？**\n\nA2: While our model's performance in terms of the SacreBLEU on IWSLT14 is not as strong as AR's, AR-Diffusion outperforms AR on various other datasets, particularly in summarization tasks such as CNN/Daily Mail and XSum. Additionally, AR-Diffusion demonstrates notably higher diversity in comparison to the auto-regressive model, as indicated by Table 6. It is foreseeable that researchers may devise improved selection strategies beyond MBR, leading to the much better samples among these diverse candidate samples.\n\n**Q3: Which decoding method does the Transformer use, greedy search or beam search? If beam search is used, what is the beam search size of each reported Transformer result?**\n\nA3: The result of AR in the paper is beam search, and the beam size is 5.\n\nWe hope our answers have resolved your concerns. If you have any other concerns, please feel free to let us know. Thanks again for your review.\n"}, {"review_id": "gIsTMtqTZr", "reviewer": "Reviewer_i56m", "summary": "This paper introduces a diffusion method optimized for the autoregressive text generation scheme. They employ different movement speeds for denoising with respect to the token positions. Specifically, they apply a lower movement speed to right-side tokens to guide models to reflect information in left-side tokens. Based on the dynamic movement speed method, they also propose a skipping mechanism during inference for efficient decoding. Experimental results show that the proposed method outperforms the previous diffusion-based approach at the same NFE, and the average performance drop is much lower in an extremely limited number of inference steps. In ablation experiments, they show that both AR-diffusion and the skipping mechanism are effective and the skipping mechanism can be applied to the other diffusion-based model.\n\n\n", "questions": "- Have you compared the decoding speed between AR-Diffusion with an inference step of 2 or 3 and NAR models?\n- Would AR-Diffusion also be robust to infilling tasks?", "limitations": "Since the model configuration of AR-Diffusion is based on Transformer-base in the paper, it would be possible to conduct a scalability study for various sizes in future work.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- The methodology is highly intuitive and well-motivated. \n- The proposed method is simple while mathematically supported and powerful. \n- They conduct experiments in various text-generation tasks to show not only consistent performance but also the efficiency of their method.\n- The skipping mechanism can be effectively applied to the other diffusion model.", "weaknesses": "- Additional case studies comparing with GENIE or (N)AR models would provide further insights.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your valuable suggestions, and we will reply to your questions one by one below.\n\n**Q1: Additional case studies comparing with GENIE or (N)AR models would provide further insights.**\n\nA1: The following two tables are the results generated by GENIE and AR-Diffusion for the same case. It can be seen that AR-Diffusion has a clear tendency to generate from left to right, while GENIE is generated irregularly.\n\n|GENIE Case|\n|:----|\n|[unused487] ع in [unused673] [unused285] response constituted ##司 ##iaceae [unused744] ##ː hart ##elial － annapolis yep trent in [unused302] support |\n|stability hit 博 tyne the helping embassy unbeaten former knesset australian and ##play [unused99] interacting have short sickness the struggle of one by syria .|\n|leave only withdrawn from the uk embassy of the built australia and ##play [unused99] benton in hour controversial the killing of the uk russia .|\n|from only withdrawn from midfielder uk embassy of reasonable built australia and with who were aground active controversial the killing of the in syria .|\n|britain has withdrawn from the uk embassy in london , australia and israel who were among in for the killing of the in countries .|\n\n|AR-Diffusion Case|\n|:----|\n|co₂ stomped out [unused673] ##δ did boxed ##ɣ ##iaceae kannada cheap hart avoided [unused285] [unused654] ##® 崎 in|\n|britain has withdrawn from midfielder uk of reasonable built trent ##play [unused99] benton aground pondered tightening|\n|britain has withdrawn from midfielder uk embassy in london and australia with blah tramway lowlands parana 忄##orescence [SEP] ##？|\n|britain has withdrawn from the uk embassy in london and australia after israel who were have intercontinental ی [unused174] £5 戸|\n|britain has withdrawn from the uk embassy in london and australia after israel who were in dubai for the killing of the country .|\n\n**Q2: Have you compared the decoding speed between AR-Diffusion with an inference step of 2 or 3 and NAR models?**\n\nA2: Different frameworks of the AR-Diffusion and NAR hinders the fair comparison. However, in theory, due to the parallel decoding mechanism of both NAR and AR-Diffusion, their decoding speed mainly depends on the number of function evaluations (NFE), in other words, the number of model forward compuatation. Thus, if NAR model has the same inference step, or decoding iterations in NAR research[1], then the decoding speed are comparable. If the NAR model requires lots of steps, then AR-Diffusion is faster.\n\n[1] A Survey on Non-Autoregressive Generation for Neural Machine Translation and Beyond.\n\n**Q3: Would AR-Diffusion also be robust to infilling tasks?**\n\nA3: We are now trying to pretrain AR-Diffusion for textual generation. One of the pre-training tasks we choose is infilling like T5 and UL2. From the observed loss curve, the loss is indeed gradually decreasing, indicating that AR-Diffusion can also be applied to filling tasks. We are currently conducting the experiment and will release these results in the next version.\n\n**Q4: Since the model configuration of AR-Diffusion is based on Transformer-base in the paper, it would be possible to conduct a scalability study for various sizes in future work.**\n\nWe will conduct scalability research on various scales of AR-Diffusion in the next version.\n\nWe hope our answers have resolved your concerns. If you have any other concerns, please feel free to let us know. Thanks again for your review.\n"}, {"review_id": "MOrxSsikJl", "reviewer": "Reviewer_63dm", "summary": "This paper presents AR-DIFFUSION, a diffusion model that displays auto-regression-like generation behavior. The primary contributions of this work can be summarized as follows:\n1)\tA multi-level diffusion strategy is proposed, encompassing both sentence-level and token-level diffusion.\n2)\tA skipping mechanism is introduced, which works in tandem with the multi-level diffusion strategy to expedite the process.\n3)\tThe superiority of the model over existing diffusion language models is verified in terms of text generation tasks and inference efficiency.", "questions": "Please answer the questions mentioned in the Weaknesses section.", "limitations": "NA", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The author presents an approach for integrating an auto-regressive-like mechanism into the diffusion model for text generation and has conducted comprehensive experiments to validate the efficacy of the proposed method. The idea of incorporating autoregressive dependency into the diffusion model is captivating.", "weaknesses": "I find the experiments in this paper insufficiently convincing.\n\nMy primary concern is that the main gains appear to be derived from MBR. With the skipping mechanism, the per-sentence generation step is reduced from 2000 to 20. This gives you chances to use K=500 for MBR, which is really large, as MBR is N^2 in computation.  The NFE metric is somewhat misleading, as it only considers the number of model forwards and does not account for the MBR process. It would be more appropriate to report the runtime speed of all methods for a fair comparison.\n\nThe comparison with baselines is not exhaustive. To substantiate the claim that their method benefits from introducing auto-regressive dependency back into text diffusion models, the authors should compare additional diffusion baselines, such as DIFFUSEQ and SeqDiffuSeq, with the same diffusion steps and candidates used in MBR, rather than just GENIE.\n\nMoreover, GENIE itself reported a Rouge-L score of 41.2 on CNN/Daily Mail, while the table in this paper shows only 32.1. This discrepancy should be clarified in the main text. If the lower score is due to a smaller parameter size, why not increase it to match GENIE's level? If the proposed method is effective, it could potentially be comparable to models like BART. As it stands, the parameter size of AR-Diffusion is too small to demonstrate its superiority.\n\nFurthermore, the comparison with NAR methods is not solid enough. Baselines such as CMLM and LevT were proposed three years ago. More recent methods like DA-Transformer should be included for a more comprehensive comparison.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for taking the time to review our paper, and I will explain your concerns in detail below.\n\n**Q1: My primary concern is that the main gains appear to be derived from MBR. With the skipping mechanism, the per-sentence generation step is reduced from 2000 to 20. This gives you chances to use K=500 for MBR, which is really large, as MBR is N^2 in computation. TheNFE metric is somewhat misleading, as it only considers the number of model forwards and does not account for the MBR process.It would be more appropriate to report the runtime speed of all methods for a fair comparison.**\n\nA1: Please let me address your primary concern by breaking it down into two parts.\n\n1. NFE is a common way to compare inference speed within diffusion-based language models. \n    1. When generating the same number of candidate samples (k), the time taken to calculate MBR between different diffusion models is considered identical. The most critical factor at this point is the number of function evaluations (NFE), or the number of model forward, enabling a relatively fair theoretical comparison among different models. \n    2. In the following table, it can be observed that the time taken to calculate mbr (\\~0.1s) is 20 times shorter than the time taken for NFE (\\~2s) when generating k≤50 samples. Therefore, in this situation, we consider it to be negligible. \n    3. Table 5 presents a comparison of the inference efficiency between AR-Diffusion and GENIE, using the same number of generated candidate samples (k). In Table 3, our model with only 20 inference steps (the 5th line) outperforms SeqDiffuSeq's performance with 2000 steps (the 4th line) when generating 1 candidate sample. Thus, we claim that our model achieves a speed improvement of 100 times compared to SeqDiffuSeq in machine translation and is 600 times faster than GENIE.\n    4. We present k=500 is to illustrate that if the resources and time are sufficient, the performance can still be gradually improved as the number of generated candidate samples increases.\n2. We report the runtime speed of GEINIE and AR-Diffusion in the following Table. \n    1. To avoid randomness, we select 50 samples from the CNNDM dataset, and each sample generates K candidates. Then calculate the total sampling time divided by the number of samples (50) to get the time required for each sample to perform NFE. Then calculate the time required to pick the best candidate by MBR. All experiments are 1 A100-40G and 50 CPUs.\n    2. From the table, we can observe that when k≤50, the MBR time is very small, which is negligible compared to NFE. So in this case, we can measure the decoding speed of the model through the NFE indicator. In addition, when k=500, step=20, although the time has increased, AR-Diffusion is still nearly twice as fast as GENIE (k=10, step=2000). In particular, the number of function evaluations (NFE) is actually the forward propagation number of the model.\n|    |GENIE|AR-Diffusion|    |    |    |\n|:----|:----|:----|:----|:----|:----|\n|K|10|10|10|50|500|\n|Steps|2000|3|20|20|20|\n|Speed of Model Forward (NFE) (s/it)|47.54s/it|0.25s/it|0.61s/it|2.12s/it|21.03s/it|\n|Speed of MBR (s/it)|0.02s/it|0.02s/it|0.02s/it|0.08s/it|7.14s/it|\n|Total Speed (s/it)|**47.56s/it**|**0.27s/it**|**0.63s/it**|**2.20s/it**|**28.17s/it**|\n|ROUGE-2 in XSum|8.78 |8.68|9.32|10.1|10.6|\n\n**Q2: The comparison with baselines is not exhaustive. To substantiate the claim that their method benefits from introducing auto-regressive dependency back into text diffusion models, the authors should compare additional diffusion baselines, such as DIFFUSEQ and SeqDiffuSeq, with the same diffusion steps and candidates used in MBR, rather than just GENIE.**\n\nA2: Please check A1 in the [Author Rebuttal by Authors](https://openreview.net/forum?id=0EG6qUQ4xE&noteId=vkeE6NZjqk). \n\n**Q3: GENIE itself reported a Rouge-L score of 41.2 on CNN/Daily Mail, while the table in this paper shows only 32.1. This discrepancy should be clarified in the main text. If the lower score is due to a smaller parameter size, why not increase it to match GENIE's level? If the proposed method is effective, it could potentially be comparable to models like BART. As it stands,the parameter size of AR-Diffusion is too small to demonstrate its superiority.**\n\nA3: In line 142 of Section 4.2, we mentioned that GENIE selects the best sample by calculating the maximum score for each generated one using ground truth, leading to unfairness. To ensure a fair comparison with our method, we re-implement GENIE and use the MBR method to select the best sample.\n\nDue to our model not undergoing pre-training, making a fair comparison with pre-trained BART is currently challenging. Nevertheless, we are currently developing a pre-trained model and intend to conduct a comprehensive comparison with BART in the next version.\n\n**Q4: Furthermore, the comparison with NAR methods is not solid enough. Baselines such as CMLM and LevT were proposed three years ago. More recent methods like DA-Transformer should be included for a more comprehensive comparison.**\n\nA4: Thanks for your suggestion. We will supplement these experiments in the next version.\n\nWe hope our answers have resolved your concerns. If you have any other concerns, please feel free to let us know. Thanks again for your review.\n\n"}, {"review_id": "0xAICUZbEe", "reviewer": "Reviewer_TRPf", "summary": "This paper presents a diffusion model on text generation. The idea is generally interesting. It learns to diffuse sentence-level and token-level diffusion, where the latter one is diffused with dynamic movement speeds.Its experiments are well-designed and its empirical results are strong.", "questions": "1. I wonder if the skipping mechanism can also be applied to other diffusion models.\n2. In Algo2 line 6, where does n come from? Do you enumerate n? \n3. In Diffusion-LM, there is a rounding operation as Algo 2 line 9 at each diffusion step. It seems AR-Diffusion do not requires such rounding operation at each step. If true, would DPM-Solver help accelerating the diffusion process?\n4. GENIE is the main (almost the only) diffusion model baseline in the experiments, but some related baselines are mssing, such as DiffuSeq [1], CDCD[2], Difformer [3], DINOISER[4] and RDM[5]. It seems the authors already noticed some of them in the related work wonder, and I think it would be helpful to include more complete baselines.\n\nIf my conerns are addressed, I'm willing to raise my score. \n\nReferences\n1. Gong et al.  Diffuseq: Sequence to sequence text generation with diffusion models 2022\n2. Dieleman et al. Continuous diffusion for categorical data 2022\n3. Gao et al. Difformer: Empowering Diffusion Models on the Embedding Space for Text Generation, 2022\n4. Ye et al. DINOISER: Diffused Conditional Sequence Learning by Manipulating Noises 2023\n5. Zheng et al. Reparameterized Discrete Diffusion for Text Generation 2023", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "1. The method is interesting  with a perspective to discuss autoregressive and non-autoregressive diffusion models.\n2. The skipping mechanism is useful to accelerate the generation process.\n3. The empirical results are strong.", "weaknesses": "1. The paper is hard to follow, and the writing should be improved.\n2. Limited diiffusion model baseline and missing some related baselines.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for taking the time to review our paper, in response to your concerns, we will give the following explanations.\n\n**Q1: The paper is hard to follow, and the writing should be improved.**\n\nA1: Our approach is designed to apply the inherent sequential features of natural language to diffusion language models. AR-Diffusion ensures that the generation of tokens on the right depends on the tokens generated on the left, by employing a dynamic number of denoising steps that vary according to the token position. \n\nWe will polish the writing in the next version, and open our code so that other researchers can reproduce it.\n\n**Q2: I wonder if the skipping mechanism can also be applied to other diffusion models.**\n\nA2: Yes. Our skip mechanism can be seamlessly applied to other diffusion models. As depicted in Figure 2(c), we also apply the skip mechanism to GENIE, which yields superior results compared to DDIM + GENIE.\n\n**Q3: In Algo2 line 6, where does n come from? Do you enumerate n?**\n\nA3: $n$ in Algo2 line 6 indicates the n-th token, which is explained in Line100 Page3. ($n$ is in $\\\\{1,...,N\\\\}$, where $N$ is the target sentence length.) In the process, we assign different token-level timesteps for each token according to the sentence-level timestep and its position.\n\n**Q4: In Diffusion-LM, there is a rounding operation as Algo 2 line 9 at each diffusion step. It seems AR-Diffusion do not requires such rounding operation at each step. If true, would DPM-Solver help accelerating the diffusion process?**\n\nA4: Since we are following the Diffusion-LM and GENIE, we also implement the rounding operation at each step, i.e., the map to nearest operation in Algo2 line 9. Although we would very much like to use DPM-Solver to speed up the diffusion process, it does not seem to be adaptable.\n\n**Q5: GENIE is the main (almost the only) diffusion model baseline in the experiments, but some related baselines are mssing, such as DiffuSeq [1], CDCD[2], Difformer [3], DINOISER[4] and RDM[5]. It seems the authors already noticed some of them in the related work wonder, and I think it would be helpful to include more complete baselines.**\n\nA5: Thank you for your valuable suggestions. \n\n1. In Appendix Table 8, we compared the results on the IWLST14 dataset with those in the DINOSIER and Diffusion-LM papers.\n2. For the latest baselines you mentioned, CDCD, Difformer and DINOSIER were not open-sourced before NeurIPS submission, so we could not reproduce it accurately. Recently, DINOISER and DiffuSeq have released their code, and we also run their code in summarization, namely, CNN/Daily Mail and XSum. You can refer to A1 in the [Author Rebuttal by Authors](https://openreview.net/forum?id=0EG6qUQ4xE&noteId=vkeE6NZjqk) for more details. We will add all the comparision in the next version.\n3. Only GENIE has been experimented on CNNDM and XSUM datasets, and release their code, so we compare with GENIE.\n\nWe hope our answers have resolved your concerns. If you have any other concerns, please feel free to let us know. Thanks again for your review.\n"}]

Author rebuttal:
**Q1: Compare with more diffusion language models.**

A1:  We have compared AR-Diffusion with SeqdiffSeq in the Table 3 , and compare with DINOISER and Diffusion-LM in the appendix Table 8. Furthermore, we enrich the comparision with more baselines in the following table. Due to the unavailability of source code for CDCD and Difformer, we choose to perform experiments using DiffuSeq and DINOISER on the CNN/Daily Mail and XSUM datasets.

1. In the case of DINOISER, we employ the same architecture as iwslt_base_postnorm in the DINOISER code. Furthermore, we adhere to the same hyperparameters utilized in IWSLT. The training process is facilitated by bf16. For CNN/Daily Mail, DINOISER is trained for a total of 65 hours spanning 200 epochs. In the case of XSum, the training duration is 37 hours for 200 epochs. During inference, we adhere to the procedure described in the DINOISER paper, wherein we generate 50 candidate samples and subsequently select the best one using MBR.
2.  For Diffuseq, it undergones training for approximately 33 hours with fp32, which equates to roughly 22 epochs. Furthermore, due to Diffuseq's generation process involving 2000 steps, generating one candidate necessitates approximately 7.5 hours. Consequently, we restrict the generation to only 5 candidate samples. To ensure fair comparison, we also included AR-Diffusion with k=5 in the result.
3. All experimental procedures were executed on a total of 8 A100-40G machines. 
4. Analysis of the table reveals that AR-Diffusion outperforms alternative diffusion language models, whether for k=5 or k=50. This observation substantiates the effectiveness of our proposed methodology.
|    |Step|CNN/Daily Mail|    |    |XSUM|    |    |
|:----|:----|:----|:----|:----|:----|:----|:----|
|Metrics|-|ROUGE-1|ROUGE-2|ROUGE-L|ROUGE-1|ROUGE-2|ROUGE-L|
|Diffuseq(k=5)|2000|18.1|3.1|16.1|25.5|5.3|19.6|
|AR-Diffusion(k=5)|20|**23.8**|**10.3**|**22.1**|**30.5**|**8.9**|**23.5**|
|    |    |    |    |    |    |    |    |
|GEINIE(k=50)|20|29.3 |8.3 |21.9|34.4 |12.8 |32.1|
|Dinoiser(k=50)|20|24.5|7.1|19.2|35.7|13.4|33.2|
|AR-Diffusion(k=50)|20|**31.7**|**10.1**|**24.7**|**39.6**|**16.3**|**37.1**|


Meta-review: This paper presents an innovative approach to text generation called Auto-Regressive Diffusion (AR-Diffusion), which incorporates the inherent sequential characteristics of natural language into diffusion models. The authors introduce a dynamic number of denoising steps based on token position, allowing for more effective generation of token sequences. Through experiments on various text generation tasks, the proposed method demonstrates superior performance over existing diffusion language models while also offering faster generation times. For the question raised by Reviewer 63dm, I think the authors gave a good response. Therefore, I recommend to accept this paper.
Decision: Accept (poster)