vLLM, explained · Part 3 of 6 · Covers §4 intro, §4.1 to §4.3, Figures 4 to 7

PagedAttention

How vLLM stores each request's keys and values in small blocks that can sit anywhere in memory, and still computes the same attention. We read §4.1 to §4.3 and build a block table that drives a real model.

Efficient Memory Management for Large Language Model Serving with PagedAttention. Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph E. Gonzalez, Hao Zhang, Ion Stoica. SOSP 2023, 2023. arXiv:2309.06180

Part 2 ended with a diagnosis. Earlier systems kept each request's KV cache in one long chunk, booked for the longest possible answer, and most of that memory sat empty. This part reads the paper's cure. There the authors cut the cache into small blocks and scatter the blocks across memory. Then they change attention so that it can still read them.

Each piece below shows the exact lines of the paper, then explains them. We also build the whole mechanism in Python and run a real model through it.

The problem, with four small requests

Start with a tiny memory that we can draw. It has room for the keys and values of 24 tokens. We call each such place a slot. Four requests want to use it: A has 5 tokens so far, B has 2, C has 7 and D has 3.

Before vLLM, a serving system booked one chunk per request, large enough for the longest answer it might write. Say that limit is 8 tokens. Then A, B and C each take a chunk of 8 slots, and the 24 slots are gone. Only 14 slots hold a token. The other 10 are booked for tokens that may never come, and request D cannot start.

vLLM cuts the same memory into 6 blocks of 4 slots. A request gets one block at a time, and a new block only when its last block is full. A needs 2 blocks, B needs 1, C needs 2 and D needs 1. All four requests now run in the same 24 slots.

Before vLLM: one chunk of 8 slots per request, booked at the startAAAAAA: 5 tokens, 3 emptyBBB: 2 tokens, 6 emptyCCCCCCCC: 7 tokens, 1 emptyDD waits24 slots, 14 tokens: 10 slots sit empty and request D (3 tokens) cannot start.With vLLM: blocks of 4 slots, one more block only when the last one is fullAAAAblock 0CCCCblock 1BBblock 2Ablock 3CCCblock 4DDDblock 524 slots, 17 tokens: all four requests run. Their blocks sit in any order.Each request leaves at most 3 empty slots, the end of its last block.
The same 24 slots, before and with vLLM. Top: one chunk of 8 slots per request leaves 10 slots booked but empty, and request D must wait. Bottom: blocks of 4, handed out one at a time, hold all four requests. A request's blocks need not be neighbours.

Two things changed. First, memory is given when it is needed, not booked at the start. Second, the blocks of one request can sit anywhere: A's two blocks are block 0 and block 3. The rest of this part explains what that costs. Attention must still find every key and value of a request, even when they are scattered.

The parts of vLLM

Before the paper's own diagram, here is our redraw of it. It shows the whole engine as one map. The parts that this page explains are highlighted.

vLLM, the whole engine: what this part explains is highlightedRequestsrequest Arequest Brequest CSchedulerpicks the requests of each stepKV cache managerBlock tables: one per requestGPU block allocatorCPU block allocatorthe CPU side: Part 4tablesWorker 0Cache engineModel shardWorker 1Cache engineModel shardWorker N-1Cache engineModel shardPagedAttention runs inside each shardand reads the blocks of its cache engine
The vLLM engine, redrawn from the paper's Figure 4. Requests come in on the left. The scheduler in the centre holds the KV cache manager, with the block tables and the block allocators. The workers on the right each hold a cache engine and a shard of the model. This part explains the highlighted pieces.

Follow one step of the engine with the four requests above. The step makes one new token for every request that runs.

  1. The scheduler looks at the waiting and running requests and picks the ones that run in this step.
  2. For each picked request, it asks the KV cache manager for a slot for the new token. The manager looks at the request's block table. If the last block has a free slot, the token goes there. If not, the GPU block allocator hands out one free block.
  3. The scheduler sends the new tokens and the block tables to the workers.
  4. Each worker runs the model. Its cache engine owns the GPU memory that holds the blocks. Attention reads the earlier keys and values through the block tables, and writes the new ones into the slots it was given.
  5. The new tokens go back to the users. When a request ends, its blocks go back to the allocator.

Most of this map is bookkeeping: lists of numbers that say which block belongs to whom. Only step 4 touches the keys and values themselves. That split is the design. The scheduler and the manager only handle numbers; they never move a key. The workers move keys, but never decide where they go.

Now the paper's own words. The first paragraph of §4 names the same pieces.

Background: how a computer finds a byte

A program sees its memory as one long row of numbered bytes, starting at 0. A byte's number in that row is its address. The row is a fiction. The real memory is cut into frames of 4,096 bytes each, and the program's row is cut into pages of the same size. Any page can sit in any frame.

A page table records the frame of each page. Take a small one. Page 0 is in frame 5, page 1 in frame 2, page 2 in frame 7 and page 3 in frame 0. The neighbours in the program's row are not neighbours in real memory.

To find a byte, the computer makes three moves. Take the address 10,000.

  1. Split it: 10,000 = 2 × 4,096 + 1,808. So the byte is in page 2, at offset 1,808 inside the page.
  2. Look up page 2 in the page table: frame 7.
  3. Put it back together: 7 × 4,096 + 1,808 = 30,480. That is the real address.

A street address works the same way. "House 8 on Elm Street" is two parts: the street, which a map turns into a place, and the house number, which you count along the street. The split costs one look at the map. In return, the streets can be anywhere.

vLLM does exactly this with tokens. A token's position plays the role of the address. A KV block plays the role of a page, and the block table plays the role of the page table. We draw the two lookups side by side in §4.2 below, after the paper has named the parts.

Background: what an attention kernel is

A program that uses a GPU runs on the CPU. When it needs heavy maths, it asks the GPU to run a small function on thousands of threads at once. That function is a kernel. Matrix products, softmax and attention are each one or a few kernels.

A kernel gets its data as an address in GPU memory plus a shape, such as "10 keys of 768 numbers each, starting here". From that it computes where every number is. Key tt starts at the start address plus tt times the size of one key. One multiplication finds any key. This only works if the keys sit one after another in one unbroken run of memory, a contiguous tensor.

That is why earlier systems kept each request's KV cache in one chunk. The attention kernels they used, such as FasterTransformer's, expect the keys and values of each request in one contiguous run of memory. A tensor cannot grow into memory that another request already uses. So the chunk had to be booked for the longest answer at the start.

Ordinary attention kernel: all keys of a request in one row of memoryFourscoreandsevenyearsagoourfathersbroughtforthkey t sits at start + t × (size of one key). One multiplication finds any key.The row must be booked for the longest answer, because it cannot grow into memory that is in use.PagedAttention kernel: keys in blocks of 4, anywhere in a pool of 9 blocksblock 0block 1block 2block 3block 4block 5block 6block 7block 8block table of the request: [7, 1, 3]key t sits in physical block table[t // 4], slot t % 4.One look into the table, then the same multiplication. The kernel needs the table as an input.
What the kernel has to know. Top: an ordinary attention kernel reads the keys of a request from one contiguous row, so a single multiplication finds key t. Bottom: with blocks, the same keys sit in physical blocks 7, 1 and 3 of a pool; the kernel must look up the block table first, then find the slot inside the block.

With blocks, the simple formula breaks. Key 9 is not 9 keys after key 0; it is in some block, wherever that block happens to be. There are two ways out. One is to copy the blocks into one contiguous tensor before each attention call, which costs a full copy of the cache at every step. The other is a new kernel that takes the block table as an extra input and follows it. PagedAttention is the second way.

PagedAttention

The mapping from the background above is short: blocks for pages, token positions for byte addresses, requests for programs. Here we need one extra fact. A key and a value exist for every token in every layer and every attention head. The footnote says how vLLM groups them.

Eq. 4: attention, block by block

Attention, as the Background page worked it, has three moves. The query of the new token gets a score against every earlier key. A softmax turns the scores into weights: take the exponential of each score, then divide each one by the sum of all of them. The output mixes the values with those weights. Eq. 4 writes the same three moves for keys and values in blocks.

Here is Eq. 4, written with the bold 1\mathbf{1} of the paper:

Aij=exp⁡(qi⊤Kj/d)∑t=1⌈i/B⌉exp⁡(qi⊤Kt/d)1,oi=∑j=1⌈i/B⌉VjAij⊤A_{ij} = \frac{\exp\left(q_i^\top K_j / \sqrt{d}\right)}{\sum_{t=1}^{\lceil i/B \rceil} \exp\left(q_i^\top K_t / \sqrt{d}\right) \mathbf{1}}, \qquad o_i = \sum_{j=1}^{\lceil i/B \rceil} V_j A_{ij}^\top

Read it from left to right. The query qiq_i belongs to the token being written, token ii. The key block KjK_j is a small matrix: the keys of the BB tokens in block jj. So qi⊤Kjq_i^\top K_j is not one number but a row of BB numbers, one score per token of the block. Dividing by d\sqrt{d} and taking the exponential works on each number of the row.

The denominator adds up those exponentials over all blocks tt from 1 to ⌈i/B⌉\lceil i/B \rceil. The bold 1\mathbf{1} is a column of ones: multiplying a row by it adds up the row. The symbol ⌈i/B⌉\lceil i/B \rceil means "i/Bi/B rounded up", the number of blocks that token ii needs. With B=4B = 4 and i=10i = 10, that is 3 blocks.

The result AijA_{ij} is the row of attention weights for the tokens of block jj. On the right, VjAij⊤V_j A_{ij}^\top mixes the values of block jj with those weights. The output oio_i adds up the mixes of all blocks. (The paper's text calls the attention it rewrites "Eq. 4" too; it means the attention equation of Part 2.)

Why splitting the softmax gives the exact answer

A softmax over blocks sounds risky. Each weight depends on every score, and the scores now live in different places. The trick is that the denominator is only a sum. Each block can add up its own exponentials, and the block sums can then be added together. The total is the same number that one long sum would give, because addition does not care about grouping.

A tiny example you can check by hand. The Background page worked attention for a query (1,0)(1, 0) and three tokens with keys (1,0)(1, 0), (0,1)(0, 1) and (1,1)(1, 1) and values (1,0)(1, 0), (0,1)(0, 1) and (1,1)(1, 1). The weights were 0.401, 0.198 and 0.401, and the output (0.802,0.599)(0.802, 0.599). Now store the same tokens in blocks of B=2B = 2. Block 1 holds tokens 1 and 2, block 2 holds token 3, with one empty slot.

Our script does Eq. 4 on these numbers, one block at a time, and prints every middle result:

plain text
== 9. Eq. 4 by hand: the Background example (query (1, 0), three tokens) in blocks of 2
block 1: scores 0.707, 0.000; exp 2.028, 1.000; block sum 3.028; weights 0.401, 0.198; adds (0.401, 0.198)
block 2: scores 0.707; exp 2.028; block sum 2.028; weights 0.401; adds (0.401, 0.401)
shared denominator 3.028 + 2.028 = 5.056; output (0.802, 0.599); torch softmax over all three tokens: (0.802, 0.599)
Eq. 4 on the Background example: query (1, 0), three tokens, blocks of 21. each block alone2. one addition3. each block againblock 1token 1score 0.707exp 2.028token 2score 0.000exp 1.000block sum 3.028weights 0.401, 0.198adds (0.401, 0.198)block 2token 3score 0.707exp 2.028block sum 2.028weights 0.401adds (0.401, 0.401)3.028 + 2.028= 5.056the shareddenominatoroutput (0.802, 0.599)Weight = exp / shared denominator. The two blockoutputs add up to the answer of ordinary attention.
Eq. 4 in three moves, on the Background example. First, each block scores its own tokens and adds up its own exponentials. Second, one addition joins the block sums into the shared denominator. Third, each block divides by it and adds its share of the output.

Read the picture from left to right. The scores are q⋅k/2q \cdot k / \sqrt{2}: 0.707, 0 and 0.707. Each block adds its own exponentials: 3.028 for block 1 and 2.028 for block 2. One addition gives the shared denominator, 5.056. Each block then divides its exponentials by 5.056 to get its weights, and mixes its own values.

Block 1 contributes 0.401⋅(1,0)+0.198⋅(0,1)=(0.401,0.198)0.401 \cdot (1, 0) + 0.198 \cdot (0, 1) = (0.401, 0.198). Block 2 contributes 0.401⋅(1,1)=(0.401,0.401)0.401 \cdot (1, 1) = (0.401, 0.401). The sum is (0.802,0.599)(0.802, 0.599), the same output as PyTorch's softmax over all three tokens at once.

The only step that needs all blocks is the one addition in the middle. Everything else is local to a block. That is the "catch" of Eq. 4 above, and it is a small one: each block passes one number to the others, not its keys.

The paper's picture of it

We wrote that procedure in Python. This is Method 1, our own PagedAttention, verbatim from the script. Look for the two loops over the block table. The block table is a list of pairs: the physical block number and how many slots of it are filled.

python
def paged_attention(q, cache, layer, table):
    """Eq. 4 for one query token. q: (H, d). table: [[physical block, # filled], ...] in logical order.
    Pass 1: the scores of each KV block. Pass 2: each block's values, weighted by its share of the softmax."""
    scale = 1 / math.sqrt(DH)
    scores = []
    for phys, filled in table:                                  # logical block j lives in physical block `phys`
        K_j = cache.K[layer, phys, :filled]                     # (filled, H, d): fetched from wherever it sits
        scores.append(torch.einsum('hd,thd->ht', q, K_j) * scale)          # q_i^T K_j / sqrt(d), (H, filled)
    m = torch.stack([s.max(-1).values for s in scores]).max(0).values      # subtract the max: same result, no overflow
    exps = [torch.exp(s - m[:, None]) for s in scores]
    denom = sum(e.sum(-1) for e in exps)                        # the sum over all ceil(i / B) blocks, (H,)
    o = torch.zeros(H, DH)
    for (phys, filled), e in zip(table, exps):
        A_ij = e / denom[:, None]                               # attention on block j, (H, filled)
        o += torch.einsum('ht,thd->hd', A_ij, cache.V[layer, phys, :filled])   # V_j A_ij^T
    return o

The first loop computes qi⊤Kj/dq_i^\top K_j / \sqrt{d} for every block. The line with denom is the one addition of the picture above. The line with m subtracts the largest score before the exponential. That changes no weight, because the same factor cancels above and below the fraction. It only keeps the exponentials from overflowing.

The second loop computes VjAij⊤V_j A_{ij}^\top and adds it up. The H dimension runs over the 12 heads of OPT-125M, each with its own query.

We ran OPT-125M on the paper's own sentence, with blocks of 4, and looked at the query of "forth" in layer 6. The model has 12 heads; we print the weight of each token averaged over them. Check that the three block totals add up to 1:

plain text
== 2. Eq. 4: the query of "forth" against KV blocks 0, 1 and 2 (layer 6, mean over the 12 heads)
block 0 (physical 7): Four 0.731, score 0.013, and 0.009, seven 0.012   block total 0.765
block 1 (physical 1): years 0.020, ago 0.024, our 0.032, fathers 0.041   block total 0.118
block 2 (physical 3): brought 0.074, forth 0.044   block total 0.118
all ten weights add up to 1.000000
a softmax inside block 0 alone would give 0.948, 0.022, 0.013, 0.017: the denominator must run over every block
Eq. 4 on OPT-125M (layer 6, mean of 12 heads): where "forth" looksforthqueryblock 0physical 7Four: 0.731Four0.731score: 0.013score0.013and: 0.009and0.009seven: 0.012seven0.012total 0.765block 1physical 1years: 0.020years0.020ago: 0.024ago0.024our: 0.032our0.032fathers: 0.041fathers0.041total 0.118block 2physical 3brought: 0.074brought0.074forth: 0.044forth0.044total 0.118One softmax over all ten keys: the three block totals add up to 1.
Eq. 4 on a real model. The query of "forth" meets three blocks stored in physical blocks 7, 1 and 3. Each slot is shaded by its attention weight. One softmax covers all ten slots, so the three block totals add up to 1.

The three block totals, 0.765, 0.118 and 0.118, add up to 1. That is the shared denominator at work. The last line shows what goes wrong without it. A softmax inside block 0 alone would give "Four" 0.948 instead of 0.731, because it ignores the six tokens in the other blocks.

The large weight on "Four" is not about its meaning. Many language models park much of their attention on the first token of a text. It is a habit learned in training, and OPT-125M shows it here in layer 6. For this part it is just a number that the paged and the contiguous computation must both reproduce.

Does paged attention give the same answer?

The paper's claim is that PagedAttention changes where keys and values live, not what attention computes. We test that claim in three ways.

Method 2 uses the library. We run the same ten tokens through the model with its own cache, past_key_values, which holds each layer's keys and values in one contiguous tensor. Then we call PyTorch's built-in scaled_dot_product_attention (SDPA) with the query of "forth". We compare the result with our paged output in each of the 12 layers:

python
    K, V = kv.layers[l].keys, kv.layers[l].values
    o_lib = F.scaled_dot_product_attention(q[None, :, None], K, V)[0, :, 0]   # (H, d), one query, all 10 keys
    diffs.append((o_lib - o_paged).abs().max().item())
plain text
== 3. The same attention with the library: past_key_values + torch scaled_dot_product_attention
attention output of "forth", paged (Method 1) against SDPA on the contiguous cache (Method 2), 12 layers:
  max difference 7.7e-07 (layer 10), smallest 9.5e-08
logits after "forth": our paged engine against the library, max difference 1.8e-05; same top token: True

The largest difference in any layer is 7.7×10−77.7 \times 10^{-7}. That is rounding: 32-bit numbers keep about 7 significant digits, and the two methods add the same terms in a different order. The final scores of the model for the next token, its logits, differ by at most 1.8×10−51.8 \times 10^{-5}, and both pick the same next token.

The second test is harder. We let our paged engine write 48 tokens on its own, picking the most likely token each time. We compare with the library's model.generate. To make sure that order in memory does not matter, the free blocks are handed out in a random order:

plain text
== 4. Greedy generation of 48 tokens, our paged engine against model.generate (random free-block order)
prompt 10 tokens; library text: " to learn a new language.\nI'm not sure if you're being sarcastic or no"...
B =  1: 57 blocks, first physical blocks [25, 61, 35, 9, 2, 5]; same 48 tokens: True; max logit difference 1.6e-05
B =  4: 15 blocks, first physical blocks [16, 5, 14, 13, 11, 10]; same 48 tokens: True; max logit difference 1.6e-05
B = 16:  4 blocks, first physical blocks [4, 1, 0, 7]; same 48 tokens: True; max logit difference 1.6e-05

With blocks of 1, 4 and 16 tokens, scattered over memory in a random order, the engine writes the same 48 tokens as the library. The logits never differ by more than 1.6×10−51.6 \times 10^{-5}. This is what Part 1 called "without affecting the model accuracy at all". The block layout is invisible to the model.

The third test pushes the softmax argument to its limit. Our paged_attention still looks at all scores before it divides. Can each block be finished completely alone, and the results joined later? Yes, if each block keeps three things: its largest score, its own sum of exponentials, and its own unweighted mix of values. Joining them needs only a rescale to a common largest score:

python
def merged_attention(q, cache, layer, table):
    """Each block alone keeps three things: its largest score m_j, its sum s_j of exp(score - m_j) and its
    unnormalised output u_j. Merging rescales every block to the largest m and divides once at the end."""
    scale = 1 / math.sqrt(DH)
    parts = []
    for phys, filled in table:
        s = torch.einsum('hd,thd->ht', q, cache.K[layer, phys, :filled]) * scale       # (H, filled)
        m = s.max(-1).values                                                           # (H,)
        e = torch.exp(s - m[:, None])
        parts.append((m, e.sum(-1), torch.einsum('ht,thd->hd', e, cache.V[layer, phys, :filled])))
    M = torch.stack([m for m, _, _ in parts]).max(0).values
    S = sum(s_ * torch.exp(m - M) for m, s_, _ in parts)                               # the shared denominator
    U = sum(u * torch.exp(m - M)[:, None] for m, _, u in parts)
    return U / S[:, None]
plain text
blocks finished one at a time and merged at the end, query of "forth", 12 layers of OPT-125M:
  merged against SDPA on the contiguous cache: max difference 7.2e-07

The merged result matches SDPA to 7.2×10−77.2 \times 10^{-7}, the same rounding as before. So the order of work is free. A GPU can give each block to a different group of threads, and join the pieces at the end. The paper does not describe this merge; we add it to show why the blockwise sum is safe.

The KV cache manager

Finding one token: the page-table lookup again

Now we can put the two lookups side by side. On the left, the operating system finds byte 10,000. On the right, vLLM finds the key of token 9, "forth", for request A of the paper's Figure 6. Its block table sends logical blocks 0, 1 and 2 to physical blocks 7, 1 and 3. We count positions from 0, as the code does.

Operating system: a bytevLLM: a tokenaddress 10,000page 2offset 1,80810,000 = 2 × 4,096 + 1,808page tablepage 0frame 5page 1frame 2page 2frame 7page 3frame 0frame 77 × 4,096 + 1,808 = 30,480token 9, "forth"logical block 2offset 19 = 2 × 4 + 1block tablelogical 0phys. 7logical 1phys. 1logical 2phys. 3physical block 33 × 4 + 1 = slot 13 of the poolThe same three moves: split the number, look the first part up, add the second part back.
The same lookup twice. Left: address 10,000 splits into page 2 and offset 1,808, the page table sends page 2 to frame 7, and the byte is at 30,480. Right: token 9 splits into logical block 2 and offset 1, the block table sends logical block 2 to physical block 3, and the token is in slot 13 of the pool.

The three moves are the same. Split the position by the block size: 9 = 2 × 4 + 1, so token 9 is in logical block 2 at offset 1. Look up logical block 2 in the block table: physical block 3. Put it back together: 3 × 4 + 1 = 13, the slot number if the pool is seen as one long row.

Our script does the lookup with one small function. We call it once with the page table of the background section and once with request A's block table. Then we check the key and value that it finds against the library's contiguous cache, for all 10 tokens in all 12 layers:

python
def locate(t, table, B):
    """The address split of paging. t: a position (a token, or a byte address). table: physical number of each
    logical block (or page). Returns (logical block, offset, physical block, slot in the pool as one long row)."""
    j, off = t // B, t % B                                      # which block, and where inside it
    phys = table[j]                                             # one look into the table
    return j, off, phys, phys * B + off
plain text
== 8. Finding a token through the block table, like an address through a page table
the operating system (Background page): page size 4,096 bytes, page table [5, 2, 7, 0]
  address 10,000 -> page 2, offset 1,808 -> frame 7 -> physical address 30,480
vLLM (request A of Figure 6): block size 4, block table [7, 1, 3]
  token 0     'Four' -> logical block 0, offset 0 -> physical block 7 -> slot 28 of the pool
  token 4    'years' -> logical block 1, offset 0 -> physical block 1 -> slot  4 of the pool
  token 7  'fathers' -> logical block 1, offset 3 -> physical block 1 -> slot  7 of the pool
  token 8  'brought' -> logical block 2, offset 0 -> physical block 3 -> slot 12 of the pool
  token 9    'forth' -> logical block 2, offset 1 -> physical block 3 -> slot 13 of the pool
keys and values found this way against the library's contiguous cache, 10 tokens x 12 layers: max difference 8.6e-06

One function serves both worlds. The same three lines turn address 10,000 into 30,480 and token 9 into slot 13. The keys found through the table match the library's keys to 8.6×10−68.6 \times 10^{-6}. They are not equal to the last bit. Our engine computed them a step at a time, and the library computed all ten in one pass. So the additions ran in a different order.

Neighbours in the request are not neighbours in memory. Tokens 7 and 8 are next to each other in the sentence, but they sit in slots 7 and 12. That is the price of paging, and the reason the kernel needs the table.

The manager in code

Here is our KV cache manager, the PagedKVCache class of the script. It owns the physical blocks of every layer, a free list, and one block table per request. The first block shows the allocator. The second shows the one important method, append_slot, which finds the slot for the next token:

python
class BlockAllocator:
    """Hands out physical block numbers from a free list, and takes them back."""
    def __init__(self, order):
        self.free = list(order)

    def allocate(self):
        if not self.free:
            raise MemoryError('no free KV block')
        return self.free.pop(0)

    def release(self, block):
        self.free.append(block)
python
    def append_slot(self, req):
        """Reserve the slot for one new token: the next free position of the last logical block,
        or a new physical block when the last one is full. Returns (physical block, offset)."""
        table = self.tables.setdefault(req, [])
        if not table or table[-1][1] == self.B:                 # last block full (or none yet): map a new one
            table.append([self.alloc.allocate(), 0])
        phys, filled = table[-1]
        table[-1][1] += 1                                       # the "# filled" column of the block table
        return phys, filled

Six lines of logic carry the whole policy of §4.2. A new physical block is taken from the free list only when the last block is full. The keys and values themselves live in two tensors of shape (layers, physical blocks, BB, heads, head size). The model writes each new token's key and value at the slot that append_slot returned.

Decoding, step by step: Figure 6

We ran this walk-through on OPT-125M. The prompt is the paper's own, exactly 7 tokens in the OPT tokenizer. The model then gets the paper's outputs "fathers", "brought" and "forth", one per step. We feed those words ourselves, because the small model would write something else (its own first choice is "team"). Our free list starts with blocks 7, 1 and 3, so the numbers match the figure. The core of each step is the start of our forward function:

python
    n = len(ids)
    slots = [cache.append_slot(req) for _ in range(n)]          # the KV cache manager reserves the slots first

Then, in each layer, the new keys and values go into those slots. A step with many tokens uses ordinary attention; a step with one token uses paged_attention:

python
        for t, (phys, off) in enumerate(slots):                 # write the new keys and values into their blocks
            cache.K[l, phys, off], cache.V[l, phys, off] = k[t], v[t]
        if n > 1:
            o = causal_attention(q, k, v)
        else:
            o = paged_attention(q[0], cache, l, cache.tables[req])[None]

In the output, watch the block table grow by one row only at "brought". At the end, the script prints what sits in each of the 9 physical blocks:

plain text
== 1. Figure 6: the block table of request A, step by step (block size 4, real OPT-125M)
prompt: 7 tokens ['Four', 'score', 'and', 'seven', 'years', 'ago', 'our']; we then feed the outputs "fathers", "brought", "forth"
prefill  (7 tokens): logical 0 -> physical 7 (4 filled)  logical 1 -> physical 1 (3 filled)
          model's top next token: ' team'
decode 1 ('fathers'): logical 0 -> physical 7 (4 filled)  logical 1 -> physical 1 (4 filled)
decode 2 ('brought'): logical 0 -> physical 7 (4 filled)  logical 1 -> physical 1 (4 filled)  logical 2 -> physical 3 (1 filled)
decode 3 (  'forth'): logical 0 -> physical 7 (4 filled)  logical 1 -> physical 1 (4 filled)  logical 2 -> physical 3 (2 filled)
physical blocks now (9 blocks of 4 slots; "." = free slot, "-" = free block):
  block 0:        -
  block 1:    years      ago      our  fathers
  block 2:        -
  block 3:  brought    forth        .        .
  block 4:        -
  block 5:        -
  block 6:        -
  block 7:     Four    score      and    seven
  block 8:        -
Request A, block size 4: the block table and the 9 physical blocks after each stepstepblock tablephysical blocks 0 to 8prefill7 tokens2 blockslogical 0 -> physical 7 (4 filled)logical 1 -> physical 1 (3 filled)012345678+ "fathers"8 tokens2 blockslogical 0 -> physical 7 (4 filled)logical 1 -> physical 1 (4 filled)012345678+ "brought"9 tokens3 blockslogical 0 -> physical 7 (4 filled)logical 1 -> physical 1 (4 filled)logical 2 -> physical 3 (1 filled)012345678+ "forth"10 tokens3 blockslogical 0 -> physical 7 (4 filled)logical 1 -> physical 1 (4 filled)logical 2 -> physical 3 (2 filled)012345678filled slotslot written in this step
The walk-through of Figure 6, from our run. Each row is one step: the block table in the middle and the nine physical blocks on the right. The table row that changed and the slot written in that step are highlighted. Only "brought" needs a new physical block.

Read the picture one row at a time. After the prefill, the table has two rows and the memory has 7 filled slots, in blocks 7 and 1. "fathers" changes one number in the table, 3 to 4, and fills the last slot of block 1. "brought" finds no free slot, so the table gets a third row and block 3 appears in memory. "forth" again changes only a number.

The block table after "brought" is the paper's table, row for row: 7 with 4 filled, 1 with 4 filled, 3 with 1 filled. We went one step further, to "forth", which fills a second slot of block 3. That is the state of Figure 5, and the step whose attention we checked against the library above. The physical blocks hold the words exactly where Figure 6 draws them.

One step for many requests

Take the four requests from the start of this page. In one step, A, B, C and D each add one token. The model gets a row of 4 tokens and runs its big matrix products once for all of them. In attention, A's token reads A's blocks through A's table, and D's token reads D's blocks through D's table. The tables keep the requests apart, even though their blocks are mixed in one pool.

The block size

We can see both forces on a laptop. For the memory side, we take 2,000 real requests from the Alpaca dataset, as in Parts 1 and 2. We count the slots held at the end of each request. For the speed side, we time our own paged_attention for one query over 2,048 keys, with the keys cut into blocks of different sizes. In the output, look at how the time falls as the blocks grow, while the answer stays right:

plain text
== 7. Block size against speed: our block-by-block attention, one query, a 2,048-token cache, one layer (CPU)
B =   1: 2048 blocks,   91.29 ms; max difference from SDPA 1.6e-07
B =   4:  512 blocks,   25.11 ms; max difference from SDPA 1.2e-07
B =  16:  128 blocks,    8.33 ms; max difference from SDPA 8.9e-08
B =  64:   32 blocks,    2.85 ms; max difference from SDPA 6.0e-08
B = 256:    8 blocks,    0.99 ms; max difference from SDPA 5.2e-08
contiguous SDPA, one call: 0.10 ms
memory holding tokens (Alpaca)B = 1B = 1: 100.0%100.0%B = 4B = 4: 98.1%98.1%B = 16B = 16: 91.1%91.1%B = 64B = 64: 70.3%70.3%B = 128B = 128: 51.4%51.4%2,048 chunk2,048 chunk: 3.7%3.7%time of our block loop (2,048 keys)B = 1B = 1: 91.3 ms91.3 msB = 4B = 4: 25.1 ms25.1 msB = 16B = 16: 8.3 ms8.3 msB = 64B = 64: 2.8 ms2.8 msB = 256B = 256: 1.0 ms1.0 msSmall blocks waste little memory but cost many separate fetches.Large blocks fetch fast but leave up to B - 1 empty slots per request.The 2,048-slot chunks: 152,590 tokens in 4,096,000 slots.
Both sides of the block size. Left: the share of held memory that holds tokens, for 2,000 Alpaca requests at their full length. Right: the time of our block-by-block attention over 2,048 keys. Small blocks save memory and cost time; large blocks do the reverse.

Every block size gives the right answer, within 1.6×10−71.6 \times 10^{-7} of SDPA. The time falls as the blocks grow, from 91 ms with blocks of one token to 0.99 ms with blocks of 256. One call of the library's contiguous SDPA takes 0.10 ms.

Be careful with what this shows.

Our loop is Python. Most of its cost per block is Python and the start of a small operation, not the GPU effect that the paper describes. The direction is the same, but the size is not. A real PagedAttention kernel runs all blocks inside one GPU program. The paper reports (§7.1) that its attention kernel takes 20% to 26% longer than FasterTransformer's, not ten times longer. The timings were the fastest of 7 runs on a laptop shared with other work, so treat them as a shape.

Waste is bounded by one block

The rule fits in one formula. A request of LL tokens in blocks of BB holds ⌈L/B⌉\lceil L/B \rceil blocks, so its waste is:

waste(L)=B⌈LB⌉−L  ≤  B−1\text{waste}(L) = B \left\lceil \frac{L}{B} \right\rceil - L \;\le\; B - 1

Read it this way. B⌈L/B⌉B \lceil L/B \rceil is the number of slots held: the number of blocks times the slots per block. Subtract the LL slots in use, and what is left is the empty end of the last block. For example, L=7L = 7 and B=4B = 4 give 4⋅2−7=14 \cdot 2 - 7 = 1, the one free slot of Figure 6. L=8L = 8 gives 4⋅2−8=04 \cdot 2 - 8 = 0, and L=9L = 9 gives 4⋅3−9=34 \cdot 3 - 9 = 3, the largest waste possible for B=4B = 4.

We check it on real lengths in two ways. Method 1 builds a block table token by token, as append_slot does, and counts the empty slots at the end. Method 2 is the formula:

python
def waste_by_table(L, B):
    """Method 1: append L tokens one by one through a block table; count the empty slots at the end."""
    table = []
    for _ in range(L):
        if not table or table[-1] == B:
            table.append(0)                                     # a new block, only when the last one is full
        table[-1] += 1
    return len(table) * B - L


def waste_closed(L, B):
    """Method 2: ceil(L / B) blocks of B slots, minus the L slots in use."""
    return B * math.ceil(L / B) - L
plain text
== 6. Waste per request at the end of generation, 2,000 Alpaca requests (prompt + answer, OPT tokenizer)
lengths: mean 76.3, shortest 8, longest 513 tokens; 152,590 tokens in all
block size max waste bound B-1 mean waste slots held  in use  methods agree
         1         0         0        0.0    152,590  100.0%  True
         2         1         1        0.5    153,576   99.4%  True
         4         3         3        1.5    155,568   98.1%  True
         8         7         7        3.4    159,480   95.7%  True
        16        15        15        7.4    167,424   91.1%  True
        32        31        31       14.8    182,240   83.7%  True
        64        63        63       32.2    216,960   70.3%  True
       128       127       127       72.1    296,704   51.4%  True
contiguous      2040               1971.7  4,096,000    3.7%  (one chunk of 2,048 slots per request)
OPT-13B with 12 GB of KV cache = 14,648 slots: chunks of 2,048 fit 7 requests; blocks of 16 fit 175 requests of these lengths, even at their full length

The two methods agree for every block size. The largest waste of any request is exactly B−1B - 1, the bound, and the mean waste is close to B/2B/2, as the "half-empty last block" argument predicts. With blocks of 16, 91.1% of the held memory holds tokens.

The last two rows show the scale of the change. Chunks of 2,048 slots hold 4,096,000 slots for 152,590 tokens, so only 3.7% of them hold anything. With 12 GB of KV cache for OPT-13B, Part 1's budget on a 40 GB A100, chunks of 2,048 fit 7 requests at once. Blocks of 16 fit 175 requests of these lengths, even when each one has reached its full length.

Two notes keep this honest. First, Alpaca requests are short, 76 tokens on average with the prompt, so the gain is large. Longer requests waste a smaller share in chunks too. Second, this count looks at one moment, the end of each request. Part 1 followed requests over their whole life and found the same picture: 3.6% with chunks of 2,048 against 90.7% with blocks of 16.

Two requests in one memory: Figure 7

We built Figure 7 with our code. Both requests run in one pool of 9 physical blocks, one iteration at a time. In iteration 1 both prompts are prefilled. In iterations 2 and 3, request A writes "fathers" and "brought" while request B writes "of" and "times". The free list starts 7, 1, 5, 2, 3, so the numbers match the figure. Then request A ends, and a third request C arrives:

plain text
== 5. Figure 7: requests A and B share one pool of 9 physical blocks (block size 4)
iteration 1 (both prefills): A: logical 0 -> physical 7 (4 filled)  logical 1 -> physical 1 (3 filled)
                             B: logical 0 -> physical 5 (4 filled)
iteration 2 (A writes 'fathers', B writes 'of'): A: [7, 1], B: [5, 2]
iteration 3 (A writes 'brought', B writes 'times'): A: [7, 1, 3], B: [5, 2]
physical blocks:
  block 0:    -
  block 1: A     years      ago      our  fathers
  block 2: B        of    times        .        .
  block 3: A   brought        .        .        .
  block 4:    -
  block 5: B        It      was      the     best
  block 6:    -
  block 7: A      Four    score      and    seven
  block 8:    -
each request against the library run alone: A max difference 1.7e-05, B max difference 1.5e-05
free list before A ends: [0, 4, 6, 8]
A ends; its blocks go back. free list now: [0, 4, 6, 8, 7, 1, 3]
a new request C of 9 tokens takes physical blocks [0, 4, 6]
Requests A and B share one pool of 9 physical blocks (block size 4)stepblock tables (physical blocks)physical blocks 0 to 8iteration 1both promptsA: 7 (4), 1 (3)B: 5 (4)012345678iteration 2A + "fathers",B + "of"A: 7 (4), 1 (4)B: 5 (4), 2 (1)012345678iteration 3A + "brought",B + "times"A: 7 (4), 1 (4), 3 (1)B: 5 (4), 2 (2)012345678A endsfree list now[0, 4, 6, 8, 7, 1, 3]B: 5 (4), 2 (2)012345678C arrives9 tokensB: 5 (4), 2 (2)C: 0 (4), 4 (4), 6 (1)012345678ABCslot written in this step
Figure 7 from our run, step by step. Each row shows both block tables, with the filled count of each block in brackets, and the nine physical blocks. The slots written in that step are highlighted. When A ends, its blocks 7, 1 and 3 go back to the free list; C then takes blocks 0, 4 and 6.

Read the picture from the top. In iteration 1, A's prompt fills blocks 7 and 1, and B's four-token prompt fills block 5 exactly. In iteration 2, B's new token "of" finds block 5 full, so B gets block 2. A's "fathers" fits in block 1. In iteration 3 it is the other way round: A's "brought" needs a new block, 3, and B's "times" fits in block 2.

After iteration 3, the pool matches Figure 7 block for block. Each request's logits agree with the library run on that request alone, to within 1.7×10−51.7 \times 10^{-5}. Sharing one pool did not let one request disturb the other.

Then request A ends. Its blocks 7, 1 and 3 go back to the end of the free list. A new request C of 9 tokens needs 3 blocks and gets 0, 4 and 6, the next ones on the list. Blocks 7, 1 and 3 wait for the request after it. No copy, no compaction, no search for a gap of the right size: a free block is a free block.

What this part sets up

§4.1 to §4.3 build one mechanism from three pieces. PagedAttention computes attention block by block, with one softmax over all blocks, and gives the same result as attention over one contiguous tensor. The block table records where each logical block of a request lives, and finds any token with the same split-and-look-up as a page table. The KV cache manager hands out a physical block only when the last one is full, and takes blocks back when a request ends.

Because a block table is only a list of numbers, two requests can point at the same physical block. Part 4 builds on that: shared prompts, beams, copy-on-write, and what happens when the free list runs empty.

What our small run cannot show

Our engine is Python on a laptop CPU, with OPT-125M in 32-bit numbers. It reproduces the logic of §4.1 to §4.3 exactly: the block table, the allocation rule and the attention result. It does not reproduce the speed. The paper's PagedAttention is a CUDA kernel that reads blocks inside one GPU program; our loop starts a separate small operation for every block. Our timings show the direction of the block size trade-off, not its real size.

We chose the order of the free list so that the block numbers match Figures 6 and 7. The paper does not say how vLLM picks a free block. The random orders of our generation test show that the choice does not change the result. We also fed the paper's output words to the model ourselves, because the small model would not write them.

Next, in Part 4: §4.4 to §4.6 and §5. Sharing blocks between samples and beams, copy-on-write, preemption, swapping, and running on many GPUs.

Run it yourself

The script behind this part is code/papers/vllm/vllm_part3.py. It builds a block allocator, a paged KV cache and PagedAttention from scratch, and runs OPT-125M through them. It walks through Figures 6 and 7 and checks every result against the library. It also counts the waste per request on Alpaca, times the block loop, does the page-table lookup for tokens, and works Eq. 4 by hand. Every number is saved in results/part3.json. On an Apple M-series laptop it takes under a minute.

bash
pip install torch transformers datasets
python vllm_part3.py   # downloads facebook/opt-125m (about 250 MB) and tatsu-lab/alpaca
Terminal output of vllm_part3.py: the block table of Figure 6 step by step, Eq. 4 on the query forth, the check against the library, greedy generation with three block sizes, the two requests of Figure 7, the waste per request, the block size timings, the token lookup and Eq. 4 by hand
The full output of vllm_part3.py, as it ran for this article.

The paper and the code

vLLM on arXiv · vLLM on GitHub · our scripts for this part