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.
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.
Follow one step of the engine with the four requests above. The step makes one new token for every request that runs.
- The scheduler looks at the waiting and running requests and picks the ones that run in this step.
- 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.
- The scheduler sends the new tokens and the block tables to the workers.
- 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.
- 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.
- Split it: 10,000 = 2 × 4,096 + 1,808. So the byte is in page 2, at offset 1,808 inside the page.
- Look up page 2 in the page table: frame 7.
- 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 starts at the start address plus 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.
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 of the paper:
Read it from left to right. The query belongs to the token being written, token . The key block is a small matrix: the keys of the tokens in block . So is not one number but a row of numbers, one score per token of the block. Dividing by and taking the exponential works on each number of the row.
The denominator adds up those exponentials over all blocks from 1 to . The bold is a column of ones: multiplying a row by it adds up the row. The symbol means " rounded up", the number of blocks that token needs. With and , that is 3 blocks.
The result is the row of attention weights for the tokens of block . On the right, mixes the values of block with those weights. The output 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 and three tokens with keys , and and values , and . The weights were 0.401, 0.198 and 0.401, and the output . Now store the same tokens in blocks of . 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:
== 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)Read the picture from left to right. The scores are : 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 . Block 2 contributes . The sum is , 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.
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 oThe first loop computes 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 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:
== 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 blockThe 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:
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())== 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: TrueThe largest difference in any layer is . 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 , 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:
== 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-05With 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 . 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:
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]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-07The merged result matches SDPA to , 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.
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:
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== 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-06One 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 . 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:
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) 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, filledSix 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, , 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:
n = len(ids)
slots = [cache.append_slot(req) for _ in range(n)] # the KV cache manager reserves the slots firstThen, 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:
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:
== 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: -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:
== 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 msEvery block size gives the right answer, within 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 tokens in blocks of holds blocks, so its waste is:
Read it this way. is the number of slots held: the number of blocks times the slots per block. Subtract the slots in use, and what is left is the empty end of the last block. For example, and give , the one free slot of Figure 6. gives , and gives , the largest waste possible for .
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:
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== 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 lengthThe two methods agree for every block size. The largest waste of any request is exactly , the bound, and the mean waste is close to , 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:
== 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]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 . 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.
pip install torch transformers datasets
python vllm_part3.py # downloads facebook/opt-125m (about 250 MB) and tatsu-lab/alpaca