The paper in four sentences
Attention compares every word with every other word, producing a table of scores whose size grows with the square of the text length.
On a GPU, that table is too big for the small, very fast memory on the chip, so it gets written out to the large, slower main memory and read back several times, and this shuttling, not the maths, is what takes most of the time.
FlashAttention processes the attention in small tiles that fit in fast memory, using a running-total trick so the final answer is exactly the same, and never stores the full table.
Training became 15% to 3× faster depending on the model, and the memory saved let models handle inputs of thousands to tens of thousands of words, which improved their quality.
Idea · §1 · §2.1 · Fig. 1
The slow part is fetching, not cooking
A GPU, the chip that trains neural networks, has two kinds of memory. A small amount of very fast memory sits right next to the calculating units (about 20 MB in total on the Nvidia A100 the paper uses, split into many small pieces). A large amount of slower memory, called HBM, sits beside the chip (40 or 80 GB). The fast memory moves data roughly ten times faster.
GPUs have become so fast at arithmetic that many operations spend most of their time waiting for data to arrive from HBM. The authors' point is that attention is one of them. The standard way of computing it builds the whole table of scores (every word against every word), writes it to HBM, reads it back to turn scores into weights, writes the weights out, and reads them back again to blend the values.
Most earlier work on fast attention tried to do fewer calculations, often by approximating. These methods frequently didn't run faster in practice, because they did nothing about the memory traffic. The paper's slogan is that attention should be IO-aware: designed around the cost of input and output between memory levels.
TakeawayOn modern GPUs, standard attention is slow because it moves a huge score table to and from slow memory, not because the arithmetic is hard.
Check yourself
- Doubling the text length multiplies the score table's size by how much?
- Four: the table is N × N, so twice the rows and twice the columns.
- Why did many "fast" approximate attention methods not speed up training much?
- They cut the number of calculations but not the memory traffic, which was the real bottleneck.
Idea · §3.1 · Algorithm 1
Work in tiles with a running total
The obvious fix is to split the work into tiles small enough for fast memory: take a block of queries and a block of keys, compute their scores, use them, move on. The trouble is the softmax, the step that turns a row of scores into weights. It divides each exponentiated score by the total over the whole row, and also (for numerical safety) subtracts the row's largest score first. You don't know the total or the maximum until you've seen every key.
The trick is a running tally that can be corrected. Keep, for each query, three things: the biggest score seen so far, the running sum of exponentiated scores, and the running blend of values. When a new block arrives with a bigger maximum, shrink the old sum and old blend by the right factor and add the new block's contribution. At the end, divide by the sum. The answer is exactly the same as doing it all at once, up to rounding.
TakeawaySoftmax can be computed block by block with a correctable running total, so attention can be tiled into fast memory without changing the answer.
Check yourself
- Is FlashAttention an approximation of attention?
- No. It computes exactly the same result as standard attention, differing only by floating-point rounding.
- Why must old totals be rescaled when a larger maximum appears?
- They were computed relative to the old maximum. Multiplying by e(old − new) re-expresses them relative to the new one, so all terms share one reference.
Idea · §3.1 · Recomputation
Recompute rather than store
Training also needs a backward pass, in which the network works out how to adjust itself. Normally the backward pass reads the stored table of attention weights. FlashAttention never stored it. Instead it keeps only the tiny per-row numbers from the running tally (the maximum and the sum), and in the backward pass it recomputes each tile of scores on the chip when needed.
That means doing some arithmetic twice. It sounds wasteful, but arithmetic is cheap and memory traffic is expensive, so it is faster overall. In the paper's measurement for a GPT-2 sized model, FlashAttention did about 13% more arithmetic than standard attention but moved about 9 times less data to and from HBM, and ran about 5.7 times faster.
The memory saved is just as important. The space needed now grows in proportion to the text length instead of its square, which is what allows much longer inputs.
TakeawayDoing a bit more arithmetic to avoid storing and reloading a huge table is a winning trade on modern hardware.
Check yourself
- FlashAttention does more calculations yet runs faster. How?
- The run time was dominated by memory transfers, and it cuts those by roughly an order of magnitude; the extra calculations cost far less than the transfers saved.
Idea · §4 · Tables 1–6
Faster training, longer inputs, better models
The speed-ups were real, end to end, not just for attention in isolation. Training BERT-large to a standard benchmark target was 15% faster than Nvidia's record-setting implementation. GPT-2 trained up to 3 times faster than the widely used Hugging Face code and about 1.7 times faster than Nvidia's Megatron.
Because memory no longer grew with the square of the length, models could take in more text. GPT-2 with four times the usual context (4,096 tokens) trained faster than the standard 1,024-token version under Megatron, and predicted text better. On classifying long medical and legal documents, longer inputs improved accuracy markedly. And a Transformer became the first to do better than chance on "Path-X", a puzzle that requires reading a sequence of 16,000 items, previously out of reach.
TakeawayExact, IO-aware attention made transformers faster to train and, by freeing memory, let them use much longer contexts.
Abstract, restated
Transformers are slow and memory-hungry on long sequences because self-attention is quadratic in time and memory. Approximate methods trade quality for complexity but often give no wall-clock speed-up. The missing principle is IO-awareness: accounting for reads and writes between GPU memory levels. FlashAttention is an exact attention algorithm that uses tiling to reduce reads and writes between HBM and on-chip SRAM. Its IO complexity is analysed, shown to require fewer HBM accesses than standard attention, and shown optimal for a range of SRAM sizes. Extended to block-sparse attention, it gives a faster approximate method. Results: 15% end-to-end speed-up on BERT-large (seq. 512) over the MLPerf 1.1 record, 3× on GPT-2 (seq. 1K), 2.4× on Long Range Arena (1K–4K); longer context gives 0.7 better perplexity on GPT-2 and 6.4 points of lift on long-document classification, and the first better-than-chance Transformers on Path-X (16K, 61.4%) and Path-256 (64K, 63.1%). NeurIPS 2022 (arXiv 2205.14135).
Section · §2 · Algorithm 0
Hardware model and standard attention
Memory hierarchy (§2.1, Fig. 1). A100: 40–80 GB HBM at 1.5–2.0 TB/s; on-chip SRAM of 192 KB per streaming multiprocessor across 108 SMs, at an estimated 19 TB/s. Operations are compute-bound (matmul with large inner dimension) or memory-bound (elementwise ops, reductions: softmax, dropout, masking). Kernel fusion helps memory-bound ops, but in training intermediate values must still be written to HBM for the backward pass.
Standard attention (§2.2). With Q, K, V ∈ ℝN×d: S = QK⊤ ∈ ℝN×N, P = softmax(S) row-wise, O = PV. Algorithm 0 loads Q, K, writes S; reads S, writes P; reads P, V, writes O. Since typically N ≫ d (e.g. GPT-2: N = 1024, d = 64), the Θ(N2) traffic for S and P dominates, and most of the time is spent in memory-bound softmax, masking and dropout rather than in the matmuls.
Section · §3.1 · Algorithm 1
Tiling with online softmax
For a vector x ∈ ℝB, define m(x) = maxi xi, f(x) = [ex1−m(x), …], ℓ(x) = Σi f(x)i, softmax(x) = f(x)/ℓ(x). For a concatenation x = [x(1) x(2)]:
and similarly for f. So keeping two statistics per row (m, ℓ) suffices to combine blocks exactly (the online-softmax normaliser of Milakov & Gimelshein, 2018, here fused with the PV product).
Algorithm 1 (forward), SRAM size M B_c = ⌈M / 4d⌉, B_r = min(⌈M / 4d⌉, d) init in HBM: O = 0 (N×d), ℓ = 0 (N), m = −∞ (N) split Q into T_r = ⌈N/B_r⌉ blocks; K, V into T_c = ⌈N/B_c⌉ blocks for j = 1..T_c: # outer loop: key/value blocks load K_j, V_j to SRAM for i = 1..T_r: # inner loop: query blocks load Q_i, O_i, ℓ_i, m_i to SRAM S_ij = Q_i K_jᵀ # B_r × B_c, on chip m̃ = rowmax(S_ij); P̃ = exp(S_ij − m̃); ℓ̃ = rowsum(P̃) m_new = max(m_i, m̃) ℓ_new = e^(m_i − m_new) ℓ_i + e^(m̃ − m_new) ℓ̃ O_i ← diag(ℓ_new)⁻¹ ( diag(ℓ_i) e^(m_i − m_new) O_i + e^(m̃ − m_new) P̃ V_j ) write O_i, ℓ_i ← ℓ_new, m_i ← m_new to HBM return O
Check yourself
- Why is Bc set to about M/4d?
- SRAM must hold roughly four B × d blocks at once (Qi, Kj, Vj, Oi), so each can have about M/4d rows.
- In this loop order, how many times is each Oi read and written?
- Tc times each, once per key/value block; this is the Θ(TcNd) term that dominates the IO count.
Section · §3.1–3.2 · Theorems 1–2 · Proposition 3
Backward pass and IO complexity
Recomputation. The forward pass stores only O and the statistics (m, ℓ), i.e. O(N) extra memory. The backward pass (App. B) reloads Q, K, V blocks, recomputes Sij and Pij in SRAM from the saved statistics, and accumulates dQ, dK, dV. Dropout masks are regenerated from the saved random-number-generator state rather than stored.
Theorem 1. Algorithm 1 returns O = softmax(QK⊤)V with O(N2d) FLOPs and O(N) additional memory beyond inputs and output.
Theorem 2. With SRAM size M, d ≤ M ≤ Nd, standard attention requires Θ(Nd + N2) HBM accesses; FlashAttention requires Θ(N2d2M−1). For typical d = 64–128 and M ≈ 100 KB, d2 is many times smaller than M.
Proposition 3. No exact attention algorithm can asymptotically improve on this for all M ∈ [d, Nd]: there is no algorithm with o(N2d2M−1) HBM accesses over that whole range.
The paper also shows (Fig. 2 middle and right) that runtime tracks HBM accesses as block size grows, up to a point: beyond block size 256 runtime is bottlenecked by other factors (arithmetic, shared resources).
Check yourself
- Plug in N = 1024, d = 64, M ≈ 100K elements. Roughly what is the ratio of standard to Flash HBM accesses predicted by Theorem 2?
- N2 / (N2d2/M) = M/d2 ≈ 100,000/4,096 ≈ 24, up to constants. The measured 40.3 GB vs 4.4 GB (≈ 9×) is the same order once constants and the backward pass are included.
Section · §3.3 · §4 · Tables 1–6
Block-sparse extension and experiments
Block-sparse FlashAttention (§3.3). Given a block mask, skip zero blocks; Proposition 4 gives Θ(Nd + N2d2M−1s) accesses for nonzero-block fraction s. The experiments use a fixed butterfly sparsity pattern.
| Experiment | Baseline | FlashAttention |
|---|---|---|
| BERT-large, time to 72.0% MLM accuracy, 8×A100 (Table 1) | 20.0 ± 1.5 min (Nvidia MLPerf 1.1) | 17.4 ± 1.4 min |
| GPT-2 small, OpenWebText (Table 2) | HF 9.5 d; Megatron 4.7 d | 2.7 d (3.5× / 1.7×) |
| GPT-2 medium (Table 2) | HF 21.0 d; Megatron 11.5 d | 6.9 d (3.0× / 1.7×) |
| Long Range Arena average (Table 3) | Transformer 59.3 | 59.8 (2.4× faster); block-sparse 59.6 (2.8×) |
| GPT-2 small, context length (Table 4) | Megatron 1K: 18.2 ppl, 4.7 d | 4K: 17.5 ppl, 3.6 d |
| MIMIC-III micro-F1 (Table 5) | 52.8 at 512 tokens | 57.1 at 16K |
| ECtHR micro-F1 (Table 5) | 72.2 at 512 tokens | 80.7 at 8K |
| Path-X (16K) / Path-256 (64K) (Table 6) | chance (50%) for prior Transformers | 61.4 / block-sparse 63.1 |
Table 2 prints speed-ups relative to Hugging Face (Megatron-LM 2.0× and 1.8×; FlashAttention 3.5× and 3.0×), which is about 1.7× over Megatron; the abstract's "3×" is relative to Hugging Face. Benchmarks (§4.3). Attention runtime up to 3× faster than PyTorch at common lengths; memory footprint linear in N and up to 20× smaller than exact baselines, and still about 2× smaller than Linformer at 64K. Approximate methods (Linformer, Performer, Reformer etc.) begin to cross over with exact FlashAttention at sequence lengths between 512 and 1024; block-sparse FlashAttention is faster than all of them at every length tested.
Section · §5 · Lineage
Limitations and what followed
- Authors' limitations (§5). Each new attention variant needs a new hand-written CUDA kernel, a large engineering effort that may not transfer across GPU architectures; the authors hope for a high-level language that compiles to IO-aware kernels. The IO analysis covers a single GPU; multi-GPU IO-awareness is future work.
- Related work. Online softmax: Milakov & Gimelshein (2018). Rabe & Staats (2021) showed attention does not need quadratic extra memory; the paper notes their method still has quadratic HBM accesses, and derives its own backward pass rather than relying on gradient checkpointing. IO complexity analysis follows Aggarwal & Vitter (1988).
- FlashAttention-2 (Dao, 2023): parallelises over the sequence dimension as well as batch and heads, swaps the loop order (queries outer) so each Oi stays on chip, defers the final rescaling, and reduces non-matmul FLOPs; about 2× over v1.
- FlashAttention-3 (Shah, Bikshandi, Zhang, Thakkar, Ramani, Dao, 2024): Hopper-specific asynchrony (TMA, warp specialisation) and FP8.
- Inference. Flash-Decoding applies the same IO-aware ideas to generation; PagedAttention (vLLM, 2023) manages key–value cache memory in pages to cut fragmentation.
- Adoption. Integrated into PyTorch's
scaled_dot_product_attention(PyTorch 2.0), and standard in LLM training stacks. Combined with RoPE context extension, it underlies today's 100K+ token contexts.
Reference
Glossary
- HBM
- High-bandwidth memory: the GPU's large off-chip DRAM (40–80 GB on A100).
- SRAM
- On-chip memory (shared memory / registers), small but about 10× faster.
- SM
- Streaming multiprocessor: one of the GPU's parallel processing units.
- IO complexity
- Number of transfers between memory levels, as opposed to FLOPs.
- Memory-bound
- Run time dominated by data movement rather than arithmetic.
- Kernel fusion
- Combining several operations into one GPU kernel so intermediates stay on chip.
- Tiling
- Splitting matrices into blocks that fit in fast memory.
- Online softmax
- Computing softmax in one pass by rescaling partial sums when the running maximum changes.
- Recomputation
- Recalculating intermediates in the backward pass instead of storing them (a form of checkpointing).