PagedAttention in Production: Boosting LLM Serving Throughput with Paged KV Cache

Background: Why KV Cache Becomes a Hidden Bottleneck in Inference Systems

During autoregressive generation in Transformers, each new token requires access to the Key and Value of all preceding tokens. To avoid recomputing the entire history at every step, inference systems cache these intermediate results—this is the KV Cache.

KV Cache has three defining characteristics:

1. Large: It grows linearly with the number of layers, hidden size, number of heads, context length, and batch size.
2. Dynamic: Request lengths vary, output lengths are unpredictable, and memory demands change continuously.
3. Memory-hungry: KV Cache typically resides in GPU memory, directly limiting the number of concurrent requests.

Without paged management, systems often allocate a contiguous block of memory for each request or estimate space based on maximum length. This leads to two types of waste:

• Internal fragmentation: The tail of a sequence isn’t fully filled, but the corresponding memory is already allocated.
• External fragmentation: Total memory is available, but there isn’t a large enough contiguous space for a new request.

This problem is amplified when request length distributions are highly uneven—for example, when a single service simultaneously handles short Q&A, long document summarization, RAG retrieval-augmented Q&A, and multi-turn Agent tasks. Even if the GPU appears to have free memory, the scheduler may not be able to safely add more requests.

Core Principle: Managing KV Cache as “Paged Memory”

PagedAttention’s design can be understood through three objects:

• Logical blocks: Contiguous token blocks for a request, logically speaking.
• Physical blocks: The actual KV Cache blocks allocated in GPU memory.
• Block table: A mapping from logical blocks to physical blocks.

Traditional KV Cache management is like “allocating one large contiguous array for a request.” PagedAttention is more like virtual memory in an operating system: a request sees a contiguous sequence of tokens, but the underlying memory blocks can be non-contiguous.

Request tokens: [ t0 t1 t2 t3 ][ t4 t5 t6 t7 ][ t8 t9 ... ]
Logical block id: [ block 0 ][ block 1 ][ block 2 ]
Block table:
  block 0 -> physical block 17
  block 1 -> physical block 03
  block 2 -> physical block 42

As a request continues generating tokens, the system allocates new blocks on demand. When a request finishes, its blocks are returned to the pool. When multiple requests share the same prefix, blocks can also be reused.

The benefit is not that “the attention algorithm’s complexity becomes constant,” but rather improved memory management efficiency. It allows the system to more reliably convert GPU memory into effective batch capacity, rather than wasting it on fragmentation and conservative reservations.

Relationship with Continuous Batching: PagedAttention is Not a Standalone Optimization

PagedAttention is often mentioned alongside continuous batching, but they are not the same thing.

Technique	Problem Solved
Continuous batching	Scheduling: when a request completes, a new request can immediately enter the batch without waiting for the entire batch to finish
PagedAttention	Memory organization: KV Cache is dynamically allocated and freed in blocks as requests enter, exit, and grow

When combined, the server can perform more aggressive dynamic scheduling:

Incoming requests
  ↓
Scheduler groups active sequences
  ↓
Paged KV blocks allocated on demand
  ↓
Attention kernel reads blocks by block table
  ↓
Completed requests release blocks
  ↓
New requests fill freed capacity

Without efficient KV Cache management, continuous batching alone can still be blocked by memory fragmentation. Without proper scheduling, PagedAttention alone may not translate memory efficiency into throughput gains.

Engineering Implementation: Suitable Production Scenarios

PagedAttention is most beneficial for the following types of services:

1. Online Inference with Highly Variable Request Lengths

For example, a single LLM API handling:

• Short instruction Q&A
• Long document summarization
• RAG retrieval-augmented Q&A
• Multi-turn conversations
• Agent tool-calling chains

The context length distribution for such workloads is unstable, and traditional contiguous memory allocation easily wastes space.

2. High-Concurrency, Throughput-Prioritized Model Serving

If the goal is to maximize throughput on a single or multiple GPUs, PagedAttention helps the system accommodate more active sequences. It doesn’t guarantee each request is faster, but it generally improves overall capacity and stability.

3. Long Context and Prefix Reuse Scenarios

Long system prompts, fixed templates, multi-turn conversations, and RAG pipelines often involve shared prefixes. Paged KV Cache provides a foundation for block-level sharing, reuse, and cache eviction strategies.

4. Multiple Output Sampling

During parallel sampling, multiple candidate outputs may share the same prompt’s KV Cache. Block-level sharing reduces redundant storage and improves parallel generation efficiency.

Deployment Architecture: From “Running” to “Controlled”

In production, don’t just start up vLLM, TGI, or TensorRT-LLM and call it done. A more robust approach is to integrate PagedAttention into the overall inference architecture.

Inference Service Layer

The inference service needs to define:

• Maximum model context length
• Maximum batch token count
• Maximum number of concurrent sequences
• Block size
• Scheduling strategy for prefill and decode phases
• Whether to enable prefix caching or KV cache reuse

Routing Layer

If there are multiple inference instances, avoid purely random routing. For shared system prompts, multi-turn conversations, or tasks with the same knowledge base, consider KV-aware routing to route requests more likely to hit the cache to the same instance or group of instances.

Rate Limiting Layer

KV Cache is not an infinite resource. Rate limiting should not be based solely on QPS but should also consider:

• Prompt token count
• Max output token count
• Current GPU memory pressure
• Whether the request is long-context
• Whether streaming output is allowed

A more reasonable approach is to establish a token budget rather than just limiting the number of requests.

Common Misconceptions

Misconception 1: PagedAttention Equals Lower Latency for All Requests

PagedAttention’s primary benefits are memory efficiency and throughput capacity. A single short request under low concurrency may not be noticeably faster. In fact, due to the overhead of block table lookups and kernel adaptations, there might be additional cost in some scenarios.

When evaluating effectiveness, don’t just look at single-request benchmarks. Look at production workload metrics:

• TTFT (Time to First Token)
• TPOT (Time per Output Token)
• tokens/s
• GPU utilization
• OOM count
• p95 / p99 latency

Misconception 2: Smaller Block Size is Always Better

Smaller blocks mean less memory waste and finer reuse granularity. However, blocks that are too small can increase management overhead and potentially impact kernel access efficiency. Block size is a classic trade-off:

Block Size	Potential Benefits	Potential Costs
Smaller	Finer-grained allocation, less tail waste, easier local reuse	More metadata, higher scheduling and access overhead
Larger	Potentially more kernel-friendly access, lower management overhead	Higher tail waste, coarser reuse hit conditions

The actual choice should be tested based on the model, context length distribution, concurrency pattern, and framework defaults.

Misconception 3: Enabling PagedAttention Eliminates the Need for Capacity Planning

PagedAttention reduces waste but doesn’t change the fact that KV Cache grows linearly. Long contexts, long outputs, and high concurrency will still make GPU memory a bottleneck. Capacity planning is still necessary before deployment.

Use the following simplified formula for initial estimation:

KV cache memory ≈ layers × 2 × hidden_size × tokens × bytes_per_element × batch_factor

Here, 2 accounts for Key and Value. Real implementations are also affected by GQA/MQA, quantization, tensor parallelism, padding, block size, and framework memory pools, so this formula is only for directional guidance.

Deployment Checklist

1. Workload Profiling

Before deployment, profile real requests—don’t just use averages:

• Prompt token p50 / p95 / p99
• Output token p50 / p95 / p99
• Percentage of multi-turn conversations
• Percentage of RAG requests
• Percentage of shared system prompts
• Percentage of streaming outputs

2. Stress Test Matrix

At minimum, cover the following combinations:

Scenario	Key Observation
Short prompt + short output	Is scheduling overhead acceptable?
Long prompt + short output	TTFT and prefill pressure
Short prompt + long output	KV growth during decode phase
Long prompt + long output	OOM, p99 latency, throughput ceiling
Multi-turn conversation	Prefix reuse and cache hits
RAG template	Reuse opportunities for system prompts and retrieved content

3. Monitoring Metrics

At a minimum, monitor:

• GPU memory utilization
• Active sequences
• Waiting queue length
• Prefill tokens/s
• Decode tokens/s
• TTFT p50 / p95 / p99
• TPOT p50 / p95 / p99
• Cache hit ratio
• Block allocation failure
• Eviction count
• OOM count
• Request cancellation rate

4. Rollback Strategy

Inference system changes should retain a rollback path:

• Keep old serving configurations
• Control the canary ratio for individual instances
• Route long-context requests separately
• Set conservative upper limits on max tokens
• Automatically degrade when OOM or p99 spikes occur

Applicability Boundaries

PagedAttention may have limited benefits in the following scenarios:

1. Low concurrency, short context services: Memory fragmentation is not a major issue.
2. Strict pursuit of lowest per-request latency: Requires simultaneous optimization of kernel, batching, model quantization, and scheduling.
3. Random requests with little cache reuse: Block sharing has limited value, though on-demand allocation may still be useful.
4. Framework or model with special attention types: Need to verify if the current serving framework supports the corresponding model architecture.

For new models, especially those with hybrid attention, sliding window attention, Mamba-like structures, or special positional encodings, check the framework documentation for compatibility notes. Don’t simply assume all models will benefit equally.

References

• Efficient Memory Management for Large Language Model Serving with PagedAttention
• vLLM: Easy, Fast, and Cheap LLM Serving for Everyone
• vLLM PagedAttention Design
• TGI PagedAttention
• TensorRT-LLM KV Cache Reuse
• New KV Cache Reuse Optimizations in NVIDIA TensorRT-LLM
• vLLM Hybrid KV Cache Manager