# Fast Transformers with Clustered Attention

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

## Key facts

- Cited by 123 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Jul 2020.

## Built on by (most cited first, 30 of 123)

- [Transformers in Vision: A Survey](https://mlsanity.com/paper/2101.01169/) (2021)
- [Nystr"omformer: A Nystr"om-Based Algorithm for Approximating Self-Attention](https://mlsanity.com/paper/2102.03902/) (2021)
- [A Survey of Transformers](https://mlsanity.com/paper/2106.04554/) (2021)
- [FNet: Mixing Tokens with Fourier Transforms](https://mlsanity.com/paper/2105.03824/) (2021)
- [Long Range Language Modeling via Gated State Spaces](https://mlsanity.com/paper/2206.13947/) (2022)
- [cosFormer: Rethinking Softmax in Attention](https://mlsanity.com/paper/2202.08791/) (2022)
- [Efficient Large Language Models: A Survey](https://mlsanity.com/paper/2312.03863/) (2023)
- [Separable Self-attention for Mobile Vision Transformers](https://mlsanity.com/paper/2206.02680/) (2022)
- [OnePose: One-Shot Object Pose Estimation without CAD Models](https://mlsanity.com/paper/2205.12257/) (2022)
- [The emergence of clusters in self-attention dynamics](https://mlsanity.com/paper/2305.05465/) (2023)
- [Learned Token Pruning for Transformers](https://mlsanity.com/paper/2107.00910/) (2021)
- [Unlimiformer: Long-Range Transformers with Unlimited Length Input](https://mlsanity.com/paper/2305.01625/) (2023)
- [Voxel Set Transformer: A Set-to-Set Approach to 3D Object Detection from Point Clouds](https://mlsanity.com/paper/2203.10314/) (2022)
- [Finetuning Pretrained Transformers into RNNs](https://mlsanity.com/paper/2103.13076/) (2021)
- [A Practical Survey on Faster and Lighter Transformers](https://mlsanity.com/paper/2103.14636/) (2021)
- [Token Pooling in Vision Transformers](https://mlsanity.com/paper/2110.03860/) (2021)
- [Flowformer: Linearizing Transformers with Conservation Flows](https://mlsanity.com/paper/2202.06258/) (2022)
- [Align and Attend: Multimodal Summarization with Dual Contrastive Losses](https://mlsanity.com/paper/2303.07284/) (2023)
- [Linear algebra with transformers](https://mlsanity.com/paper/2112.01898/) (2021)
- [Memory-efficient Transformers via Top-k Attention](https://mlsanity.com/paper/2106.06899/) (2021)
- [Training-free Diffusion Model Adaptation for Variable-Sized Text-to-Image Synthesis](https://mlsanity.com/paper/2306.08645/) (2023)
- [Sparser is Faster and Less is More: Efficient Sparse Attention for Long-Range Transformers](https://mlsanity.com/paper/2406.16747/) (2024)
- [Stable, Fast and Accurate: Kernelized Attention with Relative Positional Encoding](https://mlsanity.com/paper/2106.12566/) (2021)
- [Revisiting Token Pruning for Object Detection and Instance Segmentation](https://mlsanity.com/paper/2306.07050/) (2023)
- [Museformer: Transformer with Fine- and Coarse-Grained Attention for Music Generation](https://mlsanity.com/paper/2210.10349/) (2022)
- [Efficient Visual Tracking with Exemplar Transformers](https://mlsanity.com/paper/2112.09686/) (2021)
- [On the Expressive Power of Self-Attention Matrices](https://mlsanity.com/paper/2106.03764/) (2021)
- [Prototypical Cross-Attention Networks for Multiple Object Tracking and Segmentation](https://mlsanity.com/paper/2106.11958/) (2021)
- [EGformer: Equirectangular Geometry-biased Transformer for 360 Depth Estimation](https://mlsanity.com/paper/2304.07803/) (2023)
- [vid-TLDR: Training Free Token merging for Light-weight Video Transformer](https://mlsanity.com/paper/2403.13347/) (2024)

## Abstract (arXiv)

Transformers have been proven a successful model for a variety of tasks in sequence modeling. However, computing the attention matrix, which is their key component, has quadratic complexity with respect to the sequence length, thus making them prohibitively expensive for large sequences. To address this, we propose clustered attention, which instead of computing the attention for every query, groups queries into clusters and computes attention just for the centroids. To further improve this approximation, we use the computed clusters to identify the keys with the highest attention per query and compute the exact key/query dot products. This results in a model with linear complexity with respect to the sequence length for a fixed number of clusters. We evaluate our approach on two automatic speech recognition datasets and show that our model consistently outperforms vanilla transformers for a given computational budget. Finally, we demonstrate that our model can approximate arbitrarily complex attention distributions with a minimal number of clusters by approximating a pretrained BERT model on GLUE and SQuAD benchmarks with only 25 clusters and no loss in performance.