← Roadmap

FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness

Dao, Fu, Ermon, Rudra, Ré · 2022

① 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?

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?

Retrieval check

What is the key hardware constraint that motivates FlashAttention's tiling approach?
FlashAttention is described as 'IO-aware'. What does IO-awareness mean in this context?

Answer all 2 correctly to mark this stage mastered.

② Math

Standard attention computes:

S=QK⊤d,P=softmax(S),O=PVS = \frac{QK^\top}{\sqrt{d}}, \quad P = \text{softmax}(S), \quad O = PV

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:

mnew=max⁡(m,  max⁡jSblock,j)m_\text{new} = \max(m,\; \max_j S_{\text{block},j})lnew=em−mnew l    +    ∑jeSblock,j−mnewl_\text{new} = e^{m - m_\text{new}} \, l \;\;+\;\; \sum_j e^{S_{\text{block},j} - m_\text{new}}Onew=l⋅em−mnewlnew O    +    1lnew∑jeSblock,j−mnewVblock,jO_\text{new} = \frac{l \cdot e^{m - m_\text{new}}}{l_\text{new}} \, O \;\;+\;\; \frac{1}{l_\text{new}} \sum_j e^{S_{\text{block},j} - m_\text{new}} V_{\text{block},j}

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.

Why does online softmax subtract the running max m_new from the exponent rather than computing exp(S_block) directly?
Show next line
Stability: exp⁡(si−m)∈(0,1] when m=max⁡isi, avoiding float overflow\text{Stability: } \exp(s_i - m) \in (0, 1] \text{ when } m = \max_i s_i, \text{ avoiding float overflow}
What is the HBM memory saving from never materialising S? (N=sequence length, d=head dimension)
Show next line
Naive: O(N2) HBM writes    →    Flash: O(Nd)    ⇒    saving∝Nd\text{Naive: } O(N^2) \text{ HBM writes} \;\;\to\;\; \text{Flash: } O(Nd) \;\;\Rightarrow\;\; \text{saving} \propto \frac{N}{d}

Retrieval check

In the online softmax update, what role does the factor e^(m - m_new) play?
FlashAttention recomputes tile scores during the backward pass rather than storing them. Why?

Answer all 2 correctly to mark this stage mastered.

③ Pseudo code

Arrange the five steps of the FlashAttention forward pass in the correct order:

  1. Outer loop: for each Q-block q_i (rows i*B to (i+1)*B of Q)
  2. 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))
  3. 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
  4. After all K/V blocks, write final O-block to HBM
  5. 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_new

Retrieval check

In the FlashAttention tiling loop, which values stay in SRAM throughout the inner loop, and which are read from / written to HBM only once?

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

Why does the online_softmax_update function initialise m to -inf and l to 0 before the first block?

Answer all 1 correctly to mark this stage mastered.

⑤ Original paper

Your browser can't embed PDFs. Download FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness (Dao et al. 2022).

Open in new tab · Download

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).