The Serving Problem

A model checkpoint does not decide when a request runs, how much memory it may occupy, or which request should go next. A serving system makes those decisions while requests arrive with different prompt lengths, output lengths, and deadlines. It must create the model's state, retain that state between tokens, share finite accelerators across users, and decide when admitting more work would make existing work late.

This chapter focuses on decoder-only autoregressive Transformers. Serving them is an online resource-allocation problem. The prefill phase processes a prompt and creates attention state. The decode phase repeatedly consumes that state to produce one new token. Those phases usually stress hardware differently, but neither has a universal bottleneck. The useful objective is goodput: completed requests that meet an explicit latency contract, measured together with acceptance rate and cost.

Measure the request lifecycle

A latency number is meaningful only after its endpoints are fixed. In the formula below, $a_i$ is the time request $i$ reaches the server, $t_{i,j}$ is the time its $j$th output token leaves the server, and $O_i$ is its output-token count. For a request with at least two output tokens,

$$\begin{gathered} \operatorname{TTFT}_i=t_{i,1}-a_i, \\ \operatorname{TPOT}_i= \frac{t_{i,O_i}-t_{i,1}}{O_i-1}, \\ \operatorname{E2E}_i=t_{i,O_i}-a_i. \end{gathered}$$

Each token after the first has its own gap,

$$\begin{gathered} \operatorname{ITL}_{i,j}=t_{i,j}-t_{i,j-1}, \\ \operatorname{E2E}_i = \operatorname{TTFT}_i +\sum_{j=2}^{O_i}\operatorname{ITL}_{i,j}. \end{gathered}$$

Here time to first token (TTFT) includes every server-side delay before the first output token. Inter-token latency (ITL) is one observed gap; time per output token (TPOT) is the average of those gaps for a request. End-to-end latency (E2E) ends at the last token. For a one-token response, TPOT is undefined. The ITL distribution reveals stalls that one average can hide. Client-perceived measurements add network and client buffering outside the server boundary used above.

TTFT is not simply “prefill time.” It can contain admission delay, queueing, tokenization, prefix-cache lookup, prefill, scheduling gaps, and the first sampling step. TPOT can contain scheduler delay and interference from other requests as well as model execution. Report percentiles for each request class, because a short-prompt interactive request and a long offline generation do not have the same useful deadline.

The request path makes those delays visible:

flowchart TD
    A[Request reaches server] --> B[Admission and queue]
    B --> C[Reserve state and prefill prompt]
    C --> D[Sample and stream first token]
    D --> E{Finished?}
    E -->|no| F[Scheduler selects one decode step]
    F --> G[Append token and grow KV state]
    G --> E
    E -->|yes| H[KV manager releases state]
    H --> I[Request completes]

Throughput also needs a unit. Request throughput counts completed requests per second; token throughput counts prompt or output tokens per second. A workload can improve one while harming the other, especially when request lengths vary. For an observation interval of duration $\Delta$, one operational definition of request goodput is

$$G_{\Delta} = \frac{1}{\Delta} \sum_{i\in\mathcal C_{\Delta}} \mathbf 1[\operatorname{TTFT}_i\le S_i^{\mathrm{first}}] \mathbf 1[\operatorname{TPOT}_i\le S_i^{\mathrm{token}}].$$

Here $\mathcal C_{\Delta}$ is the set of requests completed in the interval; $S_i^{\mathrm{first}}$ and $S_i^{\mathrm{token}}$ are that request's TTFT and TPOT service-level objectives (SLOs); and $\mathbf 1[\cdot]$ is one when its condition is true and zero otherwise. DistServe instead reports the maximum arrival rate at which a chosen share of requests, such as 90%, meets both phase SLOs, another useful goodput convention (Zhong et al. 2024). A one-token response can use a TTFT or E2E contract without a TPOT condition. In every convention, goodput must be paired with offered load, admission rate, and rejection rate. A system can manufacture excellent latency by refusing difficult requests.

Prefill and decode occupy different regimes

Prefill evaluates all prompt positions and creates the keys and values needed by later attention. Its matrix operations expose parallel work across the prompt and usually have higher arithmetic intensity. Decode evaluates one new position per active sequence. At small batch sizes, each step performs little work relative to the model weights and cache bytes it must access, so it is often limited by memory bandwidth. Batching several decode requests reuses the loaded weights across more work and can move the step toward compute saturation (Pope et al. 2023; Yuan et al. 2024).

The roofline model states this condition rather than turning it into a slogan. For an operation requiring $F$ floating-point operations and $D$ bytes of data movement, its execution time is bounded below by

$$\begin{gathered} \tau \ge \max\!\left( \frac{F}{P_{\max}}, \frac{D}{B_{\max}} \right), \\ I=\frac{F}{D}. \end{gathered}$$

Here $\tau$ is execution time, $P_{\max}$ is peak arithmetic throughput, $B_{\max}$ is peak memory bandwidth, and $I$ is arithmetic intensity. The operation is bandwidth-limited in this simplified model when $I<P_{\max}/B_{\max}$ and compute-limited when the inequality reverses. Model shape, sequence length, batch composition, quantization, kernels, parallelism, and hardware all change $F$, $D$, or the attainable fractions of the two peaks. Long-prefill and small-batch-decode are common regimes, not laws of nature.

This distinction explains the basic batching trade-off. More decode sequences can amortize weight reads and raise token throughput. The larger batch also takes longer to execute, consumes more state memory, and may make each sequence wait longer for its next turn. The best batch is therefore not the one with the highest raw throughput. It is the largest feasible batch that still preserves the relevant latency distribution under the measured workload.

KV state turns memory into an admission constraint

At decode step $t$, attention needs keys and values derived from all retained positions. Saving them avoids recomputing the prefix on every token. For a standard unsharded cache, the logical KV memory of request $i$ is

$$\begin{gathered} m_i = 2L\,n_{\mathrm{kv}}\,d_{\mathrm{head}}\,b_{\mathrm{kv}}\,T_i, \\ M_{\mathrm{KV}}=\sum_{i\in\mathcal R}m_i. \end{gathered}$$

Here $L$ is the transformer-layer count; $n_{\mathrm{kv}}$ is the number of key-value heads per layer; $d_{\mathrm{head}}$ is the dimension of each head; $b_{\mathrm{kv}}$ is the number of bytes per cached element; $T_i$ is the number of retained prompt and generated tokens for request $i$; $\mathcal R$ is the set of resident requests; and the factor two accounts for keys and values. The total must fit beside other allocations:

$$\begin{aligned} M_{\mathrm{used}} &=M_{\mathrm{weights}}+M_{\mathrm{KV}}\\ &\quad+M_{\mathrm{workspace}}+M_{\mathrm{reserve}},\\ M_{\mathrm{used}}&\le M_{\mathrm{device}}. \end{aligned}$$

The four terms on the left are model weights, resident KV state, temporary kernel and communication workspace, and a safety reserve. Their sum is $M_{\mathrm{used}}$, which must not exceed usable accelerator memory $M_{\mathrm{device}}$. The formula describes logical bytes before prefix sharing. If requests share physical prefix blocks, count each unique block once. Tensor parallelism may shard KV heads or replicate them, so per-device memory depends on the parallel layout as well as the architecture.

Here the architecture fixes $L$, $n_{\mathrm{kv}}$, and $d_{\mathrm{head}}$, but the serving layer still controls cache precision, admitted sequences, block allocation, prefix sharing, eviction, and parallel placement. The KV cache is therefore often an admission constraint, not always the constraint. Weights can dominate memory for short sequences. Arithmetic, memory bandwidth, network transfer, or queueing can bind before KV capacity does.

Multi-query and grouped-query attention reduce $n_{\mathrm{kv}}$ relative to ordinary multi-head attention. Cache quantization reduces $b_{\mathrm{kv}}$. Both change the capacity equation, but they may also change accuracy or kernel behavior. Chapter 8 defines the state the model creates; Chapter 32 develops the allocation and eviction mechanisms in detail.

Iteration scheduling removes static-batch idle time

Autoregressive requests finish after different numbers of decode steps. A static batch remains tied to its longest request, leaving slots idle after short requests finish and delaying newly arrived work. Orca introduced iteration-level scheduling: after each model iteration, the server can remove finished requests and form the next batch from the remaining and waiting work (Yu et al. 2022). Modern systems commonly call this continuous batching.

The following runnable isolates that scheduling effect. Four requests are available at time zero, two slots are available, and output lengths are [2, 8, 3, 7] decode steps. It ignores prefill, memory limits, arrivals, and kernel cost, so it is an accounting example rather than a performance model.

lengths = [2, 8, 3, 7]
slots = 2

static_steps = sum(
    max(lengths[start:start + slots])
    for start in range(0, len(lengths), slots)
)

waiting = list(lengths)
running = []
continuous_steps = 0
active_slot_steps = 0

while waiting or running:
    while waiting and len(running) < slots:
        running.append(waiting.pop(0))
    active_slot_steps += len(running)
    running = [remaining - 1 for remaining in running if remaining > 1]
    continuous_steps += 1

tokens = sum(lengths)
print("static steps:", static_steps)
print("continuous steps:", continuous_steps)
print("static slot utilization:", f"{tokens / (static_steps * slots):.1%}")
print("continuous slot utilization:", f"{active_slot_steps / (continuous_steps * slots):.1%}")

Continuous batching does not reduce the model work needed for those tokens. It changes when a free slot can be reused. Real schedulers must also decide which waiting request to admit, how much future KV memory to reserve, whether to prioritize prefills or decodes, and when to preempt work. A scheduling policy is part of the service contract, not an implementation detail behind it.

What a scheduler must guarantee

A production scheduling iteration needs a clear order of operations:

1. Retire completed or cancelled requests and release their state.
2. Reject or defer requests that cannot fit the current policy and resource limits.
3. Choose prefill chunks and decode steps within token, memory, latency, and fairness budgets.
4. Reserve every required KV block before launching model work.
5. Execute the chosen batch, then commit tokens, timestamps, and cache state.

The order protects three invariants. Allocated memory never exceeds the pool; a block referenced by a running request is never freed or reassigned; and a request does not execute unless its next state has been reserved. If no batch can run, the scheduler should expose whether it is deliberately waiting, rejecting work, or blocked by a resource. Silent retry loops turn an admission failure into unbounded queueing.

Five mechanisms remove different waste

Several serving techniques are often presented as interchangeable speedups. They act on different resources and introduce different costs.

PagedAttention applies virtual-memory-style blocks to KV storage. A request's logical sequence can map to non-contiguous physical blocks allocated as it grows. This sharply reduces reservation and fragmentation waste, and it enables block sharing, but it does not reduce the logical bytes required by a unique token. In the vLLM paper's evaluated workloads, this memory management produced two to four times the throughput of the compared systems at similar latency (Kwon et al. 2023). That number belongs to those models, workloads, and baselines, not to paging in isolation.

Prefix reuse skips work only when the server can reuse KV state for exactly the same token prefix under a compatible model and cache configuration. SGLang's RadixAttention stores reusable prefixes in a radix tree and evicts them with a cache-aware policy (Zheng et al. 2024). Reuse needs explicit identity and isolation rules: model revision, adapter, cache format, positional treatment, and tenant policy can all invalidate an otherwise identical token sequence.

Chunked prefill and disaggregation address phase interference in different ways. Sarathi-Serve divides a long prefill into chunks and combines them with ongoing decodes, limiting how long decode work waits behind one prompt (Agrawal et al. 2024). DistServe assigns prefill and decode to different GPU pools and chooses resources and parallelism for each phase separately (Zhong et al. 2024). Disaggregation removes colocated kernel interference, but it does not make the phases independent: the decode pool cannot start until the KV state arrives, and both pools can still queue.

Evaluate a serving policy under load

A single unloaded latency measurement says little about a scheduler. A useful evaluation preserves the request stream and observes the system through saturation:

1. Specify the workload. Record arrival timing, prompt lengths, requested output limits, actual output lengths, sampling settings, request classes, prefix-reuse opportunities, and cancellations.
2. Specify the contract. Define the measurement boundary and per-class TTFT, TPOT, E2E, acceptance, and availability targets before tuning.
3. Sweep offered load. Increase arrivals until queueing, rejection, or tail latency violates the contract. Report the whole curve, not one favorable operating point.
4. Match resources. Compare policies on the same model, cache precision, accelerator type and count, interconnect, parallel layout, and output distribution.
5. Account for all work. Report request and token throughput, goodput, admission and rejection rates, queue depth, KV utilization, prefix-hit rate, preemptions, transferred KV bytes, accelerator time, and cost.
6. Inspect tails by cause. Separate queue delay, prefill execution, decode gaps, cache misses, preemption, transfer, and client backpressure. An average cannot identify which resource failed.

Admission policy deserves special scrutiny. Reserving every request's declared maximum length protects memory but can waste most of the pool. Reserving only its current length admits more work but needs a credible plan for growth, preemption, eviction, or rejection. Priority scheduling can protect interactive traffic while starving batch jobs. Prefix caches can improve TTFT while creating cross-tenant data or timing risks if isolation is underspecified. Every optimization moves a boundary that operations must expose.

Payoff and boundary

Serving does not turn one scalar called “compute” into one scalar called “speed.” It coordinates a request lifecycle with two recurring execution regimes, growing state, uncertain output length, finite memory, and deadlines. Continuous batching, paged KV allocation, prefix reuse, chunked prefill, and phase disaggregation each remove a different source of waste. None replaces admission control or workload-specific measurement.

A defensible serving result states the model and hardware, offered and admitted load, request-length distributions, scheduling policy, cache policy, and latency contract. It then reports tail latency, goodput, rejection, and cost together. That is the boundary between a fast kernel demonstration and a service that remains useful when users arrive concurrently.

Further reading