Model Reconciliation via Cost-Optimal Explanations in Probabilistic Logic Programming
Authors: Yinxu Tang
Stylianos Loukas Vasileiou
Vincent Derkinderen
William Yeoh
Venue: NeurIPS 2025 poster ()
Keywords: model reconciliation
probabilistic logic programming
most probable explanations (MPE)
Primary area: other

Abstract: In human-AI interaction, effective communication relies on aligning the AI agent’s model with the human user’s mental model, a process known as model reconciliation. However, existing model reconciliation approaches predominantly assume deterministic models, overlooking the fact that human knowledge is often uncertain or probabilistic. 
To bridge this gap, we present a probabilistic model reconciliation framework that resolves inconsistencies in MPE outcome probabilities between an agent’s and a user’s models.
Our approach is built on probabilistic logic programming (PLP) using ProbLog, where explanations are generated as cost-optimal model updates that reconcile these probabilistic differences. 
We develop two search algorithms -- a generic baseline and an optimized version.
The latter is guided by theoretical insights and further extended with greedy and weighted variants to enhance scalability and efficiency.
Our approach is validated through a user study on explanation types and computational experiments showing that the optimized version consistently outperforms the generic baseline.

Model Reconciliation via Cost-Optimal Explanations in Probabilistic Logic Programming
Yinxu Tang
Stylianos Loukas Vasileiou New Mexico State University stelios@nmsu.edi
Washington University in St. Louis t. y.yinxu@uust.cc edu
Vincent Derkinderen
William Yeoh
KU Leuven vincen..derinnneeentttueeevvve
Washington University in St. Louis wyeohS
Abstract
In human-AI interaction, effective communication relies aligning the Al agent's model with the human user's mental model, a process known as model reconcilia- tion. However, existing model reconciliation approaches predominantly assume deterministic models, overlooking the fact that human knowledge is often uncertain probabilistic. To bridge this gap. present probabilistic model reconciliation framework that resolves inconsistencies agent's and user's models. Our approach is built probabilistic logic pro- gramming (PLP) using ProbLog, where explanations are generated as cost-optimal model updates that reconcile these probabilistic differences. We develop algorithms generic baseline and an optimized version. The latter is guided by theoretical insights and further extended with greedy and weighted variants enhance scalability and efficiency. Our approach is validated through user study on explanation types and computational experiments showing that the optimized version consistently outperforms the generic baseline.
MPE outcome probabilities between
search
Introduction
In human-Al AI interaction, effective communication relies on aligning the Al agent's model with the human user's mental model, mismatched understandings make the agent's behavior seem inexplicable [T] Model reconciliation offers powerful explainable AI (XAI) approach by adjusting the human's 's model to align with the agent's understanding (2). For instance. in planning, it explains why an agent's s actions are valid its model but not in the human's 's (2). However, existing model reconciliation methods assume deterministic
beliefs, treating them fixed or drawn from of distinct models 3 []. This overlooks the uncertainty and graded beliefs typical of human knowledge. In reality, humans often maintain probabilistic beliefs that reflect degrees of confidence rather than absolute truths. Ignoring this uncertainty can lead to unconvincing or misaligned explanations.
Probabilistic reasoning addresses uncertainty, capturing graded beliefs and uncertain outcomes. Inference methods like most probable explanation (MPE) and maximum a posteriori (MAP) are key: MPE finds the most likely scenario given evidence, while MAP identifies the most probable hypothesis [5]. These methods are widely applied, from Bayesian networks to probabilistic logic models. However, model reconciliation has yet to fully account for probabilistic beliefs. An agent may base decisions on an MPE outcome, while a human might disagree due to different probabilistic assumptions. Bridging this gap of reconciling probabilistic model differences between agent and human remains an open challenge.
Despite this gap, model reconciliation has been extensively explored in logic programming systems. In classical planning and answer set programming (ASP), explanations are generated by modifying
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

logical rules to align beliefs [3 6 Meanwhile, probabilistic logic programming (PLP) frameworks like ProbLog 77] offer a powerful way to handle uncertainty, combining logical rules with probabilistic semantics. PIP supports diverse inference tasks, including MPF, MAP, and marginal probability computation, making it versatile tool for uncertain reasoning. However, while PI.P excels at probabilistic reasoning, its integration with model reconciliation for generating explanations under probabilistic beliefs remains unexplored.
In this paper, we introduce the first probabilistic model reconciliation framework within a PLP setting, leveraging ProbLog for its expressive power. Our approach allows an agent to reconcile differences between its probabilistic model and a human's 's model. The reconciliation is achieved by generating cost-optimal explanations that resolve inconsistencies in MPE outcome probabilities. Our key contributions are as follows:
Probabilistic Model Reconciliation: We define model reconciliation under uncertainty, addressing inconsistencies in MPE outcome probabilities between an agent's 's and a human's Problogg models. Cost-Optimal Explanations: We introduce a cost-based model where explanations are minimal updates that resolve probabilistic differences.
Algorithms and Scalability: We develop two search algorithms a generic baseline and an optimized version. The latter builds on theoretical insights to prune the search space and is further extended to greedy and weighted variants for improved scalability and efficiency. Comprehensive Evaluation: We validate our approach with a user study on explanation costs and computational tests showing the optimized search's 's superior performance.
2 Related Work
Model Reconciliation Problems (MRPs). MRPs have been widely studied in domains like ex- plainable planning and knowledge representation and reasoning (KR). In explainable planning (8] Chakraborti et al. defined it as aligming an agent's 's (planning) model with a human's 's by making mini- mal changes to the human model, using search methods like A to balance explanation completeness and simplicity (2). In KR, Vasileiou et al. introduced a general logic-based MRP framework for classical and hybrid planning problems (9) proposed a hitting-set algorithm to compute minimal sets of formulas that prove a target conclusion for problems beyond planning 4 and later extended this approach to generating personalized explanations [10]. Finally, Nguyen et al. reconciled ASP by identifying minimal rule additions and deletions such that the program yield the same target conclusion 3 (.. Beyond deterministic models, Sreedharan et al. addressed uncertainty about the human's 's model by assuming that the human's 's model is located within space of possible human models maintained by the agent [TT), while Vasileiou et al. assumed that the human model is a probability distribution representing the agent's uncertainty of the actual human model [12).
These methods share common limitation: they either assume user beliefs are deterministic or drawn from a fixed set of models, or do not allow for uncertain agent models. Consequently, these methods cannot reconcile differences when the agent's 's and human's models involve probability distributions over facts, rules, or outcomes. Our work addresses this gap through joint probabilistic framework.
Probabilistic Logic Programming (PLP). PLP integrates probabilistic reasoning with the expressive power of logic programming, enabling the specification of complex probabilistic models. This line of research started with Poole 113. who introduced the first PLP framework by extending the logic programming language Prolog [14], and with Sato [5). whose distribution semantics became the basis for several PLP systems, such as PRISM [6). ICL [17,, ProbLog and LPAD (18). The notion of explanation has been explored by the PLP community [5] where explanations are associated with possible worlds (i.e., truth-value assignments to all atoms in the language). The most prominent task there is that of the MPE, which consists of finding the world with the highest probability given some evidence (20. However, a world does not show the chain of inferences of a given explanandum and it is not minimal by definition, since it usually includes (possibly large) number of probabilistic facts whose truth value is irrelevant for the explanandum. An alternative approach is using the proof of an explanandum as explanation 2211, where proof is (minimal) partial world in which the query is true. In this case, one can casily ensure minimality. but even if the partial world contains no irrelevant facts, it is still not easy determine the chain of inferences behind a given query. Finally, Renken et al. leveraged explanations in PLP as approximation techniques for more efficiently computing weighted model counting problems (22

---

3 Background
We begin by reviewing the fundamental concepts of logic programming and its probabilistic exten- sions, with an emphasis on logical inference.
3.1 Logic Programming
An atom is expression of the form q(t1...., term. A term 4 can be a constant, a variable, or a functor applied to other terms. A literal either an atom or its negation -q(t1..... t.). An expression is said to be ground if it contains variables.
tn.,, where q is predicate of arity and each 4 is
Syntactically, a normal clause program, logic program, a of rules. A rule is an expression of the form h :- bn.....u, bn. where h is atom, referred to as the head of the rule, denoted by hrad(r) h. The body of the rule consists of a conjunction of literals b,, b1,...,bu Das and is denoted by brdy(r)= by.). The symbol ":-' represents logical implication (+)) and the comma
denotes the conjunction (A). Thus, the rule states that h holds whenever all literals in the body are satisfied. If O, meaning the rule has an empty body, the rule is called a fact.
3.2 Probabilistic Logic Programming
Syntax. A Problogg program M consists of a set of probabilistic facts F and a set of logic rules R. Formally, the set of probabilistic facts be written F (2,, Sn. where each fi is a ground fact. A probabilistic fact, written as p; :: Si. assigns a probability p; to the fact fi, i.e., P(f.) Pt- Each fact is associated with a probability value.
Logic rules define deterministic dependencies between atoms (for simplicity, we assume that all atoms are ground). An atom that unifies with probabilistic fact is called a probabilistic atom, whereas an atom that unifies with the head of a rule is referred to as derived atom. We assume that the sets of probabilistic and derived atoms are disjoint.
Semantics. Each ground probabilistic fact p; :: Sa defines an atomic choice, in which Sa is either included (with probability p:) or excluded (with probability 1 - p:). A total choice is formed by making an atomic choice for each fact in F, resulting in a subset C C JF of the selected facts. If there are n probabilistic facts, the number of possible total choices is 2". From those choices, we derive the remaining atoms by applying the logic rules.
The probability of a total choice C is computed by treating all atomic choices as independent events:
P(C) II Ps [I (1pppppppll p.).
3.3 Inference
Given a ground atom q (the query), the relevant ground program M(4) denotes the minimal subset of the grounded version of the original program M that is sufficient to derive q. Specifically, MM()) obtained via backward reasoning from g. recursively identifying all probabilistic facts and rules necessary for its derivation. This process ensures that only the components relevant to the query are retained, thereby preserving correctness while enhancing the efficiency of probabilistic inference.
In model reconciliation, the Most Probable Explanation (MPE) inference is employed to identify the most probable set of assumptions that explain why a given query q holds. This supports alignment between an agent and a human user by providing interpretable explanations. Formally, the MPE inference is defined as:
MPE(q M) = arg max P(C(g) g),
(2)
where F(q) is the set of ground probabilistic facts in M(q). and P(C(g) q) denotes the posterior probability of selecting the subset C(g) given that g is observed to be true.
Example 1. Consider the following Problog program M with query = wet:
0.7 :: rain.
0.7 :: a.
0.7 sprinkler.
0.7 b.
0.3 cloudy.
0.3
wet :- rain.
d: a.
wet sprinkler.
d: -b.
where rain, sprinkler. cloudy, and wet are denoted by a, b, c, and d, respectively, for simplicity.
3

---

Ground Probabilistic Facts of .Mg)): F(q) = {a, b}, since e is irrelevant to query d.
Effective Choices: C(g) E {0. {a], (6), (), For C(q) = (a,b). P(C(g)) = 0.7 x 0.7 0.49.
MPE Inference: MPE(q MM (a,b), P(MPE(1 M)) 0.49 and MPE(-q M) 0.
P(MPE(-q/ M)) = 0.09.
4 Probabilistic Model Reconciliation
We now present our framework for generating explanations in PLP. Intuitively, it enables us to resolve discrepancies between an agent's 's and a human's probabilistic models, caused by incomplete information, conflicting assumptions, or differing knowledge. Model reconciliation identifies and explains these differences, fostering a shared understanding between the agent and the human.
4.1 Problem Settings and Assumptions
We consider setting where agent and a human user each maintain their own ProbLog programs: the agent's model Ma and the human's 's model Mh-
Definition (Model Inconsistency). The agent model Ma and the human model Mn are said be inconsistent with respect to a query if one of the following conditions holds:
Case 1: P(MPE(glMa)) P(MPE(-q).M, but P(MPE(q)MM)) < ([MPE(-q[MM)
Case 2: P(MPE(q)Ma)) < P(MPE(-q).a)) but P(MPE(q)M))) > P(MPE(-q).a))
In both cases, the agent and the human assign opposite preferences to q and -q. indicating divergence in belief that motivates the need for model reconciliation.
4.2 Problem Formulation
To resolve the inconsistency between the agent and the human user, the agent must generate an explanation that allows the human to reconcile their model with that of the agent. To this end, we propose a logic-based formulation of model reconciliation within the ProbLog framework, referred to as P-MRP Explanation. A P-MRP Explanation is formally defined as follows:
Definition (P-MRP Explanation). Given that the agent model M, and the human model Mn, are inconsistent with respect to query q (as defined in Definition 7 define < ((t,,=) as a P-MRP explanation for q from Ma to Mr, if and only if S MMa c C _M, and the updated human model M (Mr Uct) > c is both valid and consistent with Ma with respect the query q-
When the human model Mr is updated using a P-MRP explanation e, new formulae et (including facts and rules) from MM are added, and formulae e from M₁, are removed to ensure consistency.
To evaluate the quality of an explanation, we associate a cost with each candidate explanation == (cT c ) quantified by a cost function cost(c) that models the cognitive effort required for the human to understand and incorporate the explanation. This function serves as the optimization objective and is defined as follows.
Definition 3 (Explanation Cost). Given an explanation e = (et (ett,="; let ejuc and faor denote the sets of probabilistic facts, and th and Eutle denote the sets of rules in E and e respectively. We consider the following types of modification.]
Change-probability (cp): cost Cp is incurred for each fact Sa E Eface ffwr representing probability update.
Add-fact (c ): A cost of is incurred for each new fact fi E Efjass X Effer
Add-rule (ct ); A cost of is incurred for each rule r E eitoe added to the model.
Delete-rule (c,, ): A cost G, is incurred for each rule r <ndo removed from the model.
The total explanation cost is given by:
cost(c) = Cp Ituc O Taal + of 1sstac \ TTacl + cF -Ittteel + CT -Trutel-
(3)
The task of explanation generation be formulated an optimization problem, defined follows.
We omit delete-fact since it is identical to change-probability that sets the probability of the fact O.

---

Definition& 4 (Optimal Explanation). Let Evalid be the set of all valid P-MRP explanations as defined in Definition 2 Then, an optimal explanation defined as: e* argmin cost(E).
Example 2. Continuing the scenario in Example 7 consider the the following two models Ma and Mi.
0.7
0.7 :: b.
0.3 :: a. Ma
Ma : 0.3 c.
d: -a.
d
d: -b.
Let the query be d. As shown in Example 7 we have P(MPE(d M.)) P(MPE( d MM)), but P(MPE(d M,)) P(fa]) 0.3 < P(MPE(-d M.)) = P(O) 0.7.
As an illustration, consider the following valid P-MRP explanations for d from Ma to Ma: [(f0.7::a.) :0.3::..)) ({0.7 :: b., d b.}, 0) } Given modification cost of 1 per change, the optimal explanation is: e* = (40.7 a. J. {0.3 :: a..)), where cost(E") = This is a change-
probability action, adjusting the probability of fact from 0.7 to 0.3.
5 Search-Based Explanation Generation
Since computing a cost-optimal explanation under MPE semantics is NP-hard and lies in the Σn complexity class [23], we propose two search-based algorithms solve the optimization problem in Definition
E The first is generic search algorithm that exhaustively explores all explanations to find a cost-optimal one. To improve efficiency, we introduce an optimized search algorithm with pruning and cost-guided strategies.
Both algorithms construct explanations by incrementally modifying the human model. Actions chosen from a two-level space: first, the type of modification (e.g., adding a fact or rule); second, the specific element modify.
To formalize this process, we define the key notations of the agent and human models. Let be query, and let Ma(q) and (g) denote the relevant ground programs under the agent model Ma and the initial human model MM. respectively. The human model at timestep is denoted by Mi.e. where Mr.0 Mn.- Let Fa and Fu., denote the sets of ground probabilistie facts in the agent model and the human model at timestep t. Similarly, let Fa(q) and Fn,e(q) represent the ground probabilistic facts appearing in the relevant programs Ma(g) and Ma,x(g), and let R. (ạ) and (q) denote the corresponding sets of rules. For any ground fact f. we use Pa (f) and (f,)(f) denote its probability in the agent and human models, respectively.
5.1 Generic Search Algorithm
The generic search algorithm exhaustively explores the explanation space without pruning. The first-level action space consists of four types of model modification operations, defined as:
Arpe = dahange-probabiliic add-fact, add-rule, delete-rule).
(4)
Given a selected action type a, E Aype at timestep f, the second-level action space specifies the candidate elements applicable under de:
If a, = thange-prooabillin then the candidate space A& contains shared facts with different * (f))
probabilities: A = {f E Fa (g) (f(f)
If a, add-fact, then the candidate space is Aa = F. (g) (Fh,, representing facts available in the agent model but absent from the human model.
Fa
If o, add-rule, then the candidate space is Ar = fr r E Ra(g) (2), body(r) C Fr.e) containing rules that can be added the human model.
If az = delete-rule, then the candidate space A," = Rg,( consisting of rules in the human model that can be removed. Note that do not consider deleting rules that were previously added.
At each timestep t, the explanation represented as 6 (c" ) where E c 0. The explanation is updated based on the selected action at and element as follows:
( (PPa(e)) n.),,, G-1 U (Ph.e(ee) : (..)) ((P(ee)) G-1)
a; Shange-probability. add-fact,
(ET 1,
(5)
(e Uee) G-)) (et ((e))
a, add-rule,
at delete-rule.
5

---

After each step, the human model is updated by MA.: - (M, Uc) G where 2 0.
The search process follows the A algorithm, where the heuristic function hf at each timestep t is defined as the minimum cost among all possible action types:
hit min(cp: ....
(6)
where Cps of o7, and c, denote the costs of lhange-rrobabiliyy add-fact, add-rule, and delete-rule, respectively (see Definition 3). Further implementation details can be found in Appendix A.1
To formally guarantee the correctness of this approach, present the following validity theorem and the corresponding proof is provided in Appendix A.2
Theorem 1 (Validity Guarantee). Given agent and human models Ma and M, that are inconsistent with respect query 9. the search procedure described above is guaranteed to find at least one valid explanation = (ct,ee) such that the updated human model M,, = (M₁ U Ue+) ( is consistent with M. regarding q-
5.2 Optimized Search Algorithm
While the generic search algorithm is complete, it is often inefficient due to the large explanation space, where many actions are unnecessary for resolving the model inconsistency.
To enhance scalability, we introduce an optimized search algorithm that prunes irrelevant actions by focusing only on those needed to resolve the specific inconsistency. This approach identifies the minimal set of actions required, significantly reducing the search space without losing completeness.
To formalize this idea, we first introduce several definitions grounded in the ProbLog framework. These definitions provide the foundation for a pruning theorem and its proof, enabling precise reasoning about how model updates affect query outcomes.
Definition 5 (DNF Representation of Query). Given ProbLog program M and query q. let F(g) = {f+ fz....,fr! denote the set of probabilistic ground atoms in M(q). According to the semantics of ProbLog, the query q can be represented as disjunctive normal form (DNF) formula:
= Vi where Ti = N df
Each clause r; corresponds derivation q and is expressed conjunction of literals. Each literal at is either a ground atom its negation, i.e., of F(q) uf F(g)).
This representation clarifies that satisfying any single conjunction is sufficient for to hold. Based on this structure, we now present the following theorem, which characterizes the relationship between the MPE probabilities and the DNF representation of the query.
Theorem 2. Let M be a ProbLog program and a query with DNF representation = V Tb where r; 1 az. Then:
Case 1: P(MPE(g (M)) 2 (IMPE(-qIM)) + 3i E mm] Vj E [k:]. P(a.) > 0.5.
Case 2: P(MPE(g M)) < P(MPE(-Q M)) > Vi E [m] Ej E [R:]. P(a:) < 0.5.
Proof Sketch. We present a proof sketch for Case 1. noting that the proof for Case 2 proceeds analogously, Full details provided in Appendix A.3
(=) By contradiction: Suppose that q is more probable than mq under MPE, yet each clause in its DNF contains literal with a probability below 0.5. Flipping any such literal would yield a more probable explanation favoring -q, contradicting the assumption that the MPE favors g.
(+)) If there exists a clause in the DNF of q such that all its literals have probability at least 0.5, then flipping them true in the MPE of -q results in an explanation that satisfies q and is least as probable.
Based on Theorem we can narrow the explanation search space by focusing literals or clauses that are critical for switching the model's preference between -q and q. This allows us to exclude actions irrelevant to belief change. We now refine the action space for each case in Definition ]

---

Case 1:
The agent prefers 9 while the human prefers -q, i.e.,
P(MPE(q Ma)) P(MPE((-q) Ma)), P(MPE( M.)) < P(MPE(-q Ma)). According to Theorem 2 increasing q probability in Mr requires strengthening at least one DNF clause TÚ with all literals meeting P(a?) 2 0.5 in the updated model. This allows us to prune the first-level action space to:
Aype
prounng-prbbbbbitty... add-fact, add-rule).
The delete-rule action is excluded because increasing only requires having one clause with all literals meeting the probability threshold, and deleting clauses does not help achieve this.
Given selected action type E Aryo at timestep t, the second-level action space defines the set of applicable candidate elements:
If a = Shaang-probbbiliin the candidate space is: A = (/IS E Fa n Fn,,(1), sign(Pa - 0.5) + sign(Ph,,()) -0.5))
where sign(-) returns the sign of its input, capturing facts where the agent and human disagree on belief direction.
If (r add-fact, the candidate space remains the same as the generic search algorithm.
If de add-rule, we first define the current human belief set B, based on the updated model MA,
(8) That if the human assigns a probability strictly above 0.5 to f. include f: the probability is strictly below 0.5, we include its negation -f; and if (f.)(f) 0.5, both f and -f are included, reflecting state of belief indifference.
B, = (J E Fra, Pa,(()) 2 0.5) u (~S / Fn,t Pr,x(f) / 2 0.5}.
addable rules must have all body literals supported by the current belief set, i.e., (ody(r) B. Additionally, to ensure can increase the probability, the body must include at least one literal I where (l), * 0.5. Therefore, the final candidate space is:
According to Theorem 2
A = [r|r E Ra( RR,,(1), body(r) C B., E1 E body(r) s.t. Ph,,(1) 0.5). (9)
Case 2:
The agent prefers -q while the human prefers g, i.e., P(MPE(q (Ma)) < P(MPE(-q) Ma)), P(MPE(g (M)) > P(MPE(-9 M,)).. According to Theorem 2 decreasing q's probability in Mr. requires weakening each DNF clause r; so that at least one of its literals satisfies P(a?) < 0.5 in the updated model. This allows pruning the first-level action space as follows:
Anye (changc-probability, add-fact, add-rule), if (g)((g) 0, (change-probability, delete-rule),
RR, + 0.
This distinction hinges on whether (q) is empty. When RA, 0, new rules or facts can be introduced. Otherwise, only changing probabilities or deleting rules is effective, as each clause must include at least one literal with ((a{) < 0.5.
Given a selected action type a Aype at timestep the second-level action space specifies the set of applicable candidate elements under az,
If 0e change- prannge-rrbbbblity..o the candidate space is the same in Case defined in Equation If 0r add-fac flct, the candidate space is also identical to Case 1.
If a2 add-rule, we define the opposing belief set as:
B. (f If Fn.e (f,x(f) 0.5) U uf-f If Fras Pn,((f) 0.5}.
(10)
We restrict addable rules r such that at least one literal in the body of is supported by B, The candidate space is thus defined as:
Ar = (r|r= E Ra(4) Ra,e(z), body(r) n B + 0).
If a, delete-rule, allow the removal of rules whose bodies not supported at all by the opposing belief set B, Formally,
A [r|r E Rn,,(g), B
(11)
Similar to the generic version, employ A search to identify the cost-optimal explanation e*, updating as in Equation 5 The refined heuristic function A derived from Theorem 2 is defined separately for two cases at each timestep f. yields a more informative estimate that accelerates the search process compared with k0
7

---

When only thange-probabiin actions are allowed, the heuristic estimates the minimal number of fact probability changes needed for each rule so that all literals in its body have probabilities of at least 0.5 in the updated model. For each rule r E (g), the set of modifiable literals is:
Case 1:
C - { e body(r), (() 0.5 (L A V - - A5)),
(12)
where Aū is defined in Equation 7 A rule r can be satisfied by probability adjustment alone only if every literal in its body is either already satisfied under B, (Equation (8) belongs Cý, i.e., body(r) S B, U U In this case, the number of required modifications is |CT]: otherwise, we set 6% = +oc, indicating that rule r cannot be satisfied by probability adjustment alone.
When only add-rule actions are permitted, the heuristic evaluates whether introducing a new rule can restore consistency. If the set of addable rules A (defined in Equation 9 is non-empty, adding one rule suffices. Otherwise, at least one fact must be modified or added first.
The heuristic function is then defined as:
if A # 0, min(e, min.gr.. 87 o7 t +p). if A 0.
min(c; min of ct);
(13)
If (g) = 0, a probability adjustment or at least one new rule must be introduced, implying that the heuristic function is defined as hith min(et cp).
Case 2:
Otherwise, the reasoning process depends the available action types. When only delete-rule actions are permitted, we identify the rules that can be removed, namely those whose body literals all have probabilities not less than 0.5, corresponding to A as defined in Equation
When only change-probubiid problem. We define the universe of unsatisfied rules as those not containing any literal that lies outside AC (and its negation) with probability less than 0.5:
actions are allowed, the problem can be reformulated as a sel-cover
U = (R),(() \ fr r E Ra,,(g), E e body(r), 8 $ AE A - E A Phoele) < 0.5).
(14)
For each modifiable fact f E A4, the cover subsets are defined as:
S = (r| E U, 36 e (f,-f} s.t. l E body(r) A Pf,,(e) 2 0.5 Pa(C) < 0.5].
(15)
The goal to find the smallest collection of such subsets that covers all rules in Us:
S = arg s' fE.A5) [S'] s.t. USES: S S= U4:
(16)
This formulation minimizes the number of change-probability actions needed so that each rule in Ue contains at least one literal with probability below 0.5. Since both f and -f may appear across rules, Sj may be empty, in which case at least one rule must be deleted to restore consistency.
If both delete-rule and number of deleted rules and y the number of Stange-probabiliie actions required reach the optimal explanation from the current state. Removing x rules from U4, can reduce the minimal cover size by most x, which gives S x S y S | Consequently, the total cost from the current state to the optimal explanation satisfies c, y Cp 2 |S min(c, : cp).
actions are allowed, let x (r < D denotes the
Based on the above analysis, the heuristic function defined as:
min min((. (p), LAT c if S + 0, S 0.
ppi h
(17)
Solving the exact set-cover is NP-hard. To mitigate computational cost, the rule coverage can be restricted those with the smallest body size: Ud = {r U4 [body(r)] min [body(r')) }.
More details can be found in Appendix AA.4
To further improve efficiency, we introduce a greedy variant gready which applies the standard greedy algorithm the relaxed set-cover formulation. Building on Weighted A properties, the resulting explanation cost remains bounded when different heuristics are employed, formalized below.
Theorem 3 (Theoretical Guarantee). Let hy denote the optimal heuristic value, d the optimal explanation cost, and w 2 1 the weight of heuristics used in Weighted A".
8

---

Both h and hy are admissible, i.e., h4t" S h; and h S h4. Consequently, Weighted A employing w hi or w. ht as the heuristic guarantees a total cost bounded by w c.P.
The greedy heuristic hiredd achieves a (1 + [U4)) approximation, iee, l hguedy S (1+1o) In [MA))) hig where Ur is the universe of unsatisfied rules (see Equation [4]. Hence, Weighted A using w hig the heuristic guarantees total cost bounded by (1 In(max, (Tl)) c where max; [41l I [Ri,(9)) and Rn,((g) is the set of rules in the initial human model relevant to query q.
The detailed proof is provided in Appendix A.S
6 Empirical Evaluations
6.1 Estimating Action Costs via Human-User Study
This study examines how an Al agent, Blitzcrank,, explains its decisions an intelligent warehouse, determining whether goods should be delivered. Participants compared explanation pairs and chose the one they felt best clarified the agent's reasoning. This setup represents one feasible way to evaluate explanation cost, though not the only possible approach.
Data Collection. We recruited 128 participants via Prolific (24), ensuring diverse sample Participants were fluent English speakers and were compensated USD 2.00. After attention and coherence checks, data from 100 participants were retained for analysis.
Cost Estimation. To estimate the relative cognitive effort of
Table I: Estimated Costs for
different explanation types, we used the Bradley-Tere model [25] on the pairwise comparison data. Each action a; had a strength parameter B,. with higher 8 values indicating greater participant preference. The cost of an action was defined as the negative its strength [26]. 3r, making more preferred actions correspond lower costs. To ensure non-negative costs compatible with search algorithms (e.g., A*), exponentiated the negated strength values. The final cost of each action was defined cost(a;) = e e- Based on this formulation, the estimated costs for the four explanation actions are shown in Table 1
Each Explanation Action.
action
cost(a.)
change-probability
0,9801
add-fact
0.8688
add-rule
1.0202
delete-rule
1.1511
6.2 Computational Results
This section evaluates the computational results of Generic Search and Optimized Search algorithms for model reconciliation. While the algorithms are general to any cost setting, the experiments use the costs listed in Table All experiments were run on a MacBook Pro (M2, 16GB RAM).
Experimental Setup. Our experiments use two models: Agent and Human.
Agent Model Ma: Each Ma, contains Fal = 10, 20, 100, or 1000 probabilistic facts and |R,, 5, 10, 50, or 500 rules, respectively, all related to the same query. Facts have randomly assigned probabilities, and rules have bodies of 2-4 literals, generated based on cases in Definition [
Human Model MR. Derived from each M,, at four complexity levels E {20%, 40%, 60%, 80%), reflecting the percentage of probabilistic facts that differ. Each differing fact has I/3 chance of being: modified (probability flipped), removed, or replaced (new fact). Human model rules share the same heads as the agent model but are built using existing facts, with the rule count as: [RAl = [Ral (1 1/3 I)]
We generate 100 Agent-Human Model pairs for each configuration, totaling 1,600 pairs (4 Agent settings x 4 complexity levels x 100 repetitions) for each case Definition
Evaluation Metrics. All experiments are capped at 600 seconds per run.
Average Time: The average runtime (in milliseconds) for runs completed within the time limit. Average Cost: The mean cost of achieved explanation for runs completed within the time limit.
Results and Analysis. Table 2 compares the two search algorithms under the cases defined in Definition In Case 1, we report runtime for the generic (h (h and optimized (A"Th) heuristics, along
2 Ethicc approval was obtained from our university's 's IRB. The human- study, collected data, and inplementation are released on httttps:://gttiii com/ CommYYDAA-..
Model- hat.pp/oooooooooooeeeeeeeeeaaaoo

---

Table 2: Performance Comparison of Two Algorithms across Two Cases in Definition
Case Optimiized Ar" (ms)
Case 2
|R_.]
Generic Ay (ms)
Generic (ms)
Optimaized
Ay" (mm)
ct
Ag
(ms)
2- (ms)
2 (ms)
2012
54.00
33.9
10
60%
401%
35.8
29.7
33.9
54.9
1.95
30.8
36.2
33.9
54.7
1.47
1.37
35.8
1.37
33.8
1.37
35.7
1:37
1.47
5016
33.6
35.8
2.34
28.1
34.5
1.28
36.2
1.28
33.8
1.28
36.9
1:24
201
1256.8
34.7
1.39
29758.7 7
15 Uo)"
34.6
2.47
36.8
2.47
34.3
2.47
36.1
2.47
20
10
60%
40%
3546.3 1
1846.7
35.7
35.4
1.38
1.22
11657.0 (1 Mo)
19290 4
35.0
35.2
2.08
1.92
16.0
16.5
2.08
1.92
34.4
$4.9
2.08
1.93
35.0
36.3
2.08
199
80%
6406.2 2
34.6
1.50
3187.1
33.8
1.84
36.7
1.84
34.3
1.84
35.9
1.84
20%
37.0
0.59
40.0
8.58
18,0
8.98
37.3
8.99
35.57
8.99
100
50
40%
60%
37.7
39.1
115%%
0.58
3572.2
228.1
7.93
7:35
53.9
7.93
1950.9
139.0
7.15
7.93
40.7
7.16
7.93
80%
30.2
6774. (66)
5.48
3874.
20%
176.5
0.98
80.40
1000
500
40%
235.6
3122.3
72:45
60%
254.7
63.34
8014
331.1
0.58
18936.6
57.02
"Vo" indicates limeout.
denotes that most runs timed out.
with the corresponding optimal costs coPt_ In Case 2, we further evaluate the greedy heuristic (hgreedy and the weighted variants (2 11, and 2-
t-- herreddy, ) reporting the resulting costs cereddy c and city groddy
Runtime Comparison. The optimized heuristic hith substantially reduces runtime compared to across all settings. For instance, in Case 1, runtime decreases by 99.2% (from
the generic h geg 4406.2 ms to 34.6 ms) when |Fal 20, |Ra| = 10, and 80%. In Case 2, the greedy heuristic greedy further improves efficiency over h.ThT Moreover, the weighted variants 2- 1,2" and 2 h preedyy offer additional runtime gains. For example, under [F = 100, |R., = 50, and / = 80%, 1 geedy achieves a 98.4% runtime reduction (from 8774.9 ms to 136.6 ms) compared with 1, while 2 h!t achieves 55.9% reduction over hTth Notably, 2 h.greedly can effectively produce valid solutions within the time limit, supported by the theoretical guarantee in Theorem 3
he
Cost Comparison. Focusing on Case 2. for [Fal E {10, 20, 100). the observed costs geredyy opt and of gredy remain close to the optimal cOPe Consistent with Theorem 3 (with w = 2), the empirical results satisfy the bounds ggoody < (1 + In (Rx cop opt < 2 cop and c greedy <
2. 2-(1 + In [Ral) . cope, These results empirically corroborate our theoretical guarantees.
Further detailed analysis is provided in Appendix A.6 Overall, Optimized Search demonstrates superior scalability and robustness compared to Generic Search, consistently achieving lower average runtime. The greedy and weighted variants efficiently handle large-scale models while producing ex- planations that satisfy the theoretical guarantees established in Theorem 3 These findings underscore the effectiveness of theoretically guided search strategies for scalable model reconciliation.
7 Conclusion and Discussion
In this paper, we present model reconciliation framework within probabilistic logic programming (PLP). Our approach formalizes reconciliation under uncertainty using ProbLog to represent an agent's and a human's 's probabilistic models, identifying and resolving inconsistencies in MPE outcome probabilities. We introduce cost-based explanation model that quantifies the cognitive effort of model updates, enabling the generation of cost-optimal explanations that minimally adjust the human's model. To generate these explanations, we develop two search algorithms: generic search algorithm and an optimized search algorithm guided by theoretical insights for pruning the search space. The optimized algorithm is further extended with greedy and weighted variants to improve scalability and runtime efficiency. We validate the framework through a user study examining how explanation types affect user understanding and through computational evaluations demonstrating that the optimized search consistently outperforms the generic method in both runtime and scalability.
Our framework enhances human-Al interaction by providing clear, cost-optimal explanations for AI decisions, thereby improving user understanding and trust across domains. By aligning the user's mental model with that of the agent, it enables more informed and transparent decision-making, Despite its strengths, the framework has limitations. As a logic-based approach, it has been evaluated mainly through computational experiments and controlled user study, leaving its effectiveness in real-world settings to be further verified. In future work, we plan to incorporate techniques for learning user models from feedback to enable personalized and adaptive explanations (27]
10

---

Acknowledgments and Disclosure of Funding
We thank all the reviewers for their insightful comments and suggestions, which significantly im- proved this paper. This research is partially supported by the National Science Foundation under Award No. 2232055. Additional support provided by the Flemish Government (AI Research Program), the European Research Council (ERC) under the European Union's Horizon Europe re- search and innovation programme (Grant Agreement No. 101 142702), and the iBOF/21/073 project. The views and conclusions expressed in this paper those of the authors and do not necessarily reflect the official policies or positions of the sponsoring organizations, agencies, or the United States government.
References
[1] Sarath Sreedharan, Tathagata Chakraborti, and Subbarao Kambhampati. Explanations as model reconciliation-a multi-agent perspective. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAT), pages 277-283, 2017.
[2] Tathagata Chakraborti, Sarath Sreedharan, Yu Zhang, and Subbarao Kambhampati. Plan explanations model reconciliation: Moving beyond explanation soliloquy. Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pages 156-163, 2017.
[3] Tran Cao Son, Van Nguyen, Stylianos Loukas Vasileiou, and William Yeoh. Model reconcil- iation in logic programs. In Proceedings of the European Conference on Logics in Artificial Intelligence (JELIA), pages 393-406, 2021.
[4] Stylianos Loukas Vasileiou, Alessandro Previti, and William Yeoh. On exploiting hitting sets for model reconciliation. In Proceedings of the AAAI Conference Artificial Intelligence (AAAI), pages 6514-6521, 2021.
[5] Daan Fierens, Guy Van den Broeck, Ingo Thon, Bernd Gutmann, and Luc De Raedt. Inference in probabilistic logic programs using weighted CNF's. In Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI), pages 21 221- 2011.
[6] Van Nguyen, Stylianos Loukas Vasileiou, Tran Cao Son, and William Yeoh. Explainable planning using answer set programming. In Proceedings of the International Conference Principles of Knowledge Representation and Reasoning (KR), pages 662-666, 2020.
[7] Daan Fierens, Guy Van den Broeck, Joris Renkens, Dimitar Sht. Shterionov, Bernd Gutmann, Ingo Thon, Gerda Janssens, and Luc De Raedt. Inference and learning in probabilistic logic programs using weighted Boolean formulas. Theory and Practice of Logic Programming, 15(3):358 4013588-411100 2015.
[8] Maria Fox, Derek Long, and Daniele Magazzeni. Explainable planning. arXiv preprint 1wXiv:1709.102566 2017.
[9] Stylianos Loukas Vasileiou, William Yeoh, Tran Cao Son, Ashwin Kumar, Michael Cashmore, and Daniele Magazzeni. A logic-based explanation generation framework for classical and hybrid planning problems. Journal of Artificial Intelligence Research, 73:1473-1523 1534, 2022.
[10] Stylianos Loukas Vasileiou and William Yeoh. PLEASE: Generating personalized explanations in human-aware planning. In Proceedings of the European Conference on Artificial Intelligence (ECAI), pages 2411-2418. 2023.
[11] Sarath Sreedharan, Tathagata Chakraborti, and Subbarao Kambhampati. Handling model uncertainty and multiplicity in explanations via model reconciliation. Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS), pages 518 318-526, 2018.
[12] Stylianos Loukas Vasileiou, William Yeoh, Alessandro Previti, and Tran Cao Son. On generating monolithic and model reconciling explanations in probabilistic scenarios. Journal of Artificial Intelligence Research, 84, 2025.

---

[13] David Poole. Probabilistic Horn abduction and Bayesian networks. Artificial Intelligence, 64(1):81-129, 1993.
[14] Peter Flach. Simply Logical Intelligent Reasoning by Example. Wiley, 1994.
[15] Taisuke Sato. A statistical learning method for logic programs with distribution semantics, In Proceedings of the International Conference Logic Programming (ICLP), pages 715-729, 1995.
[16] Taisuke Sato and Yoshitaka Kameya. Parameter learning of logic programs for symbolic- statistical modeling. Journal of Artificial Intelligence Research, 15:391-454, 2001.
[17] David L Poole. Exploiting the rule structure for decision making within the independent choice logic. arXiv preprint arXiv:1302, 300.4498, 2013.
[18] Joost Vennekens, Sofie Verbaeten, and Maurice Bruynooghe. Logic programs with annotated disjunctions. Proceedings of the International Conference on Logic Programning (ICLP), pages 431-445, 2004.
[19] Luc De Raedt and Kristian Kersting. Probabilistic inductive logic programming. In Probabilistic Inductive Logic Programming, pages 1-27. 2008.
[20] Dimitar Shterionov, Joris Renkens, Jonas Vlasselaer, Angelika Kimmig, Wannes Meert, and Gerda Janssens. The most probable explanation for probabilistic logic programs with annotated disjunctions. In Proceedings of the International Conference on Inductive Logic Programming pages 139- 139-153, 2015.
[21] Angelika Kimmig, Bart Demoen, Luc Raedt, Vitor Santos Costa, and Ricardo Rocha. On the implementation of the probabilistic logic programming language ProbLog. Theory and Practice of Logic Programming, 112-33)225-262,, 2011.
[22] Joris Renkens, Angelika Kimmig, Guy Van den Broeck, and Lue De Raedt. Explanation- approximate weighted model counting for probabilistic logics. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), pages 2490-2496, 2014.
[23] James D Park. MAP complexity results and approximation methods. Proceedingy of the Conference Uncertainty in Artificial Intelligence (UAI), pages 388-396, 2002.
[24] Stefan Palan and Christian Schitter. Prolific.ac subject pool for online experiments. Journal of Behavioral and Experimental Finance, 17:22-27, 2018.
[25] Ralph Allan Bradley and Milton E Terry. Rank analysis of incomplete block designs: I. the method of paired comparisons. Biometrika, 39(3/4):324-45, 1952.
[26] Kaivalya Rawal and Himabindu Lakkaraju. Learning recourse costs from pairwise feature comparisons. arXiv preprint 0tt::2209./39400 2024.
[27] Yinxu Tang, Stylianos Loukas Vasileiou, and William Yeoh. Does your AI agent get you? personalizable framework for approximating human models from argumentation-based dialogue traces. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), pages 14405-
14413, 2025.
12

---

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

---

Justification:
We provided Theorems 1 and 3 with proof sketch of Theorem in the main text. The complete proofs for these theorems are available in Appendices
and A.5
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We have provided the detailed algorithms in Section 5 and the corresponding code is provided via Github link.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
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 a specific model and empirical evaluation, 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 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 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 submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which 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 have some path reproducing verifying the results.
5. Open access to data and code
14

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
The algorithm code and experimental data are provided via Github link.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
//nips //ipss.cc/pill wttpcccpppppppppeeeeeeeeeeeeeeee httaa//gggieee//eeuuabiissssssss /Cc////oddiiisssseeeeeee ssiiissiiciiiyyyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification: We have specified the settings in Section 6.2 and the algorithm code and experimental data provided via Github link.
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 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, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
We present the comparative experimental results summarized in Table 2
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, confi- dence intervals, statistical significance tests, 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 with given experimental conditions).
15

---

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).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out of range (c.g. negative emror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The details of the compute resources are provided in Section 6.2
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: Our research fully complies with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We have discussed the impacts in the conclusion.
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.
16

---

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

---

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

---

16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to L.MM policy (https: hate:p///eerrippc.cc////oeeerers for what should or should not be described.
19

---

A Appendix
A.1 Details of Generic Search Algorithm
This section presents the pseudocode of the generic search algorithm, together with an illustrative example of the action space used to construct candidate explanations.
Algorithm Generic Search Algorithm for Cost-Optimal Explanations
Require: Agent model Ma. human model MM, query !
Ensure:
Cost-optimal explanation c² (E c²)
1: Initialize priority queue Q &- {(E0- g( )= = 0)}. where eo = (0,0)
2: Initialize g-Score map G|en] <- and closed set V
3: while @ is not empty do
4: Pop (4299t) with lowest 9r 1
5: if' g: > G[ee] then
6: continue
7: end if
8:
if G E V then
9: continue
end if
11: Construct modified human model Ma. (Mr Uet) A5
if i then
13:
return
14:
end
15:
Add 6, V
16:
for all action types d, E Aype do
17:
Determine candidate set At according to Section 5.1 for all elements e E A4 do Generate successor Ex+1 according to Equation
18:
19:
20:
9++1 + cost(e++1)
21:
if fet1 $ G 9t+1 [[e++)] then
22:
g + 9++1
23:
Insert (c+119t+1) into Q with priority fe-1 Gt+1 + 1t11
24:
end if end for
26:
end for
end while
28:
function ISCONSISTENT(,M.C. Ma.9)
if P(MPE(g Ma)) > P(MPE(-0 Ma)) then
30:
return P(MPE(g Ma.)) ) P(MPE(-g [M,))
else P(MPF(Q Ma)) < <(MPP((-) Ma)) then
32:
return P(MPE(g Ma.)) < P(MPF( MM,x)
end
34:
end function
Algorithm specifies generic A search framework for exploring the space of explanations. Starting from the empty explanation ca (0. 9), the algorithm incrementally applies actions to generate successor explanations and prioritizes them according to the evaluation function fc) = g(c) (hen (c). At each expansion step, the generated explanation governed by predefined set of action types and their corresponding candidate sets, which together define the action space of the search.
To clarify how this action space is instantiated in practice, consider the following example:
0.1 a
0.6 : b.
0.2 :: a.
0.7 ::
0.2 :: b.
M.
0.8
Mr 0.3 :: c.
d -C, e.
d -b.
d -a, b.
d -b,
d aa, c.
20

---

Based on the differences between MM and M,, the generic search algorithm considers the following first-level action types (Line 16 in Algorithm
Atype (change-probability, add-fact, add-rule, delete-rule).
For each action type d E Anpe: the corresponding candidate set A (Line 17 in Algorithm is constructed according to the criteria described in Section 5.1 In this example, the resulting candidate sets are:
Slange-probabilitg A = {a, b, c}, corresponding to facts shared by Ma and Mr but assigned different probabilities;
Add-fact: AB = {e}, corresponding to facts present in M. but absent from Mri
Add-rule: A. {d: -a, b., d -a, c.), corresponding to rules Ma \ \M, with bodies over existing human facts;
Delete-rule: A {d: b.,, d b, c. corresponding rules that appear in Ma.
This example illustrates how the action space is systematically derived from the structural and probabilistic differences between the agent and human models, while the underlying search procedure defined in Algorithm I
remains generic and independent of the specific models considered.
A.2 Proof of Theorem 1
Proof. The search algorithm exhaustively explores all possible combinations of explanation com- ponents. In particular, it will consider the explanation (ct,c-) where ex .Ma MM and e -M, MM, Applying this explanation yields the updated human model:
M = (Mr Uet) \ E -Ma-
Since Mi Ma, the models are fully aligned, and thus consistent with respect to q. Therefore, the existence of at least one valid explanation is guaranteed.
A.3 Proof of Theorem
Proof. We provide the proof for Case 1. The proof for Case 2 proceeds in similar manner.
(+) P(MPE(y M)) 2 P(MPE(- M)) = Ei E [m), Vj E [As), P(a)) 2 0.5
We prove by contradiction. Suppose (MMPE(q M)) Z P(MPE(-q M)) but Vi E [m]] 3j
[k:], P(aa) 0.5.
Let C(g)= = MPE(q) .M) be the most probable explanation under which g holds. Since q - Vm ri q holds under C(g) and only if at least one r; true. Let r1 be one such clause satisfied C(q).
By assumption, in r1 there exists some j [Ay] such that P(at) < 0.5. Without loss of generality, assume j = 1, i.c., P(at) < 0.5. Construct a new explanation C² by setting of to false, and keeping all other assignments unchanged.
Since P(a)) < 0.5, follows that:
P(C') P(C(g)).
We now show that y does not hold under C.. Since af is false in C', the clause r1 is no longer satisfied. If q were still true under C', then some other r; must be satisfied. But this would mean that C' is valid explanation for q with higher probability than C(q), contradicting the definition of C(g) as the most probable explanation of q.
Therefore, q does not hold under C², i.e., C' satisfies 7q. This leads a contradiction:
P(MPE(q MM) P(C(g)) P(C') P(MPE(-q M)).
Hence, the assumption must be false.
(+) Di E [m], Vj [k:]. P(a)) 2 0.5 + P(MPE(g M)) > P(MPE(-g (M)
Suppose zi E [m]. Vj [k=]. P(a)) ) > 0.5. Without loss of generality, assume this holds for T1.
21

---

Let (( = M M) be the most probable explanation under which does not hold. Since q V ri qq holds under C(-q) only if all r; are false. In particular, ri must be false under C(-4), meaning that at least one literal in is assigned false. Let:
{a} af
false in C(-q), [R1]].
Construct a new explanation C' by flipping the truth values of all of A to true, and keeping all other assignments unchanged.
Since each P(a)) 0.5, this modification leads to: P(C") 2 P(C(-4)).
k Furthermore, since rı Aj=1 af and all of are now true in C', we have that ri is satisfied C", and hence holds.
This yields:
P(MPE(-q M)) P(C(-g)) & P(C") & P(MPE(q) M))
A.4 Details of Optimized Search Algorithm
The pseudocode the optimized search algorithm follows the same overall structure as the generic search algorithm shown in Algorithm T differing only in the definition of the action space and the heuristic function, which are specified in Section 5.2 In addition, the INCONSISTENT predicate is evaluated according to Theorem 2 We illustrate the resulting action space and heuristic function through two examples corresponding to Case and Case 2 in Definition
Case 1 In this case, the agent model supports the query d while the human model does not, i..., P(MPE(d (Ma)) > P(MPE(-d MMa) but P(MPE(d MMa)) < P(MPE(-d MM)).. The goal is to strengthen the human model so to increase the likelihood of d.
0.1 a.
0.6 : b.
0.2 : a.
0.7
0.2 b.
Ma
0.8 : e.
Mr 0.3 : C. d -b.
d: -C
d -0, b.
d b,c.
d a, c.
We first specify the available first-level action types:
Aype (change-probabiiity, add-fact, add-rule), where the delete-rule action is pruned under the optimized setting for Case 1. Based on these action types, the resulting pruned candidate action sets are:
Change-probabillty: Ai = {b, c). since (b) = 0.6 > 0.5 while (b) 0.2 < 0.5, and Pa(c) 0.7 0.5 while (c) 0.3 < 0.5. Add-fact: A {e), which coincides with the candidate set produced by the generic search algorithm.
Add-rule: A = 0. since the current belief state B, {-,, -b, -c) (Equation g does not support the body any rule.
We next illustrate the computation of the heuristic function. For each rule in the human model, we consider the set of modifiable literals C defined in Equation [2] In particular, for rı d :- b.. C = {b}, and for 72 d:- b, c., C² = {b, c}. Thus, the minimum number of required modifications across all rules
Since A. = 0. no add-rule action is applicable at timestep t. Accordingly, the optimized heuristic
value opt (Equation 13
h
ppt
min(cp, et + c ct + cp).
22

---

Case 2 This example illustrates the opposite scenario. in which the human model supports the query d. while the agent model does not, i.e. P(MPE(d M,)) P(MPE(-d M,)). but P(MPF(d Ms)) > P(MPE(-d MM)).. The goal is to weaken the human model so that d becomes less probable.
0.1
0.2 : a.
0.6
0.2 : b.
0.7 :::00
Ma : 0.3 C.
Mn
0.8 :: E.
d: -b.
d -,
d: -b,
- 0, b.
d a,
We first specify the available action types at the first level:
Aype prannggg-pbbbbbitty... delete-rule),
where the add-rule and add-fact actions pruned under the optimized setting in Case 2.
Based on these action types, the pruned candidate action sets are given as follows:
Change-probabilityy A; = (),c), since Pa (b) = 0.2 < 0.5 while Px( 0.6 > 0.5, and Pa(c) 0.3 < 0.5 while (c) 0.7 0.5.
Delete-rule: A," {d:- :- c, e.). since the opposite belief B; = {a, -b, c, m) (Equation 10 does not support the body of this rule.
Next, we illustrate the computation of the heuristic function under this setting. The universe of unsatisfied rules is ld = {d:- e. (Equation [4]. For each modifiable fact in Af, the corresponding covering subsets are S; {d ;- c, e.} and S = {d :- a, b.} (Equation 15)
Consequently, the
smallest collection of subsets that covers Us St {S (Equation 16..
Since S, * 0, the optimized heuristic value hiTh defined in Equation given by
h = min(min(c,, cp), ).).
A.5 Proof of Theorem 3
Proof. We provide the proof below.
Admissibility of T.g" The generic heuristic n." defined in Equation 6 is admissible. At timestep I, the current human model still inconsistent with the agent model; hence, at least one further action required reach a consistent model. Since hete only counts such necessary remaining actions, never overestimates the optimal explanation cost and therefore is admissible.
Admissibility of h. The optimized heuristic 1 defined in Equations 13 and 17 is also ad- missible. At timestep t, 10th is derived by considering all valid action types and Nower-boundigg the minimum required to eliminate the set of unsatisfied rules Ue (Equation 14p. As shown in Section 5.2, this corresponds to a relaxed set-cover formulation, whose optimal value provides lower bound on the true explanation cost.
In Case 2, we further restrict the rule coverage to rules with the smallest body size,
4 = { E 24, [body(r) = min, (body(r')l)
Recall that S denotes the minimum collection of subsets covering U4 (Equation 15 and let S denote the minimum collection of subsets covering 4""
We consider the following cases:
If S 0 and S 0. then the heuristic value remains unchanged.
If St / and S * 0. then Ui C td, implies SS, S [S,], and hence the restricted heuristic does not exceed the original heuristic value.
23

---

If S = and S * 9, then deleting at least one rule is necessary. After such deletions, the resulting universe admits non-empty cover, and again we have |S |
The remaining case S + 0 and S = 0 is impossible since Ui C U. Therefore, restricting the universe to 24 cannot increase the heuristic value, and ht remains admissible.
Guarantee for hrreedy In Case 2, we formulate relaxed set-cover instance where the universe is the set of currently unsatisfied rules 24; (Equation [4). and each modifiable literal induces subset of Ur that it can "cover" (Equation [15). Recall that S denotes optimal set cover for 44 (Equation I6]. and let Stueedy denote the collection returned by the standard greedy set-cover algorithm.
In this way, the greedy set-cover solution satisfies
Istredy
S (1 + In (4A)) (8))
Hence, the greedy heuristic achieves a (1 + In (a4p)-aappoximation i.c.
h gmedy < (1 + In [eel)) nT""
A.6 Additional Analysis of Results in Table 2
Impact of Complexity on Runtime. Higher complexity implies more discrepancies in probabilistic facts but fewer rules in the human model. In Case 1, runtime increases with complexity, as the action space for change-pred coonge-poobability and add-fact expands, while delete-rule actions not applicable. In Case 2, for Generic Search, higher complexity leads to shorter runtimes because fewer rules reduce the number of costly delete-rule actions, allowing A focus lower-cost alternatives. In contrast, under Optimized Search, runtime increases with complexity. since larger number of differing facts enlarges the search space, making the heuristic-guided A search more expensive (see Equation 17).
Impact on Explanation Cost. As the model size increases, the explanation cost decreases in Case 1 but increases in Case 2. In Case 1, a larger human model with more facts and rules enables the use of lower-cost thange-probubiliiy actions. Moreover, by Theorem 2 suffices for single rule to satisfy the MPE condition, making low-cost explanations more likely. In Case larger human model introduces more rules that must be disabled, resulting in higher explanation costs due to the reliance on delete-rule actions.
At a fixed model size, increasing complexity raises the explanation cost in Case when the model is small, more fact discrepancies must be aligned. However, when the model size is large, the cost remains stable, since most cases can be resolved by adjusting a single probability or adding a single rule, again by Theorem 2 In Case higher complexity reduces the explanation cost, the number of rules in the human model decreases, thereby requiring fewer costly delete-rule actions.
24


Reviews:
[{"review_id": "ino0m7UQ8I", "reviewer": "Reviewer_azj8", "summary": "This paper introduces Model Reconiliation, that is, unifying a learned model with an user model, in the context of the probabilisti logic programming language Problog, Te authors  take advantage of  MPE learning  to reduce problem complexity, implement two search algorithms and evaluate them in a dataset.", "questions": "Although not directly connected, the approach reminded me on the work on Theory revsion, and namely the Forte work by Mooney's group and follow-up work on the Probabilistic Forte work (Aline Paes MLJ ).", "limitations": "Scalability and existing dataset come to mind.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The authors claim to be the first to pursue model reconciliation in the context of probabilistic logic program. Reconciliation may be seem as a way to compare a learned theory with the user expectations, by  detecting and describing major differences \n\nProblog and Model Reconciliation look like a good match, given that the probabilities may be helpful in finding the divergence between the user and learned , On the other hand, efficiency is a real problem for probabilistic logic systems, Eg, ProbLog compiles the program into trees for probability inference, but that requires the program to be stable. Using most likely explanations  seems to be a way to achieve acceptable performance. I think thatś the main contribution of the paper.\n \nMost likely explanations avoid the complexity of computing the full probability while still generating answers  of interest.  I also think  that finding a transformation of paths instead of complex trees may be easier for a human to understand.\n\nThe problem then reduces to searching for the best transformations. The authors present a naive naive generator and ta A* algorithm, Popular and often  more effective techniquesm eg MonteCarlo search or MAXSAT should be considered.\n\nFinally, the experimental evaluation is the weakest component of the paper. The source of the dataset should be made clear, so should the task. Experimental evaluation is hard in model reconciliation, but I would have at least expected some discussion on interpretability of the results.\n\nMy evaluation is based on the fact that I llike the idea, not just for reconciliation but  the use of MLEs. I would have expected more frrom the evaluation, though.", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the helpful and constructive comments. We appreciate your suggestions and address them below.\n\n**_Q1: Only naive and $A^*$ are explored; other methods (e.g., Monte Carlo, MaxSAT) can be considered._**\n\nA1: Our work focuses on two A*-based methods: a generic version and an optimized one. Both are grounded in a unified framework for cost-optimal model reconciliation under MPE semantics. The optimized search is not merely a variant but introduces principled pruning based on our proposed DNF analysis (Theorem 2), resulting in substantial improvements in scalability.\n\nWe agree that exploring alternative approaches could be valuable. However, incorporating MaxSAT is not straightforward in our setting. The dependencies between actions, such as changing probabilities and adding or deleting rules, are difficult to encode using propositional logic. Monte Carlo methods may help with approximate inference or serve as heuristic guidance, but aligning the sampled model updates with both MPE consistency and cost-optimality is a non-trivial challenge. We see these directions as promising future work.\n\nIn the original version, both the generic and optimized methods employed the same admissible heuristic. Since submission, we have developed enhanced heuristic functions, which we now include in this revision.\n* A tighter admissible heuristic $h_{\\text{exact}}$ derived from DNF pruning and set-cover estimation. This heuristic remains admissible while improving runtime compared to the original.\n* A greedy heuristic $h_{\\text{greedy}}$, which solves a relaxed set-cover problem and has a $(1+\\ln n)$-approximation guarantee, where $n$ is the number of uncovered DNF clauses. This ensures the total explanation cost lies within $[c^\\star, (1+\\ln n) c^\\star]$ where $c^\\star$ is the optimal cost. In practice, $n$ is often much smaller than the total number of rules, making the approach highly efficient.\n\nThis enhanced heuristic improves scalability while preserving formal guarantees. Further, we exploit properties from Weighted A*, which uses weighted heuristics $w \\cdot h$. Using this approach, if the heuristic used is $h_{\\text{exact}}$, then the explanation cost is guaranteed to be bounded from above by $w \\cdot c^\\star$. When using $h_{\\text{greedy}}$, the cost is guaranteed to be bounded from above by $w \\cdot  (1+\\ln n) c^\\star$.\n\nBelow, we present a comparative table of average running times for all **five** heuristic variants evaluated across different model sizes: the original heuristic (same in Generic) $h_{\\text{original}}$, the new exact admissible heuristic $h_{\\text{exact}}$, the greedy heuristic $h_{\\text{greedy}}$, the weighted exact heuristic ($w \\times h_{\\text{exact}}$), and the weighted greedy heuristic ($w \\times h_{\\text{greedy}}$), where we set $w = 2$ in experiments.\n\n*Note: Due to space constraints, we only report results under Case 2, which involves higher complexity compared to Case 1. For each configuration, we generate 100 Agent–Human model pairs. A time limit of 600 seconds is imposed per run; “t/o” indicates a timeout, and “–” denotes that all runs timed out.*\n|Agent Facts|Agent Rules|Human Complexity|$h_{\\text{original}}$(ms)|$h_{\\text{exact}}$(ms)|$h_{\\text{greedy}}$(ms)|$2\\times h_{\\text{exact}}$(ms)|$2\\times h_{\\text{greedy}}$(ms)|\n|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|\n|10|5|20%|29.1|32.2|31.0|32.7|35.6|\n|||40%|29.1|32.2|30.9|33.1|37.8|\n|||60%|29.1|32.1|31.1|34.3|35.8|\n|||80%|28.9|31.9|30.7|35.8|39.2|\n|20|10|20%|29.5|32.5|30.9|33.0|36.3|\n|||40%|29.6|32.8|30.9|32.8|36.1|\n|||60%|29.7|32.4|31.2|33.6|41.6|\n|||80%|29.9|32.6|31.5|33.9|40.0|\n|50|25|20%|77.7|32.2|33.2|33.4|36.5|\n|||40%|279.4|34.3|33.2|34.5|37.5|\n|||60%|384.7|47.7|36.1|40.5|43.6|\n|||80%|4154.6|112.0|42.4|70.9|40.8|\n|100|50|20%|37420.0 (5 t/o)|37.7|38.8|36.5|38.2|\n|||40%|98684.2 (38 t/o)|247.7|47.6|116.8|40.0|\n|||60%|124163.4 (55  t/o)|3612.2|73.6|1997.1|45.1|\n|||80%|69932.6 (47  t/o)|9658.6 (1  t/o)|139.9|3407.89 (1 t/o)|53.04|\n|1000|500|20%|-|-|104469.1 (56 t/o)|-|889.1|\n|||40%|-|-|-|-|3122.3|\n|||60%|-|-|-|-|7554.6|\n|||80%|-|-|-|-|18936.6|\n\nWe observe that the new variant with $h_{\\text{exact}}$ consistently achieves lower runtime compared to the original A*, while maintaining correctness. All the approximate variants with inadmissible heuristics (i.e., $h_{\\text{greedy}}$, $w \\times h_{\\text{exact}}$, and $w \\times h_{\\text{greedy}}$) yield suboptimal solutions within their theoretical bounds.\n**Furthermore, in large-scale settings where the exact variant times out, the approximate variants remain tractable and effective. More importantly, this framework also allows one to use larger weights $w$ if necessary to scale to even larger problems.** We will include these results in the revised version. \n\n\n**_Q2: Experimental evaluation is weak; dataset and task need clarification. Interpretability should be discussed._**\n\nA2: ***Interpretability*** is a key focus of our work. Each explanation in our framework corresponds to a small and meaningful model update, such as changing the probability of a fact or deleting a rule. These updates have clear semantic meaning and are designed to reflect beliefs that a human can easily understand.\n\nTo evaluate this, we designed a human-subject study described in Section 6.1. **The full study materials and instructions are included in the supplementary materials.**\n\n**Study Setup.** The study takes place in a smart warehouse scenario, where the AI agent, Blitzcrank, decides to execute a delivery task, which corresponds to a query in our model. However, the human operator holds conflicting prior beliefs and would have chosen not to execute the task. For example, the operator may believe:\n* _“Item A is highly likely to require additional inspection.”_ (fact-level belief)\n* _“The task should only be executed if Item B is part of a high-priority order.”_  (rule-level belief)\n\n**Explanations Provided and Compared.** \nParticipants are shown candidate explanations generated by Blitzcrank to justify why the task should be executed. Each explanation corresponds to a specific type of model update. For instance:\n* **Explanation 1**: _“Item B is highly likely to be part of a high-priority order, whereas it was initially considered much less likely.”_ (change-probability)\n* **Explanation 2**: _“The assumption that the task should only be executed when Item B is part of a high-priority order is inaccurate.”_ (delete-rule)\n* **Explanation 3**: _“The loading zone is unlikely to be congested and the task can also be executed if the zone has space available.”_ (add-fact and add-rule)\n\n_Note that the labels in parentheses indicate the corresponding update actions in the model. These were not shown to participants and are included here only for clarification._\n\nParticipants are asked to take the perspective of the human operator and compare pairs of explanations (e.g., Explanation 1 vs. Explanation 2). For each pair, they answer the question: \"If you were the operator, which explanation would you prefer to receive from Blitzcrank?\"\n\n**Evaluation.** To analyze the results, we use the Bradley–Terry model to estimate the relative cognitive cost of each explanation type based on the pairwise preferences collected.\n\nOur  ***computational*** evaluation complements the user study by assessing scalability and runtime on synthetic agent-human model pairs, as described in Section 6.2. Since there is no existing benchmark dataset for this task, we generate the models using a logic-driven process inspired by Example 2 in our paper. We vary the number of facts and rules in the agent model and introduce controlled differences to simulate the kinds of belief divergences a human might have. We will clarify this procedure and include additional examples in the revised version.\n\n**_Q3: The approach is reminiscent of FORTE framework and its probabilistic extension._**\n\nA3: We appreciate the reviewer’s observation. FORTE and its probabilistic extension PFORTE follow the theory revision from examples paradigm. They start with an initial logical model and iteratively fix errors using operations like deleting rules or adding conditions, aiming to improve classification accuracy through small, step-by-step adjustments.\n\nOur framework, by contrast, has a different goal. While FORTE and PFORTE repair models after observing mistakes, we focus on reconciling differences between two probabilistic models: one agent model and one human model. Instead of correcting predictions, we generate minimum-cost explanations that clarify why the agent’s behavior is reasonable. Each model update has a cost, and we use A*-based search to find the explanation that is both logically valid and cognitively aligned.\n\nWe will clarify this distinction and cite relevant work in the revised Related Work section.\n\n**_Q4: Scalability and reliance on the current dataset are potential limitations._**\n\nA4: Regarding scalability, our framework supports both exact and approximate explanation generation using A*-based search. The approximate variants leverage enhanced heuristics that significantly reduce runtime while producing suboptimal explanations within theoretical bounds, as demonstrated in our updated results (see A1). These variants remain effective even when exact search becomes infeasible, making the framework robust to larger models.\n\nFor the dataset, we note that there is currently no established benchmark for probabilistic model reconciliation. To enable controlled and systematic evaluation, we generate agent–human model pairs (see Example 2 in our paper) using a logic-based process with configurable complexity and model differences. This setup allows us to simulate a wide range of reconciliation scenarios and evaluate performance in a reproducible way. We will clarify this in the revised version.\n\nFinally, the framework is general and supports personalization: if user preferences are known, the cost model can be adapted to produce more user-aligned explanations."}, {"review_id": "rYQv0QdZe1", "reviewer": "Reviewer_abKX", "summary": "This paper studies the model reconciliation problem as explanation generation under probabilistic logic programming (PLP). It extends the existing work on deterministic/stochastic planning models to a PLP setting where model is specified as facts and rules associated with their respective probabilities. The goal is to reconcile between two models by explaining their differences such that a specific query becomes consistent across the two models while minimizing the cost of the explanation, captured as changed probability, added fact/rule, etc. Two search methods are proposed where the first is a systemic search through the entire solution space while the second allows limited pruning to expedite the search. The proposed method is evaluated via a user study that analyzes the weights of different explanation types on the user as well as computational evaluations showing the effectiveness of the proposed search methods.", "questions": "1. Is there any reason why the generated explanations are not directly compared with simple baselines for effectiveness (such as explaining facts and rules that differ in the two models and are most relevant to the query)? This can be done both with human studies and via computational evaluations and would provide direct evidence to support the proposed method. \n\n2. Can you better motivate model reconciliation as explanation generation under PLP? Why do you believe PLP is better suited for model reconciliation? Why is considering such probabilistic modeling important? I am asking these since PLP may be considered even less intuitive for human understanding than planning models, such as PDDL. \n\n3. What are the explanations being compared in the human study? Can you explain the evaluation process in more detail? How are the costs estimated? Do you expect the estimated costs to be generalizable?", "limitations": "The key limitation here is the lack of direct evaluation of the generated explanations, which is critical to establish the effectiveness of the proposed method. The fact that the authors are aware unfortunately does not alleviate the concern.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\n1. The paper addresses a gap in model reconciliation as explanation generation. \n2. The paper is well structured and clearly written.  \n3. The technical contribution seems sound and useful. \n\nWeaknesses:\n\n1. The motivation for studying model reconciliation under PLP could be strengthened. The current motivation orients around what is not done instead of why it should be done. \n2. The proposed search methods are generally intractable even with pruning. \n3. The evaluation via human-user study is missing details and does not provide a convincing argument for the effectiveness of the  explanations generated in the real-world. \n4. The proposed search methods are for one-shot explanation generation. Interaction of multiple explanations is not addressed, which would make it more relevant to real-world scenarios. \n5. The proposed are mainly search methods that are perhaps better suited for AAAI, IJCAI, etc.", "was_revised": true, "final_justification": "While I agree with the authors that model reconciliation under PLP can be a valuable contribution, especially under Bayesian theory of mind (my original comment was to encourage the authors to better connect with relevant studies in cognitive science), I do not agree with the claim that a direct evaluation with user studies is orthogonal. While reviewing the paper, I was surprised that the authors leveraged a user study to estimate weights for the different types of explanations instead of evaluating the effectiveness of the explanations (even better if evaluating with the estimated weights). \n\nHaving said that, I consider the work a good addition to the model reconciliation line of work. Trusting the authors' commitment to incorporating the additional heuristic that would alleviate the computational concern (which was however not included in the original submission), I would consider it to good contribution to NeurIPS. Hence, I have adjusted my rating to \"weak accept\".", "rebuttal": "Thank you very much for the comments! Our responses to your questions are below.\n\n_**Q1:**_ In fact, our Generic method can serve as a reasonable baseline for comparison. When explanation cost is not considered, it can produce any explanation that resolves the inconsistency, including a _**simple baseline**_ that lists differences in facts and rules between the two models that seem relevant to the query.\n\nHowever, as shown in Theorem 2, not all such differences are actually helpful for reconciliation. For example, changing the probability of a fact from 0.4 to 0.3 might have no effect on the MPE result, yet a simple baseline would still include it. This often leads to explanations that are overly long and include changes that make little difference, especially when there are many facts and rules in the model.\n\nOur method addresses this by focusing on explanations that are truly necessary to resolve the disagreement while keeping the cost as low as possible. This leads to explanations that are shorter, clearer, and more effective at helping the human and the agent reach the same understanding.\n\n_**Q2:**_  Because both the agent and the human may have uncertain or incomplete beliefs about the world, we adopt probabilistic methods to represent this uncertainty. In particular, PLP has proven effective for modeling uncertain knowledge in a structured and interpretable way. It has been successfully applied in domains such as diagnosis [1] and decision support [2].\n\nWe use PLP to represent the knowledge held by both the agent and the human. The goal is **NOT** to simulate human reasoning but to provide a formal modeling language for representing their beliefs. Similar to how PDDL is used in planning, PLP allows us to express assumptions and dependencies in a declarative form. It offers a good balance of expressivity, interpretability, and compactness, and is well suited for modeling complex probabilistic domains, including planning under uncertainty.\n\nMoreover, PLP naturally supports inference tasks like most probable explanation (MPE) and maximum a posteriori (MAP), which align with our goal of generating concise and meaningful explanations that resolve belief differences. We will clarify this motivation in the revised version. \n\n_**Q3:**_ Please see our response to **Q2** of _**Reviewer azj8**_ for details on the types of explanations compared and the evaluation process. \n\nRegarding cost estimation, we fit a Bradley–Terry model based on pairwise human preferences. Each explanation is represented as a set of atomic model updates (e.g., change-probability, delete-rule), and participants are asked to compare pairs of explanations and select the one they find more understandable.\n\n**Illustrative Example.** Suppose 100 participants compare the following two explanations:\n* **E1**: _“Item B is highly likely to be part of a high-priority order, whereas it was initially considered much less likely.”_ (change-probability)\n* **E2**: _“The assumption that the task should only be executed when Item B is part of a high-priority order is inaccurate.”_ (delete-rule)\n\nAssume 70 participants preferred E1, and 30 preferred E2. Let the latent utility parameters for these explanation types be $\\beta_{cp}$ (change-probability) and $\\beta_{dr}$ (delete-rule), respectively.\nUnder the Bradley–Terry model, the probability that the participant prefers one explanation over another is defined as:\n$$P(cp \\succ dr)=\\frac{e^{\\beta_{cp}}}{e^{\\beta_{cp}} + e^{\\beta_{dr}}}=\\frac{70}{100}.$$\n\nTo fit the model, we _maximize the log-likelihood_ of observed preferences, i.e., \n$$\\log L=70 \\cdot \\log(\\frac{e^{\\beta_{cp}}}{e^{\\beta_{cp}} + e^{\\beta_{dr}}})+30\\cdot\\log( \\frac{e^{\\beta_{dr}}}{e^{\\beta_{cp}} + e^{\\beta_{dr}}})$$\n\nOnce the $\\beta$ values are learned, the cognitive cost of each update type $f$ is computed as: $\\text{Cost}(f) = e^{-\\beta_f}$.\nThis formulation ensures an intuitive interpretation: explanation types with higher perceived utility (i.e., preferred more often, higher $\\beta$) are assigned lower cognitive costs. These learned costs are then integrated into our reconciliation framework to guide the selection of preferred explanation types.\n\n**Generalizability.** Our current cost estimates are based on user preferences collected in a smart warehouse scenario. They reflect how people in that context perceive the effort of understanding different explanation types.\n\nWe do not assume these costs apply to all domains or users. However, our framework is flexible: the cost model can be adjusted when new preference data is available. In this sense, the current estimates are just one example of how the method can be applied.\n\nIn future work, we plan to study how explanation preferences vary across domains and individuals, and how to adapt explanation generation accordingly.\n\nWe will clarify all these parts in the revised version.\n\n_**Q4: The proposed search methods are generally intractable even with pruning.**_\n\nA4:  We acknowledge that the overall problem is theoretically intractable. In particular, computing a cost-optimal explanation that aligns the agent and human models under MPE semantics is NP-hard, due to the combinatorial nature of model changes and their interactions. Even verifying the optimality of a given explanation requires comparing it against an exponential number of possible alternatives. Moreover, computing an MPE under probabilistic logic programming is known to lie in the $\\Sigma_2^P$ complexity class, which is harder than NP-complete and requires reasoning via NP oracles. We will clarify this complexity in the revised version.\n\nWhile the general problem is indeed intractable in the worst case, our proposed framework incorporates several non-trivial strategies to ensure practical tractability. _**Reviewer  azj8**_ also had the same concern and we responded in detail to them (see our response to their **Q1**). We briefly describe them here again for convenience.\n\nFirst, the optimized A* search introduces aggressive pruning based on theoretical insights (e.g., DNF clause filtering, Theorem 2), which significantly reduces the effective search space compared to the generic version.\n\nSecond, we introduce new admissible heuristics that are tighter than the original, leading to faster convergence in exact-optimal search. More importantly, we provide bounded-approximate variants using greedy heuristics with provable guarantees (within $(1+\\ln n)$ of the optimal cost), which scale well even on large instances.\n\nAs shown in our new results, the greedy strategies remain efficient and yield suboptimal explanations in cases where exact A* may time out. These improvements go beyond standard pruning and make the framework practically scalable. We will clarify the complexity landscape and our strategies in the revised version.\n\n_**Q5: The proposed search methods are for one-shot explanation generation. Interaction of multiple explanations is not addressed, which would make it more relevant to real-world scenarios.**_\n\nA5: Thank you for the suggestion. \nOur work represents an important _**first step**_ toward probabilistic model reconciliation by formalizing one-shot explanation generation under MPE semantics. This mirrors the trajectory of prior work in deterministic model reconciliation, which began with one-shot [3] formulations before progressing to multi-shot [4] and learning-based variants [5].\n\nOur framework is compatible with such extensions. In particular, the cost model we propose can be adapted or personalized over time based on user interaction data, enabling explanation generation to evolve dynamically across multiple rounds. We will clarify this potential for extension in the revised version.\n\n_**References**_\n\n[1] \"SimPLoID: Harnessing Probabilistic Logic Programming for Infectious Disease Epidemiology.\" Weitkämper et al., arXiv preprint, 2023. \n\n[2] \"Intention Recognition with ProbLog.\" Smith et al., in Frontiers in Artificial Intelligence, 2022.\n\n[3] \"Model Reconciliation in Logic Programs.\" Son et al., in Proceedings of JELIA, 2021.\n\n[4] \"Dialectical Reconciliation via Structured Argumentative Dialogues.\" Vasileiou et al., in Proceedings of KR, 2024.\n\n[5] \"Does Your AI Agent Get You? A Personalizable Framework for Approximating Human Models from Argumentation-based Dialogue Traces.\" Tang et al., in Proceedings of AAAI, 2025."}, {"review_id": "te9tvUbNXl", "reviewer": "Reviewer_mmqa", "summary": "In this paper, the authors consider the problem of reconciling two\nmodels that are specified as probabilistic logic programs. More\nprecisely, the authors consider the notion of most probable\nexplanation (MPE), which, for a query q and a probabilistic logic\nprogram M, is denoted by MPE(q | M). Then, two probabilistic logic\nprograms M_1 and M_2 are said to be consistent with respect to a query\nq if either Pr(MPE(q | M_1)) > Pr(MPE(not q | M_1)) and Pr(MPE(q |\nM_2)) < Pr(MPE(not q | M_2)), or the other way around. That is, M_1\nand M_2 have opposite evidence for the queries q and not q. The goal\nof this paper is to solve this type of inconsistencies.\n\nThe authors provide a formal definition of what it means to solve an\ninconsistency for two probabilistic logic programs M_1 and M_2,\nwhich is based on the idea of removing and adding facts and rules in one of these\nprograms. They introduce a cost measure for such updates, which are\ncalled P-MRP explanations. Moreover, they define the problem of\ncomputing an optimal P-MRP explanation for an inconsistency between\nprobabilistic logic programs, that is, a P-MRP explanation of minimal\ncost. Finally, they provide a generic search algorithm and an\noptimized search algorithm, and an experimental evaluation showing\nsome advantages of the optimized version.", "questions": "Q1 What is the complexity of the optimized search algorithm?", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\nS1 Model reconciliation is a fundamental problem for which this paper\nproposes a more principled approach based on formalizing the problem\nand proposing a solution based on probabilistic logic programming.\n\nWeaknesses:\n\nW1 The paper works under the assumption that probabilistic logic\nprogramming is an appropriate model to formalize user models, but it\ndoes not provide clear evidence for this assumption.\n\nW2 The two algorithms proposed in the paper are based on usual\ntechniques, and they do not provide a deep insight into how model\nreconciliation should be done.\n\nW3 The paper does not study the complexity of the problem of computing\noptimal P-MRP explanations. In particular, it does not provide any\nlower bounds for this problem, which could help to understand how\ngood the optimized search algorithm proposed in the paper is.", "was_revised": true, "final_justification": "My impression of the paper has improved after all the discussions. I am increasing my final score, although there are still some concerns about its contributions.", "rebuttal": "Thank you for your thoughtful feedback. We appreciate your careful reading and respond to the key concerns below.\n\n_**Q1: The paper assumes PLP is suitable for modeling user models, but this is not justified.**_\n\nA1: Because both the agent and the human may have uncertain or incomplete beliefs about the world, we adopt probabilistic methods to represent this uncertainty. In particular, PLP has proven effective for modeling uncertain knowledge in a structured and interpretable way. It has been successfully applied in domains such as diagnosis [1] and decision support [2].\n\nIn our work, PLP serves as a formal modeling language for representing the knowledge of both the agent and the human. The goal is **NOT** to simulate human reasoning, but rather to express the assumptions, dependencies, and uncertainties in a clear and compact way. PLP offers a good balance between expressivity, interpretability, and conciseness, making it suitable for modeling complex probabilistic domains.\n\nMoreover, PLP naturally supports inference tasks like most probable explanation (MPE) and maximum a posteriori (MAP), which align with our goal of generating concise and meaningful explanations that resolve belief differences. We will clarify this motivation in the revised version.\n\n_**Q2: No complexity or lower bound analysis is provided for computing optimal P-MRP explanations.**_\n\nA2: In particular, computing a cost-optimal explanation that aligns the agent and human models under MPE semantics is NP-hard, due to the combinatorial nature of model changes and their interactions. Even verifying the optimality of a given explanation requires comparing it against an exponential number of possible alternatives. Moreover, computing an MPE under probabilistic logic programming is known to lie in the $\\Sigma_2^P$ complexity class, which is harder than NP-complete and requires reasoning via NP oracles. We will clarify this complexity in the revised version.\n\n_**Q3: The proposed algorithms use standard techniques and offer limited insight into reconciliation.**_\n\nA3: We would like to clarify that while our methods build upon the general A* framework, our contributions go _**significantly**_ beyond standard applications. We introduce a novel formulation of probabilistic model reconciliation under MPE semantics, with cost-optimal explanations over PLP-based models, and develop tailored algorithms that incorporate theoretical, algorithmic, and human-centered insights.\n\nIn particular:\n* We are the _**first**_ to formally define model reconciliation under _uncertainty_, specifically targeting inconsistencies in MPE outcomes between agent and human ProbLog models.\n* While the general problem is intractable in the worst case (See A2), our framework incorporates several non-trivial strategies to ensure practical efficiency (see our response to  _**Q1**_  of  _**Reviewer azj8**_ for details): \n  - Our optimized A* search incorporates principled pruning based on theoretical insights such as DNF clause filtering and Theorem 2, which significantly reduces the effective search space compared to the generic version.\n  - We propose tighter admissible heuristics for exact-optimal search and bounded-suboptimal greedy heuristics with formal $(1 + \\ln n)$-approximation guarantees. These heuristics scale efficiently, even in large models where exact A* may time out.\n\n  These improvements go beyond standard pruning techniques and enable our framework to achieve both scalability and theoretical guarantees.\n*  We also ground our cost model in a human-subject study, where explanation types (e.g., change-probability, delete-rule are evaluated via pairwise preference comparisons and modeled using the Bradley–Terry framework. This enables the system to generate explanations that are both logically valid and cognitively aligned with user preferences.\n\nTaken together, our approach contributes algorithmic, theoretical, and human-centric advances to the problem of model reconciliation under uncertainty. We will clarify and highlight these contributions more explicitly in the revised version.\n\n_**References**_\n\n[1] \"SimPLoID: Harnessing Probabilistic Logic Programming for Infectious Disease Epidemiology.\" Weitkämper et al., arXiv preprint, 2023. \n\n[2] \"Intention Recognition with ProbLog.\" Smith et al., in Frontiers in Artificial Intelligence, 2022."}, {"review_id": "whEE1tl06s", "reviewer": "Reviewer_y1CM", "summary": "This paper introduces a probabilistic model reconciliation framework for explainable AI using PLP. The work addresses a significant gap in existing model reconciliation approaches, which predominantly assume deterministic models and fail to account for the probabilistic nature of human beliefs. The authors propose a framework built on ProbLog that resolves inconsistencies in MPE outcome probabilities between an agent's and a human's models. They formalize explanations as cost-optimal model updates and develop two search algorithms—a generic exhaustive search and an optimized version guided by theoretical insights. The approach is validated through a user study examining cognitive costs of different explanation types and computational experiments demonstrating the optimized algorithm's superior performance.", "questions": "- How does the approach scale to real-world domains with hundreds or thousands of probabilistic facts? Can you provide analysis of the theoretical complexity bounds and discuss potential approximation strategies for large-scale problems?\n  \n- The framework assumes human models are consistent and well-calibrated. How would the approach handle inconsistent human beliefs or miscalibrated probabilities? What modifications would be needed to accommodate these realistic scenarios?\n  \n- The current framework focuses on MPE-based inconsistencies. How would the approach extend to other forms of probabilistic disagreement? Would the theoretical results still hold?\n  \n- While the user study provides initial cost estimates, how sensitive are the results to different cost functions? Have you considered learning personalized cost functions or adapting costs based on user feedback during interaction?\n  \n- How does your approach compare with adapting existing deterministic model reconciliation methods to handle probability distributions? What are the fundamental advantages of the PLP-based approach over such adaptations?", "limitations": "The authors adequately address several limitations in the conclusion, including the logic-based nature limiting real-world testing, assumptions about human model consistency, and scalability challenges. However, the discussion could be strengthened by:\n\n1. Providing more specific bounds on when the approach becomes computationally intractable\n  \n2. Discussing concrete approaches to handle inconsistent human models\n  \n3. Addressing how the framework might extend beyond ProbLog to other probabilistic reasoning systems\n  \n4. While mentioned, the discussion of potential manipulation through adaptive explanations could be more detailed\n  \n\nThe authors appropriately acknowledge that flawed agent models may reinforce incorrect beliefs and discuss the need for transparency and ethical design.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n\n1. This represents the first work to address model reconciliation in probabilistic settings using PLP. The integration of uncertainty into model reconciliation is novel and addresses a genuine limitation in existing deterministic approaches. The cost-based explanation framework with different modification types (change-probability, add-fact, add-rule, delete-rule) is new.\n  \n2. The paper demonstrates strong technical rigor with well-formulated definitions, theorems with complete proofs, and a principled approach to cost optimization. The theoretical foundation is solid.\n  \n3. The paper is generally well-written with clear mathematical formulations. The progression from background through problem formulation to algorithms is logical. Examples effectively illustrate key concepts, particularly Example 1 and Example 2.\n  \n4. The work tackles an important problem in human-AI interaction where probabilistic beliefs are prevalent. The framework has potential applications across domains requiring explainable AI with uncertain reasoning.\n  \n\n**Weaknesses:**\n\n1. The evaluation relies heavily on a controlled user study with a simple warehouse scenario. Real-world validation is absent, limiting confidence in practical applicability. The user study, while methodologically sound, involves only 100 participants and a single domain.\n  \n2. Despite the optimized algorithm's improvements, timeout issues persist in larger configurations. The exponential nature of the search space remains a fundamental limitation.\n  \n3. The framework assumes human models are consistent and well-calibrated, which may not hold in practice. The restriction to MPE-based inconsistencies may not capture all relevant forms of probabilistic disagreement.\n  \n4. The paper lacks comparison with alternative approaches to probabilistic explanation generation or adaptation of existing deterministic methods to probabilistic settings.", "was_revised": true, "final_justification": "The authors addressed most of my key concerns with clear technical clarifications. However, the introduction of new heuristic variants during the rebuttal phase without providing full methodological details affects the reproducibility and transparency of the work. Additionally, the limited number of participants and the use of a single domain in the experiments raise concerns about the generalizability of the results. Scalability issues persist as evidenced by timeouts in larger configurations, which impact the practical applicability of the method. Despite these unresolved issues, the authors’ responsiveness and the technical contributions presented warrant a positive score, though I encourage further improvements in methodological detail and experimental scope in the final version.", "rebuttal": "We thank the reviewers for their thoughtful feedback and careful evaluation. Below, we provide detailed responses to the key concerns raised.\n\n_**Q1:**_ Please see our response to  _**Q1**_ of _**Reviewer azj8**_ for scalability to hundreds or thousands of facts and approximation approaches. \n\nRegarding _complexity_, we clarify that computing a cost-optimal explanation that aligns the agent and human models under MPE semantics is NP-hard, due to the combinatorial nature of model changes and their interactions. Even verifying the optimality of a given explanation requires comparing it against an exponential number of possible alternatives. Moreover, computing an MPE under probabilistic logic programming is known to lie in the $\\Sigma_2^P$ complexity class, which is harder than NP-complete and requires reasoning via NP oracles. We will clarify this complexity in the revised version.\n\n_**Q2:**_ Our framework assumes that the **deterministic facts** in the human model are _logically consistent_, meaning atoms defined without a probability (as described in Section 3.1). These facts represent hard constraints that must always hold. For example, stating both $\\texttt{bird(tweety).}$ (Tweety is a bird) and $\\texttt{\\\\\\\\+bird(tweety).}$ (Tweety is not a bird) creates a direct contradiction. Including both in the same model makes it logically inconsistent, which may cause ProbLog to fail during grounding or inference. Therefore, deterministic knowledge is required to be internally consistent.\n\nIn contrast, our framework can naturally handle _**inconsistencies in probabilistic beliefs**_, which are common in reasoning. For instance, a model might assign high probabilities to both $\\texttt{0.9::rain.}$ (it's very likely to rain) and $\\texttt{0.8::\\\\\\\\+rain.}$ (it's also very likely not to rain). While such beliefs appear contradictory, ProbLog treats them as _independent_ probabilistic events and can still compute meaningful outcomes (e.g., MPE).\n\nIn summary, while the deterministic part of the model must be consistent, our framework is designed to tolerate uncertainty and soft conflicts in probabilistic beliefs, thanks to the flexible semantics of probabilistic logic.\n\n_**Q3:**_ Thank you for the insightful question. While our current framework is specifically designed to identify and resolve MPE-based inconsistencies, the Generic approach is flexible and can be adapted to handle other forms of probabilistic disagreement, e.g., MAP-based queries or general threshold-based conditions (e.g., why $P(\\varphi) > \\theta$).\n\nHowever, it is important to note that the Optimized method presented in the paper is tailored specifically for MPE computations, due to the unique structure and properties of MPE-based reasoning. These optimizations cannot be directly applied to other forms of probabilistic disagreement and would require substantial redesign for the new query type.\n\nWe chose to focus on MPE-based inconsistencies because MPE captures what the model believes is the most likely complete picture of the world, rather than marginal probabilities over individual events. This type of explanation is more concrete and easier to interpret, especially when comparing how two models differ in their reasoning. It also aligns with how people naturally think since we often make decisions based on what we believe is most likely to happen. From the perspective of alignment, interpretability, and human-centered reasoning, MPE offers a clear and practical way to identify meaningful disagreements between the agent and the human.\n\n_**Q4:**_ Yes, explanation quality is sensitive to the underlying cost function, as it directly shapes which explanations are considered optimal. In our current work, we use cost estimates derived from a human-subject study in a smart warehouse domain to reflect how users perceive the cognitive effort of different explanation types. We do not assume these costs generalize across all domains or users, but our framework is flexible since new cost models can be substituted when additional preference data becomes available.\n\nIf a user’s preference costs are known in advance (e.g., from prior interactions or user profiles), they can be directly incorporated to generate more personalized, cognitively aligned explanations.\n\nAs a next step, we believe it is promising to adapt cost models dynamically through user interaction, as done in deterministic model reconciliation work that progressed from one-shot [1] to multi-shot [2] and learning-based [3] formulations. Our framework is compatible with such extensions and can support personalized reconciliation under uncertainty in future interactive settings.\n\n_**Q5:**_ A direct adaptation of deterministic reconciliation methods is not sufficient to handle uncertainty in probabilistic settings. In deterministic cases, differences between the agent and the human are typically binary. For example, they may disagree on whether an action is allowed or whether a condition holds. In contrast, probabilistic settings involve more subtle forms of disagreement. The agent and the human may both agree that something can happen, but they may differ in how likely they think it is or how strongly they believe a particular fact or rule. These are not simple yes-or-no differences; they reflect varying degrees of belief. As a result, we need more fine-grained, numerical explanations that deterministic methods are not equipped to provide. To address this, we develop a probabilistic model reconciliation framework that can capture and resolve such belief discrepancies.\n\nPLP offers a powerful way to represent uncertain knowledge in a structured and interpretable manner. It combines the expressiveness of logic with probabilistic reasoning, making it well suited for modeling belief differences between agents and humans. Unlike black-box statistical models, PLP provides a transparent framework for describing beliefs and how different facts and rules interact, making the reasoning process easier to understand and explain. Moreover, PLP supports inference tasks such as Most Probable Explanation (MPE) and Maximum a Posteriori (MAP), which align directly with our goal of generating concise and meaningful explanations under uncertainty. We will clarify this motivation further in the revised version.\n\n_**References**_\n\n[1] \"Model Reconciliation in Logic Programs.\" Son et al., in Proceedings of JELIA, 2021.\n\n[2] \"Dialectical Reconciliation via Structured Argumentative Dialogues.\" Vasileiou et al., in Proceedings of KR, 2024.\n\n[3] \"Does Your AI Agent Get You? A Personalizable Framework for Approximating Human Models from Argumentation-based Dialogue Traces.\" Tang et al., in Proceedings of AAAI, 2025."}]

Author rebuttal:

Meta-review: The work introduces model reconciliation (between an agent and a human) within the realm of probabilistic logic programming. The work's contributions are the formal definition of model reconciliation under uncertainty, theoretical analysis, algorithms for computation of human's reconciled model, and a cost model. The reviewers agree that the submission is well written and organized. Most reviewers expressed concerns about motivation to use PLP for model reconciliation, limited extent of empirical evaluation. Some reviewers also mentioned that the paper would be more appropriate to a general AI conference than to this venue.

The authors provided detailed and constructive feedback with theoretical explanations and empirical evidence during the discussion period, resolving some of the reviewers concerns, however other concerns remained, in particular the motivation to use PLP for model reconciliation and the extent of empirical evaluations. Since all reviewers recommend acceptance,  and the work is an interesting and refreshing view in the modern landscape of agent-human interaction, I second the reviewers' opinion.
Decision: Accept (poster)