Search Tech Journey

Find topics, journeys and posts

6-month learning plan124 / 130
back to blog
llmadvanced 55m read

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.

LLMsM14 · LLMs & Applications· Session 124 of 130 90 min

🎯 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.20perquerycannotbeaproduct.AnLLMthatcosts0.20 per query cannot be a product. 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.

You will be able to
  • 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

Serving LLMs vs serving pizzas
🌍 Real world

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.

💻 Code world

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.

The one law of LLM serving
  • 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.
  1. 2017
    Attention is All You Need
    Transformer architecture published. Inference cost = O(n²) per token; nobody worries yet because n is small.
  2. 2019
    KV cache · standard trick
    Once GPT-2 goes long, everyone caches K/V during decode. Trades memory for compute — obvious in hindsight.
  3. 2022
    FlashAttention · Dao et al.
    Fuses attention softmax + memory access to avoid materialising the N×N attention matrix. 2–4× faster attention.
  4. 2023
    vLLM + PagedAttention
    Kwon et al. treat KV cache like OS virtual memory — small pages, no fragmentation. Unlocks 23× throughput.
  5. 2023
    Speculative decoding · Leviathan et al.
    Draft-then-verify pattern. 2–3× decode speedup with zero quality loss.
  6. 2024
    Multi-LoRA serving · S-LoRA / vLLM
    Hundreds 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)

Naive (no KV cache)

1 user, O(n²)

  • ~5 tokens/sec
  • ~$40 per 1M tokens
  • GPU util <5%
  • You will not ship this
KV cache · static batch 1

1 user, O(n)

  • ~50 tokens/sec
  • ~$4 per 1M tokens
  • GPU util ~15%
  • Baseline of any tutorial
KV cache · static batch 8

8 users, HOL blocking

  • ~120 tokens/sec
  • ~$1.60 per 1M
  • GPU util ~40%
  • Head-of-line hurts you
Continuous batching (vLLM)

32+ users, no HOL

  • ~1500 tokens/sec
  • ~$0.15 per 1M
  • GPU util ~85%
  • The step that changes economics
+ Speculative decoding

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

L1 · Model + weights (fp16 / bf16 / int8 / 4-bit)
Quantisation shrinks VRAM 2–4× at 1–3 pp quality cost. Always re-eval after.
footprint
L2 · Attention kernel (FlashAttention 2/3)
Fused, block-aware attention. On by default in vLLM and TGI.
compute
L3 · KV cache management (PagedAttention)
Pages, block-level allocation, prefix caching. The biggest win of the last two years.
memory
L4 · Scheduler (continuous batching)
Decides which requests to admit/evict each step. This is where vLLM eats TGI's lunch.
scheduler
L5 · Decoding tricks (speculative, medusa, lookahead)
Extra tokens per forward pass. 2–3× further speedup on friendly workloads.
tricks
L6 · API + streaming (OpenAI-compatible)
SSE, backpressure, timeouts, retries. Where 50% of real outages happen.
ops

Common misconception
✗ What most people think

"LLM inference is compute-bound. To serve faster I need more FLOPs — a bigger GPU or better kernels."

✓ What is actually true

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.

Why the myth is so sticky

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.

Prove it to yourself

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.
From first principles
Start with the question

Why does continuous batching improve throughput so much more than static batching? Both process the same requests with the same model.

  1. 1
    Decoding 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
  2. 2
    Therefore 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
  3. 3
    But 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
  4. 4
    Static 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
  5. 5
    Continuous 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
  6. 6
    This 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

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.

Mental modelTwo phases with opposite bottlenecks

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.
🔔 Fires when you see

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.

The tradeoff

You must cut inference cost by half. Quantise the model, use a smaller model, or optimise the serving stack?

Quantisation (INT8 / FP8 / INT4 weights)
+ you gain directly reduces the bytes moved per decode step, so it improves both latency and throughput; and it shrinks the memory footprint, freeing space for a larger KV cache and therefore higher concurrency — a compounding win
− you pay quality loss that is small on average but concentrates in the hardest cases, which are exactly the ones you care about; aggressive 4-bit schemes need calibration data and careful per-channel handling; and kernel support varies by hardware
pick when you are bandwidth-bound (you almost certainly are) and can validate on a real eval set that the degradation is acceptable per-slice, not just on average
Smaller model (or distilled student)
+ you gain largest and most reliable cost reduction, and it improves every metric simultaneously — latency, throughput, memory, concurrency; a distilled student can retain most task quality on a narrow task
− you pay general capability drops in ways that are hard to fully characterise, so it can fail on inputs your eval never covered; distillation requires a pipeline and a teacher; and it is a bigger project than a config change
pick when your workload is narrow enough that you can enumerate what capability you actually need — task-specific services, classification, extraction
Serving-stack optimisation (continuous batching, paged KV, prefix caching)
+ you gain large throughput gains at zero quality cost — the only option in this list with no accuracy tradeoff at all; prefix caching in particular is nearly free when many requests share a long system prompt
− you pay higher throughput usually means higher per-request latency under load (queueing), so it trades one metric for another; and adopting a modern serving engine is real migration work
pick when first, always — before touching the model, because it costs no quality
What a senior engineer actually does

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

--enable-prefix-caching
vLLM detects the shared system prompt across requests and reuses its KV cache. Massive win when many users share a long prompt.
vLLM flag
--gpu-memory-utilization 0.9
Fraction of GPU memory vLLM may claim for weights + KV cache. Raise → more concurrent users; lower → safety margin for other processes.
vLLM flag
asyncio.gather(*[one_request(i) …])
Fires all N requests in flight at once so vLLM's scheduler actually sees a batch to combine.
load pattern
resp.usage.completion_tokens
The OpenAI-compatible response tells you exactly how many tokens were generated. Multiply by concurrency, divide by wall time → true throughput.
measurement
quantiles(lats, n=20)
Report p50 and p95 latency, not average. Averages hide the tail; SLOs are almost always defined on p95 or p99.
stats
concurrency sweep 1→32
You will see throughput scale sub-linearly then plateau. The plateau is the GPU saturating; the knee is your operating point.
capacity
Try itSee prefix caching in action — the flag that pays for itself in 10 minutes

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.

💡 Hint · Compare throughput with and without a shared 400-token system prompt. Then compare with --enable-prefix-caching vs without.

(d) Production reality · 15 min

War story A startup on Hugging Face TGI · 2024 (common failure)$8k/week GPU bill, 500 users
🔥 What broke

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.

🧯 The fix
Four stacked fixes: (1) switch to vLLM with continuous batching → 4× throughput. (2) enable prefix caching → the shared system prompt's KV is reused, saving 40% of prefill compute. (3) quantise to AWQ 4-bit → 2× throughput, negligible quality loss on their eval. (4) add speculative decoding with a 1B draft → 1.5× more. Total: ~24× improvement. New bill: ~$350/week.
🎓 Lesson to steal
The default configuration of every serving framework is 'safe and slow'. Every LLM in production deserves a serving audit within its first month — batching, prefix caching, quantisation, speculative decoding. Each is a 1.5–4× multiplier and they compose.
War story A chat product · 2024 (industry-common failure)p99 latency alerts every 20 minutes
🔥 What broke
Continuous batching was on. p50 latency looked great. But p99 was 40+ seconds and alerts fired hourly. Investigation: a handful of power users were sending prompts with max_tokens=4000 and the scheduler let them block the batch.
🧯 The fix

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.

🎓 Lesson to steal
Continuous batching doesn't remove head-of-line blocking — it just moves it from batches to long single requests. Cap max_tokens per user tier, and isolate long-form workloads on separate replicas.
War story An enterprise search deploymentquality dropped silently after a serving upgrade
🔥 What broke
Team upgraded to a newer AWQ-quantised model to save VRAM. Generic benchmark scores (MMLU, HellaSwag) barely moved. Two weeks later, code-generation quality tanked and CS tickets spiked — the quantised model was reliably worse at anything requiring precise reasoning.
🧯 The fix
Rolled back to fp16 for the code-heavy endpoint; kept AWQ for the summarisation endpoint (where the eval showed <1 pp regression). Added a rule: every quantisation change re-runs the task-specific golden set from S122, not just public benchmarks.
🎓 Lesson to steal
Public benchmarks are averaged over easy examples; your product depends on the hard ones. Any quantisation change needs a task-specific eval or you will regress silently.

Common failure modes

The serving landscape today

vLLM

Best general-purpose OSS

  • PagedAttention + continuous batching
  • Multi-LoRA
  • OpenAI-compatible API
  • Rapidly improving
TensorRT-LLM

Fastest on NVIDIA if you tolerate compile

  • Kernel fusion + graph compile
  • Per-model tuning required
  • Best for one big deployment
TGI (Hugging Face)

Easy defaults

  • Good out of the box
  • Slightly behind vLLM on scheduler
  • Tight HF Hub integration
SGLang

Fast + structured output

  • Radix attention
  • Great for JSON/constrained decode
  • Newer, smaller community
Managed (OpenAI/Anthropic/Together/Fireworks/Groq)

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

Serving is the hinge between model quality and product economics
S115 · Efficient Attention
FlashAttention 2/3 lives here — the kernel every server uses.
S122 · LLM Evaluation
Every serving change (quant, decoding trick) needs an eval diff.
S123 · Fine-Tuning
Multi-LoRA serving pattern — hundreds of adapters, one base.
S130 · Design an AI Chat Product
Capstone — capacity planning, cost model, SLOs.
S142 · Observability for ML
The metrics you must log on a serving fleet.
S148 · Capacity Planning
Tokens/sec per GPU × GPU count = your ceiling.

(e) Recall + stretch · 10 min

Recall — click each to reveal · click to reveal
★ = stretch question

Explain-out-loud test

  1. Why is decode memory-bound and prefill compute-bound?
  2. What is the single largest win going from static to continuous batching, and why?
  3. 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.