Batching and PagedAttention

The big idea

A server batches 8 requests. One asks for a 10-token answer, another for 500. With the simplest kind of batching, the short request finishes after 10 steps and its slot then sits empty for 490 more, because the batch only ends when its longest member does. New requests wait in the queue the whole time, while the GPU does a step's worth of work for a slot nobody is using.

Think of a tour bus versus a city bus. The tour bus leaves with a full load and returns only when the last passenger is back, so seats stay empty while a queue forms at the depot. A city bus lets people off and on at every stop, so empty seats fill almost immediately. LLM servers switched from tour buses to city buses, and that alone multiplied their throughput.

The second half of the story is memory. Letting requests come and go at every step only helps if their KV caches can come and go too, without leaving holes. PagedAttention borrows the operating system's answer to that problem: split memory into small fixed-size pages and keep a table of where each request's pages live.

How it works

Static batching

Static batchingGrouping requests into a batch that runs until every member has finished, then starting the next batch. Simple, but slots of finished requests sit idle. is what you get from a plain "collect N requests, run them, return the results" loop. It works well when every request does the same amount of work, as in image classification. Text generation breaks that assumption: output lengths vary from a few tokens to thousands. Three things go wrong at once:

• Idle slots: a finished request's slot does nothing until the longest request ends.
• Late returns: a request that finished early cannot return its answer until the batch is done (unless the server streams).
• Queueing: new arrivals wait for a whole batch to drain, which hurts time to first token.

Continuous batching

Continuous batchingScheduling at the granularity of single decode steps: after every step, finished requests leave the batch and waiting requests join it. Also called iteration-level scheduling or in-flight batching. moves the scheduling decision from "per batch" to "per step". After every decode step the scheduler removes finished sequences, returns them immediately, and admits waiting requests into the freed slots, as long as their KV cache fits.

A newly admitted request first needs its prefill, while the others are mid-decode. One step can mix both: the non-attention layers (the big matrix multiplications) process all tokens from all requests stacked together, while attention runs per request because each has its own cache and length. The Orca paper called this selective batching. Very long prompts are often split into chunks across several steps (chunked prefill), so one big prefill does not stall everyone else's next token.

KV cache fragmentation

Continuous batching keeps the slots busy, but the number of slots is set by memory ( GPU memory math ). Early servers stored each request's KV cache in one contiguous chunk sized for the maximum length it might reach, because they could not know in advance when it would stop. That wastes memory three ways:

• Reserved: space for tokens not generated yet. It will be used eventually, but it blocks other requests for the whole lifetime of this one.
• Internal fragmentation: space reserved for a maximum the request never reaches.
• External fragmentation: gaps between chunks of different sizes, too small for a new request.

In the PagedAttention paper's measurements, only 20.4 to 38.2 percent of the KV cache memory in such systems held actual token states. The rest was waste, and waste means a smaller batch.

PagedAttention

PagedAttentionAn attention algorithm that stores each request's KV cache in fixed-size blocks anywhere in GPU memory, found through a per-request block table, like pages in an operating system's virtual memory., introduced with the vLLM serving engine, applies operating-system paging to the KV cache. Think of blocks as pages, tokens as bytes and requests as processes:

1. GPU memory for the cache is divided into equal physical blocks, each holding the keys and values of a fixed number of tokens (16 tokens by default in the original vLLM).
2. Each request sees a sequence of logical blocks, filled left to right. A block table maps each logical block to whichever physical block holds it.
3. Blocks are allocated on demand, one at a time as tokens arrive. Nothing is reserved for a maximum length.
4. The attention kernel follows the block table to gather keys and values from scattered blocks.

The waste is now at most one partly filled block per request, and since all blocks have the same size, there is no external fragmentation at all. The vLLM team reported a waste of under 4 percent.

Sharing blocks

Because the table is an indirection, two sequences can point at the same physical block. When a request asks for several samples of the same prompt, or for beam search, the prompt's blocks are stored once with a reference count, and a block is copied only when one sequence needs to write to it (copy-on-writeSharing one copy of data between several users until one of them needs to modify it, at which point that user gets a private copy., the same trick operating systems use when forking a process). Requests that share a system prompt can share its blocks too, which is the basis of prefix caching.

When blocks run out

With on-demand allocation, a batch can outgrow memory mid-generation. vLLM serves requests first come, first served, and when it must preempt, it evicts the most recently arrived requests first. A preempted request's blocks are either swapped out to CPU memory or freed and recomputed later from the tokens so far. All blocks of a sequence are evicted together, since attention needs all of them at every step.

Try it

1. With the defaults (4 slots, mixed lengths), compare the two timelines. Where do the static gaps come from, and how much sooner does the average request finish with continuous batching?
2. Switch to similar lengths. Why does continuous batching barely help now?
3. Press "New requests" a few times. The continuous timeline also has gaps at the very end. What causes them, and why would a busy production server rarely see them?

How much memory does on-demand allocation save? A toy KV cache with room for 32,768 tokens, a maximum request length of 4,096 and mostly short requests:

# Contiguous KV reservation vs paged blocks. Memory is counted in token slots.
import random

random.seed(7)
CAPACITY = 32_768    # token slots of KV cache memory on the GPU
MAX_LEN = 4_096      # longest request the server allows
BLOCK = 16           # tokens per KV block

# final lengths (prompt + output) of a stream of requests, mostly short
lengths = [min(MAX_LEN, int(random.expovariate(1 / 600)) + 50) for _ in range(200)]

def admit(cost):
    """Admit requests in order until the next one does not fit."""
    used, n = 0, 0
    for length in lengths:
        if used + cost(length) > CAPACITY:
            break
        used, n = used + cost(length), n + 1
    real = sum(lengths[:n])
    return n, used, real

schemes = {
    "contiguous, reserve max": lambda L: MAX_LEN,
    "paged, 16-token blocks": lambda L: -(-L // BLOCK) * BLOCK,  # round up
}
for name, cost in schemes.items():
    n, used, real = admit(cost)
    print(f"{name:<24} {n:>3} requests at once, "
          f"{real / used:6.1%} of reserved slots hold real tokens")

wasted = sum(-(-L // BLOCK) * BLOCK - L for L in lengths)
print(f"\npaged waste is only the unfilled tail of each last block: "
      f"{wasted / len(lengths):.1f} slots per request on average")

contiguous, reserve max    8 requests at once,   7.9% of reserved slots hold real tokens
paged, 16-token blocks    60 requests at once,  98.6% of reserved slots hold real tokens

paged waste is only the unfilled tail of each last block: 7.7 slots per request on average

Reserving the maximum per request admits 8 requests, and under 8 percent of the reserved memory holds real tokens. Paging admits 60, because a request only ever holds the blocks it has filled. The exact numbers depend on the length distribution; the PagedAttention paper measured 20.4 to 38.2 percent of cache memory in real use for earlier systems.

Going deeper

Choosing the block size

Bigger blocks let the attention kernel read more keys and values per block in parallel, which uses the hardware better. Smaller blocks waste less in the last, partly filled block. The PagedAttention authors found that 16 tokens was large enough to use the GPU efficiently and small enough to avoid significant internal fragmentation in most workloads, and made it vLLM's default.

The indirection has a cost

Following a block table, branching and handling variable lengths makes the attention kernel itself slower. The paper measured 20 to 26 percent higher attention kernel latency than a highly optimized contiguous implementation. That cost touches only the attention operator, not the large matrix multiplications, and the much bigger batches more than pay for it.

Scheduling is a policy, not just a mechanism

Continuous batching decides when a request can join; the scheduler still decides which one. First come, first served is fair and prevents starvation. Serving engines add knobs on top, such as a cap on the tokens processed per step, which bounds how much prefill work any one step can absorb and so keeps time per output token steady for requests already decoding.

Trade-offs

Common mistakes

• Benchmarking a server with identical request lengths, which hides exactly the problem continuous batching solves.
• Assuming that continuous batching alone raises capacity, when the KV cache memory still caps how many requests can join.
• Sizing a deployment with the maximum context per request when actual lengths are much shorter, or the reverse: ignoring that a few long requests can trigger preemption for everyone.
• Treating a rise in latency under load as a model problem, when it is preemption or queueing.

In the wild

Check yourself

Recap