Serving many users at once

What happens when a thousand people open the chat in the same minute?

A payments company plans a festival cashback sale and will put its support bot on the home screen of its app. It expects ten times the usual number of chats.

Serving the model to one user is easy: the answer streams smoothly. Now picture a thousand people opening the chat in the same minute, all asking where their cashback went.

The obvious fix is to buy a faster GPU. But a GPU has two parts joined by a narrow link: a large memory that holds the weights, and arithmetic units that do the multiplying. Before you buy a faster one, you need to know which of the two it should be faster at.

Pause and predict When the GPU produces one token for one user, where does it spend most of its time?

So the useful question is how many conversations can share each pass through the weights, and how much longer each user waits because of the sharing.

That is a scheduling and memory problem: throughput against latency. Bigger batches make every token cheaper and every user slower. And the size of the batch is limited by memory, because every conversation in it needs its own KV cache.

The problem

From Inference you know that one request runs in two phases.

• Prefill pushes the whole prompt through the model in one parallel pass and fills the KV cache.
• Decode then produces one token per pass, one after another.

You also know the cache formula, per conversation: 2 × layers × kv_heads × head_dim × tokens × bytes.

That was one request. During a sale the server has many at once, arriving at random and with very different lengths. “Where is my cashback?” gets a two-line answer. “Explain every charge on my statement” gets a page.

Pause and predict Requests arrive at 8 per second, and the server handles them one at a time, in arrival order. What happens to the queue?

The problem

Requests in a batch do not finish together. One answer is 10 tokens long, another is 500.

The naive fix

Static batching, as in training: collect a full batch, run it until the longest sequence finishes, then start the next batch.

Why it fails

Finished sequences keep their slot and are padded until the longest one ends. New arrivals wait outside for the whole batch. In the simulator, 46,247 decode slot-steps are spent on padding, slot utilisation is 37%, and the median time to first token is 14.7 seconds.

The idea

Make the scheduling decision at every step, not every batch: a finished sequence leaves immediately and a waiting one takes its place.

The trade-off

The batch is no longer a tidy rectangle, so kernels and memory management must cope with sequences of different lengths. A newcomer’s prefill also interrupts everyone’s decoding.

One bottleneck, four consequences

Most of what follows will be familiar from backend work: queues, tail latency, bin packing, paging.

1. Two numbers: bandwidth for decode, arithmetic for prefill

Go back to the two parts of a GPU from the opening: a large memory that holds the weights, and arithmetic units that do the matrix multiplies.

Between them is the thin pipe: a link with a fixed speed, the memory bandwidth. On data-centre GPUs it runs from about 2 TB per second (an A100, 2020) to about 8 TB per second on the newest parts, such as NVIDIA’s B200 and B300 and AMD’s MI355X.

In a decode step every weight is needed once, so all of them cross that pipe. For one sequence the arithmetic is tiny: one token’s vector times each matrix. So the step takes as long as moving the bytes.

That gives the most useful rough estimate in serving.

Pause and predict A model has 14 GB of weights, and the GPU’s memory link moves 2 TB per second. At most, how many tokens per second can a single stream of generation get?

It is an upper bound. It ignores the KV cache reads, kernel overheads and sampling, and it assumes the whole model sits on one GPU. Real single-stream numbers are lower.

But it explains the order of magnitude, and it tells you what helps: more bandwidth, or fewer bytes. A faster arithmetic unit does nothing for it. So the faster GPU from the opening helps a single stream only if it moves bytes faster; more arithmetic speed does not help.

Prefill is the opposite. A 1,000-token prompt goes through in one pass. The weights are still read once, but now there is 1,000 times more arithmetic per byte read. So prefill is limited by arithmetic, once the prompt is longer than about 75 tokens on this GPU (the critical batch size, worked out further down). That is why the two phases get separate metrics.

2. The metrics you must keep apart

Time to first token (TTFT)

How long the user stares at nothing: time in the queue plus the prefill of their prompt.

For example: 40 ms waiting for a slot + 48 ms to prefill 500 tokens = a TTFT of 88 ms.

Report each latency as a distribution, not as an average. p50 is the median: half of your users were served faster than this. p99 is the slow tail: only one request in a hundred was worse. Output lengths are heavily skewed, so an average hides the users who suffer.

The two words in the last rows look alike. Throughput counts tokens. Goodput counts only the requests that met your promise about speed, an SLO or service level objective. A server can post an excellent throughput number while almost everyone waits too long.

3. Continuous batching: a scheduling decision at every step

Pause and predict A 10-token answer and a 500-token answer start in the same batch. With static batching, what does the short one’s slot do after step 10?

Continuous batching (iteration-level scheduling)

After every decode step, the scheduler looks again. Finished sequences leave. Waiting requests join if there is a slot and memory for them. The batch is a pool that changes all the time.

For example: A 10-token answer and a 500-token answer start together. After 10 steps the short one leaves and a queued request takes its slot. With static batching that slot would be padded for 490 more steps.

One wrinkle remains. When a new request joins, its prefill is a big arithmetic-bound pass, and while it runs, the sequences that were decoding produce nothing. A long prompt makes everyone’s stream stutter. Chunked prefill fixes that: split the prompt into chunks and run one chunk per step together with the ongoing decodes, which ride along almost for free (SARATHI, Agrawal et al., 2023; Sarathi-Serve, OSDI 2024, calls the result stall-free scheduling). Our simulator does not chunk, so you will see those stalls in the timeline.

Choosing who joins next is a priority queue: each step the scheduler pops the oldest, shortest or most urgent waiting request. That is the same structure as heaps and priority queues in Coding Patterns.

4. The KV cache is the real capacity limit

GPU memory = weights + KV caches + activations and workspace

The weights are fixed. Activations are small at inference. Whatever is left holds KV caches, and that decides how many sequences can run at once. So every byte of KV memory that is wasted makes the batch smaller, and a smaller batch means lower throughput.

The waste comes from not knowing the future. A request may generate up to its max_tokens, so early systems reserved one contiguous slab for the worst case. Most answers are short, so most of the slab was never written. The vLLM paper measured existing systems using only 20.4% to 38.2% of their KV memory for actual token states.

PagedAttention

Cut KV memory into small fixed-size blocks. A sequence gets a new block only when its last one is full, from anywhere in memory. A per-sequence block table maps “my 3rd block” to a physical block.

For example: Block size 16. A sequence holding 62 tokens owns 4 blocks, for example physical blocks 5, 6, 7 and 53. Only the last is partly empty: at most 15 token slots wasted per sequence.

That sharing, kept across requests, is prefix caching (vLLM calls it automatic prefix caching, SGLang’s version is RadixAttention). A long system prompt or a shared document is prefilled once, and later requests skip straight to their own suffix. It is what “prompt caching” on an API price list means. It cuts TTFT and prefill cost. It does not shorten a decode step, but shared blocks free KV memory, so more sequences fit in the batch.

When blocks run out mid-generation, the scheduler preempts a sequence: it frees its blocks and later recomputes them by prefilling again (older vLLM versions could swap them to CPU memory instead). Users see a pause, not an error. Current engines can also keep evicted blocks in a slower tier, CPU memory or local SSD, through connectors such as LMCache or Mooncake, so a returning conversation reloads its prefix instead of recomputing it. With many replicas, the router decides whether that prefix is found at all: send the next turn of a conversation to the replica that holds its blocks, or the cache sits unused on another machine.

The same scheduler, with real request traffic around it, is the subject of Design LLM serving in System Design.

The four points connect. Because the read of the weights is shared, the size of the batch decides what each token costs. KV memory limits how large the batch can grow. Continuous batching keeps the batch full, and paging fits more sequences into the same memory.

Capacity planning, by hand

Before a sale, whoever pays for the GPUs will ask two questions: how many users can one GPU serve, and what does a million tokens cost? Here is how to work both out.

Every input below is an assumption. Replace each one with your own.

Part 1: how many conversations fit?

It takes one subtraction and one division.

Pause and predict Before you read the table, guess: how many conversations fit on this one GPU at once?

Part 2: how fast, and how much?

Now run a decode step with all 328 on board, and add the prefills.

Three things are worth noticing.

• At a large batch, most of the bytes read are KV cache. In step 6 the average sequence holds 1,150 tokens, the prompt plus half the answer. Across 328 sequences the KV reads are three times the weight read.
• This batch sits where the two limits meet: they are nearly equal, 32.7 ms against 35.0 ms. Neither the memory link nor the arithmetic units are idle, which is exactly where the roofline says you want to be.
• Prefill is most of the bill. In step 8, three quarters of the GPU time per request goes on reading the prompt. And one stream alone would get at most 2 TB/s ÷ 16 GB = 125 tokens per second, so batching bought about 17 times the throughput.

Part 3: the promise to users

There is a catch in that ceiling. Prefills keep interrupting, so decode steps only get the GPU 24% of the time (34.7 of every 144.4 ms). Each user sees a token every 38.0 ÷ 0.24 = 158 ms, not every 38 ms.

If the company promises users a token at least every 50 ms, the ceiling of 6.9 requests per second cannot be used. The load that keeps the promise is 5.9 requests per second with 88 conversations in flight. The promise costs about 15% of the capacity, and the memory that could hold 328 conversations now holds 88.

Chunked prefill, or separate GPU pools for prefill and decode, exist to win that gap back. The algebra is below if you want it.

All of this is a napkin estimate. It ignores kernel efficiency at this batch shape and everything else a benchmark would reveal. Use it, and the simulator’s four-constant cost model, to see which resource binds and to sanity-check a vendor’s numbers, then measure your own workload before you order hardware.

The three answers together:

The math

Two small formulas carry the lesson. The first is the single-stream bound:

That “about 0.52 for int4” is the subject of the next lesson: storing each weight in fewer bytes raises this ceiling directly.

The second is the step time for a batch of B sequences. It is the roofline idea: a step lasts as long as the slower of moving bytes and doing arithmetic.

With B small the left term wins and hardly depends on B: batching is nearly free. As B grows, either ΣKV or B × 2N catches up with W, and from there each extra sequence costs real time. Throughput is B ÷ t_step, so it rises steeply and then flattens. Per-user latency is t_step, so it only ever gets worse.

Most of the economics of serving follows from these two formulas. Everything a serving engine does is an attempt to raise B without raising t_step, or to shrink W.

What you should remember

1. Decode is memory-bound, prefill is compute-bound. One stream gets at most bandwidth ÷ weight bytes tokens per second: about 143 for 14 GB on 2 TB/s. The arithmetic units are nearly idle.
2. Batching is nearly free because the weight read is shared, until KV reads or arithmetic catch up, or KV memory runs out. A bigger batch makes each token cheaper and each user slower. The batch is what you sell, and KV memory is what limits it: capacity planning is one subtraction (memory minus weights) and one division (what is left, by the cache per sequence).
3. Keep the metrics apart: TTFT (queue + prefill), TPOT (decode step + stalls), end-to-end, throughput, and goodput under an SLO, at p50 and p99.
4. Continuous batching reschedules at every step, so nobody pads and nobody waits for a whole batch. PagedAttention allocates the KV cache in blocks on demand, like virtual memory, so twice as many sequences fit and prefixes can be shared.

Where this appears in a real LLM

In this lesson

• A scheduler simulator with a four-constant cost model: no GPU, no model
• Prefill stalls every running sequence; no chunking
• Block allocator with counts and a 64-block picture
• One fixed model size and one fixed GPU

In a real system

• Engines measured on real traffic, with fused kernels for ragged batches and paged caches
• Chunked prefill, prefix caches, priorities, sometimes separate prefill and decode pools
• Tens of thousands of blocks, copy-on-write sharing, swapping to CPU memory
• Quantized weights and caches, and models spread over several GPUs

The engines you will meet, one line each:

The mechanisms in this lesson are published and open: iteration-level scheduling (Orca, OSDI 2022), PagedAttention (vLLM, SOSP 2023) and chunked prefill (Sarathi-Serve, OSDI 2024). That decode is limited by memory bandwidth and prefill by arithmetic follows from counting bytes and FLOPs, and you can verify it on any GPU by watching tokens per second as you change batch size.

A sensible plan for the sale fits on one slide: a serving engine with continuous batching and paged caches, a load test with real chat transcripts, and an alarm on the p99 time per token.

Every technique here filled the batch. The other half of serving is making each sequence cost fewer bytes, which is the next lesson: quantization, speculative decoding, and what to do when the model does not fit on one GPU at all.