S124 · LLM Serving — KV Cache, Batching, Speculative Decoding
The three ideas that turned LLM inference from $0.20/query to $0.001/query — KV cache, continuous batching, speculative decoding — plus the memory-bandwidth story nobody tells juniors.
🎯 Serve an LLM at 10× the throughput of a naive setup by understanding KV cache, continuous batching, and speculative decoding.
Why this session exists
An LLM that costs 0.001 per query can be almost anything. The gap between those two numbers is not a smaller model or a bigger GPU — it is three specific serving tricks that nobody teaches you in the "how to call the OpenAI API" tutorial. This session teaches them, in the order they compound.
- Explain why LLM decode is memory-bandwidth-bound but prefill is compute-bound.
- Describe KV cache, continuous batching, and speculative decoding in one paragraph each.
- Read a serving log and tell whether the GPU is memory-bound or compute-bound right now.
- Serve a real model with vLLM and hit >1000 tokens/sec on a single A100.
- Diagnose the top-5 serving pathologies (OOM, head-of-line blocking, KV thrash, cold starts, quantisation regressions).
Prerequisites
- S115 · Efficient Attention — Flash, Sparse, Linear (you need to know what K and V are)
- S112 · Transformers — BERT/GPT/T5 (the shape of a decoder-only forward pass)
- S122 · LLM Evaluation (to catch quality regressions from quantisation)
(a) Intuition · 5 min
A pizza kitchen with one oven has two bottlenecks: prep (dough, sauce, toppings — parallel, hands can help) and bake (the oven — one at a time). If you send one pizza at a time end-to-end, the oven is idle 90% of the day. The trick every real pizzeria learned: prep 10 pizzas in a row, then bake them together. Same oven, 8× throughput.
LLMs have the exact same two phases, and until 2023 everyone served them "one pizza at a time." Continuous batching is the "put ten in the oven" moment for LLM serving.
LLM inference has two phases. Prefill processes the whole prompt in one forward pass (compute-bound, GPU busy). Decode generates one token at a time, and each step must read the model weights + all prior K/V from HBM (memory-bandwidth-bound, GPU cores idle).
Naive decode is O(n²) — every new token re-processes every previous one. KV cache fixes the O(n²) by storing K/V per token. Continuous batching fixes the "one user at a time" waste by evicting finished requests and admitting new ones each step. Speculative decoding uses a tiny draft model to guess 4–8 tokens and lets the big model verify them all in one pass.
- Decode is memory-bandwidth-bound. Every token requires reading the entire model + KV cache from HBM.
- That means a bigger GPU with the same memory bandwidth barely helps. H100 crushes A100 at LLM serving because HBM3 is 3.3 TB/s vs 2 TB/s — not because it has more FLOPs.
- The way you 'exceed the per-user memory bound' is batching — read the weights once, use them for N users. Throughput scales with batch until you exhaust KV memory.
- 2017Attention is All You NeedTransformer architecture published. Inference cost = O(n²) per token; nobody worries yet because n is small.
- 2019KV cache · standard trickOnce GPT-2 goes long, everyone caches K/V during decode. Trades memory for compute — obvious in hindsight.
- 2022FlashAttention · Dao et al.Fuses attention softmax + memory access to avoid materialising the N×N attention matrix. 2–4× faster attention.
- 2023vLLM + PagedAttentionKwon et al. treat KV cache like OS virtual memory — small pages, no fragmentation. Unlocks 23× throughput.
- 2023Speculative decoding · Leviathan et al.Draft-then-verify pattern. 2–3× decode speedup with zero quality loss.
- 2024Multi-LoRA serving · S-LoRA / vLLMHundreds of adapters share one base in GPU memory. Personalisation at scale becomes economical.
(b) Visual walkthrough · 15 min
Prefill vs decode — two totally different workloads
Static batching vs continuous batching — the picture that made vLLM
Throughput math for Llama-2-7B on an A100 (rough)
1 user, O(n²)
- ~5 tokens/sec
- ~$40 per 1M tokens
- GPU util <5%
- You will not ship this
1 user, O(n)
- ~50 tokens/sec
- ~$4 per 1M tokens
- GPU util ~15%
- Baseline of any tutorial
8 users, HOL blocking
- ~120 tokens/sec
- ~$1.60 per 1M
- GPU util ~40%
- Head-of-line hurts you
32+ users, no HOL
- ~1500 tokens/sec
- ~$0.15 per 1M
- GPU util ~85%
- The step that changes economics
Draft-and-verify
- ~2500 tokens/sec
- ~$0.10 per 1M
- GPU util ~90%
- Requires a good small draft model
KV cache sizing — the number to internalise
For Llama-2-7B (32 layers, 32 heads, head_dim=128, fp16):
per token : 2 (K and V) x 32 layers x 32 heads x 128 dim x 2 bytes = 524 288 bytes ≈ 512 KB
per 2k ctx : 2048 x 512 KB = 1 GB (per user!)
40 users : 40 GB (fills an A100-40G before you even load the model)
That is why PagedAttention matters. Treating KV cache as small pages (16 tokens each) drops fragmentation from ~60% wasted memory to <4%, and lets you fit 3–4× more concurrent users on the same card.
The serving stack, layer by layer
The serving stack — pick a fight at each layer
"LLM inference is compute-bound. To serve faster I need more FLOPs — a bigger GPU or better kernels."
Autoregressive decoding is memory-bandwidth-bound, not compute-bound. Generating one token requires reading every model weight from HBM to produce a single token's worth of arithmetic, so arithmetic intensity is roughly 1 FLOP per parameter byte — far below what the hardware needs to saturate its ALUs. This is why batching is nearly free (the same weight read serves many sequences) and why quantisation speeds up decoding: fewer bytes to move.
Because training and prefill genuinely are compute-bound — both process many tokens per weight read, so the matmuls are large and the GPU is busy. Decode has the same code path but a batch-of-one-token shape, turning every GEMM into a skinny matrix-vector product. The mental model formed during training carries over silently, and the symptom (low GPU utilisation during generation) gets misread as a software inefficiency.
Compute arithmetic intensity for the two phases and compare against your hardware's ratio:
N = 7e9 # params
bytes_per_param = 2 # fp16
for batch, seq in [(1, 1), (32, 1), (1, 2048)]: # decode, batched decode, prefill
tokens = batch * seq
flops = 2 * N * tokens
bytes_ = N * bytes_per_param # weights read once per step
print(f'batch={batch:3d} seq={seq:5d} intensity={flops/bytes_:8.1f} FLOP/byte')
# A modern accelerator needs intensity in the hundreds to saturate.
# batch=1 decode is ~1. Batching is the only lever that changes it.Why does continuous batching improve throughput so much more than static batching? Both process the same requests with the same model.
- 1Decoding is bandwidth-bound, so the weight read per step is a fixed cost paid regardless of batch size. Adding sequences to a batch is close to free until compute becomes the limit.forced by · the same weights, read once, are applied to every sequence in the batch
- 2Therefore throughput is roughly proportional to the average number of sequences actually being decoded at each step. Keeping the batch full is the entire optimisation.forced by · an empty batch slot is a weight read amortised over fewer tokens
- 3But generation lengths vary enormously and unpredictably — one request emits 20 tokens, another 2,000, and you cannot know in advance which.forced by · the model decides when to emit the stop token; length is an output, not an input
- 4Static batching runs a fixed group until all members finish. So a batch of 32 where 31 requests finish at 50 tokens and one runs to 2,000 spends the remaining 1,950 steps decoding a batch of effectively one.forced by · finished slots sit idle but the step still runs; the batch cannot be resized
- 5Continuous batching instead operates at the granularity of a single decode step: when a sequence emits its stop token its slot is freed immediately and a queued request is admitted at the next step.forced by · nothing in the decode step requires the batch membership to be stable across steps
- 6This requires the KV cache to support non-contiguous, dynamically allocated per-sequence storage — you cannot free one sequence's cache from the middle of a preallocated contiguous block without fragmentation.forced by · variable-length lifetimes over a shared memory pool is exactly the fragmentation problem
Therefore continuous batching converts the batch from a fixed group into a running pool, and its throughput gain scales with the variance in output lengths — highest for chat workloads, negligible when all outputs are the same length.
And note what this predicts: the enabling constraint is memory management, which is why PagedAttention exists. Allocating the KV cache in fixed-size pages with a lookup table — exactly OS virtual memory — removes fragmentation, allows sharing pages between sequences with a common prefix, and makes admitting and evicting sequences cheap. The batching policy and the memory allocator are the same problem.
Prefill processes the whole prompt in parallel: large matmuls, compute-bound, GPU saturated, cost scales with prompt length. It produces the first token and the initial KV cache.
Decode emits one token at a time: every weight read from HBM for one token of work, bandwidth-bound, GPU mostly idle, cost scales with output length. Every serving optimisation targets one phase or the other, and the two rarely overlap.
- TTFT (time to first token) is a prefill metric — reduce it with prefix caching, chunked prefill, shorter prompts. TPOT (time per output token) is a decode metric — reduce it with batching, quantisation, speculative decoding.
- KV cache size = 2 × layers × headskv × dhead × tokens × bytes. It grows with every generated token and is what actually caps your concurrency.
- Quantisation helps decode because it reduces bytes moved. It helps prefill less, because prefill was compute-bound already.
- Speculative decoding verifies several draft tokens in one forward pass — it exploits the fact that the pass was bandwidth-bound and had spare compute. It reduces latency, not total compute.
Fire this model the moment you see: low GPU utilisation during generation · a latency SLA that does not distinguish first-token from per-token · OOM that depends on concurrent users rather than model size · a proposal to buy more compute for a decode-bound service · long shared system prompts recomputed on every request.
You must cut inference cost by half. Quantise the model, use a smaller model, or optimise the serving stack?
Do them in that reverse order: serving stack, then quantisation, then model size. The rule is to spend the free wins before the ones you pay for in accuracy, and serving-stack improvements are genuinely free in quality terms.
Measure before choosing, though — instrument prefill and decode separately. A service dominated by long prompts and short answers is a prefill problem and wants prefix caching; one dominated by long generations is a decode problem and wants batching and quantisation. Optimising the wrong phase is the most common way teams spend a quarter and move nothing.
(c) Hands-on · 25 min
Serve a real model with vLLM and measure how throughput scales with concurrency. Requires an NVIDIA GPU with 16 GB+; free Colab T4 works.
#!/usr/bin/env bash
# serve.sh — launch vLLM as an OpenAI-compatible server.
set -euo pipefail
pip install "vllm==0.5.4" "openai>=1.30"
python -m vllm.entrypoints.openai.api_server \
--model TinyLlama/TinyLlama-1.1B-Chat-v1.0 \
--max-model-len 2048 \
--gpu-memory-utilization 0.9 \
--enable-prefix-caching \
--port 8000 &
# wait for the server to be reachable
for i in {1..60}; do
if curl -sf http://localhost:8000/v1/models >/dev/null; then
echo "vLLM ready after ${i}s"; break
fi
sleep 1
done#!/usr/bin/env python3
# bench.py — hit the vLLM server at increasing concurrency and print throughput.
import asyncio
import time
from statistics import mean, quantiles
from openai import AsyncOpenAI
MODEL = "TinyLlama/TinyLlama-1.1B-Chat-v1.0"
client = AsyncOpenAI(base_url="http://localhost:8000/v1", api_key="dummy")
SYSTEM = "You are a poet. Answer in exactly four short rhyming lines."
async def one_request(i: int) -> tuple[float, int, float]:
t0 = time.time()
resp = await client.chat.completions.create(
model=MODEL,
messages=[
{"role": "system", "content": SYSTEM},
{"role": "user", "content": f"Write about the number {i}."},
],
max_tokens=120,
temperature=0.7,
)
latency = time.time() - t0
tokens = resp.usage.completion_tokens
return latency, tokens, tokens / latency
async def sweep(concurrency: int) -> None:
t0 = time.time()
results = await asyncio.gather(*[one_request(i) for i in range(concurrency)])
wall = time.time() - t0
lats = [r[0] for r in results]
total_tokens = sum(r[1] for r in results)
p50, p95 = quantiles(lats, n=20)[9], quantiles(lats, n=20)[18]
print(
f"conc={concurrency:3d} wall={wall:5.1f}s "
f"throughput={total_tokens/wall:7.0f} tok/s "
f"lat p50={p50:.2f}s p95={p95:.2f}s"
)
async def main() -> None:
for c in [1, 2, 4, 8, 16, 32]:
await sweep(c)
if __name__ == "__main__":
asyncio.run(main())What each block is doing
Anatomy of the benchmark
Restart the vLLM server WITHOUT --enable-prefix-caching. Bump the system prompt to ~400 tokens (paste in a policy blurb). Run the bench at concurrency=16. Note throughput. Restart WITH the flag. Run the same bench. Compare tokens/sec — you should see 20–40% improvement because the shared 400-token prefix is now cached across users.
(d) Production reality · 15 min
Team launched an internal RAG chatbot on TGI with default settings. First week: 500 users, $8k in GPU costs. Everyone panicked.
Root cause: Llama-2-70B in fp16 on 4×A100, static batching, no prefix caching, a 4k-token system prompt sent with every request. The same 4k prompt was being re-prefilled thousands of times per hour.
max_tokens=4000 and the scheduler let them block the batch.Introduced a two-tier scheduler: free users capped at max_tokens=512, paid users at 2048, "long-form" jobs routed to a separate replica pool. Added per-user token-budget accounting so nobody could saturate a shared GPU.
P99 dropped from 40 s to 3.5 s inside one deploy.
Common failure modes
The serving landscape today
Best general-purpose OSS
- PagedAttention + continuous batching
- Multi-LoRA
- OpenAI-compatible API
- Rapidly improving
Fastest on NVIDIA if you tolerate compile
- Kernel fusion + graph compile
- Per-model tuning required
- Best for one big deployment
Easy defaults
- Good out of the box
- Slightly behind vLLM on scheduler
- Tight HF Hub integration
Fast + structured output
- Radix attention
- Great for JSON/constrained decode
- Newer, smaller community
Skip the serving stack entirely
- No ops burden
- Per-token pricing
- Groq = custom hardware, ~10× tokens/sec on small models
Where this shows up in the rest of the plan
(e) Recall + stretch · 10 min
Explain-out-loud test
- Why is decode memory-bound and prefill compute-bound?
- What is the single largest win going from static to continuous batching, and why?
- When would you NOT quantise a model even if it saves half your VRAM?
What comes next
Hub: The 6-Month Learning Plan
Part of a 130-session evergreen learning series. Session structure: intuition → visual → hands-on → production war stories → recall. Duration: 90 minutes.