# Efficient Beam Tree Recursion

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 74 of its 101 references that are in the map.
- First posted on arXiv 20 Jul 2023.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer](https://mlsanity.com/paper/1910.10683/) (2019)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Neural Machine Translation by Jointly Learning to Align and Translate](https://mlsanity.com/paper/1409.0473/) (2014)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [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)
- [A large annotated corpus for learning natural language inference](https://mlsanity.com/paper/1508.05326/) (2015)
- [Self-Attention with Relative Position Representations](https://mlsanity.com/paper/1803.02155/) (2018)
- [Right for the Wrong Reasons: Diagnosing Syntactic Heuristics in Natural Language Inference](https://mlsanity.com/paper/1902.01007/) (2019)
- [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)
- [Universal Transformers](https://mlsanity.com/paper/1807.03819/) (2018)
- [Transformer in Transformer](https://mlsanity.com/paper/2103.00112/) (2021)
- [Deep Equilibrium Models](https://mlsanity.com/paper/1909.01377/) (2019)
- [Adaptive Computation Time for Recurrent Neural Networks](https://mlsanity.com/paper/1603.08983/) (2016)
- [Learning the Difference that Makes a Difference with Counterfactually-Augmented Data](https://mlsanity.com/paper/1909.12434/) (2019)
- [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)
- [Neural Networks and the Chomsky Hierarchy](https://mlsanity.com/paper/2207.02098/) (2022)
- [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)
- [Transformer Quality in Linear Time](https://mlsanity.com/paper/2202.10447/) (2022)
- [PonderNet: Learning to Ponder](https://mlsanity.com/paper/2107.05407/) (2021)
- [Breaking NLI Systems with Sentences that Require Simple Lexical Inferences](https://mlsanity.com/paper/1805.02266/) (2018)
- [ListOps: A Diagnostic Dataset for Latent Tree Learning](https://mlsanity.com/paper/1804.06028/) (2018)

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

- [Augmenting Transformers with Recursively Composed Multi-grained Representations](https://mlsanity.com/paper/2309.16319/) (2023)
- [Recursion in Recursion: Two-Level Nested Recursion for Length Generalization with Scalability](https://mlsanity.com/paper/2311.04449/) (2023)
- [Investigating Recurrent Transformers with Dynamic Halt](https://mlsanity.com/paper/2402.00976/) (2024)
- [Universal Transformers for Circuit Computations: Perfect Length Generalization in Tiny Transformers](https://mlsanity.com/paper/2608.31067/) (2026)

## Abstract (arXiv)

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