Mixing cache policies reduces regret and cuts switching costs
No-Regret Mixing of LRU and LFU with Optimal Switching Cost
Machine LearningNetworking and Internet Architecture
Summary
Caches help computers store data for quicker access, using rules like LRU (least recently used) or LFU (least frequently used) to decide what to keep. The authors show that some recent methods mixing these rules can actually do worse than sticking to one. They propose a new way to combine LRU and LFU that guarantees performance nearly as good as the best single method, while also minimizing how often the cache switches between rules. This means better and more stable caching on any request sequence.
What this means in practice
- •For operating system developers: Improve cache management by adopting algorithms that mix LRU and LFU while minimizing performance losses from switching decisions.
- •For database administrators: Enhance database caching efficiency with strategies that dynamically balance recent and frequent data accesses with controlled switching.
Authors
Younes Ben Mazziane, Xinying Zou
Abstract
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 perform asymptotically as well as the better of LRU and LFU, i.e., whether they achieve sublinear regret with respect to this benchmark. We first show that LeCar suffers linear regret against an oblivious adversary, even with unbounded history. We then propose H-MC, a Hedge-based mixture of virtual LRU and LFU caches that preserves Hedge's selection probabilities, and hence its regret guarantees, while minimizing the switching cost among all joint selection rules with these marginals.