# Constraint-Based Analysis of Reasoning Shortcuts in Neurosymbolic Learning

arXiv: https://arxiv.org/abs/2604.23377 · HTML: https://mlsanity.com/paper/2604.23377/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 28 references that are in the map.
- First posted on arXiv 25 Apr 2026.

## Builds on (most cited first, 11 of 11)

- [Concept Bottleneck Models](https://mlsanity.com/paper/2007.04612/) (2020)
- [A Semantic Loss Function for Deep Learning with Symbolic Knowledge](https://mlsanity.com/paper/1711.11157/) (2017)
- [Neural-Symbolic Learning and Reasoning: A Survey and Interpretation](https://mlsanity.com/paper/1711.03902/) (2017)
- [Not All Neuro-Symbolic Concepts Are Created Equal: Analysis and Mitigation of Reasoning Shortcuts](https://mlsanity.com/paper/2305.19951/) (2023)
- [BEARS Make Neuro-Symbolic Models Aware of their Reasoning Shortcuts](https://mlsanity.com/paper/2402.12240/) (2024)
- [A Neuro-Symbolic Benchmark Suite for Concept Quality and Reasoning Shortcuts](https://mlsanity.com/paper/2406.10368/) (2024)
- [On Learning Latent Models with Multi-Instance Weak Supervision](https://mlsanity.com/paper/2306.13796/) (2023)
- [Shortcuts and Identifiability in Concept-based Models from a Neuro-Symbolic Lens](https://mlsanity.com/paper/2502.11245/) (2025)
- [Answer Set Networks: Casting Answer Set Programming into Deep Learning](https://mlsanity.com/paper/2412.14814/) (2024)
- [Right for the Right Reasons: Avoiding Reasoning Shortcuts via Prototypical Neurosymbolic AI](https://mlsanity.com/paper/2510.25497/) (2025)
- [PiShield: A PyTorch Package for Learning with Requirements](https://mlsanity.com/paper/2402.18285/) (2024)

## Built on by (most cited first, 1 of 1)

- [Reasoning Shortcuts and Value Symmetries: What Symmetry Permits, Architecture Realizes, and Optimization Selects](https://mlsanity.com/paper/2608.10420/) (2026)

## Abstract (arXiv)

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.