Technical Summary: Guaranteed Optimal Compositional Explanations for Neurons

Problem Statement

Compositional explanations aim to describe the spatial alignment between a neuron's receptive field activations and specific concepts (e.g., objects, textures) using logical rules. The core objective is to find a logical formula $L$ composed of concepts from a set $L_1$ that maximizes the Intersection over Union (IoU) between the neuron's activation map and the concept annotations.

However, the search space for all possible concept combinations is combinatorially explosive. Previous literature (e.g., Mu and Andreas, 2020) has addressed this by restricting the search space through structural assumptions and employing beam search. While beam search is computationally efficient, it offers no theoretical guarantee of optimality. Consequently, it remains unclear whether the explanations generated are truly the best possible alignments or merely local optima, and how far they deviate from the ground truth. This uncertainty limits the reliability of current interpretability methods and hinders the development of algorithms that can reduce approximation errors.

Methodology

The authors propose a framework to compute guaranteed optimal compositional explanations over the entire state space defined by standard assumptions, without sacrificing computational feasibility. The methodology consists of three main components:

1. Decomposition of the IoU Metric (dIoU)

The paper introduces a decomposition of the IoU score into fundamental quantities that govern alignment quality. This relies on three assumptions:

• Assumption 1: Concepts in an explanation are distinct.
• Assumption 2: Concepts are combined incrementally.
• Assumption 3: Logical operators are 00-preserving (i.e., they cannot produce a 1 from two 0s). This covers standard bitwise operators: OR ($\lor$), AND ($\land$), and AND NOT ($\land \neg$).

The IoU is reformulated using four key sets derived from the neuron activation matrix $N$ and concept matrices $M$:

• Unique/Intersection ($I_U, I_C$): Locations where the neuron fires on unique or common concept annotations.
• Unique/Extras ($E_U, E_C$): Locations where the concept is annotated but the neuron does not fire.

This decomposition ($dIoU$) allows for a fine-grained analysis of how logical operators impact the numerator (intersection) and denominator (union) of the IoU score.

2. Heuristic Estimation

To guide the search, the authors design a heuristic that estimates the maximum and minimum possible IoU for any partial label $L$ and any potential path extending $L$ to the maximum length $n$.

• Label Quantities: The heuristic estimates the impact of adding a concept $k$ to a label $L$ using a Disjoint Matrix to check for overlaps. It derives bounds for intersection and extras based on whether the operands are disjoint or overlapping.
• Path Quantities: To estimate the potential of extending a label further, the method utilizes Top and Bott vectors. These vectors store the cumulative sums of the $t$ highest and lowest values for each quantity across the dataset, allowing the algorithm to estimate the best and worst-case improvements achievable by adding remaining concepts.
• Aggregated vs. Sample Computation: To balance precision and efficiency, the heuristic uses aggregated computations (summing over the dataset) for initial pruning and frontier management, while reserving sample-based computations (per-image) for refining estimates of promising nodes.

3. Optimal Search Algorithm

The authors propose a best-first search algorithm (Algorithm 1) that guarantees optimality:

1. Initialization: Compute exact quantities for all atomic concepts and estimate paths using the heuristic.
2. Frontier Management: Maintain a priority queue of nodes sorted by their estimated maximum IoU ($dIoU_{max}$).
3. Pruning: Dynamically prune the frontier by removing nodes whose $dIoU_{max}$ falls below the global maximum of the minimum estimates ($MinIoU$) found so far.
4. Expansion & Refinement:
   • Pop the node with the highest estimate.
   • If the estimate is aggregated, refine it to a sample-based estimate.
   • Apply logical equivalence rules to reduce redundancy.
   • If the node is a final label, compute its exact IoU. If it is the new best, update the global best and backpropagate exact quantities to update estimates of other nodes sharing sub-labels.
   • If the node is not final, expand it by concatenating all possible concepts and operators, re-estimating bounds, and inserting them into the frontier.

The algorithm is proven to be admissible (it never underestimates the maximum possible IoU) and complete, ensuring it finds the globally optimal solution.

Key Contributions

1. Formal Guarantees: This is the first framework to provide theoretical guarantees of optimality for compositional explanations over the full state space spanned by standard assumptions.
2. Decomposition (dIoU): A novel decomposition of the IoU metric that identifies fundamental quantities governing alignment, enabling a precise characterization of logical operator impacts.
3. Optimal Algorithm: A search algorithm that computes optimal explanations in a time comparable to exhaustive beam search, making the exploration of the full state space feasible.
4. Heuristic-Guided Beam Search: A variant of beam search guided by the proposed decomposition and heuristic, which matches or improves upon prior runtime performance while offering greater flexibility in hyperparameters.

Results

The authors evaluated their method on ResNet18, AlexNet, and DenseNet161 models trained on Places365, using three datasets of varying complexity (Cityscapes, Ade20K, Broden).

• Feasibility: The optimal algorithm successfully finds the optimal solution within feasible runtimes across all complexity levels. While it explores a larger state space than beam search, its runtime remains comparable to vanilla beam search (e.g., ~5768 seconds/unit for high complexity vs. ~5929 for vanilla beam search), whereas a naive breadth-first search would require hundreds of millions of hours.
• Suboptimality of Beam Search: The analysis reveals that 10–40% of explanations previously obtained via beam search are suboptimal when overlapping concepts are involved.
  • Category 1 (Most Common): Explanations differ in both concepts and IoU. Beam search often fails to find explanations involving complex AND/AND NOT combinations that describe specialized units.
  • Category 2: Explanations share concepts but differ in logical structure, leading to different IoU scores (e.g., ((A OR B) AND C) vs ((A AND C) OR B)).
  • Category 3: Explanations share the same IoU but differ in structure. Beam search may produce "unverified" explanations relying on disjoint concepts that never co-occur, whereas the optimal algorithm identifies the correct alignment.
• Heuristic Performance: The beam search variant guided by the proposed heuristic outperforms baselines (MMESH, Vanilla Beam) in terms of visited states and scales more effectively with explanation length and beam size, while requiring less memory as it does not need to store spatial tensors for heuristic computation.

Significance and Claims

The paper claims that identifying the ground-truth optimal solution is critical for:

1. Reliability: Preventing misleading views of neuron behavior caused by suboptimal approximations.
2. Dataset Characterization: Revealing unstudied properties of datasets if beam search converges to the optimum.
3. Algorithm Development: Providing a benchmark to guide the development of new algorithms that reduce approximation errors.

The authors emphasize that their method does not rely on spatial information (unlike MMESH), making the heuristic potentially applicable across domains beyond computer vision. They position this work as a theoretical foundation that bridges the gap between Network Dissection (which finds optimal single concepts) and Compositional Explanations (which previously sacrificed optimality for complexity). The paper concludes by noting that while the optimal algorithm is a significant step, future work is needed to extend these guarantees to non-00-preserving operators and other architectures like Transformers.