Efficient Beam Tree Recursion
Authors: Jishnu Ray Chowdhury
Cornelia Caragea
Venue: NeurIPS 2023 poster (2023)
Keywords: Recursive Models
Recursive Neural Networks
RvNNs
Length Generalization
Structured Encoding
Representation Learning
TL;DR: We make Beam Tree Recursive Cells much more efficient. We provide a way to utilize its intermediate tree nodes to turn it into a sequence contextualizer

Abstract: Beam Tree Recursive Neural Network (BT-RvNN) was recently proposed as an extension of Gumbel Tree RvNN and it was shown to achieve state-of-the-art length generalization performance in ListOps while maintaining comparable performance on other tasks. However, although better than previous approaches in terms of memory usage, BT-RvNN can be still exorbitantly expensive. In this paper, we identify the main bottleneck in BT-RvNN's memory usage to be the entanglement of the scorer function and the recursive cell function. We propose strategies to remove this bottleneck and further simplify its memory usage. Overall, our strategies not only reduce the memory usage of BT-RvNN by $10-16$ times but also create a new state-of-the-art in ListOps while maintaining similar performance in other tasks. In addition, we also propose a strategy to utilize the induced latent-tree node representations produced by BT-RvNN to turn BT-RvNN from a sentence encoder of the form $f:\mathbb{R}^{n \times d} \rightarrow \mathbb{R}^{d}$ into a token contextualizer of the form  $f:\mathbb{R}^{n \times d} \rightarrow \mathbb{R}^{n \times d}$. Thus, our proposals not only open up a path for further scalability of RvNNs but also standardize a way to use BT-RvNNs as another building block in the deep learning toolkit that can be easily stacked or interfaced with other popular models such as Transformers and Structured State Space models. Our code is available at the link: https://github.com/JRC1995/BeamRecursionFamily.

Efficient Beam Tree Recursion
Jishnu Ray Chowdhury Cornelia Caragea
Computer Science
University of Illinois Chicago cormeliaQuic.edu
jraych2Quic.edu
Abstract
Beam Tree Recursive Neural Network (BT-RvNN) was recently proposed as an extension of Gumbel Tree RvNN and it shown achieve state-of-the-art length generalization performance in ListOps while maintaining comparable performance other tasks. However, although better than previous approaches in terms of memory usage, BT-RvNN can be still exorbitantly expensive. In this paper, we identify the main bottleneck in BT-RvNN's memory usage be the entanglement of the scorer function and the recursive cell function. We propose strategies to remove this bottleneck and further simplify its memory usage. Overall,
strategies not only reduce the memory usage of BTT-RNN by 10 - 16 times but also create a new state-of-the-art in ListOps while maintaining similar performance in other tasks. In addition, we also propose strategy to utilize the induced latent-tree node representations produced by BT-RvNN to turn BT-RvNN from sentence encoder of the form f !/p At into token contextualizer of the form f I x Thus, our proposals not only open up path for further scalability of RvNNs but also standardize way to use BT-RvNNS as another building block in the deep learning toolkit that be easily stacked or interfaced with other popular models such as Transformers and Structured State Space models. Our code is available the link: https: /ettps//ggitub. Httm//RR1995/BBemaeeee catesiionaaammm
Introduction
Recursive Neural Networks (RvNNs) 63 in their most general form can be thought of as a repeated application some arbitrary neural function (the recursive cell) combined with some arbitrary halting criterion. The halting criterion can be dynamic (dependent on input) static (independent of the input). From this viewpoint, nearly any neural network encoder the deep learning family can be seen special instance of an RvNN. For example, Universal Transformers [13] repeat Transformer (85) layer block as a recursive cell and adaptively halt by tracking the halting probability
in each layer using some neural function 25 S
Deep Equilibrium Models (DEQ) implicitly
"repeat" recursive cell function using some root-finding method which is equivalent to using the
convergence of hidden states dynamics as the halting criterion. As Bai al. 2 also showed, any traditional Transformer - i.e. stacked layer blocks of Transformers with non-shared weights can be also equivalently reformulated halting criterion being some preset static upperbound (some layer depth set as a hyperparameter),
recursive repetition of big sparse Transformer block with the
A broad class of RvNNs can also be viewed repeated application of Graph Neural Network (GNN) [68, 91 allowing iterative message passing for some arbitrary depth (determined by the halting criterion). Transformer layers with sequence tokens as nodes and attention- based edge weights. In natural language processing, often encounter the use of stacks of GNNs (weight shared not) to encourage message- passagg-passing through underlying linguistic structures such as dependency parses, constituency parses, discourse
be seen implementing fully connected (all-to-all) graph
structures, abstract meaning representations, and the like 80 39 47 59
90 94
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

In many cases, such models are implemented with some static fixed number of layers or iterations. However, learning certain tasks in a length-generalicn sequence length distribution should require dynamic halting function. For example, consider a simple arithmetic task: 7x (8+ +3). is first necessary to process 8+33 before doing the multiplication in the next step. A task like this can require diructure-sensiivv sequential processing where the sequential steps depend on the input length and nested operators. Although the above example is simple enough, we can have examples with arbitrary nested operators within arbitrarily complex parenthetical structures. Datasets like ListOps [57] and logical inference 77 among others, serve as sanity check for any model's ability to perform similar crructure-enssinee tasks. Natural language tasks, on the other hand, can sometimes hide systematic failures because of the distributional dominance of confounding statistical factors [54]. While, in some algorithmic tasks, Universal Transformer [13 can perform better than vanilla Transformers, both can still struggle in length generalization in logical inference ListOps 71 (4). This brings to explore another alternative family of models-Treed RyNNs with a stronger inductive bias than Universal Transformer but still possessing form of dynamic halt that we discuss below.
fashion without prior knowledge of the
Tree Recursive Neural Networks: Tree-RvNNs 77
(more particularly, constituency Tree RvNNs) treat an input sequence of vectors as the terminal nodes of some underlying latent tree. From this perspective, Tree-RyNNY sequentially build up the tree nodes in a bottom-up manner. Each node (terminal or non-terminal) in the tree will represent some span within the sequence (for text sequences, these would be words, phrases, clauses, and the like). The root node will represent the whole input sequence and thus can be used as an encoded representation of the whole input (for sentences, it can be treated as a sentence encoding). The nodes are generally in the form of vectors.
The non-terminal nodes are built bottom-up through the repeated use of some recursive cell composi- tion function, say rec, starting from height 1 (height being the terminal nodes) all the way up to the root. When building the representation of some node p at height 6, the Tree-RvNN uses the rec function to take all the immediate child nodes of p (from the previous heights 0 to ( - 1) as input arguments and outputs the representation of p. Typically, we only consider binarized trees so the number of children as arguments will be a constant (two) for rec. Thus, it can be represented in the form rec: Rºd x R² + R² Generally, we also constrain our consideration to only projective tree structures | This implies that the model enforces only temporally contiguous node pairs be considered as candidate siblings for any parent node Finally, when the root representation is built the computation terminates. Therefore, reaching the root is the halting criterion. Since the tree structure is dependent on the input and the halting is dependent on the tree structure, the halting mechanism here is dynamic and thus can adapt with input complexity.
This approach has the potential to model mereological (part-whole) structures at different hierarchical scales in a systematic and dynamic manner As an example, let us consider that we have an input such as (4 x 3) + (7+ (8 x 9)). Then, in the ideal case, the Tree-RvNN order of operation would potentially yield: rec(rec(rec(rec(4. x) x)3), +), rec(rec(7, +), rec[rec(8, 9)).. As can see, Free-RvNNs have the potential to model sensitive order of operations considering input hicrarchies which can be botched by unconstrained attention without careful inductive biases 12 10 29
extensive pre-training" 4 We present an extended related work review in Appendix D
Motivation for Tree-RyNNs Although, at first glance to have too strong of an inductive bias, there are a few reasons to be motivated to empirically explore the vicinity of these models:
as formalized above may appear
1. Familiar Recurrent Neural Networks (RNNs) 19 33 are special cases of Rvce-RyNNs that follow enforced ity than RNNs which have served as a fairly strong general model in the pre- mre-rrnsffrmer cra; and even now, optimized linear variants of RNNs (53) are making comeback out-competing
tree. So at the very least RvNeN have more flexibil-
Transformers in long range datasets 26 27 60
'This is done mainly to simplify the search space but assuming projective structures is also standard fare in Natural Language Processing (NLP) [41 196).
"temporal" refers to the original sequential order. The original order is preserved in every iteration.
Similar inductive biases can be favorable in computer vision well 776 30 74
'Overall, RvNNs, as described above, can be also considered as a special case of DAG-GNN S3 where similar principles can apply. Exploring bottom- up tree node building through a more flexible space of DAG-structures be direction to consider in the future.

---

2. Often Tree-RvNNs are the core modules behind models that have been shown to productively
5 45 [2] in settings where other family of models struggle (at least without extensive pre-training).
or compositionally generalize [7]
10 46 32
3. The recursive cell function of Tree-R RvNNs can still allow them to go outside their explicit structural constraints by effectively organizing information in their hidden states if necessary. The projective tree-structure provides only a rough contour for information flow through RvNN- which Tree-RvNNs can Iearn to go around just as an RNN can [7]. So in practice some of these constraints can be less concerning than one may think.
Issues: Unfortunately, the flexibility of Tvee-RRNNs over RNNs comes at a cost. While in RNNs we could just follow on the same chain-structure tree (left-to-right right-to-left) for any input, in Tree-RvNNs we have to also consider some way to dynamically induce a tree-structure to follow. This can be done thternally-that is, we can rely on human inputs or some external parser. However, neither of them is always idcal. Here, we are focusing on complete Tree-RvNN setups that do their own parsing without any ground-truth tree information any in the pipeline. Going this direction makes the implementation of Tree-RyNNs more challenging because it is hard to induce discrete tree structures through backpropagation. Several methods have been proposed either induce discrete structures [1 [9 66 611 or approximate them through some continuous mechanism [10 95 72 71 Nevertheless, all these methods have their trade offs- some do not actually work in structured-sensitivee tasks [57 72 others need to resort to reinforcement learning and an array of optimizing techniques 31 or instead use highly sophisticated architectures that can become practically too expensive in space or time or both [51] 71 10). Moreover, many of the above models II (n being the sequence size). This formulation as sentence encoder limits their applicability as a deep learning building block - for example, we cannot use them as intermediate block and send their output to another module of their kind or some other kind like Transformers because the output of a sentence encoder will just be single vector.
10 31 9 have been framed and used mainly
sentence encoder of the form f: IInudd
Believing that simplicity is a virtue, we direct our attention to Gumbel-Tree (GT) RvNN 99 which uses simple easy- easy-first parsing technique (23 to automatically greedily parse tree structures and compose sentence representations according to them (we provide a more extended discussion on related works in Appendix). Despite its simplicity, GT-RvvN relies on Straight- Through Estimation (STE) 4 which induces biased gradient, and has been shown empirically to fail in strnctur-sensiiivve tasks [57]. Yet, a recent approach Beam Tree RvNN (BT-RvNN) [66] promisingly shows that simply using beam search instead of the greedy approach succeeds quite well in dructure-sensitive tasks like ListOps [57] and Logical Inference 7 without needing STE. Nevertheless, BT-RyNN can still have exhorbitant memory usage. Furthermore, so far it has been only tested sentence encoder. We take step towards addressing these issues in this paper:
Our Contributions:
1. We identify a critical memory bottleneck in both Gumbel-Tree RvNN and Beam-Tree RvNN and propose strategies to fix this bottleneck (see 3 Our strategies reduce the peak memory usage of Beam-Tree RvNNs by 10-16 times in certain stress tests (see Table 4..
2. We propose a strategy to utilize the intermediate tree nodes (the span representations) to provide top-down signals to the original terminal representations using parent attention mechanism. This allows a way to contextualize token representations using RvNNs enabling us to go beyond sentence-encoding (see $4)
3. We show that the proposed efficient variant of BT-RvNN incurs marginal accuracy loss if at
all compared to the original-and and some cases even outperforms the original by a large margin (in ListOps).
2 Existing Framework
Here we first describe the existing framework used in Choi et al. (9] and Ray Chowdhury and Caragea [66]. In the next section, we identify its weakness in terms of memory consumption and resolve it.
Task Structure: As in related prior works 9 10 71), start with our focus (although will expand- see 444 exploring the use of RvNNs sentence encoders of the form: f k - Rdd Given a sequence of vectors of size d as input (of the form xd f compresses it into a single vector (of the form ) Sentence encoders can be used for sentence-pair comparison or classification.
3

---

Components: The core components of this framework are: scoring function scorer IR - R and recursive cell rec: Ht x R² + I The scorer is implemented as scorer(t) W.U where W. E IRt The rec( rec(child, child,) function is implemented as below:
7,
childdi (child,
T:
GeLU
Wree + bi Wrer + b2
(I)
9. h
p = (o)) o child + a(r) & child, + + o h)
(2)
Here a is sigmoid: [:] represents concatenation; is the parent node representation built from the children child; and child,, Wr E RR2-dddeut, bj E RR Wy E RR x4-d, by E RR" and 1,r,g.h- E R LN is layer normalization. deell is generally set as 4 x d. Overall, this is the Gated Recursive Cell (GRC) that was originally introduced by Shen et al. [71] and has been consistently shown to be superior 71 I0 66 to earlier RNN cells like Long Short Term Memory Networks (LSTM) 33 80)
Note that these models generally also apply an initial transformation layer to the terminal nodes before starting up the RvNN. Similar to [0] 66), we apply a single linear transform followed by a layer normalization as the initial transformation.
Greedy Search Tree Recursive Neural Networks: Here describe the implementation of Gumbel- Tree RvNN 19). Assume that we have sequence of hidden states of the form (hi, hi....., in some intermediate recursion layer For the recursive step in that layer, first all possible parent node candidates are computed as:
(3) Second, each parent candidate node pł is scored as ef (corer(pt).. Next, the index of the top score is selected as j = or gmaar(ei.n-)) Finally, now the update rule for the next recursion can be expressed as:
p = rec(h; h(), p/2 rec(h2, .h)),...,,.11 rec(h" k/,,)
h
i<j
h
realh h(41) h
i i=
(4)
i>j
Note that this is essentially a greedy tree search process where in each turn all the locally available choices (parent candidates) are scored and the maximum scoring choice is selected. In each iteration, the sequence size is decreased by In the final step only one representation will be remaining (the root node). At this point, however, the tree parsing procedure is not differentiable because it purely relies on an argmax. In practice, reinforcement learning [II, STE with gumbel softmax [9, or techniques like SPIGOT [61 have been used to replace argmax. Below we discuss another alternative and our main focus.
Beam Search Tree Recursive Neural Networks (BT-RyNN): Seeing the above algorithm as a greedy process provides natural extension through beam search done in Ray Chowdhury and Caragea [66]. BT-R<NN replaces the argmax in Gumbel-Tree RvNN with a stochastic Top-K [42] that stochastically extracts both the K highest scoring parent candidates and the K corresponding log-softmaxed scores. The process collects all parent node compositions and also accumulates (by addition) log softmaxxdd scores for each selected choices in corresponding beams. With this, the end result is K beams of accumulated scores and K beams of root node representations. The final exp(s.) representation is softmax-based marginalization of the K root nodes: Σ, Σ, exp(*,) b, where b, is the root node representation of beam and s; is the accumulated (added) log-softmaxed scores every iteration for beam Doing this enabled BT-RvNN to improve greatly [66] over greedy Gumbel- Tree recursion [9] However, BT-RvNN can also substantially increase the memory usage, which makes it inconvenient to use.
3 Bottleneck and Solution
In this section, we identify a major bottleneck in the memory usage that exists in the above framework (both for greedy-searee and beam-search) that can be adjusted for.

---

III
Score
Recursive Cell
Recursive
Select
Select
Recursive
Before
Now
Cell
Figure 1: Visualization of the contrast between the existing framework (left) and the proposed one (right). H1, H2, H3 the imput representations in the iteration. The possible contiguous pairs of them are candidate child pairs for nodes to be built in this iteration. On the left side, we see each pair in parallel fed to the recursive cells create their corresponding candidate parent representations. Then they are scored and one parent (Pi) ) is selected. On the right side (our approach), each child pair candidate is directly scored. The faded colored bars in H1, H2, H3 represent sliced away vector values. The scoring function then selects one child pair. Then only that specific selected child pair is composed using the recursive cell create the parent representation (P)) not wasting unnecessary compute by applying the recursive cell for other non-selected child pairs.
The main bottleneck in the above existing framework is Eqn. That is, the framework runs a rather heavy recursive cell (concretely. the GRC function in Eqn. 2) in parallel for every item in the sequence and for every iteration. In contrast, RNNs could use the same GRC function but for one position use similarly big feedforward networks like GRC in parallel for all hidden states they have fixed a number of layers- whereas BT-RvNNs may have to recurse for hundreds of layers depending on the input making this bottleneck more worrisome. However, we think this bottleneck can be highly mitigated. Below, we present our proposals fix this bottleneck.
Bottleneck:
time sequentially taking very little memory. While Transformers also
3.1 Efficient Beam Tree Recursive Neural Network (EBT-RyNN)
Here, we describe our new model EBT-RvNN. extends BT-RvNN by incorporating the fixes below. We present the contrast between the previous method and our current method visually in Figure [
Fix (new scorer): At any iteration t, we start only with some sequence (hf.... "it....,,,,,, h²)). framework, starting from this the function compute the score for any child-pair will look like:
In the existing
e scorer rec(h;, h:+1)
(5)
This is, in fact, the only reason for which we need to apply rec to all positions (in Eqn. B) at this iteration because that is the only way get the corresponding score; that is, currently the score computation entangles the recursive cell rec and the scorer. However, there is no clear reason to do this. Instead we can just replace scorer o rec (in Eqn. 5 with single new scorer function (scorer new R22d - IR) that directly interacts with the concatenation of (h,, he41) without the rec as an intermediate step and thus disentangling it from the scorer. We use parameter-light 2-layered MLP to replace scorer o rec:
= scorernew (h4, h1+1) = Ge GeLU((h, h441 + W5 +
(6)
Here, WI E -xxd, W E Rd.x11 .bf E ARdd,bb by E IR. Since lightness of the scorer function is critical for lower memory usage (this has to be run in parallel for all contiguous pairs) we set de to be small (d, = 64). In this formulation, the rec function will be called only for the selected contiguous pairs (siblings) in Eqn.
Fix (slicing): While we already took major step above in making BT-RvNN more efficient, we can still go further. It is unclear whether the full hidden state vector size d is necessary for parsing decisions. Parsing typically hangs on more coarse gaasnneg abstract information for example, when doing arithmetic while precise numerical information needs be stored in the hidden states for future
5

---

computation, the exact numerical information is not relevant for parsing only the class of being a number should suffice. Thus, we assume that we can project the inputs into a low-dimensional space for scoring. One way to do that is to use a linear layer. However, parallel matrix multiplications on the full hidden state can be still costly when done for each hidden state the sequence in every recursion. So, instead, we can allow the initial transformation or the RvNN itself to implicitly learn to organize parsing-relann related information in some sub-region of the vector. We can treat only the first min(da, d) (out of d) as relevant for parsing decisions. Then we can simply slice the first min (d., d) out before sending the candidate child pairs to the scoring function. Thus, the score computation can be presented as below:
= neo (h:[0: min(d.. hct1 (0: min(d., d)])
So, now Wi E RR2 x dg. As before we keep d, small (d, = 64). Now, the total hidden state size (d) can be kept high as needed to preserve overall representation capacity without making the computation scale as much with increasing d. The model can now just learn through gradient descent to organize parsing relevant features in the first min(d, d) values of the hidden states because only through them will gradient signals related to parsing scores propagate. Note that unlike [31, we are not running a different rec function for the parsing decisions. The parsing decision in our case still depends on the output of the same single recursive cell but from the previous iterations (if any).
Ray Chowdhury and Caragea (66) also introduced a form of soft top-k function (OneSoft) for better gradient propagation in BT-RvNN. While we still use that as a baseline model, we do not include OneSoft in EBT-RvNN. This is because OneSoft generally doubles the memory usage and EBT-RvNN already runs well without it. The combination of EBT-RvNN with OneSoft can be studied more in the future, but it is variable that we do not focus in this study.
No OneSoft:
None of the fixes here makes any strict asymptotic difference in terms of sequence length but it does lift large overhead that can be empirically demonstrated (see Table T
4 Beyond Sentence Encoding
As discussed before many of the previous models 99 competency on structure-
10 31
66 in this sphere that focus on
tasks have been framed to work only as a sentence encoder of the form f x= - R.d Taking a step further, we also explore way to use bottom-up Tree-RvNNs for loven-level contextualization, i.e., to make it serve as a function of the form f: RR=d d RR This allows Tree-Rv RvNNs to be stackable with other deep learning modules like Transformers.
re-formalize EBS-RvNNS for token contextualization. In EBT- RvNN strictly speaking, the output is not just the final sentence encoding (the root encoding). but also the intermediate non-terminal tree nodes. Previously, we ignored them after got the root encoding. However, using them can be the key to creating a token contextualization out of EBT-RwNNS. Essentially, what EBT-RwNN will build is tree structure with node representations the terminal nodes being the initial token vectors, the root node being the overall sentence encoding vector, and the non- non-terminal nodes representing different scales of hierarchies as previously discussed.
Here, consider whether
Under this light, one way to create a token contextualization is to contextualize the terminal rep- resentations based on higher-level composite representations at different scales or hierarchies of which the terminal representation is a part of. In other words, while we use a bottom-up process of building wholes from parts during sentence encoding, for token contextualization, we can implement a top-down process of contextualizing parts from the wholes that it compose.
A similar idea is used by Teng et al. 82 to recursively contextualize child node representations based on their immediate parent node using another recursive cell starting from the root and ending up at the terminal node representations. The contextualized terminal node representations can then become the contextualized token representations. But this idea requires costly sequential operations.
An alternative that we propose is to allow the terminal nodes to attend [ to the non-terminal nodes to retrieve relevant information to different scales of hierarchies. More precisely, if we want the terminal nodes to be contextualized by the wholes that they compose then we want to restrict the attention only the parents (direct or indirect). This can be done by creating an attention mask based
'The principles discussed here also apply to them Gumbel Tree RyNNs, BT-RyNNs, and the like.

---

on the induced tree structures. In practice, we allow every terminal node as queries to attend to every node as keys and values but use mask to allow attention only if the key represents the same node as that represented by the query or the key represents some parent (direct or indirect) of the node represented by the query. We also implement a relative positional encoding to bias attention [70] using the difference in heights of the nodes as the relative distance. In essence, we are proposing the use of a form of graph attention network [86]. This attention mechanism can be repeated for iterative refinement of the token representations through multiple layers of message-passing
In the case of EBT-RvNNs, we can create separate token representations for each beam and then marginalize them based on beam scores. We describe our concrete setup briefly below but more details are presented in Appendix[F
Step I: First, we begin with beams of representations before they were marginalized. This allows us to access discrete edges connecting parents for every beam. As setup, we have some b beams of tree node representations and their structural information (edge connections).
Step 2: We use Gated Attention Unit (GAU) [36], modern Transformer variant, as the attention mechanism block. We use the terminal node representations as queries (Q) and all the non-terminal nodes as keys (K') and values (V). We use GAU, like graph attention network [86], by using an adjacency matrix A as an attention mask. Agj is set as 1 if and only if Q; is a child of Ky based on our tree extraction. Otherwise As is set as O. Thus attention is only allowed from parents to their terminal children (direct or indirect).
Step 3: We implement basic relative positional encoding similar to that of Raffel et al. 64 The only difference is that for us, the relative distances are the relative height distances.
Step 4: The GAU layer is repeated for iterative refinement of terminal node representations. We repeat for two iterations since this is an expensive step.
Step 5: As before, we marginalize the beams based on the accumulated log-softmax scores after the terminal node representations contextualized.
Use Case: In theory, the contextualized terminal node representations that are built up in Step can be used for any task like sequence labelling or masked language modeling. At this point, we explore one specific use case sentence-pair matching tasks (natural language inference and paraphrase detection). For these tasks we have two input sequences that we need to compare. Previously we only created sentence encoding for each sequences and made the vectors interact, but now we can make the whole of two sequences of contextualized terminal-node embeddings interact with each other through a stack of GAU-based self-attention. This is an approach that we use for some of the sentence-matchinn tasks in Natural Language Processing (Table The models are trained end to end. We discuss the technical details about these architectural setups more explicitly in Appendix
5
Experiments and Results
5.1 Model Nomenclature
Sentence Encoder models:
Transformer refers Transformers 85]
UT refers to Universal
Transformers 13 CRvNN refers to Continuous Recursive Neural Network [10]: OM refers to
Ordered Memory 71]: BT-GRC refers to BT-RyNN implemented with GRC (66]; BT-GRC OS
refers to BT-GRC combined with OneSoft (OS) Top-K function [66]; EBT-GRC refers to our
proposed EBT-RwNN model with GRC; GT-GRC refers to Gumbel-Tree RvNN 9 but with GRC as the recursive cell; EGT-GRC refers to GT-GRC plus the fixes that propose.
Sentence Interaction Models: Sequence interaction models refer the models in the style described in Section These models use some deeper interaction between contextualized token representations from both sequences without bottlenecking the interactions through pair of vectors. We use EBT-
GAU to refer to the approach described in Section 4 EGT-GAU refers to new baseline which uses the same framework as EBT-GAU except it replaces the Beam-Tree-S Seac-S with greedy STE gumbel-softmax based selection as in 9 GAU refers to plain stack of Gated Attention Units (36 (made to approximate the parameters of EBT-GAU) that do not use any Tree-Rv RvNNs and trained directly <SEP> concatenated sequence pairs.
7

---

Table 1: Empirical time and (peak) memory consumption for various models RTX A6000. Ran on 100 ListOps data with batch size and the same hyperparameters as used on ListOps on various sequence lengths. (-slice) indicates EBT-GRC without slicing from Fix 2, (512) indicates EBT-GRC with the hidden state dimension (d) set as 512 (instead of (21,.(512))) represents EBT-GRC with 512 dimensional hidden state size and without slicing.
Sequence Lengths
Model
200
250
500
600
900
1000
1500
2000
Time
Memory
Time
Memory
Time
Memory
Time
Memory
(min)
(GB)
(min)
(GB)
(min)
(GB)
(min)
(GB)
OM
8.0
0.09
20.6
0.21
38.2
0.35
76.6
0.68
CRvNN
1.5
1.57
4.3
12.2
8.0
42.79
OOM
OOM
GT-GRC
0.5
0.35
2.1
1.95
3.5
5.45
7.1
21.76
EGT-GRC
1
0.07
2.5
0.3
4.3
0.81
8.5
3.15
BT-GRC
1.1
1.71
2.6
9.82
5.1
27.27
OOM
OOM
BT-GRC OS
1.4
2.74
4.0
15.5
7.1
42.95
OOM
OOM
EBT-GRC
1.2
0.19
3.2
1.01
5.5
2.78
10.5
10.97
- slice
1.2
0.35
3.2
1.95
5.4
5.4
10.3
21.12
(512)
1.2
0.41
3.3
1.29
5.6
3.13
12.1
11.41
(512,- slice)
1.2
1.55
3.3
7.77
5.5
21.02
OOM
OOM
5.2 Efficiency Analysis
In Table I we compare the empirical time-memory trade offs the most relevant Tree-RvNN models (particularly those that competent in ListOps and logical inference). We use CRvNN in the no halting mode as [66] because otherwise can start to halt trivially because of limited training data. For the splits of lengths 200 1000
the data shared by Havrylov et al. [I; for the 1500 2000 split we sample from the training set of LRA listops 81.
We can observe from the table that EBT-GRC achieves better memory efficiency among all the strong RvNN contenders (GT-GRC and EGT-GRC fail on ListOps/Logical inference) except for OM. However, OM's memory efficiency comes with massive cost in time, being nearly 8 times slower than EBT-GRC. Compared to BT-GRC OS's 43GB peak memory consumption in 900-1000 sequence length from [66]. the memory consumption of EBT-GRC is reduced to only 2.8GB. Even compared to BT-GRC, the reduction is near ten times. EBT-GRC even outperforms the original greedy GT-GRC used in Choi al. [9]. Removing the slicing from the full model EBT-GRC (i.c., -sicee can substantially increase the memory cost. This becomes most apparent when training with higher hidden state size (compare (512) vs. (512, -lice)). This shows the effectiveness of slicing.
5.3 Results
Hyperparameters are presented in Appendix G architecture details are presented in Appendix F task details are provided Appendix and additional results (besides what presented below) in logical inference and text classification are provided in Appendix
List Operations (ListOps): The task of ListOps consist of hierarchical nested operations that neural networks generally struggle to solve particularly in length-generrlizabble settings. There are only a few known contenders that achieve decent performance in the task [3] I0 71 66]. For this task
we use the original training set [57] with the length generalization splits from Havrylov et al. [31] the argument generalization splits from Ray Chowdhury and Caragea (66), and the LRA from Tay et al. [8I). The different splits test the model in different out-of-diittibuttinn settings (one in unseen lengths, another in an unseen number of arguments, and another in both unseen lengths and arguments). Remarkably, as can be seen from Table 2 EBT-GRC outperforms most of the previous models in accuracy only being slightly behind OM for some argument generalization splits. EBT-GRC- Sliic represents the performance of EBT-GRC without slicing. It shows that slicing in fact improves the accuracy as well this context but even without slicing the model better than BT-GRC or BT-GRC OS.

---

Table 2: Accuracy on ListOps. For models, report the median of runs. Our models were trained on lengths Σ 100, depth I 20, and arguments Σ 5. represents results copied from [71].
We bold the best results that do not use gold trees. Subscript represents standard deviation. As example, 90, = 90 + 0.1
Model
near-IID
Length Gen.
Argument Gen.
LRA
(Lengths)
2 1000
200-300
500-600
900-1000
100-1000
100-1000
2000
(Arguments)
<
<
<
10
15
10
With gold trees
GoldTreeGRC
99.9.2
99.9,9
99.81
100.5
81.228
79.514
78.520
Baselines without gold trees
Transformer x
57.4g
UT
71.578
GT-GRC
754.6
47.7a.4
42.72.
37.5337
50.915
51 31.416
45.312
EGT-GRC
84.219
51.337
42.935
34.435
44.717
40.816
34.414
OM
99.9.3 3
99.6.7
92.413
76.313
83. 224
76.3ss
79.3
CRvNN
99.72.s
98.811
97.223
94.949
66 66.640
43.73s
55.38
BT-GRC
99.42.7
96.810
93.622
88.427
75.228
59.179
63.467
BT-GRC OS
99.6s.4
97.2ab
94.8uo
92.2sc
73.3g4
63.1u2
66.
EBT-GRC
99.9o.3
99.72.4
99.51
99.3s
82.513
79.6g.7
79.3s.a
EBT-GRC Slice
99.73
98. 98.6612
98.417
98.614
79.320
74.4s7
75.52s
Logical Inference and Sentiment Classification: We show the results of our models in formal logical inference (another dataset where only RvNN-like models have shown some success) and sentiment classification in Appendix C There show that our EBT-GRC can easily keep up these tasks with BT-GRC despite being much more efficient.
NLI and Paraphrase Detection: As we can see from Table although EBT-GRC does not strictly outperform BT-GRC or BT-GRC OS, it remains in the same ballpark performance. The sentence interaction models, unsurprisingly, tend to have higher scores that sentence encoder modes because of their more parameters and more interaction space. We do not treat them commensurate here. Among the sequence interaction models, our EBT-GAU generally outperforms both baseline models in its vicinity GAU and EGT-GAU. Even when used conjunction with Transformer, beam search still maintains some usefulness over simpler STE-based greedy search (EGT-GAU) and it shows some potential against pure Transformer stacks as well (GAU).
Conclusion
We identify memory bottleneck in popular RyNN framework 9 which has caused BT-RvNN [66] to require more memory than it needs to. Mitigating this bottleneck allows us to reduce the memory consumption of EBBTRvNNN (an efficient variant of BT-RvNN) by 10-16 times without much other cost and while preserving similar task performances (and sometimes even heating the original BT-RvNN). The fixes also equally apply any model using the framework including the original Gumbel Tree model [9]. We believe our work can serve as a basic baseline and bridge for the development of more scalable models in the RvNN family and beyond.
Limitations
Although our proposal improves upon the computational trade-offs over some of the prior works [ 66 7T. it can be still more expensive than standard RNNs although we address this limitation, to an extent, in our concurrent work [65]. Moreover, our investigation of utilizing bottom-up Tree- RvNNs for top-down signal (without using expensive CYK models [5] 16) is rather preliminary (efficiency being our main focus). This area of investigation needs to be focused more in the future.
Moreover, although our proposal reduces memory usage it does not help much on accuracy scores compared with other competitive RvNNs.

---

Table 3: Mean accuracy and standard deviaton on SNLI [6] QQP, and MNLI 89 Hard represents
the SNLI test set from Gururangan et [28] Break represents the SNLI test set from Glockner
et al. 22 Count. represents the counterfactual test set from Kaushik et al. [38]. PAWSQQP and
PAWSW SWIKI are adversarial sets from Zhang al. 197]. ConjNLI is the dev set from Saha et al. [67]. NegM,NegMM,LLeMM..oooo
are Negation Match, Negation Mismatch, Length Match, Length Mismatch stress test sets from Naik al. [56] respectively. Our models were run times on different seeds. Subscript represents standard deviation. As an example, 901
90 + 0.1
SNLI Training
QQP Training
Models
IID
Hard
Break
Count.
IID
PAWSQQP
PAWS
(Sequence Encoder Models)
CRvNN
85.32
70.6,
55.317
59.8g
84.83
34.87
46.6,
OM
85.52
70.63
67.49
59.92
84.60
38.17
45.6g
BT-GRC
84.91
70;
51
594
84.7G
36.917
46.412
BT-GRC OS
84.91
70.3
53. 53.2910
58.6g
84.22
37.1g
46.36
EBT-GRC
84.74
69.9g
55.620
58.11
84.32
36.9s
47.5s
(Sequence Interaction Models)
GAU
872
74.24
69.40
66.42.
83.61
38.614
47.31
EGT-GAU
87.1g
74.8.
66.112
66.22
83.5,
39.431
49.313
EBT-GAU
87.52
75.73
7026
67.64
83.92
42 42.335
47.2g
MNLI Training
Models
Match
MM
ConjNLI
NegM
NegMM
LenM
LenMM
(Sequence Encoder Models)
CRvNN
72.24
72.6;
41.7
52.8c
53.84.2
6244
63.347
OM
72.53
732
41.74
50.97
51.713
56.5g3
57.06g1
BT-GRC
71.62
72.31
40.76
53.737
54.843
64.76
66.45
BT-GRC OS
71.71
71.92
41.2g
53.22
54.2s
65. 65.613
66.79
EBT-GRC
72.12
721
40.93o
52.3323
53.2822
64.9210
66.410
(Sequence Interaction Models)
GAU
76.43
76.52
53.512
48.2
48. 48.2411
69.620
70.622
EGT-GAU
75.12
75.53
53.14
48.714
48.614
69.813
70.6
EBT-GAU
76.51
76.92
53.318
49.24
49g
71.618
72.519
Acknowledgments
This research is supported in part by NSF CAREER award #1802358, NSF IIS award #2107518 18, and UIC Discovery Partners Institute (DPI) award. Any opinions, findings, and conclusions expressed here are those of the authors and do not necessarily reflect the views of NSF or DPI. We thank our anonymous reviewers for their constructive feedback.
References
[1] Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. In Yoshua Bengio and Yann LeCun. editors, 3rd International Conference on Learning Representations, ICLR 2015, San Diego CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015. http:// http://xxivvvrrr.g.. orgg abs/ 1409..99... 0473
[2] Shaojie Bai, J. Zico Kolter, and Vladlen Koltun. Deep equilibrium models. In
Н. Wallach, H. Larochelle, A. Beygelzimer, d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran As- sociates, Inc., 2019. URI. htttps::/proceeddngg/ wwwrdiinnnn..u.u........ wwweurips.ccppppeeeeee 11336666dee00110000cc///66666633 Papel pdf
httpsaarrrpp..cpppppp///////1111 /pce/ppper//2///llee//
10

---

[3] Andrea Banino, Jan Balaguer, and Charles Blundell. Pondemet: Learning to ponder. ICML Workshop, abs/2107.05407, 2021. /ttps:////ar abs/2107
05407
[4] Yoshua Bengio, Nicholas Léonard, and Aaron C. Courville. Estimating or propagating gradients through stochastic neurons for conditional computation. CoRR, abs/1 2013. URL
http:://axxiv.orgg///
3432
[5] Ben Bogin, Sanjay Subramanian, Matt Gardner, and Jonathan Berant. Latent compositional representations improve systematic generalization in grounded question answering. Transactions of the Association for Computaaiional Linguistics, 9:195-210, 2021. doi: 10.1162/tacl a 003361. URL
[6] Samuel R. Bowman, Gabor Angeli, Christopher Potts, and Christopher D. Manning. A large annotated corpus for learning natural language inference. In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pages 632-642, Lisbon, Portugal, September 2015. Association for Computational Linguistics. doi: 10.18653/ URL
https://aclanthhoogg -tw.Looyyy..//1--1117770
[7] Samuel Bowman, Christopher Manning, and Christopher Potts. Tree-structured compo- sition in neural networks without tree-structured architectures. In Proceedings of the 2015th International Conference on Cognitive Computation: Integrating Neurul and Symbolic Ap- proaches Volume 1583, COCO'15, page 37-42, Aachen, DEU, 2015. CEUR-WS.org
[8] Samuel Bowman, Jon Gauthier, Abhinav Rastogi, Raghav Gupta, Christopher D. Manning, and Christopher Potts. A fast unified model for parsing and sentence understanding. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 1466-1477, Berlin, Germany, August 2016. Association for Computational Linguistics. doi: 10. 10.18653/11111-1111 139. URLhtttps: httpttssss/aaaaalllllloooo/
org/
P16- 1139
[9] Jihun Choi, Kang Min Yoo, and Sang-goo Lee. Learning to compose task-specific tree structures. In Sheila A. Mellraith and Kilian Q. Weinberger, editors, Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Intelligence (IAAI-18), and the 8th AAAI Symposium on Educational Advances Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018, pages 5094-5101. AAAI Press, 2018. URL URL httlhttps:.. / /wwww/ aaai org/ ocs/ iid/xxndxxx/////e http/AAAT/AAAA8/pppeer view file/1666 16682
[10] Jishnu Ray Chowdhury and Cornelia Caragea. Modeling hierarchical structures with continuous recursive neural networks. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 1975-1988, PMLR, 18-24 Jul 2021. httphtts:://proeeee
mlr. wttp://vvv9//chhccecee
[11] Caio Corro and Ivan Titov. Learning latent trees with stochastic perturbations and differentiabbee dynamic programming. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages
Florence, Italy, July 2019. Association for org/
Computational Linguistics. doi: 10.18653//1/P11-15551
P19-1551
[12] Róbert Csordás, Kazuki Irie, and Jürgen Schmidhuber. The neural data router: Adaptive control flow in transformers improves systematic generalization. In International Conference on Learning Representations, 2022. htR/httpp::/ppprriiee..eee
[13] Mostafa Dehghani, Stephan Gouws, Oriol Vinyals, Jakob Uszkoreit, and Lukasz Kaiser. Uni- versal transformers. In International Conference on Learning Representations, 2019. URL
[14] Gr'egoire Del'etang, Anian Ruoss, Jordi Grau-Moya, Tim Genewein, Li Kevin Wenliang, Elliot Catt, Mareus Hutter, Shane Legg, and Pedro A. Ortega. Neural networks and the chomsky hierarchy. ArXiv, hbs/2207.02099 2022.

---

[15] Andrew Drozdov, Patrick Verga, Mohit Yadav, Mohit lyyer, and Andrew McCallum. Unsuper- vised latent tree induction with deep outidee recursive auto-encoders. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume (L.ngg and Short Papers), pages 1129- 1141, Minneapolis, Minnesota, June 2019. Association for Computational Linguistics. doi: 10. 1..1865////N1--1116 URL hwtpr///aaaaaaaoooooooroeeee
1116
[16] Andrew Drozdov, Subendhu Rongali, Yi-Pei Chen, Tim O'Gorman Mohit lyyer, and Andrew McCallum. 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), pages 4832-4845, Online, November 2020. Association for Computational Linguistics. doi: swtichologgyorgg20000 wttpg/2222.mmmmmmmaai.... emnlp-main 392
URL https://
[17] Brian DuSell and David Chiang. Learning context-free languages with nondeterministic stack RNNs. In Proceedings of the 24th Conference on Computational Natural Language Learning, pages 507-519, Online, November 2020. Association for Computational Linguistics. doi: 10.18653/112220.coolll 1.41. URL
org /0200000 20t00...ooo2.... cowlloonllllll 1.11
[18] Brian DuSell and David Chiang. Learning hierarchical structures with differentiable nonde- terministic stacks. In International Conference Learning Representations, 2022. URL
https://opeareeves: wwtprriieennntefffoeeeo www.oooummddddddooeooo.
[19] Jeffrey L. Elman. Finding structure time. Cognitive Science 14(2):179 211, 1990.
ISSN 0364-0213. doi: http:///...rrg///..//00/06666210
URL httpst //wb
sciencedirect. wtt./cccccccceeeeeeeeeeeeccc.cee wwtia/ccaaatt.cele.////////00100
[20] Hao Fei, Yafeng Ren, and Donghong Ji. Retrofitting structure-aware transformer language model for end tasks. In Proceedings of the 2020 Conference on Empirical Methods in Natural
Language Processing (EMNLP), pages 2151-2161, Online, November 2020. Association for Computational Linguistics. doi: 10. 1865/v 1/2020. wttp:/000mmmmmmaa..m66.... URL https://
aclanthology. org 20200. emnlp-main main. 168
[21] Matt Gardner, Yoav Artzi, Victoria Basmov, Jonathan Berant, Ben Bogin, Sihao Chen, Pradeep Dasigi, Dheeru Dua, Yanai Elazar, Ananth Gottumukkala, Nitish Gupta, Hannaneh 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, Eric Wallace, Ally Zhang, and Ben Zhou Evaluating models' local decision boundaries via contrast sets. In Findings of the Association for Computational Linguistics: EMNLP 2020, pages 1307-1323, Online, November 2020. Association for Computationnl Linguistics. doi: 10.18653/v1/2020 findings-cmmlp.117. 117. URL /tttps://acaateee
org 2020 www.iiininng-i.. emnlp 117
[22]
Max Glockner, Vered Shwartz, and Yoav Goldberg. Breaking NLI systems with sentences that require simple lexical inferences. In Proceedings of the 56th Annual Meeting of the Association for Computationaal Linguisties ( (Volume 2: Short Papers), pages 650-655, Melbourne, Australia, July 2018, Association for Computational Linguistics. doi: 10. 1/15182211 URL
https://cclartholpgg org/ P18- 2103
[23] Yoav Goldberg and Michael Elhadad. An efficient algorithm for easy-first non-directional dependency parsing. In Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics, pages 742- 750, Los Angeles, California, June 2010. Association for Computational Linguistics. URL httpps:/aallanthology/ org/N10-1111
[24] C. Gollee and A. Kuchler. Learning lask-dependent distributed representations by backprop- agation through structure. Proceedings of International Conference on Neural Networks (ICNN'96), volume 1, pages 347-352 vol.1, 1996. doi: 10. 199/1CNNN.196.548911
[25] Alex Graves. Adaptive computation time for recurrent neural networks. ArXiv, 1bs/16603.888 2016.
10tpp//81100000333333 08983
[26] Albert Gu, Karan Goel, and Christopher Ré. Efficiently modeling long sequences with structured state spaces. arXiv preprint arXiv:2111.00396, 2021.
12

---

[27] Ankit Gupta, Albert Gu, and Jonathan Berant. Diagonal state spaces are as effective as structured state spaces. Advances in Neural Information Processing Systems, 35:22982-22999 2022.
(28) Suchin Gururangan, Swabha Swayamdipta, Omer Levy, Roy Schwartz, Samuel Bowman, and Noah A. Smith. Annotation artifacts natural language inference data. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Human Language Technologies, Volume (Short Papers), pages 107-112, New Orleans, Louisiana, June 2018, Association for Computational Linguistics. doi: 10.18653/v1/ N18-2017. URL atttps://aclantaee
Linguistics:
org/ 2017
[29] Michael Hahn. Theoretical limitations of self-attention in neural sequence models. Transactions of the Association for Computational Linguistics, 8:156-171, 171, 2020. doi: 10.1162/tacl_a_o a0000 URL hat.ittts://ccaaathollo. wwt.://ww.oooooo..r/0000.0..0.00 tac.-.......111.1111
[30] Kai Han, An Xiao, Enhua Wu, Jianyuan Guo, Chunjing Xu, and Yunhe Wang. Transformer in transformer. Advances in Neural Information Processing Systems, 34: 34:15908-15919, 2021.
[31] Serhii Havrylov, Germán Kruszewski, and Armand Joulin. Cooperative learning of disjoint syntax and semantics. 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), pages 1118-1 122,, Minneapolis, Minnesota, June 2019. Association for Computational Linguistics. doi: 10. 10.18633/1//119-111 1115. URL https: http///caaaantttooooo/oo org/N19-1115
[32] Jonathan Herzig and Jonathan Berant. basnd semantic parsing for compositional gener- alization. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Vol- ume 1: Long Papers), pages 908 921, Online, August 2021. Association for Computational Linguistics. doi: 10. 10.18653/v120211 acI-long.74 acl-long.77
URL htttss:://acaaataolooyy./ www.a/ooooooooooo///// org 2021
[33] Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural Comput., (8)1175--1880, November I 1997. ISSN 0899-7667. doi: 10. (991:///eco.1999....... 1735. URL https://aoi.org/// 1ww1//eeoo.ooeee 1997 1735
[34] 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 lan- guage modeling. In Proceedings of the 59th Annual Meeting of the Association for Com- putational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pages 4897-4908, Online, August 2021. Associa- tion for Computational Linguistics. doi: 10.18653/v1/2011 acc--
URL https
//aclanthology. org/ 20211022222222 acl-long. 379
[35] Xiang Hu, Haitao Mi, Liang Li, and Gerard de Melo. Fast-R2D2: A pretrained recursive neural network based on pruned CKY for grammar induction and text representation. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pages 2809-2821, Abu Dhabi, United Arab Emirates, December 2022. Association for Computational Linguistics. URL https: //acl hathh/olccnnnoooggyyooooo wow.ooooogooooooooooooooooo 2022. wwwne-manlll.eee main. 181
[36] Weizhe Hua, Zihang Dai, Hanxiao Liu, and Quoc Le. Transformer quality in linear time. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 9099-9117. PMLR, 17-23 Jul 2022. URL hnttps://proceeddnng mlr waasss/v62/hhua220 html
[37] Shankar Iyer, Nikhil Dandekar, and Kornél Csemnai, First quora dataset release: Question pairs. In Quora, 2017.
[38] Divyansh Kaushik, Eduard Hovy, and Zachary Lipton. Learning the difference that makes difference with conntefacttalllyaggneeeddddd data. International Conference on Learning Representations, 2020. URL http://ppenneeeeeeeeeeoooooeeeee
13

---

[39] Yoon Kim, Carl Denton, Luong Hoang, and Alexander M. Rush. Structured attention networks. International Conference on Learning Representations, 2017.
[40] Donald E. Knuth. On the translation of languages from left right. Information and Control, 8 (6):677 639, 1965. ISSN 0019-9958.
[41] Lingpeng Kong, Alexander M. Rush, and Noah A. Smith. Transforming dependencies into phrase structures. In Proceedings of the 2015 Conference of the North American Chupter of the Association for Computational Linguisties: Human Language Technologies, pages 788- 798. Denver, Colorado, May-June 2015. Association for Computational Linguistics. doi: 10.31 10.3115//1/115-1000
URLhttps:
[42] 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, editors, Proceedings of the 36th International Conference Machine Learning. volume 97 of Proceedings of Machine Learning Research, pages 3499-3508, PMLR, 09-15 Jun 2019. URL Intt::: ptttp:://proceedinggs. mlr. press/ wwtpss//vv///// w97/koo119a. html
[43] Phong Le and Willem Zuidema. Compositional distributional semantics with long short term memory. In Proceedings of the Fourth Joint Conference on Lexical and Computational Seman- rics, pages 10-19. Denver, Colorado, June 2015. Association for Computational Linguistics. doi: 10.18653/v1/S 15- 1002. URL htap::::///claanttoooooooooo
1002
[44] Phong Le and Willem Zuidema. The forest convolutional network: Compositional distributional semantics with a neural chart and without binarization. In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pages 1 1155-1164 Lisbon, Portugal, September 2015. Association for Computational Linguistics. doi: 10. 1..11655/1/D15.... 1137. URL org/ org/D15- D15 1137
nttps://aclantholle
[45]
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, pages 1129- 1 1144, Online, August 2021. Association for Computational Linguistics. doi: 10. 00.18633/v120211 findings-acl.97. URL https://acccetee http:/occclattoooyyoo.ooooo org/ 2021 www.niinnnncciii acl.nngssac.9999
[46] Qian Liu, Shengnan An, Jian-Guang Lou, Bei Chen, Zeqi Lin, Yan Gao, Bin Zhou, Nanning Zheng, and Dongmei Zhang. Compositional generalization by learning analytical expressions. In Proceedings the 34th International Conference Neural Information Processing Systems, NIPS 20, Red Hook, NY, USA, 2020. Curran Associates Inc. ISBN 9781713829546.
[47] Yang Liu and Mirella Lapata. Learning structured text representations. Transactions of the Association for Computational Linguistics, 6:63-75, 2018. doi: 10. 10.1162/taclaaaa00 Lataaclll_0000--.11
[48] 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), pages 110-114, Sofia, Bulgaria, August 2013. Association for Computational Linguistics. URL https://aclanthology) org/P13- 2020
[49] Andrew Maas, Raymond E. Daly, Peter T. 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, pages 142-
150, Portland, Oregon, USA, June 2011. Association for Computational Linguistics. URL wwwp:ioyy.rr///11111001111
[50] Jean Maillard and Stephen Clark. Latent tree learning with differentiable parsers: Shift-reduce parsing and chart parsing. In Proceedings of the Workshop on the Relevance of Linguistic Structure in Neural Architectures for NLP, pages 13-18, Melbourne, Australia, July 2018. Association for Computational Linguistics. doi: 10. 10.18663/1/W11-29003 URL https:// wwwntthooogg..rg//WB8-----
[51] Jean Maillard, Stephen Clark, and Dani Yogatama. Jointly learning sentence embeddings and syntax with unsupervised tree-Istms. Natural Language Engineering, 25(4):433 4499, 2019. doi: 10.1017/51351334999000
14

---

[52] Jiayuan 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 J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, 2021. URL https
[53] Eric Martin and Chris Cundy. Parallelizing linear recurrent neural nets over sequence length. In International Conference on Learning Representations, 2018. URL httpp:://openrevier
[54] Tom McCoy, Ellie Pavlick, and Tal Linzen. Right for the wrong reasons: Diagnosing syn- tactic heuristics in natural language inference. In Proceedings of the 57th Annual Meet- ing of the Association for Computational Linguistics, pages 2428-3448, Florence, Italy, July 2019. Association for Computational Linguistics. doi: 10. 10.18863/11/1191133 URL httpaaalllaatolooooooo///oo 1334
[55] Tsendsuren Munkhdalai and Hong Yu. Neural tree indexers for text understanding. In Pro- ceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics: Volume Long Papers, pages 11-21, Valencia, Spain, April 2017. Association for Computational Linguistics. URL http:htp::/// atttps://aclartbologgy
E17 1002
[56] Aakanksha Naik, Abhilasha Ravichander, Norman Sadeh, Carolyn Rose, and Graham Neubig. Stress test evaluation for natural language inference. In Proceedings of the 27th International Conference on Computational Linguistics, pages 2340-2353, Santa Fe, New Mexico, USA, August 2018. Association for Computational Linguistics. URL https: /topps:/werr //www.//wwww.. http://wwwwllllll... aclweb..w...... org/ anthology/CC8-114
[57] 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, pages 92-99, 29, New Orleans, Louisiana, USA, June 2018. Association for Computational Linguistics. doi: 10. 10.18663/1//N18-401111 URL https://aclanthan
org Berg/N88-400 N18-4013
[58] Xuan-Phi Nguyen, Shafiq Joty, Steven Hoi, and Richard Socher. Tree-structured attention with hierarchical accumulation. In International Conference on Learning Representations, 2020.
URL https:://ppenrevier www.:neeoooounddddddodoeooeeeeee
[59] Vlad Niculae, Andre Martins, Mathieu Blondel, and Claire Cardie. SparseMAP: Differentiable sparse structured inference. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume of Proceedings of Machine Learning Research, pages 3799-3808, Stockholmsmässan, Stockholm Sweden, 10-15 Jul 2018. PMLR.
[60] Antonio Orvieto, Samuel L Smith, Albert Gu, Anushan Fernando, Caglar Gulcehre, Razvan Pascanu, and Soham De. Resurrecting recurrent neural networks for long sequences. arXiv preprint arXiv:2303.06344 2023.
[61] Hao Peng. Sam Thomson, and Noah A. Smith. Backpropagating through structured argmax using SPIGOT. In Proceedings of the 56th Annual Meeting of the Association for Com- putational Linguistics (Volume 1: Long Papers), pages 1863-1873, Melbourne, Australia, July 2018. Association for Computational Linguistics. doi: 10. 10011863//1/118-11772 URL
[62] Jeffrey Pennington, Richard Socher, and Christopher Manning. GloVe: Global vectors for word representation. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 1532- 1532-1543, Doha, Qatar, October 2014. Association for Computational Linguistics. doi: 10.3115/v1/I4--11 URL http:://cclaattoolllge/
org/
11621162
[63] Jordan B. Pollack. Recursive distributed representations.. Artificial Intelligence, 105, 1990. ISSN 0004-3702. doi: http://doinnegll..oooooowwooooo0 URI.
15

---

[64] Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena,
Yanqi Zhou, Wei Li, and Peter J. Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. Journal of Machine Learning Research, 21(140):1-6) 2020. URL html
http://jmlr... wwtpiiir.rrgpppppaereeeee ptggpapprs//v21200
[65] Jishnu Ray Chowdhury and Comelia Caragea. Recursion in recursion: Two-level nested recursion for length generalization with scalabiliy, In Proceedings of the Neural Information Processing Systems, 2023.
[66] Jishnu Ray Chowdhury and Cornelia Caragea. Beam tree recursive cells. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 28768-28791, PMLR, 23-29 Jul 2023. URL htt.tttttt///cceeeiiiiiee
mlr press//202/rary/// 22/pa///222222ayycccuuu22222222 html
[67] Swarnadeep Saha, Yixin Nie, and Mohit Bansal. ConjNLI: Natural language inference over conjunctive sentences. In Proceedings of the 2020 Conference on Empirical Methods in Natural
Language Processing (EMNLP), pages 8240-8252, Online, November 2020. Association
for Computational Linguistics. doi: 10.18653/v 1/20000.mmmlppmmin.66... URL https://
mmg.::/...rr0022020.mmmmmmmmmaaa 661
[68] Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. Trans. Neur Netw., 20(1): jan 2009. ISSN 1045-9227. doi: 10.1 200.0NNN.000..005666
URL http:httts://dde org/ 10. 1109/TNN. 2008. 2005605
[69] M.P. Schützenbergerr. On context-fre free languages and push-down automata. Information and Control, 6(3):246 264, 1963. ISSN 0019-9958.
[70] Peter Shaw, Jakob Uszkoreit, and Ashish Vaswani. Self-attention with relative position rep- resentations. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume (Short Papers), pages 464 468, New Orleans, Louisiana, June 2018. Association for Computational Linguistics. doi: 10.18653/v 10155//1/N18--1 1/w11- 2074.. URL https: www.aaaattooooggaaoaooaooooo
[71] Yikang Shen, Shawn Tan, Arian Hosseini, Zhouhan Lin, Alessandro Sordoni, and Aaron Courville. Ordered memory. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché- Buc, F. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 5037-5048. Curran Associates, Inc., 2019. URL http:: wwwp.cc/pappp..... 8748-ordered memory. pd.
[72] Yikang Shen, Shawn Tan, Alessandro Sordoni, and Aaron Courville. Ordered neurons: Inte- grating tree structures into recurrent neural networks. In International Conference on Learning Representations, 2019. URL http:tt/opppeeeeeieeeee wwwpaarwwwwe..eeeoorrereee
[73] Yikang Shen, Yi Tay, Che Zheng, Dara Bahri, Donald Metzler, and Aaron Courville. Struct- Former: Joint unsupervised induction of dependency and constituency structure from masked language modeling. In Proceedings of the 59th Annual Meeting of the Association for Com- putational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pages 7209, Online, August 2021. Associa- tion for Computational Linguistics. doi: 10.18663/v1/2021.aadl //aclanthology.... org/ 202110222222 acl-long. 559
URL https
[74] Zhiqiang Shen, Zechun Liu, and Eric Xing. Sliced recursive transformer. In Computer Vision- ECCV 2022: 17th European Conference, Tel Aviv, Israel, October 23-27, 2022, Proceedings, Part XXIV, pages 727-744. Springer, 2022.
[75] Haoyue Shi, Hao Zhou, Jiaze Chen, and Lei Li. On tree-based neural sentence modeling. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, 2018. Association for Computational oww.aoooooooooor/1-----0190 orw.ggg.orrrrroe
pages 4631-4641, Brussels, Belgium, Linguisties. doi: 10.18653/v (/665//11/1181499//
[76] Bing Shuai, Zhen Zuo, Bing Wang, and Gang Wang. Dag-recurrent neural networks for scene labeling. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 3629, 2016.
16

---

[77] Richard Socher, Christopher D. Manning, and Andrew Y. Ng. Learning continuous phrase representations and syntactic parsing with recursive neural networks. In In Proceedings of the NIPS-2010 Deep Learning and Unsupervised Feature Learning Workshop, 2010.
[78] Richard Socher, Jeffrey Pennington, Eric H. Huang, Andrew Y. Ng. and Christopher D. Manning. Semi- supervise recursive autoencoders for predicting sentiment distributions. In Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing, pages 15 161, Edinburgh, Scotland, UK., July 2011. 1. Association for Computational Linguisties. URL
http:s///ccllatthoooooooor/////
[79] 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, pages
Seattle, Washington, USA, October 2013. Association for Computational Linguistics. URL htttp://aaclaatthlooggy.. org Dtrg/DD3-110 1170
[80]
Kai Sheng Tai, Richard Socher, and Christopher D. Manning, Improved semantic representa- tions from rre-struutured long short-term memory networks. Proceedings of the 53rd Annual Meeting of the Association for Compulational Linguistics and the 7th International Joini Con- ference on Natural Language Processing /Volume 1: Long Papers), pages 1556-1566, Beijing, China, July 2015. Association for Computational Linguistics. doi: 10.3115/v1/P15-1133 URL
htttps:/aclanthoon hccp http://aaaantooogg...oooo htwpolooyy.rg/11--..1 1150
[81] Yi Tay, Mostafa Dehghani, Samira Abnar, Yikang Shen, Dara Bahri, Philip Pham, Jinfeng Rao, Liu Yang, Sebastian Ruder, and Donald Metzler. Long range arena A benchmark for efficient transformers. International Conference on Learning Representations, 2021. URL
www..eetooooomdddd//eeeeeeeeeeee http:://ppaaeeiie...ee//rrrrrrr
grCC
[82] Zhiyang Teng and Yue Zhang. Head-lexicalized bidirectional tree LSTMs. Transactions of the Association for Computational Linguistics, 5:163-177, 2017. doi: 10. 162 a_00053, URL
nttps://aclanthol
org/ 1012
[83] Veronika Thost and Jie Chen. Directed acyclic graph neural networks. In International Conference on Learning Representations, 2021. [ttL/attts://pperreeet wttp:eewwwwwwwweeeeeeeeeeeee net/forum?
1d=JbuYF433WWB6
[84] Ke Tran, Arianna Bisazza, and Christof Monz. The importance of being recurrent for modeling hierarchical structure. Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pages 4731-4736, Brussels, Belgium, October- November 2018. Association for Computational Linguisties. doi: 10.18653/v1/D18-11 1503. URL httpp://acclanthologg oog//18-1/1000
[85] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, f. ukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Gar- nett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017. URL # Pape .ddf
[86) Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018. URL /tt//ttte///ooeeriiiiie
net fow.ooodddddddpiiiiiioooooo
[87] Yaushian Wang, Hung- Yi Lee, and Yun-Nung Chen. Tree transformer: Integrating tree structures into self-attention. In Proceedings of the 2019 Conference on Empirical Meth- ods in Natural Language Processing and the 9th International Joint Conference on Natural pages 1061-1070, Hong Kong, China, Novem- ber 2019. Association for Computational Linguistics. doi: 10.18653/1//19--100 1098. URL https://adlanthologg.ooot http://attttooooeoooo///-------0 D19
Language Processing (F.NN.P-IJCNLL)
[88] Zhiguo Wang, Wael Hamza, and Radu Florian. Bilateral multi-perspective matching for natural language sentences. Proceedings of the 26th International Joint Conference on Artificial Intelligence, IJCAI' page 4144-4150. AAAI Press, 2017. ISBN 9780999241103.
17

---

[89] Adina Williams, Nikita Nangia, and Samuel Bowman. A broad-coverage challenge corpus for sentence understanding through inference. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume (Long Papers), pages 1112-1122, New Orleans, Louisiana, June 2018. Association for Computational Linguisties. doi: 10.18653/11/1881111 URL https paallanthology.org
[90] Zhaofeng Wu. Learning with latent structures in natural language processing: A survey, arXiv preprint arXiv:2201.004990 2022.
[91] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 2-41),4-24, 2021. doi: 10. 109/TNNI 20........2.288386.
[92] Zihao Ye, Qipeng Guo, Quan Gan, Xipeng Qiu, and Zheng Zhang. Bp-rransformer: Modelling long-range context via binary partitioning. arXiv preprint 1911. 1.04070, 2019.
[93] Dani Yogatama, Phil Blunsom, Chris Dyer, Edward Grefenstette, and Wang Ling. Learning to compose words into sentences with reinforcement learning. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017.
[94] Fabio Massimo Zanzotto, Andrea Santilli, Leonardo Ranaldi, Dario Onorati, Pierfrancesco Tommasino, and Francesca Fallucchi. KERMIT: Complementing transformer architectures with encoders of explicit syntactic interpretations. In Proceedings of the 2020 Conference on Empiri- cal Methods in Natural Language Processing (EMNLP), pages 256-2611 267, Online, November 2020. Association for Computational Linguistics. doi: 10. 12116666/11122000mmmmmmmmaaaa 18. URL httts://aclaathoology org/ 2220020000222 emnlp-maaaeeeeeeeeeee aapppmmin.....
[95] 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 J. Wortman Vaughan, editors, Advances in Neural Information Processing Syslems, volume 34, pages 501-6514. Curran Associates, Inc., 2021. URL htttps:/pprocedd// Paperr
[96] Yu Zhang, Qingrong Xia, Shilin Zhou, Yong Jiang, Guohong Fu, and Min Zhang. Semantic role labeling dependency parsing: Exploring latent tree structures inside arguments. In Proceedings of the 29th International Conference on Computational Linguistics, pages 4212- 4227, Gyeongju, Republic of Korea, October 2022. International Committee on Computational Linguistics. URL
2022. wwt................. -olinn-1.3770
[97] Yuan Zhang, Jason Baldridge, and Luheng He. PAWS: Paraphrase adversaries from word scrambling. 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), pages 1298-1308, Minneapolis, Minnesota, June 2019. Association for Computational Linguistics. doi: 10. 11188//1//11--11331 URL http::ttp//// httpsth/t//://alattttt https/:///ccaaahlaaa/a org/N19- 1131
[98] Xiaodan Zhu, Parinaz Sobihani, and Hongyu Guo. Long short-term memory over recursive structures. In Francis Bach and David Blei, editors, Proceedings of the 32nd International Conference on Machine Learning. volume 37 of Proceedings of Machine Learning Research, pages 1614-1612, Lille, France, 07-09 Jul 2015. PMLR. http:tttt/oocceeeeeee press Cress/v37/aee 22ub11. html
mlr
[99] Xiaodan Zhu, Parinaz Sobhani, and Hongyu Guo. DAG-structured long short-term memory for semantic compositionality. In Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 917-926, San Diego California, June 2016. Association for Computational Linguistics. doi: 18.18653/v 1/N1/////11111/ 106. httppp:///llaattooggroo/////////
18

---

A Appendix Organization
In Section we describe the settings all the tasks and datasets that we have tested our models on. In Section we provide additional results on logical inference and sentiment classification. Then, in we present the pseudocode for EBT-RyNN, In Section [) we detail our architecture setup including the sequence-interaatioo models. In Section we provide our hyperparameters.
Section D we present an extended survey of related works. In Section E
B Task Details
ListOps: ListOps was introduced by Nangia and Bowman [57] and is a task for solving nested lists of mathematical operations. It is a 10-way classification task. Similar to Chowdhury and Caragea [10], we train models on the original training set with all samples 100 sequence lengths filtered out. We use the original development set for validation. We test on the following sets: the original test set (near-IID IID split); the length generalization splits from Havrylov et al. [3]] that include samples of much higher lengths; the argument generalization splits from Ray Chowdhury and Caragea [66] that involve unseen number of maximum arguments for each operator; and the LRA split (which has both higher sequence length and higher argument number) from Tay et al. [8].
Logical Inference introduced by Bowman et al. 7 and is task that involves classifying fine-grained inferential relations between two given sequences in a form similar to that of formal sentences of propositional logic. Similar to Tran et al.
Logical Inference:
[4 our models were trained on splits with logical connectives & 6. We show the results in OOD test sets with logical connections 10-12. We use the same splits Shen et al. (71), Tran et al. (84), Chowdhury and Caragea [10].
SST5: SST5 is a fine-gres fine-grained 5-way sentiment classification task introduced by Socher et al. We use the original splits.
IMDB: IMDB is binary sentiment classification task from Maas et al. 49 We use the same train,
validation, and IID test sets as created in Ray Chowdhury and Caragea (66) We also use the contrast
set Gardner al. 12 and counterfactual set Kaushik et al. 38 additional test splits.
is a task of classifying whether two given sequences in a pair are paraphrases of each other or not. Following prior works Wang et al. (88), randomly sample 10, 000 samples for validation and IID test set such that for each split 5, 000 samples are maintained to be paraphrases and the other 5, 000 are maintained to be not paraphrases. We also use the adversarial test sets PAWSQQP and PAWSwra IKJ form Zhang et al. (97].
QQP: QQF
SNLI: SNLI 6 is natural language inference (NLJ) task. It is 3-way classification task to classify the inferential relation between two given sequences. We use the same train, development, and III) test set splits in Chowdhury and Caragea [10]. Any data with a sequence of length > 150 is filtered out from the training set for efficiency. We use also additional test set splits for stress tests. We use the hard test set split from Gururangan et al. (28), the break test set from Glockner et al. 22 and the
counterfactual test set from Kaushik et al. 38
MNLI: MNLI 89 is another NLI dataset, which is similar to SNLI in format. We use the original development sets (match and mismatch) as test sets. We filter out all data with any sequence length 2 150 from the training set. Our actual development set is a random sample of 10. 000 data-points from the filtered training set. As additional testing sets, we use the development set of Conjunctive NLI (ConjNLI) [7] and a few of the stress sets from Naik et al. (56). These stress test sets include - Negation Match (NegM), Negation Mismatch (NegMM), Length Match (LenM), and Length Mismatch (LenMM). NegM and NegMM add tautologies containing "not" terms this can bias the models to classify contradiction as the inferential relation because the training set contains spurious correlations between existence of "not" related terms and the class of contradiction. LenM and LenMM add tautologies to artificially increase the lengths of the samples without changing the inferential relation class.
httte::/aaaaa.uuraacco///// Sttt-ssss---ttoo----tt-tee----e
Dataset- Dataset-Release- htt.ett-oooeeeeee-uuttioooaliii-
19

---

Table 4: Mean accuracy and standard deviation the Logical Inference 7 for 2 10 number of operations after training on samples with Σ 6 operations, and on SST5 [79] and IMDB [49]. Count. represents counterfactual test split from Kaushik et al. [88 and Cont. represents contrast test split from Gardner et al. [2 The best results are shown in bold. Our models were run 3 times on different
seeds. Subscript represents standard deviation. As example, 901 90 + 0.1
Logical Inference
SST5
IMDB
Model
Number of Operations
10
11
12
IID
IID
Cont.
Count.
GR-
90.3322
88.431
85. 7024
51.676.6
85.11.0
70.6321
81.97s
EGT-GRC
75.79e1
73.386s
89.688.8
51.6314
86.582.7
72g.2
81.7614
CRvNN
94.512.9
94.48p.
92.7315
51.7511
91.471.2
77.8015
85.383.5
OM
94.952
93.92.2
93.36g.2
52.302.7
91.699..
76.98
83,687.8
BT-GRC
95.042.3
94.29s.6
9
52.324.7
91.291.2
75.0720
82.8623
BT-GRC os
95.434.5
94.216.6
93.39
51.927.2
90.86a.3
75.6821
84.7711
EBT-GRC
94.951.5
93.877.4
93.04g.7
52.22;
91.471.2
76.1617
84.2912
C Additional Results
In T we show that our EBT-GRC model can keep up fairly well with BT-GRC and BT-GRC OS on logical inference 7 and sentiment classification tasks like SST5 [79]. and IMDB (21) while being much more computationally efficient as demonstrated in the main paper. Additional comparisons with other models like Transformers and Universal Transformer in logical inference can be found in prior works Shen et al. 711. Tran et al. [4]. They underperform RNNs and RvNNs in logical inference.
D Extended Related Works
RrNN History: Recursive Neural Networks (RvNNs) in the more specified sense of building
representations through trees and directed acyelic graphs were proposed in [63 [4]. Socher et al.
77 78 79 extended the use of RyNNs in Natural Language Processing (NLP) by considering
constituency trees and dependency trees. A few works [98
43 99 started adapting Long 80
Shot-term Memory Networks 333 a cell function for recursive processing. Le and Zuidema
Maillard et al. [51] proposed a chart-based method for simulating bottom-up Recursive Neural Networks through dynamic programming. Shi et (75) Munkhdalai and Yu (55) explored heuristics- based tree-structured RvNNs
44.
RyNNs also be simulated by stack-augmente recurrent neural networks (RNNs) to an extent (similar to how pushdown automata can model context-free grammar [69 40).. There are multiple works stack-augmented RNNs 8 99 50). Ordered Memory [71] is of the more modern such examples. More recently, DuSell and Chiang [17 explored non-deterministic stack augmented RNNs and Del' etang et al. [14] explored other expressive models. Wu [90 presented survey of latent structure models.
48 for auto-parsing structures for recursion utilizing STE gumbel softmax for gradient signals. Peng et al. [6] extended the framework with SPIGOT and Havrylov et al. 31 extended it with reinforcement learning (RL.. Ray Chowdhury and Caragea [66] extended with beam search and soft top-k. Chowdhury and Caragea [10.. Zhang et al. 195 introduced different forms of soft-recursion.
Choi et al. 9 proposed greedy search strategy based easy-first algorithm 23
Top-down Signal: Similar us, Teng and Zhang 82 explored bidirectional signal propagation (bottom-up and tow-d However, they sent top-down signal in a sequential manner which can be expensive- either can get slow without parallelization or memory expensive with parallelization of contextualization of nodes in the same height. Our approach in EBT-GAU also has some kinship with Br-rrrosfrreer [92]. BP- Transsfffrrerr allows message passing between fixed subset of parent nodes and terminal nodes created using a heuristics-basse based balanced binary tree.
Chart-based models can also create sequence contextualized representations [15] [6] but they can be
quite expensive by default [66] needing their separate techniques [34] 35
20

---

Algorithm Efficient Beam Tree Cell (without slicing)
Input: data X 22, mn (beam size)
BeamX +- [X]
BcorSsores +- [0]
while True do
if len (Bam.XX00 [0]) = 1 then
BeamX < [beam[() for beam in Beam
break end if
if ten (eeeBaamX = 2 then
BeamX + (bell( beam([]) for beam in BeamX]
break end if
New BeamX + N NewBeaaSss
for Beam, Braam,Bammcore in zip( BeamX, BeamScores) do
Scores < log sof ( [scorer(beam]] [i], beamli (i + 1J) for parent in Parents))
Indices topk (Scores,
for in range(K) K) do newBeam + deepcopyy
newBeam) Indices [i]] < cell Beam [ndices[dd) Beam [Inicess[]] + 1])
Delete new Beam [ndices[i] + 1]
New Bee.Beeam...pppdnneeeeee.e
newSe <- Beam + Scores [codes
new Bew.eeaaas.sss...c SewamnSerrr...ppeenneeessrrrrrr
end for end for
Indices +- Bean(eeeeBaeooreeee
BeamScores + new a for i Indices]
BeamX + [new Beam for in Indices] end while
BeamScores Softmar( (BeamScores) Softmax(BeamScorre)
Return sum ([score for score, X in zip( BeanSSores,, BeamX)))
Transformers RvNNs:
There have been several approaches to incorporating RvNN-like inductive biases to Transformers. For instance, Universal Transformer [13 introduced weight-sharing and dynamic halt to Transformers. Csordás al. [12 extended on universal transformer with geometric attention for locality bias and gating. Shen et al. [74] built weight-shared transformers with high layer depth and group self-attention. Wang et al. [87]. Nguyen et (58), Shen et al. [73] added hierarchical structural biases to self-attention. Fei et al. (20) biased pre-trained Transformers have constituent information in intermediate representations. Hu et al. [34 used Transformer as binary recursive cells in chart-based encoders.
E
Pseudocode
We present the pseudocode of EBB-RvNN in Algorithm 1 Note that the algorithms are written as they are for the sake of illustration: in practice, many of the nested loops are made parallel through batched operations.
21

---

F Architecture details
F.1 Sentence Encoder Models
For the sentence encoder models the architectural framework we use is the same siamese dual-encoder setup as Ray Chowdhury and Caragea [66].
F.2 Sentence Interaction Models
GAU-Block: Our specific implementation of a GAU-block (36] is detailed below. Our GAU- Block can be defined GAUBlock(z.
G). The function arguments are of the following forms: mpndd p RR' and G [0,1)=xl_ accepts the main sequence of vectors that is to serve as attention queries; p accepts either the sequence of intermediate node representations created from our RvNN (for parent attention) or it accepts the same input as z (for usual cases); p serves as keys and values for attention; G accepts either the adjacency matrix in case of parent attention (where Gij = 1 iff pj is a parent of a; else G.j- = 0), otherwise, it accepts just the usual attention mask; either way, G' serves as an attention mask.
x' = LN init + binst); p' =
mit + bénct)
(8)
u == --iLLU( + bu); t = -SiLU(p' ('WW, + bw)
(9)
q == 2 R SiLUU(>WW, + bb) + zbyi k = 2 = SiLUUp/W, + (b) + zbb
(10)
A = Softmax qk
+ pos
mask = G)
(11)
22d
= Av
(12)
(u (uOv')We + bo
(13)
g = Sigmoid([o; 2 W Wgate gate + bgate)
(14)
out 0 + (1 - -g) O x
(15)
Here, Wanit RRdd, W,_ dxd, W W. E Rdd binit b, b, IR 2bg 2x, zbg
RR::, bu, by E R2dd "R, W gate E R2axd represents concatenation.
LN is layer normalization. pos is calculated using the technique of Raffel et al. 64 using relative tree height distance for parent attention, or relative positional distance for usual cases.
Let GAUStack represent some arbitrary number of compositions of GAUBlocks (multilayered GAU block). GAUStack has the same function arguments as GAUBlock. Given two sequences 1I1, x22) and their corresponding attention masks (M1, M2) as inputs where
GAU Sequence Interaction Setup:
I1 E R xd
D2 E IR xd M1 E (0, 1] 1 ,
MM E f0, 1 the GAU setup can be expressed
as:
inp [CLS + segi; + segi; SEP; CLS + 86.2,, 32 + sega]
(16)
T = GAUStack(1 = imp, = inp, G = [f:[=((M (MM;; a Softmax CettmaxxGGLU(-VV: by W₂ + b2)
(17)
(18)
cls' = Σ asr
(19)
logits logits GELLU(ds'WLoog blogit W + b2
(20)
Here, CLS, SEP, segı, seg2 E xd are randomly initialized trainable vectors; seg1, se92 are segment embeddings. W1 E Raaxd W₂ E mdxx1 b, b2, Koggis E RR b/ogits E RC; Wrlggit E Ieddd Wriggtte e Ird is the number of classes for the task. f is a function that takes the attention masks as input and concatenates them while adjusting for the special tokens (CLS, SEP).
EGT-GAU Sequence Interaction Setup: EGT-GAU starts from the same input as above. Let us also assume we have the EGT-GRC(x) module which takes sequence of vectors x E IR" =xd xd as the input to recursively process and outputs (cls.p. p, G) where cls E IR I is the root representation, p E Ix is the sequence of non-terminal representations from the tree, and G' E {0, 1]nxl is the
22

---

adjacency matrix for parent attention (i.e.. Giy = 1 iff pj is parent of 2;, else G55 = 0). Technically, tree height information is also extracted for relative position but we do not express that explicitly for the sake of brevity. With these elements, EGT-GAU can be expressed as below:
cls Pl, G = EGT-GRC( = =i); cls2, P2, G2 = EGT-GRC(== = =x2)
(21)
1 GAUStack (xr = 21 pı, G = G1); 2/2 = GAUStack (sr = 22 P- = p2, G G2) (22)
cls GELU(cls W + W + b,2;
cls/ = GELU(clsp Wr + 1 + 62
(23)
inp = [cls] + segi: 01 + segi; SEP; cl&²2 + seg2, 2/2 + seg2]
(24)
r GAUStack2 = imp. p = imp, = [M,, M2))
(25)
Everything else after eqn. 25 is the same as eqn. 18 to 20 SEP, segi, seg2 E RR xd, seg1, se92 are segment embeddings as before. Wr's, W E IR u bft b E IR!
EBT-GAU Sequence Interaction Setup: This setup is similar to that of EGT-GAU but with few changes. EBT-GAU uses EBT-GRC as a module instead of EGT-GRC. EBT-GAU returns outputs of the form (cls, bp, 6G, s) where cls E 1R1xd is the beam-score- sean----oo-ww-eeeeddeee brrightdd-averagee root representation. bp E RRxxxx are the beams (beam size b) of sequences of non-terminal representations from the tree, &G E {0, 10,1]bxml 16xxxi are the heams of adjacency matrices for parent attention, and & E TF² are the beam scores. Let NGAUStack represent the same function as GAUStack but formalized for batched processing of multiple beams of sequences. With these elements, EBT-GAU can be expressed as:
cls1, by,, bG1, 81 EBT-GRC(z = x1); cls2, bp bG2, 82 EBT-GRC(x x22
(26)
br = repeat((11, b); da = repeat (22, b)
(27)
b = NGAUStack1 (bar bp1, bG1); bar22 = NGAUStack, (bxr2, bp2, DG2)
(28)
r = Σ s[1] ba](1)]
x/2 Σ 8[1] ba
(29)
29 the same as the equations [3 followed by the equations 18 to repeat(æ, b) changes R bæ E Rhbxa by batching the same æ for b times.
Everything else after eqn.
G Hyperparameter details
For sentence encoder models, we use the same hyperparameters as [66] (the preprint of the paper is available in the supplementary in anonymized form) for all the datasets. The only new hyper- parameter for EBT-GRC is de which we set as 64; otherwise the hyperparameters as that of BT-GRC or BT-GRC OS. We discuss the hyperparameters of the sequence interaction models next. For EBT-GAU/EGT-GAUU /GAUStack and a laree-layered weight-shared GAU-Blocks for GAUStacky (for pa- rameter efficiency and regularization). GAU uses five-layered GAU-Blocks (weights unshared) for GAUStack so that the parameters are similar to that of EBT-GAU or EGT-GAU. We use a dropout of 0.1 after the multiplation with W, in each GAUBlock layer and a head size da of 128 (similar to Hua et al. (36). For relative position, we set & = 5 (k here corresponds the receptive field for relative attention in Shaw al. (70) for normal GAUBlocks and k = 10 for parent attention (since parent attention is only applied to higher heights, we do not need to initialize weights for negative relative distances). Other hyperparameters are kept same the sentence encoder models. The hyperparameters of MNLI, SNLI, and QQP are shared. Note that all the natural language tasks are trained with fixed 840B Glove Embeddings 62 as in Ray Chowdhury and Caragea [66]. All models were trained in single Nvidia RTX A6000. The code is available in the supplementary.
the same
used two-layered weight-shared GAU-Blocks for
23


Reviews:
[{"review_id": "1yl1qWTpOk", "reviewer": "Reviewer_x8Vp", "summary": "1. This paper identify a critical memory bottleneck in both Gumbel-Tree RvNN and Beam-Tree RvNN and propose effective strategies to address it. The approaches reduce the peak memory usage of Beam-Tree RvNNs by 10-16 times in certain stress tests (refer to Table 4).\n2. This paper introduce a novel strategy that utilizes intermediate tree nodes (span representations) to provide top-down signals to the original terminal representations using a parent attention mechanism.\n3. This paper demonstrate that the proposed efficient variant of BT-RvNN incurs minimal accuracy loss compared to the original and, in some cases, even outperforms the original by a significant margin (especially in ListOps).", "questions": "1. If some baselines based on sequence-to-sequence methods are provided, the motivation for the Tree-based model will become clearer.", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. This paper identify a critical memory bottleneck in both Gumbel-Tree RvNN and Beam-Tree RvNN and propose effective strategies to address it. The approaches reduce the peak memory usage of Beam-Tree RvNNs by 10-16 times in certain stress tests (refer to Table 4).\n2. This paper introduce a novel strategy that utilizes intermediate tree nodes (span representations) to provide top-down signals to the original terminal representations using a parent attention mechanism.\n3. This paper demonstrate that the proposed efficient variant of BT-RvNN incurs minimal accuracy loss compared to the original and, in some cases, even outperforms the original by a significant margin (especially in ListOps).", "weaknesses": "The paper is written very clearly, and the methods are simple yet effective.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review. \n\nWe are currently focusing on encoder-focused tasks (classification, logical inference) like prior works on modern RvNNs [1,2,3] for which there is no seq2seq baseline (unless we use pre-trained models + prompting but they would not be fair comparisons). We agree that it is an interesting question as to how well our method can be adapted for seq2seq processing which we leave open for future exploration. This would require more extensive analysis (best suited for a separate paper) because of the lack of precedence in the application and comparison of RvNN-based models in seq2seq in a straightforward standardized manner. \n\n[1] Ordered Memory - Shen et al. Neurips 2019\n\n[2] Modeling Hierarchical Structures with Continuous Recursive Neural Networks - Ray Chowdhury et al. ICML 2021\n\n[3] Learning to Compose Task-Specific Tree Structures - Choi et al. AAAI 2018\n"}, {"review_id": "cxR5nVIvSp", "reviewer": "Reviewer_oTCB", "summary": "This paper presents a comprehensive analysis of Beam Tree Recursive Neural Networks (BT-RvNN), a recently proposed variant of recursive neural networks. The study identifies suboptimal neural network parameterization in BT-RvNNs, which adversely affects running efficiency and results in excessive memory consumption. By proposing several techniques to remove the memory bottleneck, the authors demonstrate that BT-RvNNs can be run with significantly reduced memory while still maintaining task performance. Additionally, the paper presents an attention-augmented approach to expand the score of Tree-RvNNs beyond sentence encoders to encompass sentence contextualization, enriching the potential downstream applications of Tree-RvNNs.", "questions": "1. Why does the simplified network parameterization outperform the original architecture? An in-depth examination of this (e.g., conducting ablation studies of proposed fixes) would contribute to a more comprehensive understanding of the underlying mechanisms.\n2. The experimental findings reveal that EGT-GRC exhibits a considerable performance drop compared to the original GT-GRC across diverse tasks, whereas EBT-GRC outperforms BT-GRC on most tasks. Why is this the case? The paper would benefit from providing a thorough discussion of the factors influencing the contrasting performance trends observed in EGT-GRC and EBT-GRC.\n3. Typo:\n    L269: missing close parenthesis.", "limitations": "The authors have adequately addressed the limitations.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- The paper is well structured and offers an extensive background of recursive neural networks.\n- The proposed generalization from sentence encoders to sentence contextualizers is compelling, showcasing promising empirical performance compared to plain attention modules without tree-RvNNs. This expansion broadens the potential applications of Tree-RvNNs and establishes them as building blocks with specific inductive biases for learning tasks.", "weaknesses": "- My main concern lies in the clarity of motivation. If my understanding is correct, the strategies proposed to enhance efficiency seem to be primarily related to improving neural network parameterization, rather than improving the beam tree recursion algorithm, which may have been inferred during the reading of the introduction. As a result, the motivation could be perceived more as an engineering effort with limited technical novelty.\n- Although the proposed method demonstrates a significant reduction in memory usage, the trade-off between runtime and memory utilization becomes evident in both baselines (GT-GRC and BT-GRC). A more in-depth exploration of this trade-off and its implications would enhance the comprehensiveness.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review. \n\nRegarding Weaknesses:\n\n1. Both BT-RvNN and Gumbel Tree RvNN [1] are rooted in an underlying easy-first parsing algorithm utilized in [1] (BT-RvNN is an extension of it using top-k operators and pruning). We improve the algorithm as used in [1] which also allows improvement of BT-RvNN. It’s not an improvement of parameter count but an improvement of how computation is allocated. The main improvement is the removal of the need for parallel application of the recursive cell function for all positions for scoring in every recursive iteration. Our modification allows employing the heavy recursive cell function to be applied only at one position per iteration - resulting in significant memory utilization reduction. The additional improvement from slicing is a bonus. We will improve the clarity of the motivation in the paper. \n\n2. GT-GRC/BT-GRC are only slightly faster than EGT-GRC/EBT-GRC. There isn’t a deep reason for that other than just differences in overhead - for example, EGT-GRC/EBT-GRC have to run an MLP scorer and then run the recursive cell, whereas GT-GRC/BT-GRC just run the recursive cell + single linear transformation on top of it for both scoring and the updated representation (this saves an extra layer of transformation per iteration). \n\nRegarding Questions:\n\n1. It’s possible that the disentanglement of the scorer function and the recursive cell as discussed in the paper enables a better division of labor for the parameters for ListOps. Moreover, slicing can provide an extra boost possibly by inducing an information bottleneck effect by limiting the dimensions of scorer inputs (and as we discussed in the paper, the scoring decision would hinge on more abstract type-level features which may be better represented with lower dimensions for mitigating overfitting). Ultimately, our main target was simply to reduce memory cost - the accuracy improvement in ListOps is more of a serendipity.  And the improvement is not consistent across the tasks - the big improvement is mainly in ListOps. \n\nWe also ran an additional ablation with no slicing here as per your requests (on ListOps):\n\n| Models            | IID    | 200- 300 | 500-600 | 900-1000 | 10    | 15    | LRA   |\n|-------------------|--------|----------|---------|----------|-------|-------|-------|\n| BT-GRC            | 99.39  | 96.15    | 92.55   | 86.7     | 77.1  | 63.7  | 67.3  |\n| EBT-GRC w/o slice | 99.87  | 99.35    | 99.5    | 99.6     | 79.25 | 74.35 | 75.35 |\n| EBT-GRC           | 99.9   | 99.85    | 99.4    | 99.5     | 82.95 | 79    | 79.5  |\n\n2. There is no consistent observation that EGT-GRC always underperforms GT-GRC. EGT-GRC does better than GT-GRC in some sections of ListOps, e.g. IID and length generalization 200-300. It also does well in semantic classification that we show in the Appendix (Table 1, SST5, IMDB). Overall, both the gumbel tree models, in structure-sensitive contexts, fail to model the task invariances properly leading to failure in length generalization. It’s hard to tell beyond that why one model fails “more” than the other in certain contexts. The non-efficient GT-GRC, however, does allow the use of the full hidden state features to store information relevant for scoring in a more direct manner - which is perhaps beneficial in some contexts when the structural signal is poorer (due to lack of beam search). \n\n[1]  Learning to Compose Task-Specific Tree Structures - Choi et al. AAAI 2018\n\n"}, {"review_id": "CVM9sGof61", "reviewer": "Reviewer_XtZN", "summary": "This paper makes 2 contributions. The major one is a more efficient Beam Tree Recursive Neural Network (BT-RvNN) that learns a binary tree structure over a sequence of tokens. The second is a cross attention mechanism to incorporate this tree structure into transformers.\n\nThey increase the efficiency by decreasing the hidden dimension and increasing the parallelizability and remove OneSoft. They verify that they do indeed see memory usage drop and can apply their method to longer sequences.\n\nThey achieve minimal or no loss in quality with their new efficient method when using it as a sentence encoder. Their model seems to work especially well in the sentence interaction context when they preserve the token representation.", "questions": "I don't complete understand section 4. Is the model jointly trained with the transformer or is the model trained separately and frozen and the tree structure is what is consumed?\n\nWhen using EBT-GAU vs EGT-GAU in the sentence interaction models, the difference is in the hidden states h_{i]^{t} of the tree nodes?", "limitations": "Method is still slow.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "Good exposition and necessary background provided.\n\nEfficiency results are very strong and the method clearly achieves a convincing win with memory usage.\n\nExperiments are well done a reproducible.", "weaknesses": "The part about sentence interactions detracted from the clarity of the paper since I think the main contribution is the efficiency wins.\n\nThe method on occasion does perform worse?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review.\n\nRe Weaknesses: \n\n1. We will improve Section 4, but we would like to point out that we already present more details in Appendix 5.2 [*] about the ideas from Section 4. If there are further questions, we will be happy to answer them here. \n\n2. The target of the approach is to reduce memory usage significantly while approximately preserving the accuracy performance against the original “non-efficient” approaches. As such, our approach can occasionally perform slightly better or slightly worse given that we have not introduced anything to guarantee better accuracy explicitly compared to the non-efficient variants. \n\nRe Questions:\n\n1. Yes, the model is jointly trained (end-to-end) with the transformer (not trained separately and no freezing is done).  Appendix 5.2 expands on section 4 more.  \n\n2. Yes, in the sense that EGT-GAU tree nodes are constructed by Greedy search, whereas EBT-GAU tree nodes are constructed by Beam Search. Another difference is that the former creates nodes of a single tree (L126-130 Appendix), and the latter (L139-143 Appendix) creates separate node representations per tree structure in each beam - which are later marginalized based on beam scores (eqn. 22 in Appendix). \n\n[*] There is a minor error in the Appendix. We set [M1;M2] as the input mask for the sequence concatenations in Appendix in Eqn. 10,18 but this misses the mask values for CLS and SEP special tokens. We will fix that in the final version.\n"}, {"review_id": "ZOpyjkOwjE", "reviewer": "Reviewer_S18L", "summary": "This paper relates to tree-recursive neural networks, which are a type of network where network modules are wired up in a tree structure that is itself determined by outputs of earlier parts of the network. This recursion poses significant challenges, including speed, memory usage, and potentially other issues (such as the need to use reinforcement learning to train the selection of tree structure). This paper proposes a more lightweight architecture for the portion of the network that determines the topology of the tree, in the context of a family of approaches that have good behavior in terms of gradient estimation. As a result, the method achieves both good memory usage and time complexity.\n\nAdditionally, the paper proposes the use of tree-recursive networks to produce representations for each token, instead of a single representation that summarizes the entire input.", "questions": "How does the proposed approach compare to more standard architectures like the Transformer?", "limitations": "No concerns regarding discussion of limitations.", "rating": 5, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The proposed method performs well in terms of speed, memory usage, and out-of-distribution generalization on ListOps -- it seems to be the overall winner compared to the baseline recursive NN methods.", "weaknesses": "One concern regarding Tree-RvNNs is that the efficiency limitations set put this entire class of methods outside of practical usefulness for many tasks. The paper is notably light in comparisons to other families of approaches, such as the standard Transformer. This weakness is most pronounced in the part of the paper dealing with token representations and evaluating on SNLI/QQP/MNLI, which are standard tasks to run Transformers on (unlike ListOps, where the applicability of Tree-RvNNs is readily apparent). \n\nThe part of the paper that deals with token-level encoding (Section 4) seems underdeveloped, at least compared to the discussion of Tree-RvNNs in the sentence-encoding scenarios. As a result the paper gives a bit of an impression of two distinct ideas ideas being glued together, as opposed to a more coherent direction for the work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review.\n\n**Transformer Comparison:**\n\nIn Logical Inference (Results in Table 1 Appendix), Transformers were shown to perform poorly in the same length generalization settings.  Tran et al. [1] showed that the performance of Transformers falls sharply to around 40% when generalizing to 12 logical operators settings. Shen et al. [2] managed to achieve around 48% with Transformers and Universal Transformers in similar settings. On the other hand, our proposed methods maintain 93%+. \n\nShen et al. [2] also showed Universal Transformers get only about 71.5% in the IID (let alone OOD) settings in ListOps; and Transformers perform even worse (~57%). In the appendix paper “Beam Tree Recursive Cells”, we also show that a more advanced Transformer model with RvNN-like biases (Neural Data Router [3]) is still deficient in more extreme OOD generalization even after 10 times more training data (Table 7). In contrast, our method is near perfect in length generalization. \n\nComparison in realistic data is more challenging in a parameter-controlled manner (increasing the parameters of RvNN is difficult without the section 4 approach for multi-layering otherwise increasing the parameters of recursive cells can make it very slow. On the other hand, reducing the parameters of Transformers can unnecessarily handicap it. Moreover, Transformers shine the best on those tasks with pre-training - which is a regime yet to be explored with RvNN). Note that this limitation (of lack of comparison of Transformers in realistic data) is also shared in other works on modern RvNNs [2,5] or RvNN-like Transformers [3]. \n\nNevertheless, for the token representation setting that you were asking for we do show, in Table 3, EBT-GAU (Our method + Transformer hybrid) vs GAU (Pure Transformer) in parameter-controlled settings. GAU is a popular modern Transformer variant [4] that is becoming a new standard (for example, it was adopted in the recent MEGA [6] as well). \n\n[1] The Importance of Being Recurrent for Modeling Hierarchical Structure - Tran et al. EMNLP 2018\n\n[2] Ordered Memory - Shen et al. Neurips 2019\n\n[3] The Neural Data Router: Adaptive Control Flow in Transformers Improves Systematic Generalization - Csordas et al. ICLR 2022\n\n[4] Transformer Quality in Linear Time - Hua et al. ICML 2022\n\n[5] Modeling Hierarchical Structures with Continuous Recursive Neural Networks - Ray Chowdhury et al. ICML 2021\n\n[6] Mega: Moving Average Equipped Gated Attention - Ma et al. ICLR 2023\n\n**Section 4:**\n\nWe will improve the presentation of section 4. Appendix 5.2 develops the section with more details.\n\n**Practical Use:**\n\nRvNNs can be used for practical sentence encoding tasks just as anything else. It will be slower (not unusable though) - but even in that direction, they can be improved. In another of our upcoming works, we managed to make EBT-RvNN significantly faster. \n"}]

Author rebuttal:

Meta-review: This paper addresses the memory usage challenges in the Beam Tree Recursive Neural Network (BT-RvNN) and identifies the main bottleneck as the entanglement of the scorer function and the recursive cell function. The reviewers agree that the paper is well-written and making a solid contribution to the community. I therefore would recommend accept this paper.
Decision: Accept (poster)