leastfrequentlyused

Leastfrequentlyused (often referred to as Least Frequently Used or LFU) is a cache eviction policy that replaces the item with the smallest access frequency when space is needed. Each cached item has a frequency counter; on a hit the counter increments, and newly inserted items start at one. When the cache is full, the item with the lowest frequency is evicted to make room for a new one. LFU aims to keep data that is accessed more often resident, assuming past frequency predicts future usefulness.

Efficient LFU implementations avoid scanning all items at eviction time. Common approaches include bucketed frequency lists, priority queues, or hash maps pairing items with frequency counters. To prevent stale rankings and slow adaptation, aging or decay mechanisms reduce counters over time or periodically promote items to higher frequency buckets. Some systems combine LFU with recency (aging LFU or hybrid schemes) so recent accesses can recover from long periods of inactivity; tie-breaking for equal frequency may use recency, insertion time, or randomness.

LFU performs well under stable workload patterns where a small set of items remains popular. It can suffer from cache pollution when workloads shift, and cold-start problems where new items are disadvantaged. Compared with Least Recently Used (LRU), LFU emphasizes long-term popularity and may respond more slowly to sudden changes. LFU variants are used in database and file-system caches, memory managers, and web proxies, often as a baseline or in combination with recency to balance stability and adaptability.