mlsanityData to 14 Oct 2026

Scatterbrain: Unifying Sparse and Low-rank Attention Approximation

arXiv 2110.15343 ↗First posted 28 Oct 2021cs.LGcited by 130

Not on the map. Why?

Abstract (arXiv)

Recent advances in efficient Transformers have exploited either the sparsity or low-rank properties of attention matrices to reduce the computational and memory bottlenecks of modeling long sequences. However, it is still challenging to balance the trade-off between model quality and efficiency to perform a one-size-fits-all approximation for different tasks. To better understand this trade-off, we observe that sparse and low-rank approximations excel in different regimes, determined by the softmax temperature in attention, and sparse + low-rank can outperform each individually. Inspired by the classical robust-PCA algorithm for sparse and low-rank decomposition, we propose Scatterbrain, a novel way to unify sparse (via locality sensitive hashing) and low-rank (via kernel feature map) attention for accurate and efficient approximation. The estimation is unbiased with provably low error. We empirically show that Scatterbrain can achieve 2.1x lower error than baselines when serving as a drop-in replacement in BigGAN image generation and pre-trained T2T-ViT. On a pre-trained T2T Vision transformer, even without fine-tuning, Scatterbrain can reduce 98% of attention memory at the cost of only 1% drop in accuracy. We demonstrate Scatterbrain for end-to-end training with up to 4 points better perplexity and 5 points better average accuracy than sparse or low-rank efficient transformers on language modeling and long-range-arena tasks.

Key facts. Cited by 130 papers in the map (data through 14 Oct 2026). Builds on 50 of its 77 references that are in the map. First posted on arXiv 28 Oct 2021.

Builds on

50 of 77 references.

References · 50

  1. 2017Attention Is All You Needcited by 60,361
  2. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,399
  3. 2020Language Models are Few-Shot Learnerscited by 32,419
  4. 2020An Image is Worth 16x16 Words: Transformers for Image Recognition at Scalecited by 30,186
  5. 2019Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformercited by 14,599
  6. 2020End-to-End Object Detection with Transformerscited by 7,414
  7. 2018GLUE: A Multi-Task Benchmark and Analysis Platform for Natural Language Understandingcited by 4,899
  8. 2020Longformer: The Long-Document Transformercited by 3,413
  9. 2016Pointer Sentinel Mixture Modelscited by 3,096
  10. 2019XLNet: Generalized Autoregressive Pretraining for Language Understandingcited by 2,811
  11. 2019ALBERT: A Lite BERT for Self-supervised Learning of Language Representationscited by 2,790
  12. 2020Transformers are RNNs: Fast Autoregressive Transformers with Linear Attentioncited by 2,022
38 more
  1. 2019Transformer-XL: Attentive Language Models Beyond a Fixed-Length Contextcited by 1,850
  2. 2020Big Bird: Transformers for Longer Sequencescited by 1,684
  3. 2020Reformer: The Efficient Transformercited by 1,668
  4. 2020Rethinking Attention with Performerscited by 1,601
  5. 2019Generating Long Sequences with Sparse Transformerscited by 1,546
  6. 2020Linformer: Self-Attention with Linear Complexitycited by 1,474
  7. 2021Tokens-to-Token ViT: Training Vision Transformers from Scratch on ImageNetcited by 1,101
  8. 2020Efficient Transformers: A Surveycited by 790
  9. 2018Image Transformercited by 772
  10. 2019Compressive Transformers for Long-Range Sequence Modellingcited by 726
  11. 2020Long Range Arena: A Benchmark for Efficient Transformerscited by 700
  12. 2020HiPPO: Recurrent Memory with Optimal Polynomial Projectionscited by 605
  13. 2020Hopfield Networks is All You Needcited by 475
  14. 2020Efficient Content-Based Sparse Attention with Routing Transformerscited by 471
  15. 2021Nystr"omformer: A Nystr"om-Based Algorithm for Approximating Self-Attentioncited by 471
  16. 2019Pay Less Attention with Lightweight and Dynamic Convolutionscited by 211
  17. 2019Adaptive Attention Span in Transformerscited by 149
  18. 2020Sparse GPU Kernels for Deep Learningcited by 141
  19. 2018ListOps: A Diagnostic Dataset for Latent Tree Learningcited by 129
  20. 2014Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS)cited by 109
  21. 2015Practical and Optimal LSH for Angular Distancecited by 106
  22. 2021Long-Short Transformer: Efficient Transformers for Language and Visioncited by 102
  23. 2018Learning long-range spatial dependencies with horizontal gated-recurrent unitscited by 98
  24. 2021Luna: Linear Unified Nested Attentioncited by 96
  25. 2019Learning Fast Algorithms for Linear Transforms Using Butterfly Factorizationscited by 76
  26. 2019SLIDE : In Defense of Smart Algorithms over Hardware Acceleration for Large-Scale Deep Learning Systemscited by 46
  27. 2020SMYRF: Efficient Attention using Asymmetric Clusteringcited by 43
  28. 2015Structured Transforms for Small-Footprint Deep Learningcited by 42
  29. 2020Kaleidoscope: An Efficient, Learnable Representation For All Structured Linear Mapscited by 36
  30. 2014Global Convergence of Stochastic Gradient Descent for Some Non-convex Matrix Problemscited by 25
  31. 2020Simplified Self-Attention for Transformer-based End-to-End Speech Recognitioncited by 20
  32. 2018Learning Compressed Transforms with Low Displacement Rankcited by 19
  33. 2020Sub-Linear Memory: How to Make Performers SLiMcited by 18
  34. 2019Butterfly Transform: An Efficient FFT Based Neural Architecture Designcited by 16
  35. 2021Scalable Optimal Transport in High Dimensions for Graph Distances, Embedding Alignment, and Morecited by 11
  36. 2020Climbing the WOL: Training for Cheaper Inferencecited by 5
  37. 2020A Tale of Two Efficient and Informative Negative Sampling Distributionscited by 5
  38. 2017Unique Entity Estimation with Application to the Syrian Conflictcited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 1; 2022: 14; 2023: 39; 2024: 36; 2025: 26; 2026: 14.

130 papers.

Sort:

By area:

  1. 2022FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awarenesscited by 3,673
  2. 2023FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioningcited by 2,598
  3. 2024FlashAttention-3: Fast and Accurate Attention with Asynchrony and Low-precisioncited by 519
  4. 2023Scissorhands: Exploiting the Persistence of Importance Hypothesis for LLM KV Cache Compression at Test Timecited by 439
  5. 2024Titans: Learning to Memorize at Test Timecited by 328
  6. 2023SqueezeLLM: Dense-and-Sparse Quantizationcited by 294
  7. 2023Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Timecited by 252
  8. 2023A Cookbook of Self-Supervised Learningcited by 250
  9. 2024CacheBlend: Fast Large Language Model Serving for RAG with Cached Knowledge Fusioncited by 223
  10. 2023SparQ Attention: Bandwidth-Efficient LLM Inferencecited by 119
  11. 2024MagicPIG: LSH Sampling for Efficient LLM Generationcited by 111
  12. 2023Fast Attention Requires Bounded Entriescited by 102
38 more
  1. 2023Modeling Dense Multimodal Interactions Between Biological Pathways and Histology for Survival Predictioncited by 92
  2. 2023HyperAttention: Long-context Attention in Near-Linear Timecited by 85
  3. 2021Pixelated Butterfly: Simple and Efficient Sparse training for Neural Network Modelscited by 76
  4. 2024Get More with LESS: Synthesizing Recurrence with KV Cache Compression for Efficient LLM Inferencecited by 75
  5. 2023Advancing Transformer Architecture in Long-Context Large Language Models: A Comprehensive Surveycited by 72
  6. 2024ThinK: Thinner Key Cache by Query-Driven Pruningcited by 68
  7. 2024ReLU2 Wins: Discovering Efficient Activation Functions for Sparse LLMscited by 67
  8. 2023KDEformer: Accelerating Transformers via Kernel Density Estimationcited by 58
  9. 2024Sparser is Faster and Less is More: Efficient Sparse Attention for Long-Range Transformerscited by 52
  10. 2023Revisiting Token Pruning for Object Detection and Instance Segmentationcited by 50
  11. 2022Rank Diminishing in Deep Neural Networkscited by 47
  12. 2024Why Larger Language Models Do In-context Learning Differently?cited by 45
  13. 2024SLTrain: a sparse plus low-rank approach for parameter and memory efficient pretrainingcited by 45
  14. 2024Post-Training Sparse Attention with Double Sparsitycited by 45
  15. 2023Solving Regularized Exp, Cosh and Sinh Regression Problemscited by 44
  16. 2023How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computationcited by 44
  17. 2023The Closeness of In-Context Learning and Weight Shifting for Softmax Regressioncited by 41
  18. 2024MambaMixer: Efficient Selective State Space Models with Dual Token and Channel Selectioncited by 40
  19. 2024SampleAttention: Near-Lossless Acceleration of Long Context LLM Inference with Adaptive Structured Sparse Attentioncited by 39
  20. 2022Compute-Efficient Deep Learning: Algorithmic Trends and Opportunitiescited by 38
  21. 2024Uniform Memory Retrieval with Larger Capacity for Modern Hopfield Modelscited by 38
  22. 2023Randomized and Deterministic Attention Sparsification Algorithms for Over-parameterized Feature Dimensioncited by 37
  23. 2024Transformers are Minimax Optimal Nonparametric In-Context Learnerscited by 37
  24. 2023FlashFFTConv: Efficient Convolutions for Long Sequences with Tensor Corescited by 33
  25. 2022Linear Complexity Randomized Self-attention Mechanismcited by 31
  26. 2022Adaptable Butterfly Accelerator for Attention-based NNs via Hardware and Algorithm Co-designcited by 31
  27. 2023Neuron Structure Modeling for Generalizable Remote Physiological Measurementcited by 31
  28. 2022ViTALiTy: Unifying Low-rank and Sparse Approximation for Vision Transformer Acceleration with a Linear Taylor Attentioncited by 29
  29. 2023A Mathematical Abstraction for Balancing the Trade-off Between Creativity and Reality in Large Language Modelscited by 29
  30. 2022Castling-ViT: Compressing Self-Attention via Switching Towards Linear-Angular Attention at Vision Transformer Inferencecited by 28
  31. 2024LoLCATs: On Low-Rank Linearizing of Large Language Modelscited by 27
  32. 2023On Efficient Training of Large-Scale Deep Learning Models: A Literature Reviewcited by 26
  33. 2023How to Protect Copyright Data in Optimization of Large Language Models?cited by 26
  34. 2023Cuttlefish: Low-Rank Model Training without All the Tuningcited by 25
  35. 2023Efficient Attention via Control Variatescited by 23
  36. 2025Block-Sparse Global Attention for Efficient Multi-View Geometry Transformerscited by 23
  37. 2023Solving Attention Kernel Regression Problem via Pre-conditionercited by 20
  38. 2024SLoPe: Double-Pruned Sparse Plus Lazy Low-Rank Adapter Pretraining of LLMscited by 20

50 most cited of 130 All 130 (JSON)