Model Reconciliation via Cost-Optimal Explanations in Probabilistic Logic Programming

We thank the reviewers for their thoughtful feedback and careful evaluation. Below, we provide detailed responses to the key concerns raised.

Q1: Please see our response to Q1 of Reviewer azj8 for scalability to hundreds or thousands of facts and approximation approaches.

Regarding 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.

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 $`bird(tweety).`$ (Tweety is a bird) and $`\\\\+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.

In 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 $`0.9::rain.`$ (it's very likely to rain) and $`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).

In 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.

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$).

However, 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.

We 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.

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.

If 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.

As 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.

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.

PLP 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.

References

[1] "Model Reconciliation in Logic Programs." Son et al., in Proceedings of JELIA, 2021.

[2] "Dialectical Reconciliation via Structured Argumentative Dialogues." Vasileiou et al., in Proceedings of KR, 2024.

[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.

Thank you very much for the comments! Our responses to your questions are below.

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.

However, 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.

Our 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.

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].

We 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.

Moreover, 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.

Q3: Please see our response to Q2 of Reviewer azj8 for details on the types of explanations compared and the evaluation process.

Regarding 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.

Illustrative Example. Suppose 100 participants compare the following two explanations:

• E1: “Item B is highly likely to be part of a high-priority order, whereas it was initially considered much less likely.” (change-probability)
• E2: “The assumption that the task should only be executed when Item B is part of a high-priority order is inaccurate.” (delete-rule)

Assume 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. Under the Bradley–Terry model, the probability that the participant prefers one explanation over another is defined as: $P(cp \succ dr)=\frac{e^{\beta_{cp}}}{e^{\beta_{cp}} + e^{\beta_{dr}}}=\frac{70}{100}.$

To fit the model, we maximize the log-likelihood of observed preferences, i.e., $\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}}})$

Once the $\beta$ values are learned, the cognitive cost of each update type $f$ is computed as: $\text{Cost}(f) = e^{-\beta_f}$. This 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.

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.

We 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.

In future work, we plan to study how explanation preferences vary across domains and individuals, and how to adapt explanation generation accordingly.

We will clarify all these parts in the revised version.

Q4: The proposed search methods are generally intractable even with pruning.

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

While 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.

First, 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.

Second, 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.

As 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.

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.

A5: Thank you for the suggestion. Our 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].

Our 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.

References

[1] "SimPLoID: Harnessing Probabilistic Logic Programming for Infectious Disease Epidemiology." Weitkämper et al., arXiv preprint, 2023.

[2] "Intention Recognition with ProbLog." Smith et al., in Frontiers in Artificial Intelligence, 2022.

[3] "Model Reconciliation in Logic Programs." Son et al., in Proceedings of JELIA, 2021.

[4] "Dialectical Reconciliation via Structured Argumentative Dialogues." Vasileiou et al., in Proceedings of KR, 2024.

[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.

Thank you for your thoughtful feedback. We appreciate your careful reading and respond to the key concerns below.

Q1: The paper assumes PLP is suitable for modeling user models, but this is not justified.

A1: 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].

In 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.

Moreover, 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.

Q2: No complexity or lower bound analysis is provided for computing optimal P-MRP explanations.

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

Q3: The proposed algorithms use standard techniques and offer limited insight into reconciliation.

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

In particular:

• We are the first to formally define model reconciliation under uncertainty, specifically targeting inconsistencies in MPE outcomes between agent and human ProbLog models.

• 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):

  • 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.
  • 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.

  These improvements go beyond standard pruning techniques and enable our framework to achieve both scalability and theoretical guarantees.

• 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.

Taken 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.

References

[1] "SimPLoID: Harnessing Probabilistic Logic Programming for Infectious Disease Epidemiology." Weitkämper et al., arXiv preprint, 2023.

[2] "Intention Recognition with ProbLog." Smith et al., in Frontiers in Artificial Intelligence, 2022.

Thank you for the helpful and constructive comments. We appreciate your suggestions and address them below.

Q1: Only naive and $A^*$ are explored; other methods (e.g., Monte Carlo, MaxSAT) can be considered.

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

We 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.

In 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.

• 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.
• 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.

This 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$.

Below, 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.

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.

We 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. 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.

Q2: Experimental evaluation is weak; dataset and task need clarification. Interpretability should be discussed.

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

To 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.

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:

• “Item A is highly likely to require additional inspection.” (fact-level belief)
• “The task should only be executed if Item B is part of a high-priority order.” (rule-level belief)

Explanations Provided and Compared. Participants 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:

• 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)
• 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)
• 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)

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.

Participants 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?"

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.

Our 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.

Q3: The approach is reminiscent of FORTE framework and its probabilistic extension.

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

Our 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.

We will clarify this distinction and cite relevant work in the revised Related Work section.

Q4: Scalability and reliance on the current dataset are potential limitations.

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

For 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.

Finally, the framework is general and supports personalization: if user preferences are known, the cost model can be adapted to produce more user-aligned explanations.

Dear Authors

Thanks for your detailed reply, I understand the concern on efficiency and scalability,but I agree that more examples would be really helpful in motivating your work.