Learning to Condition: A Neural Heuristic for Scalable MPE Inference

We introduce learning to condition (L2C), a scalable, data-driven framework for accelerating Most Probable Explanation (MPE) inference in Probabilistic Graphical Models (PGMs), a fundamentally intractable problem. L2C trains a neural network to score variable-value assignments based on their utility for conditioning, given observed evidence. To facilitate supervised learning, we develop a scalable data generation pipeline that extracts training signals from the search traces of existing MPE solvers. The trained network serves as a heuristic that integrates with search algorithms, acting as a conditioning strategy prior to exact inference or as a branching and node selection policy within branch-and-bound solvers. We evaluate L2C on challenging MPE queries involving high-treewidth PGMs. Experiments show that our learned heuristic significantly reduces the search space while maintaining or improving solution quality over state-of-the-art methods.

Contributions. This paper introduces a neural network-based conditioning strategy for MPE inference in PGMs, with the following key contributions:

• We formalize learning to condition (L2C) as a scoring problem over variable-value pairs that jointly optimizes for solution preservation and inference tractability.

• We design a data-efficient supervision strategy that generates labels using oracle solutions and solver statistics, avoiding the need for exhaustive MPE enumeration.

• We introduce an attention-based architecture that generalizes across instances and yields informative optimality and simplification scores.

• We demonstrate that our method improves both inference efficiency and solution quality over classical heuristics across a range of benchmark PGMs.

Our results show that L2C enables scalable, learned conditioning decisions that adapt to instance structure, outperforming traditional heuristics in both speed and accuracy. Our implementation, solver integrations, and experiment scripts are publicly available at, https://github.com/brijml/L2C.