Robustifying Learning-Augmented Caching Efficiently without Compromising 1-Consistency

Thank you for your comments and your support for our paper.

Weakness 1:

Guard 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.

Weakness 2:

For 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.

Theoretically, 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.

Empirically, 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.

[1] Thodoris Lykouris and Sergei Vassilvtiskii. Competitive caching with machine learned advice. Proceedings of the 35th International Conference on Machine Learning, 2018.

Weakness 3:

Thanks 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.

Thank you for your review and your valuable feedback. Since the weaknesses correspond to the questions, we respond to them together in detail.

Weakness and Question 1 (part 1):

Overall, we use the current system model for two main reasons as follows.

First, 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.

Second, 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.

Weakness and Question 1 (part 2):

However, 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.

• 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.

• 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.

  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.

Weakness 2 and Question 2:

Algorithm 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.

Below, we list the time cost associated with each relevant line in Algorithm 1 when implemented in real-world systems.

• (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.

• (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.

• (3) In Line 14, pages with the guard tags are excluded from prediction. The complexity of the algorithm A's policy (Line 15) is independent of the guard mechanism.

After 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.

Overall, 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.

We hope this response addresses your concern and would be happy to engage in further discussion.

Thank you very much for the review and for acknowledging our work.

We 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.

Thank you for reviewing our paper. We appreciate your detailed evaluation of our work.

Weakness 1:

The 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.

Weakness 2:

We 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)."

This revision introduces additional examples of existing algorithms, explains their underlying mechanisms, and references the related discussion in Appendix B.

Weakness 3 and 4:

The 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.

Weakness 5:

Thanks 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.

However, 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.

Beyond 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.

Overall, 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.