# PermuteFormer: Efficient Relative Position Encoding for Long Sequences

arXiv: https://arxiv.org/abs/2109.02377 · HTML: https://mlsanity.com/paper/2109.02377/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 30 references that are in the map.
- First posted on arXiv 6 Sep 2021.

## Builds on (most cited first, 27 of 27)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer](https://mlsanity.com/paper/1910.10683/) (2019)
- [RoFormer: Enhanced Transformer with Rotary Position Embedding](https://mlsanity.com/paper/2104.09864/) (2021)
- [wav2vec 2.0: A Framework for Self-Supervised Learning of Speech Representations](https://mlsanity.com/paper/2006.11477/) (2020)
- [Longformer: The Long-Document Transformer](https://mlsanity.com/paper/2004.05150/) (2020)
- [Pointer Sentinel Mixture Models](https://mlsanity.com/paper/1609.07843/) (2016)
- [XLNet: Generalized Autoregressive Pretraining for Language Understanding](https://mlsanity.com/paper/1906.08237/) (2019)
- [DeBERTa: Decoding-enhanced BERT with Disentangled Attention](https://mlsanity.com/paper/2006.03654/) (2020)
- [Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention](https://mlsanity.com/paper/2006.16236/) (2020)
- [Transformer-XL: Attentive Language Models Beyond a Fixed-Length Context](https://mlsanity.com/paper/1901.02860/) (2019)
- [Big Bird: Transformers for Longer Sequences](https://mlsanity.com/paper/2007.14062/) (2020)
- [Reformer: The Efficient Transformer](https://mlsanity.com/paper/2001.04451/) (2020)
- [LXMERT: Learning Cross-Modality Encoder Representations from Transformers](https://mlsanity.com/paper/1908.07490/) (2019)
- [fairseq: A Fast, Extensible Toolkit for Sequence Modeling](https://mlsanity.com/paper/1904.01038/) (2019)
- [Linformer: Self-Attention with Linear Complexity](https://mlsanity.com/paper/2006.04768/) (2020)
- [Self-Attention with Relative Position Representations](https://mlsanity.com/paper/1803.02155/) (2018)
- [Efficient Transformers: A Survey](https://mlsanity.com/paper/2009.06732/) (2020)
- [Long Range Arena: A Benchmark for Efficient Transformers](https://mlsanity.com/paper/2011.04006/) (2020)
- [LayoutLM: Pre-training of Text and Layout for Document Image Understanding](https://mlsanity.com/paper/1912.13318/) (2019)
- [Nystr"omformer: A Nystr"om-Based Algorithm for Approximating Self-Attention](https://mlsanity.com/paper/2102.03902/) (2021)
- [Random Feature Attention](https://mlsanity.com/paper/2103.02143/) (2021)
- [Synthesizer: Rethinking Self-Attention in Transformer Models](https://mlsanity.com/paper/2005.00743/) (2020)
- [Finetuning Pretrained Transformers into RNNs](https://mlsanity.com/paper/2103.13076/) (2021)
- [Sub-Linear Memory: How to Make Performers SLiM](https://mlsanity.com/paper/2012.11346/) (2020)

## Built on by (most cited first, 14 of 14)

- [LLM Inference Unveiled: Survey and Roofline Model Insights](https://mlsanity.com/paper/2402.16363/) (2024)
- [Advancing Transformer Architecture in Long-Context Large Language Models: A Comprehensive Survey](https://mlsanity.com/paper/2311.12351/) (2023)
- [MH-DETR: Video Moment and Highlight Detection with Cross-modal Transformer](https://mlsanity.com/paper/2305.00355/) (2023)
- [Efficient Attention via Control Variates](https://mlsanity.com/paper/2302.04542/) (2023)
- [Linearized Relative Positional Encoding](https://mlsanity.com/paper/2307.09270/) (2023)
- [On Learning the Transformer Kernel](https://mlsanity.com/paper/2110.08323/) (2021)
- [SMR: State Memory Replay for Long Sequence Modeling](https://mlsanity.com/paper/2405.17534/) (2024)
- [Transformers as Graph-to-Graph Models](https://mlsanity.com/paper/2310.17936/) (2023)
- [Word Order Matters when you Increase Masking](https://mlsanity.com/paper/2211.04427/) (2022)
- [Ripple Attention for Visual Perception with Sub-quadratic Complexity](https://mlsanity.com/paper/2110.02453/) (2021)
- [ContextSpeech: Expressive and Efficient Text-to-Speech for Paragraph Reading](https://mlsanity.com/paper/2307.00782/) (2023)
- [Neural Architectures for Biological Inter-Sentence Relation Extraction](https://mlsanity.com/paper/2112.09288/) (2021)
- [Lightweight Structure-Aware Attention for Visual Understanding](https://mlsanity.com/paper/2211.16289/) (2022)
- [An Evaluation of Context Length Extrapolation in Long Code via Positional Embeddings and Efficient Attention](https://mlsanity.com/paper/2602.21800/) (2026)

## Abstract (arXiv)

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.