Efficient Memory Management for Large Language Model Serving with PagedAttention

Problem

Framing

LLM serving wastes KV-cache memory through reservation, fragmentation, and duplicate prefixes, which caps batch size before FLOPs saturate. The paper closes this systems gap with PagedAttention: it virtualizes KV storage into fixed-size blocks with block tables and sharing, cutting waste to under $4\%$ and raising serving throughput by up to $24\times$ over Hugging Face Transformers.

Currently Used Methods

Foundational

• @vaswaniAttentionAllNeed2017 — standard autoregressive self-attention with per-token KV caching.
  • Limitation in context: assumes contiguous cache layout, causing serving-time fragmentation.
• @brownGPT3_2020 — large decoder-only LMs that make KV cache dominant at inference.
  • Limitation in context: does not address multi-request cache allocation efficiency.
• @daoFlashAttention2022 — IO-aware exact attention kernel for faster training and inference.
  • Limitation in context: optimizes attention compute, not KV-cache placement or sharing.
• @daoFlashAttention2_2023 — improved work partitioning for faster attention kernels.
  • Limitation in context: leaves serving throughput bottlenecked by memory waste.
• @leviathanSpeculativeDecoding2023 — reduces decoding latency with draft-and-verify generation.
  • Limitation in context: orthogonal to KV memory management during serving.

Proposed Method

Architecture

vLLM splits serving into a scheduler, a KV cache manager, CPU/GPU block allocators, and worker processes that host model shards plus cache engines. PagedAttention stores each sequence's KV cache as logical blocks mapped by a block table to non-contiguous physical blocks, enabling prefix sharing and near-zero external compaction pressure.

Loss / Objective

The paper is a serving-systems design, not a training objective paper.Its core attention computation rewrites standard attention over paged KV blocks:

where $\mathbf{K}_j = (\mathbf{k}_{(j-1)B+1}, \ldots, \mathbf{k}_{jB})$ and $\mathbf{V}_j = (\mathbf{v}_{(j-1)B+1}, \ldots, \mathbf{v}_{jB})$ are block-wise KV tensors.

Sampling Rule / Algorithm

PagedAttention computes attention blockwise, then reduces partial results across KV blocks:

This preserves exact attention while decoupling logical token order from physical memory contiguity.

Training Procedure

• No model training.
• Fixed-size KV block granularity $B$.
• CPU and GPU block allocators.
• Reference-counted shared blocks for parallel sampling and beam search.
• Copy-on-write when shared prefixes diverge.
• CPU-resident blocks support swapping under memory pressure.

Evaluation

Datasets

• ShareGPT conversation traces.
• Alpaca instruction traces.

Metrics

• Serving throughput.
• Tokens per second.
• Request latency.
• KV-cache memory waste.
• Swapping and recomputation overhead.

Headline results

• Hugging Face Transformers: up to $24\times$ higher throughput.
• Text Generation Inference: up to $3.5\times$ higher throughput.
• KV-cache waste: under $4\%$.
• ShareGPT and Alpaca workloads: latency stays lower until higher request rates.
• Parallel sampling and beam search: shared-prefix memory usage drops substantially with copy-on-write.

Ablations

• Block size: smaller blocks reduce waste but raise lookup overhead.
• Parallel sampling: block sharing sharply cuts memory versus naive duplication.
• Beam width: shared prefixes keep memory growth sublinear early in decoding.
• Swapping vs recomputation: both incur overhead; choice depends on block reuse distance.

Method Strengths and Weaknesses

Strengths

• Targets the real serving bottleneck: KV-cache capacity, not only attention FLOPs.
• Preserves exact attention semantics despite non-contiguous physical layout.
• Supports prefix sharing for parallel sampling and beam search with copy-on-write.
• Reports large end-to-end gains: up to $24\times$ over Hugging Face Transformers.

Weaknesses

• Adds block-table indirection and allocator complexity to the serving stack.
• Gains depend on cache-bound workloads with variable sequence lengths.
• Swapping and recomputation still impose measurable latency overhead under pressure.
• Paper focuses on inference systems; training-time implications are outside scope.

Suggestions from the authors

• Extend memory virtualization across multiple GPUs and nodes.
• Improve eviction and recovery policies for swapped KV blocks.
• Co-design decoding algorithms with KV sharing and paging.
• Reduce block-management overhead at extreme batch sizes.

Links

Prior Papers

• @leviathanSpeculativeDecoding2023 — alternative inference-time acceleration; useful contrast because it attacks decoding steps, not KV memory waste.

Further Papers

• @daoFlashAttention2_2023 — complementary systems optimization for attention kernels that pairs naturally with paged KV management.
• @jiangMixtral2024 — later high-throughput LLM serving workloads make KV-cache efficiency even more central.
• @dettmersQLoRA2023 — memory-efficiency work on LLM deployment complements vLLM's serving-side memory virtualization.