PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning to Bound: Monotonic, Calibrated Neural Upper Bounds for MPE Inference

Akshay Vyas, Hailiang Dong, Shivvrat Arya, Brij Malhotra, Tahrima Rahman, Vibhav Gogate, Nicholas Ruozzi

arXiv:2610.39305v1cs.LGcs.AI

TL;DR

MPE inference in PGMs becomes difficult as model size and treewidth grow, and tight classical bounds can be prohibitively expensive within branch-and-bound. L2B learns calibrated neural upper bounds and enforces monotonicity by construction. Across PGM families, it reports bounds 5–10× tighter than MBE, with improved anytime MPE solutions on high-treewidth instances.

  • Problem

    Tight upper bounds help branch-and-bound prune search, but classical methods can make those bounds prohibitively expensive to compute repeatedly.

    Source: §1 · pp. 1–2

  • Method

    L2B trains neural predictors on high-quality bounds and combines statistical calibration with structural constraints that make bounds monotone as evidence accumulates.

    Source: §1 · p. 2, Statistical Calibration · pp. 5–6

  • Results

    Across PGM families, L2B reports bounds 5–10× tighter than MBE, computed in milliseconds, and 1–6% better MPE solutions on high-treewidth Random Uniform and large grid instances.

    Source: §1 · p. 2, §6 · p. 10

  • Takeaways & Limitations

    L2B's bounds are reported to provide the greatest benefit on high-treewidth instances, where classical bounds are loosest.

    Source: §6 · p. 10

    At γ = 0.999, enforcing path monotonicity lowers mean worst-bin calibration coverage from 1.000 to 0.674, though 22/30 PGMs retain test coverage above 0.999.

    Source: Path Monotonicity · p. 9

Abstract

from arXiv · show

Probabilistic graphical models (PGMs) compactly encode structured joint distributions, but Most Probable Explanation (MPE), which finds the highest-probability assignment to unobserved variables, remains computationally intractable in large, densely structured models. Anytime systematic search, such as branch-and-bound (B&B), is a popular approach, but its efficiency depends on tight admissible upper bounds that are often prohibitively expensive to compute using classical methods like Mini-Bucket Elimination (MBE). We introduce Learning to Bound (L2B), a data-driven framework that amortizes bound computation cost by training a neural predictor. L2B targets two key properties required for effective search bounds: admissibility, which is achieved via statistical calibration techniques, and progressive tightening as evidence accumulates, which is enforced through structural architectural constraints that ensure monotonicity by construction. Across challenging benchmarks, L2B delivers tighter, monotonic bounds at orders-of-magnitude lower cost on every PGM family, and yields measurable improvements when integrated with branch-and-bound on high-treewidth instances.

1 Introduction

MPE inference becomes difficult as model size and treewidth grow, while classical upper bounds force a tradeoff between tightness and computation cost. L2B learns calibrated, monotone bounds for branch-and-bound, aiming to combine useful pruning with fast evaluation.

1 Introduction

  • Tighter upper bounds let search prune more of the space, but classical methods face a tightness-cost tradeoff that is especially restrictive when bounds are repeatedly evaluated under partial assignments.Fast bounds may be too weak to guide search, while tighter relaxations require substantially more time and memory.Source: §1 · pp. 1–2
  • Branch-and-bound maintains the best solution found as a lower bound and uses an upper bound on each node's best completion to guide search and pruning.Source: §1 · p. 1
  • L2B trains a neural network offline for each PGM on high-quality bounds, then predicts bounds from partial assignments in milliseconds during search.The training bounds are costly to compute, but serve as informative supervision for the predictor.Source: §1 · p. 2
  • Neural bounds must address two issues: validity is not guaranteed by default, and predictions may increase as evidence is added, unlike classical bounds.L2B uses statistical calibration for validity and an encoding with a Scalable Monotonic Neural Network (SMNN) to enforce monotonicity by construction.Source: §1 · p. 2
  • L2B combines bounds that are monotone by construction with statistical calibration for high-probability validity, and reports tighter bounds at low cost plus improved anytime MPE quality in branch-and-bound.The introduction reports bounds 5–10× tighter than MBE, computed in milliseconds.Source: §1 · p. 2

2 Related Work

Related work motivates L2B through the cost of tight bounds and the lack of formal guarantees in neural inference approaches. L2B predicts calibrated bounds rather than solutions or guidance signals, then uses them within branch-and-bound.

2 Related Work

  • The target setting is repeated inference on an already fitted PGM, where branch-and-bound efficiency depends on upper-bound quality and tight bounds can be prohibitively costly.Source: §2 · pp. 2–3
  • Neural methods that guide combinatorial search typically lack formal solution-quality guarantees, leaving predictions potentially arbitrarily poor on out-of-distribution instances.The paper says its calibration framework provides finite-sample coverage guarantees.Source: §2 · p. 3
  • Unlike neural methods that guide classical inference algorithms, L2B produces admissible bounds with formal coverage guarantees while preserving branch-and-bound exactness.Source: §2 · p. 3
  • Neural MPE-query methods predict solutions without formal quality guarantees, whereas L2B predicts upper bounds, calibrates them, and relies on branch-and-bound to find the MPE.Source: §2 · p. 3

3 Preliminaries

The preliminaries define PGMs and MPE, then explain how approximation bounds can guide branch-and-bound despite potentially high computational cost. Search efficiency hinges on balancing bound tightness against per-node expense.

3 Preliminaries

  • A PGM represents a joint distribution factored over a graph using nonnegative functions over discrete variables.Source: §3 · p. 3
  • MPE seeks the most probable assignment to non-evidence variables given the evidence, while approximation schemes such as max-product and mini-bucket can produce upper bounds without guaranteeing tightness at convergence.Increasing variable-group sizes can tighten these bounds, but computation grows exponentially with the largest grouping.Source: §3 · p. 3
  • Branch-and-bound explores partial assignments, prioritizes branches with higher upper bounds, and safely prunes a branch when its bound falls below the best known solution.Source: §3 · p. 3
  • Tighter bounds enable more aggressive pruning, but computing them with large-i-bound MBE can incur prohibitive cost at each search node.Source: §3 · p. 3

4 Learning to Bound

Learning to Bound (L2B) trains a neural predictor to approximate high-quality MPE bounds, then calibrates its predictions for coverage and constrains the model to be monotone as evidence accumulates.

4 Learning to Bound

  • L2B learns predictions from partial assignments and calibrates them into upper bounds, aiming to make high-quality bounds cheaper to evaluate during repeated branch-and-bound search.The method frames prediction and calibration as two steps toward bounds satisfying a user-specified coverage level.Source: §4 · p. 4

Monotonicity in Evidence

  • Because the optimal MPE score cannot increase as evidence is added, L2B constrains its predictor to be monotone non-increasing along search paths.The approach encodes unassigned variables with all-zero k-hot vectors and uses an SMNN with a negated final output.Source: Monotonicity in Evidence · pp. 4–5

Statistical Calibration

  • Conformal calibration adds a residual quantile to predictions, yielding finite-sample coverage of at least γ under exchangeability of calibration and test data.Unlike Gaussian calibration, the adopted conformal approach does not require normally distributed errors.Source: Statistical Calibration · p. 5
  • Stratifying calibration by evidence size provides per-stratum coverage, while a monotone cap on bin quantiles preserves non-increasing bounds across bin boundaries.Prediction difficulty varies with evidence size, with assignments near the search-tree root described as more uncertain.Source: Statistical Calibration · p. 6
  • At inference, L2B replaces classical bounds in AOBB and reduces per-node overhead from seconds to sub-milliseconds.Nodes whose bounds fall below the current best solution are pruned.Source: Statistical Calibration · p. 6
  • Per-node coverage does not ensure every bound is valid: one underestimate can prune the optimal subtree, and γ trades violation probability against speed.Higher γ produces looser bounds and stronger guarantees; lower γ produces tighter bounds that may prune optimal regions.Source: Statistical Calibration · p. 6

5 Experiments

Across 30 PGMs, calibrated neural bounds offered tighter estimates at lower per-query cost, while the monotone architecture avoided path violations and improved AOBB results on high-treewidth instances. Experiments also exposed a coverage trade-off when calibration was adjusted to preserve monotonicity.

5 Experiments

  • The evaluation covers 30 UAI-competition PGMs from five families, with induced widths of 10–100 and 20,000 training examples per benchmark.For Object Detection and Protein Folding, labels used evidence ratios 0.5–0.9 and i-bound 6 for tractability; baseline comparisons use i-bound 4.Source: §5 · p. 6

Upper Bound Quality

  • Stratified-conformal neural bounds maintain target coverage and achieve tighter gaps across network families in 0.001–0.4 seconds; grids favor JGLP at 10–300× higher computational cost.On Bayesian Networks, neural gaps of 0.02–0.08 compare with 0.19–0.45 for MB; on Random Uniform instances, 0.02–0.03 compare with 0.15–0.29.Source: Table 1 · p. 7, Upper Bound Quality · pp. 7–8
  • At γ = 0.999 on BN_70, raw predictions have gap 0.008 but only 47% valid bounds; stratified conformal yields gap 0.050, 10% tighter than standard conformal.Performance improves with training data up to 10,000 examples, with diminishing returns beyond 20,000.Source: Upper Bound Quality · p. 8

Path Monotonicity

  • SMNN records 0/3000 path violations, while UMLP violates on 849/3000 raw pairs; monotone calibration restores ordering but lowers worst-bin coverage.The monotone cap reduces mean worst-bin calibration coverage from 1.000 to 0.674 at γ = 0.999, while 22/30 PGMs retain test coverage above 0.999.Source: Table 2 · p. 8, Path Monotonicity · p. 9

Branch-and-Bound Integration

  • On high-treewidth instances, SMNN-augmented AOBB improves average MPE by 1–6% over MBE and reaches order-of-magnitude gaps on multiple instances at 10 minutes.The comparison uses matched wall-clock budgets and averages three candidate queries per PGM.Source: Branch-and-Bound Integration · p. 9, Table 3 · p. 10

6 Conclusion

L2B predicts MPE upper bounds with formal statistical guarantees and reports improvements in high-treewidth search; the UMLP predictor is a four-layer feedforward network.

6 Conclusion

  • When integrated into AOBB, neural bounds achieve 1–6% better MPE solutions on high-treewidth Random Uniform and large grid instances (w∗≥60), demonstrating that tight bounds enable faster discovery of high-quality regions.Source: §6 · p. 10
  • Against MBE, L2B delivers a 5–10× lower gap, millisecond rather than minute inference, and finite-sample coverage with a γ-controllable violation rate.The bounds are trained using high-quality supervision from MBE configurations with i-bound 10.Source: §6 · p. 10

A UMLP

  • The UMLP predictor has four fully connected layers, with batch normalization, ReLU, and dropout (p = 0.2) after each hidden layer.The layer widths are 512, 512, 256, and 1.Source: A UMLP · p. 14

B Neural Architecture and Path Monotonicity

The SMNN architecture makes predicted bounds non-increasing as evidence accumulates, while the L2B pipeline combines evidence encoding, neural prediction, and stratified conformal calibration.

B Neural Architecture and Path Monotonicity

  • Positive-weight layers, non-decreasing saturating activations, evidence encoding, and final output negation make SMNN bounds monotone non-increasing as search deepens.The encoding makes accumulating evidence a bitwise increase in the input vector.Source: B Neural Architecture and Path… · p. 14
  • Across 3,000 parent–child evidence pairs from 30 benchmark PGMs, SMNN had zero monotonicity violations, versus 28.3% for a standard MLP.The architecture is designed to prevent path-correctness violations that can lead to unstable pruning and search artifacts.Source: B Neural Architecture and Path… · p. 14

C L2B Pipeline

  • L2B encodes partial assignments, predicts a raw log-likelihood score with SMNN, then adds an evidence-size-bin quantile from stratified conformal calibration.The calibration provides a formal coverage guarantee of at least γ and adapts the margin to prediction confidence.Source: C L2B Pipeline · p. 14

D Benchmark Details

The evaluation covers 30 PGM benchmarks across five model families and includes selected instances with induced widths from 10 to 80.

D Benchmark Details

  • The 30 UAI competition PGMs span five families: Bayesian networks, grids, segmentation, random uniform, and WCSP or structured prediction models.The suite includes real-world, synthetic, image-segmentation, and protein-folding instances.Source: D Benchmark Details · pp. 14–15
  • Figure 1 reports zero SMNN monotonicity violations across 30 benchmark PGMs, while an unconstrained MLP violates monotonicity on 28.6% of parent–child pairs.The comparison concerns empirical effects along AOBB search paths.Source: Figure 1 · p. 15
  • Selected evaluation instances span induced widths from 10 to 80.The study uses these instances to evaluate L2B across diverse difficulty levels.Source: D Benchmark Details · p. 15

E Additional Calibration Results

The appendix compares calibration and search outcomes, then reports the data-generation, integration, and amortization conditions behind them. L2B’s high-treewidth AOBB gains are strongest where classical methods struggle.

E Additional Calibration Results

  • 10–20% tighter gaps than other calibration methods were achieved by stratified conformal calibration, while neural bounds maintained target coverage and lower gaps than mini-bucket elimination.The per-bin margins adapt to assignment-size-dependent difficulty.Source: E Additional Calibration Results · p. 17, Table 5 · p. 17
  • 5–14% better solutions were found by neural bounds on Random Uniform instances (w∗=45–52), with improvements appearing early and remaining stable.Large grids (w∗=40–80) show similar positive gaps; the appendix attributes the greatest benefit to settings where classical methods struggle most.Source: E Additional Calibration Results · p. 17

Data Generation Details

  • 20,000 examples per PGM were generated using Gibbs sampling with a 2B-step burn-in and partial-assignment sizes biased toward smaller assignments.The dataset split was 50% training, 10% validation, 20% calibration, and 20% test; calibration data was held out until after training.Source: Data Generation Details · p. 18

Data Generation and Training

AOBB Integration

  • On rus and BN_70, UMLP goes deeply negative (−0.14 to −0.42), producing invalid bounds because the SMNN-tuned desc/nn-prune configuration is safe only for monotone heuristics.Source: AOBB Integration · p. 20

G Computational Costs

  • ≈3 h to ≈60 h of one-time label generation was balanced against a break-even point of roughly 1,000–6,000 repeated queries on random-uniform instances.Predictor training took at most 10 minutes and calibration under 0.01 ms per query; the authors position L2B for repeated inference rather than one-shot queries.Source: G Computational Costs · p. 20

I Alternative Encoding: Consecutive 2-Hot

The section tests consecutive 2-hot inputs against one-hot inputs while retaining the monotonicity-preserving architecture. Its relative tightness depends on whether the PGM’s values have meaningful ordinal structure.

Encoding design

  • The 2-hot scheme sets bits k and k+1 for observed value k, adding an ordinal smoothness bias while preserving the monotone evidence-input relation.It uses d+1 bits per variable, as does one-hot encoding.Source: I Alternative Encoding: Consecutive… · p. 20

Calibration

  • Coverage remained sound across encodings: at γ = 0.999, empirical coverage was ≥0.94 on every PGM and exactly 1.00 on 28/30.The conformal calibrators behaved identically on coverage to their one-hot counterparts.Source: I Alternative Encoding: Consecutive… · p. 21

Encoding results

  • 2-hot encoding won on 4/5/5 of 30 PGMs at γ = 0.95/0.99/0.999, with wins concentrated in PGMs whose factors have ordinal or spatial structure.One-hot won on 26/25/25 PGMs at the same respective confidence levels.Source: I Alternative Encoding: Consecutive… · p. 22

Why encoding matters

  • Adjacent-bit correlation can hurt on arbitrarily labeled values, while ordinal or spatial factor structure can make the encoding’s smoothness bias a better fit.The authors link 2-hot wins to segmentation, protein-folding, and grid-Ising structure, and losses to rus, WCSP, and object detection.Source: I Alternative Encoding: Consecutive… · p. 22

Practical recommendation

  • The authors recommend one-hot as the safer default without known ordinal structure and suggest evaluating 2-hot when values have domain-specific order.For binary domains, the encoding distinction collapses; the alternatives have the same d+1-bit width and no additional inference cost.Source: I Alternative Encoding: Consecutive… · p. 22

J Monotone-Stratified Conformal Calibration

Independent per-bin conformal quantiles can make calibrated bounds increase across evidence-size boundaries, despite a monotone neural predictor. A non-increasing quantile cap restores path monotonicity, at a cost to effective coverage.

J Monotone-Stratified Conformal Calibration

  • 63/3000 parent-child pairs violated monotonicity under standard stratified conformal because per-bin quantile jumps can offset the neural bound’s monotonicity.Evidence size weakly increases from parent to child, and naturally increasing quantiles can make the calibrated bound rise at a bin boundary.Source: J Monotone-Stratified Conformal… · p. 22
  • A left-to-right cap makes the quantile schedule non-increasing across bins, so the calibrated bound remains deterministicly monotone along search paths.The method caps each bin’s stratified quantile at the preceding bin’s capped value.Source: J Monotone-Stratified Conformal… · p. 22
  • 0/3000 parent-child pairs violated monotonicity with the monotone-cap calibrator, versus 63/3000 with standard stratified conformal and 823/3000 with an unconstrained MLP.Capping quantiles reduces effective per-bin coverage; at γ = 0.999, mean worst-bin coverage fell from 1.000 to 0.674.Source: J Monotone-Stratified Conformal… · p. 22

K Branch-and-Bound Integration Algorithm

  • The L2B-guided AOBB procedure replaces mini-bucket elimination in the search loop with neural bound computation.The algorithm description identifies the neural bound query as replacing the classical bound computation.Source: K Branch-and-Bound Integration Algorithm · p. 23

L Reproducibility

The reproducibility materials specify deterministic experiment settings and report protocols for encoding and AOBB comparisons. The encoding comparison varies the input encoding while holding the other evaluation conditions fixed.

Reproducibility

  • All experiments used fixed seed 42, and the authors state that the complete pipeline and trained models would be publicly available upon publication.Evidence queries were generated deterministically from the test split.Source: L Reproducibility · pp. 23–24

Encoding comparison

  • The 1-hot versus 2-hot comparison used the same per-PGM test subsets and calibration set, with encoding as the only varied axis.The table reports gap and empirical coverage at γ = 0.95, 0.99, and 0.999, alongside MB-i4 and JGLP-i4 gaps.Source: Table 7
  • 1-hot had lower gaps on 26/25/25 PGMs and 2-hot on 4/5/5 at γ = 0.95/0.99/0.999, respectively, with no ties.The strict-better-gap counts are reported out of 30 PGMs at each confidence level.Source: L Reproducibility · p. 26

AOBB comparison

  • The AOBB tables report mean MAP improvement over MBE for matched evidence queries and orderings, with results separated into high- and moderate/low-treewidth buckets.The high-treewidth table averages three queries per PGM at two calibration levels under a 600 s deep budget.Source: Table 11 · p. 30, Table 12 · p. 31
Loading 2610.39305v1…