PagedAttention and KV Cache Compression: Optimizing LLM Inference

The most expensive real estate on Earth is not in Manhattan; it is the microscopic silicon memory packed inside an artificial intelligence processor. Modern AI models are mathematically starving for memory. When millions of users simultaneously ask a chatbot a question, the server physically runs out of High Bandwidth Memory (HBM) long before its processing cores max out their calculating limits. For years, the industry’s only solution was to spend billions of dollars physically buying more hardware to handle the traffic.

Why should you care right now? Because the software engineering community realized that buying more hardware was a mathematical trap. The AI wasn’t actually using all of its memory; it was hoarding it. By peering backward into the foundational computer science of the 1990s, researchers at UC Berkeley pulled off a software engineering heist. They adapted a classic trick called “virtual memory paging” and injected it directly into the neural networks of modern AI. Known as PagedAttention, this algorithm stops AI from hoarding idle memory, completely eliminating digital fragmentation. It allows data centers to double or quadruple their AI output on the exact same hardware, triggering a massive deflationary collapse in the cost of global cloud intelligence.

What is PagedAttention?

PagedAttention is a memory management algorithm designed for Large Language Model (LLM) inference. It breaks the model’s Key-Value (KV) cache into fixed-size, non-contiguous blocks rather than relying on massive contiguous memory allocations. By dynamically assigning memory exactly when needed, it virtually eliminates memory fragmentation and drastically increases server throughput.

At a Glance

• Concept: Stopping AI from reserving massive, empty blocks of memory for data it might generate, and instead handing it tiny blocks of memory exactly when it generates a new word.
• Why it matters: AI chips (like NVIDIA GPUs) are incredibly expensive and scarce. PagedAttention allows a company to run 4x as many simultaneous user requests on a single GPU by simply managing the memory perfectly.
• Who uses it: Open-source AI serving engines (like vLLM), major cloud hyperscalers, and AI infrastructure startups.
• Biggest takeaway: Because the memory blocks are chopped up into tiny pieces, multiple AI chatbots can now effortlessly “share” the same system prompt in memory, reducing the computing cost of complex tasks to almost zero.

In Simple Words

Imagine a highly exclusive restaurant that only takes reservations.

Under the Old AI System (Contiguous Allocation), a customer books a table but won’t say exactly how many friends are coming—maybe 2, maybe 20. To be safe, the manager reserves a massive 20-person table for every single reservation. As a result, the restaurant physically fills up after just three bookings, even though most of the chairs at the massive tables are completely empty. The restaurant wastes 80% of its space.

Under PagedAttention, the manager changes the rules. They break all the massive tables down into tiny, 4-person tables. When a customer walks in, they get one tiny table. If a 5th friend shows up, the manager simply points to a different tiny table across the room and tells the waiter, “They are part of the same party.”

Because the tables don’t have to be physically connected, the manager never wastes a single chair. The restaurant can seat four times as many people, maximizing its profits without expanding the building.

Why This Matters

For Cloud Architects, MLOps Engineers, and AI Developers, the fundamental unit of economics in artificial intelligence is the Batch Size.

Batch size dictates how many user requests a GPU can process simultaneously. Because loading a multi-billion parameter model into the processor takes time, processing 100 requests at once is exponentially cheaper than processing them one by one. The limiting factor on batch size is the Key-Value (KV) cache memory. If the KV cache is fragmented and full, the batch size drops, and the cost per token skyrockets. PagedAttention elegantly solves the fragmentation crisis, maximizing the batch size up to the absolute physical limit of the silicon, saving enterprise companies millions in monthly AWS or Azure computing bills.

The KV Cache Memory Wall in LLMs

Large Language Models (LLMs) operate via an autoregressive “attention mechanism.” As the model generates text, it must look back at all the previous words to contextually understand what to say next.

To avoid mathematically recalculating every previous word from scratch for every new token, the AI stores the pre-calculated mathematical representations (the Keys and Values) in a temporary storage called the KV Cache. As the context window grows (from 4,000 tokens to 1 million+ tokens), this cache becomes a monstrous, gigabyte-consuming entity. Managing the physical shape and location of this cache inside the GPU is the defining software engineering challenge of the modern AI era.

How PagedAttention and Virtual Memory Paging Work

Eliminating memory fragmentation requires abandoning rigid data structures and embracing dynamic virtual mapping. Here is the first-principles breakdown of the architecture.

1. The Fundamental Problem: Contiguous Memory Allocation

Before PagedAttention, deep learning frameworks required the KV cache for a single sequence to be stored in physically contiguous (connected) memory space. Because it is impossible to predict exactly how many tokens an AI will output before it stops, the system pre-allocated a contiguous chunk of memory equal to the model’s absolute maximum length (e.g., 8,000 tokens).

2. The Insufficiency of Over-Provisioning

This pre-allocation was a disaster. If a user asked a short question and the AI gave a 50-token answer, the remaining 7,950 tokens of reserved memory sat completely empty but locked. This is known as Internal Fragmentation. Furthermore, as these massive, rigid blocks filled and emptied at different times, tiny, unusable gaps appeared between them in the GPU memory—known as External Fragmentation. Over 60% of the GPU’s memory was effectively dead space.

3. The Core Mechanism: Virtual Paging

Researchers adapted “paging” from traditional operating systems. PagedAttention divides the KV cache into small, fixed-size chunks called blocks or pages. Each block can store the keys and values for a small number of tokens (typically 16 or 32).

4. Technical Depth: Block Tables and Non-Contiguous Memory

Because the data is chopped into blocks, the KV cache for a single sentence no longer needs to be physically contiguous on the GPU chip. The tokens can be scattered wildly across the memory hardware.

To keep track of them, PagedAttention uses a Block Table. When the AI is running its attention calculation, the algorithm looks at the logical sequence of words, checks the Block Table, instantly maps the logical token to its scattered physical block, and fetches the data seamlessly.

5. Real-World Consequences: Zero Fragmentation

Memory is now allocated dynamically. When the AI generates a new word, it fills up its current 16-token block. Only when that block is full does the system allocate a brand new block. Internal fragmentation drops to near zero, and because all blocks are exactly the same size, external fragmentation is physically eliminated. The GPU operates at nearly 100% memory utilization.

PagedAttention Applications: vLLM and Prefix Caching

The theoretical elegance of PagedAttention triggered a massive shift in how the global open-source community deploys models.

The vLLM Open Source Engine: PagedAttention was the foundational breakthrough behind vLLM, an open-source library for LLM inference. Within months of its release, vLLM became the industry standard for deploying models like Llama 3 or Mistral. By simply routing an open-source model through the vLLM engine, developers saw immediate 2x to 4x improvements in generation throughput compared to standard HuggingFace implementations, without altering the model’s weights or accuracy.

Complex Decoding (Beam Search & Parallel Sampling): Sometimes, developers ask an AI to generate five different possible answers to a single prompt and pick the best one. Under old systems, the massive system prompt had to be copied and saved five separate times in memory. Because PagedAttention uses blocks, it enables Copy-on-Write memory sharing. The system stores the main prompt in a few blocks once, and all five generated answers mathematically “point” to the exact same blocks. This reduces the memory cost of complex reasoning algorithms by over 50%.

System Prompt Caching: Many enterprise applications use massive “System Prompts” (e.g., uploading a 50-page company rulebook) before every user query. With PagedAttention, the KV cache blocks for the 50-page rulebook can be permanently pinned in the GPU memory. When 1,000 employees ask questions, the system does not re-process the rulebook 1,000 times; it simply links their questions directly to the pinned memory blocks, achieving near-instantaneous “Time to First Token” (TTFT) for enterprise users.

Economic & Strategic Impact

The core strategic impact of PagedAttention is the Decoupling of Inference Scale from Silicon Scarcity.

During the height of the AI hardware boom, NVIDIA H100 GPUs faced waitlists stretching beyond 12 months. Companies were bottlenecked, unable to scale their AI products simply because they could not physically acquire enough memory to hold the KV cache of their user base.

PagedAttention acted as synthetic silicon. By releasing a free, open-source algorithm that quadrupled the effective memory utilization of a GPU, the Berkeley researchers effectively gave every AI company in the world four times as many GPUs overnight. It applied a massive, sudden deflationary force to the AI ecosystem, crashing the per-token pricing wars between OpenAI, Anthropic, and open-source hosting providers, accelerating the commoditization of base-level intelligence.

Advantages

• Massive Throughput Gains: By eliminating memory fragmentation, servers can batch significantly more requests simultaneously, scaling generation throughput by 200% to 400%.
• Zero Accuracy Loss: Unlike quantization or model pruning, which compress the math and degrade the AI’s intelligence, PagedAttention only changes where the data is stored. It is mathematically identical to the original model, with zero hallucinations or reasoning loss.
• Memory Sharing: The block architecture inherently supports Copy-on-Write, allowing multiple users or parallel generation paths to effortlessly share identical memory blocks without duplicating data.
• Hardware Agnostic: While highly optimized for NVIDIA GPUs, the software logic of PagedAttention can be deployed across AMD accelerators, TPUs, and custom silicon.

Limitations

• Pointer Chasing Latency: Because the memory is non-contiguous, the GPU must constantly check the “Block Table” to find where the next piece of data lives. This “pointer chasing” introduces a microscopic amount of latency. While the overall throughput is massively higher, the raw speed of a single isolated user request might be imperceptibly slower than a perfectly contiguous allocation.
• Kernel Complexity: Writing Custom CUDA kernels to perform attention calculations across scattered blocks of memory is agonizingly difficult software engineering. Maintaining and upgrading these kernels as new hardware architectures are released requires elite, specialized developer talent.
• It Does Not Compress the Data: PagedAttention stops the waste of memory, but it does not shrink the actual size of the KV cache itself. If a user uploads a 2-million-token book, the raw mathematical size of those 2 million tokens will still overwhelm the physical limits of the GPU, requiring deeper algorithmic compression methods to solve entirely.

Common Misconceptions

Misconception: PagedAttention makes the AI “smarter.”

Reality: It has absolutely zero impact on the intelligence, reasoning, or parameters of the model. It is strictly an infrastructure plumbing optimization designed to make the model cheaper and faster to host.

Misconception: It compresses the size of the text.

Reality: It is not a compression algorithm (like a ZIP file). The data remains its full, massive size. PagedAttention simply plays a perfect game of “Tetris” with the data, fitting it flawlessly into the GPU memory without leaving any empty gaps.

Misconception: You need a special type of AI model to use it.

Reality: Almost any standard Transformer-based LLM (Llama, Mistral, Qwen) can use PagedAttention simply by being executed through an optimized inference engine like vLLM. It does not require retraining the model.

What Most People Miss

The disruptive capability of Prefix Caching with Multi-Tenancy.

Most analysts view PagedAttention purely as a way to handle unpredictable response lengths. What they miss is the profound impact of block-level hashing across thousands of users.

If thousands of developers are using an API, many of them start their prompts with the exact same phrasing (e.g., “Translate the following into French:”). With advanced PagedAttention implementations, the inference engine automatically calculates a hash (a digital fingerprint) for every block of text. When User B types the exact same intro sentence as User A, the engine instantly recognizes the matching hash. It does not calculate the text for User B; it simply points User B to User A’s already-processed memory blocks. The AI effectively “skips” reading the prompt entirely, turning multi-tenant cloud hosting into a hyper-efficient, self-optimizing organism.

Comparison Table

Feature	Legacy Inference (Contiguous Memory)	PagedAttention (vLLM Engine)
Memory Allocation	Massive, rigid, pre-allocated blocks	Tiny, dynamic, on-demand blocks
Internal Fragmentation	High (Often >50% wasted space)	Near Zero (<4% wasted space)
External Fragmentation	High (Uneven gaps between requests)	Absolute Zero (Uniform block sizes)
Memory Sharing	Impossible (Must duplicate exact data)	Native (Copy-on-Write block sharing)
Maximum Batch Size	Low (Constrained by wasted memory)	Extremely High (Limited only by hardware)

Case Study

Situation: In 2023, the explosion of open-source language models triggered a race to host cheap, accessible API endpoints. However, infrastructure providers realized that standard HuggingFace Transformers libraries were horribly inefficient for commercial production. Because user prompt lengths were unpredictable, GPUs were rejecting new requests due to “Out of Memory” errors, despite the actual silicon memory being mostly empty and fragmented.

Challenge: Develop a memory manager for the GPU that could dynamically allocate KV cache space on the fly, eliminating memory waste and drastically lowering the computing cost required to host a commercial LLM.

Solution (The UC Berkeley vLLM Project): Researchers developed PagedAttention, inspired directly by the virtual memory and paging systems used in operating systems since the 1990s. They built a custom attention algorithm that could perform the required matrix multiplications across scattered, non-contiguous blocks of memory, and packaged it into a high-performance open-source serving engine called vLLM.

Outcome: The release of vLLM fundamentally reorganized the AI infrastructure landscape. In benchmark testing on models like LLaMA, vLLM achieved up to 24x higher throughput than HuggingFace Transformers and up to 3.5x higher throughput than heavily optimized engines like Text Generation Inference (TGI). Cloud providers universally adopted the framework, plunging the retail cost of generating 1 million tokens from dollars to mere cents within a year.

Lessons Learned: The vLLM project proved that the most lucrative breakthroughs in artificial intelligence do not always require inventing new math. By rigorously applying foundational computer science principles (like OS virtual memory paging) to modern hardware bottlenecks, the open-source community effectively engineered its way out of a multi-billion-dollar silicon shortage.

Future Outlook

Next 12–24 Months

The era of Multi-Node Distributed Paging. Currently, PagedAttention is brilliant at managing memory on a single GPU or a tightly coupled 8-GPU server. The immediate future involves distributing the Block Table across massive data centers. If a user request runs out of memory on Server A, the system will use ultra-fast networking (like InfiniBand or NVLink) to seamlessly assign the next memory block on Server B. This distributed KV cache will allow for infinitely scalable attention mechanisms without triggering catastrophic latency spikes.

Next 3–5 Years

The scaling of Lossy KV Cache Compression and Eviction. PagedAttention perfectly organizes the cache, but as context windows explode to 10 million or 100 million tokens, the sheer volume of data will overwhelm even perfectly organized memory. To solve this, developers will layer aggressive “eviction algorithms” (like StreamingLLM or H2O) on top of PagedAttention. The AI will dynamically analyze which memory blocks contain “useless” words (like ‘the’ or ‘and’) and actively delete those specific blocks from the GPU, preserving only the crucial semantic blocks. This hybrid approach will enable true infinite-context AI.

Next 10 Years

The Hardware Encoding of Memory Virtualization. By the mid-2030s, the software logic of PagedAttention will be deemed so universally critical that it will be etched directly into the physical silicon of the microchip. Future AI accelerators will feature dedicated hardware Memory Management Units (MMUs) explicitly built for Tensor caching. Rather than relying on custom CUDA software kernels to map scattered blocks, the hardware itself will route the matrix multiplications natively across fragmented memory, pushing the operational overhead of LLM inference down to absolute zero.

Most Likely Scenario

PagedAttention is the definitive operational standard for the current generation of generative AI. By solving the devastating inefficiency of contiguous memory allocation, it bridged the gap between expensive laboratory research and cheap, mass-market commercialization. As models continue to scale in parameter size and context length, dynamic block-level memory management will remain the non-negotiable software foundation of the global cloud infrastructure.

Key Takeaways

• Large Language Models (LLMs) are “memory-bound,” meaning their speed is limited by how fast they can move data in and out of memory, not by how fast they can do math.
• Older systems reserved a massive, solid block of memory for every user request just in case the AI generated a long answer. Most of this space sat empty, wasting over 60% of the expensive GPU memory.
• PagedAttention solves this by borrowing “virtual memory paging” from 1990s computer operating systems. It chops the memory into tiny, fixed-size blocks.
• The AI is only given a new block of memory at the exact millisecond it needs to generate a new word. The blocks don’t need to be physically connected; a “Block Table” keeps track of them.
• Because no space is wasted, cloud servers can fit up to four times as many active users on the exact same hardware, drastically lowering the cost of running an AI company.
• This breakthrough was pioneered by the open-source vLLM project at UC Berkeley, fundamentally breaking the bottleneck of AI silicon scarcity.

Glossary

Batch Size: The number of user requests an AI processor handles at the exact same time. A higher batch size equals cheaper operational costs.

Copy-on-Write: A memory trick where multiple different processes (or users) point to the exact same block of memory. The system only creates a separate copy if one of the users actually tries to change the data.

High Bandwidth Memory (HBM): The incredibly fast, expensive memory chips physically stacked directly next to the AI processor.

Key-Value (KV) Cache: The massive memory bank where an AI stores the mathematical representations of all the words it has already seen in a conversation, so it doesn’t have to recalculate them from scratch.

Memory Fragmentation: When memory is broken up into tiny, unusable gaps (external) or trapped inside oversized, rigid reservations (internal).

PagedAttention: An algorithm that breaks the KV Cache into tiny, non-contiguous blocks, allocating memory dynamically to eliminate fragmentation.

Sources

UC Berkeley / vLLM Project: Efficient Memory Management for Large Language Model Serving with PagedAttention

Hugging Face: Optimizing LLM Inference with vLLM and PagedAttention

NVIDIA Technical Blog: Mastering LLM Techniques: Inference Optimization

arXiv (Computer Science): PagedAttention: High-Throughput LLM Serving

AnyScale: How vLLM and PagedAttention speed up LLM serving