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 x1,x2,…,xnx_1, x_2, \dots, x_n:

P(x1,…,xn)=P(x1)⋅P(x2∣x1)⋅P(x3∣x1,x2)⋯P(xn∣x1,…,xn−1)P(x_1, \dots, x_n) = P(x_1) \cdot P(x_2 \mid x_1) \cdot P(x_3 \mid x_1, x_2) \cdots P(x_n \mid x_1, \dots, x_{n-1})

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 ∣\mid 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 qq, and earlier tokens with keys kjk_j and values vjv_j, the equation reads:

o=∑jajvj,aj=exp⁡(q⋅kj/d)∑texp⁡(q⋅kt/d)o = \sum_{j} a_j v_j, \qquad a_j = \frac{\exp(q \cdot k_j / \sqrt{d})}{\sum_t \exp(q \cdot k_t / \sqrt{d})}

Read it right to left. Take the dot product of the query with key jj, divide by d\sqrt{d}, and raise ee to that power. Divide by the same thing summed over all tokens tt: that is the softmax, and it gives the weight aja_j. The output oo is the sum of the values, each times its weight.

Now a tiny example that you can do on paper. The vectors have length d=2d = 2, so we divide by 2≈1.414\sqrt{2} \approx 1.414. The query is q=[1,0]q = [1, 0]. There are three earlier tokens:

tokenkeyvalueq⋅k/2q \cdot k / \sqrt{2}
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: e0.707≈2.03e^{0.707} \approx 2.03 and e0=1e^{0} = 1. 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:

python
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
plain text
== 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: True
One query looks at three tokensq = [1, 0]k1 = [1, 0]v1 = [1, 0]weight 0.401k2 = [0, 1]v2 = [0, 1]weight 0.198k3 = [1, 1]v3 = [1, 1]weight 0.401output = 0.401 v1 + 0.198 v2 + 0.401 v3 = [0.802, 0.599]
Our tiny example. The query matches keys 1 and 3 equally, so they get the same weight, 0.401. The output is the weighted average of the values.

Why keys and values can be kept

The causal mask: each token reads only itself and the tokens before itFourscoreandsevenyearsagoFourscoreandsevenyearsagoRow = the token that reads.Column = the token it may read.The last row (orange) is the newesttoken. It adds one row and readsall earlier columns.No earlier row ever reads a latertoken, so earlier keys and valuesnever change: they can be cached.
The causal mask. Each row reads only the columns up to itself. A new token adds a row at the bottom and never changes the rows above it.

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:

plain text
== 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.5

The 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:

python
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
plain text
== 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-08

The 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:

bytes per token=2×dmodel×L×2\text{bytes per token} = 2 \times d_{\text{model}} \times L \times 2

The first 2 counts the key and the value. dmodeld_{\text{model}} is the hidden size, LL 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:

python
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
plain text
== 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: granted
External fragmentation in 32 slotsA=8, B=6, C=8, D=6AAAAAAAABBBBBBCCCCCCCCDDDDDDB and D finishAAAAAAAACCCCCCCCFree: 6 + 10 = 16 slots. Request E needs 12 in one piece: refused. In blocks of 2 slots it fits.
Our 32-slot run. After B and D leave, 16 slots are free in two gaps of 6 and 10. A request for 12 slots in one piece is refused. If memory is handed out in small blocks that can sit anywhere, the same request fits.

Sixteen 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:

plain text
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 average

This 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:

plain text
== 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.

Paging: the program sees one row; the pages sit anywherevirtual pages (the program)page 0page 1page 2page 3page table0 -> 51 -> 22 -> 73 -> 0physical frames (real memory)p31p134p06p2frame numbers 0 to 7; empty framesbelong to other programs or are freeaddress 10,000: page 2, offset 1,808 -> frame 7 -> 7 x 4,096 + 1,808 = 30,480
Paging. The program sees pages 0 to 3 in a row. The page table sends them to frames 5, 2, 7 and 0 of real memory. Address 10,000 lands in page 2 and comes out at physical address 30,480.

To find a byte, the computer splits the virtual address into a page number and an offset inside the page. With a page size PP:

page=⌊v/P⌋,offset=v mod P,physical=table[page]×P+offset\text{page} = \lfloor v / P \rfloor, \qquad \text{offset} = v \bmod P, \qquad \text{physical} = \text{table}[\text{page}] \times P + \text{offset}

Read it in order. Divide the virtual address vv 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 P=4,096P = 4{,}096 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 2122^{12}, 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:

python
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
plain text
== 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:

plain text
== 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:

plain text
== 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 unused

There 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 systemvLLM
a process (a running program)a request
a bytea token's keys and values
a page of 4 KB or 16 KBa block of a fixed number of tokens (16 by default)
the page tablethe block table of each request
a page given when first toucheda block given when the last one is full
copy-on-write when a process forkscopy-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.

bash
pip install torch transformers psutil
python vllm_partb.py   # downloads facebook/opt-125m (about 250 MB)
Terminal output of vllm_partb.py: the tiny attention example, the cached keys test, the layer rebuilt from the cache, the allocator runs, address translation and pages on demand
The full output of vllm_partb.py, as it ran for this article.

The paper and the code

Attention Is All You Need on arXiv · vLLM on arXiv · our scripts for this page