What is Paged KV Cache?

Paged KV cache is a memory-management approach for LLM inference that stores attention keys (K) and values (V) in small, fixed-size blocks instead of requiring one large contiguous allocation for every sequence.

The idea comes from operating-system virtual memory paging and is central to PagedAttention, introduced by the vLLM research paper.

Why is ordinary KV-cache allocation challenging?

• Prompt and generated-response lengths vary between requests.
• The cache grows as more tokens are generated.
• Reserving a large contiguous buffer can waste unused space; repeatedly allocating and freeing differently sized buffers can lead to fragmentation.
• This wasted memory limits the number of requests a GPU can serve simultaneously.

A paged cache allocates blocks as needed, so a sequence can grow without relocating a large contiguous cache buffer.

How does it work?

1. Divide the logical sequence into blocks. Each block holds K/V data for a fixed number of token positions.
2. Allocate physical blocks on demand. The blocks do not have to sit next to one another in GPU memory.
3. Track a block table. This maps the sequence's logical block positions to actual physical KV-cache blocks.
4. Read K/V through the mapping. A compatible attention kernel gathers the relevant keys and values during inference.
5. Grow or release blocks. As tokens arrive, the system allocates additional blocks; completed requests can release their allocations. Some implementations also support sharing identical cached prefixes.

Simple example

Assume each KV-cache block holds 16 tokens. A request with 35 cached tokens requires:

Logical block 0: tokens  1–16 → physical block 7
Logical block 1: tokens 17–32 → physical block 2
Logical block 2: tokens 33–35 → physical block 11

Block table: [7, 2, 11]

The three physical blocks are not contiguous. Only 13 positions in the final block are unused; the earlier two blocks are full.

This illustrates a key benefit: fixed-size block allocation limits much of the waste to the partially filled final block, although real implementations still have block-table and allocator overhead.

What are the advantages?

• Less fragmentation and over-reservation: Cache memory can be allocated incrementally in reusable blocks.
• Higher potential concurrency: Better cache utilization can let the server admit more sequences before reaching its memory limit.
• Flexible growth: Requests can generate different numbers of tokens without requiring one pre-sized contiguous region.
• Possible prefix sharing: Under supported conditions, requests can point to shared cached blocks rather than duplicating identical K/V data. Writable shared blocks require appropriate protection, such as copy-on-write.

What does it *not* do?

Paging is not KV-cache quantization. It does not inherently reduce the number of K/V elements stored for a given attention context or change their precision. Nor does it eliminate attention calculations or guarantee faster inference for every workload.

It improves how KV-cache memory is allocated, addressed, and reused. Compatible kernels and metadata lookups introduce engineering overhead, so actual throughput gains must be benchmarked.

How is it different from PagedAttention?

• Paged KV cache: The *storage organization*—K/V tensors in physical blocks with logical-to-physical mappings.
• PagedAttention: An *attention computation approach* that accesses K/V using those block mappings.

The two work together in serving systems such as vLLM.

For prerequisites, see “What is KV cache in an LLM?” and “Why does KV cache consume significant memory?”. A separate follow-up will cover paged attention implementations.

In short: Paged KV caching makes an LLM's growing attention memory more flexible by using reusable, non-contiguous blocks and a block table, reducing allocation waste and supporting more concurrent requests.

References: PagedAttention / vLLM paper, vLLM: Paged Attention kernel, and vLLM: Block table.