Lightweight Online Learning for Sets of Related Problems in Automated Reasoning

Haoze Wu, Christopher Hahn, Florian Lonsing, Makai Mann, Raghuram Ramanujan, Clark W. Barrett

Abstract

We present Self-Driven Strategy Learning (SDSL), a lightweight online learning methodology for automated reasoning tasks that involve solving a set of related problems. SDSL does not require offline training, but instead automatically constructs a dataset while solving earlier problems. It fits a machine learning model to this data which is then used to adjust the solving strategy for later problems. We formally define the approach as a set of abstract transition rules and describe a concrete instance using conditional sampling for data generation and random forests for modeling. Implemented on top of the Kissat solver, SDSL certifies larger bounds and finds more counter-examples than state-of-the-art bounded model checking approaches on hardware benchmarks.

Introduction

Many automated reasoning tasks, such as Bounded Model Checking (BMC) or symbolic execution, involve solving a sequence of highly related problems. Traditionally, researchers use meta-algorithmic techniques—like algorithm selection or hyperparameter tuning—to find optimal solver settings. However, these methods typically require an expensive offline phase, necessitating a massive pre-existing dataset and significant training time. This limits their utility when the problem at hand deviates from the training distribution.

Self-Driven Strategy Learning (SDSL) addresses this by moving the learning process entirely online. By learning from earlier problems in a sequence to solve later ones more efficiently, SDSL eliminates the need for offline training and allows solvers to adapt dynamically to the specific problem set.

Methodology: The SDSL Framework

SDSL builds its own dataset as it progresses through a problem sequence. The process consists of three primary phases:

  1. Collection: While solving initial problems, SDSL occasionally re-solves them using different parameter settings (strategies). It employs Markov-Chain Monte-Carlo (MCMC) sampling to explore the strategy space, prioritizing those that show promise.
  2. Training: A Random Forest model is fitted to the collected data. This model learns to predict the "cost" of a strategy—measured by the number of solver conflicts—based on the problem's index in the sequence. Using conflicts as a metric provides a more stable and reproducible proxy for performance than wall-clock time.
  3. Strategizing: For subsequent problems, the system uses the trained model as an oracle to select the strategy predicted to be the most efficient.
SDSL initially invests time to learn a strategy that eventually outperforms the baseline KISSAT solver by reaching deeper bounds faster.

As illustrated in the performance plot above, SDSL initially takes longer than a standard solver because it is busy "learning" through sampling. However, this investment pays off rapidly as it discovers a superior strategy that allows it to solve deeper bounds much faster than the baseline.

Experimental Evaluation

The approach was evaluated using benchmarks from the 2020 Hardware Model Checking Competition (HWMCC’20), focusing on 24 unsolved bitvector benchmarks and 65 satisfiable benchmarks with known property violations.

The results demonstrate that lightweight online learning can beat specialized tools. On 22 out of 24 unsolved benchmarks, KISSAT + SDSL certified larger bounds than the baseline, with an average increase of 3.9 steps. Furthermore, the solver achieved a 1.7x raw speedup on average after the learning phase. For benchmarks with known bugs, SDSL found counter-examples significantly faster and solved 7 instances that were not solved by other top-tier model checkers like AVR or PONO.

Detailed performance comparison of KISSAT + SDSL against baseline solvers across various hardware benchmarks.

Conclusion

SDSL demonstrates that lightweight online learning can effectively compete with and even surpass heavyweight specialized tools. While highly effective, the approach's success depends on a well-defined strategy space and a sufficiently long sequence of problems to allow for effective learning. Future work will explore applying SDSL to other domains like symbolic execution and MaxSAT, as well as automating strategy space construction and integrating with incremental solving techniques.

Summary updated

Abstract

We present Self-Driven Strategy Learning ($\textit{sdsl}$), a lightweight online learning methodology for automated reasoning tasks that involve solving a set of related problems. $\textit{sdsl}$ does not require offline training, but instead automatically constructs a dataset while solving earlier problems. It fits a machine learning model to this data which is then used to adjust the solving strategy for later problems. We formally define the approach as a set of abstract transition rules. We describe a concrete instance of the sdsl calculus which uses conditional sampling for generating data and random forests as the underlying machine learning model. We implement the approach on top of the Kissat solver and show that the combination of Kissat+$\textit{sdsl}$ certifies larger bounds and finds more counter-examples than other state-of-the-art bounded model checking approaches on benchmarks obtained from the latest Hardware Model Checking Competition.
BibTeX
@inproceedings{wu2023lightweight,
  author = {Haoze Wu and Christopher Hahn and Florian Lonsing and Makai Mann and Raghuram Ramanujan and Clark W. Barrett},
  title = {{Lightweight Online Learning for Sets of Related Problems in Automated Reasoning}},
  booktitle = {FMCAD},
  year = {2023},
  url = {https://openreview.net/forum?id=b2UyU87TA0},
}

Loading related content...

Figure