Prompt Cache Economics: Hit Rate, Prefix Length, and Break-Even

A repeated prompt prefix is work that has already been done. Caching it avoids recomputing the attention keys and values for those tokens, and the saving is not marginal: prefill is the compute-bound phase, so skipping it removes real arithmetic rather than hiding latency. The economics of the technique are governed by three quantities that are easy to state and hard to estimate: how much of a prompt is shared, how finely the cache can detect the sharing, and what the retained state costs in memory that could otherwise hold concurrent sequences.

What a hit removes from the bill

For a prompt of $N$ tokens of which $H$ are a cache hit, the avoided work is the prefill forward pass over those $H$ tokens: roughly $2PH$ flops for the dense layers, plus attention terms that scale with position. If the model is compute-bound during prefill, the time saved is close to the flop count divided by peak throughput. If it is bandwidth-bound because the prompt is short or the batch is large, the saving is smaller, because the weights had to be read anyway for the uncached portion.

The saving is also conditional on the hit being a prefix. Attention is causal, so the keys and values for token $i$ depend only on tokens up to $i$. A cache can therefore reuse state for positions $0 \ldots H-1$ if and only if the new request begins with exactly the same $H$ tokens. A shared span in the middle of a prompt is worthless unless everything before it also matches, and this constraint, not the storage cost, is what limits hit rates in practice.

Two consequences follow. Prompt templates that place variable content at the end achieve high hit rates; templates that place it near the beginning achieve almost none. And a cache key must be the exact token sequence, not the text: two requests whose strings differ in whitespace, or that tokenize differently because of a normalization step, are different prefixes as far as the attention state is concerned. Byte-level equality of the rendered prompt is the requirement, and any layer that reorders or re-renders the prompt invalidates the assumption.

Chunking, and the granularity of a hit

Storing cache state per token would require an index entry per token and would make eviction decisions at a granularity too fine to be useful. Real systems hash the prefix in blocks, conventionally 16 tokens, and store the state at block boundaries. A hit is then detected by walking the block hashes of the incoming prompt until one misses, which yields a hit length rounded down to a multiple of the block size. A prompt that shares 1,000 tokens with a cached one but diverges at token 1,007 gets a 992-token hit, not 1,000.

The loss from this rounding is bounded by one block, so at 16 tokens it is at most 15 tokens of recomputation. That is negligible for long prompts and noticeable for short ones, which is why block size is chosen against the shortest prompt the system expects to serve rather than the longest. Larger blocks reduce index overhead and hash computation; smaller blocks reduce rounding loss and increase the number of index entries by the same factor. At 4 bytes per entry and 16 tokens per block, a million cached tokens needs 62,500 entries, about 250 KB of index, which is small against the cache itself.

The hash must identify the block’s content together with its position in the chain, otherwise two different prompts sharing a common opening would collide on later blocks. The standard construction chains the hash: the key for block $i$ incorporates the key for block $i-1$ plus the tokens of block $i$. This makes the key an identifier for the entire prefix up to that point, which is exactly the condition under which attention state is reusable. Collisions in a 64-bit or 128-bit hash are rare enough to ignore in the same way that content-addressed storage ignores them, but the chaining is not optional.

The storage competes with concurrency

Cached state is KV cache, and KV cache is the resource that bounds how many sequences a replica can hold, as derived in the memory budget. Every block retained for a future request is a block unavailable to a request in flight. A cache with no eviction policy will eventually consume the entire budget and start refusing work, which is why every implementation pairs the cache with an LRU or similar policy and a configured maximum share of memory.

The trade is therefore not free memory against saved compute. It is concurrency against saved compute, and the exchange rate can be computed. Retaining $M_c$ bytes of cache at a mean sequence size of $S$ bytes costs $M_c/S$ concurrent sequences. Each of those sequences, if resident, would have produced tokens at a rate set by the batch economics of the marginal cost analysis. The cache pays for itself when the prefill work it avoids exceeds the decode work those displaced sequences would have performed.

The inequality is easier to reason about in time than in bytes. A cache hit of $H$ tokens saves approximately $2PH/F$ seconds of prefill. The memory holding that cached block costs one block of KV space for as long as it is retained, and that block, if used for decode, would have supported some number of output tokens over the retention interval. The break-even hit rate is the ratio of those two quantities, and it falls as prompts get longer: at $H$ in the thousands, the prefill saving dominates almost any plausible retention cost. At $H$ in the tens, the cache is a net loss unless the prompt is repeated many times within the retention window.

Measuring the hit rate that matters

Two hit rates are routinely confused. The token-weighted hit rate is the fraction of all prompt tokens served from cache; the request-weighted hit rate is the fraction of requests that hit at all. Token-weighted is the one that predicts compute savings, because a single request with a 10,000-token prefix that hits is worth more than a hundred short requests that miss. A dashboard reporting only request-level hits will understate the benefit of caching long system prompts and overstate the benefit of caching short ones.

The achievable ceiling is set by the traffic, not by the implementation. If a workload consists of $R$ distinct prompt templates used with varying user content appended, the token-weighted hit rate is bounded by the fraction of tokens in the shared prefixes. If the workload has no repeated prefixes, the ceiling is zero and no amount of cache tuning will help. Estimating the ceiling before building the cache is a matter of sampling prompt prefixes and counting distinct block-hash chains, which is the same computation the cache itself performs at admission.

import hashlib

def hit_rate(prompts, block=16):
    """Token-weighted hit rate over a static set of tokenized prompts."""
    seen, hits, total = set(), 0, 0
    for toks in prompts:
        chain = b""
        for i in range(0, len(toks) - block + 1, block):
            chunk = ",".join(map(str, toks[i:i + block])).encode()
            # chain each block into the previous key, so a key names the
            # whole prefix rather than one block in isolation
            chain = hashlib.blake2b(chain + b"|" + chunk, digest_size=16).digest()
            if chain in seen:
                hits += block
            else:
                seen.add(chain)
        total += len(toks)
    return hits / total if total else 0.0

Run against a day of sampled prompts, this yields the ceiling directly. If the number is low, the useful intervention is upstream of the cache: restructuring prompts so that the stable part comes first, or consolidating near-duplicate templates. If the number is high, the cache configuration is the lever, and the remaining question is how much memory to give it.

Where caching makes cost accounting harder

A cached request consumes fewer flops than an uncached one, but it consumes the same output tokens and the same sequence slot. A billing model that charges per token uniformly therefore overcharges cached input, which is why price sheets commonly list a separate, lower rate for cached input tokens. That discount reflects the real saving in compute, but it is applied at a rate that has to be chosen in advance rather than derived per request.

The harder accounting problem is attribution. Cache state is shared, so the cost of computing a prefix is paid once by whichever request arrived first and amortized across all later requests that hit. Deciding which request bears the original cost is a policy question with no technical answer, and it matters when multiple tenants share a pool: one tenant’s long prefix can occupy memory that another tenant’s requests need. Per-tenant cache quotas, rather than a global LRU, are the usual resolution, at the cost of lower aggregate hit rates. The trade is the same one that appears in capacity planning, where shared resources must be partitioned without knowing the future demand for each partition.