Research map / Architectures and efficiency / Attention and transformers
LevAttention: Time, Space and Streaming Efficient Algorithm for Heavy Attentions
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that large attention scores of f(x)=|x|^p attention can be found via a universal key set of size independent of n (leverage/Lewis-weight sensitivities), and proposes LevAttention, training ViTs that attend only to leverage-score-selected keys.
Problem
Computing softmax-like attention matrices costs O(n^2 d) time, which is prohibitive for long contexts; the paper asks whether all large attention entries can be identified in time linear in n without data assumptions.
Approach
Large attention scores are bounded by f-sensitivities of the key matrix, so a universal set U of keys (those with sensitivity at least epsilon, e.g., high leverage scores) of size independent of n contains all large attention targets for any query; this set can be found in streaming/parallel fashion, and ViTs can be trained to attend only to top-32 leverage-score keys per head.
Key results
- Leverage-score top-32 selection on a pretrained softmax L/16 ViT gives 48.58% accuracy vs 8.9% for squared-row-norm selection and 78.83% for full softmax.
- Training L/16 with LevAttention top-32 from scratch-style warm start reaches 75.12% accuracy; top-64 reaches 77.27%.
- Sum of f-sensitivities bounds the universal set size: |U| <= Psi^f/epsilon, with Psi^f <= d for 1<=p<=2 and d^{p/2} for p>2.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace full softmax attention with top-32 leverage-score selection at inference | S/16 pretrained with softmax · ImageNet-1k validation | accuracy: 76.47% -> 13.3% | Hurt |
| Replace squared row norm selection with leverage-score selection for top-32 keys at inference | S/16 pretrained with softmax · ImageNet-1k validation | accuracy: 3.3% -> 13.3% | Helped |
| Train with leverage-score selection instead of applying it only at inference | S/16 · ImageNet-1k validation | accuracy: 13.3% -> 68.30% | Helped |
| Increase selected keys from top-32 to top-64 (ablation) | S/16 trained with LevAttention · ImageNet-1k validation | accuracy: 68.30% -> 72.48% | Helped |
| Replace full softmax attention with top-32 leverage-score selection at inference | L/16 pretrained with softmax · ImageNet-1k validation | accuracy: 78.83% -> 48.58% | Hurt |
| Replace squared row norm selection with leverage-score selection for top-32 keys at inference | L/16 pretrained with softmax · ImageNet-1k validation | accuracy: 8.9% -> 48.58% | Helped |
| Train with leverage-score selection instead of applying it only at inference | L/16 · ImageNet-1k validation | accuracy: 48.58% -> 75.12% | Helped |
| Increase selected keys from top-32 to top-64 (ablation) | L/16 trained with LevAttention · ImageNet-1k validation | accuracy: 75.12% -> 77.27% | Helped |
| Increase selected keys from top-32 to top-128 (ablation) | L/16 trained with LevAttention · ImageNet-1k validation | accuracy: 75.12% -> 77.17% | Helped |
| Replace full softmax attention with top-32 leverage-score selection at inference | L/8 pretrained with softmax · ImageNet-1k validation | accuracy: 79.47% -> 0.8% | Hurt |
| Train with leverage-score selection instead of applying it only at inference | L/8 · ImageNet-1k validation | accuracy: 0.8% -> 71.96% | Helped |
| Increase selected keys from top-32 to top-64 (ablation) | L/8 trained with LevAttention · ImageNet-1k validation | accuracy: 71.96% -> 74.64% | Helped |
Surprising findings
- Models trained with leverage-score selection achieve accuracy similar to those trained with row-norm or even random key selection, so selection-aware training did not exploit leverage score advantage.
- Pretrained softmax ViT with LevAttention top-32 selection at inference drops to 0.8% for L/8, far below the L/16 result.
Limitations
- Accuracy drops substantially versus full softmax attention when restricting to top-32 keys at inference on pretrained models.
- Selection-aware training with leverage scores did not outperform simpler row-norm or random selection.
- Theoretical guarantees rely on bounds on sensitivity sums and the online condition number, which may be large in practice.
Experimental setup
Datasets: ImageNet-1k
Benchmarks: ImageNet-1k
Metrics: top-1 validation accuracy
Baselines: softmax attention row norm selection random key selection
Builds on: Lewis weights online leverage scores PolySketchFormer ViT
Closest papers by meaning
- MonarchAttention: Zero-Shot Conversion to Fast, Hardware-Aware Structured Attention (NeurIPS 2025 · similarity 0.86)
- XAttention: Block Sparse Attention with Antidiagonal Scoring (ICML 2025 · similarity 0.86)
- Algorithm and Hardness for Dynamic Attention Maintenance in Large Language Models (ICML 2024 · similarity 0.85)
- kNN Attention Demystified: A Theoretical Exploration for Scalable Transformers (ICLR 2025 · similarity 0.85)
- Fundamental Limitations on Subquadratic Alternatives to Transformers (ICLR 2025 · similarity 0.85)
- Are Transformers with One Layer Self-Attention Using Low-Rank Weight Matrices Universal Approximators? (ICLR 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.