Constraint-Based Analysis of Reasoning Shortcuts in Neurosymbolic Learning

• URL: http://arxiv.org/abs/2604.23377v1
• Date: Sat, 25 Apr 2026 16:51:48 GMT
• Title: Constraint-Based Analysis of Reasoning Shortcuts in Neurosymbolic Learning
• Abstract summary: We formalize reasoning shortcuts as a constraint satisfaction problem.<n>We develop an ASP-based algorithm that verifies whether a given constraint set uniquely determines the intended concept mapping.<n>We also provide a complexity classification: deciding shortcut-freeness is coNP-complete, counting shortcuts is #P-complete, and finding minimal repairs is NP-hard.
• Score: 10.5155061359458
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Which bird does not have wings: Negative-constrained KGQA with Schema-guided Semantic Matching and Self-directed Refinement [5.784146913646395]
  We introduce a new task, NEgative-conSTrained (NEST) KGQA, where each question contains at least one negative constraint.<n>We also design PyLF, a Python-formatted logical form, since existing logical forms are hardly suitable to express negation clearly.<n>We present a novel framework named CUCKOO, specialized to multiple-constrained questions and ensuring semantic executability.
  arXiv  Detail & Related papers  (2026-04-16T08:02:55Z)
• OrLog: Resolving Complex Queries with LLMs and Probabilistic Reasoning [51.58235452818926]
  We introduce OrLog, a neuro-symbolic retrieval framework that decouples predicate-level plausibility estimation from logical reasoning.<n>A large language model (LLM) provides plausibility scores for atomic predicates in one decoding-free forward pass, from which a probabilistic reasoning engine derives the posterior probability of query satisfaction.
  arXiv  Detail & Related papers  (2026-01-30T15:31:58Z)
• CoT-Seg: Rethinking Segmentation with Chain-of-Thought Reasoning and Self-Correction [50.67483317563736]
  This paper aims to explore a system that can think step-by-step, look up information if needed, generate results, self-evaluate its own results, and refine the results.<n>We introduce CoT-Seg, a training-free framework that rethinks reasoning segmentation by combining chain-of-thought reasoning with self-correction.
  arXiv  Detail & Related papers  (2026-01-24T11:41:54Z)
• Syzygy of Thoughts: Improving LLM CoT with the Minimal Free Resolution [59.39066657300045]
  Chain-of-Thought (CoT) prompting enhances the reasoning of large language models (LLMs) by decomposing problems into sequential steps.<n>We propose Syzygy of Thoughts (SoT)-a novel framework that extends CoT by introducing auxiliary, interrelated reasoning paths.<n>SoT captures deeper logical dependencies, enabling more robust and structured problem-solving.
  arXiv  Detail & Related papers  (2025-04-13T13:35:41Z)
• Critical Thinking: Which Kinds of Complexity Govern Optimal Reasoning Length? [72.70486097967124]
  We formalize a framework using deterministic finite automata (DFAs)<n>We show that there exists an optimal amount of reasoning tokens such that the probability of producing a correct solution is maximized.<n>We then demonstrate an implication of these findings: being able to predict the optimal number of reasoning tokens for new problems and filtering out non-optimal length answers results in consistent accuracy improvements.
  arXiv  Detail & Related papers  (2025-04-02T17:45:58Z)
• Greedy Algorithm for Structured Bandits: A Sharp Characterization of Asymptotic Success / Failure [50.46052024418364]
  We study the greedy (exploitation-only) algorithm in bandit problems with a known reward structure.<n>Our characterization extends to contextual bandits and interactive decision-making with arbitrary feedback.
  arXiv  Detail & Related papers  (2025-03-06T01:51:11Z)
• Testing Stationarity Concepts for ReLU Networks: Hardness, Regularity, and Robust Algorithms [31.478874616470048]
  We study the computational problem of the stationarity test for the empirical loss of neural networks with ReLU activation functions. We show that checking a certain first-order approximate stationarity concept for a piecewise linear function is co-NP-hard. We introduce an algorithmic scheme to test near-approximate stationarity in terms of both Clarke and Fr'echet subdifferentials.
  arXiv  Detail & Related papers  (2023-02-23T17:26:51Z)
• Improved Algorithms for Agnostic Pool-based Active Classification [20.12178157010804]
  We consider active learning for binary classification in the agnostic pool-based setting. Our algorithm is superior to state of the art active learning algorithms on image classification datasets.
  arXiv  Detail & Related papers  (2021-05-13T18:24:30Z)
• An Efficient Diagnosis Algorithm for Inconsistent Constraint Sets [68.8204255655161]
  We introduce a divide-and-conquer based diagnosis algorithm (FastDiag) which identifies minimal sets of faulty constraints in an over-constrained problem. We compare FastDiag with the conflict-directed calculation of hitting sets and present an in-depth performance analysis.
  arXiv  Detail & Related papers  (2021-02-17T19:55:42Z)
• A tetrachotomy of ontology-mediated queries with a covering axiom [1.749935196721634]
  Our concern is the problem of efficiently determining the data complexity of answering queries mediated by description and their optimal rewritings to standard database queries. We focus on Boolean conjunctive-mediated queries called disjunctive sirups (or d-sirups) Some d-sirups only have exponential-size resolution features, some only double-exponential-size positive existential existential-rewritings and single-exprecursive datalog rewritings.
  arXiv  Detail & Related papers  (2020-06-07T14:47:07Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.