Recursion in Recursion: Two-Level Nested Recursion for Length Generalization with Scalability
Authors: Jishnu Ray Chowdhury
Cornelia Caragea
Venue: NeurIPS 2023 poster (2023)
Keywords: Recursive Neural Networks
Long Range Arena
RvNN
Long Range Sequence Modeling
Length Generalization
LRA
Structured Encoding
Inductive Bias
Hierarchical Model
Recursive Models
TL;DR: We introduce a nested recursive model with an efficient balanced-tree outer recursion that logarithmically scales with input length and an inefficient (but powerful) inner recursion which lineary scales with bound constant input length.

Abstract: Binary Balanced Tree Recursive Neural Networks (BBT-RvNNs) enforce sequence composition according to a preset balanced binary tree structure. Thus, their non-linear recursion depth (which is the tree depth) is just $\log_2 n$ ($n$ being the sequence length). Such logarithmic scaling makes BBT-RvNNs efficient and scalable on long sequence tasks such as Long Range Arena (LRA). However, such computational efficiency comes at a cost because BBT-RvNNs cannot solve simple arithmetic tasks like ListOps. On the flip side, RvNN models (e.g., Beam Tree RvNN) that do succeed on ListOps (and other structure-sensitive tasks like formal logical inference) are generally several times more expensive (in time and space) than even Recurrent Neural Networks. In this paper, we introduce a novel framework --- Recursion in Recursion (RIR) to strike a balance between the two sides - getting some of the benefits from both worlds. In RIR, we use a form of two-level nested recursion - where the outer recursion is a $k$-ary balanced tree model with another recursive model (inner recursion) implementing its cell function. For the inner recursion, we choose Beam Tree RvNNs. To adjust Beam Tree RvNNs within RIR we also propose a novel strategy of beam alignment. Overall, this entails that the total recursive depth in RIR is upper-bounded by $k \log_k n$. Our best RIR-based model is the first model that demonstrates high ($\geq 90\%$) length-generalization performance on ListOps while at the same time being scalable enough to be trainable on long sequence inputs from LRA (it can reduce the memory usage of the original Beam Tree RvNN by hundreds of times). Moreover, in terms of accuracy in the LRA language tasks, it performs competitively with Structured State Space Models (SSMs) without any special initialization - outperforming Transformers by a large margin. On the other hand, while SSMs can marginally outperform RIR on LRA, they (SSMs) fail to length-generalize on ListOps. Our code is available at: https://github.com/JRC1995/BeamRecursionFamily/

Recursion in Recursion: Two-Level Nested Recursion for Length Generalization with Scalability
Jishnu Ray Chowdhury
Cornelia Caragea
Computer Science
University of Illinois Chicago
jraych2Quic.edi
cornelia@uic.eer
Abstract
Binary Balanced Tree Recursive Neural Networks (BBT-RvNNs) enforce sequence composition according to preset balanced binary tree structure. Thus, their non- linear recursion depth (which is the tree depth) is just log, n (n being sequence length). Such logarithmic scaling makes BBTTRvNNS efficient and scalable on long sequence tasks such as Long Range Arena (LRA). However, such computational efficiency comes at cost because BBT-RvNNs cannot solve simple arithmetic tasks like ListOps. On the flip side, RvNN models (c.g., Beam Tree RvNN) that do succeed on ListOps (and other structure-sensitivy tasks like formal logical inference) are generally several times more expensive (in time and space) than even Recurrent Neural Networks. In this paper, introduce novel framework Recursion in Recursion (RIR) to strike a balance between the two sides getting some of the benefits from both worlds. In RIR, we form of two-level nested recursion where the outer recursion a k-ary balanced tree model with another recursive model (inner recursion) implementing its cell function. For the inner recursion, we choose Beam Tree RvNNs. To adjust Beam Tree RvNNs within RIR we also propose novel strategy of beam alignment. Overall, this entails that the total recursive depth in RIR is upper-bounded by k log, n. Our best RIR-based model the first model that demonstrates high (2 90%) cength-generallzzation performance on ListOps while at the same time being scalable enough to be trainable on long sequence inputs from LRA (it can reduce the memory usage of the original Beam Tree RyNN by hundreds of times). Moreover, in terms of accuracy in the LRA language tasks, performs competitively with Structured State Space Models (SSMs) without any special initialization outperforming Transformers by large margin. On the other hand, while SSMs can marginally outperform RIR on LRA, they (SSMs) fail to length-generalize on ListOps. Our code is available at: wwt./oo/////oeeee JRC1995/ BeamRecursi inneroonnamiii Family/
Introduction
have the potential to enable powerful non- linear sequential dynamics that dynamically adapt with the input length. However, this ability that makes them powerful also causes several problems. First, RNNs are slow because of their non-linear sequential operations that scale linearly with the input sequence length. Second, backpropagation through arbitrarily large non-linear recurrence depth (depending on the input length) can lead to have stability issues overall (67]. Potentially, because of the combination of these factors, it was found that fast convolution based models [99] [8] [5]]
Non-linear Recurrent Neural Networks (RNNs) 23 40
vanishing/exploding gradients [39 3
[6 57 26 2 47] with fixed non non-linear depth could often do just as well an RNN. Transformers are built upon this trajectory replacing bounded kernel window in convolution with an attention
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

mechanism that can dynamically compute interaction weights for input tokens at any arbitrary distance.
However, despite the tremendous success of Transformers in all manner of tasks, they tend to struggle in hierarchical prructue-ssnssttvve tasks that require dynamic adaptation to input complexity and modeling of long-range dependencies [93
82 35 92]. Recently, a family of models closely connected 33 30 have been emerging. Most of these models greatly outperform Transformers in long-range datasets [3] 86 Instead of adding non-linearity in every recurrent step, they simply stack a fixed number of linear recurrences with -ineeiirasss in between. However, in doing so these models lose the ability to adapt the non-linearity depth to input. This can make it harder to tackle tasks requiring adaptation to unseen lengths of nested non-linear operations.
to linear RNNs [31 73 86
66
In this paper, we take a step back and look again at non-linear RNNs. Non-linear RNNs, more generally, can be seen as special case of (non-linear) Tree Recursive Neural Networks (Tree- RvNNs) (76 87 89 91]. Tree-RyNNs can process sequences in an arbitrary tree-structured order. Non-linear RNNs are a special case of Tree-RvNNs following chain-structured tree. However, such a chain-structured tree is an extreme case- requiring the maximum tree traversal height. On the other side of the extreme are balanced tree models. For instance, the height of k-ary balanced tree with n terminal nodes (the input length for our case) would be logg (n). Balanced Tree-RvNNs [68] 84 can then logarithmically scale with the sequence length (n). To an extent, this can greatly mitigate the original issues of non-linear RNNs while still preserving some degree of ability to dynamically adapt with imput length. Fascinatingly, we find that simple model like a Balanced Binary Tree RvNN (BBT-RyNN) with a modern recursive cell [2 13 can come close to the performance of the recent strong linear RNNs or Structured State Space Models (SSMs) without much tuning or any specialized initialization on Long Range Arena (LRA) text datasets [92 thereby, greatly outperforming Transformers in general.
Nevertheless, while BBT-RvNNS can be quite fast and scalable. they are incapable of excelling (or even passing) simple structure-sensitive tasks like ListOpe] 70 or formal logical inference [6] in a length- Soggth-generalizale manner. Transformers were already shown to underperform in these tasks [2 93), and we find that S4D [30] (a representative of linear RNN/SSM model family) and
MEGA 60] (a hybrid of Transformer and SSM) also struggle in these tasks. Looking back at Tree-RvNNs there are several models X2 13 77 that dynamically learn the tree structure from the input (instead of using some enforced heuristics) and determine the order of operations accordingly. They have been able to perform well in Etructure-sensingg
tasks. Thus, BBT-RvNNS enjoy high speed and computational efficiency but at the cost of systematic issues in modeling task structures as revealed in ListOps or logical inference tasks, whereas in sharp contrast, the more powerful RvNNs 8 [3 7 enjoy their strong length-generalizing accuracy in ListOps, logical inference, and reasonable performance in natural language domain but at the cost of high computational resource and inability to effectively train datasets like LRA.
To address the above challenges, we propose new framework called Recursion in Recursion (RIR) in which we have nested level of recursion. We use a balanced k-ary Tree-ordered recursion in the outer loop and we use a strong RvNN (particularly we use Beam Tree RvNN-based model (77]) in the inner loop to process the k arguments sent in from the outer loop. The inner RvNN can scale linearly with input size but now that size is bounded by fixed constant k. Thus, the total non-linear depth will be bounded by a linear factor of k log, (n) (the total outer loop being log, (n) and the inner loop being k). RIR makes Beam Tree RvNN (BT-RvNN) much faster and trainable on LRA but at the cost of some accuracy loss. On the flip side, RIR can be seen slower version of more basic balanced tree models but at the gain of gengraattaral in ListOps and general accuracy gain in several other datasets. In addition, we identify issue related to beam alignment in incorporating BT-RvNN within RIR and propose a strategy to circumnavigate it.
2 Preliminaries
Tree Recursive Neural Networks (Tree-RyNN): Here we focus on constituency Tree-RvNNs
[1] that build up higher-order constituent representations of a given input in bottom-up manner. Particularly, given an input sequence of vectors, Tvees treat them as terminal nodes of a latent
An example sample of ListOps Input: SM is modulo-10 10 summation.
[SM [SM [SM [MAX 5 ] 0058000 Output 7.
2

---

tree to be built up. The non-terminal nodes of the tree are filled sequentially by composing their immediate child nodes using some recursive cell function - R R² x R + Rº (we consider binary trees here so R will always have only 2 children as arguments). Given some input sequence of vectors 7 + 5 (assume each of the symbols correspond to some vector E RR"), an example of processing can be expressed as:
([R(R(T,+),.. R(R(9, x). R(-,2))
(1)
Let us say R is considered as single non-linear neural layer. In that case, the total non-linear depth of this processing can be interpreted as the maximum nested R operations which is in Eqn. [ RNNs can be now seen special case where the order of operation is always like this:
R[ 7), +), x). -)
(2)
Here, ho is the initial hidden state for RNNs. As can see, because of their chain-like structure RNNs will have the maximum possible recursion depth within the Tree-RvNN framework. In this case, the depth is 7. Another special case is BBT-RvNN (Balanced Binary Tree RvNN) which follows an enforced binary-balanced tree-based order of operations and can be expressed as:
A(B(R(T,+)) R29,, x)),
Here the maximum non-line non-linearity depth is only 3 (i.e., ~ log, (n); where == 7). With longer sequences the differences between RNNs and BBT-RvNNs will grow bigger because BBT-RyNNs can scale logarithmically to the input length.
Greedy Search Tree RvNN: If our Tree-RvNN does not employ any fixed heuristic tree structure (as in RNNs or BBT-RwNNs) and if we are not relying on an external system or user to provide tree structures, we have decide on some policy to automatically induce the latent tree structure from raw sequences. Greedy search Tree RvNNs provide us with one way of doing that. The basic idea of Greedy Search Tree RvNN can be found in multiple works 12 88 and is related to easy-first parsing [28). A general framework for greedy search parsing is as follows. Assume we are at some recursion step t. Let the input sequence of node representations in that step be ho..,h...... h(xc) (where h E II?"). Assume we have the recursive binary cell Rt as before and a neural scorer function of the form scorer: H22d, + R (where d, < d; the role of d, will be clarified). Next, consider all possible node pairs that can be built into parent node. Note that for simplicity so only contiguous node pairs (ht, 1) are considered candidates for being composed into higher-level parent node (whose children will be those nodes). The scorer assigns a scalar score to every candidate node pair as: e; = scorer (h$[0 d.], 14 d=]). The slicing above is done for efficiency reasons (we set de = 64 and generally keep it smaller than d. i.e., d. < d) following
we maintain a projective tree constraint as is often standard [12 38 13
(78). Let e represent the sequence of all scores. Assume j the position of the first node in the maximum scoring pair, i.e.
j = ar gargmaz(ees. Now the update rule for the input to the next recursion will be:
M
RON
i=j {>j
The iterative application of this rule can achieve both tree-parsing (through scorer) and sequence composition (by application of Rt) simultaneously. Finally, we will have the root representation left which can be used sentence encoding (the intermediate non-terminal nodes can be also used if needed). Note that the framework we describe already incorporates the efficiency fixes introduced in (78.. Works 11 prior to (78) made the scorer's input to be R(h, h(41) which requires running expensive recursive cells for all possible node pair siblings (not just the chosen one) in parallel and they use no slicing. A problem with directly using the above framework is that the argmax for selecting is non-differentiable. So it becomes impossible to train the scorer. Various techniques have been used to address this problem- e.g., with autoencoder loss [88), gumbel softmax 66 45)
with truighh-througlh Estimation (STE) 4 or with SPIGOT 74. Although not all of them have been exhaustively explored, STE gumbel softmax [12 which one of the more popular approaches
has been found to fail in senssiiv-eeniiivve tasks 70 38 However, viewing the above family of
approaches as a greedy search approach- opens up another way that using simple beam search replacing argmax with a top-k operator for beam search (77). We discuss this below.
3

---

Extending Greedy Search Tree RvNNs with beam search allows for keeping multiple hypotheses or beams. Each beam would be one possible induced tree structure with its node representations and corresponding beam score (addition of the log-softmax of el for each iteration in that beam). Setting up a beam-score-basee the root representations of each beam in the end allows us create a sentence vector representation: exp(si) E: Σ, exp(x;) by where by is the root representation of beam i and 8; is the beam score. The final softmax can allow competition in the top B selected beams (where B is the beam width) which can allow meaningful gradient signals to reach the scorer. Ray Chowdhury and Caragea [77] showed that this is enough to make the former framework succeed in ListOps and other logical inference tasks. We use the efficient variant Beam Tree RvNN (BT-RvNNN) i.e., Efficient Beam Tree RvNN (EBT-RvNN) which is BT-RvNN built on the specific greedy framework described above rather than the prior frameworks [2] that we contrasted. Both BT-R and EBT-RvNN use stochastic Top- K [52]. More details on BT-RvNNN can be found in 77 and more details on EBT-RyNN can be found in [78].
Beam Search Tree RvNN:
softmax-based marginalization over
Balanced Tree RvNNs: Above, we focused on Binary (2-ary) Tree RvNNs. Here we consider more general k-ary Tree RyNN. The non-termin non-terminal nodes of k-ary Tree RvNN can have at most & children. Since we defined the recursive cell R to have two parameters, we now introduce a generalized form of the recursive cell RK : IR xx -> RR RK takes a sequence of k vectors as input and outputs a single vector. Essentially RK, by itself, operates like a sentence encoder. Next, we introduce a balanced tree RvNN model that uses a k-ary recursive cell.
We call the balanced tree variant of k-ary Tree RvNN as Balanced k-ary Tree-RvNNs (BKT-RvNNs). Balanced Binary Tree RyNNs (BBT-RvNNs) is a special case of BKT-RvNN when k = 2. In each recursion, BKT-RvNNs make oon-overaapping chunks of size (so we can also say t: the "chunk size" henceforth) and then compress each chunk into single vector using RK. This is done in every recursion until there is only one vector left which becomes the root node representation, i.c., the final sentence encoding, Let us say, we have a sequence (ri: E IR Ixddda) of the form below:
Tin = r1, .2...., Tn
(5)
Assume that n is divisible by h- if not, always use padding to extend the sequence length to make it divisible. We can then create chunked sequence (c1:LEJ Ikxd))) as below:
C1 = P2,,72,...... ................................ rk). =
CLP =
Fnn
(6)
Each chunk (c:) can be then processed independently (and simultaneouslly) by RK IR kxd, + IR.h to compress the k-sized chunks into single vectors:
Pi = (cKK)))))
RK RK( (cLE))
Thus the sequence of chunks, G1:LE] IRLII turns into sequence of vectors P1: IREE xds, P1:Lg. then becomes the input to the next recursion. We terminate the recursion when only one item is left in the sequence. Since in every recursion the sequence size is cut by times, the total recursions taken (until sequence of size is left) would be [log, n. assuming the original sequence length.
3 Recursion in Recursion
Here, we introduce our framework Recursion Recursion (RIR). RIR is essentially an implementa- tion of BKT-RyNN. The question to ask when using BKT-RvNN is what to use to implement RK. In case of RIR, we use another Rvee-RvNN to implement RK. This results in a two-level nested recursion as discussed below. We present a visualization in Figure and explain the two levels below.
Outer Recursion: The outer recursion (outer RvNN) is the BKT-RvNN setup as discussed.
Inner Recursion: In RIR, the inner recursion another RvNN (inner RvNN). In principle, we can use nearly anything for the inner RvNN or the R.K function in general even Transformer [94] or

---

there will be less of an interpretation of their modeling choices X, X 3
X 3 6
X, 8 9
10 11 12
13 14 15
16 17 18
RvNN
RvNN
RvNN
RvNN
RvNN
RvNN
R(R(x, x,) x,)
R(x, R(x, x,)
R(R(x, x2) x2)
R(Xgp R(x,, x,,)
R(R(X, x x,
R(X, R(X,p kip)
RvNN
RvNN
R(R(R(R(X, x,) x,) R(x, RCx, x2))) R(R(x, x3) x,))
R(R(X, R(X,, x,2) R(R(R(X, x x, R(x,, R(X,, x,,)))
RvNN
R[R(R(R(R(x, x,) x.) R(x, R(x, x,3)) R(R(x, x,)) R(R(x, R(x,, x,,) R(R(R(X, x,2 x,2) Róx,, R(x,, x,))
Visualization of the Recursion In Recursion (RIR) framework. The sequence (I1, ....... Zg) the input sequence of vectors. The RvNN block indicates the inner RvNN. R is the recursive cell within the inner RvNN. The inner RvNN block is working within balanced k-ary Tree like structure (here k = 3)- effectively serving as the recursive cell within BKT-RvNN.
Figure I:
an RNN. Using an RNN makes the whole model similar Sliced RNN 101. Our main RIR-based model uses EBT-RyNN as the inner RvNN. We motivate this choice below.
Motivation for EBT-RyNN:
1. BT-RvNN performs quite well on logical inference and ListOps while maintaining reason- able natural language performance a feature lacking plain RNNs, Gumbel-Tree variants, other simpler RvNNs 77.. EBT-RyNN is more promising and efficient variant of BT-RyNN (78).
2. EBT-RyNN as an inner RvNN (after some adjustments to be discussed in the next section) offers clean interpretation of the RIR model searching in an additionally constrained space of tree structures (constrained by the outer balanced tree recursion). While other ListOps competent models be also forcibly used as an inner RvNN 13 82 under RIR.
approximation of EBT-RyNN
Time Complexity Analysis: The time complexity of the outer RvNN (i.c. BKT-RyNN) in RIR (if the inner RvNN were (1)) is (logg (n)) following what we already discussed. Let us say that the time complexity of the inner RyNN is some (f if is the input sequence length. Given these factors, the overall time complexity of an RIR model will be (logg, (n) fmin n))). While inner RvNNS be slow by itself, within the RIR framework its recursive depth is now bound by
like EBT-RvNN the chunk size i instead of the sequence length n. The chunk size k is hyperparameter that is preset constant before training. It remains constant during training matter how big the sequence length n becomes. As such although the inner RvNN can be expensive it now becomes bound by constant factors during training. This makes the RIR model with EBT-RyNN inner RvNN much more efficient than EBT-RyyN itself. The same is also true for other possible implementations of an inner RvNN within the RIR framework.
However, the inner recursion with EBT-RvNN can be still relatively slow and add large overheads. Thus, the bigger the k. the slower the overall model will be. On the other hand, lower l pushes the model closer to BBT-RvNN and makes it faster. When = 2, the model would just collapse into BBT-RyNN, and when oc, the model reduces into just EBT-RvNN.
3.1 Beam Alignment
Context: There are a few challenges naively integrating EBT-RvNN in the RIR framework. First, note that we initially defined RK as of the form RK RRkxd, ah If we keep it that way then we have marginalize the beams at the end of every inner recursive loop to get single vector output instead of beams of vectors. This can make it harder to extract discrete structures from the
5

---

beam search process if needed for interpretability or for sending top-down attention signals for token contextualization (as used in 78 with parent attention). Also, it in conflict with the second motivation for using EBT-RvNN. Moreover, keeping the beams active instead of marginalizing them every so often can allow for more robustness and recovery from error 20 Now, the beams are kept active, there are two main changes.
1. The input sequence in every outer recursion would belong Rhxxadd, where is the beam size. The output sequence after the outer recursion should be in RRxx [gxxL L&]xd,, In addition, we need also maintain an input of beam scores IR and an output of the same form.
2. Each chunk that is fed to RK should be now of the form 1 In addition, the beam scores E IR are also fed to RK. The output of RK should be in the form of tuple: (BS, BR) where BS RR represents the list of beam scores for each beam and BR E RRx1xxd is the list of corresponding chunk-level sentence encodings for each beam. Overall RK is to be redefined as: RK: RR² Rii + RR² x RRa xdd, The first input argument represents the input beam scores, the second represents the beam of chunks.
Problem: Now, the output of each RK is sequence E hx1x and beam scores E IR. Since there would be |x]] chunks (if the input sequence length to that level of outer recursion is n), there will be simultancous [ sequences E yyax1 xdn and similarly, L lists of beam scores E RR. The challenge to answer how we get a single sequence E R & [xd, and single list of beam scores 1RAh from this circumstance to serve as inputs to the next outer recursion.
For simplicity, let us say ] = 2 and as such, we have two chunk outputs: (BS), BRt) and (BS2, BR2). The question that is now raised is: How do we combine the different beams of the different output tuples for the input to the next outer recursion?
String-it Solution: One answer can be to just string together (concatenate) the corresponding beams in BR, and BR2 as: BRuew = concatenate( [BRi, (BB B dim = 1). In other words, we concatenate BR [i] with [ for all E (0.1..... - 1}. Here, BReew E lx2xd The beam scores can be summed up for accumulation: BSnew BSI + BS2.
The choice above is arbitrary. While concatenating the top scoring beams (the first beam of every BR) can be motivated, there is no reason to disallow beams from different ranks (say R, [i] and BRa [j] where * j) from being concatenated together especially if they form a unique beam with higher combined scores than others.
Problem with the String-it Solution:
Beam Alignment Solution: Given the above problem, we introduce our solution the Beam Alignment technique. In this technique, we apply a simple stochastic approach following the idea that "higher scoring beams should have higher chance to exist in the combined beams P Based on this idea, we simply transform each (BS,, Ra) into some (BS), BR) (we explain this below) and then apply the string-it solution on the transformed outputs (BS), BR) to get the input for the next outer recursion. The transformation works as follows:
idz; = sample(ponulation = [0. 1,.... b-1]. 1). distribution = normalize B.S)):
times = b)
That is, first, we sample the indices (idzy) of beams based on their corresponding scores (BS)). The scores BS, can be normalized with softmax. We sample times with repetition. The next steps are:
BS = [BS] for j in idaı); BR - [BR for j in ida,]
Thus, beams with higher scores will be sampled more times and in turn will have higher chance to be present in BS and BR, and in turn, more likely to be present in the stringed-together beams BSnew and B Rnew after applying the string-it solution. As such, the high-level idea of increasing
'hht is the beams of sentence encoding for the chunk input E Bxxxa as created by the inner EBT-RvNN processor.
Alternativlyy one could also try to search for an optimal combination of beams but that can increase compute and may end up losing diversity in the stringed beams.

---

the chance of higher scoring beams is implemented One additional detail: in practice, we enforce cew [0] and [ be the concatenation of the top beams from the pre-transformed materials (BS), B Ri) so that the best possible stringed beam is guaranteed to be present. We provide additional intuition on beam alignment with added visualization in Appendix [|
3.2 Pre-Chunk Processing
The chunking used in BKT-RvNN does not take into account the input content. This can create bad chunks where the information necessary to process one chunk is in another chunk. For example, imagine what happens if we split MAX (1, 2,,,,3,4, 4) into three chunks [MAX (1), [2, [2,3,4], and DJ (where the square brackets indicate chunk boundaries). There would be no information initially for the later chunks to work on. To mitigate that use an initial (single) linear RNN layer bidirectionally to propagate information outside chunks before starting the RIR loop. Specifically, we use an S4D with Gated Linear Units [30] (described more in Appendix D}. Moreover, earlier literature has often used a recurrent layer to initialize the non-termin con-terminals before running their Tree-RyNN [22 84 for more contextualized parsing decisions. So the S4D layer can be seen as serving that purpose too.
3.3 Practical Tips and Points
The chunk size (k) for BKT-RyNN can effectively work as a trade-off parameter in the RIR framework. Lower chunk size can make the whole pipeline faster by having less work do for the heavy inner- RvNN, but for the same reason the point of using EBT-RyNN (instead of a simpler RNN model) would start to get lost as we lower the chunk size. In Appendix C we show that lowering chunk size drastically deteriorates the performance of our model in ListOps. A practical option is to set the chunk size high possible while meeting one's practical computational need. We generally set k = 30 for our purposes. We also discuss theoretical ways to extend the framework for language modeling in Appendix H
RIR Inference: As mentioned before, EBT-RwNN runs within the RIR framework and can be interpreted as just EBT-RyNN with some additional constraints in its tree-search space. Thus, during inference, we can just run EBT-RvNN as is without RIR given that the core model remains the same now just being allowed cover more space and gain enhanced performance. By default, generally indeed do that during inference even if the EBT-RyNN model is trained under RIR however using RIR inference generally works just as well for less drruttre-ssesitive tasks. We discuss more about this decision in Appendix D
4 Experiments and Results
4.1 Model Nomenclature
RNN-GRC represents an RNN implemented with Gated Recursive Cell (GRC) as the recursive cell R (GRC was introduced in (2) and discussed in Appendix D): CRvNN refers to Continuous Recursive Neural Network 13: OM refers to Ordered Memory (82 BT-GRC refers to BT-RvNN
implemented with GRC 777: BT-GRC OS refers to BT-GRC combined with OneSoft (OS) Top-K
function 777]: EBT-GRC refers to EBT-RvNN model with GRC; S4D refers to stacked bidirectional S4D model implemented similar to S4D-inv in 30 MEGA refers to a hybrid model combining Transformers and an SSM based on exponential moving average introduced in [60]: BBT-GRC refers to BBT RvNN 84 but with GRC (it is intended to be a more basic baseline and does not have S4D initial layer), RIR-GRC refers to RIR-based model using a recurrent GRC cell for the inner RvNN (it can be thought to be similar to sliced RNN (01)), RIR-EBT-GRC is our main proposed model. Both of the latter models use S4D layer before starting the main RIR loop.
"The overall strategy can create some repetitions of beams. However, we do not think this should happen too often because the score distributions tend to have high entropy in practice. Moreover, the original BT-RvNN framework already allows repetitions and still works well. Trying to completely remove repetitions can require some tricky operation that takes up resources without much return. We leave it for future research for further analysis on potential ways avoid repetitions.
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. For the splits of lengths 200 1000 for the 1500 2000 split we sample from the training set of LRA listops 92
the data shared Havrylov al. [38]
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)
RNN-GRC
0.22
0.02
0.54
0.02
1.3
0.03
2.5
0.04
MEGA
0.06
0.07
0.05
0.16
0.05
0.29
0.05
0.72
S4D
0.04
0.03
0.05
0.05
0.04
0.07
0.05
0.14
BBT-GRC
0.02
0.02
0.02
0.02
0.03
0.02
0.03
0.04
RIR-GRC
0.06
0.02
0.08
0.03
0.09
0.04
0.1
0.07
ListOps Competitive
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
BT-GRC
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
RIR-EBT-GRC
0.1
0.07
0.2
0.14
0.3
0.23
0.3
0.43
Table 2: Accuracy on ListOps-O. For our models we report the median of runs. Our models
were trained on lengths 100, depth < 20, and arguments 5. We bold the best results that do not use gold trees. Subscript represents standard deviation. We use the original training set [70] with the length generalization splits from Havrylov et al. (38], the argument generalization splits
from Ray Chowdhury and Caragea and the LRA test set from Tay et al. 192.. As example,
90, 90 0.1
Model (Lengths)
near-IID
Length Gen.
Argument Gen.
LRA
S 1000
200-300
500-600
900-1000
100-1000
100-1000
2000
(Arguments)
<
5
<
5
10
15
10
MEGA
75.452.6
45.21.a
31.714
24.736
39.5g3
33.8s9
25.840
S4D
72.33
31
20.85
14.7
27.3
22.76
17.4
BB- Tree GRC
59.18
43.6
40.4
31.5
45.35
44.5
38.25
RIR-GRC
78.33
41.75
35.55
32.3
43.8
42.75
40.05
OM
99.9
99.6
92.7
76.9
84.15
75.05
80.1
CRvNN
99.82
99.5
98.5
98
65.45
45.1
55.38
BT-GRC
99.9
76.05
67.9
71.8
EBT-GRC
99.9
99.9
99.4
99.5
82.95
79
79.5
RIR-EBT-GRC
99.72
99.15
98.25
97.1
74.9
49.55
61.65
S4D
99.78
99.15
98.87
98.6
63.95
47.73
48.25
Beam Align
98.83
91.75
79.05
68.8
59.55
43.65
40.75
4.2 Results
For more details on the architectures and experiments, see Appendix There are also more ablations
in Appendix C
Efficiency Analysis: In Table we compare the empirical time-memory trade-offs of the most
relevant Tree-Rvih RvNN models. We use CRvNN in the halting mode as [77 As be seen, our RIR-EBT-GRC is multiple times faster than the original BT-GRRC models and even EBT-GRC
'Otherwise it fails leam to halt in the small training and starts halt quickly.

---

Table 3: Mean accuracy and standard deviation the Logical Inference for 2 8 number of operations after training on samples with Σ 6 operations. Our models were run times on different seeds. Subscript represents standard deviation. As example, 901
90 0.1
Model
Number of Operations
10
11
12
MEGA
89.716
83.62s.s
76.918
70.45ss
63.85s6
S4D
87.620
79.4s6
72.32
65.01sa
59.48as
BBT-GRC
77.715
72.5x1
67.411
64.014
57.512
RIR-GRC
865.8
64.89s.9
47.3527
46.4528
45.922s
OM
97.51.
96. 74..4
94.952
93.92.2
93. 93.368.2
BT-GRC os EBT-GRC
97.031.4
96.491.9
95.434.5
94.216.6
93.39
97.123
96.5g.1
94.951.5
93.877.4
93.046.7
RIR-EBT-GRC
96.841.4
96.051.3
95.453.4
94.21s.7
93.3611
Table Accuracy on LRA 99
represents that the results are copied from (30) and represents
that the results are copied from 60 For our models we report the mean of 2 runs. ListOpsMix
combines the training set of ListOps-O and ListOps LRA; it keeps the dev set and test set LRA. Subscript represents standard deviation. As example, 901 = 90 0.1
LRA
Model
ListOps
Text
Retrieval
ListOpsMix
MEGA
63.14
90.43
91.25
S4D*
60.183.5
87.34g
91.09.
S4D
59.30
88.180.
91.17.6
59.052.5
BBT-GRC
55.151
85.69o.7
90.78
55.7
RIR-GRC
20.18
86.8941.3
88.2410
58.956.5
KIR-EBT-GRC
59.04
87.971.6
08.995.2
64.
-S4D
59.531
88.131.3
89.743.9
70.43go
while using much less memory. As expected, because of still using a heavy inner loop model, not as competitive resource-wise against S4D, MEGA, BBT-GRC, or RIR-GRE However, in our experiments, we find these competitors to fail on ListOps and logical inference whereas RIR-EBT-GRC still works. We present pareto frontier analysis the Appendix(F
List Operations (ListOps): Here we discuss the results of Table 2 This table is based on the original ListOps dataset [70]. To disambiguate from the ListOps used in LRA (92), call this one ListOps-O. Similar to 13, we filtered all sequences of length > 100 from ListOps-O training set. ListOps-O involves training on much shorter samples than those in LRA ListOps but ListOps-O can be challenging in its own right because this allows investigating length sength-gnneralzzation prowess of neural networks. ListOps requires solving hierarchically nested lists of mathematical operations that neural networks, barring a few exceptions (38) 13 82 77]. generally struggle to solve. The different splits test the models different out-of-distributton settings, e.g., unseen lengths, unseen number of arguments, or both. As can be seen from Table 2 BIR-EBT-GRC does fairly well in gengrratenerliitiiinnn (still getting 2 90%) despite being perturbed within the RIR framework for efficiency. Its argument generalization performance is. however, hampered. Removing the S4D layer (used for pre-chunk preprocessing) from RIR-EBT-GRC (the SS4 row) does not actually harm length generalization but seems to harm argument generalization. Removing beam alignment from RIR-EBT-GRC (and just keeping the string-it solution) substantially deteriorates the performance showing the efffcctiveness of beam alignment (see - -Beam Align row). MEGA, S4D and RIR-GRC perform reasonably in the near- setting compared to LSTMs and Universal Transformers 82 but does not come close more powerful RvNNs. BBT-GRC also does not work well here.
'It is "near" IID because it has some longer sequence data than what is present in the training set. But generally, most data the shorter end.

---

Logical Inference: In T we show the results of our models in a formal logical inference task [6]. This is another task where only stronger Pree-RvNN based models have been able to perform well. In this task the models are trained on samples with < 6 operators and we test their generalization performance on higher operators (similar to (93). We find that RIR-EBT-GRE can keep up well with the state-of-the-an whereas others like MEGA, S4D, BBT-GRC, or RIR-GRC cannot.
LRA and ListOpsMix: In Table 4 we explore the NLP subset of LRA tasks. We find that BBT-GRC can already perform quite well in LRA without any special initialization (note that BBT-GRC does not use S4D), outperforming all non-hybrid Transformer models [18 [06]. RIR-EBT-GRE also shows high competence in LRA. It starts to get a bit slow on the Retrieval task so we reduced the chunk size to 5 which might reduce its performance there. While RIR-EBT-GRE uses S4D for pre-chunk processing. we also run variant without any S4D (see row S4D) and it performs just as well or better. This shows that the S4D layer not playing a big role here. Curiously enough, FIR-EBT-GRE does worse on ListOps LRA test in the in-distribution setting (in Table 4 than it does in the OOD setting trying to generalize from shorter sequences with lower arguments Table 2 We hypothesize that this might be because RIR-EBT-GRE learns more easily lower-length samples. To investigate whether RIR-EBT-GRC can gain more on LRA when samples of shorter length are present, we created another ListOps dataset- Mis which combines the ListOps-O training set and the ListOps LRA training set (ListOps LRA dev and test sets are used for validation and testing, respectively). As
RIR- TIR-EBT-GRC (with without S4D) is particularly better at utilizing extra lower-length data than other models; however, still underperforms compared with what EBT-GRC/OM can get with training purely on ListOps-O.
We also ran our models in a number of other natural language tasks, e.g., natural language inference and sentiment classification. The results are in Appendix E Generally RIR-EBT. GRC performs similarly to other RvNN-based models.
Other Tasks:
Conclusion
In this paper, we introduce the Recursion In Recursion (RIR) framework and beam alignment to make Efficient Beam- Trre- RvNNs (EBT-RyNN) more scalable. We also show the power of more basic models like BBT-RvNNG on LRA. Even though they do not outperform S4D or some of the newer state-of-the-art 600 86 85 24), BBT-RvNNS are coming from a completely orthogonal family of models which, in recent times, have received limited attention. Moreover, BIR-EBT-RvNN. provide a better trade-off in maintaining competitive performance in LRA text-related tasks and robust length generalization in cructure-sensitiv tasks as shown in the Pareto Frontier plots in Appendix [F] We intend results to inspire further exploration of these models. We provide extended discussion with related works in Appendix G
6 Limitations
Our main method, RIR- EBT-GRC, although much more computationally efficient than other ListOps- competent RyNNs 182 13 777, is still quite bit slower compared to BBT-GRC, RIR-GRC, MEGA, and S4D. Moreover, although it serves as a non-linear recursive model that can both scale to training on > 1000 sequence lengths and also -entt-ggeneralize on ListOps and Logical Inference (from shorter samples), it has still difficulties learning from longer sequences.
7 Acknowledgments
This research is supported part by NSF CAREER award #1802358, NSF IIS award #2107518. 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] Forough Arabshahi, Zhichu Lu, Pranay Mundra, Sameer Singh, and Animashree Anandkumar. Compositional generalization with tree stack memory units. arXiv preprint 191 2019.
10

---

[2] Shaojie Bai. J. Zico Kolter, and Vladlen Koltun. An empirical evaluation of generic convolu- tional and recurrent networks for sequence modeling. arXiv:1803.01271, 2018.
[3] Y. Bengio, P. Simard, and P. Frasconi. Learning long-term dependencies with gradient descent is difficult. IEEE Transactions on Neural Networks, 5(2):157-166, 1994.
[4] Yoshua Bengio, Nicholas Léonard, and Aaron Courville. Estimating or propagating gradients through stochastic neurons for conditional computation. CoRR, tbss/.38..332. 2013.
URL http: org/ 1/////338.3333
[5] 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 Natural Language Processing, pages 632-642, Lisbon, Portugal, September 2015, Association for Computational Linguistics. doi: 10.18653/v1/ D15-1075. JRll.atttps:/alalnttolooyy wtwp:/looooooo/1/--11000000
[6] Samuel R. Bowman, Christopher D. Manning, and Christopher Potts. Tree-structured com- position in neural networks without tree-structured architectures. Proceedings of the 2015th International Conference on Cognitive Computation: Integrating Neural and Symbolic Approaches Volume 1583, COCO' 15, page 37-42, Aachen, DEU, 2015, CEUR-WS SOUR-WS.org.
[7] Samuel R. 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 Computationnal Linguistics (Volume 1: Long Papers), pages 1466-1477, Berlin, Germany, August 2016. Association for Computational Linguistics. doi: 10.18653/v1/P16-111 hrg/P16-11 1139
URL https://acllanthologg
[8] Aydar Bulatov, Yuri Kuratov, and Mikhail Burtsev. Recurrent memory transformer. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022. URL 1d-Uyur3iPhksa
[9] Joao Carreira, Skanda Koppula, Daniel Zoran, Adria Recasens, Catalin Ionescu, Olivier Henaff, Evan Shelhamer, Relja Arandjelovic, Matt Botvinick, Oriol Vinyals, et al. Hierarchical perceiver. arXiv preprint arXiv:2202. 10890, 2022.
[10] Ilias Chalkidis, Xiang Dai, Manos Fergadiotis, Prodromos Malakasiotis, and Desmond Elliott.
An exploration of hierarchical attention transformers for efficient long document classification. arXiv preprint arXiv:2210.05529 2022.
[11] Ta-Chung Chi, Ting-Han Fan, Alexander Rudnicky, and Peter Ramadge. Transformer working memory enables regular language reasoning and natural language length extrapolation. arXiv preprint arXiv:2305.03799 2023.
[12] Jihun Choi, Kang Min Yoo, and Sang-goo Lee. Learning compose task-specific tree structures. In Sheila A. Mcllraith and Kilian Q. Weinberger, editors, Proceedings of the Teiony-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 httph:tt///// setts://www..r aaai. org/ocs/ /in//dixxxx /
16682
[13] Jishnu Ray Chowdhury and Cornelia Caragea. Modeling hierarchical structures with con- tinuous recursive neural networks. In Marina Meila and Tong Zhang, editors, Proceed- Machine Learning, volume 139 of Proceed- ings of Machine Learning Research, pages 1975-1988. PMLR, 18-24 Jul 2021. URL https:/pproceedings mlr. wwt.smmlr....ss.e.mmmmemmmmmmmee ptress/vv339/ httpee///v33//hooouuuuueee www.chhrr21...hhoooo
ings of the 38th International Conference
[14] Zihang Dai, Zhilin Yang, Yiming Yang. Jaime Carbonell, Quoc Le, and Ruslan Salakhutdinov: Transformer- XL: Attentive language models beyond a fixed-length context. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 2978 2988. Florence, Italy, July 2019. Association for Computational Linguistics. doi: 10. 10.13v53/v1/ P19-1285. URL https : httpa////aalaaahhloooo org/P1g 1285

---

[15] Zihang Dai, Guokun Lai, Yiming Yang. and Quoe Le. Funnel-transformae Filter- ing out sequential redundancy for efficient language processing. In Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural In- formation Processing Systems, volume 33, pages 4271-4282 Curran Associates, Inc., 2020. URL https://prrcceeddngs.ss neurinp ctt.ccccppoo wwwpppprpp.p..pppppppp wiw.filllppppee pttp////ppp///////eeeeee/ 24221188555500444544222222222222 patppa/aaaaceeeeeeeaaearpp.....
[16] Yann N. Dauphin, Angela Fan, Michael Auli, and David Grangier. Language modeling with gated convolutional networks. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, ICML' 17, page 113-9911.111 J...JMM..orr 2017.
[17] Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Confer- ence of the North American Chapter of the Association for Computational Linguistics: Human Minneapolis,
Language Technologies, Volume (Long and Short Papers), pages Minnesota, June 2019. Association for Computational Linguistics. doi: 11883//1/N19914430 URL http://///aaantholggoooooo
1423
[18] Aniket Rajiv Didolkar, Kshitij Gupta, Anirudh Goyal, Nitesh Bharadwaj Gundavarapu, Alex Lamb, Nan Rosemary Ke, and Yoshua Bengio. Temporal latent bottleneck: Synthesis of fast and slow processing mechanisms in sequence learning. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022. URL httths://pppnseeeee
id=mq- ddmp-
[19] Andrew Drozdov, Patrick Verga, Mohit Yadav, Mohit lyyer, and Andrew McCallum. Unsuper- vised latent tree induction with deep inside-outside recursive auto-encoders. 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 Pupers), pages 1129- 1141, Minneapolis, Minnesota, June 2019. Association for Computational Linguistics. doi: URL httpstts::// https////aaaatnoooy.oooooo
10. 18188/////N19-111
1116
[20] 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 4844, Online, November 2020. As- sociation for Computational Linguistics. doi: 10. 10111886//1/// 1/20://000000002mmaaaaaa m9.n.3 URL
org/ 2020. mamlp-main. 392
[21] Brian DuSell and David Chiang. Learning context-free languages with nondeterministic stack RNNs. In Proceedings of the 24th Conference on Compulational Natural Language Learning, pages 507-519, Online, November 2020. Association for Computational Linguistics. doi: 111186533112022..oo 2012020.coonll1.. 1.41. httttttts///clattttttt
org/2020.
2020. mon1l11..4
[22] Brian DuSell and David Chiang. Learning hierarchical structures with differentiable nonde- terministic stacks. In International Conference on Learning Representations, 2022. URL
https://openreviiee
mett/forumIid=5LXx_ppp
[23] Jeffrey L. Elman. Finding structure in time. Cognitive Science, 14(2):179-2) 211, 1990. ISSN 0364-0213. doi: wwt.a///ciiieeeeteeeeee///////..
URL https
//www.sciencedirect com/
[24] Daniel Fu, Elliot L Epstein, Eric Nguyen, Armin W Thomas, Michael Zhang, Tri Dao, Atri Rudra, and Christopher Re. Simple sendwwrr--fffcienn long convolutions for sequence model- ing. In ICLR 2023 Workshop on Mathematical and Empirical Understanding of Foundation Models, 2023. URL htt.taa://ppprrriieeeeeeee/ net. http:/ormmmiiiiiem HdW.2ddo22666622222
[25] 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-
12

---

Online, November 2020. Association for Computational Linguistics. doi: 10. 10.18653//1/2020 madings-emnll... 17. /RLL/ttps://aclaattoooggg httph/oooggyorgg///////// wttp//2/...ooooaa.o wwndinginniieiinnn mamlp.11. 117
[26] Jonas Gehring, Michael Auli, David Grangier. Denis Yarats, and Yann N. Dauphin. Con- volutional sequence to sequence learning. volume 70 of Proceedings of Machine Learning Research, pages 1243-1252, International Convention Centre. Sydney, Australia, 06-11 Aug 2017. PMLR. URL
mlr wwwps//we/ gewringgireee i html
[27] 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 Computational Linguisties (Volume 2: Short Papers), pages 650-655 Melboumn,, Australia, July 2018. Association for Computational Linguistics. doi: 10.18653/v1/P18- 2103. URL
wwaetchooogyorrg/PPe. org.p//-2g/1111110 2103
[28] 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 https://acllatthologg org. 1trg/N10--111
[29] C. Goller and A. Kuchler. Learning task-dependent distributed representations by backprop- agation through structure. In Proceedings of International Conference on Neural Networks (ICNN'96), volume 1, pages 347-352 vol.1, 1996. doi: 10. 1199/ICNN.1996.44989
[30] Albert Gu, Karan Goel, Ankit Gupta, and Christopher Ré. On the parameterization and initialization of diagonal state space models. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho. editors, Advances in Neural Information Processing Systems, 2022. URL
[31] Albert Gu, Karan Goel, and Christopher Re. Efficiently modeling long sequences with structured state spaces. In International Conference on Learning Representations, 2022. URL
https://openreviery http://pppppaaeeeeeeeeeeeee/rrrr .ett//forruriiddaaaoooo////////
[32] Albert Gu, Isys Johnson, Aman Timalsina, Atri Rudra, and Christopher Re. How to train your HIPPO: State space models with generalized orthogonal basis projections. In International Conference Learning Representations, 2023. URI httpp:://peerrevie http//pprrrvieetttttfffrrfrrrr net/forum?
1d=k1K17003KB
[33] Ankit Gupta, Albert Gu, and Jonathan Berant. Diagonal state spaces are as effective as structured state spaces. Advances in Neural Information Processing Systems, 15:22982-229999 2022.
[34] Suchin Gururangan, Swabha Swayamdipta, Omer Levy, Roy Schwartz, Samuel Bowman, and Noah A. Smith. Annotation artifacts in natural language inference data. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers), pages 107-112, New Orleans, Louisiana, June 2018. Association for Computational Linguistics. doi: 10.18653/v1/ N18-2017. URL, httttppsss//cllahhooogyy/. org/ N11-
[35] Michael Hahn. Theoretical limitations of self- in neural sequence models. Transac- tions of the Association for Computational Linguistics, 8:156-171, 2020, doi: 10.1162/tacL a 00306. URL.https://accaathot .waplooggoorrg./// wwgg/020..eo tac1-1.111111111
[36] Kai Han, An Xiao, Enhua Wu, Jianyuan Guo, Chunjing Xu, and Yunhe Wang. Transformer in transformer. Advances in Neural Information Processing Systems, 54085908-1, 2021.
[37] Ramin Hasani, Mathias Lechner, Tsun-Hsuan Wang, Makram Chahine, Alexander Amini, and Daniela Rus. Liquid structural state-space models. In The Eleventh International Con- ference on Learning Representations, 2023. URL htt.h:tts://// htttp:://pperreieeeeeee net/ feet/foru??id g40TKRKfS7R
13

---

[38] 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 I (Long and Short Papers), pages 1118-1128, Minneapolis, Minnesota, June 2019, Association for Computational Linguistics. doi: 10.18653/11/N11-1111 URL htt.ttt:s://ccaathhtttte org/ 2tg/N19-1115
[39] Sepp Hochreiter. Untersuchungen zu dynamischen neuronalen netzen. diploma thesis. Diploma thesis, TU Munich, 1991.
[40] Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural Comput., (8):1735-1780, November 1997. ISSN 0899-7667. doi: 10. ww1116///co.199..11 1997.9.8.77.335. URL
attps://doi.org: 10. 1ew2/ neco 1997. 8.8. 1735
[41] Xiang Hu, Haitao Mi, Zujie Wen, Yafang Wang, Yi Su, Jing Zheng, and Gerard de Melo. R2D2: Recursive transformer based on differentiable tree for interpretable hierarchical language modeling. In Proceedings of the 59th Anmual Meeting of the Association for Computational Linguistics and the I 11th International Joint Conference on Natural Lan- guage Processing (Volume 1: Long Papers), pages 4897-4908, Online, August 2021. Association for Computational Linguistics. doi: 10. 10.18653/v1/2011 http///2222.allooo......a acl-llogg.799
URL
org/ 2021. 10921acc--1on acl-long. 379
[42] Xiang Hu, Haitao Mi, Liang Li, and Gerard de Melo. Fast-R2D22: A pretrained recursive neural network based on pruned CKY for grammar induction and text representation. In Proceedings the 2022 Conference on Empirical Methods Natural Language Processing, pages 2809- 2821, Abu Dhabi, United Arab Emirates, December 2022. Association for Computational Linguistics. URL aattts://acaaattiitee
w02/2022.......oooo.../..g/..... 2022. emnle-maniiie aappmann.... 181
[43] 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-91111 PMLR, 17-23 Jul 2022. URL htttps://proceeednngg
mlr presss grres/vv62/hhue hwtp////22/haaaaa.aaa/a html
[44] DeLesley Hutchins, Imanol Schlag, Yuhuai Wu, Ethan Dyer, and Behnam Neyshabur. Block- recurrent transformers. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neurul Information Processing Systems, 2022. URL https
//openreview www./eeeetwtineeeeeee http:/oorummddddlooennnnll.a
[45] Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterization with gumbel-softmax.
In 5th International Conference Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedingy. OpenReview.net, 2017. URL https 7/ /ppenreview
[46] Da JU, Stephen Roller, Sainbayar Sukhbaatar, and Jason Weston. Staircase attention for recurrent processing of sequences. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022. URL https::/opennrevie: www.:/neeettoooooaaaaiiaoaa
[47] Lukasz Kaiser, Aidan N. Gomez, and Francois Chollet. Depthwise separable convolutions for neural machine translation. In International Conference on Learning Representations, 2018. URL https:///pperrevierr
[48] Nal Kalchbrenner, Edward Grefenstette, and Phil Blunsom. A convolutional neural network for modelling sentences. In Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 655-665, Baltimore, Maryland, June 2014. Association for Computational Linguistics. doi: 10.3115/w1/P14-10022 URL httpp://wwwt
aclweb. wttp::/.wwwwb.ooooooo.o.o.o wwtggaanhoooog/PP44-100
[49] Divyansh Kaushik, Eduard Hovy, and Zachary Lipton. Learning the difference that makes difference with counteffctuallyy-aggeennddd data. In International Conference on Learning Representations, 2020. httctp/se//opeereieiseeeee/ttnne
14

---

[50] Ruslan Khalitov, Tong Yu, Lei Cheng, and Zhirong Yang. Chordmixer: A scalable neural attention model for sequences with different length. In The Eleventh International Confer- ence on Learning Representations, 2023. URL httpp:://peerreeeee.eetttt
E8mzu3JbdR
[51] Yoon Kim. Convolutional neural networks for sentence classification. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 1746-1751, Doha, Qatar, October 2014. Association for Computational Linguistics. doi: 10.3115/11/D14-11888
BtLLhttps:// /ttlpps:/wwwwrr /ww. aclweb. www.wwewb.rr............ org/ lawtaaoogg/Di4--aaaa
[52] Wouter Kool, Herke Van Hoof, and Max Welling.
Stochastic beams and where find them: The Gumbel-top-t trick for sampling sequences without replacement. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 3499- 3508. PMLR, 09-15 Jun 2019. URL https: URLhttta: httpppa:/ppocceeinggee mlr. press/ v97 / html
[53] Phong Le and Willem Zuidema. Compositional distributional semanties with long short term memory. In Proceedings of the Fourth Joint Conference on Lexical and Computational Seman- tics, pages 10-19, Denver, Colorado, June 2015. Association for Computational Linguistics. doi: 10. 111653/11/1115 1002. URL https:tt/////... /tttps://aclante accps//ol/caatooogoooooooo org/S15-1002
[54] Phong Le and Willem Zuidema. The forest convolutional network: Compositional dis- tributional semantics with neural chart and without binarization. In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pages 1155- 1164, Lisbon, Portugal, September 2015. Association for Computational Linguistics. doi: 10. 118655/v1/D15-.. 1137. URL
[55] Yuhong Li, Tianle Cai, Yi Zhang, Deming Chen, and Debadeepta Dey. What makes con- volutional models great on long sequence modeling? In The Eleventh International Con- ference on Learning Representations, 2023. URL http:://pppeeeeeee...etttt net. www.://un/e.//i.eae.moeeom TGJSPPRRJJX-
[56] Bingbin Liu, Jordan T Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. Exposing attention glitches with flip-flop language modeling. arXiv preprini arXiv:2306. 00946. 2023.
[57] Jingzhou Liu, Wei-Cheng Chang. Yuexin Wu, and Yiming Yang. Deep learning for extreme multi-label text classification. In Proceedings of the 40th International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR '17, page 1 115-124, New York, NY, USA, 2017. Association for Computing Machinery. ISBN 978 450355288 doi: 10. 00.1145/3077136.3000 30.008444 URL.
http///...orrgr0...111////////// 3080834
1145/3077
[58] Nelson F Liu, Kevin Lin, John Hewitt, Ashwin Paranjape, Michele Bevilacqua, Fabio Petroni, and Percy Liang. Lost in the middle: How language models use long contexts. arXiv preprint arXiv: xrXiv:207703117, 2023.
[59] Yang Liu and Mirella Lapata. Hierarchical transformers for multi-document summarization. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 5070-5081 Florence, Italy, July 2019. Association for Computational Linguistics. doi: 10. 1..18866/v1l 1/t19- 1500. htLLhttts///ccaaatttttt
[60] Xuezhe Ma, Chunting Zhou, Xiang Kong, Junxian He, Liangke Gui, Graham Neubig, Jonathan May, and Luke Zettlemoyr. Mega: Moving average equipped gated attention. In The Eleventh International Conference on Learning Representations, 2023, URL https://openreviiee het/forumiid-qlleeitg
[61] Andrew L. Maas, Raymond E. Daly, Peter T. Pham, Dan Huang, Andrew Y. Ng, and Christo- pher Potts. Learning word vectors for sentiment analysis. Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Languuge Technologies, pages 142-150, Portland, Oregon, USA, June 2011. Association for Computational Linguistics. org/
URL
15

---

[62] Chris J. Maddison, Andriy Mnih, and Yee Whye Tch. The concrete distribution: A con- tinuous relaxation of discrete random variables. In International Conference on Learning Representations, 2017.
[63] 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. 111111/////111-222 2903. URL petts::/aclanthol/le www.:1o-////.... W18-W9000000
[64] Jean Maillard, Stephen Clark, and Dani Yogatama. Jointly learning sentence embeddings and syntax with unsupervised tree-Istms. Natural Language Engineering, 25(4):433 449, 2019. doi: 10. 10.1017/1135133491999 19000919999444
[65] Ankur Mali, Alexander G Ororbia, Daniel Kifer, and C Lee Giles, Recognizing and verifying mathematical equations using multiplicative differential neural units. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 5006-5015, 2021.
[66] Eric Martin and Chris Cundy. Parallelizing linear recurrent neural nets over sequence length. In International Conference Learning Representations, 2018. [ttpsttts://o/eeeevv...
pet/ffoumm' id Hd--HUNWwlC---
[67] John Miller and Moritz Hardt. Stable recurrent models. In International Conference on Learn- ing Representations, 2019. URL http:p/://pppppe...oioooottttfts
[68] Tsendsuren Munkhdalai and Hong Yu. Neural tree indexers for text understanding. In Proceed- ings of the 15th Conference of the European Chapter of the Association for Computational Linguistics: Volume 1, Long Papers, pages 11-21, Valencia, Spain. April 2017. Association for Computational Linguistics. URL
[69] 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: //tww/www http:/wwwccclllc www.wb.ww.............. org/ anthology/C1n 1198
[70] Nikita Nangia and Samuel Bowman. ListOps: diagnostic dataset for latent tree learning. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computaaioonll Linguistics: Student Research Workshop, pages 92-99, New Orleans, Louisiana, USA, June 2018. Association for Computational Linguistics. doi: 10.18653/v 10.18653/1//18-44000 I/N18-003.
URL
4013
[71] Sharan Narang, Hyung Won Chung, Yi Tay, Liam Fedus, Thibault Fevry, Michael Matena, Karishma Malkan, Noah Fiedel, Noam Shazeer, Zhenzhong Lan, Yanqi Zhou, Wei Li, Nan Ding, Jake Marcus, Adam Roberts, and Colin Raffel. Do transformer modifications transfer across implementations and applications? In Proceedings of the 2021 Conference Empirical Methods in Natural Language Processing, pages 5758-5773, Online and Punta Cana, Domini- can Republic, November 202.. Association for Computational Linguistics. doi: 10.18653/v1/ 202 www.eeemnmmmaii
URL https: httpp/s://aaaaaahhllooal org 2021. emnlp mommp-mmii....mmmmm 465
[72] Piotr Nawrot, Szymon Tworkowski, Michat Tyrolski, Lukasz Kaiser, Yuhuai Wu, Chris- tian Szegedy, and Henryk Michalewski. Hierarchical transformers are more efficient lan- guage models. Findings of the Association for Computational Linguistics: NAACL 2022, pages 1571, Seattle, United States, July 2022. Association for Computational Linguis- feteeefinninggnaaae
ties. doi: 10. 16611811611/222.22.
URL htttps://claatthollggg org./og..oorr.oooooooo.oo 2022
findings maacnngs-naall.111
[73] 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.06342 2023.
16

---

[74] Hao Peng, Sam Thomson, and Noah A. Smith. Backpropagating through structured argmax using a SPIGOT. In Proceedings of the 56th Annual Meeting of the Association for Com- putational Linguistics (Volume 1: Long Pupers), pages 1863-1873, Melbourne, Australia, July 2018. Association for Computational Linguistics. doi: 10. 10.1885//1//18- 1173. URL.
https://aclanthont www.:/looogorro---1111111 org/P18-1173
[75] Jeffrey Pennington, Richard Socher, and Christopher Manning. GloVe: Global vectors for word representation. In Proceedings of the 2014 Conference Empirical Methods in Natural Language Processing (EMNLP), pages 1332-153, Doha, Qatar, October 2014. Association for Computational Linguistics. doi: 10. 1162. URL httptttss/aacaaatho.ooaao
org/D14-11 1162
[76] Jordan B. Pollack. Recursive distributed representations. Artificial Intelligence, 46(1):77 105, 1990. ISSN 0004-3702. doi: https://dh.ooggoo/..ooooo0444420 com htt.:///w.w.....o...o......aaaaa
URL
http://www.siienced/
[77] Jishnu Ray Chowdhury and Comnelaa 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 Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 28768-28791, PMLR, 23-29 Jul 2023. mlr Tivess//202/aay-choovee chowdhury23a. httl
URL
[78] Jishnu Ray Chowdhury and Cornelia Caragea. Efficient beam tree recursion. In Proceedings of NeurlPS, 2023.
[79] Hongyu Ren, Hanjun Dai, Zihang Dai, Mengjiao Yang, Jure Leskovec, Dale Schuurmans, and Bo Dai. Combiner: Full attention transformer with sparse computation cost. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, 2021.
[80] 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. 10..1666 1863/v /20020emmml--main.61. URL https://
aclanthology wwt.oo/////2/ 2020. commp-mmain... 661
[81] Tao Shen, Tianyi Zhou, Guodong Long, Jing Jiang, and Chengqi Zhang. Bi-directional block self-attention for fast and memory-efficient s modeling. In International Conference on Learning Representations, 2018. URI. htt.:ttttp//peereerrrie
[82] Yikang Shen, Shawn Tan, Arian Hosseini, Zhouhan Lin, Alessandro Sordoni, and Aaron C Courville. Ordered memory. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and Garnett, editors, Advances in Neural Information Processing Systems 32, pages 5037-5048. Curran Associates, Inc., 2019. http:///: 8748-ordere meeerrmmmoorrrrro pdf
[83] Zhiqiang Shen, Zechun Liu, and Eric Xing. Sliced recursive transformer. In Computer Vision- ECCV 2022: 17th European Conference, Tel Aviy, Israel, October 23-27, 2022, Proceedings, Part XXIV, pages 727-744. Springer, 2022.
[84] 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, pages 4631-4634444 Brussels, Belgium, Detober-Novemble 2018, Association for Computational Linguistics. doi: 10.18653/v1/111 1492. URL htttttsss//aaaaatlllllat orw.://-//DDDD--999
[85] Jiaxin Shi, Ke Alexander Wang, and Emily B. Fox. Sequence modeling with multiresolution convolutional memory. In International Conference on Machine Learning. 2023.
[86] Jimmy T.H. Smith, Andrew Warrington, and Scott Linderman. Simplified state space layers for sequence modeling. In The Eleventh International Conference on Learning Representations, 2023. htttss///ppeererieeeeet////rrrrr
17

---

[87] Richard Socher, Christopher D. Manning, and Andrew Y. Ng. Learning continuous phrase representations and syntactic parsing with recursive neural networks. In Proceedings of the NIPS-2010 Deep Learning and Unsupervised Feature Learning Workshop, 2010.
[88] Richard Socher, Jeffrey Pennington, Eric H. Huang, Andrew Y. Ng, and Christopher D. Man- ning. sumi--ssereieed recursive autoencoders for predicting sentiment distributions. In Proceedings of the 2011 Conference on Empirical Methods in Natural Language Process- ing, pages 151-161, Edinburgh, Scotland, UK., July 2011. Association for Computational Linguistics. URL URL httpppass//acaaammolloogo/// wwwp://ooogooro/1--101111
[89] Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D. Manning, Andrew Ng. and Christopher Potts. Recursive deep models for semantic compositionality over sentiment treebank. In Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, pages 1631-1642, Seattle, Washington, USA, October 2013. Association for Computational Linguistics. http:tttts//accaatttiti
013 1170
[90] Alessandro Sordoni, Yoshua Bengio, Hossein Vahabi, Christina Lioma, Jakob Grue Simonsen, and Jian- Yun Nie. A hierarchical recurrent encoder-decoder for generative context-aware query suggestion. In Proceedings of the 24th ACM International on Conference on Information and Knowledge Management, CIKM '15, page 553-562, New York, NY, USA, 2015. Association for Computing Machinery. ISBN 9781 9781450337946. /115/280641111111 2806493
doi: 10. 02.114//280041122886662 URL
attps://doi..om
[91]
Kai Sheng Tai, Richard Socher, and Christopher D. Manning. Improved semantic representa- tions from rre-structured long short-term memory networks. In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Con- ference Natural Language Processing (Volume 1; Long Papers), pages 1556-1566, Beijing, China, July 2015. Association for Computational Linguistics. doi: 10.3 1/.1115/1/PP15-11555 http:ht:/ccccathhhhheea
1150
[92] 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. In International Conference on Learning Representations, 2021. URL https://openrevieet net http//foummiiii ddw.ornnni-Vye--grr-r -gC22k
[93] Ke Tran, Arianna Bisazza, and Christof Monz. The importance of being recurrent for modeling hierarchical structure. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pages 4731-4736, Brussels, Belgium, October-Novente 2018. Association for Computational Linguistics. doi: 10.18653/v 1/D11 //aclanthology. orgg/18--500
URL https
[94] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, E ukasz Kaiser, and Illia Polosukhin. Attention is all you need. In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Gar- nett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017. URL Inttps: /tpp:eeed/sooceonsss.... werddiinnnnnneuusiseeeeee wwwpurisssccppppee////// Paapaaaaaaaaaaaaaaraaaaa pdf
[95] 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'17 17, page 4144-4150. AAAI Press, 2017. ISBN 9780999241 103.
[96] Adina Williams, Nikita Nangia, and Samuel Bowman. A broad 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 Linguistics. doi: 10.18653/w1/N18- 1101. URL www.aaanhooogyoorgg//ioe wwtp/18-11/011000
[97] Chuhan Wu, Fangzhao Wu, Tao Qi, and Yongfeng Huang. Hi-transformer: Hierarchical interactive transformer for efficient and effective long document modeling. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th
18

---

International Joint Conference on Natural Language Processing (Volume 2: Short Papers), pages 848 853, Online, August 2021. Association for Computational Linguistics. doi: 10. (8653/v1/202) acl--short. acooottt 107. URL htt.aaass//aaaaaanollloooo//
org/ 2021 acl- 107
[98] Zichao Yang. Diyi Yang. Chris Dyer, Xiaodong He, Alex Smola, and Eduard Hovy. Hi- erarchical attention networks for document classification. In Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Lin- guistics: Human Language Technologies, pages 1480-1489, San Diego, California, June 2016. Association for Computational Linguistics. doi: 10.18653/v 1174. URL https://aclantholle org N16-
[99] Wen-tau Yih, Xiaodong He, and Christopher Meek. Semantic parsing for single-relation question answering. In Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pages 643-648, Baltimore, Maryland, June 2014. Association for Computational Linguistics. doi: 10.3115/1/P1--2105 URL
https://www
wwwwww.ww......... wwtp::wwwwwww.w/wwowooooooo httgg/nnhologg/11-----1 2105
[100] Dani Yogatama, Phil Blunsom, Chris Dyer, Edward Grefenstette, and Wang Ling. Learning to compose words into sentences with reinforcement learning. Sth International Conference Learning Representations, ICLR 2017, 7, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017.
[101] Zeping Yu and Gongshen Liu. Sliced recurrent neural networks. In Proceedings of the 27th International Conference Computational Linguistics, pages 2953-2964, Santa Fe, New Mexico, USA, August 2018. Association for Computational Linguistics. URL https
//aclanthology.oo www.llgoyyoogo//oo wtw/////////////-
[102] 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.18653/v1/N19-111 URL https: /RL /acaaathollt org/N19-20 1131
[103] Zizhao Zhang, Han Zhang, Long Zhao, Ting Chen, Sercan Ô Arik, and Tomas Pfister. Nested hierarchical transformer: Towards accurate, data-cfficient and interpretable visual understand- ing. In Proceedings of the AAAI Conference Artificial Intelligence, volume 36, pages 3417-3425, 2022.
[104) 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 Proceedings of Machine Learning Research, pages 1604-1612, Lille, France, 07-09 Jul 2015. PMLR. press/v37/ 20tpa///3//zuub5..m htmll
mlr
[105] 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: 10. 18653///vvll 6-N16- 1106. ARRL/tttps///acaathoollo orgg/16-
[106] Zhenhai Zhu and Radu Soricut. H-transformer-ID: Fast one-dimensional hierarchical at- tention for sequences. In Proceedings of the 59th Anmual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference Natural Language Processing (Volume 1: Long Papers), pages 3801-3815, Online, August 2021. Association for Computational Linguistics. doi: 10.18653/v1/202) acl- URL
org/ 2021.2021..oo a0021acll-100 acl- 294
19

---

A Organization
In Section we describe the settings of all the tasks and datasets that we used for model evaluation. In Section we provide an extended ablation of CIR-EBT-GRC. In Section D
we discuss in more detail the RIR inference strategy. In Section E we provide additional results on LRA, sentiment classification, natural language inference, and paraphrase detection. In Section F we provide Pareto Frontier analysis of different trade-offs for different models. In Section we present an extended survey of related work. In Section H.] we discuss ways to RIR-based models for language modeling. In Section we provide more intuition and visualization for beam alignment. In Section detail our architecture setup including the S4D. In Section K describe our hyperparameters.
B Details on Evaluation Tasks
ListOps: ListOps was originally introduced by Nangia and Bowman 77]. It task for solving nested lists of mathematical operations. It is a 10-way classification task. Like Chowdhury and Caragea [13,, we train our models on the original training set with all samples 2 100 sequence lengths filtered away. We use the original development set for validation. We test on the original test set (near-IID split); the length generalization splits from Havrylov et al. [38] that include samples of much higher lengths; the argument generalization splits from Ray Chowdhury and Caragea [77] that involve an 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. (22
Logical Inference was introduced by Bowman al. 6 This task involves classifying tne-grained inferential relations between two given sequences in a form similar to that of formal sentences of propositional logic. Similar to Tran et al. [93], our models were trained on splits with logical connectives < 6. We show the results in OOD test sets with logical connections 8-12.
Logical Inference:
We use the same splits as Shen et 82]. Tran et al. 993) Chowdhury and Caragea [3
Long Range Arena (LRA): LRA is set of tasks designed to evaluate the capacities of neural models for modeling rangerange dependencies (92). We evaluate on the language-related subset of tasks ListOps LRA, Text LRA (character-level IMDB [6]), and Retrieval LRA (character-level document pair matching task).
SST5 is a fine- grained 5-way sentiment classification task introduced in Socher et al. [8] We use the original splits.
SST5:
IMDB: IMDB is a binary sentiment classification task from Maas et al. 61
We use the same train,
validation, and IID test sets as created in Ray Chowdhury and Caragea 77
We also use the contrast
set Gardner et al. (25) and counterfactual set Kaushik et al. 49 as additional test splits.
QQP: QQF is a task of classifying whether two given sequences in a pair are paraphrases or not. As standard Wang et al. [95], we randomly sample 10, 000 samples for validation and IID test set such that for each split 5000 samples are maintained to be paraphrases and the other 5000 are maintained to be not paraphrases. We also use the adversarial test sets PAWSQQP and PAWSW IKI form Zhang et al. [102].
SNLI: SNLI (5) is natural language inference (NLJ) task. is 3-way classification task to classify the inferential relation between two given sequences. We use the same train, development, and IID test splits in Chowdhury and Caragea [13). Any data with a sequence of length > 150 is filtered from the training set for efficiency. We also use additional test set splits for stress tests. We use the hard test set split from Gururangan al. [34], the break test set from Glockner et al. [27), and the
counterfactual test set from Kaushik et al.
49
MNLI: MNLI [96] is another NLI dataset which is similar to SNLI in format. We the original development sets (match and mismatch) as test sets. We filter away all data with any sequence length > 150 from the training set. Our actual development set is random sample of 10, 000 data points from the filtered training set. As additional testing sets, we use the development set of Conjunctive NLI (ConjNLL) [80] and few of the stress sets from Naik et al. [69]. These stress test sets include Negation Match MNe Negation Mismatch (NegMM), Length Match (LenM), and Length Mismatch (LenMM), NegM and NegMM add tautologies containing "not" terms this
Datarra-DDttttt--Reellle Release- Busseeeta
20

---

Table 5: Extended Ablation ListOps-O. For models, report the median of runs. Our models are trained on lengths Σ 100, depth Σ 20, and arguments Σ 3. We bold the best results that do not gold trees. We use the original training set 770 with the length generalization splits from Havrylov et al. [38], the argument generalization splits from Ray Chowdhury and Caragea [77]. and the LRA test from Tay et al. [92] Subscript represents standard deviation. As example, 90, 90 + 0.1
Model
near-IID
Length Gen.
Argument Gen.
LRA
(Lengths)
S 1000
200-300
500-600
900-1000
100-1000
100-1000
2000
(Arguments)
S
<
S
10
15
10
RIR-GRC
78.33
41.75
35.55
32.3
43.8
42.75
40.05
RIR-CRvNN
89.15
40.45
35.2
28.7
45.55
43.4
36.65
RIR-OM
97.62
75.7
42.20
29.7
62.55
47.45
36.20
RIR-EBT-GRC
99.72
99.15
98.25
97.1
74.9
49.55
61.65
$4D
99.78
99.15
98.87
98.6
63.95
17.73
48.25
Beaa Align
98.83
91.75
79.05
68.8
59.55
43.65
40.75
+Random Align
99.14
96.89
93.3
86.4
67.2
53.2
55.05
+RIR inference
87.53
46.5
42.2
36.9
47.4
44.1
39.75
(beam 5)
99.4
97.8
94.3
89.0
65.6
53.15
48.25
(chunk 20)
98.9
91.75
77.85
63.7
66.8
55.7
50.5
(chunk 10)
89.64
47.5
47.35
39.9
45.9
37.75
33.25
can bias the models classify contradiction the inferential relation because the training set has spurious correlations between the existence of "not" related terms and the class of contradiction. LenM and LenMM add tautologies artificially increase the lengths of the samples without changing the inferential relation class.
C Extended Ablation
In Table 5] show extended ablation of RIR-EBT-GRC. As see, alternatives to EBT- GRC like CRvNN or Ordered Memory (OM) do not work as well within the RIR framework (see RIR-CRvNN RIR-OM row) although they can be still better than RIR-GRC. We also another ablation for Beam Align where we replaced it with another method Random Align. In Random Align, instead of sampling beams based beam scores, sample them based distribution. See the " Random align" row for the result of this method. As can be seen from the table, it does not perform well. This shows the effectiveness of the high-level idea behind Beam Alignment over another control test. As discussed in the main paper, we generally switch out of the RIR framework during inference. RIRI inference" shows the result of using the RIR framework during inference too. The results for RIR inference" worsen significantly. Given the efficiency of used
uniform
RIR-EBT-GRC, we also increase its default beam size from the original beam size in EBT-GRC and BT-GRC models. The row "(beam 5)" shows the result of using beam size 5 with RIR-EBT-GRC The results worsen bit. RIR-EBT-GRC uses chunk size of 30. We also show the performance degradation with lower chunk sizes see "(chunk 20)" and "(chunk 10)". These results worsen as is consistent with our discussion the main paper.
D RIR Inference
The RIR strategy enforces an outer balanced-tred structural restriction on the search space that is generally unsuited for structure-sensitiv tasks (and merely done for efficiency). However, the existence of data samples with sequence length less than or equal to chunk size leads to some non-RIR training instances which helps teach the inner recursion to learn to length-generalize. Thus, testing without RIR inference (i.e., running the inner recursion model the full input) can still lead length generalization and sometimes be even better due to the lack of balanced tree enforcement.
21

---

Table 6: Mean accuracy and standard deviation on SST5 89 and IMDB 61
Count. represents
counterfactual test split from Kaushik et al. 49] and Cont. represent contrast test split from Gardner et al. (25] We bold the best results. Our models were run 3 times different seeds. Subscript represents standard deviation. As an example, 90, = 90 + 0.1
SST5
IMDB
Model CRvNN
IID
IID
Cont.
Count.
51.7511
91.471.2
77.8015
85.383.5
OM
52.302.7
91.69p.s
76.98s.s
83.687.8
BT-GRC
52.324.7
91.291.2
75.0729
82.86g3
BT-GRC
51.927.2
90.869.3
75.6821
84.7711
EBT-GRC
52.22,
91.471.2
76.1617
84.29
BBT-GRC
50.98s.4
90.571.1
76.377.5
85.381.35
RIR-GRC
50.652.3
90.602.5
77.5330
85.0414
RIR-EBT-GRC
51.017.9
90.86
74.2514
82.92..5
Thus, during inference, we have a choice of removing the RIR structure from RIR-EBT-GRC and employing it just like EBT-GRC. We refer to this inference mode as Rion-RIR inference". If we make no changes to RIR-EBT-GRC during inference, we refer to it as "RIR inference".
Cost of non-RIk RIR inference: Non-RIR inference can be multiple times slower than RIR inference. Moreover, most tasks (including LRA). RIR inference works as well as non-RIR inference. So in most cases, RIR inference is "win-win" choice (several times faster and with similar accuracy).
context (such as ListOps-O task), it may find it difficult to learn to length generalize as well through an RIR format. Here, non-RIR inference works much better seen in the ablation (Table 2 If RIR training fails to make the model learn the task well, then even for cruucturessensiiiee tasks the difference between the accuracy of RIR inference and non-RIR inference can collapse (it happens for ListOps LRA). RIR inference in structure-sensitive tasks still performs better than MEGA or S4D.
Gain of Ron-RIR inference: When model is working in structure-sensitiee
Generally, we can take the choice of using RIR inference as a hyperparameter- the validation metric in the first epochs clues us in which inference strategy to use. For simplicity, we do not tune this choice and by default only non-RIR inference except for some LRA tasks (Text LRA and Retrieval LRA) where non-Ro -IR inference becomes too slow. For instance, in Text LRA, RIR inference takes around 7 minutes whereas non-RIR inference takes around hours. We find non-RIR inference to mainly make a substantial difference in accuracy in case of ListOps-O and Logical Inference.
E Additional Results
We show additional results of our models in sentiment classification (SST5, IMDB) in Table 6 and in natural language inference (MNLI, SNLI) and paraphrase detection in Table 7 Like prior models 822 13 77), the natural language results here are mixed. RIR-EBT-GRC does not work well sentiment classification (it may require more careful tuning), but otherwise keeps up well in sentence-pair matching task -generally even outperforming EBT-GRC. BBT-GRC sometimes does surprisingly well in some OOD sets or stress sets like the counterfactual set in IMDB and the Break test set from SNLI. We also present an extended comparison in LRA with other competitive models in Table 8 While in the paper we mainly focus on text-based tasks, theory, RIR-EBT-GRC can be also used for vision-processing tasks. We generally found that we can get greater than 60% in Sequential CIFAR (LRA Image task). Although that much lower than SSM-related or Long Convolution models, it still outperforms any pure Transformer based models. However, in our initial experiments, WIR-EBT-GRE fails in pathfinder tasks. There is more room to explore this area and perhaps look for better ways of creating synergy between SSM-based models and RIR-EBT-GRC. We did not find any notable difference in convergence speed (number of epochs taken) between RIR-EBT-GRC and EBT-GRC.
22

---

Uistps 500- 10001000000 Time (Ninutesi
BTO
Jrr
JEG eg0
MR
ListOpo Accuracy
(a) Ticc-Accuracy Tradc-off
RCR
Listpp 500 1000 Memory (68)
510
20
40
60
80
100
Listops 900-1000 OOo Accuracy
(b) Time-Memor, Trade-off
MEG
60
PRE
50
JRG
FRC
.CM
ListOps Accuracy
(c) 1LD-00DAoooo Accuracc-uuayar LRA- Accuracy Trade-off
Figure 2: Scatterplot with Pareto Frontier for different trade offs. We set accuracy to for LRA the model is too expensive to practically run eg. OM, CRvNN, BT-GRC, EBT-GRC, BT-GRC OS. S4D is S4D, GRC is a recurrent model with GRC cell function. MEG is MEGA, BBT Balanced Binary Tree GRC, RRG is RIR-GRC, OM is Ordered Memory, CR is CRvNN, BT is BT-GRC, BTO BT-GRC OS, EBT is EBT-GRC, RRE is RIR-EBT-GRE
23

---

Table Mean accuracy and standard deviaton on SNLI [5]. QQP, and MNLI 196.. Hard represents the SNLI test set from Gururangan et al. 84, Break represents the SNLI test set from Glockner al. 27 Count. represents the counterfactual test set from Kaushik al. 49 gooP and PAWS WII are adversarial test sets from Zhang et al.
[02]. MM is the mismatch dev set from MNLI, Con is the development set from Saha et al. 80, MegM, NegMM, LenM, LenMM are Negation Match, Negation Mismatch, Length Match, Length Mismatch stress test sets from Naik ct al. 669 respectively. Our models were run times on different seeds. Subscript represents standard
deviation. As an example, 90,
90 = 0.1
SNLI Training
QQP Training
Models
III
Hard
Break
Count.
IID
PAWSQQr
PAWSWiki
(Sequence Encoder Models)
CRvNN
85.32
70.6, 64
55.317
59.8
84.83
34.87
46.66
OM
85.52
70.6g
67.4g
59.92
84.60
38.17
45.6g
BT-GRC
84.91
70;
5114
591
84.73
36.917
46.412
BT-GRC OS
84.9,
70.3g
53. 53.2910
58.63
84.22
37.1s
46.3g
EBT-GRC
84.74
69.9g
55.620
58.11
84.32
36.95
47.55
BBT-GRC
84.44
69.2g
65.3g
58.14
83.64
42.921
46.712
RIR-GRC
85n.4
69.62.9
57.237
59.512
84.24.4
37.310
45.49.8
RIR-EBT-GRC
85.11
70.47
5529
59.614
83.9a
37.242
46.8s
MNLI Training
Models
Match
MM
ConjNLI
NegM
NegMM
LenM
LenMM
(Sequence Encoder Models)
CRvNN
72.24 24
72.65
41.710
52.8
53.84.2
6244
63.347
OM
72.53
732
41.74
50.97
51.713
56.533
57.0631
BT-GRC OS
71.71
71.92
41.2g
53.22
54.2s
65.613
66.7g
EBT-GRC
72.12
72,
40.93o
52.3323
53.2822
64.9210
66.410
BBT-GRC
71.12
71.44
40.912
51.56
52.6g
60.615
61.814
RIR-GRC
71.54.8
71.62.4
40.8g.9
50.91s
51.618
55.2
55.820
RIR-EBT-GRC
71.82
72.34
42.412
53.119
53.325
65.7B
67.3g
F
Pareto Frontier Analysis
We show the plots of three Pareto proett-fronserr focusing on three trade-offs in Figure 2 In Figure ( focus on the trade-off between ListOps-O OOD length generalization accuracy (which also corre with Logical Inference OOD accuracy for most parts) and empirical time cost. In Figure ( we focus on the trade-off between ListOps-O OOD length generalization accuracy and empirical memory
we
cost. In Figure 2(c we focus the trade-off between ListOps-O OOD length generalization accuracy and ListOps LRA IID accuracy. We use the empirical time/memory cost from Table [ In all three subfigures, RIR-EBT--C maintains a highly competitive trade-off. S4D, BBT-GRC, and RIR-GH RIR-GRC can win on the time cost and memory cost compared to RIR-EBT-GEE but with a sharp degradation of OOD performance in structure-sente sensitive tasks (logical inference, ListOps). While OM, CR>NN, BT-GRC, BT-GRC OS, and EBT-GRC can outperform RIR-EBT-GRE (to extent) OOD length generalization accuracy in ListOps and logical inference, they come with much more exorbitant time/memory cost.
(RRE in the figures) remains as a Pareto-efficient solution that
G Extended Related Works
RIR-related Approaches:
Many approaches have used chunking for hierarchical processing 900
98
60 to efficiently tackle long-range inputs. However, they generally neither go all the way in using full balanced tree recursion (with dynamic layer depth) nor concentrate on remaining competitive on structure-sensitte tasks. One exception Sliced
59
15
79 36
103
72 10
RNN [00]] which introduces model similar to RIR-GRC but with older recurrent cell. Some
24

---

Table 8: Accuracy LRA 192]. The results in the top block copied from the respective papers. For our models, we report the mean of 2 runs. Subscript represents standard deviation. As an example, 901 90 + 0.1
LRA
Model
ListOps
Text
Retrieval
Transformer 60
37.11
65.21
79.14
Local Attention 99
15.82
52.98
53.39
Linear Transformer
92
16.13
65.90
53.09
Reformer
37.27
56.10
53.40
Sparse Transformer
17.07
63.58
59.59
Skinhorn Transformer
92
33.67
61.20
53.83
BigBird 92
36.05
64.02
59.29
Performer
92
18.01
65.40
53.82
Linformer
92
35.70
53.94
52.27
Longformer
35.63
62.85
56.89
Transformer TLB
18
37.05
81.88
76.91
H-Transformer-1D
106
49.53
78.69
63.99
S4-LegS
32
59.6u.7
86.821.3
90.901.s
S4D-Inv
30
60.183.5
87.342
91.09.
SGConv
55
61.45
89.20
91.11
ChordMixer 50
60.12
88.82
90.17
86
62.15
89.31
91.40
Liquid S4
3
62.75
89.02
91.20
Long Cony, Exp + Squash [24
62.2
89.6
91.3
MEGA 60
63.14
90.43
91.25
LRU
60.2s
89.41
89.91
S4D-Im Inv (reproduction)
59.3p
88. 18..4
91.17.6
BBT-GRC
55.151
85.69p.7
90.781.4
RIR-GRC
20.18s.7
86.894..3
88.2410
RIR-EBI -R-EBBT-RC
59.04
87.971.6
88,995.2
-S4D
59.53
88.13
89.74s.9
18 3 approach where some k-sized chunk is used in a recurrent setup wherein each chunk is processed by a Transformer or some other neural module. These approaches similar the RIR framework where the outer recursion is made of some k-ary chain-tree structured recurrence (instead of balanced-tree recursion), and the inner 'recursion' is implemented for example by Transformer. A concurrent work Chi et al. [I]] also uses similar structure as RIR but with a Transformer stack replacing the inner inner RvNN.
approaches take block-recurrent 14 44 46
RvNN: Pollack 776. Goller and Kuchler 29 first introduced Recursive Neural Networks (RvNNs) for bottom-up representation build up based on directed acyclic graphs or trees. Socher et al. 87 88 89 extended RvNNs for NLP, and [104 91 53 (05) adapted RvNNs with LSTM cells [40].
Le and Zuidema [54], Maillard et al. [64] proposed a chart-based method for simulating bottom-up RvNNs based CYK algorithm. Drozdov al. [19 20J. Hu et al. 4T 22 built upon it. Shi
et al. 884, Munkhdalai and Yu (68) explored heuristics-tres bree-based RvNNS including balanced trees.
Multiple works explored memory-augmenteed RNNs for simulating RvNNs [7] 100 63 82 21 22). Arabshahi et al. I proposed a technique for augmenting recursive cells within RvNNs with a stack-like memory mechanism.
There are other related models verification.
655 that explore structure-sensitive tasks like mathematical equation
25

---

H RIR for Language Modeling
Language modeling today crucial for pre-training and scaling models for competitive performance in several realistic tasks. Nevertheless, directly using RIR-EBT-GRC for language modeling is not straightforward. We discuss some speculative directions we can go forward in re-framing RIR-EBT-GRC for language modeling.
Masked Language Modelingr: In a concurrent work, we propose a method create contextualized token representations for EBT-GRC or BT-GRC [78 through parent attention (making terminal nodes attend to its direct and indirect parent nodes based on the recursively built-up latent tree). The same principles can be used for RIR-EBT-GRC as well. After that RIR-EBT--RC can be used for masked language modeling as standard model setups like BERT 17] It can be also stacked with other types of models like Transformers if needed. Such a setup can also be used as encoder in Seq2Seq architecture which can be pre-trained with relevant language modeling policies.
Sentence Encoding in a Loop: There is a simple method for using any sentence encoder (including RIR-EBT-GRC) for autoregressive language modeling. At any timestep t, we can take the sequence of past tokens $1:t-1 as the input and get sentence encoding say, h2 (representing the compression of $1;1-)). Then we can predict the next token from h as st by projecting he into a probability distribution over a vocabulary. However, this is very costly method, because we have to run the whole recursion over the whole generated sequence in every timestep. would lack the memory reuse capacities of pure recurrent models (using chain-like tree structures), and it would lack the parallelism of Transformers trained with teacher-foreing. Nevertheless, it is a method that can be used given enough resources.
Block-Recurrent Sentence Encoding in a Loop: One way to address the cost of the above approach is to instead take a block-recurrent approach 44). Combined with HR-EBBT-GRC, this will be similar to taking a three-level nested recursion where the outermost recursion recurrence and CIR-EBT-GRE will be the inner two-level recursion. In this case, in a timestep RIR-EBT-GRR receives as input not the whole past sequence. but part of the past sequence with the earlier parts recurrently compressed into some finite memory blocks from the outermost recurrence. Thus, the inner recursions (IRR-BBT-GRC) with the "sentence encoding loop" setup can run with a bounded input size. There could be other creative ways to reduce the overall cost. For example, we can attempt to run the sentence-encoder loop periodically after some intervals intermixing fast (for example recurrently generating from the last sentence encoding instead of re-encoding the whole sequence) and slow generation (re-encoding the whole input sequence).
Parameter Scaling: To be a competitive language model, we need some ways to scale the parameter size of RIR-EBT-GRC. This is challenging for recursive models. The challenge is that the simplest way to increase the parameters is by increasing the hidden state sizes or overall increasing the computation of the recursive cell. Particularly, the increase has to be significant if we want to compete with parameters close to multi-layered models. However, because the recursive cell has to be repeatedly applied for an arbitrary number of times, the overall computation becomes very expensive. Similar challenges also occur for Universal Transformer 771. One way out of this problem is to stack more layers of RIR-EBT-GRC or alternate models like Transformers or SSMs after creating cokextccote representations using parent attention (78). This can also lead to the utilization of mixture of inductive biases. We can then keep the parameters the recursive cells themselves to more manageable level. Another direction to look for can be modular approach. This can allow increasing parameters while keeping computation more managcable via sparse activation. For example,
offuure-f--xper---eee based
attempt to recursively select and activate only a sparse region of parameters (some sparsely selected modules), to keep computation expense controlled while increasing the total parameter budget.
Even after all these, the overall setup would probably not be as fast as Transformer training. But speed or even mere surface capacity to handle big contexts is not everything and can come at other costs [56]] 58
I Beam Alignment Intuition
In Figure 3] we present a visualization of the String-it solution and in Figure 4 present a visualization of the Beam Alignment solution. In the visualizations, consider simple scenario where L
26

---

Chunk Results
Chunk Results
Beam Sequences
Scores
Beam Sequences
Scores
Beam Sequence
-0.4
Bearn Sequence
-0.7
Beam Sequence
-0.7
Bearn Sequence
Beam Sequence
-1.2
Beam Sequence
-1.2
Beam Sequences
Scores
Beam Sequence Beam Sequence 4
-0.4-0.7
Sequence
Sequence
-0.7-0.8
Beam Sequence + Beam Sequence 6
-1.2-1.2
-2.4
String-It Solution
Figure 3: Visualization of String-it Solution. Beam Sequence
Beam Sequence y indicates
concatenation.
2 (n input sequence length for the recursion, A: = chunk size, beam size). The String-it solution (Figure 3) is simply concatenate the beam sequences (and add the corresponding scores) from all lists that occur in the same position. For example, in Figure 3 we concatenate the first beam (Beam Sequence from the first list (chunk results) with the first beam (Beam Sequence 4) from the second list (chunk results). Similarly, we concatenate the second beam from the first list with the second beam from the second list, and on.
However, we want to create "high-scrring" beam combinations with more probability. The String-it solution does not care for that. For example, "Beam Sequence Beam Sequence 5" would be the second highest-scoring beam combination, but it cannot be ever selected by String-it since Beam Sequence is in the first position of the first list and Beam Sequence 5 is in the second position of the second list that is, they are not in the same position.
Thus, we propose Beam Alignment where we take stochastic approach towards the ideal of biasing the preservation high-scoring combinations. the String-it solution, we make the beams in each list stochastically "compete" for their positions. Essentially, we want high-scoring beams to more likely to occupy more positions in the beam lists from each chunk. This done by simply sampling beam per list position (for each of the b positions) according to the normalized beam score distribution. The result is that the beam lists will now filled with mostly the higher-scoring beams (See the results after 'Sample' in Figure 4. Next, if we simply apply the String-it solution at this point, it automatically leads to high-scoring combinations, wanted, because of the prior sampling. Now there is possibility of combinations like "beam sequence + beam sequence 5" to arise because the sampling step allows the same beam to occupy multiple positions.
this approach, instead of immediately applying
Overall, as we can see, in the simulation of Beam Alignment (Figure the resulting combined beams tend to have higher scores than in the case of the direct application of String-it (Figure 3).
27

---

Chunk
Beam Sequences
Scores
Beam Sequences
Scores
Beam Sequence
-0.4
Beam Sequence 4
-0.7
Sequence
Sequence
Beam Sequence
-1.2
Beam Sequence 6
-1.2
Sample
Sample
Beam Sequences
Scores
Beam Sequences
Scores
Beam Sequence
-0.4
Beam Sequence 4
-0.7
Sequence
Sequence
Beam Sequence
-0.7
Beam Sequence 4
-0.7
Beam Sequences
Scores
Sequence
Sequence
-1.4
Beam Sequence
Beam Sequence
-0.4-0.8 - -1.2
Beam Sequence 2 Beam Sequence
-0.7-0.7 = -1.4
Aligned Solution
Figure 4: Visualization of Beam-Align Solution. Beam Sequence x Beam Sequence y indicates concatenation.
28

---

J Architecture details
Gated Recursive Cell (GRC): For the Recursive Cell that the function (used within the inner RvNN), we use the GELU-variant of Gated Recursive Cell (GRC) [3] (originally a ReLU variant
was proposed in 82
unless mentioned otherwise. The cell function formalized below:
T,,
[childe] child,
GeLU
Wree + bi Wrec + b2
(10)
= (N(a(() o child + o(r) C child, o(g) h)
(11)
Here is sigmoid: [:] represents concatenation; is the parent node representation built from the children child; and child,, WT RR2-xdyeut b1 E RR W E R b2 E Rº and 1,r,g. R². LN is layer normalization. deell generally set as d.
Scorer: Similar to 78 for the scorer we used a two layer MLP as:
E = scorer (z, y) = W W.GeLU
b;) 6
(12)
Here, W1 E R x2.d, W E RR bf E RR by E IR.
Sentence Encoder Models: For sentence encoding, the architectural framework we use is the same Ray Chowdhury and Caragea [77]. We use Siamese dual-encoder setup for sentence-pair tasks as prior works (77].
S4D Pre-Chunk Layer: For the RIR-based models, before starting the RIR-loop, we a bidi- rectional S4D 30 layer for pre-chunk processing. Let us represent the basic single layer State space component (without non-linearity) of S4D as S4D, Rund + Iaadd (forward S4D) and S4D, R + RR (backward S4D). We express the overall pre-chunk processing layer using
S4D below:
ff = GELU(S4DD (x:)
(13)
Th = (LL.U((AD((x..ii))))...)
(14)
Feat [x
(15)
sigmoid(xcal)) W.) @ (Ieat W.) inp LN (outWW (aa)
(16)
(17)
Here Wa, W, E Rddd Wintt E 2xd and LN is Layer Normalization. Eqn. 16 is the application
of gated linear unit [16] and residual like Gu et al. (30 for feature mixing, and Eqn. 17 is the initial
leaf transformation layer that is used prior works 82 17)
S4D: When using pure imulti-layered S4D without models) S4D models, we use similar settings as Gu et al. 30. We found it more beneficial use the fused kernel for bidirectionality within their codebase when using S4D (setting 'bidirectional-Truee in their S4 function argument).
K Hyperparameter details
For prior sentence encoder models, we use the same hyperparameters as 77 for all the datasets. d, for EBT-GRC is set as 64. For EBB-GGRGG RIR- II--inference only used for Text LRA and Retrieval L.A for computational efficiency. We always use RIR-inference for RIR-GRC because we found to be better by validation accuracy. We use chunk size 30 for all RIR-models in all tasks, except Retrieval L.AA where we set chunk size as for computational efficiency (otherwise gets slow). For HIR-EBT-GRC. we use a beam size of 7 for all tasks except Retrieval LRA where use beam size of 5. Every other hyperparameters are unchanged from BT-GRC for RIR models
29

---

or BBT-GRC for the earlier tasks. For the new tasks, we share the hyperparameters for MNLI with that of SNLI, QQP, and Retrieval LRA (except that for Retrieval LRA we use smaller hidden state size 128 for parameter control and no pre-trained embeddings). We share the hyperparameters for IMDB and Text LRA (except that for Text LRA, we use smaller hidden state size 128; again, for parameter control, and no pre-trained embedding). We share the hyperparameters of ListOps-O, ListOpsMix, Logical Inference, and ListOps LRA for all models. We initialize S4D (whether when using the pure S4D model or S4D for pre-chunk processing) in S4D-Inv mode and use billinear discretization. For LRA tasks, we use the same hyperparameters as Gu et al. [30] for S4D. We use the same hyperparameters and Logical Inference. Note that all the natural language tasks (except LRA-related ones) are trained with frozen 840B Glove Embeddings [75 same as Ray Chowdhury and Caragea (77) All models
used for ListOps LRA Ma al. [60] for MEGA run in ListOps-O
were trained on a single Nvidia RTX A6000.
30


Reviews:
[{"review_id": "XvNZtb8tvN", "reviewer": "Reviewer_8Jr4", "summary": "This paper introduces the recursion-in-recursion (RIR) framework for balancing the tradeoffs between\n1. sequential processing, which offers better inductive bias and stronger solutions for many types of symbolic processing and logical inference tasks, but can be very expensive\n2. balanced tree recursion, which shortens the length of the computational graph and can be fast and scalable, but struggles with the aforementioned tasks\n\nThe RIR framework is thoroughly evaluated on a simple set of arithmetic tasks (ListOps), where it shows the ability to solve and generalize on this task, while being much faster computationally than previous methods with this ability.\n", "questions": "I think it help the story to have some attention baselines. Although many variants of attention/transformers have been tried in the original LRA works, showing some ablations within the RIR framework (e.g. as either the inner or outer aggregator) seems interesting. This is interesting particularly because attention is often viewed as a catch-all solution to discrete and symbolic data. However I am unlikely to increase my score even if these are shown, and this is just a suggestion that could strengthen the paper and make the overall line of work more convincing.\n", "limitations": "Main limitations are properly addressed. It might be worth being more explicit about the fact that the proposed family of methods is not meant to address other types of sequential data such as perceptual signals (e.g. images/audio) and likely doesn't work in those settings.  (Otherwise people may also wonder why the particular subset of LRA was chosen.)", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The paper provides a very well-explained exposition of a lesser-known model approach.\n- The proposed method/framework is novel and makes intuitive sense.\n- The method performs very well on symbolic processing tasks that it was designed for. It almost preserves the performance of much more expensive methods (e.g. full beam search) while being an order of magnitude faster.\n- Results on other LRA tasks involving language are also shown, indicating that the method is not necessarily specialized to synthetic symbolic processing tasks but could be a viable more general approach\n", "weaknesses": "A weakness of the method itself is that the RIR framework adds complexity because of the two separate levels of hierarchy which can be freely chosen. Additionally the $k$ hyperparameter seems very important and there doesn't seem to be a first-principles way to choose it well. It seems like even if there is a model that can perfectly solve a given task, once RIR is introduced there are no guarantees about whether the task can be perfectly solved. Thus it becomes a heuristic tradeoff between efficiency and strength, with many hyperparameters that must be managed.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review.\n\n* Please check the general response for comments on the complexity of RIR.\n\n\n* Regarding the selection of the hyperparameter $k$, a higher $k$ (chunk size) should be generally better in structure-sensitive tasks. $k=$infinite (or maximum input sequence length) for example would reduce RIR-EBT-GRC to EBT-GRC (which is still better in ListOps). A lower $k$ leads to lower accuracy but higher computational performance. So one first-principle way to choose $k$ is to just settle on the maximum value whose computational performance one is comfortable with. In Appendix Table 1 Ablation we show that reducing $k$ leads to lower performance, as expected, on ListOps  (please see chunk size = 20 or 10). \n\n\n* RIR + Transformer is an interesting area to explore more extensively that we keep for future work. There is a contemporary work that independently came up with a similar idea that they use to achieve OOD generalization on parity tasks [1] - this shows the general potential for the RIR framework. We briefly tried RIR + Transformer once in ListOps but it wasn’t as promising.\n\n\n* We were mainly focusing on language processing tasks where hierarchical bias is relevant (it can be relevant in image domains as well, but it’s more tricky in LRA since the images are flattened). We believe some more work is needed for RvNNs to work well there. Nevertheless, we ran them on CIFAR from LRA, and RvNN-based models can get 60%+ which is worse than the SSM-based/LongConv models but much better than any non-hybrid Transformer models. We will add some more analyses and discussion regarding that. \n\n[1] Transformer Working Memory Enables Regular Language Reasoning And Natural Language Length Extrapolation - Chi et al. ArXiv 2023"}, {"review_id": "98mVyxerwt", "reviewer": "Reviewer_619V", "summary": "This paper addresses the long-sequence modeling problem. A recursion in recursion strategy is proposed to balance the advantages between BB-Tree RvNNs and RvNN models. The idea is straightforward but achieves competitive performance on LRA tasks.", "questions": "See the weakness part.", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is easy to follow.", "weaknesses": "1. There are large numbers of related works missing. For long sequence modeling, there are at least 4 types of methods, including Linear attention, SSM, Linear RNN, and LongConv. Since these methods are implemented for the same goal, they should be included in related work as well as the experiment section.\n2. The experiments are inadequate. LRA is a toy benchmark for assessing long-sequence modeling. It is insufficient to use it as the sole indicator of effectiveness. In fact, this work focuses solely on a sub-task in LRA, making the experiments even weaker. I would encourage the author to verify the actual long sequence modeling capabilities in real-world scenarios such as language modeling, image classification, etc.\n3. Linear RNN has achieved STOA performance in many benchmarks, including LRA, language modeling, and image classification, as demonstrated in recent papers. Why should we consider non-linear RNNs, which are slow to train and perform no better than linear RNNs?\n4. The concept is straightforward and straightforward. By forming a RIR structure, it combines the advantages of the two methods. As a result, the processing time is lengthened. It would be more appealing if the processing time could be shortened. Furthermore, the competitive methods are ineffective. I don't see any standard benchmark LRA results, so it's difficult for me to justify the effectiveness of the proposed method.\n5.The maximum sequence length used in this paper for an efficient long sequence modeling method is 2K, which is a standard sequence length for transformer LLM. It would be preferable to see the proposed method in long sequence tests, such as 32K and higher. Furthermore, long sequence modeling takes much longer to process than transformer, making the method less appealing in real-world scenarios.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review.\n\n* (1.1) Many of the models you mention are already cited. SSM models are cited in [15,16,17,40], LongConv models are cited in [39,12], Linear RNN is cited in [34,30]. Top efficient Transformer based models are cited in [49,9] + indirectly efficient Transformers are referred through [45]. \n\n* (1.2) We will add more citations and discussion in related work. We will add more models in LRA.\n\n* (1.3) Our main goal is balancing scalability with the ability for robust length generalization in structure-sensitive tasks. Correct us if we are wrong, but to our knowledge, this is not tackled by any of the SSM, Linear RNN, LongConv, or Efficient Transformer models. We compare S4D as a representative of LinearRNN/SSM models for length generalization settings, and we also added MEGA (see the general response pdf). Prior results [p5,p6] have already shown that full Transformer models (that efficient transformers try to approximate) don’t work for length generalization in structure-sensitive contexts.\n\n* (2.1) Text and Retrieval tasks in LRA are both realistic tasks - one is IMDB sentiment classification and another AAN document retrieval. Neither is obviously any more toyish than image classification tasks like Sequential Cifar. Besides, “toy tasks” can be important tasks when most existing models struggle with them or fail to learn them in a generalizable manner (eg. logical inference or ListOps) without being inefficient (like Ordered Memory, CRvNN, or original Beam Tree Cell). Besides, in the Appendix we also show experiments on Natural Language Inference, Semantic Similarity, and other sentiment classification datasets. Currently, RIR-EBT-GRC is a sentence encoder model. Scaling it for causal language modeling would require more modifications which would be an interesting direction to explore  for future work. \n\n* (2.2)  It is worth noting that modern RvNNs (CRvNN, BT-RvNN) are relatively less mature. Just because they have some limitations now - doesn’t mean we will not find workarounds later. Please note that even predecessors of modern SSM-based models/S5 [p1,p2,p3] showed limited applicability or limited empirical demonstrations before being picked up and enhanced in the future. Our modeling approach is less mature and would require more development. What we show is that it has a potential in length generalization that is not shown by others (see point 3). \n\n* (3.) “Why should we consider non-linear RNNs, which are slow to train and perform no better than linear RNNs?” - As we demonstrate: our non-linear RvNNs such as RIR-EBT-GRC perform better than Linear RNNs (S4D) in OOD settings or in learning from shorter length data in Table 2 (ListOps)/Table 4 (ListOpsMix) and Table 3 (Logical Inference). We also show that RIR-EBT-GRC performs better than MEGA in similar settings (please see general response pdf). \n\n* (4.1) Regarding RIR complexity, see the general response. As expected from the theoretical time complexity, RIR-X speeds up any recursive model X by an order of magnitude (please see Table 1 in the main paper) - and thus reduces processing time.\n\n* (4.2) You are right that other ListOps-competitive RvNNs are inefficient for LRA. But that’s precisely what justifies the efficiency of RIR-X models in comparison to prior RvNNs. Besides that, we have also shown comparisons between RIR-X and X models in Table 1, Table 2, and other natural language tasks in the appendix - all of which show where our main RIR-based models stand in contrast to prior RvNNs in tasks where we can compare them. In the general response pdf, we also added Pareto frontiers showing the effectiveness of RIR-X models. \n\n* (5.) The maximum length for IMDB (LRA Text)  is 4000 (not 2K). Our model will not be as efficient with 32K+ but please see point 2.2 above on this issue. Moreover, efficiency seems to come at other costs like OOD robustness (point 3).  One future extension for RIR-framework could be to compress the sequence length beforehand like Funnel Transformer [p4] before running the model to make it handle larger sequence lengths. \n\n[p1] HiPPO: Recurrent Memory with Optimal Polynomial Projections - Gu et al. Neurips 2019\n\n[p2] Legendre Memory Units: Continuous-Time Representation in Recurrent Neural Networks -Voelker  Neurips 2019\n[p3] Parallelizing Linear Recurrent Neural Nets Over Sequence Length - Martin et al. ICLR 2018\n\n[p4] Funnel-Transformer: Filtering out Sequential Redundancy for Efficient Language Processing - Dai et al. Neurips 2020\n\n[p5] The Importance of Being Recurrent for Modeling Hierarchical Structure - Tran et al. EMNLP 2018\n\n[p6] Ordered Memory - Shen et al. Neurips 2019\n"}, {"review_id": "R4t7i7yXwP", "reviewer": "Reviewer_ozsz", "summary": "In this work, the authors try to combine the best of two worlds in proposing Recursion in Recursion, where outer recursion is K-array balanced binary tree and inner implements its cell function for recursive neural networks for sequential inputs. The proposed framework is tested on various logical inference and NLP tasks to show model can reach respectable performance and scale to longer sequences. ", "questions": "I would like to see the computational complexity analysis, such as number of FLOPs, average time for convergence for the proposed model, It is not clear what advantage proposed framework offers and what is the loss in performance. Given current paper is mainly focused on improving the scaling capability more focus should be given these problems\n\nEffect of computation budget, can authors also report values when computational budget is higher, it is not clear how higher budget would lead to better gain, and what is the bound for it (k)\nHow did you choose beam size 5 and 7? Beam search should be conducted on dev set and not on test set, so how did authors come to this conclusion is challenging to understand, can authors provide more details, how did you obtain this beam search number?\n\nThe variance for RIR based model is big, it shows they are highly unstable, can authors comment on that?\n\nIn appendix authors have written “At any iteration t, we start only with some sequence”, what is some sequence, such terms is used throughout the paper, and its difficult to know what is the bound. Please provide bound or some numbers to back these claims\n\nWhy there is a need of using 2-layer MLP for fix-1 (line 133 in appendix), why not simple linear transformation, I am confused how mathematically it suffix the same function and how does it approximate the prior function?\n\nDoes beam alignment find good structures that support required compositionality? More analysis is needed on the distribution and Importance of beam alignment.\n\nMissing relevant work [1] and [2]\n\n\n1.\tMali, A., Ororbia, A.G., Kifer, D. and Giles, C.L., 2021, May. Recognizing and verifying mathematical equations using multiplicative differential neural units. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 35, No. 6, pp. 5006-5015).\n2.\tArabshahi, F., Lu, Z., Singh, S. and Anandkumar, A., 2019. Memory augmented recursive neural networks. arXiv.", "limitations": "1. Language can be improved, some sequence, some score, some function such terms should be avoided while explaining any mathematical concepts.\n2. The variance of the proposed model is big leading to instability, hence what benefits it offers is questionable. What about the generalization effect, how does the model work on longer sentences? What is the limit? These questions are still unclear.\n3. More analysis will benefit the work.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. Good paper on scaling.\n2. Paper is well written\n3. Good sets of experiments.", "weaknesses": "1. Novelty is limited. The paper is more focused on scaling and several works are already published in the literature\n2. Why inner cell uses BT-RvNNs, given they are similar to CYK-based RvNNs, and what advantage it offers should be mentioned in depth. Since selecting top-k is still heuristic and based on beam size, results will vary.\n3. Huge standard deviation, indicating potential instability in the model.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review.\n\n**Re Weaknesses:**\n\n1. Our goal is not pure scalability. Our goals are (i) to extend RvNNs in a novel manner that achieves a balance between scalability and length-generalization capacities in structure-sensitive contexts (ii) to show that it has competitive results (if not SOTA)  in LRA compared to SSM/linear RNN and generally much better results than non-hybrid Transformers.  We are unaware of other works attempting to balance scalability with length generalizability in structure-sensitive contexts. Besides, penalizing the lack of novelty of the research goal would lead to penalizing any novel method trying to improve on any pre-established research goals. \n\n2. CYK models are much more expensive than BT-RvNN and show less performance in the non-RIR setup. This is shown in the appendix paper “Beam Tree Recursive Cells” (please see  Tables 1, 4, 5, 8 of that paper). Moreover, practical implementations of CYK-based RvNNs involve soft-attention-based marginalization of paths at every inner loop [1] or similar top-k-based selection [2] - bringing back heuristics. \n\n3. Huge std (+-9) is only shown by a specific RIR-variant  “RIR-EBT-GRC - S4D” in a specific task - ListOpsMix (if you have some other result in mind where there is a huge std, please point it out). It’s not a general norm. Besides, even the “worst” run of that model in that task is $61.45$ which is still better than all models in Table 4 except RIR-EBT-GRC.  \n\n**Re Questions:**\n\n1. See the general response for complexity analysis. Accuracy comparisons between the models are charted for various datasets - ListOps (Table 2), Logical Inference (Table 3), and many other NLP tasks in the Appendix. Empirical time/memory comparisons between the models are charted in Table 1. Combined they show the performance-cost tradeoff. We also add Pareto frontiers in the General Response PDF.  We can add FLOPs/convergence in the final version.\n\n2. As far as we are aware, we do not claim that a higher computational budget by itself leads to better performance. But higher chunk size ($k$) can lead to better gain and a higher computational budget can allow us to use bigger $k$. Theoretically, this is because higher $k$ leads to less of an artificial restriction from the outer balanced-tree structure (for example in the case of $k=$infinite, we recover EBT-GRC which still performs better than RIR-EBT-GRC in structure-sensitive tasks at the cost of memory and time). Empirically, we show this in ablation Table 1 (where reducing chunk size $k$ to 20/10/2 from 30 leads to worse performance in general (k=2 is equivalent to BBT-GRC)).\n\n3. A higher beam size can expand the search space and enhance error recovery (prevent chances of filling the beams with all bad structures). As such, higher was chosen a priori because RIR makes it more feasible to use a higher beam size. \n\n4. We found that “RIR-EBT-GRC - S4D” fails in utilizing the low-sequence-length data as well (but still better than S4D and others) in ListOpsMix in some runs but utilizes it much better in others. Otherwise, in general, we do not observe high standard deviation for RIR models in general or even “RIR-EBT-GRC - S4D” in general (see other LRA experiments for example besides ListOpsMix). Also, please refer to point 3 in Re Weaknesses.\n\n5. “Some sequence” refers to a sequence $\\in \\mathbb{R}^{n \\times d}$ (n being the sequence size). We will add more clarifying notations. \n\n6. Linear transformation can be used but we haven’t tried it. We used a non-linear function because linear functions are less expressive and because the original scoring also involved non-linearity. We do not have to “approximate” the original function in any strict sense - we just need a reasonable scoring function that gets the same input format and can be trained with gradient descent. The point is that the original function is computationally more expensive and without any clear a priori motivation for using it - and at the same time, empirically (i.e., a posteriori) it doesn’t show much better accuracy (as shown in various EBT-GRC vs BT-GRC experiments in the main paper and the appendix). \n\n7. Strictly speaking “good structures” in a human interpretable sense is abandoned in RIR-framework (unless one uses non-RIR inference but then beam alignment will not be relevant during inference) because of enforced balanced tree outer recursion. Beam alignment simply allows alignments of beams  from different chunks to be sensitive to beam score. The usefulness of beam alignment is empirically shown in Ablation Table 1 (in appendix). Both random alignment (+Random Align) and removal of beam alignment (-Beam Align) result in poorer performance. More intuition (with diagrams in the general response pdf) on beam alignment is provided in the general response.\n\nWe will add the citations you mentioned. Thank you. \n\n[1] Jointly Learning Sentence Embeddings and Syntax with Unsupervised Tree-LSTMs - Maillard et al., Natural Language Engineering 2019\n\n[2] Unsupervised Parsing with S-DIORA: Single Tree Encoding for Deep Inside-Outside Recursive Autoencoders - Drozdov et al. EMNLP 2020\n"}, {"review_id": "yBBQLV76Mo", "reviewer": "Reviewer_UxTS", "summary": "The paper proposes Recursion in Recursion (RIR) to address the shortcomings that computationally efficient models like Binary Balanced Tree Recursive neural networks have in solving arithmetic tasks like ListOps. RIR also seeks to alleviate the computational burden brought forth by structure-aware ListOps-competent models such as the Beam tree RvNN. The approach, relying on 2 levels of computation, break down a sequence into chunks (of length k) on which an inner loop uses another network (e.g. Beam tree RvNN) to compute local representations. The representations from the inner loop are subsequently taken in by an outer loop. The authors suggest that this approach can help scale structure-aware inference from (n) to (k*log_k(n)), where n is the input length. The authors conducted experiments to show that their RIR-based models use much less time and memory for the ListOps task than baseline approaches. The results on ListOps, logical inference and long range arena (LRA) show that even with this efficiency, RIR’s performance is competitive with current baselines. ", "questions": "Typo: line 102: gaurantee -> guarantee", "limitations": "Yes, addressed.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper proposes a scaleable solution that can be structure-aware and effective at tasks like ListOps.\nExperiments have shown that this approach (RIR) is promising, with performance competitive with less-efficient baselines. \nOverall, the paper is well-written and the contribution is clear.\n", "weaknesses": "Modifications are required to integrate existing models into the RIR framework, e.g. the EBT-RvNN, which can limit the widespread use of this approach.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review.\n\nPlease note the general response for clarification on the complexity of the approach.\n\nWe will fix the typo.\n"}, {"review_id": "P0vksqCrij", "reviewer": "Reviewer_jzGF", "summary": "The paper proposes a novel framework - Recursion in Recursion (RIR) for tree recursive neural networks (Tree-RvNNs) so as to get around the issue of computational infeasibility of typical RvNN models (Beam tree RvNNs are $\\mathcal{O}(n)$) while still being able to exhibit length generalization on simple arithmetic tasks like ListOps. The models based on RIR have recursive depth bounded by $k\\log_k n$ and still demonstrates over $90\\%$ length generalization performance. They explain their method thoroughly and also compare on ListOps and LRA with a fairly large suite of baselines showing that their method perfoms comparably with the best.", "questions": "1. What is \"infinite receptive field\" mentioned on line 37? Is there a reference for this?\n2. Have you checked the scaling of $k$ with $n$? Does setting $k=\\mathcal{O}(\\log n)$ for some reasonably small constant consistently work?\n3. Can you explain the problem with the string-it solution more clearly? I still don't follow it. Further, it seems like the beam-alignment solution applies it anyway after throwing some randomness into the mix.\n4. The statement \"set the chunk size according to one's computation need\" seems quite vague. Can you explain?\n5. What is the take away from Table 2? RIR-EBT performs well, but not as good as EBT-GRC. Is there a precise compute vs acc tradeoff here?", "limitations": "Yes. I commend the authors for including an honest and thorough limitations section.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "1. The paper is very well written.\n    - The method and related work is explained thoroughly while providing sufficient intuition.\n    - If anything, I would urge the authors to explain the results a little more thoroughly even if it were at the cost of pushing some of the other content to the appendix.\n2. The experiments are thorough.\n    - The authors compare with a sufficiently large suite of baselines.\n3. Length generalization is an important and difficult problem that existing methods (such as Transformers) struggle with. Getting RNN length generalization performance without the associated cost blowup is very interestin for the field.\n4.  The authors adequately list the limitations of their work, which I appreciate.", "weaknesses": "1. The authors discuss the choice of $k$ somewhat briefly explaining that small $k$ surely hurts the performance of the resulting model.\n    - On a few examples they try to suggest that $k=\\mathcal{O}(\\log n)$, however, without seeing this varied over several values of $n$, it is hard to justify this claim.\n    - Note that if $k=\\mathcal{O}(n)$, the method loses it's benefits.\n2. The authors build on unpublished work which is cited as \"Anonymous\" and shared in the appendix. This is highly unusual and I have some concerns about this.\n    - While there is nothing inherently wrong with this, it puts the burden of evaluating some of the claims within the paper to yet another unverified paper.\n3. Some of the notation in the paper can be improved. Such as the example used for explanation in Sections 2 and 3: \"$7 + 8 \\times 5 - 2$\". I feel this would be better if explained symbolically like $a_1 \\cdot op_1\\cdot a_2 \\dots$\"\n4. Some claims are not justified very well (such as the Problem with th String-it solution on page 6)\n5. I feel the results need more careful explanation. Table 1 seems like a very important result to justify the proposed method however, I don't understand why the table is split into two. (ListOps competitive and ?) Can you explain this?\n6. In table 4, the proposed method RIR-GRC performs quite poorly, however this is not called out or explained.\n7. Overall, the results are not particularly impressive. And while MEGA is mentioned multiple times, it does not appear to be listed in the benchmarks.\n8. Efficiency and accuracy are compared in separate tables. Since the main contribution of the paper is an efficient implementation of a model that shows length generalization, I would like to see a computation vs performance tradeoff curve. I feel this would go a long way in proving the superiority of the proposed method.\n9. This is very minor but I would recommend the authors include a short explanation of ListOps in the main paper. I understand that the authors chose to push it to the appendix due to space limitations but since it is such an essential part of the paper, I would recommend adding a few lines about it.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review. We will take the formatting suggestions into account. \n\n**Re Weaknesses:**\n\n1. $k$ is a constant. It is the chunk size hyperparameter and is not made to depend on sequence length or the input. Yes, if we set $k$ to be very large (e.g., as large as the maximum input sequence size) then the RIR framework loses its benefit but in the paper we show that a nice trade-off can be achieved by using smaller k. Also, please see the response to Reviewer 8Jr4  for more information on $k$. \n\n2. The cited anonymous work is published in ICML 2023. We provided an anonymous copy because the latest version of the published work was not public at the moment of submission. \n\n4. We have added more intuition about beam alignment in the general response (+ diagrams in the general response pdf). Please let us know if you have other questions. \n\n5. One of our main aims is to balance scalability while preserving competence in length generalization in structure-sensitive tasks like ListOps/Logical Inference. So, our target for efficiency comparison is mainly other ListOps-competent models. We show the computational cost with other methods like S4D, and Binary Balanced Tree  (which are not competent on listops length generalization or logical inference) for completeness but we put them in a different section because they are not the baselines we are most concerned with in terms of computational costs. \n\n6. RIR-GRC is a simpler model serving as an ablation of our main RIR-EBT-GRC  proposal. It also performs worse in Tables 2 and 3 for worse structural bias. Similarly, GRC (RecurrentGRC) tends to perform worse than EBT-GRC/BT-GRC outside the RIR framework as well (results with Recurrent GRC can be found in the appendix paper “Beam Tree Recursive Cells”).\n\n* (7.1) RIR-EBT-GRC is the only model that can be feasibly run in 2000+ sequence length data and can also get 90%+ accuracy in OOD length generalization settings in ListOps (Table 2) and Logical Inference (Table 3). In contrast, S4D/MEGA gets performance within 15-30% in ListOps OOD length generalization settings (900-1000 seq length) and ~60% in logical inference. That is at least a 30% performance gap. Moreover, RIR-EBT-GRC reduces training speed and memory by approximately 30 times in 1500-2000 sequence length settings (Table 1) compared to EBT-GRC. Yes, our accuracy results in LRA IID settings are not SOTA, but the SOTA performance comes at the cost of OOD generalization at the moment.  \n\n* (7.2) For some comparison with MEGA please see the general response pdf.\n\n8. Thank you for the suggestion. We added Pareto frontier graphs in the general response pdf.\n\n**Re Questions:**\n\n1. We will rephrase the “infinite receptive field” mentioned. We used this to refer to the unbounded nature of attention (as opposed to local convolution where interaction in a specific layer is limited to tokens within a window of some limited size).\n\n* (2-3.) We do not set $k$ as dependent on $n$. We simply choose $k$ as big as we can while getting feasible/reasonable computational costs in LRA ListOps. We set  $k=30$. Ablations with smaller $k$ are given in Table 1 Appendix. As expected, in Table 1 Appendix smaller k/chunk-size (k=20,k=10) leads to worse results but can be still better than S4D, Balanced Tree, etc. in length generalization (also EBT-GRC is effectively the result of k=infinite, and BBT-GRC is basically k=2 - and the pattern still holds that higher k yields better results at least in structure-sensitive contexts). \n\n4. In Table 2 in the main paper RIR-EBT-GRC performs better. In Appendix Table 2, it’s a more general problem that RvNN-based models often turn out to be mostly similar in performance with plain RNNs and other alternatives when it comes to more natural language tasks (see, for example, the “Beam Tree Recursive Cells” paper in Appendix). This can indicate that RvNNs are failing to exploit syntactic structures as well in those tasks (perhaps may require pre-training with language modeling) or that these tasks have exploitable statistical shortcuts that allow simpler methods to get ahead. Still, we can see in Appendix Table 3, that in some stress tests of larger datasets like MNLI, RvNN-based models perform better than simpler GRC/RIR-GRC. So there are specific contexts where inductive biases of RvNNs tend to shine more. \n"}, {"review_id": "kRi45tlCT5", "reviewer": "Reviewer_yLki", "summary": "The authors propose a new tree-style RNN that combines the computational efficiency of tree RNNs with the computational power of more complex tree RNNs. The method makes each node perform a recursive computation, so there are logarithmically many nodes but they are more expressive than the standard tree network. The resulting model can operate on long sequences comparably to state space models and much better than vanilla transformers.\n\n**Ethics Review**: It appears to me that the authors broke the integrity of the double-blind reviewing procedure. In lines 144-146, the authors write: \"we use an efficient variant of BT-RvNN (EBT-RvNN). We propose and explore EBT-RvNN in a concurrent work\". NeurIPS policy states: \"If you need to cite one of your own papers, you should do so with adequate anonymization to preserve double-blind reviewing.  For instance, write “In the previous work of Smith et al. [1]…” rather than “In our previous work [1]...”). If you need to cite one of your own papers that is in submission to NeurIPS and not available as a non-anonymous preprint, then include a copy of the cited anonymized submission in the supplementary material and write “Anonymous et al. [1] concurrently show...”).\". As such, I am flagging it for an ethics review.\n\n**Edit after rebuttal**: I have increased my score from 3 to 4.", "questions": "1. In what situations would I use this method instead of other stronger models (e.g., Mega)?\n2. Is there any benefit to using a tree-based model instead of a modified transformer architecture?", "limitations": "The authors discuss the limitations clearly, which I appreciate. They mention that their architecture improves on tree-based RNNs but is much slower than other, seemingly stronger models. It also seems to not be able to learn from long sequences, which may be the point of a long-context model. One thing they do not mention is that their architecture seems to be very complicated and has many tricks involved. They also only evaluate on a few tasks, and they seem to be very focused on ListOps in particular. For other tasks, their method performs comparably to existing tree-based models (lines 325-326).", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The paper improves on other tree-based RNNs by reducing the computation.", "weaknesses": "This may be my lack of understanding on this subject area, but I think this is an overly complicated method that does not outperform existing methods or provide a clear benefit over them. There is some value to advancing a subfield of ML (i.e., tree-based RNNs), but I find it difficult to see the significance of this work. It may also be because of issues with the writing, see below. \n\nBesides the complexity of the method and the performance issues, the authors also do not benchmark on many tasks. They focus on the ListOps task from the Long Range Arena benchmark and don't consider Mega, which has achieved SoTA on this task.\n\n**Writing**: Overall the writing is very difficult for someone who has not been actively thinking about this problem and working with tree-style RNNs. I found it very difficult to read the introduction and abstract because there is too much jargon. Below are some suggestions and questions that may help the authors improve their writing for an audience that is not working on tree-based RNNs. I generally recommend refactoring the writing into formal definitions so it is clear to see how the inner and outer recursions work together. As it stands, I couldn't even write down how your method would actually process a given input.\n- Can you make a figure illustrating these different trees instead of trying to describe them in the text?\n- I don't know what a \"strong RvNN\" is or what it means to process only some arguments that are sent in from an outer loop. (lines 75-79)\n- Can you introduce clearly what ListOps is and why it is important to be length-generalizable for that task? \n- There is not enough information about these other methods in the tables and how they 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**Re Ethics:**\n\nWe will not say too much about this given Ethics Reviewers have already checked it out. We didn’t provide any deanonymizing information about the work. While we haven’t cited the work or provided the anonymized copy at the moment (we will cite it in the final copy), we have provided all the necessary details pertinent to this work in the main paper and the appendix. If there are still some questions, we will be happy to clarify. \n\n**Re Weaknesses:**\n\n* Please see the general response comment on complexity.\n\n\n* Significance: While models like  S4D, and MEGA are generally powerful, they can struggle in structure-sensitive tasks and in length generalization (eg. in Logical Inference, and ListOps). On the other hand, models like OM, CRvNN, BT-GRC, EBT-GRC can generalize more robustly but they are very slow to run (please see Table 1). Our work proposes a framework to strike a better balance between length generalization capacity and competence in long sequence tasks (as alluded in the title of the paper). Also see the Pareto Frontier graphs in the General Response PDF for some visualizations. Moreover, as you noted, there is value in exploring niche areas and alternative approaches too (so as to not put all the eggs in one or two baskets) even if right now there are limitations to RvNNs.  \n\n\n* We also have results of logical inference (Table 3), results on IMDB, AAN retrieval from LRA (Table 4), and other NLP tasks in the Appendix. We added MEGA results in the general response pdf.\nWe will improve the writing.\n\n\n* “strong RvNNs” refers to the modern RvNNs that can perform well in tasks like ListOps/Logical Inference (eg. OM, CRvNN, BT-GRC).\n\n\n* ListOps is an arithmetic task with nested list operators example: “[MAX [MED [MED 1 [SM 3 1 3 ] 9 ] 6 ] 5 ]” the answer is 6 (here MED is median, and SM is modulo 10 summation). We will add more details in the paper.\n\n\n* Importance of length generalization: first, we can ask ourselves how do we know if a neural network learns the “right” function and is not simply exploiting some surface statistical bias from the training dataset. One simple way to test this is to test the model in unseen datasets (the test set). But this is not necessarily ideal. Test sets, if it is from the same (IID) distribution as the training set, may share some statistical biases which the model can be exploiting. So what can we do? One thing we can do is to think of specific isolated factors of generalizations that a neural network should exhibit if it learns the desired function from the data. For example, we may want the neural network to be robust against local perturbations. So we may try to test in some adversarially perturbed datasets. Or we may want the neural network to be robust to counterfactual modifications - and we may then create counterfactual test sets [1]. Similarly, “length generalization” is one such factor of generalization to test a model on. Particularly, if a human is taught arithmetic on examples up to length $100$, we would expect them to be able to solve arithmetic problems on length $>100$ without ever seeing higher-length examples before. We can check if a Neural network can exhibit similar robustness/generalization capacities. Overall, length generalization has been a topic of interest for a long time in the ML community. \n\n\n* Regarding details on other models, OM [2] is a form of stack-augmented RNN (think of pushdown automata), whereas CRvNN [3] is like a standard RvNN but it softens the sibling selection and updates mechanisms. We will add more details on these models.\n\n\n\n**Re Questions:**\n\n1. You could use our method instead of Mega when you want better OOD generalizations, particularly with tasks that require stronger structural bias. \n\n2. Modified Transformer and Tree-based models are not a dichotomy. There are Tree-based Transformers too. CRvNN is also Transformer-like in some respects. Regardless, models that are closer to the structure of Transformers have generally failed to show robust length generalization in tasks like ListOps, mathematical tasks, and propositional logical inference [2,4]. Neural Data Router [5] makes good progress but it still shows limitations in generalizing to order of magnitude higher depths and lengths (as studied in the “Beam Tree Recursive Cells” paper in the appendix). \n\n\n[1] Learning The Difference That Makes A Difference With Counterfactually-Augmented Data - Kaushik et al. ICLR 2020\n\n[2]  Ordered Memory - Shen et al. Neurips 2019\n\n[3]  Modeling Hierarchical Structures with Continuous Recursive Neural Networks - Ray Chowdhury et al. ICML 2021\n\n[4] The Importance of Being Recurrent for Modeling Hierarchical Structure - Tran et al. EMNLP 2018\n\n[5] The Neural Data Router: Adaptive Control Flow in Transformers Improves Systematic Generalization - Csordas et al. ICLR 2022\n\n\n\n"}, {"review_id": "F2eRiScC2f", "reviewer": "Reviewer_CUBJ", "summary": "The paper studies a “recursion in recursion” (RIR) approach, the outer loop being a balanced k-tree recursive NN, and the inner loop a general recursive NN that is based on a beam tree. The goal is to obtain O(k*log_k(N)) time complexity. O(2*log_2(N)) is a special case of k=2 (for binary trees) and O(N) is the special case of k=N for RNNs. The authors study (mostly) the tradeoff between performance on ListOps and Long Range Arena (LRA). Namely, RIR seems competitive to strong baselines on LRA (e.g. state space models), yet it generalizes better on longer lengths in ListOps.", "questions": "Q1. Why do you think that RIR is not very helpful for inference? I like it because of the more efficient inference that it enables. Is it possible to demonstrate the efficiency/ accuracy trade-off with another Pareto frontier plot?", "limitations": "the authors adequately addressed the limitations", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "S1. The paper is very well written. The research process is embedded in the structure of the paper: “motivation -> problem -> solution -> new problem -> new solution -> etc.”\n\nS2. The  modifications are quite reasonable and the experiments are thorough (the appendix was helpful too).\n\nS3. The papers’ evidence matches the claims quite well and the limitations are well-acknowledged.", "weaknesses": "W1. It is very hard to read through the tables. Since you are studying a trade-off of time/ memory efficiency and performance on ListOps, and likewise ListOps vs. LRA performances, I would expect scatter plots that trace out a Pareto frontier and where your RIR contributions lie on this frontier. \n\nW2. Despite the work being very engineeringly sound and well-presented, one could argue that the contributions as “combinatorial” and mostly heuristic vs. fundamental. That is OK, but one could consider it a weakness within the context of NeurIPS. \n\nW3. Following up on 2., it may be good to discuss the significance of your contribution to larger tasks and broader / realistic data distributions. For example, how would RIR might be a part of a state-of-the-art LLM architecture in the future?\n\nW4. Perhaps the most exciting discussion for me is about different inference strategies (whether to use RIR or not). I acknowledge that you have addressed some of that in the SM, but I would have expected to see a bit more discussion in the main text.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review.\n\n**W1:** We will add the Pareto frontier graphs. We currently show them in the General Response PDF.\n\n-----\n\n**W3:** At this point, we can suggest some speculative moves we can make to set up RIR-EBT-GRC in an LLM context. \n\nFirst, we need to think about parameter scaling. The naive way to scale parameters would be simply increasing the dimensions of the recursive cell. This is inefficient in recursive contexts (this would lead to repeating a large layer for indefinite times based on sequence length). Some alternatives can be to look for some sort of modular/MoE approach (where each recursion operates on some sparse parameters from a bigger parameter set) or to try some form of stacking (just as we, sometimes, stack RNNs). Now, stacking RIR-EBT-GRC is not immediately possible because it’s a sentence-encoder (it compresses a sequence of vectors into a single vector after which there is not much room to add another sequence model). However, one thing we can do is try to create a token contextualization by sending top-down signals from representations of whole to representations of parts (initial token representations) (similar to [1]). In fact, we are exploring this idea in a concurrent paper by using a parent attention mechanism. This can allow stacking the output of RIR-EBT-GRC with other RIR-EBT-GRCs, Transformers, SSMs, or CNNs (and the overall model can utilize a mixture of inductive biases).\n\nSecond, after parameter scaling, another main difficulty is utilizing it in a causal LLM training context. A difficulty is that RIR-EBT-GRC is a bidirectional model. We can still train a bidirectional model for LLM by sequentially entering the expanding context in a loop but this would be slow. To make it tractable, first, we can use a Block-Recursive style framework [2] and second, we can limit the use of RIR-EBT-GRC for specific intervals (use it sparsely), and use a simpler model that use the latest RIR-EBT-GRC-created past hidden states + free tokens (causally masked) to make predictions in between. Some loosely related ideas are used in [5] (they are also trying to work with looping a bidirectional model for autoregressive generation). \n\nEven after all these, the overall setup would probably not be as fast as Transformer training. But speed or even mere surface capacity to handle big contexts is not everything - and can come at other costs [3,4]. \n\n[1] Head-Lexicalized Bidirectional Tree LSTMs - Teng et al. TACL 2017\n\n[2] Block-Recurrent Transformers - Hutchins et al. Neurips 2022\n\n[3] Exposing Attention Glitches with Flip-Flop Language Modeling - Liu et al. ArXiv 2023\n\n[4] Lost in the Middle: How Language Models Use Long Contexts - Lie et al. ArXiv 2023\n\n[5] Real-World Compositional Generalization with Disentangled Sequence-to-Sequence Learning - Zheng et al. ArXiv 2022\n\n-----\n\n**W4-Q1:** We will add RIR inference details in the main text. We will also add trade-off information. But overall, to answer the question - in most tasks (including LRA) RIR-inference seems to work nearly as well as non-RIR-inference. So in most cases, RIR inference is a “win-win” (several times faster + nearly the same accuracy). However, when a model is working in a structure-sensitive context, it may find it difficult to learn to length generalize as well through an RIR format (it still does better than S4D/MEGA in the ablation Table 1 in Appendix) -- because ultimately the balanced-tree enforcement is a restriction on the search space that is generally unsuited for structure-sensitive tasks (and merely done for efficiency). However, the existence of data length <= chunk size, leads to some non-RIR training instances which probably helps teach the inner recursion to learn to length-generalize. Thus, testing without RIR inference (i.e., running the inner recursion model in the full input) can still lead to length generalization and be even better (in structure-sensitive contexts when the inner recursion indeed learns to utilize the relevant structures in a length-generalizable manner) due to the lack of balanced tree enforcement work. In these cases, RIR inference can reduce the performance compared to non-RIR inference. Note, however, since the use of -Beam Align or +Random Align during training reduces the non-RIR inference accuracy (these changes only make an impact for instances running in RIR mode), the RIR instances (i.e., instances with sequence length > chunk size) should be still providing some training signals  in helping the inner recursion model to learn to generalize. \n"}, {"review_id": "MAWWd85xoE", "reviewer": "Reviewer_3jTN", "summary": "Recursion in Recursion combines the efficiency characteristics of Binary Balanced Tree Recursive Neural Networks (BB-Tree RvNNs) and quality characteristics of Beam Tree RvNNs by applying the recursion in a hierarchical fashion.\n\nDoing so is not straightforward and requires several \"modifiers\" such as Beam Alignment and being careful about chunk preprocessing in the outer recursion.\n\nTable 1 demonstrates that the method is efficient in both time and memory. Table 2 demonstrates that the model quality is compromised but not by much.", "questions": "I would be curious about how frequently bad chunk processing happens and the model's ability to recover? How much does S4D help here?", "limitations": "The authors have a limitations section that discuss slowness and lack and difficulty to generalize.\n\nTo me the the method seems complex. I am not sure if it is broad applicable given that it is still slow and model quality is still lacking.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The paper provides necessary background which I appreciated since I am not too familiar with RvNNs. Experiments seem well done and reproducible. The method is efficient as promised and still maintains the ability to generalize to sequence length.\n\nWhile the method is still slow and seem less mature than other methods like transformers, I think RvNNs are interesting and worthy of discussion because of their explainability and ability to generalize to longer sequences.", "weaknesses": "While interesting, the method seems rather complex to apply generally with 2 levels of recursion and necessary modifiers to integrate them effectively.\n\nThe beam alignment section I found particular confusing. Maybe there could be a figure to help understanding?\n\nThe inability to generalize on argument length could use more discussion.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review.\n\n**Re Weaknesses**\n\n1. Please see the general response for the clarification on the complexity.\n\n2. We provide figures and additional intuition on beam alignment  in the general response. \n\n3. Argument generalization was a recently proposed challenge, and currently, most models struggle with it - including GoldTreeGRC (a model with ground truth structure data). We will need to investigate the cell function or other training strategies for proper argument generalization which would require separate work and is left as future work. Note that while it’s a limitation of our model in not being as good at argument generalization, this limitation, at the moment, is nearly universal - shared by most of the popular models - S4D, Transformers (Transformers struggle even IID [2]), MEGA, and others. Only one or two models lacking explicit structure-information (OM, EBT-GRC) are moderately good but still falling behind 90%. \n\n**Re Questions**\n\n1. Bad chunks should happen nearly 100% of the time since ListOps is not set up to have balanced structures at any level. We show the comparison of “RIR-EBT-GRC” vs “RIR-EBT-GRC-S4D” in various Tables (please see Table 2 and Table 4). As we find there, S4D actually does not help much. So this is an area open for improvement/further investigation. The ability to “recover” the right structure through bad chunks is hard to check because if it recovers it has to do it internally by organizing information in its hidden states in the right way (analogous to how an RNN may model tree structures [3]) which is more of a blackbox process. \n\n**Re Limitations**\n\n1. Note that the difficulty to generalize (e.g., in argument generalization) is also present in other existing models like S4D, MEGA, and Transformers, which fail in length generalization too [1,2]. RIR-EBT-GRC does much better than them.\n\n2. While RIR-EBT-GRC is slower than S4D/MEGA/BBT-GRC - their speed comes at the cost of worse performance in structure-sensitive contexts. Moreover, our proposal - RIR-EBT-GRC is several times faster than other powerful RvNN models (OM, CRvNN, BT-GRC) - making a massive computational improvement for RvNN models (Table 1) while retaining decent performance (Table 2, Table 3). For example, it’s 100s of times faster than OM. \n\nAlso please see the Pareto frontier graphs in the general response pdf which show how RIR-EBT-GRC gains a better trade-off than others. \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] Tree-Structured Composition in Neural Networks without Tree-Structured Architectures - Bowman et al. International Conference on Cognitive Computation: Integrating Neural and Symbolic Approaches 2015\n"}]

Author rebuttal:
We thank all our reviewers for their insightful reviews and comments.

**On the complicacy of RIR:**

* **RIR Computational Complexity:** RIR-X is generally computationally more efficient than X both memory-wise and time-wise. For example, this can be observed in RIR-EBT-GRC vs EBT-GRC in Table 1. If the time complexity of X is $O(f(n))$ (n being the sequence size), the time complexity for RIR-X is  $O(\log_k{n} f(k))$. This can effectively turn into $O(\log{n})$ if $k$ is a constant.

* **RIR Implementation Complexity:** RIR is only slightly more complicated to implement. Particularly, balanced tree recursion is a simple algorithm, and all we have to do is import some existing code for inner recursion within the balanced tree recursion for the 2-level recursion. In the case of BT-RvNN, there is an extra complexity for beam alignment but that too is only a few lines of code. Adding pre-chunk S4D contextualization is optional and requires adding only 2-3 lines of code if we are importing from an existing implementation of the inner recursion model. 

* Overall, implementation of RIR-EBT-GRC (without S4D) from scratch can still be simpler (or as complex) as prior approaches like Ordered Memory or CRvNN. Also, the code is shared in Supplementary Materials (and will be open-sourced in GitHub with documentation) to allay implementation difficulties. 

**Updates in the Rebuttal PDF (attached below)**:

1. We added MEGA results on ListOps (Table 1)  and Logical Inference (Table 2). As can be seen from these results, MEGA performs better than S4D but still falls behind RIR-EBT-GRC by a large margin in structure-sensitive length generalization contexts. 

2. We added scatter plots + Pareto frontiers in Fig. 2. In all three subfigures (focusing on different trade-offs)  in Fig. 2, RIR-EBT-GRC (RRE in the figures) remains as a Pareto-efficient solution that maintains a highly competitive trade-off. S4D, BBT-GRC, and RIR-GRC can win on the time cost and memory cost compared to RIR-EBT-GRC, but with a sharp degradation of OOD performance in structure-sensitive tasks (logical inference, ListOps). While OM, CRvNN, BT-GRC, BT-GRC OS, and EBT-GRC can outperform RIR-EBT-GRC (to an extent) on OOD length generalization accuracy in ListOps and logical inference, they come with much more exorbitant time/memory cost. 
We also added more clarification diagrams for beam alignment in Figures 1a, 1b. That is, in Fig 1a, we show the visualization of the String-it solution and in Fig 1b, we show the visualization of the beam alignment solution. 

**Additional Beam Alignment Intuitions:**

RIR framework allows a degree of parallel processing - multiple non-overlapping chunks can be simultaneously processed by the inner recursion cell. 

However, when the inner recursion cell is EBT-GRC, each chunk will return different lists of $b$ beams (sorted in the descending order of their scores). If there are $m$ chunks, we will have $m$ lists where each list will have $b$ beams. Each beam should have a scalar beam score and a beam sequence $\in \mathbb{R}^{1 \times d}$ where $1$ is the sequence size and $d$ is the hidden state size. But for the next iteration, we will need a single list of $b$ beams (where each beam should have a scalar beam score and a beam sequence $\in \mathbb{R}^{m \times d}$ where $m$ is the sequence size and $d$ is the hidden state size. Note that $m$ is initially the number of chunks. After combining the outputs of the chunks, we get the sequence size. Since output of each chunk has sequence size 1, concatenating output of m chunks lead to m sequence size.). The question then is - how to combine the different $m$ lists of $b$ beams into a single list of $b$ beams. 

In the visualizations, we consider a simple scenario where $m=2, b=3$. The String-it solution (Fig. 1a), is to simply concatenate the beam sequences (and add the corresponding scores) from all lists that occur in the same position. For example, in Fig. 1a we concatenate the first beam (Beam Sequence 1) from the first list (chunk 1 results) with the first beam (Beam Sequence 4) from the second list (chunk 2 results). Similarly, we concatenate the second beam from the first list with the second beam from the second list, and so on. 

However, we want to create "high-scoring" beam combinations with more probability. However, the string-it solution does not care for that. For example, ``Beam Sequence 1 + Beam Sequence 5" would be the second highest-scoring beam, but it cannot be ever selected by string-it since Beam Sequence 1 is in the first position of the first list, and Beam Sequence 5 is in the second position of the second list - that is, they are not in the same position. 

Thus, we propose Beam Alignment where we take a stochastic approach towards the ideal of biasing the preservation of high-scoring combinations. For this approach, instead of immediately applying the string-it solution, we make the beams in each list stochastically 'compete' for their positions. Essentially, we want high-scoring beams to be more likely to occupy more positions in the beam lists from each chunk. This is done by simply sampling a beam per list position (for each of the $b$ positions) according to the normalized beam score distribution. The result is that the beam lists will be now filled with mostly the higher-scoring beams (See the results after `Sample' in Figure 1b). Next, if we simply apply the string-it solution at this point, it automatically leads to high-scoring combinations as we wanted because of the prior sampling of high-scoring combinations. Now there is a possibility of combinations like ``beam sequence 1 + beam sequence 5" to arise because the sampling step allows the same beam to occupy multiple positions. 

Overall as we can see, in the simulation of Beam-alignment (Fig. 1b) the resulting combined beams tend to have higher scores than in the case of the direct application of String-it (Fig. 1a). 


Meta-review: This paper received many reviews and generally there have been good evidence and support for the acceptance of this paper.
Decision: Accept (poster)