🔭 astrophysics

The Inefficiency of Genetic Programming for Symbolic Regression

This paper demonstrates that genetic programming is inefficient for symbolic regression in limited settings, as it explores only a small fraction of semantically unique expressions and redundantly evaluates congruent ones compared to random search, a finding enabled by improved equality saturation algorithms.

Original authors: Gabriel Kronberger, Fabricio Olivetti de Franca, Harry Desmond, Deaglan J. Bartlett, Lukas Kammerer

Published 2026-03-30

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Gabriel Kronberger, Fabricio Olivetti de Franca, Harry Desmond, Deaglan J. Bartlett, Lukas Kammerer

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to find the perfect recipe for a cake. You have a massive cookbook (the "search space") containing millions of possible combinations of flour, sugar, eggs, and baking times. Your goal is to find the one recipe that tastes exactly like the cake your grandmother used to make.

This paper is about a specific way of searching for that recipe, called Genetic Programming (GP). It's like a digital chef that tries to evolve better recipes over time by mixing and mutating existing ones, mimicking how nature evolves species.

The authors of this paper asked a simple but shocking question: "Is this digital chef actually efficient, or is it just wasting a lot of time?"

To find out, they didn't just let the chef guess blindly. They used a super-powerful computer method to write down every single possible unique recipe in a limited cookbook. Then, they watched the digital chef work and compared its performance to a chef who just picked recipes completely at random from that list of unique options.

Here is the breakdown of their findings using some everyday analogies:

1. The Problem: The "Duplicate" Trap

The biggest issue the paper found is that the digital chef is terrible at realizing when it has already tasted a dish.

The Analogy: Imagine you are tasting soup. You taste a bowl of "Tomato Soup." Then, you taste another bowl that looks different (maybe it's in a blue bowl instead of a red one, or the spoon is on the left), but it's exactly the same soup.
What GP does: The digital chef keeps tasting these "different-looking but identical" soups over and over again. It thinks it's exploring new territory, but it's actually just walking in circles.
The Math: The paper found that for every 100 recipes the chef tried, only about 10 to 20 were actually new and unique. The other 80 to 90 were just re-tasting the same thing in disguise.

2. The Comparison: The "Random Walker" vs. The "Evolutionary Chef"

To test if the chef was doing a good job, the authors compared it to a Random Walker.

The Random Walker: This is a chef who closes their eyes, points at a page in the "Unique Recipe Book," and tries that recipe. If they like it, they keep it. If not, they pick another random page. Crucially, they never pick the same page twice.
The Result: The Random Walker found the best recipes much faster than the Evolutionary Chef.
Why? Because the Evolutionary Chef was wasting so much time re-evaluating the same "duplicate" soups, it barely made any progress. The Random Walker, by only tasting unique dishes, covered the ground much more efficiently.

3. The "Short Circuit" (Simplification)

The authors used a clever trick called Equality Saturation (think of it as a "Magic Simplifier").

The Analogy: Imagine you have a recipe that says: "Take 2 cups of flour, add 0 cups of water, mix, then add 0 cups of sugar."
The Magic: The Magic Simplifier looks at that and says, "Hey, that's just '2 cups of flour'!" It strips away the unnecessary steps to reveal the core truth.
The Finding: When the authors used this Magic Simplifier on the digital chef's work, they realized the chef was generating thousands of complex-looking expressions that all simplified down to the same simple thing (like a constant number). The chef was busy building elaborate castles out of sand, only to realize they were all just piles of sand.

4. The Real-World Test

They didn't just use made-up data. They tested this on two real scientific problems:

Water flowing through rough pipes: Trying to find the formula that predicts how fast water moves.
Galaxy movement: Trying to find the formula that explains how stars move in galaxies (a hot topic in physics regarding "Dark Matter").

In both cases, the digital chef (Genetic Programming) failed to find the absolute best formula, even after trying thousands of times. Meanwhile, the "Random Walker" (which just checked unique formulas one by one) found the best ones much more reliably.

The Big Takeaway

The paper concludes that Genetic Programming is surprisingly inefficient for this specific type of problem.

It's like sending a detective to solve a crime by interviewing 1,000 people, only to realize that 900 of them are the same person wearing different hats. The detective spends all day talking to the same suspect, missing the actual clues that a simple, random check of the suspect list would have found much faster.

In short: The paper suggests that for finding mathematical formulas, the "evolution" method might be overcomplicating things and wasting time on duplicates, whereas a smarter, more direct search for unique ideas might be the better path forward.

1. Problem Statement

The paper addresses the fundamental inefficiency of Genetic Programming (GP) when applied to Symbolic Regression (SR). While GP is a popular evolutionary algorithm for discovering mathematical expressions from data, it suffers from a "redundancy problem." The search space of GP consists of expression trees (genotypes), but many structurally different trees represent the same mathematical function (semantically equivalent or isomorphic expressions).

The authors argue that GP wastes computational resources by:

Repeatedly evaluating expressions that are semantically identical to those already visited.
Failing to explore the space of semantically unique expressions efficiently compared to a random search.
Struggling to find the global optimum even in limited search spaces where an exhaustive enumeration is possible.

2. Methodology

To rigorously quantify GP's inefficiency, the authors developed a framework to compare GP against an Exhaustive Symbolic Regression (ESR) approach and an Idealized Random Search (RS) within a constrained search space.

A. Improved Exhaustive Symbolic Regression (ESR)

The authors enhanced the ESR algorithm to enumerate all possible solutions up to a specific complexity limit.

Search Space Definition: They limited operators to $\{+, -, \cdot, \div, x^{-1}, \text{powabs}(x, y)\}$ and expression lengths (nodes) to 10, 12, and 20.
Equality Saturation (Eq-Sat): A critical innovation was the use of equality saturation (via the MetaTheory.jl package and e-graphs). Instead of relying on fitness values to detect duplicates (which fails if parameters differ), they used Eq-Sat to rewrite expressions into a canonical form. This allows the detection of semantic duplicates regardless of parameterization or structural isomorphism.
Process:
1. Generate all valid expression trees via breadth-first search.
2. Apply Eq-Sat to simplify expressions to a canonical form and remove semantic duplicates.
3. Optimize parameters for the remaining unique expressions using the VAR1 optimizer (NLOpt) with multiple random restarts to ensure global optimality.

B. Genetic Programming (GP) Setup

Algorithm: They used a modified TinyGP implementation (Koza-style) and compared it with Operon (a state-of-the-art GP system) on one dataset.
Mechanisms: Standard tournament selection, subtree crossover, and subtree mutation.
Parameter Optimization: Integrated with SciPy's BFGS optimizer for fitting parameters.
Tracking: The authors logged every evaluated expression to determine how many were unique, how many were structural duplicates, and how many were semantically equivalent after simplification.

C. Datasets

Two real-world physical science datasets were used:

Nikuradse Dataset: Flow in rough pipes (predicting turbulent friction).
Radial Acceleration Relation (RAR): Galaxy dynamics (linking visible mass acceleration to total dynamical acceleration). This dataset utilized a sophisticated Marginalized Normal Regression (MNR) likelihood function to handle uncertainties in both variables.

3. Key Contributions

Quantification of Redundancy: The paper provides empirical evidence that GP revisits semantically identical expressions at an alarming rate. In limited search spaces, only 10–20% of expressions evaluated by GP are unique; the rest are redundant.
Superiority of Random Search on Unique Space: When restricted to the space of semantically unique expressions, an idealized Random Search (RS) outperforms GP. RS finds high-quality solutions with fewer evaluations because it does not waste time on duplicates.
Equality Saturation for SR: The authors demonstrate the utility of Eq-Sat not just for theorem proving, but as a practical tool for analyzing the search dynamics of SR algorithms, enabling the detection of isomorphic solutions that traditional fitness-based checks miss.
Benchmarking Framework: They established a method to calculate the exact "success probability" of finding the global optimum by comparing GP against a fully enumerated solution space.

4. Results

Search Efficiency:
- GP vs. RS: For the Nikuradse dataset (length 10), GP required ~600 visited expressions to reach a 50% success rate for a specific MSE threshold, whereas RS reached 50% in ~100 expressions.
- Global Optimum Failure: In 50 independent runs, neither TinyGP nor Operon found the global optimum for the Nikuradse or RAR datasets within the length limits of 10 or 12.
- Longer Lengths: Even when allowing GP to search up to length 20 (to find solutions that simplify to length 12), GP still failed to find the global optimum, while RS in the length-12 space found it with 100% success.
Semantic Duplicates:
- Nikuradse: Without simplification, 60–80% of expressions were structurally distinct. However, after simplification, only 20–40% were unique. Furthermore, ~50% of evaluated expressions simplified to a trivial constant ( $p_1$ ).
- RAR: Similar trends were observed. While GP visited more distinct structures (80–100%), only about 50% were semantically unique after simplification. Approximately 10% of all evaluations were revisits of the same unique expression.
Solution Quality:
- The solution space is highly "needle-in-a-haystack." Only ~0.01% to 1% of all unique expressions are close to the global optimum.
- GP tends to get stuck in local optima or wastes cycles on redundant structures, failing to traverse the "neutral networks" effectively enough to reach the best solutions.

5. Significance and Conclusion

The paper challenges the assumption that GP's evolutionary mechanisms (crossover/mutation) are inherently superior to random sampling in the space of unique functions.

Inefficiency Confirmed: GP is shown to be inefficient in limited settings because it spends the majority of its computational budget evaluating redundant expressions.
Implications for SR: The results suggest that current GP systems may need fundamental changes, such as:
- Better mechanisms to avoid generating semantically equivalent individuals.
- Integration of equality saturation directly into the evolutionary loop to prune the search space.
- Re-evaluation of the role of "neutral steps" (revisiting equivalent fitness) in GP, as the current implementation seems to revisit them wastefully rather than usefully.
Future Work: The authors note that while these results hold for short expressions (10–20 nodes), it remains to be seen if the redundancy scales similarly to typical GP runs with longer trees (up to 100 nodes) or multiple variables.

In summary, the study provides a rigorous, data-driven argument that Genetic Programming is currently inefficient for Symbolic Regression due to its inability to navigate the search space without massive redundancy, often performing worse than a simple random search over unique expressions.