Explaining Decisions in ML Models: a Parameterized Complexity Analysis

Explaining ML decisions is computationally hard, even for "transparent" models: The paper demonstrates that generating explanations for seemingly interpretable models like Decision Trees and Random Forests involves complex computational problems, meaning that transparency in model design alone doesn't automatically make explanations easy or fast to produce.

Different types of explanations have different complexity levels: The research distinguishes between abductive explanations (why a decision was made) and contrastive explanations (why one outcome occurred instead of another), showing that these require different computational approaches and may have vastly different difficulty levels—important for practitioners choosing which explanation types to prioritize.

Ensemble models compound explanation challenges: Random Forests and other ensemble methods, which combine multiple models, present significantly greater explanatory complexity than individual models, suggesting that the widespread use of ensembles in practice may create hidden barriers to meaningful transparency and accountability.

Theoretical foundations matter for responsible AI: By mapping the mathematical complexity of explanation problems, this work provides a scientific foundation for understanding when and why explanations can be reliably generated, helping organizations set realistic expectations about what transparency they can actually achieve in their AI systems.

Model architecture choices have accountability implications: The paper's analysis across different model types (Decision Lists, Boolean Circuits, etc.) suggests that AI developers should consider explainability complexity as a design criterion, not just accuracy, since some architecturally sound models may be inherently harder to explain to stakeholders.