This section is about how a server shares one GPU among many requests. Before every step it decides which requests run together, and it finds room in GPU memory for the keys and values each request has stored. Both decisions set how many requests share the GPU at once, the batch size, and the batch size is what makes serving cheap. Done carelessly, most of the GPU's time goes to batch rows that produce nothing, and most of its memory to space reserved for tokens that are never written.

Here is why the batch matters so much, restated from §20.1. A model answers a request in two phases. Prefill runs the whole prompt through the model in one pass. It stores the keys and values that attention computed for every prompt token, the KV cache of §6.5, so that later tokens can attend to them without recomputing them. Decode then runs one forward pass per new token, a decode step, which produces one token for every sequence in the batch. Each decode step reads every weight of the model from GPU memory, and that read takes the same time whether the step serves one sequence or a hundred. So, up to a point, one more sequence in a step costs only the time to read its own cache, and it yields one more token.

That bargain is easy to lose. Thirty-two chat requests arrive together and are served as one batch, which runs decode steps until all of them are done. Thirty-one want short answers of 50 tokens, and one wants a 2,000-token essay. After 50 steps the short answers are finished. The batch then runs 1,950 more steps for the essay, and in each of them 31 of its 32 rows produce nothing. Of the $32\times 2{,}000 = 64{,}000$ row-steps the GPU ran, only $2{,}000 + 31\times 50 = 3{,}550$ made a token, 5.5%. Meanwhile the next hundred users wait in the queue.

This section repairs that waste in three steps, each borrowed from operating systems. First, choose the batch again before every step, so a finished request's row is refilled at once. Second, store each cache in small fixed-size pages handed out as the sequence grows, so that memory holds tokens and not reservations. Third, let requests that begin with the same tokens share the pages that hold them, so a popular system prompt is computed and stored once. Then we turn to prompts. A long prefill freezes every other user's stream unless it is cut into chunks, and the two phases can even run on separate GPUs, with the cache shipped between them. These mechanisms are the core of every modern serving engine, such as vLLM, SGLang, and TensorRT-LLM, and inference interviews ask candidates to build each of them.

A few symbols run through the section. $\pi$ is a GPU's peak arithmetic rate in FLOP/s and $\beta$ its memory bandwidth in bytes per second, as in the roofline of §11.2. $B$ is the number of sequences in a decode step and $N$ the number of parameters. $m_{\text{KV}}$ is the number of bytes of KV cache per token. A model with $L$ layers and $n_{kv}$ key-value heads of width $d_k$, storing $s_{\text{KV}}$ bytes per number, keeps one key and one value per head per layer, so $m_{\text{KV}} = 2Ln_{kv}d_ks_{\text{KV}}$. Llama 3.1 8B has 32 layers and 8 key-value heads of width 128. In 16-bit numbers, 2 bytes each, that is $2\times 32\times 8\times 128\times 2 = 131{,}072$ bytes, 128 KiB per token.

Why batching by request wastes the GPU

§20.1 built a model of how long one decode step takes. In its short form, a step of $B$ sequences takes

where $t_W$ is the time to read the weights, $t_K$ the time to read one sequence's cache, $t_F$ the time for one sequence's arithmetic, and $t_0$ a fixed overhead per step. In plain words, a step lasts as long as the slower of two jobs, reading memory or doing arithmetic, plus the overhead. For batches below the point where the two jobs take equally long, the knee of §20.1, reading is slower and the step costs about $t_W + Bt_K$.

Call each row of the batch a slot, and one slot during one step a slot-step. A slot held by a finished request produces nothing, yet the step still pays the full weight read. A live sequence in that slot would have added only $t_K$, a small fraction of $t_W$, and made one more token. So the fraction of slot-steps that make tokens is, to first order, the fraction of its possible throughput that a server delivers.

How much does static batching waste on ordinary traffic? It depends on how unequal the output lengths are. A standard rough model takes the lengths to be independent and exponentially distributed. A length is exponential with mean $\mathbb{E}[\ell]$ when the chance that it exceeds $x$ steps is $e^{-x/\mathbb{E}[\ell]}$. Short answers are then common, and long ones rare but not negligible. With a mean of 200 steps, about 37% of answers run past 200 and about 5% past 600. The model gives an exact answer.

The first formula just counts. The long-run fraction is a ratio of expectations because, over many batches, the total useful work and the total slot-steps both grow like the number of batches times their means, by the law of large numbers. The real work is the expected maximum, which the derivation finds.

In plain words, a static batch is as slow as its slowest member. With random lengths the slowest of 32 runs about four times the average, so three quarters of the slot-steps are idle. Doubling the batch adds about $\ln 2 \approx 0.69$ to $H_B$, so utilization keeps falling as static batches grow, slowly but without end. Exponential lengths are a model, not a law. The exact number $1/H_B$ depends on them, but the waste does not, because every slot is held until the longest member ends. The opening example, one essay among 31 short answers, wasted 94.5%.

The cell checks the theorem by simulation, with 4,000 batches at each size.

An interviewer who asks why a server should not batch requests the simple way wants this number, $1/H_B$, and then the fix.

Scheduling one step at a time

The fix is to stop treating a batch as a unit. A Transformer generates one token per sequence per forward pass, and nothing forces the set of sequences to stay the same from one pass to the next. So the server can choose the batch again before every pass. Yu et al. (2022) built the Orca serving system on exactly this observation.

Selective batching is what lets the step-time model apply to a mixed batch. The weight matrices see one tall matrix of tokens, so the weights are still read once per step for everyone. The per-request attention is what the kernels of §12.4 compute, which handle many sequences of different lengths in one launch. Here is the difference between the two policies on a case small enough to do by hand.

C finished six steps earlier in the example, and that was no accident. Under continuous batching nobody ever waits longer than under static batching, whatever the traffic.

How much does it buy on realistic traffic? The cell serves 1,000 requests on 32 slots under both policies. Output lengths are exponential with a mean of 200 steps, and requests arrive at random. Rather than step through time, it uses a shortcut. Continuous batching in arrival order is list scheduling, in which each request takes whichever slot frees first, and a heap of the times at which slots free up finds that slot. Static batching jumps from one batch to the next.

At a light load of 0.03 arrivals per step, both policies keep up, with the slots busy 19% of the time either way. Yet static batching makes the average request wait about 500 steps for the current batch to drain, and one in a hundred waits about 2,000. Continuous batching admits everyone at once. At 0.12 arrivals per step the offered work is $0.12\times 200 \approx 24$ tokens per step, three quarters of the 32 slots. Continuous batching still admits nearly everyone at once. Static batching cannot keep up at all. It saturates at about 24% of its slots, the $1/H_{32}$ of the theorem, so its queue grows for as long as requests arrive and the mean wait reaches about 9,000 steps.

Every production engine now schedules this way. Two follow-ups come up in interviews. Why does continuous batching cut the time to first token (TTFT, the wait from arrival to the first output token), and not only raise throughput? Because a new request joins the running batch at the next step instead of waiting for the batch to drain. And how can one forward pass serve requests of different lengths? Through selective batching.

def simulate_batching(arrivals, outputs, max_batch, policy):
    # Placeholder: runs every request alone, one after another.
    finish, t = [], 0
    for ell in outputs:
        t += ell
        finish.append(t)
    return {"finish": finish, "total_steps": t, "utilization": 1.0}

The widget runs this section's three scheduling policies on one H100 serving Llama 3.1 8B, with every step timed by the step-time model of §20.1. Prefill runs at 50% of peak, and every step pays 0.3 ms of overhead. The 48 requests arrive at random, 6 per second, into 8 batch slots, one slot per row. Their prompt and answer lengths are drawn from exponential distributions with means of 1,500 and 150 tokens. The strip above the slots counts the requests that have arrived and wait for a slot. Press Play to watch the slots fill, then switch from static batches to continuous batching and watch the waiting strip, the slots, and the TTFT. The third policy, chunked prefill, comes later in the section.

Continuous batching fills the slots and cuts TTFT, but the widget also shows its price. Each time a slot frees, the engine computes the newcomer's whole prompt in one step, and every running stream waits through that step. That pause is called a stall. For a long prompt it is a gap of a few hundred milliseconds in everyone's text. The first versions of vLLM ran such a step for the prompt alone. Orca ran it beside the decodes, which still made every decode wait for the whole prompt. Chunked prefill removes the stall later in the section. First, though, there is a second limit on the batch, and in practice it is the one that binds.

Why the cache needs pages

A slot also needs memory. Every running sequence keeps its KV cache in GPU memory, $m_{\text{KV}}$ bytes per token, so the number of sequences that fit is the free memory divided by what each one holds (§20.1). The hard part is knowing how much each one will hold. A sequence's length is unknown when it is admitted, since its answer may stop after 5 tokens or after 4,000.

Before 2023, serving systems stored each sequence's cache in one contiguous buffer, the layout that §6.5 built. The buffer was sized for the longest the sequence could become, its prompt plus the largest allowed number of new tokens, or even the model's whole context. Kwon et al. (2023) named three kinds of memory this wastes.

• Reserved slots hold nothing yet. They are kept for tokens the sequence may write later.
• Internal fragmentation is reserved space that is never used, because the sequence stopped early.
• External fragmentation is the gaps between buffers that are too small to hold a new one.

When they profiled such systems, only 20.4% to 38.2% of the KV memory held actual tokens. The fix they borrowed is the one operating systems use for programs. A program sees one long range of memory addresses, but the operating system backs it with fixed-size pages of physical memory that can sit anywhere. A page table records where each page really is, and a page is handed out only when the program first writes to it.

The attention kernel reads each sequence's keys and values through its block table, one block at a time. That is the gather that §12.4 previewed and Exercise 12.4e implemented. Each block is still one contiguous read, so the kernel loses little. vLLM's first paged kernel took 20% to 26% longer than a contiguous one, and only in attention, a small price for the memory it saved. Everything above the kernel, the allocator, sharing, and scheduling, is what we build here. First, how much memory does paging waste?

In plain words, paging bounds each sequence's waste by one block, whatever its length, instead of by the gap between its length and the worst case. With 16-token blocks a sequence wastes 7.5 token slots on average, under 1% of a 1,000-token chat.

How many more sequences does that fit on a real GPU? The cell serves Llama 3.1 8B in 16-bit weights on an H100, with vLLM's default of using 90% of the GPU's memory. It draws 5,000 sequences caught in the middle of decoding, with prompts of mean 1,000 tokens and outputs of mean 250 and at most 1,024. It packs them until memory runs out under four policies, and times one decode step of each batch with the step-time model.

So paging buys throughput by fitting more sequences, and it costs a little latency per token. An interviewer will ask you to size this, the batch that fits with and without paging, from the model's $m_{\text{KV}}$ and the free memory.

Choosing the block size

Why 16 tokens and not 1 or 256? Five things pull on the block size $n_{\text{blk}}$.

• Fragmentation grows with it, $(n_{\text{blk}} - 1)/2$ wasted slots per sequence on average, which matters for short sequences.
• Kernel efficiency falls when blocks are tiny. Each block is one contiguous read and one block-table lookup, so very small blocks mean short reads and many lookups. Kwon et al. found block sizes from 16 to 128 best on a trace of long ShareGPT conversations, 16 or 32 best on the short requests of the Alpaca trace, and made 16 the default.
• Prefix sharing happens in whole blocks, as we will see, so a shared prefix loses up to $n_{\text{blk}} - 1$ tokens at its end. SGLang's design uses one-token pages so that it can share prefixes to the exact token.
• Swapping blocks to CPU memory moves one block per transfer, and small transfers waste the bandwidth of PCIe, the link between the GPU and the CPU. vLLM measured a large swap overhead at small block sizes.
• Table size is $\lceil T/n_{\text{blk}}\rceil$ entries per sequence. At 128K tokens and 16-token blocks that is 8,192 entries, 32 KB at 4 bytes each, against 16 GiB of cache for Llama 3.1 8B. So it rarely matters.

Sharing blocks, and copying on write

Paging also makes sharing cheap, because two block tables can name the same physical block. Two workloads gain at once. Parallel sampling draws several answers to one prompt, as in best-of-$n$ selection or in reinforcement learning methods such as GRPO, which score a group of answers to each prompt. Beam search keeps the few most likely partial answers and extends each of them (§6.4). In both, many sequences share a long history. Here is the allocator at work on a tiny case.

The longer the shared prompt and the more samples, the bigger the saving. On OPT-13B serving the Alpaca trace, Kwon et al. (2023) measured 6.1% to 9.8% less KV memory with parallel sampling and 37.6% to 55.2% less with beam search. On ShareGPT the savings were 16.2% to 30.5% and 44.3% to 66.3%. Beam search gains most because surviving beams share most of their history. The gather of parent caches that beam search needed after every step in §6.5 becomes an update of block tables and counts, with at most one block copied per beam per step.

When memory runs out

Paging admits sequences against the memory they hold now, not the memory they may need later. That is the source of its efficiency, and of a new failure. When a running sequence fills its last block and the free list is empty, something must give. vLLM preempts a sequence, the one that arrived last, so that earlier requests are served first. It frees all of that sequence's blocks at once. Freeing only some would not help, because every step reads a sequence's whole cache, so a sequence with part of its cache missing cannot run. Requests that share blocks, such as the beams of one beam search, are preempted together. A preempted sequence comes back in one of two ways.

Swap. Copy its blocks to CPU memory over PCIe, and copy them back when there is room. It costs two transfers of its cache.

Recompute. Drop the blocks. When there is room, prefill the prompt and the tokens generated so far again, as one longer prompt. It costs a prefill.

Which is cheaper? Take a sequence of $T$ cached tokens on a replica of $n_{\text{gpu}}$ GPUs, each moving its share of the cache over a PCIe link of effective bandwidth $b_{\text{pcie}}$. The prefill time of §20.1 gives

where $N_{\text{act}}$ is the number of parameters multiplied per token ($N$ for a dense model), $d_{\text{attn}}$ is the total width of the attention heads, and MFU (model FLOP utilization) is the fraction of peak arithmetic that prefill achieves, often about half. Drop the attention term, which only makes recomputing dearer. Then swapping is cheaper exactly when

In plain words, swapping wins when the link moves one token's cache out and back faster than the GPU can recompute that token. The length $T$ cancels, so the answer depends only on the model and the hardware, and the quadratic attention term tips long sequences further toward swapping.

For grouped-query models on H100s the arithmetic favors swapping. Grouped-query attention lets several query heads share one key-value head, so the cache per token is several times smaller than the model's width suggests (§12.5). The break-even is 8.1 GB/s per GPU for Llama 3.1 8B and 2.3 GB/s for the 70B on eight GPUs, well below what a PCIe 5.0 link moves. At 25 GB/s effective, a 32,000-token sequence of the 70B swaps in 105 ms and takes 1.5 s to recompute.

Yet vLLM's current engine, V1, recomputes by default, and its documentation says recomputation has lower overhead in its architecture. The bandwidth arithmetic leaves out three things.

• Recomputing is just another prefill, chunked and batched with everything else through the same scheduler. A swap needs CPU memory, a second block table, and copies that must finish before the request can run.
• Small blocks make swap transfers inefficient. Kwon et al. found recomputation at most about 20% slower than swapping at any block size, and the two comparable for blocks of 16 to 64 tokens.
• With prefix caching, which comes next, a preempted request's full blocks go back to the free list still labeled with their contents. If nobody reuses them before the request resumes, most of its recompute is a cache hit.

The price of recomputing is GPU time that the other requests in the batch would have used, so frequent preemption shows up as a throughput loss for everyone. In an interview, give the break-even, then say why an engine may still recompute.

Now build the allocator. It is a real interview question at companies that build inference engines, and it is the core of vLLM's memory manager.

class BlockAllocator:
    def __init__(self, n_blocks, block_size):
        self.n_blocks, self.block_size = n_blocks, block_size
        self.copies = []

    def allocate(self, seq, n_tokens):
        raise NotImplementedError

The widget shows the same allocator at work on a toy memory of 1,024 token slots. A request arrives every 3 to 10 steps, and every running sequence writes one token per step. Each prompt is a 64-token system prompt plus a question of 8 to 71 tokens, and each answer runs 16 to 160 tokens. The contiguous allocator reserves room for the longest answer, 160 tokens, and the paged one uses blocks of 16. When the paged pool runs out, the newest request is preempted and recomputed later. The widget opens at step 160, reserving the maximum for one sample per request. Before you switch to paging, predict how many sequences it runs at the same step, and how many requests it has finished. Then ask for 4 samples per request and press Play with each of the three allocators.

At step 160 the reserving allocator runs 3 sequences and has finished 3 requests, while paging runs 6 and has finished 9. Most of each reserved run is empty, so paging fits about twice as many sequences in the same memory. With four samples per request, reserving runs one request at a time, because every sample reserves room for the longest answer before writing a single token. A request whose four runs would exceed the whole memory is turned away. Paging without sharing fits about one request too, since each sample stores its own copy of the prompt, but it turns nobody away. Sharing stores each prompt once for all four samples and runs two or three requests at a time. By step 320 the three allocators have finished 2, 4, and 7 requests. The batch, and with it the throughput, is set by how memory is handed out.

Reusing the cache across requests

Paging lets the samples of one request share a prompt. Can different requests share one? Recall a fact from §6.5. Under a causal mask, the keys and values of token $i$ in every layer depend only on tokens $0$ to $i$. So two requests that begin with the same $T_{\text{hit}}$ tokens, for the same model and adapter, have identical caches for those tokens. A server that keeps them can skip that part of the prefill, which is called prefix caching. §7.7 used it as a preview. Here is what it saves, and how servers find the shared part.

Take a prompt of $T_{\text{in}} = T_{\text{hit}} + T_{\text{new}}$ tokens whose first $T_{\text{hit}}$ are cached. It must still run its $T_{\text{new}}$ new tokens through every layer, and each new token at position $j$ attends to all $j$ tokens before it, cached or not. Summing over the new positions, as §20.1 did for a whole prompt,

In plain words, the weight FLOPs shrink to the new tokens alone, and the attention FLOPs lose the triangle that the cached tokens would have computed among themselves. The new tokens' attention to the cached prefix is still paid, so a hit on a long prefix saves a little less than its share of the tokens. A hit saves memory too, since the shared blocks are stored once however many requests use them.

How to order a prompt so that it hits, and what caching does to the bill of an agent that resends its history every turn, is the subject of prompt caching for agents. Here we build the mechanism.

Chained block hashes

vLLM finds shared prefixes with one hash per block. A hash maps any input to a short fixed-size label, so that equal inputs get equal labels and different inputs almost surely get different ones. The design is short, and every detail of it matters.

Why chain the hashes? Because a block's keys and values depend on every token before it, not only on its own tokens. The same 16 tokens after two different system prompts have different caches. A hash of the block's own tokens would produce false hits that silently corrupt the answer. Feeding $h_{j-1}$ into $h_j$ makes each hash commit to the entire prefix, while still costing one block of work. The extra keys exist for the same reason. The cached values of an image placeholder depend on the image, and those of an adapted model depend on the adapter.

Why only full blocks? A partly filled block is still being written by its owner, so its hash would change with every token. Caching it would also let the next request share a block its owner is about to write into, forcing a copy-on-write on every hit. So a prompt always recomputes its last partial block, and a hit can lose up to $n_{\text{blk}} - 1$ tokens. Even a prompt that hits in full recomputes its last token, because the first output token is sampled from that token's logits, which the cache does not store. vLLM caps every hit one token short of the prompt, and hits come in whole blocks, so a prompt that fills its last block exactly recomputes that whole block. And since a hash collision would serve one user's cache to another, vLLM made SHA-256, a cryptographic hash, its default block hash in version 0.11.

import hashlib
from collections import OrderedDict

def block_hashes(tokens, block_size, extra=()):
    # Placeholder: hashes each block on its own, which gives false hits.
    return [hashlib.sha256(repr(tuple(tokens[j:j + block_size])).encode()).hexdigest()
            for j in range(0, len(tokens), block_size)]

The exercise's test of a hit that stops at the first missing block shows why vLLM releases a request's blocks tail first. Under plain LRU, the first block of a prefix is the oldest and is evicted first. That makes every later block of the prefix unreachable, even though it is still cached, because a lookup stops at the first miss. Evicting from the tail keeps the shared heads alive the longest.

How high can hit rates get? The cell builds a synthetic chat trace of 120 conversations, interleaved at random. Each has one of three system prompts (600 to 2,000 tokens) and one to six turns. Each turn resends the system prompt and the whole history plus a new user message, and each answer is cached as it is generated. The cell counts hits with chained 16-token blocks under several cache sizes.

With an unlimited cache, more than nine in ten prompt tokens are hits, because every turn of a conversation is the previous turn plus a little. Shrink the cache and the hit rate falls, since interleaved conversations evict each other's histories. Real traffic is noisier, but the rates that services report are high too, 56.3% of all input tokens at DeepSeek, and 52.4% and 74.1% for two models that SGLang served in the Chatbot Arena.

Radix trees

Hashes find a shared prefix one block at a time. A tree can find it to the token, and it can also tell the scheduler which requests to run together. Zheng et al. (2024) built SGLang's prefix cache, RadixAttention, around one.

Evicting leaves first is the tree's version of the tail-first release of chained hashes. A long shared prefix sits near the root, so it survives as long as any of its descendants are in use or recent. The tree also makes a scheduling idea natural. Suppose the queue holds requests that share prefixes. Serving first the ones that share the longest cached prefix keeps reusing what is in memory. Serving them in arrival order may evict a prefix just before the next request needs it. SGLang proved that this ordering is optimal in a clean case.

Online, with requests arriving over time, SGLang approximates this order by sorting the waiting queue by matched prefix length. It reported reaching 96% of the optimal hit rate on average across its benchmarks, whose hit rates ranged from 50% to 99%. Greedy cache-aware ordering can starve a request that shares nothing, so a production scheduler bounds how long anyone waits. The same idea scales out. A router that sends each request to the replica holding its prefix (§20.7) turns a fleet's caches into one, and Mooncake, the serving platform behind Moonshot AI's Kimi assistant, schedules the whole service around where the reusable cache already is (Qin et al. 2024).

class RadixCache:
    def __init__(self):
        self.seqs = []                      # placeholder: a flat list, no sharing and no eviction

    def insert(self, tokens):
        self.seqs.append(list(tokens))
        return 0

The two designs make different things easy.

Who may share a cache

A shared cache leaks information. A prompt whose prefix is cached prefills faster, so its time to first token is measurably shorter. If two tenants share a cache, one can learn from its own response times whether a prefix it sends is cached, which tells it that someone else sent that prefix recently. This is a timing side channel. Song et al. (2024) showed that it can recover cached system prompts and other users' prompts by extending a guess one token at a time, in a controlled setting and in black-box tests of online services. Zheng et al. (2024) reported a similar attack, InputSnatch.

The defenses limit who may share, not the cache itself. Providers scope caches to one organization or trust group. vLLM lets each request carry a cache_salt, mixed into the hash of its first block, so only requests that know the same salt can hit each other's blocks. Its default hash is cryptographic, so collisions cannot be engineered. Sharing a cache across tenants is safe only for content that is public anyway, such as a provider's own published system prompt.

Mixing prefill and decode in one step

Go back to the stall in the scheduling widget at the start of the section. Under continuous batching, each newly admitted request has its whole prompt computed in one step, and every running stream waits through that step. How long is it? For Llama 3.1 8B on an H100, an 8,000-token prompt costs about $2\times 8.03\times10^9\times 8{,}000 \approx 1.3\times10^{14}$ FLOPs in its weights, plus its attention, about 290 ms at 50% MFU. Every user watching a stream sees the text freeze for a third of a second, and a burst of long prompts freezes it for seconds. Agrawal et al. (2024) measured such generation stalls lasting several seconds in vLLM serving Yi-34B on two A100s. They also found that adding a whole prefill to a decode batch raised the time between tokens up to 28.3 times. The mean time per output token (TPOT) can look fine while the inter-token latency (ITL, each gap between two tokens of a stream) is terrible at p99, the case §20.1 warned about.

The cure uses the slack that §20.1 found in every decode step. A memory-bound step reads the weights anyway, so extra tokens in the same step cost nothing until their arithmetic catches up with the reading. Prefill tokens are just more rows of the batch. So a prompt can be split into chunks, each computed in one step alongside everyone's decode token. A chunk of new tokens attends to the whole cache built so far and causally to itself. Each new token sees every cached token and the new tokens before it, the bottom-right-aligned causal mask of §4.4. That computation is the one §6.5 built. Here we schedule it.

This is the stall-free batching of Sarathi-Serve (Agrawal et al. 2024), built on the chunked prefills of their earlier Sarathi (Agrawal et al. 2023). It is vLLM V1's default policy, where the budget is the setting max_num_batched_tokens. How large can the budget be before the decodes slow down? Use the constants of §20.1. The weight read takes $t_W = M_W/(n_{\text{gpu}}\beta)$, where $M_W$ is the bytes of weights. One sequence's cache read takes $t_K = \bar Tm_{\text{KV}}/(n_{\text{gpu}}\beta)$ at mean context $\bar T$. And write $t_N = 2N_{\text{act}}/(n_{\text{gpu}}\pi)$ for the weight arithmetic of one token, which is the $t_F$ of §20.1 without its attention term.

Proof. The step is memory-bound, and costs $t_W + Bt_K$ like the decode step alone, as long as $(B + C)t_N \le t_W + Bt_K$. Divide by $t_N$ and subtract $B$. With $t_K = 0$, $t_W/t_N = (s_WN/\beta)/(2N/\pi) = s_W\pi/(2\beta) = B^\star$. ∎

In plain words, a decode step has room for about as many extra tokens as it takes to make the step compute-bound, a few hundred on an H100. Long contexts make that room bigger, because the cache reads lengthen the step without adding arithmetic. Beyond $C^\star$, each extra prefill token adds $t_N$ (more, at real MFU), and every decode in the step slows down with it.

Three trade-offs set the budget in practice.

• A larger budget lengthens every step that carries a chunk, so TPOT and ITL grow. Sarathi-Serve picks the largest budget that meets the ITL target, 512 tokens for strict targets and 2,048 for relaxed ones in its experiments.
• A smaller budget stretches each prompt over more steps, $\lceil T_{\text{in}}/(n_{\text{budget}} - B)\rceil$ of them when it is the only prompt being prefilled, so TTFT grows.
• Chunking is not quite free in total. A small chunk gives the linear layers too few tokens to be compute-bound on their own, so a prompt cut into small pieces runs less efficiently than in one pass. Each chunk also rereads the cache of the chunks before it, which the deeper box counts.

The cell puts numbers on all of this for Llama 3.1 8B on one H100, using the roofline with prefill at peak.

So the budget is the one knob that trades TTFT against ITL, and an interviewer will ask how you would pick it. Profile the step time against the number of tokens on the real GPU, and take the largest budget that meets the ITL target.

def chunked_prefill_schedule(requests, budget):
    # Placeholder: prefill each whole prompt in its own step, pausing every decode (the stall).
    steps, first, finish, t = [], [], [], 0
    for i, (a, p, o) in enumerate(requests):
        t = max(t, a)
        steps.append({"decode": [], "prefill": [(i, p)]})
        first.append(t)
        finish.append(t + o - 1)

Now go back to the scheduling widget at the start of the section and pick the third policy.

At the default budget of 512, the longest gap falls from about 300 ms under continuous batching to 20 ms, and TTFT at p99 falls too, from 0.87 s to 0.54 s. No stream pauses, because a prompt chunk only lengthens a step that the decodes run anyway. At a budget of 64 the gaps stay at 6 ms, but prompts enter so slowly that TTFT at p99 grows to 1.9 s. At 4,096 every step that carries a chunk runs long, and the longest gap grows back to 142 ms. These are the two ends of the trade that the worked example on choosing a budget priced.

The verification tokens of speculative decoding fit the same scheme. A sequence that verifies $\gamma$ drafted tokens contributes $\gamma + 1$ tokens to the step instead of one. So a scheduler that counts tokens per request per step, rather than requests, handles prefill chunks, decodes, and verification with one mechanism. That is how vLLM V1 is organized (§20.7).

Separating prefill from decode

Chunked prefill puts both phases in one step and keeps their interference small, but it cannot make it zero. Every chunk still lengthens the step of the decodes beside it. The budget is a compromise between TTFT and ITL that must be retuned when the traffic changes. And both phases are forced onto the same GPUs with the same parallel layout, although prefill wants many GPUs per prompt for a short TTFT and decode wants large batches. Zhong et al. (2024) and Patel et al. (2024) proposed the opposite design at about the same time.

How many GPUs should each pool get, and how much can disaggregation gain? A clean model answers both, and its answer is surprising.

Proof. A request needs both phases, so the pool's rate is the smaller of the two pools' rates. Let $r = \min(n_pr_p, n_dr_d)$. Then $n_p \ge r/r_p$ and $n_d \ge r/r_d$, so $r/(n_p + n_d) \le r/(r/r_p + r/r_d) = 1/(1/r_p + 1/r_d)$, with equality when both pools are exactly saturated, $n_pr_p = n_dr_d$. A time-sharing GPU that serves $r$ requests per second spends a fraction $r/r_p$ of its time on prefill and $r/r_d$ on decode. These fractions add up to at most 1, which gives the same bound. Overlapping lets the two fractions share the same seconds, so their sum may exceed 1. ∎

In plain words, splitting the phases does not create capacity. A perfect collocated server would match or beat a perfectly balanced disaggregated one. Everything disaggregation gains comes from what the clean model left out. It removes the interference (stalls, compromise budgets, chunking overheads), and it lets each phase have its own parallelism and hardware. Against that it pays for moving the cache and for rounding pool sizes to whole GPUs. Whether it pays is an empirical question about those terms, and Exercise 20.6f turns it into a calculation.

The cost of moving the cache

Disaggregation's new cost is the transfer. A prompt of $T_{\text{in}}$ tokens hands the decode pool $T_{\text{in}}m_{\text{KV}}$ bytes. Over a link of bandwidth $b_{\text{link}}$, available to the whole replica, that takes $t_x = T_{\text{in}}m_{\text{KV}}/b_{\text{link}}$, and it lands on TTFT unless it overlaps with the prefill. Divide by the prefill time, $T_{\text{in}}\cdot 2N_{\text{act}}/(n_{\text{gpu}}\pi\cdot\text{MFU})$ ignoring attention, and the prompt length cancels,

In plain words, the transfer is a fixed fraction of the prefill, set by how many bytes of cache a token has against how many FLOPs it costs. Large models with small caches transfer cheaply. Long prompts change nothing, since both sides grow with $T_{\text{in}}$, and the attention term only helps. The cell checks DistServe's numbers and prices the transfer for Llama 3.1 70B. The link is a NIC, the network interface card that connects a server to others, at 400 Gb/s, which is 50 GB/s.

For Llama 3.1 70B on eight H100s, the transfer costs 18% of the prefill over a single 400 Gb/s NIC, and 2.3% with one such NIC per GPU, as DGX H100 servers have. A 32,768-token prompt carries 10.7 GB of cache, 215 ms over one NIC against 1.53 s of prefill. Mooncake and vLLM's connectors stream the cache layer by layer or block by block while the prefill is still running, which hides most of even that. The transfer becomes the problem when the network between the pools is slow or misconfigured.

So the transfer is a cost to plan for, paid in TTFT and in network hardware, and it buys a decode stream that long prompts can no longer interrupt. The largest providers have judged that trade worth making.

Splitting by phase separates work that is compute-bound from work that is memory-bound. A mixture of experts invites a second cut of the same kind, between the attention and the experts inside every layer.

import math

def disagg_plan(rate, T_in, T_out, cfg, hw, link_bw, ttft_slo, tpot_slo, mfu=0.5, max_util=0.8, c_half=256):
    raise NotImplementedError

Tiers of KV storage

A GPU's memory (HBM, its high-bandwidth memory) is a small, fast cache for a much larger body of reusable KV. Below it sits the CPU memory of the same server, hundreds of gigabytes reached at tens of gigabytes per second over PCIe. Then come local SSDs, terabytes at a few gigabytes per second per drive, and shared storage or other servers' memory over the network. An evicted prefix that lands in a lower tier can be reloaded instead of recomputed. When is that worth it? A prompt of $T$ cached tokens reloads in $Tm_{\text{KV}}/b_{\text{tier}}$ and recomputes in about $T\cdot 2N_{\text{act}}/(n_{\text{gpu}}\pi\cdot\text{MFU})$, so reloading wins when

where $\Theta_{\text{prefill}}$ is the replica's prefill throughput in tokens per second. In plain words, the tier must deliver cached tokens faster than the GPUs can compute new ones. This is the swap break-even from the preemption subsection, with one transfer instead of two.

Where it breaks

Preemption thrash. Under sustained overload, paged admission keeps letting in requests that later run out of blocks, get preempted, are readmitted, and are preempted again, each time paying a recompute. Throughput collapses while utilization looks high. Engines keep a reserve of free blocks at admission, cap the number of running sequences (max_num_seqs in vLLM), and alert on the preemption counter. If it keeps rising, the server needs more memory per replica, from a quantized cache or more GPUs, or less traffic.

Unknown output lengths. Every scheduling decision would be easy if the scheduler knew how long each answer will be. It does not, which is why paging beats reservation and why research schedulers try to predict lengths. A request with a large max_tokens and a prompt that will run long is the one that eventually forces a preemption.

Long prompts without chunking. A single 100,000-token prompt prefilled in one step freezes every stream on its GPU for seconds. With chunking the freeze becomes a long TTFT for that one request, which is the right place for the cost.

Head-of-line blocking and fairness. Arrival-order admission lets one tenant's burst delay everyone. Sheng et al. (2024) defined fairness for LLM serving by a cost that counts input and output tokens. Their Virtual Token Counter scheduler, built on continuous batching, provably keeps the difference in service between any two backlogged clients within a fixed bound. Cache-aware ordering, which favors requests with long cached prefixes, makes starvation worse and needs the same kind of cap.

The scheduler itself. At hundreds of steps per second, building a batch, hashing blocks, and updating block tables on the CPU can take longer than the GPU's step. vLLM V1 was largely rewritten to move this work off the critical path (§20.7).

KV transfer as a failure mode. Disaggregation adds a network hop to every request. A slow or misconfigured network adds hundreds of milliseconds to every TTFT. A failed transfer must either fail the request or fall back to recomputing, and a prefill instance must hold the blocks until the decode side collects them. Collocated serving remains the right answer for many deployments, particularly at low or bursty traffic, or when TTFT and not ITL is the binding target.

Shared caches across tenants. A prefix cache is a timing side channel. Scope it to a trust group.

The table puts the alternatives of this section side by side.

In PyTorch

The kernel side of a paged cache is a gather through block tables. The block below builds a pool of scattered pages for three sequences of different lengths. It decodes one query per sequence against that sequence's own pages in a single batched computation, masking the unused slots of each last page. Then it checks the result against PyTorch's attention on each sequence's keys laid out contiguously. A real kernel such as vLLM's or FlashInfer's reads the pages in place instead of building the gathered tensor, but it computes exactly this.

In an engine you set this section's policies with a few arguments. The block below, shown and not run, configures vLLM with the block size, the per-step token budget of chunked prefill, the cap on running sequences, prefix caching, and the share of GPU memory for the weights and the block pool. It asks for two samples per prompt, which share their prompt's blocks.

Read more

• Yu et al. (2022). Orca: A Distributed Serving System for Transformer-Based Generative Models. Iteration-level scheduling and selective batching, the two ideas behind every continuous-batching engine.
• Kwon et al. (2023). Efficient Memory Management for Large Language Model Serving with PagedAttention. The vLLM paper, with the measurements of wasted KV memory, block tables, copy-on-write, preemption by swap or recompute, and the block-size study.
• vLLM. Automatic Prefix Caching. The design document for chained block hashes, the LRU free queue, eviction, and cache salts, with worked examples of the block tables.
• Zheng et al. (2024). SGLang: Efficient Execution of Structured Language Model Programs. RadixAttention, LRU eviction of leaves, cache-aware scheduling, and the proof that depth-first order is optimal.
• Agrawal et al. (2024). Taming Throughput-Latency Tradeoff in LLM Inference with Sarathi-Serve. Generation stalls measured, chunked prefills with stall-free batching, and how to choose the token budget.
• Zhong et al. (2024). DistServe: Disaggregating Prefill and Decoding for Goodput-optimized Large Language Model Serving. Goodput per GPU, prefill-decode interference, and how to size and place separate prefill and decode pools.
• Qin et al. (2024). Mooncake: A KVCache-centric Disaggregated Architecture for LLM Serving. Kimi's production system, with prefill and decode clusters, a KV cache pooled across CPU memory and SSDs, and scheduling around where the cache lives.
• Hickey (2026). Taking vLLM Apart: A Practical Guide to Disaggregated Serving. When disaggregation pays and when it does not, with measured KV transfer times, tail latencies, and the configuration of a prefill and decode pair.

Watch next

▶

▶

▶

▶