Least Recently Used (LRU)

LRU is built entirely on the temporal locality heuristic: if a piece of data was accessed recently, it has a high probability of being accessed again in the near future. This makes it highly effective for workloads with recency bias, such as user session data or sequential API calls. Unlike random eviction, LRU actively preserves the working set of hot data, maximizing the cache hit ratio for predictable access patterns. However, it performs poorly when confronted with sequential scans that load large, one-time-use datasets, as these scans flush the entire working set of frequently accessed items.

The canonical high-performance LRU implementation combines two data structures to achieve constant-time operations:

• Hash Map: Provides O(1) lookups by key to locate any cached entry instantly.
• Doubly Linked List: Maintains access order, with the most recently used item at the head and the least recently used at the tail. On every cache hit, the accessed node is detached and moved to the head of the list. On eviction, the tail node is removed. This dual-structure approach ensures that both reads and writes remain fast even as the cache grows, making it suitable for high-throughput inference caching layers.

LRU is susceptible to cache pollution, a scenario where low-value, one-time-access data displaces frequently used entries. This occurs during large sequential scans or bulk data loads where each new item is accessed once and never again. Because LRU tracks only recency, not frequency, these ephemeral items occupy the head of the list and push genuinely hot data toward eviction at the tail. In sovereign inference caching, this can manifest when a batch of unique, low-similarity queries floods the semantic cache, evicting high-value shared responses. Mitigations include LRU-K variants that track the timestamp of the K-th most recent access.

LRU and Least Frequently Used (LFU) represent two distinct eviction philosophies:

• LRU: Evicts based on recency of access. Ideal for workloads where recent items are most valuable, such as news feeds or session tokens.
• LFU: Evicts based on access count. Ideal for stable, long-lived reference data accessed repeatedly over time. LRU adapts quickly to shifting access patterns, while LFU suffers from cache pollution by history—old items with high historical counts resist eviction even after becoming irrelevant. Hybrid policies like ARC (Adaptive Replacement Cache) dynamically balance recency and frequency to capture the strengths of both.

In sovereign AI deployments, LRU serves as the default eviction policy for managing KV-Cache memory and semantic cache entries. When GPU memory is constrained, LRU evicts the KV-Cache tensors for the least recently processed prompt, freeing accelerator memory for new inference requests. For semantic caches storing embedded query-response pairs, LRU ensures that frequently asked questions remain instantly retrievable while stale, one-off queries are purged. The deterministic nature of LRU also simplifies cache telemetry and debugging in air-gapped environments where observability tooling may be limited.

Standard LRU can be refined into LRU-K, which tracks the timestamp of the K-th most recent access rather than the single most recent. This filters out one-hit-wonder items that pollute the cache. Common variants include:

• LRU-2: Evicts items based on their second-to-last access time, requiring at least two accesses to establish value.
• 2Q (Two Queue): Maintains separate FIFO and LRU queues, admitting items to the main LRU queue only after a second access.
• Clock (Second Chance): An approximate LRU using a circular buffer and reference bits, trading perfect accuracy for lower memory overhead. These variants are critical for sovereign caching layers where memory is a finite, expensive resource and every eviction decision impacts inference latency.