LLM & VLM courseBlog
125Track 5: LLM inference and serving · session 48 of 65

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.

Time: 2.5 to 3.5 hours (reading 2 hours, exercises 1 hour)Level: IntermediateBefore this: Sessions 80 (the KV cache), 82 (roofline) and 124 (FlashAttention 1, 2 and 3)

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

\[ O = \softmax\!\left( \frac{Q K^\top}{\sqrt{d}} \right) V, \qquad Q \in \R^{g \times d}, \quad K, V \in \R^{L \times d}, \quad O \in \R^{g \times d} \tag{125.1} \]
\(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

\[ I = \frac{4 g L d \ \text{FLOPs}}{2 L d \cdot 2 \ \text{bytes}} = g \ \ \frac{\text{FLOP}}{\text{byte}} \tag{125.2} \]

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.

How long does it take just to read the cache?

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_{\text{new}} = \max(m, \tilde m), \qquad \ell \leftarrow e^{m - m_{\text{new}}}\,\ell + e^{\tilde m - m_{\text{new}}}\,\tilde \ell, \qquad \mathbf{o} \leftarrow e^{m - m_{\text{new}}}\,\mathbf{o} + e^{\tilde m - m_{\text{new}}}\,\tilde{\mathbf{o}} \tag{125.3} \]
\(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]

  1. Split the keys and values into \(S\) chunks. This needs no GPU work: the chunks are views of the cache tensors.
  2. 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.
  3. 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 = \max_{j \in \mathcal{I}_p} s_j, \qquad \ell_p = \sum_{j \in \mathcal{I}_p} e^{s_j - m_p}, \qquad \mathbf{o}_p = \frac{1}{\ell_p} \sum_{j \in \mathcal{I}_p} e^{s_j - m_p}\, \mathbf{v}_j, \qquad \lambda_p = m_p + \log \ell_p \tag{125.4} \]
\(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

\[ \lambda = \log \sum_{p=1}^{S} e^{\lambda_p}, \qquad \mathbf{o} = \sum_{p=1}^{S} e^{\lambda_p - \lambda}\, \mathbf{o}_p \tag{125.5} \]

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

\[ \mathbf{o} = \frac{\sum_p e^{\lambda_p} \mathbf{o}_p}{\sum_p e^{\lambda_p}} = \frac{\sum_{j=1}^{L} e^{s_j} \mathbf{v}_j}{\sum_{j=1}^{L} e^{s_j}} = \sum_{j=1}^{L} \softmax(\mathbf{s})_j\, \mathbf{v}_j \tag{125.6} \]

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]

A merge by hand (8 keys, 2 chunks)

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.

  1. Kernel 1, grid \((B, H_{kv}, S)\): all blocks \(p\) run at the same time
  2. chunk \(p \leftarrow\) keys of split \(p\) // a view of the cache, no copy
  3. \(m \leftarrow -\infty\); \(\ell \leftarrow 0\); \(\text{acc} \leftarrow 0\)
  4. for each tile of \(T\) keys in chunk \(p\):
  5. \(s \leftarrow q \cdot K_{\text{tile}} / \sqrt d\); \(\tilde m \leftarrow \max(s)\)
  6. \(m_{\text{new}} \leftarrow \max(m, \tilde m)\); \(c \leftarrow e^{m - m_{\text{new}}}\)
  7. \(\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}}\)
  8. \(o_p \leftarrow \text{acc} / \ell\); \(\lambda_p \leftarrow m + \log \ell\) // FP32 buffer (125.4)
  9. Kernel 2 (reduce), one block per query row
  10. \(\lambda_{\max} \leftarrow \max_p \lambda_p\); \(Z \leftarrow 0\); \(O \leftarrow 0\)
  11. for \(p = 1, \dots, S\): \(w_p \leftarrow e^{\lambda_p - \lambda_{\max}}\); \(Z \mathrel{+}= w_p\); \(O \mathrel{+}= w_p\, o_p\)
  12. \(o \leftarrow O / Z\); \(\lambda \leftarrow \lambda_{\max} + \log Z\) // (125.5)
key scores \(s\)values \(v\)one color per thread block (chunk)reduce kernel
Figure 1. Flash-Decoding running on the 8 keys of the worked example (one query row, scalar values). Kernel 1: every thread block walks its own chunk tile by tile with the online softmax (125.3); all blocks move in the same clock step because they run on different SMs. Each block writes \((\mathbf{o}_p, \lambda_p)\) (125.4). Kernel 2 merges them with the log-sum-exp weights (125.5). The code line that runs is highlighted, and the box on the right shows that line with the live numbers. The merged output equals full softmax attention for every \(S\) and \(T\).
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

Algorithm 1: Flash-Decoding (split kernel, then reduce kernel)
  1. input: queries \(Q\) of shape \((B, H_q, d)\), KV cache \(K, V\) of shape \((B, L, H_{kv}, d)\), number of splits \(S\)
  2. kernel 1, grid \((B, H_{kv}, S)\): the block for \((b, h, p)\) does
  3.   load the \(g\) query rows of KV head \(h\) // GQA: all query heads of the group share the K, V loads
  4.   for each key tile in chunk \(p\) (positions \(p \lceil L/S \rceil\) to \((p+1)\lceil L/S \rceil - 1\)) do
  5.     scores \(\leftarrow Q_h K_{\text{tile}}^\top / \sqrt{d}\); online-softmax update (125.3) of \(m, \ell, \mathbf{o}\)
  6.   write \(\mathbf{o}_p = \mathbf{o} / \ell\) and \(\lambda_p = m + \log \ell\) to FP32 buffers // (125.4)
  7. kernel 2, grid \((B, H_q)\): for each query row
  8.   \(\lambda_{\max} \leftarrow \max_p \lambda_p\); \(\;w_p \leftarrow e^{\lambda_p - \lambda_{\max}}\)
  9.   \(\mathbf{o} \leftarrow \sum_p w_p \mathbf{o}_p / \sum_p w_p\) // (125.5); write in BF16
  10.   (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.

\[ N_{\text{blocks}} = B \cdot H_{kv} \cdot S, \qquad \text{waves} = \left\lceil \frac{N_{\text{blocks}}}{N_{\text{slot}}} \right\rceil, \qquad \text{efficiency} = \frac{N_{\text{blocks}} / N_{\text{slot}}}{\text{waves}} \tag{125.7} \]

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.

selected \(S\)other values of \(S\)ideal time (dashed line)
Figure 2. Toy model of one decode attention layer on an A100 (2,039 GB/s, 216 block slots), head dimension 128, 4 query heads per KV head, BF16 cache. Bars: time for each number of splits \(S\) from 1 to 128 (log time scale). Dashed line: the ideal time, all bytes at full bandwidth. The selected \(S\) is highlighted.
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\):

\[ \softmax(\mathbf{s})_j = \frac{e^{s_j - \varphi}}{\sum_{i} e^{s_i - \varphi}} \quad \text{for every } \varphi \in \R, \qquad \mathbf{o} = \frac{\sum_{p} \mathbf{N}_p}{\sum_{p} D_p}, \quad \mathbf{N}_p = \sum_{j \in \mathcal{I}_p} e^{s_j - \varphi} \mathbf{v}_j, \quad D_p = \sum_{j \in \mathcal{I}_p} e^{s_j - \varphi} \tag{125.8} \]

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:

\[ a \lt s_j - \varphi \lt b \quad \text{for all } j, \qquad \text{FP32: } b \approx \log(3.4 \times 10^{38}) = 88.7, \qquad \text{FP16: } b = \log 65504 = 11.09 \tag{125.9} \]

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]

Figure 3. The asynchronized softmax (125.8) on 64 scores \(s_j = \mu + 6 \sin(2.399\, j + 0.5)\) with values \(v_j = 1 + \cos(1.3\, j)\). Dots are \(s_j - \varphi\). Each exponential is rounded to the chosen format, the sums are kept in FP32, and the result is compared with exact softmax attention.
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.

Algorithm 2: FlashDecoding++ asynchronized softmax with fallback
  1. 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)
  2. input: query row \(\mathbf{q}\), chunks \(\mathcal{I}_1, \dots, \mathcal{I}_S\) of the KV cache
  3. for each chunk \(p\) in parallel do
  4.   \(s_j \leftarrow \mathbf{q}^\top \mathbf{k}_j / \sqrt{d}\) for \(j \in \mathcal{I}_p\)
  5.   if some \(s_j - \varphi \notin (a, b)\) then raise the flag “recompute” for this row
  6.   \(\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
  7.   atomically add \(\mathbf{N}_p\) and \(D_p\) into the row’s accumulators // or write them and sum later
  8. if the flag is raised then recompute this row with the synchronized method (125.3)–(125.5)
  9. 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.

  1. One kernel, grid \((B, H_{kv}, S)\); \(\varphi\) fixed offline; FP16 window \((a, b) = (-16.64, 11.09)\)
  2. chunk \(p \leftarrow\) keys of split \(p\)
  3. \(n_p \leftarrow 0\); \(d_p \leftarrow 0\); flag \(\leftarrow\) false // global \(N = D = 0\)
  4. for each tile of \(T\) keys in chunk \(p\):
  5. \(s \leftarrow q \cdot K_{\text{tile}} / \sqrt d\); if some \(s - \varphi \notin (a, b)\): flag \(\leftarrow\) true
  6. \(e \leftarrow \text{fp16}(e^{s - \varphi})\) // no max, no rescale
  7. \(n_p \mathrel{+}= \sum e\, v\); \(d_p \mathrel{+}= \sum e\)
  8. atomicAdd\((N, n_p)\); atomicAdd\((D, d_p)\) // any order
  9. if flag: recompute the row with Flash-Decoding, else \(o \leftarrow N / D\) // (125.8)
key scores \(s\) and \(e^{s - \varphi}\)one color per thread blockglobal accumulators \(N, D\)outside the safe window
Figure 4. The asynchronized softmax of FlashDecoding++ (Algorithm 2) on the 8 keys of Figure 1. Each exponential \(e^{s_j - \varphi}\) is rounded to FP16, as a half-precision kernel would store it; the sums are kept in FP32. The blocks add their \((n_p, d_p)\) into the global \((N, D)\) in a scrambled order to show that the order does not matter. The last step compares \(N / D\) with exact softmax attention (5.1374).
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

\[ \text{page} = \mathrm{BT}_b\!\left[ \lfloor t / P \rfloor \right], \qquad \text{slot} = t \bmod P, \qquad \mathbf{k}_t = K_{\text{pool}}[\text{page}, \text{slot}] \tag{125.10} \]
\(\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]

Figure 5. A paged KV cache with page size \(P = 16\) and a pool of 16 physical pages shared by three sequences. The top row is the chosen sequence in logical order; arrows follow its block table into the pool. Colors mark split-KV partitions of 32 tokens (2 pages), as in a partitioned paged-attention kernel.
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]

Algorithm 3: paged split-KV decode attention (one block per sequence, KV head and partition)
  1. 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\))
  2. grid: \((b, h, p)\) for \(p = 0, \dots, \lceil L_b / T \rceil - 1\) // blocks past the end exit at once
  3. \(m \leftarrow -\infty\), \(\ell \leftarrow 0\), \(\mathbf{o} \leftarrow \mathbf{0}\)
  4. for logical page \(i\) from \(pT/P\) to \(\min((p+1)T, L_b)/P\) do
  5.   \(\text{phys} \leftarrow \mathrm{BT}_b[i]\) // (125.10): one integer load per page
  6.   load keys of page phys (mask slots \(\ge L_b\) in the last page); scores; update (125.3); load values; accumulate
  7. write \(\mathbf{o}/\ell\) and \(m + \log \ell\) for partition \(p\)
  8. 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

SettingWhich kernel idea mattersWhy
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 fullPaging 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 cacheEvery answer token must attend over the whole video context; this is the batch-1, long-context case
Video-RAG and multi-document RAGPaged KV plus prefix caching; log-sum-exp merge of cached and new partsShared retrieved chunks can be cached once; (125.5) merges attention over separate KV pieces exactly [Likely]
Streaming captioning or key-moment alerts on live videoPaged KV that grows page by page; small-batch decode kernelsThe 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 GPUsFlashDecoding++ (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
It parallelizes over batch, heads and query tiles. In decode there is one query row per sequence and head, so there is one query tile, and the grid has only batch × heads thread blocks. With batch 1 and 8 KV heads that is 8 blocks on 108 SMs. Each block loops sequentially over the whole context, so only a few SMs pull data from HBM, and the kernel gets a small part of the memory bandwidth it needs.
What is the arithmetic intensity of decode attention, and why does batching not raise it?core
Per KV head and step: \(4gLd\) FLOPs (scores and weighted sum for \(g\) query rows) over \(4Ld\) bytes of BF16 keys and values, so about \(g\) FLOPs per byte: 1 for MHA, 4 for Llama 3 8B. The A100 ridge point is about 153. Batching helps linear layers because many tokens share one weight matrix, but in attention each sequence has its own KV cache, so bytes grow with the batch exactly as FLOPs do. Only sharing K and V across query rows raises it: GQA/MQA, MLA, or several query tokens (speculative verification).
Derive the rule to merge two partial attention outputs.core
Each part stores \(\mathbf{o}_p = \sum_{j \in p} e^{s_j} \mathbf{v}_j / \sum_{j \in p} e^{s_j}\) and \(\lambda_p = \log \sum_{j \in p} e^{s_j}\) (computed stably with its own max). Then \(e^{\lambda_p}\mathbf{o}_p = \sum_{j \in p} e^{s_j}\mathbf{v}_j\). Summing over parts and dividing by \(\sum_p e^{\lambda_p}\) gives exactly full softmax attention. So \(\mathbf{o} = \sum_p w_p \mathbf{o}_p\) with \(w = \softmax(\lambda_1, \dots, \lambda_S)\), and the merged log-sum-exp is \(\log\sum_p e^{\lambda_p}\). The same rule merges attention over a cached prefix and a new suffix, or over KV shards on different GPUs.
What extra memory does split-KV need, and in what precision?core
For each split, batch, head and query row: one output vector of size \(d\) and one log-sum-exp, both in FP32. FlashAttention-2 allocates buffers of shape \((\text{splits}, B, H, q_{\text{len}}, d)\) and \((\text{splits}, B, H, q_{\text{len}})\). This is tiny next to the KV cache: for \(S = 24\), 32 query heads and \(d = 128\) it is \(24 \times 32 \times 129 \times 4 \approx 0.4\) MB per sequence and layer, written and read once.
How would you choose the number of splits?advanced
Fill the GPU with about one full wave and no more. FlashAttention-2: if batch × heads × query tiles is already at least 80% of the block slots (2 per SM), use 1 split. Otherwise compute wave efficiency \(n/\lceil n \rceil\) with \(n = B H S / N_{\text{slot}}\) for every eligible \(S \le 128\), and take the smallest \(S\) within 85% of the best. Also keep each chunk long enough (at least a few key tiles) so per-block overhead and the reduce stay small, and remember that a second wave or a near-empty last chunk wastes time.
Is Flash-Decoding useful at batch 256?core
Usually not. With 256 sequences and 8 KV heads the grid already has 2,048 blocks, far more than the 216 slots of an A100, so all SMs stream KV already. Splitting would only add partial-result traffic and a reduce kernel. It helps when \(B \times H_{kv}\) is small compared to the SM count: small batches, few KV heads (GQA, MQA), and long contexts, which are also the cases where attention dominates the step time.
Explain FlashDecoding++’s unified max value. When does it fail?advanced
Softmax is unchanged if we subtract any constant \(\varphi\) instead of the max. If \(\varphi\) is fixed in advance (from offline statistics of the model’s softmax inputs), each chunk computes \(\sum e^{s_j - \varphi}\mathbf{v}_j\) and \(\sum e^{s_j - \varphi}\) independently, and the merge is a plain sum: no rescaling and no waiting for other chunks’ maxima. It fails when some \(s_j - \varphi\) leaves the safe range: overflow above about 88.7 in FP32, or the important scores falling so low that they underflow. The kernel detects this and recomputes that row with the normal synchronized method. For Llama2-7B more than 99.99% of inputs lie in [−16.8, 6.5]; for OPT-6.7B the range is too wide and the method is not used.
What does a paged attention kernel do differently from a contiguous one, and what does it cost?core
It finds keys and values through a block table: page = BT[t / P], slot = t mod P, then reads from a shared pool. The softmax math is the same, done page by page with the online-softmax update. Costs: one extra integer load per page, less regular addressing, masking of the partly filled last page, and constraints that the page size fits the kernel tile (FlashAttention-2 requires a multiple of 256). vLLM measured 20–26% higher attention-kernel latency than FasterTransformer, but gained 2–4× throughput because paging lets many more sequences fit in memory.
How does GQA change the decode kernel?advanced
The \(g\) query heads of a group read the same \(K\) and \(V\). A good kernel loads each \(K, V\) tile once and multiplies it with all \(g\) query rows, which turns a GEMV into a small GEMM and raises intensity to about \(g\) FLOPs/byte. FlashAttention-2 does this by reshaping \(q\) from \((b, 1, H_{kv} \cdot g, d)\) to \((b, g, H_{kv}, d)\) when \(q_{\text{len}} = 1\), so the group becomes the query-row dimension. The grid then counts KV heads, which makes it even smaller, so split-KV becomes more important with GQA.
Page size: what are the trade-offs between 16 and 256 tokens?advanced
Small pages waste less memory (at most \(P - 1\) empty slots per sequence) and share prefixes at a finer grain, but need more block-table entries, more pointer lookups and shorter contiguous reads. Large pages give long contiguous loads that match big kernel tiles, but waste more memory per sequence and make copy-on-write and prefix sharing coarser. vLLM defaults to 16 and found 16 to 128 best on ShareGPT; FlashAttention-2’s paged path requires multiples of 256.
Why does FlashDecoding++ also optimize GEMMs if the topic is decode attention?core
In decode, the linear layers are flat GEMMs with \(M\) = batch rows. Libraries tile \(M\) by 64, so at small batch most of the tensor-core work is padding (over 50% waste). For short and medium contexts the linear layers take most of the step time, so the paper pads \(M\) only to 8, double-buffers loads, and switches between a CUDA-core GEMV, its flat GEMM and CUTLASS according to \(M\) and the weight shape. The end-to-end speedups combine these with the softmax change.

Exercises

  1. 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?
  2. 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?
  3. 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?
  4. In FP16, \(\varphi = 2\). Which is the largest score \(s_j\) that does not overflow \(e^{s_j - \varphi}\)?
  5. Sequence of 100 tokens, page size 16. How many pages, how many empty slots, and which logical page and slot hold token 50?
  6. 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
1. Weights are \(\softmax(1, 1 + \ln 3) = (1/4, 3/4)\), so \(o = 0.25 \times 2 + 0.75 \times 6 = 5\). 2. Per token \(2 \times 32 \times 32 \times 128 \times 2 = 524{,}288\) bytes; times 16,384 = 8 GiB (8,589,934,592 bytes); at least 4.21 ms. 3. Batch 4: \(4 \times 8 = 32\) blocks, below \(0.8 \times 216 = 172.8\), so it splits (the rule returns 6 at 32k context: 192 blocks, efficiency 0.89). Batch 32: 256 blocks, above 172.8, so 1 split. 4. \(s_j - 2 \lt \ln 65504 = 11.09\), so \(s_j \lt 13.09\). 5. \(\lceil 100/16 \rceil = 7\) pages; \(7 \times 16 - 100 = 12\) empty slots; token 50 is in logical page \(\lfloor 50/16 \rfloor = 3\), slot \(50 - 48 = 2\). 6. Each merge keeps \((\lambda, \mathbf{o})\) with \(e^{\lambda}\mathbf{o} = \sum e^{s_j}\mathbf{v}_j\) and \(e^{\lambda} = \sum e^{s_j}\) over the merged keys. Both are plain sums over disjoint key sets, and sums are associative, so any grouping gives the same pair (up to rounding). This means the reduce can be a tree, chunks can finish in any order, and the same rule merges results across GPUs (for example in ring or sequence-parallel attention).

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

\[ \lambda_p = m_p + \log \ell_p, \qquad \mathbf{o} = \sum_p e^{\lambda_p - \lambda}\,\mathbf{o}_p, \quad \lambda = \log \sum_p e^{\lambda_p} \]
\[ I_{\text{decode}} \approx g \ \tfrac{\text{FLOP}}{\text{byte}}, \qquad N_{\text{blocks}} = B\,H_{kv}\,S, \qquad \mathbf{o} = \frac{\sum_p \sum_{j \in \mathcal{I}_p} e^{s_j - \varphi}\mathbf{v}_j}{\sum_p \sum_{j \in \mathcal{I}_p} e^{s_j - \varphi}} \]

References for this session

  1. Dao et al. (2023). Flash-Decoding for long-context inference (blog)
  2. Hong et al. (2023). FlashDecoding++: Faster Large Language Model Inference on GPUs
  3. Kwon et al. (2023). Efficient Memory Management for Large Language Model Serving with PagedAttention
  4. Dao et al. (2023). Flash-Decoding for long-context inference (blog)
  5. Hong et al. (2023). FlashDecoding++: Faster Large Language Model Inference on GPUs
  6. Kwon et al. (2023). Efficient Memory Management for Large Language Model Serving with PagedAttention
  7. Dao et al. (2022). FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness
  8. Dao (2023). FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioning
  9. Shah et al. (2024). FlashAttention-3: Fast and Accurate Attention with Asynchrony and Low-precision
  10. Ainslie et al. (2023). GQA: Training Generalized Multi-Query Transformer Models from Multi-Head Checkpoints
  11. Ye et al. (2025). FlashInfer: Efficient and Customizable Attention Engine for LLM Inference Serving
  12. Zhou, Ning, Hong et al. (2024). A Survey on Efficient Inference for Large Language Models