PagedAttention — why serving LLMs needs a virtual-memory system for the KV cache

Over the last few lessons, we have focused on inference.

We saw that decode generates one token at a time, that the KV cache prevents us from recomputing the whole prompt, that speculative decoding tries to advance several tokens per expensive target-model pass, and that quantization reduces the number of bytes that must be stored and moved.

Today we will look at a different problem:

At first this sounds like a mundane memory-allocation question.

It is not.

At high concurrency, KV-cache management can determine how many requests fit on a GPU, how much memory is wasted, and therefore how much throughput an inference server can deliver.

A major idea used by modern LLM serving systems is PagedAttention: manage KV-cache memory in small blocks, much like an operating system manages virtual memory in pages.

First, remember what the KV cache stores¶

At each Transformer layer, attention computes keys and values:

During autoregressive generation, previously computed keys and values do not change.

So after processing tokens:

we keep:

and:

When token \(T+1\) arrives, we compute only its new key and value and append them to the cache.

Conceptually:

token 1  → K1, V1
token 2  → K2, V2
token 3  → K3, V3
...
token T  → KT, VT

                 ↓

            KV cache

The cache grows as the sequence grows.

For one request this is manageable.

For thousands of simultaneous requests, it becomes a memory-allocation problem.

The naive approach: reserve one contiguous region per request¶

Suppose a server allows sequences up to:

tokens.

A simple allocator might reserve enough contiguous GPU memory for each request's maximum possible KV cache.

Imagine three users:

Request A → currently 500 tokens
Request B → currently 7,000 tokens
Request C → currently 1,200 tokens

If each receives space for 8,192 tokens, memory looks conceptually like:

A: [used 500][------------- unused 7692 -------------]

B: [used 7000][-- unused 1192 --]

C: [used 1200][----------- unused 6992 ------------]

Most of A's and C's reservations are empty.

We are holding memory for tokens that may never exist.

That is internal fragmentation.

Why we cannot simply allocate the exact final size¶

Because we do not know it.

A request may stop after:

12 tokens

or continue for:

4,000 tokens

or hit its maximum generation length.

Autoregressive generation reveals the required memory gradually.

We could repeatedly grow each contiguous allocation, but that creates another problem.

Suppose GPU memory currently looks like:

[A][B][C][free][D][free][E]

Request B needs more space.

There may be enough free memory in total, but not enough directly beside B.

Now we either:

• copy B somewhere larger,
• move other allocations,
• reserve excessive slack in advance, or
• fail the allocation.

This is external fragmentation.

The problem should sound familiar from operating systems.

The virtual-memory analogy¶

Your laptop does not require a process's logical memory to occupy one giant contiguous region of physical RAM.

Instead, memory is divided into fixed-size pages.

A process sees logical addresses:

page 0
page 1
page 2
page 3

but those pages might physically live in RAM as:

physical block 17 → logical page 2
physical block 41 → logical page 0
physical block  8 → logical page 3
physical block 29 → logical page 1

A page table records the mapping.

PagedAttention applies essentially this idea to the KV cache.

The sequence can be logically contiguous without being physically contiguous.

Break the KV cache into blocks¶

Suppose each KV block stores state for four tokens.

A 13-token sequence needs:

blocks.

Logically:

block 0 → tokens  1–4
block 1 → tokens  5–8
block 2 → tokens  9–12
block 3 → token   13

But physically those blocks might live anywhere:

logical block 0 → physical block 7
logical block 1 → physical block 2
logical block 2 → physical block 9
logical block 3 → physical block 4

So GPU memory could look like:

physical blocks:

0: request B
1: free
2: request A, logical block 1
3: request C
4: request A, logical block 3
5: request B
6: free
7: request A, logical block 0
8: request C
9: request A, logical block 2

Request A still sees one logical sequence.

The attention kernel follows its block table to find the corresponding keys and values.

Why this reduces waste¶

Suppose the block size is:

tokens.

A request only needs a new physical block when it crosses another \(P\)-token boundary.

If it stops partway through its final block, the wasted capacity is less than one block.

So instead of potentially wasting thousands of reserved token slots, the unused capacity per sequence is bounded roughly by:

token slots.

For example, with:

a finished sequence wastes at most 15 token positions in its final block.

That is a much tighter bound than reserving an entire maximum-length sequence.

A concrete memory example¶

Imagine KV state costs:

for some model configuration.

Suppose the maximum context is:

tokens.

A naive maximum reservation per request would be:

Now consider a request that actually reaches only:

tokens.

Its useful KV cache is:

A 1 GB reservation would leave roughly:

unused.

Now suppose paged allocation uses 16-token blocks.

The request needs:

blocks.

Those blocks provide room for:

tokens.

Only:

token slots are unused.

At 128 KB per token, that is about:

of final-block waste rather than hundreds of megabytes of reserved slack.

The exact numbers in real models vary substantially, but the allocator principle is the important part.

The hotel mental model¶

Imagine a hotel serving guests who refuse to tell you how many nights they will stay.

The naive strategy is:

Give every guest an entire 30-room hallway in case their family expands.

Most rooms remain empty.

Paged allocation instead says:

Give the guest one room now. When they need more space, assign another available room anywhere in the hotel.

The rooms do not need to be adjacent because the front desk maintains a table:

Guest A:
room 207
room 514
room 118
room 903

From the guest's logical perspective, these belong to one reservation.

The hotel's physical layout no longer dictates the logical layout.

That separation is the core idea.

But attention expects an ordered sequence¶

There is an obvious complication.

For a new query:

attention must access earlier keys and values in sequence order:

and:

If those tensors are scattered across physical blocks, the attention kernel must know where each logical block lives.

So each sequence maintains something like a block table:

logical KV block    physical KV block

0                   7
1                   2
2                   9
3                   4

The attention kernel uses this mapping while reading K and V.

This adds indirection.

Instead of assuming:

next logical token
=
next physical address

we now have:

logical token
→ logical block
→ block table
→ physical block
→ KV data

That indirection is the price paid for flexible allocation.

Why the extra indirection can still win¶

Scattered memory access is usually less convenient than perfectly contiguous memory.

So why accept it?

Because the alternative can waste so much GPU memory that fewer requests fit simultaneously.

Suppose contiguous allocation lets us fit:

active requests.

Paged allocation, by reducing fragmentation, might let us fit:

Those additional requests increase the number of decode tokens available for continuous batching.

From Day 46, we know larger decode batches improve weight reuse.

So better memory utilization can create a second-order performance benefit:

leads to:

which leads to:

which can lead to:

Memory management and compute efficiency are therefore coupled.

Pages also make growth cheap¶

Suppose a sequence currently owns:

logical blocks 0,1,2

and generates enough tokens to require block 3.

With contiguous allocation, we might need to find space directly after its current region or move the whole cache.

With paging, we simply find any free physical block:

free block 37

and update:

logical block 3 → physical block 37

No previous KV data needs to move.

This matters because sequences grow one token at a time.

Paged allocation matches the dynamic nature of autoregressive generation.

The block size is a tradeoff¶

Why not use one-token blocks?

That would minimize internal fragmentation.

But then a 100,000-token sequence would require 100,000 block-table entries.

The kernel would perform enormous amounts of address translation and metadata handling.

Why not use 10,000-token blocks?

The table would be tiny, but short sequences would waste huge amounts of memory.

So block size trades:

against:

Conceptually:

small blocks:
+ little wasted memory
- more block-table entries
- more bookkeeping

large blocks:
+ simpler metadata
+ longer contiguous runs
- more unused space in final blocks

As in quantization group size yesterday, granularity becomes a systems tuning parameter.

Paging becomes even more useful with shared prefixes¶

Now imagine 100 requests all begin with the same 2,000-token system prompt:

You are an enterprise support assistant...
[large shared instructions]

Naively, every request could store its own copy of the prompt's KV cache.

That means storing the same K/V tensors 100 times.

With block-based memory management, immutable prefix blocks can potentially be shared.

Conceptually:

                    ┌→ Request A private blocks
shared prefix blocks├→ Request B private blocks
                    ├→ Request C private blocks
                    └→ Request D private blocks

All four requests reference the same physical KV blocks for the common prefix.

Only after their contexts diverge do they need separate blocks.

This resembles shared memory and copy-on-write in operating systems.

Copy-on-write intuition¶

Suppose two sequences share the same prefix:

A: The quick brown fox
B: The quick brown fox

Their prefix KV blocks can be shared because the cached keys and values for those tokens are identical.

When A generates:

jumps

and B generates:

sleeps

the shared prefix remains unchanged.

Only their new blocks differ:

shared:
The quick brown fox

A private:
jumps ...

B private:
sleeps ...

This can be especially valuable for:

• repeated system prompts,
• few-shot examples reused across requests,
• beam-search branches,
• parallel sampling from one prompt,
• prefix caching.

The same paging abstraction makes all of these easier to represent.

Beam search exposes the advantage clearly¶

Suppose one sequence branches into four candidate continuations.

Before branching, all four beams share the same history.

Without sharing:

beam 1 → copy entire KV history
beam 2 → copy entire KV history
beam 3 → copy entire KV history
beam 4 → copy entire KV history

With shared blocks:

                  ┌→ beam 1 new blocks
shared history ───├→ beam 2 new blocks
                  ├→ beam 3 new blocks
                  └→ beam 4 new blocks

Only the divergent suffixes require new storage.

Again, the key idea is not attention mathematics.

It is memory ownership.

PagedAttention does not make attention mathematically sparse¶

The name can cause confusion.

PagedAttention does not inherently mean that the model attends to only a subset of tokens.

If ordinary causal attention says the current query attends to:

it still attends to those positions.

Paging changes where the K/V tensors are stored, not which logical tokens exist.

So distinguish:

from:

PagedAttention primarily changes the second.

Connect this to context parallelism¶

Earlier we learned that context parallelism distributes different sequence regions across GPUs.

PagedAttention solves a related but distinct problem.

Context parallelism asks:

Which GPU owns this part of the sequence?

Paging asks:

Which physical memory block stores this part of the sequence?

The two ideas can coexist.

A long context might be distributed across multiple GPUs, while each GPU also manages its local KV memory in blocks.

This gives us another level in the tensor-geography hierarchy:

logical token
    ↓
context-parallel owner GPU
    ↓
local KV block table
    ↓
physical HBM address

At scale, even "where is token 50,000's key vector?" can have a multi-stage answer.

Connect this to quantization¶

Yesterday we reduced KV-cache memory by storing each value with fewer bits.

Today we reduce wasted KV-cache memory by allocating storage more efficiently.

These optimizations attack different factors.

Very roughly:

Quantization attacks:

Paging attacks wasted:

So they compose naturally:

KV quantization
→ make each occupied block smaller

paged allocation
→ avoid allocating unnecessary blocks

This is a useful general way to think about optimization: factor the cost, then attack different factors independently.

Connect this to speculative decoding¶

Speculative decoding temporarily creates KV state for proposed future tokens.

Some proposals are accepted.

Others are rejected.

A block-based allocator makes temporary ownership easier to manage.

Conceptually:

committed blocks:
[0][1][2][3]

speculative blocks:
[4][5]

verification:
accept block 4
reject contents after some point

allocator:
retain what became committed
reclaim unused speculative capacity

Real implementations can be more fine-grained than this diagram, but the principle is the same.

Once inference becomes dynamic, memory allocation must become dynamic too.

The deeper lesson: serving capacity is not just model size¶

Suppose a GPU has:

of HBM.

A model's quantized weights consume:

It is tempting to say:

is available for requests.

But the useful serving capacity depends on how efficiently that remaining memory is managed.

If KV allocation wastes 30% through fragmentation or over-reservation, a large fraction of expensive HBM produces no useful tokens.

If paging reduces that waste, the server can admit more sequences without changing:

• the model,
• the GPU,
• the attention equation, or
• the numerical precision.

That is a pure systems win.

The key mental model¶

When you picture the KV cache, do not imagine one giant array per user.

Imagine an operating system managing pages.

Each request sees a clean logical history:

token 1
token 2
token 3
...
token 10,000

But underneath, the physical storage may look like:

GPU HBM:

[B7][A2][free][C1][A0][D4][B1][A3][free][A1]...

A block table turns that scattered physical memory back into a coherent logical sequence.

That gives us today's main principle:

The analogy to virtual memory is deeper than it first appears.

Operating systems learned long ago that variable-sized, dynamically growing programs are easier to manage when logical address spaces are decoupled from physical RAM.

LLM serving has rediscovered the same principle because autoregressive requests are also variable-sized, dynamically growing consumers of scarce memory.

And that is an important recurring theme in modern AI systems:

Once the neural-network math is fast enough, old computer-systems problems — memory allocation, paging, scheduling, locality, fragmentation — become AI performance problems.