# A-NeSI: A Scalable Approximate Method for Probabilistic Neurosymbolic Inference

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

## Key facts

- Cited by 50 papers in the map (data through 14 Oct 2026).
- Placed in Reasoning benchmarks and evaluation, one of 17 directions in LLM reasoning.
- Builds on 34 of its 64 references that are in the map.
- First posted on arXiv 23 Dec 2022.

## Placed in

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

## Builds on (most cited first, 30 of 34)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Categorical Reparameterization with Gumbel-Softmax](https://mlsanity.com/paper/1611.01144/) (2016)
- [Variational Inference with Normalizing Flows](https://mlsanity.com/paper/1505.05770/) (2015)
- [Modeling Relational Data with Graph Convolutional Networks](https://mlsanity.com/paper/1703.06103/) (2017)
- [A Distributional Perspective on Reinforcement Learning](https://mlsanity.com/paper/1707.06887/) (2017)
- [Neural Probabilistic Logic Programming in DeepProbLog](https://mlsanity.com/paper/1907.08194/) (2019)
- [Flow Network based Generative Models for Non-Iterative Diverse Candidate Generation](https://mlsanity.com/paper/2106.04399/) (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)
- [Trajectory balance: Improved credit assignment in GFlowNets](https://mlsanity.com/paper/2201.13259/) (2022)
- [On Completeness-aware Concept-Based Explanations in Deep Neural Networks](https://mlsanity.com/paper/1910.07969/) (2019)
- [Differentiation of Blackbox Combinatorial Solvers](https://mlsanity.com/paper/1912.02175/) (2019)
- [Efficient and Modular Implicit Differentiation](https://mlsanity.com/paper/2105.15183/) (2021)
- [Logic Tensor Networks](https://mlsanity.com/paper/2012.13635/) (2020)
- [Variational Lossy Autoencoder](https://mlsanity.com/paper/1611.02731/) (2016)
- [Gradient Estimation Using Stochastic Computation Graphs](https://mlsanity.com/paper/1506.05254/) (2015)
- [GFlowNets and variational inference](https://mlsanity.com/paper/2210.00580/) (2022)
- [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)
- [DeepStochLog: Neural Stochastic Logic Programming](https://mlsanity.com/paper/2106.12574/) (2021)
- [Memory Augmented Policy Optimization for Program Synthesis and Semantic Parsing](https://mlsanity.com/paper/1807.02322/) (2018)
- [Deep Learning with Logical Constraints](https://mlsanity.com/paper/2205.00523/) (2022)
- [Multi-Label Classification Neural Networks with Hard Logical Constraints](https://mlsanity.com/paper/2103.13427/) (2021)
- [NeuPSL: Neural Probabilistic Soft Logic](https://mlsanity.com/paper/2205.14268/) (2022)
- [Backpropagation through Combinatorial Algorithms: Identity with Projection Works](https://mlsanity.com/paper/2205.15213/) (2022)
- [Neuro-Symbolic Entropy Regularization](https://mlsanity.com/paper/2201.11250/) (2022)

## Built on by (most cited first, 30 of 50)

- [Amortizing intractable inference in large language models](https://mlsanity.com/paper/2310.04363/) (2023)
- [Not All Neuro-Symbolic Concepts Are Created Equal: Analysis and Mitigation of Reasoning Shortcuts](https://mlsanity.com/paper/2305.19951/) (2023)
- [Learning diverse attacks on large language models for robust red-teaming and safety tuning](https://mlsanity.com/paper/2405.18540/) (2024)
- [Improved off-policy training of diffusion samplers](https://mlsanity.com/paper/2402.05098/) (2024)
- [Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNets](https://mlsanity.com/paper/2305.17010/) (2023)
- [Neuro-Symbolic AI in 2024: A Systematic Review](https://mlsanity.com/paper/2501.05435/) (2025)
- [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)
- [HardNet: Hard-Constrained Neural Networks with Universal Approximation Guarantees](https://mlsanity.com/paper/2410.10807/) (2024)
- [How Realistic Is Your Synthetic Data? Constraining Deep Generative Models for Tabular Data](https://mlsanity.com/paper/2402.04823/) (2024)
- [A Neuro-Symbolic Benchmark Suite for Concept Quality and Reasoning Shortcuts](https://mlsanity.com/paper/2406.10368/) (2024)
- [On the Independence Assumption in Neurosymbolic Learning](https://mlsanity.com/paper/2404.08458/) (2024)
- [Beyond the convexity assumption: Realistic tabular data generation under quantifier-free real linear constraints](https://mlsanity.com/paper/2502.18237/) (2025)
- [Pre-Training and Fine-Tuning Generative Flow Networks](https://mlsanity.com/paper/2310.03419/) (2023)
- [Symbolic regression via MDLformer-guided search: from minimizing prediction error to minimizing description length](https://mlsanity.com/paper/2411.03753/) (2024)
- [Shortcuts and Identifiability in Concept-based Models from a Neuro-Symbolic Lens](https://mlsanity.com/paper/2502.11245/) (2025)
- [Neurosymbolic Diffusion Models](https://mlsanity.com/paper/2505.13138/) (2025)
- [Neuro-symbolic Learning Yielding Logical Constraints](https://mlsanity.com/paper/2410.20957/) (2024)
- [Neuro-Symbolic AI: Explainability, Challenges, and Future Trends](https://mlsanity.com/paper/2411.04383/) (2024)
- [ULLER: A Unified Language for Learning and Reasoning](https://mlsanity.com/paper/2405.00532/) (2024)
- [Latent Logic Tree Extraction for Event Sequence Explanation from LLMs](https://mlsanity.com/paper/2406.01124/) (2024)
- [On the Hardness of Probabilistic Neurosymbolic Learning](https://mlsanity.com/paper/2406.04472/) (2024)
- [LogiCity: Advancing Neuro-Symbolic AI with Abstract Urban Simulation](https://mlsanity.com/paper/2411.00773/) (2024)
- [Expected flow networks in stochastic environments and two-player zero-sum games](https://mlsanity.com/paper/2310.02779/) (2023)
- [Data-Efficient Learning with Neural Programs](https://mlsanity.com/paper/2406.06246/) (2024)
- [EXPLAIN, AGREE, LEARN: Scaling Learning for Neural Probabilistic Logic](https://mlsanity.com/paper/2408.08133/) (2024)
- [Neural Probabilistic Circuits: Enabling Compositional and Interpretable Predictions through Logical Reasoning](https://mlsanity.com/paper/2501.07021/) (2025)
- [Adaptive Destruction Processes for Diffusion Samplers](https://mlsanity.com/paper/2506.01541/) (2025)
- [Dolphin: A Programmable Framework for Scalable Neurosymbolic Learning](https://mlsanity.com/paper/2410.03348/) (2024)
- [The DeepLog Neurosymbolic Machine](https://mlsanity.com/paper/2508.13697/) (2025)

## Abstract (arXiv)

We study the problem of combining neural networks with symbolic reasoning. Recently introduced frameworks for Probabilistic Neurosymbolic Learning (PNL), such as DeepProbLog, perform exponential-time exact inference, limiting the scalability of PNL solutions. We introduce Approximate Neurosymbolic Inference (A-NeSI): a new framework for PNL that uses neural networks for scalable approximate inference. A-NeSI 1) performs approximate inference in polynomial time without changing the semantics of probabilistic logics; 2) is trained using data generated by the background knowledge; 3) can generate symbolic explanations of predictions; and 4) can guarantee the satisfaction of logical constraints at test time, which is vital in safety-critical applications. Our experiments show that A-NeSI is the first end-to-end method to solve three neurosymbolic tasks with exponential combinatorial scaling. Finally, our experiments show that A-NeSI achieves explainability and safety without a penalty in performance.