NeurIPS 2025 | 当系统算法遇上机器学习：GUARD开启学习增强缓存新范式

过去几年，机器学习在系统领域的“下沉”非常明显：它不再只做单纯的推荐、内容分类、搜索排序，还开始直接参与系统里的底层决策，例如基于 ML 模型的调度算法、缓存算法、负载均衡算法等。

同时，ML for Systems 相关 Workshops 也频繁出现于各大顶会（例如 NeurIPS '18-25, ISCA '20-25）。

然而，工程同学对此往往又爱又怕：

✅ ML 模型很准时，算法性能非常好（甚至接近最优解）
❌ ML 模型一旦不准，算法可能被“带沟里”（甚至导致系统崩溃）
🤔 有没有一种办法：既把 ML 模型当加速器，又给系统系上安全带？

围绕这类问题，Google 于 18 年提出了具备理论鲁棒性的学习增强缓存 [1]，并在近几年逐步形成了新兴的交叉方向：

Algorithms with Predictions（ALPS）[2] / Learning-Augmented Algorithms（学习增强算法）把“算法 + ML 预测”当成一个整体来设计和分析：预测准时尽量接近最优，预测不准时也要有可靠的最坏情况边界。

ALPS 致力于让“用 ML 模型增强系统”变得更可控、更敢用。这对工业界很关键：因为系统上线要面对的不仅是“某条性能曲线好看”，还是“敢不敢用、出了事兜不兜得住”。

论文标题：

Robustifying Learning-Augmented Caching Efficiently without Compromising 1-Consistency

论文链接：

https://arxiv.org/pdf/2507.16242

以缓存问题为例

缓存/换页（caching/paging）是经典到不能再经典的问题：

给你一个容量为 k 的缓存，在线地服务 page 请求，如果被请求 page 已在缓存中则命中（hit）；否则未命中（miss），需要从外部 load 该 page 进入缓存，此时若缓存空间已满则需要先剔除（evict）一个 page。

最优算法 Belady 于 1966 年提出，其总是剔除缓存中未来访问时间最远的 page。传统的启发式算法本质为利用过去信息对未来访问做“估计”，例如 LRU 利用 page 最近访问时间、LFU 利用 page 过去的访问频率等。

而学习增强缓存（learning-augmented caching）利用模型对未来进行预测，比如 page 的未来访问时间；于是我们有机会 “模仿” Belady 算法的行为：遵从预测，总是剔除预测的未来访问时间最远的 page。

然而，问题也正出在这：

一旦模型预测误差增大，其性能甚至会劣于 LRU。

本质上，我们想要这样一个算法：在预测误差小时接近最优解（一致性 consistency），在预测误差极大时与传统算法相当（鲁棒性 robustness），同时最好算法性能随着预测误差增大平滑降级（平滑性 smoothness）。

学习增强缓存

如今大部分使用 ML 模型增强缓存的工作未考虑算法鲁棒性，这也成为了其落地于实际工业场景的核心阻碍。

在学习增强算法领域，已有若干工作聚焦于“鲁棒化”学习增强缓存算法，然而现有的鲁棒化方法存在两个核心问题：

引入过高的时间复杂度（例如一些 switching 方法需要在线反复重算当前最优方案，难以落地。
损害一致性（consistency），导致算法过于保守，无法完全利用好误差较少的 ML 预测。

Guard 就是为了解决这个核心矛盾而来：

不损害一致性，强鲁棒性也保证，且每请求仅引入 O(1) 的额外计算开销。

Guard：给学习增强缓存算法装上“轻量安全带”

Guard 设计为一个算法鲁棒化框架，用于提升已有学习增强算法的鲁棒性，其核心思想：

在必要时介入算法流程，对某些缓存中的 page 进行 “保护”，防止其在一定时间内被剔除。

上图展示了 Guard 与某个基于 ML 预测的算法 A 结合后的流程，其分阶段执行，并仅在感知到预测误差时，执行鲁棒化操作。既保证了在预测准确时不干预原有算法 A（不损害一致性），又在预测不准时纠正原有算法 A（强鲁棒性保证）。

直觉上，我们可以把 GUARD 想象成一种“车道保持系统”：

原来的基于 ML 模型的算法 A 仍然负责正常驾驶（充分利用预测）
GUARD 只在检测到“开始偏离预定车道”的时候进行介入，把车拉回安全位置

同时，Guard 系列算法在理论上取得了 state-of-the-art 的 consistency 与 robustness，并展现出优越的 smoothness 与时间复杂度。

实验效果：真实数据集 + 多种预测器，表现“稳且强”

在合成噪声与真实预测器下，论文对 Guard 均做了性能评估，其中 cost ratio 代表算法 cache miss 次数与最优解 cache miss 次数的比值，cost ratio = 1 即代表性能最优。

1）合成噪声：从“预测很准”到“预测很烂”，曲线依旧稳

在 BrightKite 数据集上，通过在真实未来访问时间上加上噪声来模拟带误差的 ML 预测结果，GUARD&B.O.、GUARD&LRB 从实验上表现出与理论吻合的结果：

1-consistency（预测误差为 0 时与最优解一致）。
强鲁棒性（误差大时与 LRU 相当）。

2）真实 traces：SPEC CPU2006 Benchmark 上平均 cost ratio 最优

使用 PLECO / POPU 等真实预测器时，GUARD&B.O. 在平均 cost ratio 上优于多种强基线。
使用 LRB predictor 时，GUARD&LRB 同样给出最优平均 cost ratio。

此外我们推出了功能强大的缓存算法测试 Benchmark，支持多种启发式和现有几乎所有的学习增强算法，源码链接：https://github.com/OptiSys-ZJU/Cache-Coliseum

系统算法与机器学习的巧妙结合：未来展望

通过以上缓存这个例子我们可以看到利用 ML 模型增强系统算法的过程中有许多算法设计的空间。

事实上，不仅仅是以上这种离散算法设计，我们同样可以借鉴在线学习（online learning）的思路来设定对 ML 模型的信赖程度，从而鲁棒化系统算法。

Algorithms with Predictions（ALPS）、学习增强算法领域仍在蓬勃发展，它提供了一套把“收益”和“风险”一起量化的方法，让新一代基于模型的系统算法更可控、更有落地价值，也为 ML for Systems 领域提供了另一个全新的研究视角，欢迎感兴趣的朋友交流讨论（pgchen@zju.edu.cn）。

参考文献

[1] Thodoris Lykouris and Sergei Vassilvtiskii. Competitive caching with machine learned advice. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 3296–3305. PMLR, 10–15 Jul 2018.

[2] https://algorithms-with-predictions.github.io/

更多阅读