Learning-Augmented Heuristics: A Different Way to Build Smart Caches - Harvard Systems Group

Cache eviction research has produced many &ldquo;smart&rdquo; eviction policies such as ARC, LeCaR, LRB, LHD, GL-Cache, and 3L-Cache. Many of these policies incorporate machine learning or online adaptation to respond to workload behavior, and can outperform traditional heuristics in miss ratio.<br>Yet despite their promise in efficiency, production caches still largely rely on static heuristics such as LRU, 2Q, and FIFO variants.<br>That gap is interesting. If smart caches can achieve better miss ratios, why<br>have they seen so little adoption?<br>In our OSDI &lsquo;26 paper, we explore a different way to incorporate machine learning into cache eviction. We call this design Learning-Augmented Heuristics (LAH): keep a simple heuristic on the request path, and use learning to configure that heuristic for a particular workload.<br>Why haven&rsquo;t smart caches taken over?<br>A cache eviction algorithm sits directly on the request path, so miss ratio is only one part of the design. A practical policy must also have low overhead, remain robust across workloads, be simple to implement, and behave predictably when performance degrades.<br>Adaptive eviction is attractive because workloads can have very different access patterns. A static policy applies the same rules to all workloads, while an adaptive policy can adjust its behavior to better match the workload.<br>The challenge is that many existing adaptive caches couple learning closely with eviction decisions. This can provide fine-grained adaptivity, but it also introduces additional computation and state on the critical path.<br>ML-based algorithms like LRB and 3L-Cache, for example, operate at the object level . A machine-learning model estimates reuse information for individual objects, and these predictions are used to make eviction decisions. This requires maintaining object-level features and performing model inference during eviction, increasing both metadata overhead and critical-path computation.<br>Object-level prediction can also make poor decisions harder to diagnose. When performance degrades, the model may indicate that one object is more likely to be reused than another, but it is difficult to relate these individual predictions to a clear property of the workload.<br>Other adaptive caches operate at a coarser cache level , where adaptation changes the behavior of the cache as a whole rather than predicting reuse for individual objects. For example, ARC adjusts the relative sizes of its queues, while LeCaR changes the weights assigned to different eviction policies. These decisions are easier to interpret because they correspond to global policy settings rather than per-object predictions.<br>However, cache-level adaptation can still happen very frequently, sometimes on every cache miss. This can be problematic because short-term cache behavior is noisy. In our measurements, miss ratio varies much more over short windows than over longer ones, so frequent updates may react to transient fluctuations rather than meaningful workload changes.<br>This creates a tradeoff. Learning provides adaptivity, but tightly coupling it with fine-grained eviction decisions can increase overhead, reduce stability, and make the policy harder to reason about.<br>Learning-Augmented Heuristics explores an alternative design in which learning operates at a slower timescale and configures the eviction heuristic rather than replacing it.<br>A useful way to look at the design space<br>We found it helpful to organize smart caches along two axes:<br>Learning granularity: does the algorithm reason about individual objects,<br>or about the cache as a whole?<br>Prediction frequency: does it adapt on every miss, or only periodically?<br>That gives a simple two-by-two view of the space:

Most prior work occupies three of these four regions. LAH focuses on the fourth: periodic, cache-level learning. At this granularity, the model can reason about aggregate workload behavior without participating in every eviction decision.<br>Learning-Augmented Heuristics<br>The core idea is to learn the configuration of a heuristic rather than replace the heuristic itself.<br>Simple cache policies are often more configurable than they first appear. FIFO- and LRU-based designs may expose queue sizes, admission rules, promotion thresholds, ghost-cache sizes, or other parameters. Different settings can make the same heuristic behave very differently across workloads. In practice, these parameters are often fixed or manually tuned.<br>This suggests a different role for learning: if the heuristic is already<br>expressive enough, let the model choose its parameters.<br>Start with a fast, deterministic cache algorithm with a small number of<br>meaningful knobs. Let the cache collect lightweight aggregate statistics about<br>the workload, then use a pre-trained model to choose a<br>configuration for those knobs asynchronously.

This naturally separates the system into a data plane and a...