Distance-Restricted Explanations: Theoretical Underpinnings & Efficient Implementation

Informal explainability methods can mislead decision-makers: The paper cites "comprehensive experimental and theoretical evidence" that informal approaches to explaining AI systems provide unreliable information, highlighting why rigorous methods matter for high-stakes applications like healthcare or criminal justice.

Logic-based explanations offer stronger guarantees but face scalability challenges: While logic-based XAI provides "the strongest guarantees of rigor," it struggles with computational complexity when applied to highly complex ML models, creating a trade-off between trustworthiness and practical usability.

Distance-restricted explanations offer a middle ground: This approach provides rigorous explanations that are guaranteed to be accurate when the input is sufficiently similar to a reference point, allowing for more scalable solutions while maintaining some formal guarantees—though this guarantee only holds within a limited "distance."

Explainability connects to adversarial robustness: The paper establishes that distance-restricted explainability is "tightly related with adversarial robustness," meaning that understanding how to explain AI decisions is connected to understanding how vulnerable those systems are to manipulation or attacks.

Scaling remains a critical barrier for trustworthy AI: Even with improved algorithms, "the number of inputs still represents a key limiting factor" for logic-based explainers, suggesting that deploying rigorous explainability at scale across diverse real-world applications remains an open challenge.