Constraint-Based Analysis of Reasoning Shortcuts in Neurosymbolic Learning
Akihiro Takemura, Katsumi Inoue, Masaaki Nishino \affiliations National Institute of Informatics, Tokyo, Japan · 2026
Read Constraint-Based Analysis of Reasoning Shortcuts in Neurosymbolic Learning by Akihiro Takemura, Katsumi Inoue, Masaaki Nishino \affiliations National Institute of Informatics, Tokyo, Japan (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-23377.txt.
Introduction
Takemura, Inoue, and Nishino formalize reasoning shortcuts in neurosymbolic learning, where a system obeys logical constraints yet learns the wrong link between concepts and labels. They prove a discrimination condition is necessary but not sufficient for ruling shortcuts out, then give a verified algorithm that checks whether constraints pin down the intended mapping. They also classify the hardness of detecting, counting, and repairing shortcuts, and validate the method on eight benchmarks.
Catalog record
| CREATOR | Akihiro Takemura, Katsumi Inoue, Masaaki Nishino \affiliations National Institute of Informatics, Tokyo, Japan |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 82518 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.23377
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Constraint-Based Analysis of Reasoning Shortcuts in Neurosymbolic Learning Akihiro Takemura, Katsumi Inoue, Masaaki Nishino \affiliations National Institute of Informatics, Tokyo, Japan Abstract Neurosymbolic systems can satisfy logical constraints during learning without achieving the intended concept-label correspondence; this is a problem known as reasoning shortcuts. We formalize reasoning shortcuts as a constraint satisfaction problem and investigate under which conditions concept mappings are uniquely determined by the constraints. We prove that a discrimination property (requiring that no valid concept mapping can be transformed into another valid mapping by swapping two concept values) is necessary for shortcut-freeness under bijective mappings, but demonstrate via a counterexample that it is insufficient even when the constraint graph is connected. We develop an ASP-based algorithm that verifies whether a given constraint set uniquely determines the intended concept mapping, with proven soundness and completeness. When shortcuts are detected, a greedy repair algorithm eliminates them by augmenting the constraint set, converging in at most k k iterations, where k k is the number of alternative valid mappings. We further provide a complexity classification: deciding shortcut-freeness is coNP-complete, counting shortcuts is #P-complete, and finding minimal repairs is NP-hard. We also establish sample complexity bounds showing that logarithmically many label queries suffice for disambiguation in favorable cases, while querying all ambiguous positions suffices in the worst case. Experiments across eight benchmark domains validate our approach. 1 Introduction Neurosymbolic AI systems integrate neural perception with symbolic reasoning, combining the pattern recognition capabilities of deep learning with the reliability and explainability of symbolic logic [ 4 , 12 , 24 , 3 ] . However, recent work has identified a critical problem called reasoning shortcuts , where models satisfy constraints while learning concept mappings that differ from the intended correspondence [ 14 , 23 ] . Consider a neurosymbolic system for visual arithmetic: neural networks predict digit concepts from images, and constraints enforce arithmetic relationships (e.g., the labels assigned to two images must sum to 3). While the system may achieve high accuracy on training tasks, the learned concepts might be swapped , predicting 1 as 2 and vice versa, yet still satisfy all constraints. This reasoning shortcut undermines both correctness (concepts do not correspond to their intended labels) and robustness (fails on out-of-distribution tasks) [ 13 , 20 ] . We focus on the class of constraint-based neurosymbolic systems where logical rules over concept mappings are explicit (Definition 1 ); our results characterize when such a constraint set uniquely determines the intended concept mapping, and at what computational cost. Recent empirical work has developed mitigation strategies including uncertainty-aware methods [ 13 ] , theoretical risk analysis [ 23 ] , prototypical neurosymbolic architectures that encourage models to rely on correct internal evidence [ 2 ] , and comprehensive benchmarks [ 5 ] . However, it remains unclear whether and when constraints uniquely determine concept mappings , which is essential for deploying neurosymbolic systems with confidence. We approach this question by formalizing reasoning shortcuts as a constraint satisfaction problem (CSP). Given a set of constraints C over concept mappings \phi:N\to S , we ask, does C admit exactly one valid mapping (shortcut-free), or do multiple valid mappings exist (shortcuts present)? This CSP perspective enables us to: • Prove necessary conditions : Discrimination (no valid mapping related to another by a concept transposition) is necessary for shortcut-freeness (Theorem 1 ), but insufficient in general. We construct an explicit counterexample where discrimination holds yet shortcuts persist via longer permutation cycles, even with a connected constraint graph (Example 4 ). • Classify complexity : Deciding shortcut-freeness is coNP-complete, counting shortcuts is #P-complete, and finding minimal repairs is NP-hard (Theorems 4 – 6 ). • Bound disambiguation cost : We define a shortcut multiplicity measure with connections to the M-unambiguity [ 21 ] , and prove that logarithmically many label queries suffice for disambiguation in favorable cases, while querying all ambiguous positions suffices in the worst case (Theorem 2 ). • Provide practical algorithms : a verification algorithm based on Answer Set Programming (ASP) [ 8 ] , whose native model enumeration makes it well-suited to exhaustive shortcut search, with correctness guarantees (Algorithm 1 ), greedy repair that eliminates shortcuts by augmenting the constraint set with convergence guarantees (Algorithm 2 ), and active learning strategies. Our key observation is that reasoning shortcuts arise from symmetries in the constraint structure . Disconnected constraint graphs allow independent concept swaps within components (Example 1 ), while symmetric constraints such as modulo arithmetic admit rotational shortcuts even when the graph is connected (Example 4 ). This connects our work to classical symmetry-breaking in CSPs [ 9 ] , but extends it to the neurosymbolic setting where a specific ground-truth mapping must be uniquely determined. Our work complements existing neurosymbolic approaches, e.g., shortcut detection methods [ 14 , 23 ] , ASP-based systems [ 24 , 16 ] , Semantic Loss [ 22 ] , and Concept Bottleneck Models (CBMs) [ 11 ] , by providing the formal foundations : we prove when shortcuts can and cannot exist, characterize their computational complexity, and supply verification and repair algorithms with correctness guarantees. n_{0} n_{1} n_{2} n_{3} 0 1 2 3 Neural outputs Concept labels \phi^{*}\!=\!(0,1,2,3) \phi_{2}\!=\!(0,2,1,3) C_{1}\!:\phi(n_{0}){+}\phi(n_{3}){=}3 ✓ ✓ C_{2}\!:\phi(n_{1}){+}\phi(n_{2}){=}3 ✓ ✓ Figure 1: Reasoning shortcut in the 4-node addition problem (Example 1 ). Both the intended mapping \phi^{*} (solid) and the shortcut \phi_{2} (dashed) satisfy all constraints, but \phi_{2} incorrectly swaps concepts 1 and 2. Example 1 (Motivating Example: Simple Addition) . Consider learning a mapping from 4 neural outputs to 4 digit concepts using addition constraints (Figure 1 ): Problem setting: • Neural outputs: N=\{n_{0},n_{1},n_{2},n_{3}\} • Concept labels: S=\{0,1,2,3\} • Constraints: C_{1}:\phi(n_{0})+\phi(n_{3})=3 ; C_{2}:\phi(n_{1})+\phi(n_{2})=3 • Intended concept mapping \phi^{*}=\{n_{0}\mapsto 0,n_{1}\mapsto 1,n_{2}\mapsto 2,n_{3}\mapsto 3\} or equivalently in tuple notation, \phi(n_{i}) as the i -th entry: \phi^{*}=(0,1,2,3) Issue: There are multiple bijective mappings that satisfy all constraints. For example: • \phi_{1}=(0,1,2,3) — intended mapping • \phi_{2}=(0,2,1,3) — swaps n_{1}\leftrightarrow n_{2} • \phi_{3}=(3,1,2,0) — swaps n_{0}\leftrightarrow n_{3} • … (8 total bijective valid mappings) The network may learn any of these 8 mappings during training. If the learned mapping differs from \phi^{*} , test-time predictions will be systematically incorrect. The constraint graph G_{C} (Definition 2 ; Figure 2 ) decomposes into two disconnected components \{n_{0},n_{3}\} and \{n_{1},n_{2}\} , and this disconnection allows the two component-level transpositions to combine into 8 valid bijections. This paper also provides a mechanism to: (1) detect such shortcuts via ASP-based verification, and (2) eliminate them by augmenting the constraint set (e.g., adding “ \phi(n_{1})=1 ” reduces the 8 valid mappings to 4). Our framework provides immediately deployable tools for practitioners: ASP verification directly checks shortcut-freeness without requiring analytical proofs, repair algorithms systematically eliminate shortcuts with convergence guarantees, and active learning strategies achieve near-optimal label efficiency. This paper is organized as follows: Section 2 surveys related work. Section 3 introduces the problem setting and core definitions. Section 4 develops theoretical foundations: necessary conditions, their limitations, symmetry analysis, sample complexity bounds, and practical label selection strategies. Section 5 presents verification and repair algorithms with complexity analysis. Section 6 provides experimental validation across 8 benchmark domains. Section 7 concludes with open problems. 2 Related Works 2.1 Reasoning Shortcuts in Neurosymbolic Systems Marconato