vLLM internals: PagedAttention and continuous batching

About this article: AI-assisted writing, reviewed against the cited sources. This is source research, not a lab validation of the procedures. Check the stated versions and your own recovery requirements before making changes.

A language-model server is limited by two different decisions on every step. Continuous batching decides which requests occupy the GPU for this iteration. PagedAttention decides where each request's keys and values sit in GPU memory, and whether two requests may share a block. Get the first wrong and finished work waits behind unfinished work. Get the second wrong and most of the memory you bought stores padding, not tokens.

An AI writing system helped prepare this article for NetLeverage. Descriptions of what a model "remembers" mean stored key and value vectors. They are not a claim about subjective experience, and nothing here was measured on a GPU for this article.

The 2023 system paper and the current project documentation do not describe the same code. Throughput multiples below are that paper's results on named models and traces. They are not a purchasing number for a model you have not measured.

Why it matters

Autoregressive generation produces one new token at a time. The keys and values of earlier tokens are cached so the model does not recompute them. That cache grows with every new token and shrinks only when the request ends or is evicted. The batch size you can run is therefore a memory question before it is a FLOPS question.

Kwon et al. illustrate this on a 13-billion-parameter model on an NVIDIA A100 with 40 GB. About 65 percent of memory holds weights, which stay put for the whole service. Close to 30 percent holds the dynamic key-value cache. Activations are the small remainder. For OPT-13B in FP16 they calculate one token's cache as 2 × 5120 × 40 × 2 bytes, which is 800 KB. A sequence allowed to reach 2048 tokens can therefore need up to 1.6 GB of cache for a single request. Tens of gigabytes of GPU memory then hold only tens of such requests, and only if the allocator does not waste the space.

Their profiling of earlier serving systems found that only 20.4 to 38.2 percent of key-value memory held actual token state. The rest was reserved for tokens not yet generated, internal fragmentation against a maximum length, or external fragmentation from the allocator. A faster attention kernel cannot batch requests that do not fit.

Arrival time makes the second failure mode. If the server freezes a batch until every request in it has finished, a short answer waits on a long one, and a new request waits on the whole batch. Yu et al. name that request-level scheduling and replace it with iteration-level scheduling. The vLLM project README calls its request scheduling feature continuous batching; Orca's paper calls the underlying approach iteration-level scheduling. The vLLM paper treats the two techniques as complementary: Orca interleaves requests; paging is what lets more of those requests fit.

How it works

Prompt phase, decode phase, and who runs this step

A request arrives as prompt tokens $x_1,\dots ,x_n$ and is then sampled one token at a time. Kwon et al. split the work. Prefill runs the known prompt as matrix-matrix work and writes $k_1,\dots ,k_n$ and $v_1,\dots ,v_n$. Decode then adds one token per iteration and rereads the cache. That step is memory-bound and dominates a long answer. The same word at two positions is not one cache entry: the vectors depend on the preceding context.

Orca schedules at iteration granularity: choose requests, run one iteration, take the results back. A finished request leaves at once. A new arrival can join after this iteration, not after the longest request in a frozen batch. Their fairness rule is iteration-level first-come-first-served: an earlier request has run at least as many iterations as a later one. A short late request may still return first.

Mixed lengths will not pack into a tensor of shape [batch, length, hidden]. Orca's selective batching concatenates tokens for linear layers, layer norm, and residual adds, and it runs attention per request so one query cannot read another request's keys. The 2023 vLLM paper describes a related iteration loop. Each iteration it picks sequences, allocates any new physical blocks, and concatenates every prompt token of prefill requests with the latest token of decode requests. Admission is first-come-first-served. When blocks run out, the latest requests are preempted.

Three wastes in a contiguous cache

Earlier systems stored one request's cache as one contiguous tensor, because common deep-learning frameworks wanted contiguous storage. Output length is unknown, so they reserved a chunk sized to the maximum sequence length, for example 2048, even when the true answer would be far shorter. Kwon et al. name three wastes:

Reserving the maximum up front also blocks sharing. Parallel samples and beam candidates share a prompt, and often share a growing prefix, but separate contiguous allocations cannot point at the same bytes.

PagedAttention: fixed blocks, non-contiguous physical memory

PagedAttention keeps the same attention maths and changes the storage. The cache of a sequence is split into blocks of $B$ tokens. Block $j$ holds keys $k_{(j-1)B+1},\dots ,k_{jB}$ and the matching values. The kernel scores the query against one block, then the next, and combines them. The blocks of one sequence need not sit next to each other in GPU memory.

The paper's analogy is operating-system paging: blocks are pages, tokens are the bytes inside a page, requests are processes. A block table maps each logical block of a request to a physical block and records how many positions in that block are filled. Logical blocks fill left to right. A new physical block is allocated only when the previous one is full. All waste for that request is then inside the last partial block, not a reservation out to the model's maximum length. Equal block sizes remove external fragmentation. Small blocks cut internal fragmentation.

On the workers, a block engine takes one contiguous GPU allocation and slices it into physical blocks. The scheduler owns the map. The paper's seven-token example fills two logical blocks during prefill, writes the next token into the spare slot, and allocates a third physical block only when that slot is full. Nothing reserved a 2048-token slab at arrival.

Block size is a trade. A larger block gives the kernel more consecutive positions to read, and more internal fragmentation, and less chance that two sequences share a whole block. On the paper's ShareGPT trace, block sizes 16 through 128 behaved best. On the shorter Alpaca trace, 16 and 32 worked and larger sizes hurt because sequences were shorter than a block. The 2023 system therefore defaulted to 16. That default is a finding about those traces, not a promise that every later kernel wants the same value. Read the block size of the build you run.

Sharing with reference counts and copy-on-write

A physical block may be mapped from more than one logical block. Each physical block has a reference count.

Parallel sampling is the simple case. Several outputs share one prompt. Their prompt logical blocks point at the same physical blocks, so the prompt is stored once. When a sample must write a block whose reference count is greater than one, the engine allocates a new physical block, copies that one block, and drops the count. The other sample keeps the original. Only the diverging tail is duplicated. On the paper's Alpaca runs this saved 6.1 to 9.8 percent of blocks; on ShareGPT, 16.2 to 30.5 percent, because prompts were longer.

Beam search shares more, and the pattern changes every step. Candidates that fall out of the top-$k$ free their logical blocks and decrement reference counts. A physical block at count zero is released. New candidates allocate new blocks only for the step they just took. The paper reports 37.6 to 55.2 percent block savings on Alpaca and 44.3 to 66.3 percent on ShareGPT. The same mechanism covers a shared system-prompt prefix: the service keeps physical blocks for that prefix, and a user request maps its logical prefix onto them, with the last shared block marked copy-on-write. Prefill then runs only on the user-specific suffix.

The paper implements those policies as fork, append, and free. The kernel sees physical block IDs, not the sharing policy, so differently sampled requests can share a batch. That is a batching opportunity, not a claim that mixed sampling is free.

Preemption when blocks run out

Output length is unknown, so a legal schedule can still exhaust physical blocks. The paper evicts all blocks of a sequence or none of them, because a later step needs the whole prefix. Sequences that share memory inside one request, such as the beams of one search, are preempted and resumed together.

Two recovery methods are described:

• Swap. Copy the evicted blocks to CPU memory, managed by a second block allocator. The paper's design stops admitting new requests until the preempted sequences finish, and it bounds CPU swap space by the number of GPU blocks. Small blocks turn the copy into many short transfers and waste PCIe bandwidth. In their microbenchmark, recomputation's overhead was never higher than 20 percent of swapping's latency, and for block sizes 16 to 64 the two methods were comparable end to end.
• Recompute. Drop the cache and, when the sequence is admitted again, treat the original prompt plus the tokens already produced as a new prompt. One prefill rebuilds every position. Recomputation cost in that microbenchmark did not depend on block size.

vLLM V1 documentation defaults preemption to recompute, not swap. The documented warning names PreemptionMode.RECOMPUTE, the sequence group, and a cumulative count. Levers on that page: raise gpu_memory_utilization (the GPU-memory fraction allowed for the model executor, from which the cache budget is derived), lower max_num_seqs or max_num_batched_tokens, or add tensor or pipeline parallel so each GPU holds fewer weights. Tensor parallel adds synchronisation; pipeline parallel adds latency. Preemption counts are Prometheus metrics, and disable_log_stats=False logs the cumulative count. None of these knobs was run for this article.

Chunked prefill, which the 2023 paper does not specify

The V1 tuning guide describes a scheduler that will not run a huge prefill as one indivisible chunk beside waiting decodes. Chunked prefill is enabled by default in V1 when the build allows it. The policy runs pending decodes first. Leftover room in the max_num_batched_tokens budget is then given to prefills, and a prefill that does not fit is split.

The guide's own tuning notes, which are recommendations rather than measurements repeated here:

• A smaller budget, their example is 2048, leaves less prefill work in the step, which helps inter-token latency.
• A larger budget improves time to first token, because more prompt tokens are processed per step.
• They suggest a budget above 8192 for throughput, especially for smaller models on large GPUs.
• Setting the budget equal to the model's maximum length is close to the older V0 policy, except that decodes are still preferred.

If chunked prefill is turned off, the same page warns that max_num_batched_tokens must be greater than max_model_len, or the server may crash at startup. The guide cites arXiv:2401.08671 and arXiv:2308.16369. Those papers were not opened, so their results are not used. The tuning page discusses -O0 to -O3, --enforce-eager, and a flag written there as --kv-cache-memory. The current Engine Arguments reference instead names --kv-cache-memory-bytes. Treat that mismatch as a reason to check the installed release's help, not to copy either spelling blindly. A pinned cache size is valid only for the same GPU and the same free memory at boot. They were not run here.

Several GPUs, one block map

The paper shards attention by head in the Megatron style. One scheduler broadcasts token IDs and the block table each step. Workers all-reduce among themselves and return sampled tokens. Physical block IDs match across workers; the bytes differ because each worker stores only its heads. The V1 guide still treats tensor parallel as the usual single-node split and warns that all-reduce is the cost. Pipeline parallel places layers on different GPUs and adds latency. Do not copy the paper's eight-GPU OPT-175B layout onto a newer parallel mode without reading that release.

The kernel page, and what the 2023 runs measured

The stable "Paged Attention" page opens with a warning that it is historical and no longer describes today's code. It then documents a single-query kernel: one query token per sequence, separate key and value caches, and a compile-time block size. Its example of block size 16 and head size 128 is 2048 elements per head per block. A warp reads one KV block. That is not the same thing as a CUDA thread block. Do not treat the file path on that page as the binary you installed. Confirm the attention backend in the log before you blame "the" paged kernel.

The paper compares itself with FasterTransformer and with three reimplementations of Orca, because Orca's code was not available. Those variants reserve the true output length (Oracle, not achievable in production), the next power of two, or 2048. Traces are ShareGPT and Alpaca lengths with Poisson arrivals, scored as mean end-to-end latency divided by output length. Runs last an hour, or 15 minutes for OPT-175B. Hardware is A100 on Google Cloud A2: one 40 GB GPU for 13B (26 GB weights, 12 GB cache, 15.7K slots), four GPUs for 66B, eight 80 GB GPUs for 175B.

The abstract says 2–4× throughput at similar latency, with larger gains on long sequences, large models, and complex decoding. On ShareGPT the body reports 1.7–2.7× the request rate of Orca (Oracle), 2.7–8× versus Orca (Max), and up to 22× versus FasterTransformer. On short Alpaca sequences with OPT-175B the Oracle gap shrank because the job became compute-bound. A shared translation prefix on LLaMA-13B gave 1.67× (80 tokens) and 3.58× (341 tokens) versus Orca (Oracle). The paged attention kernel itself was 20–26 percent slower than FasterTransformer's, from the block table and variable lengths. End-to-end throughput still rose because more requests fit. The paper says accuracy was unchanged because the formula is unchanged. That is not a test of a later quantised checkpoint, and the slot counts are not a sizing sheet.

What to choose and why

Risks and limits

• The stable "Paged Attention" page says it is historical. Chunked prefill and recompute-by-default are V1 documentation, not the SOSP scheduler.
• The 2023 speedups used OPT and LLaMA-13B, ShareGPT and Alpaca lengths, and a reimplemented Orca. They are not a purchasing number.
• Our operational inference: preempted work can later complete, so success rate alone may hide a latency regression. Alert on preemption counts and latency rather than assuming every preempted request succeeds.
• The paper's swap path stops new admissions until preempted work drains, and small-block copies under-use PCIe. Confirm the mode before you size host RAM for swap.
• Block size 16 was right for those traces. The Alpaca ablation showed larger blocks wasting short sequences. Sharing is per block: the last partial block of a shared prefix is copy-on-write.
• Our diagnostic inference: slow collectives can delay an iteration independently of cache exhaustion. Measure communication time and collective timeouts separately.
• With chunked prefill off, a token budget below max_model_len can crash startup. That condition is documented, not lab-tested here.
• No command in this article was run, including the guide's LLM(..., max_num_batched_tokens=16384) example. No NetLeverage product behaviour is claimed.

Sources

1. Woosuk Kwon et al., Efficient Memory Management for Large Language Model Serving with PagedAttention, SOSP 2023, arXiv:2309.06180 — https://arxiv.org/abs/2309.06180 (HTML https://arxiv.org/html/2309.06180 opened 10 November 2026). Paging design, block size 16, waste figures, preemption, tensor-parallel block manager, and the reported throughput comparisons.
2. Gyeong-In Yu et al., Orca: A Distributed Serving System for Transformer-Based Generative Models, OSDI 2022 — https://www.usenix.org/system/files/osdi22-yu.pdf (PDF opened 10 November 2026). Iteration-level scheduling, selective batching, and iteration-level FCFS.
3. vLLM documentation, Paged Attention — https://docs.vllm.ai/en/stable/design/paged_attention/ (opened 10 November 2026). Historical-document warning, and the single-query kernel layout that page still describes.

4. vLLM documentation, Optimization and Tuning — https://docs.vllm.ai/en/stable/configuration/optimization/ (opened 10 November 2026). V1 chunked prefill, preemption warning text, gpu_memory_utilization, and the startup-crash condition when chunked prefill is off.

5. vLLM project README, main observed 10 November 2026, for continuous-batching terminology.

6. vLLM Engine Arguments, reopened 10 November 2026. GPU-memory utilisation scope and exact cache-memory flag name.

This article was originally published on 10 November 2026.