# LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 38 references that are in the map.
- First posted on arXiv 7 Oct 2024.

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

- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [ImageNet Large Scale Visual Recognition Challenge](https://mlsanity.com/paper/1409.0575/) (2014)
- [Longformer: The Long-Document Transformer](https://mlsanity.com/paper/2004.05150/) (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)
- [Linformer: Self-Attention with Linear Complexity](https://mlsanity.com/paper/2006.04768/) (2020)
- [Image Transformer](https://mlsanity.com/paper/1802.05751/) (2018)
- [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)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Sparse Sinkhorn Attention](https://mlsanity.com/paper/2002.11296/) (2020)
- [LambdaNetworks: Modeling Long-Range Interactions Without Attention](https://mlsanity.com/paper/2102.08602/) (2021)
- [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)
- [KVT: k-NN Attention for Boosting Vision Transformers](https://mlsanity.com/paper/2106.00515/) (2021)
- [Memory-efficient Transformers via Top-k Attention](https://mlsanity.com/paper/2106.06899/) (2021)
- [KDEformer: Accelerating Transformers via Kernel Density Estimation](https://mlsanity.com/paper/2302.02451/) (2023)
- [Optimal approximate matrix product in terms of stable rank](https://mlsanity.com/paper/1507.02268/) (2015)
- [PolySketchFormer: Fast Transformers via Sketching Polynomial Kernels](https://mlsanity.com/paper/2310.01655/) (2023)
- [A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Time](https://mlsanity.com/paper/2309.07418/) (2023)
- [Solving Attention Kernel Regression Problem via Pre-conditioner](https://mlsanity.com/paper/2308.14304/) (2023)
- [Online Row Sampling](https://mlsanity.com/paper/1604.05448/) (2016)
- [Dimensionality Reduction for Tukey Regression](https://mlsanity.com/paper/1905.05376/) (2019)
- [Hardness of Low Rank Approximation of Entrywise Transformed Matrix Products](https://mlsanity.com/paper/2311.01960/) (2023)

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

- [Sublinear Time Quantum Algorithm for Attention Approximation](https://mlsanity.com/paper/2602.00874/) (2026)
- [Trust the Mass: Forced Weights in KV-Cache Eviction](https://mlsanity.com/paper/2608.25230/) (2026)
- [Efficient Attention via Pre-Scoring: Prioritizing Informative Keys in Transformers](https://mlsanity.com/paper/2505.11040/) (2025)

## Abstract (arXiv)

A central problem related to transformers can be stated as follows: given two n × d matrices Q and K, and a non-negative function f, define the matrix A as follows: (1) apply the function f to each entry of the n × n matrix Q KT, and then (2) normalize each of the row sums of A to be equal to 1. The matrix A can be computed in O(n2 d) time assuming f can be applied to a number in constant time, but the quadratic dependence on n is prohibitive in applications where it corresponds to long context lengths. For a large class of functions f, we show how to find all the ``large attention scores", i.e., entries of A which are at least a positive value varepsilon, in time with linear dependence on n (i.e., n · textrmpoly(d/varepsilon)) for a positive parameter varepsilon > 0. Our class of functions include all functions f of the form f(x) = |x|p, as explored recently in transformer models. Using recently developed tools from randomized numerical linear algebra, we prove that for any K, there is a ``universal set" U subset [n] of size independent of n, such that for any Q and any row i, the large attention scores Ai,j in row i of A all have j ∈ U. We also find U in n · textrmpoly(d/varepsilon) time. Notably, we (1) make no assumptions on the data, (2) our workspace does not grow with n, and (3) our algorithms can be computed in streaming and parallel settings. We call the attention mechanism that uses only the subset of keys in the universal set as LevAttention since our algorithm to identify the universal set U is based on leverage scores. We empirically show the benefits of our scheme for vision transformers, showing how to train new models that use our universal set while training as well, showing that our model is able to consistently select ``important keys'' during training.