Neural-Symbolic Recursive Machine for Systematic Generalization
Authors: Qing Li
Yixin Zhu
Yitao Liang
Ying Nian Wu
Song-Chun Zhu
Siyuan Huang
Venue: ICLR 2024 poster (2024)
Keywords: Neuro-symbolic AI
Systematic Generalization
Compositional Generalization
Primary area: neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
TL;DR: We present Neural-Symbolic Recursive Machine for systematic generalization, which achieves state-of-the-art performance on SCAN, PCFG, and HINT.

Abstract: Current learning models often struggle with human-like systematic generalization, particularly in learning compositional rules from limited data and extrapolating them to novel combinations. We introduce the Neural-Symbolic Recursive Ma- chine ( NSR), whose core is a Grounded Symbol System ( GSS), allowing for the emergence of combinatorial syntax and semantics directly from training data. The NSR employs a modular design that integrates neural perception, syntactic parsing, and semantic reasoning. These components are synergistically trained through a novel deduction-abduction algorithm. Our findings demonstrate that NSR’s design, imbued with the inductive biases of equivariance and compositionality, grants it the expressiveness to adeptly handle diverse sequence-to-sequence tasks and achieve unparalleled systematic generalization. We evaluate NSR’s efficacy across four challenging benchmarks designed to probe systematic generalization capabilities: SCAN for semantic parsing, PCFG for string manipulation, HINT for arithmetic reasoning, and a compositional machine translation task. The results affirm NSR ’s superiority over contemporary neural and hybrid models in terms of generalization and transferability.

Published as a conference paper at ICLR 2024
NEURAL- YMMOOLI RECURSIVE MACHINE FOR SYSTEMATIC GENERALIZATION
Qing Li", Yixin Zhu?, Yitao Liang' Ying Nian Wu', Song- Chug Zhu Zhul,,,Syuan Huang' National Key Laboratory of General Artificial Intelligence. BIGAI
2 Department of Statisties, UCLA Institute for Artificial Intelligence, Peking University https: https:// //liqing uste.ustee...... uste.github titt....... io/NSR
ABSTRACT
Current learning models often struggle with human-like systematic generalization, particularly in learning compositional rules from limited data and extrapolating them to novel combinations. We introduce the Neural-Symbolic Recursive Ma- chine (NSR), whose core is Grounded Symbol System (GSS), allowing for the emergence of combinatorial syntax and semantics directly from training data. The NSR employs modular design that integrates neural perception, syntactic parsing, and semantic reasoning. These components are synergistically trained through a novel deduction-abduction algorithm. Our findings demonstrate that NSR's design, imbued with the inductive biases of equivariance and compositionality, grants it the expressiveness to adeptly handle diverse sequence-to-Se to-seuence tasks and achieve unparalleled systematic generalization. We evaluate NSR' ' efficacy across four challenging benchmarks designed to probe systematic generalization capabilities: SCAN for semantic parsing, PCFG for string manipulation, HINT for arithmetic reasoning, and a compositional machine translation task. The results affirm NSR's superiority over contemporary neural and hybrid models in terms of generalization and transferability.
INTRODUCTION
defining characteristic human intelligence, systematic compositionallit (Lake and Baroni, 2023), represents the algebraic capability to generate infinite interpretations from finite, known components, famously described as the "infinite use of finite means" (Chomsky, 1957; Montague, 1970; Marcus, 2018; Xie et al., 2021). This principle is essential for extrapolating from limited data to novel combinations (Lake et al., 2017; Jiang et al., 2023). To evaluate machine learning models' ability for systematic generalization, datasets such as SCAN (Lake and Baroni, 2018), PCFG (Hupkes et al., 2020), CFQ (Keysers et al., 2020), and HINT (Li et al., 2023b) have been introduced. Traditional neural networks often falter these challenges, leading to the exploration of inductive biases to foster better generalization. Innovations like relative positional encoding and layer weight sharing have been proposed improve Transformers' generalization capabilities (Csordás et al., 2021; Ontanón et al., 2022). Moreover, neural-symbon stack machines have been demonstrated to achieve remarkable accuracy on tasks similar SCAN (Chen al., 2020), and large language models have been guided towards compositional semantic parsing on CFQ (Drozdov et al., 2023). Yet, these solutions usually require domain-specific knowledge and struggle with domain transfer.
In pursuit of achieving human-like systematic generalization across various domains, we introduce the Neural-Symbole Recursive Machine (NSR), a principled framework designed for the joint learning of perception, syntax, and semantics. At the heart of NSR lies a Grounded Symbol System (GSS), depicted in Fig. 1, which emerges solely from the training data, eliminating the need for domain- specific knowledge. NSR employs modular design, integrating neural perception, syntactic parsing, and semantic reasoning. Initially, a neural network acts as the perception module, grounding symbols in raw inputs. These symbols are then organized into a syntax tree by cansiiiionbbsee. neural dependency parser (Chen and Manning, 2014), followed by the interpretation of their semantic meaning using functional programs (Ellis et al., 2021). We prove that NSR's capacity for various sequence-to- to-eueeue--- tasks, underpinned by the inductive biases of equivariance and compositionality. allows for the decomposition of complex inputs, sequential processing of components, and their

---

Published as a conference paper at ICLR 2024
(1) SCAN
(2) PCFG
(3) HINT
junp lift after walk roice
agrend suup C. rggat RE
2+
after 12 [WALK, WALK, LTURN, JUMP)
append 53 [C, B.
- -0
Lift ILTURN, JUMP]
twice 9 [WALK, WALK]
soap 51 [C.
BI
rggaal 52 (8.
2 2.2 X 12
jump [JUMP]
wark
[WALK]]
A [A] B C2
B BB]
4
3 33
5 9.9
Figure I: Illustrative examples of GSSs demonstrating human-like reasoning processes. (a) SCAN: each node encapsulates a triplet (word, symbol, action sequence). (b) PCFG: nodes consist of triplets (word, symbol, letter list). (c) HINT: nodes contain triplets (image, symbol, value). Symbols are denoted by their indices.
recomposition, thus facilitating the acquisition of meaningful symbols and compositional rules. These biases are critical for NSR's 's exceptional systematic generalization.
The end-to-end optimization of NSR poses significant challenges due the lack of annotations for the internal GSS and the model's non-differentiable components. To circumvent these obstacles, we devise a probabilistic learning framework and a novel deduuciion-abduutiion algorithm for the joint training. This algorithm starts with greedy deduction to form an initial GSS, which might be inaccurate. A top-down search-based abduction follows, aiming to refine the initial GSS by exploring its neighborhood for better solutions until the correct result is obtained. This refined GSS acts as pseudo supervision, enabling the independent training of each NSR component.
NSR's 's performance is validated against three benchmarks that test systematic generalization:
1. SCAN (Lake and Baroni, 2018), for translating natural language commands to action sequences;
2. PCFG (Hupkes et al., 2020), for predicting output sequences from string manipulation commands;
HINT (Li et al., 2023b), for computing results of handwritten arithmetic expressions.
NSR establishes new records on these benchmarks, achieving 100% generalization accuracy on SCAN and PCFG, and surpassing the previous best accuracy on HINT by 23%. Our analyses show that NSR's modular design and intrinsic inductive biases lead to stronger generalization than traditional neural networks and enhanced transferability over existing neural-symbolic models, with reduced need for domain-specific knowledge. NSR's s effectiveness is further demonstrated on a compositional machine translation task by Lake and Baroni (2018) with a 100% generalization accuracy, revealing its potential in practical applications with complex and ambiguous rules.
2 RELATED WORK
The exploration of systematic generalization within deep neural networks has captivated the machine learning community, especially following the introduction of the SCAN dataset (Lake and Baroni, 2018). Various benchmarks have since been introduced across multiple domains, including semantic parsing (Keysers et al., 2020; Kim and Linzen, 2020), string manipulation (Hupkes al., 2020), visual question answering (Bahdanau et al., 2019; Xic et al., 2021), grounded language understanding (Ruis al., 2020), mathematical reasoning (Saxton al., 2018; Li et al., 2023b), physical reasoning (Li et al., 2024a; Dai et al., 2023; Li et al., 2022), word learning (Jiang et al., 2023), robot manipulation et al., 2024b; Wang et al., 2024; Li et al., 2023a), and recently developed open-ended worlds (Fan et al., 2022; Xu et al., 2023), serving as platforms to evaluate different aspects of generalization, like systematicity and productivity. In particular, research in semantic parsing (Chen et al., 2020; Herzig and Berant, 2021; Drozdov et al., 2023) has explored incorporating diverse inductive biases into neural networks to improve performance across these datasets. We categorize these approaches into three groups based on their method of embedding inductive bias:
Architectural Prior: Techniques under this category aim to refine neural architectures to foster compositional generalization. Dessi and Baroni (2019) have shown convolutional networks' effec- tiveness over RNNs in SCAN's "jump" split. Russin et al. (2019) improve RNNs by developing separate modules for syntax and semantics, while Gordon et al. (2019) introduce permutation equivariant seq2seq model with convolutional operations for local equivariance. Enhancements in Transformers' systematic generalization through relative positional encoding and layer weight sharing are reported by Csordás et al. (2021) and Ontanón et al. (2022). Furthermore, Gontier et al. (2022) embed entity type abstractions in pretrained Transformers to boost logical reasoning.
2

---

Published as a conference paper at ICLR 2024
2. Data Augmentation: This strategy devises schemes to create auxiliary training data to foster compositional generalization. Andreas (2020) augment data by interchanging fragments of training samples, and Akyürek et al. (2020) employ a generative model to recombine and resample training data. The meta sequence-to-sequee
model (Lake, 2019) and the rule synthesizer (Nye et al., 2020) utilize samples from meta-grammar resembling the SCAN grammar.
3. Symbolic Scaffolding: This strategy entails the integration of symbolic components into neural frameworks to enhance generalization. Liu al. (2020) link a memory- memory-augmented model with analytical expressions, emulating reasoning processes. Chen et al. (2020) embed symbolic stack machine within a seq2seq model, with a neural controller managing operations. Kim (2021) derive latent neural grammars for both the encoder and decoder in a seq2seq model. While these methods achieve significant generalization by embedding symbolic scaffolding, their reliance on domain-specific knowledge and complex training methods, such as hierarchical reinforcement learning in Liu et al. (2020) and exhaustive search in Chen et al. (2020), restrict their practical use.
Beyond these technical implementations, existing research underscores two core inductive biases critical for compositional generalization: equivariance and compositionalliy. The introduced NSR model incorporates a generalized Grounded Symbol System as symbolic scaffolding and instills these biases within its modules, facilitating robust compositional generalization. Distinct from prior neural- symbolic methods, NSR requires minimal domain-specific knowledge and forgoes a specialized learning curriculum, leading to enhanced transferability and streamlined optimization across different domains, as demonstrated by our experiments; we refer readers to Sec. 4 for details.
Our work also intersects with neural-symbolic approaches for logical reasoning, such as the in- troduction of Neural Theorem Provers (NTPs) by Rocktäschel and Riedel (2017) for end-to-end differentiable proving with dense vector representations of symbols. Minervini et al. (2020) ad- dress NTPs' computational challenges with Greedy NTPs, extending their application to real-worll datasets. Furthermore, Mao et al. (2018) present Neuro-Symbolic Concept Learner that utilizes a domain-specific language learn visual concepts from question-ansswrrigg pairs.
3
NEURAL-SYMBOLIC RECURSIVE MACHINE
3.1
REPRESENTATION GROUNDED SYMBOL SYSTEM (GSS)
The debate between connectionism and symbolism on the optimal representation for systematic generalization has been longstanding (Fodor et al., 1988; Fodor and Lepore, 2002; Marcus, 2018). Connectionism argues for distributed representations, where concepts are encoded across many neurons (Hinton, 1984), while symbolism advocates for physical symbol systems, with each symbol encapsulating an atomic concept, and complex ideas constructed through syntactical combination (Newell, 1980; Chomsky, 1965; Hauser al., 2002; Evans and Levinson, 2009). Symbol systems, due to their interpretabilityy enable higher abstraction and generalization capabilities than distributed representations (Launchbury, 2017). However, developing symbol systems knowledge-intensiv and may lead to brittle systems, susceptible to the symbol grounding problem (Haraad, 1990).
We introduce a Grounded Symbol System (GSS) the internal representation for systematic gener- alization, aiming to seamlessly integrate perception, syntax, and semantics, as depicted by Fig. 1. Formally, GSS is directed tree T =< (a, v), 2, with each node being triplet consisting of grounded input æ, abstract symbol 8, and its semantic meaning e. The edges represent semantic dependencies, with an edge - j indicating node i's meaning depends on node j.
Given the delicate nature and intensive effort required to create handcrafted symbol systems, the necessity of anchoring them in raw inputs and deriving their syntax and semantics directly from training data is paramount. This critical aspect is explored in depth in the subsequent sections.
3.2 MODEL: NEURAL-SYMBOOT RECURSIVE MACHINE (NSR)
The NSR model, structured to induce a GSS from the training data, integrates three trainable modules (Fig. 2): neural perception for symbol grounding, dependency parsing to infer dependencies between symbols, and program synthesis deduce semantic meanings. Given the absence of ground-truth GSS during training, these modules must be trained Below, we detail these modules and the end-to-end learning approach.
without intermediate supervision.
3

---

Published as a conference paper at ICLR 2024
Inference
Learning
Grounded Symbol System
T== (x,,,,,
X
Neural
Dependency Parsing
5,e
Program
y
Abduction
Perception
Induction
Figure 2: Illustration of the inference and learning pipeline in NSR.
Neural Perception This module converts raw input x (e.g-, a handwritten expression) into a symbolic sequence s, represented by a list of indices. addresses the perceptual variability raw input signals, ensuring that each predicted token wy E accurately matches specific segment of the input 2; Formally, this relationship expressed as:
p( ; 0p) = I
pl we ww 0p)
softmax (o(i; Bp)))
where p(w; z4; B2) denotes a scoring function parameterized by neural network with parameters 0p. The design of this neural network varies with the type of raw input and can be pre-trained, such as using pre-trained convolutional neural network for processing image inputs.
Dependency Parsing To deduce the dependencies among symbols, we employ connitionn-based neural dependency parser (Chen and Manning, 2014), a widely used method in natural language sentence parsing. Operating as a state machine, the parser identifies possible transitions to transform the input sequence into dependency tree, iteratively applying predicted transitions until the parsing process is complete; Fig. A1 for illustration. At each step, the parser predicts transition based on the state representation, which includes the top elements of the stack and buffer, along with their direct descendants. A two-layer feed-forward neural network, given this state representation, determines the next transition. Formally, for an input sequence 8, the parsing process is defined as:
0.)) p(T)s;0,)
I p(41c;0,), 1,TT
where 0g the parameters of the parser, T {1 (2,,.,,,)))) h) that generates the dependency tree e, and C is the state representation at step i. A greedy decoding strategy employed to determine the most likely transition sequence for the given input sequence.
is the sequence of transitions
Program Induction Influenced by developments in program induction (Ellis et al., 2021; Balog al., 2017; Devlin et al., 2017), utilize functional programs express the semantics of symbols, framing learning as process of program induction. Symbolic programs offer enhanced generalizabil- ity, interpretability, and sample efficiency over purely statistical approaches. Formally, given input symbols and their dependencies e, the relationship is defined as:
plule,
p(u: (s,, children(ss):
where 0 denotes the set of induced programs for each symbol. Symbolic programs are utilized in practice, ensuring a deterministic reasoning process.
Deriving symbol semantics involves identifying program that aligns with given examples, employing pre-defined primitives. Based on Peano axioms (Peano, 1889; Xie al., 2021), we select universal set of primitives, such as 0, inc, dec, == and if, proven to be sufficient for any symbolic function representation; see Sec. 3.4 for an in-depth discussion. To streamline the search and improve generalization, we include a minimal subset of Lisp primitives and the recursion primitive (Y- combinator (Peyton Jones, 1987)). DreamCoder (Ellis et al., 2021) is adapted for program induction; modified it to accommodate noise in examples during the search.
Model Inference Fig. 2 depicts the model inference process, beginning with the neural perception module translating input æ, such as a handwritten expression from Fig. 1 (3) HINT, into a sequence of symbols, + 3 9. The dependency parsing module then structures this sequence into a dependency tree, for instance, programs associated with each symbol to compute node values in a bottom-up fashion, yielding calculations like 3 x 27, followed by 2 + 27 29.
2x and - 3 9. Subsequently, the program induction module employs
4

---

Published as a conference paper at ICLR 2024
3.3 LEARNING
The intermediate GSS in NSR is both latent and non-differentiable, making direct application of backpropagation unfeasible. Traditional approaches, such as policy gradient algorithms like REINFORCE (Williams, 1992), face difficulties with slow inconsistent convergence (Liang et al., 2018; Li et al., 2020). Given the vast search space for GSS, a more efficient learning algorithm is imperative. Formally, for input 2, intermediate GSS 7 =< (I, e), 2, and output y, the likelihood of observing (z, y), marginalized over T, expressed as:
ply θ) = Σ PT,, 0) T
Σ p(s|=;0p)ples 0, e @1)(((())) 8,6,0
where maximizing the observed-data log-likelihood L(x, y) = logp(y(>) becomes the learning objective, from maximum likelihood estimation viewpoint. The gradients of with respect to 8p. 0s 8r are as follows:
Vo, [(x, v) ET~p(T x. v ( 0p)],
vg, Lz. 9) ET a Vo, log 0,)]. Ve, L(x, EETPpTT an)
(5)
Ve, (ogp(ols,ec e; 0r)].
where p(T|2, y) denotes the posterior distribution Tf given (x, y). which can be represented as:
p p(T,yla;3) p(T|2, = Σr P(T ,(z;))
O, if T Q
p Ereeq P(T
if
(6)
with Q the set of I' congruent with y.
Due to the computational challenge of taking expectations with respect to this posterior dis- tribution, Monte Carlo sampling is utilized for approximation. This optimization strategy tails sampling a solution from the posterior dis- tribution and iteratively updating each module through supervised training, circumventing the difficulty of sampling within vast, sparsely populated space.
X4X 4 7 4
23
(1) abduce perception: change one symbol
7777
28
16
77
44
4
L
(2) abduce syntax: rotate one
Iaductiin-Abddctioon The essence of our learning approach is an efficient sampling from the posterior distribution p( p(T(xx, 3),, achieved through the deduction-abduction
44
+++
11
X
algorithm
4 44
4
(Alg. A1). For an instance (æ. y). we initially perform greedy deduction from to obtain initial GSS T =< (z, 6) ē >. To align 7 with the correct result y during training, top- down abduction search is employed, iterating the neighbors of T and adjusting across perception, syntax, and semantics; see Figs. 3 and A2 for more details. This search ceases upon finding 7 that yields or reaching prede- termined number of steps. Theoretically, this method acts Metropolis-Hoe Hastings sampler for p(T). a. y). facilitating an efficient approach to model training (Li et al., 2020).
(3) abduce semantics: change one value
+
23
16
4
44
Figure 3: Illustration of abduction in HINT over per- ception, syntax, and semantics. Elements modified during abduction are emphasized red.
3.4 EXPRESSIVENESS AND GENER ALIZATION OF NSR
We now examine the characteristics of NSR. particularly its expressiveness and ability to systemati- cally generalize, which are attributed to its inherent inductive biases.

---

Published as a conference paper at ICLR 2024
Expressiveness The capacity of NSR to represent broad spectrum of seq2seq tasks is substantiated by theoretical analysis. The following theorem articulates the model's '' expressiveness.
Theorem 3.1. Given any finite dataset using only four primitives: {0, inc, ==, if).
{(x', y²) there exists an NSR that can express D
The proof of this theorem involves constructing a specialized NSR that effectively "memorizes" all examples in D through comprehensive program:
(SR(2)
(2))(())=001))11 yf, (f(ff())==111))))1)11))))))))))) (x)=-111111- (.. o))....
serving as a sophisticated lookup table constructed with =if and the indexing scheme provided by {0, ) (proved by Lemmas C. and C.2). Given the universality of these four primitives across domains, NSR'S 's ability to model variety of seq2seq tasks is assured, offering improved transferability compared to preceding neural-symboll models.
The program outlined in Eq. (7), while guaranteeing perfect accuracy on the training dataset, lacks in generalization capacity. For effective generalization, it is essential incorporate certain inductive biases that are minimal yet universally applicable across various domains. Inspired by seminal works in compositional generalization (Gordon et al., 2019; Chen al., 2020; Xie et al., 2021; Zhang et al., 2022), we advocate for two critical inductive biases: equivariance and compositionality. Equivariance enhances the model's systematicity, enabling to generalize concepts "jump'
Generalization
such as "jump twice' from examples like { "run'' ' rrun twice' whereas compositionality increases the model's ability to extend these concepts to longer sequences, e.g., 'run and jump twice''.
The formal definitions of equivariance and compositionality are as follows:
Definition 3.1 (Equivariance). For X' and V, and a permutation group P with operations Tp X - X and T : y - y, mapping & X - y is equivariant iff Vz e X, pep P ((Tzz) = (2)()).
Definition 3.2 (Compositionalltyy For sets X' and V, with composition operations To (X, X) X and TV ()r y. a mapping & : X' + y is compositional iff 37,, TV Va E X, x2 E X ((T. (z) (x2)).
The three modules of NSR- neural perception (Eq. (I)), dependency parsing (Eq, (2)), and program induction (Eq. (3)) exhiitt equivariance and compositionality, functioning as pointwise transforma- tions based on their formulations. Models demonstrating exceptional compositional generalization, such as NeSS (Chen et al., 2020), LANE (Liu et al., 2020), and NSR, inherently possess these properties. This leads to our hypothesis regarding compositional generalization:
Hypothesis 3.1. A model achieving compositional generalization instantiates a mapping c that is inherently equivariant and compositional.
(: X - y
EXPERIMENTS
Our evaluation of the NSR's capabilities in systematic generalization extends across three distinet benchmarks: (i) SCAN (Lake and Baroni, 2018), focusing on the translation of natural language commands to action sequences; (ii) PCFG (Hupkes al., 2020), aimed predicting output sequences from string manipulation commands; and (ii) HINT (Li et al., 2023b), predicting outcomes of handwritten arithmetic expressions. Furthermore, explore NSR's performance on a compositional machine translation task (Lake and Baroni, 2018) to validate its applicability to real-world scenarios.
4.1 SCAN
The SCAN dataset (Lake and Baroni, 2018) emerges as a critical benchmark for assessing machine learning models' systematic generalization capabilities. It challenges models to translate natural language directives into sequences of actions, simulating the movement of an agent within a grid-like environment.
Following established studies (Lake, 2019; Gordon et al., 2019; Chen et al., 2020), we assess NSR using four splits: (i) SIMPLEF, where the dataset is randomly divided into
Evaluation Protucols

---

Published as a conference paper at ICLR 2024
training and test sets; (ii) LENGTH, with training output sequences up to 22 actions and testing on sequences from 24 to 48 actions; (iii) JUMP, training excluding the "jump" command mixed with other primitives, tested combinations including "jump"; and (iv) AROUND RIGHT, excluding "around right" from training but testing on combinations derived from the separately trained "around" and "right."
Baselines NSR is compared against multiple models including (i) seq2seq (Lake and Baroni, 2018), (ii) CNN (Dessi and Baroni, 2019), (iii) Transformer (Csordás al., 2021; Ontanón al., 2022), (iv) equívariant seq2seq (Gordon et al., 2019)-a model that amalgamates convolutional operations with RNNs to attain local equivariance, and (v) NeSS (Chen et al., 2020) a model that integrates a symbolic stack machine into a seq2seq framework.
The summarized results are presented in Tab. 1. Remarkably, both NSR and NeSS realize 100% accuracy on the splits necessitating systematic generalization. In contrast, the peak performance of other models on the LENGTH split barely reaches 20%. This stark discrepancy underscores the pivotal role and efficacy of symbolic components speciffccal.....l........ the symbolic stack machine in NeSS and the GSS NSR- in fostering systematic generalization.
Results
Table 1: Test accuracy across various splits of SCAN and PCFG. The results of NeSS PCFG reported by modifying the source code from Chen et al. (2020) for PCFG.
SCAN
PCPG
models
SIMPLE
JUMP
AROUND RIGHT LENGTH
L.d.l. systematicity productivity
Seq2Seq (Lake and Baroni, 2018)
99.7
1.2
13.8
79
CNN (Dessi and Baroni, 2019)
100.0
69.2
56.7
0.0
85
56
31
Transformer (Csordás et al., 2021)
20.0
96
85
Transformer (Ontamón et ul., 2022)
0.0
19.6
83
63
equivariant Seq2seq (Gordon al., 2019)
100.0
99.1
15.9
NeSS (Chen et al,, 2020)
100.0
100.0
100.0
100.0
R0
=0
=00
NSR (ours)
100.0
100.0
100.0
100.0
100
100
100
While NeSS and NSR both manifest impeccable generalization on SCAN, their foundational princi- ples are distinctly divergent.
1. NeSS necessitates an extensive reservoir of domain-specifee knowledge to meticulously craft the components of the stack machine, encompassing stack operations and category predictors. Without the incorporation of category predictors, the efficacy of NeSS plummets to approximately 20% in out of runs. Contrarily, NSR adopts a modular architecture, minimizing reliance on domain-specific knowledge.
2. The training regimen for NeSS contingent on a manually curated curriculum, coupled with specialized training protocols for latent category predictors. Conversely, NSR is devoid of any prerequisite for a specialized training paradigm.
Fig. 4 clucidates the syntax and semantics assimilated by NSR from the LENGTH split in SCAN. The dependency parser of NSR, exhibiting equivariance as elucidated in Sec. 3.4, delineates distinct permutation equivalent groups syntactically among the input words: {turn, walk, look, run, jump]. {left, right, opposite, around, twice, thrice), and (and, after]. It pivotal note that no prior information regarding these groups is im- parted- they are entirely manifestation of the learning from the training data. This is in stark contrast to the provision of pre-defined equivariant groups (Gordon al., 2019) or the explicit integration of category induction procedure from execution traces (Chen et al., 2020). Within the realm of the learned programs, the program synthesizer of NSR formulates an index space for the target language and discerns the accurate programs to encapsulate the semantics of each source word.
4.2 PCFG
We further assess NSR on the PCFG dataset (Hupkes et al., 2020), a task where the model is trained to predict the output of a string manipulation command. The input sequences in PCFG are synthesized using a probabilistic context-frre grammar, and the corresponding output sequences are formed by recursively executing the string edit operations delineated in the input sequences. The selection of input samples is designed to mirror the statistical attributes of a natural language corpus, including sentence lengths and parse tree depths.
7

---

Published as a conference paper at ICLR 2024
turn
turn: : 0 - []
1 WALK
walk
1.00
walk:
[inc 0J
2 LOOK
look
look: Ø |inc inc 0]
3 RUN
4 JUMP
jump
run
0.75
run: : Ø - [inc inc inc 01
5 5- LTRUN
left
jump 0 - [inc inc inc inc 0J
6 RTURN
right
0.50 left x cons (inc inc inc inc inc 0,x)
opposite
right x - cons (inc inc inc inc inc inc 0,x)
around
0.25
opposite: x + cons(car(x),x)
twice
around x - +++(+x,,
thrice
and
0.00 twice x +(x,x)
after
thrice x - + xx),xxx,,x
turn
walk
look
run
jump
left
right
opposite
around
twice
thrice and after
and: x, + + y)
after : x, + x(,x)
(a) Syntactic similarity amongst input words in NSR.
(b) Programs induced using NSR.
Figure 4: (a) Syntactic similarity amongst input words in NSR trained on the LENGTH split in SCAN. The similarity between word and word is quantified by the percentage of test samples where substituting i with j. vice versa, retains the dependencies as predicted by the dependency parser. (b) Induced programs for input words using NSR. Here, x and y represent the inputs, signifies empty inputs, cons appends an item to the beginning of list, car retrieves the first item of list, and amalgamates two lists.
Evaluation Protocols and Baselines The evaluation conducted across the following splits: (i) ii.d: where samples are randomly allocated for training and testing, (ii) systematicity: this split is designed to specifically assess the model's capability to interpret combinations of functions unseen during training, and (iii) productivity: this split tests the model's generalization to longer sequences. with training samples containing up to 8 functions and test samples having at least 9 functions. NSR is compared against (i) seq2seq (Lake and Baroni, 2018), (ïi) CNN (Dessi and Baroni, 2019), (iii) Transformer (Csordás et al., 2021; Ontanón et al., 2022), and (iv) NeSS (Chen et al., 2020).
Results The results are consolidated in Tab. 1. NSR demonstrates exemplary performance, achieving 100% accuracy across all PCFG splits and surpassing the prior best pest-performing model (Transformer) by 4% the "systematicity" split and by 15% on the "productivity" split. Notably, while NeSS exhibits flawless accuracy on SCAN, it encounters total failure on PCFG. A closer examination of NeSS's training on PCFG reveals that its stack operations cannot represent PCFG's binary functions, and the trace search process is hindered by PCFG's s extensive vocabulary and elongated sequences. Adapting NeSS this context would necessitate substantial domain-specifie modifications and extensive refinements to both the stack machine and the training methodology.
4.3 HINT
We also evaluate NSR HINT eLi al., 2023b), a task where the model predicts the integer result of a handwritten arithmetic expression, such as 3 + ) 40, without any intermediate supervision. HINT is challenging due to the high variance and ambiguity in real handwritten images, the complexity of syntax due to parentheses, and the involvement of recursive functions in seman- tics. The dataset includes one training set and five test subsets, each assessing different aspects of generalization across perception, syntax, and semantics.
Evaluation Protocols and Baselines Adhering the protocols of Li et al. (2023b), we train models on a single training set and evaluate them on five test subsets: (i) "T": expressions seen in training but composed of unseen handwritten images. (ii) "SS": unseen expressions, but their lengths and values are within the training range. (iii) "I.S": expressions are longer than those in training, but their values are within the same range. (iv) "SL." expressions have larger values, and their lengths are the same as training. (v) "LL": expressions are longer, and their values are bigger than those in training. A prediction is deemed correct only if exactly matches the ground truth. We compare NSR against several baselines including seq2seq models like GRU, LSTM, and Transformer as reported by Li et al. (2023b), and NeSS (Chen et al., 2020), with each model utilizing a ResNet- 18 as the image encoder.
Results The results summarized in Tab. 2. NSR surpasses the state-of-ther -frtte-rrtttttttt model, Trans- former, by approximately 23%. The detailed results reveal that this improvement is primarily due to better extrapolation in syntax and semantics, with NSR elevating the accuracy on the "L.I" subset
8

---

Published as a conference paper at ICLR 2024
Table 2: Test accuracy HINT. Results for GRU, LSTM, and Transformer directly cited from Li et al.
(2023b). NeSS results are obtained by adapting its source code to HINt.
Symbol Input
Image Input
Model
SS
L
SL
L.I
Avg.
I
SS
L.
SL.
Avg.
GRU
76.2
69.5
42.8
10.5
15.1
42.5
66.7
58.7
33.1
9.4
12.8
35.9
LSTM
92.9
90.9
74.9
12.1
24.3
58.9
83.9
79.7
62.0
11.2
21.0
51.5
Transformer
98.0
96.8
78.2
11.7
22.4
61.5
88.4
86.0
62.5
10.9
19.0
53.1
NeSS
=0
=0
=0
+0
=00
=00
NSR (ours)
98.0
97.3
83.7
95.9
77.6
90.1
88.5 86.2 67.1 83.2
58.2
76.0
from 19.0% to 58.2%. The gains on the "I" and "SS" subsets are more modest, around 2%. For more detailed insight into NSR's predictions on HINT, refer to Fig. A3. Similar to its performance on PCFG, NeSS fails on HINT, underscoring the challenges discussed See. 4.2.
4.4 COMPOSITIONAL MACHINE TRANSLATION
In order to assess the applicability of NSR to real-world scenarios, we conduct proof-of-concep! experiment on a compositional machine translation task, specifically the English-Frence translation task, described by Lake and Baroni (2018). This task has been benchmark for several studies (Li et al,, 2019; Chen et al., 2020; Kim, 2021) to validate the efficacy of their proposed methods in more realistic and complex domains compared to synthetic tasks like SCAN and PCFG. The complexity and ambiguity of the rules in this translation task are notably higher.
We utilize the publicly available data splits provided by et al. (2019). The training set comprises 10,000 Eiglish-Frendd sentence pairs, with English sentences primarily initiating with phrases like "I am," "you are," and their respective contractions. Uniquely, the training set includes I, 1,000 repetitions of the sentence pair ("I am daxy." "je suis daxiste"). introducing the pseudoword "daxy." The test set, however, explores 8 different combinations of "daxy" with other phrases, such as "you are not daxy." which are absent from the training set.
Results Tab. 3 presents the results of the compositional machine translation task. We compare NSR with Seq2Seq (Lake and Baroni, 2018) and NeSS (Chen et al., 2020). is noteworthy that two distinet French translations for "you are" are prevalent in the training set; hence, both are deemed correct in the test set. NSR, akin to NeSS, attains 100% generalization accuracy this task, demonstrating its potential applicability to real-world tasks characterized by diverse and ambiguous rules.
Table 3: Accuracy on composi- tional machine translation.
Model
Accuracy
Seq2Scq Transformer
12.5
14.4
NeSS
100.0
NSR (ours)
100.0
5 CONCLUSION AND DISCUSSION
We introduced NSR, model capable of learning Grounded Symbol System from data to facilitate systematic generalization. The Grounded Symbol System offers a generalizable and interpretable rep- resentation, allowing principled amalgamation of perception, syntax, and semantics. NSR employs a modular design, incorporating the essential inductive biases of equivariance and compositional- ity in each module to realize compositional generalization. We developed a probabilistic learning framework and introduced a novel doduutiio-abduction algorithm to enable the efficient training of NSR without GSS supervision. NSR has demonstrated superior performance across diverse domains, including semantic parsing, string manipulation, arithmetic reasoning, and compositional machine translation.
Limitations While NSR has shown impeccable accuracy on a conceptual machine translation task, we foresee challenges in its deployment for real-world tasks due to (i) the presence of noisy and abundant concepts, which may enlarge the space of the grounded symbol system and potentially decelerate the training of NSR, and (ii) the deterministic nature the functional programs in NSR, limiting its ability to represent probabilistic semantics inherent in existence of multiple translations for a single sentence. Addressing these challenges remains a subject for future research.
tasks, such as the

---

Published as a conference paper at ICLR 2024
Acknowledgment We thank the anonymous reviewers for their valuable feedback and constructive suggestions. Their insights have contributed significantly to improving the quality and clarity of our work. Additionally, sincerely appreciate the area chairs and program chairs for their efforts in organizing the review process and providing valuable guidance throughout the submission. We would like thank NVIDIA for their generous support of GPUs and hardware. This work is supported in part by the National Science and Technology Major Project (2022ZD01 14900) and the Beijing Nova Program.
REFERENCES
Akyürek, E.,, Akyürek, A. F., and Andreas, J. (2020). Learning to recombine and resample data for compositional generalization. In International Conference Learning Representations (ICLR).
Andreas, (2020). Good-enough compositional data augmentation. In Anmual Meeting of the Association for
Computational Linguistics (ACL).
Bahdanau, D., de Vries, H., O'Donnell, T. J., Murty, S., Beaudoin, P., Bengio, Y., and Courville, A. (2019). Closure: Assessing systematic generalization of clevr models. arXiv preprint arXiv:I912.05788 2
Balog, M., Gaunt, A. L.,, Brackschmidt, M., Nowozin, S., and Tarlow, D. (2017). Deepeoder: Leamingg write
programs. International Conference on Learning Representations (ICLR). 4, A1
Carpenter, T. P. Fennema, E., Franke, M. L., Levi, L., and Empson, S. B. (1999). Children's mathematics. Cognitively Guided. A3
Chen, D. and Manning, D. (2014). A fast and accurate dependency parser using neural networks. In Annual Conference on Empirical Methods Natural Language Processing (EMNLP). 1,
Chen, X., Liang, C., Yu, A. W., Song. D., and Zhou, D. (2020). Compositional generalization via neural-yymbolic stack machines. In Advances in Neural Information Processing Systems (NewrIPS). 1, 3. 6, 7, 8, 9, A7
Chomsky, N. (1957). Syntactic structures. In Syntactic Structures. De Gruyter Mouton.
Chomsky, N. (1965). Aspects of the Theory of Syntax. MIT press.
Csordás, R., Trie, K., Schmidhuber, J. (2021). The devil is in the detail: Simple tricks improve systematic
generalization of transformers. In Annual Conference on Empirical Methods in Natural Language Processing (EMNLP). 1, 2, 7, 8, A7
Dai, B., Wang. L., Jia, B., Zhu, S.-C., Zhang, C., and Zhu, (2023). X-voe: Measuring explanatory violation of expectation in physical events. International Conference on Computer Vision (ICCV). 2
Dessi, R. and Baroni, M. (2019). Cnns found to jump around more skillfully than mns: Compositional generalization in seq2seq convolutional networks. In Annual Meeting of the Association for Computational Linguistics (ACL). 2, A.
Devlin, J.. Uesato, J., Bhupatiraju. S., Singh. R., Mohamed. A.-r,, and Kohli, (2017). Robustfill: Neural program learning under noisy i/o. International Conference on Machine Learning (ICML). 4, A1
Drozdov, A., Schärli, N., Akyürek, E., Scales, N., Song, X., Chen, X., Bousquet, O., and Zhou, D. (2023). Compositional semantic parsing with large language models. ICLR. 1,2
Ellis, K., Ritchie, D., Solar-Lezama, A., and Tenenbaum, (2018a). Learning infer graphics programs from hand-drawn images. Advances Neural Information Processing Systems (NeurIPS).
Ellis, K., Wong, C., Nye. M., Mayeé-Meyer, M., Morales, L.. Hewitt, L., Cary, L., Solar-Lezama, A., and Tenenbaum, J. B. (2021). Dreamcoder: Bootstrapping inductive program synthesis with wake-sleep library learning. In Programming Language Design and Implementation. 1, 4, A1,
Ellis, M., Morales, E., Sablé Sablé-Meyer, M., Solar Lezama, A., and Tenenbaum, (2018b). Library learning for heurally-guidee guided bayesian program induction. In Advances in Neural Information Processing Systems (NeurIPS). Al
Evans, N. and Levinson, S. C. (2009). With diversity in mind: Freeing the language sciences from universal grammar. Behavioral and Brain Sciences, 32(5)472-492.8 3
10

---

Published as a conference paper at ICLR 2024
Fan, L.,, Wang. G., Jiang, Y.. Mandlekar, A.. Yang. Y., Zhu, H., Tang, A.. Huang, D.-A., Zhu, Y., and Anandkumar, A. (2022). Minedojo: Building open-ended embodied agents with interettscaaee knowledge. Advances Neural Information Processing Systems (NeurIPS).
Fodor, J. A. and Lepore, E. (2002). The Compositionality Papers. Oxford University Press. 3
Fodor, J. A., Pylyshyn, Z. W., et al. (1988). Connectionism and cognitive architecture: critical analysis. Cognition, 28(1 2):3-71. 3
Gontier, N., Reddy, S., and Pal, C. (2022). Does entity abstraction help generative transformers reason? TMLR. 2
Gordon, J., Lopez-Paz, D., Baroni, M., and Bouchacourt, D. (2019). Permutation equivariant models for compositional generalization in language. In International Conference Learning Representations (ICLR). 2, A2, A7
Harnad, (1990). The symbol grounding problem. Physica D: Nonlinear Phenomena, 42(1-3):335-346.
Hauser, D., Chomsky, and Fitch, W. (2002). The faculty of language: what it, who has it, and how did it evolve? Science, 29865598)
Herzig, J. and Berant, J. (2021). Span-hased semantic parsing for compositional generalization. ACL. 2
Hinton, G. E. (1984). Distributed representations. Technical Report CMU-CS-84-13 Carnegie Mellon University. 3
Hornik, K., Stinchcombe, M., and White, H. (1989). Multilayer feedforward networks are universal approxima- tors. Neural networks, 2(5):359 366.-366.61 A2
Hupkes, D., Dankers, V., Mul. M., and Bruni, E. (2020). Compositionality decomposed: how do neural networks generalise? Journal of Artificial Intelligence Research (JAIR), 67:757-795. 1, 6.
Jiang, G., Xu, M., Xin, S., Liang, W., Peng, Zhang, C., and Zhu, Y. (2023). Mewl: Few-shot multimodal word learning with referential uncertainty. In International Conference on Machine Learning (ICML). 1,2
Keysers, D., Schärli, N., Scales, N., Buisman, H., Furrer, D., Kashubin, S., Momchev, N., Sinopalnikov. D.. Stafiniak, L.,, Tihon, T., et al. (2020). Mcasuring compositional generalization: A comprehensive method on realistic data. In International Conference Learning Representations (ICLR). 1,2
Kim, N. and Linzen, T. (2020). Cogs: A compositional generalization challenge based on semantic interpretation. In Annual Conference on Empirical Methods in Natural Language Processing (EMNLP). 2
Kim, Y. (2021). Sequense-to--eqquenee learning with latent neural grammars. In Advances Neural Information Processing Systems (NeurIPS).
Kingma, D. and Ba, (2015). Adam: A method for stochastic optimization. International Conference on Learning Representations (ICLR). A3
Kulkami, T. D., Kohli, P., Tenenbaum, J. B., and Mansinghka, V. (2015). Picture: A probabilistic programming language for scene perception. In Conference Computer Vision and Puttern Recognition (CVPR). Al
Lake, B. M. (2019). Compositional generalization through meta sequence-to--sqquence learning. In Advances in Neural Information Processing Systems (NeurIPS). 6
Lake, B. M. and Baroni, M. (2018). Generalization without systematicity: On the compositional skills of recurrent networks. International Conference Machine Learning (ICML). 1.
7, 8, A7
Lake, B. M. and Baroni, M. (2023). Human-like systematic generalization through a meta- meta-learning neural network. Nature, 155
Lake, B. M., Salakhutdinov, R., and Tenenhaum, J. B. (2015). Human-level concept learning through probabilistic program induction. Science, 133--36) A1
Lake, B. M., Ullman, T. D., Tenenbaum, J. B., and Gershman, S. (2017). Building machines that learn and think like people. Behavioral and Brain Sciences, 40.
I Launchbury, (2017). darpa perspective on artificial intelligence, Retrieved November, 11 11:2019.

---

Published as a conference paper at ICLR 2024
Li, P., Liu, Li, Y., Zhu, Y., Yang. Y., and Huang, S. (2023a). Gendexgrasp: Generalizable dexterous grasping. In International Conference on Robotics and Automation (ICRA).
Li. Q. Huang. S., Hong. Y., Chen, Y., Wu, Y. N., and Zhu, S.-C. (2020). Closed loop neural-symbolic learning integrating neural perception, grammar parsing, and symbolic reasoning. In International Conference on Machine Learning (ICML). 5
Li, Q-. Huang. S., Hong, Y., Zhu, Y., Wu, N. and Zhu, S.-C. (2023b). A minimalist dataset for systematic generalization of perception, syntax, and semanties. In ICLR. 2, 6, 8, A7
Li, S., Wu, K.., Zhang, C., and Zhu, Y. (2022). On the learning mechanisms in physical reasoning. In Advances in Neural Information Processing Systems (NeurIPS).
Li S., Wu, K., Zhang, C., and Zhu, Y. (2024a). 1-phyre: Interactive physical reasoning. In International Conference on Learning Representations (ICLR).
Li, Y., Liu, B., Li, Yang, Y., Zhu, Y., Liu, T., and Huang, (2024b). Grasp multiple objects with hand. IEEE Robotics and Automation Letters (RA-L).
Li, Y., Zhao, L., Wang, J., and Hestness, (2019). Compositional generalization for primitive substitutions. In Annual Conference on Empirical Methods Natural Language Processing (EMNLP).
Liang. C., Norouzi, M., Berant, J., Le. Q V., and Lao, N. (2018). Memory augmented policy optimization for program synthesis and semantic parsing. In Advances Neural Information Processing Systems (NeurIPS).
Liu, Q. An, S., Lou, J.-G., Chen, B., Lin, Z., Gao, Y., Zhou, B., Zheng, N., and Zhang, D. (2020), Compositional generalization by learning analytical expressions. In Advances Neural Information Processing Systems (NeurIPS). 3,6
Lu, Z., Pu, H., Wang, F., Hu, Z., and Wang, L. (2017). The expressive power of neural networks: A view from width. Advances in nearal information processing systems, 30.
Mao, J.. Gan, C.. Kohli, P., Tenenbaum, J. B., and Wu, J. (2018). The neuro-symbolic concept learner: Interpreting scenes, words, and sentences from natural supervision. International Conference on Learning Representations (ICLR).
Marcus, G. F. (2018). The algebraic mind: Integrating comnectionism and cognitive science. MIT press. 1,
Minervini, P., Bošnjak, M., Rocktäschel, T., Riedel, S., and Grefenstette, (2020). Differentiable reasoning on large knowledge bases and natural language. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pages 5182-5190.
Montague, R. (1970). Universal grammar. Theoria, 36(3):373-398.
Newell, A. (1980). Physical symbol systems. Cognitive science, 4(2):135 183.
Nye, M., Solar-T -zamma A., Tenenbaum, J., and Lake, B. M. (2020). Learning compositional rules via neural program synthesis. In Advances in Neural Information Processing Systems (NeurlPS). 3
Ontanón, S., Ainslie, J., Cvicek, V., and Fisher, Z. (2022). Making transformers solve compositional tasks. In Annual Meeting of the Association for Computational Linguistics (ACL). 1, 7, A7
Peano, G. (1889). Arithmetices principia: Nova methodo exposita. Fratres Bocca. 4
Peyton Jones, S. (1987). The implementation of functional programming languages. Prentice-Hall, Inc.
Rocktäschel, T. and Riedel, (2017). End-to-end differentiable proving. Advances in neural information procexsing systems, 30.
Ruis, L., Andreas, Baroni, M.. Bouchacourt, D., and Lake, B. M. (2020). A benchmark for systematic generalization grounded language understanding. Advances Neural Information Processing Systems (NeurIPS). 2
Russin, J., J. O'Reilly, and Bengio, (2019). Compositional generalization a deep seq2seq model by separating syntax and semantics. arXiv preprint arXiv: 1904.999000 2
Saxton, D., Grefenstette, E., Hill, F. and Kohli, (2018), Analysing mathematical reasoning abilities of neural models. In International Conference on Learning Representations (ICLR). 2
Solomonoff, J. (1964), formal theory of inductive inference. part Information and control, 7(1):1222. Al
12

---

Published as a conference paper at ICLR 2024
Van Gansbeke, W., Vandenhende, S.. Georgoulis. S., Proesmans, M., and Van Gool, L. (2020). Scan: Learning classify images without labels. European Conference on Computer Vision (ECCV). A2
Wang, Q. Zhang, H.. Deng, C., You, Y., Dong. H., Zhu, Y., and Guibas, L. (2024). Sparsedff:: Sparse view feature distillation one-shot dexterous manipulation. International Conference on Learning Representations (ICIR).
Williams, (1992). Simple statistical gradient-followin algorithms for connectionist reinforeement learning. Machine Learning, 8(3-4):229 256. 5
Xie, S., Ma, X., Yu. P.. Zhu, Y., Wu, N., Zhu, S.-C. (2021). Halma: Humanlike abstraction learning meets affordance in rapid problem solving. arXiv preprint arXiv:2102.11344 1, 2, 4,
M.. Jiang, G., Liang. Zhang, C., and Zhu, Y. (2023). Active reasoning in an open-worte environment. In Advances Neural Information Processing Systems (NeurIPS).
Zhang, C., Xie, S., Jia, B., Wu, N., Zhu, S.-C., and Zhu, (2022). Learning algebraic representation for systematic generalization in abstract reasoning. In European Conference on Computer Vision (ECCV), 6, A2
13

---

Published as a conference paper at ICLR 2024
A MODEL DETAILS
Dependency Parsing Fig. Al illustrate the process of parsing arithmetic expression via the dependency parser. Formally, a state e {ar, B, A) in the dependency parser consists of a stack a, a buffer 3. and set of dependency arcs A. The initial state for a sequence = Ø. A state is regarded as terminal if the buffer is empty and
WoW1...Wn is
a = [Root]. 3 [wgWW,..Wp)] the stack only contains the node Root. The parse tree can be derived from the dependency arcs A. Let 0; denote the i-th top element on the stack, and 3 the i-th element on the buffer. The parser defines three types of transitions between states:
LEFT-ARC: add an are a; - 22 to A and remove a from the stack a. Precondition: |a] > 2.
RIGHT-ARC: add an 02 an A and remove on from the stack a. Precondition: |[]| > 2.
SHIFT: move 31 from the buffer 3 to the stack a. Precondition: |8] > 1.
The goal of the parser is predict transition sequence from initial state terminal state. The parser predicts one transition from T = [LEFT-ARC, RIGHTT-RRC SHIFT} at time, based on the current state c (a, A). The state representation is constructed from local window and contains following three elements: (i) The top three words on the stack and buffer: ag, B, i 1, 2, 3: (ii) The first and second leftmost/rightmostt children of the top two words on the stack: le, (a;). rc₁ (a;), (c2(s)), re2(() ro2(a,), i = 1, 2: (iii) The leftmost of leftmost/righmosst of rightmost children of the top two words on the stack: leq (le: (ax)), rei (rc) (a:)). (rc()))))))
1,2. We use special Null 1 token for non-existent elements. Each element in the state representation is embedded to d-dimensional vector E Rd and the full embedding matrix is denoted as E E R|E) where is the concept space. The embedding vectors for all elements in the state are concatenated as its representation: [ei e2...n.] E Rnd Given the state representation, we adopt a two-layer feed-forward neural network to predict the transition.
Program Induction Program induction, i.e,, synthesizing programs from input-output examples, was one of the oldest thcoretical frameworks for concept learning within artificial intelligence (Solomonoff, 1964). Recent advances in program induction focus on training neural networks to guide the program search (Kulkarni et al., 2015; Lake et al., 2015; Balog et al., 2017; Devlin et al., 2017; Ellis et al., 201 Sa;b). For example, Balog et al. (2017) train neural network to predict properties of the program that generated the outputs from the given inputs and then use the neural network's predictions to augment search techniques from the programming languages community. Ellis et al. (2021) released a neural-guided program induction system, DreamCoder, which can efficiently discover interpretable, reusable, and generalizable programs across wide range of domains, including both classic inductive programming tasks and creative tasks such as drawing pictures and building scenes. DreamCoder adopts "wake-sleep" Bayesian learning algorithm to extend program space with new symbolic abstractions and train the neural network on imagined and replayed problems.
To learn the semantics of a symbol from a set of examples D. is to find program Pa. composed from a set of primitives L, which maximizes the following objective:
maxp(plDe.L)) a p(Delp) p(olL),
(AI)
where p(Delp) is the likelihood of the program p matching De. and p(p] is the prior of p under the program space defined by the primitives L. Since finding globally optimal program is usually intractable, the maximization in Eq. (A1) is approximated by stochastic search process guided by a neural network, which is trained approximate the posterior distribution p(pl De, L). We refer the readers to DreamCoder (Ellis et al., 2021)' for more technical details.
httpp::///ithhbb.cmm//111
thub.
A1

---

Published as a conference paper at ICLR 2024
B LEARNING
Derivation of Eq. (5)
Take the derivative of w.r.t. 0g-
Va, ((,,)) Vo, logp(ul>) p(ulx)
Vo,p(ula)
32 V o, logp(s/<x;0p) T TT. ,y
(A2)
= -ET~p(T|>.a)) (.))) Ve, logp(s|2; 6p)].
Similarly, for 02 02 we have
Vo, L(, v) ET -TT Ve, logp(e|s;0..] Va L(,,)) [ -pT 2. Vo, log (eyllsse e;),
(A3)
Deduetion-Abbuuction Alg. A1 describes the procedure for learning NSR by the proposed deduction-abduuction algorithm. Fig. illustrates the one-step abduction over perception, syntax, and semantics in HINT and Fig. A2 visualizes a concrete example to illustrate the deduction-abduucion process. It similar for SCAN and PCFG.
C EXPRESSIVENESS AND GENERALIZATION OF NSR
Expressiveness
Lemma C.1. Given a finite unique set of {ar i O,... N}, there exists a sufficiently capable neural network fp such that: Vz*, fp((+) =
This lemma asserts the existence of neural network capable of mapping every element in a finite set to unique index, i.e., x² - 1, as supported by (Hornik et al., 1989; Lu al., 2017). The parsing process in this scenario is straightforward, given that every input is mapped singular token. Lemma C.2. Any index space can be constructed from the primitives (0, inc).
This lemma is grounded the fact that all indices are natural numbers, which can be recursively defined by {o, inc), allowing the creation of indices for both inputs and outputs.
Generalization Equivariance and compositionality are formalized utilizing group theory. following the approaches of Gordon et al. (2019) and Zhang et al. (2022). A discrete group & comprises elements (91.... Digh } and a binary group operation "." adhering to group axioms (closure, associativity, identity, and invertibility). Equivariance associated with a permutation group P, representing permutations of a set X. For compositionality, composition operation is considered, defining To: (x:(X XX X.
The three modules of NSR- -ee--ll perception (Eq. (1)), dependency parsing (Eq. (2)), and program induction (Eq. (3)) exh)-ithibi equivariance and compositionality, functioning as pointwise transforma- tions based on their formulations. Eqs. (1) to (3) demonstrate that in all three modules of the NSR system, the joint distribution factorized into product of several independent terms. This factoriza- tion process makes the modules naturally adhere to the principles of equivariance and recursiveness, as outlined Definitions 3.1 and 3.2.
D EXPERIMENTS
D.1 EXPERIMENTAL SETUP
For tasks taking symbols as input (i.e., SCAN and PCFG), the perception module is not required in NSR; For the task taking images as input, we adopt ResNet-15 18 as the perception module, which is pre- pre-trained unsupervisedly (Van Gansbeke et al., 2020) handwritten images from the training set. In the dependency parser, the token embeddings have a dimension 50, the hidden dimension of the transition classifier is 200, and we dropout of 0.5. For the program induction, adopt the
A2

---

Published as a conference paper at ICLR 2024
default setting in DreamCoder (Ellis et al., 2021). For learning NSR, both the ResNet-18 and the dependency parser are trained by the Adam optimizer (Kingma and Ba, 2015) with learning rate of 10 4. NSR trained for 100 epochs for all datasets.
Compute All training can done using a single NVIDIA GeForce RTX 3090Ti under 24 hours.
D.2 ABLATION STUDY
To explore how well the individual modules of NSR are learned, we perform an ablation study on HINT to analyze the performance of each module of NSR. Specifically, along with the final results, the HINT dataset also provides the symbolic sequences and parse trees for evaluation. For Neural Perception, we report the accuracy of classifying each symbol. For Dependency parsing, we report the accuracy of attaching each symbol to its correct parent, given the ground-truth symbol sequence as the input. For Program Induction, we report the accuracy of the final results, given the ground-truth symbol sequence and parse tree.
Overall, each module achieves high accuracy, shown in Tab. Al. For Neural Perception, most errors come from the two parentheses, "(" and "y", because they are visually similar. For Dependency Parsing, analyze the parsing accuracies for different concept groups: digits (100%), operators (95.85%), and parentheses (64.28% The parsing accuracy of parentheses is much lower than those of digits and operators. We think this is because, long digits and operators are correctly parsed in the parsing tree, where to attach the parentheses does not influence the final results because parentheses have semantic meaning. For Program Induction, can manually verify that the induced programs (Fig. 4) have correct semantics. The eπrоrs are caused by exceeding the recursion limit when calling the program for multiplication. The above analysis also verified by the qualitative examples in Fig. A3.
D.3 QUALITATIVE EXAMPLES
Figs. A3 and A4 show several examples of the NSR predictions on SCAN and HINT.
Fig. AS illustrates the evolution of semantics along the training of NSR in HINT. This pattern is highly in accordance with how children learn arithmetic in developmental psychology (Carpenter al., 1999): The model first masters the semantics of digits counting, then learns and as recursive counting, and finally figures out how to define x and + based on + and - Crucially, x and + are impossible be correctly learned before mastering and The model is endowed with such an incremental learning capability since the program induction module allows the semantics of concepts be built compositionally from those learned earlier (Ellis et al., 2021).
A3

---

Published as a conference paper at ICLR 2024
ID
Stack Buffer
Transition
Dependency
Start: o= [ROOT], B Wy, .. Wn, A=
0
3
4
Shift
Shift
o,w,lB. + olw, B,
2. Lect-Arc,
alw; B. A + alw, B, AU(r(m,w)
1
3
4 4 2
Shift
Right-Arc,
alw/ww, B. a/w, AUtr(m,w))
2
3
4 2
Left-Are
3 -
Finish: [w], Ø
3
+ 4 2
Shift
4x2
4
+ + 2
Shift
+
5
+ +
Left-Arc
+X
6
+
Shift
3
7
+X2
Right-Are
2
8
Right-Are
+-X
4
2
Figure Al: Applying the transition-basse dependency parser to an example of HINT. It is similar for SCAN and PCFG.
Deduction
11 21 P1
3+9
4
944
22275 Ps
Prionit Queue
Prionity
Priority Queue
Priority Queue
11 [a,, 221).
18, X X (Myy 4.)).18
( 04
C 99.0), 9.p
C-F- 21 (eg, 21.
x 18 (4g.0,)) 18.
9.
Pop
13.Ps
[dx, 1), 16,
(3 (3.33)).13 13,pp
++++ 21 (.))).22ppp
Pop
Abduction
4
11
21
X x 8 18 Pa
Pop
d)), 13.
3
33
P3
8
449 P4
Path
Pop
P4
Ps
Abduce peresption: None Abduce guiar: None Abduce semontics::
Abduce perception: Nane
Abdure porception: ( 999)). 9,pi Abolure suetar: Nore somuntter: ( i (9.)). 9.
Abslce syntar: Nome
( 9990)...
Abduce vomonticr:
1. (a,, a,)). pf
(a,, a,)), 18,
Top-doos veurcl:
Top-down seurch:
2 0),
( 0),
[ x (8 18.p,
Figure A2: illustration the deduaction-adduction process for an example of HINT. Given handwritten expression, the system performs a greedy deducciin to propose an initial solution, generating a wrong result. In abduction, the root node, paired with the ground-truth result, is first pushed to the priority queue. The abduction over perception, syntax, and semantics is performed top-down search also applied to propagate the expected value its children. All possible revisions are then pushed into the priority queue. This process is repeated until we find the most likely revision for the initial solution.
the popped node generate possible revisions.
A4

---

Published as a conference paper at ICLR 2024
Test subset
01-00-9933-11 1
8
/ +2))
00
22
35
(hone
77
Jore
Test subset SS
0T.371444000099399 PD. 31440066006))000000-
(3--
X (4-0+ (0X6 3/1-61
12
Test subset SL
GT: 9-808))1--08---- 457 PD: 91008871-08-499 457
GT. 1117776640022777 2464 63 0y278)77
(3x 22 X
(Roee
Meee
Test subset LS
GT. CES.://w............000000000000
Test subset LL
GT. 10..997..90222000000000000000000
PD: -
Figure A3; Examples of NSR predictions on the test set of HINT, "GT" and "PD" denote gground-truthi and "prediction." respectively. Each node in the tree is a tuple of (symbol, value).
A5

---

Published as a conference paper at ICLR 2024
ran around lajt twies and run around right and 11 [LTURN, RUN) 8 (RTURN, RUN] 4
wafk opposite right thrice after look around lift twice efter 12 ILTURN. LOOK] "8 IRTURN, RTURN, WALK]
3
brice [LTURN, RUN]
arcumi IRTURN, RUNJ
thrice IRTURN, RTURN, WALK] 3
twice [LTURN, LOOK] 8
areumd [LTURN,RUN]*
right (RTURN, RUN] run [RUN)
oppesite IRTURN, RTURN, WALK]
around 8 ILTURN, LOOK] 4
$ lift 5 [LTURN, LOOK]
lift (LTURN, RUN]
righe (RTURN, WALK]
non [RUN]
walli [WALK]
laok 2 [LOOK]
Figure A4: Examples of NSR predictions on the test set of the SCAN LENGTH split. We use (repeating the list) and (concatenating two lists) to shorten the outputs for easier interpretation.
master counting
master + and
master X and +
Training epochs
O: Null
0:
0:
0:0
1: Null
inc
I:inc
i:inc
2: Null
inc
inc inc
inc inc
Null
inc
+: Null
+: Null
+: (y 0, +(ine y))
+: (y = (ine x) (doe y))
-1 Null
Null
-: if 0,X, (doc x. dec y))
-: (y x. (doc x) (dee
Null
Null
(y x.
x: (x
(dec x)
+: Null
Null
+:if(y inc 02 if O, inc inc 0))
+: (x 0, inc ((x >) +1))
Figure A5: The evolution of learned programs in NSR for HINT, The recursive programs DreamCoder represented by lambda calculus (a.k.a. X-calculus) with Y-combinator. Here, we translate the induced programs into pseudo code for easier interpretation. Note that there might be different yet functionally-equivaal programs to represent the semantics of a symbol; we only visualize a plausible one here.
A6

---

Published as a conference paper at ICLR 2024
Table Al: Accuracy the individual modules NSR on HINT dataset.
Module
Neural Perception
Dependency Parsing
Program Induction
Accuracy
93.51
88.10
98.47
Table A2: The test accuracy on different splits of SCAN and PCFG. The results of NeSS on PCFG are reported by adapting the source code from Chen al. (2020) PCFG. Reported accuracy (%) the average of runs with standard deviation if available.
SCAN
PCFG
SIMPLE
JUMP
AROUND RIGHT
LENGTH
Lid.
systematicity productivity
Seq2Seq (Lake and Baroni, 2018)
99.7
1.2
25
13.8
79
53
30
CNN (Dess) and Baroni, 2019)
100.0:0.0
69.2+8.2
56.7
0.0+0.0
85
56
Transformer (Csordás et al., 202()
20.0
96+t I
85=1
Transformer (Ontanón
2022)
0.0
83
equivariant Seu2seq (Gordon et al., 2019)
100.0
99.1
92.010.24
15.913.2
NeSS (Chen al., 2020)
100.0
100.0
100.0
100.0
=:0
NSR (ours)
100.0.0.00
100.010.0
100.010.00
100.010.0
100.0
100.10
100
Table A3: The test accuracy on HINT. We directly cite the results of GRU, LSTM, and Transformer from Li al. (2023b). The results of NeSS are reported by adapting its souree code HINT. Reported accuracy (%) is the median and standard deviation of runs.
Model
Symbol Input
Image Input
88
LS
SL.
L.L
Avg.
LS
SL
L.L.
Arg.
GRU
76.2:006
60.5:006
42.8
10.500.2
15.121.2
4255007
667:220
78.1
33.1127
941003
128110
15.911
1STM
92.92144
9..92111
9..921
12.120.2
24320.3
38920.7
85.9209
797108
62012.5
1122001
21.0108
$1.51:0
Transformer
98.0-03
96.5:0.6
78.2
11.--03
22.45.1
61::09
884:13
86001:3
62514.1
109102
190010
53.11:16
Ne58
<0
<0
+0
<0
VSR (ours)
98.0=0.2
97.3:0.5
83.7:12
95.9-46
77.633.1
90.127
8855:100
67.1424
RA2639
5K2433
76.0226
A7

---

Published as a conference paper at ICLR 2024
Algorithm A1: Learning by Deduction-Abduuction
Input :Training set D (Ii. B+) : 1, ...,
Output _,0") .
Initial Module: perception 0 syntax 0 semantics (())
for - 0 to ' do
Buffer B - Ø
foreach (I,, v) E D do
T - DEDUCE(#, 0g ((4) .0())
T - ABDUCE(T, y)
B B But
0f++11 0 ((++1) learn(B, "0",000 00000"0000 (
return
0 _ ((T))
10
11
Function DEDUCE (æ. 0p. On. 02):
12
Sample pl 0p). ê p(e)8:0.),6 ((),6;0))
return T = (a,
14
15
Funetion ABDUCE (T' y):
16
- PrriorityQuuue()
Q-push(root(T), y, 1.0) while Q is not empty do
18
19
A, UA, (-pop()
20
A - (x, w. v. ares)
if A. Ч4 then
23
return ((A)
1/ Abduce perception foreach w' E E do
23
24
A' - A(w(w w')
if A' VA then Q.push(A UA. P(A'))
26
// Abduce syntax foreach are arcs do A' - rotate(A A, are) A'v Y then Q.push(AA, NA p(A)))
27
28
30
// Abducc semanties 31
A' - AAv yA)
32
Q.push(A', (',,A,,(('')) 1/ Top-down search
foreach B children(A) A) do
yB Solve (3, A, y (A.ww)
Q.push( yB. BB. (B)
A8


Reviews:
[{"review_id": "uSE9iS2ZdH", "reviewer": "Reviewer_ih16", "summary": "This paper introduces the Neural-Symbolic Recursive Machine (NSR), a model for systematic generalization in sequence-to-sequence tasks. The key innovation is representing the problem as a Grounded Symbol System (GSS) with combinatorial syntax and semantics that emerge from training data. The NSR incorporates neural modules for perception, parsing, and reasoning that are jointly trained via a deduction-abduction algorithm. Through architectural biases like recursiveness and equivariance, the NSR achieves strong systematic generalization on tasks including semantic parsing, string manipulation, arithmetic reasoning, and compositional machine translation.\n\nOverall, the paper presents a novel neural-symbolic architecture that combines beneficial inductive biases from both neural networks and symbolic systems to achieve human-like generalization and transfer learning abilities. The experiments demonstrate strengths on challenging benchmarks designed to test systematic generalization.", "questions": "N/A", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "- Compositional generalization is an interesting and important direction to explore, which should be one of the most important capabilities of human. Therefore, the problem and the research direction is important.\n- The Neural-Symbolic Recursive Machine (NSR) model is a novel model architecture centered around representing problems as grounded symbol systems. The deduction-abduction training procedure for coordinating the modules is an original contribution for jointly learning representations and programs.\n- The paper clearly explains the limitations of existing methods, the need for systematic generalization, and how the NSR model aims to address this. The model description and learning algorithm are well-explained. The experiments and analyses effectively demonstrate the claims.\n- The paper is technically strong, with rigorous definitions and detailed exposition of the model components and learning algorithm.\n- The experiments systematically test generalization across four datasets with carefully designed splits. The analyses provide insights into when and why the NSR architecture generalizes better than baselines.\n\nOverall, this is a technically strong and well-written paper that makes both conceptual and practical contributions towards an important research direction.", "weaknesses": "Although I understand that compositional generalization is currently driven primarily by synthetic datasets like SCAN, I would still like to see the application of this method in real-world scenarios. For example, could it achieve significantly better generalization performance compared to conventional seq2seq models on real machine translation tasks?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9BBUjNynqr", "reviewer": "Reviewer_brEA", "summary": "This paper describes a new neurosymbolic model, NSR, which consists of (1) a task-dependent model mapping from inputs to strings; (2) the Chen-Manning dependency parser; (3) a program induction module that is somehow based on DreamCoder. This pipeline is trained by gradient-based optimization (SGD?) using Metropolis-Hastings sampling to estimate the gradient. The proposed method performs well across four tasks, SCAN, PCFG, and HINT, and an artificial machine translation task.", "questions": "Section 3.3: How do you use the gradients? Is this SGD?\n\nWhy is abduction called that? It seems different from abductive reasoning?\n\nDef 3.2: Isn't \"compositionality\" a more usual word for this? \"Recursive\" has a totally different meaning in theory of computation.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "This is a very interesting approach that achieves very good results on the four tasks tested. In every setting, their model either does the best, or is tied with NeSS because both models achieve 100% accuracy.", "weaknesses": "Many statements are made like, \"This stark discrepancy underscores the pivotal role and efficacy of symbolic components—specifically, the symbolic stack machine in NeSS and the GSS in NSR—in fostering systematic generalization.\" But, for an outsider, no explanation is given for why the symbolic components actually lead to better generalization. I would like to see some more explanation or analysis to back this up.\n\nThe program induction module is not described in detail; in equation (3), what is the p in the right-hand side? When you say that you \"leverage\" DreamCoder, do you mean that this module simply is DreamCoder?\n\nFigure 3: image is wrong?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8oBPozDLec", "reviewer": "Reviewer_Gi7u", "summary": "This paper presents a neuro-symbolic architecture called the NSR which consists of 3 steps:\n1. perception module to convert raw input into symbols\n2. a parser to compute a syntax tree over symbols\n3. a program induction module to convert this syntax over induced symbols into a program which can then convert an input into an output deterministically.\n\nEach of these components are separate probabilistic modules (though details about what these models are exactly is unclear from the paper). From results on 3 tasks, we see improvements on generalization compared to neural models.", "questions": "Here are some details I could not get from Section-3:\n\n- What exactly are the symbols in T for each of the datasets? \n- Is every raw input mapped to a single symbol or is there a consolidation step where multiple raw inputs can be associated with the same symbol? \n- What models are used to parameterize all of the distributions in Eq~4? Are these neural networks?\n- What is the overall parameter count?\n- How does inference work for this model?\n- How does this compare to other neuro-symbolic systems, for example \"Neuro-Symbolic Concept Learner\" from Mao et al. 2019?", "limitations": "", "rating": 3, "confidence": 3, "soundness": 1, "presentation": 1, "contribution": 2, "strengths": "The subject matter of the paper is to make progress towards improving compositional generalization in learnt models, which is a very important area.", "weaknesses": "*Presentation is unclear*: There are very few details about the actual approach in the Section-3 (and Figure-1) to fully understand what exactly the model is (See questions). Unfortunately, because there is a lack of details around the approach, it is hard to do a thorough assessment of this work, and I request the authors to revise their draft.\n\nMoreover, the paper spends too much time (and math notation) on simple definitions such as “equivariance” and “recursiveness” and on flagposting “hypothesis” statements. Not necessarily cause for rejection, but I highly suggest that these be moved into an appendix, so more time is spent on explaining the approach.\n\n\n\n*How general is this approach*: Most of the experiments here are on datasets where symbolic approaches are likely to help, but it is unclear how well this approach would do for natural language semantic parsing tasks such as GeoQuery. I'm not fully opposed to having experiments that are only on these programmatic datasets, but it would be good to have an extended discussion on what the symbols and programs look like for more natural data distributions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "uD8wqBXx6p", "reviewer": "Reviewer_WJqb", "summary": "This work introduces a Neuro-symbolic approach capable of strong systematic generalization: NeuralSymbolic Recursive Machines (NSR).\nThe method is made of 3 modules:\n1. a neural net perception module mapping raw input to grounded symbols. This can be a pre-trained CNN or transformer for Images and Text.\n2. a dependency parser to infer dependencies between grounded symbols in a structured syntax tree, termed Grounded Symbol System (GSS)\n3. a program synthesizer that deduces semantic meanings to a given symbol based on its neighborhood in the GSS tree.\n\nTo train this system with simple input-output (x, y) pairs and without any external expert knowledge or supervision for the GSS, the authors introduced a probabilistic learning method based on deduction-abduction: start with a greedy decoded and incorrect GSS tree, then refine step by step by looking at the potential neighbouring trees, until accurate results are obtained.\nMonte-Carlo sampling is done to sample potential trees.\n\nThe method is tested on three synthetic tasks (SCAN, PCFG, Hint) and a compositional machine translation task. In SCAN, PCFG, and compositional machine translation, NSR obtains 100% accuracy. On Hint, NSR beats all baselines including vanilla Transformers.", "questions": "- see \"weakness (2)\": Could the method settle on an \"almost correct\" syntactic tree to save time? and what would the effect of that be on performance?\n\n- What is the vocabulary size of the primitives considered? Did you try more complex sets of logical primitives? What do you think the effect would be on time and performance?\n\n- Do you have any hints of how to start thinking about representing probabilistic semantics like mentioned in the Limitation section?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper proposes a method that unifies the connectionism and the symbolism views of AI. While the attempt has been made multiple times in the past, the proposed method seems original and novel, although additional references could be cited (see the minor suggestions in the Weaknesses section)\n\nThe proposed method is well presented and the paper is easy to read. Figures 3 and 4 in particular made the content of the paper easier to understand and helped gain an intuition on what the method learns.\nExperiments clearly present the strength of the proposed approach over previous baselines.\n\nEventually, this paper addresses an important challenge of current neural architectures: systematic generalization, making this work significant.", "weaknesses": "1. All results are comparing the proposed method NSR with various neural architectures and only one neuro-symbolic method: NeSS. The fact that NeSS performs 0% in 2 tasks and 100% in the other two makes it a weak comparing point (and also suggests that NeSS behaves more like a symbolic model than a neuro-symbolic one: it's all or nothing in terms of performance). I would suggest the authors provide at least 1 other neuro-symbolic method to compare against to make the results more significant. It is very clear that the proposed method outperforms vanilla neural methods such as Transformers, which is not surprising given the nature of the tasks being used, but it is less clear if the proposed method is significantly better than previous neuro-symbolic methods that also do not require additional training signal. The work from Minervini et. al. on Greedy Theorem Provers, or other variants could potentially be used as a baseline for some of these tasks.\n\n2. Another weakness of this paper is the ambiguous explanation of how the search for a GSS tree is terminated. Section 1 states that the search for a tree runs \"_until the accurate result is obtained_\", and Section 3.2 doesn't detail this point (or at least not very well). The authors should better define this stop criterion in order to better understand its limitation: what does it mean for the resulting tree to be \"accurate\"? Could the method settle on an \"almost correct\" syntactic tree to save time? and what would the effect of that be on performance?\n\n3. Eventually, at the end of Section 3, the authors state that the three modules of NSR exhibit equivariance and recursiveness. It would be beneficial to explain why this claim is true and provide additional evidence about it.\n\nThe following are minor suggestions:\n\n4.  In Table 3, for the task of compositional translation, it would be interesting to also evaluate the performance of a vanilla transformer like in the previous tables.\n\n5. the work could benefit from a discussion about previous neuro-symbolic works such as Neural Theorem Provers (NTPs) and Greedy NTPs: \"_Differentiable Reasoning on Large Knowledge Bases and Natural Language_\" by Minervini et. al, and previous work trying to add inductive biases to Transformers such as \"_Does Entity Abstraction Help Generative Transformers Reason?_\" by Gontier et. al.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)