# SMYRF: Efficient Attention using Asymmetric Clustering

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

## Key facts

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

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

- [FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness](https://mlsanity.com/paper/2205.14135/) (2022)
- [Hungry Hungry Hippos: Towards Language Modeling with State Space Models](https://mlsanity.com/paper/2212.14052/) (2022)
- [cosFormer: Rethinking Softmax in Attention](https://mlsanity.com/paper/2202.08791/) (2022)
- [Scatterbrain: Unifying Sparse and Low-rank Attention Approximation](https://mlsanity.com/paper/2110.15343/) (2021)
- [Token Fusion: Bridging the Gap between Token Pruning and Token Merging](https://mlsanity.com/paper/2312.01026/) (2023)
- [Fast Attention Requires Bounded Entries](https://mlsanity.com/paper/2302.13214/) (2023)
- [HyperAttention: Long-context Attention in Near-Linear Time](https://mlsanity.com/paper/2310.05869/) (2023)
- [Efficient Methods for Natural Language Processing: A Survey](https://mlsanity.com/paper/2209.00099/) (2022)
- [KDEformer: Accelerating Transformers via Kernel Density Estimation](https://mlsanity.com/paper/2302.02451/) (2023)
- [Stable, Fast and Accurate: Kernelized Attention with Relative Positional Encoding](https://mlsanity.com/paper/2106.12566/) (2021)
- [Solving Regularized Exp, Cosh and Sinh Regression Problems](https://mlsanity.com/paper/2303.15725/) (2023)
- [How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computation](https://mlsanity.com/paper/2310.04064/) (2023)
- [The Closeness of In-Context Learning and Weight Shifting for Softmax Regression](https://mlsanity.com/paper/2304.13276/) (2023)
- [Container: Context Aggregation Network](https://mlsanity.com/paper/2106.01401/) (2021)
- [Visual Attention Methods in Deep Learning: An In-Depth Survey](https://mlsanity.com/paper/2204.07756/) (2022)
- [Randomized and Deterministic Attention Sparsification Algorithms for Over-parameterized Feature Dimension](https://mlsanity.com/paper/2304.04397/) (2023)
- [Accelerating Transformers with Spectrum-Preserving Token Merging](https://mlsanity.com/paper/2405.16148/) (2024)
- [Expediting Large-Scale Vision Transformer for Dense Prediction without Fine-tuning](https://mlsanity.com/paper/2210.01035/) (2022)
- [Graph Transformers: A Survey](https://mlsanity.com/paper/2407.09777/) (2024)
- [Linear Complexity Randomized Self-attention Mechanism](https://mlsanity.com/paper/2204.04667/) (2022)
- [Vicinity Vision Transformer](https://mlsanity.com/paper/2206.10552/) (2022)
- [EcoFormer: Energy-Saving Attention with Linear Complexity](https://mlsanity.com/paper/2209.09004/) (2022)
- [Solving Attention Kernel Regression Problem via Pre-conditioner](https://mlsanity.com/paper/2308.14304/) (2023)
- [Beyond Classical Attention: Quantum Attention for Scalable Computation](https://mlsanity.com/paper/2307.08045/) (2023)
- [Why Softmax Attention Outperforms Linear Attention](https://mlsanity.com/paper/2310.11685/) (2023)
- [Predicting Attention Sparsity in Transformers](https://mlsanity.com/paper/2109.12188/) (2021)
- [What Can We Learn from State Space Models for Machine Learning on Graphs?](https://mlsanity.com/paper/2406.05815/) (2024)
- [Locality-Sensitive Hashing-Based Efficient Point Transformer with Applications in High-Energy Physics](https://mlsanity.com/paper/2402.12535/) (2024)
- [Kinetics: Rethinking Test-Time Scaling Laws](https://mlsanity.com/paper/2506.05333/) (2025)
- [AiluRus: A Scalable ViT Framework for Dense Prediction](https://mlsanity.com/paper/2311.01197/) (2023)

## Abstract (arXiv)

We propose a novel type of balanced clustering algorithm to approximate attention. Attention complexity is reduced from O(N2) to O(N log N), where N is the sequence length. Our algorithm, SMYRF, uses Locality Sensitive Hashing (LSH) in a novel way by defining new Asymmetric transformations and an adaptive scheme that produces balanced clusters. The biggest advantage of SMYRF is that it can be used as a drop-in replacement for dense attention layers without any retraining. On the contrary, prior fast attention methods impose constraints (e.g. queries and keys share the same vector representations) and require re-training from scratch. We apply our method to pre-trained state-of-the-art Natural Language Processing and Computer Vision models and we report significant memory and speed benefits. Notably, SMYRF-BERT outperforms (slightly) BERT on GLUE, while using 50% less memory. We also show that SMYRF can be used interchangeably with dense attention before and after training. Finally, we use SMYRF to train GANs with attention in high resolutions. Using a single TPU, we were able to scale attention to 128x128=16k and 256x256=65k tokens on BigGAN on CelebA-HQ.