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.LGSep 4, 2026

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

Authors: Hailiang Zhao, Xueyan Tang, Peng Chen, Zenong Ye, Tianjun Zhu, Jianwei Yin, Shuiguang Deng

Organizations: School of Software Technology, Zhejiang University, Ningbo, China · School of Computer Science and Engineering, Nanyang Technological University, Singapore, Singapore · College of Computer Science and Technology, Zhejiang University, Hangzhou, China · School of Engineering, Stanford University, Stanford, United States

Abstract

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.

Figures & tables

Source	Primary organizing axis	Coverage emphasis	Difference from the present survey
Boyar et al. ( Boyar et al., 2017 )	Advice complexity in bits	Online algorithms with advice	Predictions are treated as fallible task objects with error-dependent guarantees, not only information budgets.
Mitzenmacher and Vassilvitskii ( Mitzenmacher and Vassilvitskii, 2021 ; Mitzenmacher and Vassilvitskii, 2022 )	Predicted object; warm start vs. online use	Foundational algorithms-with-predictions examples	The present survey separates construction mechanism from tightness evidence and extends the comparison to systems interfaces.
Present survey	Mechanism axis P1–P5; tightness-status axis E0/E1	Five algorithmic domains, adjacent systems, composition, and semantic interfaces	Adds theorem-level matching-bound status and conditions for cost, feedback, and cross-component reasoning.

Table 1. Relation to the principal surveys used as entry points. “Present” describes the scope of this article, not a claim of exhaustive coverage.

Symbol	Meaning
$\mathcal{I},\,I$	Instance space; a single instance
$\mathcal{Y},\,\hat{y}$	Prediction space; a predictor output
$y^{*}(I)$	True (unknown) label of instance $I$
$\eta(I,\hat{y})$	Prediction error $\ell_{I}(\hat{y},y^{*}(I))$ , including stated normalization
$\ell_{I}$	Instance-aware error measure (see Table 3 )
$\mathrm{OPT}(I)$	Optimal offline cost with full knowledge of $I$

Table 2. Nomenclature.

Level and type	Predictor output	Typical error measure	Mechanisms in cited examples	Representative use
Task object: point	A scalar or vector estimate of $y^{*}$	$\ell_{1}$ , $\ell_{\infty}$ , $\|\hat{y}-y^{}\|/y^{}$	P1–P4	Ski rental horizon; job sizes; next request time ( Purohit et al., 2018 ; Lykouris and Vassilvitskii, 2018 )
Task object: distributional	A distribution $\hat{\mathcal{D}}$ over $\mathcal{Y}$	$W_{p}(\hat{\mathcal{D}},\mathcal{D}^{*})$ , $d_{\mathrm{TV}}$ , KL	P4, P5	Binary search over a predicted key distribution; contract scheduling ( Dinitz et al., 2024a ; Angelopoulos et al., 2024 )
Task object: ordinal	A ranking or pairwise comparisons	Kendall $\tau$ ; number of inversions	P1, P3, P4	Speed-oblivious scheduling; relative job order ( Lindermayr et al., 2023 )
Task object: structural	A combinatorial object: dual solution, matching, edge subset	Symmetric difference; $\\|\hat{\mathbf{y}}-\mathbf{y}^{*}\\|_{1}$ ; edit distance	P1–P4	Warm-started matchings and flows; predicted dual variables ( Dinitz et al., 2021 ; Lavastida et al., 2021 ; Davies et al., 2023 )
Representation: semantic	Unstructured text, code, or policy fragments	No canonical measure ; requires task-defined semantics and a loss	None directly; needs an adapter (§ 7 )	Log interpretation; fallback-policy synthesis

Table 3. Task objects and orthogonal interface qualifiers, with typical error measures and mechanisms used in cited examples. Evidence status E0/E1 is assigned separately to individual theorems. Entries are illustrative rather than exclusive.

Panel of Figure 1 — Figure 1. The deterministic ski-rental guarantee curve $\big(c(\lambda),r(\lambda)\big)=\big(1+\lambda,1+1/\lambda\big)$ for $\lambda\in(0,1]$ . Every point corresponds to a parameterized guarantee, and the shaded region is asymptotically unattainable as the integer purchase cost $B$ grows; finite- $B$ lower bounds include rounding terms. The endpoint $\lambda=1$ is the classical $2$ -competitive rule, and exact $1$ -consistency is approached only as robustness diverges. A convex decreasing guarantee curve in the plane whose horizontal axis is consistency and whose vertical axis is robustness, showing the relation r equals one plus one over the quantity c minus one on the valid domain where consistency is greater than one and at most two. The curve rises steeply as consistency approaches one and ends at the point where consistency and robustness both equal two. Three points are marked, corresponding to trust parameter values of one, one half and one quarter. The region below and to the left of the displayed curve is shaded and labeled asymptotically infeasible.

Panel of Figure 2 — Figure 2. The two-axis taxonomy. Axis A records one or more construction mechanisms P1–P5. Axis B separately records whether a theorem provides an achieved upper bound (E0) or whether its error dependence is matched by a lower bound under the same prediction model, error measure, adversary, benchmark, and computational assumptions (E1). Neither coordinate follows from the predictor type alone. A two-axis classification diagram. The horizontal construction axis contains five non-exclusive boxes: trust-based combination, prediction-guided primal-dual update, prediction-sensitive relaxation and rounding, prediction access and portfolios with switching, and distribution-guided decision rules. A separate tightness-status axis contains an achieved-bound state E0 and a matched-dependence state E1. The two states are not presented as a general quality ranking.

	Core mechanism	What is guaranteed	Typical scope	Failure mode	Refs.
P1	A single algorithm parameterized by a trust value $\lambda$ fixed offline, or a randomized mixture of two	A theorem-specific pair $\big(c(\lambda),r(\lambda)\big)$ when both branches are controlled	Online problems with a known prediction-free baseline	Needs that baseline to exist; dynamic switching additionally requires state-migration accounting	( Purohit et al., 2018 ; Gollapudi and Panigrahi, 2019 ; Wei and Zhang, 2020 ; Grigorescu et al., 2025 )
P2	Prediction initializes, guides, or repairs a primal or dual certificate in an optimization method	A problem-specific competitive, approximation, or running-time bound from feasibility and dual-based analysis	Online covering / packing; combinatorial warm starts	Requires an explicit relaxation, advice semantics, and invariant; a predicted dual alone gives no generic guarantee	( Bamas et al., 2020b ; Bamas et al., 2020a ; Dinitz et al., 2021 ; Sakaue and Oki, 2022 ; Grigorescu et al., 2025 )
P3	Prediction guides a fractional solution; a separate online rounding theorem makes it integral	Product of the fractional guarantee and the rounding factor, when their assumptions align	Online scheduling and facility location	Rounding may dominate the ratio and need not preserve consistency	( Lattanzi et al., 2020 ; Lattanzi et al., 2026 )
P4	Control which predictor or algorithm is consulted or followed, including query, switching, and state costs	Competition with a specified benchmark or a bound using fewer prediction calls, under a problem-specific reduction	Multiple predictors or costly access to one predictor	Prediction regret alone does not imply cost competitiveness or robustness	( Anand et al., 2022 ; Dinitz et al., 2022 ; Antoniadis et al., 2023b ; Cosa and Eliáš, 2025 ; Drygala et al., 2023 ; Im et al., 2022 ; Abdel Sadek and Eliáš, 2024 )
P5	Use a predicted distribution directly in a search, schedule, or other problem-specific rule	Error-dependent performance in a stated distributional distance, plus a separate worst-case bound when proved	Distributional predictions	No generic Wasserstein or risk theorem transfers across objectives	( Dinitz et al., 2024a ; Angelopoulos et al., 2024 ; Angelopoulos and Simon, 2025 )
Axis B: evidence status		E0 : achieved upper bound; E1 : matching lower bound under the same formal model	Assigned per theorem	Tightness does not transfer across error measures, adversaries, benchmarks, or computational models	( Rohatgi, 2020 ; Antoniadis et al., 2023c ; Dinitz et al., 2024a )

Table 4. The two taxonomy axes. P1–P5 describe construction mechanisms; E0/E1 describes theorem-level evidence. A label alone implies no guarantee.

Theorem record	Axis A	Eligible upper-bound claim	Lower-bound pairing in the same model	Axis B
Deterministic ski rental ( Purohit et al., 2018 ; Wei and Zhang, 2020 )	P1	Guarantee curve $(1+\lambda,1+1/\lambda)$ for $\lambda\in(0,1]$	Asymptotically matching impossibility frontier for the same deterministic model; finite- $B$ rounding remains	E1
Caching with next-arrival predictions ( Rohatgi, 2020 )	P1	Error-dependent competitive guarantee under the paper’s arrival-error metric	Upper and lower bounds are near-optimal but leave a functional and logarithmic gap under the strict rule	E0
Binary search with distributional predictions ( Dinitz et al., 2024a )	P5	$O(H(p)+\max\{\log\eta,0\})$ expected queries	Matching dependence under the paper’s distributional model	E1
MTS with bandit predictor access ( Cosa and Eliáš, 2025 )	P4	$O(\mathrm{OPT}_{\leq 0}^{2/3})$ regret when auxiliary parameters are constants	$\widetilde{\Omega}(\mathrm{OPT}_{\leq 0}^{2/3})$ leaves logarithmic factors	E0
Stochastic online bidding ( Angelopoulos and Simon, 2025 )	P1, P5	Distributional deterministic: tight Pareto trade-off; randomized point oracle: class-specific upper bounds	The distributional deterministic frontier is matched; the randomized results do not form one blanket match	P5: E1; P1: E0
Randomized strategic facility location ( Balkanski et al., 2024a )	outside P1–P5	The line: truthful-in-expectation frontier; higher-dimensional settings: model-specific upper bounds	The line has a matching impossibility result; the other settings do not share one matched frontier	line: E1; others: E0

Table 5. Selected theorem records illustrating the two-axis coding. Each status applies only to the stated guarantee. N/A marks adjacent empirical evidence outside Axis B, not a third evidence level.

Domain	Problem class	Core tension	Mechanism by cited result	Representative guarantee
Online optimization (§ 5.1 )	One-dimensional and multistate stopping (ski rental, Bahncard, dynamic power management)	Irrevocable timing vs. unknown horizon	P1 for ski rental; problem-specific extensions	Ski rental has the asymptotically tight curve $(1{+}\lambda,\,1{+}1/\lambda)$ ; extensions use different guarantees ( Purohit et al., 2018 ; Wei and Zhang, 2020 ; Zhao et al., 2024 ; Antoniadis et al., 2021 )
	Metrical task systems	Movement cost vs. service cost	P1 robustification; P4 predictor mixing	Robust black-box combinations and switching-aware mixtures of predictors ( Antoniadis et al., 2020 ; Antoniadis et al., 2023b )
	Online convex optimization	Adversarial regret vs. temporal regularity	optimistic online learning	Classical optimistic methods give regret controlled by $\sqrt{\sum_{t}\\|g_{t}-\hat{g}_{t}\\|_{*}^{2}}$ under the stated geometry; imperfect-hint refinements use more specific quantities ( Rakhlin and Sridharan, 2013 ; Bhaskara et al., 2020 )
	Scheduling, load balancing, online allocation	Capacity uncertainty vs. irrevocable assignment	P3 for Lattanzi et al.; other mechanisms differ	Bounds use distinct weight, size, speed, or learned-parameter errors and objectives ( Lattanzi et al., 2020 ; Cohen and Panigrahi, 2023 ; Cohen and Panigrahi, 2025 ; Lindermayr et al., 2023 ; Zhao and Zomaya, 2026 )
Caching (§ 5.2 )	Prediction-aware paging	$1$ -consistency without prohibitive overhead	P1	Error-dependent trade-offs and reduced-prediction variants ( Rohatgi, 2020 ; Abdel Sadek and Eliáš, 2024 )
	Randomized robustification	Preserving $1$ -consistency while capping the worst case	problem-specific robustifier	$1$ -consistent and $(2H_{k-1}{+}2)$ -robust with $O(1)$ additional algorithmic time per request in the cited model ( Chen et al., 2025 )

Table 6. Consolidated view of representative problem domains. Mechanisms can fall outside P1–P5. Grouped rows summarize objectives and guarantees but do not receive a single evidence label.

Panel of Figure 3 — Figure 3. An accounting view of a learning-augmented deployment. Solid arrows form the decision path and dashed arrows denote feedback. Fast mechanisms can use only immediately observable signals; delayed outcomes may support recalibration or retraining. A four-layer stack drawn bottom to top: Signal, Prediction, Decision and safety, and Actuation, connected by solid arrows. A fast dashed feedback path returns to the decision layer and a slower dashed path returns to the prediction layer.

System	Predicted quantity	Evidence and guarantee	Prediction cost	Behavior under error
LRB ( Song et al., 2020 )	Reuse distance or next access for eviction	Empirical cache performance; no native competitive guarantee	Inference on the eviction path	Error can increase misses; no theorem-level worst-case cap follows from LRB alone
Parrot ( Liu et al., 2020 )	Eviction priority learned by imitation	Empirical cache performance; no native competitive guarantee	Policy inference on eviction	Error can change eviction order; robustness remains empirical for Parrot itself
PGM ( Ferragina and Vinciguerra, 2020 )	Key position with certified segment error	Static recursive index has $O(\!\log m+\log(\epsilon+1))$ query time and $\Theta(m)$ space	Model evaluation and bounded local search	Correctness is retained by searching the certified interval; update costs use a separate dynamic analysis
ALEX ( Ding et al., 2020 )	Key position and layout cost	Correct index semantics plus empirical latency and memory results; no $(c,r,f)$ contract	Model evaluation, inserts, splits, and expansion	Adaptive structure handles updates empirically; performance varies by workload ( Wongkham et al., 2022 )
Decima ( Mao et al., 2019 )	Scheduling policy from job DAG and cluster state	Empirical system objective; no competitive guarantee	Offline trace training and online policy inference	Behavior beyond the evaluated workloads is an empirical question; no LAA theorem bounds it
Autopilot ( Rzadca et al., 2020 )	Resource settings from workload observations	Production evaluation and operational constraints; no $(c,r,f)$ theorem	Continuous observation and recommendation	Limits and gradual changes are safeguards, not competitive-ratio certificates

Table 7. Eight systems-oriented examples viewed through the LAS questions. Each row refers only to the named system or class; formal guarantees, operational safeguards, and empirical behavior are not transferred across rows.

Learning-Augmented Algorithms

Learning-augmented algorithms use predictions to improve algorithmic performance while retaining guarantees when predictions are wrong.

See all 54 papers

May 26, 2026

Parsimonious Learning-Augmented Online Metric Matching

Learning-augmented algorithms have received significant attention in recent years, particularly in the context of online optimization. Motivated by the high computational cost of generating predictions, a growing line of work studies the tradeoff between performance guarantees and the number of predictions used in learning-augmented algorithms for problems such as caching and metrical task systems. In this paper, we extend this line of research to online metric matching by developing parsimonious learning-augmented algorithms and establishing lower bounds on their performance. Our approach extends the Follow-the-Prediction framework to the parsimonious setting by filling in a virtual prediction in the absence of an actual prediction, using an online metric matching algorithm that maintains good intermediate matchings throughout its execution. We complement our theoretical results with an empirical evaluation, demonstrating the practical effectiveness of our approach.

Yongho Shin, Phanu Vajanopath

Institute of Computer Science, University of Wrocław, Wrocław, Poland.

Learning-Augmented Algorithms

Ask PDF

Feb 24, 2026

Online Algorithms with Unreliable Guidance

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.

Julien Dallot, Yuval Emek, Yuval Gil +2

TU Berlin, Germany · Technion, Israel · Reykjavik University, Iceland +1

Learning-Augmented Algorithms

Ask PDF

May 31, 2026

Towards Optimal Robustness in Learning-Augmented Paging

Learning-augmented paging has been extensively studied in recent years. A key advantage over naive ML-based approaches is bounded robustness, which guarantees worst-case performance even when predictions are inaccurate, making these algorithms valuable for real-world systems. Prior work achieves robustness bounds of

2H_k + O(1)

in the randomized setting, leaving a gap to the optimal competitive ratio

H_k

. In this paper, we study how to close this gap. We begin by reviewing online optimality and proving a new property of the latest

H_k

-competitive algorithm, which facilitates our analysis in the learning-augmented setting. Then, we review existing learning-augmented paging algorithms and introduce a unifying primitive, the relative prediction budget, which captures the essence of establishing robustness and reveals that prior algorithms either overuse or underutilize predictions. Guided by the above analysis, we develop a new framework that achieves the best-possible robustness up to an additive constant for learning-augmented paging:

H_k + O(1)

. Experiments further demonstrate strong practical performance.

Peng Chen, Hailiang Zhao, Xueyan Tang +2

Zhejiang University, Hangzhou, China · Nanyang Technological University, Singapore · Nanjing University of Aeronautics and Astronautics, Nanjing, China

Competitive Analysis Learning-Augmented Algorithms

Ask PDF

Abstract

Learning-Augmented Algorithms

Explore similar work

Parsimonious Learning-Augmented Online Metric Matching

Online Algorithms with Unreliable Guidance

Towards Optimal Robustness in Learning-Augmented Paging