Why Identical Prompts Still Miss the Prefix Cache

The Hidden Enemies of Prefix Caching: Why Seemingly Identical Prompts Cause Cache Misses and How to Operate Around Them

When you first deploy vLLM or SGLang and look at your prefix cache metrics, the numbers can be baffling. You've confirmed that every request uses the same system prompt, yet the hit rate is sitting near zero. The logs show nothing wrong with the requests themselves.

There's already plenty written about eviction policies (LRU) and request distribution issues. This post focuses on three causes that occur more frequently and are far less visible: tokenizer variation, multi-instance routing fragmentation, and rolling context. Each has its own diagnosis and mitigation, so it's worth understanding them separately.

How Prefix Caching Produces Misses

vLLM's Automatic Prefix Caching identifies KV blocks by hash. Each block's hash is computed as hash(previous block hash, token ID sequence of current block). Starting in v0.11, the default algorithm switched to SHA-256, reducing the risk of hash collisions — but if even a single token ID changes, the hash for that block and every subsequent block changes with it.

SGLang's RadixAttention operates on the same principle. Because it matches prefixes using a Radix Tree, if the last token of a shared prefix differs, the branching point in the tree shifts, and the reusable span drops to zero.

The problem is that "token IDs changing" doesn't require any difference in the text itself. The same string can produce different token sequences.

Trap 1: How a Tokenizer Produces Different Tokens from the Same String

This is the most common root cause in production.

Duplicate BOS tokens: In HuggingFace tokenizers, if add_bos_token=True and the chat template also has logic to insert <s>, the BOS token ends up in the sequence twice. vLLM's handling of add_bos_token can vary depending on server startup flags, so changing your deployment environment can cause the hash of the first prefix block to differ even for the same model.

from transformers import AutoTokenizer

tok = AutoTokenizer.from_pretrained("meta-llama/Llama-3-8B-Instruct")
sys_prompt = "You are a helpful assistant."

tok.add_bos_token = True
ids_with_bos = tok.encode(sys_prompt)

tok.add_bos_token = False
ids_without_bos = tok.encode(sys_prompt)

print("with BOS:   ", ids_with_bos[:5])
print("without BOS:", ids_without_bos[:5])
# with BOS:    [1, 2683, 527, 264, 11190]
# without BOS: [2683, 527, 264, 11190, ...]

The very first token differs, causing a cascading hash change across every subsequent block.

Trailing whitespace: This one is subtler. A single trailing space on the system prompt is enough to change the token sequence. SentencePiece-based tokenizers (LLaMA family) encode the space preceding a word as part of that word's token, so a trailing space changes the token ID of the first token in the following user message.

sys_a = "You are a helpful assistant."
sys_b = "You are a helpful assistant. "  # one trailing space

user_msg = "What is the capital of France?"

ids_a = tok.encode(sys_a + user_msg)
ids_b = tok.encode(sys_b + user_msg)

diff_pos = next(i for i, (a, b) in enumerate(zip(ids_a, ids_b)) if a != b)
print(f"첫 불일치 위치: {diff_pos}번째 토큰")
print(f"  ids_a[{diff_pos}]={ids_a[diff_pos]}, ids_b[{diff_pos}]={ids_b[diff_pos]}")

From the block where this mismatch occurs, the prefix hash diverges. prefix_match_length becomes 0.

If your service layer has multiple code paths that construct prompts — API gateway, pipeline transformations, client libraries — you need to log the actual token IDs from each path and compare them directly. Diffing at the text level will not catch this problem.

Trap 2: How Prefix Cache Efficiency Fragments Across Instances Under Round-Robin Routing

Horizontal scaling dilutes prefix caching efficiency linearly.

Consider a round-robin router distributing requests across N instances. The first request with prefix P lands on instance 1 — cache miss, P gets cached on instance 1. The next request with the same prefix goes to instance 2 — another miss, P gets cached on instance 2. Every instance sees a miss until all N instances have cached P.

If p is the fraction of requests sharing a common prefix and N is the instance count, the theoretical upper bound on hit rate is:

theoretical hit rate upper bound ≤ p × (1 - 1/N)

Even with N=8 and 90% of traffic sharing a prefix, hit rate plateaus around 79%. Factor in LRU eviction and real-world request distribution skew, and measured values will be lower still.

The cache-aware load balancer introduced in SGLang v0.4 mitigates this. It queries each instance's Radix Tree ahead of time and routes to whichever instance has the highest prefix match rate. Internal experiments reported a 3.8× improvement in hit rate and 1.9× improvement in throughput.

Sticky session routing has its own problem: requests sharing a popular system prompt pile onto the same instance, causing GPU utilization to spike on that instance alone. vLLM has no built-in cache-aware load balancer, so you'll need to implement one yourself, and its real-world effectiveness depends on how well it accounts for instance load.

Trap 3: Rolling Context Patterns Structurally Defeat Prefix Caching

In chatbot and code assistant serving, when the context length limit is hit, the common approach is a sliding window that drops the oldest messages and appends new ones. With this pattern, each request's prefix changes every turn.

Turn 1: [system][user_1]
Turn 2: [system][user_1][asst_1][user_2]
Turn 3: [system][user_1][asst_1][user_2][asst_2][user_3]
...
Window exceeded:
Turn k: [system][user_2][asst_2]...[user_k]   ← [user_1] dropped

The moment [user_1] is dropped, every hash after the [system] block changes. Only the system prompt block gets reused; the entire conversation history has to be prefilled from scratch on every request. Prefill cost keeps accumulating as conversations grow longer.

To detect this pattern in session logs, compute the prefix overlap ratio between consecutive turns:

def detect_rolling_context(session_turns):
    """각 턴 사이의 prefix overlap 비율을 계산한다."""
    overlaps = []
    for i in range(1, len(session_turns)):
        prev_ids = session_turns[i-1]['token_ids']
        curr_ids = session_turns[i]['token_ids']
        overlap_len = 0
        for a, b in zip(prev_ids, curr_ids):
            if a == b:
                overlap_len += 1
            else:
                break
        overlaps.append(overlap_len / max(len(curr_ids), 1))
    # overlap 비율이 단조 감소하면 rolling context 패턴
    return overlaps

In this pattern, enabling Prefix Caching does not meaningfully reduce TTFT. There are two alternatives.

Sticky session routing: Pin all requests with the same session ID to the same instance. SGLang retains KV cache blocks in its LRU cache after a request completes, so subsequent turns arriving at the same instance have a good chance of reusing the previous turn's KV cache. The risk that session caches are lost on instance restarts or scale-down events should be handled by checkpointing at a higher layer.

Prefill-decode disaggregation: Store session KV caches in external storage and have the prefill server restore them on the next request to resume from where it left off. This is more complex to implement but also resolves the load imbalance problem that sticky sessions introduce.

Diagnosing the Three Traps

When hit rate is low, start with vLLM's Prometheus counters.

# vLLM metrics에서 prefix cache 지표 추출
curl -s http://localhost:8000/metrics | grep -E 'prefix_cache|gpu_cache'

# 출력 예시:
# vllm:prefix_cache_queries_total{model_name="llama3"} 42300
# vllm:prefix_cache_hits_total{model_name="llama3"} 1240
# vllm:gpu_cache_usage_perc{model_name="llama3"} 0.34

# PromQL rolling hit rate
# rate(vllm:prefix_cache_hits_total[5m]) / rate(vllm:prefix_cache_queries_total[5m])

SGLang exposes a sglang:cache_hit_rate gauge at /metrics when the server is started with --enable-metrics.

Decision flow for narrowing down the cause:

• Hit rate ≈ 0, single instance: Suspect tokenizer variation. Log the actual token IDs from the service layer and diff them across requests.
• Hit rate significantly below p × (1 - 1/N) with N instances: Suspect round-robin fragmentation. If vllm:gpu_cache_usage_perc is similarly low across all instances, that confirms it.
• Hit rate converges toward the system prompt token ratio (sys_len / total_len): Rolling context pattern. The system prompt block is being reused, but the conversation history is never matching.

Operational Mitigations and Trade-offs

Tokenizer variation: Add a normalization step in the service layer where prompts are constructed. Manage the system prompt as a single canonical string in one place, and normalize trailing whitespace. Also explicitly set --tokenizer-mode at vLLM server startup so BOS handling doesn't vary across deployments.

Routing fragmentation: If you have only a few distinct system prompts and high request volume, dedicated prefix serving works better than sticky sessions. Stand up an instance dedicated to shared prefixes, keep it warm with the prefix KV cache loaded, and route all matching requests there.

Here's what the memory reservation cost looks like: 4096-token system prompt, 32 layers, GQA with 4 KV heads, head dim 128, BF16:

KV cache = 2(K+V) × 32 layers × 4 KV heads × 128 head_dim × 4096 tokens × 2 bytes
         = 268,435,456 bytes ≈ 256 MB

The KV cache for the prefix itself is 256 MB — roughly 0.3% of an A100 80 GB, which is not a significant burden. That said, you're tying up an entire GPU instance to hold this cache, and if the number of distinct system prompts grows into the dozens, the number of dedicated prefix instances grows with it.

Rolling context: Implement sticky session routing first. SGLang's LRU KV cache retention actually pays off once sessions are pinned. Fix the routing before touching Prefix Caching configuration.

When Prefix Caching Actually Works

Even if you avoid all three traps, there are three numbers to check before expecting meaningful TTFT improvement.

• System prompt token count / average total input token count: If this is below 0.3, the cacheable span is short and the savings are small.
• Fraction of requests sharing the same system prompt: The more instances you run, the higher this fraction needs to be to offset routing fragmentation.
• Average turns per session: If sessions average one to two turns, the cache warm-up cost may outweigh the benefit.

When you first get a hit rate 0% alert, it's tempting to reach for eviction policy settings. Logging the token IDs first will save you more time.