Ilmu Komputer & AI editorial
Open AccessOA2026
Learning-Augmented Heuristics: Simple, yet Smart, Robust and Interpretable Cache Eviction
A framework that learns cache-level parameters of static heuristics, demonstrated through S4-FIFO, achieving 26% mean efficiency improvement over S3-FIFO and 8% over 3L-Cache.
Haocheng Xia; William Nixon; Bintang Dwi Marthen; Pranav Bhandari; Juncheng Yang· 2026· DOI 10.48550/arXiv.2608.27975
The core problem
Caching is a cornerstone of system performance, with eviction algorithms determining which items to retain. Existing policies split into static heuristics (e.g., 2Q, S3-FIFO) and smart algorithms (e.g., ARC, LRB). Smart caches adapt to workloads but suffer from objective mismatches and instability. This paper introduces Learning-Augmented Heuristics (LAH), a framework that learns cache-level parameters of static heuristics. By decoupling 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. The authors demonstrate LAH through S4-FIFO, a Smart S3-FIFO cache eviction algorithm, pre-trained on 4,140 production traces and evaluated on 1,035 traces.
Innovation
On 1,035 evaluation traces, S4-FIFO improves mean efficiency by 26% compared to S3-FIFO and by 8% compared to 3L-Cache, the best state-of-the-art algorithm. Robustness is demonstrated: S4-FIFO increases miss ratio over FIFO by only 0.8% on the worst trace, whereas 3L-Cache increases FIFO's miss ratio by 8.8%. These results indicate that S4-FIFO achieves higher efficiency and robustness than existing smart caches. The efficiency metric can be expressed as:
or similar, but the paper likely uses a specific definition. The key numbers are: 26% improvement over S3-FIFO, 8% over 3L-Cache, and worst-case miss ratio increase of 0.8% over FIFO.
Caching is a cornerstone of system performance, with eviction algorithms determining which items to retain. Existing policies split into static heuristics (e.g., 2Q, S3-FIFO) and smart algorithms (e.g., ARC, LRB). Smart caches adapt to workloads but suffer from objective mismatches and instability. This paper introduces Learning-Augmented Heuristics (LAH), a framework that learns cache-level parameters of static heuristics. By decoupling 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. The authors demonstrate LAH through S4-FIFO, a Smart S3-FIFO cache eviction algorithm, pre-trained on 4,140 production traces and evaluated on 1,035 traces.
LAH operates by separating the data plane, which handles cache operations using a static heuristic with tunable parameters, from the control plane, which learns optimal parameters asynchronously. The control plane uses cache-level features (e.g., hit ratio, eviction patterns) to adjust parameters via a pre-trained model. S4-FIFO instantiates LAH with S3-FIFO as the base heuristic. A single model is pre-trained on 4,140 production traces and embedded in S4-FIFO to learn optimal cache parameters. The learning process is occasional and asynchronous, ensuring minimal overhead on the data plane. The framework supports interpretability: a language model can provide a rationale for why a particular configuration was chosen. The architecture can be represented as:
Why it matters
The decoupling of data and control planes allows LAH to combine the simplicity and speed of static heuristics with the adaptivity of smart caches. By learning only cache-level parameters, LAH avoids the instability and objective mismatches of existing smart caches. S4-FIFO's interpretability is a notable advantage: a language model can explain parameter choices, aiding debugging and trust. The pre-training on 4,140 traces and evaluation on 1,035 traces demonstrate generalizability. The robustness of S4-FIFO, with minimal worst-case degradation, suggests it is suitable for production environments where stability is critical. Future work may extend LAH to other heuristics and explore online learning scenarios. The framework's simplicity makes it attractive for deployment in systems where overhead must be minimal.
Who should read this
CS practitioners and researchers
Opening member content…