LLM: KV Cache and Prefix Cache Speed Up the Service

Serving a language model is not just about running a Transformer for each request. Two complementary caches, one for the ongoing generation and the other for recurring prompt beginnings, lighten the computation. Their efficiency depends as much on GPU memory management as on the ability to identify and reuse the right segments, including when the input becomes multimodal.

Cache Memory is Limited: Evictions and LRU on GPU

The capacity allocated to the KV cache is limited and can saturate if the service continuously adds blocks. When GPU memory runs low, an eviction policy becomes necessary. A common strategy is LRU (Least Recently Used), which removes the least recently used blocks first to make room for new computations. An example illustrates the removal of old blocks marked [OLD] to accommodate [NEW] blocks while retaining recent blocks. In practice, the service must constantly arbitrate which K/V segments to keep and which to remove.

At the Heart of Decoding, a K/V State Reused for Each Token

A LLM produces its output step by step, one token at a time, relying on attention to link the new token to the context. At each step, the model generates Key and Value tensors for the tokens already processed, which are useful for the subsequent tokens. Without caching, these states would be recalculated in a loop, with increasing costs as the sequence lengthens. The KV cache avoids these recomputations by storing K/V states in memory, often on GPU, and reusing them at the next decoding step. During the pre-filling of a prompt like "I love LLMs," the K/V states are built and then reused during generation, while each added token contributes to new states. This mechanism thus maintains the attention state throughout the response. However, this cache is tied to the active request and does not benefit a subsequent unrelated request as it stands.

Sharing Common Beginnings Between Requests with a Prefix Cache

When two users send prompts sharing a long identical preamble—such as an assistant role, policies, instructions, and tool definitions—recalculating this prefix each time wastes computation. Prefix caching allows for the reuse of K/V states already built for the common portion, extending reuse beyond a single request. This technique can significantly reduce the pre-filling cost for workloads where many requests start in the same way, provided the prefix matches exactly.

Identifying and Reusing Segments: Token Blocks and Hashing

To exploit these redundancies, the service splits the prompt into fixed-size token blocks, each corresponding to a portion of the K/V state. A hash, derived from the block's content and its position in the prefix, serves as a compact identifier. This tagging allows for quick determination of whether a block has already been computed, without comparing the entire prompts. In one example, two shared initial blocks lead to cache hits, while the subsequent, different blocks result in cache misses; only the latter require a pass through the model. The crucial point is the transition from a hit to the effective reuse of K/V states. It is important to note that the cache does not store the text for copying but rather the computed K/V state, which can be reloaded when the same prefix reappears.

Cache Management Considers Differences in Images Across Requests

In a multimodal scenario, two requests with identical text but different images cannot be treated as equivalent by the cache. Eligibility for reuse must incorporate a correct representation of each modality. This requirement is particularly important for vision-language model services, where prompts combine text, images, audio, or other types of inputs.