The Limits of AI Explainability: An Algorithmic Information Theory Approach

• URL: http://arxiv.org/abs/2504.20676v1
• Date: Tue, 29 Apr 2025 11:58:37 GMT
• Title: The Limits of AI Explainability: An Algorithmic Information Theory Approach
• Authors: Shrisha Rao,
• Abstract summary: This paper establishes a theoretical foundation for understanding the fundamental limits of AI explainability through algorithmic information theory.<n>We formalize explainability as the approximation of complex models by simpler ones, quantifying both approximation error and explanation using Kolmogorov.<n>Results highlight considerations likely to be relevant to the design, evaluation, and oversight of explainable AI systems.
• Score: 4.759142872591625
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper establishes a theoretical foundation for understanding the fundamental limits of AI explainability through algorithmic information theory. We formalize explainability as the approximation of complex models by simpler ones, quantifying both approximation error and explanation complexity using Kolmogorov complexity. Our key theoretical contributions include: (1) a complexity gap theorem proving that any explanation significantly simpler than the original model must differ from it on some inputs; (2) precise bounds showing that explanation complexity grows exponentially with input dimension but polynomially with error tolerance for Lipschitz functions; and (3) a characterization of the gap between local and global explainability, demonstrating that local explanations can be significantly simpler while maintaining accuracy in relevant regions. We further establish a regulatory impossibility theorem proving that no governance framework can simultaneously pursue unrestricted AI capabilities, human-interpretable explanations, and negligible error. These results highlight considerations likely to be relevant to the design, evaluation, and oversight of explainable AI systems.

Related papers

• ZebraLogic: On the Scaling Limits of LLMs for Logical Reasoning [92.76959707441954]
  We introduce ZebraLogic, a comprehensive evaluation framework for assessing LLM reasoning performance.<n>ZebraLogic enables the generation of puzzles with controllable and quantifiable complexity.<n>Our results reveal a significant decline in accuracy as problem complexity grows.
  arXiv  Detail & Related papers  (2025-02-03T06:44:49Z)
• On the Complexity of Quantum Field Theory [0.0]
  We show that from minimal assertions, one is naturally led to measure complexity by two integers, called format and degree. We discuss the physical interpretation of our approach in the context of perturbation theory, symmetries, and the renormalization group.
  arXiv  Detail & Related papers  (2024-10-30T18:00:00Z)
• 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)
• Modeling Hierarchical Reasoning Chains by Linking Discourse Units and Key Phrases for Reading Comprehension [80.99865844249106]
  We propose a holistic graph network (HGN) which deals with context at both discourse level and word level, as the basis for logical reasoning. Specifically, node-level and type-level relations, which can be interpreted as bridges in the reasoning process, are modeled by a hierarchical interaction mechanism.
  arXiv  Detail & Related papers  (2023-06-21T07:34:27Z)
• From Robustness to Explainability and Back Again [3.7950144463212134]
  This paper addresses the poor scalability of formal explainability and proposes novel efficient algorithms for computing formal explanations.<n>The proposed algorithm computes explanations by answering instead a number of queries, and such robustness that the number of such queries is at most linear on the number of features.
  arXiv  Detail & Related papers  (2023-06-05T17:21:05Z)
• Balancing Explainability-Accuracy of Complex Models [8.402048778245165]
  We introduce a new approach for complex models based on the co-relation impact. We propose approaches for both scenarios of independent features and dependent features. We provide an upper bound of the complexity of our proposed approach for the dependent features.
  arXiv  Detail & Related papers  (2023-05-23T14:20:38Z)
• A Parameterized Theory of PAC Learning [19.686465068713467]
  Probably Approximately Correct (i.e., PAC) learning is a core concept of sample complexity theory. We develop a theory of parameterized PAC learning which allows us to shed new light on several recent PAC learning results that incorporated elements of parameterized complexity.
  arXiv  Detail & Related papers  (2023-04-27T09:39:30Z)
• A simplicity bubble problem and zemblanity in digitally intermediated societies [1.4380443010065829]
  We discuss the ubiquity of Big Data and machine learning in society. We show that there is a ceiling above which formal knowledge cannot further decrease the probability of zemblanitous findings.
  arXiv  Detail & Related papers  (2023-04-21T00:02:15Z)
• MetaLogic: Logical Reasoning Explanations with Fine-Grained Structure [129.8481568648651]
  We propose a benchmark to investigate models' logical reasoning capabilities in complex real-life scenarios. Based on the multi-hop chain of reasoning, the explanation form includes three main components. We evaluate the current best models' performance on this new explanation form.
  arXiv  Detail & Related papers  (2022-10-22T16:01:13Z)
• From LSAT: The Progress and Challenges of Complex Reasoning [56.07448735248901]
  We study the three challenging and domain-general tasks of the Law School Admission Test (LSAT), including analytical reasoning, logical reasoning and reading comprehension. We propose a hybrid reasoning system to integrate these three tasks and achieve impressive overall performance on the LSAT tests.
  arXiv  Detail & Related papers  (2021-08-02T05:43:03Z)
• Parsimonious Inference [0.0]
  Parsimonious inference is an information-theoretic formulation of inference over arbitrary architectures. Our approaches combine efficient encodings with prudent sampling strategies to construct predictive ensembles without cross-validation.
  arXiv  Detail & Related papers  (2021-03-03T04:13:14Z)
• Fundamental Limits and Tradeoffs in Invariant Representation Learning [99.2368462915979]
  Many machine learning applications involve learning representations that achieve two competing goals. Minimax game-theoretic formulation represents a fundamental tradeoff between accuracy and invariance. We provide an information-theoretic analysis of this general and important problem under both classification and regression settings.
  arXiv  Detail & Related papers  (2020-12-19T15:24:04Z)
• A general framework for scientifically inspired explanations in AI [76.48625630211943]
  We instantiate the concept of structure of scientific explanation as the theoretical underpinning for a general framework in which explanations for AI systems can be implemented. This framework aims to provide the tools to build a "mental-model" of any AI system so that the interaction with the user can provide information on demand and be closer to the nature of human-made explanations.
  arXiv  Detail & Related papers  (2020-03-02T10:32:21Z)

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.