lru cache (least recently used)

**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.