vLLM / PagedAttention (SOSP 2023)

01 · THE PROBLEM

The KV cache dominates memory in LLM serving

Serving a large language model is expensive: according to recent estimates cited in the paper, processing an LLM request can cost ten times more than a traditional keyword query. For this reason, increasing throughput, and with it reducing the custo per request, is becoming more important.

Throughput can be raised by grouping several requests into a batch. However, the number of requests that fit together in the batch is still limited by GPU memory, above all by the space for the KV cache, and so the system's throughput is memory-bound.

In the paper's example, a 13B-parameter LLM on an NVIDIA A100 GPU with 40GB reserves about 65% of memory for the weights, which stay static during serving, and close to 30% for the requests' dynamic states. For a Transformer, these states are the attention keys and values, the KV cache.

The KV cache per token is large. In OPT-13B it takes 800 KB per token, and since the model generates sequences of up to 2048 tokens, a single request can need up to 1.6 GB. Even dedicating all available memory to the KV cache, only a few dozen requests would fit.

Two characteristics make this cache hard to manage: it grows and shrinks dynamically as the model generates tokens, and its lifetime and size are not known in advance.

02 · HOW IT WORKED BEFORE

Contiguous reservation and iteration-level scheduling

Earlier systems store each request's KV cache in a contiguous tensor, because most deep learning frameworks require tensors in contiguous memory. Since the output is unpredictable, they statically allocate a chunk based on the maximum possible sequence length, whatever the actual size of the input or output.

This creates three sources of waste: slots reserved for future tokens, internal fragmentation from oversizing for the maximum length, and external fragmentation from the memory allocator, such as the buddy allocator. The whole chunk stays reserved for the life of the request, and shorter requests cannot use the unused part.

In the paper's measurements, only between 20.4% and 38.2% of KV cache memory held actual token states in the existing systems.

There are also fine-grained scheduling techniques, such as iteration-level scheduling, that operate per iteration: after each one, finished requests leave the batch and new ones enter. This way, a new request waits only one iteration, not the whole batch. The paper also describes that vLLM selects the candidate sequences for the batch at each decoding iteration.

1. The request arrives through the frontend at the scheduler. With iteration-level scheduling, finished requests leave the batch and new ones enter at each iteration.

2. For each request, the system reserves in GPU memory a contiguous chunk sized by the maximum possible sequence length, whatever the actual size.

3. While the request lives, the whole chunk stays reserved and shorter requests cannot use the part that has not been used yet.

03 · PAGEDATTENTION

Virtual memory for the KV cache

PagedAttention divides each request's KV cache into blocks, and each block stores the keys and values of a fixed number of tokens. These blocks can sit in non-contiguous physical memory. The paper's analogy is operating-system virtual memory: blocks play the role of pages, tokens that of bytes, and requests that of processes.

The KV cache manager maintains block tables, which link each request's logical blocks to physical blocks. Logical blocks are filled from left to right, and separating logical from physical allows the cache to grow on demand, without reserving all positions up front. According to the paper, this eliminates most of the waste in existing systems.

vLLM is a complete serving system, with a FastAPI frontend and a GPU inference engine. Its centralized scheduler coordinates the execution of the distributed GPU workers, and the KV cache manager takes care of physical memory through the instructions it receives from the scheduler.

1. In prefill, the manager reserves only the blocks the prompt needs, not the maximum length. In the paper's example, a seven-token prompt uses two logical blocks, mapped to two physical blocks.

2. In the first decoding step, the cache of the new token fits in the last logical block, which still had a free position.

3. In the next step the last block is full: the manager allocates a new physical block and records the mapping in the block table.

4. At each step, the scheduler prepares a message with the token IDs and the block table of each request and sends it to the workers, which read the KV cache according to that table.

Because a new physical block is allocated only when all the previous ones are full, vLLM limits each request's waste to one block. When a request finishes, its blocks are released for other requests. The paper adds that relatively small blocks allocated on demand alleviate internal fragmentation, and that equal-sized blocks eliminate external fragmentation.

Block size is a design choice. If it is too small, vLLM may not exploit all the GPU's parallelism when reading and processing the KV cache; if it is too large, internal fragmentation increases and the chance of sharing decreases. The paper adopts 16 as the default, finding that value large enough to use the GPU well and small enough to avoid significant internal fragmentation in most workloads.

04 · SHARING BLOCKS

Reference counting and copy-on-write

In parallel sampling, a request generates several outputs from the same prompt, so the prompt's KV cache can be shared. In the paper's example with two outputs, the logical blocks of the prompt of both are mapped to the same physical blocks.

Because a physical block can be mapped to several logical blocks, vLLM keeps a reference count per physical block. For blocks that several sequences need to modify, it uses copy-on-write at block granularity, similar to the copy-on-write technique of operating-system virtual memory.

In beam search, sharing goes beyond the prompt: candidates also share other blocks, and the pattern changes as decoding advances, like a process tree created by forks. Earlier systems require frequent copies of the KV cache between candidates; in vLLM, most blocks can be shared, and copy-on-write involves copying only one block.

For shared prefixes, such as a long system prompt with instructions and examples, the provider can store the prefix's KV cache ahead of time. In vLLM, this is done by reserving physical blocks for a set of prefixes predefined by the provider; the user's prompt maps its logical blocks to those cached blocks, with the last one marked as copy-on-write, and the prompt phase runs only over the task input.

1. The provider reserves physical blocks for a set of predefined prefixes, and the prefix's KV cache is stored in advance.

2. A request with the prefix maps its logical blocks to the cached physical blocks, and the prompt phase only needs to run over the task input.

3. Because a physical block now serves more than one logical block, the manager keeps a reference count per physical block.

4. When a sequence needs to write to a shared block, the manager recognizes that the count is greater than one, allocates a new physical block, has the content copied, and decrements the count of the original block.

A common mapping layer, from logical to physical blocks, hides these sharing patterns: the model and its kernel see only a list of physical block IDs per sequence. This is why vLLM processes requests with different decoding methods at the same time, which existing systems do not do efficiently, according to the paper.

05 · SCHEDULING AND SCALE

Preemption, swapping to CPU, and multiple GPUs

When traffic exceeds the system's capacity, vLLM needs to prioritize requests and adopts the FCFS (first-come, first-served) policy for all requests, which guarantees fairness and avoids starvation. When preempting, the oldest requests are served first and the most recent ones are evicted first. As requests and outputs grow, vLLM may run out of physical GPU blocks for the new KV cache.

When blocks run out, it is necessary to decide which blocks to evict and how to recover them. Because all blocks of a sequence are accessed together, vLLM uses all-or-nothing eviction: either all blocks of a sequence are evicted, or none. Sequences of the same request, such as the candidates of a beam search, are scheduled as a group and preempted or rescheduled together.

The paper states that the performance of each technique depends on the bandwidth between CPU RAM and GPU memory and on the GPU's compute power. In swapping, the swap space in CPU RAM is limited by the GPU memory allocated to the KV cache.

For models too large for one GPU, vLLM supports Megatron-LM-style tensor parallelism. There is a single KV cache manager inside the centralized scheduler, and the workers share that manager and the logical-to-physical block mapping. Each worker has the same physical block IDs, but stores only the part of the KV cache for its own attention heads. This way, the workers do not need to synchronize memory management: they receive that information at the start of each decoding iteration, along with the step's inputs.

06 · RESULTS AND LIMITS

What the paper measured, and what it does not

The paper states that vLLM improves the throughput of popular LLMs by 2 to 4 times, at the same level of latency, compared with systems such as FasterTransformer and Orca. The improvement is larger with longer sequences, larger models, and more complex decoding algorithms.

On the ShareGPT dataset, vLLM sustained request rates 1.7× to 2.7× higher than Orca (Oracle) and 2.7× to 8× higher than Orca (Max), with similar latencies. On OPT-13B, it processed 2.2× more requests at the same time than Orca (Oracle) and 4.3× more than Orca (Max).

Orca (Oracle) assumes it knows the actual output length, an upper bound that is infeasible in practice; Orca (Max) always reserves space up to the model's maximum sequence length.

There are limits to consider. First, Orca was not publicly available, so the authors implemented their own version, and the variants differ in how much extra they reserve for the output. Second, on OPT-175B with the Alpaca dataset, which has short sequences, the advantage over Orca (Oracle) and Orca (Pow2) was less pronounced: there was memory left over for the KV cache, and performance became compute-bound rather than memory-bound. Third, in the chatbot test the KV cache is not kept between conversation turns.