KV cache management — prefix caching, paging, and eviction

Prefix caching detects when multiple requests share the same leading token sequence and reuses the KV cache entries for that shared prefix rather than recomputing them. In production API serving, this is overwhelmingly common: every request to a chatbot includes the same system prompt (often 500-2000 tokens), and multi-turn conversations repeat the entire prior conversation history in each request.

Prefix caching in practice

A system prompt of 1500 tokens on Llama 3 70B consumes $$320 \frac{\text{KB}}{\text{token}} \cdot 1500 = 468 \text{MB}$$ of KV cache. Without prefix caching, this 468 MB is recomputed and stored independently for every request. With prefix caching, it is computed once and shared — all requests that start with the same system prompt read from the same cached KV entries.

The savings compound at scale. A serving cluster handling 100 concurrent requests with a shared 1500-token system prompt:

• Without prefix caching: $468 \text{MB} \cdot 100 = 45.7 \text{GB}$ of redundant KV cache
• With prefix caching: $468 \text{MB} \cdot 1 = 468 \text{MB}$ shared, plus per-request cache for the unique suffix

OpenAI and Anthropic implement prefix caching automatically for their API users. OpenAI's documentation reports a 50% input token cost discount for cached prefixes (the tokens are still billed, but at half price, reflecting the reduced compute). Anthropic charges $0 for cached input tokens beyond the first request. Neither requires any user-side configuration — the system detects shared prefixes by hashing token sequences.

import hashlib
from collections import OrderedDict

class PrefixCache:
    """Simplified prefix cache: hash token prefixes, store KV entries."""
    def __init__(self, max_entries=1000):
        self.cache = OrderedDict()
        self.max_entries = max_entries

    def _prefix_key(self, token_ids, prefix_len):
        prefix = tuple(token_ids[:prefix_len])
        return hashlib.sha256(str(prefix).encode()).hexdigest()

    def lookup(self, token_ids, prefix_len):
        key = self._prefix_key(token_ids, prefix_len)
        if key in self.cache:
            self.cache.move_to_end(key)
            return self.cache[key]
        return None

    def store(self, token_ids, prefix_len, kv_entries):
        key = self._prefix_key(token_ids, prefix_len)
        self.cache[key] = kv_entries
        self.cache.move_to_end(key)
        if len(self.cache) > self.max_entries:
            self.cache.popitem(last=False)  # evict LRU

cache = PrefixCache()
system_prompt_len = 1500

cached_kv = cache.lookup(full_token_ids, system_prompt_len)
if cached_kv is not None:
    # Skip prefill for the system prompt, only process the user message
    kv_caches = cached_kv
    new_tokens = full_token_ids[system_prompt_len:]
else:
    # Full prefill
    kv_caches = None
    new_tokens = full_token_ids

In vLLM, automatic prefix caching is enabled with --enable-prefix-caching. The system maintains a radix tree of token prefixes and their cached KV blocks. When a new request arrives, it walks the tree to find the longest matching prefix, reuses those KV blocks, and only computes the remaining suffix. This reduces TTFT from the prefill-time of the full prompt to the prefill-time of only the non-cached suffix.

PagedAttention: virtual memory for KV cache

Kwon et al. (2023) introduced PagedAttention in vLLM, applying the operating system's virtual memory abstraction to KV cache management. The core problem: traditional KV cache allocation is contiguous — each request pre-allocates a continuous block of GPU memory sized to its maximum possible context length. For a model supporting 128K context on Llama 3 70B, this means reserving 40 GB per request slot, even if the actual generation only uses 2K tokens (640 MB).

This causes severe memory fragmentation. If the system has 100 GB free but in non-contiguous chunks of 5-10 GB each, it cannot allocate a single 40 GB block even though the total free memory is sufficient. The result is that systems using contiguous allocation report 60-80% memory waste under real workloads (Kwon et al. 2023 measured 60.4-68.6% waste in production Orca traces).

PagedAttention divides the KV cache into fixed-size blocks (pages), typically sized to hold KV entries for 16 tokens. Each request maintains a page table mapping logical token positions to physical memory pages. Pages are allocated on demand as the sequence grows, and freed when the request completes.

class PagedKVCache:
    """Simplified PagedAttention concept."""
    def __init__(self, page_size=16, max_pages=10000, kv_size_per_token=320*1024):
        self.page_size = page_size
        self.kv_per_token = kv_size_per_token
        self.page_bytes = page_size * kv_size_per_token
        self.free_pages = list(range(max_pages))
        self.page_tables = {}

    def allocate(self, request_id):
        """Start a new request with no pages allocated."""
        self.page_tables[request_id] = []

    def extend(self, request_id, num_new_tokens):
        """Allocate pages as needed for new tokens."""
        table = self.page_tables[request_id]
        current_tokens = len(table) * self.page_size
        needed_tokens = current_tokens + num_new_tokens
        needed_pages = (needed_tokens + self.page_size - 1) // self.page_size

        while len(table) < needed_pages:
            if not self.free_pages:
                raise MemoryError("No free KV cache pages")
            table.append(self.free_pages.pop())

    def free(self, request_id):
        """Release all pages when request completes."""
        pages = self.page_tables.pop(request_id)
        self.free_pages.extend(pages)

    def memory_usage(self):
        allocated = sum(len(t) for t in self.page_tables.values())
        total = allocated + len(self.free_pages)
        return {
            "allocated_pages": allocated,
            "free_pages": len(self.free_pages),
            "utilization": allocated / total if total > 0 else 0,
            "allocated_gb": (allocated * self.page_bytes) / (1024**3),
        }

cache = PagedKVCache(page_size=16)
cache.allocate("req_1")
cache.extend("req_1", num_new_tokens=2048)
cache.allocate("req_2")
cache.extend("req_2", num_new_tokens=512)
print(cache.memory_usage())

Memory savings

Under the production workload traces analyzed by Kwon et al., PagedAttention reduced memory waste from 60-68% to near zero. This translated to 2-4x higher throughput (measured in requests/sec) on identical hardware, because more concurrent requests could fit in memory. vLLM's PagedAttention is now the industry standard — every major open-source serving framework (vLLM, TensorRT-LLM, SGLang) implements some variant of paged KV cache management.

An additional benefit of paging: copy-on-write sharing. When two requests share a common prefix, their page tables can point to the same physical pages for the shared portion. Modifications (appending new tokens) trigger a copy of only the affected page, not the entire cache. This is how vLLM implements prefix caching efficiently — shared prefix pages have a reference count, and are freed only when all requests using them complete.

KV cache quantization

Storing K and V in reduced precision — int8 (1 byte) or int4 (0.5 bytes) instead of float16 (2 bytes) — directly reduces cache memory by 2-4x. The quality impact is generally small: KIVI (Liu et al. 2024) reported less than 0.1 perplexity increase for int8 KV cache on Llama 2 7B and 13B, and less than 0.3 for int4 on K with int8 on V.

The asymmetry between K and V quantization matters. Key vectors participate in the dot product with queries (multiplicative interaction), so quantization error in K is amplified by the softmax. Value vectors are linearly combined after softmax (additive interaction), so they tolerate more aggressive quantization. A common configuration is int4 keys with int8 values — roughly 3x total compression with minimal degradation.

def quantize_kv_cache(k_cache, v_cache, k_bits=4, v_bits=8):
    """Estimate memory savings from KV cache quantization."""
    original_bytes = (k_cache.numel() + v_cache.numel()) * 2  # float16
    k_bytes = k_cache.numel() * (k_bits / 8)
    v_bytes = v_cache.numel() * (v_bits / 8)
    quantized_bytes = k_bytes + v_bytes
    return {
        "original_gb": original_bytes / 1e9,
        "quantized_gb": quantized_bytes / 1e9,
        "compression_ratio": original_bytes / quantized_bytes,
    }

For Llama 3 70B at 8K context, int4-K / int8-V quantization reduces per-request KV cache from 2.5 GB to approximately 0.94 GB — enabling 2.6x more concurrent requests on the same hardware.

Eviction strategies for bounded memory

When context exceeds available KV cache memory, the system must evict tokens. Three approaches have emerged in production and research systems.

Sliding window attention

Mistral 7B (Jiang et al. 2023) uses a fixed sliding window of W=4096 tokens. Attention in each layer only accesses the most recent W tokens. KV entries older than W positions are discarded. This caps KV cache at W * per_token_cost regardless of input length. The tradeoff: the model cannot attend to information beyond W tokens back. In practice, the sliding window is applied per-layer, and information propagates through residual connections — a fact at position 0 can influence position 8192 if intermediate layers carried it forward through the residual stream.

Attention-based eviction (H2O)

Heavy Hitter Oracle (Zhang et al. 2023) observes that attention distributions are highly skewed: a small fraction of tokens (5-10%) receive the majority of attention mass across heads and layers. These "heavy hitter" tokens carry disproportionate information. H2O evicts tokens with the lowest cumulative attention scores, keeping a budget of the top-k most-attended tokens plus a local window of recent tokens. On Llama 2 evaluated with a budget of 20% of context, H2O preserves 95%+ of full-context performance on most benchmarks.

Cache offloading

When eviction is unacceptable (tasks requiring full context, like long-document QA), KV cache can be offloaded to CPU DRAM. GPU memory holds only the active working set; evicted pages are moved to CPU RAM (typically 256-512 GB, far larger than GPU HBM). When a decode step requires attention over offloaded tokens, those pages are fetched back to GPU memory over the PCIe bus (64 GB/s on PCIe 5.0) or NVLink. The latency penalty is significant — a 1 GB page fetch takes ~16 ms over PCIe 5.0, adding directly to per-token latency — but it prevents OOM and preserves full context fidelity.

FlexGen (Sheng et al. 2023) demonstrated that offloading-based inference can serve Llama-scale models on a single consumer GPU (24 GB) by orchestrating KV cache between GPU, CPU, and disk. Throughput drops to ~1 token/sec, but the system never runs out of memory regardless of context length.