Learning to Condition: A Neural Heuristic for Scalable MPE Inference
Authors: Brij Malhotra
Shivvrat Arya
Tahrima Rahman
Vibhav Giridhar Gogate
Venue: NeurIPS 2025 poster ()
Keywords: Most Probable Explanation
Probabilistic Graphical Models
Conditioning Heuristics
Primary area: probabilistic_methods
TL;DR: The paper proposes a neural network–based learned heuristic that accelerates MPE inference in high-treewidth PGMs by predicting impactful variable assignments from solver traces, significantly reducing search space while preserving solution quality.

Abstract: 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.

Learning to Condition: A Neural Heuristic for Scalable MPE Inference
Brij Malhotra
Shivvrat Arya Department of Computer Science New Jersey Institute of Technology shi shivvrat. arya@njia jit, edu
Department of Computer Science
The University of Texas Dallas www.ootaruuuallllassoooomm
Tahrima Rahman
Vibhav Gogate
Department of Computer Science The University of Texas at Dallas tahrima. ra raaman@utdallas. edu
Department of Computer Science The University of Texas at Dallas vibhav gogate@utdallas. edu
Abstract
We introduce learning condition (L2C), scalable, data-driven framework for accelerating Most Probable Explanation (MPE) inference in Probabilistic Graphical Models (PGMs), fundamentally intractable problem. L,CC trains neural network to score variable-value assignments based on their utility for conditioning, given observed evidence. To facilitate supervised learning, we develop scalable data generation pipeline that extracts training signals from the search traces of existing MPE solvers. The trained network serves as heuristic that integrates with search algorithms, acting as conditioning strategy prior to exact inference or as branch- ing and node selection policy within branch-and-bel 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 titte-of-hh-aase tht-hhart art methods.
solvers. We evaluate L2C
1 Introduction
Probabilistic Graphical Models (PGMs) D. such as Bayesian Networks and Markov Networks, efficiently encode joint probability distributions over large set of random variables, enabling structured reasoning under uncertainty. A fundamental inference task in these models is the Most Probable Explanation (MPE) query, where the goal is to find the most likely assignment of values to unobserved variables given observed evidence.
Answering MPE queries is computationally intractable in general due to their NP-hardness, and becomes particularly challenging as model complexity and scale increase. Classical exact methods such as AND/OR search 2 3 and integer linear programming (ILP) [[]guarattte optimality but are prohibitively expensive for large instances. Approximate methods offer scalability but often compromise on solution quality or consistency, especially in domains that demand high-precision inference.
Conditioning on variable fubiet-fixing variables to specific values a common strategy for improving the tractability of inference by simplifying the underlying problem structure. This reduction in complexity can significantly shrink the search space and improve solver performance. This principle underlies classical techniques like cutset conditioning
and recursive conditioning [5). as well as
strong branching heuristics [ in ILP solvers. A related concept in statistical physics is decimation [2,,), which iteratively fixes high-impact variables to reduce the search space message passsing algorithms such Survey Propagation, progressively simplifying the problem instance. However, the
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

effectiveness of these methods is highly sensitive to the choice and ordering of conditioned variables; poor decisions can lead significant degradation in solution quality.
This leads to a fundamental question: which variables should be fixed, to which values, and in what order, to simplify inference while preserving the optimal solution? Fixing variables incorrectly can irrevocably exclude the true optimal solution, whereas deferring all conditioning preserves complete- ness but forfeits the computational benefits of simplification. Ideally, conditioning decisions should be both safe-iee. aligned with optimal solutions and useful-i.e. significantly reduce computational effort.
In principle, access to the complete set of MPE solutions for a given instance would enable the identification of such beneficial assignments. For instance, if variable assumes the same value across all optimal solutions, fixing it would preserve optimality and likely simplify the subsequent problem. In practice, however, enumerating all MPE solutions is infeasible [I3], and exhaustively evaluating the impact of every variable-value pair on solver performance is prohibitively expensive. Consequently, existing methods rely on handcrafted heuristics [14 [5] or structure-based metrics
[16] that often lack generalization.
In this work, we introduce learning to condition (L2C), data-driven approach to rank variable-value assignments based on their utility for conditioning. The goal is to train a neural network to identify assignments that strike a balance between two objectives: preserving access to optimal solutions and simplifying the inference process. To achieve this, we train an inrecttio-bbsed neural network that assigns two scores each variable-value assignment: an optimality score, estimating the likelihood of the assignment's presence in an optimal solution, and a simplification score, measuring the extent to which fixing the assignment reduces solver effort.
We obtain supervision for these scores via a scalable data generation pipeline. For each training instance, we solve the MPE query once using oracle and treat the resulting solution as proxy for the set of optimal solutions. Variable-value pairs present in the solution are labeled as positive examples for the optimality head. To supervise the simplification head, we fix individual variables to their optimal values, re-solve the query, and record solver statistics such as runtime and the number of explored nodes, providing a quantitative measure of the reduction in inference complexity.
key insight of our method that solution ambiguity modulates conditioning risk. If a variable takes the same value across all optimal solutions, fixing it is highly effective but also risky if the estimate incorrect, as could eliminate the true MPE solution. Conversely, when a variable's values are more evenly distributed, conditioning poses less risk. Even if the model slightly misestimates the correct value, the solution space is more tolerant, and optimality may still be preserved. Our model implicitly learns to navigate this trade-off by generating soft scores that reflect both expected utility and uncertainty, shaped through diverse training examples.
At inference time, the model assigns scores to all variable-value pairs in the query set for the given instance and conditions on those with the highest scores. This strategy incrementally simplifies the problem while avoiding premature elimination of the optimal solution. Additionally, the learned model can also be integrated into branch-and-Be bouud solvers as node and variable selection heuristics.
Contributions. This paper introduces neural network- based conditioning strategy for MPE infer- ence 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-basse 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 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: h //tgtttbb..tt/t/// com coombbrijml/La
2

---

2 Background
We assume, w.l.o.g,, that all random variables are binary and take values in (0, 1). Individual variables are denoted by uppercase letters (e.g., X), and their assignments by corresponding lowercase letters (e.g., I). Sets of variables are denoted by bold uppercase letters (e.g., X), and assignments to those sets are written in bold lowercase (e.g.. x). Given a full assignment to a set X, and a subset Y C X, we use xy to denote the projection of x onto Y.
A probabilistic graphical model (PGM) M = (X, G) is defined over a set of variables X, collection of log- pes--potentllsssee F .f...... fm.....ff..: and an undirected primal graph G (V, Each log-potential fi E F is defined over subset S(fi) _ X, known as its scope. The vertex set V contains one node for each variable in X, and an edge (Va, Vi) E & is added whenever X₂ and X5 co-occur in the scope of some fi. The model defines the following joint probability distribution:
(M(x) & exp
Σ f(xs())) FEF
We focus on the most probable explanation (MPE) task: given observed evidence variables E C X with assignment c, find the most likely assignment for query variables Q X E. Formally, this is:
MPE(Q, e) arg max PM c) arg max Σ f(((gc)s(n))
q
JEF
This problem NP-hard in general and remains intractable for numerous model families 17
Exact MPE algorithms include bucket elimination [22), which uses variable elimination via local reparameterization, and Mixed Integer Programming (MIP) encodings solved with branch-and- bound solvers like SCIP [23 that combine LP relaxations with systematic search. Such solvers are often anytime, providing progressively better solutions and bounds, with optimality certificates upon con- vergence. Nevertheless, for many real-world PGMMs-particularfy those with high treewidth-exxr exact inference remains computationally infeasible.
Conditioning is a classical strategy for simplifying inference by fixing a subset of variables. For MPE, assigning values qu to conditioning set Qa C Q reduces the problem solving MPE for the remaining variables Qu = Q Qa given evidence e U qd- The resulting residual solution qö and qu form the complete MPE solution. Conditioning is fundamental to exact methods like cutset conditioning recursive conditioning [5]. and search algorithms such as Branch and Bound (B&B) and AND/OR Branch and Bound (AOBB) (24). Conditioning also informs heuristic methods such as decimation strategies inspired by statistical physics (9] T0 25 26].
Branch and Bound (B&B) performs depth-first or best-first search over decision tree, recursively partitioning the assignment space and pruning subproblems using lower bounds from LP relaxations or mini-bucket elimination [27]; its efficiency hinges branching heuristics and bound quality. AND/OR Branch and Bound (AOBB) 24 improves upon B&B by exploiting graphical model structure through pseudo free and an AND/OR search graph. This graph uses OR nodes for variable choices and AND nodes for decomposition points, enabling independent search on conditionally independent components formed by assignments. AOBB further avoids redundant computations by merging nodes with identical separator contexts. Consequently, AOBB can prune substantial portions of the search space, often achieving exponential savings over standard B&B.
Graph-based methods like Mini-Bucker Elimination [27 generate bounds (c.g., upper bounds for MPE) that accelerate B&B and AOBB through earlier pruning. Variable and value ordering heuristics further enhance their effectiveness (8-
Recent efforts integrate learning into solver decisions. In MIP, full strong branching 7
6 uses
one-step look-ahead for selecting branch variables that maximize bound improvement; neural net- works trained via imitation learning can replicate this [2]
32). Other machine learning approaches
include using SVMs to identify optimal decision variables 33 and NNs for effective node-selection strategies [44] Recent neural approaches to MPE inference have concentrated on optimizing relaxed likelihood objectives (35 While these methods eliminate the need for supervision, they provide no guarantees of optimality, they rely continuous relaxations of the MPE objective.
3

---

Our work advances conditioning based simplification by learning scoring function that ranks cariablevvalue assignments according to their utility in reducing inference complexity while preserving optimality.
3 Learning to Condition (L2C)
We propose a neural approach for ranking variable-value assignments based on their utility in simplifying MPE inference while preserving optimality. This task, which we call Learning to Condition (L2C), balances two goals: minimizing inference cost and avoiding exclusion of optimal solutions. Our model learns two scores per assignment: one measuring consistency with optimal solutions and another estimating simplification benefit. These data-driven scores guide the selection of high-confidence assignments and can also be used to steer node selection in B&B solvers. Next, we describe the L2C pipeline, including data generation, neural architecture, training objectives, ranking mechanism, and integration with inference procedures.
3.1 Data collection
We construct dataset of MPE queries and solver outcomes train the L2C model to score variable- value assignments based on two criteria: their consistency with optimal solutions and their ability to simplify inference when fixed. Because enumerating all optimal solutions exhaustively evaluating all assignments is computationally infeasible, we collect targeted supervision using selective oracle queries under randomized input conditions.
The full data collection procedure is described in Algorithm [ Given a probabilistic graphical model
M (X, F, G),, we repeatedly sample full assignments ~ PM and randomly partition the variable set into disjoint subsets: a query set Q C X of size qr |X|, and an evidence set E = X \ Q. The evidence assignment e is formed by projecting x onto E, and MPE solver is invoked compute the optimal solution q" = arg maxq (M e). The resulting assignment, along with runtime and number of nodes explored, is stored as supervision.
To evaluate the impact of variable-value assignments on inference, randomly sample subset C Q of size at most Cmax. and for each C E C, consider both binary assignments C 0 and C = 1. For each assignment, we augment the evidence to form e' u {c c). solve the resulting MPE query, and record solver statistics such as runtime, number of nodes explored, and objective value. These evalu- ations provide supervision for both the simplification and optimality scoring heads.
Algorithm 1: Data Collection for L2C with Conditioning Assignments
Input: PGM M = (X, F, G). Query Ratio gr. Max Conditions Cuax, Budget B
Output: Dataset DB Function SolveMPELMM,e B):
Run MPF solver on A with evidence e and time bound B
return rec = [assign, time, #nodes)
Initialize DB + 0 while not enough samples in DB do
Evaluating all possible variable-value assignments for each instance is computationally prohibitive, es- pecially for large models. To manage this cost, we introduce sampling parameter Cuax that bounds the number of variables considered for conditioning per instance. This allows us gather informative super- vision while keeping the number of additional MPE queries tractable. In practice, Cmax can be chosen based on the model size, the characteristics of the solver, and the available compute budget.
Sample x ~ PM
Q < random subset of X of size gr [
E +- x-XQQ
XE rec + SooveMPE(MM,e) e) Store (e, in DB C random subset of Q of size Cmax for each C C do
for each value e {0, 1 do
e' e'+eufC = ct rec' SolveMMPEMMM Store (e', rec') in DB
When the solver fails to return a result within the allocated time budget B, we log surrogate statisties such as LP-bound improvements or relaxed objective scores. Although these surrogates may be noisy, they increase coverage across instances and improve the generalization ability.
return DB
Each and its corresponding optimal assignment q" (if returned by the MPE solver) in DB serves as supervision for the optimality head. For simplification, we convert the collected solver statistics into ranking distribution over small set of candidate variables C Q. For each candidate C' C, we

---

Ver Verabble Embedding Layer
Evidencs Embeddings
Deniee
RELL
Layer Norts
Dene
Diogest
RELL
Mull-head Allention
Optimality Head
Blook with Skip Connectiions
Dense
RELU
Deriee
000
Variable Embeddings
Danse
Simpuitcation Head
Figure I: Attention-based architecture for scoring variable-value pairs by their utility in simplifying
MPE inference while preserving optimality.
define: PC to where &o is composite scalar derived from multiple solver statistics recorded for the query conditioned on C = c, including runtime, number of search nodes explored, and objective value. These quantities are combined linearly to reflect the overall simplification utility of the assignment. The resulting distribution is normalized using softmax over inverse scores, assigning higher probabilities to variable- value assignments that are more effective at reducing inference cost.
Thus the resulting dataset contains both exact and surrogate supervision, allowing the model to learn balance optimality preservation with inference simplification across a range of graphical model instances.
3.2 Neural network architecture
For a partially observed MPE instance (evidence X with assignment e, query variables Q x E), our model (Figure scores variable-value pairs on their potential for MPE optimality preservation and inference cost reduction. Each pair (X; x;; is represented by an embedding vector [38] For binary variables, an embedding table of size 2 x |X] provides distinct embeddings for each variable's possible values. An additional embedding indicates variable status (observed/evidence or unobserved/query)) enabling support for arbitrary evidence-query partitions.
For each unobserved variable Qi E Q, its value assignment embeddings query multi-head attention module (39 using evidence variable embeddings as keys and values, contextualizing each candidate assignment relative to the instance and enabling the model learn associations between evidence and promising assignments. The output contextualized embeddings, concatenated with their original counterparts, pass through shared encoder (comprising fully connected layers with ReLU activations, residual connections 400, and dropout A1).. This encoder produces representation for each variable-value pair, which is then passed two separate prediction heads.
The optimality head, a two-layer MLP with a sigmoid output, estimates an assignment's likelihood of inclusion in the MPE solution. Trained with binary cross-entropy loss against oracle-derived labels, this head learns a relaxed optimality proxy, capturing generalizable patterns across problem instances.
A separate simplification head, also two-layer MLP, outputs unnormalized scores for candidate assignments. These scores, after softmax normalization, are trained via a list-ranking cross-entropy loss 422, using targets derived from solver statistics (Section 3.Ip like runtime, search depth, or relaxed objectives. By predicting relative utility instead of absolute complexity reduction, this head produces scores that generalize well and exhibit noise robustness.
Our architecture exhibits permutation invariance variable ordering and supports arbitrary evidence- query partitions, promoting generalization. Cross-attention facilitates query-specific evidence condi- tioning, while the dual-head design jointly optimizes solution quality and inference efficiency. This yields flexible scoring function adept at guiding conditioning during inference.
3.3
Loss functions
We train our model using a multi-task objective 43 that combines two losses: binary classification loss for predicting whether variable-value pair is part of an optimal MPE solution, and list-ranking loss that encourages the model to prioritize assignments that simplify inference. These respectively supervise the network's optimality and simplification heads.
5

---

For each query variable Qi E Q and its possible values qi E {0, 1), the optimality head predicts gf E [0, 1], the probability that assignment Qi q is in the oracle MPE solution,
Optimality loss.
where (9) E {0, is the true label. The binary cross-entropy loss is applied independently per pair:
Σ Σ
(1))) log (9) - v/a) log(1 y!
Cupe
Q:EQ (E(U,1)
This formulation supports supervision with multiple optimal assignments, enabling the model to learn from all optimal solutions for a given instance.
Simplification ranking loss. For each instance, the training dataset contains solver statistics for subset of query variables C Q, obtained during data collection described in Section [.1 For each C' E C. we construct a target probability distribution PC that reflects the simplification utility of fixing C c, based on a combination of solver statisties such as runtime, number of nodes explored, and objective value. The simplification head generates scores for all variable-value pairs in Qu which are normalized via softmax into predicted distribution PC: We then compute list-ranking cross-entropy loss 42
Crank
Σ CEC
PC log PC
This loss encourages the model to prioritize assignments that lead to greater reductions in inference cost. Since supervision is available only for a subset of Q, we apply a binary mask to restrict the loss computation to the subset C for which solver statisties were recorded during training. This ensures that only observed variable-value pairs influence parameter updates, while predictions for the rest of Q remain unconstrained.
Joint objective and masking. The total loss com- bines these components as a weighted sum:
Algorithm 2:
Beam Search for L2C
Input:
PGM M, Scoring function J, Initial evidence E, Time limit fl, Max depth
>opt Lopt + Arank Crank
Dmax Beam width W
Here, Aopt and Arank balance the objectives' relative importance. We train using both exact and surrogate datasets. If supervision is available for only one head (optimality or ranking), we apply its loss and mask the other, preventing gradient updates from missing targets. This joint objective allows the model to bal- ance accuracy with inference efficiency by leveraging both exact and approximate supervision.
Output: Approximatc MPE solution Init. beam B ((0,E) //(score,,,oo evid)
for d to Dmaa do Initialize candidate list C' <- foreach (s, Epona) E B do Identify query variables
Qrem = X Equrtial
foreach unfixed Q2 E Qrem do
foreach value q. E {0, 1] do
3.4 Inference-time strategies
E' + Epunial U (Q: = 2:) Let + F(E') Add (s', to Co
At inference time, the model guides variable-value assignment decisions that simplify the MPE problem before the solver is invoked. Given probabilistic graphical model M = (X,F), an initial evidence set E C X, and assignment the model takes the current evidence as input and produces scores for each remaining query variable-value pair (Q; 4:). where Q; E V E and qi E 1).
Sort C' in descending order by score s'
Prune C to retain top W elements
B C
Let (s", E*) + TOPCANDIDATE(B) Run <- SolveMPE(M, E", return q"
The optimality head outputs confidence (4) E [0, for assignment's MPE consistency; the simplification head provides a score of E R for its inference simplification utility. These scores are combined to select conditioning assignments via two strategies:
Greedy conditioning. This strategy iteratively filters assignments by an optimality threshold т. selects the one with the highest simplification score among confident candidates, and adds it to evidence. This repeats for fixed number of steps or until no confident options remain, before passing the simplified MPE query to solver.

---

Beam search. To explore multiple conditioning sequences,
BN 12
5
0
12
12
beam search (Algorithm 2 maintains W partial assignment se- quences. At each step d S Dixx, sequences are expanded with assignments scored as greedy conditioning. The best final sequence provides evidence E' for the MPE solver.
BN 13
11
12
BN 30
12
12
12
BN 32
12
12
45
12
12
Final solution. Let E" denote the final evidence selected by either strategy. The residual MPE query is defined over Quesddal V \ E.. We call an MPE solver (exact anytime) to compute:
BN 49
0
11
12
BN 53
0
10
12
gresdual = arg max PM(q] e*)
BN 59
12
12
q
BN 61
7
12
and return the complete solution q" Tresidual ee..
BN 65
0
10
10
This framework uses learned assignments to restructure the MPE problem, reducing solver complexity while preserving correctness and enabling time-bounded inference.
BN 9
12
12
Prm 60
12
12
Prm 68
2
0
6
11
NN-Guided branch-and-bound search Our neural model also enhances branch-aa and bound (B&B) solvers. It guides branching by selecting variables predicted to simplify the subproblem (using scores akin to greedy conditioning) and uses optimality head predictions to tighten lower bounds. These actions accelerate B&B convergence while maintaining optimality guarantees.
Grid 20
12
12
SB
LO
LR
(a) Wins oracle by time limit for all methods (G: Graph, SB: Full Strong Branching, LO: L2C-OPT, LR: L2C- RANk).
Learning to Condition (L2C) transforms the traditionally static variable selection problem into learned, instance-specific de- cision process. Compatible with both exact and approximate solvers, L2C generalizes across problem instances and enables principled trade-offs between solution quality and computational cost. We next empirically evaluate its performance across di- verse set of benchmarks and graphical models.
BN 12
-.0
-3.8
-4.9
-5.2
BN 13
-1.0
-2.1
-3.1
-.11
BN
-1.66
-20.1
25.3
-3.1
BN 32
-63.7
-66.7
-69.2
-72.1
BN 45
-2.0
-2.8
-3.3
-3.5
BN -6.6
-14.0
-15.7
-11.3
4 Experiments
BN 53
-2.6
-8.1
-12.0
-10.5
BN -3.2
-9.8
-13.9
-15.2
In this section, we evaluate our neural strategies, L2C-OPT (using only the optimality head for scoring) and L2C-RANK (using the
BN
-2.8
-6.8
-13.2
-10.7
BN 65
-0.9
-4.1
-6.2
-6.6
scoring procedure from Section 3.4 We benchmark these strate- gies for two tasks: (1) against standard conditioning heuristics, and (2) as branching and node selection methods within B&B solvers. We begin by describing our experimental framework, including the PGMs, baseline methods, evaluation metrics, and NN architecture.
BN 9
-0.4
-0.8
-1.5
-2.9
Prm
-0.1
-0.2
-0.3
-0.4
Prm 68
-0.1
-0.1
-0.2
-0.2
Grid
-0.2
-0.3
-0.4
-0.6
5%
10%
15%
20%
(b) L2C-RANK oracle LL gap
4.1 Graphical models
Dmax (cols) and graphical model (rows).
We evaluated our method and baselines on 14 high- tigh-treewidth binary probabilistic graphical models (PGMs) from UAI inference competitions 44 45), featuring 90 1444 variables and up 1444 factors. Using Gibbs sampling [1. we generated 12,000 training, 1,000 test, and 1,000 validation examples per model. All MPE instances used 75% of the PGM's variables as query variables. We construct the supervised dataset following the procedure outlined in Section 3.1 During data generation, QR is set to 0.75 and Gmax is set 10% the total number of variables in each PGM.
Figure 2: Neural vs. baseline methods for greedy conditioning (SCIP oracle). (a) Win counts; (b) Log-likelihood gaps. Color:
Darker green stronger, darker red = weaker performance. Grey: Timeouts (30s).

---

L2C-Opt
Graph
Strong Branching
Depth
Depth
Depth
Depth 25%
200
PPre
33
32x
200
2:30 10h
37a
150 5.h
37a
150
140
Avr Gop
Aug Gap
Figure 3: Greedy conditioning methods (AOBB oracle): Average solution gap (x-axis) versus % node reduction (y-axis). Each subfigure denotes fixed decision count.
4.2 Experimental setup and methods
The neural networks in L2C-OPT and L2C-RANK use 256-dimensional embeddings, two multi-head attention layers, and 15 skip-connection blocks. Dense layers have 512 units with 0.1 dropout [4] and ReLU activations. We trained the models using Adam [46] with a learning rate of x 10 exponential decay rate of 0.97, batch size of 128, and early stopping after 5 stagnant epochs (maximum 50 epochs). All models were implemented in PyTorch [47] and executed on an NVIDIA B provides further hyper-parameter details.
A40 GPU. Appendix
Baseline methods: We compare our approach with two heuristic methods: The graph-based heuristic 28 30 prioritizes variables by degree, selecting them in descending order after removing evidence nodes. This max-degree strategy assigns each variable its most likely value, estimated via Gibbs Sampling 48 over the PGM. The full strong branching heuristic (77. classical technique for enhancing branch-and-bont efficiency. formulates the MPE query as an ILP [ It then scores variable-value pairs by their impact on search space pruning.
Oracle: We use two oracles unconditioned queries and as final solvers post-conditioning: the SCIP solver [23], and the AND/OR Branch and Bound (AOBB) solver (per Otten and Dechter [24 and implemented by Otten (3). MPE queries encoded as Integer Linear Programs (ILPs) [I] for SCIP, which applies its branch-and and-bundd algorithm subject to a 60-second time limit per query.
The competing approaches were evaluated based on criteria: log- likelihood scores and runtime. The log-likelihood scores, calculated as (n, q), assesses the quality of the solution in terms optimality. The runtime measures the efficiency of the conditioning process by indicating how quickly each method solves the problem.
Evaluation criteria:
4.3
Empirical evaluations
4.3.1 Greedy conditioning
We evaluate our methods and baselines as scoring functions (F) in a greedy conditioning framework (Section 3.4), selecting up to 25% of query variables For each PGM, we test 12 configurations: four conditioning depths (5%, 10%, 15%, 25% of query variables) combined with three oracle time budgets (10s, 30s, 60s). Post-conditioning. SCIP attempts to solve the residual problem within the allotted budget.
Figure 2a (heatmap) quantifies for each conditioning strategy the number of the 12 configurations where it enabled the SCIP oracle to achieve higher average log-likelihood (LL) score than solving the original, non-conditioned query. The oracle's 's time budget was identical for both conditioned and non-conditioned queries.
The results (Figure 2a show that both L2C-OPT (LO) and L2C-RANK (LR) consistently enhance oracle performance over direct solving of the original query. L2C-RANK performs best, frequently
'To ensure fair comparison. the max mex-eegree baseline supports only a beam size of 1. we use greedy conditioning for neural and strong branching methods. Appendix provides beam search results.

---

surpassing the non-conditioned oracle across all 12 configurations. Conversely, full strong branching (SB) and the graph-based heuristic (G) only occasionally improve LC scores.
Figure 2b presents the average percentage CC gap: & EE -
x 100, where
CCl)) and CCD are the oracle's log- log-liiklshoods for instance without and with conditioning by L2C-RANK, respectively. Rows denote PGMs, and columns indicate conditioning depth (percentage of query variables conditioned). The oracle's time budget is fixed 30s for both approaches.
Predominantly negative (green) values in Figure 2b indicate that L2C-RANK conditioning helps the oracle find superior solutions within the 30s budget. The gap becomes increasingly negative with more conditioning decisions (i.e., greater conditioning depth), demonstrating our method's scalability, This improvement occurs because conditioning simplifies the query by instantiating additional variables, thus presenting an casier query to the oracle.
Assisting AOBB via conditioning: We also evaluated our neural heuristic with the AND/OR Branch and Bound (AOBB) solver B as an alternative oracle.
BN
-4.0
-3.0
-0.3
BN 13
-1.9
-2.2
-0.1
Figure plots the percentage reduction in AOBB's processed node count (y-axis, proxy for effort reduction) against the average LL gap from the exact MPE solution (x-axis) Points near the y-axis indicate high solution quality with reduced effort; greater x-values imply more quality degradation.
BN 30
0.0
.4.7
-0.0
BN 32
0.0
22.1
1.6
BN 45
0.3
-0.2
-3.6
BN 0.0
-3.8
-8.0
BN 53 0.0
-12.3
-10.3
Our conditioning strategies, as shown in Figure yield near-optimal solutions while substantially reducing AOBB's s processed node count. In contrast, traditional baselines exhibit larger solution gaps with increased conditioning depth due to increasingly suboptimal deci- sions. Our methods consistently maintain high solution quality (most points near the y-axis) and more effectively accelerate AOBB by shrinking the search space, particularly with deeper conditioning.
BN 0.0
-11.6
-13.1
BN 61
0.2
-5.7
-6.9
BN
-75
-9.1
-1.8
BN 9
-1.4
-1.1
-0.6
Prm
-0.3
Consequently, L2C enables efficient resolution of queries that are otherwise challenging for the oracle, especially for harge-treewidth models, frequently yielding substantially better solutions under iden- tical time constraints.
Prm 68
0.1
-0.2
-0.0
Grid
-0.8
10
30
Figure 4: Heuristic compar- ison across datasets (rows) and time limits (columns); darker green/red indicates bet- ter/worse L2C-RANK perfor-
4.3.2 NN-Guided mauch-and-bounde search
We also employ our neural network outputs to guide branch-and- bound search, using them as branching rules (32) and node selection heuristics 34 following the methodology detailed in Section 3.4 mance.
Figure comparee our -gured- heuristics against SCIPs default strategies 23 49 51] showing the average LL gap (defined previously) over three time limits and all datasets. The predominantly green cells, particularly dark green ones, in the heatmap signify that our neural heuristics often outperform SCIP's defaults. Furthermore, the few red cells underscore that approach generally matches or surpasses SCIP's default heuristic performance and delivers better solutions within identical time budgets.
4.3.3 Comparing conditioning methods by per-decision time
Table reports the average time required to make single conditioning decision across all networks. Both L2C-OPT and LL2C-RANK maintain consistent decision times across different network sizes, demonstrating the scalability and practical feasibility of our learned heuristics. In contrast, the graph- based heuristic exhibits increasing latency as network size grows, while strong branching is considerably slower and often infeasible for large models. We imposed a 30-second timeout per decision, under which strong branching failed to return results for the largest networks (BN 30 and
NNoe and LL gap reductions for AOBB are relative to its unconditioned execution. AOBB's internal preprocessing and heuristics often enable it to solve MPE queries within the time limit; thus, a reduced node count with near-zero LL gap signifies simplified inference without quality loss.

---

Table Mean + standard deviation of decision time (s) across networks for each branching strategy. Gray cells indicate cases where the 30 s timeout was reached.
Network
L2C-OPT
L2C-RANK
Graph
Strong Branching
BN 12
0.001 = 0.000
0.002 0.001
0.001
0.001
2.215 + 0.161
BN
0.003 = 0.002
0.006 0.004
0.007 0.003
1,256 + 0.115
BN 13
0.001 0.001
0.002 0.001
0.022 0.020
2.787 1 0.114
Grid 20
0.006 0.004
0.011 1 0.004
0.107 0.062
7.325 1 0.117
BN 65
0.005 0.005
0.008 0.005
0.086 0.053
5,871 + 0.320
BN 59
0.005 0.004
0,009 = 0.005
0.097 0.057
10,993 1.683
BN 49
0.007 0.005
0.011 0.004
0.100 0.059
19.713 3.417
BN 53
0.005 0.004
0,009 0.005
0.095 + 0.056
9.106 + 0.993
BN 61
0,009 0.004
0.013 + 0.004
0. + 0.063
20.896 + 3.038
BN 45
0.011
0.005
0.014 0.003
0.088 0.050
8.675 + 0.733
Prm 68
0,013 0.004
0.016
0.085 0.051
4.279 = 0.118
Prm 60
0.015
0.002
0.015 + 0.002
0.089 + 0.052
5,432 + 0.270
BN 30
0.018
0.002
0.018 + 0.002
0.098 + 0.058
BN 32
0.023 0.005
0.025 + 0.009
0. 102 + 0.060
BN 32). Overall, these results show that L2C achieves low and predictable decision costs even as model complexity increases.
Summary: Our comprehensive experiments validate the consistent superiority of L2C. We evaluate our approach using two competitive and complementary solver backends: AOBB, a top-performing AND/OR search solver, and SCIP, state-of-the-art ILP optimizer. This combination encompasses structurally distinct inference paradigms, highlighting the solver-agnostic advantages of learned conditioning. As a conditioning strategy, it empowers SCIP to achieve better solutions within time limits, especially for intractable problems, and allows AOBB to preserve solution quality while drastically reducing search effort (node exploration). Furthermore, employing our neural scores as branching and node selection heuristics enhances SCIP's solution quality under the same time constraints. Importantly, L2C maintains stable decision times across increasing network sizes, underscoring its scalability and suitability for large-scale inference. Collectively, these results affirm our method's effectiveness both as a conditioning strategy, improving solution quality and efficiency and as an effective heuristic guiding manchhand-boud solvers.
5 Conclusion
We introduced Learning Condition (L2C), a neural approach leveraging solver search traces to accelerate Most Probable Explanation (MPE) inference in Probabilistic Graphical Models (PGMs). L.2C learns identify variable assignments that effectively balance inference simplification with optimality preservation, superseding handcrafted heuristics. It serves either as pre-processor simplifying problems for exact solvers or as an internal policy guiding branching and variable selection within search algorithms. Evaluations on high-treewidth models show L2C substantially curtails the search space, achieving solution quality comparable or superior to baselines and thus providing more efficient path to MPE solutions.
Limitations and future work: The current limitations lie in scalability, solver signal diversity, and generalization to unseen model structures. The method is tailored to a fixed PGM and depends on solver-derived supervision, which is costly to obtain at scale. Extending L2C to other solver familics, such as MAXSAT, local search, or soft arc-consistency solvers, would necessitate substantial modifications to the architecture, data collection pipeline, and learning objectives.
Future work will focus on scaling L2C to handle larger models with millions of variables and factors, while employing more efficient and bootstrapped data collection techniques to reduce oracle dependence. We will also integrate richer solver signals (e.g., branch-and-cu statisties) to enhance pruning and design neural bounding mechanisms that extend learned guidance beyond conditioning. Finally, learned variable orderings will be explored for novel neural bounding strategies, extending guidance beyond conditioning to further boost inference performance.
10

---

Acknowledgments and Disclosure of Funding
This work was supported in part by the DARPA CODORD program under contract number HR001 12590089, the DARPA Assured Neuro Symbolic Learning and Reasoning (ANSR) Pro- gram under contract number HR001122S0039) the National Science Foundation grant IIS-1652835, and the AFOSR award FA9550-23-1-0239
References
[1] D. Koller and N. Friedman. Probabilistic Graphical Models: Principles and Techniques. Adaptive computation and machine learning. MIT Press, 2009. ISBN 9780262013192.
[2] Radu Marinescu and Rina Dechter. And/or branch-and- bound for graphical models. In Pro- ceedings of the 19th International Joint Conference on Artificial Intelligence, IJCAI'05, page 224229, San Francisco, CA, USA, 2005. Morgan Kaufmann Publishers Inc.
[3] Lars Otten. Daoopt: Sequential and distributed and/or branch and bound for mpe problems, 2012. URL
[4] Judea Pearl and Rina Dechter. Identifying independence in bayesian networks. Networks, 20 (5):507-534, 1990. doi: 10. 10.10022/eet.22300000333
[5] Adnan Darwiche. Recursive conditioning. Artificial Intelligence, 126(1):5 2001. ISSN 0004-3702. doi: (0.1016/500044377000))))))
[6] Santanu Dey, Yatharth Dubey, Marco Molinaro, and Prachi Shah. A theoretical and computational analysis of full strong-branching. Math. Program., 205(12):303336, 2023. ISSN 0025-5610. doi: 10. 1011077/1000770023.0017774 URL htt.h:ttt//....... http///o..rg/11..10000/1
610107-023-01977--
[7] D. Applegate, R. Bixby, V. Chvatal, and B. Cook. Finding cuts in the tsp (a preliminary report). Technical report, 1995.
[8] M Mézard, Parisi, and Zecchina. Analytic and algorithmic solution of random satisfiability problems. Science, (1 2002.
[9] A. Braunstein, M. Mézard, and R. Zecchina. Survey propagation: An algorithm for satisfiability. Random Struct. Algorithms, 27(2):201226, 2005. ISSN 1042-9832.
[10] Lukas Kroe, Ashish Sabharwal, and Bart Selman. Message-passing and local heuristics as decimation strategies for satisfiability. In Proceedings of the 2009 ACM symposium on Applied Computing, pages 1408-1 14184,44, Honolulu Hawaii, 2009. ACM. ISBN 978-1-60555-166 166-8. doi: 10. 10.1145/1529222,15555 1529596. URL https: //dl. acm. org/ /oi/ 10. 1145/ 1121//12222..... 1529596 TLDR: The results reveal that once the authors resolve convergence issues, BP itself can solve fairly hard random k-SAT formulas through decimation; the gap between BP and SP narrows down quickly as k increases, and the hardness of the decimated formulas is explored.
[11] Keki Burjorjee. Explaining adaptation in genetic algorithms with uniform crossover: The hyperclimbing hypothesis. In Proceedings of the 14th annual conference companion on Genetic and evolutionary computation, pages 1461-1462, Philadelphia Pennsylvania USA, 2012. ACM. ISBN 978- 1778---4500-1111 178-6. doi: 10. 01144/2333784.2309999 do1/10. 111.10..144//330000 23339991
URL httph::///// acm. org/
[12] Lukas Kroc. Probabilistic techniques for constraint satisfaction problems. PhD thesis, USA, 2009. AA13376595.
[13] Radu Marinescu and Rina Dechter. Counting the optimal solutions in graphical mod- els. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' d'Ale Buc, Emily B. Fox, and Roman Gamett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neurul Information Processing Sys- tems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 12091-12101, 2019. URL. http://pprreeeddnnnn.eeirppppppp nwwninuurp... wwwprrpsscccpppee///eeee httpppsccc//pppe/2/////aaaae I (C220444400444004818411111116160 Abt.aatttttettttttttttttt

---

[14] David Poole and Nevin Lianwen Zhang. Exploiting contextual independence in probabilisticc inference. J. Artif. Int. Res., 18(1):263313, 2003. ISSN 1076-9757.
[15] Fridman. Mixed markov models. Proceedings of the National Academy of Sciences, 100(14); 8092-8096, 2003.
[16] Uffe Kjærulff. Triangulation of graph - algorithms giving small total state space. Technical Report R90-09, Aalborg University, Denmark, 1990.
[17] Gregory F. Cooper. The computational complexity of probabilistic inference using bayesian belief networks. Artificial Intelligence, 42(2-3);393-405, 1990. ISSN 00043702. doi: 10.1016/ (004-3702(990)90060-
[18] James D. Park and Adnan Darwiche, Complexity results and approximation strategies for map explanations. Artif. Int. Res., 21(1):101133 133, 2004. ISSN 1076-9757
[19] Cassio P. de Campos. New complexity results for MAP in bayesian networks. In Toby Walsh, editor, IJCAI 201 Proceedings of the 22nd International Joint Conference on Artificial Intelligence, Barcelona, Catalonia, Spain, July 16-22, 2011, pages 2100-2106. ICCA/AAAL, 2011. doi:
URL htt.:::tt///oo..... http/////oooo//////o// 559111.551/
978 978-1-97755-566-811CAA1T
[20] Diarmaid Conaty, Cassio P. de Campos, and Denis Deratani Mauá. Approximation complexity of maximum A posteriori inference in sum-product networks. In Gal Elidan, Kristian Kersting, and Alexander T. Ihler, editors, Proceedings the Thirty-Third Conference Uncertainty in Artificial Intelligence, UAI 2017, Sydney, Australia, August 11-15, 2017. AUAI Press, 2017. HtRlhhtp::// org/ uai uai2017
/ttpaaa/oo.a..//ooorrrrr//////// http://edin///ppppraeaee.a 109 109 .dff
[21] Robert Peharz. Foundations of Sum-Product Networks for Probabilistic Modeling. PhD thesis, Medical University Graz, 2015.
[22] Rina Dechter. Bucket elimination: unifying framework for reasoning. Artificial Intelligence. 113(1-2):41-85) 1999. doi: 111016/800004-3700/99000000
[23] Suresh Bolusani, Mathieu Besançon, Ksenia Bestuzheva, Antonia Chmiela, João Dionísio, Tim Donkiewicz, Jasper van Doornmalen, Leon Eifler, Mohammed Ghannam, Ambros Gleixner, Christoph Graczyk, Katrin Halbig, Ivo Hedtke, Alexander Hoen, Christopher Hojny, Rolf van der Hulst, Dominik Kamp, Thorsten Koch, Kevin Kofler, Jurgen Lentz, Julian Manns, Gioni Mexi, Erik Mühmer, Marc E. Pfetsch, Franziska Schlösser, Felipe Serrano, Yuji Shinano, Mark Turner, Stefan Vigerske, Dieter Weninger, and Lixing Xu. The SCIP Optimization Suite 9.0. Technical report, Optimization Online, 2024. /RLL/tttp://oopmmmizatttoo online org/ 2024/02/the-scip- sptp-oppimizationn wtt.oppiiiiiiiiooaasate---00001
[24] Lars Otten and Rina Dechter. A case study in complexity estimation: Towards paral- lel branch-and-bound over graphical models. In Nando de Freitas and Kevin P. Mur- phy, editors, Proceedings of the Twenty-Eighth Conference on Uncertainty in Artificial In- telligence, Catalina Island, CA, USA, August 14-18, 2012, pages 665-674, AUAI Press, 2012. URL
http://///.../.ppppaaattttttttta jmmmmmuu ftsmuuu
2earticle 1d 232
1d=28.
[25] Andrea Montanari, Federico Ricci-Tersenghi, and Guilhem Semerjian. Solving constraint satis- faction problems through belief propagation--guiee decimation. ArXiv preprint, abs/0709.1667, 2007. URL hhtps::////
pestps://arxiyy //tpx//axvvvvvv////// www./rgg//bb//o/o httppss///aaii...oor//aaa//////
1667
[26] Shaowei Cai, Chuan Luo, and Haochen Zhang. From decimation to local search and back: new approach to maxsat. In Carles Sierra, editor, Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia, August 19-25, 2017, pages 57 1-77. ijcai.org, 2017. doi: 10.249633/jcai.2011788 https:s:://dol org/
10. 24963/9 cai 2017/80
[27] Rina Dechter. Mini-buckets: general scheme for generating approximations in automated rea- soning. In Proceedings of the Fifleenth International Joint Conference on Artificul Intelligence Volume 2, IJCAI'97, page 12971302, San Francisco, CA, USA, 1997. Morgan Kaufmann Publishers Inc. ISBN 15558604804.
12

---

[28] Sajjad Siddiqi and Jinbo Huang. Variable and value ordering for mpe search. In Proceedings of the 23rd Conference on Uncertainty in Artificial Intelligence (UAI), Arlington, Virginia, USA, 2008. AUAI Press.
[29] Radu Marinescu and Rina Dechter. Dynamic orderings for ANDIOR branch-and -ouudd search in graphical models. In Proceedings of the 18th European Conference on Artificial Intelligence (ECAT), 2006.
[30] Radu Marinescu, Kalev Kask, and Rina Dechter. Systematic versus nonsystematic search algo- rithms for most probable explanations. In Proceedings of the 19th Conference on Uncertainty Artificial Intelligence (UAI), 2003.
[31] Elias Boutros Khalil, Pierre Le Bodic, Le Song, George L. Nemhauser, and Bistra Dilkina. Learning to branch in mixed integer programming. In Dale Schuurmans and Michael P. Wellman, editors, Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, February 12-17, 2016, Phoenix, Arizona, USA, pages 724-731. AAAI Press, 2016. URL http://www , aaai . wwg/ocg/////o/oooo..ooooo... wwloo//indeeeee.eeeeeeeeeeeeeeee pwppp/AI//////// TAT.//AAAAAAAAI/AA http////pppe/vii//eee/// 12214
[32] Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact combinatorial optimization with graph convolutional neural networks. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Buse Emily B. Fox, and Roman Gareett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 15566, 2019. URL https: pwwoe//ddng..cceoeggee.. neur neurips...... cc/ccppr.r......ccccccoc -rteodd--bbstrr Abstract htmll.
[33] Yuan Sun, Xiaodong Li, and Andreas Ernst. Using statistical measures and machine learning for graph reduction to solve maximum weight clique problems. IEEE Transactions on Pattern Anal- ysis and Machine Intelligence, (3(5):1746-177) 2021. doi: 10. 109/TPAMI.2019.2999
[34] Yunzhuang Shen, Yuan Sun, Andrew Eberhard, and Xiaodong Li. Learning primal heuristics for mixed integer programs. In 2021 International Joint Conference on Neural Networks (IJCNN), pages 1-8, 2021. doi: 10.1 1011109NNNNNN2388822 2021 .9533651.
[35] Shivvrat Arya, Tahrima Rahman, and Vibhav Gogate. Neural network approximators for marginal map in probabilistic circuits. In Proceedings of the Thirty-Eighth AAAI Conference on Artificial Intelligence, AAAI24. AAAI Press, 2024. ISBN 978-1-57735-855 --7773--887-- doi:
10. wttp://aai.v810.2288888
URL hattss://dol org/10. 10. 16190/......a....... ww8.10..11..0 28966
[36] Shivvrat Arya, Tahrima Rahman, and Vibhav Gogate. A neural network approach for effi- ciently answering most probable explanation queries in probabilistic models. In A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tomczak, and C. Zhang, editors, Advances in Neural Information Processing Systems, volume 37, pages 33538-33601 Inc., 2024.
Curran Associates,
[37] Shivvrat Arya, Tahrima Rahman, and Vibhav Giridhar Gogate, SINE: Scalable MPE inference for probabilistic graphical models using advanced neural embeddings. In The 28th International Conference on Artificial Intelligence and Statistics, 2025.
[38] Tomas Mikolov, Kai Chen, Gregory S. Corrado, and Jeffrey Dean. Efficient estimation of word representations in vector space. In International Conference on Learning Representations, 2013.
[39] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett, editors, Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pages 5998-6008, 2017. URL 1ttp://4554/6e1111b00beeeeeeeee.
neur ps. cccppsccc.pp.cccccccc.ccoo. wwtp:ccpppppppeeteet htt////pprr//// 2017/2201hhhhh/ htmll
[40] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In 2016 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2016, Las Vegas, NV, USA, June 27-30, 2016, pages 770-778. IEEE Computer Society, 2016 doi: 10.1100//VP...0016. URL htthst // org/10 10. 1109/CVPR. 2..09//VPR.206..00 2016.90
13

---

[41] Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: Simple Way to Prevent Neural Networks from Overfitting, Journal of Machine Learning Research, 15(56):1229-1558 2014. ISSN 1533-7928.
[42] Zhe Cao. Tao Qin, Tie-Yan Liu, Ming-Feng Tsai, and Hang Li. Learning to rank: from pairwise approach to listwise approach. Proceedings of the 24th International Conference on Machine Learning. ICML '07, page 129136, New York, NY. USA, 2007. Association for Computing Machinery. ISBN 9781595937933, doi: 1..144/1123349612233111 URL
1ttg//...114//27339998 1273513
[43] Rich Caruana. Multitask learning. Machine Learning, 28(1):41-75, 1997. doi: 10.1023/A:
1007379606734.
[44] G. Elidan and A. Globerson. The 2010 UAI Approximate Inference Challenge. 2010.
[45] Rina Dechter, Alexander Ihler, Vibhav Gogate, Junkyu Lee, Bobak Pezeshki, Annie Raichev, and Nick Cohen. UAI 2022 competition, 2022. URL
github
io/uci-2022
[46] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Yoshua Bengio and Yann LeCun, editors, 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015. URL /ttt:///rxxv..oo wwwg/bb///a 0atss//41...999
[47] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Yang. Zachary VeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence Jiché-Buc, Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 8024-8035, 2019. URL httph:: htttps://proceedding neur pt..cp...c.pp.e.ee. wttpcc///aperr219////aaaa ptpppa/ssssppppss.ppppppeee////e
[48] Kalev Kask and Rina Dechter. Stochastic local search for bayesian network. In David Hecker- man and Joe Whittaker, editors, Proceedings of the Seventh International Workshop Artificial Intelligence and Statistics, volume R2 of Proceedings of Machine Learning Research. PMLR, 03-06 Jan 1999. URL httpps:/pproceedingg. mlr http:/ccciiigaa......ee//a/aaaaa html Reissued by PMLR on 20 August 2020.
[49] Tobias Achterberg, Timo Berthold, and Gregor Hendel. Rounding and Propagation Heuris- ties for Mixed Integer Programminng page 7176. Springer Berlin Heidelberg, 2012. ISBN 9783642292101. doi: 10.1007/978-3 3-42--2221-21111111111-11 URL http://dxx doi wtt.dd/.....oo////o////
01117998-33-64-2221--000
[50] Tobias Achterberg and Timo Berthold. Hybrid branching. In Proceedings of the 6th Inter- national Conference Integration of Al and OR Techniques in Constraint Programming for Combinatorial Optimizution Problems, CPAIOR '09, page 309311, Berlin, Heidelberg, 23. URL
2009. Springer- Verlag. ISBN 9783642019289, doi: 10. 10.10077977-3-642--0099 https: org/ ntrg/10.1u 10070000777780 002-6642-111 6422019292622221
[51] Chris Wallace. Zi round, a mip rounding heuristic. Journal of Heuristics, 16(5):115722, 2009.
ISSN 1572-9397. doi: 10.10077:103332-099999
http:///://d wttp://...../1110000......00...0
810732-009-9114-6
14

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: [NA]
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: [NA]
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [NA]
15

---

Justification: [NA]
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
16

---

Answer: [Yes]
Justification: We will release the code as part of our supplementary materials. Furthermore, the UAI benchmark models used in the paper for experiments are available online.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release code and data, we understand that this might not be possible, so No is acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to to reproduce the results. See the NeurIPS code and data submission guidelines (https
Soo.eduuuee ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We provide most the details in the main paper and additional details in the supplementary materials
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emrr bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
17

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: [NA]
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics htttps///eerrpps...pppbbbt//ttt
Answer: [Yes]
Justification: [NA]
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction..
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our paper improves the speed. accuracy and scalability of Branch & Bound and other exact solver for MPE inference. Since algorithms already exist for solving MPE tasks, we do not perceive any negative or positive societal impacts beyond what currently exists.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
18

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: [NA]
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, papprssiiiiii thoode com datastts has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
19

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
20

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy pattps://neuripee /ttpaarrppp.cc///ooeeeeee//////s for what should or should not be described.
21

---

A Description of the probabilistic graphical models
Table summarizes the networks used in our experiments, listing the number of variables and factors in each. The experiments were conducted high-treewidth probabilistic graphical models (PGMs) of varying sizes, with the number variables ranging from 90 to 1440 and factor counts covering similar range. The table also lists the network aliases used throughout the paper for ease of reference.
Table 2: Summary of networks used in our experiments, including the number variables and factors for each.
Network Name
Network Alias
Number of Factors
Number of Variables
BN I2
BN 12
90
90
BN 9
BN 9
105
105
BN 13
BN 13
125
125
grid20x20.f5.o wrapp
Grid 20
1200
400
BN_ 65
BN
440
440
BN_59
BN 59
540
540
BN
BN
561
561
BN 49
BN 49
661
661
BN_
BN
667
667
BN 45
BN 45
880
880
Promedas
Prm 68
1022
1022
Promedas 60
Prm 60
1076
1076
BN
BN
1156
1156
BN_ 32
BN 32
1440
1440
B Hyperparameter details
We used consistent set of hyperparameters across all networks in our experiments. From the initial dataset of 14,000 samples, we allocated 13,000 for training and 1,000 testing. The training set was further split into 12,000 samples for training and 1,000 for validation.
The neural networks in L2C-OPT and L2C-RANK 256-dimensional embeddings, multi-head attention layers, and 15 skip-connection blocks. Dense layers have 512 units with 0.1 dropout 41 and ReLU activations. We trained the models using Adam [66] with learning an exponential decay rate of 0.97, a batch size of 128, and early stopping after 5 stagnant epochs (maximum 50 epochs). All models were implemented in Py PyTorch [47] and executed on an NVIDIA A40 GPU. After training. we evaluated the model on 1,000 MPE queries with query ratio of 0.75, defined as the fraction of variables in the query set.
of x 10 10-4
Hyperparameters were selected via 5-fold cross-validation. In particular, the weighting parameters Aopt and Arank were eritical for balancing the preservation of optimal solutions with inference efficiency. We searched over Aope E {0.3, 0.35, 0.4, 0.45, 0.5) and set Arank = Aopt-
C Extending L2C to multi-valued and continuous domains
While the main formulation of Learning to Condition (L.CC focuses on binary variables for simplicity, the framework generalizes naturally to multi-valued discrete and continuous domains with minor architectural and procedural modifications.
C.1 Multi-valued discrete variables
For multi-valued variables, we define variable-value pair for each possible assignment. During data collection, the same procedure is used to gather solver traces, now over the expanded set of candidate pairs. The attention-based scoring architecture remains unchangedeach (variable, value) pair is embedded independently and scored through the same optimality and simplification heads. This formulation allows 1.2C to reason jointly over variablevalue combinations without requiring major adjustments to training or inference. At inference time, greedy or beam-based selection can be
22

---

performed over all pairs, and conditioning proceeds as in the binary case. The learned heuristic thus generalizes directly categorical domains.
C.2 Continuous variables
Directly applying L2C to continuous domains is infeasible because the set of possible values is uncountable. To adapt, we discretize each continuous variable into finite of representative values (e.g., via uniform or quantile-bare based binning). The data collection process then conditions on these discretized values and records solver statistics as in the discrete case. During training, embeddings are created for each (variable, discretized value) pair, and the existing attention- based network and loss objectives are applied without modification. To mitigate discretization artifacts, soft-label targets or local smoothing can be used to ensure smooth transitions across adjacent bins.
At inference time, the model selects promising (variable, value) pairs based on the learned scores. After conditioning on discretized values, local continuous optimization methods (e.g.. gradient descent, coordinate search) can optionally refine assignments within selected regions, improving precision beyond discretization resolution. This hybrid strategy allows L2C to extend its learned conditioning capabilities continuous-variable inference while maintaining compatibility with existing solver frameworks.
D Greedy conditioning performance using SCIP as oracle
In this section, we analyze the conditioning performance of methods under varying oracle time budgets and numbers of greedy conditioning decisions when SCIP solver (23] is used as the oracle. For each method and network, we report the average percentage gap log-likelihood. The y-axis in Figures 5 to shows the average percentage gap in log- bog-likelhhod scores, computed as:
N
(CC [CC
CCD
avg. % gap
X 100
N
where L denotes the log-likelihood score of the oracle before conditioning, and CC denotes the score after conditioning for instance i. Thus, negative values indicate that conditioning improves solution quality, while positive values indicate a decline in performance. The x-axis represents number of conditioning decisions, and each subfigure corresponds to distinct oracle time budget.
As shown in the figures, our neural network-based strategies, 1.2C-OPT and I.2C-RANK, consistently improve the oracle performance after conditioning, as evidenced by negative percentage gaps. In contrast, the graph-based heuristic and the full strong branching heuristic lead to improvements in only a small fraction of instances. Since these baselines do not produce optimal decisions, their performance generally worsens with increasing oracle time budgets, resulting in larger positive average gaps. This degradation becomes more pronounced as the number of conditioning decisions increases. In comparison, our approaches yield increasingly negative average gaps with more decisions, indicating consistent performance gains.
23

---

LpC-Opt
L2C-Rank
Graph
Strong Branching
Timellmit 10 sec
Timelimit 30 sec
Timelimit 60 sec
20
15
Average %
-5
-10
5%
10%
15%
25%
5%
10%
1.5%
25%
5%
10%
15%
25%
Figure 5: Average percentage gap on the BN 12 network for greedy conditioning using our methods, L2C-OPT and L2C-RANK, and baseline approaches across varying time budgets and numbers of decisions. More negative values indicate better performance.
L2C-Opt
Graph
Strong Branching
Timelimit
Timelimit 30
Timelimit
15
10
Average %
49
25%
15%
Decisions Taken
Decisions Taken
Decisions Taken
Figure 6: Average percentage gap on the BN 9 network for greedy conditioning using our methods, L2C-OPT and L2C-RANK and baseline approaches across varying time budgets and numbers of decisions. More negative values indicate better performance.
24

---

L2C-Opt
L2C-Rank
Graph
Strong Branching
Timelimit sec
Timelimit sec
Timelimit sec
8
Gap
6
2
15%
Decisions Taken
Decisions Taken
Decisions Taken
Figure 7: Average percentage gap on the BN 13 network for greedy conditioning using our methods, L,C-OPT and I.2C-RANK, and baseline approaches across varying time budgets and numbers of decisions. More negative values indicate better performance.
L2C-Opt
L2C-Rank
Graph
Strong Branching
Timelimit
Timelimit
Average Gap
10
0-
Decisions Taken
Decisions
Taken
Decisions Taken
Figure 8: Average percentage gap on the Grid 20 network for greedy conditioning using our methods, L2C-OPT and L2C-RANK, and baseline approaches across varying time budgets and numbers of decisions. More negative values indicate better performance.
25

---

L2C-Opt
L2C-Rank
Graph
Strong Branching
Timelimit 10 sec
Timelimit 30 sec
Timelimit 60 sec
Gap
72
-10
25%
5%
255%
1.5%
25%
Decisions Taken
Decisions Taken
Decisions Taken
Figure Average percentage gap on the BN 65 network for greedy conditioning using our methods, L2C-OPT and L2C-RANK, and baseline approaches across varying time budgets and numbers of decisions, More negative values indicate better performance.
L2C-Opt
L2C-Rank
Graph
Strong Branching
Timelimit 10 sec
Timelimit 30 sec
Timelimit 60 sec
Average Gap
40
41
-20
5%
10%
25%
5%
1.0%
2.5%
155
25%
Decisions Taken
Decisions Taken
Decisions Taken
Figure 10: Average percentage gap on the BN 59 network for greedy conditioning using our methods, L2C-OPT and L2C-RANK and baseline approaches across varying time budgets and numbers of decisions, More negative values indicate better performance.
26

---

L2
L2C-Rank
Graph
Strong Branching
Timelimit 10 sec
Timelimit 30 sec
Timelimit 60 sec
50
Gap
10
11
5%
25%
5%
255%
1.5%
25%
Decisions Taken
Decisions Taken
Decisions Taken
Figure Average percentage gap on the BN network for greedy conditioning using our methods, L2C-OPT and L2C-RANK, and baseline approaches across varying time budgets and numbers of decisions, More negative values indicate better performance.
L2C-Opt
L2C-Rank
Graph
Strong Branching
Timelimit 10 sec
Timelimit 30 sec
Timelimit 60 sec
100
Average Gap
60
40
20
5%
10%
25%
5%
100
235%
155
25%
Decisions Taken
Decisions Taken
Decisions Taken
Figure 12: Average percentage gap on the BN 49 network for greedy conditioning using our methods, L2C-OPT and L2C-RANK and baseline approaches across varying time budgets and numbers of decisions, More negative values indicate better performance.
27

---

L2C-Opt
L2C-Rank
Graph
Strong Branching
Timelimit 10 sec
Timelimit 30 sec
Timelimit 60 sec
120
100
Average %
20
41
3
1
5%
10%
15%
25%
5%
100%
1.5%
25%
5%
10%
15%
25%
Decisions
Figure 13: Average percentage gap on the BN network for greedy conditioning using our methods, L2C-OPT and L2C-RANK, and baseline approaches across varying time budgets and numbers of decisions. More negative values indicate better performance.
L2C-Opt
Graph
Strong Branching
Timelimit
Timelimit
Timelimit
80
70
60
50
Average %
30
20
10
10%
25%
10%
15%
Decisions Taken
Decisions Taken
Decisions Taken
Figure 14: Average percentage gap on the BN 45 network for greedy conditioning using our methods, L2C-OPT and L2C-RAN RANK, and baseline approaches across varying time budgets and numbers of decisions. More negative values indicate better performance.
28

---

L2C-Opt
L2C-Rank
Graph
Strong Branching
Timelimit -1 sec
Timelimit 30 sec
Timelimit sec
14
12
Average Gap
10
4-
2-
15%
Decisions Taken
Decisions Taken
Decisions Taken
Figure 15: Average percentage gap on the Promedas 68 network for greedy conditioning using our methods, L2C-OPT and L2C-RANK, and baseline approaches across varying time budgets and numbers of decisions. More negative values indicate better performance.
L2C-Opt
L2C-Rank
Graph
Strong Branching
Timelimit
Timelimit
20
Average % Gap
15
10
Decisions Taken
Decisions Taken
Decisions Taken
Figure 16: Average percentage gap on the Promedas 60 network for greedy conditioning using our methods, L2C-OPT and LAC-RANK. and baseline approaches across varying time budgets and numbers of decisions. More negative values indicate better performance.
29

---

L2C-0pt
L2C-Rank
Graph
Timelimit 10 sec
Timelimit 30 sec
Timelimit 60 sec
-10
20
Average Gap
400
-50
-60
-80
25%
25%%
1.5%
25%
Decisions Taken
Decisions Taken
Decisions Taken
Figure Average percentage gap on the BN 30 network for greedy conditioning using our methods, L2C-OPT and L2C-RANK, and baseline approaches across varying time budgets and numbers of decisions, More negative values indicate better performance.
L2C-Opt
L2C-Rank
Graph
Timelimit 10 sec
Timelimit 30 sec
Timelimit 60 sec
Average Gap
-20
-60
5%
10%
25%
5%
100
235%
1.5%
25%
Decisions Taken
Decisions Taken
Decisions Taken
Figure 18: Average percentage gap on the BN 32 network for greedy conditioning using our methods, L2C-OPT and 12C-RANK and baseline approaches across varying time budgets and numbers of decisions, More negative values indicate better performance.
30

---

E
Conditioning performance for beam search-based conditioning
E.1
Using SCIP oracle
We now present detailed results comparing the performance of various conditioning strategies when used in beam search, using the SCIP solver the oracle. Each bar represents the average log- oeelikklihood gap (computed using equation D before and after conditioning, aggregated over conditioning depths of 5%, 10%, 15%, and 25% of the query variables, and averaged across all MPE queries solved using the oracle. Each subfigure corresponds to specific oracle time budget.
Our neural strategies, L2C-OPT and L2C-RANK, consistently outperform the full strong branching heuristic in improving oracle performance, as evidenced by the negative average percentage gap. As the beam width increases, the performance of methods either improves remains consistent. In contrast, the strong branching heuristic often fails to return a decision within the 30-second time limit on larger networks and wider beams. As a result, the corresponding bars omitted in the plots.
We omit results for the graph-based heuristic, as only supports a beam width of and is therefore not applicable in this setting.
L2C-Opt
L2C-Rank
Strong Branching
Timelimit 10 sec
Timelimit 30
Timelimit 60
15.0
12.5
10.0
Average % Gap
7.5
5.0
2.5
0.0
-2.5
-5.0
Beam Width
Beam Width
Beam Width
Figure 19: Average percentage gap on the BN 12 network comparing our methods baseline approaches across varying time budgets and beam widths using beam-search based conditioning. More negative values indicate better performance.
31

---

Lt
L2C-Rank
Strong Branching
Timelimit 10 sec
Timelimit 30 sec
Timelimit = 60 sec
10
Average % Gap
6
4
0
-2
5
Beam Width
Beam Width
Beam Width
Figure 20: Average percentage gap on the BN network comparing our methods to baseline approaches across varying time budgets and beam widths using beam-search based conditioning. More negative values indicate better performance.
L2C-Opt
L2C-Rank
Strong Branching
Timelimit 10 sec
Timelimit 30 sec
Timelimit = 60 sec
10
8
Average % Gap
6
4
2
5
Beam Width
Beam Width
Beam Width
Figure 21: Average percentage gap on the BN 13 network comparing our methods baseline approaches across varying time budgets and beam widths using beam-search based conditioning. More negative values indicate better performance.
32

---

L2C-Opt
L2C-Rank
Strong Branching
Timelimit 10
Timelimit 30
Timelimit
Average % Gap
10
3
1
5
1
Beam Width
Beam Width
Beam Width
Figure 22: Average percentage gap the Grid 20 network comparing our methods to baseline approaches across varying time budgets and beam widths using beam-search based conditioning. More negative values indicate better performance. Missing bars for strong branching indicate timeouts.
L2C-Opt
L2C-Rank
Strong Branching
Timelimit 10 sec
Timelimit 30 sec
Timelimit sec
100
80
Average % Gap
60
40
20
0
Beam Width
Beam Width
Beam Width
Figure 23: Average percentage gap on the BN 65 network comparing our methods to baseline approaches across varying time budgets and beam widths using beam-search based conditioning. More negative values indicate better performance. Missing bars for strong branching indicate timeouts.
33

---

L2C-Opt
L2C-Rank
Strong Branching
Timelimit 10 sec
Timelimit 30 sec
Timelimit
60
Average % Gap
40
20
3
1
5
1
Beam Width
Beam Width
Beam Width
Figure 24: Average percentage gap the BN 59 network comparing methods to baseline approaches across varying time budgets and beam widths using beam-search based conditioning. More negative values indicate better performance. Missing bars for strong branching indicate timeouts.
L2C-Opt
L2C-Rank
Strong Branching
Timelimit 10 sec
Timelimit 30 sec
Timelimit = 60 sec
40
30
Average % Gap
10
-10
5
Beam Width
Beam Width
Beam Width
Figure 25: Average percentage gap on the BN 53 network comparing our methods baseline approaches across varying time budgets and beam widths using beam-search based conditioning. More negative values indicate better performance. Missing bars for strong branching indicate timeouts.
34

---

L2C-Opt
L2C-Rank
Strong Branching
Timelimit 10 sec
Timelimit 30 sec
Timelimit sec
100
80
Average % Gap
60
40
Beam Width
Beam Width
Beam Width
Figure 26: Average percentage gap on the BN 49 network comparing our methods baseline approaches across varying time budgets and beam widths using beam-search based conditioning. More negative values indicate better performance. Missing bars for strong branching indicate timeouts.
L2C-Opt
L2C-Rank
Strong Branching
Timelimit
10 sec
Timelimit 30
Timelimit
100
80
Average % Gap
60
20
0
Beam Width
Beam Width
Beam Width
Figure 27: Average percentage gap on the BN 61 network comparing methods to baseline approaches across varying time budgets and beam widths using beam-search based conditioning. More negative values indicate better performance. Missing bars for strong branching indicate timeouts.
35

---

L2C-Opt
L2C-Rank
Strong Branching
Timelimit 10 sec
Timelimit 30 sec
Timelimit 60 sec
40
30
Average % Gap
20
10
3 Beam Width
1
3
5
1
5
Beam Width
Beam Width
Figure 28: Average percentage gap on the BN 45 network comparing our methods to baseline approaches across varying time budgets and beam widths using beam-search based conditioning. More negative values indicate better performance. Missing bars for strong branching indicate timeouts.
L2C-Opt
L2C-Rank
Strong Branching
Timelimit 10 sec
Timelimit 30 sec
Timelimit 60 sec
14
10
Average % Gap
3
1
3
5
1
5
Beam Width
Beam Width
Beam Width
Figure 29: Average percentage gap on the Promedas 68 network comparing our methods to baseline approaches across varying time budgets and beam widths using beam-search based conditioning. More negative values indicate better performance. Missing bars for strong branching indicate timeouts.
36

---

Lt
L2C-Rank
Strong Branching
Timelimit sec
Timelimit 30 sec
Timelimit 60 sec
17.5
15.0
Average % Gap
12.5
10.0
7.5
5.0
2.5
0.0
3
3
Width
Beam Width
Beam Width
Figure 30: Average percentage gap the Promedas 60 network comparing our methods to baseline approaches across varying time budgets and beam widths using beam-search based conditioning. More negative values indicate better performance. Missing bars for strong branching indicate timeouts.
L2C-Opt
L2C-Rank
Timelimit sec
Timelimit 30 sec
Timelimit sec
-10
Average % Gap
20
-30
-40
-50
5
5
Beam Width
Beam Width
Beam Width
Figure 31: Average percentage gap on the BN 30 network comparing our methods to baseline approaches across varying time budgets and beam widths using beam-search based conditioning. More negative values indicate better performance. Missing bars for strong branching indicate timeouts.
37

---

L2C-Opt L2C-Rank
Timelimit sec
Timelimit 30 sec
Timelimit sec
Average % Gap
33
44
-50
70
5
Beam Width
Beam Width
Beam Width
Figure 32: Average percentage gap the BN 32 network comparing methods to baseline approaches across varying time budgets and beam widths using beam-search based conditioning. More negative values indicate better performance. Missing bars for strong branching indicate timeouts.
38

---

E.2 Using AOBB as oracle
In this section, we evaluate the performance of beam search- based conditioning with AOBB (per Otten and Dechter [24] and implemented by Otten [3]) as the oracle, using beam widths of 3 and 5, as shown in Figures and 34 respectively. Each figure plots the average solution gap against the percentage reduction in the number of search nodes across 1,000 MPE queries over all networks, with each point representing one network. The solution gap is computed using Equation [] while node reduction is calculated using the same formula with log-likelihood scores replaced by node counts before and after conditioning.
Our methods, L2C-OPT and L2C-RANK, consistently yield lower solution gapsindicating better preservation of optimal solutionsand higher node reductions, reflecting improved search efficiency. In contrast, the full strong branching heuristic frequently fails to preserve solution quality, as indicated by its larger gaps, and produces fewer data points due to timeouts exceeding the 30-second limit per decision.
As before, omit results for the graph-based heuristic, as it supports only beam width of and is therefore not applicable in this setting.
L2C-Opt
L2C-Rank
Strong Branching
Depth:
Depth 10%
Depth
Dapth 25%
Figure 33: Beam search-based based conditioning with AOBB as the oracle using a beam width of 3. Each subfigure corresponds to fixed number of conditioning decisions. The x-axis indicates the average solution gap (lower is better), and the y-axis indicates the percentage reduction node count (higher is better). Each point represents a single network.
Opt
L2C-Rank
Strong Branching
Depth- 5%
Depth - 109
Depth - 15%
Dupth - 25%
Aug 34. Gap
Avg 9o Gup
Avg 54 Gap
Avg Gop
Figure 34: Beam search-based conditioning with AOBB as the oracle using a beam width 5. Each subfigure corresponds to fixed number of conditioning decisions. The x-axis indicates the average solution gap (lower is better), and the y-axis indicates the percentage reduction in node count (higher better). Each point represents a single network.
F Incorporating L2C scores as branching and node selection heuristics in branch-and-bound
In this section, we compare our trained neural networksused as branching rules 32 and node
We evaluate performance based on the average percentage gap in log-likelihood (LL.) scores between our methods, 1.2C-OPT and L-CC-RAN, and SCIPs default strategies on the same set of MPE queries. The gap is computed as:
selection heuristics (34 within the SCIP frameworkwith SCIPs default heuristics 23
49 50
39

---

N N
1
LLS LCN LC
100
(2)
where LCS) denotes the log-likelihood score achieved by SCIP's default heuristics, and CCN denotes the score obtained using our I.2C methods on the i-th instance. Negative values indicate that methods perform better; positive values indicate superior performance by SCIPs default heuristics.
As shown in Figures 35 to 48 the percentage gap is typically negative, demonstrating that our methods consistently yield higher log-likelihood scores than SCIP within the same time budget. This indicates that for constrontt settings, L2C-OPT and L2C-RANK can find higher-quality solutions more efficiently than SCIPs default branching and node selection strategies. Overall, our learned heuristics not only produce better decisions but also execute faster than the state-of-the-.. methods implemented in SCIP.
L2C-Opt
L2C-Rank
Average % Gap
-3
10
30
60
Time Budget in seconds
Figure 35: Comparison of SCIPs default heuristics with our neural strategies, L2C-OPT and L2C- RANK, for branching and node selection within the SCIP framework on the BN 12 network in terms of average % gap log-liielioood. More negative values indicate better performance.
40

---

L2C-Opt
L2C-Rank
0.0
002
0.4
Average % Gap
-0.6
-1.0
-1.2
-1.6
10
30
60
Time Budget seconds
Figure 36: Comparison of SCIPs default heuristics with neural strategies, L2C-OPP and L2C- RANK, for branching and node selection within the SCIP framework on the BN 9 network in terms of average % gap fog-likelihood. More negative values indicate better performance.
L2C-Opt
L2C-Rank
0.0
-0.5
Average % Gap
-1.0
-2.0
-2.5
10
30
60
Time Budget in seconds
Comparison of SCIPs default heuristics with neural strategies, L2C-OPP OPT and L2C- RANK, for branching and node selection within the SCIP framework on the BN 13 network in terms of average % gap in logeliiel More negative values indicate better performance.
Figure 37:
41

---

L2C-Opt L2C-Rank
Average % Gap
-0.2
-0.4
-0.6
-0.8
-1.0
10
30
60
Time Budget in seconds
Figure 38: Comparison of SCIPs default heuristics with neural strategies, L2C-OPT and L2C- RANK, for branching and node selection within the SCIP framework on the Grid 20 network in terms of average % gap in nog-likelihood. More negative values indicate better performance.
L2C-Opt
L2C-Rank
0
Average % Gap
-4
-6
-10
10
30
60
Time Budget in seconds
Comparison of SCIPs default heuristics with our neural strategies, L2C-OPT and L2C- RANK. for branching and node selection within the SCIP framework the BN 65 network in terms of average % gap logeliiid More negative values indicate better performance.
Figure 39:
42

---

L2C-Opt
L2C-Rank
0
-2
Average % Gap
-6
-8
-10
-12
-14
10
30
60
Time Budget in seconds
Figure 40: Comparison of SCIPs default heuristics with our neural strategies, L.2C-OPT and L2C- RANK, for branching and node selection within the SCIP framework the BN 59 network in terms of average % gap log-likelihood. More negative values indicate better performance.
L2C-Opt
L2C-Rank
0
-2
Average % Gap
-4
-6
-8
-10
-12
-14
10
60
Time Budget in seconds
Figure 41: Comparison of SCIPs default heuristics with our neural strategies, L2C- OPT and L2C- RANK, for branching and node selection within the SCIP framework the BN 53 network in terms of average % gap lieeeiod. More negative values indicate better performance.
43

---

L2C-Opt L2C-Rank
0
-2
Average % Gap
-4
-6
8
-10
10
30
60
Time Budget in seconds
Figure 42: Comparison of SCIPs default heuristics with neural strategies, L.2COPP and L2C- RANK, for branching and node selection within the SCIP framework on the BN 49 network in terms of average % gap log-likelihood More negative values indicate better performance.
L2C-Opt
L2C-Rank
Average % Gap
-2
-4
10
30
Time Budget in seconds
Figure 43: Comparison of SCIPs default heuristics with our neural strategies, L2C-OPT and L2C- RANK, for branching and node selection within the SCIP framework the BN 61 network in terms of average % gap in log-likelioood. More negative values indicate better performance.
44

---

Op L2C-Rank
Average % Gap
-4
10
30
Time Budget in seconds
Comparison of SCIPs default heuristics with our neural strategies, 1.2C OPT and 1,2C- RANK, for branching and node selection within the SCIP framework the BN 45 network in terms of average % gap in log- fog-likelihood. More negative values indicate better performance.
Figure 44:
L2C-Opt
L2C-Rank
0.10
0.05
Average % Gap
0.00
-0.05
00.1
0.15
-0.20
10
30
60
Time Budget in seconds
Comparison of SCIPs default heuristics with our neural strategies, L2C-OPT and L2C- RANK. for branching and node selection within the SCIP framework on the Promedas 68 network in terms of average % gap log-likelihood. More negative values indicate better performance.
Figure 45:
45

---

L2C-Opt
L2C-Rank
0.2
0.1
0.0
Average % Gap
0.1
-0.2
-03
0.4
00.5
-0.6
10
30
60
Time Budget in seconds
Figure 46: Comparison of SCIPs default heuristics with our neural strategies, L2C-OPT and L2C- RANK, for branching and node selection within the SCIP framework on the Promedas 60 network in terms of average % gap in log-likelihood. More negative values indicate better performance.
L2C-Opt
L2C-Rank
Average % Gap
-2
-5
10
30
Time Budget in seconds
Figure 47: Comparison of SCIPs default heuristics with our neural strategies, L2C-OPT and L2C- RANK, for branching and node selection within the SCIP framework the BN 30 network in terms of average % gap in log- likeliood.. More negative values indicate better performance.
46

---

L2C-Opt
L2C-Rank
30
25
Average % Gap
20
15
5
0
10
30
60
Time Budget in seconds
Figure 48: Comparison of SCIPs default heuristics with our neural strategies, L2C-OPT and L2C- RANK, for branching and node selection within the SCIP framework on the BN 32 network in terms of average % gap in log- wiggliikeihood.. More negative values indicate better performance.
47


Reviews:
[{"review_id": "liOPQxeNof", "reviewer": "Reviewer_992G", "summary": "This work aims to scale the MPE inference by using a neural network-based conditioning algorithm. It includes first constructing the learning data by collecting subset variable assignments along with the computational costs. Then it uses these data to train a neural network that predicts 1) the likelihood of variable assignments being part of the MPE solution and 2) how efficient the candidate assignments are. At inference time, these scores are combined to select conditioning assignments. Experimental results on some PGMs are presented along with a comparison with a graph-based heuristic baseline and a full strong branching heuristic baseline.", "questions": "In addition to those raised in [Strengths And Weaknesses]:\n- How well does the learned heuristic perform for out-of-distribution data?\n- Many hyperparameters are involved: sampling parameter in the data collection process, the weights in the loss function, size of the conditioning set, etc. How are these hyperparameters chose,n and how sensitive is the performance to these hyperparameters?", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "The problem of choosing a subset to condition as a way to speed up MPE inference on PGMs is important and challenging. The learning based approach in this work is novel to me. This paper is overall well written, with a thorough discussion on previous work, proposed methods clearly elaborated, and sufficient background for the readers to understand this work. Still, I have a few concerns:\n- It is unclear to me how the PGMs in the data collection process are generated. It seems to me that the learned heuristic only works well when the PGM at inference is similar to those in the data collection process; for example, if the PGMs for training data have relatively low treewidth and the PGM at inference time has high treewidth, very likely the learned heuristic won't perform well since this is out of distribution data.\n- The other thing unclear to me is how flexible the learned heuristics are. Can it be applied to various cases when the sizes of the conditioning sets are different, or does it require retraining for each case?\n- I think this work will benefit from having some toy example where the optimal MPE solution is known, and comparing how accurate the predictions from the learned heuristics are.", "was_revised": true, "final_justification": "The authors have addressed my concerns. Thus I keep my positive score.", "rebuttal": "We thank Reviewer 992G for their thoughtful and constructive feedback. Below, we address each comment individually.\n\n## Comment 1\n\n> It is unclear to me how the PGMs in the data collection process are generated. It seems to me that the learned heuristic only works well when the PGM at inference is similar to those in the data collection process; for example, if the PGMs for training data have relatively low treewidth and the PGM at inference time has high treewidth, very likely the learned heuristic won't perform well since this is out of distribution data.\n\n### Response\n\nAll PGMs in the paper are sourced from the UAI 2022 benchmark and not synthetically generated. For each PGM, we train a dedicated learned heuristic using queries specific to that graph. At test time, this heuristic is evaluated on unseen queries from the same PGM. This setup assumes the **PGM structure and parameters remain fixed**, aligning with practical scenarios where inference is repeatedly performed on a known model. Think of the neural network as a MPE compiler: it helps you solve any MPE task over a given generative model more accurately and in less time.\n\nWe agree that applying a learned heuristic trained on one PGM to another with significantly different structure is unlikely to generalize. This is by design: our method targets the model-specific query inference setting, where the space of possible queries (variable subsets and evidence configurations) is combinatorially large, even for a single PGM. \n\nGeneral-purpose heuristics (e.g., graph-based) lack this model-specific specialization, which often leads to suboptimal performance, as demonstrated in our experimental results (Sec. 4.3). In contrast, our learned heuristic captures query-specific patterns for a given PGM, enabling substantially improved performance on unseen queries from the same model.\n\nWe will highlight these details in the experimental section to ensure the setup and assumptions are clearly stated.\n\n## Comment 2\n\n> The other thing unclear to me is how flexible the learned heuristics are. Can it be applied to various cases when the sizes of the conditioning sets are different, or does it require retraining for each case?\n\n### Response\n\nOur model is inherently flexible to varying conditioning set sizes. During inference, conditioning on a variable reduces the query set size by one and increases the evidence set size by one. Consequently, even within a single query, the heuristic must operate across a range of evidence sizes.\n\nThe data collection process accounts for this variability. As shown in Algorithm 1 (last two for-loops), we generate training data over diverse evidence sizes, enabling the heuristic to generalize across different conditioning set sizes. Therefore, **we do not retrain the model for each conditioning size**. A single neural heuristic is trained per PGM for L2C.\n\nIn Sec. 4.3.1, we report results for four conditioning set sizes: 5\\%, 10\\%, 15\\%, and 25\\% of variables. Importantly, **a single neural heuristic** handles scoring across all sizes, ranging from 1 up to the number of variables corresponding to these percentages. Our method consistently outperforms baselines by a significant margin across all settings.\n\nFurther, as demonstrated in Sec. 4.3.2, the trained heuristic integrates directly into the branch-and-bound solver as both a branching and node selection strategy. It operates effectively across search tree levels where partial evidence of varying sizes is encountered.\n\n\n## Comment 3\n\n> I think this work will benefit from having some toy example where the optimal MPE solution is known, and comparing how accurate the predictions from the learned heuristics are.\n\n### Response\n\nThank you for your thoughtful comment. We completely agree that comparing against true solutions is essential for a thorough evaluation. In fact, this analysis is **already included in the paper**.\n\nAs described in Sec. 4.3.1 (“*Assisting AOBB via conditioning*”) and detailed further in the supplemental material, we use **AOBB as an oracle** to obtain exact MPE solutions.\n \nIn these experiments, we run AOBB to completion—without time limits—to obtain the **optimal MPE solution** for each instance (see Footnote 2). This ensures that the unconditioned AOBB results serve as the ground truth for optimality.\n\nTo assess the accuracy of the learned heuristic, we report the *Avg \\% Gap* between the MPE value obtained by the conditioned solver and the optimal unconditioned solution (see Fig. 3). A smaller gap indicates a solution closer to the true optimum. Our method consistently achieves low gap values, outperforming baseline heuristics across multiple conditioning sizes.\n\nThis evaluation effectively demonstrates that the learned heuristic yields **near-optimal solutions** while substantially reducing **computational effort**, as measured by the **number of nodes explored** (see y-axis).\n\n## Comment 4\n\n> How well does the learned heuristic perform for out-of-distribution data?\n\n### Response\n\nWe acknowledge the importance of evaluating the learned heuristic on out-of-distribution PGMs. While this work focuses on the fixed-PGM setting, investigating **transferability to unseen but structurally similar PGMs** (e.g., larger Ising models or models with the same graph structure but different parameters) is a promising direction with practical relevance.\n\nSuch generalization would require modifications to the architecture, embeddings, and training procedure to capture transferable patterns across related PGMs. We leave this as future work.\n\nThat said, transferring heuristics across **unrelated PGMs** is inherently challenging. Each PGM defines a distinct distribution over a different variable set and structure, making it unlikely that a heuristic trained on one model would generalize well to another without significant adaptation.\n\n\n## Comment 5\n\n> Many hyperparameters are involved: sampling parameter in the data collection process, the weights in the loss function, size of the conditioning set, etc. How are these hyperparameters chosen and how sensitive is the performance to these hyperparameters?\n\nThe **sampling parameter** in the data collection process controls the number of conditioning variables sampled per query. Larger values yield a richer dataset and higher-quality heuristics but incur greater computational cost. We set this parameter based on available computational resources.\n\nThe **loss function weights** were selected using a validation set. We performed a grid search over $\\lambda\\_{\\text{opt}} \\in \\\\{0.3, 0.35, 0.4, 0.45, 0.5\\\\}$ with $\\lambda\\_{\\text{rank}} = 1 - \\lambda\\_{\\text{opt}}$.\n\nThe **conditioning set size** represents a trade-off between solution quality and computational efficiency. Larger conditioning sets simplify the remaining inference problem, often improving runtime, but can reduce solution quality. We evaluated sizes from 5\\% to 25\\% of the total variables to cover this trade-off space. As expected, increasing the conditioning size generally improves efficiency but may slightly degrade optimality.\n\nWe include experiments with these varying conditioning set sizes to reflect scenarios where inference must be performed under **strict time constraints**, such as in neurosymbolic systems requiring real-time responses. In these cases, conditioning enables faster convergence to high-quality solutions.\n\nAs shown in the SCIP experiments (Sec. 4.3.1), unconditioned inference often fails to reach optimality within the time budget, whereas increasing the conditioning set size yields better log-likelihood (LL) values. This illustrates a **practical trade-off**: although larger conditioning sets may slightly reduce optimality in some cases, they allow the solver to find **better approximate solutions within limited time**."}, {"review_id": "AV8nJcN8NP", "reviewer": "Reviewer_CV4Q", "summary": "The paper presents a new data-driven framework called Learning to Condition (L2C) for tackling the Most Probable Explanation (MPE) inference problem in probabilistic graphical models. The MPE task in graphical models is known to be computationally intractable. Specifically, the proposed L2C method trains a neural network to score variable-value assignments based on their utility for conditioning. Essentially, L2C can generate cutset conditioning sets that once instantiated are likely to yield a much simplified MPE instance that can be solved efficiently by existing MPE solvers. In addition, the L2C approach can be used as bot variable ordering as well as value ordering heuristics for specialised search-based solvers for MPE such as MIP solvers or AND/OR search based solvers. The experimental evaluation is carried out on standard graphical models benchmarks. The results demonstrate the benefits of the proposed method.", "questions": "- Regarding transferability, it would be interesting to train L2C on a given distribution (e.g., such as the one derived from the BN/Grid instances) and experiment with problem instances from a different distribution such as the pedigree or protein networks from the UAI Challenge Benchmark. What would be the performance gap in that case?\n\n- L2C looks very similar to the learning to branch approaches developed recently for mixed integer programming (see ref [31]). What is the conceptual difference between the two approaches?", "limitations": "The proposed L2C method appears to be limited to binary variables.", "rating": 2, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths\n---------\n\nThe MPE (or MAP) inference task in graphical models is a fundamental yet very difficult task with a wide range of real-world applications. Therefore, developing new methods to solving it more efficiently in practice is definitely called for.\n\nThe paper is fairly well written and organised. Therefore, the content is relatively easy to follow. The quality of the presentation is overall quite good.\n\nThe empirical evaluation, although fairly limited, is sound and the results are presented in a clear manner which makes it relatively easy for the reader to appreciate the benefits of the proposed method.\n\n\nWeaknesses\n----------\n\nThe empirical evaluation appears to be limited to a few classes of problems from the UAI Inference Challenge Benchmark (the BN and Grid instance are actually random instances) and the training dataset seems to be generated from the same distribution. Therefore, the performance gains highlighted in the experiments aren't actually surprising. The problem instances shown in Figure 2, although they have relatively high tree widths, are actually fairly easy for exact MPE/MAP inference.\n\nState of the art branch and bound algorithms for MPE/MAP exploit both variable as well as value ordering heuristics. Value ordering heuristics make a huge difference in the case of non-binary domains. However, the benchmarks considered in the experiments (as well as the presentation of the L2C methodology) only considers the case of binary variables.\n\nThe experimental evaluation ignores two classes of MPE algorithms: the local search MPE algorithms by Hutter et al, IJCAI-2005 and the exact soft arc-consistency based search algorithms from the toolbar2 suite. The latter use dynamic variable and value ordering heuristics and L2C would be more relevant for them instead of AOBB. The AOBB version considered in this paper, although quite powerful, is limited to a static variable ordering given by the pseudo-tree. \n\nFinally, the MIP formulation for MPE/MAP is known to be not very effective. MIP solvers are typically outperformed by dedicated solvers such as as toolbar and AOBB.", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer CV4Q for their valuable comments and suggestions.\n\n>1.1 The evaluation uses only a few random BN and Grid instances from the UAI benchmark.\n\nWe selected the BN and Grid instances to introduce structural diversity across different PGMs. In addition, we evaluated our approach on the Promedas class, which contains real-world networks with varying complexity.\n\nThis selection aligns with prior work on MPE inference over PGMs \\[1,2\\], which also used models from the UAI Inference Challenge. The benchmark offers PGMs with diverse treewidths, variable counts, and factor sizes, allowing us to demonstrate that our learned heuristics are **scalable and effective across structurally varied models**.\n\n> 1.2 The training and test data share the same distribution, so the performance gains are unsurprising.\n\nThe training and test queries are sampled from the same PGM; however, the model must still generalize over a combinatorially large space of queries, each inducing a distinct inference subproblem.\n\nGeneral-purpose heuristics (e.g., graph-based) are not tailored to specific PGMs and thus often underperform. In contrast, our neural heuristic learns **model-specific structural and parametric patterns**, enabling improved performance across diverse queries, as demonstrated in our experiments.\n\nWhile this work focuses on the fixed-PGM setting, extending it to support transfer across structurally similar PGMs (e.g., larger Ising models or parameter variations) is an important direction for future work. This would require changes to the model architecture, input representations, and training procedure to capture transferable patterns. This will be the holy-grail, yielding a universally transferable MPE engine that works across model families. If we solve this, we will have achieved an chatgpt‑like breakthrough for optimization, a task that is anything but easy. We like your thought process; you are clearly thinking what the overarching goal should look like.\n\nOur setup is consistent with recent work on neural inference in PGMs \\[1\\], where a separate network is trained per model to learn its specific structure. In contrast, general-purpose learned heuristics require substantially more data, computational resources, and model capacity, often resulting in degraded performance. Our objective is to develop **PGM-specific neural heuristics** that consistently outperform generic methods in both accuracy and efficiency.\n\n>1.3 The instances in Figure 2 have high treewidth but are easy for exact MPE/MAP inference.\n\nOur method is best viewed as a **neural conditioning strategy that assists MPE solvers**, rather than an MPE solver itself. The goal is to improve solution quality and efficiency under resource constraints, across different PGMs.\n\nIn Sec. 4.3.1, we evaluate under a fixed time budget, simulating real-time inference. As Fig. 2a–b show, conditioning yields better solutions within the same limit. Even at 60 seconds, it outperforms the unconditioned solver, highlighting the challenge of exact inference under time constraints.\n\nFurthermore, when exact solutions are obtainable (Fig. 3), our learned heuristic significantly reduces the number of nodes explored while producing near-optimal results. This leads to faster inference and improved solver efficiency.\n\n>2 State-of-the-art BnB algorithms use variable and value ordering, but the experiments and L2C method only address binary variables, missing the impact of value ordering in non-binary cases.\n\nOur approach incorporates both **variable and value ordering** heuristics. Specifically, the model outputs **optimality and ranking scores for variable–value pairs**, not just variables. During training, we initialize separate learnable embeddings for each variable and each of its possible values. The attention-based neural network uses these embeddings to score variable–value pairs, enabling informed decisions during inference.\n\nThe method naturally extends to **multi-valued variables**: the number of embeddings and output nodes scales with the domain size, while the rest of the architecture remains unchanged.\n\nAlthough the current benchmarks involve binary variables, the methodology is fully compatible with non-binary domains. We plan to include experiments on multi-valued PGMs in the camera ready version to demonstrate this capability.\n\n>3 The evaluation omits local search (Hutter et al., 2005) and exact arc-consistency-based methods (toolbar2), which use dynamic heuristics where L2C would be more relevant than the static-order AOBB used.\n\nWe appreciate the reviewer's suggestion to explore local search MPE algorithms and soft arc-consistency methods[3], which align well with directions for future work.\n\nThis paper focuses on branch-and-bound (B\\&B) solvers—both classical (SCIP) and structure-aware (AOBB)—as they dominate exact inference for high-treewidth models and offer natural integration points for learned variable–value scores.\n\nWe agree L2C can extend to other solver families:\n\n* **Local Search:** L2C can precondition the problem by fixing high-confidence variable–value pairs, reducing dimensionality and guiding search, though interaction tuning is required.\n\n* **Arc-Consistency [3]:** L2C's variable–value scores can enhance or replace heuristics for adaptive ordering, improving pruning efficiency.\n\nThat said, we emphasize that **local search** and **arc-consistency–based solvers** differ fundamentally from branch-and-bound solvers in both mechanism and behavior. While the current L2C-based neural heuristic can be applied to these solvers, its performance may be suboptimal.\n\nAchieving strong results in these settings would require significant changes to L2C-including new data generation, new architecture, and potentially new training objectives. We consider this as promising future work.\n\nThank you for pointing out the relevant papers and search techniques. We will include the suggested references in the revised version of the paper.\n\n>4 MIP formulations for MPE/MAP are generally ineffective and are outperformed by dedicated solvers like toolbar and AOBB.\n\nOur method is solver-agnostic and serves as a general-purpose conditioning strategy that can be integrated with any systematic solver\n\nWe use the MIP solver solely during data collection to generate training labels. This choice is not essential—any systematic search solver, such as AOBB, can be used in its place without affecting the core framework.\n\nOnce conditioned via the learned heuristic, the modified query can be solved by any MPE solver. As shown in Sec. 4.3.1, we use the same heuristics with both MIP and AOBB, isolating the effect of conditioning. This confirms the method's **solver-agnostic** nature and broad applicability\n\n>5 To assess transferability, L2C could be trained on BN/Grid instances and tested on different distributions (e.g., pedigree or protein networks) to evaluate the resulting performance gap.\n\nTransfer across PGM classes is important and part of our future work.\n\n**Intra-class transfer** (e.g., small to large Ising models) is more feasible due to shared structure but still requires changes to architecture, embeddings, and training.\n\n**Cross-class transfer** (e.g., BN to Pedigree) is harder due to differences in topology, semantics, and factors. It would need larger models, more training data, and may still degrade performance.\n\nTraditional heuristics avoid this issue by deferring computation to test time. In contrast, our training-intensive approach enables fast, model-specific inference, essential for real-time use.\n\nOur focus is on **PGM-specific neural heuristics** that outperform generic methods in accuracy and efficiency.\n\n>6 L2C closely resembles recent learning-to-branch methods for mixed integer programming (e.g., \\[31]); what is the key conceptual difference between them?\n\nWhile both guide combinatorial solvers via learning, L2C and learning-to-branch differ in key ways:\n\n* **Purpose**: Learning-to-branch selects variables during BnB search; L2C selects variables to condition on before solving, simplifying the problem.\n* **Training signal**: Branching uses imitation learning from strong branching scores; L2C uses supervised learning from solver statistics, without needing optimal traces.\n* **Generalization**: L2C is solver-agnostic—usable for conditioning, branching, or with various solvers (e.g., MIP, AOBB), as shown in Sec. 4.3.\n\nL2C is a broader framework for query-dependent conditioning, not tied to solver internals.\n\n>7 The proposed L2C method appears to be limited to binary variables.\n\nOur proposed L2C method can be easily extended to multi-valued discrete variables and, with additional modifications, to continuous variables. We provide more details below.\n\n* **Multi-valued:**\n  Training uses embeddings for variable–value pairs; the architecture and losses remain unchanged. Inference (greedy, beam, BnB) operates directly over these pairs.\n\n* **Continuous:**\n  Discretize variables (e.g., binning, quantiles). Train and infer over (variable, discretized value) pairs. Optionally refine solutions via local optimization.\n\nThese extensions retain the core L2C architecture with minimal changes.\n\n#### References\n[1]\tS. Arya, T. Rahman, and V. G. Gogate, “A neural network approach for efficiently answering most probable explanation queries in probabilistic models,” presented at the The Thirty-eighth Annual Conference on Neural Information Processing Systems, Nov. 2024.\n\n[2]\tS. Agarwal, K. Kask, A. Ihler, and R. Dechter, “NeuroBE: Escalating neural network approximations of bucket elimination”.\n    \n[3] Larrosa, J., & Schiex, T. (2003). In the quest of the best form of local consistency for weighted CSP. Proceedings of the 18th International Joint Conference on Artificial Intelligence, 239–244. Presented at the Acapulco, Mexico. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc."}, {"review_id": "H5JgzCkMo2", "reviewer": "Reviewer_D8Hg", "summary": "This paper introduces L2C, a novel neural method that accelerates MPE inference in PGMs. By learning from exact MPE solvers, L2C identifies strategic variable assignments that effectively balance problem simplification with solution optimality, enabling it to serve as both a powerful pre-processor and an intelligent heuristic within B&B algorithms. Empirical results demonstrate L2C's superior performance over traditional methods, significantly improving the efficiency and tractability of MPE problem-solving.", "questions": "See Cons. Specifically:\n\nFirst question: Is this the first application of Attention to MPE problems?\n\nSecond: How significant is the cost of data collection?\n\nThird, this is a question.\n\nFourth, this is a suggestion.\n\nFifth, this is a suggestion.", "limitations": "The authors only discuss limitations in the \"Future work\" section, specifically stating \"Future work will target L2C’s current limitations in scalability, solver signal quality, and the scope of learned guidance.\" (lines 396), which is insufficient for a comprehensive discussion of shortcomings.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "# Pros:\n\n1.The method is technically sound, features a cleverly designed training objective, and is strongly supported by comprehensive empirical results.\n\n2.L2C effectively addresses a critical challenge in MPE inference, making previously intractable problems solvable.\n\n3.The approach of learning conditioning strategies by combining deep learning with classical MPE solvers is highly novel.\n\n# Cons:\n1.If this is the first application of Attention to MPE problems, it would be very significant. However, I'd like to ask, how significant is the difference between L2C and the attention mechanisms in classical Graph Neural Networks?\n\n2.Reliance on computationally expensive 'oracle' solvers might limit its application to large-scale problems. Could we try a Bootstrap method to accelerate data collection?\n\n3.The core insight of the paper is: \"A key insight of our method is that solution ambiguity modulates conditioning risk.\" This statement is somewhat straightforward. It's quite intuitive, much like \"high risk, high reward\". Could you elaborate further?\n\n4.A more in-depth explanation of the specific information and contextual relationships captured within the learned variable-value pair embeddings would improve clarity. As I am not an expert in this field, it took me a considerable amount of time to understand the specific mechanism of the embeddings.\n\n5.The paper's discussion on L2C's applicability or extensions to other inference types or continuous variables is limited.", "was_revised": true, "final_justification": "The author answered my questions very well, but considering the differing opinions of other reviewers, and given that my own perspective might not fully encompass every nuance of this specialized field, I believe the current score is appropriate.", "rebuttal": "We thank Reviewer D8Hg for their detailed review and insightful suggestions. Below, we address each comment individually.\n\n> 1. If this is the first application of Attention to MPE problems, it would be very significant. However, I'd like to ask, how significant is the difference between L2C and the attention mechanisms in classical Graph Neural Networks?\n\nTo the best of our knowledge, this is the first application of **attention-based models** to the MPE problem in PGMs. While prior work has explored hypergraph neural networks for MPE \\[1\\], and graph attention networks (GATs) for combinatorial optimization problems such as TSP \\[2\\], these approaches differ fundamentally from ours.\n\nOur method treats variable–value pairs as learnable embeddings, allowing the multi-head attention mechanism to operate over these pairs directly. This design enables the model to capture fine-grained, context-dependent interactions between query and evidence variables in a high-dimensional space—going beyond standard GAT-style message passing over PGM graphs. In a way, our approach introduces a **novel embedding scheme** that captures information about variables and their assigned values, tailored specifically to the MPE task. \n\nThus, while our architecture incorporates attention, it is conceptually distinct from classical GNNs and tailored to the structure of the MPE inference problem.\n\n> 2. Reliance on computationally expensive 'oracle' solvers might limit its application to large-scale problems. Could we try a Bootstrap method to accelerate data collection? How significant is the cost of data collection?\n\nDuring data collection, we solve each unconditioned MPE query exactly only once. As the size of the conditioning set $C$ increases (Algorithm 1), the resulting queries become easier to solve, since fewer variables remain in the query set.\n\nWe also incorporate a method to accelerate data collection. Rather than allowing the oracle to run indefinitely after conditioning, we limit execution to 60 seconds and use the observed improvement in log-likelihood, solving time, or number of nodes as the training signal. This enables efficient generation of high-quality supervision without full exact inference.\n\nThat said, overly noisy or weak training signals can degrade the learned heuristic's effectiveness, potentially outweighing the benefit of avoiding a few exact queries. \n\n\n> 3. The core insight of the paper is: \"A key insight of our method is that solution ambiguity modulates conditioning risk.\" This statement is somewhat straightforward. It's quite intuitive, much like \"high risk, high reward\". Could you elaborate further?\n\nConditioning on an incorrect variable–value pair can prevent recovery of the true MPE solution. This risk is context-dependent: it is highest when a variable consistently takes the same value across optimal solutions, since an incorrect assignment eliminates all optimal paths. Conversely, when a variable's assignment varies across high-probability solutions, even suboptimal choices may still preserve access to near-optimal outcomes.\n\nOur model, trained on diverse solver traces, implicitly learns this trade-off. It assigns higher scores to variable–value pairs where the expected utility outweighs the risk, and lower scores when ambiguity makes early conditioning more likely to prune optimal paths. This learned behavior captures the underlying structure of solution ambiguity and its impact on conditioning risk.\n\n\n> 4. A more in-depth explanation of the specific information and contextual relationships captured within the learned variable-value pair embeddings would improve clarity. As I am not an expert in this field, it took me a considerable amount of time to understand the specific mechanism of the embeddings.\n\nThank you for pointing this out. We will clarify this in the revised version. Below is a summary of the key design choices:\n\nEach variable–value pair is encoded as a **learnable high-dimensional embedding**, rather than using separate or one-hot encodings for variables and values. This joint representation is critical, as the model must assess the plausibility of specific assignments under a fixed evidence set. Encoding variables and values independently would fail to capture their joint semantics, particularly in high-treewidth PGMs where dependencies are complex.\n\nThe **multi-head attention mechanism** then processes these variable–value pair embeddings, enabling the model to reason over their contextual relationships. Attention allows the network to model interactions conditioned on the current evidence, effectively identifying which assignments are informative for conditioning.\n\nThis design improves both the expressiveness of the model and its ability to generalize across queries, facilitating accurate and efficient inference.\n\n> 5. The paper's discussion on L2C's applicability or extensions to other inference types or continuous variables is limited.\n\nOur proposed L2C method can be easily extended to multi-valued discrete variables and, with additional modifications, to continuous variables. We provide more details below.\n\n1. **Extension to multi-valued discrete variables:**\n\n* **Data Collection:** The procedure remains unchanged. \n\n* **Training:** As in the binary case, we initialize embeddings for all variable–value pairs. Our attention-based architecture naturally supports multi-valued variables, as it outputs scores for each pair independently. The optimality and simplification heads produce per-pair scores, and the existing loss functions remain applicable without modification.\n\n* **Inference:** The same sequential inference procedures—greedy conditioning and beam search—extend directly to the multi-valued case. For branching and node selection, we can perform greedy selection over variable–value pairs at each node in the branch-and-bound search tree.\n\nL2C **naturally supports multi-valued variables** with no major changes to data, model, or inference.\n\n2. **Continuous variables:**\n\n* **Data Collection:** Discretize variables (e.g., binning, quantiles), then collect solver stats on these values. Adaptive binning improves quality.\n* **Training:** Use embeddings for (variable, discretized value) pairs. The model and losses remain unchanged; soft labels improve robustness.\n* **Inference:** Perform greedy or beam search over discretized pairs. Optionally refine with local optimization (e.g., gradient descent) from top assignments.\n\nL2C handles continuous variables via discretization with **minimal architectural changes**.\n\n> 6. The authors only discuss limitations in the \"Future work\" section, specifically stating \"Future work will target L2C’s current limitations in scalability, solver signal quality, and the scope of learned guidance.\" (lines 396), which is insufficient for a comprehensive discussion of shortcomings.\n\nWe thank the reviewer for the suggestion. While the sentence on line 396 introduces the limitations, we do provide further detail in the subsequent lines (397–401), outlining challenges related to scalability, solver signal quality, and the scope of learned guidance:\n\n> “We will adapt L2C for larger models (millions of variables and factors), necessitating efficient large-scale data collection. Richer solver signals (e.g., branch-and-cut decisions) will be integrated for more aggressive pruning, improving upon current signal usage. Finally, learned variable orderings will be explored for novel neural bounding strategies, extending guidance beyond conditioning to further boost inference performance.”\n\nThat said, we agree that this discussion remains brief. In the revised version, we will make the limitations more explicit and include them in a dedicated subsection. In particular, we will elaborate on:\n\n* **Scalability:** Data collection and training become increasingly expensive for large PGMs. Further work is needed to reduce computational cost, possibly through model compression, amortized inference, or subgraph-based training.\n\n* **Generalization:** The current method is tailored to fixed PGMs. Extending to unseen or structurally similar PGMs—e.g., via meta-learning or transfer learning—remains an open challenge.\n\n* **Solver dependence:** Training relies on solver-generated signals, which can be expensive to obtain. Although we use proxy signals via time-limited runs, minimizing dependence on oracle solvers is an important future direction.\n\nWe will include these limitations in the revised manuscript to provide a more thorough and transparent discussion.\n\nReferences:\n\n[1]\tS. Arya, T. Rahman, and V. G. Gogate, “SINE: Scalable MPE inference for probabilistic graphical models using advanced neural embeddings,” presented at the The 28th International Conference on Artificial Intelligence and Statistics, Feb. 2025.\n\n[2] Luo, J., Heng, H. and Wu, G. Graph attention, learning 2-opt algorithm for the traveling salesman problem. Complex Intell. Syst. 11, 117 (2025). https://doi.org/10.1007/s40747-024-01716-5"}, {"review_id": "aNZx62wUfA", "reviewer": "Reviewer_GK5K", "summary": "This paper introduces Learning to Condition (L2C), a neural heuristic framework for scalable Most Probable Explanation (MPE) inference in Probabilistic Graphical Models (PGMs). The core idea is to train an attention-based neural network to score variable-value assignments based on their utility for conditioning, balancing the preservation of optimal solutions with the simplification of inference. The model is supervised using a scalable data pipeline that extracts training signals from the search traces of existing MPE solvers. L2C is integrated with search algorithms, serving as a conditioning strategy before exact inference or as a branching and node selection policy within branch-and-bound solvers. Experiments on high-treewidth PGMs demonstrate that L2C significantly reduces the search space while maintaining or improving solution quality compared to state-of-the-art methods.", "questions": "- The conditioning problem resembles MAXSAT (weighted constraint optimization). How does L2C compare to state-of-the-art PB solvers (e.g., using cutting planes or conflict analysis) in efficiency?", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- Innovative Integration: Combines neural networks with symbolic reasoning, using solver-guided feedback to ensure semantic correctness of generated constraints.\n- Data Efficiency: The supervision strategy leverages solver statistics without requiring exhaustive MPE enumeration.\n- Flexible Deployment: Functions as both a pre-processing conditioning strategy and a branching heuristic within branch-and-bound solvers.\nWeaknesses:\n- Binary Limitation: Assumes all variables are binary (\"w.l.o.g.\", Sec. 2). This restricts applicability to real-valued variables, limiting generalization beyond discrete domains.\n- MAXSAT/PB Solver Comparison: Lacks direct comparison with pseudo-Boolean (PB) solvers, missing an opportunity to contextualize novelty against established methods.", "was_revised": true, "final_justification": "Thank you for your response, which clarified my questions. My concerns are resolved, so I maintain my positive score of 4.", "rebuttal": "We sincerely appreciate Reviewer GK5K's thoughtful comments and constructive feedback. Below, we provide detailed responses to each of their points.\n\n## Comment 1\n\n> Binary Limitation: Assumes all variables are binary (\"w.l.o.g.\", Sec. 2). This restricts applicability to real-valued variables, limiting generalization beyond discrete domains.\n\n### Response\nOur proposed L2C method can be easily extended to multi-valued discrete variables and, with additional modifications, to continuous variables. We provide more details below.\n\n1. **Extension to multi-valued discrete variables:**\n\n* **Data Collection:** The procedure remains unchanged. \n\n* **Training:** As in the binary case, we initialize embeddings for all variable–value pairs. Our attention-based architecture naturally supports multi-valued variables, as it outputs scores for each pair independently. The optimality and simplification heads produce per-pair scores, and the existing loss functions remain applicable without modification.\n\n* **Inference:** The same sequential inference procedures—greedy conditioning and beam search—extend directly to the multi-valued case. For branching and node selection, we can perform greedy selection over variable–value pairs at each node in the branch-and-bound search tree.\n\nThus, the current architecture extends naturally to multi-valued discrete variables without requiring significant changes to the data collection, model design, or inference procedures.\n\n2. **Extension to continuous-valued variables:**\n\n**Data Collection:**  \n* Direct application is infeasible because the L2C framework operates on variable–value pairs. For continuous domains, discretize each variable into a finite set of representative values (e.g., via uniform binning, quantiles, or problem-specific grid points).  \n* During data collection, condition on these discretized values, and collect solver statistics as in the discrete case. To collect better quality data we can employ adaptive binning—allocating more candidate values where the density or utility gradient is high.\n\n**Training:**  \n* Initialize embeddings for each (variable, discretized value) pair.   \n* The existing attention-based network and both heads (optimality, simplification) apply without architectural change. The pairwise scoring now covers an expanded set.  \n* Retain the original objective formulations. Losses apply to target discretized values for optimality and simplification. Soft-label targets can smooth transitions across adjacent bins, improving robustness to discretization artifacts.\n\n**Inference:**  \n* Apply greedy or beam search over (variable, discretized value) pairs, as in the multi-valued setting.  \n* After selecting promising variables/bins, optionally perform local continuous optimization (e.g., gradient descent, coordinate search) initialized from the best discrete assignments, to refine the solution beyond discretization resolution.  \n* Condition or branch on the discretized values;\n\n## Comment 2\n\n> MAXSAT/PB Solver Comparison: Lacks direct comparison with pseudo-Boolean (PB) solvers, missing an opportunity to contextualize novelty against established methods.\n\n### Response\n\nOur method is best viewed as a neural conditioning strategy that assists MPE solvers, rather than a standalone solver. Its goal is to improve efficiency and solution quality under resource constraints, especially in settings where exact inference is computationally expensive.\n\nAs such, comparisons to heuristic strategies—e.g., graph-based heuristics or strong branching heuristics—are more appropriate. These baselines share the same goal: guiding solvers to improve performance, rather than solving the problem end-to-end.\n\nIn Sec. 4.3.1, we evaluate under a fixed time budget, reflecting realistic scenarios such as neurosymbolic inference or time-sensitive applications. As shown in Fig. 2a and 2b, conditioning with our learned heuristic consistently leads to higher-quality solutions within the same time window. Even with generous limits (e.g., 60 seconds), unconditioned solvers often fail to reach comparable quality.\n\nAlthough pseudo-Boolean (PB) solvers and MAXSAT formulations are relevant for certain inference tasks, a direct comparison is not meaningful in our setup. MPE inference in PGMs involves probabilistic semantics, large factor graphs, and real-valued potentials, which differ fundamentally from the propositional logic and Boolean constraints typically handled by PB solvers. Integrating or benchmarking against PB solvers would require non-trivial translation of the problem and is beyond the scope of this work."}]

Author rebuttal:

Meta-review: This paper introduces Learning to Condition (L2C), a novel framework that trains a neural network to learn heuristics for accelerating Most Probable Explanation (MPE) inference. The model learns to predict high-utility variable assignments for conditioning, effectively simplifying the problem for classical solvers. The reviews were largely positive, with three of the four reviewers leaning towards acceptance after a thorough discussion period. The 4th reviewer, CV4Q, did not participate in the discussion, only thanked the authors for clarifications, without providing any final recommendations or justifications for keeping the reject score.

AC recommends acceptance due the following strengths:

* Novelty and Significance: The paper addresses a challenging and important problem in probabilistic inference with a novel learning-based approach. The integration of deep learning with classical MPE solvers is seen as a creative and impactful contribution (R-992G, R-D8Hg, R-GK5K).

* Technical Soundness: The method is technically solid, featuring a well-designed training objective and a flexible architecture that can serve as both a pre-processing step and an integrated branching heuristic for branch-and-bound solvers (R-D8Hg, R-GK5K).

* Empirical Results: The experiments, conducted on high-treewidth graphical models, convincingly demonstrate that L2C significantly reduces the search space and improves solution quality compared to strong baselines, including competitive solvers from the UAI 2022 competition (R-992G, R-D8Hg).

* Clarity and Responsiveness: The paper is well-written and easy to follow. The authors provided thorough and convincing rebuttals that successfully addressed the majority of the reviewers' concerns regarding the experimental setup, model flexibility, and out-of-distribution performance (R-992G, R-D8Hg, R-GK5K).

While there are valid points about extending the evaluation to other solver classes and non-binary domains, the core contribution is well-defined and supported. The work represents a valuable and promising step in combining neural methods with symbolic reasoning for complex inference tasks.
Decision: Accept (poster)