Same full cache, same incoming item — three eviction policies pick three different victims.
There’s an old joke that there are only two hard problems in computer science: cache invalidation, naming things, and off-by-one errors. Caching earns its spot on that list. The idea is trivial — keep the expensive-to-fetch things close so you don’t refetch them. The hard parts are two questions the diagram above is really about: what do you throw out when you’re full, and when is what you’re holding wrong? These questions never went away; they just moved into your AI stack.
Why caching works at all
Caching pays off because access patterns aren’t uniform. Real workloads have locality: things used recently tend to be used again soon (temporal locality), and popular things stay popular (a Zipfian distribution — a small fraction of items get most of the requests). A cache exploits that skew. If 5% of your keys serve 80% of your traffic, a cache holding that 5% turns most requests into fast hits.
The metric that matters is the hit rate — the fraction of requests the cache satisfies without going to the slow backing store. A cache with a 95% hit rate and one with a 70% hit rate aren’t slightly different; they’re different systems, because the misses hit the slow path and the misses dominate your tail latency. Everything about eviction is in service of keeping that hit rate high.
The eviction question
A cache is finite. When it’s full and something new arrives, something has to leave. The eviction policy is how you choose the victim — and, crucially, it’s a bet about the future based on the past. Look at the diagram’s four cached items, each with different recency and frequency, and watch three policies disagree:
- LRU — Least Recently Used. Evict whatever’s gone untouched the longest. It bets that recency predicts the future: if you haven’t used it lately, you probably won’t soon. It evicts B (idle 9 minutes). LRU is the sensible default for most workloads and the most common policy in practice.
- LFU — Least Frequently Used. Evict whatever’s been used the fewest times. It bets on popularity: a long-term favorite deserves to stay even if it’s been quiet for a moment. Here it also drops B (only 3 hits). LFU shines when there’s a stable set of hot items, but it has a flaw — an item that was popular last week can squat in the cache long after it’s gone cold (“cache pollution”). Real LFU variants add aging to fix this.
- FIFO — First In, First Out. Evict the oldest arrival, ignoring usage entirely. It evicts D. Simple and cheap, but it will happily throw out a red-hot item just because it’s been around a while. Usually the wrong choice unless simplicity is paramount.
There’s no universally best policy — it depends on your access pattern. That’s why modern caches often use adaptive policies (like ARC, which balances recency and frequency automatically) or segmented LRU. But if you understand these three, you understand the axis they all move along: recency vs frequency vs arrival order.
The other hard problem: invalidation
Eviction is about space. Invalidation is about correctness. A cached value is a copy, and the moment the source of truth changes, your copy is a lie. Serve it and you’ve shown a user stale data. The strategies — TTL-based expiry, write-through (update cache and store together), write-invalidate (drop the cache entry on write) — are all answers to “how do I keep the copy honest?” Get it wrong in the safe direction and you waste memory; get it wrong in the unsafe direction and you serve wrong answers. This is the same TTL tension we saw in DNS: a cache is only as fresh as its invalidation strategy.
The AI-era version of all of this
Caching didn’t get less relevant with LLMs — it became one of the primary levers for cost, not just latency.
Prompt caching is caching with an eviction policy. Prompt caching stores the processed representation of a prompt prefix so repeated calls skip recomputation. But that cache is finite and time-bounded — providers evict entries after a few minutes of disuse (an LRU-flavored decision). Structuring your prompts so the stable, cacheable prefix comes first is literally optimizing for cache hit rate, and it directly cuts your token bill.
The KV cache is why long generations get expensive. During generation, a model caches the key/value tensors for every token it’s already processed so it doesn’t recompute them. That KV cache grows with context length and lives in precious GPU memory. Serving systems make real eviction decisions about it — which sequences to keep warm, which to drop — and those decisions drive throughput and cost per request. It’s LRU, but the currency is GPU HBM.
Embedding and response caches save real money. Caching embeddings so you never re-embed identical text, and caching responses to repeated queries, are among the highest-ROI optimizations in a RAG system. And they carry the classic invalidation risk: cache a response, update the underlying documents, and now you’re serving a confidently stale answer. The context window is a budget, and caching is how you avoid paying for the same tokens twice.
The takeaway
Caching is deceptively deep. The idea is a one-liner; the engineering is entirely in the two hard questions — what to evict and when your copy is wrong. The eviction policy is a bet about the future dressed up as a data-structure choice, and picking one that matches your access pattern is the difference between a 95% and a 70% hit rate. None of this changed when AI arrived; the stakes just went up, because now the thing you’re caching isn’t a database row — it’s expensive tokens and scarce GPU memory. Understand the recency-versus-frequency bet, respect invalidation, and you have a lever that works on everything from a CPU cache to a fleet of inference servers.