# Robustifying Learning-Augmented Caching Efficiently without Compromising 1-Consistency

arXiv: https://arxiv.org/abs/2507.16242 · HTML: https://mlsanity.com/paper/2507.16242/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 57 references that are in the map.
- First posted on arXiv 22 Jul 2025.

## Builds on (most cited first, 26 of 26)

- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [The Case for Learned Index Structures](https://mlsanity.com/paper/1712.01208/) (2017)
- [Near-Optimal Bounds for Online Caching with Machine Learned Advice](https://mlsanity.com/paper/1910.12172/) (2019)
- [Improving Online Algorithms via ML Predictions](https://mlsanity.com/paper/2407.17712/) (2024)
- [Secretaries with Advice](https://mlsanity.com/paper/2011.06726/) (2020)
- [Better and Simpler Learning-Augmented Online Caching](https://mlsanity.com/paper/2005.13716/) (2020)
- [Learning Augmented Binary Search Trees](https://mlsanity.com/paper/2206.12110/) (2022)
- [Online Algorithms for Weighted Paging with Predictions](https://mlsanity.com/paper/2006.09509/) (2020)
- [An Imitation Learning Approach for Cache Replacement](https://mlsanity.com/paper/2006.16239/) (2020)
- [Learning-Augmented Dynamic Power Management with Multiple States via New Ski Rental Bounds](https://mlsanity.com/paper/2110.13116/) (2021)
- [Parsimonious Learning-Augmented Caching](https://mlsanity.com/paper/2202.04262/) (2022)
- [Learning-Augmented Weighted Paging](https://mlsanity.com/paper/2011.09076/) (2020)
- [Data-driven Competitive Algorithms for Online Knapsack and Set Cover](https://mlsanity.com/paper/2012.05361/) (2020)
- [A Universal Error Measure for Input Predictions Applied to Online Graph Problems](https://mlsanity.com/paper/2205.12850/) (2022)
- [Robust Learning-Augmented Caching: An Experimental Study](https://mlsanity.com/paper/2106.14693/) (2021)
- [Algorithms for Caching and MTS with reduced number of predictions](https://mlsanity.com/paper/2404.06280/) (2024)
- [Double Coverage with Machine-Learned Advice](https://mlsanity.com/paper/2103.01640/) (2021)
- [Paging with Succinct Predictions](https://mlsanity.com/paper/2210.02775/) (2022)
- [Learning-Augmented Query Policies for Minimum Spanning Tree with Uncertainty](https://mlsanity.com/paper/2206.15201/) (2022)
- [Learning-Augmented Algorithms for the Bahncard Problem](https://mlsanity.com/paper/2410.15257/) (2024)
- [Online Graph Coloring with Predictions](https://mlsanity.com/paper/2312.00601/) (2023)
- [The Secretary Problem with Predictions](https://mlsanity.com/paper/2306.08340/) (2023)
- [Learning-Based Algorithms for Graph Searching Problems](https://mlsanity.com/paper/2402.17736/) (2024)
- [Learning-Augmented Online TSP on Rings, Trees, Flowers and (almost) Everywhere Else](https://mlsanity.com/paper/2305.02169/) (2023)
- [A Learning-Based Caching Mechanism for Edge Content Delivery](https://mlsanity.com/paper/2402.02795/) (2024)
- [Online Minimum Spanning Trees with Weight Predictions](https://mlsanity.com/paper/2302.12029/) (2023)

## Built on by (most cited first, 3 of 3)

- [Toward Robust and Efficient ML-Based GPU Caching for Modern Inference](https://mlsanity.com/paper/2509.20979/) (2025)
- [When Classic Cache Policies Fail: Learning-Augmented Replacement for Semantic Retrieval Buffers](https://mlsanity.com/paper/2607.00394/) (2026)
- [Learning-Augmented Algorithms: Guarantees, Construction Mechanisms, and System-Level Implications](https://mlsanity.com/paper/2609.04787/) (2026)

## Abstract (arXiv)

The online caching problem aims to minimize cache misses when serving a sequence of requests under a limited cache size. While naive learning-augmented caching algorithms achieve ideal 1-consistency, they lack robustness guarantees. Existing robustification methods either sacrifice 1-consistency or introduce excessive computational overhead. In this paper, we introduce Guard, a lightweight robustification framework that enhances the robustness of a broad class of learning-augmented caching algorithms to 2Hk-1 + 2, while preserving their 1-consistency. Guard achieves the current best-known trade-off between consistency and robustness, with only O(1) additional per-request overhead, thereby maintaining the original time complexity of the base algorithm. Extensive experiments across multiple real-world datasets and prediction models validate the effectiveness of Guard in practice.