What happens to a running request when the KV cache runs out of free blocks?

## Why running out is normal, not exceptional A paged engine admits requests based on the blocks they need *now*, not on the blocks they will need by the end of generation. That is the whole point — reserving for the worst case is what paging eliminated. The consequence is that admission is a bet: the scheduler may admit sequences that collectively cannot be carried to completion. When they all keep generating, the free list drains, and some sequence's next block allocation fails. This is a designed-for condition with a defined response, not a crash. ## The response: preemption The scheduler selects a victim sequence and reclaims its blocks. Selection policy matters: engines generally preempt the most recently scheduled requests first. That is deliberately unfair, and deliberately correct — under overload, finishing the oldest requests and delaying the newest yields more completed work than slowing everyone uniformly, which is the shape that turns a queue into a crowd of half-finished requests all holding memory. The victim goes back to the front of the waiting queue, so it resumes as soon as blocks free up — usually when some other sequence emits its stop token and releases everything at once. ## Recompute versus swap **Recompute** simply drops the victim's KV blocks. On resume, the engine re-runs prefill over the original prompt *plus every token the sequence had already generated* — those tokens are now part of its input, and their keys and values must exist before decoding can continue. The cost is one prefill of the current length, which is compute-efficient batched work the GPU is good at, and prefix caching can serve much of it from blocks that were never evicted. The cost is paid in GPU time. **Swap** copies the victim's blocks to pinned host memory and copies them back on resume. Nothing is recomputed, but the transfer crosses PCIe in both directions, competing with everything else on that bus, and the host-side buffer is itself a fixed budget that can fill. Swap wins when recomputing would be expensive relative to the transfer — very long sequences — and loses when PCIe is the scarcer resource, which on a modern GPU it usually is. vLLM's V1 engine preempts by recompute. Naming swap as vLLM's mode today is a version error worth avoiding; it belonged to the older V0 engine. The concept still matters because offloading KV state to host or remote memory is an active direction, exposed through connector interfaces rather than as an in-scheduler swap mode. ## What the client experiences Nothing fails. The connection stays open, tokens already streamed stay streamed, and the stream simply pauses until the request is rescheduled. To a user this looks like the model thinking mid-sentence; to a p99 inter-token-latency chart it looks like a cliff. The distinction interviewers are testing is that an LLM server under memory pressure does not shed load the way a stateless service does — it silently redistributes latency and, with recompute, does *more* total work per completed request. Some deployments prefer explicit shedding to that behaviour, rejecting or queueing at the edge when the engine is saturated, so callers get a fast failure they can retry or route elsewhere instead of an unbounded stall. ## Reading and fixing it The signals are a preemption counter that is nonzero at all, cache utilization pinned near its ceiling, and inter-token latency variance far worse than the median. Occasional preemption is healthy — it means admission is aggressive enough to keep the GPU full. Sustained preemption is thrash: the same tokens are prefilled repeatedly, so effective throughput drops while the GPU stays busy, a signature that misleads anyone looking only at utilization. The fixes run in order of bluntness: cap concurrency so fewer sequences are admitted; cap the maximum generation length so a few runaway requests cannot monopolize blocks; free memory for the cache by shrinking other consumers or quantizing the cache; add replicas. Raising concurrency limits to "use the GPU better" while preemptions climb makes throughput worse, and that inversion is the most useful thing to be able to say out loud.