![[2602.18160] Unifying Formal Explanations: A Complexity-Theoretic Perspective](https://arxiv.org/static/browse/0.3.4/images/arxiv-logo-fb.png){kind=logo}
[2602.18160] Unifying Formal Explanations: A Complexity-Theoretic Perspective
Summary
This paper presents a unified framework for understanding formal explanations in machine learning, focusing on the computational complexity of sufficient and contrastive reasons for model predictions.
Why It Matters
Understanding the complexity of explanations in machine learning models is crucial for improving model interpretability and trustworthiness. This study provides insights that could enhance the development of more efficient algorithms for generating explanations, which is vital in fields where decision-making is critical.
Key Takeaways
- Introduces a unified framework for analyzing sufficient and contrastive explanations in ML.
- Demonstrates the influence of monotonicity, submodularity, and supermodularity on computational complexity.
- Establishes polynomial-time results for global explainability settings across various ML models.
- Highlights the NP-hardness of local explainability computations, emphasizing the challenges in this area.
- Provides a deeper understanding of the properties affecting explanation generation in machine learning.
Computer Science > Machine Learning arXiv:2602.18160 (cs) [Submitted on 20 Feb 2026] Title:Unifying Formal Explanations: A Complexity-Theoretic Perspective Authors:Shahaf Bassan, Xuanxiang Huang, Guy Katz View a PDF of the paper titled Unifying Formal Explanations: A Complexity-Theoretic Perspective, by Shahaf Bassan and 2 other authors View PDF HTML (experimental) Abstract:Previous work has explored the computational complexity of deriving two fundamental types of explanations for ML model predictions: (1) *sufficient reasons*, which are subsets of input features that, when fixed, determine a prediction, and (2) *contrastive reasons*, which are subsets of input features that, when modified, alter a prediction. Prior studies have examined these explanations in different contexts, such as non-probabilistic versus probabilistic frameworks and local versus global settings. In this study, we introduce a unified framework for analyzing these explanations, demonstrating that they can all be characterized through the minimization of a unified probabilistic value function. We then prove that the complexity of these computations is influenced by three key properties of the value function: (1) *monotonicity*, (2) *submodularity*, and (3) *supermodularity* - which are three fundamental properties in *combinatorial optimization*. Our findings uncover some counterintuitive results regarding the nature of these properties within the explanation settings examined. For instance, although ...