Tree Structured Representations for Mathematical and Logical Expressions

39 concepts36 papers1 proposal

Deep learning has achieved remarkable success in natural language processing by treating text as a linear sequence of tokens. However, when standard sequence models encounter mathematics or formal logic, this flat representation breaks down. As Alexander Scarlatos et al. observe in their work on Tree-Based Representation and Generation of Natural and Mathematical Language, mathematical expressions are inherently recursive and hierarchical.

Consider a simple expression like $3 \times (4 + 5)$. A standard language model tokenizer sees a flat sequence of symbols: [3, ×, (, 4, +, 5, )]. Mathematically, however, the sub-expression $(4 + 5)$ is a single cohesive unit nested inside a multiplication operation. Forcing a neural network to process this structure as a linear string creates a fundamental structural representation gap. To solve complex mathematical and logical problems, models must move away from flat sequences and instead align their internal architectures with the tree-like topology of logic.

Why Flat Sequences Fail

When deep learning models lack an explicit structural bias, they face several critical failure modes that prevent true mathematical reasoning:

Structural Encoders: Mapping Formulas to Graphs and Trees

To bridge this gap, researchers have redesigned neural network inputs to match the topology of mathematical logic. Instead of reading a string from left to right, these models encode formulas as graphs or abstract syntax trees (ASTs).

        [*]  <-- Root Operation
       /   \
     [3]   [+] <-- Sub-expression Unit
          /   \
        [4]   [5]

For example, Mingzhe Wang et al. developed FormulaNet in Premise Selection for Theorem Proving by Deep Graph Embedding, which represents mathematical formulas as graphs to preserve argument order and quantifier bindings. By operating on the formula's topology rather than its text string, the model bypasses the challenge of tracking long-range dependencies across a flat sequence of tokens.

Similarly, Zichao Wang et al. introduced FORTE in Mathematical Formula Representation via Tree Embeddings, utilizing an unsupervised tree encoder to capture the grammar of operators and operands. This ensures that sub-expressions are transformed as cohesive units, a property critical for analyzing step-by-step algebraic manipulations (Mengxue Zhang et al. in Math Operation Embeddings for Open-ended Solution Analysis and Feedback).

To scale these ideas to high-dimensional algebra and temporal planning, researchers have embedded tree structures directly into attention mechanisms and generative flows. Mohamed Malhou et al. developed HATSolver (HATSolver: Learning Gröbner Bases with Hierarchical Attention Transformers), which nests tokens within terms and terms within equations to solve complex polynomial systems. In robot trajectory planning, Yue Meng et al. (TeLoGraF: Temporal Logic Planning via Graph-encoded Flow Matching) use graph neural networks to encode Signal Temporal Logic, achieving permutation invariance and robust generalization to unseen constraints.

Structural Decoders: Generating Valid Logic

Fixing how models read expressions is only half the battle; they must also generate structured outputs without breaking syntactic rules. Tree-structured decoders replace standard sequential token generation with a top-down or parallel expansion of an expression tree.

In Tree-structured Decoding for Solving Math Word Problems, Qianying Liu et al. designed a decoder that generates equations as ASTs in a prefix-order manner. By explicitly tracking parent-child and sibling relationships via an auxiliary stack, the model guarantees that every generated token satisfies the structural constraints of a valid equation.

To optimize this process, the authors of An Expression Tree Decoding Strategy for Mathematical Equation Generation proposed a strategy that predicts multiple independent solving steps in parallel rather than sequentially. Furthermore, Bugeun Kim et al. (Point to the Expression: Solving Algebraic Word Problems using the Expression-Pointer Transformer Model) grouped tokens into holistic "Expression" units and used pointers to maintain global consistency, preventing the fragmentation that typically derails flat sequence decoders.

Compositional Generalization and Multi-Level Proofs

The benefits of tree-structured representations become most apparent in high-level mathematical reasoning and formal verification, where models must generalize to novel, complex formulas.

Boris Katz et al. demonstrated in Encoding formulas as deep networks: Reinforcement learning for zero-shot execution of LTL formulas that when a neural network's architecture mirrors the compositional structure of Linear Temporal Logic (LTL), it achieves zero-shot generalization. Because the network architecture itself is aligned with the logical operators, the agent can execute entirely unseen formula compositions without task-specific retraining.

When moving from individual formulas to entire proofs, the hierarchy scales up: tokens form propositions, and propositions form logical arguments. Wenda Li et al. introduced the Hierarchical Transformer (HAT) in IsarStep: a Benchmark for High-level Mathematical Reasoning to maintain context across these multiple levels of abstraction. To navigate the vast search space of formal proofs, Kefan Dong et al. (Formal Theorem Proving by Rewarding LLMs to Decompose Proofs Hierarchically) developed ProD-RL, a reinforcement learning framework that rewards large language models for decomposing complex theorems into smaller, provable lemmas.

By replacing flat sequential processing with tree- and graph-structured inductive biases, these approaches eliminate the structural representation gap. Aligning the topology of neural networks with the syntax of mathematics allows models to move past surface-level string memorization and achieve true structural understanding.

Key Foundational Work

HolStep: A Machine Learning Dataset for Higher-order Logic Theorem Proving (2017) — contributed 2 concept elements to this direction.
Deep Neural Solver for Math Word Problems (2017) — contributed 1 concept elements to this direction.
Premise Selection for Theorem Proving by Deep Graph Embedding (2017) — 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_structural_representation_gap_16103235,
  title = {structural representation gap},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/structural-representation-gap/rdr_16103235b2c34a1aab8b64a1ebfd5477},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_structural_representation_gap_16103235_v1,
  title = {structural representation gap},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/structural-representation-gap/rdr_16103235b2c34a1aab8b64a1ebfd5477/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake