LLM Serving — KV Cache, Batching, Speculative Decoding

Why this session matters

Part of a 24-topic learning series on engineering, ML, and LLM systems. Each session is a 90-minute deep-dive on one topic — designed so anyone can pick it up cold. Every two topics are followed by a revision session with recall prompts and hands-on drills.

Part 1: LLM Serving Part 1 — vLLM, KV Cache, Continuous Batching

Why this session matters

Pre-training gets the headlines; serving is what pays the bills. Understanding KV cache, continuous batching, and the memory layout of a transformer at inference time is what makes the difference between a $50 and$5000 inference bill for the same workload.

Agenda

• Why naive model.generate() is terrible for production
• The KV cache — what it stores, how big it gets, why it matters
• Continuous (in-flight) batching vs static batching
• PagedAttention — vLLM's killer idea
• Throughput vs latency — the eternal tradeoff

Pre-read (skim before the session)

• vLLM paper — Efficient Memory Management for LLM Serving with PagedAttention (2023)
• Orca — Continuous batching paper (OSDI 2022)
• HuggingFace — Text Generation Inference docs
• vLLM blog — first announcement

Deep dive

1. The inference workload — two distinct phases

[ PREFILL ]                    [ DECODE ]
input prompt (N tokens)        one token at a time
heavy compute, parallel        memory-bound, sequential
~100 ms for 1k tokens          ~30 ms per token

• Prefill: compute-bound. You process the entire prompt in parallel through every transformer layer. GPU's tensor cores are saturated.
• Decode: memory-bound. One token forward at a time; bottleneck is reading the KV cache and weights from HBM, not compute.

These are different optimisation problems. Serving systems optimise both.

2. The KV cache — the silent budget eater

In a transformer, every attention head needs K and V tensors for every token in the context. To avoid recomputing them every step, we cache them.

Size per token, per layer:

2 * d_model * dtype_bytes

For Llama-3-70B (80 layers, hidden 8192, 64 heads, fp16):

• Per token KV cache: 2 * 80 * 8192 * 2 = ~2.5 MB
• 4k context: ~10 GB just for one request's KV cache.
• 128k context: ~320 GB. Yes, GB. Just KV.

This is why long context is expensive even at low compute cost.

3. Why naive batching breaks down

Static batching = wait for N requests, run them together as a batch.

Problems:

• Padding — variable-length prompts pad to max length; lots of wasted GPU.
• Tail-blocking — fastest request waits for slowest. 16-token reply blocked by 512-token reply.
• Cold queue — low traffic = small batches = poor GPU utilisation.

Throughput collapses for typical LLM workloads.

4. Continuous (in-flight) batching

Orca / vLLM insight: at decode time, every request just needs one more token. So:

• Maintain a pool of active requests.
• Each decode step: gather all active requests, run them together, append one token each.
• When a request finishes, evict it; admit a new one immediately.
• New prefill requests interleave with ongoing decodes.

Result: GPU never idles waiting for the slowest request. Throughput often 4–10x over static batching.

Time →
req A: P D D D D D D D
req B:     P D D D D D D D D
req C:           P D D D D D D D
                       ↑ A finishes, C admitted

5. PagedAttention — vLLM's contribution

Problem: KV cache for each request is variable-size, grows over time, lives next to other requests' caches. Contiguous allocation = massive fragmentation as requests come and go.

Solution: borrow virtual memory paging from OS.

• Divide KV cache into fixed-size blocks (e.g. 16 tokens).
• Each request has a block table mapping logical positions → physical blocks.
• Blocks allocated/freed on demand; no fragmentation.

Bonus: blocks can be shared across requests (prefix caching, beam search shares blocks).

Outcome: 2–4x more requests fit in same GPU memory; throughput up correspondingly.

6. Other serving systems

• TGI (HuggingFace Text Generation Inference) — production-ready, model-zoo wide, simple to deploy.
• TensorRT-LLM (NVIDIA) — fastest on NVIDIA hardware, painful build.
• DeepSpeed-Inference (Microsoft) — good for Mixture-of-Experts.
• SGLang — newer; structured outputs, prefix caching, often beats vLLM on certain workloads.
• MLX-LM / llama.cpp — local/edge inference; runs on Apple Silicon and CPU.

For most server-side production: vLLM or TGI. For best raw NVIDIA perf: TensorRT-LLM.

7. Prefix caching

Common scenario: every request shares a 2 KB system prompt. Recomputing prefill for that on every request wastes 100 ms each.

Prefix caching: hash the prefix tokens, cache the resulting KV blocks, reuse across requests. vLLM and SGLang support automatically when prefixes match.

Big win for: agent workloads (long system prompts), few-shot prompting, RAG (the same retrieved chunks reused).

8. Throughput vs latency

Two distinct service-level objectives:

• TTFT (time to first token) — user-perceived "did it start?"
• TPOT (time per output token) — user-perceived speed of streaming.
• End-to-end latency — total time.
• Throughput — total tokens/sec across all users.

You can't max all of them. Choices:

• Bigger batches → higher throughput, worse latency.
• Smaller batches → better latency, worse $/token.
• Speculative decoding (S34) → better TPOT, costs draft model time.
• Chunked prefill → smooth TTFT, slight throughput loss.

Define your SLO first. Tune second.

9. Tensor + pipeline parallelism

A 70B model doesn't fit on one 80 GB GPU at full precision. Options:

• Tensor parallelism (TP) — split each layer's matrices across GPUs; activations all-reduce after each layer. Low latency, high bandwidth needs.
• Pipeline parallelism (PP) — different layers on different GPUs; activations passed forward. Higher latency, less bandwidth.
• Expert parallelism (EP) — for MoE; experts on different GPUs.

For 8x A100: TP=8 typically fastest for inference.

10. Quantisation (preview of S34)

fp16 → int8 → int4 shrinks model + KV cache. Throughput up, quality usually within 1% on standard benchmarks. Most production deployments are int8 or int4 by 2026. Detailed in S34.

11. Cost math (do this in interview)

Llama-3-70B fp16 on 4× A100 80GB ($16/GPU-hr cloud):

• Cost: ~$64/hr.
• Realistic throughput with vLLM + continuous batching: ~3000 output tokens/sec.
• Cost per 1M tokens: $64 / (3000 * 3600 / 1e6) = ~$5.93.

Compare OpenAI GPT-4o-mini: ~$0.60/1M out. Why? Better hardware, better software stack, scale, quantisation, batching efficiency.

The gap is closing fast — but "self-host LLM" is rarely cheaper than API at low traffic.

12. Reality check

Decision tree for serving:

• < 1M tokens/day, latency permissive → API (OpenAI, Anthropic, etc.).
• 1–100M tokens/day, batchable → API with caching + prompt minimisation.
• 100M+ tokens/day with stable load → self-host with vLLM/TGI on rented GPUs.
• Privacy/regulatory hard requirement → self-host regardless.

Self-hosting eats engineering time. Budget 1 FTE for serving infra at any meaningful scale.

Reading material

Books:

• Hands-On Large Language Models — Jay Alammar & Maarten Grootendorst (the serving chapter)
• Generative AI with LangChain — Ben Auffarth (the deployment + cost chapters)
• AI Engineering — Chip Huyen (the deployment + inference economics chapter; the best practitioner book of 2024)

Papers:

• Efficient Memory Management for Large Language Model Serving with PagedAttention — Kwon et al. 2023 (SOSP) — the vLLM paper; PagedAttention explained from first principles.
• Orca: A Distributed Serving System for Transformer-Based Generative Models — Yu et al. 2022 (OSDI) — the original continuous-batching paper.
• FlashAttention — Dao et al. 2022 — the IO-aware attention kernel everyone now uses.
• FlashAttention-2 — Dao 2023 — the throughput-doubling sequel.
• SARATHI: Efficient LLM Inference by Piggybacking Decodes with Chunked Prefills — Agrawal et al. 2023 — chunked prefill, now the default in vLLM.

Official docs:

• vLLM documentation — the most popular OSS serving engine.
• Hugging Face Text Generation Inference (TGI) — HF's production serving stack.
• NVIDIA TensorRT-LLM — the GPU-vendor reference for max throughput.
• SGLang documentation — the fast structured-output serving engine.

Blog posts:

• Anyscale — Continuous Batching: How to Get 23x Throughput in LLM Inference — the canonical explanation with measured numbers.
• vLLM team — Easy, Fast, and Cheap LLM Serving with PagedAttention — the launch post; the 1-page mental model.
• Tim Dettmers — Inference math for transformers — the only resource you need for "how big a GPU do I need?"

In-depth research material

• vLLM — github.com/vllm-project/vllm — ~31k ★, the de-facto OSS serving engine; PagedAttention reference implementation.
• TGI — github.com/huggingface/text-generation-inference — ~9k ★, Hugging Face's production-grade Rust+Python serving stack.
• TensorRT-LLM — github.com/NVIDIA/TensorRT-LLM — ~9k ★, NVIDIA's max-throughput inference engine.
• SGLang — github.com/sgl-project/sglang — ~7k ★, the LMSYS engine focused on structured generation + fast serving.
• LMDeploy — github.com/InternLM/lmdeploy — ~5k ★, alternative serving runtime with TurboMind backend.
• llama.cpp — github.com/ggerganov/llama.cpp — ~67k ★, CPU/Apple Silicon inference; the "tiny VM" of the LLM world.
• SARATHI follow-up: Taming Throughput-Latency Tradeoff in LLM Inference — Microsoft Research; the modern scheduler design.
• Splitwise: Efficient generative LLM inference using phase splitting — Microsoft / NVIDIA; separating prefill and decode onto different hardware.
• DistServe: Disaggregating Prefill and Decoding for Goodput-Optimized LLM Serving — OSDI'24 — the disaggregated-serving paper.
• Character.ai blog — Optimizing AI Inference at Character.ai — a real serving stack producing 20k+ queries/sec/GPU.

Videos

• vLLM: Easy, Fast, and Cheap LLM Serving — Woosuk Kwon (vLLM lead, CMU) — Woosuk Kwon · 32 min — from the paper's first author; the definitive walk-through.
• Continuous Batching for LLM Inference — Anyscale — 24 min — the visual explanation of why static batching wastes GPUs.
• Inside vLLM: Anatomy of a High-Performance LLM Serving System — Stanford MLSys — Zhuohan Li · 58 min — the architecture lecture from a co-author.
• How to Serve LLMs with vLLM and OVHcloud AI Deploy — 42 min — hands-on deployment walkthrough.
• GPU MODE: Triton kernels for LLM inference — Horace He (PyTorch) — 1 h 12 min — the GPU-kernel-level view from a PyTorch core dev.

LeetCode — Design Bounded Blocking Queue

• Link: https://leetcode.com/problems/design-bounded-blocking-queue/
• Difficulty: Medium
• Why this problem: Producer-consumer with bounded buffer — same shape as the inference request queue feeding a continuous-batching scheduler.
• Time-box: 30 minutes. Look up the editorial only after.

Assignment / Deliverables

Give yourself a clean 2-hour window and complete all of these before moving on:

1. Read the deep-dive above end-to-end — no skimming. Take notes in your own words.
2. Solve the LeetCode problem below without help first. Only look at the hint after 15 focused minutes; only look at editorial after 30. Log your time.
3. Reproduce one code snippet locally. Pick the snippet that felt least obvious and get it running in a scratch file / notebook.
4. Draw the core diagram from memory. Paper, whiteboard, or tldraw — doesn't matter. If you can't, re-read section 2 and try again.
5. Write a 3-line takeaway in your prep journal: what surprised you, what you still don't understand, what you'd read next.
6. Skim one item from the Reading material section. Bookmark the rest for the weekend.
7. Commit any code + notes to your prep repo with message session-NN: <one-line summary>.

Stretch (optional, +30 min): explain today's topic to a rubber duck / a friend / a voice note. If you can't teach it in 5 minutes, you don't own it yet — flag it and revisit next weekend.

Post-session checklist

By the end of this session you should be able to:

• Explain why prefill is compute-bound and decode is memory-bound.
• Compute the KV cache size for a given model and context length.
• Compare static vs continuous batching with a timing diagram.
• Describe how PagedAttention avoids KV cache fragmentation.
• List 3 SLOs (TTFT, TPOT, throughput) and explain how batch size trades them off.
• Solve design-bounded-blocking-queue — semaphore-based producer-consumer.

Generated from sessions_data.py + content_part*.py. To edit a video / leetcode / title, edit the data file and re-run write_sessions.py.

Part 2: LLM Serving Part 2 — Speculative Decoding, Quantisation, Throughput

Why this session matters

Part 1 covered the engine (vLLM, KV cache, batching). Part 2 covers the levers — quantisation, speculative decoding, throughput tuning — that turn that engine from "works" to "$0.50 per million tokens". If you operate any non-trivial LLM workload, these techniques are no longer optional.

Agenda

• Quantisation — int8, int4, FP8, AWQ, GPTQ; what to pick
• Speculative decoding — small draft + big verifier
• Chunked prefill, prefix caching, lookahead decoding
• Multi-LoRA serving — many adapters, one base
• Throughput tuning — batch size, KV pool, parallelism

Pre-read (skim before the session)

• Speculative Decoding (Leviathan et al., 2023)
• GPTQ paper (Frantar et al., 2022)
• AWQ paper (Lin et al., 2023)
• vLLM docs — prefix caching

Deep dive

1. Quantisation — the headline lever

Reducing precision of weights (and optionally activations) shrinks memory + accelerates compute.

Memory savings cascade: smaller weights → more room for KV cache → more concurrent requests → higher throughput.

2. Weight-only vs weight-and-activation quantisation

• Weight-only (W8A16, W4A16) — weights quantised, activations stay fp16. Easier, less quality loss, easiest to get right.
• Weight + activation (W8A8, FP8) — both quantised. Requires careful calibration; bigger throughput win.

Most production deployments are weight-only int8/int4. FP8 weights+activations on H100 is the rising standard.

3. The popular int4 methods

• GPTQ — calibration-set post-training quantisation. Layer-by-layer optimisation. Standard for years; widely supported.
• AWQ — Activation-aware. Identifies "salient" weights (driven by activation magnitude), keeps them at higher precision. Smaller quality loss than GPTQ at int4.
• GGUF / Q4_K_M / Q5_K_S (llama.cpp ecosystem) — multiple bit widths within one model; great for CPU + Apple Silicon.

For server-side GPU: AWQ int4 is currently the sweet spot.

4. Calibration data matters

Quantisation algorithms learn from a small calibration set. Use:

• ~128–512 samples.
• Representative of your serving distribution (not random web text).
• Diverse: mix instruction, chat, domain-specific samples.

Same model quantised with wrong calibration = noticeably worse on your workload.

5. Speculative decoding

Decoding is memory-bound; the GPU is largely idle waiting for KV cache + weight reads. Idea: parallelise.

• A small draft model proposes the next N tokens (cheap, fast).
• The large target model verifies all N in one forward pass.
• Accepted tokens are kept; first rejection truncates and continues from there.

If draft model is good, you get ~2–3× speedup with no quality loss (the target model is mathematically still the authority).

draft proposes: "the quick brown fox jumps"
target verifies all 5 in parallel:
   accepts "the quick brown" — rejects "fox"
   re-samples token 4 itself: "dog"
   draft restarts from "the quick brown dog"

Variants:

• Self-speculative — same model with early-layer shortcut as draft (no separate model needed).
• Lookahead decoding — draft via n-gram pattern matching (no model needed).
• EAGLE / Medusa — small "head" branches on top of base model; cheap draft.

6. Chunked prefill

Prefill of a long prompt blocks all in-flight decodes (it monopolises GPU). Chunked prefill splits the prefill into segments, interleaves with decode steps. Result: smoother TTFT, less head-of-line blocking for short queries arriving during a long prefill.

vLLM and TGI both support. Set max_num_batched_tokens to control chunk size.

7. Prefix caching (already touched in S30)

Cache KV blocks for repeated prefixes. Hits common with:

• System prompts (every request shares).
• Few-shot exemplars.
• Conversation history (each chat turn extends from previous).
• RAG with same chunks for similar queries.

vLLM enables automatically with --enable-prefix-caching. The cache lives in GPU memory; evicted LRU. Typical 2–5× throughput improvement on chat workloads.

8. Multi-LoRA serving

Scenario: 100 customers, each with their own fine-tuned adapter. Don't deploy 100 separate models.

Pattern:

• Load base model once.
• Adapter (LoRA delta) loaded per request, small (~50 MB).
• Use kernels that compute (W + B·A)·x on the fly.

vLLM with --enable-lora, TGI with the same feature. Single GPU serves 100s of LoRAs.

Big architectural win: one fleet for all customers, vs N fleets. Cost down 10–50×.

9. Parallelism for serving

Recap from S30:

• Tensor parallel (TP) — splits weights across GPUs in one node. Low latency, high bandwidth (NVLink). Default for inference.
• Pipeline parallel (PP) — layers on different nodes. Adds latency per pipeline stage; suited to networks with weak interconnect.
• Expert parallel (EP) — MoE; experts across GPUs.

For 70B on 4× A100: TP=4. For 405B on 8× H100: TP=8 (or TP=4 PP=2).

10. Throughput tuning checklist

• max_num_batched_tokens — chunked prefill threshold.
• max_num_seqs — max in-flight requests.
• gpu_memory_utilization — fraction of GPU reserved (0.85–0.92 typical).
• kv_cache_dtype — fp16 vs fp8 (fp8 doubles KV capacity).
• Quantised weights (int8/int4).
• Prefix caching on.
• Speculative decoding on if you have a good draft.

Each lever interacts. Tune one at a time, measure, retune. Spreadsheet of (config, throughput, p50, p99) is your friend.

11. Observability for inference

• Token-level metrics — input tokens, output tokens, accepted-speculative-tokens.
• Phase timings — prefill ms, decode ms/token.
• Queue depth — pending requests.
• KV cache occupancy — fraction full; alert at 90%.
• Prefix-cache hit rate — should be 30–80% for chat workloads.

Standard exporters (Prometheus) ship with vLLM/TGI. Wire to Grafana, set SLO alerts.

12. Reality check

Cost-minimised stack circa 2026:

• vLLM with int4 AWQ weights + fp8 KV cache.
• Prefix caching enabled.
• Self-speculative decoding via Medusa or EAGLE.
• Multi-LoRA for tenant isolation.
• TP=4 on a node of 4× A100 or H100.
• Chunked prefill for smooth tail latency.

That setup serves 4–8× more tokens/sec than naive fp16 vLLM. Same hardware, same SLOs, ~5× cheaper per token. The math is obvious; the engineering is real work.

Reading material

Books:

• AI Engineering — Chip Huyen (the inference economics + cost chapters)
• Generative Deep Learning, 2nd ed. — David Foster (the chapter on autoregressive sampling for the sampling background you need)
• Hands-On Large Language Models — Jay Alammar & Maarten Grootendorst (the deployment + quantisation chapter)

Papers:

• Fast Inference from Transformers via Speculative Decoding — Leviathan, Kalman, Matias 2023 — the original speculative decoding paper.
• GPTQ: Accurate Post-Training Quantization for Generative Pre-trained Transformers — Frantar et al. 2022 — 3-4 bit weight quantisation that actually works.
• AWQ: Activation-aware Weight Quantization for LLM Compression — Lin et al. 2023 — the quantisation method shipped in vLLM / TGI by default.
• Medusa: Simple LLM Inference Acceleration with Multiple Decoding Heads — Cai et al. 2024 — speculative decoding without a separate draft model.
• EAGLE: Speculative Sampling Requires Rethinking Feature Uncertainty — Li et al. 2024 — the SOTA spec-decoding head used by vLLM.
• SmoothQuant: Accurate and Efficient Post-Training Quantization for LLMs — Xiao et al. 2023 — activation quantisation made practical.
• FlashAttention-3: Fast and Accurate Attention with Asynchrony and Low-Precision — Shah et al. 2024 — the H100-era attention kernel.

Official docs:

• vLLM — Performance Optimization guide — chunked prefill, prefix caching, speculative decoding settings.
• vLLM — Quantization support — AWQ, GPTQ, FP8, INT8 in production.
• Hugging Face Optimum — the HF quantisation + acceleration library.
• NVIDIA TensorRT-LLM — Speculative Decoding — production multi-token speculation.

Blog posts:

• Together AI — Sequoia: speculative decoding with a tree — how production speculative decoding actually works.
• PyTorch blog — Accelerating Generative AI with PyTorch II: GPT, Fast — Horace He's 10x speedup walkthrough.
• Anyscale — Throughput is all you need — the right mental model for batch sizing.

In-depth research material

• vLLM — github.com/vllm-project/vllm — ~31k ★, the canonical OSS engine with continuous batching + AWQ + FP8 + spec decoding.
• SGLang — github.com/sgl-project/sglang — ~7k ★, LMSYS engine with the fastest prefix caching and structured output.
• TensorRT-LLM — github.com/NVIDIA/TensorRT-LLM — ~9k ★, the NVIDIA max-throughput engine.
• llama.cpp — github.com/ggerganov/llama.cpp — ~67k ★, GGUF quantisation reference; the CPU/edge inference standard.
• exllamav2 — github.com/turboderp/exllamav2 — ~3.8k ★, the fastest single-GPU 4-bit inference engine for consumer hardware.
• AutoAWQ — github.com/casper-hansen/AutoAWQ — ~1.9k ★, the canonical AWQ implementation.
• AutoGPTQ — github.com/AutoGPTQ/AutoGPTQ — ~4.8k ★, the canonical GPTQ implementation.
• PyTorch GPT-Fast — github.com/pytorch-labs/gpt-fast — ~5.6k ★, the PyTorch team's reference for torch.compile + spec decoding.
• Mooncake: Trading More Storage for Less Computation — Kimi 2024 — the disaggregated KV-cache architecture from Moonshot AI (Kimi).
• Character.AI Research — Optimizing inference at Character.AI — the most detailed real-world production tuning story (20k qps/GPU).
• Tim Dettmers — Which GPU(s) to Get for Deep Learning — the only inference economics primer you need.

Videos

• Speculative Decoding: When Two LLMs are Faster than One — Mark Saroufim (PyTorch) — 31 min — the cleanest visual explanation; pairs perfectly with the Leviathan paper.
• Quantization in Depth — Hugging Face — 1 h 03 min — int8/int4/FP8/AWQ/GPTQ from first principles.
• Accelerating Generative AI: From Slow to Fast — Horace He (PyTorch) — 56 min — the GPT-Fast 10x talk; CUDA graphs + spec decoding + quantisation combined.
• Inside vLLM 2.0 — Woosuk Kwon (vLLM lead) — 58 min — chunked prefill, prefix caching, multi-LoRA, FP8.
• GPU MODE: Lecture 14 — TensorRT-LLM internals — 1 h 22 min — NVIDIA's serving engine from a GPU-kernel viewpoint.

LeetCode — Longest Palindromic Substring

• Link: https://leetcode.com/problems/longest-palindromic-substring/
• Difficulty: Medium
• Why this problem: Speculative-decode verification is essentially "longest accepted prefix of draft"; both problems are about matching segments efficiently.
• Time-box: 30 minutes. Look up the editorial only after.

Assignment / Deliverables

Give yourself a clean 2-hour window and complete all of these before moving on:

1. Read the deep-dive above end-to-end — no skimming. Take notes in your own words.
2. Solve the LeetCode problem below without help first. Only look at the hint after 15 focused minutes; only look at editorial after 30. Log your time.
3. Reproduce one code snippet locally. Pick the snippet that felt least obvious and get it running in a scratch file / notebook.
4. Draw the core diagram from memory. Paper, whiteboard, or tldraw — doesn't matter. If you can't, re-read section 2 and try again.
5. Write a 3-line takeaway in your prep journal: what surprised you, what you still don't understand, what you'd read next.
6. Skim one item from the Reading material section. Bookmark the rest for the weekend.
7. Commit any code + notes to your prep repo with message session-NN: <one-line summary>.

Stretch (optional, +30 min): explain today's topic to a rubber duck / a friend / a voice note. If you can't teach it in 5 minutes, you don't own it yet — flag it and revisit next weekend.

Post-session checklist

By the end of this session you should be able to:

• Pick the right quantisation method (int8/int4/FP8/AWQ/GPTQ) for a given GPU and workload.
• Explain why decoding is memory-bound and how speculative decoding exploits it.
• Configure prefix caching and predict the throughput impact for a chat workload.
• Stand up multi-LoRA serving with vLLM/TGI.
• Tune max_num_batched_tokens, gpu_memory_utilization, and KV-cache dtype.
• Solve longest-palindromic-substring — prefix-matching primitive used in spec verification.

Generated from sessions_data.py + content_part*.py. To edit a video / leetcode / title, edit the data file and re-run write_sessions.py.