When several threads of an exact solver search one optimization problem at once, they can post the best solution value found so far to a shared table, so every thread can abandon branches that cannot beat it. This is cooperative bound communication, and it produces some of the most striking results in parallel search: speedups greater than the number of cores, and portfolios that beat the best single solver chosen with hindsight. A separate literature shows that the running time of combinatorial search is wildly unpredictable. The same instance can take seconds or days depending on early branching choices, and the fix is to randomize choices such as tie-breaking and restart often. These two ideas have never been analyzed together. Parallel cooperative solvers are evaluated by average speedup, and nobody has asked how shared bounds change the shape of the runtime distribution. Nobody has asked where in a parallel solver randomness actually pays.
The proposal starts from one observation. An exact optimization run has two phases. The first is finding: reaching the optimal solution, which is a lucky-path search of the kind that shows heavy-tailed runtimes. The second is proving: exhaustively ruling out everything better, which behaves like proving a satisfiability instance has no solution, where runtimes are thin-tailed and randomization does not help. A shared incumbent value turns the finding time of the whole team into the minimum over its randomized members. A shared cache of solved subproblems splits up the proving work. So randomness should go to a small number of "finder" threads, and the rest should be deterministic, cache-sharing "provers". The number of finders should follow from how heavy the tail is, and that can be estimated.
Core Claim
Suppose a single randomized thread's time to reach the optimal incumbent has a power-law survival function $P[T > t] \sim C t^{-\alpha}$, where $\alpha$ is the tail index: smaller $\alpha$ means more extreme luck-dependence, with infinite variance for $\alpha<2$ and infinite mean for $\alpha<1$. If $N_f$ finder threads run roughly independently and share their incumbents, the team's finding time is the minimum of their times. Multiplying independent survival functions gives
$$P\left[\min_{i \le N_f} T_i > t\right] \sim C^{N_f}\, t^{-N_f \alpha}.$$
The team's tail index is therefore $N_f\alpha$. It needs only about $N_f^* = \lceil 2/\alpha \rceil$ finders for finite variance of the finding time. Every extra core is better spent on deterministic proving, which benefits from heuristic ordering and cache reuse but not from randomness.
The claim has three parts, and each can fail on its own. The first is empirical: shared-bound parallel solvers on standard benchmarks show a heavy-tailed finding phase and a thin-tailed proving phase. The second is mechanistic: the team tail index grows roughly linearly in $N_f$ despite the correlation that incumbent sharing introduces between finders. The third is practical: an online controller that estimates $\alpha$ from finder improvement times and sets the finder/prover split beats both all-randomized and all-deterministic cooperative search in upper runtime quantiles at equal core count.
This differs from the closest work in a specific way. Parallel AND/OR Search for Marginal MAP spreads threads apart with a deterministic penalty on crowded nodes ("virtual q-values"). It reports speedups, not runtime distributions, and it treats all threads alike. Fixed-rate random exploration, the method of A Comparison of Knowledge-Based GBFS Enhancements and Knowledge-Free Exploration and Stochastic Anytime Search for Bounding Marginal MAP, applies randomness uniformly within one sequential search. We instead place randomness by search phase and size it from a measured tail.
Research Program
Role of prior work. The motivating evidence comes from two places. Heavy-Tailed Distributions in Combinatorial Search shows power-law runtimes with $\alpha<1$ on solvable instances and near-normal runtimes on unsolvable ones. The shift between those two regimes is exactly our find/prove split. Rapid Randomized Restarts for Multi-Agent Path Finding Solvers shows that many short randomized runs beat one long run, but its runs never communicate.
The method comes from two sources. Parallel AND/OR Search for Marginal MAP supplies the shared-memory search engines and the shared cache table; we reuse its branch-and-bound variant. Boosting Combinatorial Search Through Randomization supplies randomized tie-breaking with restarts, which is how finders randomize.
The constraints come from two results. Bias in Algorithm Portfolio Performance Evaluation warns that single-seed comparisons are optimistically biased, so every configuration is run with many seeds. The GBFS comparison paper shows that real heuristic guidance beats randomness where guidance is informative, which argues against randomizing provers.
Build. We implement a shared-memory AND/OR depth-first branch-and-bound solver for Marginal MAP, following Parallel AND/OR Search for Marginal MAP. Its threads are of two types.
Finders run short randomized dives. They use random tie-breaking among near-equal heuristic values, plus a small chance of expanding a non-best child in the style of Stochastic Anytime Search for Bounding Marginal MAP, and they restart on a cutoff. They post every improved incumbent to a shared slot. Finders are restricted to exact evaluation, so every posted bound is valid; probabilistic bounds are deliberately out of scope.
Provers run deterministic best-first/depth-first proof with the shared cache and the virtual-q-value spreading. They prune against the shared incumbent.
A controller logs the times at which finders improve the incumbent across restarts. It estimates $\alpha$ online with a Hill-type estimator on restart-to-improvement times and reassigns threads between roles at restart boundaries. To test generality beyond graphical models, we build a second instantiation on MiniZinc optimization problems. There, finders are randomized-search runs of one open CP solver of the kind used in A Multicore Tool for Constraint Solving, and provers are its deterministic default search with the incumbent broadcast as a constraint.
Analyze. For each instance we run 100 or more seeds per configuration and record three things: time to the optimal incumbent, time from that point to completed proof, and total time. We fit tail indices separately for each phase using log-log survival plots and the Hill estimator. Then we measure how the team tail index grows with $N_f$ and compare it with the $N_f\alpha$ prediction.
Baselines
The naive reference point is a single deterministic thread, which anchors the speedup accounting.
The strongest existing method is deterministic cooperative search with a shared cache and virtual q-values, with all threads deterministic, as in Parallel AND/OR Search for Marginal MAP. It is the best shared-memory exact MMAP solver in the file and reports speedups of up to 8-fold on 12 cores, including superlinear cases, on 930 pedigree, pdb and planning instances. We rerun it on our hardware at 4, 8, 12 and 16 threads with the same instances and time limit, so that it and our method share every engineering choice except role allocation.
The second strong baseline is independent randomized restarts across all cores, as in Rapid Randomized Restarts for Multi-Agent Path Finding Solvers but with a shared incumbent added. This is the "all finders, no cache" configuration.
On MiniZinc we include incumbent broadcast among deterministic solvers, the mechanism of A Multicore Tool for Constraint Solving. That paper reports RCPSP instances solved in 10.56 seconds with shared bounds where isolated solvers hit the 1,800-second timeout, and 99.35% of CSP instances solved on 8 cores. Our version holds the solver fixed so that portfolio diversity is not confounded with randomness.
Three ablations isolate the key ingredient. The first is every thread randomized at a fixed exploration rate, with rates tuned over the same grid as ours; this is the direct parallel transplant of the GBFS comparison paper's 528 to 585.1 coverage gain on IPC. The second is the best fixed finder/prover split found by oracle grid search per benchmark family, which tests whether the online $\alpha$ rule recovers it. The third is our split with the shared cache disabled for provers.
All methods get the same tuning budget in seed-runs. The tail comparison target is new: no reported result found on Lacuna for runtime tail indices of any parallel cooperative solver. Beating the strongest baseline therefore means two things: a statistically significant reduction in the 90th and 99th percentile of total time across seeds at equal cores, and no loss of median time greater than 10%.
Why not just…?
Why not just randomize every thread at a fixed rate? This is the most obvious combination of the directions, and it could work well at low core counts. The phase argument predicts that it wastes proving effort. Exhaustive proof gains nothing from luck, per Heavy-Tailed Distributions in Combinatorial Search. Random expansion also scatters threads away from cached subproblems and informative ordering, which the GBFS comparison shows matters where guidance is good. The first ablation settles this. If uniform randomization matches our split in the 99th percentile at 12 to 16 cores, the role distinction is unnecessary and we will report that.
Why not just run independent randomized restarts and share only the incumbent? This is the real threat. It keeps finding luck and needs almost no synchronization. What it lacks is the shared cache that divides proving work, and it is the cache that produces the superlinear speedups in Parallel AND/OR Search for Marginal MAP. If proving dominates total time on hard instances, as the thin-tailed but long proof phase suggests, this alternative should lose on instances with large proof trees and win on instances that are almost all finding. We will report results split by each instance's measured proof fraction rather than pooled.
Why not just add random tie-breaking to virtual q-values and stop there? That is one parameter setting: all provers, each with a pinch of randomness. It is included in our split grid. Our claim is that the benefit is concentrated in a few threads and saturates once $N_f\alpha$ exceeds about 2. If adding randomness to all threads keeps helping past $N_f^*$, the saturation prediction is wrong.
Proposed Experiments
Primary benchmarks are the Marginal MAP families pedigree, pdb, planning, grid and promedas used by Parallel AND/OR Search for Marginal MAP and Stochastic Anytime Search for Bounding Marginal MAP. We restrict to instances where exact summation is feasible, so all bounds are exact. The secondary benchmark is a stratified subset of MiniZinc challenge optimization problems, including RCPSP, following Sequential Time Splitting and Bounds Communication for a Portfolio of Optimization Solvers. Metrics are solve rate within budget, median and 90th and 99th percentile total time over seeds, the fitted tail index of each phase, and, for MiniZinc, the anytime bound area.
The first decisive check tests the phase hypothesis. Single-thread randomized runs must show a finding-time tail index below 2 and a proving-time distribution without a power-law tail on a majority of hard instances. If the proving phase is itself heavy-tailed, the premise fails and the proposal becomes a pure characterization study.
The second check tests the scaling law. The measured team tail index should rise roughly as $N_f\alpha$. We report the ratio of measured to predicted index as a function of $N_f$; ratios well below one mean that incumbent sharing correlates finders and weakens the argument.
The third check tests the allocation rule. The finder count chosen online should land within one thread of the oracle-best fixed split on at least three of five benchmark families. It should also beat the all-deterministic cooperative baseline and the independent-restart baseline in the 99th percentile at 12 and 16 cores.
Together these determine whether shared bounds make parallel search more predictable, not just faster on average, and whether the right amount of randomness is a measured quantity rather than a hand-tuned rate.
References
- Parallel AND/OR Search for Marginal MAP
- A Comparison of Knowledge-Based GBFS Enhancements and Knowledge-Free Exploration
- Stochastic Anytime Search for Bounding Marginal MAP
- Heavy-Tailed Distributions in Combinatorial Search
- Rapid Randomized Restarts for Multi-Agent Path Finding Solvers
- Boosting Combinatorial Search Through Randomization
- Bias in Algorithm Portfolio Performance Evaluation
- A Multicore Tool for Constraint Solving
- Sequential Time Splitting and Bounds Communication for a Portfolio of Optimization Solvers