SOURCE-LINKED INTELLIGENCE

No-Regret Mixing of LRU and LFU with Optimal Switching Cost

arXiv · AI, language, vision and robotics · article · Sep 7, 2026 · UTC

Caching systems often rely on simple eviction policies such as Least Recently Used (LRU) and Least Frequently Used (LFU), which perform well in complementary request regimes. Recent policies such as LeCar and Cacheus combine LRU and LFU using ideas from the experts problem in online learning. Specifically, upon a miss, they randomize between the two eviction rules using probabilities derived from scores updated by tracking the history of past evictions. While these policies exhibit strong empirical performance, it remains unclear whether they are guaranteed, on every request sequence, to perfo

Read original source ↗ Open in workspace

recordType

paper

region

Global