# Guaranteed Optimal Compositional Explanations for Neurons

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 24 of its 43 references that are in the map.
- First posted on arXiv 25 Nov 2025.

## Builds on (most cited first, 24 of 24)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Densely Connected Convolutional Networks](https://mlsanity.com/paper/1608.06993/) (2016)
- [The Cityscapes Dataset for Semantic Urban Scene Understanding](https://mlsanity.com/paper/1604.01685/) (2016)
- [Sparse Autoencoders Find Highly Interpretable Features in Language Models](https://mlsanity.com/paper/2309.08600/) (2023)
- [Toy Models of Superposition](https://mlsanity.com/paper/2209.10652/) (2022)
- [Network Dissection: Quantifying Interpretability of Deep Visual Representations](https://mlsanity.com/paper/1704.05796/) (2017)
- [Scaling and evaluating sparse autoencoders](https://mlsanity.com/paper/2406.04093/) (2024)
- [Explaining Explanations: An Overview of Interpretability of Machine Learning](https://mlsanity.com/paper/1806.00069/) (2018)
- [Understanding the Role of Individual Units in a Deep Neural Network](https://mlsanity.com/paper/2009.05041/) (2020)
- [Compositional Explanations of Neurons](https://mlsanity.com/paper/2006.14032/) (2020)
- [CLIP-Dissect: Automatic Description of Neuron Representations in Deep Vision Networks](https://mlsanity.com/paper/2204.10965/) (2022)
- [Multifaceted Feature Visualization: Uncovering the Different Types of Features Learned By Each Neuron in Deep Neural Networks](https://mlsanity.com/paper/1602.03616/) (2016)
- [Identifying Interpretable Subspaces in Image Representations](https://mlsanity.com/paper/2307.10504/) (2023)
- [Labeling Neural Representations with Inverse Recognition](https://mlsanity.com/paper/2311.13594/) (2023)
- [PURE: Turning Polysemantic Neurons Into Pure Features by Identifying Relevant Circuits](https://mlsanity.com/paper/2404.06453/) (2024)
- [Disentangling Neuron Representations with Concept Vectors](https://mlsanity.com/paper/2304.09707/) (2023)
- [Linear Explanations for Individual Neurons](https://mlsanity.com/paper/2405.06855/) (2024)
- [HINT: Hierarchical Neuron Concept Explainer](https://mlsanity.com/paper/2203.14196/) (2022)
- [Towards a fuller understanding of neurons with Clustered Compositional Explanations](https://mlsanity.com/paper/2310.18443/) (2023)
- [WWW: A Unified Framework for Explaining What, Where and Why of Neural Networks by Interpretation of Neuron Concepts](https://mlsanity.com/paper/2402.18956/) (2024)
- [Disentangling Polysemantic Channels in Convolutional Neural Networks](https://mlsanity.com/paper/2504.12939/) (2025)
- [Detection Accuracy for Evaluating Compositional Explanations of Units](https://mlsanity.com/paper/2109.07804/) (2021)
- [Explaining Deep Neural Networks by Leveraging Intrinsic Methods](https://mlsanity.com/paper/2407.12243/) (2024)
- [Towards Utilising a Range of Neural Activations for Comprehending Representational Associations](https://mlsanity.com/paper/2411.10019/) (2024)

## Abstract (arXiv)

Compositional explanations are a family of methods that aim to describe the spatial alignment between neurons' receptive field activations and concepts through logical rules, typically computed via a search over all possible concept combinations. Since computing the spatial alignment over the entire state space is computationally infeasible, the literature commonly adopts assumptions related to the structure of the combinations and beam search to restrict the state space. However, beam search cannot provide any theoretical guarantees of optimality, and it remains unclear how close current explanations are to the true optimum. In this theoretical paper, we address this gap by introducing the first framework for computing guaranteed optimal compositional explanations over the entire state space spanned by the adopted assumptions. Specifically, we propose: (i) a decomposition that identifies the factors influencing the spatial alignment, (ii) a heuristic to estimate the alignment at any stage of the search, and (iii) the first algorithm that can compute optimal compositional explanations in a time comparable to exhaustive beam search. Using this framework, we demonstrate that 10-40% of explanations previously obtained with beam search are suboptimal when overlapping concepts are involved. Finally, we evaluate a beam-search variant guided by our proposed decomposition and heuristic, showing that it matches or improves runtime over prior methods while offering greater flexibility in hyperparameters and computational resources.