Prefix Caching

The key-value cache is the fundamental data structure that prefix caching stores and reuses. During autoregressive decoding, the Transformer's attention mechanism computes key and value tensors for every token. Rather than recomputing these for the entire sequence on each step, the KV-Cache stores them in GPU memory. For a reused prefix, this cache is simply loaded from memory rather than recomputed, eliminating the quadratic prefill cost. The cache size grows linearly with batch size, sequence length, and number of layers, making it the primary memory bottleneck in LLM serving.

• Memory formula: 2 × n_layers × d_model × seq_len × batch_size × precision_bytes
• Grouped-Query Attention (GQA) reduces KV-Cache size by sharing key-value heads across query heads
• PagedAttention manages KV-Cache in non-contiguous blocks to minimize fragmentation

Prompt compression techniques reduce the token count of a prompt while preserving its semantic intent, directly amplifying the benefits of prefix caching. A shorter shared prefix means a smaller KV-Cache footprint and faster cache hits. Methods include extractive compression (removing redundant tokens), abstractive compression (summarizing with a smaller model), and soft prompt tuning (learning compact continuous embeddings). When combined with prefix caching, compressed system prompts and few-shot examples reduce both storage requirements and prefill latency.

• LLMLingua uses a small language model for token-level pruning
• AutoCompressors condense long documents into summary vectors
• Compression ratios of 2-5x are common without significant accuracy loss

Speculative decoding and prefix caching are complementary inference optimizations that target different phases of generation. While prefix caching eliminates redundant prefill computation for shared prefixes, speculative decoding accelerates the decoding phase by using a small draft model to generate multiple candidate tokens that a larger model verifies in parallel. Together, they provide end-to-end latency reduction: prefix caching handles the input processing bottleneck, and speculative decoding addresses the autoregressive generation bottleneck.

• Draft models are typically 10-100x smaller than the target model
• Verification is done in a single parallel forward pass
• Combined with prefix caching, total latency can drop by 3-5x

Continuous batching is a serving technique that dynamically adds new requests to a running batch as soon as previous requests complete, rather than waiting for the entire batch to finish. This maximizes GPU utilization and interacts directly with prefix caching: when multiple requests share a common system prompt, the scheduler can group them to amortize the cached prefix computation across the batch. Frameworks like vLLM and TensorRT-LLM implement both continuous batching and prefix-aware scheduling.

• Eliminates head-of-line blocking in static batching
• Prefix-aware schedulers prioritize requests with matching prefixes
• Throughput improvements of 2-10x over naive batching

The attention mechanism is the computational core that prefix caching optimizes. In self-attention, every token computes query, key, and value projections, then calculates attention scores against all other tokens. The quadratic complexity — O(n²) in sequence length — makes the prefill phase expensive for long prompts. Prefix caching bypasses this entirely for reused prefixes by storing the already-computed keys and values. Understanding attention's causal masking is essential: the KV-Cache for a prefix is identical regardless of what follows, enabling safe reuse.

• Multi-Head Attention (MHA) computes independent attention over multiple heads
• FlashAttention uses tiling to reduce memory bandwidth during computation
• The prefill phase is compute-bound; the decode phase is memory-bound

Tokenization determines the granularity at which prefix caching operates. A cached prefix is stored as a sequence of token IDs, and a cache hit requires an exact token-level match. The choice of tokenizer — whether Byte-Pair Encoding (BPE), WordPiece, or SentencePiece — affects cache hit rates. A single differing whitespace or punctuation character can break a cache match. For optimal prefix caching, system prompts should be tokenization-stable: identical byte-for-byte across requests, with consistent formatting and no dynamic content in the shared prefix.

• Common vocabularies range from 32k to 256k tokens
• Chat templates apply consistent tokenization to conversation structures
• Cache keys are typically the hash of the token sequence