Least Frequently Used (LFU)

LFU's defining characteristic is its eviction decision, which is based solely on an item's access frequency count. When the cache is full, the algorithm identifies and removes the item with the smallest count. This contrasts with recency-based policies like Least Recently Used (LRU). The core assumption is that items accessed frequently in the past are likely to be accessed again in the future, making them more valuable to retain.

• Implementation: Typically requires a data structure (like a min-heap or a doubly linked list ordered by frequency) to efficiently track and find the minimum count.
• Example: In a cache storing API responses, an endpoint configuration fetched 100 times would be retained over a user avatar fetched only twice, regardless of when those fetches occurred.

A major drawback of a naive LFU implementation is the aging problem. An item that was intensely popular long ago accumulates a high frequency count and can 'pollute' the cache indefinitely, blocking newer, currently relevant items. This reduces cache adaptability.

Common solutions to introduce frequency decay include:

• Exponential Decay: Periodically reduce all frequency counts by a factor (e.g., halve them).
• Windowed LFU: Only count accesses within a recent time window.
• Adaptive LFU (LFU-Aging): Algorithms that dynamically adjust counts or incorporate a recency factor. This problem highlights the trade-off between pure frequency tracking and the need for temporal awareness.

Implementing an efficient LFU cache is more complex than LRU. It requires maintaining and updating two interrelated mappings:

1. Key-to-Node: A hash map from the cache key to a node containing the value and its current frequency.
2. Frequency-to-List: A hash map from frequency values to a doubly linked list of nodes that share that frequency (a 'frequency bucket').

O(1) Operations: A well-designed LFU using this structure can support get and put in constant O(1) time. The min-frequency is tracked separately. When eviction is needed, the head of the list at the min-frequency is removed. This structure efficiently handles promotions: a node is unlinked from its current frequency list and appended to the list for its new, incremented frequency.

LFU excels in specific, stable access patterns but can fail in others. Its performance is highly workload-dependent.

Ideal for:

• Looped Access Patterns: Where a small set of items is accessed repeatedly in a cycle.
• Static Popular Content: Caching for news headlines, top-selling products, or common configuration files where popularity changes slowly.

Poor for:

• Scanning/One-Time Accesses: A sequential scan of new data fills the cache with items of frequency=1, evicting potentially useful older items.
• Sudden Shifts in Popularity: A new 'viral' item must accumulate many accesses before it can displace an old, high-count item (exacerbated by the aging problem).

LFU is often contrasted with Least Recently Used (LRU), the most common alternative. Their fundamental difference is the metric of value: frequency vs. recency.

Hybrid policies like Adaptive Replacement Cache (ARC) attempt to get the best of both worlds by dynamically balancing between LRU and LFU lists.

In agentic memory and context management, LFU principles can be applied beyond simple key-value caches.

• Episodic Memory Pruning: An agent interacting with thousands of users might use an LFU-inspired policy to retain details (user preferences, past interactions) for the most frequently accessed user profiles, while pruning data for inactive users.
• Tool/API Call Caching: If an agent frequently calls a specific external API (e.g., for currency conversion), caching those results with an LFU policy ensures the most commonly needed results remain readily available, reducing latency and cost.
• Retrieved Context Chunk Management: When an agent's vector store retrieves many semantic chunks for a query, a short-term cache managed with LFU could keep the most frequently retrieved factual chunks across multiple reasoning steps, avoiding repeated expensive similarity searches.

Least Recently Used (LRU) is the canonical counterpart to LFU, prioritizing recency over frequency. It evicts the item that has not been accessed for the longest time. This is often implemented using a doubly linked list and a hash map for O(1) operations.

• Key Difference: LRU is highly sensitive to recent bursts of activity, which can protect newly loaded data. LFU, by contrast, can suffer from cache pollution if an item is accessed heavily in a short period and then never again, yet remains in cache due to its high historical count.
• Use Case: LRU excels in workloads with strong temporal locality, where recently used data is likely to be used again soon (e.g., browsing session data).

Adaptive Replacement Cache (ARC) is a sophisticated, self-tuning algorithm that dynamically balances between the LRU and LFU policies. It maintains four lists: two for recent entries (T1, T2) and two for frequent entries (B1, B2), which track evicted pages.

• Mechanism: ARC adapts the size of these lists based on the observed workload. If a workload shows strong recency, it favors the LRU-like lists. If it shows strong frequency, it grows the LFU-like lists.
• Advantage: It provides robust performance across diverse, changing access patterns without manual parameter tuning, making it suitable for general-purpose database and OS caches.

The Working Set Model is a foundational principle in operating system memory management that defines the set of memory pages a process actively needs during a specific time window (Δ). This concept directly informs eviction policy design.

• Relation to LFU: An optimal eviction policy aims to keep the working set resident in cache. LFU implicitly attempts to identify the working set by retaining frequently accessed items, assuming frequency correlates with active need.
• Engineering Implication: Monitoring the working set size is critical for capacity planning. If a cache is smaller than the working set, thrashing occurs, as items are constantly evicted and reloaded.

Time-To-Live (TTL) is a time-based expiration mechanism, often used in conjunction with access-based policies like LFU. It assigns a fixed or dynamic lifespan to a cached entry, after which the entry is invalidated regardless of its access count.

• Combined Use: LFU-TTL hybrids are common. An item might be evicted because its TTL expired (addressing staleness) or because its access frequency was the lowest (addressing capacity). This is crucial for caching dynamic data like API responses or real-time metrics.
• Implementation: TTL can be implemented via a priority queue keyed on expiration timestamps, scanned periodically or lazily on access.

A Write-Back Cache is a storage optimization where data modifications are written only to the cache initially. The updated data is written to the backing store (e.g., database, disk) only when the cache block is evicted. This creates a critical interaction with eviction policies like LFU.

• Eviction Trigger: The LFU eviction of a dirty (modified) block triggers a write I/O operation to persist the data. This makes eviction cost-aware; evicting a large, dirty, low-frequency item is more expensive than evicting a clean one.
• Risk: A system crash before the write-back occurs results in data loss. This is mitigated by mechanisms like Write-Ahead Logging (WAL).

Cache Invalidation is the process of marking cached data as stale or removing it entirely when the underlying source data changes. It is a correctness concern orthogonal to, but interacting with, capacity-driven eviction like LFU.

• Patterns: Invalidation can be push-based (the source notifies the cache on change) or pull-based (the cache uses TTL to periodically revalidate).
• Challenge with LFU: A frequently accessed (high-count) item in an LFU cache could become stale. Pure LFU will retain it due to its high frequency count, serving outdated data. Therefore, LFU implementations for mutable data must incorporate invalidation signals or TTL to ensure consistency.