Memory and Scheduling

Chapter 31 established the scheduler's central safety rule: reserve the state required by a token plan before executing it. This chapter follows that rule down to physical KV-cache blocks. The allocator must account for growing sequences, shared prefixes, cancellations, and memory pressure. The scheduler must choose work that fits those blocks without losing sight of latency, fairness, or progress.

Several systems established the main techniques. Orca introduced iteration-level scheduling in 2022 (Yu et al. 2022). vLLM's PagedAttention applied block-based allocation to KV state in 2023 (Kwon et al. 2023). SGLang organized reusable prefixes with RadixAttention in 2024 (Zheng et al. 2024). Sarathi-Serve bounded prefill work within a colocated scheduler, while DistServe separated prefill and decode pools (Agrawal et al. 2024; Zhong et al. 2024). Mooncake later extended the placement problem into a storage-backed, cluster-wide KV hierarchy (Qin et al. 2025). These mechanisms compose. They are not stages in a required historical sequence.

From retained tokens to physical blocks

Let the logical KV payload per retained token be

$$\kappa = 2L\,n_{\mathrm{kv}}\,d_{\mathrm{head}}\,b_{\mathrm{kv}}.$$

Here $L$ is the number of transformer layers, $n_{\mathrm{kv}}$ is the number of key-value heads per layer, $d_{\mathrm{head}}$ is one head's dimension, $b_{\mathrm{kv}}$ is the bytes per cached element, and the factor two accounts for keys and values. The quantity $\kappa$ is logical bytes per token before sharding, alignment, metadata, or allocator overhead.

Here one allocation block holds the state for $B$ token positions. For a request $i$ retaining $T_i$ prompt and generated tokens, $q_i$ denotes its logical block count, $M_i^{\mathrm{alloc}}$ its allocated KV capacity in bytes, and $w_i$ the unused token capacity in its final block. Then

$$\begin{gathered} q_i=\left\lceil\frac{T_i}{B}\right\rceil,\\ M_i^{\mathrm{alloc}}=q_i B\kappa,\\ w_i=q_iB-T_i, \qquad 0\le w_i<B. \end{gathered}$$

The bound shows exactly what fixed blocks guarantee: tail waste is less than one block per unshared sequence. Paging does not eliminate block tables, alignment, reference counts, reserved capacity, or unused memory elsewhere in the process.

Three kinds of waste should not be conflated:

The runnable below performs exact discrete accounting. Four requests retain [37, 81, 130, 211] tokens and each declares a maximum of 256. It reports allocated token slots and tail waste for several block sizes. It does not turn block-table entries into a synthetic runtime cost; kernel measurements are needed for that side of the trade-off.

from math import ceil

lengths = [37, 81, 130, 211]
declared_max = 256

print("block  entries  allocated  tail-waste")
for block_tokens in [1, 8, 16, 32, 64]:
    entries = sum(ceil(length / block_tokens) for length in lengths)
    allocated = entries * block_tokens
    waste = allocated - sum(lengths)
    print(f"{block_tokens:>5}  {entries:>7}  {allocated:>9}  {waste:>10}")

contiguous = len(lengths) * declared_max
print("contiguous max-reservation slots:", contiguous)

Larger blocks reduce table entries but can increase tail waste. Neither count is a complete performance model. A deployment chooses $B$ using its sequence distribution, cache layout, kernel implementation, and measured latency.

Block tables remove the contiguity requirement

PagedAttention stores a request's logical KV sequence in fixed-size blocks that need not be adjacent in physical memory (Kwon et al. 2023). Let $\mathcal P$ be the set of physical block identifiers. The block table for request $i$ is a mapping

$$\pi_i: \{0,\ldots,q_i-1\}\longrightarrow\mathcal P.$$

Here logical block index $j$ maps to physical block $\pi_i(j)$. For example, a three-block request can have the following table even when blocks 2, 7, and 9 are scattered in the pool:

The attention kernel reads through this indirection. The design is inspired by virtual memory, but it is not a hardware page table: the serving runtime and attention kernel manage the mapping explicitly, and there need not be demand faults, a translation lookaside buffer, or operating-system replacement.

In the models, workloads, and FasterTransformer and Orca baselines evaluated in the vLLM paper, the complete vLLM system delivered two to four times the throughput at a similar latency level (Kwon et al. 2023). That result includes the block manager, scheduler, kernels, and sharing behavior. It is not a hardware-independent multiplier for block allocation alone.

Allocation is part of the token plan

continuous batching lets the active set change between iterations, but an iteration does not have to advance every resident request. A plan may include decode steps, prefill chunks, or no work for a particular request because of priority, capacity, or fairness policy. If the plan schedules $s_i\ge0$ new positions for request $i$, the additional blocks it needs are

$$\Delta q_i = \left\lceil\frac{T_i+s_i}{B}\right\rceil - \left\lceil\frac{T_i}{B}\right\rceil.$$

Here $T_i$ is the request's current retained length, $s_i$ is the number of new positions in this plan, and $\Delta q_i$ is the required increase in its block table. If $q_{\mathrm{free}}$ blocks are available after permitted cache eviction, memory feasibility requires

$$\sum_{i\in\mathcal S}\Delta q_i \le q_{\mathrm{free}},$$

where $\mathcal S$ is the set of requests selected by the plan. This condition is separate from a scheduler's token or compute budget. A plan can fit in memory and still be too slow for the current latency contract.

The allocator needs a reserve, execute, and commit protocol. It reserves all new blocks atomically before launching model work. Successful execution commits the mappings and token state. Cancellation or failure rolls uncommitted reservations back. One useful conservation check is

$$q_{\mathrm{free}} +q_{\mathrm{reserved}} +q_{\mathrm{committed}} =q_{\mathrm{capacity}}.$$

The four terms are free blocks, blocks reserved for a planned iteration, committed blocks referenced by live or cached state, and total pool capacity. No referenced block may be reassigned, and every state transition must preserve the equality.

flowchart TD
    A[Build a token plan] --> B[Compute additional blocks]
    B --> C{Enough reclaimable capacity?}
    C -->|no| D[Apply the configured pressure policy]
    D --> M[Defer or terminate this plan]
    C -->|yes| E[Atomically reserve blocks]
    E --> F[Execute model work]
    F --> G{Execution succeeds?}
    G -->|no| H[Roll back reservations]
    G -->|yes| I[Commit mappings and KV state]
    I --> J{Request or cache entry released?}
    J -->|no| N[Keep referenced blocks committed]
    J -->|yes| K[Decrement block references]
    K --> L[Return zero-reference blocks to free pool]

Sharing a prefix changes block ownership

Two requests may share a physical prefix block when their corresponding KV state is identical. Equal visible text is not enough. A cache identity normally includes at least the token IDs, model weights or revision, active adapters, position treatment, attention and cache format, and any multimodal state that affects the prefix. Tenant and isolation policy may forbid sharing even when the mathematics matches.

Here $\mathcal B_i\subseteq\mathcal P$ denotes the physical blocks referenced by request $i$, and $\mathcal R$ denotes the resident-request set. The live physical-block count is

$$q_{\mathrm{live}} = \left|\bigcup_{i\in\mathcal R}\mathcal B_i\right|, \qquad q_{\mathrm{live}}\le q_{\mathrm{capacity}},$$

Here the union counts a shared block once. For each physical block $p$, a reference count $r_p$ records all live and retained-cache owners. A block is reclaimable only after its relevant references are removed and $r_p=0$.

prefix caching adds an index from compatible token prefixes to those blocks. SGLang's RadixAttention stores prefixes in a radix tree, matches the longest reusable prefix, tracks references to live nodes, and evicts reusable leaf state under memory pressure (Zheng et al. 2024). Full shared blocks remain immutable. Divergent suffixes receive different blocks; an implementation that shares a writable partial block needs copy-on-write or an equivalent rule.

Prefix caching creates four operational questions:

1. Identity: Which model, adapter, position, cache-format, modality, and tenant fields form the cache namespace?
2. Ownership: Which live requests and retained index entries reference each block?
3. Value: How many prefill tokens and how much time would a hit save?
4. Eviction: Which unpinned prefix should leave when live work needs space?

A request-level hit rate can hide most of the value. Report matched prefix tokens or bytes as well, because a hit on eight tokens and a hit on eight thousand tokens do not save the same work.

Memory pressure needs an explicit policy

Dynamic allocation admits more work than maximum-length reservation, but it does not guarantee that every admitted sequence can grow to its declared limit. Here memory pressure means that the free pool cannot satisfy $\sum_i\Delta q_i$; the system must choose among distinct actions:

These actions are not interchangeable. Evicting an unpinned cache entry does not alter a live request. Preempting live work does. Offloading preserves state but adds a data path that can become slower than recomputation. Priority can protect interactive traffic while starving an older batch request, so victim selection needs age or fairness constraints as well as a memory score.

A retry after a pressure-policy action is a policy boundary, not permission to spin forever. If capacity cannot be recovered, the scheduler must defer, reject, or surface a failure. An invisible retry loop converts a known allocation failure into unbounded queueing.

Chunked prefill shares an iteration budget

A long prefill can occupy an iteration long enough to widen inter-token gaps for active decodes. Sarathi-Serve splits a prefill into chunks and coalesces those chunks with decode work (Agrawal et al. 2024). Here $\mathcal D$ denotes the selected decode requests, $d_i$ their scheduled decode positions, $\mathcal P_f$ the selected prefill requests, $c_j$ their chunk sizes, and $K$ a profiled iteration token budget. A simplified constraint is

$$\sum_{i\in\mathcal D}d_i + \sum_{j\in\mathcal P_f}c_j \le K.$$

Without multi-token decoding, $d_i$ is usually one. Token count is only a proxy for execution time: context length, kernels, phase mix, parallel layout, and hardware change the work per token.

Chunking bounds how much prefill work enters one plan; it does not remove all prefill-decode interference. Small chunks can add launches, repeated scheduling, and less efficient kernels. Decode-first policies can protect token cadence but starve new prefills and worsen time to first token. The scheduler therefore needs per-class queue age and latency measurements, not only a target batch size.

Move KV state only when the data path earns its cost

Prefill/decode disaggregation gives each phase its own device pool. It removes colocated kernel contention and uncouples some resource and parallelism choices, but decode cannot use a request until the required KV state reaches its pool. Here $\tau_{\mathrm{fixed}}$ denotes setup and synchronization latency, $S$ the transferred KV payload in bytes, and $\beta$ the path's achieved bandwidth. The isolated transfer time obeys

$$\tau_{\mathrm{transfer}} \ge \tau_{\mathrm{fixed}}+\frac{S}{\beta}.$$

The model uses achieved rather than advertised link bandwidth. End-to-end delay also includes source and destination queues, contention, retries, and backpressure. Transfer can overlap other work, but the consumer still needs a clear readiness and ownership protocol.

DistServe optimizes separate prefill and decode resources under chosen TTFT and TPOT attainment targets (Zhong et al. 2024). Mooncake extends the same state movement problem across GPU memory, CPU dynamic random-access memory (DRAM), SSD, and network links (Qin et al. 2025). These systems demonstrate particular designs and measured workloads. They do not establish disaggregation or tiering as the universal choice.

Cache-aware routing also needs both locality and load. Here $Q_j$ denotes the predicted queue delay on worker $j$, $P_i$ the prompt length, $H_{ij}$ the compatible cached-prefix length, $C_{\mathrm{prefill}}(u;j)$ the predicted time to compute $u$ uncached tokens there, and $X_{ij}$ the transfer and routing overhead. One illustrative completion-time estimate is

$$\widehat C_{ij} = Q_j +C_{\mathrm{prefill}}(P_i-H_{ij};j) +X_{ij}.$$

Choosing the lowest estimate is only a starting point. Capacity, fairness, fault domains, prediction error, and tenant isolation can override it.

Verify the allocator and scheduler together

Correctness tests should exercise more than successful completion:

1. Cancel a request between reservation and commit; every reserved block must return to the pool.
2. Share a prefix across requests, finish them in different orders, and prove that the block is reclaimed only after its final reference disappears.
3. Inject execution and transfer failures; committed mappings must remain valid and uncommitted mappings must roll back.
4. Exhaust the pool; the configured eviction, preemption, deferral, rejection, and fairness rules must occur explicitly rather than through a retry loop.
5. Change model revision, adapter, position, modality, or tenant namespace; an incompatible prefix must miss the cache.

Under load, report four groups of measurements:

• Pool state: free, reserved, committed, and uniquely referenced blocks; tail waste; allocation failures; and high-water marks.
• Reuse and reclamation: matched prefix tokens, hit and eviction rates, reuse distance, recomputed tokens, offloaded bytes, and reload latency.
• Scheduling: queue age by request class, prefill chunk sizes, decode batch composition, preemptions, rejections, and fairness outcomes.
• Service result: TTFT, inter-token gaps, TPOT, goodput, acceptance, KV transfer bytes and latency, accelerator time, and cost.

Chapter 31 gives the matched-load evaluation protocol. The additional requirement here is conservation: reconcile every scheduled token and every physical block from admission through release.

Payoff and boundary

Block allocation gives the scheduler a precise feasibility test. Reference counts make prefix sharing safe. Pressure policies state which work may be discarded, moved, delayed, or refused. Chunk budgets control colocated phase interference, and transfer models expose the price of separating state from compute.

These mechanisms are independently useful and often combined. The allocator's job is to preserve memory and ownership invariants. The scheduler's job is to choose among safe plans using the workload's latency, fairness, acceptance, and cost contract. Confusing those responsibilities produces systems that are fast only until the first cancellation, cache miss, burst, or exhausted block pool.

Further reading