LLM inference

Two phases, two bottlenecks

An LLM serves a request in two distinct phases:

• Prefill — process the prompt (N tokens) in one forward pass. Compute scales as N². FLOP-bound for long prompts.
• Decode — generate one token at a time. Each step recomputes one query against the entire KV cache. Tiny compute per step but enormous memory reads.

Why decode is bandwidth-bound

Each decoded token requires reading all model weights (e.g., ~140 GB for a 70B model in BF16) plus the full KV cache for that request — every single step. Compute is one Q vector against the cache; the dominant cost is memory traffic. Batching helps because you read the weights once and reuse them across many requests' Q vectors.

The formula — get it right under interview pressure

During autoregressive decode, K and V for previous tokens don't change — cache them. At step t, only compute Q, K, V for the new token; append K,V to the cache; attention is Q (1×d) attending to cache (t×d) → O(t·d) per step.

Per token, per layer: 2 · n_kv_heads · d_head · n_bytes (the leading 2 is K + V).

Total: n_layers · seq_len · 2 · n_kv_heads · d_head · n_bytes.

The OS-VM analogy

(Kwon 2023, arxiv 2309.06180.) Inspired by OS virtual memory:

• KV cache is split into fixed-size blocks (e.g., 16 tokens).
• Each request has a "block table" mapping logical → physical blocks.
• New tokens allocate new blocks on demand.
• Different requests can share blocks (e.g., common prefix).

Eliminates fragmentation, enables prefix sharing, supports complex sampling (beam search, parallel sampling) cheaply.

Static vs continuous

The algorithm

(Leviathan 2023, arxiv 2211.17192.) A small draft model generates K tokens; the target model verifies all K in parallel with one forward pass; accept tokens up to first rejection, sample one more from corrected distribution. Always exact (samples from target distribution).

p_emit(t) = p_draft(t) · min(1, p_t/p_d)              [accepted path]
          + (1 − Σ p_draft · accept) · p_residual(t)   [rejected path]
        = p_target(t)                                  [the algebra works out]

Speedup ~2–3× depending on draft acceptance rate. Best when draft is fast (~5% of target cost) and aligned (high acceptance).

EAGLE / EAGLE-2/3

(Li 2024, arxiv 2401.15077.) Uses target model's hidden states (not just tokens) as input to a small auto-regressive head that drafts. Higher acceptance because the draft sees richer context.

Medusa

(Cai 2024.) Multiple parallel decoding heads on the target model; each head predicts token at position +1, +2, +3, etc. Tree-based verification. No separate draft model. Simpler deployment.

Lookahead decoding

(Fu 2024.) Generates n-grams via Jacobi iteration on the target model itself; verifies through a unified attention pattern. Draft-free.

INT8 / FP8 — the W8A8 family

Per-channel weight quantization; activations either quantized too (W8A8) or kept in FP16 (W8A16). LLM.int8() (Dettmers) handles outliers via mixed precision. FP8 is native in H100 — generally W8A8 with per-tensor or per-channel scales.

SmoothQuant (Xiao 2023, arxiv 2211.10438): activations have outlier channels that ruin quantization; migrate the difficulty from activations to weights via a diagonal scale s:

(X · diag(s)⁻¹) · (diag(s) · W)

Now activations have smaller outliers and weights absorb the scale. This is the standard recipe for production W8A8 to actually work.

W4A16 — most common production deployment

INT4 weights (GPTQ/AWQ), bf16 activations. Smaller than W8A8 in storage but equal compute (matmul still runs in bf16). Pure W4A4 is much harder due to activation outliers.

• GPTQ (Frantar 2022, arxiv 2210.17323) — post-training, layer-by-layer quantization. Uses second-order info (approximate Hessian via calibration set) to minimize MSE on activations. Per-group quantization (group size 128).
• AWQ (Lin 2023, arxiv 2306.00978) — protect "salient" weight channels by scaling — small scaling factors applied so quantization error on important channels is reduced. Activation-aware.

NF4 (QLoRA)

(Dettmers, arxiv 2305.14314.) "NormalFloat" — quantization levels chosen to match a normal distribution's quantiles. Good for weights (which are roughly Gaussian).

Microscaling (MX)

Block-wise scales — better outlier handling. MXFP8 / MXFP6 / MXFP4. Hardware support in Blackwell.

GGUF

llama.cpp's K-quants (Q4_K_M, Q5_K_S, etc.) — block-wise non-uniform schemes good for CPU/edge inference. Designed for the GGUF container format.

FA1 — the IO-aware idea

(Dao 2022, arxiv 2205.14135.) Computes attention in tiles. Standard softmax requires the full row to normalize. Online softmax: maintain running max and sum, rescale as new tiles arrive. Avoids materializing the L×L attention matrix in HBM. IO-aware; ~3× faster for typical seq lengths, much more for long.

FA2 — better partitioning

(Dao 2023, arxiv 2307.08691.) Improved work partitioning, reduced non-matmul FLOPs, parallelizes across sequence dim. Better GPU occupancy.

FA3 — H100-specific

FA3 (Shah, Bikshandi, Ye, Thakkar, Ramani, Dao 2024, arxiv 2407.08608). Note: FA3 lead author is Jay Shah, not Tri Dao (who is on the paper). Frontier-lab interviewers actually probe the attribution.

The full menu

• Greedy — argmax. Deterministic. Boring; prone to repetition.
• Temperature — divide logits by T. T<1 sharper, T>1 flatter. T=0 = greedy.
• Top-k — keep top k logits, renormalize, sample.
• Top-p (nucleus) (Holtzman 2019) — keep smallest set whose cumulative prob ≥ p, renormalize, sample. p=0.9 or 0.95 typical.
• Min-p — keep tokens with prob ≥ p · max_prob. Adaptive — wider when distribution flat.
• Beam search — maintain k beams; expand all; keep top k by total log-prob. Good for translation, bad for creative gen (mode-collapsed).
• Contrastive search (Su 2022) — max α·logp − (1−α)·max_sim_to_history. Reduces repetition.
• Repetition penalty / frequency / presence penalties (OpenAI-style) — hacky but effective.

The four numbers everyone confuses

Tradeoff: low TTFT + low ITL = expensive (small batches, lots of GPUs idle). High aggregate throughput = large batches, slower per-user. SLA-driven scheduling balances these.

Why disaggregate

Prefill is compute-bound, decode is memory-bandwidth-bound. Running them on the same GPU causes interference — decode latency spikes during prefill (head-of-line blocking).

Disaggregation: separate prefill and decode pools. Prefill GPUs do bulk compute, then transfer KV cache to decode GPUs over fast interconnect (NVLink, RDMA). Independent scaling.

The canon

• Splitwise (Patel 2024, arxiv 2311.18677) — Microsoft's original disaggregation paper.
• DistServe (Zhong 2024, arxiv 2401.09670) — Berkeley, similar idea, careful cluster sizing analysis.
• Mooncake (Qin 2024, arxiv 2407.00079) — Kimi's open-source disagg + KVCache-store design (separates KV cache as a tier between RAM and HBM).

DeepSeek's open-source serving stack uses this pattern.

Chunked prefill (Sarathi-Serve) — the single-pool alternative

Sarathi-Serve (Agrawal 2024, arxiv 2403.02310): instead of running long prefills as one big forward pass (which freezes decode for everyone), chunk the prefill into smaller pieces and interleave them with decode iterations. Removes TTFT spikes during sustained traffic. Now standard in vLLM and TensorRT-LLM.

Prefix caching

When many requests share a prompt prefix (system prompts, few-shot examples, RAG context), cache the KV for that prefix and reuse. Hash the prefix tokens, look up in a KV-cache pool. vLLM's PagedAttention enables sharing at block granularity.

Massive throughput wins for chatbots with shared system prompts and for agentic workloads with growing transcripts.

The KV-compression toolkit

• KIVI (Liu 2024) — per-channel quantization of K, per-token quantization of V → INT2 KV cache with minimal quality loss.
• H2O / Heavy Hitters (Zhang 2023, arxiv 2306.14048) — identify the small set of "heavy hitter" tokens that dominate attention; evict the rest. Drastically smaller cache, ~5% quality drop.
• SnapKV, PyramidKV — variants on eviction with per-layer policies.
• ChunkAttention — identify and dedup shared prefix chunks across distinct requests via prefix tree.
• CLA / MLKV — cross-layer KV sharing (use the same KV across multiple consecutive transformer layers — DeepSeek-V2 also explores this).

The matrix

LLM inference quiz — readiness check

1. Walk through one decode step inside vLLM.
   Show answer

   Scheduler picks ready requests up to memory limit. For each: compute Q, K, V from previous token's hidden state; write K, V to next free block in the request's block table. PagedAttention kernel: attention over all blocks for that request. FFN. Sample next token. Update block table. New requests joining first do prefill (one big forward over their prompt).

2. Why is decode memory-bandwidth-bound?
   Show answer

   Each decoded token requires reading all weights (~140 GB for 70B fp16) plus the full KV cache. Compute is small (one new Q vector). Batching helps because you reuse one weight read across many requests in the batch.

3. How would you reduce TTFT for 100k-token prompts?
   Show answer

   Chunked prefill (Sarathi-Serve), prefix caching, sequence/context parallel for prefill, more GPUs allocated to that request. The bottleneck is FLOPs.

4. Speculative decoding tradeoff?
   Show answer

   Wins when draft acceptance rate is high (similar distribution to target) and draft is fast (≤ ~5% target cost). Loses if draft too divergent (low acceptance) or too slow (overhead dominates).

5. Compare GQA vs MQA vs MLA on KV cache size.
   Show answer

   MHA: 2·n_heads·d_head per token per layer. MQA: 2·d_head. GQA(g): 2·g·d_head. MLA: 2·d_latent (much smaller, e.g., 512 vs 8192 for d_model=8192). Quality: MHA ≥ GQA ≥ MQA, MLA matches MHA at 7% cache size.

6. What's the bottleneck for serving 10k QPS chat?
   Show answer

   Memory bandwidth (decode), KV cache size (concurrent context), GPU count (cost). Mitigations: GQA/MLA, FP8 weights, prefix caching, continuous batching, speculative decoding, model routing (cheap → reasoning).

7. Design a serving stack for a reasoning model with 8k hidden CoT tokens per request.
   Show answer

   Heavy decode load (8k tokens × users); huge KV cache. Disaggregated prefill (cheap) and decode (expensive); aggressive prefix caching across reasoning segments; queue with priority for premium tier; possibly spec-decoding with a weaker model for early CoT phase.

8. How does FA3 use H100 features?
   Show answer

   TMA (Tensor Memory Accelerator) for async memory copy from HBM → SMEM. Warp-specialized producer/consumer pattern overlapping data move with compute. FP8 matmuls with two-stage scaling. Up to 75% of H100 peak (~740 TFLOPS bf16).

9. Prove speculative decoding is exact.
   Show answer

   For drafted token t: accept with prob min(1, p_t/p_d). On reject: sample from residual (p_t − p_d)_+ / Z. Marginal distribution of emitted token = p_d · accept + (1 − p_d · accept) · residual = p_t (algebra works out). Each emitted token is exactly distributed as p_t.

10. Worked example: KV cache for Llama 3 70B at 128k context?
    Show answer

    GQA: 8 KV heads, d_head=128, 80 layers, bf16. Per token per layer: 2 · 8 · 128 · 2 = 4096 B. Per token: × 80 = ~320 KB. At 128k tokens: ~40 GB per request. MHA equivalent (64 KV heads): 8× = ~320 GB.

11. Why disaggregate prefill and decode?
    Show answer

    Prefill is compute-bound; decode is memory-bandwidth-bound. Same GPU running both → decode latency spikes during prefill. Disaggregation: separate pools, transfer KV cache via NVLink/RDMA. Independent scaling. Splitwise / DistServe / Mooncake.

12. Difference between PagedAttention block size 16 vs 128?
    Show answer

    Smaller (16): less internal fragmentation, more granular sharing across requests, more block-table overhead. Larger (128): less metadata, fewer GPU memory operations per attention, more wasted space at sequence ends. 16 is the vLLM default; experimentation needed for specific workloads.

13. What is RadixAttention (SGLang)?
    Show answer

    Prefix tree (radix trie) over KV cache. When a new request shares prefix with cached requests, the tree walk gives O(log n) lookup of the longest matching prefix. Enables aggressive prefix-cache reuse with low overhead. SGLang's contribution.

14. Top-p vs top-k vs min-p?
    Show answer

    Top-k: keep top k probabilities. Top-p (nucleus): keep smallest set with cumulative prob ≥ p. Min-p: keep tokens with p ≥ p_threshold · max(p) — adaptive (wider in flat distributions).

15. EAGLE vs Medusa for speculative decoding?
    Show answer

    EAGLE: small auto-regressive head conditioned on target's hidden states (richer context → high acceptance). Medusa: multiple parallel heads predicting +1, +2, +3 with tree verification. EAGLE-2/3 push further. Medusa simpler deployment; EAGLE higher acceptance.

16. What is SmoothQuant?
    Show answer

    Migrate quantization difficulty from activations to weights via diagonal scaling: (X · diag(s)⁻¹) · (diag(s) · W). Now activations have smaller outliers, weights absorb the scale. Standard recipe for production W8A8.

17. What's the difference between W4A16 and W8A8?
    Show answer

    W4A16: INT4 weights, bf16 activations. Smaller storage; matmul still in bf16. Most common production. W8A8: INT8 weights AND activations. Faster matmul (uses int8 tensor cores) but harder due to activation outliers. Need SmoothQuant.

18. What is chunked prefill (Sarathi-Serve)?
    Show answer

    Instead of running long prefills as one big forward (freezing decode for all users), chunk the prefill and interleave with decode iterations. Removes TTFT spikes during sustained traffic. Now standard in vLLM and TensorRT-LLM.

19. What is KIVI / H2O?
    Show answer

    KIVI: per-channel quant of K, per-token quant of V → INT2 KV cache with minimal quality loss. H2O (Heavy Hitters): identify the small set of tokens that dominate attention; evict the rest. Drastically smaller cache; ~5% quality drop.

20. Continuous batching vs static batching — explain.
    Show answer

    Static: collect N requests, run all to completion. Short requests wait for long ones. Continuous: per-iteration scheduling. After each forward pass, finished requests leave; new requests join. Maximizes GPU utilization. vLLM, TGI, TensorRT-LLM all do this.