Research map / Bandits and online learning / Online convex optimization and games
Robustifying Learning-Augmented Caching Efficiently without Compromising 1-Consistency
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces Guard, a lightweight phase-based robustification wrapper for 1-consistent RB-following learning-augmented caching algorithms that achieves 1-consistency and (2H_{k-1}+2)-robustness with O(1) per-request overhead.
Problem
Learning-augmented caching algorithms that are 1-consistent (e.g., BlindOracle, LRB, Parrot) are not robust to prediction errors, while existing robustification methods either lose 1-consistency or have prohibitive computational overhead.
Approach
A phase-based guarding mechanism that protects a requested page only when a misprediction is detected (the requested page was already evicted in the current phase), using the causal eviction-chain pattern of optimal algorithms, rather than immediate marking or recomputing OPT.
Key results
- Guard achieves 1-consistency and (2H_{k-1}+2)-robustness, the best known trade-off, with O(1) extra per-request overhead.
- On SPEC CPU2006 with PLECO predictor, Guard&B.O. achieves average cost ratio 1.226 vs 1.335 for LMarker and 1.360 for F&R.
- On SPEC CPU2006 with LRB predictor, Guard&LRB achieves 1.171 vs 1.281 for LRB and 1.268 for Mark0.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Apply Guard to BlindOracle | BlindOracle · SPEC CPU2006 with PLECO predictions | average cost ratio: 1.404 -> 1.226 | Helped |
| Apply Guard to BlindOracle | BlindOracle · SPEC CPU2006 with POPU predictions | average cost ratio: 1.261 -> 1.203 | Helped |
| Apply Guard to LRB | LRB · SPEC CPU2006 with LRB predictor | average cost ratio: 1.281 -> 1.171 | Helped |
| Add Guard robustification | BlindOracle · Caching with arbitrary prediction errors | robustness: ∞ -> 2H_{k-1} + 2 | Helped |
| Add Guard robustification | LRB · Caching with arbitrary prediction errors | robustness: ∞ -> 2H_{k-1} + 2 | Helped |
| Add Guard robustification | Parrot · Caching with arbitrary prediction errors | robustness: ∞ -> 2H_{k-1} + 2 | Helped |
Limitations
- Applies only to RB-following 1-consistent algorithms; more sophisticated RB-following algorithms are left for future work.
- Robustness bound is worst-case; empirical gains are reported on a limited set of datasets and predictors.
- Smoothness of Guard&B.O. is O(log(eta/OPT)), while ExGuard trades predictor calls for smoothness.
Experimental setup
Datasets: BrightKite Citi SPEC CPU2006 memory traces
Benchmarks: BrightKite Citi SPEC CPU2006
Metrics: cache miss cost ratio relative to OPT competitive ratio
Baselines: BlindOracle&LRU BlindOracle&Marker F&R PredictiveMarker LMarker LNonMarker Mark0 Mark&Predict LRU Marker LRB
Builds on: BlindOracle LRB Parrot Marker F&R
Closest papers by meaning
- Algorithms for Caching and MTS with reduced number of predictions (ICLR 2024 · similarity 0.88)
- LaCache: Robust Semantic Caching for LLM Serving (NeurIPS 2026 · similarity 0.86)
- Randomization Boosts KV Caching, Learning Balances Query Load: A Joint Perspective (ICLR 2026 · similarity 0.86)
- Parameterized Complexity of Caching in Networks (AAAI 2025 · similarity 0.85)
- Taming the Fragility of KV Cache Eviction in LLM Inference (ICLR 2026 · similarity 0.85)
- Value-Aware Stochastic KV Cache Eviction for Reasoning Models (NeurIPS 2026 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.