Towards Optimal Robustness in Learning-Augmented Paging

Peng Chen, Hailiang Zhao, Xueyan Tang, Yixuan Wang, Shuiguang Deng

Introduction: The Paging Problem and the Robustness Gap

Paging is a fundamental problem in computer systems design: given a small, fast cache and a massive pool of slower data, which existing page should be evicted when a new request causes a "miss"?

Classic online algorithms, such as Least Recently Used (LRU) or Marker, must make these eviction decisions without knowing future requests. Their performance is traditionally measured by a competitive ratio, which compares their miss rate to an all-knowing offline optimal algorithm (Belady’s rule). For randomized online algorithms, the theoretical gold standard is the $k$-th harmonic number, $H_k \approx \ln k$, where $k$ is the cache size.

Recently, "learning-augmented" algorithms have emerged to leverage machine learning (ML) models that predict future page requests. These algorithms strive for two properties:

  1. 1-consistency: Matching the offline optimal performance if the ML predictions are perfectly accurate.
  2. Robustness: Guaranteeing worst-case performance bounds (relative to a classic online algorithm) if the predictions are completely inaccurate.

The Gap: Prior state-of-the-art learning-augmented algorithms achieved a robustness bound of $2H_k + O(1)$. However, theoretical limits suggest it should be possible to hit the optimal $H_k$ bound. This paper successfully bridges that long-standing gap, achieving optimal robustness without sacrificing the benefits of accurate predictions.

The Core Innovation: Relative Prediction Budget (RPB)

To close the robustness gap, the authors introduce a novel conceptual framework called the Relative Prediction Budget (RPB).

Previous learning-augmented methods often relied on global performance metrics to decide whether to trust ML predictions, which could lead to either overusing or underutilizing the model. RPB, by contrast, acts as a fine-grained "bank account" for risk. The algorithm earns "budget" locally when its specific eviction decisions (or those of a baseline) suggest the predictions are reliable. It then "spends" this budget to follow ML predictions instead of relying on a safe, conservative baseline.

Methodology: Building on ONLINEMIN

The authors build their solution on two primary pillars:

  1. ONLINEMIN (OM): A classical, randomized $H_k$-competitive algorithm that uses "work functions" to track the "current optimal" solution based on the requests seen so far. The authors provide a new, simplified proof for OM’s competitiveness, which serves as the theoretical foundation for their design.
  2. The RPB-OM Framework: By integrating RPB with ONLINEMIN, the resulting algorithm follows ML predictions for evictions as long as it maintains a positive budget. If the budget runs out due to poor predictions, the algorithm seamlessly falls back to the robust priorities defined by ONLINEMIN.

Key Insights and Theoretical Guarantees

The paper introduces several critical insights that make this optimal bound possible:

  • The $L_0$ Miss Opportunity: The authors prove mathematically that to achieve 1-consistency, an algorithm must rely on predictions specifically when a requested page is entirely new to the current "support" of the work function (an $L_0$ miss). This is the point of highest uncertainty, making it the exact moment predictions are most valuable.
  • The "Gate-Pass" Logic: Using a potential function argument, the authors demonstrate that even if the algorithm deviates from the baseline and incurs a temporary cost, the accumulated "budget" and the structure of the work function ensure it can "pay back" that cost. This guarantees the $H_k + O(1)$ robustness bound.

Ultimately, RPB-OM stands as the first algorithm to achieve 1-consistency and $(H_k + O(1))$-robustness simultaneously.

Empirical Performance

Beyond theoretical proofs, the authors rigorously evaluated RPB-OM using real-world memory access traces (SPEC CPU 2006 benchmark), synthetic datasets with varying levels of log-normal noise, and real predictors (POPU and PLECO). They also tested scalability on BrightKite and CitiBike datasets with larger cache sizes ($k=1000$).

Key Results: * Superiority: RPB-OM consistently outperformed previous state-of-the-art algorithms, including LMARKER and BlindOracle&LRU. * Noise Tolerance: As prediction noise increases, "naive" ML-based approaches see their performance collapse. RPB-OM, however, degrades gracefully to the performance of the robust ONLINEMIN baseline. * Efficiency: The algorithm maintains an $O(\log k)$ computation time per request, ensuring it remains practical for real-world systems.

Limitations and Future Directions

While the paper achieves the optimal leading constant for robustness ($H_k$), there remains an additive constant $O(1)$ that depends on the initial budget ($\tau$). Additionally, while $O(\log k)$ time per request is efficient, it is still more computationally expensive than simpler heuristics like LRU, which operate in $O(1)$ time using a hash map and doubly linked list.

Future work may focus on further optimizing the work function updates to reduce computational overhead. Furthermore, the Relative Prediction Budget concept is highly versatile and could be adapted to solve other online optimization challenges, such as the Bahncard problem or online knapsack problems.

Summary updated

Abstract

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 $2H_k + O(1)$ in the randomized setting, leaving a gap to the optimal competitive ratio $H_k$. In this paper, we study how to close this gap. We begin by reviewing online optimality and proving a new property of the latest $H_k$-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: $H_k + O(1)$. Experiments further demonstrate strong practical performance.
BibTeX
@inproceedings{chen2026towards,
  author = {Peng Chen and Hailiang Zhao and Xueyan Tang and Yixuan Wang and Shuiguang Deng},
  title = {{Towards Optimal Robustness in Learning-Augmented Paging}},
  booktitle = {International Conference on Machine Learning},
  year = {2026},
  url = {https://openreview.net/forum?id=ESa07RwpVr},
}
Figure