Your Prompt Is the Most Expensive Thing You Compute Twice

Ask an LLM the same 4,000-token question twice, and a naive pipeline does the same work twice: it runs the full prefill over that context, computes Keys and Values for every token, stores them, and only then starts generating. The answer generation is cheap. The prefill is not — for a long shared context it can dominate the request cost.

Prefix caching (what you’ll also see marketed as “automatic prompt caching”) is the trick that stops paying for the same prefill twice. The idea is embarrassingly simple: the K and V vectors computed for a given token sequence are deterministic for a fixed model. Recompute the exact same prefix and you get the exact same Keys and Values. So if the serving runtime keeps the KV blocks around and sees the same prefix again, it can skip the prefill entirely and start sampling from the last cached token.

This post covers how it actually works, where the savings come from, how to configure it in vLLM and other serving stacks, and the real-world traps that silently disable it even when you think it’s on.

The Mechanism: Why KV Is Safe to Reuse

In the attention block of a transformer, the Query is derived from the current token, but the Keys and Values are derived from context tokens. During prefill you compute, for every token in the prompt, a Key and Value vector per attention head. When token n attends to tokens 1..n, it reads the Keys and Values of 1..n-1.

Two properties make prefix caching correct:

• Determinism. Given the same model weights, the same tokenization, and the same prefix, the K/V vectors for that prefix are bit-for-bit reproducible. There is no sampling involved in computing them — sampling starts only at generation time.
• Locality. When a new request’s prompt starts with an already-cached prefix, every one of those tokens computes the same K/V it did last time. The model’s internal state at that boundary is unchanged, so subsequent generation is exactly what it would have been had you recomputed the prefill.

# Illustration: prefill computes K/V once; generation reuses them.
# With prefix caching, prefill for the *matching prefix* is skipped.
def complete_with_prefix(prefix: str, question: str, max_new_tokens: int = 128):
    # Full prefill happens only for `question` if `prefix` is cached.
    # `prefix`'s K/V blocks are looked up, not recomputed.
    ...

The only requirement is that everything determining the prefix’s K/V — model, tokenizer, prefix text — be identical to the cached copy. That single requirement is where most of the practical traps come from.

Where the Savings Land

Cost and latency in an LLM request are split between the prefill (processing the prompt) and decode (generating new tokens). Prefix caching attacks the prefill side:

• Latency. A request that hits a warm prefix skips the forward pass over the shared tokens. A 5,000-token system prompt that would take hundreds of milliseconds to prefill can fall to a few milliseconds of cache lookup when warm. Time-to-first-token collapses.
• Throughput. Skipping prefill frees the GPU to process other requests. Instead of re-executing the same 5,000 tokens for every user, the runtime spends its compute budget on decode and on genuinely new prefixes.
• Memory (the counterintuitive one). This is where “cache” gets confusing. Prefix caching trades recompute for memory pressure. The cached KV blocks occupy GPU memory. If you cache aggressively on a small GPU, you fill the KV pool and start evicting so fast you get nothing. Prefix caching is a latency/throughput win precisely because memory is usually the scarcer resource than the recompute it saves — buy more of the pool or evict intelligently, or the savings evaporate.

import vllm

# vLLM's automomous prefix caching is a single field. `max_num_batched_tokens`
# and `max_num_seqs` control how much memory the runtime reserves.
llm = vllm.LLM(
    model="meta-llama/Meta-Llama-3.1-8B-Instruct",
    max_model_len=8192,
    gpu_memory_utilization=0.90,
    enable_prefix_caching=True,   # the whole feature, on
)

In vLLM the feature is one boolean, enable_prefix_caching=True. The heavy lifting — hashing the prefix into blocks, checking which blocks are resident, reusing them — happens automatically. But the knob that decides whether it actually works is gpu_memory_utilization and the KV pool size, not the boolean.

Hashing, Blocks, and the LRU in the Runtime

The runtime doesn’t cache the whole prompt as one opaque blob. It works in blocks (vLLM’s term for a fixed-size chunk of KV pages, typically 16 or 128 tokens). This granularity is what makes caching cheap:

1. Tokenize the incoming prompt.
2. Hash it block-by-block into block-level content hashes.
3. Look up each block in the cache; the longest run of contiguous matching blocks is the reused prefix.
4. Compute K/V only from the first non-matching token onward.
5. Append new blocks to the cache, and evict cold blocks with an LRU once the pool fills.

# Conceptually, cache lookup asks: where does my prompt stop matching?
def longest_cached_prefix(blocks: list, cache: dict) -> int:
    n = 0
    for block in blocks:
        if cache.get(block_hash(block)) == block:
            n += 1
        else:
            break
    return n

Because matching is per-block, a request benefits even when only part of its prompt is shared. This is what makes multi-turn conversations the sweet spot: every turn repeats the entire previous history as part of the prompt, so turn two reuses the whole prefix and only prefills the new user message.

The Real-World Traps That Silently Disable It

Prefix caching wins when the prefix is stable. Everything that breaks that stability quietly turns the feature into dead code. These are the traps I’ve hit in production:

Trap 1: Timing / Non-Deterministic Tokens

The K/V of a prefix are only deterministic if the same text arrives the same way. Any nondeterminism before decoding — a timestamp that changes, a random value, a UUID that’s regenerated — changes the prefix text, which changes the block hashes, which misses the cache. If your prompt embeds datetime.now() or a running trace ID, every request is a completely new prefix. The cache never hits.

# BAD: nondeterministic prefix -> cache always misses.
system_prompt = f"Today is {datetime.now().isoformat()}."

# GOOD: system prompt is stable; only the user message changes.
system_prompt = "You are a legal research assistant. Answer from the documents provided."

Trap 2: Tokenizer Drift

The cache key is built on tokens, not characters. If you change the tokenizer version, change special-token handling, or switch a BOS/EOS convention, the same visible text tokenizes differently and the block hashes change. Every prompt becomes a cache miss until the old blocks expire. Rolling a tokenizer change on a warm serving fleet is a quiet cache-flush event.

Trap 3: Model Checkpoint Rollouts

A new checkpoint is a different function. Its K/V space is different, and cached blocks computed by the old weights are not just stale — using them corrupts the output. The runtime must invalidate the prefix cache keyed to the old model and rebuild prices. This is the same lesson as the KV-cache-in-microservices post: the model name is part of the cache key, always.

Trap 4: Zero-Shot “Cache” Misuse

Prefix caching is a serving-layer optimization. It is not an API-level prompt cache. If you’re using an API provider’s “prompt caching” feature, your mileage depends on their block granularity, their minimum shared-token threshold (many charge or require a minimum prefix length before they cache), and their TTL. None of that is under your control. The rules in this post apply to the runtime you run, not the provider’s opaque cash register.

Trap 5: Batching Fragmentation

Prefix caching and continuous batching interact. To reuse a prefix, the scheduler has to pick the right requests to co-schedule. If your scheduler is always maximizing for strict ordering, cached blocks sit idle while new requests recompute. This is less a correctness bug and more a throughput leak: the feature is on, but the scheduler never gets a chance to serve the cache hits it wants.

Sizing the Cache: The Eviction Squeeze

Since cached KV blocks live in GPU memory, there’s a real budget. The runtime reserves a KV pool out of total GPU memory (controlled via gpu_memory_utilization). What fraction of the pool goes to the LRU prefix cache vs. active decode is a live trade-off:

• Too much cache, too many active requests. The pool thrashes: blocks get evicted between a request’s turns, so the second turn of the same conversation misses the first turn’s prefix. Cache hit rate collapses.
• Too little. You don’t cache enough shared prefix to make the feature matter, and every long system prompt gets recomputed.

There is no magic number; it depends on your workload’s share of reused prefixes vs. unique traffic. Start by measuring the actual hit rate the runtime reports (vLLM exposes cache-hit metrics), then tune gpu_memory_utilization and the max active sequences until the hit rate stabilizes and you aren’t evicting mid-conversation.

# Healthy signal: cache hit rate stays high while memory doesn't fragment.
# Unhealthy: high memory util but low hit rate -> you're churning blocks.
monitor_metric("prefix_cache_hit_rate")        # want: high, stable
monitor_metric("kv_cache_usage")               # want: high, stable
monitor_metric("prefix_cache_evictions_per_second")  # want: low

When Prefix Caching Doesn’t Help

Be honest about the workload before you wire this in:

• All single-turn, unique prompts. If every request is a one-off with no shared system prefix, there’s nothing to reuse. The feature burns memory to cache blocks that never hit.
• Short prompts. The recompute you save is small, and the block-management overhead plus memory pressure can be a net loss.
• Long unique contexts. A 50k-token document processed once and never again wastes the KV pool just as it evicts the genuinely shared system prompt. This is the same “huge single-use prefix → skip the shared cache” rule.

The feature pays off for the system-prompt-heavy assistant pattern: big, stable instruction blocks repeated across thousands of requests, with only the tail varying.

Configuring It Inside a Serving Stack

In a vLLM-based service, the practical config is small:

llm = vllm.LLM(
    model="meta-llama/Meta-Llama-3.1-8B-Instruct",
    max_model_len=8192,
    gpu_memory_utilization=0.90,       # leave headroom but don't starve decode
    enable_prefix_caching=True,
    enforce_eager=False,
)

What actually matters is upstream:

• Build the system prompt once, treat it as immutable per deployment, and cache it in front of the model so every request’s prompt start is byte-identical.
• Don’t inline time/random/IDs into the prefix.
• Freeze tokenizer and checkpoint versions; bake the model version into the cache-key namespace so rollouts invalidate cleanly.
• Scope the cache key by tenant when several tenants share the runtime, exactly as you would for the KV cache in a microservice design — a prefix cache is ultimately a retained copy of the prompt.

These four changes make the boolean actually worth turning on. Without them, enable_prefix_caching=True is a placebo.

Summary

• Prefix caching reuses deterministic prefill K/V blocks for a repeated prompt prefix, skipping the recompute.
• The savings are latency and throughput on the prefill side; the cost is GPU memory, so sizing the KV pool and eviction is the real lever.
• It works block-by-block, so multi-turn conversations — where history repeats every turn — benefit most.
• Nondeterministic prefixes, tokenizer drift, and model rollouts all silently kill the cache. Keep prefixes stable, freeze the tokenizer, and version the model in the cache key.
• It’s a winner for system-prompt-heavy, shared-prefix workloads, and a net negative for all-unique, short, or single-use-long traffic.

Get the prefix stable and the cache keyed right, and every repeated system prompt stops costing you compute. Get the prefix unstable, and you’re running the most expensive incantation in the fleet for nothing.