LRU vs LFU Cache: When Recency Beats Frequency, and When It Doesn't

Eviction is a bet. Your cache is full, a new item needs space, and someone has to go. The cache has no feelings about who. LRU says: evict whatever you touched longest ago. LFU says: evict whatever you've touched the fewest times. Both run in O(1). Both are wrong sometimes. They just fail differently, which is the kind of nuance that shows up as a 40% cache miss spike at 2am.

The interesting part is knowing when.

LRU vs LFU Cache Eviction: Two Different Bets

LRU (Least Recently Used) bets on time. LFU (Least Frequently Used) bets on count.

LRU assumes future accesses look like recent history. If you last touched item X four hours ago and item Y four seconds ago, LRU keeps Y. That is usually right. Temporal locality is real: most access patterns cluster in time, and what you needed a moment ago is likely what you need next.

LFU assumes popularity is the signal. If item X has been accessed 5,000 times and item Y just once, LFU keeps X. That is also often right, for a different class of workloads.

They agree on most evictions. The cases where they diverge are the ones worth understanding. They also agree that your cache being too small is your problem, not theirs.

LRU Is a Linked List That Keeps Score by Time

LRU stores items in a doubly linked list ordered by recency, with a hash map for O(1) lookup. The head is the most recently used item. The tail is the victim.

Every get moves the accessed node to the head. Every put inserts at the head and removes from the tail when the cache overflows.

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}           # key -> node
        self.head = Node(0, 0)    # dummy MRU sentinel
        self.tail = Node(0, 0)    # dummy LRU sentinel
        self.head.next = self.tail
        self.tail.prev = self.head

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        self._move_to_head(self.cache[key])
        return self.cache[key].val

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            node = self.cache[key]
            node.val = value
            self._move_to_head(node)
        else:
            node = Node(key, value)
            self.cache[key] = node
            self._add_to_head(node)
            if len(self.cache) > self.capacity:
                lru = self._remove_tail()
                del self.cache[lru.key]

The dummy head and tail sentinels eliminate every edge case. Every insert and remove is the same three-pointer swap regardless of how many items are in the list. No null checks, no length checks, no special paths for an empty list or a single element. No 2am debugging session either.

LRU linked list: HEAD is MRU, TAIL is the victim. Every get and put is O(1) pointer surgery.

O(1) get. O(1) put. O(capacity) space. Two data structures: one hash map and one doubly linked list. For a complete implementation with all helper methods, see LRU Cache implementation.

LFU Needs Three Data Structures to Do What LRU Does With Two

Yes, three. LFU needs more machinery, and it earns every piece of it.

1. key_map maps each key to its current value and frequency.
2. freq_map maps each frequency to an ordered collection of all keys at that frequency, preserving insertion order for LRU tiebreaking within a bucket.
3. min_freq tracks the lowest occupied frequency bucket.

When you access a key, you remove it from freq_map[f] and insert it into freq_map[f+1]. If freq_map[f] becomes empty and f was min_freq, you increment min_freq by one. On eviction, you pop the oldest entry (FIFO) from freq_map[min_freq].

from collections import defaultdict, OrderedDict

class LFUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.min_freq = 0
        self.key_map = {}                           # key -> [value, freq]
        self.freq_map = defaultdict(OrderedDict)    # freq -> {key: sentinel}

    def _promote(self, key: int) -> None:
        value, freq = self.key_map[key]
        del self.freq_map[freq][key]
        if not self.freq_map[freq] and freq == self.min_freq:
            self.min_freq += 1
        self.key_map[key] = [value, freq + 1]
        self.freq_map[freq + 1][key] = None

    def get(self, key: int) -> int:
        if key not in self.key_map:
            return -1
        self._promote(key)
        return self.key_map[key][0]

    def put(self, key: int, value: int) -> None:
        if self.capacity <= 0:
            return
        if key in self.key_map:
            self.key_map[key][0] = value
            self._promote(key)
        else:
            if len(self.key_map) >= self.capacity:
                evict_key, _ = self.freq_map[self.min_freq].popitem(last=False)
                del self.key_map[evict_key]
            self.key_map[key] = [value, 1]
            self.freq_map[1][key] = None
            self.min_freq = 1

min_freq can only increase on a promotion and always resets to 1 on a new insert. There is no scan, no search, no heap operation. Every get and put is a bounded number of hash map lookups and pointer operations, which is why this is O(1) and not the O(log n) you would get from a min-heap approach.

Each frequency level is an OrderedDict. Items promote upward on access. The eviction victim is always the oldest item in the lowest-frequency bucket.

O(1) get. O(1) put. O(capacity) space. Three data structures. For the full derivation of why this achieves O(1), see LFU Cache implementation.

The Access Pattern That Splits Them Apart

Consider a cache of capacity 3. We access item A ten times in a row. Maybe A is popular. Maybe there's a bug. The cache does not judge. Then we insert B, then C.

At this point, both caches hold the same three items. Frequencies: A=10, B=1, C=1. LRU ordering (most recent to least): C, B, A (A was last touched before B and C arrived).

Now insert D.

LRU evicts A. A sits at the tail because it has not been touched since B and C arrived.

LFU keeps A in the freq=10 bucket. A has seniority. A is not going anywhere. Instead, LFU evicts B, the oldest item in the freq=1 bucket.

LFU cannot evict an item with high accumulated frequency regardless of how much time has passed since its last access. LRU can and will, whenever newer items push it to the tail.

Same state, different bets. LRU loses A because time. LFU keeps A because frequency. Neither is wrong in general, only wrong for specific workloads.

This property is called scan resistance. When a bulk scan reads thousands of uncached items sequentially, each item gets accessed exactly once. In LRU, the scan bulldozes your hot items to the tail. In LFU, the scan items pile up at freq=1 and get evicted first. Your serving cache survives the whole thing.

Two Ways LFU Gets It Wrong

Old Counts Outlive Their Usefulness

A product listing accumulates 50,000 cache hits in January. By March it is discontinued. Its frequency counter is still 50,000 and has not been notified. A newly launched product starts at frequency 1. It gets evicted before it can load its first byte. The discontinued listing remains in cache, warm and smug, going nowhere.

LFU does not distinguish between popularity now and popularity three months ago. The raw count keeps growing and never falls unless you explicitly decay it.

The fix in Redis is a logarithmic counter that decays over a configurable interval (lfu-decay-time). The counter represents an approximation of log(access_count) rather than the raw count. Old hits fade. New traffic accumulates. The counter cannot grow without bound because the logarithm saturates around 10 million accesses at the default settings.

New Items Arrive at a Disadvantage

Every new item enters at frequency 1. If your cache is populated with items at frequency 2, every new item gets evicted immediately. A cache that has been running for a week is dominated by high-frequency incumbents. New content never gets a foothold even if it is now the most popular item in the system.

The modern solution is W-TinyLFU, introduced by Einziger, Friedman, and Manes in a 2015 ACM paper. W-TinyLFU routes all new items into a small LRU admission window first. A new item only competes for the main frequency-ranked region after it demonstrates enough recency. Caffeine, the Java caching library behind Gradle, Spring Boot, and Apache Solr, uses W-TinyLFU and achieves hit rates within 1% of Belady's optimal algorithm on real-world workloads. The frequency is tracked in a compact Count-Min Sketch, which uses a fixed number of bits per item rather than an exact counter.

Redis Approximates Both and Defaults to LRU

Redis has used approximate LRU since version 1.0. Redis 4.0 (2017) added approximate LFU. Neither tracks exact access state for every key. Exact tracking would cost too much memory. Redis knows what it is doing.

For LRU, Redis stores a 24-bit access timestamp per key and samples a pool of candidates on eviction, picking the one with the oldest timestamp. For LFU, Redis uses the same 24 bits differently: 8 bits for a decay clock, 16 bits for a logarithmic frequency counter. Same storage cost, different information.

Redis defaults to allkeys-lru. It has been the default since Redis 1.0. It has held up. The recommendation to switch to allkeys-lfu applies when you have a stable hot-key distribution: a small fraction of keys that receive most requests, like a product catalog where 5% of SKUs drive 80% of traffic. For workloads with uniform access or rapidly shifting popularity, allkeys-lru performs better.

The Hybrid: ARC Adapts Without Choosing

Megiddo and Modha at IBM introduced ARC (Adaptive Replacement Cache) at USENIX FAST 2003. ARC splits the cache into T1 for items seen exactly once and T2 for items seen at least twice. It keeps ghost lists of recently evicted keys to learn the workload in real time. The balance between T1 and T2 adjusts automatically based on which evictions turn out to be mistakes.

ARC is scan resistant and self-tuning. On a real storage workload at 16 MB cache, LRU achieves a 4.2% hit ratio while ARC achieves 23.8%. ZFS uses a variant of ARC as its buffer cache. IBM's DS8000 storage controllers ship ARC directly. The algorithm is patented by IBM, which is why it appears in ZFS and enterprise storage hardware but not in the average caching library despite being theoretically superior to both LRU and LFU for mixed workloads. Patents: ensuring better algorithms stay niche since 1790.

Pick LRU First. Switch When You Have Evidence.

Start with LRU unless your workload gives you a specific reason not to. A suspicion does not count. Neither does a blog post you read once (including this one). Actual cache miss data counts. LRU is simpler to implement, easier to debug, and the right default for temporally local access patterns that describe the majority of web and application caching use cases.

Reach for LFU, or an LFU variant with decay, when:

• You have a stable hot set. A small number of items consistently drive the majority of traffic and you cannot afford to lose them to scan events or recent-access patterns.
• Scan resistance matters. Batch jobs, analytics queries, or ETL pipelines read large chunks of data and should not evict your serving cache.
• You can configure frequency decay. Raw LFU without aging will accumulate stale popularity indefinitely. Use Redis lfu-decay-time, or use a library like Caffeine that handles decay and cold start transparently.

Prefer LRU when:

• Access patterns shift over time. Trending content, session data, feature flags, any workload where popularity changes on timescales shorter than the cache lifetime.
• New items need a fair chance. LRU naturally promotes recently inserted items, so new content competes on equal terms with older items from the moment it is inserted.
• You want the simpler mental model. A cache you can reason about clearly is easier to tune than a cache that is technically optimal but opaque.

The Short Version

• LRU evicts the item you touched longest ago. LFU evicts the item you have touched the fewest times over its lifetime.
• Both achieve O(1) get and put. LFU uses three data structures; LRU uses two. Same asymptotic complexity, larger constant for LFU.
• LRU is vulnerable to scan events: sequential access to uncached items pushes hot items to the eviction tail.
• LFU has two failure modes: stale popularity (old high-frequency items dominate) and cold start (new items die immediately). Both are addressed by frequency decay and admission windows.
• Redis supports both via approximate sampling. Default is LRU; switch to LFU for stable hot-key workloads.
• ARC (Megiddo and Modha, FAST 2003) adapts between the two strategies automatically without manual tuning. ZFS uses it.
• W-TinyLFU (Einziger, Friedman, Manes, ACM 2015) fixes LFU's cold start problem with an admission window and a compact frequency sketch. Caffeine uses it and approaches optimal hit rates on real workloads.

Cache eviction tradeoffs come up regularly as follow-up questions in DSA interviews, especially after implementing LRU or LFU from scratch. If you want to practice explaining these tradeoffs under time pressure with rubric-based feedback, SpaceComplexity runs voice-based mock interviews that cover exactly this kind of depth question.

Further Reading

• Cache replacement policies, Wikipedia
• Key eviction in Redis, Redis documentation
• LFU vs. LRU: How to choose the right cache eviction policy, Redis blog
• LRU Cache, LeetCode 146
• LFU Cache, LeetCode 460
• TinyLFU: A Highly Efficient Cache Admission Policy, ACM Transactions on Storage