Beam Tree Recursive Cells
Authors: Jishnu Ray Chowdhury
Cornelia Caragea
Venue: Submitted to ICLR 2023 (2023)
Keywords: Recursive Neural Networks
RvNNs
length generalization
systematicity

Abstract: Recursive Neural Networks (RvNNs) generalize Recurrent Neural Networks (RNNs) by allowing sequential composition in a more flexible order, typically, based on some tree structure. While initially user-annotated tree structures were used, in due time, several approaches were proposed to automatically induce tree-structures from raw text to guide the recursive compositions in RvNNs. In this paper, we present an approach called Beam Tree Recursive Cell (or BT-Cell) based on a simple yet overlooked backpropagation-friendly framework. BT-Cell applies beam search on easy-first parsing for simulating RvNNs with automatic structure-induction. Our results show that BT-Cell achieves near-perfect performance on several aspects of challenging structure-sensitive synthetic tasks like ListOps and also comparable performance in realistic data to other RvNN-based models. We further introduce and analyze several extensions of BT-Cell based on relaxations of the hard top-k operators in beam search. We evaluate the models in different out of distribution splits in both synthetic and realistic data. Additionally, we identify a previously unknown failure case for neural models in generalization to unseen number of arguments in ListOps. We will release our code.

Under review as a conference paper at ICLR 2023
BEAM TREE RECURSIVE CELLS
Anonymous authors
Paper under double-blind review
ABSTRACT
Recursive Neural Networks (RvNNs) generalize Recurrent Neural Networks (RNNs) by allowing sequential composition in a more flexible order, typically, based on some tree structure. While initially user-annotated tree structures were used, in due time, several approaches were proposed to automatically induce tree- structures from raw text to guide the recursive compositions RvNNs. In this pa- per, we present an approach called Beam Tree Recursive Cell (or BT--Cell) based on a simple yet overlooked backpropagation-ffienddd beam search easy-first parsing for simulating RvNNs with automatic structure- induction. Our results show that BT-Cell achieves near-perfect performance on several aspects of challenging structure-sensitivee synthetic tasks like ListOps and also comparable performance realistic data to other RvNN-based models. We further introduce and analyze several extensions of BT--Cell based on relaxations of the hard top-k operators in beam search. We evaluate the models in different out of distribution splits in both synthetic and realistic data. Additionally, we identify a previously unknown failure case for neural models in generalization to unseen number of arguments ListOps. Code is in the supplementary.
framework. BT-Cell adapts
INTRODUCTION
In the space of sequence encoders, Recursive Neural Networks (RvNNs) can be said to lie some- where in-between Recurrent Neural Networks (RNNs) and Transformers in terms of flexibility.
While vanilla Transformers show phenomenal performance and efficient scalability on variety of tasks, can often struggle in length generalization and systematicity in syntax- sensixsee tasks (Tran) et al. 2018 Shen et al., 2019a Lakretz et al.) 2021 Csordás et al., 2022). RvNN-based models, on the other hand, can often excel on some of the latter kind of tasks (Shen et al. 2209aa [howdhury & Caragea 2021 Liu et al. 2021 Bogiin et al. 2021) making them worthy of further study although
they may suffer from limited scalability in their current formulations.
Given input text, RvNNs (Pollack 1990: Socher et al. 2010) are designed to build up the repre- sentation of the whole text by recursively building up the representations its constituents starting from the most elementary representations (tokens) in a bottom-up fashion. As such, RvNNs can model the hierarchical phrt- structures underlying texts. However, originally RvNNs required access to pre-defined hierarchical constituency-tre structures. Several works (Socher et al. 2011 Havrylov et al. 2019; Choi et al., 2018: Maillard et al., 2019; [hoowdhury & Caragea 2021) in- troduced latent-tree RvNNS that sought to move beyond this limitation by making RvNNS able to learn to automatically determine the structure of composition from any arbitrary downstream task objective, given just the raw input text.
Among these approaches, Gumbel-Tree models (Choi et al. 2018) are particularly attractive for its simplicity. It often serves as standard baseline for latent- tree models. However. Gumbel-Tree mod- els not only suffer from biased gradients (due to use of also perform poorly on synthetic tasks like ListOps (Nangia & Bowman 2018) that were specifically designed to diagnose the capacity of neural models for automatically inducing underlying hierarchi- cal structures. In this paper, we tackle these issues by introducing the Beam Tree Cell (BT-Cell) framework that applies beam-search as simple modification over Gumbel-Tree models. Instead of greedily selecting the highest scored sub-tree representations like Gumbel-Tree models, BT-Cell chooses and maintains top-k highest scored sub-tree representations. We show that this simple mod- ification increases the performance of Gumbel- Cembel-TTre models in challenging structure sensitive tasks by several folds. For example, in ListOps, when testing for samples of length 900-1000, BT-Celll
Estimation (STE)), but they

---

Under review as a conference paper at ICLR 2023
based model increases the performance of comparable Gumbel-Tree model from 37.9% to 86.7% (see: Table []. We further explore several variants of BT--Cell. Particularly, we explore ways to re- place the -on-differentiable top-k operators involved in beam search with different alternatives such as top-k gumbel softmax with STE and a novel strategy of maintaining a convex combination of bot- tom scoring paths. Our best extension achieves a new state-of-the-art in length generalization and cepth-generalization in structure-sensityy synthetic tasks like ListOps and performs comparably in realistic data against other latent-tree models.
A few recently proposed latent-tree models simulating RvNNs like LSTM-RL (Havrylov lov et al, 2019). Ordered Memory (OM) (Shen et al. 2019a) or CRvNN (Chowdhury Carageal [021] 1) are also strong contenders to BTT-Cell and its extensions on synthetic data. However, unlike BT--Cell, LSTM-RI. relies on expensive reinforcement learning and several sophisticated techniques to stabi- lize training. Moreover, compared to OM and CRvNN, one distinct advantage of BT-CClll is that it not just provides the final sequence encoding (representing the whole input text) but also the interme- diate constituent representations at different levels of hierarchy (representations of all nodes of the underlying induced trees). Such tree-structured node representations can be useful as inputs to fur- ther downstream modules like a Transformer (Vaswani et al. (017)) or GNN (Scarselli et al. 2009) in a full end-to-end setting [ While CYYK-based RvNNs (Maillard et al. 2019) are also promising and similarly can provide multiple span representations they tend be much more expensive than BT-Cell. All these architectural trade-off's among different latent-tree models are discussed in more details in Appendix E.6
Besides proposal and evaluation of BT-Cell variants, our paper also serves as a survey of how well prior proposed latent-tree RvNNS work in structure-sensitive synthetic tasks and out-of-dittribution- splits in natural language tasks, particularly when combined with more powerful recursive cells. Additionally, as further contribution, we identify a previously unknown failure case for even the best performing neural models when it comes to argument generalization in ListOps (Nangia & Bowman 2018) opening up a new challenge for future research.
2 PRELIMINARIES
Similar to Choi al. (018)) throughout this paper, we explore the use of RvNNs as a sentence encoder. Formally, given a sequence of token embeddings X' = (e1, .2....,,,, e,,) (where X' E Radd :, E R and de is the embedding size), the task of a sen- tence encoding function & IR + da is to encode the whole sequence of vectors into a single vector o = {(') (where o E RR and d, is the size of the encoded vector). We can use a sentence encoder for sentence-pair comparison tasks like logical inference for text classification.
Problem Formulation:
2.1 RECCURENT NEURAL NETWORKS AND RECURSIVE NEURAL NETWORKS
A core component of both RNNs and RvNNs is a recursive cell. In our contexts, the cell function takes as arguments two vectors (a, E IRda; and 02 E Ro and returns a single vector v = cell(a1, (2) (where v E Rd cell IR:;; RRaaz - IRd.. In our settings, we generally set da, = daz = d, d,. Given sequence X. both RNNs and RvNNs sequentially process it through recursive application of the cell function. For a concrete example, consider a sequence of token embeddings such as (2 4 x 4 + (Assume the symbols 2, 4, + etc. represent transformations of corresponding embedding vectors E dy)) Given any such sequence, RNNs can only follow a fixed left-to-right order of composition. For the particular aforementioned sequence, an RNN-like application of the cell function can be expressed as:
cell (cel
2), x),,),,
(1)
Here h0 is some input-independedn initial state ("initial hidden state") set in the model. In contrast to RNNs, RvNNs can compose the sequence in more flexible orders. For example, one way (among
'There are several works that have used intermediate span representations for better compositional gener- alization in generalization tasks (Liu et al. 2020 (Herii & Berant) [02]] Bogin et al. 2021 Liu et al. 202 Mao al. (021). We keep it future task to explore whether the span representations returned by B --Clll be used in relevant ways.
2

---

Under review as a conference paper at ICLR 2023
many) that RvNNs could apply the cell function is follows:
+), cell(cell(4, x); 4)), +),3)
o =
Thus, RNNs can be considered as, roughly, special case of RvNNs where a strict left-to-right order of composition is enforeed. As we can see, by these strategies of recursively reducing two vectors into a single vector, both RNNs and RvNNs can implement the sentence encoding function in the form of E. Moreover, the form of application of cell function exhibited by RNNs and RvNNs can also be said to reflect a tree-structure. For any application of the cell function in the form v = cell(ar, (2), e can treated as the representation of the immediate parent node of child nodes d1 and dg in a underlying tree.
In Eqn. 2 we find that RvNNs can align the order of composition to PEMDAS whereas RNNs can- not. Nevertheless, RNNs can still learn to simulate RyNNs by modeling tree-structures implicitly in their hidden state dimensions (Bowman et al. 2015b). For example, RNNs can learn to hold off the information related to "2+" until "4 x 4" processed. Their abilities to handle tree-structures is analogous to how we can use pushdown automation in recurrent manner through an infinite stack to detect tree-structured grammar. Still, RNNs can struggle effectively learn to appropriately organize information in practice for large sequences. Special inductive biases can be incorporated to enhance their abilities to handle their internal memory structures (Shen et al. 2019b a). How- ever, even then, memories remain bounded in practice and there is a limit to what depth of nested structures they can model.
More direct approaches to RvNNs, in contrast, can alleviate the above problems and mitigate the need of sophisticated memory operations to arrange information corresponding to tree-structure because they can directly compose according to the underlying structure (Eqn. 2 However, in the case of RvNNs, we have the problem of first determining the underlying structure to even start composition. One approach to handle the issue can be to train separate parser to induce a tree structure from sequences using gold tree parses. Then we can use the trained parser in RyNNs. However, this is not ideal. Not all tasks or languages would come with gold trees for training a parser and a parser trained in one domain may not translate well to another. A potentially better approach is to jointly learn both the cell function and structure induction from downstream objective. We focus on this latter approach. Below we discuss one framework for this approach.
2.2 EASY-FIRST PARSING AND GUMBEL TREE MODELS
Here, we describe an adaptation (Choi et al. 2018 of easy-first parsing Gooldbrr & Elhadad 2010 for Rwsed sentence- encodinn.. The algorithm relies on scorer function score IR IR' that scores parsing decisions. Particularly, if we have v = cell(a1, ag), then score(v) represents the plausibility of a and a2 belonging to the same immediate parent constituent. In practice, similar to
Choi et al. (2018), we keep the scorer as a simple linear transformation: score(v) = W.v (where dd and E "R
W. E IR
Recursive Loop: In this algorithm, at every iteration a recursive loop, given a sequence of hidden states h2,, (in)) we consider all possible immediate candidate parent compositions taking the current states as children: (cell(h), h2),, cell ha), cell(hn.1. kn)) We then score each of the candidates with the score function and greedily select the highest scoring can- didate (i.e. we commit to the "easiest" decision first). For the sake of illustration, assume score (cell h)+1)) score(cell(h,,, hy+1)) Vj E (1.2....,,)) n]. Thus, following the algo- rithm the parent candidate cell(h,, h;+1) 1) can be chosen. The parent representation cell(h, 1)+1) would then replace its immediate children hú and h441. Thus, the resulting sequence will become: (hi...., h ch,,(h,, hxt1), hi+2..... .1.22....h.. h.). Like this, the sequence will be iteratively reduced to a single element representing the final sentence encoding. The full algorithm is presented in the Appendix (see Algorithm]] D.
One issue here is how to choose the highest scoring candidate. One way to do to simply use an argmax operator but it will not be differentiable. Gumbel-TTre-Cell models (Choi et al. 2018) address this difficulty by using Straight Through Estimation (STE) (Bengio et al. 2013) with Gumbel Softmax (Jang et al. 2017 Maddison et al. 2017) instead of argmax. However, STE is
We focus only the class of binary projective tree structures. Thus all the candidates are compositions of two contiguous elements.
3

---

Under review as a conference paper at ICLR 2023
known to cause high bias in gradient estimation. Moreover, as it was previously discovered (Naggia & Bowman 2018), , and as we independently verify, STE Gumbel-based strategies perform poorly when tested in ttructure-sensitvv tasks. Instead, to overeome these issues, present alternative of extending argmax with a top-k operator under a beam search strategy.
BEAM TREE CELL
Gumbel-Tree models, described, relatively fast and simple but they are fun- damentally based on a greedy algorithm for a task where the greedy solution is not guaranteed to be optimal. On the other hand, adaptation of dynamic programming- ett al. way" between the two extremes is then to simply extend Gumbel-Tree models with beam-search to make it less greedy while still being less costly than CYK-parsers (See Appendix (E.6). More- over, Using beam-search also provides additional opportunity recover from local errors whereas a greedy single-path approach (like Gumbel Tree models) will be stuck with any errors made. All these factors motivate the framework of Beam Tree Cells (BT-Cell).
Motivation:
CYK-models (Maillard
2019) leads to high computational complexity (discussed more in Appendix E.6). "mmiddle
The beam search extension to Gumbel- Tree models is straight- forward and simi- lar to standard beam search. The method is described more precisely in Appendix [nn Algorithm 2 In summary, in BT-Cell, given a beam size k we maintain a maximum of & hypotheses (or beams) at each recursion. In any given iteration, each beam constitutes a sequence of hidden states repre- senting particular path of composition and an associated score for that beam based on the addition of log-softmaxed outputs of the score function (as defined 2.2) over each chosen compositions for that sequence. At the end of the recursion, we will have i sentence encodings ((01. 02, .2...... 0%) where o, RR and their corresponding scores ((51, 82,..., ;8k)) where 8; IR The final se- cap(s;))0;
Implementation:
quence encoding can be then represented as: Σ E. emp(s.)) This aims at computing the expectation over the k sequence encodings.
3.1 TOP K VARIANTS
As standard beam search, BT-Cell requires two top-k operators. The first top-k replaces the straight-through gumbel softmax (simulating top-1) in Gumbel-Tree models. However, selecting and maintaining possible choices for every beams in every iteration leads to an exponential in- crease in the number of total beams. Thus, a second top-k operator is used for pruning the beams to maintain only a maximum of & beams at the end of each iteration. Now, different variants of BT-Cell can be established depending on what kind of top-k operator we use.
The simplest variant is to simply use the vanilla top-k operator. top-k operator discrete and non-differentiable preventing gradient propagation to non-selected paths. Despite that this can still work for the following reasons: (1) Gradients can still pass through the final top l beams and scores. The scorer function can thus learn to increase the scores of better beams and lower the scores of the worse ones among the final & beams; (2) A rich enough cell func- tion can be robust local errors in the structure and learn to adjust for it by organizing information better in its hidden states. We believe that as a combination of these two factors, plain BT-Cell even with non-differentiable top-k operators can learn to perform well for Airucture-sensitee tasks (as we will empirically observe).
Plain Top-k:
However, the vanilla
While non nonfeifferentialee top-k operators can work, they still can be bottleneck because gradient signals will be received only for & beams in space of exponential possibilities. To address this, we replace the plain top-k operator with a STE (Bengio et al.) (001)) through Gumbel top-k (Kool et al., 2019). We refer this operator ST-Gumbel Top-k. This serves natural generalization of the original straight-through gumbel softmax from Choi et al. (2018) (where we had select only one item) the top-k contex[] However, ST-Gumbel Top-K can exacerbate the original issues of biased estimation related to straight-through methods (we discuss more in Appendix D)
ST-Gumbel Top-k:
In practice we find it beneficial to only replace the first top-k operator with S ST-gumbel Top-k. Replacing the second top-k operator with ST-Gumbel top-k tends lead to instability worse performance.
4

---

Under review as a conference paper at ICLR 2023
Beam Sequences
Scores
Beam Sequences
Scores
Softpath Top-K
cell(a call 44 (4)). ms)
-0.1
-0.1
(el(feele :)))
-0.2
cell
(0l102 va), call(24, (2)) (2l
0.3
(a1, (el.
-0.7
(oel((21, cell 24 mg))
Interpolated Beem
Figure 1: Visualization of Top-k Softpath selection from beams to top & beamss.
Softpath Top-k:
Here, we focus on the second top-k operator that is involved in truncating beams. As a concrete case, assume we have beams (sequences and their corresponding scores). The target for top-k operator is to keep only the top scoring & beams (where k S m.)
Ideally we want to keep the beam representations "sharp" and avoid washed out representations owing to interpolation (weighted vector averaging) of distinct paths (Drozdov et al. 2202)). This can be achieved by either plain top-k or ST-Gumbel top-k. However, the former prevents propagation of gradient signals through the bottom - k beams, and the latter can exacerbate bias (see Appendix D) as discussed before. Another line of approach is to create soft permutation matrix E IR" mR through differentiable sorting algorithm such that P.j represents the probability of the 7t beam being the jth highest scoring beam. P can then be used to softty select the top k beams. However, running differentiable sorting in a recursive loop can significantly increase computation overheads and also create more "washed out" representations leading higher more in Appendix [E.I) We tackle all these challenges by instead proposing simple hybrid strategy approach top-k selection. We provide formal description of our proposed strategy below and visualization of the process in Figure
accumulation (we discuss
(H,..... Hm) (H4 E IR Radd, and n being the sequence length) and m corresponding scores: (81, .... 8m). First, simply the plain top-k operator to discretely select the top k - beams (instead of k). This allows us to keep the most promising beams "sharp":
Assume we have m beams consisting of m sequences:
ida = topk KS k Top - ((Hs, idr)
Second, for the t beam we instead perform a softmax-based marginalization of the bottom m (k- 1) beams. This allows to still propagate gradients through the bottom scoring beams (unlike
in the pure plain top-k operator):
Bottom {(H4, (i ( idx) A (i E 11,2,..,,m]}
(4)
softaahh
Σ
cxp(s)) H
exp(s)
(H,s)) exp(s)
E(Hts) eap(())
(Htt))
(HLe) Bottom
Finally we add the softpath to the top k - discretely selected beams to get the final set of k beams: Top U {softparh). Thus, we get to achieve "middle way" between plain top-k and differentiable sorting: partially getting the benefit of sharp representations of the former through discrete top k selection, and partially getting the benefit gradient propagation of the latter through soft-selection of the th beam. In practice, we find it beneficial to switch to plain top-k during inference.
Here, we replace the softmax in the softpath extension (eqn 5 with a straight- through gumbel softmax making the induced structure discrete during training well.
Gumbelpath Top-k:
EXPERIMENTS AND RESULTS
Hyperparameters and other architectural details are in the Appendix H Next, we discuss the main models that we compare.
5

---

Under review as a conference paper at ICLR 2023
1. RecurrentGRC: RecurrentGRC is an RNN implemented with the Gated Recursive Cell (GRC) Shen et al. 2019a) as the cell function (see Appendix B for description of GRC).
2. RandomIrreGRC:: RandomTreeGRRC is an RyNN with GRC that randomly chooses parent compositions at each iteration (based on uniform probabilities).
3. BalancedTreeGGRC Teee is an RyNN with GRC that enforces binary balanced tree structure. Some prior experiments (Shi et al. 2018) have shown strong results just by using balanced trees like this.
4. GoldTreeGRC:: GoldTreeGRC a GRC-based RvNN with gold tree structures.
5. GumbelTreeL.TMM. This is the straight-through Gumbel-tree implementation by Choi et al.
2018). It uses the LSTM cell (Hochreiter & Schmidhuber 1997 Tai et al. 2015).
6. GumbelTreeGRC: This is same GUMDeITreeLSTM but with GRC instead of LSTM.
BSRP-GRC: Maillard & Clark 20118) proposed a similar approach to ours where they apply beam search into shift-reduce parsing framework instead of casy-first-parsing We adapt that framework with the GRC cell and call it as BSRP-GRC. More details are provided in Appendix C
8. CYK-GRC: This is the CYK-based model proposed by Maillard et al. (2019) but with GRC.
9. Ordered Memory: This is a form of memory-augmennt RNN simulating certain classes of RvNN functions proposed by (Shen et al., 2019a). Ordered Memory also uses GRC.
10. CRvNN: CRvNN is a variant of RvNN with a continuoux relaxation over its structural opera- tions as proposed by Chowdhury & Caragea (202T) CRvNN also uses GRC. In implementation, we ignore some extraneous elements from CRvNN such as transition features and halt penalty which were deemed have little effect during ablation.
11. BT-LSTM: Base BT-Cell model with LSTM cell and plain top-k operator.
12. BT-GRC: Base BT-Cell model with GRC and plain top-k operator.
13. Gumbel BT-GRC: BT-Cell model with GRC and ST-Gumbel top-k operator.
14. BT-GRC Softpath: BT-Cell model with GRC and Softpath top-k operator.
15. BT-GRC + Gumbelpath: BT-CClll model with GRC and Gumbelpath top-k operator.
For experiments with BT-Cell models, we consider beam size 5 as a practical choice which is neither too big nor too small. However, we also explore beam size for the most promising variants of BT- Cell to see how far can get with the minimally costly version of beam search.
4.1 LISTOPS LENGTH GENERALIZATION RESULTS
ListOps Nangia & Bowman 2018 is challenging synthetic task that requires solving of nested mathematical operations over lists of arguments. We present our results on ListOps performance,
Dataset Settings:
train the models only with < 100 lengths (we filter the rest) and test on splits of much larger lengths (eg. 200 - 300 or 900 1000) taken from Havrylov et al. (2019). "Near-IID" is the original test set of ListOps (it is "near" IID and not fully IID because percentage of the split has > 100 length sequences whereas such lengths are absent in the training split).
in Table [ To test for wongth-gnneralzzenn
sequences
As discussed before in 2.1 RNNs has to model tree struc- tures implicitly their bounded hidden states and thus can struggle generalizing to unseen struc- tural depths. This is reflected in the sharp degradation in its length generalization performance. Unsurprisingly, other cuaristic-tree-batee perform well either in this structure-sensitive task. 2. Gumbel Tree Models: Consistent with prior work Nangia & Bowman 22018), Gumbel- -ree models fail to perform well in this task; likely, due to its biased gradient estimation. 3. CYK-GRC: CYK-GRC shows some promise to length gener- alization but it was too slow to run in higher lengths (see discussion in Appendix E.6). 4. Ordered Memory (OM): Here, we find OM struggles to generalize to higher unseen lengths. OM's reliance of soft sequential updates in a nested loop can lead to higher error accumulation over larger unseen lengths or depth. 5. CRvNN: Consistent with Chowdhury & Caragea (2021), CRvNN performs
Results: 1. Heuristic Tree Models:
models (BalancedTreeGRCC or RandomTreeGRRC do not

---

Under review as a conference paper at ICLR 2023
Model
ncar-IID
Length Gen.
Argument Gen.
LRA
(Lengths)
S 1000
200-300
500-600
900-1000
100-1000
100-1000
2000
(Arguments)
S
S
S 5
S
10
15
With gold trees
GoldTreeGRC
99.95
99.88
99.85
100
80.5
79
78.1
Baselines without gold trees
LSTM-RL*
99.2s
RecurrentGRC
84.05
33.85
20.2
15.1
37.35
30.10
20.7
BalancedTreeGRCC
59.4
44.85
43.35
35.70
45.88
45.25
41.95
RanGo
70.56
48.70
45.35
37.53
54.8
55.6
49.8
GumbeTTreeLSTM
63.08
45.8
42.75
36.8
48.95
49.2
45.35
GumbelTreeGRC
74.89
47.6
43.85
37.9
51.35
50.5
46.1
CYK-GRC
97.87
93.75
60.75
42.45
BSRP-GRC
70.34
42.4
33.15
26.3
40.15
35.75
29.65
Ordered Memory
99.88
92.7
76.9
84.15
75.05
80.1
CRvNN
99.6g
98.51
97.9511
96.7819
CRvNN
98.86
95.89
93.15
89.4
57.8
24.35
45.1
Beam Tree Models with beam size 5 (also without gold trees)
BT-LSTM
94.11
85.1
83.5
78.8
67.9
44.25
57.85
BT-GRC
99.39
96.15
92.55
86.7
77.1
63.7
67.3
Gumbel-BT-GRC
96.15
75.35
64.25
55.1
58.65
50.4
50.2
BT-GRC+ Softpath
99.92
99.5
99
97.2
76.05
67.9
71.8
BT-GRC Gumbelpath
99.84
99.45
99.2
99.4
79.25
63
72.85
Beam Tree Models with beam size (also without gold trees)
BT-GRC
94.18
68.2
56.85
50.2
64.45
56.95
55.85
BT-GRC Softpath 99.69
97.55
95.40
91
75.75
62
66.1
BT-GRC Gumbelpath
88.56
55.4
51.3
46.1
54.65
52.95
49.55
Accuracy on ListOps. * indicates results from Havrylov et al. (2019). t indicates results from Chowdhury & Carageal (202I). LSTM-RL is the model proposed in HHvrylov et al. (2019) For our models we report the median of runs. Our models were trained on lengths < 100, depth S 20, and arguments 5. We bold the best results and underline the second-best among models that do not use gold trees. Subscript represents standard deviation. As an example, 901 = 90 0.1
Table 1:
relatively decently at higher lengths. BSRPC-GRC: Surprisingly, despite using similar frame- work to BT-Cell, BSRPC-GRC performs quite poorly. We suspect this is because of the limited gradient signals from its top-k operators coupled with the doubling of recurrent steps (that can cause gradient issues) due to taking shift-reduce strategy. Moreover, BSRPC-GRC. unlike BT-Cell, also lacks the global competition among all parent compositions when making shift/reduce choices. 7. when
BT-GRC and BT-LSTM: Here, we find massive boost over Gumbel-tree baselines using the base models: BT-GRC or BT-LSTMM (beam size 5). In the 900-1000 length generalization split, BT-GRC increases the performance of GumbelTreeGGRC from 37.9% to 86.7% all just by adding beam search with plain top-k. But as expected, the performance degrades severely when the beam size is reduced to 2. Note that the recurrent depth for BT-Cell it pertains to backpropagation is just the tree depth (not the doubled sequence length as in BSRP-GRC). This may further explain its superiority to BSRP-GRC. 8. Gumbel BT-GRC: This model does not perform as good. Part of its issue could be related to, again, the biased estimation due to STE. We also discuss more specific issues that applies this model Softpath was specifically designed to counteract the bottleneck of gradient propagation being limited through only & beams in the base BT-Cell (with plain top-k). The bottleneck even worse when (beam size) is 2 empirically this is reflected in the poor performance of base BT-GRC with beam size 2. However, Softpath does what it's designed to: it counteracts the bottleneck. Empirically, this is reflected in its much higher performance than base BT-GRC under beam size 2. Where base BT-GRC gets only 50.2% in the 900 1000 split, BT-GRC+ gets 91%. BT-GRC+Softpah has perfect length generalization with beam size 5. The performance of Gumbelpath is more
Gumbelpath in Appendix D Softpath and Gumbelpath:

---

Under review as a conference paper at ICLR 2023
Model
SST2 IID
SST5
IMDB
IID
LG
III
Con.
Count.
RecurrentGRC
89.440.s
52.19
47.453.9
90.941.2
74.862s
82.7219
BalancedTreeGRC
87.833.7
52.356.2
46.373.9
90.71o.9
74.9322
83.61
C
89.331
51.781.2
49.831.2
91.681.1
74.9314
82.389.3
GUM
88.652.1
52.44g
48.436.3
88.396.9
72.2716
80.6713
GumbelTreeGRC
89.225.6
51.67s.8
50.36.3
85.1111
70.6321
81.97s
CYK-GRC
89.66%
51.991s
49.143.3
OOM
OOM
OOM
Ordered Memory
89.461.6
52.302.7
49.68s
91. 91.690.5
76.98s.
83.687.s
CRvNN
88.5812
51.7511
49.5g
91.471.2
77.80 77.801s
85.383.5
Beam Tree Models with beam size
BT-LSTM
88.501.1
50.83.5
47.1417
90.771.3
74.257.7
82.243.5
BT-GRC
88.522.9
52.324.7
18.4510
91.291.2
75.07
82.8623
Gumbel-BT-GRC
88.82.u .9
51.737.1
49.671.9
86. 86.6211.3
72.2029
83.272s
BT-GRC Softpath
88.34.7
51.927.2
48.01c
90. 90.86p.3
75.6821
84.7711
BT-GRC Gumbelpath
88.6 88.673.
51.774.8
48.1516
88.3918
7239
82.65s7
Beam Tree Models with beam size
BT-GRC
88.94g
52.142.8
50.087.4
91.51
75.21
82.51
BT-GRC Softpath
88.524.a
52.24.4
472.5
90.411.s
75.8922
85.4516
BT-GRC Gumbelpath
89.27a.4
52.14
49.437.2
83. 83.2419
63.817
70.421.2
Table 2: Accuracy on SST2, SST5, and IMDB. Con. refers to Contrast test set, and Count. refers Counterfactual test We report the mean/std of We bold the best resuls and underline the second-best. Subscript represents standard deviation. As an example, 90, = 90 = 0.1
mysterious. While it struggles lower beam, it is par with Softpath with beam size 5. It appears higher beam size is necessary to unlock the potential Gumbelpath.
4.2 LISTOPS ARGUMENT GENERALIZATION RESULTS
Dataset Settings: While length generalization (Havrylov
2019 Chowdhury & Caragea 2021
and depth generalization (Csordás et al. 2022) have been tested before for ListOps, the performance on argument generalization was yet to be considered. In this paper, we also consider what would happen if we increase the number of arguments in the test set beyond the maximum number en- countered in the training set. The training of the original listops data only has S 5 arguments for each operator. To test for argument generalization we created two new splits one with 10 ar- guments per operator and another with 15 arguments per operator, In addition, we also consider the test set of ListOps from Long Range Arena (LRA) dataset (Tay al. (021)) which serves check for both length generalization (it has sequences length 2000) and argument generalization (it has 10 arguments per operators) simultaneously. Results in Table
Interestingly, we find all the models perform poorly (< 90%) on argument generalization. However, with the exception of Ordered Memory (OM), BT-cell models (discounting Gumbel-BT. GRC) with higher beam size performs much better than any other models (including otherwise strong contenders like CRvNN). Surprising, OM performs quite well in this split. We do not know the exact reason, but we can eliminate some reasons. First, we know OM not performing better simply due better parsing because it even surpasses GoldTreeGRC times. Second, also know OM's performance is not just due to a better recursive cell, since its cell (GRC) is shared by many other models that do not perform as well. This may suggest that the memory-augmente augmented RNN style setup in OM is more amenable for argument generalization.
Results:
4.3 SEMANTIC ANALYSIS (SST AND IMDB) RESULTS
Dataset Settings: SST (Socher et al. 2013) and IMDB (Maas et al. 2011) are natural language classification datasets. In the IID splits (standard split) of SST2 and SST5 all the models perform similarly. To better check for OOD performance, we create a gnntttggnneralizzatinn (LG) split in SST5 (we call this the IG split). Particularly, we only keep sequences of length < 15 in the training
8

---

Under review as a conference paper at ICLR 2023
set, keep sequences of length 16-29 in the validation set, and keep all sequences of length 2 30 in the test set. For IMDB, besides the IID test set, we also test our models on the contrast set from Gardner al. (2020) and the counterfactual test set from Kaushik al. (2020). We present our results on these datasets in Table 2
The results in this natural language tasks is rather mixed and do not provide clear consis- tent differences among these models. There are, however, some interesting highlights. Similar to Shi et al. (2018), we found BalencedTreeGRCC can perform competitively most test splits. how- ever, it performs more poorly than others when it comes to length generalization (SSTS LG split). CRvNN and OM do particularly well in the OOD splits (contrast set and counterfactual split) of IMDB, correlating with their better OOD generalization in synthetic data. BT-GRC + Sofipath is also relatively competitive in those splits and better than any other models besides CRvNN and OM. STE Gumbel-based models tend to pareform particularly worse on IMDB.
Results:
5 ADDITIONAL EXPERIMENTS AND ANALYSIS
Synthetic Logical Inference: We present results on challenging synthetic logical inference task (Bowman et al. 2015b) in Appendix E.4 We find that most variants of BT-Cell can perform on par with prior SOTA models in this task.
ListOps Depth Generalization: We also run experiments to test depth--generrlization performance on ListOps (see Appendix E..2
Transformers: We experiment briefly with Neural Data Routers (Csordás et al. 2022) which is Transformer-base model proven to do well in tasks like ListOps. However, we find that Neural Data Routers (NDRs), despite their careful inductive biases, still struggle with sample efficiency and length generalization compared to strong RvNN-based models. We discuss more Appendix E.3
Natural Language Inference: We present our results MNLI along with some stress-test splits in Appendix E.S We find that BT-Cell variants can improve robustness to some stress test splits of MNLI compared to most other models.
Parse Tree Analysis: We analyze parsed trees and score distributions in Appendix E.7
RELATED WORKS
Goldberg & Elhadad (2010) proposed the easy-first algorithm for dependency parsing. Ma et al.
(2013) extended it with beam search for parsing tasks. Choi et al. (2018) integrated easy-first-parsing with an RvNN. Similar to us. Maillard & Clark (2018) used beam search to extend shift-reduce WrozdassDrozdov BT-Cell- models achieve higher accuracy than the former style of models (eg. BSRP-GRC) and are computationally more efficient than the latter style of models (eg. CYK-GRC) (see Appendix E.6). Similar to us, Collobert et al. (2019) also use beam search in an end-to-end fashion during training but in the context sequence generation. However, none of the above approaches explored beyond hard top-k operators in beam search. One exception is Xic et al. (2020) where differentiable top-k operator is used in beam search for language generation (We compare against [iie et al. (2020)
parsing whereas Drozdov et al, (2020) used beam search extend CYK-based algorithms. However,
in Appendix E.
We provide extended related works survey in Appendix
7 CONCLUSION
Overall, we find all three of Ordered Memory, CRvNN, and BT-Cell are competitive against each other; none being completely superior in all aspects. BT-Cell with Softpath excels in length gen- cralization at ListOps and offers moderate performance on argument generalization but hurts at systematicity (disccussed in Appendix [.4). Ordered Memory excels in argument generalization while struggling in length generalization. CRvNN performs decently in length generalization but struggles in argument generalization. CYK-GRC shows some promise too but is several times more expensive (Appendix [E.6) to run while having poor performance in systematicity (Appendix [E.4] and argument generalization. We discuss future works in Appendix G

---

Under review as a conference paper at ICLR 2023
REFERENCES
Ryan Prescott Adams and Richard S. Zemel. Fast differentiable sorting and ranking, In ArXiv, 2011. URL httpt::/aaxxii...oom http/aab././11/2211
Yoshua Bengio, Nicholas Léonard, and Aaron C. Courville. Estimating or propagating gradients through stochastic neurons for conditional computation. CoRR, abs/1308.3432, 2013. URL
http://arxiv.ozg/ http:/gggab///1000 3432
Mathieu Blondel, Olivier Teboul, Quentin Berthet, and Josip Djolonga. Fast differentiable sorting and ranking. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 950-95909999 PMLR, 13-18 Jul 2020. URL https:://///mm. blondel 20an.e22a... html
htttttts///crceeee /ttp:s/////cceeeeeee ngs. mlr wwwpseeessivvi htt.....................p.m.
Ben Bogin, Sanjay Subramanian, Matt Gardner, and Jonathan Berant. Latent compositional repre- sentations improve systematic generalization in grounded question answering. Transactions of the Association for Computational Linguistics, 9:195-2100 2021. doi: 10.1162/tacl a 00361. URL
ogy. https://aclaanee wtg.llog/......ccccc/om/
Samuel R. Bowman, Gabor Angeli, Christopher Potts, and Christopher D. Manning. A large notated corpus for learning natural language inference. In Proceedings of the 2015 Confer- Empirical Methods in Natural Language Processing, pp. 632-642 Lisbon, Portugal, September 201 Sa. Association for Computational Linguistics. doi: 10. 10.18653/1/D155-0075. URL
atttss://aclanthooory..ooss org/D15 1075
Samuel R. Bowman, Christopher D. Manning. and Christopher Potts. Tree-structured composition in neural networks without tree-structured architectures. In Proceedings of the 2015th International Conference on Cognitive Computation: Integrating Neural and Symbolic Approaches Volume 1583, COCO'15 15, pp. 37-42, Aachen, DEU, 2015b. CEUR-WS.org
Samuel R. Bowman, Jon Gauthier, Abhinav Rastogi, Raghav Gupta, Christopher D. Manning, and Christopher Potts. fast unified model for parsing and sentence understanding. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Pa- pers), pp. 1466-1477, Berlin, Germany, August 2016. Association for Computational Linguistics. doi: 10.18653/v 100663//1/P11--1.. 1139. URLhttps: httptttpsss//allaahlloloo attpaaaaaaancoooo wwtp:/ooog/llooi..ee
Jihun Choi, Kang Min Yoo, and Sang-goo Lee. Learning to compose task-specific tree struc- tures. Sheila A. Mcllraith and Kilian Q. Weinberger (eds.), Proceedings of the Secooy AAAI Conference on Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Ar- rificial Intelligence (IAAI-18), and the 8th AAAI Symposium on Educational Advances Artifi- cial Intelligence (EAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018, pp. 5094-5101
AAAI Press, 2018 URL https: www. aaai. org/ ocs/ index..ei.. php/ AAAI AAAIAAAAIIAAAAAAA AAAI18/
Saper/vier
paper/view/ 16682
Jishnu Ray Chowdhury and Cornelia Caragea. Modeling hierarchical structures with continuous recursive neural networks. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th Internutional Conference Muchine Learning, volume 139 of Proceedings of Machine Learning mmrr.
Research, pp. 1978-1988. PMLR, 18-24 Jul 2021. URL
press/ vtt./ whwwwhurwwwwcccocco huml
Ronan Collobert, Awni Hannun, and Gabriel Synnaeve. A fully difffcrentiable beam search decoder. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp- 1341-1350. PMLR, 09-15 Jun 2019. URL httpps///ppccccciigg....... htt..eeeeinnnnn.....prsss//////
co lobert 9a.
Róbert Csordás, Kazuki Irie, and Jürgen Schmidhuber. The neural data router: Adaptive control flow in transformers improves systematic generalization. International Conference on Learning Representations, 2022. URL http:e///oeeereeveeeeeeeeeeeooee
10

---

Under review as a conference paper at ICLR 2023
Marco Cuturi, Olivier Teboul, and Jean- Vert. Differentiable ranking and sorting using optimal transport. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran As- sociates, Inc., 2019. URL ht /tt.//ttss////rrccedinngs neurips wttpccccpppppee cc/papper/019//11ee
Gr' Gr'egoire Del'etang, Anian Ruoss, Jordi Grau-Moya, Tim Genewein, Li Kevin Wenliang, Elliot Catt, Marcus Hutter, Shane Legg, and Pedro A. Ortega. Neural networks and the chomsky hier- archy. ArXiv, (ttb://20.000966. 2022.
Andrew Drozdov, Patrick Verga, Mohit Yadav, Mohit lyyer, and Andrew McCallum. Unsupervised latent tree induction with deep ouside- recursive auto-encoders. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume (Long and Short Papers), pp. 1129-112 1149, Minneapolis, Minnesota, June 2019, Association for Computational Linguistics. doi: 10. (0.18653/11/19-11166 URL htttts:://ccaaaaaa wttp:///ooooooooro111111111
og..
Andrew Drozdov, Subendhu Rongali, Yi-Pei Chen, Tim O'Gorman, Mohit Iyyer, and Andrew Mc- Callum. Unsupervised parsing with S-DIORA: Single tree encoding for deep inside-outside recursive autoencoders. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 4832 4845, Online, November 2020. Associa- tion for Computational Linguistics. doi: 10.
http://......mmmaiiiiiiem 7/aclanthol www.toooooy..rgo//0000. ooo.oogg//222 emn 11ppmaan.33
URL https:
Brian DuSell and David Chiang. Learning context-free languages with nondeterministic stack RNNs. In Proceedings of the 24th Conference on Computational Natural Language Learn- ing, pp. 507-519, Online, November 2020. Association for Computational Linguistics. doi:
10118633/1/2020.comll
org/ concl-o.nn.......
Brian DuSell and David Chiang. Learning hicrarchical structures with differentiable nondetermin- istic stacks. In International Conference on Learning Representations, 2022. URL https:
//openzeview. wortt/oormmmtem d=w1xw__5_ppp_e
Hao Fei, Yafeng Ren, and Donghong Ji. Retrofitting muucture-awar transformer language model for end tasks. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language
Processing (EMNLP), pp- 2151-2161, Online, November 2020. Association for Computational Linguistics. doi: 10. (1/56661//220000 20t.2200m00.0mmmmmiiii 168. URL htt.:sss//allaahhollooooo/o .org/
emn main ii.innin 168
Matt Gardner, Yoav Artzi, Victoria Basmov, Jonathan Berant, Ben Bogin, Sihao Chen, Pradeep Dasigi, Dheeru Dua, Yanai Elazar, Ananth Gottumukkala,, Nitish Gupta, Hannanch Hajishirzi, Gabriel Ilharco, Daniel Khashabi, Kevin Lin, Jiangming Liu, Nelson F. Liu, Phoebe Mulcaire, Qiang Ning, Sameer Singh, Noah A. Smith, Sanjay Subramanian, Reut Tsarfaty, Erie Wallace, Ally Zhang, and Ben Zhou. Evaluating models' local decision boundaries via contrast sets. In Findings of the Association for Computational Linguisties: EMNLP 2020, pp. 1307-1323, Online, November 2020. Association for Computational Linguistics. doi: 10. 111566533222220 findings-emnlp.117. URL http:ss//aaaaattooloeo wwg./oog...0//...oooo findings emnlp.
Yoav Goldberg and Michael Elhadad. An efficient algorithm for easy-first non-directional de- pendency parsing. In Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics, pp. 742-750, Los Angeles, California, June 2010. Association for Computational Linguistics. URL https:
//aclanthology org.
Edward Grefenstette, Karl Moritz Hermann, Mustafa Suleyman, and Phil Blunsom. Learning to transduce with unbounded memory. In Proceedings of the 28th International Conference on Neural Information Processing Systems Volume 2, NIPS' 15, pp. 1828-1836, Cambridge, MA, USA, 2015. MIT Press.
Aditya Grover, Eric Wang, Aaron Zweig, and Stefano Ermon. Stochastic optimization of sorting networks via continuous relaxations. In International Conference on Learning Representations, 2019. URL
wtt.::ew.........ee.eeeeeeee wtt.:e/etto...oo..eeeeeeeee eS533cKK

---

Under review as a conference paper at ICLR 2023
Albert Gu, Karan Goel, and Christopher Re. Efficiently modeling long sequences with structured
state spaces. In International Conference on Learning Representations, 2022. URL https:
Serhii Havrylov, Germán Kruszewski, and Armand Joulin. Cooperative learning of disjoint syn- tax and semanties. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers), pp. 1118-1128, Minneapolis, Minnesota, June 2019. Association for Com- putational Linguistics. doi: 10. 1655// URL httep::/acllantholoog.....
N19-1115
Dan Hendrycks and Kevin Gimpel. Bridging nonlinearities and stochastic regularizers with gaussian error linear units. ArXiv, abs/1606.08415, 2016. URL httpp://arrxvv.or/rbbbs/s///////
08415
Jonathan Herzig and Jonathan Berant. Span-based semantic parsing for compositional generaliza- tion. In Proceedings of the 59th Annual Meeting of the Association Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pp. 908-921, Online, August 2021. Association for Computational Linguistics. doi: 10. 18653/v1/2021 aal--lng..74.... 74. URL ht http::///aaaaathhhlocccc httpl//gg.ggggg.ooo.ooo/ 2021 acl
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural Comput., 9(8): 1735- November 1997. ISSN 0899-7667. doi: 10.1 wtt1////co..997.998..
URL
https: org/10 11 62162/nncc 1997 9. 8. 1735
Xiang Hu, Haitao Mi, Zujie Wen, Yafang Wang. Yi Su, Jing Zheng, and Gerard de Melo. R2D2: Recursive transformer based on differentiable tree for interpretable hierarchical language mod- eling. In Proceedings of the 59th Annual Meeting of the Association for Computational Lin- guistics and the 1thh International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pp. 4897-4908, Online, August 2021. Association for Computational Linguis- tics. doi: 10. 10.11855/v1120 122553//11222... 12011//........1o...177777 ac79- acl-long. 379
URL
org/2221.
Mohit Iyyer, Varun Manjunatha, Jordan Boyd-Graber, and Hal Daumé III. Deep unordered com- position rivals syntactic methods for text classification. In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Con- ference on Natural Language Processing (Volume 1: Long Papers), pp. 1681-1691, Beijing, China, July 2015. Association for Computational Linguistics. doi: 10.3115/11/15--162.. URL https: //acl antho ogy. wow.yooooooooooooooo............ org/P15-11211
Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterizatioo with gumbel-softtax In 5th International Conference Learning Representutions, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017. URL hittps:///pperev/// net /
3y85ee
Divyansh Kaushik, Eduard Hovy, and Zachary Lipton. Learning the difference that makes differ- ence with counterfacualll--aggnenetd data. In International Conference on Learning Represen- tations, 2020. URL https:://opprreeiiieeeeee net htt.://awwwwaaaeeeoooooo/ooeaaaa (oorrmmidddSklgssSSE
Wouter Kool, Herke Van Hoof, and Max Welling. Stochastic beams and where to find them: The Gumbel-top-k trick for sampling sequences without replacement. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning. volume 97 of Proceedings of Machine Learning Research, pp. 3499-3500 3508. PMLR, 09-15 Jun 2019. httphttss////rroeeeeeiie
9a. html
Yair Lakretz, Theo Desbordes, Dieuwke Hupkes, and Stanislas Dehaene. Causal transformers per- form below chance on recursive nested constructions, unlike humans. ArXiv, abs/21 2021.
Phong Le and Willem Zuidema. The forest convolutional network: Compositional distributional semantics with a neural chart and without binarization. In Proceedings of the 2015 Confer- ence on Empirical Methods in Natural Language Processing, pp. 1155-1164, Lisbon, Portugal,
12

---

Under review as a conference paper at ICLR 2023
September 2015. Association for Computational Linguistics. doi: 10.18653/ URL
Chenyao Liu, Shengnan An, Zeqi Lin, Qian Liu, Bei Chen, Jian-Guang Lou, Lijie Wen, Nanning Zheng, and Dongmei Zhang. Learning algebraic recombination for compositional generalization. In Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021. pp. 1129- 1144, Online, August 2021. Association for Computational Linguistics. doi: 10. 10.18653/v//202 1/2021. Andings-acl.99, URL
org
/ windinginnnadc.ncc acl. 97
Qian Liu, Shengnan An, Jian-Guamy Lou, Bei Chen, Zeqi Lin, Yan Gao, Bin Zhou, Nanning Zheng, and Dongmei Zhang. Compositional generalization by learning analytical expressions. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS'20 20, Red Hook, NY, USA, 2020. Curran Associates Inc. ISBN 9781713829548
Ji Ma, Jingbo Zhu, Tong Xiao, and Nan Yang, Easy-first POS tagging and dependency parsing with beam search. In Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics ( (Volume 2: Short Papers), pp. 110-114, Sofia, Bulgaria, August 2013. Association for Computational Linguistics. URL httpttsss//tseeeeeee
P
Andrew L. Maas, Raymond E. Daly, Peter Pham, Dan Huang, Andrew Y. Ng, and Christopher Potts. Learning word vectors for sentiment analysis. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, pp. 150, Portland, Oregon, USA, June 2011. Association for Computational Linguistics. URL https:
a/aclantholooy.cok
1015
Chris Maddison, Andriy Mnih, and Yee Whye Teh. The concrete distribution: A continuous re- laxation of discrete random variables. In International Conference on Learning Representations, 2017. URL URL htt.tttsss//opereeeeeeeeee
net/ faweet/forrmmtt forum?id=3 JE5L.5
Jean Maillard and Stephen Clark. Latent tree learning with differentiable parsers: Shift-reduce pars- ing and chart parsing. In Proceedings of the Workshop on the Relevance of Linguistic Structure in Neural Architectures for NLP, pp. 13-18, Melbourne, Australia, July 2018. Association for Computational Linguistics. doi: 10. 10.18653/11/W11-29000 URL https: httts::/accaatholllle
orq/R18-2903
Jean Maillard, Stephen Clark, and Dani Yogatama. Jointly learning sentence embeddings and syntax with unsupervised tree-Istms. Natural Language Engineering, 25(4):433-449, 2019. doi: 10.
1017/8135132499 190001844
Jayyua Mao, Freda H. Shi, Jiajun Wu, Roger P. Levy, and Joshua B. Tenenbaum. Grammar- based grounded lexicon learning. In A. Beygelzimer, Y. Dauphin, P. Liang, and Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021. URL https: //openreview.
6nkEžkc1
Tsendsuren Munkhdalai and Hong Yu. Neural tree indexers for text understanding. In Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics: Volume 1, Long Papers, pp. 11-21, Valencia, Spain, April 2017. Association for Computational Linguisties. https::::: anthollnnttologoo hww.hllllgooooog.ooooooo E10000
Aakanksha Naik, Abhilasha Ravichander, Norman Sadch, Carolyn Rose, and Graham Neubig. Stress test evaluation for natural language inference. In Proceedings of the 27th International Conference Computational Linguistics, pp. 2340-2353, Santa Fe, New Mexico, USA, Au- gust 2018. Association for Computational Linguistics. URL httphttps:///e ststps://www. wwwp///wwww/////////////////ww.. aclweb. wew.org////e........o........ Onthology/CIB-1119
Nikita Nangia and Samuel Bowman. ListOps: A diagnostic dataset for latent tree learning. In
Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Student Research Workshop, pp. 92-99, New Orleans, Louisiana, USA, June 2018 Association for Computational Linguistics. doi: 18.18653/v 11153//1111--0033 URL https://ach antho www.anooooooogooioiii.. ogy.
13

---

Under review as a conference paper at ICLR 2023
Xuan-Phi Nguyen, Shafiq Joty, Steven Hoi, and Richard Socher. Tree- strucctrue attention with hierarchical accumulation. In International Conference on Learning Representations. 2020. URL
net/ Forum?id--HuxSpppa
Felix Petersen, Christian Borgelt, Hilde Kuehne, and Oliver Deussen. Differentiable sorting net- works for scalable sorting and ranking supervision. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceed- ings of Machine Learning Research, pp. 8546-8555, PMLR, 18-24 Jul 2021. URL https:
7 //roceedings.mm. httppppsss//////ttttsss/aaaaaaa html
Felix Petersen, Christian Borgelt, Hilde Kuehne, and Oliver Deussen. Monotonic differentiable sorting networks. In International Conference on Learning Representations, 2022. URL https:
//openreview. ///penrevieewnnt//frrneee
Jordan B. Pollack. Recursive distributed representatiinns. Artificial Intelligence, 46(1):77 - 105, 1990. ISSN 0004-3702. doi: http::/wdb.ooo////..ooooo4400000 URL http: www /tw.:e/cccccccieee.ccccoooooo/ea
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini.
The graph neural network model. Trans. Neur Netw, 20(1):1--0,, jan 2009. ISSN 1045- 9227. doi: 20.1009/TNN.2008.000000 20C5605
URLhttps wtt.di.oog////// /0. 1109 TNN. 2008.
Yikang Shen, Shawn Tan, Arian Hosseini, Zhouhan Lin, Alessandro Sordoni, and Aaron C Courville. Ordered memory. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems 32, pp- 5037-5048. Curran Associates, Inc., 2019a. URL htttp://paper http:////paprss..ssscc..os httppccpcppprrr 8748-
pdE
Yikang Shen, Shawn Tan, Alessandro Sordoni, and Aaron Courville. Ordered neurons: Integrating tree structures into recurrent neural networks. In International Conference on Learning Repre- sentations, 2019b.
net. htte//fooommmmmell1ll....3
Yikang Shen, Yi Tay, Che Zheng, Dara Bahri, Donald Metzler, and Aaron Courville. StructFormer: Joint unsupervised induction of dependency and constituency structure from masked language modeling. In Proceedings of the 59th Annual Meeting of the Association for Computational Lin- guistics and the 11th International Joint Conference on Natural Language Processing (Volume
1: Long Papers), pp. 7196-7209, Online, August 2021. Association for Computational Linguis- tics. doi: 10.18653/v1/2000 acl-iong.55
URL https:
Haoyue Shi, Hao Zhou, Jiaze Chen, and Lei Li. On tree-based neural sentence modeling. In Pro- ceedings of the 2018 Conference on Empirical Methody in Natural Language Processing, pp- 4631-4641, Brussels, Belgium, Dotobbe-NNoemmer 2018. Association for Computational Lin- guisties. doi: 10.18653/v 1492..192. URL https: ac httplp:ss//caaaatt.ooo www.aannntooo..ogooooooooo 1492
Richard Socher, Christopher D. Manning, and Andrew Y. Ng. Learning continuous phrase represen- tations and syntactic parsing with recursive neural networks. In In Proceedings of the NIPS-20IO Deep Learning and Unsupervised Feature Learning Workshop. 2010.
Richard Socher, Jeffrey Pennington, Eric H. Huang, Andrew Y. Ng, and Christopher D. Manning. Semi-supervised recursive autoencoders for predicting sentiment distributions. In Proceedings of the 201 Conference on Empirical Methods Natural Language Processing, pp. 151-161, Edinburgh, Scotland, July 2011. Association for Computational Linguistics. URL https: 1014
aacllantholooy.orr//b0.
Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D. Manning, Andrew Ng, and Christopher Potts. Recursive deep models for semantic compositionality over a sentiment treebank. In Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, pp. 1631-1642, Seattle, Washington, USA, October 2013. Association for Computa- tional Linguistics. URL UKL.hhtte:///cclaatollooo.....//
14

---

Under review as a conference paper at ICLR 2023
Kai Sheng Tai, Richard Socher, and Christopher D. Manning. Improved semantic representa- tions from tre-sttruttrre long short-term memory networks. In Proceedings of the 53rd An- mual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume I: Long Papers), pp. 1556-1566, Beijing, China, July 2015. Association for Computational Linguistics. doi: 1033115/11/155-11555 URL
Yi Tay, Mostafa Dehghani. Samira Abnar, Yikang Shen, Dara Bahri, Philip Pham, Jinfeng Rao, Liu Yang, Sebastian Ruder, and Donald Metzler. Long range arena benchmark for efficient transformers. In International Conference on Learning Representations, 2021. URL https: //openeeviww net htt./oorrmmmio -Vyeal-eeeWeeeeaeeee
Ke Tran, Arianna Bisazza, and Christof Monz. The importance of being recurrent for modeling hier- archical structure. In Proceedings of the 2018 Conference Empirical Methods in Natural Lan- guage Processing, pp. 4731-4736, Brussels, Belgium, Octoher-November 2018. Association for Computational Linguistics. doi: 10.18653/v1/DI8- 1503. URL attpss//aclattholoogy
org/D18- 1503
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, ukasz Kaiser, and Illia Polosukhin. Attention is all you need. In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Gar- nett (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Asso- ciates, Inc., 2017. URL https: http::////sprreeeeinss.s. wew.:eeedd.....................e htc/paperr201///ilee (rai22255fcce11boooooecceeaaaaaa
pdf
Yaushian Wang, Hung-Yo Yi Lee, and Yun-Nung Chen. Tree transformer: Integrating tree structures into self-attention. Proceedings of the 2019 Conference on Empirical Methods in Natural Lan- guage Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pp. 1061-1070. Hong Kong, China, November 2019. Association for Com- putational Linguistics. doi: 10.18653/v//119 1098-1008.
URL https: http::::///aaaahhooooy...o org/
D19-1098
Adina Williams, Nikita Nangia, and Samuel Bowman. A broad-coverage challenge corpus for sen- tence understanding through inference. In Proceedings of the 2018 Conference the North Amer- ican Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers), pp. 1112-1122. Association for Computational Linguisties, 2018. URI
Sttp::/Be web. org/ antho /Ngy/N1/3 /////N11111 1111
Yujia Xie, Hanjun Dai, Minshuo Chen, Bo Dai, Tuo Zhao, Hongyuan Zha. Wei Wei, and Tomas Pfister. Differentiable top-k with optimal transport. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 20520-20531 Curran Associates, Inc., 2020. URL WtR.htttss//proceeeet ngs neurips. Cc/
93 950157772a9922111000008080000 8- pdd
Dani Yogatama, Phil Blunsom, Chris Dyer, Edward Grefenstette, and Wang Ling. Learning to com- pose words into sentences with reinforcement learning. In International Conference on Learning Representations, 2017. M
https: /ttp::::///peree/v//
net. http:///ffoorummmtossssseeee
Aston Zhang, Yi Tay, Yikang Shen, Alvin Chan, and SHUAI ZHANG. Self-instantiated recurrent units with dynamic soft recursion. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and Wortman Vaughan (eds.). Advances Neural Information Processing Systems, volume 34, pp. 6503 6514. Curran Associates, Inc., 2021. URL http::tttsstpppseepsssssss ngs meurips. cc/ //t.://2222//11113333133 h00p:7200....3331113333333aaaa22
15

---

Under review as a conference paper at ICLR 2023
Algorithm Easy First Composition
Input: data X [1 22, Tn.
while True do
if (en(X) () == 1 then
return X[O]
end if
if (en(X) = = then
return (e))
end if
Childrent, ChildrenR + X (en(()) [|1
Parents + [cell childR) for child childR in zip(Children,, Childrenal
Scores + |ccorer (porent))) for parent in Parents]
index + ar gmax (Scores)
X [index +- Parenta (
Delete (índe + 1]
end while
A PSEUDOCODES
We present the pseudocode of the easy first composition in Algorithm [ and the pseudocode of BT- cell in Algorithm 2 Note that the algorithms are written they are for the sake of illustration: in practice, many the nested loops are made parallel through batched operations in GPU.
A.1 BEAM TREE CELL ALGORITHM
Here, we briefly describe the algorithm of BT-cell (Algorithm 2 in words. In BT-Cell, instead of maintaining single sequence per sample, we maintain some & (initially 1) number of sequences and their corresponding scores (initialized to 0). k is a hyperparameter defining the beam size. Each sequence (henceforth, interchangeably referred as "beam") hypothesis representing particular sequence of choices of parents. Thus, each beam represents a different path of composition (for visualization see Figure D. At any moment the score represents the log-probability for its corresponding beam. Now, we describe the steps in each iteration in the recursion of BT-Cell. Step 1: similar to gumbel-tree models, we create all candidate parent compositions for each of the beams. Step 2:
the candidates with the score function (defined in (22)). Step 3: choose top-k highest scoring candidates. We treat the top-k choices as mutually exclusive. Thus, each of the & beams encounters & branching choices, and are updated into distinct beams (similar to before, the children are replaced by the chosen parent). Thus, we get k x k beams. Step 4: we update the beam scores. The sub-steps involved in the update are described next. Step 4.1: we apply a log-softmax to the scores of the latest candidates to put the scores into the log-probability space. Step 4.2: we add the log-softmaxed scores of the latest chosen candidate to the existing beam score for the corresponding beam where the candidate is chosen. As result, we will have k beam scores. Step we truncate the k x beams and beam scores into & beams and their corresponding k scores prevent exponential increase of the number of beams. For that, again simply use a top-k operator to keep only the highest scored beams.
At the end of the recursion, instead of single item representing the sequence-encodiing will have beams of items with their & scores. At this point, to get a single item, we do a weighted summation with the softmaxed scores as the weights described in [3)
B GATED RECURSIVE CELL (GRC)
The Gated Recursive Cell (GRC) originally introduced Shen al. (2019)) drawing inspira- tion from the Transformer's 's forward networks, In our implementation, we use the same variant of GRC used in Chowdhury & Caragea 2021) where GELU Hendrycks & Gimpell (2016)
16

---

Under review as a conference paper at ICLR 2023
Algorithm 2 Beam Tree Cell
Input: data X [1, 22, Fn. J (beam size)
BeamX [X]
BeamScores + [0]
while True do
if Len (Beaaa)))))) = then
BeamX + [beam[0] for beom in Beam.]
break end if
if' len (BeamBeaXBB (0]) = 2 then
BeamX + (cell( [eam(1]) for beam in BeamX]
break end if
New BeamX + New BeamScores 4-
for BeamSBeeamccore in sip(BeamX. BeammSorre) do
Porents [cell (beam[[), [i], beamçi + 1J] for i in range(O, len(beam) 1)]
Scores t log so fotarar (scorer(parent) for parent Parents))
Indices topk (Scores, k:)
for in range(K) do
new + deepcopy( (eam))
newBeam, newuBeam[ndiicesi]] [ndicessi]]
[trrent[[Indccss]]] Delete new Beam [ndices[i]+
Beam.. BeauBeama...pppendneauu new
newScore <- BeamSSoree + Scores
new BeamSoors neurSennSSrre..ooddneeuSSrrrr appeeedeeuunnnscree end for end for
Indices +- topk(new Bew.ee/wwwwe..seeee...a k))
BeamScores & [ew BeanScoreslii for i in Indices]
BeamX + Beam for in Indices) end while
BeamScores Softmar (ofttar((BamSSoore)) (Bammcores)
Return sum ([score X for score, X in zip( BeanScores, Beam.)))
activation function was used. We present the equations of GRC here:
2z
hg
(WCell childiefe childright
= We GeLU
+ b1 + bz
(6)
4
[4
LN(o(z)) @ childreft + (ha) & childright + a ((c)) 3 Uw)
sigmoid; 0; is the parent composition E 4x childieft, childright E 1x Woell
IRdeaxx2 x2-dn; bj E d2, W2 dd by E R1 We use this same GRC function for any recursive model (including our implementation of Ordered Memory) that constitutes GRC.
C BSRP-GRC DETAILS
For the decisions about whether to shift reduce, we use scorer function similar to that used in Chowdhury & Caragea 2021). Where Chowdhury & Caragea (2021) use the decision function on use the decision function the concate-
concatenation of local hidden states (n- (n-gram window), nation of last two items in the stack and the next item in the queue. The output is a scalar sigmoid
activated logit score We then treat log(s) the score for reducing in that step, and log(1 s)
17

---

Under review as a conference paper at ICLR 2023
Model
near-IID
Length Gen.
Argument Gen.
LRA
(Lengths)
$ 1100
200-300
500-600
900-1000
100-1000
100-1000
2000
(Arguments)
5
5
S 5
S
15
10
BT-GRC+SOFT 69
37.1
29.4
39.5
38.6
31.6
Table Accuracy of BT BT-GRC+SOFT on ListOps. We report the median of runs. The model was trained on lengths < 100, depth < 20, and arguments S 5.
as the score for shifting in that step. The scores are manipulated appropriately for edge cases (when there are no next item to shift, when there are two items in the stack to reduce). Besides that, we use the familiar beam search strategy over standard shift-reduce parsing. Finally the beams of final states are merged through the weighted summation of the states based on the softmaxed scores of each beam similar to BT-Cell models as described in :
D ST-GUMBEL TOP-K ISSUES
Let us use the notation argmars(.) (.) to denote the function for selecting the index of the h highest value element in a vector or list. Let us say, we have as vector such that 8; represents the element at the 7th dimension of s. We can now, represent the standard straight-through gumbel softmax Choi et al. (2018) as follows:
p softmax(s G G)
(8)
Lone_hot(argmary (p)) p).laac) +
(9)
Here G is the gumbel noise. This strategy allows the forward propagation to have discrete one hot values (one hot (argmaxxx, (p))) while backpropagation to propagate through the soft p. However, this creates a discrepancy between forward propagation and backpropagation that leads to biased gradient estimation. This problem can be exacerbated in ST-Gumbel Top-k. In this method, instead of top 1, top & items are selected from p. The straight-throus estimation involved in the selection of some nith item among the top k selections (r S k) can be then expressed as:
(one hot(argmax, (p)) pp) detach() -
(10)
Note that Pargmax, (n) S Purgmax, (p)- Thus the discrepancy between p and one not (argmaxx (p)) will only increase with increasing r. Moreover while originally in ST-Gumbel, when selecting top-1, p; can be interpreted (in our context) as the probability that 8; is "top-1" item. But ST-Gumbel Top- k, when selecting the top Th item there is no corresponding interpretation ps would still indicate probability for s; being the "top-I" 1" item not the probability of s; being the "top thh item. Overall, attempted ST-Gumbel Top-k more so because it's simple naive extension of plain top-k but it's not particularly principled approach. As such, the poor performance is not that surprising. A possible extension could be transform p some p" for every top ,thh selection such that pt do reflect probability for s; to be top th item but that would be non-trivial to do without adding significant overhead (similar to that caused by differentiable sorting- see Appendix(E.6)
E ADDITIONAL EXPERIMENTS AND ANALYSIS
E.
DIFFERENTIABLE SORTING
Besides the three extensions considered for BT-Cell, another strategy can be simply use differen-
tiable versions of top-k operators or sorting functions (Adams & Zemel, 2011
Grover et al. 2019
Cuturi et al. 2019 Xie al. 2020; Blondel et al., 2020 Petersen et al., 2021 2022). However, as we discussed before these methods can lead to issues related to "washing out" of representations due to using soft permutation matrices leading to higher error accumulation (although temperature can be used to partially counteract that (Petersen et al.) 2021)). Besides that, using these techniques in recursive loop can lead to significant overhead and added time complexity. Instead, in this paper, we mainly aim to show that simple method, namely, softpath can already bring marked improvement compared to plain top-k especially in low beam size settings for listops. We keep a more exhaustive investigation of application of differentiable sorters for beam search as future work. Nevertheless,
18

---

Under review as a conference paper at ICLR 2023
Model
DG
Length Gen.
Argument Gen.
LRA
(Lengths)
S 100
200-300
500-600
900-Ik
100-1k
100-1k
2K
(Arguments)
5 5
S
S
S
15
S
(Depths)
8-10
S 20
S
S 20
S
S
With gold trees
GoldTreeGRC
99.95
99.95
99.9
99.8
76.95
77.1
74.55
Baselines without gold trees
CYK-GRC
99.45
99.0
67.8
35.15
Ordered Memory
99.95
99.8
99.25
96.4
79.95
77.55
77
CRvNN
99.9
99.4
99.45
98.9
65.7
43.4
65.1
Beam Tree Models with beam size 5 (also without gold trees)
BT-LSTM
98.9
98.5
98.1
97.7
74.75
10.75
65.05
BT-GRC
99.95
99.95
99.95
99.9
75.35
72.05
68.1
BT-GRC + Softpath
99.9
99.6
98.1
97.1
78.1
71.25
75.45
BT-GRC++ + Gumbelpath
99.9
99.95
99.8
99.7
75.2
72.75
71.8
Beam Tree Models with beam size (also without gold trees)
BT-GRC Softpath
96.2
95.40
93.8
91.2
64.45
51.95
51.05
Table 4: Accuracy on ListOps-De DG. We report the median of 3 runs except in the last block where report the mean/std of 10 runs mentioned. Our models were trained on lengths < 100, depth < 6, and arguments < 5. We bold the best results and underline the second-bes best among models that do not gold trees.
we present some preliminary results here. Xie et al. (220)) used an optimal transport-based differ- entiable top k method in beam decoding for machine translation. Here, we use their method (SOFT Top-k) and create new variant of BT-GRC by replacing the softpath with SOFT Top-k. We call this new variant as BT-GRC + SOFT. We run this model in ListOps with the same dataset settings as used in Table [ We report the results in Table 3 As we can see in Table 3 BT-GRC+SOFT shows very poor performance. This supports our hypothesis that using soft permutation matrix in all recursive iterations may not be ideal because of increase chances of error accumulation and "wash- ing out" through interpolations of what would be distinct path representations. In Appendix E.6 we also demonstrate that using SOFT significantly slows down BT-GRC.
E.2 LISTOPS-DG EXPERIMENT
Dataset Settings: The length generalization experiments in ListOps do not give us an exact per- spective in depth generalizatiorr capacities. So there is question of how models will perform in unseen depths. To check for this, we create a new ListOps split which we call "ListOps-DG" For this split, we create 100, 000 training data with arguments < 5, lengths < 100. and depths 6. We create 2000 development data with arguments & 5, lengths < 100, and depths 7. We create 2000 test data with arguments 5, lengths < 100, and depths 8-10. In addition, splits (which now simultaneously have much higher depths too: - 20), same generalization splits, and LRA. The results are presented in Table 4 We only evaluate the argument
also still tested on the
models that were promising (2 90% in near IID settings) in the original ListOps split. We report the median of 3 runs for each model (except the last block of the table).
Interestingly, we find that base BT-GRC, CRvNN, and Ordered Memory now does much better in length generalization compared to the original listops split. We think this is because of the increased data (the training data in the original ListOps is ~ 75000 after filtering data of length 100 whereas here we generated 100, 000 training data). However, while the median of runs in Ordered Memory is decent, found one run to have very poor length generalization performance. To investigate more deeply if Ordered Memory has a particular stability issue, we ran Ordered Memory for 10 times with diferent seeds, and we find that it frequently fails to learn to generalize over length. As a baseline, we also ran BT-GRC similarly for 10 runs and found it to be much more stable. We report the mean and standard deviation of 10 runs of Ordered Memory and BT-GRC
Results:
"By depth, we simply mean the maximum number of nested operators in given sequence in case of ListOps
19

---

Under review as a conference paper at ICLR 2023
Model
DG
Length Gen.
Argument Gen.
LRA
(Lengths)
< 100
200-300
500-600
900-1k
100-1k
100-1k
2K
(Arguments)
S 5
5
5
S
10
15
S
(Depths)
8-10
I 20
S 20
<0
S 10
10
S
Stability Test: Mean/Std with 10 runs. Beam size for BT-GRC
Ordered Memory
99. 99.940.6
97.5832
78. 785181197
61.85291
77.6630
69.03107
67.35125
BT-GRC
99.841.s
99.58s.s
98.821
97.85x9
73.82p7
66.21 107
66.975102
Table 5: Accuracy ListOps-DG (Stability test). We report the mean and standard deviation of of 10, Our models were trained on lengths < 100, depth < 6, and arguments < S. Subscript represents standard deviation. As example, 90, 90 + 0.1
Model
DG1
Length Gen.
Argument Gen.
LRA
(Lengths)
S 50
200-300
500-600
900-1000
100-1000
100-1000
2000
(Arguments)
5
< 5
5
10
15
S 10
(Depths)
8-10
S 20
20
S 20
S 10
S 10
S 10
After Training on ListOps-Dor DGI
NDR (layer 24)
96.7
48.9
32.85
22.1
65.65
64.6
42.6
NDR (layer 48)
91.75
34.60
24.05
19.7
54.65
52.45
39.95
Model
DG2
Length Gen.
Argument Gen,
LRA
(Lengths)
< 100
200-300
500-600
900-1000
100-1000
100-1000
2000
(Arguments)
<
< 5
5
5
10
15
10
(Depths)
8-10
< 20
< 20
S 20
S 10
< 10
S 10
After Training on ListOps DG2
NDR (layer 24)
95.6
44.15
30.7
20.3
67.85
58.05
46
NDR (layer 48)
92.65
38.6
29.15
22.1
73.1
64.4
50.4
Table 6: Accuracy on ListOps-Dor and ListOps-DG2. We report the max of 3 runs. In ListOps- DGI, NDR was trained on lengths S 50, depth < and arguments < In ListOps-DGI, NDR was trained on lengths < 100, depth < 6, and arguments < 5. Lyaers denote the layers used during inference.
in Table 5 As can be seen, the mean of BT-GRC is much higher than that of Ordered Memory in length generalization splits.
E.3 NDR EXPERIMENTS
Neural Data Routers (NDR) is a Transformer-baseed model that was shown to per- form well in algorithmic tasks including Listops (Csordás et al. 2022). We tried some experiments with it too. We found NDR to be struggling in the original ListOps splits or the ListOps DG split. We noticed that in the paper (Csordás al. 2022), NDR was trained in much larger sample size (~ 10 times more data than in ListOps-DGi and also on lower sequence lengths (~ 50). To better check for the capabilities of NDR, we created two new ListOps split DG1 and DG2. In DGI, we set the sequence length to 10-50 in training, development, and testing set. We created million data for training, and 2000 data for development and testing. Other parameters (number of arguments, depths etc.) are same as in ListOps-DC split. Split DG2 is the same as ListOps-DG split in terms of data-generation parameters (i.e it includes length sizes 100) but with much larger sample size for the training split (again, 1 million samples same DG1). We present the results in T
Dataset Settings:
We find that even when we focus on the best of runs the table, although NDR general- izes to slightly higher depths (8-10 from < 6) (as reported in (Csordás et al.] (022)). it still struggles with splits with orders of magnitude higher depths, lengths, and unseen arguments. Following the suggestions of Csordás et al. (2022), we also increase the number of layers during inference (eg. upto 48) to handle higher depth sequences but that did not help substantially. Thus, even after expe- riencing more data, NDR generalizes worse than Ordered Memory, CRvNN, or BT-GRC. Moreover, NDR requires some prior estimation of the true computation depth of the task for its hyperparameter setup unlike the other latent-tree models.
Results:
20

---

Under review as a conference paper at ICLR 2023
Model
Number of Operations
10
11
C
With gold trees
GoldTreeGRC
97.141
96.52
95.292.c
94. 94.219.9
93.677.7
97.411.
Baselines without gold trees
Transformer*
52
51
51
51
48
51
Universal Transformer
52
51
51
51
ON-LSTM*
87
85
81
78
75
Self-IRUf
95
93
92
90
88
RecurrentGRC
93.04s
90.434.9
88.48a
86.57s.8
80.581.5
83.17s.1
BalC
77.813.6
72.566.6
67.544.4
63. 63.666.4
57.447.6
74.451a
Random Cee
86.675.1
84.78s.2
80.458.2
76.62..5
71.714.7
78.069.7
Gumbe/TreeLSTM
77.0312
74.626.1
69.551.7
67 07.94s.1
59.9510
78.2011
GuR
93.4614
91.891a
90.3322
88.4318
85.7024
89.342a
CYK-GRC
96.622.3
96.074.6
94.6711
93.44s.a
92.549.3
77.0827
BSRP-GRC
89.37
85.9230
83.06a5
80.6333
74.9142
81.88a1
CRvNN
96.93.7
95.992.a
94.512.9
94.48s.c
92.731a
89. 79.7
Ordered Memory
97.51.6
96.741.4
94.952
93.92.2
93.366.2
94.887
Beam Tree Models with beam size 5 (also without gold trees)
BT-LSTM
93.272.5
92.63s.3
88,5510
87 07.858.2
84.5612
73.0212
BT-GRC
96.831
95.992.4
95.042.3
94.29g,
93.362.4
94.1714
Gumbel-BT-GRY BT-GRC
95.56s
94.1411
92.7716
91.7121
89.841s
86.55ga
BT-GRC + Softpath
97.03
96.491.a
95.43..5
94.21g..
93.391.s L.
78.0443
BT-GRC + Gumbelpath
96.931.2
95.821.5
94.670.6
93.482.9
92.58g
83.6347
Beam Tree Models with beam size 2 (also without gold trees)
BT-GRC
96.632.2
95.953.7
95.453.1
93.71s.5
93.283.9
86.97ax
BT-GRC + -Softpath
96.961.1
96.491.2
95.381.s
94.64s.4
93.55s.a
81.396a
BT-GRC Gumbelpath
96.481.6
96.024.7
94.717.2
93.947
92.461.1
90.87pa
Table 7:
Mean accuracy and standard deviaton the Logical Inference for > 8 number of opera- tions after training on samples with < 6 operations. We also report results of the systematicity split C. We bold the best results and underline the second-best for all models without gold trees. indi- cates that the results were taken from (Shen et al.] (2019a) and f indicates results from Zhang et al.) (202T). Our models were run 3 times different seeds. Subscript represents standard deviation. As an example, 90, = 90 + 0.1
E.4 SYNTHETIC LOGICAL INFERENCE RESULTS
Dataset Settings: We also consider the synthetic testbed for detecting logical relations between sequence pairs as provided by [Bowman et al. (2015b). Following Tran et al.) (2018), we train the models on sequences with < operators and test on data with greater number of operators (here, we check for cases with > 8 operators) to check for capacity to generalize to unseen number of operators. Similar Shen et al. (2019a); Chowdhury & Caragea (202T), also train the model the systematicity split C. In this split we remove any sequence matching the pattern * (and not*)) ))+ from the training set and put them the test set to check for systematic generalization.
Results: In Table 7 in terms of operation generalization, our proposed BT-Cell models perform similarly prior SOTA models like Ordered Memory (OM) and CRvNN while approximating GoldTreeGRC for both beam sizes. GRC-based models perform better than comparative LSTM- based models. Unsurprisingly, following discussions Appendix D Gumbel-BT-GRC does not perform as well. In terms of systematicity (split C), OM and BT-GRC (with beam size 5) perform similarly (both above 94%) and much better than the other models. Lower beam size extensions hurts systematicity performance for BT-GRC which is not too surprising given beam size. Surprisingly. however, GRC shows promise in operator generalization but shows poor systematicity well. Gumbel-GRC
limiting the extensions also hurt systematicity. CYK-
21

---

Under review as a conference paper at ICLR 2023
Model
M
MM
Len M
Len MM
Neg M
Neg MM
RecurrentGRC
71.2a
71.44
4925
49.524
49.3e
50.1s
Balanced
71.1s
71.4:
59g
60.7a
50.24
50.4s
RandomTreeGRe
72.2g
72.3s
61.423
62.323
51.7g
52.77
GumbelTrecGRC
71.27
71.26
57.517
59.612
50.520
51.820
CRvNN
72.24
72.6G
6244
63.347
52.8s
53.84
Ordered Memory
72.5g
732
56.533
57.1s1
50.97
51.713
Beam Tree Models with beam size 5
BT-GRC
71.62
72.31
64.7e
66.4s
53.737
54.843
BT-GRC+ +Softpath
71.71
71.92
65.61a
66.7g
53.22
54.2s
BT-GRC + Gumbelpath
72.13
71.91
66.37
66.914
51.619
52.221
Beam Tree Models with beam size 2
BT-GRC
72.61
72.62
66.6s
68.
53.321
54.424
BT-GRC + Softpath
71.13
71.91
63.717
65.612
51.819
5312
BT-GRC + Gumbelpath
6746
67.845
55.167
56.2a7
47.842
48.343
Table Mean accuracy and standard deviaton on MNLI Our models were run 3 times on different seeds. Subscript represents standard deviation. As example, 90
90 + 0.1
performs better than fixed tree models (ReccurentGRC or BalencedTreeCell) or RandomTreeCell but still far from SOTA which is not unexpected given its poor results in ListOps.
E.5 NATURAL LANGUAGE INFERENCE EXPERIMENTS
Dataset Settings: We ran our models on MNLI Willliass et al. 2018 which is natural language inference task. We tested our models on the development set of MNLI and use a randomly sampled subset of 10, 000 data points from the original training set as the development set. Our training setup is different from Chowdhury & Caragea (222)) and other prior latent tree models which combines SNLI (Bowman et 201 and MNLI training sets (we don't 't add SNLI data.). We filter sequences 2 150 from the training set for efficiency. We also test our models in various stress tests (Naik et al., 2018). We report the results in Table g M denotes matched development set (used as test set) of MNLI. MM denotes mismatched development set (used test set) of MNLI. LenM denotes length matched stress set from (Naik et al., 2018). LenMM denotes length mismatched stress set from (Naik et al. 2018). NegM denotes negation matched stress set from (Naik al. (2088). NegMM denotes negation mismatched stress set from (Naik et al. 2018). Length matched/mismatcher stress sets add the length of the premise by adding tautologies. Negation matched/mismatched stress sets add tautologies containing "not" terms which can bias the model to falsely predict contradictions.
Results: Results in Table g show BT-GRC variants are not particularly better than the other models in the standard matched/mismatched sets. However, discounting Gumbelpath (which tends to break down), even the weakest BT-GRC variants outperform all other models on length matched/mismatched stress test. BT-GRC (with beam 2 or 5) or BT-GRC with Softpath and beam 5 also tend to do marginally better than other models in negation matched/mismatched test sets, Over- all most BT-Cell variants show better robustness stress tests. We ignore testing Gumbel-BT-GRC because it generally is bad performer.
Overall, given both the performance here and at IMDB, gumbel-based models (including gumbel- path) may be better avoided in general (Also consider that GumbelTrreeGRC, here, performs worse than RRnC)..reeGRRC.
E.6 EFFICIENCY ANALYSIS
compare the empirical performance of various models in terms of time and memory. We ran each models on ListOps splits of different sequence lengths (200-250, 500-600, and 900-1000). Each split contains 100 samples. We ran each model with the batch size of 1. Other hyperparameters are same as those used for ListOps. Note that we are showing time and memory consumption during training (not inference). All models
Settings: In Table 9
in an Nvidia RTX A6000 GPU.
22

---

Under review as a conference paper at ICLR 2023
Sequence Lengths
Model
200
250
500
600
900
1000
Time
Memory
Time
Memory
Time
Memory
RecurrentGRC
0.2 min
0.02 GB
0.5 min
0.02 GB
1.3 min
0.03 GB
BalencedTreeGRC
0.3 min
0.02 GB
1.2 min
0.03 GB
2.1 min
0.04
RandomTreeGGRC
0.4 min
0.33 GB
1.4 min
1.86
3.0 min
5.18 GB
GunbelTreeGRC
0.5 min
0.35 GB
2.1 min
1.95 GB
3.5 min
5.45 GB
CYK-GRC
9.3 min
32.4 GB
OOM
0OM
OOM
OOM
BSRP-GRC
2.3 min
0.06 GB
6.1 min
0.19 GB
10.5 min
0.42 GB
Ordered Memory
8.0 min
0.09 GB
20.6 min
0.21 GB
38.2 min
0.35 GB
CRvNN
1.5 min
1.57 GB
4.3 min
12.2 GB
8.0 min
42.79 GB
Beam Tree Models with beam size 5
BT-GRC
1.1 min
1.71 GB
2.6 min
9.82 GB
5.1 min
27.27 GB
BT-GRC + Softpath
1.4 min
2.74 GB
4.0 min
15.5 GB
7.1 min
42.95 GB
BT-GRC + SOFT
5.1 min
2.67 GB
12.6 min
15.4 GB
23.1 min
42.78 GB
Beam Tree Models with bean size 2
BT-GRC
1.1 min
0.68 GB
2.6 min
3.92 GB
5.1 min
10.90 GB
BT-GRC + Softpath
1.4 min
0.88 GB
4.0 min
5.03 GB
7.1 min
14.01 GB
Table 9: Empirical time and memory consumption for various models. Ran 100 ListOps data of different sequence lengths wiht batch size 1
Discussions:
Assume denotes the sequence length, d denotes the hidden state dimensions, k denotes the beam size. and m denotes the number of memory slots (for Ordered Memory).
Recurrent models performs reasonably well. While it need to go through se- quential steps but so do most other models. Moreover, computation in each iteration of the sequential loop is relatively simple it is just the application of the recursive cell function. The space com- plexity is also very little because of lack of parallel processing accross the sequence length (it has to only store the hidden state memory O(d)). Thus the memory consumption stays nearly constant with increasing sequence length.
RecurrentGRC:
BalancedTreeGRC:
BalancedTreeGRC also moderately efficient. It can slightly increase mem- ory consumption because of more parallelized processing. It composes multiple children in every step. However, since cuts off half the sequence at every step, its outer sequential loop only in the order of Ologg)) Thus, its memory consumption does not increases as much compared to GumbelTreeGRC or RandomTreed Tre.GR.. While the total sequential steps is much less for Bal- GRC, it seems that the added overhead from more parallelized processing per iteration still makes it slightly slower than RecurrentGRC in practice (still it is faster than any other models). However, there may be room for better code optimization for BalancedTrreeCen
RreCelTreeCelll and GumlelTreeCell: Both are similar in terms of complexity. Both chooses one composition time requiring them still go through seuqntial steps in the outer loop unlike Balencc However, unlike RecurrentGRC, in each loop, it has to also parallely compute all possible parent compositions this leads to higher space complexity for each iteration ((nd²) that also scales up with increasing sequence length n and also higher computational overhead per iteration in the loop. Thus, they run slower than RecurrentGRC and takes much more memory as well. Nevertheless, in comparison to other latent-tree models these are still relatively fast, simple, and lightweight.
CYK-GRC: CYK-GRC is the worst offender of all in terms of computational efficiency. Note also that GRC can itself be relatively expensive cell function because of high dimensional feedforward networks adding up overhead compared to classical CYK models. CYK-GRC takes chart-filling approach dynamic programming style. The number of cells in the filled chart is n /2. Each cell in the original CYK algorithm can again have multiple options, however, Maillard et al. (2019) simplifies this by keeping only one option per cell through attention-basee pooling. Even after that, each cell still has to contain d dimensional hidden state. This leads to atleast o(n2d) space
23

---

Under review as a conference paper at ICLR 2023
complexity, Moreover, it still has to take n sequential steps in the outer loop to recursively fill up the chart. At the same time each sequential step is also more expensive than any of the other models. For filling up any cell it has to compute all valid possible ways to combine pre-computed cell and then perform an attention pooling. It has to, thus, apply GRC multiple times to all possible ways of composition from prior chart cells. This step can be, however, parallelized (and we do parallelize it). Nevertheless, applying GRC in parellel to all possible left-right children pair (from prior computed chart cells) can still add to memmory consuption and temporal overheads. This reflects in both extremely high memory consumption and also the slowest speed among all else.
BSRP-GRC: BSRP-GRC is essentially form of stack augmented RNN. Similar to Recurrent- GRC, it's memory consuption is low because of limited parallel processing (although its stack size grow with each iteration which reflects in sharply rising memory with increasing sequence length compared to Recurrent GRC). However, it has added expenses in each recurrent iteration due to additional stack operations and shift/reduce decision computation. In effect this makes the model quite slow although better than some others. BSRPC-GRC taking shift-reduce parsing strategy also need to increase the sequential steps from n to 2n. Although that doesn't 't make an asymptotic difference, it still can further contribute to the empirical slowdown. We use beam size of 5 for BSRP-GRC here for better comparison against BT-GRC.
Ordered Memory: Ordered Memory (OM) is also form of stack augmented RNN and thus, have similar memory advantages as RecurrentGRC (although overall memory consumption is relative increased due storing multiple slots of hidden states). However, the main bottleneck in OM is time. Precisely, OM utilizes nested loop. The outerloop is the same times sequential operation as RecurrentGRC, but in the in each step of that loop, OM has again sequentially apply GRC over the m memory slots. This leads to a (mm) sequential steps. Thus, we get a heavy hit to time consumption with OM.
The framework of CRvNN is roughly similar to GumbelTreeGRC. However, instead of choosing one parent at a time, can choose multiple parents at time, that too in soft manner. But this comes at cost. While GuRC can reduce the sequence size with each sequential step, CRvNN has to still maintain the whole sequence each step with associated "existential probabil- ity" for each sequence item. Moreover, computing the composition of contiguous representations also becomes harder. Since CRyNNs sequence items exists with some probability, what counts as the first existing contiguous item is also probabilistic. In effect, CRvNN needs to create n? attention matrix (similar to Transformers but based on existential probabilities instead of dot prod- uct attention) to retrieve neighbor (contiguous) elements to create parent candidates. Furthermore, in each sequential steps, this n² attention matrix needs to be applied multiple times for example, to get local composition scores for sigmoid modulation and also to retrieve some local items for its convolution-base decision function. That can also add significant overhead (although still quite tame, in terms of temporal overhead, compared to the memory-slot-wiss recursion in OM). Thus, in effect, we get increased memory consumption and time compared to GumbelTreeGRe At the same time, however, efficiency analysis for CRvNN is complicated by the fact that it can dynamically halt early. That is, it does not need to take full sequential steps unlike any of the other models (besides Tal,nCedTreeGRRC) However, this doesn't mean CRvNN is guaranteed to take (logn) sequentials steps. Ideally, it is intended to take as many sequential steps as is the induced binary tree depth. Underlying binary tree depths are not necessarily always (or even in average) around (logn). So while it can give an increase performance boost, there is not a clear boost asymptotically. More- over, we found it challenging to evaluate CRvNN fairly. In the 100 samples dataset, CRvNN with early halting can just induce bad trees (given lack of enough data to be trained well) and halt very fast (unreflective of realistic performance) but increasing number of samples makes the analysis more cumbersome overall for all other models. So instead show the "worst case" performance of CRvNN. The "worst case" is the case when CRvNN does not halt early; thus, to simulate the "worst case" we disable early halting. The "worst case" is also still practically relevant and needed to be considered to set up the hyperparameters (like batch size) properly so that the model does not run out of memory during training because of the "worst case" induction. With this setup, we find CRvNN to be in-between in terms of performance. We discuss more about it in comparison to BT-Cell models in the next section.
CRNNN:
BT-GRC:
The time complexity of BT-GRC is O(nkknd + k-nd)). l (beam size) is technically a relative small constant and can be ignored in asymptotic analysis (bringing BT-GRC at a similar complexity level to Gumbel-Te -ree GRC), but we keep it here for better exposition of the effect of
24

---

Under review as a conference paper at ICLR 2023
beam size (k). Similar to most other models here, BT-GRC has to take outer sequential steps of n. In each sequential step, similar to GumbelTreeGRC it has to calculate all parent candidates which can lead to complexity of ((nd)), but since now we have to do the same for each of the k beams we have a multiplicative effect: ( However, this nd2 computation can be done in computed in parallel in GumbelTreeGRC). Similarly each beams
parallel (all parent candidates are independent and can be computed in parallel as well. So in effect the computation cost here is similar to increasing the batch size of GumbelTreeGRC by k. The term ndd indicates the selection costs of i vectors of size d from k.² vectors of size d for sequence of size n. Again, in practice this can be also parallelized by creating a ko2 permutation matrix and performing single matrix multiplication in CUDA. Overall, this doesn't 't add as much cost over parent composition.
As we a priori suspected, empirically, we also verified the increased time/memory cost of BT-GRC in different sequence length to match the effect of increasing the batch size of GumbelTreeGRR by k. Even though, ultimately, is a constant, practice, this can still lead to a significant expense. This is where small k (example beam 2) can be valuable. As we can see because most computation through k is parallelized the time not changed as much in changing from beam size (k) 2 to 5. But the memory consumption can be significantly decreased with lower beam (k 2). Thus, BT-Celll with beam size 2 can be an attractive choice here particularly when it can still perform relatively on par with bigger beam models on synthetic logical inference and natural language tasks. Also with softpath and beam size 2, listops performance is still decent.
Another interesting point to note is that BT-GRCC does not rely on any n² matrix CRvNN. Thus, we can see that its memory consumption scales better with increasing length than CRvNN. For example, in sequence length 200-250, CRvNN took slightly less memory than BT-GRC, but in sequence length 900-1000, CRvNN takes nearly twice as much memory compared to BT-GRC.
However, we wouldn't 't claim that CRvNN is strictly worse than BT-GRC in efficiency departments because CRvNN can be made more efficient by bounding its outer sequential loop and dynamic halting (but these factors are more tricky to fairly analyze).
BT-GRC + Softpath: Although the forward propagation complexity should be nearly the same for Softpath, in practice we find that adding Softpath increases both the memory and time significantly compared to base BT-GRC. We find that this is because of added backpropagation expenses because of more complicated gradient propagation. We verified this by keep the forward network of Softpath variant the same and using Pytorch's detach() function to cut the gradient from Top-K Softpath selection. This change leads to similar empirical efficiency to base BT-GRC. Nevertheless, despite the added costs, Softpath is still comparable to CRvNN and much faster than OM, CYK-GRC, SOFT top-k, and BSRP-GRC. Moreover, Softpath with beam size 2 still remains an attractive option with further lowered memory consumption.
BT-GRC + SOFT: As we already claimed before using differentiable sorting algorithm (SOFT Top-k) (Xie al. 2020) in recursive loop can bring significant overhead and slowdown. We show it empirically in 9 Replacing Softpath with SOFT Top-k can increase the time taken by around 3x compared to SRCoophh....
E.7 PARSE TREE ANALYSIS
In this section, analyze the induced structures of BT-Cell models. Note, however, although in- duced structures can provide some insights to the model, we can draw limited conclusions from them. First, if we take stance similar to Choi et al. (0018) in considering it suitable to allow different kinds of structures to be induced as appropriate for a specific task then it's not clear how structures should be evaluated by themselves (besides just the donwstream task evaluations). Sec- ond, the extracted structures may not completely reflect what the models may implicitly induce because the recursive cell can override some of the parser decisions (given how there is evidence that even simple RNNs Bowman et al. (2015b) can implicitly model different tree structures within its hidden states to an extent even when its explicit structure always conform to the left-to-right or- der of composition). Third, even if the extracted structure perfectly reflects what the model induces, another side of the story is the recursive cell itself and how it utilizes the structure for language un- derstanding. This part of the story can still remain unclear because of the baackbox-naturr of neural nets. Nevertheless, extractive structures may still provide some rough idea of the inner workings of BT-Cell variants.
25

---

Under review as a conference paper at ICLR 2023
Score
Parsed Structures
BT-GRC (beam size 5)
0.42
((i (did not)) ((llike a) (single minute)) ((of this) film))
0.40
(((i (did not)) (like a) (single minute))) ((of this) film)
0.20
((i (did not)) (((like a) ((single minute) of) (this film))
0.40
((i (shot an)) ((elephant in) (my pajamas]))
0.21
((Oi shot) (an elephant)) ((in my) pajamas)
0.19
((Gi shot) (an elephant)) (in (my pajamas])
0.19
((i shot) ((an elephant) ((in my) pajamas)))
0.40
(Gjohn saw) ((a man) (with binoculars))
0.40
((Gjohn saw) (a man)) (with binoculars))
0.20
(Gjonn (saw a)) ((man with) binoculars))
0.61
((rroger (dodger is)) (one (of the))) (((most compelling) (variations of)) (this theme)))
0.40
(((roger (dodger is)) ((one (of the)) (most compelling)) ((variations of) (this theme)))
BT-GRC (beam size 2)
0.50 ((i ((did not) like)) (((a single) minute) ((of this) film))
0.50
((i (((did not) like) (a single))) ((minute of) (this film))
0.50
((i (shot an)) ((elephant in) (my pajamas))
0.50
((i ((shot an) elephant)) ((in my) pajamas))
0,51
((john (saw a)) ((man with) binoculars))
0.49
(john ((ssaw a) man) (with binoculars)))
1.0
(Iroger ((dodger is) one)) ((((of the) most) (compelling variations)) ((of this) theme)))
Table 10: Parsed Structures of BT-GRC trained on MNLL Each block represents different beams.
In Table 10. we show the parsed structures of some iconic sentences by BT-GRC after it is trained on MNLI. We report all beams and their corresponding scores. Note, although beam search ensures that the sequence of parsing actions for each beam is unique, different sequences of parsing action can still lead to the same structure. Thus, some beams end up being duplicates. In such cases, for the sake of more concise presentation, we collapse the duplicates into single beam and add up their corresponding scores. This why we can note in Table T0 that we sometimes have fewer induced structures than the beam size.
At rough glance, we can see that the different induced structures roughly correspond to human intuitions. One interesting appeal for beam search is that it can more explicitly account for ambigu- ous interpretations corresponding to ambiguous structures. For example, "i shot an elephant in my pajamas" is ambiguous with respect to whether it is the elephant who is in the shooter's 's pajamas, or if it is the shooter who is in the pajamas. The induced structure (beam size 5 model in Table [TP ((6i shot) (an elephant)) (fin my) pajamas)) corresponds better the latter interpretation whereas (ii shot) ((an elephant) ((in my) pajamas)) corresponds better to the former interpretation (because "an elephant" is first composed with "in my pajamas").
Similar to above, "john saw a man with binoculars" is also ambiguous. Its interpretation is ambigu- ous with respect to whether it is John who is seeing through binoculars, or whether it is the man who just possesses the binoculars. Here, again, we can find (beam size 5 model in Table TOp that the induced structure (((john saw) (a man)) (with binoculars) corresponds better to the former interpre- tation whereas ((john saw) ((u man) (with binoculars)) corresponds better to the latter. Generally, we find the score distributions to have a high entropy. A future consideration would be whether we should add an auxiliary objective to minimize entropy.
In Table II
we show the parsed structures of the same sentences by So-GRCh after it is trained on MNLI, and in Table 12 we show the same for BT-GRC+Gumbelpathh Most of the points above applies here for Softpath and Gumbelpath as well. Interestingly, Softpath and Gumbelpath seemed to have relatively lower entropy distribution that is most evident in beam size 2. We also note that Gumbelpath structures are of a similar quality despite having much lower empirical performance in MNLI.
26

---

Under review as a conference paper at ICLR 2023
Score
Parsed Structures
BT-GRC + Softpath (beam size 5)
0.42
((ii did) (not like)) (((a single) minute) ((of this) film))
0.20
((((i did) not) (like a) single)) ((minute of) (this film))
0.19 (((ii did) (not like)) ((a single) minute)) ((of this) film)
0.19
((0i (did not)) ((like a) single)) ((minute of) (this film))
0.41
(((i shot) an) ((clephant in) (my pajamas))
0.21
((Gi shot) (an elephant)) ((in my) pajamas)
0.19
((i (shot an)) ((elephant in) (my pajamas)))
0.19 ((((i shot) an) (clephant in)) (my pajamas)
0.21
(Gjohn (saw a)) ((man with) binoculars))
0.20
((johnn saw) (a man)) (with binoculars))
0.20
(Gjhhn saw) ((a man) (with binoculars))
0.19
(Gohnn ((saw a) man)) (with binoculars))
0.40
(((roger dodger) (is one)) ((((of the) most) (compelling variations)) ((af this) theme)))
0.21
(((roger (dodger is)) ((one of) the)) (((most compelling) variations) ((of this) theme)))
0.20
((((roger dodger) (is one)) (fof the) most)) (ccompelling variations) ((of this) theme)))
0.19
(Iroger (dodger is)) ((((one of) the) ((most compelling) variations)) ((of this) theme)))
BT-GRC + Softpath (beam size 2)
0.57
((i ((did not) like)) (((a single) minute) ((of this) film))
0.43
((i ((did not) like)) (((a single) (minute of)) (this film))
0.54
((i ((shot an) elephant)) ((in my) pajamas))
0.46
((i (shot an)) ((clephant in) (my pajamas)))
0.55
(ijohn (saw a)) ((man with) binoculars))
0.45
((john ((saw a) man)) (with binoculars))
0.53
(rroger ((dodger is) one)) ((((of the) most) (compelling variations)) ((of this) theme)))
0.47
(((roger ((dodger is) one)) ((of the) most)) (ccompelling variations) ((af this) theme)))
Table 11: Parsed Structures of BT-GRC Softpath trained on MNLI. Each block represents different beams.
We found the structures induced by BT-Cell variants after training on SST5 IMDB to be more ill-formed. This may indicate that sentiment classification does not provide a strong enough signal for parsing rather, exact induction of structures not necessary (lyyer et al. 2015).. We show the parsings of these models after training on IMDB and SST datasets in a text file included in the supplementary.
F EXTENDED RELATED WORKS
Socher et al. (2010) used with user-annotated tree-structured data. Some explored use of heuristic trees such as balanced trees for RvNN-like settings Munkhdalai & Yu, 2017 Shi et al., 2018). In due time, several approaches were introduced for dynamically inducing structures from data for RyNN-style processing. This includes the greedy easy-first framework using
Initially RvNN Pollack 1990);
loss (Socher et al. (001]) or gumbel softmax
(Choi et al. 2018). RL-based frameworks (Havrylov et 20.1) CYK-base
framework (Le &
Zuidema 2015 Maillard al. 2019 Drozdov et al. 2019 Hu et al. 2021), shift-reduce parsing
or augmened or stack-augmented RNN frameworks (Grefenstette et al.) 2015 [Bwmmn
let al.) 2016; Yogatama et al.) 2017, Maillard Clark, 2018 [hhnn et al., 2019a DuSell & Chi-
ang 2020 2022), and soft-recursion-basee frameworks (Chowdhury & Caragea 202 Zhang al.)
2021). Besides RvNNs, other approaches range from adding information-orf -orderinnn-reringggg biases to hidden
states in RNNs (Shen al. 2019b) or even adding additional structural or recursive constraints to
Transformers (Wang et al. 2019: 2019.Nguyen Nguyen et al., 2020;
Fei et al. 2020 Shen et al.] 2021
Csordás
al. 2022).
27

---

Under review as a conference paper at ICLR 2023
Score
Parsed Structures
BT-GRC+ Gumbelpath (beam size 5)
0.42
((6i (did not)) (like a)) ((single (minute of)) (this film))
0.38
(((i did) ((not like) (a singlc))) ((minute (of this)) film)
0.20
((Gi did) ((not like) (a single))) ((minute (of this)) film)
0.43
((i (shot an)) ((elephant in) (my pajamas))
0.20
((O shot) (an elephant)) ((in my) pajamas)
0.19 ((Gi shot) (an (elephant in))) (my pajamas)
0.18
((Gi (shot an)) (elephant in)) (my pajamas))
0.39
(((john saw) (a man) (with binoculars))
0.39
(Gohnn saw) ((a man) (with binoculars)))
0.21
(Gjohn (saw a)) ((man with) binoculars))
0.41
((rroger (dodger is)) (one (of the))) ((most (compelling variations)) ((of this) theme)))
0.21
(((roger dodger) (is one)) (((of the) (most (compelling variations)) ((of this) theme)))
0.20
(((roger dodger) (fis one) (of the))) ((most (compelling variations)) ((af this) theme)))
0.19
(((roger (dodger is)) ((one (of the)) (most (compelling variations))) ((of this) theme))
BT-GRC Gumbelpath (beam size 2)
0.58
(((((i did) (not like)) (a single) (minute (of this))) film)
0.42
(((((i did) (not like)) (a single)) (minute of) (this film)
0.64
(((i (shot an)) (elephant (in my))) pajamas)
0.36
(((i (shot an)) (elephant in)) (my pajamas))
0.53
((john (saw a)) (man (with binoculars))
0.47
((Gjohn (saw a)) (man with)) binoculars)
0.51
(((((roger dodger) (is one)) (of the)) (most (compelling variations)) (of (this theme)))
0.49
(((((((oger dodger) (is one)) (of the)) (most (compelling variations)) (of this)) theme)
Table 12: Parsed Structures of BT-GRC + Gumbelpath trained on MNLI. Each block represents different beams.
G LIMITATIONS AND FUTURE WORKS
The ideal future direction would be extend to methods which generalize better in all aspects while maintaining computational efficiency and at the same time having more flexible architecture for handling more free structures like non-projective trees or directed acyclic graphs and also richer classes of languages (DuSell & Chiang 2022; Del'etang et al. 2022). Another direction to explore would be to linearize the recursion particularly taking inspiration from state space models (Gu al.) 2022) to make these models more scalable.
H HYPERPARAMETERS
For all recursive/recurrent models, we use linear layer followed by layer normalization for initial leaf transformation before starting the recursive loop (similar to Shen et al. (2019a); Chowdhury &
Caragea 2)2TT). ). Overall we use the same boilerplate classifier architecture for classification and the same boilerplate sentnece-pair siamese architecture for logical inference as Chowdhury & Caragea (202T) over our different encoders. In practice, for BT-Cell, we use stochastic top-k through gumbel perturbation similar to Kool et al. (2019). However, we find deterministic selection to work similarly.
In terms of the optimizer, hidden size, and other hyperparameters besides dropout, we use the same ones as used by (Chowdhury & Caragea 2021) for all models for corresponding datasets; for number of memory slots and other ordered memory specific parameters we use the same ones as used by (Shen et al.] 2019a). For ESRP-Cell we use a beam size of 8 (we also tried with 5 but results similar or slightly worse). We use dropout rate of 0.1 for logical inference for all models (tuned on the validation set using grid search among [0.1, 0.2, 0.3, 0.4] with 5 epochs per run using BalancedTreeCall for GRC-based models and Mumbe/Treel.STM for LSTM based models). We
28

---

Under review as a conference paper at ICLR 2023
dropouts in the same places used in (Chowdhury & Caragea 2021 We then use the same chosen dropouts for ListOps. We tune the dropouts for SST in the same way (but with a maximum epoch of 20 per trial) on SST5 using RecurrentGRC for mRC-lodels, and Gumbel-Tree-LSTT for LSTM models. After tuning, for GRC-based models in SST5, we found a dropout rate of 0.4 for input/output dropout layers, and 0.2 for the dropout layer in the cell function. We found dropout 0.3 for LSTM-based models in SSTS, and We share the hyperparameters of SSTS with SST2 and IMDB. For MNLI, used similar settings Chowdhury & Caragea (2021).
For NDR experiments, we use the same hyperparameters as used for ListOps by Csordás et al. 2202).. The hyperparameters will also be available in code.
All codes are run in single RTX A6000 GPU.
29


Reviews:
[{"review_id": "uda4OyOEy4p", "reviewer": "Reviewer_dDzD", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a new method, called Beam Tree Recursive Cells, for sentence representation recursively using beam search. The BT-cell extracts a beam of parses (using the same mechanism of easy-first parsing, replacing argmax with top-k) when processing a sentence, and then combining all beams at the end for a sentence representation. Although top-k is non-differentiable, the paper shows that it is quite effective enough for training, without the need for back-prop though top-k. The paper demonstrates that BT-cell is effective for artificial tasks Logical Inference, ListOps, and real tasks SST and IMDB. ", "summary_of_the_review": "The paper doesn't meet the acceptance standard: \n* its quality should be improved so that the the choices and their impacts are understood better\n* the work is quite incremental, i.e. the contribution doesn't seem significant. \n", "strength_and_weaknesses": "The BT-cell is a straightforward extension for argmax-based easy-first parsing and thus it is clear and easy to understand. The paper however does't explain why this extension is helpful. \n\nFirstly, the paper lacks analyses about the impact of beam search and found structures among the beams. For instance, by examining the beams, can we find *good* structures that support required compositionality? What if we vary the beam size? What are distributions of scores? Also, as the paper claims that top-k is good enough although it is non-differentiable, would there be an analysis looking into the beams to support the argument given right below eq (3)? \n\nThe experiment setting is pretty unfair to the baselines. The paper compares several variations of BT-cells (with different beam sizes, top-k operators...) against the baselines. But that is not much different from fine-tuning on test sets, where hyper-params are beam size and top-k operator. For instance, in Tab1 we can see that BT-GRC performs very well on 'C', with '+softpath' it does better on '7,8,...,12' but much worse on 'C'. BT-cell with different beam sizes also yields different results ( tab1 vs tab3). However in the end, all the conclusions are for BT-cell in general, rather than some specific BT-cell configuration. \n\nThe paper claims that CYK approaches are expensive, but there's no complexity analysis for the proposed BT-cell. \n\n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "huT6N2W1l0", "reviewer": "Reviewer_Dk8K", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper presents a differentiable easy-first beam search for structure induction, called Beam Tree Recursive Cells (BT-RC). A couple methods are presented to handle the sparse gradient issue in beam search. There are two sources of sparsity: parent composition and the topk filtering of beams. The two groups of methods presented are Gumbel-BT-GRC, which uses straight-through Gumbel topk for parent composition, and Softpath variants, which use a convex combination of beam elements. The models are evaluated against strong structure-sensitive baselines and perform comparably and in some cases favorably.", "summary_of_the_review": "I advocate for a weak reject. The method approaches key issues in scaling latent structured models, but is missing crucial analyses. I will be happy to increase my score to accept given more analysis on space/time complexity and empirical speed numbers.\n\nEdit: After updated score from 5->6 after author's response.", "strength_and_weaknesses": "*Strengths*\n\nThe accuracy evaluation is thorough, and the results have convinced me that the method is performant. However, one of the biggest drawbacks of latent structure methods is scalability. I would like to better understand the computational complexity of the method and baselines.\n\n*Weaknesses*\n\nThe paper needs an analysis of computational complexity. I believe the method has $O(B^2k)$ runtime. How do the other methods compare? A table with asymptotic runtimes / space complexity is a crucial missing component. An empirical study of the runtime (time per iteration vs sentence length) would greatly improve a scalability argument as well.\n\n\n\n*Comments*\n* The text description of beam search can be placed in the appendix.\n* An illustration of the easy-first beam search with Softpath would be a nice figure to have.\n* The paper is missing a citation for easy-first beam search [1].\n* What is the connection between state space models and beam search mentioned in the last sentence of the paper?\n* I believe beam search + softpath can be interpreted as a continuous relaxation of the sum-and-sample estimator [2], generalized to beam search. The sum-and-sample estimator takes the top-k elements from a proposal distribution and samples an extra element to eliminate bias at the cost of added variance. Instead of sampling to reduce bias, Softpath makes a soft decision that reduces bias less than a sample would but does not add variance.\n\n[1] Ji Ma, Jingbo Zhu, Tong Xiao, and Nan Yang. 2013. Easy-First POS Tagging and Dependency Parsing with Beam Search. In Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pages 110–114, Sofia, Bulgaria. Association for Computational Linguistics.\n\n[2] Liu, Runjing et al. “Rao-Blackwellized Stochastic Gradients for Discrete Distributions.” ICML (2019).", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "LDni-LfnlPl", "reviewer": "Reviewer_muQo", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors present a novel algorithm for recursive neural network processing of sequence inputs. The algorithm combines easy-first parsing techniques with beam search in order to efficiently explore the space of possible latent tree structures during training and inference. They also present soft relaxations of the framework which lead to improved performance. They include an extensive evaluation of their model variants and many baseline models on synthetic and naturalistic language tasks.", "summary_of_the_review": "This paper presents what seems to me a small increment on existing recursive neural network models, which yields modest performance increases. Interpretation of the models' successes are extremely limited. While I appreciate the attempt at a broad evaluation of many recursive neural network models, the results are not well synthesized beyond tables of numbers and lists of qualitative results.\n\nOn these grounds I recommend rejection. I recommend the authors work on evaluating and interpreting the model results in order to better support future model development, or push for meaningful performance improvements, especially on naturalistic language datasets.", "strength_and_weaknesses": "- Impressive synthesis of existing recursive neural network models and evaluation on a level playing field.\n- Novel model with a reasonable selection of variants, with some improvements in performance over baseline models.\n- Limited interpretation and evaluation of why this model works (or why other models work).", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "7ajkFrF9ex", "reviewer": "Reviewer_bsU1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper presents BT-Cell, which uses a beam-search style technique to calculate the representation of a sequence with recursive neural networks while automatically determine the best backbone structure. Experiments show improvements in some generalization splits on a synthetic dataset (listops), and results on real datasets are on par with existing state-of-the-art methods.\n", "summary_of_the_review": "This paper presents BT-Cell, which uses a beam-search style technique to calculate the representation of a sequence with recursive neural networks while automatically determine the best backbone structure. The contribution of this paper is to combine the idea of beam search with latent tree structure learning in recursive neural networks, and demonstrate the effectiveness on a synthetic dataset. While the proposed BT-cell achieves improved performance on listops long sequences, showing a potential on the length-generalization in real NLP applications, most techniques exist in prior work. The paper also lacks of qualitative analysis or gain on real NLP tasks. \n\nI hereby acknowledge the value of this work, but recommend a rejection for this paper as I don't think the content and novelty is sufficient enough for ICLR.\n", "strength_and_weaknesses": "## Strengths\n\n- The proposed BT-cell shows improved performance on listops long sequences, showing a potential on the length-generalization in real NLP applications.\n\n- Very comprehensive survey and comparison to existing work.\n\n## Weaknesses \n\n- Lack of qualitative analysis on failure cases: while the improvement by the proposed BT-cell is marginal on listops, it would be good to understand which types of sequences BT-cells help to process.\n\n- Most techniques exist in prior work, while lack of gain on real NLP tasks.\n\n- Missing reference: [1] applies a CKY style algorithm for CCG induction, which improved the performance of generalization on two tasks. Their expected execution results is essentially in the same spirit as this work's list of beam, and both pieces of work focus on generalization.\n\n[1] Mao et al., 2021. [Grammar-Based Grounded Lexicon Learning](https://proceedings.neurips.cc/paper/2021/file/4158f6d19559955bae372bb00f6204e4-Paper.pdf). In NeurIPS. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject