Guaranteed Optimal Compositional Explanations for Neurons

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.

Understanding what individual neurons recognize inside deep neural networks remains a major challenge in artificial intelligence. One promising approach is compositional explanations, which describes neuron behavior using logical combinations of human concepts, such as colors, textures, or objects. These explanations are extracted by measuring how well these concepts spatially align with the regions where a neuron activates. For example, a neuron may respond to regions matching a rule such as "water AND NOT blue" (i.e., bodies of water that are not blue). However, existing methods rely on beam search, a shortcut strategy that explores only a small portion of the possible explanations and cannot guarantee that the final explanation is truly the best one. In this work, we introduce the first framework that can compute guaranteed optimal compositional explanations. We developed a mathematical decomposition of spatial alignment between neuron activations and concepts, together with a new search algorithm and heuristic that make this previously infeasible problem tractable. Our method can identify the best explanation while remaining computationally practical. When applying our framework to several deep neural networks, we discovered that up to 40% of explanations produced by previous methods are suboptimal. Our work provides stronger theoretical guarantees for neural network interpretability and offers new tools for understanding how deep learning systems represent information