PagedAttention: Managing AI Memory Efficiently

Here’s the KV cache’s practical headache: when a request arrives, nobody knows how long its answer will be. Twenty tokens? Four thousand? Early serving systems played it safe and reserved a big, continuous block of memory for the maximum possible length, the moment each request started.

That wasted memory in three ways at once:

• 🪑Reserved but never used. A 50-token answer sitting in room for 2,000.
• 🧩Gaps. When requests finish, they leave holes of odd sizes. A new request needs one unbroken stretch, so a hole that’s too small is useless, even if the free memory adds up to plenty.
• 📄Copies. Ten requests sharing the same long system prompt each stored their own copy of it.

Researchers found that existing systems were wasting most of their KV-cache memory this way. In 2023, the team behind vLLM borrowed a fix that operating systems have used for decades: paging.

With PagedAttention, the cache is cut into small fixed-size pages, each holding, say, 16 tokens. A request gets a new page only when it actually needs one, and the page can be anywhere in memory. A little page table per request remembers where its pages live, and the attention computation follows that table. Waste shrinks to the unfilled end of each request’s last page.

Two bonuses fall out for free. Requests with an identical beginning, like a shared system prompt, can point at the very same pages (“prefix caching”), so that prompt is stored and prefilled once. And because more conversations fit, the batch can grow, which, as you know, means more throughput from the same GPU.