Paper deep dive
DPNL: A DPLL-based Algorithm for Probabilistic Neurosymbolic Learning
Thomas Jean-Michel Valentin, Pierre Genev{è}s, Luisa Sophie Werner, Sarah Chlyah, Nabil Laya{ï}da, Nils Gesbert
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Probabilistic Neurosymbolic Learning (PNL) combines neural predictions with symbolic reasoning, enabling end-to-end learning from final-output supervision without labels for intermediate concepts. A central challenge is probabilistic inference: state-of-the-art approaches often rely on materializing the logical provenance of a query, which can itself become a major computational bottleneck. We introduce Dynamic Probabilistic Neurosymbolic Learning (DPNL), an oracle-guided framework that avoids requiring complete provenance materialization before inference. DPNL lazily explores the space of intermediate assignments, while oracles resolve entire regions that can already be certified to produce or exclude the target output. We establish conditions ensuring soundness and termination. ApproxDPNL extends the same search with early termination while maintaining certified bounds on the exact output probability, providing controlled approximation guarantees. The oracle interface decouples inference from the representation of the symbolic component, enabling problem-specific reasoning within the same framework. Experiments on several neurosymbolic tasks show that DPNL and ApproxDPNL substantially extend the range of problem instances tractable by probabilistic neurosymbolic inference.
Tags
Links
- Source: https://arxiv.org/abs/2610.06270v1
- Canonical: https://arxiv.org/abs/2610.06270v1
Trouble viewing inline? Open PDF directly →
Full Text
71,469 characters extracted from source content.
Expand or collapse full text
DPNL: A DPLL-based Algorithm for Probabilistic Neurosymbolic Learning Thomas Valentin , Pierre Genev ` es , Luisa Werner , Sarah Chlyah , Nabil Laya ̈ ıda , Nils Gesbert Tyrex team, Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG Grenoble, France, 38000 Abstract Probabilistic Neurosymbolic Learning (PNL) com- bines neural predictions with symbolic reasoning, enabling end-to-end learning from final-output su- pervision without labels for intermediate concepts. A central challenge is probabilistic inference: state- of-the-art approaches often rely on materializing the logical provenance of a query, which can it- self become a major computational bottleneck. We introduce Dynamic Probabilistic Neurosymbolic Learning (DPNL), an oracle-guided framework that avoids requiring complete provenance materializa- tion before inference. DPNL lazily explores the space of intermediate assignments, while oracles resolve entire regions that can already be certified to produce or exclude the target output. We estab- lish conditions ensuring soundness and termination. ApproxDPNL extends the same search with early termination while maintaining certified bounds on the exact output probability, providing controlled approximation guarantees. The oracle interface de- couples inference from the representation of the symbolic component, enabling problem-specific rea- soning within the same framework. Experiments on several neurosymbolic tasks show that DPNL and ApproxDPNL substantially extend the range of problem instances tractable by probabilistic neu- rosymbolic inference. 1 Introduction Neurosymbolic artificial intelligence seeks to combine the learning capabilities of neural networks with structured sym- bolic reasoning [ van Harmelen and ten Teije, 2019; Ver- meulen et al., 2023 ] . Probabilistic Neurosymbolic Learn- ing (PNL) is one approach to this integration, in which neu- ral networks predict probability distributions over interme- diate concepts and a symbolic component combines these predictions to produce the final output [ De Raedt et al., 2020; Li et al., 2023 ] . A key advantage of this setting is that the inter- mediate predictions need not be supervised directly. Instead, the symbolic computation connects them to the observed out- put, allowing the neural component to be trained end-to-end from supervision on the final task. At the same time, the symbolic component makes explicit how intermediate predic- tions are combined to determine the final output, providing a structured and inspectable reasoning process. Consider, for instance, a kinship-reasoning task in the style of CLUTRR [ Sinha et al., 2019 ] . Given a short text describing relations between people, a neural component may predict distributions over uncertain relations such as sister, aunt, or parent. Symbolic kinship rules then compose these relations to answer a query such as “How are Rich and Anne related?”. Training may provide only the correct answer to this final query, and not the intermediate relations required to derive it. Learning therefore requires propagating supervision through the symbolic reasoning process while accounting for uncer- tainty in the intermediate neural predictions. This introduces a central computational challenge. To ob- tain the probability of a given output, probabilistic reasoning must aggregate the probability mass of all assignments of the intermediate predictions that make the symbolic computation produce that output. Depending on the task, this aggregation may admit an efficient computation or a compact representa- tion. In general, however, the number of relevant assignments can grow rapidly with the number of intermediate variables, making their explicit enumeration impractical. Importantly, this difficulty is distinct from the cost of evaluating the sym- bolic computation on one complete assignment: a symbolic function may be inexpensive to evaluate while the set of assign- ments leading to a given output is much harder to represent or aggregate over. Existing exact PNL approaches such as DeepProbLog [ Man- haeve et al., 2021a ] address this problem by constructing the logical provenance of a query, using knowledge compi- lation techniques, and subsequently performing probabilistic inference over that representation. However, constructing the complete provenance can itself become a bottleneck when the number of alternative reasoning paths is large. Approx- imate methods have consequently been proposed to extend PNL to larger problem instances [ Manhaeve et al., 2021b; Huang et al., 2021; van Krieken et al., 2023 ] . These methods trade exact inference for scalability in different ways. This motivates a complementary question: can probabilistic infer- ence avoid constructing the complete provenance in the first place, while retaining exact inference when feasible and pro- viding explicit control over the error when approximation is necessary? arXiv:2610.06270v1 [cs.AI] 5 Oct 2026 Contribution. Our main contribution is the DPNL frame- work, a new probabilistic reasoning architecture for end-to-end neurosymbolic learning, with two major aspects: i.Inference without full provenance materialization. In- stead of constructing the complete logical provenance of a query before inference, DPNL performs a lazy explo- ration of partial assignments and dynamically eliminates regions of the implicit reasoning space that can be de- termined to succeed or fail. Only regions that cannot yet be decided are explored further. This yields an ex- act inference procedure when exploration is continued to completion. i.Certified approximation. When exact inference is not required, ApproxDPNL can stop this exploration early while maintaining certified bounds on the exact output probability. Specifically, it tracks the probability mass of unresolved regions and maintains certified lower and upper bounds on the exact output probability at any point during the search. An important architectural property of DPNL and Approx- DPNL is their ability to combine neural predictions over finite- domain random variables with diverse forms of symbolic rea- soning. They separate probabilistic inference from the rep- resentation and implementation of the symbolic component, allowing the same inference architecture to accommodate a broad range of symbolic representations and reasoning proce- dures. We formalize a generic oracle interface that supports ordinary executable symbolic programs, solver-backed logi- cal specifications, and domain-specific oracles, and establish conditions under which oracle-guided inference is sound and terminating. We implement DPNL and ApproxDPNL in a research pro- totype and evaluate them on several neurosymbolic tasks. Ex- periments show that oracle-guided reasoning can substantially extend the range of tractable problem instances for probabilis- tic neurosymbolic learning. 2 Problem Setting and Definitions A probabilistic neurosymbolic learning (PNL) problem com- bines a neural component with a symbolic reasoning compo- nent, with the goal of learning intermediate neural predictions from supervision on the final symbolic output. Given a fixed observed inputifrom an input spaceI, the neural component predicts a distribution for each ofmrandom variablesX 1 (i),...,X m (i), where eachX k (i)takes values in a finite domain V k . We write π θ,k (x| i) = P X k (i) = x for the predicted distribution ofX k (i), whereθcollects all neural parameters. The neural component may consist of one or several neural networks. The symbolic component is a deterministic function S : V 1 ×·× V m →O, which maps a joint assignment of the neural variables to an output o∈O. For instance, in the kinship example, the variablesX k (i) represent uncertain relations extracted from the text, while Sapplies symbolic reasoning to these relations to infer the answer to the final kinship query. Foreachfixedinputi,therandomvariables X 1 (i),...,X m (i)are assumed to be mutually indepen- dent. The probability assigned to an outputofor inputiis then p θ (o| i) := Pr(S(X 1 (i),...,X m (i)) = o) = X x:S(x)=o m Y k=1 π θ,k (x k | i), (1) wherex = (x 1 ,...,x m ). SinceSis deterministic and does not depend onθ, Eq.(1) is a finite sum of products of neural probabilities. Therefore, since the distributionsπ θ,k are differentiable with respect to θ, thenp θ (o | i)is differentiable as well. This enables end- to-end learning from supervision on the final output, without requiring labels for the intermediate variables X k (i). Major computational challenge. Computing Eq.(1)can nevertheless be expensive. The set of assignments x∈ V 1 ×·× V m | S(x) = o may be exponentially large inm. Consequently, explicitly enumerating all assignments that contribute to the sum can become intractable. The inference problem considered in this work is therefore to computep θ (o | i)exactly, or to approximate it with cer- tified bounds, without explicitly materializing the full set of satisfying assignments. 3 DPNL: Oracle-Guided Inference We now introduce Dynamic Probabilistic Neurosymbolic Learning (DPNL), an inference framework for computing the output probability in Eq.(1)without explicitly materializing the set of satisfying assignments. The key idea is to reason over regions of the assignment space rather than over complete assignments individually. DPNL queries the symbolic component through an oracle that, for a region and a target outputo, can return one of three answers: (i) every assignment in the region produceso, (i) no assignment in the region produceso, or (i) the available information is insufficient to decide. In the first two cases, DPNL can account for or discard the entire region without exploring its individual assignments. In the third case, DPNL further explores the region. This oracle interface abstracts away the particular repre- sentation ofS: DPNL only requires enough information to determine whether a region can already be accepted or rejected. The resulting split-or-prune process follows the same recur- sive principle as DPLL-style search (an analogy intentionally reflected in the name DPNL). We now formalize these regions using valuations and state the conditions that an oracle must satisfy. 3.1 Search Regions and Oracle Interface We formalize the regions explored by DPNL using valuations. A valuationvof the variables(X k ) 1≤k≤m is an array of size m such that, for every k ∈ [1,m], v[k]∈ V k ∪⋆. The value ⋆ indicates that X k (i) has not yet been assigned. We denote byVthe set of all valuations. A valuationvis total ifv[k] ̸= ⋆for everyk ∈ [1,m], and partial otherwise. A valuation v ′ is a refinement of v if ∀k ∈ [1,m], v[k]̸= ⋆ =⇒ v ′ [k] = v[k]. Thus,v ′ preserves all values fixed inv, while possibly fixing additional variables. We denote bytot(v)the set of all total refinements ofv. We calltot(v)the region represented byv. The empty valuation v ∅ = [⋆,...,⋆]represents the whole assignment space, while a total valuation represents a single complete assignment. Forx ∈ V k , we denote byv v[k]←x the valuation obtained from v by replacing v[k] with x. For a given valuationvand outputoofS, an oracle is in charge of determining whether it is still relevant to explore refinements ofvor whether the exploration process can be stopped. Formally, an oracle is a function O S :V ×O →0, 1,⋆. Given a valuationvand a target outputo, the oracle returns 1if it can establish that every total refinement ofvproduces o,0if it can establish that no total refinement produceso, and ⋆otherwise. Intuitively,⋆indicates that the oracle cannot yet decide the region and further exploration is needed. We call an oracle valid when its definitive answers are sound and it always decides total valuations. Formally,O S is a valid oracle for S if, for every v ∈V and o∈O, O S (v,o) = 1 =⇒∀v ′ ∈ tot(v), S(v ′ [1],...,v ′ [m]) = o, (2) O S (v,o) = 0 =⇒∀v ′ ∈ tot(v), S(v ′ [1],...,v ′ [m])̸= o. (3) In addition, for every total valuationv,O S (v,o) ̸= ⋆. Since tot(v) =v when v is total, the previous conditions imply O S (v,o) = 1 if S(v[1],...,v[m]) = o, 0 otherwise. A valid oracle is complete if the implications in Eqs.(2)–(3) are equivalences. Importantly, DPNL requires validity but not completeness: returning⋆on a partial valuation only causes the corresponding region to be explored further. Completeness therefore affects pruning efficiency, but not correctness. 3.2 Exact Inference with DPNL Algorithm 1 presents the core algorithm of the framework. Starting from the empty valuationv ∅ = [⋆,...,⋆], DPNL computes the output probability in Eq. 1 as DPNL(i,o,v ∅ ,O S ) = P S(X 1 (i),...,X m (i)) = o = p θ (o| i). Algorithm 1: DPNL(i,o,v,O S ) Input: i∈I, o∈O, v ∈V , and an oracle O S for S. Output: The probability of obtaining o under 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 ∈ [1,m] such that v[k] = ⋆. 7:return Σ y∈V k P(X k (i) = y)· DPNL(i,o,v v[k]←y ,O S ) 8: end if A recursive call terminates as soon as the oracle returns 0or1. Otherwise, choosing an unassigned variableX k (i) partitions the current region into the regions represented by its refinements, whose contributions are combined according to Pr(X k (i) = y). Theorem 1 (DPNL termination and correctness). For any inputi ∈ I, outputo ∈ O, and valid oracleO S forS, DPNL(i,o,v ∅ ,O S ) terminates and returns p θ (o| i). The proof is provided in the supplementary material. Crucially, DPNL explores the assignment space lazily: re- gions are further explored only when the oracle cannot decide them. It therefore avoids materializing the full query prove- nance before inference. 3.3 Approximate Inference with ApproxDPNL ApproxDPNL, presented in Algorithm 2, extends this lazy search with early termination while maintaining certified bounds on the exact probability. Algorithm 2: ApproxDPNL(i,o,O S ,STOP,H) Input:i ∈ I,o ∈ O, a valid oracleO S forS, a stopping condition STOP, and a search heuristic H. Output: Bounds (low, up) such that low ≤ p θ (o| i)≤ up. 1: low, up ← 0, 1 2: Q←v ∅ 3: while Q̸=∅ and¬STOP(low, up) do 4: v ← H(Q) 5: Q← Q\v 6:mass ← Y k:v[k]̸=⋆ π θ,k (v[k]| i) 7:if O S (v,o) = 1 then 8:low ← low + mass 9:else if O S (v,o) = 0 then 10:up ← up− mass 11:else 12:Choose k ∈ [1,m] such that v[k] = ⋆ 13: Q← Q∪v v[k]←y | y ∈ V k 14:end if 15: end while 16: return (low, up) ApproxDPNL maintains a setQof valuations representing regions whose contribution to the target output has not yet been resolved. Throughout the search, it maintains a lower bound lowand an upper boundupsuch thatp θ (o | i) ∈ [low,up]. The lower boundlowis the probability mass already certified to produceo, whileupadditionally includes all unresolved probability mass, which may still contribute to the output. Equivalently,1− upis the probability mass already certified not to produceo. Hence,up− lowis precisely the unresolved probability mass, and at every iteration, the interval tightens: low ≤ p θ (o| i)≤ up. Stopping condition. A functionSTOPdetermines how tightly the returned interval must boundp θ (o | i)before in- ference terminates. IfSTOPnever triggers, all regions are eventually resolved andlow = up = p θ (o| i), recovering ex- act inference. Different stopping conditions provide different approximation guarantees. Additive approximation. For a desired absolute errorε > 0 with respect to the exact probabilityp θ (o| i), the search can stop whenup− low ≤ 2ε. The midpointˆp = (low + up)/2 then satisfies|ˆp− p θ (o| i)|≤ ε. Multiplicative approximation. Forε > 0,ˆpis a multiplica- tiveε-approximation whenp θ (o | i)/(1 + ε) ≤ ˆp ≤ (1 + ε)p θ (o| i) . Whenlow > 0, stopping whenup ≤ low(1 +ε) 2 and takingˆp = √ low upprovides this guarantee. This interval- to-estimate conversion follows [ Dubray et al., 2024 ] . Anytime inference. Without prescribing an error tolerance, ApproxDPNL may instead be interrupted under any compu- tational budget: the returned interval remains certified at any time. Its midpoint has absolute error at most(up − low)/2; whenlow > 0, the geometric mean provides a multiplicative guarantee with ε = p up/low − 1. Search heuristic. The search heuristic H determines which unresolved region is explored next by selecting a valuation vfromQ. The choice of the next unassigned variableX k (i) can likewise follow a fixed ordering or a problem-specific branching heuristic. These choices affect how quickly the bounds tighten, but not their validity. 3.4 Designing and Combining Oracles Both DPNL and ApproxDPNL rely on the same oracle in- terface. Any symbolic functionSthat can be evaluated on complete valuations admits a valid oracle: one may simply return⋆on every partial valuation and evaluateSonce the valuation is total. Hence, the existence of an oracle does not restrict the applicability of DPNL. Oracles determine how efficiently the search space can be explored. In practice, oracle design involves a trade-off between the cost of each oracle call and its pruning power, i.e., how early and how much of the remaining search space it can resolve. A stronger oracle may avoid many recursive calls, but may itself be more expensive to evaluate. In particular, completeness maximizes the ability to decide partial valuations, but does not imply computational efficiency. Basic oracles. When an executable implementation ofS is available, a basic oracle can be obtained automatically by running it on a partial valuation. If the execution attempts to access an unassigned variable, the oracle returns⋆; otherwise, the computation terminates without depending on the remain- ing variables and its output determines whether to return 0 or 1. Basic oracles therefore inherit the computational efficiency of the implementation of S, but need not be complete. Solver-backed oracles.WhenSis expressed in a decidable logic, a solver can be used to determine whether all comple- tions of the current partial valuation produce the target output o, or whether none of them do. Such oracles can provide sub- stantially stronger pruning than direct program execution. We give in the supplementary material a generic construction for logic-based PNL systems, together with sufficient conditions under which the resulting oracle is valid and complete. Custom and combined oracles. Domain knowledge can also be used to implement specialized valid oracles. For exam- ple, in relational reasoning tasks such as CLUTRR, an oracle can propagate the relations already fixed in a partial valua- tion. Knowing thatAis the sister ofBandBthe father ofC, for instance, may already determine thatAis the aunt ofC, independently of the remaining unknown relations. Different valid oracles can moreover be combined safely. GivenO 1 ,...,O p , DPNL may query them in sequence and return the first answer different from⋆. The resulting oracle remains valid; if one of the queried oracles is complete, the combination is complete as well. This makes it possible to query inexpensive oracles first and fall back to stronger, more costly reasoning only when needed. 4 Experimental Evaluation We conduct experiments on symbolic and neurosymbolic rea- soning 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 ap- proach compare to SOTA PNL systems with exact and approx- imate reasoning in terms of efficiency and accuracy? Q3: How do the parameters of ApproxDPNL, the per- sample timeout of the anytime approximation and the error budgetεof theε-approximation, trade accuracy against run- time? We first report on the experimental methodology and re- sults for symbolic reasoning tasks, followed by neurosymbolic evaluations and an analysis of theεand anytime timeout pa- rameters of ApproxDPNL. 4.1 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. 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 over0,..., 9, simulating uncer- tainty in perception. Here, we randomly generate the digit distributions. The symbolic functionSperforms 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 forS. The logic oracle is generated from the Boolean logic represen- tation 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 withNnodes, represented by an adjacency matrix containingN 2 potential edges. Each edge is assumed to be independently present with a certain probability. The symbolic functionSis 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. 23456789101112 N 10 1 10 0 10 1 10 2 Runtime (seconds) MNIST-N-SUM Basic Oracle Logic Oracle Combined Oracle ProbLog Timeout (120s) Figure 1: Q1 Runtimes (in seconds) for MNIST-N-SUM. 345678 N 10 1 10 0 10 1 10 2 Runtime (seconds) Graph Reachability Basic Oracle Logic Oracle Combined Oracle Custom Oracle ProbLog Timeout (120s) Figure 2: Q1 Runtimes (in seconds) for graph reachibility. Experimental results.Figures 1 and 2 show the time spent on symbolic reasoning for MNIST-N-SUM and graph reach- ability, respectively. On MNIST-N-SUM, results show that DPNL scales better than ProbLog, solving task instances for N ≥ 7where ProbLog fails with a timeout. Results also show that the logic oracle, although slower on small instances, scales better than the basic oracle. Reasoning BenchmarkDifficulty Exact ε- approx. Anytime approx. Leaf120✓ MNIST-N -SUM 10 2N ✓ Visual Sudoku10 N×N ✓ Table 1: Overview of the neurosymbolic benchmarks. Difficulty is the size of the symbolic search space The Reasoning columns mark which DPNL inference modes are evaluated on each benchmark. Regarding graph reachability, for small instances (up to N = 5) Problog is faster than DPNL. However, forN ≥ 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. 4.2 Application to neurosymbolic AI (Q2) We now evaluate DPNL on a neuro-symbolic benchmark suite, including MNIST-N-Sum, Visual Sudoku and Leaf classifica- tion. Table 1 summarizes the difficulty of the task (regarding the symbolic search space) and the versions of the algorithm (exact,ε-approximation or anytime approximation) that are evaluated on each benchmark. More details on hyperparam- eter values, timeout thresholds and information on hardware and baseline configurations are given in the supplementary material. Leaf Classification We use the LEAF-ID dataset built from the plant-leaf collec- tion of Kanda et al. [ 2021 ] which includes leaf images of11 plant species, with330training and110test samples. Each leaf is described by three discrete features (MARGIN, SHAPE and TEXTURE) with6,5and4possible values respectively. A neural model predicts a distribution over the values of each feature from the image, and the symbolic functionSmaps the feature values to a species.Sis a fixed decision tree over the species. Because the tree has a bounded number of paths, the reasoning difficulty does not scale with any instance-size parameter. There are at most6× 5× 4 = 120feature com- binations. The oracle evaluates the decision tree on a partial valuation and returns the species as soon as the branch is de- termined, usually without reading all three features. DPNL is used with exact reasoning on this benchmark. DPNL is trained for50epochs with the Adam optimiser (learning rate 1e−4, batch size4), and all methods are evaluated over10 independent runs. We compare DPNL against two families of baselines. The neurosymbolic baselines include DeepProbLog [ Manhaeve et al., 2018 ] , Scallop [ Huang et al., 2021 ] in two configurations (top-kprovenance and exact provenance, A- NeSI [ van Krieken et al., 2023 ] , and ISED [ Solko-Breslin et al., 2024 ] . The sampling-based gradient-approximation base- lines REINFORCE [ Williams, 1992 ] and NASR [ Cornelio et al., 2023 ] treat the tree as a black box and estimate the gradient from sampled neural predictions Results.The results are given in Table 2. DPNL with exact MethodAccuracyStdTime DPNL (exact)0.80800.036010:15 Neurosymbolic (probabilistic inference) DeepProbLog0.43270.03081:02:28 Scallop (top-k)0.77090.02845:30 Scallop (exact)0.76910.029455:34 A-NeSI0.72910.090921:33 ISED0.79640.026118:03 Sampling-based gradient approximation REINFORCE0.79550.03576:52 NASR0.10090.01552:03 Table 2: Results on the Leaf benchmark. Average test accuracy, standard deviation, and total wall-clock runtime (h:m:s), over 10 independent runs. Highest accuracy and lowest runtime in bold. reasoning obtains the highest mean accuracy (0.808) on Leaf. Among the exact methods it is also the fastest:10:15against 55:34for Scallop withk = 120and1:02:28for DeepProbLog, whose accuracy drops to0.43. ISED and REINFORCE come close to DPNL (0.796), whereas NASR falls to chance level (0.10≈ 1/11). MNIST-N-Sum MNIST-N-SUM [ Manhaeve et al., 2018 ] is the task of pre- dicting the sum of twoN-digit numbers written as sequences of handwritten-digit images, supervised only by the value of the sum and never by the individual digit labels (e.g. a pair of two-digit images reading28 + 35 = 63). We evaluate N = 2, 3, 4, 8. DPNL is run in three modes: exact infer- ence,ε-approximation, and anytime approximation. Training uses Adam with learning rate1e−3and batch size2. The accuracy numbers are averaged over10seeds. Per-mode and per-Nhyper-parameters are listed in Table 6 in the appendix. We compare DPNL (with the basic oracle) with the exact neu- rosymbolic methods DeepProbLog and Scallop [ Huang et al., 2021 ] and with A-Nesi [ van Krieken et al., 2023 ] , DPLA ∗ [ Manhaeve et al., 2021b ] and Scallop (with the top-k semir- ing), 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 exper- iment is performed with multiple independent runs, and we report the average test accuracy and the average reasoning time per sample during training. The parameters forεand timeout for ApproxDPNL have been chosen based on parameter tun- ing to find a good balance between accuracy and runtime, see Section 4.3. ResultsAmong the other exact PNL systems, DeepProbLog matches DPNL’s accuracy atN = 2but no longer finishes forN ≥ 3, and Scallop (exact) already times out atN = 2. DPNL in exact mode is the only method that completes N = 4(avg. accuracy0.83) and times out only atN = 8. Theε- and anytime-approximation modes preserve accuracy while improving scalability. The anytime mode matches exact inference to within one point at everyNwhile cutting the per-sample symbolic time by5to23×(e.g.0.27s vs.6.1s at N = 4), and it is the only method that runs at all atN = 8 within the timeout threshold. Theε-approximation behaves similarly. It stays within one point of exact inference (0.9062, 0.8730,0.8219forN = 2, 3, 4), and atN = 4its per-sample symbolic time is0.67s which is9×below exact, between the anytime mode (0.27s) and exact (6.1s). Comparing exact and approximate inference under the same training budget, a clear accuracy gap opens between the DPNL modes and the approximate baselines fromN = 3on. DPNL reaches ≈ 0.87atN = 3versus at most0.84for the baselines, and atN = 4only A-NeSI among the baselines finishes, its best variant (explain) reaching0.66versus0.83for DPNL. This gap should be read as a difference in data efficiency under a short training budget rather than as a bound on the accuracy that approximate methods can reach, since A-NeSI is reported to reach higher accuracies with substantially more training epochs [ van Krieken et al., 2023 ] . AtN = 8, all three A- NeSI variants terminate and reach0.702± 0.025(predict), 0.702± 0.031(explain) and0.684± 0.021(prune), close to the0.723± 0.257of anytime DPNL, the only DPNL mode that finishes at this scale. A-NeSI keeps its speed advantage: its per-sample reasoning time is0.0136s (predict),0.0349s (explain) and0.0340s (prune), the same order of magnitude as forN ≤ 4and more than50×below the1.94s of anytime DPNL. Visual Sudoku We use the Visual Sudoku Puzzle Classification dataset of Augustine et al. [ 2022 ] . The task is to decide whether an N × Ngrid of digit images forms a valid Sudoku, that is, whether no digit occurs twice in any row, any column, or any √ N × √ Nblock. We considerN ∈ 4, 9. Each cell is perceived by the same MNIST classifier as in the MNIST- N-SUM task. In DPNL, each of theN 2 cells is a random variable over0,..., 9, so a naive PWMC enumeration of the possible grids would consider10 N×N total valuations. The oracle prunes this search space as follow. Given a partial valuation (a partially filled grid), it returns0(invalid) as soon as a duplicate appears in any row, column or block, without waiting for the remaining cells to be assigned. We test DPNL in its exact, anytime and epsilon mode. We compare DPNL to a CNN as neural baseline and to the neuro-symbolic methods NeuPSL [ Pryor et al., 2023 ] and A-Nesi. As for MNIST, the parameters for epsilon and anytime result from parameter tuning, see Section 4.3. For N9, we use a pretrained classifier. For better comparability, we also evaluate A-Nesi with the same pretrained classifier on N9. The results for the CNN, A-Nesi (without pretraining) and NeuPSL are taken from [ van Krieken et al., 2023 ] . Results.Table 4 reports the results. AtN = 4, exact DPNL reaches0.912without classifier pretraining, slightly above the best baselines trained in the same setting (A-NeSI,0.898; NeuPSL,0.897). Both approximations stay close to exact inference (0.910for theε-approximation and0.890for any- time) while reducing the wall-clock time per run from about 45to12and5min, respectively. AtN = 9, the search space grows to10 81 grids and the exact inference baseline times out, whereas anytime DPNL still trains and reaches0.757, the highest accuracy of all methods, ahead of pretrained A-NeSI N = 2N = 3N = 4N = 8 AccStdTimeAccStdTimeAccStdTimeAccStdTime DPNL (exact)0.91000.01610.03010.87350.01680.47830.83200.02096.1344T/OT/OT/O DPNL (ε)0.90620.01240.00610.87300.02160.04300.82190.02430.6656T/OT/OT/O DPNL (anytime)0.91150.01180.00630.86360.01570.02710.82660.03670.26540.72270.25661.9446 DeepProbLog0.90980.01220.4784T/OT/OT/OT/OT/OT/OT/OT/OT/O Scallop (exact)T/OT/OT/OT/OT/OT/OT/OT/OT/OT/OT/OT/O DPL A*0.89450.01460.02550.83650.03030.1237T/OT/OT/OT/OT/OT/O Scallop (top-k)0.82570.20600.02440.75230.26120.9521T/OT/OT/OT/OT/OT/O A-Nesi (predict) † 0.88490.01420.02650.77960.00740.01700.59290.03940.02210.70230.02480.0136 A-Nesi (explain) † 0.89520.00710.02130.77070.01790.02190.65840.02390.02680.70160.03090.0349 A-Nesi (prune) † 0.78660.22250.01950.77060.02140.02060.59050.03390.02450.68410.02070.0340 Table 3: Results on the MNIST-N-SUM task: average test accuracy (Acc), its standard deviation (Std), and average reasoning time per sample during training (Time, in seconds), over several independent runs. Highest accuracy and lowest runtime in bold. † It is worth noting that van Krieken et al. [ 2023 ] report higher accuracies for A-NeSI (0.960forN = 2and0.926forN = 4) with100training epochs and batch size16 on a GPU. We instead train A-NeSI with training parameters similar to those of the other methods, to keep accuracies and reasoning times comparable across systems. ForN = 8, all methods are trained for more epochs, which explains why A-NeSI reaches a higher accuracy at N = 8 than at N = 4. MethodN = 4N = 9 DPNL (exact)0.9115± 0.0111T/O DPNL (ε-approx.)0.9100± 0.0191T/O DPNL (anytime)0.8895± 0.0297 0.7570± 0.0172 CNN0.5150± 0.03340.5120± 0.0220 NeuPSL [ Pryor et al., 2023 ] 0.8970± 0.02200.5150± 0.0137 A-NeSI (symbolic pred.)0.8970± 0.02080.6215± 0.0208 A-NeSI (neural pred.)0.8980± 0.02110.6225± 0.0220 A-NeSI (pretrained)–0.7230± 0.0214 Table 4: Results on Visual Sudoku: mean test accuracy±standard deviation over10runs. Highest accuracy in bold. Baselines are taken from van Krieken et al. [ 2023 ] , except A-NeSI (pretrained), which was ran on the same hardware. T/O denotes timeout. Wall-clock time per DPNL run is about45,12and5min atN = 4(exact,ε-approx., anytime) and 1h 43m to 3h 33m at N = 9. (0.723) that also profits from the pretraining of the classifier. 4.3 Analysis of the ε and Anytime Timeout Parameters (Q3) We study how the two parameters of ApproxDPNL trade ac- curacy against runtime and consider the per-sample timeout tof the anytime approximation and the error budgetεof the ε-approximation. MNIST-N-SUM. Figure 3 shows test accuracy and total runtime as a function oftforN ∈2, 3, 4. Accuracy behaves like a threshold: it stays at0as long astis too small for most samples to be resolved, then jumps to a plateau (about0.90for N = 2,0.84to0.89forN = 3and0.83to0.85forN = 4) that larger timeouts barely improve. Runtime, in contrast, grows roughly linearly witht, e.g. from1h 20m att = 0.5s to7h 57m att = 3s forN = 4. The best operating point therefore lies just above the threshold. Figure 4 shows the analogous experiment overεforN ∈ 1, 2, 3, 4. Runtime drops steeply asεgrows, while accuracy stays close to that of exact inference up to a breaking point that decreases with the task size (aboutε = 0.6forN = 2,0.5forN = 3and t (s)Acc.StdRuntime 0.010.3500.1891:07 0.020.4010.0851:52 0.040.4920.0182:56 0.050.4990.0023:35 0.060.5340.0764:16 0.070.8150.0224:49 0.0750.8390.0375:03 0.080.8800.0465:13 0.10.8770.0256:23 0.20.9030.0199:19 0.50.8840.03716:16 Table 5: Anytime-timeout tuning on Visual SudokuN = 4: mean test accuracy, its standard deviation and mean total runtime (m:s) over 5 seeds. Highest accuracy and lowest runtime in bold. 0.4forN = 4) and collapses beyond it. AtN = 4, exact inference and all budgetsε≤ 0.2exceed the4h limit, so the ε-approximation is what makes this instance tractable. Larger instances thus tolerate less approximation, but they are also those that benefit most from it. Visual Sudoku.Table 5 and Figure 5 report the same obser- vation overtforN = 4, with10training epochs, batch size 1, no classifier pretraining and5seeds per configuration. The anytime approximation shows the same threshold behaviour as on MNIST-N-SUM. Accuracy stays at or below chance level (0.5on this binary task) up tot = 0.06s, rises to0.815at t = 0.07s and0.880att = 0.08s, and then saturates between 0.877and0.903up tot = 0.5s, while the runtime keeps growing from5to16min. We therefore uset = 0.08s in the main experiments. 5 Related Works 5.1 Symbolic AI DPNL builds on a line of work on exact and approximate weighted model counting (WMC). Probabilistic logic program- ming languages such as ProbLog [ De Raedt et al., 2007 ] pro- (a) N = 2(b) N = 3(c) N = 4 Figure 3: Test accuracy (blue, left axis) and total runtime (red, right axis) as a function of the per-sample symbolic timeout t (in seconds) for the anytime approximation on MNIST-N -SUM. No sweep was run for N = 8. vide an important foundation for provenance-based probabilis- tic inference, later adopted by neurosymbolic approaches such as DeepProbLog. The recursive, search-based structure of DPNL follows the DPLL algorithm [ Davis et al., 1962 ] , which decomposes a formula by branching on variable assignments. The use of oracles inside DPNL used to resolve a query under partial valuations is inspired by the decision-DNNF compila- tion strategies of Lagniez and Marquis [ Lagniez and Marquis, 2017 ] . The approximation techniques used in ApproxDPNL are inspired by works in the symbolic AI literature, namely the anytime DPLL-based weighted model counting procedure of Dubray et al. [ Dubray et al., 2024 ] and the approximate weighted model counting withεguarantees [ Chakraborty et al., 2015 ] . Unlike DPNL and ApproxDPNL, none of these systems are used to train a neural component from output-level supervision. They only address general-purpose probabilistic inference and compilation rather than neuro-symbolic learn- ing. 5.2 Neurosymbolic AI Neurosymbolic AI is a wide field containing a large number of different approaches. They share the same overall goal: bringing neural networks and symbolic AI together, but dif- fer widely in how the two are combined, e.g. by relaxing logical connectives into differentiable operators (fuzzy-logic approaches such as Logic Tensor Networks [ Badreddine et al., 2022 ] ) or by adding a differentiable penalty for constraint vio- lation to the training loss (the semantic loss [ Xu et al., 2018 ] ). Other probabilistic neurosymbolic frameworks adopt different inference semantics altogether. For instance, NeuPSL [ Pryor et al., 2023 ] integrates neural predictions with Probabilis- tic Soft Logic and performs symbolic inference as convex MAP inference in a deep hinge-loss Markov random field. See [ van Harmelen and ten Teije, 2019; De Raedt et al., 2020; Vermeulen et al., 2023 ] for surveys. Within this broad landscape, we focus on approaches for solving the PNL problem defined in Section 2, in which neu- ral predictions over intermediate variables are combined by a symbolic function to determine the final output. Existing approaches differ primarily in how they perform the probabilis- tic inference required to compute or approximate the output probability in Eq. (1). We distinguish below approaches based on exact reasoning, proof-based approximation, surrogate or sampling-based approximation, and hardware-oriented accel- eration. Exact reasoning. DeepProbLog [ Manhaeve et al., 2018 ] is the seminal PNL approach that compiles the query’s full logi- cal provenance and performs exact weighted model counting (WMC) on it. NeurASP [ Yang et al., 2020 ] provides an anal- ogous integration with Answer Set Programs. DPNL instead computes the output probability in Eq. 1 through a lazy search over regions of the assignment space, without requiring the complete provenance to be materialized before inference. Proof-based approximation. A common approach to im- proving scalability is to restrict probabilistic inference to a subset of the query’s proofs. Scallop’s top-ksemiring [ Huang et al., 2021; Li et al., 2023 ] retains at mostkhigh-probability proofs during provenance construction, while approximate DeepProbLog [ Manhaeve et al., 2021b ] (DPLA ∗ ) uses A ∗ - search to focus inference on high-probability explanations rather than exhaustively aggregating over all proofs. These approaches therefore control the amount of proof search per- formed, rather than directly controlling the approximation error on the output probability. In particular, Scallop’s pa- rameterkcontrols the number of retained proofs, while the resulting error depends on the probability mass of the dis- carded proofs. ApproxDPNL instead maintains certified lower and upper bounds on the exact output probability throughout inference. Its stopping condition can therefore be expressed directly in terms of a desired additive or multiplicative er- ror, while the search may be interrupted at any point and still returns a certified interval. Surrogate and sampling-based approximation.Other ap- proaches avoid exact probabilistic inference by approximating either the inference result or the learning signal. A-NeSI [ van Krieken et al., 2023 ] trains neural prediction and explanation models to approximate probabilistic neurosymbolic inference, optionally combined with a symbolic pruner that excludes infeasible partial assignments. ISED [ Solko-Breslin et al., 2024 ] instead samples intermediate symbols, evaluates the symbolic program on these samples, and estimates gradients from the resulting partial representation of the program’s be- havior. These approaches can avoid the cost of exact inference, (a) N = 1(b) N = 2 (c) N = 3(d) N = 4 Figure 4: Test accuracy (left panel) and training time (right panel) as a function of the error budgetεfor theε-approximation on MNIST-N-SUM. For N = 4, the hatched region marks the budgets whose runs exceed the 4 h limit. No sweep was run for N = 8. Figure 5: Test accuracy (blue, left axis) and total runtime (red, right axis) as a function of the per-sample timeouttfor the anytime approx- imation on Visual SudokuN = 4. Shaded bands span±1standard deviation over seeds; the dashed line marks exact inference (accuracy 0.902). but unlike ApproxDPNL they do not maintain certified lower and upper bounds on the exact probability in Eq. 1. In partic- ular, unlike A-NeSI, ApproxDPNL does not require an aux- iliary learned inference model: its approximation guarantees follow directly from the unresolved probability mass during search. ApproxDPNL nevertheless retains an explicit search over the assignment space rather than replacing it with amor- tized or sampling-based inference. A complementary direction changes the probabilistic modeling assumptions themselves. Neurosymbolic diffusion models [ van Krieken et al., 2025 ] model dependencies between intermediate symbols through a discrete diffusion process. DPNL instead retains the inde- pendence assumption of the PNL problem considered in this work and focuses on making inference over that model more efficient and controllable. Hardware-oriented acceleration. A complementary line of work improves the execution of neurosymbolic reasoning on modern hardware. KLAY [ Maene et al., 2025 ] maps arith- metic circuits to a representation designed for efficient parallel evaluation on GPU, while Lobster [ Biberstein et al., 2026 ] compiles Datalog-based neurosymbolic programs for GPU execution. Dolphin [ Naik et al., 2025 ] executes symbolic reasoning on the CPU while vectorizing the probabilistic and gradient computations on the GPU. DeepLog [ Derkinderen et al., 2025 ] provides a more general neurosymbolic abstract machine based on extended algebraic circuits and GPU ex- ecution. These approaches primarily address the execution of neurosymbolic computations, whereas DPNL changes the inference procedure itself by lazily exploring the assignment space and avoiding complete provenance materialization when possible. The two directions are therefore complementary: hardware-oriented execution techniques could in principle also be investigated for accelerating DPNL. 6 Conclusion We introduced DPNL, an oracle-guided inference framework for probabilistic neurosymbolic learning that avoids requiring the complete logical provenance of a query to be materialized before inference. DPNL instead explores the space of inter- mediate assignments lazily, resolving regions as soon as their contribution to the target output can be determined. A generic oracle interface decouples this inference procedure from the representation of the symbolic component. For valid oracles, DPNL terminates and returns the exact output probability, while ApproxDPNL can stop the same search early while maintaining certified lower and upper bounds on that prob- ability, yielding controlled approximation guarantees. Our experiments show that DPNL can substantially extend the range of instances tractable by exact probabilistic inference, while ApproxDPNL extends this range further through cer- tified approximate inference. This suggests that probabilis- tic neurosymbolic inference can be organized as dynamic, on-demand exploration of the assignment space, rather than requiring a complete representation of all reasoning paths be- fore inference begins. This opens substantial room for further improvements in pruning, region selection, and branching strategies. References [ Augustine et al., 2022 ] Eriq Augustine, Connor Pryor, Charles Dickens, Jay Pujara, William Yang Wang, and Lise Getoor. Visual sudoku puzzle classification: A suite of collective neuro-symbolic tasks. In International Work- shop on Neural-Symbolic Learning and Reasoning (NeSy), Windsor, United Kingdom, 2022. [ Badreddine et al., 2022 ] Samy Badreddine, Artur d’Avila Garcez, Luciano Serafini, and Michael Spranger. Logic ten- sor networks. Artificial Intelligence, 303:103649, February 2022. [ Biberstein et al., 2026 ] Paul Biberstein, Ziyang Li, Joseph Devietti, and Mayur Naik. Lobster: A GPU-accelerated framework for neurosymbolic programming. In Proceed- ings of the 31st ACM International Conference on Architec- tural Support for Programming Languages and Operating Systems, Volume 1, ASPLOS ’26. ACM, 2026. [ Biewald, 2020 ] Lukas Biewald. Experiment tracking with weights and biases, 2020.Software available from wandb.com. [ Chakraborty et al., 2015 ] Supratik Chakraborty, Dror Fried, Kuldeep S. Meel, and Moshe Y. Vardi. From weighted to unweighted model counting. In Proceedings of the Twenty- Fourth International Joint Conference on Artificial Intelli- gence (IJCAI), 2015. [ Cornelio et al., 2023 ] Cristina Cornelio, Jan Stuehmer, Shell Xu Hu, and Timothy Hospedales. Learning where and when to reason in neuro-symbolic inference. In NeSy 2023, 17th International Workshop on Neural-Symbolic Learning and Reasoning, volume 3432 of CEUR Workshop Proceedings, 2023. Also published at ICLR 2023. [ Davis et al., 1962 ] M. Davis, G. Logemann, and D. Love- land. A machine program for theorem-proving. Communi- cations of the ACM, pages 394–397, 1962. [ De Raedt et al., 2007 ] Luc De Raedt, Angelika Kimmig, and Hannu Toivonen. Problog: A probabilistic prolog and its application in link discovery. In IJCAI, pages 2468–2473, 2007. [ De Raedt et al., 2020 ] Luc De Raedt, Sebastijan Duman ˇ ci ́ c, Robin Manhaeve, and Giuseppe Marra. From statistical re- lational to neural-symbolic artificial intelligence. In IJCAI, pages 4943–4950, 2020. [ Derkinderen et al., 2025 ] Vincent Derkinderen, Robin Man- haeve, Rik Adriaensen, Lucas Van Praet, Lennert De Smet, Giuseppe Marra, and Luc De Raedt. The deeplog neu- rosymbolic machine, 2025. [ Dubray et al., 2024 ] Alexandre Dubray, Pierre Schaus, and Siegfried Nijssen. Anytime weighted model counting with approximation guarantees for probabilistic inference. In 30th International Conference on Principles and Practice of Constraint Programming, pages 10:1–10:16, 2024. [ Huang et al., 2021 ] Jiani Huang, Ziyang Li, Binghong Chen, Karan Samel, Mayur Naik, Le Song, and Xujie Si. Scal- lop: From probabilistic deductive databases to scalable differentiable reasoning. In NeurIPS, pages 25134–25145, 2021. [ Kanda et al., 2021 ] Paul Shekonya Kanda, Kewen Xia, and Olanrewaju Hazzan Sanusi. A deep learning-based recog- nition technique for plant leaf classification. IEEE Access, 9:162590–162613, 2021. [ Lagniez and Marquis, 2017 ] Jean-Marie Lagniez and Pierre Marquis. An improved decision-DNNF compiler. In Pro- ceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI), 2017. [ Lecun et al., 1998 ] Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278–2324, 1998. [ Li et al., 2023 ] Ziyang Li, Jiani Huang, and Mayur Naik. Scallop: A language for neurosymbolic programming. In ACM on Programming Languages, pages 1463–1487, 2023. [ Maene et al., 2025 ] Jaron Maene, Vincent Derkinderen, and Pedro Zuidberg Dos Martires. Klay: Accelerating arith- metic circuits for neurosymbolic ai, 2025. [ Manhaeve et al., 2018 ] Robin Manhaeve, Sebastijan Du- man ˇ ci ́ c, Angelika Kimmig, Thomas Demeester, and Luc De Raedt. Deepproblog: Neural probabilistic logic pro- gramming. In NeurIPS, pages 3753–3763, 2018. [ Manhaeve et al., 2021a ] Robin Manhaeve, Sebastijan Du- mancic, Angelika Kimmig, Thomas Demeester, and Luc De Raedt. Neural probabilistic logic programming in deep- problog. Artif. Intell., 298:103504, 2021. [ Manhaeve et al., 2021b ] Robin Manhaeve, Giuseppe Marra, and Luc De Raedt. Approximate Inference for Neural Probabilistic Logic Programming. In Proceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning, pages 475–486, 11 2021. [ Naik et al., 2025 ] Aaditya Naik, Jason Liu, Claire Wang, Amish Sethi, Saikat Dutta, Mayur Naik, and Eric Wong. Dolphin: A programmable framework for scalable neu- rosymbolic learning. In ICML, 2025. arXiv:2410.03348. [ Paszke et al., 2019 ] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas K ̈ opf, Edward Yang, Zach DeVito, Martin Raison, Alykhan Tejani, Sasank Chil- amkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library, 2019. [ Pryor et al., 2023 ] Connor Pryor, Charles Dickens, Eriq Au- gustine, Alon Albalak, William Yang Wang, and Lise Getoor. Neupsl: Neural probabilistic soft logic. In Edith Elkind, editor, Proceedings of the Thirty-Second Interna- tional Joint Conference on Artificial Intelligence, IJCAI-23, pages 4145–4153. International Joint Conferences on Arti- ficial Intelligence Organization, 8 2023. Main Track. [ Sinha et al., 2019 ] Koustuv Sinha, Shagun Sodhani, Jin Dong, Joelle Pineau, and William L. Hamilton. CLUTRR: A diagnostic benchmark for inductive reasoning from text. arXiv preprint arXiv:1908.06177, 2019. [ Solko-Breslin et al., 2024 ] Alaia Solko-Breslin, Seewon Choi, Ziyang Li, Neelay Velingker, Rajeev Alur, Mayur Naik, and Eric Wong. Data-efficient learning with neural programs. In NeurIPS, 2024. arXiv:2406.06246. [ van Harmelen and ten Teije, 2019 ] Frank van Harmelen and Annette ten Teije. A boxology of design patterns for hybrid learning and reasoning systems, 2019. [ van Krieken et al., 2023 ] Emile van Krieken, Thiviyan Thanapalasingam, Jakub Tomczak, Frank van Harmelen, and Annette Ten Teije. A-nesi: A scalable approximate method for probabilistic neurosymbolic inference.In NeurIPS, pages 24586–24609, 2023. arXiv:2212.12393. [ van Krieken et al., 2025 ] Emile van Krieken, Pasquale Min- ervini, Edoardo Maria Ponti, and Antonio Vergari. Neu- rosymbolic diffusion models.In Advances in Neu- ral Information Processing Systems, volume 38, 2025. arXiv:2505.13138. [ Vermeulen et al., 2023 ] Arne Vermeulen, Robin Manhaeve, and Giuseppe Marra. An experimental overview of neural- symbolic systems. In ILP, pages 124–138, 2023. [ Williams, 1992 ] Ronald J. Williams.Simple statistical gradient-following algorithms for connectionist reinforce- ment learning. Machine Learning, 8(3–4):229–256, 1992. [ Xu et al., 2018 ] Jingyi Xu, Zilu Zhang, Tal Friedman, Yitao Liang, and Guy Van den Broeck. A semantic loss function for deep learning with symbolic knowledge. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 5502– 5511. PMLR, 10–15 Jul 2018. [ Yang et al., 2020 ] Zhun Yang, Adam Ishay, and Joohyung Lee. Neurasp: Embracing neural networks into answer set programming. In Christian Bessiere, editor, Proceedings of the Twenty-Ninth International Joint Conference on Artifi- cial Intelligence, IJCAI-20, pages 1755–1762. International Joint Conferences on Artificial Intelligence Organization, 7 2020. Main track. A Termination and Correctness of DPNL We prove that DPNL terminates and returns the exact proba- bility associated with the target output. For a valuation v, let U(v) =k ∈ [1,m]| v[k] = ⋆ denote the set of unassigned variables. We define the comple- tion probability of output o under v as p θ (o| i;v) := X v ′ ∈tot(v) S(v ′ [1],...,v ′ [m])=o Y k∈U(v) π θ,k (v ′ [k]| i). Thus, the values fixed byvare held fixed, while the remaining variables are independently distributed according to their input- dependent distributions. These weights define a probability distribution overtot(v), since X v ′ ∈tot(v) Y k∈U(v) π θ,k (v ′ [k]| i) = Y k∈U(v) X y∈V k π θ,k (y | i) = 1. For the empty valuationv ∅ , this definition coincides with Eq. (1): p θ (o| i;v ∅ ) = p θ (o| i). Theorem 2. For any inputi∈ I, outputo∈ O, valid oracle O S for the symbolic function S, and valuation v ∈V , DPNL(i,o,v,O S ) = p θ (o| i;v). In particular, DPNL(i,o,v ∅ ,O S ) = p θ (o| i). Proof. We proceed by induction on the number of unassigned variables in v: n(v) =|U(v)|. Base case.Assume thatn(v) = 0. Thenvis a total valuation and tot(v) =v. SinceO S is a valid oracle, it always decides total valuations. Therefore, O S (v,o) = 1 if S(v[1],...,v[m]) = o, 0 otherwise. By definition of the completion probability, and using the convention that an empty product equals 1, p θ (o| i;v) = 1 if S(v[1],...,v[m]) = o, 0 otherwise. Hence DPNL returns exactly p θ (o| i;v), and terminates. Induction step.Assume the theorem holds for every valua- tion with at mostnunassigned variables. Consider a valuation v with n(v) = n + 1. There are three possible cases depending on the oracle out- put. CaseO S (v,o) = 1. By validity of the oracle, every total refinement of v produces the output o. Hence, p θ (o| i;v) = X v ′ ∈tot(v) Y k∈U(v) π θ,k (v ′ [k]| i). Sincetot(v)contains exactly all combinations of values of the variables indexed byU(v), and eachπ θ,k (·| i)is a probability distribution, p θ (o| i;v) = Y k∈U(v) X y∈V k π θ,k (y | i) = 1. DPNL returns 1, which is therefore the correct value. CaseO S (v,o) = 0. By validity of the oracle, no total re- finement ofvproduces the outputo. The sum defining the completion probability therefore contains no satisfying refine- ment, and p θ (o| i;v) = 0. DPNL returns 0, which is the correct value. CaseO S (v,o) = ⋆. In this case, DPNL selects an indexk such thatv[k] = ⋆. The regions represented by the refinements v v[k]←y , for y ∈ V k , partition the region represented by v. For each y ∈ V k , U(v v[k]←y ) = U(v)\k, and every v ′ ∈ tot(v v[k]←y ) satisfies v ′ [k] = y. Hence, Y j∈U(v) π θ,j (v ′ [j]| i) = π θ,k (y | i) Y j∈U(v v[k]←y ) π θ,j (v ′ [j]| i). Therefore, partitioning the total refinements ofvaccording to the value assigned to X k (i) gives p θ (o| i;v) = X y∈V k π θ,k (y | i)p θ (o| i;v v[k]←y ). For everyy ∈ V k , the valuationv v[k]←y contains one fewer unassigned variable: n(v v[k]←y ) = n(v)− 1. Hence, by the induction hypothesis, DPNL(i,o,v v[k]←y ,O S ) = p θ (o| i;v v[k]←y ), and each recursive call terminates. Since Pr(X k (i) = y) = π θ,k (y | i), the recursive computation performed by DPNL returns X y∈V k Pr(X k (i) = y) DPNL(i,o,v v[k]←y ,O S ) = X y∈V k π θ,k (y | i)p θ (o| i;v v[k]←y ) = p θ (o| i;v). SinceV k is finite and every recursive call decreases the num- ber of unassigned variables, the current call also terminates. Finally, for the empty valuation v ∅ , p θ (o| i;v ∅ ) = p θ (o| i), and therefore DPNL(i,o,v ∅ ,O S ) = p θ (o| i). B Logic Oracle Construction B.1 Logic-based characterization of symbolic functions We consider symbolic functions over finite domains that can be characterized by logical reasoning. For each variableX k with finite domainV k , we associate each possible valuex ∈ V k with a logical formulaφ k,x expressing thatX k = x. We assume that, for every k, the formulas φ k,x | x∈ V k are mutually exclusive and exhaustive. For each output valueo∈ O, letφ o denote a logical formula expressing that the symbolic function produces output o. LetTbe a logical theory. We assume that the symbolic function S satisfies: S(x 1 ,...,x m ) = o ⇐⇒ T ∪φ k,x k | k ∈ [1,m]⊢ φ o . In other words, once all variables are assigned, the output of the symbolic function is determined by logical entailment. For a valuation v, we define the theory induced by v as T v = T ∪φ k,v[k] | v[k]̸= ⋆. Hence, a partial valuation corresponds to a partially instan- tiated logical theory. B.2 Logic oracle The logic oracle uses a decision procedure for the underlying logic to determine whether the current partial valuation is sufficient to decide the target output. Algorithm 3: Logic oracle Require: valuation v, target output o Ensure: oracle output if T v ⊢¬φ o then r ← 0 else if T v ⊢ φ o then r ← 1 else r ← ⋆ end if return r B.3 Validity and completeness Theorem 3. Assume that the logical consequence relation is sound. Then Algorithm 3 defines a valid oracle for S. Proof. Let v be a valuation. Assume first that the oracle returns1for target outputo. Then T v ⊢ φ o . Letv ′ ∈ tot(v)be any total refinement ofv. By definition of refinement, every formula induced byvis also induced by v ′ , and therefore T v ⊆ T v ′ . By monotonicity of logical entailment, T v ′ ⊢ φ o . Using the characterization of S, we obtain S(v ′ [1],...,v ′ [m]) = o. Hence every total refinement of v produces output o. Now assume that the oracle returns 0. Then T v ⊢¬φ o . For any total refinement v ′ ∈ tot(v), we again have T v ⊆ T v ′ , and therefore T v ′ ⊢¬φ o . Consequently, S(v ′ [1],...,v ′ [m])̸= o. Hence no total refinement of v produces output o. Therefore the oracle is valid. Theorem 4. Assume that the logical consequence relation is sound and complete. Then Algorithm 3 defines a complete oracle for S. Proof. Assume that the oracle returns ⋆ for a valuation v and output o. Then T v ⊬ φ o and T v ⊬¬φ o . By completeness of the logical consequence relation, there exists a model I 1 of T v such that I 1 |= φ o , and a model I 0 of T v such that I 0 |=¬φ o . For j ∈0, 1, define a valuation v j by v j [k] = x iff I j |= φ k,x . BecauseI j satisfiesT v , all values fixed byvare preserved. Therefore, v 0 ,v 1 ∈ tot(v). Moreover, by the characterization of S, S(v 1 [1],...,v 1 [m]) = o and S(v 0 [1],...,v 0 [m])̸= o. Thus both a refinement producingoand a refinement not producing o exist in the region represented by v. Therefore returning⋆is correct, and the oracle is complete. C Application to DeepProbLog C.1 DeepProbLog as a logic-based symbolic function DeepProbLog provides a natural instance of the logic-based symbolic functions considered in Section B. A DeepProbLog program combines deterministic logic rules with neural predicates. The outcomes of neural predi- cates define the intermediate variablesX 1 ,...,X m , while the deterministic logic program defines the symbolic function S. Consider a DeepProbLog queryqand letTdenote the deterministic part of the program. For a complete valuation v, letR v denote the set of neural facts corresponding to the values fixed by v. The symbolic function associated with the query is defined as S(v[1],...,v[m]) = 1 ⇐⇒ T ∪ R v ⊢ q. Therefore, DeepProbLog fits the logic-based characteriza- tion introduced in Section B, where the formulas associated with the values of neural predicates correspond to the possible neural facts. C.2 DeepProbLog oracle For DeepProbLog programs without negation, the logic oracle can be implemented using the underlying Prolog inference procedure. For the Boolean query setting of DeepProbLog, we consider O =0, 1 and focus on the target output o = 1. For a partial valuationv, letR v denote the neural facts fixed byv. LetR ⋆ v denote the optimistic completion ofR v , obtained by assuming all unassigned predicates are true. The oracle is defined as follows: Algorithm 4: DeepProbLog oracle Require: valuation v if T ∪ R v ⊢ q then return 1 else if T ∪ R ⋆ v ⊬ q then return 0 else return ⋆ end if The oracle is valid because DeepProbLog programs without negation are monotonic: adding additional neural facts cannot invalidate an existing proof. The first case certifies that every completion of the current valuation produces the query, while the second case certifies that no completion can produce it. Otherwise, further explo- ration is required. C.3 Representing probabilistic choices DeepProbLog represents probabilistic choices through mu- tually exclusive outcomes, rather than independent Boolean facts. For a categorical variable with outcomesx 1 ,...,x n , di- rectly introducing independent probabilistic facts would incor- rectly allow several outcomes to hold simultaneously. Deep- ProbLog therefore uses annotated disjunctions (ADs) and neu- ral annotated disjunctions (nADs) to represent such choices. This transformation introduces auxiliary logical variables and rules. Consequently, the logical representation used for provenance-based inference may become substantially larger as the number of probabilistic choices increases. DPNL does not require this complete logical representation to be materialized: its oracle-guided exploration can reason directly over regions of the assignment space. C.4 Example: Graph reachability Consider a probabilistic directed graph where each potential edge(e i ,e j )is represented by a neural predicateedge(e i ,e j ). The query asks whether a target node is reachable from a source node. The deterministic rules can be written as reachable(e 1 ). reachable(Y )← reachable(X),edge(X,Y ). The corresponding symbolic function returns1when the query reachable(e N ) can be proved. A provenance-based approach constructs a logical formula representing all possible paths between the source and target nodes. In a dense graph, the number of such paths can grow exponentially with the number of nodes. In contrast, the DeepProbLog oracle can reason directly over partial valuations. For example, if a reachable path is already established by the currently assigned edges, the region can immediately be accepted without enumerating the remain- ing edges. Conversely, if reachability is impossible even when all unknown edges are assumed present, the whole region can be rejected. This illustrates how DPNL can exploit logical reasoning directly during inference instead of first materializing the com- plete provenance. D Variable Selection Heuristics The choice of the next variable to refine determines the struc- ture of the exploration tree and can substantially affect the number of recursive calls required by DPNL. Correctness and termination do not depend on this choice, as every branching step reduces the number of unassigned vari- ables. However, problem-specific heuristics may significantly improve pruning efficiency. When the oracle is complete, a partial valuationvreturn- ing⋆indicates that the region represented byvcontains both successful and unsuccessful total refinements. In principle, a complete oracle may provide information about refinements leading to each outcome. This suggests a branching heuris- tic that prioritizes variables that are likely to separate such refinements. More precisely, if the oracle can provide witness refinements v + ,v − ∈ tot(v) such that S(v + [1],...,v + [m]) = o and S(v − [1],...,v − [m])̸= o, one may prioritize variables X k for which v + [k]̸= v − [k]. Such variables directly distinguish regions that respec- tively contribute to or exclude the target output and may lead to smaller exploration trees. Designing effective variable- selection heuristics based on oracle information is an interest- ing direction for future work. E Experimental Details E.1 Hardware The symbolic experiments are executed on an Apple Mac- Book Pro (M1 Max) with 64GB RAM. The neurosymbolic experiments on Leaf and MNIST-N-SUM are executed on a CPU-only Dell Precision 7960 workstation with an Intel Xeon w5-3425 processor (12 cores, 24 threads, 3.2 GHz base and 4.6 GHz turbo frequency) and 512GB RAM. The Visual Sudoku experiments are executed on a server with two Intel Xeon Silver 4114 processors (10 cores and 20 threads each, 2.2 GHz base and 3.0 GHz turbo frequency), 187GB RAM and an NVIDIA Quadro P5000 GPU. E.2 Implementation Details The DPNL framework is implemented in a modular and ex- tensible Python codebase centered around symbolic reasoning with probabilistic inputs. It introduces a unified abstraction for defining symbolic functions, managing structured probabilis- tic 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 Symbolicclass, an abstract interface for symbolic functions S, and theInputclass, which represents structured inputs composed of random variables (RndVar). EachRndVarhas a discrete domain and a probability distribution, and may be left undefined (unknown) until instantiated during inference. Oracle Mechanism.DPNL oracles implement theOracle interface, which answers whether§v = ois always true, al- ways false, or unresolved for a given (possibly partial) valua- tion v and output o. Multiple oracle variants are supported: •Enumeration Oracle: A naive baseline that returns unknownif any variable inIis undefined. Useful as a reference implementation for exact inference. •Basic Oracle: Executes§vand traps access to undefined variables to detect when the computation depends on an unassigned 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 ora- cles, falling back as needed to obtain stronger pruning or efficiency. Recursive Inference. ThePNLProblemclass wraps a symbolic function and input. It computes the probability that S(v) = ovia 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. TheSATLogicclass encodes formulas us- ing literals, clauses, and conjunctions, and interfaces with a SAT solver (e.g., MiniSAT). Symbolic functions defined in SAT are specified through theSATLogicSymbolicinter- face, which supports variable declarations, clause generation, and relational constraints over domains to easily defineS. This enables symbolic functions to be expressed and reasoned about at the propositional level, improving pruning and solver per- formance. This experimental instantiation is only one possible implementation of the generic logic oracle interface. E.3 Hyperparameters. The hyperparameters used in the experiments are summarized in Table 6. 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. We enforce computational timeout: 24h forN = 2, 3, 4and 48h forN = 8. For Visual Sudoku we enforce a computational timeout of 48h. 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 (n.Conv2d(1, 6, 5)and n.Conv2d(6, 16, 5),) followed by Max pooling and Relu activation (n.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. E.4 Baselines To obtain the results with the baselines for the MNIST-N-Sum task, 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 For the Leaf task, all baselines were reproduced with the code from the ISED repository: https://github.com/ alaiasolkobreslin/ISED. A-Nesi. We conduct five independent runs with different random seeds for each experiment. Table 7 shows the hyperpa- rameters used for configurations used for the different variants of A-Nesi [ van Krieken et al., 2023 ] . KeyExplainPredict OnlyPrune amtsamples600600600 Kbeliefs250025002500 nrmlr0.0010.0010.001 perceptionlr0.0010.0010.001 dirichletlr0.010.010.01 dirichletiters505050 dirichletinit0.10.10.1 dirichletL2900000900000900000 nrmlossmsemsemse hiddensize800800800 layers333 pruneFalseFalseTrue predictonlyFalseTrueFalse usepriorTrueTrueTrue Table 7: Table of hyperparameters of A-Nesi for the variants explain, predict only, and prune. 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,4in order to use it as baseline. The logic programs are given in Listing 1. We use Scallop with exact as well as with ap- proximate reasoning. For approximate reasoning of Scallop we choose thediff-top-k-proofsemiring withk = 3, as recommended in [ Huang et al., 2021 ] . To investigate the performance of Scallop with exact reasoning, we choosek in a way that the logic provenance formula is in any case smalle thankand is consequently not pruned. In particular, we choose k for every MNIST-N-SUM task depending on N: k = 2 2·10·N . This way,krepresents an upper bound for the length of the logical provenance formula. DPLA ∗ .DPLA ∗ employs heuristics to estimate the proba- bility of partial proofs to search for the best proof. Here, we use the geometric mean heuristic [ Manhaeve et al., 2021b ] . 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 Engine t (s)εEpochs Batch Pretrain Test t (s) Leaf –exact–504– MNIST-N -SUM (basic oracle) N ∈2, 3, 4 exact–12– N = 2anytime0.006–12–1 N = 3anytime0.025–12–1 N = 4anytime0.25–12–1 N = 8anytime0.25–1016–100 N = 2ε-approx.–0.512– N ∈3, 4 ε-approx.–0.412– Visual Sudoku (Sudoku oracle) N = 4exact–101– N = 4anytime0.08–101– N = 4ε-approx.–10 −6 101– N = 9anytime0.25–25164 ep.200 Table 6: Hyperparameters for the neuro-symbolic experiments Leaf, MNIST-N-Sum and Vsudoku. All runs use the Adam optimiser with learning rate1e−3(1e−4for Leaf), and CPU-only execution.tis the per-sample symbolic timeout for Anytime ApproxDPNL andεthe error budget. For Visual Sudoku N9 and MNIST N8, a higher timeout at inference is used. Classifier pretraining uses batch size32and learning rate 1e−3. The total training timeout is24–48h for MNIST-N-SUM,24h (exact) and5h (anytime,ε-approx.) for Visual SudokuN = 4, and48h for N = 9. ) :- digit_5(a), digit_6(b), digit_7(c ), digit_8(d)") Listing 1: Rules used in Scallop for the MNIST-N-SUM task