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:
- Syntactic Invalidity: Without structural constraints, sequence-to-sequence models frequently generate mathematically impossible expressions—such as mismatched parentheses or dangling operators. This limitation is highlighted by Lei Wang et al. in Translating Math Word Problem to Expression Tree and Markus N. Rabe et al. in Mathematical Reasoning via Self-supervised Skip-tree Training.
- Loss of Global Consistency: In math word problems, a model must map linear text to a mathematical solution. Yan Wang et al. (Deep Neural Solver for Math Word Problems) and Zhenwen Liang et al. (MWP-BERT: Numeracy-Augmented Pre-training for Math Word Problem Solving) demonstrate that flat models struggle to capture the logical distance between numbers in a solution tree, leading to errors in the predicted sequence of operations.
- Sensitivity to Surface Variations: In formal logic, changing a variable name (e.g., $A \land B$ to $X \land Y$) or reordering terms ($A \lor B$ to $B \lor A$) does not alter the underlying meaning. Yet, Yaqi Xie et al. (Embedding Symbolic Knowledge into Deep Networks.) show that sequential models are highly sensitive to these arbitrary string changes. Eser Aygün (Proving Theorems using Incremental Learning and Hindsight Experience Replay) similarly argues that linear strings fail to capture the inherent structural geometry and logical invariances of formal proofs.
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.