PagedAttention: Optimizing KV Cache Utilization in Large Language Models

When serving Large Language Models (LLMs) in multi-user environments, memory capacity is the main bottleneck. During generation, the model saves the Key-Value (KV) history of prior tokens to avoid recomputing them. This is known as the KV Cache.

The size of the KV cache increases with the sequence length and concurrent request counts. In standard systems, KV cache memory is allocated contiguously. This introduces two major sources of waste:

• Internal Fragmentation: Allocating memory for the maximum possible sequence length up front, even if the request completes early.
• External Fragmentation: Memory gaps between requests that cannot be utilized due to size differences.

As a result, up to 60% to 80% of KV cache memory can be wasted. PagedAttention solves this by managing KV cache memory in non-contiguous pages, similar to virtual memory in operating systems.

PagedAttention Memory Management

The Mechanics of PagedAttention

PagedAttention divides the KV cache for each request into logical blocks. Each block contains the KV vectors for a fixed number of tokens (e.g. 16 tokens).

• Logical Blocks: The KV cache is represented as a sequence of logical blocks from Block 0 to Block N.
• Physical Blocks: The actual GPU memory is allocated as non-contiguous physical blocks.
• Page Table: A lookup table maps each request's logical blocks to their corresponding physical blocks.

During generation, as new tokens are generated, the system allocates physical blocks dynamically. The KV vectors are written to these blocks even if they are scattered across different parts of GPU memory.

The Math: Block Attention Calculation

When calculating attention for query token q_i, the system queries the page table to locate the physical addresses of the key vectors K_j. The attention score for block b is:

A_{i,b} = \text{Softmax}\left( \frac{q_i K_b^T}{\sqrt{d_k}} \right)

where K_b represents the key vectors stored within physical block b.

Implementing PagedAttention with vLLM

vLLM uses PagedAttention under the hood to achieve high serving throughput. Here is a Python script to start a vLLM engine:

from vllm import LLM, SamplingParams

# block_size controls how many tokens of KV cache live in one physical block.
# gpu_memory_utilization reserves the pool that PagedAttention allocates from.
llm = LLM(
    model="facebook/opt-125m",
    block_size=16,
    gpu_memory_utilization=0.85,
)

sampling_params = SamplingParams(temperature=0.8, top_p=0.95, max_tokens=64)

# Batching several prompts lets the block manager interleave them in one pass
prompts = [
    "Once upon a time in a galaxy far away,",
    "The three laws of robotics state that",
    "In the year 2145, the last library on Earth",
]

outputs = llm.generate(prompts, sampling_params)

for output in outputs:
    print(f"PROMPT: {output.prompt}")
    print(f"GENERATED: {output.outputs[0].text.strip()}")
    print("-" * 60)

Serving Advantages

• Zero Waste: Memory is allocated dynamically per block, reducing fragmentation to under 4%.
• Shared Memory (Beam Search / Multi-User): Multiple requests can share the physical blocks of a common prompt prefix (e.g. system instructions), reducing memory usage in multi-turn chats.
• Increased Throughput: By reclaiming wasted memory, vLLM can process 2x to 4x more concurrent requests than standard serving frameworks.

Conclusion

The 2x-4x throughput numbers are real, but they are throughput numbers, and it is worth being clear about what that buys you. PagedAttention raises the number of requests a GPU can serve concurrently; it does not make any single request faster. If your problem is that one user waits too long for a response, paging will not help and may marginally hurt — there is a small indirection cost on every attention lookup. It is a capacity optimization, not a latency optimization, and teams occasionally deploy vLLM expecting the wrong one.

There is also a scheduling behavior that surprises people. Because blocks are allocated on demand as generation proceeds, a batch that fit comfortably at admission can run out of physical blocks mid-generation. vLLM handles this by preempting requests and recomputing or swapping their KV cache, which shows up as sudden latency spikes for unlucky requests under load rather than a clean rejection. If your p99 looks fine in testing and terrible in production, look at preemption counts before you look at the model.

The block size is the one knob worth touching, and the tradeoff runs in both directions: larger blocks mean fewer page-table lookups but more waste in the final partially-filled block of each sequence, which matters a lot if your traffic is many short chats rather than a few long documents. The default of 16 is a sensible starting point; measure against your own sequence length distribution before changing it.

Where paging pays off most is prefix sharing. If every request in your application carries the same long system prompt or few-shot preamble, those blocks are stored once rather than per request — often a larger practical win than the fragmentation fix itself. Structuring prompts so the shared portion comes first is a free optimization that costs nothing but attention to ordering.