PidokuInfra
11Prefix and Prompt Caching
On this page

Prefix and Prompt Caching

Basic Advanced 1h 30m Difficulty 4/5 Topic 11 of 15

Prerequisites 05, 10

1. What is it?#

Reusing the KV cache computed for a shared prompt prefix across requests, instead of recomputing it.

Request 1: [system prompt 2000 tok][user question A 20 tok]
Request 2: [system prompt 2000 tok][user question B 25 tok]
                    ↑ identical
           compute this ONCE, reuse for request 2
           → request 2's prefill drops from 2025 tokens to 25 tokens
           → 98.8% of its prefill eliminated

Also called: automatic prefix caching (vLLM), RadixAttention (SGLang), context caching (commercial APIs), prompt caching.

Diagram — Prefix cache lookup on admission#

flowchart TB
  R["New request tokens"] --> H["Hash the prompt block by block<br/>each hash chains the previous one"]
  H --> L{"Longest cached prefix?"}
  L -->|"hit: k blocks"| RE["Reuse those KV blocks<br/>ref count + 1"]
  L -->|"miss"| FULL["Prefill the whole prompt"]
  RE --> REST["Prefill only the remaining tokens"]
  REST --> DEC["Decode"]
  FULL --> DEC
  DEC --> ST["Completed full blocks stay cached<br/>evicted LRU under memory pressure"]

  class RE,REST,ST memory
  class FULL,DEC compute
  class L queue
  class R,H neutral

2. Why does it exist?#

Because real workloads share prefixes constantly, and re-prefilling them is pure waste.

Workload                        Typical shared prefix
Chatbot with system prompt      500-3,000 tokens, on EVERY request
Few-shot prompting              2,000-10,000 tokens of examples
RAG over a fixed corpus         document chunks recur across queries
Multi-turn conversation         the entire history, every turn
Agentic loops                   tool definitions + scratchpad, every step
Code assistant                  the open file, every keystroke

Multi-turn conversation is the biggest one. Turn 10 of a conversation re-prefills turns 1-9 every single time. With prefix caching, turn 10 prefills only the new user message.

3. Simple analogy#

A chef with prepped ingredients.

Every dish on the menu starts with the same mirepoix — 20 minutes of chopping. Without prep, each order takes 20 minutes of chopping plus 5 minutes of actual cooking. With a batch of mirepoix prepped once in the morning, each order takes 5 minutes.

The complications map exactly:

  • The prep must be identical (exact prefix match — one different character and it’s useless).
  • It takes fridge space (cache memory competes with active requests).
  • It goes off (eviction policy).

4. Tiny example#

The effect, measured:

Go
// prefix.go — three requests that share a long system prompt.
// Start the server with prefix caching on, e.g.:
//
//	vllm serve Qwen/Qwen2.5-1.5B-Instruct --enable-prefix-caching
package main

import (
	"bytes"
	"encoding/json"
	"fmt"
	"io"
	"net/http"
	"strings"
	"time"
)

func main() {
	const url, model = "http://localhost:8000/v1/completions", "Qwen/Qwen2.5-1.5B-Instruct"
	system := strings.Repeat("You are a helpful assistant. ", 200) // ~1200 tokens

	for i, q := range []string{"What is 2+2?", "What is 3+3?", "What is 4+4?"} {
		body, _ := json.Marshal(map[string]any{"model": model, "prompt": system + q, "max_tokens": 20})
		t0 := time.Now()
		resp, err := http.Post(url, "application/json", bytes.NewReader(body))
		if err != nil {
			fmt.Println(err)
			return
		}
		io.Copy(io.Discard, resp.Body)
		resp.Body.Close()
		fmt.Printf("request %d: %d ms\n", i, time.Since(t0).Milliseconds())
	}
}

Typical:

request 0: 285 ms      ← cold: full prefill
request 1:  48 ms      ← warm: prefix hit, only the question is prefilled
request 2:  47 ms

6x faster TTFT and 6x less GPU work, for a config flag.

5. Technical explanation#

How it works with paged KV#

1. Split the prompt into blocks (16 tokens each).
2. For each block, compute a hash of (all token ids up to and including this block).
   The hash MUST include the prefix, not just the block — otherwise blocks with the
   same content but different preceding context would collide incorrectly.
3. Look up each hash in a table:  hash → physical_block_id.
4. For the longest matching prefix of blocks, reuse them (increment refcount).
5. Prefill only the remaining tokens.
hash chain:
  block 0 hash = H(t0..t15)
  block 1 hash = H(block0_hash, t16..t31)
  block 2 hash = H(block1_hash, t32..t47)
  ...

The chained hash is essential: block content alone isn’t enough, because attention makes each block’s KV depend on everything before it.

Why block granularity matters#

Prompt A: [.......2000 tokens.......][question A]
Prompt B: [.......2000 tokens.......][question B]

With block size 16, you match 125 blocks = 2000 tokens.
The partial block containing the boundary can't be shared.

Match granularity = block size. Smaller blocks match more precisely; the standard 16 is fine.

RadixAttention (SGLang’s approach)#

Instead of a flat hash table, maintain a radix tree (prefix tree) of token sequences:

                    root
                     │
            "You are a helpful"
                   /        \
        "assistant."      "coding assistant."
              /    \              |
      "What is"  "Explain"    "Write a"

Advantages over a flat hash table:

  • Naturally represents branching conversations (a shared prefix with many continuations).
  • LRU eviction on the tree respects the prefix structure — evicting a leaf doesn’t break its parent.
  • Efficient longest-prefix-match lookup.

Particularly good for agentic and tree-search workloads where many branches share a long prefix.

The RoPE constraint#

Cached keys have position information baked in (file 05). So:

Sequence A: [system 2000 tokens][question]     system at positions 0-1999
Sequence B: [system 2000 tokens][question]     system at positions 0-1999   ✓ SHARE

Sequence C: [user preamble 50][system 2000][question]   system at positions 50-2049  ✗ CANNOT

The shared prefix must start at the same position. In practice this means: put your system prompt first, and don’t put per-request content before shared content.

This is a real prompt-engineering constraint with direct cost implications. A template that puts the user’s name before the system prompt destroys all prefix sharing.

Eviction#

The cache competes with active requests for the same block pool:

Free blocks needed for a new request → evict cached (refcount 0) blocks
Policy: LRU, usually with a preference for evicting shorter/less-shared prefixes

Blocks with refcount > 0 (in use by a running sequence) are never evictable. Cached-but-unused blocks are.

Tuning tension: a large cache improves hit rate but leaves fewer blocks for active requests, reducing concurrency. Most engines handle this automatically by making cached blocks the first eviction candidates.

6. Under the hood#

The hit-rate calculation that determines whether this matters for you:

savings = hit_rate × (shared_prefix_tokens / total_prompt_tokens) × prefill_fraction_of_cost

Example: chatbot with a 1500-token system prompt, 100-token questions,
         200-token answers, 95% hit rate.

  prefill tokens saved = 0.95 × 1500 = 1425 of 1600 = 89% of prefill
  prefill is ~40% of total GPU time for this shape
  → ~36% total cost reduction, and TTFT drops ~85%

For a RAG workload with a 20,000-token retrieved context that’s different every query, the hit rate is ~0 and prefix caching does nothing. Measure your hit rate before assuming benefit.

7. Performance implications#

Workload                       Hit rate   TTFT improvement   Cost reduction
Chat with system prompt        90-99%     3-10x              20-40%
Multi-turn conversation        95-99%     5-20x              40-70%
Few-shot classification        99%        10-50x             60-85%
Agentic loop (tools+scratchpad) 90-98%    5-15x              50-75%
RAG, distinct documents        0-20%      ~1x                0-5%
Fully unique prompts           0%         1x                 0%

Multi-turn conversation is the killer app. Without prefix caching, turn N re-prefills all N-1 previous turns — the cost grows quadratically with conversation length. With it, cost is linear.

8. Production implications#

  • Turn it on. --enable-prefix-caching in vLLM; on by default in SGLang. There is almost no downside.
  • Design prompts for cache-friendliness:
    GOOD: [static system prompt][static tools][static few-shot][dynamic user content]
BAD:  [timestamp][user id][system prompt][user content]     ← nothing shares
    Putting a timestamp at the start of your system prompt destroys the entire cache. This happens.
  • Prefix-aware routing is essential at scale (Section XII.07). If request 2 of a conversation goes to a different replica than request 1, the cache is useless. Route by conversation id or prefix hash.
  • Monitor hit rate. It’s a direct cost metric. vLLM exposes prefix cache hit rate.
  • Commercial APIs expose this explicitly (cache write vs cache read pricing, typically 10x cheaper for cached tokens). Structure prompts to exploit it.
  • Cached content is a security consideration: a shared cache across tenants could in principle leak timing information. Most implementations key the cache per-tenant or accept the risk; know which yours does.

9. Common mistakes#

Dynamic content at the start of the prompt. Timestamps, request IDs, user names. Destroys everything.

Round-robin routing with prefix caching enabled. The cache is per-replica; random routing gives you a 1/N hit rate.

Assuming it helps every workload. RAG with unique documents gets nothing.

Forgetting the RoPE position constraint. Prefixes must start at the same position.

Not measuring hit rate. You can’t optimize what you don’t measure.

Letting the cache starve active requests. Rare with good engines, but check your preemption rate after enabling it.

10. Hands-on exercise#

A. Measure the win. Run the example in section 4 with and without prefix caching. Then vary the system prompt length from 100 to 8,000 tokens and plot the TTFT improvement.

B. Multi-turn. Simulate a 20-turn conversation. Measure total prefill tokens with and without prefix caching. Plot cumulative cost vs turn number for both. Confirm the quadratic-vs-linear difference.

C. Break it. Add a timestamp to the front of the system prompt and re-measure. Confirm the hit rate drops to 0.

D. Implement it. Extend your block manager (Project 09) with a prefix hash table: chained block hashing, longest-prefix lookup, refcounting, and LRU eviction of unreferenced blocks. Verify correctness by comparing outputs to a non-caching run.

E. Routing. Simulate 4 replicas with round-robin vs prefix-hash routing for a workload with 10 distinct system prompts. Compare aggregate hit rates.

11. Interview questions#

  1. What is prefix caching and how much does it save for a chatbot workload?
  2. How does block hashing work, and why must the hash chain include the prefix?
  3. Why does RoPE constrain which prefixes can be shared?
  4. How does RadixAttention differ from a flat hash table, and when does that matter?
  5. What prompt structure maximizes cache hit rate?
  6. Why does prefix caching require prefix-aware routing at scale?
  7. Why is multi-turn conversation the highest-value case?
  8. When does prefix caching provide no benefit?

12. Further reading#

  • [ESTABLISHED] Zheng et al., “SGLang: Efficient Execution of Structured Language Model Programs” (2023) — RadixAttention
  • [REFERENCE] vLLM automatic prefix caching documentation and implementation
  • [REFERENCE] Commercial prompt-caching API documentation (compare pricing models)
  • Next: 12 — Speculative decoding
esc

↑↓ navigate↵ openesc close