Robustifying Learning-Augmented Caching Efficiently without Compromising 1-Consistency
Authors: Peng Chen
Hailiang Zhao
Jiaji Zhang
Xueyan Tang
Yixuan Wang
Shuiguang Deng
Venue: NeurIPS 2025 poster ()
Keywords: Learning-augmented Algorithms
Paging
Caching
Robustness
Consistency
Primary area: optimization
TL;DR: We propose a framework called Guard to enhance the robustness of a broad class of 1-consistent learning-augmented caching algorithms, while preserving 1-consistency and incurring low additional computational overhead.

Abstract: 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 $\mathcal{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.

Robustifying Learning-Augmented Caching Efficiently without Compromising Cetpromising-Consistttoennn I-Consistency
Peng Chen'
Hailiang Zhao! Jiaji Zhang' Xueyan Tang²
Yixuan Wang? Shuiguang Deng!*
'Zheiiang University NNayyang Technological University
Nanjjng University of Aeronautics and Astronautics
{pgchen, hliangzhao , edu. asxytangentu. edu. sg
vangyixuanOnuaa. edu, on
Abstract
The online caching problem aims to minimize cache misses when serving a se- quence of requests under limited cache size. While naive reaming-augmented caching algorithms achieve ideal 1-consistency, they lack robustness guarantees. Existing robustification methods either sacrifice 1-consistency introduce exces- sive computational overhead. In this paper, we introduce GUARD, a lightweight robustification framework that enhances the robustness augmented caching algorithms to 2H + 2, while preserving their 1-consistency. GUARD achieves the current best-known trade-off between consistency and ro- bustness, 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 practice.
broad class of learning-
Introduction
The classical caching (or paging) problem fundamental online optimization problem with widespread applications in operating systems, web caching, and database management. It involves serving sequence page requests using cache of limited size (1 < k: < oo). A request incurs zero cost if the corresponding page is already in the cache (cache hit); otherwise, a cache miss occurs, requiring the page be loaded into the cache, possibly evicting another page to make space. The objective is to minimize the total number of cache misses over the entire request sequence.
Caching has been extensively studied in both deterministic and randomized settings. In the offline setting where future requests are known, Belady []] proposed the first optimal strategy, Belady's 's rule, which evicts the page whose next request lies furthest the future. In the online setting. where future requests are unknown, strong theoretical lower bounds exist. Specifically, no deterministic algorithm can achieve a competitive ratio better than & [2], and no randomized algorithm can do better than Hy [3), where H₃ Σ is the k-th harmonic number satisfying In + 1) < H3 < In(k) 1. Several algorithms have been developed approach these bounds: MARKER [3] achieves a competitive ratio of 2H, 1, while EQUITABLE [4] matches the optimal HA, but at the cost of significantly higher time complexity ((k2) per request, limiting its practicality.
Recent advances machine learning have inspired new paradigm: Gearning-augmentte algorithms, which leverage predictive models to guide decision-making in online problems such caching. These algorithms aim to improve performance when predictions are accurate while remaining robust
Corresponning authors: hliangzhao8zzj.. edu. en, dengsgezju edu..
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

in the face of prediction errors. Their performance is typically evaluated using three key metrics: consistency, robustness, and smoothness. Consistency measures the competitive ratio under perfect predictions; Robustness bounds the algorithm performance under arbitrary prediction errors, and smoothness captures how the competitive ratio degrades as prediction errors increase.
This paper focuses on Gaaning-auugentt algorithm design for the classical caching problem, which lies at the intersection of machine learning and theoretical computer science. While the caching problem itself is fundamental and pervasive in computer systems, our work demonstrates the potential for safely integrating machine learning into cache systems.
1.1 Related Work
The first -aggenned caching algorithm is BLINDORACLE [5]. which blindly follows pre- dictions by evicting the page predicted be requested furthest in the future. While this yields ideal 1-consistency (a competitive ratio of I under perfect predictions), the algorithm lacks robustness: it can perform arbitrarily worse when predictions are inaccurate. This limitation has motivated a line of work on robustification methods, which can be broadly categorized into two families.
Embedding- based methods integrate prediction-driverr logic directly into classical caching algo- rithms like MARKER 3 For instance, PREDICTIVVM.RREES (5) modifies the original eviction policy of MARKER based predictions and achieves 4 robussssss but 1-consistency. Sub- sequently, LMARKER [6] improves smoothness and offers a (2H + 4)-robustness bound with 4-consistency. These algorithms derive their robustness from the marking mechanism inherent in MARKER, but this mechanism also restricts their ability to attain 1-consistency.
Switching- based methods switch between reamiin--augmente and classical algorithms based on past performance comparisons or the detection of prediction errors. For example, BLINDORACLE&LRR 77] switches between BLINDORACLE and LRU, following the currently better-performing one, and achieves 24-robustness and 2-consistency. More recently, F&R and F&R (FITF) [8] switch from non-robust aaugmete algorithm to robust upon detecting prediction errors, achieving (log -oobbuussssss and 1-consistency. However, both F&R and F&R (FITF) have a total computational overhead of (n log k), as they require recomputing the optimal solution over the entire observed request sequence upon each cache miss, with each recomputation costing On log k).
We provide further related work in Appendix A along with comprehensive comparison of existing algorithms in Appendix B Overall, while prior methods have made progress in improving robustness, they often do so at the cost of compromising 1-consistency or significantly increasing time complexity.
This leads to the central question of our work: Can we enhance the robustness of -aggeinned caching algorithms in time-efficient manner, without compromising 1-consistency?
1.2 Our Contributions
New Framework. We answer the above question affirmatively by introducing GUARD, a robus- tification framework applicable to any RB- RB-following algorithm, which we formally define in Sec. caching algorithms, including BLINDORACLE, Given an RB-following algorithm A, GUARD&A maintains the original asymptotic time complexity of while achieving the trade-off between consistency and robustness: (1, (1,2H + 2), which is state-of-the-art.
3.2, broad class of Shariing-uugmentn
P
GUARD introduces a novel, lightweight phase-based mechanism for detecting prediction errors. In contrast to switching- based methods, it avoids recomputing costly optimal solutions online and monitoring the performance of alternative algorithms.
New Algorithms and Empirical Evaluation. We apply GUARD to three representative RB-lollowing
algorithms, i.e., BLINDORACLE (5). LRB (9, and PARROT [10), each using different type of prediction. All resulting variants achieve 1 1-consistency and (2H + 2)-robustness, while maintaining their original asymptotic time complexities. Extensive experiments show that GUARD- based algorithms outperform existing methods and closely approach the state-of-the-arr across a broad range of benchmarks with both synthetic and real-world predictors. The combination of strong theoretical guarantees and low runtime overhead underscores their value in practical applications.
In this paper, focus on the algorithm's 's time complexity, excluding the cost of predictor calls.

---

2 Preliminaries
The caching problem involves a universe of pages P and a cache of size k. A sequence of page requests σ := 7 "..,"" I' must be processed online. Each request r; is pair Pt), where t; denotes the time which P: E P requested. Upon receiving a request r; the algorithm must determine whether the corresponding page P: resides in the cache. If it does, the request results in cache hit; otherwise, a cache miss occurs, and the page must be loaded into the cache. If the cache is full, an eviction decision must be made to accommodate the new page. The objective is to minimize the total number of cache misses over the entire sequence a.
An online algorithm makes eviction decisions without knowledge of future requests, whereas an offline algorithm has complete knowledge of the entire request sequence in advance. For any algorithm A, let (o) denote its cost when serving the sequence a, defined as the number of cache misses incurred. In the case of randomized algorithms, we consider the expected cost. The performance of online algorithms is typically evaluated using the competitive ratio. An algorithm A has competitive ratio a if for every request sequence o, the following holds:
A(o) S OPT(a) +
(1)
where (P)(a) denotes the cost of optimal offline algorithm, and is constant independent of the input. In our algorithms, the additive constant c will be zero. We also say that is a-competitive in this case. For brevity, we omit when it is clear from the context.
algorithms, the competitive ratio often takes the form min(7 + f(v), d). which encapsulates key performance metrics such as consistency, robustness, and smoothness. The parameter y reflects the performance when predictions are perfect (i.e., 1 = 0), making the algorithm y-consistent. The bound 5 ensures that the performance never degrades beyond this factor, no matter how inaccurate the predictions are, which defines 5-robustness. The function f()) characterizes how performance degrades with increasing total prediction error 77, reflecting the notion of (n)) smoothness when is constant.
For
3 Algorithm Optimality and 1-Consistency
To maintain 1-consistency during robustification, begin by analyzing structural properties of opti- mal offline eviction policies and identifying a broad class of 1-consistent online learning-augmented algorithms. Let OPT denote the optimal offline algorithm that follows Belady's rule: evicting the page whose next request occurs furthest in the future. For each request = (c). let T; denote the time of the next request for page p; after 4. Following Antoniadis al. and Song al. (9) define the Belady's 's binary label as follows:
{
1 if OPT evicts P; before Ti 0 otherwise.
y =
We refer to the page p; as I-page if = 1, and a O-page if y 0. Note that page may be I-page at some times and a O-page at others if it is loaded into the cache multiple times, depending on OPT's eviction decisions. By default, assume that OPT serves the entire request sequence
3.1 RB-Compliant Algorithms
Belady's 's binary labeling naturally gives rise to class of optimal algorithms that, although not necessarily replicating the exact eviction decisions of OPT, still achieve optimal performance.
This is achieved through adherence to principle we refer the relaxed Belady's rule: prioritizing the eviction of 1-pages over O-pages whenever a cache replacement is necessary.
Definition 3.1. An algorithm is said to be RB-compliant if it adheres to the relaxed Belady's 's rule.
To analyze the behavior of such algorithms, we define the following notation. Let the sets 1 and O denote the sets of cached 1-pages and O-pages, respectively, after algorithm A processes request ri. Similarly, let 1 and O denote the corresponding sets for OPT. The following lemma provides key structural property of RB-compliant algorithms: while their eviction decisions may differ from those of OPT, they maintain the same set of O-pages in the cache at all times.
3

---

Lemma 3.2. For an RB-compliant algorithm A, we have |1 = [1:| and 0 = 0 after serving each request Ti-
Proof. The proof carried out by exhaustive case analysis. See Appendix
C for details.
This result implies that an RB- RB-compliant algorithm always caches least one 1-page when cache miss occurs; otherwise, OPT would evict O-page at that time, contradicting the definition. Therefore, we have the following corollary:
Corollary 3.3. RB-compliant algorithms evict only 1-pages.
This ensures that RB-compliant algorithms match the performance of OPT exactly: Proposition 3.4. RB-compliant algorithms are optimal, incurring the same cost as OPT.
Proof. Lemma 3.2 implies that an RB-compliant algorithm A maintains the same set of O-pages as OPT at every step. Since O-pages are precisely those pages that will be accessed again before any 1-page needed, incurs least many cache hits as OPT, and thus no more cache misses. Therefore, A is optimal.
Proposition 3.5 reveals key property concerning the ordering of next request times.
Proposition 3.5. For RB-compliant algorithm A, after serving each request the next request time of any page in 1 later than that of any page O...
Proof. The proof follows from several observations about the relationship between the pages cached by A and OPT. See Appendix D for details.
3.2 RB-Following Algorithms
Building the theory from the previous section, we now define class of aanmentd algorithms based on the relaxed Belady's rule. This class captures a wide range of searning-augment algorithms that are 1-consistent.
Definition 3.6. A learning augmented algorithm is said to be RB-following if prioritizes evicting 1-pages over O-pages under perfect predictions.
By definition, an RB-following algorithm is RB-compliant when predictions are accurate. As result, all conclusions and performance guarantees derived for RB-compliant algorithms in Sec. 3.1 apply directly to RB-following algorithms under perfect predictions. Consequently, we have:
Corollary 3.7. RB-following algorithms are 1-consistent.
RB-following algorithms can leverage various types of predictions, including predicted next request times, Belady binary labels (as defined above), or even the optimal eviction choices made by OPT. Several representative learning augmented algorithms are RB- following:: BLINDORACLE [5] evicts the page with the furthest predicted next request time; LRB 19] randomly selects predicted 1-page for eviction, prioritizing them over predicted O-pages; PARROT [TO] mimics the eviction decisions of OPT by evicting the page predicted to be requested furthest in the future (FitF). See Sec. 4.4 for further discussion of these algorithms. However, all the aforementioned RBB-ollooiig algorithms follow predictions blindly, leading to a critical drawback: poor robusiness in the face of inaccurate predictions. Lemma 3.8 shows that such algorithms can incur unbounded competitive ratios.
Lemma 3.8. RB-following algorithms that blindly follow predictions have unbounded robustness.
Proof. The proof presents simple adversarial case. See Appendix for details.
This observation motivates a robustification framework that preserves the I-consistency of RB- following algorithmss while significantly enhancing their robustness.

---

4 GUARD: The Robustification
Framework
4.1 Insights and Overview
We now introduce GUARD, general framework that robustifies RB-following algorithms by mitigat- ing the impact of prediction errors while preserving their 1-consistency under accurate predictions. The design of GUARD is grounded in three key observations as follows.
Observation I: Immediate protection hurts 1-consistency. Marking-based learning-augmented caching algorithms, such as PREDICTIVEMARKE use a fixed mechanism to protect pages from eviction immediately after they are requested. While this method ensures bounded robustness, it may prevent necessary evictions that would otherwise be justified by accurate predictions. This observation motivates us to rethink the timing and conditions under which protection is applied, rather than applying it uniformly after every access. In particular, we aim to guard pages only when there is evidence of a prediction error, avoiding overprotection.
[5 LMARKER [6], and MARK& PREDICT [.]
Observation 2: Error detection must balance accuracy and efficiency. Many switching- based methods detect prediction errors at runtime to switch between prediction-driver and robust fallback policies. A common method, as used by BLINDOR ACLE& and BLINDORACLES M MARKER 77, involves comparing the current total cost incurred by the prediction-base algorithm with that of the fallback algorithm. However, this comparison is often insensitive: when the Gearning-uggmen algorithm underperforms relative to the classical onc, the accumulated prediction errors can be large, as the classical algorithm (e.g., LRU) may perform significantly worse than OPT. Consequently, this introduces a multiplicative factor of 2 in the robustness guarantees. Alternatively, some methods, such as F&R and F&R (FiTF) (8). detect prediction errors by explicitly recomputing the optimal solution over the observed request sequence up to the point of a cache miss, and checking whether the optimal solution would also incur a miss. While this yields highly accurate error detection, its overhead is prohibitive for real-time use. This motivates an error detection mechanism that is lightweight, sensitive errors that trigger cache misses, and practical for real systems.
Observation 3: RB-compliant algorithms follow an intrinsic eviction pattern. Any RB-compliant algorithm, including OPT, never retains unrequested page in the cache during the time interval between the eviction and the next request of another page, revealing the underlying principle of optimal eviction decisions. We defer the proof to Appendix G Formally, if a request r; results in a cache miss at time t;, and the requested page was previously evicted at time f < f4, then all pages remaining in the cache at time t; must have been requested at least once between μ and t, This behavior implies a kind of causal chain between evictions and requests, which motivates a way to identify mispredictions without recomputing OPT directly.
Inspired by the above, GUARD selectively guards (i.e., protects) a requested page ps from eviction only when prediction error is detected, thereby preserving I-consistency under accurate predictions. This mechanism ensures that pages that should be evicted before p; are indeed evicted within the same phase, maintaining bounded robustness even under poor predictions.
Algorithm I describes GUARD&A. A. Specifically, the execution of GUARD is divided into phases. At the start of each phase, all cached pages are labeled as old and stored in set M, which tracks unrequested old pages. A new phase begins when U/ becomes empty, indicating that all old pages have either been requested or evicted. The period from the beginning of execution until the first reset of (Line 8) is referred to as the 0-th phase. When a cache miss occurs, if the requested page P4 was previously evicted in the current phase (Line 10), this signals a potential prediction error. In response, GUARD evicts a random unguarded page from 2 and marks p; as guarded, preventing it from being evicted until the next phase. Otherwise, A's A's eviction policy is followed over the set of unguarded pages. This design leverages the intrinsic pattern of the optimal eviction behavior (Observation 3) to detect meaningful mispredictions efficiently without costly recomputation (Observation 2). while avoiding immediate protection (Observation 1) and insensitive performance comparisons (Observation 2).
We simplify by omitting its specific eviction behavior and other auxiliary logic in Algorithm 1 This is because, in essence, GUARD operates as a companion process to A, running concurrently, dynamically restricting the set of eviction candidates (Line 14- 15) or overriding 'ss eviction policy (Line 11) when necessary.
5

---

Algorithm GUARD&&
U 9 (the set tracks wrrequested old pages in the cache)
2: for i 1,,... n. do
3: Receive a page request r; (4.) at time
4: if p: is not in the cache then
5: if the cache is full then
6:
uf is empty then Unguard all cacked pages
7:
8:
U &- {all cached pages} (a new phase begins)
9:
end
10:
if pt evicted in the current phase then
11:
Evict a page x from U uniformly at random
12:
Guard p;
13:
else
14:
S fall unguarded cached pages}
15:
Follow A's policy to evict a page r from based on predictions
16:
end if
17:
the evicted page & E U then
18:
4 U(
19:
end end if
20:
21:
Load p. into the cache
22:
end if
23:
if p: 4 then
U1 t [p:)
25: end if
end for
4.2 Preserving 1-Consistency
Proposition 4.1. Under perfect predictions, no page will guarded by GUARD&A.
Proof. Suppose, for contradiction, that a page Pa is the first page ever guarded by GUARD&A, and guarded at time upon request for Pa. Before t,, pages have been guarded, GUARD& behaves exactly like up to this point. Consider the phase during which pa is guarded.
By the algorithm's 's logic, Pa must have been evicted earlier in this phase, say, at time μ < f. According to Corollary [33] Pa is 1-page time μ.. At time t,, since Pa was previously evicted, GUARD&& enters the error-handling branch (Lines 10-12), implying there exists an unrequested old page pa E l at time l, whose next request occurs at time T, >> 4. Then, ps was also a I-page cache at time according to Proposition 3.5
Now consider alternative algorithm, GUARD& B, behaves identically GUARD& A before 4, except that it evicts pa instead of at time μ. keeping in the cache until t.. Because both Pa and ps are 1-pages at time p. GUARD&B remains RB-compliant before t; under perfect predictions. At time t;. GUARD& B would experience a cache hit for Pa. whereas OPT incurs a cache miss (since was a I-page at time j and was not accessed again until f;). Moreover, GUARD&B B and OPT incur the same number of cache misses before f; (see Proposition 3.4). implying GUARD& B performs better than OPT after serving requests up to time t, which contradicts the optimality of OPT.
Therefore, no such Pa can exist, and no page is ever guarded under perfect predictions.
From Proposition 4.1 under perfect predictions, GUARD& A never guards any page and thus behaves identically to A. Since 1-consistent by definition, GUARD&A inherits the following property:
Corollary 4.2. For any RB-following algorithm A. GUARD&A is I-consistent.

---

4.3 Enhancing Robustness
Our preliminary proof shows the (log robuusttssss of GUARD& A. A more refined analysis (see Appendix D tightens this bound 2 2.
To establish the robustness bound, we introduce several key notations. Let the final phase executed by GUARD& be the Q-th phase and denote by 2 the set {0, ..., Q}. A page request r; is distinct within a phase if the requested page p; has not been previously requested during that phase. Let Cy denote the number of distinct new pages requested during the q-th phase.
Among the requests leading to evictions in the q-th phase, let ny denote the number of requests for new pages and 0g denote the number of requests for old pages. We decompose ny into ni representing the number of requests that cause the eviction new pages, and nild representing the nold number of requests that result in the eviction of old pages. Therefore, we have ng = m + " This notation allows precisely track the types of evictions occurring during each phase.
The following lemma gives lower bound on the cost of OPT on sequence a. Note that, in this paper, we denote OPT(a) by OPT for brevity.
Lemma 4.3.
Σ c S OPT S Σ 4E
old
QEQ 4
Proof. The proof builds phase-based analysis, following the approach of Fiat al. Appendix for details.
3 See
Lemma 4.4. For each q E Q. ny S 2c, and ni old S Cqp
Proof. Each distinct new page can be loaded into the cache at most twice per phase, as it becomes guarded upon second request. Hence, ng I 20g.
If a new page is loaded into the cache twice within phase, it must be evicted by request for another new page before its second request. This is because, if request for old page results cache miss, GUARD& A only evicts an old page from Ut Thus, we have n2 Co S n ne which implies
n old n2
n S Cq.
Theorem 4.5. GUARD& A is Ollog robustt
Proof. We bound the number of evictions. In phase let ny be the number of cache misses due to new pages, and Og those due old pages. From Lemma 4.4 ng S 20g. To upper bound 0g. we make the following assumptions, each of which can only increase the number of cache misses.
1. The number of distinct old-page requests (the maximum possible).
2. All ni old evictions happen before requests for old pages.
3. Evicted old pages have earlier next request times than remaining ones.
On each cache miss for an old-page request, an unrequested page from 2/ is evicted and the requested page guarded. Let p, denote the probability of a cache miss for the j-th subsequent distinct old page request. We have
1,
1 < j S old
n
Pj
if j > old.
(3)
7

---

The expected value of Og is bounded as follows:
E 10yl
S n
min (pz, 1}
jmnglt +1
R k-n
2ng +
1)
j ma +1
= =(2 + H Hk-now
H vogis old
$ (Hly + 1)...
(by Lemma
The inequalities hold regardless of whether q < Q or q misses incurred by GUARD&A A during the q-th phase. E[GA] is bounded by:
Q. Let GAg denote the number of cache
By 4. GUARD& A's total expected cost
E E|GA] co Σ
B[GA,] = c
Σ
(ng + E(og))
VEQ
1EQ
(H& + 3)
Σ
cq S (2H + OTPP. (by Lemmas 4.3 and 4.4
(5)
This completes the proof.
The above assumptions simplify the proof and immediately yield logarithmic robustness, but in- evitably loosen the result. Theorem preppent a tight bound.
Theorem 4.6. GUARD&A (2H+-1 + 2o-rob which tight.
Proof. The proof analyzes eviction chains that account for each eviction, without relying on any assumptions. See Appendix for details.
4.4 Applications
We apply GUARD to three RB-following algorithms: BLINDORACLE [5]. LRB 9. and PARROT [1O]. These algorithms are selected because they are representative and rely on predictors that are practical in implementation. However, as they blindly follow predictions. they are 1-consistent but not robust. After being robustified via GUARD, each algorithm gains (2H + ro-rouusts while retaining 1-consistency. Implementing GUARD incurs (11) overhead per request when using hash tables, so the time complexity remains asymptotically the same as that of the base algorithm.
BLINDORACLE evicts the page with the furthest predicted next request time (NRT), as detailed in Algorithm 3 in Appendix F LRB 9 is an algorithm that has been applied to content distribution network caching. See Algorithm 4 It predicts Belady's binary labels and prioritizes eviction of predicted 1-pages over predicted 0 pages, labeled by the OPT that starts from the current cache content of LRB and serves subsequent requests σ. Note that LRB remains RB-following, as proven in Appendix H PARROT [10] learns to imitate the optimal policy using a neural network model. See Algorithm for details. It directly evicts the predicted FitF (furthest-in-the future) page, where FitF follows the definition in Sadek and Elias [8). GUARD is also applicable to more sophisticated RB-following algorithms that do not blindly follow predictions, which we leave as future work.
Table Robustified RB-following algorithms. B.O. stands for BLINDORACLE, NRT refers to the next request time, while FitF stands for ieneess----thh-uuttue
Algorithm
Prediction
Consistency
Robustness
Smoothness
Time Complexity
GUARD&B.O O. GUARD&LRB
NRT
1
2H, +2
O(log(n/ (OPT))
On k) O(n)
Binary
2H,
O(Hs /PPTT)
GUARD&PARROT
FitF Page
2/1 +
O(Hs /
O(n)
8

---

Refer to Table 1 for a summary, and to Appendix K for their pseudo-codes, smoothness proofs. and implementation details. Th. The and My are enror measures for different types of predictions. representing the total & error of predicted next request times, the number of incorrect predictions of Belady's s binary labels, and the number of incorrect predictions of FitF pages, respectively. A comprehensive comparison of existing algorithms is provided in Table in Appendix
4.5 Achieving Better Smoothness with EXGUARD
we explore how to trade off smoothness against predictor usage. The challenge lies in maintaining logarithmic robustness while adjusting the use of predictions. We propose an extension of GUARD, called EXGUARD, which allows for improved smoothness the cost of increased predictor usage. EXGUARD constrains subsequent random evic- tions triggered by a misprediction-induued eviction, thereby avoiding excessive conservativeness and improving smoothness. Meanwhile, EXGUARD maintains 1-consistency and Ollog robbuussssss
Inspired by F&R 8 and ADAPTIVEQUERY--
The -uggmnnted algorithms in this paper invoke the predictor upon eviction, following com- mon implementations in prior caching systems 19]3 [4]. GUARD&B.. and GUARD& PARROT invoke the predictor (OPTT) times, whereas EXGUARD&B... O. and EXGUARD& PARDD&&ARRRRR PARROT use the predictor Odd OPT) times, where d E Ha]. EXGUARD&BLINDORE -smoothness, where À h//e S 1/c. Here, h Hz/(2d),
achieves
O( min() /Tt/ /PPT, n, and thus h E [1/2, Hx/2]. EXGUARD& PARROT achieves O(H ((Hz/d-nf/OPT)) (prr rithms using EXGUARD are also included in Table the Appendix for comparison. Appendix N present a comprehensive introduction to EXGUARD, including its empirical results and formal proofs of the favorable trade-offs it achieves.
Algo-
5 Experiments
We now present a comprehensive evaluation of performance under both synthetic and real-world predictions.
caching algorithms to assess their
5.1 Experimental Setup
Building on the experimental frameworks of Liu et al. [10 and Chiędowski et al. [15] we construct an expanded benchmark that includes more algorithm variants, datasets, and prediction types. We evaluate algorithms using three types of predictions: Next request times (NRT), Belady's ' binury labels, and FilF page predictions. We also include F&R (8) whose action predictions can derived from predicted next request times as demonstrated in Sadek and Elias (8) For switching-bare
algorithmss,
we follow Chiędowski et al. [15), setting a deterministic switching bound of 1 and a randomized weight 3 = 0.99. Some algorithms are omitted due to either performance equivalence or excessive computational overhead.
Datasets. We use BrightKite 16 and Citi [17], with cache sizes set to 10 and 100, respectively, following Lykouris and Vassilvtiskii [5) We further use SPEC CPU2006 memory traces [8] to evaluate real-world performance. Following Chiędowski et al. [5 and Liu et al. [0]] we adopt the 16-way 2MB cache configuration for consistency.
Predictions. We consider both synthetic and real predictors. For synthetic predictions, NRT and binary label predictions are processed differently. To simulate NRT predictions, we add log-normal noise to true request times. Pages without future requests are assigned a value of n + 1, where n the number of requests. On the other hand, binary label predictions are generated by flipping true Belady labels with given probability to simulate noisy prediction scenarios. For real-world predictors, we consider the following:
(i) PLECO 19:: A probability based predictor that estimates the access likelihood p of a page and predicts its next request after 1/p steps; (ii) POPU [20] A frequency-based predictor that assumes page requested in fraction p of past accesses will reappear after 1 1/p steps; (iii) LRB Predictor: Uses LightGBM [2]] to predict next request times, then classifies pages beyond the Belady boundary as predicted 1ppages and others as predicted O-pages, consistent with Song al. 99.

---

5.2
Experimental Results
All cost ratios are reported relative to OPT. Figures and shoow algorithm performance under varying levels of synthetic next request time (NRT) and binary prediction enrors on the BrightKite dataset. Below. we abbreviate BLINDORACLE (B.O.). LMARKER (LM.), LNONMARKER (LNoNM.), PREDICTIVEMARKEA (P.M.), and MARK& PREDICT (.).P.). Due to differing interpretations of binary labels, only synthetic results for &PP. are included. Both GUARD& B.O. O. and GUARD& exhibit empirical 1-consistency and bounded robustness, aligning with theoretical guarantees.
1.5
1.4
MARKII
1.8
B.O.
TIU
Cone Ratio
1.3
Cor
1.0
1.BB
P.M.
MARKO
1.2
B.O.AM.
1.4
B. B.O.AM..
1.1
F&R
122
0.4
0.6
Log aonmal noise parameter
Probubility of dipppnn the true binary information.
Figure 1: Performance with synthetic predic- tions of NRT on BrightKite.
Figure Performance with synthetic predic-
tions of binary labels on BrightKite.
Table 2: Average cost ratios on SPEC CPU2006 using PLECO and POPU predictors.
Predictor
LRU
B.O.
LM.
LNoNM.
P.M.
B.O.&M."
F&R
GUARD&B.O
PLECO
1.478
1.404
1.335
1,346
1.335
1.294
1.360
1.226
POPU
1,478
1.261
1.320
1.312
1.312
1.233
1.319
1.203
Table 3: Average cost ratios on SPEC CPU2006 Benchmark using LRB predictor.
Predictor
LRU
MARKER
LRB
MARKO
GUARD&LRB
LRB predictor
1.478
1.394
1.281
1.268
1.171
We further evaluate the algorithms on the SPEC CPU2006 benchmark using real-world predictors. Average cost ratios across all 13 datasets are shown in Tables 2 and 3 M... is omitted due inferior performance compared B.O.& M., Results show that both GUARD&B.O and GUARD& LRB achieve the lowest average cost ratios when using their respective predictors.
Additional results, including per-dataset performance and those using the "FitF page" predictor, presented in Appendix M We implement new benchmark, Cache-Coliseuni for comprehensive comparison of learning-augmeented algorithms (including ours), which is publicly available at https wttpttu..com/pttiysy////////ceee
//github. wtt.//om/mpp// ZJuttiiyyyyUUUccaa cache- coliseum
Conclusion
In this paper, we introduced GUARD, a framework designed to robustify learning-augmenter caching algorithms that follow the relaxed Belady's rule. GUARD preserves 1-consistency, improves robust- ness to 2 + 2, and incurs minimal additional computation, making it highly practical for real- world applications. Experiments across multiple datasets and predictors show that GUARD&B O., GUARD&LRB, and GUARD&PARRE achieve the best near-best performance. These results vali- date the effectiveness GUARD enhancing both theoretical guarantees and empirical performance.
Our results highlight the potential of lightweight robustification techniques for integrating machine learning to enhance existing caching systems. Future work may explore: (1) whether robustness and smoothness can be further improved toward their respective theoretical lower bounds, as discussed Appendix L while still preserving I-consistency and the asymptotic time complexity of the base algorithm: and (2) exploring robust Barning-augmentt arise in modern systems, as discussed in Appendix where, for example, the conventional constraint that "the requested item is always stored" is relaxed.
algorithms under other caching models that
10

---

Acknowledgments and Disclosure of Funding
This work was supported in part by the National Key Research and Development Program of China under Grant 2022YFB4500100 the National Science Foundation of China (62125206, 62502441), the Major Program of the National Natural Science Foundation of Zhejiang (LD25F020002), and the Singapore Ministry of Education under Academic Research Fund Tier 2 Award MOE-T2EP201 20222- 0007 and Tier Award RG23/23. Hailiang Zhao's 's work was supported in part by the Zhejiang University Education Foundation Qizhen Scholar Foundation.
References
[1] Laszlo A. Belady, A study of replacement algorithms for a virtual-storage computer. IBM Systems journal, (22:788101, 1966.
[2] Daniel D Sleator and Robert E Tarjan. Amortized efficiency of list update and paging rules. Communications of the ACM, 28(2):202-208, 1985.
[3] Amos Fiat, Richard M Karp, Michael Luby, Lyle A McGeoch, Daniel D Sleator, and Neal E Young. Competitive paging algorithms. Journal of Algorithms, 12(4):685-699, 1991.
[4] Dimitris Achlioptas, Marek Chrobak, and John Noga. Competitive analysis of randomized paging algorithms. Theoretical Computer Science, 234(1-2):203-218, 2000.
[5] Thodoris Lykouris and Sergei Vassilvtiskii. Competitive caching with machine learned ad- vice. 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. URL/ttts://pproceddnn mlr press/v80/ Lykourislaa. html
[6] Dhruv Rohatgi. Near-optimal bounds for online caching with machine learned advice. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1834-1845, SIAM, 2020.
[7] Alexander Wei. Better and Simpler Seaariing-Aumenntee Online Caching. In Jarosław Byrka and Raghu Meka, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDON, 2020), volume 176 of Leibniz International Proceedings in Informatics (LIPIcs). pages 10:1-60:10 17, Dagstuhl, Germany, 2020. Schloss Dagstuhl Leibniz-Zentrum für Informatik. ISBN 978-3-95977-164-11
doi: 10.4230/LIPIcss APPROX/RANDOM 202000000222006666 60. URL //rrpp/.drrpppo dagstuhl. de/ hts//nnitiee document./ 10. N0.4230/LIPIcss
http://LLIIcc..PPO//AAAAAAAA AAPRROX/RANDOOOO 2020.66 60
[8] Karim Ahmed Abdel Sadek and Marek Flias. Algorithms for caching and MTS with reduced number of predictions. In The Twelfth International Conference on Learning Representations, 2024.
net.
[9] Zhenyu Song, Daniel S Berger, Kai Li, Anees Shaikh, Wyatt Lloyd, Soudeh Ghorbani, Changhoon Kim, Aditya Akella, Arvind Krishnamurthy, Emmett Witchel, et al. Learning relaxed belady for content distribution network caching. In 17th USENIX Symposium on Networked Systems Design and Implementation (NSDI 20), pages 529-544, 2020.
[10] Evan Liu, Milad Hashemi, Kevin Swersky, Parthasarathy Ranganathan, and Junwhan Ahn. An imitation learning approach for cache replacement. In International Conference on Machine Learning, pages 6237-6247. PMLR, 2020.
[11] Antonios Antoniadis, Joan Boyar, Marek Eliás, Lene Monrad Favrholdt, Ruben Hoeksma, Kim Larsen, Adam Polak, and Bertrand Simon. Paging with succinet predictions. In International Conference on Machine Learning, pages 952-968. PMLR, 2023.
[12] Sungjin Im, Ravi Kumar, Aditya Petety, and Manish Purohit. Parsimonious aagminggauggenteed caching. In International Conference on Machine Learning, pages 9588-9601. PMLR, 2022.
11

---

[13] Xinyue Hu. Eman Ramadan, Wei Ye, Feng Tian, and Zhi-Li Zhang. Raven: belady-guides predictive (deep) learning for in in-memory and content caching. In Proceedings of the 18th International Conference emerging Networking EXperiments and Téchnologies, pages 72-90, 2022.
[14] Zhenyu Song, Kevin Chen, Nikhil Sarda, Deniz Aluubüken, Eugene Brevdo, Jimmy Coleman, Xiao Ju, Pawel Jurezyk, Richard Schooler, and Ramki Gummadi. (HALP}: Heuristic aided learned preference eviction policy for { YouTTub)) content delivery network. In 20th USENIX Symposium on Networked Systems Design and Implementation (NSDI 23), pages 1149-1163, 2023.
[15] Jakub Chledowski, Adam Polak, Bartosz Szabucki, and Konrad Tomasz Zoina. Robust learning- augmented caching: An experimental study. In Marina Meila and Tong Zhang, editors, Pro- ceedings of the 38th International Conference
Machine Learning, volume 139 of Pro- ceedings of Machine Learning Research, pages 1920-1930. PMLR, 18-24 Jul 2021. URL
https:/ https:///rroceeding.. mlr prwss/ wwwps//wssss1 v19./v139///// http399/hhlloowsi2221.1 html
[16] Eunjoon Cho, Seth A. Myers, and Jure Leskovec. Friendship and mobility: user movement in location-based social networks. In Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '11, page 1082-1090, New York, NY, USA, 2011 1. Association for Computing Machinery. ISBN 9781450308137, doi: 10.1145/202040. 2022555 UtL/tttee///aoo.rr///0/1//000000
[17] CitiBike, Citi bike system data. URL http://tgss/w...cttttlllyeecceep
[18]
CRC. The 2nd Cache Replacement Championship. 2017.,
2017, 2017. URL httpp://ccc22eeee
tamu. edu/
[19] Ashton Anderson, Ravi Kumar, Andrew Tomkins, and Sergei Vassilvitskii. The dynamics of repeat consumption. In Proceedings of the 23rd international conference on World wide web, pages 2014.
[20] Antonios Antoniadis, Christian Coester, Marek Eliáš, Adam Polak, and Bertrand Simon. Online metric algorithms with untrusted predictions. pages 345-355, 2020.
[21] Guolin Ke, Qi Meng. Thomas Finley, Taifeng Wang, Wei Chen, Weidong Ma, Qiwei Ye, and Tie- Yan Liu. Lightghm: a highly efficient gradient boosting decision tree. In Proceedings of the 3 Ist International Conference Neural Information Processing Systems, NIPS' 17, page 3149-3157, Red Hook, NY, USA, 2017. Curran Associates Inc. ISBN 9781510860964.
[22] Tim Kraska, Alex Beutel, Ed Chi, Jeffrey Dean, and Neoklis Polyzotis. The case for learned index structures. In Proceedings of the 2018 international conference on management of data, pages 489 409,504, 2018
[23] Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ml predictions. Advances in Neural Information Processing Systems, 31, 2018
[24] Antonios Antoniadis, Christian Coester, Marek Eliás, Adam Polak, and Bertrand Simon. Leaming-augmmntted dynamic power management with multiple states via new ski rental bounds, Advances in neural information processing systems, 34:16714-16726, 2021.
[25] Marina Drygala, Sai Ganesh Nagarajan, and Ola Svensson. Online algorithms with costly predictions. In International Conference on Artificial Intelligence and Statisties, pages 8078- 8101. PMLR, 2023.
[26] Hailiang Zhao, Xueyan Tang, Peng Chen, and Shuiguang Deng. Learning-augmented algorithms for the bahneard problem. arXiv preprint arXiv:2410.15257 2024.
[27] Sungjin Im, Ravi Kumar, Mahshid Montazer Qaem, and Manish Purohit. Online knapsack with frequency predictions. Advances in neural information processing systems, 34:2733-2743, 2021.
12

---

[28] Ali Zeynali, Bo Sun, Mohammad Hajiesmaili, and Adam Wierman. Data-driven competitive algorithms for online knapsack and set cover. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 10833-10841, 2021.
[29] Giulia Bernardini, Alexander Lindermayr, Alberto Marchetti-Spaccamnt Nicole Megow. Leen Stougie, and Michelle Sweering. A universal error measure for input predictions applied to online graph problems. Advances Neural Information Processing Systems, 35:3178-311 2022.
[30] Evripidis Bampis, Bruno Escoffier, Themis Gouleakis, Niklas Hahn, Kostas Lakis, Golnoosh Shahkarami, and Michalis Xefteris. Saamingg-augmettd online tsp rings, trees, flowers and (almost) everywhere else. arXiv preprint arXiv:2305.02 2023.
[31] Alexander Lindermayr, Nicole Megow, and Bertrand Simon. Double coverage with machine- learned advice. arXiv preprint arXiv:2103. 03,01640, 2021.
[32] Nicolas Christianson, Junxuan Shen, and Adam Wierman. Optimal robustness-consistee tradeoffs for learning- augmented metrical task systems. In International Conference on Artificial Intelligence and Statistics, pages 9377-9399. PMLR, 2023.
[33] Paul Dütting, Silvio Lattanzi, Renato Paes Leme, and Sergei Vassilvitskii. Secretaries with advice. In Proceedings of the 22nd ACM Conference on Economics and Computation, pages 409 429, 2021.
[34] Kaito Fujii and Yuichi Yoshida. The secretary problem with predictions. Mathematics of Operations Research, 19(2):1241-126) 2024.
[35] Antonios Antoniadis, Hajo Broersma, and Yang Meng. Online graph coloring with predictions. In International Symposium on Combinatorial Optimizationn, pages 289-302. Springer, 2024.
[36] Adela F DePavia, Erasmo Tani, and Ali Vakilian. Learning- algorithms for graph searching problems. International Conference on Artificial Intelligence and Statistics, pages 928-938- PMLR, 2024.
[37] Honghao Lin, Tian Luo, and David Woodruff. Learning augmented binary search trees. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 13431-13440, PMLR, 17-23 Jul 2022. mlr. press/v162/lin222 URL https:://pocceeeeee httppoeddddass......rress/////aa
html
[38] Thomas Erlebach, Murilo Santos de Lima, Nicole Megow, and Jens Schlöter. Learning- augmented query policies for minimum spanning tree with uncertainty. arXiv preprint arXiv:2206. 15201, 2022.
[39] Magnus Berg, Joan Boyar, Lene Favrholdt, and Kim S Larsen. Online minimum spanning trees with weight predictions. In Algorithms and Data Structures Symposium, pages 136-148. Springer, 2023.
[40] Hoda Torabi, Hamzeh Khazaei, and Marin Litoiu. A learning-based caching mechanism for edge content delivery. Proceedings of the 15th ACM/SPEC International Conference on Performance Engineering, pages 236-246, 2024.
[41] Akanksha Jain and Calvin Lin. Back to the future: Leveraging belady's algorithm for improved cache replacement. ACM SIGARCH Computer Architecture News, 44(3):78-89) 2016.
[42] Zhan Shi, Xiangru Huang, Akanksha Jain, and Calvin Lin. Applying deep learning to the cache replacement problem. In Proceedings of the 52nd Annual IEEE/ACM International Symposium on Microarchitecture, pages 413-425, 2019.
[43] Avrim Blum and Carl Burch. On-line learning and the metrical task system problem. In Proceedings of the tenth annual conference on Computational learning theory, pages 45-53, 1997.
13

---

[44] Lyle A McGeoch and Daniel D Sleator. A strongly competitive randomized paging algorithm. Algorithmica, 6(1):816 825, 1991.
[45] Gerth Stølting Brodal, Gabriel Moruz, and Andrei Negoescu. Onlinemin: fast strongly competitive randomized paging algorithm. Theory of Computing Systems, 56:22-40, 2015.
[46] Stéphane Ross, Geoffrey Gordon, and Drew Bagnell. A reduction of imitation learning and structured prediction to no-regret online learning. In Proceedings of the fourteenth interna- tional conference artificial intelligence and statistics, pages 627-635. JMLR Workshop and Conference Proceedings, 2011.
[47] Nikhil Bansal, Niv Buchbinder, and Joseph Naor. A primal-dual randomized algorithm for weighted paging. Journal of the ACM (JACM). 59(4):1224 2012.
[48] Zhihao Jiang, Debmalya Panigrahi, and Kevin Sun. Online algorithms weighted paging with predictions. ACM Transactions on Algorithms (TALG), 18(4):1-27, 2022.
[49] Nikhil Bansal, Christian Coester, Ravi Kumar, Manish Purohit, and Erik Vec. Learning- augmented weighted paging. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 67-89. SIAM, 2022.
[50] Thomas Anderson and Mike Dahlin. Operating Systems: Principles and Practice, Volume 3: Memory Management. Recursive Books, n.d. Available at lhttp::/// htapp:://wwwww/// kea. nu/files/
Settbooks//aapposppp33
[51] Jim Gray and Andreas Reuter. Transaction processin:: concepts and techniques. Elsevier, 1992.
[52] Gil Einziger, Roy Friedman, and Ben Manes. Tinylfu: A highly efficient cache admission policy, ACM Transactions on Storage (ToS), 13(4):1-31, 2017.
[53] Qilin Fan, Xiuhua Li, Jian Li, Qiang He, Kai Wang, and Junhao Wen. Pa-cache: Evolving learning-basse based popularity- aware content caching in edge networks. IEEE Transactions Network and Service Management, 18(2):1746-1757 2021.
14

---

Appendix
A Further Related Work
Learning-Augmenter Algorithms. The concept of beaning-auugmenter algorithms was pioneered by Lykouris and Vassilvtiskii [5]. who introduced the idea of integrating machine-learned predictions
into online decision- makkiinn-making frameworks. Since then, this paradigm has gained traction across
wide range of algorithmic domains, including index structures [22], ski rental problems [23 (24),
the Bahncard problem [25 26), online knapsack [27 28). online TSP (29 30], k-server problems
3IJ metrical task systems (MTS) 200 [3]], secretary problems 33 34 graph-related tasks 33 36
and data structures 37 39] These techniques have also found applications in broader system-level
contexts such as networking
40 and caching 42).
Bearning-Augmentee Caching. Recently, there has been growing interest in applying learning- augmented methods to the caching problem. The first robust -ugmenge eaching algorithm, PREDICTIVEMARKER was proposed by Lykouris and Vassilvtiskii [5]. It achieves a competitive ratio of min + 4n,, /PT + 1, 44Hx where OPT is the optimal offline cost and 7/2 represents the li-rrror of the prediction on next request times. This bound was later improved by Rohatgi (6], who introduced LMARKER, achieving smoothness guarantee of (log(() (OP)). The same work also proposed LNONMARKER, which offers superior smoothness but sacrifices bounded robustness. Wei 77) further improved the competitive ratio by proposing simple approach to combine BLINDORACLE with LRU, and proved its competitive ratio to be 2 min + 2n/ OPT, 4 + 4/(k 1) Th /OP, k). Wei 77 also combined BLINDORACLE with the randomized algorithm EQUITABLE, and proved that its competitive ratio is (1 + 7) min + 2n/ PPP/PTT 4 4+ 4/(k - 1) /PPOT, Hx), plus an additive constant (kk/r), where 7 (0, 1/4) is trade-off parameter.
Antoniadis et al. (20 studied the succinctness of the prediction. They show that it suffices to receive predictions of size Olog k) per request, indicating which page should be evicted. This was further simplified by Antoniadis et al. [T], who demonstrated that binary predictions indicating whether cached page is expected to be evicted can still yield strong performance. This practical insight inspired our exploration of caching with binary predictions and led to the development of the GUARD framework based on this minimalistic form of side information.
Im et [2] and Sadek and Elias [ approached the problem differently, focusing on limiting the number of times predictions are used. Their work highlights the trade-off between the frequency of prediction queries and overall algorithmic performance, which is a consideration of particular relevance in settings where acquiring predictions is costly or resource-intensive.
B Comparative Analysis of Existing Algorithms
Table 4 provides a comprehensive comparison of recent focusing on their performance guarantees and prediction requirements. Below, we analyze key algorithmic paradigms and design principles that distinguish these approaches.
caching algorithms,
Prediction Types. The literature explores various forms of predictions, each offering different levels of information and utility.
1. Next Request Time Prediction. The most commonly used prediction type is the next request time of a page, which is utilized by many existing algorithmss, including BLINDORACLE (5).
PREDICTIVEMARKER (5), LMARKER (6), and LNONMARKER (6)
2. Binary Prediction. Binary predictions convey specific binary information and have been explored both in systems 42] and theoretical studies M.. For example. MARKO predicts Belady's 's binary labels guide eviction decisions. MARK & PREDICT predicts whether page will be requested during given phase, rather than estimating the exact request time.
3. FilF seertheei-ii-thh---ieeee identifies the cached page that will be requested furthest in the future. used by F& R (FitF) [8]. and PARROT 19.
Puge Prediction. Given the cache content, the predictor directly
15

---

Table 4: Comparison of Learning-Augmented Caching Algorithms. Prediction type egorizes the algorithms listed in the first column, including NRT (Next Request Time), Bi- nary information (e.g., Belady's binary label or whether page will be accessed in the cur- rent phase), FitF (Furthest-in-the-Fuurr page to be requested), and Action (e.g., cache content of an optimal offline algorithm). Abbreviations include PREDICTIVEMAREES (P.M.), LNON- MARKER (LNoNM.), LMARKER (L.M.,, BLINDORACLE (B.O.), EQUITABLE (EQ-), BLINDORA- CLE&MARKER (B. B.O.&&M. &M.,, MARK& PREDICT (M.&P.), and PARROT (PA.). The superscripts D and R denote deterministic switching and randomized switching. respectively. For B.O.&M." and B.O.&EQ. 7 E (0, 1) is tunable trade-off parameter. Time. refers to the time complexity of the algorithm, excluding the cost of making predictor calls. n is the total number of page requests. The log & in the time complexity of algorithms using NRT predictions comes from selecting the page with the furthest next request time. Cons. denotes consistency (i.e., the competitive ratio when predictions are perfect). Coefficients and constants presented robustness are mostly obtained directly from the conclusions of the respective papers, while those for F&R and F&R (FITF) are derived from inequalities and may not be tight. Error measures 7/s Tho las and f7 use different units across differ- ent prediction types, so their magnitudes are not directly comparable. For EXGUARD, d E [1, Hg]- For EXGUARD& B. O.,, À h/c² < 1/e, where H (2d), and thus h E [1/2, Hz/2]. For F&R (FITF), parameter E {1, [1,....og, k).
NRT
Time.
Cons.
Robustness
Smoothness
P.M.
Onn log k)
2
AHz
O O(yn/OPP)
LM. 6
O(n k)
4
2Hs +
O(lg((n/OPT)
LNONM.
6
O(n k)
4
(log(())kk-m /OPT)
B.O. S
O(n log k)
co
O(1/k-m//PP
B.O.&LRU
O(n log k)
2k
B.O.&M."
O(n log k)
2
4H2 -2
B.O.&M."
O(n log k)
1+Y
(1+1) (2Hxx - +
0l1kkmm/0P
B.O.&EQ
7
(nk2²
1+7
(1+ HH + +
011/k-1//PP
GUARD&B.CO OO
On log k)
1
2Hh-1
Olog(mn/O8 (PPT)) O Omin(logg DPT
EXGUARD&B.O.
(n log k)
1
2H 2H(-1+0(d)
OPT
Binary
Time.
Cons.
Robustness
Smoothness
M.&P.
((n)
4H₂ + 001)
O(H, TpPOT)
MARKO
((n)
1
00
О Tp
GUARD&LRB
((n)
1
2 211.-++00
O(H₂ /PPTT O /d 7p/OPT)
EXGUARD&LRB
((n)
Action
Time.
Cons.
Robustness
Smoothness
F&R 8
O log
3(1 log k) (1)
(Mog(Ta/OPT))
FitF
Time.
Cons.
Robustness
Smoothness
F&R (FITF) S
On log ((n)
9(1 + 1/b) log k O(b)
Olog(k)/bb my pt
GUARD&PA.
2H;-1 +2
O(H₂ ny OPT)
EXGUARD&PA.
(n)
1
+
O(Hu/d nr
4. Action Prediction. Introduced by Antoniadis al. (20 action predictions have been primarily used metrical task systems (MTS). In caching, they indicate the cache contents of an optimal algorithm. F&R [8] is a recent example that leverages this type of prediction.
Design Principles. Below we compare the underlying designs of existing algorithms in detail.
Embedding methods integrate additional algorithmic logic directly into existing caching algorithms to refine eviction strategies. For instance, PREDICTIVEMARKER and LMARKER [6] refine eviction policies by leveraging eviction chains, i.e.. a sequence of evictions where each evietion is triggered by a cache miss caused by prior eviction. MARK& PREDICT [1] augments the MARKER algorithm by incorporating binary predic- tions to prioritize certain pages for eviction. The MARKER framework marks requested page and prohibits its eviction until the end of phase. While embedding into MARKER
16

---

enables the aforementioned algorithms to achieve logarithmic robustness, this approach inherently limits the best achievable consistency to This limitation arises because the MARKER framework prevents evicting some marked pages, even when OPT would prioritize their eviction.
Instead, some algorithms adopt high-level principles from the MARKER framework without strictly adhering to its structure. For example. LNONMARKER 66 and MARKO [T modify the definition of phases. They both achieve 1 1-consistency but have unbounded robustness.
Switching- based methods dynamically alternate between algorithms based historical performance or detected prediction errors. This approach was first introduced in the seminal work of Fiat et al. [ and later refined by Blum and Burch [33. The algorithms proposed by algorithm and a classical robust
Wei 77 switch between a 1 1-consistent algorithm. Their deterministic variant achieves consistency of 2, while the randomized version attains (1 + >-)cosiistyccyy for E (0, 1/4). Although (1 + 7) appears promising, the competitive ratio of the randomized version includes a non-negligible constant term Okk/7), which degrades practical performance. Sadek and Elias [8] further refine switching- based methods by adopting more fine-graines approach. Unlike Wei (7), F&R (8] switches to a robust algorithm only when prediction errors are detected on the fly, thereby ensuring l-consistency. However, the detection mechanism overly sensitive, resulting in high algorithmic complexity of On" log k)). The key challenge of switching-basee algorithms lies determining the switching timing.
C Proof of Lemma 3.2
Lemma 3.2 For any RB-compliant algorithm A, we have |1 = |1;| and 0 = 0, after serving each request r3.
Proof. The proof proceeds by induction. Suppose the cache becomes full for the first time after serving page requests. For any 1,.... m, the lemma holds trivially, eviction occurs for cither A or OPT. Now assume that at time t; (i 2 m)) the conditions [1 = [1;] and 0 = 0 hold. Consider the following two cases when r++1 arrives at time f,+1:
Case
Pi+1 E O. By hypothesis 0 0 we have P=+1 E O Since Of and 0 are the sets of cached O-pages for OPT and A, respectively, ri+1 results in a cache hit for both A and OPT.
(a) If Vi+1 1, P++1 is I-page at this moment. Then 1/41 17 U {pi+1) ) and 1 U [p+11] ( Since |1;| |1 1, it follows that [1; = 1 On the other hand, 0,41 = 02 \ {pe+1] = 0 {pe+1) = 0
(b) If V-+1 = 0, Pi+1 is O-page at this moment. Then 1/ 1 and 1 1
Thus, 11+11| |1| | |1 Similarly, 0,+1 0 = 0 0
Case (ii)
Pi+1 & 0j. Note that Pi+1 & 1: must hold because OPT evicts 1 1-pages at some time before they are requested again. Since P++1 neither in Of nor 17, r241 results in cache miss for OPT. By Belady's rule, OPT evicts the page with the furthest next request time, denoted as Pa- This page Pa must be a 1-page by definition, implying [1]] > 0.
Then we consider A. By hypothesis O = 0 we have Pi+1 & OAA By hypothesis |I = -|1%/, we have | 0. Therefore, if r:+1 results in cache miss for A, it evicts 1-page from | denoted as Pa; otherwise, 1 results in a cache hit for A, indicating Pi+1 E 1
(a) If W141 = 1, Pi+1 is a I-page at this moment. Then 1; = 1, {po} U (p(+))
For A, | = =|1 regardless of whether ri+1 results in a cache hit or not for A.
Thus, 1 = - Moreover, 0 = 0 = O = 0
(b) If yi+1 = 0, Pi+1 is a O-page at this moment. Then 1 = 1; \ {pa} and
01 = 0, U [p441. :. For A. if ri+1 results in a cache miss, 1 1 \ {p
and 0A, 0 U [pp+11k if r:t1 results in cache hit, 1 1 \ {p:41) and
0 0 U (p.+1) Thus, 1 |1 and o = 0,41 always hold.
17

---

In both cases, | 1 - | and O 0 completing the induction. Additionally, we observe
that A experiences no more cache misses than OPT from the above analysis.
D Proof of Proposition 3.5
We first establish three lemmas facilitate the proof of Proposition 3.5
Lemma D.1. For OPT, after serving each request Ts. the next request time of any page in 12 is later than that of any page in O-.
Proof. Suppose that there exists a pair of I I-page aj and O-page do in the OPT's cache such that the next arrival time of aj is smaller than that of ag. That is to say, h1 < hv- Assume aj is evicted at time μr, then μl < hi since a 1-page is evicted before it is requested again. ag is also cached at time ji since jun hn < ho, and it will be kept cached before hg by the definition of O-page. This implies at the time μl, OPT evicts page whose next arrival time is not the largest, which contradicts the definition.
Lemma D.2. For any algorithm A, after serving each request TG, O C 0 holds.
Proof. Consider any O-page P3 O at some time μ (4,, 4+1). Its last request occurs time t, S t < μ., and its next request occurs at time T₃ > μu. Immediately after its last request at tj. P/ must be in OPT's cache, regardless of whether OPT experienced cache hit or not at ty. Since Pj is O-page, OPT will not evict it before Tj. Thus, at time we have Pj E 0, which proves the lemma.
For OPT and an RB-compliant algorithm A. let H; and H denote the ordered sets of the next request times of 1 1-pages in 1, and 1 after serving request ry, respectively, where the next request times are arranged in ascending order. We use H (1) and ( to represent the 1-th element in these ordered sets.
Lemma D.3. For an RB-compliant algorithm A, after serving each request To H following holds:
(HA) and the
W/ 1,
H
(6)
Proof. We prove this proposition by induction. Suppose the cache becomes full for the first time after
serving m page requests. The above inequalities hold trivially for any 1, 1,... m, eviction
occurs for either or OPT. Now assume that after serving request r (i 2 m). [ < H and (6)
hold. We will show that they also hold after serving request ri+1. There are three cases consider when r arrives:
Case
Pi+1 E O By Lemma D.2, Ps+1 E 0f also holds. Thus, 7r41 results in cache hit for both A and OPT. Then, Pi+1 remains in 0/ and 0, if Vi+1 = O. Otherwise, Pi+1 is moved to 1/41 and 1 for A and OPT, respectively. In both scenarios, |H; < H and clement-wist relationship (6) is maintained after serving Ti+1-
Case (ii)
Pi+1 E Of but Di+1 & OA, Since pi+1 is a O-page at this moment, Pi+1 & 1 also holds. By Lemma D.2 we know that [0,) < |0 Since |0 + + = k = j0 |171. have 17 < T and [H < H . In this case, OPT experiences a cache hit while A suffers a cache miss.
Conceptually, cache evolvement for serving request T/+1 includes two steps: (i) since A is RB- RBBcoopliant, it must evict page from 1,; (ii) P-+1 's next request time is either inserted to both H; and H (if li+1 = 1) or none (if ys+1 = 0). After these two steps,
| < H because H < | before step (i), and step (ii) does not change the relation between HH and H Moreover, the alement-wiss relationship
( continues to hold for + 1. This is because step (i) removes an element from H which can never decrease (1) at any index 1; and for step (ii), inserting the same element to both H and H does not change the element- wise relation.
18

---

Case (iii)
we have Pi+1 & O, Note that Pi+1 & 1 must hold because OPT evicts 1-pages at some time before they are requested again. Thus, OPT suffers cache miss and evicts the 1-page with the furthest next request time from 17. Meanwhile, A can experience either a cache miss cache hit.
P++1 & O By Lemma D.2
A experiences a cache hit, pi+1 1 as Pi+1 É O We can conceptually consider cache evolvement two steps: (i) OPT evicts the 1-page with the furthest next request time from 1, and A evicts p:+1 from 1 (ii) Pi+1 is either inserted to both 1 and 1 (if yi+1 1) none (if 4/+ 0). After these two steps,
| +1 apparently holds because H H A before step (i). Moreover, step (i) does not affect the element-wise relationship 6 because OPT evicts the page with the furthest next request time from 1 i.e., removing the last element from H. For step (ii), inserting the same element to both H and H does not change the element-wise relation either. Therefore, (6) continues to hold for + 1.
suffers a cache miss, it just changes "A evicts pi+1 from AM in step (i) above to be "A evicts page from 1 1 since A is RB-compliant. All the above arguments continue to apply, so both - S H and the element-wise relationship (6) for + 1 hold.
By induction, [H: [ and (6) hold for all 1,... n, where n denotes the total number of requests. This completes the proof.
Proposition 3.5, For an RB-compliant algorithm A, after serving each request ra the next request time of any page in 1 is later than that of any page in O
Proof. Suppose Ps: and Pr, are the I-pages with the earliest next request times 1 and 1; respec- tively. By Proposition D.3 the next request time of Pa. is not earlier than that of Py- By Proposition D.I. the next request time of Py is later than any O-page in O Thus, the next request time of pa is also later than any O-page in O%. Additionally, we have 0 S O by Lemma D.2] Therefore, the next request time of Pa is later than any O-page in 0 completing the proof.
E Proof of Lemma 3.8
Lemma 3.8, RB-following algorithms that blindly follow predictions have unbounded robustness.
Proof. Consider a cache of size 2, where at time f, pages Pa and ps are cached. From time t onward, an infinite sequence of alternating requests for Pe and ps arrives. OPT incurs only one cache miss by evicting Pa upon the first request for Pc, making Pa 1-page and both and Pe O-pages indefinitely. Suppose an RB-following algorithm A receives completely incorrect predictions. the predictions, may instead evict ps and Pe alternately, resulting in an infinite number of cache misses. Since OPT incurs only one miss, the competitive ratio of A is unbounded, implying infinite robustness.
blindly trusts
RB-Following Algorithms that Blindly Follow Predictions
Algorithm 2 gives template RB-following algorithms that blindly follow predictions. Refer to Sec. 3.2 for the definition of RB-following.
19

---

Algorithm 2 An RB-following algorithm that blindly follows predictions
do 2: Receive the page request r; = (44, P:) at time tq
1: for
3: if p; is in the cache then
4:
the cache is full then 5: Call function Evict()
6: end if
7: Load p; into the cache
8: end if
9: end for
3 and 5 define the eviction functions of BLINDORACLE, LRB, and PARROT, re- spectively. They can embedded into the template Algorithm to restore the corresponding algorithms.
Algorithm
Algorithm 3 Evict () of BLINDORACLE
1: Invoke the predictor to get the predicted next request times of cache pages
2: Evict the page with the furthest predicted next request time
Algorithm Evict O) of LRB
1: Invoke the predictor to get the predicted Belady's binary labels of cached pages
2: if there is predicted I-page then
3: Evict predicted 1-page uniformly at random
4: else
5: Evict predicted O-page uniformly at random
6: end if
Algorithm 5 Evict () of PARROT
Invoke the predictor to get the predicted FitF page
2: Evict the predicted FitF page
G Proof of Eviction Pattern of RB-Compliant Algorithms
The following theorem corresponds to Observation Section
Theorem G.I. For an RB-compliant algorithm A, it never keeps an unrequested page in the cache during the time interval between the eviction and next request of another page. Formally, if request r, results in a cache miss time t, and the requested page pt was previously evicted time μ t, then all pages remaining in the cache at time t; must have been requested at least once between and 14
Proof. Suppose, for contradiction, that there is cached page Pa, at time f; that has not been requested since time μ.. Consider an alternative algorithm B, which behaves identically to up to 4, except that it evicts Pa, instead of p; time thereby keeping Pa: cached until 4. Algorithm B incurs the same number cache misses as A before time 4, However, at time 4, experiences cache hit, whereas A incurs cache miss due to the prior eviction of p;. This indicates that B outperforms A after serving rú, contradicting the optimality A, as established Proposition 3.4
H Proof that LRB is RB-following
We first show general conclusion below.
Lemma H.1. If algorithm A is RB-following when serving (ri,..., r5). then A&OPT()) is RB- following. Here, we define the following: (1) OPT(A, j) denotes the OPT algorithm that begins with the cache content A A({Ti....,T. and serves the subsequent requests in where Al A(TT,,... }3))
20

---

represents the cache content of A after serving the first j requests; (2) A&OPT(J) denotes the hybrid algorithm that follows A when serving (f1:...,y T33 and then follows OPT(A. for the remaining sequence.
Proof. Since A is RB-following before serving ry+1, have 0 O by Lemma 3.2 and Propo- sition 3.4 implying that OPT also incurs cache miss at time ty+1 and evicts a 1-page. Moreover, 0. By Belady's 's rule, at time 1,+1, OPT(A, evicts the page with the furthest next request time, denoted Pa- By Proposition 3.5 and |1,3 O, we have Pa 15. This implies that A&OPT(j) is RB-following until served 1 it prioritizes the eviction of 1-pages.
Therefore, if algorithm is RB-following when serving {ri..... ry), then A&OPT() remains RB-following after serving Ty+1- By induction, A&OPT()) is RB-following for the entire request sequence, completing the proof.
Proposition H.2. LRB is RB-following.
Proof. Suppose LRB is RB-following when serving (ri, ry} and incurs cache miss when serving ry4u
Ty+1- By Lemma H.l and Corollary 3.3 &RB is RB-following and always evicts only 1-pages under perfect predictions. Recall that LRB relies on predicted 1-pages labeled by the OPT that begins with the current cache content of LRB, which corresponds exactly to LRB&OPT()). Consequently, under perfect predictions, all predicted 1-pages are 1-pages labeled by OPT. Therefore, LRB remains RB-following after serving rj+1- The proof follows by induction. L.
I Proof of Lemma 4.3
Lemma 4.3
Σ
cc, < OPT < Σ qEQ
old n
9EQ
Proof. We first show OPT S Σ nold, Assume an alternative algorithm GUARD&B that behaves qEe
identically to GUARD& A except that, when serving requests for new pages, evicts the nidd old pages whose next request times are later than those the remaining old pages. As a result, GUARD& experiences cache hits when the remaining old pages are requested. Note that at the end of the q-th phase, the cache content of GUARD& A is identical to that of GUARD&B. B. Clearly, the total cost of GUARD&B is Σ nldd implying that OPT <
gEQ
4EQ
Next, the proof of OPT N Σ
C follows from Fiat et al. 3 though our phase definition differs q
from theirs.
Let OPT, represent the number of cache misses incurred by OPT while processing the requests that arrive during the q-th phase of GUARD& Let St and SG denote the sets of cached pages for OPT and GUARD& A, respectively, at the beginning of the q-th phase. Define hg (0 S S Q) as the number of pages OPT's cache but absent in GUARD& A's cache, i.e., h2 = S n SGAL Note that ho 0.
First, we claim that OPT, 2 Cy hy. Among the eg distinct new page requests in the q-th phase, at most hy of them may already reside in OPT's cache. Hence, OPT incurs at least Cy - hg cache misses.
Next, we show that OPT, , 2 h1+1- By definition, the pages in GUARD& A's 's cache at the end of the q-th phase, S remain in the cache at the beginning of the (q + 1)-th phase. Since OPT's cache 1 contains h pages not present in SGA, it follows that SGA, also contains hy+1 pages that are absent in S* g+ Moreover, since every cached page in SGA, is requested at least once during the q-th must have evicted at least h1+1 pages within the same phase.
phase,
Note that the final phase (Q-th phase) may not end after serving all requests. Thus, to be rigorous, we denote hi+1 as the number of pages that satisfy two conditions: (1) The page has been requested at least once in the Q-th phase. (2) The page is in GUARD&A 's cache but absent in OPT's cache after
21

---

serving all requests. Similarly, OPT must have evicted at least hQ+1 (ho+1 > 0) pages within the same phase.
Combining the two inequalities, we have:
OTT q 2 Σ max Cy Bug hitt))
9=0
Cq hg 1gtt1)
20 ho + hQ+1
Q 2
cq
(since ho = 0,0 0,h1211 2 0),
(7)
2
-=0
which completes the proof.
J
A Tight Analysis of GUARD&A's Robustness
Theorem 4.6 GUARD& is (2H + 2)-rohust, which is tight.
Proof. We adopt Lemma 4.3 Lemma 4.4 and notations from Sec. 4.3
All evictions that occur during given phase form an eviction graph. A directed edge (Pas Ps) is added from page Pa to page P3 if Pa is evicted upon the arrival of request ra, which targets page Pa- At a high level, the directed edge represents "evicted by". Figure iillstraaee an example of such graph consisting of multiple connected subgraphs. In the graph, edges with "pred." and "rand." denote prediction-driven evictions and random evictions, respectively.
old
old
old
chain A (type 2)
rand.
old
old
old
new
chain B (type 1)
pred.
pred.
pred.
rand.
old
old
chain (type 2)
old
old
old
chain (type 1)
pred.
Figure 3: Eviction Graph
The number of edges in the eviction graph equals the number of evictions that occur during the phase. According to the definition of GUARD&A. an eviction graph has the following properties:
The out-degree of any page most 1, as each page can be evicted no more than once within the phase under the "guard" mechanism.
22

---

2. The in-degree of each old page is at most 1, as it will be guarded after being loaded into the cache.
3. The in-degree of each new page is at most 2, it can be loaded into the cache most twice. In addition, a new page with an in-degree of must have an out-degree of 1. It evicts a page based on prediction upon its first cache miss, and a randomly selected old page upon its second cache miss.
4. A new page can only point to (be evicted by) another new page (based on predictions), since request for an old page previously evicted new page only leads to the random eviction of an old page upon a cache miss.
5. A page with an out-degree of must be new page, as an old page remains in the cache if is not evicted during the phase.
A chain that contains multiple old pages and single new page is defined chain, such as chains A, B, C, and D Figure 3 The following two conclusions hold regarding the length of old-page eviction chain, which is defined as the number of edges and depends the chain type. We classify old-page eviction chains based on the first eviction.
old-page eviction
Type 1:
the request for the page evicts old page based on predictions. The expected length of this type of chain at most Hx-1 + 1.
Proof. Denote L(x) the expected number of subsequent random evictions of old pages when the number of unrequested old pages in the cache x. This implies that, subsequently, up old pages will be requested during this phase. Thus, we have
L(x) S 1+ Σ 400,,
(8)
10
where L(O)- = O. Consequently, M(x)= < ΣE =
In the worst case, the old page with the earliest next request time is evicted by the request for the new page. Old pages are evicted randomly afterwards, so the expected length of the sub-chain is bounded by L(k 1) + H4-1
Type the request for the new page evicts an old page uniformly at random. The expected length of this type of chain is at most H
Proof. When the request for the new page evicts an old page randomly, at most k unrequested old pages remain in the cache, since the new page must have been evicted previously. Thus, the expected length of the chain is at most L(k 1) H
Within a connected subgraph with r distinct new pages, all new pages form chain, according to Properties and 4 stated above. Based on Property 3, most one old-page-eviction chain of type and x - old-page-eviction chains of type 2 exist in the subgraph. See Figure 3 for an illustration. Therefore, the expected number of edges within this subgraph is at most H + (x 1) + (x - 1) = r (H + 1).
By Lemma 4.4 we know that the number of old-page eviction chains ny ald old is at most cg. This leads to the following Temma directly.
Lemma J.1. At most Cy old-page eviction chains exist in the eviction graph of phase q, where co denotes the number of distinct new pages requested during this phase.
Combining the above conclusions, the expected number of evictions in phase is most cg (HH-1+1), Finally, we derive an upper bound on the total cost of GUARD& A as follows.
Q
Q
E GA| = dg + Σ B[GA,| & (Hę-1 +1)
C
q=1
q=0
< (2H +2OPTT,
(by Lemma 4.3
23

---

where both GUARD&A and OPT experience dg cache misses during the 0-th phase no evictions occur. GUARD&A (2H 2 established by 44.3
Tightness. Consider the case where ny evictions occur at the beginning of the phase, evicting exactly Cq old pages (i.e., ny Gg) whose next request times earlier than the remaining old pages. In this case, we can bound GUARD& A's 's total cost GA as follows, where denotes the j-th subsequent distinct old page request.
Q
G|GA| cD
B co +
Σ
n4
Bloy]
q=1
q=1
Q
ng + Cg + Σ
Cg
-1)
Co
(j
9=1
j=
Q
= 60
(2 + Hk-co
Hog
(since Fly = cq)
q=1
Q
60
(Ha-1 1 + 1) (equality holds if Co 1)
8=1
(10)
By (T). we have
lim R[GA] Q020
<
Σ (H + 1)0g
9EQ
(by Lemma 4.3
(11)
We now demonstrate that the equality in the final inequality [I can indeed be achieved under the following conditions, where all previously defined settings remain unchanged.
Let wy denote the only new page requested during phase q. implying that Cg = 1. Consider the cache contents of GUARD& A and OPT after all requests in phase q have been served:
GUARD&A: GUARD&A'S cache contains wy and k old pages at the end of phase This is because the request for wy evicts the old page with the earliest next request time, leading to subsequent random evictions of only old pages.
Assume that OPT's cache content at the beginning of phase matches that of GUARD& A and that w. is never requested again after its next request. Following Belady's rule, OPT evicts Wi during this phase. All subsequent old page requests result cache hits. Consequently, at the end of phase q, OPT's cache contains all old pages, with one old page not being requested during phase We denote this old page as ug.
OPT:
As result, at the start of phase q + 1, My resides in OPT's cache but is absent from GUARD&A cache. Suppose Ug serves as the only new page in phase q + 1, implying Cg+1 1, and is requested before any other page in phase q + 1. After serving requests ends. At this point, both OPT and GUARD& A once again have identical cache contents.
1 distinct old pages, phase q +
This construction enables repeated alternation between the behaviors in phases q and q + for all subsequent phases. Notably, OPT incurs total cost of across phases and y + 1, which equals (cg + c/+1)/2. Consequently, this pair of phases repeats and Q co, obtain:
OPT
Cq.
2
thereby establishing the tightness the bound in 5 This case confirms the tightness.

---

K
Applications of GUARD
K.1 Algorithm
We first present the pseudo-codes for the three variants of GUARD&A.
Algorithm 6 GUARD&A
U < 9 (the set tracks unrequested old pages in the cache)
2: for = 1, ..... do
3: Receive a page request r, = (l,, at time 4
4: if p; is not in the cache then
5:
the cache is full then 6: u is empty then Unguard all cached pages
7:
8:
U {all cached pages} (a new phase begins)
9:
end
if pt evicted in the current phase then
11:
Evict a page x from U uniformly at random Guard ps
12:
13:
else
S {all unguarded cached pages} Call function Evict(S)
15:
end if
17:
if the evicted page r E U then
u U[zr
19:
end if
end if
21:
Load p; into the cache
22:
end if
23:
u then if p; + [p.
24:
25:
end if
26: end for
Algorithms 7 8 and define the eviction functions of BLNDRRA& GUARD&LRBB, and QuArd&PPRrOT, respectively. They can be embedded into Algorithm restore the corresponding algorithms.
Algorithm 7 Evict(S) of BUURD&&BLNDOORACEL
1: Invoke the predictor to get the predicted next request times of pages in S
2:
Evict the page with the furthest predicted next request time from S
Algorithm Evict(S) of GUARD& LRR
1: Invoke the predictor to get the predicted Belady's binary labels of pages in S
2: if there is predicted I -pag then
3: Evict predicted 1-page from S uniformly at random
4: else
5: Evict predicted O-page from S uniformly at random
6: end if
Algorithm 9 Evict(S) of GUARD&PPRROY
Invoke the predictor to get the predicted FitF page from
2: Evict the predicted FitF page from S
25

---

All these algorithms invoke the predictor upon eviction, consistent with common implementations in real systems. GUARD&A restricts the range predictions only for unguarded pages the cache, denoted by S. Below, we present implementation details regarding the predictor queries.
G requires only the predicted next request times for pages in S, which is straightforward to implement since each prediction is independent.
GUARD&LRB utilizes the predicted Belady's binary labels only for pages in S, as labeled by the OPT algorithm that begins with the current cache content and serving subsequent requests in without evicting pages outside of S. This is achieved by the LRB Predictor [9] which first predicts the next request times of pages S and then classifies them based on the predicted Belady boundary.
GUARD& PARROT queries the predictor for the FitF page within S, selected based on the eviction priorities assigned by the FitF page predictor, neural network-based model proposed by Liu et al. [10].
K.2 Smoothness Proof for GUARD&
We first show the relationship between prediction error fp: and inversions, as studied by Rohatgi [6]
Definition K.1. (Inversion). Given two sequences A (21,02,.. .... an) and B (b1, .... bn), let inv(A, B) be the number of inversions, which denotes the number of pairs of indices (i.j) such that a, aj but b, >> by-
Definition K.2. (li-distance). Given two sequences A (a1, - an) and B (b1.-.;bal define
444 B) = Σ a, be] as the I lydistance between A and B.
We then present lemma from Rohatgi 66, with its descriptive form slightly modified for clarity. Lemma K.3. (Rohatgi (0). Lemma 4.1) Let A = (a1,... an) and B = (bI....,ba) be two integer sequences. Then inv B) S (A, B), with inv(A) (A) and l as defined above.
Next, relate 7/e the number of inversions. For page request sequence a, let their request time be 0 {Ti, T2 ... Tn and let [T iT..... "....,,JJ Th represent the predicted arrival times. By definition, T). = (0, 0). Then, by Lemma
K.3 we have
inv inv 0) s (0. 21j.
(12)
Theorem K.4. GUARD&BLINDORACLLE is Olog(nn/OPT)))-mm
Proof. In the following, bound the expected length of an old-page eviction chain in phase q. called Eg. according to the properties of the eviction graph (Figure Denote |1,] as its length.
If E, is a chain of type 1, which consists of new page and multiple old pages, and the request for the new page eviets old page based on predictions. Denote the new page as Pa. Let Ug be the set of unrequested old pages when the old page Ps. which was previously evicted at time μ by the request for Pas requested and cache miss occurs. This contributes at least 1 ((E,) [usl inversions, since each pair of pæ and page in Ug indicates an inversion in predictions time μ.
According to L(x)= < He in Appendix D
we have E|E,|| || < O(log I(E,)).
If Eg is a chain of type 2, which consists of new page and multiple old pages, and the request for the new page Pa randomly evicts an old page. Its new page Pa must be previously evicted by another new page py, as Pa must have an in-degree of 2 and an out-degree of in the eviction graph, according to Property 3 mentioned in Appendix [] Let Ud, be the set of unrequested old pages when the new page Pa is requested. Each pair of p., and a page in U, indicates an inversion in predictions when evicting Pa- Similarly, this chain contributes at least (EEg) Ua inversions, and we have 1] < Ollog I (E,)))
26

---

The total inversions inv(0,0) 2 Σ Σ ((
Suppose there are a total of N old-page eviction
9 &
chains across all phases, where N = Σ Σ 1
Σ
old by definition. By Lemma 4.3 we have
9E@ Eg
gE
OPT < N =
Σ
old
S
Σ
cq S
20PT.
(13)
9
qE@
GUARD&BLINDORACLE'SS expected total cost G is:
B[G&B] <
Σ
(cp
8E@
Eg
Σ
Cq
(log I(E)))
(by Lemma 4.3
&
inv e0 0)
Cq
N (log(
(by Jensen's inequality and concavity)
N
< 2OPT 20PT Ollog(
T
(by and Lemma K.3
OPT
( log(
OPT
1/t )).
(14)
This demonstrates the OOlog(n// (OP)) -mootheess of GUARD& BLINDORCLE
K.3
Smoothness Proof for GUARD&LRB
We first present key lemma that helps establish smoothness. We denote OPT (A, f) as the OPT algorithm that begins with the cache content A(fri,..., and serves the subsequent requests in a without evicting guarded pages. Here, A( (Tri,.,TT;)) represents the cache content of after serving the first requests.
Lemma K.5. When serving request r5+1 at time ti+1, if GUARD&LRB evicts a I-page (as labeled by OPT(A, j)), then the current phase must terminate before ps is requested again.
Proof. Suppose OPT(A, j) evicts page Pa at time μ t.41. By definition, Ps is the page with the furthest next request time at time μ. Let T. denote the next request time of pa- This implies that the remaining i- pages in the cache at time i will
requested before Tz.
Whenever one of these remaining pages, say Pa. requested after time μ., if it results in a cache hit, then p. l or U 44 \ {..).. Otherwise, if a cache miss occurs, GUARD&LRB evicts random page from U. Therefore, after evicting P> and serving requests for all of these pages, the current phase must terminate.
Theorem K.6. GUARD&LRB O(H: 1// (e/OPPT)-mmoone
Proof. According the description of GUARD&LRB provided in Section K.1 there is at least 1-page in the set of unguarded pages S upon a cache miss. Otherwise, the OPT algorithm, starting from the current cache content, would have evict a O-page from S, contradicting the definition of Belady's 's binary labels. Thus, the algorithm always evicts a 1-page when predictions are accurate upon cache miss.
According to the properties of the eviction graph (Figure 3), each old-page eviction chain results from unique prediction-driven eviction. By Lemma K.5 evicting a 1-page leads to subsequent evictions. Thus, given a prediction error of Mы,, the total expected length of all old-page eviction chains is most O(H₂ 1)), where each chain has length at most O (H&)) shown in Appendix
OH 1/6) also bounds the expected total cost of GUARD&LRB, thereby completing the proof.
K.4 Smoothness Proof for GURRD&PARROT
Theorem K.7. GUARD&PARROW is O(H₃ OP/OPTT smooohh.
27

---

Proof. According to the properties of the eviction graph (Figure 3), each incorrect prediction of FitF page leads either (1) the eviction of an old page, which subsequently generates an old-page eviction chain of type 1, or (2) the eviction of new page, which subsequently generates an old-page eviction chain of type
Therefore, given prediction error of 77,, there are at most 7y old-page eviction chains in the eviction graphs across all phases. From Appendix [ the expected length of old-page eviction chain is at most (H+)). Thus, we can bound the expected total cost of GURRD&PARROT, denoted E[G&P), as:
E|G&P| S O(H2 mf))
(15)
which completes the proof.
L Lower Bounds
Robustness. No randomized -aggeend can achieve robustness better than Hę. which is the lower bound of randomized online caching algorithms [3]. To the best of our knowledge, existing online algorithms that achieve Hę competitive ratio include EQUITABLE 44, PARTITION 44). ONLINEMIN (45), among which ONLINEMIN has the lowest asymptotic time complexity and uses (log k) time per request (or Oloo k/ log log k)) in the RAM model). Thus, we may be able to further enhance the consistency/robustnes trade-off of the robustification framework to (1, H4 + (1)). at the expense more than (1) additional computation per request.
Smoothness. Rohatgi [6] demonstrates that for a randomized learning-augmented caching al- gorithm utilizing next request time (NRT) predictions, the smoothness cannot be better than (log(11 (/k log k) n//OPT)). To the best of our knowledge, no existing algorithm has achieved this bound. At the same time, whether improving smoothness to approach this bound compromises 1-consistency or bounded robustness remains an open problem.
M More Experimental Results and Discussions
M.1 Experiments on Brightkite and Citi Using PLECO and POPU
We evaluate algorithms that utilize page request time predictions on the BrightKite and Citi datasets using PLECO and POPU, two widely adopted predictors in this domain 5 20 g For F&R, predictions of page request times are converted into action predictions, following the methodology of Sadek and Elias 88. [ presents the cost ratios of different algorithms. The results indicate that GUARD&B.O. consistently achieves the best or near-best performance.
Table 5: Cost ratios of algorithms BrightKite and Citi using PLECO and POPU predictors.
Dataset
Predictor
B.O.
P.M.
LM.
LNoNM.
B.O.&M.
F&R
GUARD&B.O
PLECO
2.081
1.341
1.337
1,321
1.317
1,348
1.303
BrightKite
POPU
1.707
1.262
1.264
1,259
1.305
1.304
1.198
PLECO POPU
2.277
1.877
1.875
1.888
1.860
1.864
1.900
Citi
1.739
1.776
1.779
1.769
1.732
1.790
1.693
M.2
Experiments on SPEC CPU2006 Benchmark Using PLECO and POPU
To evaluate the performance of algorithms that utilize predictions page request times in a more realistic scenario, employ real-world memory trace datasets from the SPEC CPU2006 benchmark, following the setup Chiędowski et al. [15].
Average Cost Ratios. Table presents the average cost ratios of various algorithms relative to OPT across all 13 datasets. The results indicate that GUARD& B.O. O. achieves the best overall performance on average.
28

---

Table 6: Average cost ratios SPEC CPU2006 Benchmark using PLECO and POPU predictors.
Predictor
LRU
B.O.
P.M.
LM.
LNoNM.
B.O.&M."
F&R
GUARD&B.O.
PLECO
1.478
1.404
1.335
1.335
1.346
1.294
1.360
1.226
POPU
1.478
1.261
1.312
1,320
1.312
1.233
1.319
1.203
LRU-normalized Cost Ratios and Figures. To ensure clear comparisons across different datasets, adopt the LRU-normalized empirical competitive ratio from Chiędowski et al. [13], referred as the LRU-normalized cost ratio (LCR) in this study. LCR evaluates an algorithm ALG in relation to LRU, and is defined follows:
ALG - OPT LCR(ALG) = LRU OPT
The average LRU-normalized cost ratios across all 13 datasets are summarized in Table 7 while Figures 4 and 5 provide a datasct-wise performance breakdown. These results further validate that GUARD& O.O. consistently outperforms other methods or remains among the best-performing algorithms.
Table 7: Average LRU-normalized cost ratios on SPEC CPU2006 Benchmark using PLECO and POPU predictors.
Predictor
LRU
B.O.
P.M.
LM.
LNONM.
B.O.&M." D
F&R
GUARD&B.O.
PLECO
1
1.050
0.947
0.943
0.926
0.763
0.845 0.829
0.625
POPU
1
0.768
0.881
0.885
0.880
0.664
0.568
2.4
LRU-Normalized Cost Ratio
2.2
2.0
1.8
1.4
1.2
LRU
0.8
0.6
0.4
0.2
OPT
astar
bzip
bwaves
cactusadm
gems
Ibm
lesfie3d
libg
mcf
milc
onnetpp
sphinx3
xalanc
MARKER
B.O.
P.M.
LM.
LNONM.
B.O.&M."
B.O.&M.
F&R
GUARD&B.O.
Figure LRU-normalized cost ratios on SPEC CPU2006 Benchmark using the PLECO predictor.
M.3
Experiments on SPEC CPU2006 Benchmark Using LRB predictor
In this section, we evaluate performance of algorithms leveraging binary predictions of Be- lady's binary labels on datasets from the SPEC CPU2006 benchmark, using LRB predictor. The algorithm MARK& PREDICT (M.&P.) is excluded from this comparison, as employs different interpretation of predicted binary labels. In addition, implement LRB&MARKER 2 (LRB&M..) P)

---

1.8
LRU--Nomalized Cost Ratio
1.6
1.4
1.2
LRU
0.8
0.6
0.4
0.2
OPT
astar
bzip
bwaves
cactusddm
gemss
Ibm
leslie3d
libq
mef
mile
omnetpp
sphinx3
xalane
MARKER
B.O.
P.M.
LM.
LNoNM.
B.O.&M."
B.O.MM.
R
F&R
GUARD&B.O.
Figure 5: LRU-normalized cost ratios on SPEC CPU2006 Benchmark using the POPU predictor.
and &AR&MARKER R. (LRB&M.. R), which combine LRB with MARKER using deterministic and randomized switching, respectively, following the switching based approach introduced by Wei [7].
Following the methodology of Song al. []] extract features from the SPEC CPU2006 datasets, setting [Delta]| 10 and EECC| 10. In addition to the original PC and address features, a total of 22 features were used for training. The GBM model is configured with learning rate of 0.01, a maximum depth of 6, and 31 leaves. Both the sub-sample rate and column sample rate are set to 0.8. The model employs L2-norm loss, and early stopping is applied 8000 rounds to determine the optimal parameters.
Average Cost Ratios. Table 8 presents the average cost ratios of all evaluated algorithms relative to OPT across all 13 datasets. The results show that GUARD& LRB outperforms other algorithms, including the base algorithm LRB.
Table 8: Average cost ratios on SPEC CPU2006 Benchmark using LRB predictor.
Predictor
LRU
MARKER
LRB
MARKO
LRB&M.
LRB&M.
GUARD&LRB
LRB predictor
1.478
1.394
1.281
1.268
1.259
1.293
1.171
LRU-normalized Cost Ratios and Figure. Table 9 and Figure 6
show the LCR comparison when
using GBM.
Table Average LRU-normalized cost ratios on SPEC CPU2006 Benchmark using LRB predictor.
Predictor
LRU
MARKER
LRB
MARKO
LRB&M."
LRB&M
GUARD&LRE
LRB predictor
0.970
0.809
0.506
0.714
0.808
0.357
30

---

1.2
Normalized Cost Ratio
LRU
0.8
0.6
0.4
0.2
OPT
astar
bwaves
bzip
cactusadm
gems
Ibm
leslie3d
libg
mcf
mile
omnetpp
sphinx3
xalane
MARKER
LRB
MARKO
LRB&M."
LRB&M."
GUARD&LRD
Figure 6: L.U--nrmalized cost ratios on SPEC CPU2006 Benchmark using LRB predictor.
M.4
Experiments on SPEC CPU2006 Benchmark Using Parrot
FitF page predictor. We investigate Parrot, a neural network seteork-based model proposed by Liu al. [10], which utilizes an imitation learning approach to approximate the optimal policy, Built on LSTM and attention mechanisms, Parrot predicts the page with the highest eviction priority whenever an eviction is needed. In our experiments, Parrot is trained for 20,000 steps with batch size of 32, without applying the Dagger algorithm [46]
The Algorithm PARROT. We propose PARROT (abbreviated as PA.), which directly follows the prediction of the Parrot model and evicts the predicted FitF page. PARROT also RB- following algorithm that blindly follows predictions. It is clear that PARROT is 1-consistent, while GUARD& PARROT (abbreviated as GUARD&PA.) (2H + 2)-robust. Additionally, ment PARROT MARKER ?> and MARKOT&MARKER" R which combine PARROT with MARKER using deterministic and randomized switching, respectively, following the switching-bar based approach introduced by Wei 7
imple-
Interestingly, the best algorithms for the metrics differ due their different calculations. Nonethe- less, GUARD& PARROT consistently achieves either the best or near-best performance.
Average Cost Ratios. Table 10 shows the average cost ratios of algorithms compared to OPT across all 13 datasets.
Table 10: Average cost ratios on SPEC CPU2006 Benchmark using the FitF page predictor.
Predictor
LRU
MARKER
PA.
PA.&M.
&A.&M.
GUARD&PA.
FitF page predictor
1.478
1.394
1.363
1.315
1.348
1.338
LRU-normalized Cost Ratios and Figure. Table and Figure show the LCR comparison.
Table 11: Average LRU-normalized cost ratios SPEC CPU2006 Benchmark using the FitF page predictor.
Predictor
LRU
MARKER
PA.
PA.&M.
&A.&M. R
GUARD&PA.
FitF page predictor
0.970
1.006
0.851
0.947
0.816
31

---

1.8
LRU-Normalized Cost Ratio
1.4
1.2
LRU
0.6
0.4
0.2
OPT
astar
bzip
bwaves
cactusadm
gems
Ibm
leslie3d
liby
mcf
mile
omnetpp
sphinx3
xalanc
MARKER
PA.
PA.&M.
&
GUARD&PA.
Figure 7: LRU-normalized cost ratios on SPEC CPU2006 Benchmark using the FitF page predictor.
N
The EXGUARD Framework
N.1 Motivation and Performance Overview
Observation. Essentially, the bounded robustness of GUARD&& stems from page protection, i.c., the guard mechanism. Its asymptotic logarithmic robustness depends random evictions when necessary. However, overly aggressive random evictions may lead to a long eviction chain initiated by eviction based on incorrect predictions, thereby degrading smoothness. Conversely, relying solely on predictions compromises robustness and may be impractical due to frequent predictor queries.
This motivates limiting the number of random evictions (Line 13 in Algorithm 10 on each eviction chain, as illustrated in Figure This strikes balance between smoothness and the number of predictions used without compromising the asymptotic robustness. T2ble compares the applications of EXGUARD with those of GUARD.
Table 12: Robustified RB-following algorithms. Here, B.O. stands for BLINDORACLE, PA. denotes PARROT. Cons., #Pred. and Time. represent consistency. number of predictor calls, and time complexity, respectively. For EXGUARD, d Hx]. For EXGUARD&B.O. O., À h/c" < 1/e, where h = Hz/(2d) and h E [1/2, Hz/2].
Algorithm
Cons.
Robustness
Smoothness
#Pred.
Time.
GUARD&B.O.
2H + 211x-1 + (d))
(Tog(n/OPTT)
O(OPT)
O(n log k)
EXGUARD&B.O.
O Ominnlog 2u / 2
O(d OPT)
O(n lol k)
GUARD&LRB EXGUARD&LRB
211 + 2
O To TO/PPT)
((OPT)
O(n)
2H1 + (d)
O(H// Tp/OPT)
Old OPT)
O(n)
GUARD&PARROT EXGUARD&PA.
2H +
O(He /PP)
((OPT)
O(n)
2H + (d)
O(Ha/d felaaddns//OP OPT)
Old OPT)
O(n)
old
old
old
pred.
at most Ha/d random evictions
pred.
Figure 8: Random eviction budget along the eviction chain
32

---

Algorithm 10 EXGUARD&A
U 9 (the set tracks wrrequested old pages in the cache)
2: for i 1,.... n. do
3: Receive a page request r; (c) at time
4: if p; is not in the cache then
5: if the cache is full then
6:
uf is empty then Unguard all cacked pages
7:
8:
U &- {all cached pages} (a new phase begins)
9:
end
10:
E 4- the corresponding eviction chain of pi (EE) +- the random eviction budget of & if p: evicted in the current phase then if BEE)= Σ 0 then
11:
12:
13:
14:
Call function Evict (u)
15:
B(E)= = Hx/d
16:
else
17:
Evict a page x from uniformly at random BEE) B(E) 1
18:
19:
end
20:
Guard pi
21:
else
22:
S (all unguarded cached pages}
23:
Call function Evict(S)
B(E) Hx/d
25:
end if
if the evicted page x U then
27:
u U-
end
29:
end if
30:
Load p; into the cache
31:
end if
32:
if p; then
33:
u + (pp.
34:
end if
35:
end for
N.2 Algorithm Descriptions
Algorithm 10 describes the EXGUARD framework. Algorithm 7 and 9 can also be embed- ded into Algorithm 10 to generate the corresponding algorithms: EXGLARDD&BLINOOAACLEE EXGUARD&LRB. and EXGUARD&PARROT.
Theorem N.1. EXGUARD& is 1-consistent and 2H (dd)roobus.
Proof. We focus on the modification introduced by EXGUARD over GUARD.
Since EXGUARD& A retains the guard mechanism, it remains 1-consistency, as established by Proposition 4.1 and Corollary
From the analysis in Appendix J the expected length of an old-page eviction chain is at most O (H₂)). EXGUARD introduces most d) additional prediction-driven evictions along each chain, resulting in (2H + -obusttbss.ssss.
N.3 Predictor Usage Proof for EXGUARD
Theorem N.2. GUARD&A and EXGUARD& calls the predictor O(OPT) and O(d OPT) times, respectively, where A E (BLINDORACLE, LRB, PARROT).
33

---

Proof. Recall that the predictor is called only when an eviction is required, consistent with common implementations in real systems. Let A (BLINDORACLE, LRB, PARROT] in the following.
For GUARD& A, a prediction-driven eviction occurs only when serving request for a new page. Thus, the number of predictor calls in phase g ng- By Lemma 4.4 and 4.3
bound the total
number of predictor calls as:
Σ Thy gE Q
S
Σ 20g S 40PT = O(PPT). Q
(16)
EXGUARD& introduces additional (Hy, /d) calls for the predictor. According to Theorem N.1 the expected total cost of EXGUARD&A A satisfies Σ (mg + 0₂) I OPT O(H)). Therefore, the
q
total number of predictor calls used by EXGUARD&A is bounded by:
Σ
(ng + d o [1,) s Old OPT).
(17)
16 and 17 complete the proof.
N.4
Smoothness Proof for EXGUARD&&LINDORACIE
Theorem N.3. EXGUARD& BLINDORACLE is (mmin((g((//OPP).// / smooth, where h = (2d(.
Proof. For old-page eviction chain Eg in phase q with æ mediction-driver evictions, the expected length of it is | S x Hg/d. When there are z unrequested old pages in the cache, the expected number of subsequent random evictions satisfies L(z) S H2 In(k) 1. (Refer Appendix for eviction results in y subsequent random evictions, it implies at
[(=).) Thus, if a prediction-banl least (ee)) inversions in expectation, arising from all pairs between the prediction-driver evicted page and other unrequested old pages.
From the above, if Eg contributes I(Ey) inversions, then I(E) 2 O(2² Hx/d) since there are
prediction-driven evictions. Therefore, |E,1 S x Hx/d S 0
Hh
I.E "aal
The total number of inversions satisfies inv(0, 0) > Σ ΣE()) Let N denote the total number of
qE &
old- eviction chains, where OPT & N < 20PT, as shown in Equation of Appendix K.2 We then bound the total of EXGUARD& BITTAAAAI denoted as E[ExG&B] by
E EXG&B] < EG cq + ΣΣ (Hald / ((Ea)/eMaa))) (by Lemma J.1)
VEQ
inv inv(0.0) (()00)
< Σ
Cq N HHH//(HHeee (He/(deHu/(dd)
(by Jensen's 's inequality)
N
Q
= = h/c²
Tl
(by Lemma
K.3
(18)
OPT
where / = H2d() ExG.&B.O. inherits the O(lo((n/OO (OPT)) smoothness of GUARD&B.OO O.. adding at most (d) evictions per old-page chain, where 1 S d < HІ. Combining the two bounds above completes the proof.
N.5 Smoothness Proof for EXGUARD&LRB
Theorem N.4. EXGUARD&LRB is OHHy/d Tp/ OPP)))sooooth
34

---

NRT Proof. EXGUARD&LRB limits the number of subsequent random evictions to Hx/d after prediction- eviction. According to the smoothness analysis GUARD&LRB (Theorem K.6). and given a prediction enror of Ths, the expected total cost of EXGUARD&LRR is at most O(H /d (b), thereby completing the proof.
N.6 Smoothness Proof for ExGUARD&PARKEE
Theorem N.5. EXGUARD&PARROT is ((Hy/dd 1//OPT)
Proof. Similarly, EXGUARD& PARROT limits the number of subsequent random evictions to H after prediction- -based eviction. Based on the smoothness analysis of GUARD& (Theorem K.7
we can bound the expected total cost of EXGUARD&PARROSS denoted B E|x as:
E[ExG&P] O(Hx/d. ns);
(19)
which completes the proof.
N.7
Trade-offs Between Smoothness and Predictor Usage in ExGuard
Table 13: Comparison of Smoothness and Predictor Usage.
Smoothness
#Pred.
P.M.
((Vss)
O OPT)
LM.
((log(p:))
((OPT)
LNONM.
(llo((k) pp))
unbounded
B.O.
O(1/k vP1)
unbornded
B.O.&LRU
O(1/k (p:)
O(k OPT)
B.O.&M." D
O(1/k pp))
O(H₂ OPT)
B.O.&M."
((1/k.p2)
O(H₂ OPT)
&.O.EEQ.
0(1kk-P1) O(lo((pi)) O (min(log(()))AA//p)
O(H, OPT)
G.&BOO.
((OPT)
ExG &B...
Old- OPT)
Binary
Smoothness
#Pred.
M.P.
O(Hs ppb)
O(H₂ OPT)
MARKO
O(H Pb)
unbounded
G&&LRB
O (P))
O(OPT)
EXG.&LRB
O(He/d- (p))
O(d-OPT)
Action
Smoothness
#Pred.
F&R (f(1) = 1) (llg((P))
O(Vk OPT)
F&R
O0 (pa))
Of OPT)
FitF
Smoothness
#Pred.
F&R (FITF)
(llo(kk)/bbgg ips)
O(b OPT)
G.&PA.
O(Hs (P))
O(OPT)
EXG.&PA.
O(Hx/d-pp)
O(d OPT)
Notations in Table 13
Abbreviations include BLINDORACLE (B.O.), PREDICTIVEMARKER
(P.M.,, LNONMARKER (LNoNM.), LMARKER (LM.), BLINDORACLEKMARKER (B.O&&M) &.... EQUITABLE (EQ-), MARK&PREDICT (M.&P.), PARROT (PA.), GUARD (G.), and EXGUARD (ExG.).
#Pred. represents the upper bound of the number of predictor calls. F&R's smoothness depends on f(i), which limits predictor calls. Our experiments focus on the F&R variant with optimal smoothness (f( = 2 1). For clarity, we denote n// /PP as TPP as yb. /PPOPT as Pa. and n /PPT y, where Mı T/b Tex My represent different types of prediction errors.
For EXGUARD, parameter d E [1, Hy]. The smoothness parameter of ExG.&B.O. satisfies = h/ch < 1/e (see Theorem N.3 where Hx/(2d). For F&R (FITF), parameter b log..,,ogg,,
35

---

Analysis of Predictor Usage. B.O. and MARKO. suffer from unbounded robustness and invoke the predictor on each cache miss, resulting unbounded predictor usage. The predictor usage of F&R and F&R (FITF) has been analyzed in the corresponding paper.
P.M. invokes the predictor O -PT)), it evicts pages based predictions whenever the corresponding eviction chain has length at most Hę. In contrast, LMM. relies on predictions only once the beginning of each eviction chain, resulting in (OPTT) predictor queries. The predictor usage of LNONM. is unbounded, as it invokes the predictor once per eviction chain, and the number of eviction chains depends on the total prediction error.
M.&P.. invokes the predictor on each cache miss, so its predictor usage bound is the product of O(OPT) and its robustness. Similarly, the predictor usage of B. R.O.&AA &A is bounded by the product of ((PPT) competitive ratio of the classical algorithm A, where A E (LRU, MARKER, EQ.)
Favorable Tradeoffs Achieved by EXGUARD. For algorithms relying NRT predictions, ExG.&B. B.G.&B.O.. achieves better tradeoffs than P.M. and LMM as their tradeoffs are theoretically directly comparable. To compare with other algorithms such B.O. OR&,R, conduct experiments, and the results indicate that ExG. B. O. achieves the best empirical tradeoff.
Moreover, both ExG.& B.B.O. O. and G.&B.O O. exhibit good smoothness, even with O(OPT) predictor usage. This enhances practicality, especially when predictor calls are costly.
Among algorithms that rely on binary predictions or the FitF predictor, both ExG.&LRB and ExG.&PA. achieve state-of-the-art tradeoffs.
N.8 Experimental Results for EXGUARD
We empirically compare EXGUARD&B.O. O. with other algorithms, with d set Ha.
1.R11 MARKER
LRU
Number predittor calls
MARKDR
B.O.
Coi
LNoxM.
LNONM.
P.M.
PM..
B.O.MM."
B.O.MM"
G.BB..D
G.R.O.O.
EXG.&B.O.
EXG &B..
Figure 9: Performance with synthetic predic-
Figure 10: Number of predictor calls with syn- thetic predictions of NRT on BrightKite.
tions of NRT on BrightKite.
Table 14: Average cost ratios (CR), average LRU-normalized cost ratios (LCR), and average number of predictor calls (#Prred.) on SPEC CPU2006 Benchmark using PLECO predictor.
Metries
LRU
B.O.
P.M.
L.M.
LNoNM.
B.O.&M.
G.&BOO.
ExG.&B.O.
CR
1.478
1.404
1.335
1.335
1.346
1.294
1.226
1.225
LCR
1.049
0.946
0.942
0.951
0.766
0.627
0.623
#Pred.
79488
75870
72682
72767
79488
62099
62553
Improved Performance. Figure 9 10 and Table 14 show that EXGUARD&B.O outperforms GUARD&B. O. through increased predictor usage, empirically validating its improved smoothness. is noteworthy that &.& O. and ExG. ExG.&B.C. &BO. depend less the predictor than other algorithms utilizing next request time (NRT) predictions.
In the above, B.O.&M. R is excluded due to underperforming relative to B.O.&M. F&R is excluded due to its reliance on action prediction. Although action predictions can be generated using (NRT), doing so requires NRT predictions for all requested pages. In contrast, other algorithms only predict the NRT of cached pages eviction (predictions can be reused if not requested). Thus, their predictor call counts not comparable.
36

---

Other Caching Models
Beyond the classical caching model, where item sizes and cache-miss costs are uniform, researchers have also investigated more general variants such as weighted caching, in which different pages incur different loading costs, both without machine learning [47] and with
approaches 48 49). However, research on settings, such as those with variable-sized items, remains limited and deserves further study.
algorithms for general caching
In addition to accounting for cache-miss costs and item sizes, the conventional caching model inherently assumes that every requested item is stored upon access. This constraint is prevalent in classical systems. (I) In operating systems, virtual memory management depends on the guarantee that once page is requested, must be loaded into physical memory for execution to continue; otherwise, data errors, crashes, or inconsistent behavior may occur [50]. (2) In databases, this constraint ensures data consistency and transaction integrity in relational systems [5T] If page is not retained in memory after being accessed until the transaction completes, it may result in partial updates or lost modifications, thereby violating the transaction's 's atomicity.
In contrast, the constraint can be relaxed in several modern settings. (1) In web browsers, caching is more flexible, as algorithms such TinyLFU 522 explicitly allow the system to skip caching certain requested items. (2) In content delivery networks, caching decisions are governed by parameters like TTL, content popularity, and regional demand [53], meaning that not all requested content is cached immediately at the edge. In summary, whether this constraint can be relaxed depends on scenario-specific requirements. Future research could explore rearning-augment
algorithms that operate without this constraint and investigate how cache admission choices impact robustness.
P Experimental Setup
Most of our experiments rely solely on a standard computer equipped with a CPU and RAM. Evaluating algorithms that use neural network-based predictor, such as PARROT, requires a GPU,
Broader Impacts
This paper presents the design, analysis, and evaluation learning- augmented algorithms for the caching (paging) problem. Our work has potential positive societal impact by improving the efficiency and performance guarantees of caching systems.
37

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction clearly reflect the contributions, aligning both the theoretical and experimental results.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
The algorithms proposed in this paper are only for the traditional caching (paging) problem, instead of the general caching problem, such as weighted paging caching with varying sizes, etc. This has been stated at the beginning of our paper in the introduction. For empirical evaluation, we explicitly list all the open-source datasets used. Although they are extensive, it is not possible to cover every caching scenario.
Justification:
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory assumptions and proofs
38

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: All propositions, lemmas, theorems, and corollaries in the paper are numbered and cross-referenced. Each theoretical result fully proven, either the main text or the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results,
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We publicly release the code and data, along with instructions to reproduce the results reported in the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to model. In general. releasing code and data often one good way to accomplish this, but reproducibilityy can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open- open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibiliity In the case of closed-source models, it may be that access to the model is limited in
39

---

some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We publicly release the code and data, along with instructions to reproduce the results reported in the paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. ec/
public/guidess httpl///uuiiss/ooouuubiissssssss onlliicy))) for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ //nips. //nips.c/pput httpll/ic/guidee//oeeeeeeeeeeeee
ssiiisssiniiii ssionPolicy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: The detailed experimental settings are presented in the experiment section. Moreover, the code is provided.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We have given the distributions and parameters for synthetic prediction gener- ation in the experiment section.
Guidelines:
The answer NA means that the paper does not include experiments.
40

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Section provides detailed requirements for reproducing the experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.g., preliminary or failed experiments that didn't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: We have reviewed the NeurIPS Code of Ethics and affirm that the research conducted adheres to it in all respects.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: See Section
41

---

Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: The data and code for certain existing algorithms were obtained from publicly available datasets or open-source GitHub repositories provided by the corresponding authors.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
42

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the datasets.paperssiii paperswi thcode. www.coo//aaaaa datasets package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
The code is provided along with its documentation.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmodll as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
43

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
The proposed methods do not involve L.MMs.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy httppe///earrrpooccc///oeeeerrre for what should or should not be described.
44


Reviews:
[{"review_id": "WeQ84Gt9HL", "reviewer": "Reviewer_exXN", "summary": "The authors address the problem of enhancing the robustness of learning-augmented caching algorithms. They propose GUARD, a general framework designed to robustify caching strategies that adhere to a relaxed version of Belady’s rule. GUARD achieves a robustness guarantee of $​2H_k + 2$ while incurring minimal additional computational overhead. The authors conduct experiments on multiple datasets to verify the effectiveness of the GUARD framework.", "questions": "Please see weaknesses above.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths.** The authors consider an important problem of robustifying online caching algorithms and develop a general framework that can be utilized to robustify learning-augmented caching algorithms that follow the relaxed Belady’s rule. The algorithm is intuitive, while the results presented are impactful. The paper is well written and easy to follow even for a non-expert. The presented experiments demonstrate the effectiveness of the proposed framework. \n\n**Weaknesses.** The paper has only minor weaknesses; however, I provide a few concerns that may be worth addressing.\n\n- There is an issue with the notation, in  Section 3, OPT is defined to be an algorithm. Then, in Section 4, the authors provide upper and lower bounds on OPT. Please correct. \n\n- The discussion in observation 2 can be strengthened with some references or examples. Currently, the argument appears somewhat speculative and lacks rigor. \n\n- The authors first present a weaker robustness result of $2 H_k + 6$ and provide its proof. Then, the authors present the improved result with a robustness guarantee of $2 H_k + 2$. What is the need to present two types of guarantees on robustness? \n\n- It would be useful to provide some discussion on the proof of Theorem 4.6. Specifically, how the proof differs from Theorem 4.5.\n\n- I believe the introduction could be strengthened by more clearly articulating the relevance and potential impact of the proposed algorithm and analysis for the machine learning community.", "was_revised": true, "final_justification": "I thank the authors for their response. My concerns have been adequately addressed. I will maintain my score.", "rebuttal": "Thank you for reviewing our paper. We appreciate your detailed evaluation of our work.\n\n**Weakness 1:**\n\nThe cost of OPT on sequence $\\sigma$, i.e., OPT($\\sigma$), is abbreviated as OPT by omitting $\\sigma$ for brevity, as mentioned in Section 2. However, based on your suggestion, we will restate this in Section 4 to make it clearer to the reader.\n\n**Weakness 2:**\n\nWe will revise Observation 2 to: \"Many switching-based methods, such as BlindOracle&LRU [7] and F&R [8], attempt to detect prediction errors during execution to decide when to switch between a prediction-based policy and a robust fallback strategy. A common method, as used by BlindOracle&LRU and BlindOracle&Marker [7], involves comparing the current total cost incurred by the prediction-based algorithm with that of the fallback algorithm. … Alternatively, some methods, such as F&R and F&R (FitF) [8], detect prediction errors by explicitly recomputing the optimal solution over the observed request sequence up to the point of a cache miss, and checking whether the optimal solution would also incur a miss. While this yields highly accurate error detection, its computational overhead is prohibitively high for real-time applications. The differences among prediction error detection strategies used in switching-based algorithms are discussed in detail in Appendix B (Design Principles).\"  \n  \nThis revision introduces additional examples of existing algorithms, explains their underlying mechanisms, and references the related discussion in Appendix B.\n\n**Weakness 3 and 4:**\n\nThe proof of Theorem 4.5 ($2H_k + 6$) is first presented under three assumptions to show the $O(\\log k)$-robustness, as it is concise, easy to understand, and largely follows the classical proof framework of the Mark algorithm. However, it is difficult to derive a tight robustness bound within this proof framework, as the required assumptions make the bound loose. Thus, we prove Theorem 4.6 ($2H_{k-1} + 2$) using a different technique (eviction graph) without relying on any assumptions, resulting in a tight bound. As suggested, we will include the above discussion to highlight the differences between the two proof methods and enhance clarity.\n\n**Weakness 5:**\n\nThanks for this suggestion. While this paper focuses specifically on learning-augmented algorithms, which sit at the intersection of machine learning and theoretical computer science, the caching problem itself is widespread across computer systems. Our work highlights the potential and effectiveness of machine learning in enhancing the performance of traditional caching algorithms in modern systems. The field of machine learning for systems has grown rapidly in recent years, leading to many emerging research challenges. This trend was highlighted by Google’s keynote at ASPLOS 2025, a top conference in computer systems, where various research opportunities were discussed, including ML for compilers, memory management, cluster scheduling and resource allocation, network routing, and other system-level applications.\n\nHowever, the lack of robustness guarantees remains a key barrier to applying machine learning models in real-world, risk-sensitive systems such as cloud infrastructures, thereby limiting their potential benefits. Another real-world challenge lies in achieving robustness efficiently, which is also a key focus of our paper. We believe the insights from our lightweight robustification framework may help guide the safer and more reliable application of machine learning in caching and other decision-making scenarios.\n\nBeyond caching, there are many other scenarios where robust performance guarantees are highly desirable. These include reliable resource provisioning under uncertain demand patterns through load forecasting in power grid management, and the use of robust Markov Decision Processes (MDPs) or reinforcement learning to ensure safe operation in autonomous systems and industrial control. Similar needs also arise in cloud autoscaling and financial trading under volatile conditions.\n    \nOverall, this line of work on learning-augmented algorithms, including ours, supports the deployment of machine learning models in real systems, further demonstrates the value of ML research, strengthens the impact of the ML community, and may lead to new research opportunities, such as developing system-oriented low-latency models and enabling the safer integration of ML into systems. Given the above, we will outline the key relevance and potential implications in the introduction."}, {"review_id": "7cDILrif1r", "reviewer": "Reviewer_tNoD", "summary": "The paper investigates the caching problem, where the objective is to store $k$ pages to minimize cache misses---a scenario where a requested page is not present in the cache. The authors specifically examines learning-augmented caching policies, which leverage predictions to guide decisions about page retention and eviction. A key aspect of these policies is their performance under varying prediction accuracy: a consistent policy performs as well as the best caching algorithm when predictions are perfect, while a robust policy guarantees a bounded competitive ratio against the optimal solution even when predictions are flawed. The paper's primary contribution is the proposed algorithm GUARD, which serves as a wrapper to enhance the robustness of any learning-augmented algorithm without compromising its consistency.", "questions": "* Could you clarify the necessity of the system model's constraint that a specific cache must always store the requested file? What benefits or challenges might arise if this constraint were more flexible?\n\n* How does the \"guard\" mechanism's complexity, which depends on the request sequence size (n), impact the practical scalability of your \"lightweight\" approach, especially with very large and frequent request sequences in real-world systems?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strengths.**\n\n* The paper does a good job of situating its contributions within the relevant literature, and the research gap it seeks to fill is clearly articulated. The individual contributions are presented in a logical and easily understandable manner, and the work itself appears to be comprehensive and technically solid.\n\n**Weaknesses.**\n\n* It's unclear why the system model necessitates a specific cache always storing the requested file. While this aligns with the operation of many caching policies (e.g., LRU, LFU), its inclusion as a general system model constraint lacks clear justification. Allowing for greater flexibility in this regard could potentially lead to even stronger comparative optimums.\n\n* The authors claim their approach is lightweight; however, the complexity of the \"guard\" mechanism appears to depend on the size of the request sequence (n). In real-world systems, where request sequences can be very large and frequent, it's not clear how this algorithm would remain practical.", "was_revised": true, "final_justification": "The authors satisfactorily addressed my concerns, leading me to raise my score from weak accept to accept.", "rebuttal": "Thank you for your review and your valuable feedback. Since the weaknesses correspond to the questions, we respond to them together in detail.\n\n**Weakness and Question 1 (part 1):**\n\nOverall, we use the current system model for two main reasons as follows.\n\nFirst, this model captures a wide range of real-world systems, many of which explicitly require that the requested page or data be cached immediately after access as a hard constraint. For example, in operating system virtual memory management, the OS must load the requested page into memory and cache it in the page table or physical memory upon a page fault. This is essential for memory correctness and helps avoid costly disk I/O on repeated accesses. Similarly, in database buffer management for the most popular class of relational databases, a page is cached in the buffer pool and pinned as soon as it is read, such as during a transaction, because it must remain resident to ensure consistency and support rollback. A modern example can be found in GPU caching for recommendation models or large language models, where a vector such as an embedding or a KV cache vector must be cached in GPU memory after being fetched from host DRAM to support efficient reuse in subsequent forward passes.\n\nSecond, since all existing learning-augmented caching algorithms, totaling more than 10 developed since 2018, use the current system model, we adopt the same model to ensure a fair performance comparison, as shown in Appendix B.\n\n**Weakness and Question 1 (part 2):**\n\nHowever, there are some scenarios where the requested item is typically cached after access, but this is not enforced as a hard constraint. Examples include applications such as web browsers, which cache page resources, and content delivery networks (CDNs), which store requested content at the edge. In these cases, there is an opportunity to relax this constraint, and we agree that doing so may improve caching performance.\n\n- **Benefits**: Without this constraint, the optimal algorithm can choose to skip storing the requested item if its next request time is later than that of all items currently in the cache. Essentially, this expands the eviction candidate set from $k$ to $k+1$, including the requested item as a candidate. This can reduce the optimal cost in certain cases, such as the following: suppose the cache initially contains $k$ items, $A_1$ to $A_k$. First, item $B_1$ is requested and will not be requested again. Next, items $A_1$ to $A_k$ are requested one by one. This two-step pattern is repeated for $n$ rounds, with $B_1, \\ldots, B_n$ being requested in sequence. In this case, the optimal algorithm incurs a cost of $2n$ if it is required to store each requested item, but only $n$ if storing is optional. While the above case is extreme, it shows the potential benefits of relaxing the constraint. Similarly, learning-augmented algorithms may also benefit, particularly when the predictor is highly accurate.\n\n- **Challenges**: Incorporating this flexibility requires only minor modifications to existing learning-augmented algorithms, leaving their core structure unchanged. For example, in the case of Guard, we can forgo storing the requested item if its eviction priority (e.g., predicted next request time) is higher than that of all cached items. This modification can also be applied to other learning-augmented algorithms, making them easily adaptable to the new system model.\n\n    Therefore, adopting a more flexible system model may not pose significant challenges. The key challenge in this setting is ensuring that the algorithm avoids cases where frequently requested items are consistently not stored due to inaccurate predictions, leading to significant cost. We will outline the discussion of the new system model in the conclusion section.\n\n**Weakness 2 and Question 2:**\n\nAlgorithm 1 presents the application of the *guard* mechanism to serve a sequence of $n$ requests. The mechanism introduces a total time complexity of $O(n)$ after serving $n$ requests, resulting in an amortized cost of $O(1)$ per request. This matches the overall overhead of classical caching algorithms such as LRU and LFU, which update the last access time or item frequency per request, also incurring a total cost of $O(n)$. In general, to robustify an online learning-augmented algorithm, the additional overhead mentioned above is inevitable. Existing learning-augmented mechanisms all incur at least additional $O(n)$ overhead over $n$ requests. For example, switching between algorithms in BlindOracle\\&LRU incurs an $O(n)$ overhead, while the customized mechanism in F\\&R incurs an $O(n^2)$ overhead after serving $n$ requests.\n\nBelow, we list the time cost associated with each relevant line in Algorithm 1 when implemented in real-world systems.\n\n- (1) Upon receiving a request $r_i$ (Line 3), if the page is already in the cache, we set its *requested* tag of this page (Lines 23, 24), and decrease the number of unrequested old pages by 1, both in $O(1)$ time. If a cache miss occurs and the cache is full (Line 5), we check whether the number of unrequested old pages is zero (Line 6), also in $O(1)$ time. If so, a new phase begins: we remove the *guard* tag and *requested* tag of all cached pages (Line 7-8), which costs $O(k)$ in total, amortized to $O(1)$ per request.\n\n- (2) When a prediction error is detected (Line 10) via a hash table lookup, we add the *guard* tag to the requested page (Line 12), which costs $O(1)$. To perform random eviction from the set $U$ (Line 11), we use a temporary array of cache indices, i.e., $1, \\ldots, k$, and randomly shuffle their order at the beginning of each new phase at a cost of $O(k)$, amortized to $O(1)$ per request. When a random eviction is needed, we scan the pages using shuffled indices and select the first one whose *requested* tag is unset. The next random eviction starts from the last page found and moves forward. This results in a worst-case cost of $O(k)$ per phase, amortized to $O(1)$ per request.\n\n- (3) In Line 14, pages with the \n*guard* tags are excluded from prediction. The complexity of the algorithm A's policy (Line 15) is independent of the *guard* mechanism.\n\nAfter being robustified by Guard, the new algorithms, including Guard\\&B.O., Guard\\&LRB, and Guard\\&PA., achieve state-of-the-art asymptotic time complexity among learning augmented algorithms that use different types of predictions, as summarized in Table 4 of Appendix B.\n\nOverall, the *guard* mechanism maintains very low additional time complexity, asymptotically matching the time complexity of classical algorithms. In most scenarios, the overhead of classic caching algorithms like LRU is generally negligible compared to I/O or network latency, thereby ensuring practical scalability of Guard in real-world systems with large and frequent request streams.\n\nWe hope this response addresses your concern and would be happy to engage in further discussion."}, {"review_id": "CBrU3p77rn", "reviewer": "Reviewer_KGyM", "summary": "The paper studies the online paging problem in the learning-augmented setting. It provides a framework that, given a consistent learning-augmented algorithm following a relaxed version of Belady's rule, maintains consistency while improving robustness to $2H_k+2$. That is, the final algorithm performs optimally for perfect predictions, and in the worst case, its cost is at most $2H_k+2$  times more than the optimal cost. The authors also perform extensive experiments to empirically compare the proposed algorithms with the baselines.", "questions": "N/A", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "1. Unlike the common approach in the framework of algorithms with predictions, which focuses on predicting the input, this work starts with a learning-augmented algorithm with specific properties and robustifies it without losing consistency. This is an interesting approach and may have applications in other problems studied in the learning-augmented setting.\n\n2. They achieve a state-of-the-art consistency-robustness tradeoff.\n\n3. The proposed robustification technique is simple, lightweight, and introduces minimal computational overhead, making it practical for real-world deployment.\n\n4. The authors conduct comprehensive experiments that demonstrate performance improvements over existing baselines.\n\n5. The paper is well-written and well-organized, making the technical content accessible and easy to follow. In particular, the detailed comparison with recent learning-augmented caching algorithms is helpful.", "was_revised": true, "final_justification": "The concerns raised by the reviewers appear to have been addressed by the authors. I will keep my original rating.", "rebuttal": "Thank you very much for the review and for acknowledging our work.\n\nWe are encouraged that our proposed robustification approach may be applicable to other problems, and that the comparison of existing learning-augmented caching algorithms is helpful. We hope this work can inspire and benefit other researchers in the community, help advance research at the intersection of machine learning, theoretical computer science, and computer systems, and support the application of machine learning in real-world systems efficiently and robustly. Any further suggestions are welcome."}, {"review_id": "ITJ4YpO6HR", "reviewer": "Reviewer_Dovr", "summary": "This paper addresses the online caching problem, focusing on minimizing cache misses under limited cache size. While existing learning-augmented caching algorithms achieve ideal 1-consistency, they often lack robustness guarantees. To tackle this, the authors propose GUARD, a lightweight robustification framework that significantly improves robustness to  2Hk+2 without sacrificing 1-consistency. GUARD maintains the original algorithm’s time complexity by adding only a constant per-request overhead. Extensive experiments on various real-world datasets and prediction models demonstrate the practical effectiveness of GUARD.", "questions": "see weakness", "limitations": "No", "rating": 4, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1. The paper provides thorough and rigorous theoretical analysis\n2. The writing is clear and well-structured.\n3. This work is well-motivated.\n\nWeaknesses:\n\n1. The experiments could include more ablation studies to isolate the effects of different components of GUARD.\n2. It is unclear how GUARD performs under extreme or adversarial conditions that may arise in some practical caching scenarios.\n3. The paper could provide more detailed discussion on the potential limitations or failure cases of the method.", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments and your support for our paper.\n\n**Weakness 1:**\n\nGuard has two main components at its core: protecting certain pages (Line 12 in Algorithm 1) and randomly evicting an unrequested old page (Line 11 in Algorithm 1) when a prediction error is detected (Line 10). We have conducted ablation experiments using variants of Guard that exclude random eviction or page protection. The table below extends the results of Table 7 in Appendix N.2, presenting average cost ratios across 13 SPEC CPU2006 benchmark datasets. The results indicate that both components are beneficial, with protection having a greater impact.\n\n| Predictor | LRU | Marker | B.O. | LM. | LNonM. | P.M. | B.O.\\&M.^D | F\\&R | Guard | Guard (without random eviction) | Guard (without protection) |\n|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|\n| PLECO  | 1.478  | 1.394  | 1.404 | 1.335  | 1.345  | 1.335 | 1.294 | 1.362 | 1.226  | 1.234  | 1.335 |\n| POPU   | 1.478  | 1.394  | 1.261 | 1.319  | 1.312 |  1.312 | 1.231 | 1.319 | 1.203  | 1.207 |  1.320 |\n\n\n**Weakness 2:**\n\nFor learning-augmented algorithms, adversarial conditions include adversarial inputs to online problems (in our caching problem, the request sequence/trace) and adversarial predictions (extremely inaccurate predictions) in the learning-augmented setting.\n\nTheoretically, we have established the theoretical robustness of Guard, which directly corresponds to its worst-case performance bound under both adversarial traces and predictions. Its cost is at most $2H\\_k + 2$ times that of the optimal.\n\nEmpirically, it is challenging to reproduce both adversarial conditions for Guard or other existing learning-augmented algorithms, as real-world traces rarely exhibit truly adversarial behavior. As a result, previous work in this field, including the milestone work [1], often simulates only adversarial predictions in experiments. Similarly, in Section 5.2, we used synthetic predictors to evaluate the algorithms under varying levels of prediction error on a real-world dataset, BrightKite, and demonstrated that Guard performs robustly in these scenarios.\n\n[1] Thodoris Lykouris and Sergei Vassilvtiskii. Competitive caching with machine learned advice. Proceedings of the 35th International Conference on Machine Learning, 2018.\n\n**Weakness 3:**\n\nThanks for pointing this out. Our framework is tailored to the standard paging problem, where all items have equal size and cost, and thus does not directly apply to more general settings like weighted or variable-sized caching. Like most learning-augmented caching algorithms, Guard also relies on high-performance predictors to be practical in low-latency systems, which makes reducing predictor usage important. As shown in the additional appendix (Appendix Q) provided in the supplementary material, Guard already reduces predictor usage compared to prior methods. Nonetheless, we believe that exploring the lower bound of predictor usage while maintaining strong performance would be an interesting direction for future work. We will add more discussion on limitations and future directions."}]

Author rebuttal:

Meta-review: This work in the learning-augmented algorithms realm proposes a new method for improving the robustness of other learning augmented  caching algorithms by limiting the set of pages that can be evicted and sometimes overriding the algorithm's decisions. The reviewers agreed on the novelty, and appreciated the additional empirical experiments.
Decision: Accept (poster)