What Does PagedAttention Actually Optimize?

What Does Paged Attention Actually Optimize?

This post focuses specifically on PagedAttention in vLLM. The earlier post, Understanding vLLM — A Complete Breakdown of KV Cache and PagedAttention, covered the full pipeline in order: tokenization, Attention, KV Cache, Prefill, and Decode. This post zooms in on why PagedAttention was needed, what problem it solves, and how it actually manages memory.

In one sentence, PagedAttention is a memory management scheme that, instead of pre-allocating one large contiguous block for the ever-growing KV Cache during LLM inference, splits it into small fixed-size blocks and chains them together on demand. It applies the same idea that operating systems use for virtual memory paging — but to the Attention KV Cache in LLMs.

This is not a minor optimization. KV Cache memory is the central bottleneck that largely determines serving throughput. The vLLM paper shows that existing systems can waste 60–80% of KV Cache memory. PagedAttention cuts that waste so that a single GPU can handle far more concurrent requests.

Figure. PagedAttention manages KV Cache placement on GPU memory at the block level. Image source: https://funktor.github.io/software-engineering/2025/06/21/the-gpu-notes-1.html

1. Starting with a Simple Example

Take the following sentence:

안녕하세요 반갑습니다

Assume it is tokenized into these 6 tokens:

["안녕", "하", "세요", "반갑", "습", "니다"]

An LLM does not read this sentence the way a human does and move on. It converts each token to a numeric ID, maps that to a vector, and passes it through multiple Transformer layers to predict the next token. At each step, Attention computes how much the current token should attend to each previous token.

For example, when processing the last token "니다", the model looks back at "안녕", "하", "세요", "반갑", and "습". Recomputing these relationships from scratch every time would be prohibitively expensive, so the Key and Value vectors for previous tokens are saved. That is the KV Cache.

The KV Cache is exactly what it sounds like: it stores already-computed Keys and Values in GPU memory so they can be reused. The problem is that as generation grows longer, the cache keeps growing with it.

2. Why the KV Cache Is So Large

For every token the LLM processes, it produces a Key and Value at each layer. If the model has 32 layers, a single token leaves a Key and Value in each of those 32 layers. A token is not just a small string — it accumulates as a bundle of vectors spread across layers in GPU memory.

KV Cache size is roughly determined by:

• Number of requests in the batch
• Current sequence length of each request
• Number of Transformer layers
• Number of attention heads (or KV heads)
• Head dimension
• Data type size (e.g., FP16 or BF16 = 2 bytes per value)

Simplified:

KV Cache size
= num_requests
  x num_tokens
  x num_layers
  x num_kv_heads
  x head_dim
  x 2  (K and V)
  x bytes_per_dtype

The key factor here is num_tokens. A short user query produces a small KV Cache. A long document produces a large one. And as the model generates a longer response, the KV Cache keeps growing with each new token.

From a serving system's perspective, it is hard to know upfront how long each request will be. Just because a user sets max_tokens=2048 does not mean the model will actually generate 2048 tokens. Some requests finish in 20 tokens; others exceed 1000.

This uncertainty is the problem PagedAttention was built to solve.

3. The Core Problem with Naive Approaches: Over-Allocate, Copy, or Waste

To understand PagedAttention, it helps to look at what happens without it.

The simplest approach is to pre-allocate a large contiguous block of memory for each request's KV Cache. If a request might generate up to 2048 tokens, reserve enough space for 2048 tokens upfront.

But in practice, requests look like this:

In this table, GPU memory is already reserved. Unused space cannot be reclaimed by other requests. The GPU appears to have plenty of free space, but the serving system cannot accept new requests.

A useful analogy is a restaurant that assigns a private room for 20 to every party that walks in. Even if only 2 people sit down, that room is unavailable to anyone else. If every party gets a large room because their size is uncertain, the restaurant's total capacity drops fast.

The same thing happens in GPU memory. Pre-allocating large contiguous regions is simple to manage but extremely wasteful. On the other hand, allocating exactly what is needed on the fly and copying data around reduces waste but introduces copy and management overhead.

PagedAttention takes a different approach. Instead of requiring one large contiguous block per request, it links together multiple small blocks to present them as a single long KV Cache.

4. The Core Idea Behind PagedAttention

PagedAttention has three key components:

• Logical block: the block as seen from within a request
• Physical block: the actual block that exists in GPU memory
• Block table: the mapping from logical blocks to physical blocks

Rather than laying tokens out as one long contiguous sequence, PagedAttention cuts them into fixed-size chunks called blocks. For example, with a block size of 4 tokens, the 6 tokens in "안녕하세요 반갑습니다" are split like this:

tokens: [안녕, 하, 세요, 반갑, 습, 니다]

logical block 0: [안녕, 하, 세요, 반갑]
logical block 1: [습, 니다, <empty>, <empty>]

The actual block size in vLLM depends on configuration and implementation, but the concept is the same: a request's tokens are divided into fixed-size blocks, and the last block may not be full.

Here is where the key change happens: logical block 0 and logical block 1 do not need to be contiguous in physical GPU memory.

Request A's logical blocks:
logical 0 -> physical 17
logical 1 -> physical 03
logical 2 -> physical 91

From request A's perspective, blocks 0, 1, and 2 appear as a contiguous sequence. In physical GPU memory, however, they may be scattered across physical blocks 17, 3, and 91. The block table stores this mapping.

This mirrors how operating system virtual memory works. A program sees its memory as contiguous, but the physical memory is spread across many pages. PagedAttention applies this same idea to the KV Cache.

5. What the Block Table Does

The block table is essentially an address book that exists per request. Each request has its own set of logical block numbers, and the block table tells the system which physical block holds each logical block.

For example, suppose request A has 10 tokens and the block size is 4:

Request A token count: 10
Block size: 4
Blocks needed: ceil(10 / 4) = 3

Request A's logical blocks:

logical block 0: tokens 0–3
logical block 1: tokens 4–7
logical block 2: tokens 8–9

In physical GPU memory, they might be laid out as:

Block table for request A:

logical block 0 -> physical block 42
logical block 1 -> physical block 07
logical block 2 -> physical block 18

When the Attention kernel needs to read the Key and Value for a specific token, it follows the block table. If it needs token 5 of request A, it first computes that this token lives in logical block 1, looks up the block table to find that logical block 1 is at physical block 07, and then reads the KV values from the appropriate offset within physical block 07.

This indirection looks complicated at first, but the purpose is straightforward: avoid allocating one long contiguous region per request by adding one level of address translation.

6. Block Allocation for "안녕하세요 반갑습니다" — A Walkthrough

Let's continue with block size 4. This is not the default in a real system; it's just a number that makes the concept easy to follow.

The input has 6 tokens:

0: 안녕
1: 하
2: 세요
3: 반갑
4: 습
5: 니다

Blocks needed:

ceil(6 / 4) = 2

Two logical blocks:

logical block 0: [안녕, 하, 세요, 반갑]
logical block 1: [습, 니다, <empty>, <empty>]

Suppose the free block pool in GPU memory contains:

free physical blocks: [11, 12, 13, 14, 15, 16]

vLLM allocates two physical blocks to this request:

Request R1 block table:
logical block 0 -> physical block 11
logical block 1 -> physical block 12

During the Prefill phase, KV vectors for all 6 tokens are computed and stored in physical blocks 11 and 12:

physical block 11: [안녕, 하, 세요, 반갑]
physical block 12: [습, 니다, <empty>, <empty>]

Now suppose the model generates a new token — say ".":

0: 안녕
1: 하
2: 세요
3: 반갑
4: 습
5: 니다
6: .

Logical block 1 still has 2 empty slots, so no new physical block is needed. The KV for "." is written into the next available slot in physical block 12:

physical block 12: [습, 니다, ., <empty>]

One more token fills the last slot:

physical block 12: [습, 니다, ., <next>]

When the following token is generated, logical block 2 is needed. At that point, vLLM pulls a new physical block from the free pool:

Request R1 block table:
logical block 0 -> physical block 11
logical block 1 -> physical block 12
logical block 2 -> physical block 13

This is the key behavior of PagedAttention: rather than reserving space for the maximum possible length upfront, it allocates blocks incrementally as new tokens are generated.

7. Why Waste Is Confined to the Last Block

PagedAttention reduces memory waste for a simple reason: the only place waste can occur within a request is the last block.

Say the block size is 16 tokens and a request uses 100 tokens:

ceil(100 / 16) = 7 blocks

The first 6 blocks are fully packed:

6 blocks x 16 tokens = 96 tokens

The last block holds only 4 tokens:

last block: 4 tokens used, 12 slots empty

The waste is 12 slots in the last block. Compare this to pre-allocating space for 2048 tokens when only 100 are actually used.

In general, with block size B, the maximum internal fragmentation per request is B − 1 slots. With a block size of 16, that is at most 15 wasted slots — regardless of whether the request uses 1000 tokens or 4000 tokens.

The vLLM paper reports that PagedAttention keeps memory waste below 4%. That is a substantial improvement over pre-allocating large contiguous regions.

8. Does PagedAttention Change the Attention Computation Itself?

This is a common point of confusion. PagedAttention does not change the model's semantics. It does not replace the Attention formula with something different.

The standard Attention equation still applies:

Attention(Q, K, V) = softmax(QK^T / sqrt(d))V

What PagedAttention changes is how K and V are laid out in memory. In a naive implementation, it is natural to assume K and V for a given request form one long contiguous array. With PagedAttention, K and V are stored across multiple physical blocks, and the kernel follows the block table to fetch the K and V it needs.

The context the model sees is identical. The structure in which "니다" attends to "안녕", "하", "세요", "반갑", and "습" is preserved exactly. What changes is where in GPU memory those values live.

This is not a question of output quality. It is a question of how many requests a server can handle efficiently on the same GPU.

9. How PagedAttention Appears in Prefill and Decode

LLM serving is broadly divided into Prefill and Decode.

Prefill is the phase where the entire input prompt from the user is processed in one shot. The model takes in, say, 6 tokens for "안녕하세요 반갑습니다", and builds the KV Cache for each layer. Because all input tokens are fed at once, parallel computation dominates this phase.

Decode is the phase where the model generates new tokens one at a time. If the response is 100 tokens long, Decode runs 100 times. Each iteration produces a new Query, which then attends over all Keys and Values accumulated so far. This is why the cost of reading the KV Cache becomes important during Decode.

PagedAttention is involved in both phases.

During Prefill, it allocates the blocks needed for the number of input tokens and fills them with KV data. During Decode, when a new token is generated, it appends the new KV to the current last block if space is available, or allocates a new block if not.

The flow looks like this:

1. 요청 수신
2. 토크나이징
3. 필요한 초기 블록 수 계산
4. free block pool에서 physical block 할당
5. block table 생성
6. Prefill 실행 및 KV 저장
7. Decode 반복
8. 마지막 블록에 공간이 있으면 KV 추가
9. 마지막 블록이 가득 차면 새 physical block 할당
10. 요청 종료 시 physical block 반환

This structure means short requests use only a few blocks and release them quickly. Longer requests acquire additional blocks on demand. GPU memory usage tracks the actual length of each request much more closely.

10. The Effect Becomes Clearer Alongside Continuous Batching

PagedAttention's impact becomes most apparent when viewed alongside continuous batching, another core feature of vLLM.

In conventional batch processing, multiple requests are grouped and processed together. The problem is that generation length varies per request. Some finish quickly; others run long. With fixed batching, a completed short request stays locked in the batch until the longest request finishes.

Continuous batching fills the slot left by a completed request with a new one immediately, dynamically updating the batch so the GPU stays busy.

Loose KV Cache memory management causes problems here. Even if you want to add a new request, it's difficult if there's no large contiguous free region on the GPU. With PagedAttention's small physical block units, the blocks freed by a completed request go straight back to the free block pool, where a new request can immediately claim them.

In short, continuous batching is a scheduling-level optimization, and PagedAttention is the underlying infrastructure that makes that scheduling work correctly on actual GPU memory.

11. Prefix Caching and Copy-on-Write

PagedAttention also pairs naturally with prefix caching. Prefix caching lets multiple requests that share the same leading portion of a prompt reuse the KV Cache for that prefix instead of recomputing it.

For example, suppose every request is prepended with the same system prompt:

너는 친절한 한국어 AI 어시스턴트다.
사용자의 질문에 정확하고 간결하게 답하라.

If this prompt is repeated across thousands of requests, recomputing its KV Cache every time is pure waste. vLLM's automatic prefix caching allows the KV Cache for a shared prefix to be reused.

In the PagedAttention framework, shareable prefixes are managed at block granularity. Multiple requests can reference the same physical block, with each request's block table pointing to the same physical block.

request A logical block 0 -> physical block 30
request B logical block 0 -> physical block 30
request C logical block 0 -> physical block 30

Here, physical block 30 holds the KV Cache for the common system prompt. All three requests read from the same block — no memory is written three times.

The complication arises when a request needs to modify that block. Writing directly to a shared block would affect all other requests referencing it. That's where Copy-on-Write comes in: blocks are shared for reads, but the moment a write is needed, a copy is made so only that request uses the new block.

This pattern is analogous to what file systems and OS memory managers have used for decades. Because PagedAttention already has a block-addressed layout, prefix caching and Copy-on-Write follow naturally from the design.

12. Understanding Swap and Eviction

When too many requests are in flight, the KV Cache blocks on the GPU can run out. The system then has to choose among several options:

• Queue new requests and wait.
• Abort or fail some requests.
• Move KV Cache blocks for lower-priority requests to CPU memory.
• Immediately reclaim blocks from requests that have already finished.

vLLM's scheduler and memory manager work together to decide which requests continue running on the GPU. PagedAttention is an advantage here too. When memory is tied up in large contiguous chunks, moving only part of it is difficult. With block-level granularity, the unit of management is small.

That said, swapping to CPU is not free. Moving data between GPU and CPU memory introduces latency. Swapping is therefore more of a buffer for throughput stability than an efficient steady-state mode. The ideal situation is keeping enough blocks on the GPU to serve requests without eviction.

13. A Simple Numerical Comparison

The following is a simplified example to build intuition. Actual numbers depend on the model and configuration.

Assumptions:

• Each request can generate up to 2048 tokens.
• Average actual usage is 300 tokens.
• Block size is 16 tokens.
• One KV Cache unit is used per token per request (simplified).

With static reservation, each request reserves 2048 units:

100 requests x 2048 = 204,800 units reserved

Actual usage averages 300 tokens:

100 requests x 300 = 30,000 units used

A large fraction of the reserved space sits empty.

With PagedAttention, each request allocates only as many blocks as its actual length requires:

ceil(300 / 16) = 19 blocks
19 blocks x 16 = 304 units
100 requests x 304 = 30,400 units reserved

Against actual usage of 30,000 units, the reserved amount is 30,400 — waste is bounded to a partial last block per request.

This example illustrates the intuition behind PagedAttention. The point is not that the GPU gets bigger, but that the same GPU memory is used far more densely.

14. Why a Dedicated Kernel Is Needed

Storing KV Cache in blocks improves memory efficiency but makes the Attention computation more complex. If K and V live in a contiguous array, a kernel can simply read them sequentially. With PagedAttention, token positions must be translated through the block table before reading.

That's why vLLM uses an Attention kernel designed for PagedAttention. The vLLM Paged Attention documentation describes the structure for looking up KV cache blocks via the block table.

From the kernel's perspective, each step requires:

• Reading the current request's block table.
• Determining which logical block each needed token position belongs to.
• Translating the logical block to a physical block.
• Computing the offset within the physical block.
• Reading the Key and Value at that location.
• Computing the Attention score and weighted sum.

This address-translation overhead is real. But it is outweighed by the gains from eliminating large contiguous memory reservations and being able to serve more concurrent requests. vLLM's performance improvements are the result of this memory management scheme and the kernel implementation working in concert.

15. What PagedAttention Does Not Solve

PagedAttention is powerful, but it is not a silver bullet. It's important to be precise about its scope.

PagedAttention does not reduce model parameters. If you don't have enough GPU memory to load a 70B model, PagedAttention alone won't fix that. Reducing model weight requires other techniques such as quantization, tensor parallelism, or CPU offloading.

PagedAttention does not eliminate the total KV Cache required for long prompts. If a sequence is one million tokens, the corresponding KV Cache is still needed. What PagedAttention does is lay out, share, and reclaim that memory more efficiently.

PagedAttention also does not fundamentally make Attention computation linear. The computational burden of Attention over long contexts remains. PagedAttention addresses primarily the problem of KV Cache memory layout and management.

To summarize: PagedAttention does not make an LLM smarter — it makes the LLM server use GPU memory more effectively.

16. Where PagedAttention Is Felt in Practice

In practice, most vLLM users never directly manipulate PagedAttention. Running vllm serve brings up the scheduler, KV cache manager, and PagedAttention kernel all working together under the hood.

The effects show up in these situations:

• The same GPU can handle more concurrent requests.
• Memory waste is reduced even when short and long requests are mixed together.
• KV Cache is reclaimed at block granularity quickly once a request finishes.
• Combined with prefix caching, the cost of repeated prompts drops.
• Combined with continuous batching, GPU idle time decreases.

The settings users typically need to think about are max_model_len, gpu_memory_utilization, and batch-related options. These values directly affect how much KV Cache space PagedAttention has to work with and how many requests can be processed concurrently.

For example, setting max_model_len excessively large increases the potential context length each request can use. Even though PagedAttention reduces waste, workloads that actually use long contexts still need substantial KV Cache.

gpu_memory_utilization is a key parameter that controls what fraction of GPU memory vLLM will use. Setting it too low reduces the number of requests that can be handled concurrently; setting it too high leaves insufficient headroom for other processes or runtime overhead.

17. A Minimal Pseudocode Walkthrough

Expressed in pseudocode rather than real code, PagedAttention looks like this:

BLOCK_SIZE = 4

class RequestState:
    def __init__(self):
        self.tokens = []
        self.block_table = []  # logical block index -> physical block id

free_blocks = [11, 12, 13, 14, 15, 16]
kv_memory = {}


def allocate_block():
    return free_blocks.pop(0)


def ensure_capacity(request, next_token_index):
    logical_block = next_token_index // BLOCK_SIZE

    while len(request.block_table) <= logical_block:
        physical_block = allocate_block()
        request.block_table.append(physical_block)
        kv_memory[physical_block] = [None] * BLOCK_SIZE


def write_kv(request, token_index, kv_value):
    ensure_capacity(request, token_index)

    logical_block = token_index // BLOCK_SIZE
    offset = token_index % BLOCK_SIZE
    physical_block = request.block_table[logical_block]

    kv_memory[physical_block][offset] = kv_value


def read_kv(request, token_index):
    logical_block = token_index // BLOCK_SIZE
    offset = token_index % BLOCK_SIZE
    physical_block = request.block_table[logical_block]

    return kv_memory[physical_block][offset]

This pseudocode shows only the core idea. Real vLLM handles layers, heads, dtypes, GPU kernels, the scheduler, the block manager, prefix caching, swapping, and more. The central principle is the same:

• Convert a token position into a logical block and an offset.
• Map the logical block to a physical block via the block table.
• Read and write KV within the physical block.

These three steps are the essence of PagedAttention.

18. Putting the Full Flow Together

Using the "안녕하세요 반갑습니다" example, here is the complete flow condensed:

1. Receive input sentence
   "안녕하세요 반갑습니다"

2. Tokenize
   ["안녕", "하", "세요", "반갑", "습", "니다"]

3. Calculate required blocks based on block size
   block size = 4 → 2 blocks needed

4. Allocate physical blocks from the free block pool
   logical 0 -> physical 11
   logical 1 -> physical 12

5. During prefill, compute and store KV for each token
   physical 11: 안녕, 하, 세요, 반갑
   physical 12: 습, 니다, empty, empty

6. During decode, generate new tokens
   If space remains in the last block, append there

7. When the last block is full, allocate a new physical block
   logical 2 -> physical 13

8. When the request completes, release its physical blocks
   11, 12, 13 are returned to the free block pool

In this flow, PagedAttention has no say in what the model actually generates. Instead, it manages the KV cache produced during generation by splitting it into small blocks. Better management of that cache means the same GPU can reliably handle more concurrent requests.

19. Key Takeaways for vLLM Users

There are three things worth keeping in mind when first encountering PagedAttention.

First, the KV cache in LLM inference is large and grows continuously. Long prompts and long responses consume GPU memory fast.

Second, the traditional approach of pre-allocating a large contiguous region per request leaves a lot of memory unused. That waste causes situations where the GPU appears to have memory to spare yet cannot accept new requests.

Third, PagedAttention splits the KV cache into fixed-size blocks and connects them through a block table. This lets the system add blocks as a request grows, reclaim blocks when a request finishes, and share blocks for a common prefix across requests.

This design is the core of vLLM's competitive advantage. The usability of serving an OpenAI-compatible API with a single vllm serve command matters, but PagedAttention is the foundation that makes efficient handling of many concurrent requests possible underneath.

The full flow for installing and running vLLM for the first time is covered in vLLM Complete Beginner's Guide — From Installation to OpenAI-Compatible API Serving. If you want to walk through the entire KV cache and attention flow with a token-level example, read '안녕하세요 반갑습니다' — A Complete Dissection of vLLM, KV Cache, and PagedAttention first. When you move on to production serving options, vLLM serve Option Reference covers max_model_len, gpu_memory_utilization, and batch-related settings together.