Fast Interleaved Bidirectional Sequence Generation (2020)

Abstract: Independence assumptions during sequence generation can speed up inference, but parallel generation of highly inter-dependent tokens comes at a cost in quality. Instead of assuming independence between neighbouring tokens (semi-autoregressive decoding, SA), we take inspiration from bidirectional sequence generation and introduce a decoder that generates target words from the left-to-right and right-to-left directions simultaneously. We show that we can easily convert a standard architecture for unidirectional decoding into a bidirectional decoder by simply interleaving the two directions and adapting the word positions and selfattention masks. Our interleaved bidirectional decoder (IBDecoder) retains the model simplicity and training efficiency of the standard Transformer, and on five machine translation tasks and two document summarization tasks, achieves a decoding speedup of ~2x compared to autoregressive decoding with comparable quality. Notably, it outperforms left-to-right SA because the independence assumptions in IBDecoder are more felicitous. To achieve even higher speedups, we explore hybrid models where we either simultaneously predict multiple neighbouring tokens per direction, or perform multi-directional decoding by partitioning the target sequence. These methods achieve speedups to 4x–11x across different tasks at the cost of <1 BLEU or <0.5 ROUGE (on average)

## introduction neural sequence generation aided by encoderdecoder models @xcite has achieved great success in recent years @xcite @xcite , but still suffers from slow inference. one crucial bottleneck lies in its generative paradigm which factorizes the conditional probability along the target sequence @xmath0, y 2 , . . . , y n } of length n as follows: a promising direction to break this barrier is to generate multiple target words at one decoding step to improve the parallelization of inference @xcite . however, this introduces independence assumptions that hurt translation quality, since words produced in parallel are in fact likely to be inter-dependent. we hypothesize that there are groups of words that are less likely to be strongly inter-dependent than neighbouring words, which will allow for better parallelization. inspired by bidirectional modeling @xcite , we resort to an alternative probabilistic factorization: introducing an independence assumption between t and @xmath1. based on this factorization, @xcite propose synchronous bidirectional translation using a dedicated interactive decoder, and report quality improvements compared to left-toright semi-autoregressive decoding @xcite in translation quality. however, their success comes along with extra computational overhead brought by the specialized decoder. empirically, @xcite only report a decoding we combine the strengths of bidirectional modeling and sa, and propose interleaved bidirectional decoder (ibdecoder) for fast generation. as shown in figure 1a , we interleave target words from the left-to-right and right-to-left directions and separate their positions to support reusing any standard unidirectional decoders, such as the transformer decoder @xcite . we reorganize the self-attention mask to enable inter-and intra-direction interaction (figure 1c ) following sa. unlike sa, we show through experiments that distant tokens from different directions are less inter-dependent, providing a guarantee for better performance. compared to previous studies @xcite @xcite , our approach has no extra model parameters and brings in little overhead at training and decoding. ibdecoder is speedup-bounded at 2×. to push this ceiling up, we explore strategies for multiword simultaneous generation, including multidirectional decoding (imdecoder, figure 1d ) and sa (figure 1b ). the former extends eq. 2 by inserting more generation directions, while the latter allows each direction to produce multiple target words @xcite . these strategies offer us a chance to aggressively improve the decoding speed albeit at the risk of degenerated performance. to encourage multi-word generation in parallel, we propose a modified beam search algorithm. we extensively experiment on five machine translation tasks and two document summarization tasks, with an in-depth analysis studying the impact of batch size, beam size and sequence length on the decoding speed. we close our analysis by examining the capacity of our model in handling long-range dependencies. on these tasks, ibdecoder yields ∼2× speedup against transformer at inference, and reaches 4×-11× after pairing it with sa. still, the overall generation quality is comparable. when we pair our method with sequence-level knowledge distillation @xcite , we outperform a transformer baseline on 6 out of 7 tasks. our contributions are summarized below: ## related work efforts on fast sequence generation come along with the rapid development of encoder-decoder models @xcite . a straightforward way is to reduce the amount of computation. methods in this category range from teacherstudent model @xcite , constrained softmax prediction @xcite , beam search cube pruning @xcite , float-point quantization @xcite , model pruning @xcite , to simplified decoder architectures, such as lightweight recurrent models @xcite @xcite , average attention network @xcite , merged attention network @xcite , dynamic convolution @xcite , and hybrid attentions @xcite , .etc. nonetheless, the above methods still suffer from the inference bottleneck caused by the sequential nature of autoregressive models. instead, @xcite propose non-autoregressive generation where target words are predicted independently, leading to great speedup, albeit at a high cost to generation quality. follow-up studies often seek solutions to recover the performance @xcite @xcite @xcite , but also reveal the trade-off between the quality and speed in terms of autoregressiveness. this motivates researchers to discover the optimal balance by resorting to semi-autoregressive modeling @xcite , iterative refinement @xcite @xcite or in-between @xcite . we hypothesize that generation order affects the felicity of independence assumptions made in semiautoregressive modelling. unlike generation with flexible orders @xcite @xcite , we employ deterministic generation order for model simplicity and training efficiency, specifically focusing on bidirectional decoding. the study of bidirectional modeling dates back to the era of phase-based statistical machine translation @xcite and recently gained popularity in neural machine translation @xcite @xcite . unfortunately, these methods either design complex neural decoders, which hurts training efficiency, and/or perform the left-to-right and right-to-left inference separately followed by rescoring, which slows down decoding. by contrast, our model speeds up inference while maintaining training speed. our work is closely related to sa @xcite and synchronous bidirectional generation @xcite . ibdecoder extends sa to incorporate information from different directions. in contrast to @xcite , we only make minimal changes to the standard transformer decoder, which benefits efficiency during training and inference, and makes our method easy to implement. we also find improvements in both decoding speed and translation quality compared to @xcite . ## autoregressive transformer transformer @xcite , the state-of-theart neural sequence generation model, follows the autoregressive factorization as in eq. 1. to handle the dependency of target word y t on previous target words @xmath2, transformer relies on a masked selfattention network in the decoder: the mask matrix @xmath3. formally, given the target sequence length n, this matrix can be constructed by the following masking function: the input layer to transformer's decoder is the addition of target word embedding e y and word position encoding pe t , i.e y 0 = e y + pe @xmath4. t maps y to its word position sequence, which is a simple indexing function (figure 1b ): ## interleaved bidirectional decoder the structure of transformer is highly parallelizable, but the autoregressive schema (@xmath5, @xmath6. we alleviate this barrier by exploring the alternative probabilistic factorization in eq. 2 to allow words predicted from different directions simultaneously. we propose ibdecoder as shown in figure 1a . we reuse the standard decoder's architecture in a bid to largely inherit transformer's parallelization and avoid extra computation or parameters, rather than devising dedicated decoder architectures @xcite . to make the left-to-right and right-to-left generation collaborative, we reorganize the target sequence and the word positions below (purple and green rectangles in figure 1a ): by following the generation order defined by eq. 2, the sequence y bd interleaves y 1: n /2 and y n /2 +1:n and converts a bidirectional generation problem to a unidirectional one. we introduce negative positions to t bd to retain the locality bias of sinusoidal positional encodings in y bd . 2 compared to (y, t ), the reorganized sequences (y bd , t bd ) have the same length, thus with no extra overhead. we also adapt the self-attention mask to permit step-wise bidirectional generation: ## experiments setup we test our model on machine translation (mt) and document summarization. we train mt models on five different language pairs: wmt14 english-german (en-de, @xcite , wmt14 english-french (en-fr, @xcite , wmt16 romanian-english (ro-en, bojar et al., 2016), wmt18 english-russian (en-ru, @xcite and wat17 small-nmt english-japanese (en-ja, @xcite . translation quality is measured by bleu @xcite , and we report detokenized bleu using the toolkit sacrebleu @xcite foot_3 except for en-ja. following @xcite , we segment japanese text with kytea foot_4 and compute tokenized bleu. we train document summarization models on two benchmark datasets: the non-anonymized version of the cnn/daily mail dataset @xcite and the annotated english gigaword (gigaword, @xcite . we evaluate the summarization quality using rouge-l @xcite . we provide details of data preprocessing and model settings in appendix a. we perform thorough analysis of our model on wmt14 en-de. we also report results improved by knowledge distillation (kd, @xcite . . bleu: detokenized bleu for models trained from scratch, +kd: detokenized bleu for models trained with knowledge distillation. latency (in millisecond) and speedup are evaluated by decoding the test set with a batch size of 1, averaged over three runs. we report the latency and speedup for 2 , 3 and 4 trained with kd. train compares the training speed averaged over 100 steps. time is measured on geforce gtx 1080. ## conclusion and future work we present interleaved bidirectional sequence generation to accelerate decoding by enabling generation from the left-to-right and right-to-left directions simultaneously. we combine the strengths of sbsg @xcite and sa @xcite , and propose a simple interleaved bidirectional decoder (ibdecoder) that can be easily implemented on top of a standard unidirectional decoder, like transformer, via interleaving the target sequence and tweaking the word positions and selfattention masks. ibdecoder inherits transformer's training parallelization with no additional model parameters, and is extensible with sa and multidirectional decoding. we show that the independence assumptions we introduce between the two directions are less harmful to translation quality than the independence assumptions in left-to-right sa. on a series of generation tasks, we report comparable quality with significant inference speedup (4×-11×) and little training overhead. we also show that the approach is orthogonal to speedups to autoregressive decoding, e.g. by reducing model size. in the future, we would like to further improve multi-directional generation, and will investigate alternative ways to partition the target sequence and encode positional information. we are also in-terested in better measuring and reducing the quality loss resulting from long-distance dependencies. finally, we would like to adapt our interleaving approach to other sequence-to-sequence architectures.