  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.
