In symbolic AI—whether we are proving theorems, discovering physical laws via regression, or optimizing complex queries—we represent mathematical and logical ideas as nested structures. Traditionally, these are viewed as expression trees. However, trees suffer from a fundamental flaw: they are incredibly redundant. A simple operation like differentiating a formula or expanding a recursive definition can cause "expression swell," where the underlying data structure balloons in size, filled with identical copies of the same sub-expressions.
The research direction explored across these papers moves away from trees toward Directed Acyclic Graphs (DAGs). By ensuring that every unique sub-expression is stored exactly once and referenced via pointers, we can achieve exponential memory savings and transform computationally "impossible" problems into tractable ones.
The Problem of Expression Swell
In a standard tree representation, the formula $(a+b) \times (a+b)$ requires two separate branches for $(a+b)$. As formulas grow more complex—for instance, during the "anti-unification" of logical expressions described by Egor Vyacheslavovich Kostylev and Владимир Анатольевич Захаров—this redundancy leads to exponential memory consumption.
Reinhold Letz demonstrated in On the Polynomial Transparency of Resolution that even "short" proofs in automated theorem proving can be physically impossible to store if each inference step duplicates data. This "efficiency wall" is the primary motivator for structural sharing.
Collapsing Trees into DAGs
The core mechanism of this research is structural sharing (or "hash consing"). Instead of duplicating data, the system uses pointers to common sub-terms. This transforms the tree into a DAG.
Foundational work by Alberto Martelli and Ugo Montanari in Theorem Proving with Structure Sharing and Efficient Unification showed that by refining how variables are bound and stored, we can avoid the exponential blowups that plagued early proof checkers.
This isn't just a memory optimization; it changes the nature of the search. In Scaling Up Unbiased Search-based Symbolic Regression, Joachim Giesen and Henrik Voigt argue that representing equations as DAGs effectively shrinks the search space. If the algorithm doesn't have to "re-discover" the same sub-expression multiple times, it can focus on higher-level structural combinations.
From Syntax to Semantics with Equality Graphs
A more recent evolution of this idea is the Equality Graph (e-graph). While a standard DAG shares identical syntactic structures, an e-graph shares semantically equivalent ones.
In EGG-SR: Embedding Symbolic Equivalence into Symbolic Regression via Equality Graph, Yexiang Xue and colleagues use e-graphs to store sets of equivalent expressions (like $x+x$ and $2x$) in a single compact node. This allows search algorithms—whether based on Reinforcement Learning or Large Language Models—to treat mathematically identical formulas as a single entity, preventing the search from getting stuck in "algebraic loops."
Applications Across the AI Spectrum
The shift from trees to DAGs has yielded breakthroughs in several distinct sub-fields:
- Theorem Proving: Aditya Paliwal and Christian Szegedy at Google showed in Graph Representations for Higher-Order Logic and Theorem Proving that Graph Neural Networks (GNNs) perform significantly better when formulas are represented as DAGs. This allows the model to learn a unified embedding for a concept used across different parts of a proof.
- Symbolic Regression: Frameworks like GraphED, developed by Hao Xu and Yuntian Chen, treat equations as directed graphs to discover new constitutive laws in material science. By allowing multiple computational paths to reuse the same sub-expressions, they find simpler, more interpretable equations than traditional tree-based methods.
- Probabilistic Inference: Scott Sanner demonstrated in Symbolic Variable Elimination for Discrete and Continuous Graphical Models that representing piecewise functions as DAGs (specifically XADDs) allows for exact inference in complex models by merging redundant symbolic branches.
- Knowledge Tracking: Dafna Shahaf and Eyal Amir used DAGs to represent belief states in partially observable environments, ensuring that the representation size remains linear relative to the action sequence, even as the history of the agent grows.
Why It Works: The Intuition of Canonicality
The power of this approach lies in canonicalization. When we represent logic as a graph, we can "absorb" structural symmetries. Lucas Dixon explains in Basic Elements of Logical Graphs that this approach ensures logically equivalent statements map to a single canonical data structure.
In a tree, $A \land B$ and $B \land A$ are different. In a properly shared graph structure, they can be reduced to the same node. This reduction doesn't just save space; it simplifies the "reasoning" the computer has to do. If two things are the same in memory, the computer doesn't have to prove they are the same—it knows it by default.
By treating mathematical expressions as physical networks of shared components rather than isolated hierarchies, researchers are overcoming the "expression swell" that has historically limited the scale of symbolic reasoning.