Paged Attention: Managing the KV Cache Like Virtual Memory

The KV Cache worked out what the cache holds: for every token of every running request, a key and a value per layer and key-value head. For Qwen2.5-1.5B that is 28 KiB per token, and a server holds thousands of tokens per request across dozens of requests. How many requests fit at once, and so the throughput, is set by how well this memory is used. The difficulty is that the cache grows one token per decode step, by an amount nobody knows in advance: the answer ends when the model emits its end token. Paged attention (Kwon et al., 2023) stores the cache the way an operating system stores a program’s memory: in fixed-size blocks placed anywhere, found through a table. This post measures the waste it removes, builds a paged cache for a real model, and follows what the block table makes possible.

Table of contents

Where the memory goes

A server stores each request’s cache somewhere, and the simple way is one contiguous array per request, since attention kernels read keys and values as one tensor. A contiguous array can’t grow in place once other requests sit after it, so it has to be reserved at its final size when the request starts. The final size is unknown. The paper names three resulting losses: slots reserved for tokens not generated yet, which are eventually used but block other requests until then; internal fragmentation, slots reserved past where the answer ends, which are never used; and external fragmentation, gaps between reservations that are too small for the next request.

How much is lost depends on the lengths real requests have. The paper used two datasets, ShareGPT (conversations people shared from ChatGPT, long prompts and long answers) and Alpaca (short instructions), and compared its paged cache against three versions of a contiguous one, which differ in how much they know about the answer’s length. The same comparison, on 5,000 requests from each dataset with this series’ tokenizer (lm.py loads Qwen2.5-1.5B-Instruct and its tokenizer, as in Decoding). The heart of the comparison:

reserve = {
    "max": lambda p, a, held: MAX,
    "pow2": lambda p, a, held: p + 2 ** math.ceil(math.log2(a)),
    "oracle": lambda p, a, held: p + a,
    "paged": lambda p, a, held: BLOCK * math.ceil(held / BLOCK),
}
for name, pairs in (("ShareGPT", sharegpt()), ("Alpaca", alpaca())):
    reqs = lengths(pairs)
    json.dump(reqs, open(f"{name.lower()}_lengths.json", "w"))
    p_mean = sum(p for p, a in reqs) / N
    a_mean = sum(a for p, a in reqs) / N
    print(f"{name}: {N} requests, prompt {p_mean:.0f} tokens on average, answer {a_mean:.0f}")
    for way, r in reserve.items():
        held = reserved = 0
        for p, a in reqs:
            for t in range(1, a + 1):
                held += p + t
                reserved += r(p, a, p + t)
        steps = sum(a for p, a in reqs)
        print(f"  {way:6s} real tokens {held / reserved:6.1%} of reserved slots; "
              f"{reserved / steps:6.0f} slots per running request, {int(15_700 // (reserved / steps)):4d} running at once")

Full script: waste.py, with the pinned dataset downloads, tokenizing and filtering.

ShareGPT: 5000 requests, prompt 220 tokens on average, answer 204
  max    real tokens  17.6% of reserved slots;   2048 slots per running request,    7 running at once
  pow2   real tokens  47.7% of reserved slots;    757 slots per running request,   20 running at once
  oracle real tokens  63.0% of reserved slots;    573 slots per running request,   27 running at once
  paged  real tokens  98.0% of reserved slots;    369 slots per running request,   42 running at once
Alpaca: 5000 requests, prompt 18 tokens on average, answer 58
  max    real tokens   3.4% of reserved slots;   2048 slots per running request,    7 running at once
  pow2   real tokens  41.9% of reserved slots;    168 slots per running request,   93 running at once
  oracle real tokens  57.0% of reserved slots;    124 slots per running request,  127 running at once
  paged  real tokens  90.4% of reserved slots;     78 slots per running request,  201 running at once

Reserving the model’s whole window wastes most of the memory: a ShareGPT request ends with 424 tokens on average, of its 2,048 slots, and an Alpaca request with 76. Knowing the answer’s length to within a factor of two, which no server does, still leaves half the reservation empty, and even an exact prediction leaves 37% (ShareGPT) or 43% (Alpaca) empty, because a request reserves its final length on its first step and fills it one token per step. With 16-token blocks, the only empty slots are in each request’s last block, on average 7.5 of them. The result is concurrency. In the 15.7K token slots the paper’s 13B model had on one GPU (12 GiB of KV cache on a 40 GB A100, at 800 KiB per token), 7 requests fit if each reserves the window, and 42 ShareGPT requests or 201 Alpaca requests with paging; against an exact-length reservation (27 and 127), paging fits about 1.6 times as many.

The simulation simplifies in three ways. It averages over decode steps, so long answers weigh more; it leaves out prefill; and it places every contiguous reservation perfectly, with no gaps between them, which favors the contiguous schemes. Its concurrency figures are averages in a steady state, not a promise: a server that admits requests on their current sizes can still run out of memory as answers grow, the subject of a section below. The lengths also differ from the paper’s (its Figure 11 gives ShareGPT means of 161 prompt and 338 answer tokens, against 220 and 204 here, from a different tokenizer, dataset version and filtering); the comparison between schemes is the point.

The paper measured the same thing inside running systems (its Figure 2): of the KV memory in three variants of its own reimplementation of Orca, a serving system that reserves contiguously (Max, Pow2 and Oracle, the schemes above), 20.4%, 26.8% and 38.2% held real tokens, against 96.3% for vLLM. The Pow2 and Oracle figures are lower than the simulation’s: they include external fragmentation, which the simulation leaves out. The Max figure is a little above even the simulation’s ShareGPT number, 17.6%. The paper doesn’t say which of its two datasets Figure 2 measures; its ShareGPT trace has longer answers (a mean of 338 tokens against 204 here), which would fill more of the 2,048-token window. The ordering is the same.

Paging, from operating systems

The problem isn’t new. A program sees its memory as one contiguous range of addresses, but physical memory is shared by many programs that start, grow and finish at different times. Since the Atlas computer at the University of Manchester (Kilburn et al., 1962), operating systems have solved this by paging: memory is divided into fixed-size pages, each program’s addresses are divided the same way, and a page table per program maps each of its pages to wherever a physical page was free. A program’s pages needn’t be adjacent, nothing is reserved ahead, and the only waste is the unused end of the last page.

Paged attention makes the same move for the KV cache:

With a block of $b$ tokens, a sequence of $S$ tokens needs $\lceil S / b \rceil$ blocks and wastes at most $b - 1$ slots, whatever the longest answer could have been. vLLM’s default block size is 16 (as of vLLM v0.31.0).

A paged KV cache, in code

The cache below follows vLLM’s organization (the order of dimensions inside a block varies between vLLM’s attention backends). Each layer has a pool of blocks, [blocks, key-value heads, 16 tokens, head dimension], for keys and the same for values; a block number refers to the same position in every layer’s pool, so one block table per sequence serves all 28 layers. Before each forward pass the sequence reserves slots for its new tokens (vLLM’s scheduler does this, before the model runs). Each layer then writes the new keys and values into those slots and reads the sequence’s blocks back in table order to attend over them. The class plugs into Hugging Face’s cache interface, so the model itself is unchanged. A sequence reserves its slots, and forks by sharing its blocks:

class Sequence:
    def __init__(self, pool):
        self.pool, self.table, self.n = pool, [], 0   # n: tokens whose keys and values are stored

    def reserve(self, new):
        """Make room for `new` more tokens: copy a shared last block before
        writing into it (copy-on-write), then add blocks as needed."""
        p = self.pool
        if self.n % BLOCK and p.refs[self.table[-1]] > 1:
            old, b = self.table[-1], p.alloc()
            p.k[:, b], p.v[:, b] = p.k[:, old], p.v[:, old]
            p.release(old)
            self.table[-1] = b
            p.copies += 1
        while len(self.table) * BLOCK < self.n + new:
            self.table.append(p.alloc())

    def fork(self):
        """A second sequence sharing every block of this one."""
        child = Sequence(self.pool)
        child.table, child.n = list(self.table), self.n
        for b in self.table:
            self.pool.refs[b] += 1
        return child

    def free(self):
        for b in self.table:
            self.pool.release(b)
        self.table = []

and each layer writes its new keys and values through the table and reads the sequence’s blocks back in order:

class PagedLayer(DynamicLayer):
    def __init__(self, seq, layer):
        super().__init__()
        self.seq, self.layer, self.is_initialized = seq, layer, True

    def update(self, k, v, *args, **kwargs):          # k, v: [1, kv_heads, new tokens, head_dim]
        s, p = self.seq, self.seq.pool
        pos = torch.arange(s.n, s.n + k.shape[2])
        table = torch.tensor(s.table)
        blocks, offsets = table[pos // BLOCK], pos % BLOCK
        p.k[self.layer, blocks, :, offsets] = k[0].transpose(0, 1)
        p.v[self.layer, blocks, :, offsets] = v[0].transpose(0, 1)
        total = s.n + k.shape[2]                      # gather this sequence's blocks, in order
        used = table[: -(-total // BLOCK)]
        K = p.k[self.layer, used].transpose(0, 1).flatten(1, 2)[:, :total]
        V = p.v[self.layer, used].transpose(0, 1).flatten(1, 2)[:, :total]
        return K[None], V[None]

    def get_seq_length(self):
        return self.seq.n

Full script: paged.py, with the block pool and the step function.

The test: two prompts decoded greedily for 100 tokens each, taking turns so their blocks interleave in one pool, then decoded again with Hugging Face’s ordinary contiguous cache:

prompts = ["The KV cache stores", "Paged attention borrows an idea from operating systems:"]
seqs = [Sequence(pool) for _ in prompts]
paged = [[] for _ in prompts]
nxt = [encode(p) for p in prompts]
for t in range(100):
    for i, s in enumerate(seqs):                         # take turns, one step each
        logits = step(model, s, nxt[i])
        paged[i].append(int(logits.argmax()))
        nxt[i] = torch.tensor([paged[i][-1]], device=DEVICE)

Full script: same.py, with the contiguous run and the comparison. All of this post’s scripts, including the GPU ones (same.py, share.py and the kernel benchmark kernel.py), take about 2 minutes in all on the Apple laptop, after the downloads.

one block: 16 tokens x 28 layers x K and V x 2 heads x 128 dimensions x 2 bytes = 458,752 bytes
prompt 0: 103 tokens in blocks [0, 3, 5, 7, 9, 11, 13]; same 100 tokens as the contiguous cache: True
prompt 1: 110 tokens in blocks [1, 2, 4, 6, 8, 10, 12]; same 100 tokens as the contiguous cache: True
block size 16; 50 of 64 blocks free
' the ability to request a certain amount of data from a database, and then receive it in a batch. This is a way to improve the performance of a database system. In the context of a database'

The two sequences’ blocks alternate through the pool, as in the figure at the top, and every token matches the contiguous cache. (To stay short, this cache runs one sequence per forward pass. vLLM runs every scheduled sequence in one pass, as one flat batch of tokens, with a slot mapping that says where each token’s keys and values go.) The attention is the same computation; only where its inputs are stored has changed. One block of this model is 448 KiB, so the 7 blocks of a 103-token sequence take 3.1 MiB, of which 9 slots, 0.25 MiB, are empty.

This version copies the blocks back into one tensor before attending, which a real server can’t afford: reading the blocks, writing the copy and reading it again roughly triples the memory traffic of a step that is already limited by memory (How a GPU Runs Deep Learning). The point of the paper’s kernel is to attend over the blocks where they lie.

Attention over scattered blocks

At decode time each sequence contributes one query, which attends over all of its cached keys and values. A paged kernel does the same reads as a contiguous one, from different addresses: for each cached token it looks up the token’s block in the table and reads the key at that block’s address. The kernel below does this on the Apple laptop GPU used throughout, in Metal, for 16 sequences with 4,096 cached tokens each and Qwen2.5-1.5B’s attention shapes, at block sizes from 1 to 256, with the blocks in order and scattered at random, against a contiguous cache addressed directly, with no table.

The one change paging makes to the kernel is where a token’s key and value are found:

uint row(device const int* table, uint seq, uint h, uint t) {      // where token t's key or value starts
#if NO_TABLE                                         // the contiguous cache: [sequences, kv heads, S, D]
    return ((seq * NK + h) * S + t) * D;
#else
    uint b = table[seq * NB + t / BLOCK];
    return ((b * NK + h) * BLOCK + t % BLOCK) * D;
#endif
}

and the loop that uses it, each SIMD group reading a 256-byte row per token and updating a running softmax for the 6 query heads that share it:

    for (uint t = slice * SLICE + sg; t < (slice + 1) * SLICE; t += 4) {
        uint r = row(table, seq, h, t);
        float4 k4 = float4(((device const half4*)(k + r))[lane]);
        float4 v4 = float4(((device const half4*)(v + r))[lane]);
        for (uint g = 0; g < G; g++) {                       // running softmax, per query head
            float s = simd_sum(dot(qv[g], k4));
            float mn = max(m[g], s), a = exp(m[g] - mn), e = exp(s - mn);
            l[g] = l[g] * a + e; acc[g] = acc[g] * a + e * v4; m[g] = mn;
        }
    }

Full script: kernel.py: the Metal source, the merge and copy kernels, and the timing.

16 sequences x 4096 cached tokens, 64 MiB of keys and values per step
contiguous, no table: attention 1.16 ms (58 GB/s read), max error vs PyTorch 5.2e-08; copying alone 1.60 ms (84 GB/s read and written)
        attention, time vs contiguous     copying alone                max error
block   in order   scattered               in order   scattered        vs PyTorch
    1      1.00x      1.02x                  1.00x      1.01x           5.2e-08
    2      0.99x      1.00x                  1.00x      1.02x           5.2e-08
    4      1.00x      1.00x                  1.00x      1.01x           5.2e-08
    8      1.01x      1.01x                  1.00x      1.00x           5.2e-08
   16      1.00x      0.99x                  0.99x      1.00x           5.2e-08
   32      1.00x      1.00x                  0.99x      1.00x           5.2e-08
   64      1.00x      0.99x                  0.99x      1.00x           5.2e-08
  128      1.00x      0.98x                  1.00x      0.99x           5.2e-08
  256      1.01x      0.99x                  1.00x      1.00x           5.2e-08

With the laptop otherwise idle, the attention kernel read keys and values at 58 GB/s, and the plain copy, counting what it reads and writes, ran at 84 GB/s, against the 92 GB/s How a GPU Runs Deep Learning measured for a copy on this GPU. At every block size, in order or scattered, both stayed within 2% of the contiguous cache, and the attention matched PyTorch’s to within 5.2e-8 throughout. The indirection is nearly free here because a token’s key is a 256-byte row, read whole by one SIMD group: even a block of one token is a full, aligned read, and the table adds one small integer per token, which stays in cache. Two limits on that conclusion. The attention kernel runs at about two thirds of the copy’s bandwidth, so part of its time is arithmetic, which could hide a slower memory pattern; the copy, which does no arithmetic, is the stronger evidence, and it shows no cost either. And this benchmark has none of the other costs the paper named for its kernel, “accessing the block table, executing extra branches, and handling variable sequence lengths”: every sequence here has exactly 4,096 tokens. It is one Apple GPU, not a data-center one.

The paper’s own kernel, in 2023, measured 20 to 26% slower than FasterTransformer’s contiguous attention kernel (its §7.1), a cost its larger batches more than repaid: attention is only part of each step, and the throughput figures below include it. vLLM (as of v0.31.0) no longer ships that kernel on NVIDIA GPUs: its default attention backends, FlashAttention and FlashInfer, accept a block table directly, so the paged layout is now an input format of the fastest kernels rather than a kernel of its own (see FlashAttention).

Choosing the block size

Small blocks waste less of the last block; large blocks mean fewer table entries to look up and longer contiguous runs for the kernel to read. And a cached prefix, below, is reused only in whole blocks. The same requests as before, at eight block sizes:

for size in (1, 4, 8, 16, 32, 64, 128, 256):
    use, blocks = [], []
    for reqs in traces.values():
        held = reserved = 0
        for p, a in reqs:
            for t in range(1, a + 1):
                held += p + t
                reserved += size * math.ceil((p + t) / size)
        use.append(held / reserved)
        blocks.append(sum(math.ceil((p + a) / size) for p, a in reqs) / len(reqs))
    print(f"{size:4d}    {use[0]:7.1%}    {use[1]:7.1%}      {blocks[0]:8.1f} {blocks[1]:8.1f}      "
          f"{85 // size * size:3d}")

Full script: blocksize.py.

block   real tokens / reserved     blocks per request     B's 85 shared tokens
size    ShareGPT     Alpaca        ShareGPT   Alpaca      reused from the cache
   1     100.0%     100.0%         424.0     75.5       85
   4      99.6%      97.9%         106.4     19.2       84
   8      99.0%      95.3%          53.4      9.9       80
  16      98.0%      90.4%          27.0      5.2       80
  32      95.9%      82.4%          13.7      2.8       64
  64      92.0%      68.7%           7.1      1.7       64
 128      84.9%      48.8%           3.8      1.1        0
 256      73.0%      27.2%           2.2      1.0        0

Up to 16, the waste stays within 2% on ShareGPT and 10% on Alpaca, while the table shrinks sixteenfold from one entry per token. Beyond 32 the short Alpaca requests lose fast: most of them fit in one or two blocks, mostly empty. The paper ran this ablation on throughput (its §7.2, sizes 1 to 256): on ShareGPT, sizes 16 to 128 did best, on Alpaca 16 and 32, and it chose 16 as “large enough to efficiently utilize the GPU and small enough to avoid significant internal fragmentation in most workloads”. Its reason against very small blocks is the kernel: with them, vLLM “may not fully utilize the GPU’s parallelism”.

Sharing blocks: parallel sampling and copy-on-write

A block table is a list of block numbers, so two tables can list the same block. That makes sharing cheap. When a request asks for several samples of one prompt (parallel sampling, or best-of-n), the prompt’s keys and values are the same for every sample: compute them once and let every sample’s table point at them. A block shared this way is read-only. A sequence about to write into a shared block first copies it, the copy-on-write an operating system uses for the pages of a forked process; a reference count per block says whether anyone else still uses it. Four samples of one prompt in the style of The Notebook Assistant, End to End, checked against four separate contiguous caches with the same random seeds. The prompt is prefilled once, and the other three samples fork from it:

first = Sequence(pool)
logits = step(model, first, prompt)
print(f"prompt: {len(prompt)} tokens in {len(first.table)} blocks, the last one "
      f"{len(prompt) % BLOCK} of {BLOCK} full")
seqs = [first] + [first.fork() for _ in range(N - 1)]
gens = [torch.Generator().manual_seed(i) for i in range(N)]
paged = [[sample(logits, g)] for g in gens]
for t in range(NEW - 1):
    for s, out, g in zip(seqs, paged, gens):
        out.append(sample(step(model, s, torch.tensor(out[-1:], device=DEVICE)), g))

Full script: share.py, with the prompt, the block counts and the check against separate caches.

prompt: 44 tokens in 3 blocks, the last one 12 of 16 full
4 samples of 64 tokens: 22 blocks in use, against 28 without sharing (21% fewer); 3 copy-on-write copies
tables:
  [0, 1, 3, 6, 10, 14, 18]
  [0, 1, 4, 7, 11, 15, 19]
  [0, 1, 5, 8, 12, 16, 20]
  [0, 1, 2, 9, 13, 17, 21]
each sample the same as without sharing: [True, True, True, True]
  'A KV (Key-Value) cache needs its own memory manager because KV caches are typically small '
  "A KV (key-value) cache needs its own memory manager because the cache's memory usage and m"
  "A KV (Key-Value) cache needs its own memory manager to efficiently manage the cache's memo"
  'A Key-Value (KV) cache typically needs its own memory manager because it often operates at'

The samples are token for token the ones separate caches produce. The prompt’s two full blocks are stored once instead of four times; its third block was 12 of 16 full, so each sample’s first token went into it, and the first three to write copied it, while the fourth found itself the only user and wrote in place. Here the saving is 21%, small because the prompt is short next to four 64-token answers. The paper measured 6.1 to 9.8% memory saved by parallel sampling on Alpaca and 16.2 to 30.5% on ShareGPT (OPT-13B, its §6.3). Beam search shares more, since beams also share most of what they generate: 37.6 to 55.2% and 44.3 to 66.3%. Sharing is also why the paper’s throughput gain grew with the number of samples and beams.

Prefix caching: blocks named by their prefix

Sharing within one request extends across requests. Many requests begin with the same tokens: a system prompt, tool definitions, a long document asked several questions. If a block’s keys and values stay in the pool after its request finishes, the next request with the same beginning can point at them instead of recomputing them. Prompt Caching measured what that saves; here is how a server finds the blocks.

A block’s keys and values depend on its own tokens and on every token before it, so a block is named by both: vLLM hashes each full block as hash(parent block's hash, this block's token ids, extra keys), with SHA-256 by default and extra keys such as a LoRA adapter’s name (vLLM’s kv_cache_utils.py, as of v0.31.0). A new request hashes its full blocks in order and reuses them until the first hash it hasn’t seen. Three requests to the Notebook Assistant, with its real system prompt:

def block_hashes(ids):
    parent, out = b"", []
    for i in range(0, len(ids) - len(ids) % BLOCK, BLOCK):        # full blocks only
        parent = hashlib.sha256(pickle.dumps((parent, tuple(ids[i:i + BLOCK])))).digest()
        out.append(parent)
    return out

Full script: prefix.py, with the system prompt and the three requests.

A: 96 tokens, 6 full blocks; tokens shared with A from the start:  96; blocks found in the cache: 0, prompt tokens not recomputed: 0
B: 96 tokens, 6 full blocks; tokens shared with A from the start:  85; blocks found in the cache: 5, prompt tokens not recomputed: 80
C: 110 tokens, 6 full blocks; tokens shared with A from the start:   3; blocks found in the cache: 0, prompt tokens not recomputed: 0

Request B shares its first 85 tokens with A and reuses 80: five whole blocks, while the 5 shared tokens in the sixth block are recomputed, since only full blocks are cached. Request C differs only by a date in front, and reuses nothing: only its first 3 tokens (the chat template’s opening) match A’s, so its first block’s hash differs, and with it every block’s hash after. (vLLM also always recomputes a prompt’s last token, even on a full hit, to get the logits for the first generated token.) That is the rule Prompt Caching gave for ordering a prompt, stable content first and anything that changes per request last, seen from the server’s side. Cached blocks with no current user are evicted least recently used first. SGLang (SGLang and RadixAttention) organizes the same reuse as a radix tree over tokens instead of a table of block hashes.

When memory runs out

Paging doesn’t create memory. With no reservation, a server admits requests on what they hold now, and as their answers grow the pool can run out mid-step. Something must then give up its blocks. The paper evicts a whole sequence group at once (all or nothing, since every block of a sequence is needed for its next token) and either swaps its blocks to CPU memory or frees them and recomputes the cache later from the tokens, which is one prefill. Its measurements found recomputation never more than 20% slower than swapping, and faster for small blocks (§7.3). vLLM (as of v0.31.0) only recomputes: a preempted request goes back to the front of the waiting queue with its blocks freed. vLLM Architecture follows the scheduler that makes these choices.

What paging bought

The paper’s headline is throughput: 2 to 4 times as many requests per second as FasterTransformer and Orca at the same latency, on OPT models from 13B to 175B and LLaMA-13B. The gain is batching. Decoding one token reads all of the weights whatever the batch (The KV Cache), so more sequences in each step means more tokens for the same weight traffic, until the step becomes compute-bound. The paper’s Figure 13 shows vLLM keeping 2.2 times as many requests in flight as the oracle version of Orca, the one that knows every length in advance, and 4.3 times as many as the version that reserves the whole window (OPT-13B on ShareGPT, at 2 requests a second): more than the simulation’s 1.6 times over an exact reservation, since the paper’s Orca also loses memory to external fragmentation.

The figures often quoted with vLLM, “up to 24 times HF Transformers” and “3.5 times TGI”, come from the launch blog post, not the paper, under different settings: 14 to 24 times HF and 2.2 to 2.5 times TGI with one sample per request, 8.5 to 15 times HF and 3.3 to 3.5 times TGI with three (LLaMA-7B and 13B, on A10G and A100 GPUs). The baseline matters: HF Transformers batched requests statically, so part of that gap is continuous batching, which TGI also had (vLLM Architecture covers it). The “under 4% waste” in the blog matches the paper’s 96.3%.

Limits, and an alternative

• Paging bounds the waste per sequence, not per pool. A server still needs a policy for which requests to admit and when to preempt, and a pool full of long requests still fits few of them. Shrinking each token’s cache is a different lever: fewer key-value heads (How LLM Architecture Evolved) or fewer bits and fewer tokens (KV Cache Compression). They multiply with paging.
• Reuse is block-aligned and exact. A prefix is reused in whole blocks, and only up to the first differing token.
• The kernel must understand the table. Every attention kernel has to take a block table, and code written for contiguous tensors doesn’t run on a paged cache unchanged. vAttention (Prabhu et al., 2025) argues for the other choice: keep each request’s cache contiguous in virtual memory and map physical pages on demand with the GPU driver’s virtual-memory API, so unmodified kernels work; it reports up to 1.23 times the throughput of the paged kernels of FlashAttention and FlashInfer. It is the operating system’s own mechanism, used directly.

Where this leads

• vLLM Architecture follows vLLM’s scheduler: continuous batching, chunked prefill and preemption on top of this pool.
• SGLang and RadixAttention turns prefix reuse into a radix tree shared across requests.

Takeaways

• A contiguous KV cache must be reserved before the answer’s length is known. On ShareGPT requests, real tokens filled 17.6% of a 2,048-token reservation, and 63% even with the exact length known in advance.
• Fixed-size blocks found through a block table, an operating system’s paging applied to the cache, leave empty only the last block of each sequence: 98% of slots held real tokens on ShareGPT and 90% on Alpaca, so 6 to 29 times as many requests fit in the paper’s memory budget as when each reserves the whole window, and about 1.6 times as many as with exact-length reservations.
• Paging changes storage, not computation: Qwen2.5-1.5B with a paged cache produced the same tokens as with a contiguous one.
• The block size trades the last block’s waste against table length and kernel efficiency; 16 is vLLM’s default.
• Block tables make sharing a matter of pointing at the same block: parallel samples share their prompt with copy-on-write, and prefix caching names each full block by a hash of everything before it, so reuse stops at the first differing token.

References

Start with Kwon et al.: §3 for the three kinds of waste, §4 for the design, §7 for the block size and the cost of the kernel.

• Kwon et al., Efficient Memory Management for Large Language Model Serving with PagedAttention (SOSP, 2023): the design of paged attention, the waste measurements of Figure 2, the kernel’s cost (§7.1) and preemption (§7.3).
• Kwon et al., vLLM: Easy, Fast, and Cheap LLM Serving with PagedAttention (vLLM blog, 2023): the launch post, with the comparison against HF Transformers and TGI.
• vLLM documentation, Automatic Prefix Caching, and the block hashing in vllm/v1/core/kv_cache_utils.py.
• Prabhu, Nayak, Mohan, Ramjee and Panwar, vAttention: Dynamic Memory Management for Serving LLMs without PagedAttention (ASPLOS, 2025): the alternative of contiguous virtual memory with pages mapped on demand.
• Kilburn, Edwards, Lanigan and Sumner, “One-Level Storage System”, IRE Transactions on Electronic Computers EC-11(2), 1962: the Atlas computer’s paging; see the IEEE milestone page for the history.
• Arpaci-Dusseau and Arpaci-Dusseau, Operating Systems: Three Easy Pieces, the chapters on paging, if the analogy is new.
• The workloads: ShareGPT (the file vLLM’s benchmarks use) and Alpaca.