PagedAttention Internals

The Memory Waste Problem

LLM inference stores earlier attention data in a KV cache, which grows as each sequence generates tokens.

Traditional serving reserves one contiguous memory region for every request.

Because the final sequence length is unpredictable, systems often reserve space for the maximum possible length.

A short response then occupies only part of its reservation. The remaining space is reserved but unused.

This internal fragmentation can waste up to 96% of allocated memory in naive implementations.

For a serving engineer, that waste limits batch size, lowers GPU utilization, and increases cost per request.

Why Contiguous Storage Breaks

Contiguous storage requires each request to receive one connected memory block for its entire KV cache.

Imagine a request that might generate 2,000 tokens but finishes after 200. Its reserved region still reflects the larger maximum.

Several requests create the same problem at once. Their unused spaces remain tied to individual reservations.

The system may have free memory in scattered gaps, yet lack one large contiguous region for a new request.

This is fragmentation. The memory exists, but its layout prevents efficient reuse.

Increasing the batch can therefore trigger memory pressure earlier than expected.

Paging Comes From Operating Systems

PagedAttention applies an operating-system idea to LLM memory: separate a logical address space from physical storage.

The KV cache is divided into small, fixed-size blocks instead of one large contiguous buffer.

A sequence sees its tokens in logical order. The underlying blocks can live in different physical locations.

This separation removes the requirement that all tokens occupy neighboring memory addresses.

The result is non-contiguous storage, which uses scattered free space more effectively.

The core shift is simple: logical sequence order stays stable while physical placement becomes flexible.

Fixed-Size KV Blocks

PagedAttention partitions each request's KV cache into fixed-size blocks.

As a sequence grows, the system allocates another block when the current one fills.

A request no longer needs a maximum-length buffer at the beginning. It receives storage progressively, matching its actual generation.

Unused capacity is limited to space inside the currently incomplete block, rather than an entire maximum reservation.

Fixed-size blocks also make placement predictable. Any suitable free block can hold the next portion of the cache.

This design reduces internal fragmentation while supporting dynamic sequence lengths.

The Block Table Map

PagedAttention uses a block table to connect logical token positions with physical KV blocks.

Suppose a sequence logically needs blocks 0, 1, and 2. Those blocks can map to physical locations 8, 3, and 11.

Attention follows the table to find the correct data, even though the physical blocks are separated.

The mapping preserves the sequence's logical order without requiring contiguous GPU memory.

When a sequence grows, the table records an additional physical block.

This indirection is the key mechanism behind flexible placement and dynamic growth.

Sharing And Dynamic Growth

PagedAttention allows multiple requests to use memory more efficiently through block-based allocation and sharing.

Instead of reserving large private buffers, each request obtains the blocks it currently needs.

A short request releases less unused capacity than a maximum-length reservation would leave behind.

As sequences grow, vLLM can add blocks without reallocating one large buffer.

This matters during batching, where requests often finish at different times and have different output lengths.

The memory manager can respond to those changing sizes while keeping logical token mappings correct.

Serving Impact And Takeaways

For a working vLLM engineer, PagedAttention is a memory-efficiency mechanism with direct serving consequences.

Less wasted KV-cache space allows more active requests to fit on the same GPU.

That can increase batch size and improve throughput, while raising GPU utilization.

The practical chain is: fixed-size blocks reduce fragmentation, the block table enables non-contiguous placement, and dynamic allocation follows real sequence growth.

Naive implementations may waste up to 96% of memory through reservations that remain unused.

PagedAttention turns that wasted capacity into room for additional work, helping reduce cost per request.

In traditional LLM serving implementations, memory reserved for a request's KV cache must be stored in a _____ memory buffer.

• contiguous
• non-contiguous

Answer: contiguous

Traditional serving requires one contiguous memory block reserved upfront for the entire maximum potential request length, causing high internal fragmentation.

In PagedAttention, tokens maintain a sequential _____ order while their KV cache blocks occupy scattered _____ memory addresses.

Answer: In PagedAttention, tokens maintain a sequential logical order while their KV cache blocks occupy scattered physical memory addresses.

PagedAttention decouples logical sequence ordering from physical memory layout, allowing non-contiguous storage in physical GPU memory without breaking sequence continuity.

What is the main role of the block table in PagedAttention?

• Mapping logical token positions to physical KV cache block locations
• Pre-allocating a single contiguous buffer matching maximum sequence length
• Compressing key-value tensor values to reduce GPU memory bandwidth
• Sorting requests in the batch based on total prompt length

Answer: Mapping logical token positions to physical KV cache block locations

The block table acts as an indirection layer, mapping logical sequence block indices to physical memory block locations scattered across GPU memory.