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

• URL: http://arxiv.org/abs/2606.16836v1
• Date: Mon, 15 Jun 2026 15:15:25 GMT
• Title: Does Traversal Order Matter? A Systematic Study of Tree Traversal Methods in Transformer Grammars
• Abstract summary: Transformer Grammars (TGs) enhance language modeling incorporating syntactic tree structures.<n>Existing studies rely solely on Depth-First Traversal (DFT) for linearization.<n>We explore Breadth-First Traversal (BFT) and a novel hybrid traversal strategy, Production-Rule Traversal (PRT)<n>We empirically evaluate their performance on language modeling, syntactic generalization and summarization.
• Score: 35.50997062221377
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: 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.

Related papers

• Sneaking Syntax into Transformer Language Models with Tree Regularization [33.74552367356904]
  Introducing syntactic inductive biases could unlock more robust and data-efficient learning in transformer language models.<n>We introduce TreeReg, an auxiliary loss function that converts bracketing decisions from silver parses into a set of differentiableity constraints.<n>TreeReg integrates seamlessly with the standard LM objective, requiring no architectural changes.
  arXiv  Detail & Related papers  (2024-11-28T03:27:48Z)
• A Pure Transformer Pretraining Framework on Text-attributed Graphs [50.833130854272774]
  We introduce a feature-centric pretraining perspective by treating graph structure as a prior. Our framework, Graph Sequence Pretraining with Transformer (GSPT), samples node contexts through random walks. GSPT can be easily adapted to both node classification and link prediction, demonstrating promising empirical success on various datasets.
  arXiv  Detail & Related papers  (2024-06-19T22:30:08Z)
• Learning Syntax Without Planting Trees: Understanding Hierarchical Generalization in Transformers [74.96551626420188]
  Transformers trained on natural language data have been shown to learn its hierarchical structure and generalize to sentences with unseen syntactic structures.<n>We investigate sources of inductive bias in transformer models and their training that could cause such generalization behavior to emerge.
  arXiv  Detail & Related papers  (2024-04-25T07:10:29Z)
• Tree-Planted Transformers: Unidirectional Transformer Language Models with Implicit Syntactic Supervision [4.665860995185884]
  We propose a new method dubbed tree-planting. Instead of explicitly generating syntactic structures, we "plant" trees into attention weights of unidirectional Transformer LMs. Tree-Planted Transformers inherit the training efficiency from SLMs without changing the inference efficiency of their underlying Transformer LMs.
  arXiv  Detail & Related papers  (2024-02-20T03:37:24Z)
• Bidirectional Trained Tree-Structured Decoder for Handwritten Mathematical Expression Recognition [51.66383337087724]
  The Handwritten Mathematical Expression Recognition (HMER) task is a critical branch in the field of OCR. Recent studies have demonstrated that incorporating bidirectional context information significantly improves the performance of HMER models. We propose the Mirror-Flipped Symbol Layout Tree (MF-SLT) and Bidirectional Asynchronous Training (BAT) structure.
  arXiv  Detail & Related papers  (2023-12-31T09:24:21Z)
• Differentiable Tree Operations Promote Compositional Generalization [106.59434079287661]
  Differentiable Tree Machine (DTM) architecture integrates interpreter with external memory and agent that learns to sequentially select tree operations. DTM achieves 100% while existing baselines such as Transformer, Tree Transformer, LSTM, and Tree2Tree LSTM achieve less than 30%.
  arXiv  Detail & Related papers  (2023-06-01T14:46:34Z)
• Transformer Grammars: Augmenting Transformer Language Models with Syntactic Inductive Biases at Scale [31.293175512404172]
  We introduce Transformer Grammars -- a class of Transformer language models that combine expressive power, scalability, and strong performance of Transformers. We find that Transformer Grammars outperform various strong baselines on multiple syntax-sensitive language modeling evaluation metrics.
  arXiv  Detail & Related papers  (2022-03-01T17:22:31Z)
• R2D2: Recursive Transformer based on Differentiable Tree for Interpretable Hierarchical Language Modeling [36.61173494449218]
  This paper proposes a model based on differentiable CKY style binary trees to emulate the composition process. We extend the bidirectional language model pre-training objective to this architecture, attempting to predict each word given its left and right abstraction nodes. To scale up our approach, we also introduce an efficient pruned tree induction algorithm to enable encoding in just a linear number of composition steps.
  arXiv  Detail & Related papers  (2021-07-02T11:00:46Z)
• Syntax-driven Iterative Expansion Language Models for Controllable Text Generation [2.578242050187029]
  We propose a new paradigm for introducing a syntactic inductive bias into neural text generation. Our experiments show that this paradigm is effective at text generation, with quality between LSTMs and Transformers, and comparable diversity.
  arXiv  Detail & Related papers  (2020-04-05T14:29:40Z)
• Tree-structured Attention with Hierarchical Accumulation [103.47584968330325]
  "Hierarchical Accumulation" encodes parse tree structures into self-attention at constant time complexity. Our approach outperforms SOTA methods in four IWSLT translation tasks and the WMT'14 English-German translation task.
  arXiv  Detail & Related papers  (2020-02-19T08:17:00Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.