# A Learnability Analysis on Neuro-Symbolic Learning

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 71 references that are in the map.
- First posted on arXiv 21 Mar 2025.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Scaling Laws for Neural Language Models](https://mlsanity.com/paper/2001.08361/) (2020)
- [FixMatch: Simplifying Semi-Supervised Learning with Consistency and Confidence](https://mlsanity.com/paper/2001.07685/) (2020)
- [Self-supervised Learning: Generative or Contrastive](https://mlsanity.com/paper/2006.08218/) (2020)
- [Deep Learning for Classical Japanese Literature](https://mlsanity.com/paper/1812.01718/) (2018)
- [Neural Probabilistic Logic Programming in DeepProbLog](https://mlsanity.com/paper/1907.08194/) (2019)
- [The Neuro-Symbolic Concept Learner: Interpreting Scenes, Words, and Sentences From Natural Supervision](https://mlsanity.com/paper/1904.12584/) (2019)
- [A Semantic Loss Function for Deep Learning with Symbolic Knowledge](https://mlsanity.com/paper/1711.11157/) (2017)
- [Informed Machine Learning -- A Taxonomy and Survey of Integrating Knowledge into Learning Systems](https://mlsanity.com/paper/1903.12394/) (2019)
- [Logic Tensor Networks](https://mlsanity.com/paper/2012.13635/) (2020)
- [Analyzing Differentiable Fuzzy Logic Operators](https://mlsanity.com/paper/2002.06100/) (2020)
- [Explainable Object-induced Action Decision for Autonomous Vehicles](https://mlsanity.com/paper/2003.09405/) (2020)
- [From Statistical Relational to Neurosymbolic Artificial Intelligence: a Survey](https://mlsanity.com/paper/2108.11451/) (2021)
- [Scallop: A Language for Neurosymbolic Programming](https://mlsanity.com/paper/2304.04812/) (2023)
- [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)
- [Neuro-Symbolic Continual Learning: Knowledge, Reasoning Shortcuts and Concept Rehearsal](https://mlsanity.com/paper/2302.01242/) (2023)
- [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)
- [Neuro-symbolic Learning Yielding Logical Constraints](https://mlsanity.com/paper/2410.20957/) (2024)
- [Learning with Logical Constraints but without Shortcut Satisfaction](https://mlsanity.com/paper/2403.00329/) (2024)
- [On the Hardness of Probabilistic Neurosymbolic Learning](https://mlsanity.com/paper/2406.04472/) (2024)
- [Efficient Rectification of Neuro-Symbolic Reasoning Inconsistencies by Abductive Reflection](https://mlsanity.com/paper/2412.08457/) (2024)
- [Symbolic Knowledge Extraction and Injection with Sub-symbolic Predictors: A Systematic Literature Review](https://mlsanity.com/paper/2501.14836/) (2025)
- [Deciphering Raw Data in Neuro-Symbolic Learning with Provable Guarantees](https://mlsanity.com/paper/2308.10487/) (2023)
- [Relational Neurosymbolic Markov Models](https://mlsanity.com/paper/2412.13023/) (2024)
- [Valid Text-to-SQL Generation with Unification-based DeepStochLog](https://mlsanity.com/paper/2503.13342/) (2025)
- [Reduced Implication-bias Logic Loss for Neuro-Symbolic Learning](https://mlsanity.com/paper/2208.06838/) (2022)

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

- [Quantitative Estimation of Target Task Performance from Unsupervised Pretext Task in Semi/Self-Supervised Learning](https://mlsanity.com/paper/2508.07299/) (2025)
- [Curriculum Abductive Learning](https://mlsanity.com/paper/2505.12275/) (2025)
- [Candidate Retention for Abductive Learning](https://mlsanity.com/paper/2609.39561/) (2026)

## Abstract (arXiv)

This paper analyzes the learnability of neuro-symbolic (NeSy) tasks within hybrid systems. We show that the learnability of NeSy tasks can be characterized by their derived constraint satisfaction problems (DCSPs). Specifically, a task is learnable if the corresponding DCSP has a unique solution; otherwise, it is unlearnable. For learnable tasks, we establish error bounds by exploiting the clustering property of the hypothesis space. Additionally, we analyze the asymptotic error for general NeSy tasks, showing that the expected error scales with the disagreement among solutions. Our results offer a principled approach to determining learnability and provide insights into the design of new algorithms.