# Does Traversal Order Matter? A Systematic Study of Tree Traversal Methods in Transformer Grammars

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 19 references that are in the map.
- First posted on arXiv 15 Jun 2026.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [RoFormer: Enhanced Transformer with Rotary Position Embedding](https://mlsanity.com/paper/2104.09864/) (2021)
- [GLU Variants Improve Transformer](https://mlsanity.com/paper/2002.05202/) (2020)
- [Root Mean Square Layer Normalization](https://mlsanity.com/paper/1910.07467/) (2019)
- [Don't Give Me the Details, Just the Summary! Topic-Aware Convolutional Neural Networks for Extreme Summarization](https://mlsanity.com/paper/1808.08745/) (2018)
- [BLiMP: The Benchmark of Linguistic Minimal Pairs for English](https://mlsanity.com/paper/1912.00582/) (2019)
- [A Systematic Assessment of Syntactic Generalization in Neural Language Models](https://mlsanity.com/paper/2005.03692/) (2020)
- [Recurrent Neural Network Grammars](https://mlsanity.com/paper/1602.07776/) (2016)
- [Fast and Accurate Neural CRF Constituency Parsing](https://mlsanity.com/paper/2008.03736/) (2020)
- [Transformer Grammars: Augmenting Transformer Language Models with Syntactic Inductive Biases at Scale](https://mlsanity.com/paper/2203.00633/) (2022)
- [Effective Inference for Generative Neural Parsing](https://mlsanity.com/paper/1707.08976/) (2017)
- [Structural Guidance for Transformer Language Models](https://mlsanity.com/paper/2108.00104/) (2021)
- [In-Order Transition-based Constituent Parsing](https://mlsanity.com/paper/1707.05000/) (2017)
- [Generative Pretrained Structured Transformers: Unsupervised Syntactic Language Models at Scale](https://mlsanity.com/paper/2403.08293/) (2024)
- [Dependency Transformer Grammars: Integrating Dependency Structures into Transformer Language Models](https://mlsanity.com/paper/2407.17406/) (2024)

## Abstract (arXiv)

Transformer Grammars (TGs) enhance language modeling by incorporating syntactic tree structures. Despite the potentially significant impact on model performance of how syntactic trees are linearized in TGs, existing studies rely solely on Depth-First Traversal (DFT) for linearization. In this paper, we expand the traversal design space by exploring Breadth-First Traversal (BFT) and a novel hybrid traversal strategy, Production-Rule Traversal (PRT), which combines the structural lookahead of BFT with the early lexical generation of DFT. We integrate these traversal methods with varying tree configurations and masking strategies, and empirically evaluate their performance on language modeling, syntactic generalization and summarization. We reveal the inherent trade-offs between nested composition and global lookahead, providing actionable recommendations for designing task-aware Transformer Grammars.