Continuous batching, paged attention, prefix caching

Why it matters

Decode reads the whole model out of memory to produce one token. A server that does that for one request at a time wastes almost all of the accelerator, because the arithmetic for a single token is a sliver of what the chip can do while the weights stream past. Everything that makes self-hosted inference affordable comes from reading the weights once and producing tokens for many requests at the same time, and everything that makes that hard comes from the KV cache, which every request needs and which does not fit for very many of them. Interviewers ask about batching and the cache because they are the difference between ten requests a second and a thousand on the same hardware, and because prefix caching is the reason prompt layout became a performance concern.

The idea

Static versus continuous batching

Static batching groups a fixed set of requests, runs them in lockstep and returns when the longest finishes. Short answers sit idle inside the batch waiting for long ones, padding wastes compute, and nothing new can start until the group ends. It is simple, and it is how most people first imagine batching.

Continuous batching schedules at the level of the decode step instead of the request. After every step the scheduler looks again: finished requests leave and free their cache, waiting requests are admitted, their prefill runs, and the next step proceeds with the new membership. The batch is a rolling population rather than a group. Utilisation stays high because the accelerator is never waiting on the slowest member, and time to first token stays low because arrivals do not wait for a batch to drain.

step 1: [A] [B]          C arrives; its prefill runs between steps
step 2: [A] [B] [C]      C joined without waiting for A or B
step 3: [A]     [C]      B finished; its cache blocks return to the pool
step 4: [A] [D] [C]      D took the blocks B released

Paged attention

The obstacle to a large rolling batch is memory. The naive allocator reserves a contiguous region for each request sized to its maximum possible length, so a request that was allowed 4,000 output tokens and produced 200 held 3,800 tokens of cache that nobody could use, and the gaps between regions were too small for anyone else. Most of the accelerator's memory was reserved and empty.

Paged attention borrows the operating system's answer. The KV cache is divided into fixed-size blocks of a few dozen tokens each. A request owns a block table mapping its logical positions to physical blocks, and a new block is allocated only when the current one fills. Waste falls to less than one block per request, fragmentation disappears, and the same memory holds several times as many concurrent requests. The attention kernel follows the table to find each token's keys and values, which is where the name comes from.

Prefix caching

Once the cache is made of blocks, blocks can be shared. Two requests whose first 30,000 tokens are identical produce identical keys and values for them, so the server keeps one physical copy and points both block tables at it. Prefix caching hashes each block together with the blocks before it; a new request whose leading blocks match an entry already in memory skips their prefill entirely and starts decoding from the first token that differs. Blocks are reference counted and evicted least-recently-used when memory is needed.

This is why the system prompt, the tool definitions and the few-shot examples must come first and the user's turn last: sharing works on a prefix, and the first differing token ends it. It is also the mechanism behind the prompt-caching discount on the API price list.

KV-cache-aware routing

A fleet of replicas each has its own cache. A plain round-robin balancer scatters one tenant's requests across all of them, so every replica builds and holds its own copy of the same prefix, and the hit rate on any one of them is a fraction of what it could be. KV-cache-aware routing sends a request to the replica that already holds its prefix: the router hashes the leading blocks, keeps a map of which replica cached what, and falls back to the least-loaded replica on a miss. Stickiness is by prefix, not by user, so a tenant with one system prompt and a million users still lands on a warm cache. The cost is load skew, which the router bounds by moving a hot prefix to a second replica when the first saturates.

Throughput against latency

A larger batch produces more tokens a second in total and fewer tokens a second for each member, because every step now reads more cache and does more arithmetic. Prefill for new arrivals also competes with decode for everyone already running; chunked prefill splits a long prompt into pieces interleaved with decode steps so one 100,000-token arrival does not freeze the batch. A serving engine exposes the knobs as limits: maximum sequences in flight, maximum tokens per step, memory reserved for cache. The two numbers to watch are time to first token and inter-token latency at the tail; the number to maximise is tokens a second per accelerator. vLLM and SGLang are the reference open-source servers implementing all of the above, and most managed inference products run something descended from them.