arXiv:2604.23377cs.AI2026-04

提出检测神经符号学习中推理捷径的方法,确保概念映射唯一性。

Constraint-Based Analysis of Reasoning Shortcuts in Neurosymbolic Learning

  • 将推理捷径建模为约束满足问题,用ASP验证映射唯一性。
  • 证明了唯一性需满足判别性质,但该条件不充分。
  • 开发修复算法并给出复杂度分析,适用于模型可解释性研究者。

神经符号系统在学习过程中可满足逻辑约束,但未必达成预期的概念-标签对应关系,这种现象称为推理捷径。本文将推理捷径形式化为约束满足问题,研究在何种条件下概念映射由约束唯一确定。证明在双射映射下,判别性质(即无法通过交换两个概念值得到另一有效映射)是避免捷径的必要条件,但即使约束图连通,该条件仍不充分。提出基于ASP的算法,可证明性地验证给定约束集是否唯一确定目标映射。当发现捷径时,设计贪心修复算法,最多经过k次迭代收敛,其中k为替代有效映射的数量。进一步提供复杂度分类:判断无捷径性为coNP完全,计数捷径为#P完全,寻找最小修复为NP难。还建立样本复杂度边界,表明在有利情况下对数级标签查询即可消歧,最坏情况需查询所有模糊位置。在八个基准领域上的实验验证了方法的有效性。

原文摘要 · Abstract (English)

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.

神经符号推理捷径约束求解可解释性

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。