What problem does PagedAttention solve, and what is continuous batching?

How to think about it

Short answer

PagedAttention solves a GPU-memory allocation problem in LLM serving: the KV cache grows one token at a time, but traditional contiguous allocation wastes memory and becomes fragmented when requests have different lengths. Continuous batching solves a scheduling problem: it adds and removes requests between generation iterations, so short requests do not leave idle batch slots while a long request continues.

They are complementary, not interchangeable. PagedAttention manages where the cache lives; continuous batching manages which requests the GPU works on next.

Why the KV cache becomes the problem

An LLM generates text autoregressively, meaning it produces one token, then uses that token to help produce the next. A KV cache, short for key-value cache, stores the attention keys and values already computed for each request. Without it, the model would repeatedly recompute the entire prompt and all previous output on every new token.

There are two important phases. Prefill is the first pass over the input prompt. Decode is the one-token-at-a-time generation phase. Prefill is usually compute-heavy. Decode repeatedly reads the existing KV cache and appends a small amount of new data, so it is often limited by memory bandwidth and cache capacity.

The cache belongs to the request, not just to the model. A request with a 200-token prompt and a 4,000-token conversation needs much less cache than a request with an 8,000-token context. Requests also finish at different times.

A simple allocator has an awkward choice. It can reserve a large contiguous buffer for every request, perhaps enough for the configured maximum context length. That is predictable but wasteful. Or it can grow each buffer as tokens arrive, which may require finding a new larger region and copying the old cache.

The result is wasted memory in two forms:

• Over-reservation: space is held for tokens the request never generates.
• External fragmentation: free memory exists, but it is split into holes rather than one sufficiently large contiguous region.

That second case is particularly unpleasant. The GPU can report plenty of free memory while the server still cannot admit another request.

How PagedAttention works

PagedAttention borrows the core idea of virtual memory from operating systems, but its “pages” are fixed-size blocks in GPU memory. It does not normally page KV data to disk. That would be a very different performance story.

Suppose a block holds 16 tokens. A request with 50 tokens needs four logical blocks: three full blocks and one block containing two tokens. Those physical blocks do not need to sit next to one another in GPU memory.

The serving system maintains a block table, which maps a request’s logical block number to a physical GPU block. The attention kernel follows that table when it reads keys and values. A request may therefore use physical blocks 12, 87, 301, and 44 while still representing positions 0 through 49 in the correct order.

This fixed-block design has two benefits:

1. The allocator can take any free block, so it does not need one large contiguous region.
2. The final partially filled block wastes at most the unused space in one block, rather than reserving the full maximum context.

PagedAttention can also allow physical blocks to be shared. Beam-search candidates, for example, may have an identical prefix. Instead of copying that prefix’s KV cache for every candidate, the candidates can reference the same blocks. When one candidate diverges, copy-on-write creates a private block for the changed portion. Prefix caching can use a similar idea when the serving system supports it.

Common misconception: PagedAttention is not compression. It does not, by itself, reduce the number of bytes required per cached token. It changes the layout and allocation strategy. Grouped-query attention, KV-cache quantization, shorter contexts, and model architecture changes address the bytes-per-token problem.

A concrete memory example

Consider an illustrative model with:

• 32 transformer layers
• 8 KV heads
• head dimension 128
• FP16 keys and values

The raw KV memory per token is:

2 × 32 × 8 × 128 × 2 bytes = 131,072 bytes

That is 128 KiB per token, where the factor of 2 at the start accounts for keys and values.

Now four requests are active:

Request	Live tokens	16-token blocks	Allocated KV
A	3,900	244	488 MiB
B	420	27	54 MiB
C	2,100	132	264 MiB
D	70	5	10 MiB
Total	6,490	408	816 MiB

The live data itself occupies about 811.25 MiB. The extra 4.75 MiB is the tail space caused by rounding each request up to a whole 16-token block, ignoring metadata and alignment.

With a conventional design that reserves 4,096 tokens for every request, each request would receive 512 MiB. Four requests would reserve 2 GiB even though their actual caches need only about 811 MiB. PagedAttention lets the allocator hand out the 408 blocks wherever free space exists. When request B finishes, its 27 blocks return to the pool immediately and can be used by a new request.

The block size is a real engineering trade-off. Smaller blocks reduce tail waste and make sharing more precise, but increase block-table entries and bookkeeping. Larger blocks reduce metadata overhead but waste more space when requests end at awkward lengths.

What continuous batching changes

Traditional static batching groups requests together, runs generation until the batch is finished, and then starts another batch. That works tolerably for equal-length jobs. LLM requests are rarely equal-length jobs.

Use the same requests. Suppose A generates 2 new tokens, B generates 8, and C generates 20. In a static batch, the server continues launching work for all three through 20 iterations. A and B have already finished, so their rows contribute no useful generation during most of those iterations.

With continuous batching, often called iteration-level batching, the scheduler checks the active requests at each generation boundary. A leaves after iteration 2. B leaves after iteration 8. A queued request E can take a newly available slot after its prompt prefill has been scheduled. Its KV blocks are allocated from the same pool.

The GPU is still executing batches. The difference is that the membership of the batch changes while the workload is running. A request is not forced to wait for the longest request in its original group.

Continuous batching improves throughput because the server spends fewer iterations processing finished or padded sequences. It can also reduce queueing under mixed workloads. But it does not guarantee lower latency for every request. A larger active batch can make each decode iteration take longer, and a newly admitted long prompt can compete with existing decodes.

How the two fit together in production

A typical serving loop looks like this:

1. A request enters a queue.
2. The server schedules prefill and allocates KV blocks.
3. The request joins the decode pool.
4. Each iteration generates one token per active sequence.
5. Finished sequences release their blocks.
6. Waiting sequences are admitted when capacity allows.

PagedAttention makes steps 2 and 5 efficient for variable-length requests. Continuous batching makes step 4 efficient when requests finish and arrive at different times.

The prefill and decode phases need careful scheduling. A 20,000-token prompt can consume substantial compute and delay the next token for several existing users. Production servers often limit the number of tokens processed per scheduling step or use chunked prefill, which breaks a long prompt into smaller pieces. Otherwise, average throughput may look healthy while p99 time between output tokens becomes visibly bad.

The senior-level nuance

PagedAttention does not create more GPU memory. If the KV pool is genuinely full, the server must queue a request, preempt and later recompute another request, offload cache data, reduce context length, or reject traffic. Each option trades memory for latency, compute, or availability.

Continuous batching also has a policy problem. The scheduler must balance throughput against time to first token, the delay before a user sees the first generated token, and inter-token latency, the gap between successive output tokens. Aggressively admitting work can raise utilization while making interactive responses feel sluggish. A latency-sensitive endpoint may use stricter admission limits than an offline summarization queue.

A failure mode you can diagnose

A common symptom is: nvidia-smi shows free VRAM, but new requests wait and the server reports that KV capacity is exhausted. Inspect the serving system’s free KV-block count, maximum active sequences, maximum batched tokens, and memory reserved for weights and workspaces. Free VRAM is not the same thing as free KV capacity.

Another symptom is a sudden p99 inter-token-latency spike whenever a long prompt arrives. That usually points to prefill starving decode, not to PagedAttention failing. Limiting prefill work per iteration, separating traffic classes, or using a scheduler with explicit decode priority can help.

What they’ll ask next

Does PagedAttention reduce KV-cache memory per token?

No. It reduces allocation waste and fragmentation. The bytes per token still depend on the number of layers, KV heads, head dimension, data type, and sequence length. GQA, quantization, and shorter contexts reduce the actual cache size.

How is continuous batching different from dynamic batching?

The terms are not used perfectly consistently. Usually, dynamic batching collects requests that arrive near one another and runs them as a batch. Continuous batching reschedules at each generation iteration, allowing individual sequences to finish and new sequences to enter without waiting for the whole batch. In practice, a server may use both a short admission window and iteration-level scheduling.

What happens when the KV cache is full?

The scheduler applies a capacity policy: queue the request, preempt another sequence and recompute it later, evict or offload cache data if supported, or reject the request. PagedAttention makes allocation more efficient; it does not make an unbounded context fit on a finite GPU.

Say this in the interview: “PagedAttention fixes inefficient KV-cache allocation with non-contiguous GPU blocks, while continuous batching keeps the decode batch changing as requests finish and arrive; together they improve memory utilization and serving throughput, but neither removes the underlying KV-memory or latency trade-offs.”