# TaylorShift: Shifting the Complexity of Self-Attention from Squared to Linear (and Back) using Taylor-Softmax

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 42 references that are in the map.
- First posted on arXiv 5 Mar 2024.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Swin Transformer: Hierarchical Vision Transformer using Shifted Windows](https://mlsanity.com/paper/2103.14030/) (2021)
- [FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness](https://mlsanity.com/paper/2205.14135/) (2022)
- [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)
- [Rethinking Attention with Performers](https://mlsanity.com/paper/2009.14794/) (2020)
- [Linformer: Self-Attention with Linear Complexity](https://mlsanity.com/paper/2006.04768/) (2020)
- [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)
- [Nystr"omformer: A Nystr"om-Based Algorithm for Approximating Self-Attention](https://mlsanity.com/paper/2102.03902/) (2021)
- [DeiT III: Revenge of the ViT](https://mlsanity.com/paper/2204.07118/) (2022)
- [A Survey of Transformers](https://mlsanity.com/paper/2106.04554/) (2021)
- [Random Feature Attention](https://mlsanity.com/paper/2103.02143/) (2021)
- [XCiT: Cross-Covariance Image Transformers](https://mlsanity.com/paper/2106.09681/) (2021)
- [Explaining NonLinear Classification Decisions with Deep Taylor Decomposition](https://mlsanity.com/paper/1512.02479/) (2015)
- [On The Computational Complexity of Self-Attention](https://mlsanity.com/paper/2209.04881/) (2022)
- [Focused Transformer: Contrastive Training for Context Scaling](https://mlsanity.com/paper/2307.03170/) (2023)
- [ListOps: A Diagnostic Dataset for Latent Tree Learning](https://mlsanity.com/paper/1804.06028/) (2018)
- [Scaling Transformer to 1M tokens and beyond with RMT](https://mlsanity.com/paper/2304.11062/) (2023)
- [MB-TaylorFormer: Multi-branch Efficient Transformer Expanded by Taylor Formula for Image Dehazing](https://mlsanity.com/paper/2308.14036/) (2023)
- [A Practical Survey on Faster and Lighter Transformers](https://mlsanity.com/paper/2103.14636/) (2021)
- [Explaining Convolutional Neural Networks using Softmax Gradient Layer-wise Relevance Propagation](https://mlsanity.com/paper/1908.04351/) (2019)
- [ViTALiTy: Unifying Low-rank and Sparse Approximation for Vision Transformer Acceleration with a Linear Taylor Attention](https://mlsanity.com/paper/2211.05109/) (2022)
- [An Exploration of Softmax Alternatives Belonging to the Spherical Loss Family](https://mlsanity.com/paper/1511.05042/) (2015)
- [Efficient Attention via Control Variates](https://mlsanity.com/paper/2302.04542/) (2023)
- [Exploring Alternatives to Softmax Function](https://mlsanity.com/paper/2011.11538/) (2020)

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

- [Understanding the differences in Foundation Models: Attention, State Space Models, and Recurrent Neural Networks](https://mlsanity.com/paper/2405.15731/) (2024)
- [On the Expressiveness of Softmax Attention: A Recurrent Neural Network Perspective](https://mlsanity.com/paper/2507.23632/) (2025)
- [ZeroS: Zero-Sum Linear Attention for Efficient Transformers](https://mlsanity.com/paper/2602.05230/) (2026)
- [Optimizing Vision Transformers with Data-Free Knowledge Transfer](https://mlsanity.com/paper/2408.05952/) (2024)
- [A Low-Resolution Image is Worth 1x1 Words: Enabling Fine Image Super-Resolution with Transformers and TaylorShift](https://mlsanity.com/paper/2411.10231/) (2024)
- [Self-Attention at Constant Cost per Token via Symmetry-Aware Taylor Approximation](https://mlsanity.com/paper/2602.00294/) (2026)
- [Not All Dimensions Are Equal: Outlier-Aware Attention Linearization with Grouped Quadratic Kernels](https://mlsanity.com/paper/2610.13674/) (2026)
- [Expanding Attention: A Taylor-Series Route to Linear-Time Transformers with a Fixed Number of Recurrent States](https://mlsanity.com/paper/2610.20637/) (2026)

## Abstract (arXiv)

The quadratic complexity of the attention mechanism represents one of the biggest hurdles for processing long sequences using Transformers. Current methods, relying on sparse representations or stateful recurrence, sacrifice token-to-token interactions, which ultimately leads to compromises in performance. This paper introduces TaylorShift, a novel reformulation of the Taylor softmax that enables computing full token-to-token interactions in linear time and space. We analytically determine the crossover points where employing TaylorShift becomes more efficient than traditional attention, aligning closely with empirical measurements. Specifically, our findings demonstrate that TaylorShift enhances memory efficiency for sequences as short as 800 tokens and accelerates inference for inputs of approximately 1700 tokens and beyond. For shorter sequences, TaylorShift scales comparably with the vanilla attention. Furthermore, a classification benchmark across five tasks involving long sequences reveals no degradation in accuracy when employing Transformers equipped with TaylorShift. For reproducibility, we provide access to our code under https://github.com/tobna/TaylorShift.