Exact combinatorial search keeps a table of already-solved subproblems so it does not solve them twice. When memory runs out, the solver must throw entries away and later recompute them, and this recomputation can dominate runtime. Parallel solvers also share the best solution found so far (the "incumbent") so every thread can skip branches that cannot beat it. We argue that these two facts interact in a way no one has measured. A shared incumbent does more than prune the search. It also tells every thread which cached entries are almost certainly useless, so memory can be reclaimed before anything valuable is evicted.
Our claim is that when RAM is tight, this second effect compounds. More threads find good incumbents sooner. That frees memory sooner, which means fewer useful entries are evicted and fewer subproblems are recomputed. The parallel speedup over a sequential solver given the same memory should therefore grow as the memory budget shrinks, and it should exceed the thread count in the tight regime. If this is right, a paging-free, memory-capped parallel solver can solve instances that sequential search cannot finish within the same RAM. We would build that solver, measure speedup as a function of the memory cap, and use ablations to separate this effect from ordinary "exploration luck."
Where This Sits
Three lines of prior work motivate the idea, and none of them looks at it directly. The first shows that cooperative bounds produce super-linear speedups in memory. Parallel Recursive Best-First AND/OR Search for Exact MAP Inference in Graphical Models (SPRBFAOO) shares a cache of subproblem bounds across threads and reports up to a 7-fold speedup on 12 cores for exact MAP inference. MAP inference means finding the single most likely assignment of all variables in a graphical model. Parallel AND/OR Search for Marginal MAP extends this to marginal MAP, with a best-first solver and a depth-first branch-and-bound solver (SPAOBB-MMAP). It reports up to 8-fold speedups on 12 cores and occasional super-linear speedups "as a strong bound found by one thread could immediately prune massive subtrees for all others." Parallel Beam Search Algorithms for Domain-Independent Dynamic Programming sees the same effect in Bin Packing (36x on 32 threads). All three assume the shared table fits in RAM. None asks what bound sharing does once it does not.
The second line treats memory as the bottleneck but without cooperative bounds. External Memory Best-First Search for Multiple Sequence Alignment (PE2A*) spills the frontier to disk in hashed buckets. It is the first method to solve all of BAliBASE Reference Set 1 with affine gap costs. However, it does not propagate incumbent bounds to suppress writes, and it fails if a single bucket exceeds RAM. Stochastic Node Caching for Memory-Bounded Search shows that which nodes a bounded cache keeps matters a great deal. Caching expanded nodes at random with a fixed probability cuts node visits by 63% relative to greedy caching, and its advantage grows as the cache shrinks. That result supplies our evaluation lens: the admission and eviction policy is a first-class design variable. SNC is sequential, though, and its policy ignores bounds.
The third line supplies the load-balancing mechanism we reuse. In the SPRBFAOO papers, threads temporarily inflate the cost estimate of a node they are working in, called its virtual q-value. Peers are then nudged elsewhere, and threads spread across the tree without a central queue. We keep this mechanism unchanged. What matters for our claim is that it makes threads explore different regions, which is exactly what produces early, diverse incumbents. The same papers constrain the design. Lock contention on the shared cache is expected to hurt beyond roughly 12–16 cores, and a centralized master-slave variant (SPRBFAOO2-MMAP) performed much worse than the decentralized scheme. We therefore use a lock-sharded table and no central coordinator.
Core Claim
Take minimization, which covers MAP inference in negative-log form. Let $U$ be the shared incumbent cost. For a cached subproblem $n$, let $\mathrm{lb}(n)$ be its cached lower bound and $g_{\min}(n)$ the smallest path cost seen so far on any path reaching it. Let $c(n)$ be a recorded estimate of the nodes needed to re-derive $n$, which is its subtree size when it was solved. We propose that each cache shard evicts the entry with the lowest retention score:
$$ r(n) = \frac{c(n)}{\max\big(\epsilon,\; U - g_{\min}(n) - \mathrm{lb}(n)\big)} $$
Here $\epsilon$ is a small positive constant. Entries whose optimistic total already reaches the incumbent get a near-zero denominator, so they score as nearly worthless unless they are very expensive to recompute. Every time a thread improves $U$, the scores of many entries in every shard drop at once.
Two properties matter. First, correctness never depends on the score. Because cached values in a context-minimal AND/OR graph are shared across paths, a later path might arrive with a smaller $g$. Eviction only costs recomputation; it never produces a wrong answer. Second, the policy uses information that only exists because of cooperation. A sequential solver computes the same score but with its own, later-arriving incumbent.
The quantity we study is the same-memory speedup
$$ S(P, M) = \frac{T_{1}(M)}{T_{P}(M)}. $$
Here $T_P(M)$ is the wall-clock time of a $P$-thread solver whose shared cache is hard-capped at $M$ bytes, and $T_1(M)$ is the same solver run with one thread at the same cap. The prediction is that for fixed $P$, $S$ rises as $M$ falls. The reasoning is that sequential recomputation cost grows as memory shrinks, and the parallel solver cuts that cost in two ways: incumbents arrive earlier in wall-clock time, and the resulting evictions then target dead entries rather than live ones. For the strongest competitor, the file gives "up to 7-fold on 12 cores" for SPRBFAOO on MAP and "up to 8-fold on 12 cores" for the marginal MAP solvers, both measured with memory unconstrained. There is no reported result on Lacuna for either solver's speedup as a function of a hard memory cap. Establishing that curve is part of the contribution.
Research Program
We would modify SPAOBB-MMAP and SPRBFAOO, the branch-and-bound and best-first shared-cache solvers from the marginal MAP and MAP papers, in four ways. We would impose a hard byte cap on the shared cache, sharded with per-shard locks. We would add $g_{\min}$ and $c(n)$ fields to each entry. We would broadcast $U$ through a single atomic word that threads read before every eviction decision. And we would replace the existing replacement rule with the score above. Virtual q-value coordination stays as published.
The depth-first branch-and-bound solver is the primary target because an incumbent is native to it. For the best-first solver, which uses thresholds rather than an incumbent, we would use the best solution found by the anytime path. We would also report where the score is less informative there.
The analysis has three parts. The first is instrumentation that logs, over time, the fraction of evictions hitting entries later re-requested. This "regret rate" is the direct mechanism signal. The second is separating the node-count ratio from the wall-clock ratio, so that super-linearity from fewer recomputations can be told apart from super-linearity from pruning. The third is a sweep over incumbent-broadcast delay. Artificially delaying $U$ propagation by $k$ node expansions tests whether gains disappear as sharing becomes stale, which would tie the effect causally to cooperation.
Baselines
The naive reference is the same solver run with one thread at the same cap $M$. This is $T_1(M)$, the denominator of $S$. It uses the same bound-aware score, so any super-linearity cannot come from the policy alone. It is also run with its native replacement policy, to show the absolute benefit of the policy for sequential users.
The strongest existing method is published SPAOBB-MMAP and SPRBFAOO with their original cache handling, simply capped at $M$. This is the competitor because it already has shared bounds, virtual q-value balancing, and reported super-linear cases. We run it on the same instances, the same 12-core machine, the same cap, and the same time limits as the source papers (one hour for marginal MAP, two hours for MAP), with identical mini-bucket heuristics. Beating it means a statistically significant gain in solved-instance count or median $T_P(M)$ at caps of 50% or less of the uncapped peak footprint, with no loss above that. Matching its reported up-to-7x and up-to-8x behavior when uncapped is a sanity check on our reimplementation.
A second baseline is least-recently-used eviction in the shared cache. This is the default a systems reviewer would reach for, and the Littman-style bounded caching noted in the memory-bounded search literature. A third is SNC-style probabilistic admission ported to the shared table, with the admission probability tuned per domain on a held-out instance split. That tuning budget is matched by tuning our $\epsilon$ on the same split.
The key ablations isolate cooperation. In the private-cache split, each of $P$ threads gets $M/P$ and its own incumbent, which removes sharing but keeps parallelism. The broadcast-delay sweep degrades sharing gradually. Disabling virtual q-values makes threads crowd together, which tests whether exploration diversity is what yields early incumbents.
Why not just…?
Why not just give the machine more RAM or let the OS swap? More RAM moves the cliff rather than removing it. The marginal MAP paper already reports instances that time out sequentially, and PE2A* was needed precisely because lattice problems outgrow memory. OS swapping turns cache hits into random disk reads. The file's evidence on main-memory managers and on delayed duplicate detection both point to uncoordinated paging as the failure mode. We include a swap-enabled run at a cap below peak footprint to show the cliff directly.
Why not just run independent randomized restarts, which already give super-linear speedups? Parallel Restarted Search gets 35.7x on 32 cores for MiniZinc satisfaction-style instances, but its restarts share nothing and discard state. They cannot prove optimality on MAP or marginal MAP, which is the task here. Solving to proven optimality is our success criterion, so restarts are not a competitor on it. We do include a $P$-seed portfolio of sequential solvers at $M/P$ each as a reference.
Why not just use least-recently-used eviction? This is a real threat. If recency happens to correlate with deadness in these search graphs, LRU could match our score. The regret-rate log settles it: if LRU and the bound-aware score produce similar regret, we will report that the effect comes from sharing incumbents, not from the policy. The private-cache and broadcast-delay ablations still test the main claim either way.
Why not just attribute super-linear speedups to seed luck? Heavy-tailed runtimes can make any parallel solver look super-linear on a few instances, as Seven Challenges in Parallel SAT Solving notes. We address this in three ways. We report $S(P,M)$ as distributions over at least ten seeds per instance. We compare against the minimum over $P$ independent sequential seeds, which is exactly what luck alone would deliver. And we require that the trend in $M$, not individual outliers, carries the claim. Luck does not predict that speedup grows as memory shrinks.
Proposed Experiments
The main benchmarks are the MAP suites from the SPRBFAOO paper (pedigree, protein/pdb, and grid networks) and the 930-instance marginal MAP suite (pedigree, pdb, planning). We first run each instance uncapped to record peak cache footprint $F$. We then sweep caps $M \in \{F, F/2, F/4, F/8, F/16\}$ at $P \in \{1, 4, 12\}$, with a contention probe at 32 threads. The contention probe tells us whether the ceiling reported in the SPRBFAOO paper limits the effect.
The reported metrics are $S(P,M)$, node-count ratios, solved-instance counts at the source papers' time limits, the regret rate, and the count of instances solved in parallel but not sequentially at the same cap. As a check that the mechanism is not specific to graphical models, we run a secondary experiment on the lattice-structured seven-sequence alignment benchmark used by SNC. The goal there is to see whether the bound-aware score helps where SNC's random admission already reduced visits by 63%.
The decisive check is a two-way comparison. The claim holds if $S(12, M)$ rises monotonically as $M$ shrinks, exceeds 12 in the median at the tightest caps where the sequential solver still finishes, and collapses toward the private-cache split's value when incumbent broadcast is delayed. If $S$ is flat in $M$, or if the private-cache split matches the shared version, then shared incumbents do not reclaim memory in a way that matters, and the proposal is refuted.
References
- Parallel Recursive Best-First AND/OR Search for Exact MAP Inference in Graphical Models
- Parallel AND/OR Search for Marginal MAP
- Parallel Beam Search Algorithms for Domain-Independent Dynamic Programming
- External Memory Best-First Search for Multiple Sequence Alignment
- Stochastic Node Caching for Memory-Bounded Search
- Parallel Restarted Search
- Seven Challenges in Parallel SAT Solving