Modern sequence-to-sequence architectures, from recurrent neural networks to Transformers, are designed to ingest flat arrays of tokens. However, much of the data we want these models to understand—such as linguistic parse trees, source code Abstract Syntax Trees (ASTs), mathematical operational trees, and tables—is inherently hierarchical or graph-structured.
To bridge this gap, researchers frequently turn to linearization: traversing a graph or tree structure and flattening it into a single string. While this allows structured data to fit into standard sequence pipelines, it introduces a severe, often hidden tax: sequence length expansion. Trying to expose structural context explicitly to a model can inadvertently degrade its performance and scalability by inflating the token count.
The Mechanics of Structural Token Overhead
Why does flattening a graph cause a sequence to explode in length? A naive serialization cannot simply list the nodes of a tree; it must also encode the edges and hierarchical boundaries to remain lossless. This requires injecting explicit structural markers, such as brackets, tags, or backtracking tokens.
Tree Structure:
A
/ \
B C
Naive Linearization: A B C (Loses topology!)
Lossless Linearization: (A (B) (C)) or A B [BACKTRACK] C
As these structural markers accumulate, the sequence length grows drastically relative to the raw underlying text:
- Linguistic Syntax: In neural machine translation, Roee Aharoni et al. demonstrated in Towards String-To-Tree Neural Machine Translation that converting hierarchical constituency trees into flat sequences can easily double the total token count per sentence. Similarly, Wolf Nuyts et al. note in Explicitly Representing Syntax Improves Sentence-to-layout Prediction of Unexpected Situations that adding explicit syntax tags significantly inflates the token count, driving up latency during the encoding phase.
- Source Code ASTs: Code intelligence models face a similar bottleneck. Daya Guo et al. found in UniXcoder: Unified Cross-Modal Pre-training for Code Representation that incorporating AST metadata into Transformer inputs expands the sequence length by roughly 70%.
- Other Domains: This overhead appears whenever structure is flattened. Alexander Scarlatos et al. observe it when linearizing mathematical operation trees in Tree-Based Representation and Generation of Natural and Mathematical Language. In document processing, Jan Buchmann et al. show in Document Structure in Long Document Transformers that prepending special tokens to represent document hierarchy exacerbates computational bottlenecks in long-context models. For tabular data, Naihao Deng et al. demonstrate in Tables as Texts or Images: Evaluating the Table Reasoning Ability of LLMs and MLLMs that linearizing large tables into text strings creates massive sequences that overwhelm a model's ability to retrieve or reason over specific data points.
The Dual Costs: Memory and Structural Dilution
This sequence expansion harms models in two distinct ways: it creates a severe hardware bottleneck, and it dilutes the very structural relationships it was meant to highlight.
1. Computational and Memory Bottlenecks
Because the self-attention mechanism in Transformers scales quadratically with sequence length, a 70% to 100% increase in token count translates to a massive spike in computational complexity. As Danielle Saunders et al. point out in Multi-representation ensembles and delayed SGD updates improve syntax-based NMT, these extended sequences frequently exceed the memory capacity of standard hardware, requiring specialized training adjustments like delayed SGD updates. Furthermore, Chunpeng Ma et al. note in Forest-Based Neural Machine Translation that this expansion causes a substantial drag on decoding speeds during inference, making deployment impractical.
2. Structural Dilution and Long-Range Dependencies
Ironically, flattening a graph to expose its structure often makes that structure harder for the model to parse. In a tree or graph, a parent node and its child are separated by a single hop. However, when linearized, an entire subtree may be inserted between them.
As Ganbin Zhou et al. explain in Tree-Structured Neural Machine for Linguistics-Aware Sentence Generation, the path distance between structurally related elements scales linearly with the sequence length $N$ in a flat string. This long-distance separation strains the model's memory.
For recurrent networks, this increases the risk of vanishing gradients; for Transformers, it increases the risk of attention failures. As argued by Gabriel Stanovsky et al. in Semantics as a Foreign Language and Linfeng Song et al. in A Graph-to-Sequence Model for AMR-to-Text Generation, as the graph grows, semantically connected components are pushed so far apart in the flattened string that standard sequence-to-sequence models struggle to maintain coherence.
Mitigating the Overhead
To resolve this tension, recent research focuses on capturing structural relationships without paying the price of sequence expansion. The field has split into two primary strategies: injecting structure directly into the attention matrix, or abandoning sequence decoders entirely.
Structural Attention Masking
Instead of modifying the input token sequence by adding brackets or tags, we can modify the model's internal attention mechanism to respect the graph's topology.
Colin McDonald et al. demonstrate the value of this approach in Syntax-Based Attention Masking for Neural Machine Translation. They show that explicitly adding structural tokens can actually degrade model performance—especially in low-resource environments—because the token overhead outweighs the structural benefits. By using learnable attention masks based on syntax trees instead, the model learns linguistic relationships natively without expanding the sequence length.
Naive Linearization (High Overhead):
Tokens: [ Root ] [ Node1 ] [ Parent ] [ Child ] ... (Sequence length explodes)
Structural Attention Masking (Zero Overhead):
Tokens: [ Standard Text Tokens Only ]
Matrix: Attention bias applied directly to pairs based on graph distance
Taking this a step further, Ze Tang et al. introduced the AST-Transformer: Encoding Abstract Syntax Trees Efficiently for Code Summarization. Instead of relying on complex, high-overhead flattening traversals that bottleneck the preprocessing pipeline, they replace standard all-to-all attention with a "Tree-Structure Attention" mechanism. By restricting attention strictly to parent-child and sibling nodes within the AST, they bypass sequence expansion entirely and reduce computational complexity by 90–95%.
Native Graph and Tree Architectures
The alternative strategy is to replace the sequential encoder or decoder with a structure-aware module. On the generation side, the X2TREE framework introduced by Ganbin Zhou et al. generates sentences by predicting dependency parse trees in a top-down, hierarchical fashion rather than word-by-word. This eliminates the linear path-distance penalty entirely. On the encoding side, the graph-to-sequence model developed by Linfeng Song et al. utilizes a graph-state LSTM to encode semantic structures directly from their native geometry, preserving critical structural relationships without ever flattening them into strings.
Key Foundational Work
Towards String-To-Tree Neural Machine Translation (2017) — contributed 2 concept elements to this direction.
Forest-Based Neural Machine Translation (2018) — contributed 2 concept elements to this direction.
Semantics as a Foreign Language (2018) — contributed 2 concept elements to this direction.