vLLM, explained · Background · Covers Vaswani et al. (2017) §3.1 and §3.2; virtual memory, paging and memory allocators
The KV Cache and Paging
The two ideas the paper joins: the cache of keys and values that a language model keeps while it writes, and the pages an operating system uses to hand out memory. With small runs you can check.
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
The vLLM paper takes an idea from operating systems and puts it inside a language model. To follow it, you need both halves. One half is how a model remembers the text it has already read: the KV cache. The other half is how a computer hands out memory to programs that grow and shrink: paging.
This page builds both from the ground up, with small runs that you can check by hand. If you know one half already, skip to the other.
A model writes one token at a time
A language model does one thing. You give it a piece of text, and it gives back a probability for every possible next token. A token is a piece of text: a word, part of a word, or a sign. The model picks one token, adds it to the text, and asks itself again. An answer of 300 tokens takes 300 rounds.
The probability of a whole text is built from these one-step guesses. For a text of tokens :
Read it left to right. The chance of the whole text is the chance of the first token, times the chance of the second given the first, and so on. The bar means "given". Each factor is one round of the model. Suppose the model gives "Four" a chance of 0.01, then "score" after "Four" a chance of 0.5, then "and" after "Four score" a chance of 0.9. The three tokens together get 0.01 × 0.5 × 0.9 = 0.0045.
The point for this paper is in the shape of the formula. Every factor looks back at all earlier tokens. The model must know about the whole text so far, every round. The question is what it keeps in memory so that it does not read the whole text again each time.
Attention: a query, keys and values
The part of the model that looks back at earlier tokens is attention. The Transformer paper of 2017 describes it in two sentences.
For one new token with query , and earlier tokens with keys and values , the equation reads:
Read it right to left. Take the dot product of the query with key , divide by , and raise to that power. Divide by the same thing summed over all tokens : that is the softmax, and it gives the weight . The output is the sum of the values, each times its weight.
Now a tiny example that you can do on paper. The vectors have length , so we divide by . The query is . There are three earlier tokens:
| token | key | value | |
|---|---|---|---|
| 1 | [1, 0] | [1, 0] | 1 / 1.414 = 0.707 |
| 2 | [0, 1] | [0, 1] | 0 / 1.414 = 0 |
| 3 | [1, 1] | [1, 1] | 1 / 1.414 = 0.707 |
The softmax: and . The sum is 2.03 + 1 + 2.03 = 5.06. So the weights are 2.03 / 5.06 = 0.401, then 0.198, then 0.401. The output is 0.401 × [1, 0] + 0.198 × [0, 1] + 0.401 × [1, 1] = [0.802, 0.599]. Tokens 1 and 3 match the query, so the output leans towards their values.
We check this with code, two ways. Method 1 follows the equation step by step. Method 2 is PyTorch's built-in attention:
def attention_by_hand(q, K, V):
"""softmax(q K^T / sqrt(d)) V, one step at a time."""
d = q.shape[-1]
scores = K @ q / math.sqrt(d) # how well the query matches each key
weights = torch.exp(scores) / torch.exp(scores).sum() # softmax: positive, sums to 1
return scores, weights, weights @ V # weighted average of the values== 1. Attention for one query over three tokens (d = 2)
scores q.k/sqrt(2): [0.707, 0.0, 0.707]
weights softmax : [0.401, 0.198, 0.401] sum 1.000
output, Method 1 : [0.802, 0.599]
output, Method 2 : [0.802, 0.599] agree: TrueWhy keys and values can be kept
We test this claim on a real model, OPT-125M, the smallest model of the OPT family that the vLLM paper serves. We run it on the first 8 tokens of a sentence. Then we run it on the same 8 tokens followed by 9 more. If the claim is right, the keys and values of the first 8 tokens are the same in both runs, in all 12 layers:
== 2. Do the keys of earlier tokens change when more tokens follow? (OPT-125M, FP32, CPU)
8 tokens alone, then the same 8 tokens followed by 9 more
largest change of a key or value of the first 8 tokens, over all 12 layers: 7.39e-06
largest key value, for scale: 6.5The largest change is 0.0000074, against values as large as 6.5. That is rounding noise from adding numbers in a different order, not a real change. Later tokens do not touch earlier keys and values.
The new token needs only its own query
So each step of writing needs three things: the query of the new token, and the keys and values of all tokens so far. Only the query is new work. We check this inside OPT-125M. We run the model on all tokens but the last, which fills the cache. Then we feed the last token alone and record what the first attention layer receives and returns.
Method 1 rebuilds that layer by hand. It computes the query of the new token, reads every key and value from the cache, and applies the attention equation. Method 2 is the library's own output for the same layer:
def layer0_from_cache(h, cache):
"""Method 1: query of the new token only; keys and values of all tokens read from the cache."""
H, D = attn.num_heads, attn.head_dim
qn = (attn.q_proj(h) * attn.scaling).view(1, 1, H, D).transpose(1, 2) # (1, 12, 1, 64); OPT scales q
Kc, Vc = cache.layers[0].keys, cache.layers[0].values # (1, 12, n, 64), new token included
w = torch.softmax(qn @ Kc.transpose(-1, -2), dim=-1) # (1, 12, 1, n): one weight per token
o = (w @ Vc).transpose(1, 2).reshape(1, 1, H * D) # weighted values, heads joined
return attn.out_proj(o), w== 3. Layer 0 for the newest token, rebuilt from the cache by hand
input to layer 0: (1, 1, 768) (one token); cached keys: (1, 12, 17, 64)
attention weights of head 0 over the 17 tokens: 0.04 0.05 0.01 0.03 0.02 0.01 0.04 0.02 0.02 0.01 0.01 0.02 0.02 0.03 0.07 0.58 0.03
Method 1 (by hand from the cache) vs Method 2 (the library): max difference 5.96e-08The input to the layer is one token, a vector of 768 numbers. The cache holds keys for all 17 tokens, split into 12 heads of 64 numbers each. The two methods agree to 0.00000006. This is the whole job of attention while a model writes: one query against a growing cache. In head 0, most of the weight (0.58) goes to one earlier token.
How large the cache gets
Each token stores one key and one value, each as long as the model's hidden size, in every layer. With 2 bytes per number (FP16), the cache of one token is:
The first 2 counts the key and the value. is the hidden size, the number of layers, and the last 2 is bytes per number. For OPT-125M: 2 × 768 × 12 × 2 = 36,864 bytes, about 36 KB per token. For OPT-13B, the paper's main model: 2 × 5,120 × 40 × 2 = 819,200 bytes, which is 800 KB per token. A single answer of 2,048 tokens then needs 1.68 GB. Part 1 checks this formula against the real tensors.
So the cache is large, it grows by one token per step, and nobody knows its final size until the answer ends. That is a memory problem, and computers have faced it before.
How a computer hands out memory
Memory is a long row of numbered slots. When a program needs space, it asks an allocator for a run of slots. The allocator finds a free run, marks it as taken, and returns where it starts. When the program is done, the run goes back.
Most data in deep learning lives in contiguous runs: one unbroken stretch of slots per tensor. That is simple and fast, because the next element is always in the next slot. But it has a weakness. Requests of different sizes come and go, and they leave holes between them.
Here is the weakness in 32 slots. Four requests take 8, 6, 8 and 6 slots. Then B and D finish:
class FirstFit:
"""Give each request one contiguous run of slots: the first free gap that is large enough."""
...
def alloc(self, name, n):
for s, g in self.gaps():
if g >= n:
self.used[name] = (s, n)
return True
return False== 4. Contiguous memory: a first-fit allocator (memory of 32 slots)
after A=8, B=6, C=8, D=6: AAAAAAAABBBBBBCCCCCCCCDDDDDD....
after B and D finish: AAAAAAAA......CCCCCCCC.......... free 16, largest gap 10
request E needs 12 slots in one piece: refused, although 16 slots are free
the same memory in blocks of 2 slots, any block anywhere:
free blocks 8; E needs 6 blocks: grantedSixteen slots are free, and a request for 12 is refused, because no single gap holds 12. This is external fragmentation: free memory that exists but is cut into pieces too small to use. The fix in the last line is the fix of this whole page. If a request may take small blocks from anywhere, every free block is useful.
The same effect shows over a long run. We replay 5,000 requests of 20 to 400 slots in a memory of 4,096 slots, with old requests finishing at random:
trace of 5000 requests in 4096 slots, sizes 20 to 400; a request that does not fit is refused:
contiguous first fit: memory holding data 81.6% on average; 2468 refused, 2456 of them while enough slots were free in total; slots not holding data at a refusal: 746 on average
blocks of 16: memory holding data 91.9% on average; 2473 refused; slots not holding data at a refusal: 305 on averageThis trace sends far more work than the memory can hold, so both designs refuse about half of the requests. The difference is in how full the memory is while they work. Contiguous runs keep 81.6% of the memory holding data; blocks keep 91.9%. In the contiguous design, 2,456 of the 2,468 refusals happened while enough slots were free in total, just not in one piece. Blocks waste only the unused end of each request's last block.
Rounding up: the buddy allocator
Many allocators make bookkeeping easier by rounding every request up to a power of two: 32, 64, 128 and so on. A well-known design, the buddy allocator, splits memory in halves until a piece of the right power of two remains. The vLLM paper assumes that its baseline, Orca, uses one. Rounding has a price:
== 4b. The buddy allocator rounds every request up to a power of two
request 25 -> chunk 32: 7 slots never used (22% of the chunk)
request 300 -> chunk 512: 212 slots never used (41% of the chunk)
request 513 -> chunk 1024: 511 slots never used (50% of the chunk)
request 1500 -> chunk 2048: 548 slots never used (27% of the chunk)A request just above a power of two wastes almost half of its chunk: 513 slots get 1,024. That is internal fragmentation, created on purpose to make the allocator simple.
Paging: the operating system's answer
Operating systems met this problem in the 1960s, with programs instead of requests. Their answer is paging, and every laptop and phone uses it today.
Memory is cut into pages of one fixed size. A program does not get one long run of real memory. It gets a list of pages, and each page can sit anywhere. The program still sees one unbroken row of addresses, its virtual memory. A table, the page table, records where each of its pages really is.
To find a byte, the computer splits the virtual address into a page number and an offset inside the page. With a page size :
Read it in order. Divide the virtual address by the page size and round down: that is the page number. The remainder is the offset, the position inside the page. Look the page up in the table to get its real frame, multiply by the page size, and add the offset back.
A worked example with bytes. The address 10,000 divided by 4,096 is 2, remainder 1,808. So it is in page 2 at offset 1,808. Our table sends page 2 to frame 7. The physical address is 7 × 4,096 + 1,808 = 30,480.
Hardware does not divide. The number 4,096 is , so it shifts the address right by 12 bits to get the page. It keeps the low 12 bits as the offset. Our run does it both ways:
def translate_div(v):
"""Method 1: page number and offset by division."""
page, offset = v // P, v % P
return page, offset, page_table[page] * P + offset
def translate_bits(v):
"""Method 2: what the hardware does. 4096 = 2^12, so shift by 12 bits and keep the low 12 bits."""
page, offset = v >> 12, v & 0xFFF
return page, offset, (page_table[page] << 12) | offset== 5. Paging: from a virtual address to a physical one
virtual 10000 -> page 2, offset 1808 -> frame 7 -> physical 30480; bit method agrees: True
virtual 4095 -> page 0, offset 4095 -> frame 5 -> physical 24575; bit method agrees: True
virtual 4096 -> page 1, offset 0 -> frame 2 -> physical 8192; bit method agrees: True
this laptop's page size: 16384 bytes (16 KB)Look at addresses 4,095 and 4,096. They sit next to each other for the program, but they land in frames 5 and 2, far apart in real memory. The program never knows. The laptop that ran this uses pages of 16 KB; many other computers use 4 KB.
Pages on demand
Paging gives a second gift. A page does not need real memory until the program uses it. The program can ask for a gigabyte, and the operating system only writes that down. Real memory is given page by page, at the moment a page is first touched. We can watch this on the laptop. We ask for 1 GB, then write one byte into each page of the first 256 MB:
== 5b. Pages on demand: map 1 GB, then touch 256 MB of it
resident memory before: 1022.7 MB
after mapping 1 GB: 1022.7 MB (+0.0 MB)
after touching 256 MB: 1278.7 MB (+256.0 MB, 16384 pages written)Asking for 1 GB cost nothing. Touching 16,384 pages of 16 KB cost exactly 256 MB. The resident memory is the real memory a program holds, and it grew only where pages were used. A program that books a lot but uses little costs only what it uses.
The waste of paging is small and has a clear bound. A program's last page may be partly empty, so it wastes less than one page:
== 5c. The waste of paging is the unused end of the last page
1 bytes -> 1 pages of 4096 = 4096 bytes, 4095 unused
4096 bytes -> 1 pages of 4096 = 4096 bytes, 0 unused
4097 bytes -> 2 pages of 4096 = 8192 bytes, 4095 unused
10000 bytes -> 3 pages of 4096 = 12288 bytes, 2288 unusedThere is no external fragmentation at all, because every page has the same size and any free frame fits any page.
Sharing and copy-on-write
Paging gives a third gift: sharing. Two page tables can point to the same frame. On Linux or macOS, a program can start a copy of itself. The copy gets a new page table that points to the same frames as the original.
Nothing is copied. Only when one of them writes to a shared page does the operating system copy that one page first. This is copy-on-write. Memory is copied only where the two really differ.
The two halves together
Put the halves side by side. A language model's KV cache grows one token at a time, its final size is unknown, and many requests of different sizes come and go. Serving systems before vLLM stored each cache in one contiguous run, booked for the longest possible answer. That is the old allocator with all its waste: booked space that is not used yet, rounding, and gaps between runs.
The vLLM paper's move is to treat the KV cache the way an operating system treats a program's memory:
| Operating system | vLLM |
|---|---|
| a process (a running program) | a request |
| a byte | a token's keys and values |
| a page of 4 KB or 16 KB | a block of a fixed number of tokens (16 by default) |
| the page table | the block table of each request |
| a page given when first touched | a block given when the last one is full |
| copy-on-write when a process forks | copy-on-write when several answers share one prompt |
One thing does not carry over for free. A program reads memory through the processor, which follows the page table in hardware. Attention reads keys and values in a GPU kernel, which expected them in one contiguous tensor. So the paper had to write a new attention kernel that follows the block table: PagedAttention. Part 1 starts the paper there.
Run it yourself
The script behind this page is code/papers/vllm/vllm_partb.py. It runs the tiny attention example, tests the cached keys of OPT-125M, rebuilds one attention layer from the cache, and replays the allocator traces. It also translates addresses and maps 1 GB of memory to watch pages arrive. Every number is saved in results/partb.json. It runs on a CPU in under a minute.
pip install torch transformers psutil
python vllm_partb.py # downloads facebook/opt-125m (about 250 MB)
The paper and the code
Attention Is All You Need on arXiv · vLLM on arXiv · our scripts for this page