Towards More Efficient Insertion Transformer with Fractional Positional Encoding (2023)

Abstract: Auto-regressive neural sequence models have been shown to be effective across text generation tasks. However, their left-to-right decoding order prevents generation from being parallelized. Insertion Transformer (Stern et al., 2019) is an attractive alternative that allows outputting multiple tokens in a single generation step. Nevertheless, due to the incompatibility between absolute positional encoding and insertion-based generation schemes, it needs to refresh the encoding of every token in the generated partial hypothesis at each step, which could be costly. We design a novel reusable positional encoding scheme for Insertion Transformers called Fractional Positional Encoding (FPE), which allows reusing representations calculated in previous steps. Empirical studies on various text generation tasks demonstrate the effectiveness of FPE, which leads to floating-point operation reduction and latency improvements on batched decoding.

## introduction transformer-based models @xcite have been successfully applied to various text generation tasks @xcite @xcite @xcite . most of these models utilize a fixed left-to-right auto-regressive generation strategy, where the strict factorization means that the model can only generate one token per step. this makes it difficult to parallelize the decoding process, while parallel generation may help to improve decoding efficiency. recently, insertion-based sequence-generation models @xcite @xcite have been developed as attractive alternatives to the auto-regressive ones by allowing flexible generation order. in particular, the insertion transformer @xcite , which combines the transformer architecture and the insertionbased strategy, can match the performance of an auto-regressive model while requiring many fewer decoding steps with parallel generation. the original insertion transformer utilizes absolute positional encoding as in the vanilla autoregressive transformer. in the vanilla transformer, due to its left-to-right generation scheme, tokens' absolute positions do not change; thus, previous computation can be reused. however, this property no longer holds if insertion is allowed, and the insertion transformer re-encodes all previously generated tokens at each decoding step, which brings additional computational overheads. in this work, we propose a reusable positional encoding scheme called fractional positional encoding (fpe) to accelerate the insertion transformer. this scheme dynamically calculates each token's positional representations according to its left and right neighbors at insertion time. in this way, each token's positional representations will not change during the decoding process so that the computation can be reusable in the same way as the vanilla transformer, leading to a reduction of computation for the insertion transformer. we evaluate fpe with a range of text generation tasks, including machine translation, word reordering, summarization as well as an open-ended text completion task. we show that the proposed scheme can reduce floating point operations of the insertion-based model while maintaining comparable performance to the vanilla transformer. our implementation is available at https:// github.com/zzsfornlp/zgen1/ . ## insertion transformer insertion transformer @xcite generates the target sequences via a series of insertion operations. this provides a flexible scheme that can enable different generation orders as well as parallel generation. we focus on the parallel-generation variant that inserts multiple tokens at each step. while the left-to-right scheme can only append one token at each step, the insertion-based scheme can add multiple tokens at different slots, thus potentially enabling more efficient generation. ## positional encoding figure 1 provides an overview of different positional encoding schemes that we explore. the vanilla left-to-right (l2r) transformer model @xcite adopts a simple absolute positional encoding scheme by assigning left-to-right increasing indexes to each token. this naturally fits the left-to-right generation procedure and allows the previously calculated hidden representations to be reusable. however, in the insertion-based generation, since tokens can be inserted before previously generated tokens, the absolute position of a token may change. therefore, if still using the absolute positional encoding (abs), the previously calculated hidden layers cannot be reused and the insertion transformer needs to re-encode all the existing tokens at each step. this yields computation overhead, which may offset the computation gain from parallelization. to solve this problem, alternative positional encoding schemes are required. relative positional encoding (rel; @xcite is an example, which has been adopted for insertion-based models @xcite . here, each token records its relative positional information at its insertion time. though this scheme alleviates encoding absolute positions and allows reusing, it requires complex modifications in the attention calculations. in this work, we design fractional positional encoding (fpe), which is a simpler alternative scheme that only modifies the input embeddings. we still give each token a positional embedding p, which is dynamically calculated along the gener-ation process. whenever a new token w new is inserted between two existing tokens w left and w right , its positional representations will be calculated with a function f applying to its current left and right neighbors: p @xmath0, p right ). in this way, we will have the "fractional"-styled positions. the positional representations of all the tokens will not change throughout the decoding process, and re-encoding is no longer needed. we specify the fpe representations p to have the same dimension as the model size and add them to the input embeddings as in the vanilla transformer. we further specify two randomly-initialized embeddings p b and p e for the beginning-and endingof sequence tokens, respectively. the function f is modeled by a linear layer foot_0 which takes the concatenation of the two neighbors' positional embeddings and outputs a new vector of the model size. at training time, all these fpe-related parameters are tuned along with other parameters in the model. the linear layer is lightweight compared to the transformer layers, thus introducing negligible cost. ## conclusion in this work, we investigate the re-encoding issue that sometimes hinders the insertion transformer from receiving its computation gain and propose a fractional positional encoding scheme that is naturally compatible with the insertion-based generation scheme to solve this issue. with experiments on various tasks, we show that this simple scheme eliminates the need of re-encoding the previously generated tokens and obtains a promising balance between efficiency and performance.