Abductive Reasoning in Logical Credal Networks

Authors: radu  marinescu
junkyu  lee
debarun  bhattacharjya
fabio  cozman
alexander  gray
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 10:41:49

Abstract: Logical Credal Networks or LCNs were recently introduced as a powerful probabilistic logic framework for representing and reasoning with imprecise knowledge. Unlike many existing formalisms, LCNs have the ability to represent cycles and allow specifying marginal and conditional probability bounds on logic formulae which may be important in many realistic scenarios. Previous work on LCNs has focused exclusively on marginal inference, namely computing posterior lower and upper probability bounds on a query formula. In this paper, we explore abductive reasoning tasks such as solving MAP and Marginal MAP queries in LCNs given some evidence. We first formally define the MAP and Marginal MAP tasks for LCNs and subsequently show how to solve these tasks exactly using search-based approaches. We then propose several approximate schemes that allow us to scale MAP and Marginal MAP inference to larger problem instances. An extensive empirical evaluation demonstrates the effectiveness of our algorithms on both random LCN instances as well as LCNs derived from more realistic use-cases.

Main paper: 
 introduction: 
 Probabilistic logic which combines probability and logic in a principled manner has emerged over the past decades as a unified representational and reasoning framework capable of dealing effectively with complex real-world applications that require efficient handling of uncertainty and compact representations of domain expert knowledge [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] . Logical Credal Networks or LCNs [11] were introduced recently as a probabilistic logic designed for representing and reasoning with imprecise knowledge. Unlike many existing probabilistic logics, LCNs have the ability to represent cycles (e.g., feedback loops) as well as allow specifying marginal and conditional probability bounds on logic formulae which may be important in many realistic usecases.Up until now, the work on LCNs has focused exclusively on marginal inference, i.e. efficiently computing posterior lower and upper probability bounds on a query formula. However, abductive reasoning tasks such as explaining the evidence observed in an LCN are equally important in many real-world applications. In probabilistic graphical models, these tasks are commonly known as MAP and Marginal MAP (MMAP) inference and have received extensive attention over the past decades [12, 13] . They are typically tackled efficiently with dynamic programming (e.g., variable elimination) or heuristic search (e.g., depth-first branch and bound) based algorithms [13, 14, 15, 16] .Contribution. In this paper, we consider solving MAP and Marginal MAP inference queries in LCNs. Unlike in graphical models, an LCN encodes a set of probability distributions over its interpretations. Therefore, a complete or a partial explanation of the evidence which represents a complete or a partial truth assignment to the LCN's propositions may correspond to more than one distribution. Our work builds on very recent work on Marginal MAP inference for credal networks, a class of probabilistic graphical models that allow reasoning with imprecise probabilities [17] . We formally introduce the MAP and Marginal MAP tasks for LCNs as finding a complete or a partial truth assignment to the LCN's propositions with maximum lower (respectively, upper) probability, given some evidence in the LCN. We show how to evaluate such MAP assignments using exact marginal inference for LCNs and, subsequently, propose several search schemes based on depth-first search, limited discrepancy search and simulated annealing to solve these tasks in practice. We then extend a recent message-passing scheme for approximate marginal inference in LCNs [18] to handle effectively the MAP and MMAP inference tasks in LCNs as well as adapt the limited discrepancy search and simulated annealing methods to use an approximate evaluation of the MAP assignments during search. We experiment and evaluate our proposed exact and approximate algorithms on several classes of LCNs including random as well as more realistic LCN instances. Our results show that the search methods based on exact evaluation of the MAP assignments are limited to solving small size problems in practice, while the approximate message-passing scheme and, to some extent, the approximate search-based methods can scale to much larger problem instances. This is important because it allows us to tackle practical problems involving hundreds and possibly many thousands of propositions. The supplementary material includes additional details and experiments. 
background: 
 We provide next a brief overview of basic concepts about LCNs and marginal inference in these models. Throughout the paper we will use the following notations. Logical propositions are denoted by uppercase letters (e.g., A, B, C, ...) while for sets of propositions we use boldfaced uppercase letters (e.g., A, B, C, ...). Truth assignments to propositions (i.e., literals) are denoted by either lowercase or uppercase letters, namely we use a or A to indicate that proposition A holds true, and ¬a or ¬A if A is false. Sets of literals are denoted by boldfaced lowercase letters (e.g., a, b, c, ...).A Logical Credal Network (LCN) [11] is defined by a tuple L = ⟨A, C⟩, where A = {A 1 , . . . , A n } is a set of propositions (or atoms), and C is a set of probability labeled sentences (or constraints) having the following two forms:EQUATIONHere, ϕ and φ are arbitrary propositional logic formulae1 involving propositions in A and logical connectives such as negation, disjunction and conjunction, and 0 ≤ α ≤ β ≤ 1 are lower and upper probability bounds, respectively.An LCN is associated with primal graph which is a directed graph G containing formula nodes and proposition nodes, as well as directed edges from each proposition node in a formula ϕ to the formula node representing ϕ (for type 1 sentences), and directed edges from each of the proposition nodes in φ to φ, a directed edge from φ to ϕ, and bi-directed edges from ϕ to the proposition nodes in ϕ, respectively (for type 2 sentences) [11] . A parent of a proposition A in G is a proposition B such that there is a directed path in G from B to A in which all intermediate nodes are formulae. A descendant of a proposition A in G is a proposition B such that there is a directed path in G from A to B in which no intermediate node is a parent of A [11] .An LCN is endowed with a Local Markov Condition (LMC) where a proposition node A is independent, given its parents, of all proposition nodes that are not A itself nor descendants of A nor parents of A [11] . Therefore, an LCN represents a set of probability distributions over all interpretations of its formulae that satisfy the constraints represented by the type (1) and ( 2) sentences as well as the constraints induced by the independence relations given by the local Markov condition [11] . Figure 1b shows the primal graph where the formula and proposition nodes are displayed as rectangles and shaded circles, respectively.EQUATIONEQUATIONEQUATIONEQUATIONGiven an LCN L with n propositions, the marginal inference task is to compute lower and upper bounds on the posterior probability P (ψ) of a query formula ψ, which we denote by P (ψ) and P (ψ), respectively. This is achieved by solving a non-linear program given by Equations ( 3)-( 8) and defined by a set of non-negative real-valued variables representing the probabilities of L's interpretations, a set of linear constraints derived from L's sentences, a set of non-linear constraints corresponding to the independence assumptions given by the local Markov condition, and a linear objective function encoding the query P (ψ) which is minimized and maximized to yield the desired bounds. More specifically, let ⃗ p = (p 1 , . . . , p m ) be the vector of real-valued variables representing the probabilities of L's interpretations, where m = 2 n , and let ⃗ I ϕ = (a ϕ 1 , . . . , a ϕ m ) be a binary vector, called an indicator vector, such that a ϕ i is 1 if formula ϕ is true in the i-th interpretation and 0 otherwise. Since the probability of a formula ϕ is the sum of the probabilities of the interpretations in which ϕ is true, we can write P (ϕ) as ⃗ I ϕ ⊙ ⃗ p where ⊙ is the dot-product of two vectors. Therefore, Equations ( 3) and (4) ensure that ⃗ p is a valid probability distribution, Equations ( 5) and ( 6) encode the type (1) and (2) sentences in L while Equation 7 encodes the conditional independencies of the form P (X j |S j , T j ) = P (X j |S j ), where X j is a proposition, S j = {S j1 , . . . , S jk } and T j = {T j1 , . . . , T jl } are X j 's parents and non-descendants in the primal graph of L, ⃗ I ϕ and ⃗ I ϕ∧φ are the indicator vectors for formulae ϕ and ϕ ∧ φ involved in L's sentences, and ⃗ I a , ⃗ I b , ⃗ I c and ⃗ I d are the indicator vectors corresponding to the formulae a = (x j ∧ s j1 ∧ • • • ∧ s jk ∧ t j1 ∧ • • • ∧ t jl ), b = (s j1 ∧ • • • ∧ s jk ), c = (x j ∧ s j1 ∧ • • • ∧ s jk ), and d = (s j1 ∧ • • • ∧ s jk ∧ t j1 ∧ • • • ∧ t jl ), respectively (see also [11] for more details). 
map and marginal map inference in lcns: 
 Maximum A Posteriori (MAP) and Marginal MAP (MMAP) inference are well known abductive reasoning tasks in probabilistic graphical models such as Bayesian networks and Markov networks [12, 13, 14, 15, 16] . Specifically, the MAP task calls for finding a complete assignment to all variables having maximum probability, given the evidence. Marginal MAP generalizes MAP and looks for a partial variable assignment that has maximum marginal probability, given the evidence. MAP and MMAP inference tasks appear in many real-world applications such as diagnosis, abduction and explanation and are typically tackled with dynamic programming (e.g., variable elimination) or heuristic search (e.g., depth-first branch and bound) based algorithms [13, 14, 15, 16] .In this section, we present our novel approach for solving the MAP and Marginal MAP inference tasks in Logical Credal Networks. Unlike in graphical models, a (partial) variable assignment (or interpretation) in an LCN may correspond to more than one distribution. Therefore, we begin by formally defining two MAP and MMAP inference tasks for LCNs, called maximin MAP (resp. maximin MMAP) and maximax MAP (resp. maximax MMAP). Subsequently, we develop several exact and approximation schemes for solving these tasks efficiently in practice.Let L = ⟨A, C⟩ be an LCN with n propositions and let E = {E 1 , . . . , E k } ⊆ A be a subset of k propositions, called evidence, for which the truth values e = {e 1 , . . . , e k } are known. Let Y = {Y 1 , . . . , Y m } ⊆ A \ E be a subset of m propositions called MAP propositions. A truth assignment to Y is is called a MAP assignment and is denoted by y = {y 1 , . . . , y m }, respectively. Clearly, if Y = A \ E (i.e., m = n -k) then we have a MAP task, otherwise we have a MMAP task (i.e., m < n -k). The maximin and maximax MAP/MMAP tasks are defined as follows:Definition 1 (maximin). Given an LCN L with n propositions, evidence e, and MAP propositions Y, the maximin MAP (or maximin MMAP if m < n -k) task is finding a truth assignment y * to Y having maximum lower probability, given evidence e, namely:EQUATIONwhere Ω(Y) is the set of all truth assignments to the MAP propositions, and ψ y∧e = y 1 ∧ • • • ∧ y m ∧ e 1 ∧ • • • ∧ e k isEQUATIONwhere Ω(Y) is the set of all truth assignments to the MAP propositions, andψ y∧e = y 1 ∧ • • • ∧ y m ∧ e 1 ∧ • • • ∧ e kis the conjunction of the literals in y and e, respectively.We present next three search-based schemes for solving the MAP and MMAP tasks in LCNs. These methods employ different search strategies for exploring the search space defined by the MAP propositions while evaluating exactly each complete or partial MAP assignment.Exact Evaluation of a MAP Assignment. Clearly, computing the lower and upper probabilities P (ψ y∧e ) and P (ψ y∧e ) of a MAP assignment y given evidence e can be done easily by minimizing and, respectively maximizing the non-linear program defined by Equations ( 3)-( 8), where the query formula is the conjunction of positive or negative literals in y and e, namelyψ y∧e = y 1 ∧ • • • ∧ y m ∧ e 1 ∧ • • • ∧ e k .Therefore, evaluating a MAP assignment in case of both MAP and Marginal MAP inference in LCNs is quite difficult as it involves solving a maginal inference problem for LCNs which is know to be NP-hard [11] . This is in contrast with graphical models where, at least for MAP inference, the evaluation of a MAP assignment is linear in the number of variables [13] .Example 2. For illustration, consider the LCN example from Figure 1 and assume that we have evidence e = {x, ¬s}, namely a patient has a positive X-Ray result (X = x) and is not smoking (S = ¬s). The MAP propositions in this case are Y = {B, C, D} and the MAP assignment y = (b, ¬c, ¬d) corresponds to the query formula ψ y∧e = b ∧ ¬c ∧ ¬d ∧ x ∧ ¬s. The lower and upper probabilities P (ψ y∧e ) and P (ψ y∧e ) of the MAP assignment are 9.9e-09 and 0.1, respectively. for all values y ∈ {y i , ¬y i } do for all values y ∈ {y i , ¬y i } do17: if y[i] == y then 18: z ← SEARCH(y, Y, i + 1, θ) 19: else 20: y ′ ← y; y ′ [i] ← y 21: z ← SEARCH(y ′ , Y, i + 1, θ -1) 22:return z Depth-First Search. Our first approach for solving the MAP and MMAP tasks, called DFS, is described by Algorithm 1. It takes as input an LCN L = ⟨A, C⟩, evidence E = e and a set of MAP propositions Y ⊆ A \ E and outputs the optimal MAP assignment y * . The method conducts a depth-first search over the space of partial assignments to the MAP propositions, and, for each complete MAP assignment y computes its score as the exact lower probability P (ψ y∧e ) for maximin tasks, and respectively, the upper probability P (ψ y∧e ) for maximax tasks, given the evidence e. This way, the optimal solution y * corresponds to the MAP assignment with the highest score.Theorem 1 (complexity). Given an LCN L = ⟨A, C⟩ with n propositions, evidence E = e and MAP propositions Y ⊆ A \ E, algorithm DFS is sound and complete. The time and space complexity of the algorithm is O(2 m+2 n ) and O(2 n ), respectively, where m is the number of MAP propositions.Example 3. Consider again the LCN from Figure 1 with evidence e = {x, ¬s}. In this case, the exact maximin MAP assignment found by algorithm DFS is y * = {¬b, c, d} with value 9.99e-09, while the exact maximax MAP assignment is y * = {¬b, ¬c, d} with value 0.7, respectively. Limited Discrepancy Search. Our second approach for MAP and MMAP inference in LCNs uses Limited Discrepancy Search (LDS) [19, 20] to explore the search space and is described by Algorithm 2. Specifically, LDS is a depth-first search strategy that searches for new solutions by iteratively increasing the number of discrepancy values, where a discrepancy value indicates the maximum number of allowed variable-value assignment changes to an initial solution [19] . Function SEARCH (lines 7-22) performs the actual exploration of the search space limited by discrepancy θ. If the selected truth value y ∈ {y i , ¬y i } is different from the one corresponding to proposition Y i ∈ Y at position i in the assignment y, θ is decremented to reduce the number of changes allowed to the remaining MAP propositions. Otherwise, the truth value for proposition Y i remains unchanged and the θ value is preserved. As before, complete MAP assignments are evaluated exactly (lines 9-12) and the best solution found so far is maintained (lines 13-14). Simulated Annealing. The third approach for solving MAP and MMAP tasks in LCNs is described by Algorithm 3 and employs a form of stochastic local search known as Simulated Annealing (SA) [21] to explore the search space defined by the MAP propositions. The algorithm starts from an initial guess y as a truth assignment to the MAP propositions Y, and iteratively tries to improve it by moving to a better neighbor y ′ that has a higher score. A neighbor y ′ of y is defined as a new assignment y ′ which results from changing the truth value of a single proposition Y in Y. At each step, the transition from the current state y to a neighboring state y ′ is decided probabilistically using an acceptance probability function P (y ′ , y, T ) that depends on the scores of the two states as well as a global time-varying parameter T called temperature which is decreased using a cooling schedule σ < 1 [21] . We chose P (y ′ , y, T ) = e ∆ T , where ∆ = log score(y ′ ) -log score(y). Theorem 3 (complexity). Given an LCN L = ⟨A, C⟩ with n propositions, evidence E = e and MAP propositions Y ⊆ A \ E, the time and space complexity of algorithmSA is O(N • M • 2 2 n ) and O(2 n ),respectively, where N is the number of iterations and M is the number of flips per iterations.The main bottleneck in the proposed search algorithms is the exact evaluation of the MAP assignments which is computationally very expensive [11] . This limits the applicability of these methods to relatively small LCNs. Therefore, in order to be able to tackle larger LCNs, we extend a recent message-passing approximation scheme for marginal inference in LCNs [18] to solve the MAP and MMAP tasks in LCNs. Subsequently, we also adapt the limited discrepancy search and simulated annealing methods to use an approximate evaluation of the MAP assignments during search. Algorithm 4 describes our message-passing based approximation scheme for MAP and MMAP inference in LCNs which we denote hereafter by AMAP. We build upon a recent scheme for approximate marginal inference in LCNs, called ARIEL [18] , which propagates messages along the edges of a factor graph associated with the input LCN until convergence. The factor graph F of an LCN L is a bi-partite graph the connects proposition nodes labeled by the propositions in L with factor nodes associated with sentences that involve the same set of propositions [18] . The messages propagated between the nodes of F are intervals representing lower and upper bounds on the marginal probabilities of L's propositions and are computed as follows: the message sent from a proposition to a factor node tightens these bounds based on the incoming messages from the factor nodes connected to it; the message sent from a factor to a proposition node computes new bounds by solving a local non-linear program defined by the factor's sentences and the constraints encoding the assumption that the factor's propositions are independent of each other and the marginal probabilities of the factor's propositions are within the bounds given by the incoming proposition-to-factor messages (see also [18] for more details). Upon convergence, the maximin MAP assignment y * can be obtained as follows: for each MAP proposition Y ∈ Y we compute the tightest lower probability bound P (y) by maximizing the lower bound of all incoming factor-to-proposition messages to Y , and, subsequently, select y as the most likely value assignment to Y if P (y) > P (¬y) and ¬y otherwise (for the maximax tasks we use the upper probability bounds P (y) and P (¬y), respectively).Theorem 4 (complexity). Given an LCN L = ⟨A, C⟩ with n propositions, evidence E = e and MAP propositions Y ⊆ A \ E, the time and space complexity of algorithmAMAP is O(N • M • 2 2 r ) and O(2 r), where N is the number of iterations, M bounds the number of factor-to-node messages per iteration and r bounds the number of propositions in the factor nodes, respectively.The main assumption behind algorithm AMAP is that all MAP propositions are independent of each other and therefore the solution y * returned by AMAP is likely to correspond to a local maxima. One way to escape such a local optima and obtain a potentially better solution is to employ a search scheme based on either limited discrepancy search or simulated annealing that continues the exploration of the search space starting from y * . However, in order to scale to larger LCNs, we would like the search schemes to rely on an approximate rather than an exact evaluation of the MAP assignments.Approximate Evaluation of a MAP Assignment. Estimating the lower and upper probabilities of a MAP assignment y can be done by approximate marginal inference on an augmented LCN as follows. Let L = ⟨A, C⟩ be the input LCN and let y = (y 1 , . . . , y m ) be a MAP assignment to propositions Y = {Y 1 , . . . , Y m } (for simplicity, we include the evidence e in y). The augmented LCN L ′ = ⟨A ′ , C ′ ⟩ is constructed by adding a set of auxiliary propositions W = {W 1 , . . . , W m }, one for each MAP proposition, and additional constraints of the following two forms: P (W 1 |Y 1 ) and P (W j |W j-1 ∧Y j ), for all 2 ≤ j ≤ m, such that P (w 1 |y 1 ) = 1, P (w 1 |¬y 1 ) = 0, P (w j |w j-1 ∧y j ) = 1, P (w j |w j-1 ∧ ¬y j ) = 0, P (w j |¬w j-1 ∧ y j ) = 0 and P (w j |¬w j-1 ∧ ¬y j ) = 0, respectively. Then, we can estimate P (ψ y ) and P (ψ y ), where ψ y = y 1 ∧ • • • ∧ y m , by computing the posterior marginals P (w m ) and P (w m ) in the augmented LCN L ′ using the method from [18] .Limited Discrepancy Search and Simulated Annealing. Our approximate LDS and SA based algorithms denoted by ALDS and ASA can be obtained from Algorithms 2 and 3 by replacing the score(y) function with the approximate MAP evaluation scheme described above. These algorithms can start the search either from a random MAP assignment or from the solution found by algorithm AMAP. Finally, the time complexity of algorithms ALDS and ASA can be bounded by O(2 m+2 r ) and O(N • M • 22 r ), respectively, where m is the number of MAP propositions, N is the number of iterations used by ASA, M is the maximum number of flips per iteration, and r bounds the number of propositions in the factor nodes of the factor graph associated with the input LCN [18] . 
experiments: 
 In this section, we empirically evaluate the proposed exact and approximate schemes for MAP and MMAP inference in LCNs. All competing algorithms were implemented 2 in Python 3.10 and used the ipopt 3.14 solver [22] with default settings to handle the non-linear constraint programs. We ran all experiments on a 3.0GHz Intel Core processor with 128GB of RAM. Random LCNs. We generated three classes of random LCNs with n propositions {X 1 , . . . X n } and sentences of the following types: (a) l ≤ P (x i ) ≤ u, (b) l ≤ P (x i |x j ) ≤ u, i ̸ = j and (c)l ≤ P (x i |X j ∧ X k ) ≤ u, i ̸ = j ̸ = k, such that the corresponding primal graph is a polytree, a dag or a random graph. The type (c) sentences were generated for all truth values of propositions X j and X k , namely P (x i |x j ), P (x i |¬x j ), P (x i |x j ∧ x k ), P (x i |x j ∧ ¬x k ), P (x i |¬x j ∧ x k ) and P (x i |¬x j ∧ ¬x k ), respectively. The probability bounds l and u were selected uniformly at random between 0 and 1 such that u -l ≤ 0.6, and we ensured that all instances with n ≤ 10 were consistent.Table 1 summarizes the results obtained for maximax MAP queries on the random LCNs. For each problem class we consider both smaller (5 ≤ n ≤ 10) and larger (30 ≤ n ≤ 70) scale instances, respectively. We report the average CPU time in seconds and number of problem instance solved (out of 10) for each problem size. A '-' indicates that the respective algorithm exceeded the 2 hour time limit. The maximum discrepancy value use by algorithms LDS and ALDS was set to δ = 3, while algorithms SA and ASA used up to 30 flips over a single iteration. We can see that the algorithms using exact MAP assignment evaluations (i.e., DFS, LDS and SA) are limited to small scale problem instances with up to 8 propositions and they run out of time on the larger instances. This is caused by the prohibitively large computational overhead associated with the exact evaluation of the MAP assignments during search. In contrast, the approximate search algorithms ALDS and specially ASA can scale to much larger problem instances due to the less expensive approximate MAP assignment evaluations. AMAP is the best performing algorithm in terms of running time and number of problems solved for all reported problem sizes. However, since the solution found by AMAP is only a local maxima, in Figure 2 we report on the solution quality found by algorithms AMAP, ALDS and ASA on LCN instances of size 10. Specifically, we show the number of wins as the number of times (out of 10) each algorithm found the best solution. In this case, algorithms ALDS and ASA were initialized with the MAP assignment found by AMAP. We can see that almost always the search-based approaches ALDS and ASA are able to find better solutions than AMAP. This is important in practice, particularly on larger scale problems where we can use AMAP to find a MAP solution quickly, and subsequently refine that solution using a search-based algorithm like ALDS or ASA if the time budget allows it. Finally, in Figure 3 we show the impact of the maximum discrepancy value δ on the running time of algorithm ALDS(δ). It is easy to see that as the discrepancy value δ increases, the search space explored by ALDS(δ) becomes larger, and therefore its corresponding running time increases as well.Realistic LCNs. We experimented with a set of more realistic LCNs which were first introduced in [18] . These LCNs were derived from real-world Bayesian networks [23] and contain up to 10 propositions as well as up to 24 sentences of the form l ≤ P (x i ) ≤ u and l ≤ P (x i |π i ) ≤ u, respectively, where x i is the positive literal of proposition X i and π i = y i1 ∧ • • • ∧ y ik is the conjunction of the positive or negative literals corresponding to a particular configuration of the parents {Y i1 , . . . Y ik } of X i in the Bayesian network. The specification of these LCNs is included in the supplementary material. Table 2 reports the results obtained on 10 LCN instances for the maximax MMAP task with 4 MAP propositions selected randomly. As before, algorithms DFS, LDS(3) and SA which rely on exact evaluations of the MAP assignments during search can only solve the smallest problem instances within the 2 hour time limit. In contrast, algorithms ALDS(3) and ASA solve all problem instances due to a much reduced overhead associated with the approximate MAP assignment evaluations. In this case, the search spaces explored by ALDS(3) and ASA are approximately the same in size and therefore the corresponding running times are comparable. AMAP is the fastest algorithm in this case as well.Application to Factuality in Large Language Models. We consider an application of MMAP inference in LCNs to assess the factuality of the output A generated by a large language model (LLM) in response to a user query Q with respect to an external source of knowledge C that may contain contradicting factual information (e.g., Wikipedia) [24] . The goal is to compute a factuality score for response A, denoted by f C (A), in the context of the information from C. In the following, we assume that A can be decomposed into a set of n atomic facts (or just atoms) A = {A 1 , . . . , A n } (e.g., one way to do that is to split A into sentences) and, for each atom A i , up to k relevant passages {C i1 , . . . , C ik } called contexts can be retrieved from C. A natural language inference (NLI) classifier such as SBERT [25] can be used to infer the entailment, contradiction and neutrality relationships between the texts corresponding to the atoms and contexts together with their corresponding probabilities (or scores). Specifically, we consider relationships between an atom and a context r(A i , C ij ), and between two contexts r(C ij , C pq ), respectively, where r ∈ {entailment, contradiction}. We define an LCN L containing n + n × k propositions for each of the atoms and contexts, and two types of sentences corresponding to the entailment and contradiction relationships as follows:l ≤ P (Y |X) ≤ u if X entails Y , and l ≤ P (¬Y |X) ≤ u if X contradicts Y, where X and Y are the propositions corresponding to a context and an atom, or to two different contexts, respectively. The lower and upper bounds l and u can be calculated easily from the probabilities obtained by running multiple NLI classifiers. Finally, the factuality score f C (A) is the proportion of true atoms in the MAP assignment obtained by solving a maximax MMAP task over L where the MAP propositions are those corresponding to A's atoms.Table 3 displays the results obtained on randomly generated factuality LCNs. More specifically, for each reported problem size n ∈ {2, 4, 6, 10, 20, 50, 100}, we generated 10 random instances with n atoms and k = 2 contexts per atom such that 10% of all possible pairwise relationships between atoms and contexts were selected to be either entailment or contradiction with probability 0.5 while the remaining relationships were labeled as neutral and thus ignored. The lower and upper probability bounds l and u in the corresponding LCN sentences were also generated randomly between 0 and 1 such that u -l ≤ 0.6. In this case, the maximum discrepancy value was set to 2 and simulated annealing was allowed a single iteration and 30 flips. We observe again that algorithms DFS, LDS (2) and SA can only solve the smallest instances due to large computational overhead associated with exact evaluation of the MAP assignments. In contrast, algorithms ALDS(2) and ASA which rely on less expensive approximate evaluations of the MAP assignments can scale to larger problems with up to 20 atoms. Algorithm AMAP outperforms its competitors and solves all problem instances.In summary, our empirical evaluation showed that the exact search-based MAP/MMAP algorithms are limited to solving relatively small problem instances. In contrast, the approximate MAP/MMAP schemes based on either message-passing or search can scale to much larger LCN instances. 
conclusions: 
 In this paper, we address abductive reasoning tasks such as generating MAP and Marginal MAP (MMAP) explanations in Logical Credal Networks (LCNs), a recently introduced probabilistic logic framework for reasoning with imprecise knowledge. Since an LCN encodes a set of distributions over its interpretations, a complete or partial explanation of the evidence (i.e., a MAP assignment) may correspond to more than one distribution. Therefore, we define the maximin/maximax MAP and MMAP tasks for LCNs as finding complete or partial MAP assignments that have maximum lower/upper probability given the evidence. We propose several search algorithms that combine depthfirst search, limited-discrepancy search or simulated annealing with exact evaluations of the MAP assignments using marginal inference for LCNs. We also develop an approximate message-passing scheme as well as extend limited discrepancy search and simulated annealing to use an approximate evaluation of the MAP assignments during search. Our experiments with random LCNs and LCNs derived from realistic use-cases demonstrate conclusively that the search methods based on exact evaluations of the MAP assignments are limited to small size problems, while the approximation schemes can scale to much larger problems. For future work we plan to investigate more advanced depth-first branch-and-bound and best-first search techniques. However, these kinds of methods require developing novel heuristic bounding schemes to guide the search more effectively [16] .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 a 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 it 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 to 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 a 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 submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. , with an open-source dataset or 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.In the case of closed-source models, it 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 to have some path to reproducing or verifying the results.Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer: [Yes] Justification: Section 4 and supplementary material Guidelines:• The answer NA means that paper does not include experiments requiring code. • At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable). • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
experimental setting/details: 
 Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes]Justification: Section 4 and the supplementary material Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [Yes]Justification: Section 4 and the supplementary material Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence 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 are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run 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). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. 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 or 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. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA] Justification:Answer: [NA] Justification: Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: The original definition of LCNs allows for relational structures and first-order logic formulae, but their semantics is obtained by grounding on finite domains thus yieling a propositional LCN[11].The open-source implementation of LCNs is available at: https://github.com/IBM/LCN 


Decision: In the family of probabilistic graphical models, logical credal networks (LCNs) have recently garnered attention for their ability to represent imprecise probabilities in a compact and intuitive way. Up to now, there has been limited exploration of queries for this model class. This paper aims to broaden the practical applications of LCNs by focusing on the widely used maximum a posteriori (MAP) and marginal MAP queries. After providing an overview of LCNs and their queries, the authors propose exact and approximate algorithms for MAP and marginal MAP inference. These algorithms are evaluated using both synthetic and real-world benchmarks.

All reviews for this paper are positive, ranging from borderline accept to accept. As acknowledged by reviewers, this paper provides the first approach to handle abductive reasoning (with MAP and marginal MAP) on logical credal networks. As the runtime (and space) complexity of exact inference algorithms is prohibitive, an important contribution of this paper is to focus on the empirical analysis of various approximation algorithms, including message-passing, limited discrepancy search, and simulated annealing. In summary, this paper paves the way for future research on abductive reasoning with imprecise graphical models.

While the main concerns of reviewers have been addressed in the fruitful discussions with authors, I highly recommend providing a light revision of the current manuscript to consider all reviewers' comments. Notably:
* Applicability: as several reviewers were skeptical about the practical interest of LCNs, the insightful global response provided by the authors should be incorporated into the paper.
* Complexity: the paper should include a discussion on the computational complexity of MAP (and marginal MAP) for LCNs in order to justify the use of approximation algorithms. I would suggest providing an NP^PP hardness result (even if, as suspected by the authors, the complexity class is even higher). By first taking a class of undirected or directed graphical models for which MAP is NP^PP hard and then explaining that this class can be transformed (in polynomial time and space) into an LCN, the hardness result should follow.
* Presentation: The paper, in its current state, is targeted to specialists in probabilistic graphical models. The too short introduction should be revised to motivate this study for a larger NeurIPS audience. Furthermore, in order to deal with the density of the paper, the authors’ suggestion to provide additional examples and use additional space would be welcome. Finally, even if the state-of-the-art methods for (M)MAP inference are dedicated to probabilistic models and cannot be trivially extended to credal models, this should be emphasized at the beginning of the experimental section.

Reviews: review: paper_summary: paper_summary: Logical Credal Networks (LCNs) are a probabilistic logic framework designed for representing and reasoning with imprecise knowledge. While previous research on LCNs has focused on marginal inference, there has been a lack of exploration in abductive reasoning within this context. This paper addresses this gap by investigating abductive reasoning in LCNs using Maximum A Posteriori (MAP) and Marginal MAP (MMAP) queries. To solve MAP and MMAP tasks, the authors propose techniques based on Depth-First Search (DFS), Limited Discrepancy Search (LDS), and Simulated Annealing (SA). Additionally, to improve time complexity, they introduce a method that utilizes a message-passing approximation scheme, allowing for more efficient and scalable solutions.
strength_weakness: strength_weakness: Comparison with prior work & Experiments
- Mention how you build upon from the previous works by Radu Marinescu et al. The introduction mentions that existing approaches use heuristic algorithms or DP algorithms for MAP and MMAP inference, and this paper does not employ a significantly different method.
- If this is a follow-up to the aforementioned research, wouldn't it have been better to demonstrate the performance of the previous research with the addition of Message Passing Approximation? The current paper compares the method added to LDS and SA. The advantages of using SA and LDS compared to previous research are not clearly demonstrated.
- While I agree that there may not be existing studies that have introduced LCNs, there are certainly prior studies that have tackled MAP and Marginal MAP tasks. It would be beneficial to include baselines comparing the performance of the proposed algorithms with those of existing studies. Without such baselines, the current experimental results only allow for comparisons among the proposed algorithms themselves, making it difficult to ascertain whether these algorithms are superior to those from other research. The absence of baseline comparisons hampers a complete understanding of the contribution of the proposed methods.
- A comparison and introduction of MAP estimation methods in Credal Networks (CN) and Bayesian Networks (BN) would have been beneficial to understand the practical advantages over these existing methods. (Probably author thought this was the scope of the prior work - Logical Credal Network)
- It is unclear whether ALDS and ASA are needed instead of AMAP. Experimental results show that AMAP consistently outperforms in terms of CPU time(in Tables 1, 2, 3), and the auxiliary measure of solved problem instances(in Tables 1, 3) is always 10/10 with AMAP. These results raise questions about the necessity of ALDS and ASA. Although the paper attempts to address these concerns with Figure 2, but it demonstrates that sufficient problem-solving can be achieved without the optimal LCN, suggesting that the approximation methods of ALDS and ASA may be inefficient.

Presentation
- There is insufficient evidence for the statement in LINE 24: "Logical Credal Networks (LCNs) have focused exclusively on marginal inference, i.e., efficiently computing posterior lower and upper probability bounds on a query formula."
- The main contribution seems to be Algorithm 4, but its emphasis is not different from Algorithms 1-3, which perform inference through DFS, making it difficult to identify the core of the paper.
- Line 36: Is the term "probability bound" more accurate than "imprecise probability."?
- Section 3 lack sufficient explanation of the proposed methodology, making it difficult for readers to fully understand. Additionally, the paper lacks a clear analysis of the time complexity and space complexity of the algorithms, which is crucial for evaluating their efficiency.
questions: questions: - Could you provide more detailed descriptions of the algorithm implementation? Additionally, could you include a clear analysis of the time and space complexity of the algorithms to help evaluate their efficiency? I recommend this paper should answer these questions in the Appendix. (Could be in the supplementary material)
- Could you include baselines comparing the performance of the proposed algorithms with those of existing studies? Without such baselines, it is challenging to determine whether your algorithms are superior to existing research.
- Could you clarify the specific advantages of ALDS and ASA over AMAP, and provide additional justification for their inclusion? How do these algorithms contribute to this paper?
limitations: limitations: - As the authors mentioned, the method still relies on heuristic approaches for finding MAP, indicating a need for further development. The proposed method is not yet practical for real-world applications without additional improvements, as evidenced by the computational overhead and limited scalability shown in the experiments.
- Arbitrary Setting of Hyperparameter Values: 
   * Size of problem (n): Figure 3 shows a trend where CPU time increases as the discrepancy increases for n = 7. However, Table 1 shows experiments conducted for n = 5, 8, 10, 30, 50, 70 for the same datasets. It is unclear why only Figure 3 uses other values, indicating an arbitrary setting of hyperparameters without a specific criterion. 
   * Discrepancy (delta): Table 1 and Table 2 use a discrepancy value of 3, whereas Table 3 uses a discrepancy value of 2 for the experiments. The rationale behind these hyperparameter settings needs to be clarified. Setting discrepancy values without a consistent criterion undermines the study's consistency and can confuse interpreting the results. Furthermore, a discrepancy of 2 appears to be an elbow point, suggesting it is an optimal parameter value for ALDS(2). Maybe, results for the large data(n = 30, 50, 70) could have been obtained using ALDS(2).
   * Contexts per atom (k): In Table 3, since k is fixed to 2, you don't have to indicate repeatedly it in the table. Also, it would be better to append the results of experiments with various k.
- Uncertain Contribution: While this paper proposes various algorithms based on LCN, it is questionable whether the introduction of LCN is necessary for solving Marginal MAP. I summarize the points previously mentioned from this perspective. Firstly, in the performance of the approximation algorithms, it is evident that AMAP, which relatively fails to find the optimal LCN, performs better. This result weakens the necessity of LCN to solve the marginal MAP problem. Additionally, it is difficult to prove the superiority of LCN without a theoretical comparison (e.g., time complexity, space complexity) or experimental comparison (i.e., experimental results) between LCN-based algorithms and existing algorithms. To prove the contributions of this paper, it seems necessary to supplement these aspects.
paper_summary: paper_summary: The paper presents an approach for MAP and marginal MAP in logical credal networks using search based algorithms. Compared to PGMs, MAP and marginal MAP is harder in LCNs since a MAP assignment could correspond to one of several distributions and therefore, to even evaluate the MAP, we need to perform marginalization which is a hard task. The exact algorithms are developed using DFS, limited discrepancy search and simulated annealing. However, since these are infeasible in practice, approximate methods are developed based on a marginal inference method for LCNs. The main idea is to compute lower and upper MAP (or marginal MAP) probabilities 

Experiments are performed on synthetic LCNs and those generated from Bayesian nets. Further, an application related to testing LLMs is presented. Specifically, the idea is to connect atoms from the generated text to a source such as wikipedia and compute facility as a the MAP score. Scalability results are shown for the LCNs used in this task for different variants of the proposed methods.
strength_weakness: strength_weakness: In terms of significance of the proposed approaches, the results mainly show scalability of the approximate methods and their ability to find MAP/MMAP solutions. However, the actual application of MAP/MMAP seems missing. For example, in the LLM application the results do not really tell us how useful the MAP/MMAP solution was compared to other methods other than that the MAP/MMAP solution could be found as the LCN becomes larger. In general, I feel the proposed approaches would be much more significant if the results showed that if the proposed solution improved over other approaches that could be used to solve the same problem.
questions: questions: Are there specific use cases where the MAP or MMAP solutions for LCNs can be compared with other competing methods? In general, what would be the advantages of MAP/MMAP queries for LCNs as compared to other probabilistic approaches.
limitations: limitations: Limitations are not explicitly mentioned.
paper_summary: paper_summary: This is a paper about inference on logical credal networks, a class of graphical models that cope with interval-valued probabilistic statements on propositional logic formulae. The novelty of the paper is that it focuses on marginal MAP inference (and hence also MAP as a special case). Exact and approximate algorithms based on search strategies are proposed and empirically tested.
strength_weakness: strength_weakness: LCNs are not very popular models, at least for the moment, and their potential for applications to real problems is not very clear.
Something similar could be said, more specifically, to the need for tools for abductive reasoning in such models.
questions: questions: - The authors do not report results on the hardness of their inference tasks. This is probably obvious, right? Yet, some comments about that would help. It would be also interesting to compare a brute-force wrt the exact methods.
- With credal models, there is a difference between the "conditional" and the "joint" versions of an inference task for the simple reason that the two models are proportional through the probability of the evidence, which is not constant in a credal setup. I believe that the authors consider a "joint" version, but this point should be made clearer.
- I don't understand how the ground-truth values in the experiments are obtained.
- The results show that the topology of the networks seems not to affect the execution time too much. Some comments about that would be valuable, as the situation is very different in other graphical models.
limitations: limitations: -
paper_summary: paper_summary: This paper proposes how to solve MAP and Marginal MAP queries for Logical Credal Networks (LCNs). LCNs are a class of graphical probabilistic logic models with the expressiveness to represent cycles as well as marginal and conditional probability bounds on logical formulae. The authors first present three search algorithms for exactly computing MAP/MMAP bounds on queries to LCNs. Then, because the MAP/MMAP problem for LCNs is NP-Hard, the authors present three approximation methods that offer considerable speedup at only a small cost to accuracy. The supplemental material contains formal proofs and extensive experiment details.
strength_weakness: strength_weakness: My primary critique is on the exposition and motivation.
* It would help to better motivate the strengths of LCNs by providing examples/references of why cycles and marginal+conditional probabilities show up. This would be stronger than claiming "... which may be important in many realistic use cases".
* Having more examples and figures of LCNs would be helpful, especially in Section 2.1.
* Emphasizing the NP-Hardness of MAP/MMAP for LCNs would help better motivate the need for search techniques and approximation algorithms.
* Section 2.2 is a bit dense. Moreover, it appears that Equation (8) is a vector-valued objective, which does not make sense to me. Overall, this section would benefit from a more relaxed exposition pace --- possibly in a future manuscript version.

The experiments would also benefit from having the main takeaways more explicitly stated.
* It would help to have captions that succinctly explain the main points, e.g., for Table 1: that AMAP does very well compared to DFS, LDS(3), and SA.
* It would be useful to supplement Figure 2 with a plot of the optimality gaps of the approximations, rather than simply the "wins".

Others comments:
* At present, it appears that the practical algorithms are restricted to fairly small LCNs.
* Three exact algorithms and three approximation schemes in one paper are quite a lot. It would help the reader to see the author's recommendations and discussions of their various trade-offs.
* The part on "Application to Facuality in Large Language Models" is a bit dense and sudden. If the authors deem it within the scope of the paper, it would help to supplement this with some experiments.

Minor Comments:
* Section 3.2: It would be helpful to explicitly list Algorithm 1, 2, and 3 in the paragraph headers, e.g., "Algorithm 1: Depth-first Search"
* More descriptive names for theorem labels would be helpful, e.g. "Theorem 1 (Complexity of Depth-first Search)"
questions: questions: * The space complexities appear quite extreme. Could the authors please comment on whether this is a fundamental drawback, and if so, how much better might one (in practice) reasonably expect to do?
* Figure 3 in the paper looks different from Figure 6 in the supplemental material. Could the authors please address why this might be the case?


I have saved my harshest critiques for last. I am an outsider to the graphical models community, so please forgive my ignorance. I am willing to revise my assessment if the authors could please expand on the following points that a general ML audience might have:
* Why care about LCNs?
* What are real-world cases of people using LCNs or similar models?
* What's an example of something that LCNs can capture that other graphical models can't?
* In fact, why care about graphical models at all when deep learning is everywhere? (Some comments about explainability + interpretability should be well-received)
* If the existing algorithms for LCNs are so expensive, what would be some "realistic" scenarios for which they're relevant?
limitations: limitations: The authors sufficiently discuss the limitations of their work.
paper_summary: paper_summary: This paper addresses abductive reasoning tasks such as generating MAP and Marginal MAP (MMAP) explanations in Logical Credal Networks (LCNs). Given that LCNs encode sets of distributions over their interpretations, a complete or partial explanation of the evidence may correspond to multiple distributions. Thus, the authors define the maximin/maximax MAP and MMAP tasks for LCNs as finding complete or partial MAP assignments with maximum lower/upper probability given the evidence. They propose several search algorithms that combine depth-first search, limited-discrepancy search, or simulated annealing with exact evaluations of MAP assignments using marginal inference for LCNs. Additionally, they develop an approximate message-passing scheme and extend limited discrepancy search and simulated annealing to use approximate evaluations of MAP assignments during the search. Experiments show that the approximation schemes which they have proposed can scale to much larger problems compared to search methods.
strength_weakness: strength_weakness: The experimental setup is relatively simple, lacking more practical industrial examples and relying more on basic toy experiments. Additionally, there is no comparison with other methods.
questions: questions: 1. In the initial LCN papers, the authors compared LCN with ProbLog and MLN. Can your method be compared with these? For example, ProbLog is a direct derivative of logic programming, which can perform basic reasoning, including deductive reasoning as well as abductive reasoning.
2. In the experiments, different approximate algorithms show significant differences in solving time, despite having almost equivalent time complexity. How can this be explained?
3. In line 80, should it be "less likely"?
limitations: limitations: Yes.

Comments: title: Reply to authors
comment: Thanks for your response. I think the issue of LCNs being able to solve problems better than other statistical relational models is good. I do think that being the first work to add MAP and MMAP (both of which are important tasks in graphical models) to LCNs is a valuable contribution. The technical components seem solid in the work in terms of improving scalability of MAP/MMAP queries in LCNs, but I was still a bit unsure about the quality of the approximation algorithms relative to some other approach, particularly since I think it is hard to have theoretical guarantees on the approximation. That would have made the paper much stronger in terms of the significance I feel. In summary though, I feel this seems like a solid enough work with some weaknesses.
I thank the authors for their comments. All my questions/doubts have been clarified, and I am happy to confirm my positive opinion about that paper.
Thank you for the detailed response. I am still skeptical of LCNs due to their currently limited adoption, but I am warming up to their potential usefulness. I have increased my score.
Thank you for answering my questions.

As another reviewer commented, it would be beneficial to initiate a discussion with the audience on how we can incorporate the idea of symbolic reasoning (LCN) in the era of large neural networks. Potentially, neural networks could provide some unknown LCN sentences that were missed by domain experts, making the overall framework more comprehensive.

As the last reviewer (ZTSx) mentioned, comparing your method with approaches outside of LCN could be helpful to justify that LCN is also practically useful among diverse solutions. Additionally, providing more discussion on the benefits of ALDS/ASA over AMAP would help in the detailed understanding of the methods.

Although I am not an expert in the field, I believe this paper is beneficial in advancing research towards building a System 1+2 engine. I look forward to seeing more contributions in neuro-symbolic abductive reasoning. I will maintain my positive score.

I would like to suggest lowering the entry barrier of this manuscript for audiences who aren't familiar with LCN and MMAP. For instance, including toy examples of MAP and MMAP in medical diagnosis or fault detection could effectively illustrate how these inference tasks are applied in real-world scenarios. While the supplementary material includes LCNs for multiple real-world scenarios, some readers may also require background knowledge on MAP and MMAP. Consider reorganizing the manuscript and supplementary materials to enhance readability.

-----

These are still a few remaining questions, so I would like to ask for some additional clarification.

> Q1. Could you provide more detailed descriptions of the algorithm implementation? Additionally, could you include a clear analysis of the time and space complexity of the algorithms to help evaluate their efficiency? I recommend this paper should answer these questions in the Appendix. (Could be in the supplementary material)

> A1. We included the actual Python implementation of the proposed algorithms in the supplementary material (see the exact_map.py and approx_map.py scripts) and we are currently in the process of open sourcing our code. Theorems 1, 2, 3 and 4 in the main paper provide the time and space complexity bounds of the proposed algorithms. Their proofs are included in the supplementary material.

We feel that an additional explanation in the proof would be beneficial for clarity. For instance, in the proof of Theorems 1, 2, and 3, it is mentioned that the complexity is O(2^2^n) because the LCN has 2^n interpretations, but this point could be elaborated further to ensure a clear understanding. Regarding the proof of Theorem 4, the claim that "the complexity of algorithm AMAP is dominated by the complexity of the factor-to-node messages" could benefit from additional clarification. Specifically, it would be helpful to show the time complexities of the other parts of algorithms to support this claim.

> Q2. Could you include baselines comparing the performance of the proposed algorithms with those of existing studies? Without such baselines, it is challenging to determine whether your algorithms are superior to existing research.

> A2. To the best of our knowledge, our paper provides the first study on MAP and MMAP inference in LCNs and therefore there are no other baseline algorithms to compare with on these two tasks.

We are curious about the practical benefits of using the proposed MAP/MMAP algorithms with LCNs compared to Bayesian networks and Credal Networks. In scenarios where LCNs are expected to be advantageous due to the richer information they encode, it would be helpful to know the extent of these benefits. Additionally, since LCNs use more information, is there a concern regarding potential overfitting?


> Q3. Could you clarify the specific advantages of ALDS and ASA over AMAP, and provide additional justification for their inclusion? How do these algorithms contribute to this paper?

> A3. Algorithms ALDS and ASA could potentially improve the solution found by AMAP. More specifically, the initial solution found by AMAP is most likely a local optimum, but if more time is available then we can use ALDS/ASA to search for a better solution. 
Figure 2 in the main paper is meant to illustrate the benefit of using ALDS/ASA on top of AMAP. In this case, both ALDS and ASA were initialized with the solution found by AMAP and the plot shows how many times ALDS/ASA found a better solution compared with the initial one upon exceeding the time limit. We will expand the discussion in the paper to emphasize the benefits of ALDS/ASA over AMAP.

You mentioned that AMAP is likely to get stuck in local optima, and we would like to understand the reason behind this. Additionally, we are interested in learning more about the specific situations where ALDS and ASA perform better relative to each other. Insight into the conditions under which one algorithm outperforms the other would be valuable.
Thank the authors for their response. I appreciate the clarification, especially regarding the runtime, which has addressed my concerns. However, I still believe that comparing your method with approaches outside of LCN, even if those methods use the most naive or brute-force algorithms, is necessary. Nonetheless, I consider this paper to be solid work and will maintain my current rating.