mlsanityData to 7 Oct 2026

Learning-Augmented Algorithms: Guarantees, Construction Mechanisms, and System-Level Implications

arXiv 2609.04787 ↗First posted 4 Sep 2026cs.LG cs.DScited by 0

Not on the map. Why?

Abstract (arXiv)

Learning-augmented algorithms use fallible predictions while retaining formal performance guarantees. This survey synthesizes prediction interfaces, error measures, consistency--robustness trade-offs, and five representative construction mechanisms across online optimization, caching, learned data structures, graph problems, and mechanism design. An orthogonal theorem-level axis distinguishes achieved upper bounds from matched asymptotic dependence. Formal guarantees are separated from empirical systems evidence, with explicit treatment of prediction cost, feedback, and composition. The resulting synthesis states sufficient conditions for limited end-to-end reasoning and delineates open problems in cost-aware prediction, endogenous error, semantic predictors, and benchmarking.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 67 of its 105 references that are in the map. First posted on arXiv 4 Sep 2026.

Builds on

67 of 105 references.

References · 67

  1. 2023Not what you've signed up for: Compromising Real-World LLM-Integrated Applications with Indirect Prompt Injectioncited by 1,339
  2. 2020Performative Predictioncited by 318
  3. 2015Strategic Classificationcited by 256
  4. 2018Competitive caching with machine learned advicecited by 194
  5. 2017The Case for Learned Index Structurescited by 188
  6. 2020Algorithms with Predictionscited by 152
  7. 2018Learning Scheduling Algorithms for Data Processing Clusterscited by 133
  8. 2020The Primal-Dual method for Learning Augmented Algorithmscited by 78
  9. 2019Near-Optimal Bounds for Online Caching with Machine Learned Advicecited by 73
  10. 2024Improving Online Algorithms via ML Predictionscited by 65
  11. 2019A Model for Learned Bloom Filters, and Optimizing by Sandwichingcited by 64
  12. 2020Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithmscited by 64
38 more
  1. 2020Bao: Learning to Steer Query Optimizerscited by 62
  2. 2021Faster Matchings via Learned Dualscited by 56
  3. 2019End to end learning and optimization on graphscited by 44
  4. 2019ALEX: An Updatable Adaptive Learned Indexcited by 43
  5. 2020Secretaries with Advicecited by 41
  6. 2020Better and Simpler Learning-Augmented Online Cachingcited by 38
  7. 2020Learning Augmented Energy Minimization via Speed Scalingcited by 38
  8. 2020Online Learning with Imperfect Hintscited by 37
  9. 2018FITing-Tree: A Data-aware Index Structurecited by 30
  10. 2020Online Algorithms for Weighted Paging with Predictionscited by 29
  11. 2021Flow Time Scheduling with Uncertain Processing Timecited by 29
  12. 2020Learnable and Instance-Robust Predictions for Online Matching, Flows and Load Balancingcited by 27
  13. 2022Learning Predictions for Algorithms with Predictionscited by 25
  14. 2020An Imitation Learning Approach for Cache Replacementcited by 24
  15. 2015Route Planning in Transportation Networkscited by 22
  16. 2017Revenue Optimization with Approximate Bid Predictionscited by 21
  17. 2021Learning-Augmented Dynamic Power Management with Multiple States via New Ski Rental Boundscited by 20
  18. 2023Predictive Flows for Faster Ford-Fulkersoncited by 20
  19. 2020Are We Ready For Learned Cardinality Estimation?cited by 19
  20. 2022Learning-Augmented Mechanism Design: Leveraging Predictions for Facility Locationcited by 19
  21. 2025A Survey of AIOps in the Era of Large Language Modelscited by 18
  22. 2022Discrete-Convex-Analysis-Based Framework for Warm-Starting Algorithms with Predictionscited by 16
  23. 2021Distortion-Oblivious Algorithms for Minimizing Flow Timecited by 15
  24. 2024Online bipartite matching with imperfect advicecited by 13
  25. 2021Robust Learning-Augmented Caching: An Experimental Studycited by 12
  26. 2023Mixing predictions for online metric algorithmscited by 12
  27. 2024Algorithms for Caching and MTS with reduced number of predictionscited by 12
  28. 2024Binary Search with Distributional Predictionscited by 11
  29. 2023Online Algorithms with Uncertainty-Quantified Predictionscited by 9
  30. 2024Learning-Augmented Algorithms with Explicit Predictorscited by 8
  31. 2024Contract Scheduling with Distributional and Multiple Advicecited by 8
  32. 2024Overcoming Brittleness in Pareto-Optimal Learning-Augmented Algorithmscited by 8
  33. 2025Learning-Augmented Online Bipartite Fractional Matchingcited by 8
  34. 2024Learning-Augmented Algorithms for the Bahncard Problemcited by 7
  35. 2025On Tradeoffs in Learning-Augmented Algorithmscited by 7
  36. 2021Learning-Augmented Algorithms for Online Steiner Treecited by 6
  37. 2023Speed-Oblivious Online Scheduling: Knowing (Precise) Speeds is not Necessarycited by 5
  38. 2023Bicriteria Multidimensional Mechanism Design with Side Informationcited by 4

50 most cited of 67 All 67 (JSON)

Built on by

Not cited yet.