Statistical Regimes and Runtime Prediction

Barry Hurley, Barry O'SullivanIJCAI 2015

Introduction

In the fields of Satisfiability (SAT) solving and Constraint Programming (CP), a single run of a solver on a benchmark instance is traditionally treated as a definitive measure of performance. This "single-run" paradigm governs solver competitions, parameter tuning, and the development of empirical hardness models. However, this approach ignores a critical reality: modern solvers are inherently stochastic. By utilizing randomized heuristics for variable selection, tie-breaking, and restarts, solvers exhibit significant runtime variance. This paper, presented at IJCAI 2015, demonstrates that this variance is so high—often spanning several orders of magnitude on the same instance—that current evaluation methods are essentially "noisy."

Methodology and Data

To quantify this stochasticity, the authors conducted a large-scale empirical study. They re-evaluated the top three solvers from the 2014 SAT Competition—Lingeling, SWDiA5BY, and Riss BlackBox—by running each 100 times on 300 industrial instances. Since some solvers lacked native support for random seeds, the authors emulated randomness by "shuffling" input instances (renaming variables and reordering clauses), a technique that preserves problem structure while altering the solver's internal search path.

Detailed runtime statistics for specific instances, highlighting the extreme variance between minimum and maximum runtimes.

As shown in the data above, the variance on a single instance can be staggering. For example, on instance 008-80-4.cnf, Lingeling's runtime ranged from 142 seconds to a timeout at 3600 seconds, demonstrating that a single sample is a poor proxy for actual solver behavior.

The Instability of Solver Rankings

The most striking finding is the "Any Permutation" result. The performance gap between top-tier solvers is often smaller than the noise generated by their internal stochasticity. By modeling the "success rate" (instances solved within a timeout) as a random variable, the authors calculated 95% confidence intervals for solver performance.

Distribution of the number of instances solved across 100 runs for the top three solvers, illustrating significant overlap in performance.

The overlap in these distributions suggests that the 2014 SAT Competition podium was statistically unstable. While Lingeling officially took first place, the expected success rate analysis suggested that SWDiA5BY might be the superior solver on that specific instance set when considering the full distribution of possible outcomes.

Predictive Fragility and Statistical Regimes

The paper also explores "predictive fragility" in runtime modeling. Standard Random Forest models trained to predict a solver's median runtime fail significantly when tasked with predicting worst-case (maximum) runtimes. This indicates that current empirical hardness models capture only a "thin slice" of solver behavior. The authors argue that models should instead aim to predict the parameters of the runtime distribution, allowing for risk-aware solver selection.

Conclusion

The study highlights the need for more robust statistical comparisons in combinatorial search. Moving forward, the community should transition from simple mean-based rankings to tests like the Kolmogorov-Smirnov test. While the computational cost of gathering 100 samples per instance is high, understanding these "statistical regimes" is essential for building reliable solver portfolios and ensuring that competition rankings reflect true algorithmic superiority rather than random noise.

Summary updated

BibTeX
@inproceedings{hurley2015statistical,
  author = {Barry Hurley and Barry O'Sullivan},
  title = {{Statistical Regimes and Runtime Prediction}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure