Tree Linearization for Neural Sequence Models

285 concepts199 papers3 proposals

The real world is full of hierarchical data. Syntactic parse trees map the structure of human language; Abstract Syntax Trees (ASTs) define the logic of source code; and nested JSON, HTML, or database query plans dictate how software systems communicate.

Yet, the most powerful deep learning architectures we have—such as Transformers and LSTMs—are fundamentally optimized for one-dimensional sequences. To process trees with these models, researchers face a choice: design specialized, pointer-heavy tree-structured neural networks, or find a way to flatten the hierarchy into a sequence.

Tree linearization is the practice of systematically converting a hierarchical tree structure into a flat sequence of tokens without losing its underlying topology. By mapping trees to strings, we can leverage general-purpose sequence-to-sequence architectures to solve complex structured prediction tasks.


The Mechanics of Flattening a Tree

To understand why tree linearization works, we must look at how a multi-dimensional branching structure can be compressed into a single dimension. The most common approach relies on tree traversals combined with structural markers.

Depth-First Search and Bracketed Notation

The foundational approach to linearization uses a Depth-First Search (DFS) traversal to visit nodes sequentially, using parentheses or brackets to explicitly denote when a sub-tree opens and closes.

In their seminal paper Grammar as a Foreign Language, Vinyals et al. demonstrated that a standard sequence-to-sequence model with attention could perform syntactic constituency parsing with remarkable accuracy simply by "translating" a sentence into a linearized, bracketed parse tree:

(S (NP John) (VP (V loves) (NP Mary)))

This simple string representation allows the attention mechanism to learn nested dependencies and hierarchical relationships purely through sequential token distances.

Specialized Structural Tokens

When dealing with data beyond natural language syntax—such as tables or user interfaces—standard brackets are often replaced with domain-specific boundary tokens. For example, in Structure-Aware Pre-Training for Table-to-Text Generation, Xing et al. linearized tabular data using specialized tokens that explicitly mark cell, row, and table boundaries. Similarly, in FormLM, Zhou et al. used structural markers to preserve the relational context of nested online forms.

Lossless Graph Encodings

Beyond standard traversals, graph theory offers highly compressed, bijective (lossless) mappings between trees and sequences. Jinpa et al. explored this in Code Representation Learning Using Prüfer Sequences, demonstrating that iteratively removing the smallest labeled leaf node and recording its parent creates a highly concise linear format that optimizes how sequence models process code structure.


Why Traversal Order Matters

The specific sequence order chosen for linearization fundamentally changes what the neural network "sees" at each step of generation or encoding. Different traversal strategies expose different structural contexts to the model's attention mechanism.

Top-Down (Pre-Order) Linearization

A pre-order traversal visits the parent node before its children. In sequence generation, this gives the model global structural context and lookahead information. As Liu argues in Improving Sequence-to-Sequence Constituency Parsing, top-down linearization allows a model to make high-level decisions about constituent boundaries early in the generation process, providing superior structural guidance compared to bottom-up approaches.

In code intelligence, pre-order DFS ensures that grammatical node types appear immediately before their associated values. As shown by Zhao et al. in Code Prediction by Feeding Trees to Transformers, this ordering provides explicit structural context right before a token is predicted, making it highly effective for autocompletion.

In-Order Linearization

An in-order traversal visits the parent node after its first child but before the remaining children. In Enriched In-Order Linearization for Faster Sequence-to-Sequence Constituent Parsing, Fernández-González et al. demonstrated that this strategy balances local and global context. By processing the first child first, the model gains partial structural information that helps it contextualize and accurately predict the parent label before committing to the rest of the branch.

Breadth-First Search (BFS)

While DFS prioritizes deep ancestral relationships, Breadth-First Search (BFS) prioritizes horizontal, sibling-level relationships. This is crucial for layout-driven data. In Screen2Words, Wang et al. used BFS linearization to flatten mobile UI hierarchies, allowing the model to learn dependencies across an entire visual layout structure.

To get the best of both worlds, some frameworks employ multi-traversal linearization. For instance, Xie et al. introduced a mutual learning framework in Improving Tree-Structured Decoder Training for Code Generation via Mutual Learning that forces a pre-order decoder and a breadth-first decoder to teach each other, capturing both vertical and horizontal structural dependencies simultaneously.


Applications Across Domains

By treating structured prediction as a sequence-to-sequence translation task, tree linearization has unified several disparate fields under standard language modeling objectives.


The Core Limitation: Do Models Truly Understand Recursion?

While tree linearization is highly effective in practice, it raises a fundamental theoretical question: Does a sequence model processing a flattened tree actually learn the underlying hierarchical rules, or is it just memorizing surface-level string patterns?

In Transformer-Based Models Are Not Yet Perfect At Learning to Emulate Structural Recursion, Zhang et al. investigated this exact boundary. They discovered that when recursive data structures are represented as linear sequences using inductive constructor tokens, Transformers frequently adopt non-recursive "shortcut" algorithms. While these shortcuts work perfectly on standard test sets, they fail on edge cases and struggle to generalize when evaluated on deeper, more highly nested structures than those seen during training.

Thus, while tree linearization serves as an incredibly powerful bridge—allowing us to deploy highly optimized sequence architectures to handle complex hierarchical data—the responsibility for maintaining structural integrity still largely rests on the cleverness of the linearization format and the constraints applied during decoding.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 197 papers
  2. Version 1 · 2026-10-04 · 244 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_tree_linearization_a895b946,
  title = {tree linearization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/tree-linearization/rdr_a895b946e47b4d86ac0734e230df1ee8},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 2, frozen text):

@misc{lacuna_tree_linearization_a895b946_v2,
  title = {tree linearization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/tree-linearization/rdr_a895b946e47b4d86ac0734e230df1ee8/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake