Solver Runs as Censored Counts: Nonnegative Factorization for Algorithm Selection

Picking which solver to run on a hard problem, such as a satisfiability formula or a constraint program, is usually done by computing hand-designed descriptors of the instance and feeding them to a model that predicts each solver's runtime. This works well, but it has three weaknesses. The descriptors can cost as much as solving the problem. Most of the training data are timeouts, which tell you only that the runtime exceeded the cutoff. And the full table of every solver on every instance is expensive to collect. We propose to treat the table of solver runs as data from a survival process: each run either finishes, which is an event, or is cut off, which is censored. We then model that table with a nonnegative low-rank factorization. The model is the exact counterpart of Kullback–Leibler nonnegative matrix factorization (NMF), so it can be fit with the same simple multiplicative updates.

The point of the construction is that one likelihood handles timeouts, missing training runs, and short "probe" runs of any length on a new instance, with no ad-hoc penalties. A new instance can then be routed using only a few seconds of actual solver runs. The model decides which solver to probe next from its uncertainty about the instance's latent mixture of "hardness profiles".

Core Claim

The statistical reading of NMF says that minimizing generalized KL divergence is the same as maximizing a Poisson likelihood. Ding et al. prove this equivalence with probabilistic latent semantic indexing, and Raj et al. show that the multiplicative updates coincide with expectation–maximization for latent class models and extend naturally to tensors. A standard survival-analysis identity says that a piecewise-constant-hazard model of censored times has exactly a Poisson likelihood, with the event indicator as the count and the time at risk as the exposure. Putting the two together gives the model we propose.

Instance $i$, solver $j$, and log-spaced time bin $b$ get hazard

$$\Lambda_{ijb} = \sum_{k=1}^{K} W_{ik} H_{kjb}, \qquad \log L = \sum_{i,j,b} \big( \delta_{ijb} \log \Lambda_{ijb} - e_{ijb} \Lambda_{ijb} \big),$$

where the symbols are defined as follows:

  • $W_{ik} \ge 0$ is instance $i$'s weight on latent profile $k$.
  • $H_{kjb} \ge 0$ is how quickly solver $j$ finishes on profile $k$ during bin $b$.
  • $\delta_{ijb}$ is 1 if the run finished inside bin $b$ and 0 otherwise.
  • $e_{ijb}$ is the time the run spent inside bin $b$.

Up to constants, this is a weighted KL-NMF of the event tensor $\delta$ against $e \circ \Lambda$. It has the following properties:

  • A timeout contributes exposure with no event.
  • A one-second probe contributes one second of exposure.
  • An unrun pair contributes zero exposure, so it is simply missing.
  • The probability that solver $j$ finishes instance $i$ within a budget follows in closed form, as one minus the exponential of the accumulated hazard.
  • Piecewise hazards allow the heavy-tailed, "fast or never" behaviour typical of combinatorial solvers.

Our claim is empirical and testable. When instance descriptors are unavailable, expensive, or must be charged to the clock, this censored factorization plus adaptive probing will choose solvers better than three alternatives:

  • the existing feature-free latent class approach;
  • low-rank models fit to penalized runtimes;
  • random forests on fixed probe outcomes.

It will also degrade gracefully when the training table is heavily censored or sparse.

Relation to Prior Work

The closest work is Latent Class Models for Algorithm Portfolio Methods. It clusters instances into hard latent classes, models discretized solver outcomes with multinomial and Dirichlet-compound-multinomial mixtures trained by expectation–maximization, and updates class beliefs online from short solver runs. It motivates our proposal, because it shows solver behaviour alone can beat feature-based selection on 2009 SAT Competition data. We differ in three ways:

  • Our likelihood is a censored hazard with exposure rather than a categorical outcome, so runs of arbitrary length and cutoffs at arbitrary times enter correctly.
  • Instances have mixed membership across profiles rather than a single class.
  • Fitting reduces to weighted KL-NMF, which brings the identifiability and regularization tools of the NMF literature.

OBOE supplies the online idea we adapt. It factorizes a dense dataset-by-model error table with principal component analysis, probes a few models chosen by experiment design, and projects their results to fill in the rest. It assumes a densely observed, Gaussian-noise table, which is exactly what censored runtime tables violate. We keep its probe-then-project structure but replace the loss.

Tornede and Wever cast selection as recommendation with a neural Plackett–Luce ranker over instance and algorithm descriptors. Like us, they argue that regressing raw runtimes is distorted by timeouts. Their answer is to drop magnitudes and learn rankings. Ours is to keep magnitudes through a censored likelihood, which a budgeted schedule needs.

The graph side of the NMF literature constrains what we may claim. Zhang et al. show that the noise model determines which factorization corresponds to a block-model likelihood, and that the probabilistic and algebraic solvers behave differently depending on how clean the clusters are. Mao et al. prove that mixed-membership factors are identifiable only when each community has "pure" members and interactions are diagonal. We therefore treat interpretable solver profiles as something to check, by looking for near-pure instances, rather than something guaranteed. We also treat the local minima reported by Ding et al. as a reason to use multiple restarts.

Research Program

Offline model. We build the exposure-weighted Poisson tensor factorization above. We place Gamma priors on $W$ and $H$ so that the conditional updates are conjugate, which gives cheap posterior uncertainty for a new instance's row of $W$. The number of profiles $K$ and the time bins are chosen by held-out censored likelihood.

Online stage. The learned $H$ is held fixed. Each new instance starts from the prior over its weights. After each probe, the posterior over those weights is updated with the same multiplicative updates restricted to one row. The next action is chosen by a simple rule: either run the solver with the highest posterior probability of finishing per second of remaining budget, or spend a short probe on the solver whose outcome most reduces uncertainty about that quantity. We deliberately keep this rule simple and identical across model variants, so that differences in results come from the model.

Extension: instance descriptors as side information. When descriptors are available, we couple a second nonnegative factorization of the descriptor matrix sharing $W$, in the spirit of tri-factorization. A cold instance with descriptors but no runs then has an informed prior.

Analysis. We will examine whether learned profiles align with known instance families in ASlib scenarios, such as random versus industrial SAT, and with solver types.

Baselines

The naive reference points are the single best solver per scenario and the virtual best solver, which is an oracle that knows the fastest solver per instance. Every method is reported as the fraction of the gap between these two that it closes, alongside raw penalized average runtime (PAR10: timeouts are charged as ten times the cutoff).

AutoFolio. The strongest existing method is AutoFolio. It configures preprocessing, feature selection, the selection model, feature-time caps and pre-solving schedules with SMAC. It reports average speedups of 1.3 to 15.4 over the single best solver across the 13 ASlib 1.0 scenarios, new best results on 7 of 13 scenarios, and nearly 4x over SATzilla'11 on SAT12-RAND, at roughly 2 CPU days of configuration per scenario. We will run it with the official ASlib cross-validation splits and its own configuration budget. Our model gets an equal or smaller budget for choosing $K$, bins and priors.

Per-algorithm random forest. From ASlib, per-algorithm random regression forests on instance descriptors were best on 13 of 17 ASlib 2.0 scenarios. We will run it on the same folds, charging descriptor computation time. The file reports no per-scenario PAR10 values for either baseline ("no reported result found on Lacuna for per-scenario ASlib PAR10"), so we will reproduce both rather than quote them.

Probe-landmark forest. This is the most direct threat. A random forest takes as input the censored outcomes of a fixed set of short probe runs, using the same total probe seconds as our method.

Feature-free latent class reimplementation. This is a hard-class, discretized-outcome model following Silverthorn and Miikkulainen. On 2009 SAT Competition data they report 424.2 versus SATzilla's 407.5 random instances solved, 129.4 versus 125.6 crafted, and 146.0 versus 137.6 industrial. We will run it on ASlib data with identical probe budgets.

OBOE-style selector. This uses principal component analysis on PAR10-imputed log runtimes, with the same probes and projection.

Ablations. Two ablations isolate our key ingredients:

  • The same nonnegative factorization fit to PAR10-imputed values, which keeps the factorization but drops the censored likelihood.
  • The same censored likelihood with hard single-class membership, which drops mixed membership.

A third comparison, fixed versus adaptive probe order, isolates the value of posterior-guided probing.

What counts as success. In the feature-free and feature-charged regimes, the method must close more of the single-best-to-virtual-best gap than every probe-based baseline in a clear majority of the 17 ASlib 2.0 scenarios. It must also beat the PAR10-imputed ablation, which shows that the likelihood rather than the low-rank structure does the work. In the full-descriptor regime, we count matching AutoFolio within fold-to-fold variation as success, and the coupled model improving on it as a bonus.

Why not just…?

Why not just use AutoFolio or a random forest on instance descriptors? Where descriptors are cheap and the training table is complete, this may well win, and we do not claim otherwise. AutoFolio's need for a dedicated feature-time cap and pre-solving schedules shows that descriptor cost is a real constraint. Silverthorn and Miikkulainen's results show that solver behaviour alone can match descriptor-based selection. Our experiments separate the regimes explicitly: descriptors free, descriptors charged, and descriptors unavailable. That way, a loss to AutoFolio in the first regime is reported as such, not argued away.

Why not just feed short probe outcomes into a random forest? This is the most serious alternative, because it uses the same information as our method. Its limits are structural: it needs the same probes on every instance, it treats a probe that timed out at one second as a fixed feature value, and it cannot reuse sparse training runs that lack those probes. If it matches our method at equal probe seconds on full ASlib tables, then the factorization adds nothing beyond convenience. We would then pivot the contribution to the sparse-training regime, which the next experiment tests directly.

Why not just do OBOE-style low-rank completion on penalized runtimes? The PAR10-imputed ablation is exactly this question with nonnegativity added. If it performs as well as the censored model, the statistical interpretation is decorative. We expect it to fail most where censoring is heaviest, because PAR10 imputation turns every timeout into the same large value regardless of cutoff. We will report the results stratified by each scenario's timeout fraction.

Why not just run a static parallel portfolio? Petrik et al. avoid all inference by sharing CPU across solvers. We include the best static schedule learned from the training folds as a baseline. Instance-specific gains like AutoFolio's suggest that static schedules leave much of the oracle gap open, but we will measure this rather than assume it.

Proposed Experiments

All experiments use the ASlib 2.0 scenarios with their 10-fold splits. ASlib stores the complete runtime, or timeout, for every solver on every instance, so a probe of $b$ seconds can be simulated exactly as the minimum of the true runtime and $b$. One caveat follows: ASlib records single runs, so run-to-run variance of randomized solvers ("burstiness") cannot be simulated, and we will not claim to model it.

The first decisive check is the feature-free comparison at matched probe budgets, against the latent class, OBOE-style and probe-forest baselines.

The second is a sparsity stress test. Training runs are re-censored at progressively lower cutoffs and random entries are removed. We then measure how the fraction of oracle gap closed degrades for each method. The prediction is that the censored model degrades least, because it uses partial runs as exposure rather than discarding or imputing them.

The third is the likelihood ablation stratified by timeout fraction.

The fourth checks calibration of the predicted finish-within-budget probabilities on held-out instances. If these are badly calibrated, the online rule has no basis.

Finally, we test the coupled-descriptor model against AutoFolio with descriptor time charged. The 2009 SAT Competition suite serves as a secondary check against the published latent class numbers.