Linearizing Expression Trees for Symbolic Reasoning

17 concepts16 papers1 proposal

Neural networks, particularly Transformers, are designed to process linear sequences of tokens. However, mathematical and logical expressions are inherently hierarchical, traditionally represented as trees where internal nodes are operators and leaves are operands. To bridge this gap, researchers have converged on expression tree linearization: a method of serializing these trees into unambiguous sequences that allow sequence-to-sequence models to perform "rigid" symbolic reasoning.

The Problem with Infix Notation

Standard mathematical notation (e.g., $2 + (3 \times 4)$) is known as infix notation. While intuitive for humans, it is computationally difficult for neural networks to generate for two reasons:

  1. Ambiguity: Without parentheses or complex precedence rules (PEMDAS), the order of operations is unclear.
  2. Syntactic Overhead: Generating balanced parentheses is a structural requirement that consumes model capacity. If a model fails to close a bracket, the entire expression becomes syntactically invalid.

As Lample and Charton demonstrate in Deep Learning For Symbolic Mathematics, treating math as a translation task requires a representation that is as streamlined as natural language but as precise as a computer program.

Serialization via Tree Traversal

The solution is to represent expressions as trees and then flatten them using specific traversal algorithms. Two primary formats emerge across the literature:

  • Prefix Notation (Polish Notation): Derived from a pre-order traversal (root-left-right). Operators precede their operands (e.g., $+ \ 2 \ \times \ 3 \ 4$). Ustyuzhanin et al. note in Symbolic expression generation via variational auto-encoder that this format simplifies the generation of valid formulas by removing the need for explicit brackets.
  • Postfix Notation (Reverse Polish Notation): Derived from a post-order traversal (left-right-root). Operands precede their operators (e.g., $2 \ 3 \ 4 \ \times \ +$). Wang et al. argue in Reinforcement-Enhanced Autoregressive Feature Transformation that postfix notation ensures every generated sequence is structurally valid and reduces the token set, making it easier for decoders to process complex formulas.

Why Linearization Works

The power of these representations lies in their unambiguity. In a linearized tree, the structure of the calculation is baked into the sequence itself.

1. Eliminating Parentheses

By using prefix or postfix notation, the model no longer needs to learn the "tax" of balancing nested parentheses. d'Ascoli et al. highlight in ODEFormer that this structural choice ensures every generated sequence can be uniquely parsed back into a computational tree. This is particularly useful for Symbolic Regression, where the model must discover the underlying physics of a system from noisy data.

2. Leveraging Fixed Arity

In many formal systems, operators have a fixed number of arguments (arity). For example, addition ($+$) is binary, while square root ($\sqrt{x}$) is unary. Yeh and Ong explain in Most of a Formal Proof is Forced that when arity is fixed, a pre-order traversal creates a token stream that requires no delimiters at all. The model simply "knows" how many tokens to expect after each operator.

3. Simplifying the Grammar

For tasks like Math Word Problems (MWP), Wang et al. show in Translating Math Word Problem to Expression Tree that predicting a postorder traversal allows the decoder to focus on the logical sequence of operations rather than the surface-level syntax of the expression. This is echoed in Evolutionary Large Language Model for Automated Feature Transformation, where postfix notation reduces syntactic errors during the automated discovery of new data features.

Applications Across Domains

This technique has enabled Transformers to master domains previously reserved for symbolic solvers:

By transforming hierarchical logic into a flat, unambiguous sequence, linearization allows neural networks to treat symbolic reasoning as a standard language modeling task, effectively bridging the gap between connectionist pattern recognition and symbolic logic.

Key Foundational Work

Modeling Intra-Relation in Math Word Problems with Different Functional Multi-Head Attentions (2019) — contributed 1 concept elements to this direction.
Translating Math Word Problem to Expression Tree (2018) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

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

This exact version (version 1, frozen text):

@misc{lacuna_expression_tree_linearization_5936c5bd_v1,
  title = {expression tree linearization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/expression-tree-linearization/rdr_5936c5bddd0d432a9d98744a5a78a0d3/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake