Title: A GENERALIZED FRAMEWORK OF SEQUENCE GEN-ERATION WITH APPLICATION TO UNDIRECTED SE-QUENCE MODELS

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.

1. INTRODUCTION:

Undirected neural sequence models such as BERT (Devlin et al., 2019) have recently brought significant improvements to a variety of discriminative language modeling tasks such as questionanswering 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, a 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 us 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 as monotonic autoregressive, non-autoregressive by iterative refinement and monotonic semiautoregressive decoding as special cases of the proposed model. This separation of coordinate selection and symbol replacement allows us to build a diverse set of decoding algorithms agnostic to the parameterization or training procedure of the underlying model. We thus fix the symbol replacement distribution as a variant of BERT and focus on deriving novel generation procedures for undirected neural sequence models under the proposed framework. We design a coordinate selection distribution using a 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 on machine translation using a translation-variant 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-German. Our experiments show that generation from undirected sequence models, under our framework, is competitive with the state of the art, and that adaptive-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 a 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 a 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 a generation sequence G of pairs of an intermediate sequence Y t = (y t 1 , . . . , y t L ) and the corresponding coordinate sequence Z t = (z t 1 , . . . , z t L ), where y t i ∈ V , V is a vocabulary, L is a length of a sequence, T is a number of generation steps, and z t i ∈ {0, 1}. The coordinate sequence indicates which of the current intermediate sequence are to be replaced. That is, each consecutive pairs are related to each other by

y t+1 i = (1 -z t+1 i )y t i + z t+1 i ỹt+1 i

, where ỹt+1 i ∈ V is a new symbol for the position i. This sequence of pairs G describes a procedure in which a final sequence Y T is created, starting from an empty sequence Y 1 = ( mask , . . . , mask ) and empty coordinate sequence Z 1 = (0, ..., 0). This procedure of sequence generation is probabilistically modelled as

EQUATION

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 = ∅.

We first predict the length L of a target sequence Y according to p(L|X) distribution to which we refer as (c) length prediction. At each generation step t, we first select the next coordinates Z t+1 for which the corresponding symbols will be replaced according to p(z t+1 i |Y ≤t , Z t , 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 t+1 i |Y ≤t , Z t+1 , X), leading to the next intermediate sequence Y t+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 T . In the remainder of this section, we describe several special cases of the proposed framework, which are monotonic autoregressive, non-autoregressive, semi-autoregressive 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 a time, monotonically moving from the left-most position to the right-most. In this case, we define the coordinate selection distribution of the generalized sequence generation model in Eq. (1) (a) as p(z t+1 i+1 = 1|Y ≤t , Z t , X) = 1(z t i = 1), where 1(•) is an indicator function and z 1 1 = 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 intermediate sequences. We then choose the symbol replacement distribution in Eq. (1) (b) to be p(y t+1 i+1 |Y ≤t , X) = p(y t+1 i+1 |y t 1 , y t 2 , . . . , y t i , X), for z t+1 i+1 = 1. Intuitively, we limit the dependency of y t+1 i+1 only to the symbols to its left in the previous intermediate sequence y t <(i+1) and the input variable X. The length distribution (1) (c) is implicitly defined by considering how often the special token eos , which indicates the end of a sequence, appears after L generation steps: p(L|X) ∝ y 1:L-1 L-1 l=1 p(y l+1 l+1 = eos |y ≤l ≤l , X). With these choices, the proposed generalized model reduces to p(G|X) = L i=1 p(y i |y <i , X) which is a widely-used 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 generation step (Lee et al., 2018) . We design the coordinate selection distribution to be p(z t+1 i = 1|Y ≤t , Z t , X) = 1 ∀i ∈ {1, ..., L}, implying that we replace the symbols in all the positions. 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 t+1 i is conditioned on the entire current sequence Y t and the input variable X. We do not need to assume any relationship between the number of generation steps T and the length of a sequence L in this case. The length prediction distribution p(L|X) is estimated from training data.

Semi-autoregressive neural sequence models Wang et al. (2018) recently proposed a compromise between autoregressive and non-autoregresive sequence models by predicting a chunk of symbols in parallel at a 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

p(z t+1 k(i+1)+j = 1|Y ≤t , Z t , X) = 1, if z t ki+j = 1, ∀j ∈ {0, 1, . . . , k} 0, otherwise,

where k is a group size. Similarly we modify the symbol replacement distribution:

p(y t+1 k(i+1)+j |Y ≤t , X) = p(y t+1 k(i+1)+j |y t <k(i+1) , X), ∀j ∈ {0, 1, . . . , k} ,

for z t i = 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 use this connection to design a set of approximate, deterministic decoding algorithms for undirected sequence models.

3.1. BERT AS AN UNDIRECTED SEQUENCE MODEL:

BERT (Devlin et al., 2019) is a masked language model: It is trained to predict a 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 a special mask symbol and the model is trained to predict p(y i |y <i , mask , y >i , X). We refer to this as the conditional BERT distribution. This objective was interpreted as a stochastic approximation to the pseudo log-likelihood objective (Besag, 1977) by Wang and Cho (2019) . This approach of fullcontext 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 et al., 2019) has demonstrated that undirected neural sequence models like BERT can learn complex sequence distributions and generate wellformed sequences. In such models, it 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 a ground-truth sequence. Finding a good sequence in a deterministic manner is also nontrivial.

A number of papers have explored using pretrained language models like BERT to initialize sequence generation models. Ramachandran et al. (2017) , Song et al. (2019) , and Lample and Conneau (2019) use a pretrained undirected language model to initialize a conventional monotonic autoregressive sequence model, while Edunov et al. (2019) use a BERT-like model to initialize the lower layers of a generator, without finetuning. Our work differs from these in that we attempt to directly generate from the pretrained model, rather than using it as a starting point to learn another model.

3.2. GIBBS SAMPLING IN 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|X) is estimated from training data, as is the case in the non-autoregressive neural sequence model. In Gibbs sampling, we often uniformly select a new coordinate at random, which corresponds to p(z

t+1 i = 1|Y ≤t , Z t , X) = 1/L with the constraint that L i=1 z t i = 1

. By using the conditional BERT distribution as a 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 a log-linear model with features φ i based on the intermediate and coordinate sequences:

EQUATION

again with the constraint that L i=1 z t i = 1. τ > 0 is a temperature parameter controlling the 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) . We investigate three features φ i : (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:

φ negent (Y t , Z t , X, i) = -H(y t+1 i |y t <i , mask , y t >i , X).

In other words, we prefer a position i if we know the change in i has a high potential to alter the joint probability p(Y |X) = p(y 1 , y 2 , ..., y L |X).

(2) For each position i we measure how unlikely the current symbol (y t i , not

y t+1 i ) is under the new conditional distribution: φ logp (Y t , Z t , X, i) = -log p(y i = y t i |y t <i , mask , y t >i , X)

. Intuitively, we prefer to replace a 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: φ pos (i) = -log(|t -i| + ), where > 0 is a small constant scalar to prevent log 0. This feature encodes our preference to generate from left to right if there is no information about the input variable nor of any intermediate sequences.

Unlike the special cases of 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 α negent , α logp and α pos , which are selected or estimated to maximize a target quality measure on 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 in Eq. ( 2), we can now design an inference procedure to approximately find the most likely sequence from the sequence distribution p(Y |X) by exploiting the corresponding model of sequence generation. In doing so, a naive approach is to marginalize out the generation procedure G using a Monte Carlo method:

argmax Y p(Y |X) = argmax Y T 1 M G m p(Y T |Y m,<T , Z m,≤T , X)

, where G m is the mth sample from the sequence generation model. This approach suffers from a high variance and non-deterministic behavior, and is less appropriate for practical use. We instead propose an optimistic decoding approach following equation (1):

argmax L,Y 1 ,...,Y T Z 1 ,...,Z T log p(L|X) + T t=1 L i=1 log p(z t+1 i |Y ≤t , Z t , X) + z t+1 i log p(y t+1 i |Y ≤t , X). (3)

The proposed procedure is optimistic in that we consider a 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 a deterministic approximation scheme such as greedy and beam search, although it is as intractable to solve this problem as the original problem which required marginalization of the generation path. 

H t-1 = h t-1 k = (( Ŷ 1 k , . . . , Ŷ t-1 k ), ( Ẑ1 k , . . . , Ẑt-1 k )) K k=1

. Each generation hypothesis has a score:

s(h t-1 k ) = log p(L|X) + t-1 t =1 L i=1 log p(ẑ t i | Ŷ <t k , Ẑt -1 , X) + ẑt i log p(ŷ t i | Ŷ ≤t , X).

For notational simplicity, we drop the time superscript t. Each of the K generation hypotheses is first expanded with K candidate positions according to the coordinate selection distribution:

ĥk,k K k =1 = arg top-K u∈{1,...,L} s(h k ) + log p(z k,u = 1| Ŷ <t , Ẑt-1 , X) =s(h k one-hot(u))

so that we have K × K candidates ĥk,k , where each candidate consists of a hypothesis h k with the position sequence extended by the selected position u k,k and has a score s(h k one-hot(u k,k )). 1We then expand each candidate with the symbol replacement distribution:

ĥk,k ,k K k =1 = arg top-K v∈V s(h k one-hot(u k,k )) + log p(y z k,k = v| Ŷ ≤t , X) =s(h k,k ( Ŷ t-1 <z k,k ,v, Ŷ t-1 >z k,k

))

.

This results in K × K × K candidates ĥk,k ,k , each consisting of hypothesis h k with intermediate and coordinate sequence respectively extended by v k,k ,k and u k,k . Each hypothesis has a score

s(h k,k ( Ŷ t-1 <z k,k , v k,k ,k , Ŷ t-1 >z k,k )), 2 which we use to select K candidates to form a new hypothesis set H t = arg top-K h∈ ĥk,k ,k k,k ,k s(h).

After iterating for a predefined number T of steps, the algorithm terminates with the final set of K generation hypotheses. We then choose one of them according to a prespecified criterion, such as Eq. ( 3), and return the final symbol sequence Ŷ T .

4. EXPERIMENTAL SETTINGS:

Data and preprocessing We evaluate our framework on WMT'14 English-German translation. The dataset consists of 4.5M parallel sentence pairs. We preprocess this dataset by tokenizing each sentence using a script from Moses (Koehn et al., 2007) and then segmenting each word into subword units using byte pair encoding (Sennrich et al., 2016) with a joint vocabulary of 60k tokens. We use newstest-2013 and newstest-2014 as validation and test sets respectively.

Sequence models We base our models off those of Lample and Conneau (2019) . Specifically, we use a Transformer (Vaswani et al., 2017) with 1024 hidden units, 6 layers, 8 heads, and Gaussian error linear units (Hendrycks and Gimpel, 2016) . We use a pretrained model3 trained using a masked language modeling objective (Lample and Conneau, 2019) on 5M monolingual sentences from WMT NewsCrawl 2007 -2008. To distinguish between English and German sentences, a special language embedding is 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 or 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-decoder 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 , β 1 = 0.9, β 2 = 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 log-linear coordinate selection distribution in §2:

1. Uniform: τ → ∞, i.e., sample a position uniformly at random without replacement 2. Left2Right: α negent = 0, α logp = 0, α pos = 1 3. Least2Most (Ghazvininejad et al., 2019) : We use beam search described in §3.3 with K fixed to 1, i.e., we consider only one possible position for replacing a 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-probability of the final sequence (Wang and Cho, 2019) . Additionally, we experimented with choosing best translation according to log-probability of the final sequence calculated by an autoregressive neural sequence model.

α negent = 0, α logp = 1, α pos = 0 4. Easy-First: α negent = 1, α logp = 1, 4 α pos = 0 # of length

Decoding scenarios:

We consider two decoding scenarios: 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 = O(1). At the t-th iteration of generation, we replace o t -many symbols, where o t is either a constant L/T or linearly anneals from L to 1 (L → 1) as done by Ghazvininejad et al. (2019) .

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 L iterations on the development set.

5. LINEAR-TIME DECODING: RESULT AND ANALYSIS:

Main findings We present translation quality measured by BLEU (Papineni et al., 2002) in Table 1 .

We identify a number of important trends. ( 1 (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 1 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 a 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 is trained to follow all possible generation orders and to use context from both directions, which is not available when generating left-to-right at 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 to 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→De. We explain these two behaviors by the availability of contextual evidence, or lack thereof. At the beginning of generation, the only two non-mask symbols are the beginning and end of sentence symbols, making it easier to predict a 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. This process manifests either as monotonic or outside-in generation. We present sample sequences generated using these strategies in Appendix D.

6. 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 a 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-first strategy works on par with least2most, which again confirms that decoding strategies must be selected based on the target tasks and decoding setting.

With a 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 to beam-search translations using the strong neural autoregressive model (30.13 vs 30.92). Even with a 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-time machine translation approaches, our model outperforms many recent approaches by Gu et al. (2018) ; Lee et al. (2018) ; Wang et 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 a 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-art autoregressive models, given an appropriate choice of decoding strategy. We further show that constant-time translation in 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 are generated either monotonically or 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 so would likely result in better quality sequences as well as the discovery of more non-trivial generation orders. Second, we only apply our framework to sequence generation, but we could also apply it to 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 a variety of settings. 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 generation (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 is often not decided in advance, the intermediate coordinate sequence Z t and the coordinate selection distribution are reparameterized to work with relative coordinates rather than absolute coordinates. We do not go into details of these recent algorithms, but we emphasize that all these approaches are special cases of the proposed framework, which further suggests other variants of non-monotonic generation.

C ENERGY EVOLUTION OVER GENERATION STEPS:

While the results in Table 1 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 to the average energy of intermediate sentences generated by picking positions uniformly at random. We plot this energy difference over decoding in Figure 2 . We additionally plot the evolution of energy of the sequence by different position selection algorithms throughout generation process in Figure 3 . Overall, we find that left-to-right, least-to-most, and easy-first do find sentences that are lower energy than the uniform baseline over the entire decoding process. Easy-first produces sentences with the lowest energy, followed by least-to-most, 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, T = L in Figures 4, 5 

:

h k one-hot(u k,k ) appends one-hot(u k,k ) at the end of the sequence of the coordinate sequences in h k

h k,k ( Ŷ t-1 <z k,k , v k,k ,k , Ŷ t-1 >z k,k) denotes creating a new sequence from Ŷ t-1 by replacing the z k,k -th symbol with v k,k ,k , and appending this sequence to the intermediate sequences in h k,k .

https://dl.fbaipublicfiles.com/XLM/mlm_ende_1024.pth

We set αlogp = 0.9 for De→En based on the validation set performance.

Figures and Tables:

) 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 handcrafted 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 1 BLEU over greedy search, confirming the utility of the proposed framework as a 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.

Figure 2: Average difference in energy ↑ between sequences generated by selecting positions uniformly at random versus by different algorithms, over the course of decoding.

Figure 3: Evolution of the energy of the sequence ↓ over the course of decoding by different position selection algorithms.

Results (BLEU↑) on WMT'14 En↔De translation using various decoding algorithms and different settings of beam search width (b) and number of iterations (T ) as a function of sentence length (L). For each sentence we use 4 most likely sentence lengths. * denotes rescoring generated hypotheses using autoregressive model instead of proposed model.Length-conditioned beam searchTo solve this intractable optimization problem, we design a heuristic algorithm, called length-conditioned beam search. Intuitively, given a length L, this algorithm performs beam search over the coordinate and intermediate token sequences. At each step t of this iterative algorithm, we start from the hypothesis set H t-1 that contains K generation hypotheses:

Table content: <table><tr><td/><td/><td/><td>Baseline</td><td colspan="4">Decoding from an undirected sequence model</td></tr><tr><td/><td>b</td><td>T</td><td colspan="5">Autoregressive Uniform Left2Right Least2Most Easy-First</td></tr><tr><td>En→De</td><td colspan="2">1 4 4 L* L L 1 2L</td><td>25.33 26.84 --</td><td>21.01 22.16 22.74 21.16</td><td>24.27 25.15 25.66 24.45</td><td>23.08 23.81 24.42 23.32</td><td>23.73 24.13 24.69 23.87</td></tr><tr><td/><td colspan="2">4 2L</td><td>-</td><td>21.99</td><td>25.14</td><td>23.81</td><td>24.14</td></tr><tr><td>De→En</td><td colspan="2">1 4 4 L* L L 1 2L</td><td>29.83 30.92 --</td><td>26.01 27.07 28.07 26.24</td><td>28.34 29.52 30.46 28.64</td><td>28.85 29.03 29.84 28.60</td><td>29.00 29.41 30.32 29.12</td></tr><tr><td/><td colspan="2">4 2L</td><td>-</td><td>26.98</td><td>29.50</td><td>29.02</td><td>29.41</td></tr></table>

Constant-time machine translation on WMT'14 De→En with different settings of the budget (T ) and number of tokens predicted each iteration (o t ). * denotes rescoring generated hypotheses using autoregressive model instead of proposed model.

Table content: <table><tr><td>T</td><td>ot</td><td colspan="5">Uniform Left2Right Least2Most Easy-First Hard-First</td></tr><tr><td>10</td><td>L → 1</td><td>22.38</td><td>22.38</td><td>27.14</td><td>22.21</td><td>26.66</td></tr><tr><td colspan="2">10 L → 1*</td><td>23.64</td><td>23.64</td><td>28.63</td><td>23.79</td><td>28.46</td></tr><tr><td>10</td><td>L/T</td><td>22.43</td><td>21.92</td><td>24.69</td><td>25.16</td><td>23.46</td></tr><tr><td>20</td><td>L → 1</td><td>26.01</td><td>26.01</td><td>28.54</td><td>22.24</td><td>28.32</td></tr><tr><td colspan="2">20 L → 1*</td><td>27.28</td><td>27.28</td><td>30.13</td><td>24.55</td><td>29.82</td></tr><tr><td>20</td><td>L/T</td><td>24.69</td><td>25.94</td><td>27.01</td><td>27.49</td><td>25.56</td></tr></table>

BLEU scores on WMT'14 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.

Table content: <table><tr><td>WMT2014</td></tr></table>

Peer review (iclr2020):
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. Overall the paper has significant contributions in the following aspects: 1. It enables undirected sequence models, like BERT, to perform decoding or sequence generation directly, instead of just serving as model pre-training. 2. The proposed framework unifies directed and undirected sequence models decoding, and it can represent a few existing sequence model decoding as special cases. 3. 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. 4. The analysis of the coordinate selection order is interesting and helpful for understanding the algorithm. 5. 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. The presentation of the paper is also clear. I am leaning towards accepting the paper. However, there are some weaknesses: 1. 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? 2. What is the motivation for *hard-first*? 3. 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. Additional minor comments for improving the paper: 1. 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. 2. 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. 3. 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? 4. *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. 5. 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?