Revocable Learned Conditioning for MPE Inference

Finding the single most likely joint assignment in a probabilistic graphical model is called MPE (most probable explanation) inference. A probabilistic graphical model is a large probability distribution written as a product of small local factors. On densely connected models, MPE inference is NP-hard, and exact solvers run out of time. A recent and effective trick is to let a neural network pick a few variables and fix their values before handing the smaller problem to an exact solver. This is called conditioning. It can remove most of the search, but each fixed value is a bet. If the network is wrong, the true optimum is permanently cut out of the search, and the solver gives no warning.

This note proposes to treat every learned conditioning decision as a provisional commitment rather than a permanent one. Each commitment is either certified safe by a cheap optimization bound or revoked when the evidence against it has grown large enough. The rule for when to revoke comes from online algorithms that take advice from a learned predictor. In that setting, abandoning a commitment too early wastes the speedup, and abandoning it too late wastes search on a wrong branch. This is the structure of ski rental, the classic rent-or-buy problem. Learning-augmented primal-dual methods already solve ski rental with a tunable trust in the predictor. The result is a solver that keeps nearly all of the neural speedup when predictions are good. When predictions are bad, it degrades to a bounded multiple of the solver without conditioning, and it always reports a valid gap to the optimum.

Core Claim

Neural conditioning for MPE is high-stakes in a way that can be fixed. Learning to Condition (L2C) trains an attention network that scores variables for how likely their predicted value is to be optimal and how much fixing them shrinks the search. Inside AND/OR branch-and-bound (AOBB), it reports 80–90% fewer explored nodes with near-zero solution gaps on 14 high-treewidth benchmarks from the UAI inference competitions. The same paper notes that fixing a variable to a wrong value permanently excludes the optimal solution. We claim two things can be added at negligible cost. The first is a certificate for each commitment, computed from the dual of the standard linear-programming (LP) relaxation of MAP. The second is a revocation rule with a consistency–robustness guarantee: near-L2C performance under accurate predictions, and bounded loss relative to unconditioned search under arbitrary errors.

The certificate is simple. Let $U(\cdot)$ denote the upper bound on the log-likelihood obtained from a few iterations of dual coordinate descent, of the max-product LP type, on a subproblem. Let $L$ be the log-likelihood of the best assignment found so far. A commitment $c = (x_i = v)$ is certified safe when

$$U(x_i \neq v) \le L,$$

because then no assignment with $x_i \neq v$ can beat the incumbent. Certified commitments become permanent. Commitments that are not yet certified accumulate a "suspicion" cost $s_c$, which grows over solver time. It is measured with the local primal-dual gap of Tighter Relaxations for MAP-MRF Inference. That paper shows the total gap between the current dual bound and the incumbent splits exactly into a sum of local gaps over factors. We add up the share of that sum on factors touching $x_i$:

$$U - L = \sum_{f} g_f, \qquad s_c(t) = \int_0^t \sum_{f \ni x_i} g_f(\tau)\, d\tau .$$

Here $g_f \ge 0$ is the local gap at factor $f$, and $t$ is solver time. Revoking $c$ has a "buy" price: the expected growth of the search space, which L2C's simplification head already predicts. The decision of when $s_c$ justifies paying that price is an online covering problem with a prediction attached, namely the network's optimality score. We resolve it with the primal-dual rule of The Primal-Dual method for Learning Augmented Algorithms. That rule speeds up or slows down the growth of the "buy" variable according to the advice, with a trust parameter $\lambda \in [0,1]$.

How This Differs from Prior Work

Prior work plays three roles here. L2C and BEACON motivate the problem. BEACON trains an attention network to propose local-search flips and reports 50–80% higher log-likelihood improvement than greedy search. Both papers show that learned guidance helps a great deal on high-treewidth models. Neither gives a recourse when predictions are wrong: BEACON's convergence result needs the network to be right more than half the time. We keep their networks and add the certification and revocation layer.

Two papers supply the method. The local-gap decomposition of Tighter Relaxations for MAP-MRF Inference is used offline in that paper, to choose which higher-order clusters to add to the relaxation. We reuse it online, to assign blame to individual commitments. The learning-augmented primal-dual analyses of The Primal-Dual method for Learning Augmented Algorithms and Learning-Augmented Algorithms for Online Linear and Semidefinite Programming give the trust-modulated update rules. Those works only treat abstract covering problems, positive semidefinite programs, and network examples; they never touch graphical models or search heuristics.

One paper constrains the design. Dynamic Inference in Probabilistic Graphical Models updates Gibbs samples incrementally, but only under a weak-interaction (rapid-mixing) condition. Frustrated grids, Promedas, and Pedigree models are exactly where that condition fails. We therefore use no mixing assumption and rely only on LP duality, which holds on any model.

We are deliberately not proposing a competitive ratio for online MAP itself. The offline problem is NP-hard, and the MAP LP is neither a pure covering nor a pure packing program. The online-algorithms machinery is applied only where it fits exactly: the rent-or-revoke decision for each commitment.

Research Program

The first component is the analysis. We will prove two bounds for each commitment, both under the assumption that suspicion is a valid proxy for wasted effort. The first is a consistency bound: when the advice is correct, the solver time lost to revocation overhead is at most a factor depending on $\lambda$ above the time with no revocation. The second is a robustness bound: when the advice is wrong, the time spent before revoking is at most a factor depending on $\lambda$ above what an oracle that knew the commitment was wrong would spend. These bounds inherit their form from the learning-augmented ski-rental analysis in The Primal-Dual method for Learning Augmented Algorithms. The real work is in the proxy assumption. We will state precisely when local gap mass bounds the search wasted on a wrong commitment, and we will measure how often that condition holds empirically. Separately, the final certificate $U_0 - L$ is valid by weak duality whatever the network does, where $U_0$ is the dual bound of the original, unconditioned model.

The second component is the system. We will reimplement L2C-style conditioning on top of AOBB and SCIP, and add incremental dual coordinate descent that is warm-started across commitments. Computing $U(x_i \neq v)$ then costs a handful of message-passing sweeps rather than a fresh solve. The certification and suspicion bookkeeping run as a side process that can revoke commitments and backtrack.

The third component is a streaming extension. Evidence arrives as a sequence of queries on a fixed model. The commitments certified on the previous query serve as advice for the next, mirroring how Learning-Augmented Algorithms for Online Linear and Semidefinite Programming used the previous day's optimum as advice on the Oregon-1 router graph.

Baselines

The naive reference point is AOBB, and separately SCIP, run on the unconditioned model with the same 30-second limit used by L2C. This tells us what conditioning buys at all.

The strongest existing method is L2C with hard conditioning. We will use the published 5% conditioning depth inside AOBB and SCIP, retrain it on the same training split as our method, and give it the same 30 seconds. Its reported result is an 80–90% reduction in explored AOBB nodes with near-zero gaps (Learning to Condition). The file reports no exact percentage-gap value, so "near-zero" is the reference. Beating L2C means two things. On clean advice, we must stay within a small factor of its node reduction and match its gap. On corrupted advice, we must have strictly lower gap and no instances where the optimum is lost.

A third baseline is L2C used only as a branching order. The solver explores the network's suggested values first but never prunes the alternatives. This is exact, and it isolates whether committing buys anything over ordering.

For anytime quality without certificates, we include BEACON and GLS+, given the same step budget. GLS+ is guided local search that adds penalties to escape local optima. BEACON's reported advantage is 50–80% higher log-likelihood improvement over greedy search (BEACON).

Two ablations isolate the key ingredients. The first keeps revocation but uses a fixed threshold, ignoring the network's confidence. This is the oblivious online rule, and it tests whether trust modulation matters. The second revokes on a timer without the local-gap signal, which tests whether dual blame matters. All methods share the same model files, hardware, time limit, and hyperparameter tuning budget on a held-out split.

Why not just…?

Why not just use L2C as a branching order, which is already exact? Ordering never excludes the optimum, but it also gives up much of the search-space reduction. Commitments let the solver discard whole subtrees immediately, and that is where the 80–90% node savings come from. The branching-order baseline measures this directly. If it matches our method on both clean and corrupted advice, the commitment idea is unnecessary, and we will report that.

Why not just run the conditioned and unconditioned solvers side by side and keep the better answer? This is a real threat. Time-sharing the two runs, or splitting the 30 seconds between them, is automatically within a factor of two of the better one, with no theory at all. Our argument is granularity. A single wrong commitment out of fifty kills the whole conditioned run in the portfolio, whereas our method revokes only that one commitment. The decisive comparison is at intermediate corruption rates, roughly 10–30% of commitments wrong. If the portfolio is not clearly beaten there, the proposal reduces to the portfolio and should be reframed.

Why not just use local search (GLS+ or BEACON) and skip LP bounds entirely? These methods scale well and BEACON is strong early in the search. However, they return no bound on how far they are from the optimum, and GLS+ rediscovers the same traps on every query. We report both log-likelihood at fixed budgets and certified gap. Local search can win on the first metric but cannot produce the second.

Why not just recompute from scratch for each streaming query? On these benchmarks, uncontrolled solving within 30 seconds already struggles. The streaming experiment compares warm-started certified commitments against cold restarts, using time-to-target-gap as the measure.

Proposed Experiments

We use the high-treewidth binary UAI competition models used by L2C and BEACON: Grids, Promedas, Pedigree, Bayesian networks, and the weighted constraint satisfaction (WCSP) and RUS models. Best-known optima come from long offline runs. Metrics are the percentage gap to the best-known optimum, the certified gap $(U_0 - L)/|L|$, explored nodes, time to reach a target gap, and the fraction of instances on which the optimum was excluded.

The key experiment injects controlled corruption into the network's predictions, flipping 0%, 10%, 30%, 50%, and 80% of proposed values. This follows the noise protocol of The Primal-Dual method for Learning Augmented Algorithms. We sweep $\lambda$ at each corruption level.

The method succeeds on three conditions. At 0% corruption, it must track hard L2C. At 50% or more, it must stay within a bounded factor of unconditioned AOBB while hard L2C collapses. In between, it must beat the side-by-side portfolio. We will also report how often commitments are certified early, since that determines whether the overhead of computing the bounds pays off. If certification almost never fires on Promedas or Pedigree, the LP relaxation is too loose for this approach on those families. That limitation can be tested by adding clusters to tighten the relaxation, using the same local-gap scoring.