KV-cached generation, metrics and your GPU’s roofline
In this lab you write the generation loop twice, without and with a KV cache, check that both give the same tokens, and time them on your own GPU. You measure time to first token and time per output token as the prompt and the batch grow, measure your GPU’s real memory bandwidth and matmul speed, draw its roofline, and place your own prefill and decode passes on it.
What you will learn
- How to write generate() without and with a preallocated KV cache, and how to test it (FP32 token equality; why BF16 can flip near-ties)
- Why the cache saves more than 99% of the FLOPs but can save much less time: memory-bound steps make the saved math free
- How to time GPU code correctly: warm-up, synchronization, repeats, and what launch overhead does to a token loop
- How TTFT grows with prompt tokens and why TPOT grows much more slowly than the batch size, measured on a 1B-shaped model
- How to measure memory bandwidth (a 1 GiB copy) and matmul speed, and draw the measured roofline with its ridge
- How to place prefill and decode on the roofline from FLOP and byte counts, and read the efficiency of your software
- Why repeating grouped K and V before attention makes long-context decode slow
Why this matters
You have read that decode is memory-bound, that prefill is compute-bound, and that a KV cache makes generation fast. In this lab you stop taking these sentences on trust. You write the generation loop twice, time it on your own GPU, measure the two numbers that define your GPU (memory bandwidth and matmul speed), and place your own measurements on a roofline. At the end you can say, with your own numbers, why your model is as fast as it is and what would make it faster.
This lab ties together five earlier sessions. Session 78 gave the two phases, prefill and decode. Session 80 gave the cache and its size. Session 81 defined time to first token (TTFT) and time per output token (TPOT). Session 82 gave the cost formulas and the roofline, with spec-sheet numbers. Session 86 showed how to measure the effective bandwidth of one kernel. Here you do the same for a whole model.
The work has four parts, one per key point of the session:
- Write
generate()without and with a KV cache, check that both give the same tokens, and measure the speed-up. - Measure TTFT and TPOT as the prompt length and the batch size change.
- Measure the memory bandwidth and the matmul speed of your GPU, and draw its roofline.
- Place your prefill and decode passes on that roofline.
All our numbers come from one machine: a laptop with an Apple M5 Pro chip (20-core GPU, 48 GB of unified memory), PyTorch 2.8 with the MPS back-end, in BF16. Other jobs were running on the machine at the same time, so our times are noisy and somewhat pessimistic; we report the best of several repeats. Your numbers will be different. The point of the lab is the method and the shape of the curves, which carry over to any GPU.
The lab model: a 1B-shaped transformer with random weights
For timing we do not need a trained model. The time of a forward pass depends on the shapes of the matrices, not on their values. So we build a model with the exact shape of Llama 3.2 1B and fill it with random numbers. This needs no download and no license, and it runs on any GPU with about 4 GB of free memory.
The shape, from the model’s config.json [Certain]: vocabulary \(V = 128{,}256\), model width \(d = 2048\), \(L = 16\) layers, 32 query heads and \(n_{kv} = 8\) key-value heads of size \(d_h = 64\) (grouped-query attention, from session 97), a SwiGLU feed-forward layer of width 8,192, and an output layer that shares (ties) its weights with the input embedding. We leave out the RoPE scaling for long contexts; it does not change the cost.
- Read the symbols
- \(N_{mm}\)
- the weights used in matrix multiplies during one step: the 16 blocks plus the output layer (tied to the embedding, but still read once per step)
- \(h, n_{kv}, d_h\)
- 32 query heads, 8 key-value heads, head size 64
- \(d_{ff}\)
- feed-forward width, 8,192 (SwiGLU has three matrices of size \(d \times d_{ff}\))
- \(\text{kv}_{\text{tok}}\)
- bytes of KV cache per token: keys and values (the 2), for every layer and KV head
- \(s\)
- bytes per number: 2 for BF16
One block: \(2048 \cdot 48 \cdot 64 + 2048^2 + 3 \cdot 2048 \cdot 8192 = 6{,}291{,}456 + 4{,}194{,}304 + 50{,}331{,}648 = 60{,}817{,}408\) weights. Sixteen blocks: \(N_{\text{body}} = 973{,}078{,}528\). Embedding: \(128{,}256 \times 2048 = 262{,}668{,}288\). With the norms, PyTorch counts 1,235,814,400 parameters, so 2.47 GB in BF16. Every decode step must read about 2.47 GB of weights.
KV cache: \(2 \cdot 16 \cdot 8 \cdot 64 \cdot 2 = 32{,}768\) bytes = 32 KiB per token. A 4,096-token context needs 134 MB per sequence, about 5% of the weights. Thanks to grouped-query attention this is four times less than with 32 KV heads.
The full code is in the section “The whole lab in one file” below. The model is about 60 lines: an RMSNorm, RoPE, a block with fused QKV and gate-up matrices, and a forward pass that returns the logits of the last position only. The cache is a list of preallocated tensors, one key tensor and one value tensor per layer, of shape (batch, \(n_{kv}\), max length, \(d_h\)). A forward pass with a cache writes the new keys and values at positions start to start + T and attends over everything up to there.
Part 1: generate() without and with a KV cache
Without a cache, every step feeds the whole sequence so far through the model and keeps only the last logits. With a cache, the first call (the prefill) processes the prompt and stores every layer’s keys and values; every later call (a decode step) feeds one token, appends its key and value, and attends over the stored ones.
- input: model \(f\), prompt tokens \(x_{1..P}\), number of new tokens \(n\)
- \(\text{seq} \leftarrow x_{1..P}\)
- for \(i = 0, \dots, n-1\):
- \(\ell \leftarrow f(\text{seq})\) // all P + i positions, all layers, every time
- \(\text{seq} \leftarrow \text{seq} \,\Vert\, \arg\max \ell_{\text{last}}\)
- return the last \(n\) tokens of seq
- input: model \(f\), prompt \(x_{1..P}\), \(n\); allocate \(K, V\) of shape \((L, B, n_{kv}, P + n, d_h)\)
- \(\ell \leftarrow f(x_{1..P};\ \text{write } K, V \text{ at } 0..P-1)\) // prefill: one pass over the prompt
- \(y_1 \leftarrow \arg\max \ell_{\text{last}}\) // the first token: TTFT ends here
- for \(i = 1, \dots, n-1\):
- \(\ell \leftarrow f(y_i;\ \text{write at } P+i-1,\ \text{read } K, V[0..P+i-1])\) // decode: one token
- \(y_{i+1} \leftarrow \arg\max \ell\)
- return \(y_{1..n}\)
Both loops are greedy, so with exact arithmetic they must return the same tokens. That is the first test you run.
The correctness test, and why it needs FP32
Run both loops on a tiny model (width 128, 2 layers, 4 prompts of 16 tokens, 48 new tokens) and compare. In FP32, on CPU and on the GPU, all 192 tokens match, and the logits differ by at most \(3 \times 10^{-7}\). In BF16 on the GPU, only 97.9% match: one of the four rows goes a different way at token 37. [Certain, our run]
This is not a bug in the cache. The two loops add the same numbers in a different order (different matrix shapes pick different kernels), and BF16 keeps only about 3 significant digits. The logits differ by up to 0.023, and random weights give logits that are close together (all within about ±1.3 here), so a small difference can swap the top token. After one swap, the two sequences are different texts. A trained model has sharper logits and swaps less often, but it can still happen. So test the logic in FP32, where it must be exact, and test BF16 only with a tolerance on the logits.
How much work does the cache save?
Count FLOPs and bytes of one forward pass, as in session 82. Our model computes logits only for the last position, so the output layer costs the same in every pass.
- Read the symbols
- \(F, Q\)
- FLOPs of the pass and bytes it must move between GPU memory and the chip (at least)
- \(T\)
- tokens in a prefill pass (or in a no-cache step)
- \(2LdT^2\)
- causal attention: scores and the weighted sum, \(4Ld\) FLOPs per pair of tokens, over about \(T^2/2\) pairs
- \(b, c\)
- sequences decoding together and their context length
- \(4Ldc\)
- attention of one new token over \(c\) cached tokens
A no-cache step at length \(P + i\) is a full prefill of \(P + i\) tokens. A cached loop is one prefill of \(P\) tokens and then \(n - 1\) decode steps:
If we keep only the linear layers, the ratio has a simple form: the no-cache loop pushes \(\sum_i (P+i)\) tokens through the weights, the cached loop \(P + n - 1\):
For \(P = 128\) and \(n = 256\) that is \(65{,}408 / 383 = 170.8\). The exact count of (87.4), with the output layer and attention, gives 144.6. So the cache saves more than 99% of the FLOPs. Does it save 99% of the time? Not necessarily, and this is the first surprise of the lab.
A pass cannot be faster than its math at peak speed, nor faster than its bytes at full bandwidth. Every pass reads all the weights at least once, so every pass costs at least \(sN_{mm}/\text{BW}\). A no-cache step with a few hundred tokens does a few hundred times more math than a decode step, but if that math still fits under the memory time, it is free: the step takes the same time. The saved FLOPs turn into saved time only when the no-cache steps become compute-bound, that is, when \(P + i\) passes the ridge of the GPU (about 295 tokens on an H100 in BF16).
How to read Figure 1
Start with the defaults (\(P = 128\), \(n = 256\), our M5 Pro): the cache saves 144.6 times the FLOPs, but the best-case speed-up is only about 1.63×, because the first no-cache steps are memory-bound and cost the same as a cached step. Switch to the H100: its ridge is higher, every no-cache step stays under it, and the best-case speed-up drops to 1.00×. Now drag the prompt to 2,048: the no-cache curve climbs steeply, the steps are compute-bound, and the speed-up grows to 6 on the H100 and 13.6 on the M5 Pro. Long prompts are where the cache pays most. Notice that the cached curve hardly moves: its steps are set by the weight bytes.
What we measured
With a 128-token prompt and 256 new tokens, one sequence, BF16: the no-cache loop took 32.5 s and the cached loop 7.75 s, a speed-up of 4.2×. [Certain, our run] That is more than the best case of Figure 1 (1.63×). Why? Because the real no-cache steps are far from the roof. Our measured prefill of 128 tokens took 46 ms against a bound of 10.6 ms; real kernels for medium-size matrices are slow, and PyTorch’s attention on this back-end has its own overhead. The cached loop runs mostly decode steps, which are simple and close to the memory bound. So the measured speed-up depends on how good your kernels are at each shape, not only on FLOPs. On a data-center GPU with well-tuned kernels, expect the measured speed-up at short prompts to be small and the speed-up at long prompts to be large [Likely].
Measuring time correctly
Before Part 2, learn the four rules of GPU timing. Most wrong benchmark numbers you will see break one of them.
- The GPU runs asynchronously. A PyTorch call on a GPU tensor puts a kernel in a queue and returns at once. If you read the clock right after, you measured how long Python took to issue the work. Call
torch.cuda.synchronize()(ortorch.mps.synchronize()) before you stop the clock. - Warm up first. The first call allocates memory, picks kernels, compiles shaders or graphs, and fills caches. Run the measured function once or twice before timing it.
- Repeat and report a robust statistic. Use the minimum to estimate what the hardware can do, and the median or a percentile to describe what users will see. Never a single run.
- Measure what the user waits for. TTFT ends when the first token exists (after the prefill and the first argmax); TPOT is the time of one decode step, including the sync that brings the token to the CPU, because a real loop needs it there to stream it or to check for the end-of-sequence token.
- input: a function \(g\) that launches GPU work; \(w\) warm-up runs; \(r\) timed runs
- repeat \(w\) times: \(g()\) // allocation, kernel choice, compilation
- synchronize; \(\text{best} \leftarrow \infty\)
- repeat \(r\) times: \(t_0 \leftarrow\) clock; \(g()\); synchronize; \(\text{best} \leftarrow \min(\text{best}, \text{clock} - t_0)\)
- return best // or keep all \(r\) times and report the median and P90
How to read Figure 2
With the defaults (issue 2 ms, GPU 6 ms) and “no sync”, the timer reads 10 ms, but the GPU finishes at 32 ms: the number is three times too small. “Sync at the end” gives the true 32 ms. “Sync every step” gives 40 ms, 8 ms per step, because the GPU now waits while the CPU issues each next step. Now set the issue time to 8 ms: the loop becomes launch-bound, and the GPU is idle most of the time. This is what happens to a small model run in eager PyTorch, and why serving engines use CUDA graphs (session 50).
On our laptop the launch cost is real: one decode step of the 1B model issues several hundred small GPU operations from Python (16 layers, each with a few dozen operations: norms, RoPE, cache writes, attention, the matmuls). This is one reason why our measured TPOT is about twice the bandwidth bound (Part 2). On a CUDA GPU you can remove most of this cost with CUDA graphs or torch.compile(mode="reduce-overhead"), which record the step once and replay it with a single launch [Certain].
Part 2: TTFT and TPOT vs prompt length and batch size
We measure the two phases separately, as in session 81:
- Read the symbols
- \(t_{\text{pre}}\)
- measured time of one prefill pass plus the argmax of the first token, with an empty queue (no waiting time)
- \(t_{\text{dec}}(B, c)\)
- measured time of one decode step for \(B\) sequences that each have \(c\) tokens in the cache
- \(P\)
- prompt length; \(B\) is the batch size
Measuring one decode step at a fixed context is cleaner than timing a whole loop: you control \(c\) exactly, and you can sweep \(B\) and \(c\) on a grid. The lab code does exactly this: it fills a cache of the right size (the values do not matter for timing) and times one call at position \(c\).
How to read Figure 3
TTFT vs prompt: the line for one sequence rises roughly in proportion to \(P\) from 512 tokens on, a bit faster at the long end. Eight sequences of \(P\) tokens cost about as much as one sequence of \(8P\) tokens, or less, because each sequence’s attention covers only its own \(P\) tokens. Both stay a factor of about 2 to 5 above the bound. TPOT vs batch: the work grows 128 times from 1 to 128 sequences, but TPOT grows only about 2 times, so total throughput grows about 55 times. The bound grows too, because 128 caches of 512 tokens add 2.1 GB to each step. The points in the middle are noisy. TPOT vs context: with grouped attention the step barely grows up to 16K tokens of context for one sequence. The dashed lines repeat K and V four times before attention (the naive way to run grouped-query attention); at long contexts and batch 16 this is many times slower. The readout lists every point and its ratio to the bound.
What the curves say
- TTFT grows with the number of prompt tokens in the batch. For one sequence, TTFT went from 46 ms at 128 tokens to 1,161 ms at 4,096. [Certain, our run] Prefill is compute-bound from a few hundred tokens on (Part 4), so its time follows the FLOPs, and the FLOPs follow \(B \times P\) (plus the \(T^2\) attention term, which matters at long prompts).
- TPOT grows much more slowly than the batch. At 512 tokens of context, one sequence took 20.1 ms per step and 128 sequences 46.5 ms. [Certain, our run] So 128 users get 55 times the total tokens per second of one user, while each of them waits only about twice as long per token. This is the whole reason for batching (session 84). The bound for batch 1 is 10.7 ms; we are at 1.9× the bound, mostly because of the launch overhead of Figure 2.
- Long contexts cost bytes, and kernels decide how many. One sequence at 16K context adds \(16{,}384 \times 32\) KiB = 0.54 GB to each step’s 2.47 GB of weights: about 22% more bytes. With the grouped kernel we measured 26.6 ms; with K and V repeated four times, 176 ms. The naive version writes and reads a four-times larger copy of the cache in every layer, every step.
One decode step, batch 1, context 512. Bytes: \(Q = 2 \times 1{,}235{,}746{,}816 + 512 \times 32{,}768 = 2.488\) GB (formula 87.3; \(N_{mm}\) leaves out the norms). With our measured bandwidth of 233 GB/s: \(2.488 / 233 = 10.7\) ms. FLOPs: \(2 \times 1.236 \times 10^9 + 4 \cdot 16 \cdot 2048 \cdot 512 = 2.54\) GFLOP, which at 29.2 TFLOP/s takes 0.09 ms. Memory wins by about 123 times.
Measured: 20.1 ms, so 1.9× the bound, or 53% of the bandwidth. On this machine about half of the step is not memory traffic: it is launch overhead and small kernels that do not reach full bandwidth. The bound tells you that a perfect implementation could run at most 1.9 times faster; it could not run 10 times faster.
Part 3: measure your GPU and draw its roofline
The roofline needs two numbers: how many bytes per second the GPU can move, and how many FLOPs per second it can compute. Spec sheets give peak values; we measure what we can actually reach, because the measured values are what limit your code.
- Read the symbols
- \(n, s\)
- number of elements copied and bytes per element; a copy reads and writes each byte once, hence the 2
- \(t_{\text{copy}}, t_{\text{matmul}}\)
- best measured time of
y.copy_(x)and of the matrix multiply - \(M, K, N\)
- the matmul shape: an \(M \times K\) matrix times a \(K \times N\) matrix; each output needs \(K\) multiply-adds, 2 FLOPs each
Use a big copy (1 GiB here) so that the fixed launch cost is negligible and caches cannot hold the data. Use a big square matmul (4096 or larger) for the compute roof.
Bandwidth. Copying 1 GiB of BF16 (\(2^{29}\) elements) moves 2.15 GB. Our best copy reached 233 GB/s; a pure read (x.sum()) reached 216 GB/s. Apple lists the M5 Pro with memory bandwidth “up to 307 GB/s” [Certain], so we reach about 76% of the spec. Reaching 70 to 90% of the spec bandwidth in a simple copy is typical for GPUs [Likely].
Compute. A \(4096 \times 4096\) BF16 matmul (\(2 \cdot 4096^3 = 137.4\) GFLOP) reached 26.1 TFLOP/s, and the best shape in our sweep (\(M = 1,024\), see below) 29.2 TFLOP/s. We use 29.2 as the roof.
Ridge. \(I^* = F / \text{BW} = 29.2 \times 10^{12} / 233 \times 10^{9} = 125\) FLOP per byte. For comparison, from the spec sheets: H100 SXM 295, L4 403, A100 153. A pass needs more than 125 FLOPs per byte moved to be compute-bound on our machine.
Then measure the roofline itself, not only its two ends. Multiply an \(M \times 8192\) matrix by a fixed \(8192 \times 8192\) weight for \(M = 1, 2, 4, \dots, 4096\). This is exactly a linear layer applied to \(M\) tokens. Its intensity is
because the weight (\(KN\) numbers, 134 MB here) dominates the bytes. So \(M\) tokens give about \(M\) FLOPs per byte. On our machine the sweep went from 0.15 TFLOP/s at \(M = 1\) (an effective 148 GB/s) up to 29.2 TFLOP/s at \(M = 1,024\), The points run parallel to the slanted roof, at about 50 to 75% of it, up to \(M = 128\), then bend onto the flat roof, which they reach at \(M = 1{,}024\); the two largest shapes are a little slower again. [Certain, our run] At \(M = 1\) the effective bandwidth is lower than the copy’s because one 134 MB matrix–vector product is a single short kernel.
- \(\text{BW} \leftarrow\) best of copy(1 GiB); \(\;F \leftarrow\) best of a large matmul // formula (87.8)
- roof: \(P(I) = \min(F,\ I \cdot \text{BW})\) on log-log axes; ridge at \(I^* = F / \text{BW}\)
- for each pass you care about (prefill at \(T\), decode at \(b, c\)):
- count \(F_{\text{pass}}\) and \(Q_{\text{pass}}\) with (87.2) or (87.3); \(\;I \leftarrow F_{\text{pass}} / Q_{\text{pass}}\)
- time the pass with Algorithm 3: \(t\); \(\;\text{achieved} \leftarrow F_{\text{pass}} / t\)
- plot the point \((I, \text{achieved})\); efficiency \(= \text{achieved} / P(I)\)
Part 4: place prefill and decode on the roofline
- Read the symbols
- \(P(I)\)
- the attainable FLOP/s at intensity \(I\): the roof
- \(F_{\text{pass}} / t_{\text{meas}}\)
- the achieved FLOP/s of your measured pass
- efficiency
- how close you are to the roof; it equals the bound time (87.6) divided by the measured time
From (87.2), a prefill of \(T\) tokens has intensity about \(2T/s = T\) in BF16 (more with attention). From (87.3), a decode step has intensity about \(b\) for short contexts, and less when the KV cache bytes grow. So the two phases sit far apart:
- Prefill at 2,048 tokens: \(I \approx 1,679\), far right of our ridge (125). Compute-bound. Measured 534 ms, so 8.0 TFLOP/s achieved, 27% of the roof.
- Decode at batch 1, context 512: \(I = 1.02\), far left. Memory-bound. Achieved 0.13 TFLOP/s, 53% of the slanted roof at that intensity.
- Decode at batch 128: \(I = 70.3\). Still left of our ridge, still memory-bound, but now 7.0 TFLOP/s. Batching moves decode to the right along the slope.
How to read Figure 4
With the defaults, the prefill point (2,048 tokens) sits on the flat roof and the decode point (batch 1) at the far left, low on the slope: about 123 times less FLOP/s. The open circles show the truth on our machine: the measured prefill passes sit below the roof, and the measured decode steps sit at about half the slope. Raise the batch: the decode point climbs the slope; it reaches our ridge near \(b = 710\). Raise the context to 32K with a large batch: the decode point moves back left, because the KV cache bytes grow with \(b \times c\) while the weights are shared. Switch to the H100: the whole roof moves up and its ridge moves right, so more batch is needed before decode becomes compute-bound.
Yuan et al. built the same kind of analysis into a tool (LLM-Viewer) and report it layer by layer for real models: prefill operations are mostly compute-bound, decode operations are memory-bound. [Certain] Your measured roofline tells you something the spec-sheet roofline cannot: how far your software is from the hardware. On our machine, prefill reaches about 27% of the measured roof and decode about 53% of the slope. These two percentages are the targets of the rest of Track 5: better kernels and fewer launches raise them; quantization and smaller caches change the bytes and move the points.
The whole lab in one file
This script runs on an NVIDIA GPU, on Apple silicon (MPS) or, slowly, on a CPU. It is deterministic (fixed seeds) except for the timings. It needs PyTorch 2.x and about 4 GB of GPU memory for the BF16 model (more for the batch-64 decode test). We ran exactly this file on our machine. [Certain]
# lab.py: KV-cached generation, metrics and the roofline (PyTorch 2.x, CUDA, Apple MPS or CPU)
import time, torch, torch.nn as nn, torch.nn.functional as F
class Cfg: # the shape of Llama 3.2 1B (RoPE scaling left out); weights are random
vocab, d, L, h, kv, ff, theta = 128256, 2048, 16, 32, 8, 8192, 500000.0
class Tiny(Cfg):
vocab, d, L, h, kv, ff = 512, 128, 2, 4, 2, 256
class RMSNorm(nn.Module):
def __init__(s, d): super().__init__(); s.w = nn.Parameter(torch.ones(d))
def forward(s, x):
x32 = x.float()
return (x32 * torch.rsqrt(x32.pow(2).mean(-1, keepdim=True) + 1e-5)).type_as(x) * s.w
def rope(pos, dh, theta):
inv = theta ** (-torch.arange(0, dh, 2, device=pos.device).float() / dh)
ang = pos.float()[:, None] * inv[None]
ang = torch.cat([ang, ang], -1)
return ang.cos(), ang.sin()
def rot(x, cos, sin):
a, b = x.chunk(2, -1)
return x * cos + torch.cat([-b, a], -1) * sin
class Block(nn.Module):
def __init__(s, c):
super().__init__(); s.c = c; dh = c.d // c.h
s.n1, s.n2 = RMSNorm(c.d), RMSNorm(c.d)
s.qkv = nn.Linear(c.d, (c.h + 2 * c.kv) * dh, bias=False)
s.o = nn.Linear(c.h * dh, c.d, bias=False)
s.gu = nn.Linear(c.d, 2 * c.ff, bias=False)
s.down = nn.Linear(c.ff, c.d, bias=False)
def forward(s, x, cos, sin, cache=None, start=0):
c = s.c; B, T, _ = x.shape; dh = c.d // c.h; r = c.h // c.kv
q, k, v = s.qkv(s.n1(x)).split([c.h * dh, c.kv * dh, c.kv * dh], -1)
q = q.view(B, T, c.h, dh).transpose(1, 2)
k = k.view(B, T, c.kv, dh).transpose(1, 2)
v = v.view(B, T, c.kv, dh).transpose(1, 2)
cos, sin = cos.to(q.dtype), sin.to(q.dtype)
q, k = rot(q, cos, sin), rot(k, cos, sin)
if cache is not None: # write the new K, V; then read all past ones
K, V = cache
K[:B, :, start:start + T] = k; V[:B, :, start:start + T] = v
k, v = K[:B, :, :start + T], V[:B, :, :start + T]
if T == 1: # decode: group the r query heads of each KV head
a = F.scaled_dot_product_attention(q.view(B, c.kv, r, dh), k, v).view(B, c.h, 1, dh)
else: # prefill: repeat K, V for the r query heads
k, v = k.repeat_interleave(r, 1), v.repeat_interleave(r, 1)
a = F.scaled_dot_product_attention(q, k, v, is_causal=True)
x = x + s.o(a.transpose(1, 2).reshape(B, T, c.d))
g, u = s.gu(s.n2(x)).chunk(2, -1)
return x + s.down(F.silu(g) * u)
class LM(nn.Module):
def __init__(s, c):
super().__init__(); s.c = c
s.emb = nn.Embedding(c.vocab, c.d)
s.blocks = nn.ModuleList(Block(c) for _ in range(c.L))
s.norm = RMSNorm(c.d)
def forward(s, idx, caches=None, start=0):
pos = torch.arange(start, start + idx.shape[1], device=idx.device)
cos, sin = rope(pos, s.c.d // s.c.h, s.c.theta)
x = s.emb(idx)
for i, b in enumerate(s.blocks):
x = b(x, cos, sin, None if caches is None else caches[i], start)
return s.norm(x[:, -1:]) @ s.emb.weight.T # logits of the last position only (tied head)
def build(c, dev, dt, seed=0):
m = LM(c); g = torch.Generator().manual_seed(seed)
for p in m.parameters():
if p.dim() > 1: p.data.copy_(torch.randn(p.shape, generator=g) * 0.02)
return m.to(dev, dt).eval()
def make_cache(c, B, Tmax, dev, dt): # one (K, V) pair per layer: (B, n_kv, Tmax, d_h)
shape = (B, c.kv, Tmax, c.d // c.h)
return [(torch.zeros(shape, device=dev, dtype=dt), torch.zeros(shape, device=dev, dtype=dt))
for _ in range(c.L)]
@torch.no_grad()
def generate_nocache(m, prompt, n):
seq = prompt
for _ in range(n): # the whole sequence, every step
nxt = m(seq)[:, -1].argmax(-1, keepdim=True)
seq = torch.cat([seq, nxt], 1)
return seq[:, prompt.shape[1]:]
@torch.no_grad()
def generate_cache(m, prompt, n):
B, P = prompt.shape; p = next(m.parameters())
caches = make_cache(m.c, B, P + n, p.device, p.dtype)
out = [m(prompt, caches, 0)[:, -1].argmax(-1, keepdim=True)] # prefill fills the cache
for t in range(n - 1): # decode: one token per step
out.append(m(out[-1], caches, P + t)[:, -1].argmax(-1, keepdim=True))
return torch.cat(out, 1)
# ---------- timing helpers ----------
dev = "cuda" if torch.cuda.is_available() else "mps" if torch.backends.mps.is_available() else "cpu"
def sync():
if dev == "cuda": torch.cuda.synchronize()
elif dev == "mps": torch.mps.synchronize()
def bench(f, warmup=2, reps=5): # best (min) wall time of f(), with the GPU queue drained
for _ in range(warmup): f()
sync(); best = float("inf")
for _ in range(reps):
t = time.perf_counter(); f(); sync(); best = min(best, time.perf_counter() - t)
return best
if __name__ == "__main__":
torch.manual_seed(0)
# 1. correctness: both loops must give the same tokens (FP32, tiny model)
tiny = build(Tiny(), dev, torch.float32)
pr = torch.randint(0, 512, (4, 16), generator=torch.Generator().manual_seed(1)).to(dev)
a, b = generate_nocache(tiny, pr, 48), generate_cache(tiny, pr, 48)
print("same tokens:", torch.equal(a, b))
# 2. speed-up of the cache: 128-token prompt, 256 new tokens, 1B shape in BF16
dt = torch.bfloat16 if dev != "cpu" else torch.float32
c = Cfg(); m = build(c, dev, dt)
pr = torch.randint(0, c.vocab, (1, 128), generator=torch.Generator().manual_seed(1)).to(dev)
t_nc = bench(lambda: generate_nocache(m, pr, 256), 1, 2)
t_c = bench(lambda: generate_cache(m, pr, 256), 1, 2)
print(f"no cache {t_nc:.2f} s, cache {t_c:.2f} s, speed-up {t_nc / t_c:.1f}x")
# 3. TTFT = one prefill pass; TPOT = one decode step at context c
with torch.no_grad():
for B in [1, 8]:
for P in [128, 512, 2048]:
p = torch.randint(0, c.vocab, (B, P), device=dev); ca = make_cache(c, B, P + 1, dev, dt)
print(f"TTFT B={B} P={P}: {1e3 * bench(lambda: m(p, ca, 0).argmax(-1)):.1f} ms")
for B in [1, 16, 64]:
ca = make_cache(c, B, 513, dev, dt); tok = torch.zeros(B, 1, dtype=torch.long, device=dev)
print(f"TPOT B={B} c=512: {1e3 * bench(lambda: m(tok, ca, 512).argmax(-1)):.1f} ms")
del ca
# 4. the roofline: bandwidth (copy 1 GiB) and peak matmul speed
x = torch.randn(2**29, device=dev, dtype=dt); y = torch.empty_like(x)
bw = 2 * x.numel() * x.element_size() / bench(lambda: y.copy_(x)) # read + write
A = torch.randn(4096, 4096, device=dev, dtype=dt)
fl = 2 * 4096**3 / bench(lambda: A @ A)
print(f"bandwidth {bw / 1e9:.0f} GB/s, matmul {fl / 1e12:.1f} TFLOP/s, ridge {fl / bw:.0f} FLOP/byte")
W = torch.randn(8192, 8192, device=dev, dtype=dt)
for M in [1, 8, 64, 512, 4096]: # X (M, 8192) @ W: intensity about M FLOP/byte
X = torch.randn(M, 8192, device=dev, dtype=dt)
t = bench(lambda: X @ W.T)
I = 2 * M * 8192**2 / (2 * (8192**2 + 2 * M * 8192))
print(f"M={M:5d} I={I:7.1f} FLOP/B {2 * M * 8192**2 / t / 1e12:6.2f} TFLOP/s")
The output of one run of this file on our machine. Other jobs were using the machine at the same time, so these single-run numbers are noisier and slower than the best-of-repeats numbers in the text and the figures, which come from a longer benchmark with the same model and the same measurements. Your numbers will differ.
same tokens: True
Things to try next, each a few lines of change: time the decode step with torch.compile on a CUDA GPU and see how much of the gap to the bound was launch overhead; replace the grouped decode attention with the repeat version and reproduce the TPOT-vs-context gap of Figure 3; store the cache in FP8 and see how TPOT at long context changes; add a timer around the argmax and the .item() that a real server needs, and see what fraction of TPOT it is.
Where this is used
| Where | What you measure | What it decides |
|---|---|---|
| Choosing a GPU for serving | Bytes per decode step and your measured bandwidth | TPOT and cost per token; the bandwidth ratio predicts the decode speed-up between two GPUs |
| Capacity planning (session 81) | TTFT vs prompt length, TPOT vs batch | The largest batch that meets a latency target, and so requests per GPU |
| Serving engines (vLLM, SGLang, TensorRT-LLM) | Benchmark scripts that report TTFT, TPOT and ITL percentiles [Certain] | Scheduler settings: batch size, chunked-prefill size, CUDA graphs |
| Kernel work (session 86) | Achieved bandwidth or FLOP/s against the measured roof | Whether a kernel is worth optimizing further |
| Long-context and video models | Prefill time for very long inputs (thousands of visual tokens per video), KV bytes per step | Whether to compress visual tokens, use a smaller cache, or split prefill into chunks; video question answering and Video-RAG send long prompts, so TTFT dominates |
| On-device inference (laptops, phones) | Bandwidth of unified memory, launch overhead | Model size and quantization: decode speed is about bandwidth divided by model bytes |
| Performance regression tests | The same fixed-shape benchmark after every change | Catches a slower kernel or a missing cache before users do |
Common mistakes
- No synchronize before stopping the clock. You measure Python, not the GPU (Figure 2). The numbers look too good, and they do not change when you change the model size.
- No warm-up. The first call includes memory allocation and kernel selection or compilation. A single cold run can be several times slower than the steady state.
- Testing the cache in BF16 with exact token equality. Order-of-addition differences can flip a near-tie, and then the texts differ. Test the logic in FP32; test BF16 with a logit tolerance.
- Using
is_causal=Truewhen the query is shorter than the keys. In PyTorch the causal mask is aligned to the top-left, so a one-token query over a cache would see only the first key. Decode needs no mask at all (all cached keys are in the past); a chunk of several new tokens needs an explicit mask shifted by the cache length. - Timing one whole
generate()and calling it “TPOT”. The total mixes prefill, decode at many context lengths and Python overhead. Time the phases separately, at fixed shapes. - Measuring bandwidth with a small tensor. A 64 MB copy stays partly in on-chip caches or is dominated by launch cost; our first try with a 64 MB tensor gave a lower number than the 1 GiB copy. Use at least several hundred MB.
- Comparing your measurement with the spec-sheet peak only. Then a well-written kernel looks bad. Compare with your measured roof, and report both.
- Expanding grouped \(K\) and \(V\) before attention.
repeat_interleavemakes a full-size copy of the cache in every layer, every step; at long contexts it costs more than the attention itself (Figure 3, TPOT vs context).
Interview questions
Why can greedy generation with and without a KV cache give different tokens, and how do you test a cache implementation?basic
The KV cache saves more than 99% of the FLOPs. Why can the measured speed-up be only 2 to 4 times?core
How do you measure the time of a GPU operation correctly in PyTorch?basic
.item() inside the timed region unless it belongs to what you measure, and make sure other jobs are not sharing the GPU.How would you measure your GPU’s memory bandwidth, and why is it below the spec?core
y.copy_(x), take the best of several runs, and divide \(2 \times\) the bytes by the time (one read and one write per byte). Also time a pure read such as a sum. The result is typically 70 to 90% of the spec [Likely], because the spec is the raw interface rate and real traffic has refresh cycles, row switches, and read/write turnarounds. On our M5 Pro we measured 233 GB/s against a spec of 307 GB/s. Use a large tensor; small ones fit in caches or are dominated by launch cost.What is the arithmetic intensity of a decode step, and how does batching change it?core
Why does TTFT grow linearly with prompt length while TPOT barely grows with context length?basic
Your measured TPOT is twice the bandwidth bound. What do you check?advanced
torch.compile(mode="reduce-overhead"), and fuse small operations. Then check each kernel’s achieved bandwidth: matrix-vector products at batch 1 often do not reach full bandwidth; the attention over the cache may copy K and V (for example repeating them for grouped heads); RoPE and norms may be separate memory-bound kernels. Finally check for host syncs inside the step, such as .item() or Python conditions on GPU values.Where on the roofline do prefill and decode sit, and what optimizations does each position suggest?core
Why do we time a decode step at a fixed context, instead of averaging over a full generation?advanced
A laptop GPU and a data-center GPU: which ratio predicts the speed-up of decode, and which predicts prefill?core
Exercises
- Use (87.5) to estimate the FLOP ratio between the no-cache and the cached loop for \(P = 2048\) and \(n = 256\). Then use Figure 1 to find the best-case time ratio on an H100. Why are they so different?
- Our model has 8 KV heads of size 64 in 16 layers. What would \(\text{kv}_{\text{tok}}\) be with 32 KV heads (plain multi-head attention)? At a 16K context and batch 1, by how much would the bytes of one decode step grow?
- A colleague reports a TPOT of 0.8 ms for the lab model on our laptop. Using the bound, explain why the number must be wrong, and name the most likely mistake.
- Compute the intensity (87.9) of the matmul sweep at \(M = 64\) and \(M = 1024\) with \(K = N = 8192\) in BF16. On our measured roof, which one is memory-bound?
- For the H100 (989 TFLOP/s, 3.35 TB/s), at what batch does a decode step of the lab model at context 512 reach the ridge? Use (87.3). Could it be reached at context 32K?
- Run the lab file on your GPU. Write down your bandwidth, matmul speed and ridge, and the ratio of your measured TPOT (batch 1) to its bound. Is your loop closer to the bound than ours?
Answerscheck
Key takeaways
- Write the cached loop as one prefill that fills a preallocated cache, then one-token decode steps that write at position \(P + i - 1\) and read everything before. Test it in FP32 for exact token equality; BF16 can flip near-ties.
- The cache saves about \((nP + n^2/2)/(P+n)\) times the FLOPs, but the time saved depends on whether the no-cache steps were compute-bound. On our laptop: 32.5 s against 7.75 s, 4.2×.
- Time GPUs with warm-up, synchronization and repeats. Without a sync you measure Python. With a sync every step you see the launch overhead that a real loop pays.
- TTFT grows with the prompt tokens in the batch (compute-bound). TPOT grows much more slowly than the batch (memory-bound: the weights are read once per step and shared), so batching multiplies throughput.
- Measure your roof: a 1 GiB copy for bandwidth, a large matmul for FLOP/s. Ours: 233 GB/s, 29.2 TFLOP/s, ridge 125.
- Prefill sits on the flat roof (\(I \approx T\)), decode on the slope (\(I \approx b\)). The ratio of your measured time to the bound is the most useful single number for deciding what to optimize.
Key formulas
References for this session
- Raschka, Build a Reasoning Model (From Scratch), chapter E: Batching and throughput-oriented execution
- Yuan et al. (2024). LLM Inference Unveiled: Survey and Roofline Model Insights
- Raschka, Build a Reasoning Model (From Scratch), chapter E: Batching and throughput-oriented execution
- Yuan et al. (2024). LLM Inference Unveiled: Survey and Roofline Model Insights
- Williams et al. (2009). Roofline: An Insightful Visual Performance Model for Multicore Architectures
- Zhou, Ning, Hong et al. (2024). A Survey on Efficient Inference for Large Language Models
- Kwon et al. (2023). Efficient Memory Management for Large Language Model Serving with PagedAttention
- Meta (2024). Llama 3.2 1B model card and config.json (Hugging Face)
- PyTorch (2024). Scaled dot-product attention in torch.nn.functional (documentation)
- Apple (2026). Apple debuts M5 Pro and M5 Max (press release, memory bandwidth up to 307 GB/s)