pith. sign in

arxiv: 2602.20706 · v2 · pith:BGXMUUPBnew · submitted 2026-02-24 · 💻 cs.AI · cs.DS

Online Algorithms with Unreliable Guidance

Julien Dallot , Yuval Emek , Yuval Gil , Maciej Pacut , Stefan Schmid This is my paper

Pith reviewed 2026-05-21 13:14 UTC · model grok-4.3

classification 💻 cs.AI cs.DS
keywords online algorithmslearning-augmented algorithmsunreliable guidancebipartite matchingcachingmetrical task systemsconsistency-robustnesscompiler
0
0 comments X

The pith

A new model separates unreliable guidance from online decisions, allowing a simple compiler to produce prediction-aware algorithms with performance guarantees.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper establishes a framework for online algorithms with unreliable guidance that cleanly separates the predictive and algorithmic components in online decision-making. This separation allows for a generic compiler that converts any standard online algorithm into one that can use predictions when they are reliable and ignore them otherwise. The approach yields new trade-offs for bipartite matching under adversarial arrivals and optimal solutions for caching and uniform metrical task systems. A sympathetic reader would care because it provides a unified analysis method independent of specific prediction formats or error measures.

Core claim

The OAG model, formulated through request-answer games, introduces concepts such as predictions from the answer space, a guide, and anytime competitiveness. These enable the drop-or-trust-blindly compiler to turn almost any standard online algorithm into a learning-augmented one with strong consistency-robustness guarantees for bipartite matching, caching, and uniform metrical task systems.

What carries the argument

The drop-or-trust-blindly (DTB) compiler, which decides whether to drop or trust the guidance in order to convert standard online algorithms into learning-augmented versions.

If this is right

  • New trade-offs for bipartite matching with adversarial arrival order.
  • Optimal solutions for the caching problem.
  • Optimal solutions for uniform metrical task systems.
  • Analysis that depends only on the problem at hand and stays independent of predictor semantics or error functions.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same compiler structure could be applied to other online problems not covered in the three examples.
  • The separation might make it easier to swap in different predictors without redoing the entire analysis.
  • Algorithms produced this way could be tested on inputs where prediction quality changes over time.

Load-bearing premise

That guidance can be treated as a separate unreliable signal whose quality does not interfere with the underlying analysis of the online algorithm.

What would settle it

Showing that the DTB compiler fails to meet the stated consistency-robustness trade-off on one of the three problems when predictions are always perfect or always wrong.

read the original abstract

This paper introduces online algorithms with unreliable guidance (OAG), a model for ML-augmented online decision-making that cleanly separates the predictive and algorithmic components, thus offering a single, well-defined analysis framework that depends only on the problem at hand. Formulated through the lens of request-answer games, the OAG model brings multiple concepts (predictions from the answer space, guide, anytime competitiveness) which enable learning-augmented algorithms to be analyzed independently of predictor-specific choices - such as prediction semantics, error functions, or probing strategies - that would otherwise restrict the algorithm's generality and applicability. The clean framework of the OAG model allows to build the first generic compiler, the drop-or-trust-blindly (DTB) compiler, that turns almost any standard, prediction-free online algorithm into a learning-augmented one. Although simple, we show that the DTB compiler produces new learning-augmented algorithms with strong consistency-robustness guarantees for three classic online problems: we achieve new trade-offs for bipartite matching with adversarial arrival order, and obtain optimal solutions for caching and uniform metrical task systems.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 1 minor

Summary. The paper introduces the Online Algorithms with Unreliable Guidance (OAG) model, formulated via request-answer games, which separates predictive and algorithmic components to enable analysis independent of specific predictor choices such as semantics or error functions. It presents the Drop-or-Trust-Blindly (DTB) compiler as a black-box wrapper that converts standard prediction-free online algorithms into learning-augmented ones, and applies it to obtain new consistency-robustness trade-offs for bipartite matching under adversarial arrival order as well as optimal solutions for caching and uniform metrical task systems.

Significance. If the central claims hold, the OAG framework and DTB compiler would provide a generic, problem-centric approach to incorporating unreliable guidance into online algorithms, unifying analysis across domains and yielding predictor-agnostic guarantees. The optimality results for caching and uniform MTS would be particularly notable advances in the learning-augmented online algorithms literature.

major comments (1)
  1. [Section 4, Theorems 4.3 and 5.1] Section 4, Theorems 4.3 and 5.1: The robustness analysis employs a threshold comparing the guide's answer to the algorithm's current state to decide drop/trust. This presupposes a concrete error metric (additive, multiplicative, or distance-based) in the answer space. Changing the metric can flip the decision for the same prediction quality, altering the resulting competitive ratio and contradicting the abstract's claim that the framework and analysis depend only on the problem and are independent of predictor-specific error functions.
minor comments (1)
  1. [Section 3] The definition of 'anytime competitiveness' is introduced in Section 3 but could be stated more formally with explicit notation for the request-answer game before the DTB construction.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for recognizing the potential of the OAG model and DTB compiler to provide a generic, problem-centric approach to learning-augmented online algorithms. We address the single major comment below.

read point-by-point responses

  1. Referee: Section 4, Theorems 4.3 and 5.1: The robustness analysis employs a threshold comparing the guide's answer to the algorithm's current state to decide drop/trust. This presupposes a concrete error metric (additive, multiplicative, or distance-based) in the answer space. Changing the metric can flip the decision for the same prediction quality, altering the resulting competitive ratio and contradicting the abstract's claim that the framework and analysis depend only on the problem and are independent of predictor-specific error functions.

    Authors: We thank the referee for this observation. We respectfully maintain that the analysis does not presuppose a predictor-specific error metric. In the OAG model, formulated via request-answer games, the guide outputs elements directly from the problem's answer space; consistency is defined strictly as the fraction of requests on which the guide's answer coincides with an optimal offline choice for that request. The DTB compiler's drop/trust threshold compares the guide's answer against the algorithm's current state using only the problem's native cost structure and transition rules (for example, the matching cost in bipartite matching or the eviction cost in caching). This comparison is therefore part of the problem definition itself and does not invoke any external distance function, additive/multiplicative error, or training loss that a particular predictor might employ. Robustness is established via a worst-case argument over all sequences in which the guide may be incorrect, again without reference to any predictor-chosen metric. Consequently, the consistency-robustness trade-offs depend solely on the underlying online problem, as stated in the abstract. The results in Theorems 4.3 and 5.1 remain valid under this interpretation. revision: no

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper introduces the OAG model via request-answer games and concepts like guide and anytime competitiveness, then presents the DTB compiler as a black-box wrapper on standard online algorithms. Central claims about new trade-offs for bipartite matching and optimal solutions for caching and uniform MTS derive from the framework definitions and problem-specific analysis without reducing by construction to fitted inputs, self-definitions, or self-citation chains. No load-bearing step equates a prediction or result to its own inputs via the paper's equations or prior author work; the separation of predictive and algorithmic components is asserted as a modeling choice rather than derived circularly. This is the most common honest finding for framework papers that remain self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 2 invented entities

Only the abstract is available for review, so the complete set of free parameters, axioms, and invented entities cannot be exhaustively identified. The paper introduces new modeling concepts and a compiler on top of standard online algorithm frameworks.

axioms (1)
  • standard math Request-answer games provide a suitable lens for formulating online decision-making with guidance
    The OAG model is formulated through the lens of request-answer games.
invented entities (2)
  • OAG model no independent evidence
    purpose: To separate predictive and algorithmic components for general analysis
    New model introduced to enable predictor-independent analysis of learning-augmented algorithms.
  • DTB compiler no independent evidence
    purpose: To convert standard online algorithms into learning-augmented versions with consistency-robustness guarantees
    Generic compiler proposed that turns almost any prediction-free online algorithm into a learning-augmented one.

pith-pipeline@v0.9.0 · 5726 in / 1534 out tokens · 72982 ms · 2026-05-21T13:14:09.513338+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

16 extracted references · 16 canonical work pages

  1. [1]

    Chen, and Piotr Indyk

    1 Anders Aamand, Justin Y. Chen, and Piotr Indyk. (optimal) online bipartite matching with degree information. InAdvances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28 - December 9, 2022,

    work page 2022

  2. [2]

    Secretary and online matching problems with machine learned advice

    4 Antonios Antoniadis, Themis Gouleakis, Pieter Kleer, and Pavel Kolev. Secretary and online matching problems with machine learned advice. InAdvances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual,

    work page 2020

  3. [3]

    Learning- augmented weighted paging

    5 Nikhil Bansal, Christian Coester, Ravi Kumar, Manish Purohit, and Erik Vee. Learning- augmented weighted paging. InProceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 67–89. SIAM,

    work page 2022

  4. [4]

    Metric clustering and MST with strong and weak distance oracles

    6 MohammadHossein Bateni, Prathamesh Dharangutte, Rajesh Jayaram, and Chen Wang. Metric clustering and MST with strong and weak distance oracles. In Shipra Agrawal and Aaron Roth, editors,The Thirty Seventh Annual Conference on Learning Theory, June 30 - July 3, 2023, Edmonton, Canada, volume 247 ofProceedings of Machine Learning Research, pages 498–550. PMLR,

    work page 2023

  5. [5]

    Birnbaum and Claire Mathieu

    7 Benjamin E. Birnbaum and Claire Mathieu. On-line bipartite matching made simple.SIGACT News, 39(1):80–87, 2008.doi:10.1145/1360443.1360462. 8 Lucas Boczkowski, Uriel Feige, Amos Korman, and Yoav Rodeh. Navigating in trees with permanently noisy advice.ACM Trans. Algorithms, 17(2):15:1–15:27,

    work page doi:10.1145/1360443.1360462 2008

  6. [6]

    Learning- augmented maximum independent set

    13 Vladimir Braverman, Prathamesh Dharangutte, Vihan Shah, and Chen Wang. Learning- augmented maximum independent set. In Amit Kumar and Noga Ron-Zewi, editors,Ap- proximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2024, London School of Economics, London, UK, August 28-30, 2024, volume 317 ofLIPIcs, pages...

    work page 2024

  7. [7]

    Online algorithms with advice: The tape model.Information and Computation, 254:59–83, 2017.doi:10.1016/j.ic.2017.03.001

    14 Hans-Joachim Böckenhauer, Dennis Komm, Rastislav Královič, Richard Královič, and Tobias Mömke. Online algorithms with advice: The tape model.Information and Computation, 254:59–83, 2017.doi:10.1016/j.ic.2017.03.001. 15 Davin Choo, Themistoklis Gouleakis, Chun Kai Ling, and Arnab Bhattacharyya. Online bipartite matching with imperfect advice. InForty-fi...

    work page doi:10.1016/j.ic.2017.03.001 2017

  8. [8]

    Optimal robustness-consistency tradeoffs for learning-augmented metrical task systems

    16 Nicolas Christianson, Junxuan Shen, and Adam Wierman. Optimal robustness-consistency tradeoffs for learning-augmented metrical task systems. InInternational Conference on Artificial Intelligence and Statistics, 25-27 April 2023, Palau de Congressos, Valencia, Spain, pages 9377–9399,

    work page 2023

  9. [9]

    Learning-augmented approximation algorithms for maximum cut and related problems

    17 Vincent Cohen-Addad, Tommaso d’Orsi, Anupam Gupta, Euiwoong Lee, and Debmalya Panigrahi. Learning-augmented approximation algorithms for maximum cut and related problems. In Amir Globersons, Lester Mackey, Danielle Belgrave, Angela Fan, Ulrich Paquet, Jakub M. Tomczak, and Cheng Zhang, editors,Advances in Neural Information Processing Systems 38: Annua...

    work page 2024

  10. [10]

    Learning-augmented algorithms with explicit predictors

    18 Marek Eliás, Haim Kaplan, Yishay Mansour, and Shay Moran. Learning-augmented algorithms with explicit predictors. In Amir Globersons, Lester Mackey, Danielle Belgrave, Angela Fan, Ulrich Paquet, Jakub M. Tomczak, and Cheng Zhang, editors,Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 202...

    work page 2024

  11. [11]

    Online computation with advice.Theor

    19 Yuval Emek, Pierre Fraigniaud, Amos Korman, and Adi Rosén. Online computation with advice.Theor. Comput. Sci., 412(24):2642–2656, 2011.doi:10.1016/J.TCS.2010.08.007. 20 Yuval Emek, Yuval Gil, Maciej Pacut, and Stefan Schmid. Online algorithms with randomly infused advice. In Inge Li Gørtz, Martin Farach-Colton, Simon J. Puglisi, and Grzegorz Herman, ed...

    work page doi:10.1016/j.tcs.2010.08.007 2011

  12. [12]

    Spectral clustering with side information.CoRR, abs/2511.17326, 2025.arXiv:2511.17326,doi:10.48550/ARXIV.2511.17326

    22 Hendrik Fichtenberger, Michael Kapralov, Ekaterina Kochetkova, Silvio Lattanzi, Davide Mazzali, and Weronika Wrzos-Kaminska. Spectral clustering with side information.CoRR, abs/2511.17326, 2025.arXiv:2511.17326,doi:10.48550/ARXIV.2511.17326. 23 Anupam Gupta, Debmalya Panigrahi, Bernardo Subercaseaux, and Kevin Sun. Augmenting online algorithms with $\v...

    work page doi:10.48550/arxiv.2511.17326 2025

  13. [13]

    Online bipartite matching with advice: Tight robustness-consistency tradeoffs for the two-stage model

    25 Billy Jin and Will Ma. Online bipartite matching with advice: Tight robustness-consistency tradeoffs for the two-stage model. InAdvances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28 - December 9, 2022,

    work page 2022

  14. [14]

    Karp, Umesh V

    26 Richard M. Karp, Umesh V. Vazirani, and Vijay V. Vazirani. An optimal algorithm for on-line bipartite matching. In Harriet Ortiz, editor,Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, May 13-17, 1990, Baltimore, Maryland, USA, pages 352–358. ACM, 1990.doi:10.1145/100216.100262. 27 Alexander Lindermayr and Nicole Megow. ALPS - algo...

    work page doi:10.1145/100216.100262 1990

  15. [15]

    28 Thodoris Lykouris and Sergei Vassilvitskii

    Accessed: 24-Jan-2026. 28 Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. 35th International Conference on Machine Learning (ICML),

    work page 2026

  16. [16]

    Better and simpler learning-augmented online caching

    31 Alexander Wei. Better and simpler learning-augmented online caching. In Jaroslaw Byrka and Raghu Meka, editors,Approximation, Randomization, and Combinatorial Optimization. Al- gorithms and Techniques, APPROX/RANDOM 2020, Virtual Conference, August 17-19, 2020, volume 176 ofLIPIcs, pages 60:1–60:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 20...

    work page doi:10.4230/lipics.approx/random.2020.60 2020