Learning-Augmented Heuristics (LAH), a framework that learns the cache-level parameters of static heuristics, is introduced and demonstrated the effectiveness of LAH through S4-FIFO, a Smart S3-FIFO cache eviction algorithm.
Abstract
Caching is widely used across the system stack to improve performance and efficiency, with eviction algorithms at its core. Existing cache eviction policies fall into two broad categories: static heuristics (e.g., 2Q, S3-FIFO) and smart algorithms (e.g., ARC, LRB). Smart caches can adapt to workloads and have the potential to achieve higher efficiency and robustness than static heuristics. However, we find that existing smart caches suffer from objective mismatches and instability. We introduce Learning-Augmented Heuristics (LAH), a framework that learns the cache-level parameters of static heuristics. By decoupling the data and control planes, LAH supports simple, high-speed data reads and writes on the data plane, while performing occasional asynchronous learning on the control plane using cache-level features. We demonstrate the effectiveness of LAH through S4-FIFO, a Smart S3-FIFO cache eviction algorithm. We pre-train a single model on 4,140 production traces and embed it in S4-FIFO to learn optimal cache parameters. On 1,035 evaluation traces, S4-FIFO improves the mean efficiency by 26% compared to S3-FIFO and by 8% compared to 3L-Cache, the best state-of-the-art algorithm. S4-FIFO is also robust---increasing miss ratio over FIFO by 0.8% on the worst trace, whereas 3L-Cache increases FIFO's miss ratio by 8.8%. Finally, S4-FIFO's decisions are also interpretable: a language model can provide a rationale for why a particular configuration was chosen.
Caches reduce latency and network traffic, and cache performance largely depends on the eviction policy. Eviction effectiveness is typically measured by byte and object miss ratios. Although learning-based eviction policies can reduce misses, their high computational overhead limits practical deployment. This work pres...
Qian Wang, Chang Xu, Wenbin Zhou et al.· ACM Transactions on Computer...· 0 citations
CACHEFORGE is the first framework to evolve cache-replacement policies end-to-end by embedding a large language model inside a governed hardware-aware loop and enforces feasibility through reward shaping, structural checks, dynamic mutation, temperature scheduling, and cross-policy crossover.
Modern web applications demand sustained low latency under workloads that shift across users, devices, sessions, and network conditions. Classical cache replacement policies such as Least Recently Used (LRU) and Least Frequently Used (LFU) treat every cached object identically and ignore the cost-of-miss heterogeneity...
Akshatha Madapura Anantharamu· World Journal of Advanced En...· 0 citations
AvoKV-E is introduced, a training-free eviction policy that first delays eligibility for recent states and then ranks eligible entries using candidate-normalized read pressure, key redundancy, and value-payload potential, which shows that long-reasoning KV eviction should preserve not only keys that are likely to be re...
Han Yu, Wen-Hui Zhu, Xi-Wen Chen et al.· 0 citations
Online OS tuning can improve long-running services, but existing tuners are not well suited for live hosts. They treat scheduler, power, memory, and I/O controls as black-box variables and optimize a scalar reward. This approach ignores cross-knob policy structure, breaks down when application metrics are unavailable,...
Georgios Liargkovas, M. Joshi, Hubertus Franke et al.· Proceedings of the ACM SIGOP...· 0 citations