You have a trained model and a stream of prompts. Turning that into an endpoint that keeps a $30,000 GPU busy, never runs out of memory, and answers each request inside its latency budget is one of the hardest systems problems in the stack. This lesson builds that endpoint from first principles and then walks the real internals of vLLM — the engine most production LLM serving runs on — with the actual component names, the scheduling loop, the memory manager, and code you can map onto the source.
If you want the exhaustive code walkthrough, Aleksa Gordić’s vLLM deep dive traces every class; this lesson is the systems view of the same machine: the why behind each mechanism, the number that forces it, and the failure it prevents.
The workload: two phases and one memory hog
Everything follows from one fact: LLM inference is autoregressive. The model emits one token per forward pass and feeds it back to produce the next. A single request has two phases with opposite hardware profiles:
- Prefill — the whole prompt goes through the network in one parallel forward pass. Lots of math on many tokens at once → compute-bound (saturates the GPU’s tensor cores).
- Decode — tokens are generated one at a time, each a single token through the entire network. Almost no math, but every step must stream all model weights from HBM → memory-bandwidth-bound (tensor cores idle, waiting on memory).
The bridge between them is the KV cache. Attention at step t needs the key/value vectors of every previous token; recomputing them each step would make generation quadratic, so we cache them. That cache is the resource that caps everything. Per token, per request:
kv_bytes_per_token = 2 (K and V) × num_layers × num_kv_heads × head_dim × dtype_bytesFor Llama-3-8B (32 layers, 8 KV heads, head_dim 128, fp16): 2 × 32 × 8 × 128 × 2 ≈ 131 KB/token. A 2,048-token conversation pins ~270 MB of KV cache — for one request. Weights are fixed; KV cache scales with concurrency × length, and it is what decides how many requests you can batch.
Two metrics anchor quality of service, one per phase:
- TTFT (time to first token) = queueing + prefill.
- TPOT / ITL (time per output token / inter-token latency) = the decode step time.
Interactive chat wants low TTFT and steady TPOT; batch jobs want raw throughput. Nearly every knob below trades one against the other.
Why the obvious batching fails
Because decode is memory-bound, serving one request at a time is ruinous — you read the full weights to make a single token for a single user. Batching fixes that: read weights once, make a token for many requests. But the naive form, static (request-level) batching — collect N requests, run until all finish — breaks on autoregressive work:
Static batch of 3 requests (each cell = one decode step; ▓ = real work, · = wasted slot):
t→ 1 2 3 4 5 6 7 8 9 10 11 12
R1 ▓ ▓ ▓ ⏹ · · · · · · · · done at t=3, slot wasted for 9 steps
R2 ▓ ▓ ▓ ▓ ▓ ▓ ▓ ⏹ · · · · done at t=7
R3 ▓ ▓ ▓ ▓ ▓ ▓ ▓ ▓ ▓ ▓ ▓ ⏹ done at t=11
↑ a new request that arrived at t=2 cannot start until t=12Three structural flaws: head-of-line blocking (short replies pinned behind the longest), no mid-flight admission (arrivals wait for the whole batch to drain), and padding waste. Utilization routinely sits at 10–20%. The bug is the granularity: batching at the request level when the natural unit of work is a token.
Continuous batching — Orca’s iteration-level scheduling
Orca (OSDI 2022) fixed it by scheduling at the iteration (token) level, not the request level. This is continuous (a.k.a. in-flight, iteration-level) batching, and it is what vLLM does every step.
Continuous batch — the set changes every iteration:
t→ 1 2 3 4 5 6 7 8 9 10 11 12
R1 ▓ ▓ ▓ ⏹ done → slot freed at t=4
R4 ▓ ▓ ▓ ▓ ⏹ R4 admitted into R1's freed slot at t=4
R2 ▓ ▓ ▓ ▓ ▓ ▓ ▓ ⏹
R5 ▓ ▓ ▓ ▓ ▓ admitted when R2 finishes
R3 ▓ ▓ ▓ ▓ ▓ ▓ ▓ ▓ ▓ ▓ ▓ ⏹
↑ every step: evict finished, admit waiting. No slot idles.After each decode step the scheduler evicts finished requests and admits waiting ones. To run requests of different lengths (and phases) in one forward pass, Orca adds selective batching: the position-independent ops (the big matmuls, MLP, layernorm) are batched across all sequences by flattening them into one long “super-sequence”; attention, which is inherently per-sequence, is computed per request using a mask so each token only attends to its own sequence. No right-padding is needed.
Flattened "super-sequence" fed to the GPU in one step (prefill + decode mixed):
[ R4 prompt tok0 tok1 tok2 | R2 decode tokN | R3 decode tokM | R5 prompt tok0 tok1 ]
└── prefill chunk ──┘ └─ 1 token ─┘ └─ 1 token ─┘ └── prefill chunk ─┘
attention mask keeps each request attending only to its own KV blocksThis is table stakes now (vLLM, TGI, TensorRT-LLM’s “in-flight batching”). It keeps the GPU busy — and immediately exposes the next bottleneck: how many sequences fit in KV memory, and how that memory is managed.
PagedAttention — vLLM’s KV-cache memory manager
Before vLLM, a server reserved one contiguous KV region per request, sized to the max possible length (attention kernels wanted contiguous memory). Catastrophic:
- Internal fragmentation — a 50-token reply holding a 2,048-token reservation wastes ~97%.
- External fragmentation — fixed max-size holes that nothing fits into.
- No sharing — identical system prompts each store their own copy.
vLLM (SOSP 2023) borrowed virtual-memory paging and applied it to the KV cache — PagedAttention:
- The KV cache is a pool of fixed-size physical blocks, each holding
block_sizetokens (default 16). - Each request has a block table (a page table) mapping its logical token positions → physical block numbers, which need not be contiguous.
- Blocks are allocated on demand, one at a time as the sequence grows.
Logical view of R1's tokens Block table (R1) Physical KV blocks in HBM
(block_size = 4 for the picture) logical → physical (shared pool, any order)
┌──────────────────────────┐ ┌───────────────┐ ┌───────┐ blk0 (R2)
│ t0 t1 t2 t3 | t4 t5 t6 t7 │ │ 0 → 7 │ │ ... │
│ t8 t9 ... | │ │ 1 → 3 │ ├───────┤ blk3 ← R1 logical#1
└──────────────────────────┘ │ 2 → 0? no →11 │ ├───────┤ ...
logical blocks 0,1,2 └───────────────┘ ├───────┤ blk7 ← R1 logical#0
├───────┤ blk11← R1 logical#2
A 50-token reply uses ⌈50/16⌉ = 4 blocks — and not one byte more.Fragmentation drops to under one block per sequence, so you pack far more concurrent requests into the same GPU, and bigger effective batches mean higher throughput. The indirection also unlocks sharing:
- Prefix / prompt caching — requests with the same system prompt point their block tables at the same physical blocks (computed once).
- Parallel sampling / beam search — branches share the prompt’s blocks copy-on-write; a block is duplicated only when a branch writes to it.
vLLM reported 2–4× the throughput of Orca-generation systems at equal latency, almost entirely from fitting more sequences in memory. During the forward pass, a slot_mapping array tells the CUDA kernel exactly which physical slot each token’s K/V goes to, and the PagedAttention kernel gathers K/V through the block table.
The engine, concretely (vLLM V1)
Here is the machine the requests flow through:
flowchart TB
U[Client / OpenAI API] --> LLM[LLMEngine / AsyncLLM<br/>tokenize, output processing]
LLM --> EC[EngineCore]
subgraph EC[EngineCore]
SCH[Scheduler<br/>waiting + running queues<br/>FCFS / priority]
KV[KVCacheManager<br/>free_block_queue<br/>req_to_blocks, prefix cache]
EX[Model Executor<br/>UniProc / MultiProc]
end
SCH <--> KV
EX --> W[Worker + ModelRunner<br/>weights, KV tensors, sampler<br/>PagedAttention kernels]
W --> G[(GPU HBM<br/>KV block pool)]
- LLMEngine / AsyncLLM — tokenizes prompts, builds request objects, detokenizes and streams output.
- EngineCore — the beating heart; owns the scheduler, the KV-cache manager, and the model executor.
- Scheduler — keeps a
waitingand arunningqueue and, each step, decides which requests run and how many tokens each contributes. - KVCacheManager — owns the
free_block_queuepool, thereq_to_blocksmapping, and the prefix-cache hash table. - Model Executor / Worker / ModelRunner — drives the forward pass on the GPU(s); holds weights, KV tensors, buffers (
input_ids,positions,slot_mapping), and the sampler.UniProcExecutorfor one GPU;MultiProcExecutorfor tensor/pipeline parallelism.
Initialization: profiling the KV cache
You can’t know num_gpu_blocks up front — it depends on the model, activations, and gpu_memory_utilization (e.g. 0.9 = use 90% of VRAM). vLLM measures it:
# Conceptually, at startup:
free = total_vram * gpu_memory_utilization
run_profiling_forward_pass(max_batch) # measure weights + peak activation memory
kv_budget = free - weights_bytes - peak_activation_bytes
block_bytes = 2 * block_size * num_kv_heads * head_dim * dtype_bytes * num_layers
num_gpu_blocks = kv_budget // block_bytes # e.g. tens of thousands of 16-token blocks
# total token capacity = num_gpu_blocks * block_sizeThat single number — num_gpu_blocks — is the hard ceiling on concurrency × length. Every scheduling decision is really “do I have a free block?”
The step() loop
The engine is a loop over step(). Each call schedules a batch, runs one forward pass, samples, and post-processes:
def step(self):
scheduler_output = self.scheduler.schedule() # pick requests + token budget, allocate blocks
model_output = self.executor.execute_model(scheduler_output) # 1 forward pass on the GPU
sampled = self.sampler.sample(model_output.logits, sampling_params)
return self.postprocess(sampled) # append tokens, detokenize, check stop (EOS, max_len, stop strs)
def schedule(self):
budget = self.max_num_batched_tokens
scheduled = []
# 1) decodes first (cheap: 1 token each), from the running queue
for req in self.running:
if self.kv.allocate_slots(req, num_tokens=1): # needs a block only when it crosses a boundary
scheduled.append((req, 1)); budget -= 1
else:
self.preempt(req) # out of blocks → evict a victim
# 2) then prefills from the waiting queue, up to the token budget
for req in list(self.waiting):
n = min(req.num_prompt_tokens, budget) # chunked prefill: cap tokens/step
if n > 0 and self.kv.allocate_slots(req, num_tokens=n):
scheduled.append((req, n)); budget -= n
self.running.append(req); self.waiting.remove(req)
return scheduledallocate_slots is where paging lives:
def allocate_slots(self, req, num_tokens):
need = ceil((req.num_computed_tokens + num_tokens) / block_size) - len(self.req_to_blocks[req])
if need > len(self.free_block_queue):
return False # caller preempts
for _ in range(need):
self.req_to_blocks[req].append(self.free_block_queue.popleft())
return TrueNotice the elegance: a decode step needs a new block only when the sequence length crosses a 16-token boundary; otherwise it just writes into the current block. Admission, eviction, and growth are all “pop from / push to free_block_queue.”
Prefill vs decode, and chunked prefill
Mixing a huge prefill with everyone’s decode is dangerous: a 30,000-token prompt’s prefill is compute-heavy and stalls the decode steps of every other request (one user’s TTFT becomes everyone’s TPOT stutter). Chunked prefill caps how many prompt tokens any single step admits (long_prefill_token_threshold), splitting a long prefill across several steps interleaved with decodes:
Without chunked prefill: [ ─────── R_long prefill (30k tok) ─────── ] decodes stall
With chunked prefill: [ prefill chunk | others' decodes | prefill chunk | decodes | ... ]
smooth TPOT for everyone; R_long's TTFT slightly higherPrefill/decode disaggregation goes further — run prefill and decode on separate worker pools so a prefill burst never touches decode latency. The prefill instance writes KV to a connector (e.g. LMCache/NIXL); the decode instance loads it via start_load_kv before its first step.
Prefix caching: hashing the KV blocks
If a block’s tokens (and everything before it) are identical to a block already computed, its KV is identical too — so reuse it. vLLM hashes each full 16-token block as a chain:
# block hash = f(previous_block_hash, this_block's_token_ids, extra_keys like lora_id/salt)
h = None
for block_tokens in chunks(prompt_ids, block_size):
if len(block_tokens) < block_size: break # only full blocks are cacheable
h = hash((h, tuple(block_tokens), lora_id))
block_hashes.append(h)
# at schedule time:
hit_blocks = find_longest_cache_hit(block_hashes) # walk cached_block_hash_to_block
for b in hit_blocks:
b.ref_count += 1 # share it; copy-on-write on divergenceTwo requests sharing a 2,000-token system prompt now skip ~125 blocks of prefill each — a large TTFT win at high QPS. Blocks are reference-counted and returned to free_block_queue when the count hits zero. On by default (enable_prefix_caching).
When memory runs out: preemption
Under load the block pool empties. The scheduler must preempt an in-flight request to free its blocks for a higher-priority one, then resume it later. Two strategies:
- Recompute — drop the victim’s KV blocks; when it resumes, re-run its prefill. Cheap memory, costs compute. Default for short sequences.
- Swap — copy the victim’s KV blocks to CPU RAM and back. Costs PCIe bandwidth, saves recompute. Better for long sequences.
Preemption is the quiet killer: it silently inflates TTFT/TPOT for victims while the GPU dashboard still reads “busy.” Track preemption count and the queued-to-running ratio; alert before KV utilization hits 100%.
Squeezing decode latency: speculative decoding
Decode is one-token-at-a-time and memory-bound, so the GPU is underused per step. Speculative decoding fills that slack: a cheap draft proposes k tokens, the big model verifies all k in a single forward pass, accepting the longest correct prefix (with a probabilistic accept/reject that preserves the target distribution).
sequenceDiagram participant D as Draft (small / n-gram / EAGLE) participant T as Target (big model) D->>D: propose k tokens (cheap) D->>T: context + k draft tokens T->>T: 1 forward pass → k+1 distributions T->>T: accept longest correct prefix, resample the first reject Note over T: 1 big-model pass yields ≥1 (often 2–4) tokens
vLLM V1 ships draft-model-free variants: n-gram (match a recent substring, propose what followed), EAGLE (a light MLP head predicting the next hidden state), Medusa (parallel linear heads). Wins scale with acceptance rate; on predictable text you can 2–3× TPOT.
Scaling past one GPU
When weights don’t fit on one GPU, split the model: tensor parallelism (shard each layer’s matrices across GPUs, all-reduce per layer) and pipeline parallelism (assign layer ranges to GPUs, micro-batch through). vLLM goes from UniProcExecutor (one worker) to MultiProcExecutor (one worker process per rank, rank 0 the driver, coordinated over a shared-memory message queue). From the scheduler’s view nothing changes — it still calls execute_model. Above that, data parallelism replicates whole engines behind a load balancer that scores each engine len(waiting)*4 + len(running) and routes to the lightest. (See the scaling lesson for the general shape.)
The roofline: why batch size is the master knob
Decode step time has two regimes, and knowing which you’re in tells you what to tune:
step_time
│ ┌─── compute-bound: time grows ~linearly with B
│ ┌────┘ (tensor cores saturated)
│ memory-bound ┌────┘
│ (flat: dominated │
│ by weight HBM ───┘ ← B_sat (saturation batch)
│ reads)
└───────────────────────────────────────────► batch size B- Below B_sat, step time is flat — you’re paying to read weights regardless of batch, so more requests are nearly free throughput. Push batch size up.
- Above B_sat, kernels are compute-bound and step time grows with B — now bigger batches raise TPOT. Back off if you have a latency SLO.
Tune gpu_memory_utilization (more blocks), max_num_batched_tokens (prefill chunk budget), and max_num_seqs (batch ceiling) against this curve. Measure goodput — requests served within SLO — not raw tokens/sec, which happily climbs while every user misses their deadline. vLLM’s own tools make the regimes visible: vllm bench latency (small batch, ITL), vllm bench throughput (1000 prompts at QPS=∞), vllm bench serve (Poisson arrivals, full metric set).
Using it (and the knobs that matter)
from vllm import LLM, SamplingParams
llm = LLM(
model="meta-llama/Llama-3.1-8B-Instruct",
gpu_memory_utilization=0.90, # more KV blocks → bigger batches
max_num_seqs=256, # batch ceiling (latency vs throughput)
max_num_batched_tokens=8192, # prefill/chunk token budget per step
enable_prefix_caching=True, # share identical prompt prefixes
# enable_chunked_prefill=True, tensor_parallel_size=2, ...
)
out = llm.generate(
["Explain PagedAttention in one paragraph."],
SamplingParams(temperature=0.7, max_tokens=256),
)
print(out[0].outputs[0].text)For a server: vllm serve meta-llama/Llama-3.1-8B-Instruct --gpu-memory-utilization 0.9 --max-num-seqs 256 exposes an OpenAI-compatible /v1/chat/completions.
Failure modes and their detectors
- KV-cache exhaustion / preemption thrash → track preemption count + queued:running ratio; alert before KV utilization = 100%.
- Head-of-line blocking from long prefills → watch p99 TPOT, not the mean; enable chunked prefill.
- Throughput/latency mismatch → measure goodput under SLO, not tokens/sec.
- Length creep → alert when average sequence length rises while running-batch size falls (the block ceiling is closing in).
- Prefix-cache stampede on a changed system prompt → a one-character prompt edit invalidates every cached block; watch cache hit-rate after any prompt/template change.
The interview summary
Serve LLMs with continuous, iteration-level batching (Orca) so no request waits for its batch to drain, keeping the GPU busy. Manage the KV cache with PagedAttention (vLLM) — fixed blocks addressed through a per-request block table — to eliminate fragmentation, share prefixes copy-on-write, and pack 2–4× more sequences into the same memory. The engine is a step() loop: schedule (decodes first, then chunked prefills, allocate_slots from a free_block_queue), forward, sample, postprocess. Layer on prefix caching, chunked prefill / P-D disaggregation, speculative decoding, and TP/PP for big models. Tune batch size against the roofline (free throughput below B_sat, latency cost above it) and optimize goodput under an SLO. The two metrics that anchor it are TTFT (prefill + queue) and TPOT (decode step), and the resource that quietly caps everything is KV-cache memory — i.e. num_gpu_blocks.