# Fourier Transformer: Fast Long Range Modeling by Removing Sequence Redundancy with FFT Operator

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- Builds on 44 of its 49 references that are in the map.
- First posted on arXiv 24 May 2023.

## Builds on (most cited first, 30 of 44)

- [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)
- [Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer](https://mlsanity.com/paper/1910.10683/) (2019)
- [RoBERTa: A Robustly Optimized BERT Pretraining Approach](https://mlsanity.com/paper/1907.11692/) (2019)
- [BART: Denoising Sequence-to-Sequence Pre-training for Natural Language Generation, Translation, and Comprehension](https://mlsanity.com/paper/1910.13461/) (2019)
- [Longformer: The Long-Document Transformer](https://mlsanity.com/paper/2004.05150/) (2020)
- [Pointer Sentinel Mixture Models](https://mlsanity.com/paper/1609.07843/) (2016)
- [Switch Transformers: Scaling to Trillion Parameter Models with Simple and Efficient Sparsity](https://mlsanity.com/paper/2101.03961/) (2021)
- [The Pile: An 800GB Dataset of Diverse Text for Language Modeling](https://mlsanity.com/paper/2101.00027/) (2020)
- [Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention](https://mlsanity.com/paper/2006.16236/) (2020)
- [Big Bird: Transformers for Longer Sequences](https://mlsanity.com/paper/2007.14062/) (2020)
- [Reformer: The Efficient Transformer](https://mlsanity.com/paper/2001.04451/) (2020)
- [Rethinking Attention with Performers](https://mlsanity.com/paper/2009.14794/) (2020)
- [Generating Long Sequences with Sparse Transformers](https://mlsanity.com/paper/1904.10509/) (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)
- [Perceiver: General Perception with Iterative Attention](https://mlsanity.com/paper/2103.03206/) (2021)
- [Teaching Machines to Read and Comprehend](https://mlsanity.com/paper/1506.03340/) (2015)
- [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)
- [ELI5: Long Form Question Answering](https://mlsanity.com/paper/1907.09190/) (2019)
- [KILT: a Benchmark for Knowledge Intensive Language Tasks](https://mlsanity.com/paper/2009.02252/) (2020)
- [Efficient Content-Based Sparse Attention with Routing Transformers](https://mlsanity.com/paper/2003.05997/) (2020)
- [Nystr"omformer: A Nystr"om-Based Algorithm for Approximating Self-Attention](https://mlsanity.com/paper/2102.03902/) (2021)
- [Reducing Transformer Depth on Demand with Structured Dropout](https://mlsanity.com/paper/1909.11556/) (2019)
- [Axial Attention in Multidimensional Transformers](https://mlsanity.com/paper/1912.12180/) (2019)
- [Random Feature Attention](https://mlsanity.com/paper/2103.02143/) (2021)
- [FNet: Mixing Tokens with Fourier Transforms](https://mlsanity.com/paper/2105.03824/) (2021)
- [A Structured Self-attentive Sentence Embedding](https://mlsanity.com/paper/1703.03130/) (2017)
- [Pay Less Attention with Lightweight and Dynamic Convolutions](https://mlsanity.com/paper/1901.10430/) (2019)

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

- [Accelerating Transformers with Spectrum-Preserving Token Merging](https://mlsanity.com/paper/2405.16148/) (2024)
- [SAM-PARSER: Fine-tuning SAM Efficiently by Parameter Space Reconstruction](https://mlsanity.com/paper/2308.14604/) (2023)
- [FAEDKV: Infinite-Window Fourier Transform for Unbiased KV Cache Compression](https://mlsanity.com/paper/2507.20030/) (2025)
- [EmMixformer: Mix transformer for eye movement recognition](https://mlsanity.com/paper/2401.04956/) (2024)
- [FreqKV: Key-Value Compression in Frequency Domain for Context Window Extension](https://mlsanity.com/paper/2505.00570/) (2025)
- [Fourier Controller Networks for Real-Time Decision-Making in Embodied Learning](https://mlsanity.com/paper/2405.19885/) (2024)
- [TreeKV: Smooth Key-Value Cache Compression with Tree Structures](https://mlsanity.com/paper/2501.04987/) (2025)
- [Fourier Compressor: Frequency-Domain Visual Token Compression for Vision-Language Models](https://mlsanity.com/paper/2508.06038/) (2025)
- [Adaptive KV Cache Reuse for Fast Long-Context LLM Serving](https://mlsanity.com/paper/2605.24022/) (2026)
- [Event USKT : U-State Space Model in Knowledge Transfer for Event Cameras](https://mlsanity.com/paper/2411.15276/) (2024)
- [Spectral Compression Transformer with Line Pose Graph for Monocular 3D Human Pose Estimation](https://mlsanity.com/paper/2505.21309/) (2025)
- [Towards Compressive and Scalable Recurrent Memory](https://mlsanity.com/paper/2602.11212/) (2026)
- [Efficient Encoder-Free Fourier-based 3D Large Multimodal Model](https://mlsanity.com/paper/2602.23153/) (2026)
- [Caracal: Causal Architecture via Spectral Mixing](https://mlsanity.com/paper/2605.00292/) (2026)
- [SUBLLM: A Novel Efficient Architecture with Token Sequence Subsampling for LLM](https://mlsanity.com/paper/2406.06571/) (2024)
- [Towards Efficient Post-Training via Fourier-Driven Adapter Architectures](https://mlsanity.com/paper/2512.22378/) (2025)
- [FourierSampler: Unlocking Non-Autoregressive Potential in Diffusion Language Models via Frequency-Guided Generation](https://mlsanity.com/paper/2601.23182/) (2026)
- [FourierMoE: Fourier Mixture-of-Experts Adaptation of Large Language Models](https://mlsanity.com/paper/2604.01762/) (2026)
- [Latent Fourier Transform](https://mlsanity.com/paper/2604.17986/) (2026)
- [WNet: Discrete Wavelets Transform for Efficient Token Mixing](https://mlsanity.com/paper/2610.04720/) (2026)

## Abstract (arXiv)

The transformer model is known to be computationally demanding, and prohibitively costly for long sequences, as the self-attention module uses a quadratic time and space complexity with respect to sequence length. Many researchers have focused on designing new forms of self-attention or introducing new parameters to overcome this limitation, however a large portion of them prohibits the model to inherit weights from large pretrained models. In this work, the transformer's inefficiency has been taken care of from another perspective. We propose Fourier Transformer, a simple yet effective approach by progressively removing redundancies in hidden sequence using the ready-made Fast Fourier Transform (FFT) operator to perform Discrete Cosine Transformation (DCT). Fourier Transformer is able to significantly reduce computational costs while retain the ability to inherit from various large pretrained models. Experiments show that our model achieves state-of-the-art performances among all transformer-based models on the long-range modeling benchmark LRA with significant improvement in both speed and space. For generative seq-to-seq tasks including CNN/DailyMail and ELI5, by inheriting the BART weights our model outperforms the standard BART and other efficient models. Our code is publicly available at https://github.com/LUMIA-Group/FourierTransformer