Abstract: We propose the Insertion-Deletion Transformer, a novel transformer-based neural architecture and training method for sequence generation. The model consists of two phases that are executed iteratively, 1) an insertion phase and 2) a deletion phase. The insertion phase parameterizes a distribution of insertions on the current output hypothesis, while the deletion phase parameterizes a distribution of deletions over the current output hypothesis. The training method is a principled and simple algorithm, where the deletion model obtains its signal directly on-policy from the insertion model output. We demonstrate the effectiveness of our Insertion-Deletion Transformer on synthetic translation tasks, obtaining significant BLEU score improvement over an insertion-only model.

Introduction: Neural sequence models BIBREF0, BIBREF1 typically generate outputs in an autoregressive left-to-right manner. These models have been successfully applied to a range of task, for example machine translation BIBREF2. They often rely on an encoder that processes the source sequence, and a decoder that generates the output sequence conditioned on the output of the encoder. The decoder will typically generate the target sequence one token at a time, in an autoregressive left-to-right fashion. Recently, research in insertion-based non- or partially- autoregressive models has spiked BIBREF3, BIBREF4, BIBREF5, BIBREF6. These model are more flexible than their autoregressive counterparts. They can generate sequences in any order, and can benefit from parallel token generation. They can learn complex orderings (e.g., tree orderings) and may be more applicable to task like cloze question answering BIBREF6 and text simplification, where the order of generation is not naturally left to right, and the source sequence might not be fully observed. One recently proposed approach is the Insertion Transformer BIBREF3, where the target sequence is modelled with insertion-edits. As opposed to traditional sequence-to-sequence models, the Insertion Transformer can generate sequences in any arbitrary order, where left-to-right is a special case. Additionally, during inference, the model is endowed with parallel token generation capabilities. The Insertion Transformer can be trained to follow a soft balanced binary tree order, thus allowing the model to generate $n$ tokens in $O(\log _2 n)$ iterations. In this work we propose to generalize this insertion-based framework, we present a framework which emits both insertions and deletions. Our Insertion-Deletion Transformer consists of an insertion phase and a deletion phase that are executed iteratively. The insertion phase follows the typical insertion-based framework BIBREF3. However, in the deletion phase, we teach the model to do deletions with on-policy training. We sample an input sequence on-policy from the insertion model (with on-policy insertion errors), and teach the deletion model its appropriate deletions. This insertion-deletion framework allows for flexible sequence generation, parallel token generation and text editing. In a conventional insertion-based model, if the model makes a mistake during generation, this cannot be undone. Introducing the deletion phase makes it possible to undo the mistakes made by the insertion model, since it is trained on the on-policy errors of the insertion phase. The deletion model extension also enables the framework to efficiently handle tasks like text simplification and style transfer by starting the decoding process from the original source sequence. A concurrent work was recently proposed, called the Levenshtein Transformer (LevT) BIBREF7. The LevT framework also generates sequences with insertion and deletion operations. Our approach has some important distinctions and can be seen as a simplified version, for both the architecture and the training algorithm. The training algorithm used in the LevT framework uses an expert policy. This expert policy requires dynamic programming to minimize Levenshtein distance between the current input and the target. This approach was also explored by BIBREF8, BIBREF9. Their learning algorithm arguably adds more complexity than needed over the simple on-policy method we propose. The LevT framework consists of three stages, first the number of tokens to be inserted is predicted, then the actual tokens are predicted, and finally the deletion actions are emitted. The extra classifier to predict the number of tokens needed to be inserted adds an additional Transformer pass to each generation step. In practice, it is also unclear whether the LevT exhibits speedups over an insertion-based model following a balanced binary tree order. In contrast, our Insertion-Deletion framework only has one insertion phase and one deletion phase, without the need to predict the number of tokens needed to be inserted. This greatly simplifies the model architecture, training procedure and inference runtime. An alternative approach for text editing is proposed by BIBREF10, which they dub Deliberation Networks. This work also acknowledges the potential benefits from post-editing output sequences and proposes a two-phase decoding framework to facilitate this. In this paper, we present the insertion-deletion framework as a proof of concept by applying it to two synthetic character-based translation tasks and showing it can significantly increase the BLEU score over the insertion-only framework.

Question: How much is BELU score difference between proposed approach and insertion-only method?
Answer: Learning shifted alphabetic sequences: 21.34
Caesar's Cipher: 2.02