# Recursion in Recursion: Two-Level Nested Recursion for Length Generalization with Scalability

arXiv: https://arxiv.org/abs/2311.04449 · HTML: https://mlsanity.com/paper/2311.04449/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 85 of its 107 references that are in the map.
- First posted on arXiv 8 Nov 2023.

## Builds on (most cited first, 30 of 85)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Lost in the Middle: How Language Models Use Long Contexts](https://mlsanity.com/paper/2307.03172/) (2023)
- [Categorical Reparameterization with Gumbel-Softmax](https://mlsanity.com/paper/1611.01144/) (2016)
- [A Broad-Coverage Challenge Corpus for Sentence Understanding through Inference](https://mlsanity.com/paper/1704.05426/) (2017)
- [Efficiently Modeling Long Sequences with Structured State Spaces](https://mlsanity.com/paper/2111.00396/) (2021)
- [Estimating or Propagating Gradients Through Stochastic Neurons for Conditional Computation](https://mlsanity.com/paper/1308.3432/) (2013)
- [Transformer-XL: Attentive Language Models Beyond a Fixed-Length Context](https://mlsanity.com/paper/1901.02860/) (2019)
- [A large annotated corpus for learning natural language inference](https://mlsanity.com/paper/1508.05326/) (2015)
- [An Empirical Evaluation of Generic Convolutional and Recurrent Networks for Sequence Modeling](https://mlsanity.com/paper/1803.01271/) (2018)
- [The Concrete Distribution: A Continuous Relaxation of Discrete Random Variables](https://mlsanity.com/paper/1611.00712/) (2016)
- [Convolutional Neural Networks for Sentence Classification](https://mlsanity.com/paper/1408.5882/) (2014)
- [Simplified State Space Layers for Sequence Modeling](https://mlsanity.com/paper/2208.04933/) (2022)
- [Language Modeling with Gated Convolutional Networks](https://mlsanity.com/paper/1612.08083/) (2016)
- [Long Range Arena: A Benchmark for Efficient Transformers](https://mlsanity.com/paper/2011.04006/) (2020)
- [Annotation Artifacts in Natural Language Inference Data](https://mlsanity.com/paper/1803.02324/) (2018)
- [Transformer in Transformer](https://mlsanity.com/paper/2103.00112/) (2021)
- [Convolutional Sequence to Sequence Learning](https://mlsanity.com/paper/1705.03122/) (2017)
- [Learning the Difference that Makes a Difference with Counterfactually-Augmented Data](https://mlsanity.com/paper/1909.12434/) (2019)
- [On the Parameterization and Initialization of Diagonal State Space Models](https://mlsanity.com/paper/2206.11893/) (2022)
- [Resurrecting Recurrent Neural Networks for Long Sequences](https://mlsanity.com/paper/2303.06349/) (2023)
- [PAWS: Paraphrase Adversaries from Word Scrambling](https://mlsanity.com/paper/1904.01130/) (2019)
- [Diagonal State Spaces are as Effective as Structured State Spaces](https://mlsanity.com/paper/2203.14343/) (2022)
- [Improved Semantic Representations From Tree-Structured Long Short-Term Memory Networks](https://mlsanity.com/paper/1503.00075/) (2015)
- [Theoretical Limitations of Self-Attention in Neural Sequence Models](https://mlsanity.com/paper/1906.06755/) (2019)
- [Stress Test Evaluation for Natural Language Inference](https://mlsanity.com/paper/1806.00692/) (2018)
- [Stochastic Beams and Where to Find Them: The Gumbel-Top-k Trick for Sampling Sequences Without Replacement](https://mlsanity.com/paper/1903.06059/) (2019)
- [Recurrent Memory Transformer](https://mlsanity.com/paper/2207.06881/) (2022)
- [Transformer Quality in Linear Time](https://mlsanity.com/paper/2202.10447/) (2022)
- [Mega: Moving Average Equipped Gated Attention](https://mlsanity.com/paper/2209.10655/) (2022)

## Built on by (most cited first, 5 of 5)

- [A Theory for Length Generalization in Learning to Reason](https://mlsanity.com/paper/2404.00560/) (2024)
- [Compositional simulation-based inference for time series](https://mlsanity.com/paper/2411.02728/) (2024)
- [Investigating Recurrent Transformers with Dynamic Halt](https://mlsanity.com/paper/2402.00976/) (2024)
- [Length Generalization with Log-Depth Recurrent Units](https://mlsanity.com/paper/2605.26035/) (2026)
- [Log-Depth Recurrent Language Modeling](https://mlsanity.com/paper/2609.28212/) (2026)

## Abstract (arXiv)

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 log2 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 logk n. Our best RIR-based model is the first model that demonstrates high (≥ 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: urlhttps://github.com/JRC1995/BeamRecursionFamily/.