PagedAttention

Allocate the KV cache in blocks .

PagedAttention stores a sequence’s keys and values in fixed-size blocks. A block table tracks their locations in GPU memory. The server can allocate blocks as needed and share them across compatible requests.

KV-cache allocation · block tables · copy-on-write

Read the paper

Reserved space can go unused

The server cannot know the final response length in advance. Compare the cache space reserved for a request with the amount it actually uses.

Compare reserved and used space

The response length is unknown when the request starts. Change the number of used slots within a fixed reservation.

answer tokens actually used7

one contiguous reservation

16 token slots

9 empty

used

reserved

wasted

56%

Those slots hold the request’s KV cache, which stores earlier keys and values. Reserving too much leaves unused space. Reserving too little requires more allocation.

Add pages as the request grows

Think of each cache block as a page with a fixed number of slots. Allocate another page when the current one fills. Only the last page can have unused slots.

Add a page when the current one is full

Each page holds four tokens here. Add tokens to see when the request needs another page.

tokens generated11

logical page 0

logical page 1

logical page 2

tokens stored

pages allocated

empty slots

Only the final block has unused slots. Full blocks are retained. Later blocks have not been allocated.

Keep pages in order

A book’s pages have a reading order even if they are stored on different shelves. The block table records where each page is in GPU memory. Select a request to follow the mapping.

Follow the page order

The pages can be stored in different places. Select a request to see how its page table keeps them in order.

page table

logical 0→ block 6

logical 1→ block 1

logical 2→ block 8

→

physical GPU memory

block 0

block 1crossed the

block 2

block 3

block 4

block 5

block 6The red fox

block 7

block 8quiet field

Logical token order is preserved. The attention kernel uses the table to locate each block of keys and values.

Share matching prefixes

Compatible requests with the same prefix can reuse cached blocks. Copy-on-write creates a private copy before a request modifies a shared block.

Share prefix blocks

Two requests start with matching cached prefixes. Compare shared prefix blocks with private continuation blocks.

answer A

shared 1

shared 2

shared 3

answer B

shared 1

shared 2

shared 3

shared physical blocks

private blocks

copies avoided

This is copy-on-write. Both requests can reference the same prefix blocks. Writing to a shared block requires a private copy. Appending after a full block only needs a new block.

Measure memory use across requests

Paging reduces unused reservations and can share prefix storage. It changes cache allocation without changing the attention equation.

Compare batch memory use

The contiguous layout reserves 20 slots per request. The paged layout allocates blocks as they fill. Change the request count to compare them.

simultaneous requests5

request 1

5 tokens

request 2

13 tokens

request 3

7 tokens

request 4

18 tokens

request 5

10 tokens

contiguous reservations100 slots

paged allocations64 slots

tokens actually stored53 slots

the saving

Paging uses 36% fewer slots in this example. The remaining capacity can be used for other requests.

the cost

The attention kernel must support block-table lookups. The cache layout changes. The attention equation and learned weights stay the same.

Original paper

Efficient Memory Management for Large Language Model Serving with PagedAttention Kwon et al. · 2023

Loading diagram…

Reference

← All guides

PagedAttention

PagedAttention stores the KV cache in fixed-size blocks. A block table maps each sequence’s logical positions to physical blocks in GPU memory.

Overview

How it works

A request’s blocks do not need to be adjacent. The server allocates more as its sequence grows, and the attention kernel follows the block table to read them in order. The attention equation stays the same.

Details

Unused reservations

Response lengths are not known in advance. Reserving one large contiguous region per request can leave unused space or produce gaps too small for another request. Paging reduces these allocation problems.

Details

Block allocation

Divide the cache into blocks with a fixed number of token slots. Allocate the next block when needed. In this simplified layout, unused space is limited to the final block of each sequence.

Details

Shared blocks and copy-on-write

Compatible requests can point to the same cached prefix blocks. Before modifying a shared block, a request receives a private copy. Appending beyond a full shared block only requires a new block for the continuation.

Details

Serving more requests

Paging reduces allocation waste and can avoid duplicate prefix storage. It does not compress the keys and values themselves. The server needs attention kernels that can follow block tables. Actual throughput depends on the workload and implementation.

Sources

Efficient Memory Management for Large Language Model Serving with PagedAttention ↗Kwon et al. · 2023