I. Why Is KV Cache Needed?
During autoregressive generation in large language models, every time the model generates a new token, it must use the context information that has already been generated.
The Transformer's attention computation requires Query, Key, and Value:
Where:
- Query (Q): the query vector of the current token.
- Key (K): the key vector of historical tokens.
- Value (V): the value vector of historical tokens.
- d_k: the dimension of the key vector.
If the Key and Value of the entire historical sequence are recomputed every time a new token is generated, a large amount of redundant computation will occur.
KV Cache is designed to solve this problem.
1. Computation Without KV Cache
Assume the model needs to generate three tokens:
Input: A B C
Generation 1:
Compute A, B, C → generate D
Generation 2:
Recompute A, B, C, D → generate E
Generation 3:
Recompute A, B, C, D, E → generate F
As the sequence grows, historical tokens are repeatedly recomputed.
2. Computation With KV Cache
With KV Cache, the model saves the Key and Value of historical tokens.
Input: A B C
Prefill:
Compute A, B, C
Save K, V cache
Decode 1:
Compute only K, V for D
Read historical cache
Generate E
Decode 2:
Compute only K, V for E
Read historical cache
Generate F
The KV of historical tokens does not need to be recomputed.
Note: the Decode stage still needs to read the historical KV Cache for attention; it only avoids recomputing the K and V of historical tokens.
3. Where KV Cache Is Located in the Transformer
For a model with multiple Transformer layers, each layer needs to maintain its own Key and Value.
Assume the model has 32 layers:
- Layer 1 maintains its own K, V.
- Layer 2 maintains its own K, V.
- And so on up to layer 32.
Therefore, KV Cache is cache data organized by dimensions such as Layer, Head, and Token.
II. Data Structure of KV Cache
To understand PagedAttention, you first need to understand the storage structure of KV Cache.
1. Basic Dimensions of KV Cache
A typical KV Cache can be abstracted as:
Where:
| Parameter | Meaning |
|---|---|
| L | Number of Transformer layers |
| 2 | The two parts: Key and Value |
| B | Request batch size |
| S | Cache sequence length |
| H_{kv} | Number of KV heads |
| D_h | Dimension of each head |
In actual implementations, the physical layout of KV Cache is affected by the Attention Backend, parallelization strategy, and hardware implementation, and does not necessarily strictly follow the above dimension order.
2. KV Cache Storage Illustration
Assume the model has 2 layers, and each layer stores Key and Value:
Transformer
│
├── Layer 0
│ ├── Key Cache
│ └── Value Cache
│
└── Layer 1
├── Key Cache
└── Value Cache
Each token generates its own Key and Value at the corresponding layer.
As the generation length increases, KV Cache continues to grow.
3. Differences Between KV Cache and Model Weights
| Comparison Dimension | Model Weights | KV Cache |
|---|---|---|
| Content stored | Parameters obtained from model training | Key, Value of historical tokens |
| Whether it changes with requests | Usually unchanged | Changes dynamically with request execution |
| Whether it is related to context length | Not directly related | Highly related |
| Whether it increases with concurrency | Usually does not increase linearly with the number of requests | Usually increases with concurrency |
| Lifecycle | Usually exists with the model instance | Usually changes with the lifecycle of a request or cache reuse |
| GPU memory purpose | Store model parameters | Store historical context computation results |
Model weights determine the model's computational capability, while the KV Cache stores the historical information already computed during inference.
III. Why Does the KV Cache Consume So Much GPU Memory?
The GPU memory footprint of the KV Cache is directly related to the model architecture, context length, number of concurrent requests, and data precision.
1. KV Cache Memory Formula
The theoretical footprint of the KV Cache for a single request can be expressed as:
Where:
- L: number of model layers.
- S: number of cached tokens.
- H_{kv}: number of KV heads.
- D_h: head dimension.
- P: number of bytes per element.
- 2: represents Key and Value respectively.
If there are multiple requests:
This assumes all requests have the same cache length. In practice, request lengths often differ, so memory must be calculated per request or estimated from the block allocation.
2. Memory Estimation Example
Assume a model with the following parameters:
| Parameter | Value |
|---|---|
| Number of Transformer layers | 32 |
| Number of KV heads | 8 |
| Head dimension | 128 |
| Data precision | FP16 |
| Context length per request | 8192 |
| Number of concurrent requests | 16 |
FP16 uses 2 bytes per element.
Single request:
This is approximately 1 GiB.
16 requests:
In other words, the KV Cache alone can occupy about 16 GiB of GPU memory.
This does not yet include model weights, activations, the CUDA workspace, or runtime overhead.
3. Impact of GQA and MQA on the KV Cache
KV Cache size is also affected by the attention architecture.
| Attention structure | Number of KV heads | Memory characteristics |
|---|---|---|
| MHA | Same as the number of query heads | Larger KV Cache |
| GQA | Fewer than the number of query heads | Smaller KV Cache |
| MQA | Usually 1 | Smaller KV Cache |
For example, a model with 32 query heads:
- MHA: 32 KV heads.
- GQA: 8 KV heads.
- MQA: 1 KV head.
With all other parameters identical:
Therefore, GQA and MQA not only reduce the GPU memory requirements of the KV Cache but also lower the pressure of reading KV data during the decode phase.
IV. Problems with Traditional KV Cache Management
Traditional contiguous KV Cache management typically requires each request's cache to be stored in a contiguous region of GPU memory.
This approach is simple to implement but has obvious problems in high-concurrency inference scenarios.
1. Wasted Memory from Pre-allocation
Suppose three requests each have a maximum context length of 4096 tokens:
| Request | Maximum Reserved Tokens | Actual Used Tokens |
|---|---|---|
| A | 4096 | 512 |
| B | 4096 | 2048 |
| C | 4096 | 3000 |
If space is preallocated according to the maximum context length, each request would need to occupy 4096 tokens of cache space.
But actual usage is only 512, 2048, and 3000, respectively.
This creates a large amount of unused cache space.
2. GPU Memory Fragmentation Problem
Suppose there are multiple free regions of different sizes in GPU memory:
GPU memory space:
[Request A][Free][Request B][Free][Request C][Free]
Although the total free space may be sufficient, there may not be a contiguous space large enough to satisfy the allocation requirements of a new request.
This is the external GPU memory fragmentation problem.
Two types of waste need to be distinguished:
- Internal fragmentation: The allocated space is larger than the actual usage, and the remaining part cannot be used by other requests.
- External fragmentation: Free space is scattered, making it difficult to satisfy larger contiguous allocation requests.
3. Uncertain Request Length
The output length of a large model usually cannot be accurately determined in advance.
For example:
- Request A ends after generating 20 tokens.
- Request B ends after generating 200 tokens.
- Request C ends after generating 2000 tokens.
If preallocated according to the maximum length, there will be obvious waste.
If allocated according to the current length, the cache space will need to be expanded frequently.
Traditional contiguous allocation methods struggle to simultaneously balance dynamic expansion, GPU memory utilization, and concurrency capacity.
4. Main Problems of Traditional Management Methods
| Problem | Cause | Impact |
|---|---|---|
| Internal fragmentation | Preallocated space is too large | GPU memory utilization decreases |
| External fragmentation | Contiguous memory allocation restrictions | Allocation is difficult |
| Difficulty in dynamic expansion | Request lengths keep changing | Requires reallocation or copying |
| Isolation between requests | Caches are usually allocated independently | Difficult to share the same prefix |
| Limited concurrency | A single request occupies too much space | The number of runnable requests decreases |
V. Core Idea of PagedAttention
PagedAttention is one of the core technologies proposed by vLLM.
It draws on the virtual memory paging mechanism of operating systems and divides the KV Cache into fixed-size Blocks.
Each request no longer needs to occupy an entire contiguous GPU memory region; instead, a Block Table records the mapping between logical positions and physical Blocks.
1. From Contiguous Storage to Paged Storage
Traditional approach:
Request A:
[Block 0][Block 1][Block 2][Block 3]
Request B:
[Block 4][Block 5][Block 6][Block 7]
Each request usually requires a contiguous cache region.
PagedAttention:
Request A:
Logical Block 0 → Physical Block 3
Logical Block 1 → Physical Block 8
Logical Block 2 → Physical Block 1
Request B:
Logical Block 0 → Physical Block 5
Logical Block 1 → Physical Block 2
Logical Block 2 → Physical Block 9
Physical Blocks can be distributed in different locations in GPU memory.
Logically contiguous tokens do not need to be stored in physically contiguous GPU memory regions.
2. Core Components of PagedAttention
| Component | Function |
|---|---|
| KV Cache Block | Stores K and V data for a fixed number of tokens |
| Block Table | Records the mapping between logical Blocks and physical Blocks |
| Block Manager | Manages Block allocation, release, and references |
| Free Block Pool | Holds currently available physical Blocks |
| Attention Kernel | Reads KV Cache according to the Block mapping and computes Attention |
| Scheduler | Schedules execution based on request status and resource conditions |
3. Overall Structure of the Paging Mechanism
flowchart TD
A["Request Token Sequence"] --> B["Logical Token Position"]
B --> C["Compute Logical Block Index"]
C --> D["Query Block Table"]
D --> E["Get Physical Block Index"]
E --> F["Compute Offset Within Block"]
F --> G["Locate KV Cache"]
G --> H["Read Key and Value"]
H --> I["Perform Attention Computation"]
I --> J["Generate Model Output"]
K["Block Manager"] --> L["Free Block Pool"]
L --> M["Allocate Physical Block"]
M --> D
N["Request State Change"] --> O["Update Block Table"]
O --> D
style A fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
style B fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
style C fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
style D fill:#EAE8FA,stroke:#A49BD5,color:#51477D
style E fill:#EAF3EC,stroke:#83A995,color:#315D49
style F fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
style G fill:#EAF3EC,stroke:#83A995,color:#315D49
style H fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
style I fill:#EAF3EC,stroke:#83A995,color:#315D49
style J fill:#DCEFE5,stroke:#4F8B70,color:#24563F
style K fill:#EAE8FA,stroke:#A49BD5,color:#51477D
style L fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
style M fill:#EAF3EC,stroke:#83A995,color:#315D49
style N fill:#F7F4E8,stroke:#C7B77A,color:#675A2D
style O fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
6. Organization of KV Cache Blocks
To understand PagedAttention, the most important thing is to understand how Blocks are organized.
1. Basic Definition of a Block
A Block is a KV Cache storage unit with a fixed capacity.
Assume:
- Each Block holds 16 Tokens.
- Each Token stores a Key and a Value at each layer.
- Every Transformer Layer has corresponding cached data.
When a request has 35 Tokens, it requires:
The logical organization of the three Blocks:
| Logical Block | Token Range | Used Count |
|---|---|---|
| Block 0 | 0–15 | 16 |
| Block 1 | 16–31 | 16 |
| Block 2 | 32–34 | 3 |
The last Block still has 13 Tokens of remaining capacity.
This part is unused space inside the Block.
2. Calculating the Offset Within a Block
Assume the Block Size is 16 and the logical position of the Token is 35.
Logical Block index:
Offset within the Block:
Therefore:
- The logical Block index is 2.
- The offset within the Block is 3.
Then query the Block Table for the corresponding physical Block index to ultimately locate the KV Cache data.
General formulas:
3. Structure of the Block Table
Assume request A uses three logical Blocks:
| Logical Block | Physical Block |
|---|---|
| 0 | 3 |
| 1 | 8 |
| 2 | 1 |
The Block Table can be represented as:
block_table = {
"request_A": [3, 8, 1]
}
This means that logical Blocks 0, 1, and 2 of request A correspond to physical Blocks 3, 8, and 1, respectively.
Note that this is only a simplified Python representation to help understand the mapping relationship. Inside real vLLM, efficient data structures and GPU-accessible index information are used; it does not simply rely on a Python dictionary to perform every Token's GPU memory access.
4. Physical Layout of Blocks
The physical cache layout of PagedAttention is usually organized along dimensions such as model layer, KV type, Block, Head, and Head Dimension.
Conceptually, it can be understood as:
KV Cache
│
├── Layer 0
│ ├── Key
│ │ ├── Physical Block 0
│ │ ├── Physical Block 1
│ │ └── Physical Block N
│ │
│ └── Value
│ ├── Physical Block 0
│ ├── Physical Block 1
│ └── Physical Block N
│
├── Layer 1
│ ├── Key
│ └── Value
│
└── Layer N
├── Key
└── Value
The specific physical tensor layout depends on the Attention Backend and model configuration being used.
VII. Execution Principles of PagedAttention
PagedAttention does not simply store the KV Cache in blocks; it also needs to solve how to efficiently access these scattered cached data.
1. Cache Access in Traditional Attention
Suppose a request has 64 historical Tokens.
The traditional contiguous storage approach can directly access a contiguous segment of KV Cache:
Token 0 → Token 1 → Token 2 → ... → Token 63
The access logic is relatively simple.
However, contiguous memory allocation brings problems with dynamic expansion and GPU memory fragmentation.
2. Cache Access in PagedAttention
Suppose the Block Size is 16:
Logical Tokens:
0-15 → Logical Block 0
16-31 → Logical Block 1
32-47 → Logical Block 2
48-63 → Logical Block 3
The physical Blocks may be distributed as:
Logical Block 0 → Physical Block 5
Logical Block 1 → Physical Block 2
Logical Block 2 → Physical Block 9
Logical Block 3 → Physical Block 1
The Attention Kernel needs to find the corresponding physical cache according to the Block Table.
3. Attention Access Process
flowchart TD
A["Current Query"] --> B["Read logical Token position"]
B --> C["Calculate logical Block number"]
C --> D["Query Block Table"]
D --> E["Obtain physical Block address"]
E --> F["Calculate offset within Block"]
F --> G["Read historical Key"]
F --> H["Read historical Value"]
G --> I["Calculate QK similarity"]
H --> J["Participate in weighted sum"]
I --> K["Softmax"]
K --> L["Attention output"]
J --> L
style A fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
style B fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
style C fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
style D fill:#EAE8FA,stroke:#A49BD5,color:#51477D
style E fill:#EAF3EC,stroke:#83A995,color:#315D49
style F fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
style G fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
style H fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
style I fill:#EAF3EC,stroke:#83A995,color:#315D49
style J fill:#EAF3EC,stroke:#83A995,color:#315D49
style K fill:#EAE8FA,stroke:#A49BD5,color:#51477D
style L fill:#DCEFE5,stroke:#4F8B70,color:#24563F
4. What Does PagedAttention Change?
PagedAttention does not change the core mathematical computation of Attention.
What it changes is:
- The storage organization of KV Cache.
- The mapping from logical Tokens to physical Blocks.
- The way the Attention Kernel accesses historical KV.
- The management of cache allocation and release.
Therefore, the value of PagedAttention is mainly reflected in GPU memory management and high-concurrency inference efficiency.
8. Block Manager: Cache Allocation and Release
Block Manager is a key component in KV Cache management.
It is responsible for maintaining the usage status of physical Blocks and dynamically allocating and releasing cache according to the request lifecycle.
1. Responsibilities of Block Manager
| Responsibility | Specific Role |
|---|---|
| Block initialization | Create a pool of available physical Blocks |
| Block allocation | Allocate cache space for new requests |
| Block mapping | Establish the relationship between logical Blocks and physical Blocks |
| Block expansion | Request additional Blocks when a request grows |
| Block release | Reclaim cache when a request completes |
| Reference counting | Manage Blocks shared by multiple requests |
| Cache reuse | Support reuse scenarios such as prefix caching |
2. Free Block Pool
Suppose the system initializes 10 physical Blocks:
Free Block Pool:
[0][1][2][3][4][5][6][7][8][9]
Request A needs two Blocks:
Request A:
[0][1]
The free pool becomes:
Free Block Pool:
[2][3][4][5][6][7][8][9]
Request B needs three Blocks:
Request B:
[2][3][4]
When Request A completes, Block 0 and Block 1 can return to the free pool.
3. Block Allocation Process
flowchart TD
A["New request arrives"] --> B["Calculate the number of Blocks needed"]
B --> C["Query Free Block Pool"]
C --> D{"Are there enough free Blocks"}
D -->|"Yes"| E["Allocate physical Blocks"]
D -->|"No"| F["Check reclaimable cache"]
F --> G{"Do reclaimable resources exist"}
G -->|"Yes"| H["Free or reclaim Blocks"]
G -->|"No"| I["Wait or apply preemption policy"]
H --> C
I --> J["Wait for resources to become available"]
J --> C
E --> K["Update Block Table"]
K --> L["Request continues execution"]
style A fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
style B fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
style C fill:#EAE8FA,stroke:#A49BD5,color:#51477D
style D fill:#F7F4E8,stroke:#C7B77A,color:#675A2D
style E fill:#EAF3EC,stroke:#83A995,color:#315D49
style F fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
style G fill:#F7F4E8,stroke:#C7B77A,color:#675A2D
style H fill:#EAF3EC,stroke:#83A995,color:#315D49
style I fill:#F7EAE7,stroke:#C98D7C,color:#754438
style J fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
style K fill:#EAE8FA,stroke:#A49BD5,color:#51477D
style L fill:#DCEFE5,stroke:#4F8B70,color:#24563F
4. Block Release Mechanism
After a request finishes, the Block Manager checks the Blocks occupied by that request.
If a Block is no longer referenced by any other request, it can be released and put back into the free pool.
If a Block is being shared by multiple requests, it cannot be released directly; instead, its reference count must be decremented until no request is using it any more.
This mechanism is an important foundation that allows Prefix Caching to reuse caches safely.
IX. Prefix Caching: Prefix Cache Sharing
The paged structure of PagedAttention provides the basis for KV Cache sharing.
Prefix Caching allows different requests to reuse the KV Cache produced by an identical prefix, thereby reducing redundant Prefill computation.
1. Why is prefix caching needed?
In real-world workloads, many requests use a fixed system prompt.
For example:
Request A:
You are a professional Java assistant.
Please explain JVM garbage collection.
Request B:
You are a professional Java assistant.
Please explain the Java class loading mechanism.
Request C:
You are a professional Java assistant.
Please explain how the thread pool works.
All three requests contain the same system prompt.
If this shared prefix were recomputed every time, GPU compute resources would be wasted.
2. The reuse process of prefix caching
Assume the shared prefix has already been computed and the corresponding KV Cache Blocks still exist.
Subsequent requests can reuse these Blocks by matching the cached information.
flowchart TD
A["Request A"] --> C["Shared Token Prefix"]
B["Request B"] --> C
D["Request C"] --> C
C --> E["Execute Prefix Prefill"]
E --> F["Generate KV Cache Block"]
F --> G["Build Cache Index"]
G --> H["Reuse by Request A"]
G --> I["Reuse by Request B"]
G --> J["Reuse by Request C"]
H --> K["Compute A's Unique Content"]
I --> L["Compute B's Unique Content"]
J --> M["Compute C's Unique Content"]
style A fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
style B fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
style D fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
style C fill:#EAE8FA,stroke:#A49BD5,color:#51477D
style E fill:#EAF3EC,stroke:#83A995,color:#315D49
style F fill:#EAF3EC,stroke:#83A995,color:#315D49
style G fill:#EAE8FA,stroke:#A49BD5,color:#51477D
style H fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
style I fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
style J fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
style K fill:#DCEFE5,stroke:#4F8B70,color:#24563F
style L fill:#DCEFE5,stroke:#4F8B70,color:#24563F
style M fill:#DCEFE5,stroke:#4F8B70,color:#24563F
3. Basis for Prefix Cache Matching
Prefix Caching usually matches based on the content of the Token Block and the relevant computation context, rather than simply determining whether two pieces of text are similar.
Factors to consider:
- Whether the Token sequences are identical.
- Whether the models are the same.
- Whether the relevant computation configurations are compatible.
- Whether the multimodal input information is identical.
- Whether the cached Block still exists.
- Whether the cache meets the reuse conditions of the current request.
4. Why Is Reuse Usually Done by Full Block?
Paged cache is usually managed in units of Blocks.
For example, if Block Size is 16:
Common prefix:
Token 0–15: Full Block
Token 16–31: Full Block
Token 32–39: Unfilled Block
Full Blocks are easier to match and share in cache.
The last unfilled Block usually cannot be directly used as a shared prefix for any new request in the same way as a full Block. The exact reuse boundary depends on the cache granularity and matching strategy in the implementation.
5. Reference Counting and Copy-on-Write
When multiple requests share the same physical Block, the system needs to track reference relationships.
Assume:
Request A ──┐
├── Shared physical Block 5
Request B ──┘
If request A completes, it can only decrement the reference count of that Block, and the Block cannot be reclaimed directly.
If request B is still using that Block, the cache must continue to retain it.
When different content needs to be written after a shared prefix, the system also needs to avoid directly overwriting shared data. A common approach is Copy-on-Write, which allocates new Blocks when shared content needs to be modified.
10. Dynamic Expansion Mechanism of KV Cache
The generation length of large models is usually uncertain, so KV Cache must support dynamic growth.
1. Allocating Cache When a Request Begins
Assume Block Size is 16.
The Prompt has 30 Tokens:
At request start, two Blocks are required.
2. Expansion During the Decode Phase
As Tokens are generated:
| Current Token Count | Required Block Count |
|---|---|
| 30 | 2 |
| 31 | 2 |
| 32 | 2 |
| 33 | 3 |
| 48 | 3 |
| 49 | 4 |
When the Token count exceeds the capacity of the current Block, a new Block needs to be requested.
3. Dynamic Expansion Flow
flowchart TD
A["Request starts"] --> B["Allocate initial Block"]
B --> C["Execute Prefill"]
C --> D["Enter Decode"]
D --> E["Generate new Token"]
E --> F{"Does the current Block have remaining capacity?"}
F -->|"Yes"| G["Write to current Block"]
F -->|"No"| H["Request new Block"]
H --> I{"Is allocation successful?"}
I -->|"Success"| J["Update Block Table"]
I -->|"Failure"| K["Trigger insufficient resource handling"]
K --> L["Wait, preempt, or recompute"]
L --> H
J --> G
G --> M{"Has the stop condition been reached?"}
M -->|"No"| D
M -->|"Yes"| N["Release request cache"]
style A fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
style B fill:#EAF3EC,stroke:#83A995,color:#315D49
style C fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
style D fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
style E fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
style F fill:#F7F4E8,stroke:#C7B77A,color:#675A2D
style G fill:#EAF3EC,stroke:#83A995,color:#315D49
style H fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
style I fill:#F7F4E8,stroke:#C7B77A,color:#675A2D
style J fill:#EAE8FA,stroke:#A49BD5,color:#51477D
style K fill:#F7EAE7,stroke:#C98D7C,color:#754438
style L fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
style M fill:#F7F4E8,stroke:#C7B77A,color:#675A2D
style N fill:#DCEFE5,stroke:#4F8B70,color:#24563F