Guaranteed Optimal Compositional Explanations for Neurons

AI summary

Overview

• Research area: Interpretability of neural networks, specifically compositional explanations for individual neurons, combining logical rule search with heuristic design from AI search theory.
• Technical level: Advanced. The paper is primarily theoretical, with a formal decomposition of the IoU metric, admissibility-style bounds, and a proof of optimality, plus an empirical evaluation on vision datasets.
• Scope in one sentence: The paper introduces the first framework that decomposes the Intersection over Union (IoU) objective behind compositional explanations, derives a heuristic from that decomposition, and uses it to compute guaranteed-optimal explanations over the entire admissible search space in time comparable to prior beam-search approaches.

What This Paper Is About

Compositional explanations describe neurons by finding logical combinations of concepts (e.g., ((Cat OR Car) AND White)) whose spatial locations best align with where a neuron fires. Because the full space of possible combinations is far too large to explore — the paper reports 2.8 × 10^14 operations under the settings of Mu and Andreas (2020) — prior work restricts the space with structural assumptions and uses beam search, which offers no optimality guarantee. This paper asks how far those approximate explanations are from the true optimum, and builds the machinery needed to actually compute the optimum.

Key Contributions

1. A decomposition of the IoU score (dIoU) that isolates the fundamental quantities governing spatial alignment — unique and common intersections and extras — and enables a finer-grained characterization of how logical operators (OR, AND, AND NOT) affect alignment. Lemma 3.6 shows dIoU is equivalent to IoU when the operators involved are 00-preserving.
2. A heuristic and a corresponding optimal algorithm that jointly shrink the state space to be explored and guide the search. The algorithm is a best-first search that is proven (Appendix F) to always return the most aligned explanation, and it computes optimal explanations in feasible time.
3. The first quantification of beam-search suboptimality: 10-40% of explanations previously obtained with beam search are suboptimal when overlapping concepts are involved.
4. A heuristic-guided beam search variant using the proposed label-quantity estimation in place of MMESH. It matches or improves runtime over prior methods while offering greater flexibility in hyperparameters and computational resources, and scales more effectively with explanation length and beam size. Code is released.

Main Findings

• Optimal solutions are computationally feasible. The optimal algorithm consistently found the optimal solution within feasible runtimes across all three annotation-complexity settings, a result the authors call "a major milestone," since navigating the entire state space and finding the optimum was considered infeasible by previous literature.
• Runtime is comparable to vanilla beam search even at high complexity. In the high-complexity setting the optimal algorithm took 5768 seconds per unit versus 5929 for vanilla beam search; in the intermediate setting it took 90.57 versus 450; in the low-complexity setting 0.08 versus 2.77.
• The optimal algorithm searches very few exact-IoU nodes. In the high-complexity setting it visited 47 nodes compared with 53,775 for vanilla beam search, while expanding 10^5 nodes and making 10^8 estimates.
• Expanded states are a tiny fraction of the space. The number of expanded states is less than 0.1% of the overall state space and is significantly smaller than the number of estimated states, which is described as crucial for refining heuristic estimates without hurting runtime.
• Heuristic-guided beam search beats all baselines on visited states. Our beam variant visited 6, 10, and 27 nodes in the low, intermediate, and high complexity settings, versus MMESH at 121, 39, and 43, and vanilla beam search at 716, 37,979, and 53,775.
• Heuristic-guided beam search is competitive or better on runtime. 0.17 s/u vs. 10.37 (MMESH) and 2.77 (vanilla) at low complexity; 11.55 vs. 38.42 and 450 at intermediate complexity; 123.33 vs. 102.35 and 5929 at high complexity.
• Exhaustive breadth-first search is impractical. Under an optimistic assumption of 0.005 seconds per node, breadth-first search would need roughly 400 million hours in the intermediate and high-complexity settings and about 140 seconds in the lowest-complexity setting, which is 1000 times slower than the proposed optimal algorithm.
• Operator semantics are characterized. OR is 1-preserving and keeps common elements shared by both concepts while summing non-shared and unique ones; AND is 0-preserving and removes all unique elements plus common elements not shared by both; AND NOT preserves all unique elements but removes common elements shared by both concepts.
• All beam variants returned the same solution in the experiments. Because they share the same restricted state space and use admissible heuristics, the paper does not report IoU in Table 2 — the difference between the variants lies in search cost, not output.

Methodology in Plain English

The authors begin by breaking the IoU score into four parts that can be counted separately: locations where the neuron fires and exactly one concept is annotated (unique intersection), locations where the neuron fires and several annotated concepts overlap (common intersection), and the two corresponding "extras" — annotated locations where the neuron does not fire. Unique elements can never be shared between concepts, so their contribution to any logical combination can be computed exactly. Common elements are the hard part, and the authors handle them by checking whether the two sides of a formula share any annotation overlap using a precomputed binary Disjoint Matrix, then deriving formulas for the minimum and maximum possible values of each quantity under each operator.

With per-label quantities in hand, they estimate how good a partial formula could possibly become after adding more concepts. Since explanation length is bounded in practice (typically 3), they precompute, for each quantity, the n highest and n lowest concept scores and accumulate them into Top and Bott vectors, producing an upper bound dIoU_max and a lower bound dIoU_min for every possible continuation path. They also offer an aggregated version of these computations that sums values per label rather than per sample, trading precision for speed.

The optimal algorithm is a best-first search. It starts by seeding the frontier with all paths whose upper bound exceeds the best lower bound seen so far, then repeatedly pops the most promising node, refines aggregated estimates into sample-based ones, expands the label with every allowed concept and connective, and prunes anything whose upper bound falls below the current best lower bound. When it reaches a complete label, it computes the exact IoU and back-propagates the exact sub-label quantities to other frontier nodes that share those sub-labels. Logical equivalence rules and a cache of recently explored nodes cut redundant work. Because each path's estimate is an overestimate and the search visits every node whose estimate exceeds the best found explanation, the returned explanation is guaranteed to be the most aligned one.

Evaluation uses three settings: low complexity (Cityscapes, 25 concepts, all disjoint), intermediate complexity (the extended Ade20K version provided by Detectron2, 847 concepts with no overlapping annotations), and high complexity (Broden, 1198 concepts with frequent overlaps). Baselines are MMESH-guided beam search and vanilla beam search, both with beam size fixed to 5. Following Mu and Andreas (2020), the authors extract 50 random units from the last convolutional layer of a ResNet trained on Places365 and use the highest activations (top 0.005 percentile) as activation ranges.

Why This Matters

Providing the ground truth that previous algorithms only approximate changes what claims about neuron explanations can mean. If beam search was returning suboptimal rules for 10-40% of cases involving overlapping concepts, then published explanations of neuron behavior may have been partial or misleading, and any downstream conclusion drawn from them is affected. Having the true optimum available also lets researchers measure approximation error directly, design better approximate algorithms, and study the trade-off between explanation quality and runtime with concrete numbers rather than assumptions.

• Auditing vision models: the evaluation targets convolutional networks and segmentation-style concept annotations (Cityscapes, Ade20K, Broden, Places365), exactly the setting where practitioners inspect what a classifier or detector has learned.
• Safety-critical deployment: in domains where a model's behavior must be justified, knowing whether an explanation is optimal rather than merely plausible changes the strength of the justification.
• Dataset and concept-overlap diagnostics: the finding that overlapping concepts drive suboptimality points to annotation structure itself as a variable worth inspecting when explanations look weak.
• Interpretability tooling: the heuristic-guided beam search variant offers a cheaper, more configurable option for tools that cannot afford a full optimal search.

Industry relevance comes from both directions: the optimal algorithm makes it possible to produce reference explanations for benchmarking, while the heuristic-guided beam search gives a production-friendly option that the authors report is competitive or better than MMESH in runtime and scales better with explanation length and beam size. The paper explicitly frames the availability of ground truth as a way to "guide and promote research" on reducing approximation errors.

Future Directions

• Extending beyond CNNs and computer vision. The authors state they apply the method first to computer vision and Convolutional Neural Networks given their prominence in compositional explanation research, and explicitly leave extension to other architectures (e.g., Transformers) and other domains to future work.
• Handling paths that mix multiple operators. The heuristic combines operators by taking the maximum and minimum of each quantity across the operators considered; the paper notes that explicitly modeling every possible combination is discussed separately (Section E.3), leaving room for tighter bounds.
• Refining the precision-efficiency trade-off. The aggregated computation reduces cost to a single comparison per quantity at the expense of precision, and the paper leaves the balance between the sample-based and aggregated versions as an open design question.
• Explaining why beam search sometimes reaches the optimum. The authors raise the possibility that when beam search converges to the optimal solution, this "could indicate unstudied or unknown properties of the underlying datasets" — a question the new ground truth now makes investigable.

Target Audience

Researchers in explainable AI and neural network interpretability, especially those working on concept-based and neuron-level explanations; search and heuristic-design researchers interested in admissible bounds for structured combinatorial objectives; and practitioners who need either a benchmark-quality explanation or a tunable, compute-aware approximation. Readers will get the most out of the paper with some background in propositional logic, set-based segmentation metrics such as IoU, and best-first search, though the plain-language intuition behind the decomposition is accessible to anyone who understands how concept masks and neuron activation masks overlap.

Authors’ abstract

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.