PagedAttention & the KV Cache
The opening question of every LLM-inference interview: "why is serving memory-bound, and how does vLLM fix it?" If you can compute KV-cache size and explain paging in OS terms, you clear the bar.
Do you understand that the KV cache — not FLOPs — is the serving bottleneck? And that PagedAttention doesn't make attention faster, it makes memory dense so you can batch more sequences?
Why the KV Cache Dominates
During autoregressive decoding, the model caches the Key/Value tensors of every past token so it doesn't recompute attention each step. This cache is large and grows as generation proceeds. Naive servers reserve a contiguous chunk sized to max_len per request — wasting 60–80% of KV memory to fragmentation and over-reservation.
Reserve for max_len, but the sequence ends early — the tail sits unused.
Variable-sized contiguous reservations leave unusable gaps between allocations.
Space held for tokens not yet generated — reserved now, used maybe later.
PagedAttention = OS Virtual Memory
The core idea borrows straight from operating systems. Interviewers love the analogy — state it explicitly:
Because sequences reference physical blocks through the block table, parallel samples / beam branches sharing a prompt can point at the same physical blocks (ref-counted). On a divergent write, vLLM clones the block first — copy-on-write. This cut parallel-sampling memory by up to ~55% and lifted throughput up to ~2.2×.
The KV-Cache Formula — Know It Cold
You will be asked to size a KV cache on a whiteboard. Here's the derivation:
# 2 = Key AND Value
per_token = 2 * n_layers * n_kv_heads
* head_dim * dtype_bytes
# Llama-3-8B, FP16, GQA:
# 2 * 32 * 8 * 128 * 2 = 131072 B
# = 128 KB / token
# 2048-token ctx = ~256 MB / sequenceSpot the Bug: OOM at Startup
A candidate's vLLM server refuses to start — "No available memory for the cache blocks." Click the misconfigured line.
llm = LLM(model="meta-llama/Llama-3.1-8B-Instruct", gpu_memory_utilization=0.30, # too low! max_model_len=131072)KV blocks are carved from gpu_memory × gpu_memory_utilization − weights − activations. Set utilization high (0.9) to maximize cache; if you truly lack memory, shrink max_model_len or max_num_seqs, or add tensor parallelism — don't starve the cache.
Conceptual Round
1. What does PagedAttention actually improve?
2. Two sequences share a prompt prefix. How does vLLM avoid corruption when one diverges?
• "How does GQA/MQA change your KV math?" — Fewer n_kv_heads → proportionally smaller cache; that's why modern models use it.
• "Why is serving memory-bound, not compute-bound?" — Decode reads the whole KV cache + weights per single token (low arithmetic intensity).
• "What's left to optimize inside a block?" — Only the final partial block wastes space now.
For a WebGL walkthrough of vLLM's parallelism dimensions, see How vLLM Scales Across GPUs. This course is the interview-drill companion.
Continuous Batching
The other half of vLLM's throughput story. Interviewers want you to cleanly separate this scheduling technique from PagedAttention's memory technique — and explain why static batching is uniquely bad for LLMs.
Can you explain iteration-level scheduling and why output-length variance makes static batching waste the GPU? And do you keep continuous batching (scheduling) distinct from PagedAttention (memory)? They're complementary, not the same.
Static vs Continuous Batching
Group N requests, run to completion. Can't admit new work until the longest sequence finishes — short requests idle while one long generation runs. GPU starves.
Schedule at the iteration level: after every decode step, evict finished sequences and admit waiting ones. The batch changes token-by-token, keeping the GPU saturated.
vs HuggingFace Transformers: 14–24× throughput. vs TGI: 2.2–3.5×. This — combined with PagedAttention's dense memory letting more sequences fit — is where vLLM's throughput comes from.
Why Static Batching Is Uniquely Bad for LLMs
The winning answer names the property: output lengths vary wildly and are unknown up front. One request generates 20 tokens, another 2,000 — and you can't tell which until it emits an end-of-sequence token.
Batch of 8 starts together
7 finish at token 50
1 runs to token 2000
7 slots idle for 1950 steps
Continuous batching refills those 7 slots the instant they free up — no waiting for the straggler.
Match the Concept to Its Effect
Drag each concept onto what it primarily delivers.
PagedAttentionContinuous batchingIteration-level schedulingStatic batchingThe Two Knobs That Bound the Batch
LLM(model="...",
max_num_seqs=256,
max_num_batched_tokens=16384)Conceptual Round
1. Why is static batching specifically bad for LLM decode?
2. Relationship between PagedAttention and continuous batching?
• "Does continuous batching help latency?" — It boosts throughput/utilization; under heavy load individual-request latency can rise (queueing/preemption).
• "What refills a freed slot?" — The scheduler's waiting queue (Module 3).
• "Can prefill and decode share a batch?" — Yes, via chunked prefill (Module 3).
The Scheduler & Memory Management
Where the vLLM V1 engine earns its throughput. Preemption, prefix caching, and chunked prefill are the "do you actually know the internals" questions — and the OOM-is-handled-by-preemption-not-failure insight.
That running out of KV cache triggers preemption, not a crash; the recompute-vs-swap tradeoff; and that prefix caching only speeds prefill while chunked prefill is the TTFT↔ITL knob.
Queues & the Unified V1 Scheduler
Requests live in a waiting queue and a running queue. The V1 scheduler is unified: it drops V0's hard prefill-vs-decode split and represents each step as a token-budget dict like {request_id: num_tokens}. Default policy prioritizes decodes, then fills the remaining token budget with (chunked) prefill.
Preemption: Recompute vs Swap
Transformers are autoregressive, so KV demand grows mid-generation. When the cache fills, vLLM preempts running requests to free blocks and resumes them later — it does not fail the request.
Drop the KV blocks; recompute the prefix on resume. Prefill is cheap/parallel, so this avoids the CPU↔GPU copy cost — lower overhead in V1.
Copy KV blocks to CPU RAM, swap back on resume. Avoids recompute but pays the PCIe transfer both ways.
Frequent "...is preempted by PreemptionMode.RECOMPUTE... not enough KV cache space" with a rising total_cumulative_preemption_cnt means thrashing. Mitigate: raise gpu_memory_utilization, lower max_num_seqs/max_num_batched_tokens, or add TP/PP.
Spot the Bug: Throughput Collapse Under Load
A deployment runs fine at low load but throughput cratered when concurrency rose, with logs full of preemption messages. Click the root cause.
llm = LLM(model="meta-llama/Llama-3.1-70B", tensor_parallel_size=4, max_num_seqs=1024) # admits more than the cache holds # 1000 concurrent requests hit the serverTwo V1 Features Worth Naming
max_num_batched_tokens → better ITL; larger → better TTFT/throughput.
Conceptual Round
1. V1's default preemption mode, and why?
2. Automatic prefix caching speeds up which phase?
• "Why is APC safe to leave on at 0% hit rate?" — O(1) hash/eviction structures make overhead <1%.
• "Multi-tenant prefix-cache isolation?" — Use cache_salt and a crypto hash (sha256) to prevent cross-tenant collisions.
• "How does chunked prefill improve ITL?" — It caps prefill tokens per step and co-schedules decodes, so a giant prompt can't monopolize a forward pass.
Throughput vs Latency — Serving System Design
The system-design half of the vLLM interview. Everything flows from one roofline insight: prefill is compute-bound, decode is memory-bandwidth-bound. Get that, and disaggregation and speculative decoding fall out naturally.
The roofline framing — prefill compute-bound, decode memory-bound — and whether you can name the right latency metric (TTFT vs ITL) and the right lever (disaggregation shapes latency, it does not raise throughput).
Two Phases, Two Metrics
Whole prompt in one parallel pass → first token. Big matmuls, high arithmetic intensity → compute-bound. Determines TTFT.
One token at a time, re-reading all weights + KV per token. Low arithmetic intensity → memory-bandwidth-bound. Determines ITL / TPOT.
Because the two phases stress different resources, batching them together (chunked prefill) improves utilization — but they also compete, which is the core throughput↔latency tension.
System Design: A Low-Latency LLM Serving Stack
"Serve this model for real-time chat with tight p99 TTFT and ITL SLOs." The rubric a strong candidate hits:
TTFT (prefill-bound) and ITL (decode-bound) pull in different directions. Name both up front — a single "latency" number hides the real tradeoff.
Smaller max_num_batched_tokens → fewer/smaller prefills stalling decodes → better ITL. Larger → better TTFT/throughput. This is your first dial.
Run prefill and decode on separate instances; a connector transfers the KV cache. Now TTFT and ITL are tuned independently and prefill spikes can't bleed into ongoing decodes (tail-ITL control).
In the memory-bound decode regime, a cheap proposer + parallel verification cuts ITL — if QPS is low-to-medium. At high QPS the batch is already compute-saturated and it can hurt.
Disaggregated Serving — a Latency Lever, Not a Throughput One
Split prefill and decode across instances; a KV connector moves the cache between them.
• Tune TTFT and ITL independently (each instance gets its own TP/PP).
• Control tail ITL — prefill work can't spike into ongoing decodes.
• It does not increase throughput — it's an SLO/latency-shaping tool. Saying otherwise is the classic wrong answer.
--kv-transfer-config '{
"kv_connector": "NixlConnector",
"kv_role": "kv_both",
"kv_buffer_device": "cuda"}'The Roofline Round
1. Why is decode memory-bound while prefill is compute-bound?
2. When does speculative decoding backfire?
Speculative Decoding in One Screen
A cheap proposer guesses several future tokens; the target model verifies them all in one parallel forward pass. Accepted tokens skip sequential decode steps → lower ITL. It's lossless up to numeric precision.
• "Does disaggregation raise throughput?" — No; it independently shapes TTFT/tail-ITL.
• "Is speculative decoding lossy?" — No, lossless up to hardware precision.
• "One knob for TTFT vs ITL?" — max_num_batched_tokens: smaller favors ITL, larger favors TTFT/throughput.
Collective Communication Primitives
The distributed half begins. Every parallelism strategy is really a choice of collective. If you can map DDP/FSDP/TP/MoE to their primitives on demand — and recite the two all-reduce identities — you own this round.
That collectives must be called symmetrically (same order, same shape) on all ranks — mismatched calls are the #1 cause of hangs — and that you can name which primitive each training strategy uses.
The Six Primitives
AllReduce = ReduceScatter + AllGather (this is how ring all-reduce is built — Module 6).
AllReduce = Reduce + Broadcast (the naive/tree-ish view).
Which Parallelism Uses Which
Every replica holds the full model; gradients are averaged with one all-reduce (effectively AVG) per step.
Reduce-scatter gradients (keep your shard), all-gather params to materialize full weights just-in-time. Exactly the all-reduce decomposition, split across the step.
Exactly one all-reduce in forward and one in backward, per transformer block (Module 8 derives why).
Tokens are routed to the ranks holding their chosen experts (dispatch), then combined back — two all-to-alls. Summing would be semantically wrong.
Pipeline parallel uses point-to-point send/recv, not a collective — it passes activations between stages.
Match the Strategy to Its Collective
all-reducereduce-scatter + all-gatherall-to-allsend / recvThe PyTorch API
import torch.distributed as dist
dist.init_process_group("nccl") # CUDA
rank = dist.get_rank()
x = torch.ones(4, device=f"cuda:{rank}") * rank
dist.all_reduce(x, op=dist.ReduceOp.SUM)
# contiguous variants (faster):
# dist.reduce_scatter_tensor(out, inp)
# dist.all_gather_into_tensor(out, inp)Conceptual Round
1. Every GPU needs the averaged gradient. Which primitive, and its decomposition?
2. Why does MoE use all-to-all rather than all-reduce?
• "What happens if ranks call collectives in different order?" — Hang, crash, or silent corruption (undefined behavior).
• "Broadcast vs all-gather?" — Broadcast copies one rank's buffer to all; all-gather concatenates every rank's distinct shard.
• "Reduce vs all-reduce?" — Reduce leaves the result on the root only.
Collective Algorithms: Ring vs Tree
The whiteboard-derivation module. Interviewers ask you to derive ring all-reduce's 2(N−1)/N data volume and explain why it's bandwidth-optimal but latency-linear — and when tree wins instead.
Can you derive the ring all-reduce cost (not just recite "ring is fast"), explain its N-independence in bandwidth, and reason about the latency-vs-bandwidth flip that makes tree win for small messages / large N?
Ring All-Reduce — Two Phases
Split the K-element buffer into N chunks. Arrange the N GPUs in a ring. Two phases, each N−1 steps:
Scatter-reduce: send-right, receive-left, accumulate. After N−1 steps each GPU owns one fully-reduced chunk.
All-gather: same ring motion but overwrite. After N−1 steps everyone has the full result.
Watch a 4-GPU Ring All-Reduce
Step through the scatter-reduce phase across 4 ranks — this is the narration to give on a whiteboard.
The Formula to Memorize
Data moved per GPU in ring all-reduce:
The 2 = two phases (scatter-reduce + all-gather). (N−1) = steps per phase. K/N = chunk size. The product is bounded by ~2K regardless of N — that's what "bandwidth-optimal" means. Throughput is limited only by the slowest adjacent link.
You traverse the ring, so you pay ~2(N−1) serial hops of startup latency. Fine for hundreds of GPUs; it breaks down at thousands.
Tree All-Reduce — Latency-Optimal
Reduce up a tree to a root, broadcast back down: latency is logarithmic in N. A naive single binary tree wastes bandwidth (leaves only send or only receive), so NCCL 2.4+ uses double binary trees — ring-like bandwidth and log-N latency.
Bandwidth-bound regime. Saturates links; O(N) latency is amortized over big transfers.
Latency-bound regime. log(N) hops beat linear N. NCCL auto-switches — you don't hand-tune it, but you should know why.
The Derivation Round
1. Why is ring all-reduce's per-GPU data volume ~independent of N?
2. All-reducing a 4 KB tensor across 512 GPUs — ring or tree?
• "Cost model?" — Ring: 2(N−1)α + 2(N−1)/N·Kβ; tree: 2·log₂(N)·α + bandwidth term (α=per-hop latency, β=inverse bandwidth).
• "Who chooses ring vs tree?" — NCCL, adaptively by message size and world size.
• "Where does the '2' come from?" — The two phases: scatter-reduce then all-gather.
NCCL, Topology & Compute/Comm Overlap
The hardware-reality module. Bus vs algorithm bandwidth, the NVLink/PCIe/InfiniBand hierarchy, and DDP gradient bucketing — plus the roofline test for when communication is your bottleneck.
That "bandwidth" is ambiguous — bus bandwidth is what you compare to hardware peak — and that overlap needs independent compute to hide behind. Topology awareness (inter-node IB is the bottleneck) is the senior signal.
The Interconnect Hierarchy
Hundreds of GB/s per pair; H100 NVLink 4 ~900 GB/s aggregate/GPU. Highest bandwidth, lowest latency. Put TP here.
Gen4 x16 ~32 GB/s, Gen5 ~64 GB/s. An order of magnitude slower than NVLink.
NDR 400 Gb/s ≈ 50 GB/s/NIC. GPUDirect RDMA lets the NIC hit GPU memory directly. ~10–20× slower than NVLink.
Implication: hierarchical collectives (reduce-scatter within node → all-reduce across nodes → all-gather within node) keep bulk traffic on NVLink.
Bus Bandwidth vs Algorithm Bandwidth
A favorite "did you actually run nccl-tests" question. The two are not the same:
1 GB all-reduce over 8 GPUs, measured algbw = 100 GB/s. Factor = 2(N−1)/N = 2×7/8 = 1.75. So busbw = 175 GB/s — that's what you judge against the NVLink peak, not the 100. Factors: all-reduce 2(N−1)/N; reduce-scatter/all-gather/all-to-all (N−1)/N; broadcast/reduce = 1.
Overlapping Compute & Communication
DDP's canonical trick: gradient bucketing. The Reducer groups gradients into buckets in reverse parameter order and fires an async all-reduce as soon as each bucket fills — while backward keeps computing earlier layers.
work = dist.all_reduce(
bucket, async_op=True)
# ... independent compute overlaps ...
work.wait() # CUDA: stream dep, not CPU blockSpot the Bug: Throughput Collapse at Scale
A model runs 8-GPU TP fine on one node. Scaling TP to 16 across two nodes tanks throughput. Click the design mistake.
# 2 nodes, 8 GPUs each, connected by InfiniBandllm = LLM(model=..., tensor_parallel_size=16) # TP across nodes!# TP all-reduce fires every transformer layerTP = GPUs per node (NVLink); PP = number of nodes (slow link). TP's all-reduce is heavy and per-layer, so it must stay on the fast intra-node fabric. Pipeline parallel passes only activations between stages — cheap enough for inter-node.
Conceptual Round
1. Why does DDP bucket gradients in reverse parameter order?
2. DDP throughput/GPU collapses going 8 → 512 GPUs. Diagnosis?
• "Roofline test for comm bottleneck?" — Compare t_comm = bytes/busbw vs t_compute = FLOPs/peak; if comm > compute, overlap can't hide it.
• "What is GPUDirect RDMA?" — NIC DMAs straight to GPU memory, skipping the host bounce.
• "Does async_op=True block the CPU?" — On CUDA, wait() is a stream dependency, not a CPU block.
Custom Fused Comm Kernels & System Design
The staff-level capstone. Derive the one-all-reduce-per-block TP pattern, know why one-shot/two-shot fused kernels beat NCCL for small TP messages, then tie the whole course together in an MoE serving design.
Can you derive (not recite) the colwise→rowwise TP pattern that yields exactly one all-reduce per block? And do you know TP all-reduce is on the critical path and can't overlap — which is why fused one-shot kernels exist?
Tensor Parallelism: One All-Reduce Per Block
The MLP is Y = GeLU(X·A)·B. The trick is sharding the two matmuls so no communication is needed between them:
# A split COLUMN-wise: A = [A1, A2]
Y1_half = GeLU(X @ A1) # local
Y2_half = GeLU(X @ A2) # local
# B split ROW-wise: B = [B1; B2]
Z1 = Y1_half @ B1
Z2 = Y2_half @ B2
Y = all_reduce(Z1 + Z2) # ONE all-reduceNet: the conjugate operators f (identity fwd / all-reduce bwd) and g (all-reduce fwd / identity bwd) give one all-reduce in forward, one in backward, per block. Attention is analogous: QKV projection column-parallel, output projection row-parallel.
Why NCCL Isn't Enough for TP
TP all-reduce messages are small, latency-bound, and on the critical path — the next matmul needs the result, so they can't overlap (unlike DDP). NCCL ring is suboptimal here. SymmetricMemory exposes peers' GPU memory directly so you can write custom fused kernels.
Every rank reads all peers' buffers directly and reduces locally. ~1 round trip → lowest latency. Ideal for small TP tensors.
Reduce-scatter then all-gather — less redundant movement. The symm-mem analogue of the ring decomposition.
import torch.distributed._symmetric_memory as symm_mem
t = symm_mem.empty(N, device=...)
hdl = symm_mem.rendezvous(t, group) # exchange peer ptrs
torch.ops.symm_mem.one_shot_all_reduce(t, "sum", group)
torch.ops.symm_mem.two_shot_all_reduce_(t, "sum", group)System Design: Serve a Large MoE Model
"Design distributed inference for a DeepSeek-style MoE model that doesn't fit on one node." This ties the whole course together — the rubric:
TP intra-node (NVLink) for the dense attention/MLP; expert parallelism (all-to-all) to shard experts across ranks; DP on attention layers for throughput. Match each dim to its interconnect.
DP ranks are not independent for MoE — every rank must align forward passes and run dummy forward passes when idle so the expert all-to-all stays synchronized. vLLM's DP Coordinator handles this.
PagedAttention for dense KV memory, continuous batching + chunked prefill for utilization, prefix caching for shared system prompts (Modules 1–4).
TP all-reduce is small and blocking → one-shot fused kernels over NVLink. Keep all-to-all expert traffic on the fastest fabric available; watch busbw vs peak (Module 7).
The Staff-Level Round
1. Why column-split the first MLP matmul and row-split the second?
2. Why do fused one-shot all-reduce kernels matter for TP but not DDP?
Eight modules: PagedAttention, continuous batching, the V1 scheduler, and throughput/latency — then collective primitives, ring vs tree, NCCL topology, and custom fused kernels. The through-line: name the resource that bounds you (KV memory, memory bandwidth, interconnect bandwidth, or latency), then pick the technique that relieves it. That framing is the senior/staff signal.
• vLLM V1 engine is the default; recompute is the default preemption mode; APC + chunked prefill are on by default.
• Ring all-reduce = 2(N−1)/N; NCCL uses double-binary trees for small messages / large N.
• TP colwise→rowwise = one all-reduce/block; _symmetric_memory (one-shot/two-shot) is alpha.
• "Why must idle DP ranks run dummy forward passes in MoE?" — The expert all-to-all is synchronized across all ranks; a lagging rank stalls or desyncs the collective.
• "One-shot vs two-shot threshold?" — A latency-vs-bandwidth tradeoff (small vs large message), not a fixed size.
• "Where does fusion help most?" — Folding the reduction into the matmul epilogue removes the kernel-launch boundary on the critical path.
For Triton-level vLLM kernel internals, see vLLM Optimization Deep Dive; for the animated parallelism walkthrough, How vLLM Scales Across GPUs. Pair with the PyTorch Interview Prep course for the framework layer.