The Explainability Trilemma

Power, simplicity, or fidelity? Pick two.

This is Part 2 of a two-part series on explainability and assurance. Part 1 covered why every explanation is a simplification and what different methods trade away.

Last week I argued that every explanation method produces a compressed, simplified view of a model’s behaviour, and that the compression always discards something. For instance, perturbation methods explain a surrogate, not the model; gradient methods are exact at one point but fragile everywhere else; and attention weights show magnitude without direction. Each family of xAI methods trades away something different.

A natural follow-up is whether this is a temporary limitation that the xAI community may address, or a permanent one that cannot be solved. To put it another way, if current methods are imperfect, can future methods do better? Or is there a point where an explanation is too simple to be faithful, no matter how much computational effort you invest?

The answer, to the latter question, is yes. And the implications of this affirmative answer extend beyond methodology into regulation and governance, because several major frameworks implicitly assume otherwise.

The hard limit

In ‘The Limits of AI Explainability: An Algorithmic Information Theory Approach’, Shrisha Rao formalises what many practitioners have suspected but could not demonstrate.^[1] Using a branch of mathematics called algorithmic information theory, Rao establishes what he calls the Complexity Gap Theorem. The intuition is straightforward, even if the proof is not.

A modern machine learning model encodes a complex function. An explanation is a simpler representation of that function. If the explanation is genuinely simpler than the model (which it must be, if a human is to understand it), then there must exist some inputs where the explanation and the model disagree. The simpler the explanation, the larger the potential region of disagreement. The figure below illustrates this with two levels of simplification.

Figure 1. The solid line is a model’s actual behaviour across its input space. The dashed line is the explanation — a simpler approximation. The left panel shows a moderate simplification that tracks the model’s broad shape but misses fine detail. The right panel shows a greater simplification that captures only the overall trend. In both cases, the shaded coral regions show where the explanation and model disagree. The key observation: the simpler the explanation, the larger the disagreement regions. Illustrative functions — not derived from a real model.

This is not a claim about current methods being inadequate. No future explanation method, no matter how clever, can produce an explanation that is simultaneously simpler than the model and perfectly faithful to it across all possible inputs.^[2] Simplicity and perfect fidelity are in direct tension, and the tension is provable as a mathematical constraint. This means that the SHAP bar chart in your model card that shows feature importance cannot be both simple enough for a deployer to interpret and perfectly faithful to the model’s reasoning across all inputs. Somewhere in the input space, the explanation will give a different answer than the model. The question that needs to be asked is, “how often do the explanation and model diverge”, and whether it matters for your deployment context.

The trilemma

Rao extends this result into a direct challenge for AI governance frameworks. He proves a Regulatory Impossibility Theorem showing that no framework can simultaneously guarantee all three of the following:

1. Unrestricted model capability, allowing the most powerful AI systems to be deployed

2. Simple, human-interpretable explanations, requiring that explanations be comprehensible to non-technical stakeholders

3. Low explanation error, requiring that explanations faithfully represent the model’s actual behaviour

You can have any two, but not all three (Figure 3). If you want powerful models with simple explanations, you must accept explanation error. If you want powerful models with faithful explanations, the explanations will be complex (potentially as complex as the model itself). If you want simple and faithful explanations, you must constrain the model’s capability.

This is the explainability trilemma, a structural constraint, not a design challenge to be solved with better tooling, that governance frameworks need to acknowledge and manage if they are to have meaningful practical utility for development and procurement teams.

The distributional escape hatch

Before this starts to sound like the situation is hopeless, there is an important nuance. The Complexity Gap Theorem guarantees that a simpler explanation must disagree with the model somewhere in the full input space. It does not guarantee disagreement on the inputs that matter. Figure 2 illustrates this distinction.

Figure 2. The same model and explanation from Figure 1’s right panel. The green band marks the operational distribution — the range of inputs the system actually encounters in deployment. Within this window, the model and explanation agree closely. The coral disagreement regions from Figure 1 are still present, but they fall outside the operational window. The theorem guarantees disagreement somewhere, but it might not be where your system operates. Illustrative functions — not derived from a real model.

Consider a medical imaging model that classifies retinal scans. The model might encode subtle nonlinear interactions between features that only manifest for input combinations that never occur in clinical practice (e.g. physically impossible combinations of retinal measurements). A simpler explanation could be perfectly faithful across every clinically realistic input while diverging from the model only on inputs no clinician will ever encounter.

This distinction between worst-case fidelity (over all possible inputs) and distributional fidelity (over operationally relevant inputs) is where the theorem becomes practically useful instead of just being discouraging. The theorem tells you exactly what to check. That is, if your explanation is simpler than your model, there exists a region of disagreement, and your job is then to determine whether that region includes inputs your system will encounter in deployment.^[3]

But this escape hatch comes with conditions:

• The distributional fidelity claim holds only as long as the distribution holds.

• If operational conditions shift (e.g. a new patient population, a new sensor modality, an adversary deliberately pushing inputs into the disagreement region), the explanation that was faithful yesterday may be misleading today.

This makes distributional assumptions a first-class component of any assurance case that includes an explainability claim.

The trilemma regulators don’t acknowledge

This is not merely a theoretical concern for xAI researchers. Several major governance frameworks currently assume, implicitly or explicitly, that powerful AI systems can provide faithful and comprehensible explanations of their outputs. The trilemma says they cannot. We can consider three examples that illustrate the pattern:

1. The EU AI Act (Article 13) requires high-risk AI systems to be designed so that their operation is “sufficiently transparent to enable deployers to interpret a system’s output and use it appropriately.”^[4] The harmonised standards that are supposed to define what “sufficiently transparent” means in practice (being developed by CEN-CENELEC JTC 21) missed the original August 2025 target, and the Digital Omnibus package now proposes pushing high-risk obligations to December 2027. The delay has largely administrative and political causes, but the underlying difficulty remains: even when standards do arrive, defining “sufficient transparency” for powerful AI systems requires confronting a trade-off the legislation does not surface.

2. JSP 936 and the AI Practitioner’s Hub (UK MoD) require that relevant individuals “understand AI systems and their outputs” and that design choices be “justified and documented.”^[5] The recently published AI Practitioner’s Handbook operationalises this through mandatory model cards, a five-stage assurance lifecycle, and testing that generates evidence linked to identified risks.^[6] For defence applications, where AI systems may be highly capable and operate under real-time constraints, the trilemma bites hard. Safety case authors face a choice the current guidance does not acknowledge, namely whether to accept a less powerful model, accept explanations that operators cannot use under time pressure, or accept that the explanations carry approximation error that needs to be documented and bounded.

3. The FDA/Health Canada/MHRA joint guidance on transparency for ML-enabled medical devices comes closest to acknowledging the problem.^[7] It defines explainability as “the degree to which logic can be explained in a way that a person can understand” and requires manufacturers to communicate “how the AI model reaches outputs”, but qualifies this with “when this information is available and easily understood.” That “when available” caveat tacitly concedes that for some models, faithful and simple explanations may not be available. But the guidance does not provide a framework for managing the trade-off when they are not.

All three frameworks span different jurisdictions and domains (EU general regulation, UK defence, and international medical device guidance), but they share the same structural gap. None provides a principled approach for managing the trilemma (e.g. determining which leg to relax, by how much, and under what documented assumptions).

This is not necessarily a failure of intent. Regulators have good reasons to avoid prescribing specific explanation methods, giving development and procurement teams the flexibility to choose techniques appropriate to their context. But flexibility requires a shared framework for documenting the choices made and the trade-offs accepted. Without that framework, flexibility becomes ambiguity, and each organisation is left to manage the trilemma on its own terms — or, more likely, not to manage it at all.

Making the trade-off explicit

If the trilemma is unavoidable, the question for practitioners shifts from “how do we explain this model?” to “which trade-off are we making, and can we defend it?”

An assurance case that includes an explainability claim needs to document several things that current practice usually omits:

• Which leg of the trilemma has been relaxed, and by how much. If you are using a powerful model with simple post-hoc explanations, you have accepted explanation error. The assurance case should say so, and characterise that error where possible.

• The distributional assumptions under which the fidelity claim holds. What inputs are considered operationally relevant? What correlations in the data are assumed to hold? What would cause those assumptions to break?

• Monitoring requirements that follow from those assumptions. If fidelity depends on the input distribution staying within a defined envelope, you need mechanisms to detect when it drifts outside that envelope — and a plan for what happens when it does.

• The explanation’s role in the decision process. A saliency map used for post-incident review has different fidelity requirements than one used for real-time clinical decision-making. The acceptable level of explanation error depends on what the explanation is being used for.

None of this requires abandoning explanation methods. As I argued in Part 1, the point is not that explanations are useless — far from it — but that they should be treated with the same discipline as any other piece of evidence in an assurance case. The trilemma simply makes the stakes more precise. There is a mathematical floor on how faithful a simple explanation can be, and if your assurance case does not acknowledge that floor, it has an evidential gap.

Figure 3. The explainability trilemma. The three vertices represent model capability, explanation simplicity, and explanation fidelity. Each edge connects two properties you can have simultaneously, but only by relaxing the third (the opposite vertex). The annotations show the practical consequence of each trade-off and what your assurance case needs to document as a result.

The burden of proof

This two-part series has been about one question:

What does it mean to use an explanation as evidence?

Part 1 showed that every explanation method simplifies, and that the simplification discards something specific and identifiable. Part 2 shows that this is not a limitation of current methods but a structural feature of explanation itself. The mathematics of compression guarantees it.

For organisations building assurance cases focused on interpretability, transparency, or explainability, the practical implication is that specific property claims need the same evidential discipline as any other claim about a system. What method was used? What does it trade away? Under what distributional assumptions does the fidelity claim hold? What monitoring is in place to detect when those assumptions break?

Regulators are demanding explanations. Assurance requires understanding what those explanations can and cannot tell you. The gap between the two is where the real work lies.

---

This is the fourth edition of Burden of Proof, and Part 2 of a two-part series on explainability and assurance. Each week, I take one development in AI assurance and work through what it means in practice. If you found this useful, subscribe to get future posts delivered to your inbox.

---

1. Rao (2025), The Limits of AI Explainability: An Algorithmic Information Theory Approach. The Complexity Gap Theorem (Theorem 2.13) and the Regulatory Impossibility Theorem (Theorem 4.6) are the two central results. The framework uses Kolmogorov complexity to measure explanation simplicity. https://arxiv.org/abs/2504.20676↩︎

2. This is the old cartographic paradox made mathematically precise (i.e. a perfectly accurate map would need to be the same size as the territory, and at that point it would no longer be a map).↩︎

3. For a fuller treatment of the distributional vs worst-case fidelity distinction, and why it matters for operational AI systems, see the discussion of operational domain characterisation in Hawkins et al. (2021), A Guidance Framework for the Assurance of Machine Learning in Autonomous Systems, University of York.↩︎

4. EU AI Act, Article 13 — Transparency and provision of information to deployers. CEN-CENELEC JTC 21 is developing harmonised standards to operationalise the transparency requirements, but these missed the original August 2025 target. The Digital Omnibus on AI, proposed by the Commission in November 2025, would push high-risk obligations to December 2027; the Council and Parliament adopted positions in March 2026 and trilogue negotiations are ongoing. See the AI Act standards tracker for current status.↩︎

5. UK Ministry of Defence, JSP 936: Dependable AI in Defence, November 2024. Part 1 establishes “Understanding” as a core ethical principle and requires integration of AI-specific safety risks into broader safety cases.↩︎

6. Defence AI Centre, AI Practitioner’s Hub, February 2026. The companion guidance to JSP 936 Part 2, operationalising the policy through mandatory model cards, a five-stage assurance lifecycle, and structured evidence generation.↩︎

7. FDA, Health Canada, and MHRA, Transparency for Machine Learning-Enabled Medical Devices: Guiding Principles, June 2024.↩︎