# Faster Causal Attention Over Large Sequences Through Sparse Flash Attention

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

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 36 references that are in the map.
- First posted on arXiv 1 Jun 2023.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness](https://mlsanity.com/paper/2205.14135/) (2022)
- [Longformer: The Long-Document Transformer](https://mlsanity.com/paper/2004.05150/) (2020)
- [The Pile: An 800GB Dataset of Diverse Text for Language Modeling](https://mlsanity.com/paper/2101.00027/) (2020)
- [Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention](https://mlsanity.com/paper/2006.16236/) (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)
- [Improving language models by retrieving from trillions of tokens](https://mlsanity.com/paper/2112.04426/) (2021)
- [Ethical and social risks of harm from Language Models](https://mlsanity.com/paper/2112.04359/) (2021)
- [Analyzing Multi-Head Self-Attention: Specialized Heads Do the Heavy Lifting, the Rest Can Be Pruned](https://mlsanity.com/paper/1905.09418/) (2019)
- [Are Sixteen Heads Really Better than One?](https://mlsanity.com/paper/1905.10650/) (2019)
- [Efficient Transformers: A Survey](https://mlsanity.com/paper/2009.06732/) (2020)
- [Long Range Arena: A Benchmark for Efficient Transformers](https://mlsanity.com/paper/2011.04006/) (2020)
- [Random Feature Attention](https://mlsanity.com/paper/2103.02143/) (2021)
- [SpAtten: Efficient Sparse Attention Architecture with Cascade Token and Head Pruning](https://mlsanity.com/paper/2012.09852/) (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)
- [Structured Pruning Learns Compact and Accurate Models](https://mlsanity.com/paper/2204.00408/) (2022)
- [Learned Token Pruning for Transformers](https://mlsanity.com/paper/2107.00910/) (2021)
- [Practical and Optimal LSH for Angular Distance](https://mlsanity.com/paper/1509.02897/) (2015)
- [Differentiable Subset Pruning of Transformer Heads](https://mlsanity.com/paper/2108.04657/) (2021)
- [Fixed Encoder Self-Attention Patterns in Transformer-Based Machine Translation](https://mlsanity.com/paper/2002.10260/) (2020)
- [Linear Complexity Randomized Self-attention Mechanism](https://mlsanity.com/paper/2204.04667/) (2022)
- [Scheduled DropHead: A Regularization Method for Transformer Models](https://mlsanity.com/paper/2004.13342/) (2020)
- [A Mixture of h-1 Heads is Better than h Heads](https://mlsanity.com/paper/2005.06537/) (2020)

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

- [A Survey on Efficient Inference for Large Language Models](https://mlsanity.com/paper/2404.14294/) (2024)
- [Efficient Large Language Models: A Survey](https://mlsanity.com/paper/2312.03863/) (2023)
- [LoongServe: Efficiently Serving Long-Context Large Language Models with Elastic Sequence Parallelism](https://mlsanity.com/paper/2404.09526/) (2024)
- [Towards Efficient Generative Large Language Model Serving: A Survey from Algorithms to Systems](https://mlsanity.com/paper/2312.15234/) (2023)
- [Advancing Transformer Architecture in Long-Context Large Language Models: A Comprehensive Survey](https://mlsanity.com/paper/2311.12351/) (2023)
- [Sparser is Faster and Less is More: Efficient Sparse Attention for Long-Range Transformers](https://mlsanity.com/paper/2406.16747/) (2024)
- [Mixture of Attention Spans: Optimizing LLM Inference Efficiency with Heterogeneous Sliding-Window Lengths](https://mlsanity.com/paper/2406.14909/) (2024)
- [SampleAttention: Near-Lossless Acceleration of Long Context LLM Inference with Adaptive Structured Sparse Attention](https://mlsanity.com/paper/2406.15486/) (2024)
- [Large Language Model Inference Acceleration: A Comprehensive Hardware Perspective](https://mlsanity.com/paper/2410.04466/) (2024)
- [Cognitive Memory in Large Language Models](https://mlsanity.com/paper/2504.02441/) (2025)
- [CoTFormer: A Chain-of-Thought Driven Architecture with Budget-Adaptive Computation Cost at Inference](https://mlsanity.com/paper/2310.10845/) (2023)
- [Analysing The Impact of Sequence Composition on Language Model Pre-Training](https://mlsanity.com/paper/2402.13991/) (2024)
- [FlashMask: Efficient and Rich Mask Extension of FlashAttention](https://mlsanity.com/paper/2410.01359/) (2024)
- [StoryBench: A Dynamic Benchmark for Evaluating Long-Term Memory with Multi Turns](https://mlsanity.com/paper/2506.13356/) (2025)
- [MoQAE: Mixed-Precision Quantization for Long-Context LLM Inference via Mixture of Quantization-Aware Experts](https://mlsanity.com/paper/2506.07533/) (2025)
- [HDT: Hierarchical Document Transformer](https://mlsanity.com/paper/2407.08330/) (2024)
- [Compression Barriers for Autoregressive Transformers](https://mlsanity.com/paper/2502.15955/) (2025)
- [Spark Transformer: Reactivating Sparsity in FFN and Attention](https://mlsanity.com/paper/2506.06644/) (2025)
- [Overcoming Long-Context Limitations of State-Space Models via Context-Dependent Sparse Attention](https://mlsanity.com/paper/2507.00449/) (2025)
- [Model Agnostic Hybrid Sharding For Heterogeneous Distributed Inference](https://mlsanity.com/paper/2407.19775/) (2024)
- [Longer Attention Span: Increasing Transformer Context Length with Sparse Graph Processing Techniques](https://mlsanity.com/paper/2502.01659/) (2025)
- [TalkMosaic: Interactive PhotoMosaic with Multi-modal LLM Q&A Interactions](https://mlsanity.com/paper/2409.13941/) (2024)
- [Mixtures of Subspaces for Bandwidth Efficient Context Parallel Training](https://mlsanity.com/paper/2606.16384/) (2026)
- [BF1: A Causal Dyadic Sparse-Attention Retrofit for Efficient Long-Context Transformers](https://mlsanity.com/paper/2608.20427/) (2026)
- [Channel Match: Calibrating Shape Latents for Few-Step 3D Generation](https://mlsanity.com/paper/2610.15321/) (2026)

## Abstract (arXiv)

Transformer-based language models have found many diverse applications requiring them to process sequences of increasing length. For these applications, the causal self-attention -- which is the only component scaling quadratically w.r.t. the sequence length -- becomes a central concern. While many works have proposed schemes to sparsify the attention patterns and reduce the computational overhead of self-attention, those are often limited by implementations concerns and end up imposing a simple and static structure over the attention matrix. Conversely, implementing more dynamic sparse attentions often results in runtimes significantly slower than computing the full attention using the Flash implementation from Dao et al. (2022). We extend FlashAttention to accommodate a large class of attention sparsity patterns that, in particular, encompass key/query dropping and hashing-based attention. This leads to implementations with no computational complexity overhead and a multi-fold runtime speedup on top of FlashAttention. Even with relatively low degrees of sparsity, our method improves visibly upon FlashAttention as the sequence length increases. Without sacrificing perplexity, we increase the training speed of a transformer language model by 2.0× and 3.3× for sequences of respectively 8k and 16k tokens.