Most caches evict on the way out — LRU kicks out the least recently used item when space runs low. TinyLFU flips the question: it decides on the way in. When a new item arrives and the cache is full, TinyLFU asks, "Is this new item accessed more frequently than the victim we're about to evict?" If no, the new item is rejected. The incumbent stays.

This matters because LRU has a fatal weakness: scan pollution. A single sequential scan through cold data — a cron job walking every user record, a crawler hitting every URL once — will blow away your entire hot set. LRU sees "recent access" and assumes "valuable." TinyLFU sees "one access, ever" and says "no thanks."

The implementation uses a Count-Min Sketch with a decay mechanism (called the "aging" or "reset" step). Every access increments the sketch. Every N accesses (typically when total samples hit a threshold like 10× the cache size), every counter is halved. This gives you a frequency estimate over a sliding window without storing per-key history.

Real-world example: Caffeine, the JVM caching library that replaced Guava Cache, uses Window-TinyLFU (W-TinyLFU). It splits the cache into a small 1% "window" (LRU) that catches new arrivals, and a 99% "main" region protected by TinyLFU admission. New items get a probationary period in the window; only if they earn their keep do they get promoted past the admission filter. Caffeine's hit rates beat plain LRU by 5-15% on real workloads — sometimes 30%+ on scan-heavy traces like database access logs.

The rule of thumb: if your workload has any sequential scans, one-shot lookups, or long-tail cold reads mixed with a hot working set, TinyLFU admission will beat LRU. Memory cost: roughly 8 bits per cache slot for the sketch (4 counters × 2 bits, or similar). For a 1M-entry cache, that's ~1MB of overhead for admission control — often earning back 10× that in avoided evictions.

When to skip it: if your workload is uniformly random (every key equally likely), TinyLFU adds overhead with no benefit — there is no hot set to protect. Same if your cache is large enough to hold the entire working set; admission control only matters when you're forced to choose.

The insight: recency is a proxy for frequency, and it's a bad one under adversarial access patterns. Measuring frequency directly, cheaply, changes the game.