KLay: Accelerating Arithmetic Circuits for Neurosymbolic AI
Authors: Jaron Maene
Vincent Derkinderen
Pedro Zuidberg Dos Martires
Venue: ICLR 2025 Poster (2025)
Keywords: Neurosymbolic AI
Arithmetic Circuits
Sparse Inference
Primary area: neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
TL;DR: We speed-up neurosymbolic AI by evaluating arithmetic circuits efficiently on the GPU.

Abstract: A popular approach to neurosymbolic AI involves mapping logic formulas to arithmetic circuits (computation graphs consisting of sums and products) and passing the outputs of a neural network through these circuits. This approach enforces symbolic constraints onto a neural network in a principled and end-to-end differentiable way. Unfortunately, arithmetic circuits are challenging to run on modern tensor accelerators as they exhibit a high degree of irregular sparsity. To address this limitation, we introduce knowledge layers (KLay), a new data structure to represent arithmetic circuits that can be efficiently parallelized on GPUs. Moreover, we contribute two algorithms used in the translation of traditional circuit representations to KLay and a further algorithm that exploits parallelization opportunities during circuit evaluations. We empirically show that KLay achieves speedups of multiple orders of magnitude over the state of the art, thereby paving the way towards scaling neurosymbolic AI to larger real-world applications.

Published as a conference paper at ICLR 2025
KLAY: ACCELERATING ARITHMETIC CIRCUITS FOR NEUROSYMBOLIC AI
Jaron Maene & Vincent Derkinderen
Department of Computer Science
KU Leuven
Leuven, Belgium
{jaron. maene, vincent www.ceett.de.iiiddeeeeeeee.....e
Pedro Zuidberg Dos Martires
Centre for Applied Autonomous Sensor Systems
Örebro University
Örebro, Sweden
pedro. zui aub
ABSTRACT
A popular approach to neurosymbolic AI involves mapping logic formulas arithmetic circuits (computation graphs consisting of sums and products) and passing the outputs of neural network through these circuits. This approach enforces symbolic constraints onto neural network in a principled and end-to- end differentiable way. Unfortunately, arithmetic circuits are challenging to run on modern tensor accelerators as they exhibit high degree of irregular sparsity. To address this limitation, we introduce knowledge layers (KLAY), a new data struc- ture represent arithmetic circuits that can be efficiently parallelized Moreover, we contribute two algorithms used in the translation of traditional cir- cuit representations KLAY and a further algorithm that exploits parallelization opportunities during circuit evaluations. We empirically show that KLAY achieves speedups of multiple orders of magnitude over the state of the art, thereby paving the way towards scaling neurosymbolic AI to larger real-world applications.
GPUs.
INTRODUCTION
continues to grow the integration of sym- bolic reasoning and neural networks has been shown to increase reasoning capabilities (Yi et al.]
Interest in neurosymbolic AI (Hitzler & Sarker 2022)
2018 Trinh al. 2024), safety (Yang et al. 2023). controllability (Jiao et al., 2024). and inter- pretability (Koh et al. 2020). Furthermore. neurosymbolic methods often require less data by allowing richer and more explicit set of priors (Diligenti et 2017 Manhaeve et al. 2018).
However, as the computational structure of many neurosymbolic models is partially dense (in its neu- ral component) and partially sparse (in its symbolic component), efficiently learning neurosymbolic models still presents challenge (Wan et al. 2024). So far, the symbolic components of these neurosymbolic models have struggled fully exploit the potential of modern GPUs or TPUs.
Our work focuses on a particular flavor of neurosymbolic AI, pioncered by Xu et al. (2018) and Manhaeve et al.) (2018), which performs probabilistic inference on the outputs of neural network. This is achieved by encoding the symbolic knowledge using arithmetic circuits. While arithmetic circuits are end-to-end differentiable, they also pose certain challenges. circuits are ill-suited to be evaluated in terms of dense tensor operations due to their high degree of irregular sparsity. In this work, we address the challenge of optimizing neurosymbolic architectures to efficiently leverage available widely available hardware. To this end, we present KLAY: data structure representing arithmetic circuits as knowledge layers which can exploit the parallel compute present in modern GPUs or TPUs.
particular, arithmetic

---

Published as a conference paper at ICLR 2025
The main advantage of KLAY is that it reduces arithmetic circuit evaluations to index and scatter operations operations already present in popular tensor libraries. This allows for the embarrass- ingly parallel nature of these knowledge layers to be harnessed. Importantly and in contrast to alternative approaches that speed up sparse neurosymbolic computation graphs (Dadu et al., 2019) Liu et al., 2024), we forego the need for custom hardware-specific implementations. This makes KLAY completely agnostic towards the underlying hardware. By leveraging the compiler stacks of open-source tensor libraries, KLAY can furthermore considerably outperform existing hand-written CUDA kernels.
ARITHMETIC CIRCUITS AND NEUROSYMBOLIC AI
The symbolic knowledge in neurosymbolic AI is commonly specified Boolean logic. Boolean circuits are a compact representation of Boolean logic using directed acyelic graphs (Darwiche) 2021]. More specifically, the leaves in Boolean circuits correspond to Boolean variables (or their negation), while inner nodes either A-gates V-gates. We make the usual assumption that Boolean circuits do not contain negation, known as negation normal form (NNF). Figntaina an example of a Boolean circuit. A circuit can be evaluated for a set of inputs by simple post-order traversal of the graph, meaning children get evaluated before their parents. More formally, the value (n) of node n is defined
L v(n) [{ Nosc, v(c) ( v(c)
if n is leaf node, if is A-gate,
if n is V-gate.
We write l, for the Boolean input value of the leaf node n and Cn for the set of children of an inner node n. The evaluation of circuit is function B- which maps the Boolean inputs of the leaves to the value of the root node.
In order to render Boolean circuits useful in the context of neurosymbolic AI, we first need to perform a so-called knowledge compilation step (Darwiche & Marquis, 2002). This compilation step transforms an NNF circuit into deterministic decomposable negation normal form (d-DNNF). Determinism (Darwiche) 2001b) and decomposabiliry (Darwiche) 2001a) are two properties that guarantee certain computations can be performed tractably, such as finding the number of satisfying assignments. We refer the reader to Vergari et al. (202T) for an in-depth discussion on tractable com- putations on circuits. Figure Tb contains the d-DNNF circuit resulting from knowledge-compiling
the circuit in Figure Ia
The important advantage of d-DNNF circuits over general NNF circuits is that they allow linear time probabilistic inference. Assume first that the Boolean variables are not deterministic anymore but constitute Bernoulli random variables. We can then compute the probability of the d-DNNF circuit evaluating to true under the input distribution by labeling the leaves of the circuit with the probabilities of the Boolean variables and replacing A- and V-gates with x and + operations, re- spectively. The resulting circuit also called an arithmetic eircuit (Darwiche 2003) and is displayed in Figure Ic
While probabilistic inference on d-DNNF circuits has linear time complexity, transforming NNF circuit into d-DNNF is #P-hard (Valiant 1979). However, once the d-DNNF structure is obtained we can re-evaluate the circuit with different probabilities for the Boolean variables in the leaves. This approach has been very successful in probabilistic inference for a variety of models such as Bayesian networks (Chavira & Darwiche 2008) and more general probabilistic programs (Fierens) et al. 2015).
This compile once and evaluate often paradigm has also gained traction in neurosymbolic sys- tems (Manhaeve et al. 2018 Ahmed et al.] 2022b De Smet et al. (023). The high-level idea behind these approaches is to compile the symbolic knowledge once into an arithmetic circuit and let a neu- ral network predict the probabilities to be fed into the arithmetic circuit. Given that the arithmetic circuit consists only of sum and product operations, the resulting computation graph (neural network arithmetic circuit) is end-to-end differentiable and the parameters can be optimized using standard gradient descent methods. Furthermore, as gradient descent is an iterative method, the circuit (and its gradient) needs to be evaluated repeatedly. This yields convenient return investment for the
2

---

Published as a conference paper at ICLR 2025
b
a
C
d
p-o
pod
Pe
Pd
(a) NNF circuit.
(b) d-DNNF circuit.
(c) Arithmetic circuit.
Figure 1: Example of (a) Boolean circuit, (b) its d-DNNF version, and (c) the corresponding arithmetic circuit. The arithmetic circuit replaces Boolean variables with their probabilities. Con- sequently, the arithmetic circuit computes the probability of the underlying Boolean circuit being satisfied. In a neurosymbolic setting, the input probabilities are predicted by a neural network.
initial expensive knowledge compilation step, which now amortizes over multiple evaluations. Ap- pendix D eexplains in more detail how neural networks and circuits can be used together simple example.
As discussed in the introduction, arithmetic circuits currently hinder the efficient application of neurosymbolic methods as these circuits are not well-suited to evaluated as parallel tensor oper- ations. As a matter of fact, the standard way to evaluate arithmetic circuit in neurosymbolic context is to naively evaluate every node one by one (Manhaeve et al. 2018 Ahmed et al. 2022a bb) using naive traversal of the arithmetic circuit. Although this naive traversal of the circuit allows for a certain degree of data parallelism, fails to fully utilize the capacity of modern GPUs. Con- sequently, many existing frameworks in practice just evaluate the entire computation graph on the CPU (Manhaeve et al. 2018 Ahmed et al. 2022b).
3 LAYERIZING CIRCUITS
In this section, we show how map a d-DNNF circuit to our layerized KLAY representation. Af- terward, in Section 4 discuss how the resulting KLAY representation can be run efficiently GPUs. Although our exposition focuses on d-DNNF circuits, it is more generally applicable to NNF circuits, meaning KLAY could also be of interest neurosymbolic systems based on, e.g. fuzzy logic Badreddine et al. 2022 or grammars (Winters et al. 2022).
3.1 FROM LINKED NODES TOWARDS LAYERS
In order to parallelize d-DNNF circuit, group the nodes into sets of nodes that be evaluated in parallel. We dub these groups layers reminiscent of layers in neural networks. Concretely, for each node in circuit C' we compute its height in the circuit hns and nodes with the same height are assigned to the same layer.
00
if n is a leaf,
142 (n E C | hr i] where
hn
max he + otherwise.
Here, we use C, to denote the set of children of node Note that the height of all nodes can be efficiently evaluated single post-order circuit traversal. The initial layer, Lo. comprises all leaf nodes, while the last layer comprises the root node.
Without loss of generality, we can assume that V-gates only have A-gates as children and that A- gates have either V-gates or Icaf nodes children (Choi et al. (020).. This implics that A- and V-gates appear an alternating fashion throughout the circuit, which can be observed in Figure lb and that all nodes in the same layer have the same type.
nodes are assigned to layers based on their height ht, the child of a node can be in any of the previous layers. However, to transform the circuit evaluation into sequence of parallel operations, is more convenient all children are in the immediately preceding layer. In such a structure, the next layer can be computed solely using the current layer.

---

Published as a conference paper at ICLR 2025
layer La
layer La
layer L
layer L1
C
c
d
a
layer Lo
Figure 2: A layered version of the d-DNNF in Figure lb Dashed nodes indicate nodes that are not present in the original d-DNNF and which are introduced during the layerization of the circuit.
We obtain this layer-by-layer structure by introducing additional unary nodes. Whenever node Ls., has child e in a non-immediately preceding layer Lt.,, i.e. he - 1 < hn, we introduce chain of unary nodes, one per layer between Ln. and Ln.,, to connect n to c via these unary nodes. This is illustrated in Figure 2 where the newly introduced nodes are indicated by dashed circles. Note that the type of a unary node (V or A) is irrelevant and chosen to satisfy the assumption of alternating node types. Algorithm 2 in Appendix C summarizes this layerization in pseudo-code.
3.2 MULTI-ROOTED CIRCUITS AND NODE DEDUPLICATION
Suppose now that we have multiple circuits over a (partially) shared set of variables. A set of M circuits effectively computes a Boolean function f NB - B Such M -idimensionnal circuits also called multi-rooted circuits and are rather common in the standard neurosymbolic setting. Indeed, unless all data has the same symbolic knowledge, batched training or inference requires multi-rooted circuits. For instance, the widely-known MNIST addition problem (Manhaeve al., 2018) can be solved using a multi-rooted arithmetic circuit with 19 roots, as it has 19 different possible outputs.
If all M circuits comprising the multi-rooted circuit have already been layerized according to Sec- tion 3.1 again have that nodes at the same height in different circuits are of the same type. We can hence simply combine the layers of the different circuits to further exploit parallelization. Additionally, different circuits might share equivalent sub-circuits amongst each other. By correctly identifying and merging shared nodes, we avoid redundant computations. Figure 3 gives an example of multi-rooted d-DNNF circuit with shared nodes.
To merge all duplicate nodes, we need an efficient way to identify these nodes. We show that this is possible in linear time.
Theorem 1.
Given set of circuits, all identical sub-cireuits can be identified in linear expected time complexity in the total number of edges in the circuits.
The proof is included Appendix A. For canonical circuits, such as SDDs with the same variable tred this result is strengthened from syntactically identical sub-circuits semantic equivalence. We realize Theorem] I [using Merkle hashes (Merkle 1987). That is, we associate a hash hash(n) with every node For each internal node, we combine the hashes of the children using permutation invariant function.
recursive fashion. For each leaf node, we hash the associated (negated) variable.
if n is leaf. =iDcsc mix miixhha(((ss((e)) otherwise.
( /mixxhasise mnixxhash((x))
hash(n)
(3)
Here, L, is unique identifier for the (negated) variable of the leaf node b is a permutation- invariant operation such as XOR, and mix_hash a function that disperses the bits of the hash.
We can now merge all equivalent nodes in multi-rooted circuit by computing the node hashes in bottom-up pass and merging all nodes with the same hash, e.g. by storing the nodes in a hash map.
A sentential decision diagram (SDD) is a subclass of d-DNNF circuits that canonical given variable tree. We refer to Darwiche (201)) for more details.
4

---

Published as a conference paper at ICLR 2025
A
-a
b
- C
(a) Layered d-DNNF circuit.
(h) Layered multi-rooted circuit.
Figure contains a layered d-DNNF circuit over the variables a, d, and e. The dashed circles indicate again nodes introduced during the layerization process. (b) illustrates a multi-rooted circuit where the upper left node computes the circuit from Figure[aand where the upper right node computes the circuit from Figure a.. Note how nodes at the same height in the multi-rooted circuit are of the same type and how the sub-circuit colored in orange used compute both root nodes.
The efficient deduplication via Merkle hashes not only useful the context of merging single- rooted circuits; duplicate nodes may also occur within single circuit. This can, for instance, happen when the circuit is an SDD Another source of duplicate nodes stems from the layerization proce- dure in Section 3.1 Concretely, the connection of node
higher-up node through chain of unary nodes results in equivalent chains if node n has multiple higher-up parent nodes. Using Merkle hashes resolves this issue as it automatically merges multiple equivalent node chains, limiting the overhead of adding new nodes.
Lastly, we make sure that all circuits have the same height by artificially extending circuit with unary nodes at the root if necessary. This results in the last layer of our multi-rooted circuit contain- ing the root nodes of every added circuit.
4 TENSORIZING LAYERED CIRCUITS
In the previous section, we organized d-DNNF circuits into layers by assigning each node n in the circuit a height lgg. We also avoided duplicate nodes by computing a unique Merkle hash hash(n) for each node. We proceed in this section with mapping layered linked nodes a layered computation graph where layers are evaluated sequentially and computations within a layer can be parallelized.
To this end, we make simple, yet powerful, observation: the current layer can be computed from the output the previous layer by only using indexing and aggregation. see this, we first impose an arbitrary order the nodes within each layer. This means a layer Lę as a vector N,. For our running example, we simply pick the order already insinuated by the graphical representation in Figure except for the input layer where we order lexicographically: No PP. P ra Pb, P p-b. Pe, P-ex Pd. Pdd T.
write the values of all nodes in
Now, in order to compute N; from N between N₁-1 and N, S, contains the index of the input node, while R3 contains the index of the output node. We exemplify this for single layer in Figure 4 By imposing order the input nodes and by providing the set of vectors (S....S, Sr.} arithmetic circuit. This means that we can use these vectors instead of linked node representation to evaluate the circuit.
two vectors of indices: S, and R, For each edge
and ...... Rr). we entirely characterize an
To compute N,, we first select relevant values from N using as index S,, giving E; N W [Si].
The vector E essentially contains the values of all the edges between N, and N Next, we need correctly segment the edges E, and aggregate the individual segments either by using sums or products, depending on the layer. This is done using Ry: all elements with the same index in R
An SDD node represents an V-gate, and is defined set of tuples each representing A-gates. This structure typically does not share tuples, and thus does not automatically duplicate A-gates.
5

---

Published as a conference paper at ICLR 2025
X
X
node values N
aggregation indices R edge indices S
3
7
node values No
Pa
p-a
pb
p-b
Pc
p-o
Pd
p-d
Figure 4: The evaluation of the first layer in Figure Ic as an indexing and aggregation operation. The symbols No and N denote the node values layer Lo and Lı respectively. First, index in No using the edge indices S₁, effectively creating a vector with the values all edges between No and 1 Next, the aggregation indices R2 determine what edges are reduced together. As result we obtain the node values 1 scatter (N, [ R1 reduce = 'product').
are reduced together. Fortunately, such segment-reduce operations are implemented as primitives in various tensor libraries such Jax, TensorFlow, or PyTorch (Abadi et al.) 2015 Paszke al., 2019 Bradbury et al. 2018). In Figure 4 these segments are indicated with alternating colors.
Algorithm contains pseudo-code for the layerwise circuit evaluations, where we use the common scatter function to segment and aggregate the E; vectors. In Figure we show the full tensorized circuit representation of the arithmetic circuit in Figure [c] which corresponds to the computation graph induced by Algorithm]] [ Although we depict the edge vectors E; in Figure 5 we stress that these do not need to be represented explicitly because modern tensor libraries in practice fuse the indexing and segmentation operations together.
Algorithm 1: KLay Forward Evaluation
Input: No, selection indices S S Sy. ......,,...
reduction indices R1, R2...., R
for I <- 1 to do
E - N [
it mod 2 0 then
N; + scatter( (E, Ry, reduce='sum')
else
N - scatter(E, E, Ri, reduce= reduce='product") productt);;
end
end
return Ny;
Finally, we note that in practice arithmetic circuits are usually evaluated in the logarithmic domain for numerical stability. This means that the reduction uses logsumexp and sum operations instead of the sum and product, respectively. We provide the pseudo-code in Algorithm 4 in Appendix C More generally, any pair of operations that forms semiring may be used to evaluate the circuit (Kimmig et al.] (017). as long as the semiring operations can be expressed as reduction operations in the tensor library.
RELATED WORK
The closest related work is the arithmetic circuit layerization present in JUICE (Dang et al.) 2021
Similar to our circuit layerization scheme, JUICE takes a Boolean circuit and maps it to a set of layers that can be evaluated sequentially, although not layer per layer. To this end, Dang et al. (2021) implemented a custom SIMD implementation for the CPU and custom CUDA kernels for the GPU. This is in contrast KLAY where reduce circuit evaluations to sequence of index and scatter- reduce operations, which are already efficiently implemented the modern deep learning stack. In experiments, show that KLAY dramatically outperforms JUICE in terms of time

---

Published as a conference paper at ICLR 2025
node values N
edge values E,
X
X
node values N3
edge values E3
node values N
edge values E node values N edge values E
X
X
X
X
node values No
Pa
P ia
pb
pbb b
Pe
p
ic
Pd
Figure 5: Tensorized KLAY representation of the arithmetic circuit in Figure Ic
We depict the
segments of the edge vectors E, with alternating colors.
CPU and more importantly on GPU as well. Noteworthy here is that our experimental evaluation also shows that JUICE's GPU implementation slower than their CPU implementation hinting at missed parallelization opportunities.
The difficulty of running arithmetic circuits on GPUs was also pointed out by [Shah al. (2020) 2021}. While [Shah et al. (2020; (021)) focused on developing hardware accelerators for arithmetic circuits, they also implemented custom eircuit evaluations exploiting to a certain degree SIMD structions and GPU parallelization. They found that CPU circuit evaluations outperformed the GPU implementations. [hahh et al. (2020) concluded that arithmetic circuits were simply too sparse to be run efficiently on GPUs. By layerizing arithmetic circuits and interpreting the product and sum layers as indexing and seatter-reduce operations, we are able to refute this claim. We provide exper- imental evidence for this in Section 6
Notable is also the work of Vasimuddin et al. (2018), who proposed an efficient CPU implementation for evaluating arithmetic circuits deployed multiple CPU cores. They deemed efficient GPU implementation to be impractical due to the high demands on memory bandwidth. We can again refute this claim.
Arithmetic circuits are closely related to the model class of probabilistic circuits (ergari et al., 2021. The main difference is that the sum units for the latter are parameterized using mixture weights, while the former does not contain such weights. In order to run probabilistic circuits efficiently on the GPU, implementations usually rely on casting circuit evaluations dense matrix- vector product (Peharz et al. [2020b Galindez Olascoaga et al. 2019 Mari et al.) 2023 Sommer al. (02T). This idea has recently been generalized by Liu al. (202)) who allow for presence of block-sparsity in the matrix that encodes layer. By exploiting this sparsity via custom kernels, they widened the class probabilistic circuits that can be run efficiently on GPUs. Nevertheless, probabilistic circuits are usually far more dense than arithmetic circuits that compiled from logical theory. Unfortunately, this prevents the techniques developed for probabilistic circuits to be effective in the context of arithmetic circuits. Similarly, having densely parameterized sum nodes also limits the relevance of techniques developed for arithmetic circuits for probabilistic circuits, e.g. the indexing and segmenting scheme of LLAY circuit evaluations.

---

Published as a conference paper at ICLR 2025
Besides algorithmic advances, specialized hardware solutions have also been proposed to deal with the irregularity of the computational graph of an arithmetic circuit (Dadu et al. 2019: Shah et al. 2020 202I). However, these approaches have the drawback that they would require the purchase of non-commoditized hardware. While this could partially be remedied by the use of FPGAs, as done by Sommer al. (2018); (ebee et al. (2022); Choi al. (2023). any custom hardware retains a communication overhead. Specifically, in the context of neurosymbolic AI, one needs to pass the output of a neural network an arithmetic circuit. If the neural net and the circuit on two different devices, e.g. GPU and an FPGA, the latency of data transfer can counteract gains in evaluation speed.
6 EXPERIMENTAL EVALUATION
We implement KLAY Python library supporting two popular tensor libraries: PyTorch and Jax. We evaluate the runtime performance KLAY on several synthetic benchmarks and neurosymbolic experiments. All experiments were conducted the same machine, which has an NVIDIA GeForce RTX 4090 as GPU and an Intel 19-13900K as CPU.
6.1 SYNTHETIC BENCHMARKS
We first consider the performance of KLAY on set of synthetic circuits, by randomly generating logical formulas in 3-CNF. We compile the 3-CNF formulas into d-DNNF circuits, more specifically SDD circuits, using the PySDD library |] CNF, we vary the size of the compiled circuits over 5 orders of magnitude. Figure [ compares the performance of KLAY with the native post-order traversal from PySDD implemented in C. We report results for both the real and logarithmic semiring. As JUICE does not support the logarithmic scatter multiplication, these are excluded
By changing the number of variables and clauses in the
semiring and Jax does not support backpropagation from the respective comparisons. In Appendix B we repeat the same experiment using the D4 knowledge compiler (Lagniez & Marquis, 2017) instead of PySDD.
Our results in igguicatindicate that on large circuits, KLAY on GPU outperforms all baselines with over one order of magnitude. Due to SIMD and multi-core parallelization, KLAY on CPU still considcrably faster than the baselines. JUICE does not include results for the largest instances due to a timeout after 30 minutes. KLAY attains best results with Jax, due to its superior JIT compilation and kernel fusion.
In Figure 7 we display the size and sparsity of the circuits in our synthetic benchmark. Remarkably, KLAY on average has fewer nodes than the original SDD, meaning the node deduplication outweighs the overhead of introducing unary node chains. As we discuss in Appendix B. this is not the case for circuits compiled by D4. Figure (right) shows that larger circuits are increasingly sparse, with less than one in a million edges being present for the largest circuits.
6.2 NEUROSYMBOLIC BENCHMARKS
Next, we consider the use of KLAY in neurosymbolic learning, by measuring the runtime of cal- culating the gradient on the circuits of several neurosymbolie tasks. As a baseline, we consider the naive evaluation in PyTorch, which is the standard approach performed by existing exact proba- bilistic neurosymbolic approaches where each node evaluated individually. We take four different neurosymbolic benchmarks from the literature. The Sudoku benchmark is classification problem, determining whether a 4 X 4 grid of images forms a valid Sudoku (Augustine et al. 2022). The Grid (Xu et al.) 2018) and Warcraft (Pogančié et al. 2020) instances require the prediction of valid low-cost path. Finally, hierarchical multi-level classification (HMLC) concerns the consistent classification of labels in hierarchy (Giunchiglia & Lukasiewicz 2020). The results in Table
demonstrate the drastic speedups of KLAY compared to the naive baseline, improving by as far as
four orders of magnitude for the Warcraft experiment.
As a last experiment, we demonstrate the integration of KLAY into a neurosymbolic framework. Specifically, we use KLAY instead of conventional SDD circuits in DeepProbLog. We measure the
8

---

Published as a conference paper at ICLR 2025
Log Semiring
Real Semiring
Cumulative Time (ms)
104
104
KLay (torch, cpu)
KLay (torch, cuda)
10a
10a
KLay (jax, cpu)
10a
10
KLay (jax, cuda) Post-arder (cpu)
104
10a
Juice (cpu)
10a
10"
Juice (cuda)
10-1
Instances
Instances
Figure 6: Cumulative runtime in milliseconds for the forward and backward pass circuit. That is, we plot the combined run time of the fastest circuit evaluations against the number of n cir- cuits. Timings are averaged over 10 runs per SDD. The SDDs are randomly generated from 3-CNF, where the difficulty is varied by the number of variables and clauses. The left and right figure show cumulative evaluation times for the logarithmic and real semiring, respectively.
10a
10"2
Nb of Nodes in SDD
Nb Nodes in KLay
10'
10-3
No of Nodes
Sparsity
10f
10-4
10a
10-5
10
10-*
10a
40
60
80
100
0
20
80
100
Instances
Instances
Figure 7: (Left) Number nodes in the original SDD, compared to the KLAY representation. The instances are the same in Figure (Right) The sparsity of KLAY, meaning the number of edges in the circuit divided by the number of edges in a dense interconnection of layers.
Table 1: (Top) Number of nodes in the SDD circuits of various neurosymbolic benchmarks, and the number of nodes and layers in the corresponding KLAY representation. (Middle) Runtime in milliseconds for one forward and backward pass on the circuit with batch size 128, using PyTorch autograd for both KLAY and the naive baseline. (Bottom) Runtime in milliscconds for one forward and backward pass the neural network of the neurosymbolic task.
Sudoku (4
Grid (4x4)
HMLC
Warcraft (12 12)
SDD Nodes
2408 3 326
6610
9730
110 234
KLAY Nodes
6.590
26
155 063
KLAY Layers
30
24
84
84
Naive (cpu)
17.35 0.05
46.12 0.49
127.00
140.03
11484.53 + 251.94
Naive (cuda)
42.70 + 2.76
107.78 + 4.67
175.58 +
1.26
18930.67 + 496.16
KLAY (cpu)
0.45 0.02
0.53 + 0.03
1.41
0.02
18.55 + 0.14
KLAY (cuda)
0.46 + 0.17
0.49 + 0.19
1.03 + 0.35
1.59 +
0.25
Neural (cpu)
0.90 + 0.63
0.17 + 0.02
0.55 +
0.29
242.60 +
4.81
Neural (cuda)
0.51 0.13
0.34 + 0.12
0.20
0.04
2.80 +
0.07

---

Published as a conference paper at ICLR 2025
Table MNIST-addition training time in seconds for one epoch. We report the average and standard deviation over 10 epochs, using batch size of 128. Both KLAY and the baselines use PyTorch as autograd. T/O indicates timeout after 2 hours.
Nb of Digits
3
KLAY Nodes
776
660
1 1015 867
DeepProbLog (cpu)
241.63 - 4.38
323.26 + 22.20
T/O
Scallop (epu, k =
52.30 = 0.37
601.20 = 14.65
5345.78 + 171.47
KLAY (cpu)
2.08 + 0.12
2.10 = 0.14
71.54 + 0.46
KLAY (cuda)
1.26 0.03
1.25 + 0.01
8.85 +
0.02
training time of the MNIST-addition task in Table MNIST-addition is common neurosymbolic task where the input is two numbers represented as MNIST images and the model needs to predict their sum. For more details, refer to Manhaeve al. (018). As reference, also include Scallop, which aims to improve the scalability of DeepProbLogg by approximating using top-k prove- nance (Li et al. 2023). While DeepProbLog and Scallop cannot perform batched inference, KLAY can by using multi-rooted circuits. This is reflected in speed-ups of two orders of magnitude over the existing DeepProbLog implementation, even on rather small circuits. Even though KLAY remains exact unlike Scallop, KLAY also demonstrates large speedups here.
CONCLUSIONS
The success of neural networks has been largely attributed to their scale (Kaplan et al. 2020), which realized by their effective use of hardware accelerators. To compete, novel methods must run effi- ciently the available hardware risk losing out due what Hooker (2021) coined the hardware lottery. We tackled this issue for neurosymbolic AI by introducing KLAY- new data structure to represent arithmetic circuits that is amenable to efficient evaluations modern GPUs or TPUs. Along with this representation, we contributed three algorithms for KLAY. The first two algorithms map the traditional linked node representation of arithmetic circuits to the corresponding KLAY representation (Algorithm 2 and 3). This representation is efficiently evaluated using the third algo- rithm, which exploits the parallelization opportunities (Algorithm(]) D
Contrary to widely held belief, our experiments demonstrated that arithmetic circuits can be run efficiently on GPUs, despite their high degree of sparsity. To this end, key aspect the reduction of circuit evaluations to a sequence of indexing and scatter-reduce operations, as these can be im- plemented using highly optimized primitives available modern tensor libraries. Resolving circuit evaluations as one of the major bottlenecks present in current neurosymbolic architectures allows to further scale neurosymbolic models and tackle new problems that have been out of reach so far.
AUTHOR CONTRIBUTIONS
PZD conceived the conceptual idea of KLAY and made an initial prototype. JM worked out the technical details and implemented the methods with the help of VD. JM proposed and carried out the experiments. All authors contributed equally to the writing. PZD supervised the project.
ACKNOWLEDGMENTS
This research received funding from the Flemish Government (AI Research Program), the Flan- ders Research Foundation (FWO) under project G097720N, the KU Leuven Research Fund (C14/18/062), and the European Research Council (ERC) under the European Union's 's Horizon 2020 research and innovation programme (Grant agreement No. 101 101142702). PZD is supported by the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation. We thank Lue De Raedt for his valuable feedback.
10

---

Published as a conference paper at ICLR 2025
REPRODUCIBILITY
The functionality of KLAY has been described in pseudo-code (Algorithms 2 and 3 and has been implemented Python library easily replicate all experiments in the paper, available
htttp:://github. https//oo////KKeeee//////////// KUleeven/klay
REFERENCES
Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S. Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Ian Goodfellow, Andrew Harp, Geoffrey Irving, Michael Isard, Yangqing Jia, Rafal Jozefowicz, Lukasz Kaiser, Manjunath Kudlur, Josh Levenberg, Dandelion Mané, Rajat Monga, Sherry Moore, Derek Murray, Chris Olah, Mike Schuster, Jonathon Shlens, Benoit Steiner, llya Sutskever, Kunal Talwar, Paul Tucker, Vincent Vanhoucke, Vijay Vasudevan, Fernanda Viégas, Oriol Vinyals, Pete Warden, Martin Wat- tenberg. Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. TensorFlow: Large-scabe machine learn- ing on heterogeneous systems, 2015. URL https:/ /tops:://www. wwwsorflow..ooooo.. org/ Software available from tensorflow.org.
Kareem Ahmed, Tao Li, Thy Ton, Quan Guo, Kai-Wei Wei Chang, Parisa Kordjamshidi, Vivek Sriku- mar, Guy Van den Broeck, and Sameer Singh. Pylon: A pytorch framework for learning with constraints. In NeurlPS 2021 Competitions and Demonstrations Track, pp. 319-324. PMLR, 2022a.
Kareem Ahmed, Stefano Teso, Kai-Wei Chang, Guy Van den Broeck, and Antonio Vergari. Seman- tic probabilistic layers for neuro-symbolic learning. Advances in Neural Information Processing Systems, 35:29944-29959, 2022b.
Eriq Augustine, Connor Pryor, Charles Dickens, Jay Pujara, William Wang, and Lise Getoor. Vi- sual sudoku puzzle classification: A suite of collective neuro-symbolic tasks. In International Workshop on Neural-Symbolic Learning and Reasoning (NeSy), 2022.
Samy Badreddine, Artur d' Avila Garcez, Luciano Serafini, and Michael Spranger. Logic tensor networks. Artificial Intelligence, 303:103649, 2022.
Djamal Belazzougui, Fabiano C Botelho, and Martin Dietzfelbinger. Hash, displace, and compress. In European Symposium on Algorithms, pp. 682-693. Springer, 2009.
James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman- Milne,, and Qiao Zhang. JAX: composable transformations Python+NumPP programs, 2018. URL http:
//github. cow.bb//ccc/goooll///aaaa
Mark Chavira and Adnan Darwiche. On probabilistic inference by weighted model counting. Arti- ficial Intelligence, 172(6-7):772-79, 2008.
YooJung Choi, Antonio Vergari, and Guy Van den Broeck. Probabilistic circuits: A unifying frame- work for tractable probabilistic models. Technical report, University of California Los Angeles, 2020.
Young-kyu Choi, Carlos Santillana, Yujia Shen, Adnan Darwiche, and Jason Cong. Fpga accelera- tion of probabilistic sentential decision diagrams with high-level synthesis. ACM Transactions Reconfigurable Technology and Systems, 16(2):1-22, 2023.
Vidushi Dadu, Jian Weng, Sihao Liu, and Tony Nowatzki. Towards general purpose acceleration by exploiting common denendeeen forms. In Proceedings of the 52nd Annual IEEE/ACM International Symposium on Microarchitecturre pp. 924 939, 2019.
Meihua Dang, Pasha Khosravi, Yitao Liang, Antonio Vergari, and Guy Van den Broeck. Juice: A julia package for logic and probabilistic circuits. In Proceedings of the AAAI Conference on Artificial Intelligence, pp. 16020-16023, 2021.
Adnan Darwiche. Decomposable negation normal form. Journal of the ACM (JACM), 48(4):608- 647, 2001a.
11

---

Published as a conference paper at ICLR 2025
Adnan Darwiche. On the tractable counting of theory models and its application truth maintenance and belief revision. Journal of Applied ton-Classicca Logics, 11(1-2)11134, 2001b.
Adnan Darwiche. A differential approach to inference Bayesian networks. Journal of the ACM (JACM), (0(3)0000-033333 2003.
Adnan Darwiche. SDD: A new canonical representation of propositional knowledge bases. In Twenty-Second International Joint Conference on Artificial Intelligence, 2011.
Adnan Darwiche. Tractable boolean and arithmetic circuits. In Neuro-Symbolic Artificial Intelli- gence: The State of the Art, pp. 146-172. IOS Press, 2021.
Adnan Darwiche and Pierre Marquis. A knowledge compilation map. Journal of Artificial Intelli- gence Research, 17:229-264, 2002.
Lennert De Smet, Pedro Zuidberg Dos Martires, Robin Manhaeve, Giuseppe Marra, Angelika Kim- mig, and Lue De Readt. Neural probabilistic logic programming discrete-continuous domains. In Uncertainty in Artificial Intelligence, pp. 229-538. PMLR, 2023.
Michelangelo Diligenti, Marco Gori, and Claudio Sacca. Semantic- regularization for learning and inference. Artificial Intelligence,
2017.
Daan Fierens, Guy Van den Broeck, Joris Renkens, Dimitar Shterionov, Bernd Gutmann, Ingo Thon, Gerda Janssens, and Luc De Raedt. Inference and learning in probabilistic logic programs using weighted boolean formulas. Theory and Practice of Logic Programming, 15(3):358 4018 2015.
Laura Galindez Olascoaga, Wannes Meert, Nimish Shah, Marian Verhelst, and Guy Van den Broeck. Towards hardware-aware tractable learning of probabilistic models. Advances in Neural Information Processing Systems, 32, 2019.
Eleonora Giunchiglia and Thomas Lukasiewicz. Coherent hierarchical multi-label classification networks. Advances in neural information processing systems, 33:9662 2673, 2020.
Pascal Hitzler and Md Kamruzzaman Sarker. Neuro-symbolic artificial intelligence: The state of the art. IOS press, 2022.
the Sara Hooker. The hardware lottery. Communications the ACM, 64(12):58-65, 2021.
Ying Jiao, Lue De Raedt, and Giuseppe Marra. Valid text-to-sql generation with unification-barl deepstochlog. In Processings of the 18th International Conference on Neubal-Symbolic Learning and Reasoning, 2024.
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprint arXiv:2001.0836/ 2020.
Angelika Kimmig, Guy Van den Broeck, and Luc De Raedt. Algebraic model counting. Journal of Applied Logic, 22:46-62, 2017.
Pang Wei Koh, Thao Nguyen, Yew Siang Tang, Stephen Mussmann, Emma Pierson, Been Kim, and Percy Liang. Concept bottleneck models. In International conference machine learning, pp- 5338-5348. PMLR, 2020.
Marie Lagniez and Pierre Marquis. An Improved Decision-DNNF Compiler. IJCAI, vol- ume 17, pp. 667-673, 2017.
Ziyang Li, Jiani Huang, and Mayur Naik. Scallop: A language for neurosymbolic programming. Proceedings of the ACM on Programming Languages, 166LD)): 2023.
Anji Liu, Kareem Ahmed, and Guy Van den Broeck. Scaling tractable probabilistic circuits: A systems perspective. In Forty-first International Conference on Machine Learning, 2024.
Robin Manhaeve, Sebastijan Dumancic, Angelika Kimmig, Thomas Demeester, and Lue De Raedt. Deepproblog: Neural probabilistic logic programming. Advances in neural information process- ing systems, 31, 2018.
12

---

Published as a conference paper at ICLR 2025
Antonio Mari, Gennaro Vessio, and Antonio Vergari. Unifying and understanding overparame- terized circuit representations via low-rank tensor decompositions. In The 6th Workshop on Tractable Probabilistic Modeling, 2023.
Ralph C Merkle. A digital signature based conventional encryption function. In Conference the theory and application of cryptographic techniques, pp. 369-378. Springer, 1987.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury. Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high- performance deep learning library. Advances in neural information processing systems, 32, 2019.
Robert Peharz, Steven Lang, Antonio Vergari, Karl Stelzner, Alejandro Molina, Martin Trapp. Guy Van den Broeck, Kristian Kersting, and Zoubin Ghahramani. Einsum networks: Fast and scalable learning of tractable probabilistic circuits. In International Conference on Machine Learning, pp- 7563-7574. PMLR, 2020a.
Robert Peharz, Antonio Vergari, Karl Stelzner, Alejandro Molina, Xiaoting Shao, Martin Trapp, Kristian Kersting, and Zoubin Ghahramani. Random sum-product networks: A simple and effec- tive approach to probabilistic deep learning. In Uncertainty in Artificial Intelligence, pp. 334-344.
PMLR, 2020b.
Marin Vlastelica Pogančić, Anselm Paulus, Vit Musil, Georg Martius, and Michal Rolinek. Differ- entiation of blackbox combinatorial solvers. In International Conference on Learning Represen- tations, 2020.
Nimish Shah, Laura Galindez Olascoaga, Wannes Meert, and Marian Verhelst. Acceleration of probabilistic reasoning through custom processor architecture. In 2020 Design, Automation & Test in Europe Conference & Exhibition (DATE), pp. 322-325, IEEE, 2020.
Nimish Shah, Laura Isabel Galindez Olascoaga, Shirui Zhao, Wannes Meert, and Marian Verhelst. Dpu: Dag processing unit for irregular graphs with precision-scalable posit arithmetic in 28 nm.
IEEE Journal of Solid-State Circuits, 57(8):2586 2021.
Lukas Sommer, Julian Oppermann, Alejandro Molina, Carsten Binnig, Kristian Kersting, and An- dreas Koch. Automatic mapping of the sum-produs propprrduct network inference problem to fpga-based accelerators. In 2018 IEEE 36th International Conference on Computer Design (ICCD), pp- 350-357. IEEE, 2018.
Lukas Sommer, Michael Halkenhäuser, Cristian Axenie, and Andreas Koch. Spnc: Accelerating sum-product network inference on cpus and gpus. In 2021 IEEE 32nd International Conference on iopplicatiio-speciife Systems, Architectures and Processors (ASAP), pp. 53-56. IEEE, 2021.
Trieu Trinh, Yuhuai Wu, Quoe V Le, He He, and Thang Luong. Solving olympiad geometry without human demonstrations. Nature, 625(79955:476-48)) 2024.
Leslie G Valiant. The complexity of computing the permanent. Theoretical computer science, 8(2); 189-201, 1979.
Md Vasimuddin, Sriram P Chockalingam, and Srinivas Aluru. A parallel algorithm for Bayesian network inference using arithmetic circuits. In 2018 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pp. 34-43, IEEE, 2018
Antonio Vergari, Yoolung Choi, Anji Liu, Stefano Teso, and Guy Van den Broeck, compositional atlas of tractable circuit operations for probabilistic inference. In Advances in Neural Information Processing Systems, 2021.
Zishen Wan, Che-Kat Liu, Hanchen Yang, Ritik Raj, Chaojian Li, Haoran You, Yonggan Fu, Cheng Wan, Sixu Li, Youbin Kim, al. Towards Efficient Meuro-Symbolt Al: From Workload Char- acterization to Hardware Architecture. IEEE Transactions on Circuits and Systems for Artificial Intelligence, 2024.
Lukas Weber, Johannes Wirth. Lukas Sommer, and Andreas Koch. Exploiting bandwihh memory for fpga-acceleration of inference on sum-product networks. In 2022 IEEE International Parallel and Distributed P Processing Symposium Workshops (IPDPSW). pp. 112-119. IEFF, 2022.
13

---

Published as a conference paper at ICLR 2025
Thomas Winters, Giuseppe Marra, Robin Manhaeve, and Luc De Raedt. Deepstochlog: Neural stochastic logic programming. Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 100900101000 2022.
Jingyi Xu, Zilu Zhang, Tal Friedman, Yitao Liang, and Guy Broeck. semantic loss function for deep learning with symbolic knowledge. In International conference on machine learning, pp- 5502-5511. PMLR, 2018.
Wen-Chi Yang, Giuseppe Marra, Gavin Rens, and Luc De Raedt. Safe reinforcement learning via probabilisticc logic shields. In Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, pp. 5739-5749, 2023.
Kexin Yi, Jiajun Wu, Chuang Gan, Antonio Torralba, Pushmeet Kohli, and Josh Tenenbaum. Neural- symbolic vqa: Disentangling reasoning from vision and language understanding. Advances in neural information processing systems, 31, 2018.
14

---

Published as a conference paper at ICLR 2025
APPENDIX
A PROOF OF THEOREM
Theorem 1. Given a set of circuits, all identical sub-circuits can be identified in linear expected time complexity in the total number of edges in the circuits.
Proof. We provide a constructive proof. First, observe that nodes representing syntactically identical sub-eircuits have the same height and are therefore members of the same layer. Second, observe that nodes within a layer are identified by their set of children. Combining these two observations, we can rely on the following inductive property: by ensuring deduplication of all nodes layer I,- trivial to check equivalence for the nodes in layer T.. In conclusion, we can identify and deduplicate all equivalent nodes by iterating over all nodes bottom-up. To detect equivalent nodes within a layer, employ an efficient hashing scheme where cach node is hashed the set of the hashes of its children Cn (see Equation 3). As the set of nodes is fixed, we can assume perfect hashing scheme devoid of any hashing confficts (Belazzougui al. 2009). As this algorithm considers each edge precisely once, indeed linear in the number of edges. Moreover, the hash tables requires linear memory in the number of nodes.
B ADDITIONAL EXPERIMENTAL DETAILS
Synthetic Benchmarks To generate the circuits, we randomly generate 3-CNF formulas. This requires parameters, the number of clauses k and the number of variables v. The generated 3-CNF formulas contains & clauses with 3 randomly picked variables from the v variables. To vary the difficulty, we generate 3-CNF with 30, 35, 40, 45, 50, 55, 60, 65, 70. 75, and 80 variables. For each variable count, we generate 10 random instances, resulting count is also taken as half the number of variables for the SDD benchmarks and twice the number of variables for the D4 benchmarks. This difference can be attributed to D4 generating smaller circuits, so we make the instances harder.
total of 110 instances. The clause
Extra Experiments In Figure g we repeat the same synthetic experiment as in Figure but us- ing top-down d-DNNF knowledge compiler, D4, instead of bottom-up SDD compiler. As baseline, we use an optimized Rust implementation rithm. These circuits do not contain duplicate nodes and somewhat less balanced, leading larger overhead in terms of extra nodes, as is visible on the right of Figure S Nonetheless, KLAY still outperforms the baseline by large margin. Finally, Table experiments from Table with batch size 128 instead of
the node-by-node post-order evaluation algo-
we repeat the neurosymbolic
10a
No of Nodes d-DNNF
10a
KLay (torch, cpu)
KLay
No of Nodes
107
10a
KLay (torch, cuda)
10a
102
KLay (jax, cpu)
KLay (jax, cuda) Post-order (cpu)
10a
10a
10c
10a
10a
10-1
40
60
100
20
40
60
80
100
Instances
Instances
Figure 8: (Left) Number of nodes in the original d-DNNF, compared to KLAY'S layerized circuit. (Right) Cumulative runtime in milliseconds for forward and backward pass on d-DNNF circuit in the log semiring. Timings for each individual circuit are averaged over 10 runs. Each instance a randomly generated logical formula 3-CNF, compiled into d-DNNF circuit using D4. The number of variables and clauses in the CNF was varied achieve different levels of difficulty.
15

---

Published as a conference paper at ICLR 2025
Table 3: (Top) Number of nodes in the SDD circuits of various neurosymbolic benchmarks, and the number of nodes and layers in the corresponding KLAY representation. (Middle) Runtime in milliseconds for one forward and backward pass on the circuit with batch size 128, using PyTorch autograd for both KLAY and the naive baseline. (Bottom) Runtime in milliseconds for one forward and backward pass on the neural network of the neurosymbolic task.
Sudoku (4x4)
Path (4x4)
HMLC
Warcraft (12x 12)
SDD Nodes
2408
6610
9730
110234
KLAY Nodes
3 922
6.590
26.306
155 063
KLAY Layers
30
24
84
84
Naive (cpu)
21.55 + 0.83
55.46 + 5.83
122.37 + 35.33
12225.93 + 626.03
Naive (cuda)
47.20 + 5.29
112.86 2.49
201.07 + 18.62
19324.75
74.16
KLAY (cpu)
5.64 + 0.06
4.96 0.15
15.43 = 0.17
514.20 + 22.14
KLAY (cuda)
3.03 + 0.05
2.47 0.03
8.76
1.56
72.59
0.16
Neural (cpu)
23.05 + 3.63
0.72 - 0.02
0.63 + 0.15
17420.27
202.31
Neural (cuda)
1.24 + 0.21
0.30 + 0.02
0.21 + 0.04
73.20 + 0.02
C PSEUDO-CODE
Algorithm and contains pseudo-code of the previously discussed layerization and tensorization procedures. Algorithm 4 contains the pseudo-code for the evaluation KLAY in the logarithmic semiring instead of the real semiring.
Algorithm 2: KLay Layerization
Input: Boolean Circuit C' as linked nodes.
layers
height <
hashes
for node in the nodes of C, children before parents do n is leaf node then
height(m (n) +- 0;
hashes(n) [n]] +- hash(n);
else
height[n] + mcXcecchldeen(s) height(c];
Bring children the prior layer */ for child node in children(n) do while heightfc]+1 & height(n| do
c- unary node with child
height c < height ccild(c)] hashes hash (hashes/ccild((())) cc)) < c:
layers [hgeess/heghh([[]hhaheee
end end hashes(n) +- + eEchildren(n) hash(hashes(c) end
* Add node to its layer #/ layers layers[height/ m)] [hashes[]]] [m]] n
end
return layers;
16

---

Published as a conference paper at ICLR 2025
Algorithm 3: KLay Tensorization
Input: layers.
1 We assume the nodes in each layer are ordered, such that index(n) is the index of node in layer. */
for layer in layers do
R
for node n in layer do
for child of node do
(r
end
end end
return
(SI....,Shh: (R......... R
Algorithm 4: KLay Forward Evaluation in the Logarithmic Semiring
Input: No, selection indices S,,S,... .,...., .t,....,,.... reduction indices R. R R,, epsilon
for I 1 to do
E, < N 1 S
if mod 2 = then
1* As logsumexp reduction is not always implemented for scatter, we perform it using max and sum scatter operations. */
M < scatter( E, reduce max');
T f- scatter( exp E M(R,)), R,, reduce=ssum))
N + log(T T + t) M:
else
N scatter Er R reduce='sum"):
end
end
return N,;
D NEUROSYMBOLIC EXAMPLE
We demonstrate how neural networks can be combined with circuits on simplified variant of the canonical MNIST-addition task (Manhaeve et al.) 2018). In this task, two MNIST images given containing either the digit zero or one, and the goal is to predict the sum of the two digits. Note that the labels of the individual digits not given. There truth labels of the images. Either both images are zero and the sum is also zero, or one image is zero and the other is one resulting in sum of one, both one and the sum is two.
four distinct possibilities for the ground
Let us write p(Img, = j) for the probability that image i contains the digit j. and p(Sum = k)) for the probability that the sum equals k. Now it follows that
p(Sum 0) = p(Imgo 0) p(Img, 0)
p(Sum 1) = p(Imgo 0) p(Img, 1) + +p(mng = - p(Img; = 0)
((Sum 2) = p(Imgo 1) p(Img =1)
We can now encode the above probabilities in multi-rooted circuit, which we visualize in Figure Observe that each root computes of the probabilities for p(Sum k).
17

---

Published as a conference paper at ICLR 2025
p(Sum = 0)
p(Sum = 1)
p(uum = 2)
p(Imgo 0)
p(Imgo 1)
p(Img, = 0)
p(Img, = 1)
Figure 9: A simple neurosymbolic model for the MNIST-addition task. Two MNIST images given as input. First, vision model classifies the probability of the image containing zero or one. Next, circuit uses these probabilities calculate the probabilities of the different possible sums.
18


Reviews:
[{"review_id": "72TkkdGeX6", "reviewer": "Reviewer_dDtS", "summary": "This paper proposes a new data structure, called knowledge layers (KLay), that allows the efficient parallelization of arithmetic circuits, which appear to be a major computational bottleneck in a specific type of neuro-symbolic AI approach.", "questions": "Answering the following questions/remarks could further improve the paper: \n\n1) Unclear impact on end-to-end neuro-symbolic approaches. While the introduction clearly states the dominance of the “symbolic” part, this dominance is not obvious in the experimental results. To my understanding, only the MNIST addition dataset tests the end-to-end timing results (including \"neural\"+\"symbolic\"). What are the contributions of the individual blocks? It would be great to quantify. Moreover, this is an example where the “neural” part is rather lightweight (simple digit recognition). How would this relation between “neural” and “symbolic” would look like in other tasks?\n \n2) Explosion in the number of KLay Nodes on “Sudoku” and “HMLC”. On these two datasets, the number of KLay nodes increases by 1.5-2.7x. What is the reason for the increase? Could you please elaborate on it?\n \n3) Insufficient introduction of datasets. It would be good to introduce all the datasets in the appendix so that the paper becomes more self-contained. In particular, the number of instances in Figure 6 is not introduced. Are they variables, clauses, or their combination? The mentioned range over 5 orders of magnitude is not visible in Figure 6.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "First, the paper tackles an important challenge in neuro-symbolic AI, where scalability is still one of the major roadblocks for their general application. The achieved speed-ups of the proposed KLay on both CPU and GPU seem very promising.  Finally, the paper is well-written, and the methods are explained intuitively thanks to the use of appropriate figures and examples. This makes the paper accessible despite the methodology being quite involved.", "weaknesses": "1) Although the paper indicated in 3rd paragraph that it focused on a \"particular flavor of neurosymbolic AI\", i.e., a neural network feeding into probabilistic inference based on arithmetic circuits, it would be beneficial to reflect it explicitly in other parts, e.g., in the abstract, or a more specific title (Accelerating Arithmetic Circuits in Neurosymbolic AI), to be able to attract the right audience.\n\n2) The actual \"interface\" and details between the neural network and the used arithmetic circuits remain largely a secret for readers(of course there are pointers to prior arts). It would be beneficial to open up and explain how exactly a neural network is interfaced to the arithmetic circuits, what are the assumptions and domain knowledge etc. at least for one of the tasks (e.g. MNIST addition) in an appendix.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "VZrRGJC2r8", "reviewer": "Reviewer_HTjk", "summary": "In this paper, the authors introduce a new data structure called knowledge layers (KLAY) designed to enhance the parallelization of Boolean circuit computation in neurosymbolic AI. They propose organizing d-DNNF circuits into layers and applying Merkle hashing for node deduplication, subsequently reducing circuit evaluation to indexing and scattering operations. Empirical results demonstrate that KLAY achieves speedups of several orders of magnitude compared to related works, providing a significantly more efficient implementation on GPUs.", "questions": "1. Although the title of Section 2 is \"A Brief Primer on Neurosymbolic AI,\" it does not adequately explain the concept. It focuses primarily on the use of Boolean circuits in neurosymbolic AI and the challenges associated with their execution on GPUs. The significance and value of the work need to be more emphasized.\n2. In Figure 6, there is a noticeable increase in slope when the number of instances exceeds 100. Does this behavior align with the authors' expectations regarding the linear time complexity of the algorithm?\n3. In Table 1, a batch size of 1 is used. Is this a standard measurement practice? Could this choice potentially disadvantage non-parallel methods due to lower resource utilization?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The utilization of modern AI accelerators is crucial for advancing the field of neurosymbolic AI, enabling the development of large-scale models and tackling more complex problems that have been previously out of reach.\n2. The ability to enable parallel computation on GPUs results in speedups of multiple orders of magnitude over current state-of-the-art approaches.", "weaknesses": "1. The background introduction to neurosymbolic AI is somewhat lacking, providing insufficient context. \n2. The experimental comparisons with state-of-the-art methods appear limited in scope compared to those discussed in related works.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "edB2tCS5vi", "reviewer": "Reviewer_EziM", "summary": "The authors propose KLay, a data structure that enable parallel computing on irregular operations in knowledge layers of neurosymbolic AI.", "questions": "I appreciate the authors effort in advancing neurosymbolic AI, and I personally am educated a lot from this work. Below are some questions, mainly regarding the motivation. \n\n1. \"arithmetic circuits are ill-suited to be evaluated on AI accelerators...\" Additional to GPUs/TPUs, AI accelerators also use ASICs and FPGAs as platforms, which are known to be capable of handling irregular operations. It would be insightful if the authors could discuss why arithmetic circuits are not suitable on these platforms. \n\n2. Could you please clarify if the neural networks are indeed separate from the arithmetic circuit? My understanding is that the leaf node values represent probabilities obtained from neural networks, and the subsequent operations involve arithmetic computations from the leaf nodes to the root node. Would it be practical to transfer the probability data to CPUs for post-order tree traversal after the neural network computations are performed on GPUs?\n\n3. Could the authors provide insights into how the workload and time consumption of the arithmetic circuit compare to the upstream neural networks? Is there a typical percentage that represents this comparison?\n\n4. Could the authors clarify if this approach can be considered an efficient method for parallel post-order tree traversal? If so, how does it compare to other efficient parallel algorithms for post-order tree traversal, if any exist?\n\n5. Do current AI models possess the capabilities that neurosymbolic AI offers? What are the advantages compared to modern AI models do the authors anticipate that neurosymbolic AI can achieve? It would be very helpful if examples can be provided.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The problem the authors formulated is clear.", "weaknesses": "The motivation needs further justification.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "UXKjzSPS2F", "reviewer": "Reviewer_Jxpy", "summary": "This paper proposes a method to tackle a numerical problem in the field of neurosymbolic AI. It allows to represent arithmetic circuits, used to model symbolic constraints, as a new kind of data structure, knowledge layers (KLay), on which computations can be performed more efficiently. Notably, computations on KLay can be performed in parallel, and thus exploit the full potential of AI accelerators such as GPUs. Empirical results show the superiority of these layers over existing methods in terms of computational speed.", "questions": "How are the KLay optimized ? Is optimization performed on the arithmetic circuits (that are emphasized as differentiable in the text) before representing them as KLay ? Could the authors address this question more explicitly would benefit to the completeness of the analysis.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "+ The paper tackles an apparently difficult problem, which other authors had claimed is impossible to solve\n+ It paves the way for a broader deployment of neurosymbolic AI models on standard deep learning hardwares such as GPU or TPU, while efficiently exploiting their potential\n+ Empirical results are displayed in a clear way, showing the effective superiority of the proposed method over existing ones", "weaknesses": "No weekness to mention", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)