Memory and Scheduling

A serving engine spends most of its accelerator memory on one growing object, the key-value cache, and most of its scheduling effort deciding which requests share a forward pass. The mechanisms in this chapter form a dependency chain. Continuous batching removes static-batch waste but makes allocation churn visible. PagedAttention answers it, clearing the fragmented cache and making prefix sharing cheap. With sharing now cheap, radix-tree prefix caching reuses shared prompts, but prefill and decode still interfere. That last interference is what phase splitting removes, and the price is a network transfer. Memory layout and scheduling policy are therefore the same serving problem, seen from two sides.

Two facts that make one problem

Chapter 31 named the two phases of generation and their opposite shapes. Prefill reads the whole prompt in one compute-bound pass and produces the first token. Decode then emits one token per forward pass, each step reading the entire key-value cache for one new query, so decode is memory-bandwidth-bound and runs at batch size one per request unless the engine batches across requests. The memory cost and the scheduling cost of those two phases are not separate concerns. They are two faces of one resource problem, and treating them together is what this chapter is for.

The memory fact is that the key-value cache is large, per-request, and grows by one slot per layer per generated token. For a request of length $T$, the cache holds $2 \cdot T \cdot L \cdot n_{\text{kv}} \cdot d_{\text{head}}$ values, the factor of two for keys and values. On a model with billions of parameters the weights are fixed, but the cache for a few dozen concurrent long-context requests can exceed the weights, and it appears and disappears as requests arrive and finish. A naive engine reserves the maximum possible length for every request up front, which wastes most of the reservation for requests that finish early and caps the batch size far below what the hardware could hold.

The scheduling fact is that requests do not share a length. In a batch of generations, one request may stop at twenty tokens and another run to two thousand. If the engine schedules a batch and waits for every member to finish before admitting the next, the short requests sit idle inside a padded batch while the longest one decodes, and newly arrived requests wait behind the whole batch. Throughput collapses to the pace of the slowest member, and latency for a new arrival is the tail of the batch in front of it.

So the problem has two halves that this chapter treats together: pack the key-value cache so memory is not wasted, and schedule the forward passes so no request waits on another's length. The four sections that follow each take one mechanism, and each mechanism earns its place by fixing what the previous one exposed.

Iteration, not request

The first move is to schedule at the granularity of an iteration rather than a request. An iteration is one forward pass that advances every active request by a single token. After each iteration the scheduler is free to remove requests that just emitted their stop token and admit waiting requests into the next iteration's batch. This is continuous batching, also called iteration-level scheduling, introduced by Orca (Yu et al. 2022). The batch is no longer a fixed cohort that lives and dies together; it is a sliding window over the active set, refilled every step. A request that finishes at token twenty leaves immediately and its slot is reused, instead of padding out the batch until the longest member finishes. Figure 32.1 shows the loop: every iteration retires whatever just emitted its stop token and admits waiting requests, so the batch composition changes each step.

Before Orca, serving systems batched at request granularity: form a batch, run it to completion, return the results. This is request-level scheduling, and it inherits the static-batch pathology of any padded-cohort design. Orca's contribution was to schedule at iteration granularity and to make the batch a living set, refilled every step, which is the single change that lets a serving engine keep accelerators busy under heterogeneous request lengths (Yu et al. 2022). Orca also introduced selective batching, batching the parts of the computation that can be batched across requests of different lengths while running attention per request.

Continuous batching solves the scheduling fact and immediately exposes the memory fact in a sharper form. If admission happens every iteration, the engine must allocate and free key-value cache space every iteration, for requests whose final length it does not know. Reserving a contiguous maximum-length buffer per request, the obvious scheme, fragments memory: a finished request leaves a hole too small for the next, and reserved-but-unused tail space is dead weight. Measurements in the vLLM paper put the waste from this fragmentation and over-reservation at the majority of cache memory in prior systems (Kwon et al. 2023). The next move exists to reclaim it.

The cache as virtual memory

The second move removes that waste by borrowing virtual memory from operating systems. The insight is that the key-value cache is exactly the kind of object virtual memory was invented for: a per-process allocation that grows unpredictably and must share a fixed physical pool without fragmentation. PagedAttention (Kwon et al. 2023) stores the key-value cache in fixed-size blocks, each holding the keys and values for a fixed number of tokens, and lets a request's logical sequence of blocks map to physically non-contiguous blocks through a block table. The attention kernel is rewritten to gather keys and values through that table instead of assuming contiguity. Now allocation is per block, not per request: a request grows by appending a block when its current block fills, memory is shared at block granularity across all requests, and the only internal waste is the partial final block. The analogy is precise. The block is a page, the block table is a page table, and the engine is a memory manager that hands out and reclaims pages as sequences grow and finish. Figure 32.2 shows the indirection: a request's logical sequence of token blocks maps through a block table to physically scattered blocks in a shared pool.

vLLM is the serving system built on this idea, and it reported two to four times the throughput of the prior generation at the same latency by lifting the achievable batch size (Kwon et al. 2023). The lift comes from where the waste goes. Figure 32.4 contrasts the two schemes: reserving a maximum-length buffer per request leaves utilization at the ratio of average to maximum length, so a workload of mostly short requests strands most of the pool, while paging holds only the realized length plus a partial final block and keeps utilization near one regardless of length spread, which is what lifts the achievable batch size. The rest of vLLM, the block manager, the swapping of blocks to host memory under pressure, the copy-on-write sharing, all follows from treating the cache as paged virtual memory. The result reset the throughput baseline for open serving. It also opened a door: once the cache is paged and blocks can be shared, identical content across requests need not be stored or computed twice.

Sharing prefixes

Paging makes sharing cheap, and that is the third move. Two requests that begin with the same prompt, a shared system prompt or a few-shot preamble, compute identical keys and values for that prefix. Under paging, they can point their block tables at the same physical blocks for the shared prefix and diverge only where their tokens diverge, with copy-on-write when one writes into a shared block. The open question is how to find shareable prefixes automatically across a stream of requests with arbitrary overlap. RadixAttention (Zheng et al. 2024), the prefix caching mechanism of the SGLang runtime, answers it by storing all cached prefixes in a radix tree keyed by token sequence, with least-recently-used eviction. A new request walks the tree to find the longest cached prefix of its prompt, reuses those blocks, and computes only the uncached suffix. The radix tree turns prefix reuse from a special case, handled by hand for a known shared prompt, into a default the runtime applies to all traffic. Prefix caching turns the repeated structure of real workloads, shared system prompts, multi-turn chat history, branching agent calls, into reused computation rather than recomputed computation. The same reuse is now a billed product surface: API providers sell it as prompt caching, with cached input tokens priced at roughly a tenth of the standard input rate and some providers charging for cache writes (Anthropic 2025), so putting the stable prefix first in a prompt became a caller's cost lever as well as a server's scheduling win. Figure 32.5 shows two requests sharing a system-prompt prefix: they point at the same cached blocks up to the branch point and compute only their divergent suffixes.

Paging and prefix sharing both assume prefill and decode share a device and a batch, and that assumption is the next thing to break. Running both in one batch means a long prefill stalls the decodes waiting behind it, because the two phases want different parallelism and different batch shapes. One way out keeps the single device and schedules around the interference. Sarathi-Serve (Agrawal et al. 2024) addresses it within a single device by splitting prefill into chunks and coalescing each chunk with ongoing decodes, so a long prefill never stalls decode. The fourth move takes the opposite route.

Splitting the phases

The fourth move separates the two phases onto different hardware. Prefill is compute-bound and bursty; decode is memory-bandwidth-bound and steady. Prefill/decode disaggregation runs prefill on one pool of machines and decode on another, transferring the key-value cache between them over the network. Each pool is provisioned and parallelized for its own phase, and neither interferes with the other's latency. DistServe (Zhong et al. 2024) optimizes the placement for goodput, the rate of requests that meet both a time-to-first-token target for prefill and a time-per-output-token target for decode. Mooncake (Qin et al. 2024) centers the whole architecture on the key-value cache, pooling CPU dynamic random-access memory (DRAM) and SSD across the cluster into a disaggregated cache that prefill writes and decode reads. Figure 32.6 sketches the split: the prompt enters a prefill pool, the resulting key-value cache crosses the network, and the decode pool reads it to emit tokens, each pool sized and parallelized for its own phase.

This is the most recent move, and it inverts the assumption the first three shared. The within-device line, exemplified by chunked-prefill scheduling (Agrawal et al. 2024), keeps one resource pool and schedules carefully; the disaggregated line (Zhong et al. 2024; Qin et al. 2024) accepts a network transfer of the key-value cache to remove interference entirely. At scale the two lines composed rather than one displacing the other: fleets disaggregate across pools while each pool's scheduler still chunks and interleaves, and disaggregation is the core design of the production orchestration layers, NVIDIA Dynamo and the CNCF llm-d project among them (NVIDIA 2025; llm-d project 2025).

Once the cache can cross the network, its placement stops being a single device's problem. Production systems now treat KV blocks as a tiered storage hierarchy of their own: hot blocks in accelerator memory, warm blocks spilled to host DRAM and SSD, and shared stores such as LMCache and Mooncake's disaggregated store keeping them addressable across instances, so a prefix computed on one replica can be reused on another (LMCache team 2025; Qin et al. 2024). Routing follows the cache: a KV-aware scheduler such as Dynamo's sends a request to the replica that already holds its prefix rather than to the least loaded one (NVIDIA 2025). The cache this chapter began by scheduling within one device ends as a placed, routed resource at fleet scale.

What each move costs

The cascade buys four benefits, and each comes with a named cost.

• Block size in paging. A small block wastes little in the partial final block and shares at fine granularity, but multiplies block-table entries and per-kernel gather overhead. A large block cuts that overhead but wastes more tail memory and shares more coarsely. Figure 32.7 plots the two costs against block size: internal fragmentation rises with the block while indirection overhead falls, and their sum is a U-curve with an interior optimum. The block size is a tuning knob, not a constant, and the right value depends on typical sequence length and how much prefix sharing the workload has.

Try changing T, the typical sequence length, and watch the optimal block size move with it, matching the square-root formula.

import numpy as np
import matplotlib.pyplot as plt
T = 512            # typical sequence length, in tokens
w_frag = 1.0       # cost per wasted token in the partial final block
w_indir = 4.0      # cost of one block-table entry and its gather
b = np.arange(1, 257)
frag = w_frag * (b / 2)          # waste grows with block size
indir = w_indir * (T / b)        # indirection falls as 1/block
total = frag + indir
b_star = b[np.argmin(total)]
b_formula = np.sqrt(2 * w_indir * T / w_frag)
print("argmin block size:", b_star, "  sqrt formula:", round(b_formula, 1))
plt.plot(b, frag, "--", label="fragmentation (b/2)")
plt.plot(b, indir, "--", label="indirection (T/b)")
plt.plot(b, total, label="total")
plt.axvline(b_star, color="k", lw=0.8)
plt.xlabel("block size (tokens)"); plt.ylabel("cost"); plt.legend(); plt.show()

• Prefix-cache retention versus memory. Keeping more prefixes in the radix tree raises the hit rate for workloads with shared structure, but the cache competes with live requests for the same physical blocks. Under memory pressure the engine must evict cached prefixes to admit new work, so the prefix cache is a bet that reuse will pay before the blocks are reclaimed. Workloads with little overlap pay the bookkeeping and get little back.
• Disaggregation versus colocation. Disaggregation removes interference and lets each phase scale alone, at the cost of a key-value cache transfer per request and the bandwidth to hide it. Colocation with chunked prefill keeps one pool and one transfer-free path, at the cost of scheduling complexity and some residual interference. The crossover is set by prompt length and latency targets.
• Throughput versus latency in batching. A larger continuous batch raises throughput but lengthens each iteration, which raises time-per-output-token for every request in it. Admission is therefore a latency knob: the engine can cap batch size or reserve headroom to protect tail latency, trading some throughput for it.

The engine as a loop and a memory manager

All four moves reduce, in code, to a loop and a memory manager. The loop is iteration-level: each step, the scheduler picks the set of requests to run, the model runs one forward pass over them, the sampler produces one token each, finished requests are retired, and waiting requests are admitted into the next step. In vLLM this is the engine-core step (EngineCore.step, vllm/v1/engine/core.py), which calls the scheduler (vllm/v1/core/sched/scheduler.py) to form the batch and the model runner to execute it. The scheduler tracks queues for running, waiting, and swapped requests, and moves requests between them as cache blocks are allocated and reclaimed.

The memory manager owns the block pool. It maintains a free list of physical blocks and a per-request block table mapping logical positions to physical blocks. Allocation appends a block when the current one fills; freeing returns a request's blocks to the pool on completion. Under pressure the manager can preempt a request, either recomputing its cache later or swapping its blocks to host memory and back, which is the serving analogue of paging to disk. The attention kernel reads through the block table, so the physical layout stays invisible to the rest of the model. For prefix sharing, the block table of a new request is initialized to point at the cached blocks of its longest matching prefix, with a reference count so a shared block is freed only when its last user finishes, and copied on first write past the shared point.

Two operational realities are worth naming. First, the partial final block is the only internal fragmentation paging leaves, so average waste falls as sequences lengthen relative to block size, which is why long-context workloads benefit most from paging. Second, prefix-cache hit rate is workload-shaped: a chat service with a fixed system prompt or an agent loop that re-sends a long tool preamble can see most of its prefill served from cache, while a stream of unrelated single-turn prompts sees almost none. Instrumenting the hit rate, the achievable batch size, and the preemption rate is how an operator reads whether the memory manager is winning.

Further reading