LLM serving: KV cache, batching, paged attention and quantization

Before this lesson: lesson 08 (the KV cache, grouped-query attention, why caching is exact) and lesson 12 (bytes per parameter, rooflines, tensor parallelism). The full theory is in the ML Systems track: the roofline model, quantization and inference serving; queueing is also in MLOps 05. Time: about 85 minutes, plus the notebook.

---

Why this matters #

"Design the inference system for our chat model." "How many GPUs do we need for 10 requests per second?" "GPU utilization is 30% during decoding. Why?" "Which quantization would you use?" These are standard questions in LLM infrastructure, ML engineer and research engineer rounds. A popular model is trained once but serves billions of tokens every day, so serving often costs more than training. The answers are arithmetic on a few numbers: the bytes of the weights, the bytes of the KV cache, and the GPU's FLOP/s against its memory bandwidth. Add continuous batching and paging, and you can explain how vLLM, SGLang and TensorRT-LLM work.

1. Predict first #

2. The picture #

Generation has two phases (lesson 08). Prefill runs the whole prompt in one forward pass, writes the keys and values of every prompt token to the cache, and gives the first output token. Decode makes one token per step for each sequence; every step reads all the weights and the whole cache of every sequence in the batch.

The roofline. A GPU operation takes at least $\max(\text{FLOPs}/F,\ \text{bytes}/\text{BW})$, where $F$ is the peak FLOP/s and BW the memory bandwidth in bytes/s. The arithmetic intensity of an operation is its FLOPs per byte moved. When it is below $F/\text{BW}$, the operation is memory-bound.

GPU	$F$ (dense, bf16)	BW (HBM)	$F/\text{BW}$
A100-80GB SXM	312 TFLOP/s	2.04 TB/s	153 FLOP/byte
H100 SXM	989 TFLOP/s	3.35 TB/s	295 FLOP/byte

Simplest case: one sequence, one weight matrix. Decode multiplies a $1 \times d$ vector by a $d \times d$ matrix: $2d^2$ FLOPs, but $2d^2$ bytes of bf16 weights to read. That is 1 FLOP per byte, far below 153: the arithmetic units are idle more than 99% of the time. With $B$ sequences in the batch, each loaded weight is used $B$ times, so the intensity is about $B$. Serving is therefore about batching, and the batch is limited by KV-cache memory.

The memory of a serving GPU has three parts: the weights (fixed), activations and workspace (small), and the KV cache (the rest). The cache grows by one token per step for every running sequence.

An inference engine (vLLM, SGLang, nano-vllm) has four parts: an API server that receives requests and streams tokens back; a scheduler that decides, at every step, which sequences run; a KV-cache manager that gives out memory blocks; and a model runner that does one forward pass over all scheduled tokens and samples the next tokens.

Interactive figure: loading…

3. Definitions and main results #

Notation. $L$ layers; $n_h$ query heads; $n_{kv}$ key/value heads ($n_{kv} = n_h$ for multi-head attention, fewer for grouped-query attention, GQA, where $n_h/n_{kv}$ query heads share one key and value head); $d_h$ head dimension; $d = n_h d_h$ model width; $b$ bytes per stored number (2 for bf16); $\Psi$ parameters; $B$ sequences in a decode batch; $C$ average number of cached tokens per sequence; $k$ KV bytes per token; $F$ peak FLOP/s; BW memory bandwidth. 1 GB $= 10^9$ bytes.

3.1 Latency and throughput #

• TTFT (time to first token) $=$ queueing $+$ prefill. The user sees the answer start.
• TPOT (time per output token, also inter-token latency) $=$ the time between streamed tokens $\approx$ the decode step time.
• End-to-end latency $=$ TTFT $+ (n_{\text{out}} - 1) \times$ TPOT for $n_{\text{out}}$ output tokens.
• Throughput $=$ output tokens per second over all requests; it sets the cost.
• Goodput $=$ requests per second that meet the latency targets (the SLO, service-level objective). Report percentiles (p50, p99), not only means.

3.2 KV-cache memory #

Each layer stores one key and one value vector of size $d_h$ per KV head and per token:

The tokens that fit are $(M_{\text{GPU}} - M_{\text{weights}} - M_{\text{act}})/k$. GQA divides $k$ by $n_h/n_{kv}$; an fp8 cache halves $b$. Example: Llama-2-13B ($L = 40$, $n_{kv} = n_h = 40$, $d_h = 128$) stores $2 \cdot 40 \cdot 40 \cdot 128 \cdot 2 = 819{,}200$ bytes = 800 KiB per token. The vLLM paper (§3) gets the same 800 KiB for OPT-13B. One 4,096-token sequence needs 3.4 GB, 13% of the 26 GB of weights.

3.3 Prefill is compute-bound, decode is memory-bound #

Theorem (arithmetic intensity of serving). With $b = 2$ (bf16): (a) a weight matmul applied to $B$ tokens at once has intensity $\approx B$ FLOP/byte when $B$ is much smaller than the matrix dimensions; (b) decode attention over $t \gg 1$ cached tokens, where each sequence reads its own cache, has intensity $n_h/n_{kv}$ FLOP/byte, for every batch size and every context length. So a prefill of more than $F/\text{BW}$ tokens is compute-bound; decode is memory-bound in the weight matmuls unless $B > F/\text{BW}$, and always memory-bound in attention.

Proof.

1. A weight $W$ of size $d_{\text{in}} \times d_{\text{out}}$ applied to activations $X$ of size $B \times d_{\text{in}}$ costs $2 B d_{\text{in}} d_{\text{out}}$ FLOPs (one multiply and one add per term).
2. It moves $b\,(d_{\text{in}} d_{\text{out}} + B d_{\text{in}} + B d_{\text{out}})$ bytes: the weight, the input and the output.
3. Divide, then divide the numerator and the denominator by $b\,d_{\text{in}} d_{\text{out}}$: the intensity is $\dfrac{2B/b}{1 + B/d_{\text{out}} + B/d_{\text{in}}} \approx \dfrac{2B}{b} = B$ when $B \ll d_{\text{in}}, d_{\text{out}}$. In prefill, $B$ is the number of prompt tokens; in decode, the number of sequences in the batch. This proves (a).
4. Decode attention for one new token over $t$ cached tokens, in one layer: each of the $n_h$ query heads computes $q^\top K$ ($2 t d_h$ FLOPs) and the weighted sum of the values ($2 t d_h$ FLOPs). Total: $4 t d_h n_h$ FLOPs.
5. It reads the sequence's own keys and values: $2 t d_h n_{kv} b$ bytes. Every sequence has a different cache, so nothing is reused across the batch. (The query and the output, $O(n_h d_h)$ bytes, are negligible next to the $O(t)$ cache bytes.)
6. The intensity is $\dfrac{4 t d_h n_h}{2 t d_h n_{kv} b} = \dfrac{n_h}{n_{kv}}$ for $b = 2$: 1 for multi-head attention, 8 for GQA with groups of 8. Both are far below 153 or 295. $\blacksquare$

Decode step-time model. Each step reads all weights once and the cache of every sequence:

TPOT $\approx t_{\text{step}}$ and throughput $= B/t_{\text{step}}$. The weight term is shared by the whole batch; the KV term grows with $B$. So throughput first grows almost linearly with $B$, then flattens when the KV term dominates. And $B$ is capped by the KV memory: this is the latency–throughput trade-off of serving.

Prefill time $\approx 2\Psi T/(\text{MFU} \cdot F)$ for a prompt of $T$ tokens, where MFU is the fraction of peak FLOP/s achieved. Causal attention adds about $2LT^2d$ FLOPs, small unless $T$ is many thousands of tokens.

3.4 Continuous batching #

Static (request-level) batching forms a batch and runs it until its longest sequence ends. Two kinds of waste:

• Finished sequences keep their slot. With output lengths 10, 20, 50 and 200 tokens, the batch runs 200 steps $\times$ 4 slots $=$ 800 slot-steps for 280 useful tokens: 35% use.
• New requests wait until the whole batch ends (head-of-line blocking), which hurts TTFT.

Continuous batching (iteration-level scheduling; Orca, Yu et al., 2022) lets the scheduler decide again after every step. A finished sequence leaves at once, and a waiting request joins at the next step (its prefill runs in that step). This needs attention kernels that handle sequences of different lengths without padding, and a KV manager that can give memory to any sequence at any step. Paging gives exactly that.

Interactive figure: loading…

3.5 Paged attention #

Earlier servers stored the cache of each request as one contiguous tensor sized for its maximum length. The vLLM paper (Kwon et al., 2023, §3.1) names three kinds of waste:

• reserved slots: space for future tokens, held for the whole life of the request;
• internal fragmentation: space for the maximum length that the request never uses;
• external fragmentation: gaps between buffers of different sizes, left by the allocator.

In their measurements only 20.4–38.2% of the KV memory of existing systems held real token states.

PagedAttention borrows virtual memory from operating systems:

• KV memory is a pool of fixed-size physical blocks (vLLM's default: 16 tokens).
• Each sequence has a block table: logical block $i$ (tokens $16i, \dots, 16i + 15$) $\to$ a physical block id. The blocks of a sequence need not be next to each other.
• A sequence gets a new block only when its last block is full.
• The attention kernel follows the block table and reads keys and values one block at a time.

Waste bound. With blocks of $B_s$ tokens, a sequence of $n$ tokens uses $\lceil n/B_s \rceil$ blocks. Its waste is $B_s \lceil n/B_s \rceil - n \le B_s - 1$ tokens: less than one block, instead of (maximum length $- n$) with reservation.

Sharing. A physical block can belong to several sequences; a reference count says how many.

• Parallel sampling ($n$ answers to one prompt) and beam search share the prompt's blocks.
• Copy-on-write: before a sequence writes into a block whose reference count is above 1, it gets a private copy, and the count of the shared block drops by 1.
• Prefix caching: a full block is identified by a hash of its tokens and of all tokens before it. A new request whose prompt starts with the same tokens (a system prompt, few-shot examples, earlier chat turns) reuses those blocks and skips their prefill. SGLang keeps the prefixes in a radix tree (RadixAttention).

Interactive figure: loading…

Preemption. When no block is free, the scheduler must stop some sequences. vLLM serves requests first come, first served, so it preempts the most recently arrived request first, and it evicts all blocks of a sequence or none. Later it restores them by swapping them back from CPU memory, or by recomputation: one prefill over the prompt plus the tokens generated so far.

The step loop of a small server (vLLM §4.5):

1. Remove finished sequences and free their blocks (decrease the reference counts).
2. For every running sequence whose last block is full, allocate a block. If none is free, preempt the most recently admitted running sequence and try again.
3. If nothing was preempted, admit waiting requests from the head of the queue while blocks for their prompts are free and the batch is below its maximum size.
4. Run one forward pass over all scheduled tokens: whole prompts (or prompt chunks) for new requests, one token for every decoding sequence.
5. Sample one token per sequence, append it, check the stop conditions, stream the token.

3.6 Prefill interference: chunked prefill and disaggregation #

A long prefill in the same step as many decodes delays all their tokens: a TPOT spike for every running request. Two fixes:

• Chunked prefill (Sarathi-Serve, Agrawal et al., 2024): split prompts into chunks (for example 512 tokens) and fill every step up to a token budget, decode tokens first, then a prefill chunk. Decode steps are memory-bound, so their unused compute absorbs the chunk almost for free.
• Prefill/decode disaggregation (DistServe, Splitwise, 2024): separate GPU pools for prefill and decode; the KV cache is sent from the prefill GPU to a decode GPU. Each pool is tuned for its own bottleneck and target (TTFT or TPOT). The cost is the KV transfer and a more complex system.

3.7 Quantization for serving #

Uniform symmetric quantization with $n$ bits: scale $s = \max|w|/(2^{n-1} - 1)$, integer $q = \operatorname{round}(w/s)$, reconstruction $\hat w = sq$. Inside the range, $|w - \hat w| \le s/2$. One scale per output channel, or per group of 128 weights, keeps a single large weight from making the scale large for all the others. int4 with one bf16 scale per group of 128 costs $4 + 16/128 = 4.125$ bits per weight.

What each scheme speeds up follows from section 3.3:

Scheme	Stored in low precision	Matmuls run in	Speeds up	Typical use
weight-only int8 / int4 (GPTQ, AWQ)	weights	bf16 (dequantized inside the kernel)	memory-bound decode at small and medium batch; frees memory for the cache	chat at low batch; a larger model on one GPU
W8A8: int8 (SmoothQuant) or FP8	weights and activations	8-bit tensor cores, $2\times$ the bf16 FLOP/s	compute-bound prefill and large-batch decode	high-throughput serving on H100-class GPUs
fp8 / int8 KV cache	keys and values	bf16	$2\times$ tokens in memory, half the KV read time	long contexts, large batches

Activation outliers (a few channels up to about 100 times larger than the rest) make per-tensor int8 activations inaccurate. SmoothQuant moves part of their range into the weights with an exact rescaling, $XW = (X \operatorname{diag}(s)^{-1})(\operatorname{diag}(s) W)$. After quantizing, check quality on the task evaluation, not only on perplexity.

3.8 Other levers #

• GQA or MQA (multi-query attention, $n_{kv} = 1$): $n_h/n_{kv}$ times less KV cache, and decode attention intensity $n_h/n_{kv}$. It is a model choice, made at training time.
• Tensor parallelism: a model too large for one GPU is split over $t$ GPUs of one node. Each GPU reads $1/t$ of the weights per step (a shorter step) and holds $n_{kv}/t$ of the KV heads (when $n_{kv} \ge t$; otherwise KV heads are copied). The cost is two all-reduces per layer (lesson 12).
• Multi-LoRA serving: one shared base model and many small adapters, batched together with special kernels (S-LoRA, Punica), instead of one merged model copy per adapter.

Speculative decoding. A small draft model proposes $\gamma$ tokens; the target model checks all of them in one forward pass. A rejection-sampling rule accepts each draft token with probability $\min(1, p(x)/q(x))$ (target over draft probability) and, at the first rejection, samples a correction from an adjusted distribution. The output has exactly the target model's distribution (Leviathan et al., 2023; Chen et al., 2023).

Result (expected tokens per target pass). If each draft token is accepted with probability $\alpha$, independently, the expected number of tokens per target pass is

1. Let $X$ be the number of accepted draft tokens. The first $i$ are all accepted with probability $\alpha^i$, so $P(X \ge i) = \alpha^i$ for $0 \le i \le \gamma$.
2. Every pass yields $X + 1$ tokens: the accepted ones plus one from the target (the correction at the first rejection, or a bonus token when all $\gamma$ are accepted).
3. For a count $Y \ge 1$, $\mathbb{E}[Y] = \sum_{i \ge 1} P(Y \ge i)$. With $Y = X + 1$: $\mathbb{E}[Y] = \sum_{i=0}^{\gamma} P(X \ge i) = \sum_{i=0}^{\gamma} \alpha^i$.
4. The geometric sum is $(1 - \alpha^{\gamma+1})/(1 - \alpha)$. $\blacksquare$

For $\alpha = 0.8$, $\gamma = 4$: 3.36 tokens per pass. If a draft pass costs $c$ times a target pass, the speed-up is $\mathbb{E}[\text{tokens}]/(\gamma c + 1)$. It helps most at small batch, where decode is memory-bound and checking $\gamma + 1$ tokens costs about as much as checking 1.

Interactive figure: loading…

3.9 Capacity: Little's law and queueing #

Little's law. For any stable system in steady state, the average number of requests in the system $L$, the arrival rate $\lambda$ and the average time in the system $W$ satisfy

It turns traffic into concurrency: 10 requests/s that each stay 8.5 s means 85 sequences in the batch on average, and so a KV-memory need.

Result (M/M/1 latency). Requests arrive as a Poisson process with rate $\lambda$; one server serves them first come, first served, with exponential service times of mean $S = 1/\mu$; the utilization is $\rho = \lambda/\mu < 1$. Then the mean time in the system is

1. The number in the system $N$ is a birth–death chain: up at rate $\lambda$, down at rate $\mu$ when $N > 0$. In steady state the flow from level $n$ to $n + 1$ equals the flow back: $\lambda P(n) = \mu P(n+1)$, so $P(n) = (1 - \rho)\rho^n$.
2. $\mathbb{E}[N] = \sum_n n(1 - \rho)\rho^n = \rho/(1 - \rho)$.
3. Little's law gives $W = \mathbb{E}[N]/\lambda = \frac{1}{\mu(1 - \rho)} = \frac{1}{\mu - \lambda}$. $\blacksquare$

The time in the system is in fact exponential with rate $\mu - \lambda$, so its 95th percentile is $\ln 20/(\mu - \lambda) \approx 3/(\mu - \lambda)$. Two lessons. $W$ grows like $1/(1 - \rho)$, so latency explodes near full utilization: plan for $\rho$ around 0.6–0.8. And a faster model helps twice: it shortens the service and it lowers $\rho$. Model inference has nearly constant service times, which queue less (M/D/1: the waiting part is half that of M/M/1), so M/M/1 is a pessimistic estimate.

Interactive figure: loading…

Answers to section 1. (1) About 17 ms. The step reads the 26 GB of weights in 12.7 ms at 2.04 TB/s, whatever the batch size; 16 caches of 640 tokens add $16 \times 640 \times 819{,}200$ bytes $= 8.4$ GB, another 4.1 ms. Throughput rises from 77 to about 950 tokens/s. (2) $61{,}035/4{,}096 = 14$ requests with reservation; $61{,}035/768 = 79$ with 16-token blocks, 5.6 times more.

4. Worked example #

(a) Size a chat deployment #

Prompt. "Serve a 13B chat model (Llama-2-13B shape: $L = 40$, $n_h = n_{kv} = 40$, $d_h = 128$, context up to 4,096 tokens) on A100-80GB GPUs. Peak traffic: 10 requests per second; prompts of 512 tokens and outputs of 256 tokens on average. Target: TPOT $\le$ 50 ms. How many GPUs, and what would you change?"

Step 1 — memory. Weights: $13 \cdot 10^9 \times 2$ bytes $= 26$ GB. Assume 50 GB remain for the cache after activations and the runtime. $k = 819{,}200$ bytes per token, so $50 \cdot 10^9/819{,}200 = 61{,}035$ tokens fit.

Step 2 — concurrent sequences per GPU. Reserving 4,096 tokens per request: 14 sequences. Paged, counting each request at its final length of 768 tokens: 79 sequences.

Step 3 — decode step. Take $C = 640$ cached tokens on average (512 prompt + half of 256). Each sequence adds $640 \times 819{,}200 = 524$ MB of reads, 0.257 ms; the weights take 12.75 ms. So $t_{\text{step}}(B) \approx 12.75 + 0.257\,B$ ms:

$B$	step (ms)	output tokens/s	compute at peak (ms)
1	13.0	77	0.1
14 (reservation)	16.3	857	1.2
79 (paged)	33.0	2,390	6.6
144	49.8	2,894	12.0

TPOT $\le$ 50 ms allows $B \le 144$, but memory allows only 79: KV memory binds, not latency. The compute at $B = 79$ takes 6.6 ms, far below the 33 ms of memory traffic: memory-bound, as the theorem says.

Step 4 — prefill. $2 \times 13 \cdot 10^9 \times 512 = 1.33 \cdot 10^{13}$ FLOPs. At 50% MFU this takes 85 ms; the intensity is about 512, above 153, so it is compute-bound. TTFT $\approx$ queueing $+$ 85 ms.

Step 5 — number of GPUs.

• Little's law: a request stays about $0.085 + 255 \times 0.033 \approx 8.5$ s, so $10 \times 8.5 = 85$ sequences are active at peak: more than the 79 that fit on one GPU.
• Work per second: prefill $10 \times 85$ ms $= 0.85$ GPU-seconds per second; decode $2{,}560/2{,}390 = 1.07$ GPUs (10 requests/s $\times$ 256 tokens). Total about 1.9 GPUs busy, an upper bound, because chunked prefill hides part of the prefill inside memory-bound decode steps.
• With about 30% headroom: 3 A100s, each with its own copy of the model, behind a load balancer. Without paging (14 sequences, 857 tokens/s per GPU) decode alone would need 3 GPUs, about 4 in total and 5–6 with headroom. Paging gives 2.8 times the decode throughput here, inside the 2–4 times range that the vLLM paper reports.

Step 6 — levers on the binding limit (KV memory). Keep 768 tokens per request for capacity and 640 for the step time:

Change	KV memory	sequences	step (ms)	tokens/s per GPU
baseline (bf16 weights and cache)	50 GB	79	33.0	2,390
int8 weights (13 GB freed)	63 GB	100	32.1	3,118
int8 weights + fp8 cache	63 GB	200	32.1	6,236

With 200 sequences the compute is 16.7 ms, still below the 32.1 ms of memory traffic. Other levers: a model with GQA (8 KV heads instead of 40 store 5 times less), prefix caching of a shared system prompt, and a limit on the output length.

(b) Size a simple model endpoint #

A model endpoint (for example an embedding model or a classifier, one request at a time) gets $\lambda = 40$ requests/s at peak; the target is p95 $\le$ 150 ms.

• fp32 model, service time 20 ms ($\mu = 50$), one replica: $\rho = 0.8$, $W = 1/(50 - 40) = 100$ ms, p95 $= \ln 20/10 \approx 300$ ms. Fails. Two replicas with random routing (20 requests/s each): $W = 1/30 \approx 33$ ms, p95 $\approx 100$ ms. Passes.
• int8 model, 10 ms ($\mu = 100$), one replica: $\rho = 0.4$, $W = 1/60 \approx 16.7$ ms, p95 $\approx 50$ ms. Passes.
• Little's law: on average $L = \lambda W = 4$ requests are in the fp32 system, 0.67 in the int8 one.
• A 2 times faster model gives a 6 times lower mean latency at one replica, and needs half the replicas.

5. In code #

NumPy checks the numbers of the worked example, the intensity theorem, the quantization error, and the queueing and speculative-decoding results. The notebook has these cells and the exercises.

import numpy as np

# Llama-2-13B shape on one A100-80GB, bf16 weights and cache
L, n_h, n_kv, d_h = 40, 40, 40, 128
params, BW, F = 13e9, 2.04e12, 312e12              # parameters, HBM bytes/s, peak bf16 FLOP/s
w_bytes = 2 * params                                # 26 GB of weights
k = 2 * L * n_kv * d_h * 2                          # KV bytes per token: K and V, every layer, bf16
print(k, k / 1024)                                  # 819200 800.0 (KiB)

tokens = 50e9 / k                                   # 50 GB left for the cache
print(int(tokens), int(tokens // 4096), int(tokens // 768))   # 61035 14 79

# decode step: read the weights once and every sequence's cache (640 tokens); compare compute
B = np.array([1, 14, 79, 144])
mem_ms = 1e3 * (w_bytes + B * 640 * k) / BW
comp_ms = 1e3 * 2 * params * B / F
print(mem_ms.round(1), comp_ms.round(1), (B / mem_ms * 1e3).round())
# [13.  16.3 33.  49.8] [ 0.1  1.2  6.6 12. ] [  77.  857. 2390. 2894.]

prefill_ms = 1e3 * 2 * params * 512 / (0.5 * F)     # 512-token prompt at 50% MFU
e2e_s = prefill_ms / 1e3 + 255 * mem_ms[2] / 1e3    # TTFT + 255 more tokens at B = 79
print(round(prefill_ms, 1), round(e2e_s, 2), round(10 * e2e_s))   # 85.3 8.51 85 (Little, 10 req/s)

# intensity of a weight matmul on B tokens (bf16): about B FLOPs per byte
d = 5120
for b in (1, 16, 153, 512):
    print(b, round(2 * b * d * d / (2 * (d * d + 2 * b * d)), 1))   # 1.0, 15.9, 144.4, 426.7

At $B = 153$ the intensity is 144, not 153, because the input and output bytes (step 3 of the proof) are no longer negligible.

import numpy as np

# symmetric int8 weights: per-tensor vs per-channel scales, with one outlier row
rng = np.random.default_rng(0)
w = rng.normal(size=(256, 512))
w[3] *= 50                                          # one output channel with large weights
def fake_quant(w, s):                               # round to the int8 grid and map back
    return s * np.clip(np.round(w / s), -127, 127)
s_t = np.abs(w).max() / 127                         # one scale for the whole tensor
s_c = np.abs(w).max(axis=1, keepdims=True) / 127    # one scale per row (output channel)
for name, s in (("per-tensor", s_t), ("per-channel", s_c)):
    err = np.abs(w - fake_quant(w, s))
    print(name, bool((err <= s / 2 + 1e-12).all()), round(err[4:].mean(), 4))
# per-tensor True 0.307      mean error on the normal rows, where |w| is about 0.8
# per-channel True 0.0065

# M/M/1: Poisson arrivals (40/s), one server, exponential service (mean 20 ms), first come first served
lam, mu, n = 40.0, 50.0, 200_000
arrive = np.cumsum(rng.exponential(1 / lam, n))
service = rng.exponential(1 / mu, n)
leave = np.empty(n)
free = 0.0
for i in range(n):
    free = max(free, arrive[i]) + service[i]        # start when the server is free
    leave[i] = free
T = leave - arrive                                   # time in the system of each request
print(round(1000 * T.mean(), 1), round(1000 * np.quantile(T, 0.95), 1))   # about 100 and 300 ms
print(round(T.sum() / leave[-1], 2), round(lam * T.mean(), 2))           # about 4.0 and 4.0: L = lambda W

# speculative decoding: tokens per target pass = 1 + accepted drafts before the first rejection
a, g = 0.8, 4
acc = rng.random((100_000, g)) < a
first_reject = np.where(acc.all(axis=1), g, np.argmin(acc, axis=1))
print(round((first_reject + 1).mean(), 2), round((1 - a ** (g + 1)) / (1 - a), 2))   # about 3.36 and 3.36

Both scales respect the bound $s/2$, but the per-tensor scale is set by the outlier row, so the other rows lose almost all their precision (an error of 0.3 on weights of size about 0.8).

6. Where it shows up #

• Every LLM product. Chat, coding assistants and APIs run an engine of this kind; the KV-cache and roofline numbers decide the GPU bill.
• Batch inference. Offline evaluation, synthetic data and the rollouts of RL fine-tuning (lesson 11) are serving problems where only throughput counts: large batches, no TTFT target.
• RAG and agents (lesson 15). Long prompts make prefill and KV memory the main load; prefix caching of system prompts and conversation history matters most.
• ML for science. An autoregressive weather or other surrogate model processes a whole state (thousands of tokens) at every step, so each step looks like a prefill: compute-bound, unlike LLM decoding. Weight-only quantization then helps little, while FP8 or W8A8 matmuls do. The roofline tells you which case you are in before you optimize.

7. Common mistakes #

• Forgetting the factor 2 (keys and values), or using $n_h$ instead of $n_{kv}$ for a GQA model.
• "Decode is slow because it needs a lot of compute." It needs little compute; it is limited by reading the weights and the cache.
• Expecting batching to fix attention. Batching helps the weight matmuls, not attention: each sequence reads its own cache, intensity $n_h/n_{kv}$.
• Mixing up capacity rules. With reservation, count the maximum length per sequence; with paging, count the real length (plus less than one block).
• Expecting weight-only int4 to speed up prefill or very large batches: those are compute-bound, and the dequantization even adds work.
• Ignoring prefill in capacity planning. With long prompts it can be the larger load.
• Planning at 95% utilization. Queueing latency grows like $1/(1-\rho)$; leave headroom.
• Reporting throughput only. High throughput with TPOT spikes fails the SLO; report goodput and percentiles.

8. Check yourself #

1. A model with the Llama-3-70B shape (80 layers, 8 KV heads, $d_h = 128$, about 70B parameters) is served in bf16 with tensor parallelism over 4 H100s (80 GB each). Each GPU keeps 5 GB for activations. How many KV bytes per token, and how many tokens fit?
   Answer

   $k = 2 \cdot 80 \cdot 8 \cdot 128 \cdot 2 = 327{,}680$ bytes $= 320$ KiB per token. Weights: 140 GB, 35 GB per GPU. Cache: $4 \times (80 - 35 - 5) = 160$ GB, so $160 \cdot 10^9/327{,}680 \approx 488{,}000$ tokens. Each GPU stores 2 of the 8 KV heads of every token.
2. Why can a larger batch make the weight matmuls of decoding compute-bound, but never decode attention?
   Answer

   All sequences share the weights, so one read of a weight serves $B$ tokens: intensity $\approx B$. In attention each sequence reads its own keys and values, so the bytes grow with $B$ as fast as the FLOPs: intensity $n_h/n_{kv}$, independent of $B$ and of the context length.
3. Four requests with output lengths 10, 20, 50 and 200 tokens run with static batching. What fraction of the slot-steps does useful work? What does continuous batching change?
   Answer

   $280/(4 \times 200) = 35\%$. Continuous batching refills a slot at the step after its sequence finishes, so no slot idles while requests wait, and a new request waits for one step instead of for the whole batch (better TTFT).
4. Parallel sampling: 4 answers to one 1,000-token prompt, blocks of 16 tokens. How many blocks does the prompt use with and without sharing? What happens when the first new tokens are written?
   Answer

   $\lceil 1000/16 \rceil = 63$ blocks (62 full and one with 8 tokens). Without sharing: $4 \times 63 = 252$; with sharing: 63, reference count 4. Each sequence writes its first new token into the shared last block, so copy-on-write gives three of them private copies; the last writer finds a reference count of 1 and writes in place. Total: 66 blocks.
5. One H100 runs offline summarization at batch 512. Which quantization helps most, and why not weight-only int4?
   Answer

   W8A8 or FP8. With $B = 512 > 295$ the weight matmuls are compute-bound, and 8-bit tensor cores double the FLOP/s. Weight-only int4 reduces bytes, which no longer limit the step, and dequantization adds work. An fp8 KV cache still helps the attention reads and the capacity.
6. Speculative decoding with $\alpha = 0.8$ and $\gamma = 4$, and a draft that costs $c = 0.05$ of a target pass. What is the expected speed-up? When does it not pay off?
   Answer

   $\mathbb{E}[\text{tokens}] = (1 - 0.8^5)/0.2 = 3.36$, speed-up $3.36/(4 \cdot 0.05 + 1) = 2.8$. It pays off less at large batch (the target pass becomes compute-bound, so rejected tokens cost real compute), with a low acceptance rate, or when the draft model is slow.

Recall cardsAnswer in your head first, then reveal. Add the cards to your review deck to see them again just before you would forget.

1. How many bytes does the KV cache need per token?

   Show answer

2. What is the arithmetic intensity of a weight matmul on $B$ tokens in bf16, for small $B$?

   Show answer

3. What is the arithmetic intensity of decode attention, and why does batching not change it?

   Show answer

4. What do TTFT and TPOT measure, and which phase sets each one?

   Show answer

5. Write the decode step-time model.

   Show answer

6. Which waste does continuous batching remove?

   Show answer

7. Which waste does paged attention remove, and what is left?

   Show answer

8. Which quantization speeds up decode at batch 1, and which speeds up prefill?

   Show answer

9. State Little's law and the M/M/1 mean latency.

   Show answer

10. Expected tokens per target pass in speculative decoding with acceptance $\alpha$ and $\gamma$ drafts?

    Show answer

Add these cards to my reviewOpen the review →

9. Interview angle #

Recognize the task from the wording.

The prompt says	Start with
"how many GPUs for X requests per second?"	weights, $k$ per token, sequences per GPU, step time, Little's law
"GPU utilization is low during decoding"	decode is memory-bound; larger batch, paging, quantized weights
"we run out of memory with long contexts"	$k = 2Ln_{kv}d_hb$; GQA, fp8 cache, paging, tensor parallelism
"TPOT spikes when long prompts arrive"	prefill interference; chunked prefill or disaggregation
"make it cheaper"	throughput per GPU: batch size, paging, quantization by phase
"make it faster for one user"	weight-only quantization, speculative decoding, tensor parallelism
"latency is fine at night but bad at peak"	utilization $\rho$, $W = S/(1 - \rho)$, autoscaling, headroom
"many users share a system prompt"	prefix caching, prefix-aware routing

The routine to say aloud (about 30 seconds): "First the numbers: weight bytes, KV bytes per token, how many tokens fit, then the decode step time from bytes over bandwidth and the prefill time from FLOPs. Little's law turns the traffic into concurrent sequences. Then I name the limit that binds, usually KV memory, and pick the levers for that limit."

A plan for 45 minutes.

1. 0–5 min: clarify the model (size, attention type, context), traffic (requests per second, prompt and output lengths, peak factor), targets (TTFT, TPOT, p99), hardware, budget.
2. 5–15 min: numbers: weights, $k$ per token, tokens and sequences per GPU, decode step time, prefill time, Little's law, number of GPUs.
3. 15–30 min: architecture: API and streaming, router (prefix-aware), engine (scheduler with continuous batching, paged KV manager, model runner), autoscaling, metrics.
4. 30–40 min: the binding limit and its levers: quantization, GQA, prefix caching, chunked prefill or disaggregation, speculative decoding, tensor parallelism.
5. 40–45 min: failure modes (preemption storms, long-prompt spikes, out-of-memory, node failure) and trade-offs (throughput against TPOT, cost against quality).

Typical questions and short model answers.

1. "Why is decode slow?" — "Each decode step reads every weight and every cached key and value from HBM, but does only about 2 FLOPs per weight per sequence. At batch 1 the intensity is about 1 FLOP per byte, while an A100 needs 153 to be compute-bound. So the step time is the time to read the weights. Batching many sequences shares that read; the KV memory limits the batch."
2. "How does vLLM work?" — "Two ideas. Paged attention stores the KV cache in 16-token blocks with a block table per sequence, like virtual memory, so no memory is reserved for tokens that never come and sequences can share blocks with reference counts. Continuous batching reschedules after every step, so finished sequences leave and new ones join at once. Together they allow 2–4 times larger batches than reserving the maximum length."
3. "How many GPUs for 10 requests per second on a 13B model?" — "26 GB of weights, 800 KiB of cache per token, so about 61,000 tokens and 79 sequences per A100. The step is about 33 ms, so a request stays 8.5 s, and Little's law gives 85 concurrent sequences. Decode needs about 1.1 GPUs and prefill about 0.85; with headroom, 3 GPUs."
4. "Which quantization would you use?" — "It depends on the phase that binds. At small batch, decode is memory-bound, so weight-only int4 or int8 shortens the step and frees memory for the cache. At large batch or for prefill, the matmuls are compute-bound, so W8A8 or FP8 doubles the FLOP/s. An fp8 KV cache doubles the tokens that fit. Then I check quality on the task evals."
5. "What is speculative decoding and when does it help?" — "A small draft model proposes $\gamma$ tokens and the target model checks them in one pass, with a rejection rule that keeps the target distribution exactly. With acceptance $\alpha$, a pass yields $(1-\alpha^{\gamma+1})/(1-\alpha)$ tokens. It helps when decode is memory-bound, at small batch; at large batch the checks cost real compute."
6. "Why does latency explode at high load?" — "For one server, $W = S/(1 - \rho)$. At 50% utilization the latency is twice the service time, at 80% five times, at 95% twenty times. So I plan for 60–80% utilization at peak and autoscale on queue length."

Typical follow-ups. "Why not just increase the batch size?" (KV memory caps it, and TPOT grows with $B$ through the KV reads.) "What does paging cost?" (an indirection in the attention kernel and less than one block of waste per sequence; the larger batch pays for it.) "Swap or recompute after preemption?" (recompute when the GPU has spare compute and the sequences are short; swap when the CPU–GPU link is fast and the sequences are long.) "How do you serve a model that does not fit on one GPU?" (tensor parallelism inside a node; pipeline parallelism across nodes only if needed, because it adds latency.)

10. Practice #

The notebook for this lesson runs in Colab, in NumPy and plain Python. Each exercise has tests:

1. kv_bytes_per_token and max_sequences: the cache size and the number of sequences that fit, checked against Llama-2-13B and Llama-3-70B.
2. decode_step_ms: the step-time model and the throughput curve; find the batch where KV memory binds.
3. PagedKVCache: a block allocator with block tables, reference counts and copy-on-write, tested with thousands of random operations (no leaked block, no double free).
4. simulate_mm1: a single-server queue; compare the mean latency with $1/(\mu - \lambda)$ and check Little's law.
5. speculative_tokens: simulate acceptance and compare with $(1-\alpha^{\gamma+1})/(1-\alpha)$.

Timed practice (45 minutes each, aloud): "Serve a 70B model with GQA for a coding assistant: 2,000 requests per minute at peak, prompts of 2,000 tokens, outputs of 300 tokens, TTFT $\le$ 1 s, TPOT $\le$ 40 ms, H100 nodes with 8 GPUs." "Design a batch-inference service that summarizes 10 million documents per day at the lowest cost." Then read the scheduler and block manager of nano-vllm (nanovllm/engine/scheduler.py, nanovllm/engine/block_manager.py) and find the preemption rule and the hash used for prefix caching.

Say it aloud drill. Without notes, explain in 2 minutes why decode is memory-bound and what paged attention changes. Then derive the M/M/1 mean latency in 1 minute.

11. Watch and read #

Fast LLM Serving with vLLM and PagedAttentionAnyscale · 32 min

The vLLM authors explain the three kinds of KV-cache waste, block tables, sharing with copy-on-write, and the measured gains.

EfficientML.ai Lecture 13 - LLM Deployment Techniques (MIT 6.5940 Fall 2026)MIT HAN Lab · 69 min

A lecture from MIT's Efficient ML course on how LLMs are made cheaper and faster to run; watch it next to sections 3.7 and 3.8.

Quantization explained with PyTorch - Post-Training Quantization, Quantization-Aware TrainingUmar Jamil · 51 min

Symmetric and asymmetric quantization, scales and the rounding error, worked out in code.

What is Speculative Sampling? | Boosting LLM inference speedAssemblyAI · 6 min

The draft-and-verify idea and why the output distribution stays the same.

• Stanford CS336 (Spring 2025), Lecture 10: Inference (video on YouTube; embedding is disabled): arithmetic intensity of prefill and decode, the KV cache, and speculative decoding.
• Kwon et al. (2023), Efficient Memory Management for Large Language Model Serving with PagedAttention (vLLM): §3 (the three kinds of waste), §4 (PagedAttention, sharing, scheduling and preemption).
• Austin et al., How to Scale Your Model: All About Transformer Inference (free web book): latency and throughput estimates, and the design of an inference engine.
• Yu et al. (2022), Orca: A Distributed Serving System for Transformer-Based Generative Models (iteration-level scheduling); Agrawal et al. (2024), Sarathi-Serve (chunked prefill); Zhong et al. (2024), DistServe (prefill/decode disaggregation).
• Leviathan et al. (2023), Fast Inference from Transformers via Speculative Decoding, §3 (the expected number of tokens and the speed-up).
• Xiao et al. (2023), SmoothQuant; Lin et al. (2024), AWQ; Ainslie et al. (2023), GQA.
• nano-vllm: a readable vLLM-style engine in about 1,200 lines of Python.