System Design Handbook · llms.txt
Attention is the one part of a transformer whose cost grows with the square of the sequence. Computed the obvious way, it writes an N × N matrix of scores to GPU memory, reads it back for the softmax, writes the probabilities, and reads them again, so at long contexts the memory traffic and the memory itself run out long before the arithmetic does. FlashAttention computes the same result without ever storing that matrix. This chapter derives the trick it rests on, the online softmax, builds a working FlashAttention kernel in Triton, and measures it against plain PyTorch and PyTorch's built-in fused attention on an H100.
Before this chapter, read writing kernels in Triton, especially the tiled matmul, and where the FLOPs go for attention's cost.
For one head, attention computes S = Q Kᵀ ÷ √d, applies the causal mask, takes P = softmax(S) along each row, and returns O = P V. With N tokens and head width d, Q, K, V and O are N × d each, but S and P are N × N. At N = 8,192 that is 67 million scores per head.
Written as ordinary PyTorch operations, each step is a separate kernel that reads its input from HBM and writes its output back. The lab's model of the plain PyTorch version used in the measurements below counts 32 bytes of traffic per score: the matmul writes S, the scaling, the mask, the conversion to FP32, the softmax and the conversion back each read and write it, and the final matmul reads it. For a batch of 4 sequences with 16 heads of 128, the lab's online_softmax.py prints:
3. HBM traffic of causal attention, BF16, d = 128, batch 4 x 16 heads (bytes to and from GPU memory)
N tiled ordinary, minimum plain PyTorch PyTorch at 3.0 TB/s
1024 0.18 GB 0.60 GB 2.2 GB 0.7 ms
4096 2.35 GB 8.86 GB 34.6 GB 11.5 ms
8192 8.99 GB 34.90 GB 138.0 GB 46.0 ms
16384 35.17 GB 138.51 GB 550.8 GB 183.6 ms
The "ordinary, minimum" column is the least any attention that stores S and P must move: write S, read it, write P, read it. The "tiled" column is the FlashAttention approach described below. At N = 8,192 the plain PyTorch version moves 138 GB, which takes 46 ms at the H100's measured 3.0 TB/s, while the arithmetic of the causal half takes about 1.1 ms at the dense BF16 peak. Ordinary attention at long context is a memory-bound operation dressed up as two matmuls.
Memory capacity fails too. The measurement below found that the plain version needed 40 GiB of GPU memory for its intermediate matrices at N = 8,192, and at 16,384 it would need four times that, more than an H100 has.
A softmax over a row seems to need the whole row at once: first the maximum, for numerical safety, then the sum of exponentials, then each probability. Milakov and Gimelshein showed in 2018 that the maximum and the sum can be computed in one pass over the row, block by block. The trick is to keep a running maximum m and a running sum l of exp(s − m), and to rescale l whenever a new block raises the maximum:
At the end, l is exactly the sum of exp(s − max) over the whole row. Attention needs one more running quantity: the output accumulator acc = Σ exp(s_j − m) v_j, which is rescaled by the same alpha. After the last block, acc ÷ l is the softmax-weighted sum of the values, equal to the exact result, without the row of probabilities ever existing in full.
The lab checks this on a CPU. Over a row of 1,000 scores in blocks of 128, the online result differs from the exact softmax by 5.6 × 10⁻¹⁷, which is double-precision rounding. The widget below runs the same algorithm on one row of 16 scores. Step through the blocks and watch alpha: it is 1 when a block brings no new maximum and below 1 when it does.
FlashAttention, by Dao and others (2022), applies the online softmax to attention with tiling. Its abstract describes the goal as making attention IO-aware, accounting for reads and writes between HBM and on-chip SRAM, and reports that it needs fewer HBM accesses than standard attention. The algorithm, in the form the lab implements:
The scores live only in registers, one block at a time. Each program reads Q once and writes O once, and reads the K and V rows its queries can see, which is why the "tiled" column above is about four times smaller than even the minimum for ordinary attention, and 15 times smaller than plain PyTorch.
The core of the Triton kernel is the loop, which is the online softmax from the previous section written over blocks:
hi = tl.minimum((start_m + 1) * BLOCK_M, N) # causal: no key after the block's last query
for start_n in range(0, hi, BLOCK_N):
cols = start_n + offs_n
k = tl.load(K + base + cols[None, :] * D + offs_d[:, None], mask=cols[None, :] < N, other=0.0)
s = tl.dot(q, k) * qk_scale # [BLOCK_M, BLOCK_N] scores, in registers only
s = tl.where((offs_m[:, None] >= cols[None, :]) & (cols[None, :] < N), s, -float("inf"))
m_new = tl.maximum(m_i, tl.max(s, 1))
alpha = tl.exp2(m_i - m_new) # rescales everything accumulated so far
p = tl.exp2(s - m_new[:, None])
l_i = l_i * alpha + tl.sum(p, 1)
v = tl.load(V + base + cols[:, None] * D + offs_d[None, :], mask=cols[:, None] < N, other=0.0)
acc = acc * alpha[:, None] + tl.dot(p.to(v.dtype), v)
m_i = m_new
Two details are worth noticing. The scale 1 ÷ √d is multiplied by log₂(e) once, so the kernel can use exp2. The GPU's special function unit computes powers of 2 directly, and exp is compiled as a multiplication by log₂(e) followed by that instruction, so folding the constant into the scale saves one multiplication per score. And the probabilities are converted to BF16 before the second matmul, so both matmuls run on tensor cores while the running statistics stay in FP32.
The lab ran the Triton kernel, plain PyTorch attention and PyTorch's scaled_dot_product_attention (SDPA), which chooses a fused attention backend by itself, on a batch of 4 sequences with 16 heads of 128 in BF16, causal:
NVIDIA H100 80GB HBM3, PyTorch 2.15.0+cu132, Triton 3.9.0
causal attention forward, BF16, batch 4, 16 heads of 128; TFLOP/s count only the unmasked half
N | Triton flash SDPA naive | max error vs SDPA | naive peak memory
1024 | 197.1 332.5 17.5 | 7.8e-03 | 0.6 GiB
2048 | 270.6 469.6 18.2 | 3.9e-03 | 2.5 GiB
4096 | 320.5 548.1 17.2 | 3.9e-03 | 10.0 GiB
8192 | 350.1 572.7 16.1 | 3.9e-03 | 40.0 GiB
16384 | 364.3 586.0 skipped | 3.9e-03 | too large
Four results stand out:
The three versions keep the same algorithm and change how the work is organised on the GPU:
| Version | Main change, from each paper's abstract | Reported result |
|---|---|---|
| FlashAttention (2022) | Tiling to reduce reads and writes between HBM and on-chip SRAM | 3× faster GPT-2 training at sequence length 1K |
| FlashAttention-2 (2023) | Fewer non-matmul FLOPs, parallelism across the sequence for a single head, and work split between warps to cut shared-memory traffic | 50% to 73% of the A100's peak |
| FlashAttention-3 (2024) | Warp specialization with TMA to overlap memory and compute, interleaved matmul and softmax, and FP8 with block quantization | Up to 740 TFLOP/s in FP16 on H100 (75%), and close to 1.2 PFLOP/s in FP8 |
The lab's kernel corresponds roughly to the FlashAttention-2 plan: one program per block of queries, iterating over keys. On this H100, SDPA dispatches to cuDNN's fused attention, as the trace in chapter 2.5 also shows, and cuDNN's Hopper kernels use the same kind of techniques as FlashAttention-3. That work, which needs control a plain tl.dot loop does not give, accounts for most of the remaining gap.
Decode is a different shape. Each sequence adds one query, which attends to the whole KV cache, so there is no block of queries to share loads across, and attention is memory-bound at an intensity set by the grouped-query ratio, as chapter 1.1 showed. Two techniques adapt FlashAttention to it:
Tier: [Mac] for part A, [1 GPU] for part B. Part A runs on any laptop with NumPy in a second. Part B ran in 10 seconds on a Modal H100, about one cent.
The scripts are ready to download:
modal run modal_run.py --script flash_attention.py --gpu 'H100!'.Part A, the algorithm on a CPU. Implement the online softmax over blocks and check it against an ordinary softmax. Then implement causal attention tiled over query blocks and key blocks, without forming the N × N matrix, and check it against ordinary attention. The part is done when both agree to within 10⁻¹² in double precision.
Part B, the kernel. Write a causal FlashAttention forward kernel in Triton for inputs of shape batch × heads × N × d in BF16. Test it against scaled_dot_product_attention and benchmark it against plain PyTorch attention and SDPA for N from 1,024 to 16,384. The part is done when the maximum error is within a few BF16 rounding steps, your kernel is at least ten times faster than plain PyTorch at N = 8,192, and you can explain where plain PyTorch's time goes.
Extensions. Add the backward pass, which recomputes the scores from Q and K instead of storing them; support grouped-query attention by letting several query heads share one key/value head; or write a decode kernel with one query per sequence that splits the keys across programs as Flash-Decoding does.
Part A. This is the output of online_softmax.py on an M2 MacBook:
1. Online softmax over one row of 1,000 scores, in blocks of 128
max |online - exact| = 5.6e-17, final max 9.198 = row max 9.198
2. Tiled causal attention against ordinary attention, N = 1,000, d = 64
max |tiled - ordinary| = 7.8e-16
The third part of its output is the traffic table at the top of this chapter. The tiled function in the script has the same structure as the Triton kernel, with NumPy arrays in place of registers.
Part B. The kernel is in flash_attention.py, and its output is the table in the measurement section above. Three points decide whether a solution is correct and fast:
The time of plain PyTorch attention is explained in the first section: at N = 8,192 it moves about 138 GB through seven kernels over the full N × N matrix (the first matmul writes it, five element-wise steps each read and write it, and the second matmul reads it), about 46 ms at 3.0 TB/s, against a measured 68 ms.
Both are multiplied by alpha = exp(2.0 − 5.0) = exp(−3) ≈ 0.050 before the new block's terms are added. The old terms were computed relative to a maximum of 2.0, and multiplying by alpha re-expresses them relative to 5.0, so all terms share one reference point.
To the N × N intermediates for all 64 heads. One BF16 copy of the scores is 64 × 8,192² × 2 bytes, about 8.6 GB, and the FP32 copy and the FP32 softmax output are about 17.2 GB each. During the softmax, the BF16 scores, their FP32 copy and the FP32 output are all alive at once: 8.6 + 17.2 + 17.2 = 43.0 GB, which is the 40.0 GiB the lab measured. FlashAttention never allocates any of them.
Every key after a query's position is masked out, so its probability is zero and its block contributes nothing. Stopping early skips about half of all key blocks for causal attention, which halves the work without changing the result. Only the diagonal block, which mixes visible and masked keys, needs the element-wise mask.
On this setup SDPA used cuDNN's attention kernels. Production kernels for Hopper, such as these and the ones described in the FlashAttention-3 paper, use TMA for asynchronous loads, warp specialization so that some warps load while others compute, and interleaving of the softmax with the matmuls to keep the tensor cores busy. The lab's kernel loads and computes in the same warps and relies on Triton's general pipelining.
Each chunk produces a partial output normalised by its own sum, plus its log-sum-exp. The final step rescales each chunk's output by exp(chunk log-sum-exp − overall log-sum-exp) and adds them, which is the online softmax's rescaling applied to whole chunks rather than blocks within one program. The result equals attention over the full cache.
Previous: CUDA for reading and debugging · Next: Profiling and benchmarking