Caching — Hit Rates, Zipf and the Working Set

What a cache of a given size actually buys under realistic popularity skew, and why prefix caching is governed by a different quantity than object caching.

AI SystemsAdvanced⏱ 1 hour9 min readcachingzipfhit rateLRUworking set

1 problem →

AssumesLittle's Law and the Capacity of a Serving System · Expectation, Variance and Conditional Expectation

What a hit rate is worth

PropositionEffective latency under a cache

Let $h$ be the probability a request hits, $t_{\text{hit}}$ the cost of a hit, and $t_{\text{miss}}$ the cost of a miss (including the work to populate the cache). Then

\E[T] \;=\; h\,t_{\text{hit}} + (1-h)\,t_{\text{miss}} \;=\; t_{\text{miss}} - h\,(t_{\text{miss}} - t_{\text{hit}}) .

CorollaryA cache cannot beat its own miss path

The speedup relative to no cache is

S(h) \;=\; \frac{t_{\text{miss}}}{\E[T]} \;=\; \frac{1}{(1-h) + h\,t_{\text{hit}}/t_{\text{miss}}} \;\xrightarrow[h \to 1]{}\; \frac{t_{\text{miss}}}{t_{\text{hit}}} ,

and for $h$ below $1$ the miss term $(1-h)$ dominates as soon as $1-h \gtrsim t_{\text{hit}}/t_{\text{miss}}$ .

Key idea

With $t_{\text{miss}}/t_{\text{hit}} = 100$ , a hit rate of 90% gives speedup $1/(0.1 + 0.009) \approx 9.2$ , and 99% gives $1/(0.01+0.009) \approx 53$ . The last percent of hit rate is worth more than the first fifty. Cache work is therefore worth doing precisely when you are already close to the ceiling — the opposite of most optimisation.

Where hit rates come from

DefinitionZipf popularity

Items ranked $1,\dots,N$ by popularity have request probabilities

p_i \;=\; \frac{i^{-a}}{H_N(a)}, \qquad H_N(a) = \sum_{j=1}^N j^{-a},

with $a > 0$ the skew exponent. $H_N(a)$ is the generalised harmonic number. Larger $a$ means more concentrated popularity.

PropositionStatic optimal hit rate under a Zipf popularity law

A cache of capacity $C$ holding the $C$ most popular items — the best any eviction policy can do against i.i.d. requests — achieves hit rate

h(C) \;=\; \sum_{i=1}^{C} p_i \;=\; \frac{H_C(a)}{H_N(a)} .

CorollaryThe power-law form of the hit rate

For $0 < a < 1$ and $1 \ll C \ll N$ ,

h(C) \;\approx\; \left(\frac{C}{N}\right)^{1-a} ,

for $a = 1$ , $h(C) \approx \ln C / \ln N$ , and for $a > 1$ , $h(C) \to$ a constant close to $1$ even for $C \ll N$ .

Checking the approximation against exact sums with $N = 10^6$ :

$a$	$C$	exact $h$	approximation
0.5	$10^3$	0.031	0.032
0.5	$10^4$	0.099	0.100
0.8	$10^3$	0.207	0.251
1.0	$10^3$	0.520	0.500
1.2	$10^3$	0.822	—

Key idea

For $a < 1$ the hit rate is a power law in cache size, so there is no knee. Going from 1 GB to 10 GB multiplies the hit rate by $10^{1-a}$ — at $a = 0.8$ , a factor of $1.58$ — and going from 10 GB to 100 GB does exactly the same again. Cache sizing is therefore an economic question with no natural stopping point, which is why it is usually settled by cost per byte rather than by finding a threshold.

LRU rather than an oracle

Real caches do not know the popularity ranking. The standard analytic handle is Che's approximation.

HeuristicChe's approximation for LRU

Heuristic — a reasoning shortcut that predicts the right answer in the regimes discussed here. It is not a proof and can fail outside them.

Define the characteristic time $t_C$ as the unique solution of

\sum_{i=1}^{N}\Bigl(1 - e^{-p_i \lambda t_C}\Bigr) \;=\; C ,

where $\lambda$ is the total request rate. Then item $i$ 's hit probability is approximately $1 - e^{-p_i \lambda t_C}$ , and the overall LRU hit rate is $\sum_i p_i\bigl(1-e^{-p_i\lambda t_C}\bigr)$ .

Assumptions

The approximation replaces the per-item eviction time, which genuinely depends on the whole request sequence, by a single deterministic constant shared by all items. It is an approximation with no general error bound, reported to be accurate for large caches under independent-reference workloads, and it is offered here as a modelling tool rather than a theorem.

Prefix caching is a different problem

Caching an LLM's KV state for a shared prompt prefix does not fit the model above, and the reason is worth stating precisely: the unit of reuse is not an object but a prefix, and prefixes form a tree rather than a set.

PropositionPrefill saved by a shared prefix

Let a request have prompt length $S$ of which the first $k$ tokens are already cached. Using the prefill cost $C_{\text{fwd}}(S) \approx 2NS + 4LdS^2$ from Inference Arithmetic and the Roofline, the work saved is

C_{\text{fwd}}(S) - \bigl[C_{\text{fwd}}(S) - C_{\text{fwd}}(k)\bigr]_{\text{recomputed}} \;=\; 2Nk + 4Ld\,k^2 ,

so the saving is superlinear in the cached prefix length whenever the quadratic attention term is not negligible.

Key idea

Object caches save a fixed cost per hit; prefix caches save a cost that grows faster than linearly in how much of the prompt is shared. A system prompt shared across every request is therefore worth far more than its token count suggests, and the correct eviction policy weights entries by $2Nk + 4Ldk^2$ rather than by recency — a cost-aware policy, not an LRU one.

What this does not say

Nothing here models cache coherence. A read-only cache of immutable KV blocks has no invalidation problem; a cache of anything mutable does, and by the argument in Scaling Limits — Amdahl, Gustafson and the Coherency Penalty cross-replica invalidation introduces exactly the pairwise coherency term that produces a throughput maximum. Distributed caches with invalidation are in the retrograde regime, and their capacity curve should be measured rather than assumed monotone.

References

PaperH. Che, Y. Tung, Z. Wang (2002). Hierarchical Web Caching Systems: Modeling, Design and Experimental ResultsSource of the characteristic-time approximation for LRU quoted here as a heuristic.
PaperL. Breslau, P. Cao, L. Fan, G. Phillips, S. Shenker (1999). Web Caching and Zipf-like Distributions: Evidence and ImplicationsThe measurement study behind the Zipf modelling assumption and its consequences for hit rates.

These works are cited as sources to read, not reproduced. All exposition, examples and problems on this site are written independently; where an argument is standard, the citation points to a canonical treatment.

Results stated on this page

PropositionEffective latency under a cacheproof includedMean latency is the hit rate times the hit cost plus the miss rate times the miss cost, so the benefit is linear in the hit rate and bounded by the miss cost.
PropositionStatic optimal hit rate under a Zipf popularity lawproof includedCaching the C most popular of N items under Zipf exponent a gives a hit rate equal to a ratio of generalised harmonic numbers.
CorollaryThe power-law form of the hit rateproof includedFor exponent below one the hit rate grows like (C/N)^(1−a), so each order of magnitude of cache buys a fixed multiplicative gain.
CorollaryA cache cannot beat its own miss pathproof includedHowever large the cache, speedup is capped by the ratio of miss cost to hit cost, which is Amdahl's law with the miss rate as the serial fraction.
DefinitionZipf popularityRank-ordered request probabilities proportional to a negative power of the rank, normalised by a generalised harmonic number.
HeuristicChe's approximation for LRUReplacing each item's eviction time by one shared characteristic time gives a closed-form estimate of the LRU hit rate.
PropositionPrefill saved by a shared prefixproof includedA cached prompt prefix of k tokens saves 2Nk + 4Ldk^2 FLOPs, which is superlinear in the shared length.

Problems (1)

All problems

Cache hit rates under Zipf popularityCodingIntermediate⏱ 1 hour