Learning-Augmented Algorithms: Guarantees, Construction Mechanisms, and System-Level Implications
Hailiang Zhao, Xueyan Tang, Peng Chen, Zenong Ye, Tianjun Zhu, Jianwei Yin, Shuiguang Deng
cs.LG · cs.DS
Quick verdict
Survey organizes LAA via P1–P5 mechanism and E0/E1 tightness axes; rigorous, honest synthesis, but single-coder qualitative coding limits auditability.
Summary
This survey synthesizes the learning-augmented algorithms (LAA) literature: online algorithms that consume possibly wrong predictions while retaining formal guarantees. Rather than organizing by prediction type or advice complexity, it proposes two orthogonal axes: five construction mechanisms (P1 trust-based combination, P2 prediction-guided primal-dual updates, P3 prediction-sensitive relaxation plus rounding, P4 prediction-access/portfolio/switching reductions, P5 distribution-guided decision rules) and a theorem-level evidence axis (E0 achieved upper bound vs. E1 matching lower bound under the same model). The corpus, built by snowballing and targeted searches through September 2026, spans five domains: online optimization, caching, learned data structures, graph problems, and mechanism design. Matched tightness (E1) is found concentrated in a few well-specified models (ski rental, distributional binary search, selected caching and strategic facility-location results), while most guarantees remain E0. The survey adds expository composition propositions showing that component consistency-robustness-smoothness triples do not compose into pipeline guarantees without benchmark decomposition, distortion, or Lipschitz-edge facts; a kappa-augmented competitive ratio pricing predictor calls; and a conservative reading of LLM predictions as interface-conditional evidence rather than guarantees. Limitations: single coder without inter-rater statistics, no PRISMA-style screening log, and qualitative rather than quantitative corpus coding.
Review complete
Assessment at a glance
3
risk flags identified
● high 0
● medium 1
● low 2
5 strengths · 5 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- A two-axis taxonomy — five construction mechanisms (P1–P5) and theorem-level matching-bound status (E0/E1) — organizes the LAA corpus in ways prediction-type or advice-complexity classifications cannot.
- Matched asymptotic dependence (E1) is confined to a small set of well-specified models (ski rental, distributional binary search, selected caching and strategic facility-location records); most error-dependent guarantees in the corpus are achieved upper bounds (E0) only.
- Component consistency-robustness-smoothness triples do not compose into pipeline guarantees without additional benchmark-decomposition, distortion-factor, or Lipschitz-edge facts (Propositions 6.2–6.4).
- Charging predictor invocations in the objective (κ-augmented competitive ratio, Definition 8.1) makes exact multiplicative 1-consistency against an uncharged optimum impossible whenever the exact-prediction instance incurs positive prediction cost, absent additive terms or a different benchmark.
- No consistency-robustness guarantee of the form in Definitions 3.1–3.3 follows from placing a language model in the prediction layer without a new model, adapter failure analysis, and proof; existing LLM instantiations are conditional-interface evidence only.
Strengths
Genuinely new organizational axis beyond prior surveys
The E0/E1 tightness axis (§2.3, §4, Table 5) with a strict same-model rule — E1 requires agreement on prediction object, adversary, benchmark, objective, error, and computational assumptions — is a contribution Table 1 explicitly differentiates from Boyar et al. [33] and Mitzenmacher-Vassilvitskii [90, 91].
Theorem-level precision in cited bounds
Each quoted number is tied to its exact configuration: deterministic ski-rental curve (1+λ, 1+1/λ) with asymptotic Pareto-optimality and finite-B rounding caveats (§3.5, Fig. 1); Guard&A preserving 1-consistency with (2H_k−1+2)-robustness in the RB-following model [34] (§5.2.3); O(H(p)+max{log η,0}) for distributional binary search [44] coded E1; bandit-access MTS O(OPT≤0^{2/3}) vs eΩ(OPT≤0^{2/3}) correctly kept E0 due to log factors (Table 5); joint replenishment [43] near-tight-but-not-E1 because the Ω(η^{1/3}) bound is class-restricted.
Unusually candid methodology disclosure
Actionable composition and cost accounting
Careful conceptual hygiene that prevents citation errors
Weaknesses
Central deliverable rests on a single unauditable coder
Binary E0/E1 label discards gradations of tightness
Headline phrasing outruns the underlying math
Qualitative corpus with no coverage quantification
Self-authored works sit among the coded records
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
This is a structured narrative survey of learning-augmented algorithms (LAA): online algorithms that consume fallible predictions while retaining formal guarantees. Four research questions organize it (§2.1): reusable devices that convert untrusted predictions into guarantees (RQ1); which stated trade-offs carry matching lower bounds under the same model (RQ2); which contract assumptions need extra modeling once the algorithm is a system component (RQ3); and the status of foundation-model predictions (RQ4). The claimed contribution is organizational rather than theorem-new: two orthogonal axes — construction mechanisms P1–P5 (§4, Table 4: trust-based combination; prediction-guided primal-dual updates; sensitive relaxation plus rounding; prediction-access/portfolio/switching reductions; distribution-guided rules) and theorem-level evidence status E0/E1 (achieved upper bound vs. matched asymptotic dependence, Table 5) — plus a systems-level reading (LAS, §6) and a deliberately conservative treatment of LLM predictions (§7). Five domains are covered (§5): online optimization, caching, learned data structures (explicitly labeled adjacent evidence), graph problems, and mechanism design, with the corpus updated through 3 September 2026.
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 5 strengths & 5 weaknesses, analyzed in detail
- 3 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
What is a learning-augmented algorithm?
An algorithm that receives a machine-learned prediction (for example, of a future request or workload) and may follow it, but is designed so that its performance stays provably bounded even when the prediction is arbitrarily wrong. Three standard measures apply: consistency (performance under perfect predictions), robustness (worst case over all predictions), and smoothness (how performance degrades as a function of prediction error).
What do P1–P5 and E0/E1 mean in this survey?
P1–P5 are five recurring construction mechanisms: trust-parameter combination of a prediction-follower with a robust baseline; prediction-guided primal-dual updates; prediction-sensitive fractional relaxation plus rounding; control of predictor access, portfolios, and switching; and direct use of predicted distributions. E0/E1 is a separate, per-theorem label: E0 means the stated upper bound is not paired with a matching lower bound in the same model in this survey; E1 means upper and lower bounds agree asymptotically under the same assumptions.
Can LLMs be used as predictors in algorithms with formal guarantees?
Not automatically, according to this survey. A language model emits free-form text, so an adapter must map it to a typed prediction object and define an error measure before any consistency-robustness theorem applies. Token likelihood is not a calibrated probability of task correctness, and existing LLM instantiations (such as a heavy-hitter oracle in time-decay moment estimation) count as conditional-interface evidence, not guarantees.
Do guarantees of individual components add up in a pipeline?
No. The survey's Propositions 6.2–6.4 show that composing components requires extra interface facts: a pathwise decomposition of the system benchmark (a factor β), bounds on how much each stage distorts the next stage's benchmark, or Lipschitz sensitivity of the connecting maps. Perfect consistency of every component need not imply perfect system consistency.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- The provided excerpt contains three explicit [...sampling gap...] regions — mid-paper body (parts of §3.5 and the §5 domain sections), the end of §7.3 (cut mid-word at 'extensions to non-exc...'), and references around [74]–[82]. No claim in this review relies on the omitted passages.
- No code or data availability statement appears in the provided text; whether one exists in the sampled-out portions cannot be ruled out.
- Table 5 shows seven coded theorem records in the visible text; the survey states these are representative examples, not the full coding.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.