# On the Hardness of Probabilistic Neurosymbolic Learning

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Placed in Reasoning benchmarks and evaluation, one of 17 directions in LLM reasoning.
- Builds on 24 of its 56 references that are in the map.
- First posted on arXiv 6 Jun 2024.

## Placed in

- LLM reasoning / [Reasoning benchmarks and evaluation](https://mlsanity.com/lr/reasoning-benchmarks-and-evaluation/)

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

- [Estimating or Propagating Gradients Through Stochastic Neurons for Conditional Computation](https://mlsanity.com/paper/1308.3432/) (2013)
- [The Concrete Distribution: A Continuous Relaxation of Discrete Random Variables](https://mlsanity.com/paper/1611.00712/) (2016)
- [Neural Probabilistic Logic Programming in DeepProbLog](https://mlsanity.com/paper/1907.08194/) (2019)
- [GFlowNet Foundations](https://mlsanity.com/paper/2111.09266/) (2021)
- [Monte Carlo Gradient Estimation in Machine Learning](https://mlsanity.com/paper/1906.10652/) (2019)
- [A Semantic Loss Function for Deep Learning with Symbolic Knowledge](https://mlsanity.com/paper/1711.11157/) (2017)
- [Logic Tensor Networks](https://mlsanity.com/paper/2012.13635/) (2020)
- [Neural-Symbolic Computing: An Effective Methodology for Principled Integration of Machine Learning and Reasoning](https://mlsanity.com/paper/1905.06088/) (2019)
- [Semantic Probabilistic Layers for Neuro-Symbolic Learning](https://mlsanity.com/paper/2206.00426/) (2022)
- [Analyzing Differentiable Fuzzy Logic Operators](https://mlsanity.com/paper/2002.06100/) (2020)
- [Implicit MLE: Backpropagating Through Discrete Exponential Family Distributions](https://mlsanity.com/paper/2106.01798/) (2021)
- [From Statistical Relational to Neurosymbolic Artificial Intelligence: a Survey](https://mlsanity.com/paper/2108.11451/) (2021)
- [A-NeSI: A Scalable Approximate Method for Probabilistic Neurosymbolic Inference](https://mlsanity.com/paper/2212.12393/) (2022)
- [ROAD-R: The Autonomous Driving Dataset with Logical Requirements](https://mlsanity.com/paper/2210.01597/) (2022)
- [The Model Counting Competition 2020](https://mlsanity.com/paper/2012.01323/) (2020)
- [On the Independence Assumption in Neurosymbolic Learning](https://mlsanity.com/paper/2404.08458/) (2024)
- [Softened Symbol Grounding for Neuro-symbolic Systems](https://mlsanity.com/paper/2403.00323/) (2024)
- [Distribution-Aware Sampling and Weighted Model Counting for SAT](https://mlsanity.com/paper/1404.2984/) (2014)
- [Differentiable Sampling of Categorical Distributions Using the CatLog-Derivative Trick](https://mlsanity.com/paper/2311.12569/) (2023)
- [Semantic Strengthening of Neuro-Symbolic Learning](https://mlsanity.com/paper/2302.14207/) (2023)
- [Learning to Reason: Leveraging Neural Networks for Approximate DNF Counting](https://mlsanity.com/paper/1904.02688/) (2019)
- [Approximate Knowledge Compilation by Online Collapsed Importance Sampling](https://mlsanity.com/paper/1805.12565/) (2018)
- [Semirings for Probabilistic and Neuro-Symbolic Logic Programming](https://mlsanity.com/paper/2402.13782/) (2024)
- [Understanding the Complexity of Lifted Inference and Asymmetric Weighted Model Counting](https://mlsanity.com/paper/1405.3250/) (2014)

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

- [Neurosymbolic Diffusion Models](https://mlsanity.com/paper/2505.13138/) (2025)
- [A Learnability Analysis on Neuro-Symbolic Learning](https://mlsanity.com/paper/2503.16797/) (2025)
- [Right for the Right Reasons: Avoiding Reasoning Shortcuts via Prototypical Neurosymbolic AI](https://mlsanity.com/paper/2510.25497/) (2025)
- [Quantum Algorithms for Weighted Constrained Sampling and Weighted Model Counting](https://mlsanity.com/paper/2407.12816/) (2024)
- [Curriculum Abductive Learning](https://mlsanity.com/paper/2505.12275/) (2025)
- [Weakly Supervised Segmentation as Semantic-Based Regularization](https://mlsanity.com/paper/2605.13674/) (2026)
- [LTLZinc: a Benchmarking Framework for Continual Learning and Neuro-Symbolic Temporal Reasoning](https://mlsanity.com/paper/2507.17482/) (2025)
- [DeepProofLog: Efficient Proving in Deep Stochastic Logic Programs](https://mlsanity.com/paper/2511.08581/) (2025)
- [EM-NeSy: Expectation Maximization for Neurosymbolic Learning](https://mlsanity.com/paper/2606.14463/) (2026)

## Abstract (arXiv)

The limitations of purely neural learning have sparked an interest in probabilistic neurosymbolic models, which combine neural networks with probabilistic logical reasoning. As these neurosymbolic models are trained with gradient descent, we study the complexity of differentiating probabilistic reasoning. We prove that although approximating these gradients is intractable in general, it becomes tractable during training. Furthermore, we introduce WeightME, an unbiased gradient estimator based on model sampling. Under mild assumptions, WeightME approximates the gradient with probabilistic guarantees using a logarithmic number of calls to a SAT solver. Lastly, we evaluate the necessity of these guarantees on the gradient. Our experiments indicate that the existing biased approximations indeed struggle to optimize even when exact solving is still feasible.