Continuous Function

Foundation reference

LLM Serving at Scale: Prefill, Decode & Continuous Batching

A language-model server handles each request in two phases: prefill processes the prompt, and decode generates the output one token at a time, reading the keys and values of earlier tokens from a key–value (KV) cache. vLLM's PagedAttention brought KV-cache waste close to zero and improved throughput 2–4× over earlier serving systems at the same latency (Kwon et al., 2023).

A newer notebook covers this concept. This older page keeps its summary, math and sources.

Concept 21 of 100EfficiencyStudy phase 6
Open the demoOpen the newer notebookAll concepts
Key equation
Latency≈TTFT+(Tout−1)⋅TPOT\text{Latency} \approx \text{TTFT} + (T_{\text{out}}-1) \cdot \text{TPOT}
Reading map and next steps

Study guide

Where to start

Concept 21 of 100LLM ServingEfficiency · Study phase 6: Modern efficiency & inference
Question

Why are prefill (large parallel matrix multiplications over the prompt) and decode (small matrix multiplications plus large KV-cache reads) such different workloads, and why does batching them together cause interference?

Open the demoGo to the mathOpen the newer notebookNext concept
How to study this pagePredict · Check · Generalize · Continue
PredictSay what you expect.

Before you move a control in the demo, say what you expect to change.

CheckCheck against the math and the papers.

Compare what the demo shows with the key equation and with the papers cited below.

GeneralizeName what stays the same.

Identify the part of the idea that survives a change of notation or model, so you can recognize it in another paper or system.

ContinueContinue in the newer notebook.

The newer notebook covers the same concept and has an interactive demo.

Why It Matters for Modern Models

  • A language-model server handles each request in two phases: prefill processes the prompt, and decode generates the output one token at a time, reading the keys and values of earlier tokens from a key–value (KV) cache. vLLM's PagedAttention brought KV-cache waste close to zero and improved throughput 2–4× over earlier serving systems at the same latency (Kwon et al., 2023).
  • Prefill is usually compute-bound, while decode at typical batch sizes is limited by memory bandwidth. DistServe runs the two phases on separate GPUs and reports serving 7.4× more requests, or meeting 12.6× tighter latency targets, than earlier systems (Zhong et al., 2024).
  • Continuous (iteration-level) batching adds and removes requests after every decoding step, so the GPU does not sit idle waiting for the longest request in a batch to finish (Yu et al., 2022).
  • KV-cache memory grows with context length and limits how many requests fit in a batch; paging makes that memory easier to allocate and share.

Questions to Think About

  • How does continuous batching, which keeps a rolling set of active sequences as requests arrive and finish, differ from simply using bigger batches?
  • Why does the KV cache, rather than arithmetic, usually decide the largest batch a server can run?
  • How does paging the KV cache avoid fragmentation as requests grow and finish at different times, and how does it let requests share a cached prefix?

Interactive Demo

Core Math

If you prefer intuition first, try the demo above, then come back for the math.

Key Equation
Latency≈TTFT+(Tout−1)⋅TPOT\text{Latency} \approx \text{TTFT} + (T_{\text{out}}-1) \cdot \text{TPOT}

Serving a language model to many users is a scheduling problem under latency targets, and KV-cache memory is usually the binding constraint.

Latency of one request:

Latency≈TTFT⏟time to first token+(Tout−1)⋅TPOT⏟time per output token\text{Latency} \approx \underbrace{\text{TTFT}}_{\text{time to first token}} + (T_{\text{out}}-1) \cdot \underbrace{\text{TPOT}}_{\text{time per output token}}

TTFT is dominated by prefill, which processes the whole prompt in parallel (plus any time spent queueing); TPOT is set by decode, which generates one token at a time and reads the KV cache at every step.

Goodput: DistServe defines it as the highest request rate at which a target fraction pp of requests (for example 90%) meet both latency objectives (Zhong et al., 2024):

Goodput=max⁡{λ:Pr⁡λ ⁣(TTFT≤STTFT∧TPOT≤STPOT)≥p}\text{Goodput} = \max\left\{\lambda : \Pr_\lambda\!\left(\text{TTFT} \le S_{\text{TTFT}} \wedge \text{TPOT} \le S_{\text{TPOT}}\right) \ge p\right\}

where λ\lambda is the request arrival rate and STTFT,STPOTS_{\text{TTFT}}, S_{\text{TPOT}} are the service-level objectives (SLOs).

KV-cache paging: with blocks of PP tokens, a sequence of length TT occupies

KV-mem(T)∝⌈TP⌉⋅P⇒waste(T)∝⌈TP⌉⋅P−T<P\text{KV-mem}(T) \propto \left\lceil \frac{T}{P} \right\rceil \cdot P \quad \Rightarrow \quad \text{waste}(T) \propto \left\lceil \frac{T}{P} \right\rceil \cdot P - T < P

PagedAttention stores each sequence's cache in fixed-size blocks that need not be contiguous. This removes fragmentation between sequences, limits waste to the unfilled part of each sequence's last block, and lets sequences share blocks for a common prefix (Kwon et al., 2023).

Key Papers

Orca: A Distributed Serving System for Transformer-Based Generative Models

Yu et al.2022OSDI
Read paper →

Efficient Memory Management for Large Language Model Serving with PagedAttention

Kwon et al.2023SOSP
Read paper →

DistServe: Disaggregating Prefill and Decoding for Goodput-optimized Large Language Model Serving

Zhong et al.2024OSDI
Read paper →

vAttention: Dynamic Memory Management for Serving LLMs without PagedAttention

Prabhu et al.2025ASPLOS
Read paper →

Connections

Prerequisites

AttentionEfficient AttentionSpeculative Decoding

Leads to

MoEMoE ServingLong ContextQuantization

Where to go next

A newer notebook covers LLM Serving, with an interactive demo.

Continue in the newer notebook
Other connections (7)

Which limitations does it address, or leave to a later idea?

  • Production serving: a limitation of Attention that LLM Serving addresses. Open Attention

    Running a transformer once is easy; serving thousands of users at once within latency targets is not. Serving techniques such as continuous batching, separating prompt processing from generation, and paged key-value caches were developed to make this practical (Kwon et al., 2023).

  • Latency reduction: a limitation of Speculative Decoding that LLM Serving addresses. Open Speculative Decoding

    Speculative decoding spends extra computation to cut latency: a small model drafts several tokens and the large model checks them all in one parallel pass. It keeps the large model's output distribution exactly and reduces the time per generated token; it does not speed up processing of the prompt (Leviathan et al., 2023).

Where does it break down?

  • KV cache dominates: where LLM Serving breaks down, taken up in Long Context. Open Long Context

    As prompts get longer, reading and storing the key-value cache dominates the cost of serving. That shrinks the batch sizes that fit in memory and lowers the number of requests served within latency targets; a system tuned for 4,000-token prompts can fail at 128,000.

  • Low acceptance: where Speculative Decoding breaks down, taken up on this page. Open Speculative Decoding

    Speculative decoding speedups rely on high draft-token acceptance. Under distribution shift, long contexts, or mismatched decoding settings, acceptance can drop and the method becomes neutral or even slower.

Where else does the same idea appear?

  • Scheduling under skew: an analogy between LLM Serving and MoE Serving. Open MoE Serving

    Both are scheduling problems under memory and latency constraints; MoE serving is like LLM serving with an extra routing-induced permutation and heavier tail-latency from skew.

  • Budget allocation: an analogy between LLM Serving and Scaling Laws. Open Scaling Laws

    Scaling laws ask how to divide a compute budget between model size and data for the lowest loss. Serving asks how to divide GPU memory and compute among users to serve the most requests within latency targets. Both are optimization under a fixed budget.

  • Blocked KV memory layout: the same technique appears in Efficient Attention. Open Efficient Attention

    Both split attention data into fixed-size blocks, for different reasons. FlashAttention tiles the computation so that each block fits in fast on-chip memory (Dao et al., 2022). PagedAttention stores the key-value cache in fixed-size blocks that need not be contiguous, so memory can be allocated as sequences grow without fragmentation (Kwon et al., 2023).