Taming the Combinatorial Explosion in Symbolic Regression

514 concepts344 papers3 proposals

Symbolic regression (SR) is often described as the "holy grail" of data-driven science. Unlike standard regression, which fits parameters to a fixed model, SR seeks to discover the underlying mathematical formula itself. However, as Zhengyao Huang et al. note, this is a "needle-in-a-haystack" problem of infinite size. The number of ways to combine variables, constants, and operators grows exponentially with the length of the expression, a phenomenon known as the combinatorial search space explosion.

To make this search tractable, researchers have moved beyond simple brute-force enumeration, developing strategies to prune, guide, and decompose the search space.

The Geometry of the Search Space

The fundamental challenge of symbolic regression is that the search space is discrete and non-differentiable. In a standard neural network, you can follow a gradient toward a better solution. In SR, changing a single operator (e.g., changing a + to a *) can radically alter the model's behavior, making the "fitness landscape" jagged and difficult to navigate.

Louis Wehenkel et al. point out that this complexity creates severe computational bottlenecks, where the evaluation of even moderately long formulas becomes resource-intensive. As the number of input variables increases, Kazumi Saito et al. argue that traditional symbolic search methods quickly become unmanageable.

Guiding Search with Neural Priors

One of the most successful ways to navigate this explosion is to use deep learning as a "compass" for the discrete search. Instead of searching blindly, a neural network can learn which mathematical structures are most likely to fit the data.

Brenden K. Petersen et al. introduced a framework that uses a Recurrent Neural Network (RNN) to generate expressions token-by-token. By using a "risk-seeking" policy gradient, the model focuses on finding the single best expression rather than the average performance, effectively steering the search toward high-performing regions of the combinatorial space. Similarly, Miles Cranmer et al. use Graph Neural Networks (GNNs) to "factorize" complex systems into simpler internal components, which are then distilled into symbolic forms. This "divide-and-conquer" approach reduces the dimensionality of the symbolic search, making it possible to discover laws for multi-component physical systems.

Continuous Relaxation of Discrete Choices

If the main problem is that symbolic search is discrete, one solution is to make it continuous. Ahmed Alaa et al. proposed symbolic metamodeling, which uses a highly general class of functions called Meijer G-functions. Because these functions can represent almost any common mathematical expression, the authors can transform the discrete search for a formula into a continuous optimization problem solvable via gradient descent.

Philipp Scholl furthered this idea with ParFam, which uses flexible mathematical templates. By pairing these templates with a Transformer-based neural guide, the search for the correct polynomial degree or operator becomes a guided optimization rather than a random mutation.

Pruning with Physical Constraints

The search space for symbolic regression contains an astronomical number of expressions that are mathematically valid but physically nonsensical. By enforcing physical laws during the search, researchers can prune the majority of the search space.

Marko Durasevic et al. demonstrated that "dimensional awareness"—ensuring that you don't add meters to seconds—doesn't just prune the search space; it often makes complex physics problems trivial to solve. By rejecting dimensionally inconsistent candidates, the algorithm focuses only on the narrow slice of the search space that could actually represent a physical law. Hao Xu took this a step further with EqGPT, a model that learns the "language" of physics from mathematical handbooks, ensuring that generated candidate equations align with established scientific principles.

Decomposition and Parallelism

When faced with high-dimensional datasets, the search space explodes because the algorithm tries to find a single formula that relates all variables at once. Nan Jiang 0012 et al. introduced Control Variable Genetic Programming (CVGP) to solve this. By holding most variables constant while varying one at a time—mimicking the classical scientific method—they break an exponentially large search space into manageable, polynomial-sized chunks.

Finally, when the search space cannot be pruned or guided further, it must be searched faster. Kai Ruan et al. developed Parallel Symbolic Enumeration (PSE), which leverages GPU parallelism to evaluate millions of candidate expressions simultaneously. By turning the search into a high-speed race, they can exhaustively explore deeper into the combinatorial space than previously possible.

Through these combined efforts—neural guidance, continuous relaxation, physical pruning, and decomposition—symbolic regression is evolving from a niche tool for low-dimensional problems into a scalable engine for scientific discovery.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 352 papers
  2. Version 1 · 2026-10-04 · 446 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_combinatorial_search_space_explosion_sym_805284ca,
  title = {combinatorial search space explosion (symbolic search space complexity)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/combinatorial-search-space-explosion-symbolic-search-space-complexity/rdr_805284ca10b8476d8906434edf31cddf},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 2, frozen text):

@misc{lacuna_combinatorial_search_space_explosion_sym_805284ca_v2,
  title = {combinatorial search space explosion (symbolic search space complexity)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/combinatorial-search-space-explosion-symbolic-search-space-complexity/rdr_805284ca10b8476d8906434edf31cddf/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake