# A Complexity Map of Probabilistic Reasoning for Neurosymbolic Classification Techniques

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Reasoning benchmarks and evaluation, one of 17 directions in LLM reasoning.
- Builds on 17 of its 63 references that are in the map.
- First posted on arXiv 12 Apr 2024.

## Placed in

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

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

- [ImageNet Large Scale Visual Recognition Challenge](https://mlsanity.com/paper/1409.0575/) (2014)
- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Differentiation of Blackbox Combinatorial Solvers](https://mlsanity.com/paper/1912.02175/) (2019)
- [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)
- [Semantic Probabilistic Layers for Neuro-Symbolic Learning](https://mlsanity.com/paper/2206.00426/) (2022)
- [Implicit MLE: Backpropagating Through Discrete Exponential Family Distributions](https://mlsanity.com/paper/2106.01798/) (2021)
- [NeurASP: Embracing Neural Networks into Answer Set Programming](https://mlsanity.com/paper/2307.07700/) (2023)
- [Fine-Grained Car Detection for Visual Census Estimation](https://mlsanity.com/paper/1709.02480/) (2017)
- [A-NeSI: A Scalable Approximate Method for Probabilistic Neurosymbolic Inference](https://mlsanity.com/paper/2212.12393/) (2022)
- [SIMPLE: A Gradient Estimator for k-Subset Sampling](https://mlsanity.com/paper/2210.01941/) (2022)
- [Neuro-Symbolic Entropy Regularization](https://mlsanity.com/paper/2201.11250/) (2022)
- [Semantic Strengthening of Neuro-Symbolic Learning](https://mlsanity.com/paper/2302.14207/) (2023)
- [Connecting Knowledge Compilation Classes and Width Parameters](https://mlsanity.com/paper/1811.02944/) (2018)
- [T-Norms Driven Loss Functions for Machine Learning](https://mlsanity.com/paper/1907.11468/) (2019)
- [An Abstract View on Optimizations in Propositional Frameworks](https://mlsanity.com/paper/2206.06440/) (2022)
- [Pseudo Polynomial-Time Top-k Algorithms for d-DNNF Circuits](https://mlsanity.com/paper/2202.05938/) (2022)

## Abstract (arXiv)

Neurosymbolic artificial intelligence is a growing field of research aiming to combine neural network learning capabilities with the reasoning abilities of symbolic systems. Informed multi-label classification is a sub-field of neurosymbolic AI which studies how to leverage prior knowledge to improve neural classification systems. Recently, a family of neurosymbolic techniques for informed classification based on probabilistic reasoning has gained significant traction. Unfortunately, depending on the language used to represent prior knowledge, solving certain probabilistic reasoning problems can become prohibitively hard when the number of classes increases. Therefore, the asymptotic complexity of probabilistic reasoning is of cardinal importance to assess the scalability of such techniques. In this paper, we develop a unified formalism for four probabilistic reasoning problems. Then, we compile several known and new tractability results into a single complexity map of probabilistic reasoning. We build on top of this complexity map to characterize the domains of scalability of several techniques. We hope this work will help neurosymbolic AI practitioners navigate the scalability landscape of probabilistic neurosymbolic techniques.