Research map / Bandits and online learning / Online convex optimization and games
Algorithms for Caching and MTS with reduced number of predictions
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.
Designs parsimonious learning-augmented algorithms for caching and metrical task systems (MTS) that use action predictions with a bounded number of predictor queries or queries separated by at least a steps, achieving 1-consistency for caching and linear-in-a consistency/smoothness for MTS.
Problem
Learning-augmented online algorithms for caching and MTS usually query an expensive predictor at every step; the paper asks how consistency and smoothness degrade when the number of predictions (or the query frequency) is restricted.
Approach
A caching algorithm (FR) that follows Belady-action predictions while they remain correct and switches to a robust marking-based procedure with windows and a convex budget function f that governs how many predictions are requested per phase; for MTS, a work-function based FtSP algorithm that uses one prediction every a steps.
Key results
- The caching algorithm is 1-consistent and O(log k)-robust, with smoothness O(f^{-1}(eta/OPT)) using O(f(log k))OPT predictions; with O(sqrt(k))OPT predictions it matches the O(1+log(eta/OPT+1)) smoothness of prior work that queries every step.
- A lower bound shows any f(eta)-smooth caching algorithm must use at least f(ln k)OPT predictions, and with 0.5 OPT predictions no algorithm beats O(log k) competitiveness.
- For MTS with one prediction every a steps, the FtSP algorithm achieves cost O(a)(OFF + 2eta), improving smoothness from 1+4eta/OFF to 1+2eta/OFF for a=1.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use action predictions with FR instead of unlimited prediction queries | FR for caching · Caching | consistency | Helped |
| Use f(i)=2^i-1 instead of unrestricted prediction queries | FR for caching · Caching | number of predictions: O(\sqrt{k}) \OPT | Helped |
| Use f(i)=i^2 (ablation) | FR for caching · Caching | smoothness: O(\log^2 k) \OPT; O(\sqrt{2\frac\eta\OPT}) | Mixed |
| Use f(i)=i (ablation) | FR for caching · Caching | smoothness: O(\log k) \OPT; O(\frac\eta\OPT) | Mixed |
| Use f(i)=0 (ablation) | FR for caching · Caching | smoothness: 2\OPT; O(\frac{k\eta}{\OPT}) | Hurt |
| Limit queries to once every a time steps | FtSP for MTS · MTS | cost: O(a) \cdot (\OFF + 2\eta) | Hurt |
| Use FtSP work-function selection rather than the cited MTS method | MTS with action predictions · MTS, a=1 | smoothness: 1+4\eta/\OFF -> 1+2\eta/\OFF | Helped |
| Separate caching prediction queries by at least a time steps | FR for caching · Caching | smoothness: O( f^{-1}(\eta/\OPT)) -> O( f^{-1}(a\eta/\OPT)) | Hurt |
| Use a=2-separated queries instead of a=1 on BrightKite | FR · BrightKite | competitive ratio | Hurt |
| Use a=2 or a=3 instead of a=1 with σ > 20 | FR · BrightKite, synthetic predictor | number of predictions | Hurt |
| Use a=20-separated queries rather than unrestricted query timing | FR · CitiBike, k=100 | competitive ratio | No clear effect |
| Use fewer predictions with the PLECO predictor | FR · CitiBike and BrightKite | competitive ratio | No clear effect |
Surprising findings
- With f(i)=0 the caching algorithm asks for at most 2OPT predictions and remains 1-consistent, though its smoothness is poor.
Limitations
- For MTS the number of predictions cannot be bounded as a function of OPT, since scaling the instance changes OPT.
- Consistency for MTS with one query per a steps is O(a), and smoothness loses a factor a; the robust variant loses (1+epsilon).
- Caching algorithm is not 1-consistent with well-separated queries; consistency becomes O(1).
Experimental setup
Datasets: BrightKite check-in dataset CitiBike trip dataset
Benchmarks: BrightKite caching instances (k=10) CitiBike caching instances (k=100)
Metrics: competitive ratio number of predictor queries smoothness vs prediction error
Baselines: FtP T&D FtPM AQ L&V LMark LnonMark LRU Marker
Builds on: Belady's algorithm Im et al. 2022 parsimonious predictions Antoniadis et al. 2023 action predictions Marker algorithm work function algorithms
Closest papers by meaning
- Robustifying Learning-Augmented Caching Efficiently without Compromising 1-Consistency (NeurIPS 2025 · similarity 0.88)
- Parameterized Complexity of Caching in Networks (AAAI 2025 · similarity 0.85)
- Learning-Augmented Algorithms with Explicit Predictors (NeurIPS 2024 · similarity 0.84)
- Algorithms with Calibrated Machine Learning Predictions (ICML 2025 · similarity 0.83)
- Non-clairvoyant Scheduling with Partial Predictions (ICML 2024 · similarity 0.83)
- EPIC: Efficient Position-Independent Caching for Serving Large Language Models (ICML 2025 · similarity 0.83)
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.