# Learning-Augmented Weighted Paging

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Nov 2020.

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

- [Permutation Predictions for Non-Clairvoyant Scheduling](https://mlsanity.com/paper/2202.10199/) (2022)
- [Parsimonious Learning-Augmented Caching](https://mlsanity.com/paper/2202.04262/) (2022)
- [Discrete-Convex-Analysis-Based Framework for Warm-Starting Algorithms with Predictions](https://mlsanity.com/paper/2205.09961/) (2022)
- [Sorting with Predictions](https://mlsanity.com/paper/2311.00749/) (2023)
- [Mixing predictions for online metric algorithms](https://mlsanity.com/paper/2304.01781/) (2023)
- [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 Priority Queues](https://mlsanity.com/paper/2406.04793/) (2024)
- [Robustifying Learning-Augmented Caching Efficiently without Compromising 1-Consistency](https://mlsanity.com/paper/2507.16242/) (2025)
- [On Optimal Consistency-Robustness Trade-Off for Learning-Augmented Multi-Option Ski Rental](https://mlsanity.com/paper/2312.02547/) (2023)
- [Warm-starting Push-Relabel](https://mlsanity.com/paper/2405.18568/) (2024)
- [Learning-Augmented Online Minimization with Dual Predictions](https://mlsanity.com/paper/2606.05380/) (2026)
- [Online Algorithms with Unreliable Guidance](https://mlsanity.com/paper/2602.20706/) (2026)
- [Robust and Consistent Ski Rental with Distributional Advice](https://mlsanity.com/paper/2603.29233/) (2026)
- [Asymptotically Robust Learning-Augmented Algorithms for Preemptive FIFO Buffer Management](https://mlsanity.com/paper/2604.26349/) (2026)
- [The Secretary Problem with a Stochastic Precursor](https://mlsanity.com/paper/2605.22653/) (2026)
- [Online Packet Scheduling with Deadlines and Learning](https://mlsanity.com/paper/2606.00835/) (2026)

## Abstract (arXiv)

We consider a natural semi-online model for weighted paging, where at any time the algorithm is given predictions, possibly with errors, about the next arrival of each page. The model is inspired by Belady's classic optimal offline algorithm for unweighted paging, and extends the recently studied model for learning-augmented paging (Lykouris and Vassilvitskii, 2018) to the weighted setting. For the case of perfect predictions, we provide an ℓ-competitive deterministic and an O(log ℓ)-competitive randomized algorithm, where ℓ is the number of distinct weight classes. Both these bounds are tight, and imply an O(log W)- and O(log log W)-competitive ratio, respectively, when the page weights lie between 1 and W. Previously, it was not known how to use these predictions in the weighted setting and only bounds of k and O(log k) were known, where k is the cache size. Our results also generalize to the interleaved paging setting and to the case of imperfect predictions, with the competitive ratios degrading smoothly from O(ℓ) and O(log ℓ) to O(k) and O(log k), respectively, as the prediction error increases. Our results are based on several insights on structural properties of Belady's algorithm and the sequence of page arrival predictions, and novel potential functions that incorporate these predictions. For the case of unweighted paging, the results imply a very simple potential function based proof of the optimality of Belady's algorithm, which may be of independent interest.