By Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph E. Gonzalez, Hao Zhang, Ion StoicaSourcearXiv
Fork
Clone
git clone https://openversions.com/git/index/arxiv-2309-06180.git
Cite
Version link
https://openversions.com/index/arxiv-2309-06180/commit/6d3577fbca43321338a9074ea022cf033cf8bc71
Version identifier (commit hash)
6d3577fbca43321338a9074ea022cf033cf8bc71

Fork to create your own copy with credit to the source. Clone to get a Git copy on your computer.

Claims

Findings

Headline finding

vLLM, built on top of PagedAttention, improves the serving throughput of popular LLMs by 2-4x with the same level of latency compared to state-of-the-art systems such as FasterTransformer and Orca, with more pronounced improvements for longer sequences, larger models, and more complex decoding algorithms, without affecting model accuracy.

vLLM achieves near-zero waste in KV cache memory, utilizing 96.3% of KV cache memory for actual token states compared to 20.4% - 38.2% in existing Orca baselines.

On the ShareGPT dataset, vLLM sustains 1.7x-2.7x higher request rates compared to Orca (Oracle), 2.7x-8x compared to Orca (Max), and up to 22x compared to FasterTransformer while maintaining similar latencies.

Through KV block sharing, vLLM achieves 6.1% - 9.8% memory saving on parallel sampling and 37.6% - 55.2% on beam search for the Alpaca dataset, and 16.2% - 30.5% on parallel sampling and 44.3% - 66.3% on beam search for the ShareGPT dataset, improving throughput over Orca (Oracle) on OPT-13B/Alpaca from 1.3x in basic sampling to 2.3x in beam search with width 6.

When input prompts share a common prefix, vLLM achieves 1.67x higher throughput than Orca (Oracle) for a 1-shot prefix and 3.58x higher throughput for a 5-shot prefix on LLaMA-13B with WMT16.

On a synthesized ShareGPT chatbot workload with OPT-13B, vLLM sustains 2x higher request rates compared to the three Orca baselines.

PagedAttention's custom GPU kernels incur 20-26% higher attention kernel latency compared to FasterTransformer's implementation, yet vLLM significantly outperforms FasterTransformer in end-to-end performance.

In vLLM, recomputation is more efficient than swapping when the block size is small, swapping is more efficient when the block size is large (with recomputation overhead never exceeding 20% of swapping's latency), and both exhibit comparable end-to-end performance for medium block sizes (16 to 64).

Methods

PagedAttention partitions each sequence's KV cache into fixed-size KV blocks (each containing key and value vectors for B tokens) that can be stored in non-contiguous physical memory, and computes attention block-wise.

Source excerpts

“Specifically, PagedAttention partitions the KV cache of each sequence into KV blocks. Each block contains the key and value vectors for a fixed number of tokens, which we denote as KV block size (B).” · Show in paper

vLLM's KV cache manager uses a block table to map logical KV blocks to physical KV blocks on GPU DRAM (and CPU RAM for swapping), allocating physical blocks dynamically on demand as tokens are generated.

Source excerpts

“The KV block manager also maintains block tables—the mapping between logical and physical KV blocks of each request. Each block table entry records the corresponding physical blocks of a logical block and the number of filled positions. Separating logical and physical KV blocks allows vLLM to dynamically grow the KV cache memory without reserving it for all positions in advance” · Show in paper

vLLM implements block-level memory sharing with reference counting and a copy-on-write mechanism to support parallel sampling, beam search, and shared prefixes.

Source excerpts

“Since a single physical block can be mapped to multiple logical blocks, we introduce a reference count for each physical block. ... vLLM implements a copy-on-write mechanism at the block granularity for the physical blocks that need modification by multiple sequences, similar to the copy-on-write technique in OS virtual memory” · Show in paper

vLLM uses first-come-first-serve (FCFS) scheduling with all-or-nothing eviction, gang-scheduling of sequence groups, and supports both swapping evicted blocks to CPU RAM and recomputing KV caches upon rescheduling.

Source excerpts

“In vLLM, we adopt the first-come-first-serve (FCFS) scheduling policy for all requests, ensuring fairness and preventing starvation. ... we implement an all-or-nothing eviction policy, i.e., either evict all or none of the blocks of a sequence. Furthermore, multiple sequences within one request (e.g., beam candidates in one beam search request) are gang-scheduled as a sequence group.” · Show in paper

For distributed execution across multiple GPUs using Megatron-LM style tensor parallelism, vLLM uses a centralized scheduler and single KV cache manager that broadcasts block tables to SPMD GPU workers.

Source excerpts

“Therefore, vLLM features a single KV cache manager within the centralized scheduler, as in Fig. 4. Different GPU workers share the manager, as well as the mapping from logical blocks to physical blocks.” · Show in paper

vLLM implements three custom CUDA kernel optimizations: fused reshape and block write, fused block read and attention (adapted from FasterTransformer), and fused block copy for copy-on-write operations.

Source excerpts

“(1) Fused reshape and block write. ... (2) Fusing block read and attention. ... (3) Fused block copy.” · Show in paper

The evaluation uses OPT (13B, 66B, 175B) and LLaMA-13B on NVIDIA A100 GPUs with workloads synthesized from ShareGPT and Alpaca datasets using Poisson arrival times, compared against FasterTransformer and three re-implemented variants of Orca (Oracle, Pow2, Max).

Source excerpts

“We use OPT [62] models with 13B, 66B, and 175B parameters and LLaMA [52] with 13B parameters for our evaluation. ... For all of our experiments, we use A2 instances with NVIDIA A100 GPUs on Google Cloud Platform. ... We synthesize workloads based on ShareGPT [51] and Alpaca [50] datasets” · Show in paper