# Characterizing Intrinsic Compositionality in Transformers with Tree Projections

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

## Key facts

- Cited by 41 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 32 references that are in the map.
- First posted on arXiv 2 Nov 2022.

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

- [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)
- [Domain-Adversarial Training of Neural Networks](https://mlsanity.com/paper/1505.07818/) (2015)
- [Beyond Accuracy: Behavioral Testing of NLP models with CheckList](https://mlsanity.com/paper/2005.04118/) (2020)
- [Domain Generalization via Invariant Feature Representation](https://mlsanity.com/paper/1301.2115/) (2013)
- [Neural Module Networks](https://mlsanity.com/paper/1511.02799/) (2015)
- [Assessing the Ability of LSTMs to Learn Syntax-Sensitive Dependencies](https://mlsanity.com/paper/1611.01368/) (2016)
- [Improved Semantic Representations From Tree-Structured Long Short-Term Memory Networks](https://mlsanity.com/paper/1503.00075/) (2015)
- [COGS: A Compositional Generalization Challenge Based on Semantic Interpretation](https://mlsanity.com/paper/2010.05465/) (2020)
- [Targeted Syntactic Evaluation of Language Models](https://mlsanity.com/paper/1808.09031/) (2018)
- [Improving Text-to-SQL Evaluation Methodology](https://mlsanity.com/paper/1806.09029/) (2018)
- [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)
- [Measuring Compositionality in Representation Learning](https://mlsanity.com/paper/1902.07181/) (2019)
- [A Minimal Span-Based Neural Constituency Parser](https://mlsanity.com/paper/1705.03919/) (2017)
- [Finding Syntax in Human Encephalography with Beam Search](https://mlsanity.com/paper/1806.04127/) (2018)
- [Assessing Phrasal Representation and Composition in Transformers](https://mlsanity.com/paper/2010.03763/) (2020)
- [RNNs Implicitly Implement Tensor Product Representations](https://mlsanity.com/paper/1812.08718/) (2018)
- [Revisiting the Compositional Generalization Abilities of Neural Sequence Models](https://mlsanity.com/paper/2203.07402/) (2022)

## Built on by (most cited first, 30 of 41)

- [Sudden Drops in the Loss: Syntax Acquisition, Phase Transitions, and Simplicity Bias in MLMs](https://mlsanity.com/paper/2309.07311/) (2023)
- [The Truth is in There: Improving Reasoning in Language Models with Layer-Selective Rank Reduction](https://mlsanity.com/paper/2312.13558/) (2023)
- [Interpretability at Scale: Identifying Causal Mechanisms in Alpaca](https://mlsanity.com/paper/2305.08809/) (2023)
- [Physics of Language Models: Part 1, Learning Hierarchical Language Structures](https://mlsanity.com/paper/2305.13673/) (2023)
- [Grokking of Hierarchical Structure in Vanilla Transformers](https://mlsanity.com/paper/2305.18741/) (2023)
- [What does the Knowledge Neuron Thesis Have to do with Knowledge?](https://mlsanity.com/paper/2405.02421/) (2024)
- [The Impact of Depth on Compositional Generalization in Transformer Language Models](https://mlsanity.com/paper/2310.19956/) (2023)
- [Injecting structural hints: Using language models to study inductive biases in language learning](https://mlsanity.com/paper/2304.13060/) (2023)
- [Coarse-to-Fine Contrastive Learning in Image-Text-Graph Space for Improved Vision-Language Compositionality](https://mlsanity.com/paper/2305.13812/) (2023)
- [Learning Syntax Without Planting Trees: Understanding Hierarchical Generalization in Transformers](https://mlsanity.com/paper/2404.16367/) (2024)
- [Language Models as Models of Language](https://mlsanity.com/paper/2408.07144/) (2024)
- [How to Plant Trees in Language Models: Data and Architectural Effects on the Emergence of Syntactic Inductive Biases](https://mlsanity.com/paper/2305.19905/) (2023)
- [Do Language Models Exhibit Human-like Structural Priming Effects?](https://mlsanity.com/paper/2406.04847/) (2024)
- [Pushdown Layers: Encoding Recursive Structure in Transformer Language Models](https://mlsanity.com/paper/2310.19089/) (2023)
- [Self-attention Networks Localize When QK-eigenspectrum Concentrates](https://mlsanity.com/paper/2402.02098/) (2024)
- [Large Linguistic Models: Investigating LLMs' metalinguistic abilities](https://mlsanity.com/paper/2305.00948/) (2023)
- [Geometric Signatures of Compositionality Across a Language Model's Lifetime](https://mlsanity.com/paper/2410.01444/) (2024)
- [Position: A Theory of Deep Learning Must Include Compositional Sparsity](https://mlsanity.com/paper/2507.02550/) (2025)
- [Sometimes I am a Tree: Data Drives Unstable Hierarchical Generalization](https://mlsanity.com/paper/2412.04619/) (2024)
- [Mechanisms vs. Outcomes: Probing for Syntax Fails to Explain Performance on Targeted Syntactic Evaluations](https://mlsanity.com/paper/2506.16678/) (2025)
- [Analyzing the Inner Workings of Transformers in Compositional Generalization](https://mlsanity.com/paper/2502.15277/) (2025)
- [Data Factors for Better Compositional Generalization](https://mlsanity.com/paper/2311.04420/) (2023)
- [Compositional Generalization Across Distributional Shifts with Sparse Tree Operations](https://mlsanity.com/paper/2412.14076/) (2024)
- [Approximating CKY with Transformers](https://mlsanity.com/paper/2305.02386/) (2023)
- [Modularity in Deep Learning: A Survey](https://mlsanity.com/paper/2310.01154/) (2023)
- [Emergence and Function of Abstract Representations in Self-Supervised Transformers](https://mlsanity.com/paper/2312.05361/) (2023)
- [Sneaking Syntax into Transformer Language Models with Tree Regularization](https://mlsanity.com/paper/2411.18885/) (2024)
- [StrAE: Autoencoding for Pre-Trained Embeddings using Explicit Structure](https://mlsanity.com/paper/2305.05588/) (2023)
- [Structure Before Collapse: Transient semantic geometry in next-token prediction](https://mlsanity.com/paper/2606.26749/) (2026)
- [Syntax-guided Neural Module Distillation to Probe Compositionality in Sentence Embeddings](https://mlsanity.com/paper/2301.08998/) (2023)

## Abstract (arXiv)

When trained on language data, do transformers learn some arbitrary computation that utilizes the full capacity of the architecture or do they learn a simpler, tree-like computation, hypothesized to underlie compositional meaning systems like human languages? There is an apparent tension between compositional accounts of human language understanding, which are based on a restricted bottom-up computational process, and the enormous success of neural models like transformers, which can route information arbitrarily between different parts of their input. One possibility is that these models, while extremely flexible in principle, in practice learn to interpret language hierarchically, ultimately building sentence representations close to those predictable by a bottom-up, tree-structured model. To evaluate this possibility, we describe an unsupervised and parameter-free method to functionally project the behavior of any transformer into the space of tree-structured networks. Given an input sentence, we produce a binary tree that approximates the transformer's representation-building process and a score that captures how "tree-like" the transformer's behavior is on the input. While calculation of this score does not require training any additional models, it provably upper-bounds the fit between a transformer and any tree-structured approximation. Using this method, we show that transformers for three different tasks become more tree-like over the course of training, in some cases unsupervisedly recovering the same trees as supervised parsers. These trees, in turn, are predictive of model behavior, with more tree-like models generalizing better on tests of compositional generalization.