Transformer Inference Overview

1. What is it?#

The map of everything in this section, and how the pieces connect. Read this file, then read it again after finishing the section — it will mean something different the second time.

2. Why does it exist?#

Because LLM inference has about a dozen interlocking concepts, and learning them in isolation produces someone who knows the words. The value is in the connections: why the KV cache forces paged memory, why paged memory enables prefix sharing, why prefix sharing changes your routing strategy.

3. The mental model#

                         A REQUEST ARRIVES
                                │
                                ▼
                    ┌───────────────────────┐
                    │   TOKENIZE  (02)      │  text → integers
                    └───────────┬───────────┘
                                ▼
                    ┌───────────────────────┐
                    │   SCHEDULER (08, 09)  │  can this run now?
                    │   - KV space?         │  is there memory?
                    │   - batch full?       │  who else is running?
                    └───────────┬───────────┘
                                ▼
                    ┌───────────────────────┐
                    │   PREFIX CACHE (11)   │  have we seen this prompt before?
                    └───────────┬───────────┘
                                ▼
                    ┌───────────────────────┐
                    │   PREFILL   (03)      │  process all prompt tokens at once
                    │   compute-bound       │  → first token, and fill the KV cache
                    │   O(S²) attention     │
                    └───────────┬───────────┘
                                ▼
                ┌───────────────────────────────┐
                │      DECODE LOOP  (03,04)     │  ← repeat per output token
                │   ┌─────────────────────────┐ │
                │   │ read ALL weights        │ │  memory-bound
                │   │ read the KV cache (05)  │ │  grows every step (06,07)
                │   │ compute one token       │ │
                │   │ append K,V to cache     │ │  paged blocks (10)
                │   │ sample (13)             │ │
                │   │ stream out (14)         │ │
                │   └─────────────────────────┘ │
                └───────────────┬───────────────┘
                                ▼
                    ┌───────────────────────┐
                    │   FREE KV BLOCKS      │
                    └───────────────────────┘

4. The five facts that explain everything#

Fact 1 — Prefill and decode are different workloads. Prefill processes S tokens in parallel: compute-bound, high arithmetic intensity. Decode processes 1 token per sequence: memory-bound, arithmetic intensity ~1. Every scheduling decision in an LLM server is about managing this asymmetry.

Fact 2 — Decode reads all the weights for every token.

70B FP16 → 140 GB read per decode step, regardless of batch size
On an H100 at 3.35 TB/s → 42 ms floor per step

This is why batching (amortize over more sequences) and quantization (read fewer bytes) are the two dominant optimizations.

Fact 3 — The KV cache makes decode affordable, and then becomes the constraint. Without it, generating token N requires recomputing attention over all N-1 previous tokens. With it, you store K and V and read them. The storage grows linearly with tokens × batch and becomes what limits your concurrency.

Fact 4 — Requests have wildly different costs and unknown durations. A request may generate 5 tokens or 4,000. You cannot know in advance. This breaks static batching, breaks round-robin load balancing, and forces iteration-level scheduling.

Fact 5 — Capacity is a memory budget, and it’s computable.

KV budget = GPU memory − weights − overhead
concurrency = KV budget ÷ (bytes per token × context length)

Every capacity question reduces to this. File 15 does a dozen worked examples.

5. How the techniques map to the facts#

Every technique in the curriculum is an attack on one of five facts. When you meet a new technique, ask which fact it attacks. If you can’t answer, you haven’t understood it.

6. The numbers you should be able to produce from memory#

For any model, given its config:

Weights (GB)        = params × bytes_per_param / 1e9
FLOPs per token     ≈ 2 × params + 4 × L × S × d
KV bytes per token  = 2 × L × n_kv_heads × head_dim × bytes
Decode step floor   = bytes_read / HBM_bandwidth
Max concurrency     = (GPU_mem − weights − overhead) / (KV_per_token × context)

Five formulas. With them and a spec sheet you can answer nearly any capacity question before provisioning anything.

7. What you’ll be able to do after this section#

• Read a model config and predict its serving profile.
• Explain to a skeptical colleague why their 100-token prompt and 100-token generation cost wildly different amounts.
• Diagnose why a serving system is slow, by phase.
• Size a cluster.
• Choose between engines and configurations on evidence rather than folklore.
• Implement continuous batching and a paged KV cache from scratch (Projects 08, 09).

8. Hands-on exercise#

A. Draw it yourself. Without looking, reproduce the diagram in section 3 from memory. Then compare. What did you miss?

B. Predict. Before reading further, write down your predictions:

• How much bigger is the KV cache than the weights for Llama-3-8B at 128k context?
• What fraction of slots does static batching waste for a realistic length distribution?
• How much does continuous batching improve throughput? Then check your predictions at the end of the section. The gaps are what you learned.

C. Set up a lab. Install vLLM (or SGLang) and serve a small model locally. You’ll use it for every exercise in this section.

pip install vllm
vllm serve Qwen/Qwen2.5-1.5B-Instruct --max-model-len 4096
# then:  curl http://localhost:8000/v1/models

9. Further reading#

• [ESTABLISHED] Kwon et al., “PagedAttention” (SOSP 2023) — read the introduction now, the rest after file 10
• [ESTABLISHED] Pope et al., “Efficiently Scaling Transformer Inference” (2022)
• Next: 02 — Tokenization