Prefix Caching

When multiple requests share a common prompt prefix—such as a system prompt, few-shot examples, or a long document—the KV cache computed for that prefix is stored once and reused. This avoids recomputing attention for the identical prefix tokens across every request.

• Mechanism: The attention keys and values for the prefix are materialized and cached after the first request
• Benefit: Subsequent requests skip the prefill phase for the shared prefix entirely
• Example: A chatbot with a 4,000-token system prompt serves 100 concurrent users; prefix caching reduces prefill compute by 99% for the shared portion

Modern inference engines like SGLang and vLLM use radix tree data structures to organize cached KV blocks by token sequences. This enables efficient lookup and partial matching of prefixes.

• Structure: A trie-based index where each node represents a token and its associated KV cache block
• Partial Matching: A request with prefix "A, B, C, D" can reuse the cache from a previously computed "A, B, C" prefix
• LRU Eviction: Least-recently-used leaf nodes are evicted under memory pressure, preserving hot prefixes

Prefix caching is implemented on top of PagedAttention, which manages the KV cache as non-contiguous blocks of tokens rather than a monolithic tensor. This block-level granularity is what makes prefix sharing practical.

• Block Sharing: KV cache blocks are reference-counted and shared across sequences
• Copy-on-Write: When a sequence diverges from the cached prefix, only the divergent blocks are duplicated
• Memory Efficiency: Eliminates fragmentation and enables dynamic memory allocation for cached prefixes

The most impactful use case for prefix caching is caching the system prompt or instruction template that remains constant across all user interactions in a deployed application.

• Constant Prefix: The system prompt is identical for every request, making it a perfect caching candidate
• Latency Impact: Time To First Token (TTFT) drops dramatically because the entire system prompt prefill is skipped
• Throughput Gain: GPU compute is freed to handle more concurrent decoding streams rather than redundant prefill operations

In conversational AI, the entire dialogue history up to the current turn forms a shared prefix for the next response. Prefix caching stores the KV cache for the conversation history, avoiding recomputation of all prior turns.

• Incremental Growth: Each new turn appends tokens to the cached prefix rather than recomputing from scratch
• Long Context Efficiency: Conversations spanning tens of thousands of tokens benefit disproportionately
• Implementation: Requires the serving engine to track conversation session IDs and associate them with cached prefixes

Advanced inference runtimes implement automatic prefix caching that transparently identifies and caches shared prefixes without explicit developer annotation. The runtime hashes incoming token sequences and checks against the cache store.

• Hash-Based Matching: Token sequences are hashed to quickly identify cache hits
• No Code Changes: Applications benefit from caching without modifying prompt construction logic
• Granularity Tradeoff: Block-level matching (e.g., 16-token blocks) balances cache hit rate against indexing overhead

The key-value cache is the fundamental data structure that prefix caching operates on. During autoregressive generation, the model computes key and value tensors for each token. Rather than recomputing these for every new token, the KV cache stores them in GPU memory. For a sequence of length n, this reduces the attention computation from O(n²) to O(n). The cache grows linearly with batch size, sequence length, and number of layers, often becoming the primary memory bottleneck in high-throughput serving. Prefix caching exploits the fact that the KV cache for a shared prompt prefix is identical across requests, enabling reuse without recomputation.

A memory management technique that treats the KV cache as a collection of non-contiguous blocks rather than a single contiguous allocation. Inspired by virtual memory paging in operating systems, PagedAttention eliminates internal and external fragmentation by allocating cache memory in fixed-size blocks. When prefix caching identifies a shared prompt, the corresponding blocks can be shared across multiple sequences via pointer references rather than physical copies. This enables memory-efficient prefix sharing and is a core innovation in the vLLM serving engine.

A serving optimization that dynamically adds new requests to a running batch without waiting for all in-progress generations to complete. Traditional static batching requires all sequences in a batch to finish before a new batch begins, leaving GPU compute idle. Continuous batching interleaves new prefill operations with ongoing decode steps. When combined with prefix caching, a new request sharing a system prompt can immediately join the batch and reuse the cached KV tensors, dramatically reducing Time To First Token (TTFT) for high-concurrency workloads like chatbots.

An inference acceleration method that uses a lightweight draft model to generate multiple candidate tokens quickly, then verifies them in parallel with the full target model. While distinct from prefix caching, both techniques target the memory-bandwidth bottleneck in autoregressive decoding. Speculative decoding reduces the number of sequential forward passes, while prefix caching eliminates redundant computation for shared prefixes. They can be combined: a cached system prompt prefix avoids recomputation, while speculative decoding accelerates the unique suffix generation.

A critical latency metric measuring the delay between sending a prompt and receiving the first generated token. TTFT is dominated by the prefill phase, where the model processes the entire input prompt in a single forward pass. Prefix caching directly reduces TTFT by eliminating the need to recompute the KV cache for cached prefix tokens. For a system prompt of 1,000 tokens, prefix caching can reduce TTFT from hundreds of milliseconds to near-zero, transforming user-perceived responsiveness in interactive applications.