Learn AI Create the Future — with Pranay
Main site

How Text Is Generated

PagedAttention

Serving systems stopped reserving one long contiguous slab of memory per conversation and started handing out small fixed-size blocks on demand, which recovered most of the memory that used to be wasted.

Read these first

On this page 7
  1. The problem it fixed
  2. How it works
  3. The second gift: sharing
  4. Where you have already seen this
  5. What is honestly hard here
  6. Remember this
  7. What to learn next

One lesson, three depths. Pick the one that fits you today — you can switch any time.

Beginner — No maths. Plain English.

PagedAttention hands out the model's memory in small fixed-size blocks, instead of reserving one big slab per conversation up front.

Think about booking a hall for a wedding. You do not know if two hundred or six hundred guests will come, so you book for six hundred. Four hundred chairs sit empty all evening. The family next door could not book anything, because you had taken the room.

Now picture a hall where you take one round table at a time, as guests actually arrive. Nobody is turned away for space that is not being used.

That is the whole change. Conversations take small blocks of memory as they grow. Nobody reserves room for the longest reply they might ever produce.

The problem it fixed

A server has no idea how long a reply will be. It might be five words, it might be two thousand.

So the old approach reserved room for the longest allowed reply, for every single user, from the first moment. Most of that room was never touched.

There was a second waste. Even when a conversation ended and freed its slab, the space came back in awkward shapes. No new conversation could fit into them. Memory that was free but unusable.

Between the two, published measurements found that most of the memory was doing nothing. The team behind this idea reported that existing systems wasted between sixty and eighty percent of it.

How it works

   OLD WAY: reserve the worst case for everyone

   |### user A: reserved 256 ############|   used 52
   |### user B: reserved 256 ############|   used 20
   |### user C: reserved 256 ############|   used 135
   memory full. user D is turned away.


   NEW WAY: blocks of 16, handed out when the last one fills

   [A][A][A][A] [B][B] [C][C][C][C][C][C][C][C][C] [D][D]...
   plenty still free, and user D gets served

Each conversation keeps a small list saying which blocks belong to it, and in what order. The blocks themselves can sit anywhere.

Waste drops to at most part of one block per conversation. That is the last, partly-filled table.

The second gift: sharing

Blocks unlock something the old way could not do at all.

If ten users start with the same long instruction text, that text produces exactly the same notes every time. With blocks, all ten can point at one copy.

The moment any of them writes something different, that user gets a private copy of the block being changed. Everything before it stays shared.

This is why chat products with a large fixed instruction block are far cheaper to run than they look.

Where you have already seen this

  • A self-hosted chat server that handles many more users after switching to vLLM.
  • A provider offering cheaper pricing for cached prompt tokens.
  • A local model tool that stops refusing requests once you turn on a modern server.

What is honestly hard here

The idea is borrowed from how your phone and laptop manage memory, using pages and a lookup table. That analogy is genuinely useful, but the implementation is not something you write in an afternoon.

The attention calculation itself has to be rewritten to read from scattered blocks rather than one continuous run of memory. That is specialist code. You use it; you do not usually write it.

Remember this

  • Old servers reserved worst-case memory per user, and mostly wasted it.
  • Paged servers hand out small blocks on demand, wasting at most part of one.
  • Identical prompt prefixes can share blocks, which makes repeated instructions nearly free.

What to learn next

Developer — Code and libraries.

Setup

bash
# no libraries needed
python3 --version

You will not implement a paged attention kernel here. You will implement the allocator, which is where the memory saving actually comes from, and measure the waste both ways.

The allocator, both strategies

paged_allocator.py
BLOCK = 16          # tokens per block, the value vLLM has shipped as its default
POOL_BLOCKS = 64    # the whole GPU KV pool, in blocks -> 1024 token slots

MAX_LEN = 256       # what a naive server must reserve: the worst case
REQUESTS = {        # (prompt tokens, tokens actually generated)
    "r1": (40, 12),
    "r2": (17, 3),
    "r3": (95, 40),
    "r4": (8, 200),      # the one nobody sized for
}

pool = POOL_BLOCKS * BLOCK
print(f"KV pool: {POOL_BLOCKS} blocks x {BLOCK} tokens = {pool} token slots\n")

# ---------- allocator 1: one contiguous reservation per request ----------
print("CONTIGUOUS, reserve max_len up front")
used = 0
served = []
for name, (p, g) in REQUESTS.items():
    if used + MAX_LEN <= pool:
        used += MAX_LEN
        served.append(name)
        print(f"  {name}: reserved {MAX_LEN:>3} slots, will use {p + g:>3}"
              f"  -> {MAX_LEN - (p + g):>3} wasted")
    else:
        print(f"  {name}: REJECTED, only {pool - used} slots free")
real = sum(p + g for n, (p, g) in REQUESTS.items() if n in served)
print(f"  served {len(served)}/{len(REQUESTS)}   reserved {used}   really needed {real}"
      f"   waste {100 * (used - real) / used:.0f}%\n")

# ---------- allocator 2: blocks, handed out on demand ----------
print(f"PAGED, {BLOCK}-token blocks handed out only when the previous one fills")
free = POOL_BLOCKS
tables = {}                     # request -> list of block ids it owns
next_id = 0
for name, (p, g) in REQUESTS.items():
    tables[name] = []
    need = -(-p // BLOCK)       # ceiling division: blocks for the prompt
    if need > free:
        print(f"  {name}: REJECTED at prefill")
        continue
    free -= need
    tables[name] = list(range(next_id, next_id + need))
    next_id += need
    filled = p
    for _ in range(g):          # decode: one token, and a new block only when full
        if filled % BLOCK == 0:
            if free == 0:
                print(f"  {name}: PREEMPTED mid-generation, pool exhausted")
                break
            free -= 1
            tables[name].append(next_id)
            next_id += 1
        filled += 1
    print(f"  {name}: {len(tables[name]):>2} blocks for {filled:>3} tokens"
          f"  -> {len(tables[name]) * BLOCK - filled:>2} wasted (last block only)")

held = sum(len(b) for b in tables.values()) * BLOCK
real = sum(p + g for p, g in REQUESTS.values())
print(f"  served {sum(1 for b in tables.values() if b)}/{len(REQUESTS)}"
      f"   held {held}   really needed {real}"
      f"   waste {100 * (held - real) / held:.0f}%")
print(f"  blocks still free: {free} of {POOL_BLOCKS}")

# ---------- the second trick: sharing ----------
print("\nSHARING one system prompt across 3 users")
sys_tokens = 96
sys_blocks = -(-sys_tokens // BLOCK)
print(f"  copied per user : {3 * sys_blocks} blocks")
print(f"  shared by pointer: {sys_blocks} blocks, refcount 3")
print(f"  saved            : {(3 - 1) * sys_blocks * BLOCK} token slots")
Output
KV pool: 64 blocks x 16 tokens = 1024 token slots

CONTIGUOUS, reserve max_len up front
  r1: reserved 256 slots, will use  52  -> 204 wasted
  r2: reserved 256 slots, will use  20  -> 236 wasted
  r3: reserved 256 slots, will use 135  -> 121 wasted
  r4: reserved 256 slots, will use 208  ->  48 wasted
  served 4/4   reserved 1024   really needed 415   waste 59%

PAGED, 16-token blocks handed out only when the previous one fills
  r1:  4 blocks for  52 tokens  -> 12 wasted (last block only)
  r2:  2 blocks for  20 tokens  -> 12 wasted (last block only)
  r3:  9 blocks for 135 tokens  ->  9 wasted (last block only)
  r4: 13 blocks for 208 tokens  ->  0 wasted (last block only)
  served 4/4   held 448   really needed 415   waste 7%
  blocks still free: 36 of 64

SHARING one system prompt across 3 users
  copied per user : 18 blocks
  shared by pointer: 6 blocks, refcount 3
  saved            : 192 token slots

Reading the output

59 percent against 7 percent. That gap is the entire contribution of the paper, reproduced in forty lines of Python. The published figure for real systems was 60 to 80 percent waste, and the toy lands squarely in that range without any tuning.

The contiguous allocator filled the pool exactly. Four requests at 256 slots each is 1024, the whole pool. A fifth would have been rejected while 609 slots sat idle. That is the failure mode: rejecting users because of memory that is reserved but empty.

The paged allocator finished with 36 of 64 blocks free. Same four requests, more than half the pool still available. That free space is where extra concurrent users come from, and concurrency is what turns a memory saving into a throughput number.

Waste is bounded by the last block. r4 wasted nothing because 208 divides evenly by 16. Nobody else wasted more than 12 slots. Under paging, waste per sequence is at most BLOCK - 1 tokens, independent of how long the sequence is or how badly you guessed its length.

The PREEMPTED branch never fired here, and it matters. When a real pool runs dry mid-generation, the scheduler must evict somebody. vLLM either recomputes the evicted sequence's prefill later, or swaps its blocks to host memory. Both are expensive, and a rising preemption rate is your real capacity alarm — not GPU memory usage, which stays pinned near full by design.

Mapping this onto vLLM

The toy above is the block manager. In vLLM the pieces have these names:

  • Block table — the per-sequence list of physical block ids, exactly the tables dict above.
  • block_size — tokens per block, 16 by default.
  • gpu_memory_utilization — the fraction of the card vLLM may claim. The KV pool is what remains after weights and activations.
  • num_gpu_blocks — printed at start-up. This number is your capacity, and it is the first log line worth reading.
  • Automatic prefix caching — the sharing demonstrated at the end, keyed by a hash of block-aligned token ids.
python
from vllm import LLM

llm = LLM(
    model="Qwen/Qwen3-0.6B",
    gpu_memory_utilization=0.85,
    max_model_len=4096,          # the single biggest lever on pool size
    enable_prefix_caching=True,
)

No output block for this one, on purpose. It needs a CUDA GPU and downloads model weights, so any output printed here would be invented rather than observed. On a machine with a supported GPU the start-up log reports the resulting block count, and that number is the thing to record.

Common mistakes

Tuning block_size first. It is rarely the problem. Smaller blocks cut the last-block waste and add per-block bookkeeping to the attention kernel. The default is fine; max_model_len is where the wins are.

Setting gpu_memory_utilization to 0.98. Activation memory spikes during long prefills. The failure arrives under load, not at start-up.

Expecting prefix caching to work with a variable prefix. Sharing is keyed on identical token ids from position zero. A timestamp, a user id, or a session token at the top of the system prompt destroys every hit. Put variable content at the end.

Comparing throughput without matching context length. Halving max_model_len doubles the block pool and improves throughput on its own. Benchmarks that vary this while claiming to compare engines are meaningless.

Try it yourself

Add a fifth and sixth request to REQUESTS. The contiguous allocator will reject both. Count how many the paged allocator serves before the pool runs dry. Then change BLOCK to 1 and to 64, and watch the waste move in the direction you predict.

What to learn next

Researcher — Mathematics and papers.

The framing

Kwon et al., Efficient Memory Management for Large Language Model Serving with PagedAttention, SOSP 2023 (arxiv.org/abs/2309.06180) make one observation. KV cache allocation is structurally identical to virtual memory in an operating system, so they import the solution wholesale.

The mapping is exact enough to be worth writing down:

Operating systemLLM serving
ProcessRequest or sequence
PageKV block of $B$ tokens
Page tableBlock table
Physical frameSlot in the GPU KV pool
Copy-on-writeFork for parallel sampling and beam search
SwappingPreemption to host memory

The three classical waste categories transfer as well. Internal fragmentation becomes the partly-filled last block, bounded by $B - 1$ tokens per sequence. External fragmentation disappears entirely, since every block is the same size. Reservation waste — space held for tokens that will never be generated — disappears because allocation is on demand.

Reported results: near-zero waste, and $2$ to $4\times$ higher throughput than FasterTransformer and Orca at equal latency, with larger gains at longer sequences and higher sampling widths.

The kernel consequence

Standard attention assumes $K$ and $V$ are contiguous tensors of shape $(n, d_h)$. Under paging they are $\lceil n/B \rceil$ scattered blocks.

The kernel therefore takes a block table and gathers as it goes:

$$ o_t = \sum_{j=1}^{\lceil t/B \rceil} \mathrm{softmax_partial}!\left(q_t, K_{\text{block}(j)}\right) V_{\text{block}(j)} $$

accumulated with the online-softmax running maximum and normaliser from FlashAttention (Dao et al., 2022) so the full score vector is never materialised. Blocks are sized to fit the GPU's memory transaction granularity, which is why 16 is a reasonable default and 1 is not.

Current vLLM (V1) no longer ships the original hand-written PagedAttention kernel as the main path. It uses FlashAttention and FlashInfer backends that accept paged KV layouts directly. The memory-management idea outlived its original kernel, which is the usual fate of a good systems abstraction.

Sharing, and the reference counting it needs

Copy-on-write is what makes paging more than a fragmentation fix.

For parallel sampling with $k$ candidates from one prompt, the prompt's blocks are allocated once with refcount $k$. A block is copied only when a sequence writes into a block whose refcount exceeds one. Beam search benefits more, because beams share long internal prefixes and not only the prompt.

Cross-request sharing generalises this to automatic prefix caching: hash each block-aligned prefix of token ids, look it up in a global table, and reuse on a hit. SGLang's RadixAttention (Zheng et al., 2024) instead maintains a radix tree over token sequences, with LRU eviction. That handles partial and branching overlaps a flat hash table misses.

The correctness condition is strict. Two prefixes share a block only if every token id is equal. Not the rendered text — the ids. A chat-template change, a tokenizer version bump, or a stray space produces a silent full miss with no error anywhere.

Preemption

When the pool is exhausted and a running sequence needs a block, the scheduler must free one. Two policies:

  • Recompute. Drop the sequence's blocks; re-prefill from its token ids when it is rescheduled. Costs prefill compute, costs no bandwidth.
  • Swap. Copy blocks to pinned host memory over PCIe and back. Costs bandwidth, costs no compute.

Recompute usually wins on modern hardware, because prefill is compute-dense and PCIe is slow relative to HBM. vLLM defaults to recompute.

Preemption rate, not memory utilisation, is the meaningful saturation signal. A paged server holds memory near full by design, so a memory-usage alarm fires constantly and tells you nothing.

Where the idea went next

  • Disaggregated prefill and decode — run the two phases on separate GPU pools with different parallelism, and transfer the KV cache between them. The block abstraction is what makes the transfer expressible.
  • Hierarchical KV caching — spill cold prefix blocks to host memory or NVMe, with the block table as the indirection layer. LMCache and vLLM's connector interface build on this.
  • KV cache offload for very long context — page blocks in and out of HBM by attention demand, which is paging in the fullest sense, including the page-fault stall.

Papers

What to learn next