Flash Attention Algorithm Overview
What you'll learn: How Flash Attention computes exact attention efficiently by cleverly organizing memory access without creating the massive intermediate attention matrix.
The Core Problem
Standard attention computes a full N × N attention matrix (where N is sequence length), materializing it in GPU memory before applying softmax and multiplying with values. For long sequences, this matrix is enormous—a 4K sequence requires ~64MB just for attention weights, and 16K sequences balloon to 1GB per layer.
The Flash Attention Solution
Flash Attention uses two key techniques:
Tiling (Blocking)
Instead of computing the entire attention matrix at once, Flash Attention divides queries, keys, and values into blocks (tiles). It loads one tile of queries and one tile of keys from slow HBM (high-bandwidth memory) into fast SRAM, computes their partial attention scores, then moves to the next tile.
Think of it like reading a book chapter-by-chapter instead of photocopying the entire book first—you process small pieces sequentially without needing space for everything at once.
Kernel Fusion
Flash Attention fuses the attention operations (QK^T, softmax, multiply by V) into a single GPU kernel. Traditional implementations write intermediate results back to HBM between operations. Fusion keeps intermediate values in fast SRAM registers, dramatically reducing memory reads/writes.
The Mathematical Trick
The algorithm uses an online softmax technique that incrementally updates softmax statistics as it processes tiles, ensuring the final result is mathematically identical to standard attention—it's not an approximation.
Key Takeaway: Flash Attention achieves exact attention with sub-quadratic memory by tiling operations across GPU memory hierarchy and fusing kernels, making it IO-aware rather than compute-bound—essential for efficient long-context LLM inference.