Sibling Heads as Early Warnings: Per-Instance Trust for Algorithms with Multi-Task Predictions

Online algorithms with predictions face a trade-off between two goals. They can trust a machine-learned forecast and perform near-optimally when it is right, a property called consistency. Or they can hedge and keep a worst-case guarantee when it is wrong, a property called robustness. Today the hedging is controlled almost everywhere by a single global knob, such as the confidence parameter in data-center capacity scaling or the trust weight in metrical task systems. That knob is set without knowing whether the forecast in front of the algorithm right now is good.

Many deployed predictors are multi-task. They are one shared network with several output "heads," and some heads forecast quantities that are revealed quickly, like next-minute load, while the head the algorithm actually needs forecasts something revealed late, like load an hour ahead. We propose to use the quickly verified heads as an online alarm. Their errors share a backbone with the critical head, so a surge in their residuals should signal that the critical prediction is also going wrong, before the algorithm pays for it. The algorithm then raises or lowers trust instance by instance. Because trust is never allowed below a fixed floor, the worst-case guarantee stays intact, and the gain shows up as lower cost at the same guaranteed robustness.

Core Claim

The claim is that, at a fixed robustness guarantee, a learning-augmented algorithm whose trust is driven by residuals of fast-verifiable sibling heads achieves lower realized cost under distribution shift than any fixed trust setting, than trust derived from the critical head's own calibrated confidence, and than trust adapted from the advice's past realized performance.

The claim also says why. Errors across heads of a shared backbone are correlated, and the proposal tests that this correlation, not merely access to extra forecasts, is what carries the signal. An ablation replaces the shared model with separately trained monitors to check this.

This view reverses how the multi-task literature usually treats shared representations. There, shared errors and gradient conflict are something to suppress. Here, coupling between heads is an asset for safety.

Relation to Prior Work

The work closest on the algorithmic side sets trust with a fixed scalar. A New Approach to Capacity Scaling Augmented With Unreliable Machine Learning Predictions interpolates between a 5-competitive online rule (Balanced Capacity Scaling, BCS) and a follow-the-forecast heuristic (Adapt to the Prediction, AP) through a confidence parameter $r$. It treats the forecaster as an immutable black box. Optimal robustness-consistency tradeoffs for learning-augmented metrical task systems proves that $(1+\epsilon)$-consistency forces $2^{O(1/\epsilon)}$ robustness in general metrics. Its algorithm, DART, maintains adaptive trust weights, but those weights are updated from the realized costs of following advice, which is a lagging signal. Online Computation with Untrusted Advice establishes that the frontier is a strict Pareto curve. These papers constrain the proposal: we cannot hope to beat the frontier in the worst case, only to sit at a better point on realized instances for a given robustness level.

The most direct precedent is Algorithms with Calibrated Machine Learning Predictions. It replaces global trust with instance-level calibrated probabilities for ski rental and scheduling, and its costs degrade gracefully in calibration error and mean-squared error. It also argues that conformal intervals often become uninformative in these settings. We borrow its per-instance philosophy but change the source of the signal. Calibration is a statement about the critical head's own output distribution, and under distribution shift that calibration is exactly what breaks. Our signal comes from residuals that are actually observed online on other heads. It therefore reacts to shift rather than assuming calibration survives it.

On the multi-task side, RotoGrad: Gradient Homogenization in Multi-Task Learning rotates the shared representation per task and rebalances gradient magnitudes so that task gradients stop conflicting. Shared-backbone designs like Fast R-CNN and Multi-task Self-Supervised Visual Learning motivate using one backbone for several heads, and they report generalization benefits. None of these evaluates a downstream competitive ratio.

This raises a tension we address head-on. Methods that decouple tasks, such as RotoGrad, may also decouple their errors and weaken the early-warning signal. We therefore measure that effect rather than assume it away.

A2Perf: Benchmarking Autonomous Agents End-to-End in Realistic Domains measures consistency and robustness empirically for agents but designs no algorithm. It motivates the evaluation style of reporting worst-case and dispersion alongside mean performance, and it is not a testbed here.

Research Program

The system has three parts.

The first part is the predictor. It is a shared encoder over recent workload history with $H$ heads forecasting load at horizons $1,\dots,H$. It is trained jointly with standard losses. The long-horizon head feeds the capacity-scaling decision. The short horizons are revealed within minutes, so their residuals are cheap to observe.

The second part is the monitor. It is a small model $g$, fit on held-out validation traces, that maps a window of recent sibling-head residuals $e^{\text{aux}}_t$ to a predicted error of the critical head.

The third part is the trust rule, which sets the time-varying confidence as

$$r_t = \mathrm{clip}\big(g(e^{\text{aux}}_t),\, r_{\min},\, 1\big),$$

where $r_t$ is the confidence passed to ABCS at time $t$ and $r_{\min}$ is the floor that fixes the worst-case guarantee.

The theoretical work has two parts.

The first is showing that a time-varying confidence above the floor inherits ABCS's robustness bound for $r_{\min}$. This is not automatic. Changing $r$ can itself trigger server switching costs. We expect to need either a bounded rate of change on $r_t$ or an extra additive switching term, and we will prove whichever holds.

The second is bounding the consistency-side gain. We expect a bound in terms of how well the monitor's output ranks the critical head's true error; a rank correlation is the natural quantity. With a monitor at chance, the gain reduces to that of fixed-$r_{\min}$ ABCS. With a perfect monitor, it approaches the gain of an oracle that knows when the forecast fails. The empirical analysis measures that rank correlation directly for three predictor types: a shared model, a RotoGrad-trained shared model, and separately trained models.

The same construction transfers to ski rental on Citi Bike. There, sibling heads predict station-level demand in the near term alongside the rental-duration head that drives the buy decision. We will also try it on the clinical sepsis scheduling data used by the calibrated-predictions paper, if its features support auxiliary short-term targets.

Baselines

The naive reference points are pure BCS, which ignores forecasts, and AP, which follows them blindly. On TI-2016 DNS, the ABCS paper reports that AP's cost is 27.7 times the optimum when predictions fail. Any trust scheme must stay far from that.

The strongest fixed-trust competitor is ABCS itself with $r$ fixed at our floor $r_{\min}$, and separately with the best fixed $r$ chosen in hindsight on validation data. A New Approach to Capacity Scaling Augmented With Unreliable Machine Learning Predictions reports empirical competitive ratios on TI-2016 DNS of 1.00 with accurate predictions and 1.19 when predictions fail. Those are the reference numbers. We will run it on identical traces, with an identical forecaster for the critical head and an identical search over $r$.

The strongest per-instance competitor adapts the calibrated-trust approach of Algorithms with Calibrated Machine Learning Predictions. We give the critical head a calibrated probability of large error, recalibrated on the same validation split our monitor uses, and map that probability to $r_t$ with the same clipping. This isolates the source of the signal while holding everything else fixed.

A retrospective-adaptation baseline updates $r_t$ multiplicatively from the realized cost gap between following and ignoring advice, in the spirit of DART's trust weights. It isolates the value of early warning versus lagging feedback.

Two ablations isolate the key ingredient. The first replaces the shared-backbone siblings with separately trained short-horizon models of equal capacity and training budget, and tests whether sharing matters. The second uses the multi-task predictor with fixed $r$, and tests whether any gain comes merely from multi-task training improving the critical forecast.

All methods get the same traces, the same shift protocol, and the same validation data for tuning. Beating the baseline means strictly lower mean and 90th-percentile competitive ratio across shift scenarios at an equal proven robustness floor, with the confidence interval over seeds and trace splits excluding zero difference against the calibrated-trust and separate-monitor baselines.

Why not just…?

Why not just train separate single-task models, one per quantity? Separate short-horizon models trained on the same data may well see the same distribution shift and show correlated errors for that reason alone. If so, the sharing claim is wrong and only the "use fast-verifiable forecasts as alarms" claim survives. This is a real threat. The separate-monitor ablation settles it directly by comparing the rank correlation between monitor output and critical-head error, and the downstream competitive ratio, at matched capacity. The efficiency arguments for multi-task training, such as the more-than-5x speedup in A Classification-Based Polyphonic Piano Transcription Approach Using Learned Feature Representations, are secondary here and would not rescue the idea if the ablation ties.

Why not just calibrate the critical head and use its own confidence, as in the calibrated-predictions work? That approach is the right choice when the calibration continues to hold at test time. Our target setting is shift, where a model's confidence about its own output is typically what degrades first, whereas sibling residuals are measured rather than predicted. The calibrated-trust baseline tests this under our shift protocol. If it matches us, the contribution collapses into "recalibrate online," and we would report that.

Why not just adapt trust from the advice's realized performance, as DART does? Realized cost reveals a bad forecast only after the algorithm has acted on it, and at the long horizons capacity scaling cares about, that lag is the whole problem. The retrospective baseline quantifies this. We also measure detection lead time, meaning the minutes between a shift onset and the trust drop. If lead time is near zero because shifts are gradual, retrospective adaptation will match us, and we expect that on slow-drift scenarios.

Why not just use conformal intervals to set safety margins? Algorithms with Calibrated Machine Learning Predictions reports that such intervals often widen to cover the whole domain in these problems. We will include split-conformal interval width as another trust signal under the same clipping, but we expect it to inherit the lagging-calibration issue.

Proposed Experiments

The primary testbed is the TI-2016 DNS trace from the ABCS paper. We train on early days and test on later days. Shifts are injected in three ways: time-of-day misalignment, synthetic surges of varying magnitude and onset speed, and input corruption applied to the encoder so that the shared representation itself drifts. The last of these tests the negative-transfer concern that a drifting backbone can keep average accuracy while ruining downstream robustness.

The metric is empirical competitive ratio against the offline optimum. We report the mean, the 90th percentile, and the worst case over scenarios, and we plot realized cost against the proven robustness floor as $r_{\min}$ varies. That plot is an empirical Pareto curve on which each method traces its own line.

The secondary testbed is ski rental on Citi Bike. For it and for the sepsis scheduling data, no reported numerical result was found on Lacuna for the calibrated baseline, so we will reproduce that baseline ourselves before comparing.

The decisive checks are three. First, on TI-2016 DNS our curve must lie below fixed-$r$ ABCS at every floor, for example below its reported 1.19 under failed predictions when evaluated at the same floor. Second, the shared-backbone monitor must beat the separate-model monitor in rank correlation and in cost. Third, training the backbone with RotoGrad should measurably reduce the monitor's rank correlation. If the third holds, multi-task methods face a real trade-off between clean per-task accuracy and downstream safety, and the proposal names it.

If the first check fails, the idea is wrong. If only the second fails, the result narrows to fast-verifiable forecasts as alarms, independent of multi-task sharing.