When a SAT or planning solver is stopped at a time limit, we learn only that it would have needed more than that much time. Statisticians call this right-censoring: we observe a lower bound, not the event time. Anyone who allocates compute across a portfolio of solvers faces this problem on every instance. They must split a fixed wall-clock budget across cores, solvers, and random restarts. Picking the best split is a combinatorial problem that is NP-hard in general. The only feedback they get is truncated runs, and the truncation point is whatever time they chose to give each run. A theory already exists for online learning over NP-hard decision sets when only an approximation algorithm is available. Efficient Online Linear Optimization with Approximation Algorithms shows that an α-approximation oracle, wrapped in a "separation-or-decomposition" routine built on the Ellipsoid method, achieves α-regret with only $O(\log T)$ amortized oracle calls per round. The paper contains no experiments at all, and it notes that the Ellipsoid method is numerically fragile in practice.
This note proposes to turn that theory into a working learner for censored compute allocation and to test it on real runtime data. The idea fits in two sentences. Under independent randomized runs, the log-probability that a whole schedule fails on an instance is a sum of per-run log-survival terms, so schedule selection becomes online linear optimization over an NP-hard set. The feedback from a truncated run reveals exactly the loss entries for time slices no longer than the one granted, which is a censored, prefix-shaped kind of partial feedback. The contribution has three parts: a stable, implementable replacement for the Ellipsoid step, an estimator that is aware of censoring, and the first empirical measurement of whether approximate-oracle online learning beats simple plug-in scheduling on real solver runtimes.
Core Claim
Fix a menu of time slices $\tau_1<\dots<\tau_K$ and a set of candidate runs $a$, where each run is a solver–seed stream placed on a core. A schedule is a binary vector $x$ with $x_{a,k}=1$ if run $a$ receives slice $\tau_k$. The schedule is feasible if each core's slices sum to at most the budget $B$. For instance $t$, let $S^a_t(\tau)$ be the probability that run $a$ has not solved the instance by time $\tau$. If runs with different seeds or solvers are independent given the instance, the schedule fails with probability $\prod_a S^a_t(\tau_{k(a)})$, where $k(a)$ is the slice assigned to run $a$. That gives the linear loss
$$\ell_t(x)=\sum_{a,k} x_{a,k}\,\max\{\log S^a_t(\tau_k),\ \log\varepsilon\},$$
where $\varepsilon>0$ is a floor that keeps losses bounded. Minimizing $\ell_t$ over feasible $x$ is a multiple-choice, multi-core knapsack problem. It is strongly NP-hard once the number of cores is part of the input, but greedy and LP-rounding algorithms give constant-factor approximations.
The claim has three parts. The first is that Garber's reduction applies to this loss once the Ellipsoid-based decomposition is replaced with a stable active-set cutting-plane routine. The second is that the censored feedback, which reveals $\ell_t$ on slices $\tau_j\le\tau_{k(a)}$ for every run actually executed, supports an estimator whose exploration cost falls between full information and bandit feedback. The third is that on real runtime benchmarks this learner beats plug-in scheduling when the instance stream drifts, and does no worse when it does not.
The novelty is not a new survival model. It is the combination of an α-oracle online learner with right-censored prefix feedback, together with an honest empirical test of a line of work that has none.
Research Program
The first component is a numerically stable decomposition step. Garber's separation-or-decomposition routine needs to express a point near the convex hull of feasible schedules as a mixture of oracle outputs, or else find a separating direction. We will replace the Ellipsoid with a working-set cutting-plane loop in the style of the 1-slack method from Cutting-plane training of structural SVMs. That method solves exponentially large constraint sets in a number of iterations independent of sample size, by repeatedly calling an oracle for the most violated constraint and re-solving a small quadratic program. We will add the "forget" rule from Project and Forget: Solving Large-Scale Metric Constrained Problems, which prunes inactive constraints from the working set and scaled to instances with trillions of constraints. In our setting, the oracle's cuts are feasible schedules returned by the approximation algorithm.
The analytical question is whether Garber's α-regret bound survives when the Ellipsoid is swapped for a method with a weaker worst-case iteration guarantee. We expect a bound that depends on the size of the working set rather than on dimension squared. We will prove what we can and measure the rest.
The second component is the censored estimator. Each executed run on instance $t$ yields one censored draw: either a solve time or a lower bound at $\tau_{k(a)}$. From that draw, the indicators "unsolved by $\tau_j$" are observed for all $j\le k(a)$ and hidden for longer slices. We will estimate per-slice losses with a Kaplan–Meier-style product estimator pooled across the concurrent runs on the instance. For longer slices we will use importance weighting, with exploration probability placed on schedules that extend some run to a longer slice. The prefix structure means that one long exploratory run informs every shorter slice. We expect this to make the exploration overhead much smaller than generic bandit exploration.
The log of an unbiased survival estimate is biased. We will therefore treat estimation error as bounded perturbation in the regret analysis and check empirically whether the bias matters. The deliberate contrast is with naive handling of censoring, which the survival literature has shown to be harmful. Treating a truncated run as a failure at its cutoff produces label bias (Loh et al.). Dropping truncated runs produces survival bias (Bello et al.).
The third component is the testbed and the evaluation protocol, which address the empirical gap directly. The seven runtime benchmarks used in Can Tabular Foundation Models Predict Algorithm Runtime Distributions? record 100 seeds per instance. They include pairs of solvers on the same instance families: Spear and YalSAT on QCP, and Spear and YalSAT on SWGCP. From this data we can compute each instance's empirical $S^a_t$ offline for scoring. We can also simulate any censored online interaction exactly, by truncating a recorded run at the slice the learner chose. The product form of the failure probability is justified here, because different seeds of a randomized solver are independent given the instance.
Baselines
The naive reference point is the single best solver: whichever solver solves the most training instances, run alone on all cores with independent seeds and the full budget. The ceiling is the virtual best schedule, meaning the best schedule per instance computed with hindsight from all 100 recorded seeds. It is not achievable, but it bounds the headroom.
The strongest competitor is a plug-in scheduler. After each instance it refits pooled Kaplan–Meier survival curves from all censored runs seen so far, then calls the same approximation oracle on those curves to choose the next schedule. This is follow-the-leader with a censoring-aware estimator. In an independent and identically distributed instance stream it should be close to optimal, and it is the baseline our method must actually beat.
The second strong competitor is the parametric approach of Dynamic Algorithm Portfolios. It fits extreme-value distributions to censored log-runtimes and reallocates time online. On its trap-problem portfolio, it reported cumulative training time about three orders of magnitude lower than a static algorithm-selection approach. That is the only relevant reported figure in the file. For the SAT and planning benchmarks, no reported result was found on Lacuna for portfolio success rate or regret.
The third competitor is the Kakade–Kalai–Ligett-style reduction that Garber improves on, which needs $O(T)$ oracle calls. It isolates Garber's oracle-efficiency claim. We will also include Garber's original Ellipsoid decomposition, implemented as faithfully as possible, to isolate the value of our stable replacement.
Two further ablations target the key ingredients. The first swaps our censoring-aware estimator for the two naive treatments of censoring, failure-at-cutoff and deletion. The second removes prefix sharing, so the learner treats each (run, slice) entry as an independent bandit arm.
All methods get the same fixed approximation oracle (greedy with a known factor), the same slice menu, the same budget $B$, and the same instance orderings. Each gets an equal hyperparameter-tuning budget on a held-out benchmark. Wall-clock time is measured on identical hardware.
Beating the plug-in scheduler means a statistically significant gain, across seeds of the instance ordering, in the fraction of instances solved within $B$ under drifting streams, with no significant loss under shuffled streams. It also means using no more oracle calls per round.
Why not just…?
Why not just use the plug-in Kaplan–Meier scheduler? This is a real threat. In a shuffled stream of instances from one benchmark, estimating survival curves and greedily scheduling may match or beat an online learner, which pays for hedging against adversaries that are not present. We will not argue around this. The experiments include shuffled streams precisely so we can report whether the plug-in scheduler wins there. The case for the proposal rests on drifting streams, where follow-the-leader is known to be exploitable. Examples are instances ordered by difficulty (as in the increasing-difficulty trap problems of Dynamic Algorithm Portfolios) or concatenations such as QCP followed by SWGCP. If the plug-in scheduler also wins under drift, the proposal's practical claim fails. The contribution then reduces to a negative empirical result on Garber-style methods, which the literature currently lacks entirely.
Why not just solve the allocation exactly with dynamic programming? With a single core, the problem is a multiple-choice knapsack over discretized slices, and a pseudo-polynomial dynamic program solves it exactly and cheaply. In that case the approximation oracle is unnecessary, and we will use the exact solver there as a sanity check. With several cores and restarts, the problem becomes strongly NP-hard, and the approximation oracle is then the realistic choice. We will report the core count at which exact solving stops being feasible within the per-instance decision time.
Why not just predict runtimes with a tabular foundation model and schedule on the predictions? Can Tabular Foundation Models Predict Algorithm Runtime Distributions? found TabPFN strong with as few as 32–64 context examples. It also found that TabPFN degrades beyond 2,048 context samples when repeated runs act as heteroscedastic noise, and that it has no native handling of censored runs. Both conditions are exactly what an online allocator produces. We will still run TabPFN, fed only uncensored runs, as a feature-aware predictor behind the same oracle. If it wins early in the stream, that points to a hybrid design rather than a refutation.
Proposed Experiments
The primary experiment runs every method over 20 random orderings under three stream regimes: shuffled, difficulty-sorted, and benchmark-concatenated. It uses the QCP and SWGCP solver pairs. Candidate runs are solver × seed-stream × core, and we test 1, 4, and 16 cores. The budget $B$ is set at three values that yield roughly 20%, 60%, and 90% censored runs. The high-censoring tier matters because survival-ranking work found that methods discarding information collapse at extreme censoring. Fast Training of Support Vector Machines for Survival Analysis reports Uno's c-index falling to 0.560 for a pair-pruning method on the 8.3%-event AIDS cohort, versus 0.711 for the full-information model.
The metrics are the fraction of instances solved within $B$, α-regret against the best fixed schedule in hindsight (computed offline with a mixed-integer solver on small configurations), oracle calls per round, and wall-clock time per decision.
Three results would settle the proposal. The first is whether the stable cutting-plane decomposition keeps oracle calls per round logarithmic in $T$ in practice, while the faithful Ellipsoid implementation diverges or stalls numerically. That would be the first measurement of the failure mode Garber warns about. The second is whether the censoring-aware estimator beats both naive treatments by a margin that grows with the censoring rate, as label-bias and survival-bias arguments predict. The third is whether the online learner beats the plug-in scheduler under drift while staying within noise of it on shuffled streams.
A secondary check tests the log-linear surrogate itself. We will compare against greedily maximizing the solved fraction directly, with no linearization. If the surrogate costs more than it saves, we will say so. Portability will be tested on LPG-Zenotravel, and on the 76-algorithm trap portfolio if its data can be reconstructed.
References
- Efficient Online Linear Optimization with Approximation Algorithms
- Cutting-plane training of structural SVMs
- Project and Forget: Solving Large-Scale Metric Constrained Problems
- Limitations of Binary Classification for Long-Horizon Diagnosis Prediction and Advantages of a Discrete-Time Time-to-Event Approach: Empirical Analysis
- Deep-learning cardiac motion analysis for human survival prediction
- Can Tabular Foundation Models Predict Algorithm Runtime Distributions?
- Dynamic Algorithm Portfolios
- Fast Training of Support Vector Machines for Survival Analysis