Efficient Memory Management for Large Language Model Serving with PagedAttention

1 Introduction

1. What limits the throughput of LLM serving, according to Kwon et al.?
   How many requests can be batched, which is bounded by GPU memory for the KV cache. Existing systems wasted most of it: only 20–38% of KV cache memory held actual token states.
   • Kwon et al., 2023, Efficient Memory Management for Large Language Model Serving with PagedAttention (Proceedings of the 29th Symposium on Operating Systems Principles (SOSP ’23)), §1
2. Why did existing serving systems waste KV cache memory?
   They stored each request’s KV cache contiguously and pre-allocated a chunk for the maximum possible length, because the output length is unknown. This causes reserved-but-unused slots, internal fragmentation (requests end shorter than reserved) and external fragmentation between chunks of different sizes, and prevents sharing between sequences.
   • Kwon et al., 2023, Efficient Memory Management for Large Language Model Serving with PagedAttention (Proceedings of the 29th Symposium on Operating Systems Principles (SOSP ’23)), §1
3. What is PagedAttention?
   An attention algorithm that lets a sequence’s keys and values live in non-contiguous memory: the KV cache is split into fixed-size blocks, like pages in an operating system’s virtual memory (blocks as pages, tokens as bytes, requests as processes), allocated on demand.
   • Kwon et al., 2023, Efficient Memory Management for Large Language Model Serving with PagedAttention (Proceedings of the 29th Symposium on Operating Systems Principles (SOSP ’23)), §1