Study guide · Language models & AI · 2022

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

Tri Dao, Daniel Fu, Stefano Ermon, Atri Rudra, Christopher Ré · NeurIPS 2022

Attention was slow and memory-hungry on long inputs, and most attempts to fix it computed a cheaper approximation. Dao and colleagues noticed that the real bottleneck on a GPU is not the arithmetic but moving a huge table of scores in and out of slow memory. FlashAttention computes exactly the same answer in small tiles that never leave the chip's fast memory, making attention several times faster and letting models read much longer texts.

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.

The sliders are powers of two (N = 2slider tokens; copies = 2slider, e.g. 8 sentences × 16 heads = 128). Bars, on a log scale: the score table for one head of one text (N × N numbers at 2 bytes each), the same for all copies, the A100's on-chip memory (about 20 MB in total, but only 192 KB in each of its 108 processing units) and its HBM (40 GB). The time estimate assumes standard attention writes and reads both the score table and the weight table once each at 1.5 TB/s, the HBM speed in the paper's Fig. 1.
Everyday pictureA chef with a tiny worktop and a big pantry down the hall. The chef chops very fast, but if every recipe step means carrying everything back to the pantry and fetching it again, most of the evening is spent walking. The fix isn't a faster knife; it's organising the work so ingredients stay on the worktop.

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.

One query's 12 scores against 12 keys, each key carrying a value (a single number here). The scores are processed in blocks of 4, as FlashAttention processes key blocks. After each block, the running maximum m, running sum ℓ and running unnormalised output are updated, with old totals rescaled by e(old m − new m) whenever the maximum grows. The last line compares the result with ordinary softmax over all 12 at once.
Everyday pictureTallying an exam where marks will be scaled so the top score is 100. You don't need to wait for all papers: keep a running total scaled to the best so far, and whenever a new paper beats the best, rescale your running total once. The final numbers match marking everything at the end.

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.

Later refinementFlashAttention-2 (Dao, 2023) reorganised the work across the GPU's processing units and cut non-matrix arithmetic, roughly doubling speed again; FlashAttention-3 (2024) exploited features of newer Nvidia chips. The approach is now built into PyTorch and most training and serving software, so most large language models use it without anyone thinking about it.

TakeawayExact, IO-aware attention made transformers faster to train and, by freeing memory, let them use much longer contexts.

Follow the idea

Built on: Transformer (2017)