Robustifying Learning-Augmented Caching Efficiently without Compromising 1-Consistency

The online caching problem aims to minimize cache misses when serving a sequence of requests under a limited cache size. While naive learning-augmented caching algorithms achieve ideal 1-consistency, they lack robustness guarantees. Existing robustification methods either sacrifice 1-consistency or introduce excessive computational overhead. In this paper, we introduce GUARD, a lightweight robustification framework that enhances the robustness of a broad class of learningaugmented caching algorithms to 2H k-1 + 2, while preserving their 1-consistency. GUARD achieves the current best-known trade-off between consistency and robustness, with only O(1) additional per-request overhead, thereby maintaining the original time complexity of the base algorithm. Extensive experiments across multiple real-world datasets and prediction models validate the effectiveness of GUARD in practice.

k i=1 1 i is the k-th harmonic number satisfying ln(k + 1) ≤ H k ≤ ln(k) + 1. Several algorithms have been developed to approach these bounds: MARKER [3] achieves a competitive ratio of 2H k -1, while EQUITABLE [4] matches the optimal H k , but at the cost of significantly higher time complexity O(k 2 ) per request, limiting its practicality.

Recent advances in machine learning have inspired a new paradigm: learning-augmented algorithms, which leverage predictive models to guide decision-making in online problems such as caching. These algorithms aim to improve performance when predictions are accurate while remaining robust