Guaranteed Optimal Compositional Explanations for Neurons

Summary

This paper attacks a genuine gap in the compositional-explanations literature for CNN neuron interpretation. Since Mu and Andreas (2020), the community has approximated the best logical combination of concepts describing a neuron's spatial alignment with beam search, but nobody knew how close those beam solutions were to the true optimum because the state space is astronomically large ($\sim 2.8\times 10^{14}$ combinations under standard Mu-Andreas settings). The authors' conceptual move is to decompose the Intersection-over-Union objective into fundamental per-sample quantities — unique/common intersections and extras — and to build both admissible label and path heuristics on top of this decomposition. This lets them frame the problem as a best-first branch-and-bound search with provable optimality and, empirically, per-unit runtimes comparable to vanilla beam search. As a by-product they use the same decomposition to guide a new heuristic beam variant that is competitive with, and often better than, MMESH, especially at larger explanation lengths and beam sizes. They then use the optimal algorithm as an oracle to quantify beam-search suboptimality on three CNNs on Broden: 9-39% of beam explanations are strictly worse than the optimum, and a substantive slice differ in the concept identities themselves rather than merely in how the concepts are wired together. This is a solid, well-motivated contribution and I expect it to be picked up as ground truth for future comparisons. My main concerns are conceptual and presentational rather than architectural: the paper's proofs of admissibility are readable but sprinkled with cross-reference errors, one important paragraph defining the aggregated path heuristic is garbled by a typesetting collision, several tables are hard to interpret from headers alone, and the empirical claims — especially cross-domain generalisation and the '10-40%' headline — outrun the sampled evidence in a couple of places. None of these threaten the central contribution; all of them affect a careful reader's ability to trust it end-to-end.

Strengths

• Conceptual contribution. The dIoU decomposition into unique vs common intersections/extras is the enabling idea behind everything else in the paper, and it looks clean and general: the operator impact table (Observation 1) drops out naturally, the sample and aggregated path bounds share the same shape, and admissibility falls out of one set-inclusion argument per operator.
• Feasibility of exhaustive-quality search. Reducing an $\mathcal{O}(10^{14})$ combinatorial optimisation to a per-unit runtime in the same order of magnitude as vanilla beam search is genuinely surprising, and the design choices (aggregate-then-refine, backpropagation of exact sub-label quantities, on-the-fly frontier pruning by $MinIoU$) each have a plausible motivation and interact sensibly.
• Independent value of the beam variant. The MMESH-free beam heuristic keeps only binary information about concept masks, which is architecturally cleaner, cheaper on the memory side, and scales roughly flat with explanation length and beam size (Table 8) while MMESH grows almost linearly.
• Suboptimality diagnosis. The three-category taxonomy (different concepts, different connectives, same IoU / same concepts) turns the optimal solutions into a substantive qualitative critique of beam search rather than just a numeric win. The "unverified" AND NOT example (ball-pit / flower / dining-room) is a good illustration of how beam artefacts can distort narrative interpretation.
• Reference open-source implementation. The released code implements all four algorithms and matches the paper's headline commands, giving future work a shared substrate to compare against — a real service in an area that has struggled with reproducibility.

Weaknesses

• Central paragraph is garbled. The definition of the aggregated path heuristic on page 6 has prose and equations physically interleaved character-by-character. This is not a cosmetic complaint: it is the equation that drives all frontier pruning, and a reviewer trying to verify admissibility cannot read off whether the OR path numerator uses $Bott_1(I^C)$ or $Top_1(I^C)$, or how the aggregated form relates to the per-sample form.
• Proof cross-references are inconsistent. In Appendix F.3 the AND-case proof declares 'To prove Equation (105)' (the numerator/optimistic constraint) but concludes with 'Equation (106) is satisfied' twice — Eq. (106) is defined as the denominator constraint. Since the OR case uses the labels correctly, the reader cannot tell whether the AND case has a typo or a load-bearing error. The AND NOT path proof also has a step ('$I^C(L_k)_x$ removes at least $Bott_1(I^C)_x$') that appears to conflate cardinality of $L_k$ with cardinality of $L_k \cap L_i$, and the aggregated-form admissibility ('follows the same proof') skips the $Union_{\min} > 0$ edge case the authors themselves flagged in E.2.2.
• Overreach on cross-domain / cross-architecture applicability. The introduction is explicit that the work is CNN-vision only, but the conclusion, the outer part of the Discussion, and the "Extension to New Models and Domains" section repeatedly promise applicability 'across domains' and 'without modification' to future projection strategies. No NLP, tabular, or transformer experiment is offered, and the Section 4.3 caveat about NLP being slow-because-few-unique-elements contradicts the 'without modification' framing.
• Empirical scope of the suboptimality diagnosis. All of Tables 3, 4 and 9 are based on 50 randomly-selected units of one layer, at one activation range (top 0.005 quantile) or one cluster, with a fixed length of 3. The '10-40%' headline (which is actually 9-39%) is presented as a general property of beam search but is drawn from that thin slice; the "broader activation range → more difficult" trend in Table 9 rests on two points on one model.
• Same-IoU / Category-3 story rests on a precision choice. Appendix I concedes that at higher visualisation precision, apparent Cat 3 solutions may actually be Cat 1 (or vice-versa). Since Category 3 (17% of ResNet non-optimal) is used to argue that beam search produces "unverified" formulas, its size depends on the equality tolerance, which the paper never states. Related: the ResNet Cat 2 average IoU in Table 4 is 0.065 for both beam and optimal, despite the definition of Cat 2 requiring strictly different IoU.
• Optimality proof is loose in one place. The final one-line optimality argument in Section 3.3 talks about 'exploring exhaustively all nodes with estimated alignment greater than the found solution', but the algorithm actually prunes against $MinIoU$, a lower bound on the reachable IoU. That is a legitimate branch-and-bound completeness condition, but the sentence as written conflates the two invariants and could be tightened.
• Table readability. Table 2's header row folds section labels into column headers and duplicates 'Exp./Esti./Complexity'; the High Complexity Optimal row prints '105' and '108' where Tables 5–7 show these to be exponents ($3.5\times10^5$ nodes expanded, $1.28\times10^8$ estimated). A reader who only sees Table 2 will draw wrong conclusions about the algorithm's cost.
• Small notational / presentational issues that accumulate. AND NOT is written $\neg\wedge$ in Assumption 3 but $\wedge\neg$ everywhere else; the symbol $D$ is used for both the probing dataset and the disjoint matrix; Observation 1 says $\wedge\neg$ "preserves all unique elements" without noting it preserves only the left operand's uniques; the AND NOT footnote justification ("always true") is factually wrong; the main text and Appendix B disagree on whether units are drawn from the "last convolutional" or "penultimate" layer; Algorithm 1 has until Frontier is not empty (should be until Frontier is empty), passes an argument named Quantities that was never introduced, and never initialises BestIoU/BestLabel.

Reproducibility & code

• Released code covers the pipeline but not the environment. The compositional/optimal.py, compositional/beam_optimal.py, compositional/mmesh.py, and compositional/vanilla_search.py implementations correspond directly to the four algorithms in Table 2, and compare_methods.py computes the visited/expanded/estimated/time aggregates plus the Cat1/2/3 percentages the paper reports. A reviewer can trace each headline number to a specific code path.
• Datasets and checkpoints are not shipped. Broden requires the download script, Cityscapes requires registration, and ADE20K-847 requires manual Detectron2 dataset registration via datasets/register_ade20k_847.py; Places365 checkpoints must be fetched separately. The manuscript's single "we release the code" line does not walk a reader through this pipeline.
• Cluster-5 restriction is silently baked into the code. utils/compositional_utils.py skips clusters $\neq$ the highest one when computing optimal explanations on Broden. This is consistent with Table 9's setup but not documented in the paper, so a reader trying to reproduce cluster 1–4 will silently get empty results.
• Instrumentation is missing for two diagnostic claims. The backpropagation update count ("2000-3000 nodes per unit") and the memory-consumption ordering ("optimal is the lightest") have no counters or peak-memory hooks in the released code. Both claims are load-bearing engineering statements and would require patching to be verified.
• Table 2 numbers may drift. The repository's CHANGES.MD warns that post-ICML optimisations may shift visited counts and runtimes from the exact Table 2 values. This is normal for research code, but it means the paper should either freeze a tagged release matching Tables 2/5–7 or acknowledge that small deviations are expected.
• Hardware is only stated in the appendix. Section 4.1 quotes 5768 s/unit for the high-complexity optimal without disclosing hardware; Appendix B mentions the NVIDIA RTX 3090 workstation but no CPU or RAM. Since the algorithm runs "without parallelization", CPU model materially affects the numbers.

Recommended Changes

Essential

• Fix the garbled aggregated-path paragraph on page 6. Typeset each of the OR / AND / AND NOT path numerators and denominators on its own line, separate the aggregated-form commentary from the equations, and re-verify against Appendix E.2. This paragraph defines the pruning heuristic and currently cannot be read.
• Audit Appendix F.3 cross-references. Every citation of Equation (105) vs (106) in the AND and AND NOT cases should be checked; add the missing '$I^C(L_i)_x \cap I^C(L_k)_x$ lower-bounded by $Bott_1(I^C)_x$' step (or a counterexample) in the AND NOT path proof; and address the aggregated-form admissibility for the $Union_{\min} > 0$ case that E.2.2 flags.
• Rebuild Table 2. Use a proper multi-row header separating the three complexity blocks from the four metric columns, and format 105/108 in the High Complexity Optimal row as $3.5\times10^5$ / $1.28\times10^8$ (matching Tables 5–7). Move the RTX 3090 workstation description into Section 4.1 and add CPU model + system RAM.
• Reconcile the '10-40%' headline with Table 3. Either change the abstract and Section 4.2 to say '9-39% across three CNNs' or explain why 10% is the correct lower bound. In the same pass, resolve the ResNet Cat 2 identical-mean row (add a decimal, or clarify how ties are handled) and state the numerical precision at which Cat 1 vs Cat 3 are distinguished.
• Empirically verify the "all beams find the same IoU" claim behind omitting IoU from Table 2. Either report the beam-variant IoUs directly, or prove that level-wise admissibility of the heuristic implies identical beams for the same $b$ across MMESH / ours / vanilla.
• Soften cross-domain and cross-architecture claims. In the Conclusion and Section H, restrict the strong "across domains" / "without modification" language to what is actually demonstrated (CNN feature maps on vision, projected to input resolution), and restate the non-CNN caveats from Section 4.3.
• Fix Algorithm 1. Change until Frontier is not empty to until Frontier is empty; initialise BestIoU/BestLabel; rename the mystery Quantities argument on line 48 to match ConceptQuantities; reconcile argument order with Algorithm 2's compute_quantities call.
• Document the Cluster-5 code restriction. Either add a paragraph to Section 4.1 / Appendix B saying that optimal on Broden is only computed for the highest cluster index (i.e., num_clusters - 1), or remove the restriction from utils/compositional_utils.py.

Suggested

• Unify notation. Change $\neg\wedge$ in Assumption 3 to $\wedge\neg$; rename the disjoint matrix (e.g., $\Delta$) so it does not collide with the dataset $D$; fix the "cat AND NOT dog is always true" footnote to say "equivalent to cat" instead; qualify Observation 1's $\wedge\neg$ statement as "preserves all the unique elements of the left side".
• Add uncertainty to the suboptimality diagnosis. Report per-model bootstrap or Wilson CIs for the non-optimal percentage in Table 3 and, if compute permits, a second layer or a larger unit sample per model. For Table 9, add at least one intermediate activation-range point on a second model before drawing a monotone-with-breadth conclusion.
• Expose diagnostic counters in the release. Add ancestor-update counters to perform_search so that the "2000-3000 nodes per unit" claim is checkable, and instrument peak memory (e.g., torch.cuda.max_memory_allocated) so that "the optimal algorithm is the lightest in terms of memory" becomes a measurement.
• Add a small ablation table for sample-only vs aggregated-only vs combined path computation. The paper's justification for the combined design is qualitative; a three-row table across the three complexity settings would settle it.
• Reconcile the layer name. Say explicitly whether experiments use the last convolutional layer or the penultimate layer, and give the tensor names for each model (e.g., ResNet18 layer4.1.conv2, DenseNet161 features.norm5, AlexNet features.10) so the probing setup is unambiguous.
• Sharpen the runtime comparison against BFS. Provide a small footnote that shows precisely how "$\sim 400$ million hours" and the "$\times 1000$" factor are computed from the 0.005 s/node assumption, so the arithmetic is checkable.
• Add variance bars to Table 8. Match Tables 5–7 by reporting SD (or min/max) for the length- and beam-size sweeps.
• Clarify the '50,000 nodes per unit' remark. Give the baseline frontier size in the same setting so 'slightly' is interpretable.
• State which units the "2000-3000 backpropagation updates" range refers to. Almost certainly DenseNet161 on High Complexity, but the paper does not say.
• Ship a dedicated Reproducibility section. Enumerate the download / registration steps for each dataset, the Places365 checkpoints, the tagged commit that matches Tables 2/5–7, and the hardware used for all runtime numbers.