SYNTOLOGY HomeExplorerAtlasCodeMethodologyAboutDevelopersFeedPricing
Paper · 2106.14693 · ICML · 2021

Robust Learning-Augmented Caching: An Experimental Study

Konrad Żołna, Jakub Chłędowski, Adam Polak, Bartosz Szabucki

arXiv · PDF · Open in the Atlas

Code that ran

We have not lifted any functions out of this paper's repositories yet, so there is nothing we have run. The repositories linked to it are listed below.

Repositories linked to this paper

Some links come from the archived Papers with Code dataset (CC BY-SA 4.0): attribution and licence.

Abstract

Effective caching is crucial for the performance of modern-day computing systems. A key optimization problem arising in caching -which item to evict to make room for a new item -cannot be optimally solved without knowing the future. There are many classical approximation algorithms for this problem, but more recently researchers started to successfully apply machine learning to decide what to evict by discovering implicit input patterns and predicting the future. While machine learning typically does not provide any worst-case guarantees, the new field of learning-augmented algorithms proposes solutions that leverage classical online caching algorithms to make the machine-learned predictors robust. We are the first to comprehensively evaluate these learning-augmented algorithms on real-world caching datasets and state-of-theart machine-learned predictors. We show that a straightforward method -blindly following either a predictor or a classical robust algorithm, and switching whenever one becomes worse than the other -has only a low overhead over a wellperforming predictor, while competing with classical methods when the coupled predictor fails, thus providing a cheap worst-case insurance.

For agents

The same record, over MCP at https://syntology.ai/mcp:

get_harvested_code_for_paper("2106.14693")
get_code_for_paper("2106.14693")
have("2106.14693")

The run record, dated, one paper per request, free:

curl https://syntology.ai/api/ran/2106.14693.json

A badge for a README (the split and the date, never a ratio):

[![Syntology run record](https://syntology.ai/api/ran/2106.14693.svg)](https://syntology.ai/paper/2106.14693)

Connect an agent — have() is free.