Serving is a memory problem: prefill, decode and the KV cache

Part 10 ended with a trained model. Serving it runs into a limit most software engineers never profile: how fast the machine can read memory.

I measured it on my laptop, an Apple M5 Pro, serving Qwen3.5-9B in 4-bit through llama-server, llama.cpp’s HTTP server. I also read how vLLM’s scheduler decides who runs next. Most of what follows is arithmetic you can check against a stopwatch. One part of it isn’t, and that part is the reason to measure your own stack.

Prefill reads the weights once, decode reads them per token

A request runs in two phases. Prefill pushes the whole prompt through the model in one pass, all positions in parallel, and fills the KV cache from Part 6. Decode then produces one token per step. Every step runs the full model again for that single position.

On this machine prefill ran at 1,143 tokens a second on a 1,024-token prompt. Decode ran at 42.6. With the same weights, decode was twenty-seven times slower per token.

The weights explain it. One decode step has to read every weight once: 5.38 GB for this file, not counting the embedding table, since a step reads only one row of it. A read benchmark on the same chip moved 273 GB/s. Divide, and the floor is 19.7 ms per token. The llama.cpp benchmark timed the step at 23.5 ms. Reading the weights at full speed accounts for 84% of it. The same division for Llama-3.1-8B in bf16 on an H100 SXM, 15 GB a token at 3.35 TB/s, gives 4.5 ms before any overhead.

Prefill reads the same 5.38 GB once and amortises it over hundreds of positions. It runs out of arithmetic instead. Operations per byte read has a name, arithmetic intensity. With the embedding table left out on both sides, a decode step for one sequence does about 3 operations per byte. Prefill’s 1,143 tokens a second come to about 18 trillion operations a second. Over 273 GB/s that is about 66 per byte, this chip’s break-even: below it memory sets the pace, above it arithmetic does. Between the two sits a factor of more than twenty.

The KV cache is the other half of memory

Decode also reads the KV cache, the keys and values every earlier position left behind. Its size per token is two tensors, times layers, times key-value heads, times head size, times bytes. For Llama-3.1-8B in bf16 that is 2 × 32 × 8 × 128 × 2: 128 KiB per token, and Part 7’s grouped-query attention already cut it to a quarter. Every factor is in your model’s config.

Qwen3.5 cuts it again. Only 8 of its 32 layers are full attention. The other 24 are linear-attention layers: each carries a recurrent state of fixed size per sequence and keeps no per-token cache. The cache comes to 32 KiB a token, and decode on this laptop barely noticed context: 42.6 tokens a second with an empty cache, 41.3 at 4,096 tokens deep. The fixed state isn’t free either. llama.cpp keeps it in f32, where its main part takes 48 MiB per sequence, as much as 1,536 tokens of cache. A request pays it whether it is ten tokens long or ten thousand.

On a GPU the cache is what caps concurrency. An H100 sold as 80 GB reports about 85.5 GB, and vLLM by default claims 92% of it. After Llama’s 16 GB of weights, at most about 62 GB is left for cache: roughly 116 requests of 4,096 tokens each, fewer once activations take their share. A new request that doesn’t fit waits (scheduler.py:1223). A running one that needs another block evicts someone. Here is the eviction, condensed from vllm/v1/core/sched/scheduler.py:564-810 at v0.31.0:

# There's no "decoding phase" nor "prefill phase" in the scheduler.
token_budget = self.max_num_scheduled_tokens
while True:
    new_blocks = self.kv_cache_manager.allocate_slots(request, num_new_tokens)
    if new_blocks is not None:
        break                                   # the cache had room
    preempted_req = self.running.pop()          # it didn't: evict the newest running request
    self._preempt_request(preempted_req, scheduled_timestamp)

The first line is a comment in the scheduler itself, and it states the design. Each step has a budget of tokens; prefill chunks and decode tokens draw from the same one, so a long prompt is sliced and run alongside other requests’ decodes.

The cache is handed out in blocks of 16 tokens by default. When allocate_slots finds too few free blocks it returns None, and under the default first-come policy the loop takes the most recently admitted running request off the GPU. _preempt_request then frees its blocks and sets num_computed_tokens = 0 (scheduler.py:1560). When the request comes back it recomputes its prompt and what it had generated, minus whatever is still in the prefix cache, which is on by default (config/cache.py:142). Running out of cache costs compute, and the newest request pays it.

Batching is free on paper

That gap, 3 operations per byte against a break-even of 66, is the case for batching. If one step reads all the weights anyway, you’d expect decoding many sequences in that step to cost little more than decoding one, until the arithmetic catches up.

To get the paper number I built a roofline model of this laptop. A step takes the longer of two times, reading its bytes at the measured bandwidth or doing its arithmetic at prefill’s rate, plus a fixed overhead fitted to the one-sequence step. It says 32 sequences at once take 37 ms a step, against 24 ms for one as llama-server timed it. Then I fired 1 to 32 requests at llama-server together and read the step time from the server’s own timings.

The widget opens on a control model, there to check the method: Qwen3-Reranker-0.6B in 8-bit, built on Qwen3-0.6B with ordinary attention in every layer. Up to four sequences the arithmetic is right to within 7%. At eight the measured step is 7.1 ms against 5.1 predicted. Past that the measured line pulls away.

Now pick the 9B. At two sequences the step is already 29.3 ms against 24.8 predicted, 18% over. Thirty-two sequences take 195 ms a step, a few percent of it spent prefilling the last prompts. That is about 5.5 ms for each extra sequence on average, where bandwidth and the recurrent state predict under half a millisecond. The arithmetic promised 864 tokens a second and the server delivered 164. That is under a fifth.

These numbers don’t say which kernel spends those milliseconds; the control can’t narrow it much. It is fifteen times smaller and quantized differently. Fixed overhead is 42% of its one-sequence step. Up to four sequences it would batch cheaply almost whatever its layers were. The control is there for the method, and the method holds: on the same runtime and machine, measured the same way, a model batches as the arithmetic predicts up to four sequences. The excess belongs to this model on this runtime.

The queue is where p99 lives

Everything above fired requests together. Users don’t; they arrive at random. I set llama-server to eight slots, its name for the sequences it decodes side by side, and sent it 60 requests at Poisson intervals: each arrival independent of the last, the usual model for unrelated users. Every request had 256 prompt tokens and 128 out. For each one I timed the first token, the wait a user sees before anything appears.

Start with capacity. Eight clients in a closed loop, each sending its next request as soon as the last one returned, got 87.2 tokens a second out of the server, about 0.68 requests a second. With identical requests a closed loop like that runs almost in lockstep: eight prefills close together, then eight decodes, rarely interrupted, until they all finish and the next prompts arrive at nearly the same moment.

At the two highest rates I tried, about 0.9 and 2 a second, the queue never emptied between the 10th and the 50th completion, and over that stretch the server sustained 85.7 and 85.9 tokens a second. Prefills now land in the middle of other requests’ decodes, the same mixing vLLM’s shared budget does on purpose. The time per output token rose from 76 ms in the closed loop to 89, and the other requests’ prefills account for about 12 ms of those 13. The closed loop paid the same prefills as a pause between rounds, so the cost had only moved, and the closed loop’s 87.2 was within 2% of both.

Sixty arrivals are a short sample. The rate they came at drifted from the one I set: three runs set to 0.5 a second got 0.37, 0.39 and 0.50. The widget orders all eleven runs by the rate they got.

The surprise is below capacity. Drag through the runs. Up to 0.50 requests a second, 64 tokens a second offered and about three quarters of the closed-loop figure, the median first token came in between 0.3 and 0.4 s every time. At 0.65, 95% of it, the median was 1.6 s and p99 9.4 s. At 0.71, just past it, the median was 0.6 s and p99 5.5 s; with one run per rate, the order of those two means little. At 0.94 the median was 12 s, and at 2 it was 28 s. From 0.65 up, a request that has started gets a token every 89 ms or so, whatever the rate. The rest is waiting in the queue, and past capacity the queue grows for as long as arrivals keep coming.

The 99th percentile is noisier still. Three runs at 0.33 to 0.35 a second, all near half load, gave a p99 of 0.4, 5.2 and 0.6 s. Of 60 requests, p99 is the second slowest. How slow that request is depends on how the arrivals happened to bunch, as much as on the model. One short load test can’t pin it down; in production you get all three runs, on different days.

What the ML engineer watches

Four habits, and none of them needs a profiler to start.

Count bytes per token before FLOPs. Weights read per step, divided by measured bandwidth, is your decode floor; the floor over the measured step is your efficiency. Here it was 84%. A quantized file moves the floor in proportion to its size, which is most of why 4-bit weights serve faster.

Budget the cache like memory, because it is. Bytes per token, times context, times concurrent requests, has to fit in what the weights leave over. Check the architecture before you trust a rule of thumb: a hybrid like Qwen3.5 gives up three quarters of the cache for a fixed state per sequence.

Measure your batching curve. Step time against sequences in flight, with your model on your runtime, from 1 up to where it bends. On this laptop the same server matched the arithmetic for one model up to four sequences and charged the other about 5.5 ms a sequence on average.

Load-test with arrivals, and read p99 time to first token. A closed loop of identical clients got capacity within 2% here and says nothing about the wait at 95% of it. Random arrivals show what a user sees, and a few dozen of them give a p99 that moves from run to run, so repeat it.

The floor takes one division and the cache budget one multiplication. That 18% at two sequences showed up only on a stopwatch.