# Fast-R2D2: A Pretrained Recursive Neural Network based on Pruned CKY for Grammar Induction and Text Representation

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 47 references that are in the map.
- First posted on arXiv 1 Mar 2022.

## Builds on (most cited first, 21 of 21)

- [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)
- [GLUE: A Multi-Task Benchmark and Analysis Platform for Natural Language Understanding](https://mlsanity.com/paper/1804.07461/) (2018)
- [Pointer Sentinel Mixture Models](https://mlsanity.com/paper/1609.07843/) (2016)
- [Categorical Reparameterization with Gumbel-Softmax](https://mlsanity.com/paper/1611.01144/) (2016)
- [Don't Stop Pretraining: Adapt Language Models to Domains and Tasks](https://mlsanity.com/paper/2004.10964/) (2020)
- [Google's Neural Machine Translation System: Bridging the Gap between Human and Machine Translation](https://mlsanity.com/paper/1609.08144/) (2016)
- [A* Sampling](https://mlsanity.com/paper/1411.0030/) (2014)
- [Recurrent Neural Network Grammars](https://mlsanity.com/paper/1602.07776/) (2016)
- [Ordered Neurons: Integrating Tree Structures into Recurrent Neural Networks](https://mlsanity.com/paper/1810.09536/) (2018)
- [Compound Probabilistic Context-Free Grammars for Grammar Induction](https://mlsanity.com/paper/1906.10225/) (2019)
- [Unsupervised Latent Tree Induction with Deep Inside-Outside Recursive Autoencoders](https://mlsanity.com/paper/1904.02142/) (2019)
- [Learning to Compose Task-Specific Tree Structures](https://mlsanity.com/paper/1707.02786/) (2017)
- [Unsupervised Recurrent Neural Network Grammars](https://mlsanity.com/paper/1904.03746/) (2019)
- [StructFormer: Joint Unsupervised Induction of Dependency and Constituency Structure from Masked Language Modeling](https://mlsanity.com/paper/2012.00857/) (2020)
- [Straight to the Tree: Constituency Parsing with Neural Syntactic Distance](https://mlsanity.com/paper/1806.04168/) (2018)
- [Learning to Compose Words into Sentences with Reinforcement Learning](https://mlsanity.com/paper/1611.09100/) (2016)
- [Jointly Learning Sentence Embeddings and Syntax with Unsupervised Tree-LSTMs](https://mlsanity.com/paper/1705.09189/) (2017)
- [Ordered Memory](https://mlsanity.com/paper/1910.13466/) (2019)
- [R2D2: Recursive Transformer based on Differentiable Tree for Interpretable Hierarchical Language Modeling](https://mlsanity.com/paper/2107.00967/) (2021)
- [Modeling Hierarchical Structures with Continuous Recursive Neural Networks](https://mlsanity.com/paper/2106.06038/) (2021)

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

- [Generative Pretrained Structured Transformers: Unsupervised Syntactic Language Models at Scale](https://mlsanity.com/paper/2403.08293/) (2024)
- [Efficient Length-Generalizable Attention via Causal Retrieval for Long-Context Language Modeling](https://mlsanity.com/paper/2410.01651/) (2024)
- [Beam Tree Recursive Cells](https://mlsanity.com/paper/2305.19999/) (2023)
- [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)
- [A Multi-Grained Self-Interpretable Symbolic-Neural Model For Single/Multi-Labeled Text Classification](https://mlsanity.com/paper/2303.02860/) (2023)
- [Efficient Beam Tree Recursion](https://mlsanity.com/paper/2307.10779/) (2023)
- [Simple Hardware-Efficient PCFGs with Independent Left and Right Productions](https://mlsanity.com/paper/2310.14997/) (2023)
- [Banyan: Improved Representation Learning with Explicit Structure](https://mlsanity.com/paper/2407.17771/) (2024)
- [Unsupervised Morphological Tree Tokenizer](https://mlsanity.com/paper/2406.15245/) (2024)
- [Grammar Induction from Visual, Speech and Text](https://mlsanity.com/paper/2410.03739/) (2024)
- [On Eliciting Syntax from Language Models via Hashing](https://mlsanity.com/paper/2410.04074/) (2024)
- [Understanding Syntactic Generalization in Structure-inducing Language Models](https://mlsanity.com/paper/2508.07969/) (2025)
- [Holographic Neural PCFG for Unsupervised Parsing](https://mlsanity.com/paper/2607.08063/) (2026)
- [Know Yourself and Know Your Neighbour: A Syntactically Informed Self-Supervised Compositional Sentence Representation Learning Framework using a Recursive Hypernetwork](https://mlsanity.com/paper/2610.16547/) (2026)

## Abstract (arXiv)

Recently CKY-based models show great potential in unsupervised grammar induction thanks to their human-like encoding paradigm, which runs recursively and hierarchically, but requires O(n3) time-complexity. Recursive Transformer based on Differentiable Trees (R2D2) makes it possible to scale to large language model pre-training even with complex tree encoder by introducing a heuristic pruning method. However, the rule-based pruning approach suffers from local optimum and slow inference issues. In this paper, we fix those issues in a unified method. We propose to use a top-down parser as a model-based pruning method, which also enables parallel encoding during inference. Typically, our parser casts parsing as a split point scoring task, which first scores all split points for a given sentence, and then recursively splits a span into two by picking a split point with the highest score in the current span. The reverse order of the splits is considered as the order of pruning in R2D2 encoder. Beside the bi-directional language model loss, we also optimize the parser by minimizing the KL distance between tree probabilities from parser and R2D2. Our experiments show that our Fast-R2D2 improves performance significantly in grammar induction and achieves competitive results in downstream classification tasks.