KV Cache › Cache Management

Efficient cache management involves necessary decisions about memory allocation strategies, handling variable sequence lengths across concurrent requests, and managing batched generation effectively. These operational considerations often determine whether a deployment can reach its throughput and latency targets. Getting the compute right is necessary but not sufficient; you also need to get the memory management right.

Think of cache management like hotel room allocation. Model weights are the building itself: fixed overhead that is always there. Each user request is a guest who needs a room (cache memory) for the duration of their stay (generation). Some guests stay for 10 minutes (short generations), others for hours (long generations). If you pre-assign the biggest possible room to everyone, you waste capacity. If you assign rooms dynamically but poorly, you get fragmentation where no contiguous block is large enough for the next guest even though total free memory is sufficient.

Static allocation pre-allocates cache tensors for the maximum sequence length at the start of generation. This approach reserves all memory upfront, avoiding the overhead of repeated memory allocation during the generation process. Static allocation is preferred when the maximum sequence length is known in advance, when memory fragmentation must be avoided, and when consistent, predictable latency is required. The downside is waste: a request that only generates 100 tokens uses the same amount of pre-allocated memory as one that generates 4,096 tokens.

Dynamic allocation grows the cache as needed, typically by allocating larger tensors and copying existing data when the current allocation is exhausted. This saves memory for shorter sequences but introduces allocation overhead and potential fragmentation. Modern frameworks often use a hybrid approach, allocating in chunks of 128 or 256 tokens at a time to balance these tradeoffs. The chunk size is a compromise between allocation frequency (smaller chunks mean more frequent allocations) and waste (larger chunks mean more potential waste at the end).

The management challenge compounds when serving multiple requests concurrently. A request that finishes early frees its cache memory, but that freed memory may be fragmented: a 500-token hole here, a 200-token hole there. A new incoming request wanting 1,000 tokens cannot use these fragments even though total free memory is sufficient. This is the classical memory fragmentation problem, and it is why vLLM's Paged Attention, which we will cover in the next chapter, attracted such attention: it applies the operating system's paging approach to eliminate fragmentation entirely.

When generating for multiple sequences simultaneously, cache management becomes more complex because different sequences may have different lengths. The typical approaches each involve different tradeoffs:

• Padding: Allocate cache based on the longest sequence in the batch, padding shorter sequences. Simple to implement and preserves batched matrix operations, but wasteful when sequence lengths vary materially. A batch where one sequence has 4,096 tokens and five others have 50 tokens wastes nearly all the allocated memory for those five.
• Separate caches: Maintain independent cache tensors per sequence. Avoids wasted memory but complicates the attention computation and prevents batched matrix operations, hurting GPU utilization.
• Paged attention: Allocate cache in fixed-size blocks and track which blocks belong to which sequence using a block table (in effect a page table). This approach lets efficient memory utilization with variable-length sequences and is the basis of the vLLM serving system.

When a sequence reaches the model's maximum context length, the system must decide how to proceed. Three main strategies exist, each with different tradeoffs:

Truncation simply stops accepting new tokens or drops the oldest tokens from the sequence. The model loses access to early context, which can cause coherence problems in long conversations.

Sliding window maintains only the most recent $W$ tokens, discarding older ones. This is the approach used in Mistral's architecture, as we discussed in Part XXIX. The advantage is a constant memory footprint; the disadvantage is that the model cannot reference information from the distant past.

Attention sinks keeps initial tokens (which empirically receive disproportionate attention regardless of content, the "sink" phenomenon we explored in Part XVIII) plus a window of recent tokens. This preserves the model's numerical stability while using a bounded cache.

Each strategy has tradeoffs between memory usage, coherence over long conversations, and computational complexity. Production systems often need to support multiple strategies and allow users or operators to choose based on their application requirements.