1.6.3
The Flash Attention Algorithm
What is it?
The FlashAttention algorithm divides query rows into blocks and key-value sequences into blocks. It loads these blocks into SRAM, calculates partial attention scores and updates running softmax statistics and output accumulators. Intermediate attention tiles are discarded instead of being written to HBM. During the backward pass, attention information can be recomputed rather than storing the full matrix.
Key points
1. Divide Q into blocks of Br rows.
2. Divide K and V into blocks of Bc rows.
3. Load key and value blocks into SRAM.
4. Load the relevant query block and its running statistics.
5. Calculate the partial score matrix QK transpose divided by the square root of the key dimension.
6. Apply the online softmax update.
7. Update the output accumulator and running statistics.
8. Discard the intermediate attention tile.
9. Return the accumulated output after all blocks have been processed.
10. The backward pass can recompute attention rather than storing the complete attention matrix.
Example: The forward-pass workflow
Simplified algorithm:
1. Split Q, K and V into blocks.
2. Initialize output O, running maximum m and running sum l.
3. Load a K/V block into SRAM.
4. Process each relevant Q block.
5. Calculate attention scores.
6. Update m, l and O using online softmax.
7. Write the updated accumulators as required.
8. Continue until all blocks are processed.
The intermediate attention score tile stays in SRAM and is discarded after use.
Real-world application
This algorithm is useful for efficient Transformer training, especially when long sequences make conventional attention memory-intensive.
Key takeaway
FlashAttention keeps intermediate attention tiles on-chip, updates the result incrementally and avoids writing the full attention matrix to HBM.