A Generalized Framework of Sequence Generation with Application to Undirected Sequence Models
Authors: Elman Mansimov
Alex Wang
Kyunghyun Cho
Venue:  (2020)
Keywords: nlp
sequence modeling
natural language generation
machine translation
BERT
Sesame Street

Abstract: Undirected neural sequence models such as BERT (Devlin et al., 2019) have received renewed interest due to their success on discriminative natural language understanding tasks such as question-answering and natural language inference. 
The problem of generating sequences directly from these models has received relatively little attention, in part because generating from such models departs significantly from the conventional approach of monotonic generation in directed sequence models. We investigate this problem by first proposing a generalized model of sequence generation that unifies decoding in directed and undirected models. The proposed framework models the process of generation rather than a resulting sequence, and under this framework, we derive various neural sequence models as special cases, such as autoregressive, semi-autoregressive, and refinement-based non-autoregressive models. This unification enables us to adapt decoding algorithms originally developed for directed sequence models to undirected models. We demonstrate this by evaluating various decoding strategies for a cross-lingual masked translation model (Lample and Conneau, 2019). Our experiments show that generation from undirected sequence models, under our framework, is competitive with the state of the art on WMT'14 English-German translation. We also demonstrate that the proposed approach enables constant-time translation with similar performance to linear-time translation from the same model by rescoring hypotheses with an autoregressive model.

Under review as a conference paper at ICLR 2020
A GENERALIZED FRAMEWORK OF SEQUENCE GEN- ERATION WITH APPLICATION TO UNDIRECTED SE- QUENCE MODELS
Anonymous authors Paper under doublc-blind review
ABSTRACT
Undirected neural sequence models such as BERT (Devlin et al., 2019) have ceived renewed interest due to their success on discriminative natural language understanding tasks such question-answering and natural language inference. The problem of generating sequences directly from these models has received relatively little attention, in part because generating from such models departs significantly from the conventional approach of monotonic generation in directed sequence models. We investigate this problem by first proposing a generalized model of sequence generation that unifies decoding in directed and undirected models. The proposed framework models the process of generation rather than a resulting sequence, and under this framework, we derive various neural se- quence models as special cases, such as autoregressive, refinement-basse -utorrrregressvve models. This unification enables us to adapt decoding algorithms originally developed for directed sequence models to undi- rected models. We demonstrate this by evaluating various decoding strategies for a cross- lingual masked translation model (Lample and Conneau, 2019). Our experiments show that generation from undirected sequence models, under our framework, is competitive with the state of the art on WMT' 14 English-German translation. We also demonstrate that the proposed approach enables constant-time translation with similar performance to linear-time translation from the same model by rescoring hypotheses with an autoregressive model.
autreerutorersssvveee and
INTRODUCTION
Undirected neural sequence models such as BERT (Devlin al., 2019) have recently brought significant improvements to a variety of discriminative language modeling tasks such as question- answering and natural language inference. Generation of sequences from such models has received relatively little attention. Unlike directed sequence models, each word often depends on the full left and right context around it in undirected sequence models. Thus, decoding algorithm for an undirected sequence model must specify both how to select positions and what symbols to place in the selected positions. In this paper we formalize this process of selecting positions and replacing symbols as a generalized framework of sequence generation, and unify decoding from both directed and undirected sequence models under this framework. This framing enables to study generation on its own, independent from the specific parameterization of the sequence models.
Our proposed unified framework casts sequence generation as a process of determining the length of the sequence, and then repeatedly alternating between selecting sequence positions followed by generation of symbols for those positions. A variety of sequence models can be derived under this framework by appropriately designing the length distribution, position selection distribution, and symbol replacement distribution. Specifically, we derive popular neural decoding algorithms such monotonic autoregressive, non-autoregressive by iterative refinement and monotonic semi- autoregressive decoding as special cases of the proposed model.
This separation of coordinate selection and symbol replacement allows to build diverse set of decoding algorithms agnostic to the parameterization or training procedure of the underlying model. We thus fix the symbol replacement distribution variant of BERT and focus on deriving novel

---

Under review as a conference paper at ICLR 2020
generation procedures for undirected neural sequence models under the proposed framework. We design a coordinate selection distribution using a log- log-linear model and demonstrate that our model generalizes various fixed-order generation strategies, while also being capable of adapting generation order based on the content of intermediate sequences.
We empirically validate our proposal machine translation using a translation-variann of BERT called a masked translation model (Lample and Conneau, 2019). We design several generation strategies based on features of intermediate sequence distributions and compare them against the state-of-the-art monotonic autoregressive sequence model (Vaswani et al., 2017) on WMT' 14 English-Germant Our experiments show that generation from undirected sequence models, under our framework, is competitive with the state of the art, and that udaptive-oree order generation strategies generate sequences in different ways, including left-to-right, right-to-left and mixtures of these. This suggests the potential for designing and learning a more sophisticated coordinate selection mechanism.
Due to the flexibility in specifying coordinate selection mechanism, we design constant- time variants of the proposed generation strategies, closely following the experimental setup of Ghazvininejad et al. (2019). Our experiments reveal that we can do constant-time translation with the budget as low as 20 iterations (equivalently, generating sentence of length 20 in the conventional approach) while achieving similar score to linear- time translation from the same masked translation model. This again confirms the potential of the proposed framework and generation strategies.
2 A GENERALIZED FRAMEWORK OF SEQUENCE GENERATION
We propose a generalized framework of probabilistic sequence generation to unify both directed and undirected neural sequence models under a single framework. In this generalized framework, we have generation sequence G of pairs of an intermediate sequence Y (ví, (vf.-..,,ff, v2. and the corresponding coordinate sequence Z' (zf,.... =f)), where yi E V. V is vocabulary, L is length of a sequence, T is a number of generation steps, and of E {0, 1}. The coordinate sequence indicates which of the current intermediate sequence
be replaced. That is, each consecutive 2++ yy! + 2 y/ where 0/ E V is a new
pairs are related to each other by y, = (1 2 symbol for the position i. This sequence of pairs G describes procedure in which final sequence Y is created, starting from an empty sequence Y = ((mask) ..... (mask) ) and empty coordinate sequence Z (0, ..., 0). This procedure of sequence generation is probabilistically modelled
p[G
p((Ix)
IIII
p(z p 2
p(ub
(c) length prediction
(a) coordinate selection
(b) symbol replacement
We condition the whole process on an input variable X to indicate that the proposed model is applicable to both conditional and unconditional sequence generation. In the latter case, X 0.
We first predict the length L of a target sequence Y according to p( X) distribution to which we refer as (c) length prediction. At each generation step t. we first select the next coordinates Z for which the corresponding symbols will be replaced according to p(z + y Z', X),, to which we refer as (a) coordinate selection. Once the coordinate sequence is determined. we replace the corresponding symbols according to distribution P(y,+Ily/s Z'+1, 1++1,)), leading to the next intermediate sequence y++1, From this sequence generation framework, we recover the sequence distribution p(Y|X) by marginalizing out all the intermediate and coordinate sequences except for the final sequence Y In the remainder of this section, we describe several special cases of the proposed framework, which are monotonie autoregressive, non-autoregresssvve semi- cutr-autorerressivee neural sequence models.
2.1 SPECIAL CASES
Monotonic autoregressive neural sequence models We first consider one extreme case of the generalized sequence generation model, where we replace one symbol at time, monotoni- cally moving from the left-most position to the right-most. In this case, we define the co- ordinate selection distribution of the generalized sequence generation model in Eq. (1) (a) as p(z = 1 X) = 1(2 = =1), where (-() is an indicator function and 2 = 1. This coordinate selection distribution is equivalent to saying that we replace one symbol at a time, shifting from the left-most symbol to the right-most symbol, regardless of the content of inter- mediate sequences. We then choose the symbol replacement distribution in Eq. (1) (b) to be
2

---

Under review as a conference paper at ICLR 2020
(+] ply (Yst, x) = foot-illf lei v2...... .2.............................. .., X), for 2/41 = 1. Intuitively, we limit the dependency of vitl only the symbols to its left in the previous intermediate sequence v2(64+1) and the in- put variable X. The length distribution (I) (c) implicitly defined by considering how often the special token (cos). which indicates the end of sequence, appears after L generation steps: Si
p()]X) E I p (eos) M2 X). With these choices, the proposed generalized
model reduces p(G - p(y Mei. X) which is widely- monotonic autoregressive neural sequence model.
Non-autoregressive neural sequence modeling by iterative refinement We next consider the other extreme in which we replace the symbols in all positions at every single gen- eration step (Lee et al., 2018). We design the coordinate selection distribution to be Zz, X))= = vi {I....,, L). implying that we replace the symbols in all the posi- tions. We then choose the symbol replacement distribution to be as it was in Eq. (1) (b). That is, the distribution over the symbols in the position i in a new intermediate sequence y; is conditioned on the entire current sequence Y and the input variable X. We do not need to assume any relationship between the number of generation steps T and the length of sequence L in this case. The length prediction distribution p( L X) is estimated from training data.
1 =
Semi-autoregreesive neural sequence models Wang al. (2018) recently proposed compromise between autoregressive and non-autoregresive sequence models by predicting a chunk of symbols in parallel time. This approach can also be put under the proposed generalized model. We first extend the coordinate selection distribution of the autoregressive sequence model into
= = f1, 00
if =fus 1, Vj E otherwise,
++1 + = 1| "x,"",,',x) p
where k is group size. Similarly modify the symbol replacement distribution:
p L X) p(yit1 (o X), (k]].
for 2 = 1. This naturally implies that T = [L/k].
3 DECODING FROM MASKED LANGUAGE MODELS
In this section, we give an overview of masked language models like BERT, cast Gibbs sampling under the proposed framework, and then this connection to design set of approximate, deterministic decoding algorithms for undirected sequence models.
3.1 BERT AS AN UNDIRECTED SEQUENCE MODEL
BERT (Devlin et al., 2019) is masked language model: It is trained to predict word given the word's left and right context. Because the model gets the full context, there are no directed dependencies among words, so the model is undirected. The word to be predicted is masked with special (mask) symbol and the model is trained to predict p(ssle<s, (mask) X)). We refer to this as the conditional BERT distribution. This objective was interpreted as a stochastic approximation to the pseudo liceliieldood objective (Besag, 1977) by Wang and Cho (2019). This approach of full- context generation with pseudo log-likelihood maximization for recurrent networks was introduced earlier by Berglund et al. (2015). More recently, Sun et al. (2017) use it for image caption generation.
Recent work (Wang and Cho, 2019; Ghazvininejad al., 2019) has demonstrated that undirected neural sequence models like BERT can learn complex sequence distributions and generate well- formed sequences. such models, is relatively straightforward to collect unbiased samples using, for instance, Gibbs sampling. But due to high variance of Gibbs sampling, the generated sequence is not guaranteed to be high-quality relative to ground-truth sequence. Finding a good sequence in a deterministic manner is also nontrivial.
number of papers have explored using pretrained language models like BERT to initialize sequence generation models. Ramachandran al. (2017), Song et al. (2019), and Lample and Conneau (2019) use pretrained undirected language model to initialize a conventional monotonic autoregressive sequence model, while Edunov et al. (2019) use BERT-like model initialize the lower layers of
3

---

Under review as a conference paper at ICLR 2020
generator, without finetuning. Our work differs from these in that attempt to directly generate from the pretrained model, rather than using it as a starting point to learn another model.
3.2 GIBBS SAMPLING THE GENERALIZED SEQUENCE GENERATION MODEL
Gibbs sampling: uniform coordinate selection To cast Gibbs sampling into our framework, we first assume that the length prediction distribution P(L is estimated from training data, as is the case in the von-autoregressive neural sequence model. In Gibbs sampling, we often uniformly select new coordinate at random, which corresponds to p(z, 12f+1 = 1|Y St Z X) 1/L with the
constraint that Σ of = 1. By using the conditional BERT distribution symbol replacement distribution, we end up with Gibbs sampling.
Adaptive Gibbs sampling: non-uniform coordinate selection Instead of selecting coordinates uniformly at random, we can base selections on the intermediate sequences. We propose log-linear model with features oe based the intermediate and coordinate sequences:
p( 1/ Z X) exp andi (Y', Z x,
again with the constraint that Σi=1 sharpness of the coordinate selection distribution. A moderately high smooths the coordinate selection distribution and ensures that all the coordinates are replaced in the infinite limit of T, making it a valid Gibbs sampler (Levine and Casella, 2006).
0 is a temperature parameter controlling the
We investigate three features de. (1) We compute how peaked the conditional distribution of each position given the symbols in all the other positions is by measuring its negative entropy: Onegone (Y', 2t, xX
lB + (mask) X)). In other words, we prefer position if we know the change in has high potential to alter the joint probability p(Y [X) =p(y1, U/,.... VL (X). (2) For each position we measure how unlikely the current symbol (y/, not yf+1) ) is under the new conditional distribution: dlogp (Y,, Zz, X)
-Hly)
log p(y: y/lv' (mask) 3/ X). Intuitively, we prefer to replace symbol if it is highly incompatible with the input variable and all the other symbols in the current sequence. (3) We encode a positional preference that does not consider the content of intermediate sequences: Opes (i)
log(It il + <), where e > 0 is small constant scalar to prevent log O. This feature encodes our preference to generate from left to right there no information about the input variable nor of any intermediate sequences.
Unlike the special cases the proposed generalized model in $2, the coordinate at each generation step is selected based on the intermediate sequences, previous coordinate sequences, and the input variable. We mix the features using scalar coefficients Onegennt Otogp and Aposs which are selected or estimated to maximize target quality measure validation set.
3.3 OPTIMISTIC DECODING AND BEAM SEARCH FROM A MASKED LANGUAGE MODEL
Based on the adaptive Gibbs sampler with the coordinate selection distribution Eq. (2), we can now design inference procedure to approximately find the most likely sequence from the sequence distribution p( X) by exploiting the corresponding model of sequence generation. In doing so, naive approach is to marginalize out the generation procedure G using Monte Carlo method: argmaxy (X) = argmaXyT 37 Eg p(Y" m
Sermmrrrreeee Z ,X), where GTD the m-
th sample from the sequence generation model. This approach suffers from high variance and non-deterministie hehavior, and is less appropriate for practical use. We instead propose an optimistic decoding approach following equation (1):
argmax log logp(I.(X) + Σ Σ
log logp(s!+1 yst Z X) + 21 1+1 logg(o/ X).
(3)
f.y1 Y 7
The proposed procedure is optimistic in that we consider sequence generated by following the most likely generation path to be highly likely under the sequence distribution obtained by marginalizing out the generation path. This optimism in the criterion more readily admits deterministic approximation scheme such as greedy and beam search, although it as intractable to solve this problem as the original problem which required marginalization of the generation path.
4

---

Under review as a conference paper at ICLR 2020
Baseline Autoregressive
Decoding from undirected sequence model
T
Uniform
Least2Most Left2Right
Easy-First
8
L
25.33 26.84
21.01
24.27
23.08
23.73
4
L
22.16
25.15
23.81
24.13
L
22.74
25.66
24,42
24.69
2L
21.16
24.45
23.32
23.87
2L
21.99
25.14
23.81
24.14
L
29.83
26.01
28.34
28.85
29.00
I
30.92
27.07
29.52
29.03
29.41
4
7
28.07
30.46
29.84
30.32
2L
26.24
28.64
28.60
29.12
2L
26.98
29.50
29.02
29.41
Table 1: Results (BLEU1) on WMT En translation using various decoding algorithms and different settings of beam search width (b) and number of iterations (7) as a function of sentence length (L). For each sentence use 4 most likely sentence lengths. denotes rescoring generated hypotheses using autoregressive model instead of proposed model.
Length-conditionee conditionnd beam search To solve this intractable optimization problem, we design heuristic algorithm, called length-conditioned beam search. Intuitively, given length L, this algo- rithm performs beam search over the coordinate and intermediate token sequences. At each step of this iterative algorithm, we start from the hypothesis set H that contains K generation hypotheses:
H--1
{ hh (09g) ..... 1 - (2) )))
Each generation hypothesis has score: k=1
K
t-1 L s(h 1--1 = log p (1X) +
log pl
Niee 2- x)) log (x)x
#=1
For notational simplicity, we drop the time superscript Each of the generation hypotheses first expanded with K' candidate positions according to the coordinate selection distribution:
K' } JK-1 arg top- wE(I.....I) s(ha) -ogp((E, = 20-
{ (hw
k=1
=s [|one-hor(w))
so that we have K x K' candidates {ir,,e) where each candidate consists of hypothesis bi with the position sequence extended by the selected position u and has score s(h; potne-hot(ux.ee (2).)))) We then expand each candidate with the symbol replacement distribution:
K" } Jmez1 arg top- K" ee sha///one hotellone-ho(uuue honeee,tt )) + log p(y = - XX)
s(hk [1(Pe- Mt-1 S3 25
This results in K x K' x K" candidates fha,er, kn each consisting of hypothesis hi with inter- mediate and coordinate sequence respectively extended by uk,K',"" and ux.k Each hypothesis has score s(ha, [|( <= U,,,","" N²,, ÿ1-1 )). which we use to select K candidates to form new s(h).
hypothesis set H arg top- K he(he,erw")) ) k."
After iterating for a predefined number T steps, the algorithm terminates with the final set of K generation hypotheses. We then choose one of them according to prespecified criterion, such as Eq. (3), and return the final symbol sequence Y
hu [lllonehho((ua, (o)(u) appends one one-hot(Us,,)) ) at the end of the sequence the coordinate soquences in fg. "he [[2-) (Yeeyy M,,,,,, V5-1,, denotes creating new sequence from r-t by replacing the w symbol with Ve Weeaee en, and appending this sequence the intermediate sequences ha.

---

Under review as a conference paper at ICLR 2020
4 EXPERIMENTAL SETTINGS
Data and preprocessing We evaluate our framework WMT" 14
translation. The dataset consists of 4.5M parallel sentence pairs. We preprocess this dataset by tokenizing each sentence using script from Moses (Koehn et al., 2007) and then segmenting each word into subword units using byte pair encoding (Sennrich et al., 2016) with joint vocabulary of 60k tokens. We use newstest-2013 and newstest-2011 as validation and test sets respectively.
Sequence models We base our models off those of Lample and Conneau (2019). Specifically, we use Transformer (Vaswani al., 2017) with 1024 hidden units, 6 layers, 8 heads, and Gaussian error linear units (Hendrycks and Gimpel, 2016). We use a pretrained model trained using masked language modeling objective (Lample and Conneau, 2019) on 5M monolingual sentences from WMT NewsCrawl 2007-2008. To distinguish between English and German sentences, special language embedding added as an additional input to the model.
We adapt the pretrained model to translation by finetuning it with a masked translation objective (Lample and Conneau, 2019). We concatenate parallel English and German sentences, mask out a subset of the tokens in either the English German sentence, and predict the masked out tokens. We uniformly mask out 0 - 100% tokens as in Ghazvininejad et al. (2019). Training this way more closely matches the generation setting where the model starts with an input sequence of all masks.
Baseline model We compare against a standard Transformer encoder-decodee autoregressive neural sequence model (Vaswani et al., 2017) trained for left-to-right generation and initialized with the same pretrained model. We train a separate autoregressive model to translate an English sentence to a German sentence and vice versa, with the same hyperparameters as our model.
Training details We train the models using Adam (Kingma and Ba, 2014) with an inverse square root learning rate schedule, learning rate of 10-4, B1 0.9, 32 0.98, and dropout rate of 0.1 (Srivastava et al., 2014). Our models are trained on 8 GPUs with a batch size of 256 sentences.
Decoding strategies We design four generation strategies for the masked translation model based on the fog-linear coordinate selection distribution in $2:
1. Uniform: - oo, i.c., sample position uniformly at random without replacement
2. Left2Right: Onegent 0, Aoog = 0, Opps =
3. Least2Most (Ghazvininejad et al., 2019): O'negent = O, Oloog = 1, Oppos =
4. Easy-First: Onegent
1, Mlog 1, a'pos =0
We use beam search described in $3.3 with K" fixed to i.e., we consider only one possible po- sition for replacing symbol per hypothesis each time of generation. We vary K = K" between 1 (greedy) and 4. For each source sentence, we consider four length candidates according to the length distribution estimated from the training pairs, based on early experiments showing that using only four length candidates performs as well as using the ground-truth length (see Table 2). Given the four candidate translations, we choose the best one according to the pseudo log probaabiiyy of the final sequence (Wang and Cho, 2019). Additionally, experimented with choosing best translation according to log- -og-brbbability of the final sequence calculated by an autoregressive neural sequence model.
# of length candidates
Gold
2
3
En-De Dc
22.50
22.22
22.76
23.01
23.22
28.05
26.77
27.32
27.79
28.15
Table 2:
Effect of the number of length candi- dates considered during decoding on BLEU, mea- sured on the validation set (newstest-2013) using the easy-first strategy.
linear-time and constant-time decoding. In the linear-time scenario, the number of decoding iterations T grows linearly w.r.t. the length of a target sequence L. We test setting T' to L and 2L. In the constant-time scenario, the number of iterations is constant w.r.t. the length of a translation, i.e., T = 0(1). At the t-th iteration of generation, we replace or-many symbols, where o, either a constant [L/T] or linearly anneals from L to 1 (L- + 1) as done by Ghazvininejad et al. (2019).
Decoding scenarios We consider two decoding scenarios:
'tttps: / /dd. fba i ipbb 1 seiiiille les. com/ XIM /mmmm mmm_ende______ 10___1024pppppp WWe set Olgp 0.9 for Dn hased the validation set performance.

---

Under review as a conference paper at ICLR 2020
0.0
0.0
0.5
0.5
Relative Time Stee
1.0
1.0
04
Eisy- bn
Leasi2Most, Er->De
0.0
0.0
0.5
0.5
1.0
022
04
0,5
6.6
0.0
0.2
CA
0.6
Easy-First, De->En
Least2Most De->En
Figure 1: Generation orders given by easy-first and least2most coordinate selection. We group the orders into five clusters and visualize cluster centers with normalized positions (x-axis) over normalized steps (y-axis). We use greedy search with I. iterations on the development set.
LINEAR-TINE DECODING: RESULT AND ANALYSIS
Main findings We present translation quality measured by BLEU (Papineni al., 2002) in Table 1. We identify number of important trends. (1) The deterministic coordinate selection strategies (left2right, least2most and easy-first) significantly outperform selecting coordinates uniformly at random, by up to 3 BLEU in both directions. The success of these relatively simple hand- crafted coordinate selection strategies suggest avenues for further improvement for generation from undirected sequence models. (2) The proposed beam search algorithm for undirected sequence models provides an improvement of about BLEU over greedy search, confirming the utility of the proposed framework way to move decoding techniques across different paradigms of sequence modeling. (3) Rescoring generated translations with an autoregressive model adds about 1 BLEU across all coordinate selection strategies. Rescoring adds minimal overhead as it is run in parallel. (4) Different generation strategies result in translations of varying qualities depending on the setting. On English-German translation, left2right is the best performing strategy, achieving up to 25.66 BLEU. Easy-first and left2right perform nearly the same in the other direction, achieving up to 30.46 BLEU. (5) We see little improvement in refining a sequence beyond the first pass, though we suspect this may be due to the simplicity of the coordinate selection schemes tested. (6) Lastly, the masked translation model lags behind the more conventional neural autoregressive model, although the difference is within BLEU point when greedy search is used with the autoregressive model and approximately 2 BLEU with beam search. We hypothesize that a difference between train and test settings causes slight performance drop of masked translation model compared to conventional autoregressive model. In the standard autoregressive case, the model is explicitly trained to generate in left-to-right order, which matches the test time usage. By randomly selecting tokens to mask during training, our undirected sequence model trained to follow all possible generation orders and to use context from both directions, which is not available when generating left-to-right test time.
Adaptive generation order The least2most and easy-first generation strategies automatically adapt the generation order based on the intermediate sequences generated. We investigate the resulting generation orders on the development set by presenting each as a 10-dim vector (downsampling as necessary), where each element corresponds to the selected position in the target sequence normalized by sequence length. We cluster these sequences with k-means clustering and visualize the clusters centers as curves with thickness proportional the number of sequences in the cluster in Fig. 1.
In both strategies, we see two major trends. First, many sequences are generated largely monotonically either left-to-right or right-to-left (see, e.g., green, blue and orange clusters in easy-first, En->De, and blue, orange, and red clusters in least2most, De->En.) Second, another cluster of sequences are generated from outside in, as seen in the red and purple clusters in easy-first, En-+De, and green, orange, and purple clusters in least2most, En- We explain these two behaviors by the availability of contextual evidence, or lack thereof. At the beginning of generation, the only two mon-mask symbols the beginning and end of sentence symbols, making it easier predict symbol at the beginning or end of the sentence. As more symbols are filled near the boundaries, more evidence is accumulated for the decoding strategy to accurately predict symbols near the center.
7

---

Under review as a conference paper at ICLR 2020
T
Uniform
Left2Right
Least2Most
Easy-First
Hard-First
L-1
22.38
22.38
27.14
22.21
26.66
10
L-17
23.64
23.64
28.63
23.79
28.46
10
[L/T]
22.43
21.92
24.69
25.16
23.46
20
L-1 1
26.01
26.01
28,54
22.24
28.32
20
1-+1*
27.28
27.28
30.13
24.55
29.82
20
[L/T]
24.69
25.94
27.01
27.49
25.56
Table 3: Constant-time machine translation on WMT 14 De-+En with different settings of the budget (T) and number of tokens predicted each iteration (o,). denotes rescoring generated hypotheses using autoregressive model instead of proposed model.
This process manifests either as monotonic outside-in generation. We present sample sequences generated using these strategies in Appendix D.
CONSTANT-TIME DECODING: RESULT AND ANALYSIS
The trends in constant-time decoding noticeably differ from those in linear-time decoding. First, the left2right strategy significantly lags behind the least2most strategy, and the gap is wider (up to 4.7 BLEU) with tighter budget (T 10). This gap suggests that a better, perhaps learned, coordinate selection scheme could further improve constant-time translation. Second, the easy-first strategy is surprisingly the worst in constant-time translation, unlike in linear-time translation. To investigate this degradation, we test another strategy where we flip the signs of the coefficients in the log-linear model. This new hard-fire strategy works on par with least2most, which again confirms that decoding strategies must be selected based on the target tasks and decoding setting.
With fixed budget of T 20, linearly annealing K, and least2most decoding, constant-time translation can achieve translation quality comparable to linear-time translation with the same model (30.13 vs. 30.46). and beam-search translations using the strong neural autoregressive model (30.13 vs 30.92). Even with tighter budget of 10 iterations (less than half the average sentence length), constant-time translation loses only 1.8 BLEU points (28.63 vs. 30.46), which confirms the finding by Ghazvininejad et al. (2019) and offers new opportunities in advancing constant-time machine translation systems. Compared to other constant-ting machine translation approaches, our model outperforms many recent approaches by Gu et al. (2018); Lee et al. (2018); Wang al. (2019); Ma et al. (2019), while being comparable to Ghazvininejad et al. (2019); Shu et al. (2019). We present full results in Table 4 in Appendix A.
7 CONCLUSION
We present a generalized framework of neural sequence generation that unifies decoding in directed and undirected neural sequence models. Under this framework, we separate position selection and symbol replacement, allowing us to apply diverse set of generation algorithms. inspired by those for directed neural sequence models, to undirected models such as BERT and its translation variant.
We evaluate these generation strategies on WMT' 14 En-De machine translation using a recently proposed masked translation model. Our experiments reveal that undirected neural sequence models achieve performance comparable to conventional, state-of-the-ard autoregressive models, given an appropriate choice of decoding strategy. We further show that constant-time translation these models performs similar to linear-time translation by using one of the proposed generation strategies. Analysis of the generation order automatically determined by these adaptive decoding strategies reveals that most sequences generated either monotonically outside-in.
We identify two promising extensions to our work. First, we could have a model learn the coordinate selection distribution from data to maximize translation quality. Doing would likely result in better quality sequences as well as the discovery of more non-trivee non-trivial generation orders. Second, we only apply framework to sequence generation, but could also apply it other structured data such as grids (for e.g. images) and arbitrary graphs. Overall, we hope that our generalized framework opens new avenues in developing and understanding generation algorithms for variety of settings.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Mathias Berglund, Tapani Raiko, Mikko Honkala, Leo Kärkkäinen, Akos Vetek, and Juha T Karhunen. Bidirectional recurrent neural networks generative models. In Advances in Neural Information Processing Systems, pages 856-864, 2015.
Julian Besag. Efficiency of pseudolikelihood estimation for simple gaussian fields. 1977.
Jacob Devlin, Ming-Wei Chang, and Kristina Toutanova Kenton Lee. Bert: Pre-training of deep bidirectional transformers for language understanding. NAACL, 2019.
Sergey Edunov, Alexei Baevski, and Michael Auli. Pre-trained language model representations for language generation, 2019.
Marjan Ghazvininejad, Omer Levy, Yinhan Liu, and Luke Zettlemoye. Constant- machine translation with conditional masked language models. arXiv preprint wrXiv:194.0093: 2019.
Jiatao Gu, James Bradbury, Caiming Xiong, Victor O. K. Li, and Richard Socher. Non-autoregressive neural machine translation. CoRR, abs/1711 .02.2022122222 2018.
Jiatao Gu, Qi Liu, and Kyunghyun Cho. Insertion-basee decoding with automatically inferred generation order. CoRR, obs/1902.01370, 2019.
Dan Hendrycks and Kevin Gimpel. Bridging nonlinearities and stochastic regularizers with gaussian error linear units. arXiv preprint
2016.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 1412.6980, 2014.
Philipp Kochn, Hicu Hoang, Alexandra Birch, Chris Callison-Burch, Marcello Federico, Nicola Bertoldi, Brooke Cowan, Wade Shen, Christine Moran, Richard Zens, et al. Moses: Open source toolkit for statistical machine translation. In ACL, 2007.
Guillaume Lample and Alexis Conneau. Cross-lingual language model pretraining. arXiv preprint arXiv:190..07291, 2019.
Jason Lee, Elman Mansimov, and Kyunghyun Cho. Deterministic aun-autoreeressive neural sequence modeling by iterative refinement. arXiv preprint arXiv: (802.0//00000000 2018.
Richard A Levine and George Casella. Optimizing random scan gibbs samplers. Journal of Multivariate Analysis, 27110)2071-2104 2006.
Xuezhe Ma, Chunting Zhou, Xian Li, Graham Neubig, and Eduard Hovy. Flowseq: Non-
autoregressive conditional sequence generation with generative flow. arXiv preprint 1909.02480. 2019.
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 on association for computational linguistics, pages 311-318 Association for Computational Linguistics, 2002.
Prajit Ramachandran, Peter Liu, and Quoe Le. Unsupervised pretraining for sequence to sequence learning. Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, 2017. doi: 10. 10.18653/v1/117-1000 1039. httpttt: www..o...c.. www.doo....g..... 18653//11.113111.11 d17-1039.
Rico Sennrich, Barry Haddow, and Alexandra Birch. Neural machine translation of rare words with subword units. ACL, 2016.
Raphael Shu, Jason Lee, Hideki Nakayama, and Kyunghyun Cho. Latent-variable non-autoregressive neural machine translation with deterministic inference using delta posterior. arXiv preprint 1908.07181, 2019.
Kaitao Song. Xu Tan, Tao Qin, Jianfeng Lu, and Tie- Yan Liu. Mass: Masked sequence to sequence pre-training for language generation, 2019.

---

Under review as a conference paper at ICLR 2020
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, llya Sutskever, and Ruslan Salakhutdinov. Dropout: simple way to prevent neural networks from overfitting. 2014.
Mitchell Stern, William Chan, Jamie Kiros, and Jakob Uszkoreit. Insertion transformer: Flexible
sequence generation via insertion operations. CoRR, abs/1902.03249, 2019.
Qing Sun, Stefan Lee, and Dhruv Batra. Bidirectional beam search: Forward- inference in neural sequence models for fill-in-the- blank image captioning. 2017.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. In NIPS, 2017.
Alex Wang and Kyunghyun Cho. Bert has a mouth, and it must speak: Bert as markov random field language model. arXiv preprint arXiv: /902.04094, 2019.
Chunqi Wang. Ji Zhang, and Haiqing Chen. Semi- cuni-auuoreeressive neural machine translation, arXiv preprint arXiv:1808.088 2018.
Yiren Wang, Fei Tian, Di He, Tao Qin, ChengXiang Zhai, and Tie-Yan Liu. Non-autoregressive machine translation with auxiliary regularization. arXiv preprint 1902.10245, 2019.
Sean Welleck, Kianté Brantley, Hal Daumé, and Kyunghyun Cho. Non-monotonic sequential text generation. CoRR, abs/190..02192, 2019.
10

---

Under review as a conference paper at ICLR 2020
20
L>R
10
EF
40
Delta Energy
Lengths
25
27-30
lteration
Figure Average difference in energy t between sequences generated by selecting positions uniformly at random versus by different algorithms, over the course of decoding.
A COMPARISON WITH OTHER NON-AUTORFFGRESSIVE NEURAL MACHINE TRANSLATION APPROACHES
We present the comparison of results of our approach with other constant-time machine translation approaches in Table 4.
B NON-MONOTONIC NEURAL SEQUENCE MODELS
The proposed generalized framework subsumes recently proposed variants of non-monotonic gen- eration (Welleck et al., 2019; Stern et al., 2019; Gu et al., 2019). Unlike the other special cases described above, these non-monotonic generation approaches learn not only the symbol replacement distribution but also the coordinate selection distribution, and implicitly the length distribution, from data. Because the length of a sequence often not decided in advance, the intermediate coordinate sequence Z' and the coordinate selection distribution coordinates rather than absolute coordinates. We do not go into details these recent algorithms, but emphasize that all these approaches special cases of the proposed framework, which further suggests other variants of non-monotonic generation.
reparameterized
work with relative
C ENERGY EVOLUTION OVER GENERATION STEPS
While the results in Table indicate that our decoding algorithms find better generations in terms of BLEU relative to uniform decoding, we verify that the algorithms produce generations that are more likely according to the model. We do so by computing the energy (negative logit) of the sequence of intermediate sentences generated while using an algorithm, and comparing the average energy of intermediate sentences generated by picking positions uniformly at random. We plot this energy difference over decoding in Figure We additionally plot the evolution of energy the sequence by different position selection algorithms throughout generation process in Figure 3. Overall, find that left-to-right, least-to-most, and easy-first do find sentences that are lower energy than the uniform baseline the entire decoding process. Easy- fasy-first produces sentences with the lowest energy, followed by teast-to-mont and then left-to-right.
D SAMPLE SEQUENCES AND THEIR GENERATION ORDERS
We present sample decoding processes using the easy-first decoding algorithm on De-=En with
b 1, I, in Figures 4, 5, 6, and 7. We highlight examples decoding in right-to-lefftto-right

---

Under review as a conference paper at ICLR 2020
Energy throughout Generation Process
Relative energy (to initial energy)
1.0
Uniform L->-R
0.3
E-F
0.0
-0.5
10
12
14
22
Relative iteration step
Figure 3: Evolution of the energy of the sequence J over the course of decoding by different position selection algorithms.
to-left order, outside-in, left-to-right, and right-to-left orders, which respectively correspond to the orange, purple, red, and blue clusters from Figure 1, bottom left. These example demonstrate the ability of the easy-first coordinate selection algorithm to adapt the generation order based on the intermediate sequences generated. Even in the of largely monotonic generation order (left-to- right and right-to-left), the algorithm has the capacity to make small changes to the generation order as needed.
12

---

Under review as a conference paper at ICLR 2020
WMT2014
Models
EN-DE
DE-EN
AR Transformer base (Vaswani et al., 2017)
27.30
AR (Gu et 2018)
23.4
NAR (+Distill +FT +NPD S=100)
21.61
AR (Lee et al., 2018)
24.57
28.47
Adaptive NAR Model
16.56
Adaptive NAR Model (+Distill)
21.54
25.43
AR (Wang al., 2019)
27.3
31.29
NAT-REG (+Distill)
20.65
24.77
NAT-REG (+Distill +AR rescoring)
24.61
28.90
AR (Ghazvininejad al., 2019)
27.74
31.09
CMLM with 4 iterations
22.25
CMLM with 4 iterations (+Distill)
25.94
29.90
CMLM with 10 iterations
24.61
CMLM with 10 iterations (+Distill)
27.03
30.53
AR (Shu et al., 2019) Latent-Variabl NAR
26.1
11.8
Latent-Variable NAR (+Distill)
22.2
Latent-Variahh NAR (+Distill +AR Rescoring)
25.1
AR (Ma al., 2019)
27.16
31.44
FlowSeq-bass (+NPD n 30)
21.15
26.04
FlowSeq-base (+Distill +NPD n 30)
23.48
28.40
AR (ours)
26.84
30.92
Contant-time iterations
21.98
27.14
Contant-time iterations (+AR Rescoring)
24.53
28.63
Contant-time 20 iterations
23.92
28.54
Contant-time 20 iterations (+AR Rescoring)
25.69
30.13
Table BLEU scores on WMT' En-+De and De-+En datasets showing performance of various constant-time machine translation approaches. Each block shows the performance of autoregressive model baseline with their proposed approach. AR denotes autoregressive model. Distill denotes distillation. AR rescoring denotes rescoring of samples with autoregressive model. FT denotes fertility. NPD denotes noisy parallel decoding followed by rescoring with autoregressive model.
13

---

Under review as a conference paper at ICLR 2020
Iteration
Right-oo-Leff-o-RRigh------
(source)
Würde es mir je gelingen an der Universität Oxford normales Leben zu ftihren
2
Oxford
3
Oxford ?
ever
Oxford
5
ever
of Oxford ?
6
Would I ever
of Oxford
7
Would I ever
normal of Oxford ? of Oxford ? normal the Oxford ?
8
Would I
normal
Would ever
10
Would leer
normal at the University of Oxford
11
Would ever
normal life the University of Oxford
12
Would I ever live normal life at the University of Oxford ?
Would ever live a normal life at University of Oxford
14
Would ever able live a normal life at the University of Oxford
15
Would ever be able live normal life at the University of Oxford ?
16
Would ever be able to live normal life at the University of Oxford
(target)
Would ever be able to lead normal life at Oxford
Figure 4: Example sentences generated following an tight generation order, using the easy-first decoding algorithm on De
Iteration
Outside-In
(source)
Doch ohne zivilgesellscaatticce Organisationen könne eine Demokratic nicht funktionicren.
cannot
democracy cannot
without democracy cannot
5
But without democracy cannot work.
without
democracy cannot work.
But without
democracy cannot work
But without society
democracy cannot work But without society a democracy cannot work
10
But without civil society democracy cannot work..
11
But without civil society organisations, democracy cannot work. without civil society organisations, democracy cannot function.
(target)
Figure 5: Example sentences generated following an outside-in generation order, using the easy-first decoding algorithm on De->En.
Iteration
Left-to-Right
(source)
Denken Sie, dass die Medien zu viel vom PSG erwarten
Do you
Do you think
-
5
Do you think
PS
Do you think
PS @G
Do you think media
PS @G
Do you think the media
PS @G
Do you think the media expect
PS @
10
Do you think the media expect much PS @G
you think the media expect too much Do you think the media expect too much PS @G
@G
12 (target)
Do you think the media expect too much of PS @G?
Figure 6: Example sentences generated following an left-to-right generation order, using the easy-first decoding algorithm on De-IEn.
14

---

Under review as a conference paper at ICLR 2020
Iteration
Right-to-Lefi
(source)
Ein weiterer Streitpunkt: die Befugnisse der Armee.
army.
of army..
of the army..
powers of the army
the powers of the army.
the powers of army..
point: the powers of the army
contentious point: the powers of the army.
10
Another contentious point: the powers of the army.
(larget)
Another issue the powers conferred on the army.
Figure 7: Example sentences generated following an right-to-left generation order, using the easy-first decoding algorithm on De-+En.
15


Reviews:
[{"review_id": "ryeBboGP9B", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a generalized framework for sequence generation that can be applied to both directed and undirected sequence models. The framework generates the final label sequence through generating a sequence of steps, where each step generates a coordinate sequence and an intermediate label sequence. This procedure is probabilistically modeled by length prediction, coordinate selection and symbol replacement. For inference, instead of the intractable naive approach based on Gibbs sampling to marginalize out all generation paths, the paper proposes a heuristic approach using length-conditioned beam search to generate the most likely final sequence. With the proposed framework, the paper shows that masked language models like BERT, even though they are undirected sequence models, can be used for sequence generation, which obtains close performance to the traditional left-to-right autoregressive models on the task of machine translation.\n\nOverall the paper has significant contributions in the following aspects:\n1. It enables undirected sequence models, like BERT, to perform decoding or sequence generation directly, instead of just serving as model pre-training.\n2. The proposed framework unifies directed and undirected sequence models decoding, and it can represent a few existing sequence model decoding as special cases.\n3. The coordinate sequence selection function in the framework can be dependent on the intermediate label sequence. A few simple selection approaches proposed in the paper are shown to be effective. It could be further extended. \n4. The analysis of the coordinate selection order is interesting and helpful for understanding the algorithm.\n5. The experiment results for decoding masked language models on machine translation are promising. It also provides the comparison to recent related work on non-autoregressive approaches.\n\nThe presentation of the paper is also clear. I am leaning towards accepting the paper.\n\nHowever, there are some weaknesses:\n\n1. It should be analyzed more why different coordinate selection approaches perform differently in linear-time decoding vs. constant-time decoding. Even in constant-time decoding, the conclusion varies in different decoding setting, easy-first is the worst for the L->1 case, but the best for the L/T case, why is that?\n\n2. What is the motivation for \"hard-first\"?\n\n3. The setting of \"least2most\" with L->1 is similar to Ghazvininejad et al. 2019. But Table 4 in the appendix shows the result in this paper is still worse (21.98 vs. 24.61, when both systems use 10 iterations without AR). Also, the gap from the AR baseline is larger than that in Ghazvininejad et al. 2019. Given the two systems are considered similar, it should be explained in the paper the possible reasons for these discrepancies in results.\n\nAdditional minor comments for improving the paper:\n\n1. In the introduction, it mentions the baseline AR is (Vaswani et al. 2017), while in the experimental settings, it mentions the baseline AR is (Bahdanau et al. 2015). Please clarify which one is used.\n\n2. In Table 1, how does T = 2L work for the \"Uniform\" case while the target sequence length is only T, since it is mentioned the positions are sampled without replacement. Similarly, how does T = 2L work for the \"Left2Right\" case? Is it just always choosing the last position when L < t <= 2L? In these two cases, it seems T > L is not needed.\n\n3. In Table 3, the header for the 2nd column should be o_t, as defined in Section 4 - \"Decoding scenarios\". What is the actual value of K and K'' for the constant-time machine translation experiments in the paper?\n\n4. \"Rescoring adds minimal overhead as it is run in parallel\" - it still needs to run left-to-right in sequence since it is auto-regressive. Please clarify what it means by \"in parallel\" here.\n\n5. What is the range and average for the target sentence length? How is T = 20 for constant-time decoding compared to linear-time decoding in terms of speed?", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BklHgEkAFB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper presents a general framework for sentence generation using a BERT-like model. The authors decompose the problem of sentence generation into two problems. One is selecting the positions at which changes should be made, and the other is actually replacing the current word with a new word. This framework enables them to represent many decoding strategies including that of Ghazvininejas et al. (2019) in a unified manner, and they propose a new decoding strategy that considers the prediction confidence of the current and the new word. The paper also presents a heuristic algorithm for beam search decoding to find the most likely generation path. Their experimental results on the WMT14 English-German dataset suggest that the proposed approach could achieve translation quality comparable to that of the standard autoregressive approach under a constant-time translation setting.\n\nIt is nice to see existing decoding strategies represented in a generalized framework, but I was a bit disappointed that the authors do not seem to address the most critical problem in using a BERT-like model for sentence generation, namely, how to find the most likely sentence in a probabilistically sound way. It seems to me that the authors rely on at least two approximations. One is using pseudo-likelihood and the other is using the most likely generation path instead of performing marginalization. It is fine that the authors focus on empirical results of translation quality but then I would like to see more strong and extensive evidence that supports the use of such approximation.\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "B1gITGseqB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper focuses on decoding/generation in neural sequence models (specifically machine translation) in a non-autoregressive manner that instead of generating in a left-to-right manner, focuses on generating sequences by picking a length first ,and then indices to replace in a deterministic or random scheme and, finally using a context sensitive distribution over vocabulary (using BERT-like masked LM scheme)  to pick the word to replace. In practice, this procedure of picking indices and words to replace is repeated T number of times and hence the final sequence is obtained by this iterative refinement procedure. This is an interesting and important research direction because not only would it result in better and context sensitive greedy/approximate-MAP decoded outputs, but also opens up opportunities for parallelization of the decoding procedure which is difficult to achieve with left-to-right decoders.\nThat said, the results are fairly inconclusive and the practical implementation does leave things desired for a practical decoder. As observed by the authors, different deterministic strategies for choosing T results in very different performances among the variants of the proposed approach. Besides among the variants, one clear pattern is that uniformly random picking of indices is worse than other schemes (left-to-right, least-to-most, easy-first) which is not unexpected but no conclusive empirical evidence can be found for relative differences between the performances of other 3 schemes. Moreover, the proposed decoding variants generally perform worse than or at best similarly to standard autoregressive baselines. As authors note, this is due to the mismatch between the method in which the model was trained and the decoding procedure which is not surprising, but at the same time this does not give insight into the effectiveness of the proposed decoding objective. The central question is: if the training prefers left-to-right generation then how valuable is it to device  more reasonable but incompatible decoding procedures?\n\nAlso, authors also note that index picking schemes investigated in the paper are heuristic based and a more interesting decoder could be learned if index selection procedure itself was learned with features depending on the previous index selection states, decoded states Y, and other relevant quantities. They attribute poor performance of the proposed decoder to the nature of index selection approaches investigated in the paper. I think the paper would be strengthened with results with a more sophisticated learned index selection procedure in addition to the heuristics investigated in this paper.\n\nOverall, while the idea and motivation behind this work is exciting, the inconclusive results and the approaches for practical implementation leave open significant room for improvement. ", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a generalized way to generate sequences from undirected sequence models.

Overall, I believe a framework like this could definitely be a valuable contribution, but as Reviewer 1 and Reviewer 3 noted, the paper is a bit lacking both in theoretical analysis and strong empirical results. I don't think that this is a bad paper at all, but it feels like the paper needs a little bit of an extra push to tighten up the argumentation and/or results before warranting publication at a premier venue such as ICLR. I'd suggest the authors continue to improve the paper and aim to re-submit at revised version at a future conference. 
Decision: Reject