1.6.2
Tiling and Online Softmax: The Key Insight
What is it?
FlashAttention uses tiling and online softmax to calculate attention without storing the complete attention matrix in high-bandwidth memory. Query, key and value tensors are processed in blocks that fit in fast on-chip SRAM. Running statistics allow softmax and the output to be updated as each new block is processed.
Key points
1. Tiling divides Q, K and V into smaller blocks.
2. Blocks are transferred into fast on-chip SRAM.
3. Attention scores are calculated for the current blocks.
4. Online softmax maintains a running maximum and normalization sum.
5. When a new block arrives, previous results are rescaled using the updated maximum.
6. The output is accumulated incrementally.
7. The full attention matrix is never required in HBM.
8. The online update is mathematically equivalent to full softmax computation.
Example: Processing attention in blocks
Imagine processing a long sequence using four key-value blocks.
Block 1: Calculate partial attention and initialize running statistics.
Block 2: Update the running maximum, normalization sum and output.
Block 3: Rescale previous contributions and add the new block contribution.
Block 4: Complete the accumulated output.
The model does not need to store the entire attention matrix at once.
Real-world application
Tiling and online softmax are useful in long-context training and inference because they reduce intermediate memory requirements and expensive memory transfers.
Key takeaway
FlashAttention processes attention block by block and uses online softmax to produce the mathematically equivalent result without materializing the full attention matrix.