mlsanityData to 13 Oct 2026

Algorithms for Caching and MTS with reduced number of predictions

arXiv 2404.06280 ↗First posted 9 Apr 2024cs.LG cs.DScited by 12

Not on the map. Why?

Abstract (arXiv)

ML-augmented algorithms utilize predictions to achieve performance beyond their worst-case bounds. Producing these predictions might be a costly operation -- this motivated Im et al. '22 to introduce the study of algorithms which use predictions parsimoniously. We design parsimonious algorithms for caching and MTS with action predictions, proposed by Antoniadis et al. '20, focusing on the parameters of consistency (performance with perfect predictions) and smoothness (dependence of their performance on the prediction error). Our algorithm for caching is 1-consistent, robust, and its smoothness deteriorates with the decreasing number of available predictions. We propose an algorithm for general MTS whose consistency and smoothness both scale linearly with the decreasing number of predictions. Without the restriction on the number of available predictions, both algorithms match the earlier guarantees achieved by Antoniadis et al. '20.

Key facts. Cited by 12 papers in the map (data through 13 Oct 2026). Builds on 32 of its 55 references that are in the map. First posted on arXiv 9 Apr 2024.

Builds on

32 of 55 references.

References · 32

  1. 2018Competitive caching with machine learned advicecited by 194
  2. 2017The Case for Learned Index Structurescited by 188
  3. 2020Algorithms with Predictionscited by 152
  4. 2020Online metric algorithms with untrusted predictionscited by 74
  5. 2019Near-Optimal Bounds for Online Caching with Machine Learned Advicecited by 73
  6. 2020Secretary and Online Matching Problems with Machine Learned Advicecited by 71
  7. 2021Faster Matchings via Learned Dualscited by 56
  8. 2022Faster Fundamental Graph Algorithms via Learned Predictionscited by 42
  9. 2020Secretaries with Advicecited by 41
  10. 2020Better and Simpler Learning-Augmented Online Cachingcited by 38
  11. 2020Learning Augmented Energy Minimization via Speed Scalingcited by 38
  12. 2020Online Algorithms for Weighted Paging with Predictionscited by 29
20 more
  1. 2021Flow Time Scheduling with Uncertain Processing Timecited by 29
  2. 2021Learning-Augmented k-means Clusteringcited by 26
  3. 2020An Imitation Learning Approach for Cache Replacementcited by 24
  4. 2022Permutation Predictions for Non-Clairvoyant Schedulingcited by 22
  5. 2021Learning-Augmented Dynamic Power Management with Multiple States via New Ski Rental Boundscited by 20
  6. 2022Parsimonious Learning-Augmented Cachingcited by 19
  7. 2020Learning-Augmented Weighted Pagingcited by 17
  8. 2021A Novel Prediction Setup for Online Speed-Scalingcited by 17
  9. 2022Discrete-Convex-Analysis-Based Framework for Warm-Starting Algorithms with Predictionscited by 16
  10. 2021Distortion-Oblivious Algorithms for Minimizing Flow Timecited by 15
  11. 2020Data-driven Competitive Algorithms for Online Knapsack and Set Covercited by 14
  12. 2022A Universal Error Measure for Input Predictions Applied to Online Graph Problemscited by 14
  13. 2021Robust Learning-Augmented Caching: An Experimental Studycited by 12
  14. 2018Metrical task systems on trees via mirror descent and unfair gluingcited by 11
  15. 2022Learning-Augmented Maximum Flowcited by 11
  16. 2021Double Coverage with Machine-Learned Advicecited by 10
  17. 2021Robustification of Online Graph Exploration Methodscited by 10
  18. 2020Online Page Migration with ML Advicecited by 8
  19. 2024Learning-Augmented Algorithms with Explicit Predictorscited by 8
  20. 2022Online Unit Profit Knapsack with Untrusted Predictionscited by 4

Built on by

Cited by year (2026 to 13 Oct)

Citing papers per year: 2024: 4; 2025: 3; 2026: 5.

12 papers.

  1. 2024Learning-augmented Maximum Independent Setcited by 11
  2. 2024Efficient LLM Inference using Dynamic Input Pruning and Cache-Aware Maskingcited by 11
  3. 2024Non-clairvoyant Scheduling with Partial Predictionscited by 7
  4. 2024Learning-Augmented Priority Queuescited by 7
  5. 2025Robustifying Learning-Augmented Caching Efficiently without Compromising 1-Consistencycited by 3
  6. 2025Toward Robust and Efficient ML-Based GPU Caching for Modern Inferencecited by 3
  7. 2025Learning-Augmented Algorithms for MTS with Bandit Access to Multiple Predictorscited by 2
  8. 2026Parsimonious Learning-Augmented Online Metric Matchingcited by 1
  9. 2026Learning-Augmented Online Minimization with Dual Predictionscited by 1
  10. 2026Towards Optimal Robustness in Learning-Augmented Pagingcited by 0
  11. 2026Learning-Augmented Algorithms: Guarantees, Construction Mechanisms, and System-Level Implicationscited by 0
  12. 2026Compressing Value Predictions for Learning-Augmented Metrical Task Systemscited by 0