Treating Unfinished Solver Runs as Censored Data in Parallel Online Algorithm Selection

Online algorithm selection learns which solver to run on each incoming hard instance, such as a SAT formula or a constraint problem, and updates its runtime predictions as results come in. Every method in this literature assumes the result of one run arrives before the next decision is made. Real solver farms do not work that way. Many instances run in parallel, a fast solver reports back in milliseconds, and a slow or doomed run reports back hundreds of seconds later. The feedback delay is therefore correlated with the very quantity being learned. While a bad solver's slow runs are still in flight, the learner sees only that solver's fast successes, so it grows overconfident and keeps routing new instances to it. This is the worst kind of feedback lag: it is long exactly where the news is bad.

We propose to remove this delay rather than tolerate it. A run that has been executing for $e$ seconds without finishing is not missing information. It is a right-censored observation: we know its runtime exceeds $e$. The censored-feedback machinery that already handles solver timeouts can therefore absorb in-flight runs at every decision point. Each pending run is treated as censored at its current elapsed time, and that contribution is revised as the run continues and eventually finishes. Stochastic approximation is the theory of noisy iterative updates and their limiting ordinary differential equations (ODEs). Under the usual "wait until it finishes" update, the learner tracks a delay-differential equation, which can lose stability abruptly as the delay grows. We expect progressive censoring to restore a delay-free mean ODE with the same fixed point. The proposal builds this update, proves when it converges, and tests it on ASlib replayed through a simulated parallel solver farm.

Core Claim

In parallel online algorithm selection, the learner has a choice. It can wait for completions, which gives it exact but stale data. It can drop pending runs, which biases it toward fast outcomes. Or it can use progressive censoring, which gives it current but weak data. We claim progressive censoring is the right choice for two reasons. The censoring threshold, the elapsed wall-clock time, is independent of the true runtime given that the run has not yet finished. The censored likelihood therefore still has the true parameters as its stationary point. And because the information lag is zero, the stability limit that delay imposes on step size disappears.

The concrete model follows Machine Learning for Online Algorithm Selection under Censored Feedback: log-runtime of solver $a$ on an instance with features $x$ is $y = \theta_a^\top x + \sigma\epsilon$, with Gaussian $\epsilon$. Our update is a stochastic gradient step on the censored log-likelihood of all currently available information:

$$\theta_{k+1} = \theta_k + \alpha_k \Big( \sum_{i \in \mathcal{D}_k} g(\theta_k; x_i, y_i) + \sum_{j \in \mathcal{P}_k} \big[ h(\theta_k; x_j, \log e_{j,k}) - h(\theta_k; x_j, \log e_{j,k-1}) \big] \Big).$$

Here $\mathcal{D}_k$ is the set of runs that completed at step $k$ and $g$ is their uncensored log-likelihood gradient. $\mathcal{P}_k$ is the set of runs still pending, $e_{j,k}$ is the elapsed time of pending run $j$ at step $k$, and $h$ is the censored gradient, the derivative of $\log P(y > \log e \mid x)$. The bracketed difference replaces a pending run's old censored contribution with its newer, tighter one. When a pending run finally completes, its last censored term is withdrawn and the exact term $g$ added.

A cutoff timeout is the special case where $e$ reaches the cutoff $C$. The method therefore contains the sequential Buckley-James and Thompson approach of Tornede et al. when there is one worker.

Relation to Prior Work

Two papers motivate the proposal by establishing online selection while leaving delay untouched. Online Algorithm Selection frames selection as a contextual bandit evaluated on streams carved from ASlib tables. It finds that greedy online updating beats a static offline regression forest on 15 of 18 scenarios, while ε-greedy and UCB exploration often lose even to the offline model. Tornede et al. add survival-analysis imputation for timeouts and report roughly 6% lower PAR10 than Degroote's approach. PAR10 is penalized average runtime, which counts each timeout as ten times the cutoff. Both papers process feedback in lockstep, and neither analyzes stability. We keep their model class and their censoring idea, and change what counts as a censored observation and when it is used.

Two papers supply the analytical method. Constant step-size stochastic approximation with delayed updates shows that delayed updates track a delay-differential equation with lag equal to step size times delay. Their synthetic system with step size 0.1 converges at delay 6 and diverges violently at delay 7. This gives us the predicted failure mode of the wait-for-completion baseline. That analysis assumes delay independent of the update; in solver farms delay depends on the outcome, and we must handle this. It also assumes bounded iterates a priori, which we hope to avoid. For that we plan to borrow the running-max boundedness argument of Convergence of Two-Timescale Markovian Stochastic Approximations with Applications in Reinforcement Learning. The natural two timescales are the fast churn of pending-run states and the slow parameter vector.

On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems supports the decaying step size $\alpha_k = \Theta(1/k)$ we use for the last-iterate result, and the emphasis on single-run convergence.

Static parallel portfolios (Learning Static Parallel Portfolios of Algorithms) also use parallelism, but they split CPU time across solvers offline instead of learning per instance. AutoFolio represents strong offline configured selection. Neither addresses streaming feedback.

Research Program

The theoretical part characterizes the mean ODE of the progressive-censoring recursion. This ODE also includes the selection policy, because which solver runs depends on $\theta$. We will show that the true parameters are a stationary point whenever the elapsed-time process is independent of the runtime given non-completion. Local asymptotic stability follows from concavity of the Gaussian censored likelihood in a suitable reparametrization, a property we will verify rather than assume.

We will then compare this ODE with the delay-differential equation the wait-for-completion update tracks. The aim is to derive the critical delay, expressed through the worker count and the runtime distribution, beyond which waiting destabilizes constant-step learning. A plausible but unproven intermediate result is that dropping pending runs has a biased fixed point, shifted toward fast solvers in proportion to the in-flight fraction. If we can prove it, it would explain the burst-routing failure.

The empirical part builds a replay simulator. Instances arrive as a Poisson stream onto $W$ workers. Each routed run's duration is its recorded ASlib runtime, capped at the scenario cutoff, so completions arrive out of order exactly as they would on real hardware. Every policy uses Thompson sampling over the same linear model, so they differ only in how they use pending information.

Baselines

The naive reference points are the single best solver from the training split, which needs no learning, and the virtual best solver as the oracle lower bound on PAR10. All regret numbers are reported against the oracle.

The strongest existing method is bj_thompson from Tornede et al. We run it in three ways, all with the same features, warm-start split, prior, and Thompson sampling. First, we run it sequentially with $W = 1$, its native setting. Second, we run it in parallel, updating only on completion. Third, we run it in parallel, treating pending runs as absent. Its reported result is about a 6% average PAR10 improvement over Degroote's method across ASlib v4.0 scenarios. The file gives no absolute per-scenario PAR10 values, so we will reproduce those numbers ourselves before comparing.

Degroote's greedy online regression is the second learned baseline. For context only, we include an offline random forest and AutoFolio under its reported regime. AutoFolio reports speedups of 1.3 to 15.4 over the single best algorithm on ASlib 1.0 after about 2 CPU days of configuration per scenario.

The key ablation isolates the revision step. It treats pending runs as censored once, at dispatch-plus-epsilon, without later tightening, so it tests whether timely censored information or merely acknowledging pending runs drives any gain. A second ablation swaps decaying for constant step size.

Beating the baselines means two things. Progressive censoring must reach lower stream-averaged PAR10 than wait-for-completion bj_thompson at matched $W$ on most scenarios, with the gap widening as $W$ grows. And it must stay within a few percent of sequential bj_thompson while processing instances roughly $W$ times faster in wall-clock terms.

Why not just…?

Why not just wait for completions and shrink the step size? Delay theory says a small enough step restores stability, so this is the real threat. It does not, however, fix the policy-level problem. While a bad solver's slow runs are pending, Thompson sampling keeps drawing optimistic predictions for it and dispatches more instances to it. Those wasted runs cost PAR10 regardless of how gently the parameters move. The worker-count sweep settles the question directly. If tuned-step wait-for-completion matches progressive censoring at $W = 64$, our method offers no practical advantage, and we would report that.

Why not just treat every pending run as a timeout at the cutoff? This is a maximally pessimistic imputation. It biases the learner against slow but successful solvers, and it penalizes exactly the hard instances where specialist solvers earn their value. It is included as an extra baseline. We expect it to underperform on scenarios with many long successful runs, such as QBF and CSP.

Why not run selection sequentially, or use a static parallel portfolio? Sequential processing discards the parallelism a farm exists to provide. Static portfolios split compute across solvers on every instance. Petrik and Zilberstein report a 37% mean-time reduction over the best single solver on Sat-Ex, but instance-level routing exploits heterogeneity that fixed shares cannot. Neural Solver Selection for Combinatorial Optimization finds the best individual solver wins only about 40% of instances. We report a static-share portfolio, fitted on the warm-start data, at equal total CPU as a reference.

Proposed Experiments

We will use the ASlib v4.0 scenarios evaluated by Tornede et al., including the SAT, CSP and QBF families, with Degroote's split: 10% warm start, 80% stream, 10% held-out test. Worker counts are $W \in \{1, 4, 16, 64\}$, with arrival rates set so the farm runs at 50% and 90% utilization. Metrics are stream-averaged PAR10, regret to the virtual best solver, held-out PAR10 of the final model, parameter-error trajectories on a synthetic scenario with known $\theta$, and the fraction of runs in which parameters diverge or oscillate.

There are three decisive checks. First, the wait-for-completion baseline should degrade sharply beyond a worker count close to our derived critical delay, while progressive censoring does not. Second, on synthetic streams with known parameters, drop-pending should converge to a measurably shifted fixed point while progressive censoring converges to the truth. Third, the no-revision ablation should recover only part of the gain. If the first check fails at realistic worker counts, the delay story is weaker than claimed, and the contribution reduces to the bias correction alone.