PagedAttention from First Principles

Why this guide exists

If you've read the vLLM blog post, you know the headline: "PagedAttention gives up to 24× higher throughput than HuggingFace Transformers" (Kwon et al., 2023). That's a real number, but it tends to land as folklore. The reader walks away knowing PagedAttention is good, without quite knowing why a different memory layout produces twenty-four times the throughput.

The answer is that LLM inference is, almost entirely, a memory-bound problem. The model weights are huge, the KV cache is huger still over a batch, and on an A100 or H100 the FLOPs sit idle waiting for HBM. Anything that lets you fit more concurrent requests in the same memory budget turns directly into throughput, because the GPU was going to spin on memory bandwidth anyway. PagedAttention is, fundamentally, a memory layout change. Everything else — prefix caching, continuous batching, chunked prefill, LoRA hot-swapping — is a downstream consequence of the layout being page-shaped.

This guide is structured to build the intuition from the bottom up. We start with what the KV cache actually is in memory, why naive allocation is so wasteful, how the page-table indirection works, and then walk up through the family of optimizations that the indirection enables. By the end you should be able to read vllm/core/block_manager.py and recognize what you're looking at.

1. The problem PagedAttention solves

Start with the simplest possible inference server. A user sends a prompt, the model generates tokens one at a time, you stream them back. To avoid recomputing attention over the entire prefix at every step, the model caches the key and value tensors of every attention layer for every prompt token, and appends to that cache as it generates. This is the KV cache.

For a single layer of a single request, the KV cache has shape [seq_len, num_kv_heads, head_dim] for K, and an identical shape for V. Multiply by 2 (K and V), by num_layers, and by the dtype size (2 bytes for fp16/bf16) and you get the bytes per token of context.

Plug in numbers for Llama-3-70B: 80 layers, 8 KV heads (GQA), head_dim 128. Per token:

bytes_per_token  = 2 (K and V)
                 × num_layers          (80)
                 × num_kv_heads        (8)
                 × head_dim            (128)
                 × dtype_bytes         (2  for bf16)
                 = 327,680 bytes  ≈  320 KiB per token

So one token of KV state for Llama-3-70B is ~320 KiB. A 2,048-token context is ~640 MiB per request just for the cache. An 80 GB H100 fits the 140 GB model across two cards, leaving maybe 20 GB per card for KV cache — so you've got headroom for perhaps ~50 concurrent 2k-context requests, before you've even considered activations and CUDA workspace.

Now the trap. The classical way to allocate the KV cache, before vLLM, was to pre-allocate a contiguous tensor sized for max_tokens per request. max_tokens is the worst case — the most tokens the user might ever generate. So if a user sets max_tokens=2048 but the model emits an EOS at token 80, you have just paid for 1,968 tokens of unused KV state, and you can't reclaim it until that request finishes, because the GPU memory allocator can't move tensors around mid-decode.

Empirically, real workloads have actual generation lengths that are 5–10× shorter than the max_tokens users set. The vLLM paper measures this directly on ShareGPT and Alpaca traces: only 20.4% to 38.2% of the pre-allocated cache is ever used. The rest is dead weight, holding the GPU hostage so it can refuse a new request because "memory is full" while sitting on hundreds of megabytes of zeros.

2. What lives in the KV cache, exactly

Before we look at the layout, pin down what the cache actually stores. For each transformer layer, after the QKV projection, the model has three tensors per token: Q, K, V. Q is consumed immediately by the attention op and discarded. K and V are needed again at every subsequent step, because attention at step t reads keys and values for every token at positions 1..t.

So the cache shape per layer is:

K[i] : [num_kv_heads, head_dim]       # per token i, per layer
V[i] : [num_kv_heads, head_dim]       # per token i, per layer

For a request of length L tokens, that's L × num_layers × 2 × num_kv_heads × head_dim × dtype bytes. The cache is append-only during generation: at decode step t, you produce one new K and V vector per layer and append.

This append-only-but-bounded structure is what makes blocks work. You don't need random writes — you only ever append at the tail. You just need the tail to be allowed to physically live anywhere in memory.

3. Fragmentation: internal & external

"Fragmentation" is a term operating-systems people use for memory you have but can't use. There are two kinds, and naive KV allocation suffers both.

Internal fragmentation

You allocated more than you need, inside an allocation that's still alive. This is the max_tokens=2048 request that only generates 80 tokens — the other 1,968 token slots are internal to the request's allocation, but unused. The allocator sees them as "in use" because the request still holds the slab.

External fragmentation

You have enough total free memory but no contiguous block big enough. Imagine 8 GB free, scattered as 16 holes of 512 MB each, and a new request needs a contiguous 1 GB slab — it can't be allocated, even though there's 8× the memory it needs. CUDA's caching allocator (cudaMalloc wrapped in a slab allocator) hits this constantly when KV slabs have varying max_tokens.

Here's a visual of a four-request memory layout under naive allocation, with each request allocating a 2,048-token-shaped slab:

GPU HBM (KV region, simplified — each cell is one token slot of ~320 KiB)

Request A (slab capacity 2048, actual length 120):
  [AAAA AAAA AAAA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .]
   ^120 used                ^1928 wasted (internal fragmentation)

Request B (slab capacity 2048, actual length 1900):
  [BBBB BBBB BBBB BBBB BBBB BBBB BBBB BBBB BBBB BBBB BBBB BBBB BBBB BBBB BBBB B..]
   ^1900 used                                                              ^148 wasted

Request C (slab capacity 2048, actual length 60):
  [CCCC C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .]
   ^60 used         ^1988 wasted

Request D (slab capacity 2048, actual length 800):
  [DDDD DDDD DDDD DDDD DDDD DDDD DDDD DDDD . . . . . . . . . . . . . . . . . . .]
   ^800 used                            ^1248 wasted

Across these four requests, you've paid for 8,192 token slots and used 2,880 of them. ~65% wasted, and that's before counting external fragmentation between slabs as some requests finish and free their slab while neighbours are still live.

The point of PagedAttention is to attack both at once: allocate in small fixed-size blocks (kills internal fragmentation — you waste at most one partial block per request), and let blocks live anywhere via an indirection table (kills external fragmentation — any free block is usable).

4. The OS analogy: why "Paged"

The naming is intentional. The KV cache problem in 2023 is structurally identical to the virtual-memory problem operating systems solved in the 1960s. Process address spaces are too big and too varied to live in contiguous physical RAM, so the OS splits them into fixed-size pages (typically 4 KiB), keeps a per-process page table that maps virtual page numbers to physical frames, and lets the hardware MMU do the translation on every access.

The mapping in PagedAttention:

This analogy is more than rhetorical. The vLLM team explicitly designed around it, and once you internalize the mapping you can predict roughly half the engineering decisions before reading the code. Why is block size a tunable? Same reason page size is a tunable: small pages reduce internal fragmentation but blow up the page table; large pages do the opposite. Why is there a copy-on-write path? Same reason fork() has one: shared prefixes across requests are the common case, divergence is the exception. Why does the kernel walk an indirection? Same reason your CPU walks a page table on every load.

5. The PagedAttention algorithm

Here's the layout in concrete terms. Pick a block size B (vLLM defaults to B = 16 tokens). Pre-allocate a large pool of physical KV blocks at server startup, sized to fill the available GPU memory minus model weights minus activation headroom. Each block holds the K and V tensors for B tokens, for one layer, for one request.

Wait — for one layer? Yes. There are subtle layout choices here. vLLM's actual layout stores the cache as two big tensors per layer:

k_cache[layer] : [num_blocks, num_kv_heads, head_dim/x, block_size, x]
v_cache[layer] : [num_blocks, num_kv_heads, head_dim,    block_size   ]

The x dimension on the K cache is a vectorization trick (8 fp16 elements packed for coalesced loads). Don't get hung up on it; the conceptual picture is "per layer, a flat array of blocks indexed by physical block id".

For each logical request, vLLM maintains a block table: a list of physical block IDs that, in order, make up the request's KV sequence. When a request grows past a block boundary (token B+1, 2B+1, etc.), it asks the block manager for a new physical block and appends its ID to the block table.

Logical view (one request, 50 tokens, B=16):

  tokens   0..15      16..31     32..47     48..49
           ┌───────┐  ┌───────┐  ┌───────┐  ┌──┐
  logical  │ blk 0 │  │ blk 1 │  │ blk 2 │  │3 │
           └───────┘  └───────┘  └───────┘  └──┘

Physical mapping via block_table for this request:
  block_table = [7, 23, 4, 19]       # arbitrary, depends on what was free

Physical GPU HBM (k_cache, simplified):
  [ blk0=. blk1=. blk2=. blk3=. blk4=req_X blk5=. blk6=. blk7=req_X
    blk8=. blk9=. blk10=. ... blk19=req_X ... blk23=req_X ... ]

Physically, the four logical blocks of the request live at HBM offsets 7, 23, 4, and 19. They're not contiguous, they're not even in order. The attention kernel doesn't care, because it reads through the block table.

The pseudocode for a single decode step is brutally simple at the dispatcher level:

# Simplified — this is the algorithm, not the literal vLLM code

def paged_attention_decode(query, k_cache, v_cache, block_table, context_len):
    """
    query        : [num_kv_heads, head_dim]            # this step's Q
    k_cache      : [num_blocks, num_kv_heads, head_dim, block_size]
    v_cache      : same shape
    block_table  : [num_blocks_in_seq]                 # logical -> physical
    context_len  : int, number of valid tokens
    """
    num_blocks = (context_len + BLOCK_SIZE - 1) // BLOCK_SIZE
    out = torch.zeros_like(query)
    running_max = -inf
    running_sum = 0.0

    for i in range(num_blocks):
        physical_id = block_table[i]
        k_block = k_cache[physical_id]    # [heads, head_dim, block_size]
        v_block = v_cache[physical_id]

        # tokens in this block that are actually valid
        block_start = i * BLOCK_SIZE
        block_end   = min(block_start + BLOCK_SIZE, context_len)
        valid       = block_end - block_start

        # standard masked attention restricted to valid tokens
        scores = query @ k_block[..., :valid] / sqrt(head_dim)   # [heads, valid]
        # online softmax accumulation (FlashAttention-style)
        block_max  = scores.max(dim=-1)
        running_max = max(running_max, block_max)
        # ...rescale running_sum and out by exp(old_max - new_max)...
        attn = exp(scores - running_max)
        running_sum += attn.sum(dim=-1)
        out += attn @ v_block[..., :valid].transpose(-1, -2)

    return out / running_sum

The crucial bits:

1. Indirection: every block read is k_cache[block_table[i]], not k_cache[i]. The kernel chases a pointer per block.
2. Tail handling: the last block of a request is usually partial. The kernel knows this and masks off the unused slots in that block. This is where internal fragmentation goes — at most (B - 1) tokens per request, which for B=16 is 15 tokens of waste worst-case, vs. potentially thousands under naive allocation.
3. Online softmax: the kernel accumulates max and sum across blocks à la FlashAttention, so it never has to materialize the full [1, context_len] attention vector. This matters because PagedAttention and FlashAttention compose: vLLM ships its own kernel ("PagedAttention v2") that does both.

6. The block table, byte by byte

The block table is the single most important data structure in PagedAttention. Let's look at what it costs.

For a batch of N concurrent requests, with each request potentially having up to max_blocks_per_seq blocks (where max_blocks_per_seq = ceil(max_model_len / block_size)), vLLM keeps a single 2D int32 tensor on the GPU:

block_tables : torch.int32  shape [N, max_blocks_per_seq]

Example with N=200, max_model_len=8192, block_size=16:
  max_blocks_per_seq = 512
  block_tables.shape = [200, 512]
  block_tables.numel() = 102,400
  bytes              = 409,600  ≈  400 KiB

That's it. 400 KiB on the GPU to keep track of where every block of every request in a 200-deep batch lives. The savings on the KV cache side dwarf this by four to five orders of magnitude.

Unused slots in the block table are filled with a sentinel (typically zero or -1). The kernel reads context_lens[req] separately to know how far into the request's row to walk, so it never dereferences a sentinel.

Now layer on the physical block pool. The pool is the giant tensor that actually holds bytes. For Llama-3-70B with num_kv_heads=8, head_dim=128, num_layers=80, block_size=16, dtype=bf16:

bytes per block = block_size × num_kv_heads × head_dim × 2 (K+V) × dtype_bytes
                = 16 × 8 × 128 × 2 × 2
                = 65,536 bytes  =  64 KiB per block per layer

Total per block (all 80 layers) = 80 × 64 KiB = 5.0 MiB
                                  (this is the cost of one logical block of context)

If you reserve 40 GiB for the KV pool:
  40 GiB / 5.0 MiB per block ≈ 8,192 blocks
  8,192 blocks × 16 tokens   = 131,072 tokens of total KV capacity

That 131k token capacity is the total pooled capacity across all concurrent requests. Under naive allocation, if every request reserved max_tokens=2048, you'd fit 64 requests. Under paged allocation with average actual length 400, you'd fit ~327 requests in the same memory. The 5× factor on the math is real.

7. Inside the attention kernel

A worry someone always raises: doesn't the gather hurt performance? Pointer-chasing through a block table sounds slow.

The honest answer: it costs something, but much less than you'd expect, for three reasons.

The reads are large and coalesced

Within a block, the memory is contiguous: all 16 tokens of a block live side-by-side, all heads of one token live side-by-side, all elements of one head live side-by-side. The block table only fragments at the granularity of 16-token chunks. A warp loading one block does a clean coalesced burst from HBM. The indirection cost is one int32 lookup per block, not per token.

The work is memory-bound anyway

Decode attention reads O(context_len) bytes of KV cache to produce one output token's worth of work. The compute is trivial — a sequence of dot products. So the kernel sits on HBM bandwidth waiting for the data, and the cost of looking up where the data lives is amortized across the read. A back-of-envelope: an H100 has 3.35 TB/s HBM bandwidth. A 4k-context decode reads 4096 × 8 × 128 × 2 × 2 = 16 MiB of KV from one layer; that's ~4.8 µs of bandwidth. The block table walk is single-digit nanoseconds per block; it's noise.

The kernel is fused

vLLM doesn't gather blocks into a contiguous buffer and then do attention. It fuses the gather and the attention math. The block-by-block loop is the kernel. Each warp loads its assigned block(s), does the per-block softmax accumulation, and writes back partial results, all without round-tripping through global memory.

The result is that PagedAttention's decode kernel is competitive with, and sometimes faster than, a contiguous-layout reference, because being able to fit a larger batch overwhelms the per-block lookup cost. The slow path is the one that ran out of memory and had to evict a request.

8. The math of savings — a worked example

Let's make this concrete with numbers you could defend in a design review.

Scenario: a Llama-3-70B endpoint with 200 concurrent requests, served on a 4×H100 node. Users set max_tokens=2048 by default. Looking at three months of production traces, the actual generated length distribution has mean 400 and p95 of 1,200.

KV memory per token, from earlier: 320 KiB.

Naive allocation

Per request (worst case = max_tokens):
  2048 tokens × 320 KiB     = 640 MiB

200 concurrent requests:
  200 × 640 MiB             = 128,000 MiB  =  125 GiB

Across 4 H100s with ~50 GiB free per card for KV (after weights):
  4 × 50 GiB                = 200 GiB available
  Headroom                  = 200 - 125 = 75 GiB free

But — you must reserve for the worst case at admission time.
Effective concurrency cap = floor(200 GiB / 640 MiB)  =  320 requests

Of the 125 GiB actually reserved:
  Used     = 200 × 400 tokens × 320 KiB  = 25.0 GiB
  Wasted   = 125 - 25                    = 100 GiB  (80% waste)

Paged allocation, block_size=16

Per request (actual usage rounded up to block boundary):
  ceil(400 / 16) × 16 tokens × 320 KiB = 400 tokens × 320 KiB ≈ 125 MiB
  (worst tail-block waste: 15 tokens × 320 KiB = 4.8 MiB)

200 requests at mean length:
  200 × 125 MiB           = 25,000 MiB  =  24.4 GiB

The same 200 GiB budget now fits, on average:
  200 GiB / 125 MiB        = 1,638 requests at the mean

In practice you set max_num_seqs to something like 256-512
because compute (not memory) becomes the new bottleneck.

Block table overhead:
  512 reqs × 512 max_blocks_per_seq × 4 bytes = 1 MiB
  (negligible)

Throughput consequence

If batch size goes from 64 (naive) to 256 (paged), and decode is memory-bandwidth-bound (it is), then throughput scales nearly linearly with batch size up to the point where compute saturates. The vLLM paper measures ~5× higher throughput on real ShareGPT traces from this effect alone, with further gains from continuous batching and prefix caching layered on top. The 24× headline number requires all three plus a comparison against a particularly slow baseline (HuggingFace's transformers.generate with naive padding), but the 5–10× factor over a competently-built naive server is robust.

9. Prefix caching

Once you have blocks, sharing them across requests is almost free. This is prefix caching, and it's the second-biggest win in vLLM after PagedAttention itself.

The observation: if two requests start with the same prefix (a common system prompt, a few-shot exemplar, a retrieved document), they would compute identical KV state for those prefix tokens. Naive servers do this computation twice and store it twice. Paged servers can share the physical blocks and only compute it once.

vLLM's implementation:

1. Hash each block by the token IDs it contains. The hash is H(prev_block_hash, token_ids_in_block) — i.e. it includes the chain back to the start, so two blocks with the same 16 tokens are only considered identical if their entire prefix matches.
2. Maintain a global hash table {block_hash → physical_block_id, ref_count}.
3. When a new request comes in, walk its prompt block-by-block. For each fully-filled prefix block, look up the hash. If a physical block exists, point the new request's block table at it and bump the ref count. If not, allocate a fresh block, compute, and insert into the hash table.

The savings are dramatic when system prompts are long. A 1,500-token system prompt that's shared across a million daily requests means you compute its KV state once a server lifetime (or once per cold start), not a million times. That's 1,500 prefill tokens × 1M requests = 1.5B FLOPs saved per day per prompt, and an equivalent KV-cache-bytes saved by sharing.

Two requests, shared prefix "You are a helpful AI assistant. Always..." (32 tokens):

Request 1 block_table:  [P0, P1, U1a, U1b]
                         ↑    ↑    ↑    ↑
                         shared    private (user-specific)
Request 2 block_table:  [P0, P1, U2a]
                         ↑    ↑    ↑
                         shared    private

Physical block pool:
  P0 (refcount=2, hash=h0)
  P1 (refcount=2, hash=h1=H(h0, tokens 16..31))
  U1a (refcount=1), U1b (refcount=1), U2a (refcount=1)

The eviction policy matters: when the block pool is full and a new block is needed, vLLM evicts the least-recently-used block with refcount=0. Blocks with refcount > 0 (in use by an active request) are pinned. This is essentially page replacement in OS land, and the LRU choice is the simplest thing that works — Belady's anomaly notwithstanding, LRU is what production runs.

10. Copy-on-write and beam search

Prefix sharing is read-only by construction (the prefix doesn't change). But there's a richer case: beam search, or sampling multiple candidates from the same prefix, where each candidate extends the shared prefix differently.

This is the same problem fork() solved with copy-on-write. The child process shares parent pages until it writes one, at which point the kernel duplicates that page and gives the child its own copy.

vLLM does exactly this. When a request is "split" (e.g. parallel sampling with n=4 sampled completions), each child gets a block table that initially points at the parent's blocks. As each child generates and fills up new blocks past the divergence point, those new blocks are private. The shared prefix blocks stay shared, and their refcount reflects all live children.

Parallel sampling, n=4, shared prompt of 48 tokens (3 blocks):

   parent prompt blocks
   ┌────┐ ┌────┐ ┌────┐
   │ P0 │ │ P1 │ │ P2 │            refcount=4 each
   └────┘ └────┘ └────┘
      │      │      │
      ├──── child A ─── [A3, A4, ...]   (private completion)
      ├──── child B ─── [B3, ...]
      ├──── child C ─── [C3, C4, C5, ...]
      └──── child D ─── [D3, ...]

If a child needs to write into a shared block (very rare — only happens with mid-block divergence, like when the user message ends mid-block), the block manager allocates a new physical block, copies the existing tokens in, and rewrites the child's block table entry. Pure COW.

This same primitive powers tree-of-thought, MCTS-over-token-trees, and any other algorithm that wants to explore multiple continuations from a shared prefix without paying the prefix cost N times.

11. Continuous batching (the partner mechanism)

PagedAttention is necessary but not sufficient for vLLM-style throughput. The other half is continuous batching, sometimes called iteration-level scheduling.

Traditional batching: gather N requests, pad them to the same length, run them as a single batch through the model, return all N when the last one finishes. The problem is variable-length completions. If 19 requests in your batch of 20 finished at token 50 but the 20th is still going at token 2000, the GPU is wasting 95% of its work computing attention for tokens that have already terminated.

Continuous batching dissolves this. The scheduler maintains a set of "running" requests. At each forward pass, it:

1. Selects which subset of running requests to step this iteration.
2. For each selected request, computes one decode step (or chunk of prefill — see next section).
3. Checks termination conditions; finished requests are evicted from the running set, their blocks freed, and their slots reused.
4. Admits new requests from the waiting queue, allocating their initial blocks.

The forward pass batches across requests, but each request's length is independent. The kernel takes (query_per_request, block_tables_per_request, context_lens_per_request) as inputs and computes them all in one fused launch.

Why does this need PagedAttention? Because without paged storage, evicting a finished request and admitting a new one would require either a contiguous reshuffle of the KV cache (impossible at GPU memory speeds) or pre-allocating slots for every potential admission (back to naive). With pages, "freeing" a request is just decrementing refcounts on its blocks, and "admitting" a new request is just allocating fresh blocks from the pool. Both are O(blocks-in-request) and trivial to do between iterations.

Iteration t   : running = [A(@token 50), B(@token 12), C(@token 800)]
Iteration t+1 : C terminates ─→ free its 50 blocks
Iteration t+2 : admit D (new) ─→ allocate its prefix blocks
Iteration t+2 : running = [A(@token 51), B(@token 13), D(@token 0 prefill)]

Note that D's prefill and A,B's decode coexist in the same batch. They have different work shapes — D is doing O(prompt_len²) attention, A/B are doing O(context_len) — but a properly written kernel handles both. This is where chunked prefill comes in.

12. Chunked prefill

A new request with a 10,000-token prompt is going to spend a long time in prefill. If you naively put that prefill in the same iteration as a batch of decodes, every decode-only request waits for the prefill to finish — a classic head-of-line block. Latency p99 goes through the roof.

Chunked prefill says: split the prefill into chunks of, say, 512 tokens at a time. Each iteration of the scheduler can process one chunk of one prefilling request plus a bunch of decode steps from running requests, all in the same forward pass. The prefilling request doesn't finish prefill in a single iteration, but the decodes don't have to wait.

The scheduler has a budget for each iteration — typically expressed in tokens (e.g. "step at most 2048 tokens of work this iteration"). It fills the budget greedily: decodes first (1 token each, very cheap), then as much of a pending prefill as fits. If a prefill request needs more than one chunk, it stays in a "prefilling" state across iterations.

Iter t budget = 2048 tokens:
  decode A   :    1 token
  decode B   :    1 token
  decode C   :    1 token
  ...
  decode (×64): 64 tokens of decode  (one per running request)
  prefill D  : 1984 tokens of D's 8000-token prompt
                                       ↑ first chunk
  total       = 2048 tokens

Iter t+1:
  decode (×65)  :  65 tokens (D is still prefilling, doesn't decode yet)
  prefill D     : 1983 tokens
  ...

Iter t+5:
  decode (×65)  :  65 tokens
  prefill D     : final 256 tokens, D enters decode set at t+6

The win: tail latency for short requests doesn't depend on the longest concurrent prefill. The cost: peak throughput on prefill-heavy workloads drops slightly because each chunk has to re-load the model weights and KV state from HBM rather than fusing the whole prefill into one big matmul.

13. Throughput vs goodput

Now we're in the part of inference systems engineering that's poorly named in the literature. "Throughput" — tokens per second — is the headline metric in vendor benchmarks. It's also a bit of a lie, because users don't experience throughput. They experience latency.

Three latencies matter:

• TTFT (time to first token): how long from request received until the first token streams back. Dominated by prefill cost. Felt acutely in chat (the spinner-while-thinking experience).
• TPOT (time per output token): the inter-token delay during streaming. Dominated by per-step decode latency, which is dominated by batch size and KV memory bandwidth. Felt as "the typing speed".
• End-to-end latency: TTFT + (output_length × TPOT). What actually shows up in your SLO.

A "fast" server in pure tokens/sec terms might have terrible TTFT — it batched your request behind a giant prefill and your spinner spun for four seconds. Conversely, a server with low p50 TTFT but tiny batch size might be wasting GPU.

Hence goodput: tokens per second that arrived under SLO. If your SLO is "TTFT < 1s and TPOT < 50ms" and 30% of your output tokens come from requests that breached one of those, your goodput is 70% of your throughput.

Hypothetical server stats:

                    throughput   |   p99 TTFT   |   p99 TPOT   |   goodput (SLO: TTFT<1s, TPOT<50ms)
  config A          12,000 tok/s |   3.2 s      |   28 ms      |   ~4,000 tok/s   (most requests breach TTFT)
  config B           9,500 tok/s |   0.7 s      |   42 ms      |   ~9,200 tok/s
  config C           6,000 tok/s |   0.4 s      |   18 ms      |   ~6,000 tok/s

  → config B has the highest goodput despite being middle-of-pack on throughput.

This is why SLO-aware scheduling exists. Chunked prefill is one tool — by bounding prefill chunks, you bound TTFT for waiting requests. Another is prioritization (admit prefills that improve goodput, defer those that won't make SLO anyway). DistServe and Splitwise take this further by separating prefill and decode onto different physical GPUs entirely.

14. Speculative decoding and how it interacts with PagedAttention

Speculative decoding: use a small fast model (the "draft") to propose a short sequence of tokens, then use the big model (the "verifier") to check them in a single forward pass. If the draft was right, you got multiple tokens for the cost of one big-model step. If wrong, you fall back to one token at a time.

The bargain works when:

• The draft model is much smaller than the verifier (e.g. Llama-3-8B drafting for Llama-3-70B).
• The draft's acceptance rate is high (the draft and verifier mostly agree).
• The verifier's forward pass dominates the draft's — true when the verifier is 10–20× larger.

How does this interact with PagedAttention? The verifier still uses paged KV storage. Speculative tokens are appended to the verifier's KV cache speculatively — if they're accepted, the appended blocks stay; if rejected, they're discarded (blocks freed back to the pool). This is the same allocate/free machinery already in place. The block manager doesn't need to know it's serving speculative tokens.

Where the interaction matters: batch size. Speculative decoding can hurt the verifier's batch efficiency because each verifier step now produces, say, 4 tokens per request (assuming 75% acceptance over 5 drafted tokens) — so the batch shape changes. With paged storage and continuous batching, this falls out automatically: the scheduler treats a verifier step that accepts 4 tokens identically to four decode steps, freeing the slots back to the pool at the next iteration.

Speculative decoding is enabled in vLLM via --speculative-config. Production gains are usually 1.5–2× on throughput when properly tuned. The main pitfall is choosing a draft model with poor acceptance rate — a draft that disagrees often is worse than no draft.

15. KV-cache offloading and disaggregated serving

GPU HBM is expensive (literal dollars per GiB, plus the bandwidth premium). Host RAM is cheap. NVMe is cheaper. The natural extension to PagedAttention is to tier the block pool across memory levels.

Once the KV cache is page-shaped, offloading is mechanical: a page on HBM that hasn't been touched recently can be DMA'd out to host RAM and the HBM slot freed. When the request needs it again (e.g. it returns to the active scheduling window), copy it back. This is page-swapping, full stop.

vLLM has a swap mechanism for preempted requests: when memory pressure is high and a low-priority request needs to be evicted, its KV blocks are copied to host RAM rather than discarded. When the request is scheduled again, the blocks are copied back in. The cost is two PCIe round trips, but the alternative is recomputing the prefill, which can be much worse for long-context requests.

Disaggregated serving (PD disagg)

The frontier idea: prefill and decode have such different compute/memory profiles that putting them on the same GPU is suboptimal.

• Prefill: compute-bound (full FlashAttention over the prompt). Wants tensor parallelism, big matmuls. Wants very few concurrent prefills to maximize utilization.
• Decode: memory-bound (one new Q per step against a long K/V). Wants large batch sizes to amortize KV-cache reads. Wants many concurrent decodes.

DistServe (OSDI '24) and Splitwise (ISCA '24) propose dedicating prefill GPUs and decode GPUs separately, transferring the prompt's KV cache from prefill to decode GPU over a high-bandwidth interconnect when prefill finishes. This is non-trivial — you're moving hundreds of MiB over the network — but with NVLink or RDMA it's tractable, and the throughput-per-dollar gains can be 2–3× for mixed workloads.

vLLM is moving in this direction. See the P2P_NCCL KV transfer experiments in recent vLLM versions. The block-shaped layout is what makes this tractable: you transfer blocks, not slabs.

16. Multi-LoRA serving

One more downstream consequence worth understanding. LoRA adapters are small (~1% of model weight count), and you often want to serve many adapters from one base model — different customers, different fine-tunes, different versions, all hitting the same GPU fleet.

The serving challenge is that each request can specify a different adapter. Naively you'd run a separate model server per adapter, paying for the full base weights N times. With multi-LoRA serving (S-LoRA, vLLM's LoRA support), you keep the base model resident once and hot-swap adapter matrices per request, fused into the kernel.

PagedAttention's role here is indirect but real: because requests share base weights and have KV state that's compatible across adapters (the K/V projections share base + adapter), the same paged storage works. The kernel reads (adapter_id_per_request, block_tables_per_request) and dispatches. You couldn't easily do this with naive per-request slabs; the bookkeeping is what scales.

The block-shaped layout also enables adapter-aware prefix caching: a shared prefix's K/V state under adapter A is different from under adapter B (because A and B modify the K and V projections differently), so the prefix cache must key on (block_hash, adapter_id). This is what vLLM does; it's a one-line change in the cache key once you've already got the hashing infrastructure.

17. Reading the vLLM code

If this guide has done its job, you can now open the vLLM source and read it. Here's a guided tour of where the magic lives, as of mid-2025 release branches.

vllm/core/block_manager.py

The block manager owns the physical block pool and the per-request block tables. Key classes:

• BlockManagerV2 — the production block manager. Splits into SelfAttnBlockSpaceManager and (for encoder-decoder) EncoderDecoderBlockSpaceManager.
• PrefixCachingBlockAllocator vs NaiveBlockAllocator — flipped by the --enable-prefix-caching flag. The prefix-caching allocator wraps the naive one with a hash→block map.
• can_allocate(seq_group) — admission check: does the pool have enough free blocks for this new request's prompt? Returns one of OK, NEVER (request too big to ever fit), or LATER (currently full).
• allocate(seq_group), append_slots(seq_group), free(seq_group) — the lifecycle.

vllm/core/scheduler.py

The scheduler decides which requests to step each iteration. The main entry point is Scheduler.schedule(), called once per forward pass. It returns a SchedulerOutputs describing which sequences to run, in what order, and with what slot allocations.

Internal state: three queues — waiting, running, swapped. Each iteration the scheduler tries to admit from waiting (subject to can_allocate), step everything in running, and bring back from swapped if memory frees up. The token budget for chunked prefill is enforced here, in _schedule_chunked_prefill().

vllm/attention/ops/paged_attn.py and CUDA kernels

The Python side dispatches to C++/CUDA kernels in csrc/attention/. The two main kernels are paged_attention_v1_kernel and paged_attention_v2_kernel. The v2 kernel has a reduce step that combines partial softmax outputs across blocks of the same sequence — useful when one sequence is so long it needs to parallelize across SMs.

vllm/attention/backends/

Different backends for different hardware: flash_attn.py (FlashAttention 2/3 on Ampere/Hopper), xformers.py (legacy), torch_sdpa.py (CPU/fallback), flashinfer.py (NVIDIA's FlashInfer kernel library, often faster on H100/B200 for specific shapes). The block-table interface is the same across backends.

vllm/engine/llm_engine.py

The orchestrator. Combines scheduler, model executor, and block manager. The main loop is step(): schedule → execute → sample → return. Reading this end-to-end will give you the full picture in maybe 200 lines.

18. Common misconceptions and pitfalls

"PagedAttention is a new attention algorithm"

It's not. It's a memory-layout change to the KV cache. The math of attention is unchanged. The kernel does extra indirection to find blocks, but the softmax-of-QKᵀ is the same softmax-of-QKᵀ.

"Block size 16 is optimal"

It's a reasonable default. Smaller blocks reduce internal fragmentation but increase block-table overhead and kernel launch cost. Larger blocks (32, 64) can be faster for very long contexts where the indirection cost matters and prefixes are mostly fully filled. The right answer depends on workload; benchmark for yours. vLLM exposes --block-size.

"Prefix caching is always on in vLLM"

No — it's opt-in via --enable-prefix-caching. Default-off for backward compatibility and because some workloads (true one-shot, randomized prompts) see no benefit and a small hashing overhead. In production with stable workloads it should be on.

"More batch size always = more throughput"

Up to a point. Above some batch size, you saturate compute (FLOPs) rather than memory bandwidth, and adding more requests just adds latency without throughput. That point depends on the model and hardware; for Llama-3-70B on H100, it's typically around batch 256–512 at moderate context lengths. vLLM's --max-num-seqs caps this.

"Continuous batching is the same as dynamic batching"

Related but different. Dynamic batching (in TF Serving, Triton) gathers requests into a batch once at admission and runs them as one fixed batch. Continuous batching mutates the batch every iteration. The latter is strictly more flexible and is the right move when iterations are cheap (which they are for decode).

"PagedAttention only matters for serving many concurrent requests"

It matters most there, but even for a single-user single-stream case it helps because it makes long-context inference fit when naive allocation wouldn't. The max_model_len=128k configs you see on vLLM endpoints are only practical because the cache is paged.

"Block table overhead might be significant"

It's not. As we computed earlier, a 200-request × 512-block-per-request table is 400 KiB. Compared to GiB of KV cache, this is rounding noise. The myth probably comes from worrying about pointer-chasing, but that's a kernel concern, not a memory concern.

19. References and further reading

Primary source

• Kwon, Li, Zhuang, Sheng, Zheng, Yu, Gonzalez, Zhang, Stoica. "Efficient Memory Management for Large Language Model Serving with PagedAttention." SOSP 2023. arXiv:2309.06180. The paper that introduced PagedAttention and vLLM. Reads cleanly — it's a systems paper, not an ML paper.

vLLM project resources

• vllm-project/vllm on GitHub. The code we walked through above.
• docs.vllm.ai — official docs. The "Architecture" and "Design" sections are worth reading once you understand the paper.
• vLLM launch blog post (June 2023). The first writeup, with the famous 24× throughput chart. Worth reading for the rhetorical framing.

Related work

• Dao et al. "FlashAttention" and "FlashAttention-2". The kernel-level innovation that PagedAttention composes with. arXiv:2205.14135, arXiv:2307.08691.
• Yu et al. "Orca: A Distributed Serving System for Transformer-Based Generative Models." OSDI 2022. Introduced iteration-level scheduling (the seed of continuous batching). Open-access at USENIX.
• Patel et al. "Splitwise: Efficient Generative LLM Inference Using Phase Splitting." ISCA 2024. PD disaggregation. arXiv:2311.18677.
• Zhong et al. "DistServe: Disaggregating Prefill and Decoding for Goodput-Optimized Large Language Model Serving." OSDI 2024. The goodput framing, and a different cut at PD disagg. arXiv:2401.09670.
• Sheng et al. "S-LoRA: Serving Thousands of Concurrent LoRA Adapters." MLSys 2024. The multi-tenant LoRA story. arXiv:2311.03285.
• Leviathan, Kalman, Matias. "Fast Inference from Transformers via Speculative Decoding." ICML 2023. The original speculative decoding paper. arXiv:2211.17192.

Adjacent ecosystem

• NVIDIA TensorRT-LLM — NVIDIA's answer to vLLM. Different layout choices, similar block-based KV management. Worth comparing for pedagogical contrast.
• HuggingFace TGI — adopted PagedAttention-style management; useful for comparing engineering tradeoffs.
• FlashInfer — kernel library used by vLLM (and others) for paged attention on H100/B200.

Closing

PagedAttention is the rare systems paper that landed at exactly the right moment with exactly the right abstraction. The block-table indirection looks trivial in retrospect — of course you'd page the KV cache, it works for every other large piece of memory humans have built — but the timing required someone to notice that LLM serving had become a memory-management problem rather than a compute problem, and to commit to a kernel rewrite to prove the point.

Everything in modern LLM inference now hangs off this primitive. Prefix caching, copy-on-write sampling, continuous batching, chunked prefill, KV offloading, PD disaggregation, multi-tenant LoRA — every one of these is "do the natural thing once your unit of allocation is a block instead of a slab". If you understand the block, you understand the rest.

The interesting question now is what the next layout shift looks like. Disaggregated serving suggests pages should be transferable between GPUs. Multi-tier KV suggests they should be transferable between HBM and DRAM and NVMe. Maybe future LLMs will have layer-asymmetric KV (some layers cheap, some layers expensive) and pages will need per-layer granularity. The page abstraction has another generation in it at least.