FlashAttention: Why Attention Is a Memory Problem in Disguise

Attention gets described as an O(N²) algorithm, and that description is simultaneously correct and misleading. Yes, the score matrix between every pair of tokens has N² entries. But on a modern GPU, the math is almost free — matrix multiplication throughput has exploded over five generations of hardware — while the memory bandwidth that feeds the math has crawled. The reason your transformer is slow is not that attention computes too much. It is that the naive implementation moves gigabytes of data that never needed to leave the chip.

FlashAttention is the fix, and its insight is worth internalizing because it generalizes far beyond attention: on accelerators, memory traffic is the budget, and algorithms should be designed around the memory hierarchy, not the FLOP count. This post walks through why standard attention wastes bandwidth, how tiling and online softmax eliminate the waste without changing the output, and how the technique evolved across four hardware generations.

The Memory Hierarchy Sets the Rules

A data-center GPU has two memory tiers that matter. High-bandwidth memory (HBM) is large — 80 GB and up — but relatively slow to reach, on the order of 2–8 TB/s depending on the generation. On-chip SRAM is tiny — about 192 KB per streaming multiprocessor, roughly 20 MB in total on an A100-class part — but roughly an order of magnitude faster. Everything a kernel computes must be hauled from HBM into SRAM, transformed, and written back.

Attention at a sequence length of 4096 and batch 8, with 32 heads in half precision, produces a score matrix of 8 × 32 × 4096 × 4096 × 2 bytes ≈ 8 GB. That is the intermediate output of one matmul, written to HBM, then read back for the softmax, written again, read back for the second matmul, and finally written to HBM a third time as the output. The N² intermediate S and P matrices dominate memory traffic and are the reason peak memory grows quadratically with sequence length — at 32K tokens, the same tensors would need hundreds of gigabytes.

Tiling: Keep the Intermediates On-Chip

The fix starts by noticing that no single output element of attention needs the whole score matrix at once. Each output row is a weighted sum over values, with weights from one query row’s scores. So you can compute attention in blocks small enough to fit entirely in SRAM: load a block of queries, iterate over blocks of keys and values, and keep every intermediate — score tile, softmax tile, partial output — on-chip from first touch to last use.

This is kernel fusion taken to its logical conclusion. Instead of three kernels with HBM round-trips between them, one kernel does the whole computation, touching HBM once to read Q, K, V and once to write the output. The full N×N matrix never exists anywhere, in HBM or in SRAM. Memory traffic drops from O(N² + Nd) to O(N²d / M), where M is the SRAM size — and memory becomes linear in sequence length, because only the output is stored.

There is a catch, and it is the interesting part of the algorithm. Matrix multiplication tiles cleanly because addition is associative — partial sums can accumulate in any order. Softmax does not. The numerically stable softmax of a row needs the row’s global maximum and the sum of exponentials over the entire row before any output can be finalized. When you process the row in tiles, you do not have those statistics yet. The naive workaround — two passes over the data to collect statistics first — would defeat the purpose. The solution is to compute softmax statistics incrementally as the tiles arrive.

Online Softmax: Statistics That Correct Themselves

Online softmax maintains a running maximum m and a running sum of exponentials l for each query row. When a new score tile arrives, three things happen: the maximum may increase, the accumulated sum must be rescaled by how much the maximum moved, and the new tile’s contributions are added. Any partial output computed so far gets rescaled by the same correction factor.

import torch

def flash_attn_fwd(q, k, v, Bc=64):
    """Exact attention via tiling + online softmax (single pass).
    q: (n_q, d), k: (n_k, d), v: (n_k, d)."""
    n_q, d = q.shape
    m = torch.full((n_q,), float("-inf"))   # running max per query row
    l = torch.zeros(n_q)                    # running sum of exp
    acc = torch.zeros(n_q, v.size(-1))      # unnormalized output accumulator

    for kb in range(0, k.size(0), Bc):
        k_tile, v_tile = k[kb:kb+Bc], v[kb:kb+Bc]
        scores = q @ k_tile.T / d ** 0.5    # (n_q, Bc) — small tile, on-chip
        m_new = torch.maximum(m, scores.amax(dim=-1))
        correction = torch.exp(m - m_new)   # rescale everything seen so far
        p = torch.exp(scores - m_new.unsqueeze(-1))
        l = l * correction + p.sum(-1)
        acc = acc * correction.unsqueeze(-1) + p @ v_tile
        m = m_new

    return acc / l.unsqueeze(-1)            # final normalization

The rescaling factor exp(m_old - m_new) shrinks all previous work by exactly the right amount, so once the last tile has been processed, the accumulated result is mathematically identical to standard softmax computed on the full row — same output, computed in a single pass, with the exponentials always taken against a current max, which also keeps the computation numerically safe for long sequences.

Recomputation: Buying Back Bandwidth With Cheap FLOPs

The forward pass saves memory by never storing the N×N probability matrix. The backward pass needs those probabilities to compute gradients. Storing them would undo the memory win, so instead the backward pass recomputes the score and probability tiles from the stored Q, K, V and the saved softmax statistics. This trades extra FLOPs — the backward pass does roughly 2.5× the tensor-core work of the forward pass, with recomputation supplying the extra chunk — for a massive reduction in HBM traffic. Because attention on modern hardware is bandwidth-bound, not compute-bound, spending arithmetic to avoid memory movement is a clear net win, and wall-clock speedups of 2–4× over the naive fused-in-PyTorch implementation were reported for realistic model sizes, alongside the jump from quadratic to linear memory.

From FlashAttention to FlashAttention-4

The algorithm has been retuned once per GPU generation, and the retuning history is a map of where hardware bottlenecks moved:

  • FlashAttention (2022) established the tiling and online-softmax formulation and proved the IO bound: for a wide range of SRAM sizes, no exact-attention algorithm can touch HBM fewer times.
  • FlashAttention-2 (2023) attacked work partitioning. The first version parallelized across batch and heads, leaving many streaming multiprocessors idle at long sequence lengths, and wasted effort on non-matmul operations like exponentials and rescaling. The sequel parallelizes across the sequence dimension too and strips non-matmul work, roughly doubling throughput on A100-class parts.
  • FlashAttention-3 (2024) targeted Hopper’s asynchronous units: warp-specialized producer/consumer pipelines overlap data movement with tensor-core math, and the FP8 path pushed attention past 700 TFLOPs in FP16 and close to 1.2 PFLOPs in FP8 on H100.
  • FlashAttention-4 (2026) moves to Blackwell, where compute now so far outpaces the non-matmul units (transcendentals, rescaling) that the softmax itself became the bottleneck. The kernel pipelines the exponential work, is written in a Python-embedded DSL that compiles roughly 20–30× faster than the older C++ template stack, and lands around 1.3× over the vendor cuDNN kernel and 2.7× over Triton on B200, with backward passes exceeding 1,400 TFLOPs at long sequence lengths.

The pattern across all four: the core algorithm has not changed since the first paper. What changes is how aggressively the kernel hides memory latency and feeds the tensor cores for each new silicon generation.

Using It in Practice

If you use PyTorch, you get fused attention without installing anything: scaled_dot_product_attention dispatches to a fused kernel when shapes and hardware allow it. The naive formulation for comparison:

import torch
import torch.nn.functional as F

# Naive: materializes S (N×N) and P (N×N) in HBM. Quadratic memory.
def attention_naive(q, k, v):
    d = q.size(-1)
    scores = q @ k.transpose(-2, -1) / d ** 0.5   # (B, H, N, N)
    p = F.softmax(scores, dim=-1)                 # another (B, H, N, N)
    return p @ v

# Fused: one call, dispatches to a FlashAttention-class kernel
def attention_fast(q, k, v):
    return F.scaled_dot_product_attention(q, k, v)

Standalone libraries add knobs the fused PyTorch path does not expose — deterministic backward passes, block-level sparsity, paged KV layouts for inference serving, and sliding-window or ALiBi-style attention masks. When in doubt, benchmark with your real shapes: for short sequences the win is modest, and the quadratic blow-up that makes fused attention mandatory only asserts itself in the thousands-of-tokens range and beyond.

The takeaway generalizes. When a kernel is slow, profile the data movement before profiling the math. The FlashAttention paper formalized the IO-complexity argument (second, third, and fourth installments document the per-generation retuning), and the reference implementation lives in the flash-attention repository. The next time a compute routine feels irreducibly quadratic, ask the FlashAttention question: does any single output element actually need the full quadratic intermediate at once? Very often, the answer is no — and the algorithm you need is the same one, just reorganized around the memory hierarchy.

Leave a Reply

Your email address will not be published. Required fields are marked *