P ermute F ormer: Efficient Relative Position Encoding for Long Sequences (2021)

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 Performer. Based on the analysis, we propose PermuteFormer, 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 negligible computational overhead by design that it runs as fast as Performer. We evaluate PermuteFormer on Long-Range Arena, a dataset for long sequences, as well as WikiText-103, a language modeling dataset. The experiments show that PermuteFormer uniformly improves the performance of Performer with almost no computational overhead and outperforms vanilla Transformer on most of the tasks.

## introduction the transformer architecture @xcite has achieved state-of-the-art on various fields of research, including natural language processing @xcite , speech processing @xcite and image processing @xcite . but transformer does not scale well to long sequences, because the time complexity and memory complexity of the attention module in transformer are both quadratic to the sequence length. recently, several efficient transformers @xcite @xcite have been proposed to speed up the model from quadratic complexity to linear complexity without significant performance loss. generally, they utilize efficient algorithms to approximate attention. §2 briefly introduces these efficient transformers and a more thorough review can be found in @xcite . among these efficient transformers, it is suggested that performer @xcite is the fastest one @xcite . in this paper, we denote as performer the family of efficient transformers similar to @xcite , e.g., @xcite ; @xcite ; @xcite , not only @xcite itself. performer utilizes kernel method to avoid explicit calculation of attention weights. it applies a non-linear feature 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 appropriate ordering of matrix multiplications, performer achieves complexity linear of the sequence length. moreover, some implementation of unidirectional performer @xcite even reduces memory footprint to constant at both training time and inference time. although performer accelerates attention to linear complexity, the existing relative position encoding @xcite @xcite still has quadratic complexity with respect to the sequence length. so performer cannot benefit from relative position encoding, which has already been a common practice for a bunch of state-of-the-art transformers @xcite @xcite . relative position encoding has several advantages over absolute position encoding. (1) relative position encoding may be applied to sequences with arbitrary lengths, with no limitation imposed by training datasets. (2) relative position encoding is more efficient and effective than absolute position encoding. @xcite besides performer, existing relative position encodings also do not fit with other efficient transformers. some relative position encoding @xcite adds a bias to the attention matrix, and others @xcite add a relative-position-dependent bias to key vectors. both require explicit calculation of dot-products between query vectors and key vectors. this conflicts with the second and third categories of efficient transformers described in section 2 because they reduce the computation complexity by avoiding the explicit calculation of dot-products between query vectors and key vectors. as for the first category of efficient transformers, lsh in @xcite may fail to locate major attention weights in the presence of relative position encoding; @xcite ; @xcite rely on global tokens heavily, whose relative positions to other tokens are not defined. in this paper, we propose a performercompatible relative position encoding that scales linearly on long sequences. performer with this novel relative position encoding is named per-muteformer. permuteformer applies a positionaware transformation on query features and key features to encode positional information. more specifically, we choose a random permutation π : {1, 2, • • • , d} → {1, 2, • • • , d} where d is the dimension of query / key features per attention head, and applies the permutation i times to i-th token's query / key feature. 2 in this way, positional information is encoded into attention weights. we prove that, although the transformation applied to query feature and key feature of a token depends on its absolute position, the effects of absolute position on query features and key features cancel out with each other on calculating dot-product of them. thus, the final attention weights do not depend on the absolute positions, and permuteformer encodes relative position only. permuteformer is as efficient as performer, with negligible computational overhead. permuting of query features and key features can be implemented efficiently, with computational complexity proportional to their size. since the size is far less than the computational complexity of the whole model, the cost of permutation in permuteformer is negligible compared to the overall computational cost of performer. the analysis above is also confirmed by the experiment results. we evaluate permuteformer on long-range arena @xcite for bidirectional case and on wikitext-103 @xcite for unidirectional case. long-range arena is a benchmark designed to evaluate efficient transformers on long sequences. we find that the new relative position encoding improves the performance of per-muteformer significantly on long-range arena. it not only performs better than performer but also out-performs the vanilla transformer, as well as other efficient transformers, e.g., @xcite al. (2020); wang et al. (2020); xiong et al. (2021). wikitext-103 is a language modeling dataset. per-muteformer reduces the performance gap between performer and transformer on wikitext-103. it also speeds up the convergence of the model. ## methods we propose an efficient relative position encoding that is compatible with performer architecture. performer with this new relative position encoding is named as permuteformer, because it permutes elements of query feature and key feature to encode positional information. the difference among vanilla transformer, performer and permuteformer is illustrated in figure 1 . in this section, we first introduce transformer and performer briefly, and then describe details of permuteformer. for brevity and clarity, discussions in this section focus on a single head in multi-head attention. they can be directly applied to the whole multi-head attention. ## experiments we evaluate bidirectional permuteformer on long-range arena, which consists of many longsequence tasks. unidirectional permuteformer is evaluated on wikitext-103, a language modeling task. 3 ## conclusions we discuss possible ways to add relative position encoding to performer, a family of efficient transformers scales linearly. based on the analysis, we propose permuteformer, a variant of performer with position-aware permutation to encode relative positional information. while improving the performance, this novel relative position encoding introduces negligible overhead compared to the overall computational cost of performer. experiments show that it runs as fast as performer. extensive experiments are conducted on per-muteformer, including byte-level text tasks and pixel-level image classification of long-range arena, as well as language modeling on wikitext-103. bidirectional permuteformer is used for the former tasks, while unidirectional permuteformer is adopted for the latter one. results show that permuteformer uniformly improves the performance of performer, accelerates convergence, and achieves state-of-the-art on some tasks.