Continuous batching and PagedAttention: serving many users from one GPU

One user on my box gets at most about 59 forward passes a second, because every pass reads 17 GB of weights (the decode note has the math). Serving ten users doesn’t need ten times the bandwidth. That’s the whole case for batching, and also where its limits come from.

Why batching is almost free

A decode step reads the weights once whether it computes one sequence or sixteen. Put B sequences in the same pass and they all share that read. Total throughput grows with B until the arithmetic catches up with the memory traffic.

With rough assumptions (54 GFLOP per token, half of the card’s tensor throughput usable, weights only):

Batch	Pass time	Total tokens/s
1	16.9 ms	59
8	16.9 ms	474
16	16.9 ms	949
26	17.0 ms	1,528
32	21.0 ms	1,528
64	41.9 ms	1,528

Up to about 26 sequences, the pass doesn’t get slower: each user keeps their single-stream speed while the server does 26× the work. Past that point the pass becomes compute-bound, total throughput flattens, and each user’s speed starts to fall.

The table leaves out one thing that matters: every sequence’s attention reads its own KV cache. Long contexts add bytes per sequence, so the real crossover comes earlier.

Memory, not compute, caps the batch

Each sequence needs its own KV cache. After the 17 GB of weights, a 24 GB card has roughly 7 GiB left for cache. That’s a hard cap on how many tokens can be in flight at once (the per-token sizes are in the KV cache note):

Cache format	Tokens that fit	At 8K each	At 32K each
FP16	~115K	14 sequences	3
Q8_0	~216K	26 sequences	6
TBQ4, 4-bit	~445K	54 sequences	13

So a quantised cache doesn’t just let one user have a longer context. It’s often the difference between 14 concurrent users and 54.

Static batching wastes the GPU

The naive server collects a batch, runs it to completion and starts the next. Sequences finish at different lengths, so short ones sit idle as padding until the longest is done, and new requests wait for the whole batch.

Continuous batching (Orca, Yu et al., 2022) schedules per decode step instead. Finished sequences leave after any step and waiting requests join at the next. The batch stays full and nobody waits for a stranger’s long answer. Every serious server does this now. llama.cpp’s server runs parallel slots (-np) with continuous batching on by default.

Fragmentation: PagedAttention

The second waste is memory. A server that reserves a contiguous cache region for each sequence’s maximum length wastes whatever isn’t used. Reserve 32K for a request that ends at 2K and 94% of that region sat empty.

PagedAttention (Kwon et al., 2023, the core of vLLM) borrows virtual memory from operating systems:

• the cache is stored in fixed-size blocks of 16 tokens;
• each sequence has a block table mapping its logical positions to physical blocks;
• a sequence only wastes the unfilled part of its last block.

The paper reports existing systems using only 20–38% of their KV memory for actual tokens, against under 4% waste with paging. Blocks also make sharing cheap. Parallel samples of the same prompt, or requests with a common prefix, can point at the same physical blocks until they diverge, which is the basis of prefix caching.

Prefill gets in the way

A new request’s prompt has to be prefilled, which is a big compute-bound pass. Run a 100K-token prefill in one go and every decoding user stalls until it finishes. Chunked prefill splits the prompt into pieces and interleaves them with decode steps. The newcomer’s first token arrives a bit later, and everyone else keeps streaming.

Rules I use

1. Decide what you’re optimising. Throughput and per-user latency trade against each other past the crossover, so pick the batch size from your latency target, not the other way round.
2. Quantise the cache before adding GPUs. On one card it’s the cheapest way to raise concurrency.
3. Turn on chunked prefill if you serve long prompts to more than one user.
4. Measure with realistic context lengths. A load test with 500-token prompts says little about a 50K-token agent session.

Sources: Yu et al., Orca (OSDI 2022). Kwon et al., Efficient Memory Management for Large Language Model Serving with PagedAttention (SOSP 2023). The throughput table is a model, not a measurement: 54 GFLOP per token, 50% of ~165 TFLOPS, 1,008 GB/s, weights-only traffic.