# Trees in transformers: a theoretical analysis of the Transformer's ability to represent trees

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 28 references that are in the map.
- First posted on arXiv 16 Dec 2021.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Layer Normalization](https://mlsanity.com/paper/1607.06450/) (2016)
- [Big Bird: Transformers for Longer Sequences](https://mlsanity.com/paper/2007.14062/) (2020)
- [Are Transformers universal approximators of sequence-to-sequence functions?](https://mlsanity.com/paper/1912.10077/) (2019)
- [OpenNMT: Open-source Toolkit for Neural Machine Translation](https://mlsanity.com/paper/1709.03815/) (2017)
- [Open Sesame: Getting Inside BERT's Linguistic Knowledge](https://mlsanity.com/paper/1906.01698/) (2019)
- [Tree Transformer: Integrating Tree Structures into Self-Attention](https://mlsanity.com/paper/1909.06639/) (2019)
- [Provable Limitations of Acquiring Meaning from Ungrounded Form: What Will Future Language Models Understand?](https://mlsanity.com/paper/2104.10809/) (2021)
- [Self-Attention with Structural Position Representations](https://mlsanity.com/paper/1909.00383/) (2019)
- [Tree-Transformer: A Transformer-Based Method for Correction of Tree-Structured Data](https://mlsanity.com/paper/1908.00449/) (2019)
- [Top-down Tree Long Short-Term Memory Networks](https://mlsanity.com/paper/1511.00060/) (2015)

## Abstract (arXiv)

Transformer networks are the de facto standard architecture in natural language processing. To date, there are no theoretical analyses of the Transformer's ability to capture tree structures. We focus on the ability of Transformer networks to learn tree structures that are important for tree transduction problems. We first analyze the theoretical capability of the standard Transformer architecture to learn tree structures given enumeration of all possible tree backbones, which we define as trees without labels. We then prove that two linear layers with ReLU activation function can recover any tree backbone from any two nonzero, linearly independent starting backbones. This implies that a Transformer can learn tree structures well in theory. We conduct experiments with synthetic data and find that the standard Transformer achieves similar accuracy compared to a Transformer where tree position information is explicitly encoded, albeit with slower convergence. This confirms empirically that Transformers can learn tree structures.