Combinatorial search algorithms often exhibit highly erratic behavior: a solver might find a solution to a problem instance in milliseconds, yet hang indefinitely on a seemingly identical instance. In Heavy-Tailed Distributions in Combinatorial Search, Carla P Gomes et al. demonstrated that this phenomenon is mathematically rooted in heavy-tailed cost distributions. In these power-law distributions, the probability of encountering an exceptionally long-running search path decays slowly, leading to a massive or even infinite variance in runtime.
This erratic behavior means that a solver can easily get trapped in an unproductive, deeply nested branch of a search tree. As Tad Hogg et al. observed in Expected Gains from Parallelizing Constraint Solving for Hard Problems, this issue is particularly acute around the phase transitions of hard problems, where a small fraction of search paths incur extremely high computational costs that are unrepresentative of the typical solution time.
The Intuition Behind Randomized Restarts
To understand why abandoning a search and starting completely over makes it faster, consider how a typical backtracking solver explores a search tree. At the highest levels of the tree, the solver makes critical branching decisions. If it makes an incorrect choice early on, it can become trapped in a massive, solution-less subtree, spending exponential time backtracking through irrelevant variables.
The intuition behind randomized restarts is to redistribute computational resources away from these stagnant subtrees and toward the high-probability success region typically found at the beginning of a search. Because the runtime distribution is heavy-tailed, a significant portion of the success probability is concentrated in the very early stages of a run—the "short-tail" region. If a run does not succeed quickly, it is highly likely to be trapped in an exponential backtracking loop.
By introducing controlled randomization into the solver's heuristics or initial conditions and enforcing a strict cutoff, we can truncate these catastrophic long tails. In Boosting Combinatorial Search Through Randomization, Carla P Gomes et al. showed that terminating a search after a predefined budget and re-initializing with a new random seed transforms the overall runtime distribution, turning exponential-time failures into predictable distributions with a finite mean.
The mathematical optimality of this approach was analyzed by Rémi Monasson in Exponentially hard problems are sometimes polynomial, a large deviation analysis of search algorithms for the random satisfiability problem, and its application to stop-and-restart resolutions. The author demonstrated that a stop-and-restart mechanism employing a linear-time cutoff can achieve an exponential speedup by repeatedly attempting to find rare, highly efficient search trajectories.
Designing Restart Schedules
The critical challenge in implementing this strategy is determining the optimal cutoff time. If the cutoff is too short, the solver may never reach a solution that requires a deeper search; if it is too long, the solver wastes time in dead ends.
Fixed and Geometric Cutoffs
Early strategies used a fixed threshold. However, Toby Walsh proposed randomized geometric restarts in Search in a Small World, where the search cutoff increases by a constant factor after each failed attempt. This ensures that the solver can still exploit short runs while guaranteeing it will eventually scale up to solve exceptionally hard instances.
Universal Sequences
To avoid needing prior knowledge of the runtime distribution altogether, researchers leverage universal restart sequences, such as the Luby sequence. In The Effect of Restarts on the Efficiency of Clause Learning, Jinbo Huang demonstrated that these sequences—which interleave many short intervals with occasionally longer ones—are remarkably effective at minimizing execution times in modern clause-learning SAT solvers. Similarly, Laurent Orseau et al. utilized universal restart sequences in Single-Agent Policy Tree Search With Guarantees to structure stochastic searches and prevent them from becoming trapped in deep, low-reward branches.
Dynamic and Adaptive Restarts
Instead of relying on static mathematical patterns, modern approaches dynamically adjust cutoffs based on the solver's real-time performance or learned models.
In Dynamic Restart Policies, Eric Horvitz et al. pioneered the use of Bayesian models to predict a run's success based on its first few steps. When a trajectory is predicted to be exceptionally long, the system triggers an immediate termination, reallocating computational resources to new random seeds with higher success probabilities.
For scenarios involving multiple problem instances, Matthew J. Streeter et al. developed a greedy optimization framework in Restart Schedules for Ensembles of Problem Instances to select restart thresholds that maximize the expected number of solved instances per unit of time. Taking this a step further, Matteo Gagliolo et al. introduced an adaptive online mechanism called GAMBLER in Learning Restart Strategies, which dynamically updates cutoffs based on online observations without requiring prior knowledge of the problem's difficulty.
Broad Applications Across Automated Reasoning
The strategy of rapid randomized restarts has proven foundational across diverse automated reasoning domains:
- AI Planning and SAT Sampling: Henry A. Kautz et al. integrated frequent restarts into systematic SAT-based planners in Unifying SAT-based and Graph-based Planning, demonstrating that general-purpose reasoning engines could outpace specialized planners. Beyond optimization, Jordan Erenrich et al. showed in Sampling Combinatorial Spaces Using Biased Random Walks that adjusting the search cutoff serves as a vital mechanism for tuning the trade-off between sampling uniformity and search efficiency.
- Multi-Agent Path Finding (MAPF): Solvers in this domain are highly sensitive to initial conditions. In Improved Solvers for Bounded-Suboptimal Multi-Agent Path Finding, Liron Cohen et al. utilized rapid restarts by shuffling agent orderings to bypass stagnant search branches. David Chan et al. formalized this concept as Rapid Randomized Restarts (RRR) in Rapid Randomized Restarts for Multi-Agent Path Finding Solvers, partitioning a fixed computational budget into short, independent attempts to dramatically boost success rates in complex routing environments.
- Games and Deep Learning Search: The principle extends to game-theoretic and neural network-guided searches. In Combining local search techniques and path following for bimatrix games, Nicola Gatti et al. combined random restarts with local search to find Nash Equilibria, bypassing worst-case computational paths. In deep-learning-based planning for complex puzzles like Sokoban, Dieqiao Feng et al. discovered "left heavy tails" in Left Heavy Tails and the Effectiveness of the Policy and Value Networks in DNN-based best-first search for Sokoban Planning, proving that frequent restarts allow neural-guided best-first searches to successfully navigate critical decision nodes that would otherwise cause exponential failures. Even in massive state spaces without explicit heuristics, randomized search frameworks like Nested Monte-Carlo Search (Tristan Cazenave in Nested Monte-Carlo Search) rely on nested random playouts to discover optimal solutions far faster than exhaustive depth-first alternatives.
Key Foundational Work
Heavy-Tailed Distributions in Combinatorial Search (1997) — contributed 2 concept elements to this direction.
Expected Gains from Parallelizing Constraint Solving for Hard Problems (1994) — contributed 1 concept elements to this direction.