Data-Efficient Learning with Neural Programs
Authors: Alaia Solko-Breslin
Seewon Choi
Ziyang Li
Neelay Velingker
Rajeev Alur
Mayur Naik
Eric Wong
Venue: NeurIPS 2024 poster (2024)
Keywords: neurosymbolic learning
Primary area: other

Abstract: Many computational tasks can be naturally expressed as a composition of  a DNN followed by a program written in a traditional programming language or an API call to an LLM. We call such composites "neural programs" and focus on the problem of learning the DNN parameters when the training data consist of end-to-end input-output labels for the composite.  When the program is written in a differentiable logic programming language, techniques from neurosymbolic learning are applicable, but in general, the learning for neural programs requires estimating the gradients of black-box components. We present an algorithm for learning neural programs, called ISED, that only relies on input-output samples of black-box components. For evaluation, we introduce new benchmarks that involve calls to modern LLMs such as  GPT-4 and also consider benchmarks from the neurosymbolic learning literature. Our evaluation shows that for the latter benchmarks, ISED has comparable performance to state-of-the-art neurosymbolic frameworks. For the former, we use adaptations of prior work on gradient approximations of black-box components as a baseline, and show that ISED achieves comparable accuracy but in a more data- and sample-efficient manner.

Data-Efficient Learning with Neural Programs
Alaia Solko-Breslin, Seewon Choi, Ziyang Li, Neelay Velingker, Rajeev Alur, Mayur Naik, Eric Wong
University of Pennsylvania
{alaia, seewon, 1iby99,99009 neelay, alur, mlurr,h eeabnni,,ewwon... aaeeas.uuenn....... edu
Abstract
Many computational tasks can be naturally expressed as a composition DNN followed by program written in a traditional programming language or an API call an LLM. We call such composites "neural programs" and focus on the prob- lem of learning the DNN parameters when the training data consist of end-to-ce and input-output labels for the composite. When the program written tiable logic programming language, techniques from neurosymbolic learning are applicable, but general, the learning for neural programs requires estimating the gradients of black-box components. We present an algorithm for learning neu- programs, called ISED, that only relies on input-output samples of black-box components. For evaluation, we introduce new benchmarks that involve calls to modern LLMs such as GPT-4 and also consider benchmarks from the neurosym- bolic learning literature. Our evaluation shows that for the latter benchmarks, ISED has comparable performance to state-of-the-art neurosymbolic frameworks. For the former, we adaptations of prior work gradient approximations of black-box components as baseline, and show that ISED achieves comparable accuracy but in more data- and sample-efficient manner.
differen-
Introduction
Many computational tasks cannot be solved by neural perception alone but can be naturally expressed as composition of neural model Mg followed by program P written a traditional programming language or API call to large language model (LLM).. We call such composites "neural programs" and study the problem of learning neural programs in an end-to-end manner with focus on data and sample efficiency. One problem that is naturally expressed as neural program is scene recognition [29], where Ma classifies objects in image and P prompts GPT-4 to identify the room type given these objects (Fig. 1).
Neurosymbolic learning [2] is one instance of neural program learning in which P takes the form of logic program. DeepProbLog (DPL) [14] and Scallop [13] are frameworks that extend ProbLog and Datalog, respectively, ensure that the symbolic component P is differentiable. This differentiability requirement is what facilitates learning in many neurosymbolic learning frameworks. There are also abductive learning frameworks that do not explicitly differentiate programs. Instead, they require that the symbolic component expose method for abducing the function's 's inputs for a given output, often using Prolog for the symbolic component as a result [6, 23). While logic programming languages are expressive enough for these frameworks to solve tasks such as sorting [14], visual question answering [13), and path planning [23], they offer restricted features and a narrow range of libraries, making them incompatible with calls to arbitrary APIs to modern LLMs.
Learning neural programs when not expressed as logic program is difficult problem because gradients across black-bor box programs cannot be computed explicitly. One possible solution is to use REINFORCE [26] sample symbols from distributions predicted by Mg and compute the expected
'Code available at http:///ithh....ommaaaaaoololsss
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

There is cup, dish, paper towel, and type
kitchen
GPT4
Ms
Figure 1: Neural program decomposition for scene recognition.
reward using the output label. However, REINFORCE not sample-efficient as it produces a weak learning signal, especially when applied to programs with large number of inputs. There are other CEINFORCE-basse methods that can be applied to the neural program learning setting, namely IndeCateR [21] and Neural Attention for Symbolic Reasoning (NASR) [5]. However, IndeCateR struggles with sample efficiency despite providing lower variance than REINFORCE, and NASR performs poorly when intermediate labels are unavailable for pretraining. Another possible solution Approximate Neurosymbolic Inference (A-NeSI) [24], which trains neural network to estimate the gradient of P, but learning the surrogate neural network becomes difficult the complexity of increases. Moreover, the additional neural models in the learning framework in A-NeSI results in data inefficiency.
In this paper, we propose an algorithm for learning neural programs, based on reinforcement learning, which is compatible with arbitrary programs. Our approach, called ISED Infee--Samle--sstmaal Descend), yields a framework that expands the applicability of neural program learning frameworks by providing data- and sample-effie cample-efficient method of training neural models with randomly initialized weights. ISED uses outputs of Ma as a probability distribution over inputs of and samples representative symbols from this distribution. ISED then computes outputs of P corresponding to these symbols. The resulting symbol-output pairs can be viewed as a symbolic program consisting of clauses of the form if symbol to estimate the gradient across this symbolic summary, inspired by ideas from the neurosymbolic learning literature, propagate loss across the composite model.
then output
v summarizing P. The final step is
Our evaluation considers 16 neural program benchmark tasks. Our results show that ISED outperforms purely neural networks and CLIP [19] on neural program tasks involving GPT-4 calls. Additionally, ISED outperforms neurosymbolic methods on 9 of the 14 benchmarks tasks that can be encoded in logic programming languages. ISED is also the top performer on 8 out of the 16 benchmark tasks when compared to REINFÖRCE- baseed and black-box gradient estimation baselines. Furthermore, show that ISED is more data- and sample-efficient than baseline methods.
In summary, the main contributions of this paper are as follows: 1) we introduce neural programs as generalization of neurosymbolic programs, 2) we introduce new tasks involving neural programs that use Python and calls to GPT-4 called neuroPython and neuroGPT programs, respectively, 3) we present ISED, a general algorithm for data- and sample-efficient learning with neural programs, and 4) we conduct a thorough evaluation using existing techniques against a diverse set of benchmarks.
2 Neural Programs
Problem Statement. In the neural program learning setting, we attempt to optimize model parameters Mo which are being supervised by a fixed program P. Specifically, we are given a training dataset D of length N containing input-output pairs, i.e., D = {011 v.),... (IN, B.)). Each z; represents unstructured data (e.g., image data) whose corresponding structured data (intermediate labels) are not given. Each ys is the result of applying P to the structured data corresponding to zi. Given a loss function L. we want to minimize the loss of (( y/) for each (æ,, yy) pair in order to optimize 0. Loss minimization is straightforward when there is some mechanism for automatically differentiating programs, but we focus on the setting of optimizing without assuming the differentiability of P. We now introduce three motivating applications that can be framed in this

---

formula def leaf idhpheee str, texture: str):
result
prob/correct
0.729
Linon
if nargan serrulate elif nergin = enttre's
Terminalia
0.124
X
Leaf Clussiication
cheracteristics Ciellipttcat" "entarer "poowy"")
return "Pongania Pinnata" elif shape ovate" :
Pantata
0.012
X
Infer
p"ellipticat"
Exeeute
Granasun
Paniua
Rstimate
0.016
X
unds "glosdy"1
hentire " glossy")
Poovatet
result
crob/correct
Chelliptical" Montard" (
def teaf_id(shape str,
nang textures stri;
CStrus
Linen
0.729 of
proret CClsssify Leaf
Arjuto
x
features: (chape), (nargin), [texture).
Pintata
0.942
X
return parse. putput (respons))
Granaius
Pantca
0.036
X
Figure 2: Illustration of our inference pipeline for the leaf classification task. leaf_ id can be written with decision tree (top program) or with call to GPT-4 (bottom program).
setting, namely classifying images of leaves [9], scene recognition [29], and evaluation (HWF) [12].
Leaf Classification. We consider a real-world example that deals with the problem of classifying leaf images. Traditional neural methods predict the species directly, without explicit notion of leaf features such as margin, shape, and texture, resulting in solutions that data-inefficient, inaccurate, and harder to understand.
We instead present neural programming solution, making use of leaf classification decision trees [22]. These decision trees allow identifying plant species based on the visible characteristics of their leaves. Here, the neural model takes leaf image and predicts its shape, margin, and texture. The program can then be written in two ways: one implementation involves encoding the decision tree in Python; another involves constructing a prompt using the predicted leaf features and calling GPT-4 (see Fig. 2). The latter is possible because ISED allows the use of black-box programs, so programs can also use state-of-the-art foundation models such GPT-4 for computation.
Scene Recognition. The goal of this task is to classify images according to their room types. The model receives image from scene dataset [16] and predicts among the 9 different room types: bedroom, bathroom, dining room, living room, kitchen, lab, office, house lobby, and basement.
The traditional neural solution trains a convolutional neural network that directly predicts the room type. On the other hand, the neural program solution decomposes the task into detecting objects in the scene and identifying the room type based on those objects. We use an off-the-shed object detection model YOLOv8 [20] and finetune it with a custom convolutional neural network to output labels related to scene recognition. We then make a GPT-4 call to predict the most likely room type given the list of detected objects.
Hand-written Formula. In this task, a model is given a list of hand Hannd-written symbols containing digits (0-9) and operators (+, -. x, and +) [12]. The dataset contains length 1-7 formulas free of syntax or divide-by-zero errors. The model is trained with supervision on the evaluated floating- poating-point result without the label of each symbol. Since inputs are combinatorial and results are rational numbers, end-to-end neural methods struggle with accuracy. Meanwhile, neurosymbolic methods for this task either use specialized algorithms [12] or handerafted differentiable programs [13].
With ISED, the program can be written in just a few lines of Python. It takes in a list of characters representing symbols, and simply invokes the Python eval function the joined expression string. The hwf evaluation function can he used just like any other Py Torch [17] module since ISED internally performs sampling and probability estimation to estimate the gradient.
3 Learning Neural Programs
In this section, we present the intuition behind ISED and the values it approximates. Next, we introduce the programming interface for ISED, which lays the groundwork for presenting the algorithm. We then formally describe the steps of ISED.
3

---

3.1 ISED Overview
Assuming P is a black-box, we can collect symbol-output samples (u, v) from P. Such collection of samples can be viewed as a summary logic program consisting of rules of the form if r = u then y v. For instance, in the task of adding two digits r1 and r2, one rule of the logic program would be r =1 A = 2 + weighted model counting (WMC) [10] can then be used for computing the gradient across such summary of P. However, having the complete summary of all combinations of symbols is not feasible for black-box P. ISED samples symbols from the probability distribution predicted by the neural network Mg, evaluates P on each sample, and takes the gradient across this partial summary of P. This is a good approximation of the complete summary since is likely to contain symbols with high probability, which contribute the most in exact computation.
3. Techniques from neurosymbolic literature via exact or approximate
This approach differs from REINFORCE in how it differentiates through this summary of P. RE- INFORCE rewards sampled symbols that resuited in the correct output through optimizing the log probability of each symbol, weighted by reward values. This weighted-sum style estimation provides weaker learning signal compared to WMC used by ISED, making learning harder for REINFORCE. as the number of inputs to P increases. See Appendix A for further details.
3.2 Preliminaries and Programming Interface
ISED allows programmers to write black-bor box programs that operate on diverse structured inputs and outputs. To allow such programs interact with neural networks, we define an interface named structural mapping. This interface serves to 1) define the data-types of black black-box programs' input and output, 2) marshall and un-marshall data between neural networks and logical black-box functions, and 3) define the loss. We define a structural mapping T as either a discrete mapping (with Σ being the set of all possible elements), a floating point, a permutation mapping with n possible elements, a tuple of mappings, or list of up to elements. We define 7 inductively as follows:
T : DISCRETE(S) ()) FLOAT PERMUTATION,
CEPLEE(T......T... (T)
Using this, we may further define data-types such as INTEGER DISCRETEE k)), DIGIT INTEGER and BooL- = DISCRETE( (truee, false)). These types give ISED the flexibility learn neural programs with diverse types of inputs and outputs, e.g.. PERMUTATION, input and output contoutssss types for integer list sorting and LIST, ( (LIST ( (DIGIT)) for sudoku solving.
We also define black-box program P function (71....,
To, where Ti..... Tm are the input types and To is the output type. For example, the structural input mapping for the brittwritten formula task is LIST, (DISCRETE((0) ((0,... ................................ 9, + -, x, }})), and the structural output mapping is FLOAT. The mappings suggest that the program takes list of length up to 7 as input, where each element is a digit or arithmetic operator, and returns floating point number.
There are two interpretations of structural mapping: the set interpretation SET(T) represents a mapping with defined values, e.g., a digit with value 8; the tensor interpretation DIST(T) represents a mapping where each value associated with a probability distribution, e.g. a digit that is I with probability 0.6 and 7 with probability 0.4. We use the set interpretation to represent structured program inputs that can be passed to a black-box program and the tensor interpretation to represent probability distributions for unstructured data and program outputs. These two interpretations are defined for the different structural mappings in Table 1.
Table 1: Set and tensor interpretations of different structural mappings.
Mapping (r)
Sel Interpretation (SET(T))
Tensor Interpredation (DIST(r)
DISCRETEg FLOXT
(i E .
[
0o 1], 1... I....
R
n/a
PERMUTATION,,
{p] a permutaionn of [1, ..., m])
{[V Un]
& E R" U., 6 [0, 1), I...R)
TUPLE(T).... Tm))
{()...... Gm) SET(T.))
[lai... 6m)
DIST(7:))
LiST..(7))
[aa...., 05]1 n, SET(>'))
{lai....
asl / S n, DIST(r"))
In order to represent the ground truth output as a distribution to used in the loss computation, there needs to be a mechanism for transforming SET(7) mappings into DIST(7) mappings. For

---

this purpose, we define vectorize function 8, (SET(T), - (TST(T) for the different output mappings T in Table 2. When considering datapoint (x, y) during training. ISED samples many symbols and obtains a list of outputs y. The vectorizer then takes the ground truth y and the outputs y as input and returns the equivalent distribution interpretation of y. While ý is not used by 6, in most cases, we include it as an argument so that FL.AAT output mappings can be discretized, which is necessary for vectorization. For example, if the inputs to the vectorizer for the hand-writter formula task are y = 2.0 and [1.0, 3.5, 2.0, 8.0], then it would return [0, 0, 1, O].
Table 2: Vectorize and aggregate functions of different structural mappings.
Mapping (7)
Vectorizer (6. (v. B1)
Aggregator (or pI)
DISCRETE,
(00)) with dim
plr]
FLOAT PURMUTATION, TUPLE(T).... ..., 7m) (r)
[y for i E [L, leng
n/a
[ouscoar,, (v(I) for e [L,...,]]]
dusCEETE, (P1)) A())
16 (vlil) for 5 [1, mm]] (6,r(a,) for a, vl
dr (PB). p(3))
2 d (+ (I) p(d))
We also require mechanism to aggregate the probabilities of sampled symbols that resulted in a particular output. With this aim, we define an aggregate function o, (SET(r), DIST(T)) - R for different input mappings in Table 2. ISED aggregates probabilities either by taking their minimum or their product, and we denote both operations by @. The aggregator takes as input sampled symbols è and neural predictions from which f was sampled. It gathers values in P at each index in f and returns the result of @ applied to these values. For example, suppose we use min as the aggregator & for the hand-written formula task. Then if @ takes f = [1. +. 1] and ý as inputs where p[0][]] = 0.1, p[][++] = 0.05, and [[]][]] = 0.1, it would return 0.05.
3.3 Algorithm
We now formally present the ISED algorithm. For a given task, there is a black-box -bx program P. taking m inputs, that operates structured data. Let Ti.... Tm be the mappings for these inputs and To the mapping for the program's 's output. We write P as a function from its input mappings to its output mapping: P (fI..., Tm) - To- For each unstructured input to the program, there is a neural model Mj, : I2 + DIST(T;). S is a sampling strategy (e.g., categorical sampling) that samples symbols using the outputs of a neural model, and k is the number of samples to take for each training example. There is also loss function L whose first and second arguments are the predicted and ground truth values respectively. We present the pseudocode of the algorithm in Algorithm I and describe its steps with the hand-written formula task:
Infer. The training pipeline starts with an example from the dataset, (= +, 2 3.0), and uses CNN to predict these images, as shown on lines 3-4. ISED initializes ÿ (z(
Sample. ISED samples from P for k iterations using sampling strategy S. For each sample j. the algorithm initializes f; to be the sampled symbols, as shown on lines 6-9. To continue our example, suppose ISED initializes f, = [7, +.2] for sample j. The next step is to execute the program on fy. as shown on line 10, which in this example means setting ú, = ((,,) = 9.0.
Estimate. In order to compute the prediction value to use in the loss function. ISED must consider each output y1 in the output mapping and accumulate the aggregated probabilities for all sampled symbols that resulted in the output y)- We specify @ as the min function, and as the max function in this example. Note that ISED requires that & and ( represent either min and max or mult and add respectively. We refer to these two options as the min-max and add-mult semirings. We define an accumulate function w that takes as input an element of the output mapping yt, sampled outputs ğ. sampled symbols f. and predicted input distributions p. The accumulator performs the @ operation on aggregated probabilities for elements of ý that are equal to y and is defined as follows:
(yt, G. f, p) = の ,== T (5)
Continuing our example, suppose, among the samples, there are two symbolic combinations (7, +, 2 and [3, x,3] 3)) that resulted in the output 9.0. Let us say that these sets of symbols had probabilities [0.3, 0.8, 0.8) and [0. (0.1,0.7 0.1, respectively. Then the result of the probability aggregation for
Y1 = 9.0 would be (9.00 ÿ. P, max(min([0.3, 0.8, 0.8)), min( 0.1, 0.1)) = 0.3.
5

---

Algorithm ISED training pipeline
Require: P is the black-box program (T1,..., Tm) Tas Mý. the neural model at; (1ST( for
each Tg. S the sampling strategy. the sample count, L the loss function, and 'D the dataset.
1: procedure TRAIN
2: for ((z1,... Zm); 1) E D do
3: for i
do
4:
111 + Mj, (T:)
> Infer
5: end for
6:
for j E 1. k do
7:
for i 1 m do
8:
Sample [ from p[1] using 5
Sample
9:
end for Új < P(fy) end for @ Normalize([w<Mn) f, for y E (or yı E 0)]
10:
11:
12:
Estimate
13:
w f- 8 9) I + [(w, w)
14:
15:
Compute
0 30
by performing back-propagation on !
Optimize 0 based 30
Ø
Descend
17:
end for end procedure
ISED then sets i (yt, 9. f. for 3i E Ta] in the case where To is not FLOAT. When T, is FLOAT, hand-written
for hand-war written formula, it only considers y Next, it performs L2 normalization over each
element w and sets vē to this result. To initialize the ground truth vector, it sets w = 5(y, g). ISED al for each input i. These steps are shown on lines 12-15.
then initializes I = [(O;, w) and computes ae; In our running example, since 9.0 is an incorrect output, the probability of the first symbol being equal to (instead of the correct answer 1) will be penalized while the probabilities for predicting other symbols are unchanged.
Descend. The last step is shown on line 16, where the algorithm optimizes 0, for each input based At
on 80, using stochastic optimizer (e.g.. Adam optimizer). This completes the training pipeline for one example, and the algorithm returns all final 0g after iterating through the entire dataset.
4 Evaluation
In this section, we evaluate ISED and aim answer the following research questions:
RQI: How does ISED compare to state-of-the-arr neurosymbolic, REINFORCE based, and gradient estimation baselines in terms of accuracy?
RQ2: What the sample efficiency of ISED when compared to REINFORCE-based algorithms?
RQ3: How data-efficient is ISED compared neural gradient estimation methods?
4.1 Benchmark Tasks: NeuroGPT, NeuroPython, and Neurosymbolic
We first introduce new neural program learning benchmarks which both contain program component that can make a call to GPT-4. We call such models neuroGPT programs.
Leaf Classification. In this task, of 11 different plant species [4], containing 330 training samples and 110 testing samples. We define custom DISCRETE types MARGIN, SHAPE, TEXTURE. With this, we define LEAF-TRAIT (MPLEEMARGIN, SHAPE, TEXTURE) and LEAF-OUTPUT to be the DISCRETE set of 11 plant species in the dataset. Neural program solutions either prompt GPT-4 (GPT leaf) or a decision tree (DT leaf).
dataset, which call LEAF-ID, containing leaf images
Scene Recognition. We use dataset containing scene images from 9 different room types [16], consisting of 830 training examples and 92 testing examples. We define custom types OBJECTS and SCENES to be DISCRETE set of 45 objects and 9 room types, respectively. We freeze the parameters

---

Table 3: Performance on selected benchmarks. "TO" means time-out, out, and "N/A" means the task could not be programmed in the framework. Methods are divided (from top to bottom) by neurosymbolic, black-box gradient estimation, and REINFORCFE-bsed.
Accuracy (%)
Method
Sum2
Sumg
Sum,
HWF
DT leaf
GPT leaf
scene
sudoku
DPL Scallop
95.14
93.80
TO
39.70 81.13
N/A
N/A
TO
91.18
91.86
80.10
96.65
N/A
N/A
TO
A-NeSI
96.66
94.39
78.10 10
3.13
78.82
72.40
61.46
26.36
REINFORCE
74.46
19.40
13.84
88.27
40.24
53.84
12.17
79.08
IndeCateR
96.48
93.76
92.58
95.08
78.71
69.16
12.72
66.50
NASR
6.08
5.48
1.86
1.85
16.41
17.32
2.02
82.78
ISED (ours)
80.34
95.10
94.10
97.34
82.32
79.95
68.59
80.32
of YOLOv8 and only optimize the custom neural network. The neural program solution prompts GPT-4 to classify the scene.
We also consider several tasks from the neurosymbolic literature, including hand-written formula (HWF) evaluation and Sudoku solving. While the solutions to many of these tasks are usually presented as a logic program in neurosymbolic learning frameworks, neural program solutions can take the form of Python programs. We call such models neuroPython programs.
MNIST-R. MNIST-R [13, 14] contains 1l tasks operating on inputs of images of handwritten digits from the MNIST dataset [11]. This synthetic test suite includes tasks performing arithmetic (sum2, sum3, sum, multz, mod2, add-mod-3, add-sub), comparison (less-than, equal), counting (count-3-or- 4), and negation (not-3-or-4) over the digits depicted in the images. Each task dataset has a training set of 5K samples and testing set of 500 samples.
HWF. The goal of the HWF task is to classify images of handwritten digits and arithmetic operators and evaluate the formula [12). The dataset contains 10K formulas of length 1-7, with 1K length 1 formulas, IK length 3 formulas, 2K length 5 formulas, and 6K length formulas.
Visual Sudoku. The goal of this task is to solve an incomplete 9x9 Sudoku, where the problem board given as MNIST digits. We follow the experimental setting of NASR [5], including their pre-trained MNIST digit recognition models and sudoku solvers. We use the SatNet dataset consisting of 9K training samples and 500 test samples [25].
4.2 Evaluation Setup and Baselines
All our experiments were conducted on machine with two 20-core Intel Xeon CPUs, one NVIDIA RTX 2080 Ti GPU, and 755 GB RAM. Unless otherwise noted, the sample count, i.c., the number of calls to the program P per training example, is fixed at 100 for all relevant methods. For additional details on experimental setup, see Appendix B. We apply timeout of 10 seconds per testing sample, and report the average accuracy and I-sigma standard deviation obtained from 10 randomized runs.
We pick baselines neurosymbolic methods DeepProbLog (DPL) [14] and Scallop [13], A-NeSI [24] which performs neural approximation of the gradients, and sampling-basee based gradient approximation methods REINFORCE [26], IndeCateR [21], and NASR [5]. IndeCateR achieves provably lower variance than REINFORCE by using a specialized sampling method (Appendix A), and NASR is a variant specialized for efficient finetuning by using single sample and custom reward function. We also use purely neural baselines and CLIP [19] for GPT leaf and scene. CLIP is multimodal model that supports zero-shot image classification by simply providing names of the output categories.
4.3
RQ1: Performance and Accuracy
To answer RQ1, we evaluate ISED's 's accuracy against those of the baselines. ISED matches, and in many cases surpasses, the accuracy of neurosymbolic and gradient estimation baselines. We highlight the results for sum, from MNIST-R and other benchmarks in Table 3, Tables 7-10 in Appendix C
7

---

Table 4: Performance comparisons for sumy, sum12, and sum16 with different sample counts
Accuracy (%)
sums
sum12
Sum16
Method
k = 80
A: 800
k 120
& 1200
k 160
k 1600
REINFORCE
8.32
8.28
7.52
8.20
5.12
6.28
IndeCateR
5.36
89.60
4.60
77.88
1.24
5.16
IndeCateR+
10.20
88.60
6.84
86.92
4.24
83.52
ISED (Ours)
87.28
87.72
85.72
86.72
6.48
8.13
contain results for the remaining MNIST-R tasks, including standard deviations for all tasks. ISED the top performer on 8 out of the 16 total tasks.
On the GPT leaf and scene tasks, ISED outperforms the purely neural baseline by 3.82% and 31.42% respectively, and zero-shot CLIP by 59.80% and 17.50%. For many tasks, A-NeST the non- neurosymbolic method that comes closest to ISED, sometimes outperforming our method. However, A-NeSI achieves significantly lower performance than ISED on tasks involving complex programs, namely HWF and sudoku. This is likely due to the difficulty of training neural model estimate the output of P' and its gradient when P is complex. ISED also outperforms REINFORCE on all but 3 tasks due to the REINFORCE learning signal being weaker for tasks where P' involves multiple inputs. NASR outperforms ISED only on sudoku by 2.46% due to NASR being well-suited for fine-tuning as restricts its algorithm use a single sample. IndeCateR achieves similar performance compared to ISED on most tasks but achieves significantly lower accuracy on the scene classification task, which has a large input space with maximum 10 objects each with 47 possible values in each scene, demonstrating that IndeCateR is less sample-efficient than ISED. We elaborate more on this point in RQ2.
ISED outperforms the neurosymbolic methods on 9 out of 14 tasks that can be written in logic programming languages. Despite treating P as a black-box, ISED even outperforms Scallop on HWF by 0.69% and comes within 1.16% of NGS, specialized neurosymbolic learning framework that uses abductive reasoning [12]. Furthermore, DPL timed out on 4 tasks, and Scallop timed out on (sudoku). These results demonstrate that even for tasks that can be written in a logic programming language, treating the program as a black-box can often yield optimal results.
4.4 RQ2: Sample Efficiency
To answer RQ2, we evaluate the sample efficiency of ISED against REINFORCE, IndeCateR, and
IndeCateR+ adding MNIST digits. IndeCateR+ [21] is variant of IndeCateR with sampling method and loss computation customized for higher dimensional setting such as the addition of 16 MNIST digits. We vary the size of the input and output space (sums, sum sum16) of P as well as the sample count, and report the average accuracy and standard deviation obtained from 5 randomized runs (Tables 4, 11-13).
For a lower number of samples, ISED outperforms all other methods on the three tasks, outperforming IndeCateR by over 80% on sums and sum]2. The experimental findings support the conceptual difference of REINFORCE-basee (Section 3.1). While ISED achieves accuracy similar the top performer for sumy and sum12 with a high sample count, it comes second on sum16 with IndeCateR+ beating ISED by 75.39%. This suggests approach is limited in scaling to high- nigh-dimensional inputs to P. and motivates exploring better sampling techniques, which is the core difference between IndeCateR and IndeCateR+.
methods providing a weak learning signal compared to ISED
4.5
RQ3: Data Efficiency
We now examine how ISED compares to state-of-ther trr baselines in terms of data efficiency. We compare ISED and A-NeSI terms of training time and accuracy on sum; and sum4. We choose these tasks for evaluation because A-NeSI has been shown to scale well to multi-digit addition tasks [24]. Furthermore, these tasks come from the MNIST-R suite which we use 5K training samples, which is less than what A-NeSI would have used in its evaluation (20K training samples for sumg

---

1
0.8
0.8
Accuracy
Accuracy
0.6
0.6
0.4
0.4
0.2
0.2
ISED
A-NeSI
ISED
A-NeSI
200
400
600
200
400
600
Time (seconds)
Time (seconds)
Figure 3: Accuracy vs. Time for sumg.
Figure 4: Accuracy vs. Time for sum..
and 15K for sum,). We plot the average test accuracy and standard deviation vs, training time (over 10 runs) in Figures 3 and where each point represents the result of epoch.
While ISED and A-NeSI learn at about the same rate for sum; after about 5 minutes training, ISED learns at much faster rate for the first 5 minutes, reaching an accuracy of 88. 28.22% after just epochs (Fig. 3). The difference between ISED and A-NeSI is more pronounced for sum4, with ISED reaching an accuracy of 94. 10% after just 10 epochs while A-NeSI reaches 49.51 5% accuracy the end of its 23rd epoch (Fig. 4). These results demonstrate that with limited training data, ISED is able learn more quickly than A-NeSI, even for simple tasks. This result is likely due to A-NeSI training 2 additional neural models in its learning pipeline compared to ISED, with A-NeSI training prior as well as a model estimate the program output and gradient.
Limitations and Future Work
The main limitation of ISED is the difficulty of scaling with the dimensionality of the space of inputs to the program P. There are interesting future directions adapting and expanding ISED for high dimensionality.. Specifically, improvements to the sampling strategy could help adapt ISED to complex space inputs. Techniques can be borrowed from the field of Bayesian optimization where such large spaces have traditionally been studied. Furthermore, there is merit systematically combining white-box and black-box methods. ISED is especially useful when logic programs fail to encode reasoning components. Therefore, believe that ISED be used an underlying engine for new neurosymbolic language that blends the accessibility of black-box with the performance of white-box methods.
Related Work
Neurosymbolic programming frameworks. These frameworks provide general mechanism to define white-box neurosymbolic programs. DeepProbLog [14] and Scallop [13] abstract away gradient calculations behind rule-based language. Others specialize in targeted applications, such as NeurASP [28] for answer set programming, or NeuralLog [3] for phrase alignment in NLP. ISED is similar in that it seeks make classes of neurosymbolic programs easier write and access; however, it diverges by offering an interface not bound by any specific domain or language syntax.
RL and sampling- based neurosymbolic frameworks. ISED incorporates concepts found in the RL algorithm REINFORCE [26] such as the sampling of actions according to the current policy distribution, similar to NASR [5], and IndeCateR [21]. Other work has proposed semantic loss function for neurosymbolic learning which measures how well neural network outputs match a given constraint [27]. While this technique resembles ISED in that it samples symbols from their predicted distributions to derive the loss, it relies on symbolic knowledge in the form of a constraint in Boolean logic, whereas ISED allows the program component to be any black-box program.
Specialized neurosymbolic methods. The majority of the neurosymbolic learning literature pertains to point solutions for specific use cases [7, 25]. In the HWF example, NGS [12] and several of its variants leverage hand-defined syntax defining the inherent structure within mathematical expres- sions. Similarly, DiffSort [18] leverages the symbolic properties of sorting to produce differentiable

---

sorting networks. Other point solutions address broader problem setups. such as NS-CL [15] which provides a framework for visual question answering by learning symbolic representations in text and images. For reading comprehension, the NeRd [3] framework converts NI questions into executable programs over symbolic information extracted from text. ISED aligns with all of these point solutions by aiming to solve problems that have thus far required technically specific solutions in order to access the advantages of neurosymbolic learning, but it takes an opposite and casier approach by forgoing significant specializations and instead leverages existing solutions as black-boxes.
Differentiable programming and non-differentiable optimization. Longstanding libraries in deep learning have grown to great popularity for their ability to abstract away automatic differen- tiation behind easy-to-use interfaces. PyTorch
[17] is able do so by keeping track of dynamic computational graph. Similarly, JAX [1] leverages functional programming to abstract automatic differentiation. ISED follows the style of these frameworks by offering an interface to abstract away gradient calculations for algorithms used in deep learning, but ISED improves upon them by allowing systematic compatibility of non-differentiable functions.
Conclusion
We proposed ISED, data- and sample-efficient algorithm for learning neural programs. Unlike existing general neurosymbolic frameworks which require diffcrentiable logic programs, ISED is compatible with Python programs and API calls to GPT, and it employs sampling-based technique to learn neural model parameters using forward evaluation. We showed that for neuroGPT, neuroPython, and neurosymbolic benchmarks, ISED achieves better accuracy than end-to-end neural models and similar accuracy compared to neurosymbolic frameworks. ISED also often achieves superior accuracy on complex programs compared to REINFORCCE-based and gradient estimation baselines. Furthermore, ISED learns in a more data- and sample-efficient manner compared to these baselines.
8 Acknowledgements
We thank the anonymous reviewers for useful feedback. This research was supported by ARPA-H grant D24AC00253-00, NSF award CCF 2313010, and by gift from AWS Al to ASSET (Penn Engineering Center on Trustworthy Al).
References
[1] James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Mandermaan-Milne and Qiao Zhang. JAX: composable transformations of Python+NumPy programs, 2018.
[2] Swarat Chaudhuri, Kevin Ellis, Oleksandr Polozov, Rishabh Singh, Armando Solar-Lezama, Yisong Yue, al. Neurosymbolic programming. Foundations and Trends in Programming Languages, 7(3):158-243, 2021.
[3] Zeming Chen, Qiyue Gao, and Lawrence S. Moss. NeuralLog: Natural language inference with joint neural and logical reasoning. In Proceedings of *SEM 2021: The Tenth Joint Conference on Lexical and Computational Semantics, pages 18-88,777 2021.
[4] 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.
[5] Cristina Cornelio, Jan Stuehmer, Shell Xu Hu, and Timothy Hospedales. Leamnngg where and when to reason in neuro-symbolic inference. In International Conference on Learning Representations, 2023.
[6] 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.
[7] Rajdeep Dutta, Qincheng Wang, Ankur Singh, Dhruv Kumarjiguda, Li Xiaoli, and Senthilnath Jayavelu. S-reinforce: A neuro-symbolic policy gradient approach for interpretable reinforce- ment learning, arXiv preprint ar arXiv:2305.07366 2023.
10

---

[8] 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 Proceedings of the 35th International Conference on Neural Information Processing Systems, pages 25134-25145, 2021.
[9] Paul Shekonya Kanda, Kewen Xia, and Olanrewaju Hazzan Sanusi. A deep learning- based recognition technique for plant Ieaf classification. JEEE Access, 9:162590-162613, 2021.
[10] Angelika Kimmig. Guy Van den Broeck, and Luc De Raedt. Algebraic model counting. CoRR, 2012.
[11] Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11 86(11):2278-234) 1998.
[12] Qing Li, Siyuan Siyuan Huang, Yining Hong, Yixin Chen, Ying Nian Wu, and Song-Chun Zhu. Closed loop neural-symbolic learning via integrating neural perception, grammar parsing, and symbolic reasoning. In Proceedingy of the 37th International Conference on Machine Learning, page 5884-5894, 2020.
[13] Ziyang Li, Jiani Huang, and Mayur Naik. Scallop: A language for neurosymbolic programming. In ACM International Conference on Programming Language Design and Implementation, page 1 1463-1488 1483-1187,220 2023.
[14] 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, page 3753-3763, 2018.
[15] Jiayuan Mao, Chuang Gan, Pushmeet Kohli, Joshua B. Tenenbaum, and Jiajun Wu. The neuro- symbolic concept learner: Interpreting scenes, words, and sentences from natural supervision. In International Conference on Learning Representations, 2019.
[16] Lukas Murmann, Michael Gharbi, Miika Aittala, and Fredo Durand. A multi-illumination dataset of indoor object appearance. In 2019 IEEE International Conference on Computer Vision (ICCV), Oct 2019.
[17] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary VeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In Proceedings of the 33rd International Conference on Neural Information Processing Systems, page 8026-8033 8037, 2019.
[18] Felix Petersen, Christian Borgelt, Hilde Kuehne, and Oliver Deussen. Differentiable sorting networks for scalable sorting and ranking supervision. In Proceedings of the 38th International Conference Machine Learning. 2021.
[19] 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.
[20] Joseph Redmon, Santosh Divvala, Ross Girshick, and Ali Farhadi. You only look once: Unified, real-time object detection. In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 779-788, 2016.
[21] 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 on Neural Information Processing Systems, 2023.
[22] Dagher R. Talhouk S.N., Fabian M. Landscape plant database, 2015.
[23]
Efthymia Tsamoura, Timothy Hospedales, and Loizos Michael. Neural-symbolic integration: A compositional perspective. In AAAI Conference on Artificial Intelligence, 2020.
[24] Emile van Krieken, Thiviyan Thanapalasingam. Jakub M. 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, 2023.
[25] Po- Pe-Wei Wang, Priya Donti, Bryan Wilder, and Zico Kolter. Satnet: Bridging deep learning and logical reasoning using differentiable satisfiability solver. Proceedings of the 36th International Conference on Machine Learning, pages 6545-6554, 2019.
11

---

[26] Ronald J. Williams. Simple statistical gradient- followwng algorithms for connectionist reinforce- ment learning, Machine Learning. 8(3-4):229-2555 1992.
[27] 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.
[28] Zhun Yang. Adam Ishay, and Joohyung Lee. Neurasp: Embracing neural networks into answer set programming. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, pages 1755-1762, 2020.
[29] Delu Zeng, Minyu Liao, Mohammad Tavakolian, Yulan Guo, Bolei Zhou, Dewen Hu, Matti Pietikäinen, and Li Liu. Deep learning for scene classification: survey, 2021.
12

---

A Explanation of Differences Between ISED and Baseline Methods
We explain the differences between ISED and prior techniques using the simple example of sumg. where digits are restricted to be between 0-2. Suppose that we are training a neural network Ma for this task, and we are considering the symbol-output sample where the ground truth symbols are and 2, i.e., = 1, = 2, and the ground truth output is 3. Suppose that the predicted distributions from Ma for 71 and 12 are [0.1, 0.6, 0.3] and [0.2, 0.1. 0.7] respectively. We now explain how different methods perform their loss computations.
A.1 ISED
Suppose ISED is initialized with sample count of and the sampled symbol-output pairs (11,2)3)), ((1,0), 1), and (),3) We use the add-mult semiring this example. ISED can be thought of as differentiating through the following summary logie program:
71 1 r2 = 2 3
1 Arz =
71 A2 =
As a result, the final vector calculated for the loss function before normalization would be
0.2
0.0
0.6 0.7 0.7+0... 0.3 * 0.1 0.0
where each value corresponds to the probability of the given output (possible outputs are in the range 0-4). Note that there are duplicate samples, ISED includes the duplicate probabilities in its aggregation. In our implementation, we would perform normalization on this vector and then pass it into the binary cross-entropy loss function, with the ground truth vector being:
0..0
0.0
0.0
1.0
0.0
We would then minimize this loss and update Ma accordingly.
If use the min-max semiring instead, is replaced by min and by max in the final vector calculation, resulting in
00.07
0.2
0.0
0.6
0.0
A.2 REINFORCE
Suppose REINFORCE is also initialized with a sample count of 3, and samples the same symbol- output pairs. The final reward is computed by dement-wise multiplication of the log probability of each sample with its reward value and taking the mean, as follows:
1 log(0.6) + log(0.7) (0.7)
[1.0
(0.6) log 0.2)
0.0
3
[og( + (0.1)
110
and the goal is to optimize My to maximize this reward. While this approach resembles ISED's loss computation for add-mult semiring, does not involve the mult step. As rewards possible values instead of possible combinations, the final reward would have been the same when (1,1) and (2,2) were the correct samples, instead of (1,2) and (2,1). Hence, the learning signal is weaker compared to ISED when there is more than one input to P.
13

---

A.3 IndeCateR and NASR
IndeCateR an extension of the REINFORCE estimator that unbiased with a provably lower variance. It assumes and exploits the factoring of the underlying multivariate distribution into independent categorical variables by summing out one dimension while keeping a sample for other dimensions fixed. For each sample drawn, IndeCateR systematically creates additional samples that differ on a single entry by enumerating all possible values for each variable. NASR targets efficient finetuning by setting the sample count to one and customizing the reward function.
The loss computation for IndeCateR and NASR are identical to that of REINFORCE, also providing weak signals with fewer samples. Furthermore, both set the reward to 0 for samples leading to incorrect predictions, effectively ignoring them, unlike ISED which penalizes such symbols. Since only the correct symbol contribute to the final reward, the signal is sparser than ISED, making it cemple-inefficient
A.4 A-NeSI
A-NeSI trains two additional neural networks: a prediction model Qo as a surrogate for P, and prior model R, for learning the parameters ar for the Dirichlet distribution Da.
Suppose A-NeSI is also initialized with sample count of 3. At each training step, A-NeSI first updates using ÿ = Mo(x). Next, it samples single symbol from each of the 3 distributions sampled from Da. and uses the sampled symbol-output pair and the standard cross entropy loss to update Qa. Then, A A-NeSI optimizes Ma by minimizing the loss L(Qar (r1,T2))) using the prediction model instead P.
A.5 DeepProbLog
DeepProbLog (DPL) enumerates all possible proofs for each output and aggregates probabilities
accordingly. For example, the proofs for y 1 include Y1 0, r2 = 1 and r 1, T22 = 0. Thus, the probability of this output is 0.6 * 0.2 + 0.1 * 0.1. The final vector calculated would be
0.1 0.2
0.6 * 0.2 + 0.1 * 0.1
0.1 0.7 + 0.6 0.1 + 0.3 0.2
0.6 * 0.7 + 0.3 * 0.1
0.3 0.7
and we would pass this vector into some loss function (e.g., cross-entropy), with the same ground truth vector that ISED would use. DPL would then minimize this loss and update Ma accordingly.
A.6 Scallop
Suppose Scallop is configured to use the diff-top-1-proot possible output, Scallop will use the proof of that output with the highest probability. For instance, the most likely proof for y = is rı and r2 = 0, and the probability the output y = is 0.6 0.2. The final vector calculated would be
semiring. This means that for each
[0.1 0.27
0.6 0.2
0.1 0.7
0.6 * 0.7
0.3
and we would pass this vector into some loss function (e.g., binarrycross-entropy). with the same ground truth vector that ISED would use. Scallop would then minimize this loss and update Ma accordingly. This probability estimation would change depending on the choice of semiring (e.g.. diff-top-k-proofe for different value of k).
B Evaluation Setup
For tasks with the MNIST dataset as unstructured data, we employ LeNet [11], a 2-layer CNN-based model, except for sums, sum]2, and sumia tasks where we choose smaller 2-layer CNN used by
14

---

IndeCateR [21]. For HWF. we also use a 2- 2-layer CNN-based model. For leaf classification tasks, images are scaled down and passed For the scene recognition, we use YOLOv8 and 3-layer convolutional network for neural program methods, 7-layer CNN for the purely neural solution, and CLIP with ViT-B/32. For all tasks included in RQ1, other than sudoku, we remove the final softmax function at the end of each network when evaluating IndeCateR since its sampling procedure yields optimal results without the softmax. We also do that same with REINFORCE if it results in higher accuracy. Since sudoku uses a pretrained CNN, we use the same CNN across all methods, including IndeCateR and REINFORCE.
simple CNN-based network with 4 convolutional layers.
We use the Adam optimizer with the best learning rate among 1e-3, 5e-4, le-4), We train for maximum 100 epochs, but stop early if the training saturates. For MNIST-R tasks, we used learning rate le-4 and trained ISED for 10 epochs, REINFORCE and IndeCateR for 50 epochs, and A-NeSI and NASR for 100 epochs. We trained ISED for 30 epochs, A-NeSI for 100 epochs, and the rest for 50 epochs for HWF and Leaf Classification with learning rate 1e-4. For the Scene Recognition task, we trained A-NeSI and the purely neural baseline 50 epochs and the rest 100 epochs with learning rate 5e-4. For tasks sums to sum16 we trained ISED for 50 epochs and the rest for 100 epochs with learning rate le-3. For Visual Sudoku, we follow the setting in NASR [5] and train for 10 epochs with learning rate 1e-5.
We configure ISED use the min-max semiring for HWF and the add-mul- semiring for all other tasks. We use categorical sampling and binary cross-entropy loss for ISED.
B.1 Neural-GPT Experiment Prompts
For leaf classification and scene recognition, the neural-GPT experiments, used the up-to-date version of GPT-4, gpt-4-1 10--1006-previi and gpt-4o respectively, with the parameter top-p set to le-8. We present the prompts used for the experiments in Tables 5 and 6.
Table 5: GPT-4 prompt for the leaf classification task.
You are an expert in classifying plant species based the margin, shape, and texture of leaves. You are designed to output a single JSON.
System message
<PLANT NAMES. Classify into one of: AARGIN/SHAPE/EETUUR Give your answer without explanation.
User message
Table 6: GPT-4 prompt for the scene recognition task.
You are an expert identifying room types based on the object detected.
System message
Give short single responses.
There are <DETECTED OBJECTS>. What type of room is most likely? Choose among <SCENES>.
User message
We use MARGIN = (entire, dentate, lobed, serrate, serrulate, undulate). SHAPE =(ellipti- cal, lanceolate, obovate, oblong, ovate), TEXTURE =(glossy, leathery, smooth, medium), and PLANT NAME E EAAlstonaa Scholaris, Citrus limon, Jatropha curcas, Mangifera indica, Ocimum basilicum, Platanus orientalis, Pongamia Pinnata, Psidium guajava, Punica granatum, Syzygium cumini, Terminalia Arjuna).
Furthermore, SCENES = (bathroom, bedroom, dining room, living room, kitchen, lab, office, home lobby, basement) and DETECTED OBJECTS is a list of maximum length 10 with duplicates.
C Full Performance Summary
We report the accuracy of all benchmarks with 1-sigma standard deviation in Tables 7, 8, 9, and 10. We further provide the performance comparison with varying sample counts with 1-sigma standard deviation in Tables 11, 12, and 13.
15

---

Table Performance comparison for DT leaf, GPT leaf, scene, and sudoku.
Accuracy (%)
Method
DT leaf
GPT leaf
Scene
sudoku
DPL
39.70 + 6.55
N/A N/A
N/A N/A
TO тO
Scallop
81.13 + 3.50
A-NeSI
78.82 +: 4.42
72.40 + 12:24
61.46 + 14.18
26.36 +: 12.68
REINFORCE
40.24 + 0.08
53.84 0.04
12.17 0.02
79.08 + 0.87
IndeCateR
78.71 + 5.59
69.16 2.35
12.72 2.51
66.50 + 1.37
NASR
16.41 + 1.79
17.32 = 1.92
2.02 + 0.23
82.78 + 1.06
ISED (ours)
82.32 + 4.15
79.95 + 5.71
68.59 + 1.95
80.32 1 1.79
Table 8: Performance comparison for HWF, sum2, sum3, and sum4.
Accuracy (%)
Method
HWF
Sum2
sum;
SUm,
DPL
TO
95.14 + 0.80
93.80 0.54
TO 80.10 = 20.4
Scallop
96.65 + 0.13
91.18 = 13.43
91.86 + 1.60
A-NeSI
3.13 0.72
96.66 + 0.87
94.39 + 0.77
+: 78.10
REINFORCE
88.27 + 0.02
74.46 26.29
19.40 - 4.52
13.84 = 2.26
IndeCateR
95.08 + 0.41
96.48 + 0.53
93.76 + 0.47
92.58 + 0.80
NASR
1.85 + 0.27
6.08 = 0.77
5.48 + 0.77
4.86 + 0.93
ISED (ours)
97.34 + 0.26
80.31 16.14
95.10 + 0.95
94.1 + 1.6
Table 9; Performance comparison for mult2, mod2, less-than, and add-mod-3,
Accuracy (%)
Method
mult
mod2
less-than
add-mod-3
DPL.
95.43 + 0.97
96.34 + 1.06
96.60 + 1.02
95.28 + 0.93 75.12 + 21.64
Scallop
87.26 + 24.70
77.98 + 37.68
80.02 + 3.37
A-NeSI
96.25 + 0.76
96.89 = 0.84
94.75 1 0.98
77.44 + 24.60
REINFORCE
96.62 + 0.23
94.40 + 2.81
78.92 + 2.31
95.42 + 0.37
IndeCateR
96.32 0.50
97.04 + 0.39
94.98 + 1.50
78.52 + 23.26
NASR
+
20.02 2.67
49.30 1 2.14
33.38 1 2.81
ISED (ours)
96.02 1 1.13
96.68 1 0.93
96.22 1 0.95
83.76 1 12.89
Table 10: Performance comparison for add-sub, equal, not-3-or-4, and count-3-4,
Accuracy (%)
Method
add-sub
equal
not-3-or-4
count-3-4
DPL
93.86 + 0.87
98.53 + 0.37
98. 19.19 + 0.55
TO 93.47 1 0.83
Scallop
92.02 1 1.58
71.60 1 2.29
97.42 1 0.73
A-NeSI
93.95 + 0.60
77.89 + 36.01
98.63 + 0.50
93.73 + 2.93
REINFORCE
17.86 1 3.27
78.26 + 3.96
99.28 + 0.21
87.78 +: 1.14
IndeCateR
93.74 + 0.44
98.18 + 0.39
99. 1 0.16
94.30 + 1.26
NASR
5.26 + 1.10
81.72 + 1.94
68.36 + 1.54
25.26 + 1.66
ISED (ours)
95.32 + 0.81
96.02 1.74
98.08 + 0.72
95.26 + 1.04
16

---

Table 11: Performance comparison for sumg with different sample counts k.
Accuracy (%)
Method
k 80
à 800
REINFORCE
8.32 2.52
8.28 0.39
IndeCateR
5.36 0.26
89.60 0.98
IndeCateR+
10.20 + 1.12
88.60 1.09
ISED (Ours)
87.28 + 0.76
87.72 = 0.86
Table 12: Performance comparison for sum12 with different sample counts k.
Accuracy (%
sum
Method
k = 120
h: 1200
REINFORCE
7.52 + 1.92
8.20 + 1.80
IndeCateR
4.60 0.24
77.88 6.68
IndeCateR+
6.84 2.06
86.92 1.36
ISED (Ours)
85.72 + 2.15
86.72 = 0.48
Table 13: Performance comparison for sum16 with different sample counts k.
Accuracy (%)
sum1s
Method
k= = 160
k = 1600
REINFORCE
5.12 1.91
6.28 1 1.04
IndeCateR
1.24 1: 1.68
5.16 1 0.52
IndeCateR+
4.24 - 0.95
83.52
+ 1.75
ISED (Ours)
6.48 0.50
8.13 1.10
D License Information
For implementing the baselines, we adapted the code from the official repositories of DeepProblog
[14] (Apache 2.0). Scallop [8] (MIT), A-NeSI [24] (MIT), NASR [5] (MIT), and IndeCateR [21] (Apache 2.0). Additionally, our benchmarks use fulti-illumination dataset [16] (CC BY 4.0), HWF dataset (CC BY-NC-SA 3.0) from NGS [12], subset of the leaf database [4] (CC BY 4.0), YOLOv8 (AGPL-3.0) and CLIP (MIT).
17

---

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]
Justification: The abstract and introduction claim that our proposed algorithm (ISED) achieves similar, and often superior accuracy, compared to state-of-the- neurosymbolic learning, REINFORCE-
and black-box gradient estimation frameworks, but in more data- and sample-efficient manner. We provide evidence for these claims in our evaluation in Sections 4.3, 4.4, 4.5.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as 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: We have separate section on Limitations (Section 5), and show limitation in scaling to high dimensional inputs with experimental results in RQ2 (Section 4.4).
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
18

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [NA]
Justification: Our paper does not include any theoretical results.
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 they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix 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 the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification; We release code for all baselines and ISED reproduce the results reported in the paper. The hyperparameters used for experiments are summarized in Appendix B.
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 make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
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 a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (c.g., a large language model), then there should either be way to 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 (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
19

---

5. Open access to data and code
Question: 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?
Answer: [Yes]
Justification: We are releasing data and code, along with the instructions for reproducing all results. We include directions for downloading datasets and setting up the environment.
Guidelines:
The answer NA means that paper does not include experiments requiring code. Please see the NeurlPS code and data submission guidelines (https://nips. cc/ /ttpdeee///eoeeummiiiii
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" 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 run to reproduce the results. See the NeurIPS code and data submission guidelines (https: / /nips. wwtppcccccggpcueeeeeeeeeeeeeeeee hwwp//gwdee///ee/e /CodeSubmic eeeiiissiiniiiieeeee
for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If 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: We provide information on data splits in Section 4.1 and provide the rest of the experimental details in Appendix B.
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 results are accompanied by standard deviation with clearly stated factors of variability. While some tables are presented without standard deviations (Tables 3 and 4), 1-sigma standard deviation provided for these results in Tables 7-13 in Appendix C.
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.
20

---

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 to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
Question:
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?
Answer: [Yes]
Justification: We provide details of the compute used in Section 4.2. We also specify the number of runs and epochs for each task (Appendix B) and training time for selected benchmarks (Section 4.5).
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: //tuuenursp.../ httpppl///tiissuiiiieeeeoooo
Answer: [Yes]
Justification:
We have reviewed the Code of Ethics and and followed them whenever
relevant.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If 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 (e.g.. if there is special consid- cration 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: We propose new framework for learning neural networks in presence of black-box components and there is societal impact to be pointed out.
21

---

Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact 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), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considcrations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is a 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 as intended and functioning conrectly, 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 deseribe 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:
We do not release new data models, hence the work poses such risks.
Guidelines:
The answer NA means that the paper poses no 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 to 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 is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
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?
Question:
Answer: [Yes]
Justification: For datasets, code, and pretrained models used, we cited the original paper and provided the license information in Appendix D. We stated the versions of GPT-4 and YOLO in Appendix B.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
22

---

The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. cow.coo////oo//o comdattaees 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 is 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: The paper releases code for the proposed learning algorithm, which is well documented with license and training information. The limitations are mentioned in the paper (Sections 4.4 and 5).
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an 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 as details about compensation (if any)?
Answer: [NA]
Justification: This paper did not involve any crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does 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 as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, 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 an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper did not involve any crowdsourcing or research with human subjects
Guidelines:
23

---

The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
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 expect authors adhere 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.
24


Reviews:
[{"review_id": "4OqU1g0tI8", "reviewer": "Reviewer_ubXN", "summary": "This paper is about learning the parameters for a neural network (or other differentiable structure) where its output is then provided to a different black-box procedure, and we can compute a loss for the (second) output from that procedure.\n\nThe procedure consists of four parts: infer, sample (+ execute), and estimate, and descend. Given the input, we \"infer\" using the neural network, which produces a distribution over the inputs to the black-box program. We \"sample\" from this distribution multiple times to construct possible inputs to the black-box program, and we run the program on these inputs. We \"estimate\" by combining the outputs from the program to construct a distribution over the black-box program's output space, only using differentiable operations over the neural network's outputs. We \"descend\" by computing the loss using that distribution against the ground-truth label and computing the derivative with respect to the neural network's parameters. \n\nThe authors consider several benchmark tasks: classifying leaf images to the correct plant species, scene recognition from images, arithmetic and sudoku solving using images of handwritten digits. The authors compare against two neuro-symbolic methods, A-NeSI which emulates the black-box program with a differentiable neural network, and three other methods for computing gradients through black-box programs. The authors show that their proposed method generally outperforms the comparison methods and demonstrates better data efficiency.", "questions": "- What is the specific sampling strategy used in Algorithm 1? Are there restrictions on what this sampling strategy is allowed to be?\n- For computing the results in the paper, how did you sample from the neural network at test time?", "limitations": "The author's description of the limitations seems adequate.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "### Originality\nIn my view, the paper explores an interesting point in the design space that is an interesting variant some of the existing baselines, e.g. it is akin to a sampled version of DeepProbLog. Much of the value of the paper is in showing that this variant works well empirically on a variety of tasks.\n\n### Quality\nThe paper performs a thorough evaluation on a variety of different tasks involving different image recognition problems and compares against many baselines, which convincingly demonstrates the empirical gains of this approach.\n\n### Clarity\nThe paper is generally well-written and easy to understand. Some aspects of the algorithm description could have been clearer, but I found the worked example in Appendix A very useful for both understanding the proposed algorithm and also how it compares to the baselines studied.", "weaknesses": "- The studied tasks all have a relatively small space of potential discrete outputs from the black-box program. The method seems to lack support for the case where outputs of the program can be real-valued.\n- If the combination of the initial neural network and black-box program produce the correct answer for an input with very low likelihood, or if the sampling is unlucky and fails to produce a black-box program input which gives the correct answer, it would seem that there is no learning signal at all. The method as stated is not adaptive to such cases, for example by sampling from the neural network more often until some suitable input is found.\n- The study of the proposed method is entirely empirical and there are no theoretical justifications provided for why it works (also as stated by the authors in item 3 of the paper checklist).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> The method seems to lack support for the case where outputs of the program can be real-valued.\n\nWe support program outputs that are real-valued, and the handwritten formula (HWF) benchmark is an example of this. As we mention on L136 and L158, after the sampling step, floating-point output space is discretized by grouping program outputs that are approximately equal (to account for the floating point error) into buckets. We treat these buckets as we would treat the discrete output space in any other task.\n\n> If the combination of the initial neural network and black-box program produces the correct answer for an input with very low likelihood, or if the sampling is unlucky and fails to produce a black-box program input which gives the correct answer, it would seem that there is no learning signal at all.\n\nWe first note that ISED works by rewarding sampled symbols that result in the correct output as well as penalizing sampled symbols that result in the wrong output. Even with no positive learning signal, ISED still provides some negative feedback. Although more advanced sampling strategies may reduce the likelihood of failing to produce input that gives the correct answer, any sampling-based strategy will have this limitation. This point is related to the main limitation of ISED that we discuss: it does not scale to high-dimensional inputs because it cannot produce a good learning signal in such cases. Nonetheless, we do intend to address this limitation in future work. \n\n> The study of the proposed method is entirely empirical and there are no theoretical justifications provided for why it works.\n\nWe will list this as a limitation.\n\n> What is the specific sampling strategy used in Algorithm 1?\n\nThe algorithm is generic and any sampling strategies could be used, but we only used categorical sampling in our experiments.\n\n> For computing the results in the paper, how did you sample from the neural network at test time?\n\nSimilar to training time, we perform the steps of ISED and obtain an output distribution. We take the argmax of this distribution as the final prediction.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4XsQLP9Prx", "reviewer": "Reviewer_2rwx", "summary": "The paper introduces a sample-efficient algorithm called ISED (Iterative Sampling for Efficient Differentiable Programming) for learning neural programs i.e. programs that have a neural network component (that needs to be learned) and another fixed program. The fixed program could be a python program, a call to a black box LLM model, or a logic program. The task here is to train this neural program using only end-to-end input-output data. The challenge lies in propagating gradients through the fixed program, which could be complex, non-differentiable, and black-box. The paper proposes an alternative to REINFORCE-based methods by  trying to approximate the fixed program as if input = u then output = v by sampling multiple u with the NN's predicted distribution and using  neurosymbolic methods to compute gradients through this approximate program.", "questions": "Why do tests time out during test time? While it is understandable for Sudoku, why does sum_4 also time out for DPL?", "limitations": "Limitations are addressed.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- Combining neural networks with pre-trained LLMs is an interesting idea and very useful in many applications. \n\n- The paper addresses the challenging problem of propagating gradients through black-box LLMs with an interesting approach.\n\n- The proposed method offers an alternative to REINFORCE-based methods which require significantly more samples due to weak supervision. \n\n- The evaluation is comprehensive. The authors considered many variants of benchmarks and baselines. The results are promising, showing better performance and sample efficiency than REINFORCE-based methods and faster training than the A-NeSI baseline.", "weaknesses": "One of the main limitations, as mentioned by the authors, is that the approach doesn't work effectively on high-dimensional intermediate inputs. The authors should definitely explore this limitation further.\n\n\nAlso one minor comment: The paper should present results for all benchmarks in Table 3. It is misleading to show mostly positive benchmarks in the main paper and relegate the negative ones to the appendix.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> The paper should present results for all benchmarks in Table 3. It is misleading to show mostly positive benchmarks in the main paper and relegate the negative ones to the appendix.\n\nWe did not intend to be misleading, but we understand how we gave off that impression. We note that this paper goes further than most other neurosymbolic work by evaluating on benchmarks that cannot be expressed as logic programs. Our goal for Table 3 was to highlight these benchmarks as well as the most interesting/complex benchmarks in our suite that were taken from the neurosymbolic literature (sum4, HWF, and Sudoku). In the final version, we will highlight more than just the six benchmarks in the main body to give a better idea of how the techniques compare across the benchmarks.\n\n> Why do tests time out during test time? While it is understandable for Sudoku, why does sum_4 also time out for DPL?\n\nWe used DeepProbLog with exact inference, which means that it is still collecting all proofs for each possible output in sum_4. DeepProbLog timing out on this task is consistent with prior work comparing Scallop to DeepProbLog [1] (Table 1).\n\n[1] Scallop: From Probabilistic Deductive Databases to Scalable Differentiable Reasoning, NeurIPS 2021", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7CO7Wkgmns", "reviewer": "Reviewer_E3jF", "summary": "This paper proposes an algorithm ISED for learning a composition between a neural model (e.g., using DNN to classify objects in an image) and traditional programming (e.g., calling GPT-4 to identify room type). ISED is based on reinforcement learning, which summarizes the input-output samples of the traditional black-box program as if-then logic programming. Evaluation of several benchmark tasks, such as leaf classification and scene recognition, shows the effectiveness and generalizability of the ISED.", "questions": "- What is the motivation of the composition?\n- What are the advantages of ISED over individual programming ?\n- What is the impact of the capability of traditional programming on the ISED’s performance?", "limitations": "The authors adequately addressed the limitations of this work.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "+ Proposing a data-efficient learning framework ISED.\n+ Evaluating the effectiveness of ISED on three types of benchmark tasks.\n+ Analyzing the efficiency of data sampling and used data for ISED.", "weaknesses": "- The motivation could be made stronger.\n- The advantages of ISED over individual programming are not investigated.\n- Lack of investigation on the impact of the capability of traditional programming on the ISED’s performance.\n\nMore specifically:\n\n. (Introduction) The motivation of this work is not very strong. If the two models work well, why composite them with a neural program? For the scene recognition example, DNN plus GPT-4 can identify objects in the image and classify the scene. What is the goal of the composed program? \n\n. (Method) ISED considers traditional programming as a black-box program. It is assumed that ISED can learn from any program. In the evaluation, GPT-4 is a powerful LLM that can generate good outputs. Thus, for a powerful black-box program, ISED works better. It is suggested to analyze how the capability of a black-box program affects the performance of neural symbolic learning.\n\n. (Evaluation) This study presents two new neural program learning benchmarks which both contain a program component that can make a call to GPT-4. A neural model can only learn  limited capability of LLM. The composite program may not replace individual programming?\n\n.(RQ1: Accuracy) The results indicate that ISED can achieve higher performance than other neurosymbolic methods. It is suggested to analyze the differences between the composite program and the individual programming.\n\n. (RQs) The three investigated RQs only focused on the performance and efficiency of ISED. Generally, the composite neural program aims to build a more explainable logic programming. The explainability is not verified.\n\n. The acronyms need to be defined in the first place, such as ISED and LLM.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "To address these concerns, we ran additional experiments (highlighted in bold) for tasks involving GPT-4 which we summarize here.\n\n### Leaf Classification\n\n| Architecture      | Test Accuracy      |\n| ------------- | ------------- |\n| Purely Neural | 78.50% |\n| CLIP   | 20.15% |\n|  **GPT-4o Vision**  |  52.72% |\n|  **GPT + GPT** |  32.74% |\n|  ISED (GPT) | 79.95% |\n| ISED (DT) |  82.32% |\n\n- GPT-4o vision and CLIP are pre-trained vision-language models\n- GPT+GPT refers to prompting GPT-4o vision to identify leaf traits (margin/shape/texture) from image and asking GPT-4 to classify based on these features.\n\n\n### Scene Recognition\n\n| Architecture      | Test Accuracy      |\n| ------------- | ------------- |\n| Purely Neural | 37.17% |\n| CLIP  | 51.09% |\n| **YOLO + GPT** | 18.57% |\n| **GPT + GPT** | 32.72% |\n| ISED | 68.59% |\n\n- YOLO+GPT refers to using YOLO, a pre-trained object detector, to identify objects in the scene and asking GPT-4 to classify based on these objects.\n- GPT+GPT refers to prompting GPT-4o to identify objects in the scene and asking GPT-4 to classify the scene.\n\nWe now address your individual concerns below.\n\n> What is the motivation of the composition?\n\nNeural programs target tasks that can be better solved with a pipeline involving a DNN followed by a program, compared to DNN alone. The goal of the learning algorithm is to train the neural network in this composed model with only end-to-end labels. The lack of intermediate labels makes it impossible to train the DNN directly and requires a way to backpropagate the loss through the program component. For the scene recognition example, we know the ground truth room type, but not the list of objects found in the scene. Hence, we are unable to train the DNN to detect objects using the standard supervised learning. On the other hand, with ISED, we can train the DNN to detect objects in this DNN plus GPT-4 pipeline, where GPT-4 identifies the room type based on the list of detected objects. A neural component is necessary for this task since traditional (purely symbolic) programs cannot deal with unstructured inputs like images. While we can train a custom DNN or use a pre-trained vision language model to directly predict the room type, we showed in our paper that ISED outperforms the purely neural baseline by 31.42% and zero-shot CLIP by 17.50% respectively.\n\n*Why can we not use only pre-trained models? Why do we need to train with ISED?*\n\nAlternatively, we can use pre-trained models for object detection without any finetuning while keeping the DNN plus GPT-4 structure. Simply using a pre-trained object detector YOLO, and GPT-4 for object detection, resulted in 19.57% and 59.78% accuracy respectively, compared to 68.59% for ISED. This demonstrates the benefit of training to achieve high accuracy on specific tasks.\n\n> What are the advantages of ISED over individual programming?\n\nFor the benchmarks involving GPT-4, we also used purely neural networks, and the pre-trained vision language model CLIP, as baselines. We reported that on the leaf classification task, ISED outperforms the purely neural baseline by 3.82% and zero-shot CLIP by 59.80%. For better comparison with the state-of-the-art foundation models, we ran more experiments using the recent vision language model GPT-4o. When directly asked to predict the species from the leaf image, GPT-4o achieves 52.72% accuracy. We also tried a GPT+GPT structure where we ask GPT-4o to predict leaf features from the input image and again prompt GPT-4 to classify based on them, which resulted in 32.73% accuracy. ISED’s GPT Leaf architecture that instead trains a custom neural network to identify leaf features achieves 79.95% accuracy, outperforming both. This demonstrates that it can be useful to compose a neural network and a black-box program to perform reasoning.\n\n> What is the impact of the capability of traditional programming on the ISED’s performance?\n\nIndeed, the capability of a black-box program affects the performance of neurosymbolic learning. This was shown in our two different methods of solving the leaf classification task. One implementation uses a decision tree from a leaf identification guide, and the other prompts the GPT-4 to identify the leaf based on the predicted features (margin, shape, texture). The ISED decision tree and GPT methods achieve 82.32% and 79.95% accuracy, respectively. ISED learns better from the decision tree, which is directly based on expert knowledge and has better leaf classification capability compared to GPT-4. Although it is possible that a newer version of GPT could close this accuracy gap, we would like to note that a good selection of each component of the composite is important for good performance. To benefit from using an LLM in the black-box program, the part delegated to the LLM should be something it can do well. If the LLM produces bad outputs more often than good outputs, ISED wouldn’t be able to learn from such programs.\n\n> Generally, the composite neural program aims to build a more explainable logic programming. The explainability is not verified.\n\nWhile explainability has not been the focus of our paper, ISED by design offers better explainability than purely neural models. With ISED, we can recover intermediate labels during test time, and there have been prior works [1]  on how intermediate labels improve explainability. Furthermore, when the black-box program is a logic program or a simple Python program without API calls, we can look at the implementation of the symbolic component and analyze how the symbols predicted by the neural network contribute to the final prediction, offering additional explainability.\n\n[1] Concept bottleneck Models, ICML 2020. \n\n> The acronyms need to be defined in the first place, such as ISED and LLM.\n\nIn the final version, we will define these acronyms upfront.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JYh8d9sxAn", "reviewer": "Reviewer_5P1v", "summary": "This paper looks at optimizing \"neural programs\", which are composites of a deep neural network (DNN) followed by a program written in a traditional programming language or an API call to a large language model (LLM). This paper proposes ISED (Infer-Sample-Estimate-Descend) for learning neural programs that only rely on input-output samples of black-box components. ISED is evaluated on benchmarks involving calls to GPT-4 and prior work from neurosymbolic learning literature, showing comparable performance to state-of-the-art neurosymbolic frameworks and achieving more data- and sample-efficient results.", "questions": "* What are the choice reasons for the types of defined structural mapping?\n* What does \"interpretation\" mean here in L145? How is that related?\n* Besides scalability, what other future directions do the authors see as promising for the development and improvement of neural programs?", "limitations": "As is acknowledged by the authors, ISED struggles with scaling to high-dimensional input spaces, limiting its applicability in complex scenarios.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "* From comprehensive evaluations, ISED significantly outperforms prior work regarding accuracy and data efficiency.\n* The proposed ISED approach is novel by estimating gradients of black-box programs from inductive samples.", "weaknesses": "* Clarity: While Section 1 and 2 is nicely written and can be understood by readers new to this field, it is challenging to read Section 3 due to over-formalism and the lack of end-to-end running examples. \n* Clarity: The symbolism is a bit inconsistent. $x$ and $y$ in Section 2 presents the input to $M_\\theta$ and output from $P$, while in Section 3.1 $x$ and $y$ denotes the \"input-output samples\" of $P$. \n\nOther minor editorial suggestions:\n* L3 and L20: double quotation can be done via `` and '' in LaTeX.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> While Section 1 and 2 is nicely written and can be understood by readers new to this field, it is challenging to read Section 3 due to over-formalism and the lack of end-to-end running examples.\n\nThank you for this feedback. We agree that the lack of end-to-end running examples makes the algorithm harder to understand and will keep using the HWF example throughout our explanation in the final version.\n\n> The symbolism is a bit inconsistent. and in Section 2 presents the input to and output from , while in Section 3.1 and denotes the \"input-output samples\" of .\n\nThank you for this suggestion. We noticed this inconsistency after submission and improved the wording in a newer draft of the paper.\n\n> What are the choice reasons for the types of defined structural mapping?\n\nWe define these structural mappings to state what input and output types of black-box programs are supported by our framework. Since Python programs support many kinds of structured inputs, we wanted to formulate ISED in a way that is compatible with a diverse set of programs. For example, ISED supports sorting variable length lists of digits (hence the permutation type), which is a task that cannot be easily expressed in other neurosymbolic learning frameworks like Scallop [1]. The types defined in the paper is not an exhaustive list of types supported by the framework, but rather a fraction that were implemented for our benchmarks. The structural mappings also serve to exchange information between the neural network and the black-box program, and explain how to derive the loss, which is why we define vectorizer and aggregator for each type.\n\n[1] Scallop: From Probabilistic Deductive Databases to Scalable Differentiable Reasoning, NeurIPS 2021\n\n> What does \"interpretation\" mean here in L145? How is that related?\n\n“Interpretation” refers to the discrete vs probabilistic interpretations of inputs and outputs to the black-box program. We distinguish the two interpretations to make it clear how the sampling stage deals with probability distribution (from the neural network) and samples discrete values from them. Additionally, we wanted to clearly explain how the discrete outputs from the black-box program are vectorized/ turned into probabilistic outputs, which is crucial for computing the loss.\n\n> Besides scalability, what other future directions do the authors see as promising for the development and improvement of neural programs?\n\nFor other future work, we would like to extend the gradient estimation technique to be compatible with more complex architectures. For example, end-to-end training with a neural network, followed by a program, followed by another neural network could be an interesting direction, especially if the final neural network is trying to train a bias correction parameter. Such an architecture would require an explicit estimation of the Jacobian of the black-box program, which ISED does not currently do. This estimation could use finite difference or randomized finite difference techniques from numerical analysis. For this work, we plan to also provide some theoretical justification behind the gradient estimation, possibly showing that it is an unbiased estimator of the true gradient.\n\n> ISED seems challenging to implement and understand by practitioners without a strong background in related fields.\n\nIn most cases, a practitioner would only need to specify the input and output types of the program component. Furthermore, a benefit of using ISED is that the program can be specified in Python, which removes the need to learn specialized languages like Datalog. However, it is true that it might be challenging to implement a task where the black-box component has an input or output type that our implementation does not yet support.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for their insightful comments. Our work explores the idea of composing DNNs with any program that performs reasoning over the network’s predictions. We introduced a novel algorithm for learning such composites with a black-box program component. We introduced new benchmarks that use an LLM in the program component, and our experiments show that our algorithm can learn more effectively than previous techniques in these settings. 

We also thank the reviewers for pointing out some weaknesses including the scalability of our algorithm as well as our evaluation that is strictly empirical. These insights help motivate future work on ISED, including improving its scalability and developing a gradient estimator that is provably unbiased.

Meta-review: The paper appears to make significant progress in the direction of neurosymbolic approaches and integration of differential and traditional programming. All reviewers agreed that the novelty in the paper is substantial and that the empiric evaluation is sound. While some technical concerns were raised in the reviews, these could be mostly addressed in the rebuttal phase. Further, the presented type of neuro-symbolic research should be of broad interest to the NeurIPS community. Overall, the clear consensus is to accept the paper.
Decision: Accept (poster)