Abstract
Symbolic regression (SR) aims to discover mathematical expressions that best fit a given dataset. A significant challenge in SR is syntactic redundancy, where multiple distinct expressions represent the same mathematical function, leading to inefficient search. This paper introduces EGG-SR, a framework that integrates symbolic equivalence into SR algorithms using Equality Graphs (e-graphs). By grouping equivalent expressions into e-classes, EGG-SR enables more efficient exploration and more accurate discovery of physical laws. We demonstrate the effectiveness of EGG-SR across Monte Carlo Tree Search (MCTS), Deep Reinforcement Learning (DRL), and Large Language Model (LLM) based solvers.
Introduction
The search for mathematical formulas to describe natural phenomena is a cornerstone of scientific discovery. Symbolic regression automates this process but faces an exponentially large search space. A primary bottleneck is the "syntactic redundancy" problem: many syntactically different expressions are semantically identical (e.g., $x+x$ and $2x$). Standard SR algorithms treat these as separate entities, wasting computational resources on redundant paths. EGG-SR addresses this by embedding mathematical "common sense" directly into the search process through a compact representation of symbolic equivalence.
Methodology: The Egg Module and E-Graphs
The core of the EGG-SR framework is the Egg module, which leverages Equality Graphs (e-graphs). An e-graph is a data structure that compactly stores sets of equivalent expressions by sharing common sub-expressions. Instead of enumerating every possible variant, expressions are grouped into "e-classes."
The construction of an e-graph involves four main steps: initialization, matching sub-expressions against predefined rewrite rules (e.g., commutativity), substituting new nodes based on those rules, and merging equivalent nodes into the same e-class. This process, known as "equality saturation," allows the system to discover complex simplifications and equivalences that might be non-obvious to standard algorithms.
Integration with SR Algorithms
EGG-SR is designed to be a plug-and-play module for various SR paradigms, providing theoretical benefits such as tighter regret bounds and reduced gradient variance.
Egg-MCTS (Monte Carlo Tree Search)
In standard MCTS, the algorithm explores a tree of production rules. Egg-MCTS uses the e-graph as a transposition table. When a new expression is generated, the Egg module identifies its equivalent counterparts already present in the search tree.
During the backpropagation phase, rewards and visit counts are updated not just for the current path, but across all equivalent paths simultaneously. This "EGG-based Propagation" effectively prunes the search space by sharing information between semantically identical nodes.
Egg-DRL and Egg-LLM
In DRL-based SR, Egg-DRL utilizes the e-graph to sample equivalent variants of a generated expression, producing a lower-variance gradient estimator for more stable training. For LLM-based SR, the Egg module enriches the feedback loop by providing the LLM with both the original formula’s fitness and its equivalent forms, helping the model better navigate the mathematical landscape.
Experimental Evaluation
The researchers evaluated EGG-SR on several benchmarks, including custom trigonometric datasets with high redundancy, scientific benchmarks (e.g., Oscillation, Bacterial Growth), and the Feynman dataset.
Key Results
- Accuracy and Efficiency: EGG-SR consistently outperformed baseline versions of MCTS, DRL, and LLM-SR in terms of Normalized Mean Squared Error (NMSE).
- Memory Compactness: E-graphs proved exceptionally efficient. For expressions with 80 variables, the e-graph required only roughly $10^2$ KB of memory, whereas an array-based storage of equivalent forms would require over $10^6$ KB.
- Low Computational Overhead: The time required for e-graph construction and querying was negligible compared to other SR tasks like coefficient optimization.
Discussion and Future Work
While EGG-SR significantly improves SR efficiency, some limitations remain. Rewrite rules must be carefully defined to avoid domain violations (e.g., $\log(ab)$ vs $\log a + \log b$ for negative values) and infinite loops. Future work involves extending the framework to other architectures like Symbolic Networks and exploring e-graph utility during the inference phase.
Summary updated