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.
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.
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