LRU-K Algorithm

Cache eviction is the process of removing items from a cache to free up space for new entries. It is governed by specific policies that determine which item to remove.

• Primary Goal: Maximize cache utility by retaining the most valuable data.
• Triggered by: Cache reaching its capacity limit or an item expiring based on Time-To-Live (TTL).
• Policies: Range from simple (FIFO, Random) to complex (LRU, LFU, ARC, LRU-K). LRU-K is an advanced eviction policy designed to predict future access more accurately than standard LRU.

Least Recently Used (LRU) is a foundational cache eviction algorithm that removes the item that has not been accessed for the longest period when space is needed.

• Mechanism: Tracks only the timestamp of the most recent access for each cached item.
• Weakness: Vulnerable to one-time scans or large, non-repeating queries that can flush the entire cache of useful, frequently accessed items.
• Relation to LRU-K: LRU is a specific case of LRU-K where K=1. LRU-K generalizes this by tracking the last K accesses to better distinguish between infrequently accessed and truly cold items.

Adaptive Replacement Cache (ARC) is a self-tuning, patented eviction algorithm that dynamically balances between recency (like LRU) and frequency (like LFU) to optimize hit ratio under varying access patterns.

• Core Idea: Maintains two LRU lists: one for recently accessed items (T1) and one for frequently accessed items (T2). A ghost list tracks recently evicted items to adapt the size of T1 and T2.
• Comparison to LRU-K: Both are advanced policies. ARC adapts cache partition sizes between recency/frequency. LRU-K uses a deeper access history (K references) to make a more informed eviction decision on a per-item basis. ARC is often more complex to implement due to its adaptive ghost lists.

Cache hit ratio is the primary performance metric for any caching system, calculated as (Number of Cache Hits / Total Cache Requests) * 100%.

• Significance: Directly correlates to reduced latency, lower backend load, and improved system throughput. A high hit ratio indicates an effective caching strategy.
• Optimization Target: The sole purpose of advanced eviction policies like LRU-K is to maximize the cache hit ratio for a given cache size and workload.
• Measurement: Must be monitored continuously. LRU-K typically outperforms standard LRU on workloads with mixed access patterns, leading to a higher sustained hit ratio.

A deterministic cache stores the results of pure, side-effect-free functions where the same input arguments always produce the identical output.

• Key Property: Enables safe, correct caching because the cached value is guaranteed to be valid for its key indefinitely (or until the underlying function logic changes).
• Use Case: Ideal for caching agent-side computations, LLM inference on static prompts, or API calls to idempotent endpoints.
• Connection to LRU-K: LRU-K is an eviction policy, not a cache type. A deterministic cache can use LRU-K to manage its storage, evicting the least valuable deterministic results when the cache is full.

A cache admission policy is a rule that determines whether a newly fetched or computed data item should be inserted into the cache at all. It works in tandem with the eviction policy.

• Purpose: To prevent low-value or one-time-use items from polluting the cache and evicting more valuable data. Not all data deserves a cache entry.
• Common Policies: Always admit (standard), admit if future access is predicted (complex), or admit only if fetched on a second request (like in 2Q algorithm).
• LRU-K Context: LRU-K is primarily an eviction policy. Its historical data (K-access history) can, however, inform a sophisticated admission policy—for example, only admitting items after their K-th access, indicating they are entering a frequent-access phase.