① Intuition
Standard attention is quadratic in sequence length — both in compute and in memory. But the memory bottleneck is subtler than it first appears. A modern GPU has two kinds of storage: High Bandwidth Memory (HBM), which on an A100 holds ~40 GB but has relatively high latency; and on-chip SRAM (shared memory), which is extremely fast but totals only ~20 MB spread across all streaming multiprocessors. When naive attention computes the N×N score matrix S = QK^T, it writes all N² values to HBM so that softmax can read them back. For N=8192 and 32-bit floats, that is 256 MB written and then re-read — a round trip to slow memory, repeated every layer.
FlashAttention (Dao et al., 2022) reframes the problem as an IO-aware algorithm. Instead of asking “what is the minimal flop count?” it asks “how do we minimise HBM reads and writes?” The answer is tiling: divide Q, K, and V into blocks small enough to fit in SRAM simultaneously. Within each tile, compute partial scores, maintain running statistics (max m and normalizer l) to fuse the numerically-stable online softmax, and accumulate the output O — all without touching HBM. The full N×N score matrix is never materialised. The result is mathematically exact (no approximation), 2–4× faster wall-clock, and uses O(N) instead of O(N²) HBM memory.
Before using the widget: if the N×N score matrix never touches HBM, what is the dominant HBM cost for FlashAttention, and how does it scale with N?
Without materialising S, the only values written to HBM are Q, K, V (each N×d) and the final output O (N×d). That is 4Nd elements — linear in N. The naive approach writes N² elements just for the score matrix. For N=8192 and d=64, the naive HBM cost is ~67M elements vs. flash’s ~2M — a 32× reduction in this component alone.
Interact with the widget: choose different sequence lengths N and tile sizes B. Observe how the savings ratio grows quadratically as N increases. Also watch the SRAM-per-tile value — once it exceeds 192 KB the widget warns you that the tile is too large for one A100 SM’s shared memory and the kernel cannot run.
Naive I/O (log₁₀)
6.10
= 1,245,184 elements
Flash I/O (log₁₀)
5.42
= 262,144 elements
Savings ratio
4.8×
naive / flash I/O
SRAM per tile
48.0 KB
3 × B × d × 4 bytes
d = 64 (fixed head dim). Naive materializes N×N attention matrix in HBM; FlashAttention keeps intermediates in SRAM tiles of size 64×64.
After exploring the widget: at N=8192 with tile B=64 the savings ratio is large, and SRAM per tile is well under 192 KB. What happens if you increase B to 256 at N=8192, and why does that matter for kernel design?
At B=256 the SRAM per tile grows to 3 × 256 × 64 × 4 bytes = 196 KB, which exceeds the 192 KB limit and triggers the warning. A real CUDA kernel at this tile size would overflow shared memory, causing a runtime error or silent register spilling. Kernel writers therefore choose B to stay just under the SRAM budget — a hardware-aware parameter that directly constrains the algorithm.
Retrieval check
Answer all 2 correctly to mark this stage mastered.
② Math
Standard attention computes:
For a row of S with values s_1, …, s_N, the numerically stable softmax subtracts the row maximum m = max(s_i) before exponentiation: P_i = exp(s_i - m) / sum_j exp(s_j - m). Naive attention must read the entire row to find m, then read it again to compute the exponentials — two HBM passes over N² elements.
Online softmax fuses these two passes into one by maintaining running statistics. Given a new block of scores S_block, update the running max m and normalizer l:
The factor e^(m - m_new) rescales the old statistics whenever the running max is updated by a new block. After processing all blocks, O holds the exact same result as the two-pass softmax.
Show next line
Show next line
Retrieval check
Answer all 2 correctly to mark this stage mastered.
③ Pseudo code
Arrange the five steps of the FlashAttention forward pass in the correct order:
- Outer loop: for each Q-block q_i (rows i*B to (i+1)*B of Q)
- Update running max and normalizer: m_new = max(m, rowmax(S_ij)); l_new = rescale(l, m, m_new) + rowsum(exp(S_ij - m_new))
- Inner loop: for each K/V-block (k_j, v_j) — compute tile scores S_ij = q_i * k_j^T / sqrt(d) in SRAM
- After all K/V blocks, write final O-block to HBM
- Update output accumulator: O_new = rescale(O, m, m_new) + exp(S_ij - m_new) * v_j / l_new
Fill in the blank — the online softmax running-max update used inside the inner loop:
def flash_inner(m, l, O, S_block, V_block):
m_new = _______
scale = exp(m - m_new)
l_new = scale * l + rowsum(exp(S_block - m_new))
O_new = scale * O + matmul(exp(S_block - m_new), V_block) / l_new
return m_new, l_new, O_newRetrieval check
Answer all 1 correctly to mark this stage mastered.
④ Code (Python)
Implement the online softmax accumulation step in NumPy. Given the current running state (m, l, O) and a new block of raw (unscaled) attention scores S_block (shape B_q x B_k) and V_block (shape B_k x d), compute and return the updated (m_new, l_new, O_new).
Retrieval check
Answer all 1 correctly to mark this stage mastered.
⑤ Original paper
Suggested reading order: §1 (Introduction — the IO bottleneck and motivation for tiling) → §3.1 (IO Complexity — formal proof that FlashAttention reduces HBM reads/writes from O(Nd + N²) to O(N²d/M) where M is SRAM size) → §3.2 (FlashAttention Algorithm — the full tiled forward and backward pass pseudocode).