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-consistency: Matching the offline optimal performance if the ML predictions are perfectly accurate.
- 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:
- 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.
- 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