How LLM inference is served: prefill and decode, time to first token and time per output token, batching and scheduling, and why KV-cache memory often limits batch size.
The idea in plain words, before the symbols.
Serving an LLM is not "run the model once". It means running the model for many users at once while keeping each user's wait short and the GPUs busy.
Generating a response has two phases with different costs:
Batching helps decode because the weights are read once per step and shared by every sequence in the batch. The KV cache cannot be shared that way: each sequence has its own. At small batches and short contexts, reading the weights dominates each step; at large batches and long contexts, reading the KV caches does (Pope et al., 2023, §2). Long contexts therefore slow every decode step, and because each sequence's cache must stay in memory, they also limit how many sequences fit in a batch. The KV cache becomes the main resource a serving system schedules around (Kwon et al., 2023).
Continuous batching keeps the GPU busy. A static batch waits until its longest request finishes; with iteration-level scheduling the server re-forms the batch at every decode step, admitting new requests and retiring finished ones (Yu et al., 2022).
Throughput alone is the wrong target if requests wait too long. Serving systems set latency targets, called service-level objectives (SLOs), for the time to the first token and the time per later token, and measure goodput: the rate of requests that meet those targets (Zhong et al., 2024).
Each button copies a prompt about this section to your clipboard, for an AI assistant you already use. Nothing is sent by this site.
Definitions, assumptions and the derivation.
Let be the number of generated tokens. A simple decomposition is:
Across a batch of sequences and layers, with key-value heads of dimension , storing keys and values for tokens costs roughly:
The factor of 2 is for storing both and , and "bytes" is the size of one element (2 for fp16). Every decode step reads this whole cache, so for long contexts and large batches it sets both the memory needed and much of the time per step.
If the latency targets are and , one simple definition counts only the requests that meet both:
A system that is fast on average can still have low goodput if many requests miss a target. DistServe (Zhong et al., 2024) reports goodput as the highest request rate at which a chosen share of requests, such as 90%, meets both targets.
If KV memory is allocated in blocks of tokens, then for a sequence length :
With blocks, at most token slots per sequence are wasted, in its last block. Reserving one contiguous region per request for the longest possible output wastes far more. PagedAttention allocates blocks on demand, like pages of virtual memory, which lets more sequences share the GPU under continuous batching (Kwon et al., 2023).
Continuous batching is easiest to see by counting rounds. Take sequence slots and four requests that still owe , , and output tokens, queued as A, B, C, D. One decode round gives every active request one token. If a schedule takes rounds, it offers slot-rounds; the requests use of them, where is what request owes, and
With fixed batches, A and B hold both slots until B finishes, then C and D do the same. The rounds have active requests: , slot-rounds are idle, and the utilization is . With refill, a slot freed at the end of a round goes to the next request in the queue. The rounds hold (A, B), (B, C), (B, D), (B, D), (D), (D): , slot-rounds are idle, and the utilization is . C no longer waits for B.
Refill does not always save rounds. Queue the same requests as B, D, A, C: both rules run B and D together for four rounds and A and C for one, with no idle slot. Requests of equal length that start together leave nothing to refill. Over all 24 orders of these four requests, fixed batches take 5 or 8 rounds and refill takes 5 or 6.
The counts assume every decode round costs the same, and they leave out prefill, KV-cache reads and the scheduler's own work, so they are not latencies or measured throughput. The refill rule is Orca's iteration-level scheduling (Yu et al., 2022); the requests and the numbers are this page's example.
Each button copies a prompt about this section to your clipboard, for an AI assistant you already use. Nothing is sent by this site.
The same calculation as runnable code, in the notation of the derivation.
import numpy as np
def kv_gb(T, layers, h_kv, d_head, batch=1, bytes_per_elem=2):
elems = batch * layers * T * h_kv * d_head * 2 # K and V
return elems * bytes_per_elem / 1e9
def waste_tokens(T, b):
return int(np.ceil(T / b) * b - T)
L, Hkv, dh, B = 80, 8, 128, 16 # example: 80 layers, grouped-query attention with 8 KV heads, fp16
for T in [2048, 8192, 32768, 131072]:
print("T=", T, "KV~", round(kv_gb(T, L, Hkv, dh, batch=B), 2), "GB")
b = 256 # tokens per block
for T in [2000, 8192, 20000]:
print("T=", T, "waste_tokens=", waste_tokens(T, b))
This standard-library Python code counts the rounds, idle slot-rounds and utilization of both rules for both queue orders above. It counts rounds; it does not time anything.
SLOTS = 2
QUEUE = (("A", 1), ("B", 4), ("C", 1), ("D", 4))
REORDERED = (("B", 4), ("D", 4), ("A", 1), ("C", 1))
def schedule(queue, rule, slots=SLOTS):
"""Each round gives every active request one token; returns rounds, idle, utilization."""
position = {name: i for i, (name, _) in enumerate(queue)}
rounds = []
def run(active):
active = sorted(active, key=lambda request: position[request[0]])
rounds.append(tuple(name for name, _ in active))
return [(name, left - 1) for name, left in active if left > 1]
if rule == "fixed":
for start in range(0, len(queue), slots):
batch = list(queue[start:start + slots])
while batch: # the batch keeps its slots until all finish
batch = run(batch)
elif rule == "refill":
waiting = list(queue)
active = [waiting.pop(0) for _ in range(min(slots, len(waiting)))]
while active:
active = run(active)
while len(active) < slots and waiting: # refill freed slots
active.append(waiting.pop(0))
else:
raise ValueError(rule)
busy = sum(steps for _, steps in queue)
offered = slots * len(rounds)
return rounds, offered - busy, busy / offered
fixed = schedule(QUEUE, "fixed")
refill = schedule(QUEUE, "refill")
assert [len(r) for r in fixed[0]] == [2, 1, 1, 1, 2, 1, 1, 1]
assert fixed[1:] == (6, 10 / 16)
assert refill[0] == [("A", "B"), ("B", "C"), ("B", "D"), ("B", "D"), ("D",), ("D",)]
assert refill[1:] == (2, 10 / 12)
for label, queue in (("A, B, C, D", QUEUE), ("B, D, A, C", REORDERED)):
for rule in ("fixed", "refill"):
rounds, idle, utilization = schedule(queue, rule)
print(f"{label} {rule:6} rounds={len(rounds)} idle={idle} utilization={utilization:.3f}")
Each button copies a prompt about this section to your clipboard, for an AI assistant you already use. Nothing is sent by this site.
Change an input, predict the result, and see which quantities respond.
Optional and ungraded. Opening a guide saves nothing.
Choose what to inspect in LLM Serving at Scale: Prefill, Decode & Continuous Batching, then open its guide.
The demo is a toy latency calculator with illustrative numbers, not a benchmark. For prompt length (in tokens), output length and batch size it computes ms and ms per output token, then the decomposition above, , with the first output token counted in TTFT. The term stands in for the per-step KV-cache reads, and the batch size is one fixed number, not a scheduler.
Each phase challenge states its fixed inputs and its rule before you answer, and the calculator stays open while you do. A phase dominates when it is more than 55% of the modelled total; about equal means each phase is 45–55%. The doubled-batch challenge compares growth in milliseconds, not percentage growth. The coloured summary line uses separate 30%/70% bands and is not a grade. The workload cards show rough indicators that the latency numbers do not use.
The calculator models one request. It has no stream of requests, queue or throughput, so it cannot compute goodput; you can compare its TTFT and TPOT with a target you choose. The demo does not use the KV-memory and paging formulas; the code above computes them. The practice after the demo counts a small queue of requests under fixed batches and refill.
Each button copies a prompt about this section to your clipboard, for an AI assistant you already use. Nothing is sent by this site.
Count decode rounds for four queued requests under fixed batches and under refill, then reorder the queue and count again.
What is the smallest example of LLM Serving at Scale you can work through by hand, and what does it show?
concept:llm-systems/llm-servingAfter the first pass
Section by section
How LLM inference is served: prefill and decode, time to first token and time per output token, batching and scheduling, and why KV-cache memory often limits batch size.
Choose what you expect to see in this section of LLM Serving at Scale: Prefill, Decode & Continuous Batching.
Looking at the picture
How LLM inference is served: prefill and decode, time to first token and time per output token, batching and scheduling, and why KV-cache memory often limits batch size.
Pick the part of the picture you expect to explain LLM Serving at Scale: Prefill, Decode & Continuous Batching.
Sources
Treats generative transformer serving as many iterations, each producing one output token per request, and introduces iteration-level scheduling, which re-forms the batch at every iteration, together with selective batching (OSDI 2022).
Shows that the large, dynamically growing KV cache wastes memory through fragmentation and over-reservation, limiting batch size; PagedAttention stores it in fixed-size blocks like virtual-memory pages, and vLLM builds on it (SOSP 2023).
Models inference cost: each step moves the weights and KV cache from memory; loading weights dominates at small batches and short sequences, loading the KV cache at large batches and long sequences (§2) (MLSys 2023).
Defines time to first token (TTFT) and time per output token (TPOT), measures goodput as the highest request rate at which a target share of requests meets both targets, and splits prefill and decode across GPUs (OSDI 2024).
Claims and sources
The checks were made by this site, not by an independent reviewer.
Orca supports the scheduling part: generative Transformer serving is multi-iteration autoregressive inference with one output token per iteration, and fixed request-level batches motivate iteration-level sch...
This covers the serving mechanism. TTFT and TPOT follow DistServe; the goodput formula is a simpler version of its definition, and the KV-memory formula is a standard count. The demo's coefficients are illus...
Orca supports autoregressive transformer serving as many iterations that each emit one token, which motivates iteration-level scheduling and selective batching because fixed request-level batches waste capacity. PagedAttention supports the KV cache as large, dynamic, fragmentation-prone memory that can limit batch size and throughput.
Practice · LLM Serving at Scale: Prefill, Decode & Continuous Batching
How LLM inference is served: prefill and decode, time to first token and time per output token, batching and scheduling, and why KV-cache memory often limits batch size.
Concept · Selected for practice
What it rests on: Sources: Orca: A Distributed Serving System for Transformer-Based Generative Models; Efficient Memory Management for Large Language Model Serving w...
LLM Systems
For LLM Serving at Scale: Prefill, Decode & Continuous Batching: What is the smallest example of LLM Serving at Scale you can work through by hand, and what does it show? Explain your answer, including what changes, why, and which assumption matters.
A rough first thought is enough. Your draft stays when you change tasks.
Your draft stays on this page and is cleared when you leave or reload.
Open one hint at a time. These are suggestions, not your answer or a grade.
0 of 3 hints shown for this question.
Clearing your answer keeps this help record. Outside help is your own report; this page cannot check it.
No AI feedback runs here. You can copy a prompt to use elsewhere; nothing is sent automatically. Review the text before sharing, and leave out private information.
Write an attempt before copying a feedback prompt.
A draft, or an AI reply to it, is not a test of what you have learned. To check that, try a different case later without help.
assert [len(r) for r in fixed[0]] == [2, 1, 1, 1, 2, 1, 1, 1]Your question
Open the draft below to save one note and next action in this browser.
What is the smallest example of LLM Serving at Scale you can work through by hand, and what does it show?
Fixed prompts generated from this item. They are not comments from people or independent reviews.
The 4 cited sources must support this exact item, not just the surrounding topic.
Connect the definition to one equation, piece of code or demo before widening the discussion.
Change one input, then check that the same relationship holds in the mathematics, the code and the demo.
You can state the mechanism in your own words
This draft stays in this browser and is attached to this item only.
concept/concept-notebook/llm-systems/llm-serving
concept:llm-systems/llm-serving