Can OS paging techniques reduce LLM serving memory waste?

The paper proposes PagedAttention, "an attention algorithm inspired by the classical virtual memory and paging techniques in operating systems," built into a serving engine called vLLM. The problem it targets is the key-value cache (KV cache), the per-request memory that stores earlier tokens' key and value tensors so the model does not recompute them at every decoding step. On a 13B-parameter model on an A100 GPU, the paper reports "approximately 65% of the memory is allocated for the model weights" and "close to 30%" to this per-request KV cache, which "grows and shrinks dynamically" and is "huge." Existing systems waste much of that 30% to fragmentation and duplication, which caps how many requests can be batched together and therefore caps throughput. The paper's evaluations find vLLM "improves the throughput of popular LLMs by 2-4× with the same level of latency compared to the state-of-the-art systems, such as FasterTransformer and Orca," with the gain "more pronounced with longer sequences, larger models, and more complex decoding algorithms."

The mechanism follows the OS analogy directly. PagedAttention splits each request's KV cache into fixed-size "KV blocks" and lets the attention computation run block by block, so the blocks "can be stored in non-contiguous physical memory." A KV cache manager then tracks, per request, a "block table" mapping logical blocks to physical ones, the same separation an OS makes between a program's logical pages and physical memory. Because physical blocks are allocated only as new tokens are generated rather than reserved upfront for an unknown final length, "this eliminates most memory waste in existing systems." The same block structure also lets requests share KV blocks within and across a batch, further cutting memory use. The paper is explicit that this only pays off because LLM serving is memory-bound and allocation sizes are not known in advance — it says the same paging idea would not help, and could even "degrade the performance," for workloads that are compute-bound or have static tensor shapes, such as ordinary DNN training or non-LLM DNN serving.

This sits in a cluster of notes about memory as the binding constraint on LLM inference, but at a different point in the stack. What actually limits language models on mobile phones? and Does recomputing weights cost less than moving them on mobile? both treat memory-bound serving as a hardware limit on a single device and respond by shrinking or reusing static weights. PagedAttention instead leaves the model and its weights untouched and attacks waste in the dynamic KV cache on data-center GPUs serving many concurrent requests — a batching-and-fragmentation problem, not a parameter-count problem. Can recursive subtask trees overcome context window limits? shares the object of attack, the KV cache, but a different tool and goal: TIM prunes entries to free capacity for longer reasoning in a single request, where PagedAttention repacks entries to fit more simultaneous requests without discarding any of them.

What the excerpt does not establish is cost in dollar or energy terms — the throughput gain is reported in requests-per-unit-time and latency parity, not as a measured reduction in serving cost per request, though higher throughput on the same hardware implies a lower cost per request if utilization was the binding constraint. The excerpt also does not say how the gain scales past the specific comparisons tested (FasterTransformer, Orca) or quantify "near-zero waste" numerically within this passage. The cited claim that "processing an LLM request can be 10× more expensive than a traditional keyword query" is attributed in the source to a separate reference the excerpt does not identify, so it should be read as a cited estimate from elsewhere, not a finding of this paper.