Constraint-Based Analysis of Reasoning Shortcuts in Neurosymbolic Learning

Computer Science > Artificial Intelligence arXiv:2604.23377 (cs) [Submitted on 25 Apr 2026] Title:Constraint-Based Analysis of Reasoning Shortcuts in Neurosymbolic Learning Authors:Akihiro Takemura, Katsumi Inoue, Masaaki Nishino View a PDF of the paper titled Constraint-Based Analysis of Reasoning Shortcuts in Neurosymbolic Learning, by Akihiro Takemura and 2 other authors View PDF HTML (experimental) 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$ iterations, where $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. Comments: This is the full version of a paper appearing at the 23rd International Conference on Principles of Knowledge Representation and Reasoning (KR 2026) Subjects: Artificial Intelligence (cs.AI) Cite as: arXiv:2604.23377 [cs.AI] (or arXiv:2604.23377v1 [cs.AI] for this version) https://doi.org/10.48550/arXiv.2604.23377 Focus to learn more arXiv-issued DOI via DataCite Submission history From: Akihiro Takemura [view email] [v1] Sat, 25 Apr 2026 16:51:48 UTC (44 KB) Full-text links: Access Paper: View a PDF of the paper titled Constraint-Based Analysis of Reasoning Shortcuts in Neurosymbolic Learning, by Akihiro Takemura and 2 other authorsView PDFHTML (experimental)TeX Source view license Current browse context: cs.AI < prev | next > new | recent | 2026-04 Change to browse by: cs References & Citations NASA ADSGoogle Scholar Semantic Scholar export BibTeX citation Loading... BibTeX formatted citation × loading... Data provided by: Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Code, Data and Media Associated with this Article alphaXiv Toggle alphaXiv (What is alphaXiv?) Links to Code Toggle CatalyzeX Code Finder for Papers (What is CatalyzeX?) DagsHub Toggle DagsHub (What is DagsHub?) GotitPub Toggle Gotit.pub (What is GotitPub?) Huggingface Toggle Hugging Face (What is Huggingface?)…

This excerpt is published under fair use for community discussion. Read the full article at arXiv.org.