提出轻量级框架Guard，让预测增强缓存算法既保高效又抗干扰。
Robustifying Learning-Augmented Caching Efficiently without Compromising 1-Consistency
- 引入Guard框架，通过简单机制提升算法鲁棒性。
- 实现2H_{k-1} + 2的鲁棒性上界，同时保持1-一致性。
- 每请求仅增O(1)开销，适合实际部署场景。
在线缓存问题旨在有限缓存大小下最小化服务请求序列时的缓存未命中次数。尽管朴素的预测增强缓存算法能实现理想的1-一致性，但缺乏鲁棒性保障。现有鲁棒化方法要么牺牲1-一致性，要么引入过高计算开销。本文提出Guard框架，可将一大类预测增强缓存算法的鲁棒性提升至2H_{k-1} + 2，同时保持其1-一致性。Guard仅带来O(1)的每请求额外开销，维持原算法的时间复杂度。在多个真实数据集与预测模型上的大量实验验证了Guard的实际有效性。
原文摘要 · Abstract (English)
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 learning-augmented 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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。