Speculative Decoding: Lossless Speedup of Autoregressive Translation
Authors: Heming Xia
Tao Ge
Si-Qing Chen
Furu Wei
Zhifang Sui
Venue: Submitted to ICLR 2023 (2023)

Abstract: Different from some previous work accelerating autoregressive translation (AT) at the sacrifice of quality, we propose Speculative Decoding (SpecDec) -- a novel decoding paradigm inspired by speculative execution in computer architecture, which combines respective advantages of AT and non-autoregressive translation (NAT) for lossless speedup of translation. At each decoding step, SpecDec first speculatively drafts (i.e. decodes) next $k$ tokens with an NAT model and then verifies them with an AT model, where only the drafted tokens passing the verification are accepted as decoded tokens for guaranteeing its translation result is exactly the same as AT. The collaboration of NAT drafting and AT verification leads to a much higher decoding speed without quality loss due to parallel computing enabled by speculative decoding.

We conduct experiments in 4 standard WMT translation benchmarks and confirm the vanilla SpecDec yields exactly the same results as AT greedy decoding with an around $3\times$ speedup, and that its variant (SpecDec++) with an advanced verification strategy not only outperforms AT greedy decoding, but also further improves the decoding speed, resulting in an around $5\times$ speedup over AT. Moreover, SpecDec can be easily generalized for speeding up other seq2seq tasks like Abstractive Summarization, and benefit more from stronger computing devices, demonstrating its potential to become a de facto decoding standard in the future for efficient and lossless seq2seq generation.

Under review as a conference paper at ICLR 2023
SPECULATIVE DECODING: LOSSLESS SPEEDUP OF AUTOREGRESSIVE TRANSLATION
Anonymous authors Paper under double-blind review
ABSTRACT
Different from some previous work accelerating autoregressive translation (AT) at the sacrifice of quality, we propose Speculative Decoding (SpecDec)- a novel decoding paradigm inspired by speculative execution in computer architecture, which combines respective advantages of AT and non-autoregressive translation (NAT) for lossless speedup of translation. At each decoding step. SpecDec first speculatively drafts (i.e. decodes) next & tokens with an NAT model and then veri- fies them with an AT model, where only the drafted tokens passing the verification are accepted as decoded tokens for guaranteeing its translation result is exactly the same as AT. The collaboration of NAT drafting and AT verification leads to a much higher decoding speed without quality loss due to parallel computing enabled by speculative decoding.
We conduct experiments in 4 standard WMT translation benchmarks and con- firm the vanilla SpecDec yields exactly the same results as AT greedy decoding with an around 3x speedup, and that its variant (SpecDec++)) with an advanced verification strategy not only outperforms AT greedy decoding, but also further improves the decoding speed, resulting in an around 5x speedup over AT. More- over, SpecDec can be easily generalized for speeding up other seq2seq tasks like Abstractive Summarization, and benefit more from stronger computing devices, demonstrating its potential to become a de facto decoding standard in the future for efficient and lossless seq2seq generation. We will release all our codes and checkpoints facilitate reproducing our results.
INTRODUCTION
Since the Transformer (Vaswani et al. 2017) prevailed in Natural Language Processing (NLP), au- toregressive decoding has become the de facto standard for neural machine translation (NMT) as well as other generation tasks, because is easy train and reliable to generate high-quality results. Despite its advantages, autoregressive translation (AT) has been widely blamed for its poor inference efficiency, motivating non-autoregressive translation (NAT). Unlike AT which sequentially decodes only one token at each iteration so that the next token prediction can condition on the previous de- coding results, NAT decodes tokens in parallel without depending on the surface form of previous tokens, largely improving the inference efficiency.
Recent research NAT mainly focuses on improving its translation quality to bridge the perfor-
mance gap between NAT and AT (Gu et al. 2018 Qian et al.) 2021 Geng et al., 2021 Savinov al. 202T. Until now, however, NAT's performance still less reliable than AT, NAT is more difficult than AT given its unawareness of the conditional dependence of translated tokens.
Given AT's reliable generation results and NAT's high efficiency, we propose an approach named Speculative Decoding (SpecDec) to combine their advantages, inspired by speculative execution [ to accelerate translation without quality loss compared with AT. SpecDec decomposes a decoding iteration into two substeps: draft and verify: At each iteration, SpecDec first speculatively drafts (i.e.. decodes) a fixed number of tokens?) in parallel through NAT; Then, the drafted tokens are verified
'Speculative exccution some task in advance to avoid delays that would have to be incurred by doing the task after is known that it required (hotps: / / k ped' i org/ww/w k Specul 1 at We use "a block of drafted tokens" to denote them in the following parts of this paper.
optimization technique used in computer architecture where a system performs
in)..

---

Under review as a conference paper at ICLR 2023
Source Sentence
What are the basic physcca laws of the Universe?
Input
[BOS]
Was
(MASK]
[AASK]
[MASK]] phycea
[MASK]
[MASK]
Draft (NAT)
[BOS)
Was
Sind
di
schen
Grundee
X
X
Verify (AT)
[BOS]
Was
sind
dic
grundlegendenn EDtarcation
icchen
Grundoo
Output
[BOS]
Was
gnindlegndden
Next Input
[BO5]
Was
sind
dic
grundlegenden
[MASK]
[AASK]
[MASK]
[MASK]
[MASK]
Figure 1: Speculative Decoding where a decoding iteration involves two substeps: draft and verify. In the Draft substep, an NAT model speculatively drafts (i.e., decodes) a block (block size k = 5 for this example) of tokens parallel conditioning on the source sentence and previously decoded tokens (i.e., the tokens in the rectangle boxes). In the Verify substep, drafted tokens are verified in parallel: bifurcation is detected as the first position where we find the drafted token does not match the top-1 1 result verified by an AT model. The drafted tokens after the bifurcation position are all discarded, for guaranteeing SpecDec's translation is exactly the same with greedy decoding of AT.
by an AT model in an autoregressive manner to determine how many of them match AT's (top-1) results and thus can be accepted as translation results, as Figure In contrast to conventional AT which decodes at a low speed, AT verification is highly efficient because it performs in parallel; more importantly, it helps guarantee SpecDec's is translation is identical to AT, resulting a desirable balance between translation speed and quality, shown in Figure 2
In addition to the vanilla SpecDee whose translation is required (strictly by the top-1 I matching criterion in AT verification) to be identical to greedy decoding advanced vari-
4.5x
of AT, we propose SpecDec++ ant of SeecDec by slightly relaxing the rigid require- ment during AT verification. SpecDec++ not only yields translations beyond greedy decoding, but also prevents good drafted tokens from being discarded just because they are different from greedy decoding results, leading to a higher inference speedup.
4.0x
Translation Speed-up
AT
ATwiND
3.0x
MullTaa
2.5x
SUNDAS
Reerle
Loogless
SpacDacce
The experiments in four standard WMT bench- marks show that SpecDec can yield exactly the same translations as greedy decoding of AT with a 3x speedup and that variant SpecDec++ can out- perform greedy decoding with an even higher (~ 5x) speedup. Moreover, the SpeeDec paradigm can be casily generalized to other seq2seq tasks like Abstractive Summarization and benefit more from stronger computing devices. Its lossless quality and promising speedup results demonstrate its great po- tential evolve into de facto decoding standard for efficient seq2eq generation in the future.
1.5x
1.0x
27.5
28.5 Translation quality (BLEU)
28.0
29.0
Figure 2:
Translation quality and effi- ciency of models on WMT14 EN-DE. The speedup baseline (1.0x) ) is the Transformer- base (Vaswani et al. 2017)) with beam search. All models above except "AT" are trained with KD by Transformer-big teacher.
2
BACKGROUND
2.1 AUTOREGRESSIVE TRANSLATION
Given source sentence (x1, ......
x. and the target sentence y (y/1 1/2, , Wm)) an au- toregressive translation (AT) model is trained with the target distribution of conditional probabilities based on the chain rule:
LA = log P(y æ;; OxT) Eog P (ya yei, QxT)
where y<a denotes previous target tokens before the 5t position. As Eq 11 shows, AT model is trained via the teacher-fir teacher-forcing strategy that uses target tokens as previously decoded tokens, which performs efficiently as the probability P (yx yei, a) at each iteration be calculated in parallel.
2

---

Under review as a conference paper at ICLR 2023
During inference, AT model sequentially predicts output tokens given preceding decoded tokens:
ý = arg max
log P (uj yej æ; OAT)
where " = (91. ....... Fm)) is the predicted output sentence.
Although AT offers desirable translation quality, its sequential decoding scheme with limited paral- lelism largely reduces its decoding speed, being its main efficiency bottleneck.
2.2 NON-AUTOREGRESSIVVE TRANSLATION
To accelerate inference, non-autoregressive translation (NAT) (Gu al. 2018) removes sequential dependence between target tokens with conditional independence assumption:
N Σ log P (yk
a;; (NAT)
In contrast to AT that will not start predicting y until y-jj are completely decoded, NAT decodes the output sentence in parallel, which much more efficient than AT:
arg
log (35 zx; ORNNT)
On the other hand, however, the conditional independence assumption makes it hard to train an NAT model well, leading to degradation in translation quality despite an improvement in decoding speed.
3 SPECULATIVE DECODING
Given the fact that AT translates better whereas NAT performs faster, we propose Speculative Decod- ing (SpecDec) to combine their respective advantages, inspired by speculative execution, to achieve lossless acceleration for seq2seq generation. Specifically, SpecDec decomposes every decoding it- eration into two substeps draft and verify:
Draft At each iteration, SpecDec first utilizes NAT model to simultaneously decode block of drafted tokens (denoted as [MASK] in its decoder input in Figure [ speculatively, conditioning
on preceding translated tokens. Formally, given the source sentence : = (Æ1, 22....2...... Zn)) and the previously translated tokens yoj (y1, 191.92..... ...,,. Uj). SpecDec decodes the next k (drafted) tokens block in parallel:
E log P (Mi++ Bss. ar; 0sKT)
arg
HaGX
Verify Then, the drafted tokens リイ+1--f+h verified with AT model in the autoregressive manner, which performs in parallel. We find the bifurcation position e by comparing the drafted tokens with the autoregressive decoding results conditioning the draft as F
1 (Ts+z + De+1)
arg max
isisk k
9 arg max log P(is+ Bss. -1- ²xT)
where 1(.) is the indicator function and ūح+ز the top-1 1 result verified by the AT model conditioning
on the previously translated tokens yı; and the drafted tokens --. We only accept the verified tokens before (including) the bifurcation position as translated tokens, which ensures that SeecDec yields the same results as greedy decoding of AT:
Vi+1o-ffe Dstt (Ui+1--+to11 Di+e)
We iterate decoding with the above substeps until the termination condition is met, i.e. the [EOS] token is decoded or the sentence reaches the maximal length. As illustrated, SpecDec is highly efficient because both draft and verify perform in parallel.
We ÿ denote NAT's translations, while use denote AT decoded/verified translation results.
3

---

Under review as a conference paper at ICLR 2023
Source Sentence
What are
the basic ptysiccal las of the Universe?
Input
[B06]
Was
[MASK]
JMASKI
[MASK]]
[MASK]
[MASK]
Draft (NAT)
[ROS]]
Was
sind
dic
Ischan
Grundipg
Verify (AT)
[B06]
grundllgendden
Grundgo
gesetze
-
[blrkk]
[Blank]
physipe
[Hlank]]
[barkk]]
[bank]]
[Dlank]]
physee
[blank
[blank]
Output
[BOS]
Was
sind
die
phy-3p
lichen
Grundig
gesetre
Next Input
[BOS]
Was
sind
di
physee
Ischen
Grundee
MASKI
[MASK]
[MASK]
[MASK]
[MASK]
Illustration of SpecDec++. Compared to the vanilla SpecDec strictly requiring the drafted tokens to match the top-1 result of the AT verifier, SpecDec++ slightly relaxes the criterion trust NAT's draft more, by only requiring the drafted tokens to fall in the top-3 candidates of verifier with tolerable log-likelihood gap (not shown in this Figure; see Eq (7)). As result, SpeeDec++ allows more drafted tokens to be accepted even if they are slightly different from the top-1 result of the AT verifier, leading to a higher inference speedup.
Figure 3:
3.1 NAT DRAFTER
As demonstrated above, an NAT model is the key to speculative decoding, which can efficiently generate block of drafted tokens in parallel. Our NAT drafter differs from other NAT models two aspects: First, we only require the NAT drafter decode a block (i.e., fixed length) of tokens in each decoding iteration, instead of the whole sequence; Second, as illustrated in Figure I since we decode from Left to Right, the NAT drafter is required to decode tokens conditioning on the previously decoded tokens. Formally, given the source sentence æ (Z1, .nn and the randomly sampled prefix Уsp (0 S p < m) of the target sentence y = (1/1 ... 9m), the model trained to predict the next k tokens, as shown in Figure 1
p-
LAAT
log P (y: Msps 2z; ONAT)
s=P+1
In addition, we leverage the glancing strategy following Qian et al. (2021) which exploits cur- riculum learning during training to get better performance. As in previous NAT work, we apply sequence-level knowledge distillation (D) (Kim & Rush 2016) by an autoregressive Trans- former teacher model to train our NAT drafter.
3.2 AT VERIFIER
We the conventional Transformer (see Section 2.1 anteeing translation quality. As we hope as many drafted tokens by the NAT model as possible can be accepted by the AT verifier for a higher speedup. we also apply Seq-KD the AT verifier by a shared teacher (with the NAT drafter), which not only allows the NAT drafter and AT verifier to perform similarly, but also improves the AT verifier's translation quality (Furlanello et al. 2018).
our AT verifier, which is the key guar-
4 SPECDEC++
As shown in Figure D and discussed in Section B the vanilla SpecDec only accepts the drafted tokens that match the top-1 result of the AT verifier, which guarantees that SpecDec's translation identical greedy decoding AT. However, the top-1 results are not necessarily better than the drafted tokens. As result, the strict verification criterion (i.c.. top-1 matching) will result in many good drafted tokens being discarded just because they are different from the top-1 result the AT verifier, which limits the speedup of SpecDec.
To overcome this limitation, we propose a variant of SpecDec named SpecDec++, which illus- trated in Figure Instead of the rigid t matching requirement shown in Eq (5), SpecDect+ relaxes the criterion to trust NAT's draft more, by only requiring the drafted tokens to fall in top-8 candidates with tolerable (log-likelihood) score gap (away from the top-1 result):
4

---

Under review as a conference paper at ICLR 2023
05++ Mi+s, if SpecDec+ requirement is met
same as Eq (5)
otherwise
As discussed above, SpecDec++ requirement is met if Eq
6 and
are both true:
log PM5++ Msj. ax; 0NXT) 2 log P( Wsj My +1: OxT)
(6)
log P yıi U5 11+1-144-111 x; xx) - log P(i++ + Uss z; @ S
(7)
where log P( the top-3 ranked result's log-likelihood score by the AT verifier.
The advanced verification criterion with the hyperparameter top-3 and tolerance only allows more drafted tokens to be accepted for higher speedup but also enables SpecDec++ to yield trans- lations beyond greedy decoding.
EXPERIMENTS
5.1
EXPERIMENTAL SETTINGS
Datasets and Evaluation We mainly evaluate our approach on the most recognized machine trans- lation benchmark: WMT14 English- English-German German translation which contains 4.5M translation pairs for training. Following prior work (Ott et al. 2018), we adopt newstest-13 as our validation set for finding the best hyperparameters
model checkpoints, and test on newstest- /4. We use 32K Byte Pair Encoding (BPE) (Sennrich et al. 2016) subwords"] lowing prior work in NAT, we report BLEU (Papineni et al., 2002) to facilitate translation quality comparison. For inference efficiency, speedup over beam search. Specifically, we test the inference speed by running the model with one sentence time (batch=1 I using fairseq implementationf on Nvidia P100 GPU.
the joint source-target dictionary. Fol-
use both the average number of decoding iterations and
In addition to WMT14 EN-DE, we also test SpecDec on WMT14 DE-EN and WMT16 EN-RO/RO- EN benchmarks, as previous NAT work.
Model Configuration We mainly conduct experiments on the most commonly used base-size Transformer /Vaswani et al. 2017) architecture. The Transformer-bas/ has 6-layer encoder and 6-layer decoder. Its embedding/FFN dimension/#heads are 512/2.048/8. We use the model architec- ture for both the drafter (NAT) and the verifier (AT). We apply sequence-level knowledge distillation as discussed in Section 3.1 3.2 for both the drafter and verifier using a shared teacher. Following recent iterative NAT work (Saharia et al. 2020; Savinov et al. 202T), we use the Transformer-big as the teacher for WMT14 EN-DE/DE-EN and use YYansformer-basee for WMT16 EN-RO/RO-EN, which all train with the raw training set and generate the distilled training set with beam search (b 5). We include model training details in Appendix A
5.2 MAIN RESULTS
The translation quality and speedup results on WMT14 EN-DE are presented in Table 1 Unlike previous NAT approaches that are inferior to AT with Seq-KD (i.e., our AT verifier), SpecDec in- troduces an around 3x speedup with exactly the same translation quality as (autoregressive) greedy decoding by our AT verifier, truly achieving lossless acceleration. SpecDec++ further improves the results by relaxing the strict top-1 matching criterion: slightly relaxing (i.e.. SpecDec++ high- quality) allows us achieve better translation than greedy decoding even approaching the beam search result with higher speedup (3.0x + 3.6x). and little more aggressively relaxing (i.e., SpecDec++ high-efficiency) further accelerates inference (3.6x - 4.5x) owing to the acceptance of more tokens despite a marginal loss of translation quality.
"We use the same BPE tokenization and vocabulary Ghazvininejad et al. 2019
5 'We report performances with various batch sizes in Appendix /https://// thub. com wwwp///twwc/////ccototoooooococt weyytorchaairrree raeq Beam search (b 5) is our speed baseline (1.0x)
also include results a Transformer with a deep encoder and a shallow decoder in Appendix R.5 As a reference, the teacher models of Saharia et al. (2020) achieve 29.5 and 32.2 BLEU in WMM144EN-DD and DE-EN respectively, which stronger than our teachers achieving 29.3 and 32.1 respectively.
5

---

Under review as a conference paper at ICLR 2023
Models
Iter.
Speedup
WMT14
WMT16
DE-EN
EN-RO
RO-EN
AT baseline
Transformer-base (w/o Se
1.0x
27.74
31.09
34.28
33.99
NAT Fertility (Gu 2018
15.6x
17.69
21.47
27.29
29.06
CTC
(Libovicky & Helel
018
17.68
19.80
19.93
24.71
AXE
Ghazyimmee jad et
2122aa
23.53
27.90
30.75
31.54
GLAT (Vian
15.3x
25.21
29.84
31.19
32.04
Fully NAT
OaXE (Du et il.
26.10
30.20
32.40
33.30
AligNAKT (Sing all
2021
13.4%
26.40
30.40
32.50
33.10
DSLP (Haaig
14.8x
27.02
31.61
34.17
34,60
F-VAE Gu Kone 2021
16.5x
27.49
31.10
33.79
33.87
REDER (Zheng et 202
5.5%
27.50
31.25
33.60
34.03
DA-TranStorner [Fusing 2022a
13.9%
31.37
INAT Le 2018
10
21.61
25,48
29.32
30.19
CMLM mizz vin et al. 2019
10
1.7x
18x
27.03
30.53
33.08
33.31
LevT Gu 2019
4.0%
3.7x
27.27
33.26
SMART
add
20206
10
1.7x
1.8%
27.65
31.27
DisCo Kassi crai 2020
4.8
3,5X
27.34
31.31
33.22
33.25
Iterative NAT
Imputer Sanarii al 2020
3,9%
28.20
31.80
34.40
34,10
Multi- NXT (Hao
2021
1.7x
188
27.98
31.27
33.80
33,60
RewriteNAT Geng el cla
4021
2.7
3.1X
288%
27.83
31.52
33.63
34.09
SUNDAE (Savinov a.
2021
1.4X
28.46
32.30
CMLMC Huaing
28.37
31.41
34.57
34.13
Teacher
29.31*
32.11*
34.72
34,49
NAT drafter (N
25)
1.6
14.3x
26:48
30.23
32.08
32.21
AT verther (b 5)
1.xx
28.89
32.53
34.96
34.86
verifier (b
34.83
34.65
SpecDec (t = 25)
4.9
3,0%
28.73
32.18
34.83
34,65
SpecDec++ (k 25, high-quatity)
4.0
3.6x
28.89
32,56
35.32
34.98
SpecDec++ (e 25, high (efiiener)))))))
32.19
34.92
Table Results of SpecDec on four standard WMT benchmarks. For inference efficiency, we report the averaged decoding iteration (denoted as Iter.) and speedup on WMT14 EN-DE. The results that truly match outperform autoregressive decoding (i.e., AT verifier with 1) are highlighted in red. AT baselines' results are from Ghazvininejad et al. (2019). indicates results obtained by Transformer-big. denotes models distilled by a Transformer-big model. While speedup numbers reported by the previous papers (left column) devices and environments, we reran some of them that are open source using the same device and environment and report their speedups (right column), observing significant difference.
not strictly comparable to ours due to different
By looking into the results, our NAT drafter's translation quality is better than the majority of early fully NAT work but inferior to most iterative NAT approaches. Compared with the NAT models including complicated mechanisms such length prediction, length beam, reranking, and CTC that slow down the efficiency per iteration our NAT drafter is simple and straightforward. As a result, its decoding efficiency per iteration higher decoding iterations on average. The acceptable translation quality and high efficiency of our NAT drafter significantly help accelerate autoregressive decoding, playing instrumental role lossless acceleration of Sec.Dec.
comparable to fully NAT despite taking 1.6
Results for other language pairs similar to WMT14 EN-DE. We include details in Table g in Appendix B.I
5.3 ANALYSIS
5.3.1
HYPERPARAMETER
Block Size We conduct experiments with various block sizes on the development and show the results in Table 2 As the block size & increases, the number of mean accepted tokens, which highly correlates with speedup and the number of decoding iterations. first increases and reaches peak when = 25. Further increasing k has an adverse effect, because it will become very hard for the model to learn translate too many tokens simultaneously given the limited model capacity, leading to drop in both efficiency and quality.
Top-3 and Tolerance 7 in SpecDec++ We study the effects of hyperparameters in SpeeDec++: top-3 and tolerance т, and show the results the development set in Table 33, Moderately increas- ing and B not only leads to an increase of mean accepted tokens since AT verification becomes
For example, RewriteNAT (Geng et al. 2021 uses length beam size slowing down its efficiency.

---

Under review as a conference paper at ICLR 2023
Models
k
Tok.
BLEU
Speed
(6 =
1.00
26.72
1.00x
Models
Top-3 3)
Top-5 (8
7.56/27.02
7.58/27.02
10
5.97
26.68
3.04x
8.64/26.92
8.77/26.92
15
6.74
26.94
3.47x
SpecDec++
9.46/26.84
9.72/26.84
SpecDec++
20
7.24
26.75
3.55x
10.04/26.78
10.50/26.
7.56
26.92
3
10.38/26.70
10.99/26.64
30
7.44
26.75
3.63x
Table 3: Results on the development set (newstest-13) with different hyperparameters in SpecDec++ (k = 25). Each cell lists the mean accepted tokens and BLEU score. The BLEU score of greedy decoding of the AT verifier is 26.62.
Table 2: The mean accepted tokens (Tok.), the translation quality (BLEU), and the efficiency (Speed) when decoding with various ber of block size k on the development set (newstest-13). The results are obtained with SpecDec++ (top-3, 1.0).
Models
Iteration
BLEU
Speed
Blockwise decoding (k
N
29.11
1.0x
Blockwise
Stern et al. 2018
Blockwise decoding (k: = 2)
/
28.95
1.7x
Blockwise decoding (k: 10)
/ 27.40
3.0x!
Teacher (Transformer big. 5)
N
29.31
1.0x
AT verifier (6 = 5)
N
29.25
1.0x
AT verifier (b 1)
N
29.18
1.1x
NAT drafter (k- =10)
3.3
27.41
7.2x
SpecDee = 10)
5.4
29.18
2.7x
Ours
SpecDec++ (k = 10. top-3, 1.0)
5.0
29.28
2.9x
SpecDec++ (k = 10. top-5, 6.0)
3.9
29.12
3.8x
NAT drafter (k 30)
1.4
27.35
15.0x
SpecDee 30)
4.8
29.18
3.0x
SpecDee++ (k 30, top-3, r 1.0)
4.2
29.32
3.5x
SpecDec++ (k = 30, top-5, = 6.0)
2.6
29.15
5.0%
Table 4: Results of SpecDec of the big-size model configuration WMT14 EN-DE and the com-
parison to the state-of-the-an Blockwise Decoding Stern et al. (2018). denotes the speedup results reported in original papers obtained by comparison with greedy decoding.
less strict but also improves the translation quality over greedy decoding. However, the translation quality will decrease if the constraints are over relaxed: the BLEU score will degrade from the peak of 27.02 to 26.64 when decoding with top-5 selection (i.e., 8 = 5) and T 5.0. Based on the results in the development set, we conservatively select / = 3, and use 5, r 3.0 as the high-efficiency SpecDec+++ to pursue the higher speedup without substantial loss of translation quality for WMT14 EN-DE as in Table []
1.0 for the high-quality SpecDec+t,
5.3.2 MODEL SIZE
In addition to models of the base-size configuration, we also study larger models to test the effec- tiveness of SpecDec. We here use Transformer-big (Vaswani al. (001)) as our model architecture for both the NAT drafter and the AT verifier in SpecDDec/SpeDecct
and compare it with the conventional Transformer-big baseline as well as Blockwise Decoding (teem et al., 2018) a state- of-the-art efficient Transformer-big variant by introducing additional t k- heads on top of the Transformer decoder to generate next i tokens as a block and verifies, which works in a similar way to ours. According to Table 4 our SpecDeccSpecDecct substantially speeds up the AT baselines and outperforms Blockwise Decoding with both better results and a higher speedup. Compared with Blockwise Decoding whose performance drops significantly when increases 10 due to its underinvestment in speculation by only using lightweight heads to generate the next few tokens in parallel, SpecDec/SpeeDeccH using an independent NAT drafter is much more powerful generate more drafted tokens that can be accepted, turning out to result in a significantly higher speedup, de- spite introducing more parameters (see Appendix for detailed discussion of memory cost issues).
10 hyperparameters (e.g., block size h Top-8, tolerance 7) in SpecDec (hig) are re-tuned the devel- opment set, which may be different from those in the basc-size models.

---

Under review as a conference paper at ICLR 2023
Models AT-base (greedy)
Drafter
Tok.
Iter.
BLEU
1.00
N
28.73
lightweight heads
2.23
11.5
28.73
SpecDec-base
NAT-base
5.53
5.0
28.73
NAT-big
5,90
4.7
28.73
lightweight heads
2.35
10,9
28.11
SpecDect+-base (top-3, 1.0)
NAT- base
6,69
4.1
28.81
NAT-big
7.32
3.8
29.12
lightweight heads
2.61
10.6
27.02
SpeeDect+-base (top-5, 3.0)
NAT-bac
8.71
3.2
28.58
NAT-big
9.73
2.8
28.98
Table 5: Results of SpecDec-base (k 30) with various sizes of drafters on WMT14 EN-DE.
Models
Iteration
R-1
R-2
R-L
Speed
Teacher
BART (Lewis et al. 2020
N
44.16
21.28
40,90
AT (w/o Seq- SD)
BART-base (b
N
42.84
20.08
39.51
1.0x
NAT drafter (h 25)
3,3
37.10
14.87
33.47
15,0x
AT verifier 5)
N
42.55
19.83
39.31
1.0x
AT verifier 1)
N
43.00
20.28
39,96
1.1x
Ours
SpecDec 25)
43.00
20.28
39,96
3.0x
SpecDee++ = 25, top-3, 1.0)
42.95
20.24
39.73
3.7x
SpecDec++ (k = 25, - 3.0)
7.9
42.02
19.42
38.66
4.8x
Table 6: Results of SSeecDec-base model CNN-DM for Abstractive Summarization.
Moreover, observe that big-size models models (A: = 25) since larger capacity equips the model with a more powerful ability to learn to decode more tokens well parallel. To better demonstrate this point, we conduct comparative study of using drafters of different sizes in SpecDec-base, given the same block size (A = 30). According Table 5 the big-size NAT drafter largely outperforms the base-size counterpart and the drafter with lightweight heads (as used in Stern et al. (2018)) performs worst, demonstrating that a stronger drafter can generate drafted tokens more reliably (i.e., on average more drafted tokens accepted by the AT verifier), resulting in fewer decoding iterations, which indicates that SeecDec may further improved if more powerful (not necessarily larger) NAT drafter is equipped.
larger block size (A: 30) than the base-size
5.3.3 OTHER SEQ2SEQ TASKS
We test SpecDec's effectiveness in one of the most representative seq2seq tasks Abstractive Sum- marization. We employ the distilled training data of CNN Daily Mail (Hermann et al.) (015) from BART (Lewis et al. 2020) to train the NAT drafter and the AT verifier whose model architectures test on the CNN Daily Mail test split following previous work.
are both BART-base,
According to Table [ the vanilla SpecDec consistently achieves exactly the same result as the AT verifier = 1), which is, to the best of our knowledge, the first work that achieves such a 3x lossless speedup for Abstractive Summarization. SpecDec++ further accelerates inference but does not show any quality improvement as observed NMT experiments because of the larger performance gap between the NAT drafter and the AT verifier in the abstractive summarization benchmark.
5.4 DISCUSSION
Extensive experiments in multiple tasks show that SpecDec can significantly speed up seq2seq gen- eration without quality loss. The state-of-the-art lossless speedup is attributed to the substantially im- proved computational parallelism that allows better utilization (hardware) computing resources. We believe SpecDec is promising and can even benefit more from evolving processor hardware that will become increasingly powerful and better at parallel computing (shown in Appendix E)
As preliminary study, SpecDec is far from perfect and has much headroom for improvement. First, according to the experimental results above, we know SpecDec's translation quality mainly depends on the AT verifier and its efficiency relies the NAT drafter (whose capability matters how many drafted tokens can be accepted). We believe more powerful NAT/AT models (than the simple and naive ones used in this paper) will benefit Deec to achieve better results.
8

---

Under review as a conference paper at ICLR 2023
Moreover, SpecDec's potential can be further exploited by optimizing its implementation in com- puting and memory access. For example, according to Table [8 showing time cost by modules in SpecDectt, naive implementation costs total of approximately 16% of overall time to (se- quentially) encode the input for AT' and NAT. Obviously, this part can be optimized by performing AT and NAT encoding in parallel because they are independent, or sharing (or partially sharing) AT's encoder with NAT, which we leave as future exploration. Also, the NAT decoder costs more than the AT decoder because employs bi-directional attention and cannot save the computation for the already decoded tokens as AT, which we believe can be improved in the future with better non-autoregressive decoding mechanism designed for SpecDec.
6 RELATED WORK
Non-autoregressive Decoding To accelerate autoregressive translation (AT), Gu et al. (2018) first proposed Non-Autoregressive Translation (NAT), which decodes the output sentence in one single iteration despite translation quality loss. Recent work mainly focused on improving the quality while
maintaining competitive speedups, including applying various training objectives (Wang et al. 2019
Wei et al. [019 (Shu et al.] 2020 |Shao et al. 2020 Guo et al.
2020: Liu et al. 202 Ding et al.
20216
Zeng et al. [022] Shao et 2002),, modeling dependencies between target tokens KKissr
et al.
2018
Sun al. 2019; Ghazvininejad et al.) 2019 Liu et al.) 2020; Bao et al.) [021] Zhan
let al.
2022
Zhu et al. 2022) and refining the translation outputs with multi-pass iterations Chan
al.
2019 Stern al. [219 (Sun & Yang (0200] Ghazvininejad al. [0220b [Ding et al. 2021a
Norouzi et al., 2002). However, due to the inherent conditional independence assumption, NAT
models' translation quality is generally less reliable than AT.
Semi-autooegrrssivve Decoding There are also some attempts trying combine autoregressive (AR) and non-autoregressive (NAR) decoding: Wang et al. (2018) proposed to utilize NAR decoding locally while keeping the AR property globally; on the contrary, Ran al. (2020) and Kong et al. (0200) introduced a local-AR model which retained the NAR property globally. Similar ideas have been also proposed for Grammatical Error Correction (GEC): Chen al.] (2020) proposed to use sequence tagger to identify the grammatical errors' spans and then use AR decoding to correct them; Aggressive Decoding (Sun et al.) 202T) the first work that introduces speculative decoding into GEC. It assumes that the input is the sentence to be generated in the future (i.e., there are no grammatical errors in the input), and then verifies the whole sentence in parallel through greedy decoding of AT. However, Aggressive Decoding works only for tasks where the input and output are highly similar, which limits its application. The most similar work to ours is Blockwise Decoding (Stern al. 2018) that proposed to additionally insert k - 1 NAR heads on top of the Transformer decoder to generate k positions in parallel and use the original AR head to verify these outputs. However, its underinvestment in the NAR modeling seriously limits its performance, resulting in much lower efficiency than our approach.
CONCLUSION AND FUTURE WORK
We propose novel Speculative Decoding (SpecDec) paradigm as well as its variant (SpecDec++) by combining respective advantages of AT and NAT. Contrary to the stereotype that more models (parameters) tend to slow down inference, SpecDec's introduction of an additional NAT model sub- stantially speeds up AT without quality loss, achieving state-of-the-at lossless acceleration result owing to higher computational parallelism introduced by the idea of speculative execution to better utilize computing resources.
Besides machine translation, SpecDec can be easily generalized to other seq2seq tasks like Ab- stractive Summarization and benefit from stronger computing devices (to discuss in Appendix [E) It demonstrates a novel yet promising perspective for efficient seq2seq generation, orthogonal to the efforts for advancing the state-of-the-art NAT and AT models that can further benefit SpecDec.
Despite the of art results, SpecDec still has great potential with much headroom for im- provement, we discuss in Section 5.4 We hope that our preliminary study could draw more attention to improving this promising decoding paradigm with potential to evolve into a de facto standard for efficient and lossless seq2seq generation in the near future.
9

---

Under review as a conference paper at ICLR 2023
REFERENCES
Yu Bao, Shujian Huang. Tong Xiao, Dongqi Wang, Xinyu Dai, and Jiajun Chen. Non-a autoregressivve translation by learning target categorical codes. In Kristina Toutanova, Anna Rumshisky, Luke Zettlemoyer, Dilek Hakkani-Tür, Iz Beltagy. Steven Bethard, Ryan Cotterell, Tanmoy Chakraborty, and Yichao Zhou (eds.), Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Technologies, Association for Computational hww.://......nnnnmm.aa..a.aaalla maiic--mii.458 URL stttps://dos orq/1C.
NAT 2021, Online, June 6-11, 2021, pp. Linguistics, 2021. doi: 00.18653/v1/202/
18653/v1/202 nww..aaaaacaaaaam 458 458
William Chan, Nikita Kitaev, Kelvin Guu, Mitchell Stern, and Jakob Uszkoreit. KERMIT: gen-
erative insertion-based modeling for sequences. CoRR, abs/1906.01604, 2019. URL http:
01604
Mengyun Chen, Tao Ge, Xingxing Zhang, Furu Wei, and Ming Zhou. Improving the efficiency of grammatical error correction with erroncous span detection and correction. arXiv preprint arXiv:2010.03260, 2020.
Liang Ding, Longyue Wang, Xuebo Liu, Derek F. Wong, Dacheng Tao, and Zhaopeng Tu. Reju- venating low-frequency words: Making the most of parallel data in non- aon-auorregressvve transla- tion. In Chengqing Zong, Fei Xia, Wenjie Li, and Roberto Navigli (eds.), Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing, ACL/UCCNPP 2021. (Volume 1: Long Papers), Virtual Event, August 1-6, 2021, pp. 3431-3441. Association for Computational Linguistics. 2021a. doi: 10. (0.18653/v1/2221 waw.-....l-ooo..66.... URL htttps://oot /ttp://///oo..r///./////o 18653/v1/
266
Liang Ding, Longyue Wang, Xuebo Liu, Derek F. Wong, Dacheng Tao, and Zhaopeng Tu. Un- derstanding and improving lexical choice in non-autoregressive translation. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. net Eorum ? i www.ummnddddFFFeeAAAA IIFSSBIXC
OpenReview.net, 2021b. URL/tttps://pppneeeeee
Cunxiao Du, Zhaopeng Tu, and Jing Jiang. Order-agnostic cross entropy for non-autoregressive ma- chine translation. Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International
Conference on Machine Learning, ICML 2021, 18-24 24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pp. 2849 2859. PMLR, 2021. URL. http: //proceedi ml wwwps/eessvvv wttpa/ssvvl/////// htt9//u2cc.hhmmmmm html
Tommaso Furlanello, Zachary Lipton, Michael Tschannen, Laurent Itti, and Anima Anandkumar. Born again neural networks. In International Conference Machine Learning, pp. 1607-1616.
PMLR, 2018
Xinwei Geng, Xiaocheng Feng. and Bing Qin. Learning to rewrite for non-autoregressive neural machine translation. In Marie-Francine Moens, Xuanjing Huang, Lucia Specia, and Scott Wen- tau Yih (eds.), Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, EMNLP 2021, Virtual Event Punta Cana, Dominican Republic, 7-11 November, 2021, pp. 3297-3308, Association for Computational Linguistics, 2021. doi: 10. 10.18653/1120211 emnlp-main.265. URL htttttt::///o http:////oooo///////// 10 10.
emn p- ma.in.2 265
Marjan Ghazvininejad, Omer Levy, Yinhan Liu, and Luke Zettlemoyer. Mask-predict: Paral- lel decoding of conditional masked language models. In Kentaro Inui, Jing Jiang, Vincent Ng. and Xiaojun Wan (eds.), Proceedings of the 2019 Conference Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing, EMNI.P-IICNIPP 2019, Hong Kong, China, November 3-7, 2019, pp. 6111-6120. Association for Computational Linguistics, 2019. doi: 10. 11.1186//1//111166 1633. URL https: //doi. www.1/.16/119-1111
Marjan Ghazvininejad, Vladimir Karpukhin, Luke Zettlemoyer, and Omer Levy. Aligned cross entropy for non-autoregressivve machine translation. In Proceedings of the 37th International Conference Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pp. 3515 3523. PMLR, 2020a. URL http: htm
mtr...r..sssssss.............e //proceed igg. ml wwwpsreasvvii ttreas//il1/ghaariinneee
10

---

Under review as a conference paper at ICLR 2023
Marjan Ghazvininejad, Omer Levy, and Luke Zettlemoyer. Semi-auttoregressive training improves mrask-predict decoding. CoRR, abs/2001 008785 2020b. URL htapps://aaxiv..oo /bs/
0000100770
Jiatao Gu and Xiang Kong. Fully non-autoregressive neural machine translation: Tricks of the trade. In Chengqing Zong, Fei Xia, Wenjie Li, and Roberto Navigli (eds.), Findings of the Association for Computational Linguistics: ACL/IJCNLP 2021. Online Event, August 1-6, 2021, volume ACL/IJNNLP 2021 Findings of ACL, pp. 120-133, Association for Computational Linguistics. 2021. doi: 10. 1...8633/112222.iiniiii 2021. Findings-acll
findingss-cll.... 11. URL /ttp::://oi..or/11.118838
Jiatao Gu, James Bradbury, Caiming Xiong, Victor O.K. Li, and Richard Socher. Non-autoregressive neural machine translation. In International Conference on Learning Representations, 2018. URL
htttps:/oppereviil .ee htt.//oormmfdo fttpmnee/ooommmmmd1111111e1
Jiatao Gu, Changhan Wang, and Junbo Zhao. Levenshtein transformer. In Hanna M. Wallach, Hugo Larochelle. Alina Beygelzimer, Florence d' Alché-Buuc Emily B. Fox, and Roman Gareett (eds.), Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, URL htt /ttpttpppe/prrrcceennggge.g neur ieporripp... wttpcp/pppp/./// htmm
Canada, pp. 11179 11189 2019.
Junliang Guo, Linli Xu, and Enhong Chen. Jointly masked sequence-to-sequenec model for non-autoregressive neural machine translation. In Dan Jurafsky, Joyce Chai, Natalie Schluter, and Joel R. Tetreault (eds.), Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, ACL 2020, Online, July 5-10, 2020, pp. 376-385, Association for Computational Linguistics, 2020. doi:
URL http:: //doi.
htg/10.186533
Yongchang Hao, Shilin He, Wenxiang Jiao, Zhaopeng Tu, Michael R. Lyu, and Xing Wang- Multi-task learning with shared encoder for non-autoregressive machine translation. In Kristina Toutanova, Anna Rumshisky, Luke Zettlemoyer, Dilek Hakkani-Tür, Beltagy, Steven Bethard, Ryan Cotterell, Tanmoy Chakraborty, and Yichao Zhou (eds.), Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-HLT 2021, Online, June 6-11, 2021, pp. 3989-3996. Association for Computational I. Linguistics, 2021. doi: 10. 10.18653/v1/202 naacl-main.311 URL
https://dor ftttss://doi.or/100// 0...0...111111000 maa.::/aaaaammma333333 3..
Karl Moritz Hermann, Tomás Kociský, Edward Grefenstette. Lasse Espeholt, Will Kay, Mustafa Suleyman, and Phil Blunsom. Teaching machines to read and comprehend. In Corinna Cortes, Neil D. Lawrence, Daniel D. Lee, Masashi Sugiyama, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec. Canada, pp- 1693-1701, 2015. URL http/tttss//pppccceddnee neurips wttparrsss......peeeeeeeeme cc/ppaper/201//aas. a
Abtt:cc9o-bbbbattctctbc html
Chenyang Huang, Hao Zhou, Osmar R. Zaianee Lili Mou, and Lei Li. Non-autoregressivv translation with layer-wise prediction and deep supervision. CoRR, abs/21 10.07515, 2021. URL https:
7/ aazxiv.org/abs//11131 2751
Fei Huang, Hao Zhou, Yang Liu, Hang Li, and Minlie Huang. Directed acyclic transformer for non- autoregressive machine translation. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song. Csaba Szepesvári, Gang Niu, and Sivan Sabato (eds.), International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine https: http:///coceeiiigsee mmr..
Learning Research, pp. 9410-9428, PMLR, 2022a. URL
sxess/v162/huangee
html
Xiao Shi Huang, Felipe Perez, and Maksims Volkovs. Improving non-autoregreessvve translation models without distillation. International Conference on Leaminng Representations, 2022b.
URL htt.:httpss//pppeeevieee htt.:e/ewwweeeooomo/dddtaaaa

---

Under review as a conference paper at ICLR 2023
Lukasz Kaiser, Samy Bengio, Aurko Roy, Ashish Vaswani, Niki Parmar, Jakob Uszkoreit, and Noam Shazeer. Fast decoding in sequence models using discrete latent variables. In Jen- nifer G. Dy and Andreas Krause (eds.). Proceedings of the 35th International Conference Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, vol- 80 of Proceedings of Machine Learning Research, pp. 2395 -2044. PMLR, 2018. URL http:/ http://proceedings mlr. wtwpppee/eeswsseeee////. htt.errm8...mllm.....mmmmm
Jungo Kasai, James Cross, Marjan Ghazvininejad, and Jiatao Gu. Non-autoregressive machine translation with disentangled context transformer. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pp. 5144-5155. PMLR, 2020. URL http: //proceedings.. mlr www.r.peess//e 20ress/vl19/kasai2000 html
Jungo Kasai, Nikolaos Pappas, Hao Peng, James Cross, and Noah A. Smith. Deep encoder, shallow decoder: Reevaluating non-autoregressivv machine translation. In 9th International Conference
on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenRe-
view.net, 2021. URL https:
Yoon Kim and Alexander M Rush. Sequence-level knowledge distillation.
arXiv preprint
arXiv:1606.07945 607477 2016.
Xiang Kong, Zhisong Zhang, and Eduard H. Hovy. Incorporating a local translation mechanism into non-autoregressive translation. In Bonnie Webber, Trevor Cohn, Yulan He, and Yang Liu (eds.), Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, EMNLP 2020, Online, November 16-20, 2020, pp. 1067-1073. Association for Computational Linguistics. 2020. doi: 10. 1ttp:/0.0112000mmm...pmm 18653/v1/2022 ett.:/2222mmmmmm.p.mmmmmmmmm emnlp------..... main. 79
URL https::/doi.
Jason Lee, Elman Mansimov, and Kyunghyun Cho. Deterministic non-autoregressive neural se- quence modeling by iterative refinement. In Ellen Riloff, David Chiang, Julia Hockenmaier, and Jun Jun'ichi Tsujüi (cds.). Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, Brussels, Belgium, October 31 November 4, 2018, pp. 1173-1182. As- sociation for Computational Linguistics, 2018. doi: 10.18653/v1/d1-- 1149. URL https:
//doi. org/1000 10. Bt///////////111///////.
Mike Lewis, Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, Abdelrahman Mohamed, Omer Levy, Veselin Stoyanov, and Luke Zettlemoyer. BART: denoising sequence-to--eqqueee pre- training for natural language generation, translation, and comprehension. In Dan Jurafsky, Joyce Chai, Natalie Schluter, and Joel R. Tetreault (eds.), Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, ACL 2020, Online, July 5-10, 2020, pp. 7871-7880 Association for Computational Linguistics, 2020. doi: 10. 10.18653/112222.accc :ttpss//dol. wrg/lorllo...o......oooooo...... /10 18651/66//8188 v1 200022220222 wwwaammmiin.... 703
703. URL
Jindrich Libovický and Jindrich Helel. End-to-end aur-eeeoreeeessvve neural machine transla- tion with connectionist temporal classification. In Ellen Riloff, David Chiang, Julia Hocken- maier, and ichi Tsujii (eds.), Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, Brussels, Belgium, October 31 November 4, 2018, pp. 3016- 3021. Association for Computational Linguistics, 2018. doi: 10. 10.18653/v1/d18 1336. URL https: /oi.. www.orgg............. 18653/ v w 21//11111111 1336
Jinglin Liu, Yi Ren, Xu Tan, Chen Zhang, Tao Qin, Zhou Zhao, and Tie-Yan Liu. Task-level curriculum learning for non-autoregresssvv neural machine translation. In Christian Bessiere (ed.), Proceedings the Twenty-Nint International Joint Conference on Artificial Intelligence, IJCAI 2020, pp. 3861 3867. ojcai.org. 2020. doi: 0..29633/jeai.2222/533. URL https:
Ye Liu, Yao Wan, Jian-Guo Zhang, Wenting Zhao, and Philip S. Yu. Enriching non-autoregressive transformer with syntactic and semantic structures for neural machine translation. In Paola Merlo, Jörg Tiedemann, and Reut Tsarfaty (eds.), Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguistics: Main Volume, EACL 2021, Online, April 19- 23, 2021, pp. 233-11244 Association for Computational Linguistics, 2021.
12

---

Under review as a conference paper at ICLR 2023
doi: 10.186533v1/2021. maullmmin... main. 105. URL http:ps://ao..cr//0118855/////// facl-main... 105
Sajad Norouzi, Rasa Hosseinzadeh, Felipe Pérez, and Maksims Volkovs. Dims: Distilling multiple steps of iterative -on-auttoeerrsssive transformers. CoRR, abx/2206.02999, 2022. doi: 10.48550/ arXiv.2206.022 02999. URL https://coi.org:
48550/arXiv 2206. 02999
Myle Ott, Sergey Edunov, David Grangier, and Michael Auli. Scaling neural machine trans- lation. In Proceedings of the Third Conference Machine Translation: Research Papers, pp. 1-9, Brussels, Belgium, October 2018. Association for Computational Linguistics. doi: httLhttsss///cclameee www.tthhoolyooro.rro.ooo..
N.11855//1/W11-665
6301
Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. Bleu: a method for automatic evaluation of machine translation. In Proceedings of the 40th Annual Meeting of the Association for Computational Linguisties, July 6-12, 2002, Philadelphia. PA, USA, pp. 311-318, ACL, 2002. URL BtLpttps:: httptttppp/aaaaattooteeeeo http//aaaaaatttyyy...oaoaooooaaa wrg.hoolowooooooooooooooooo org PO2 1040/
doi: 10.3115/10730031103311
Matt Post. A call for clarity in reporting BLEU scores. In Ondrej Bojar, Rajen Chatterjee, Christian Federmann, Mark Fishel, Yvette Graham, Barry Haddow, Matthias Huck, Antonio Seneno-Yepess Philipp Koehn, Christof Monz, Matteo Negri, Aurélie Névéol, Mariana L. Neves, Matt Post, Lucia Specia, Marco Turchi, and Karin Verspoor (eds.), Proceedings of the Third Conference on Machine Translation: Research Papers. WMT 2018, Belgium, Brussels, October 31 November 1, 2018, pp. 186-191. Association for Computational Linguistics, 2018. doi: 10-665///w///1-611111 URL htttp:://ddoto www.orrg...0 (2633vvvll/. /tt.////////11/333
Lihua Qian, Hao Zhou, Yu Bao, Mingxuan Wang, Lin Qiu, Weinan Zhang, Yong Yu, and Lei Li. Glancing transformer for non-autoregressive neural machine translation. In Chengqing Zong, Fei Xia, Wenjie Li, and Roberto Navigli (eds.), Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 1 Itth International Joint Conference Natural Language Processing, ACL/JJCNPP 2021, (Volume 1: Long Papers). Virtual Event, August 1 1-6, 2021, pp. acl-long.153 155. URL fattps:///oo wrg.:ooo..rroooooooooo 1tt.:/11..115311111
Association for Computational Linguisties, 2021. doi: 10.18653/v1/200 1/2021. acl long. 155
Samyam Rajbhandari, Conglong Li, Zhewei Yao, Minjia Zhang, Reza Yazdani Aminabadi, Am- mar Ahmad Awan, Jeff Rasley, and Yuxiong He. Deepspeed-moe: Advancing mixture-of-expprts inference and training to power next-generation ai scale. arXiv preprint arXiv:2201.0533 2022.
Qiu Ran, Yankai Lin, Peng Li, and Jie Zhou. Learning to recover from multi-modalle errors for non-autoregressive neural machine translation. In Dan Jurafsky, Joyce Chai, Natalie Schluter, and Joel R. Tetreault (eds.), Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, ACL 2020, Online, July 5-10, 2020, pp. 3059-3069. Association for Computational Linguistics, 2020. doi: 10. 10.18653/v 1/2.5////2022.ccll..ooo maa.n...217mmm7 URL https:
7/ www.ooggo11... /0. 11653881112000 acl main. 277
Ricardo Rei, Craig Stewart, Ana C. Farinha, and Alon Lavie. COMET: A neural framework for MT evaluation. In Bonnie Webber, Trevor Cohn, Yulan He. and Yang Liu (eds.). Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, EMNIP 2020, Online, November 16-20, 2020, pp. doi: 10.1866331/22200.emmp..... 213. URL htt.:t..p.../bo.oog/00......3.13
Association for Computational Ltg.atiiioiiiiniiiiiiiiii Linguistics, 2020.
emr.1p ma iiain.22 213
Chitwan Saharia, William Chan, Saurabh Saxena, and Mohammad Norouzi. Non-autoregressive machine translation with latent alignments. In Bonnie Webber, Trevor Cohn, Yulan He, and Yang Liu (eds.). Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, EMNLP 2020, Online, November 16-20, 2020, pp. 1098-1 1 108. Association for Com- putational Linguistics, 2020. doi: 10.18653/
w1t.200.mmllp-mmm mainp-mmin.83. URL https:://ooi.
org/10.188 111111018653481 653 /2020. emn 1 ma i..inn.......
Nikolay Savinov, Junyoung Chung, Mikolaj Binkowski. Erich Elsen, and Aäron den Oord. Step-unrolled denoising autoencoders for text generation. CoRR, abs/21 12.06749, 2021. URL
https::/arxiv. http://rwxxww..oo////////////22/
13

---

Under review as a conference paper at ICLR 2023
Robin M. Schmidt, Telmo Pires, Stephan Peitz, and Jonas Lööf. Non-autoreerressvve neural machine translation: A call for clarity. CoRR, abs/2205.10577, 2022. doi: 10:48550aaxin,2205.05777
URL https::/db..ozgg/////ooo
(1555//arXiv.200000 10577
Rico Sennrich, Barry Haddow, and Alexandra Birch. Neural machine translation of rare words with subword units. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguisties, ACI 2016, August 7-12, 2016, Berlin, Germany, Volume Long Papers. The Association for Computer Linguistics, 2016. doi: 10. 10.18653/v 1162. URL https:
//doi.org/100 www.11116/vvllli 1162
Chenze Shao, Jinchao Zhang. Yang Feng, Fandong Meng, and Jie Zhou. Minimizing the bag-of- ngrams difference for non-autoregressive neural machine translation. In The Thirty-Fourth AAAI Conference on Artificial Intelligence. AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference. IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020, / index.dixx. php/AAAI/ AAAI/
pp. 298-205, AAAI Press, 2020. URL https: /aas:///aaai.oe org/ o jss article/view//e
Chenze Shao, Xuanfu Wu, and Yang Feng. One reference is not enough: Diverse distillation with reference selection for non-autoregressive translation. In Marine Carpuat, Marie-Catherine de Marneffe, and Iván Vladimir Meza Ruíz (eds.), Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Technologies, NAACL 2022, Seattle, WA, United States, July 10-15, 2022, pp. 3779-3791. As- sociation for Computational Linguistics, 2022. doi: 10. 1/266//////22..mmmmm/. nww.l-main.n11111 URL naacl ma maaaacc-mmin..2.1 .
ht.pps://df http:/doioorgg////// 11633/11
Raphael Shu, Jason Lee, Hideki Nakayama, and Kyunghyun Cho. Latent-variable non- autoregressive neural machine translation with deterministic inference using delta posterior. In The Thirty-Fourth AAAI Conference Artificial Intelligence. AAAI 2020. The Thirty-Seoond Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020, pp. 8846 8853. AAAI Press, 2020. URL https::/of] aaai. .rrg/
index. Btteee/ppp/AAAaaaaiiccccco
6413
Jongyoon Song, Sungwon Kim, and Sungroh Yoon. Alignart: Non-autoregressive neural machine translation by jointly learning to estimate alignment and translate. In Marie-Francine Moens, Xu- anjing Huang, Lucia Specia, and Scott Wen-tau Yih (eds.), Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, EMNLP 2021, Virtual Event Punta Cana, Dominican Republic, 7-11 November, 2021, pp. 1 1-14. Association for Computational Linguis- tics, 2021. doi: 10. 11168///1/201..mmpppp. v1/2021 emn 1alppmain 1
URL https://do:: org/ /0. 18653/
Mitchell Stern, Noam Shazeer, and Jakob Uszkoreit. Blockwise parallel decoding for deep autoregressive models. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, December 3-8, 2018 Montréal, Canada, pp. 10107- 10116, 2018. URL httpt::::/// htttps:://proceedings neurips wwtppppee//11//aass.... c412 199994fe (ew.111443552224400055050 Abstre2cct..acatacttttt..... Abstract.
Mitchell Stern, William Chan, Jamie Kiros, and Jakob Uszkoreit. Insertion transformer: Flexible sequence generation via insertion operations. In Kamalika Chaudhuri and Ruslan Salakhutdi- nov (eds.), Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pp. 5985. PMLR, 2019. URL htw.:http/// http:::/proceedingg. wtw.eeiinnnsm..m............. ml..prrsss./// stern 9a h
Xin Sun, Tao Ge, Furu Wei, and Houfeng Wang. Instantaneous grammatical error correction with shallow aggressive decoding. In Chengqing Zong, Fei Xia, Wenjie Li. and Roberto Navigli (eds.), Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 1 11th International Joint Conference on Natural Language Processing, ACL/UCCNLP
14

---

Under review as a conference paper at ICLR 2023
2021, (Volume 1: Long Papers), Virtual Event. August 1-6, 2021, pp- 5937-5947. Associa- tion for Computational Linguistics, 2021. doi: 10. 12228663///222222cclhc 462. URL https:
/0 18w.118663311 //01/111 acl- long.
Zhiqing Sun and Yiming Yang. An EM approach to non-autoregressive conditional sequence gen- eration. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pp. URL
9249 9258. PMLR, 2020.
nggs mlr. wwwss/ s/snnncc.
htm
Zhiqing Sun, Zhuohan Li, Haoqing Wang, Di He, Zi Lin, and Zhi-Hong Deng. Fast struc- tured decoding for sequence models. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d'Alché-Buc, Emily B. Fox, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NewrlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 3011 3011-3020, 2019, URL https: htttps::/pprcceednnnnee neurips. wwtppappe///1/////e/eee 7456 wwt.oddaadaccceeeeeddeeeee.e..ee - html
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. 5998-6008 //tpp/tpp///ppproeeedngg....o.. neuris wttpppppe/01///eaaeeee/pp/// 515ee243547deee 7 3
html
Chunqi Wang. Zhang, and Haiqing Chen. Semi-autorregressive neural machine translation. In Ellen Riloff, David Chiang, Julia Hockenmaier, and Jun ichi Tsujii (eds.), Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, Brussels, Belgium, October 31 November 4, 2018, pp. 479 488. Association for Computational Linguistics, 2018. doi: 10.18653/v 1/d11/ 1044.
Yiren Wang, Fei Tian, Di He, Tao Qin, ChengXiang Zhai, and Tie- Yan Liu. Non-autoregressive machine translation with auxiliary regularization. In The Thirty- AAAI Conference on Artificial Intelligence, AAAI 2019, The Thirty-First Innovative Applications of Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019, Honolulu, Hawaïi, USA, January 27 February 1, 2019, pp. 5377-5384, AAAI Press, 2019, doi: 10. 1at.://9aai..33331333300000 333.01.33.11113177 URL httpt::t////o/ erg 0rq/10.1609//me
v33101. 00033111130115010 33015377
Bingzhen Wei, Mingxuan Wang, Hao Zhou, Junyang Lin, and Xu Sun. Imitation learning for non-autoregressive neural machine translation. In Anna Korhonen, David R. Traum, and Lluis Mårquez (eds.). Proceedings of the 57th Conference of the Association for Computational Linguistics, ACL 2019, Florence, Italy, July 28- August 2, 2019, Volume 1: Long Papers, pp- 7304-13122 Association for Computational Linguistics, 2019. doi: 10. 10.18863/111119-1125 URL. wttp//o...ogg....o 1ttp:///010.0133///1111111111111
Chun Zeng, Jiangjie Chen, Tianyi Zhuang, Rui Xu, Hao Yang. Ying Qin, Shimin Tao, and Yanghua Xiao. Neighbors are not strangers: Improving non-autoregressive translation under low-frequency lexical constraints. In Marine Carpuat, Marie-Catherine de Marneffe, and Iván Vladimir Meza Ruiz ), Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL 2022, Seattle, WA. United States, July 10-15, 2022, pp. 5777-5790. Association for Computational Linguisties, 2022. doi: 10. 18653/v1/2023 www.naaaaaaaa.aa 424
424. URL htttps://do..org////
Jiaao Zhan, Qian Chen, Boxing Chen, Wen Wang. Yu Bai, and Yang Gao. Non-autoregressivv translation with Sependency-aware decoder. CoRR, 162626033.16266.. 2022, doi: 10.48550/arXiv. 2203.16266. URL ht.ps::ts:: :/dp:s:://do. org/ htte:/1....5555/0 48550/arXi 221.....222.111... 1666
15

---

Under review as a conference paper at ICLR 2023
Zaixiang Zheng, Hao Zhou, Shujian Huang, Jiajun Chen, Jingjing Xu, and Lei Li. Du- learning for reversible machine translation. In Mare' Aurelio Ran- zato, Alina Beygelzimer. Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan (eds.), Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, pp. 21070-21084, 2021. URL https://proceddngg meereieiiinnn...eiii...p / i
plex
Minghao Zhu, Junli Wang, and Chungang Yan. Non-autoregressive neural machine translation with consistency regularization optimized variational framework. In Marine Carpuat, Marie-Catherinn de Marneffe, and Iván Vladimir Meza Ruíz (eds.), Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Technologies, NAACL 2022, Seattle, WA, United States, July 10-15, 2022, pp. 607-617. As- sociation for Computational Linguistics, 2022. doi: 10. 10.18653/v1/0022.mmm https://doi. 2000oo////2..11333/////2222 -at.:/22.aaallaaaaaa maaacclmaiin...
URL
16

---

Under review as a conference paper at ICLR 2023
APPENDIX
A HYPERPARAMETERS
of training SpecDec are listed in T Following Vaswani et al. (2017) and On
al. 2018). we also average model parameters from the last 10 checkpoints.
Hyperparameter
Value
Hyperparameter
Value
devices
8 Nvidia V100 GPU
devices
8 Nvidia V100 GPU
label smoothing # max tokens
0.1
label smoothing
0.1
20000
# max tokens
4096
update frequency
update frequency
4
dropout rate
[0.1, 0.2, 0.3]
dropout rate
[0.1, 0.2, 0.3]
max source positions
1000
max source positions
1000
max target positions
1000
max target positions
1000
Adam
1 x 10-3
Adam Ir
x 10-1
Adam 31
0.9
Adam 3
0.9
Adam 32
0.99
Adam 32
0.999
Ir-scheduler
inverse square
Adam
X 10-6
warm-up Ir
1 x 10
Ir-scheduler
inverse square
weight decay clip norm # warmup updates
0.00001
warm-up Ir
x 10-7
3.0
weight decay
0.01
4000
clip norm
5.0
max updates
100K
# warmup updates
10000
max epoch
1000
max updates
300K
Table 7: Hlyee--paaaeee and settings of the AT verifier (left) and the NAT drafter (right).
B DETAILS OF EXPERIMENTAL RESULTS
B. SPEEDUP RESULTS FOR MACHINE TRANSLATION
While only report the speedup results of EN-DE translation in the main body of this paper due to space limitation, we here report speedup details of EN-DE, DE-EN, EN-RO and RO-EN in Table 8 As demonstrated in Section [...] we tune the hyperparameters (k, B and 7) of SpecDec//ppeDDctte on the development set for each direction of benchmarks, According to Table [8. SpecDec/SpecDect+ performs consistently well on all the language pairs despite slight differ- ences in speedup ratios.
EN-X
X-EN BLEU
Models
3,7
Iter.
BLEU
Speed
3,7
Iter.
Speed
AT
AT verifier (b
N
28.73
1.1x
N
32.18
1.1x
NAT draller
1.6
26.48
14.3x
1.5
30.23
14.0x
WMT14
SpecDec (k 25)
4.9
28.73
3,0x
4.4
32.18
3.0x
EN-DE
SpecDec++ 25, high-quality)
3,1.0
28.89
3.6x
3,1.0
3.4
32.56
3.9x
SpecDec++ 25, high-efficiency)
5,3.0
3.1
28.73
4.5x
5,3.0
2.5
32.19
4.8x
AT
AT verifier
N
34.83
1.1x
N
34.65
1.1x
NAT drafter
1.6
32.08
13.3x
1.6
32.21
13.8x
WMT16 EN-RO
SpecDec (k = 25)
6.4
34.83
2.2x
5.9
34,65
2,4x
SpecDec++ (R 25, high-quality)
5.4.0
4.5
35.32
3.1x
3.2.0
4.6
34.98
2.9x
SpecDec++ (I: 25, high efficienc)))))
5.6.0
4.0
34.92
3.3x
5,3.0
4.0
34.80
3.3x
Table 8: Details of the main results of SpeeDee//peeDectt on WMT benchmarks. denotes the
corresponding language in each benchmark (German in WMT14 EN-DE and Romanian in WMT16 EN-RO). & is the block size. 3 indicates the Top-3 selection in SpecDec++ and T is the tolerance hyperparameter. All hyperparameters (k, 3 and 7) are tuned on the development set of each bench- mark.
17

---

Under review as a conference paper at ICLR 2023
B.2 SPEEDUP DISTRIBUTION
To further understand the acceleration effects of SpecDec, we present the speedup distribution of single sentence the WMT14 EN-DE showing that most sentences are translated with a 3x ~ 6x speedup compared to the beam search baseline, while some rare cases can even achieve over 10x speedup.
(which has 3,003 sentences in total) in Figure
Models
BLEU
Rep.
250
AT (greedy)
28.73
0.18%
CMLM (T 4)
25.75
1.13%
Sumple Mamber
CMLM (T = 10)
27.09
0.24%
SpecDec
28.73
0.18%
SpecDec++
28.89
0.17%
100-
50
Table 9: Token repetition ratio on WMT14 EN- DE. SpecDee-base is test with hyper-parameters k: = 25, top-3, T 1.0. CMLM is tested with our implementation with the length beam set to 3.
Speedup
Figure 4: Single sentence speedup distribution by SpecDec++ (k 25, sighheffficennc)
B.3 WORD REPETITIONS
With the conditional independence assumption, NAT models show serious weakness in modeling highly multimodal distributions. The token repetition ratio often utilized as a proxy to measure this multi-modality problem, which represents the degree of the text inconsistency. However, the role of our AT verifier guarantces that this problem does not exist in SpeeDec. As shown in Table 9 the token repetition ratio of Speclec//ppecDett is similar to that of our AT baseline, which is significantly lower than most relevant NAT models.
B.4 TEACHER MODEI.(S)
We study the effects of the teacher" on SpecDec, by comparing the results of single teacher with the teacher ensemble of 3 Transformer-big models in Table TO] Compared with sin- gle teacher model, teacher ensemble improves all the NAT drafter, AT verifier, and end-to-end
SpecDec/SpecDectt results, indicating that our approach can benefit from better teacher.
Single Teacher
Teacher Ensemble
Models
Iter.
BLEU
Speed
Iter.
BLEU
Speed
Teacher
Transformer- (b =
N
29.31
N
30.64
NAT drafter
1.6
26.48
14.3x
1.6
27.16
14.0x
AT verifier (b 5)
N
28.89
1.0x
N
29.19
1.0x
AT verifier 1)
N
28.73
1.1x
N
29.24
1.1x
Base
SpecDec = 25)
4.9
28.73
3.0x
4.5
29.24
3.3x
SpecDec++ (k = 25, top-3, r 1.0)
4.0
28.89
3.6x
4.0
29.31
3.4x
SpecDec++ (k = 25, top-5. 3.0)
3.1
28.73
4.5x
3.1
29.52
4.3x
NAT drafter AT verifier (b = 5)
1.4
27.35
15.0x
1.4
28.10
14.8x
N
29.25
1.0x
N
29.74
1.0x
AT verifier (b = 1)
N
29.18
1.1x
N
29.69
1.1x
Big
SpecDee (k 30)
4.8
29.18
3,0x
4.2
29.69
3.3x
SpecDec++ + (k
top-3, 1.0)
4.2
29.32
3.5x
3.8
29.88
3,6x
SpecDec++ (k 30, top-5. 7 6.0)
2.6
29.15
5.0x
2.5
29.81
5.1x
Table 10: Performance comparison between a single teacher model and teacher ensemble (3 teacher models) on WMT14 EN-DE. We report the results of both base-size and big-size SpecDec. Transformer- baans/ with beam search are the speed haselines of SpecDee-bbas/big respectively.
We will release all teachers facilitate reproducing our results.
18

---

Under review as a conference paper at ICLR 2023
B.5 RESULTS FOR TRANSFORMER 12-2
Kasai et al. (2021) points out that the Transformer with a deep encoder and a shallow decoder
achieve comparable translation quality with remarkable speedups. In Table TT present the results of SpecDec-base with the configuration of 12 encoder layers and 2 decoder layers. The results indicate that even in the deep-shallow configuration, SpeeDec/SpecDect can further speed
up translation without quality loss.
Models
F-D)
Iteration
BLEU
Speed
AT baseline
Transformer base (w/o SD)
6-6
27.74
1.0x
Teacher
6-6
29.31
NAT drafter (k 25)
12-2
1.6
25.67
18.1x
AT verifier (b = 5)
12-2
29.13
1.8x
Ours
AT verifier (b
12-2
N
28.99
2.0x
SpecDec (k: = 25)
12-2
5.6
28.99
4.6x
SpecDec++ (k 25, 1op-3, 1.0)
12-2
4.7
29.13
5.0x
SpecDec++ (k: = 25, top-5, 4.0)
12-2
3.4
29.00
6.3x
Table 11: Results of SpecDec with the deep-shallow model configuration on WMT14 EN-DE. Both the AT verifier and the NAT drafter have 12 encoder layers and 2 decoder layers. E: encoder depth; D: decoder depth. denotes the results of AT baselines = 5) implemented by Ghaavvninejad al. 2019). indicates results obtained by Transformer-big.
B.6 SACREBLEU AND COMET SCORES FOR WMT14 EXPERIEMENTS
We report SacreBLEU Post 2018 and COMET 13 Rei et al. 2020) scores in order to provide reference for future research. SpecDec/Spee Dec++ can also achieve lossless speedup even evaluated in SacreBLEU and COMET, [Schmidt et al. (2022) pointed out that inconsistencies in the use of
tokenized BLEU lead deviations up to 1.8 BLEU points. Therefore, we recommend that future research use sacreBLEU when comparing with our work.
BLEU
SacreBLEU
COMET
Teacher (Transformer-big)
29.31
28.6
52.95
NAT drafter (k: 25)
26.48
26.0
23.63
AT verifier (b 5)
28.89
28.2
51.90
AT verifier (b 1)
28.73
28.0
51.53
SpeeDee (k 25)
28.73
28.0
51.53
SpecDec++ (k = 25, high-quality)
28.89
28.2
52.10
SpecDec++ (k- 25. high-efffciencyy
28.73
28.0
51.56
Table 12: SacreBLEU and COMET scores on WMT14 EN-DE.
Models)
EN-DE
DE.
EN
RO-EN
Teacher (Transformer- big)
29.31(28.6")
32.11(31.6')
34.72(33.91)
34.49(33.9
NAT drafter 25)
26.48(26.0*)
30.23(29.8
32.08(31.3))
32.21(31.7
AT verifier (b = 5)
28.89(28.2
32.53(32.1
34.96(34.0
34.86(34.21)
AT verifier (b 1)
28.73(28.0))
32.18(31.7')
34.83(33.91)
34.65(33.91)
SpecDec (k 25)
28.73(28.0))
32.18(31.7
34.83(33.91)
34.65(33.95)
SpecDec++ + (k 25, high-quality)
28.89(28.2"))
32.56(32.1*)
35.32(34.44)
34.98(34.3))
SpecDec++ (k 25, high-efficiency)
28.73(28.0")
32.19(31.7')
34.92(34.0")
34.80(34.21)
Table 13: BLEU and SacreBLEU (denoted by t) scores on WMT14 EN-DE and WMT16 EN-RO benchmarks.
http:////gggh.bc.coooo///////eee 1...
OOtaiined with wmt 2 da from version
19

---

Under review as a conference paper at ICLR 2023
C MEMORY ANALYSIS
C.I ADDITIONAL MEMORY COST BY SPECDEC
The peak memory footnote of SpecDec during inference mainly comes from three parts:
Static AT verifier's weights
Static NAT drafter's weights
Intermediate variables/results
Compared with AT, the additional memory cost of SpecDec comes from the last two parts. While the static NAT drafter's weights account for the majority of the additional memory cost, the addi- tional cost for storing intermediate variables is negligible because the NAT drafter and AT verifier decode alternatively during inference. Compared with AT, SpecDec's additional intermediate vari- ables/results include:
The NAT drafter's last encoder layer's representation that will not be freed until decoding finishes, which is equal to S where B is the batch size, S is the sequence length and is the dimension of the model. This part is actually negligible: for example, when B 32, S 128, d = 512, this part's memory cost is only 8MB (fp32) 4MB (fpl6).
The largest intermediate variables/results during inference:
For a short sequence (e.g., sentence-level inputs/outputs in MT tasks), the largest inter- mediate variable is the output tensor after the NAT drafter's/AN verifier's vocabulary projection layer- B [V| k where B is the batch size, [V] is the vocabulary size and à the block size. Compared with the memory cost for storing the NAT drafter's weights, this part is usually smaller. Also B k tokens can be easily divided into small batches (e-g.. -softmax--haane memory cost in case B V k is large.
in fairseq) for vocabulary projection to avoid massive
- For long sequence (e.g., paraggaphl/oocumen-eeee inputs/outputs in summarization tasks), the largest intermediate variable becomes the tensor for storing self-attention computation whose size increases quadratically with (S is the sequence length). This variable accounts for the largest memory cost for storing intermediate results in both AT and SpecDec. Therefore, in this case, this part does not introduce additional memory cost compared with AT.
Batch Size
Models
Model Weights
4
16
32
AT (greedy)
232.4
243.2
271.7
301.4
366.4
494.6
SpecDec++
469.8
483.4
511.8
551.1
626.0
774.4
AMemory
237.4
240.2
240.1
249.7
259.6
279.8
Table 14: Peak GPU memory utilization on WMT14 EN-DE translation dataset. The results are obtained with fp32 on single Nvidia P100 GPU. The hyperparameters of SpecDec++ are k 25, top-5, T = 3.0.
Models
Model Weights
Memory Cost
AT (greedy)
534.6
696.9
SpecDec++
1071.4
1246.2
AMemory 536.8
549.3
Table 15: Peak GPU memory utilization on CNN-DM with batch size with fp32 on a single Nvidia P100 GPU.
20

---

Under review as a conference paper at ICLR 2023
Table 14 and Table 15 show the comparisons of peak GPU memory footprin (MB) between SpeeDec and AT (during inference) on the above two scenarios (i.e., MT and summarization). The results are consistent with our analysis above:
The majority of the additional memory cost (i.e., AMemory) is for storing the NAT drafter's weights and the additional memory cost is not very likely to significantly increase as the batch size or sequence length increases.
Our experiments above pre-loaded both the NAT drafter and AT verifier. In fact, it also possible to load the static weights of the AT verifier and NAT drafter in a lazy loading manner in the meantime of GPU computation to save memory they run alternatively. However, is usually unnecessary in practice, because for a seq2seq model deployed on modern GPUs for online service, it is latency rather than memory that is the performance bottleneck. See the next section for more discussion.
C.2 MEMORY IS RARELY THE BOTTLENECK
To understand the performance bottleneck of online deployed seq2seq models, we test the latency and memory cost of Ia-la (around 770M parameters) with fp16 on Nvidia A40 GPU running greedy decoding in the machine translation and abstractive summarization task, and show results in Table 16 and
Batch Size
Batch Size
Statisties
Statistics
32
1
32
Latency (s)
1.0.A
1.4.
Latency (s)
2.7A
4.7A
Memory Util. (MB)
1482
2003
Memory Util. (MB)
2999
7230
Memory Util. (%)
3.0
4.0
Memory Util. (%)
6.2
15.0
Table 16:
Latency and peak GPU memory uti- lization of T5-Large WMT14 EN-DE.
Table 17:
Latency and peak GPU memory uti-
lization of T5-Large CNN-DM.
For MT. T5-lers''s ' latency is over second which is actually too long to be accepted because most MT engines in practice require the latency to less than 100ms. However, its memory cost is only less than 2GB far below A40 GPU's ss memory capacity (i.e., 48GB
For abstractive summarization, even if the batch size increases to 32, its memory cost still less than 50% utilization of 1 A40 GPU but its latency is already close up to 5 seconds that is too long for an online service in practice.
To sum up, we now understand latency is the bottleneck of seq2seq models for online deployment in most cases. Therefore, we do not think additional memory cost by SpecDec will undermine its practical value; instead, we think significant lossless acceleration even at the cost of memory (i.e., time-memory trade-off) is much more meaningful than the acceleration at the cost of quality, which should be the right path that we need to pay more attention to given much memory headroom on modern GPUs.
D PROFILING
We show the inference time cost by modules in SpecDec++ in Table 18 The current naive imple- mentation costs total of approximately 16% of overall time (sequentially) encode the input for the AT and NAT model, which can be obviously optimized. Also, the NAT decoder costs more than AT decoder because of the multi-round computation for previously decoded tokens.
"Tested with the command torch. cuda. memory allocated ()
In practice, T5-large is rarely deployed for online service hecause it is too large and expensive to serve. It also easily scale 96GB with NVIDIA NVLink connection of multiple GPUs.
21

---

Under review as a conference paper at ICLR 2023
Modules
Latency(ms)
Percent( %
AT Encoder
5.65
7.70
NAT Encoder
5.73
7.80
NAT Decoder
31.44
42.81
AT Decoder
27.33
37.21
Others
3.31
4.48
Total
73.46
100
Table 18: Profiling SpecDec++(bse-siize,, 23, top-5. 3.0) on the WMT14 EN-DE test set.
E SPECDEC ON VARIOUS COMPUTING DEVICES
We also tes te the inference efficiency of SpecDec with the batch implementation various GPUs, as shown in Figure It is obvious that more powerful devices (e.g., V100/A100 can benefit SpecDec/SpecDect+ more (i.e., higher speedup).
1B
P100
V100
A100
800
+ SpacDect-t
SpecDec
Unoe (mma] Losk perr bater awRE
SpecDec
SpecDect
5.0
SpecDec
SpocDect+
-500
Hime cou Bestem
800
400
300
200
trme
200
100
12
1.5
20
24
28
12
15
32
batch
batch
batch
Figure 5: Inference latency of SpecDec-base (A: = 25, top-5, T = 3.0) on P100 (fp32), V100 (fp16) and A100 (fp16). The results are obtained WMT14 EN-DE. The speedup baseline (1x) is AT (b = 5) when batch = 32.
Therefore, we believe SpecDec's speedup ratio in the future can be much higher than the number report in this paper, because it can benefit more from evolving processor hardware that will become increasingly powerful and better at parallel computing (c.g., Nvidia H900 with fp8 support).
DISCUSSIONS OF BEAM SEARCH
For possible concerns that SpecDec may not apply beam search, we make three points here:
1. As Kim & Rush (0166) mentioned, knowledge distillation largely decreases the perfor- mance gap of beam search and greedy decoding. In practice, greedy decoding can actually be comparable to beam search results after KD.
2. In practical online deployment, KD is almost used by default for enhancing the results for student models and greedy decoding is much more common than beam search because it is more cost-effective - it not only runs faster than beam search but also achieves decent performance with student model trained through KD (as Point addressed)
!' test with the batch size up 32 because will become higher. Therefore, it impractical to use a large batch size during inference, as RRajbhandaii et al.
batch size increases, the inference latency per batch
2022) points out.
in SpecDec save the computation for previously decoded tokens as conventional AT, which means its result probably much underestimated.
15 For simplifying implementation, do
incremental
But even so, SpecDee//Spec
still shows very promising speedup.
"htpps: www. nwi di com/ wwt..///////aaaaaaaaaa http://nnneeeeaaaaaatttet//////a cetter//honnnt
22

---

Under review as a conference paper at ICLR 2023
3. Beam search is also approximate and heuristic solution, which is not golden rule. In fact, SpecDec++ works in similar way as beam search it is also an approximate and heuristic solution by considering n-best and scores, which can be considered an approximation of beam search. As shown in T achieves comparable performance to beam search but much faster (3x 5x). Therefore, think it can replace beam search for efficient seq2seq generation.
G CASE STUDY
we represent several examples to illustrate how SpecDec/SpecDect+ generates trans- lations. Take Example for illustration, the first iteration, the outputs of the drafter non- autoregressive with multi-modality problems like "Angaben Angaben". The verifier accepts tokens of "Nach den" and replaces the inappropriate translation "Angaben" with "vorliegenden". In the second iteration, the verification of the vanilla SpecDec finds the bifurcation at the first position thus all tokens after this position are discarded. After iterations, the decoding is finished since the [ECS] token is found.
In Table 19,
Compared with the vanilla SpecDec, in the second iteration, SpecDec++ finds that the top-ß can- didate "Angaben" meets the relaxing requirement so that it accepts this token, showing that the relaxing constraints do help to accept more tokens for our proposed SpecDec model.
23

---

Under review as a conference paper at ICLR 2023
Example I- vanilla SpecDec
SOURCE
According to the details provided, the tunnel had not yet heen put into use.
D
Nach den Angaben Angahen war der Tunnel noch nicht in
V
Nach den vorliegenden war war der Tunnel noch nicht in Betrieb
D
Nach den vorliegenden Angaben war der Tunnel noch nicht in Betrieh genommen
V
Nach den vorliegenden Einzelheiten war Tesnel seaesnel--ec---iieeeee nicht-in BeteeeBeeeeeeeeeeeeeeeeeeeeee genommen--warden
D
Nach den vor vorliegenden Finzelheiten war der Tunnel noch nicht in Retrieb genommen [FOS]
V
Nach den vorliegenden Einzelhciten war der Tunnel noch nicht in Betrieb genommen worden
D
Nach den vor vorliegenden Einzelheiten war der Tunnel noch nicht in Betrieb genommen worden, [EOS]
V
Nach den vor vorliegenden Einzelheiten war der Tunnel noch nicht in Betrieb genominen worden. [BOS]
RESULTS
Nach den vorliegenden Finzelheiten war der Tunnel noch mihh in Hetrieb genommen worden.
Example 2-vanilla SpecDec
SOURCE
Yesterlay Gutee acht 's Mayor gave clear answer to this question..
D
Gestern hat der Bürgeré 8 meister vom Gute e acht eine klare
V
Gestern hat Guta@ Bürgerê meister von Gut @ acht eine klare Antwort
D
Gestem hat Guige achtd@ is Bürgeree meister eine klare Antwort auf diese Frage
V
Gestem hat Gutg ach@@ Büirgerg meister-eine eine klare Antwost auf diese -iese-Frage Frage-gogehen
D
Gestern hat Gutgg achee is Bürgeré meister eine klare Antwort auf diese Frage gegeben
V
Gestern hat G achee ts Bürgerë è meister eine klare Antwort auf diese Frage gegeben.
D
Gestern hat Gutee achee Is Bürgerè? @ meister eine klare Antwort aul diese Frage gegeben [EOS]
V
Gestern hat G achee ts Bürgerê meister eine klare Antwort auf diese Frage gegeben [EOS]
RESULTS
Gestern hat Gut ach ts Bürgerê meister eine klare Antwort auf diese Frage gegeben
Example S-SpeeDec++
SOURCE
According to the details provided, the tunnel had not yet been into
D
Nach den Angaben Angaben war der Tunnel noch nicht in
V
Nach den vorliegenden war war der Tunnel noch nicht in Betrieb
D
Nach den vorliegenden Angaben war der Tunnel noch nicht in Betrieb genommen [ECS]
V
Nach den vor liegenden Angaben war der Tunnel noch nicht in Betrieb genommen worden
D
Nach den vorliegenden Angaben war der Tunnel noch nicht in Betrich genommen worden (ECS)
v
Nach den vorliegenden Angaben war der Tunnel noch nicht in Betrieb genommen worden [BOS]
RESULTS
Nach den vorliegenden Angaben war der Tunnel noch nicht in Betrieb genommen worden.
Example
SpeetDec++
SOURCE
Yesterday Gut acht Mayor gave clear answer to this question..
D
Gestern hat der Bürgerê 9 meister von Gut acht eine klare
V
Gestern hat der Bürgerě 8 meister von Gut 8 acht eine klare Antwort
D
Gestern hat der Bürgere 9 meister von Gut acht eine klare Antwort auf diese Frage gegeben. [EOS]
V
Gestern hat der Bürgerl' 8 meister von Gut 8 acht eine klare Antwort auf diese Frage gegeben.. [FOS]
RESULTS
Gestern hat der Bürgerê' 9 meister von Gut acht eine klare Antwort auf diese Frage gegeben.
Table 19: Examples from the WMT14 14 English-Germat translation task. At each iteration, D and are the outputs of the drafter and the verifier, respectively. Tokens within red blocks are the bi- furcation positions. The verification pieces after the bifurcation annotated strikethrough. The highlighted parts are translations of previous iterations. Tokens in blue blocks are top-3 candidates which meet the SpecDec++ requirement. The hyperparameters are A 10, top-3, = 1.0. '0e' is the BPE token, e.g., Gut acht - Gutacht. The output pieces after the [EOS] ] token is omitted in the table.
24


Reviews:
[{"review_id": "v4XSvNWvo-", "reviewer": "Reviewer_RP8T", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper aims at accelerating translation inference without quality degeneration. The authors extend the idea of \"Predict-Verify\" to \"Draft-Verify\" and propose SpecDec which leverages a non-autoregressive model to produce the next k tokens followed by an autoregressive model verifying these predictions in parallel. Only accepted tokens are used as outputs. The authors also propose relaxed strategies for the verification which allows more drafted tokens accepted, further gaining efficiency. Results on WMT14 En-De, WMT16 En-Ro, and CNN/Daily Mail show improved inference speed with comparable and even better generation quality.\n", "summary_of_the_review": "While the paper presents some interesting results, the model is incremental to the \"Predict-Verify\" work and its comparison is often unfair as a large teacher model is employed. Besides, it's unclear whether the proposed SpecDec can achieve better quality-speed trade-off than recent advanced NAT models and highly optimized AT models.", "strength_and_weaknesses": "**Strengths:**\n\n* The proposed idea is intuitive and easy to follow;\n* The generation performance looks promising, with good quality and inference speedup;  \n* SpecDec generalizes to different sequence generation tasks, including translation and summarization;\n\n**Weaknesses:**\n\n* The idea of speculative decoding has been explored before in the form of \"Predict-Verify\" [1]. This work is somehow incremental. While using a separate non-autoregressive model improves translation performance, it comes at the cost of increased memory usage.\n* Considering recent progress on NAT which obtains comparable and even better quality than its AT counterpart, the value of this paper becomes somehow questionable. \n* Comparison and experiments should be further improved to fully convince the readers.\n\n[1] Stern et al. 2018. Blockwise Parallel Decoding for Deep Autoregressive Models", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "oIh82I2SeHK", "reviewer": "Reviewer_GbVT", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The decoding method called SpecDec(++) that is proposed in this paper is a combination of auto-regressive and non-autoregressive machine translation (AT & NAT). The token-by-token decoding in vanilla AT is replaced by a drafting step in which the NAT model predicts k tokens in advance, and a verification step in which the k tokens are checked against the AT decoder output. NAT predictions are discarded as soon as they are not in the top-\\beta AT results. The authors demonstrate speed-ups over beam search of 4.5x without significant BLEU loss.", "summary_of_the_review": "A reasonable idea, but the reported translation quality and speed-ups would need some work to make me trust them more. Tendency to oversell.", "strength_and_weaknesses": "The idea is motivated well, makes intuitive sense, and is described carefully. Speed-ups without loss in quality - what's not to like?\n\nThere are, of course, caveats, and it would have been good if the paper was more explicit about its limitations.  Perhaps the most obvious one is that SpecDec can only guarantee to match AT greedy output, and it is not clear how to use AT beam search as a base. The entire architecture is significantly more complex: Training a teacher model, distilling an AT and NAT model from it, and then combine both models in this decoding scheme is more cumbersome to maintain than running simple beam search. But I think that there are also non-obvious caveats when interpreting the results in Table 1 - both in terms of translation quality and speed up.\n\nTranslation quality: AT verifier b=5 and b=1 are *very* close together in terms of BLEU. It is known that KD moves beam search and greedy search closer together, but this is closer than I would expect. I also find it odd that the \"AT verifier (b=1)\" - besides on En-De - consistently outperforms the \"Teacher\" even though the teacher has the same or bigger model size and uses beam search instead of greedy search. So to get a better sense of how to read this I would suggest to\n(a) report SpecDec results with the Teacher as the AT verifier\n(b) report BLEURT/COMET instead / in addition to BLEU scores\nAnother thing to keep in mind is that (unlike SpecDec) SpecDec++ is a model combination for which an AT+NAT ensemble would be the right baseline to compare BLEU scores with.\n\nSpeed ups: The total number of compute operations is higher for SpecDec than for vanilla greedy AT decoding, so speed-ups are due to parallelization. But better parallelization can also be achieved by simple (sentence-level) batching, which (I believe) is not used in this work. The greedy AT runtime with sentence-level batching would be a valuable baseline. Furthermore, in practice, the decoder in Transformer encoder-decoders are often replaced by recurrent models due to the time complexity of self-attention.\n\nThe paper sometimes tends to oversell the contributions. For example: \"demonstrating its potential to become a de facto decoding standard in the future\nfor efficient and lossless seq2seq generation\" is a bit much. Perhaps unintentionally, calling SpecDec \"lossless\" suggests the absence of search errors which is misleading.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "kn8FcGMZpAa", "reviewer": "Reviewer_KQwP", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes speculative decoding, a decoding scheme for conditional NLG that aims to achieve the quality of traditional autoregressive approaches while retaining the speedup improvements of non-autoregressive approaches. The proposed framework combines a non-autoregressive transformer (NAT) to generate \"draft\" sequences of $k$ tokens and a standard autoregressive transformer (AT) to verify the proposed drafts. Since verification is parallelizable, this approach performs faster than usual autoregressive decoding. The experimental results reported by the authors show that this approach performs on par with greedy decoding and achieves a considerable inference speedup.", "summary_of_the_review": "Although the experimental results are convincing, the technical contribution is quite limited, as the proposed method is essentially Blockwise Parallel Decoding enhanced with other techniques from prior work. Thus, I am not convinced that the work has enough novelty to be presented in a top venue like ICLR. However, the authors' rebuttal and/or the discussion with the remaining reviewers may persuade me.\n\n**Update after rebuttal:**\nThe authors’ response has reinforced my positive opinion about the empirical relevance of their work. Nonetheless, I still think this work consists of a well-engineered refinement of prior work, with limited scientific contribution. Hence, my opinion is that this work is a better fit for an NLP-specific venue and, for this reason, I decided to keep my score. ", "strength_and_weaknesses": "Strengths:\n- The motivation of the paper is strong.\n- The paper is very clear and pleasant to read.\n- The experimental results are promising. In particular, achieving a 3x or more speedup while performing on par with greedy decoding and beam search in both MT and summarization is a significant achievement.\n- The fact that, in addition to MT, the paper also presents results for abstractive summarization is a plus.\n\nWeaknesses:\n1. The major weakness of the paper is its very high similarity with Blockwise Parallel Decoding (Stern et al., 2018). The decoding algorithm is essentially the same, with the only significant difference relying on the fact that the proposed method uses two separate models to generate drafts and verify them. The NAT model employed in this work is more advanced, but those advancements were also brought from prior work.\n2. The proposed approach works as a faster alternative to autoregressive mode-seeking algorithms (greedy decoding or beam search). Extending its principles to sampling-based approaches (top-k, nucleus, typical decoding, etc) would be an interesting contribution that is missing.\n3. The claim that SpecDec offers a \"3× *lossless* speedup for abstractive summarization\" is an overstatement, since SpecDec performs slightly worse than the teacher model.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "XB3pQf5hcz", "reviewer": "Reviewer_cfnL", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper introduces a faster decoding algorithm for autoregressive translation (AT) called Speculative Decoding (SpecDec), which achieves lossless speedup. Specifically, they combine the strengths of AT and non-autoregressive translation (NAT) and adopt a *draft* and *verify* strategy. For each step:\n- The NAT first generates a fixed-length sequence of draft tokens in parallel.\n- Then the AT verifies the longest acceptable prefix, reserves it, and proceeds to the next step. \n\nSpecDec's speedup comes from a high degree of parallelism: NAT is parallel, and the AT verification process uses teacher-forcing, which is also parallel. SpecDec is lossless because the verification step uses a strict strategy to determine the longest acceptable prefix, i.e., each token in the prefix must be the top-1 choice for the AT model. As a result, SpecDec produces the identical sequence as the greedy search of the AT. They also relax the criteria for the acceptable prefix and form the variant SpecDec++, which achieves more speedup and potential improvement of translation quality. They perform empirical experiments to demonstrate the superior performance of SpecDec and detail analyses of the key components and hyper-parameters. ", "summary_of_the_review": "This paper proposes a lossless acceleration algorithm for AT that cleverly combines the features of AT and NAT. The experimental results show that the proposed method performs well in terms of efficiency and performance.", "strength_and_weaknesses": "Pros:\n+ The most important contribution of this paper is that the proposed accelerated decoding algorithm is lossless. Unlike other acceleration methods for AT, such as half-precision inference, SpecDec produces the same results as greedy search. For online commercial translation systems, it is important to maintain the stability of the translation results.\n+ The design of SpecDec is clever. The authors have done a good job combining the advantages of NAT and AT. AT is serial, but it is parallel when using teacher-forcing. The authors take this to verify the NAT results, which greatly improves the overall parallelism.\n+ The SpecDec++ variant further speeds up the decoding by relaxing the acceptance criteria and potentially gives better results than the original.\n+ The authors provide an exhaustive analysis of the proposed algorithm, including the impact of hyper-parameters, the number of tokens accepted, etc. \n\nCons:\n- The major weakness is that SpecDec can not apply to beam search (beam size > 1). At least, it is not straightforward and not discussed by the authors. This makes \"lossless\" a bit overclaimed since AT model with beam search usually produces better results than greedy search.\n- The NAT model causes additional memory cost, which decreases the max batch size. From this point of view, SpecDec reduces parallelism to a certain extent.\n\nMinor:\n- It would be better to complete the conditions for the probabilities in Eq 6-7 to avoid misunderstanding whether the probabilities are AT or NAT models.\n- Table 1: What is the batch size?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject