{"id":"e9ce69d4-ea11-40cd-ad77-86b7e64388b3","arxiv_id":"2507.11357","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Conditionally independent neurosymbolic predictors cannot represent uncertainty over reasoning shortcuts except in rare partial-supervision cases, which limits their out-of-distribution reliability.","lead":"Neurosymbolic models that assume their visual concepts are independent cannot represent uncertainty when multiple different concepts produce the same label, so they often lock onto the wrong concept mapping with high confidence. This paper proves that limitation formally and shows that more expressive models can be made aware of such 'reasoning shortcuts' with the right design.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 7 quantifies over an arbitrary set A of remappings, but the 'only extremely rare cases' claim in the abstract requires A to be the full set of label-preserving maps; the paper never fixes this, and with a curated A even common programs satisfy the theorem's condition.","rationale":"The formal machinery of Theorem 7 appears sound: a product distribution's support must be a subcube, so if it reproduces a mixture whose support is not a subcube, RS-awareness is impossible. However, the paper's central narrative is stronger than the theorem. The theorem is about a fixed, arbitrary set A of concept remappings, while the abstract and contributions claim that independent models can be RS-aware only in 'extremely rare cases' and that the question is settled. The rarity conclusion needs a well-defined reference class: is A the full set of all label-preserving remappings for the task, or is it any set of remappings a practitioner chooses to model? The paper never states this. My AND example shows that with a small curated A, Theorem 7's necessary condition is satisfied for a meaningful Boolean program, so the theorem alone does not imply rarity. Under the full-A reading the rarity claim is plausible (the level sets must all be subcubes, which for Boolean inputs essentially forces projections or constants), but that reading is implicit and the counting is never done. There is also a secondary mismatch: Section 5 says Traffic Lights MNIST has no reasoning shortcuts, but Definition 1 admits many label-preserving functions for β(c)=¬c1∨¬c2; the 'no RS' verdict depends on an architecture-specific notion that enters neither Definition 1 nor Theorem 7. The correct response is not rejection: the theorem is a useful necessary condition and the experimental section supports the qualitative point. But the headline claim should either be scoped to exhaustive A with a formal rarity statement, or softened. Hence Conditional rather than Unchanged.","tokens_in":37027,"tokens_out":28031,"duration_ms":368155,"concrete_test":"Enumerate all Boolean programs β:{0,1}^k→{0,1} for k=2,3. For each β, compute A_full={α : β∘α=β}. Check whether the condition of Theorem 7 holds for UCI weak RS-awareness over A_full, and whether a positive-weight product distribution can represent p_{A_full,π}. Repeat the same check for every two-element set A={id, α} with α non-identity. Report the fraction of programs in each family. If the full-A fraction is asymptotically negligible but the curated-A fraction is substantial, the 'rare cases' claim must be stated with the exhaustive-A qualification; if not, the abstract as written is supported.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Definition 3 and Theorem 7 are stated for any fixed set A of concept remappings. Nothing in the statement requires A to be the full set of all label-preserving functions for the task, and the proof of Theorem 7 never uses exhaustiveness. The 'extremely rare' headline therefore does not follow from the theorem as stated. Concrete example: for β(c)=c1∧c2 (AND), take A={id, α} with α(0,0)=(0,1), α(0,1)=(0,0), α(1,0)=(0,0), α(1,1)=(1,1). This α preserves β. The confusion sets are V_(0,0)=V_(0,1)={(0,0),(0,1)} (cover of c1=0), V_(1,0)={(1,0),(0,0)} (cover of c2=0), V_(1,1)={(1,1)}. All are implicant covers, so Theorem 7's condition is satisfied, and a universal UCI function can represent p_{A,π}. AND is not a 'meaningless partial supervision' program. If instead A is taken to be the full set of label-preserving functions, AND fails because V_(0,0) would contain three distinct concepts, which is not a subcube. Thus the conclusion 'only in extremely rare cases' is only justified under an exhaustive-A reading that the paper never defines. Section 5's claim that Traffic Lights has no RSs is likewise architecture-dependent, whereas Definition 1 admits many label-preserving maps.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies conditionally independent neurosymbolic predictors and their ability to be aware of reasoning shortcuts. It formalizes RS-awareness through sets of concept remappings A and mixtures p_{A,π} (Definitions 2 and 3), defines the universal conditionally independent (UCI) model class (Definition 4), and proves a necessary condition for weak RS-awareness (Theorem 7): all confusion sets must be covers of implicants of the label constraint. It also proves a necessary and sufficient condition for complete RS-awareness (Theorem 8). Experimentally, the paper compares independent, joint, and autoregressive models on XORMNIST and Traffic Lights MNIST, showing that independent models cannot represent the RS-aware distribution, while suitably designed expressive models can.","tokens_in":37325,"tokens_out":13172,"duration_ms":155558,"significance":"The formal criterion in Theorem 7 is clean and useful: for a fixed set of remappings, weak RS-awareness requires every confusion set to be an implicant cover, which is the same as having partial supervision over some concept variables. The proofs in Appendix A are clear, and the paper provides code and a careful empirical study with multiple seeds and architectures. The main caveat is that the headline claim that independence makes RS-awareness possible only in 'extremely rare cases' is stronger than the theorem as stated; the theorem quantifies over an arbitrary set A and does not establish genericity. This gap is fixable and does not undermine the correctness of the formal results.","major_comments":[{"comment":"The statement of Theorem 7 quantifies over an arbitrary set A of concept remappings, and the proof never uses exhaustiveness of A. The abstract and Contribution C2 claim that UCI models can be RS-aware only in 'extremely rare cases'. This conclusion does not follow from the theorem as stated. For example, for β(c)=c1∧c2, take A={id,α} with α(0,0)=(0,1), α(0,1)=(0,0), α(1,0)=(0,0), α(1,1)=(1,1). Every map in A satisfies Eq. (6), yet the confusion sets are V_(0,0)=V_(0,1)={(0,0),(0,1)} (cover of the implicant c1=0), V_(1,0)={(1,0),(0,0)} (cover of c2=0), and V_(1,1)={(1,1)}, so Theorem 7's condition holds for this A. Thus the paper should either formalize the 'rare' claim by defining a natural set of remappings (e.g., all label-preserving maps) and proving that the condition generically fails, or weaken the abstract and Section 4 wording to match the theorem.","section":"Section 4, Theorem 7; Abstract"},{"comment":"In Section 5, the paper states that Traffic Lights MNIST 'does not contain RSs for independent models.' This is not consistent with Definition 1, under which any non-identity α satisfying Eq. (6) is an RS. For β(c)=¬c1∨¬c2, the map α that swaps (0,1) and (1,0) and fixes (0,0) and (1,1) is label-preserving, so RSs exist under Definition 1. The claim is only true if A is restricted to remappings realizable by the shared per-digit architecture used for the independent model (cf. Footnote 3). This restriction should be stated explicitly in Definition 1 or the claim should be revised; otherwise the empirical comparison is framed around an architecture-specific notion while the formal results use a broader one.","section":"Section 5, Definition 1"}],"minor_comments":[{"comment":"The simplex is written as Δ^{k-1}, but the mixture is over m remappings; it should be Δ^{m-1}. Also, when m=1, the condition 0<π_i<1 for all i has no solution, so the definition of weak RS-awareness should either exclude this degenerate case or be clarified.","section":"Definition 3"},{"comment":"The argument invokes Theorem 4.3 of van Krieken et al. (2024) without stating it. Since this theorem is load-bearing for the proof, please include its statement (or at least its precise assumptions) so the proof is self-contained.","section":"Appendix A, proof of Theorem 7"},{"comment":"The phrase 'which give the probability that an RS mixture (Theorem 2 remapsc∗ toc' appears to be a typo or extraction error; it should refer to Definition 2 and to p_{A,π}(c|c*).","section":"Appendix A, Definition 9"},{"comment":"Reporting only mean±std for XORMNIST concept accuracy is uninformative because the results are bimodal (0% or 100%); please also report the fraction of seeds that found the reasoning shortcut.","section":"Table 1"}],"recommendation":"major_revision","confidential_remarks":"The formal core (Theorems 7 and 8) appears correct, and the empirical section is a genuine strength. The main risk to publication is the mismatch between Theorem 7 and the 'extremely rare' claim; I would recommend asking the authors to add a corollary that states the condition explicitly for the full set of label-preserving remappings and prove that, for k≥2 non-constant β, this condition reduces to projection-like programs (or to state a precise measure-theoretic genericity result). The AND example in this report shows that without such a corollary the abstract's claim is not supported. I do not see plagiarism or scope issues."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear [Colleague],\n\nThe core result is Theorem 7: if a universal conditionally independent model is weakly reasoning-shortcut-aware over a set A of remappings, then every confusion set must be the cover of an implicant of the label constraint. That is a clean, useful characterization, and the proof via Theorem 4.3 of van Krieken et al. (2024) is sound. The paper earns its place: it gives the first formal definition of RS-awareness, a necessary condition for independent models, a full characterization for complete awareness (Theorem 8), and an autoregressive architecture that is actually RS-aware on XORMNIST while staying accurate on Traffic Lights. The experiments are simple but honest.\n\nThe main soft spot is the gap between the theorem and the abstract. The theorem is stated for an arbitrary fixed A. Nothing in it requires A to be the full set of label-preserving maps, and the proof never uses exhaustiveness. The abstract's 'never' and the contributions' 'extremely rare' only follow if A is the full set. With a curated A, even AND satisfies the theorem's condition: take A = {id, α} where α maps (0,0) to (0,1), (0,1) to (0,0), (1,0) to (0,0), and fixes (1,1). The confusion sets are then implicant covers, and UCI is RS-aware. AND is not a 'meaningless' program. So the headline overstates the formal result. This is fixable: define A as the full set of label-preserving remappings (or a canonical subset) and check which programs satisfy the condition for that A.\n\nA smaller issue: Section 5's claim that Traffic Lights 'has no RSs' is architecture-dependent. Under Definition 1, NAND admits label-preserving maps, so the formal framework does allow RSs there. The empirical story still stands, but the wording should be softened.\n\nThe reliance on Theorem 4.3 from the authors' own ICML paper is fine—it is published and parameter-free—but reproducing its statement would make the proof more self-contained.\n\nOverall, this is a serious paper. The mathematical core is correct; the interpretive claims need tightening. I'd send it to a referee.","headline":"Solid formal characterization of when conditionally independent NeSy models can be RS-aware, but the 'extremely rare' claim only holds for the full set of remappings, which the paper never fixes.","tokens_in":37879,"tokens_out":5600,"would_cite":true,"duration_ms":64079,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68T37","68T27"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that neurosymbolic predictors using the conditional-independence assumption can only be aware of reasoning shortcuts in rare cases, and shows that expressive models with the right loss and architecture can hedge…","keywords":["reasoning shortcuts","neurosymbolic learning","conditional independence","concept uncertainty","probabilistic logic programming","XORMNIST","autoregressive concept models","expected calibration error"],"falsifier":"Train a conditionally independent NeSy predictor on XORMNIST, or any parity-style program with two-concept ambiguity, using the KL-to-uniform objective: if any run reaches perfect label accuracy while assigning 0.5/0.5 posterior mass to the two valid concept combinations on ambiguous inputs, Theorem 7 is refuted. The paper's own appendix predicts instead that independent models collapse to uniform, input-independent marginals; a brute-force search over $k=3$ boolean programs and remappings for a weakly reasoning-shortcut-aware independent model whose confusion set is not an implicant cover would settle the theorem directly.","tokens_in":36812,"feed_emoji":"🧩","tokens_out":8669,"duration_ms":95338,"temperature":0.7,"pith_summary":"The paper sets out to settle a live dispute: does the conditional-independence assumption used in most neurosymbolic (NeSy) predictors actually limit what they can learn, or is it harmless in practice? It claims that independence is a genuine ceiling: a model that factorises over symbolic concepts cannot represent uncertainty about concept combinations that are ambiguous under the label program, and therefore cannot be aware of reasoning shortcuts except in rare, nearly trivial settings. The paper proves two theorems characterising exactly when an independent model class can be reasoning-shortcut aware, illustrates the failure on the XORMNIST task, and shows that non-factorised models trained with a suitable loss can hedge correctly. If the claim holds, then reliability guarantees for the large class of NeSy systems built on independent concept factors are fragile exactly when the data leave multiple concept explanations open.","feed_headline":"Independence assumption blinds NeSy models to reasoning shortcuts","feed_subtitle":"Formal theorems show ambiguous concept pairs can't be hedged, so overconfident wrong explanations are guaranteed.","key_machinery":"The load-bearing objects are concept remappings, confusion sets, and implicant covers. A concept remapping $\\alpha$ is a non-identity function on ground-truth concepts that preserves the label under the program $\\beta$; each such remapping is a reasoning shortcut, and a mixture over several remappings is how a predictor would express uncertainty between correct and shortcut explanations. The confusion set $V_{c^*}$ collects all concepts reachable from a ground-truth world $c^*$ under the available remappings. Theorem 7 says an independent, factorised model class can represent such a mixture only when $V_{c^*}$ is the cover of an implicant of the label constraint — in other words, when the ambiguity is confined to variables that the program does not constrain. This turns the independence assumption itself into the mechanism doing the work: a factorised distribution over $k$ boolean concepts has only $k$ free parameters, so it cannot spread probability across arbitrary subsets of the concept cube, and overconfidence in one reasoning shortcut is the inevitable result.","core_discovery":"The central claim is that conditionally independent NeSy predictors are almost never reasoning-shortcut aware. Theorem 7 proves a necessary condition: if the universal class of conditionally independent models can weakly represent a mixture over a set of concept remappings, then for every ground-truth concept $c^*$, the confusion set $V_{c^*}$ — the set of concepts that the remappings can produce from $c^*$ — must be exactly the cover of an implicant of the label constraint $\\varphi_y$. Theorem 8 sharpens this for complete awareness: each confusion set must be a singleton or a pair of concepts differing in exactly one coordinate. The XORMNIST parity problem fails this test, because its confusion sets are $\\{(1,0),(0,1)\\}$ and $\\{(0,0),(1,1)\\}$, neither of which is an implicant cover, so an independent model cannot simultaneously solve the label task and express 0.5/0.5 uncertainty over the two valid concepts; the experiments show 11 of 20 runs committing to the reasoning shortcut. On the positive side, the paper demonstrates that a joint or autoregressive model with a KL-to-uniform loss can be reasoning-shortcut aware, with the autoregressive model also succeeding on a shortcut-free task where a plain joint model loses concept accuracy.","pith_inferences":["A practical design rule follows: if you keep independent concept factors, every concept variable the program does not pin down should either be marginalised out or modelled jointly, because independence can hedge at most one free variable.","The confusion-set-versus-implicant-cover criterion could be turned into a benchmark diagnostic: compute the maximum number of free variables in any confusion set of a program, and use it to predict which benchmarks will exhibit overconfident independent predictors.","The paper's result is restricted to full observability; under partial observability the ground-truth posterior is not factorised, which makes independence even less adequate, so an empirical study with occluded inputs would likely show larger reliability gaps.","The same criterion can serve as a post-hoc warning sign: a trained independent model that is highly confident on inputs whose ground truth has a non-implicant confusion set is probably exhibiting a reasoning shortcut, so its confidence should be discounted."],"forward_implications":["In any NeSy problem whose ambiguity spans two or more free concept variables, an independent-factor predictor that reaches perfect label accuracy has silently selected one reasoning shortcut and will report high confidence in it.","Changing the training loss cannot rescue independent models: the KL-to-uniform objective that makes expressive models reasoning-shortcut aware drives an independent model toward input-independent uniform marginals, so it stops learning the task at all.","Expressive concept distributions are necessary but not sufficient for reasoning-shortcut awareness; the paper's experiments show architecture choice matters, with the autoregressive model achieving both label accuracy and calibrated concept uncertainty on XORMNIST and Traffic Lights MNIST.","Concept-quality evaluation, such as expected calibration error on concepts, is what exposes reasoning-shortcut awareness; label accuracy alone is nearly identical between models that commit to the shortcut and models that hedge."],"supporting_citations":[{"why":"Defines reasoning shortcuts, the ground-truth generative process with assumptions A1 and A2, and the proposition that all concept distributions solving the input-label mapping are convex mixtures of remapping distributions; the paper's formalization builds directly on this.","marker":"Marconato et al. (2023)"},{"why":"Proves the theorem on independent distributions and implicants that the paper invokes to link a factorised distribution's support to an implicant cover, and supplies the earlier results on disconnected loss minima.","marker":"van Krieken et al. (2024)"},{"why":"States the skeptical position that independence is not a limiting issue in typical NeSy settings; the paper's formal results and Traffic Lights experiments are designed to answer it.","marker":"Faronius and Dos Martires (2025)"},{"why":"Introduces the unbiased-exploration / KL-to-uniform approach that the paper adapts as the loss enabling expressive models to be reasoning-shortcut aware.","marker":"Zombori et al. (2024)"},{"why":"Introduces BEARS, the ensemble approach whose reasoning-shortcut awareness notion the paper formalizes, and supplies the expected-calibration-error implementation used in the experiments.","marker":"Marconato et al. (2024)"},{"why":"Provides the semantic objective function whose adaptation appears in Equation 7 as the uniform-KL loss.","marker":"Mendez-Lucero et al. (2024)"}],"fun_headline_variants":["NeSy independence forces reasoning shortcuts, new proof shows","Independent NeSy can't hedge uncertainty, so reasoning shortcuts ensue","Formal proof: independence assumption guarantees reasoning shortcuts","NeSy independence locks out uncertainty, guaranteeing reasoning shortcuts","Why independence in NeSy leads to reasoning shortcuts"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The theorems presuppose that each input fully determines the true concepts through an invertible oracle and that the program deterministically maps concepts to labels; when inputs are only partial observations, the formal impossibility result no longer applies and the paper falls back on a looser expressivity argument.","fun_headline_variants_meta":{"raw":{"variants":["NeSy independence forces reasoning shortcuts, new proof shows","Independent NeSy can't hedge uncertainty, so reasoning shortcuts ensue","Formal proof: independence assumption guarantees reasoning shortcuts","NeSy independence locks out uncertainty, guaranteeing reasoning shortcuts","Why independence in NeSy leads to reasoning shortcuts"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001345,"raw_usage":{"total_tokens":5474,"prompt_tokens":962,"completion_tokens":4512,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":578,"completion_tokens_details":{"reasoning_tokens":4435}},"tokens_in":578,"tokens_out":4512,"duration_ms":35893,"temperature":1.0,"reasoning_tokens":4435,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T17:10:52.303289+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Train a conditionally independent NeSy predictor on XORMNIST, or any parity-style program with two-concept ambiguity, using the KL-to-uniform objective: if any run reaches perfect label accuracy while assigning 0.5/0.5 posterior mass to the two valid concept combinations on ambiguous inputs, Theorem 7 is refuted. The paper's own appendix predicts instead that independent models collapse to uniform, input-independent marginals; a brute-force search over $k=3$ boolean programs and remappings for a weakly reasoning-shortcut-aware independent model whose confusion set is not an implicant cover would settle the theorem directly.","supporting_citations":[{"cited_title":"Not All Neuro-Symbolic Concepts Are Created Equal : Analysis and Mitigation of Reasoning Shortcuts","cited_arxiv_id":null,"evidence_quote":"Defines reasoning shortcuts, the ground-truth generative process with assumptions A1 and A2, and the proposition that all concept distributions solving the input-label mapping are convex mixtures of remapping distributions; the paper's formalization builds directly on this."},{"cited_title":"Independence Is Not an Issue in Neurosymbolic AI","cited_arxiv_id":"2504.07851","evidence_quote":"States the skeptical position that independence is not a limiting issue in typical NeSy settings; the paper's formal results and Traffic Lights experiments are designed to answer it."},{"cited_title":"Towards unbiased exploration in partial label learning","cited_arxiv_id":null,"evidence_quote":"Introduces the unbiased-exploration / KL-to-uniform approach that the paper adapts as the loss enabling expressive models to be reasoning-shortcut aware."},{"cited_title":"Semantic Objective Functions: A distribution-aware method for adding logical constraints in deep learning","cited_arxiv_id":"2405.15789","evidence_quote":"Provides the semantic objective function whose adaptation appears in Equation 7 as the uniform-KL loss."}],"review_version":1}