# SEA: Sparse Linear Attention with Estimated Attention Mask

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

## Key facts

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

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Distilling the Knowledge in a Neural Network](https://mlsanity.com/paper/1503.02531/) (2015)
- [GLUE: A Multi-Task Benchmark and Analysis Platform for Natural Language Understanding](https://mlsanity.com/paper/1804.07461/) (2018)
- [FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness](https://mlsanity.com/paper/2205.14135/) (2022)
- [OPT: Open Pre-trained Transformer Language Models](https://mlsanity.com/paper/2205.01068/) (2022)
- [Longformer: The Long-Document Transformer](https://mlsanity.com/paper/2004.05150/) (2020)
- [Pointer Sentinel Mixture Models](https://mlsanity.com/paper/1609.07843/) (2016)
- [A Broad-Coverage Challenge Corpus for Sentence Understanding through Inference](https://mlsanity.com/paper/1704.05426/) (2017)
- [WaveNet: A Generative Model for Raw Audio](https://mlsanity.com/paper/1609.03499/) (2016)
- [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)
- [TinyBERT: Distilling BERT for Natural Language Understanding](https://mlsanity.com/paper/1909.10351/) (2019)
- [Token Merging: Your ViT But Faster](https://mlsanity.com/paper/2210.09461/) (2022)
- [Super-NaturalInstructions: Generalization via Declarative Instructions on 1600+ NLP Tasks](https://mlsanity.com/paper/2204.07705/) (2022)
- [Sparse Sinkhorn Attention](https://mlsanity.com/paper/2002.11296/) (2020)
- [cosFormer: Rethinking Softmax in Attention](https://mlsanity.com/paper/2202.08791/) (2022)
- [Synthesizer: Rethinking Self-Attention in Transformer Models](https://mlsanity.com/paper/2005.00743/) (2020)
- [Learned Token Pruning for Transformers](https://mlsanity.com/paper/2107.00910/) (2021)
- [Scatterbrain: Unifying Sparse and Low-rank Attention Approximation](https://mlsanity.com/paper/2110.15343/) (2021)
- [Transformer Acceleration with Dynamic Sparse Attention](https://mlsanity.com/paper/2110.11299/) (2021)
- [Learning to Memorize Entailment and Discourse Relations for Persona-Consistent Dialogues](https://mlsanity.com/paper/2301.04871/) (2023)

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

- [A Training-free Sub-quadratic Cost Transformer Model Serving Framework With Hierarchically Pruned Attention](https://mlsanity.com/paper/2406.09827/) (2024)
- [When Linear Attention Meets Autoregressive Decoding: Towards More Effective and Efficient Linearized Large Language Models](https://mlsanity.com/paper/2406.07368/) (2024)
- [InfiniteHiP: Extending Language Model Context Up to 3 Million Tokens on a Single GPU](https://mlsanity.com/paper/2502.08910/) (2025)
- [FSA: An Alternative Efficient Implementation of Native Sparse Attention Kernel](https://mlsanity.com/paper/2508.18224/) (2025)
- [Training-Free Exponential Context Extension via Cascading KV Cache](https://mlsanity.com/paper/2406.17808/) (2024)
- [KV Admission: Learning What to Write for Efficient Long-Context LLM Inference](https://mlsanity.com/paper/2512.17452/) (2025)
- [ReviewGrounder: Improving Review Substantiveness with Rubric-Guided, Tool-Integrated Agents](https://mlsanity.com/paper/2604.14261/) (2026)
- [Fused3S: Fast Sparse Attention on Tensor Cores](https://mlsanity.com/paper/2505.08098/) (2025)
- [Breaking the Attention Bottleneck](https://mlsanity.com/paper/2406.10906/) (2024)
- [WorldAttention: An Efficient Attention Architecture for Interactive Video World Models](https://mlsanity.com/paper/2609.34606/) (2026)

## Abstract (arXiv)

The transformer architecture has driven breakthroughs in recent years on tasks which require modeling pairwise relationships between sequential elements, as is the case in natural language understanding. However, long seqeuences pose a problem due to the quadratic complexity of the attention operation. Previous research has aimed to lower the complexity by sparsifying or linearly approximating the attention matrix. Yet, these approaches cannot straightforwardly distill knowledge from a teacher's attention matrix and often require complete retraining from scratch. Furthermore, previous sparse and linear approaches lose interpretability if they cannot produce full attention matrices. To address these challenges, we propose SEA: Sparse linear attention with an Estimated Attention mask. SEA estimates the attention matrix with linear complexity via kernel-based linear attention, then subsequently creates a sparse attention matrix with a top-k selection to perform a sparse attention operation. For language modeling tasks (Wikitext2), previous linear and sparse attention methods show roughly two-fold worse perplexity scores over the quadratic OPT-1.3B baseline, while SEA achieves better perplexity than OPT-1.3B, using roughly half the memory of OPT-1.3B, providing interpretable attention matrix. We believe that our work will have a large practical impact, as it opens the possibility of running large transformers on resource-limited devices with less memory.