Algorithm Runtime Prediction: Methods & Evaluation
Frank Hutter, Lin Xu, Holger H. Hoos, Kevin Leyton-Brown
cs.AI, cs.LG, cs.PF, stat.ML
2012-11-06
Random forests predict SAT/MIP/TSP solver runtime from instance features within a factor of 3, generalize to unseen instances and parameter settings, and need only a few hundred runs.
NP-complete problems are everywhere, and SAT, mixed-integer programming (MIP), and the travelling salesperson problem (TSP) are the three most studied. Worst case they are intractable, but the instances that actually show up in practice are usually solvable. The real trouble is runtime variance: with problem size held fixed, a single solver can swing across orders of magnitude from instance to instance, and the same instance can take wildly different times under different solvers. There is no theory that explains why.
For roughly a decade the pragmatic answer has been to fit a supervised regression model to how long an algorithm will run on a given instance, what the paper calls an empirical performance model (EPM). Inputs are instance features (variable counts, graph structure, statistics from a 2-second probe run); the output is log runtime. These models underpin algorithm selection (SATzilla-style portfolios), parameter tuning (SMAC), and benchmark generation. This 2014 Artificial Intelligence journal paper, from Hutter, Hoos, and Leyton-Brown at UBC, is the foundational synthesis-and-advance for the area: better models, fuller feature sets, the largest experiments to date, and a sounder treatment of prematurely terminated runs.
The EPM setup is simple: concatenate instance features and algorithm parameters into one input vector and regress log runtime. The log matters because runtime spans orders of magnitude and is unmodelable in linear space. The paper systematically compares six model families: two ridge-regression variants (RR with two-phase forward selection, SPORE-FoBa forward-backward), a single-hidden-layer neural network, Gaussian processes, regression trees, and their two additions, an approximate Gaussian process (projected process) and random forests.
Each new choice has a reason:
On features they assembled 138 for SAT, 121 for MIP, and 64 for TSP, with two new families: probing features (run an existing solver for two seconds and read its trajectory, such as how many clauses Zchaff learned, what CPLEX presolve found, and local-minimum statistics from Concorde/LK on TSP) and timing features (how long each feature group took to compute). Probing transfers: a probe from one family, say local search, helps predict a different family, say tree search.
Eleven solvers, thirty-five instance distributions, three prediction regimes. On new instances, Minisat runtime on the mixed competition set spans about six orders of magnitude, and random forests reach an RMSE of 0.47 in log10 runtime, which works out to an average misprediction of under a factor of 3.
| Dataset | Model | log10-runtime RMSE |
| Minisat 2.0-COMPETITION | Random forest | 0.47 |
| Minisat 2.0-COMPETITION | Ridge regression (RR) | 1.01 |
| CPLEX-BIGMIX (heterogeneous) | Random forest | 0.64 |
| CPLEX-BIGMIX (heterogeneous) | Ridge regression (RR) | 2.7x10^8 |
Random forests are the overall winner: best on every SAT benchmark, best on the heterogeneous MIP set BIGMIX, and cheap to train at 0.1 to 11 seconds. Ridge regression blows up on BIGMIX, hitting RMSE 2.7x10^8 from a few outliers. Tree methods win on heterogeneous data because they model separate regions of the input space independently instead of letting distant points tug at each other.
Feature economics are clear too: on SAT, features up to the moderate cost tier match the full set at far lower computation cost, and the new features improve MIP in 11 of 12 cases. Hyperparameter optimization (DIRECT, 30 evaluations) yields only marginal gains while slowing training by up to a factor of 3000, not worth it in practice.
Move to new parameter configurations (SPEAR has 8.34x10^17 configurations, CPLEX 1.90x10^47) and the projected process is best overall thanks to the Hamming kernel, with random forests close behind; both beat regression trees, the prior workhorse for categorical configuration spaces. Neural networks and SPORE-FoBa do poorly, evidence that picking the right feature combinations is not trivial.
The hardest case is generalizing to unseen instances and unseen configurations at once. These experiments burned 60 CPU-years, but the finding is that the best models handle both new instances and new configurations almost as well as either alone, and a few hundred data points suffice to push the predicted-versus-true correlation above 0.9 (CPLEX-CORLAT needs only 30). In practice, 150 runs at a 300-second cutoff take 12.5 hours on one machine, enough to build a usable performance model overnight.
This is the methodological root of modern AutoML and hyperparameter optimization. SMAC, Hutter later tool, and the broader family of Bayesian-optimization hyperparameter search all run the same loop the paper codifies: learn a performance model, use it to pick the next configuration to try, run it, feed the result back (SMBO). For practitioners the direct use is that if you are tuning a solver or model whose runs are expensive, a random forest plus a few hundred runs gives a usable performance surrogate, and it handles categorical hyperparameters and timed-out censored runs natively, which is exactly the real tuning situation.
Honestly, this is a 2014 paper about combinatorial solvers, not about large language models, and absolute numbers tied to Minisat 2.0 and CPLEX 12.1 do not transfer. What does transfer is the methodological verdict: random forests are reliably strongest on this class of task, small data is enough, and censored data needs dedicated handling. Those conclusions have held up over the decade since.
Random forests extrapolate poorly beyond observed data, and the authors say so: predicting very long runs from training data with short captimes is a job for other models. With a fixed captime, their censored-data handling is unbiased only out to about 2kappa, negligible against orders-of-magnitude spread, so it really needs instance-specific captimes to be useful.
The whole framework depends on hand-designed, problem-specific instance features written by a domain expert; it is not a drop-in predictor for an arbitrary algorithm, and prediction quality is capped by feature quality. Reproducibility is gated on serious compute: the joint-space experiments took 60 CPU-years. Solvers and hardware are a decade old, so absolute numbers are dated.