DPNL: A DPLL-based Algorithm for Probabilistic Neurosymbolic Learning
Thomas Jean-Michel Valentin, Luisa Sophie Werner, Nabil Layaïda, Pierre Genevès · HAL (Le Centre pour la Communication Scientifique Directe) · 2025
Neurosymbolic AI aims to integrate neural networks with symbolic reasoning. Within this field, probabilistic neurosymbolic learning (PNL) reduces inference tasks to the Probabilistic Weighted Model Counting problem. A key step in this reduction, used in seminal systems such as Deep-ProbLog, involves computing a Boolean formula called the logical provenance, which encodes the input combinations that can yield a given output. However, the size of this formula can grow exponentially, creating a major bottleneck that limits the scalability and practical applicability of existing PNL systems. We introduce a novel approach, DPNL, which avoids computing the full logical provenance. DPNL performs exact logical inference through a recursive, DPLLstyle decomposition, guided by oracles that prune the search space as early as possible. These oracles can be either automatically generated or manually crafted. We prove that the resulting oracles are valid, enjoy effective pruning capabilities, and that DPNL is correct and terminates. This new approach opens the door to a next generation of PNL systems in which symbolic reasoning is performed efficiently in a modular manner. Experimental results show that DPNL has the potential to scale exact inference further, resulting in more accurate neurosymbolic models.