FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness
- Publication
- NeurIPS 2022Conference
- First submitted to arXiv
- arXiv:2205.14135
Cite this paper · BibTeX
The citation identifies the linked source version. It cites the original paper and its authors.
@misc{transformersflashattention2022,
title = {{FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness}},
author = {Tri Dao and Daniel Y. Fu and Stefano Ermon and Atri Rudra and Christopher Ré},
year = {2022},
eprint = {2205.14135},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2205.14135}
}
When writing code, our intuition is to store a computed result and reuse it next time, since that should be cheaper than calculating it again.
On a GPU, why does that intuition suddenly seem less reliable?
The GPU computes quickly, but storing a result in memory and reading it back also takes time. Sometimes moving the data takes longer than doing the calculation again!
The authors of this paper noticed that problem in attention. They split the calculation into small tiles to reduce data transfers; when the backward pass needs an intermediate result, they recompute it in the GPU's fast on-chip memory.
Yes, you read that right!
Calculate it, discard it, and calculate it again when needed.
The problem
Start with the figure below. Four positions scoring one another make a cell table; eight positions make an cell table. Double the length, and the table has four times the area. The figure shows one sample and one attention head; for now, think of a “head” as one independent set of vectors used to score positions.
Each row records how one position scores the whole sequence. Softmax then turns each score into ( is about 2.718) and divides it by the sum of across that row. The weights now add up to 1, with higher-scoring positions receiving more weight in the output.
A conventional implementation writes the full score table to the GPU's large memory, HBM, reads it back for softmax, and writes the weight table back. At sequence length 2048, just one table for one head contains over four million cells, about 8 MiB (8.4 MB) at half precision. Multiple heads and samples multiply the amount of data.
The GPU also has on-chip SRAM. It is much smaller, but feeds data to the arithmetic units much faster. The authors want to bring only the tile being processed into SRAM, finish it, and move on without sending the complete score and weight tables through HBM.
But softmax requires every position in a row to share the same denominator. Suppose we normalize the first half of a row so its weights add up to 1. A larger score appears in the second half. How do we revise the first half?
The method
Meet the three matrices
Inside an attention layer, each position has three vectors. holds queries that look for information, holds keys to compare against them, and holds the content to combine using the resulting weights. With positions and vector width per head, dense attention is
Along one row, a query scores every key; division by keeps scores from tending to grow as the vectors gain dimensions; softmax turns the scores into weights; and those weights produce a weighted average of the values. is the output. The expensive intermediates are and , each with cells.
FlashAttention splits into tiles. The paper's Figure 1 shows the arrangement:
is on the left, above, and on the right. An orange square is the tile currently loaded into SRAM; the dotted box marks the attention table that need not be written in full to HBM. The red arrows move through tiles, and the blue arrows through tiles. Each encounter computes a small patch of scores and updates the output. Every query still meets every key. What disappears is storing and moving the full intermediate table, not the pairwise calculations.
Four scores, two passes
Suppose one row of scores, already divided by , is . One dimension of the corresponding values is . Looking at all four positions together gives
Now process the first two positions and the last two separately. To keep from growing too large, subtract each tile's maximum score first. Subtracting the same number from every score in a group scales softmax's numerator and denominator together, leaving the answer unchanged. We only need to keep the maximum , the sum of exponentials , and the weighted sum before division by .
On the left, subtract 3 from . The exponential terms become , so . With values , we get . On the right, subtract 4 from . Again , but with values we get .
Both tiles are correct on their own, yet we cannot simply add their values. The left tile uses 3 as its reference; the right uses 4. Adding them directly would treat their top scores as equal. Use 4 as a common reference instead, multiplying the left tile's and by :
We recover the same as the full-row calculation. If a third tile arrives, treat the current as a summary of all previous tiles and update it the same way. That is online softmax, which lets separate tiles share one final denominator without storing the entire row of scores. Real values have dimensions, so is a vector, but the information carried per row remains far smaller than the full table.
During training, calculate it again
The forward pass goes from input to output without saving the full weight table . Training also has a backward pass, which works out how to adjust the model's parameters and needs the attention weights again. When FlashAttention reaches a tile during backward, it recomputes that tile from and the normalization information kept from forward.
Now return to that opening intuition. Recomputation adds arithmetic, but avoids writing all of to HBM and reading it back. The paper's Theorem 2 expresses the trade in memory accesses. Standard attention needs , while the tiled algorithm needs . is the number of values SRAM can hold, with . The symbol describes how a quantity grows as the input grows, ignoring fixed multipliers.
The formula suggests we can move less data, but does the whole operation actually finish sooner?
Discussion
More arithmetic, less waiting
Look at the left panel of Figure 2. On an A100, the authors measured attention's combined forward and backward passes at sequence length 1024, with vector width 64 per head, 16 heads, batch size 64, a padding mask and no dropout.
| Figure 2 | Standard attention | FlashAttention |
|---|---|---|
| Arithmetic | 66.6 GFLOPs | 75.2 GFLOPs |
| HBM reads and writes | 35.3 GB | 4.4 GB |
| Time | 35.1 ms | 11.7 ms |
GFLOPs counts billions of floating-point operations, GB measures the data moved, and ms is one thousandth of a second. Read in order, the rows show arithmetic increasing about 13%, HBM traffic falling to about one eighth, and time falling from 35.1 to 11.7 ms. The time saved on transfers more than pays for the recomputation.
The middle panel shows that increasing tile size from 64 to 256 generally reduces both traffic and time. At 512, time no longer falls at the same rate. SRAM capacity and the way work is scheduled on the GPU both matter when choosing a tile size.
What happens as the sequence grows? In the paper's Figure 3, the left panel measures time and the right measures attention memory:
On the right, FlashAttention's memory curve rises roughly in a straight line with sequence length, while the conventional intermediate table grows with . In the measured settings, attention memory differs by as much as 20-fold. Time still rises quickly on the left because no query-key pairs have been removed. The brown line stretching to 64K on the right is Linformer, a separate approximate method; it is not standard dense attention.
If attention gets faster, how much faster is the full model? The paper's Table 1 offers one answer for BERT-large:
Time to the same training target falls from to minutes. The model has other layers to compute, so the whole training run improves less than the attention kernel alone. This comparison gives the Figure 2 result a place in a real model.
Does another GPU give the same answer?
We also tried an RTX 4090. On the same card and with the same attention inputs, one version uses PyTorch eager's three steps and the other uses the v1.0.9 Triton tiled forward kernel; only sequence length changes. The settings are fp16, batch size 2, eight heads of width 64, no mask or dropout. After warm-up, timing is the median of 30 runs. Extra memory is counted after have been allocated.
| Sequence length | PyTorch eager | Tiled kernel | Speed ratio | Extra peak: eager / tiled |
|---|---|---|---|---|
| 512 | 0.0501 ms | 0.0781 ms | 0.64× | 18.0 / 1.06 MiB |
| 1024 | 0.1341 ms | 0.1044 ms | 1.28× | 68.0 / 2.13 MiB |
| 2048 | 0.9533 ms | 0.2007 ms | 4.75× | 264.0 / 4.25 MiB |
At 512 positions, tiling is slower. By 2048, avoiding the large table outweighs the cost of tiling. These numbers cover forward only; the paper's experiments are where we look for backward and full-model training results.
Conclusion
Looking back at the first generation, two design choices are especially useful to learn from.
First, the amount of arithmetic does not determine speed on its own. In the paper's A100 experiment, FlashAttention performs about 13% more arithmetic, yet the combined forward and backward attention time drops from 35.1 ms to 11.7 ms, roughly a third of the original. The key is that HBM traffic falls from 35.3 GB to 4.4 GB. Doing a little more calculation to move much less data pays off.
Second, an intermediate result can be recalculated when needed. Online softmax combines the results of separate tiles correctly. During the backward pass, the output and softmax statistics retained from the forward pass let us recompute the needed attention weights in SRAM, without storing the entire weight table. Attention still calculates every pair; changing the order of work and what gets saved improves both speed and memory use.
The first generation still leaves some GPU capacity unused. Scaling and normalization during softmax updates involve non-matrix operations that can be reduced. Work is assigned mainly across batches and heads, so with few of either, parts of the GPU may sit idle. Even within one thread block, different warps exchange and combine intermediate results through shared memory, paying for extra reads, writes, and synchronization.
Now that data moves less, can we divide the work better so the GPU spends less time waiting and more time computing?
Let's have a cup of coffee and come back for the next chapter.