LRU vs LFU: Cache Eviction Policies Compared

LRU (Least Recently Used) and LFU (Least Frequently Used) are the two most common cache eviction policies, and they optimize for different things: LRU assumes whatever hasn’t been touched in a while is unlikely to be touched again soon, while LFU assumes whatever has historically been accessed rarely will keep being accessed rarely. They frequently agree on what to evict — but the cases where they disagree are exactly the cases that matter when choosing between them.

LRU: recency is the signal

An LRU cache evicts whichever item hasn’t been accessed for the longest time, regardless of how often it was accessed historically. Implementations typically combine a hash map for O(1) lookups with a doubly linked list that tracks access order — every read or write moves that item to the “most recently used” end of the list, and eviction simply removes from the opposite end.

LRU’s underlying assumption is temporal locality: data accessed recently is likely to be accessed again soon. This holds well for a lot of real workloads — a user’s current session data, the last few pages someone browsed, the working set of a database query — but it has a specific failure mode: a single burst of one-time-only accesses (a full table scan, a batch job scanning every record once) can flush an entire cache of genuinely hot items, replacing them with cold items that will never be touched again. This is sometimes called cache pollution from a scan.

LFU: frequency is the signal

LFU evicts whichever item has been accessed the fewest total times, keeping a counter per cached item that increments on every access. Because it tracks a running total rather than recency, LFU is naturally resistant to the scan-pollution problem that trips up LRU — a one-time burst of scan traffic doesn’t crowd out items with a long history of frequent access, since each scanned item’s counter only reaches one.

LFU’s failure mode runs the other direction: it has long memory, which becomes a liability when access patterns actually shift over time. An item that was extremely popular last month but hasn’t been touched since can sit in the cache indefinitely, protected by a high historical counter, crowding out genuinely current items that simply haven’t accumulated as many hits yet. This is usually addressed with some form of aging — periodically decaying counters, or windowing frequency counts to a recent time period — but that adds real implementation complexity that plain LRU doesn’t need.

Comparison table

	LRU	LFU
Eviction signal	Recency of last access	Total access frequency
Core data structure	Hash map + doubly linked list	Hash map + frequency buckets or a min-heap
Per-operation cost	O(1)	O(1) with bucketed frequency lists; O(log n) with a heap
Vulnerable to	One-time scans flushing hot data	Stale “was popular” items overstaying
Needs aging/decay to stay accurate	No	Usually, for shifting access patterns
Implementation complexity	Lower	Higher

Implementation complexity in practice

A textbook LRU cache is a well-known, compact implementation: a hash map from key to linked-list node, plus a doubly linked list ordered by recency, giving O(1) access, insertion, and eviction. LFU is structurally harder to keep at O(1): a naive implementation using a single counter and scanning for the minimum on eviction is O(n), and getting LFU down to true O(1) per operation requires an additional layer — typically a hash map from frequency count to a linked list of items sharing that count, so the eviction candidate is always at the head of the lowest-frequency bucket. That extra structure is more code to get right and more edge cases (an item’s frequency changing requires moving it between buckets) than LRU needs.

Where each one tends to win

LRU is the more common default, and for good reason: most real caching workloads — web sessions, recently viewed content, Redis-backed application caches — do exhibit real temporal locality, and LRU’s simplicity and predictable O(1) behavior make it the safer choice when you’re not certain which pattern your workload follows. It’s also the policy underlying Cache-Control-driven browser and CDN caching conceptually, even though those systems layer TTLs and validation on top rather than relying purely on eviction order.

LFU tends to win specifically when access patterns are stable and skewed — a small set of items that are reliably hot over long periods, with a long tail of items accessed rarely — and where scan-like traffic patterns are common enough that LRU’s vulnerability to them would be a real, recurring cost rather than a theoretical one. Content delivery for a fixed, popular library (a fixed catalog of media where popularity is stable over months) is a better fit for LFU than a workload with rapidly shifting hot items.

Beyond the two: hybrid policies

Because each policy’s weakness is the other’s strength, production caching systems frequently use hybrid approaches rather than pure LRU or pure LFU — approximating both recency and frequency at once, or using a small recency-based window in front of a frequency-based main cache to get scan resistance without full LFU’s bookkeeping cost. Understanding plain LRU and LFU first makes these hybrids easier to reason about, since they’re almost always describable as “LRU, but corrected for its scan weakness” or “LFU, but corrected for its staleness weakness” rather than a genuinely new third idea. The same hash table fundamentals underlie all of these — the eviction policy changes what gets tracked alongside each key, not the O(1) lookup that makes caching worthwhile in the first place. And regardless of eviction policy, the choice of a write-through, write-back, or write-around strategy for handling writes is an entirely separate, orthogonal decision layered on top.

The takeaway

LRU evicts based on how recently an item was used; LFU evicts based on how often it’s been used overall. LRU is simpler to implement correctly at O(1), handles shifting access patterns naturally, but is vulnerable to one-time scans flushing genuinely hot data. LFU resists scan pollution but needs explicit aging to avoid protecting items that used to be popular and no longer are, at the cost of a more involved implementation. When in doubt, LRU’s simplicity and broad applicability make it the reasonable default — reach for LFU specifically when your workload’s popularity distribution is stable and scan-like access patterns are a known, recurring problem.