Blog

One Block Short: A KV Cache Livelock That Looks Like a Busy Server

2026-08-16

There is a class of failure where a server does nothing, forever, while its dashboard shows the same numbers as a server that is merely busy for a moment. This is one of those, in vLLM's KV cache accounting, and the gap that causes it is exactly one block wide.

I did not find this bug. I reviewed the pull request that fixed it, asked whether the fix covered a case it did not, and the answer turned out to be a second instance of the same defect. The bug itself, the measurement, and both fixes are @malaiwah's work in vllm-project/vllm#52530.

It is worth writing up anyway, because the shape generalizes: two pieces of code compute the same quantity, disagree by one, and the system responds by quietly doing nothing forever.

The null block

vLLM stores attention keys and values in fixed-size blocks, effectively pages, with each request holding a block table that maps its token positions to physical block IDs. At startup the engine sizes the pool so it can hold at least one request at max_model_len, and refuses to boot otherwise. So far, so correct.

But BlockPool reserves one block as a sentinel:

self.null_block = self.free_block_queue.popleft()
self.null_block.is_null = True

The null block is never handed to a request. A pool of N blocks therefore has N - 1 usable ones, and the startup check was sizing against N.

A pool built at exactly the startup minimum is one block short of a single max_model_len request. Startup passes. A request whose length lands in that gap is admitted, prefilled to about 99% of the pool, and then cannot allocate its final chunk. It is descheduled, and it is never scheduled again, because the pool state that rejected it will never improve. Zero tokens out, the entire prefill discarded. The only observable is a metric saying one request is waiting for capacity, which is exactly what a briefly busy server also looks like.

The case I asked about

The fix added an admission gate bounded on num_tokens + 1: the prompt plus one slot of output. Reviewing it, I noticed that a generate request grows to prompt + max_tokens, and traced what happens to a request that clears admission but grows past the pool:

max_model_len = 8192, max_servable = 8000
prompt = 7000, max_tokens = 1000
  frontend       7000 + 1000 = 8000 <= 8192   accepted
  admission      7000 +    1 = 7001 <= 8000   admitted
  at token 8000  needs a block the pool does not have

I had not reproduced it and did not know whether that request would hang or merely stall, so I asked it as a scoping question rather than reporting a bug.

The author built a CPU-only harness and reproduced it:

pool = 69 blocks, max_servable = 1008
request: prompt = 1000, max_tokens = 24

step 12  computed=1008  out=9  free=1   RUNNING
step 13  computed=   0  out=9  free=68  PREEMPTED  preempt=1
step 14 ... step 3999   sched=0  out=9  free=68  PREEMPTED  preempt=1

3,987 of 4,000 steps produced nothing, with the whole pool idle. Livelock, not slow progress.

The part I would not have guessed: the preemption counter increments once and stops. Preemption discards the request's KV and re-prefills it from scratch, but at 1,009 tokens the request is now too long for its own re-prefill. It collapses straight into the original prefill bug and inherits its silence. One failure mode turns out to be the other one's terminal state.

My proposed fix was wrong

I suggested bounding admission on num_tokens + max_tokens. It catches the bad request. It also rejects good ones: a control in the same run showed prompt = 1000, max_tokens = 8 completing cleanly on that same 69-block pool. Callers routinely pass max_tokens far above what the model will actually emit, so that bound trades a rare livelock for frequent false rejections. Rejecting work the system could have done is not obviously better than hanging on work it can't.

The author's fix moves the bound to the point of exhaustion instead, and is one line:

-  stopped = check_stop(request, self.max_model_len)
+  stopped = check_stop(request, self.max_servable_num_tokens)

The request stops at the pool's real ceiling and returns everything it produced, with finish_reason: length. One bound, three call sites, and no request rejected that could have finished.

What generalizes

Reserved resources leak out of capacity math. The null block is a one-line sentinel, and a correct one. It was not reflected in a sizing calculation written somewhere else, possibly by someone else, possibly years apart. Every reservation is a standing invitation for this bug.

Two computations of one quantity will drift. The startup check and the allocator each had their own notion of how many blocks the pool holds, and they disagreed by one. The durable fix was not correcting the arithmetic; it was collapsing the two computations into one function, so there is nothing left to drift.

A metric that fires once looks like health. One preemption event plus one waiting request is indistinguishable from a momentarily full server. If a permanent failure and a transient condition produce the same signal, the alarm is decorative. The difference has to be made observable, or it gets discovered by a user with a stopwatch.

A scoping question outperforms a bug report you can't back. I could not have credibly filed "generate requests livelock past the servable ceiling": I hadn't run it, and I might have been wrong about the mechanics. "Does the new bound cover the growth case?" cost one review comment, and turned out to have a harness-verified livelock behind it. In a codebase you are still learning, the well-aimed question is a real contribution.

The gap is exactly one block wide, and zero as soon as the pool has a spare. Narrow, but total and silent inside that radius, and it appears precisely on pools sized at the minimum. Which is what you get when you do the natural thing and raise max_model_len until vLLM stops complaining.

Thanks to @malaiwah for the find, the harness, and the patient writeups.