Research map / Probabilistic and scientific modeling / Molecules and proteins
Learning to Condition: A Neural Heuristic for Scalable MPE Inference
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes learning to condition (L2C), an attention-based neural scorer trained on MPE solver search traces to pick variable-value conditioning decisions that speed up exact and anytime MPE solvers on high-treewidth PGMs.
Problem
MPE inference in probabilistic graphical models is NP-hard, and choosing which variables to condition on (and to which values) strongly affects solver effort and solution quality, while existing heuristics generalize poorly.
Approach
Train an attention-based network with two heads, an optimality head (BCE on oracle MPE solution assignments) and a simplification head (list-ranking loss on inverse solver runtime/node statistics), and use its scores for greedy/beam conditioning or as SCIP branching and node-selection rules.
Key results
- L2C-Rank frequently surpasses the non-conditioned SCIP oracle across all 12 configurations, while strong branching and the graph heuristic only occasionally improve log-likelihood.
- With AOBB as oracle, L2C reduces processed node count substantially while keeping solution gaps near zero, whereas baselines show larger gaps at deeper conditioning.
- Per-decision time for L2C is around 0.001-0.025 s across networks, versus up to ~20 s for full strong branching.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use L2C-Rank instead of graph-based conditioning decisions | Greedy conditioning for MPE inference with SCIP · 14 high-treewidth PGMs | log-likelihood gap | Helped |
| Use L2C-Rank instead of full strong branching for conditioning | Greedy conditioning for MPE inference with SCIP · 14 high-treewidth PGMs | log-likelihood gap | Helped |
| Use L2C-Rank conditioning before AOBB | AOBB MPE inference · 14 high-treewidth PGMs | processed node count | Helped |
| Use L2C-Rank predictions for branching and node selection | SCIP branch-and-bound · 14 high-treewidth PGMs | log-likelihood | Helped |
| Use beam search rather than a single conditioning sequence | L2C conditioning · 14 high-treewidth PGMs | log-likelihood gap | No clear effect |
Surprising findings
- Full strong branching and the graph-based heuristic often fail to improve over unconditioned SCIP, and their performance degrades with more conditioning decisions.
Limitations
- Scalability to much larger models (millions of variables and factors) is untested and requires efficient data collection.
- Supervision relies on solver signals that may be noisy, and surrogate statistics are used when the solver times out.
- Only binary variables and only conditioning/branching guidance are considered; richer solver signals such as branch-and-cut are not used.
Experimental setup
Datasets: UAI inference competition PGMs (14 high-treewidth binary models)
Benchmarks: UAI inference competition PGMs (BN 12, BN 9, BN 13, Grid 20, BN 65, BN 59, BN 53, BN 49, BN 61, BN 45, Promedas 68, Prom
Metrics: average log-likelihood gap (%) node reduction (%) win counts vs oracle per-decision time
Baselines: graph-based max-degree heuristic full strong branching SCIP default heuristics AOBB
Builds on: AND/OR branch and bound full strong branching SCIP Gibbs sampling
Closest papers by meaning
- A Neural Network Approach for Efficiently Answering Most Probable Explanation Queries in Probabilistic Models (NeurIPS 2024 · similarity 0.90)
- Neural Network Approximators for Marginal MAP in Probabilistic Circuits (AAAI 2024 · similarity 0.85)
- Large Language Models to Enhance Bayesian Optimization (ICLR 2024 · similarity 0.84)
- On the Hardness of Probabilistic Neurosymbolic Learning (ICML 2024 · similarity 0.84)
- Token-Supervised Value Models for Enhancing Mathematical Problem-Solving Capabilities of Large Language Models (ICLR 2025 · similarity 0.84)
- Soft Reasoning: Navigating Solution Spaces in Large Language Models through Controlled Embedding Exploration (ICML 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.