FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness

Tri Dao, Daniel Y. Fu, Stefano Ermon, Atri Rudra, Christopher Ré

The Quadratic Bottleneck in Transformers

The "Standard Attention" mechanism at the heart of Transformers has a major flaw: its computational and memory requirements grow quadratically with the sequence length ($N^2$). If you double the length of a document, the attention processing becomes four times as demanding.

While many "efficient" attention variants have been proposed—such as sparse or low-rank approximations—they often fail to deliver real-world wall-clock speedups. The authors of this paper argue that this is because existing methods focus primarily on reducing FLOPs (floating-point operations) while ignoring IO overhead. IO overhead is the time spent moving data between the GPU’s slow, large memory (High Bandwidth Memory or HBM) and its fast, small on-chip memory (SRAM). On modern GPUs, mathematical operations are often faster than memory transfers, making memory access the true bottleneck.

Memory hierarchy and FlashAttention tiling mechanism

FlashAttention: An IO-Aware Approach

FlashAttention introduces an IO-aware algorithm to compute exact attention. It uses two primary techniques to minimize costly HBM accesses:

  1. Tiling: The algorithm breaks the massive $N \times N$ attention matrix into smaller blocks that comfortably fit into the GPU's fast SRAM. It computes the attention for these blocks locally and then "stitches" them back together. To achieve this with the Softmax function (which traditionally requires access to an entire row at once), the authors employ a mathematical trick to compute the Softmax normalization factor incrementally.
  2. Recomputation: In standard training, the large attention matrix is materialized and stored in HBM for the backward pass (gradient calculation). FlashAttention avoids this massive memory write entirely. Instead, it only stores the Softmax normalization factors and recomputes the necessary attention blocks on-the-fly during the backward pass.

Even though recomputation involves strictly more mathematical operations, it is significantly faster. It saves the model from the "slow lane" of HBM storage, proving that optimizing data movement is often more critical than optimizing raw calculations. The authors implemented this as a single "fused" CUDA kernel to maintain fine-grained control over memory movement.

Performance comparison showing FlashAttention uses more GFLOPs but significantly less HBM read/write, resulting in faster runtime

Key Insights

  • More Math can be Faster: The most counter-intuitive takeaway is that doing extra work (recomputing the attention matrix) is a net win for speed because it drastically reduces HBM reads and writes.
  • Exactness Matters: Unlike many previous "efficient" Transformers that approximate attention to save time (often degrading model quality), FlashAttention is an exact implementation. It delivers speed and memory benefits without any drop in accuracy.
  • Linear Memory Scaling: By avoiding the materialization of the $N \times N$ matrix, memory usage scales linearly with sequence length ($O(N)$), allowing for context windows that were previously physically impossible to fit on a GPU.

Empirical Results and Breakthroughs

The authors evaluated FlashAttention across a wide variety of benchmarks, including language modeling (BERT-large, GPT-2), Long-Range Arena (LRA), and long document classification (MIMIC-III, ECtHR).

  • Speed: FlashAttention achieves a 15% end-to-end wall-clock speedup on BERT-large and a 3x speedup on GPT-2 compared to standard implementations.
  • Scaling and Model Quality: It enables Transformers to scale to sequence lengths of 64k. By allowing GPT-2 to process 4k tokens instead of the usual 1k, the model achieved a 0.7 better perplexity, demonstrating that longer context directly translates to better language understanding.
  • New Capabilities: FlashAttention allowed a Transformer to solve the Path-X challenge (16k sequence length) for the first time, achieving better-than-chance accuracy (61.4%), and similarly succeeded on Path-256 (64k length).

Limitations and Future Work

While highly effective, FlashAttention requires writing low-level CUDA kernels, making it less portable across different hardware architectures (like TPUs or non-NVIDIA GPUs) compared to standard high-level PyTorch code. The current optimizations are highly tuned for the memory hierarchy of modern NVIDIA GPUs (like the A100).

Looking forward, the authors suggest that "IO-awareness" should be applied to other memory-intensive layers in deep learning, not just the attention mechanism. They envision a future where deep learning compilers automatically perform these types of IO optimizations across all model architectures.

Summary updated

Abstract

Transformers are slow and memory-hungry on long sequences, since the time and memory complexity of self-attention are quadratic in sequence length. Approximate attention methods have attempted to address this problem by trading off model quality to reduce the compute complexity, but often do not achieve wall-clock speedup. We argue that a missing principle is making attention algorithms IO-aware---accounting for reads and writes between levels of GPU memory. We propose FlashAttention, an IO-aware exact attention algorithm that uses tiling to reduce the number of memory reads/writes between GPU high bandwidth memory (HBM) and GPU on-chip SRAM. We analyze the IO complexity of FlashAttention, showing that it requires fewer HBM accesses than standard attention, and is optimal for a range of SRAM sizes. We also extend FlashAttention, yielding an approximate attention algorithm that is faster than any existing approximate attention method. FlashAttention, 3x speedup on GPT-2 (seq. length 1K), and 2.4x speedup on long-range arena (seq. length 1K-4K). FlashAttention, yielding higher quality models (0.7 better perplexity on GPT-2 and 6.4 points of lift on long-document classification) and entirely new capabilities: the first Transformers to achieve better-than-chance performance on the Path-X challenge (seq. length 16K, 61.4% accuracy) and Path-256 (seq. length 64K, 63.1% accuracy).
BibTeX
@inproceedings{dao2022flashattention,
  author = {Tri Dao and Daniel Y. Fu and Stefano Ermon and Atri Rudra and Christopher Ré},
  title = {{FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=rED_fECrowq},
}
Figure