LRU Cache (Least Recently Used) is a cache eviction policy that removes the least recently accessed item when the cache reaches its capacity limit. It operates on the principle that items accessed recently are more likely to be accessed again soon — a property called temporal locality.

How LRU Works

• Access: When an item is read or written, it moves to the front (most recently used position).
• Eviction: When the cache is full and a new item needs to be inserted, the item at the back (least recently used) is evicted.
• Data Structure: Typically implemented using a doubly-linked list (for O(1) move operations) combined with a hash map (for O(1) lookups). This combination provides O(1) time for both get and put operations.

Comparison with Other Eviction Policies

• LRU: Evicts the least recently used item. Best for workloads with temporal locality.
• LFU (Least Frequently Used): Evicts the least frequently accessed item. Better when popular items should persist even if not recently accessed.
• FIFO (First In, First Out): Evicts the oldest item regardless of access patterns. Simplest but least adaptive.
• Random: Evicts a random item. Surprisingly effective and very simple to implement.
• ARC (Adaptive Replacement Cache): Self-tuning algorithm that balances between recency and frequency. Used by some databases and file systems.

LRU in AI/ML Systems

• KV Cache Management: In transformer inference, LRU-style eviction manages the key-value cache when it exceeds memory limits (e.g., H2O and StreamingLLM use attention-score-based variants).
• Model Caching: GPU-mounted model caching — when multiple models compete for GPU memory, evict the least recently used model.
• Embedding Cache: Cache computed embeddings with LRU eviction — frequently queried documents stay cached.
• Response Cache: Cache LLM responses with LRU eviction — popular queries remain cached while rare queries are evicted.

Python Implementation

Python provides functools.lru_cache as a built-in decorator for function-level LRU caching. For distributed systems, Redis supports LRU-style eviction natively.

LRU is the default choice for most caching scenarios due to its simplicity, O(1) performance, and effectiveness across a wide range of access patterns.