# DPNL: A DPLL-based Algorithm for Probabilistic Neurosymbolic Learning

Thomas Jean-Michel Valentin, Luisa Sophie Werner, Nabil Layaïda, Pierre Genevès

► To cite this version:

Thomas Jean-Michel Valentin, Luisa Sophie Werner, Nabil Layaïda, Pierre Genevès. DPNL: A DPLL-based Algorithm for Probabilistic Neurosymbolic Learning. 2025. hal-05189824

HAL Id: hal-05189824

https://hal.science/hal-05189824v1

Preprint submitted on 29 Jul 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# DPNL: A DPLL-based Algorithm for Probabilistic Neurosymbolic Learning

Thomas Jean-Michel Valentin<fnref n="1" />,<fnref n="2" />, Luisa Sophie Werner<fnref n="1" />, Nabil Layaïda<fnref n="1" />, Pierre Genèves<fnref n="1" />

## Abstract

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, DPLL-style 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.

## Introduction

Neurosymbolic artificial intelligence van Harmelen and ten Teije (2019); Vermeulen, Manhaeve, and Marra (2023) seeks to integrate neural perception with symbolic methods to produce more accurate, efficient, and reliable models. Probabilistic Neurosymbolic Learning (PNL) is a research direction that combines neural networks with probabilistic reasoning De Raedt et al. (2020); Li, Huang, and Naik (2023). Neural networks are employed to extract probability distributions from raw data. They are end-to-end integrated with the reasoning process of a logic program to derive solutions. In contrast to pure neural black-box models, the passage through a logic program provides a clear lineage of how a result is derived, enhancing interpretability. However, PNL systems face significant scalability challenges due to the complexity of the inference in the logic program. Specifically, prominent systems for exact inference such as Deep-ProbLog Manhaeve et al. (2018) rely on a reduction to the Probabilistic Weighted Model Counting problem (PWMC).

However, a fundamental drawback of existing reductions to PWMC is the calculation of the logical provenance formula from the logic program. This is the computation of a DNF representing the set of models in which the user query admits a proof. The drawback is that these clauses are not disjoint, and the DNF is most often of exponential size. Therefore PWMC, which is #P-hard, is far from trivial in practice. This significantly limits the applicability of PNL systems, as they struggle to handle large problem instances effectively. Approximations have been developed to overcome these scalability issues Manhaeve, Marra, and De Raedt (2021); Winters et al. (2022); van Krieken et al. (2023); Huang et al. (2021). However, this potentially undermines one of the primary benefit of PNL: increased confidence in the reliability of the model.

**Contribution.** We introduce a new approach for probabilistic neurosymbolic learning to overcome this drawback. It is based on a new algorithm, DPNL, for exact probabilistic reasoning. One of its main advantages is that it bypasses the explicit computation of the logical provenance formula. Instead, DPNL relies on a recursive decomposition of probabilistic computations in a DPLL-inspired manner. This enables the use of oracles to guide and accelerate the logical inference process. We propose a method to automatically construct valid oracles, and we formally prove the termination and correctness of DPNL. Experiments demonstrate that DPNL has the potential to scale exact inference further, resulting in more accurate neurosymbolic models.

## Problem statement and definitions

We first introduce a general formalization of the entangled integration between symbolic programs and neural networks. This formalization allows us to go beyond existing methods which are subject to their specific calculation technique based on logical provenance computation and knowledge compilation. To the best of our knowledge, this is the first such general formalization. It opens the door to alternative reductions to PWMC. For that purpose, we first introduce a definition of the Probabilistic Learning (PL) problem and then we define Probabilistic Neurosymbolic Learning (PNL) systems.

We introduce some notations. A function $f$ that maps elements from a set $A$ to a set $B$ is denoted as $f: A \to B$.

<footnote n="1">¹TYREX Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG, 655 av Europe, 38330 Montbonnot Saint Martin, France, https://www.inria.fr/fr/tyrex</footnote>

<footnote n="2">²ENS Paris-Saclay, 4 av des Sciences, 91190 Gif-sur-Yvette, France, https://ens-paris-saclay.fr/thomas.valentin@ens-paris-saclay.fr, {luisa.werner, pierre.geneves}@inria.fr</footnote>
The set of all such functions is written as $\mathcal{F}(A, B)$. For any function $f: A \to B$ and any $y \in B$, the preimage of $y$, i.e., the set of all $x \in A$ such that $f(x) = y$, is denoted by $f^{-1}(y)$. An estimator of a function $f$ is denoted by $\hat{f}$.

**Probabilistic Learning Problem.** A PL problem is a quadruplet $P = ((\Omega, A, \mathbb{P}), \mathcal{I}, \mathcal{O}, F)$ where:

* $(\Omega, A, \mathbb{P})$ is a probability space with sample space $\Omega$, event space $A$ and probability function $\mathbb{P}$.

* $\mathcal{I}$ is the input space.

* $\mathcal{O}$ is the finite output set.

* $F: \mathcal{I} \to \mathcal{F}(\Omega, \mathcal{O})$ is a function that maps each input $i \in \mathcal{I}$ to its output random variable $F(i)$.

The probability distribution of $P$ is the function $p$ that maps every input $i$ to the probability distribution of $F(i)$:

$$ \forall i \in \mathcal{I}, p(i) : o \in \mathcal{O} \mapsto \mathbb{P}(F(i) = o). $$

We define solving $P$ as estimating $p$.

**Example 1 (MNIST Classification).** Consider the MNIST classification task. The goal is to recognise handwritten digits in images, e.g. the digit in $\mathfrak{F}$ is 8. This task can be modelled as the MNIST PL problem $((\Omega, A, \mathbb{P}), \mathcal{I}_{MNIST}, \mathcal{O}_{MNIST}, F_{MNIST})$, where $\mathcal{I}_{MNIST} = \mathbb{R}^{28 \times 28}$ represents the space of all possible images, $\mathcal{O}_{MNIST} = [0, 9]$ is the set of possible output labels, and $F_{MNIST}$ associates with each image $i$ the random variable $F_{MNIST}(i)$ for the digit in $i$. Solving the MNIST PL problem amounts to estimating the function $p_{MNIST}$ that maps each image $i$ to the probability distribution of $F_{MNIST}(i)$, which can be done using a neural network $\hat{p}_{MNIST}$.

**Probabilistic Neurosymbolic Learning System.** Let $P = ((\Omega, A, \mathbb{P}), \mathcal{I}, \mathcal{O}, F)$ be a PL problem and $p$ its corresponding probability distribution. A PNL system for $P$ is a quadruplet $((V_k)_{1 \le k \le m}, (X_k)_{1 \le k \le m}, (\hat{p}_k)_{1 \le k \le m}, S)$ where:

* $m \ge 1$ is the order of the PNL system.

* $\forall k \in [1, m], P_k = ((\Omega, A, \mathbb{P}), \mathcal{I}, V_k, X_k)$ is a PL problem with its probability distribution $p_k$.

* $\forall i \in \mathcal{I}$, the random variables $(X_k(i))_{1 \le k \le m}$ are independent. We say that the sub-problems $(\hat{P}_k)_{1 \le k \le m}$ are independent.

* $\forall k \in [1, m], \hat{p}_k$ is a neural network which solves $P_k$, i.e., it estimates $p_k$. The set of learnable parameters of $\hat{p}_k$ is $\theta_k$.

* $S: V_1 \times \dots \times V_m \to \mathcal{O}$ is a symbolic function that maps values obtained from the sub-problems to the output. $S$ is known.

* $F = S \circ (X_1, \dots, X_m)$, that is, for all $i \in \mathcal{I}$ and $w \in \Omega$, $F(i)(w) = S(X_1(i)(w), \dots, X_m(i)(w))$.

The PNL system decomposes $P$ into $m$ smaller, independent sub-problems $(P_k)_{1 \le k \le m}$. Each sub-problem $P_k$ is solved by estimating $p_k$ with a neural network $\hat{p}_k$. The outputs of the neural networks are then combined using the symbolic function $S$ to estimate $p$ thanks to the following relation,

which holds because of the independence assumption of the random variables:

$$ p(i)(o) = \sum_{(x_1, \dots, x_m) \in S^{-1}(o)} \mathbb{P}(\bigcap_{k=1}^{m} X_k(i) = x_k) \quad (1) $$

$$ = \sum_{(x_1, \dots, x_m) \in S^{-1}(o)} \prod_{k=1}^{m} p_k(i)(x_k). \quad (2) $$

The corresponding estimator $\hat{p}$ is defined by:

$$ \hat{p}(i)(o) = \sum_{(x_1, \dots, x_m) \in S^{-1}(o)} \prod_{k=1}^{m} \hat{p}_k(i)(x_k). \quad (3) $$

Moreover, $\hat{p}(i)(o)$ is differentiable w.r.t. to the parameters $\theta = (\theta_k)_{1 \le k \le m}$ of all the neural networks $\hat{p}_k$. This makes it possible to train them with gradient descent on a data set with distant ground truth supervision (using labels of final output $\mathcal{O}$). In other terms, neural networks $\hat{p}_k$ receive supervision signal from the symbolic reasoning: the gradients are end-to-end backpropagated from the supervision at the output of the logic program directly to the parameters of the neural networks (without any intermediate labels for the individual sub-problems).

**Major Challenge.** The primary computational challenge lies in efficiently evaluating the sum over $S^{-1}(o)$ in equation (3). Indeed, $|S^{-1}(o)|$ can grow exponentially w.r.t. $m$, and inverting a symbolic function is in essence a NP-hard task. Therefore, addressing the complexity of computing $S^{-1}(o)$ is a key focus in improving PNL system scalability.

**Example 2 (MNIST-SUM Task).** We consider the neurosymbolic MNIST-SUM task Manhaeve et al. (2018), which will be used as a running example. The goal is to learn to predict the sum of handwritten digits, given only the label of the sum, but not the labels of the individual digits in the images, e.g. $\mathfrak{F} + \mathfrak{F} = 8$. This involves two subtasks: (1) perception of the digit in the image and (2) reasoning on the combination of the digits (with the sum as the symbolic function $S$). Building on the MNIST PL problem, see Example 1, we define the MNIST-SUM PL problem as $((\Omega, A, \mathbb{P}), \mathcal{I}, \mathcal{O}, F)$, where $\mathcal{I} = \mathcal{I}_{MNIST} \times \mathcal{I}_{MNIST}$ are pairs of images, $\mathcal{O} = [0, 18]$ are the output values of the sum, and $F(i_1, i_2) = F_{MNIST}(i_1) + F_{MNIST}(i_2)$ is the random variable related to the sum of the digits in the two images $i_1, i_2$.

For this task, we also define the PNL system $((V_1, V_2), (X_1, X_2), (\hat{p}_1, \hat{p}_2), S)$, where $V_1 = V_2 = [0, 9]$, $X_1(i_1, i_2) = F_{MNIST}(i_1)$ and $X_2(i_1, i_2) = F_{MNIST}(i_2)$ for all pairs of images $(i_1, i_2) \in \mathcal{I}_{MNIST} \times \mathcal{I}_{MNIST}$, $\hat{p}_1(i_1, i_2) = \hat{p}_{MNIST}(i_1)$ and $\hat{p}_2(i_1, i_2) = \hat{p}_{MNIST}(i_2)$ for all $(i_1, i_2) \in \mathcal{I}^2$, and $S(d_1, d_2) = d_1 + d_2$ for all digit values $d_1 \in V_1, d_2 \in V_2$. Thus, this PNL system for MNIST-SUM consists of two independent MNIST PL problems for classifying the digits in the images. This task can easily be extended to MNIST-N-SUM, where $N$ is the number of digits per summand. In this notation, the previous example is a MNIST-1-SUM. For $N=2$, two digits form the summands, e.g. $\mathfrak{F} + \mathfrak{F} = 63$.

**Example 3 (Inverting $S$ for MNIST-N-SUM).** The challenge of PNL is clearly to compute equation 3 efficiently.
The order of the PNL system for MNIST-N-SUM is $m = 2N$, which corresponds to the total number of digits to recognize (N for the first summand and N for the second). To compute $S^{-1}(o)$ for a given sum $o$, one could enumerate all possible combinations of digits ($d_1, \dots, d_{2N}$) and check if $S(d_1, \dots, d_{2N}) = o$. For example, given the MNIST-1-SUM task and the output sum value 4, all combinations of digits that sum to 4 are considered: $(0, 4), (3, 1), \dots, (4, 0)$. This naive approach would require at least $10^{2N}$ operations.

A common approach, popularized by the seminal work on Problog De Raedt, Kimmig, and Toivonen (2007), is to consider that $S$ is expressed in a probabilistic Prolog language (see Supplementary material for details). The probability of a query is then computed by reducing it to the probabilistic weighted model counting (PWMC) problem, a specific case of the weighted model counting problem whose formal definition is provided below.

**Probabilistic Weighted Model Counting.** Consider:

* $\mathbf{X}$ is a set of (independent) binary (random) variables.

* $G: \mathcal{F}(\mathbf{X}, \{0, 1\}) \to \{0, 1\}$ is a Boolean formula.

* $\sigma: \mathbf{X} \to [0, 1]$ is a probability distribution.

For any valuation $\psi \in \mathcal{F}(\mathbf{X}, \{0, 1\})$, we define the weight of $\psi$ w.r.t. $\sigma$ by

$$w_{\psi}^{\sigma} := \prod_{X \in \psi^{-1}(1)} \sigma(X) \cdot \prod_{X \in \psi^{-1}(0)} (1 - \sigma(X)).$$

A valuation $\psi \in \mathcal{F}(\mathbf{X}, \{0, 1\})$ such that $G(\psi) = 1$ is called a model of $G$ and $G^{-1}(1)$ denotes the set of models of $G$. The probabilistic weighted model count of $G$ under $\sigma$ is defined as

$$\text{PWMC}_{G}^{\sigma} := \sum_{\psi \in G^{-1}(1)} w_{\psi}^{\sigma}. \qquad (4)$$

The reduction to PWMC implemented in existing PNL systems such as DeepProbLog involves the explicit representation of the symbolic function $S$ of a PNL system as a Boolean logical formula $G$, known as the logical provenance, incurring major performance bottlenecks.

## A novel architecture for PNL systems

We now introduce the main contribution: the *Dynamic Probabilistic Neuro Symbolic Learning* (DPNL) framework. DPNL is a novel approach that enables the construction of a new class of PNL systems in which the classic logical provenance calculation step is replaced by the use of a representation that (i) does not need to be in CNF, (ii) can operate more directly with non-binary random variables, and (iii) does not even need to be fully materialized. This directly addresses the challenge of efficiently evaluating the sum over $S^{-1}(o)$ in equation (3), using a novel method inspired by DPLL.

We introduce this new approach in two steps for pedagogical reasons: first, we present ProbDPLL as an intermediate algorithm that serves as the basis for key observations. Then, building on these observations, we introduce the more general setting of DPNL.

**Algorithm 1: ProbDPLL(G, σ)**

**Input:** $G$ a Boolean formula represented in CNF, $\sigma$ a probability distribution of the variables in $\mathbf{X}$

**Output:** $\text{PWMC}_{G}^{\sigma}$

1: **if** $G$ has no clauses **then**

2: **return** 1

3: **else if** $G$ contains the empty clause **then**

4: **return** 0

5: **else**

6: Choose $X \in \mathbf{X}$ such that $X$ appears in $G$

7: $p_{G|X=1} \leftarrow \text{ProbDPLL}(G|_{X=1}, \sigma)$

8: $p_{G|X=0} \leftarrow \text{ProbDPLL}(G|_{X=0}, \sigma)$

9: **return** $\sigma(X) \cdot p_{G|X=1} + (1 - \sigma(X)) \cdot p_{G|X=0}$

10: **end if**

**ProbDPLL.** It is possible to solve the PWMC problem using a DPLL-like algorithm Sang, Bearne, and Kautz (2005); Oztok and Darwiche (2018); Dubray, Schaus, and Nijssen (2023), which we recall below. ProbDPLL (see Algorithm 1) computes $\text{PWMC}_{G}^{\sigma}$ when $G$ is a Boolean formula in CNF form. It builds on the observation that model counting is analogous to PWMC. It extends the \#DPLL model counter introduced in Bacchus, Dalmao, and Pitassi (2003), which is based on the seminal DPLL algorithm Davis, Logemann, and Loveland (1962), adapting it to compute $\text{PWMC}_{G}^{\sigma}$. It uses the notation $G|_{X=b}$ to denote the CNF formula obtained by replacing $X$ with $b$ in $G$ and simplifying the formula. It explores partial valuations of the formula $G$ and stops exploration when the partial valuation evaluates $G$ as true (when no clauses remain) or false (when the empty clause is reached). A vizualization of an example run of ProbDPLL as well as the proof of its correctness and termination are given in the supplementary material.

**Key observations.** In relation to the issue of logical provenance size, we highlight two key observations. First, ProbDPLL is designed for Boolean formulas but can be adapted to general (non-Boolean) functions, such as the symbolic function $S$ as previously defined, by working with independent random variables with finite domains (instead of independent binary random variables, as in PWMC). For instance, in the MNIST-SUM Example 2, the input values of $S$ are the digit values $[0, 9]$. Therefore, it is more convenient to use random variables with values in the range $[0, 9]$ than to encode them with independent binary random variables (which would result in an exponential blowup, as done in DeepProbLog and detailed in Supplementary material).

Second, ProbDPLL does not require $G$ to be in CNF. As long as $G$ is represented in a form that allows the algorithm to partially evaluate it with respect to a variable $X$ and determine whether this partial evaluation makes $G$ true or false, the algorithm will function correctly. Furthermore, $G$ does not even need to be explicitly known. ProbDPLL can operate as long as it has access to the answers to the question: “Does the partial valuation evaluate $G$ to true or false?”.

**DPNL.** We now introduce the core algorithm of DPNL, which generalizes ProbDPLL to support more general symbolic functions $S$ (not necessarily Boolean formulas like $G$)
and independent random variables with finite domains (instead of only independent binary random variables). Instead of working directly with a specific representation of S, as ProbDPLL does with G, DPNL follows a different approach. It calls an oracle function that extracts only the necessary information about S to guide the inference process in a way similar to ProbDPLL. The concept of an oracle here is an abstraction that captures precisely the properties required for DPNL to be correct. We now formally define the concepts of valuations and oracles used in DPNL.

**Valuation.** A valuation $v$ of the variables $(X_k)_{1\le k\le m}$ is an array of size $m$ such that for all $k \in [1, m]$, $v[k] \in V_k \cup \{\text{unknown}\}$. The following notations are used:

• $\mathcal{V}$ denotes the set of all valuations.

• A total valuation is a valuation where : $\forall k \in [1, m], v[k] \neq \text{unknown}$.

• A partial valuation is a valuation that is not total.

• $v'$ is a sub-valuation of $v$ if:

$$ \forall k \in [1, m], v[k] \neq \text{unknown} \implies v'[k] = v[k] $$

• $\text{sub}(v)$ is the set of sub-valuations of $v$.

• $\text{tot}(v)$ is the set of total sub-valuations of $v$.

• $w(i, v)$ is the event corresponding to $v$ with input $i$. Formally, it is the set of $w \in \Omega$ such that $[X_1(i)(w), ..., X_m(i)(w)] \in \text{tot}(v)$.

• $v_{v[k] \leftarrow x}$ is the valuation $v$ where the value of $v[k]$ is replaced by $x$.

**Oracle.** Given the symbolic function $S$ of a PNL system, an oracle $O_S$ for $S$ is a function that, given a valuation $v \in \mathcal{V}$ and an output $o \in \mathcal{O}$, answers the question “Is $S$ always equal to or always different from $o$ for all subvaluations of $v$?”. Intuitively, from a given output $o$, the oracle is in charge of determining whether it is still relevant to explore subvaluations or whether the exploration process can be stopped. Formally, a function $O_S: \mathcal{V} \times \mathcal{O} \to \{0, 1, \text{unknown}\}$ is a valid oracle for $S$ if and only if, for all $v \in \mathcal{V}$ and $o \in \mathcal{O}$:

• If the valuation $v$ is total,

$$ O_S(v, o) = \begin{cases} 1 & \text{if } S(v[1], ..., v[m]) = o, \\ 0 & \text{otherwise} \end{cases} $$

• If $O_S(v, o) = 1$,
  $\forall v' \in \text{tot}(v), S(v'[1], ..., v'[m]) = o$

• If $O_S(v, o) = 0$,
  $\forall v' \in \text{tot}(v), S(v'[1], ..., v'[m]) \neq o$

We say that the oracle is complete if the last two points are equivalences.

**Core DPNL Algorithm.** Algorithm 2 presents the core algorithm of the DPNL framework. We can compute $p(i)(o)$ by initially calling DPNL$(i, o, [\text{unknown}, ..., \text{unknown}], O_S)$.

In practice however, we want to compute $\hat{p}(i)(o)$ because we do not know $\mathbb{P}$. Therefore, we replace $\mathbb{P}(X_k(i) = y)$ at line 7 by its neural estimation $\hat{p}_k(i)(y)$.

**Algorithm 2: DPNL(i, o, v, O_S)**

**Input:** $i \in \mathcal{I}, o \in \mathcal{O}, v \in \mathcal{V}, O_S$ an oracle for $S$

**Output:** $\mathbb{P}(F(i) = o|w(i, v))$

1: **if** $O_S(v, o) = 1$ **then**

2: **return** 1

3: **else if** $O_S(v, o) = 0$ **then**

4: **return** 0

5: **else**

6: **Choose** $k \in [1, m]$ such that $v[k] = \text{unknown}$.

7: **return** $\sum_{y \in V_k} \mathbb{P}(X_k(i) = y) \cdot \text{DPNL}(i, o, v_{v[k] \leftarrow y}, O_S)$

8: **end if**

**Theorem 1.** DPNL Termination and Correctness. For every PL problem $((\Omega, \mathcal{A}, \mathbb{P}), \mathcal{I}, \mathcal{O}, F)$, PNL system $(V_k, X_k, \hat{p}_k, S)$ for the k-th PL problem with $1 \le k \le m$, valid oracle $O_S$ for $S$, $i \in \mathcal{I}$, $o \in \mathcal{O}$ and $v \in \mathcal{V}$, DPNL$(i, o, v, O_S)$ always terminates and returns $\mathbb{P}(F(i) = o|w(i, v))$.

A detailed proof of the termination and correctness of the algorithm is provided in the supplementary material.

**Example 4 (DPNL vs. PWMC on MNIST-1-sum).** For example, Figure 1 illustrates how DPNL determines the probability of an outcome (in this case, that the sum of the digits in two images equals two) in a fundamentally different way from PWMC. PWMC starts from a logic program, here written in ProbLog De Raedt, Kimmig, and Toivonen (2007), which includes a neural predicate for predicting the digits in the two images ($I_1$ and $I_2$). From this, all possible worlds must be computed. Then, the worlds that satisfy the query ($R = 2$) are compiled into a sequential decision diagram, which is then executed to compute the probability of the query. Importantly, this compilation step is repeated for each individual query. DPNL, in contrast, does not rely on any compilation step. Instead, it directly evaluates portions of the provenance formula through recursion and calls of an oracle function on partial valuations. In the example, the algorithm begins by selecting a variable (here $X_1$ for the digit in the first image). It then recursively evaluates the probabilities of different assignments by partially validating the formula with each possible value of $X_1$. Here, in some cases (if $X_1 > 2$), the oracle returns zero and pruning occurs: since the sum can no longer be 2, the specific value of $X_2$ (the digit in the second image) becomes irrelevant. Thus, all combinations involving such a value of $X_1$ are skipped. For the cases, where the result of $X_2$ is still relevant for the output ($X_1 = \{0, 1, 2\}$), the oracle returns unknown (u) and DPNL is called with values for $X_1$ and $X_2$. This pruning mechanism offers an advantage over weighted model counting, whose compilation step considers all possible worlds regardless of their relevance to the query.

**Constructing Oracles**

Oracles are a core component of DPNL, playing a critical role in guiding the inference process and significantly impacting performance. Fundamentally, for any decidable symbolic function $S$, if we have a procedure that computes
<figure><img src="image_2.png" /><figcaption>Figure 1: Illustration of DPNL vs. PWMC on the MNIST-1-sum task.</figcaption></figure>

S, then a valid oracle for S can be constructed. For example, an oracle which is valid for S is one which returns **unknown** for partial valuations, and checks if the result of S matches the output for a total valuation.

Oracles can exhibit various properties, and from a performance standpoint, two dimensions are particularly important: *algorithmic efficiency* and *pruning capability*. Algorithmic efficiency refers to the computational cost of evaluating the oracle on a given partial valuation. An efficient oracle answers quickly, ideally in sublinear or linear time relative to the input size. In practice, low-cost oracles are essential for exploring large search spaces without incurring prohibitive runtime overhead. *Pruning capability* measures the oracle's ability to return definitive answers (0 or 1) on partial valuations. The more often the oracle can avoid returning **unknown**, the more it can prune unnecessary branches of the search tree. High pruning capability enables DPNL to discard large portions of the search space early, dramatically reducing the number of valuations explored. In problems with large input domains or deep variable trees, this early pruning is essential to avoid combinatorial explosion.

We now present ways to obtain different oracles along those two dimensions, as illustrated on Fig. 2 (right). Specifically, we introduce the *naive oracle*, the *basic oracle*, the *logic oracle* and the *custom oracle*. We first give the intuitions and briefly present each of them.

**Naive Oracle.** A naive oracle tests all total sub valuations of $v$ to answer 0 or 1. However, with this naive oracle, the complexity of DPNL is the same as testing $S$ over all possible inputs to compute $S^{-1}(o)$. It is thus interesting to design oracles that return 0 or 1 for partial valuations in order to prune the search space of DPNL.

**Basic Oracle.** We assume that we dispose of an implementation of $S$. The basic oracle is automatically derived from this implementation. It executes $S$ on a partial valuation. If the execution of $S$ fails due to an attempt to access the value of a variable marked **unknown**, the oracle returns **unknown**. Otherwise, if the execution of $S$ successful

completes and produces an output, this output is then compared to the expected value so that the basic oracle returns 0 or 1. This approach is interesting for several reasons. First, it is *automatic*, requiring no manual analysis nor tool development beyond having access to $S$. Second, since the implementation of $S$ is often optimized, it may not read the full input before producing an output. This means the oracle is *algorithmically efficient* and can often return 0 or 1 on partial inputs, enabling some *pruning capability*. In other terms, the *basic oracle* inherits the efficiency of the implementation of $S$. Finally, since it is directly based on $S$, the validity of this oracle is immediate.

**Logic Oracles.** In our formalism, $S$ is a symbolic function which can be represented in various ways. In usual PNL contexts, $S$ is represented by a logic program such as in ProbLog De Raedt and Kimmig (2015). We detail in the supplementary material how logic oracles can be derived automatically from a broad class of logic programs. For any logic (Prolog, Boolean logic, Linear arithmetic...) with a solver (e.g. Prolog engine, SAT solvers, SMT solvers), we provide a general procedure based on calls to the solver that derives an oracle for every $S$ defined in this logic. This approach is interesting for several reasons. These oracles are complete, meaning they have high *pruning capabilities*. It allows the definition of complex $S$ in expressive logics, as long as the logic disposes of a solver. The only programming work required is to implement the interface between the logic, its solver and the DPNL implementation. The *algorithmic efficiency* relies on the underlying solver efficiency, which enables leveraging efficient state-of-the-art solvers. More details on obtaining logic oracles and the proof of their validity and completeness are given in the supplementary material.

**Custom Oracles and Oracles combination.** A major advantage of the DPNL approach is its way of exposing oracles in modular manner. DPNL can readily work with any of the aforementioned oracles, while also providing the flexibility to define custom oracles. Building on the intuition that an oracle can be seen as a generalization of $S$ to partial valuation
tions, hand-crafting an oracle is always possible.

Furthermore, one strength of the oracle abstraction is that combining oracles is possible and can be done in various ways. A simple strategy involves calling a list of oracles in sequence and returning the first non-unknown answer: by ordering the oracles from fastest (with potentially low pruning capability) to slowest (with potentially high pruning capability), one can achieve interesting balances between computational cost and pruning capability.

## Experimental Evaluation

We conduct experiments on symbolic and neurosymbolic reasoning tasks in order to bring elements of answers to the following research questions:

**Q1:** How does DPNL compare to other exact probabilistic reasoning systems?

**Q2:** In a neurosymbolic setting, how does the DPNL approach compare to SOTA PNL systems with exact and approximate reasoning in terms of efficiency and accuracy?

The full codebase, including a complete implementation of the DPNL approach, experiments and reproducible baselines, is publicly available at https://anonymous.4open.science/r/dpnll_19FE/ and included in the supplementary material. We first report on the experimental methodology and results for symbolic reasoning tasks, followed by neurosymbolic evaluations.

### Symbolic reasoning (Q1)

We compare DPNL to ProbLog a state-of-the-art system with exact probabilistic inference used in DeepProbLog. We use the two following probabilistic reasoning tasks.

We first evaluate DPNL on the popular MNIST-N-SUM task as presented in Example 2. By extending from an $N$ digit sum to an $N+1$ digit sum, the complexity of reasoning increases exponentially. Thus, the multi-digit MNIST-N-SUM task is well-suited for exploring the scalability of PNL systems. Each digit is represented as a probability distribution over $\{0, \dots, 9\}$, simulating uncertainty in perception. Here, we randomly generate the digit distributions. The symbolic function $S$ performs digit by digit integer addition and verifies the equality with the target. The following oracles are compared on this task. The *basic oracle* is built on the digit-by-digit addition implementation for $S$. The *logic oracle* is generated from the Boolean logic representation of the $N$-digit addition. The *combined oracle* uses the sequential combination of the basic and logic oracles.

We also evaluate DPNL on a graph reachability task. This involves estimating the probability that a path exists between a source and a target node in a probabilistic graph. We consider a graph with $N$ nodes, represented by an adjacency matrix containing $N^2$ potential edges. Each edge is assumed to be independently present with a certain probability. The symbolic function $S$ is a reachability predicate, implemented using a depth-first search (DFS) algorithm. Probabilities are randomly assigned to the edges, and the existence of a path from the source to the destination node is evaluated.

**Experimental results.** Figure 2 shows the time spent on symbolic reasoning for MNIST-N-SUM (left) and graph reachability (center). On MNIST-N-SUM, results show that DPNL scales better than ProbLog, solving task instances for $N \ge 7$ where ProbLog fails with a timeout. Results also show that the logic oracle, although slower on small instances, scales better than the basic oracle. Regarding graph reachability, for small instances (up to $N = 5$) ProbLog is faster than DPNL. However, for $N \ge 7$, ProbLog fails with timeout, whereas DPNL successfully completes with the logic and combined oracles. Results also illustrate that DPNL offers the possibility to scale even further given some manual programming effort with a custom oracle.

### Application to neurosymbolic AI (Q2)

We now evaluate DPNL on a neurosymbolic task MNIST-N-Sum where a neural classifier is trained to estimate probabilities for digits from image data. In other terms, this task extends the symbolic MNIST-N-SUM by integrating perception with neural networks. Digit distributions are derived from a neural network trained on MNIST images. This task allows us to evaluate the integration of neural and symbolic components with DPNL and to compare it with other PNL baselines. Specifically, we compare DPNL (with the basic oracle) with the PNL systems DeepProbLog and Scallop Huang et al. (2021) that use exact inference, and with A-Nesi van Krieken et al. (2023), DPLA\* Manhaeve, Marra, and De Raedt (2021) and Scallop (with the top-k semiring), which use approximate inference. A-Nesi is evaluated across its different variants (predict only, explain, prune). We use the MNIST dataset from Lecun et al. (1998). Each training sample consists of the images for the two summands and the supervision label on their ground truth sum. We evaluate the test accuracy and the runtime of the symbolic reasoning component. To ensure comparability, we maintain consistent experimental settings across all models, by reproducing baseline results on the same hardware and using the same parameters. Furthermore, we compare exact and approximate reasoning. We use a common set of hyperparameters. Each experiment is performed with multiple independent runs, and we report the average test accuracy and the average reasoning time per sample during training. Further, we enforce timeout thresholds, terminating any experiment with a run that exceeds the limit of six hours. Hyperparameter values, and information on hardware and baseline configurations are given in the supplementary material.

**Experimental Results.** We first compare DPNL with other PNL systems using exact inference (DeepProbLog and Scallop). Results are shown in Table 1. DeepProbLog achieves similar accuracy to DPNL for $N = 1$ and $N = 2$. In terms of reasoning time per sample, DPNL outperforms DeepProbLog, with the advantage becoming more noticeable as task complexity increases. Scallop with exact reasoning only succeeds to complete the task $N = 1$. For $N \ge 3$, DeepProbLog fails to finish, while DPNL achieves an accuracy of 0.82 for $N = 4$ with an average reasoning time per sample of 1.24s. Among all the exact PNL systems considered, DPNL is the only one that scales to $N = 4$.
<figure><img src="image_3.png" /><figcaption>Figure 2: Q1 Runtimes (in seconds) for MNIST-N-SUM (left) and graph reachability (center). Overview of oracles (right).</figcaption></figure>

<table><caption>Table 1: Q2 Results on the MNIST-N-SUM task. T/O=timeout. Highest test accuracy and shortest reasoning times in bold.</caption><thead><tr><th rowspan="2"></th><th colspan="3">N = 1</th><th colspan="3">N = 2</th><th colspan="3">N = 3</th><th colspan="3">N = 4</th></tr><tr><th>Acc</th><th>Std</th><th>Time</th><th>Acc</th><th>Std</th><th>Time</th><th>Acc</th><th>Std</th><th>Time</th><th>Acc</th><th>Std</th><th>Time</th></tr></thead><tbody><tr><td>DPNL</td><td>0.9550</td><td>0.0090</td><td>0.0011</td><td><strong>0.9116</strong></td><td>0.0106</td><td><strong>0.0099</strong></td><td><strong>0.8787</strong></td><td>0.0100</td><td>0.1079</td><td><strong>0.8262</strong></td><td>0.0211</td><td>1.2485</td></tr><tr><td>DeepProbLog</td><td><strong>0.9556</strong></td><td>0.0060</td><td>0.0238</td><td>0.9098</td><td>0.0122</td><td>0.4784</td><td>T/O</td><td>T/O</td><td>T/O</td><td>T/O</td><td>T/O</td><td>T/O</td></tr><tr><td>Scallop (exact)</td><td>0.9515</td><td>0.0037</td><td>0.0594</td><td>T/O</td><td>T/O</td><td>T/O</td><td>T/O</td><td>T/O</td><td>T/O</td><td>T/O</td><td>T/O</td><td>T/O</td></tr><tr><td>DPL A*</td><td>0.8120</td><td>0.1635</td><td>0.0213</td><td>0.8945</td><td>0.0146</td><td>0.0255</td><td>0.8365</td><td>0.0303</td><td>0.1237</td><td>T/O</td><td>T/O</td><td>T/O</td></tr><tr><td>Scallop (top-k)</td><td>0.9512</td><td>0.0076</td><td><strong>0.0009</strong></td><td>0.8257</td><td>0.2060</td><td>0.0244</td><td>0.7523</td><td>0.2612</td><td>0.9521</td><td>T/O</td><td>T/O</td><td>T/O</td></tr><tr><td>A-Nesi (predict)</td><td>0.9435</td><td>0.0071</td><td>0.0328</td><td>0.8849</td><td>0.0142</td><td>0.0265</td><td>0.7796</td><td>0.0074</td><td><strong>0.0170</strong></td><td>0.5929</td><td>0.0394</td><td><strong>0.0221</strong></td></tr><tr><td>A-Nesi (explain)</td><td>0.9510</td><td>0.0066</td><td>0.0348</td><td>0.8952</td><td>0.0071</td><td>0.0213</td><td>0.7707</td><td>0.0179</td><td>0.0219</td><td>0.6584</td><td>0.0239</td><td>0.0268</td></tr><tr><td>A-Nesi (prune)</td><td>0.9489</td><td>0.0070</td><td>0.0251</td><td>0.7866</td><td>0.2225</td><td>0.0195</td><td>0.7706</td><td>0.0214</td><td>0.0206</td><td>0.5905</td><td>0.0339</td><td>0.0245</td></tr></tbody></table>

When comparing exact and approximate reasoning systems, exact reasoning positively impacts accuracy, and this effect becomes more pronounced as the task difficulty increases. Exact inference enables distortion-free backpropagation and yields higher accuracy (e.g., at $N = 4$, DPNL achieves 0.82 vs. 0.66 for the best approximate method). For $N = 1$, the mean test accuracy of all systems considered is centered around the value 0.95 (except DPLA*). However, for $N = 2$ there is already a noticeable accuracy gap between approximate methods and exact methods such as DeepProbLog and DPNL. This gap becomes even larger for $N = 3$, where DPNL achieves a considerably higher accuracy of 0.87 compared to the approximate methods, which do not exceed 0.83. For $N = 4$, even the approximate methods such as DPLA* and Scallop (top-k) fail to complete their runs, while DPNL finishes successfully. The only baseline that finishes for $N = 4$ is A-Nesi. All variants of A-Nesi have noticeably lower reasoning times per sample compared to DPNL. However, DPNL has a clear advantage in terms of accuracy. The most accurate A-Nesi model is the explain variant, which achieves an accuracy of 0.66, while DPNL reaches an accuracy of 0.82.

## Related Works

There is a large body of work on neuro-symbolic methods aimed at bridging the gap between learning and reasoning. Within this field, PNL systems can be categorized into two groups: those based on exact reasoning and those based on approximate reasoning. Exact reasoning systems such as DeepProbLog Manhaeve et al. (2018), NeurASP Yang, Ishay, and Lee (2020), and other methods in this line of works Xu et al. (2018); Ahmed et al. (2022) provide exact in-

ference with probabilistic circuit methods Choi, Vergari, and Van den Broeck (2020). However, they suffer from the scalability issues previously mentioned due to explicit computation of logical provenance. Specifically, in DeepProbLog, the size of the Sequential Decision Diagram can increase exponentially (see supplementary material). In comparison, DPNL provides a radically different approach, as described previously, opening the door to SAT solving techniques.

To address the scalability issue, PNL systems with approximate reasoning have been developed. DeepStochLog Winters et al. (2022) employs the semantics of stochastic definite clause grammars that achieves better scaling properties thanks to a reduced search space. Scallop Huang et al. (2021) computes only the $k$ most probable clauses of the logical provenance and performs PWMC on the disjunction of these $k$ clauses. This approach thus limits both the size of the formula and the complexity of PWMC to a polynomial function of $k$. DPLA* Manhaeve, Marra, and De Raedt (2021) is based on DeepProbLog, but uses only a subset of all proofs. It employs A*-search and heuristics to efficiently search for the best proofs. However, while being polynomial in complexity, these approximations lack guarantees and may fail when the logical provenance's essential structure is not captured by a few clauses. Other systems relying on similar polynomial approximations have been developed. In particular, A-Nesi van Krieken et al. (2023) uses deep generative modeling to improve scalability. One of the important drawbacks of using approximations is that it undermines one of the primary strengths of PNL: confidence in the model's reliability. In comparison, DPNL makes it possible to obtain more accurate models since it pushes the boundaries of exact inference further.
Conclusion

We have presented the new DPNL approach for exact proba-
bilistic reasoning in neurosymbolic learning. Its core feature
lies in the use of oracles, which enables significant acceler-
ation of the inference process by eliminating computations
of irrelevant portions of logical provenance formulas. The
correctness and termination of DPNL are formally proved.
Experimental results suggest that DPNL provides an inter-
esting foundation for building modular and more scalable
PNL systems. As directions for future work, DPNL opens
avenues for improvements, such as leveraging SAT litera-
ture and approximation techniques. We believe these results
represent a promising step for the PNL community toward
the adoption of SAT-solver methods.

References

Ahmed, K.; Teso, S.; Chang, K.-W.; den Broeck, G. V.; and Vergari, A. 2022. Semantic Probabilistic Layers for Neuro-Symbolic Learning. arXiv:2206.00426.

Bacchus, F.; Dalmao, S.; and Pitassi, T. 2003. Algorithms and complexity results for# SAT and Bayesian inference. In *44th IEEE SFCS*, 340–351.

Biewald, L. 2020. Experiment Tracking with Weights and Biases. Software available from wandb.com.

Choi, Y.; Vergari, A.; and Van den Broeck, G. 2020. Probabilistic Circuits: A Unifying Framework for Tractable Probabilistic Models.

Davis, M.; Logemann, G.; and Loveland, D. 1962. A machine program for theorem-proving. *Communications of the ACM*, 394–397.

De Raedt, L.; Dumančić, S.; Manhaeve, R.; and Marra, G. 2020. From Statistical Relational to Neural-Symbolic Artificial Intelligence. In *IJCAI*, 4943–4950.

De Raedt, L.; and Kimmig, A. 2015. Probabilistic (logic) programming concepts. *Machine Learning*, 100(1): 5–47.

De Raedt, L.; Kimmig, A.; and Toivonen, H. 2007. ProbLog: A probabilistic Prolog and its application in link discovery. In *IJCAI*, 2468–2473.

Dubray, A.; Schaus, P.; and Nijssen, S. 2023. Probabilistic Inference by Projected Weighted Model Counting on Horn Clauses. In Yap, R. H. C., ed., *29th International Conference on Principles and Practice of Constraint Programming (CP 2023)*, volume 280 of *Leibniz International Proceedings in Informatics (LIPIcs)*, 15:1–15:17. Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. ISBN 978-3-95977-300-3.

Huang, J.; Li, Z.; Chen, B.; Samel, K.; Naik, M.; Song, L.; and Si, X. 2021. Scallop: From Probabilistic Deductive Databases to Scalable Differentiable Reasoning. In *NeurIPS*, 25134–25145.

Lecun, Y.; Bottou, L.; Bengio, Y.; and Haffner, P. 1998. Gradient-based learning applied to document recognition. *Proceedings of the IEEE*, 86(11): 2278–2324.

Li, Z.; Huang, J.; and Naik, M. 2023. Scallop: A Language for Neurosymbolic Programming. In *ACM on Programming Languages*, 1463–1487.

Manhaeve, R.; Dumančić, S.; Kimmig, A.; Demeester, T.; and De Raedt, L. 2018. DeepProbLog: Neural Probabilistic Logic Programming. In *NeurIPS*, 3753–3763.

Manhaeve, R.; Marra, G.; and De Raedt, L. 2021. Approximate Inference for Neural Probabilistic Logic Programming. In *Proceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning*, 475–486.

Oztok, U.; and Darwiche, A. 2018. An exhaustive DPLL algorithm for model counting. *J. Artif. Int. Res.*, 62(1): 1–32.

Paszke, A.; Gross, S.; Massa, F.; Lerer, A.; Bradbury, J.; Chanan, G.; Killeen, T.; Lin, Z.; Gimelshein, N.; Antiga, L.; Desmaison, A.; Köpf, A.; Yang, E.; DeVito, Z.; Rai-son, M.; Tejani, A.; Chilamkurthy, S.; Steiner, B.; Fang, L.; Bai, J.; and Chintala, S. 2019. PyTorch: An Imperative Style, High-Performance Deep Learning Library. arXiv:1912.01703.

Sang, T.; Bearne, P.; and Kautz, H. 2005. Performing Bayesian inference by weighted model counting. In *Proceedings of the 20th National Conference on Artificial Intelligence - Volume 1*, AAAI'05, 475–481. AAAI Press. ISBN 157735236x.

van Harmelen, F.; and ten Teije, A. 2019. A Boxology of Design Patterns for Hybrid Learning and Reasoning Systems.

van Krieken, E.; Thanapalasingam, T.; Tomczak, J.; van Harmelen, F.; and Ten Teije, A. 2023. A-NeSI: A Scalable Approximate Method for Probabilistic Neurosymbolic Inference. In *NeurIPS*, 24586–24609.

Vermeulen, A.; Manhaeve, R.; and Marra, G. 2023. An Experimental Overview of Neural-Symbolic Systems. In *ILP*, 124–138.

Winters, T.; Marra, G.; Manhaeve, R.; and De Raedt, L. 2022. DeepStochLog: Neural Stochastic Logic Programming. In *AAAI*, 10090–10100.

Xu, J.; Zhang, Z.; Friedman, T.; Liang, Y.; and Van den Broeck, G. 2018. A Semantic Loss Function for Deep Learning with Symbolic Knowledge. In Dy, J.; and Krause, A., eds., *Proceedings of the 35th International Conference on Machine Learning*, volume 80 of *Proceedings of Machine Learning Research*, 5502–5511. PMLR.

Yang, Z.; Ishay, A.; and Lee, J. 2020. NeurASP: Embracing Neural Networks into Answer Set Programming. In Bessiere, C., ed., *Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20*, 1755–1762. International Joint Conferences on Artificial Intelligence Organization. Main track.
# ProbDPLL

## Notation details

ProbDPLL is described in Algorithm 1. We first refine some notations. $\mathbf{X}$ is a set of (independent) binary (random) variables. A Boolean formula is a function from the set of valuations $\mathcal{F}(\mathbf{X}, \{0, 1\})$ into $\{0, 1\}$. For all $\mathbf{X} \in \mathbf{X}$, we also denote by $\mathbf{X}$ the Boolean formula such that for all valuation $v \in \mathcal{F}(\mathbf{X}, \{0, 1\})$, $\mathbf{X}(v) = 1$ iff $v(\mathbf{X}) = 1$. We use logical operators $\land$, $\lor$ and $\neg$ to build Boolean formulas. A Boolean formula $G$ is in CNF when

$$G = \bigwedge_{i=1}^{N} \bigvee_{j=1}^{M_i} L_{i,j}$$

where $N$ is the number of clauses in $G$, $M_i$ is the number of atoms in the $i$-th clause of $G$ and $L_{i,j}$ is a literal $X$ or $\neg X$ with $X \in \mathbf{X}$ for all $i, j$. For all $X \in \mathbf{X}$,

* $G_{|X=0}$ denotes $G$, where every clause containing $\neg X$ is set to true and where $X$ is eliminated from every clause in which it occurred.

* $G_{|X=1}$ denotes $G$, where every clause containing $X$ is set to true and where $\neg X$ is eliminated from every clause in which it occurred.

Consider the following relation $G \equiv (G_{|X=0} \land \neg X) \lor (G_{|X=1} \land X)$ (see Davis, Logemann, and Loveland (1962)). Given a probability distribution $\sigma : \mathbf{X} \to [0, 1]$ of the variables in $\mathbf{X}$, we note $\text{PWMC}_G^\sigma$ the probabilistic weighted model count of $G$ w.r.t. $\sigma$ as defined in the body of the paper.

## Vizualisation

Figure 3 illustrates the trace of ProbDPLL($G$, $\sigma$), see Algorithm 1, for the example formula $G = (A \lor B \lor \neg C) \land (A \lor B \lor C) \land (B \lor \neg A) \land (\neg B \lor C) \land (\neg B \lor \neg C)$ as a tree. Each node stands for a recursive call. Since $G$ is not satisfiable, $\text{PWMC}_G^\sigma$ returns 0.

<figure><img src="image_4.png" /><figcaption>Figure 3: Trace of ProbDPLL($G$, $\sigma$) where $G = (A \lor B \lor \neg C) \land (A \lor B \lor C) \land (B \lor \neg A) \land (\neg B \lor C) \land (\neg B \lor \neg C)$.</figcaption></figure>

## Termination and Correctness

In this section we prove the termination and correctness of ProbDPLL.

### Theorem 2. For every

* Boolean formula $G = \bigwedge_{i=1}^{N} \bigvee_{j=1}^{M_i} L_{i,j}$ in CNF over a finite set of (independent) binary (random) variables $\mathbf{X}$,

* probability distribution $\sigma : \mathbf{X} \to [0, 1]$,

$\text{ProbDPLL}(G, \sigma)$ terminates and returns $\text{PWMC}_G^\sigma$.

*Proof.* We proceed by induction for $n$ over the number of variables $|\mathbf{X}|$ in $G$. We define the induction hypothesis $H_n$:

For every Boolean formula $G = \bigwedge_{i=1}^{N} \bigvee_{j=1}^{M_i} L_{i,j}$ in CNF over a finite set of (independent) binary (random) variables $\mathbf{X}$ and a probability distribution $\sigma : \mathbf{X} \to [0, 1]$ such that $|\mathbf{X}| \le n$, $\text{ProbDPLL}(G, \sigma)$ terminates and returns $\text{PWMC}_G^\sigma$.

We can then prove $H_n$ for all $n \ge 0$ by induction:

**Base case $H_0$:** Let

* $G = \bigwedge_{i=1}^{N} \bigvee_{j=1}^{M_i} L_{i,j}$ a Boolean formula in CNF over $\mathbf{X}$ a finite set of (independent) binary (random) variables,

* $\sigma : \mathbf{X} \to [0, 1]$,

such that $|\mathbf{X}| \le 0$. Therefore, $G$ is constant because $\mathcal{F}(\emptyset, \{0, 1\})$ only contains one element $v_0$.

Moreover,

$$ \begin{aligned} \text{PWMC}_G^\sigma &:= \sum_{v \in G^{-1}(1)} \prod_{X \in v^{-1}(1)} \sigma(X) \prod_{X \in v^{-1}(0)} (1 - \sigma(X)) \\ &= \sum_{v \in G^{-1}(1)} 1 \\ &= G(v_0). \end{aligned} $$

There are two cases:

* $N = 0$: In this case ProbDPLL($G$, $\sigma$) terminates and returns 1 because $G$ has no clauses. Since $N = 0$, $G$ is constant and equal to the empty conjunction, so $G$ is equal to 1. It follows ProbDPLL($G$, $\sigma$) = $\text{PWMC}_G^\sigma = 1$.

* $N > 0$: In this case, ProbDPLL($G$, $\sigma$) terminates and returns 0 because $G$ contains the empty clause. Since $N > 0$, $G$ is constant and equal to a conjunction of empty clauses, so $G$ is constant and equal to 0. It follows ProbDPLL($G$, $\sigma$) = $\text{PWMC}_G^\sigma = 0$.

**Induction step:** $H_n \implies H_{n+1}$: Let $n \ge 0$ and suppose that $H_n$ holds. Consider

* a Boolean formula $G = \bigwedge_{i=1}^{N} \bigvee_{j=1}^{M_i} L_{i,j}$ in CNF over a finite set of (independent) binary (random) variables $\mathbf{X}$,

* a probability distribution $\sigma : \mathbf{X} \to [0, 1]$,
such that $|\mathbf{X}| \le n + 1$. If $|\mathbf{X}| < n + 1$, we can directly apply $H_n$ to conclude. So we consider that $|\mathbf{X}| = n + 1$. Let $X \in \mathbf{X}$ be the chosen variable in line 6 of Algorithm 1. We have:

* $G \equiv G_0 \lor G_1$ with $G_0 = (G_{|X=0} \land \neg X)$ and $G_1 = (G_{|X=1} \land X)$.

* Since $G_0$ contains $\neg X$, it follows for all $v \in G_0^{-1}(1)$ $v(X) = 0$.

* Since $G_1$ contains $X$, it follows for all $v \in G_1^{-1}(1)$, $v(X) = 1$.

Therefore, $G_0^{-1}(1)$ and $G_1^{-1}(1)$ are disjoint and form a partition of $G^{-1}(1)$. Since $\text{PWMC}_G^\sigma :=$

$$ \sum_{v \in G^{-1}(1)} \prod_{Y \in v^{-1}(1)} \sigma(Y) \cdot \prod_{Y \in v^{-1}(0)} (1 - \sigma(Y)) $$

by dividing the sum in two parts, we obtain $\text{PWMC}_G^\sigma = \text{PWMC}_{G_0}^\sigma + \text{PWMC}_{G_1}^\sigma$.

We now prove that

* $\text{PWMC}_{G_0}^\sigma = (1 - \sigma(X)) \cdot \text{PWMC}_{G_{|X=0}}^\sigma$ and

* $\text{PWMC}_{G_1}^\sigma = \sigma(X) \cdot \text{PWMC}_{G_{|X=1}}^\sigma$.

Since the two proofs are similar, we only show the proof for $G_1$. For every $v \in G_1^{-1}(1)$, the restriction of $v$ to $\mathbf{X} \setminus \{X\}$, noted as $v|_{\mathbf{X} \setminus \{X\}}$, is a model of $G_{|X=1}$, i.e. $v|_{\mathbf{X} \setminus X} \in G_{|X=1}^{-1}(1)$. And for every $v' \in G_{|X=1}^{-1}(1)$ the extension of $v'$ to $\mathbf{X}$ by setting $v'(X) = 1$ is a model of $G_1$. Indeed, $G_{|X=1}$ is a Boolean formula over $\mathbf{X} \setminus \{X\}$ and $G_1 = (G_{|X=1} \land X)$. From this follows:

$$ \begin{aligned} \text{PWMC}_{G_1}^{\sigma} &:= \sum_{v \in G_1^{-1}(1)} \prod_{Y \in v^{-1}(1)} \sigma(Y) \prod_{Y \in v^{-1}(0)} (1 - \sigma(Y)) \\ &= \sum_{v' \in G_{|X=1}^{-1}(1)} (\sigma(X) \cdot \prod_{Y \in v'^{-1}(1)} \sigma(Y) \cdot \prod_{Y \in v'^{-1}(0)} (1 - \sigma(Y))) \\ &= \sigma(X) \cdot \text{PWMC}_{G_{|X=1}}^{\sigma}. \end{aligned} $$

Thus $\text{PWMC}_{G_1}^\sigma = \sigma(X) \cdot \text{PWMC}_{G_{|X=1}}^\sigma$. Following the same considerations, we derive $\text{PWMC}_{G_0}^\sigma = (1 - \sigma(X)) \cdot \text{PWMC}_{G_{|X=0}}^\sigma$.

Since $G_{|X=1}$ and $G_{|X=0}$ are Boolean formula in CNF over $\mathbf{X} \setminus \{X\}$ and $|\mathbf{X}| = n + 1$, we can apply $H_n$:

* ProbDPLL($G_{|X=1}$, $\sigma$) terminates and returns $\text{PWMC}_{G_{|X=1}}^\sigma$.

* ProbDPLL($G_{|X=0}$, $\sigma$) terminates and returns $\text{PWMC}_{G_{|X=0}}^\sigma$.

In conclusion, we have:

$$ \begin{aligned} \text{PWMC}_G^\sigma &= \text{PWMC}_{G_0}^\sigma + \text{PWMC}_{G_1}^\sigma \\ &= (1 - \sigma(X)) \cdot \text{PWMC}_{G_{|X=0}}^\sigma + \\ & \qquad \sigma(X) \cdot \text{PWMC}_{G_{|X=1}}^\sigma \\ &= (1 - \sigma(X)) \cdot \text{ProbDPLL}(G_{|X=0}, \sigma) + \\ & \qquad \sigma(X) \cdot \text{ProbDPLL}(G_{|X=1}, \sigma) \end{aligned} $$

Thus ProbDPLL($G$, $\sigma$) terminates and returns $\text{PWMC}_G^\sigma$.

□

# DPNL

## Termination and Correctness

In this section we prove the termination and correctness of DPNL.

### Theorem 3. For every

* PL problem $((\Omega, A, \mathbb{P}), \mathcal{I}, \mathcal{O}, F)$,

* PNL system $((V_k)_{1 \le k \le m}, (X_k)_{1 \le k \le m}, (\hat{p}_k)_{1 \le k \le m}, S)$ for the PL problem,

* valid oracle $O_S$ for $S$,

* $i \in \mathcal{I}, o \in \mathcal{O}$ and $v \in \mathcal{V}$,

DPNL($i, o, v, O_S$) terminates and returns $\mathbb{P}(F(i) = o|w(i, v))$.

*Proof.* We proceed by induction over the number of non-assigned variables $n$ of the valuation $v$, i.e, the size of $v^{-1}(\text{unknown})$. We define $H_n$ as:

#### For every

* PL problem $((\Omega, A, \mathbb{P}), \mathcal{I}, \mathcal{O}, F)$,

* PNL system $((V_k)_{1 \le k \le m}, (X_k)_{1 \le k \le m}, (\hat{p}_k)_{1 \le k \le m}, S)$ for this problem,

* valid oracle $O_S: \mathcal{V} \times \mathcal{O} \to \{0, 1, \text{unknown}\}$ for $S$,

* $i \in \mathcal{I}, o \in \mathcal{O}$ and $v \in \mathcal{V}$,

such that $|v^{-1}(\text{unknown})| = n$, DPNL($i, o, v, O_S$) terminates and returns $\mathbb{P}(F(i) = o|w(i, v))$.

We can prove $H_n$ for all $n \ge 0$ by induction:

#### Base case $H_0$: Let

* $((\Omega, A, \mathbb{P}), \mathcal{I}, \mathcal{O}, F)$ be a PL problem,

* $((V_k)_{1 \le k \le m}, (X_k)_{1 \le k \le m}, (\hat{p}_k)_{1 \le k \le m}, S)$ be a PNL system for this problem,

* $O_S: \mathcal{V} \times \mathcal{O} \to \{0, 1, \text{unknown}\}$ be a valid oracle for $S$,

* $i \in \mathcal{I}, o \in \mathcal{O}$ and $v \in \mathcal{V}$,

such that $|v^{-1}(\text{unknown})| = 0$.

Since $\forall k \in [1, m], v[k] \ne \text{unknown}$, $v$ is total and thus $\text{tot}(v) = \{v\}$. By definition of $w(i, o)$, $\forall w \in w(i, v)$,

$$ [X_1(i)(w), \dots, X_k(i)(w)] \in \text{tot}(v). $$

Therefore, for all $w \in w(i, v)$ and $k \in [1, m]$,

$$ X_k(i)(w) = v[k]. $$
It follows, for all $w \in w(i, v)$,

$$F(i)(w) = S(X_1(i)(w), \dots, X_1(i)(w)) = S(v[1], \dots, v[m]).$$

There are two cases:

* Case $S(v[1], \dots, v[m]) = o$:

In this case, for all $w \in w(i, v)$, $F(i)(w) = o$ thus $\mathbb{P}(F(i) = o|w(i, v)) = 1$.

Moreover, $O_S$ is a valid oracle so that $O_S(v, o) = 1$ because $v$ is total and $S(v[1], \dots, v[m]) = o$. It follows that DPNL($i, o, v, O_S$) terminates and returns 1.

* Case $S(v[1], \dots, v[m]) \neq o$:

In this case, for all $w \in w(i, v)$, $F(i)(w) \neq o$ thus $\mathbb{P}(F(i) = o|w(i, v)) = 0$. Moreover, $O_S$ is a valid oracle so that $O_S(v, o) = 0$ because $v$ is total and $s(v[1], \dots, v[m]) \neq o$. It follows that DPNL($i, o, v, O_S$) terminates and returns 0.

Induction step $H_n \implies H_{n+1}$: Let $n \ge 0$ and assume that $H_n$ holds. Let

* $((\Omega, \mathcal{A}, \mathbb{P}), \mathcal{I}, \mathcal{O}, F)$ be a PL problem,

* $((V_k)_{1 \le k \le m}, (X_k)_{1 \le k \le m}, (\hat{p}_k)_{1 \le k \le m}, S)$ be a PNL system for this PL problem,

* $O_S: \mathcal{V} \times \mathcal{O} \to \{0, 1, \text{unknown}\}$ be a valid oracle for $S$,

* $i \in \mathcal{I}, o \in \mathcal{O}$ and $v \in \mathcal{V}$,

such that $|v^{-1}(\text{unknown})| = n + 1$.

There are 3 cases about $O_S(v, o)$:

* Case $O_S(v, o) = 0$:

In this case, DPNL($i, o, v, O_S$) terminates and returns 0.

We prove that $\mathbb{P}(F(i) = o|w(i, v)) = 0$.

Let $w \in w(i, o)$.

By definition

$$[X_1(i)(w), \dots, X_k(i)(w)] \in \text{tot}(v)$$

Moreover, since $O_S$ is a valid oracle and $O_S(v, o) = 0$ for all $v' \in \text{tot}(v)$,

$$S(v'[1], \dots, v'[m]) \neq o.$$

Therefore,

$$F(i)(w) = S(X_1(i)(w), \dots, X_m(i)(w)) \neq o.$$

It follows that $\mathbb{P}(F(i) = o|w(i, v)) = 0$.

* Case $O_S(v, o) = 1$:

In this case, DPNL($i, o, v, O_S$) terminates and returns 1.

We prove that $\mathbb{P}(F(i) = o|w(i, v)) = 1$.

Let $w \in w(i, o)$.

By definition

$$[X_1(i)(w), \dots, X_m(i)(w)] \in \text{tot}(v).$$

Moreover, since $O_S$ is a valid oracle and $O_S(v, o) = 0$ for all $v' \in \text{tot}(v)$,

$$S(v'[1], \dots, v'[m]) = o$$

Therefore,

$$F(i)(w) = S(X_1(i)(w), \dots, X_k(i)(w)) = o.$$

It follows that $\mathbb{P}(F(i) = o|w(i, v)) = 1$.

* Case $O_S(v, o) = \text{unknown}$:

In this case, DPNL($i, o, v, O_S$) chooses $k \in [1, m]$ such that $v[k] = \text{unknown}$.

Since $v$ is partial, such a $k$ exists. Indeed, if $v$ was a total valuation, $O_S(v, o)$ would return 0 or 1.

The events $(X_k(i) = y)_{y \in V_k}$ form a partition of $\Omega$. By the law of total probability, $\mathbb{P}(F(i) = o|w(i, v))$ is equal to

$$\Sigma_{y \in V_k} \mathbb{P}(X_k(i) = y|w(i, v)) \cdot \mathbb{P}(F(i) = o|w(i, v) \cap X_k(i) = y).$$

By definition, $w(i, v)$ only depends on the $X_l(i)$ such that $v[l] \neq \text{unknown}$, $v[k] = \text{unknown}$ and the $(X_l(i))_{1 \le l \le m}$ are independent by the definition of the PNL system. Therefore, $w(i, v)$ is independent of $X_k(i)$ for all $y \in V_k$:

$$\mathbb{P}(X_k(i) = y|w(i, v)) = \mathbb{P}(X_k(i) = y).$$

Moreover, by definition of $v_{v[k] \leftarrow y}$ and $w(i, v_{v[k] \leftarrow y})$

$$w(i, v_{v[k] \leftarrow y}) = w(i, v) \cap (X_k(i) = y)$$

because $v[k] = \text{unknown}$.

It holds

$$\mathbb{P}(F(i) = o|w(i, v) \cap X_k(i) = y) = \mathbb{P}(F(i) = o|w(i, v_{v[k] \leftarrow y})),$$

Finally, since $v[k] = \text{unknown}$ and $|v^{-1}(\text{unknown})| = n + 1$,

$$|v_{v[k] \leftarrow y}^{-1}(\text{unknown})| = n$$

Consequently, we can apply $H_n$. For all $y \in V_k$, DPNL($i, o, v_{v[k] \leftarrow y}, O_S$) terminates and returns $\mathbb{P}(F(i) = o|w(i, v_{v[k] \leftarrow y}))$.

We conclude that DPNL terminates and returns $\mathbb{P}(F(i) = o|w(i, v))$.

□

## Heuristics for choosing variables in DPNL

In DPNL, choosing $k$ with its associated variable $X_k$ (see line 6 of Algorithm 2), as for ProbDPLL, determines the number of recursive calls. The objective is to choose $k$ such that the execution tree of DPNL is as small as possible. The heuristic is designed based on the specific oracle. However, when the oracle is complete, the following heuristic is intuitively interesting:

* When the oracle is complete and answers unknown this means that there exists a total sub-valuation $v_0$ of $v$ such that $S(v[1], \dots, v[m]) \neq o$ and a total sub-valuation $v_1$ of $v$ such that $S(v[1], \dots, v[m]) = o$. It is often straightforward to modify an oracle to return these two sub-valuations instead of unknown by taking inspiration from the proof of completeness of the oracle, which often explicitly constructs these sub-valuations.
• The heuristic should choose $k$ so that $v[k] = \text{unknown}$ and $v_0[k] \neq \text{unknown}$ or $v_1[k] \neq \text{unknown}$.

## Logic PNL systems and Logic Oracles

We now present a systematic method for deriving logic oracles (as introduced in Section Logic Oracles in the body of the paper) from a broad class of logic programs. To this end, we first recall the connection between logic and probabilistic learning (PL) problems. Next, we define a class of neural probabilistic logic programs, building on ProbLog De Raedt, Kimmig, and Toivonen (2007) and DeepProbLog Manhaeve et al. (2018). Finally, we provide an algorithm to compute oracles from these programs, and prove that the obtained oracles are valid. The formal definitions follow.

**Logics.** A logic $\mathcal{L}$ consists of a set of functions $\mathcal{F}$ and predicates $\mathcal{P}$, logical operators such as $\wedge$ and $\exists$, their semantics, and an infinite set of variables $\mathcal{X}$. Combinations of functions and variables form terms, predicates applied to terms form atoms and logical combinations of atoms form logical formulas. The purpose of a logic is to model aspects of reality, which is formalized through an interpretation $I = (\Delta, [.]_\mathcal{F}, [.]_\mathcal{P})$, where:

• $\Delta$ is a set of real objects called the domain,

• for all $f \in \mathcal{F}, [f]_\mathcal{F} \in \mathcal{F}(\Delta^{arity}(f), \Delta)$ is the interpretation of $f$,

• for all $p \in \mathcal{P}, [p]_\mathcal{P} \in \mathcal{F}(\Delta^{arity}(p), \{0, 1\})$ is the interpretation of $p$.

This defines a semantics $[.]_I$ by recursively applying the semantics of logical operators and the interpretations of functions and predicates.

**Example 5 (Logic for MNIST).** In MNIST, we can consider $\mathcal{L}$ where $\mathcal{F} = \{i_1(0), i_2(0), \underline{0}(0), ..., \underline{9}(0)\}$ and $\mathcal{P} = \{is(2)\}$ where $s(k)$ denotes a symbol of arity $k$. We can define $I = (\text{Images} \cup [0, 9], [.]_\mathcal{F}, [.]_\mathcal{P})$ where $[i_1]_\mathcal{F}, [i_2]_\mathcal{F}$ are images, $[d]_\mathcal{F} = d$ and where, for example, $[is(i_1, \underline{7})]_I = [is]_\mathcal{P}([i_1]_\mathcal{F}, [\underline{7}]_\mathcal{F}) = 1$ iff $[i_1]_\mathcal{F}$ is an image of 7.

In the MNIST classification example, the task consists in estimating the probability of $is(i_1, \underline{d})$ for every digit $d$. Therefore, we can model this probabilistic aspect in the logic by considering the predicate interpretation as probabilistic. We can then define logic PL problems by following this idea.

**Logic PL problem.** Consider a logic $\mathcal{L}$, a domain $\Delta$ and a closed (i.e without variables) logical formula $\phi$ over $\mathcal{L}$. We define:

• $\Gamma_{\mathcal{L},\Delta} = (\Omega_{\mathcal{L},\Delta}, \mathcal{A}_{\mathcal{L},\Delta}, \mathbb{P}_{\mathcal{L},\Delta})$ is the probabilistic space of $\mathcal{L}$ in the real context $\Delta$. It models the probabilistic aspect of facts by taking $\Omega_{\mathcal{L},\Delta}$ as the set of all predicate interpretations $[.]_\mathcal{P}$ for $\Delta$ that are possible. $\mathbb{P}_{\mathcal{L},\Delta}$ is specific to the real context and models the likelihood of each $[.]_\mathcal{P}$.

• $\mathcal{I}_{\mathcal{L},\Delta}$ is a subset of all possible function interpretations $[.]_\mathcal{F}$ for $\Delta$. It models the possible observations about the reality and depends on the real context.

• $B_{\mathcal{L},\Delta}^{\phi}$ is the function that maps interpretations of $\mathcal{I}_{\mathcal{L},\Delta}$ to binary random variables in $\Gamma_{\mathcal{L},\Delta}$ corresponding to $\phi$:

$$B_{\mathcal{L},\Delta}^{\phi}([.]_\mathcal{F})([.]_\mathcal{P}) = [\phi]_{(\Delta, [.]_\mathcal{F}, [.]_\mathcal{P})}.$$

• $P_{\mathcal{L},\Delta}^{\phi} = (\Gamma_{\mathcal{L},\Delta}, \mathcal{I}_{\mathcal{L},\Delta}, \{0, 1\}, B_{\mathcal{L},\Delta}^{\phi})$ is the logic PL problem of $\phi$.

By taking inspiration from ProbLog and DeepProbLog, we now define a class of PNL systems for logic PL problems. Consider a logical formula $\phi$. The idea is to decompose $P_{\mathcal{L},\Delta}^{\phi}$ into $m$ smaller logic PL problems $P_{\mathcal{L},\Delta}^{\phi_1}, ..., P_{\mathcal{L},\Delta}^{\phi_m}$ where $\phi_1, ..., \phi_m$ represent simpler concepts. A symbolic function $S$, based on axioms about the context, combines $\phi_1, ..., \phi_m$ to determine the truth value of $\phi$.

**Logic PNL system.** Consider a logic $\mathcal{L}$ and a domain $\Delta$. Suppose the existence of an axiom set $A = \{\alpha_1, ..., \alpha_n\}$ such that all $\alpha_i$ are true in $\Gamma_{\mathcal{L},\Delta}$:

$$\bigcup_{[.]_\mathcal{F} \in \mathcal{I}_{\mathcal{L},\Delta}} (B_{\mathcal{L},\Delta}^{\alpha_i}([.]_\mathcal{F}) = 0) = \emptyset$$

We write $\{\Phi_1, ..., \Phi_l\} \vdash \Phi$ to denote that there exists a proof of $\Phi$ in $\mathcal{L}$ assuming $\Phi_1, ..., \Phi_l$. Now suppose there exist formulas $\phi_1, ..., \phi_m$ such that:

• $(P_{\mathcal{L},\Delta}^{\phi_k})_{1 \le k \le m}$ are independent logic PL problems,

• for all $\phi'_1, ..., \phi'_m$ such that $\phi'_k = \phi_k$ or $\phi'_k = \neg \phi_k$:

- $A \cup \{\phi'_1, ..., \phi'_m\} \vdash \phi$ or $A \cup \{\phi'_1, ..., \phi'_m\} \vdash \neg \phi$

- $A \cup \{\phi'_1, ..., \phi'_m\} \nvdash \bot$.

We say that the $\phi_1, ..., \phi_m$ decide $\phi$ and are coherent with respect to $A$.

Under these assumptions, we have sufficient elements to prove that the following constitutes a PNL system for $P_{\mathcal{L},\Delta}^{\phi}$: $((\{0, 1\})_{1 \le k \le m}, (B_{\mathcal{L},\Delta}^{\phi_k})_{1 \le k \le m}, (\hat{p}_k)_{1 \le k \le m}, S)$, where:

• for all $k \in [1, m], \hat{p}_k$ is a neural network which takes as input ground terms of $\phi_k$ interpreted as elements of $\Delta$ and returns an estimation of the probability distribution of $B_{\mathcal{L},\Delta}^{\phi_k}$,

• for all $x_1, ..., x_m \in \{0, 1\}, S(x_1, ..., x_m)$ is equal to

$$\begin{cases} 1 & \text{else if } A \cup \{\phi_k | x_k = 1\} \cup \{\neg \phi_k | x_k = 0\} \vdash \phi, \\ 0 & \text{otherwise.} \end{cases}$$

The proof is given in Supplementary material.

**Oracles for Logic PNL systems.** Consider a logic PNL system such that the theory $(\mathcal{L}, A)$ is decidable. Then, Algorithm 3 describes the pseudocode of a valid and complete oracle for the function $S$ based on a decision procedure of $(\mathcal{L}, A)$. The proof is given in Supplementary material.

## Logic PNL Systems Correctness

**Theorem 4.** Consider a logic $\mathcal{L}$, a domain $\Delta$ and a closed formula $\phi$. We assume the existence of an axiom set $A = \{\alpha_1, ..., \alpha_n\}$ and a set of closed formulas $\phi_1, ..., \phi_m$ that decide $\phi$ and are coherent with respect to $A$. Furthermore, $((\{0, 1\})_{1 \le k \le m}, (B_{\mathcal{L},\Delta}^{\phi_k})_{1 \le k \le m}, (\hat{p}_k)_{1 \le k \le m}, S)$ is a PNL system for $P_{\mathcal{L},\Delta}^{\phi}$.
**Algorithm 3: Logic Oracle**

**Input:** $v \in \mathcal{V}$, $o \in \mathcal{O}$

**Output:** A valid oracle output for $S$

1: **if** $A \cup \{\phi_k|v[k] = 1\} \cup \{\neg\phi_k|v[k] = 0\} \vdash \neg\phi$ **then**

2: $\mathit{res} \leftarrow 0$

3: **else if** $A \cup \{\phi_k|v[k] = 1\} \cup \{\neg\phi_k|v[k] = 0\} \vdash \phi$ **then**

4: $\mathit{res} \leftarrow 1$.

5: **else**

6: $\mathit{res} \leftarrow \mathit{unknown}$.

7: **end if**

8: **if** $\mathit{res} \neq \mathit{unknown} \land o = 0$ **then**

9: $\mathit{res} \leftarrow 1 - \mathit{res}$.

10: **end if**

11: **return** $\mathit{res}$.

*Proof.* Consider a logic $\mathcal{L}$, a domain $\Delta$ and a closed formula $\phi$. Let us consider the following hypothesis (denoted as H).

* The existence of $A = \{\alpha_1, ..., \alpha_n\}$ such that all $\alpha_i$ are true in $\Gamma_{\mathcal{L},\Delta}$, i.e, for all $i \in [1, n]$:

$$ (H_i) \quad \bigcup_{[\cdot]_\mathcal{F} \in \mathcal{I}_{\mathcal{L},\Delta}} (B_{\mathcal{L},\Delta}^{\alpha_i}([\cdot]_\mathcal{F}) = 0) = \emptyset $$

* The existence of a set of closed formulas $\phi_1, ..., \phi_m$ such that:

(H1) $(P_{\mathcal{L},\Delta}^{\phi_k})_{1 \le k \le m}$ are independent logic PL problems

(H2) For all $\phi'_1, ..., \phi'_m$ such that $\phi'_k = \phi_k$ or $\phi'_k = \neg\phi_k$, $A \cup \{\phi'_1, ..., \phi'_m\} \vdash \phi$ or $A \cup \{\phi'_1, ..., \phi'_m\} \vdash \neg\phi$.

(H3) For all $\phi'_1, ..., \phi'_m$ such that $\phi'_k = \phi_k$ or $\phi'_k = \neg\phi_k$, $A \cup \{\phi'_1, ..., \phi'_m\} \not\vdash \bot$.

By definition and by the assumptions:

* $\forall k \in [1, m]$, $P_{\mathcal{L},\Delta}^{\phi_k}$ is a PL problem as previously defined

* $(P_{\mathcal{L},\Delta}^{\phi_k})_{1 \le k \le m}$ are independent logic PL problems (by H1)

* $\forall k \in [1, m]$, $\hat{p}_k$ is a neural network which solves $P_{\mathcal{L},\Delta}^{\phi_k}$, by definition.

* $S: \{0, 1\}^m \to \{0, 1\}$.

It still remains to prove that $B_{\mathcal{L},\Delta}^{\phi}$ is equal to $S \circ (B_{\mathcal{L},\Delta}^{\phi_1}, ..., B_{\mathcal{L},\Delta}^{\phi_m})$.

Let $[\cdot]_\mathcal{F} \in \mathcal{I}_{\mathcal{L},\Delta}$ and $[\cdot]_\mathcal{P} \in \Omega_{\mathcal{L},\Delta}$. We note:

* For all $k \in [1, m]$, $x_k = B_{\mathcal{L},\Delta}^{\phi_k}([\cdot]_\mathcal{F})([\cdot]_\mathcal{P})$

* $T = A \cup \{\phi_k|x_k = 1\} \cup \{\neg\phi_k|x_k = 0\}$

In order to prove that $B_{\mathcal{L},\Delta}^{\phi}([\cdot]_\mathcal{F})([\cdot]_\mathcal{P}) = S(x_1, ..., x_m)$ we consider two cases:

* If $S(x_1, ..., x_m) = 1$:

By definition of $S$, $T \vdash \phi$.

For all interpretations $I$, if $I$ satisfies $T$, that is:

– For all $i \in [1, n]$, $[\alpha]_I = 1$

– For all $k \in [1, m]$, $[\phi_k]_I = x_k$

it follows by soundness that $[\phi]_I = 1$.

Moreover,

– For all $i \in [1, n]$, $[\alpha]_{(\Delta, [\cdot]_\mathcal{F}, [\cdot]_\mathcal{P})} = 1$ (by $H_i$)

– For all $k \in [1, m]$, $x_k = B_{\mathcal{L},\Delta}^{\phi_k}([\cdot]_\mathcal{F})([\cdot]_\mathcal{P}) = [\phi_k]_{(\Delta, [\cdot]_\mathcal{F}, [\cdot]_\mathcal{P})}$ by definition.

Therefore, $B_{\mathcal{L},\Delta}^{\phi}([\cdot]_\mathcal{F})([\cdot]_\mathcal{P}) = [\phi]_{(\Delta, [\cdot]_\mathcal{F}, [\cdot]_\mathcal{P})} = 1 = S(x_1, ..., x_m)$.

* If $S(x_1, ..., x_m) = 0$:

By definition of $S$, $T \vdash \phi$. Since $T \vdash \phi$, applying H2 results in $T \vdash \neg\phi$.

For all interpretation $I$, if $I$ satisfies $T$, that is:

– For all $i \in [1, n]$, $[\alpha]_I = 1$

– For all $k \in [1, m]$, $[\phi_k]_I = x_k$

it follows by soundness $[\neg\phi]_I = 1$. By applying the semantics of $\neg$ we can derive $[\phi]_I = 1 - [\neg\phi]_I = 0$. Moreover,

– For all $i \in [1, n]$, $[\alpha]_{(\Delta, [\cdot]_\mathcal{F}, [\cdot]_\mathcal{P})} = 1$ by $(H_i)$

– For all $k \in [1, m]$, $x_k = B_{\mathcal{L},\Delta}^{\phi_k}([\cdot]_\mathcal{F})([\cdot]_\mathcal{P}) = [\phi_k]_{(\Delta, [\cdot]_\mathcal{F}, [\cdot]_\mathcal{P})}$ by definition.

It results that $B_{\mathcal{L},\Delta}^{\phi}([\cdot]_\mathcal{F})([\cdot]_\mathcal{P}) = [\phi]_{(\Delta, [\cdot]_\mathcal{F}, [\cdot]_\mathcal{P})} = 0 = S(x_1, ..., x_m)$.

□

**Logic Oracle Validity and Completeness**

We now prove validity and completeness of the logic oracle in Algorithm 3.

**Theorem 5.** The logic oracle is a valid oracle for $S$.

*Proof.* We denote $O(v, o)$ the as the result of the logic oracle on $v \in \mathcal{V}$ and $o \in \{0, 1\}$ (in Algorithm 3). We check that Algorithm 3 satisfies every property of a valid oracle for $S$:

* Since $\mathit{res}$ in the algorithm takes values in $\{1, 0, \mathit{unknown}\}$, the algorithm returns values in $\{0, 1, \mathit{unknown}\}$.

* Let $v \in \mathcal{V}$ and $o \in \{0, 1\}$ and assume that $O(v, o) = 0$. Given that $O$ satisfies $O(v, 0) = 1 - O(v, 1)$ and that $\mathit{res}$ in the algorithm is inverted for $o = 0$, we can suppose without loss of generality that $o = 1$. We now want to prove that for all $v' \in \mathit{tot}(v)$, $S(v'[1], ..., v'[m]) = 0$. Let $v' \in \mathit{tot}(v)$.

We note $T = A \cup \{\phi_k|v[k] = 1\} \cup \{\neg\phi_k|v[k] = 0\}$ and $T' = A \cup \{\phi_k|v'[k] = 1\} \cup \{\neg\phi_k|v'[k] = 0\}$.

Since $O(v, o) = 0$ and we assumed that $o = 1$, this implies that $\mathit{res}$ has been set to 0 which results in $T \vdash \neg\phi$. Moreover, $v'$ is a sub-valuation of $v$ so that $T \subset T'$ hence $T' \vdash \neg\phi$ because the proof tree of $\neg\phi$ in $T$ is also a valid proof tree in $T'$.

In addition, by H3, $T' \vdash \bot$ so that $T' \vdash \phi$ since $T' \vdash \neg\phi$. By definition of $S$ it follows $S(v'[1], ..., v'[m]) = 0$.

* Let $v \in \mathcal{V}$ and $o \in \{0, 1\}$ and assume that $O(v, o) = 1$. Given that $O$ satisfies $O(v, 0) = 1 - O(v, 1)$ and that $\mathit{res}$ is inverted for $o = 0$, we can suppose without loss of generality that $o = 1$. We thus want to prove that for all $v' \in \mathit{tot}(v)$, $S(v'[1], ..., v'[m]) = 1$. Let $v' \in \mathit{tot}(v)$.

We note $T = A \cup \{\phi_k|v[k] = 1\} \cup \{\neg\phi_k|v[k] = 0\}$ and $T' = A \cup \{\phi_k|v'[k] = 1\} \cup \{\neg\phi_k|v'[k] = 0\}$.
Since $O(v,o) = 1$ and we assumed that $o = 1$, this implies that $res$ has been set to 1 which results in $T \vdash \phi$. Moreover, $v'$ is a sub-valuation of $v$ so that $T \subset T'$ hence $T' \vdash \phi$ because the proof tree of $\phi$ in $T$ is also a valid proof tree in $T'$.

By definition of $S$ it follows $S(v'[1], ..., v'[m]) = 1$.

<figure><img src="image_5.png" /></figure>

**Theorem 6.** *The logic oracle describes a complete oracle for $S$.*

*Proof.* We denote $O(v,o)$ as the result of Algorithm 3 on $v \in \mathcal{V}$ and $o \in \{0, 1\}$. Since we have already proven the validity, it remains to prove that for all $v \in \mathcal{V}$ and $o \in \{0, 1\}$, if $O(v,o) = \text{unknown}$ there exists $v_0, v_1 \in \text{tot}(v)$ such that $S(v_0[1], ..., v_0[m]) = 0$ and $S(v_1[1], ..., v_1[m]) = 1$.

Let $v \in \mathcal{V}$ and $o \in \{0, 1\}$ such that $O(v,o) = \text{unknown}$. We note $T = A \cup \{\phi_k|v[k] = 1\} \cup \{\neg \phi_k|v[k] = 0\}$.

Since $O(v,o) = \text{unknown}$, it means that $T \vdash \phi$ and $T \vdash \neg \phi$. We can thus apply the completeness theorem and consider interpretations $I_0$ and $I_1$ that satisfy $T$ such that $[\phi]_{I_0} = 0$ and $[\phi]_{I_1} = 1$.

For $i \in \{0, 1\}$, we note $v_i = [[\phi_1]_{I_i}, ..., [\phi_m]_{I_i}]$ and $T_i = A \cup \{\phi_k|v_i[k] = 1\} \cup \{\neg \phi_k|v_i[k] = 0\}$. Since $I_i$ satisfies $T$, we conclude that $v_i \in \text{tot}(v)$. We now show that $S(v_i[1], ..., v_i[m]) = i$:

* $i = 0$:

By contradiction, we assume that $S(v_0[1], ..., v_0[m]) = 1$, which implies $T_0 \vdash \phi$. By definition of $I_0$, $v_0$ and $T_0$, $I_0$ satisfies $T_0$. Given completeness, it results that $[\phi]_{I_0} = 1$, which contradicts $[\phi]_{I_0} = 0$.

It follows that $S(v_0[1], ..., v_0[m]) = 0$.

* $i = 1$:

By contradiction, we assume that $S(v_1[1], ..., v_1[m]) = 0$. It means that $T_1 \vdash \phi$ hence $T_1 \vdash \neg \phi$ because we assume that $\phi_1, ..., \phi_m$ decide $\phi$ w.r.t. $A$ when defining the PNL system.

By definition of $I_1$, $v_1$ and $T_1$, $I_1$ satisfies $T_1$. Given completeness, it results that $[\phi]_{I_1} = 1 - [\neg \phi]_{I_1} = 0$, which contradicts $[\phi]_{I_1} = 1$.

It follows that $S(v_1[1], ..., v_1[m]) = 1$.

<figure><img src="image_6.png" /></figure>

## Application to DeepProbLog

This section discusses how a logic oracle can be used in the context of programs in DeepProbLog.

## Formal definitions

We start by giving formal the formal definitions of a Problog program De Raedt, Kimmig, and Toivonen (2007) and a DeepProblog program Manhaeve et al. (2018).

**ProbLog program.** A ProbLog program is defined as a set $T = \{p_1 : c_1, ..., p_n : c_n\}$ of rules $c_k$ without negation annotated by their probability $p_k$. It defines a probability distribution over logic programs $L \subseteq L_T = \{c_1, ..., c_n\}$ as follows:

$$P_T(L) := \prod_{c_k \in L} p_k \cdot \prod_{c_k \notin L} (1 - p_k)$$

For every query $q$ the probability of success of $q$ is defined as:

$$P_T(q) := \sum_{L \subseteq L_T, L \models q} P_T(L)$$

**DeepProbLog program.** For the sake of clarity, we use different notations from Manhaeve et al. (2018) to define a DeepProbLog program. Formally, a DeepProbLog program over logic $\mathcal{L}$ (as previously defined) is a set $D = T \cup T_N$ where:

* $T = \{c_1, ..., c_n\}$ is a Prolog program over $\mathcal{L}$ without negation,

* $T_N = \{\text{NN}_1 : r_1, ..., \text{NN}_n : r_m\}$ is the set of neural predicates in the program

* $r_k$ is a Prolog rule without negation with $l_k$ ground terms $t_k^1, ..., t_k^{l_k}$

* $\text{NN}_k = (m_k, t_k^1, ..., t_k^{l_k})$ where $m_k$ is a neural network that maps the interpretations of the $t_k^1, ..., t_k^{l_k}$ as element of $\Delta$ to the probability of $r_k$.

For all $[..]_\mathcal{F}$, we define the interpretation of $D$ as the Deep-ProbLog program:

$$[D]_{\mathcal{F}} = \{1 : c_k|1 \le k \le n\} \cup \{m_k([t_k^1]_{\mathcal{F}}, ..., [t_k^{m_k}]_{\mathcal{F}}) : \\ r_k|1 \le k \le m\},$$

where $[t_k^l]_{\mathcal{F}}$ is the interpretation of $t_k^l$ in $\Delta$ by recursively applying $[..]_\mathcal{F}$ to the functions of $t_k^l$.

**DeepProbLog PNL system.** Consider $P_{\mathcal{L},\Delta,q}$ and $D = T \cup T_N$ as defined above. If

* $q$ corresponds to a Prolog query,

* $(P_{\mathcal{L},\Delta}^{r_k})_{1 \le k \le m}$ are independent PL problems,

* $c_i \in T$ is true, i.e., $\bigcup_{[..]_\mathcal{F} \in \mathcal{I}_{\mathcal{L},\Delta}} (B_{\mathcal{L},\Delta}^{c_i}([..]_\mathcal{F}) = 0) = \emptyset$.

$D$ corresponds to a PNL system for $P_{\mathcal{L},\Delta}^q$. Indeed, $((\{0, 1\})_{1 \le k \le m}, (B_{\mathcal{L},\Delta}^{r_k})_{1 \le k \le m}, (\hat{p}_k)_{1 \le k \le m}, S)$ is a PNL system where

* $\hat{p}_k([..]_\mathcal{F})(1) = 1 - \hat{p}_k([..]_\mathcal{F})(0) = m_k([t_k^1]_\mathcal{F}, ..., [t_k^l]_\mathcal{F})$,

* $S(x_1, ..., x_m) = \begin{cases} 1 & \text{if } T \cup \{r_k|x_k = 1\} \models q, \\ 0 & \text{else} \end{cases}$.

**Inference in DeepProbLog.** Given $[..]_P \in \mathcal{I}_{\mathcal{L},\Delta}$, Deep-ProbLog computes $S$ in the form of a logical formula of the $x_1, ..., x_m$ in DNF. Then, it computes $\text{PWMC}_S^\sigma$ with the probability $\sigma(x_k) = m_k([t_k^1]_P, ..., [t_k^{l_k}]_P)$ of $r_k$. By definition of $P_{[D]}_\mathcal{F}$ and $S$, $P_{[D]}_\mathcal{F}(q)$ is equal to $\text{PWMC}_S^\sigma$.
**Algorithm 4: DeepProbLog Oracle**

**Input:** $v \in \mathcal{V}$, $o \in \mathcal{O}$

**Output:** A valid oracle output for the function $S$

1: **if** $R \cup \{r_k|v[k] = 1\} \vdash q$ **then**

2: $res \leftarrow 1$

3: **else if** $R \cup \{r_k|v[k] = 1 \lor v[k] = \text{unknown}\} \vdash q$ **then**

4: $res \leftarrow \text{unknown}$.

5: **else**

6: $res \leftarrow 0$.

7: **end if**

8: **if** $res \neq \text{unknown} \land o = 0$ **then**

9: $res \leftarrow 1 - res$.

10: **end if**

11: **return** $res$.

## Oracle for DeepProbLog

Building on a Prolog solver, Algorithm 4 provides an oracle for the logical provenance. Its validity is based on the fact that the program has no negation. It follows that if we cannot prove $q$ by adding all rules $r_k$ such that $v[k] = \text{unknown}$, then we can directly return 0. If, in addition, the program has no functor, the Prolog solver is polynomial-time. It results that its oracle is also polynomial-time.

**Example 6 (Graph Reachability).** Graph reachability queries are the key ingredients in numerous tasks such as semi-supervised classification in citation networks Winters et al. (2022). A probabilistic directed graph consists of the following elements, denoted as follows

* $E = \{e_k|1 \le k \le N\}$ describes the set of nodes

* $G(e_i, e_j)$ denotes an edge from node $e_i$ to node $e_j$, $(e_i, e_j \in E)$.

* $NN_G(e_i, e_j)$ is the probability that the edge $G(e_i, e_j)$ is present in the graph.

* Reachability is defined as $R(e_i)$. A node $e_i$ is reachable from node $e_1$ if $R(e_i)$ it true.

For this problem, we are interested in the probability that a node $e_N$ is reachable from a starting node $e_1$ and formulate this as query $q = R(e_N)$. The full logical provenance formula for a query $q$ is denoted as $LP_q$. Consider the following DeepProbLog program $D = T_N \cup T$ for graph reachability:

* $T_N = \{NN_{i,j}: G(e_i, e_j) | 1 \le i, j \le N\}$.

* $T = \{R(e_1), R(Y) : -R(X), G(X, Y)\}$.

This program contains neither negation nor functions. Therefore, the DeepProbLog oracle in algorithm 4 is polynomial-time. However,

* for each path $e_1 \to e_{i_1} \to \dots \to e_{i_k} \to e_N$ (with intermediate nodes $e_{i_1}, \dots, e_{i_k}$) the corresponding clause $G(e_1, e_{i_1}) \land \dots \land G(e_{i_k}, e_N)$ implies $LP_q$,

* and $LP_q$ implies the existence of such a path

Therefore, $LP_q$ is equivalent to the disjunction of clauses that correspond to the path from $e_1$ to $e_N$. Moreover,

* for each path we can potentially remove loops and obtain a path whose corresponding clause is included in the original clause (before removing loops),

* and if we remove a literal from a clause corresponding to a loop-free path it does not correspond to a path, hence it does not imply $LP_q$.

Therefore, $LP_q$ is exactly the disjunction of clauses that correspond to the loop-free path. Choosing a loop-free path from $e_1$ to $e_N$ in a complete graph is equivalent to:

* Choosing the number of intermediate node $i \in [0, |E| - 2]$

* Choosing $i$ nodes from the set of remaining $|E| - 2$ nodes in the graph

* Choosing a permutation of these $i$ nodes that correspond to the order in which they are visited

Therefore, $LP_q$ contains exactly $\sum_{i=0}^{|E|-2} \binom{|E|-2}{i} \cdot i!$ clauses. In conclusion, since $|E| - 2 \sim_{|E| \to \infty} \sqrt{|T|}$, $|LP_q| \sim_{|E| \to \infty} (\sqrt{|T|})!$

## Modeling Probabilistic Choices

This section describes how probabilistic choices are treated in ProbLog De Raedt, Kimmig, and Toivonen (2007) (and in DeepProbLog Manhaeve et al. (2018)), as detailed in De Raedt and Kimmig (2015). Probabilistic choices are categorical random variables with mutually exclusive outcomes. The representation with probabilistic facts is not sufficient as these are considered to be independent. In contrast, the outcomes of probabilistic choices are dependent. ProbLog uses annotated disjunctions (ADs) to model probabilistic choices. Based on ADs, DeepProbLog uses neural annotated disjunctions (nADs), which can be represented by the activated classification function of a neural network.

Probabilistic choices for ADs are transformed to (1) a set of probabilistic facts and (2) deterministic clauses:

* $\tilde{p}_i :: sw_{id}(h_i, v_1, \dots, v_f)$ is the set of probabilistic facts.

* The deterministic clauses are

$h_i: -b_1, \dots, b_m, \text{not } (sw_{id}(h_1, v_1, \dots, v_f)), \dots, \text{not } (sw_{id}(h_{i-1}, v_1, \dots, v_f)), sw_{id}(h_i, v_1, \dots, v_f)$,

where $v_1, \dots, v_f$ are the free variables in the body of the AD and $sw_{id}$ is a switch variable with an identifier for the respective AD.

The probability $\tilde{p}_i$ is defined as

$$ \tilde{p}_i := \begin{cases} p_i \cdot \left(1 - \sum_{j=1}^{i-1} p_j\right)^{-1} & \text{if } p_i > 0 \\ 0 & \text{if } p_i = 0 \end{cases} $$

To recover the original probabilities $p_i$ from the transformed values $\tilde{p}_i$, one can initialize $p_1 := \tilde{p}_1$ and iteratively compute $p_i$ for $i = \{2, 3, \dots, n\}$ using the formula

$$ p_i := \tilde{p}_i \cdot \left(1 - \sum_{j=1}^{i-1} p_j\right). $$

**Example 7 (ADs for MNIST Classification).** Consider the example of MNIST classification, where the variables indicating that an image $I$ contains a certain digit in $[0, 9]$ are modeled as probabilistic facts in ProbLog, e.g.

$p_0 :: \text{digit}(I, 0), p_1 :: \text{digit}(I, 1), \dots, p_9 :: \text{digit}(I, 9)$.
This implies that the probability of all digits being simultaneously valid for an image equals $\prod_{i=0}^{9} p_i$. In contrast, since the variables are mutually exclusive (and therefore dependent), the probability of this event should be zero. To this end, the digits can be modeled as probabilistic choices with ADs. For the MNIST Classification task, the AD can be represented as follows:

digit(I, 0) : -sw(digit(I, 0))
digit(I, 1) : -not(sw(digit(I, 0))), sw(digit(I, 1))
digit(I, 2) : -not(sw(digit(I, 0))), ..., sw(digit(I, 2))
...
digit(I, 9) : -not(sw(digit(I, 0))), ..., sw(digit(I, 9))

# Experimental Details

## Hardware

All experiments are executed on an Apple Macbook M1 Max with 64GB RAM.

## Implementation Details

The DPNL framework is implemented in a modular and extensible Python codebase centered around symbolic reasoning with probabilistic inputs. It introduces a unified abstraction for defining symbolic functions, managing structured probabilistic inputs, and executing exact inference using oracle-guided recursive evaluation. The implementation relies on Pytorch Paszke et al. (2019) and uses Weights and Biases Biewald (2020) as experiment tracking tool.

### Core Abstractions.
At the heart of the system is the Symbolic class, an abstract interface for symbolic functions S, and the Input class, which represents structured inputs composed of random variables (RndVar). Each RndVar has a discrete domain and a probability distribution, and may be left undefined (unknown) until instantiated during inference.

### Oracle Mechanism.
DPNL oracles implement the Oracle interface, which answers whether $S(I) = o$ is always, never, or possibly true for a given input I and output o. Multiple oracle variants are supported:

* **Enumeration Oracle:** A naive baseline that returns unknown if any variable in I is undefined. Useful to establish a ground truth result.

* **Basic Oracle:** Executes $S(I)$ and traps access to undefined variables to detect when S need to access an unknown variable.

* **Logic Oracle:** Implementation of the procedure to obtain a logic oracle given an interface with a logic, its solver and the function S.

* **Combination Oracle:** Sequentially tries multiple oracles, falling back as needed to obtain stronger pruning or efficiency.

### Recursive Inference.
The PNLProblem class wraps a symbolic function and input. It computes the probability that $S(I) = o$ via recursive branching over undefined variables, guided by the oracle.

### SAT Logic Integration.
We implemented an interface for the Logic Oracle with the Boolean logic and SAT solvers for the experiments. The SATLogic class encodes formulas using literals, clauses, and conjunctions, and interfaces with a SAT solver (e.g., MiniSAT). Symbolic functions defined in SAT are specified through the SATLogicSymbolic interface, which supports variable declarations, clause generation, and relational constraints over domains to easily define S. This enables symbolic functions to be expressed and reasoned about at the propositional level, improving pruning and solver performance.

## Hyperparameters.

The hyperparameters used in the experiments are summarized in Table 2. We keep the hyperparameters constant across the experiments with different numbers of digits. Further, we conduct 10 independent runs with different random seeds for DPNL.

<table><caption>Table 2: Hyperparameters used for DPNL and baselines.</caption><thead><tr><td>Parameter</td><td>value</td></tr></thead><tbody><tr><td># epochs</td><td>1</td></tr><tr><td>Batch size</td><td>2</td></tr><tr><td>Learning rate</td><td>1e-03</td></tr><tr><td>Classifier</td><td>MNIST Classifier</td></tr><tr><td>Loss</td><td>BCE Loss</td></tr></tbody></table>

### MNIST Classifier.
We follow Manhaeve et al. (2018) and use the following neural network architecture as digit classifier. It consists of two convolutional layers with kernel size 5 and output dimension 6 and 16 (nn.Conv2d(1, 6, 5) and nn.Conv2d(6, 16, 5),) followed by Max pooling and Relu activation (nn.MaxPool2d(2, 2)). A classifier with three linear layers is stacked which have the dimensions 120 and 84 respectively. The output dimension corresponds to the number of digits and equals 10.

## Baselines

To obtain the results with the baselines, we used the source code from the following publicly available code repositories:

* DeepProbLog & DPLA*: https://github.com/ML-KULeuven/deepproblog

* A-Nesi: https://github.com/HEmile/a-nesi

* Scallop: https://github.com/scallop-lang/scallop

The code with which we ran the baselines and measured the runtimes is available.<fnref n="1" />

### A-Nesi.
We conduct five independent runs with different random seeds for each experiment. Table 3 shows the hyperparameters used for configurations used for the different variants of A-Nesi van Krieken et al. (2023).

<footnote n="1">¹https://anonymous.4open.science/r/dpnll_19FE/</footnote>
<table><caption>Table 3: Table of hyperparameters of A-Nesi for the variants explain, predict only, and prune.</caption><thead><tr><td>Key</td><td>Explain</td><td>Predict Only</td><td>Prune</td></tr></thead><tbody><tr><td>amtSamples</td><td>600</td><td>600</td><td>600</td></tr><tr><td>K-beliefs</td><td>2500</td><td>2500</td><td>2500</td></tr><tr><td>nrm.Lr</td><td>0.001</td><td>0.001</td><td>0.001</td></tr><tr><td>perception.Lr</td><td>0.001</td><td>0.001</td><td>0.001</td></tr><tr><td>dirichlet.Lr</td><td>0.01</td><td>0.01</td><td>0.01</td></tr><tr><td>dirichlet.Iters</td><td>50</td><td>50</td><td>50</td></tr><tr><td>dirichlet.init</td><td>0.1</td><td>0.1</td><td>0.1</td></tr><tr><td>dirichlet.L2</td><td>900000</td><td>900000</td><td>900000</td></tr><tr><td>nrm(loss</td><td>mse</td><td>mse</td><td>mse</td></tr><tr><td>hidden.size</td><td>800</td><td>800</td><td>800</td></tr><tr><td>layers</td><td>3</td><td>3</td><td>3</td></tr><tr><td>prune</td><td>False</td><td>False</td><td>True</td></tr><tr><td>predict_only</td><td>False</td><td>True</td><td>False</td></tr><tr><td>use_prior</td><td>True</td><td>True</td><td>True</td></tr></tbody></table>

**Scallop.** Since Scallop has been only applied to the MNIST-1-SUM task Huang et al. (2021), we extend the experiments with Scallop to the MNIST-N-SUM task for N={2,3,4} in order to use it as baseline. The logic programs are given in Listing 1. We use Scallop with exact as well as with approximate reasoning. For approximate reasoning of Scallop we choose the `diff-top-k-proof` semiring with $k=3$, as recommended in Huang et al. (2021). To investigate the performance of Scallop with exact reasoning, we choose $k$ in a way that the logic provenance formula is in any case small than $k$ and is consequently not pruned. In particular, we choose $k$ for every MNIST-N-SUM task depending on N:

$$k = 2^{2 \cdot 10 \cdot N}.$$

This way, $k$ represents an upper bound for the length of the logical provenance formula.

**DPLA\*.** DPLA\* employs heuristics to estimate the probability of partial proofs to search for the best proof. Here, we use the geometric mean heuristic Manhaeve, Marra, and De Raedt (2021).

1 # N=1
2 self.scl_ctx.add_rule("summand_one(a) :- digit_1(a)")
3 self.scl_ctx.add_rule("summand_two(a) :- digit_2(a)")
4 # N=2
5 self.scl_ctx.add_rule("summand_one(10 * a + b) :- digit_1(a), digit_2(b)")
6 self.scl_ctx.add_rule("summand_two(10 * a + b) :- digit_3(a), digit_4(b)")
7 # N=3
8 self.scl_ctx.add_rule("summand_one(10 * 10 * a + 10 * b + c) :- digit_1(a), digit_2(b), digit_3(c)")
9 self.scl_ctx.add_rule("summand_two(10 * 10 * a + 10 * b + c) :- digit_4(a), digit_5(b), digit_6(c)")
10 # N=4
11 self.scl_ctx.add_rule("summand_one(10 * 10 * 10 * a + 10 * 10 * b + 10 * c + d) :- digit_1(a), digit_2(b), digit_3(c), digit_4(d)")

12 self.scl_ctx.add_rule("summand_two(10 * 10 * 10 * a + 10 * 10 * b + 10 * c + d) :- digit_5(a), digit_6(b), digit_7(c), digit_8(d)")

<caption>Listing 1: Rules used in Scallop for the MNIST-N-SUM task</caption>