Why informative explanations only exist for simple functions and what this means for the European AI Act

Explainable machine learning is often proposed as a tool to increase the transparency of machine learning systems and to satisfy requirements that might come with the European AI Act. However, to satisfy legal requirements, explanations should not merely appear plausible, but actually be reliable. To investigate when this is the case we introduce a mathematical framework that measures whether explanations are informative. Surprisingly, we find that most of the widely used post-hoc explanations are only informative if the underlying decision function is already simple. This questions the use of post-hoc explanations for complex machine learning models in a legal context. We suggest a path forward by augmenting explanations with concrete, valid interpretations. This can make explanations both formally informative and intuitively useful.