Research map / Learning theory and algorithms / Prediction and decision losses

Explaining, Fast and Slow: Abstraction and Refinement of Provable Explanations

ICML 2025 · Learning theory and algorithms › Prediction and decision losses · approach: Provable post-hoc explanations · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes an abstraction-refinement method that merges neurons in a neural network to build a smaller abstract network, computing provably sufficient and minimal explanations faster than verification on the original network.

Problem

Computing provably sufficient and minimal feature-subset explanations for neural networks requires many expensive verification queries, which does not scale to large networks.

Approach

Abstract the network by merging similar neurons into a reduced network whose sufficient explanations are provably sufficient for the original; when a counterexample is spurious, iteratively refine the abstraction (increasing reduction rate) until the explanation converges to a provably minimal one for the original network.

Key results

• Abstract+refine reduces computation time versus the standard greedy verification method by 41% (MNIST), 36% (CIFAR-10), and 56% (GTSRB).
• On MNIST, mean explanation size is 204.4 for the proposed method versus 408.7 for the standard method under a 100s timeout.
• Heuristic methods Anchors and SIS yield sufficient explanations for only 0-25% of inputs, while the proposed method achieves 100% provable sufficiency.

Measured effects reported in the paper

Surprising findings

• Heuristic explanations from Anchors and SIS are frequently not sufficient (0-25%), even though they are faster.

Limitations

• Depends on neural network verification queries, which remain limited in scalability for state-of-the-art models.
• Intermediate abstract explanations may not be minimal for the original network until refinement converges.
• Evaluated only on image classification benchmarks with small networks.

Experimental setup

Datasets: MNIST CIFAR-10 GTSRB

Benchmarks: MNIST CIFAR-10 GTSRB

Metrics: explanation size computation time sufficiency rate

Baselines: Standard verification-based minimal explanation search Anchors SIS

Builds on: neuron-merging abstraction for neural network verification minimal sufficient explanation search via verification (Wu et al. style) abductive/formal explanation

Closest papers by meaning

• Explainable Neural Networks with Guarantee: A Sparse Estimation Approach (AAAI 2025 · similarity 0.90)
• Towards Modeling Uncertainties of Self-Explaining Neural Networks via Conformal Prediction (AAAI 2024 · similarity 0.89)
• Beyond Topological Self-Explainable GNNs: A Formal Explainability Perspective (ICML 2025 · similarity 0.89)
• Explain Yourself, Briefly! Self-Explaining Neural Networks with Concise Sufficient Reasons (ICLR 2025 · similarity 0.89)
• SHAP Meets Tensor Networks: Provably Tractable Explanations with Parallelism (NeurIPS 2025 · similarity 0.88)
• GNNX-BENCH: Unravelling the Utility of Perturbation-based GNN Explainers through In-depth Benchmarking (ICLR 2024 · similarity 0.87)