Continuous batching and paged attention

Continuous batching refills the batch every iteration; paged attention allocates cache memory in small blocks on demand. Each needs the other to keep both slots and memory full.

Early LLM serving systems batched requests the way a training system does: collect a set, run them to completion together, return the results. Throughput per GPU was poor and latency was unpredictable. Two changes, one to scheduling and one to memory management, are responsible for most of the improvement since.

Static batching and its cost

In a static batch, all sequences start together and the batch runs until the longest one finishes. A sequence that generates 20 tokens sits idle for the remaining steps while a neighbour generates 800. New requests wait for the whole batch to drain. Effective utilisation depends on how similar the sequence lengths happen to be, and in production they are not similar.

Continuous batching

Continuous batching (also called iteration-level scheduling, introduced in the Orca paper) makes the batch membership change every step. After each decode iteration, the scheduler removes sequences that have finished and admits waiting sequences into the freed slots. A batch of 32 slots stays full as long as there is demand, regardless of how long individual sequences run.

Consequences:

• Throughput rises several-fold because slots are no longer wasted on finished sequences.
• Time to first token drops because a new request waits for the next iteration, a few milliseconds, rather than for a batch to drain.
• Prefill and decode mix in one batch. A new sequence's prefill runs alongside other sequences' decode steps. Without care, a long prefill stretches that iteration for everyone; chunked prefill splits the prompt across iterations to bound the effect.

The scheduler now has a decision to make every few milliseconds: which waiting sequences to admit, given the memory available. That decision is only tractable if memory allocation is flexible, which is where the second technique comes in.

The memory problem

Each sequence's KV cache grows by one token per step, and its final length is unknown at admission. The pre-2023 approach reserved a contiguous region sized for the maximum length. A request with a 2,048-token limit reserved 2,048 tokens of cache and might use 100. Reserved-but-unused memory, plus fragmentation between regions of different sizes, left 60 to 80 percent of cache memory unusable. Since the cache is what limits batch size, this capped continuous batching's benefit.

Paged attention

PagedAttention, introduced by vLLM, applies virtual memory ideas to the cache. The cache is divided into fixed-size physical blocks, commonly 16 tokens each. Each sequence has a block table mapping its logical token positions to physical blocks. Blocks are allocated one at a time as the sequence grows and freed when it finishes.

Effects:

• Waste is bounded by one partial block per sequence, so utilisation exceeds 90 percent.
• Blocks need not be contiguous, so fragmentation disappears.
• Two sequences can reference the same physical block. A shared prompt prefix is stored once (prefix caching). Parallel sampling from one prompt shares the prompt's blocks with copy-on-write for the divergent part.
• Admission becomes a simple question: are there enough free blocks for this sequence's prompt, plus a margin for generation?

The attention kernel is modified to gather keys and values through the block table rather than from a contiguous buffer. The overhead is small relative to the utilisation gain.

Why they depend on each other

Continuous batching without paged allocation fills its slots but runs out of cache memory early, because each admitted sequence reserves far more than it uses. Paged allocation without continuous batching packs memory efficiently but leaves slots idle between batches. Together, the scheduler can admit whenever blocks are free and free blocks the moment a sequence ends, which keeps both slots and memory near full.

Every current serving engine implements both. The differences between engines are in the details: block size, pre-emption policy when blocks run out (recompute versus swap to host memory), chunked prefill scheduling, and how prefix sharing is indexed.

Operational implications

• Pre-emptions in the metrics mean the block pool ran out. The remedy is memory, shorter contexts, or fewer concurrent sequences, not scheduler tuning.
• max_num_batched_tokens (or the engine's equivalent) bounds the work per iteration and is the main lever between throughput and time per token.
• Block utilisation is the capacity metric for a replica. GPU utilisation is not.

Summary

Continuous batching keeps the batch full by changing membership every iteration. Paged attention keeps memory full by allocating the cache in small blocks on demand. Each technique needs the other to reach its potential, and together they are the baseline that every serving engine now starts from.