vLLM Internals: PagedAttention, Continuous Batching, and Where the 2-4x Comes From

A decode step moves every weight in the model from HBM into the SMs to produce exactly one token per sequence. At batch size 1 that is a catastrophically bad trade: you read tens of gigabytes of weights to do a few megaflops of useful work, and the GPU sits idle waiting on memory. Put 60 sequences in the batch and you read the same weights once and do 60 tokens’ worth of work with them. Throughput climbs close to linearly in batch size until the model finally becomes compute-bound.

So the single most important number in an LLM serving system is not the latency of its attention kernel. It is how many sequences it can keep resident at once. And that number is set almost entirely by one thing: how well the system manages KV cache memory.

The measurement that motivated vLLM is blunt. Profiling the serving systems of the day (FasterTransformer and re-implementations of Orca), Kwon et al. found that only 20.4% to 38.2% of the KV cache memory those systems allocated actually held token state. Roughly 60-80% of the most contended resource on the GPU was holding nothing. Not because of a bug — because of the memory layout everyone was using.

This post is about what that layout was, why paging fixes it, what the fix costs, and how the scheduler on top of it works. It is the third of a three-part arc that started with how attention itself works and continued into why model size and data scale the way they do — that second post ended on the observation that how you train a model fixes the shape of the thing you eventually have to serve. This is that serving problem.

Why the KV cache is the binding constraint

GPU memory during inference splits three ways: model weights (fixed, known at load time), activations (small and transient — they live for one layer), and the KV cache (per sequence, grows by one entry per generated token, lives as long as the request does). Only the third term scales with concurrency, so it is the one that decides your batch size.

Its size per token is pure arithmetic:

def kv_bytes_per_token(n_layers, n_kv_heads, head_dim, dtype_bytes=2):
    # one K vector and one V vector, per layer, per token
    return 2 * n_layers * n_kv_heads * head_dim * dtype_bytes

# illustrative shapes for a 13B-class model — substitute your own config
per_token = kv_bytes_per_token(n_layers=40, n_kv_heads=40, head_dim=128)
print(per_token / 1024, "KiB per token")             # 800.0
print(per_token * 2048 / 1e9, "GB per request @ 2048 tokens")   # ~1.68

Eight hundred kilobytes per token. A single 2048-token request’s cache is the better part of two gigabytes. On a GPU where the weights already ate most of the board, the number of requests you can serve concurrently is “leftover memory divided by that” — which makes serving throughput, very directly, an allocator design problem.

The naive layout, and its three kinds of waste

Deep learning frameworks want contiguous tensors. An attention kernel that assumes K[seq, pos, head, dim] is one flat buffer is easy to write and easy to make fast. But a request’s final length is unknown when it arrives — you find out how long the answer is by generating it. So the obvious implementation reserves a contiguous chunk sized to the model’s maximum sequence length (2048, in the paper’s example) up front, and holds it for the request’s entire lifetime.

That produces three distinct wastes, and it is worth keeping them separate because paging kills them in different ways:

• Reservation. Slots held for tokens this request will generate later. Genuinely needed eventually, but idle now, and unavailable to anyone else in the meantime.
• Internal fragmentation. The gap between the request’s actual final length and the 2048 it was allocated. A 37-token answer in a 2048-token buffer wastes 2011 slots — for the whole request, unrecoverably.
• External fragmentation. Different requests reserve different-sized contiguous chunks, so the allocator (the paper assumes a buddy allocator) accumulates unusable holes between them. Exactly the heap fragmentation you already know from malloc, with the same cause: variable-size contiguous allocation.

Quantified on a handful of requests:

import math

MAX_LEN, BLOCK = 2048, 16
final_lengths = [37, 512, 128, 64, 900, 41, 1503, 72]   # actual, known only afterwards

used   = sum(final_lengths)
naive  = MAX_LEN * len(final_lengths)                    # contiguous, max-len reservation
paged  = sum(BLOCK * math.ceil(L / BLOCK) for L in final_lengths)

print(f"used {used}, naive alloc {naive} ({used/naive:.1%} useful)")   # 20.8% useful
print(f"paged alloc {paged} ({used/paged:.1%} useful)")                # 99.1% useful

That 20.8% is not a coincidence — it lands right in the 20.4-38.2% band the paper measured on real traces. The waste is structural, and it is what caps batch size, and batch size is what caps throughput.

PagedAttention: page tables, for KV

The fix is the one operating systems settled on decades ago for exactly this problem. Stop requiring that a sequence’s memory be physically contiguous. Instead:

1. Chop the KV cache into fixed-size blocks — 16 tokens per block by default. A block holds the K and V vectors for 16 consecutive positions of a given attention head.
2. Keep a global pool of physical blocks, allocated on demand, one block at a time, as a sequence actually grows into it.
3. Give each sequence a block table: an array mapping logical block index to (physical_block_number, num_filled_slots).
4. Teach the attention kernel to walk that table at execution time and gather K/V from wherever the blocks happen to live.

Step 4 is the whole trick. It is a page-table lookup on the critical path of attention, which is why the technique needs a custom kernel rather than being a pure allocator change.

    flowchart LR
	    subgraph seqA["Sequence A - block table"]
	        A0["logical 0 → phys 7, 16/16"]
	        A1["logical 1 → phys 1, 16/16"]
	        A2["logical 2 → phys 3, 4/16"]
	    end
	    subgraph seqB["Sequence B - block table"]
	        B0["logical 0 → phys 7, 16/16"]
	        B1["logical 1 → phys 1, 16/16"]
	        B2["logical 2 → phys 9, 11/16"]
	    end
	    subgraph pool["Physical KV block pool in HBM - order is arbitrary"]
	        P7["block 7<br/>ref=2 · shared prompt"]
	        P1["block 1<br/>ref=2 · shared prompt"]
	        P3["block 3<br/>ref=1 · A only"]
	        P9["block 9<br/>ref=1 · B only"]
	        PF["blocks 0,2,4,5,6,8<br/>free list"]
	    end
	    A0 --> P7
	    A1 --> P1
	    A2 --> P3
	    B0 --> P7
	    B1 --> P1
	    B2 --> P9

Address translation is three lines:

BLOCK = 16

def resolve(block_table, pos):
    """logical token position -> (physical block, offset within block)"""
    logical_block, offset = divmod(pos, BLOCK)
    physical_block, num_filled = block_table[logical_block]
    assert offset < num_filled, "reading a slot that hasn't been written"
    return physical_block, offset

And growth is “append a block only when you cross a boundary”:

class BlockAllocator:
    def __init__(self, num_blocks):
        self.free = list(range(num_blocks))
        self.ref_count = [0] * num_blocks

    def allocate(self):
        pb = self.free.pop()
        self.ref_count[pb] = 1
        return pb

    def release(self, pb):
        self.ref_count[pb] -= 1
        if self.ref_count[pb] == 0:
            self.free.append(pb)          # back to the pool, reusable by anyone

Now re-examine the three wastes:

• External fragmentation is eliminated by construction. Every block is the same size, so any free block satisfies any request. There is no such thing as a hole too small to use.
• Internal fragmentation is bounded, not eliminated. The last block of a sequence is partially filled, so worst-case waste is under one block — fewer than 16 token-slots per sequence, against up to max_len - actual_len before. The paper’s phrasing is “near-zero waste in KV cache memory”, and the hedge in that phrase is load-bearing. It is not zero.
• Reservation waste disappears because nothing is reserved. Blocks are handed out on the step the sequence needs them.

Why 16

Block size is a real tuning knob with pressure from both directions. Too small, and the kernel does more block-table lookups per token and reads memory in chunks too small to saturate the GPU’s parallelism. Too large, and you are back to paying internal fragmentation (a whole block wasted at the tail of every sequence) and you lose sharing granularity, because sharing happens at block boundaries.

The paper’s ablation over ShareGPT and Alpaca traces found 16 through 128 all near-optimal on ShareGPT, but only 16 and 32 performed well on Alpaca — the shorter sequences in Alpaca degrade quickly as blocks get big, since a 64-token block wasted at the tail of a 90-token sequence is a large fraction of it. 16 is the value that is safe on both. Every docs version I checked agrees on 16 as the default, though I pulled those from a mix of versioned snapshots rather than one current source-of-truth file, so treat it as “very likely still 16” rather than pinned to today’s release.

The kernel pays for the indirection

Here is the part that most write-ups get backwards. PagedAttention does not make attention faster. It makes it slower.

The paper’s own microbenchmark puts the paged kernel at 20-26% higher latency than the equivalent highly-optimized non-paged FasterTransformer attention kernel. That is the cost of block-table lookups, extra branching, and handling variable-length sequences instead of a uniform contiguous buffer. It is a real cost and the paper reports it honestly.

Making the gather even that cheap takes deliberate work at the memory-layout level. In the reference kernel implementation, the key and value caches use different tensor layouts:

key   cache: [num_blocks, num_kv_heads, head_size/x, block_size, x]
value cache: [num_blocks, num_kv_heads, head_size,   block_size]

The x-factored split on the key side exists so that neighboring threads in a warp end up reading neighboring addresses — coalesced access — given the access pattern the query-key dot product has, which differs from the pattern the value-weighted sum has. Element addresses resolve as roughly physical_block_number * kv_block_stride + kv_head_idx * kv_head_stride + physical_block_offset * x. Parallelism is structured so that a small thread group (commonly 2 threads) cooperatively handles one query-key pair, a warp of 32 threads processes one whole KV block per iteration and loops over the sequence’s blocks, and the CUDA grid is shaped (num_heads, num_seqs, max_num_partitions) so each thread block owns one head of one sequence.

So why accept a 20-26% slower attention op? Because attention is one operator among many. The linear layers are untouched. And in exchange you fit far more sequences in memory — on OPT-13B with the ShareGPT trace, the paper reports vLLM batching 2.2x more concurrent requests than Orca (Oracle) and 4.3x more than Orca (Max). A 20-26% slower kernel running on a 2-4x larger batch is a very good trade. The end-to-end win is a batch-size lever, not a kernel-speed trick, and describing it as “faster attention” misrepresents the mechanism entirely.

One caveat on version drift: the hand-written 2023 kernel benchmarked above is not necessarily the code path your current install uses. Modern vLLM supports FlashAttention, FlashInfer, and TRTLLM-GEN backends, and those libraries implement their own paged-KV-compatible kernels. The block-table memory model is still the foundation; the specific kernel is not something you should assume.

Ref counts and copy-on-write

Once logical-to-physical is indirected through a table, sharing becomes nearly free. Two sequences with identical token history — parallel samples from one prompt, beam-search candidates, or two unrelated requests that happen to start with the same system prompt — can just point their logical blocks at the same physical block. Each physical block carries a reference count.

The complication is that these sequences will eventually diverge, and when one writes into a shared block, the other must not see the write. Same problem fork() has, same solution: copy-on-write at block granularity.

def append_token(seq, token, alloc, kv_mem):
    """Append one generated token to a sequence, with CoW on shared blocks."""
    if seq.num_tokens % BLOCK == 0:                 # crossing into a fresh logical block
        seq.block_table.append([alloc.allocate(), 0])
    else:
        pb, filled = seq.block_table[-1]
        if alloc.ref_count[pb] > 1:                 # shared with someone else
            new_pb = alloc.allocate()
            kv_mem[new_pb] = kv_mem[pb].clone()     # copy the 16 slots we inherited
            alloc.release(pb)                       # drop our reference to the old one
            seq.block_table[-1] = [new_pb, filled]

    pb, filled = seq.block_table[-1]
    write_kv(kv_mem, pb, filled, token)             # write into slot `filled`
    seq.block_table[-1][1] = filled + 1
    seq.num_tokens += 1

Trace the paper’s worked example through that code. Two parallel samples A1 and A2 from one prompt both map their logical blocks to physical blocks 7 and 1, each at ref count 2. A1 generates first: block 1 has ref count 2, so vLLM allocates physical block 3, copies block 1’s contents in, decrements block 1 to ref count 1, and repoints only A1’s table entry. A2 generates next: the block it maps to now has ref count 1, so it writes in place, no copy. One copy total, not one per sequence per step — and the shared prompt blocks (block 7 and everything before it) are never copied at all, because nobody ever writes into a full block.

Beam search is the same mechanism under a harder workload: candidates fork and get pruned every step, so the sharing graph is a constantly-reshaping tree rather than a fixed fan-out. When a candidate is dropped, its logical blocks are released, ref counts decrement, and any block that hits zero returns to the free list. The paper compares it to a compound process tree, which is exactly right.

How much this saves depends entirely on how much is actually shared — these are workload measurements, not constants:

Beam search shares far more because candidates share deep common paths, not just the prompt. And more sharing translates directly into bigger batches: on OPT-13B with Alpaca, vLLM’s throughput advantage over Orca (Oracle) grows from 1.3x with basic single-sample decoding to 2.3x at beam width 6.

Shared prefixes across different requests show the same effect. On LLaMA-13B doing WMT16 English-to-German translation with a cached few-shot prefix, the paper measured 1.67x the throughput of Orca (Oracle) with a 1-example (80-token) shared prefix, and 3.58x with a 5-example (341-token) prefix. Longer shared prefix, more blocks deduplicated, bigger batch.

Continuous batching, and who actually invented it

vLLM did not invent continuous batching. This matters, because conflating the two techniques hides what each one does.

Static (request-level) batching forms a batch of N requests at admission and runs it to completion as a unit. Every sequence steps together; sequences that finish early leave their slot idle or padded until the longest sequence in the batch finishes; nothing new gets admitted mid-flight.

static batch of 4   (· = useful compute, x = idle/padded slot)

S1  ······················    finishes at t=22
S2  ············xxxxxxxxxx    finished at t=12, slot wasted for 10 steps
S3  ·····xxxxxxxxxxxxxxxxx    finished at t=5,  slot wasted for 17 steps
S4  ················xxxxxx    finished at t=16
                          ^
              queued requests wait until here, no matter when they arrived

Continuous batching — the vLLM paper calls it iteration-level scheduling, citing Orca (OSDI 2022) and cellular batching — makes batch composition a per-iteration decision instead:

After each iteration, completed requests are removed from the batch, and new ones are added. Therefore, a new request can be processed after waiting for a single iteration, not waiting for the entire batch to complete.

    flowchart TD
	    subgraph static["Static / request-level batching"]
	        S1["Form a batch of N requests"] --> S2["Run one decode step for all N"]
	        S2 --> S3{"Every sequence<br/>finished?"}
	        S3 -->|no| S2
	        S3 -->|"yes"| S4["Free all KV at once,<br/>drain, form next batch"]
	        S4 --> S1
	    end
	    subgraph cont["Continuous / iteration-level scheduling"]
	        C1["Run one step for the current batch"] --> C2["Emit one token per running sequence"]
	        C2 --> C3["Finished sequences exit;<br/>free their blocks immediately"]
	        C3 --> C4["Admit queued requests<br/>that fit in the free blocks"]
	        C4 --> C1
	    end

Note what the right-hand loop needs to be worth anything: step C4 is only useful if freeing one sequence’s blocks actually frees enough memory to admit another, and if the freed memory is usable by a differently-sized newcomer. Under max-length contiguous reservation, neither holds well — the memory was never really free, and what is free is fragmented.

That is the correct framing of the two contributions, and the paper states it plainly. Orca raises GPU utilization by interleaving requests at the scheduling level. vLLM raises it by raising memory utilization so that more requests’ working sets fit simultaneously — which is what lets the iteration-level scheduler actually pack the batches it was always theoretically capable of forming. The paper’s summary: “By reducing memory fragmentation and enabling sharing, vLLM runs more requests in a batch in parallel and achieves a 2-4x speedup compared to Orca.”

(Also worth keeping straight: “dynamic batching”, where composition is decided once at batch-formation time and then the batch runs as a fixed unit, is not continuous batching. Continuous batching changes composition at every decode step, mid-generation. A lot of write-ups use the terms interchangeably; they are different granularities.)

The scheduler loop

Admission and preemption ordering is first-come-first-served, which the paper justifies as ensuring fairness and preventing starvation: earliest-arrived requests are preempted last. When demand for blocks exceeds supply, someone must be evicted, and vLLM uses all-or-nothing eviction per sequence group — all of a sequence’s blocks go together, because all of a sequence’s blocks are accessed together anyway. That is a domain-specific simplification over general OS page-replacement heuristics, and it is valid precisely because attention touches the entire history every step.

A sketch of one iteration (simplified — real preemption loops until enough is free):

def schedule_step(waiting, running, kv, TOKEN_BUDGET):
    scheduled = {}                            # request_id -> num_scheduled_tokens

    # 1) Decode: one token per running sequence, but crossing a block
    #    boundary needs a fresh physical block.
    for req in list(running):                 # FCFS order, oldest first
        if not kv.can_append(req):
            victim = running[-1]              # newest request preempted first
            kv.free_all(victim)               # all-or-nothing eviction
            running.remove(victim)
            waiting.appendleft(victim)        # recovered later by recompute or swap-in
            if victim is req:
                continue
        kv.append_slot(req)
        scheduled[req.id] = 1

    # 2) Prefill: spend the leftover token budget admitting queued work.
    while waiting and sum(scheduled.values()) < TOKEN_BUDGET:
        req = waiting[0]
        n = min(req.num_prompt_tokens - req.num_computed,
                TOKEN_BUDGET - sum(scheduled.values()))     # chunked prefill
        if not kv.can_allocate(req, n):
            break                             # strict FCFS: head of line blocks
        kv.allocate(req, n)
        scheduled[req.id] = n
        req.num_computed += n
        if req.num_computed == req.num_prompt_tokens:
            running.append(waiting.popleft())

    return scheduled

An evicted request’s KV state has to come back somehow, and vLLM supports two mechanisms:

• Recomputation — throw the blocks away, and when the request is rescheduled, run a single prompt-phase forward pass treating the already-generated tokens as an extended prompt. Overhead is constant in block size.
• Swapping — copy the blocks out to CPU RAM and back. Efficient at larger block sizes; at small block sizes it degenerates into many tiny transfers that waste effective PCIe bandwidth.

The paper measured recomputation overhead as never higher than 20% of swapping’s latency, with the two roughly comparable across the practical block-size range of 16 to 64. Neither is free; both beat the alternative of running out of memory.

What the engine looks like today

The scheduler representation has gotten simpler since the paper. In vLLM’s V1 engine, a scheduling step is essentially just a mapping {request_id: num_scheduled_tokens}, with no hard prefill/decode phase distinction — a request being prefilled 512 tokens at a time and a request decoding one token at a time are the same kind of entry with different values. That single representation is what lets chunked prefill, prefix caching, and speculative decoding share one scheduling code path instead of each bolting a special case onto the loop. The V1 blog post reports up to 1.7x higher throughput than the V0 engine on Llama 3.1 8B and Llama 3.3 70B with the ShareGPT dataset, attributed to CPU-overhead reduction and that scheduler redesign rather than kernel-level changes.

Architecturally, the pieces are split across processes:

    flowchart LR
	    U["HTTP client"] --> API["API server process<br/>HTTP, tokenization, detokenization"]
	    API -->|"ZMQ"| EC["EngineCore process<br/>scheduler + KV cache manager<br/>tight busy loop"]
	    EC --> W1["GPU worker<br/>model shard"]
	    EC --> W2["GPU worker<br/>model shard"]
	    W1 --> EC
	    W2 --> EC
	    EC -->|"ZMQ"| API
	    API --> U
	    BT["block tables<br/>+ free list<br/>+ ref counts"] -.-> EC

The other post-paper evolution worth knowing is Automatic Prefix Caching, which generalizes the paper’s copy-on-write sharing from “sibling sequences of one request” to “any two requests that happen to share a prefix”. Each block gets an identity that is a hash of its parent block’s hash plus the token IDs in the block plus optional extra metadata — LoRA adapter ID, image hash, or a per-request cache salt for multi-tenant isolation. That forms a hash chain over the sequence, and a global hash-to-physical-block table makes shared prefixes reusable across unrelated requests, with LRU eviction of unreferenced cached blocks:

import hashlib

def block_hashes(token_ids, block_size=16, salt=None):
    """Sketch of the prefix-cache key chain (not vLLM's literal serialization)."""
    out, parent = [], b""
    for i in range(0, len(token_ids) - block_size + 1, block_size):
        blk = tuple(token_ids[i:i + block_size])
        parent = hashlib.sha256(parent + repr((blk, salt)).encode()).digest()
        out.append(parent)
    return out

a = block_hashes(system_prompt + user_a)
b = block_hashes(system_prompt + user_b)
# identical prefix tokens -> identical leading hashes -> those blocks are
# looked up in the global table and reused, never recomputed.

Because it is a chain, a single differing token invalidates everything after it but nothing before it, which is the correct semantics for a prefix cache. SHA-256 became the default hash around v0.11 specifically to reduce collision risk relative to a faster non-cryptographic hash — a collision here means serving one request another request’s KV state, so the paranoia is warranted. The V1 blog reports under 1% throughput decrease even at a 0% cache hit rate, which is why it can be on by default rather than a flag you flip when you know your workload has shared prefixes.

Where this breaks down

The attention kernel really is slower. 20-26% in the paper’s microbenchmark against FasterTransformer’s non-paged kernel. If your workload is a single sequence at batch size 1 — a local assistant, a latency-critical single-user path — paging costs you and buys you nothing, because there is no batch to grow.

When memory isn’t the bottleneck, none of this helps. The paper is honest about this: on OPT-175B with the shorter-sequence Alpaca trace, vLLM’s advantage over the Orca baselines shrinks, because the model’s own footprint means even an inefficient baseline batches enough requests to become compute-bound. PagedAttention’s advantage is largest exactly where memory pressure is highest: long sequences, tight memory budgets, complex decoding. It is not a universal multiplier.

Every number in this post is a workload measurement. 2-4x, 1.7-2.7x over Orca (Oracle), 2.7-8x over Orca (Max), up to 22x over FasterTransformer, 37-55% beam-search block savings — all tied to specific models (mostly OPT-13B, some 66B/175B, some LLaMA-13B), specific traces (ShareGPT, Alpaca, WMT16), and specific decoding configs, measured in 2023. The launch blog’s separately-reported 14-24x over HuggingFace Transformers and 2.2-2.5x over TGI come from the project’s own less rigorously documented setup, not the peer-reviewed comparison. Read all of these as “X was measured under Y”, never as vLLM’s general performance characteristic.

“Near-zero waste” is not zero waste. Internal fragmentation is bounded to under one block per sequence, not eliminated. Only external fragmentation goes away by construction.

Preemption is a cliff, not a slope. FCFS plus all-or-nothing eviction means a sustained overload does not degrade gracefully — it evicts whole sequences and redoes their work. Recomputation overhead is bounded (never above 20% of swapping’s latency in the paper’s measurements), but bounded redone work is still redone work, and it lands as tail latency.

Paging here does not mean paging to disk. Blocks normally all live in GPU memory. The only off-GPU destination in the paper is optional CPU RAM, used specifically as one of the two preemption-recovery paths — not a general steady-state memory hierarchy that transparently spills to storage.

And the design itself is contested. vAttention (Microsoft Research / Georgia Tech, arXiv:2405.04437) argues the whole approach of rewriting attention kernels around block tables is avoidable: use CUDA’s virtual memory APIs to keep the KV cache contiguous in virtual address space while backing it with non-contiguous physical pages, getting the fragmentation win without the kernel indirection. That paper reports PagedAttention-style kernels executing roughly 7-13% more instructions than non-paged equivalents, and that paged-KV variants of FlashAttention-2 and FlashInfer prefill kernels can run up to roughly 37% and 42% slower respectively than those same libraries’ non-paged kernels, with vAttention claiming up to around 1.23x end-to-end serving throughput over PagedAttention-based serving. I have not independently verified that methodology, and their kernel-level comparisons report larger ratios on what may be different metrics, so take these as “a competing paper reports” rather than settled consensus. The underlying critique is nonetheless worth taking seriously: PagedAttention solved a memory-layout problem by pushing complexity into every attention kernel anyone will ever write, and it is legitimate to ask whether the hardware’s own address-translation machinery could have absorbed that instead.

The one-sentence version

Serving throughput is a function of batch size, batch size is a function of KV cache memory efficiency, and the pre-2023 layout was wasting 60-80% of it on reservation and fragmentation. PagedAttention recovers that memory by borrowing virtual memory’s block tables, pays 20-26% on the attention kernel for the indirection, and hands the recovered capacity to an iteration-level scheduler that Orca had already designed but could not previously feed. Then ref counts turn that same indirection into free prefix sharing, which is where beam search, parallel sampling, and system prompts get their extra win.

None of it makes a single token arrive faster. All of it makes far more tokens arrive per second, which for anything serving real traffic is the number that actually pays the bill.