{"id":"4396628a-27c7-4fbb-9753-0f82ad0bbe26","arxiv_id":"2511.20934","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A best-first search with an admissible heuristic computes guaranteed-optimal compositional neuron explanations in practical time and shows beam search was suboptimal in 10–40% of cases with overlapping concepts.","lead":"Neuron-level explanations built from logical concept combinations are usually found by beam search, which can miss the best combination. This paper gives a best-first search with a provable optimality guarantee and shows standard beam search was suboptimal for 10–40% of overlapping-concept cases.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Section F proves admissibility only for exclusive operator paths; the mixed-operator max/min estimate used by the optimal algorithm is asserted, not proved. This is load-bearing for the optimality guarantee, though the missing lemma is likely true.","rationale":"The reader's weakest assumption points to mixed-operator path admissibility, and I agree that this is the least secure step in the optimality proof. The paper's Section F explicitly proves only exclusive paths, and Section E.3's treatment of mixed paths is informal and incomplete. However, my own derivation suggests the missing statement is true: every formula in the restricted state space is a subset of the OR-union of its constituent concepts, which gives a global numerator upper bound and a global denominator lower bound. Thus the concern is a rigor gap that should be fixed with a formal lemma, not a demonstrated counterexample. I would keep the reader's CONDITIONAL verdict: the paper's central guarantee is plausible but not yet fully proven as written. The empirical '10-40% suboptimal' claim also deserves attention because category-3 differences share the same IoU, but the theoretical proof gap is more load-bearing for the paper's primary claim of guaranteed optimality.","tokens_in":907,"tokens_out":822,"duration_ms":377577,"concrete_test":"Formalize the subset lemma for arbitrary mixed operator sequences: for each sample x, the mask of any formula ( ... ((L ⊕ c1) ⊕ c2) ... ⊕ ct ) is a subset of the mask of L OR c1 OR ... OR ct. Then verify: (i) the OR exclusive numerator estimate (Eq. 12/35) is an upper bound on |N ∩ (L OR c1 ... OR ct)|, hence on every mixed path's numerator; (ii) the AND exclusive denominator estimate (Eq. 14/40), which equals |N|, is a lower bound on every mixed path's denominator. If both hold, complete Appendix F with this mixed-path admissibility argument, confirming the guarantee. If any mixed path violates (i) or (ii), construct a dataset realizing that path and run Algorithm 1 to check whether the optimal node is pruned.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The optimality guarantee rests on the path heuristic (Section 2.3.2, Eqs. 11-16) being admissible for every path in the assumption-restricted state space. Appendix F proves admissibility only for exclusive OR, AND, and AND NOT paths (F.3). For mixed paths, Section E.3 estimates values by taking the maximum of exclusive numerator estimates and the minimum of exclusive denominator estimates, with an informal derivation only for the OR+AND pairing (Eqs. 54-59) and a remark that other combinations are similar. No theorem states that this mixed estimate is an upper bound on the exact IoU of every path mixing OR, AND, and AND NOT. The pruning step (Algorithm 1 lines 52-55) removes nodes whose estimated max falls below the global min estimate; if a mixed path's max were underestimated, the optimum could be pruned. This is therefore a real proof gap in the central claim. The gap is likely closable: the 1-set of any formula built from L plus t added concepts is a subset of L OR c1 OR ... OR ct, which would make the OR exclusive numerator (Eq. 12/35) a global numerator bound and the AND exclusive denominator (|N|, Eq. 14/40) a global denominator lower bound. But the paper does not state or prove this subset lemma; it merely asserts the mixed-path combination.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a framework for computing guaranteed optimal compositional explanations of neurons. It introduces a decomposition of the IoU objective (dIoU) into unique/common intersection and extra sets, designs a path heuristic that estimates the best continuation of any partial label, and presents a best-first search algorithm intended to return the globally optimal explanation within the state space defined by distinct concepts, left-associative formulas, and 00-preserving operators. The paper also proposes a beam-search variant guided by the heuristic and reports experiments on Cityscapes, ADE20K, and Broden assessing runtime and the suboptimality of prior beam-search explanations.","tokens_in":30096,"tokens_out":14212,"duration_ms":150541,"significance":"If the optimality claim is made fully rigorous, this would be a valuable contribution: the dIoU identity (Lemma 1) is exact, no fitted parameters enter the proof, and the work directly addresses a gap in the compositional-explanations literature. The proposed heuristic and beam variant are practically relevant and the empirical finding that many beam-search explanations are suboptimal is important. However, the current proof leaves a load-bearing gap for mixed-operator paths, and there are concrete errors in the definition of the disjointness matrix and in the reported empirical range.","major_comments":[{"comment":"The optimality guarantee requires the path heuristic to be admissible for the full state space of left-associative formulas with arbitrary operator sequences. Section 2.3.2 asserts that mixed-operator paths are handled by taking the max/min of exclusive-path estimates, but Appendix E.3 only analyzes the OR+AND pair (Eqs. 54-59) and Appendix F.3 proves admissibility for exclusive OR, AND, and AND-NOT paths. Algorithm 1 expands nodes with every allowed connective (line 49) and prunes nodes whose estimated dIoU_max falls below the global dIoU_min (lines 52-55), so an inadmissible mixed-path estimate could discard the optimum. The missing lemma is plausible (the 1-set of any formula built from L plus t concepts is a subset of the union of those concepts' positive supports), but it is not stated or proved. This is load-bearing for the central claim.","section":"Section 2.3.2 / Appendix E.3 / F.3"},{"comment":"The disjointness matrix is defined as D[k1,k2]=1 iff M_{k1}[x,j] != M_{k2}[x,j] for every location. That is the condition that the two concept matrices are logical complements, not the condition that the concepts have no annotation overlap. For typical disjoint concepts with locations where neither concept is annotated, D=0, so the exact 'disjoint' branch of Section 2.3.1 would not be entered. This contradicts the stated purpose of D and can materially affect the tightness of the estimates and the reported efficiency. The condition should be, e.g., D[k1,k2]=1 iff no location has both annotations.","section":"Section 2.3.1, Eq. (5)"},{"comment":"The abstract and Section 3.2 claim that '10-40%' of beam-search explanations are suboptimal when overlapping concepts are involved. Table 2 reports Diff = 8% for ResNet, 22% for AlexNet, and 39% for DenseNet. The lower endpoint 10% is contradicted by the 8% ResNet row. If 'Diff' means something different from the suboptimality rate, the text must say so; as written, the stated range is not supported by the table.","section":"Abstract / Section 3.2 / Table 2"}],"minor_comments":[{"comment":"The footnote says 'cat AND NOT dog is always true.' This is not a valid logical statement by itself; presumably the intended meaning is that when the two concepts are disjoint, 'cat AND NOT dog' is equivalent to 'cat.' Please reword.","section":"Section 2.3.1, footnote 1"},{"comment":"The displayed constraint uses |EU_min|+|EC_max| in the denominator, but the surrounding proof and requirement (64) concern EC_min. This looks like a typo and should be corrected for readability.","section":"Appendix F.1, Eq. (62)"},{"comment":"The statement that 'both MMESH and our beam variant converge to the same solutions as those found by the extensive search (Vanilla Beam), since they use admissible heuristics' is not justified: an admissible heuristic alone does not guarantee that a bounded beam search reproduces the full beam search's outcome. If this equality was verified empirically, say so; otherwise remove or qualify the claim.","section":"Section 3.1"},{"comment":"Category 3 explanations are described as if the optimal algorithm 'correctly identifies' the alignment even though the table says these explanations have the same IoU. Under the formal objective Eq. (1), both formulas are equally optimal; semantic/visual preferences should not be presented as an optimality defect of beam search.","section":"Section 3.2"},{"comment":"The formula for the number of combinations is garbled in the typesetting: 'Pn k=1 nk−1 o Q k(|L1|−k)' should be a readable product/summation. Also, Table 4 has formatting issues in the mean±std columns.","section":"Section 2.1"}],"recommendation":"major_revision","confidential_remarks":"The core idea is strong and the dIoU decomposition is a genuine contribution, but the mixed-path admissibility gap in Appendix F is a real proof hole in the claimed guarantee. It is likely closable with a subset argument, and I would be willing to accept after that proof is added and the D-matrix and empirical-range issues are fixed. The paper should also be explicit about what 'optimal' means relative to the assumed left-associative state space, since the title and abstract can be read as claiming more."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nWhat you should know first: this is a real contribution, not a repackaging. The paper gives the first algorithm with a claimed optimality guarantee for compositional neuron explanations over the assumption-restricted state space. The dIoU decomposition in Lemma 1 is exact, and the admissibility proofs for exclusive OR, AND, and AND-NOT paths are careful and self-contained. That is genuinely new relative to Mu-Andreas beam search and the authors' own MMESH.\n\nThe main soft spot is exactly where your reader put it. Section F proves admissibility only for exclusive operator paths. The actual search expands nodes with every allowed connective, and the mixed-path estimate in Section 2.3.2 and E.3 is asserted, not proved. The OR+AND case gets an informal derivation; the rest get \"similar observations can be made.\" This matters because the pruning step (Algorithm 1, lines 52-55) relies on the estimated max being an upper bound. If a mixed path is underestimated, the optimum could be pruned. The gap is likely closable — the 1-set of a formula built from L plus t added concepts is a subset of L OR c1 OR ... OR ct, which would give a global numerator bound and a denominator lower bound — but the paper does not state or prove that subset lemma. The authors should either add that proof or scope the optimality claim to exclusive paths.\n\nThe second issue is the headline number. The abstract says 10-40% of beam-search explanations are \"suboptimal,\" but Table 2's category 3 is same-IoU, different structure. Those are alternative optima, not suboptimal explanations. The honest number is the share of category 1 and 2 differences, which is smaller. That needs re-scoping.\n\nTo the authors' credit, they flag the breadth-first convergence and the unmeaningful-unit slowdown in Section 3.3, which is the right kind of honesty. No code is released, so the runtime claims rest on an implementation we cannot check yet.\n\nNet: the central idea is not obviously wrong, the exclusive-path proofs are genuine, and the empirical setup is appropriate. This deserves a serious referee. I would send it out, with the request to prove or scope the mixed-path admissibility, re-report the suboptimality rate excluding identical-IoU differences, and release code.","headline":"A genuinely new first algorithm for guaranteed-optimal compositional explanations; the central admissibility gap for mixed-operator paths is real but likely closable, and the '10-40% suboptimal' headline overstates because it includes same-IoU alternatives.","tokens_in":30547,"tokens_out":2671,"would_cite":true,"duration_ms":30071,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims a best-first search that provably returns the optimal logical explanation of a neuron's spatial alignment.","keywords":["compositional explanations","neuron interpretability","best-first search","heuristic search","Intersection over Union","optimality guarantee","beam search","concept alignment"],"falsifier":"On a small synthetic dataset with two overlapping concepts and a single neuron, exhaustively enumerate every legal formula of length at most three and compute the true IoU for each; then compute the heuristic's estimated maximum for every partial formula and check whether any estimate is below the true best IoU of a formula extending it. A single counterexample would show the heuristic is inadmissible and the optimality proof does not cover all paths.","tokens_in":29653,"feed_emoji":"🧠","tokens_out":5225,"duration_ms":54402,"temperature":0.7,"pith_summary":"This paper sets out to establish that the best logical explanation of what a neuron detects—the combination of concepts whose locations overlap its activation pattern most—can be computed exactly, not merely approximated. The route is a decomposition of the overlap score into quantities that can be estimated cheaply, followed by a best-first search that expands partial formulas in order of their estimated ceiling and prunes using an estimated floor. The authors prove that, under the field's standard assumptions (distinct concepts, incremental left-associative formulas, 00-preserving logical operators), the first complete formula returned is the one with the highest true alignment. If the proof holds, earlier beam-search explanations were suboptimal in 10–40% of cases involving overlapping concepts, and the gap can be closed in roughly the time a plain beam search took.","feed_headline":"New search provably finds the best neuron explanation","feed_subtitle":"Beam search misses the true best explanation in up to 40% of cases; new heuristic finds it in comparable time.","key_machinery":"The central object is the decomposed Intersection-over-Union (dIoU), which splits the alignment calculation into four per-sample counts—unique intersections, common intersections, unique extras, common extras—so that the effect of each logical operator (OR, AND, AND NOT) on each count is predictable. The matching heuristic builds Top and Bottom vectors from the per-concept values of these counts to estimate, for any partial formula, the maximum and minimum IoU achievable by any continuation of bounded length. The algorithm that carries the argument is best-first search with an admissible heuristic: it prunes nodes whose estimated maximum is below the current best minimum, and it is this comb","core_discovery":"The central claim is that guaranteed optimal compositional explanations are feasible. The paper introduces the decomposed Intersection-over-Union (dIoU) score, which separates locations into unique and common elements and separates neuron-active locations into intersections and extras, and proves that dIoU equals the standard IoU whenever the logical operators are 00-preserving. On top of this decomposition it builds a heuristic that, for any partial formula, upper-bounds the best IoU achievable by extending it and lower-bounds the worst, using precomputed Top and Bottom vectors of individual concept contributions. The optimal algorithm is a best-first search that visits nodes in descending","pith_inferences":["If the mixed-operator path estimates are later shown to be inadmissible in some corner of the state space, the guarantee would degrade gracefully to single-operator explanations; the empirical suboptimality of beam search would still hold but without a formal optimality certificate.","The same decomposition could be repurposed for other set-overlap metrics (for instance, Dice or other Jaccard-style scores) by re-deriving the Top and Bottom vectors, provided the operators remain 00-preserving.","A practical audit pipeline could run the beam variant first to flag units whose explanations are likely suboptimal, then invoke the optimal algorithm only for those units, making the guarantee affordable at large scale.","The 10–40% suboptimality rate suggests that interpretability conclusions drawn from beam-search explanations of overlapping-concept datasets may be systematically imprecise; re-running standard benchmarks with the optimal algorithm could yield a corrected catalogue of neuron explanations."],"forward_implications":["If the central claim is correct, any existing beam-search explanation can be replaced by a provably optimal one without leaving the standard assumptions of the field, at a comparable computational cost.","The 10–40% discrepancy measured in overlapping-concept settings means that a meaningful fraction of previously reported compositional explanations were not the best-aligned ones; this can now be detected and corrected.","A beam-search variant guided by the same heuristic matches or beats the runtime of prior guided beam search while finding the same explanations as exhaustive search, removing the need to keep annotations in memory.","The heuristic's independence from spatial information makes the optimal-search framework usable in non-vision settings where concept locations are defined differently, such as audio or text."],"fun_headline_variants":["Optimal neuron explanations, provably, in beam-search time","Beam search missed 40% of best neuron explanations—now fixed","First proven-optimal search for compositional explanations","No more suboptimal neuron explanations: provably optimal"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The guarantee assumes that the path heuristic never overestimates the best alignment reachable from any partial explanation, and that property is formally proven for paths using one operator but only sketched for paths that mix multiple operators.","fun_headline_variants_meta":{"raw":{"variants":["Optimal neuron explanations, provably, in beam-search time","Beam search missed 40% of best neuron explanations—now fixed","First proven-optimal search for compositional explanations","No more suboptimal neuron explanations: provably optimal"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000221,"raw_usage":{"total_tokens":1285,"prompt_tokens":741,"completion_tokens":544,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":485,"completion_tokens_details":{"reasoning_tokens":477}},"tokens_in":485,"tokens_out":544,"duration_ms":7067,"temperature":1.0,"reasoning_tokens":477,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-03T20:07:59.884546+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On a small synthetic dataset with two overlapping concepts and a single neuron, exhaustively enumerate every legal formula of length at most three and compute the true IoU for each; then compute the heuristic's estimated maximum for every partial formula and check whether any estimate is below the true best IoU of a formula extending it. A single counterexample would show the heuristic is inadmissible and the optimality proof does not cover all paths.","supporting_citations":[],"review_version":1}