Attention operator 2: decode attention, FlashDecoding and FlashDecoding++
During decode each sequence brings only one new query row, so a FlashAttention kernel built for long prompts leaves most of the GPU idle. Flash-Decoding splits the KV cache into chunks, attends to each chunk on its own SM, and merges the parts exactly with log-sum-exp. FlashDecoding++ removes the rescaling between chunks with one fixed scale, and paged-KV kernels read the cache through a block table.
What you will learn
- Why decode attention is a memory-bound matrix-vector product with about g FLOPs per byte, where g is the GQA group size
- Why one query row gives too few thread blocks to fill 108 SMs, and how that wastes memory bandwidth
- How Flash-Decoding splits the KV sequence, computes partial outputs with their log-sum-exp, and merges them exactly
- How to pick the number of splits: waves, the FlashAttention-2 heuristic, and the cost of the reduce step
- How FlashDecoding++ uses one unified max value to skip rescaling, when it must fall back, and what its flat-GEMM and dataflow ideas are
- How paged-KV kernels find each token through a block table, and how vLLM and FlashAttention combine paging with split-KV
Why this matters
When an LLM writes text, each step adds one token. For that step, attention has one new query row per sequence and per head, and it must read the whole KV cache. FlashAttention was built for the opposite case: thousands of query rows. Used as is for decode, it can leave most of the GPU idle while the user waits.
Recall the two phases from session 78. Prefill processes the whole prompt at once: the query matrix has as many rows as the prompt has tokens. Decode produces one token at a time: the query has one row, and the keys and values of all earlier tokens come from the KV cache (session 80). In session 124 we saw how FlashAttention computes attention in tiles without writing the full score matrix to memory. It gives each thread block (a group of GPU threads that runs on one streaming multiprocessor, or SM) one tile of query rows. For decode there is only one tile per sequence and head. So the number of thread blocks is just batch size times number of heads.
An A100 has 108 SMs. [Certain] With batch 1 and the 8 KV heads of Llama 3 8B, a kernel that gives one thread block to each (sequence, KV head) pair starts 8 blocks: 8 of 108 SMs work, 7.4%. The other 100 SMs wait. Long contexts make it worse, because they need so much KV memory that the batch must be small. The Flash-Decoding authors write that with batch size 1, FlashAttention “will use less than 1% of the GPU”. [Certain, Flash-Decoding blog]
This session shows three fixes that are in every modern inference engine:
- Flash-Decoding (Dao, Haziza, Massa, Sizov, 2023): split the KV sequence into chunks, let different SMs attend to different chunks, then merge the partial results exactly with a log-sum-exp.
- FlashDecoding++ (Hong et al., 2023): use one fixed “unified max value” so the chunks never need to rescale each other; plus faster matrix products for small batches.
- Paged-KV attention (vLLM’s PagedAttention, Kwon et al., 2023): read the cache from fixed-size pages through a block table, so memory is not wasted, and combine this with split-KV.
Decode attention is a memory-bound matrix-vector product
Take one sequence, one KV head and one decode step. The cache holds \(L\) keys and \(L\) values, each a vector of size \(d\). With grouped-query attention (GQA, session 97), \(g\) query heads share this KV head, so we have \(g\) query rows. The operation is
- \(L\)
- context length: number of tokens already in the cache
- \(d\)
- head dimension (128 in Llama 2 and Llama 3)
- \(g\)
- query heads per KV head (1 for normal multi-head attention, 4 for Llama 3 8B)
- \(Q, K, V\)
- queries of this step, cached keys and cached values
With \(g = 1\), \(QK^\top\) is a vector times a matrix (a GEMV), not a matrix times a matrix (a GEMM). Let us count. Computing the scores costs \(2gLd\) FLOPs (one multiply and one add per pair). Applying them to \(V\) costs another \(2gLd\). The kernel must read \(K\) and \(V\): \(2Ld\) numbers of 2 bytes each in FP16 or BF16. Everything else (the query, the output) is tiny. So the arithmetic intensity, FLOPs per byte read from memory, is
An A100 80GB (SXM) does 312 TFLOP/s in dense BF16 and reads 2,039 GB/s from HBM. [Certain] Its ridge point, the intensity above which a kernel is limited by compute instead of memory (session 82), is \(312 / 2.039 \approx 153\) FLOPs per byte. Decode attention has 1 (MHA) or 4 (Llama 3 8B). It sits far to the left of the ridge: its speed is set only by how fast we can stream the KV cache. A bigger batch does not help here, unlike for the linear layers, because every sequence has its own cache: twice the batch means twice the bytes.
Llama 3 8B has 32 layers, 8 KV heads and \(d = 128\). [Certain] One token in the cache costs \(2 \times 32 \times 8 \times 128 \times 2 = 131{,}072\) bytes, that is 128 KiB (keys and values, all layers, BF16). A context of 32,768 tokens holds 4 GiB per sequence.
Each decode step must read all of it once. At 2,039 GB/s this takes at least \(4 \times 2^{30} / 2.039 \times 10^{12} = 2.11\) ms per token, for attention alone, for one sequence. Per layer it is 134 MB and at least 65.8 µs. Llama 2 7B uses full multi-head attention (32 KV heads), so its cache is 4 times larger: 512 KiB per token, 16 GiB at 32k, at least 8.43 ms per token.
This lower bound assumes the whole HBM bandwidth is used. It is reached only if enough SMs are reading at the same time. That is the real problem of decode attention.
Why one query row leaves the GPU idle
An SM can only keep a limited number of memory requests in flight. To use the full bandwidth of HBM, many SMs must issue loads at once. FlashAttention-2 launches a grid of thread blocks over (batch, heads, query tiles). In decode, the query tile count is 1, so the grid has \(B \times H\) blocks. Each block walks over the full context, tile by tile, keeping a running max and a running sum (the online softmax from session 124):
- \(m, \ell, \mathbf{o}\)
- running max, running sum of exponentials and running (unnormalized) output, over the key tiles seen so far
- \(\tilde m, \tilde \ell, \tilde{\mathbf{o}}\)
- the same three quantities for the new key tile
This loop is sequential: tile 2 needs the max of tile 1. If \(B \times H\) is much smaller than the number of SMs, the loop over a long context runs on a few SMs only, at a few SMs’ worth of bandwidth.
Flash-Decoding: split the KV sequence
Flash-Decoding adds a new axis of parallel work: the KV sequence itself. It works in three steps. [Certain, Flash-Decoding blog]
- Split the keys and values into \(S\) chunks. This needs no GPU work: the chunks are views of the cache tensors.
- Attend to each chunk in parallel with a FlashAttention-style kernel. Each chunk writes its partial output and one extra number per query row: the log-sum-exp of its scores.
- Reduce: a second small kernel combines the \(S\) partial outputs, weighting each one with its log-sum-exp.
Now the grid has \(B \times H \times S\) blocks. With \(B = 1\), 8 KV heads and \(S = 24\), that is 192 blocks instead of 8.
The math of the merge
Write \(s_j = \mathbf{q}^\top \mathbf{k}_j / \sqrt{d}\) for the score of key \(j\), for one query row. Chunk \(p\) holds the key indices \(\mathcal{I}_p\). It computes four things on its own:
- \(m_p\)
- largest score in chunk \(p\), subtracted for numerical safety
- \(\ell_p\)
- sum of the shifted exponentials in chunk \(p\)
- \(\mathbf{o}_p\)
- the attention output if chunk \(p\) were the whole context (a normalized partial output)
- \(\lambda_p\)
- the log-sum-exp of chunk \(p\): \(\lambda_p = \log \sum_{j \in \mathcal{I}_p} e^{s_j}\)
The reduce step then computes
Why is this exact? Because \(e^{\lambda_p} \mathbf{o}_p = \sum_{j \in \mathcal{I}_p} e^{s_j} \mathbf{v}_j\) (the \(m_p\) and \(\ell_p\) cancel). So
which is plain softmax attention over all \(L\) keys. Nothing is approximated. The weights \(e^{\lambda_p - \lambda}\) are just a softmax over the \(S\) log-sum-exp values, and in code the reduce kernel subtracts \(\max_p \lambda_p\) first, so nothing overflows. FlashAttention-2 stores the partial outputs and log-sum-exps in FP32 buffers of shape (splits, batch, heads, query rows, head dim) and (splits, batch, heads, query rows). [Certain, flash_api.cpp]
Scores \(\mathbf{s} = (1.2, -0.5, 2.0, 0.3 \,|\, 3.1, -1.0, 0.8, 2.4)\) and scalar values \(v = (1, 2, 3, 4 \,|\, 5, 6, 7, 8)\). The bar marks the split.
Chunk 1: \(m_1 = 2.0\), \(\ell_1 = e^{-0.8} + e^{-2.5} + e^{0} + e^{-1.7} = 1.7141\), \(o_1 = 2.5344\), \(\lambda_1 = 2.0 + \log 1.7141 = 2.5389\).
Chunk 2: \(m_2 = 3.1\), \(\ell_2 = 1.6134\), \(o_2 = 6.0579\), \(\lambda_2 = 3.5784\).
Reduce: \(\lambda = \log(e^{2.5389} + e^{3.5784}) = 3.8812\). Weights \(e^{\lambda_1 - \lambda} = 0.2613\) and \(e^{\lambda_2 - \lambda} = 0.7387\) (they sum to 1). Output \(0.2613 \times 2.5344 + 0.7387 \times 6.0579 = 5.1374\).
Full softmax over all 8 keys gives \(5.1374\) and log-sum-exp \(3.8812\): the same. Note that a plain average of the two partial outputs, \(4.296\), would be wrong; chunk 2 has the larger scores and must count more.
- Kernel 1, grid \((B, H_{kv}, S)\): all blocks \(p\) run at the same time
- chunk \(p \leftarrow\) keys of split \(p\) // a view of the cache, no copy
- \(m \leftarrow -\infty\); \(\ell \leftarrow 0\); \(\text{acc} \leftarrow 0\)
- for each tile of \(T\) keys in chunk \(p\):
- \(s \leftarrow q \cdot K_{\text{tile}} / \sqrt d\); \(\tilde m \leftarrow \max(s)\)
- \(m_{\text{new}} \leftarrow \max(m, \tilde m)\); \(c \leftarrow e^{m - m_{\text{new}}}\)
- \(\ell \leftarrow c\,\ell + \sum e^{s - m_{\text{new}}}\); \(\text{acc} \leftarrow c \cdot \text{acc} + \sum e^{s - m_{\text{new}}}\, v\); \(m \leftarrow m_{\text{new}}\)
- \(o_p \leftarrow \text{acc} / \ell\); \(\lambda_p \leftarrow m + \log \ell\) // FP32 buffer (125.4)
- Kernel 2 (reduce), one block per query row
- \(\lambda_{\max} \leftarrow \max_p \lambda_p\); \(Z \leftarrow 0\); \(O \leftarrow 0\)
- for \(p = 1, \dots, S\): \(w_p \leftarrow e^{\lambda_p - \lambda_{\max}}\); \(Z \mathrel{+}= w_p\); \(O \mathrel{+}= w_p\, o_p\)
- \(o \leftarrow O / Z\); \(\lambda \leftarrow \lambda_{\max} + \log Z\) // (125.5)
How to read Figure 1
Press Play, or Step to go one line at a time (Back goes one line back). Click a thread block card to show its numbers in the formula box. With \(S = 1\) you have plain FlashAttention in decode: one block walks all 8 keys; with tile \(T = 1\) that takes 8 tile steps, and the readout counts them. With \(S = 2\), \(T = 2\) each block needs only 2 tile steps, and you get the numbers of the worked example: \(\lambda_1 = 2.5389\), \(o_1 = 2.5344\), \(\lambda_2 = 3.5784\), \(o_2 = 6.0579\), then \(w_1 = e^{2.5389 - 3.5784} = 0.3536\), \(Z = 1.3536\), and \(o = 5.1374\). Watch line 6: when a new tile has a larger max, the old \(\ell\) and acc are multiplied by \(c \lt 1\) (a rescale); the readout counts rescales. With \(S = 8\) each block holds one key, so \(\ell_p = 1\), \(\lambda_p = s_p\), and the reduce is a softmax over the 8 scores. Every setting ends with \(o = 5.1374\) and \(\lambda = 3.8812\).
The two kernels as pseudo-code
- input: queries \(Q\) of shape \((B, H_q, d)\), KV cache \(K, V\) of shape \((B, L, H_{kv}, d)\), number of splits \(S\)
- kernel 1, grid \((B, H_{kv}, S)\): the block for \((b, h, p)\) does
- load the \(g\) query rows of KV head \(h\) // GQA: all query heads of the group share the K, V loads
- for each key tile in chunk \(p\) (positions \(p \lceil L/S \rceil\) to \((p+1)\lceil L/S \rceil - 1\)) do
- scores \(\leftarrow Q_h K_{\text{tile}}^\top / \sqrt{d}\); online-softmax update (125.3) of \(m, \ell, \mathbf{o}\)
- write \(\mathbf{o}_p = \mathbf{o} / \ell\) and \(\lambda_p = m + \log \ell\) to FP32 buffers // (125.4)
- kernel 2, grid \((B, H_q)\): for each query row
- \(\lambda_{\max} \leftarrow \max_p \lambda_p\); \(\;w_p \leftarrow e^{\lambda_p - \lambda_{\max}}\)
- \(\mathbf{o} \leftarrow \sum_p w_p \mathbf{o}_p / \sum_p w_p\) // (125.5); write in BF16
- (optional) write \(\lambda = \lambda_{\max} + \log \sum_p w_p\) // useful for later merges, e.g. prefix caches
How many splits?
More splits give more parallel work. But they also cost something: each split writes a partial output in FP32, the reduce kernel must read them all, and there is a second kernel launch. And the GPU runs thread blocks in waves: if it can hold \(N_{\text{slot}}\) blocks at once and you launch a few more than that, the extra blocks run in a second, mostly empty wave.
FlashAttention-2 picks \(S\) with exactly this formula. [Certain, flash_api.cpp] If \(B \cdot H \cdot (\text{query tiles})\) already fills 80% of the slots, it uses one split. Otherwise it computes the wave efficiency for every \(S\) up to 128, finds the best one, and returns the smallest \(S\) whose efficiency is at least 85% of the best. It counts two blocks per SM (\(N_{\text{slot}} = 2 \times 108 = 216\) on an A100) and skips values of \(S\) that give the same chunk length as \(S - 1\). For decode with GQA it first moves the \(g\) query heads of a group into the “query rows” dimension, so the grid counts KV heads, and one K, V load serves all \(g\) heads.
Figure 2 puts these rules in a small cost model. The model is a toy: it assumes each of the 216 slots can stream at most \(1/216\) of the HBM bandwidth, and that the reduce kernel costs 3 µs plus its memory traffic. Real SMs can take more than their share when others are idle, so the real loss at \(S = 1\) is smaller than the toy shows. [Likely] The shape of the curve is the lesson, not the exact microseconds.
How to read Figure 2
The default is Llama 3 8B shapes at batch 1 and 32k context. With \(S = 1\) there are 8 blocks, 3.7% of the slots are busy, and the toy time is 1,777 µs against an ideal of 65.8 µs. Press the heuristic button: it picks \(S = 24\) (192 blocks, efficiency \(192/216 = 0.89\), which is at least 85% of the best), and the time falls to 77.5 µs. \(S = 27\) fills all 216 slots (69.3 µs). At \(S = 64\) there are 512 blocks in 3 waves, and the time goes up again to 87.3 µs. Now set the batch to 32 and the context to 4,096: 256 blocks already exceed the 80% rule, the heuristic returns 1, and splitting gives little.
Two practical points. First, split-KV matters most for small batches and long contexts: exactly the case of a single user with a long document or a long video. At large batch the grid is already full, and engines turn it off. Second, Flash-Decoding reports up to 8× faster end-to-end decoding for CodeLlama-34B at very long sequences, and attention up to 50× faster than FlashAttention; in their micro-benchmark (A100, batch 1, 16 query heads, 2 KV heads, \(d = 128\)) the attention time stayed almost constant up to 32k tokens. [Certain, Flash-Decoding blog] It shipped in FlashAttention 2.2 and xFormers 0.0.22. [Certain]
FlashDecoding++: one unified max value
Flash-Decoding still has one source of waiting. Inside each chunk, the online softmax (125.3) must rescale its running output each time the max grows. Across chunks, the reduce step must wait for every chunk’s \(\lambda_p\) before it can weight anything. FlashDecoding++ calls this the synchronized partial softmax update. On an A100 with Llama2-7B and input length 1024, its profile shows this update takes 18.8% of the attention time. [Certain, FlashDecoding++ paper]
The fix starts from a simple fact: the max in a softmax can be replaced by any number \(\varphi\):
We subtract the max only to keep the exponentials in range. If \(\varphi\) is a fixed number known in advance, every chunk can compute \(\mathbf{N}_p\) and \(D_p\) without knowing anything about the other chunks, and the merge is a plain sum, in any order. No rescaling, no max, no waiting: the authors call it an asynchronized softmax.
The risk is overflow and underflow. We need \(e^{s_j - \varphi}\) to stay representable:
Scores far below \(\varphi\) underflow to 0; that is fine only for tokens whose weight is negligible anyway. FlashDecoding++ picks \(\varphi\) from statistics collected offline. For Llama2-7B more than 99.99% of the softmax inputs lie in \([-16.8, 6.5]\). [Certain, FlashDecoding++ paper] That window is 23.3 wide; \(e^{23.3} \approx 1.3 \times 10^{10}\) fits in FP32 easily but not in FP16, whose largest value is 65,504. When some score of a vector falls outside the safe window, the kernel throws away that vector’s asynchronous result and recomputes it with the normal synchronized method. The paper says this is rare enough to be negligible, from its statistics. For OPT-6.7B the input range is too wide, and the method is not applied. [Certain, FlashDecoding++ paper]
How to read Figure 3
At the start (\(\mu = 0\), \(\varphi = 0\), FP32) all dots are inside the safe zone and the error is about \(2 \times 10^{-7}\) (FP32 sums). Switch to FP16: the error grows to about \(2 \times 10^{-5}\) (FP16 rounding of each exponential) but there is no overflow. Now move \(\mu\) to 8: the largest \(s_j - \varphi\) is 14.0, above \(\log 65504 = 11.09\), so FP16 overflows and the kernel must fall back. In FP32 the same case is fine. Move \(\mu\) to −14 in FP16: no overflow, but 20 of the 64 exponentials round to zero and the error is \(3.4 \times 10^{-5}\); it stays small only because the lost tokens have small weights. In FP32, \(\mu = 90\) overflows, and \(\mu = -105\) loses 35 of 64 tokens with an error of \(2.2 \times 10^{-3}\), about 10,000 times larger than at \(\mu = 0\). The lesson: a unified max works when the score range is narrow and predictable, and the overflow check is not optional.
- offline: run the model on sample data; record the softmax inputs; choose \(\varphi\) and a safe window \((a, b)\) that holds almost all of them (125.9)
- input: query row \(\mathbf{q}\), chunks \(\mathcal{I}_1, \dots, \mathcal{I}_S\) of the KV cache
- for each chunk \(p\) in parallel do
- \(s_j \leftarrow \mathbf{q}^\top \mathbf{k}_j / \sqrt{d}\) for \(j \in \mathcal{I}_p\)
- if some \(s_j - \varphi \notin (a, b)\) then raise the flag “recompute” for this row
- \(\mathbf{N}_p \leftarrow \sum_j e^{s_j - \varphi}\mathbf{v}_j\), \(\;D_p \leftarrow \sum_j e^{s_j - \varphi}\) // no max, no rescale
- atomically add \(\mathbf{N}_p\) and \(D_p\) into the row’s accumulators // or write them and sum later
- if the flag is raised then recompute this row with the synchronized method (125.3)–(125.5)
- else \(\mathbf{o} \leftarrow \sum_p \mathbf{N}_p / \sum_p D_p\) // (125.8)
Figure 4 runs Algorithm 2 on the same 8 keys as Figure 1, so you can compare the two step by step. Look at what is missing: no running max, no rescale factor \(c\), and no reduce kernel. The blocks add their sums into two global numbers in whatever order they finish.
- One kernel, grid \((B, H_{kv}, S)\); \(\varphi\) fixed offline; FP16 window \((a, b) = (-16.64, 11.09)\)
- chunk \(p \leftarrow\) keys of split \(p\)
- \(n_p \leftarrow 0\); \(d_p \leftarrow 0\); flag \(\leftarrow\) false // global \(N = D = 0\)
- for each tile of \(T\) keys in chunk \(p\):
- \(s \leftarrow q \cdot K_{\text{tile}} / \sqrt d\); if some \(s - \varphi \notin (a, b)\): flag \(\leftarrow\) true
- \(e \leftarrow \text{fp16}(e^{s - \varphi})\) // no max, no rescale
- \(n_p \mathrel{+}= \sum e\, v\); \(d_p \mathrel{+}= \sum e\)
- atomicAdd\((N, n_p)\); atomicAdd\((D, d_p)\) // any order
- if flag: recompute the row with Flash-Decoding, else \(o \leftarrow N / D\) // (125.8)
How to read Figure 4
Press Play or Step. The default \(\varphi = 3\) is a little below the largest score (3.1), so all \(s_j - \varphi\) lie in \([-4, 0.1]\) and the result is \(5.13736\), an error of \(2.4 \times 10^{-5}\) that comes only from FP16 rounding of the exponentials. Compare the tile lines with Figure 1: there is no \(m\), no \(c\), and no reduce kernel. Now move \(\varphi\) to −8: the largest \(s_j - \varphi\) is 11.1, above \(\log 65504 = 11.09\); \(e^{11.1}\) overflows FP16, line 4 raises the flag, and the last line falls back to Flash-Decoding. At \(\varphi = 10\) nothing overflows, but all exponentials are tiny (the largest is 0.001); the smallest ones are FP16 subnormal numbers with fewer significant bits, and the error grows to \(3.8 \times 10^{-4}\). At \(\varphi = 16\) the smallest \(s_j - \varphi\) is −17, below the window, so the flag is raised again.
The other two parts of FlashDecoding++
The paper has two more ideas. They are about the linear layers, which we study in session 126; here is the short version.
- Flat GEMM with double buffering. In decode, a linear layer multiplies a weight matrix by a matrix with only \(M\) = batch size rows: a “flat” GEMM. Libraries such as cuBLAS and CUTLASS tile \(M\) in blocks of 64, so with a small batch most of each tile is zero padding, and more than 50% of the work is wasted. FlashDecoding++ pads \(M\) only to 8 and uses two shared-memory buffers, so one tile loads while the other computes. [Certain, FlashDecoding++ paper]
- Heuristic dataflow. For each weight shape \([N, K]\) it profiles, offline, three implementations: a GEMV on CUDA cores (FastGEMV), its flat GEMM on Tensor Cores, and a normal CUTLASS GEMM. At run time it picks one by comparing \(M\) to two thresholds \(M_1\) and \(M_2\) found by that profiling. [Certain, FlashDecoding++ paper]
The abstract reports up to 4.86× (NVIDIA) and 2.18× (AMD) speedup over Hugging Face implementations, and an average of 1.37× over state-of-the-art inference engines. [Certain, FlashDecoding++ abstract] These are whole-model numbers, so they mix the three ideas.
Paged-KV attention kernels
So far we assumed the cache of each sequence is one contiguous tensor. Real servers do not do this. Sequences grow by one token per step and finish at unknown times. Reserving the maximum length for each one wastes memory: the vLLM paper measured that only 20.4% to 38.2% of KV-cache memory held real token states in earlier systems. [Certain, vLLM paper] PagedAttention stores the cache in fixed-size pages (vLLM calls them blocks; the default is 16 tokens [Certain]). Each sequence has a block table: a list of page numbers in logical order, like the page table of an operating system. Memory management is the topic of session 134; here we care about what the attention kernel must do differently.
To find token \(t\) of sequence \(b\), the kernel computes
- \(\mathrm{BT}_b\)
- block table of sequence \(b\): logical page index to physical page index
- \(P\)
- page size in tokens
- \(K_{\text{pool}}\)
- one big tensor of shape (pages, \(P\), \(H_{kv}\), \(d\)) shared by all sequences; values live in a second pool with the same layout
Because softmax attention does not care where the keys are stored, only which keys are in the set, the math is unchanged: the kernel loops over pages instead of over contiguous tiles. The vLLM paper writes the attention as a sum over KV blocks, the same structure as (125.4)–(125.5) with one block per tile. The cost is an extra lookup in the block table and less regular memory access: vLLM measured 20–26% higher attention-kernel latency than FasterTransformer’s contiguous kernel, a cost limited to the attention operator. [Certain, vLLM paper] The pay-off is much more room for sequences, and so larger batches: 2–4× higher throughput at the same latency. [Certain, vLLM abstract]
How to read Figure 5
Sequence B has 70 tokens, so it needs \(\lceil 70/16 \rceil = 5\) pages; its last page holds only 6 tokens, and 10 slots are empty. That is the only waste of paging: less than one page per sequence. With partitions of 32 tokens the kernel launches 3 blocks for B: pages {4, 13}, {0, 9} and {14}. Move the slider: token 37 is in logical page 2, slot 5, and the block table sends it to physical page 0. Switch to sequence C (20 tokens): it needs 2 pages and only one partition, so a split kernel gives it no extra parallelism.
Paging and splitting together
Paging and split-KV fit well: a chunk is just a range of pages. vLLM’s own CUDA kernels (as of v0.6.0) have two versions. V1 gives one block per (sequence, head) and loops over all pages. V2 cuts the context into partitions of 512 tokens, runs one block per partition, and merges with the log-sum-exp rule, exactly Flash-Decoding. The Python wrapper uses V1 when the longest sequence has at most 8,192 tokens and either there is only one partition or sequences × heads is above 512; otherwise V2. [Certain, vLLM v0.6.0 source] FlashAttention-2’s flash_attn_with_kvcache also accepts a block table; in the version we read, the page size must be a multiple of 256 tokens. [Certain, flash_api.cpp] FlashInfer stores the paged cache as a block-sparse matrix and adds load-balanced scheduling for batches with very different lengths. [Certain, FlashInfer abstract]
- input: queries, page pools \(K_{\text{pool}}, V_{\text{pool}}\), block tables \(\mathrm{BT}\), lengths \(L_b\), page size \(P\), partition size \(T\) (a multiple of \(P\))
- grid: \((b, h, p)\) for \(p = 0, \dots, \lceil L_b / T \rceil - 1\) // blocks past the end exit at once
- \(m \leftarrow -\infty\), \(\ell \leftarrow 0\), \(\mathbf{o} \leftarrow \mathbf{0}\)
- for logical page \(i\) from \(pT/P\) to \(\min((p+1)T, L_b)/P\) do
- \(\text{phys} \leftarrow \mathrm{BT}_b[i]\) // (125.10): one integer load per page
- load keys of page phys (mask slots \(\ge L_b\) in the last page); scores; update (125.3); load values; accumulate
- write \(\mathbf{o}/\ell\) and \(m + \log \ell\) for partition \(p\)
- reduce kernel: merge the partitions of each row with (125.5); skip the reduce when there is only one partition
The whole thing in PyTorch
The code below builds a paged KV cache with scattered pages, runs split-KV decode attention for 1, 2, 4 and 8 splits, runs the unified-max variant with its fallback, and checks everything against PyTorch’s scaled_dot_product_attention. It runs on a CPU in a second; on a GPU the inner loops are what one thread block does.
import math, torch torch.manual_seed(0) B, Hq, Hkv, d = 2, 8, 2, 64 # batch, query heads, KV heads (GQA group g = 4), head dim g = Hq // Hkv P = 16 # tokens per KV page (block) lens = torch.tensor([45, 70]) # current context length of each sequence # 1) a paged KV cache: one pool of pages + a block table per sequence num_pages = 16 k_pool = torch.randn(num_pages, P, Hkv, d) v_pool = torch.randn(num_pages, P, Hkv, d) perm = torch.randperm(num_pages) # pages are scattered on purpose block_table = [perm[:3].tolist(), perm[3:8].tolist()] # ceil(45/16)=3, ceil(70/16)=5 pages q = torch.randn(B, Hq, d) # decode: ONE new query row per sequence and head def gather_kv(b): """Read the pages of sequence b in logical order (a real kernel reads them in place).""" pages = torch.tensor(block_table[b]) k = k_pool[pages].reshape(-1, Hkv, d)[: lens[b]] # (L, Hkv, d), formula (125.10) v = v_pool[pages].reshape(-1, Hkv, d)[: lens[b]] return k, v # 2) Flash-Decoding: split the KV sequence, attend to each split, merge with log-sum-exp def split_attend(qh, k, v): """One split: partial output o_p and its log-sum-exp, formula (125.4).""" s = (k @ qh) / math.sqrt(d) # (Ls,) scores m = s.max() p = torch.exp(s - m) l = p.sum() return (p @ v) / l, m + torch.log(l) def merge(outs, lses): """Reduce step, formula (125.5): weights exp(lse_p - lse).""" lses = torch.stack(lses) w = torch.softmax(lses, dim=0) # = exp(lse_p - logsumexp(lses)) return (w[:, None] * torch.stack(outs)).sum(0) def flash_decode(q, num_splits): out = torch.empty(B, Hq, d) for b in range(B): k, v = gather_kv(b) L = k.shape[0] chunk = math.ceil(L / num_splits) for h in range(Hq): kvh = h // g # GQA: query head h reads KV head h // g outs, lses = [], [] for start in range(0, L, chunk): # these splits run in parallel on a GPU o_p, lse_p = split_attend(q[b, h], k[start:start + chunk, kvh], v[start:start + chunk, kvh]) outs.append(o_p); lses.append(lse_p) out[b, h] = merge(outs, lses) return out # 3) FlashDecoding++ idea: one fixed "unified max" phi, no rescaling, plain sums def unified_max_decode(q, num_splits, phi=6.0, bound=80.0): out = torch.empty(B, Hq, d); fallbacks = 0 for b in range(B): k, v = gather_kv(b); L = k.shape[0]; chunk = math.ceil(L / num_splits) for h in range(Hq): kvh = h // g; num = torch.zeros(d); den = torch.zeros(()) s_all = (k[:, kvh] @ q[b, h]) / math.sqrt(d) if (s_all - phi).abs().max() > bound: # outside the safe window (125.9): recompute the usual way fallbacks += 1 out[b, h] = flash_decode(q, num_splits)[b, h]; continue for start in range(0, L, chunk): p = torch.exp(s_all[start:start + chunk] - phi) # no max, no rescale (125.8) num += p @ v[start:start + chunk, kvh]; den += p.sum() out[b, h] = num / den return out, fallbacks # 4) reference: plain softmax attention with SDPA, one sequence at a time ref = torch.empty(B, Hq, d) for b in range(B): k, v = gather_kv(b) kk = k.repeat_interleave(g, dim=1).transpose(0, 1) # (Hq, L, d) vv = v.repeat_interleave(g, dim=1).transpose(0, 1) ref[b] = torch.nn.functional.scaled_dot_product_attention(q[b][:, None], kk, vv)[:, 0] for S in (1, 2, 4, 8): print(S, (flash_decode(q, S) - ref).abs().max().item()) # all below 1e-6 o_u, nfb = unified_max_decode(q, 4) print("unified max:", (o_u - ref).abs().max().item(), "fallbacks:", nfb) # about 4e-7, 0 o_big, nfb_big = unified_max_decode(q * 40, 4) # scores 40x larger print("large scores, fallbacks:", nfb_big, "of", B * Hq) # 13 of 16 rows fall back
On our machine (PyTorch 2.8, CPU) the four split counts give maximum errors between \(2.4 \times 10^{-7}\) and \(4.2 \times 10^{-7}\): FP32 rounding only. With scores 40 times larger, 13 of the 16 (sequence, head) rows leave the window of ±80 and fall back.
Where this is used
| Setting | Which kernel idea matters | Why |
|---|---|---|
| Chat with one user and a long document (batch 1, 32k–128k context) | Split-KV (Flash-Decoding), GQA packing | \(B \times H_{kv}\) is tiny; without splits most SMs are idle while the 4 GiB+ cache is read |
| High-throughput serving (vLLM, SGLang, TensorRT-LLM) | Paged KV with block tables; split-KV only when the grid is not full | Paging packs many sequences into memory; large batches already fill the GPU [Likely] |
| Long-video question answering with a VLM (thousands of visual tokens per clip) | Split-KV over the long visual prefix, paged cache | Every answer token must attend over the whole video context; this is the batch-1, long-context case |
| Video-RAG and multi-document RAG | Paged KV plus prefix caching; log-sum-exp merge of cached and new parts | Shared retrieved chunks can be cached once; (125.5) merges attention over separate KV pieces exactly [Likely] |
| Streaming captioning or key-moment alerts on live video | Paged KV that grows page by page; small-batch decode kernels | The context grows without a known end, so contiguous allocation does not work |
| Speculative decoding verification (session 128) | Decode kernels with a few query rows (draft length + 1) | Still far fewer rows than a FlashAttention tile; split-KV and GQA packing apply |
| Consumer and AMD GPUs | FlashDecoding++ (also evaluated on RTX 3090, MI210, RX 7900 XTX) | Fewer SMs and different tensor-core shapes make the dataflow choice more important [Likely] |
Common mistakes
- Averaging partial outputs. The parts must be weighted by \(e^{\lambda_p - \lambda}\) (125.5). A plain average gave 4.296 instead of 5.1374 in the worked example.
- Weighting by \(\ell_p\) alone. \(\ell_p\) is computed after subtracting each chunk’s own max \(m_p\), so sums from different chunks are on different scales. Use \(\lambda_p = m_p + \log \ell_p\).
- Storing partial results in BF16. Partial outputs and log-sum-exps are kept in FP32 (as FlashAttention-2 does); rounding each part to BF16 before the merge adds error for nothing.
- Empty chunks. With ragged lengths a chunk can contain no keys; \(\lambda_p = -\infty\) must produce weight 0, not NaN.
- Splitting when the grid is already full. At large batch, split-KV only adds reduce traffic and a kernel launch. Use a rule such as the 80% test of FlashAttention-2.
- Too many splits. Past one full wave, extra splits add a second, mostly empty wave and more partial results (Figure 2 at \(S = 64\)).
- A unified max without an overflow check. Scores depend on the input; one unusual prompt can push \(s_j - \varphi\) above 88.7 (FP32) or 11.09 (FP16). The fallback path is part of the algorithm.
- Benchmarking decode at short context only. At 512 tokens every kernel looks similar; the differences appear at long context and small batch.
Interview questions
Why does FlashAttention-2 use the GPU poorly during decode?basic
What is the arithmetic intensity of decode attention, and why does batching not raise it?core
Derive the rule to merge two partial attention outputs.core
What extra memory does split-KV need, and in what precision?core
How would you choose the number of splits?advanced
Is Flash-Decoding useful at batch 256?core
Explain FlashDecoding++’s unified max value. When does it fail?advanced
What does a paged attention kernel do differently from a contiguous one, and what does it cost?core
How does GQA change the decode kernel?advanced
Page size: what are the trade-offs between 16 and 256 tokens?advanced
Why does FlashDecoding++ also optimize GEMMs if the topic is decode attention?core
Exercises
- Merge two chunks: chunk 1 has \(\lambda_1 = 1.0\), \(o_1 = 2\); chunk 2 has \(\lambda_2 = 1.0 + \ln 3\), \(o_2 = 6\) (scalar values). What is the merged output?
- Llama 2 7B (32 layers, 32 KV heads, \(d = 128\), BF16), batch 1, context 16,384. How many bytes does one decode step read from the KV cache, and what is the lower bound on its time at 2,039 GB/s?
- With the FlashAttention-2 rule and 216 block slots, does a batch of 4 with 8 KV heads use split-KV? What if the batch is 32?
- In FP16, \(\varphi = 2\). Which is the largest score \(s_j\) that does not overflow \(e^{s_j - \varphi}\)?
- Sequence of 100 tokens, page size 16. How many pages, how many empty slots, and which logical page and slot hold token 50?
- Show that the merge (125.5) is associative: merging (A, B) and then C gives the same result as merging A with (B, C). Why does this matter for GPUs?
Answerscheck
Key takeaways
- Decode attention (125.1) has one query row per sequence and head; its intensity is about \(g\) FLOPs per byte (125.2), far below an A100’s ridge of 153, so its speed is the speed of reading the KV cache.
- FlashAttention parallelizes over batch, heads and query tiles; in decode that gives only \(B \times H\) blocks, too few to use all SMs and all of the bandwidth.
- Flash-Decoding adds the KV sequence as a parallel axis: chunks compute \((\mathbf{o}_p, \lambda_p)\) (125.4), and a reduce merges them exactly with log-sum-exp weights (125.5, 125.6).
- The number of splits is a waves problem (125.7): fill about one wave; FlashAttention-2 uses an 80% and 85% rule; at large batch, do not split.
- FlashDecoding++ subtracts one fixed \(\varphi\) (125.8) so chunks never rescale, with a fallback when a score leaves the safe window (125.9); it also tunes flat GEMMs and picks kernels per shape.
- Paged-KV kernels read keys through a block table (125.10); the math is unchanged, the kernel is 20–26% slower in vLLM’s measurement, and serving throughput grows 2–4×.
Key formulas
References for this session
- Dao et al. (2023). Flash-Decoding for long-context inference (blog)
- Hong et al. (2023). FlashDecoding++: Faster Large Language Model Inference on GPUs
- Kwon et al. (2023). Efficient Memory Management for Large Language Model Serving with PagedAttention
- Dao et al. (2023). Flash-Decoding for long-context inference (blog)
- Hong et al. (2023). FlashDecoding++: Faster Large Language Model Inference on GPUs
- Kwon et al. (2023). Efficient Memory Management for Large Language Model Serving with PagedAttention
- Dao et al. (2022). FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness
- Dao (2023). FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioning
- Shah et al. (2024). FlashAttention-3: Fast and Accurate Attention with Asynchrony and Low-precision
- Ainslie et al. (2023). GQA: Training Generalized Multi-Query Transformer Models from Multi-Head Checkpoints
- Ye et al. (2025). FlashInfer: Efficient and Customizable Attention Engine for LLM Inference Serving
- Zhou, Ning, Hong et al. (2024). A Survey on Efficient Inference for Large Language Models