KV cache

What it is

A large language model writes text one token at a time: it produces a token, appends it to the input, and runs again to produce the next one. At every step the attention layers need a key vector and a value vector for each token seen so far. Those vectors for earlier tokens do not change when a new token is appended, so recomputing them from scratch each step is wasted work. The key-value cache is where they are kept: once a token has been processed, its key and value stay in memory and are read back at every later step. The cache is maintained per request, so its size is set by how many tokens that request has handled; it can be very large, and it grows and shrinks dynamically as generation proceeds ^[1].

How it works

A concrete example makes the idea clear. Suppose the input so far is a short phrase and the model has already processed it. The cache now holds one key vector and one value vector for each position in that phrase. To produce the next token, the query vector of the new position is compared against the stored keys (plus the key of the new position itself), and the resulting attention weights are used to mix the stored values. The token that comes out is appended, and its own key and value are written into the cache. When the following token is generated, every earlier entry is reused exactly as it was.

Without such a cache, each generation step would push the whole prefix through the model again, and the repeated work would balloon as the text gets longer. With the cache, most of the per-step cost becomes reading through a growing store of key and value vectors rather than recomputing them.

Where the memory problem comes from

That store is not a minor bookkeeping detail. For a single request the cache can be huge, and its size is not fixed: different requests have very different lengths, and one request keeps growing while it is being generated ^[1]. If memory is allocated naively, for instance by reserving one contiguous region sized for the worst case, the unused part sits idle. Uneven request lengths leave fragmentation, and some memory is taken up by redundant duplicates of the same data ^[1]. This waste directly lowers the number of requests a server can keep in flight, and serving at high throughput is precisely about batching many requests at once ^[1].

PagedAttention and vLLM

In September 2023, Kwon et al. proposed PagedAttention, an attention algorithm inspired by virtual memory and paging techniques in operating systems ^[1]. Paging, in an operating system, maps contiguous logical addresses onto physical blocks that can sit anywhere in memory, with a table recording the mapping, so no single contiguous run has to be reserved. PagedAttention applies the same style of thinking to the key-value cache.

On top of PagedAttention the authors built vLLM, an LLM serving system that achieves near-zero waste in key-value cache memory ^[1]. vLLM also allows flexible sharing of the cache within a request and across requests, which reduces memory use further ^[1].

Results and where it stands

Compared with systems such as FasterTransformer and Orca, vLLM improved the throughput of popular LLMs by 2–4x at the same level of latency ^[1]. The improvement is more pronounced with longer sequences, larger models and more complex decoding algorithms ^[1]. The work was published at SOSP 2023, and its source code is publicly available ^[1]. For anyone building or studying LLM serving, key-value cache management is now a central design question alongside the attention computation itself: the cache is what a server spends its memory on, and how that memory is handed out decides how many users the machine can serve at once.

Limits

Paging removes waste, not the underlying data. The key and value vectors still have to be stored, and the amount needed still scales with context length and with the number of concurrent requests. The reported gains also depend on the workload: because the improvement is more pronounced for longer sequences, larger models and more complex decoding ^[1], short-sequence or simple-decoding settings benefit less.