Model-Based Diagnosis (MBD) is widely used to identify minimal conflicts and repair actions in constraint-based systems. Recent advances in parallel reasoning have significantly reduced runtime in large-scale models through speculative and multicore execution strategies. However, existing approaches primarily focus on computational efficiency and implicitly assume that minimal diagnoses are inherently suitable explanations for human decision makers. In complex configuration environments, minimality does not necessarily imply interpretability, as diagnoses may involve structurally dispersed or semantically heterogeneous constraints. To address this limitation, this paper introduces a multi-objective explainability-aware framework for parallel MDB. Diagnosis selection is formulated as a Pareto optimization problem balancing total computational cost and a formally defined interpretability penalty. Interpretability is quantified using graph-based structural dispersion, semantic entropy, hierarchical complexity, and ambiguity metrics. The proposed E-ParetoDiag algorithm computes non-dominated diagnoses and identifies balanced knee-point solutions without modifying correctness guarantees of underlying diagnosis algorithms. Experimental evaluation on large-scale benchmark datasets demonstrates a measurable trade-off between runtime and interpretability, particularly in dense constraint systems. Comparative analysis against classical selection strategies shows that the proposed approach reduces structural dispersion by up to 18% while increasing computational cost by only 7%. Statistical validation confirms that these improvements are significant (p < 0.01) in medium- and high-density scenarios. The results indicate that aggressive parallelism may improve computational efficiency while increasing explanation complexity, highlighting the need for multi-objective selection strategies. Overall, the proposed framework extends scalable symbolic reasoning toward a human-centered diagnosis paradigm and establishes a principled foundation for explainability-aware optimization in constraint-based systems.
Chacón-Luna et al. (Thu,) studied this question.