vLLM, explained · Part 6 of 6 · Covers §4 and §5, rebuilt in Python
Build It from Scratch
We write a small vLLM in about 500 lines of Python: blocks, block tables, PagedAttention, a scheduler and parallel sampling. It runs the real OPT-125M, matches the transformers library and serves real requests.
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
Parts 1 to 5 read the paper. In this part we build its core ourselves, in about 500 lines of Python. Then we run it on the real weights of a small OPT model.
The proof has three steps. First, each piece does what the paper says, and we print it doing so. Second, the whole engine writes the same tokens as the transformers library, to the last token. Third, it serves a batch of real requests faster than the same code with one contiguous chunk per request.
Each piece below shows the exact lines of the paper, the code that builds them, and what the code printed.
The map: Figure 4 as seven files
A serving engine is a program that takes requests from many users and runs one model for all of them. Before we write one, we need a map. The paper gives it in Figure 4.
Each box of Figure 4 is a file of our package, minivllm. Dashed boxes are in the paper but not in our code:
We left out two boxes. The CPU block allocator serves swapping, which our laptop cannot use, as we explain below. Workers 1 to N-1 serve a model split over many GPUs (Part 4).
The code lives in code/papers/vllm/minivllm. It uses PyTorch for arithmetic and transformers only for the weights. The first lines of our script count the lines of each file:
== 1. The package minivllm
block_manager.py 151 lines
kv_cache.py 27 lines
attention.py 49 lines
model.py 64 lines
sequence.py 31 lines
scheduler.py 71 lines
engine.py 108 lines
total 501 lines of Python (no CUDA)| File | Box of Figure 4 | What it holds | Paper |
|---|---|---|---|
sequence.py | Requests | Requests, their samples and the sampling settings | §4.4, §4.5 |
scheduler.py | Scheduler | First come, first served; preemption by recomputation | §4.5 |
block_manager.py | KV cache manager | Free list, reference counts, block tables, copy-on-write | §4.2 to §4.4 |
kv_cache.py | Cache engine | One big tensor cut into blocks; the block copy | §4.2, §5.1 |
model.py | Model shard | OPT written out by hand, reading its keys and values through block tables | §4.3 |
attention.py | Model shard | PagedAttention: Eq. 4, and the fast versions the engine uses | §4.1 |
engine.py | the arrows | The loop: schedule, run the model, sample, fork, free | §4.3, §5.2 |
A map does not show the order in which things act. The second picture does: one step of the engine, as calls from file to file.
The engine asks the scheduler what to run (1 to 4), makes any block copies (5) and calls the model (6). In each layer, the model stores the new keys and values (7), and PagedAttention reads the old ones block by block (8, 9). The engine then picks the next tokens and tells the block manager about new samples and finished requests (10, 11).
The model is facebook/opt-125m, the smallest OPT, built like the OPT-13B of the paper. It has 12 layers and 12 attention heads of 64 numbers. We run it in FP32 on the CPU, so that our numbers can match the library's closely.
The KV cache as blocks
Here is the whole cache, from kv_cache.py. Look at the shape in the docstring first; the rest follows from it:
class PagedKVCache:
"""GPU memory for keys and values, booked once at start-up and cut into num_blocks physical blocks.
Shape: (layers, 2, num_blocks, block_size, heads, head_dim). Index 0 of the second axis holds keys, 1 values.
Every layer uses the same block numbers, so one block table per sequence serves all layers."""
def __init__(self, num_layers, num_blocks, block_size, num_heads, head_dim, dtype=torch.float32, device='cpu'):
self.num_blocks, self.block_size = num_blocks, block_size
self.data = torch.zeros(num_layers, 2, num_blocks, block_size, num_heads, head_dim, dtype=dtype, device=device)
def blocks(self, layer):
"""Keys and values of one layer, each (num_blocks, block_size, heads, head_dim)."""
return self.data[layer, 0], self.data[layer, 1]
def write(self, layer, slots, k, v):
"""Store the new keys and values (t, heads, head_dim) at their slots (t,) = block * block_size + offset."""
keys, values = self.blocks(layer)
keys.view(-1, *keys.shape[2:])[slots] = k # view the blocks as one long list of slots
values.view(-1, *values.shape[2:])[slots] = vRead the shape from left to right. There are 12 layers. Each layer has two halves, keys and values. Each half is cut into num_blocks blocks. Each block has block_size places for tokens, and each place holds 12 heads of 64 numbers.
Now the method write, for a tiny cache of 9 blocks of 4. view(-1, ...) lays the 9 blocks end to end as one list of 36 slots, without copying. Then [slots] = k puts each new key at its slot. Two new tokens at slots 7 and 15 are stored by one line.
Every layer uses the same block number, so one block table per sequence serves all 12 layers. For OPT-125M in FP32, one token takes bytes, 72 KB, and a block of 16 tokens takes 1.2 MB. Read the product as: keys and values, 12 layers, 768 numbers per layer (12 heads of 64), 4 bytes per number.
PagedAttention, Eq. 4
Here is Eq. 4 as the paper writes it. (The in the bottom is a vector of ones; it adds up the numbers of block .)
Read it from left to right. is the query of token . holds the keys of block , so is a row of scores, one per token of the block. Dividing by keeps the scores in a good range.
is the number of blocks that hold tokens 1 to ("ceil" rounds up). The bottom adds the exponentials of all scores in all those blocks. So is the row of weights for block . Last, mixes the values of block with those weights, and adds the blocks together.
A tiny example you can check by hand. Take and three tokens, so block 1 holds tokens 1 and 2 and block 2 holds token 3. Let the scores be 0, 0 and 0.693, whose exponentials are 1, 1 and 2. The bottom is .
So and . With values 4, 8 and 2, the output is . A softmax over all three tokens at once gives the same weights and the same 4.
Method 1 is Eq. 4 word for word, from attention.py. It handles one query token. Watch for two loops: the first gets the scores of each block, the second mixes the values of each block.
def paged_attention_eq4(q, k_blocks, v_blocks, block_table, context_len):
"""Eq. 4 for one query token i: q (H, D), the sequence's block table, tokens 1..context_len. Returns (H, D)."""
B, D = k_blocks.shape[1], q.shape[-1]
n_blocks = -(-context_len // B) # ceil(i / B) blocks hold the context
scores = []
for j in range(n_blocks):
K_j = k_blocks[block_table[j]] # fetch block j from wherever it sits: (B, H, D)
n_j = min(B, context_len - j * B) # the last block may be only partly filled
scores.append(torch.einsum('hd,bhd->hb', q, K_j[:n_j]) / D ** 0.5) # q_i^T K_j / sqrt(d): (H, n_j)
# The denominator of Eq. 4 sums exp(...) over all blocks; we subtract the largest score first so that
# exp() cannot overflow. This changes no result: it cancels between the top and the bottom of the fraction.
m = torch.cat(scores, -1).max(-1, keepdim=True).values # (H, 1)
total = sum(torch.exp(s - m).sum(-1, keepdim=True) for s in scores)
o = torch.zeros_like(q)
for j, s in enumerate(scores):
A_ij = torch.exp(s - m) / total # the attention scores on block j: (H, n_j)
V_j = v_blocks[block_table[j]][:s.shape[-1]] # (n_j, H, D)
o += torch.einsum('hb,bhd->hd', A_ij, V_j) # o_i = sum_j V_j A_ij^T
return oWalk through it with the test below: 10 tokens, , block table [7, 1, 3]. n_blocks is . For the loop fetches physical block 7 and uses all 4 of its tokens. For it fetches block 3, and n_j is , because the last block holds only 2 tokens.
einsum('hd,bhd->hb', ...) means "for each head, the dot product of the query with each key". So each block gives 12 heads by n_j scores. The variable total is the bottom of Eq. 4, and the second loop is the top, block by block. Subtracting the largest score m keeps every exponential at 1 or below; in FP32, is already too large to store.
The engine uses a faster form: it gathers a sequence's blocks in table order, blocks[block_table], then runs one ordinary attention. Method 2 is the library: we copy the blocks into one contiguous tensor and call PyTorch's scaled_dot_product_attention. We put 10 tokens in physical blocks 7, 1 and 3, as in Figure 5. In the output, look for the size of the differences, and for the last line:
== 3. PagedAttention (Eq. 4): one query against 10 tokens in 3 scattered blocks of 4 (12 heads of 64)
Eq. 4 block by block vs torch on a contiguous copy: max difference 4.2e-07
gathered version (used by the engine) vs torch: max difference 2.4e-07
same blocks moved to physical 0, 5, 8 (new block table): max difference 0.0e+00All three agree to within , the size of rounding errors in FP32. The last line is the point of paging. We moved the same three blocks to other places in memory and changed only the block table. The output did not change at all, not even by one rounding error.
Physical blocks and block tables
The allocator and the block table, from block_manager.py. The allocator has three operations, take a block, share it and let go of it; the table translates a token's position into a slot:
class BlockAllocator:
"""Hands out physical KV blocks by number and counts how many logical blocks point at each one (§4.4)."""
def __init__(self, num_blocks):
self.num_blocks = num_blocks
self.free_list = list(range(num_blocks))[::-1] # pop() hands out block 0 first, then 1, 2, ...
self.ref_count = [0] * num_blocks
def allocate(self):
if not self.free_list:
raise MemoryError('no free KV block')
block = self.free_list.pop()
self.ref_count[block] = 1
return block
def share(self, block):
"""One more logical block points at this physical block."""
self.ref_count[block] += 1
def free(self, block):
"""One logical block lets go; the physical block returns to the free list when nobody points at it."""
self.ref_count[block] -= 1
if self.ref_count[block] == 0:
self.free_list.append(block)
@property
def num_free(self):
return len(self.free_list)
@dataclass
class BlockTable:
"""The block table of one sequence (Figure 6): logical block j lives in physical block blocks[j]."""
blocks: list = field(default_factory=list)
num_tokens: int = 0 # tokens whose keys and values are stored
def filled(self, j, block_size):
"""The "# filled" column of Figure 6: how many slots of logical block j hold a token."""
return min(block_size, self.num_tokens - j * block_size)
def slot(self, pos, block_size):
"""Where token number pos lives: its physical block times the block size, plus its offset."""
return self.blocks[pos // block_size] * block_size + pos % block_sizeFollow a cache of 4 blocks. At the start, free_list is [3, 2, 1, 0]. The first allocate pops 0 from the end and sets its count to 1. If a second sequence shares block 0, share raises the count to 2. Each free lowers it by 1. Only when it reaches 0 does block 0 go back on the list.
So the allocator is a stack of free block numbers: to allocate is to pop one, to free is to push it back. Both take the same tiny time, whatever the size of the cache.
The block table is a plain list plus a token count, because every block but the last is full. The method slot is the address translation of virtual memory, shown here for two tokens of our run:
Take "the" at position 8. With , and , so it is place 0 of logical block 2. Entry 2 of the table [2, 3, 5] is 5. So its slot is . Two divisions and one lookup find any token, however long the sequence.
Decoding one request, step by step
Steps 1 to 3 are two methods of our BlockManager. The prompt step calls allocate. Each decoding step calls append_slot. Both return slots, the addresses that PagedKVCache.write needs:
def allocate(self, seq_id, num_tokens):
"""Prompt phase (§4.3, step 1): book only the blocks that the prompt fills. Returns the prompt's slots."""
t = BlockTable([self.allocator.allocate() for _ in range(cdiv(num_tokens, self.block_size))], num_tokens)
self.tables[seq_id] = t
return [t.slot(p, self.block_size) for p in range(num_tokens)]
def append_slot(self, seq_id):
"""Find the slot of the next token (§4.3, steps 2 and 3; §4.4, copy-on-write). Returns the slot."""
t, B = self.tables[seq_id], self.block_size
if t.num_tokens % B == 0: # last block full: map a new logical block
t.blocks.append(self.allocator.allocate())
else:
last = t.blocks[-1]
if self.allocator.ref_count[last] > 1: # the last block is shared: copy it before writing
new = self.allocator.allocate()
self.copies.append((last, new)) # the block engine copies the data later
self.allocator.free(last) # ref count of the old block goes down by one
t.blocks[-1] = new
slot = t.slot(t.num_tokens, B)
t.num_tokens += 1
return slotcdiv is division that rounds up: 7 tokens need blocks. So allocate pops 2 blocks, builds the table, and returns 7 slots, one per prompt token.
Now append_slot, for request A after its 7-token prompt. num_tokens is 7, and , not 0. So the last block has room: this is step 2 of the paper. The block is not shared, so no copy. The slot is place 3 of the last block, and the count becomes 8.
At the next call, : the last block is full. The first branch takes a new block, which is step 3 of the paper. The branch for a shared block belongs to §4.4, further down.
Now we replay Figures 6 and 7 with the real model. OPT puts a start token, </s>, before every prompt. So "Four score and seven years ago" is 7 tokens, like the paper's prompt. B is "It was the best of times", also 7 tokens. Block size 4, a cache of 9 physical blocks, as in the figures. In the output, watch the "filled" count of each request's last block, and the count of free blocks:
== 2. Block tables (Figures 6 and 7): block size 4, a cache of 9 physical blocks
after the prompt step:
A logical 0 -> physical 0, filled 4: </s> | Four | score | and
A logical 1 -> physical 1, filled 3: seven | years | ago
B logical 0 -> physical 2, filled 4: </s> | It | was | the
B logical 1 -> physical 3, filled 3: best | of | times
free blocks: 5 of 9
after the decoding step 1:
A logical 0 -> physical 0, filled 4: </s> | Four | score | and
A logical 1 -> physical 1, filled 4: seven | years | ago | ,
B logical 0 -> physical 2, filled 4: </s> | It | was | the
B logical 1 -> physical 3, filled 4: best | of | times | ,
free blocks: 5 of 9
after the decoding step 2:
A logical 0 -> physical 0, filled 4: </s> | Four | score | and
A logical 1 -> physical 1, filled 4: seven | years | ago | ,
A logical 2 -> physical 4, filled 1: the
B logical 0 -> physical 2, filled 4: </s> | It | was | the
B logical 1 -> physical 3, filled 4: best | of | times | ,
B logical 2 -> physical 5, filled 1: the
free blocks: 3 of 9This is Figure 6, step by step. After the prompt, each request holds 2 blocks, and its second block is filled 3 of 4. In step 1 the model reads ",", the token it chose in the prompt step, and its key and value fill the free slot. Filled goes from 3 to 4, and no block is taken. In step 2 it reads "the", the last block is full, and each request gets a new physical block.
Our allocator hands out the lowest free number, so the numbers differ from the paper's 7, 1 and 3. That changes nothing. Request A's logical block 1 is in physical block 1 and its logical block 2 is in physical block 4, with B's blocks in between. This is Figure 7.
One iteration for many requests
Here is one iteration of our model, from model.py. The Batch holds the joined list of tokens, the position of each token in its own sequence, its slot, and the block tables. Before the code, look at what goes in, for the prompt step of requests A and B above:
A and B both start at position 0, because a position counts inside one request. But their slots differ. A's prompt goes to slots 0 to 6, in blocks 0 and 1. B's prompt goes to slots 8 to 14, in blocks 2 and 3. Slot 7 stays empty until the next step. Now the code:
@torch.no_grad()
def forward(self, batch, cache):
"""Run one iteration. Returns the logits (R, vocab) of the last token of each scheduled sequence."""
T, H, D = batch.input_ids.shape[0], self.h, self.dh
x = self.embed[batch.input_ids] + self.pos_embed[batch.positions + POS_OFFSET] # (T, d)
for l, W in enumerate(self.layers):
# ---- attention: the only place where the tokens of one sequence meet
a = F.layer_norm(x, (self.d,), W['self_attn_layer_norm.weight'], W['self_attn_layer_norm.bias'])
q = F.linear(a, W['self_attn.q_proj.weight'], W['self_attn.q_proj.bias']).view(T, H, D)
k = F.linear(a, W['self_attn.k_proj.weight'], W['self_attn.k_proj.bias']).view(T, H, D)
v = F.linear(a, W['self_attn.v_proj.weight'], W['self_attn.v_proj.bias']).view(T, H, D)
cache.write(l, batch.slots, k, v) # store the new keys and values first
k_blocks, v_blocks = cache.blocks(l)
o = torch.empty_like(q)
for start, end, table in batch.prefills: # prompt phase: many tokens of one sequence
o[start:end] = paged_attention(q[start:end], k_blocks, v_blocks, table, batch.positions[start:end])
if len(batch.decode_idx): # generation phase: one token per sequence
o[batch.decode_idx] = paged_attention_batched(q[batch.decode_idx], k_blocks, v_blocks,
batch.decode_tables, batch.decode_lens)
x = x + F.linear(o.reshape(T, self.d), W['self_attn.out_proj.weight'], W['self_attn.out_proj.bias'])
# ---- feed-forward: each token on its own (position-wise)
f = F.layer_norm(x, (self.d,), W['final_layer_norm.weight'], W['final_layer_norm.bias'])
f = F.linear(F.relu(F.linear(f, W['fc1.weight'], W['fc1.bias'])), W['fc2.weight'], W['fc2.bias'])
x = x + f
x = F.layer_norm(x[batch.last_idx], (self.d,), *self.final_ln)
return x @ self.embed.T # (R, vocab): the output layer reuses the embeddingFollow the 14 tokens of the picture. The first line turns each token and its position into 768 numbers, so x is (14, 768). In each layer, the layer norm and the three projections run over all 14 rows at once. view(T, H, D) cuts each row into 12 heads of 64.
Then cache.write stores the 14 new keys and values at their 14 slots, and only then does attention read them. The loop over batch.prefills runs twice. First it takes A's range (0, 7) with table [0, 1], then B's range (7, 14) with table [2, 3]. Each prompt token sees only the earlier tokens of its own request; this rule is the causal mask.
In a decoding step, the tokens go through paged_attention_batched instead, one per request, all in one call. The rest of the layer again runs over the whole list. At the end, last_idx is [6, 13], because only the last token of each request needs scores. So the output has 2 rows.
Is it right? Method 2 is the library: transformers' own OPT with its own cache, which is one contiguous tensor per request. First we compare the logits at every step for one prompt. Then we serve 8 Alpaca prompts together and compare 48 greedy tokens of each with the library, which runs them one at a time. Alpaca is a public set of 52,000 instructions with answers, made to teach models to follow instructions. In the output, look for "identical":
== 4. Our OPT on the paged cache against transformers (FP32, CPU)
prompt of 9 tokens, then 5 decoding steps: max logit difference per step 2.0e-05, 6.7e-06, 4.8e-06, 4.3e-06, 5.7e-06, 3.8e-06
greedy tokens: ours ['were', 'the', 'first', 'to', 'have', 'a']; library ['were', 'the', 'first', 'to', 'have', 'a']
8 Alpaca prompts (8 to 21 tokens) served together, 48 greedy tokens each:
identical outputs 8 of 8; identical tokens 384 of 384; steps 48
first prompt: 'Give three tips for staying healthy.'
our answer: '\n\n1. Eat healthy.\n\nEat healthy. Eat healthy. Eat healthy. Eat healthy. Eat healthy.' ...The logits differ by at most , on values that are tens in size. That is rounding: we add and multiply in a different order from the library. All 384 tokens are identical, although the 8 prompts had different lengths and filled their blocks at different steps. The answer to "Give three tips for staying healthy." is poor, because OPT-125M is very small, but it is exactly the library's answer.
Parallel sampling and copy-on-write
The data classes, from sequence.py. A Sequence is one answer; num_cached counts how many of its tokens have keys and values in the cache:
@dataclass
class SamplingParams:
n: int = 1 # number of samples from one prompt (parallel sampling)
max_tokens: int = 16 # stop after this many new tokens
temperature: float = 0.0 # 0 means greedy: always take the most likely token
ignore_eos: bool = False # True: keep writing past </s> (to replay known output lengths)
seed: int = 0
class Sequence:
"""One prompt plus the tokens written so far, and how many of them have keys and values in the cache."""
def __init__(self, seq_id, token_ids, prompt_len, group):
self.seq_id = seq_id
self.token_ids = list(token_ids)
self.prompt_len = prompt_len
self.group = group
self.num_cached = 0 # tokens whose keys and values are stored in the KV cache
self.status = WAITING
self.logprobs = [] # log-probability of each written token, for the checks
@property
def output_ids(self):
return self.token_ids[self.prompt_len:]
class SequenceGroup:
"""One request. Its sequences are scheduled and preempted together (gang scheduling, §4.5)."""
def __init__(self, request_id, params, arrival):
self.request_id, self.params, self.arrival = request_id, params, arrival
self.seqs = []
self.first_step = self.finish_step = None
def unfinished(self):
return [s for s in self.seqs if s.status != FINISHED]A sequence keeps its prompt and its answer in one list, token_ids; prompt_len says where the answer starts. A request with n = 4 starts as one sequence and becomes four after its prompt step. arrival is its place in the queue.
In our code, copy-on-write is the middle branch of append_slot above. It needs only two more pieces. fork makes a new sequence that shares every block of its parent, and copy_blocks in the cache does the copies that append_slot asked for:
def fork(self, parent_id, child_id):
"""A new sequence that shares every block of its parent (parallel sampling, §4.4)."""
p = self.tables[parent_id]
for b in p.blocks:
self.allocator.share(b)
self.tables[child_id] = BlockTable(list(p.blocks), p.num_tokens) def copy_blocks(self, pairs):
"""Copy-on-write (§4.4): copy whole blocks src -> dst, in every layer, keys and values."""
if pairs:
src = torch.tensor([s for s, _ in pairs])
dst = torch.tensor([d for _, d in pairs])
self.data[:, :, dst] = self.data[:, :, src] # one batched copy, as in the fused kernel of §5.1Take a parent with table [0, 1]. fork raises the counts of blocks 0 and 1 from 1 to 2. The child gets its own list, [0, 1], a copy of the numbers only. No key or value moves.
copy_blocks takes pairs such as (1, 2): "copy block 1 into block 2". The : on the first two axes means "in every layer, keys and values". All the pairs of a step are done in one indexed copy.
The engine runs the prompt once, with one sequence. Right after that step it forks the other samples, and each one samples its own first token from the same logits:
if g.first_step is None: # first step of a request with n samples:
g.first_step = self.step_no # fork n - 1 children that share every block
for _ in range(g.params.n - 1):
child = self._new_seq(seq.token_ids, seq.prompt_len, g)
child.num_cached, child.status = seq.num_cached, RUNNING
self.bm.fork(seq.seq_id, child.seq_id)
g.seqs.append(child)
self._sample(logits[row], child)
self._sample(logits[row], seq)For , the loop runs once. It makes a child with the same tokens and forks the block table. Then child and parent each draw a token from the same logits, each with its own random generator.
We replay Figure 8 with the real model: the same 7-token prompt, block size 4, two samples drawn at random (temperature 1). In the output, follow the block lists and the reference counts from step 0 to step 2:
== 5. Parallel sampling and copy-on-write (Figure 8): 2 samples, block size 4
step 0: A1 blocks [0, 1], A2 blocks [0, 1]; ref counts {0: 2, 1: 2}; copies []
step 1: A1 blocks [0, 2], A2 blocks [0, 1]; ref counts {0: 2, 1: 1, 2: 1}; copies [(1, 2)]
step 2: A1 blocks [0, 2, 3], A2 blocks [0, 1, 4]; ref counts {0: 2, 1: 1, 2: 1, 3: 1, 4: 1}; copies []
sample A1: ': Tahitians reach WC 180\nTony Kanaan'
sample A2: " right now your dad hadn't lived in Bortles easily"
log-probability of all 24 sampled tokens, ours vs the library on the full text: max difference 6.2e-06It is Figure 8, line for line. After the prompt, both samples point at blocks 0 and 1, and both counts are 2. In step 1, A1 writes first. Block 1 is shared, so it is copied to block 2, A1 moves to block 2, and the count of block 1 drops to 1. A2 then writes into block 1 with no copy.
Block 0 stays shared to the end. In step 2 both last blocks are full, so each sample takes a fresh block of its own.
The last line checks that sharing did not damage anything. For each sample we ran the library's model once on the prompt plus all 12 written tokens. We compared its log-probability for every sampled token with the one our engine had when it sampled it. They agree to , so each sample read its own correct cache, shared blocks and copied block included.
How much memory does sharing save? We gave 16 Alpaca prompts 4 samples each, with output lengths up to 64. At every step we counted the blocks held, and the blocks the same sequences would hold with no sharing:
== 8. Parallel sampling, 4 samples per prompt: blocks held with sharing against without (16 Alpaca prompts)
63 steps; mean blocks held 107.0, without sharing 118.9; mean saving 11.2%; copy-on-write copies 42Sharing saved 11.2% of the blocks on average. The paper measured 6.1% to 9.8% for parallel sampling on Alpaca with OPT-13B (Figure 15, Part 5). It used the same formula: blocks saved over blocks without sharing. Alpaca prompts are short, so only a small part of each sequence is shared; long prompts save much more.
The run made 42 block copies. A prompt whose last block has room makes 3. The first three samples to write each make a copy; the fourth finds a count of 1 and writes in place.
Scheduling and preemption
Our scheduler, from scheduler.py. preempt is recomputation: it frees every block of the request and puts it back in the queue by arrival time. schedule picks the work of one step. The two numbered comments in schedule are its two parts:
def preempt(self, group):
"""Recomputation: free every block of the group (all or nothing), and queue it again in arrival order.
Later its prompt plus the tokens it already wrote are computed again as one longer prompt."""
for s in group.unfinished():
self.bm.free(s.seq_id)
s.num_cached, s.status = 0, WAITING
self.running.remove(group)
i = 0
while i < len(self.waiting) and self.waiting[i].arrival < group.arrival:
i += 1
self.waiting.insert(i, group) # it arrived early, so it goes near the front
self.num_preemptions += 1
def schedule(self):
"""Pick the work of one iteration. Running requests first (oldest first), then new ones (FCFS)."""
out = SchedulerOutput()
# 1. Each running sequence needs a slot for the token it feeds now. When the blocks run out,
# preempt the request that arrived last, until the older ones fit.
self.running.sort(key=lambda g: g.arrival)
queue = list(self.running)
while queue:
g = queue.pop(0)
seq_ids = [s.seq_id for s in g.unfinished()]
while not self.bm.can_append(seq_ids):
victim = queue.pop() if queue else g
self.preempt(victim)
out.preempted.append(victim)
if victim is g:
break
else:
out.decode += [(s, self.bm.append_slot(s.seq_id)) for s in g.unfinished()]
# 2. Admit waiting requests in arrival order while their tokens fit. Not in a step that preempted.
budget = self.max_prefill_tokens
num_seqs = sum(len(g.unfinished()) for g in self.running)
while self.waiting and not out.preempted:
g = self.waiting[0]
lengths = [len(s.token_ids) for s in g.unfinished()]
if not g.first_step and g.params.n > 1: # samples not forked yet: count them for a non-sharing manager
lengths += lengths[:1] * (g.params.n - 1)
if (num_seqs + len(lengths) > self.max_num_seqs or sum(lengths) > budget
or not self.bm.can_allocate(lengths)):
break
self.waiting.popleft()
budget -= sum(len(s.token_ids) for s in g.unfinished())
num_seqs += len(lengths)
for s in g.unfinished():
out.prefill.append((s, self.bm.allocate(s.seq_id, len(s.token_ids))))
s.status = RUNNING
self.running.append(g)
out.copies, self.bm.copies = self.bm.copies, []
return outThe schedule runs every step: this is iteration-level scheduling, as in Part 2. Take three running requests, R0, R1 and R2, in arrival order, and one free block. R0 and R1 each need a new block for their next token.
Part 1 of schedule takes R0 first, and append_slot gives it the free block. Then R1 asks, and no block is left. The while loop preempts the last request in the queue, R2. Its blocks return to the free list, and R1 now fits.
Part 2 admits waiting requests in arrival order while their blocks fit, and stops at the first one that does not. It admits nothing in a step that preempted. max_num_seqs and budget cap a step at 256 sequences and 4,096 prompt tokens.
A recomputed request needs no special code. Its token_ids hold its prompt plus the tokens it wrote. So allocate treats them as one longer prompt, and the next step rebuilds the whole cache in one pass.
Now we squeeze the memory. Six Alpaca requests must each write 64 greedy tokens. The cache has 12 blocks of 16, which is 192 slots, while the six requests need about 460 slots at the end. Then we compare all outputs with the library, which never preempts. In the output, watch which request is preempted (always the newest running one), and the line that says "identical":
== 6. Scheduling and preemption by recomputation: 6 requests, 64 greedy tokens each, a cache of 12 blocks of 16
step 10: preempt request 5 (it has 10 new tokens); free blocks now 1
step 24: preempt request 4 (it has 24 new tokens); free blocks now 2
step 26: preempt request 3 (it has 26 new tokens); free blocks now 2
step 42: preempt request 2 (it has 42 new tokens); free blocks now 3
step 64: request 2 back: recompute 49 tokens (7 prompt + 42 written) in one pass
step 64: request 3 back: recompute 34 tokens (8 prompt + 26 written) in one pass
step 64: request 4 back: recompute 40 tokens (16 prompt + 24 written) in one pass
step 64: request 5 back: recompute 18 tokens (8 prompt + 10 written) in one pass
step 73: preempt request 5 (it has 19 new tokens); free blocks now 1
step 80: preempt request 4 (it has 40 new tokens); free blocks now 3
... 4 more events
prompts [9, 24, 7, 8, 16, 8] tokens; 138 steps; 7 preemptions
outputs identical to the library (which never preempts): 6 of 6
the cache of 128 tokens: one pass 54 ms; a 16-token prompt then 112 tokens one by one 1490 ms (28x longer)All six requests start at step 0. As their answers grow, the cache fills, and at step 10 request 5, the last to arrive, is preempted with 10 tokens written. Requests 4, 3 and 2 follow at steps 24, 26 and 42. Each time the newest running request gives way.
At step 63, requests 0 and 1 write their 64th token and free their blocks. In the next step, the four waiting requests come back. Each one rebuilds its whole cache in one pass: request 2 recomputes 49 tokens, its 7-token prompt plus the 42 tokens it had written. The memory is still too small for all four to finish together, so requests 5 and 4 are preempted again later. In total there are 7 preemptions, and the work takes 138 steps instead of 64.
The line that matters is the last but one: all six outputs are identical to the library's, which never preempts. Throwing away a cache and computing it again changes nothing in the result; it only costs time.
And that time is small. The last line compares the two ways to build the cache of 128 tokens. Computing it in one pass took 54 ms. Writing it token by token took 1,490 ms, 28 times longer.
We did not build swapping. On our laptop, an Apple M-series machine, the CPU and the GPU share one memory, so there is nothing to swap to. Part 4 explains swapping and Part 5 compares the two methods.
One engine step, all pieces together
Here is the whole step, from engine.py. You have met every call in it. Read it once from top to bottom, then compare it with the picture below:
def step(self):
out = self.scheduler.schedule()
self.cache.copy_blocks(out.copies) # copy-on-write copies, before anyone writes
if not out.prefill and not out.decode:
if self.scheduler.has_work():
raise RuntimeError('a request does not fit in the KV cache even when it runs alone')
return out
batch, order = self._batch(out)
logits = self.model.forward(batch, self.cache) # (sequences, vocab)
self.last_logits = {seq.seq_id: logits[row] for row, seq in enumerate(order)} # kept for the checks
for row, seq in enumerate(order):
seq.num_cached = len(seq.token_ids)
g = seq.group
if g.first_step is None: # first step of a request with n samples:
g.first_step = self.step_no # fork n - 1 children that share every block
for _ in range(g.params.n - 1):
child = self._new_seq(seq.token_ids, seq.prompt_len, g)
child.num_cached, child.status = seq.num_cached, RUNNING
self.bm.fork(seq.seq_id, child.seq_id)
g.seqs.append(child)
self._sample(logits[row], child)
self._sample(logits[row], seq)
for g in list(self.scheduler.running):
if not g.unfinished():
g.finish_step = self.step_no
self.scheduler.running.remove(g)
self.stats.append(dict(step=self.step_no, prefill_tokens=sum(len(s.token_ids) - 1 for s, _ in out.prefill),
decode=len(out.decode), running=sum(len(g.unfinished()) for g in self.scheduler.running),
blocks_held=self.bm.blocks_held(), blocks_no_sharing=self.bm.blocks_without_sharing(),
tokens=self.bm.tokens_stored(), preempted=len(out.preempted), copies=len(out.copies)))
self.step_no += 1
return outThe picture is decoding step 1 of the run with requests A and B. First, schedule returns the plan: A's next token goes to slot 7 and B's to slot 15. Second, any copies are made, before any write. If no request fits even alone, the engine stops with an error.
Third, _batch joins the 2 tokens into one Batch, and forward returns 2 rows of logits. Fourth, _sample picks each next token; a new request with several samples forks here. Last, finished requests leave the running list. Their blocks were freed already, inside _sample. The stats line records the numbers for our charts.
The method run repeats step until no request is left. That is the whole engine.
Fork, append, free, and the kernels
Serving real requests
Now the whole engine against the baseline of §3.1. We take 64 Alpaca instructions as prompts. Each request writes as many tokens as the dataset's own answer has, capped at 128. It ignores the end token, so both runs do exactly the same work. The paper builds its workloads from dataset lengths in the same way.
Both runs use the same code and the same KV cache of 128 blocks of 16, which is 2,048 slots. Only the block manager differs. The paged run uses BlockManager. The contiguous run uses ContiguousManager. It books one chunk of 512 slots for each request when it starts, like the systems of §3.1 with a maximum length of 512. (The real OPT maximum is 2,048; we are kind to the baseline.)
ContiguousManager answers the same questions as BlockManager, so the engine can use either. Its allocate shows the difference:
def allocate(self, seq_id, num_tokens):
start = self._find_chunks(1)[0]
self.used[start:start + self.chunk] = [True] * self.chunk
t = BlockTable(list(range(start, start + self.chunk)), num_tokens)
self.tables[seq_id] = t
return [t.slot(p, self.block_size) for p in range(num_tokens)]self.chunk is blocks. _find_chunks looks for 32 free blocks in a row and returns where the run starts. The request gets all 32 at once, whatever it will need, and its table is simply 32 consecutive numbers. A request that writes 20 tokens still holds 512 slots until it finishes.
The picture shows what this means for the cache, after the first step of each run:
With chunks, 4 requests fill all 2,048 slots, but only 81 slots hold a token. With blocks, 63 requests run at once, 1,324 slots hold a token, and 272 slots are still free.
The table below has one row per run. Look first at "mean batch", then at "steps", then at "tokens/s":
== 7. Serving 64 Alpaca requests: KV cache of 128 blocks x 16 = 2048 token slots
prompts: mean 21.2 tokens; outputs: the length of the dataset answer, at most 128, mean 30.0; 1917 tokens to write
seconds tokens/s requests/s steps mean batch max batch slots holding a token preemptions
contiguous 25.2 76 2.54 494 3.8 4 10.2% 0
paged 7.4 259 8.64 128 14.5 63 87.3% 0
runs (seconds): contiguous 25.9, 25.2; paged 7.4, 7.4
paged / contiguous: throughput x3.4, mean batch x3.9
the KV cache is 151 MB in both runs (72 KB per token in FP32); booking 512 slots each, the paged mean batch would need 546 MBThe paged engine finished the same 1,917 tokens 3.4 times faster: 259 tokens per second against 76. The reason is in the batch column. With 512 slots booked per request, the 2,048-slot cache holds only 4 requests. So the contiguous run worked through the queue 4 at a time, in 494 steps. The paged run gave each request only the blocks it filled. It started 63 requests in the first step and finished in 128 steps, the length of the longest answer.
Each paged step did more work, but it did not take 3.9 times longer. Part 2 showed why: a weight matrix takes almost the same time for 1 token as for 64. More requests per step from the same memory means more throughput.
The memory column says where the gain comes from. In the contiguous run, only 10.2% of the booked slots held a token, on average over the steps. The rest was reserved or never used, the waste of Figure 3.
In the paged run, 87.3% held a token. The rest is the empty end of last blocks, at most 15 slots per sequence. The paper reports 20.4% to 38.2% of real token states for its baselines and 96.3% for vLLM (Figure 2, Part 1). Our requests are much shorter than ShareGPT conversations, so one partial block per request weighs more.
Seen the other way around, take the paged run's mean batch of 14.5 requests. With 512 slots booked each, the contiguous engine would need 546 MB of KV cache for it, instead of 151 MB. The timings are noisy, because the laptop was busy with other work. The step counts and the memory shares do not depend on the timing at all.
What this code does not show
Our engine runs one small model in FP32 on a laptop CPU; the paper serves OPT-13B to OPT-175B in FP16 on A100 GPUs. The checks against the library are measured, not estimated. The timings are the fastest of two runs on a busy laptop, so treat the ratios as shapes, not server numbers.
We left out swapping, beam search, shared prefixes, many GPUs, the HTTP front end and the CUDA kernels. Our requests all arrive at time 0, while the paper sends them at a random rate and measures latency per token.
Run it yourself
The package is code/papers/vllm/minivllm, and the script that runs every check on this page is code/papers/vllm/vllm_part6.py. Every number is saved in results/part6.json. On an Apple M-series laptop the script takes about five minutes, most of it in the contiguous serving run.
pip install torch transformers datasets
cd code/papers/vllm
python vllm_part6.py # downloads facebook/opt-125m (about 250 MB) and tatsu-lab/alpacaTo use the engine on your own prompts:
import torch
from transformers import AutoTokenizer, AutoModelForCausalLM
from minivllm import LLMEngine, SamplingParams
tok = AutoTokenizer.from_pretrained('facebook/opt-125m')
hf = AutoModelForCausalLM.from_pretrained('facebook/opt-125m', dtype=torch.float32)
engine = LLMEngine(hf, num_blocks=128, block_size=16)
for p in ['The capital of France is', 'Write a poem about the sea.']:
engine.add_request(tok(p).input_ids, SamplingParams(n=2, max_tokens=30, temperature=0.8))
engine.run()
for g in engine.groups:
for s in g.seqs:
print(tok.decode(s.output_ids))
The paper and the code
vLLM on arXiv · vLLM on GitHub · our minivllm package and scripts