Finding the single most likely explanation of observed evidence in a Bayesian network, known as MAP inference, is NP-hard. It is still a workhorse task in diagnosis, protein design and vision. In 1990, Shimony and Charniak showed that any belief network can be rewritten, in linear size for bounded in-degree, as a weighted Boolean-function DAG (WBFDAG). This is a circuit of AND/OR/XOR-style gates whose cheapest satisfying assignment is exactly the MAP assignment. Best-first search over this circuit also enumerates the second-best, third-best and later explanations for free (A new algorithm for finding MAP assignments to belief networks). The idea was never tested. The authors used what they called a "trivial" admissible heuristic, reported no benchmarks, and explicitly called for timing studies that never came.
This note proposes to give that search a strong heuristic. At every search state, the heuristic is a lower bound computed from a linear-programming (LP) relaxation of the remaining circuit. That relaxation is tightened by an approximate separation oracle, meaning a cheap procedure that finds constraints the current relaxed solution violates and adds them on the fly. The central observation is that approximate separation behaves differently inside search than inside the ellipsoid method. There, missing a violated constraint can stop the optimizer at an uncertified, pseudo-feasible point. Inside best-first search, a missed cut only makes the lower bound looser. The heuristic stays admissible, so the search still returns a certified optimum, and oracle quality affects only speed. The empirical question is then how much bound quality is worth buying per search node. We answer it on standard protein, stereo and Bayesian-network-repository benchmarks, with the wall-clock and memory reporting that theory-only work in this area has omitted.
Core Claim
A search state $s$ in the WBFDAG fixes a subset of gate values. Let $\lambda$ denote the dual variables of the relaxed circuit restricted to the unfixed part, and $\mathcal{C}_t$ the set of cuts generated so far. The heuristic is
$$h(s) \;=\; D(\lambda; s, \mathcal{C}_t) \;\le\; \min_{x \text{ consistent with } s} \mathrm{cost}(x),$$
where $D$ is the dual objective of the relaxation. The inequality holds for any dual-feasible $\lambda$, however few iterations were run and however many violated cuts the oracle failed to find. Weak duality gives this for free. It is the property that lets an approximate oracle plug into an exact search without adding error.
The claim is concrete. Relaxation-guided best-first search on WBFDAGs, with a cheap randomized oracle for cluster-consistency cuts, should do three things. It should expand orders of magnitude fewer nodes than the trivial heuristic. It should certify optimality on instances where LP tightening alone stalls. And it should enumerate the $k$ best explanations at a marginal cost that grows slowly in $k$, which neither LP tightening nor MAX-SAT local search provides.
The two ingredients play different roles. The WBFDAG supplies the search space and the next-best enumeration. The separation oracle supplies the heuristic. The empirical-validation gap supplies the evaluation discipline: every claim is reported in nodes, oracle calls, wall-clock time and peak memory.
Relation to Prior Work
The closest work is Tightening LP Relaxations for MAP using Message Passing. Sontag et al. tighten the local LP relaxation by greedily adding triplet clusters in the dual, with warm-started message passing. They solve all 30 hard side-chain models and 96 of 97 protein design problems, but some runs take up to 11 days and one instance stays unsolved. Their method is a pure relaxation. When the bound does not close the integrality gap, nothing branches, and it never produces a second-best solution. We reuse their dual machinery as the inner bound. We wrap it in search, and we replace greedy triplet pursuit with an explicit oracle whose violation threshold is a controlled knob.
The oracle design borrows from Approximating a RUM from Distributions on k-Slates. That paper pairs a theoretically polynomial separation oracle with a practical randomized local-search oracle over an exponential constraint family. It shows that the heuristic oracle is what makes the method run on real data. Their setting is choice models over permutations, not graphical models. We transfer only the design pattern: an exact reference oracle for small cluster size, plus a local-search oracle for deployment.
MPLP++: Fast, Parallel Dual Block-Coordinate Ascent for Dense Graphical Models supplies a fast dual solver for the pairwise part. It also supplies a constraint we must respect: dual coordinate ascent wins only above roughly 10% graph density, and TRW-S wins on very sparse grids. The heuristic's per-node cost will therefore depend on density, and we measure that dependence rather than assume it away.
Two exact-search and encoding lines constrain the design. Computational Protein Design Using AND/OR Branch-and-Bound Search shows that mini-bucket heuristics inside AND/OR branch-and-bound already beat A* by large margins, so a new heuristic must beat mini-buckets, not just the trivial one. Using Weighted MAX-SAT Engines to Solve MPE shows that generic weighted MAX-SAT local search beats specialized MPE local search. Those engines give no certificate, which is the gap we target.
The MWIS and perfect-graph reductions play a supporting role. Message Passing for Max-weight Independent Set suffers the same auxiliary-graph blowup as the WBFDAG. On MAP Inference by MWSS on Perfect Graphs and Revisiting the Limits of MAP Inference by MWSS on Perfect Graphs. identify model classes where the relaxation is provably tight but the ellipsoid-based solver is slow in practice. We use those classes as a sanity control. On almost-balanced binary models our heuristic should prune to near-zero branching.
Research Program
The first component is a lazy WBFDAG. Shimony and Charniak's construction is exponential in parent count, because each parent configuration gets a cost node. We never materialize these nodes. A cost node is created only when the search or the pricing step needs it. Pricing means the LP's reduced-cost check, which scans the CPT under current dual prices for the most negative-cost parent configuration. For compact CPTs such as noisy-OR or context-specific tables, that scan is sublinear in the table size.
The benchmark MRFs are not directed. We convert each potential into an observed binary child with a proportional CPT. This standard construction preserves the MAP assignment, and it puts protein and stereo instances inside the WBFDAG formalism.
The second component is the relaxed circuit. Each gate is replaced by its linear hull over $[0,1]$ values. Consistency cuts come from clusters of $c$ original variables that share ancestors in the moralized network. We build two oracles. The exact oracle enumerates all clusters up to size $c = 3$ in $n^{O(c)}$ time and serves as a reference. The approximate oracle runs randomized local search, seeded at the most frustrated edges of the current dual. It returns any cluster whose bound gain exceeds a threshold $\alpha$.
The heuristic at a node is the dual value after a fixed budget of message-passing sweeps, warm-started from the parent node's duals. The warm start is what makes per-node bounding affordable.
The third component is best-first search with next-best continuation. It produces the MAP assignment, then the second-best and later explanations, as in the original paper. It also keeps the global lower bound, so an anytime gap is always available. Everything ships as one open-source harness that logs nodes, oracle calls, cuts, wall-clock time, peak memory and gap. This directly answers the missing-metrics complaint in the validation-gap literature.
Baselines
The naive reference point is Shimony and Charniak's best-first search on the same lazy WBFDAG with their trivial admissible heuristic. It is run on identical hardware under an 8-hour, 4 GB-per-instance budget. This baseline shows how much of any gain comes from the heuristic itself. No timing numbers were ever reported for it, so no reported result exists on Lacuna for WBFDAG search on any benchmark. Our own run of this baseline will be the first. Beating it means solving strictly more instances within budget and expanding at least an order of magnitude fewer nodes on the instances both solve.
The strongest relaxation baseline is Sontag et al.'s cluster-pursuit message passing. It gets the same time budget and uses the authors' triplet-selection rule. On protein design, the reported figure is exact MAP for 96 of 97 problems within a $10^{-4}$ integrality gap, with runtimes from minutes to 11 days. On side-chain placement it solved all 30 models, over half in under 9 minutes, adding about 7 triplets per model. Beating it means solving the remaining unsolved design instance or matching 96/97 at lower median wall-clock time. On side-chain placement, beating it means lower time-to-certificate. For $k$-best enumeration, cluster pursuit has no native procedure. We give it the fairest workaround: re-solving with the previous optimum excluded by a no-good cut.
The strongest exact-search baseline is AND/OR branch-and-bound with mini-bucket heuristics. It runs with the same i-bound tuning budget we give our cluster size. Zhou et al. report exact solutions for 21 of 23 hard core-redesign instances within 8 hours under a 4 GB limit, a case where A* took about 30 minutes and AOBB took 117 ms, and all six full-design cases solved in under 18 seconds. Beating it on core redesign requires solving at least one of the two instances it misses, or cutting median time at equal solve rate.
For the Bayesian network repository and the Darwiche-generator networks, the reference is weighted MAX-SAT with Guided Local Search, following Park and Darwiche. It runs on the same 10 networks, 20 cases each with 10 evidence variables, under equal time. Park and Darwiche report that it outperforms SLS and DLM but give no exact percentages, so no reported numeric result was found on Lacuna. We re-run it ourselves. Beating it means matching its solution probability while also returning a certificate.
Two ablations isolate the key ingredients. The first swaps the approximate oracle for the exact $c=3$ enumerator and for "add all triplets", with everything else fixed. This measures what oracle speed buys against oracle completeness. The second runs the same relaxation heuristic inside a plain variable-ordering branch-and-bound over the original network rather than the WBFDAG. This tells us whether the Boolean-circuit representation contributes anything beyond hosting the $k$-best enumeration.
Why not just…?
Why not just run Sontag et al.'s cluster pursuit longer? On most instances it already closes the gap, and there it is hard to beat. We expect to lose some wall-clock comparisons on easy side-chain models, where search adds overhead. The case for our method rests on three things. The first is the instances where the tightened LP remains fractional; the one unsolved design problem and the multi-day runs show these exist. The second is anytime certified gaps when the relaxation does not close. The third is $k$-best enumeration. If per-instance results show that search never beats cluster pursuit, even on its slowest decile, we will report that the relaxation alone suffices.
Why not just use AND/OR branch-and-bound with mini-buckets? This is the most serious threat. It is exact, memory-aware and very fast on protein design. The question is whether an LP bound with cuts is tighter per unit of compute than a mini-bucket bound. Our second ablation answers this directly, because it puts our bound into a plain branch-and-bound, and a head-to-head at matched i-bound and cluster size answers the rest. If mini-buckets win uniformly, the proposal narrows to a hybrid heuristic taking the maximum of both bounds, which remains admissible.
Why not just hand the problem to a weighted MAX-SAT engine? Park and Darwiche show that local-search MAX-SAT finds very probable assignments. It never proves optimality or bounds the gap, and it does not enumerate ranked explanations with guarantees. We compare solution quality at equal time and additionally report certified gaps. If GLS finds the optimum first in most cases, that is useful to know, and our method's role becomes certifying and ranking its answers.
Proposed Experiments
The benchmark suite has four parts. The first is the 30 side-chain and 97 protein-design instances used by Sontag et al. The second is the 23 hard core-redesign and six full-design cases from Zhou et al. The third is the Tsukuba stereo model. The fourth is the 10 repository networks and the three Darwiche-generator datasets from Park and Darwiche. The generator datasets contain 100-variable networks of width about 16, with and without deterministic CPTs, and 500-variable dense networks.
Four checks decide the proposal.
The first check tests whether the heuristic is informative. We plot nodes expanded against instance difficulty for the trivial heuristic, our approximate-oracle heuristic, and the exact-oracle heuristic. The prediction is at least a tenfold reduction from trivial to approximate, with the approximate oracle recovering most of the exact oracle's pruning at a fraction of its cost.
The second check tests the admissibility argument. We sweep the oracle threshold $\alpha$ and confirm that every run returns the same certified optimum. The only thing that should change is time, and we expect a U-shaped curve with an interior optimal $\alpha$.
The third check tests enumeration. We measure the time to produce the top 10 explanations against the no-good re-solve workaround. Search should grow sublinearly in the number of explanations, while re-solving should grow roughly linearly.
The fourth check tests density dependence. We bin instances by graph density at the roughly 10% threshold reported for MPLP++. We test whether the per-node bound cost makes our method lose on very sparse grids like Tsukuba and win on dense protein models. As a control, we also run almost-balanced binary models from Weller's tractable classes, where the relaxation should be tight and the search should barely branch.
All results are released with per-instance logs, so the practical boundary of the method is visible rather than asserted.
References
- A new algorithm for finding MAP assignments to belief networks
- Tightening LP Relaxations for MAP using Message Passing
- Approximating a RUM from Distributions on k-Slates
- MPLP++: Fast, Parallel Dual Block-Coordinate Ascent for Dense Graphical Models
- Computational Protein Design Using AND/OR Branch-and-Bound Search
- Using Weighted MAX-SAT Engines to Solve MPE
- Message Passing for Max-weight Independent Set
- On MAP Inference by MWSS on Perfect Graphs.
- Revisiting the Limits of MAP Inference by MWSS on Perfect Graphs.