# Better and Simpler Learning-Augmented Online Caching

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

## Key facts

- Cited by 38 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 May 2020.

## Built on by (most cited first, 30 of 38)

- [Permutation Predictions for Non-Clairvoyant Scheduling](https://mlsanity.com/paper/2202.10199/) (2022)
- [Online Algorithms with Multiple Predictions](https://mlsanity.com/paper/2205.03921/) (2022)
- [Learning-Augmented Dynamic Power Management with Multiple States via New Ski Rental Bounds](https://mlsanity.com/paper/2110.13116/) (2021)
- [Triangle and Four Cycle Counting with Predictions in Graph Streams](https://mlsanity.com/paper/2203.09572/) (2022)
- [Parsimonious Learning-Augmented Caching](https://mlsanity.com/paper/2202.04262/) (2022)
- [A Novel Prediction Setup for Online Speed-Scaling](https://mlsanity.com/paper/2112.03082/) (2021)
- [Sorting with Predictions](https://mlsanity.com/paper/2311.00749/) (2023)
- [Mixing predictions for online metric algorithms](https://mlsanity.com/paper/2304.01781/) (2023)
- [Online bipartite matching with imperfect advice](https://mlsanity.com/paper/2405.09784/) (2024)
- [Robust Learning-Augmented Caching: An Experimental Study](https://mlsanity.com/paper/2106.14693/) (2021)
- [A Regression Approach to Learning-Augmented Online Algorithms](https://mlsanity.com/paper/2205.08717/) (2022)
- [Algorithms for Caching and MTS with reduced number of predictions](https://mlsanity.com/paper/2404.06280/) (2024)
- [(Optimal) Online Bipartite Matching with Degree Information](https://mlsanity.com/paper/2110.11439/) (2021)
- [Double Coverage with Machine-Learned Advice](https://mlsanity.com/paper/2103.01640/) (2021)
- [Paging with Succinct Predictions](https://mlsanity.com/paper/2210.02775/) (2022)
- [Improved Learning-augmented Algorithms for k-means and k-medians Clustering](https://mlsanity.com/paper/2210.17028/) (2022)
- [Active causal structure learning with advice](https://mlsanity.com/paper/2305.19588/) (2023)
- [Learning-Augmented Algorithms for Online TSP on the Line](https://mlsanity.com/paper/2206.00655/) (2022)
- [Learning-Augmented Algorithms with Explicit Predictors](https://mlsanity.com/paper/2403.07413/) (2024)
- [Learning-Augmented Algorithms for Online Steiner Tree](https://mlsanity.com/paper/2112.05353/) (2021)
- [Improved Bounds for Online Facility Location with Predictions](https://mlsanity.com/paper/2107.08277/) (2021)
- [Contextual Pandora's Box](https://mlsanity.com/paper/2205.13114/) (2022)
- [Online Dynamic Acknowledgement with Learned Predictions](https://mlsanity.com/paper/2305.18227/) (2023)
- [The Predicted-Updates Dynamic Model: Offline, Incremental, and Decremental to Fully Dynamic Transformations](https://mlsanity.com/paper/2307.08890/) (2023)
- [Robustifying Learning-Augmented Caching Efficiently without Compromising 1-Consistency](https://mlsanity.com/paper/2507.16242/) (2025)
- [Toward Robust and Efficient ML-Based GPU Caching for Modern Inference](https://mlsanity.com/paper/2509.20979/) (2025)
- [On Optimal Consistency-Robustness Trade-Off for Learning-Augmented Multi-Option Ski Rental](https://mlsanity.com/paper/2312.02547/) (2023)
- [Learning-Augmented Algorithms for MTS with Bandit Access to Multiple Predictors](https://mlsanity.com/paper/2506.05479/) (2025)
- [Learning-Augmented Online Bipartite Matching in the Random Arrival Order Model](https://mlsanity.com/paper/2511.23388/) (2025)
- [The Secretary Problem with Predictions and a Chosen Order](https://mlsanity.com/paper/2601.07482/) (2026)

## Abstract (arXiv)

Lykouris and Vassilvitskii (ICML 2018) introduce a model of online caching with machine-learned advice, where each page request additionally comes with a prediction of when that page will next be requested. In this model, a natural goal is to design algorithms that (1) perform well when the advice is accurate and (2) remain robust in the worst case a la traditional competitive analysis. Lykouris and Vassilvitskii give such an algorithm by adapting the Marker algorithm to the learning-augmented setting. In a recent work, Rohatgi (SODA 2020) improves on their result with an approach also inspired by randomized marking. We continue the study of this problem, but with a somewhat different approach: We consider combining the BlindOracle algorithm, which just na"ively follows the predictions, with an optimal competitive algorithm for online caching in a black-box manner. The resulting algorithm outperforms all existing approaches while being significantly simpler. Moreover, we show that combining BlindOracle with LRU is in fact optimal among deterministic algorithms for this problem.