CTSketch: Compositional Tensor Sketching for Scalable Neurosymbolic Learning
Authors: Seewon Choi
Alaia Solko-Breslin
Rajeev Alur
Eric Wong
Venue: NeurIPS 2025 poster ()
Keywords: Neurosymbolic learning
Primary area: general_machine_learning

Abstract: Many computational tasks benefit from being formulated as the composition of neural networks followed by a discrete symbolic program. The goal of neurosymbolic learning is to train the neural networks using end-to-end input-output labels of the composite. We introduce CTSketch, a novel, scalable neurosymbolic learning algorithm. CTSketch uses two techniques to improve the scalability of neurosymbolic inference: decompose the symbolic program into sub-programs and summarize each sub-program with a sketched tensor. This strategy allows us to approximate the output distribution of the program with simple tensor operations over the input distributions and the sketches. We provide theoretical insight into the maximum approximation error. Furthermore, we evaluate CTSketch on benchmarks from the neurosymbolic learning literature, including some designed for evaluating scalability. Our results show that CTSketch pushes neurosymbolic learning to new scales that were previously unattainable, with neural predictors obtaining high accuracy on tasks with one thousand inputs, despite supervision only on the final output.

CTSketch: Compositional Tensor Sketching for Scalable Neurosymbolic Learning
Seewon Choi* University of Pennsylvania seewon@seas upenn. edu
Alaia Solko-Breslin" University of Pennsylvania alaia0seas upenn. edu
Rajeev Alur University of Pennsylvania alur@seas. upenn. edu
Eric Wong University of Pennsylvania exwongSseas. upenn. edu
Abstract
Many computational tasks benefit from being formulated composition of neu- ral networks followed by discrete symbolic program. The goal of neurosymbolic learning is to train the neural networks using end-to-end input-output labels of the composite. We introduce CTSketch, novel, scalable neurosymbolic learning algo- rithm. CTSketch uses two techniques to improve the scalability of neurosymbolic inference: decompose the symbolic program into sub- cub-programs and summarize each sub-program with sketched tensor. This strategy allows us to approximate the output distribution of the program with simple tensor operations over the input distributions and the sketches. We provide theoretical insight into the maximum approximation error. Furthermore, neurosymbolic learning literature, including some designed for eval evaluating scalabil- ity. Our results show that CTSketch pushes neurosymbolic learning to new scales that were previously unattainable, with neural predictors obtaining high accuracy on tasks with one thousand inputs, despite supervision only on the final output."
evaluate CTSketch benchmarks from the
1 Introduction
Many computational tasks can be formulated as the composition neural networks whose out- puts are fed into discrete program. Neurosymbolic learning aims train the neural network using only end-to-end labels of the composite. Concretely, given parameterized neural network Mg. fixed symbolic program c, and training data ((z),.... Nn), y), the goal is minimize the loss L(e( Ma (Z KT)), y) to optimize 0. The key challenge concerns computing the output distribution of with respect its input distributions while ensuring the loss is fully differentiable.
One solution to this problem is to encode e as a differentiable logic program, as Scallop [21], DeepProbLog [25], and DeepSoftLog [23] do. Scallop uses probabilistic Datalog specify the symbolic program e and can be configured with diffcrent provenance semirings, which determine how to aggregate proofs of each fact when evaluating query. However, limitation of many logic programming frameworks that they often do not support external API calls to black-box modules within the symbolic program. This means they cannot large language models (LLMs) to perform reasoning, which can be useful for certain tasks. For example, scene recognition has natural decomposition of an object detector followed by program that prompts LLM classify the scene based on the object predictions.
Equual contribution.
Code is available at http://gghhhbcccomaaaiiolllbbhee
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Other neurosymbolic learning solutions instead treat as black-box that can be encoded in any language and can include API calls. ISED [31] and IndeCateR [9] are techniques that fall into this category, as they both sample inputs to and compute the corresponding outputs to associate rewards with inputs. A-NeSI [32] is another black-box technique that uses a neural network to perform approximate inference over the weighted model counting ( (WMC) problem- the problem of computing the probability of each possible output by adding the probabilities of the corresponding input teignmmnttswwhiee is known to be computationally expensive [2]. While black-box learning algorithms can learn tasks that cannot be encoded as differentiable logic programs, they suffer from slow convergence and low accuracy on tasks with many inputs. This raises the question: one design a more scalable solution by combining the strengths of white- and black-box techniques?
We propose CTSketch, a learning algorithm that encodes programs in tensors. In particular, the tensor summary & captures the exact input-output relationship of c, i.e., dfr] = c(r). Since the size of matches the input space of it may be computationally unaffordable to store & if e involves large number of inputs. CTSketch uses two techniques to address scalability: decompose the symbolic program into sub-programs and sketch each sub- aub-program summary. For white-box programs in which the internals are known, we can manually specify sub-programs that form a tree structure. In this architecture, inference proceeds through each sub-program by computing the product of its summary tensor and the input probabilities. The resulting distributions are passed on to the next sub-programs as inputs, and this process repeats until the last layer produces the final output distribution.
We use tensor sketching methods to reduce the size of sub-program summaries and increase the efficiency of inference. These techniques decompose a high-dimensional tensor into a product of low-rank tensors with low reconstruction error. Tensor sketching can be applied to any symbolic component, including black-box programs, regardless of the sub- sub-program decomposition. With these sketches, we can perform inference via simple tensor operations and efficiently obtain the expected value of the output. From the reconstruction error of the sketching methods, we derive bound on the maximum error of the approximation of the output distribution, providing insight into the performance of CTSketch.
In summary, the main contributions of this paper are as follows. First, we introduce program decomposition with tensor summaries as a way to scale neurosymbolic learning. Next, we introduce CTSketch, a scalable algorithm for learning neurosymbolic programs using composed tensor sketches. Then, we derive bound on the maximum error of the approximation obtained by CTSketch. Finally, we conduct thorough evaluation using state-of-thh-aar neurosymbolic frameworks against a diverse set of benchmarks. Our results demonstrate that CTSketch pushes the frontier of neurosymbolic learning, broadening its applicability to larger problems. In particular, it can solve the task of adding one thousand handwritten digits, which is a significantly larger problem than what prior works could solve, while remaining competitive with existing techniques on standard neurosymbolic benchmarks.
2 Overview
2.1 Problem Statement
For a task that involves unstructured inputs (zi...., the training pipeline consists of neural networks M with parameters 0, followed by a symbolic program e R Y that computes structured output given structured inputs ri,..., rn E Rí X ... x Ra = R. For each input H, the neural network outputs probability distribution p; over discrete values (symbols) in R, We aim to estimate the distribution of the outputs of given the input distributions p.. with the goal to optimize 0 using only end-to-end training data ((Z1,.... 2n), y), without intermediate supervision on r.
In order to predict the probability of each output أ E Y given input distributions pı...., we aim to approximate the following WMC problem
VMC(Ulp.....P..)) ...
(M.) T
Σ I
(2.1)
using tensors that summarize the program. We summarize the input-output pairs of the program using single tensor Y | x|R,, which maps each input combination to its corresponding program
2

---

7
P1
Py-0
Φ1
9
Py=1
P2
3 H
P3
Py-35
P1
P4
Py=36
M,
Figure I: Program decomposition for sum4 Φi computes the sum of 2 digits, and de computes the sum of the results from the first sums.
i 10x10
f P
10x
:R
Figure 2: Φ1 and Φ2 for decomposed sum, without sketching (left of m²) and with sketching
(right of =). Sketching o; involves decomposing it as the product of rank-2 tensors &f and th
output. is also useful to represent ó using a one-hot tensor dOH, {0, 13 R [X.,xxX,
nn 0) c(ri,..., =
otherwise.
During inference, after obtaining predicted distributions p; [0, 1] from the network, we initialize to be their outer product, i.e., p 1i= and compute the probability of each output y E Y, using Equation 2.1 with ØO as the indicator function:
Py=$
Σ (r. 01 plr Tnl. Pine..
(2.2)
The problem with this approach is that the size of ø increases exponentially with the number of inputs, limiting its scalability. To address this challenge, we decompose and use low-rank approximation of each component.
Program Decomposition and Sketching
To decompose for a given task, it is necessary to manually separate into sub-programs. For instance, the program that adds handwritten digits can decomposed as the sum of sums (Fig. 1). The neural network predictions of the digits p! MM(x;)) used inputs to the first 2-digit sum Φ1. Inference through this first layer outputs distributions p}. i.c., inputs to the second sum d2.
While CTSketch can use any tensor sketching algorithm, we explain our method with tensor-train singular value decomposition (TT-SVD) [28]. The goal TT-VVD cores, that reconstruct the original tensor with low eтror (Fig. 2). Given an approximation rank each core built by reshaping the tensor into matrix by flattening all except the i-th dimension, applying truncated SVD, and taking the top p right singular vectors. With a large enough rank, TT-SVD can achieve an arbitrarily small error.
find low-rank tensors, called
We use TT-SVD to sketch each sub program summary d; Y Xx Ral, Given TT-SV outputs cores (ti...., (2) where ti R |II((,, ta [Rax|1 and all other t) (R,X,, The full tensor reconstruction T, is defined as
T
[d]
Σ k
(2.3)

---

where ku = 1 and 2y 1. Note that we do not fully reconstruct T during inference in CTSketch, as this would not reduce memory overhead. Instead, we take the product of individual cores and input distributions to get an approximate output. We describe this process in more detail in $3.2.
This strategy differs from prior works neurosymbolic scalability. The most closely related work is A-NeSI [32], which learns neural network (prediction model) to predict the WMC result given probability distributions from the perception network (inference model). Therefore, the weights of both the inference and prediction models are learned during training. CTSketch circumvents this additional training complexity by requiring the task specific program architecture to be user-defined and initialized by iterating through all (or some subset of) input-output pairs. These initialized tensors accurately capture the program semanties, and after sketching, the WMC approximation is still very accurate because sketching methods guarantee low error. This is in contrast to the DNN used by the inference model in A-NeSI, which can be trained achieve high accuracy but lacks a theoretical guarantee on the error of the estimate.
3 CTSketch
3.1
Algorithm
When the symbolic program e has many inputs, we manually decompose it into sub-programs that from tree structure of m layers. The leaves at layer I are neural network predictions y = Ma (x;) and the root is the final output. The exact structure can be flexible, with one constraint to allow the computation to proceed sequentially from layer 1 to m: the sub-program at layer i can only take outputs from the previous layers p²<3 as inputs. The program does not need to be decomposed into a prefect tree as in Figure 1. For instance, it can contain bounded loops, which can be decomposed by unrolling into a sequence of repeated layers. For each sub-program, its input and output dimension need to be specified. For the sum4 case, the input specifications would be of (pi,r5), oh (p3, pl) and of (2).
We describe the steps of CTSketch using sum4 (Fig. 1) and provide pseudocode in Appendix A. Prior to training, CTSketch initializes each di, using cs, either by sampling a subset of the possible inputs to the sub-program or enumerating all combinations and computing the corresponding outputs. Note this does not require labeled data (Ir, y) as we use structured input/output pairs (r, v). After initializing each di, the algorithm obtains cores (ti (ti...., tta) by sketching di. The decomposition rank p is a hyperparameter and can be chosen to be the full rank that equals the minimum product of the preceding or succeeding dimensions, min; (II [Ryl IRll-IIe=tt> (Rul). In this case, the i-th core would exactly match the original tensor flattened into three dimensions, and the others would be identity matrices, ensuring a reconstruction error of zero.
After computing the sketches, for each training example ((T),..., ,,..,,,,n); kn), u) and its neural network predictions (pi....,,p) pb)) Mo(x1, ,,)), CTSketch goes layer-by-layer through the program layers and computes the expected output for each sub-program.
3.2 Sketching Sub-Programs
We explain the inference steps by continuing with the sum, example. Assuming we use rank-2 TT-SVD decomposition, the program summary Φ1 of the first layer decomposes into two rank-2 tensors t and Ez. which are multiplied with network predictions pi and p! to produce e R. Note that we can compute u without explicitly reconstructing the full tensor (Equation 3.3).
Ril R2
p Ha
(3.1)
b
Ri
R22l
Σ
Σ
plaattifa,2)
Σ
ps pitt [z. b))
(3.2)
= [p) +)) (thp))
(3.3)

---

We apply the RBF kernel and L1 normalization to convert the value into probability distribution Pf 1155 be used as input in the following layers.
ril = RBF(c, exp --
2 11 -
Such transformation is needed for the last layer, where the value can directly compared with the ground truth for the loss computation (e.g., using L1 loss). Hence, the final output space, computed by the last layer, can be infinite (e.g., floating-point outputs).
For programs with finite output space, we can instead decompose the one-hot tensor summary Ø1 and obtain three rank-2 tensors: t1, tz and tz. Multiplying these with network predictions pi and p4 results in a distribution pf E TR 19. This is also computable without explicit reconstruction.
Ra Σ
pibl
Σ
p Plcclp/// altgir, vitgly.
(3.4)
2
[tzl pá Mess d,
Σ Ng il
Σ
Σ EmHadaaa
Σ
(3.5)
2 Σ Jl (p) ( (ll))
(3.6)
The distributions p and p are input the second layer, and repeating this process produces the final output used for the loss computation. Note that we use the symbolic program at test time with the argmax inputs r; argmax (x;)) instead of the sketches.
jE[R,
3.3 Bound on Approximation Error
Suppose that we use TT-SVD to decompose Φs, and the tensor reconstructed from the cores T (Equation 2.3). Let E be the truncation error of the decomposition: for the kth core, is the Frobenius norm of the singular values discarded during the truncation step. With this, we can state the bound on the reconstruction error.
Theorem 3.1 [28]. The reconstruction error of T satisfies
|| - TillF S
Σ
(3.7)
In practice, the reconstruction error is very low, even for small values of approximation rank p. For example, in the sum, task, where the goal is to predict the sum of digits, we decompose the program into (n) layers, with each uub-program computing the sum of its two inputs (Fig. 1). Even for sum1024, where the summary tensor of the sub-program for the final layer, Φ10. has shape 4609 x 4609, rank 2 is enough to give us a reconstruction еттоr < le-5 for all layers. With such low reconstruction error, we can also guarantee that the product of each T with the corresponding input distributions will have very low error. We derive an error bound of the output distribution if we were to do a full reconstruction Φ..
Theorem 3.2 (CTSketch error bound). For input distribution p, The error of the output distribution is bounded by
| OH p- pH S /2lpp///4/1/ T: 1
(3.8)
We provide short proof, which uses the the full reconstruction is not exactly how CTSketch performs inference, it still gives us a good idea of how well the algorithm approximates the final distribution. CTSketch takes the product of each core, without reconstruction, with the respective input distribution and obtain an expected value of the output. This is then converted to distribution with the RBF kernel and L, normalization.
Schwartz inequality, in Appendix B. While using
5

---

4 Evaluation
In this section, we evaluate CTTSketch and aim to answer the following research questions:
RQI:
Can CTSketch learn tasks with a large number of inputs that are not solvable by prior works?
RQ2:
How does CTSketch perform on benchmarks that can be solved by existing techniques?
RQ3: How efficiently does CTSketch learn, i.e., how quickly does it converge compared to the baselines?
RQ4: How does the approximation rank of CTSketch influence its performance and training time?
4.1
Benchmark Tasks
We consider tasks from the neurosymbolic learning literature, including some designed for evaluating scalability.
MNIST Sum. We consider the problem of computing the sum of handwritten digits (sum,,) from the MNIST dataset [19]. We use sums of n = 2* digits, where k E {2, 4, 6, 8, 10). Each task uses a training set of 5K samples and testing set of IK samples, except sum1024 where we use 4K training samples due to resource constraints.
Multi-digit Addition. We use the Multi-digt MNISTAdd task (add,)). originally proposed by [25], where the goal is to compute the sum of two n-digit numbers. We use n E {1, 4, 15, 100) with a training set of 60,000/2r 22 samples and test set of 10,000/2n samples.
Visual Sudoku. We use the ViSudo-PC dataset [I] containing 200 4x4 and 2K 9x9 filled boards for training and testing. The goal of this task is to predict whether the input is valid Sudoku board.
Sudoku Solving. The goal of this task is to solve 9x9 Sudoku puzzle, where the board is given as a sequence of MNIST images with the digit 0 representing an empty cell. We use the SatNet [33] dataset with 9K training samples and 500 test samples and follow the same experimental setup as [4].
HWF. The HaiteWritten Formula (HWF) task uses a dataset from [20] of 10K formulas of length 1-7 containing handwritten images of digits and operators. The dataset includes 1K length formulas, IK length 3 formulas, 2K length 5 formulas, and 6K length 7 formulas. The goal is to predict the result of the formula evaluation.
Leaf Identification and Scene Classification. We include two tasks from [31] which use GPT-4 to perform reasoning in the symbolic component for leaf identification and scene recognition, using datasets from [3] and [27] respectively. The goal is to identify a leaf species from the predicted features or classify scene from the predicted objects.
4.2 Baselines and Experimental Setup
We choose several neurosymbolic techniques as baselines, with some specifically designed for scalability. We include Scallop [21], framework that uses probabilistic Datalog to specify the symbolic component and has been shown to outperform DeepProbLogg [25]. We also compare with DeepSoftLog (DSL) [23] for MNIST sum and multi-digit addition, but omit for other tasks since it cannot encode programs that use GPT-4 (leaf, scene), and requires customized solutions in which encoding complex reasoning is difficult (visudo, sudoku, hwf). We also consider IndeCateR [9], scalable gradient estimator with lower variance than REINFORCE [34], ISED [31] that uses sampling and summary logic program to obtain a custom loss, and A-NeSI [32], framework for approximating WMC results by training a neural estimator.
We run all experiments on a machine with one 14-core Intel 19-10940X CPU, one NVIDIA RIX 3090 GPU, and 66 GB of RAM. We run each task with 10 random seeds and apply a timeout of 5 seconds per training example. We choose the number of epochs used for each technique based on when training saturates. For MNIST tasks, we use LeNet [19], a 2-layer CNN-based model, and we use similar architecture for HWF and leaf. For the scene task, we use YOLOv8 [30] and a 3-layer CNN to detect objects. We also select the sample count, a key hyperparameter used in IndeCateR and ISED, based on the task, with the goal of balancing the training time while also giving the frameworks enough samples to learn. We describe the choices of other hyperparameters as well as the task decompositions in Appendices C. and C.2.

---

Table 1: Test accuracy results for sum, and add,, The reference approximates the accuracy of neural predictor for MNIST images with 0.99 accuracy using 0.99" for sum, and 0.992n for add,,
Accuracy (%)
Method
Suma
sumg
Sum2266
Suml11244
add;
add4
add1a
add100
Scallop
8.43
TO
TO
TO
95.3
TO
TO
TO
DSL
2.19
0.78
TO
96.6
93.5
77.1
25.6
IndeCateR
83.01
44.43
0.51
0.60
93.3
89.0
69.6
6.4
ISED
73.50
1.50
0.64
ERR
93.1
89.71
0.0
0.0
A-NeSI
17.14
10.39
0.93
1.21
96.0
92.1
76.8
ERR
CTSketch (Ours)
83.84
47.14
7.76
2.73
96.7
92.51
74.8
23.5
Reference
85.15
52.56
7.63
0.003
96.06
92.27
73.97
13.40
CTSketch
Scallop
DeepSoftLog
IndeCateR
1 ISDD
A-NeSI
100
Accuracy (5))
75
50
25
SutM1024
add ado
Visudog
sudoku
hwf
leaf
Scene
Test accuracy results for sum1021. add100. visudog, sudoku, HWF, leaf, and scene tasks. "X" indicates that there was timeout, there was an error/overflow. or the given task was not able to be programmed in the framework. Error bars show standard deviations.
Figure 3:
4.3 RQI: Scalability
To answer RQ1, increase the number of inputs to the sum, task up 1024, which is orders of magnitude larger than previously studied input spaces. We report the sum, results for E {16, 64, 256, 1024] in Table and full results with standard deviations in Table 4 of Appendix C.3. The reference refers to the lower bound of accuracy when the neural predictor is supervised per-input to do individual digit recognition, computed 0.99*
CTSketch is the best performer on all n 2 16 and is the only method to consistently match the reference. All baseline methods fail learn sumg56. whereas CTSketch also works for sum1024- Even with very weak supervision on only the final sum of 1024 digits, CTSketch attains a per-digit accuracy of 93.69%. Although A-NeSI reaches similar accuracy, its per-digit accuracy stays at 17.92%, implying that the result due to small dataset size and redundant use of training images.
While IndeCateR is overall the next best method, it faces limit at 256 inputs and struggles even with 25,600 samples per example. ISED requires the most computational resources and exceeds the machine availability for n 2 64 using the same sample count as IndeCateR. We reduce the sample count to 6,400 and 1,024 for sumg1 and sum256. respectively, resulting a significant performance drop. We report eтrоr (ERR) for sum1024 since even sample count of one does not work.
Scallop, DSL, and A-NeSI are unable learn efficiently from sum16. Scallop times out with top-1 proofs for n 2 64 since there are exponentially many input combinations to consider. By manually embedding the exact WMC inference, DSL attains the highest accuracy for sum, However, the exact inference times out for sum and we use the alternative of training a surrogate neural network to predict the inference results. This neural embedding unable to achieve high accuracy and eventually times out. A-NeSI also attempts to do neural approximation and similarly struggles to learn the inference model due to limited supervision.
4.4 RQ2: Accuracy
We compare the test accuracy of CTSketch with the baselines across tasks from the neurosymbolic learning literature. We summarize the results of visual sudoku (visudo), sudoku, hwf, leaf, and scene
7

---

CTSketch
IndeCateR
A-NeSI
4
Full
0.8
0.8
Accuracy
0.6
Accuracy
0.6
0.4
0.4
0.2
0.2
0
0
0
200
400
0
2,000
4,000
Time (seconds)
Time (seconds)
Figure 4: Accuracy vs. Time for add1s for IndeCateR, A-NeSI, and CTSketch.
Figure 5: Accuracy vs. Time for different
ranks p E {2, 4, 8, full).
in Figure 3, and we report the results for add,, Table Full results with standard deviations can be found in Tables and 5 (Appendix C.3). CTSketch is the highest performer 4 tasks, including visudog, sudoku, and scene. Of all tasks which CTSketch does not obtain the highest accuracy, the largest difference in accuracy is in visudo,, where CTSketch comes within 2.55% of A-NeSI. Furthermore, for every add,, task, CTSketch comes within 5.42% of the reference accuracy (of 0.99 accuracy MNIST predictor) but often above the reference. These results demonstrate that though CTSketch designed for scalability, it can still solve a variety of classic neurosymbolic tasks.
No other baseline performs consistently well as CTSketch across the benchmark tasks. Scallop times out of of the tasks and cannot encode the leaf and scene tasks due to their use of GPT-4. The REINFORCE- Casssed techniques, IndeCateR and ISED, do not scale as well as CTSketch because they cannot get strong enough learning signal with the specified sample count. IndeCateR lags behind on sudoku and scene, and ISED struggles with scaling to visudog and add,, for large values of A-NeSI performs poorly on complex reasoning tasks like sudoku, and hwf and exhibits high variance. This is because A-NeSI trains additional neural network to estimate the WMC result, and learns best when there a stronger supervision than what is provided in some tasks. For example, A-NeSI scales well for add, where provide per-digit supervision for the multi-digit output, but fails to scale for tasks like sum1024 where there weaker supervision on the final output.
4.5
RQ3: Computational Efficiency
We compare CTSketch to the baselines in terms of the test accuracy over training time tasks: add and add and present the results Figure 4 and Figure (Appendix C.3). While per-epoch accuracy improvement for CTSketch is not always the largest, CTSketch learns far faster than the baselines because of how efficiently performs inference: the average epoch times for add and add100 are 1.70 and 0.92 seconds, respectively. The next fastest methods for add1s were IndeCateR, taking 23.07 seconds, and A-NeSI, taking 52.72 seconds per epoch on average. While DSL shows comparable accuracy to CTSketch minutes per epoch. For some tasks, such as add100. CTSketch converges before DSL even completes training epoch. We attribute this difference the efficiency of inference. While other techniques require training a prediction network (as in A-NeSI) or learning neural embedding (as in DSL), CTSketch requires only short sequence of tensor operations perform inference.
these tasks, its learning prohibitively slow, taking over 20
In our experiments, overhead requirement initializing and sketching sub-program summaries very low, taking less than one minute across all tasks. This demonstrates that the overhead of sketching is negligible when considering the performance improvement it provides, allowing for extremely efficient inference and fast convergence.
4.6 RQ4: Sketching Rank
We study how the rank sketching affects the accuracy and training time with the HWF task. We vary the rank p E {2, 4, 8, full) for sketching the largest tensor, which is of size 147, We plot accuracy against time Figure 5, where we mark the test accuracy for every 10 epochs during the first 1.5 hours of training. The comparison between the full rank and the others demonstrates the advantage of

---

sketching: when an appropriate rank is used, CTSkkttch can converge much faster without sacrificing accuracy. While the training time for single epoch is similar across the lower ranks, it takes about twice the time using full rank. Consequently, while the rank-8 tensor converges to 95% accuracy in 70 minutes, the full rank tensor still around 80% after 90 minutes.
The learning curve for rank 2 implies that the rank should be sufficiently large, or the neural network will fail to learn the optimal weights even with more training. We see time and space trade-offs in ranks 4 and 8. Since the number of entries for the sketched tensor is (5p² + 2p) x 14, rank 8 requires 3.82 times more memory, but takes 30% less time to reach 90% accuracy. This demonstrates that training is not particularly sensitive to the choice of the rank, and can be chosen flexibly depending on the available resources. It is useful to consider both the reconstruction error || ~11 and the maximum difference MAX((T - ø)) when deciding the rank. For example, the maximum error is above 60 for the rank-4 approximation. Still, the model manages to learn as the reconstruction error is around 0.07, which corresponds to all entries in the tensor only differing by le-5.
Limitations and Future Work
The primary limitation of CTSketch lies in requiring manual decomposition of the program component to scale. When the full program summary tensor is computationally affordable, CTSketch is always applicable. However, when the input and output spaces are large, program decomposition is needed to fit program summaries in memory (Appendix D.1). The decomposition must be specified by the user, which may be difficult or impossible for complex tasks. In this sense, CTSketch can be viewed as a restrictive "language" in which not all tasks can be encoded. This motivates future work on automating the decomposition, possibly using program synthesis techniques.
Furthermore, it would be interesting to explore different tensor sketching methods and the trade-offs they provide, extending upon the initial results in Appendix D.2, where we compare TT-SVD against CP [13]. Tucker [16], and Tensor Ring [37] decomposition methods. When using these methods, we initialize the tensor summary by enumerating all possible input combinations upfront, before sketching. If we instead use a streaming tensor sketching method, we would iteratively refine the sketches with a subset of input-output pairs at each iteration. A small amount of time overhcad to update the sketches would result in a significant reduction in memory.
Related Work
Neurosymbolic WMC techniques. These frameworks provide techniques for computing the exact or approximate WMC result for a given input distribution and program. [36] proposed semantic loss function for learning with symbolic knowledge, which measures how well neural network outputs satisfy a given constraint using sampling for the WMC approximation. DeepProbLog [25] performs the exact WMC computation during inference, making it prohibitively expensive to use for complex tasks. Scallop [21] offers a more scalable solution by using provenance semirings that determine which proof terms to drop in the WMC approximation. Other solutions focus on treating the symbolic component as a black-box that can be written in any language; ISED [31] uses sampling procedure, and A-NeSI [32] trains an additional neural network, to approximate the WMC result. While CTSketch and these methods both learn with a WMC estimate, CTSketch takes a different approach by performing inference using sketched tensor summaries. Inference in CTSketch does not aggregate proofs through a logic program (as in Scallop and DeepProbLogg) or requires weight optimization of the approximation model (as in A-NeST), resulting in more efficient learning.
Other logic programming frameworks. Other logic programming neurosymbolic techniques solve the learning problem without any exact or approximate weighted model counting during inference. [26] proposed extending DecpProbLog with an approximate inference technique, called DPLA* * which involves an -like search to obtain small set of best proofs for given query. DeepStochLog [35] uses stochastic (rather than probabilistic) logic programming to encode neurosymbolic programs and uses SLD resolution to get the probability of deriving a certain goal. On the other hand, DeepSoftLog [23] uses soft-unification to integrate embeddings into probabilistic logic programming. DeepSeaProblogg [11] also extends DeepProbL.og by offering support for discrete-contee conciinte-ooniuuuus random variables and uses weighted model integration, which can handle infinite sample spaces unlike weighted model counting. Abductive learning techniques [5, 14], which often use Prolog for the

---

symbolic component, offer an alternative solution that learns by by abducing aseudo-labed from ground truth labels. These works use logic programming languages to encode the program component. unlike CTSketch which represents the program component with tensor summaries.
Arithmetic and probabilistic circuits. Arithmetic and probabilistic circuits (ACs and PCs) enable probability distributions to be computed in a fully differentiable manner with a combination of sum and product nodes [6. 7, 8]. This differentiability property makes them suitable for encoding the reasoning layer in neurosymbolic architectures. For example, a Semantic Probabilistic Layer has been proposed to integrate neural networks with logical constraints encoded as PC and has been applied to tasks such as pathfinding [36]. However, one challenge with ACs and PCs in neurosymbolic difficult run them on modern tensor accelerators. To solve this problem. PyJuice has been proposed as general implementation design for running inference through PCs on the GPU [22]. Additionally knowledge layers (KLay) are a data structure for ACs that can be parallelized on GPUs [24]. Like ACS and PCs, decomposed program summaries in CTSkktcc also aim to make inference through the symbolic component fully differentiable. However, inference in CTSketch does not need additional data structures to improve efficiency since it uses only simple tensor operations that can already be performed on the GPU, and allows for tensor sketching to improve memory efficiency.
learning is that
Other neurosymbolic techniques. There also exist neurosymbolic techniques that do not require the program component to be specified as logic program. IndeCateR [9] offers a lower variance gradient estimator than REINFORCE [34] and can scale complex black-box neurosymbolic programs. NASR [4] is REINFORCE-styl algorithm suited for fine-tuning models such as neural Sudoku solvers and scene graph predictors. ISED [31] also falls under this category of techniques that treat the neurosymbolic program as black-box. While CTSketch is compatible with black-box programs, as in the leaf and scene tasks, the algorithm benefits from decomposing the symbolic component when there are many inputs. This allows CTSketch to scale far better than existing black-box frameworks, but it requires manual effort to decompose complex tasks.
Additionally, PLIA, [10] speeds up linear integer arithmetic by representing probabilistic integers as tensors and adapting FFT for sum operation, allowing efficient neurosymbolic inference. While PLIA, relies on tensor operations and decomposition of problems for scalability, similar to CTSketch, its applicability limited to programs expressible using integer arithmetic. Terpre'T' [12] a compositional rule framework that learns programs by inferring each instruction and its arguments sequentially. While program decomposition central to both TerpreT and CTSketch, TerpreT is designed for inductive program synthesis whereas CTSketch is a neurosymbolic learning algorithm for training the neural component by backpropagating the gradient through the symbolic component.
Conclusion
We proposed CTSketchh a framework that uses decomposed programs to scale neurosymbolic learning. During inference, CTSketch uses sketched tensors, each representing the input-output summary of a sub-program, to efficiently approximate the output distribution of the symbolic component with simple tensor operations. We provide theoretical justification for our architecture and derive an error bound on the approximation. Our results show that CTSketch pushes the frontiers of neurosymbolic learning by solving previously unattainable tasks, such as adding one thousand handwritten digits.
Acknowledgments and Disclosure of Funding
We thank the anonymous reviewers for the useful feedback. This research was supported by ARPA-H grant D24AC00253-00 and NSF award CCF 2313010.
References
[1] 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 Workshop on Neural-Symbolic Learning and Reasoning (NeSy), Windsor, United Kingdom, 2022.
10

---

[2] Mark Chavira and Adnan Darwiche. On probabilistic inference by weighted model counting. Artificial Intelligence, 172(6):72-799. 2008.
[3] Siddharth Singh Chouhan, Uday Pratap Singh, Ajay Kaul, and Sanjeev Jain. data repository of leaf images: Practice towards plant conservation with plant pathology. In 2019 4th International Conference on Information Systems and Computer Networks (ISCON), pages 700-707, 2019.
[4] Cristina Cornelio, Jan Stuchmer, Shell Xu Hu, and Timothy Hospedales. Learning where and when reason in neuro-symbolic inference. In International Conference Learning Representations, 2023.
[5] Wang-Zhou Dai, Qiuling Xu, Yang Yu, and Zhi-Hua Zhou. Bridging machine learning and logical reasoning by abductive learning. In Proceedings of the 33rd International Conference on Neural Information Processing Systems, 2019.
[6] Adnan Darwiche. On the tractable counting of theory models and its application to truth maintenance and belief revision. Journal of Applied Non-Classical Logics, 11, 04 2000.
[7] Adnan Darwiche. Decomposable negation normal form. J. ACM, 48(4))608-666 647, July 2001.
[8] Adnan Darwiche. differential approach inference in bayesian networks. ACM, 5063):280-305, May 2003.
[9] Lennert De Smet, Emanuele Sansone, and Pedro Zuidberg Dos Martires. Differentiable sampling of categorical distributions using the catlog-derivative trick. In Proceedings of the 37th International Conference Neural Information Processing Systems, volume 36, pages 30416 - 30428, 2023.
[10] Lennert De Smet and Pedro Zuidberg Dos Martires. A fast convoluted story: Scaling proba- bilistic inference for integer arithmetics. In A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tomczak, and C. Zhang, editors, Advances in Neural Information Processing Systems, volume 37, pages 102456-102477 2024.
[11] Lennert De Smet, Pedro Zuidberg Dos Martires, Robin Manhaeve, Giuseppe Marra, Angelika Kimmig, and Luc De Readt. Neural probabilistic logic programming in discrete-continuour domains. In Proceedings of the Thirty-Ninth Conference on Uncertainty in Artificial Intelligence, volume 216, pages 529-538, 2023.
[12] Alexander L. Gaunt, Marc Brockschmidt, Rishabh Singh, Nate Kushman, Pushmeet Kohli, Jonathan Taylor, and Daniel Tarlow. Terpret: A probabilistic programming language for program induction, 2016.
[13] Richard A. Harshman. Foundations of the PARAFAC procedure: Models and conditions for an explanatory multimodal factor analysis. PhD thesis, University of California, Los Angeles, 1970.
[14] Hao- Yuan He, Hui Sun, Zheng Xie, and Ming Li. Ambiguity aware abductive learning. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp, editors, Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 18019-18042, PMLR, 21-27 Jul 2024.
[15] Jiani Huang, Ziyang Li, Binghong Chen, Karan Samel, Mayur Naik, Le Song, and Xujie Si. Scallop: From probabilistic deductive databases to scalable differentiable reasoning. In Advances in Neural Information Processing Systems, volume 34, pages 25134-25145. 2021.
[16] Tamara G. Kolda and Brett W. Bader. Tensor decompositions and applications. SIAM Rev.,
51 51:455-500, 2009.
[17] Jean Kossaifi, Yannis Panagakis, Anima Anandkumar, and Maja Pantic. Tensorly: Tensor learning in python. Journal of Machine Learning Research (JMLR), 20(26), 2019.
[18] Daniel Kressner, Bart Vandereycken, and Rik Voorhaar. Streaming tensor train approximation. SIAM Journal on Scientific Computing, 45(5):A2610-A2611, 2023.

---

[19] Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):227--233 23244, 1998.
[20] Qing Li, Siyuan Siyuan Huang, Yining Hong, Yixin Chen, Ying Nian Wu, and Song Chun Zhu, Closed loop neural-ymmbolic learning via integrating neural perception, grammar parsing, and symbolic reasoning. In Proceedings of the 37th International Conference on Machine I Leurning. page 5884-5894, 2020.
[21] Ziyang Li, Jiani Huang, and Mayur Naik. Scallop: A language for neurosymbolic programming. Proc. ACM Program. Lang., 7(P.DI), June 2023.
[22] Anji Liu, Kareem Ahmed, and Guy Van Den Broeck. Scaling tractable probabilistic circuits: systems perspective. Proceedings of the 41st International Conference on Machine Learning, 2024.
[23] Jaron Maene and Luc De Raedt. Soft-unification deep probabilistic logic. In Proceedings of the 37th International Conference on Neural Information Processing Systems, volume 36, pages 60804 60820, 2023.
[24] Jaron Maene, Vincent Derkinderen, and Pedro Zuidberg Dos Martires. Klay:: Accelerating arithmetic circuits for neurosymbolic AI. In The Thirteenth International Conference on Learning Representations, 2025.
[25] Robin Manhaeve, Sebastijan Dumancic, Angelika Kimmig, Thomas Demeester, and Luc De Raedt. Deepproblog: neural probabilistic logic programming. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS' 18, page 3753-3763,
2018.
[26] 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, 2021.
[27] Lukas Murmann, Michael Gharbi, Miik Aittala, and Fredo Durand. A multi-illumination dataset of indoor object appearance. 2019 IEEE International Conference on Computer Vision (ICCV), Oct 2019.
[28] Ivan Oseledets. Tensor-train decomposition. SIAM Scientific Computing, 33:2295- -2117, 01 2011.
[29] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agar- wal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, Gretchen Krueger, and Ilya Sutskever. Learning transferable visual models from natural language supervision, 2021.
[30] Joseph Redmon, Santosh Divvala, Ross Girshick, and Ali Farhadi. You only look once: Unified, real-time object detection. 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 779-788, 2016.
[31] Alaia Solko-Breslin, Seewon Choi, Ziyang Li, Neelay Velingker, Rajeev Alur, Mayur Naik, and Eric Wong. Data-efficient learning with neural programs. In Advances in Neural Information Processing Systems, volume 37, pages 14669, 2024.
[32] Emile van Krieken, Thiviyan Thanapalasingam, Jakub Tomezak, Frank van Harmelen, and Annette Ten Teije. A-nesi: A scalable approximate method for probabilistic neurosymbolic in- ference. In Proceedings of the 37th International Conference on Neural Information Processing Systems, volume 36, pages 24586 24669,, 2023.
[33] Po- Rei Wang, Priya L. Donti, Bryan Wilder, and Zico Kolter. Satnet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver. In International Conference on Machine Learning, 2019.
[34] Ronald J. Williams. Simple statistical
algorithms for connectionist reinforce-
ment learning, Machine Learning, ((3-4):229-256) 1992.
12

---

[35] Thomas Winters, Giuseppe Marra, Robin Manhaeve, and Luc De Raedt. Deepstochlog: Neural stochastic logic programming. Proceedings of the AAAI Conference on Artificial Intelligence. 36(9):10000-11000 2022.
[36] Jingyi Xu, Zilu Zhang, Tal Friedman, Yitao Liang, and Guy Van den Broeck. A semantic loss function for deep learning with symbolic knowledge. In Proceedings of the 35th International Conference Machine Learning, pages 5502-5511, 2018.
[37] Qibin Zhao, Guoxu Zhou, Shuhui Xie, Long Zhang, and Andrzej Cichocki. Tensor ring decomposition. In Proceedings of the 33rd International Conference on Machine Learning (ICML), pages 2016-2025, 2016.
13

---

A Pseudocode
Without loss of generality, we assume the pseudocode that there is only one program in each layer to simplify the notation. For example, we decompose the sum; program to consist of three layers, each with sub-programs C1, C2, and C32 instead of two layers as in Figure
Algorithm 1 CTSketch training algorithm
Require:
Symbolic programs c1..... Cm where takes d, inputs and outputs E [Y]], neural network Mp. loss function L, and training dataset 2)
function TRAIN(D)
for i = 1.... m7 do t ......: dd INITIALIZE(c)
end for
for ((x), (........ Inn 11) do (p)..... .........))) f- Mo(Ti,...,.e8 Fnn
for
1,..., m do (P1..... .Pd.) t INPUTS(c))
02 = E1p1 |1 [x]
for k
2. de do
lpal
end for
for j
1, Y do [b] - RBF(
p
end for p f- 1)
end for I <- + L(Um,y) v) end for optimize and update 0
end function
B Approximation Error Proof
Suppose that we sketch d with TT-SVD, i.e., (4 (Li,..., 1)) SKETCH (d)), where the sketching rank is p. Let T/ be the reconstruction of é; using the sketches.
Theorem 3.2 (CTSketch error bound). The error the output distribution satisfies
1 p pll S /2/pp|r|441 Til
(B.1)
Proof. With some rearranging and by definition of the L.2 norm, we have
10000p p- - T, pl1a = !1 - -
(B.2)
((000 T.OH) 1)
(B.3)
DEY
Applying the Sauchy-Schwarry incquality to the inner product, we obtain
<
11 [ (,
(B.4)
DeY
= |lplIF
(1 T. :...,,.........11.1
(B.5)
DeY
= =IIp|IF
(0 T ) . Fd. 2]
(B.6)
JEY Pi
14

---

Note that if | (rl....... .al -ral-Tarr -T(ri...... .et.......... rall 2 0.5, then the one-hot encodings 6f " exactly two positions, which results in a squared difference of Pulling this factor out, we obtain the desired result.
[ri... ra differ
= -llllr
2
Σ
[(| .aa Ti .rall 2 0.5)
(B.7)
Pinurr
By rearranging the definition of ||ov Tell. the maximum, i.c. worst case, number of .I...... such that ( Ti(r....... rall 0.5 is
| Tille
[4ll T
0.5
s llpllyy 2 [4|10 7-
(B.8)
2 [lrllr|4/1e
1
(B.9)
C Experiment Details and Complete Results
C.1 Experimental Setup and Hyperparameters
Unless stated otherwise, we keep the optimizer, training epochs, and batch size consistent across methods, and use the best learning rate among (le-3, 5e-4, 2e-4, 1e-4, 5e-5). For neural-GPT experiments, leaf classification and scene recognition, we copy the model, prompt and configuration from the original paper [31] where the tasks were introduced. The hyperparameters used for CTSketch are summarized in Table 2.
Table 2: Hyperparameters used in CTSketch for the benchmark tasks
hyperparameter
visudo
sudoku
hwf
leaf
scene
sum,
add,
optimizer
Adam
Adam W
Adam
Adam
Adam
Adam
Adam
learning rate
1e-3 / 5e-4
5e-6
le-4
le-4
5e-4
le-3 / 5e-4
1e-3
training epochs
1000
5000
10
150
100
50
100 / 150
100 / 300
batch size
20
256
16
16
16
16
64
sketching rank
full
full
full
full
For the baseline methods Scallop, IndeCateR, ISED, A-NeSI, and DeepSoftLog we use:
Visual Sudoku. We use top-3 semiring for Scallop and learning rate 2c-4. We use 20 x N x 2 samples for IndeCateR, and learning rates 2e-4 and 5c-5 for 4x4 and 9x9 board, respectively. We use the same sample count for ISED and learning rates le-3 and 5e-4. For A-NeSI, we copy the hyperparameters used their paper for this task.
MNIST Sum. For Scallop, we again use top-3 proofs and le-4 learning rate. For IndeCateR and ISED, we use sample count of 100 n. For IndeCateR, we run for 300 epochs, using batch size 10 learning rates le-3 and 5e-4. We use learning rates le-4 and 5e-5 for ISED, and reduce the sample count to 6400 and 1024 for sumg4 and sum256- For DSL and A-NeSI, we copy the parameters used for MNIST-Ade tasks in their papers. In the case of DSL, we use the neural embeddings for sumie with learning rate 1c-3 and le-5 weight decay. For A-NeSI, we decrease the learning rate to 5e-4, 2c-4, and lc-4 for 64, 256, 1024. Due memory constraints, also reduce the embedding size from 800 to 400 for r 1024.
Multi-digit Addition. For Scallop, we again use top-3 proofs and 1e-3 learning rate, and we use 30 epochs. For IndeCateR, we use sample count of 10 and le-3 learning rate. We train for 15 epochs for all values of except 100, where we use 45 epochs. These are the points when training saturates and accuracy starts to drop slightly with additional training. For ISED, we use sample count of 100 and le-4 learning rate. We train for 10 epochs because this is when training saturates. For A-NeSI and DeepSoftl.ao Log, we use the same hyperparameters used in their evaluation that have been optimized for multi-digit addition.
15

---

C.2 Task Decompasition
MNIST Sum. These tasks involve adding n digits, where n is some power of 2. As a result, we structure the decomposition as a tree with (ogz(n) layers. Each @; takes two inputs, each being integers between 0 and 9 2 + 1, and the result the sum of the two inputs. Therefore, the shape of d; is (9* 2 + +1 x (9 # 2 + 1), and its entries are the sum of the indices. Concretely, (a b]
b.
Multi-digit Addition. These tasks involve adding two n-digit numbers. We structure the decomposi- tion as a chain of adds and carries. Φ1 is the same as the first layer in MNIST sum, which takes 2 digits as inputs, and the possible outputs are 0- 0-18. 18. For each place in the n-digit numbers, we add the two digits using Φ1 in the first layer. For each of the n layers after this, we define o; as the earry sum, taking two inputs: the result of the current place sum and the result of the previous place's carry sum. The idea is that if the previous carry sum results in a 2-digit number, we earry over 1, and the current place sum predictions get incremented by 1. This means each Φ is 19 20 tensor, with the first 10 column entries equal to the row index, and the last 10 column entries equal to one plus the row index.
Visual Sudoku. We decompose the task of determining whether the input is a valid sudoku board into pairwise comparisons of the cells. The cells in the same row, column, or block need to have distinct values, which leads to total of n 56 and 810 comparisons for 4 x 4 and 9 x 9 sudoku boards, respectively. Hence, the program consists of single layer with n instances of Φ such that o[i,j] = = j. where N E {4,9).
N
Sudoku Solving. For single row, column, block in Sudoku board, if eight cells filled with distinct values, the remaining one cell is uniquely defined as some value e E [1, 9]. Using this idea, decompose the Sudoku solving task into multiple instances of a program that computes the value v given eight other values in the row, column, or block. We iterate through each cell, resulting in total of 3 x 81 instances. We allow the inputs to be 0, meaning that it is unfilled and could be any value n. E [1, 9]. Note that the program is no longer a one-to-one mapping between the inputs and the output. For instance, if the eight inputs are all zeros, the output can be between and 9. To encode one-to-many relationship we use gOH. 10 x ... x 9, such that g [nl,.... n8, v + 1] = for all satisfying the constraint. The case where (nl,..., n8) contains redundant values is naturally ignored as gffl fnl..... n8, :] becomes an all-zero vector.
Handwritten Formula. The HWF architecture uses only layer, but we initialize 4 different o; tensors corresponding to each possible formula length (1, 3, 5, and 7). Since there are 14 possible symbols (10 digits and 4 arithmetic operators), &; has the same number of dimensions the corresponding formula length, and each dimension has size 14. Each entry represents the real-valued output of the evaluated formula, and invalid formulas correspond to output of O.
Leaf Identification and Scene Classification. For these tasks that use GPT-4, the model internals are unknown, so we do not decompose them and instead initialize single tensor summarizing the program. For the leaf task, there are 3 features (margin, texture, and shape) taking on 3, 3, and possible values, respectively. The output values task the object detector YOLOv8 returns a maximum of 10 objects per image, where each can be one of the 45 classes. The output values are one of the 9 possible room types.
one of the 11 possible leaf species. For the scene
C.3 Full Experimental Results
We report full experimental results with I-sigma standard deviation in Tables 3, 4, and 5, and plot test accuracy against training time add100 task in Figure 6. Note that the training for CTSketch converges before the first epoch DeepSoftLog and ISED.
Table 3: Test accuracy on traditional neurosymbolic benchmarks.
Accuracy (%)
Method
visudo;
visudog
sudoku
hwf
leaf
scene
Scallop
84,92 1 3.11
TO
TO 66.50 1.37
96.65 1: 0.13
N/A
N/A
IndeCateR
87.20
2.14
81,92 2.11
95.08
0.41
69.16 2.35
12.72 2.51
ISED
79.40 1 3.36
50.0
1 0.0
80.32
1 1.79
97.34
0.26
79.95
5.71
68.59 1 1.95
A-NeSI
91.90 1 1.90
92.11
1 1.71
26.36
1 12.68
3.13 1 0.41
72.40
1 12.24
61.46
1. 14.18
CTSketch (Ours)
89.35 1 2.45
92.50 1 1.81
81.46 1 0.53
95.22 1 0.61
74.55
5.42
69.78
1.52
16

---

Scallop Table 4: Test accuracy results for sum.. predictor with 0.99 accuracy using 0.99".
The reference approximates the accuracy of an MNIST
Accuracy (%)
Method sum4
s
sum64
Sum2256
Sum1104
Scallop
88.90 + 10.78
8.43 = 1.56
тO
TO
TO
DSL
94.13 0.82
2.19 0.51
0.78 + 0.32
TO
TO
IndeCateR
92.55 + 0.87
83.01 + 1.18
44.43 + 10.19
0.51 + 0.34
0.60 + 0.23
ISED
90.79 + 0.81
73.50 + 2.73
1.50 + 0.34
0.64 + 0.26
ERR
A-NeSI
93.53 0.35
17.14 2.87
10.39 + 0.92
0.93 + 0.80
1.21 + 1.28
CTSketch (Ours)
92.17 + 0,43
83.84 + 0.92
47.14 + 3.29
7.76 + 1.43
2.73 + 0.81
Reference
96.06
85.15
52.56
7.63
0.003
Table 5: Test accuracy results for add,, The reference approximates the accuracy of an MNIST predictor with 0.99 accuracy using 0.992" For DSL and A-NeSI, we report the results from [23].
Accuracy (%)
Method add
add2
add4
add15
add100
96.9 0.5
95.3
TO
TO
TO
DSL
9.14
9.3
93.5
77.11.0
2.4
IndeCateR
97.7
93
8.1
69.6
6.4
ISED
91.4
933
8.1
0.0
0.0
A-NeSI
9..4
965
92.1
7.8
ERR
CTSketch (Ours)
98.3 +
96.7 0.4
92.5 + 1.1
74.8
23.5 + 4.9
Reference
98.01
96.06
92.27
73.97
13.40
CTSketch
IndeCateR
Accuracy
0.2
0.1
20
40
60
80
100
120
140
160
Time (seconds)
Figure 6: Accuracy vs. Time for add1o0 for IndeCateR and CTSketch.
D Additional Ablation Studies
D.1 Decomposition and Sketching
We compare the gains of program decomposition and tensor sketching for CTSketch using the sum16 task. We vary the level of decomposition and compare accuracy, per-digit accuracy, and per-epoch training time for using full-rank tensors against rank-2 sketches in Table 6.
For the same decomposed program structure, we observe that sketching offers substantial memory savings, albeit with some loss in accuracy. When scaling to highesodimensional input spaces, memory becomes critical bottleneck program decomposition alone often insufficient, which highlights the necessity of tensor sketching for scaling. Within full-rank, the gains from greater degree of
17

---

decomposition are clear, both in terms of training time and memory efficiency. However, this trend reverses with sketches, due the use of the RBF kernel the output each program layer.
Table Ablation on gains of program decomposition and tensor sketching using sum16- For Dims, 16 refers decomposition, whereas (8, refers to 2-layer decomposition into two sum-8 the first layer and a sum-2 at the second layer. Method refers to different inference procedures, where SKETCH rank-2 sketches, FULL uses one-hot program tensors of (Equation 3.6), and FULL + RBF use program tensors Φ with RBF kernel (Equation 3.3). OOM refers to out-of-memory.
Method
Dims
# Entries
Accuracy (%)
Digit Accuracy (%)
Time(s)
SKETCH
16
600
83.52
98.86
1.72
8,2
572
83.88
98.90
2.11
4, 4
588
83.25
98.85
2.57
2, 2, 2,
556
82.51
98.78
3.88
FULL
16
1.45 X 1
OOM
OOM
OOM
8,2
7.30
109
OOM
OOM
OOM
4,4
2.72 10a
85.59
99.01
17.66
2, 2, 2,
8.88 10
85.80
99.04
2.0139
+ULL RBF
16
1.00 x 10t6
OOM
OOM
OOM
8,2
1.00 10a
83.29
98.85
17.63
4,4
1.88
106
83.62
98.89
2.15
2, 2, 2
7.18 103
82.53
98.80
3.81
D.2 Tensor Sketching Methods
We compare the performance of tensor sketching methods Tensor-Train, CP [13], Tucker [16], and Tensor Ring [37] on sum4 and HWF in Table 7. While our method is not sensitive to the employed method, CP decomposition may insufficient for complex input-output relationships, such as HWF, due to its restrictions rank- tensors. Our experiments Tensor- Train decomposition, which is not the best performer in terms of accuracy, but is competitive while requiring less space.
Table 7: Test accuracy on different tensor sketching methods on sum, and HWF tasks.
sum4
HWF
Method
Accuracy (%)
# Entries
Rank
Accuracy (%)
Entries
Rank
Tensor Train
92.17 = 0.43
40
2
95.22 0.61
1344
CP
92.33 + 0.59
40
2
72.90 17.40
1568
Tucker
92.31 + 0.62
44
2
95.29 = 0.92
16776
4
Tensor Ring
92.58 + 0.58
80
2
95.47 = 0.51
1568
E License Information
To test the baselines, we used code from the official repositories of Scallop [15] (MIT), DeepSoftLog
[23] (MIT), IndeCateR [9] (Apache 2.0), ISED [31] (MIT), and A-NeSI [32] (MIT). Additionally, for CTSketch, we used the implementation of TT-SVD from the python package tt-sketch [18] (CC BY-NC-ND 4.0) and cp. tucker, tensor ring decompositions from tensorly [17] (BSD 3-Clause).
We used several datasets in our evaluation, namely the Multi-illumination dataset [27] (CC BY 4.0), the handwritten formula dataset (CC BY-NC-SA 3.0) from NGS [20], and subset of the leaf database [3] (CC BY 4.0). As part of the scene task experimental setup, we used YOLOv8 [30] (AGPL-3.0) and CLIP [29] (MIT).
18

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
The abstract and introduction claim that our proposed neurosymbolic learning algorithm (CTSketch) scales to tasks involving over one thousand inputs, while remaining competitive with the baselines on standard benchmarks. We demonstrate this by describing the overall test accuracy (and sometimes neural predictor accuracy) across all benchmarks and baselines in $4.3 and $4.4. Additionally, we argue that CTSketch is more computation- ally efficient than the baselines and provide justification for this in $4.5.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The limitations of the proposed method are stated in Section 5.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory assumptions and proofs
19

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: The paper contains one theorem, and the proof sketch and the full proof is presented in $3.3 and Appendix B, respectively.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: We release the code to reproduce the experimental results, including instruc- tions download the datasets and run each task.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access hosted model (e.g.. in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should be possible for other researchers to have some path to reproducing verifying the results.
20

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [Yes]
Justification: We release code for the experiments along with the instructions to access the data. We provide scripts to reproduce experiments for the baselines and the proposed method, and refer to relevant repositories if results were borrowed from prior works.
Guidelines:
The answer NA means that paper does not include experiments requiring code. Please see the NeurIPS code and data submission guidelines (https://nipp cc/
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to rum to reproduce the results. See the NeurIPS code and data submission guidelines (https: // //iips.co cct..cccppoo wwcppuulc///aeececcceeceeeeeeeee http//uuddese///ee
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: For each task, describe the train/test split in $4.1, and report the experimen- tal details, including hyperparameters and optimizers, in Appendix C.I.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification:
All experimental results are accompanied by I-sigma standard deviation.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
21

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: We specify the machine used for the experiments in $4.2, and compare training times in $4.5 and $4.6.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: http://eeeiipp.eeeee httttp/ss//rrrppss.cc//b//////it http:///../...tctttccciiieeellll
Answer: [Yes]
Justification:
The authors have reviewed and conformed the Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g.. if there special consid- eration due to laws or regulations in their jurisdiction..
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is societal impact of the work performed.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
22

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), faimess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best. faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: For datasets, code, and pretrained models used in evaluation, cited the original papers and provided the license information in Appendix E.
Guidelines:
The answer NA means that the paper does
existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
23

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/dataseta has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We include the code for the proposed learning algorithm in the supplementary material, and we intend to release the code publicly upon acceptance. The code is well- documented with license and training information, and the limitations of our proposed algorithm are mentioned in Section 5.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
24

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The usage of LLMss was not an important, original, or non-standard component of the core methods in this research.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy (https / /ttp://neeui.peeeeeee www.rrpp.cc/ooofeeeeeececoccmmoe wwt/oc/e///neeeeeeeeeeeeeeeeeeee cc//oomferrncee/22255LLMM for what should or should not be described.
25


Reviews:
[{"review_id": "CCBiUQpSbH", "reviewer": "Reviewer_hw4L", "summary": "In this paper, the authors propose CTSKetch, a framework to efficiently train neuro-symbolic models by using only end-to-end training data (i.e., without intermediate supervision on the representations extracted by the neural component). To achieve this, CTSKetch summarizes all possible relations between inputs and outputs (the task semantics) in a single tensor, mapping inputs (representations extracted from the neural component) to outputs (labels). To tackle the potential combinatorial explosion in size of this tensor, the authors propose two remedies: decomposition of the full tensorized program into composable sub-programs and low-rank decomposition of task-tensors (TT-SVD is used in the paper but could be any low-rank decomposition as suggested in Future Work). The authors provide an approximate error bound (valid for when TT-SVD is used as LoRa approximation) for the proposed CTSKetch. Finally, the authors present experimental results on different well-known benchmark in the neuro-symbolic community (MNIST sum/addition, visual sudoku, sudoku solving, HVF, leaf identification and scene classification), showing that 1) it overall scales better compared to other baselines (e.g., increasing the number of operands in the sum), 2) it achieves competitive results in terms of task accuracy, and 3) it converges faster compared to other baselines.", "questions": "Please see weaknesses.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\nThe paper was overall well-written, and I enjoyed reading it. The idea of using low-rank approximation to avoid the instantiation of the full task tensor at one time in memory is nice, and so is the perpendicular contribution of decomposing the full task into a composition of sub-tasks. Furthermore, the authors provide a sufficiently wide range of experiments on the CTSKetch, with some statistical significance obtained by using multiple (10) seeds.\n\n**Weaknesses**\n\n- Different aspects of this submission do not fully convince me. Firstly, the manual decomposition of tasks necessary for scaling (also mentioned by the authors themselves, which I appreciate) seems indeed a significant limitation for the applicability of the method outside of the simple domains investigated in this work. You mentioned that program synthesis could potentially come to the rescue in that case. Could you argue more about it?\n\n\n- For my understanding, CTSKetch requires the explicit programming of the task tensor, which also sounds very limited in terms of scalability and applicability to broader domains. You mention in the paper that the construction of this vector could also be automated (using a subset of the training), but this would require labels for the intermediate representations, which would be against the initial proposition of working in an end-to-end setting.\n\n\n- On another note, for my understanding, using low-rank approximation allows the avoidance of the instantiation of the full (sub-) task tensor in memory. However, this still needs to be computed fully (see Equation between Lines 135-136). So, if from a computation perspective the LoRa approximation only worsens the efficiency, where do the improvements shown in Section 4.5 come? Is it only the decomposition of the full task into multiple subtasks? I suggest that the authors elaborate more on this regard in the manuscript to increase its soundness, possibly including additional ablations regarding the effect of the single components (LoRa approximation, sub-task decomposition) on both accuracy and computational efficiency for at least some of the investigated tasks.\n\n\n- More generally, I also question the generalizability of encoding the task semantics with a single input-output tensor, which is, by construction, only going to work with known input examples. For instance, a network trained on sum4 would not generalize to sum5 out of the box, requiring the manual extension of its entries to cover those examples which are not in $sum4 \\cap sum5$.\n\n\n- Regarding the writing, I think that the quality of the paper is acceptable, but some parts are not extremely clear (especially Sections 1 and 2) due to notation clutter or imprecise/verbose explanations. For instance, in Equation 2.1 what does p_i[r_i] refers to? Shouldn't it be sufficient to have \\sum p_i? In my understanding, p_i is already the distribution associated with r_i. Or also, I didn’t find Figure 2 helpful right now, while, for example, populating the matrices with actual values and guiding a bit more the readers with some captioning could really increase the effectiveness and helpfulness of this figure. Also, why in Figure 1 is the fourth digit separated from the others? Also, in Line 147, shouldn’t it be “Approximate Error Bound”?", "was_revised": true, "final_justification": "The idea is original. The clarifications and additional experimental results provided during the rebuttal solved some of my initial concerns about the work. However, I still have concerns regarding the scalability of the proposed approach beyond the very simplistic settings investigated in the paper. I also hope that the authors, in case of acceptance, will effectively spend time increasing the quality of the write-up, which in the initial submission was not exceptional.", "rebuttal": ">  You mentioned that program synthesis could potentially come to the rescue in that case. Could you argue more about it?\n\nAs a starting point for synthesizing decomposed programs, we asked Gemini 2.5 Flash how it would decompose Sum16: “How would you decompose the program that adds 16 digits, into a tree-based structure, using sub-programs that take as few inputs as possible…” Its response was the same as what we came up with:\n\n**Depth:** 4 layers (excluding the initial input layer).\n\n**Components:**\n- Layer 0 (Inputs): 16 single-digit inputs.\n- Layer 1: 8 ADD sub-programs. Each takes 2 single-digit inputs.\n- Layer 2: 4 ADD sub-programs. Each takes 2 multi-digit inputs from Layer 1.\n- Layer 3: 2 ADD sub-programs. Each takes 2 multi-digit inputs from Layer 2.\n- Layer 4 (Root): 1 ADD sub-program. Takes 2 multi-digit inputs from Layer 3.\n\nAfter two steps of prompting, we were also able to get a pairwise comparison decomposed program for Visudo. We think that LLMs could be a first step towards automating the decomposition process.\n\n> Firstly, the manual decomposition of tasks necessary for scaling (also mentioned by the authors themselves, which I appreciate) seems indeed a significant limitation for the applicability of the method outside of the simple domains investigated in this work.\n\nWe are also currently investigating CTSketch’s applicability to real-world domains such as predicting long-horizon sepsis from electronic health record (EHR) data. We are working on training a transformer to predict future EHR data from previous entries, and using a SOFA score program (which measures the severity of organ failure in a patient) with CTSketch to add an additional learning signal for predicting sepsis.\n\n> You mention in the paper that the construction of this vector could also be automated (using a subset of the training), but this would require labels for the intermediate representations, which would be against the initial proposition of working in an end-to-end setting.\n\nWe did not mean to imply that the construction of the task tensor would use a subset of the training data. What we meant was that the task tensor can use a subset of all possible structured input combinations, which doesn’t require any labeled data. For example, to initialize a sum2 tensor, we would need to know that the possible values (symbols) for both inputs are integers between 0 and 9, and we could sample some subset of the possible symbol combinations (and their corresponding outputs) to populate the summary tensor.\n\n> On another note, for my understanding, using low-rank approximation allows the avoidance of the instantiation of the full (sub-) task tensor in memory. However, this still needs to be computed fully (see Equation between Lines 135-136). So, if from a computation perspective the LoRa approximation only worsens the efficiency, where do the improvements shown in Section 4.5 come?\n\nDue to properties of tensor products, we can compute the value of the Equation between lines 135-136 without reconstructing the tensor.\n\n\\begin{align}\nv &= \\sum_a^{|R_1|} \\sum_b^{|R_2|} \\sum_x^2 {p_1}[a] {p_2}[b] {t_1}[a, x] {t_2}[x, b] \\\\\\\\\nv &= \\sum_x^2 \\left( \\sum_a^{|R_1|} {p_1}[a] {t_1}[a, x] \\right)  \\left(  \\sum_b^{|R_2|} {p_2}[b]  {t_2}[x, b] \\right) \\\\\\\\\nv &= ( p_1^\\top t_1 ) \\cdot ( t_2 p _2 )\n\\end{align}\n\n$p_1:|R_1|$ and $p_2:|R_2|$ are vectors representing probability distributions, and $t_1:|R_1|\\times 2$ and  $t_2:|R_2|\\times 2$ are rank-2 sketches. By rearranging the equation, we see that, instead of taking the output product of $t_1 \\times t_2$, we can obtain the result with  two vector-matrix multiplications and taking the inner product of the resulting vectors.\n\n> I suggest that the authors elaborate more on this regard in the manuscript to increase its soundness, possibly including additional ablations regarding the effect of the single components (LoRa approximation, sub-task decomposition) on both accuracy and computational efficiency for at least some of the investigated tasks.\n\nWe performed an ablation study on comparing the performance gains from program decomposition and tensor sketching with sum-16. We vary the level of decomposition and compare accuracy, per-digit accuracy, and per-epoch training time using full-rank vs rank-2 sketches. Here 16 refers to no decomposition, whereas (8, 2) refers to 2-layer decomposition into two sum-8 at the first layer and a sum-2 at the second layer. \n\n|Method|Dims|# Entries|ACC (%)|DIGIT ACC (%)|TIME (s)\n|-|-|-|-|-|-\n|**SKETCH**|16|$600$|0.8352|0.9886|1.7154\n||8, 2|$280, 292$ $(572)$|0.8388|0.9890|2.1066\n||4, 4|$120, 468$ $(588)$|0.8325|0.9885|2.5705\n||2,2,2,2|$40, 76, 148, 292$ $(556)$|0.8251|0.9878|3.8828\n|**FULL**|16|$10^{16}*{145}$|Out of Memory\n||8, 2|$10^8*{73}, 73^2*{145}$|Out of Memory\n||4, 4|$10^4*{37}, 37^4*{145}$ $(272123345)$|0.8559|0.9901|17.6586\n||2,2,2,2|$10^2*{19}, 19^2*{37}, 37^2*{73}, 73^2*{145}$ $(887899)$|0.8580|0.9904|2.0139\n|**FULL+RBF**|16|$10^{16}$|Out of Memory\n||8, 2|$10^8, 73^2$|0.8329|0.9885|17.6282\n||4, 4|$10^4, 37^4$ $(1884161)$|0.8362|0.9889 |2.1516\n||2,2,2,2|$10^2, 19^2, 37^2, 73^2$ $(7159)$|0.8253|0.9880|3.8092\n\nBy comparing the full-rank (FULL) and rank-2 sketches configurations under the same decomposition structure, we observe that sketching offers substantial space savings, albeit with some loss in accuracy. As we scale to higher-dimensional input spaces, memory becomes a critical bottleneck—program decomposition alone is often insufficient. This highlights the necessity of tensor sketching for scaling.\n\nWithin full-rank, the gains from greater degree of decomposition are clear, both in terms of training time and memory efficiency. However, this trend reverses with sketches, due to the use of the RBF kernel at the output of each program layer. For reference, we report results on using full-rank tensors with RBF kernels (FULL+RBF) which also show that  accuracy drops with more program layers.\n\n> More generally, I also question the generalizability of encoding the task semantics with a single input-output tensor, which is, by construction, only going to work with known input examples. For instance, a network trained on sum4 would not generalize to sum5 out of the box, requiring the manual extension of its entries to cover those examples which are not in sum4 \\cap sum5\n\nWe want to make it clear which components do and do not generalize to different tasks. It is true that a program summary tensor for sum4, representing the program’s discrete inputs and outputs, would not generalize to sum5. However, the same could be said for existing neurosymbolic approaches, i.e., a DeepProbLog program that sums 2 digits cannot be used to train sum4. However, the neural network used to train sum2 in CTSketch (with sketching) does generalize to sum4 at test time. Over 10 random seeds, we obtained an average of 92.5% accuracy and 98.1% digit accuracy on sum4, using a neural network trained on sum2.\n\n> Regarding the writing, I think that the quality of the paper is acceptable, but some parts are not extremely clear (especially Sections 1 and 2) due to notation clutter or imprecise/verbose explanations.\n\nThank you for this feedback. To clarify, in Equation 2.1, we are considering a program with $n$ inputs, so we have probability distributions over each input $p_1$ through $p_n$. $r_i$ refers to the $i$th discrete input in the input combination $r_1, \\dots, r_n$ that results in output $\\hat{y}$. So $p_i[r_i]$ refers to the probability of this input value. Since this notation is confusing, we will revise it to $$\\text{WMC}(\\hat{y} \\mid p_1, \\dots, p_n) = \\sum_{\\mathbf{r} \\in \\mathcal{R},~ c(\\mathbf{r}) = \\hat{y}} \\prod_{i=1}^n p_i(r_i)$$\n\nwhere $r=(r_1, \\dots,r_n​) \\in R_1 \\times \\dots \\times R_n$. We hope that this will remove some ambiguity around indexing. For Figure 2, we thought that populating these matrices with values would make the figure look cluttered, but we can see why only explaining how they are populated could be unclear. In the revised version, we will add these numbers to the figure either in the main body or in the appendix. We can fix Figure 1 to make it clear that the 4th digit is also an input to the neural network, and we will change the section title to “Bound on Approximation Error”"}, {"review_id": "JutJRSDg1k", "reviewer": "Reviewer_o1QR", "summary": "This paper targets at efficient computation of the output distributions of a program given the input variables' distribution. It assumes variables are discrete and the program/function can thus be modelled as a tensor mapping from choices of input variables' values to the output variable's value. They then apply tensor decomposition algorithms to approximate the tensor operations with low-rank and computationally efficient ones. The method also exploits the structure of programs. For example, summing n digits can be calculated as a tree of binary-sum sub-programs. They approximate each sub-program with tensor operations and then feed the outputted distributions to the next sub-program. The resulting method is differentiable and can thus support neuro-symbolic learning with gradient descent. \n\nThe method is evaluated in various classic neuro-symbolic tasks and shows better scalability for the sum_n program. It also performs competitively with previous methods in other tasks.", "questions": "* Are there more results regarding scalabilities e.g., for more programs and with more metrics? Can tensor operation approximation speed up general programs such as solving sudoku?\n* Can tensor operation approximation be extended more realistic settings where the sub-program tensor summary is infeasible?", "limitations": "N/A", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "This paper targets at an important problem: efficient approximations of the forward & backward computations of programs for neuro-symbolic learning. The method is interesting and incorporates the tensor decomposition techniques for approximation. \n\nHowever, as discussed by the authors, tensor decomposition is only applicable when the full program summary tensor is computationally affordable. It is hard to apply those techniques in more realistic settings. Program decomposition itself is well-known and commonly used in the neuro-symbolic field such as in Terpret. \n\nThe experimental results are positive to some extent but are not strong enough to support claiming general improvements on scalabilities. The results about scalability are mainly for the sum_n program where program decomposition is easy. It is hard to tell if the scalability comes from program decomposition or tensor operation approximation. Just for sum_n, we could simply approximate its outputs' expectation as the summation of all input variables' expectations and get similar performance in my understanding. \nThe authors did not state the ranks to approximate each program in experiments as well. It would be cool to see faster sudoku approximations with e.g., partial input-output examples, although I am not sure if it's feasible.", "was_revised": true, "final_justification": "The paper is generally interesting while it would be better to have experiments on more complex programs.", "rebuttal": "> [..] tensor decomposition is only applicable when the full program summary tensor is computationally affordable.\n\nIn the paper, we construct the full program summary tensor before applying sketching, and mention streaming tensor sketching methods—where sketches are computed without explicitly forming the full tensor—as a direction for future work.\nHowever, in response to your comment, we conducted an additional experiment on the sum-16 task without program decomposition (results reported below). In this setting, the full summary tensor would have size $10^{16}$, making direct construction computationally infeasible. Instead, we employed a cross approximation technique to learn rank-2 sketches directly from a subset of input-output samples, without forming the full tensor. We used the implementation provided by the tntorch Python package. A more thorough evaluation of how cross approximation can be integrated into CTSketch is left for future work.\n\n\n> Program decomposition itself is well-known and commonly used in the neuro-symbolic field such as in Terpret.\n\nWe should clarify that CTSketch isn’t the first work to propose program decomposition. TerpreT does have a compositional rule framework which guides their program synthesis. But TerpreT is a language designed for inductive program synthesis, and its programs can be used in the neurosymbolic learning setting. However, we believe that CTSketch is the first neurosymbolic learning framework to use a decomposed program, represented as tensors, to improve the efficiency of inference. While a Scallop sum64 program would probably not benefit from decomposing it as 6 layers of sum programs (a timeout will still occur), CTSketch can drastically improve its efficiency when programs are decomposed. We will clarify in the revision that we are introducing program decomposition with tensor summaries, not just general program decomposition.\n\n> The authors did not state the ranks to approximate each program in experiments as well.\n\nWe report the ranks for each task in Table 2 (Appendix C) along with other hyperparameters.\n\n> It is hard to tell if the scalability comes from program decomposition or tensor operation approximation. [...] Are there more results regarding scalabilities e.g., for more programs and with more metrics?\n\nWe performed an ablation study on comparing the performance gains from program decomposition and tensor sketching with sum-16. We vary the level of decomposition and compare accuracy, per-digit accuracy, and per-epoch training time using full-rank vs rank-2 sketches. Here 16 refers to no decomposition, whereas (8, 2) refers to 2-layer decomposition into two sum-8 at the first layer and a sum-2 at the second layer. \n\n|Method|Dims|# Entries|ACC (%)|DIGIT ACC (%)|TIME (s)\n|-|-|-|-|-|-\n|**SKETCH**|16|$600$|0.8352|0.9886|1.7154\n||8, 2|$280, 292$ $(572)$|0.8388|0.9890|2.1066\n||4, 4|$120, 468$ $(588)$|0.8325|0.9885|2.5705\n||2,2,2,2|$40, 76, 148, 292$ $(556)$|0.8251|0.9878|3.8828\n|**FULL**|16|$10^{16}*{145}$|Out of Memory\n||8, 2|$10^8*{73}, 73^2*{145}$|Out of Memory\n||4, 4|$10^4*{37}, 37^4*{145}$ $(272123345)$|0.8559|0.9901|17.6586\n||2,2,2,2|$10^2*{19}, 19^2*{37}, 37^2*{73}, 73^2*{145}$ $(887899)$|0.8580|0.9904|2.0139\n|**FULL+RBF**|16|$10^{16}$|Out of Memory\n||8, 2|$10^8, 73^2$|0.8329|0.9885|17.6282\n||4, 4|$10^4, 37^4$ $(1884161)$|0.8362|0.9889 |2.1516\n||2,2,2,2|$10^2, 19^2, 37^2, 73^2$ $(7159)$|0.8253|0.9880|3.8092\n\nBy comparing the full-rank (FULL) and rank-2 sketches configurations under the same decomposition structure, we observe that sketching offers substantial space savings, albeit with some loss in accuracy. As we scale to higher-dimensional input spaces, memory becomes a critical bottleneck—program decomposition alone is often insufficient. This highlights the necessity of tensor sketching for scaling. \n\nWithin full-rank, the gains from greater degree of decomposition are clear, both in terms of training time and memory efficiency. However, this trend reverses with sketches, due to the use of the RBF kernel at the output of each program layer. For reference, we report results on using full-rank tensors with RBF kernels (FULL+RBF) which also show that  accuracy drops with more program layers. Sketching ranks are reported in Table 2 (Appendix C)  along with other hyperparameters. \n\n> Can tensor operation approximation speed up general programs such as solving sudoku?\n\nEncoding programs as tensors provides a faster way to do inference and gradient propagation  on general programs compared to other neurosymbolic frameworks. Tensor sketching provides additional benefit in terms of memory, in trade-off of performance. For high-dimensional inputs, smaller sized tensors allow for faster inference. \n\n> Can tensor operation approximation be extended to more realistic settings where the sub-program tensor summary is infeasible?\n\nThe additional results reported above include solving sum-16 without program decomposition, for which using a full program tensor is computationally infeasible. Furthermore, the sum-8 sub-program tensor when decomposing into sum-8 and sum-2 also does not fit in memory. In both cases, sketching those tensors provides a solution."}, {"review_id": "hQK7uxjuOt", "reviewer": "Reviewer_D6gf", "summary": "The paper proposes a new method to perform scalable and approximate inference for neurosymbolic AI based on low-rank tensor decompositions of symbolic programs.", "questions": "1) Tensors (used in this paper) and arithmetic/probabilistic circuits (used in many other works) exhibit many similarities. It would be nice to see a discussion on these similarities in the context of the paper.\n\n2) How was the full rank tensor implemented. Was it as dense multilinear function? The reason I am asking is because recent advances have shown that one can efficiently implement arithmetic circuits (ie sparse multilinear functions, ie sparse tensors) efficiently on the GPU and scale neurosymbolic learning without any approximations [2]. This might imply that scaling is mainly due to program decomposition and not low-rank tensor approxiamtions?\n\n3) Is it not a bit of cheating to give direct supervision to the low-rank tensor decompositions of the sub-programs compared to what other methods are getting as training signal?\n\n[2] \"KLay: Accelerating Arithmetic Circuits for Neurosymbolic AI\", Jaron Maene, Vincent Derkinderen, and Pedro Zuidberg Dos Martires, ICLR, 2025", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths**\n\nThe idea of using low-rank tensor decompositions to approximate symbolic programs in a differentiable fashion is novel.\n\n\n**Weaknesses**\n\n1) The paper claims that they are the first to use program decompositions to scale neurosymbolic learning. However, this is not the case. De Smet and Zuidberg Dos Martires [1] already used program decomposition to scale to similar problem sizes. Albeit for a restricted set of neurosymbolic problems. This reference is missing in the paper. Note, the techniques used in [1] was not explicitly called program decomposition.\n2) The claim that logic programming languages do not support external API calls seems a bit strange. Logic programming is Turing-complete meaning they should probably be able to express an API call. \n\n[1] \"A Fast Convoluted Story: Scaling Probabilistic Inference for Integer Arithmetic\", Lennert De Smet, and Pedro Zuidberg Dos Martires, NeurIPS, 2024", "was_revised": true, "final_justification": "See discussion with authors.", "rebuttal": "> The paper claims that they are the first to use program decompositions to scale neurosymbolic learning. However, this is not the case.\n\nWe will clarify in the revision that we are not the first to introduce general program decomposition. We do believe that CTSketch is the first neurosymbolic framework to use a decomposed program, represented as tensors, to improve the efficiency of inference. While a Scallop sum64 program would probably not benefit from decomposing it as 6 layers of sum programs (a timeout will still occur), CTSketch can drastically improve its efficiency when programs are decomposed. \n\n> De Smet and Zuidberg Dos Martires [1] already used program decomposition to scale to similar problem sizes. Albeit for a restricted set of neurosymbolic problems. This reference is missing in the paper.\n\nWe will refer to PLIA in the Related Works section, explaining PLIA adapts FFT for efficient addition of probability distributions over integers, showing high speed-ups for programs expressible with integer arithmetics.\n\n> The claim that logic programming languages do not support external API calls seems a bit strange. Logic programming is Turing-complete meaning they should probably be able to express an API call.\n\nWe made this claim in the context of differentiable logic programs not being compatible with calls to APIs. For example, one could not write a DeepProbLog program that calls GPT-4 as part of a neurosymbolic learning framework because it would not be end-to-end differentiable. However, some logic programming languages do offer foreign function interfaces like SWI-Prolog, which allows HTTP requests.\n\n> Tensors (used in this paper) and arithmetic/probabilistic circuits (used in many other works) exhibit many similarities. It would be nice to see a discussion on these similarities in the context of the paper.\n\nIndeed, there are several similarities between the tensors used in CTSketch and probabilistic circuits (PCs). PCs decompose their probability distribution computation with sum and product nodes. Product nodes in PCs compute the product of their inputs, where each input corresponds to a probability over a disjoint set of random variables. This is similar to how CTSketch takes the product of probabilities corresponding to every possible input combination. Sum nodes in PCs compute a probability distribution over the same set of random variables. This is similar to how for each possible output, CTSketch adds the probabilities of the input combinations that resulted in this output. Unlike PCs, CTSketch has the ability to compute an approximate output distribution extremely efficiently with tensor sketching. However, their similarities are important to highlight in the related work section, and we plan to do so in the next revision.\n\n> How was the full rank tensor implemented? Was it a dense multilinear function? The reason I am asking is because recent advances have shown that one can efficiently implement arithmetic circuits (ie sparse multilinear functions, ie sparse tensors) efficiently on the GPU and scale neurosymbolic learning without any approximations [2].\n\nYes, the full rank tensor is implemented as a dense multilinear function. For a program $P: R_1 \\times \\dots \\times R_n \\rightarrow Y$, the full-rank tensor would be $\\phi: R_1 \\times \\dots \\times R_n$. This tensor can be represented as a arithmetic circuit consisting of three layers with $\\sum_i |R_i|$ leaves, $\\prod_i |R_i|$ nodes in layer 2, and $|Y|$ root nodes, similar to Figure 9 in [2]. KLay allows a time efficient neurosymbolic learning with this circuit, whereas CTSketch sketches $\\phi$ for scalable inference..\n\nTo clearly state how inference is done with the sketches, we further explain the computation of the equation between lines 135 and 136.\n\\begin{align}\nv &= \\sum_a^{|R_1|} \\sum_b^{|R_2|} \\sum_x^2 {p_1}[a] {p_2}[b] {t_1}[a, x] {t_2}[x, b] \\\\\\\\\nv &= \\sum_x^2 \\left( \\sum_a^{|R_1|} {p_1}[a] {t_1}[a, x] \\right)  \\left(  \\sum_b^{|R_2|} {p_2}[b]  {t_2}[x, b] \\right) \\\\\\\\\nv &= ( p_1^\\top t_1 ) \\cdot ( t_2 p _2 )\n\\end{align}\nWe have vectors $p_1:|R_1|$ and $p_2:|R_2|$ that are probability distributions, and 2D matrices $t_1:|R_1|\\times 2$ and $t_2:|R_2|\\times 2$ (where 2 is the sketching rank). Instead of taking the outer product of $t_1 \\times t_2$ and reconstructing the tensor, we can rearrange the order and do vector-matrix multiplication ($p_1$ and $t_1$, $p_2$ and $t_2$) and take the inner product of the two.\n\n> This might imply that scaling is mainly due to program decomposition and not low-rank tensor approxiamtions?\n\n|Method|Dims|# Entries|ACC (%)|DIGIT ACC (%)|TIME (s)\n|-|-|-|-|-|-\n|**SKETCH**|16|$600$|0.8352|0.9886|1.7154\n||8, 2|$280, 292$ $(572)$|0.8388|0.9890|2.1066\n||4, 4|$120, 468$ $(588)$|0.8325|0.9885|2.5705\n||2,2,2,2|$40, 76, 148, 292$ $(556)$|0.8251|0.9878|3.8828\n|**FULL**|16|$10^{16}*145$|Out of Memory||\n||8, 2|$10^8*{73}, 73^2*{145}$|Out of Memory||\n||4, 4|$10^4*{37}, 37^4*{145}$ $(272123345)$|0.8559|0.9901|17.6586\n||2,2,2,2|$10^2*{19}, 19^2*{37}, 37^2*{73}, 73^2*{145}$ $(887899)$|0.8580|0.9904|2.0139\n|**FULL+RBF**|16|$10^{16}$|Out of Memory||\n||8, 2|$10^8, 73^2$|0.8329|0.9885|17.6282\n||4, 4|$10^4, 37^4$ $(1884161)$|0.8362|0.9889 |2.1516\n||2,2,2,2|$10^2, 19^2, 37^2, 73^2$ $(7159)$|0.8253|0.9880|3.8092\n\nWe performed an ablation study on comparing the performance gains from program decomposition and tensor sketching with sum-16. We vary the level of decomposition and compare accuracy, per-digit accuracy, and per-epoch training time using full-rank vs rank-2 sketches. Here 16 refers to no decomposition, whereas (8, 2) refers to 2-layer decomposition into two sum-8 at the first layer and a sum-2 at the second layer. \n\nBy comparing the full-rank (FULL) and rank-2 sketches configurations under the same decomposition structure, we observe that sketching offers substantial space savings, albeit with some loss in accuracy. As we scale to higher-dimensional input spaces, memory becomes a critical bottleneck—program decomposition alone is often insufficient. This highlights the necessity of tensor sketching for scaling.\n\nWithin full-rank, the gains from greater degree of decomposition are clear, both in terms of training time and memory efficiency. However, this trend reverses with sketches, due to the use of the RBF kernel at the output of each program layer. For reference, we report results on using full-rank tensors with RBF kernels (FULL+RBF) which also show that  accuracy drops with more program layers.\n\n> Is it not a bit of cheating to give direct supervision to the low-rank tensor decompositions of the sub-programs compared to what other methods are getting as training signal?\n\nWe do not provide any direct supervision using intermediate labels. We make the same assumptions as other neurosymbolic frameworks, which assume the domain of symbols (inputs to the program) is known. We use this assumption to randomly sample the symbols, prior to training and irrelevant to the actual training set labels, to initialize the program tensor."}, {"review_id": "oYCB6o7dB4", "reviewer": "Reviewer_8NU1", "summary": "The work introduces CTSketch, a novel neurosymbolic learning algorithm that is designed to scale better.\nThe idea is to represent a logic program as a tensor, mapping each input combination to either 0 or 1, which still scales exponential in the number of variables. To scale, they approximate such a program by 1) decomposing it into several subprograms (currently limited to a user defined decomposition), which reduces the number of variables within a subprogram, and by 2) considering a low-rank approximation of those subprogram tensors. The empirical analysis demonstrates strong results.", "questions": "Not really questions, more feedback:\n\nWith regards to related work / future work, the authors may find interesting work on tensor decompositions for probabilistic inference in general. Some of these automatically identify decompositions based on the variable dependencies etc. E.g.,\n- \"Tensor Belief Propagation\", ICML2017. Andrew Wrigley, Wee Sun Lee, Nan Ye\n- \"Parallel Weighted Model Counting with Tensor Networks. MCC2020. Jeffrey M. Dudek, Moshe Y. Vardi\n- \"Efficient Contraction of Large Tensor Networks for Weighted Model Counting through Graph Decompositions\". 2019. Dudek et al.\n- \"Expressive power of tensor-network factorizations for probabilistic modelling\". NeurIPS 2019. Glasser et al.\n- \"What is the Relationship between Tensor Factorizations and Circuits (and How Can We Exploit it)?\" TMLR2025. Loconte et al.\n- \"Learning from Binary Multiway Data: Probabilistic Tensor Decomposition and its Statistical Optimality\". JMLR2020. Wang et al.\n\n\nTypo: \n* \"learning, Next, we ...\"\n* \"Inference in CTSketch does not aggregate proofs\", is an odd statement in a sense that the summations performed within CTSketch are aggregating in a similar fashion. I.e., you compute Eq 2.2, which is aggregating 'proofs'.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Clarity**: \nThe primary ideas of the proposed work are easy to follow, and well-illustrated using Figures.\n\n**Originality**: \nThe techniques proposed in this work exist; the novelty is their application in a neurosymbolic context. Having said that, the techniques only apply to the symbol-inference part, and are disconnected from the neural part of the pipeline. In that sense, it is not too surprising that this can be done. I was pleasantly surprised however by how well it appears to work in a neurosymbolic learning setting.\n\n**Significance**:\nThe paper demonstrates strong empirical results, increasing the potential impact on the field. The fact that a user needs to manually specify a program decomposition limits the more general applicability of this work. However, I believe that existing related work may help here (see Questions section).\n\n**Quality**:\nThe work is of good quality: the proof for the error bound is included in the appendix (but I did not verify it), the empirical experiments are in line with existing neurosymbolic papers, and the discussion of the empirical results are sufficiently informative/convincing. Something that could be of interest and that is currently missing is the impact of the program decomposition on the final results.", "was_revised": true, "final_justification": "The authors have sufficiently addressed my questions. I remain positive about the work for the reasons outlined above.", "rebuttal": "> Originality: [...] Having said that, the techniques only apply to the symbol-inference part, and are disconnected from the neural part of the pipeline. \n\nThe reason why we use the program summaries and tensor approximations is to connect the neural component with the symbolic program in a way that is end-to-end differentiable. In that sense, CTSketch is connected to the neural part of the pipeline.\n\n> Quality: [...] Something that could be of interest and that is currently missing is the impact of the program decomposition on the final results.\n\n|Method|Dims|# Entries|ACC (%)|DIGIT ACC (%)|TIME (s)\n|-|-|-|-|-|-\n|**SKETCH**|16|$600$|0.8352|0.9886|1.7154\n||8, 2|$280, 292$ $(572)$|0.8388|0.9890|2.1066\n||4, 4|$120, 468$ $(588)$|0.8325|0.9885|2.5705\n||2,2,2,2|$40, 76, 148, 292$ $(556)$|0.8251|0.9878|3.8828\n|**FULL**|16|$10^{16}*145$|Out of Memory||\n||8, 2|$10^8*{73}, 73^2*{145}$|Out of Memory||\n||4, 4|$10^4*{37}, 37^4*{145}$ $(272123345)$|0.8559|0.9901|17.6586\n||2,2,2,2|$10^2*{19}, 19^2*{37}, 37^2*{73}, 73^2*{145}$ $(887899)$|0.8580|0.9904|2.0139\n|**FULL+RBF**|16|$10^{16}$|Out of Memory||\n||8, 2|$10^8, 73^2$|0.8329|0.9885|17.6282\n||4, 4|$10^4, 37^4$ $(1884161)$|0.8362|0.9889 |2.1516\n||2,2,2,2|$10^2, 19^2, 37^2, 73^2$ $(7159)$|0.8253|0.9880|3.8092\n\nWe performed an ablation study on comparing the performance gains from program decomposition and tensor sketching with sum-16. We vary the level of decomposition and compare accuracy, per-digit accuracy, and per-epoch training time using full-rank vs rank-2 sketches. Here 16 refers to no decomposition, whereas (8, 2) refers to 2-layer decomposition into two sum-8 at the first layer and a sum-2 at the second layer. \n\nBy comparing the full-rank (FULL) and rank-2 sketches configurations under the same decomposition structure, we observe that sketching offers substantial space savings, albeit with some loss in accuracy. As we scale to higher-dimensional input spaces, memory becomes a critical bottleneck—program decomposition alone is often insufficient. This highlights the necessity of tensor sketching for scaling.\n\nWithin full-rank, the gains from greater degree of decomposition are clear, both in terms of training time and memory efficiency. However, this trend reverses with sketches, due to the use of the RBF kernel at the output of each program layer. For reference, we report results on using full-rank tensors with RBF kernels (FULL+RBF) which also show that  accuracy drops with more program layers\n\n>  With regards to related work / future work, the authors may find interesting work on tensor decompositions for probabilistic inference in general.\n\nThank you for all these references. We will look into them for automating program decomposition.\n\n\n> \"Inference in CTSketch does not aggregate proofs\", is an odd statement in a sense that the summations performed within CTSketch are aggregating in a similar fashion. I.e., you compute Eq 2.2, which is aggregating 'proofs'.\n\nWe agree that this statement is inaccurate. What we meant to say is that CTSketch does not aggregate proofs following the execution of a logic program, as is done in Scallop and DeepProbLog. CTSketch instead aggregates proofs through its tensor operations. We will clarify this point in the revised version of the paper."}]

Author rebuttal:

Meta-review: This submission introduces a compositional tensor sketching method designed to scale neurosymbolic learning. The reviewers generally agreed that the contribution is technically solid, with experiments demonstrating both efficiency and accuracy. Some concerns were raised about the breadth of applications and experimentation, but the rebuttal largely addressed the concerns. Overall, the committee reached consensus that this contribution advances the scalability of neurosymbolic methods and will be of interest to the NeurIPS community. I recommend acceptance.
Decision: Accept (poster)