PermuteFormer: Efficient Relative Position Encoding for Long Sequences

Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pages 10606–10618 November 7–11, 2021. c⃝2021 Association for Computational Linguistics 10606 PermuteFormer: Efficient Relative Position Encoding for Long Sequences Peng Chen Peking University chen.peng@pku.edu.cn Abstract A recent variation of Transformer, Performer, scales Transformer to longer sequences with a linear attention mechanism. However, it is not compatible with relative position encoding, which has advantages over absolute position encoding. In this paper, we discuss possible ways to add relative position encoding to Per- former. Based on the analysis, we propose Per- muteFormer, a Performer-based model with relative position encoding that scales linearly on long sequences. PermuteFormer applies position-dependent transformation on queries and keys to encode positional information into the attention module. This transformation is carefully crafted so that the final output of self- attention is not affected by absolute positions of tokens. PermuteFormer introduces negligi- ble computational overhead by design that it runs as fast as Performer. We evaluate Per- muteFormer on Long-Range Arena, a dataset for long sequences, as well as WikiText-103, a language modeling dataset. The experi- ments show that PermuteFormer uniformly im- proves the performance of Performer with al- most no computational overhead and outper- forms vanilla Transformer on most of the tasks. 1 1 Introduction The Transformer architecture (Vaswani et al., 2017) has achieved state-of-the-art on various fields of research, including natural language processing (Devlin et al., 2019; Raffel et al., 2020), speech processing (Baevski et al., 2020) and image pro- cessing (Dosovitskiy et al., 2020; Tan and Bansal, 2019). But Transformer does not scale well to long sequences, because the time complexity and mem- ory complexity of the attention module in Trans- former are both quadratic to the sequence length. Recently, several efficient Transformers (Kitaev 1Code is available at https://github.com/ cpcp1998/PermuteFormer. et al., 2020; Wang et al., 2020; Zaheer et al., 2020; Xiong et al., 2021) have been proposed to speed up the model from quadratic complexity to linear complexity without significant performance loss. Generally, they utilize efficient algorithms to ap- proximate attention. §2 briefly introduces these efficient Transformers and a more thorough review can be found in Tay et al. (2020c). Among these efficient Transformers, it is sug- gested that Performer (Choromanski et al., 2020) is the fastest one (Tay et al., 2020b). In this paper, we denote as Performer the family of efficient Trans- formers similar to Choromanski et al. (2020), e.g., Katharopoulos et al. (2020); Peng et al. (2021); Ka- sai et al. (2021); Likhosherstov et al. (2020), not only Choromanski et al. (2020) itself. Performer utilizes kernel method to avoid explicit calculation of attention weights. It applies a non-linear fea- ture map to queries and keys to get query features and key features respectively and then multiplies query features, key features, and values together directly, without applying softmax. With the ap- propriate ordering of matrix multiplications, Per- former achieves complexity linear of the sequence length. Moreover, some implementation of uni- directional Performer (Likhosherstov et al., 2020) even reduces memory footprint to …

Content truncated to 500 words