This site has two caches, and they close with the same admission. LRU Cache evicts whoever's gone longest without being
touched; LFU Cache evicts whoever's been touched the
fewest times overall. Both are O(1) on get and put. Neither
page's own Complexity section settles which one actually keeps more of the right things cached —
LFU Cache's own words are "picking between them is a bet about the real workload, not something
either page's own complexity bound can settle." This guide takes that bet literally: it runs both
pages' own shipped reference implementations, unmodified, against two small synthetic workloads —
one built to expose each policy's real weakness — and measures the real hit rates rather than
reasoning about them in the abstract.
A cache's complexity bound says how fast one get or put runs. It says
nothing about how often a get is a hit in the first place — that depends entirely on
which entries the policy chose to keep, which depends entirely on the sequence of keys a real
caller actually sends it. Two workloads below are built to disagree about that sequence as sharply
as possible: one where a small set of entries is genuinely, persistently more valuable than
everything else (LFU's bet pays off), and one where the entries that used to be valuable aren't
anymore (LRU's bet pays off, and LFU's can fail completely).
Picture a cache sitting in front of something that gets hit constantly by a small set of hot keys — plus, periodically, a much larger flood of keys that are each touched exactly once and never again: a nightly batch report, a backup job walking every row once, a log tailer scanning a day's worth of entries. Each flood alone is bigger than the cache. The question is whether the flood is allowed to evict the hot core it otherwise never competes with.
Under LRU, yes: recency is the only thing that matters, and every key in the flood is, for one moment, more recent than the hot core. By the time the flood ends, the hot core has been completely pushed out — it has to be re-faulted in from scratch after every single flood, no matter how many times it was touched before the flood started. Under LFU, the hot core's frequency count survives the flood untouched: each flood key arrives at frequency 1, which is already the lowest frequency in the cache the moment it arrives (a brand-new key's frequency can't be lower than 1), so flood keys evict each other, never the hot core, as long as the hot core's own frequency is already above 1 when the flood starts.
At capacity = 1,000 — a 100-key hot core touched 10 times per cycle, then a flood of 3,000
brand-new one-time keys, repeated for 20 cycles — LRU's hot-core hit rate is exactly
90.00% (9 hits out of every 10 touches: the first touch after each flood is always
a forced re-fault, and nothing else ever evicts the hot core mid-cycle). LFU's hot-core hit rate is
99.50% — the only misses are the very first touch of each hot key, ever; once a
hot key has been touched twice, no flood dislodges it again. That gap holds at every capacity
tested (200 through 5,000, same ratios throughout, since every workload parameter scales with
capacity) and widens the more times a key is touched per cycle before the flood arrives — at 50
touches per cycle LRU's floor rises to 98.00%, a fixed (touches−1)/touches, while
LFU stays within a hair of 100% regardless.
Now the opposite shape: a set of keys is genuinely hot for a long stretch, then popularity shifts entirely to a different, equally-sized set that was never touched before — a trending topic cooling off while a new one takes over, a feature flag's old cohort being retired in favor of a new one, the start of a new business day's working set. The old set's keys don't come back. The question is how fast each policy adapts.
LRU adapts almost immediately: a new key is, by definition, the most recent thing touched, so it only has to wait for the single oldest entry to cycle out, which happens on the very next miss. LFU can do far worse than "slow to adapt" — it can get stuck permanently. The old set spent a long stretch building up a high frequency count. When the new set's keys start arriving, each one lands at frequency 1 — the global minimum — so the next new key to arrive evicts the previous new key (also frequency 1), never the old, stale, but much-higher-frequency set sitting untouched. The new keys evict each other in an endless round-robin while the genuinely cold old keys squat in the cache indefinitely, simply because their frequency count was earned a long time ago and LFU — as built on this site, with no aging or decay — never forgets it.
At capacity = 1,000 — 1,000 keys fill the cache exactly, each touched 30 times, then a second, disjoint set of 1,000 keys is touched 30 times each — LRU's hit rate on the new set is 96.67% (29 hits out of every 30 touches, the standard "one forced miss, then it sticks" shape). LFU's hit rate on the new set is a literal 0.00% — not a small number, not a slow convergence that would improve given more rounds: it stays exactly 0.00% at 30 rounds, 100 rounds, 1,000 rounds, even 10,000 rounds. The new keys never stop evicting each other, because nothing in this page's reference implementation (or the real LFU algorithm it implements) ever lowers a frequency once it's been earned. This is precisely the "aging problem" LFU Cache's own page names in passing — real production systems that use frequency at all almost always decay it over time for exactly this reason — measured here at its most extreme, not just asserted.
If the hot set can shift entirely over the cache's lifetime — and most real caches eventually see this, even if rarely — plain LFU's failure mode above is not a rounding error, it's a permanent correctness-shaped problem: popular-once keys can squat forever. LRU degrades gracefully in exactly the situation LFU degrades catastrophically in. If the hot set is genuinely stable and the real threat is periodic one-time floods — batch jobs, scans, backups, anything that touches a huge number of keys exactly once — LFU's frequency memory is a real, measured win, and LRU pays for it every single flood. Most production systems that care about this trade-off don't pick one pure policy; they blend recency and frequency (or decay frequency over time) specifically to get the flood-resistance above without the permanent-lock-in risk — a combination neither pure policy on this site implements.
| Workload | LRU Cache | LFU Cache | Winner |
|---|---|---|---|
| Stable hot core + periodic one-time floods | 90.00% hot-core hit rate (10 touches/cycle) | 99.50% hot-core hit rate | LFU, and it widens with more touches/cycle |
| Popularity reversal (hot set changes entirely) | 96.67% hit rate on the new set | 0.00% hit rate on the new set, permanently | LRU, decisively |