vLLM, explained · Part 5 of 6 · Covers §6 to §10, Figures 11 to 19

The Experiments

How the paper tests vLLM against FasterTransformer and three versions of Orca, how to read its latency plots, and what the ablations show. We rebuild the main experiments as a small serving simulation on real request lengths.

Efficient Memory Management for Large Language Model Serving with PagedAttention. Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph E. Gonzalez, Hao Zhang, Ion Stoica. SOSP 2023, 2023. arXiv:2309.06180

Parts 1 to 4 built the idea. Store each request's KV cache in small blocks, hand them out on demand, and share them when requests can. This part asks the question that decides whether any of it matters. On a real GPU with real requests, does vLLM serve more people at the same speed?

Each piece below shows the exact lines of the paper, then explains them. Next to the paper's numbers we put our own: a small serving simulator fed with real request lengths. Those numbers come from a laptop, not from the paper's A100 GPUs, and the page says so each time.

Parts 3 and 4 opened the boxes of vLLM one by one. This part closes them again. It treats the whole system as one machine: requests go in on the left, answers come out, and a stopwatch measures each request. The map below is the paper's Figure 4, redrawn. The highlighted scheduler, with its KV cache manager, is the piece that changes from one system to the next.

You are here: Part 5 tests the whole system from the outsideRequestsprompt lengthsfrom ShareGPTor Alpaca, atrandom timesSchedulerwhat the baselines replaceKV cache managerBlock tablesGPU block allocatorCPU block allocatorWorker 0Cache engineModel shardWorker 1Cache engineModel shardWorker N-1Cache engineModel shardMeasured outside: request rate in (requests per second), and for each request: time in the system / tokens written
The vLLM architecture, redrawn from the paper's Figure 4 as a map. Part 5 measures it from the outside. Each baseline keeps the workers and the model, and replaces the highlighted scheduler and memory manager with its own.

How a serving system is tested

Before we read the paper's tests, we need the shape of any serving test. It is the same for a web server, a database or a language model.

A serving test has three inputs. The first is the requests: for us, a prompt length and an answer length each. The second is the arrival times: when each request reaches the server. The third is the server itself, the system under test. The test keeps the first two fixed and swaps the third.

The test then reads two kinds of numbers. One is how much work the server finishes per second. The other is how long each user waits. The next two boxes name them.

A good server has both: high throughput and low latency. The two pull against each other. A server can raise its throughput by packing more requests into each step, but each request then waits longer. So the paper does not report one number. It reports a curve: latency at each request rate.

The test bench

Table 1 is a division: the memory for the KV cache over the size of one slot, from Part 2. A tiny case first. If one slot were 1 MB and the cache had 10 MB, there would be 10 slots. We check the real table with the real model configurations. The function gives the bytes of one slot; look at the last two columns of the output, ours and the paper's:

python
def kv_bytes_per_token(layers, hidden, bytes_per_value=2):
    """A key and a value (2) of `hidden` numbers in every layer, 2 bytes each in FP16."""
    return 2 * layers * hidden * bytes_per_value
plain text
== 1. Table 1: KV cache slots = memory for the KV cache / KV cache of one token
model     layers hidden  KB/token KV memory slots (GiB)  Table 1
OPT-13B       40   5120       800     12 GB      15,729    15.7K
OPT-66B       64   9216     2,304     21 GB       9,557     9.7K
OPT-175B      96  12288     4,608    264 GB      60,075    60.1K
our simulated server: 15,728 slots (OPT-13B on one A100); with 2048-token requests that is 7.68 requests
the same 15,728 slots of OPT-125M take 580 MB, so a laptop can hold them

Two rows match exactly once we read "GB" as binary gigabytes (GiB, 2302^{30} bytes). For OPT-66B we get 9,557 slots, a little under the table's 9.7K; the table probably rounds the memory. The first row is our server for the rest of this part: 15,728 slots. Only 7.68 requests of the full 2,048 tokens fit in it. Remember that number.

The workloads

The picture shows the difference. Both rows have the same average rate of 1 request per second. The top row is a metronome. The bottom row is one random draw of Poisson arrivals, from the same generator our simulator uses.

Thirty seconds of arrivals at an average of 1 request per secondevery secondevery second: 1.00 severy second: 2.00 severy second: 3.00 severy second: 4.00 severy second: 5.00 severy second: 6.00 severy second: 7.00 severy second: 8.00 severy second: 9.00 severy second: 10.00 severy second: 11.00 severy second: 12.00 severy second: 13.00 severy second: 14.00 severy second: 15.00 severy second: 16.00 severy second: 17.00 severy second: 18.00 severy second: 19.00 severy second: 20.00 severy second: 21.00 severy second: 22.00 severy second: 23.00 severy second: 24.00 severy second: 25.00 severy second: 26.00 severy second: 27.00 severy second: 28.00 severy second: 29.00 severy second: 30.00 s30 arrivalsPoissonPoisson: 3.12 sPoisson: 6.08 sPoisson: 6.14 sPoisson: 6.22 sPoisson: 8.03 sPoisson: 9.36 sPoisson: 10.47 sPoisson: 10.84 sPoisson: 11.77 sPoisson: 12.70 sPoisson: 13.57 sPoisson: 13.74 sPoisson: 14.31 sPoisson: 14.81 sPoisson: 16.09 sPoisson: 21.35 sPoisson: 24.34 sPoisson: 25.12 sPoisson: 25.71 sPoisson: 26.02 sPoisson: 26.06 sPoisson: 26.09 sPoisson: 26.71 sPoisson: 27.10 sPoisson: 27.58 sPoisson: 29.80 s26 arrivalsa gap of 5.3 s3 within 0.06 s051015202530time (seconds)
Regular arrivals against Poisson arrivals at the same average rate. The random row has clumps, three requests in less than a tenth of a second, and long quiet gaps. A server must absorb the clumps, so random arrivals are harder to serve than regular ones.

We repeat the counting on 4,000 requests of each dataset, with the OPT tokenizer. For ShareGPT we take the first question and its answer. The paper does not say exactly how it cut the conversations, so our ShareGPT numbers cannot match to the token:

plain text
== 2. Figure 11: prompt and output lengths (OPT tokenizer)
dataset   requests mean prompt mean output paper prompt paper output
ShareGPT      4000       148.0       294.3       161.31       337.99
Alpaca        4000        18.2        59.1        19.31        58.45
ShareGPT / Alpaca: prompts 8.1x longer, outputs 5.0x longer (paper: 8.4x and 5.8x)
Prompt and output lengths of our requests (OPT tokenizer)promptoutputShareGPT: mean prompt 148, mean output 294 tokens0500100015002000tokens (bins of 50)Alpaca: mean prompt 18, mean output 59 tokens0500100015002000tokens (bins of 50)
Our requests, counted with the OPT tokenizer. ShareGPT prompts and answers spread out to 2,000 tokens; Alpaca is packed near zero. Compare with the paper's Figure 11 above.

Alpaca matches closely: 18.2 and 59.1 tokens against the paper's 19.31 and 58.45. ShareGPT is near too, with 8.1 times longer prompts against the paper's 8.4. Note the long tail of ShareGPT answers: the unknown length of Part 2, now with real data.

The arrival times come from a few lines of code. Each gap is drawn from an exponential distribution with a mean of one over the rate. At 2 requests per second, the mean gap is half a second. The function adds the gaps one by one to get the arrival times:

python
def poisson(n, rate, seed):
    """Arrival times of n requests: gaps drawn from an exponential distribution with mean 1 / rate."""
    r, t, out = random.Random(seed), 0.0, []
    for _ in range(n):
        t += r.expovariate(rate); out.append(t)
    return out

The baselines

A baseline is the system you compare against. A new system is only as good as the strongest baseline it beats. The paper picks two families: the fastest engine of the day, and the best scheduler of the day.

The three Orca versions differ only in how much answer they book. Max books for the worst case, Pow2 books up to twice the real answer, and Oracle books the real answer. In our simulator, this function gives the slots each version books for a prompt of pp tokens and an answer of oo tokens. Then our buddy allocator rounds that up to a power of two:

python
def reserve(system, p, o):
    """Slots that an Orca version books for a request at admission (before the buddy allocator rounds it up)."""
    if system == 'Orca (Max)':
        return 2048                                            # the model's maximum sequence length
    if system == 'Orca (Pow2)':
        return p + (1 << (o - 1).bit_length())                 # output booked up to 2x: 25 -> 32
    return p + o                                               # Oracle: knows the real output length

A worked example. A request has a prompt of 19 tokens and an answer of 25. Oracle books 19+25=4419 + 25 = 44 slots, and the buddy allocator gives it 64. Pow2 books 19+32=5119 + 32 = 51, which also becomes 64. Max books 2,048.

With 16-token blocks, vLLM holds 2 blocks (32 slots) right after the prompt. At the end, after all 44 tokens, it holds 3 blocks (48 slots).

Memory set aside for one request: prompt 19 tokens, answer 25 tokenspromptanswer, writtenset aside but never usedFasterTransformer... 2,048 slotsOrca (Max)... 2,048 slotsOrca (Pow2)books 51buddy gives 64Orca (Oracle)books 44buddy gives 64vLLM3 blocks of 16 = 48taken one at a timeOne slot holds the keys and values of one token. Bars are drawn to scale up to 76 slots.
One request, five systems. Blue is the prompt, orange is the answer that the model really writes, and the dashed red part is memory set aside but never used. Only vLLM keeps the waste below one block.

The picture is the whole experiment in small. Every system writes the same 44 tokens. FasterTransformer and Orca (Max) block 2,048 slots to do it, about 46 times more than needed. Even the perfect guess of Oracle loses 20 slots to the buddy rounding. The vLLM bar loses 4, and it takes its blocks one at a time, as the answer grows.

Normalized latency

In symbols, with NN requests, arrival times aia_i, finish times fif_i and output lengths oio_i:

normalized latency=1N∑i=1Nfi−aioi\text{normalized latency} = \frac{1}{N} \sum_{i=1}^{N} \frac{f_i - a_i}{o_i}

Read it from left to right. It is an average over the NN requests. Each term is fi−aif_i - a_i, the time request ii spent waiting plus running, divided by its oio_i answer tokens.

A tiny example with three requests, small enough to check by hand:

requestarrivesfinishesanswer tokens(finish - arrive) / tokens
A0 s2 s1002 / 100 = 0.02
B1 s5 s504 / 50 = 0.08
C1.5 s3.5 s102 / 10 = 0.20

The mean is (0.02+0.08+0.20)/3=0.10(0.02 + 0.08 + 0.20) / 3 = 0.10 s/token. Request B waited in a queue, and its number is four times that of A. Request C wrote only 10 tokens, so each of its seconds weighs heavily. The short requests count as much as the long ones in the mean.

The paper says it focuses on throughput, but it plots latency. The two are linked. The throughput of a server, in the paper's sense, is the highest request rate it can take while the normalized latency stays low. A user never sees throughput. A user sees the wait for each token.

The simulator

We cannot run OPT-13B on an A100 here. We can rebuild the experiment's logic and keep the part that the paper is about: memory. Our simulator has five pieces.

  1. Requests: 1,000 real (prompt, answer) lengths from ShareGPT or Alpaca, with Poisson arrival times.
  2. Memory: 15,728 slots, the Table 1 budget of OPT-13B on one A100.
  3. Five ways to store the cache: FasterTransformer, three Orca versions with a real buddy allocator, and vLLM. Its 16-token blocks come with preemption by recomputation (Part 4, and the box below).
  4. A scheduler: first come, first served, at most 256 running requests, as in vLLM's default setting.
  5. A clock: each iteration costs a time from a step-time model measured on our laptop.

A step with more requests, or with longer caches, takes longer. We time real decode steps of OPT-125M on the laptop GPU for many batch sizes and cache lengths, and fit a straight line:

python
def step_time(n_decode, cached, prompt_tokens):
    """One iteration: the fixed cost, plus each decoding request, plus each cached token it reads, plus prompt tokens."""
    return A_STEP + B_REQ * n_decode + C_TOK * cached + E_PRE * prompt_tokens
plain text
== 3. Step-time model: OPT-125M on the laptop GPU (FP16, fastest of 15 runs)
batch context decode step ms
    1      64          10.47
    1     512          11.88
    1    1024          13.14
    8      64          12.40
    8     512          14.01
    8    1024          21.82
   32      64          16.91
   32     512          32.51
   32    1024          60.79
   64      64          25.13
   64     256          31.63
   64     512          73.90
  128      64          25.64
  128     256          81.49
fit: decode step = 8.62 ms + 78.0 us per request + 1667.8 ns per cached token (largest error of the fit 29%)
prompt pass ms for 64, 128, 256, 512, 1024 tokens: 12.3, 14.3, 16.1, 32.2, 49.8
fit: prompt pass = 8.83 ms + 40.6 us per prompt token

One decode step costs 8.62 ms even for a single request: the fixed cost of a pass through the model, which batching shares. Each cached token adds about 1.7 microseconds, because attention must read it. The fit is off by up to 29%, and the laptop was busy with other work. So treat our seconds as a shape, not as a server measurement.

The heart of the simulator is the vLLM path. Before each iteration, every running request needs room for one more token. If a new block is needed and none is free, the latest arrival gives up all its blocks. It goes back to the front of the queue.

A small case shows the rule. Say 2 blocks are free, and three running requests each need a new block. The first two get them. The third finds none, so the request that arrived last is preempted, and its blocks pay for the third. In the code, need is the number of new blocks a request needs, free the free blocks, and hold the blocks each request holds:

python
        if paged:                                              # room for one more token in each running request
            k = 0
            while k < len(running):
                i = running[k]
                need = -(-(P[i] + gen[i] + 1) // block) - hold[i]
                while need > free and running[-1] != i:        # preempt the latest arrival: free all its blocks
                    v = running.pop(); free += hold.pop(v); waiting.appendleft(v); preempt += 1; preempted = True
                if need > free:                                # i itself is the latest arrival
                    running.pop(); free += hold.pop(i); waiting.appendleft(i); preempt += 1; preempted = True
                    break
                free -= need; hold[i] += need; k += 1

The expression -(-x // block) is the number of blocks that xx tokens need, rounded up. For 17 tokens and blocks of 16, it gives 2. In the Orca path there is no such loop. A request joins only if the buddy allocator finds a chunk for its whole reservation, and it never needs more.

Figure 12: latency against request rate

How to read a latency plot

The paper's main figures all have the same shape, so it pays to learn to read one first. The picture below is drawn on our own ShareGPT run, with only two systems. Read the four numbered marks in order.

How to read a latency plot (our ShareGPT run, two systems)0.000.250.500.751.00012345request rate: the load (requests per second)s/tokenOrca (Oracle), 0.25: 0.010Orca (Oracle), 0.5: 0.011Orca (Oracle), 1: 0.012Orca (Oracle), 1.5: 0.015Orca (Oracle), 2: 0.033Orca (Oracle), 2.5: 0.363vLLM, 0.25: 0.010vLLM, 0.5: 0.011vLLM, 1: 0.012vLLM, 1.5: 0.015vLLM, 2: 0.018vLLM, 2.5: 0.024vLLM, 3: 0.076vLLM, 3.5: 0.401vLLM, 4: 0.8091234Orca (Oracle)vLLM1Flat floor: nobody waits.0.010 s to write a token.2Knee: the batch is full,and a queue starts.3Wall: requests come infaster than they leave.4Further right is better:more users on one GPU.Lines that leave the topare cut, as in the paper.
Anatomy of a latency plot. (1) At low load every system sits on the same flat floor. (2) At the knee the batch is full and a queue starts. (3) Past the knee the line becomes a wall. (4) The system whose knee is further right serves more users on the same GPU.

The horizontal axis is the load: requests per second. The vertical axis is the normalized latency: how slow each token feels to a user. A point on a line answers one question. If users arrive at this rate, how slow does this system feel?

On the floor, the server has spare room. Each request is served at once, and the latency is just the time to compute a token. At the knee, the batch is as large as memory allows, and newcomers start to wait. The wall follows: the queue grows, and so does every wait. So the plot is not about the height of the lines. It is about where each line leaves the floor.

The paper's plot

Why the bend is so sharp

The simplest queue has one cashier and random arrivals. Customers arrive at a rate λ\lambda (lambda) per minute, and the cashier serves μ\mu (mu) per minute on average, also at random. Queueing theory gives the mean time a customer spends in the shop, queue and checkout together:

W=1μ−λW = \frac{1}{\mu - \lambda}

Read it from left to right. WW is the mean time in the shop. The bottom, μ−λ\mu - \lambda, is the spare speed of the cashier: how many more customers a minute it could serve. The formula holds only while λ<μ\lambda < \mu.

A worked example with a cashier who serves μ=10\mu = 10 customers a minute. At λ=5\lambda = 5, W=1/5W = 1/5 of a minute, or 12 seconds. At λ=8\lambda = 8, W=1/2W = 1/2 minute, 30 seconds. At λ=9\lambda = 9, W=1W = 1 minute. At λ=9.9\lambda = 9.9, W=10W = 10 minutes. The last 10% of load costs far more than the first 90%.

One cashier, 10 customers a minute: why the curve bends so sharplycashierthe queueCustomers arrive at random.Below 10 a minute, the queue empties now and then.At 10 or more, it never empties again.0123450246810capacity: 105 a minute: 0.20 min5/min: 12 s8 a minute: 0.50 min8/min: 30 s9 a minute: 1.00 min9/min: 60 scustomers arriving per minuteminutes in the shop
The cashier's queue from the formula above. The mean time in the shop stays low up to about half the cashier's speed, then climbs ever faster, and has no limit at 10 customers a minute. It is the same shape as each line in Figure 12.

A language model server is not a single cashier. It serves a whole batch at once, and its speed changes with the batch. But the shape carries over. Its "cashier speed" is the rate at which its memory lets requests through. vLLM raises that speed, because more requests fit in memory. So its wall moves to the right.

Here is our simulator on the same experiment. Each point is a run of 1,000 requests. We use OPT-125M step times and the 15,728 slots of OPT-13B. Each row is one request rate, and each column one system. Read down a column: the number stays near 0.01, then jumps. Look at which column jumps first:

plain text
== 4. Figure 12 rebuilt: normalized latency (s/token) against request rate, 1000 requests per point, 15,728 slots
normalized latency = mean over requests of (finish time - arrival time) / output tokens
ShareGPT:
 req/s FasterTransformer        Orca (Max)       Orca (Pow2)     Orca (Oracle)              vLLM
  0.25             0.089             0.010             0.010             0.010             0.010
   0.5             2.759             0.011             0.011             0.011             0.011
     1            13.667             0.014             0.013             0.012             0.012
   1.5            17.891             0.086             0.027             0.015             0.015
     2            20.039             1.445             0.488             0.033             0.018
   2.5            21.222             2.587             1.581             0.363             0.024
     3            22.011             3.355             2.358             1.081             0.076
   3.5            22.575             3.904             2.887             1.640             0.401
     4            22.998             4.321             3.267             2.000             0.809
     5            23.589             4.907             3.846             2.573             1.345
     6            23.984             5.298             4.261             2.968             1.727
     8            24.477             5.788             4.741             3.415             2.197
Alpaca:
 req/s FasterTransformer        Orca (Max)       Orca (Pow2)     Orca (Oracle)              vLLM
     5             1.959             0.010             0.010             0.010             0.010
    10             5.701             0.031             0.010             0.010             0.010
    20             7.607             1.391             0.012             0.012             0.012
    30             8.242             2.020             0.015             0.015             0.015
    40             8.559             2.336             0.055             0.019             0.019
    60             8.742             2.652             0.307             0.095             0.029
    80             8.964             2.810             0.448             0.213             0.053
   100             9.059             2.905             0.523             0.292             0.096
   120             9.115             2.968             0.573             0.357             0.131
   140             9.117             3.013             0.624             0.395             0.164
   160             9.152             3.047             0.650             0.426             0.188
   200             9.200             3.095             0.692             0.468             0.225
FasterTransformerOrca (Max)Orca (Pow2)Orca (Oracle)vLLMShareGPT0.000.250.500.751.0002468request rate (requests per second)FasterTransformer, 0.25: 0.089Orca (Max), 0.25: 0.010Orca (Max), 0.5: 0.011Orca (Max), 1: 0.014Orca (Max), 1.5: 0.086Orca (Pow2), 0.25: 0.010Orca (Pow2), 0.5: 0.011Orca (Pow2), 1: 0.013Orca (Pow2), 1.5: 0.027Orca (Pow2), 2: 0.488Orca (Oracle), 0.25: 0.010Orca (Oracle), 0.5: 0.011Orca (Oracle), 1: 0.012Orca (Oracle), 1.5: 0.015Orca (Oracle), 2: 0.033Orca (Oracle), 2.5: 0.363vLLM, 0.25: 0.010vLLM, 0.5: 0.011vLLM, 1: 0.012vLLM, 1.5: 0.015vLLM, 2: 0.018vLLM, 2.5: 0.024vLLM, 3: 0.076vLLM, 3.5: 0.401vLLM, 4: 0.809Alpaca0.000.250.500.751.00050100150200request rate (requests per second)Orca (Max), 5: 0.010Orca (Max), 10: 0.031Orca (Pow2), 5: 0.010Orca (Pow2), 10: 0.010Orca (Pow2), 20: 0.012Orca (Pow2), 30: 0.015Orca (Pow2), 40: 0.055Orca (Pow2), 60: 0.307Orca (Pow2), 80: 0.448Orca (Pow2), 100: 0.523Orca (Pow2), 120: 0.573Orca (Pow2), 140: 0.624Orca (Pow2), 160: 0.650Orca (Pow2), 200: 0.692Orca (Oracle), 5: 0.010Orca (Oracle), 10: 0.010Orca (Oracle), 20: 0.012Orca (Oracle), 30: 0.015Orca (Oracle), 40: 0.019Orca (Oracle), 60: 0.095Orca (Oracle), 80: 0.213Orca (Oracle), 100: 0.292Orca (Oracle), 120: 0.357Orca (Oracle), 140: 0.395Orca (Oracle), 160: 0.426Orca (Oracle), 200: 0.468vLLM, 5: 0.010vLLM, 10: 0.010vLLM, 20: 0.012vLLM, 30: 0.015vLLM, 40: 0.019vLLM, 60: 0.029vLLM, 80: 0.053vLLM, 100: 0.096vLLM, 120: 0.131vLLM, 140: 0.164vLLM, 160: 0.188vLLM, 200: 0.225normalized latency (s/token), simulated: OPT-125M step times from our laptop, 15,728 KV slots
Our simulation of Figure 12, cut at 1.0 s/token as in the paper. The order of the bends is the paper's order: FasterTransformer, then Orca (Max), Orca (Pow2), Orca (Oracle) and vLLM. FasterTransformer on Alpaca is above 1.0 s/token even at 5 requests per second, so its line is off the chart.

At low load, all four iteration-level systems give the same 0.010 s/token on ShareGPT: when nobody waits, memory management does not matter. Then the bends appear in the paper's order. To turn bends into "times higher", we draw a line at 0.1 s/token, about ten times the unloaded latency. Then we read where each curve crosses it:

python
def crossing(rates, vals, limit=LIMIT):
    """The rate at which the curve first rises above the limit, read between the two points around it."""
    if vals[0] > limit:
        return 0.0
    for (r0, v0), (r1, v1) in zip(zip(rates, vals), zip(rates[1:], vals[1:])):
        if v1 > limit:
            return r0 + (r1 - r0) * (limit - v0) / (v1 - v0)
    return float('inf')
plain text
request rate where normalized latency crosses 0.1 s/token (our "same latency" line, linear between points):
ShareGPT  FasterTransformer 0.3, Orca (Max) 1.5, Orca (Pow2) 1.6, Orca (Oracle) 2.1, vLLM 3.0
          vLLM / Orca (Oracle) = 1.4x, vLLM / Orca (Pow2) = 1.9x, vLLM / Orca (Max) = 2.0x
Alpaca    FasterTransformer < 5, Orca (Max) 10.5, Orca (Pow2) 43.6, Orca (Oracle) 60.8, vLLM 102.3
          vLLM / Orca (Oracle) = 1.7x, vLLM / Orca (Pow2) = 2.3x, vLLM / Orca (Max) = 9.7x
paper, ShareGPT: vLLM sustains 1.7x to 2.7x the rate of Orca (Oracle), 2.7x to 8x that of Orca (Max), up to 22x that of FasterTransformer
0.00.10.20.30.40.501234request rate (requests per second)s/tokenOrca (Oracle), 0.25: 0.010Orca (Oracle), 0.5: 0.011Orca (Oracle), 1: 0.012Orca (Oracle), 1.5: 0.015Orca (Oracle), 2: 0.033Orca (Oracle), 2.5: 0.363vLLM, 0.25: 0.010vLLM, 0.5: 0.011vLLM, 1: 0.012vLLM, 1.5: 0.015vLLM, 2: 0.018vLLM, 2.5: 0.024vLLM, 3: 0.076vLLM, 3.5: 0.401our line: 0.1 s/token2.13.0Orca (Oracle)crosses at 2.1 req/svLLMcrosses at 3.0 req/s3.0 / 2.1 = 1.4x the rateReading a panel: pick a latency, see which rate each system reaches (ShareGPT, our run)
How to read "times higher". Fix a latency (the dashed line), find where each curve crosses it, and divide the two rates. On our ShareGPT run, Orca (Oracle) crosses at 2.1 requests per second and vLLM at 3.0.

The choice of 0.1 s/token is ours; the paper does not give the latency level it used. Another line would give other ratios, but in our table the order of the systems is the same at every rate.

How much faster, and why

Our simulator gives the same bars. We let all 1,000 requests arrive at time 0, so the queue is never empty, and we count the running requests at each iteration. We also check the count with a second method. When memory is full, the slots held by the running requests add up to the budget. A request stays in the batch for oo steps, so a running request is a long request more often than a short one. That gives a closed form:

batch≈S⋅∑ioi∑i∑g=1oimi(g)\text{batch} \approx S \cdot \frac{\sum_i o_i}{\sum_i \sum_{g=1}^{o_i} m_i(g)}

Read it from left to right. SS is the budget, 15,728 slots. The top sum adds up the answer lengths, so it counts request-steps. The bottom sum adds up mi(g)m_i(g), the slots that request ii holds after writing gg tokens, over its whole life.

The fraction is one over the slots of an average running request. For Orca, mi(g)m_i(g) is its buddy chunk at every step; for vLLM, the blocks it holds so far.

A tiny example. Two requests, with answers of 1 and 3 tokens. Each holds 4 slots at every step. The sums are 1+3=41 + 3 = 4 request-steps and 4⋅1+4⋅3=164 \cdot 1 + 4 \cdot 3 = 16 slot-steps, so a running request holds 4 slots on average. With S=40S = 40, the batch is 40⋅4/16=1040 \cdot 4 / 16 = 10.

python
def closed_form_batch(system, reqs, block=16, slots=S):
    """Method 2: when memory is full, the slots held by the running requests add up to the budget. A request is
    running for o steps, so a random running request is picked in proportion to o. Fragmentation is ignored."""
    held = 0
    for p, o in reqs:
        if system == 'vLLM':
            held += sum(block * -(-(p + g) // block) for g in range(1, o + 1))   # blocks grow as it writes
        else:
            held += o * (1 << (reserve(system, p, o) - 1).bit_length())         # one chunk for its whole life
    return slots * sum(o for _, o in reqs) / held
plain text
== 5. Figure 13 rebuilt: requests running at once while the queue is never empty (all arrive at time 0)
ShareGPT: system             simulated closed form tokens/step  tokens/s preemptions
          Orca (Max)              7.00        7.68         6.9       495           0
          Orca (Pow2)             9.30       10.55         9.1       583           0
          Orca (Oracle)          14.91       17.08        14.5       731           0
          vLLM                   37.54       38.02        34.8       952        1443
          vLLM against Orca (Oracle): 2.4x the tokens per step, 1.3x the tokens per second (bigger batches make each step slower)
          vLLM runs 2.5x the requests of Orca (Oracle) and 5.4x those of Orca (Max)
Alpaca: system             simulated closed form tokens/step  tokens/s preemptions
          Orca (Max)              7.00        7.68         6.9       678           0
          Orca (Pow2)            43.98       46.55        36.6     2,211           0
          Orca (Oracle)          75.91       82.34        57.3     2,723           0
          vLLM                  204.01      183.95       103.9     3,296         274
          vLLM against Orca (Oracle): 1.8x the tokens per step, 1.2x the tokens per second (bigger batches make each step slower)
          vLLM runs 2.7x the requests of Orca (Oracle) and 29.1x those of Orca (Max)
paper, Figure 13 (OPT-13B, A100): ShareGPT 7.00, 9.81, 13.62, 30.42; Alpaca 7.00, 43.24, 72.75, 132.44
note: we cap a batch at 256 requests, as vLLM did by default
Requests in the batch when the queue is never emptyour simulationpaper (A100)ShareGPTOrca (Max): 7.007.0Orca (Max): 7.007.0(Max)Orca (Pow2): 9.309.3Orca (Pow2): 9.819.8(Pow2)Orca (Oracle): 14.9115Orca (Oracle): 13.6214(Oracle)vLLM: 37.5438vLLM: 30.4230vLLMAlpacaOrca (Max): 7.007.0Orca (Max): 7.007.0(Max)Orca (Pow2): 43.9844Orca (Pow2): 43.2443(Pow2)Orca (Oracle): 75.9176Orca (Oracle): 72.7573(Oracle)vLLM: 204.01204vLLM: 132.44132vLLMOrca labels: (Max), (Pow2), (Oracle). Our batch is capped at 256 requests.
Requests in the batch, our simulation next to the paper's Figure 13. The Orca bars are close to the paper's on both datasets. Our vLLM bars are higher than the paper's, most of all on Alpaca.

Orca (Max) gives exactly 7.00, as in the paper. The closed form says 7.68, and the gap is the buddy allocator. The budget of 15,728 is not a power of two, so it is split into pieces of 8,192, 4,096 and fewer slots. Only seven chunks of 2,048 fit in them. That lost 0.68 of a request is external fragmentation: free memory cut into pieces too small to use. It appears on its own.

For Orca (Pow2) and Orca (Oracle), the simulation sits 5% to 13% below the closed form: chunks of mixed sizes leave holes. For vLLM on ShareGPT, the two methods agree within 1.3%, because equal blocks leave no holes. On Alpaca, the 256-request cap and the 274 preemptions break the formula's assumption of a steady, full memory.

Our Orca bars are close to the paper's: 9.30 against 9.81, 14.91 against 13.62, 43.98 against 43.24, 75.91 against 72.75. Memory counts depend only on lengths and budget, so a laptop can get them right. Our vLLM bars are higher, 37.54 against 30.42 and 204 against 132, because a real server has limits that we leave out.

The picture below puts the ShareGPT bars into memory. Each bar is the same 15,728 slots. It is cut into one piece per running request, and the blue part of each piece is what an average running request really holds.

The same 15,728 slots of KV cache, ShareGPT, the queue never empty (our simulation)Orca (Max)1,392 slots left, too small for a chunk7 requests at onceOrca (Oracle)14.91 requests at oncevLLM37.54 requests at onceheld by an average running request (419 slots = 15,728 / 37.54)booked but empty, or holes
Before vLLM and with vLLM, on the same memory. Orca (Max) cuts it into 7 chunks of 2,048 slots, mostly empty, and 1,392 slots are left over, too small for an eighth chunk. Orca (Oracle) fits about 15 requests, with empty room and holes in each. vLLM fills the memory with about 37 requests.

The blue part is the same size in all three bars: about 419 slots, or 15,728 divided by vLLM's 37.54 requests. That is fair, because a running request holds the same tokens whatever system serves it. Only the empty part around it changes. Remove the empty part, and the same memory holds 5.4 times as many requests as Orca (Max).

Now the reason our speed gains are smaller. On ShareGPT, vLLM writes 2.4 times as many tokens per step as Orca (Oracle), but only 1.3 times as many per second. On our laptop, a step with 38 requests and their caches takes much longer than a step with 15. On an A100, each step must read 26 GB of weights, a fixed cost that a bigger batch shares. The next box shows what happens when that stops being true.

We rebuild the parallel sampling bars two ways. Method 1 is a small block manager with reference counts and copy-on-write, as in Part 4. Method 2 is a closed form. After the first step, only the ⌊p/16⌋\lfloor p / 16 \rfloor full prompt blocks stay shared, so with nn samples and ℓ=p+g\ell = p + g tokens each:

blocks without sharing=n⌈ℓ16⌉,blocks with sharing=⌊p16⌋+n(⌈ℓ16⌉−⌊p16⌋)\text{blocks without sharing} = n \left\lceil \frac{\ell}{16} \right\rceil, \qquad \text{blocks with sharing} = \left\lfloor \frac{p}{16} \right\rfloor + n \left( \left\lceil \frac{\ell}{16} \right\rceil - \left\lfloor \frac{p}{16} \right\rfloor \right)

Read it this way. ⌈ℓ/16⌉\lceil \ell / 16 \rceil is the blocks one sample needs for ℓ\ell tokens, rounded up. Without sharing, each of the nn samples has all of them. With sharing, the full prompt blocks are stored once, and each sample keeps only its own blocks after them.

A tiny example: p=18p = 18, two samples, each with 6 new tokens, so ℓ=24\ell = 24. Without sharing, 2⋅2=42 \cdot 2 = 4 blocks. With sharing, 1+2⋅(2−1)=31 + 2 \cdot (2 - 1) = 3 blocks. That saves 1 block of 4, or 25%, at this step.

python
def sharing_refcount(p, o, n, block=16):
    """Method 1: a block manager. The prompt blocks are mapped by all n samples (reference count n). When a sample
    writes into a block that others still map, it gets its own copy first (copy-on-write). Each step we count the
    physical blocks in use and the blocks that n separate copies would need."""
    ref, nxt = {}, 0

    def new_block():
        nonlocal nxt
        ref[nxt] = 1; nxt += 1
        return nxt - 1
    prompt_blocks = [new_block() for _ in range(-(-p // block))]
    for b in prompt_blocks:
        ref[b] = n
    tables, length = [list(prompt_blocks) for _ in range(n)], [p] * n
    with_sharing = without = 0
    for _ in range(o):                                         # each step, every sample writes one token
        for s in range(n):
            if length[s] % block == 0:
                tables[s].append(new_block())                 # the last block is full: take a fresh one
            elif ref[tables[s][-1]] > 1:                       # shared and about to change: copy-on-write
                ref[tables[s][-1]] -= 1; tables[s][-1] = new_block()
            length[s] += 1
        with_sharing += sum(1 for c in ref.values() if c > 0)
        without += sum(len(t) for t in tables)
    return with_sharing, without
plain text
== 6. Figure 15a rebuilt: memory saved by sharing prompt blocks in parallel sampling (block size 16)
ShareGPT  2 samples: saved 20.74% (block manager), 20.74% (closed form)
ShareGPT  4 samples: saved 31.10% (block manager), 31.10% (closed form)
ShareGPT  6 samples: saved 34.56% (block manager), 34.56% (closed form)
Alpaca    2 samples: saved  4.51% (block manager),  4.51% (closed form)
Alpaca    4 samples: saved  6.76% (block manager),  6.76% (closed form)
Alpaca    6 samples: saved  7.52% (block manager),  7.52% (closed form)
paper, Figure 15a (Alpaca): 6.09%, 8.53%, 9.79%; §6.3 (ShareGPT): 16.2% to 30.5%
assumption: all samples of a request write as many tokens as the dataset answer (real samples differ)

The block manager and the formula agree to every digit. Our Alpaca savings, 4.51% to 7.52%, are a little under the paper's 6.09% to 9.79%. Our ShareGPT savings, 20.74% to 34.56%, are a little over its 16.2% to 30.5%. The pattern is the same: more samples save more, with diminishing returns, and long prompts save far more. One assumption shapes our numbers: every sample writes as many tokens as the dataset's answer, while real samples stop at different times. We did not rebuild beam search, whose sharing depends on the model's choices.

Shared prefixes and chatbots

The cost of the indirection

An ablation test removes or changes one part of a system to see what that part contributes. Section 7 asks what vLLM's design costs and which settings are right.

Block size

Our simulator can show only one side of this tug of war. It counts memory exactly, but its step time does not depend on the block size, so tiny blocks cost nothing in it. We run vLLM with block sizes 1 to 256, at the rate where 16-token blocks reach our 0.1 s/token line:

plain text
== 7. Figure 18b rebuilt: vLLM in the simulator with block sizes 1 to 256 (memory only, no kernel cost)
ShareGPT at 3.0 req/s: 1: 0.072, 2: 0.073, 4: 0.072, 8: 0.074, 16: 0.076, 32: 0.080, 64: 0.085, 128: 0.107, 256: 0.150
Alpaca at 102.3 req/s: 1: 0.084, 2: 0.085, 4: 0.086, 8: 0.092, 16: 0.100, 32: 0.114, 64: 0.148, 128: 0.221, 256: 0.392
vLLM with different block sizes (our simulator, memory effects only)ShareGPTAlpaca0.00.10.20.30.41248163264128256block size (tokens)s/tokenShareGPT, 1: 0.072ShareGPT, 2: 0.073ShareGPT, 4: 0.072ShareGPT, 8: 0.074ShareGPT, 16: 0.076ShareGPT, 32: 0.080ShareGPT, 64: 0.085ShareGPT, 128: 0.107ShareGPT, 256: 0.150Alpaca, 1: 0.084Alpaca, 2: 0.085Alpaca, 4: 0.086Alpaca, 8: 0.092Alpaca, 16: 0.100Alpaca, 32: 0.114Alpaca, 64: 0.148Alpaca, 128: 0.221Alpaca, 256: 0.392fixed rates: ShareGPT 3.0 req/s, Alpaca 102.3 req/s
Our simulator with block sizes 1 to 256. Without a kernel cost, small blocks are free, so only the right side of the paper's Figure 18b appears: large blocks hurt, and they hurt short Alpaca requests far more.

The right side of the paper's figure appears clearly. From 16 to 256, Alpaca's latency grows almost four times, from 0.100 to 0.392 s/token. ShareGPT's grows by about half, from 0.076 to 0.150. Short requests suffer more from large blocks, as the paper says.

The left side does not appear, and that is the lesson. In our simulator, block size 1 is the best. The paper's high latency at block sizes 1 to 4 comes from the GPU kernel, which we did not model. So memory alone pushes toward small blocks, and the GPU kernel sets the lower limit.

Recompute or swap

We time both on the laptop. We take the real KV cache of OPT-125M after a 1,024-token prompt. We copy it to CPU memory and back, one block of each layer at a time, for block sizes 1 to 256. Then we time one prompt pass that rebuilds the same cache:

python
for b in BS:
    def out():
        for g, c in zip(gpu, cpu):
            for j in range(0, CTX, b):
                c[:, :, j:j + b].copy_(g[:, :, j:j + b])

    def back():
        for g, c in zip(gpu, cpu):
            for j in range(0, CTX, b):
                g[:, :, j:j + b].copy_(c[:, :, j:j + b])
    t_out, t_in = fastest(out, 3), fastest(back, 3)
plain text
== 8. Figure 19a rebuilt: move a 1,024-token KV cache (OPT-125M, FP16) GPU -> CPU -> GPU, block by block,
       against recomputing it with one prompt pass (laptop, fastest of 3 runs)
KV cache: 37.7 MB in 24 tensors; recompute (one prompt pass): 21.1 ms
block  copies swap out ms swap in ms
    1  24,576      7350.2     5298.7
    2  12,288      2826.4     2787.9
    4   6,144      1278.6     1217.5
    8   3,072       716.2      577.4
   16   1,536       351.9      325.7
   32     768       131.6      165.3
   64     384       126.7      151.3
  128     192        56.5       56.4
  256      96        29.2       29.4
swap in + out against recompute: 599x slower at block size 1, 2.8x at block size 256; never faster on this laptop
Bring back a 1,024-token KV cache on our laptop (37.7 MB, OPT-125M)swap out + swap inrecompute (one prompt pass)101001,00010,0001248163264128256block size (tokens)ms (log)swap, 1: 12648.956swap, 2: 5614.308swap, 4: 2496.038swap, 8: 1293.582swap, 16: 677.537swap, 32: 296.897swap, 64: 277.922swap, 128: 112.974swap, 256: 58.575recompute, 1: 21.130recompute, 2: 21.130recompute, 4: 21.130recompute, 8: 21.130recompute, 16: 21.130recompute, 32: 21.130recompute, 64: 21.130recompute, 128: 21.130recompute, 256: 21.130
Our laptop version of Figure 19a, on a log scale. Swapping gets cheaper as blocks grow, because there are fewer copies. Recomputing does not depend on the block size at all.

The shape is the paper's. With 1-token blocks, the cache becomes 24,576 copies: 7,350 ms to move it out and 5,299 ms to move it back. With 256-token blocks it is 96 copies, 29.2 ms out and 29.4 ms back. The start-up cost of each copy dominates. Recomputation takes 21.1 ms at every block size.

The ending differs. On the A100, swapping wins at large blocks. On our laptop, recomputation wins at every size, by 2.8 times even at 256. An Apple laptop has no PCIe link, each small copy is a separate GPU command, and a 125M model recomputes 1,024 tokens very quickly. So the winner depends on the hardware, which is why vLLM supports both.

What the idea is good for

The conclusion

The limits

Some limits are the paper's. Orca was not public, so the authors rebuilt it with an assumed buddy allocator. The largest numbers, 8× and 22×, compare against Orca (Max) and FasterTransformer; against the best possible Orca the ShareGPT gain is 1.7× to 2.7×. Arrival times are random, while real traffic comes in bursts. And the gain shrinks when memory is not the limit, as Figure 12 (f) and §8 say.

Some limits are ours. The simulator is a model, not vLLM. Its clock comes from OPT-125M on a busy laptop, with a fit that is off by up to 29%. It also leaves out some limits of a real server. On our laptop a larger batch makes each step much slower than on an A100, so our speed gains are smaller than the paper's. What our runs show reliably is the memory side: how many requests fit, and why.

Next, in Part 6: build it from scratch. A small paged KV cache and serving loop in Python, checked against a library model.

Run it yourself

The script behind this part is code/papers/vllm/vllm_part5.py. It checks Table 1 and counts the lengths of ShareGPT and Alpaca requests. It times OPT-125M steps on the laptop GPU and fits a step-time model. Then it runs the serving simulator for five systems and checks its batch sizes with a closed form.

Last, it counts the blocks of parallel sampling two ways, sweeps the block size, and times swapping against recomputing. Every number is saved in results/part5.json. On an Apple M-series laptop it takes a few minutes after the downloads. The timings change from run to run.

bash
pip install torch transformers datasets numpy
python vllm_part5.py   # downloads facebook/opt-125m, two OPT configs, tatsu-lab/alpaca and the ShareGPT file (about 670 MB)
Terminal output of vllm_part5.py: Table 1, the dataset lengths, the step-time model, the latency table of five systems, the batch sizes, the sharing savings, the block sizes and the swap timings
The first 60 lines of the output of vllm_part5.py, as it ran for this article. The full log is results/part5_stdout.txt.

The paper and the code

vLLM on arXiv · vLLM on GitHub · our scripts for this part