vLLM, explained · Part 4 of 6 · Covers §4.4 to §4.6, §5, Figures 8 to 10
Sharing, Scheduling and Many GPUs
How vLLM lets several answers share one prompt's memory, what it does when memory runs out, and how it runs one model on many GPUs. We read §4.4 to §4.6 and §5, and build each piece in Python.
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 3 cut the KV cache into small blocks that can sit anywhere in GPU memory. This part shows what that freedom buys. Several answers can share one prompt's blocks. A full GPU can push requests out and bring them back. And one model can run on many GPUs with a single memory manager.
Each piece below shows the exact lines of the paper, then explains them. We build every mechanism in Python and check it against the library.
The map below is the paper's Figure 4, redrawn. Requests come in on the left. The scheduler in the middle decides which requests run, and its KV cache manager keeps the block tables. The workers on the right are the GPUs that run the model. Part 3 explained the block tables and the GPU block allocator.
This part adds the three highlighted pieces. They are the reference counts in the block tables (§4.4), the CPU block allocator (§4.5) and the model shards on several GPUs (§4.6).
The parts of vLLM, after the paper's Figure 4. The highlighted boxes are the subject of this part: the reference counts that let block tables share blocks, the CPU block allocator that holds preempted requests, and the model shards that split one model over several GPUs.
Start with a tiny example. A user sends the prompt "The best pizza topping is" and asks for three answers. The model samples three times and might write " mushrooms", " pineapple" and " extra cheese". This is parallel sampling: one prompt, several answers drawn at random, all made at the same time.
Each answer is its own sequence: the same prompt tokens, then its own new tokens. All three need the keys and values of the prompt tokens at every step. A system that gives each sequence its own contiguous cache stores the keys and values of the prompt three times. The keys and values are identical in all three copies, because they depend only on the prompt.
Where is this used? A code assistant shows several suggestions and lets the programmer choose. A chat service can show two answers and ask which one the user likes. Some systems draw many answers and keep the best one by some score. In all of these, the prompt is shared and the answers are not.
The picture shows the whole of Figure 8 as two moments. Follow the reference count on each block. In the first moment, both block tables say "logical 0 is block 7, logical 1 is block 1", so both blocks have a count of 2. In the second moment, A1 has written "fathers". Its table now says "logical 1 is block 3", a fresh copy, and the count of block 1 has fallen to 1.
Copy-on-write in two moments. Left: A1 and A2 map the same two physical blocks, each with a reference count of 2. Right: A1 wanted to write into the shared block 1, so it got a copy (block 3) and the count of block 1 fell to 1. A2 then writes into block 1 directly. Block 7 is full and stays shared.
Block 7 never changes. It is full, so no sample ever writes into it again, and it stays shared until both samples finish. Only the one block where the two answers start to differ is copied.
We build this ourselves. Our block manager keeps a pool of physical blocks, a block table and a length per sequence, and a reference count per block. It has three calls, and §5.2 of the paper will name the same three. fork makes a new sequence that points at its parent's blocks. append stores one new token, with copy-on-write inside it. free drops a sequence:
python
def fork(self, parent, child): """fork: a new sequence that maps every block of its parent. Nothing is copied; reference counts go up.""" self.table[child], self.length[child] = list(self.table[parent]), self.length[parent] for b in self.table[child]: self.ref[b] += 1 def append(self, seq, kv): """append: store the keys and values of one new token. kv: (layers, 2, heads, head size).""" t, pos = self.table[seq], self.length[seq] if pos % self.B == 0: # the last block is full (or there is none): take a new one t.append(self._allocate()) elif self.ref[t[-1]] > 1: # the last block is shared: copy-on-write new = self._allocate() self.pool[new].copy_(self.pool[t[-1]]) # copy the one block, then write into the copy self.ref[t[-1]] -= 1 t[-1] = new self.cow_copies += 1 self.pool[t[-1], :, :, :, pos % self.B] = kv self.length[seq] = pos + 1 def free(self, seq): """free: drop a sequence. A block goes back to the free list when no sequence maps it any more.""" for b in self.table.pop(seq): self.ref[b] -= 1 if self.ref[b] == 0: self.free_blocks.append(b) del self.length[seq]
The append call has three cases. If the last block is full, it takes a fresh block. If the last block is shared, it copies it first. Otherwise it writes in place. The pool is a real tensor that holds the keys and values of OPT-125M, for all 12 layers.
To run the model on this cache, a helper called extend reads each sequence's blocks in table order. It hands them to the model as the past keys and values, and stores the new ones with append. Parallel sampling is then short. We run the prompt phase once, fork four samples, and drop the prompt's own sequence:
python
mgr = BlockManager(512, B) mgr.new('prompt') logits = extend(mgr, ['prompt'], [prompt]) seqs = [f's{i}' for i in range(n)] for s in seqs: mgr.fork('prompt', s) mgr.free('prompt')
After that, each step draws one token per sample and calls extend for all four. We use the paper's prompt, "Four score and seven years ago", and a block size of 4, as in Figure 8. Method 2 is the library: model.generate with num_return_sequences=4 and the same random seed. It keeps one full copy of the cache per sample. If our shared blocks or our copies were wrong, the tokens would differ.
plain text
== 1. Parallel sampling (Figure 8): 4 samples share the blocks of one prompt, block size 4prompt of 7 tokens (with the start token </s>) in 2 blocks: </s> Four score and | seven years agoafter fork: every sample maps blocks [370, 26]; reference counts {370: 4, 26: 4}after the first new token: block tables [[370, 153], [370, 116], [370, 366], [370, 26]]; copy-on-write copies: 3 sample 1: ', as the Los Angeles Dodgers amassed a 54-55 record, the question was: Will the Dodgers compete for the National' sample 2: ' this song crossed your mind...I just jokingly said (again) it had the power to be the best instrumental your' sample 3: ', Dave wanted the quintessential "I am her Unicorns" phase, but he had to think ahead.\nLast' sample 4: ", Bellus had a massive eye tear on one of Justin Matthews' passing screens. Being in the 80s, the"Method 1 (paged, shared prompt) and Method 2 (model.generate, same seed): same 96 tokens: Truemax difference of the logits against one plain pass per sample: 2.2e-05at the end: 29 physical blocks with sharing, 32 without; copy-on-write copies in total: 3
Our own Figure 8, from the run above. Right after fork, all four block tables point at the same two physical blocks. After the first new token, three samples have their own copy of the second block, and the fourth writes into the original.
This is Figure 8 with four samples instead of two. With the start token, the prompt has 7 tokens: 4 in physical block 370 and 3 in block 26, with one free slot. After fork, both blocks have a reference count of 4.
Then all four samples write their first token. The first three find block 26 shared, so each gets a copy: blocks 153, 116 and 366. The fourth finds a count of 1 and writes into block 26 directly. That is 3 copies in all, exactly the paper's rule. Block 370 was full, so it stays shared to the end.
The check passes. All 96 tokens are the same as the library's, and the logits match one plain pass per sample to 2.2×10−5. (The samples are random text from a small model; only the agreement matters.)
Parallel sampling wants variety. Beam search wants the opposite: the single answer that the model finds most likely as a whole. A translator wants one good translation, not five random ones.
Greedy decoding does not give that answer. It picks the best next word and never looks back. Suppose the best first word has probability 0.5, but all its continuations are weak, at 0.2 each. A second-best first word of 0.4, followed by a word of 0.9, gives a better pair: 0.4 × 0.9 = 0.36 against 0.5 × 0.2 = 0.10. Greedy decoding never finds it, because it threw that first word away.
Beam search keeps a few candidates alive, say 4. They are called beams, like the beam of a torch: a narrow light that searches part of a large dark space. Each step grows every beam by one token and keeps the 4 best results. Weak beams die, and a strong beam can have several children.
The score of a beam is the sum of the log-probabilities of its tokens:
score(y1,…,yt)=i=1∑tlogP(yi∣x,y1,…,yi−1)
Read it from left to right. The tokens y1 to yt are the answer so far, and x is the prompt. Each term is the log of the probability that the model gives token i, given the prompt and the earlier tokens. Adding logs is the same as multiplying probabilities, which is Eq. 1 from Part 2. Logs are used because a product of many small numbers gets too small for a computer.
A tiny example with k=2 and three tokens a, b, c. The two beams are "a" with score −0.5 and "b" with score −1.0. The model gives "a" the next-token log-probabilities −0.2, −2.0 and −3.0, and "b" gives −0.1, −0.3 and −4.0. The six candidates score −0.7, −2.5, −3.5, −1.1, −1.3 and −5.0. The top two are "aa" (−0.7) and "ba" (−1.1).
Both beams survive here, each with one child. If "ab" had scored above "ba", beam "a" would have both children and beam "b" would die.
The tiny example as a tree. Two beams, "a" and "b", each try all three tokens. Of the six candidates, only the two best scores survive: "aa" at −0.7 and "ba" at −1.1. The other four are dropped.
Now look at the tree with memory in mind. Both survivors start with the prompt, so they share its cache. "aa" also reuses the cache of "a", its parent. In a real search, beams share long common starts and split late. That is the sharing Figure 9 shows.
Our beam search uses the same three calls. At each step, every new beam is a fork of its parent, and then all old beams are freed. Then the new token of each beam is stored with append:
python
top = torch.topk((scores[:, None] + logp).flatten(), k) parents, words = (top.indices // V).tolist(), (top.indices % V).tolist() new = [] for i, (p, w) in enumerate(zip(parents, words)): nid += 1 c = f'b{nid}' mgr.fork(beams[p], c) toks[c] = toks[beams[p]] + [w] new.append(c) if p != i: # a contiguous cache would copy the parent's whole cache contiguous_copy += mgr.length[beams[p]] for b in beams: mgr.free(b)
The first line is the score equation: the beam scores plus the log-probabilities of every next token, all k⋅∣V∣ of them, then the top k. Fork comes before free, so a block that a child still needs never reaches a count of 0. Method 2 is model.generate with num_beams=4:
plain text
== 2. Beam search (Figure 9): 4 beams fork, append and free blocks at every step, block size 4 beam 1: ', I was in my early 20s.\nI was in my early 20s.\nI was in my early' beam 2: ', I was in my early 20s.\n\nI was in my early 20s.\n\nI was in' beam 3: ', I was in my early 20s.\nI was in my early 20s.\nI was in my late' beam 4: ', I was in my early 20s.\nI was in my early 20s.\nI was in my mid'Method 1 (paged beam search) and Method 2 (model.generate, num_beams=4): same 96 tokens: Truefinal block tables: [[782, 921, 628, 975, 950, 147, 92, 201], [782, 921, 628, 975, 904, 521, 772, 907], [782, 921, 628, 975, 950, 147, 92, 201], [782, 921, 628, 975, 950, 147, 92, 201]]blocks mapped by all 4 beams: [782, 921, 628, 975]; physical blocks in use 14, without sharing 32copied during the search: 22 blocks by copy-on-write = 88 token slots; a contiguous cache that keeps beam i in slot i copies 1029 token slots
Our own Figure 9. The block tables of the four beams at the end. All four map the same first four blocks; beams 1, 3 and 4 map the same eight. Only beam 2 has its own last four blocks.
All 96 tokens match the library. The block tables tell the story of Figure 9 in numbers. All four beams share their first four blocks. Beams 1, 3 and 4 share all eight. They differ only in the token just chosen ("early", "late", "mid"), and its keys and values are not stored yet. Beam 2 split off earlier, at the double line break.
So 14 physical blocks hold what four separate caches would store in 32 blocks.
Physical blocks in use at each step of our two runs. Without sharing, four beams need four full caches (top). With sharing, beam search stays far lower. The four samples share only their short prompt, so they need almost as much as four separate caches.
We counted both in the run above. A contiguous cache that keeps beam i in slot i would copy 1,029 token slots over the 24 steps. Our block manager copied 22 blocks of 4, which is 88 token slots. (The library itself copies even more: it reorders the whole cache of all beams at every step.)
How much memory does sharing save in a larger setting? We run both methods again with vLLM's default block size of 16. The prompt is the 41-token translation prefix of Figure 10 below, and every answer has 48 tokens. The saving is the paper's measure: blocks saved by sharing, divided by the blocks needed without sharing.
plain text
== 3. Memory saved by sharing blocks, block size 16 (the vLLM default), prompt of the Figure 10 prefixprompt of 41 tokens, 48 new tokens; saving = blocks saved by sharing / blocks without sharing, averaged over the stepsparallel sampling, 2 / 4 / 6 samples: 23.1% / 34.7% / 38.5%beam search, width 2 / 4 / 6: 31.9% / 43.8% / 48.2%
Memory saved by sharing in our run, block size 16. More samples or wider beams share more. Beam search saves more than parallel sampling because beams also share parts of their answers.
Both grow with the number of sequences, and beam search saves more than sampling. The paper reports 6.1% to 9.8% for sampling and 37.6% to 55.2% for beam search, on OPT-13B with Alpaca requests (§6.3, Part 5). Our sampling numbers are higher because our prompt is long next to our answers. As the paper said, the saving depends on the prompt length.
The third case crosses the line between users. Most LLM products send the model more than the user typed. A support chatbot for a bank might put a hidden text in front of every question: "You are the assistant of Example Bank. Answer politely. Never give investment advice. Here are three sample answers..." This hidden text is the system prompt. It can be hundreds or thousands of tokens long, and it is the same for every user.
So a thousand users who each ask a short question send a thousand prompts that start with the same long text. Without sharing, the server computes the keys and values of that text a thousand times and stores a thousand copies. With paged memory, the text can be computed once, kept in a few blocks, and mapped by every request.
We store the 41-token prefix once, in blocks of 4. Each request is a fork of it. Our extend then runs the prompt phase on the task tokens only. We check the answer against model.generate on the full prompt, computed from scratch:
plain text
== 4. Shared prefix (Figure 10): the prefix is computed once and two requests map its blocks 'cheese =>': 3 task tokens computed instead of 44; maps 10 prefix blocks, owns 3; greedy output ' pouvoir\npouv'; same as model.generate on the full prompt: True 'I love you =>': 4 task tokens computed instead of 45; maps 10 prefix blocks, owns 4; greedy output ' le le le le le le le le'; same as model.generate on the full prompt: Trueprefix of 41 tokens in 11 blocks; its last block is partly full, so each request copied it once: 2 copy-on-write copies
The prompt phase computed 3 tokens instead of 44 for the first request, and 4 instead of 45 for the second. Both answers equal the library's answers on the full prompt. The prefix fills 10 blocks and 1 token of an eleventh. That last block is the one "marked copy-on-write": each request copied it once, before writing its own tokens.
A shared prefix before and with vLLM. Top: each request computes and stores the same 41-token prefix again. Bottom: the prefix is computed once and stored in 11 blocks; each request maps those blocks and computes only its own task tokens, 3 and 4 of them.
OPT-125M is far too small to translate. It writes nonsense French, so do not read the outputs as translations. The point is that the shared cache gives exactly the same tokens as computing everything again.
Sharing makes memory go further, but it cannot make memory endless. Answers grow one token at a time, and nobody knows how long they will get. Sooner or later, a running request needs a new block and none is free.
A tiny example shows the problem. A GPU has 6 free blocks of 4 tokens. Three requests run, and each holds 2 blocks. Now each writes its next token, and the last block of each is full. Each needs one more block, and there are none. Somebody must give up memory, or nobody can take a step.
Go back to the tiny example: 6 blocks, three requests with 2 blocks each, and all three need a third block. Request 3 arrived last, so it is preempted and gives up both of its blocks. Now 2 blocks are free. Requests 1 and 2 take one each and go on. Request 3 waits until one of the others finishes.
Why not take only one block from request 3, so that it could keep going? Because the next step of request 3 reads all of its blocks. With one block missing, it cannot run at all, and the block it kept is wasted space. This is the old Unix choice too: a program that cannot run gives up all its memory at once.
The picture puts both ways of recovering on one timeline. Three requests run. At step 5 no block is free, and request 3, the last to arrive, is preempted. At step 8 request 1 ends, and its blocks become free. With swapping, request 3's blocks waited in CPU memory and are copied back. With recomputation, they were thrown away and one prompt pass builds them again.
Either way, request 3 then runs on from the token where it stopped. Its answer is the same; only its latency is longer.
One preemption, recovered in two ways (a sketch, not a measurement). Top: with swapping, the preempted request's blocks wait in CPU memory and are copied back when room appears. Bottom: with recomputation, the blocks are thrown away and rebuilt in one prompt pass. In both, the request that arrived last is the one preempted.
We build the scheduler as a simulation in steps, with the memory rules above and no model. The requests are 200 real Alpaca prompts and answers, counted in OPT tokens; one arrives per step. The GPU has room for 64 blocks of 16 tokens. Here is the part that preempts:
python
# 2. every running request writes one token; it may need one more block. If none is free, preempt the # request that arrived last (all of its blocks), as often as needed. for r in list(running): if r not in running: continue n = REQ[r][0] + gen[r] # tokens stored so far if n % BS == 0: # the last block is full while free == 0: victim = running.pop() # the latest arrival hold = blocks(REQ[victim][0] + gen[victim]) free += hold st['preemptions'] += 1 st['preempt_steps'].append(t) if policy == 'swap': st['swap_out'] += hold; cpu += hold; cpu_max = max(cpu_max, cpu) preempted.append(victim); preempted.sort() if victim == r: break if r not in running: continue free -= 1
The running list is sorted by arrival, so running.pop() takes the request that came last. It loses all its blocks at once. At the start of each step, the scheduler brings back preempted requests, oldest first. It admits no new request while any is still out. We run the same traffic with swapping and with recomputation. In the output, look for two things: whether every request still gets all its tokens, and what each method pays for its preemptions.
plain text
== 5. First-come-first-served scheduling with preemption (simulation in steps, Alpaca request lengths)200 requests, one per step; prompt mean 19.9 tokens, output mean 53.8; GPU memory: 64 blocks of 16 tokensswap : 873 steps, mean batch 12.3, 356 preemptions; every request got all its tokens: Truerecompute: 873 steps, mean batch 12.3, 356 preemptions; every request got all its tokens: Trueswap : 705 blocks out, 705 in; at most 24 blocks in CPU memory (never more than the 64 GPU blocks: True) bytes moved, OPT-13B: 18.48 GB; OPT-125M: 831.7 MBrecompute: 9,115 tokens computed again, in 356 prompt passes
Our scheduler over 873 steps. The free blocks (green) soon fall to zero and stay near zero while the queue is long; each tick under the axis is one preemption. Only when the queue empties near the end do blocks come free.
The traffic is far more than 64 blocks can serve, on purpose. Memory is full almost all the time, and the scheduler preempts 356 times. Still, every request gets every one of its tokens. In a simulation in steps, both methods give the same timeline. What differs is the cost of each preemption.
Swapping moved 705 blocks out and 705 back in. For OPT-13B, with 800 KB of cache per token, that is 18.48 GB over the CPU-GPU connection. At no time did CPU memory hold more than 24 blocks, well under the bound of 64 that the paper promises. Recomputation moved nothing, but computed 9,115 tokens again, in 356 prompt passes.
Which is cheaper? A simple model of the two costs helps:
Read the left part first. Swapping pays for the bytes it moves, divided by the bandwidth. It also pays a fixed start-up cost tcopy for every separate copy, and there is one copy per block. The right part says that recomputation costs one prompt pass over all the tokens, whatever the block size.
A tiny example: say the connection moves 32 GB/s. Then 64 MB takes 2 ms. As 4 blocks with a fixed cost of 0.1 ms each, it takes 2.4 ms. As 4,096 tiny blocks, the fixed costs alone add 409.6 ms. Small blocks make swapping slow.
Now the real thing. We take a request with a 14-token prompt and 200 written tokens and do both on OPT-125M. First we check that recomputation gives back the same cache. Then we time the three ways to get that cache on the laptop GPU:
plain text
== 6. Swapping against recomputation on the real model (OPT-125M)a request with a 14-token prompt and 200 written tokens: 213 tokens of KV cacherecomputed in one pass against built one token at a time: max difference 1.8e-05; next token after recomputation the same: Truelaptop GPU (mps), FP16, fastest of several runs; 213 tokens = 7.85 MB of KV cache building it the first time, one pass per token: 1342.8 ms recomputation, one prompt pass: 9.5 ms swap out + swap in, blocks of 16 tokens: 5.9 ms; round trip exact: True recomputation took 142 times less time than building the cache one token at a timeswap time against block size (the same 213 tokens; one copy per block): block size 1 2 4 8 16 32 64 128 256 out ms 40.14 21.50 9.65 4.81 2.77 1.48 1.02 0.52 0.33 in ms 46.75 19.37 9.18 4.99 2.84 1.49 0.92 0.52 0.33 recompute 9.45 ms at every block size (it does not read the blocks) block size 1 means 213 copies each way: 0.19 ms per copy out; block size 256 means 1 copy
Time to swap the same 213-token cache out and back in, against the block size, on our laptop. One copy per block makes small blocks expensive. Recomputation does not read the blocks, so its cost is the same at every block size.
Recomputation is exact: the cache from one pass equals the cache built token by token to 1.8×10−5, and the next token is the same. Swapping is exact too, bit for bit.
The paper's claim about speed holds by a wide margin. Building the cache one token at a time took 1,342.8 ms. Recomputing it in one pass took 9.5 ms, 142 times less.
The block-size table shows the start-up cost. At block size 1, each direction makes 213 small copies, about 0.19 ms each, and the swap takes over 40 ms. At block size 16 it takes under 3 ms each way, and at 256 one copy does it. Recomputation sits at 9.45 ms whatever the block size. So recomputation wins for small blocks and swapping for large ones, the pattern the paper measures in §7.3 (Part 5).
Our laptop's numbers are not a server's. An Apple laptop's CPU and GPU share one memory, so "swapping" here copies within the same chips. A server moves the blocks over PCIe, which is slower. A server GPU also computes much faster. These timings come from a laptop shared with other jobs, so treat them as shapes.
Every number of a model's weights must sit in GPU memory while the model runs. In 16-bit numbers, each parameter takes 2 bytes. So a model of 13 billion parameters needs 26 GB for its weights alone, and the largest A100 holds 80 GB. The paper's Table 1 lists its three models: 26 GB, 132 GB and 346 GB of weights.
Why one model needs several GPUs. The weights of the paper's three models (Table 1) against the memory of one A100. Only OPT-13B fits on one card; the paper runs OPT-66B on 4 GPUs and OPT-175B on 8.
The weights are not all. The KV cache also needs room, and that room decides how many requests can run at once. On 4 A100s with 160 GB together, OPT-66B leaves 21 GB for the cache (Table 1). So the question is not only "does the model fit?" but "how do several GPUs work as one?".
Why is a sum enough? The last step of attention multiplies the outputs of all heads, side by side, by an output matrix Wo. Split the head outputs into GPU 0's part h(0) and GPU 1's part h(1), and split the rows of Wo the same way:
Read it from left to right. The row vector of all head outputs times the full matrix equals two smaller products added together. GPU 0 can compute h(0)Wo(0) with its own heads and its own rows of Wo, and GPU 1 the other term. One all-reduce adds them. This is just how matrix multiplication works, with no approximation.
A tiny example: h=(1∣2) and Wo with rows 3 and 4. The full product is 1⋅3+2⋅4=11. GPU 0 computes 1⋅3=3, GPU 1 computes 2⋅4=8, and the all-reduce gives 3+8=11.
Attention split by heads over two GPUs. GPU 0 holds heads 0 to 5 and GPU 1 heads 6 to 11. Each multiplies its head outputs by its own rows of the output matrix and gets a partial output. The all-reduce adds the partial outputs, 3 + 8 = 11 in the tiny example, and gives the sum to both GPUs.
The heads themselves need no talk between GPUs. Each head reads only its own queries, keys and values. Only the last multiplication mixes the heads, and that is the one place where the GPUs must add their results.
Here is one GPU's work, for the first attention layer of OPT-125M. It takes the query, key and value rows of its own heads and runs attention for those heads. Then it multiplies by its own columns of the output matrix. The second block is the all-reduce, here just a sum of the two results. If the split is right, the sum must equal the layer of the library:
python
def attention_shard(x, heads): """One GPU's work: the query, key and value rows of its own heads (column split), attention for those heads, and its columns of the output matrix (row split). The result is a partial sum, without the output bias.""" rows = slice(heads.start * D, heads.stop * D) q = (x @ attn.q_proj.weight[rows].T + attn.q_proj.bias[rows]) * attn.scaling k = x @ attn.k_proj.weight[rows].T + attn.k_proj.bias[rows] v = x @ attn.v_proj.weight[rows].T + attn.v_proj.bias[rows] h = len(heads) q, k, v = (t.view(-1, h, D).transpose(0, 1) for t in (q, k, v)) # (heads, tokens, head size) s = q @ k.transpose(1, 2) + torch.full((Tn, Tn), -float('inf')).triu(1) # causal mask o = (torch.softmax(s, -1) @ v).transpose(0, 1).reshape(-1, h * D) return o @ attn.out_proj.weight[:, rows].T, k # partial output, this GPU's keys
python
parts = [attention_shard(x, range(0, 6)), attention_shard(x, range(6, 12))]allreduce = parts[0][0] + parts[1][0] + attn.out_proj.bias # all-reduce = sum over the GPUs
(PyTorch stores a weight matrix transposed. So the "rows of Wo" in the equation are columns of out_proj.weight here.) The bias is added once, after the sum, or it would be counted twice. Method 2 is the unsplit attention layer of the library, which we capture while the model runs. We also split the feed-forward layer the same way and compare the whole layer:
plain text
== 7. Tensor parallelism (§4.6): one OPT-125M layer split over 2 simulated GPUs, 6 heads each11 tokens; GPU 0 has heads 0-5, GPU 1 has heads 6-11; each computes a partial output of shape (11, 768)all-reduce (sum of the 2 partial outputs) against the unsplit attention of the library: max difference 4.2e-07the whole layer (attention + feed-forward, 2 all-reduces) against the library layer: max difference 2.3e-05KV cache per GPU: keys of shape (6, 11, 64) (6 heads, all 11 positions); the two halves together equal the full keys: Trueper GPU and per token: 18,432 bytes of KV cache instead of 36,864 (FP16); the same block table serves bothdata sent by each all-reduce: 11 x 768 numbers; 2 all-reduces per layer, 24 per pass
One attention layer split over two GPUs, as in our run. Both GPUs get the same input. Each computes six heads and a partial output; the all-reduce adds the two partial outputs into the layer's output.
The two partial outputs add up to the library's attention output, to 4.2×10−7. The whole layer, with a second all-reduce after the feed-forward part, matches to 2.3×10−5. Each layer needs two all-reduces, so OPT-125M on 2 GPUs would need 24 per pass. Our two "GPUs" are two function calls on one laptop; a real setup sends these sums over fast links between the cards.
Look at the keys. Each GPU keeps keys for its 6 heads, but for all 11 positions. Each token's cache is cut in half, 18,432 bytes per GPU instead of 36,864, but every position is on every GPU. That fact is the point of the next box.
We try both fused writes in PyTorch on the laptop GPU. For the block write, 256 sequences each store one new key. The slot of a token is its physical block times 16 plus its offset inside the block:
python
slots = (tables[torch.arange(256), lens // B9] * B9 + lens % B9).to(GPU) # where each new token goes
python
def write_loop(): for i in range(256): cache[slots[i]] = new[i]def write_fused(): cache.index_copy_(0, slots, new)
The copy-on-write test copies 128 scattered blocks, once with one copy per block and once with one batched copy. In the output, compare the two times on each line, and check that both ways give the same result:
plain text
== 8. Kernels of §5.1 in PyTorch, on the laptop GPU (FP16, one layer's key cache: blocks x 16 x 12 x 64)block write of 256 new tokens: one copy per token 62.15 ms (256 launches), one scatter 0.155 ms (1 launch); same cache: True; 401xcopy-on-write of 128 scattered blocks: one copy per block 1.10 ms, one batched copy 0.405 ms; same result: True; 2.7x
Kernel fusion in our run. Writing 256 new tokens with one launch each pays the fixed launch cost 256 times; one fused launch pays it once and does the same work. The bars are a sketch; the two times are from our laptop GPU.
Both versions give the same cache, bit for bit. The single scatter is 401 times faster than 256 separate writes. Batching the 128 block copies makes them 2.7 times faster. A PyTorch call on an Apple GPU has much more overhead than a CUDA kernel launch, so the ratios on an A100 are different. The direction is the same: many small operations lose to one large one.
Our model was OPT-125M on an Apple laptop, not OPT-13B on an A100. The block tables, reference counts, copies and the agreement with model.generate are exact and do not depend on the hardware. The memory savings depend on our prompt and answer lengths, which are not the paper's workload.
The scheduler is a simulation in steps: it counts blocks and tokens but does not time anything. Our timings come from a laptop GPU that shares its memory with the CPU and ran other jobs at the same time. We took the fastest of several runs, but treat the numbers as shapes, not server numbers. Our two "GPUs" for tensor parallelism are two function calls; we did not measure the cost of a real all-reduce. Part 5 reads the paper's own measurements.
Next, in Part 5: §6 to §10. The experiments: throughput against latency, the measured savings of sharing, swapping against recomputation on an A100, and the limits.
Run it yourself
The script behind this part is code/papers/vllm/vllm_part4.py. It builds the block manager and runs parallel sampling, beam search and a shared prefix on it, each checked against model.generate. It measures the memory saved by sharing. It then simulates the scheduler with swapping and recomputation, and times both on the real model.
Last, it splits one layer over two simulated GPUs and tries two of the fused writes of §5.1. Every number is saved in results/part4.json. On an Apple M-series laptop it takes under a minute.