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:

Figure 4 of the paper, with the file of minivllm that builds each boxengine.py: the loop that drives every step (LLMEngine)Requestssequence.pyadd_request()prompt + settingsSchedulerscheduler.pyKV cache managerblock_manager.pyBlock tablesBlockTableGPU block allocatorBlockAllocatorCPU block allocatornot built (no swapping)Worker 0Cache enginekv_cache.pyModel shardmodel.pyattention.pyWorkers 1 to N-1not built: one process,one device, no all-reduceslotslogitsbuilt in minivllmin the paper, not built here
Figure 4 redrawn as a map of our package. Requests enter on the left. The scheduler holds the KV cache manager, with its block tables and its GPU block allocator. Worker 0 holds the cache engine and the model. engine.py is the loop that drives all of them. 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:

plain text
== 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)
FileBox of Figure 4What it holdsPaper
sequence.pyRequestsRequests, their samples and the sampling settings§4.4, §4.5
scheduler.pySchedulerFirst come, first served; preemption by recomputation§4.5
block_manager.pyKV cache managerFree list, reference counts, block tables, copy-on-write§4.2 to §4.4
kv_cache.pyCache engineOne big tensor cut into blocks; the block copy§4.2, §5.1
model.pyModel shardOPT written out by hand, reading its keys and values through block tables§4.3
attention.pyModel shardPagedAttention: Eq. 4, and the fast versions the engine uses§4.1
engine.pythe arrowsThe 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.

One step, in time order: which file calls which (read from top to bottom)engine.pyscheduler.pyblock_manager.pymodel.pyattention.pykv_cache.py1. schedule()2. allocate / append3. slots, copies4. SchedulerOutput5. copy_blocks(copies): copy-on-write first6. forward(Batch)7. write(slots, k, v)8. paged_attention9. read blocks10. logits, one row per sequence11. fork() and free()steps 7 to 9 repeat in each of the 12 layers
One step of the engine as a sequence diagram. Time runs down. The engine asks the scheduler for work, the scheduler asks the block manager for slots, and the engine runs the model, which writes to the cache and reads blocks through PagedAttention. The logits go back to the engine, which samples, forks and frees.

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:

python
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] = v

Read 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 2×12×768×4=73,7282 \times 12 \times 768 \times 4 = 73{,}728 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 1\mathbf{1} in the bottom is a vector of ones; it adds up the BB numbers of block tt.)

Aij=exp⁡(qi⊤Kj/d)∑t=1⌈i/B⌉exp⁡(qi⊤Kt1/d),oi=∑j=1⌈i/B⌉VjAij⊤A_{ij} = \frac{\exp\left(q_i^\top K_j / \sqrt{d}\right)}{\sum_{t=1}^{\lceil i/B \rceil} \exp\left(q_i^\top K_t \mathbf{1} / \sqrt{d}\right)}, \qquad o_i = \sum_{j=1}^{\lceil i/B \rceil} V_j A_{ij}^\top

Read it from left to right. qiq_i is the query of token ii. KjK_j holds the BB keys of block jj, so qi⊤Kjq_i^\top K_j is a row of BB scores, one per token of the block. Dividing by d\sqrt{d} keeps the scores in a good range.

⌈i/B⌉\lceil i/B \rceil is the number of blocks that hold tokens 1 to ii ("ceil" rounds up). The bottom adds the exponentials of all scores in all those blocks. So AijA_{ij} is the row of BB weights for block jj. Last, VjAij⊤V_j A_{ij}^\top mixes the BB values of block jj with those weights, and oio_i adds the blocks together.

A tiny example you can check by hand. Take B=2B = 2 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 (1+1)+2=4(1 + 1) + 2 = 4.

So Ai1=(0.25,0.25)A_{i1} = (0.25, 0.25) and Ai2=(0.5)A_{i2} = (0.5). With values 4, 8 and 2, the output is 4⋅0.25+8⋅0.25+2⋅0.5=44 \cdot 0.25 + 8 \cdot 0.25 + 2 \cdot 0.5 = 4. 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.

python
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 o

Walk through it with the test below: 10 tokens, B=4B = 4, block table [7, 1, 3]. n_blocks is ⌈10/4⌉=3\lceil 10/4 \rceil = 3. For j=0j = 0 the loop fetches physical block 7 and uses all 4 of its tokens. For j=2j = 2 it fetches block 3, and n_j is 10−8=210 - 8 = 2, 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, e89e^{89} 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:

plain text
== 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+00

All three agree to within 4.2×10−74.2 \times 10^{-7}, 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:

python
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_size

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

Where does a token live? Request B, block size 4, block table [2, 3, 5]tokenposition pp // 4, p % 4block tablephysical blockslot"was"2logical 0, place 2entry 0 = 2block 22 x 4 + 2 = 10"the"8logical 2, place 0entry 2 = 5block 55 x 4 + 0 = 20slot = physical block x block size + placeThe slot is the token's address in the cache tensor. Every layer uses the same slot.
Address translation for two tokens of request B in our run. The position, divided by the block size, gives the logical block and the place in it. The block table turns the logical block into a physical block, and the slot follows. "was" lives at slot 10, "the" at slot 20.

Take "the" at position 8. With B=4B = 4, 8 / ⁣/ 4=28 \,/\!/\, 4 = 2 and 8 mod 4=08 \bmod 4 = 0, so it is place 0 of logical block 2. Entry 2 of the table [2, 3, 5] is 5. So its slot is 5×4+0=205 \times 4 + 0 = 20. 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:

python
    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 slot

cdiv is division that rounds up: 7 tokens need ⌈7/4⌉=2\lceil 7/4 \rceil = 2 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 7 mod 4=37 \bmod 4 = 3, 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, 8 mod 4=08 \bmod 4 = 0: 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:

plain text
== 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 9
Our run: two requests, block size 4, 9 physical blocks (after decoding step 2)physical KV blocksblock 0</s>Fourscoreandblock 1sevenyearsago,block 2</s>Itwastheblock 3bestoftimes,block 4theblock 5theblock 6block 7block 8request A: logical blocks</s>Fourscoreand0-> 0sevenyearsago,1-> 1the2-> 4request B: logical blocks</s>Itwasthe0-> 2bestoftimes,1-> 3the2-> 5
Our run after decoding step 2. Each request has three logical blocks in order. Their physical blocks interleave: request A owns blocks 0, 1 and 4, request B owns 2, 3 and 5. Blocks 6 to 8 are still free.

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

The prompt step: two prompts joined into one list of 14 tokenstokenpositionslot</s>00Four11score22and33seven44years55ago66</s>08It19was210the311best412of513times614request A: prefill (0, 7), block table [0, 1]its logits come from token 6 onlyrequest B: prefill (7, 14), block table [2, 3]its logits come from token 13 onlyLayer norms, projections and the feed-forward run once over all 14 tokens. Only attention keeps A and B apart.
The input of our prompt step. The 7 tokens of A and the 7 tokens of B form one list of 14. Each token carries its position in its own request and its slot in the cache. A prefill range and a block table tell attention which tokens belong together.

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:

python
    @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 embedding

Follow 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":

plain text
== 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 2×10−52 \times 10^{-5}, 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:

python
@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:

python
    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)
python
    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.1

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

python
            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 n=2n = 2, 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:

plain text
== 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-06
Parallel sampling in our run: two samples, one prompt (block size 4)after the prompt stepsample A1</s>Fourscoreandblock 0, ref 2sevenyearsagoblock 1, ref 2sample A2</s>Fourscoreandblock 0, ref 2sevenyearsagoblock 1, ref 2no copy yet: both samples point at the same 2 blocksafter decoding step 1sample A1</s>Fourscoreandblock 0, ref 2sevenyearsago:block 2, ref 1sample A2</s>Fourscoreandblock 0, ref 2sevenyearsagorightblock 1, ref 1copy-on-write: block 1 copied to block 2
Our run of Figure 8. Left: after the prompt step both samples point at blocks 0 and 1, each with a reference count of 2. Right: after the first decoding step, A1 has a copy of block 1 in block 2, and A2 still writes into block 1.

It 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 6.2×10−66.2 \times 10^{-6}, 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:

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

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

python
    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 out

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

plain text
== 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)
Six requests, a cache of 12 blocks: who runs at each steprunningwaiting after a preemptionrequest 0request 1request 2request 3request 4request 50255075100125step
Our preemption run. Each row is a request and each column a step. Filled cells: the request runs. Hatched cells: it waits after a preemption, until enough blocks are free to recompute its cache in one pass.

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:

python
    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 out
One engine step with real values: decoding step 1 of requests A and B (block size 4)1. schedulescheduler.py, block_manager.pyA and B are running; each needs one slot for the token it feeds.A: last block 1 has 1 free place -> slot 7. B: block 3 -> slot 15.No block taken, no copy, no preemption.2. build the batchengine.pytokens [",", ","], positions [7, 7], slots [7, 15]block tables [0, 1] and [2, 3], context lengths [8, 8]3. run the modelmodel.py, attention.py, kv_cache.pyIn each of 12 layers: write the 2 new keys and values at slots 7 and 15,then A attends over blocks [0, 1] (8 tokens) and B over blocks [2, 3].Out: logits, 2 rows of 50,272 scores.4. sampleengine.pyGreedy: the largest score of each row. A writes "the", B writes "the".5. tidy upengine.py, block_manager.pyNobody finished, so nothing is freed. Both last blocks are now full,so in the next step append_slot takes a new block for each request.
Decoding step 1 of our two-request run, stage by stage. The scheduler finds one free place in each last block. The batch has 2 tokens. The model writes their keys and values and reads blocks through the tables. Greedy sampling picks "the" for both. Nothing finishes, so nothing is freed.

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

python
    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 512/16=32512 / 16 = 32 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:

The same cache of 2,048 slots after the first step of the serving runone chunk eachbefore vLLM (512 slots booked)4 requests running; 81 slots hold a token; 1,967 booked but empty; 0 freepagedwith vLLM (blocks of 16)63 requests running; 1,324 slots hold a token; 452 booked but empty; 272 freeholds a tokenbooked, emptyfree
The same 2,048-slot cache after the first step. With one 512-slot chunk per request, 4 requests fill the whole cache, and almost all of it is booked but empty. With blocks of 16, 63 requests run, most booked slots hold a token, and some blocks are still free.

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

plain text
== 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 MB
Sequences in the batch at each step (64 Alpaca requests, same 2,048-slot cache)014284256700100200300400steppaged: mean 14.5, done after 128 stepscontiguous: mean 3.8, done after 494 steps
The number of sequences in the batch at each step of our serving run. The contiguous run never holds more than 4, because 4 chunks of 512 fill the cache. The paged run starts 63 of the 64 requests in its first step and finishes in far fewer steps.
Of the KV slots booked at each step, the share that holds a token (mean over steps)pagedpaged: 87.3%87.3%contiguouscontiguous: 10.2%10.2%Same 2,048-slot cache in both runs. The contiguous run books 512 slots per request.
Of the KV slots that each run had booked, the share that held a token, averaged over the steps.

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

bash
pip install torch transformers datasets
cd code/papers/vllm
python vllm_part6.py   # downloads facebook/opt-125m (about 250 MB) and tatsu-lab/alpaca

To use the engine on your own prompts:

python
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))
Terminal output of vllm_part6.py: the package size, the block tables of Figures 6 and 7, the Eq. 4 check, the comparison with the library, copy-on-write, preemption, the serving run and the sharing count
The output of vllm_part6.py, as it ran for this article.

The paper and the code

vLLM on arXiv · vLLM on GitHub · our minivllm package and scripts