Standard Transformer architectures treat data as a flat sequence, using linear positional encodings (1, 2, 3...) to represent the order of tokens. However, many complex data types—such as source code, mathematical formulas, taxonomies, and dialogue threads—are inherently hierarchical. In these domains, the "distance" between two elements is better defined by their structural relationship in a tree than by their surface-level proximity in a string.
To address this, researchers have developed hierarchical positional encodings that inject the recursive topology of trees directly into the model's coordinate system.
Encoding the Path from Root to Leaf
The most direct way to represent a node's position in a tree is to describe the unique trajectory required to reach it from the root. Instead of a single integer, each node is assigned a "path-based" encoding that acts as a structural address.
Jang et al. argue that these path-based encodings are essential for Transformers to process hierarchical sequences; without them, models struggle to maintain the recursive context necessary for accurate structural reconstruction. For example, in mathematical expressions, Scarlatos et al. demonstrate that deriving embeddings from the root-to-node path allows a model to explicitly capture the depth and branching context of a symbol, which is critical for maintaining logical consistency in nested formulas.
Different methods exist to compress these paths into vectors:
- Recurrent Encoding: Su et al. use a Gated Recurrent Unit (GRU) to process the sequence of nodes from the root to a specific part, ensuring structural consistency in generated 3D objects.
- Prefix Trees: Huang et al. reparameterize token embeddings by organizing a vocabulary into a prefix tree, where a token's final vector is the cumulative sum of trainable vectors along its path from the root.
- Deterministic Addressing: Prange et al. use a deterministic binary tree addressing scheme to generate structured labels without needing recursive architectures.
Multi-Dimensional Structural Coordinates
Another approach moves away from paths and toward multi-dimensional coordinate systems that describe a node's local and global environment. This typically involves decomposing position into three distinct facets: depth, parent identity, and sibling order.
Juncai Guo proposes a "triplet position" encoding for Abstract Syntax Trees (ASTs) that records a node's vertical depth, its parent's horizontal position, and its own sibling index. This unique identifier prevents the loss of hierarchical information that occurs when trees are flattened. Similarly, Li et al. introduce a "2D recursive positional encoding" that combines global absolute positions with local relative relationships. They emphasize that incorporating the total number of siblings is vital for semantic context, as it allows the model to distinguish between different structural roles, such as the first versus the last element in a list.
In the context of social media, Xu et al. use structural embeddings to map news propagation trees, distinguishing between the depth of a retweet chain and the breadth of initial replies. Even in generative tasks, the authors of HoneyCode show that including a node's depth as a feature allows models to follow structural conventions, such as placing license files only at the root of a directory hierarchy.
Structural Inductive Biases and Generalization
Hierarchical encodings do more than just improve accuracy; they provide an inductive bias that helps models generalize to unseen or longer structures.
For source code, Zhang et al. developed HiRoPE, which encodes positions as multi-level vectors (e.g., function-level vs. token-level). This allows Large Language Models to process sequences exponentially longer than their training limit by mapping distances to a structured coordinate system rather than a flat, ever-increasing index. In linguistics, Kuncoro et al. show that "Transformer Grammars" using relative structural distances outperform models 1000x larger by prioritizing hierarchical proximity over surface-level token distance.
This structural awareness is also crucial for arithmetic. Cho et al. found that decomposing encodings to track both digit significance and operand identity simultaneously allows Transformers to generalize to much longer math problems than those seen during training. By treating the input as a structured hierarchy rather than a string of digits, the model recognizes symmetries across different parts of the calculation.
Beyond Linear Attention
While many researchers focus on augmenting standard Transformers, others argue that the architecture itself should follow the tree. The authors of the Tree Transformer suggest that when a model performs a bottom-up traversal of a syntactic tree, explicit positional encodings may become redundant. In these cases, the inherent topology of the tree provides sufficient relational information, making coordinate-based signals unnecessary for capturing sequence order. Similarly, Tai et al. showed that assigning unique parameter matrices to specific child positions (e.g., left vs. right) allows models to learn distinct transformations for different structural roles without explicit position vectors.
Key Foundational Work
Unsupervised clustering of continuous trajectories of kinematic trees with SOM-SD (2006) — contributed 1 concept elements to this direction.
Distributed Representation of Syntactic Structure by Tensor Product Representation and Non-Linear Compression (2004) — contributed 1 concept elements to this direction.