Compositional Generalization Across Distributional Shifts with Sparse Tree Operations
Authors: Paul Soulos
Henry Conklin
Mattia Opper
Paul Smolensky
Jianfeng Gao
Roland Fernandez
Venue: NeurIPS 2024 spotlight (2024)
Keywords: compositionality
compositional generalization
systematicity
neurosymbolic
differentiable computing
vector symbolic
VSA
trees
Primary area: neuroscience_and_cognitive_science
TL;DR: We introduce a unified neurosymbolic architecture with compositional generalization across a variety of distributional shifts and datasets.

Abstract: Neural networks continue to struggle with compositional generalization, and this issue is exacerbated by a lack of massive pre-training. One successful approach for developing neural systems which exhibit human-like compositional generalization is $\textit{hybrid}$ neurosymbolic techniques. However, these techniques run into the core issues that plague symbolic approaches to AI: scalability and flexibility. The reason for this failure is that at their core, hybrid neurosymbolic models perform symbolic computation and relegate the scalable and flexible neural computation to parameterizing a symbolic system. We investigate a $\textit{unified}$ neurosymbolic system where transformations in the network can be interpreted simultaneously as both symbolic and neural computation. We extend a unified neurosymbolic architecture called the Differentiable Tree Machine in two central ways. First, we significantly increase the model’s efficiency through the use of sparse vector representations of symbolic structures. Second, we enable its application beyond the restricted set of tree2tree problems to the more general class of seq2seq problems. The improved model retains its prior generalization capabilities and, since there is a fully neural path through the network, avoids the pitfalls of other neurosymbolic techniques that elevate symbolic computation over neural computation.

Compositional Generalization Across Distributional Shifts with Sparse Tree Operations
Paul Soulos*
Henry Conklin University of Edinburgh
Mattia Opper* University of Edinburgh
Johns Hopkins University psoulos1@jh. edu
Paul Smolensky
Jianfeng Gao Microsoft Research
Roland Fernandez Microsoft Research
Johns Hopkins University and Microsoft Research
Abstract
Neural networks continue to struggle with compositional generalization, and this issue is exacerbated by lack of massive pre-training. One successful approach for developing neural systems which exhibit human-like compositional generalization is hybrid neurosymbolic techniques. However, these techniques run into the core issues that plague symbolic approaches to AI: scalability and flexibility. The reason for this failure is that their core, hybrid neurosymbolic models perform symbolic computation and relegate the scalable and flexible neural computation to parameterizing a symbolic system. We investigate a unified neurosymbolic system where transformations in the network can be interpreted simultaneously as both symbolic and neural computation. We extend a unified neurosymbolic architecture called the Differentiable Tree Machine in two central ways. First, we significantly increase the model's efficiency through the use of sparse vector representations symbolic structures. Second, enable its application beyond the restricted set of tree2tree problems to the more general class seq2seq problems. The improved model retains its prior generalization capabilities and, since there is fully neural path through the network, avoids the pitfalls other neurosymbolic techniques that elevate symbolic computation over neural computation.
L.D.
Introduction
Lexical
MCD
Deep learning models achieve remarkable performance across a broad range of natural language tasks [71], despite having difficulty generalizing outside of their training data, struggling with new words [36], known words new contexts [29], and novel syntactic struc- tures, like longer sequences with greater recursive depth [30, 39]. Increasingly this problem is addressed through data augmentation, which tries to make it less likely model will encounter something unlike what sees during training reducing the degree by which it has to generalize [1, 15, 26). However, even models trained on vast quantities of data struggle when evaluated on examples unlike those seen during training [32].
25
1-Shot
Lexical
Template
sDTM Transformer
NQG RU-Transformer
Length/ Struccurra
Figure 1: Generalization ability our ap- proach (sDTM) compared with baselines across various di-triibttittn shifts, av- eraged over different datasets. See $5.
WWrk partially completed while at Microsoft Research.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

This stands in contrast to how humans process language. which enables robust generalization [51]. By breaking novel sentences into known parts, we can readily interpret phrases and constructions that we have never encountered before (e.g. 'At the airport I smiled myself an upgrade', [22]). Why do models trained on orders of magnitude more language data than human hears in 200 lifetimes [25] still fail to acquire some of language's s most essential properties?
Central to language's s generalizability is compositional structure [49] where contentful units, like words, fit together in a structure, like a syntactic tree. Many classical approaches in NLP and Machine Learning attempt to induce a grammar from data the hope of leveraging the same kinds of generalization seen in natural language [e.g. 34, 33, 68]. However, structured representations are not first-order primitives in most neural networks [44, 63]. Despite theoretical appeal. the strictures of purely discrete symbolic approaches have made them difficult to apply to the breadth of tasks and domains where deep learning models have proven successful [18]. In contrast, purely connectionist models - like Transformers [71] - struggle with the kinds of sample efficiency and robust generalization ubiquitous to human learning.
Neurosymbolic methods attempt to integrate neural and symbolic techniques to arrive at a system that both compositional and flexible [4, 19, 20, 63J. While some neurosymbolic architectures achieve impressive compositional generalization, they are often brittle due to the symbolic core of their computation [58]. These methods are hybrid neurosymbolic systems, where the primary computation is symbolic, and the neural network serves to parameterize the symbolic space. We take different approach, one where symbolic operations happen in vector space. In our system, neural and symbolic computations are unified into a single space; we multiply and add vector-embedded symbolic structures instead of multiplying and adding individual neurons.
We introduce a new technique for representing trees in vector space called Sparse Coordinate Trees (SCT). SCT allows us to perform structural operations: transformations which change the structure of an object without changing the content. This is a crucial aspect of compositionality, where the structure and content can be transformed independently. We extend the Differentiable Tree Machine (DTM), a system which operates over binary trees in vector space, into the Sparse Differentiable Tree Machine (sDTM) to improve performance and upplicability to larger variety of tasks². While DTM processes vector-embes eetedded binary trees as the primitive unit of computation, the order of operations and argument selection is governed by a Transformer. We present results showing that this unified approach retains many of the desirable properties of more brittle symbolic models with regards to generalization, while remaining flexible enough to work across far wider set of tasks. While fully neural architectures or hybrid neurosymbolic techniques excel at certain types of generalization, we find that DTM, with its unified approach, excels across the widest array shifts.
The main contributions from this paper are:
Sparse Coordinate Trees (SCT), method for representing binary trees vector space as sparse tensors. ($3.1)
Bit- Shift Operating systematic and parallelized tree operations for SCT. ($3.2)
The introduction of Sparse Differentiable Tree Machine (sDTM), architectural improvements to the DTM to leverage SCT and drastically reduce parameter and memory usage. (84)
Techniques to apply DTM to seq2seq tasks by converting sequences into trees. ($4.5)
Empirical comparisons between sDTM and various baselines showing sDTM's strong general- ization across a wide variety of tasks. ($5)
2 Related Work
Work leveraging the generalizability of tree structures has a long history across Computer Science, Linguisties, and Cognitive Science [9, 45, 57, 64, 68). Much of classical NLP aims to extract structured representations from text like constituency or dependency parses [for overview: 13, 42). More recent work has shown the representations learned by sequence-to-sequene structural supervision can recover constituency, dependency, and part of speech information from latent representations in machine translation and language models [3, 6]. While those analyses show
models without
"oode available https: htap:::///tthbbb httpps///gttthb..o//pooo///////

---

Values
Tree positional index
DP.001
DP
1
The
2
The.010
NP.011
NP
3
fun
5
fun.101 person. 1 111
person
7
Figure 2: An example representation using Sparse Coordinate Trees (SCT). The values N- dimensional vectors, and the tree positional indices are integer representations of positions in the tree. The absent child nodes of "The" (indices and 6) are skipped with SCT.
structural information is encoded, they stop short showing that the representations themselves are tree-structured. Analyses inspired by Tensor Product Representations [46, 66] and chart parsing [48] give an account how representations become somewhat struttree over the course of training.
Despite the apparent emergence of semi-structured representations in Transformers and LSTMs, these architectures still appear to struggle with the kinds of structural generalization that come easily to humans [36, 31, 29]. A variety of approaches try to tackle this problem through meta-learning [37, 11], data augmentation [1], or decomposing the task into separate parts [56, 41]. The Relative- Universal Transformer [12] combines relative positional embeddings with a recurrent component, in an effort emphasize local structures while allowing for unbounded computation.
Explicitly tree structured network architectures have been introduced for RNNs [65], LSTMs [70, 16], and Transformers [72, 61]. However, these variants often do not outperform their unstructured counterpart on out-of distribuuin challenges [67]. This may be because generalization requires both structured representations and operations that respect that structure. separate line of work considers neural architectures that are used to parameterize components of a symbolic system [33, 8] fuzzy/probabilistic logic [75, 73, 14]. Similar to how vectors embedded in trees in work, some work embeds vectors within logical systems [54, 43J. Logic approaches to structure learning are also an active area of research [47, 59]. Other approaches leverage explicit stack operations [17, 24, 27, 76]. NQG from Shaw et al. [58] combines the outputs from neural and symbolic models by inducing grammar, but deferring to T5 [53] when that grammar fails. However the grammar's induction method has polynomial complexity with both dataset size and sequence length, which limits its application to larger tasks.
Vector Symbolic Architectures (VSAs) implement symbolic algorithms while leveraging high dimen- sional spaces [52, 21, 28, 35). VSAs are similar uniform neurosymbolic approaches, although VSAS commonly lack a learning component. Our work extends that of Soulos et al. [67] which can be viewed integrating Deep Learning and VSAs. They introduce the Differentiable Tree Machine for Tree-to-Tree transduction. Here we instantiate a sparse Sequence-to-Scquence version with far fewer parameters and improved memory efficiency.
3 Differentiable Tree Operations Over Sparse Coordinate Trees
Representing trees in vector space enables us to perform differentiable structural operations on them. Soulos et al. [67] used Tensor Product Representations (TPRs) [64] for this purpose. TPRs use the tensor (or outer) product to represent trees in vector space (SA.1). Use an outer product leads to a representation dimensionality that is multiplicative with both the embedding dimensionality and the number of possible tree nodes. Additionally, the number nodes is itself an exponential function of the supported depth. This makes TPRs difficult to in practice, given available memory is quickly exceeded as tree depth increases.
In this section, we introduce Sparse Coordinate Trees (SCT), a new schema for representing trees vector space. We then define library of parallelized tree operations and how to perform these operations on SCT.
3

---

Tree positional index
New tree positional index
5.0001
Values
Even mask
DP0010
VP.0011
Right bit-shift
0
2
>>
The.0100
NP0110
0a0111
hungry:0111
3
0
101.
person 1110
fun
10
5
Figure 3: Left: Performing left (orange) and right (blue). Right: visualizing the 1eft transforma- tion which results in DP being placed the root. Tree positional indices of 0 and their corresponding values are discarded.
3.1 Sparse Coordinate Trees (SCT)
Like TPRs, we want an encoding for trees that factorizes the representation into subspaces for structure and content respectively. This approach to representational spaces differs from models like RNN and Transformer, which represent structure and content jointly in unfactorized manner. By separating the structure and content subspaces a priori, we can operate over these two spaces independently. This decision is motivated by the fact that distinct treatment of these spaces is an essential aspect of compositionality.
We derive our tree representation scheme from the sparse coordinate list (COO) format. COO stores tensor data in tuples of (indices [integers], values [any format], size [integers]). The indices are N-dimensional to simulate a tensor of arbitrary shape (e.g. including dimensions such batch or length). When an index is not indicated in indices, it is assumed that the corresponding value is 0.
We give structural meaning to COO representations by defining one dimension of indices as the tree position occupied by value vector. Our tree addressing scheme based on Gorn addresses [23]: to get the tree position from an index, convert the index to binary and read from right to left. left-branch is indicated by 0 and a right branch by a 1. To distinguish between leading and left-branches (e.g. 010 vs 10), we start our addressing scheme at 1 instead of O. This indicates that all Os the left of the most-significant are unfilled and not left-branches. Figure shows an example TPR with certain constraints, and
encoding of tree with this approach. SCT can be viewed Section A. defines this equivalence and formally describes the memory savings.
Section 5.2 discusses the performance, memory, and parameter comparison between DTM models which use standard TPRs and SCT.
3.2 Differentiable Tree Operations
To operate on the trees defined in the previous section, we need a set of functions. We use small library of only three: left-child (left), right-child (right), and construct (cons) new tree from left and right subtree. Although these three functions are simple, along with the control operations of conditional branching and equality-checking, these five functions are Turing complete [45].
In addition to saving memory, SCT also provides a more efficient method for performing differentiable tree operations. The operations defined Soulos et al. [67] require precomputing, storing, and applying linear transformations for left, right, and cons. Since our values and tree positional indices are kept separate, we can compute the results of left, right, and cons dramatically more efficiently using indexing, bit-shifts, and addition.
Figure shows how we perform left directly SCT. left is performed by indexing the indices (i.e. those with 0 in the least significant bit, which targets all the nodes left of the root) and their corresponding values, then performing right bit-shift on the indices. right symmetrical, except that we index for the odd positional indices and ignore position in order to remove the previous root node. cons performed by left bit- bit-shifting the positional indices from the left- and
In LISP and expert systems literature, left is referred car, and right is referred cdr.

---

sught-subtree arguments, then adding to the newly shifted indices for the right argument. A new value s can be provided for the root node.
Our network also needs to learn a program over multiple operations differentiably. This involves the aforementioned structured operations, well differentiable selection of which operation to perform and on which trees. We take weighted sums over the three operations left, right, and cons, as well over potential trees. Specific details are discussed in the next section. The result of our weighted sum is coalesced, which removes duplicate positional indices by summing together all of the values that share a specific index. Formally, define the trees over which to perform left Tr, right Tn. and cons TcL. & Ton: T = [Tz; Tn: TCL; Tcn]. We also take new value s TRd to be inserted (x) at the new root node of the cons operation, and vector of operation weights = (WL, WR. we) which sum to I.
( T,,) w.leef(TT)) wnright(Tn) + wc(cons(TcL, Tcn) + m)
(I)
4 The Sparse Differentiable Tree Machine (sDTM)
Our work extends the Differentiable Tree Machine (DTM) introduced in Soulos et al. [67] with the Sparse Differentiable Tree Machine (sDTM). While similar to the original at a computational level, sDTM represents different implementation of these concepts that make it dramatically more parameter and memory efficient. We also introduce techniques to apply sDTM to tasks with sequence input and output (seq2seq).
4.1 Overview
sDTM uses our Sparse Coordinate Trees schema across its components. Like the original DTM, our model is comprised of agent, interpreter, and mem- ory (illustrated in Figure 4). The Interpreter performs Equation by applying the bit-shifting tree opera- tions from Section 3.2 and weighting the result. The output from the interpreter written to the next avail- able memory slot, and the last memory slot is taken as the output.
Differentiable Tree Machine (DTM)
Agent
Interpreter
Memory
Figure 4: A schematic of how the three core components of the DTM (agent, interpreter, and memory) relate to each other. Adapted from Soulos al. [67].
The Agent is a Transformer encoder that takes an encoding of the memory as input and produces the inputs for Equation 1: पē, T, and s. Two special tokens, <OP> and <ROOT>, are fed into the Agent to represent ui and s. Each time a tree is written to memory, a fixed-dimensional encoding of that tree is produced and fed as new token to the agent ($4.2). The agent soft-selects tree arguments for the over the trees in memory. Figure 6 in the Appendix
interpreter, T. by performing weighted contains a detailed diagram showing the flow of information for one layer sDTM
The agent which implicitly parameterizes the conditional branching and control flow of the program modeled by a Transformer, and it is possible for sDTM to face some of the generalization pitfalls that plague Transformers. The design of sDTM encourages compositional generalization through differentiable programs, but it does not strictly enforce the constraints classical symbolic programs. As the results in Section 5 show, sDTM can learn generalizable solutions to some tasks despite the presence of a Transformer, but on some other tasks the issues with generalization are still present.
4.2 Pooling by attention
Each tree in memory needs to have fixed-dimense dimensional encoding to feed into the agent regardless of how many nodes are filled. Commonly this is done via pooling, like taking the means in the tree, or linear transformation in the case of the original DTM. Instead, we use Pooling by Multi-headed Attention (PMA) [38], which performs a weighted sum over the elements, where the weight is derived based on query-key attention.
elements
5

---

Attention is permutation invariant to the ordering of key and value vectors, but it is important that our pooling considers tree position information. To enforce this, we convert the position indices to their binary vector representation
This leads to an asymmetrical vector with only positive represent left branches -1 and keep right branches as +1. For example, position + [0, 0, 0, 0, 0, 0, - |0,0,0,0,0, 1, -1, The input to our pooling function the concatenation of this positional encoding i with the token embedding I at that position: { D). This method for integrating token and node position is similar to tree positional encoding from Shiv and Quirk [60], except that we use concatenation and a linear transformation to mix the content and position information instead of addition.
values, so instead
Unlike standard self attention, we use separate learnable parameter for our query vector T E Raum_ headsxkkey_dimm We pass [ through linear transformations to generate keys k e Renum_heads feadsxxey__dimgg and values E R
x valuddi The result of this computation is always
E _aun b dim given that q is fixed and does not depend on the input. The rest of the computation is identical to a Transformer with pre-layer normalization [74].
4.3 Tree Pruning
While Sparse Coordinate Trees mean that trees with fewer filled nodes take up less memory. the way our model blends operations results in trees becoming dense. The interpreter returns blend of all three operations at each step, including the cons operation which increases the size of the representation by combining two trees. practice even as the entropy of the blending distribution drops, the probability of any operation never becomes fully O. This means that over many steps, trees start to become dense due to repeated use of cons. order to keep our trees sparse, we use pruning: only keeping the top-k nodes as measured by magnitude. k is hyper-paramett that can be set along with the batch size depending on available memory.
4.4 Lexical Regularization
To aid lexical generalization, we add noise to our token embeddings. Before feeding an embedded batch into the model, we sample from multi-variate standard normal for each position in each tree, adding the noise to the embeddings as a form of regularization [5]. Ablation results showing the importance of this regularization are available in Appendix A.3.
4.5 Handling Sequential Inputs and Outputs
seq2tree The original DTM can only be applied to tasks where a tree structure is known for both inputs and outputs. Here we provide extension to allow DTM to process sequence inputs. To do this we treat each input token as a tree with only the root node occupied by the token embedding. We then initialize the tree memory with N trees, one for each token in the input sequence. Figure 5 left depicts the initial memory state for a sequence. The agent's 's attention mechanism is ionmuutttiionnnvaiinnt so in order to distinguish between two sequences which contain the same tokens but in different orders, we apply random sinusoidal positional encodings to the first N tokens passed to the agent [40, 55). Random positional encodings sample set of increasing integers from left-to-right instead of assigning a fixed position to each token. The purpose of left and right is to extract subtrees. Since our seq2tree setting the input sequence processed in a completely bottom-up manner, we restrict the agent and interpreter to only have single operation: cons. Use of a single operation to construct new trees from subtrees aligns the DTM theoretically with the Minimalist Program [10], which addresses natural language's compositionality in terms of single operation: merge.
seq2seq To handle sequence inputs and outputs we convert the output sequence to a tree. One method to convert the output sequence into a tree is to use parser. Alternatively, when a parser is not available, we can embed sequence as the left-aligned leaves at uniform depth (LAUD). Figure right shows how an output sequence can be embedded using LAUD. Since all of the non-terminal nodes are the same, we can hardeode the root argument to cons. We insert special token <EOB> to signify the end of branch, similar to an <EOS> token.

---

walk thrice and look right
WALK WALK WALK RIGHT LOOK
<NT>
Memory
walk
thrice
and
look
right
<NT>
<NT>
<NT>
<NT>
<NT>
<EOB>
0
2
Ø
WALK RIGHT LOOK
Figure 5: Left: The memory state is initialized as a sequence of trees where only the root node contains a token, Right: An output sequence is embedded in tree using the left-aligned uniform- depth (LAUD) scheme. <NT> and <EOB> are special tokens not in the original output sequence.
Results
5.1 Baselines
We consider models that are trained from scratch on the datasets they're evaluated on; while the compositional capabilities of large pre-trained models are under active debate [32], we are interested in the compositional abilities of the underlying architecture - rather than those that may result from a pre-training objective. We compare sDTM two fully neural models, standard Transformer TrUnssssformerr which was previously shown
[71] as well as a relative universal Transformer to improve systematic generalization on variety of tasks [12]. We also compare our model to hybrid neurosymbolic system, NQG [58, 69], model which uses a neural network to learn quasi-synchronous context-free grammar [62]. NQG was introduced alongside NQG-T5, which is modular system that uses NQG when the grammar produces answer and falls back to a fine-tuned large language model T5 [53]. As mentioned at the beginning of this section, we only compare to NQG in this paper since we want to evaluate models that have not undergone significant pre-training." Details related to data preprocessing ($A.4), model training ($A.6, $A.8), compute resources ($A.9), and dataset details (S).10) are available in the Appendix. For all datasets, the reported results the best exact match accuracies on the test set over five random seeds. Additional data on means and standard deviations across the five runs shown in Section A.7.
For each task, we test whether models generalize to samples drawn from various data distributions. Independent and identically distributed (IID) samples are drawn from a distribution shared with training data. We evaluate several out-of-distribution (OOD) shifts. One-shot lexical samples, while drawn from the same distribution as the training data, contain word that was only seen in a single training sample. Similarly, Zero-shot lexical samples are those where the model is not exposed to word at all during training. Structural/length generalization tests whether models can generalize to longer sequences (length) or nodes not encountered during training (structural). Template generalization withholds abstract n-gram sequence during training, and then each test sample fits the template. Finally, maximum compound divergence (MCD) generates train and test sets with identical uni-gram distributions but maximally divergent n-grams frequencies [29]. Although models are often tested on a single type of generalization, we believe evaluating a model across a broad array of distributional shifts is essential for characterizing the robustness of its generalization performance.
5.2 Performance Regression (Active==Loiica)
Lotivet+Logical is tree2tree task containing input and output trees in active voice and logical forms [67]. Transforming tree in active voice to its logical form simulates semantic parsing, and transforming a logical form tree to active voice simulates natural language generation. For this dataset, there are three test sets: IID, 0-shot lexical, and structural. In addition to the baselines listed in the previous section, we also compare our modified sDTM the original DTM. This enables us to confirm that our proposed changes to decrease parameter count and memory usage while increasing inference speed does not lead a performance regression. The results are show in Table
NQQ uses pre-trained BERT embeddings [15]; it is unknown how much this pre- pre-training helps the method.
7

---

Table 1: Active++Logical accuracy. Results are the best performance over five runs. The sets are divided into IID, and OOD sets 0-shot lexical and structural. Parameter and memory usage is shown for the original DTM with TPRs and our proposed sparse DTM with and without pruning. Our modifications reduce the parameter count by almost two orders of magnitude. "NQG was trained on a seq2seq version without parantheses because was not able to learn the tree2tree training set.
Model
Split
O-Shot Lexical
IID
Structural
Transformer
1.0
0.0
0.0
RU-Transformer
1.0
0.0
.12
NQG
.45
0.0
0.0
Relative Speed
Parameters
Memory (GB)
Original DTM
1.0
1.0
1.0
72M
12.3
34
sDTM
1.0
1.0
1.0
1M
9.7
2.5
sDTM (pruned k= k=1024)
1.0
1.0
.95
1M
1.8
1
The various DTM models and Transformers all perform perfectly the III test set. NQG struggles to learn the Activet+Logical task, an example of the brittleness of hybrid neurosymbolic systems. Only the DTM variants succeed on the OOD test sets. As anticipated, the RU-Transformer performs better than the standard Transformer with regards to structural generalization.
Comparing the original DTM sDTM without pruning, pooling by attention, a 20% reduction in memory usage from fewer parameters and SCT, as well as a roughly 13x speedup. We are able to gain even further memory savings and speed improvements due to the pruning method. The final two rows show that the pruning method has no impact on lexical generalization and minor impact
70x reduction in parameter count from
structural generalization, while reducing memory usage by 5x and improving speed by 2.5x. The results from this experiment confirm that sDTM is capable of matching DTM performance ceiling, it is difficult to isolate the effect of the proposed changes in this paper. We will investigate this question further in Section 5.5. Next,
previous baseline. However, since both DTM and sDTM perform near
tasks where the original DTM could not be used.
5.3 Scalability (FOR2LAM)
FOR2LAM is tree2tree program translation task translate an abstract syntax tree (AST) in an imperative language (FOR) to an AST in a functional language (LAM) [7]. Due to the depth of the trees in this dataset, DTM unable fit a batch size of into memory. This makes FOR2LAM good dataset to test the scalability of sDTM to more complex samples. We augment the FOR2LAM dataset with a 0-shot lexical test set. During training, only two variable names appear: 'x' and 'y'. For the 0-shot test, we replace all occurrences of in the test set with new token 'z'. We are unable to test DTM on FOR2LAM because batch size of does not fit into memory due to the depth of the trees in the dataset.
Results on FOR2LAM are shown on the left side of Table 2. NQG suffers with scale (see A.8), and we were unable to include results for it on FOR2LAM due to training and evaluation exceeding 7 days. All other models do well on the in-distribution test set, but only DTK able to achieve substantive accuracy on the 0-shot lexical test. DTK's performance is impressive given work on data augmentation has shown the difficulty of few-shot generalization inversely proportional to vocabulary size [50], with smaller vocabulary tasks being more challenging. This (-shot challenge is from 2 variables (x, y) to 3 (x, y, 7), making difficult enough that both transformer variants score 3%.
5.4 Seq2Tree (GeoQuery)
GeoQuery is natural language to SQL. dataset [77] where model needs to map question stated in natural language to correctly formatted SQL query, including parentheses to mark functions

---

Table 2: Accuracies on FOR2LAM and GeoQuery. Results are the best performance over five runs. NQG cannot be evaluated on FOR2LAM because it takes over a week to train. 'Results taken from Shaw et al. [58]. "We report the results from a replication study of NQG where the result on the Length split differed substantially from the original result [69].
FOR2LAM
GeoQuery
Model
IID
O-shot lexical
IID
Length
Template
TMCD
Transformer
1.0
.03
.88
.26
.79
.40
Tranrfosformer
1.0
.03
.87
.25
.77
.37
NQG
.76
.371266*
.62
.41
sDTM
1.0
.61
.73
.20
.20
.36
and arguments. We the parentheses and function argument relationship as the tree structure for our output. In this format, GeoQuery is a seq2tree task, and we follow the description from Section 4.5, We use the same preprocessing and data as Shaw al. [58]. The TMCD split for Quequery [58] extends MCD to natural language datasets instead of synthetic languages. GeoQuery is a very small dataset, with training set containing between 440 and 600 samples, depending on the split. Like FOR2LAM, we are unable to test DTM on GeoQuery because a batch size of does not fit into memory due to the depth of the trees in the dataset.
Results for GeoQuery are shown on the right side of Table 2. This is the most difficult task that we test because of the small training set, and the natural language input is not draw from a synthetic grammar. Given this, a potential symbolic solution to this task might be quite complex. We find that both NQG and DTM perform worse than the two Transformer variants on the IID test set. This also holds true for the Template split, where Transformers outperform the neurosymbolic models. On the Length and TMCD splits, all of the baselines achieve roughly the same performance while DTM performs slightly worse - the degree of variation in the input space and small training set appear to make it difficult for sDTM to find a compositional solution.
is worth noting that there is substantial room for improvement across every model on GeoQuery. The small dataset with high variation poses problem for both compositional methods of sDTM and NQG. It is possible that with sufficient data, GeoQuery's latent compositional structure could be identified by NQG and DTM, but the released GeoQuery dataset has only the order of 500 training examples. Given all methods struggle to model the IID split, we refrain from drawing substantive conclusions based minor differences in accuracy on this single task in isolation from the rest of the results.
5.5 Seq2Seq (SCAN)
SCAN is a synthetic seq2seq task with training and test variations to examine out-of-distribution generalization [36]. To process seq2seq samples, we follow the description in Section 4.5. We compare two methods for embedding the output sequence into tree by writing parser for SCAN's output and comparing this to the left-aligned uniform -epth trees (LAUD). In addition to the standard test splits from SCAN, introduce 0-shot lexical test set well.
Since the trees in SCAN are not very deep, we are able to compare sDTM to DTM to isolate the effect of pooling by attention ($4.2). We modify the original DTM to handle sequential inputs and outputs as described in Section 4.5. Replacing the linear transformation in DTM with pooling by attention in sDTM leads to drastically better results; DTM is unable to perform well even on the simple IID split, whereas sDTM performs well across many of the splits.
All baselines perform well on the IID test set, showing that they have learned the training distribution well. Transformer variants perform poorly on lexical, length, and MCD splits. The Transformers and sDTM perform well on the Template split while NQG completely fails. Along with the results from GeoQuery, which showed weak sDMM performance on the Template split and strong performance from both Transformers, it seems that the Transformer architecture is robust under template shifts between training and testing. sDTM is the only model to perform well on the O-shot lexical test set, whereas NQG is the only model able to perform well the MCD test set. The two sDTM rows

---

Table 3: SCAN accuracy. Results are the best performance over five runs. MCD scores are calculated as the average of the three MCD splits. 'Results from Shaw et al. [58]. "Results from Sun et al. [69].
Model
Split
IID
1-shot lexical
0-shot lexical
Length
Template
MCD
Transformer
1.0
.08
0.0
.07
1.0
.02
RU-Transformer
1.0
.11
0.0
.19
1.0
.01
NQG
1.0*
1.0
0.0
1.0
0.0*
1.0
sDTM (parse trees)
1.0
.99
.99
.75
.95
.03
sDTM (LAUD trees)
1.0
.87
.98
.06
.98
0.0
DTM (parse trees)
0.0
0.0
0.0
0.0
0.0
0.0
compare models trained with output trees from a parser or LAUD encoding. The main performance difference is on the Length split, where the structurally relevant information in the parse trees is necessary for sDTM to perform well. It is not necessary to have structured input for the model to perform well length generalization as long as the output is structured.
6 Conclusions
We introduced the Sparse Differentiable Tree Machine (sDTM) and a novel schema for efficiently representing trees in vector space: Sparse Coordinate Trees (SCT). Unlike the fully neural and hybrid neurosymbolic baselines presented here, sDTM takes unified approach whereby symbolic operations occur vector space. While not perfect sDTM struggles with MCD and Template shifts, as well as the extremely small GeoQuery dataset - the model generalizes robustly across the widest variefy of distributional shifts. sDTM also uniquely capable of zero-shot lexical generalization, likely enabled by its factorization of content and structure.
While these capacities for generalization are shared with the original DTM, our instantiation is computationally efficient (representing a 75x reduction in parameters) and can be applied to seq2seq. seq2tree, and tree2tree tasks. Our work reaffirms the ability of neurosymbolie approaches to bridge the flexibility of connectionist models with the generalization of symbolic systems. We believe continued focus on efficient neurosymbolic implementations can lead to architectures with the kinds of robust generalization, scalability, and flexibility characteristic of human intelligence.
References
[1] Jacob Andreas. Good-Enough Compositional Data Augmentation. Proceedings of the 58th Annual Meeting the Association for Computational Linguistics, pages 7556-7566, Online, 2020. Association for Computational Linguistics. doi: 10.1 18653//1/2000..clmmaiil https://www. http://wwwwwwlwe.bbbb aclweb. org/
URL
aacl-main.677.
[2] Samy Badreddine, Artur Avila Garcez, Luciano Serafini, and Michael Spranger. Logic tensor networks. Artificial Intelligence, 303: 303:103649, 2022. ISSN 0004-3702. doi: https:
(tbiioog//00.101//.aatttttt.
URL URL.ttsps://wwx..cieneeee http:///wwww.ccneeeeeeee.ttt cew.rienceerretttcco/sieeeeet com/science/
articleepp1//00447702200002
[3] Yonatan Belinkov and James Glass. Analysis methods neural language processing: A survey. Transactions of the Association for Computational Linguistics, 7:49-72, 2019.
[4] Tarek R. Besold, Artur S. d' Avila Garcez, Sebastian Bader, Howard Bowman, Pedro M. Domin- gos, Pascal Hitzler, Kai-Uwe Kühnberger, Luis C. Lamb, Daniel Lowd, Priscila Machado Vieira Lima, Leo de Penning, Gadi Pinkas, Hoifung Poon, and Gerson Zaverucha. Neural-symbolic learning and reasoning: A survey and interpretation. CoRR, Abs/1711.0099/ 2017. URL http:/ hett:///rziie www.xii..og/bba....... wtggaab//71...... 03902.
[5] Chris M. Bishop. Training with noise equivalent tikhonov regularization. Neural Computa- tion. 7(1):108-116 1995. doi: 1tl.16///cco..99..7..02
10

---

[6] Terra Blevins, Omer Levy, and Luke Zettlemoyer. Deep rns encode soft hierarchical syntax. arXiv preprint arXiv:1805.044 04218, 2018.
[7] Xinyun Chen, Chang Liu, and Dawn Song. Tree-to-tree neural networks for program translation. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc.. 2018. URL https: //poceeed/s//seeeenn..... neurips. cc/ "paape_rillee wtt.ff/eee//pppr///////111/ TT5S77658Babb11222666665555544 Paper. .df.
[8] Xinyun Chen, Chen Liang, Adams Wei Yu, Dawn Song, and Denny Zhou. Compositional generalization via neural-symbolic stack machines. Advances in Neural Information Processing Systems, 33:1190--1111 2020.
[9] Noam Chomsky. Aspects of the theory of syntax. Number no. 11 in Massachusetts Institute of Technology. Research Laboratory of Electronics. Special technical report. The MIT Press, Cambridge, Massachusetts, 50th anniversary edition edition, 1965. ISBN 978-0-262-52740-8.
[10] Noam Chomsky. The Minimalist Program. The MIT Press, 12 2014. ISBN 9780262327282. doi: 7551 /mstttssssss//////
(17751/mmippes//9777223377747 000.7000000000011. URL https:t/tti.oooooo
7780262527347.000 111.000..0000 0001.
[11] Henry Conklin, Bailin Wang, Kenny Smith, and Ivan Titov. Meta-learning to compositionally generalize. arXiv preprint arXiv:2106. 100e22006.442,,, 2021.
[12] Róbert Csordás, Kazuki Irie, and Juergen Schmidhuber. The devil is in the detail: Simple tricks improve systematic generalization of transformers. In FranieFFanccie Moens, Xuanjing Huang, Lucia Specia, and Scott Wen-tau Yih, editors, Proceedings of the 202/ Conference Methods in Natural Language Processing, pages
Empirical Online and Punta Cana, Dominican Republic, November 2021. Association for Computational Linguistics. doi: 10. 10.18653/v1/20211. emnlp-main.49) URL hhwl:///ooolllllaoooooo org/2021
[13] Fernando Cuetos, Don C Mitchell, and Martin MB Corley. Parsing in different languages. In Language processing in Spanish, pages 163-208. Psychology Press, 2013.
[14] Lennert De Smet, Pedro Zuidberg Dos Martires, Robin Manhaeve, Giuseppe Marra, An- gelika Kimmig, and Luc De Readt. Neural probabilistic logic programming in discrete- continuous domains. In Robin J. Evans and Ilya Shpitser, editors, Proceedings of the Thirty-Ninth Conference on Uncertainty Artificial Intelligence, volume 216 of Proceed- ings of Machine Learning Research, pages 529-538. PMLR, 31 Jul-04 Aug 2023. URL https:/ https:://proceeding: mlr. ..ir.pres ppwss//216/ smet23a. html.
[15] Jacob Devlin, Ming- Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. 1rXiv:1810.000 04800 [cs], May 2019. URL http: //axivv./xxii.///// hbtg//bs//ie 04805. arXiv: 1810.04805.
[16] Li Dong and Mirella Lapata. Language logical form with neural attention. arXiv preprint 1601.0028 2016.
[17] Brian DuSell and David Chiang. Stack attention: Improving the ability of transformers model hierarchical patterns. In The Twelfth International Conference Learning Representations, 2024. URL https: h /pwpn/eveeeeeeeeee///////eeeeeee net/ wttf/oooommnd//naaa
[18] Daniel Furrer, Mare van Zee, Nathan Scales, and Nathanael Schärli. Compositional gen- eralization in semantic parsing: Pre-training vs. specialized architectures. arXiv preprint arXiv:2007.08970. 2020.
[19] Artur SD' Avila Garcez, Luis Lamb, and Dov M Gabbay. Newral-symbolic cognitive reasoning. Springer Science & Business Media, 2008
[20] Marta Garnelo and Murray Shanahan. Reconciling deep learning with symbolic artificial intelligence: representing objects and relations. Current Opinion in Behavioral Sciences, 29; 17-23, 2019. ISSN 2352-1546.
doi: http::/do..agg///..o0ooo...ooooa
12.011. URL
https:/ attps://www.cr https//ww...cicmeddeeee.. http://.....t..t.........oooaaaa
Arti-
ficial Intelligence.
[21] Ross W Gayler. Vector symbolic architectures answer jackendoff's challenges for cognitive neuroscience. In Peter Slezak, editor, Proceedings of the ICCS/ASCS Joint International Conference on Cognitive Science (ICCS/ASCS 2003), pages 133-138, Sydney, NSW, AU, jul 2003. University of New South Wales. URL http:://arraeete //tp://aaivv//////////eeeea.aev/ org/ abs/ cs 0412059.
11

---

[22] Adele E Goldberg. Constructions at work: the nature of generalization in language. Oxford Uni- versity Press, Oxford; New York, 2006. URL http: / pubbicc..c....ppppp.p ebookcentral. wwo.unre.........t........ proquest. com/choice/publle www.bbiiculrrroor.dcooo 3tt.
OCI.C: 193697889.
[23] Saul Gom. Explicit Definitions and Linguistic Dominoes, pages 77-115. University of Toronto Press, Toronto, 1967. ISBN 9781487592769. doi: 1b1::000.1188/788187555722668880 https://doi.org//
URL
[24] Edward Grefenstette, Karl Moritz Hermann, Mustafa Suleyman, and Phil Blunsom. Learning to transduce with unbounded memory. Advances in neural information processing systems, 28, 2015.
[25] Thomas I. Griffiths. Understanding human intelligence through human limitations. Trends in Cognitive Sciences, 24:873-883, 2020. URL. / www.nticscholle............ org/
CorpusID: 221996148.
[26] Demi Guo, Yoon Kim, and Alexander M. Rush. Sequence-LLevel Mixed Sample Data Augmen- tation. arXiv:2011.09033 [cs]. November 2020. URL http://// //tp://///xxvv///a http://aaxivv....aaaa./ wwt.ooog/////aaeeeo/ooo httg//b//2011..// 09039. arXiv: 201 1.09039.
[27] Armand Joulin and Tomas Mikolov. Inferring algorithmic patterns with stack-augmented recurrent nets. Advances in neural information processing systems, 28, 2015.
[28] Pentti Kanerva. Hyperdimensional computing: An introduction to computing in distributed representation with nigh-dimensional random vectors. Cognitive computation, 1: 159, 2009.
[29]
Daniel Keysers, Nathanael Schärli, Nathan Scales, Hylke Buisman, Daniel Furrer, Sergii Kashu- bin, Nikola Momchev, Danila Sinopalnikov, Lukasz Stafiniak, Tibor Tihon, Dmitry Tsarkov, Xiao Wang, Mare van Zee, and Olivier Bousquet. Mcasuring compositional generalization: comprehensive method on realistic data. In International Conference on Learning Representa- tions, 2020. URL batpss: http///ppeeeeeeeeeeeeeeeeeeeeeee wtt.://eooooommteddseeeattteeee
[30] Najoung Kim and Tal Linzen. COGS: A compositional generalization challenge based on semantic interpretation. In Bonnie Webber, Trevor Cohn, Yulan He, and Yang Liu, editors, Proceedings of the 2020 Conference Empirical Methods in Natural Language Processing (EMNLP), pages 9087-9105, Online, November 2020. Association for Computational Lin- guistics. doi: emnlp-main. 731.
mmn.0-mainnmm.731....... URL https: htapp:://aalaaateee /ttp//aaaaaattoo........o org. 22200
[31] Najoung Kim and Tal Linzen. COGS: A Compositional Generalization Challenge Based on Semantic Interpretation. arXiv:2010.05465 [cs], October 2020. URL http://arxiv org/ abs/2010. 05465. arXiv: 2010.05465.
[32] Najoung Kim, Tal Linzen, and Paul Smolensky. Uncontrolled lexical exposure leads to overesti- mation of compositional generalization in pretrained models. arXiv preprint arXiv:2212.10700 2022.
[33] Yoon Kim, Chris Dyer, and Alexander M Rush. Compound probabilistic context-free grammars for grammar induction. arXiv preprint arXiv:1906. 10225, 2019.
[34] Dan Klein and Christopher D Manning. A generative constituent-contex model for improved grammar induction. In Proceedings of the 40th Annual Meeting of the Association for Computa- tional Linguistics, pages 135, 2002.
[35] Denis Kleyko, Dmitri A. Rachkovskij, Evgeny Osipov, and Abbas Rahimi. A survey hyperdimensional computing aka vector symbolic architectures, part i: Models and data trans- formations. ACM Comput. Surv,, 55(6), dec 2022. ISSN 0360-0300. doi: 10.1145/3538531.
URI. htt.hhttt://oll org/10 10. 1145/3538531.
[36] Brenden Lake and Marco Baroni. Generalization without systematicity: On the compositional recurrent networks. 35th International Conference on Machine
skills of sequence-to-sequeee Learning, ICMI. 2018, 7:4487-4499, 2018. arXiv: 1711.0030 ISBN: 9781 510867666.
[37] Brenden M Lake. Compositional generalization through meta sequennce-to-sequeece learning. Advances in neural information processing systems, 32, 2019.
[38] Juho Lee, Yoonho Lee, Jungtaek Kim, Adam Kosiorek, Seungjin Choi, and Yee Whye Teh. Set transformer: A framework for attention-based permutation-invaric neural networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference Machine Learning, volume 97 of Proceedings of Machine Learning Research,
12

---

pages 1754-3753. PMLR, 09-15 Jun 2019. URL https://pprooeedings mlr http:://poooeddnngg...rresss//// lee19d. html.
[39] Bingzhi Li, Lucia Donatelli, Alexander Koller, Tal Linzen, Yuekun Yao, and Najoung Kim. SLOG: A Structural Generalization Benchmark for Semantic Parsing, October 2023, URL http://arxi:: wttp:vv..rg/bb//////ee 15040. urXiv:2310.15040 [cs].
[40] Yuxuan Li and James McClelland. Representations and computations in transformers that support generalization structured tasks. Transactions Machine Learning Research, 2023.
ISSN 2835-8856. URL https: /ttp///peeeeeeeeeeeeeeeeeeeeeeee wttpe//weeeetttommm///ooo/o000/ od=.F
[41]
Matthias Lindemann, Alexander Koller, and Ivan Titov. Compositional generalization without trees using multiset tagging and latent permutations. arXiv preprint arXiv:2305.16994. 2023.
[42]
Adam Lopez. Statistical machine translation, ACM Computing Surveys (CSUR), 40(3):1 49, 2008.
[43] Jaron Maene and Luc De Raedt. Soft-unification in deep probabilistic logic. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances in Neu- ral Information Processing Systems, volume 36, pages 60804-60820. Curran Associates, Inc., 2023. URL https: httpps://prooceedingg neurips cc/ wwwpaper_fiiieceeeceeeeeeeeeeepp wwt.ffeeeeeppe//2/.... 722215577777733066667766666466 Paapeee--aaao-------------e---e erence. pdf.
[44] Gary F. Marcus. The Algebraic Mind: Integrating Connectionism and Cognitive Science. MIT
Press, 2001.
[45] John McCarthy. Recursive functions of symbolic expressions and their computation by machine, part i. Communications of the ACM, 3(4):184-195) 1960.
[46] Thomas McCoy, Tal Linzen, Ewan Dunbar, and Paul Smolensky. Rons implicitly implement tensor product representations. arXiv preprint arXiv:1812.08771. 2018.
[47] Stephen Muggleton. Inductive logic programming. New Generation Computing, 8(4):295-318, February 1991. ISSN 1882-7055. doi: 10.1007/BBF03037089 URL https://doi...... org/10.
1007/BF03037089.
[48] Shikhar Murty, Pratyusha Sharma, Jacob Andreas, and Christopher D) Manning. Char- acterizing intrinsic compositionality in transformers with tree projections. arXiv preprint arXiv:2211.01228, 2022.
[49] Barbara Partee et al. Lexical semantics and compositionality. An invitation to cognitive science: Language, 1-360, 1995.
[50] Arkil Patel, Satwik Bhattamishra, Phil Blunsom, and Navin Goyal. Revisiting the compositional generalization abilitics of neural sequence models. arXiv preprint arXiv:2203.077 074402 2022. [51] Steven Pinker. The language instinct: How the mind creates language. Penguin uk, 2003.
[52] Tony A. Plate. Holographic Reduced Representation: Distributed Representation for Cognitive Structures. CSLI Publications, USA, 2003, ISBN 1575864290.
[53] Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. J. Mach. Learn. Res., (1)., jan 2020. ISSN 1532-4435.
[54] Tim Rocktäschel and Sebastian Riedel. Learning knowledge base inference with neural thcorem provers. In Jay Pujara, Tim Rocktaschel, Danqi Chen, and Sameer Singh, editors, Proceedings of the 5th Workshop on Automated Knowledge Base Construction, pages 45-50, San Diego, CA, June 2016. Association for Computational Linguisties. doi: 10.18653/v1/W 16 1309. URL https://aacaatthonn
org/w16- 1309.
[55] Anian Ruoss, Grégoire Delétang, Tim Genewein, Jordi Grau-Moya, Róbert Csordás, Mehdi Bennani, Shane Legg, and Joel Veness. Randomized positional encodings boost length gen- eralization of transformers. In Anna Rogers, Jordan Boyd-Graber, and Naoaki Okazaki, ed- itors, Proceedings of the 61st Annual Meeting of the Association for Computational Lin- guisties (Volume 2: Short Papers), pages 1889-1903, Toronto, Canada, July 2023. Associ- ation for Computational Linguistics. doi: 10. accp://///22....sro.or..oo // //aclanthology . org /223.223..o2 acl- short.
URL https:
[56] Jake Russin, Jason Jo, Randall C O'RReilly and Yoshua Bengio. Compositional generalization in deep seq2seq model by separating syntax and semanties. arXiv preprint arXiv:1904.009: 2019.
13

---

[57] Itiroo Sakai. Syntax in universal translation. In Proceedings of the International Conference on Machine Translation and Applied Language Analysis, 1961.
[58] Peter Shaw, Ming- generalization and natural language variation: Can semantic parsing approach handle both? In Chengqing Zong, Fei Xia, Wenjie Li, and Roberto Navigli, editors, Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 1 11th International Joint Conference on Natural Language Processing (Volume I: Long Papers), pages 922-938, Online, August 2021. Association for Computational Linguistics. doi: 10.18653/v1/2021. acl-long.75 URL https: / /a//aclllllm aclanthology org/2021 acl- 1ong.15.....
Ming-Wei Wei Chang, Panupong Pasupat, and Kristina Toutanova. Compositional
[59] Hikaru Shindo, Masaaki Nishino, and Akihiro Yamamoto. Differentiable inductive logic programming for structured examples. Proceedings of the AAAI Conference on Artificial Intelligence, 35(6):50345001, May 2021. doi:
wttp///aaaa.33..16666. URL. https:
Btt///AAAA/araiaa /AA.///artiieeeveee///tteae / //jjs. //ojs.aai.... org/index.pppiie
[60] Vighnesh Shiv and Chris Quirk. Novel positional encodings to enable tree-based transform- ers. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL https:: p/toceeee//ppoooeeeennneee www.wne..r./enneeeeeeee 00001746221488111855577666oo Paapeedrdddddddeeaeer.eeere pdf.
[61] Vighnesh Shiv and Chris Quirk. Novel positional encodings to enable tree-based transformers. Advances in neural information processing systems, 32, 2019.
[62] David Smith and Jason Eisner. Quasi-synchronous grammars: Alignment by soft projection of syntactic dependencies. In Philipp Koehn and Christof Monz, editors, Proceedings on the Workshop on Statistical Machine Translation, pages 23-30, New York City, June 2006. Association for Computational Linguistics. URL https: / //a/aaaaaantlllooooo org/W06-330
[63] Paul Smolensky. On the proper treatment of connectionism. Behavioral and Brain Sciences, 11 (1):1-23, 1988. doi: 10. 1017//001405550000522202
[64] Paul Smolensky, Tensor product variable binding and the representation of symbolic structures in connectionist systems. Artif. Intell., 46: 159-216, 1990.
[65] Richard Socher, Brody Huval, Christopher D. Manning, and Andrew Y. Ng. Semantic com- positionality through recursive matrix-vector spaces. In Lun'ichi Tsujii, James Henderson, and Marius Pasca, editors, Proceedings of the 2012 Joint Conference on Empirical Meth- ods in Natural Language Processing and Computational Natural Language Learning, pages 1201-1211, Jeju Island, Korea, July 2012. Association for Computational Linguistics. URL https://aclanthholgg org/ Dttg/D12-111001
[66] Paul Soulos, Tom McCoy, Tal Linzen, and Paul Smolensky. Discovering the compositional structure of vector representations role learning networks. arXiv preprint 1101::1910009113, 2019.
[67] Paul Soulos, Edward Hu, Kate McCurdy, Yunmo Chen, Roland Fernandez, Paul Smolensky. and Jianfeng Gao. Differentiable Tree Operations Promote Compositional Generalization, June 2023. URL http:: org/ abs/ 00751. arXiv:2306.00751 [cs].
[68] Mark Steedman. Combinatory grammars and parasitic gaps. Natural Language & Linguistic Theory, 5(3):403-439 1987.
[69] Kaiser Sun, Adina Williams, and Dieuwke Hupkes. A Replication Study of Compositional Generalization Works on Semantic Parsing. August 2023. URL httpp::/ net/
[70] Kai Sheng Tai, Richard Socher, and Christopher D Manning. Improved semantic representations from tree-structured long thort-term memory networks. arXiv preprint arXiv:
2015.
[71] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017.
[72] Yau-Shian Wang, Hung-Yi Yi Lee, and Yun-Nung Chen. Tree transformer: Integrating tree structures into self-attention. arXiv preprint
2019.
14

---

[73] Thomas Winters, Giuseppe Marra, Robin Manhaeve, and Luc De Raedt. Deepstochlog: Neural stochastic logic programming. Proceedings of the AAAI Conference on Artificial Intelligence. 36(9):10090-11100, Jun. 2022. doi: 10.
URL. https:////// aaai.
[74] Ruibin Xiong, Yunchang Yang, Di He, Kai Zheng, Shuxin Zheng, Chen Xing, Huishuai Zhang, Yanyan Lan, Liwei Wang, and Tieyan Liu. On layer normalization in the transformer architecture. In International Conference on Machine Learning, pages 10524-10533. PMLR, 2020.
[75] Zhun Yang. Adam Ishay, and Joohyung Lee. Neurasp: Embracing neural networks into answer set programming. Christian Bessiere, editor, Proceedings of the Twenty-Ninth International Joint Conference Artificial Intelligence, IJCAI-20, pages 1755-1762. International Joint Conferences on Artificial Intelligence Organization, 7 2020. doi: 10.24966/ijccal.2002/44 URL https://doi.. otaeliii.oiggggoo 10. 2092222934311 1/033/jjjai. /4300 Main track.
[76] Dani Yogatama, Yishu Miao, Gabor Melis, Wang Ling, Adhiguna Kuncoro, Chris Dyer, and Phil Blunsom. Memory architectures recurrent neural network language models. International Conference on Learning Representations, 2018. URL https://opperevieer net/forum?
SLFF
[77] John M Zelle and Raymond Mooney. Learning to parse database queries using inductive logic programming. In Proceedings of the national conference artificial intelligence, pages 1050-1055, 1996.
15

---

A Appendix
A.1 Sparse Coordinate Trees as Tensor Product Representations
This section shows that Sparse Coordinate Trees is the same as a TPR with the constraint that the role basis is the standard basis. TPRs define structural positions as role vectors Ti Rd,, and the content that fills these positions is defined by filler vectors Si E RR4, For a particular role and filler pair, the filler Ja is bound to the role r; using the tensor/outer product: fa 69 r; E RR xd, The representation of an entire structure is the sum over all N individual filler-role pairs: - Si @ ri E Rd xd. As shown in the previous two equations, the dimensionality of a single filler-role pair is equal to the dimensionality of an entire structure: both have dimensionality R xd., This means that a tree with only filled root node takes up the same memory as dense tree with every node filled. An important requirement for TPRs that the role vectors must be linearly independent; this ensures that filler can be unbound from role without introducing noise using the inner product: f, = =T] where (rz) 3 is the basis dual to {ra)= Previous work typically used randomly initialized and frozen orthonormal vectors to define the role basis. By defining our role vectors in a sparse manner as opposed to random initialization, we can greatly reduce the memory used by TPRs.
-i=1
Classic symbolic data structures grow in memory linearly with the number of filled positions. It is possible to replicate this behavior with TPRs by defining the role vectors to be the standard one-hot basis, which is orthonormal by definition. The i-th element of role vector is 1, and the other elements are When a filler and role vector are both dense, the resulting bound vector is also dense. When the role vector is one-hot, the resulting bound vector is 0 everywhere except for column i which corresponds the value in r.. By using a sparse tensor representation that only keeps track of dimensions that are not equal to O, we can reduce the memory usage of TPRs to linear growth that scales with the number of filled positions, like a classical symbolic data structure. This however forgoes a motivating desideratum for the design of TPRs, that roles (and not just fillers) have similarity relations that support generalization across structural positions.
We can additionally improve the efficiency by refraining from performing the outer product. Since we are not performing a tensor product, this technique is only implicitly Tensor Product Representation. Instead, we can keep the filler and role vectors in two aligned lists. A filler is bound to role by sharing an index in our aligned lists. This is equivalent to the binding and unbinding from classical dense TPRs without having to perform multiplication.
Since are not performing outer product, instead of storing sparse role vectors, we can simply store a role integer, where the integer corresponds to the one-hot dimension. We derive a tree addressing scheme based Gorn addresses [23]. In our scheme, addresses are read from right to left, giving the path from the root where a left- fifft-brncchhaccc is indicated by a 0 and a right-branch is indicated by a 1. We need a way to distinguish between leading Os and left-branches (c.g., 010 vs. 10), so we start our addressing scheme at instead of O. This indicates that all Os to the left of the left-most 1 are unfilled and not left-branches; the left-most and all preceding Os are ignored when decoding the path- aath-from-row from-root. Figure? 2 shows an example encoding of a tree in the sparse implicit approach.
We can compare the memory requirements of the Sparse Coordinate Tree encoding used in the sDTM to the memory requirements of the full TPRs used in the original DTM of Soulos et al. [67]. A TPR uses the same amount of memory regardless of the number of filled nodes. As with all sparse tensor formats, the memory savings arise when there are many zeros. In a dense tree where every node is occupied, the classical dense TPR approach is actually more efficient: the SCT's value list has the same total dimension as the classical TPR, but, in addition, the SCT encoding includes the list of filled-node addresses.
A.2
Agent Figure
See Figure 6.
A.3
Lexical Regularization Ablation
To see the importance of adding noise to our input embeddings as defined in Section 4.4, we show the performance of sDTM with and without this regularization in Table 4.
16

---

Append-
[i]
Pooling by Allendon
Tree 2
Traa 1
Differentiable Tree Interpreter
Operation Encoding"
Root Symbol Encading
Tree Encoding"
Tree Ercoding
2 Enooding
Tree Memory
1
layer
Operation Encoding"
Roal Symiba Enooding?
Encoding"
Enceding'
*(A)
a/u
Tree
Softmax
Softrax
Stip
Feedforward
Operation Logits
e/0
Operation x Tree Arg Logits
Muhtheed Attention!)
Wall
W
Symbol
Tree Encoding
Operation Encoding"
Roor Symbol Encoding?
Tree Encoding"
Tree Enooding?
Encoding
Enooding!
Ercoding
From presious Transformer layer
Figure 6: Adapted from Soulos et al. [67]. One step of DTM is expanded to show how the agent produces the input the interpreter. The interpreter then writes the output memory and encodes the output for the agent. Parts of the architecture with learnable parameters are indicated in yellow. The agent uses three linear transformations on top a standard Transformer encoder layer to parameterize the inputs to the interpreter. The superscript indicates the layer number and refers to parameters and activations that are exclusive this layer.
Table 4: Comparing sDTM's accuracy on SCAN 1-shot lexical OOD generalization with and without lexical regularization. We use LAUD embed the output sequence in tree.
With noise .87
Without noise
0.0
A.4 Dataset Preprocessing
We preprocessed GeoQuery according to the steps from Shaw et al. [58]. FOR2LAM and GeoQuery both contain non-binary trees, which we convert to binary form using Chomsky normal form. When a new node is inserted to make branch binary, we use the token <NT>, For output sequences with length embedded according left-aligned uniform-depth, make the single token the left child of new <NT> root node.
A.5 0-shot Lexical Test Generation
For both FOR2LAM and SCAN, introduce (-shot lexical tests. For FOR2LAM, do this by replacing every occurrence of 'x' in the test set with a new token 'z'. For the SCAN 0-shot set, we start with the i-shot lexical test set and remove the sample containing the 1-shot word 'jump'. We alter the output vocabulary to use the same tokens as the input vocabulary, since it is impossible for word level model to translate between input and output word without any exposure to that word.
A.6 DTM Training Details
When applicable, we adopt the hyperparameters from Soulos et al. [67]. Below we list the newly introduced hyperparameters and changes made existing parameters.
Soulos et [67] set the dimensionality of the embeddings to be equal the size of vocabulary. This works for the datasets with small vocabulary examined in the original paper. We keep this setting for
17

---

Table 5: Summary statisties for Activer+Logical. Mean and standard deviation accuracies are shown.
Model
Split
0-Shot Lexical
IID
Structural
Original DTM
1.0 0.0
1.0 0.0
1.0 0.0
sDTM sDTM (pruned k=1024)
1.0 0.0
1.0 0.0
1.0 0.0
1.0 0.0
1.0 + 0.0
.86 + .04
Table 6: Summary statistics for FOR2LAM and GeoQuery. Mean and standard deviation accura- cies are shown.
FOR2LAM
GeoQuery
Model
IID
0-shot lexical
IID
Length
Template
TMCD
sDTM
1.0+0.00
.31.11
.681.01
.194.01
.16:1.03
.35+0.0
Lctive++Logical, but set the embedding dimension to 64 for FOR2LAM, and 128 for GeoQuery and SCAN. We also changed the loss function from mean-squared error cross entropy.
For each new task, we need decide how many layers use for sDTM. We followed the heuristic of doubling the max tree depth for the models with sequence input and quadrupling the number of layers for tree input. This leads to 56 layers for FOR2LAM, 22 layers for GeoQuery, and 14 layers for SCAN.
attention 4.2 introduces new hyperparameters such as number of pooling heads and pooling key dimensionality, and we set the value of these to be the same as the Transformer hyperparameters for the agent. Tree pruning 4.3 introduces a new hyperparameter & for the maximum number of nodes to keep. In general, larger & is better but uses more memory. For Activet+Logical we set k 1024, for FOR2LAM k 1024, for GeoQuery A 2048, and for SCAN With the memory savings from SCT, pooling by multi-headed attention, and pruning, we increase the batch size from 16 to 64. We also increased the agent's 's model dimension 256 with 8 heads of attention due to the memory savings except for Activet+Logical where we matched the original hyperparameters.
Pooling by
256.
Random positional embeddings (RPE) also introduce a new hyperparameter for the max input integer, and we this to be double the max input length. This leads an RPE hyperparameter of 44 for GeoQuery and 18 for SCAN.
We noticed that randomly initializing and freezing our emhedding vectors essential for sDTM achieve 0-shot generalization on SCAN.
For the results, we reported the best run of 5 random seeds. Like DTM, sDTM suffers from high variance. Some runs get stuck local optima and fail to achieve moderate performance on the training set, which leads to poor performance the test sets. This is known issue with models that use superposition data structures, and reporting the best run over a number of random seeds has been previously used [76, 17].
A.7 DIM Summary Statistics
Mean and standard deviation accuracies shown in Tables 5, 6, and 7.
A.8 Baseline Training Details
NQG: Lotive++Loogial rule induction used the following hyperparameters: sample size=training set size, terminal code length=8, allow repeated nts=True. The terminal code length setting was
18

---

Table Summary statistics for SCAN. Mean and standard deviation accuracies are shown.
Model
Split
I-Shot Lexical
0-Shot Lexical
IID
Length
Template
MCD
sDTM (parse trees)
.8011.39
:514
.804.34
.341.30
.194.38
.02::001
sDTM (LAUD trees)
1.0=10.0
.70
.75::.22
.04::00
.84
0.0:10.0
DTM (parse trees)
0.0+-0.0
0.0+00.0
0.0++0.0
0.0++.00
0.0++0.0
0.0+0.00
obtained via grid search over the values 1, 8, 32. For the actual training of the model we follow the hyperparameters utilised by [69, 58). FOR2LAM used the same hyperparameters with the exception of sample size which had to be set to 1000 additional increases became computationally intractable. Even under these settings rule induction took 42 hours on a machine with 64gb ram. Writing the training set would take additional week of processing time, which considered computationally too expensive.
Transformer: We followed the same hyperparameters obtained via grid search from [67]. Specifically these are: 30,000 steps of which 1000 were warmup and linear learning rate decay; batch size 256; one encoder layer and three decoder layer each with hidden dimension of 1024 and two attention heads; the optimizer was Adam.
RU-Transformer: We followed the hyperparameters reported by [12]. These are: 128 dimension hidden size with 256 feedforward; 8 attention heads; 3 layers; batch size 256; trained using Adam with learning rate 10-3
A.9 Compute resources
All reported sDTM runs could processed on NVIDIA 16gh V100 GPUs. Depending on availability, we ran some seeds on 80gb H100 GPUs, but this is not necessary. The Transformer baselines were also run on NVIDIA 16gb V100 GPUs. NQG used NVIDIA 40gb A100 GPUs. The GPUs we used were hosted on internal cluster.
Designing our architecture involved many preliminary experiments that are not reported in the paper.
A.10 Dataset Statistics and Samples
Example input and output pairs are shown for Active<~Logical in Figure 7 FOR2LAM in Figure 8, GeoQuery in Figure 9, and SCAN Figure 5. The memory usage of DTM grows exponentially with tree depth, so we present the max depth of the datasets here:
Letive<+Logical: max tree depth 10
FOR2LAM: max tree depth
GeoQuery: max tree depth 16
SCAN: max tree depth 8
A.11 Licenses
Baselines:
DTM: Permissive 2.0
Transformer: BSD-3 (Pytorch implementation)
Trunnsosform::: MIT Licence
NQG: Apache 2.0
Datasets:
19

---

S
LF
NP
VP
V
ARGS
DET
N
V
NP
ate
NP
NP
the
dog
ate
DET
N
DET
N
DET
N
the
treat
the
dog
the
treat
Figure An input and output pair from Activer=l.oicaa.
<BEC>
ASSIGN
Dea
FF-0
<MMPyp
vASSiGh
ASSIGNG
<Eages
J.NT.
Figure 8: An input and output pair from FOR2LAM.
answer
intersection
capital
intersection
city
loc 2
what is the capital city of the largest state in the m0
largest
intersection
state
loc 2
m0
Figure 9; An input and output pair from GeoQuery.
20

---

GeoQuery: G.P2.0
SCAN: BSD
Activet+Logical: Permissive 2.0
FOR2LAM: Not public (no licence obtained through email request original authors)
21

---

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: At the end of the introduction, we outline the primary contributions of our paper along with the associated section where that content is available.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not 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 not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We address limitations of our approach in Section
Guidelines:
The answer NA means that the paper has no 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 a separate "Limitations" section 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 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 few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low 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 of 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 used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [NA]
22

---

Justification:
We provide mathematical descriptions of our model, but we do not introduce
any proofs.
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 referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof's provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results 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)?
Question:
Answer: [Yes]
The main content outlines our model and empirical setup. In Appendix A.6 we provide details for training our model, and in Appendix A.8 we outline details for training the baselines. Additionally, we plan to make our code and data open source at the time of publication facilitate reproducibility.
Justification:
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 a dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a 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 the 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 NeurlPS 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 to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results or way to reproduce the model (e.g., with an open- open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
23

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: plan to make our code and data open source the time of publication facilitate reproducibility.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm cc/
public/ Baallii/guiie///e Saaaidee/oodSuumissee semiisssiiopiyyyy 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 NeurlPS code and data submission guidelines (https: / //nips. wwtppcccc//ccccccccccccccccccclt gtwic//gg//////eieeieiiiccciise/ guw.de//ooeeuuumiiiiiccc wwweeoomiisisiiieoooooe wwwsssssssiiooooooooo for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is 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: The data splits are discussed extensively in Section 5. In Appendix A.6 provide details for training our model, and in Appendix A.8 we outline details for training the baselines.
Guidelines:
The answer NA means that the paper does 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: [No]
Justification: for our results, we report the best run across five random initializations. As discussed in Appendix A.6, neurosymbolic technique can have high variance, and this method of reporting results is common.
Guidelines:
The answer NA means that the paper does not include experiments.

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall 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.
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 errоrs is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results are out range (e.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: In Appendix A.9 we discuss the compute resources needed to run our experi- ments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well 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 into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: / /ttp///eerrpp.eeeee cc cc/ppbblic/Etiie httpaaice/thcccuieeeeeeeeee
Answer: [Yes]
Justification:
This research is upstream of any concrete applications. While there is always a risk of scientific research, we do not believe this work contains risks beyond general scientific research.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS 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., there a special consid- eration due to laws 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]
25

---

This research is upstream of any concrete applications. While there is always risk of scientific research, we do not believe this work contains risks beyond general scientific research.
Justification:
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to partieular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out, For example, it is legitimate to point out that 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 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 correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or 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 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 or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
This research is upstream of any concrete applications. While there is always a risk of scientific research, we do not believe this work contains risks beyond general scientific research.
Justification:
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
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We cited the papers that introduce the models and datasets that we use. Most of the models and datasets we used are publicly available. Appendix A. contains additional
information with regards to the licenses of each asset.
26

---

Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if 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: plan to make our code and data open source the time of publication to facilitate reproducibility.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing 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?
27

---

Answer:
[NA]
Justification:
Our paper does not involve crowdsourcing nor human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing 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 we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
28


Reviews:
[{"review_id": "BYNMPxr2wD", "reviewer": "Reviewer_bgti", "summary": "This work addresses the problem of compositional generalization in the domain of natural language processing. The authors highlight that incorporating tree structures into a models representation space is important for achieving compositional generalization. To this end, the authors build upon a recent method for incorporating such structure by extending the method such that it is 1. significantly more parameter/memory efficient and 2. able to handle seq2seq task opposed to just tree to tree task. The authors test their method on various natural language task and show superior compositional generalization performance across several metrics relative to baseline methods as well as improved efficiency relative to the method they build upon.", "questions": "* What is the primary purpose of the experiments in Sections 5.3-5.5?\n\n&NewLine;\n\n* Do the authors have intuition for how well sDTM could scale to more complex models/datasets? In particular, given its compute efficiency over DTM?\n\n&NewLine;\n\n* Do the authors envision that sDTM could be applied in task outside of natural language, e.g. visual reasoning or planning task?", "limitations": "This paper does not contain an explicit limitations section, however, the authors provide a transparent discussion about some limitations of sDTM in Section 5 and in the Conclusion section.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* This paper addresses an important problem; namely, closing the gap between human's and machine's ability to generalize compositionally in natural language task.\n\n&NewLine;\n\n* The paper is very well written, well structured, and easy to understand.\n\n&NewLine;\n\n* Section 2 provides a solid review of prior works and does a good job contextualizing the authors contribution relative to prior works.\n\n&NewLine;\n\n* The authors method yields promising empirical results both in terms of memory efficieny and performance relative to existing baselines e.g. Transformers.\n\n&NewLine;\n\n* The authors are upfront and transparent when their method underperforms in Section 5.4 and aim to provide potential explanations for why this may be occurring.", "weaknesses": "__1.__ I found the experiments section to be a bit unclear in its focus. As I understand, one of the core points of sDTM and thus the paper, is that sDTM is significantly more memory/compute efficiency than DTM. While the authors compare these two methods in terms of efficiency and performance in 5.2, such an experiment does not exist for the tree2tree task in 5.3. Consequently, I am a bit confused on the purpose of the experiments in 5.3 given the main message of this work. \n\n&NewLine;\n\nSpecifically, the current point seems to be to show that sDTM outperforms baseline methods on FOR2LAM. Given that sDTM is an extension of DTM, the scores for sDTM in isolation do not seem particularly meaningful without a relative comparison to DTM as was done in 5.2. Please let me know, however, if there is something I am missing here.\n\n&NewLine;\n\nFor the same reasons, I think the experiments in 5.4 and 5.5 would also benefit from reporting scores for DTM alongside sDTM. I suppose the original DTM method cannot be directly applied since these inputs involve sequences, however, if I understand correctly, it seems the same technique to deal with sequence task in sDTM can be applied to DTM.\n\n&NewLine;\n\n$\\newline$\n\n&NewLine;\n\n__2.__ It would be important to understand the compositional generalization benefits obtained by sDTM over e.g. Transformers on more large scale models/datasets, however, I also recognize that such a study could be out of the scope of this work.\n\n&NewLine;\n\n$\\newline$\n\n&NewLine;\n\n__3.__ There are some cases in which sDTM does not offer benefits over existing baselines as reported in Section 5.4, however, the authors are upfront about this in the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Reviewer bgti\nThank you for the time you spent to understand our submission and provide valuable feedback! Addressing your concerns will make our paper substantially stronger. We are pleased that you found that our paper “addresses an important problem”, is “very well written”, contextualizes our contribution in relation to prior work, and “yields promising empirical results”. Below we will address the weaknesses and questions that you highlighted.\n\n## Weakness\n1. Our original submission did not adequately address the significance of each experiment, and we failed to explain when it is possible to compare DTM and sDTM. As you and other reviewers point out, we only directly compare sDTM and DTM in Section 5.2. The reason that we did not include DTM in Section 5.3, and this is a point we will be sure to highlight in the camera-ready version, is that DTM cannot fit a batch size of 1 into memory on FOR2LAM. Theoretically, DTM should be able to solve FOR2LAM, but the inefficiencies with regard to exponential growth due to tree depth (lines 111-115) make it impossible in practice. The purpose of Section 5.3 is to show that sDTM, which has the same theoretical guarantees as DTM but is practically more efficient, can scale up and solve FOR2LAM.\n\\\n\\\nYour understanding of the separation between our contribution of seq2tree and seq2seq and architectural improvements in sDTM is correct. The same technique to process sequences that we introduce alongside sDTM can also be applied to DTM. GeoQuery has deeper trees than FOR2LAM, which means that it is also not feasible to test DTM on GeoQuery. However, it is practical to train both sDTM and DTM on SCAN. We will run the experiment to test DTM on SCAN and will update the camera-ready version with these results.\n\\\n\\\nIn order to make the purpose of each experiment clear, we propose to change the subheaders in the Results section of the camera-ready version to better reflect the significance of each experiment, with the associated dataset in parentheses. **Section 5.2: Performance Regression (Active$\\leftrightarrow$Logical)** confirms that sDTM does not worsen DTM's original performance. **Section 5.3: Scalability (FOR2LAM)** investigates a tree2tree transformation task that DTM cannot handle as explained in the previous section of this rebuttal. **Section 5.3: Seq2Tree (GeoQuery)** introduces the change of processing a sequence as input instead of a tree, and **Section 5.4: Seq2Seq (SCAN)** adds an additional modification of sequence outputs.\n\n2. We hope that our more efficient implementation of DTM will allow us in future work to compare the compositional generalization benefits of sDTM and Transformers on larger datasets and models. In this work, we focused on making it practical to test DTM on a wider variety of tasks by making it much more efficient and capable of processing sequence inputs and outputs. As mentioned in the previous section, the original DTM could not be tested on FOR2LAM and GeoQuery because it was too inefficient to fit a batch size of 1 into the available memory. sDTM provides a base for us to approach larger datasets in future work.\n\n3.  While we would be excited if sDTM was the best model across every split and every dataset, Figure 1 shows that sDTM's improvement over baselines comes when results are considered as a whole. As we note in our general response to reviewers, we aim to present results across a breadth of distributional shifts to help shed light on what kinds of generalization different architectures excel at.\n\n## Questions\n1. Please see our response to Weakness #1 above.\n2. Please see our response to Weakness #2 above.\n3. With regard to other modalities, we hope that sDTM can be applied to any task that can benefit from hierarchical representation and processing. As you mention, many types visual reasoning and task planning, such as scene understanding and goal decomposition into subgoals, can be formulated as hierarchical problems. The challenge here will be going from raw input such as an image into a tree-structured representation, as well as managing this encoding in a way that generalizes.\n\n## General\nPlease let us know if you think that our submission would benefit from an explicit Limitations section.\n\\\n\\\nWe hope that we have addressed your questions and concerns. If you have any additional questions, or we did not address any of your original points, please let us know. We are committed to continuously improving our paper and appreciate your feedback. If you find that our changes in response to your feedback improved our submission, please consider increasing your support for our paper.\n\\\n\\\nThank you again for your time and consideration. We look forward to hearing back from you.", "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": "ZhlcISOICF", "reviewer": "Reviewer_Hmrt", "summary": "The paper proposes a novel way of representing sparse trees where nodes have vector attributes in a denser, tensorised format which they call Sparse Coordinate Trees (SCT). Essentially, the crucial component for SCTs is to represent the indices of the nodes according to their topological ordering, allowing for all nodes to be represented by a vector of indices and a tensor of attributes. Additionally, the authors also show how some traditional operations on trees, such as taking left/right subtrees or constructing a new tree from left/right branches, can be efficiently implemented with simple indexing or bitshifts when working on the binary representation of the node indices. Moreover, these operations can be parametrised in a differentiable way using modern machine learning models, such as transformers, opening the door to learning the structure of a SCT\n\nThe next contribution is then to use SCT to extend an existing neurosymbolic [1, 2] framework called Differentiable Tree machines (DTM) to be able to work with sequence data (seq2tree and seq2seq tasks) instead of just tree data (tree2tree tasks). While maintaining the semantics of DTM, the use of SCT as an inference engine is also shown to be more memory and parameter efficient. Finally, the theoretical claims of the paper are supported by a strong suite of four benchmarks.\n\n[1] Garcez, A. D. A., & Lamb, L. C. (2023). Neurosymbolic AI: The 3 rd wave. Artificial Intelligence Review, 56(11), 12387-12406.\n\n[2] Marra, G., Dumančić, S., Manhaeve, R., & De Raedt, L. (2024). From statistical relational to neurosymbolic artificial intelligence: A survey. Artificial Intelligence, 104062.", "questions": "Apart from the concerns raised in the previous section, here are a couple more specific questions:\n\n1. What is the intuition behind only using a single learnable parameter for the query vector? (lines 205-206)\n\n2. While it is nice to see that sDTM generally does perform better than transformers in terms of OOD generalisation, I am left wondering if it also can not be prone to the same pitfalls as transformers as SCT and hence sDTM do utilise transformers internally to construct trees. Could you elaborate on this as it could be an important limitation of this paper? As experimental support for this limitation, the lacking performance in the experiment of Section 5.4 could be evidence. Additionally, the imperfect score of 0.61 in Table 2 can also be seen as evidence for this, given the rather simple nature of \"replacing the name of a variable\".\n\n3. Experimental questions:\n     + Why is the original DTM only present in Table 1 and not Table 2? Both relate to tree2tree tasks where DTM should also be applicable if I understand correctly.\n     + Lines 283-285: How much of the 20% memory reduction is due to the use of pooling by attention and how much is due to using SCT?\n     + Table 2: sDTM gets a score of 0.61 on the 0-shot test set where one variable name is consistently changed to another. Do all test set occurences contain the variable x that is changed to z?\n     + In general, the evaluation metrics should be explained a bit more in detail. For example, what does it mean for a FOR2Lam translation to be correct? The translated AST is exactly the same as the target, or equivalent in some way?\n     + Lines 321-322: the small dataset is used as argument for the lacking performance of sDTM compared to other methods, but do those other methods not also suffer from the small dataset? Transformers are known to be rather data-hungry, so I would still have expected sDTM to outperform them at least in this task. Do you have some deeper intuitions as to why this is not the case?\n     + In general, why the choice of the best performance out of 5 runs? While means and standard deviations are certainly not always ideal, aggregate and variability metrics are still more insightful to gauge the consistency of the tested methods. If one does not want to use means and standard deviations/errors because of their distributional assumptions, medians and quantiles are a good solution.\n     + It seems like there are more neurosymbolic methods that could be applied to the discussed tasks, such as those mentioned in the related work in lines 97-98. Why the choice for only NQG?\n\n4. I am curious about the overall training times for all methods, to see if sDTM requires substantially more time to train or not. Can you comment on this please?\n\nIn general, I do give a more positive rating to this paper as its presentation is excellent, its contribution is interesting and its experimental evidence is quite convincing. I will gladly further increase my score if the authors can answer my concerns.", "limitations": "I believe limitations are sufficiently addressed, as the conclusion specifically mentions that sDTM still struggles with some OOD generalisation tasks. However, some potentially limiting factors, such as training times, are not immediately clear.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "1. The paper is very well written and easy to follow. The motivation for the ideas in the paper and their explanations are clear.\n\n2. The suite of experiments is quite extensive, covering the three kinds of tasks discussed in the paper (tree2tree, seq2tree, seq2seq) on recognised datasets. Apart from the number of experiments, the advantages of sDTM compared to the chosen baselines are also clear in most cases.\n\n3. The idea of the paper is simple, but elegant and it is easy to see why it can give substantial improvements in terms of efficiency. It also nicely allows for the incorporation of modern machine learning models like transformers. While I am unsure about the overall impact of the work as it seems there are many questions left to answer, the questions and answers about generalising beyond mere i.i.d. training and test cases are crucial and tie in with the current rise of neurosymbolic AI.", "weaknesses": "While I overall enjoyed reading this interesting paper and appreciate the provided insights, I do have some comments and questions:\n\n1. A lot of related work is properly and extensively discussed in Section 2, yet I do believe a series of references might be missing. There are many more general neurosymbolic frameworks that use neural nets to parametrise symbolic components. Some are based on fuzzy logic [1], while others use probabilistic logic [2, 3], in contrast to being based on tree structures. For the special case of sequences, a system based on stochastic grammars also exists [4]. Even more, some of these systems go further in allowing neural embeddings to be present within the logical system [5, 6], similarly to how nodes in the tree are composed of their vectors of attributes. It is true that many of these systems have not focused on structure learning and do assume some prior knowledge, which is not a prerequisite for the proposed method. Although this area of \"structure learning\" (or learning a *program* as line 157 puts it) is an active area of research [7, 8]\n\n2. In section 3.2 it is shown that the operations *left*, *right* and *cons* can be implemented very efficiently as tensor operations. However, not much is said about the additional operations of *conditional branching* and *equality-testing*. It is mentioned that the five operations together are Turing complete, but only the first three seem to be used and nothing is said about an implementation of the last two for SCT.\n\n3. sDTM extends DTM to tasks different from just tree2tree tasks, but it is not completely clear how much of this is due to the use of SCT. For example, to allow even sDTM to deal with seq2seq tasks, the authors do need a hardcoded translation from output trees to sequences. I wonder if a similar hardcoding could not have been used for input sequences to trees, allowing vanilla DTM to deal with the same coverage of tasks, albeit with a less flexible input encoding. \n\n4. Most of the experimental results are promising, but some results did raise some questions (see below in the questions section). It would also be nice to see some examples of some of the datasets, even if only in the appendix, to make it more tangible what the input and output is of the experimental tasks.\n\n5. As briefly mentioned previously, the true impact of this work remains hard to guess. There is surely a lot of promise in neurosymbolic methods in general and the proposed SCTs and sDTM do show improved generalisation performance by learning both neural and symbolic components *from scratch* and *from data*. However, the use of *only* tree structures could prove limiting for applications with more intricate dependencies.\n\nSmaller concerns:\n\n1. Section 4.3 talks about how pruning can be used by keeping the top-$k$ nodes. However, it is unclear whether this can be done during training, since the top-$k$ operation is not differentiable.\n\n2. On line 197 it is stated that attention is permutation invariant, yet this is not completely correct. Attention is invariant to permutations of the keys and values and only *equivariant* to permutations of the queries. It would be good to make the distinction clear to avoid confusion.\n\n[1] Badreddine, S., Garcez, A. D. A., Serafini, L., & Spranger, M. (2022). Logic tensor networks. Artificial Intelligence, 303, 103649.\n\n[2] Yang, Z., Ishay, A., & Lee, J. (2020, July). NeurASP: Embracing Neural Networks into Answer Set Programming. In 29th International Joint Conference on Artificial Intelligence (IJCAI 2020).\n\n[3] De Smet, L., Dos Martires, P. Z., Manhaeve, R., Marra, G., Kimmig, A., & De Readt, L. (2023, July). Neural probabilistic logic programming in discrete-continuous domains. In Uncertainty in Artificial Intelligence (pp. 529-538). PMLR.\n\n[4] Winters, T., Marra, G., Manhaeve, R., & De Raedt, L. (2022, June). Deepstochlog: Neural stochastic logic programming. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 36, No. 9, pp. 10090-10100).\n\n[5] Rocktäschel, T., & Riedel, S. (2016, June). Learning knowledge base inference with neural theorem provers. In Proceedings of the 5th workshop on automated knowledge base construction (pp. 45-50).\n\n[6] Maene, J., & De Raedt, L. (2024). Soft-unification in deep probabilistic logic. Advances in Neural Information Processing Systems, 36.\n\n[7] Shindo, H., Nishino, M., & Yamamoto, A. (2021, May). Differentiable inductive logic programming for structured examples. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 35, No. 6, pp. 5034-5041).\n\n[8] Muggleton, S. (1991). Inductive logic programming. New generation computing, 8, 295-318.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Reviewer Hmrt\nThank you for the extensive feedback you provided on our submission! Addressing your questions and the weaknesses you identified will significantly strengthen our work. We are pleased that you found our work “very well written”, “the suite of experiments is quite extensive”, and “the idea of the paper is simple, but elegant”. Below we will address the weaknesses and questions that you identified.\n\n## Weaknesses\n1. We are grateful for the additional references that you provided. We will amend the Related Work section in the camera-ready version to include a subsection on Neurosymbolic Computation with the references you provided, as well as additional citations.\n2. Thank you for catching this oversight. Conditional branching and equality-testing are the control flow mechanisms for how to sequence the structural operations as well as argument selection. In this regard, conditional branching and equality-testing are implicitly parameterized by the Agent using a Transformer. In numerous approaches to neural program synthesis, neural networks are used to parameterize program control flow (e.g. Nye et al (2020), where networks generate symbolic rule sequences). Unlike most of that work, however, in our approach the synthesized programs are themselves differentiable. We will update the camera-ready version to make this contribution of our work clear.\n\n3. Please see our response to this in the **sDTM vs DTM** section of the Global Rebuttal.\n\n4. Thank you for this suggestion. We included an example sample from SCAN in Figure 5 and will add addition samples across the datasets to the Appendix in the camera-ready version.\n\n5. Extending data structures in superposition to graphs is an active area of research. We focused on trees given their importance in language processing, but we would like to generalize the techniques in our paper to graphs as well. Many data structures such as lists, stacks, and queues can be implemented using left, right, and cons, so it is possible for sDTM to succeed on tasks that would be better modeled by these data structures. This is an interesting point that we intend to investigate in follow-up work.\n\nSmaller Concern 1: top-k selection is also done during training. Top-k selection can be viewed similarly to deterministic channel-wise dropout. As such, when a node is dropped, the node does not contribute to the output, and thus it will have a gradient of 0. We will include additional text in the camera-ready version to make sure that it is clear how top-k selection works with regards to training.\n\nSmaller concern 2: this is a good point, thank you for your attention to detail! We will update the text to make it clear that attention is permutation equivariant.\n\n## Questions\n1. The sentence that you pointed out is written incorrectly. We have n_head query vectors each of dimension d_key. We will correct this in the camera-ready version. Thank you for spotting this typo.\n2. Good point, and this ties in to point 2 you raised in the Weaknesses section. As long as the Transformer can make the correct control flow predictions, what operations to perform on what trees in memory, the transformation will have good generalization. However, sDTM can still fail to generalize correctly when the underlying Transformer that powers the agent does not make correct control flow predictions. We address some concerns about model performance in the **Performance concerns** section of the Global Rebuttal.\n\n3. Experimental questions\n    1. Please see our response to this in the **sDTM vs DTM** section of the Global Rebuttal.\n    2. This is a good question, and we don't have a definitive answer just yet. SCT only provides memory savings when nodes are empty. DTM with more layers will eventually lead to fully dense trees, in which case all of the memory savings will be due to pooling by attention. However, in this specific example, the early sparse trees will account for some of the memory savings.\n    3. Yes, every test set sample contains a variable x that is changed to z in the 0-shot test set.\n    4. The evaluation metric that we use is Exact Match Accuracy. We will update the paper to clarify this.\n    5. Please see our response to this in the **Performance concerns** section of the Global Rebuttal\n    6. We find that sDTM is prone to getting stuck in local optima and followed previous papers in reporting the best run, as described on lines 982-986 in the Appendix. We acknowledge that summary statistics are still helpful. We want to continue reporting the best performance since this highlights the theoretical capabilities of our model, but we will also include summary statistics in the updated version.\n    7. We picked NQG as our signature hybrid neurosymbolic model since it was applied to different distributional shifts and datasets. Most other hybrid neurosymbolic models are heavily tied to a specific dataset or distribution shift, and we did not have the resources to adapt models for each task and distribution shift.\n4. Thank you for pointing out this oversight, we should have included information about the training time for each architecture and will rectify this. On Active$\\leftrightarrow$Logical, 20k steps took DTM 11 hours, sDTM 6 hours, and our Transformer 2 hours. While the forward and backward speed of Transformer is still much faster than sDTM, it uses highly optimized CUDA kernels, whereas sDTM has a lot of room for improvement.\n\n## General\n\nPlease let us know if you have any additional questions or concerns. If we addressed your questions and concerns, please consider increasing your score. We truly appreciate the time that it must have taken to provide such a careful analysis of our submission. Thank you!", "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": "85vsCXgrUA", "reviewer": "Reviewer_mbkf", "summary": "Authors propose a new representation that they call Sparse Coordinate Trees. When applied to Differentiable Tree Machines, they make computation much more parameter and memory efficient. Due to clever design, the SCTs allow for much more efficient tree operations by bit-shifting, indexing, and addition. Because the tree will naturally become very dense, they apply pruning to make it more sparse. They also propose how to adapt it for sequential inputs and outputs, rather than in tree-form.\n\nIn the experimentation section, they provide results on IID, zero-shot, one-shot, structural / length, and template tasks to test generalization, showing that in some ways these methods outperform previous work.", "questions": "A) in line 306, you say the variants score 0.03%, however in Table 2, they have .03 -- do you mean 3% or .0003? Or are the values in the table truly in percent, and the method is just getting 1%?\n\nB) Do I understand correctly that in Table 3, sDTM performs the worst of all metrics on all 4 tasks?", "limitations": "Limitations are adequately addressed.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "A) Professional and clear writing\n\nB) The number of parameters is clearly reduced from the original DTM\n\nC) The memory usage is reasonably reduced, and very reduced for the pruned version\n\nD) Operations are quite a bit more efficient", "weaknesses": "A) It would be clearer if there was a better description of what the left, right, and cons functions are intended to accomplish, as this is quite central to the methods\n\nB) There is a lot of extra space in the graphs and 5 runs--adding standard deviation would be nice\n\nC) In Table 1, I am not fully convinced this dataset presents a fitting challenge. The IID are already at 1.0 for almost every method, providing no meaningful distinction between them (although on its own this is maybe fine, as the OOD tasks are the focus). However, both OOD sets go from primarily 0% in the previous works to 100% in this work--not only does it make it seem like the task is very easy once attempted, but it also makes it very difficult once again to differentiate between methods.\n\nD) The only comparison to DTM is in Table 1--aside from lowering resource consumption, it is not clear if the methods have any performance difference (and as pointed out in C, it is not clear if they are truly equivalent or the dataset is just too easy). DTM should really be included in the other experiments. That way, it is clear if sDTM has added performance or just implementation efficiency. If it is just efficiency, then more experiments showing time, memory, parameters, etc would be more fitting than many separate results.\n\nE) Overall, the space is not well used (lots of white space, especially in experiments). It would be better if this were used to showcase more in the paper.\n\nF) Method consistently shows bad performance on MCD (worst of all 4 methods in Table 3, very bad in Table 4)\n\nG) Same as F, but for length experiment\n\nH) It is inconsistent where / when the different tasks are presented. e.g. sDTM seems to be good at 0-shot lexical and structural, but structural is only shown in Table 1. If this is where it is good, it would be much more interesting to see more of that task, than to see MCD in two places (Table 3 + 4), even though sDTM is consistently bad at these tasks.\n\nMy primary concerns are \n1) I'm not fully convinced on the novelty, because how I understand, it is mostly a more efficient version of DTM, but the experiments focusing on this are very limited and it is also not compared much to DTM in terms of performance (see C, D, E)\n\n2) the results are not great (see C, F, G). In some tasks the method underperforms across the board (length, MCD), and in others where it is good, there is a shortage of results (see H)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Reviewer mbkf\n\nThank you for the time you spent reviewing our paper. Addressing your feedback will make our submission much stronger.\n\n## Weaknesses\nA. We will make sure to improve the motivation for using left, right, and cons in the camera-ready version. The design of DTM was motivated by the fact that the vast majority of classic symbolic AI was carried out in Lisp, using binary trees as the universal data structure, and using left, right, cons as the complete set of universal structural operators (literally Turing-universal when deployed with the control operation of conditional branching on testing for symbolic equality, as noted in the paper on lines 141-144). This generality means DTM and sDTM are potentially applicable to the huge range of AI tasks previously solved with Lisp.\n\nB. We acknowledge that Table 1 and Table 3 both have whitespace. We will use the whitespace in the tables to include summary statistics about the five runs in the camera-ready version. Can you please let us know where you see excessive whitespace in other figures and tables? Additionally, we experimented with a vertical version of Figure 2 to try and reduce whitespace. The vertical version is available in the PDF attached to our global rebuttal. We would be grateful to know whether you think that this design is a better use of space.\n\nC. We are a bit confused by this comment. Highlighting that some models go from 100\\% IID performance to 0\\% OOD performance is a signature metric in compositional generalization. In addition to Table 1, we find a similar pattern on FOR2LAM (Table 2), SCAN (Table 4). This pattern is also present in other compositional generalization tasks such as COGS, PCFG, and CFQ. If this observation does not address the issue, we would appreciate a clarification of the problem we should address.\n\nD. This point was also mentioned by other reviewers, and it is clear to us that we did not provide adequate explanation for why we did not test DTM on FOR2LAM, GeoQuery, and SCAN. Please see our response to this in the **sDTM vs DTM** section of the Global Rebuttal.\n\nWe appreciate your point that we should emphasise the efficiency gains of sDTM. In addition to parameter and memory efficiency, sDTM is also almost twice as fast as DTM, a point that we did not highlight in the submission. We will correct this in the camera-ready version so that the efficiency improvements of sDTM are better explained.\n\nE. If you care to let us know where you find there is excessive whitespace, we would appreciate it, and would take steps to eliminate it. In order to fit within the NeurIPS style guidelines, there is only so much we can do about whitespace around Tables. We have much more control about whitespace in Figures and are happy to update any figure that you mention as poorly using space.\n\nF. MCD distribution shift is one where we did not find benefits over Transformer and RU-Transformer. We address these limitations in the Conclusion on lines 344-347, where we also highlight that despite the poor performance on MCD shifts, our model performs well in comparison to baselines across the widest variety of distributional shifts.\n\nG. We grouped structural and length generalization together to highlight that generalizing to novel linear positions can also be viewed as generalizing to novel structural positions in a latent parse tree. As shown in Figure 1, our model has the best overall performance on length/structural distributional shifts. One potential area for this confusion is the performance of sDTM on SCAN where the model performs significantly better when the output strings are parsed in a meaningful way.\n\nH. Please see our response to this in the **Layout of the experimental results** section of the Global Rebuttal.\n\nOne of the goals of our submission is to highlight distributional shifts and how different models perform differently across them. With this goal in mind, we thought that it was important to include results for sDTM on MCD shifts even though sDTM's performance is disappointing.\n\n### Primary Concerns\n1. We failed to explain in our submission that DTM is unable to train on FOR2LAM and GeoQuery. We hope that our explanation in the **sDTM vs DTM** section of the Global Rebuttal adequately highlights the extent to which sDTM provides drastic efficiency improvements. Our response to Weakness H also explains how each experiment is associated with a novel contribution from our work.\n2. We would like to reiterate that our results illuminate how different models, even ones designed for compositional generalization, perform differently across different datasets and distributional shifts. While NQG has good 1-shot lexical generalization accuracy, we found that it has no 0-shot generalization accuracy. Additionally, while NQG has perfect length generalization on SCAN, it does not outperform a Transformer on the GeoQuery length split and has 0\\% accuracy on the Active$\\leftrightarrow$Logical structural split. We hope that sDTM’s performance when considered across all of the datasets and splits in our submission highlights our contribution.\n\n## Questions\nA. Thank you for catching this typo, line 306 should read 3\\% and not .03\\%. Our model scores 100\\% IID and 61\\% on 0-shot lexical generalization.\n\nB. Yes, we included results of GeoQuery to show how sDTM and the baselines all struggle on this task. Please see our response to this in the **Performance concerns** section of the Global Rebuttal.\n\n## General\n\nPlease let us know if we did not adequately address any of your questions or concerns. We are committed to engaging with you during the discussion period to continue improving our paper. If you find that our changes in response to your feedback improved our submission, please consider increasing your rating for our paper.$\\newline\\newline$\nThank you again for your time and consideration. We look forward to hearing back from you.", "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:
# Global Rebuttal
We thank all of our reviewers for their careful analysis of our work. In this global response, we highlight points shared by multiple reviewers.

First, we are excited by the kind comments that reviewers provided concerning our paper. All three reviewers found our paper to be clear, easy to understand, and well written. They also highlighted the empirical performance and computing efficiency benefits of our work compared to the original DTM, especially in terms of parameter count and memory usage. We realized that in addition to the benefits that the reviewers highlighted, we failed to describe the speed benefits of sDTM over DTM. Due to the much smaller number of parameters and activation dimensions, sDTM is also much faster than DTM. On Active$\leftrightarrow$Logical, DTM takes 11 hours to to train for 20k steps, whereas sDTM takes 6 hours. We will update the camera-ready version of our paper to include empirical results showcasing the speed improvements of sDTM vs DTM. 

The primary feedback across reviewers was the need for greater clarity about the relationship between the original DTM and our proposed sDTM including a more thorough comparison of the architectures. Reviewers also asked for clarification with regard to the importance of each experiment in our Results section. In the sections below, we address these two issues and explain the changes we will make to our work for the camera-ready version informed by your feedback.

## sDTM vs DTM
We agree with reviewers that since sDTM is introduced as a more efficient version of DTM, full results comparing these two techniques are essential. It was an oversight not to include more direct comparisons of sDTM and DTM, and to explain why such a comparison is not possible on certain datasets due to the limitations of the original DTM.

In addition to the representational change (Sparse Coordinate Trees Section 3) and architectural change (pooling by attention Section 4.2) to go from DTM to sDTM, we also contributed an orthogonal technique to process sequence inputs and outputs (Section 4.5). We did not adequately isolate these orthogonal contributions by comparing sDTM and DTM on sequence inputs and outputs. As the reviewers pointed out, only Section 5.2 (Active$\leftrightarrow$Logical) contains a comparison between the original DTM and our proposed sDTM. In the camera-ready version, we will also report results for the original DTM on the seq2seq task SCAN (Section 5.5).

We did not test the original DTM in Section 5.3 (FOR2LAM) and 5.4 (GeoQuery) as the original DTM is so inefficient as to be impossible to run on our available hardware; a batch of only a single sample from these datasets causes an out-of-memory error on a 16gb V100 GPU. To put this in perspective, sDTM is able to process batches of 64 samples on the same GPUs, which exemplifies the dramatic efficiency benefits of sDTM. DTM cannot practically be run on FOR2LAM and GeoQuery because of the max tree depth of samples in these datasets. As explained on lines 111-115, DTM's memory requirement grows exponentially with the max tree depth and quickly runs into performance issues. The maximum tree depth for Active$\leftrightarrow$Logical, SCAN, FOR2LAM and GeoQuery are respectively 10, 8, 14, and 16. We will update the camera-ready version of our paper to explain the absence of DTM results on FOR2LAM and GeoQuery, as well as to include a table in the Appendix with tree depth statistics for all the datasets.

## Layout of the experimental results
Reviewers also sought clarity in how each individual dataset and experiment contributes to our overall contributions. To make the relationship between each experiment and our contributions more clear, we will change the subheaders in the Results section of the camera-ready version to better reflect the significance of each experiment, with the associated dataset in parentheses. **Section 5.2: Performance Regression (Active$\leftrightarrow$Logical)** confirms that sDTM does not perform worse than DTM. **Section 5.3: Scalability (FOR2LAM)** investigates a tree2tree transformation task that DTM cannot handle as explained in the previous section of this rebuttal. **Section 5.3: Seq2Tree (GeoQuery)** introduces the change of processing a sequence as input instead of a tree, and **Section 5.4: Seq2Seq (SCAN)** adds an additional modification of sequence outputs.

## Performance concerns
Multiple reviewers pointed out that sDTM does not achieve state-of-the-art performance across all tasks, with relatively weak performance on GeoQuery (Section 5.4). While we would be excited if sDTM was the best model across every split and every dataset, we want to remind reviewers that the results should be considered as a whole, as exemplified by Figure 1.

It is worth noting that there is substantial room for improvement across every model on GeoQuery. (s)DTM is proposed to complement generic similarity-based generalization (already offered by Transformers) with compositional-structure-based generalization. In tasks lacking sufficient opportunities for compositional generalization, DTM will have limited value to augment generic transformer-style generalization. It appears that GeoQuery is such a task, because the strongly compositional symbolic methods of NQG fail. It is possible that with sufficient data, GeoQuery's latent compositional structure could be identified by NQG and DTM, but the released GeoQuery dataset has only on the order of 500 training examples. Given all methods perform well below ceiling on GeoQuery (including on the IID split), we refrain from drawing substantive conclusions based on minor differences in accuracy on this single task in isolation from the rest of our results. We will update the text to clarify DTM's performance on GeoQuery.

We thank the reviewers again for the time that they dedicated to improving our submission. By responding to their feedback, we feel that our paper is much stronger and understandable.

Meta-review: The paper addresses a relevant and significant problem, i.e. how to improve OOD performances in a neural network (in this case in the NLP domain) mainly exploiting the compositional property of symbolic systems. In fact, the combination of neural and symbolic systems (Neurosymbolic Systems) have been studied since the 90', looking for the ``right'' way to combine these two technologies. This paper contributes to the advancement in this field by introducing a new technique for representing trees in vector space called Sparse Coordinate Trees, enabling the definition of structural operations useful for efficiently handling seq2seq task. 
Especially after rebuttal, all reviewers agreed that the contribution of the paper is technically solid and significant. The authors are encouraged to embed in the final version of the paper all reviewers recommendations.
Decision: Accept (spotlight)