Prefix Caching

Many requests share the same prefix — system prompts, few-shot examples, or common document contexts. Prefix caching avoids recomputing KV cache for shared prefixes, reducing TTFT by 50-90% for these workloads.

---

1. The Redundancy Problem

In production, most requests share a common prefix:

Request 1: "You are a helpful assistant. [system prompt 2K tokens]" + "What is CUDA?"
Request 2: "You are a helpful assistant. [system prompt 2K tokens]" + "Explain PagedAttention"
Request 3: "You are a helpful assistant. [system prompt 2K tokens]" + "How does batching work?"

Without caching, each request prefills the same 2K-token system prompt — identical computation repeated for every request. With 100 requests/second, that’s 100 redundant prefills of the same tokens.

---

2. Block-Level KV Sharing

PagedAttention’s block structure enables prefix caching naturally:

1. First request: Prefills system prompt → KV blocks computed and stored
2. Subsequent requests: Check if their prefix blocks already exist in cache
3. Match found: Skip prefill for matched blocks, only prefill the unique suffix
4. No match: Normal prefill

Request 1 (first): Prefill all [Block 0, 1, 2, 3 (system), Block 4 (query)]
                    → Blocks 0-3 kept in cache after completion

Request 2 (later):  Blocks 0-3 match cache → SKIP prefill for these!
                    Only prefill Block 5 (new query)
                    → TTFT reduced by ~80%

Reference Counting

Shared blocks use reference counting — they’re only freed when no request or cache entry references them. This extends PagedAttention’s copy-on-write sharing from concurrent requests to sequential requests over time.

---

3. RadixAttention: Tree-Based Cache Lookup

SGLang introduced RadixAttention — organizing cached prefixes as a radix tree (trie) indexed by token sequences:

Root
├── "You are a helpful assistant..." (system prompt A)
│   ├── "What is CUDA?" → cached KV for this full prompt
│   ├── "Explain PagedAttention" → cached KV
│   └── "How does..." → cached KV for common prefix
├── "You are a code reviewer..." (system prompt B)
│   ├── "Review this function..." → cached KV
│   └── "Find bugs in..." → cached KV
└── "[Document context: paper.pdf]" (RAG prefix)
    ├── "Summarize the key findings" → cached KV
    └── "What methodology was used?" → cached KV

Lookup: For a new request, walk the trie matching tokens. The longest matching prefix gives the cached KV to reuse. Only the unmatched suffix needs prefill.

Eviction

When GPU memory is full, evict the least recently used (LRU) cached prefixes. High-frequency prefixes (like system prompts) naturally stay cached.

---

4. Automatic Prefix Caching in vLLM

from vllm import LLM

llm = LLM(
    model="meta-llama/Llama-3.1-70B",
    enable_prefix_caching=True,  # enable automatic prefix caching
)

# First request: full prefill (cache miss)
output1 = llm.generate("System: You are helpful.\nUser: What is CUDA?")

# Second request with same prefix: partial prefill (cache hit!)
output2 = llm.generate("System: You are helpful.\nUser: Explain TP")
# Only "Explain TP" tokens need prefill — system prompt KV reused

When Prefix Caching Helps Most

Scenario	Prefix length	Cache hit rate	TTFT reduction
System prompts	100-2K tokens	90%+	50-80%
Few-shot examples	1K-4K tokens	80%+	60-90%
RAG with repeated docs	2K-8K tokens	50-70%	40-70%
Unique prompts	0 tokens	0%	None

---

5. Multi-Turn Conversations

Chat applications naturally benefit — each turn extends the previous prefix:

Turn 1: [System + User1 + Assistant1]
Turn 2: [System + User1 + Assistant1 + User2]  ← prefix of Turn 1 cached!
Turn 3: [System + User1 + Assistant1 + User2 + Assistant2 + User3]  ← prefix cached!

Each turn only prefills the new user message — all previous turns’ KV is cached.

For how scattered KV blocks are read during attention, see PagedAttention. For how prefill chunks interact with caching, see Chunked Prefill.

---

6. Beyond Exact Prefix: Advanced KV Reuse

Standard prefix caching has a strict limitation: only exact token-by-token matches from the beginning can be reused. If shared text appears in the middle, or prompts are similar but not identical, no reuse happens:

Request A: [System prompt] + [Doc X] + [Question 1]
Request B: [Doc X] + [System prompt] + [Question 2]
→ Standard prefix caching: NO reuse (different prefix order)

Several techniques break this limitation:

Prompt Cache: Position-Independent Reuse

Prompt Cache (Gim et al., 2023) pre-defines cacheable prompt modules (system prompts, few-shot examples, document chunks) and assigns them fixed position encodings. Because KV values depend on positional encoding, using consistent position IDs for each module means its KV is valid regardless of where it appears in the full prompt.

Module "system_v2" (positions 0-500): always uses positions 0-500
Module "few_shot_math" (positions 501-1200): always uses positions 501-1200

Request 1: [system_v2] + [few_shot_math] + [query]  → both modules cached
Request 2: [system_v2] + [query]  → system_v2 still valid!

Limitation: Modules must be pre-defined and their position ranges fixed at design time.

CacheBlend: Partial Reuse from Similar Contexts

CacheBlend (2024) enables reuse even when contexts are similar but not identical. The key insight: for tokens far from the divergence point between two prompts, their KV representations are nearly the same.

1. Find cached KV from a similar (not identical) prompt
2. Identify tokens where cached KV diverges significantly from what the current context would produce
3. Selectively recompute only the divergent tokens (typically 20-50%)
4. Blend recomputed KV with cached KV

Result: 50-70% prefill compute savings even for prompts that share no common prefix.

Semantic Caching: Skip Inference Entirely

GPTCache and similar systems cache full responses (not KV tensors) indexed by semantic similarity:

embedding = embed(user_query)
similar = vector_search(embedding, cache_index, threshold=0.95)
if similar:
    return cached_response[similar]  # skip inference entirely!
else:
    response = llm.generate(user_query)
    cache.store(embedding, response)
    return response

Not KV-level caching — skips the model entirely for near-duplicate queries. Useful for FAQ-style workloads.

Distributed KV Stores

At cluster scale, Mooncake (2024) maintains a distributed KV cache pool across serving instances. Requests are routed to the instance most likely to have relevant KV cached (cache-affinity routing).

Comparison

Technique	Reuse condition	Savings	Limitation
Prefix caching	Exact token prefix match	50-90% TTFT	Prefix-only
Prompt Cache	Pre-defined module match	50-80% TTFT	Must pre-define modules
CacheBlend	Semantically similar context	50-70% prefill	Depends on divergence
Semantic caching	Similar query embedding	100% (skip model)	Near-duplicates only
Distributed KV	Cached KV on any node	Varies	Network transfer cost

For distributed KV cache sharing across instances, see Distributed KV Cache.

---

Self-Check

• Explain why shared prefixes cause redundant computation without caching
• Describe block-level KV sharing and reference counting
• Explain RadixAttention’s trie-based cache lookup
• Calculate TTFT reduction for a 2K-token system prompt with caching
• Identify workloads where prefix caching helps most vs least
• Explain Prompt Cache’s position-independent module reuse
• Explain CacheBlend’s approach to reusing KV from similar (non-identical) contexts
• Compare prefix caching vs semantic caching vs CacheBlend

---

References

• SGLang: Efficient Execution of Structured Language Model Programs (Zheng et al., 2023)
• vLLM Automatic Prefix Caching