# Towards Optimal Robustness in Learning-Augmented Paging

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 38 references that are in the map.
- First posted on arXiv 31 May 2026.

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

- [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)
- [Online metric algorithms with untrusted predictions](https://mlsanity.com/paper/2003.02144/) (2020)
- [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)
- [A Model for Learned Bloom Filters, and Optimizing by Sandwiching](https://mlsanity.com/paper/1901.00902/) (2019)
- [Better and Simpler Learning-Augmented Online Caching](https://mlsanity.com/paper/2005.13716/) (2020)
- [Learning-Augmented Dynamic Power Management with Multiple States via New Ski Rental Bounds](https://mlsanity.com/paper/2110.13116/) (2021)
- [Data-driven Competitive Algorithms for Online Knapsack and Set Cover](https://mlsanity.com/paper/2012.05361/) (2020)
- [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)
- [Paging with Succinct Predictions](https://mlsanity.com/paper/2210.02775/) (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)
- [Near-Optimal Consistency-Robustness Trade-Offs for Learning-Augmented Online Knapsack Problems](https://mlsanity.com/paper/2406.18752/) (2024)
- [Learning-Based Algorithms for Graph Searching Problems](https://mlsanity.com/paper/2402.17736/) (2024)
- [Time Fairness in Online Knapsack Problems](https://mlsanity.com/paper/2305.13293/) (2023)
- [Learning-augmented smooth integer programs with PAC-learnable oracles](https://mlsanity.com/paper/2602.02505/) (2026)

## Abstract (arXiv)

Learning-augmented paging has been extensively studied in recent years. A key advantage over naive ML-based approaches is bounded robustness, which guarantees worst-case performance even when predictions are inaccurate, making these algorithms valuable for real-world systems. Prior work achieves robustness bounds of 2Hk + O(1) in the randomized setting, leaving a gap to the optimal competitive ratio Hk. In this paper, we study how to close this gap. We begin by reviewing online optimality and proving a new property of the latest Hk-competitive algorithm, which facilitates our analysis in the learning-augmented setting. Then, we review existing learning-augmented paging algorithms and introduce a unifying primitive, the relative prediction budget, which captures the essence of establishing robustness and reveals that prior algorithms either overuse or underutilize predictions. Guided by the above analysis, we develop a new framework that achieves the best-possible robustness up to an additive constant for learning-augmented paging: Hk + O(1). Experiments further demonstrate strong practical performance.