Caching with Calibrated Predictions

Learning-augmented online algorithms use predictions to improve performance beyond worst-case guarantees while preserving robustness to prediction errors. In caching, existing approaches typically rely on signals such as next-arrival times or ranking scores, whose quality is measured through aggregate or worst-case error notions. These notions lack explicit probabilistic semantics, making it difficult to relate prediction quality directly to algorithmic performance.

We study online caching with calibrated probabilistic predictions. Every cached page receives a succinct phase prediction in [0, 1] representing the probability that it will not reappear in the next phase. Calibration ensures that these probabilities match empirical frequencies, providing a meaningful notion of predictor reliability. As a preliminary result, we give a threshold-based algorithm that labels a cached page as evictable whenever its phase prediction exceeds the closed-form threshold T * = 1/1 + H _k induced by the asymmetric paging loss. Our main result bounds the expected competitive ratio in terms of the optimal cost and the quality of the predictions, with an additive calibration term that vanishes as the predictor approaches perfect calibration.