# Interpretability Guarantees with Merlin-Arthur Classifiers

arXiv: https://arxiv.org/abs/2206.00759 · HTML: https://mlsanity.com/paper/2206.00759/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 39 of its 63 references that are in the map.
- First posted on arXiv 1 Jun 2022.

## Builds on (most cited first, 30 of 39)

- [U-Net: Convolutional Networks for Biomedical Image Segmentation](https://mlsanity.com/paper/1505.04597/) (2015)
- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- ["Why Should I Trust You?": Explaining the Predictions of Any Classifier](https://mlsanity.com/paper/1602.04938/) (2016)
- [A Survey on Bias and Fairness in Machine Learning](https://mlsanity.com/paper/1908.09635/) (2019)
- [Interpretable Explanations of Black Boxes by Meaningful Perturbation](https://mlsanity.com/paper/1704.03296/) (2017)
- [Captum: A unified and generic model interpretability library for PyTorch](https://mlsanity.com/paper/2009.07896/) (2020)
- [Towards Robust Interpretability with Self-Explaining Neural Networks](https://mlsanity.com/paper/1806.07538/) (2018)
- [Fooling LIME and SHAP: Adversarial Attacks on Post hoc Explanation Methods](https://mlsanity.com/paper/1911.02508/) (2019)
- [AI safety via debate](https://mlsanity.com/paper/1805.00899/) (2018)
- [Unmasking Clever Hans Predictors and Assessing What Machines Really Learn](https://mlsanity.com/paper/1902.10178/) (2019)
- [European Union regulations on algorithmic decision-making and a "right to explanation"](https://mlsanity.com/paper/1606.08813/) (2016)
- [Rationalizing Neural Predictions](https://mlsanity.com/paper/1606.04155/) (2016)
- [Learning to Explain: An Information-Theoretic Perspective on Model Interpretation](https://mlsanity.com/paper/1802.07814/) (2018)
- [Real Time Image Saliency for Black Box Classifiers](https://mlsanity.com/paper/1705.07857/) (2017)
- [Explanations can be manipulated and geometry is to blame](https://mlsanity.com/paper/1906.07983/) (2019)
- [Explaining individual predictions when features are dependent: More accurate approximations to Shapley values](https://mlsanity.com/paper/1903.10464/) (2019)
- [Abduction-Based Explanations for Machine Learning Models](https://mlsanity.com/paper/1811.10656/) (2018)
- [Explaining Image Classifiers by Counterfactual Generation](https://mlsanity.com/paper/1807.08024/) (2018)
- [A Symbolic Approach to Explaining Bayesian Network Classifiers](https://mlsanity.com/paper/1805.03364/) (2018)
- [Invariant Rationalization](https://mlsanity.com/paper/2003.09772/) (2020)
- [Interpretable Neural Predictions with Differentiable Binary Variables](https://mlsanity.com/paper/1905.08160/) (2019)
- [Stabilizing Training of Generative Adversarial Networks through Regularization](https://mlsanity.com/paper/1705.09367/) (2017)
- [Counterfactual Explanations Can Be Manipulated](https://mlsanity.com/paper/2106.02666/) (2021)
- [Fooling Neural Network Interpretations via Adversarial Model Manipulation](https://mlsanity.com/paper/1902.02041/) (2019)
- [Rethinking Cooperative Rationalization: Introspective Extraction and Complement Control](https://mlsanity.com/paper/1910.13294/) (2019)
- [Shapley explainability on the data manifold](https://mlsanity.com/paper/2006.01272/) (2020)
- [Fairwashing Explanations with Off-Manifold Detergent](https://mlsanity.com/paper/2007.09969/) (2020)
- [Stabilizing Generative Adversarial Networks: A Survey](https://mlsanity.com/paper/1910.00927/) (2019)
- [On Explaining Decision Trees](https://mlsanity.com/paper/2010.11034/) (2020)

## Built on by (most cited first, 9 of 9)

- [Prover-Verifier Games improve legibility of LLM outputs](https://mlsanity.com/paper/2407.13692/) (2024)
- [Object Centric Concept Bottlenecks](https://mlsanity.com/paper/2505.24492/) (2025)
- [Models That Prove Their Own Correctness](https://mlsanity.com/paper/2405.15722/) (2024)
- [How to Avoid Debate: Scalable AI Safety via Doubly-Efficient Interactive Proofs](https://mlsanity.com/paper/2607.03561/) (2026)
- [Hardness of Deceptive Certificate Selection](https://mlsanity.com/paper/2306.04505/) (2023)
- [Neural Concept Verifier: Scaling Prover-Verifier Games via Concept Encodings](https://mlsanity.com/paper/2507.07532/) (2025)
- [Bounding Hallucinations: Merlin-Arthur Protocols for Mutual-Information Bounds in Language Models](https://mlsanity.com/paper/2512.11614/) (2025)
- [Learn from A Rationalist: Distilling Intermediate Interpretable Rationales](https://mlsanity.com/paper/2601.22531/) (2026)
- [On the Monitorability of Natural Language Autoencoders: Identification vs Discrimination](https://mlsanity.com/paper/2610.18727/) (2026)

## Abstract (arXiv)

We propose an interactive multi-agent classifier that provides provable interpretability guarantees even for complex agents such as neural networks. These guarantees consist of lower bounds on the mutual information between selected features and the classification decision. Our results are inspired by the Merlin-Arthur protocol from Interactive Proof Systems and express these bounds in terms of measurable metrics such as soundness and completeness. Compared to existing interactive setups, we rely neither on optimal agents nor on the assumption that features are distributed independently. Instead, we use the relative strength of the agents as well as the new concept of Asymmetric Feature Correlation which captures the precise kind of correlations that make interpretability guarantees difficult. We evaluate our results on two small-scale datasets where high mutual information can be verified explicitly.