TL;DR: Build an iteration scheduler with bounded admission, explicit KV allocation and per-request output queues. Capacity is constrained by both memory and the measured latency contract. Choose whether to reserve worst-case growth or allow controlled preemption; neither policy is free. A slow client must not block shared execution, and cancellation releases state only after its users finish.
How to approach it
Fix the model, cache layout, request-length distribution and TTFT/token-gap objectives. Draw a request through waiting, admission, prompt processing, decode and cleanup. Compute the page budget before choosing concurrency. Then explain fairness and overload behavior, and validate the resulting scheduler with a traffic replay rather than declaring a p95 from a bandwidth bound.
A strong answer
Two requests can have the same prompt length and very different remaining memory needs. A short answer may finish in the current cache block; a long answer can require many more. The scheduler needs an explicit growth policy, not just a count of requests currently running.
Continuous Batching lets requests enter and leave between iterations. Chunked Prefill divides prompt work into pieces that can share the schedule with decode. A token budget limits how much work the scheduler selects, but its duration still depends on tensor shapes, context length and the other work in that step. Measure those durations before promising a batch size or latency.
Toy reservation policy: 12 pages, four retained positions per page.
A: prompt 5 + maximum output 3 = 8 positions → ceil(8/4) = 2 pages
B: prompt 9 + maximum output 7 = 16 positions → ceil(16/4) = 4 pages
Remaining reservation capacity = 12 − 2 − 4 = 6 pages
C: maximum 25 positions → ceil(25/4) = 7 pages, so it cannot enter yet.
Sanity: A and B reserve 24 positions, although their prompts total only 14.
This policy reserves enough space for the complete prompt and maximum output. It is deliberately conservative; the final sampled token may never be consumed by the model, so its state may not need storage. The reservation is a promise of capacity, not proof that physical pages have already been allocated. Allocate them as needed while honoring the promise, enforce the output limit, and count shared-prefix references correctly. Budget workspace separately so a later allocation cannot consume memory already promised to requests.
For a concrete cache-payload example, BF16 GQA with 80 layers, eight KV heads and head dimension 128 uses 2 × 80 × 8 × 128 × 2 = 327,680 bytes per retained position. A sixteen-position page carries 5 MiB of values before metadata. KV Cache Sizing then connects reservations to actual per-rank capacity. Cache dtype is independent of weight dtype; an FP8 weight checkpoint does not establish FP8 KV.
At each iteration, the scheduler handles completed work and safe releases, considers eligible waiting requests, and selects prefill and decode work within the measured budgets. It executes that work and sends events to bounded queues for each request. Keep request IDs intact through routing and cancellation. Shared pages become reusable only after their references and in-flight GPU users are finished. An independent network writer prevents one blocked client socket from stalling everyone.
Worst-case reservation reduces surprise preemption but can strand capacity when output bounds are loose. Dynamic allocation can improve use of memory, at the cost of swap/recompute policy, victim selection and tail latency. vLLM's optimization guidance describes memory-pressure and scheduler tuning; inspect the deployed version rather than assuming it never preempts. Start with conservative reservation for a strict interactive contract, then relax only when a replay demonstrates worthwhile goodput without unacceptable tails.
Bound the waiting queue and record oldest age. At a stable hypothetical 40 admissions/s and a 0.4-second average wait, Little's law gives an average queue of 16 requests. That average identity is not a worst-case deadline guarantee: variable service times and bursts require age/deadline checks and a measured admission policy. Reject excess work with a retry contract and jitter so clients do not recreate the overload together.
Measure offered requests, joint objective passes, timeouts, preemptions, memory peaks and client token gaps. A memory-service floor such as (weights + cache traffic)/bandwidth helps explain an observed bottleneck; multiplying it by an arbitrary efficiency factor cannot certify p95. Keep a reproducible workload sweep across context lengths and output bounds. Reverse an interactive batching preference for an offline workload only after checking useful completion throughput and fairness; even offline jobs can have deadlines.
What interviewers probe next
- "Can A finishing admit C?" Yes in the toy: releasing A's two reserved pages raises six free to eight, enough for C's seven, assuming cleanup is safe.
- "Does a queue of sixteen ensure 400 ms waiting?" No. It is an average under stated stable rates, not a tail bound.
- "How do we find a cancellation leak?" Inject disconnects in each phase and track acknowledgement, scheduled work and reusable pages separately.
Common mistakes
- Confusing reservation with already-computed cache state.
- Deriving an SLO percentile from a decode bandwidth floor.
- Releasing buffers before kernels or shared references finish.
- Equating a request-count limit with a token/memory budget.
Key takeaways
- The toy admits A and B but leaves only six pages for a seven-page request.
- Growth, shared references and temporary allocations need explicit accounting.
- Choose reservation versus preemption through measured goodput and tail behavior.