# Sharing, Scheduling and Many GPUs

Author: Ishwar Jangid
Canonical URL: https://ishwarj.com/papers/vllm/part-4-sharing-scheduling-and-many-gpus/
Updated: 2026-10-24
Source: https://github.com/ishwar6/ishwar-books/blob/main/content/papers/vllm/part-4-sharing-scheduling-and-many-gpus.md


Part 3 cut the KV cache into small blocks that can sit anywhere in GPU memory. This part shows what that freedom buys. Several answers can share one prompt's blocks. A full GPU can push requests out and bring them back. And one model can run on many GPUs with a single memory manager.

Each piece below shows the exact lines of the paper, then explains them. We build every mechanism in Python and check it against the library.

The map below is the paper's Figure 4, redrawn. Requests come in on the left. The scheduler in the middle decides which requests run, and its KV cache manager keeps the block tables. The workers on the right are the GPUs that run the model. Part 3 explained the block tables and the GPU block allocator.

This part adds the three highlighted pieces. They are the reference counts in the block tables (§4.4), the CPU block allocator (§4.5) and the model shards on several GPUs (§4.6).

<figure class="fig"><svg viewBox="0 0 720 330" role="img" aria-label="Requests enter the scheduler. Inside it, the KV cache manager holds the block tables with reference counts, a GPU block allocator and a CPU block allocator. The scheduler sends work to workers 0 to N-1, each with a cache engine and a model shard. The block tables, the CPU block allocator and the model shards are highlighted as the subject of this part."><defs><marker id="ah" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="arrow" d="M0,0L10,5L0,10z"/></marker><marker id="ah-on" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="6" markerHeight="6" orient="auto-start-reverse"><path class="arrow-on" d="M0,0L10,5L0,10z"/></marker><marker id="ah-2" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="6" markerHeight="6" orient="auto-start-reverse"><path class="arrow-2" d="M0,0L10,5L0,10z"/></marker></defs><text class="t-title" x="20.0" y="24.0" text-anchor="start">Where this part sits in vLLM (a redraw of the paper's Figure 4)</text><rect class="box" x="20.0" y="120.0" width="110.0" height="96.0" rx="10"/><text class="t-tick t-strong" x="75.0" y="142.0" text-anchor="middle">Requests</text><rect class="box-ghost" x="34.0" y="152.0" width="82.0" height="16.0" rx="4"/><text class="t-tick" x="75.0" y="164.5" text-anchor="middle">request 1</text><rect class="box-ghost" x="34.0" y="172.0" width="82.0" height="16.0" rx="4"/><text class="t-tick" x="75.0" y="184.5" text-anchor="middle">request 2</text><rect class="box-ghost" x="34.0" y="192.0" width="82.0" height="16.0" rx="4"/><text class="t-tick" x="75.0" y="204.5" text-anchor="middle">request 3</text><line class="edge" x1="132.0" y1="168.0" x2="160.0" y2="168.0" marker-end="url(#ah)"/><rect class="box" x="162.0" y="40.0" width="290.0" height="270.0" rx="12"/><text class="t-tick t-strong" x="307.0" y="62.0" text-anchor="middle">Scheduler</text><text class="t-tick" x="307.0" y="80.0" text-anchor="middle">who runs, who waits, who is preempted (§4.5)</text><rect class="box-ghost" x="178.0" y="94.0" width="258.0" height="202.0" rx="10"/><text class="t-tick t-strong" x="307.0" y="114.0" text-anchor="middle">KV cache manager</text><rect class="box-on" x="192.0" y="126.0" width="230.0" height="40.0" rx="6"/><text class="t-tick" x="307.0" y="150.5" text-anchor="middle">Block tables, ref counts (§4.4)</text><rect class="box-1" x="192.0" y="182.0" width="230.0" height="40.0" rx="6"/><text class="t-tick" x="307.0" y="206.5" text-anchor="middle">GPU block allocator</text><rect class="box-on" x="192.0" y="238.0" width="230.0" height="40.0" rx="6"/><text class="t-tick" x="307.0" y="262.5" text-anchor="middle">CPU block allocator (§4.5)</text><line class="edge" x1="454.0" y1="168.0" x2="486.0" y2="168.0" marker-end="url(#ah)"/><rect class="box" x="488.0" y="40.0" width="214.0" height="116.0" rx="10"/><text class="t-tick t-strong" x="595.0" y="62.0" text-anchor="middle">Worker 0</text><rect class="box-1" x="502.0" y="74.0" width="186.0" height="30.0" rx="6"/><text class="t-tick" x="595.0" y="93.5" text-anchor="middle">Cache engine</text><rect class="box-on" x="502.0" y="112.0" width="186.0" height="30.0" rx="6"/><text class="t-tick" x="595.0" y="131.5" text-anchor="middle">Model shard (§4.6)</text><rect class="box" x="488.0" y="194.0" width="214.0" height="116.0" rx="10"/><text class="t-tick t-strong" x="595.0" y="216.0" text-anchor="middle">Worker N-1</text><rect class="box-1" x="502.0" y="228.0" width="186.0" height="30.0" rx="6"/><text class="t-tick" x="595.0" y="247.5" text-anchor="middle">Cache engine</text><rect class="box-on" x="502.0" y="266.0" width="186.0" height="30.0" rx="6"/><text class="t-tick" x="595.0" y="285.5" text-anchor="middle">Model shard (§4.6)</text><text class="t-tick t-strong" x="595.0" y="178.0" text-anchor="middle">. . .</text><rect class="box-on" x="20.0" y="300.0" width="12.0" height="12.0" rx="2"/><text class="t-tick" x="38.0" y="310.0" text-anchor="start">explained in this part</text></svg><figcaption>The parts of vLLM, after the paper's Figure 4. The highlighted boxes are the subject of this part: the reference counts that let block tables share blocks, the CPU block allocator that holds preempted requests, and the model shards that split one model over several GPUs.</figcaption></figure>

## Blocks and block tables, in brief

Three words carry this whole part. Here they are again, in one line each.

> [!DEFINITION] KV block
> A fixed-size piece of the KV cache. It holds the keys and values of $$B$$ tokens, for example 4 or 16. When vLLM starts, it cuts all the cache memory of a GPU into such blocks.

> [!DEFINITION] Logical and physical block
> A **logical block** is a place in one request's own list: its first block, its second block, and so on. A **physical block** is a real block in GPU memory, with a number. Logical block 1 of a request can live in physical block 26.

> [!DEFINITION] Block table
> The list that maps each logical block of a request to its physical block. The table `[370, 26]` means: logical block 0 is physical block 370, and logical block 1 is physical block 26.

Two requests whose tables hold the same number point at the same memory. That one fact makes everything in §4.4 possible.

## Many answers from one prompt {§4.4}

> [!PAPER] · §4.4 · page 6
> [![The opening of §4.4, with greedy decoding and sampling, more complex decoding scenarios and more opportunities for memory sharing highlighted](https://ishwarj.com/img/papers/vllm/p4-intro.pngs/vllm/p4-intro.png)](/img/papers/vllm/p4-intro.png)
>
> **What it says:** §4.3 covered "greedy decoding and sampling", where one prompt gives one answer. Real services must offer "more complex decoding scenarios", and these give "more opportunities for memory sharing".
>
> **What it means:**
>
> Until now, one request meant one sequence: one prompt, one answer, one block table. Many products break that rule. A code assistant shows three suggestions. A translator searches several candidate translations and keeps the best. A company puts the same long instructions in front of every user's question.
>
> In all these cases, several sequences start with the same tokens. The cache of a token depends only on the tokens before it, as Part 2 showed. So these sequences have identical caches for their common start. The question of this section is how to store that common part once.

> [!DEFINITION] Greedy decoding and sampling
> Two ways to pick the next token. **Greedy decoding** always takes the most likely token. **Sampling** draws the token at random, with the model's probabilities as weights, so the same prompt can give different answers.

### Parallel sampling {§4.4}

Start with a tiny example. A user sends the prompt "The best pizza topping is" and asks for three answers. The model samples three times and might write " mushrooms", " pineapple" and " extra cheese". This is **parallel sampling**: one prompt, several answers drawn at random, all made at the same time.

Each answer is its own sequence: the same prompt tokens, then its own new tokens. All three need the keys and values of the prompt tokens at every step. A system that gives each sequence its own contiguous cache stores the keys and values of the prompt three times. The keys and values are identical in all three copies, because they depend only on the prompt.

Where is this used? A code assistant shows several suggestions and lets the programmer choose. A chat service can show two answers and ask which one the user likes. Some systems draw many answers and keep the best one by some score. In all of these, the prompt is shared and the answers are not.

> [!PAPER] · §4.4 · pages 6 to 7
> [![The paragraph on parallel sampling, with multiple sampled outputs for a single input prompt highlighted](https://ishwarj.com/img/papers/vllm/p4-sampling-1.pngm/p4-sampling-1.png)](/img/papers/vllm/p4-sampling-1.png)
> [![Its continuation on page 7, with a request generates multiple sequences and the KV cache of the prompt to be shared highlighted](https://ishwarj.com/img/papers/vllm/p4-sampling-2.pngm/p4-sampling-2.png)](/img/papers/vllm/p4-sampling-2.png)
>
> **What it says:** in program assistants, a model makes "multiple sampled outputs for a single input prompt", and the user picks one. From here on, the paper assumes that "a request generates multiple sequences". With paged memory, this lets "the KV cache of the prompt to be shared".
>
> **What it means:**
>
> Note the change of words. A **request** is now what the user sent. A **sequence** is one prompt-plus-answer inside it. One request can hold four sequences, all with the same prompt and four different answers.
>
> The prompt is computed once, in the prompt phase, so its keys and values exist once. The question is whether the system copies them four times or lets four sequences point at one copy.

> [!PAPER] · Figure 8 · page 7
> [![Figure 8 of the paper (left of the crop): samples A1 and A2 each have logical blocks 0 and 1. Both map logical block 0 to physical block 7, holding Four score and seven. A1's logical block 1 points to a new physical block 3, a copy-on-write copy holding years ago our fathers; A2's points to physical block 1, holding years ago our mothers. A label says Ref count 2 to 1](https://ishwarj.com/img/papers/vllm/p4-figure8.pngvllm/p4-figure8.png)](/img/papers/vllm/p4-figure8.png)
>
> **What it says:** "Parallel sampling example." Two samples, A1 and A2, share the prompt "Four score and seven years ago our". A1 writes "fathers" and A2 writes "mothers". A red arrow marks "Copy-on-write", and a label says "Ref count: 2 → 1".
>
> **What it means:**
>
> Read the middle column first. It is GPU memory, nine physical blocks of four slots. The prompt sits in physical block 7 ("Four score and seven") and physical block 1 ("years ago our" plus one free slot). On both sides, each sample has its own block table with two logical blocks. Both tables point at blocks 7 and 1.
>
> Then the samples write their first new token. A2 writes "mothers" into the free slot of block 1. A1 cannot, because block 1 is shared. So block 1 is first copied to block 3, and A1 writes "fathers" there. After the copy, block 1 has one owner left, so its count drops from 2 to 1.

> [!NOTE] Where this idea comes from: fork() in Unix
> The two tools of the next boxes, reference counts and copy-on-write, are older than GPUs. They come from operating systems. Since the first versions of Unix, around 1970, a running program can call `fork()`. The call makes a second program, the child, that starts as an exact copy of the first, the parent.
>
> The early systems really copied all the parent's memory at every fork. That was slow and mostly wasted, because a child often replaces itself with another program at once. Later Unix systems stopped copying. Parent and child get page tables that point at the same physical pages, and each page counts how many page tables point at it.
>
> The pages are marked read-only. When either program writes to one, the processor stops it, and the operating system copies that one page and lets the write go on. Pages that nobody writes stay shared forever. vLLM does exactly this, with blocks of tokens in the place of pages of bytes. The paper says so itself: "similar to the copy-on-write technique in OS virtual memory (e.g., when forking a process)".

> [!PAPER] · §4.4 · page 7
> [![The paragraph that explains Figure 8, with reserve space for one copy, mapped to the same physical blocks, reference count and are both 2 highlighted](https://ishwarj.com/img/papers/vllm/p4-refcount.pngllm/p4-refcount.png)](/img/papers/vllm/p4-refcount.png)
>
> **What it says:** both outputs share the prompt, so vLLM will "reserve space for one copy" of it. The logical blocks of both sequences are "mapped to the same physical blocks". Each physical block gets a "reference count"; for blocks 7 and 1 the counts "are both 2".
>
> **What it means:**
>
> A reference count is a tally on each physical block: how many block tables point here right now. It answers one question. Is anyone else using this block?
>
> The count makes two things safe. A block goes back to the free list only when its count reaches 0, so nobody loses data that another sequence still reads. And a sequence may write into a block only when the count is 1, so nobody changes data that another sequence still reads.

> [!DEFINITION] Reference count
> A number kept for each shared object: how many users point at it. Each new user adds 1; each user that leaves takes 1 away. At 0 the object can be thrown away. Operating systems use it for shared memory pages and open files.

> [!PAPER] · §4.4 · page 7
> [![The rest of the paragraph, with copy-on-write mechanism at the block granularity, is greater than 1, allocates a new physical block, decreases the reference count to 1 and directly writes highlighted](https://ishwarj.com/img/papers/vllm/p4-cow.pngers/vllm/p4-cow.png)](/img/papers/vllm/p4-cow.png)
>
> **What it says:** vLLM uses a "copy-on-write mechanism at the block granularity". When A1 wants to write into physical block 1, its count "is greater than 1", so vLLM "allocates a new physical block" (block 3), copies block 1 into it and "decreases the reference count to 1". When A2 then writes to block 1, the count is already 1, so A2 "directly writes" there.
>
> **What it means:**
>
> Think of two students who share one printed worksheet. While they only read it, one copy is enough. The moment one of them wants to write an answer, that student photocopies the page and writes on the copy. The other keeps the original. Only the page with the writing is copied, not the whole workbook.
>
> Here the "page" is one block of four tokens. Copy-on-write costs one block copy per sample, at the moment the samples split. The blocks that are full stay shared for the whole life of the request, because nobody ever writes into a full block again.

> [!DEFINITION] Copy-on-write
> Share data until someone writes to it; copy only the piece that is written, and only at that moment. The [Background page](https://ishwarj.com/papers/vllm/background-the-kv-cache-and-paging/) shows how an operating system does this when a program forks.

The picture shows the whole of Figure 8 as two moments. Follow the reference count on each block. In the first moment, both block tables say "logical 0 is block 7, logical 1 is block 1", so both blocks have a count of 2. In the second moment, A1 has written "fathers". Its table now says "logical 1 is block 3", a fresh copy, and the count of block 1 has fallen to 1.

<figure class="fig"><svg viewBox="0 0 720 330" role="img" aria-label="Left: block tables of A1 and A2 both map to physical blocks 7 and 1, each with reference count 2. Right: after A1 writes, A1 maps to blocks 7 and 3, a new copy; block 1 has reference count 1 and holds mothers, block 3 holds fathers; block 7 is still shared with count 2."><defs><marker id="ah" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="arrow" d="M0,0L10,5L0,10z"/></marker><marker id="ah-on" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="6" markerHeight="6" orient="auto-start-reverse"><path class="arrow-on" d="M0,0L10,5L0,10z"/></marker><marker id="ah-2" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="6" markerHeight="6" orient="auto-start-reverse"><path class="arrow-2" d="M0,0L10,5L0,10z"/></marker></defs><text class="t-title" x="20.0" y="24.0" text-anchor="start">Copy-on-write in the paper's Figure 8, block size 4</text><text class="t-tick t-strong" x="10.0" y="56.0" text-anchor="start">1. after the prompt: both samples share</text><text class="t-tick" x="10.0" y="82.0" text-anchor="start">block tables</text><text class="t-tick" x="170.0" y="82.0" text-anchor="start">physical blocks (GPU memory)</text><rect class="box-1" x="170.0" y="94.0" width="170.0" height="52.0" rx="6"/><text class="t-tick t-strong" x="180.0" y="114.0" text-anchor="start">block 7   ref count 2</text><text class="t-tick" x="180.0" y="134.0" text-anchor="start">Four score and seven</text><rect class="box-1" x="170.0" y="158.0" width="170.0" height="52.0" rx="6"/><text class="t-tick t-strong" x="180.0" y="178.0" text-anchor="start">block 1   ref count 2</text><text class="t-tick" x="180.0" y="198.0" text-anchor="start">years ago our  _</text><text class="t-tick t-strong" x="10.0" y="120.0" text-anchor="start">A1</text><rect class="box" x="40.0" y="100.0" width="80.0" height="28.0" rx="6"/><text class="t-tick" x="80.0" y="118.5" text-anchor="middle">0 → 7</text><line class="edge-dim" x1="120" y1="114" x2="168" y2="120"/><rect class="box" x="40.0" y="134.0" width="80.0" height="28.0" rx="6"/><text class="t-tick" x="80.0" y="152.5" text-anchor="middle">1 → 1</text><line class="edge-dim" x1="120" y1="148" x2="168" y2="184"/><text class="t-tick t-strong" x="10.0" y="210.0" text-anchor="start">A2</text><rect class="box" x="40.0" y="190.0" width="80.0" height="28.0" rx="6"/><text class="t-tick" x="80.0" y="208.5" text-anchor="middle">0 → 7</text><line class="edge-dim" x1="120" y1="204" x2="168" y2="120"/><rect class="box" x="40.0" y="224.0" width="80.0" height="28.0" rx="6"/><text class="t-tick" x="80.0" y="242.5" text-anchor="middle">1 → 1</text><line class="edge-dim" x1="120" y1="238" x2="168" y2="184"/><text class="t-tick t-strong" x="380.0" y="56.0" text-anchor="start">2. A1 writes "fathers" into a copy</text><text class="t-tick" x="380.0" y="82.0" text-anchor="start">block tables</text><text class="t-tick" x="540.0" y="82.0" text-anchor="start">physical blocks (GPU memory)</text><rect class="box-1" x="540.0" y="94.0" width="170.0" height="52.0" rx="6"/><text class="t-tick t-strong" x="550.0" y="114.0" text-anchor="start">block 7   ref count 2</text><text class="t-tick" x="550.0" y="134.0" text-anchor="start">Four score and seven</text><rect class="box-2" x="540.0" y="158.0" width="170.0" height="52.0" rx="6"/><text class="t-tick t-strong" x="550.0" y="178.0" text-anchor="start">block 1   ref count 1</text><text class="t-tick" x="550.0" y="198.0" text-anchor="start">years ago our mothers</text><rect class="box-on" x="540.0" y="222.0" width="170.0" height="52.0" rx="6"/><text class="t-tick t-strong" x="550.0" y="242.0" text-anchor="start">block 3   ref count 1</text><text class="t-tick" x="550.0" y="262.0" text-anchor="start">years ago our fathers</text><text class="t-tick t-strong" x="380.0" y="120.0" text-anchor="start">A1</text><rect class="box" x="410.0" y="100.0" width="80.0" height="28.0" rx="6"/><text class="t-tick" x="450.0" y="118.5" text-anchor="middle">0 → 7</text><line class="edge-dim" x1="490" y1="114" x2="538" y2="120"/><rect class="box" x="410.0" y="134.0" width="80.0" height="28.0" rx="6"/><text class="t-tick" x="450.0" y="152.5" text-anchor="middle">1 → 3</text><line class="edge-dim" x1="490" y1="148" x2="538" y2="248"/><text class="t-tick t-strong" x="380.0" y="210.0" text-anchor="start">A2</text><rect class="box" x="410.0" y="190.0" width="80.0" height="28.0" rx="6"/><text class="t-tick" x="450.0" y="208.5" text-anchor="middle">0 → 7</text><line class="edge-dim" x1="490" y1="204" x2="538" y2="120"/><rect class="box" x="410.0" y="224.0" width="80.0" height="28.0" rx="6"/><text class="t-tick" x="450.0" y="242.5" text-anchor="middle">1 → 1</text><line class="edge-dim" x1="490" y1="238" x2="538" y2="184"/><line class="path" x1="352.0" y1="170.0" x2="366.0" y2="170.0" marker-end="url(#ah-on)"/><text class="t-tick" x="20.0" y="312.0" text-anchor="start">A1 got a copy (block 3) and block 1 fell from 2 to 1; A2 then writes "mothers" into block 1 with no copy.</text></svg><figcaption>Copy-on-write in two moments. Left: A1 and A2 map the same two physical blocks, each with a reference count of 2. Right: A1 wanted to write into the shared block 1, so it got a copy (block 3) and the count of block 1 fell to 1. A2 then writes into block 1 directly. Block 7 is full and stays shared.</figcaption></figure>

Block 7 never changes. It is full, so no sample ever writes into it again, and it stays shared until both samples finish. Only the one block where the two answers start to differ is copied.

We build this ourselves. Our block manager keeps a pool of physical blocks, a block table and a length per sequence, and a reference count per block. It has three calls, and §5.2 of the paper will name the same three. `fork` makes a new sequence that points at its parent's blocks. `append` stores one new token, with copy-on-write inside it. `free` drops a sequence:

```python
    def fork(self, parent, child):
        """fork: a new sequence that maps every block of its parent. Nothing is copied; reference counts go up."""
        self.table[child], self.length[child] = list(self.table[parent]), self.length[parent]
        for b in self.table[child]:
            self.ref[b] += 1

    def append(self, seq, kv):
        """append: store the keys and values of one new token. kv: (layers, 2, heads, head size)."""
        t, pos = self.table[seq], self.length[seq]
        if pos % self.B == 0:                               # the last block is full (or there is none): take a new one
            t.append(self._allocate())
        elif self.ref[t[-1]] > 1:                           # the last block is shared: copy-on-write
            new = self._allocate()
            self.pool[new].copy_(self.pool[t[-1]])          # copy the one block, then write into the copy
            self.ref[t[-1]] -= 1
            t[-1] = new
            self.cow_copies += 1
        self.pool[t[-1], :, :, :, pos % self.B] = kv
        self.length[seq] = pos + 1

    def free(self, seq):
        """free: drop a sequence. A block goes back to the free list when no sequence maps it any more."""
        for b in self.table.pop(seq):
            self.ref[b] -= 1
            if self.ref[b] == 0:
                self.free_blocks.append(b)
        del self.length[seq]
```

The `append` call has three cases. If the last block is full, it takes a fresh block. If the last block is shared, it copies it first. Otherwise it writes in place. The pool is a real tensor that holds the keys and values of OPT-125M, for all 12 layers.

To run the model on this cache, a helper called `extend` reads each sequence's blocks in table order. It hands them to the model as the past keys and values, and stores the new ones with `append`. Parallel sampling is then short. We run the prompt phase once, fork four samples, and drop the prompt's own sequence:

```python
    mgr = BlockManager(512, B)
    mgr.new('prompt')
    logits = extend(mgr, ['prompt'], [prompt])
    seqs = [f's{i}' for i in range(n)]
    for s in seqs:
        mgr.fork('prompt', s)
    mgr.free('prompt')
```

After that, each step draws one token per sample and calls `extend` for all four. We use the paper's prompt, "Four score and seven years ago", and a block size of 4, as in Figure 8. Method 2 is the library: `model.generate` with `num_return_sequences=4` and the same random seed. It keeps one full copy of the cache per sample. If our shared blocks or our copies were wrong, the tokens would differ.

```text
== 1. Parallel sampling (Figure 8): 4 samples share the blocks of one prompt, block size 4
prompt of 7 tokens (with the start token </s>) in 2 blocks: </s> Four score and | seven years ago
after fork: every sample maps blocks [370, 26]; reference counts {370: 4, 26: 4}
after the first new token: block tables [[370, 153], [370, 116], [370, 366], [370, 26]]; copy-on-write copies: 3
  sample 1: ', as the Los Angeles Dodgers amassed a 54-55 record, the question was: Will the Dodgers compete for the National'
  sample 2: ' this song crossed your mind...I just jokingly said (again) it had the power to be the best instrumental your'
  sample 3: ', Dave wanted the quintessential "I am her Unicorns" phase, but he had to think ahead.\nLast'
  sample 4: ", Bellus had a massive eye tear on one of Justin Matthews' passing screens. Being in the 80s, the"
Method 1 (paged, shared prompt) and Method 2 (model.generate, same seed): same 96 tokens: True
max difference of the logits against one plain pass per sample: 2.2e-05
at the end: 29 physical blocks with sharing, 32 without; copy-on-write copies in total: 3
```

<figure class="fig"><svg viewBox="0 0 720 350" role="img" aria-label="Left: four samples whose block tables all point to the same two physical blocks. Right: after the first new token, three samples got their own copy of the second block and the last one writes in place."><defs><marker id="ah" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="arrow" d="M0,0L10,5L0,10z"/></marker><marker id="ah-on" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="6" markerHeight="6" orient="auto-start-reverse"><path class="arrow-on" d="M0,0L10,5L0,10z"/></marker><marker id="ah-2" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="6" markerHeight="6" orient="auto-start-reverse"><path class="arrow-2" d="M0,0L10,5L0,10z"/></marker></defs><text class="t-title" x="20.0" y="26.0" text-anchor="start">Our Figure 8: four samples, block size 4 (OPT-125M run)</text><text class="t-tick" x="20.0" y="50.0" text-anchor="start">prompt blocks: logical 0 = "&lt;/s&gt; Four score and", logical 1 = "seven years ago" (1 free slot)</text><text class="t-tick t-strong" x="30.0" y="84.0" text-anchor="start">after fork</text><text class="t-tick" x="140.0" y="104.0" text-anchor="middle">logical 0</text><text class="t-tick" x="250.0" y="104.0" text-anchor="middle">logical 1</text><text class="t-tick" x="30.0" y="137.0" text-anchor="start">sample 1</text><rect class="box-1" x="90.0" y="116.0" width="100.0" height="32.0" rx="6"/><text class="t-tick" x="140.0" y="136.5" text-anchor="middle">block 370</text><rect class="box-1" x="200.0" y="116.0" width="100.0" height="32.0" rx="6"/><text class="t-tick" x="250.0" y="136.5" text-anchor="middle">block 26</text><text class="t-tick" x="30.0" y="179.0" text-anchor="start">sample 2</text><rect class="box-1" x="90.0" y="158.0" width="100.0" height="32.0" rx="6"/><text class="t-tick" x="140.0" y="178.5" text-anchor="middle">block 370</text><rect class="box-1" x="200.0" y="158.0" width="100.0" height="32.0" rx="6"/><text class="t-tick" x="250.0" y="178.5" text-anchor="middle">block 26</text><text class="t-tick" x="30.0" y="221.0" text-anchor="start">sample 3</text><rect class="box-1" x="90.0" y="200.0" width="100.0" height="32.0" rx="6"/><text class="t-tick" x="140.0" y="220.5" text-anchor="middle">block 370</text><rect class="box-1" x="200.0" y="200.0" width="100.0" height="32.0" rx="6"/><text class="t-tick" x="250.0" y="220.5" text-anchor="middle">block 26</text><text class="t-tick" x="30.0" y="263.0" text-anchor="start">sample 4</text><rect class="box-1" x="90.0" y="242.0" width="100.0" height="32.0" rx="6"/><text class="t-tick" x="140.0" y="262.5" text-anchor="middle">block 370</text><rect class="box-1" x="200.0" y="242.0" width="100.0" height="32.0" rx="6"/><text class="t-tick" x="250.0" y="262.5" text-anchor="middle">block 26</text><text class="t-tick t-strong" x="390.0" y="84.0" text-anchor="start">after the first new token</text><text class="t-tick" x="500.0" y="104.0" text-anchor="middle">logical 0</text><text class="t-tick" x="610.0" y="104.0" text-anchor="middle">logical 1</text><text class="t-tick" x="390.0" y="137.0" text-anchor="start">sample 1</text><rect class="box-1" x="450.0" y="116.0" width="100.0" height="32.0" rx="6"/><text class="t-tick" x="500.0" y="136.5" text-anchor="middle">block 370</text><rect class="box-on" x="560.0" y="116.0" width="100.0" height="32.0" rx="6"/><text class="t-tick" x="610.0" y="136.5" text-anchor="middle">block 153</text><text class="t-tick" x="390.0" y="179.0" text-anchor="start">sample 2</text><rect class="box-1" x="450.0" y="158.0" width="100.0" height="32.0" rx="6"/><text class="t-tick" x="500.0" y="178.5" text-anchor="middle">block 370</text><rect class="box-on" x="560.0" y="158.0" width="100.0" height="32.0" rx="6"/><text class="t-tick" x="610.0" y="178.5" text-anchor="middle">block 116</text><text class="t-tick" x="390.0" y="221.0" text-anchor="start">sample 3</text><rect class="box-1" x="450.0" y="200.0" width="100.0" height="32.0" rx="6"/><text class="t-tick" x="500.0" y="220.5" text-anchor="middle">block 370</text><rect class="box-on" x="560.0" y="200.0" width="100.0" height="32.0" rx="6"/><text class="t-tick" x="610.0" y="220.5" text-anchor="middle">block 366</text><text class="t-tick" x="390.0" y="263.0" text-anchor="start">sample 4</text><rect class="box-1" x="450.0" y="242.0" width="100.0" height="32.0" rx="6"/><text class="t-tick" x="500.0" y="262.5" text-anchor="middle">block 370</text><rect class="box-1" x="560.0" y="242.0" width="100.0" height="32.0" rx="6"/><text class="t-tick" x="610.0" y="262.5" text-anchor="middle">block 26</text><line class="edge" x1="330.0" y1="200.0" x2="380.0" y2="200.0" marker-end="url(#ah)"/><rect class="box-1" x="30.0" y="294.0" width="12.0" height="12.0" rx="2"/><text class="t-tick" x="48.0" y="304.0" text-anchor="start">shared physical block (reference count above 1 before the write)</text><rect class="box-on" x="30.0" y="314.0" width="12.0" height="12.0" rx="2"/><text class="t-tick" x="48.0" y="324.0" text-anchor="start">new block made by copy-on-write (3 copies)</text><text class="t-tick" x="30.0" y="344.0" text-anchor="start">reference counts after fork: block 370: 4, block 26: 4</text></svg><figcaption>Our own Figure 8, from the run above. Right after fork, all four block tables point at the same two physical blocks. After the first new token, three samples have their own copy of the second block, and the fourth writes into the original.</figcaption></figure>

This is Figure 8 with four samples instead of two. With the start token, the prompt has 7 tokens: 4 in physical block 370 and 3 in block 26, with one free slot. After fork, both blocks have a reference count of 4.

Then all four samples write their first token. The first three find block 26 shared, so each gets a copy: blocks 153, 116 and 366. The fourth finds a count of 1 and writes into block 26 directly. That is 3 copies in all, exactly the paper's rule. Block 370 was full, so it stays shared to the end.

The check passes. All 96 tokens are the same as the library's, and the logits match one plain pass per sample to $$2.2 \times 10^{-5}$$. (The samples are random text from a small model; only the agreement matters.)

> [!PAPER] · §4.4 · page 7
> [![The summary of parallel sampling, with with the exception of the final logical block and long input prompts highlighted](https://ishwarj.com/img/papers/vllm/p4-sampling-sum.pngp4-sampling-sum.png)](/img/papers/vllm/p4-sampling-sum.png)
>
> **What it says:** vLLM shares most of the prompt's KV cache across the samples, "with the exception of the final logical block", which copy-on-write handles. The saving is largest "especially for long input prompts".
>
> **What it means:**
>
> Only the last, partly filled block of the prompt is ever copied. Every full block of the prompt is stored once, however many samples there are. So the saving grows with the length of the prompt.
>
> Our run shows the other side. The prompt has only 7 tokens, so sharing saves just 3 blocks: 29 instead of 32 at the end. The four answers are 24 tokens each and cannot be shared. A prompt of 2,000 tokens with short answers would save almost everything.

### Beam search {§4.4}

Parallel sampling wants variety. Beam search wants the opposite: the single answer that the model finds most likely as a whole. A translator wants one good translation, not five random ones.

Greedy decoding does not give that answer. It picks the best next word and never looks back. Suppose the best first word has probability 0.5, but all its continuations are weak, at 0.2 each. A second-best first word of 0.4, followed by a word of 0.9, gives a better pair: 0.4 × 0.9 = 0.36 against 0.5 × 0.2 = 0.10. Greedy decoding never finds it, because it threw that first word away.

Beam search keeps a few candidates alive, say 4. They are called **beams**, like the beam of a torch: a narrow light that searches part of a large dark space. Each step grows every beam by one token and keeps the 4 best results. Weak beams die, and a strong beam can have several children.

> [!NOTE] Where this idea comes from
> Beam search is far older than language models. It comes from speech recognition systems of the 1970s, which had to find the most likely sentence among very many possible ones. Machine translation then used it for decades. When neural networks took over translation, beam search stayed, and today's LLM servers still offer it.

> [!PAPER] · §4.4 · pages 7 to 8
> [![The paragraph that introduces beam search, with Beam search and the most probable output sequence highlighted](https://ishwarj.com/img/papers/vllm/p4-beam-1.png/vllm/p4-beam-1.png)](/img/papers/vllm/p4-beam-1.png)
> [![Its continuation, with beam width, number of top candidates, retained at every step and is the vocabulary size highlighted](https://ishwarj.com/img/papers/vllm/p4-beam-2.png/vllm/p4-beam-2.png)](/img/papers/vllm/p4-beam-2.png)
>
> **What it says:** beam search finds "the most probable output sequence" without trying every possible answer. Its "beam width" $$k$$ is the "number of top candidates retained at every step". Each step extends every candidate by every token and keeps the top $$k$$ of the $$k \cdot |V|$$ candidates, where $$|V|$$ "is the vocabulary size".
>
> **What it means:**
>
> The example above, 0.36 against 0.10, showed why greedy decoding can miss the best answer. Trying every answer is impossible too: with 50,000 tokens, two steps already give 2.5 billion pairs.
>
> Beam search sits in between. It keeps $$k$$ partial answers, the **beams**. At each step it tries every next token on every beam and keeps the $$k$$ best results. A beam can die, and a good beam can have several children.

The score of a beam is the sum of the log-probabilities of its tokens:

$$
\text{score}(y_1, \ldots, y_t) = \sum_{i=1}^{t} \log P(y_i \mid x, y_1, \ldots, y_{i-1})
$$

Read it from left to right. The tokens $$y_1$$ to $$y_t$$ are the answer so far, and $$x$$ is the prompt. Each term is the log of the probability that the model gives token $$i$$, given the prompt and the earlier tokens. Adding logs is the same as multiplying probabilities, which is Eq. 1 from Part 2. Logs are used because a product of many small numbers gets too small for a computer.

A tiny example with $$k = 2$$ and three tokens a, b, c. The two beams are "a" with score −0.5 and "b" with score −1.0. The model gives "a" the next-token log-probabilities −0.2, −2.0 and −3.0, and "b" gives −0.1, −0.3 and −4.0. The six candidates score −0.7, −2.5, −3.5, −1.1, −1.3 and −5.0. The top two are "aa" (−0.7) and "ba" (−1.1).

Both beams survive here, each with one child. If "ab" had scored above "ba", beam "a" would have both children and beam "b" would die.

<figure class="fig"><svg viewBox="0 0 720 368" role="img" aria-label="A tree. The prompt has two beams, a with score minus 0.5 and b with minus 1.0. Each has three children. The two best of the six, aa at minus 0.7 and ba at minus 1.1, are kept; the other four are dropped."><defs><marker id="ah" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="arrow" d="M0,0L10,5L0,10z"/></marker><marker id="ah-on" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="6" markerHeight="6" orient="auto-start-reverse"><path class="arrow-on" d="M0,0L10,5L0,10z"/></marker><marker id="ah-2" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="6" markerHeight="6" orient="auto-start-reverse"><path class="arrow-2" d="M0,0L10,5L0,10z"/></marker></defs><text class="t-title" x="20.0" y="24.0" text-anchor="start">Beam search with k = 2 and a vocabulary of three tokens (a, b, c)</text><rect class="box" x="20.0" y="173.0" width="90.0" height="34.0" rx="6"/><text class="t-tick" x="65.0" y="194.5" text-anchor="middle">prompt</text><text class="t-tick t-strong" x="170.0" y="50.0" text-anchor="middle">step 1: 2 beams</text><text class="t-tick t-strong" x="420.0" y="50.0" text-anchor="middle">step 2: 6 candidates, keep the best 2</text><line class="edge" x1="110.0" y1="190.0" x2="128.0" y2="127.0" marker-end="url(#ah)"/><rect class="box-on" x="130.0" y="110.0" width="100.0" height="34.0" rx="6"/><text class="t-tick" x="180.0" y="131.5" text-anchor="middle">"a"  −0.5</text><line class="edge" x1="230" y1="127" x2="298" y2="79"/><rect class="box-on" x="300.0" y="64.0" width="240.0" height="30.0" rx="6"/><text class="t-tick" x="420.0" y="83.5" text-anchor="middle">"aa"   −0.5 −0.2 = −0.7</text><text class="t-tick t-strong" x="552.0" y="84.0" text-anchor="start">kept</text><line class="edge-dim" x1="230" y1="127" x2="298" y2="125"/><rect class="box-ghost" x="300.0" y="110.0" width="240.0" height="30.0" rx="6"/><text class="t-tick t-muted" x="420.0" y="129.5" text-anchor="middle">"ab"   −0.5 −2.0 = −2.5</text><text class="t-tick t-muted" x="552.0" y="130.0" text-anchor="start">dropped</text><line class="edge-dim" x1="230" y1="127" x2="298" y2="171"/><rect class="box-ghost" x="300.0" y="156.0" width="240.0" height="30.0" rx="6"/><text class="t-tick t-muted" x="420.0" y="175.5" text-anchor="middle">"ac"   −0.5 −3.0 = −3.5</text><text class="t-tick t-muted" x="552.0" y="176.0" text-anchor="start">dropped</text><line class="edge" x1="110.0" y1="190.0" x2="128.0" y2="253.0" marker-end="url(#ah)"/><rect class="box-on" x="130.0" y="236.0" width="100.0" height="34.0" rx="6"/><text class="t-tick" x="180.0" y="257.5" text-anchor="middle">"b"  −1.0</text><line class="edge" x1="230" y1="253" x2="298" y2="205"/><rect class="box-on" x="300.0" y="190.0" width="240.0" height="30.0" rx="6"/><text class="t-tick" x="420.0" y="209.5" text-anchor="middle">"ba"   −1.0 −0.1 = −1.1</text><text class="t-tick t-strong" x="552.0" y="210.0" text-anchor="start">kept</text><line class="edge-dim" x1="230" y1="253" x2="298" y2="251"/><rect class="box-ghost" x="300.0" y="236.0" width="240.0" height="30.0" rx="6"/><text class="t-tick t-muted" x="420.0" y="255.5" text-anchor="middle">"bb"   −1.0 −0.3 = −1.3</text><text class="t-tick t-muted" x="552.0" y="256.0" text-anchor="start">dropped</text><line class="edge-dim" x1="230" y1="253" x2="298" y2="297"/><rect class="box-ghost" x="300.0" y="282.0" width="240.0" height="30.0" rx="6"/><text class="t-tick t-muted" x="420.0" y="301.5" text-anchor="middle">"bc"   −1.0 −4.0 = −5.0</text><text class="t-tick t-muted" x="552.0" y="302.0" text-anchor="start">dropped</text><text class="t-tick" x="20.0" y="338.0" text-anchor="start">score of a beam = sum of the log-probabilities of its tokens; "ab" (−2.5) lost to "ba" (−1.1)</text><text class="t-tick" x="20.0" y="358.0" text-anchor="start">each beam keeps one child here; if "ab" had beaten "ba", beam "b" would die</text></svg><figcaption>The tiny example as a tree. Two beams, "a" and "b", each try all three tokens. Of the six candidates, only the two best scores survive: "aa" at −0.7 and "ba" at −1.1. The other four are dropped.</figcaption></figure>

Now look at the tree with memory in mind. Both survivors start with the prompt, so they share its cache. "aa" also reuses the cache of "a", its parent. In a real search, beams share long common starts and split late. That is the sharing Figure 9 shows.

> [!DEFINITION] Log-probability
> The natural logarithm of a probability. It is 0 for a certain event and more negative for a rarer one: $$\log 0.5 \approx -0.69$$, $$\log 0.01 \approx -4.6$$. Adding log-probabilities gives the log of their product.

> [!PAPER] · Figure 9 · page 7
> [![Figure 9 of the paper (right of the crop): four beam candidates as chains of blocks. All start at block 0; candidates 0 to 2 share blocks 1 and 3; candidate 3 has blocks 2, 4 and 8. Blocks 2, 4, 5 and 8 are crossed out. After a dotted line, new blocks 9 to 12 extend the survivors](https://ishwarj.com/img/papers/vllm/p4-figure9.pngvllm/p4-figure9.png)](/img/papers/vllm/p4-figure9.png)
>
> **What it says:** "Beam search example." Four beam candidates, drawn as chains of blocks, before and after one iteration (the dotted line).
>
> **What it means:**
>
> Each row is one beam, and each box is one physical block. Before the dotted line, all four beams share block 0, the prompt. Beams 0 to 2 also share blocks 1 and 3, then split into blocks 5, 6 and 7. Beam 3 left the others early and has its own blocks 2, 4 and 8.
>
> After the dotted line, all four new beams descend from old beams 1 and 2. Old beams 0 and 3 die. Their blocks 5, 2, 4 and 8 have no owner left, so they are crossed out and freed. The survivors get new blocks 9 to 12.

> [!PAPER] · §4.4 · page 7
> [![The paragraph that explains Figure 9, with sharing patterns dynamically, process tree in the OS created by compound forks, whose reference counts reach and all candidates share blocks 0, 1, 3 highlighted](https://ishwarj.com/img/papers/vllm/p4-beam-share.pngm/p4-beam-share.png)](/img/papers/vllm/p4-beam-share.png)
>
> **What it says:** in beam search the "sharing patterns dynamically" change, "similar to the process tree in the OS created by compound forks". When beams 0 and 3 drop out, vLLM frees all blocks "whose reference counts reach" 0 (blocks 2, 4, 5 and 8). Afterwards "all candidates share blocks 0, 1, 3".
>
> **What it means:**
>
> In parallel sampling the sharing is fixed: the prompt is shared and the answers never are. In beam search, which beams share which blocks changes at every step. A beam is born as a copy of its parent: a fork. It dies when it falls out of the top $$k$$: a free.
>
> The beams form a family tree, like processes that fork other processes. Reference counts do all the bookkeeping. A block lives exactly as long as some living beam still descends through it.

Our beam search uses the same three calls. At each step, every new beam is a `fork` of its parent, and then all old beams are freed. Then the new token of each beam is stored with `append`:

```python
        top = torch.topk((scores[:, None] + logp).flatten(), k)
        parents, words = (top.indices // V).tolist(), (top.indices % V).tolist()
        new = []
        for i, (p, w) in enumerate(zip(parents, words)):
            nid += 1
            c = f'b{nid}'
            mgr.fork(beams[p], c)
            toks[c] = toks[beams[p]] + [w]
            new.append(c)
            if p != i:                                      # a contiguous cache would copy the parent's whole cache
                contiguous_copy += mgr.length[beams[p]]
        for b in beams:
            mgr.free(b)
```

The first line is the score equation: the beam scores plus the log-probabilities of every next token, all $$k \cdot |V|$$ of them, then the top $$k$$. Fork comes before free, so a block that a child still needs never reaches a count of 0. Method 2 is `model.generate` with `num_beams=4`:

```text
== 2. Beam search (Figure 9): 4 beams fork, append and free blocks at every step, block size 4
  beam 1: ', I was in my early 20s.\nI was in my early 20s.\nI was in my early'
  beam 2: ', I was in my early 20s.\n\nI was in my early 20s.\n\nI was in'
  beam 3: ', I was in my early 20s.\nI was in my early 20s.\nI was in my late'
  beam 4: ', I was in my early 20s.\nI was in my early 20s.\nI was in my mid'
Method 1 (paged beam search) and Method 2 (model.generate, num_beams=4): same 96 tokens: True
final block tables: [[782, 921, 628, 975, 950, 147, 92, 201], [782, 921, 628, 975, 904, 521, 772, 907], [782, 921, 628, 975, 950, 147, 92, 201], [782, 921, 628, 975, 950, 147, 92, 201]]
blocks mapped by all 4 beams: [782, 921, 628, 975]; physical blocks in use 14, without sharing 32
copied during the search: 22 blocks by copy-on-write = 88 token slots; a contiguous cache that keeps beam i in slot i copies 1029 token slots
```

<figure class="fig"><svg viewBox="0 0 720 280" role="img" aria-label="Four rows of eight blocks. The first four blocks are the same in every row; three beams share all eight blocks; one beam has its own last four. 14 physical blocks in use instead of 32."><defs><marker id="ah" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="arrow" d="M0,0L10,5L0,10z"/></marker><marker id="ah-on" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="6" markerHeight="6" orient="auto-start-reverse"><path class="arrow-on" d="M0,0L10,5L0,10z"/></marker><marker id="ah-2" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="6" markerHeight="6" orient="auto-start-reverse"><path class="arrow-2" d="M0,0L10,5L0,10z"/></marker></defs><text class="t-title" x="20.0" y="26.0" text-anchor="start">Our Figure 9: block tables of 4 beams after 24 steps, block size 4</text><text class="t-tick" x="20.0" y="71.0" text-anchor="start">beam 1</text><rect class="box-1" x="80.0" y="50.0" width="72.0" height="32.0" rx="6"/><text class="t-tick" x="116.0" y="70.5" text-anchor="middle">782</text><rect class="box-1" x="158.0" y="50.0" width="72.0" height="32.0" rx="6"/><text class="t-tick" x="194.0" y="70.5" text-anchor="middle">921</text><rect class="box-1" x="236.0" y="50.0" width="72.0" height="32.0" rx="6"/><text class="t-tick" x="272.0" y="70.5" text-anchor="middle">628</text><rect class="box-1" x="314.0" y="50.0" width="72.0" height="32.0" rx="6"/><text class="t-tick" x="350.0" y="70.5" text-anchor="middle">975</text><rect class="box-2" x="392.0" y="50.0" width="72.0" height="32.0" rx="6"/><text class="t-tick" x="428.0" y="70.5" text-anchor="middle">950</text><rect class="box-2" x="470.0" y="50.0" width="72.0" height="32.0" rx="6"/><text class="t-tick" x="506.0" y="70.5" text-anchor="middle">147</text><rect class="box-2" x="548.0" y="50.0" width="72.0" height="32.0" rx="6"/><text class="t-tick" x="584.0" y="70.5" text-anchor="middle">92</text><rect class="box-2" x="626.0" y="50.0" width="72.0" height="32.0" rx="6"/><text class="t-tick" x="662.0" y="70.5" text-anchor="middle">201</text><text class="t-tick" x="20.0" y="113.0" text-anchor="start">beam 2</text><rect class="box-1" x="80.0" y="92.0" width="72.0" height="32.0" rx="6"/><text class="t-tick" x="116.0" y="112.5" text-anchor="middle">782</text><rect class="box-1" x="158.0" y="92.0" width="72.0" height="32.0" rx="6"/><text class="t-tick" x="194.0" y="112.5" text-anchor="middle">921</text><rect class="box-1" x="236.0" y="92.0" width="72.0" height="32.0" rx="6"/><text class="t-tick" x="272.0" y="112.5" text-anchor="middle">628</text><rect class="box-1" x="314.0" y="92.0" width="72.0" height="32.0" rx="6"/><text class="t-tick" x="350.0" y="112.5" text-anchor="middle">975</text><rect class="box-4" x="392.0" y="92.0" width="72.0" height="32.0" rx="6"/><text class="t-tick" x="428.0" y="112.5" text-anchor="middle">904</text><rect class="box-4" x="470.0" y="92.0" width="72.0" height="32.0" rx="6"/><text class="t-tick" x="506.0" y="112.5" text-anchor="middle">521</text><rect class="box-4" x="548.0" y="92.0" width="72.0" height="32.0" rx="6"/><text class="t-tick" x="584.0" y="112.5" text-anchor="middle">772</text><rect class="box-4" x="626.0" y="92.0" width="72.0" height="32.0" rx="6"/><text class="t-tick" x="662.0" y="112.5" text-anchor="middle">907</text><text class="t-tick" x="20.0" y="155.0" text-anchor="start">beam 3</text><rect class="box-1" x="80.0" y="134.0" width="72.0" height="32.0" rx="6"/><text class="t-tick" x="116.0" y="154.5" text-anchor="middle">782</text><rect class="box-1" x="158.0" y="134.0" width="72.0" height="32.0" rx="6"/><text class="t-tick" x="194.0" y="154.5" text-anchor="middle">921</text><rect class="box-1" x="236.0" y="134.0" width="72.0" height="32.0" rx="6"/><text class="t-tick" x="272.0" y="154.5" text-anchor="middle">628</text><rect class="box-1" x="314.0" y="134.0" width="72.0" height="32.0" rx="6"/><text class="t-tick" x="350.0" y="154.5" text-anchor="middle">975</text><rect class="box-2" x="392.0" y="134.0" width="72.0" height="32.0" rx="6"/><text class="t-tick" x="428.0" y="154.5" text-anchor="middle">950</text><rect class="box-2" x="470.0" y="134.0" width="72.0" height="32.0" rx="6"/><text class="t-tick" x="506.0" y="154.5" text-anchor="middle">147</text><rect class="box-2" x="548.0" y="134.0" width="72.0" height="32.0" rx="6"/><text class="t-tick" x="584.0" y="154.5" text-anchor="middle">92</text><rect class="box-2" x="626.0" y="134.0" width="72.0" height="32.0" rx="6"/><text class="t-tick" x="662.0" y="154.5" text-anchor="middle">201</text><text class="t-tick" x="20.0" y="197.0" text-anchor="start">beam 4</text><rect class="box-1" x="80.0" y="176.0" width="72.0" height="32.0" rx="6"/><text class="t-tick" x="116.0" y="196.5" text-anchor="middle">782</text><rect class="box-1" x="158.0" y="176.0" width="72.0" height="32.0" rx="6"/><text class="t-tick" x="194.0" y="196.5" text-anchor="middle">921</text><rect class="box-1" x="236.0" y="176.0" width="72.0" height="32.0" rx="6"/><text class="t-tick" x="272.0" y="196.5" text-anchor="middle">628</text><rect class="box-1" x="314.0" y="176.0" width="72.0" height="32.0" rx="6"/><text class="t-tick" x="350.0" y="196.5" text-anchor="middle">975</text><rect class="box-2" x="392.0" y="176.0" width="72.0" height="32.0" rx="6"/><text class="t-tick" x="428.0" y="196.5" text-anchor="middle">950</text><rect class="box-2" x="470.0" y="176.0" width="72.0" height="32.0" rx="6"/><text class="t-tick" x="506.0" y="196.5" text-anchor="middle">147</text><rect class="box-2" x="548.0" y="176.0" width="72.0" height="32.0" rx="6"/><text class="t-tick" x="584.0" y="196.5" text-anchor="middle">92</text><rect class="box-2" x="626.0" y="176.0" width="72.0" height="32.0" rx="6"/><text class="t-tick" x="662.0" y="196.5" text-anchor="middle">201</text><rect class="box-1" x="80.0" y="230.0" width="12.0" height="12.0" rx="2"/><text class="t-tick" x="98.0" y="240.0" text-anchor="start">mapped by all 4 beams</text><rect class="box-2" x="267.0" y="230.0" width="12.0" height="12.0" rx="2"/><text class="t-tick" x="285.0" y="240.0" text-anchor="start">by 3 beams</text><rect class="box-4" x="377.0" y="230.0" width="12.0" height="12.0" rx="2"/><text class="t-tick" x="395.0" y="240.0" text-anchor="start">by 1 beam</text><text class="t-tick" x="80.0" y="268.0" text-anchor="start">14 physical blocks hold what would need 32 without sharing</text></svg><figcaption>Our own Figure 9. The block tables of the four beams at the end. All four map the same first four blocks; beams 1, 3 and 4 map the same eight. Only beam 2 has its own last four blocks.</figcaption></figure>

All 96 tokens match the library. The block tables tell the story of Figure 9 in numbers. All four beams share their first four blocks. Beams 1, 3 and 4 share all eight. They differ only in the token just chosen ("early", "late", "mid"), and its keys and values are not stored yet. Beam 2 split off earlier, at the double line break.

So 14 physical blocks hold what four separate caches would store in 32 blocks.

<figure class="fig"><svg viewBox="0 0 720 300" role="img" aria-label="Physical blocks in use at each step. Beam search with sharing stays near 14 blocks while it would need 32 without sharing."><defs><marker id="ah" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="arrow" d="M0,0L10,5L0,10z"/></marker><marker id="ah-on" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="6" markerHeight="6" orient="auto-start-reverse"><path class="arrow-on" d="M0,0L10,5L0,10z"/></marker><marker id="ah-2" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="6" markerHeight="6" orient="auto-start-reverse"><path class="arrow-2" d="M0,0L10,5L0,10z"/></marker></defs><line class="grid" x1="64" y1="250.0" x2="530" y2="250.0"/><text class="t-tick" x="56.0" y="254.0" text-anchor="end">0</text><line class="grid" x1="64" y1="187.1" x2="530" y2="187.1"/><text class="t-tick" x="56.0" y="191.1" text-anchor="end">10</text><line class="grid" x1="64" y1="124.3" x2="530" y2="124.3"/><text class="t-tick" x="56.0" y="128.3" text-anchor="end">20</text><line class="grid" x1="64" y1="61.4" x2="530" y2="61.4"/><text class="t-tick" x="56.0" y="65.4" text-anchor="end">30</text><text class="t-tick" x="64.0" y="270.0" text-anchor="middle">1</text><text class="t-tick" x="148.7" y="270.0" text-anchor="middle">5</text><text class="t-tick" x="254.6" y="270.0" text-anchor="middle">10</text><text class="t-tick" x="360.5" y="270.0" text-anchor="middle">15</text><text class="t-tick" x="466.5" y="270.0" text-anchor="middle">20</text><text class="t-tick" x="530.0" y="270.0" text-anchor="middle">23</text><line class="axis" x1="64" y1="250" x2="530" y2="250"/><polyline class="l3" points="64.0,199.7 85.2,174.6 106.4,174.6 127.5,174.6 148.7,174.6 169.9,149.4 191.1,149.4 212.3,149.4 233.5,149.4 254.6,124.3 275.8,124.3 297.0,124.3 318.2,124.3 339.4,99.1 360.5,99.1 381.7,99.1 402.9,99.1 424.1,74.0 445.3,74.0 466.5,74.0 487.6,74.0 508.8,48.9 530.0,48.9"/><g class="mark"><title>beams, no sharing, 1: 8</title><circle class="s3 ring" cx="64.0" cy="199.7" r="5"/></g><g class="mark"><title>beams, no sharing, 2: 12</title><circle class="s3 ring" cx="85.2" cy="174.6" r="5"/></g><g class="mark"><title>beams, no sharing, 3: 12</title><circle class="s3 ring" cx="106.4" cy="174.6" r="5"/></g><g class="mark"><title>beams, no sharing, 4: 12</title><circle class="s3 ring" cx="127.5" cy="174.6" r="5"/></g><g class="mark"><title>beams, no sharing, 5: 12</title><circle class="s3 ring" cx="148.7" cy="174.6" r="5"/></g><g class="mark"><title>beams, no sharing, 6: 16</title><circle class="s3 ring" cx="169.9" cy="149.4" r="5"/></g><g class="mark"><title>beams, no sharing, 7: 16</title><circle class="s3 ring" cx="191.1" cy="149.4" r="5"/></g><g class="mark"><title>beams, no sharing, 8: 16</title><circle class="s3 ring" cx="212.3" cy="149.4" r="5"/></g><g class="mark"><title>beams, no sharing, 9: 16</title><circle class="s3 ring" cx="233.5" cy="149.4" r="5"/></g><g class="mark"><title>beams, no sharing, 10: 20</title><circle class="s3 ring" cx="254.6" cy="124.3" r="5"/></g><g class="mark"><title>beams, no sharing, 11: 20</title><circle class="s3 ring" cx="275.8" cy="124.3" r="5"/></g><g class="mark"><title>beams, no sharing, 12: 20</title><circle class="s3 ring" cx="297.0" cy="124.3" r="5"/></g><g class="mark"><title>beams, no sharing, 13: 20</title><circle class="s3 ring" cx="318.2" cy="124.3" r="5"/></g><g class="mark"><title>beams, no sharing, 14: 24</title><circle class="s3 ring" cx="339.4" cy="99.1" r="5"/></g><g class="mark"><title>beams, no sharing, 15: 24</title><circle class="s3 ring" cx="360.5" cy="99.1" r="5"/></g><g class="mark"><title>beams, no sharing, 16: 24</title><circle class="s3 ring" cx="381.7" cy="99.1" r="5"/></g><g class="mark"><title>beams, no sharing, 17: 24</title><circle class="s3 ring" cx="402.9" cy="99.1" r="5"/></g><g class="mark"><title>beams, no sharing, 18: 28</title><circle class="s3 ring" cx="424.1" cy="74.0" r="5"/></g><g class="mark"><title>beams, no sharing, 19: 28</title><circle class="s3 ring" cx="445.3" cy="74.0" r="5"/></g><g class="mark"><title>beams, no sharing, 20: 28</title><circle class="s3 ring" cx="466.5" cy="74.0" r="5"/></g><g class="mark"><title>beams, no sharing, 21: 28</title><circle class="s3 ring" cx="487.6" cy="74.0" r="5"/></g><g class="mark"><title>beams, no sharing, 22: 32</title><circle class="s3 ring" cx="508.8" cy="48.9" r="5"/></g><g class="mark"><title>beams, no sharing, 23: 32</title><circle class="s3 ring" cx="530.0" cy="48.9" r="5"/></g><polyline class="l1" points="64.0,218.6 85.2,206.0 106.4,206.0 127.5,206.0 148.7,206.0 169.9,187.1 191.1,199.7 212.3,199.7 233.5,199.7 254.6,180.9 275.8,193.4 297.0,193.4 318.2,199.7 339.4,187.1 360.5,187.1 381.7,187.1 402.9,187.1 424.1,174.6 445.3,174.6 466.5,174.6 487.6,174.6 508.8,155.7 530.0,162.0"/><g class="mark"><title>beams, shared, 1: 5</title><circle class="s1 ring" cx="64.0" cy="218.6" r="5"/></g><g class="mark"><title>beams, shared, 2: 7</title><circle class="s1 ring" cx="85.2" cy="206.0" r="5"/></g><g class="mark"><title>beams, shared, 3: 7</title><circle class="s1 ring" cx="106.4" cy="206.0" r="5"/></g><g class="mark"><title>beams, shared, 4: 7</title><circle class="s1 ring" cx="127.5" cy="206.0" r="5"/></g><g class="mark"><title>beams, shared, 5: 7</title><circle class="s1 ring" cx="148.7" cy="206.0" r="5"/></g><g class="mark"><title>beams, shared, 6: 10</title><circle class="s1 ring" cx="169.9" cy="187.1" r="5"/></g><g class="mark"><title>beams, shared, 7: 8</title><circle class="s1 ring" cx="191.1" cy="199.7" r="5"/></g><g class="mark"><title>beams, shared, 8: 8</title><circle class="s1 ring" cx="212.3" cy="199.7" r="5"/></g><g class="mark"><title>beams, shared, 9: 8</title><circle class="s1 ring" cx="233.5" cy="199.7" r="5"/></g><g class="mark"><title>beams, shared, 10: 11</title><circle class="s1 ring" cx="254.6" cy="180.9" r="5"/></g><g class="mark"><title>beams, shared, 11: 9</title><circle class="s1 ring" cx="275.8" cy="193.4" r="5"/></g><g class="mark"><title>beams, shared, 12: 9</title><circle class="s1 ring" cx="297.0" cy="193.4" r="5"/></g><g class="mark"><title>beams, shared, 13: 8</title><circle class="s1 ring" cx="318.2" cy="199.7" r="5"/></g><g class="mark"><title>beams, shared, 14: 10</title><circle class="s1 ring" cx="339.4" cy="187.1" r="5"/></g><g class="mark"><title>beams, shared, 15: 10</title><circle class="s1 ring" cx="360.5" cy="187.1" r="5"/></g><g class="mark"><title>beams, shared, 16: 10</title><circle class="s1 ring" cx="381.7" cy="187.1" r="5"/></g><g class="mark"><title>beams, shared, 17: 10</title><circle class="s1 ring" cx="402.9" cy="187.1" r="5"/></g><g class="mark"><title>beams, shared, 18: 12</title><circle class="s1 ring" cx="424.1" cy="174.6" r="5"/></g><g class="mark"><title>beams, shared, 19: 12</title><circle class="s1 ring" cx="445.3" cy="174.6" r="5"/></g><g class="mark"><title>beams, shared, 20: 12</title><circle class="s1 ring" cx="466.5" cy="174.6" r="5"/></g><g class="mark"><title>beams, shared, 21: 12</title><circle class="s1 ring" cx="487.6" cy="174.6" r="5"/></g><g class="mark"><title>beams, shared, 22: 15</title><circle class="s1 ring" cx="508.8" cy="155.7" r="5"/></g><g class="mark"><title>beams, shared, 23: 14</title><circle class="s1 ring" cx="530.0" cy="162.0" r="5"/></g><polyline class="l2" points="64.0,218.6 85.2,193.4 106.4,193.4 127.5,193.4 148.7,193.4 169.9,168.3 191.1,168.3 212.3,168.3 233.5,168.3 254.6,143.1 275.8,143.1 297.0,143.1 318.2,143.1 339.4,118.0 360.5,118.0 381.7,118.0 402.9,118.0 424.1,92.9 445.3,92.9 466.5,92.9 487.6,92.9 508.8,67.7 530.0,67.7"/><g class="mark"><title>samples, shared, 1: 5</title><circle class="s2 ring" cx="64.0" cy="218.6" r="5"/></g><g class="mark"><title>samples, shared, 2: 9</title><circle class="s2 ring" cx="85.2" cy="193.4" r="5"/></g><g class="mark"><title>samples, shared, 3: 9</title><circle class="s2 ring" cx="106.4" cy="193.4" r="5"/></g><g class="mark"><title>samples, shared, 4: 9</title><circle class="s2 ring" cx="127.5" cy="193.4" r="5"/></g><g class="mark"><title>samples, shared, 5: 9</title><circle class="s2 ring" cx="148.7" cy="193.4" r="5"/></g><g class="mark"><title>samples, shared, 6: 13</title><circle class="s2 ring" cx="169.9" cy="168.3" r="5"/></g><g class="mark"><title>samples, shared, 7: 13</title><circle class="s2 ring" cx="191.1" cy="168.3" r="5"/></g><g class="mark"><title>samples, shared, 8: 13</title><circle class="s2 ring" cx="212.3" cy="168.3" r="5"/></g><g class="mark"><title>samples, shared, 9: 13</title><circle class="s2 ring" cx="233.5" cy="168.3" r="5"/></g><g class="mark"><title>samples, shared, 10: 17</title><circle class="s2 ring" cx="254.6" cy="143.1" r="5"/></g><g class="mark"><title>samples, shared, 11: 17</title><circle class="s2 ring" cx="275.8" cy="143.1" r="5"/></g><g class="mark"><title>samples, shared, 12: 17</title><circle class="s2 ring" cx="297.0" cy="143.1" r="5"/></g><g class="mark"><title>samples, shared, 13: 17</title><circle class="s2 ring" cx="318.2" cy="143.1" r="5"/></g><g class="mark"><title>samples, shared, 14: 21</title><circle class="s2 ring" cx="339.4" cy="118.0" r="5"/></g><g class="mark"><title>samples, shared, 15: 21</title><circle class="s2 ring" cx="360.5" cy="118.0" r="5"/></g><g class="mark"><title>samples, shared, 16: 21</title><circle class="s2 ring" cx="381.7" cy="118.0" r="5"/></g><g class="mark"><title>samples, shared, 17: 21</title><circle class="s2 ring" cx="402.9" cy="118.0" r="5"/></g><g class="mark"><title>samples, shared, 18: 25</title><circle class="s2 ring" cx="424.1" cy="92.9" r="5"/></g><g class="mark"><title>samples, shared, 19: 25</title><circle class="s2 ring" cx="445.3" cy="92.9" r="5"/></g><g class="mark"><title>samples, shared, 20: 25</title><circle class="s2 ring" cx="466.5" cy="92.9" r="5"/></g><g class="mark"><title>samples, shared, 21: 25</title><circle class="s2 ring" cx="487.6" cy="92.9" r="5"/></g><g class="mark"><title>samples, shared, 22: 29</title><circle class="s2 ring" cx="508.8" cy="67.7" r="5"/></g><g class="mark"><title>samples, shared, 23: 29</title><circle class="s2 ring" cx="530.0" cy="67.7" r="5"/></g><line class="grid" x1="536.0" y1="48.9" x2="546.0" y2="48.9"/><rect class="s3" x="550.0" y="43.9" width="10" height="10" rx="2"/><text class="t-note" x="566.0" y="52.9" text-anchor="start">beams, no sharing: 32</text><line class="grid" x1="536.0" y1="67.7" x2="546.0" y2="67.7"/><rect class="s2" x="550.0" y="62.7" width="10" height="10" rx="2"/><text class="t-note" x="566.0" y="71.7" text-anchor="start">samples, shared: 29</text><line class="grid" x1="536.0" y1="162.0" x2="546.0" y2="162.0"/><rect class="s1" x="550.0" y="157.0" width="10" height="10" rx="2"/><text class="t-note" x="566.0" y="166.0" text-anchor="start">beams, shared: 14</text><text class="t-tick" x="297.0" y="290.0" text-anchor="middle">decoding step (block size 4)</text><text class="t-tick" x="14.0" y="18.0" text-anchor="start">physical blocks</text></svg><figcaption>Physical blocks in use at each step of our two runs. Without sharing, four beams need four full caches (top). With sharing, beam search stays far lower. The four samples share only their short prompt, so they need almost as much as four separate caches.</figcaption></figure>

> [!PAPER] · §4.4 · page 7
> [![The paragraph on memory copies in earlier systems, with frequent memory copies, copy a large portion and only copying one block of data highlighted](https://ishwarj.com/img/papers/vllm/p4-beam-copy.pnglm/p4-beam-copy.png)](/img/papers/vllm/p4-beam-copy.png)
>
> **What it says:** earlier systems needed "frequent memory copies" of the KV cache across beams. In Figure 9, beam 3 "would need to copy a large portion" of beam 2's cache. In vLLM, copy-on-write applies only when a new token lands in an old shared block, which means "only copying one block of data".
>
> **What it means:**
>
> With one contiguous chunk per beam, a beam that takes over another beam's place must copy that beam's whole cache into its own chunk. That happens again and again, because beams die and split at almost every step.
>
> With blocks, taking over a cache means copying a block table, a short list of numbers. The only real data copy is the last, half-full block, when the new beam first writes into it.

We counted both in the run above. A contiguous cache that keeps beam $$i$$ in slot $$i$$ would copy 1,029 token slots over the 24 steps. Our block manager copied 22 blocks of 4, which is 88 token slots. (The library itself copies even more: it reorders the whole cache of all beams at every step.)

How much memory does sharing save in a larger setting? We run both methods again with vLLM's default block size of 16. The prompt is the 41-token translation prefix of Figure 10 below, and every answer has 48 tokens. The saving is the paper's measure: blocks saved by sharing, divided by the blocks needed without sharing.

```text
== 3. Memory saved by sharing blocks, block size 16 (the vLLM default), prompt of the Figure 10 prefix
prompt of 41 tokens, 48 new tokens; saving = blocks saved by sharing / blocks without sharing, averaged over the steps
parallel sampling, 2 / 4 / 6 samples: 23.1% / 34.7% / 38.5%
beam search, width 2 / 4 / 6:          31.9% / 43.8% / 48.2%
```

<figure class="fig"><svg viewBox="0 0 720 230" role="img" aria-label="Bars: parallel sampling saves 23.1%, 34.7%, 38.5% for 2, 4 and 6 samples; beam search saves 31.9%, 43.8%, 48.2% for widths 2, 4 and 6."><defs><marker id="ah" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="arrow" d="M0,0L10,5L0,10z"/></marker><marker id="ah-on" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="6" markerHeight="6" orient="auto-start-reverse"><path class="arrow-on" d="M0,0L10,5L0,10z"/></marker><marker id="ah-2" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="6" markerHeight="6" orient="auto-start-reverse"><path class="arrow-2" d="M0,0L10,5L0,10z"/></marker></defs><text class="t-title" x="20.0" y="40.0" text-anchor="start">Memory saved by sharing blocks (block size 16, 41-token prompt, 48 new tokens)</text><text class="t-tick" x="142.0" y="67.0" text-anchor="end">2 samples</text><g class="mark"><title>2 samples: 23.1%</title><rect class="s1" x="150.0" y="53.0" width="181.1" height="18.0" rx="3"/></g><text class="t-val" x="337.1" y="67.0" text-anchor="start">23.1%</text><text class="t-tick" x="142.0" y="93.0" text-anchor="end">4 samples</text><g class="mark"><title>4 samples: 34.7%</title><rect class="s1" x="150.0" y="79.0" width="271.7" height="18.0" rx="3"/></g><text class="t-val" x="427.7" y="93.0" text-anchor="start">34.7%</text><text class="t-tick" x="142.0" y="119.0" text-anchor="end">6 samples</text><g class="mark"><title>6 samples: 38.5%</title><rect class="s1" x="150.0" y="105.0" width="301.9" height="18.0" rx="3"/></g><text class="t-val" x="457.9" y="119.0" text-anchor="start">38.5%</text><text class="t-tick" x="142.0" y="145.0" text-anchor="end">beam width 2</text><g class="mark"><title>beam width 2: 31.9%</title><rect class="s1" x="150.0" y="131.0" width="250.1" height="18.0" rx="3"/></g><text class="t-val" x="406.1" y="145.0" text-anchor="start">31.9%</text><text class="t-tick" x="142.0" y="171.0" text-anchor="end">beam width 4</text><g class="mark"><title>beam width 4: 43.8%</title><rect class="s1" x="150.0" y="157.0" width="342.8" height="18.0" rx="3"/></g><text class="t-val" x="498.8" y="171.0" text-anchor="start">43.8%</text><text class="t-tick" x="142.0" y="197.0" text-anchor="end">beam width 6</text><g class="mark"><title>beam width 6: 48.2%</title><rect class="s1" x="150.0" y="183.0" width="377.4" height="18.0" rx="3"/></g><text class="t-val" x="533.4" y="197.0" text-anchor="start">48.2%</text><text class="t-tick" x="150.0" y="222.0" text-anchor="start">saving = blocks saved by sharing / blocks without sharing, mean over steps</text></svg><figcaption>Memory saved by sharing in our run, block size 16. More samples or wider beams share more. Beam search saves more than parallel sampling because beams also share parts of their answers.</figcaption></figure>

Both grow with the number of sequences, and beam search saves more than sampling. The paper reports 6.1% to 9.8% for sampling and 37.6% to 55.2% for beam search, on OPT-13B with Alpaca requests (§6.3, Part 5). Our sampling numbers are higher because our prompt is long next to our answers. As the paper said, the saving depends on the prompt length.

### Shared prefix {§4.4}

The third case crosses the line between users. Most LLM products send the model more than the user typed. A support chatbot for a bank might put a hidden text in front of every question: "You are the assistant of Example Bank. Answer politely. Never give investment advice. Here are three sample answers..." This hidden text is the **system prompt**. It can be hundreds or thousands of tokens long, and it is the same for every user.

So a thousand users who each ask a short question send a thousand prompts that start with the same long text. Without sharing, the server computes the keys and values of that text a thousand times and stores a thousand copies. With paged memory, the text can be computed once, kept in a few blocks, and mapped by every request.

> [!DEFINITION] System prompt
> Instructions that a service puts in front of every user's message: the task, the rules, and often a few worked examples. The user usually does not see it. Many requests share it word for word.

> [!PAPER] · §4.4 · pages 7 to 8
> [![The paragraph on shared prefixes, with instructions and example inputs and outputs and system prompt highlighted](https://ishwarj.com/img/papers/vllm/p4-prefix-1.pngllm/p4-prefix-1.png)](/img/papers/vllm/p4-prefix-1.png)
> [![Figure 10 of the paper: two sequences whose prompts start with the same shared prefix, Translate English to French with three examples, followed by different task inputs, cheese and I love you, and their outputs fromage and Je t'amie](https://ishwarj.com/img/papers/vllm/p4-figure10.pngllm/p4-figure10.png)](/img/papers/vllm/p4-figure10.png)
>
> **What it says:** users often give a long description of the task with "instructions and example inputs and outputs", also known as a "system prompt". Figure 10 shows two requests whose prompts start with the same translation prefix and end with different task inputs.
>
> **What it means:**
>
> A translation service might put the same instruction and three worked examples in front of every word a user sends. Here every request starts with "Translate English to French:" and three example pairs. Only the last line differs: "cheese =>" in one request, "I love you =>" in the other.
>
> This is sharing across different requests from different users, not inside one request. The shared part is often much longer than the user's own text.

> [!PAPER] · §4.4 · page 8
> [![The paragraph on storing the prefix, with store the KV cache of the prefix in advance, reserving a set of physical blocks, shared library across processes, last block marked copy-on-write and task input highlighted](https://ishwarj.com/img/papers/vllm/p4-prefix-2.pngllm/p4-prefix-2.png)](/img/papers/vllm/p4-prefix-2.png)
>
> **What it says:** the service can "store the KV cache of the prefix in advance", by "reserving a set of physical blocks" for known prefixes, like an OS handles a "shared library across processes". A request maps its logical blocks to these cached blocks, with the "last block marked copy-on-write". The prompt phase then runs only on the user's "task input".
>
> **What it means:**
>
> On a computer, many programs use the same library code. The operating system keeps one copy of it in memory for all of them. vLLM does the same with a popular prefix. Its keys and values are computed once and kept in a few blocks that no request owns.
>
> A new request starts as a fork of the prefix. Its block table already points at the cached blocks, so the prompt phase skips those tokens and only reads them. This saves memory and computation: the prefix is neither stored twice nor computed twice.

We store the 41-token prefix once, in blocks of 4. Each request is a fork of it. Our `extend` then runs the prompt phase on the task tokens only. We check the answer against `model.generate` on the full prompt, computed from scratch:

```text
== 4. Shared prefix (Figure 10): the prefix is computed once and two requests map its blocks
  'cheese =>': 3 task tokens computed instead of 44; maps 10 prefix blocks, owns 3; greedy output ' pouvoir\npouv'; same as model.generate on the full prompt: True
  'I love you =>': 4 task tokens computed instead of 45; maps 10 prefix blocks, owns 4; greedy output ' le le le le le le le le'; same as model.generate on the full prompt: True
prefix of 41 tokens in 11 blocks; its last block is partly full, so each request copied it once: 2 copy-on-write copies
```

The prompt phase computed 3 tokens instead of 44 for the first request, and 4 instead of 45 for the second. Both answers equal the library's answers on the full prompt. The prefix fills 10 blocks and 1 token of an eleventh. That last block is the one "marked copy-on-write": each request copied it once, before writing its own tokens.

<figure class="fig"><svg viewBox="0 0 720 320" role="img" aria-label="Top: two requests, each with its own copy of the same long prefix followed by its task. Bottom: one stored copy of the 41-token prefix, and two short task inputs that point to it. The requests compute 3 and 4 tokens instead of 44 and 45."><defs><marker id="ah" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="arrow" d="M0,0L10,5L0,10z"/></marker><marker id="ah-on" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="6" markerHeight="6" orient="auto-start-reverse"><path class="arrow-on" d="M0,0L10,5L0,10z"/></marker><marker id="ah-2" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="6" markerHeight="6" orient="auto-start-reverse"><path class="arrow-2" d="M0,0L10,5L0,10z"/></marker></defs><text class="t-title" x="20.0" y="24.0" text-anchor="start">A 41-token shared prefix (the paper's Figure 10), two user requests</text><text class="t-tick t-strong" x="20.0" y="56.0" text-anchor="start">Without sharing: every request computes and stores the prefix again</text><rect class="box-ghost" x="20.0" y="68.0" width="360.0" height="30.0" rx="6"/><text class="t-tick" x="200.0" y="87.5" text-anchor="middle">prefix: instruction + 3 examples</text><rect class="box-2" x="388.0" y="68.0" width="150.0" height="30.0" rx="6"/><text class="t-tick" x="463.0" y="87.5" text-anchor="middle">cheese =&gt;</text><text class="t-tick" x="548.0" y="88.0" text-anchor="start">request 1</text><rect class="box-ghost" x="20.0" y="108.0" width="360.0" height="30.0" rx="6"/><text class="t-tick" x="200.0" y="127.5" text-anchor="middle">prefix: instruction + 3 examples</text><rect class="box-2" x="388.0" y="108.0" width="150.0" height="30.0" rx="6"/><text class="t-tick" x="463.0" y="127.5" text-anchor="middle">I love you =&gt;</text><text class="t-tick" x="548.0" y="128.0" text-anchor="start">request 2</text><text class="t-tick t-strong" x="20.0" y="176.0" text-anchor="start">With sharing: the prefix is computed once and every request maps its blocks</text><rect class="box-on" x="20.0" y="190.0" width="360.0" height="30.0" rx="6"/><text class="t-tick" x="200.0" y="209.5" text-anchor="middle">prefix, stored once (11 blocks of 4)</text><rect class="box-2" x="388.0" y="236.0" width="150.0" height="30.0" rx="6"/><text class="t-tick" x="463.0" y="255.5" text-anchor="middle">cheese =&gt;</text><line class="edge" x1="388" y1="251" x2="300" y2="222" marker-end="url(#ah)"/><text class="t-tick" x="548.0" y="256.0" text-anchor="start">3 tokens computed, not 44</text><rect class="box-2" x="388.0" y="276.0" width="150.0" height="30.0" rx="6"/><text class="t-tick" x="463.0" y="295.5" text-anchor="middle">I love you =&gt;</text><line class="edge" x1="388" y1="291" x2="300" y2="222" marker-end="url(#ah)"/><text class="t-tick" x="548.0" y="296.0" text-anchor="start">4 tokens computed, not 45</text></svg><figcaption>A shared prefix before and with vLLM. Top: each request computes and stores the same 41-token prefix again. Bottom: the prefix is computed once and stored in 11 blocks; each request maps those blocks and computes only its own task tokens, 3 and 4 of them.</figcaption></figure>

OPT-125M is far too small to translate. It writes nonsense French, so do not read the outputs as translations. The point is that the shared cache gives exactly the same tokens as computing everything again.

### Mixed decoding methods {§4.4}

> [!PAPER] · §4.4 · page 8
> [![The paragraph on mixed decoding methods, with simultaneous processing of requests with different decoding preferences, common mapping layer, list of physical block IDs and broadens the batching opportunities highlighted](https://ishwarj.com/img/papers/vllm/p4-mixed.pngs/vllm/p4-mixed.png)](/img/papers/vllm/p4-mixed.png)
>
> **What it says:** vLLM allows the "simultaneous processing of requests with different decoding preferences". It hides all sharing behind a "common mapping layer" from logical to physical blocks. The model and its kernel only see a "list of physical block IDs" for each sequence. This "broadens the batching opportunities".
>
> **What it means:**
>
> In one step, a batch can hold a greedy request, a request with four samples and a beam search with six beams. They share memory in completely different patterns. The attention kernel does not care. For each sequence, it gets a block table and reads those blocks, whether one sequence or five point at them.
>
> Our `extend` works the same way. It never asks why two tables hold the same number; it just reads the blocks. All the decoding logic lives above it, in fork, append and free. That split is what lets one batch mix any decoding methods.

## When memory runs out {§4.5}

Sharing makes memory go further, but it cannot make memory endless. Answers grow one token at a time, and nobody knows how long they will get. Sooner or later, a running request needs a new block and none is free.

A tiny example shows the problem. A GPU has 6 free blocks of 4 tokens. Three requests run, and each holds 2 blocks. Now each writes its next token, and the last block of each is full. Each needs one more block, and there are none. Somebody must give up memory, or nobody can take a step.

> [!NOTE] Where this idea comes from: scheduling in operating systems
> A computer runs more programs than it has processors. The part of the operating system that picks which program runs next is the **scheduler**. Its oldest rule is **first-come-first-served**: run the jobs in the order they arrived, like a queue at a counter. Modern schedulers can also **preempt**: stop a running program in the middle, give its turn to another, and resume it later.
>
> Memory has the same problem. Sometimes programs want more memory than the machine has. The operating system then moves some of their memory out to disk, and brings it back when it is needed. This is **swapping**. The early Unix systems swapped whole programs at once; later systems with paging swap single pages.
>
> vLLM borrows all three ideas. Its scheduler serves requests first-come-first-served and preempts a request when blocks run out. It can swap that request's blocks out to CPU memory, which plays the part of the disk.

> [!PAPER] · §4.5 · page 8
> [![The opening of §4.5, with first-come-first-serve (FCFS), earliest arrived requests are served first and latest requests are preempted first highlighted](https://ishwarj.com/img/papers/vllm/p4-fcfs.pngrs/vllm/p4-fcfs.png)](/img/papers/vllm/p4-fcfs.png)
>
> **What it says:** when traffic is more than the system can serve, vLLM uses a "first-come-first-serve (FCFS)" policy, for fairness and against starvation. The "earliest arrived requests are served first" and the "latest requests are preempted first".
>
> **What it means:**
>
> This is the rule of a queue at a bakery: whoever came first is served first. When the shop gets too full and someone must step outside for a while, it is the person who came in last.
>
> The rule is simple on purpose. A server could try to be clever, for example by serving short requests first. But it does not know which requests are short, and a long request could then wait forever. That is **starvation**. FCFS cannot starve anyone, because every request only waits for the ones that came before it.

> [!DEFINITION] Preemption
> Stopping a running job before it is done, to give its resources to someone else, and resuming it later. Here the resource is the request's KV cache blocks.

> [!PAPER] · §4.5 · page 8
> [![The paragraph on running out of blocks, with input prompts for an LLM can vary significantly in length, not known a priori and run out of the GPU's physical blocks highlighted](https://ishwarj.com/img/papers/vllm/p4-evict-1.pngvllm/p4-evict-1.png)](/img/papers/vllm/p4-evict-1.png)
> [![Its continuation in the right column, with Which blocks should it evict?, How to recover evicted blocks, all-or-nothing eviction policy and gang-scheduled as a sequence group highlighted](https://ishwarj.com/img/papers/vllm/p4-evict-2.pngvllm/p4-evict-2.png)](/img/papers/vllm/p4-evict-2.png)
>
> **What it says:** prompt lengths vary a lot and output lengths are "not known a priori", so vLLM can "run out of the GPU's physical blocks". It must answer two questions: "Which blocks should it evict?" and "How to recover evicted blocks". All blocks of a sequence are used together, so vLLM uses an "all-or-nothing eviction policy". The sequences of one request are "gang-scheduled as a sequence group".
>
> **What it means:**
>
> An operating system evicts single pages. It tries to guess which page nobody will need for the longest time. vLLM does not need to guess. At every step, attention reads every block of a running sequence, from the first to the last. Evicting half of a sequence's blocks saves nothing, because the sequence cannot take a single step without them. So either all its blocks stay, or all go.
>
> The same holds one level up. Four samples or six beams of one request share blocks. Evicting one beam would not free the shared blocks, and the beams must stay together to compare scores. So a whole request, its **sequence group**, is stopped and resumed as one unit.

> [!DEFINITION] Eviction
> Removing data from fast memory to make room. The data is either thrown away or moved to slower memory, and must be brought back or rebuilt before it is used again.

Go back to the tiny example: 6 blocks, three requests with 2 blocks each, and all three need a third block. Request 3 arrived last, so it is preempted and gives up both of its blocks. Now 2 blocks are free. Requests 1 and 2 take one each and go on. Request 3 waits until one of the others finishes.

Why not take only one block from request 3, so that it could keep going? Because the next step of request 3 reads all of its blocks. With one block missing, it cannot run at all, and the block it kept is wasted space. This is the old Unix choice too: a program that cannot run gives up all its memory at once.

> [!PAPER] · §4.5 · page 8
> [![The paragraph on swapping, with copy evicted blocks to the CPU memory, CPU block allocator, stops accepting new requests until all preempted sequences and never exceeds the number of total physical highlighted](https://ishwarj.com/img/papers/vllm/p4-swap.pngrs/vllm/p4-swap.png)](/img/papers/vllm/p4-swap.png)
>
> **What it says:** the first way to recover is swapping. vLLM will "copy evicted blocks to the CPU memory", managed by a "CPU block allocator". After a preemption, it "stops accepting new requests until all preempted sequences" are done. So the blocks in CPU memory "never exceeds the number of total physical" blocks on the GPU.
>
> **What it means:**
>
> The CPU of a server has its own memory, often several times larger than the GPU's. Swapping parks a preempted request's blocks there. When room appears on the GPU, the blocks are copied back and the request goes on as if nothing happened.
>
> The rule about new requests is what keeps this bounded. While any request is parked, no newcomer may start, so the parked requests always come back first. The total parked can never exceed what fit on the GPU in the first place. A server can size its CPU swap space in advance.

> [!PAPER] · §4.5 · page 8
> [![The paragraph on recomputation, with significantly lower than the original latency, one prompt phase iteration, bandwidth between CPU RAM and GPU memory and computation power of the GPU highlighted](https://ishwarj.com/img/papers/vllm/p4-recompute.pnglm/p4-recompute.png)](/img/papers/vllm/p4-recompute.png)
>
> **What it says:** the second way is recomputation: throw the cache away and compute it again on resume. This can be "significantly lower than the original latency", because the prompt and the written tokens form a new prompt, whose cache comes out in "one prompt phase iteration". Which way is faster depends on the "bandwidth between CPU RAM and GPU memory" and the "computation power of the GPU".
>
> **What it means:**
>
> Recomputation sounds wasteful, but there is a trick. The request first built its cache slowly, one token per step, because each token had to be written before the next. On resume, all those tokens are already known. They can go through the model in one pass, as one long prompt, using the GPU at full speed (Part 2).
>
> An operating system can never do this. A page of a program's memory cannot be rebuilt from nothing. A KV cache can, because it is a pure function of the tokens. That makes recomputation a choice that only an LLM server has.

> [!DEFINITION] Bandwidth
> How many bytes a connection moves per second. Between CPU memory and a server GPU, data moves over **PCIe**, the standard slot that connects a GPU card to the rest of the computer. PCIe is much slower than the memory inside the GPU.

> [!DEFINITION] Latency
> The time one request waits from the moment it is sent until its answer is complete. A preempted request has a longer latency, because it spends some steps waiting.

The picture puts both ways of recovering on one timeline. Three requests run. At step 5 no block is free, and request 3, the last to arrive, is preempted. At step 8 request 1 ends, and its blocks become free. With swapping, request 3's blocks waited in CPU memory and are copied back. With recomputation, they were thrown away and one prompt pass builds them again.

Either way, request 3 then runs on from the token where it stopped. Its answer is the same; only its latency is longer.

<figure class="fig"><svg viewBox="0 0 720 442" role="img" aria-label="Two timelines of 12 steps with three requests. At step 5 memory is full and request 3, the last to arrive, is preempted. With swapping its blocks wait in CPU memory and are copied back in steps 9 and 10. With recomputation its blocks are thrown away and one prompt pass rebuilds them in steps 9 and 10. Request 1 ends at step 8 and frees the room."><defs><marker id="ah" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="arrow" d="M0,0L10,5L0,10z"/></marker><marker id="ah-on" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="6" markerHeight="6" orient="auto-start-reverse"><path class="arrow-on" d="M0,0L10,5L0,10z"/></marker><marker id="ah-2" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="6" markerHeight="6" orient="auto-start-reverse"><path class="arrow-2" d="M0,0L10,5L0,10z"/></marker></defs><text class="t-title" x="20.0" y="24.0" text-anchor="start">One preemption, two ways to recover (a sketch, 12 steps)</text><text class="t-tick" x="133.0" y="50.0" text-anchor="middle">1</text><text class="t-tick" x="179.0" y="50.0" text-anchor="middle">2</text><text class="t-tick" x="225.0" y="50.0" text-anchor="middle">3</text><text class="t-tick" x="271.0" y="50.0" text-anchor="middle">4</text><text class="t-tick" x="317.0" y="50.0" text-anchor="middle">5</text><text class="t-tick" x="363.0" y="50.0" text-anchor="middle">6</text><text class="t-tick" x="409.0" y="50.0" text-anchor="middle">7</text><text class="t-tick" x="455.0" y="50.0" text-anchor="middle">8</text><text class="t-tick" x="501.0" y="50.0" text-anchor="middle">9</text><text class="t-tick" x="547.0" y="50.0" text-anchor="middle">10</text><text class="t-tick" x="593.0" y="50.0" text-anchor="middle">11</text><text class="t-tick" x="639.0" y="50.0" text-anchor="middle">12</text><text class="t-tick" x="20.0" y="50.0" text-anchor="start">step</text><text class="t-tick t-strong" x="20.0" y="76.0" text-anchor="start">Swapping</text><text class="t-tick" x="20.0" y="105.0" text-anchor="start">request 1</text><rect class="box-1" x="111.0" y="86.0" width="320.0" height="28.0" rx="6"/><text class="t-tick" x="271.0" y="104.5" text-anchor="middle">running</text><rect class="box" x="433.0" y="86.0" width="44.0" height="28.0" rx="6"/><text class="t-tick" x="455.0" y="104.5" text-anchor="middle">done</text><text class="t-tick" x="20.0" y="141.0" text-anchor="start">request 2</text><rect class="box-1" x="111.0" y="122.0" width="550.0" height="28.0" rx="6"/><text class="t-tick" x="386.0" y="140.5" text-anchor="middle">running</text><text class="t-tick" x="20.0" y="177.0" text-anchor="start">request 3</text><rect class="box-1" x="111.0" y="158.0" width="182.0" height="28.0" rx="6"/><text class="t-tick" x="202.0" y="176.5" text-anchor="middle">running</text><rect class="box-2" x="295.0" y="158.0" width="182.0" height="28.0" rx="6"/><text class="t-tick" x="386.0" y="176.5" text-anchor="middle">blocks in CPU memory</text><rect class="box-3" x="479.0" y="158.0" width="90.0" height="28.0" rx="6"/><text class="t-tick" x="524.0" y="176.5" text-anchor="middle">swap in</text><rect class="box-1" x="571.0" y="158.0" width="90.0" height="28.0" rx="6"/><text class="t-tick" x="616.0" y="176.5" text-anchor="middle">running</text><line class="bad-line" x1="294" y1="168" x2="294" y2="210"/><text class="t-tick t-strong" x="290.0" y="222.0" text-anchor="end">preempted</text><text class="t-tick t-strong" x="20.0" y="242.0" text-anchor="start">Recomputation</text><text class="t-tick" x="20.0" y="271.0" text-anchor="start">request 1</text><rect class="box-1" x="111.0" y="252.0" width="320.0" height="28.0" rx="6"/><text class="t-tick" x="271.0" y="270.5" text-anchor="middle">running</text><rect class="box" x="433.0" y="252.0" width="44.0" height="28.0" rx="6"/><text class="t-tick" x="455.0" y="270.5" text-anchor="middle">done</text><text class="t-tick" x="20.0" y="307.0" text-anchor="start">request 2</text><rect class="box-1" x="111.0" y="288.0" width="550.0" height="28.0" rx="6"/><text class="t-tick" x="386.0" y="306.5" text-anchor="middle">running</text><text class="t-tick" x="20.0" y="343.0" text-anchor="start">request 3</text><rect class="box-1" x="111.0" y="324.0" width="182.0" height="28.0" rx="6"/><text class="t-tick" x="202.0" y="342.5" text-anchor="middle">running</text><rect class="box-ghost" x="295.0" y="324.0" width="182.0" height="28.0" rx="6"/><text class="t-tick" x="386.0" y="342.5" text-anchor="middle">blocks thrown away</text><rect class="box-3" x="479.0" y="324.0" width="90.0" height="28.0" rx="6"/><text class="t-tick" x="524.0" y="342.5" text-anchor="middle">prompt pass</text><rect class="box-1" x="571.0" y="324.0" width="90.0" height="28.0" rx="6"/><text class="t-tick" x="616.0" y="342.5" text-anchor="middle">running</text><line class="bad-line" x1="294" y1="334" x2="294" y2="376"/><text class="t-tick t-strong" x="290.0" y="388.0" text-anchor="end">preempted</text><text class="t-tick" x="20.0" y="414.0" text-anchor="start">Step 5: no block is free, so the request that came last loses all its blocks at once.</text><text class="t-tick" x="20.0" y="432.0" text-anchor="start">Step 8: request 1 ends and frees its blocks, so request 3 can come back.</text></svg><figcaption>One preemption, recovered in two ways (a sketch, not a measurement). Top: with swapping, the preempted request's blocks wait in CPU memory and are copied back when room appears. Bottom: with recomputation, the blocks are thrown away and rebuilt in one prompt pass. In both, the request that arrived last is the one preempted.</figcaption></figure>

We build the scheduler as a simulation in steps, with the memory rules above and no model. The requests are 200 real Alpaca prompts and answers, counted in OPT tokens; one arrives per step. The GPU has room for 64 blocks of 16 tokens. Here is the part that preempts:

```python
        # 2. every running request writes one token; it may need one more block. If none is free, preempt the
        #    request that arrived last (all of its blocks), as often as needed.
        for r in list(running):
            if r not in running:
                continue
            n = REQ[r][0] + gen[r]                          # tokens stored so far
            if n % BS == 0:                                 # the last block is full
                while free == 0:
                    victim = running.pop()                   # the latest arrival
                    hold = blocks(REQ[victim][0] + gen[victim])
                    free += hold
                    st['preemptions'] += 1
                    st['preempt_steps'].append(t)
                    if policy == 'swap':
                        st['swap_out'] += hold; cpu += hold; cpu_max = max(cpu_max, cpu)
                    preempted.append(victim); preempted.sort()
                    if victim == r:
                        break
                if r not in running:
                    continue
                free -= 1
```

The running list is sorted by arrival, so `running.pop()` takes the request that came last. It loses all its blocks at once. At the start of each step, the scheduler brings back preempted requests, oldest first. It admits no new request while any is still out. We run the same traffic with swapping and with recomputation. In the output, look for two things: whether every request still gets all its tokens, and what each method pays for its preemptions.

```text
== 5. First-come-first-served scheduling with preemption (simulation in steps, Alpaca request lengths)
200 requests, one per step; prompt mean 19.9 tokens, output mean 53.8; GPU memory: 64 blocks of 16 tokens
swap     : 873 steps, mean batch 12.3, 356 preemptions; every request got all its tokens: True
recompute: 873 steps, mean batch 12.3, 356 preemptions; every request got all its tokens: True
swap     : 705 blocks out, 705 in; at most 24 blocks in CPU memory (never more than the 64 GPU blocks: True)
           bytes moved, OPT-13B: 18.48 GB; OPT-125M: 831.7 MB
recompute: 9,115 tokens computed again, in 356 prompt passes
```

<figure class="fig"><svg viewBox="0 0 720 360" role="img" aria-label="Over 873 steps, the number of running requests stays near 12 and the free blocks stay near zero; 356 preemptions happen while the queue is long."><defs><marker id="ah" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="arrow" d="M0,0L10,5L0,10z"/></marker><marker id="ah-on" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="6" markerHeight="6" orient="auto-start-reverse"><path class="arrow-on" d="M0,0L10,5L0,10z"/></marker><marker id="ah-2" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="6" markerHeight="6" orient="auto-start-reverse"><path class="arrow-2" d="M0,0L10,5L0,10z"/></marker></defs><text class="t-title" x="20.0" y="24.0" text-anchor="start">Our scheduler on Alpaca lengths: 64 blocks of 16 tokens, 356 preemptions</text><line class="grid" x1="60" y1="290.0" x2="680" y2="290.0"/><text class="t-tick" x="52.0" y="294.0" text-anchor="end">0</text><line class="grid" x1="60" y1="235.0" x2="680" y2="235.0"/><text class="t-tick" x="52.0" y="239.0" text-anchor="end">16</text><line class="grid" x1="60" y1="180.0" x2="680" y2="180.0"/><text class="t-tick" x="52.0" y="184.0" text-anchor="end">32</text><line class="grid" x1="60" y1="125.0" x2="680" y2="125.0"/><text class="t-tick" x="52.0" y="129.0" text-anchor="end">48</text><line class="grid" x1="60" y1="70.0" x2="680" y2="70.0"/><text class="t-tick" x="52.0" y="74.0" text-anchor="end">64</text><line class="edge-dim" x1="93.4" y1="290" x2="93.4" y2="298"/><line class="edge-dim" x1="93.4" y1="290" x2="93.4" y2="298"/><line class="edge-dim" x1="94.1" y1="290" x2="94.1" y2="298"/><line class="edge-dim" x1="94.8" y1="290" x2="94.8" y2="298"/><line class="edge-dim" x1="94.8" y1="290" x2="94.8" y2="298"/><line class="edge-dim" x1="94.8" y1="290" x2="94.8" y2="298"/><line class="edge-dim" x1="95.6" y1="290" x2="95.6" y2="298"/><line class="edge-dim" x1="95.6" y1="290" x2="95.6" y2="298"/><line class="edge-dim" x1="97.7" y1="290" x2="97.7" y2="298"/><line class="edge-dim" x1="98.4" y1="290" x2="98.4" y2="298"/><line class="edge-dim" x1="99.8" y1="290" x2="99.8" y2="298"/><line class="edge-dim" x1="102.7" y1="290" x2="102.7" y2="298"/><line class="edge-dim" x1="104.8" y1="290" x2="104.8" y2="298"/><line class="edge-dim" x1="105.5" y1="290" x2="105.5" y2="298"/><line class="edge-dim" x1="106.2" y1="290" x2="106.2" y2="298"/><line class="edge-dim" x1="106.2" y1="290" x2="106.2" y2="298"/><line class="edge-dim" x1="106.9" y1="290" x2="106.9" y2="298"/><line class="edge-dim" x1="109.8" y1="290" x2="109.8" y2="298"/><line class="edge-dim" x1="112.6" y1="290" x2="112.6" y2="298"/><line class="edge-dim" x1="114.0" y1="290" x2="114.0" y2="298"/><line class="edge-dim" x1="116.2" y1="290" x2="116.2" y2="298"/><line class="edge-dim" x1="117.6" y1="290" x2="117.6" y2="298"/><line class="edge-dim" x1="118.3" y1="290" x2="118.3" y2="298"/><line class="edge-dim" x1="121.1" y1="290" x2="121.1" y2="298"/><line class="edge-dim" x1="122.6" y1="290" x2="122.6" y2="298"/><line class="edge-dim" x1="124.7" y1="290" x2="124.7" y2="298"/><line class="edge-dim" x1="129.0" y1="290" x2="129.0" y2="298"/><line class="edge-dim" x1="129.7" y1="290" x2="129.7" y2="298"/><line class="edge-dim" x1="132.5" y1="290" x2="132.5" y2="298"/><line class="edge-dim" x1="133.9" y1="290" x2="133.9" y2="298"/><line class="edge-dim" x1="138.2" y1="290" x2="138.2" y2="298"/><line class="edge-dim" x1="138.2" y1="290" x2="138.2" y2="298"/><line class="edge-dim" x1="138.2" y1="290" x2="138.2" y2="298"/><line class="edge-dim" x1="138.9" y1="290" x2="138.9" y2="298"/><line class="edge-dim" x1="141.1" y1="290" x2="141.1" y2="298"/><line class="edge-dim" x1="141.8" y1="290" x2="141.8" y2="298"/><line class="edge-dim" x1="143.2" y1="290" x2="143.2" y2="298"/><line class="edge-dim" x1="143.9" y1="290" x2="143.9" y2="298"/><line class="edge-dim" x1="145.3" y1="290" x2="145.3" y2="298"/><line class="edge-dim" x1="147.5" y1="290" x2="147.5" y2="298"/><line class="edge-dim" x1="148.2" y1="290" x2="148.2" y2="298"/><line class="edge-dim" x1="151.7" y1="290" x2="151.7" y2="298"/><line class="edge-dim" x1="152.4" y1="290" x2="152.4" y2="298"/><line class="edge-dim" x1="153.1" y1="290" x2="153.1" y2="298"/><line class="edge-dim" x1="155.3" y1="290" x2="155.3" y2="298"/><line class="edge-dim" x1="157.4" y1="290" x2="157.4" y2="298"/><line class="edge-dim" x1="158.8" y1="290" x2="158.8" y2="298"/><line class="edge-dim" x1="159.5" y1="290" x2="159.5" y2="298"/><line class="edge-dim" x1="161.7" y1="290" x2="161.7" y2="298"/><line class="edge-dim" x1="163.1" y1="290" x2="163.1" y2="298"/><line class="edge-dim" x1="163.8" y1="290" x2="163.8" y2="298"/><line class="edge-dim" x1="163.8" y1="290" x2="163.8" y2="298"/><line class="edge-dim" x1="164.5" y1="290" x2="164.5" y2="298"/><line class="edge-dim" x1="164.5" y1="290" x2="164.5" y2="298"/><line class="edge-dim" x1="166.7" y1="290" x2="166.7" y2="298"/><line class="edge-dim" x1="168.8" y1="290" x2="168.8" y2="298"/><line class="edge-dim" x1="170.2" y1="290" x2="170.2" y2="298"/><line class="edge-dim" x1="173.1" y1="290" x2="173.1" y2="298"/><line class="edge-dim" x1="175.2" y1="290" x2="175.2" y2="298"/><line class="edge-dim" x1="175.9" y1="290" x2="175.9" y2="298"/><line class="edge-dim" x1="180.2" y1="290" x2="180.2" y2="298"/><line class="edge-dim" x1="182.3" y1="290" x2="182.3" y2="298"/><line class="edge-dim" x1="190.1" y1="290" x2="190.1" y2="298"/><line class="edge-dim" x1="190.8" y1="290" x2="190.8" y2="298"/><line class="edge-dim" x1="191.5" y1="290" x2="191.5" y2="298"/><line class="edge-dim" x1="192.2" y1="290" x2="192.2" y2="298"/><line class="edge-dim" x1="193.0" y1="290" x2="193.0" y2="298"/><line class="edge-dim" x1="193.0" y1="290" x2="193.0" y2="298"/><line class="edge-dim" x1="193.0" y1="290" x2="193.0" y2="298"/><line class="edge-dim" x1="193.7" y1="290" x2="193.7" y2="298"/><line class="edge-dim" x1="193.7" y1="290" x2="193.7" y2="298"/><line class="edge-dim" x1="197.9" y1="290" x2="197.9" y2="298"/><line class="edge-dim" x1="200.8" y1="290" x2="200.8" y2="298"/><line class="edge-dim" x1="208.6" y1="290" x2="208.6" y2="298"/><line class="edge-dim" x1="208.6" y1="290" x2="208.6" y2="298"/><line class="edge-dim" x1="209.3" y1="290" x2="209.3" y2="298"/><line class="edge-dim" x1="209.3" y1="290" x2="209.3" y2="298"/><line class="edge-dim" x1="209.3" y1="290" x2="209.3" y2="298"/><line class="edge-dim" x1="209.3" y1="290" x2="209.3" y2="298"/><line class="edge-dim" x1="210.0" y1="290" x2="210.0" y2="298"/><line class="edge-dim" x1="210.7" y1="290" x2="210.7" y2="298"/><line class="edge-dim" x1="211.4" y1="290" x2="211.4" y2="298"/><line class="edge-dim" x1="214.3" y1="290" x2="214.3" y2="298"/><line class="edge-dim" x1="215.0" y1="290" x2="215.0" y2="298"/><line class="edge-dim" x1="215.7" y1="290" x2="215.7" y2="298"/><line class="edge-dim" x1="216.4" y1="290" x2="216.4" y2="298"/><line class="edge-dim" x1="219.3" y1="290" x2="219.3" y2="298"/><line class="edge-dim" x1="219.3" y1="290" x2="219.3" y2="298"/><line class="edge-dim" x1="220.7" y1="290" x2="220.7" y2="298"/><line class="edge-dim" x1="220.7" y1="290" x2="220.7" y2="298"/><line class="edge-dim" x1="221.4" y1="290" x2="221.4" y2="298"/><line class="edge-dim" x1="222.1" y1="290" x2="222.1" y2="298"/><line class="edge-dim" x1="222.8" y1="290" x2="222.8" y2="298"/><line class="edge-dim" x1="223.5" y1="290" x2="223.5" y2="298"/><line class="edge-dim" x1="224.2" y1="290" x2="224.2" y2="298"/><line class="edge-dim" x1="224.2" y1="290" x2="224.2" y2="298"/><line class="edge-dim" x1="226.4" y1="290" x2="226.4" y2="298"/><line class="edge-dim" x1="227.1" y1="290" x2="227.1" y2="298"/><line class="edge-dim" x1="227.8" y1="290" x2="227.8" y2="298"/><line class="edge-dim" x1="229.9" y1="290" x2="229.9" y2="298"/><line class="edge-dim" x1="231.4" y1="290" x2="231.4" y2="298"/><line class="edge-dim" x1="232.1" y1="290" x2="232.1" y2="298"/><line class="edge-dim" x1="235.6" y1="290" x2="235.6" y2="298"/><line class="edge-dim" x1="237.8" y1="290" x2="237.8" y2="298"/><line class="edge-dim" x1="239.2" y1="290" x2="239.2" y2="298"/><line class="edge-dim" x1="242.0" y1="290" x2="242.0" y2="298"/><line class="edge-dim" x1="243.4" y1="290" x2="243.4" y2="298"/><line class="edge-dim" x1="244.2" y1="290" x2="244.2" y2="298"/><line class="edge-dim" x1="247.0" y1="290" x2="247.0" y2="298"/><line class="edge-dim" x1="250.6" y1="290" x2="250.6" y2="298"/><line class="edge-dim" x1="252.0" y1="290" x2="252.0" y2="298"/><line class="edge-dim" x1="253.4" y1="290" x2="253.4" y2="298"/><line class="edge-dim" x1="254.8" y1="290" x2="254.8" y2="298"/><line class="edge-dim" x1="255.5" y1="290" x2="255.5" y2="298"/><line class="edge-dim" x1="256.9" y1="290" x2="256.9" y2="298"/><line class="edge-dim" x1="258.4" y1="290" x2="258.4" y2="298"/><line class="edge-dim" x1="259.1" y1="290" x2="259.1" y2="298"/><line class="edge-dim" x1="261.9" y1="290" x2="261.9" y2="298"/><line class="edge-dim" x1="261.9" y1="290" x2="261.9" y2="298"/><line class="edge-dim" x1="264.8" y1="290" x2="264.8" y2="298"/><line class="edge-dim" x1="265.5" y1="290" x2="265.5" y2="298"/><line class="edge-dim" x1="266.9" y1="290" x2="266.9" y2="298"/><line class="edge-dim" x1="268.3" y1="290" x2="268.3" y2="298"/><line class="edge-dim" x1="270.5" y1="290" x2="270.5" y2="298"/><line class="edge-dim" x1="273.3" y1="290" x2="273.3" y2="298"/><line class="edge-dim" x1="273.3" y1="290" x2="273.3" y2="298"/><line class="edge-dim" x1="277.6" y1="290" x2="277.6" y2="298"/><line class="edge-dim" x1="278.3" y1="290" x2="278.3" y2="298"/><line class="edge-dim" x1="279.0" y1="290" x2="279.0" y2="298"/><line class="edge-dim" x1="279.7" y1="290" x2="279.7" y2="298"/><line class="edge-dim" x1="279.7" y1="290" x2="279.7" y2="298"/><line class="edge-dim" x1="281.1" y1="290" x2="281.1" y2="298"/><line class="edge-dim" x1="284.7" y1="290" x2="284.7" y2="298"/><line class="edge-dim" x1="289.7" y1="290" x2="289.7" y2="298"/><line class="edge-dim" x1="289.7" y1="290" x2="289.7" y2="298"/><line class="edge-dim" x1="290.4" y1="290" x2="290.4" y2="298"/><line class="edge-dim" x1="291.1" y1="290" x2="291.1" y2="298"/><line class="edge-dim" x1="291.1" y1="290" x2="291.1" y2="298"/><line class="edge-dim" x1="293.2" y1="290" x2="293.2" y2="298"/><line class="edge-dim" x1="293.9" y1="290" x2="293.9" y2="298"/><line class="edge-dim" x1="294.6" y1="290" x2="294.6" y2="298"/><line class="edge-dim" x1="295.3" y1="290" x2="295.3" y2="298"/><line class="edge-dim" x1="296.1" y1="290" x2="296.1" y2="298"/><line class="edge-dim" x1="299.6" y1="290" x2="299.6" y2="298"/><line class="edge-dim" x1="301.0" y1="290" x2="301.0" y2="298"/><line class="edge-dim" x1="302.5" y1="290" x2="302.5" y2="298"/><line class="edge-dim" x1="304.6" y1="290" x2="304.6" y2="298"/><line class="edge-dim" x1="313.8" y1="290" x2="313.8" y2="298"/><line class="edge-dim" x1="322.4" y1="290" x2="322.4" y2="298"/><line class="edge-dim" x1="325.2" y1="290" x2="325.2" y2="298"/><line class="edge-dim" x1="332.3" y1="290" x2="332.3" y2="298"/><line class="edge-dim" x1="333.0" y1="290" x2="333.0" y2="298"/><line class="edge-dim" x1="333.7" y1="290" x2="333.7" y2="298"/><line class="edge-dim" x1="334.4" y1="290" x2="334.4" y2="298"/><line class="edge-dim" x1="335.9" y1="290" x2="335.9" y2="298"/><line class="edge-dim" x1="336.6" y1="290" x2="336.6" y2="298"/><line class="edge-dim" x1="338.0" y1="290" x2="338.0" y2="298"/><line class="edge-dim" x1="340.8" y1="290" x2="340.8" y2="298"/><line class="edge-dim" x1="348.0" y1="290" x2="348.0" y2="298"/><line class="edge-dim" x1="350.1" y1="290" x2="350.1" y2="298"/><line class="edge-dim" x1="356.5" y1="290" x2="356.5" y2="298"/><line class="edge-dim" x1="357.2" y1="290" x2="357.2" y2="298"/><line class="edge-dim" x1="357.2" y1="290" x2="357.2" y2="298"/><line class="edge-dim" x1="359.3" y1="290" x2="359.3" y2="298"/><line class="edge-dim" x1="360.8" y1="290" x2="360.8" y2="298"/><line class="edge-dim" x1="361.5" y1="290" x2="361.5" y2="298"/><line class="edge-dim" x1="363.6" y1="290" x2="363.6" y2="298"/><line class="edge-dim" x1="366.4" y1="290" x2="366.4" y2="298"/><line class="edge-dim" x1="367.9" y1="290" x2="367.9" y2="298"/><line class="edge-dim" x1="370.0" y1="290" x2="370.0" y2="298"/><line class="edge-dim" x1="370.7" y1="290" x2="370.7" y2="298"/><line class="edge-dim" x1="370.7" y1="290" x2="370.7" y2="298"/><line class="edge-dim" x1="370.7" y1="290" x2="370.7" y2="298"/><line class="edge-dim" x1="372.8" y1="290" x2="372.8" y2="298"/><line class="edge-dim" x1="374.3" y1="290" x2="374.3" y2="298"/><line class="edge-dim" x1="375.0" y1="290" x2="375.0" y2="298"/><line class="edge-dim" x1="375.7" y1="290" x2="375.7" y2="298"/><line class="edge-dim" x1="376.4" y1="290" x2="376.4" y2="298"/><line class="edge-dim" x1="376.4" y1="290" x2="376.4" y2="298"/><line class="edge-dim" x1="377.1" y1="290" x2="377.1" y2="298"/><line class="edge-dim" x1="379.2" y1="290" x2="379.2" y2="298"/><line class="edge-dim" x1="381.4" y1="290" x2="381.4" y2="298"/><line class="edge-dim" x1="381.4" y1="290" x2="381.4" y2="298"/><line class="edge-dim" x1="382.1" y1="290" x2="382.1" y2="298"/><line class="edge-dim" x1="382.8" y1="290" x2="382.8" y2="298"/><line class="edge-dim" x1="383.5" y1="290" x2="383.5" y2="298"/><line class="edge-dim" x1="384.2" y1="290" x2="384.2" y2="298"/><line class="edge-dim" x1="385.6" y1="290" x2="385.6" y2="298"/><line class="edge-dim" x1="385.6" y1="290" x2="385.6" y2="298"/><line class="edge-dim" x1="386.4" y1="290" x2="386.4" y2="298"/><line class="edge-dim" x1="387.1" y1="290" x2="387.1" y2="298"/><line class="edge-dim" x1="388.5" y1="290" x2="388.5" y2="298"/><line class="edge-dim" x1="389.2" y1="290" x2="389.2" y2="298"/><line class="edge-dim" x1="390.6" y1="290" x2="390.6" y2="298"/><line class="edge-dim" x1="392.0" y1="290" x2="392.0" y2="298"/><line class="edge-dim" x1="392.8" y1="290" x2="392.8" y2="298"/><line class="edge-dim" x1="394.2" y1="290" x2="394.2" y2="298"/><line class="edge-dim" x1="395.6" y1="290" x2="395.6" y2="298"/><line class="edge-dim" x1="397.0" y1="290" x2="397.0" y2="298"/><line class="edge-dim" x1="397.7" y1="290" x2="397.7" y2="298"/><line class="edge-dim" x1="400.6" y1="290" x2="400.6" y2="298"/><line class="edge-dim" x1="402.0" y1="290" x2="402.0" y2="298"/><line class="edge-dim" x1="404.1" y1="290" x2="404.1" y2="298"/><line class="edge-dim" x1="404.8" y1="290" x2="404.8" y2="298"/><line class="edge-dim" x1="405.6" y1="290" x2="405.6" y2="298"/><line class="edge-dim" x1="405.6" y1="290" x2="405.6" y2="298"/><line class="edge-dim" x1="406.3" y1="290" x2="406.3" y2="298"/><line class="edge-dim" x1="407.7" y1="290" x2="407.7" y2="298"/><line class="edge-dim" x1="407.7" y1="290" x2="407.7" y2="298"/><line class="edge-dim" x1="408.4" y1="290" x2="408.4" y2="298"/><line class="edge-dim" x1="409.8" y1="290" x2="409.8" y2="298"/><line class="edge-dim" x1="411.9" y1="290" x2="411.9" y2="298"/><line class="edge-dim" x1="414.1" y1="290" x2="414.1" y2="298"/><line class="edge-dim" x1="415.5" y1="290" x2="415.5" y2="298"/><line class="edge-dim" x1="416.9" y1="290" x2="416.9" y2="298"/><line class="edge-dim" x1="417.6" y1="290" x2="417.6" y2="298"/><line class="edge-dim" x1="419.8" y1="290" x2="419.8" y2="298"/><line class="edge-dim" x1="421.2" y1="290" x2="421.2" y2="298"/><line class="edge-dim" x1="422.6" y1="290" x2="422.6" y2="298"/><line class="edge-dim" x1="425.5" y1="290" x2="425.5" y2="298"/><line class="edge-dim" x1="426.2" y1="290" x2="426.2" y2="298"/><line class="edge-dim" x1="428.3" y1="290" x2="428.3" y2="298"/><line class="edge-dim" x1="428.3" y1="290" x2="428.3" y2="298"/><line class="edge-dim" x1="431.9" y1="290" x2="431.9" y2="298"/><line class="edge-dim" x1="432.6" y1="290" x2="432.6" y2="298"/><line class="edge-dim" x1="436.1" y1="290" x2="436.1" y2="298"/><line class="edge-dim" x1="436.8" y1="290" x2="436.8" y2="298"/><line class="edge-dim" x1="438.3" y1="290" x2="438.3" y2="298"/><line class="edge-dim" x1="439.0" y1="290" x2="439.0" y2="298"/><line class="edge-dim" x1="439.7" y1="290" x2="439.7" y2="298"/><line class="edge-dim" x1="440.4" y1="290" x2="440.4" y2="298"/><line class="edge-dim" x1="441.1" y1="290" x2="441.1" y2="298"/><line class="edge-dim" x1="441.8" y1="290" x2="441.8" y2="298"/><line class="edge-dim" x1="442.5" y1="290" x2="442.5" y2="298"/><line class="edge-dim" x1="443.2" y1="290" x2="443.2" y2="298"/><line class="edge-dim" x1="443.9" y1="290" x2="443.9" y2="298"/><line class="edge-dim" x1="446.1" y1="290" x2="446.1" y2="298"/><line class="edge-dim" x1="447.5" y1="290" x2="447.5" y2="298"/><line class="edge-dim" x1="450.3" y1="290" x2="450.3" y2="298"/><line class="edge-dim" x1="453.2" y1="290" x2="453.2" y2="298"/><line class="edge-dim" x1="453.2" y1="290" x2="453.2" y2="298"/><line class="edge-dim" x1="455.3" y1="290" x2="455.3" y2="298"/><line class="edge-dim" x1="456.0" y1="290" x2="456.0" y2="298"/><line class="edge-dim" x1="458.9" y1="290" x2="458.9" y2="298"/><line class="edge-dim" x1="461.7" y1="290" x2="461.7" y2="298"/><line class="edge-dim" x1="461.7" y1="290" x2="461.7" y2="298"/><line class="edge-dim" x1="461.7" y1="290" x2="461.7" y2="298"/><line class="edge-dim" x1="461.7" y1="290" x2="461.7" y2="298"/><line class="edge-dim" x1="462.4" y1="290" x2="462.4" y2="298"/><line class="edge-dim" x1="462.4" y1="290" x2="462.4" y2="298"/><line class="edge-dim" x1="463.1" y1="290" x2="463.1" y2="298"/><line class="edge-dim" x1="463.1" y1="290" x2="463.1" y2="298"/><line class="edge-dim" x1="463.9" y1="290" x2="463.9" y2="298"/><line class="edge-dim" x1="464.6" y1="290" x2="464.6" y2="298"/><line class="edge-dim" x1="464.6" y1="290" x2="464.6" y2="298"/><line class="edge-dim" x1="466.0" y1="290" x2="466.0" y2="298"/><line class="edge-dim" x1="466.7" y1="290" x2="466.7" y2="298"/><line class="edge-dim" x1="466.7" y1="290" x2="466.7" y2="298"/><line class="edge-dim" x1="467.4" y1="290" x2="467.4" y2="298"/><line class="edge-dim" x1="468.1" y1="290" x2="468.1" y2="298"/><line class="edge-dim" x1="470.3" y1="290" x2="470.3" y2="298"/><line class="edge-dim" x1="473.1" y1="290" x2="473.1" y2="298"/><line class="edge-dim" x1="473.1" y1="290" x2="473.1" y2="298"/><line class="edge-dim" x1="473.8" y1="290" x2="473.8" y2="298"/><line class="edge-dim" x1="474.5" y1="290" x2="474.5" y2="298"/><line class="edge-dim" x1="475.9" y1="290" x2="475.9" y2="298"/><line class="edge-dim" x1="478.8" y1="290" x2="478.8" y2="298"/><line class="edge-dim" x1="479.5" y1="290" x2="479.5" y2="298"/><line class="edge-dim" x1="480.9" y1="290" x2="480.9" y2="298"/><line class="edge-dim" x1="481.6" y1="290" x2="481.6" y2="298"/><line class="edge-dim" x1="484.5" y1="290" x2="484.5" y2="298"/><line class="edge-dim" x1="485.9" y1="290" x2="485.9" y2="298"/><line class="edge-dim" x1="489.4" y1="290" x2="489.4" y2="298"/><line class="edge-dim" x1="491.6" y1="290" x2="491.6" y2="298"/><line class="edge-dim" x1="495.8" y1="290" x2="495.8" y2="298"/><line class="edge-dim" x1="496.6" y1="290" x2="496.6" y2="298"/><line class="edge-dim" x1="501.5" y1="290" x2="501.5" y2="298"/><line class="edge-dim" x1="502.2" y1="290" x2="502.2" y2="298"/><line class="edge-dim" x1="504.4" y1="290" x2="504.4" y2="298"/><line class="edge-dim" x1="509.4" y1="290" x2="509.4" y2="298"/><line class="edge-dim" x1="518.6" y1="290" x2="518.6" y2="298"/><line class="edge-dim" x1="520.7" y1="290" x2="520.7" y2="298"/><line class="edge-dim" x1="524.3" y1="290" x2="524.3" y2="298"/><line class="edge-dim" x1="528.6" y1="290" x2="528.6" y2="298"/><line class="edge-dim" x1="530.0" y1="290" x2="530.0" y2="298"/><line class="edge-dim" x1="532.1" y1="290" x2="532.1" y2="298"/><line class="edge-dim" x1="532.1" y1="290" x2="532.1" y2="298"/><line class="edge-dim" x1="532.8" y1="290" x2="532.8" y2="298"/><line class="edge-dim" x1="533.5" y1="290" x2="533.5" y2="298"/><line class="edge-dim" x1="534.2" y1="290" x2="534.2" y2="298"/><line class="edge-dim" x1="535.0" y1="290" x2="535.0" y2="298"/><line class="edge-dim" x1="535.7" y1="290" x2="535.7" y2="298"/><line class="edge-dim" x1="536.4" y1="290" x2="536.4" y2="298"/><line class="edge-dim" x1="537.1" y1="290" x2="537.1" y2="298"/><line class="edge-dim" x1="537.8" y1="290" x2="537.8" y2="298"/><line class="edge-dim" x1="539.2" y1="290" x2="539.2" y2="298"/><line class="edge-dim" x1="541.4" y1="290" x2="541.4" y2="298"/><line class="edge-dim" x1="542.1" y1="290" x2="542.1" y2="298"/><line class="edge-dim" x1="542.8" y1="290" x2="542.8" y2="298"/><line class="edge-dim" x1="543.5" y1="290" x2="543.5" y2="298"/><line class="edge-dim" x1="544.9" y1="290" x2="544.9" y2="298"/><line class="edge-dim" x1="551.3" y1="290" x2="551.3" y2="298"/><line class="edge-dim" x1="552.0" y1="290" x2="552.0" y2="298"/><line class="edge-dim" x1="552.7" y1="290" x2="552.7" y2="298"/><line class="edge-dim" x1="553.4" y1="290" x2="553.4" y2="298"/><line class="edge-dim" x1="553.4" y1="290" x2="553.4" y2="298"/><line class="edge-dim" x1="554.2" y1="290" x2="554.2" y2="298"/><line class="edge-dim" x1="554.9" y1="290" x2="554.9" y2="298"/><line class="edge-dim" x1="556.3" y1="290" x2="556.3" y2="298"/><line class="edge-dim" x1="556.3" y1="290" x2="556.3" y2="298"/><line class="edge-dim" x1="557.7" y1="290" x2="557.7" y2="298"/><line class="edge-dim" x1="558.4" y1="290" x2="558.4" y2="298"/><line class="edge-dim" x1="559.1" y1="290" x2="559.1" y2="298"/><line class="edge-dim" x1="559.8" y1="290" x2="559.8" y2="298"/><line class="edge-dim" x1="559.8" y1="290" x2="559.8" y2="298"/><line class="edge-dim" x1="560.6" y1="290" x2="560.6" y2="298"/><line class="edge-dim" x1="560.6" y1="290" x2="560.6" y2="298"/><line class="edge-dim" x1="560.6" y1="290" x2="560.6" y2="298"/><line class="edge-dim" x1="561.3" y1="290" x2="561.3" y2="298"/><line class="edge-dim" x1="562.0" y1="290" x2="562.0" y2="298"/><line class="edge-dim" x1="562.7" y1="290" x2="562.7" y2="298"/><line class="edge-dim" x1="563.4" y1="290" x2="563.4" y2="298"/><line class="edge-dim" x1="564.1" y1="290" x2="564.1" y2="298"/><line class="edge-dim" x1="565.5" y1="290" x2="565.5" y2="298"/><line class="edge-dim" x1="566.2" y1="290" x2="566.2" y2="298"/><line class="edge-dim" x1="566.2" y1="290" x2="566.2" y2="298"/><line class="edge-dim" x1="567.7" y1="290" x2="567.7" y2="298"/><line class="edge-dim" x1="567.7" y1="290" x2="567.7" y2="298"/><line class="edge-dim" x1="570.5" y1="290" x2="570.5" y2="298"/><line class="edge-dim" x1="571.9" y1="290" x2="571.9" y2="298"/><line class="edge-dim" x1="574.1" y1="290" x2="574.1" y2="298"/><line class="edge-dim" x1="577.6" y1="290" x2="577.6" y2="298"/><line class="edge-dim" x1="577.6" y1="290" x2="577.6" y2="298"/><line class="edge-dim" x1="579.0" y1="290" x2="579.0" y2="298"/><line class="edge-dim" x1="580.5" y1="290" x2="580.5" y2="298"/><line class="edge-dim" x1="581.9" y1="290" x2="581.9" y2="298"/><line class="edge-dim" x1="581.9" y1="290" x2="581.9" y2="298"/><line class="edge-dim" x1="584.7" y1="290" x2="584.7" y2="298"/><line class="edge-dim" x1="584.7" y1="290" x2="584.7" y2="298"/><line class="edge-dim" x1="584.7" y1="290" x2="584.7" y2="298"/><line class="edge-dim" x1="587.6" y1="290" x2="587.6" y2="298"/><line class="edge-dim" x1="589.0" y1="290" x2="589.0" y2="298"/><line class="edge-dim" x1="590.4" y1="290" x2="590.4" y2="298"/><line class="edge-dim" x1="590.4" y1="290" x2="590.4" y2="298"/><line class="edge-dim" x1="593.3" y1="290" x2="593.3" y2="298"/><line class="edge-dim" x1="596.1" y1="290" x2="596.1" y2="298"/><line class="edge-dim" x1="598.9" y1="290" x2="598.9" y2="298"/><line class="edge-dim" x1="600.4" y1="290" x2="600.4" y2="298"/><line class="edge-dim" x1="601.8" y1="290" x2="601.8" y2="298"/><line class="edge-dim" x1="601.8" y1="290" x2="601.8" y2="298"/><line class="edge-dim" x1="601.8" y1="290" x2="601.8" y2="298"/><line class="edge-dim" x1="607.5" y1="290" x2="607.5" y2="298"/><line class="edge-dim" x1="610.3" y1="290" x2="610.3" y2="298"/><line class="edge-dim" x1="613.2" y1="290" x2="613.2" y2="298"/><line class="edge-dim" x1="613.2" y1="290" x2="613.2" y2="298"/><line class="edge-dim" x1="616.0" y1="290" x2="616.0" y2="298"/><polyline class="l1" points="60.0,286.6 60.7,283.1 61.4,279.7 62.1,276.2 62.8,272.8 63.6,269.4 64.3,265.9 65.0,262.5 65.7,259.1 66.4,255.6 67.1,255.6 67.8,252.2 68.5,252.2 69.2,252.2 70.0,252.2 70.7,248.8 71.4,245.3 72.1,248.8 72.8,245.3 73.5,241.9 74.2,241.9 74.9,241.9 75.6,241.9 76.4,241.9 77.1,241.9 77.8,245.3 78.5,241.9 79.2,238.4 79.9,235.0 80.6,235.0 81.3,231.6 82.0,228.1 82.8,228.1 83.5,224.7 84.2,228.1 84.9,224.7 85.6,221.2 86.3,217.8 87.0,214.4 87.7,210.9 88.4,210.9 89.2,210.9 89.9,210.9 90.6,210.9 91.3,210.9 92.0,207.5 92.7,207.5 93.4,210.9 94.1,210.9 94.8,217.8 95.6,224.7 96.3,221.2 97.0,221.2 97.7,224.7 98.4,228.1 99.1,228.1 99.8,228.1 100.5,228.1 101.2,228.1 101.9,228.1 102.7,228.1 103.4,228.1 104.1,228.1 104.8,231.6 105.5,228.1 106.2,235.0 106.9,238.4 107.6,238.4 108.3,238.4 109.1,238.4 109.8,238.4 110.5,238.4 111.2,238.4 111.9,238.4 112.6,241.9 113.3,235.0 114.0,238.4 114.7,238.4 115.5,238.4 116.2,241.9 116.9,241.9 117.6,245.3 118.3,248.8 119.0,248.8 119.7,248.8 120.4,248.8 121.1,248.8 121.9,241.9 122.6,245.3 123.3,245.3 124.0,245.3 124.7,248.8 125.4,248.8 126.1,248.8 126.8,248.8 127.5,248.8 128.3,248.8 129.0,252.2 129.7,252.2 130.4,252.2 131.1,252.2 131.8,252.2 132.5,255.6 133.2,255.6 133.9,252.2 134.7,252.2 135.4,252.2 136.1,252.2 136.8,252.2 137.5,252.2 138.2,248.8 138.9,252.2 139.6,252.2 140.3,252.2 141.1,255.6 141.8,241.9 142.5,241.9 143.2,245.3 143.9,245.3 144.6,245.3 145.3,238.4 146.0,238.4 146.7,238.4 147.5,241.9 148.2,245.3 148.9,245.3 149.6,241.9 150.3,241.9 151.0,241.9 151.7,245.3 152.4,248.8 153.1,252.2 153.9,241.9 154.6,241.9 155.3,241.9 156.0,241.9 156.7,241.9 157.4,245.3 158.1,245.3 158.8,248.8 159.5,252.2 160.3,252.2 161.0,252.2 161.7,241.9 162.4,228.1 163.1,231.6 163.8,235.0 164.5,241.9 165.2,241.9 165.9,241.9 166.7,245.3 167.4,245.3 168.1,245.3 168.8,248.8 169.5,248.8 170.2,252.2 170.9,252.2 171.6,252.2 172.3,252.2 173.1,255.6 173.8,255.6 174.5,248.8 175.2,252.2 175.9,255.6 176.6,255.6 177.3,255.6 178.0,255.6 178.7,255.6 179.4,255.6 180.2,259.1 180.9,259.1 181.6,259.1 182.3,262.5 183.0,262.5 183.7,262.5 184.4,262.5 185.1,262.5 185.8,262.5 186.6,262.5 187.3,262.5 188.0,262.5 188.7,262.5 189.4,262.5 190.1,265.9 190.8,265.9 191.5,265.9 192.2,265.9 193.0,255.6 193.7,259.1 194.4,259.1 195.1,259.1 195.8,259.1 196.5,259.1 197.2,259.1 197.9,262.5 198.6,262.5 199.4,262.5 200.1,262.5 200.8,265.9 201.5,265.9 202.2,265.9 202.9,265.9 203.6,265.9 204.3,265.9 205.0,265.9 205.8,265.9 206.5,265.9 207.2,265.9 207.9,265.9 208.6,231.6 209.3,238.4 210.0,238.4 210.7,238.4 211.4,241.9 212.2,241.9 212.9,241.9 213.6,241.9 214.3,245.3 215.0,245.3 215.7,245.3 216.4,248.8 217.1,248.8 217.8,248.8 218.6,221.2 219.3,228.1 220.0,228.1 220.7,235.0 221.4,238.4 222.1,241.9 222.8,241.9 223.5,241.9 224.2,245.3 225.0,245.3 225.7,245.3 226.4,231.6 227.1,235.0 227.8,238.4 228.5,238.4 229.2,238.4 229.9,241.9 230.6,241.9 231.4,245.3 232.1,248.8 232.8,248.8 233.5,248.8 234.2,248.8 234.9,248.8 235.6,252.2 236.3,252.2 237.0,252.2 237.8,248.8 238.5,248.8 239.2,252.2 239.9,252.2 240.6,252.2 241.3,252.2 242.0,255.6 242.7,252.2 243.4,255.6 244.2,259.1 244.9,259.1 245.6,259.1 246.3,245.3 247.0,248.8 247.7,245.3 248.4,245.3 249.1,245.3 249.8,245.3 250.6,235.0 251.3,235.0 252.0,238.4 252.7,238.4 253.4,241.9 254.1,241.9 254.8,238.4 255.5,241.9 256.2,241.9 256.9,245.3 257.7,245.3 258.4,241.9 259.1,245.3 259.8,245.3 260.5,231.6 261.2,231.6 261.9,238.4 262.6,238.4 263.3,238.4 264.1,231.6 264.8,235.0 265.5,238.4 266.2,238.4 266.9,241.9 267.6,241.9 268.3,245.3 269.0,245.3 269.7,245.3 270.5,248.8 271.2,248.8 271.9,241.9 272.6,241.9 273.3,248.8 274.0,248.8 274.7,248.8 275.4,248.8 276.1,248.8 276.9,241.9 277.6,245.3 278.3,248.8 279.0,252.2 279.7,252.2 280.4,252.2 281.1,255.6 281.8,255.6 282.5,255.6 283.3,255.6 284.0,252.2 284.7,255.6 285.4,255.6 286.1,255.6 286.8,255.6 287.5,255.6 288.2,248.8 288.9,248.8 289.7,255.6 290.4,255.6 291.1,259.1 291.8,259.1 292.5,259.1 293.2,248.8 293.9,241.9 294.6,245.3 295.3,248.8 296.1,248.8 296.8,248.8 297.5,245.3 298.2,245.3 298.9,245.3 299.6,248.8 300.3,248.8 301.0,245.3 301.7,245.3 302.5,248.8 303.2,248.8 303.9,248.8 304.6,252.2 305.3,252.2 306.0,252.2 306.7,252.2 307.4,252.2 308.1,252.2 308.9,252.2 309.6,252.2 310.3,252.2 311.0,252.2 311.7,252.2 312.4,252.2 313.1,252.2 313.8,255.6 314.5,255.6 315.3,255.6 316.0,255.6 316.7,255.6 317.4,255.6 318.1,255.6 318.8,255.6 319.5,255.6 320.2,255.6 320.9,255.6 321.7,255.6 322.4,259.1 323.1,259.1 323.8,259.1 324.5,259.1 325.2,262.5 325.9,262.5 326.6,262.5 327.3,262.5 328.1,265.9 328.8,265.9 329.5,265.9 330.2,265.9 330.9,259.1 331.6,259.1 332.3,262.5 333.0,262.5 333.7,262.5 334.4,248.8 335.2,248.8 335.9,252.2 336.6,255.6 337.3,255.6 338.0,259.1 338.7,259.1 339.4,259.1 340.1,259.1 340.8,262.5 341.6,262.5 342.3,262.5 343.0,262.5 343.7,262.5 344.4,262.5 345.1,262.5 345.8,262.5 346.5,259.1 347.2,259.1 348.0,262.5 348.7,262.5 349.4,262.5 350.1,265.9 350.8,265.9 351.5,265.9 352.2,265.9 352.9,265.9 353.6,265.9 354.4,265.9 355.1,265.9 355.8,265.9 356.5,231.6 357.2,238.4 357.9,238.4 358.6,238.4 359.3,241.9 360.0,241.9 360.8,245.3 361.5,248.8 362.2,248.8 362.9,248.8 363.6,252.2 364.3,252.2 365.0,252.2 365.7,252.2 366.4,255.6 367.2,255.6 367.9,228.1 368.6,228.1 369.3,228.1 370.0,231.6 370.7,238.4 371.4,238.4 372.1,238.4 372.8,241.9 373.6,241.9 374.3,224.7 375.0,228.1 375.7,231.6 376.4,238.4 377.1,241.9 377.8,241.9 378.5,241.9 379.2,245.3 380.0,245.3 380.7,245.3 381.4,241.9 382.1,241.9 382.8,241.9 383.5,245.3 384.2,248.8 384.9,248.8 385.6,228.1 386.4,231.6 387.1,235.0 387.8,235.0 388.5,238.4 389.2,238.4 389.9,235.0 390.6,238.4 391.3,238.4 392.0,231.6 392.8,235.0 393.5,235.0 394.2,238.4 394.9,238.4 395.6,241.9 396.3,241.9 397.0,245.3 397.7,248.8 398.4,248.8 399.2,248.8 399.9,248.8 400.6,252.2 401.3,252.2 402.0,248.8 402.7,248.8 403.4,217.8 404.1,221.2 404.8,224.7 405.6,231.6 406.3,235.0 407.0,231.6 407.7,235.0 408.4,238.4 409.1,238.4 409.8,241.9 410.5,241.9 411.2,241.9 411.9,245.3 412.7,245.3 413.4,245.3 414.1,248.8 414.8,238.4 415.5,241.9 416.2,241.9 416.9,245.3 417.6,248.8 418.3,248.8 419.1,248.8 419.8,245.3 420.5,245.3 421.2,248.8 421.9,248.8 422.6,252.2 423.3,252.2 424.0,252.2 424.7,238.4 425.5,228.1 426.2,231.6 426.9,231.6 427.6,231.6 428.3,238.4 429.0,238.4 429.7,238.4 430.4,238.4 431.1,238.4 431.9,228.1 432.6,231.6 433.3,231.6 434.0,231.6 434.7,231.6 435.4,231.6 436.1,235.0 436.8,238.4 437.5,238.4 438.3,235.0 439.0,238.4 439.7,241.9 440.4,245.3 441.1,224.7 441.8,228.1 442.5,231.6 443.2,235.0 443.9,235.0 444.7,235.0 445.4,238.4 446.1,238.4 446.8,238.4 447.5,241.9 448.2,241.9 448.9,241.9 449.6,241.9 450.3,245.3 451.1,245.3 451.8,231.6 452.5,231.6 453.2,235.0 453.9,235.0 454.6,235.0 455.3,238.4 456.0,241.9 456.7,241.9 457.5,241.9 458.2,241.9 458.9,241.9 459.6,235.0 460.3,235.0 461.0,235.0 461.7,224.7 462.4,217.8 463.1,224.7 463.9,224.7 464.6,210.9 465.3,207.5 466.0,207.5 466.7,214.4 467.4,217.8 468.1,221.2 468.8,221.2 469.5,214.4 470.3,217.8 471.0,217.8 471.7,217.8 472.4,217.8 473.1,224.7 473.8,224.7 474.5,228.1 475.2,228.1 475.9,231.6 476.7,231.6 477.4,231.6 478.1,231.6 478.8,235.0 479.5,235.0 480.2,235.0 480.9,238.4 481.6,238.4 482.3,238.4 483.1,238.4 483.8,238.4 484.5,241.9 485.2,241.9 485.9,245.3 486.6,245.3 487.3,245.3 488.0,245.3 488.7,245.3 489.4,248.8 490.2,248.8 490.9,248.8 491.6,252.2 492.3,252.2 493.0,252.2 493.7,252.2 494.4,252.2 495.1,252.2 495.8,255.6 496.6,255.6 497.3,255.6 498.0,255.6 498.7,255.6 499.4,255.6 500.1,255.6 500.8,255.6 501.5,259.1 502.2,259.1 503.0,259.1 503.7,255.6 504.4,259.1 505.1,259.1 505.8,259.1 506.5,259.1 507.2,259.1 507.9,259.1 508.6,259.1 509.4,262.5 510.1,262.5 510.8,262.5 511.5,262.5 512.2,262.5 512.9,262.5 513.6,262.5 514.3,262.5 515.0,262.5 515.8,259.1 516.5,252.2 517.2,252.2 517.9,252.2 518.6,255.6 519.3,255.6 520.0,255.6 520.7,259.1 521.4,259.1 522.2,255.6 522.9,255.6 523.6,255.6 524.3,259.1 525.0,259.1 525.7,259.1 526.4,259.1 527.1,259.1 527.8,259.1 528.6,252.2 529.3,252.2 530.0,255.6 530.7,255.6 531.4,241.9 532.1,248.8 532.8,252.2 533.5,255.6 534.2,248.8 535.0,248.8 535.7,248.8 536.4,248.8 537.1,248.8 537.8,245.3 538.5,245.3 539.2,248.8 539.9,248.8 540.6,248.8 541.4,252.2 542.1,238.4 542.8,241.9 543.5,238.4 544.2,238.4 544.9,241.9 545.6,241.9 546.3,241.9 547.0,241.9 547.8,241.9 548.5,245.3 549.2,245.3 549.9,241.9 550.6,241.9 551.3,245.3 552.0,228.1 552.7,231.6 553.4,238.4 554.2,241.9 554.9,245.3 555.6,235.0 556.3,241.9 557.0,217.8 557.7,207.5 558.4,210.9 559.1,204.1 559.8,210.9 560.6,217.8 561.3,214.4 562.0,217.8 562.7,217.8 563.4,217.8 564.1,221.2 564.8,221.2 565.5,224.7 566.2,231.6 566.9,228.1 567.7,235.0 568.4,235.0 569.1,235.0 569.8,235.0 570.5,238.4 571.2,238.4 571.9,241.9 572.6,241.9 573.3,241.9 574.1,245.3 574.8,238.4 575.5,238.4 576.2,238.4 576.9,238.4 577.6,245.3 578.3,245.3 579.0,248.8 579.7,245.3 580.5,248.8 581.2,248.8 581.9,235.0 582.6,235.0 583.3,235.0 584.0,224.7 584.7,235.0 585.4,235.0 586.1,235.0 586.9,235.0 587.6,231.6 588.3,231.6 589.0,235.0 589.7,235.0 590.4,241.9 591.1,241.9 591.8,241.9 592.5,241.9 593.3,245.3 594.0,245.3 594.7,245.3 595.4,245.3 596.1,248.8 596.8,248.8 597.5,248.8 598.2,248.8 598.9,252.2 599.7,252.2 600.4,255.6 601.1,255.6 601.8,248.8 602.5,248.8 603.2,241.9 603.9,241.9 604.6,241.9 605.3,245.3 606.1,245.3 606.8,245.3 607.5,248.8 608.2,248.8 608.9,248.8 609.6,248.8 610.3,252.2 611.0,252.2 611.7,252.2 612.5,252.2 613.2,252.2 613.9,252.2 614.6,252.2 615.3,252.2 616.0,255.6 616.7,248.8 617.4,248.8 618.1,248.8 618.9,248.8 619.6,248.8 620.3,252.2 621.0,252.2 621.7,252.2 622.4,252.2 623.1,252.2 623.8,252.2 624.5,255.6 625.3,255.6 626.0,255.6 626.7,255.6 627.4,255.6 628.1,259.1 628.8,259.1 629.5,259.1 630.2,259.1 630.9,259.1 631.7,259.1 632.4,259.1 633.1,259.1 633.8,262.5 634.5,265.9 635.2,265.9 635.9,269.4 636.6,269.4 637.3,269.4 638.1,269.4 638.8,269.4 639.5,269.4 640.2,269.4 640.9,272.8 641.6,272.8 642.3,272.8 643.0,272.8 643.7,272.8 644.4,272.8 645.2,272.8 645.9,272.8 646.6,272.8 647.3,272.8 648.0,272.8 648.7,272.8 649.4,272.8 650.1,272.8 650.8,272.8 651.6,272.8 652.3,272.8 653.0,272.8 653.7,272.8 654.4,272.8 655.1,272.8 655.8,272.8 656.5,272.8 657.2,272.8 658.0,272.8 658.7,272.8 659.4,272.8 660.1,272.8 660.8,276.2 661.5,276.2 662.2,276.2 662.9,276.2 663.6,279.7 664.4,279.7 665.1,279.7 665.8,279.7 666.5,279.7 667.2,279.7 667.9,279.7 668.6,279.7 669.3,279.7 670.0,279.7 670.8,279.7 671.5,279.7 672.2,279.7 672.9,279.7 673.6,279.7 674.3,279.7 675.0,279.7 675.7,279.7 676.4,279.7 677.2,283.1 677.9,283.1 678.6,283.1 679.3,283.1 680.0,286.6"/><polyline class="l3" points="60.0,73.4 60.7,76.9 61.4,80.3 62.1,87.2 62.8,94.1 63.6,104.4 64.3,111.2 65.0,114.7 65.7,125.0 66.4,125.0 67.1,131.9 67.8,135.3 68.5,138.8 69.2,135.3 70.0,142.2 70.7,152.5 71.4,142.2 72.1,149.1 72.8,159.4 73.5,152.5 74.2,152.5 74.9,159.4 75.6,169.7 76.4,166.2 77.1,159.4 77.8,162.8 78.5,169.7 79.2,180.0 79.9,183.4 80.6,190.3 81.3,200.6 82.0,204.1 82.8,214.4 83.5,214.4 84.2,228.1 84.9,235.0 85.6,238.4 86.3,248.8 87.0,265.9 87.7,262.5 88.4,262.5 89.2,259.1 89.9,259.1 90.6,259.1 91.3,269.4 92.0,272.8 92.7,286.6 93.4,286.6 94.1,286.6 94.8,290.0 95.6,276.2 96.3,290.0 97.0,290.0 97.7,286.6 98.4,286.6 99.1,276.2 99.8,286.6 100.5,286.6 101.2,290.0 101.9,276.2 102.7,286.6 103.4,286.6 104.1,290.0 104.8,269.4 105.5,290.0 106.2,286.6 106.9,286.6 107.6,286.6 108.3,286.6 109.1,269.4 109.8,286.6 110.5,286.6 111.2,290.0 111.9,290.0 112.6,262.5 113.3,283.1 114.0,286.6 114.7,286.6 115.5,290.0 116.2,283.1 116.9,283.1 117.6,283.1 118.3,279.7 119.0,279.7 119.7,279.7 120.4,265.9 121.1,262.5 121.9,290.0 122.6,286.6 123.3,286.6 124.0,290.0 124.7,283.1 125.4,286.6 126.1,286.6 126.8,290.0 127.5,290.0 128.3,290.0 129.0,262.5 129.7,286.6 130.4,290.0 131.1,290.0 131.8,290.0 132.5,279.7 133.2,259.1 133.9,286.6 134.7,286.6 135.4,290.0 136.1,290.0 136.8,290.0 137.5,269.4 138.2,290.0 138.9,286.6 139.6,286.6 140.3,290.0 141.1,262.5 141.8,290.0 142.5,290.0 143.2,286.6 143.9,290.0 144.6,265.9 145.3,286.6 146.0,286.6 146.7,290.0 147.5,290.0 148.2,286.6 148.9,272.8 149.6,290.0 150.3,290.0 151.0,290.0 151.7,286.6 152.4,290.0 153.1,259.1 153.9,286.6 154.6,279.7 155.3,290.0 156.0,290.0 156.7,290.0 157.4,286.6 158.1,290.0 158.8,290.0 159.5,286.6 160.3,286.6 161.0,262.5 161.7,265.9 162.4,290.0 163.1,286.6 163.8,290.0 164.5,286.6 165.2,286.6 165.9,290.0 166.7,286.6 167.4,279.7 168.1,290.0 168.8,286.6 169.5,279.7 170.2,286.6 170.9,290.0 171.6,290.0 172.3,290.0 173.1,283.1 173.8,265.9 174.5,290.0 175.2,290.0 175.9,286.6 176.6,286.6 177.3,286.6 178.0,290.0 178.7,290.0 179.4,290.0 180.2,283.1 180.9,286.6 181.6,290.0 182.3,279.7 183.0,279.7 183.7,279.7 184.4,279.7 185.1,279.7 185.8,279.7 186.6,286.6 187.3,272.8 188.0,286.6 188.7,286.6 189.4,290.0 190.1,276.2 190.8,276.2 191.5,276.2 192.2,241.9 193.0,286.6 193.7,286.6 194.4,286.6 195.1,286.6 195.8,286.6 196.5,286.6 197.2,286.6 197.9,286.6 198.6,290.0 199.4,290.0 200.1,290.0 200.8,279.7 201.5,279.7 202.2,279.7 202.9,279.7 203.6,279.7 204.3,286.6 205.0,290.0 205.8,290.0 206.5,290.0 207.2,290.0 207.9,207.5 208.6,272.8 209.3,286.6 210.0,279.7 210.7,290.0 211.4,286.6 212.2,286.6 212.9,290.0 213.6,290.0 214.3,283.1 215.0,283.1 215.7,290.0 216.4,290.0 217.1,283.1 217.8,235.0 218.6,290.0 219.3,286.6 220.0,290.0 220.7,290.0 221.4,286.6 222.1,286.6 222.8,286.6 223.5,286.6 224.2,283.1 225.0,283.1 225.7,255.6 226.4,290.0 227.1,290.0 227.8,279.7 228.5,286.6 229.2,290.0 229.9,286.6 230.6,290.0 231.4,286.6 232.1,283.1 232.8,286.6 233.5,290.0 234.2,276.2 234.9,286.6 235.6,283.1 236.3,283.1 237.0,265.9 237.8,286.6 238.5,290.0 239.2,286.6 239.9,286.6 240.6,290.0 241.3,290.0 242.0,265.9 242.7,290.0 243.4,290.0 244.2,279.7 244.9,279.7 245.6,248.8 246.3,290.0 247.0,272.8 247.7,286.6 248.4,286.6 249.1,286.6 249.8,228.1 250.6,290.0 251.3,290.0 252.0,286.6 252.7,290.0 253.4,286.6 254.1,269.4 254.8,290.0 255.5,290.0 256.2,290.0 256.9,290.0 257.7,269.4 258.4,290.0 259.1,286.6 259.8,255.6 260.5,290.0 261.2,283.1 261.9,290.0 262.6,290.0 263.3,272.8 264.1,290.0 264.8,290.0 265.5,286.6 266.2,290.0 266.9,290.0 267.6,290.0 268.3,286.6 269.0,286.6 269.7,290.0 270.5,286.6 271.2,262.5 271.9,286.6 272.6,290.0 273.3,276.2 274.0,286.6 274.7,286.6 275.4,286.6 276.1,272.8 276.9,290.0 277.6,290.0 278.3,290.0 279.0,272.8 279.7,290.0 280.4,290.0 281.1,283.1 281.8,286.6 282.5,286.6 283.3,272.8 284.0,290.0 284.7,290.0 285.4,290.0 286.1,290.0 286.8,290.0 287.5,272.8 288.2,290.0 288.9,290.0 289.7,286.6 290.4,286.6 291.1,286.6 291.8,286.6 292.5,259.1 293.2,269.4 293.9,290.0 294.6,290.0 295.3,276.2 296.1,290.0 296.8,283.1 297.5,290.0 298.2,290.0 298.9,290.0 299.6,290.0 300.3,265.9 301.0,283.1 301.7,276.2 302.5,286.6 303.2,286.6 303.9,290.0 304.6,286.6 305.3,245.3 306.0,265.9 306.7,269.4 307.4,269.4 308.1,269.4 308.9,272.8 309.6,272.8 310.3,272.8 311.0,276.2 311.7,276.2 312.4,276.2 313.1,262.5 313.8,272.8 314.5,272.8 315.3,276.2 316.0,283.1 316.7,283.1 317.4,283.1 318.1,286.6 318.8,286.6 319.5,286.6 320.2,290.0 320.9,290.0 321.7,290.0 322.4,279.7 323.1,279.7 323.8,279.7 324.5,283.1 325.2,276.2 325.9,262.5 326.6,269.4 327.3,269.4 328.1,269.4 328.8,269.4 329.5,272.8 330.2,255.6 330.9,290.0 331.6,290.0 332.3,286.6 333.0,286.6 333.7,255.6 334.4,286.6 335.2,283.1 335.9,290.0 336.6,290.0 337.3,290.0 338.0,283.1 338.7,286.6 339.4,286.6 340.1,286.6 340.8,286.6 341.6,286.6 342.3,286.6 343.0,279.7 343.7,286.6 344.4,286.6 345.1,286.6 345.8,265.9 346.5,286.6 347.2,286.6 348.0,283.1 348.7,286.6 349.4,290.0 350.1,283.1 350.8,283.1 351.5,283.1 352.2,290.0 352.9,290.0 353.6,290.0 354.4,290.0 355.1,290.0 355.8,221.2 356.5,290.0 357.2,290.0 357.9,290.0 358.6,290.0 359.3,283.1 360.0,290.0 360.8,286.6 361.5,286.6 362.2,286.6 362.9,290.0 363.6,290.0 364.3,283.1 365.0,279.7 365.7,290.0 366.4,286.6 367.2,235.0 367.9,290.0 368.6,290.0 369.3,290.0 370.0,283.1 370.7,286.6 371.4,290.0 372.1,290.0 372.8,290.0 373.6,248.8 374.3,286.6 375.0,290.0 375.7,290.0 376.4,290.0 377.1,286.6 377.8,290.0 378.5,290.0 379.2,283.1 380.0,283.1 380.7,265.9 381.4,286.6 382.1,286.6 382.8,290.0 383.5,286.6 384.2,283.1 384.9,241.9 385.6,290.0 386.4,286.6 387.1,290.0 387.8,290.0 388.5,286.6 389.2,279.7 389.9,290.0 390.6,290.0 391.3,269.4 392.0,290.0 392.8,286.6 393.5,286.6 394.2,286.6 394.9,290.0 395.6,286.6 396.3,286.6 397.0,290.0 397.7,286.6 398.4,290.0 399.2,290.0 399.9,290.0 400.6,283.1 401.3,265.9 402.0,286.6 402.7,231.6 403.4,290.0 404.1,290.0 404.8,290.0 405.6,290.0 406.3,279.7 407.0,276.2 407.7,286.6 408.4,286.6 409.1,286.6 409.8,286.6 410.5,286.6 411.2,290.0 411.9,286.6 412.7,286.6 413.4,290.0 414.1,262.5 414.8,290.0 415.5,286.6 416.2,290.0 416.9,290.0 417.6,286.6 418.3,286.6 419.1,265.9 419.8,286.6 420.5,290.0 421.2,290.0 421.9,290.0 422.6,283.1 423.3,283.1 424.0,252.2 424.7,255.6 425.5,286.6 426.2,286.6 426.9,286.6 427.6,290.0 428.3,279.7 429.0,290.0 429.7,290.0 430.4,283.1 431.1,255.6 431.9,286.6 432.6,283.1 433.3,286.6 434.0,279.7 434.7,276.2 435.4,290.0 436.1,290.0 436.8,286.6 437.5,272.8 438.3,286.6 439.0,290.0 439.7,290.0 440.4,235.0 441.1,290.0 441.8,290.0 442.5,286.6 443.2,276.2 443.9,286.6 444.7,279.7 445.4,269.4 446.1,286.6 446.8,290.0 447.5,279.7 448.2,283.1 448.9,283.1 449.6,286.6 450.3,286.6 451.1,241.9 451.8,283.1 452.5,276.2 453.2,283.1 453.9,286.6 454.6,286.6 455.3,286.6 456.0,286.6 456.7,286.6 457.5,286.6 458.2,276.2 458.9,269.4 459.6,290.0 460.3,290.0 461.0,255.6 461.7,272.8 462.4,290.0 463.1,283.1 463.9,262.5 464.6,269.4 465.3,276.2 466.0,283.1 466.7,283.1 467.4,286.6 468.1,286.6 468.8,259.1 469.5,290.0 470.3,290.0 471.0,283.1 471.7,286.6 472.4,286.6 473.1,276.2 473.8,290.0 474.5,286.6 475.2,290.0 475.9,276.2 476.7,283.1 477.4,283.1 478.1,290.0 478.8,272.8 479.5,286.6 480.2,290.0 480.9,283.1 481.6,286.6 482.3,286.6 483.1,286.6 483.8,286.6 484.5,286.6 485.2,290.0 485.9,283.1 486.6,286.6 487.3,290.0 488.0,290.0 488.7,290.0 489.4,283.1 490.2,286.6 490.9,290.0 491.6,279.7 492.3,279.7 493.0,283.1 493.7,283.1 494.4,283.1 495.1,283.1 495.8,262.5 496.6,279.7 497.3,279.7 498.0,283.1 498.7,286.6 499.4,286.6 500.1,286.6 500.8,286.6 501.5,276.2 502.2,279.7 503.0,259.1 503.7,290.0 504.4,279.7 505.1,279.7 505.8,279.7 506.5,279.7 507.2,286.6 507.9,290.0 508.6,290.0 509.4,276.2 510.1,279.7 510.8,279.7 511.5,279.7 512.2,279.7 512.9,283.1 513.6,286.6 514.3,286.6 515.0,259.1 515.8,255.6 516.5,290.0 517.2,290.0 517.9,290.0 518.6,283.1 519.3,286.6 520.0,286.6 520.7,283.1 521.4,265.9 522.2,290.0 522.9,290.0 523.6,290.0 524.3,283.1 525.0,286.6 525.7,286.6 526.4,286.6 527.1,286.6 527.8,259.1 528.6,290.0 529.3,290.0 530.0,283.1 530.7,259.1 531.4,290.0 532.1,286.6 532.8,290.0 533.5,265.9 534.2,286.6 535.0,286.6 535.7,279.7 536.4,286.6 537.1,272.8 537.8,283.1 538.5,283.1 539.2,286.6 539.9,290.0 540.6,290.0 541.4,252.2 542.1,279.7 542.8,262.5 543.5,290.0 544.2,290.0 544.9,286.6 545.6,286.6 546.3,286.6 547.0,286.6 547.8,283.1 548.5,283.1 549.2,272.8 549.9,286.6 550.6,290.0 551.3,255.6 552.0,290.0 552.7,290.0 553.4,290.0 554.2,279.7 554.9,265.9 555.6,290.0 556.3,245.3 557.0,265.9 557.7,290.0 558.4,276.2 559.1,290.0 559.8,283.1 560.6,276.2 561.3,290.0 562.0,279.7 562.7,283.1 563.4,290.0 564.1,290.0 564.8,290.0 565.5,286.6 566.2,269.4 566.9,290.0 567.7,286.6 568.4,286.6 569.1,290.0 569.8,283.1 570.5,286.6 571.2,286.6 571.9,286.6 572.6,286.6 573.3,290.0 574.1,262.5 574.8,286.6 575.5,286.6 576.2,286.6 576.9,290.0 577.6,290.0 578.3,290.0 579.0,272.8 579.7,290.0 580.5,286.6 581.2,252.2 581.9,286.6 582.6,286.6 583.3,269.4 584.0,290.0 584.7,290.0 585.4,290.0 586.1,290.0 586.9,262.5 587.6,283.1 588.3,283.1 589.0,290.0 589.7,290.0 590.4,290.0 591.1,290.0 591.8,290.0 592.5,290.0 593.3,286.6 594.0,286.6 594.7,286.6 595.4,286.6 596.1,290.0 596.8,290.0 597.5,290.0 598.2,290.0 598.9,283.1 599.7,283.1 600.4,279.7 601.1,231.6 601.8,286.6 602.5,269.4 603.2,286.6 603.9,286.6 604.6,279.7 605.3,283.1 606.1,276.2 606.8,290.0 607.5,272.8 608.2,286.6 608.9,290.0 609.6,290.0 610.3,276.2 611.0,276.2 611.7,286.6 612.5,259.1 613.2,290.0 613.9,290.0 614.6,290.0 615.3,290.0 616.0,252.2 616.7,286.6 617.4,286.6 618.1,286.6 618.9,286.6 619.6,265.9 620.3,265.9 621.0,269.4 621.7,272.8 622.4,272.8 623.1,283.1 623.8,259.1 624.5,269.4 625.3,269.4 626.0,269.4 626.7,269.4 627.4,241.9 628.1,248.8 628.8,248.8 629.5,248.8 630.2,248.8 630.9,248.8 631.7,248.8 632.4,252.2 633.1,238.4 633.8,204.1 634.5,210.9 635.2,200.6 635.9,200.6 636.6,200.6 637.3,200.6 638.1,200.6 638.8,200.6 639.5,204.1 640.2,166.2 640.9,166.2 641.6,166.2 642.3,166.2 643.0,166.2 643.7,169.7 644.4,173.1 645.2,173.1 645.9,176.6 646.6,180.0 647.3,180.0 648.0,180.0 648.7,180.0 649.4,180.0 650.1,180.0 650.8,183.4 651.6,183.4 652.3,183.4 653.0,183.4 653.7,183.4 654.4,183.4 655.1,186.9 655.8,190.3 656.5,190.3 657.2,193.8 658.0,197.2 658.7,197.2 659.4,197.2 660.1,166.2 660.8,166.2 661.5,166.2 662.2,169.7 662.9,145.6 663.6,145.6 664.4,145.6 665.1,145.6 665.8,145.6 666.5,149.1 667.2,152.5 667.9,152.5 668.6,155.9 669.3,155.9 670.0,155.9 670.8,155.9 671.5,155.9 672.2,155.9 672.9,155.9 673.6,155.9 674.3,155.9 675.0,155.9 675.7,155.9 676.4,125.0 677.2,125.0 677.9,128.4 678.6,128.4 679.3,94.1 680.0,70.0"/><text class="t-tick" x="60.0" y="314.0" text-anchor="middle">0</text><text class="t-tick" x="202.2" y="314.0" text-anchor="middle">200</text><text class="t-tick" x="344.4" y="314.0" text-anchor="middle">400</text><text class="t-tick" x="486.6" y="314.0" text-anchor="middle">600</text><text class="t-tick" x="628.8" y="314.0" text-anchor="middle">800</text><text class="t-tick" x="370.0" y="346.0" text-anchor="middle">step (ticks under the axis: a preemption)</text><rect class="s1" x="70.0" y="44.0" width="12.0" height="12.0" rx="2"/><text class="t-tick" x="88.0" y="54.0" text-anchor="start">running requests</text><rect class="s3" x="230.0" y="44.0" width="12.0" height="12.0" rx="2"/><text class="t-tick" x="248.0" y="54.0" text-anchor="start">free blocks</text></svg><figcaption>Our scheduler over 873 steps. The free blocks (green) soon fall to zero and stay near zero while the queue is long; each tick under the axis is one preemption. Only when the queue empties near the end do blocks come free.</figcaption></figure>

The traffic is far more than 64 blocks can serve, on purpose. Memory is full almost all the time, and the scheduler preempts 356 times. Still, every request gets every one of its tokens. In a simulation in steps, both methods give the same timeline. What differs is the cost of each preemption.

Swapping moved 705 blocks out and 705 back in. For OPT-13B, with 800 KB of cache per token, that is 18.48 GB over the CPU-GPU connection. At no time did CPU memory hold more than 24 blocks, well under the bound of 64 that the paper promises. Recomputation moved nothing, but computed 9,115 tokens again, in 356 prompt passes.

Which is cheaper? A simple model of the two costs helps:

$$
t_{\text{swap}} \approx \frac{\text{bytes}}{\text{bandwidth}} + n_{\text{blocks}} \cdot t_{\text{copy}}, \qquad t_{\text{recompute}} \approx t_{\text{prompt pass}}(n_{\text{tokens}})
$$

Read the left part first. Swapping pays for the bytes it moves, divided by the bandwidth. It also pays a fixed start-up cost $$t_{\text{copy}}$$ for every separate copy, and there is one copy per block. The right part says that recomputation costs one prompt pass over all the tokens, whatever the block size.

A tiny example: say the connection moves 32 GB/s. Then 64 MB takes 2 ms. As 4 blocks with a fixed cost of 0.1 ms each, it takes 2.4 ms. As 4,096 tiny blocks, the fixed costs alone add 409.6 ms. Small blocks make swapping slow.

Now the real thing. We take a request with a 14-token prompt and 200 written tokens and do both on OPT-125M. First we check that recomputation gives back the same cache. Then we time the three ways to get that cache on the laptop GPU:

```text
== 6. Swapping against recomputation on the real model (OPT-125M)
a request with a 14-token prompt and 200 written tokens: 213 tokens of KV cache
recomputed in one pass against built one token at a time: max difference 1.8e-05; next token after recomputation the same: True
laptop GPU (mps), FP16, fastest of several runs; 213 tokens = 7.85 MB of KV cache
  building it the first time, one pass per token:  1342.8 ms
  recomputation, one prompt pass:                     9.5 ms
  swap out + swap in, blocks of 16 tokens:            5.9 ms; round trip exact: True
  recomputation took 142 times less time than building the cache one token at a time
swap time against block size (the same 213 tokens; one copy per block):
  block size      1      2      4      8     16     32     64    128    256
  out ms      40.14  21.50   9.65   4.81   2.77   1.48   1.02   0.52   0.33
  in ms       46.75  19.37   9.18   4.99   2.84   1.49   0.92   0.52   0.33
  recompute    9.45 ms at every block size (it does not read the blocks)
  block size 1 means 213 copies each way: 0.19 ms per copy out; block size 256 means 1 copy
```

<figure class="fig"><svg viewBox="0 0 720 300" role="img" aria-label="Time to swap the 213-token cache out and in against block size, with the flat cost of recomputation. Small blocks make swapping slow."><defs><marker id="ah" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="arrow" d="M0,0L10,5L0,10z"/></marker><marker id="ah-on" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="6" markerHeight="6" orient="auto-start-reverse"><path class="arrow-on" d="M0,0L10,5L0,10z"/></marker><marker id="ah-2" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="6" markerHeight="6" orient="auto-start-reverse"><path class="arrow-2" d="M0,0L10,5L0,10z"/></marker></defs><line class="grid" x1="64" y1="250.0" x2="550" y2="250.0"/><text class="t-tick" x="56.0" y="254.0" text-anchor="end">0.0</text><line class="grid" x1="64" y1="206.0" x2="550" y2="206.0"/><text class="t-tick" x="56.0" y="210.0" text-anchor="end">10.0</text><line class="grid" x1="64" y1="162.0" x2="550" y2="162.0"/><text class="t-tick" x="56.0" y="166.0" text-anchor="end">20.0</text><line class="grid" x1="64" y1="118.0" x2="550" y2="118.0"/><text class="t-tick" x="56.0" y="122.0" text-anchor="end">30.0</text><line class="grid" x1="64" y1="74.0" x2="550" y2="74.0"/><text class="t-tick" x="56.0" y="78.0" text-anchor="end">40.0</text><line class="grid" x1="64" y1="30.0" x2="550" y2="30.0"/><text class="t-tick" x="56.0" y="34.0" text-anchor="end">50.0</text><text class="t-tick" x="64.0" y="270.0" text-anchor="middle">1</text><text class="t-tick" x="124.8" y="270.0" text-anchor="middle">2</text><text class="t-tick" x="185.5" y="270.0" text-anchor="middle">4</text><text class="t-tick" x="246.2" y="270.0" text-anchor="middle">8</text><text class="t-tick" x="307.0" y="270.0" text-anchor="middle">16</text><text class="t-tick" x="367.8" y="270.0" text-anchor="middle">32</text><text class="t-tick" x="428.5" y="270.0" text-anchor="middle">64</text><text class="t-tick" x="489.2" y="270.0" text-anchor="middle">128</text><text class="t-tick" x="550.0" y="270.0" text-anchor="middle">256</text><line class="axis" x1="64" y1="250" x2="550" y2="250"/><polyline class="l1" points="64.0,73.4 124.8,155.4 185.5,207.5 246.2,228.8 307.0,237.8 367.8,243.5 428.5,245.5 489.2,247.7 550.0,248.5"/><g class="mark"><title>swap out, 1: 40.1</title><circle class="s1 ring" cx="64.0" cy="73.4" r="5"/></g><g class="mark"><title>swap out, 2: 21.5</title><circle class="s1 ring" cx="124.8" cy="155.4" r="5"/></g><g class="mark"><title>swap out, 4: 9.7</title><circle class="s1 ring" cx="185.5" cy="207.5" r="5"/></g><g class="mark"><title>swap out, 8: 4.8</title><circle class="s1 ring" cx="246.2" cy="228.8" r="5"/></g><g class="mark"><title>swap out, 16: 2.8</title><circle class="s1 ring" cx="307.0" cy="237.8" r="5"/></g><g class="mark"><title>swap out, 32: 1.5</title><circle class="s1 ring" cx="367.8" cy="243.5" r="5"/></g><g class="mark"><title>swap out, 64: 1.0</title><circle class="s1 ring" cx="428.5" cy="245.5" r="5"/></g><g class="mark"><title>swap out, 128: 0.5</title><circle class="s1 ring" cx="489.2" cy="247.7" r="5"/></g><g class="mark"><title>swap out, 256: 0.3</title><circle class="s1 ring" cx="550.0" cy="248.5" r="5"/></g><polyline class="l2" points="64.0,44.3 124.8,164.8 185.5,209.6 246.2,228.0 307.0,237.5 367.8,243.4 428.5,246.0 489.2,247.7 550.0,248.5"/><g class="mark"><title>swap in, 1: 46.8</title><circle class="s2 ring" cx="64.0" cy="44.3" r="5"/></g><g class="mark"><title>swap in, 2: 19.4</title><circle class="s2 ring" cx="124.8" cy="164.8" r="5"/></g><g class="mark"><title>swap in, 4: 9.2</title><circle class="s2 ring" cx="185.5" cy="209.6" r="5"/></g><g class="mark"><title>swap in, 8: 5.0</title><circle class="s2 ring" cx="246.2" cy="228.0" r="5"/></g><g class="mark"><title>swap in, 16: 2.8</title><circle class="s2 ring" cx="307.0" cy="237.5" r="5"/></g><g class="mark"><title>swap in, 32: 1.5</title><circle class="s2 ring" cx="367.8" cy="243.4" r="5"/></g><g class="mark"><title>swap in, 64: 0.9</title><circle class="s2 ring" cx="428.5" cy="246.0" r="5"/></g><g class="mark"><title>swap in, 128: 0.5</title><circle class="s2 ring" cx="489.2" cy="247.7" r="5"/></g><g class="mark"><title>swap in, 256: 0.3</title><circle class="s2 ring" cx="550.0" cy="248.5" r="5"/></g><polyline class="l3" points="64.0,208.4 124.8,208.4 185.5,208.4 246.2,208.4 307.0,208.4 367.8,208.4 428.5,208.4 489.2,208.4 550.0,208.4"/><g class="mark"><title>recompute, 1: 9.5</title><circle class="s3 ring" cx="64.0" cy="208.4" r="5"/></g><g class="mark"><title>recompute, 2: 9.5</title><circle class="s3 ring" cx="124.8" cy="208.4" r="5"/></g><g class="mark"><title>recompute, 4: 9.5</title><circle class="s3 ring" cx="185.5" cy="208.4" r="5"/></g><g class="mark"><title>recompute, 8: 9.5</title><circle class="s3 ring" cx="246.2" cy="208.4" r="5"/></g><g class="mark"><title>recompute, 16: 9.5</title><circle class="s3 ring" cx="307.0" cy="208.4" r="5"/></g><g class="mark"><title>recompute, 32: 9.5</title><circle class="s3 ring" cx="367.8" cy="208.4" r="5"/></g><g class="mark"><title>recompute, 64: 9.5</title><circle class="s3 ring" cx="428.5" cy="208.4" r="5"/></g><g class="mark"><title>recompute, 128: 9.5</title><circle class="s3 ring" cx="489.2" cy="208.4" r="5"/></g><g class="mark"><title>recompute, 256: 9.5</title><circle class="s3 ring" cx="550.0" cy="208.4" r="5"/></g><line class="grid" x1="556.0" y1="208.4" x2="566.0" y2="208.4"/><rect class="s3" x="570.0" y="203.4" width="10" height="10" rx="2"/><text class="t-note" x="586.0" y="212.4" text-anchor="start">recompute: 9.5</text><line class="grid" x1="556.0" y1="248.5" x2="566.0" y2="248.5"/><rect class="s1" x="570.0" y="243.5" width="10" height="10" rx="2"/><text class="t-note" x="586.0" y="252.5" text-anchor="start">swap out: 0.3</text><line class="grid" x1="556.0" y1="248.5" x2="566.0" y2="265.5"/><rect class="s2" x="570.0" y="260.5" width="10" height="10" rx="2"/><text class="t-note" x="586.0" y="269.5" text-anchor="start">swap in: 0.3</text><text class="t-tick" x="307.0" y="290.0" text-anchor="middle">block size in tokens (log scale)</text><text class="t-tick" x="14.0" y="18.0" text-anchor="start">milliseconds</text></svg><figcaption>Time to swap the same 213-token cache out and back in, against the block size, on our laptop. One copy per block makes small blocks expensive. Recomputation does not read the blocks, so its cost is the same at every block size.</figcaption></figure>

Recomputation is exact: the cache from one pass equals the cache built token by token to $$1.8 \times 10^{-5}$$, and the next token is the same. Swapping is exact too, bit for bit.

The paper's claim about speed holds by a wide margin. Building the cache one token at a time took 1,342.8 ms. Recomputing it in one pass took 9.5 ms, 142 times less.

The block-size table shows the start-up cost. At block size 1, each direction makes 213 small copies, about 0.19 ms each, and the swap takes over 40 ms. At block size 16 it takes under 3 ms each way, and at 256 one copy does it. Recomputation sits at 9.45 ms whatever the block size. So recomputation wins for small blocks and swapping for large ones, the pattern the paper measures in §7.3 (Part 5).

Our laptop's numbers are not a server's. An Apple laptop's CPU and GPU share one memory, so "swapping" here copies within the same chips. A server moves the blocks over PCIe, which is slower. A server GPU also computes much faster. These timings come from a laptop shared with other jobs, so treat them as shapes.

## Many GPUs {§4.6}

Every number of a model's weights must sit in GPU memory while the model runs. In 16-bit numbers, each parameter takes 2 bytes. So a model of 13 billion parameters needs 26 GB for its weights alone, and the largest A100 holds 80 GB. The paper's Table 1 lists its three models: 26 GB, 132 GB and 346 GB of weights.

<figure class="fig"><svg viewBox="0 0 720 186" role="img" aria-label="Bars: OPT-13B has 26 GB of weights, OPT-66B 132 GB and OPT-175B 346 GB. A line at 80 GB marks one A100. Only the smallest model fits on one GPU."><defs><marker id="ah" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="arrow" d="M0,0L10,5L0,10z"/></marker><marker id="ah-on" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="6" markerHeight="6" orient="auto-start-reverse"><path class="arrow-on" d="M0,0L10,5L0,10z"/></marker><marker id="ah-2" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="6" markerHeight="6" orient="auto-start-reverse"><path class="arrow-2" d="M0,0L10,5L0,10z"/></marker></defs><text class="t-title" x="20.0" y="34.0" text-anchor="start">Weights alone, in GB (the paper's Table 1), against the memory of one A100</text><text class="t-tick" x="122.0" y="65.0" text-anchor="end">OPT-13B</text><g class="mark"><title>OPT-13B: 26 GB</title><rect class="s1" x="130.0" y="47.0" width="33.9" height="26.0" rx="3"/></g><text class="t-val" x="169.9" y="65.0" text-anchor="start">26 GB</text><text class="t-tick" x="122.0" y="99.0" text-anchor="end">OPT-66B</text><g class="mark"><title>OPT-66B: 132 GB</title><rect class="s1" x="130.0" y="81.0" width="172.3" height="26.0" rx="3"/></g><text class="t-val" x="308.3" y="99.0" text-anchor="start">132 GB</text><text class="t-tick" x="122.0" y="133.0" text-anchor="end">OPT-175B</text><g class="mark"><title>OPT-175B: 346 GB</title><rect class="s1" x="130.0" y="115.0" width="451.7" height="26.0" rx="3"/></g><text class="t-val" x="587.7" y="133.0" text-anchor="start">346 GB</text><line class="bad-line" x1="234.4" y1="40" x2="234.4" y2="150"/><text class="t-tick" x="238.4" y="172.0" text-anchor="start">one A100: 80 GB at most</text><text class="t-tick" x="20.0" y="172.0" text-anchor="start">the paper uses 1, 4 and 8 GPUs</text></svg><figcaption>Why one model needs several GPUs. The weights of the paper's three models (Table 1) against the memory of one A100. Only OPT-13B fits on one card; the paper runs OPT-66B on 4 GPUs and OPT-175B on 8.</figcaption></figure>

The weights are not all. The KV cache also needs room, and that room decides how many requests can run at once. On 4 A100s with 160 GB together, OPT-66B leaves 21 GB for the cache (Table 1). So the question is not only "does the model fit?" but "how do several GPUs work as one?".

> [!NOTE] Where this idea comes from: Megatron-LM
> In 2019 a team at NVIDIA published Megatron-LM. They wanted to train language models too big for one GPU, and showed a simple way to cut each layer into slices, one per GPU. With it they trained a model of 8.3 billion parameters. Their method is called **tensor parallelism**, and most LLM servers use it today, vLLM among them.
>
> Think of two cooks and one long recipe. One way to share the work: the first cook does the first half of the steps, then passes the dish to the second. That is **pipeline parallelism**. The other way: at every step, both cooks work at once, each on half of the ingredients, and they join the results. That is tensor parallelism, and Megatron-LM does it at every layer.

> [!DEFINITION] Shard
> One piece of something that is cut up and spread over several machines. A **model shard** is the part of the model's weights that one GPU holds.

> [!PAPER] · §4.6 · pages 8 to 9
> [![The opening of §4.6, with exceeding the capacity of a single GPU, Megatron-LM style tensor model parallelism and SPMD (Single Program Multiple Data) highlighted](https://ishwarj.com/img/papers/vllm/p4-dist-1.png/vllm/p4-dist-1.png)](/img/papers/vllm/p4-dist-1.png)
> [![Its continuation on page 9, with all-reduce operation, split on the attention head dimension and a subset of attention heads highlighted](https://ishwarj.com/img/papers/vllm/p4-dist-2.png/vllm/p4-dist-2.png)](/img/papers/vllm/p4-dist-2.png)
>
> **What it says:** many models are "exceeding the capacity of a single GPU". vLLM supports "Megatron-LM style tensor model parallelism", with an "SPMD (Single Program Multiple Data)" schedule. The linear layers are split, and the GPUs combine their results with an "all-reduce operation". Attention is "split on the attention head dimension": each GPU computes "a subset of attention heads".
>
> **What it means:**
>
> As the chart above showed, OPT-66B cannot fit on one A100. So the paper serves it on 4 GPUs and OPT-175B on 8 (Table 1, Part 5). The question is how to cut one model into pieces that work together at every step.
>
> Tensor parallelism cuts every layer, not the list of layers. Every GPU runs the same program on every token, which is what SPMD means. Each GPU holds a slice of every weight matrix. For attention the cut is natural: a layer with 12 heads on 2 GPUs gives 6 heads to each. Heads do not talk to each other until the very end, so each GPU can do its own heads alone.

> [!DEFINITION] Tensor parallelism
> Splitting each weight matrix of a model across several GPUs, so that every GPU does part of every layer. The other common split, pipeline parallelism, gives each GPU a different group of whole layers.

> [!DEFINITION] All-reduce
> A group operation: each GPU has a tensor of the same shape, and afterwards every GPU holds the sum of all of them. A library such as NCCL, NVIDIA's library for sending data between GPUs, does it over the links between the cards.

> [!DEFINITION] Attention head
> One of several small attention units that work side by side in one layer. OPT-125M has 12 heads per layer, each with vectors of 64 numbers. Each head makes its own query, key and value and its own output; the layer then joins the 12 outputs.

> [!DEFINITION] SPMD
> Single Program, Multiple Data. Every GPU runs the same code at the same time, each on its own share of the data. Here the "share" is a share of the weights: GPU 0 has heads 0 to 5, GPU 1 has heads 6 to 11.

Why is a sum enough? The last step of attention multiplies the outputs of all heads, side by side, by an output matrix $$W_o$$. Split the head outputs into GPU 0's part $$h^{(0)}$$ and GPU 1's part $$h^{(1)}$$, and split the rows of $$W_o$$ the same way:

$$
o = \begin{bmatrix} h^{(0)} & h^{(1)} \end{bmatrix} \begin{bmatrix} W_o^{(0)} \\ W_o^{(1)} \end{bmatrix} = h^{(0)} W_o^{(0)} + h^{(1)} W_o^{(1)}
$$

Read it from left to right. The row vector of all head outputs times the full matrix equals two smaller products added together. GPU 0 can compute $$h^{(0)} W_o^{(0)}$$ with its own heads and its own rows of $$W_o$$, and GPU 1 the other term. One all-reduce adds them. This is just how matrix multiplication works, with no approximation.

A tiny example: $$h = (1 \mid 2)$$ and $$W_o$$ with rows 3 and 4. The full product is $$1 \cdot 3 + 2 \cdot 4 = 11$$. GPU 0 computes $$1 \cdot 3 = 3$$, GPU 1 computes $$2 \cdot 4 = 8$$, and the all-reduce gives $$3 + 8 = 11$$.

<figure class="fig"><svg viewBox="0 0 720 360" role="img" aria-label="Two GPU frames. GPU 0 holds heads 0 to 5, GPU 1 holds heads 6 to 11. Each multiplies its head outputs by its rows of the output matrix and gets a partial output: 3 and 8 in the tiny example. An all-reduce adds them to 11 and gives the sum to both GPUs."><defs><marker id="ah" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="arrow" d="M0,0L10,5L0,10z"/></marker><marker id="ah-on" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="6" markerHeight="6" orient="auto-start-reverse"><path class="arrow-on" d="M0,0L10,5L0,10z"/></marker><marker id="ah-2" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="6" markerHeight="6" orient="auto-start-reverse"><path class="arrow-2" d="M0,0L10,5L0,10z"/></marker></defs><text class="t-title" x="20.0" y="24.0" text-anchor="start">Splitting attention by heads, and the all-reduce that joins the halves</text><rect class="box-1" x="20.0" y="40.0" width="330.0" height="190.0" rx="10"/><text class="t-tick t-strong" x="185.0" y="62.0" text-anchor="middle">GPU 0</text><rect class="box" x="35.0" y="74.0" width="45.0" height="30.0" rx="6"/><text class="t-tick" x="57.5" y="93.5" text-anchor="middle">head 0</text><rect class="box" x="86.0" y="74.0" width="45.0" height="30.0" rx="6"/><text class="t-tick" x="108.5" y="93.5" text-anchor="middle">head 1</text><rect class="box" x="137.0" y="74.0" width="45.0" height="30.0" rx="6"/><text class="t-tick" x="159.5" y="93.5" text-anchor="middle">head 2</text><rect class="box" x="188.0" y="74.0" width="45.0" height="30.0" rx="6"/><text class="t-tick" x="210.5" y="93.5" text-anchor="middle">head 3</text><rect class="box" x="239.0" y="74.0" width="45.0" height="30.0" rx="6"/><text class="t-tick" x="261.5" y="93.5" text-anchor="middle">head 4</text><rect class="box" x="290.0" y="74.0" width="45.0" height="30.0" rx="6"/><text class="t-tick" x="312.5" y="93.5" text-anchor="middle">head 5</text><text class="t-tick" x="185.0" y="130.0" text-anchor="middle">outputs of its 6 heads: h(0)</text><text class="t-tick" x="185.0" y="152.0" text-anchor="middle">times its rows of the output matrix: Wo(0)</text><rect class="box" x="85.0" y="168.0" width="200.0" height="30.0" rx="6"/><text class="t-tick" x="185.0" y="187.5" text-anchor="middle">partial output h(0) Wo(0)</text><text class="t-tick t-strong" x="185.0" y="220.0" text-anchor="middle">tiny example: 1 × 3 = 3</text><line class="edge" x1="185.0" y1="232.0" x2="360.0" y2="262.0" marker-end="url(#ah)"/><rect class="box-2" x="370.0" y="40.0" width="330.0" height="190.0" rx="10"/><text class="t-tick t-strong" x="535.0" y="62.0" text-anchor="middle">GPU 1</text><rect class="box" x="385.0" y="74.0" width="45.0" height="30.0" rx="6"/><text class="t-tick" x="407.5" y="93.5" text-anchor="middle">head 6</text><rect class="box" x="436.0" y="74.0" width="45.0" height="30.0" rx="6"/><text class="t-tick" x="458.5" y="93.5" text-anchor="middle">head 7</text><rect class="box" x="487.0" y="74.0" width="45.0" height="30.0" rx="6"/><text class="t-tick" x="509.5" y="93.5" text-anchor="middle">head 8</text><rect class="box" x="538.0" y="74.0" width="45.0" height="30.0" rx="6"/><text class="t-tick" x="560.5" y="93.5" text-anchor="middle">head 9</text><rect class="box" x="589.0" y="74.0" width="45.0" height="30.0" rx="6"/><text class="t-tick" x="611.5" y="93.5" text-anchor="middle">head 10</text><rect class="box" x="640.0" y="74.0" width="45.0" height="30.0" rx="6"/><text class="t-tick" x="662.5" y="93.5" text-anchor="middle">head 11</text><text class="t-tick" x="535.0" y="130.0" text-anchor="middle">outputs of its 6 heads: h(1)</text><text class="t-tick" x="535.0" y="152.0" text-anchor="middle">times its rows of the output matrix: Wo(1)</text><rect class="box" x="435.0" y="168.0" width="200.0" height="30.0" rx="6"/><text class="t-tick" x="535.0" y="187.5" text-anchor="middle">partial output h(1) Wo(1)</text><text class="t-tick t-strong" x="535.0" y="220.0" text-anchor="middle">tiny example: 2 × 4 = 8</text><line class="edge" x1="535.0" y1="232.0" x2="360.0" y2="262.0" marker-end="url(#ah)"/><rect class="box-on" x="220.0" y="264.0" width="280.0" height="34.0" rx="6"/><text class="t-tick" x="360.0" y="285.5" text-anchor="middle">all-reduce: 3 + 8 = 11</text><text class="t-tick" x="360.0" y="320.0" text-anchor="middle">afterwards both GPUs hold 11, the same as the unsplit layer (1 × 3 + 2 × 4)</text><text class="t-tick" x="360.0" y="342.0" text-anchor="middle">in our OPT-125M run: max difference 4.2e-07 against the library</text></svg><figcaption>Attention split by heads over two GPUs. GPU 0 holds heads 0 to 5 and GPU 1 heads 6 to 11. Each multiplies its head outputs by its own rows of the output matrix and gets a partial output. The all-reduce adds the partial outputs, 3 + 8 = 11 in the tiny example, and gives the sum to both GPUs.</figcaption></figure>

The heads themselves need no talk between GPUs. Each head reads only its own queries, keys and values. Only the last multiplication mixes the heads, and that is the one place where the GPUs must add their results.

Here is one GPU's work, for the first attention layer of OPT-125M. It takes the query, key and value rows of its own heads and runs attention for those heads. Then it multiplies by its own columns of the output matrix. The second block is the all-reduce, here just a sum of the two results. If the split is right, the sum must equal the layer of the library:

```python
def attention_shard(x, heads):
    """One GPU's work: the query, key and value rows of its own heads (column split), attention for those heads,
    and its columns of the output matrix (row split). The result is a partial sum, without the output bias."""
    rows = slice(heads.start * D, heads.stop * D)
    q = (x @ attn.q_proj.weight[rows].T + attn.q_proj.bias[rows]) * attn.scaling
    k = x @ attn.k_proj.weight[rows].T + attn.k_proj.bias[rows]
    v = x @ attn.v_proj.weight[rows].T + attn.v_proj.bias[rows]
    h = len(heads)
    q, k, v = (t.view(-1, h, D).transpose(0, 1) for t in (q, k, v))          # (heads, tokens, head size)
    s = q @ k.transpose(1, 2) + torch.full((Tn, Tn), -float('inf')).triu(1)   # causal mask
    o = (torch.softmax(s, -1) @ v).transpose(0, 1).reshape(-1, h * D)
    return o @ attn.out_proj.weight[:, rows].T, k                              # partial output, this GPU's keys
```

```python
parts = [attention_shard(x, range(0, 6)), attention_shard(x, range(6, 12))]
allreduce = parts[0][0] + parts[1][0] + attn.out_proj.bias                    # all-reduce = sum over the GPUs
```

(PyTorch stores a weight matrix transposed. So the "rows of $$W_o$$" in the equation are columns of `out_proj.weight` here.) The bias is added once, after the sum, or it would be counted twice. Method 2 is the unsplit attention layer of the library, which we capture while the model runs. We also split the feed-forward layer the same way and compare the whole layer:

```text
== 7. Tensor parallelism (§4.6): one OPT-125M layer split over 2 simulated GPUs, 6 heads each
11 tokens; GPU 0 has heads 0-5, GPU 1 has heads 6-11; each computes a partial output of shape (11, 768)
all-reduce (sum of the 2 partial outputs) against the unsplit attention of the library: max difference 4.2e-07
the whole layer (attention + feed-forward, 2 all-reduces) against the library layer: max difference 2.3e-05
KV cache per GPU: keys of shape (6, 11, 64) (6 heads, all 11 positions); the two halves together equal the full keys: True
per GPU and per token: 18,432 bytes of KV cache instead of 36,864 (FP16); the same block table serves both
data sent by each all-reduce: 11 x 768 numbers; 2 all-reduces per layer, 24 per pass
```

<figure class="fig"><svg viewBox="0 0 720 340" role="img" aria-label="The input goes to both GPUs. Each computes attention for six heads and a partial output; an all-reduce adds the two partial outputs into the layer output."><defs><marker id="ah" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="arrow" d="M0,0L10,5L0,10z"/></marker><marker id="ah-on" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="6" markerHeight="6" orient="auto-start-reverse"><path class="arrow-on" d="M0,0L10,5L0,10z"/></marker><marker id="ah-2" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="6" markerHeight="6" orient="auto-start-reverse"><path class="arrow-2" d="M0,0L10,5L0,10z"/></marker></defs><text class="t-title" x="20.0" y="26.0" text-anchor="start">One attention layer on 2 GPUs (our OPT-125M run: 12 heads, 6 per GPU)</text><rect class="box" x="250.0" y="44.0" width="220.0" height="32.0" rx="6"/><text class="t-tick" x="360.0" y="64.5" text-anchor="middle">input x (same on both GPUs)</text><rect class="box-1" x="40.0" y="104.0" width="300.0" height="150.0" rx="10"/><text class="t-tick t-strong" x="190.0" y="126.0" text-anchor="middle">GPU 0: heads 0-5</text><text class="t-tick" x="190.0" y="152.0" text-anchor="middle">Q, K, V rows of its own heads</text><text class="t-tick" x="190.0" y="176.0" text-anchor="middle">attention for 6 heads</text><text class="t-tick" x="190.0" y="200.0" text-anchor="middle">its 384 columns of the output matrix</text><text class="t-tick" x="190.0" y="232.0" text-anchor="middle">KV cache: heads 0-5, same block IDs</text><line class="edge" x1="360.0" y1="76.0" x2="190.0" y2="102.0" marker-end="url(#ah)"/><line class="edge" x1="190.0" y1="256.0" x2="360.0" y2="286.0" marker-end="url(#ah)"/><rect class="box-2" x="380.0" y="104.0" width="300.0" height="150.0" rx="10"/><text class="t-tick t-strong" x="530.0" y="126.0" text-anchor="middle">GPU 1: heads 6-11</text><text class="t-tick" x="530.0" y="152.0" text-anchor="middle">Q, K, V rows of its own heads</text><text class="t-tick" x="530.0" y="176.0" text-anchor="middle">attention for 6 heads</text><text class="t-tick" x="530.0" y="200.0" text-anchor="middle">its 384 columns of the output matrix</text><text class="t-tick" x="530.0" y="232.0" text-anchor="middle">KV cache: heads 6-11, same block IDs</text><line class="edge" x1="360.0" y1="76.0" x2="530.0" y2="102.0" marker-end="url(#ah)"/><line class="edge" x1="530.0" y1="256.0" x2="360.0" y2="286.0" marker-end="url(#ah)"/><rect class="box-on" x="230.0" y="288.0" width="260.0" height="32.0" rx="6"/><text class="t-tick" x="360.0" y="308.5" text-anchor="middle">all-reduce: sum the 2 partial outputs</text><text class="t-tick" x="360.0" y="334.0" text-anchor="middle">sum vs. unsplit layer: max difference 4.2e-07</text></svg><figcaption>One attention layer split over two GPUs, as in our run. Both GPUs get the same input. Each computes six heads and a partial output; the all-reduce adds the two partial outputs into the layer's output.</figcaption></figure>

The two partial outputs add up to the library's attention output, to $$4.2 \times 10^{-7}$$. The whole layer, with a second all-reduce after the feed-forward part, matches to $$2.3 \times 10^{-5}$$. Each layer needs two all-reduces, so OPT-125M on 2 GPUs would need 24 per pass. Our two "GPUs" are two function calls on one laptop; a real setup sends these sums over fast links between the cards.

Look at the keys. Each GPU keeps keys for its 6 heads, but for all 11 positions. Each token's cache is cut in half, 18,432 bytes per GPU instead of 36,864, but every position is on every GPU. That fact is the point of the next box.

> [!PAPER] · §4.6 · page 9
> [![The paragraph on the single KV cache manager, with the same set of input tokens, single KV cache manager, share the manager and only stores a portion of the KV cache highlighted](https://ishwarj.com/img/papers/vllm/p4-one-manager.png/p4-one-manager.png)](/img/papers/vllm/p4-one-manager.png)
>
> **What it says:** with model parallelism, each shard still processes "the same set of input tokens", so it needs the KV cache for the same positions. vLLM therefore has a "single KV cache manager" in the central scheduler, and all GPU workers "share the manager". Each worker uses the same physical block IDs but "only stores a portion of the KV cache": the part for its own heads.
>
> **What it means:**
>
> Picture a library whose books are so wide that each book is cut down the middle. The left halves stand on shelf A, the right halves on shelf B. A single catalogue says "your book is at position 26", and both halves stand at position 26 on their shelves.
>
> Block 26 on GPU 0 holds heads 0 to 5 of some 16 tokens. Block 26 on GPU 1 holds heads 6 to 11 of the same 16 tokens. So one block table is right for every GPU. The scheduler can do all the memory bookkeeping in one place, and no GPU ever needs to ask another where a block is.

> [!PAPER] · §4.6 · page 9
> [![The paragraph on one step, with broadcasts this control message, all-reduce communication primitive and do not need to synchronize on memory management highlighted](https://ishwarj.com/img/papers/vllm/p4-control.pngvllm/p4-control.png)](/img/papers/vllm/p4-control.png)
>
> **What it says:** at each step, the scheduler prepares the token IDs and block tables of the batch and "broadcasts this control message" to the workers. The workers run the model and combine results with the "all-reduce communication primitive", without the scheduler. They send back the sampled tokens. So workers "do not need to synchronize on memory management".
>
> **What it means:**
>
> One step has a simple rhythm. The scheduler decides who runs, does fork, append and free, and sends one message with the token IDs and block tables. The GPUs then compute, talking only to each other through all-reduces. At the end they report the new tokens.
>
> All memory decisions happen before the step starts. During the step, the GPUs only read and write the blocks they were told about. That keeps the fast path, the model on the GPUs, free of any memory logic.

## The implementation {§5}

> [!PAPER] · §5 · page 9
> [![The opening of §5, with 8.5K lines of Python and 2K lines of C++/CUDA code and custom CUDA kernels highlighted](https://ishwarj.com/img/papers/vllm/p4-impl.pngrs/vllm/p4-impl.png)](/img/papers/vllm/p4-impl.png)
>
> **What it says:** vLLM has a FastAPI frontend that extends the OpenAI API, and an engine of "8.5K lines of Python and 2K lines of C++/CUDA code". The scheduler and block manager are Python; "custom CUDA kernels" handle key operations such as PagedAttention.
>
> **What it means:**
>
> The split follows the cost. The scheduler and the block manager run once per step and deal with lists and counters. Python is fast enough for that, and easy to change. The work that touches every number of the cache, thousands of times per step, runs on the GPU in hand-written kernels.
>
> Our block manager is the same idea in one short Python class. What we cannot write in Python is the fast GPU side. The next two boxes show why it needs special kernels.

> [!DEFINITION] Kernel and kernel launch
> A **kernel** is a function that runs on the GPU, on many threads at once. A **kernel launch** is the CPU telling the GPU to start one. Each launch has a small fixed cost, so a thousand tiny kernels can cost more than the work they do.

> [!NOTE] Where this idea comes from: GPU kernels and kernel fusion
> A GPU has thousands of small cores. It does not run a whole program by itself. The CPU runs the program and hands the GPU one job at a time: "multiply these two matrices", "copy these bytes". Each job is a kernel. Since 2007, NVIDIA's **CUDA** has let programmers write their own kernels in a form of C++. A **thread** is one of the many copies of the kernel that run at once, each on its own piece of the data.
>
> Every launch has a fixed cost, a few microseconds on a server GPU, before any real work starts. Think of a trip to the shop. Buying ten things in ten trips costs ten journeys; buying them in one trip costs one. **Kernel fusion** is the one trip. Several small steps are joined into one kernel, so the fixed cost is paid once. The data also stays on the chip between the steps.
>
> Fast inference libraries are built on fused kernels. One of them is NVIDIA's FasterTransformer, which the paper uses as a baseline in its experiments. The vLLM authors took FasterTransformer's attention kernel and changed it to read keys and values through a block table.

> [!PAPER] · §5.1 · page 9
> [![The first part of §5.1, with Fused reshape and block write, into a single kernel., Fusing block read and attention and assign a GPU warp to read each block highlighted](https://ishwarj.com/img/papers/vllm/p4-kern-1.png/vllm/p4-kern-1.png)](/img/papers/vllm/p4-kern-1.png)
>
> **What it says:** (1) "Fused reshape and block write": the new KV cache is split into blocks, reshaped and saved at the places that the block table gives, all "into a single kernel". (2) "Fusing block read and attention": the attention kernel reads the cache through the block table on the fly, and they "assign a GPU warp to read each block".
>
> **What it means:**
>
> At every step, every layer writes one new key and value per sequence into some slot of some block. Done naively, that is one small copy per token per layer. The fused kernel gets a list of target slots and writes them all in one launch.
>
> The second kernel is PagedAttention itself. It reads keys and values block by block, following the table, inside the attention computation. A **warp** is a group of 32 GPU threads that run in lockstep. Giving each block to one warp makes those threads read neighbouring addresses at the same time, which is the fast way to read GPU memory.

> [!PAPER] · §5.1 · page 9
> [![The end of §5.1, with Fused block copy, numerous invocations of small data movements and into a single kernel launch highlighted](https://ishwarj.com/img/papers/vllm/p4-kern-2.png/vllm/p4-kern-2.png)](/img/papers/vllm/p4-kern-2.png)
>
> **What it says:** (3) "Fused block copy": the copies that copy-on-write asks for may touch scattered blocks. With one cudaMemcpyAsync call per block, that means "numerous invocations of small data movements". vLLM batches all of them "into a single kernel launch".
>
> **What it means:**
>
> In one step of a large beam search, dozens of blocks may need copy-on-write. Each copy is small, a few kilobytes per layer. Paid one launch at a time, the fixed costs add up, as with our small-block swaps. One kernel that gets the full list of (source, target) pairs does all of them in one go.

We try both fused writes in PyTorch on the laptop GPU. For the block write, 256 sequences each store one new key. The slot of a token is its physical block times 16 plus its offset inside the block:

```python
slots = (tables[torch.arange(256), lens // B9] * B9 + lens % B9).to(GPU)       # where each new token goes
```

```python
def write_loop():
    for i in range(256):
        cache[slots[i]] = new[i]


def write_fused():
    cache.index_copy_(0, slots, new)
```

The copy-on-write test copies 128 scattered blocks, once with one copy per block and once with one batched copy. In the output, compare the two times on each line, and check that both ways give the same result:

```text
== 8. Kernels of §5.1 in PyTorch, on the laptop GPU (FP16, one layer's key cache: blocks x 16 x 12 x 64)
block write of 256 new tokens: one copy per token 62.15 ms (256 launches), one scatter 0.155 ms (1 launch); same cache: True; 401x
copy-on-write of 128 scattered blocks: one copy per block 1.10 ms, one batched copy 0.405 ms; same result: True; 2.7x
```

<figure class="fig"><svg viewBox="0 0 720 250" role="img" aria-label="Top: a row of many small launches, each with a fixed start cost and a little work, 62.15 ms in all. Bottom: one launch with one start cost and all the work, 0.155 ms."><defs><marker id="ah" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="arrow" d="M0,0L10,5L0,10z"/></marker><marker id="ah-on" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="6" markerHeight="6" orient="auto-start-reverse"><path class="arrow-on" d="M0,0L10,5L0,10z"/></marker><marker id="ah-2" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="6" markerHeight="6" orient="auto-start-reverse"><path class="arrow-2" d="M0,0L10,5L0,10z"/></marker></defs><text class="t-title" x="20.0" y="24.0" text-anchor="start">Kernel fusion: 256 small writes against one batched write (our laptop GPU)</text><text class="t-tick t-strong" x="20.0" y="60.0" text-anchor="start">one launch per token</text><rect class="box" x="180.0" y="46.0" width="9.0" height="22.0" rx="1"/><rect class="box-on" x="189.0" y="46.0" width="4.0" height="22.0" rx="1"/><rect class="box" x="196.0" y="46.0" width="9.0" height="22.0" rx="1"/><rect class="box-on" x="205.0" y="46.0" width="4.0" height="22.0" rx="1"/><rect class="box" x="212.0" y="46.0" width="9.0" height="22.0" rx="1"/><rect class="box-on" x="221.0" y="46.0" width="4.0" height="22.0" rx="1"/><rect class="box" x="228.0" y="46.0" width="9.0" height="22.0" rx="1"/><rect class="box-on" x="237.0" y="46.0" width="4.0" height="22.0" rx="1"/><rect class="box" x="244.0" y="46.0" width="9.0" height="22.0" rx="1"/><rect class="box-on" x="253.0" y="46.0" width="4.0" height="22.0" rx="1"/><rect class="box" x="260.0" y="46.0" width="9.0" height="22.0" rx="1"/><rect class="box-on" x="269.0" y="46.0" width="4.0" height="22.0" rx="1"/><rect class="box" x="276.0" y="46.0" width="9.0" height="22.0" rx="1"/><rect class="box-on" x="285.0" y="46.0" width="4.0" height="22.0" rx="1"/><rect class="box" x="292.0" y="46.0" width="9.0" height="22.0" rx="1"/><rect class="box-on" x="301.0" y="46.0" width="4.0" height="22.0" rx="1"/><rect class="box" x="308.0" y="46.0" width="9.0" height="22.0" rx="1"/><rect class="box-on" x="317.0" y="46.0" width="4.0" height="22.0" rx="1"/><rect class="box" x="324.0" y="46.0" width="9.0" height="22.0" rx="1"/><rect class="box-on" x="333.0" y="46.0" width="4.0" height="22.0" rx="1"/><rect class="box" x="340.0" y="46.0" width="9.0" height="22.0" rx="1"/><rect class="box-on" x="349.0" y="46.0" width="4.0" height="22.0" rx="1"/><rect class="box" x="356.0" y="46.0" width="9.0" height="22.0" rx="1"/><rect class="box-on" x="365.0" y="46.0" width="4.0" height="22.0" rx="1"/><rect class="box" x="372.0" y="46.0" width="9.0" height="22.0" rx="1"/><rect class="box-on" x="381.0" y="46.0" width="4.0" height="22.0" rx="1"/><rect class="box" x="388.0" y="46.0" width="9.0" height="22.0" rx="1"/><rect class="box-on" x="397.0" y="46.0" width="4.0" height="22.0" rx="1"/><rect class="box" x="404.0" y="46.0" width="9.0" height="22.0" rx="1"/><rect class="box-on" x="413.0" y="46.0" width="4.0" height="22.0" rx="1"/><rect class="box" x="420.0" y="46.0" width="9.0" height="22.0" rx="1"/><rect class="box-on" x="429.0" y="46.0" width="4.0" height="22.0" rx="1"/><rect class="box" x="436.0" y="46.0" width="9.0" height="22.0" rx="1"/><rect class="box-on" x="445.0" y="46.0" width="4.0" height="22.0" rx="1"/><rect class="box" x="452.0" y="46.0" width="9.0" height="22.0" rx="1"/><rect class="box-on" x="461.0" y="46.0" width="4.0" height="22.0" rx="1"/><rect class="box" x="468.0" y="46.0" width="9.0" height="22.0" rx="1"/><rect class="box-on" x="477.0" y="46.0" width="4.0" height="22.0" rx="1"/><rect class="box" x="484.0" y="46.0" width="9.0" height="22.0" rx="1"/><rect class="box-on" x="493.0" y="46.0" width="4.0" height="22.0" rx="1"/><rect class="box" x="500.0" y="46.0" width="9.0" height="22.0" rx="1"/><rect class="box-on" x="509.0" y="46.0" width="4.0" height="22.0" rx="1"/><rect class="box" x="516.0" y="46.0" width="9.0" height="22.0" rx="1"/><rect class="box-on" x="525.0" y="46.0" width="4.0" height="22.0" rx="1"/><rect class="box" x="532.0" y="46.0" width="9.0" height="22.0" rx="1"/><rect class="box-on" x="541.0" y="46.0" width="4.0" height="22.0" rx="1"/><rect class="box" x="548.0" y="46.0" width="9.0" height="22.0" rx="1"/><rect class="box-on" x="557.0" y="46.0" width="4.0" height="22.0" rx="1"/><rect class="box" x="564.0" y="46.0" width="9.0" height="22.0" rx="1"/><rect class="box-on" x="573.0" y="46.0" width="4.0" height="22.0" rx="1"/><rect class="box" x="580.0" y="46.0" width="9.0" height="22.0" rx="1"/><rect class="box-on" x="589.0" y="46.0" width="4.0" height="22.0" rx="1"/><rect class="box" x="596.0" y="46.0" width="9.0" height="22.0" rx="1"/><rect class="box-on" x="605.0" y="46.0" width="4.0" height="22.0" rx="1"/><rect class="box" x="612.0" y="46.0" width="9.0" height="22.0" rx="1"/><rect class="box-on" x="621.0" y="46.0" width="4.0" height="22.0" rx="1"/><rect class="box" x="628.0" y="46.0" width="9.0" height="22.0" rx="1"/><rect class="box-on" x="637.0" y="46.0" width="4.0" height="22.0" rx="1"/><rect class="box" x="644.0" y="46.0" width="9.0" height="22.0" rx="1"/><rect class="box-on" x="653.0" y="46.0" width="4.0" height="22.0" rx="1"/><rect class="box" x="660.0" y="46.0" width="9.0" height="22.0" rx="1"/><rect class="box-on" x="669.0" y="46.0" width="4.0" height="22.0" rx="1"/><rect class="box" x="676.0" y="46.0" width="9.0" height="22.0" rx="1"/><rect class="box-on" x="685.0" y="46.0" width="4.0" height="22.0" rx="1"/><text class="t-tick" x="180.0" y="88.0" text-anchor="start">(32 of the 256 shown) each = fixed launch cost (grey) + tiny work (blue): 62.15 ms</text><text class="t-tick t-strong" x="20.0" y="132.0" text-anchor="start">one fused launch</text><rect class="box" x="180.0" y="118.0" width="9.0" height="22.0" rx="1"/><rect class="box-on" x="189.0" y="118.0" width="128.0" height="22.0" rx="1"/><text class="t-tick" x="180.0" y="160.0" text-anchor="start">one fixed cost, then all 256 writes together: 0.155 ms</text><text class="t-tick" x="20.0" y="206.0" text-anchor="start">The work is the same; the fused version pays the start-up cost once.</text><text class="t-tick t-muted" x="20.0" y="228.0" text-anchor="start">The bars are a sketch, not to scale; the times are from our run.</text></svg><figcaption>Kernel fusion in our run. Writing 256 new tokens with one launch each pays the fixed launch cost 256 times; one fused launch pays it once and does the same work. The bars are a sketch; the two times are from our laptop GPU.</figcaption></figure>

Both versions give the same cache, bit for bit. The single scatter is 401 times faster than 256 separate writes. Batching the 128 block copies makes them 2.7 times faster. A PyTorch call on an Apple GPU has much more overhead than a CUDA kernel launch, so the ratios on an A100 are different. The direction is the same: many small operations lose to one large one.

> [!PAPER] · §5.2 · page 9
> [![§5.2, with fork, append, and free, creates a new sequence from an existing one, appends a new token and deletes the sequence highlighted](https://ishwarj.com/img/papers/vllm/p4-api.pngers/vllm/p4-api.png)](/img/papers/vllm/p4-api.png)
>
> **What it says:** vLLM builds all its decoding algorithms from three methods: "fork, append, and free". Fork "creates a new sequence from an existing one", append "appends a new token", and free "deletes the sequence". Parallel sampling forks the samples, appends tokens each step and frees finished ones; beam search and prefix sharing use the same calls.
>
> **What it means:**
>
> This is the block manager we built at the start of this part. Parallel sampling was one fork per sample, then appends. Beam search was fork the winners, free the losers, append. A shared prefix was a fork of a stored sequence. Copy-on-write and reference counts hide inside the three calls, and the decoding code never touches a block.
>
> The authors add that future decoding methods can be built from the same three calls. The memory side would not change at all: a new method only decides when to fork, append and free.

## What our small run cannot show

Our model was OPT-125M on an Apple laptop, not OPT-13B on an A100. The block tables, reference counts, copies and the agreement with `model.generate` are exact and do not depend on the hardware. The memory savings depend on our prompt and answer lengths, which are not the paper's workload.

The scheduler is a simulation in steps: it counts blocks and tokens but does not time anything. Our timings come from a laptop GPU that shares its memory with the CPU and ran other jobs at the same time. We took the fastest of several runs, but treat the numbers as shapes, not server numbers. Our two "GPUs" for tensor parallelism are two function calls; we did not measure the cost of a real all-reduce. Part 5 reads the paper's own measurements.

> [!TAKEAWAYS] Key takeaways
> - **Sharing blocks needs only two tools:** a reference count per physical block, and copy-on-write when a sequence writes into a shared block.
> - **Parallel sampling** stores the prompt once. In our run, four samples copied only the last, half-full prompt block (3 copies) and matched `model.generate` on all 96 tokens.
> - **Beam search** shares more, and the sharing changes at every step. Our 4 beams used 14 physical blocks instead of 32 and copied 88 token slots instead of 1,029.
> - **A shared prefix** is computed once and mapped by every request. Our two requests ran the prompt phase on 3 and 4 tokens instead of 44 and 45.
> - **The kernel only sees block tables.** That is why one batch can mix greedy decoding, sampling and beam search.
> - **When blocks run out,** vLLM preempts the latest request, all of its blocks at once, and serves requests first-come-first-served.
> - **Swapping** copies the blocks to CPU memory; **recomputation** runs prompt plus answer as one prompt. Recomputing our 213-token cache took 142 times less time than building it token by token.
> - **Tensor parallelism** gives each GPU a share of the attention heads. One all-reduce adds the partial outputs, which matched the unsplit layer to $$4.2 \times 10^{-7}$$.
> - **One block table serves every GPU,** because every GPU stores the same token positions for different heads.
> - **fork, append and free** are the whole interface between decoding algorithms and memory.

**Next, in Part 5:** §6 to §10. The experiments: throughput against latency, the measured savings of sharing, swapping against recomputation on an A100, and the limits.

<details>
<summary>Run it yourself</summary>

The script behind this part is [`code/papers/vllm/vllm_part4.py`](https://github.com/ishwar6/ishwar-books/blob/main/code/papers/vllm/vllm_part4.py). It builds the block manager and runs parallel sampling, beam search and a shared prefix on it, each checked against `model.generate`. It measures the memory saved by sharing. It then simulates the scheduler with swapping and recomputation, and times both on the real model.

Last, it splits one layer over two simulated GPUs and tries two of the fused writes of §5.1. Every number is saved in `results/part4.json`. On an Apple M-series laptop it takes under a minute.

```bash
pip install torch transformers datasets
python vllm_part4.py   # downloads facebook/opt-125m (about 250 MB) and tatsu-lab/alpaca
```

<figure><img src="/img/papers/vllm/part4-run.png" alt="Terminal output of vllm_part4.py: parallel sampling and beam search on the block manager, the memory saved by sharing, the shared prefix, the scheduler simulation, swapping against recomputation, tensor parallelism and the fused kernels" loading="lazy" /><figcaption>The full output of vllm_part4.py, as it ran for this article.</figcaption></figure>

</details>

## The paper and the code

[vLLM on arXiv](https://arxiv.org/abs/2309.06180) · [vLLM on GitHub](https://github.com/vllm-project/vllm) · [our scripts for this part](https://github.com/ishwar6/ishwar-books/tree/main/code/papers/vllm)

