Unifying Formal Explanations: A Complexity-Theoretic Perspective

• URL: http://arxiv.org/abs/2602.18160v1
• Date: Fri, 20 Feb 2026 11:52:26 GMT
• Title: Unifying Formal Explanations: A Complexity-Theoretic Perspective
• Abstract summary: We show that complexity of computations is influenced by three key properties of the value function.<n>We show that even highly simplified versions of these explanations become NP-hard to compute in the corresponding local explainability setting.
• Score: 9.350838775251075
• License: http://creativecommons.org/licenses/by/4.0/
• 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 the *local* value functions do not exhibit monotonicity or submodularity/supermodularity whatsoever, we demonstrate that the *global* value functions do possess these properties. This distinction enables us to prove a series of novel polynomial-time results for computing various explanations with provable guarantees in the global explainability setting, across a range of ML models that span the interpretability spectrum, such as neural networks, decision trees, and tree ensembles. In contrast, we show that even highly simplified versions of these explanations become NP-hard to compute in the corresponding local explainability setting.

Related papers

• Not All Explanations Simulate Equally: Comparing Verbalized Feature Attributions and Self-Generated Rationales [1.8772057593980798]
  This paper compares two families of explanations for question answering models: verbalized feature attributions and self-generated rationales.<n>We analyze how explanation source, verbalization strategy, and feature granularity affect the simulatability of explanations.
  arXiv  Detail & Related papers  (2026-05-31T10:35:35Z)
• Evaluating Local Explainability Metrics for Machine Learning Models on Tabular Data [1.423280626666929]
  An explanation can appear plausible to humans but fail to capture the internal reasoning of a model.<n>This paper studies the trustworthiness of local explainability techniques when applied to complex tabular classification tasks.
  arXiv  Detail & Related papers  (2026-05-26T19:38:10Z)
• Additive Models Explained: A Computational Complexity Approach [9.380879437204277]
  Generalized Additive Models (GAMs) are commonly considered *interpretable* within the ML community.<n>We analyze the *computational complexity* of generating different explanations for various forms of GAMs across multiple contexts.
  arXiv  Detail & Related papers  (2025-10-24T09:40:30Z)
• Exact Shapley Attributions in Quadratic-time for FANOVA Gaussian Processes [12.496136169054541]
  Shapley values are widely recognized as a principled method for attributing importance to input features in machine learning.<n>We show that the exact computation of Shapley values scales exponentially with the number of features.<n>Our work provides more scalable, axiomatically sound, and uncertainty-aware explanations for predictions generated by structured probabilistic models.
  arXiv  Detail & Related papers  (2025-08-20T07:39:14Z)
• Loss-Complexity Landscape and Model Structure Functions [53.92822954974537]
  We develop a framework for dualizing the Kolmogorov structure function $h_x(alpha)$.<n>We establish a mathematical analogy between information-theoretic constructs and statistical mechanics.<n>We explicitly prove the Legendre-Fenchel duality between the structure function and free energy.
  arXiv  Detail & Related papers  (2025-07-17T21:31:45Z)
• Internal Causal Mechanisms Robustly Predict Language Model Out-of-Distribution Behaviors [61.92704516732144]
  We show that the most robust features for correctness prediction are those that play a distinctive causal role in the model's behavior.<n>We propose two methods that leverage causal mechanisms to predict the correctness of model outputs.
  arXiv  Detail & Related papers  (2025-05-17T00:31:39Z)
• Hard to Explain: On the Computational Hardness of In-Distribution Model Interpretation [0.9558392439655016]
  The ability to interpret Machine Learning (ML) models is becoming increasingly essential. Recent work has demonstrated that it is possible to formally assess interpretability by studying the computational complexity of explaining the decisions of various models.
  arXiv  Detail & Related papers  (2024-08-07T17:20:52Z)
• Explaining Text Similarity in Transformer Models [52.571158418102584]
  Recent advances in explainable AI have made it possible to mitigate limitations by leveraging improved explanations for Transformers. We use BiLRP, an extension developed for computing second-order explanations in bilinear similarity models, to investigate which feature interactions drive similarity in NLP models. Our findings contribute to a deeper understanding of different semantic similarity tasks and models, highlighting how novel explainable AI methods enable in-depth analyses and corpus-level insights.
  arXiv  Detail & Related papers  (2024-05-10T17:11:31Z)
• A simple probabilistic neural network for machine understanding [0.0]
  We discuss probabilistic neural networks with a fixed internal representation as models for machine understanding. We derive the internal representation by requiring that it satisfies the principles of maximal relevance and of maximal ignorance about how different features are combined. We argue that learning machines with this architecture enjoy a number of interesting properties, like the continuity of the representation with respect to changes in parameters and data.
  arXiv  Detail & Related papers  (2022-10-24T13:00:15Z)
• Curvature-informed multi-task learning for graph networks [56.155331323304]
  State-of-the-art graph neural networks attempt to predict multiple properties simultaneously. We investigate a potential explanation for this phenomenon: the curvature of each property's loss surface significantly varies, leading to inefficient learning.
  arXiv  Detail & Related papers  (2022-08-02T18:18:41Z)
• Explainability in Process Outcome Prediction: Guidelines to Obtain Interpretable and Faithful Models [77.34726150561087]
  We define explainability through the interpretability of the explanations and the faithfulness of the explainability model in the field of process outcome prediction. This paper contributes a set of guidelines named X-MOP which allows selecting the appropriate model based on the event log specifications.
  arXiv  Detail & Related papers  (2022-03-30T05:59:50Z)
• Towards Unifying Feature Attribution and Counterfactual Explanations: Different Means to the Same End [17.226134854746267]
  We present a method to generate feature attribution explanations from a set of counterfactual examples. We show how counterfactual examples can be used to evaluate the goodness of an attribution-based explanation in terms of its necessity and sufficiency.
  arXiv  Detail & Related papers  (2020-11-10T05:41:43Z)
• The Struggles of Feature-Based Explanations: Shapley Values vs. Minimal Sufficient Subsets [61.66584140190247]
  We show that feature-based explanations pose problems even for explaining trivial models. We show that two popular classes of explainers, Shapley explainers and minimal sufficient subsets explainers, target fundamentally different types of ground-truth explanations.
  arXiv  Detail & Related papers  (2020-09-23T09:45:23Z)
• Automated and Sound Synthesis of Lyapunov Functions with SMT Solvers [70.70479436076238]
  We synthesise Lyapunov functions for linear, non-linear (polynomial) and parametric models. We exploit an inductive framework to synthesise Lyapunov functions, starting from parametric templates.
  arXiv  Detail & Related papers  (2020-07-21T14:45:23Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.