Branch and Bound Search for Exact MAP Inference in Credal Networks
Authors: Radu Marinescu
Fabio Cozman
Denis Mauá
Debarun Bhattacharjya
Junkyu Lee
Alexander G. Gray
Venue: ICLR 2026 Poster (2026)
Keywords: probabilistic reasoning
credal networks
search
MAP inference
Primary area: probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
TL;DR: The paper presents new branch and bound search algorithms for exact MAP inference in credal networks

Abstract: Credal networks extend Bayesian networks by incorporating imprecise probabilities through convex sets of probability distributions known as credal sets. MAP inference in credal networks, which seeks the most probable variable assignment given evidence, becomes inherently more difficult than in Bayesian networks because it involves computations over a complex joint credal set. In this paper, we introduce two tasks called \emph{maximax} and \emph{maximin} MAP, and develop depth-first branch-and-bound search algorithms for solving them \emph{exactly}. The algorithms exploit problem decomposition by exploring an AND/OR search space and use a partitioning-based heuristic function enhanced with a cost-shifting scheme to effectively guide the search. Our experimental results obtained on both random and realistic credal networks clearly demonstrate the effectiveness of the proposed algorithms as they scale to large and complex problem instances.

Published as a conference paper at ICLR 2026
BRANCH-AND-BOUND SEARCH FOR EXACT MAP INFERENCE IN CREDAL NETWORKS
Radu Marinescu
IBM Research
Dublin, Ireland
Badu.marinees ie. i.m. com
ma
Fabio Cozman & Denis Maua University of Sao Paolo
Sao Paolo, Brazil (fgcozman, deni s. maua @usp.br
Debarun Bhattacharjya Junkyu Lee
IBM Research Yorktown Heights, NY 10598, USA
debarunbeus ibm. com, junkyu Leweiim....ooooo.ee..eee.eeeooee
Alexander Gray
Centaur AI Institute
alexander gray@centaurlnatiutee.oo
ABSTRACT
Credal networks extend Bayesian networks by incorporating imprecise probabili- ties through convex sets of probability distributions known credal sets. MAP inference in credal networks, which seeks the most probable variable assignment given evidence, becomes inherently more difficult than in Bayesian networks be- cause it involves computations over a complex joint credal set. this paper, we introduce two tasks called maximax and maximin MAP, and develop depth-firs: first suunch-and-boutg search algorithms for solving them exactly. The algorithms exploit problem decomposition by exploring AND/OR search space and a partitioning- based heuristic function enhanced with a cost-shifting scheme to effectively guide the search. Our experimental results obtained both random and realistic credal networks clearly demonstrate the effectiveness of the proposed algorithms as they scale large and complex problem instances.
INTRODUCTION
Credal networks (Cozman 2000) are probabilistic graphical models that generalize Bayesian networks (Pearl 1988) by allowing imprecise probabilities. Instead precise probability mass functions, they utilize convex sets of probability distributions known as credal sets to represent the local models for network variables given their parents. This enables more flexible and robust treatment of uncertainty compared with Bayesian networks, accommodating severe uncertainty, unreliable data or conflicting information (Mauá & Cozman 2020). Credal networks are especially valuable when precise probability estimates are difficult undesirable to obtain. Moreover, credal networks obtained in partially identifiable structural causal models with non-observed latent variables, as often met in causal discovery and inference (Zaffalon al. 2020).
Over the past decades, research has primarily focused on developing marginal inference algorithms to efficiently compute the upper and lower probability bounds of query variable given evidence in credal network (Mauá & Cozman 2020) Cano et Antomucci et al.) 2010, Wijk et al.) 2022). Maximum Posteriori or MAP inference tasks for credal networks, which aim to identify

---

Published as a conference paper at ICLR 2026
the most probable value assignments to the variables given evidence, have received relatively little attention from the community. This stands in stark contrast to Bayesian network MAP, which has been extensively investigated over the years (Koller & Friedman, 2009).
MAP inference in credal networks substantially more challenging than in Bayesian networks due to computations over the joint credal set. Despite its difficulty, it remains relevant for explaining evidence, whether or not hidden variables are involved. Some recent work has proposed a variety of exact and approximate algorithms for Marginal MAP inference in credal networks, including variable elimination, exhaustive depth-first search and stochastic local search (Marinescu et al. (023). Although these methods can be trivially extended to credal MAP inference they often scale poorly, limiting applicability to small models or offering no guarantees on solution quality.
Contributions:
This paper advances recent research on MAP inference in credal networks. In particular, we focus on two MAP tasks called maximax and maximin MAP, defined as finding an assignment to the network variables that consistent with the evidence and has a maximum upper and, respectively, lower probability. We introduce new depth-first branch-and-bound search algorithms for solving these tasks exactly in practice. The methods leverage an AND/OR search space associated with the credal network, effectively exploiting the underlying problem structure during search. The proposed AND/OR search for credal networks extends the approach previously developed for Bayesian networks (Dechter & Mateescu (007). Furthermore, we enhance these algorithms with heuristic that combines potential approximations with cost-shifting strategies produce effective search heuristics. We empirically evaluate the new MAP inference algorithms on random credal networks with various graph topologies and on a collection of credal networks derived from
novel partitioning-base
applications. The experimental results demonstrate that our algorithms significantly improve computational efficiency, scaling effectively to large problems with over 3000 variables while guaranteeing the optimality of the solutions found. Thus, our proposed approach addresses two major shortcomings of previous methods for MAP inference in credal networks: the lack of solution quality guarantees and the inability to solve large and complex problems. The Appendix includes additional details, experimental results, code and benchmarks.
2 BACKGROUND
2.1 BAYESIAN NETWORKS
Bayesian network (BN) (Peall 1988) is defined by a tuple {X, P, G). where X {Xi...., } is set of variables over multi-valued domains D {D), ........ DnJ. G is di- rected acyclic graph (DAG) over X as nodes, and = (P:} where P; = P(X,(IIa) are con- ditional probability tables (CPTs) associated with each variable X, and II, X are the parents of X, in G. A Bayesian network represents a joint probability distribution over X, given by P(X) I IT).)
Given evidence e on a subset of variables E C X, the MAP task seeks an assignment y" = (vi (yi,...,b%, v to the remaining variables Y = X E that has maximum probability:
y" arg max P(y, e) arg max yEn(Y)
II P())(T)) yEn(Y) i=1
where ?) denotes the Cartesian product of the domains of the variables in Y, while x; and n; are the configurations of X, and X, parents II, in the assignment x (y, e) consistent with c.
Kwisthout 2011). However, in recent decades, several algorithmic schemes have been developed to solve MAP exactly (Kask & Dechter
MAP is known to be Na-hard in general (Shimony 1994
1999: Larrosa & Schiex 2003 Marinescu & Dechter 2009
Otten & Dechter 2011).
2.2 CREDAL NETWORKS
A set of probability distributions for variable X is called a credal set and is denoted by K(X) Levi 1980). Similarly. a conditional credal set is set of conditional distributions, obtained by applying Bayes rule to each distribution in a credal set of joint distributions (Walley 1991). We consider credal sets that closed and convex with finite number of vertices. Two credal sets K(XYY y1) and
2

---

Published as a conference paper at ICLR 2026
A
B
B
(S.27))
1
13
18
E
1
(a) Credal network
(b) Pscudo tree
(c) AND/OR search tree
Figure 1: Example of credal network and its ANDIOR search space.
K(XYY = y2), where y1 + 1/2 are two values in variable Y's domain, are called separately specified if there is no constraint the first set that is based on the properties of the second set.
A credal network (CN) (Cozman 2000) is defined by a tuple (X D, K, G), where X {X1...., . is set of discrete variables with finite domains D {Di.... Dn.. G is di- rected acyclic graph (DAG) over X as nodes, and K = (K = πT)}} is a set of separately specified conditional credal sets for each variable X; and each k-th configuration Tak of its parents I1, in G. The strong extension ((X) of a credal network is the convex hull (denoted CH) all joint distributions that satisfy the following Markov property: every variable strongly independent of its non-descendants conditional on its parents (see Cozman 2000) for more details).
n
K(X) = (H(P()) P(X)= II P(X. ((()) a vertex of K(X; =Tsk)] (2)
can be shown that the strong extension K(X) can be built from the extreme points of the conditional local credal sets denoted by ext( (at(K( (X,|I; Tu)) (Mauá & Cozman 2020).
Example Figure Ta shows simple credal network with five bi-valued variables {A, B, C, D, E). The local conditional credal sets are given by closed probability intervals. For example, we have that 0.1 < P(B = 1|A = 0) I 0.3 and 0.5 < PBB = 1 1) S 0.7, respectively.
In credal networks, there may be multiple distributions that admit maximal assignments (Mau & Cozman 2020). Therefore, we define the following maximax and maximin credal MAP tasks: Definition 1 (maximax MAP). Given credal network C = (X, D. K, G) and evidence e on E C
the maximax MAP task is finding the assignment y Y X E with maximum upper probability:
Y' arg max yEl(Y) ((E
max
II P(X.(I.)) [=1
Definition 2 (maximin MAP). Given a credal network C the maximin MAP task is finding the assignment y" to Y = X E with maximum lower probability:
(X, D, D,K,K,KK. G) and evidence on E C X.
y" arg max min yER(Y) ((E
II P(X.)L))
It is easy to see that the upper probability (or value) of an assignment x = (z1,..., In) to X can be calculated as P(x)= = I (Tx.(TT), where and n, are X; and II; configurations in and P(x,|m;) max ext K (z: mT)) is the extreme point of ((x,TT,) with the highest value. Similarly, the lower probability of x is P(x) = II (() where P(x.(T)) = min ext K ((xs(m))) is the extreme point of K ((I:(T,) with the smallest value.
Example 2. Consider again the credal network from Figure la and let x = (1,1,0,0,0 be a complete assignment variables A, B, C. D and E. In this case, the conditional local credal sets (AA = 1) and K(B = 1|A = 1) have unique extreme points each, i.e., (((KA = 1)) {0.6, 0.8) and ext( K(B 1|A= = 1)) [0.5, 0.7), respectively. The lower and upper probabilities of the assignment can be computed as P(x) 0.0144 and P(x) 0.10752, respectively.
3

---

Published as a conference paper at ICLR 2026
MAP inference in credal networks also be shown to be NP-hard (Kwisthout 2011 1 Campos & Cozman 2005). Despite sharing the same complexity class as Bayesian MAP, credal MAP involves an optimization step over the extreme points of the joint credal set, making it significantly more challenging to solve in practice. However, unlike Bayesian MAP, currently there are no established algorithmic frameworks for exact MAP inference in credal networks.
BRANCH-AND-BOUS SEARCH FOR CREDAL MAP
We present now the first depth-fing first branch-and-boute search algorithms to exactly solve the maximax and maximin MAP tasks in credal networks. These algorithms explore an AND/OR representation of the search space which exploits the problem structure and has led to significant improvements the search for MAP explanations in Bayesian networks (Marinescu & Dechter 2009).
3.1 AND/OR SEARCH SPACES FOR CREDAL NETWORKS
The AND/OR search space which is defined relative to a pseudo free capturing problem decomposition (Freuder & Quinn] 1985) has never been considered in the context of credal networks. Here, we extend and leverage it to facilitate the credal maximax and maximin MAP inference tasks.
Definition 3 (pseudo tree). A pseudo tree of an undirected graph G = (V, E) is directed rooted
tree T (V, F') such that every are of G not included in E' is a back-are in T, namely, connects node in T to one of its ancestors. The arcs in E' may not all be included in F.
Given credal network (X, D, K, G) and pseudo tree T of G. the AND/OR search tree ST based on T' has alternating levels of OR nodes corresponding to the variables and AND nodes corresponding to the values of the OR parent's 's variable, with edges weighted according to the extreme point of the conditional local credal sets in K. The size of the AND/OR search tree bounded exponentially by the depth of the pseudo tree rather than the number of variables (Dechter & Mateescu (007).
solution free & of ST subtree that: (1) contains the root of ST : (2) if an internal OR node ST is in & then n is labeled by variable and exactly one of its children is in še; (3) if an internal AND node n E ST is in & then all its OR children labeled variables are in x.
Each edge from an OR node X, to its AND child (Xi, is associated with weight w w(,,, xz;). For maximax MAP, the weight is defined by the product of the upper probabilities corresponding to the extreme points of the conditional local credal sets K [Xx| whose scopes mention variable X, and are completely instantiated along the path from the root of ST to (X,, For maximin MAP, we consider the lower probabilities instead. Each node n in ST is associated with value v(n) that captures the optimal maximax or maximin MAP value of the conditioned subproblem rooted n. Clearly, v(n) can be computed recursively based the values of n's successors and the corresponding edge weights: OR nodes by maximization and AND nodes by multiplication. The value of the optimal solution is therefore given by the value v(s) of the root node of ST.
Example 3. Figure [c we show the AND/OR search tree of the credal network from Figure Ta relative to the pseudo tree given in Figure Tb The solution tree X corresponding to the assignment
(A= = 1, B, = C, D 1, E 1) is highlighted, and its maximax MAP value, for example, is obtained by multiplying the weights associated with the OR-1o-AD edges in X. In this case, the weight
w(A,1) 1) of the edge from A (A, in & is wi (A, 1) P(A 1)- P 1 = -(CC = 1|A
1) 0.336, where P(A 1) = max ext( 1)) 0.8, P(B = 1/ 1) max (xt(K (B
1|A- 1)) 0.7 and P(C 1|A
max ea(K 1|A = 1)) 0.6, respectively.
3.2 AND/OR BRANCH-AND-BER BOUND SEARCH FOR CREDAL MAP
We present an AND/OR Branch and Bound algorithm designed to solve the maximax and maximin MAP tasks. This algorithm builds upon recent AND/OR search schemes developed for MAP inference in Bayesian networks (Marinescu & Dechter 2009). extending them to credal networks.
Algorithm outlines the AND/OR Branch and Bound (AOBB) approach for solving the maximax MAP problem in credal networks. We denote the current partial solution, the evidence and the value of the best solution found far X, e, and S respectively. The algorithm assumes that variables
4

---

Published as a conference paper at ICLR 2026
Algorithm 1 AND/OR Branch-and-Bound Search for Maximax/Maximin Credal MAP
1:
procedure AOBB(C [X, D. (.)
13: Initialize o(Xx,
then 3: return 1
14:
for all children X, of Xx in do val +- AO e, T)
15:
4: else
16:
v(X,, t v Xx. T&) val
5: X SELECTVAR(X) according T
17:
else
6:
if X evidence variable then
18:
Set ((X,, +
D (ax) such that ie e
19:
&; f- 8o (Xx 2x
Initialize v.Xx)
20:
val <- (T) v(xe, vb.
9:
for all values 24 E De do
21:
Update v(Xx)
max(v(Xx).. val)
10: & &t U [Xx m
22:
if is root of then
11:
Evaluate f(xe)
23:
Update S +- (axx(S,((X.)
12:
if f(x)) S then
24:
return v(Xx)
selected statically based pseudo tree T. A heuristic evaluation function, f(x,, computes an upper bound on the optimal maximax MAP extension of &. For the maximin MAP task, only the computation of edge weights and the heuristic evaluation function needs be adjusted.
the set X is empty, the result is trivially computed (line 3). Otherwise, AOBB selects the next variable X in 7 and iterates over its domain values (i.e., its AND successors) compute the OR node value v(Xx)) ) (lines 8-21). Subsequently, the algorithm attempts to prune unpromising domain values by comparing the upper bound f (*) of the current partial solution tree the value S of the current best solution tree found which is maintained by the root node s of the search space (line 12). For each domain value 2g of Xg. the problem rooted by the AND node labeled (Xx, is decomposed into independent subproblems C. = (x.: D Kg), one for each child X, of X2, in T. Note that if X5 is an evidence variable then its domain just D; = {ax) where ds e (lines 6-7). These problems are then solved independently and their results are accumulated by the AND node value v(X,, Ik) (lines 14-16). After trying all possible values of variable X2. the maximax MAP value of the subproblem rooted by X3 is (XXx) and is returned (line 24). Finally, the optimal maximax MAP value for the original problem is returned by the root node of the search space.
AOBB computes its guided heuristic function f(x using improved mini-bucker based bounding scheme which we will deseribe in detail in Section 4. The heuristic can be pre-compiled along the reverse order of depth-fin first traversal of the pseudo tree (which corresponds
elimination order).
Theorem (complexity). Given a credal network C = (X. D.K,K.G. G) and evidence e, the time and space complexities algorithm AOBB O(n db)) and (n), respectively, where h is the depth of the pseudo tree T of G, n. is the number of variables and d bounds their domain sizes.
MINI-BUCKETS FOR CREDAL MAP
We next describe novel partitioning cratitioning-based bounds (aka mini-bucket bounds) that are compatible with AOBB search for both maximax and maximin MAP. Although the mini-bucket bounds have proven effective in guiding search algorithms for MAP in Bayesian networks (Kask & Dechter 2001 Marinescu & Dechter 2009), they have not yet been explored in the context of credal networks.
4.1 POTENTIALS AND THEIR APPROXIMATIONS
Unlike in Bayesian networks, variable elimination schemes for the credal MAP tasks must operate on sets of probability functions called potentials (Mauá & Cozman 2020 Marinescu et al. 2023):
Definition 4 (potential). Given a set of variables Y. a potential ((Y) is a set of non-negative functions p(Y) on Y. The product of two potentials of Y) and (i) is o(Y) (Z) {p q p E o(Y), E (Z)). The max-marginal maxz o(Y) of a potential o(Y) with respect to a (Y)).
subset of variables Z C Y is defined by maxz Φ1 Y) {maxz (iiiz((Y) p(Y):
5

---

Published as a conference paper at ICLR 2026
Algorithm 2 Mini-Buckets with Moment-Matching for Maximax MAP
1: procedure MBMM(C (X,
14:
Let dhr PLUB LeEue 6, M)
Initialize I f 0
15:
Let Y. vers (Qu.) Xx
3: for all variable X2 E do
16:
Momentt-mtthinng on max marginals
4: Let du = {p: E eI((K(XA[IL)) ))
17:
Let μrr PLUB P-PBBLUUXXN (MaXY, Okr,
5: Update [ = U {PLUB(OK, M))B(((,))))) M)}
Let μ (II, 1/R
18:
6: Create elimination ordering of XI, Xn
7:
for all variable Xx E do
19:
Update obr Ohr
b Create bucket Fx and mini-buckets Qar Let = (Ø E I, Xx E vvrr(())
20:
Computt the downward messages
9:
21:
for all r to R do
10:
Update I' T I'x
22:
Let A PLUB maxxx, Ox., M)
11:
b Create mini-buckets Qui..... QuR
23:
Update {}#}
12:
Partition I' into (Qki....; Quat
24:
return max
13:
for all r = to R do
A non-negative probability function p( Y) defined over variables Y can be viewed as vector in R" where (Y is the Cartesian product of the domains the variables Y, and m = ||((Y) is its cardinality. We say that p(Y) Σ ((Y) ) if and only if ?(Y)) p(y) I q(y). Clearly, is a partial order. Therefore, pruning operator max o(Y) that selects the maximal elements a potential (YY)
defined relative
max ob Y {x(Y) E (YY) (Y) o(Y). PYY (Y)).
Furthermore, since the multiplication operator can significantly increase the size of potentials, we require a potential to have restricted cardinality, at most M (2 1). Therefore, that takes the potential o(Y), with (oY) > M, and reduces it to a smaller potential o' (Y() with cardinality at most M, while ensuring that d'(Y (Y) provides an upper bound on o Specifically, for every ( E o there exists QY) ) d' (Y) such that p(Y) S (YY). ). To achieve this, we utilize
need operator
the Pareto Least Upper Bound (PLUB) of vectors in RTT defined as follows:
Definition (PLUB). The Pareto Least Upper Bound (PLUB) J R. of a set of k vectors (UI...., } E R" is given by ū = max 1 T. where the max is applied point-wise.
simple procedure compute the upper bound o' (Y) of ( is to group the elements of ő (Y) into M clusters based on minimizing the Manhattan distance to each cluster's centroid (i.c., minimize De [p: - ril, where p; and r; are the i-th components of p and r, respectively). Then, for each cluster we replace its components with their Pareto least upper bound.
4.2 THE MAXIMAX MAP CASE
Algorithm 4 adapts the mini- mini-bucket approximation scheme developed for Bayesian MAP (Dechter & Rish (003) to the maximax MAP task credal networks. Specifically, the MBMM(1) algorithm partitions large buckets into smaller subsets, called mini-buckets, each containing at most distinct variables (aka the i-bound). The mini-buckets are processed separately by maximizing out the bucket variable from the combination of potentials within each bucket Furthermore, the algorithm avoids generating prohibitively large potentials at each elimination step by approximating both the intermediate and the original potentials with their Pareto least upper bounds of size M.
While the ILUB-based approximation of potentials may result in a looser overall upper bound, this bound can be tightened further using cooment-matching re-parameterization scheme inspired by (Thler et al. 2012)). Consider the following simple example with three variables A, B, C and two binary potentials @(A, B) and of ((,O) C). In this case, we can rewrite the mini-bucker upper bound as:
max (o(A (AA, C)] max (Ø(A, B) (A) Φ(A, C) (x))
A
S max [Ø(A, B) (1)) max (Ø C) A2(4))
A
where X1 (A) and dz (A) are auxiliary positive functions such that A₁ (1) (e 1. A simple
choice for the À functions is to use the max max-marginall on A. Let ii (A) = max Φ(A, B) and (P2(A) maxc o( A, C) be the max-marginal potentials A, and let in (A) and (2(A) be their

---

Published as a conference paper at ICLR 2026
Table Quality of Heuristics for Maximax MAP on 100 variables random networks. Average CPU time (sec) and number of nodes expanded using i-bounds from 2 to 10. Time limit 1 hour.
algorithm
=
10
time
nodes
time
nodes
time
nodes
time
nodes
time
nodes
AOBB-MB(.1)
2.90
29603
0.99
13934
0.54
6877
0.25
5280
0.18
2352
AOBB+MB(G110)
3.06
29603
1.47
13934
18.65
6877
501.36
5834
809.46
2582
100
AOBB-MB(i.50)
3.25
29603
2.07
13934
558.29
7609
2781.15
2492
3284.57
251
AOBB IBMM..))
2.25
21057
0.39
8316
0,40
4448
0.15
3344
0.20
1807
AOBB-MBMMIC
1.97
21057
0.75
8316
15,99
4448
488.84
3906
797.66
1978
AOBB-MBMM(,300
2.22
21057
1.04
8316
548.81
4910
2800.54
1633
3312,94
108
AOBB+MB(i)
2.87
29603
2.77
13934
972.37
7336
PLUB approximations of size 1. If ((A) (A) (22(A) is their geometric mean, then for #(A)
re- re-parameterization we can use: (A)
(((A and A2(A)
respectively. We have that:
[A]
Theorem (complexity). Algorithm MBMM(1) computes an upper bound on the optimal maximax MAP value. The time and space complexity is On -22 dd),, where i the i-bound, is the number of variables, d bounds the domain sizes and M bounds the cardinality of the potentials.
4.3 THE MAXIMIN MAP CASE
For the maximin MAP task, we define the pruning operator min ((Y) identify the minimal elements of a potential 6 Y) according to the same partial order & used in the maximax MAP scenario, as follows: min( ( Y)) {p(Y) E o(Y): #Y() o(Y), (Y) S p(Y))}
However, the max and min operators in Equation do not commute. As result, the variable elimination scheme that uses the min pruning operator not exact anymore and only yields an upper bound on the optimal maximin MAP value. Even when the mini-bucket approximation is enhanced with cost-shifting via moment matching, it continues to provide an upper bound though these are generally much looser than those obtained in the maximax MAP setting. Our experimental results clearly demonstrate that the associated search algorithms face significant challenges as a result.
bounds for maximin MAP are substantially weaker, and the
EXPERIMENTS
We evaluate the proposed aaacchhan-bbuuae search algorithms for maximax and maximin MAP on random credal networks and credal networks derived from real-world applications. All competing algorithms were implemented in C++ and the experiments 3GHz CPU and 128GB of RAM running Ubuntu Linux 24.04.
machine with 16-core
5.1 ALGORITHMS, BENCHMARKS AND MEASURES OF PERFORMANCE
Our proposed AND/OR Branch and Bound (AOBB) algorithm is equipped with the following versions of the mini-bucket heuristics: (1) mini-buckets without potential approximation and moment- matching denoted by AOBB+MB(), (2) mini-buckets with potential approximation of size M only, denoted by AOBB+MB(1, M), and (3) mini-buckets with both potential approximation and moment- matching, denoted by AOBB+MBMML, M). For comparison, we also ran the OR Branch and Bound (BB) counterparts guided by the same heuristic schemes, denoted by BB+MB()), BB+MB(i, M), and BB+MBMM(,, M). Unlike the former methods, the latter ones are not sensitive to the underlying problem structure. For reference, also ran the brute-force depth-first search denoted by DES that exhaustively enumerates all possible MAP assignments (see Appendix).
For purpose, we generate random and m-by-m grid credal networks. Specifically, for random networks, we vary the number variables n E (100, 150, 200) and, for grids, we choose m E {10, 14, 16), respectively. For each problem size, all cases, the maximum domain size is set to 2 and the local conditional credal sets are generated uniformly random probability intervals. In addition, consider set of 15 credal networks
generate 10 random problem instances. In
7

---

Published as a conference paper at ICLR 2026
Table 2: Results for Maximax MAP on random and grid credal networks. Average CPU time (sec) and number of nodes expanded using mini-bucket i-bounds from 2 to 10. Time limit hour.
size (onA))
algoeithm
time
nodes
nodes
nodes
nodes
time
nodes
credal networks
BB-MB()
3525,20
40136432
6399801
1799.33
125229
100
BB-MBMMÍL.)
2481.97
34115031
154.77
1717539
29.81
362314
1.00
33382
0.86
15106
(18,28)
AO6B+MBO)
2,87
29603
2.77
13934
972.37
7336
AOBB+MBMMSL)
2.25
21057
0.39
8316
0.40
4448
0.15
3544
0.20
1807
150
BB MBMM(..
3253.52
38114767
1119.96
15193688
1046.74
16149075
389.39
4938087
(27,38)
(BBB
156.22
1452909
77.77
492383
1275.38
419109
3252.94
411225
AOBB+MBMMELL
68.48
612721
23,95
323892
11.55
158230
6.56
14878]
8.43
133786
BR-MB
200
BB MBMM(.1)
2780.10 10
41392520
2342.75
37828931
(36,48)
ABBB-MB()
1555,37
8510209
1126.37
49694224
2285. 98
813793
3458.96
96.389
MORB-MRMMUL)
1158.54
84484W9
1108.73
7985450
2193611
1974790
364.89
2768420
grid credal
BB-MBG)
100
BB-MBMM(..)
3287.93
45186026
362.59
5259684
0.07
699
0.13
123
(14,38)
AOBB+MBO)
3.82
656-18
0.23
21338
AOBB+MBMMG.))
0.74
19531
0.30
2138
0.06
1235
0.07
226
0.21
107
BB-MBB)
144
BB-MBMMİL.)
3244.43
38700863
33.68
736998
0.35
1810
(18,49)
AOBB
33,80
524460
0.42
8355
1BMMM).)
18.45
247311
0.73
8325
0.27
7413
0.11
1046
0.32
327
BB-MB3)
196
1B-MBMM((T
3240.10
39599609
1072.23
16685172
(20,57)
AOBB+MBB)
961.58
10746465
1.54
32950
3478.82
32950
AOBB-MBMMG.D
4201
1.83
32948
Table 3: Results for Maximax MAP real-world credal networks. CPU time (sec) and number of nodes expanded using mini-bucked bobudd from 2 to 10. Time limit hour.
instance
algarithm
4
== 6
i
10
(n.
time
modes
time
nodes
time
nodes
time
nodes
time
nodes
2030.54
150170
3.98
50
6.07
39
3.87
alamm
BB+MBMM()D)
5.52
4535
3.77
39
3.99
4.92
39
5.36
(37,4.1)
AOBB-MBO)
5.78
85
4.81
42
5.25
39
7.64
39
6.60
39
AOBR-MHMMM(.)
2.62
2.82
39
2.80
5.38
39
2.80
MB))
link
B8+MBMM(..)
(724,15,43)
AOBB+MBB)
23.09
67424
1772
AOBB-MBMM(..)
9.77
33603
2.97
1004
2.99
978
2.79
978
2.58
793
BB+MB())
mastermind1
BH4MBMM(()))
(1220,20,56)
AOBB+MB(3
102.6 60
346669
AOBD-MBMM6.J
26.64
34493
9.96
17619
9.97
17619
9.83
17619
BB+MB())
mastermind3
BB+MBMM66.)
(3692.39,92)
AOBB-MBG)
AOBB-MBMMG.J)
3264.92
2180932
3088.55
2172466
3036.91
2167200
derived from real-world Bayesian networks by converting the probability values in the conditional probability tables into probability intervals. For all our problem instances, we ensure that the difference between the lower and upper bounds of the probability intervals was most 0.3. The problem sizes were deliberately chosen to ensure they could be solved exactly within the specified time limit. Finally, experiment with maximax and maximin MAP tasks with no evidence.
In all of our experiments, we report the CPU time in seconds and the number of nodes expanded during the search. We also record the number of variables (n), the induced width (w)) and the height of the pseudo trees (h) for all of our benchmarks. The best performance points are highlighted. All competing algorithms were allocated I hour time limit and 10GB of memory. The "_" symbol indicates that the respective algorithm exceeded its time or memory budget.
5.2 QUALITY OF HEURISTICS
Table I
shows the average CPU time in seconds and number of nodes expanded by AOBB when guided by the MB(O), MB(i, M) and MBMM(,, M) heuristics for solving maximax MAP random
Available http://wwww.mllem.mmmmmeneesssss
8

---

Published as a conference paper at ICLR 2026
Table Results for Maximin MAP on real-world credal networks, CPU time (sec) and number of nodes expanded using mini bucket i-bounds from 2 to 12. Time limit 1 hour.
instance
algorihhm
(0.10 R0
time
modes
time
rodes
time
medis
modiss
time
mardes
time
medes
BB4MBI))
128.78
2522160
77.19
2532160
alann
BBIMBMMEE.
126.35
101.46
2523160
(37,4.12)
AOBB+MB()
6:90
6.79
5.68
5499
A0BB-MEMMILL
596
348
7.31
6.17
348
0.91
(BM))))
Tak
BB+MBMMi
(724.15.43)
1245.14
113988
7405547
A080-MIMMILJ
1538.00
7655392
1245.57
7406117
1188.25
7386176
1132.29
7383518
0862912
8R4MRU)
8B4MBMM66.
(1228.20.66)
ADBB-MB()
62281
32.35
28,90
A0BB-MEMMEED
49.17
62281
32.14
32.29
61275
61245
BB+MB67
mastormind!
BD+MBMM6..)
(3691.99922
ADBE-MB6)
1200.00
1357913
1090 27
1350053
109261
1362794
1103.9
1300357
AORR-MAMMEEE
1205.83
1958178
10RL09
1360571
1077.66
1369064
1049.79
1677606
credal networks with 100 variables. The columns indexed by the i-bound, and we varied M between 1 and 50, respectively. We can see that all of the mini-bucket heuristics are competitive for the smallest i-bounds and all values of M because the intermediate potentials do not grow too large in this case and, therefore, the computational overhead is reduced. However, as the i-bound and M value increase, the size of intermediate potentials grows significantly due much larger scope sizes, which eventually translates into increased overhead. We notice that using M = 1 yields the most cost-effective heuristies, especially for larger i-bounds which produce more accurate bounds that prune the search space very effectively (Marinescu & Dechter 2009). The moment-matching cost- shifting scheme further tightens the heuristics, almost always leading to time savings, as previously observed for Bayesian networks (Thler et al. 2012 Marinescu et al. 2014).
5.3 RESULTS FOR MAXIMAX AND MAXIMIN MAP
Summaiiss the results obtained on the random and gr credal networks with the search al- gorithms guided by the MB(i) and MBMM(i, M = heuristics. As before, algorithm AOBB+MB(I is competitive only at the smallest i-bounds due to the computational overhead associated with the larger intermediate potentials that are generated larger i-bounds. Furthermore, the AND/OR search algorithms that exploit the problem structure and are guided by the MBMM(1, M = 1) heuristics improve dramatically over their OR search counterparts, in some cases by up orders of magnitude, especially at relatively smaller i-bounds (e.g.. i 4 on 10-by-10 grids). As the i-bound increases, the corresponding heuristics tend to be more accurate, and this often translates into additional time savings for the MBBB- M = 1) algorithm. However, when the i-bound increases even further, the running time AOBB+MBMM M = 1) starts to increase slightly because of the overhead associated with compiling the heuristics. The brute-force DFS algorithm could only solve problems with up to 20 variables, and therefore is omitted. These results are consistent with those obtained previously Bayesian MAP (Marinescu & Dechter (2009).
Table 3 reports the CPU time in seconds and number of nodes expanded on 4 real-world credal networks. The results show similar pattern as before where the AND/OR search algorithm equipped with mini-buckets using moment-matching and potential approximation of size 1 outperforms dra- matically its competitors, all reported i-bounds. Furthermore, AOBB+MBMM M 1) the only algorithm that scales to problems with more than 3000 variables (c.g., mastermindy and proves the optimality of the solutions obtained.
Table 4 shows the results for maximin MAP on real-world networks. As with maximax MAP, AND/OR search algorithms consistently outperform their OR counterparts across all i-bounds. However. maximin MAP proves significantly more challenging, primarily due to weaker heuristics that lead larger search spaces and reduced performance (see Appendix for additional results).
5.4 EXACT VERSUS LOCAL SEARCH
In Table we report the average CPU time obtained with the recent local search algorithms from Marinescu et al. (0033) which we adapted to maximax MAP. Specifically, we ran each of the
Stochastic Local Search (SLS), Taboo Search (TS), Simulated Annealing (SA) and Guided Local

---

Published as a conference paper at ICLR 2026
Table 5: Average CPU time in seconds for exact vs local search algorithms. Time limit I hour.
size
AOBB+MBMM(..)
SLS
TS
SA
GLS
random credal networks
20
0.00
49.60
46.34
33.61
55.83
50
0.01
184.46
107.5
98.24
175.69
100
0.10
372.75
188.92
196.96
352.78
150
2.62
565.95
223.03
300.46
529.20
200
109.25
681.60
438.32
326.83
563.61
gr d credal networks
25
0.01
53.21
44.77
38,20
59,95
49
0.01
186.56
68.27
59.30
169.44
100
0.05
350.69
171.27
164.97
327.31
144
0.09
421.20
203.42
207.58
424.90
196
0.14
572.15
312.78
362.54
456.23
Search (GLS) algorithms for total of 10 iterations (i.e., random restarts) with maximum of 100K flips per iteration. The random flip probability was set to 0.1, the taboo list had maximum size of 1000, while the alpha and initial temperature used by SA were set to 0.1 and 100, respectively. We can see clearly that in this case the exact algorithm AOBB+MBMMG, 1) dominates the other competitors while proving the optimality of the solutions obtained.
While this paper primarily focuses proving solution optimality, we note that our search schemes can be readily extended to efficient anytime algorithms, following the approach in Otten & Dechter (20TT), provide the best solution found so far at any point during the search. Furthermore, since the optimal maximax/maximin MAP assignment may not be unique, the proposed AND/OR algorithms can be equipped with book-keeping mechanism similar to the one developed for the kebest MAP task in Bayesian networks (Dechter et al. 2012) to enable the enumeration of all optimal assignments.
6 RELATED WORK
Bayesian MAP has been extensively investigated over the years and several exact and approximate
algorithmic frameworks have been developed such stochastic local search (Kask & Dechter 1999
Park 2002] Hutter et al. 2005). variational approximation and message- passsggg-pssinggggg schemes (Pearl
1988 Dechter
2002 Dechter & Rish 2003 Wainwright et al.) 2005 Kolmogorov 2006 Ihler
ct al. 2012). or hcuristic search (Kask & Dechter [999; Larrosa & Schiex 2003] Marinescu &
Dechter 2009 |209 Otten& & Dechter 2011). More recently, neural network based approximate solvers
without solution guarantees have also been proposed (Arya et al.) 2024 2025). Credal MAP has
received limited attention with some prior work on MAP inference in specialized models such as
hidden Markov models with set-valued parameters (Mauá et al.
2016) and the approximate solvers
for credal Marginal MAP developed recently by Marrnescuu et al. (2023) contrast, our contribution
addresses exact credal MAP inference with guarantees in general nigh-dimensional credal networks.
7 CONCLUSION
This paper significantly advances the field of MAP inference in credal networks by introducing novel depth-first branch-and-boune search algorithms. These algorithms leverage the AND/OR search space effectively exploit the problem structure, and are further enhanced with partitioning- based heuristic that combines potential approximations with cost-shifting strategies. Our empirical evaluations demonstrate that these new methods not only improve computational efficiency but also scale to large problems with over 3000 variables while guaranteeing optimality of solutions. Thus, our proposed approach addresses critical limitations of the state-of-the-arr, providing robust and efficient solutions for MAP inference tasks in credal networks, Potential future directions include improving the mini-bucket heuristics for maximin MAP by developing tighter approximations as well as pursuing alternative search strategies such as best-first search or hybrids of depth-fire first and best-first search.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENTS
F. G. Cozman is partially supported by CNPq grant Pq 305753/2022-3, and thanks the Center for Artificial Intelligence (C4AI-USP) with support from the São Paulo Research Foundation (FAPESP) grant 2019/07665-4) and from the IBM Corporation.
REFERENCES
Alessandro Antonucci, Yi Sun, Cassio P De Campos, and Marco Zaffalon. Generalized loopy 2u: A new algorithm for approximate inference in credal networks. International Journal of Approximate Reasoning, 51(5):474 484, 2010.
Shivvrat Arya, Tahrima Rahman, and Vibhav Gogate. A neural network approach for effi ciently answering most probable explanation queries in probabilistic models. In A. Glober- son, L. Mackey, D. Belgrave, A. Fan, U. Paquet. Tomczak, and C. Zhang (eds.), Advances in Neural Information Processing Systems, volume 37, pp. 33538-3360) Cur- ran Associates, Inc., 2024. URL https://proceedingssuu www.ndiinnnnnnuuiss..om cwtpurips..cpppprrrriie httppe/iiees/ppe/222//iea
Patiee-apppraaae Conference.pdil
Shivvrat Arya, Tahrima Rahman, and Vibhav Giridhar Gogate. SINE: Scalable MPE inference for probabilistic graphical models using advanced neural embeddings. In Yingzhen Li, Stephan Mandt, Shipra Agrawal, and Emtiyaz Khan (eds.), Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, volume 258 of Proceedings of Machine Learning Research, pp. 4465-4473. PMLR, 03-05 May 2025. URL
Cassio Campos and Fabio Cozman. The inferential complexity of Bayesian and credal networks. In International Joint Conference on Artificial Intelligence (IJCAI), pp. 1313-1318, 2005.
Andrés Cano, Manuel Gómez, Serafín Moral, and Joaquín Abellán. Hill-climbing and branch-and- bound algorithms for exact and approximate inference in credal networks. International Journal of Approximate Reasoning, 24(3):261-280 2007.
Fabio Cozman. Credal networks. Artificial Intelligence, 120(2):19--233 2000.
R. Dechter, R. Mateescu, and K. Kask. Iterative join-graph propagation. In Proceedings of the Eighteenth Conference Uncertainty in Artificial Intelligence (UAF'02), pp. 128-136, 2002.
Rina Dechter. Bucket elimination: A unifying framework for reasoning, Artificial Intelligence, 113: 41-85, 1999.
Rina Dechter and Robert Mateescu. AND/OR search spaces for graphical models. Artificial Intelligence, 171(2-3):73-106 2007.
Rina Dechter and Irina Rish. Mini-buckets: A general scheme of approximating inference. Journal of ACM, 1072)3107-153, 2003.
Rina Dechter, Natalia Flerova, and Radu Marinescu. Search algorithms for best solutions for graphical models. In Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, AAAI'12 12, pp. 1895-1901. AAAI Press, 2012.
Eugene Freuder and Michael Quinn. Taking advantage of stable sets variables in constraint satisfaction problems. In International Joint Conference Artificial Intelligence (IJCAI), pp. 1076-1078, 1985.
Frank Hutter, Holger Hoos, and Thomas Stutzle. Efficient stochastic local search for MPE solving. In International Joint Conference on Artificial Intelligence (IJCAI, pp. 169-174, 2005.
Alex Ihler, Natalia Flerova, Rina Dechter, and Lars Otten. Join boingrrap based cost-shifting schemes. In Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI), pp. 397-406, 2012.
Kalev Kask and Rina Dechter. Stochastic local search for Bayesian networks, In Workshop on Al and Stafistics, pp. 113-122, 1999.
11

---

Published as a conference paper at ICLR 2026
Kalev Kask and Rina Dechter. A general scheme for automatic generation of search heuristics from specification dependencies. Artificial Intelligence. 129(1-2)9111311, 2001.
Daphne Koller and Nir Friedman. Probabilistic Gruphical Models: Principles and Techniques. MIT Press, 2009.
Vladimir Kolmogorov. Convergent tree-reweighted message passing for energy minimization. IEEE Transactions on Pattern Analysis and Machine Intelligence, 18810))558-1153, 2006.
Johan Kwisthout. Most probable explanations in Bayesian networks: Complexity and tractability. International Journal of Approximate Reasoning, 52(1): 12(1):145,1146, 2011.
Javier Larrosa and Thomas Schiex. In the quest of the best form local consistency for weighted
CSP. In International Joint Conference in Artificial Intelligence (IJCAI-2003), pp. 631 (31-677 2003.
Isaac Levi. The Enterprise of Knowledge. MIT Press, 1980.
Radu Marinescu and Rina Dechter. AND/OR branch-and-boundd search for combinatorial optimization in graphical models. Artificial Intelligence, 173(16-17):1457-1449) 2009.
Radu Marinescu, Rina Dechter, and Alexander Ihler. AND/OR search for marginal MAP. In Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI), pp. 563-572, 2014.
Radu Marinescu, Debarun Bhattachariya, Junkyu Lec, Fabio Cozman, and Alexander G. Gray. Credal marginal MAP. In Thirty-seventh Conference Neural Information Processing Systems, 2023. URL http:://wpeeeeeeewwweeee/oououuu
Denis Mauá and Fabio Cozman. Thirty years of credal networks: Specifications, algorithms and complexity. International Journal of Approximate Reasoning, 1(126):133-377 2020.
Denis Mauá, Alessandro Antonucci, and Cassio Polpo de Campos. Hidden Markov models with set-valued parameters. Neurocomputing, 100:94-107,9 2016.
Lars Otten and Rina Dechter. Anytime AND/OR depth-first search for combinatorial optimization. In International Symposium on Combinatorial Search, pp. 117-702, 2011.
James Park. Using weighted MAX-SAT engines to solve MPE. In National Conference on Artificial Intelligence (AAAI), 2002.
Judea Pearl. Heuristies: Intelligent Search Strategies. Addison- Addison-Wesley. 1984.
Judea Pearl. Probabilistic Reasoning in Intelligent Systems. Morgan Kaufmann, 1988.
Solomon Eyal Shimony. Finding maps for belief networks is NP-hard. Artificial Intelligence, 68(2): 399-410, 1994.
Martin J. Wainwright, Tommi S. Jaakkola, and Alan S. Willsky, MAP estimation via agreement on trees: Message-passing and linear programming. IEEE Transactions on Information Theory. 51 (11):3697-3717, 2005.
Peter Walley, Statistical Reasoning with Imprecise Probabilities. Chapman and Hall, London, UK, 1991.
Hjalmar Wijk, Benjie Wang, and Marta Kwiatkowska. Robustness guarantees for credal Bayesian networks via constraint relaxation over probabilistic circuits. In Proceedings of the International Joint Conference on Artificial Intelligence (ICAII) pp. 4885 4892, 2022.
Marco Zaffalon, Alessandro Antonucci, and Rafael Cabañas. Structural causal models are (solvable by) credal networks. In Proceedings of the International Conference on Probabilistic Graphical Models (PGM). pp. 581-592. PMLR. 2020.
12

---

Published as a conference paper at ICLR 2026
13
0
1
1
Figure 2: The OR search tree corresponding to the credal network from Figure la
A APPENDIX
B DEPTH-FIRST SEARCH FOR MAXIMAX AND MAXIMIN MAP
The simplest approach to solve exactly the maximax and maximin MAP tasks in credal networks is to perform a depth-first search in the space of partial assignments to the variables (called the OR search space), and, for each complete assignment denoted by &, evaluate its score as the exact upper (resp., lower) probability P(x) = II==1 mT) (resp. P(x) -T=P((a (T.)) where 2; and m the values of X; and its parents πT; in š, respectively, and P(,, max ext( K (a:a]r (m,)) (resp. [(x:]=;;) = min ext( K (In (T))). ). In this way, the optimal solution x" corresponds to the assignment with the highest score (i.e.. the maximum upper probability for maximax MAP, and maximum lower probability for maximin MAP, respectively). Although complete, the algorithm is inefficient because enumerates all possible configurations of the variables. Therefore, its time complexity bounded by O(k"), where n is the number of variables and l bounds their domain sizes, but it can operate in linear space (Pearl 1984).
Example 4. Figure 2 shows the OR search tree explored by the depth- search algorithm
when solving the maximax MAP task for the credal network in Figure Ia A solution path cor-
responding to the assignment X (A = 1, B = 1.C = 0, D = 0, E 1) is highlighted
in red and its maximum MAP value is g(x) = P(A 1) P(B
1 1) P(C
0 = 1) P(D = B = C,C 1) P(E = 1|D = 0) 0.21504, where, for exam- ple, P(A = max ext( (xr(K ( 1|A = 1)) max( ((0.,, 0.7, 0.5, 0.7)) 007,, respectiiy,, The optimal maximax and maximin MAP solutions are in this case x" (A =A= -,
max ex = 1)) max((0.6,088) = =0.8 and P(B 1|A 1|A=1
0) with value E, = 0) with value 0.0504, respectively.
0.26244 and x 1A=1, 1,C
C BUCKET ELIMINATION FOR MAXIMAX MAP
The Maximax MAP task defined by Equation can be solved exactly using a bucket elimination procedure (Dechter 1999) that extends the Credal Variable Elimination (CVE) algorithm developed for marginal inference in credal networks (Mauá & Cozman 2020). The algorithm relies on the notion of potential well combination and marginalization operators over potentials which defined as follows.
Definition 6 (potential). Given set of variables Y. potential oi Y) is a set of non-negative
real-valued functions p(Y) on Y. The product of two potentials d(Y) and (Z( defined by
<(Y) (Z) (p q : p E d( (YY), g E 1h( (- The max-marginal maxz oi YY of potential (
with respect to a subset of variables Z C Y is defined by maxz ((Y) (maxz p YY:
o (Y)).
Since the multiplication operator may grow the size of potentials dramatically, we introduce an additional pruning operation that can reduces the cardinality a potential. Specifically, the operator max oYY) returns the set of non-zero maximal elements of d(Y), under the partial order < defined component-we as (Y) S g(Y) iff Vy E Slx, < q(y). where fy is the cartesian product of the domains of the variables in Y: max ((Y) (p(Y) (Y) (Y) E ((Y),(()) & (Y)).
13

---

Published as a conference paper at ICLR 2026
Φ (A): (pi (A), P2 (A)3
( B): (pr P2(AA), P3 (BIA), Pa (BIA))
(4)
Pz0A)
A
Pi(R(A)
A
8
Px(B)A)
Ps(814)
(e(PAA)
0.6
0.8
0
1
0.1
0
1
0.1
1
0.3
0.5
2 1
0.5
1
0.7
0.5
0.7
Figure 3: Examples of potentials for the credal network from Figure 1a
Definition 7 (dominance). Let o and Y) be two potentials defined the subset of variables Y. Then we say that d(Y) & (Y) if and only ( E o(Y), 3q E (Y) such that p(Y) I q(Y), where the latter corresponds component-wisg
defined above.
Proposition 1 (commuting max operators), Let o(X,, Xj) and (K.,,X4) ) be two potentials such that {pi, {pI.P2.... P2....,Pur Pn and psi {qi, 901.92....9m... Then, the max-marginal operator and the max-pruning operator commute, and the following equality holds:
18X
+(X; Xj) (XXi, X; P(Z)EK(Z)
max (IE
108X @ Xj) (X,, Xt), (5)
X;
where Z = (X,)UX, U X (Z) is the credal set for (X, Xj) (X;, Xx), and K" K' (x:)) is the credal set for maxx, (X,, Xj) ob(X,, Xx).
Proof. Since maXP(Z)EK(Z) prunes the credal set by finding the dominating function,
(XX; Xj) (X, Xx)
P(Z)EK(Z) o(X,, (XX
max EE (x)
max
(X,, X²))
=" X₁) 4 (Xi,Xa)
where p" (X,, X,) and q² (X, Xx) are the dominating function in the credal set (Z X₁) and
[Z Xj), respectively.
By commuting max-marginal operator,
max max X(,,,X)) (X X²)
X. P(Z)E((Z)
max (ER X, (maxp X,) (xX,,x)) e
MAX of (Xi, xx)(((X. Xx))
EER maxpp mX, (X,, (Xx,
X.
Example Consider ugain the credal network from Figure Ta Figure 3 we show the potentials ((A) and o A, B) corresponding to the sets of extreme points of the local conditional credal sets K ((A) and K ((B)A), respectively. We can see that, for example, o(A, B) has 4 extreme points represented by the distributions Pı (B)A), P2(B A), Ps (BB) and pa A)), respectively.
Algorithm 3 describes the bucket climination procedure called CBE that can be used to solve Equation 3 Let X1, X2,... Xn, be ordering of the variables X such that X, is eliminated first, then X₂ and so on. First, the algorithm creates a set of potentials T from the input local conditional credal sets K (XX,III,
). Each potential du contains the set of all conditional probability distributions P(Xa]Ila) such that (())) = P(X Ix|II; = Tkj) E ext( (X Tkj), where Tkj is the j-th configuration of the variables IIg
The algorithm then eliminates each variable X₃ by maximization from the combination of potentials that contain X in their scope, namely it computes a new potential X max (maxx, IL 6)
The resulting potential A is pruned by removing its non-maximal elements. Finally, the optimal maximax MAP value is obtained after eliminating the last variable in the ordering.
14

---

Published as a conference paper at ICLR 2026
Algorithm 3 Bucket Elimination for Maximax MAP
1: procedure CBE(C [X, K))
9:
> Create bucket L' for variable Xx
2:
b Create the potentials
10:
Let r = {Ø= E ET, T X E cars()))
3: Initialize r <-
11:
Update r = r T
4: for all variable X₃ E X do
12:
> Compute the downward message
5: Let Øx - {p p ext(K [+))
13:
Let X <- max (maxx, x Il 2)
6: Update r ru
14: Update r = u
7: Create elimination ordering o: X1 ....... Xn
8:
for all variable X E do
15:
return max Ππ
(:A(A) ()A,B) $(A.C)
(A(B,C) max(max(((4) ((A,C)))
C: $(B,C,D) (B,C)
(B, max (max($(B,C,D) (B(B))))
B:
(B,,)
(D) max (Bax(1
8
E:
(D,
2 (D) max (max(
4
D: (D)
(D)
Maximax MAP max (2) 25
max (max max (max max (D) max (max max (max & (B, mmx (A(() (AA, B) (AA, ()))))
Figure 4: Schematic bucket elimination for maximax MAP on the credal network from Figure la
Example 6. Figure shows the schematic bucket elimination for maximax MAP on the credal network from Figure Ta In this case, the variable ordering is: o A, C, B, F, D. The intermediate potentials denoted by X are shown in red.
Theorem 3 (complexity)- Given a credal network C (X, D, K), the CBE algorithm computes the optimal maximum MAP value of The time and space complexity is bounded by O(n M² " where is the number of variables, d is the maximum domain size, and M bounds the cardinality of the potentials.
Proof. Clearly, the pruning operator max commutes with the max-marginalization operator in Equation 3 Therefore, eliminating first variable and subsequently pruning the non-maximal elements from the resulting potential is equivalent to eliminating the variable from the maximizing distribution in Equation
C.1 MINI-BUCKETS FOR MAXIMAX MAP
The CBE algorithm is exact for Maximax MAP but time and space exponential in the induced width of the credal network. We describe next mini-bucket approximation for maximax MAP which we enhance further with cost-shifting scheme based moment matching.
Algorithm 4 and adapts the mini-bucket partitioning scheme developed for graphical models (Dechter & Rish 2003) to the maximax MAP task in credal networks. Specifically, algorithm MB()) which approximates CBE is parameterized by an i-bound i and works by partitioning large buckets into smaller subsets, called muni-buckets, each containing at most distinct variables. The buck-bsckets are processed separately by maximizing out the bucket variable from the combination of potentials in the respective mini-bucket. Based on previous work (Dechter & Rish 2003), it is possible show that MB(i) outputs an upper bound on the optimal maximax MAP value from Equation 3
Proposition (mini-bucke bound). Let o(X,, X,) and ((X,, X²) be two potentials such that (p1, P2, -:: Pn) and to {q1, 9m.-- respectively. Then, the following inequality holds:
15

---

Published as a conference paper at ICLR 2026
Algorithm 4 Mini-Buckets for Maximax MAP
1: procedure MB(C = K)) i-bound)
11:
Create mini-buckets QKI..... Qkn 12: Partition a3 into
2: Initialize <-
Qkn)
3: for all variable X E X do
13:
for all 1 to R do
4: Let Ø2 = {p:p E ex((((X)|))))
14:
Let @ur IIpEQu.. Φ
5: Update I = ru (Øx}
15:
& Compute the downward messages to R do
6: Create elimination ordering o: X1
Xn
16:
for all
7: for all variable X E do
17:
Let X + max (maxx, Φkr)
8: > Create bucket a and mini-buckets Qki
18:
Update I = [
9: Let & = {ó= XR E vars(
19:
return max 6)
10:
Update r 1 F
(A) ((A,B) (AA,C)
(B) = max (max (A(A) (max(((A) (AA, ()),
A
(C(C) max(max (A,
C:
D(B,C,D) 1A(C)
A
2 (B, D) max (max C, D, (C)))
B:
(B)
(B,,D)
C
2 (D) max (max (B,
B
E:
(D,,E)
2 (D) max (max (DD,)))
D: (D)
(D)
Upper Bound = max (D) 2 (D)))
max (max(((4) ((A,B) ((,B) ((4,,)))((4CC)) S max maxx(((A) - max (A,)))
Figure 5: Schematic execution of MB(2) on the credal network from Figure la
max(o(X,, (XX, X+) < [max ((X, X,)] [max (X, X+)]
(6)
X;
Proof. Let A maxx, (X,, X2,x,)) )x).-b(X. Xx)) and let maxx, Pr(X,, X, x (X,, X2)
be one of
its components. Clearly, maxx, Pe (X;, X,) (X, X,) < maxx, Pa (X X maxx, (X, X,). Let b (X,
maxx, gr X₂) and let B maxx, o(X,, X,) and C maxx. e/ XX, X₁), respectively. Therefore, a < b.c. Then it fol- lows that for every a E A, we can identify an element of a' B such that a S d'.
maxx, Pr (X, X and c = qi
Example 7. Figure shows the schematic execution of algorithm MB(i = 2) on the credal network from Figure [a In this case, the elimination ordering A, C, B, D. namely variable A is eliminated first, then C and so After eliminating the last variable D, we obtain upper bound on the optimal maximax MAP value.
Proposition 3. Algorithm MB(1) computes an upper bound on the optimal maximax MAP value.
Proof. The result follows easily by applying Proposition 2
16

---

Published as a conference paper at ICLR 2026
Algorithm 5 Bucket Elimination for Maximin MAP
1: procedure CBE(C- (X. D))
9:
> Create bucket F' for variable Xx
2:
b Create the potentials
10:
Let r = fØ Φ E ET, TT,X, X E cars(
3: Initialize r < 0
11:
Update r = r T
4: for all variable X₃ E X do
12:
>> Compute the downward message
5: Let cx = {p : p (X [.))
13:
Let X <- min (maxx, HoEr, 9)
6: Update r ru
14: Update r = (u
7: Create elimination ordering o: X1, X1..... Xn
8: for all variable X E o do
15: return min [ 2)
D BUCKET ELIMINATION FOR MAXIMIN MAP
For maximin MAP, we define min pruning operator that returns the minimal elements of a po- tential o relative to the same partial order S, namely min(o(Y)) = {p(Y) o(Y) : $q E
,(Y), S p(Y)).
Proposition 4 (commuting max-marginal and min-pruning operators). Let o(X,, X,) and (X,,, Xx) be two potentials such that Φb = (pi,p2,...,53 PP and psi = {q), 92.... 4m.. Then, commuting the max-marginal operator and the min-pruning operator yields the following inequality:
max min 6(X,, X,) (6) X: P(Z)EK(Z)
min JER
max (X,, X2) (X,, Xx), X;
where Z = (X,) U X (Z)) is the credal set for of (x Xj) . (X,, Xx), and (' (X:))
the credal set for maxx; of ,, Xz) xb,,, Xx).
Proof. The left-hand side of the inequalty can be written as,
max min o(X,, X,) (X,, Xx)
X; ((Z)
max
min X; (K,
Xx)
min
(XX,, Xx)
(2222))
max p. Xx X,) qa( (X, Xx),
X;
where p. (X,, X,) and qz (X,, x are the dominated function in the credal set KZ Xx) and
(Z X)), respectively.
By commuting max-marginal and min-pruning operator,
max o( (X,, X, (X X,) (Z((X))E X;
min
min PEX (Z((.)) X.
{max pl (X,,, X,) (X,,
-X, X 2 max (X,, Xj) g. (Xi, Xt),
X:
where r. (X, X₂) is the dominated function in the set (maxx, P glvp E 0, E v).
Algorithm 5 describes the bucket elimination procedure called CBE that can be used to solve Equation However, unlike maximax MAP, in this case CBE is no longer exact and only computes an upper bound on the optimal maximin MAP value. It is easy to see that max and min do not commute in Equation 4 We illustrate with simple example that by pushing the outside max inside the min operator yields an upper bound: max(min(3, 1), min(3.2) = max 2) 2 S min(max(3,, 1), max(1, 2)) m3n 3.
Let o: X1, X2,X2... Xy...., Xx, be an ordering of the variables X such that X, is eliminated first, then X₂ and First, the algorithm creates set of potentials I' from the input local conditional credal sets K(X,II, = ). Each potential Φy contains the set of all conditional probability distributions ((X such that P(rx (())) P P(Xx 24 [ mRj) E ext( K ((X,[TT [Tx mkj). The algorithm
17

---

Published as a conference paper at ICLR 2026
Table 6: Results for Maximax MAP on 100 variables random networks. Average CPU time in seconds and number of nodes expanded using mini-bucke i- i-bounds from to 12. Time limit hour.
size
algorithm
2 nodes
i bodes
== nodes
i= nodes
= 12 nodes
time
time
nodes
time
time
time
time
candiom credal networks
AOBB-MB((1))
2.90
29603
0.99
13934
0.54
6877
0.25
5280
0.18
23352
0.09
1438
1OBB-MB((.1))
1.47
501.36
5834
809.46
1405.00
AOBB-MB(i.30)
3.25
29603
1.72
13934
555.51
7609
2731.54
3462
3153.93
209
AOBB-MB(..50)
3.25
29603
2.07
13934
558.29
7609
2781.15
2492
3284.57
25
100
AOBB- 1)MMM.
2.25
21057
0.39
8316
0.40
4448
0.15
3544
0.20
1807
0.10
773
1.97
21057
0.75
8316
15.99
4448
488. 84
3906
797.66
1978
1770.41
1204
2.12
21057
0,94
8316
2162
3189.10
BOBB-MBMMM..55
2.22
21057
1.04
8316
548.81
4910
2800.54
1633
3312.94
108
AOBB-MIBIC
2.87
2.77
Table 7: Results for Maximax MAP on random credal networks. Average CPU time (sec) and number of nodes expanded using mini-bucket i-bounds from 2 to 12. Time limit hour.
size (ur.A)
algorilun
2
[- 30
12
time
modes
time
nodles
tinse
nodes
timse
sodes
cime
noles
Lime
nidles
DUS BB-MBG)
18.55
209/152
0.01
0.01
775.55
776.53
774.82
(4.9)
BB+MB/LL))
0.01
0.01
BB-MBXIMLL)
0.01
0.00
776.20
A0BB-MBMIMS
BB-MB
1:15
0.57
3351.72
1,00
00901
0:45
9572
947
0/02
0,00
BBMMEM
0.36
5178
0.07
818
0.02
276
0.01
0.02
52
0.02
AOBB MBB/2
0.03
296
0.04
198
$18.48
161
3333.34
55
NOBB-8228 -BBBB)
0.03
298
0.02
198
0.05
106
0.01
75
0.04
54
0.02
AOBB-MBB30 --BBB- 1)
0:00
159
0.01
107
0.06
94
0.01
0.07
0.02
DFS
100
BB-MBBI
3525.20
40135432
1014.36
6399801
1789:35
123229
(18,28)
BB-MBLLL
3414.32
46208833
576.28
6399801
21.88
348970
1992
64725
0.39
10498
0.35
10254
1B
2481.97
341 15031
154.77
1717539
29:11
302116
1.00
33382
0.86
15106
0.30
5206
2.87
29603
2.77
13934
97237
2326
2.50
20003
0.99
13934
0.54
0827
0.2
5390
0.18
2350
0:00
1438
D
2.25
21057
0.39
8316
4448
0.20
1807
0.10
RR-MIRG..
3273.95
21740102
987.20
6021565
BB-MBMMMLL
3253.52
35114767
111996
15193688
16149075
389.39
4908087
459900
MOBB-MBBL
156.22
1452909
37.37
492385
1225.38
439109
3252
411224
KOBB-MBOLD
151,57
1452909
41.20
492385
30.97
351672
11.04
279360
281745
11,02
176400
AOBII-MIMMI.
612721
23.95
323892
158230
135796
2,82
47218
DES
200
UB-MBK00
(16.48)
B0-MBRLLD
$458.00
56460834
2699.46
58464711
BI-MREMMMLL
2780 10
41302520
2342:75
37628931
1495.40
29931863
AOBB-MAB
1555.32
8510009
1136-37
4069434
2285.08
813703
345% 95
98389
AOBR-MBB..
1537.41
9057428
1112.31
7572102
079
0378560
73%
7500775
433.13
3553045
113.94
1407560
1155.54
$455259
1106.75
7983450
197.49
219351
224.33
19717900
364.89
2768420
109.25
1344753
then eliminates each variable X₂ by maximization from the combination of potentials that contain
X₁ in their scope, namely it computes a new potential X min (maxx, I x) The resulting potential A is pruned by removing its non-minimal elements. After eliminating the last variable in the ordering, the resulting value is upper bound the optimal maximin MAP value.
E ADDITIONAL EXPERIMENTS
In this section we include additional experiments and details that were omitted from the main paper. We note that all of our experiments, did not consider any evidence.
E. RESULTS FOR MAXIMAX MAP
Tables and g summarize the results obtained on the random, and grid credal networks. The columns are indexed by the mini-bucket i-bound, and in each cell we show the average CPU time in seconds, and the average number of nodes expanded by the respective algorithm. We ran the OR and AND/OR branch and bound algorithms guided by mini-bucket heuristies without poten- tial approximation and moment-matee matchhig (i.e., BB+MB(), AOBB+MB()), mini-bucket heuristics with potential approximation of size only (i.e., MB,, AOBB+MB(.1)) and mini-bucket
18

---

Published as a conference paper at ICLR 2026
Table 8: Results for Maximax MAP on grid credal networks. Average CPU time (sec) and number of nodes expanded using mini-bucket i- i-bounds from 2 to 12. Time limit hour.
size
tigorithm
10
12
(ur A1
time
modee
Fime
piddes
time
middes
timee
time
nodies
1436
3186.05
3383.82
KOBD-MBOLD
0.01
0.01
0.04
0.01
KOBD-MUIMMML
0.01
0.04
0,01
DFS
49
BB-MBB
141.00
4454273
5.10
53819
3534.1
498
(9,25)
BB-MBILJ)
187.40
4454273
2.23
53819
0.02
708
0.01
74
0.04
51
0.00
51
MBMMM
$0.53
1725556
1.01
20788
001
96
0.02
0.05
0.00
51.
ACBSB-M360
0.00
562
0.11
266
1392
132
A0BR-MB66.)
0.00
562
0.03
266
001
144
0.3
0.06
51
0.01
51
40BR-MBMMM.
0.02
299
0.07
227
001
67
0.03
0.10
51
0.02
51
DES
100
(14.38)
RB-MBRG
2069
1342799
4123
0.06
BB-MBMMELL)
5259584
699
0.07
AMBB-MBB1
0.23
144
BB-MB()
(38,49)
BB-MB-LD
2682.01
51081184
986.25
23294052
5:44
184264
RB- MIBMMM
1244.5 45
34700863
38.68
716998
0.55
1810
0.16
1787
A0BB-MBB)
33,50
524450
0.42
8355
A0BB-MB(LL)
43,48
534450
0.46
8555
0.28
8324
0.33
7073
0.74
5710
0.15
2278
X0BB-MBSIMIL
18.43
247311
0.33
8525
0.27
7413
0.13
1046
0.52
327
0.09
243
DES
196
BB-MBGG
(20,57)
BB-MB/LJ1
2243.14
53045763
BB+MBMIMLL))
3240.10
39599609
1072.23
16685172
0.24
1060
AOBB MIBO
961.58
10746423
1.54
32950
3478.82
32950
ACBB-MMRLL
32045
1.01
A0BB-MBBMML
395.68
42013907
2.19
32950
31339
24508
1.83
0.14
heuristics with potential approximation of size 1 and moment-matching (i.e., BB+MBMM(.J) AOBB+MBMM(.I) respectively. In addition to the branch-and sorcch-and-buune algorithms, we also ran the brute force depth- depth-first first search algorithm denoted by DFS.
E.2 RESULTS FOR MAXIMIN MAP
Tables TO and TT summarize the results obtained on the random and grid credal networks for the Maximin MAP task. In addition, Table [2 shows the results obtained the real-world credal networks. As before, we report the average CPU time in seconds and average number of nodes expanded during search, across various mini-bucket i-bounds. We Branch and Bound algorithms that exploit the problem structure dramatically outperform their OR search counterparts, across all reported i-bounds.
again that the AND/OR
However, unlike the Maximax MAP case, the Maximin MAP task appears to be much more difficult solve by the proposed AND/OR search algorithm. This is primarily due the much weaker mini-bucket heuristics compiled for Maximin MAP compared to those compiled for Maximax MAP. Indeed, we recall that the variable climination procedure described by Algorithm Bis not exact for Maximin MAP and only outputs an upper bound on the optimal Maximin MAP value. Consequently, the mini-bucke approximation of this bound turns out be much looser even if we try to tighten with the moment-matching scheme.
Consequently, the AND/OR branch and bound algorithms for Maximin MAP guided by the mini- bucket heuristics with potential approximation of size and moment-matching can only solve random problems with up to 150 variables.
We observe however that AOBB+MB() with relatively small i-bounds (i.e., 2 or 4) performs quite well and able to solve the problems relatively efficiently. This indicates that the corresponding mini-bucket bounds without potential approximation and moment-matching are tighter than those involving the Pareto least upper bound. Unfortunately, compiling the MB(i) heuristics for higher i-bounds is not feasible because of the computational overhead. Therefore, possible direction of future work is to study the mini-bucket heuristics for Maximin MAP and develop new ways to tighten them even further.
19

---

Published as a conference paper at ICLR 2026
Table Results for Maximax MAP on real-world credal networks. CPU time (sec) and number of i-bounds from 2 to 12. Time limit 1 hour.
nodes expanded using
Insance
aggonthm
=2.0
4
(0. M1.
time
rodles
time
meries
time
medee
time
meades
time
medess
time
musden
BU-MIDE
150170
3.52
5.25
7.64
6.60
6.56
39
2.80
2.75
39
BB-MB(3)
0.02
0.00
72
0.00
72
0.00
72
0.00
72
0.04
72
child
BB BBB-MMMMIL 11
0.00
73
0.00
72
0.01
72
0.01
72
0.00
72
0.01
72
(30,3,0
0.01
74
0.00
22
0.001
22
0.00
22
001
22
0.01
22
AOBR+MBMMML
0.00
0.00
22.
0.00
22
0.00
22
0.00
22
0.00
22
6B-MB(5)
3.57
174
hatlinder
RIR-MMMMII
13:10
16%
58
10.95
11:29
58
1089
58
(56,5,11)
AORR+MRIJ
58
534
0.09
0.07
0.30
(27.7.11)
NOB3+MBUS
MBMM+
0.06
0.07
0.08
56
MBB
Bnk
BB MUMMMMK 13
(724,15.4))
A0BB+MB())
23.00
67424
3.74
1772
KOB3+MEMMI...
9.77
33603
2.97
1004
2.99
978
2.79
978
2.58
793
2.88
755
R8-MRG)
muskmmidd
B8-MRMMMC
(1230,20.56)
40B3+MB(0)
102.60
988
17619
9.67
17619
BB-MBi5)
maskernind
1
(1692,9992)
MOBIS-MBU
MOBB+MHMMMLL
$764.92
2180030
3038.55
2123466
3016.1
2167200
901041
2167117 17
BSI-MIN0
3K77
349647
0.87
42
1.44
57
1.40
57
1.25
37
3,52
37
mildow
MII-MIIMMLL 13
3.14
33005
0.10
37
0.11
57
0.11
52
0.11
37
0.12
57
(35
XOBB+MBIa
0.13
112
0.73
1,53
57
1.81
57
1.27
37
1.44
37
.0BBB NOBB+MEMMAI..)
0.05
0.13
0.11
0.11
0.12
37
0.12
37
BB-MBB))
munio
11
7.71
1056
7,47
1043
7.04
(1041.8.26)
1076
AOBR+MBMMC
1.78
1044
1.24
1043
1.62
1043
1.90
MBB
pasiinnzl
BR-MRMMMCL
93.25
974000
(334,21,47)
A0BB+MB())
1009 58
$359182
53.27
131390
158.79
131300
K0B3+MEMMXKJ)
(543.)
839905
34.54
131390
29.64
85817
29.90
104772
23.39
12259
22,50
466
BR-MIR65
polignad7
BR-MRMMILL 1J
(1008
MBBB+MBB
2816.21
3050
239
1901613
74.35
547030
BB-MMB
pedugneet
132421
KOBB+MEMM(LLL
3126.56
16782641
121021
25684
8:96
15427
16.43
32946
165.72
119.07
415
191.26
166.74
Adlabctes
BB-MBMMACGL
0.52
415
0.56
415
0.56
415
0.57
415
(413,4.44)
MB
0.40
520
1.04
425
153,02
415
179.66
415
163.06
415
114.08
415
KOBR--MMMMML
0.19
405
0.12
435
0.21
415
0.21
415
0.26
415
0.5
415
6B-MB66
3255
559615
17.32
510
xharley
BUN-MUMMIIL 13
3601
7.89
15:71
50
1582
50
1692
30
17.35
50
(48.7711)
22:34
AOBR+MRMMICL)
7.9
7.66
50
16.90
50
16.91
0.79
(441,10,25)
NOBB:MB(I)
535
463
252.95
X0B3+MBMM)))
480
0.16
454
0.35
0.33
0.35
F COMPARISON WITH LOCAL SEARCH ALGORITHMS
We also extended the local search algorithms developed previously for credal Marginal MAP (Mari nescu et al.) 2023) to solving the credal maximax and maximin MAP tasks well. Specifically, we developed the following algorithms: Stochastic Local Search (SL.S), Taboo Search (TS), Simulated Annealing (SA) and Guided Local Search (GL.S), respectively. In all our experiments, we ran the algorithms for total of 10 iterations (i.c., random restarts) with maximum of 100,000 flips per iterations. The random flip probability was set to 0.1, the taboo list had a maximum size 1,000, while the alpha and initial temperature used by SA were set 0.1 and 100, respectively. As before, the time limit was set to hour.
Tables 13 and 15 present the results for the Maximax MAP task both random and real-world credal networks. Similarly, Tables [4 and 16 report the results for the Maximin MAP task on the same set of problem instances.
20

---

Published as a conference paper at ICLR 2026
Table 10: Results for Maximin MAP on random credal networks. Average CPU time (sec) and number of nodes expanded using mini-bucket bucket i-bounds from 2 to 12. Time limit 1 hour.
s7z0 (ur A1
sigorithm
10
12
time
modes
Fime
poddes
time
middes
timre
rodies
rimee
time
modles
(4.9)
1210
12.10
0.01
760.20
781.64
781.64
1OBD-MBOLD
0.01
93
0.01
0.00
0.00
65
KOBB-MBMMI..
0.01
0.01
0.01
69
DFS
50
MB-M
2197.76
50789163
2235.78
90543636
2466.3 74
40490369
(9.17)
MB-MBIL.)
3695.3
50996426
2374.55
47800538
2013.88 88
43649700
2307. 14
43401873
2415.52
50355186
2383.77
48786553
2452.6
48682244
2166.87
41940652
2156:39
45607 576
2405 55
50088103
2411811
50118806
23
414871555
ACBB--M36)
0.00
S11
0.5
407
1564 35
797
3287 63
591
A0BR-bR66.)
0.06
992
0.04
767
0.9
574
0.04
697
0.04
772
0.01
6K3
40BR-MBMME.
0.06
816
0,05
678
0.04
510
0.05
702
0.06
6R9
0.05
683
DES
100
(18.38)
RB-MBRG
BB-MBMMELL
AMBB-MBB1
32181
2283083
330-53
1400455
2535
31087
205
200
106
(27.38)
1.50
BB-MB-LD)
RR- JIBMMML
BB-MBQ)
3241.71
3041
33579900
24284657
237 19719
334
1341 35
3244.57
56683101
3221
3241.00
4341 07
30000506
5627155
3240
954R 90
30044588
328074
$120000
3240.63
504045
A0BB-MBB)
2536.15
10771886
2209 90
79055843
1348.35
111 1112588
A0BB-MB(LL)
3342.14
16470814
2498 03
13012006
2825.30 31
18955006
25900 95
19512663
2299.04
16106412
3450.80
19844066
21333760
X0BB-MBSIMIL
3099.00
15395878
2451.84
16626578
3216.77
18055772
2299:00 99
15835166
2546.66
19344809
2603.07
DES
200
BB-MBG)
(36,48)
BB-MBILJ)
BB-MEMIMLL)
COBB-MBBL
AIBB-MBLLL
MBBB-MBMMEL
Table 11: Results for Maximin MAP on grid credal networks. Average CPU time (sec) and number of nodes expanded using mini-bucket i-bounds from 2 to 12. Time limit hour.
siec (e'.A) A]
algınihm
12
time
modes
titee
oodes
1100
nodes
1101e
modes
time
nodes
180t
00.06
67105564
0.06
3275
24
3253
27
BBB MBBLL
2139003
58.13
21019433
2083664
53.75
20836664
2063666
52.75
2053684
BB-MEMMM)LJ
45.17
2142016
42.65
2092664
41.00
2081684
41.61
2061684
42.53
2063684
38.19
2063684
XOBB-MMB0
0.01
122
0.85
50
3278.55
27
3286.95
27
3263.82
27
3259099
27
N08I--MB0L1
0.06
1680
1186
1909
1195
349h
0.05
3495
0.05
349h
1.00
3495
NO8B A0B6-MBMMLLL
0.10
3653
0.10
3506
0.10
3496
0.10
3495
0.09
3496
0.09
3495
DFS
MB+MB661
1450
110349922
3555.44
129042447
3532
135249370
3579.86
141018196
MEMM3L)
3522.94
120903523
3993.77
130957532
2880,00
137553732
AORB-MRMMELL)
NOBB (BBB-
MORR--MB
0.09
2.76
1,30
67668
65652
662
0.13
0.63
1.26
40579
90705
2656
1992
0.92
1.26
99591
40029
192
121
1IEE
39748
30690
1.02
1:30
39624
50634
1.02
1.27
39524
50504
DRS
MBRI
3410.50
45573423
(14.38)
BR-MENNMM..D
3850,00
56787785
MOBB-MBB
MOBB-MBELI)
390.56
25.49
10999062
32883
364
TU.54
10424997
1126
102801
565158
11333724
102
$417.01
362.88
11541135
102
362 64
10914006
362.85
11132756
NOBB- MOBB-MEMMALL
384.44
8525836
363.05
8545538
364 31
363.55
362 98
9007334
363.20
0076567
DRS
144
(20,57)
BB4MB/L.)
50354017
NOBB MMBO
524460
8355
NOBB (MBLL)
99
61463739
1455
1455.18
52002185
1451.04
52766048
$451,10
55655795
MORB-MRMMMLL
3094.0
58071151
1739.55 59
49651511
1457 63
44004163
1455 40
44007400
145% 90
44122608
E252 ST
DRS
196
BB+MBB
(18
HIN-MILLL
BIB MENNMIL))
NOBBB
10706465
32850
AOBE-MB6.1
31596532
2270
38296631
2248.19
38594634
36055993
NOBBB- NOBB-MUMMELT
1610.52
20372542
195066
25765210
2259.95
120998166
1638
27250308
2249:21
37315455
G SUMMARY OF THE CONTRIBUTION
This paper presents significant advancements in the field of MAP inference for credal networks. While MAP inference has been extensively studied in Bayesian networks over the past decades, its counterpart in credal networks has received comparatively limited attention. To date, there exists no established algorithmic framework for solving credal MAP tasks in practical settings.
21

---

Published as a conference paper at ICLR 2026
Table 12: Results for Maximin MAP on real-world credal networks. CPU time (sec) and number of i-bounds from 2 to 12. Time limit 1 hour.
nodes expanded using
instance
algorihm
12
(0. R)
time
mudee
time
rodles
time
medie
modirs
time
mardes
lime
nedes
BB4MBI))
BBAMBMMEE.
(37,4.12)
ADBB A0BB-MBMMMLL
7.31
(B+MBB)
1786
1786
1766
(20,3.)
1080-MIMMIL.))
0.00
0.00
0.00
884MRL)
baillanke
BB+MBMM66.
(56,5.11)
ADBB-MB()
10.34
389
40BB-MEMMEE
10.14
BB+MBU6
158021
14.32
155472
11.34
135918
11.14
135918
8.65
135918
135918
BB-MBMM6..
15.45
191919
13:12
14015
12.23
135918
10.79
135918
7.80
135918
135918
(2.7.11
AOBE-MB6)
0.07
205
0.05
212
0.03
207
0.05
207
0.06
MORR-MEMMME..
0.07
315
268
0.06
212
0.05
207
0.03
307
0.06
207
BB+MBB
Tink
BRAMRMME.J
(724
4ORB+MB6)
1663.40
7K30555
1245.14
7448834
1180g95
7427647
1199.88
7405547
1072.66
7400959
AOBB-MEMMEE.)
1538.40
7455392
1245.57
7406117
1188.25
7386176
1122.29
7583818
995.99
6862912
BB BB+MB63
masteriind
BB MB+MBMMILL
(1220.2056)
ADBB-MBB
49.00
64081
49.14
64240
34,42
82281
52.35
61822
28.90
61189
30,69
801266
ADB0-MUMMEJ.
47.79
64081
49.17
64259
34.04
82281
32.14
617.77
32.29
61275
30.07
61245
BB4MBG)
mustemindd
BB-MBMME..
(3692.39.92)
AOBB+MBC)
1200.00
1357913
1099.27
1357053
[092.1
1362794
29
1370757
A0BB-MBMMEED
1205.83
1359178
1083.09
1360571
1077.06
1365064
1049.79
1357600
BB+MBG)
0.09
5376
0.18
5376
0.37
5376
0.15
5376
0.10
5376
0,09
5376
mildew
BB 1BMMIEEE)
0.15
5376
0.17
5376
0.19
5376
0.10
5376
0.19
5376
0.15
3376
(35,4.15)
AOBB-MBC)
0.22
1563
0.17
98.
0.10
570
0.14
970
0.08
970
0.15
970
1OBB-MBMMEL.
0.20
1128
0.19
912
0.15
970
0.21
970
0.20
970
0.12
970
2048
BRAMRMEE.
0.56
2048
0.48
847
2048
(441.10.25)
AOBB-MBB)
2192
0.58
1.00
0.88
2232
A0BB+MEMME).)
2282
8.0
2282
Table 13: Results for Maximax MAP random and grid networks. Average CPU time in seconds for systematic vs con-systematic search algorithms. Time limit hour.
size
AOBB+MBMM(.1)
SLS
TS
GLS SA
random networks
20
0.00
49.60
46.34
33.61
55.83
50
0.01
184.46
107.5
98.24
175.69
100
0.10
372.75
188.92
196.96
352.78
150
2.62
565.95
223.03
300.46
529.20
200
109.25
681.60
438.32
326.83
563.61
g 1 d networks
25
0.01
53.21
44.77
38.20
59.95
49
0.01
186.56
68.27
59.30
169.44
100
0.05
350.69
171.27
164.97
327.31
144
0.09
421.20
203.42
207.58
424.90
196
0.14
572.15
312.78
362.54
456.23
Recently, Marinescu al. (2023) pioneered the study Marginal MAP inference in eredal networks a generalization of pure MAP inference. They introduced several stochastic local search algorithms alongside an exact brute-force depth-first search method. However, their empirical evaluation revealed that these approaches either limited to very small problem instances lack guarantees regarding the quality of the solutions produced.
In response to these limitations, we propose novel branch-and-bourd search framework designed to address two critical challenges: (1) scalability to larger and more complex credal networks, and (2) provision of solution quality guarantees, particularly optimality. Our approach leverages the AND/OR search space to exploit the underlying problem structure efficiently. This is further enhanced by a partitioning-based heuristic that integrates potential approximations with cost-shifting strategies. The
22

---

Published as a conference paper at ICLR 2026
Table 14: Results for Maximin MAP on random and grid networks. Average CPU time in seconds for systematic vs non-systematic search algorithms. Time limit 1 hour.
size
AOBB+MBMM 1)
SLS
TS
SA
GLS
random networks
20
0.01
51.34
49.47
35.47
59.17
50
0.04
232.09
103.47
72.94
139.67
100
297.10
349.30
175.27
149.91
272.30
150
2216.77
471.92
311.40
198.21
384.21
200
576.57
380.96
262.67
435.96
gri d networks
25
0.09
61.80
46.19
39.46
62.67
49
1.20
178.29
73.36
63.61
120.19
100
362.98
355.03
213.00
114.30
258.98
144
1452.31
401.44
257.59
171.27
327.11
196
1638.70 70
508.97
277.42
245.27
466.84
Table 15: Results for Maximax MAP on the real-world credal networks. CPU time in seconds for systematic vs non-systematic search algorithms. Time limit hour.
instance alarm child
AOBB+MBMM((.)
SLS
TS
SA
GLS
2.62
3600.05
3600.00
3600.02
3600.02
0.00
23.22
28.96
8.88
14.99
hailfinder
10.74
3600.05
3600.05
3600.05
3600.05
insurance
0.06
296.68
219.52
146.25
145.71
link
2.58
3600.01
3600.01
3600.01
3600.01
mastermind1
9.67
3543.37
874.84
1056.
2629.90
mastermind3
3010.41
3600.02
3600.02
3600.02
3600.02
mildew
0.08
242.49
128.90
124.13
257.74
munin
1.59
3600.00
1678.61
2563.09
3600.01
pedigree
22.50
3600.00
3600.25
3600.25
3600.25
pedigree7
74.35
3600.00
3600.25
3600.25
3600.25
pedigree9
8.96
3600.00
3600.25
3600.25
3600.25
xdiabetes
0.12
445.32
726.82
622.27
688.75
zbarley
7.66
3600.08
3600.08
3600.08
3600.08
zpigs
0.19
2478.80
638.01
673.14
1813.44
AND/OR search space, previously shown to yield substantial time savings in Bayesian networks, is here extended to credal networks and both maximax and maximin MAP tasks.
Given that mini-bucket approximations of variable elimination in credal networks often incur high computational costs due to very large potentials, we introduce a novel approximation scheme. This scheme utilizes the Pareto least upper bound concept for multi-dimensionn vectors to manage potential complexity effectively.
Our empirical results obtained both synthetic and more realistic credal networks demonstrate that the proposed methods not only enhance computational efficiency but also scale to large networks with over 1,000 variables, all while guaranteeing the optimality of the solutions.
Finally, we observed that Maximin MAP is much more difficult to solve by our proposed algorithms than Maximax MAP. This is because the mini-bucket based heuristic upper bounds for Maximin MAP are significantly weaker than those compiled for Maximax MAP. Therefore, another avenue for future work explore new ways tighten the mini-bucke heuristics for Maximim MAP.
23

---

Published as a conference paper at ICLR 2026
Table 16: Results for Maximin MAP on the real-world credal networks. CPU time in seconds for systematic non-systematic search algorithms. Time limit hour.
instance
AOBB+MBMM I)
SLS
TS
SA
GLS
alarm child
3.77
3600.05
3600.00
3600.02
3600.02
0.00
25.54
19.07
6.43
31.67
hailfinder
9.37
3600.15
3600.04
3600.06
3600.05
insurance
0.03
447.66
113.53
98.23
196.98
link
995.99
3600.01
3600.02
3600.01
3600.03
mastermindl
30.17
1965.99
948.96
1237.18
2295.69
mastermind3
1049.79
3600.02
3600.02
3076.61
3600.02
mildew
0.12
741.58
557.08
190.81
240.82
zpigs
0.62
894.96
282.35
257.57
542.11
24


Reviews:
[{"review_id": "iF7hiFXThl", "reviewer": "Reviewer_JLKE", "summary": "This paper uses various techniques developed that have been previously applied to MAP inference in Bayesian networks, and extends them to credal networks, specifically to the maximax and maximin MAP tasks. The resulting algorithm is provably exact and empirically more efficient than existing algorithms (both exact and not).", "questions": "1. Section 1 mentioned Marginal MAP, but doesn't define it. How does it relate to the MAP tasks studied in this paper: Is one harder than the other? For which real-world problems are they best-suited?\n2. Figure 1(b): according to the definition, it seems there should be an arc between C and D, correct? Does this affect the solution tree or the way the algorithms operate on this example?\n3. Some questions about Algorithm 1:\n  - there seems to be a hat missing on $\\mathbf{x}_k$ in line 12 of the algorithm (similarly, line 216 of the text has a bar instead of a hat);\n  - $S$ is not mentioned anywhere else in the algorithm. Is it an alias for $v(s)$? If so, I suggest to write that instead.\n4. What is the distribution of the \\texttt{random} graphs?\n5. According to the main text, the algorithm for maximin MAP is much less efficient than the maximax one. Yet when comparing mastermind3 in tables 3 and 4, the maximin case is much faster. What is going on here?\n\n### Minor comments\n\n- line 27: \"Instead *of*\"\n- definition of $\\max$ on line 251: this should rule out the possibility of taking $q(Y)$ the same as $p(Y)$; as written, $\\max$ is always the empty set. Same for $\\min$ (line 310)\n- the two-column form of the algorithms makes it impossible to see at which nesting level the first line of the second column is. Please resolve this, for instance by adding vertical helper lines.\n- section \"A Appendix\" is empty; remove/replace this header\n- Definition 6 and the text below it in Appendix C replicates part of the main text\n- line 748: stray \"and\"", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The algorithm is a substantial improvement over existing work, in a challenging and significant problem. The theoretical quality seems to be very high. The work is mostly clearly presented, though improvement is possible there.", "weaknesses": "The appendices include a lot of additional material, but the individual appendices are not referenced from the main text, making it an \"exercise for the reader\" to discover when they should skip from the main text to an appendix. The storyline of the main paper came across as incoherent in section 4 due to this.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "j8U6rD94Dd", "reviewer": "Reviewer_Q5Sg", "summary": "This paper focuses on Maximum a Posteriori (MAP) inference in credal networks, which generalize Bayesian networks by allowing imprecise probabilities represented through convex sets of distributions (credal sets).\n\nThe authors define two MAP tasks, maximax MAP (finding assignments maximizing the upper probability) and maximin MAP (maximizing the lower probability). To solve these tasks, the paper introduces:\n\n1- Depth-first Branch-and-Bound algorithms for exact MAP inference in credal networks, extending prior AND/OR search formulations used for Bayesian MAP inference.\n\n2- A partitioning-based mini-bucket heuristic with potential approximation and cost-shifting (moment matching) to guide the search and reduce runtime.\n\nThe algorithms are evaluated on random and real-world credal networks (e.g., ALARM, Link, Mastermind) and demonstrate scalability to networks with over 3,000 variables.", "questions": "See weaknesses.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "1- The paper is mathematically sound, with clear definitions of credal networks, the maximax/maximin MAP formulations, and the bounding procedures.\n\n2- Well-written and organized, following the style of classical graphical model research.\n\n3- Empirical results demonstrate strong performance improvements over simpler search strategies and show good scalability.\n\n4- Provides one of the few systematic attempts to perform exact inference in credal networks, which are otherwise rarely explored.", "weaknesses": "1- The overall contribution is incremental, mainly extending existing AND/OR branch-and-bound frameworks and mini-bucket heuristics from Bayesian to credal networks. The adaptation is conceptually straightforward, and the heuristic improvements are mostly engineering refinements rather than theoretical advances.\n\n2- The runtime reduction relies on heuristic approximations (mini-buckets, Pareto least upper bounds, and moment matching). These are not guaranteed to always yield efficient pruning or optimal bounds, and no theoretical runtime guarantees are provided.\n\n3- While the reported results are promising, they are mostly demonstrated on synthetic credal networks. Extending the experiments to more practical domains could further validate the effectiveness and real-world applicability of the proposed approach.\n\n4- The claim that the proposed method “solves these tasks exactly in practice” is somewhat ambiguous. In principle, the algorithm can find the true optimal MAP solution if given enough time, since branch-and-bound guarantees exactness through exhaustive search with pruning. However, in practice, the approach relies heavily on heuristic bounds to reduce runtime, meaning that its “exactness” depends on the tightness of those bounds. This makes the statement somewhat overstated and potentially misleading without a clearer discussion of the trade-off between theoretical exactness and practical efficiency.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5HuBsaRiZA", "reviewer": "Reviewer_KRmC", "summary": "This paper presents new depth-first branch-and-bound algorithms for performing exact Maximum a Posteriori (MAP) inference in credal networks—a generalization of Bayesian networks that allow imprecise probabilities.\nThe authors introduce two related inference tasks, maximax and maximin MAP, and develop algorithms that leverage an AND/OR search space to exploit problem decomposition.\nThey also propose a partitioning-based heuristic enhanced with a cost-shifting (moment-matching) strategy to guide the search.\nExtensive experiments on both synthetic and real-world credal networks demonstrate significant efficiency improvements and scalability up to models with over 3000 variables.", "questions": "How sensitive is the algorithm’s performance to the choice of pseudotree structure? Could dynamic variable ordering further enhance pruning efficiency?\n\nFor the maximin MAP task, have you explored any alternative bounding schemes beyond mini-buckets that could yield tighter lower bounds?\n\nCould the proposed AOBB framework be adapted for anytime inference (as hinted in Section 5), and if so, how would heuristic accuracy affect the anytime performance curve?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper makes a meaningful step forward by providing the first exact branch-and-bound framework for MAP inference in credal networks, addressing a clear gap in the literature.\n\nThe proposed AND/OR Branch-and-Bound (AOBB) approach is well-motivated, theoretically grounded, and effectively extends existing frameworks from Bayesian networks to the more general credal setting.\n\nThe introduction of partitioning-based mini-bucket bounds with moment-matching (MBMM) is both technically interesting and empirically effective, improving heuristic accuracy without excessive computational cost.", "weaknesses": "While the paper acknowledges weaker heuristics and higher computational difficulty for the maximin case, the discussion could better analyze why this occurs and suggest concrete mitigation strategies.\n\nThe theoretical complexity results are concise but could benefit from a more intuitive discussion of practical bottlenecks—especially regarding heuristic pre-compilation and space trade-offs.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QOrcRW2n7i", "reviewer": "Reviewer_jvi6", "summary": "The authors propose a new way of exactly deriving versions of the MAP estimate for credal networks, a generalization of Bayesian networks to sets of probabilities. They provide experimental evidence testifying the effectiveness of their method.", "questions": "See weaknesses.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well written, well motivated, it solves an open problem, and it does so exactly. The experiments show that the proposed method is indeed effective.", "weaknesses": "This is a strong paper, with only two minor -- almost cosmetic -- weaknesses, and it deserves to be accepted.\n\n(i) There are a few typos, e.g. in Line 2, it should be \"Instead of precise [...]\"; there are two parentheses in the second line of section 2, so it is displayed $P_i = P(X_i | \\Pi_i))$\n\n(ii) The importance of causal inference in general, and credal networks in particular, for the field of Imprecise Probabilistic Machine Learning could be briefly mentioned in the related work section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)