The Limits of AI Explainability: An Algorithmic Information Theory Approach

There are hard limits to how simple AI explanations can be: The paper proves that any explanation significantly simpler than the original AI model will necessarily make different predictions on at least some inputs. This means we cannot always have both highly accurate AI systems and truly simple explanations—there's a fundamental tradeoff that cannot be overcome through better engineering alone.

Explanation complexity explodes as AI systems handle more complex inputs: For AI systems processing high-dimensional data (like images or text), the paper shows that explanation complexity grows exponentially with the number of input dimensions. This suggests that explaining AI decisions becomes progressively harder as systems tackle more realistic, complex problems.

Local explanations are more feasible than global ones: The paper demonstrates that explaining an AI's decision for a specific case (local explanation) can be much simpler than explaining how the entire system works across all possible inputs (global explanation). This finding suggests focusing oversight efforts on explaining individual decisions rather than demanding complete system transparency.

Governance faces an impossible trilemma: The paper establishes a "regulatory impossibility theorem" proving that policymakers cannot simultaneously achieve three goals: allowing unrestricted AI capability development, ensuring human-interpretable explanations, and maintaining negligible error rates. Regulators must therefore make explicit tradeoffs between these objectives rather than assuming all three are achievable.

Current explainability expectations may be unrealistic: These theoretical limits suggest that some regulatory or public expectations for AI explainability may be mathematically impossible to satisfy, indicating a need to recalibrate what "explainable AI" can reasonably deliver.