A prediction can make an online decision far better than a conservative worst-case rule, but it can also fail exactly when the decision is most consequential. This survey organizes the field around that tension. Its central move is to separate three questions: what the predictor says, how the algorithm uses it, and what the theorem actually proves.
1. Why this field needs more than a list of applications
Classical online algorithms make decisions without knowing the future. Their worst-case guarantees are dependable, but can be conservative when workloads are predictable. A learned policy takes the opposite bet: it uses historical regularity to improve average behavior, but its performance outside the evaluation distribution may be unclear.
Learning-augmented algorithms place a fallible prediction inside a formally analyzed algorithm. This is not simply machine learning followed by a fallback. The prediction interface, the error measure, the fallback state, and the objective all participate in the proof. Two papers can both use a next-arrival predictor and still establish incomparable results if they normalize error differently or compete against different benchmarks.
2. The basic contract: good advice should help, bad advice should not be catastrophic
Let (I) be an instance, (hat y) a prediction, (y^*(I)) the unknown target, and (eta(I,hat y)) a task-specific prediction error. A learning-augmented algorithm (A) is compared with the offline optimum (operatorname{OPT}(I)). The survey uses a trust parameter (lambdain[0,1]), chosen before the unrevealed part of the instance is seen; smaller (lambda) means greater trust in the prediction.
These statements are related but not interchangeable. A smoothness curve can grow without bound and therefore provide no prediction-independent robustness. A strong consistency guarantee says what happens at zero error, but says nothing by itself about a small nonzero error. A consistency-robustness pair is a tight frontier only when a lower bound rules out every better pair under the same formal model.
Ski rental makes the trade-off visible
Suppose renting costs one per day, buying costs (B), and a predictor estimates the number of ski days. A parameterized rule trusts the estimate more as (lambda) decreases. One standard guarantee has the form
At zero error, the second branch gives consistency (1+lambda). For arbitrary error, the first branch caps the ratio at (1+1/lambda). More trust improves consistency but weakens the worst-case cap.
3. Before choosing an algorithm, specify the prediction
The predictor output is part of the problem definition. The survey distinguishes several task objects and treats uncertainty or semantic representation as additional interface qualifiers.
Point prediction
A scalar or vector such as a horizon, job size, or next-request time. Absolute and relative errors lead to different bounds.
Distributional prediction
A probability distribution used by a search or scheduling rule. The theorem must name its distance and regularity assumptions.
Ordinal prediction
A ranking or set of pairwise comparisons. Inversions may matter more than numerical distance.
Structural prediction
A matching, dual solution, edge set, or other combinatorial object that may be repaired or used as a warm start.
An error metric is not a reporting detail. It determines which mistakes are expensive in the theorem. It also matters when the true target becomes observable. An error revealed after an irreversible decision can support retrospective evaluation, but cannot directly drive an online trust controller.
4. Five ways predictions enter a provable construction
The survey's first axis classifies the mechanism, rather than the application domain. The five labels are non-exclusive, so one paper may use more than one.
- P1: trust-based combination. A prediction-following method is mixed or interpolated with a prediction-free baseline. A one-shot randomized mixture and a continuously parameterized algorithm are different constructions. Dynamic switching additionally requires state-migration accounting.
- P2: prediction-guided primal-dual methods. Advice initializes, steers, or repairs primal or dual variables. Feasibility and a dual invariant do the real work in the proof; a predicted dual has no generic guarantee without them.
- P3: prediction-sensitive relaxation and rounding. Prediction improves a fractional construction, then a compatible online rounding theorem produces an integral decision. The rounding factor may dominate the final ratio or prevent exact consistency.
- P4: access, portfolio, and switching reductions. The algorithm controls which predictor or policy is queried or followed. Low regret on a surrogate loss becomes meaningful only through a problem-specific reduction to actual cost, compatible state transitions, and an appropriate comparator.
- P5: distributional predictions. A predicted distribution directly changes a search, schedule, or decision rule. Error-dependent performance remains tied to a stated distance and objective; there is no universal transfer from Wasserstein distance or a risk measure to system cost.
5. A second axis prevents strong claims from being blurred together
Axis B records theorem-level evidence independently of the mechanism. E0 means the survey records an achieved upper bound but does not pair it with a matching lower bound in the same model. E1 means the asymptotic dependence is matched under the same prediction model, error metric, adversary, benchmark, and computational assumptions.
| Representative result | Mechanism | Evidence | What the label says |
|---|---|---|---|
| Deterministic ski rental | P1 | E1 | Matched asymptotic trade-off in its model |
| Caching with next-arrival predictions | P1 | E0 | Upper and lower bounds still leave a gap |
| Binary search with distributional predictions | P5 | E1 | Matched dependence on distributional error |
| Metrical task systems with bandit predictor access | P4 | E0 | Known lower bound leaves logarithmic factors |
E0 is not a judgment that a result is weak, and E1 is not a maturity score. Tightness does not transfer across different models. Empirical systems evidence is marked separately because measured performance and a competitive theorem answer different questions.
6. The same framework spans different objectives
The survey follows the mechanisms through five domains: online optimization, caching and paging, learned data structures, graph algorithms and networking, and mechanism design. This breadth reveals recurring proof devices, but also a reason for caution. These domains optimize different quantities, including competitive ratio, approximation quality, query complexity, running time, and social welfare.
For example, a learned index may preserve correctness by searching a certified interval around a predicted key position. That is a valuable guarantee, but it is not automatically a consistency-robustness theorem for update latency. Likewise, a strategyproof mechanism must preserve incentives in addition to feasibility, so an algorithmic robustifier cannot be transferred without rechecking the strategic model.
7. From a component theorem to an operating system
A component theorem typically studies one prediction interface and one objective. A deployment connects prediction, decision, actuation, and feedback, often across shared compute and state. The survey isolates three omissions that become first-class systems concerns:
- Predictions are not free. Model inference, queries, retraining, and data collection consume time and resources that the classical competitive objective usually does not charge.
- Error can be late and endogenous. Ground truth may arrive after the action, be censored by it, or change because the policy changes future observations.
- Components are not isolated. One stage can alter the instance, state, and offline benchmark seen by the next. Local ratios therefore do not automatically multiply into a system ratio.
Pricing a predictor changes the guarantee
If each call costs (c) in the units of the system objective and (Q_A) is the number of calls, the survey proposes the accounting quantity
Against an offline optimum that is not charged for predictions, exact multiplicative 1-consistency is impossible whenever perfect-prediction instances still require a positive expected prediction cost, unless the model adds an additive term or changes the benchmark.
Composition needs interface facts, not only local ratios
The survey gives limited sufficient conditions for three patterns. Additive composition needs component costs and offline benchmarks to share a pathwise decomposition. Cascaded composition needs bounds on how each stage distorts the next stage's benchmark. Error propagation needs metrics and Lipschitz-like sensitivity on every connecting edge:
If an edge has no meaningful metric, sensitivity bound, or perturbation model, this argument supplies no transferred smoothness guarantee.
8. What changes when the prediction is generated as language
Most learning-augmented theorems expect a number, ranking, distribution, or combinatorial structure. A foundation model may emit free-form text. The text becomes usable only after an adapter maps it to a typed task object and the system defines an error measure that the downstream theorem understands.
Predictor
Produces a duration, order, or other formal object. Parsing and the theorem's error assumptions still apply.
Adapter
Extracts structured input from text. Validation must cover the adapter's failure modes.
Policy synthesizer
Proposes a rule or fallback. The artifact needs verification and deployment controls.
Explainer
Summarizes telemetry for an operator. Provenance and uncertainty still matter because the output can influence action.
Token likelihood is not automatically a calibrated probability of task correctness, and agreement across sampled responses measures self-consistency rather than labeled accuracy. Rich semantic reasoning may be useful, but it does not improve an existing guarantee without a new information model and proof.
9. The research agenda
The survey closes with four connected challenges: pricing prediction within the objective, developing a calculus for composition, modeling policy-dependent or strategic error, and making empirical benchmarks comparable. The broader lesson is methodological. A prediction should be treated as a typed, fallible, and priced input to an algorithm, not as an informal source of intelligence. A guarantee belongs to the complete contract among prediction, decision, state, objective, and benchmark.