KLay: Accelerating Arithmetic Circuits for Neurosymbolic AI

How are the KLay optimized ?

We optimize the parameters of a circuit with conventional gradient-based optimizers, specifically, Adam (line 125). Note also that we do not learn the structure of the circuit, as this structure is generated by a knowledge compiler such as PySDD (lines 86-93).

Is optimization performed on the arithmetic circuits (that are emphasized as differentiable in the text) before representing them as KLay ?

Both inference and training using KLay is considerably faster (see e.g. Table 1). Hence, the point is to first convert the circuit to KLay before training.

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?

The circuit evaluation time typically dominates the inference in neurosymbolic experiments. For instance, when running the MNIST-addition experiment with SoTA methods (e.g. Scallop or DeepProbLog), the neural network takes less than 1% of the inference runtime. For reference, we have added the neural network inference timings for the considered neurosymbolic tasks in Table 1 and 3. Although the precise ratio between circuits and neural nets depends on the specific experiment setup, the absolute improvement in execution time of KLay is very significant as long as the circuit is large (see Figure 6), regardless of the choice of neural net.

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.

As mentioned in the first paragraph, “including symbolic information has been shown to increase reasoning capabilities [1, 2], safety [3], controllability [4], and interpretability [8]. Furthermore, neurosymbolic methods often require less data by allowing a richer and more explicit set of priors [5, 6].”

As a concrete example, neurosymbolic methods can generate code that is guaranteed to be executable [4], or generate predictions for self-driving cars that are always consistent with common-sense constraints [7]. On the other hand, it is impossible for pure neural approaches to attain similar guarantees.

[1]: Yi, Kexin, et al. "Neural-symbolic vqa: Disentangling reasoning from vision and language understanding." Advances in neural information processing systems 31 (2018).

[2]: Trinh, Trieu H., et al. "Solving olympiad geometry without human demonstrations." Nature 625.7995 (2024).

[3]: Yang, Wen-Chi, et al. "Safe reinforcement learning via probabilistic logic shields." Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence. 2023.

[4]: Jiao, Ying, et al. "Valid text-to-sql generation with unification-based deepstochlog." International Conference on Neural-Symbolic Learning and Reasoning, 2024.

[5]: Diligenti, Michelangelo, Marco Gori, and Claudio Sacca. "Semantic-based regularization for learning and inference." Artificial Intelligence 244 (2017): 143-165.

[6]: Manhaeve, Robin, et al. "Deepproblog: Neural probabilistic logic programming." Advances in neural information processing systems 31 (2018).

[7]: Giunchiglia, Eleonora, et al. "ROAD-R: the autonomous driving dataset with logical requirements." Machine Learning 112.9 (2023).

[8]: Koh, Pang Wei, et al. "Concept bottleneck models." International conference on machine learning. 2020.

We are glad to read that the problem was clearly formulated, that there are no weaknesses barring the motivation, and that the work has personally educated you. In this light, we were surprised by the low score. We have added a section in the Appendix to motivate the use of circuits with neural networks, and we hope to address your remaining questions below.

"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.

Efficiently executing circuits on FPGAs is certainly possible [1, 2]. However, as pointed out in the paper (lines 380-388) it remains desirable that neurosymbolic methods can be trained on the same device as the neural network, which in practice usually means either GPUs or TPUs. Not only are FGPAs much less widely available to practitioners (line 383), they also induce considerable latency as the probabilities and gradients need to be transferred between GPU and FPGA every iteration (line 386).

[1]: Sommer, Lukas, et al. "Automatic mapping of the sum-product network inference problem to fpga-based accelerators." 2018 IEEE 36th International Conference on Computer Design (ICCD). IEEE, 2018.

[2]: Choi, Young-kyu, et al. "FPGA acceleration of probabilistic sentential decision diagrams with high-level synthesis." ACM Transactions on Reconfigurable Technology and Systems 16.2 (2023): 1-22.

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.

Yes, this is correct (see lines 107-125). This is an established technique in neurosymbolic AI [1,2,3,4].

[1]: Xu, Jingyi, et al. "A semantic loss function for deep learning with symbolic knowledge." International conference on machine learning (2018).

[2]: Manhaeve, Robin, et al. "Deepproblog: Neural probabilistic logic programming." Advances in neural information processing systems 31 (2018).

[3]: Maene, Jaron, et al. "On the Hardness of Probabilistic Neurosymbolic Learning." Forty-first International Conference on Machine Learning (2024).

[4]: Ahmed, Kareem, et al. "Semantic probabilistic layers for neuro-symbolic learning." Advances in Neural Information Processing Systems 35 (2022).

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?

No, this is not practical. Firstly, the communication between CPU and GPU introduces considerable latency. Secondly, post-order evaluation on CPU is not parallel and hence many orders of magnitudes slower compared to leveraging GPUs (see Figure 6). Note that even on CPU our method is still 10x faster than post-order traversal (see Figure 6).

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?

There do exist methods for parallel tree traversal on the GPU. However, they are not applicable in our setting as 1) we have a DAG and not a tree and 2) we have alternating node types inside of the DAG. In this regard, our method is not commensurable with existing GPU tree traversal methods.

The experimental comparisons with state-of-the-art methods appear limited in scope compared to those discussed in related works.

We interpreted this comment in two possible way:

1. We did not compare to enough competing methods
2. We did not perform the comparison on enough problems.

For the first interpretation, we believe to have included all state-of-the art methods. If the reviewer has a method in mind that we might have overlooked we would kindly ask for a specific pointer.

As for the second interpretation of the comment, we believe to have an experimental evaluation with appropriate scope to show that our premise holds in general. That is, using KLay yields enormous speed-ups in run time.

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.

The contribution of our work lies in circuit evaluation, and hence this is what the background material focuses on. We have revised the title of Section 2 to “Arithmetic Circuits and Neurosymbolic AI” to more accurately reflect its contents. We have also added an example in Appendix of how neural networks can be used in combination with circuits, to motivate our paper to a wider audience.

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?

Yes, this is expected. For small circuits, the GPU is heavily underutilized and increasing the circuit can just use additional parallelization, but at some point the GPU will be used near capacity and this slope will increase. We note that all considered algorithms have the same linear complexity, and hence for sufficiently large experiments the slope is expected to be the same.

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?

A batch size of 1 is the most challenging to parallelize as there is no data parallelism to exploit. It also occurs in practice as many neural network evaluations may be needed for the input of a single circuit evaluation. For example, batch size of 1 for the circuit of the Warcraft dataset still requires a batch of 144 for the neural network. Finally, note that we repeat Table 1 with a batch size 128 in Table 3.

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

The first sentence of the abstract explains what flavor of neurosymbolic AI we use: “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”.

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.

The inputs to the circuit are the output probabilities of neural networks (lines 107-125), forming the interface. This is an established approach in neurosymbolic AI [1, 2, 3, 4]. The contribution of our work lies in circuit evaluation, and hence the background and discussion focuses on circuits. We added a further section in Appendix that exemplifies how the MNIST-addition experiment combines circuits with neural networks. We hope this makes the paper accessible to a wider audience.

[1]: Xu, Jingyi, et al. "A semantic loss function for deep learning with symbolic knowledge." International conference on machine learning (2018).

[2]: Manhaeve, Robin, et al. "Deepproblog: Neural probabilistic logic programming." Advances in neural information processing systems 31 (2018).

[3]: Maene, Jaron,et al. "On the Hardness of Probabilistic Neurosymbolic Learning." Forty-first International Conference on Machine Learning (2024).

[4]: Ahmed, Kareem, et al. "Semantic probabilistic layers for neuro-symbolic learning." Advances in Neural Information Processing Systems 35 (2022).

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?

The circuit evaluation time typically dominates the inference in neurosymbolic experiments. For instance, when running the MNIST-addition experiment with SoTA methods (e.g. Scallop or DeepProbLog), the neural network takes less than 1% of the inference runtime. For reference, we have added the neural network inference timings for the considered neurosymbolic tasks in Table 1 and 3. Although the precise ratio between circuits and neural nets depends on the specific experiment setup, the absolute improvement in execution time of KLay is very significant as long as the circuit is large (see Figure 6), regardless of the choice of neural net.

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?

The layerization procedure of KLay introduces new nodes such that each node only has children in the previous layer (see Section 3.1 or a visualization in Figure 2). Depending on the circuit structure, this can be a considerable amount of new nodes. However, our experiments show that KLay is much faster despite this increase in the number of nodes (see Appendix B).

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?

For the synthetic experiment in Figure 6, there are 110 instances (SDD circuits). These are generated by compiling random 3-CNF formulas (see line 400). We have added additional details on how the synthetic experiments are generated in Appendix D.

The mentioned range over 5 orders of magnitude is not visible in Figure 6.

The sizes of the circuits in Figure 6 vary between 1000 nodes to 100 million nodes. This is visualized in Figure 7 (left).