Recursion in Recursion: Two-Level Nested Recursion for Length Generalization with Scalability
Binary Balanced Tree RvNNs (BBT-RvNNs) enforce sequence composition according to a preset balanced binary tree structure. Thus, their non-linear recursion 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, RvNNs (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 than even RNNs. 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 (BT-RvNN). To adjust BT-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. 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: \url{https://github.com/JRC1995/BeamRecursionFamily/}.
Paper
Similar papers
Peer review
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. Doing so is not straightforward and requires several "modifiers" such as Beam Alignment and being careful about chunk preprocessing in the outer recursion. Table 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.
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. While 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. The beam alignment section I found particular confusing. Maybe there could be a figure to help understanding? The inability to generalize on argument length could use more discussion.
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?
Rating
4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
2 fair
Contribution
2 fair
Limitations
The authors have a limitations section that discuss slowness and lack and difficulty to generalize. To 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.
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.
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.” S2. The modifications are quite reasonable and the experiments are thorough (the appendix was helpful too). S3. 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. W2. 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. W3. 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? W4. 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.
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?
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
3 good
Contribution
3 good
Limitations
the authors adequately addressed the limitations
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. **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. **Edit after rebuttal**: I have increased my score from 3 to 4.
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. Besides 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. **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. - Can you make a figure illustrating these different trees instead of trying to describe them in the text? - 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) - Can you introduce clearly what ListOps is and why it is important to be length-generalizable for that task? - There is not enough information about these other methods in the tables and how they work.
Questions
1. In what situations would I use this method instead of other stronger models (e.g., Mega)? 2. Is there any benefit to using a tree-based model instead of a modified transformer architecture?
Rating
4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
Confidence
2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
2 fair
Presentation
2 fair
Contribution
2 fair
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).
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.
Strengths
1. The paper is very well written. - The method and related work is explained thoroughly while providing sufficient intuition. - 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. 2. The experiments are thorough. - The authors compare with a sufficiently large suite of baselines. 3. 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. 4. 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. - 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. - Note that if $k=\mathcal{O}(n)$, the method loses it's benefits. 2. 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. - 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. 3. 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$" 4. Some claims are not justified very well (such as the Problem with th String-it solution on page 6) 5. 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? 6. In table 4, the proposed method RIR-GRC performs quite poorly, however this is not called out or explained. 7. Overall, the results are not particularly impressive. And while MEGA is mentioned multiple times, it does not appear to be listed in the benchmarks. 8. 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. 9. 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.
Questions
1. What is "infinite receptive field" mentioned on line 37? Is there a reference for this? 2. Have you checked the scaling of $k$ with $n$? Does setting $k=\mathcal{O}(\log n)$ for some reasonably small constant consistently work? 3. 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. 4. The statement "set the chunk size according to one's computation need" seems quite vague. Can you explain? 5. 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?
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
4 excellent
Contribution
2 fair
Limitations
Yes. I commend the authors for including an honest and thorough limitations section.
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.
Strengths
The paper proposes a scaleable solution that can be structure-aware and effective at tasks like ListOps. Experiments have shown that this approach (RIR) is promising, with performance competitive with less-efficient baselines. Overall, the paper is well-written and the contribution is clear.
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.
Questions
Typo: line 102: gaurantee -> guarantee
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
3 good
Contribution
3 good
Limitations
Yes, addressed.
Acknowledgement of rebuttal
I have read the authors' rebuttal and decided to keep my original score.
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.
Strengths
1. Good paper on scaling. 2. Paper is well written 3. 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 2. 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. 3. Huge standard deviation, indicating potential instability in the model.
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 Effect 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) How 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? The variance for RIR based model is big, it shows they are highly unstable, can authors comment on that? In 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 Why 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? Does beam alignment find good structures that support required compositionality? More analysis is needed on the distribution and Importance of beam alignment. Missing relevant work [1] and [2] 1. Mali, 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). 2. Arabshahi, F., Lu, Z., Singh, S. and Anandkumar, A., 2019. Memory augmented recursive neural networks. arXiv.
Rating
5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
2 fair
Presentation
2 fair
Contribution
2 fair
Limitations
1. Language can be improved, some sequence, some score, some function such terms should be avoided while explaining any mathematical concepts. 2. 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. 3. More analysis will benefit the work.
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.
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. 2. 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. 3. 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? 4. 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. 5.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.
Questions
See the weakness part.
Rating
5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
3 good
Presentation
3 good
Contribution
3 good
Limitations
Yes.
Summary
This paper introduces the recursion-in-recursion (RIR) framework for balancing the tradeoffs between 1. 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 2. balanced tree recursion, which shortens the length of the computational graph and can be fast and scalable, but struggles with the aforementioned tasks The 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.
Strengths
- The paper provides a very well-explained exposition of a lesser-known model approach. - The proposed method/framework is novel and makes intuitive sense. - 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. - 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
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.
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.
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
3 good
Presentation
4 excellent
Contribution
3 good
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.)
Thanks to the authors for their response. RE: the ethics review, I just wanted to do my due diligence following the instructions. The authors did a good job of addressing my concerns, particularly with respect to Mega and other Transformer-based models for long sequence modeling. I think the method is sound, and the authors' claims seem reasonable. Ultimately, I still have my concerns about the significance of the work, given how slow and complicated the method is. I recognize the authors' efforts to alleviate concerns about the difficulty of implementing this method, but I still feel that it is a much more complex method for a small gain. Ultimately, I am raising my score 3 -> 4 because I think the work is sound and represents an improvement over other works. I will leave it to the AC and SAC to judge the significance of this work (i.e., the utility of the proposed method) in the subfield of long-range sequence modeling.
Clarification on the gain
Thank you very much for raising the scores. Re: > I still feel that it is a much more complex method for a small gain. We acknowledge (as we did in the limitations of the main paper) the limitation that RIR-EBT-GRC is slower compared to BBT-GRC, S4D, and MEGA but we would like to quantitatively highlight the gains: * RIR-EBT-GRC reduces the training time of EBT-GRC (in Table 1's 1500-2000 sequence length settings) from $10.5$ minutes to $0.3$ minutes. The gain is $35$x speed up here. RIR-EBT-GRC also reduces $10.97$ GB memory of EBT-GRC to $0.43$ GB in the same settings which is ~$25$ times memory reduction while maintaining comparable performance (as you acknowledged: "their method performs comparably to existing tree-based models"). The overall speed-up compared to OM ($255$x) and memory reduction compared to CRvNN/BT-GRC OS ($188$x) is even greater. * Moreover, MEGA gets $23.5$% accuracy in 900-1000 OOD settings of ListOps. RIR-EBT-GRC gets $97.1$%. That's a substantial difference of $73.6$%. * MEGA gets ~$64$% in logical inference with 12 operators (after training on <=6 operators). RIR-EBT-GRC gets ~$93$%. That's nearly a $29$% difference. We acknowledge that in IID settings for long-range sequence modeling, this method is not ideal compared to MEGA/S4D and others. However, the significance motivated for the proposal was not "doing better than others in long-range settings", but **striking a balance** between scalability and length generalizability (including in short-range settings) while maintaining reasonable performance in long-range settings. There are also strategies that follow from the results of the paper to mitigate the speed limitations: * By reducing the chunk size $k$ we can get RIR-EBT-GRC closer to BBT-GRC (a special case of RIR-EBT-GRC when k=2) and start to approach the speed of S4D (in Table 1 in the main paper BBT-GRC is as fast or faster than S4D). Using small $k$ is still competitive in LRA text sets (eg. BBT-GRC performance in Table 1). Although smaller $k$ provides lower performance in OOD settings of ListOps, it's still much better than MEGA/S4D (see k (chunk size)$=10$,k (chunk size) $=20$ results in Ablations Table 1 in Appendix) in comparable settings. * Also because of the length generalization ability of RIR-EBT-GRC, we may not need to train on long-range data. We can train on much shorter data and allow it to length generalize during inference. In fact, RIR-EBT-GRC learns even better from shorter data. RIR-EBT-GRC for example can already get near $61$% on LRA ListOps (~$2000$ sequence lengths) by training on shorter ListOps data ($\leq 100$ lengths) and possibly could get even better if LRA did not have a different number of arguments (most models still struggle to generalize to higher number of arguments. Pure length generalization performance of RIR-EBT-GRC is much better - for example, it retains $97.1$% accuracy when the only difference is sequence length such as 900-1000 sequence length split after training on data $\leq 100$ lengths). ------------- Also, the point about complexity can be a bit subjective if we are not talking about any objective measure like Lines of Codes or Time/Space complexity. It is not so clear why RIR-EBT-GRC should be counted as more complicated than OM/CRvNN or popularly adopted methods in the literature like chart-based RvNNs/CYK-based RvNN [1] which utilizes dynamic programming with nested loops requiring careful implementations for efficiency or its newer extensions with beam search [2] and pruning strategies [3]. Also note that RIR-EBT-GRC, as of now, runs nearly as well without S4D. Compared to RIR-EBT-GRC w/o S4D, S4-based models or successful linear RNNs models [4,5] generally also require sophisticated initialization schemes or hybridization with Transformers with chunking [6], Flash Attention, and other modifiers like adaptive sparsification [7] for memory-efficient performant implementations. [1] Jointly learning sentence embeddings and syntax with unsupervised Tree-LSTMs - Maillard et al. Natural Language Engineering 2019 [2] Unsupervised Parsing with S-DIORA: Single Tree Encoding for Deep Inside-Outside Recursive Autoencoders - Drozdov et al. EMNLP 2020 [3] R2D2: Recursive Transformer based on Differentiable Tree for Interpretable Hierarchical Language Modeling - Hu et al. ACL 2021 [4] Resurrecting Recurrent Neural Networks for Long Sequences - Orvieto et al. ArXiv 2023 [5] How to Train Your HiPPO: State Space Models with Generalized Orthogonal Basis Projections - Gu et al. ICLR 2023 [6] Mega: Moving Average Equipped Gated Attention - Ma et al. ICLR 2023 [7] Sparse Modular Activation for Efficient Sequence Modeling - Ren et al. ArXiv 2023
Thank you for the clarifications
I thank the authors for their detailed rebuttal and for answering all of my questions. I am raising the score to 6 and recommending acceptance of the paper.
I read the rebuttal. I appreciate the clarifications and additions and will raise my score.
Thanks. I would encourage you to add the discussions in the main text/ SM.
Thank you for raising the score. We will add the discussions.
Official Comment by Reviewer 619V
Thanks to the author for the reply, my concerns have been addressed and I will raise the score to 5
Thanks for the rebuttal. I am maintaining my score on the grounds that although perhaps not immediately practical, this work explores an important direction toward structure-sensitive sequence modeling problems that is not sufficiently addressed by existing methods.
Decision
Accept (poster)