# A Bayesian Approach to Tackling Hard Computational Problems

arXiv: https://arxiv.org/abs/1301.2279 · HTML: https://mlsanity.com/paper/1301.2279/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Jan 2013.

## Built on by (most cited first, 5 of 5)

- [What Can Transformers Learn In-Context? A Case Study of Simple Function Classes](https://mlsanity.com/paper/2208.01066/) (2022)
- [From Medprompt to o1: Exploration of Run-Time Strategies for Medical Challenge Problems and Beyond](https://mlsanity.com/paper/2411.03590/) (2024)
- [Improved Sample Complexity Bounds for Branch-and-Cut](https://mlsanity.com/paper/2111.11207/) (2021)
- [Formalizing Preferences Over Runtime Distributions](https://mlsanity.com/paper/2205.13028/) (2022)
- [Arbitrarily Large Labelled Random Satisfiability Formulas for Machine Learning Training](https://mlsanity.com/paper/2211.15368/) (2022)

## Abstract (arXiv)

We are developing a general framework for using learned Bayesian models for decision-theoretic control of search and reasoningalgorithms. We illustrate the approach on the specific task of controlling both general and domain-specific solvers on a hard class of structured constraint satisfaction problems. A successful strategyfor reducing the high (and even infinite) variance in running time typically exhibited by backtracking search algorithms is to cut off and restart the search if a solution is not found within a certainamount of time. Previous work on restart strategies have employed fixed cut off values. We show how to create a dynamic cut off strategy by learning a Bayesian model that predicts the ultimate length of a trial based on observing the early behavior of the search algorithm. Furthermore, we describe the general conditions under which a dynamic restart strategy can outperform the theoretically optimal fixed strategy.