1. Introduction

Transformer attention computes

O=softmax⁡ ⁣(QK⊤d)V, O = \operatorname{softmax}\!\left(\frac{QK^\top}{\sqrt{d}}\right)V,

where QQ, KK, and V∈RN×dV \in \mathbb{R}^{N \times d}, NN is the sequence length, and dd is the head dimension. The factor 1/d1/\sqrt{d} scales the dot products before softmax. This formulation suggests a straightforward implementation: compute the score matrix S=QK⊤/dS=QK^\top/\sqrt{d}, apply row-wise softmax to obtain PP, and compute O=PVO=PV.

The straightforward implementation is inefficient because both SS and PP contain N2N^2 elements. Each intermediate is written to HBM and read by a subsequent kernel. GPU tensor cores can compute the matrix products rapidly, but the intermediate traffic repeatedly crosses a much slower memory interface.

FlashAttention is based on one systems observation:

The kernel computes one score tile in on-chip SRAM, immediately incorporates it into a running softmax and output, and then discards it. This reordering computes the same attention function with substantially less memory traffic.

2. Background

2.1 GPU memory hierarchy

GPUs expose a large HBM capacity and a much smaller on-chip storage hierarchy composed of registers and shared memory. HBM holds model state and activations but has much lower bandwidth relative to the arithmetic rate of tensor cores. Shared memory is fast enough to feed matrix-multiply units, but only a small tile of the working set fits at one time.

This asymmetry makes data movement a first-class algorithmic cost. An implementation with the minimum number of floating-point operations can still underperform if it repeatedly materializes large intermediates in HBM.

2.2 Conventional attention

A conventional implementation launches separate kernels for three stages:

S=QK⊤d,P=softmax⁡(S),O=PV. S = \frac{QK^\top}{\sqrt{d}}, \qquad P = \operatorname{softmax}(S), \qquad O = PV.
Three separately launched kernels with the score and probability matrices written to and reread from HBM between them.
Figure 1. Conventional attention as three kernel launches. Amber marks a kernel; gray marks tensors whose size is linear in the sequence length; red marks the two quadratic intermediates that are written to HBM and read back, which is the traffic FlashAttention removes.

The inputs and output require Θ(Nd)\Theta(Nd) storage, whereas each intermediate requires Θ(N2)\Theta(N^2) storage. For long sequences, the quadratic traffic dominates.

For example, with N=16,384N=16{,}384 and d=128d=128, each of QQ, KK, and VV contains approximately 2.1 million elements. The score matrix contains approximately 268 million elements. The principal problem is not that these scores must be computed; it is that a conventional schedule writes and rereads them.

The consequence is visible without any timing at all. Running the same attention over the same tensors, once with the two intermediates materialized and once through a fused kernel, and recording peak allocated memory:

Sequence lengthConventional: eager (reference)Fused: SDPA cuDNN (SM100)Ratio (eager / cuDNN)
51256 MB46 MB1.2×
2,048336 MB88 MB3.8×
8,1924,368 MB256 MB17.1×
Log-log plot of peak allocated memory against sequence length. The gray eager curve rises much faster than the green SDPA cuDNN curve; other backends are also shown.
Figure 2. Peak allocated memory against sequence length, on log-log axes. The table compares the gray eager (reference) curve with the green SDPA cuDNN (SM100) curve. Their widening separation shows the cost of materializing the quadratic intermediates; the other plotted backends are not part of this comparison.

This is a memory comparison, not a speed measurement. The widening gap matters more than any one ratio: the conventional path stores two N×NN \times N intermediates, while the fused path does not.

2.3 Numerically stable softmax

For one score row xx, stable softmax is

softmax⁡(x)i=exi−m∑jexj−m,m=max⁡jxj. \operatorname{softmax}(x)_i = \frac{e^{x_i-m}}{\sum_j e^{x_j-m}}, \qquad m=\max_j x_j.

Subtracting the row maximum prevents exponential overflow. The apparent obstacle to tiling is that both the maximum and normalization sum depend on the complete row.

3. The fused alternative

Tiling either matrix multiplication alone does not solve the problem. A tuned GEMM can efficiently produce SS, but if SS is subsequently written to HBM, consumed by a softmax kernel, and written again as PP, the implementation retains the dominant traffic.

The optimization boundary must therefore include the full operator:

A query tile and streamed key-value blocks feeding an on-chip loop of score tile, online-softmax update, and running output, with the output written to HBM once.
Figure 3. The fused alternative. The green region stays in registers and shared memory: for every key block the kernel forms a score tile, folds it into the running softmax statistics, and updates the accumulator. Only the final output returns to HBM.

This produces two requirements:

  • The score and probability tiles must remain on chip and never become global intermediates.
  • Softmax statistics computed from separate key blocks must be merged exactly.

The second requirement is the key algorithmic problem solved by FlashAttention.

4. Design

4.1 Tiled execution

Partition the query matrix into row blocks QiQ_i and the key and value matrices into blocks KjK_j and VjV_j. For each query block, the kernel scans all key/value blocks:

  1. Load QiQ_i, KjK_j, and VjV_j into on-chip storage.
  2. Compute the score tile Sij=QiKj⊤/dS_{ij}=Q_iK_j^\top/\sqrt{d}.
  3. Merge SijS_{ij} into the running softmax statistics for QiQ_i.
  4. Accumulate the weighted values into the running output OiO_i.
  5. Discard SijS_{ij} and proceed to the next key/value block.

Only the final OiO_i is written to HBM.

4.2 Online softmax

For one query row, maintain three quantities after processing some key blocks:

  • mm: the largest score observed so far;
  • ℓ\ell: the sum of exponentials relative to mm;
  • zz: the unnormalized weighted-value sum relative to mm.

For a new score block ss with corresponding value block VjV_j, compute

m~=max⁡(s),m′=max⁡(m,m~). \tilde m = \max(s), \qquad m' = \max(m, \tilde m).

The previous state was expressed relative to mm, whereas the merged state must be expressed relative to m′m'. Rescale the old contribution and add the new block:

ℓ′=em−m′ℓ+∑kesk−m′, \ell' = e^{m-m'}\ell + \sum_k e^{s_k-m'},
z′=em−m′z+∑kesk−m′Vj,k. z' = e^{m-m'}z + \sum_k e^{s_k-m'}V_{j,k}.

After all blocks have been processed,

O=zℓ. O = \frac{z}{\ell}.

This recurrence is exact in real arithmetic. Every old exponential is converted from the old reference maximum to the new one because

ex−mem−m′=ex−m′. e^{x-m}e^{m-m'} = e^{x-m'}.

4.3 Worked example

4.4 IO complexity

FlashAttention chooses tile sizes so the active Q, K, V, score, and output tiles fit on chip. The score and probability matrices are never written out in full. The original paper analyzes how much HBM traffic this saves as the on-chip tile capacity grows [1]; the practical point is that the kernel trades reuse of small tiles for the cost of storing two full N×NN \times N intermediates.

4.5 Backward pass

For training, saving the full probability matrix for the backward pass would undo that memory saving. FlashAttention instead keeps the output and a normalization statistic per row, then recomputes score and probability tiles as needed during backward. It spends some extra arithmetic to avoid storing quadratic intermediate state [1].

5. Concrete GPU Implementation

5.1 Kernel structure

A simplified forward kernel has the following structure. One thread block owns a query tile, and the online-softmax state is scalar per row. Later versions change the scheduling around this loop, but not the loop itself.

parallel for each query tile Q_i:
    load Q_i
    m = -infinity
    l = 0
    z = 0

    for each key/value tile (K_j, V_j):
        load K_j and V_j into shared memory
        S_ij = (Q_i @ transpose(K_j)) / sqrt(d)

        new_m = max(m, rowmax(S_ij))
        old_scale = exp(m - new_m)
        P_ij = exp(S_ij - new_m)

        l = old_scale * l + rowsum(P_ij)
        z = old_scale * z + P_ij @ V_j
        m = new_m

    O_i = z / l
    store O_i

One thread block typically owns one or more query tiles. Warps cooperate on tensor-core matrix multiplications, row-wise maximum and sum reductions, and movement between HBM, shared memory, and registers. Causal attention skips score tiles that lie entirely above the diagonal and masks only tiles intersecting the diagonal.

5.2 Fusion boundary

The implementation must fuse score computation, masking, softmax, dropout when required, and value accumulation into one kernel. Writing S_ij or P_ij to global memory between these stages defeats the design. The fusion boundary, rather than a novel matrix-multiplication primitive, is what removes the quadratic intermediate traffic.

5.3 Resource tradeoffs

Larger tiles improve data reuse but consume more shared memory and registers, so fewer blocks may run concurrently. Which tile size works best depends on the GPU and the attention shape.

6. What does the performance look like?

The memory plot shows why avoiding intermediates matters; it does not measure runtime. In this separate B300 comparison (B=2B=2, H=8H=8, dh=128d_h=128, BF16, causal), speedup is measured against an eager attention implementation at each sequence length:

Log-scale plot of speedup over eager attention against sequence length from 512 to 8192 tokens. The SDPA cuDNN curve climbs most steeply; the SDPA math curve remains below one.
Figure 4. Speedup over eager attention on an NVIDIA B300 (SM10.3), by sequence length. The green SDPA cuDNN curve rises from about 3× at 512 tokens to nearly 59× at 8,192; the orange SDPA math curve remains below 1×. Higher means faster relative to eager, not less memory. The spread between curves shows why the executed backend and the problem shape matter.

The growing speedup is consistent with avoiding quadratic intermediate traffic as sequences get longer. It is not a fixed benefit of “FlashAttention”: short sequences, different head sizes, or a different GPU can change the comparison.

7. What to take away

The two matrix multiplications are not the whole cost of attention. A conventional schedule writes their N×NN \times N intermediates to HBM; FlashAttention instead computes and consumes small score tiles on chip. Online softmax makes that possible by carrying a maximum, a normalization sum, and a weighted-value sum from tile to tile.

This changes where data lives, not the dense attention function or its quadratic arithmetic. It also does not promise a fixed speedup: the workload, kernel implementation, and hardware still matter. The next article follows how later GPU implementations schedule this same computation.

References

  1. Tri Dao, Daniel Y. Fu, Stefano Ermon, Atri Rudra, and Christopher Ré. FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness. NeurIPS 2022.