Papers › Scatterbrain: Unifying Sparse and Low-rank Attention

Scatterbrain: Unifying Sparse and Low-rank Attention

21 May 2021NeurIPS 2021 12archive 2025-07-28

Beidi Chen, Tri Dao, Eric Winsor, Zhao Song, Atri Rudra, Christopher Ré

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.1 × 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.

PaperPDFCode

Syntology This paper has no arXiv id in the archive, and this site joins papers to Syntology's graph by arXiv id, so this page does not say whether the graph holds it.

Code

hazyresearch/scatterbrain officialmentioned in paperpytorchSyntology: no sample linked to this paper (harvested for another paper). Syntology's graph links these samples to Scatterbrain: Unifying Sparse and Low-rank Attention Approximation (arXiv:2110.15343; that paper's own run record: 1 ran (of which 0 constructed an object rather than computing a result; 0 with no instrument failure: 0 honoured, 0 violated, 0 with no contract checked; 1 where Syntology's instrument failed) · 0 unverified); nothing checks that they implement this paper's method. report

Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.

A paper named beside a repository with no sample linked to this paper is shown with that paper's own run record, not this paper's: “ran” means executed on a synthesized input, not that the code is correct, and “where Syntology's instrument failed” counts failures of Syntology's instrument, not of the code. Papers are listed in arXiv-id order, at most three per repository.

Code Syntology ran Syntology

Not run by Syntology. Nothing on this page verifies that the listed code works.

Tasks

Image GenerationLanguage ModelingLanguage Modelling

Results from the paper archive 2025-07-28

No leaderboard rows for this paper in the archive.

Methods

1x1 ConvolutionAdamAttentionBatch NormalizationConditional Batch NormalizationConvolutionDense ConnectionsDropoutEarly StoppingFeedforward NetworkGAN Hinge LossLayer NormalizationLinear LayerMulti-Head AttentionNon-Local BlockNon-Local OperationOff-Diagonal Orthogonal RegularizationProjection DiscriminatorReLUResidual BlockResidual ConnectionSAGANSoftmaxSpectral NormalizationT2T-ViTTTURTruncation Trick

Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections