# Beam Tree Recursive Cells

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 54 of its 89 references that are in the map.
- First posted on arXiv 31 May 2023.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [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)
- [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)
- [The Concrete Distribution: A Continuous Relaxation of Discrete Random Variables](https://mlsanity.com/paper/1611.00712/) (2016)
- [Long Range Arena: A Benchmark for Efficient Transformers](https://mlsanity.com/paper/2011.04006/) (2020)
- [Learning the Difference that Makes a Difference with Counterfactually-Augmented Data](https://mlsanity.com/paper/1909.12434/) (2019)
- [Improved Semantic Representations From Tree-Structured Long Short-Term Memory Networks](https://mlsanity.com/paper/1503.00075/) (2015)
- [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)
- [Fast Differentiable Sorting and Ranking](https://mlsanity.com/paper/2002.08871/) (2020)
- [ListOps: A Diagnostic Dataset for Latent Tree Learning](https://mlsanity.com/paper/1804.06028/) (2018)
- [Differentiable Ranks and Sorting using Optimal Transport](https://mlsanity.com/paper/1905.11885/) (2019)
- [Stochastic Optimization of Sorting Networks via Continuous Relaxations](https://mlsanity.com/paper/1903.08850/) (2019)
- [Ordered Neurons: Integrating Tree Structures into Recurrent Neural Networks](https://mlsanity.com/paper/1810.09536/) (2018)
- [Neural Nearest Neighbors Networks](https://mlsanity.com/paper/1810.12575/) (2018)
- [Span-based Semantic Parsing for Compositional Generalization](https://mlsanity.com/paper/2009.06040/) (2020)
- [Tree Transformer: Integrating Tree Structures into Self-Attention](https://mlsanity.com/paper/1909.06639/) (2019)
- [The Neural Data Router: Adaptive Control Flow in Transformers Improves Systematic Generalization](https://mlsanity.com/paper/2110.07732/) (2021)
- [Unsupervised Latent Tree Induction with Deep Inside-Outside Recursive Autoencoders](https://mlsanity.com/paper/1904.02142/) (2019)
- [Learning to Transduce with Unbounded Memory](https://mlsanity.com/paper/1506.02516/) (2015)
- [Compositional Generalization by Learning Analytical Expressions](https://mlsanity.com/paper/2006.10627/) (2020)
- [Learning to Compose Task-Specific Tree Structures](https://mlsanity.com/paper/1707.02786/) (2017)
- [The Importance of Being Recurrent for Modeling Hierarchical Structure](https://mlsanity.com/paper/1803.03585/) (2018)
- [A Fast Unified Model for Parsing and Sentence Understanding](https://mlsanity.com/paper/1603.06021/) (2016)
- [StructFormer: Joint Unsupervised Induction of Dependency and Constituency Structure from Masked Language Modeling](https://mlsanity.com/paper/2012.00857/) (2020)
- [Differentiable Sorting Networks for Scalable Sorting and Ranking Supervision](https://mlsanity.com/paper/2105.04019/) (2021)
- [Learning Algebraic Recombination for Compositional Generalization](https://mlsanity.com/paper/2107.06516/) (2021)

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

- [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)
- [Efficient Beam Tree Recursion](https://mlsanity.com/paper/2307.10779/) (2023)
- [Banyan: Improved Representation Learning with Explicit Structure](https://mlsanity.com/paper/2407.17771/) (2024)
- [On the Design Space Between Transformers and Recursive Neural Nets](https://mlsanity.com/paper/2409.01531/) (2024)

## Abstract (arXiv)

We propose Beam Tree Recursive Cell (BT-Cell) - a backpropagation-friendly framework to extend Recursive Neural Networks (RvNNs) with beam search for latent structure induction. We further extend this framework by proposing a relaxation of the hard top-k operators in beam search for better propagation of gradient signals. We evaluate our proposed models in different out-of-distribution splits in both synthetic and realistic data. Our experiments show that BTCell achieves near-perfect performance on several challenging structure-sensitive synthetic tasks like ListOps and logical inference while maintaining comparable performance in realistic data against other RvNN-based models. Additionally, we identify a previously unknown failure case for neural models in generalization to unseen number of arguments in ListOps. The code is available at: https://github.com/JRC1995/BeamTreeRecursiveCells.