shreyansh

01 Fundamentals Prefill Decode KV Cache

Part of Index of Inference Engineering. Book: Ch 2 (Models), §2.1-2.4, and Ch 5 intro. Read fully — this is the conceptual core.

0. Ops:byte / arithmetic intensity (derive, don't memorize)

  • Arithmetic intensity = FLOPs performed per byte moved from memory. Compare to machine balance = peak FLOPS ÷ memory bandwidth.
  • If intensity < machine balance → memory-bandwidth-bound. If > → compute-bound.
  • Prefill: large matmuls, reuse each weight across many tokens → high intensity → compute-bound.
  • Decode: one token per step, each weight read once per token → intensity ≈ 2 × batch → at batch 1 it is far below machine balance → memory-bandwidth-bound. This single fact drives quantization, batching, and speculative decoding.
  • Bottleneck formula: ops:byte ratio (= intensity) vs hardware balance tells you whether to spend FLOPs (compute) or shrink bytes (bandwidth). Book §2.4.1-2.4.2.
  • Image generation is compute-bound (iterative denoising), unlike LLM decode — Book §2.4.3.

1. Request lifecycle (memorize)

tokenize → prefill (process whole prompt at once, compute-bound) → decode loop (1 token/step, memory-bandwidth-bound) → stream tokens → stop condition

  • TTFT (time to first token) ≈ queue + prefill. Dominated by prompt length + cache hits.
  • ITL/TPOT (inter-token latency / time per output token) ≈ decode speed. Dominated by weight size ÷ bandwidth + batch pressure.
  • Throughput (tok/s) rises with batching until KV cache or bandwidth saturates, then preemptions collapse it.

2. Roofline mental model

Every optimization is a move on one plot:

  • Quantization → attacks bandwidth-bound decode (smaller weights = fewer bytes moved).
  • Continuous batching → raises arithmetic intensity toward compute roof.
  • Speculative decoding → spends cheap FLOPs to cut sequential memory loads (wins only at low concurrency).
  • Disaggregation (prefill vs decode split) → exists because the two phases fight over one GPU.

3. KV cache (the core)

Each generated token stores K/V tensors reused for next steps. Grows with layers × hidden × seq_len × batch. Two requests sharing a system prompt recompute the same prefill unless routed to the same pod (see 08-Routing-Router-LiteLLM-Dynamo).

  • PagedAttention (vLLM, SOSP'23): manages KV cache like OS virtual memory — non-contiguous pages, <4% waste vs ~60% naive. Don't reimplement; read block manager + V1 scheduler source until paging is obvious.
  • Continuous batching / iteration-level scheduling (Orca, OSDI'22): add new requests each decode step instead of waiting for fixed batch to drain. Why vLLM throughput is 2-4x naive.
  • Chunked prefill (SARATHI, OSDI'24): split long prefills into chunks interleaved with decodes so one long prompt doesn't stall everyone.

4. What to read (in order)

  1. Paralleliq "Inference Stack" blog — routing vs serving layers.
  2. vLLM SOSP PagedAttention — §3-4 only (block manager, scheduling).
  3. Orca (OSDI'22) abstract + scheduling figure.
  4. NomadX "vLLM vs TGI vs Triton on K8s 2026" — decision framing.

5. Do (no GPU needed)

  • Tokenize 3 prompts with transformers (AutoTokenizer), count tokens, predict which has higher TTFT and why.
  • Draw request path: LB → router → pod → scheduler → KV check → prefill/decode → stream. Keep for interviews.

6. Interview one-liners

  • "Prefill is compute-bound, decode is bandwidth-bound — that's why quantization helps decode and disaggregation helps at scale."
  • "Decode has an ops:byte ratio near 2 × batch, far below the GPU's balance point, so it's memory-bound; prefill's matmuls have high reuse, so they're compute-bound."
  • "PagedAttention cut fragmentation; continuous batching keeps the GPU full; chunked prefill stops long prompts starving decodes."

7. Book cross-reference

  • Ch 2.1 neural nets + attention; Ch 2.2 LLM architecture, transformer blocks, MoE; Ch 2.3 image-gen mechanics; Ch 2.4 ops:byte + bottleneck calculation; Ch 2.5 optimizing attention.