EGG-SR: Embedding Symbolic Equivalence into Symbolic Regression via Equality Graph
Authors: Nan Jiang
Ziyi Wang
Yexiang Xue
Venue: ICLR 2026 Poster (2026)
Keywords: Symbolic Regression
symbolic equivalence
Monte Carlo Tree Search
Deep Reinforcement Learning
Large Language Model
Primary area: applications to physical sciences (physics, chemistry, biology, etc.)
TL;DR: We introduce EGG-SR, a unified framework that integrates equality graphs (e-graphs) into diverse symbolic regression algorithms.

Abstract: Symbolic regression seeks to uncover physical laws from experimental data by searching for closed-form expressions, which is an important task in AI-driven scientific discovery. Yet the exponential growth of the search space of expression renders the task computationally challenging.
A promising yet underexplored direction for reducing the search space and accelerating training lies in *symbolic equivalence*: many expressions, although syntactically different, define the same function -- for example, $\log(x_1^2x_2^3)$, $\log(x_1^2)+\log(x_2^3)$, and $2\log(x_1)+3\log(x_2)$.
Existing algorithms treat such variants as distinct outputs, leading to redundant exploration and slow learning.
We introduce EGG-SR, a unified framework that integrates symbolic equivalence into a class of modern symbolic regression methods, including Monte Carlo Tree Search (MCTS), Deep Reinforcement Learning (DRL), and Large Language Models (LLMs).
\method-SR compactly represents equivalent expressions through the proposed EGG module (via equality graphs), accelerating learning by:
(1) pruning redundant subtree exploration in EGG-MCTS,
(2) aggregating rewards across equivalent generated sequences in EGG-DRL, and
(3) enriching feedback prompts in EGG-LLM.
Theoretically, we show the benefit of embedding EGG into learning: it tightens the regret bound of MCTS and reduces the variance of the DRL gradient estimator.
Empirically, EGG-SR consistently enhances a class of symbolic regression models across several benchmarks, discovering more accurate expressions within the same time limit.
Project page is at: https://nan-jiang-group.github.io/egg-sr.

Published as a conference paper at ICLR 2026
EGG-SR: EMBEDDING SYMBOLIC EQUIVALENCE INTO SYMBOLIC REGRESSION VIA EQUALITY GRAPH
Nan Jiang
Ziyi Wang, Yexiang Xue
University of Texas El Paso n langeutep. edu
Purdue University (wang4538 yexiang (eprduueeuuuuuuu edu
ABSTRACT
Symbolic regression seeks to uncover physical laws from experimental data by searching for closed-form expressions, which is an important task in AI-driven scientific discovery. Yet the exponential growth of the search space of expression renders the task computationally challenging. A promising yet underexplored di- rection for reducing the search space and accelerating training lies in symbolic equivalence: many expressions, although syntactically different, define the same function - for example, (og(xf log(x1) log(22). and 2 (og( + 3 log(22). Existing algorithms treat such variants as distinct outputs, leading to redundant exploration and slow learning. We introduce EGG-SR, unified framework that integrates symbolic equivalence into a class of modern symbolic regression meth- ods, including Monte Carlo Tree Search (MCTS), Deep Reinforcement Learn- ing (DRL), and Large Language Models (LLMs). EGG-SR compactly represents equivalent expressions through the proposed EGG module (via equality graphs), accelerating learning by: (1) pruning redundant subtree exploration in EGG- MCTS, (2) aggregating rewards across equivalent generated sequences in EGG- DRL, and (3) enriching feedback prompts in EGG-LLM. Theoretically, we show the benefit embedding EGG into learning: tightens the regret bound of MCTS and reduces the variance of the DRL gradient estimator. Empirically, EGG-SR consistently enhances a class of symbolic regression models across several bench- marks, discovering more accurate expressions within the same time limit.
Project page is at: https: : nan jono-jjann lang -allanng-rroa group. github. i oo/egg--
INTRODUCTION
Symbolic regression aims to automatically discover physical knowledge from experimental data and
has been widely used in scientific domains (Schmidt & Lipson 2009: Udrescu & Tegmark 2020
et al.) 2024: Yu & Wang 2024 LaFollette et al. 2025). Many contemporary methods
for symbolic regression formulate the search for optimal expressions a sequential decision-making
process. In literature, existing methods learn to predict the sequence of grammar rules (Sun et al.,
2023]. the traversal sequence of expression trees (Petersen al. 2021 Kamienny al. (0022), or
executable strings that follow Python syntax (Shojaee et al.J 2025 /Zhang et al. 2025).
This task
remains computationally challenging due its NP-hard nature (Virgolin & Pissis 2022
that is, the
search space of candidate expressions grows exponentially with the data dimension.
promising yet underexplored direction for reducing the search space and accelerating discovery is the integration of symbolic equivalence into learning algorithms. For example. these expressions log( (x)) log(x?) + log(r]), and 2 2ogg(11) + log(222 all represent the same math function and are therefore symbolically equivalent. Ideally, a well-trained model would recognize such equiv- alence and assign identical goodness-of-fit. rewards, or losses to the corresponding predicted ex- pressions (Allamanis al. 2017). since these expressions produce identical functional outputs and attain the same prediction error on the dataset. In the literature, existing SR algorithms treat these expressions distinct outputs, leading to redundant exploration of the search space and slow train- aaboolicall-eeuivalllee.. expressions
ing. The main challenge of this direction is: how to represent and embed them into modern learning frameworks in unified and scalable manner?

---

Published as a conference paper at ICLR 2026
Since the number of equivalent variants grows exponentially with expression length, explicitly main- taining the set of equivalent expressions is not time and memory scalable. To mitigate this scalability challenge, a line of recent works introduced the Equality graph (e- (e-graph), data structure that com- pactly encodes the set of equivalent variants by storing shared sub-expressions only once (Nandi) et al. 202T Willsey et al.] 202T, Kurashige et al. [0024). e-graphs have been applied to tasks, including program optimization (Barbulescu et al.) 2024), dataset generation of equivalent expres- sions (Zheng et al. 2025). In genetic programming basen symbolic regression, e-graphs have been used for duplicate detection (de França & Kronberger, (025), expression simplification (de França & Kronberger (023), and expression template pattern matching (de França & Kronberger] (025). Despite the empirical successes, we find that a unified framework that enables diverse symbolic regression algorithms to interact with e-graphs to accelerate learning has room for improvement.
We present a unified framework, EGG-SR, that integrates symbolic equivalence into class of learn- ing algorithms via e-graphs. Our framework encompasses EGG-MCTS, EGG-DRL, and EGG-LLM. The core idea is to leverage EGG to efficiently sample equivalent variants of expressions predicted by SR algorithms and compute a new equivalence-aware learning objective. Specifically, (1) EGG- MCTS prunes redundant exploration over equivalent subtrees; (2) EGG-DRL aggregates rewards over equivalent expressions, stabilizing training: (3) EGG- enriches the feedback prompt with multiple equivalent expressions better guide next round predictions. Under mild theoretical sumptions, we show the benefit of emhedding symbolic equivalence into learning: (1) EGG-MCTS offers tighter regret bound than standard MCTS (Sun et al. (2023) and (2) the gradient estimator of EGG-DRL exhibits a lower variance than that of standard DRL (Petersen et al. 2021).
In experiments, we evaluate EGG-SR with several representative symbolic regression baselines across several challenging benchmarks. We demonstrate its advantages over existing approaches using EGG than without. EGG consistently improves performance across diverse frameworks, dis- covering more accurate expressions than baseline within fixed time budget.
PRELIMINARIES
Symbolic Expression. Let x (x1,..., denote input variables and c (cI,..., Cm be co- efficients. A symbolic expression ø connects these variables and coefficients using mathematical operators such as addition, multiplication, and logarithm. For example, e = 3 log xi + 2 log 22 is symbolic expression composed of variables {21, operators {+, log). and coefficients {cr
3, 02 = 2]. In literature, symbolic expressions have been represented as binary trees (de França & Kronbergger, 2025), pre-order traversal sequences of the binary tree (Petersen al. 2021 topo-
logical traversal sequences of the expression graph (Kahlmeyer et al. 2024 Xiang et al. 2025 or sequences of production rules defined by context-free grammar (Sun et al. 2023).
To handle all symbolic objects in this work, a context-free grammar is adopted to represent symbolic expressions (Brence et al., 2021). The grammar is defined by a tuple (V, Σ, Rt, where (1) V is a set of non-terminal symbols representing arbitrary sub-expressions, i.e., V = {A]: (2) Σ is a set of terminal symbols, including input variables and coefficients, i.e., {x1 { , 2,,) U [c]: (3) R is
a set of production rules representing mathematical operations. For example, A + A x A denotes multiplication, and the semantics to replace the left-hand side with the right-hand side; (4) S is the start symbol, typically set to S = A. Given a sequence of production rules, an expression is constructed by sequentially applying each rule to the leftmost nonterminal, starting from S. the resulting string contains no nonterminals, it corresponds to valid expression.
Figure 6 (in appendix) shows the expression construction with sequence (A + A x A, A c, log(z1) x1 ]]. The first rule A + A x A expands the start symbol ś A to Φ A x A. Applying the next rule A + c yields o= = C1 x A. An index is assigned to the coefficient symbol e, to differentiate multiple coefficients. Finally, applying A + log(x1) to 6 C₁ x A yields 6 c₁ log(z1).
Symbolic Equivalence under a Rewrite System. Rewrite rules are widely used to simplify, re- arrange, and reformulate expressions in tasks such as code optimization and automated theorem proving (Huet & Oppen| 1980 Nandi et al. 2021). A rewrite system provides principled proce- dure for transforming expressions by replacing sub-expressions according to predefined patterns.
Formally, a rewrite rule r; is written as "LHS ~e RHS", where the left-hand side (LHS) specifies a pattern to be matched, and the right-hand side (RHS) specifies the substitution applied upon match.
2

---

Published as a conference paper at ICLR 2026
Given set of rewrite rules R = {r1, rs....., ..), the symbolic equivalence relation =R induced by R is defined as follows: for two symbolic expressions Φ1 and 22
Φ R の22
if and only if
Φ1 -- Φ2 02 Φ1
(1)
where Φ1 = 22 means that Φ1 can be transformed into de by applying finite sequence of rewriting using R. In other words, two expressions are equivalent under R if one can be transformed into the other via repeated rewriting.
For example, consider the rewrite rule log(a x b) ~ log(a) + log(b) (denoted as rı), where a and b are placeholders for arbitrary sub-expressions. Since Φ1 = (og(z{=²) can be transformed into 2 = log( + log (23) by applying 71 once, Φ1 and d2 are symbolically equivalent under r1-
In this work, the known mathematical identities listed in Table 3 (in the appendix) are encoded as rewrite rules in R. Section 3.1 applies these rewrite rules over the e-graph to generate a batch of symbolically equivalent expressions via matching (Figure (T)) and substitution (Figure TT) opera-
tions. Implementation details of rewrite rules are provided in Appendix B.2
Symbolic Regression (SR) posits that experimental data generated by underlying closed- form expression, an assumption that is widely adopted across the sciences (Ma et al. (022). . Given dataset D {(x;, y:)) the goal is find an optimal expression 6 that minimizes the loss:
1
Σ l(((xx 3).
arg min @ N
where function measures the discrepancy between the prediction o(x;, c) and the ground truth ye- The coefficients с in é are typically optimized on the training data D using numerical optimizers such as BFGS (Fletcher 2000). This problem NP-hard (Virgolin & Pissis 2022). posing major challenge for SK algorithms. Recent efforts to mitigate this challenge are reviewed in Section
3 METHODOLOGY
3.1 EGG: EQUALITY GRAPH FOR GRAMMAR-BASH SYMBOLIC EXPRESSION
Enumerating all equivalent variants of symbolic expression is combinatorially expensive. Storing these variants explicitly is time-consuming and memory-inefficieee To mitigate this scalability chal- lenge, we adopt the recently proposed Equality graph (i.e, E-graph) data structure (Willsey al., 2021 Waldmann et al. 2002]. which compactly represents the set of equivalent expressions by shar- ing common subexpressions. We extend E-graphs to support grammar- -based symbolic expressions, noted as EGG, facilitating unified integration with symbolic regression algorithms.
Definition, An e-graph consists of collection of equivalence classes, called e-classes. Each e-class contains set of e-nodes representing symbolically equivalent sub- sub-expressions (Willsey et al. (021)) Each e-node encodes a mathematical operation and references a list of child e-classes corresponding to its operands. Edges always point from an e-node to e-classes.
Figure d shows an example e-graph. The hight-hig part is an e-class (in dashed box) containing two e-nodes (in solid boxes): A + log(A) and A + A + A. The two e-nodes represent logarithmic operation and addition, respectively. The e-node A - log(A) has single outgoing edge to its child e-class A - A x A, because log(-) operator is unary.
Construction. this work, an e-graph is initialized with a sequence of production rules, repre- senting an input expression. Each rewrite rule (as defined in section ( is applied by matching its left-hand side (LHS) pattern against the current e-graph, which involves traversing all e-classes to identify subexpressions that match LHS. For every successful match, new e-classes and e-nodes corresponding to the right-hand side (RHS) of the rule are created. A merge operation is applied to incorporate the new e-class with the matched e-class, thereby preserving the structure of known equivalences. This process, known as equality saturation, iteratively applies pattern matching and merging until either further rules
be applied a maximum number of iterations is reached.
Example 3.1. Figure shows an example e-graph construction with the rewrite rule log(a x b) ~9 log(a) + log(b), where and b are placeholders for arbitrary -ub-expressions. The e-graph is ini- tialized with an expression = log(={x²) in Figure [a... The LHS is matched against the color- highlighted e-classes in Figure [b) with of and b 2². The substitution step constructs
3

---

Published as a conference paper at ICLR 2026
logta
log(A
log(4)
+++
log(A)
A
AAA
AXA
4XX
log(A)
log(A)
AXA
log(A
log(A)
(4)
(a) Initialization.
(b) Matching.
(c) Substitution.
(d) Merging.
Figure 1: Example e-graph construction by applying rewrite rule log(a b) log(a) + log(b) to an e-graph representing the expression log(zfa²)) (a) The initialized e-graph consists e-classes (dashed boxes), each containing equivalent e-nodes (solid boxes). Edges connect e-nodes to their child e-classes. (b) The matching step identifies the e-nodes that match the LHS of the rule. (c) The substitution step adds e-classes and edges corresponding to the RHS the e-graph. (d) The merging step consolidates equivalent e-classes. See Example 3.2 for a detailed explanation.
e-classes and e-nodes that represent RHS, which are color-highlighted in Figure [c). The newly created e-class is merged with the matched e-class in Figure [d). The resulting e-graph represents two equivalent expressions: log(x}=²) and log(xi) + (og(zz). The e-graph in Figure [ saves memory by storing two sub-expressions z and 2 only once. Additional EGG visualizations on more complex expressions are provided in Appendix D.1
Extraction. After the e-graph is saturated, extraction step is performed to obtain K representative expressions (Goharshady et al. 2024). Because an e-graph encodes up to an exponential number of equivalent expressions, exhaustive enumeration is computationally infeasible. We therefore adopt two practical strategies: (1) cost- cost-based extraction, which selects several simplified expressions by minimizing user-defined cost function over operators and variables (de França & Kronherger) 2025). and (2) random-walk sampling, which generates a batch of expressions by stochastically traversing the e-graph. detailed explanation of extraction provided in Appendix
Interaction with SR algorithms. Prior research has leveraged e-graphs, based on the principle of Occam's 's razor, to obtain the most simplified and least-cost equivalent form (de Franca & Kro- nberger 2025). In this study, however. equivalence-awan learning (detailed in Section 3.2) is en- couraged by explicitly exposing SR algorithms to an extra subset of equivalent variants.
The EGG module is primarily used to generate subset of equivalent variants-i.e. expressions that represent the same mathematical function under a set of math identities. Given a sequence of produc- produc tion rules predicted by an SR algorithm, EGG constructs the e-graph and then performs extraction (via random-walk sampling) to return a batch of equivalent sequences. EGG implemented for grammar-bused symbolic expressions in pure Python, following the original e-graph paper (Willsey)
ct al. 202T). Implementation of EGG is provided Appendix B
3.2 EMBEDDING SYMBOLIC EQUIVALENCE INTO SYMBOLIC REGRESSION VIA EGG
Embedding EGG into Monte Carlo Tree Search. MCTS (un al. 2023 Ruan al. 2025)
maintains a search tree to explore an optimal sequence of decisions, here corresponding to a se- quence of production rules. Each edge labeled with production rule, and each node is labeled by the sequence of edge labels from the root. By the grammar definition, this node label corresponds to partially completed (or complete) expression.
During learning, MCTS iterates the following four steps (Brence et al. 202I): (1) Selection. Starting from the root node, successively select the edge of node (noted as a) with the highest Upper Confidence Bound for Trees (UCT) (Kocsis & Szepesvári 2006):
(2) where reward(s, a) is the average reward obtained by selecting edge a at node s, visits(s) is the number of visits to node and visits(s, a) is the number of times rule has been selected at node The constant (often set to v2 in theory) balances between exploration and exploitation. (2)
UCT a) reward(s, + (st.l/oovviiiits))vvvsssis
4

---

Published as a conference paper at ICLR 2026
-+(a) (a) Selection
(b) Expansion
(c) Simulation
(d) EGG-based Propagation
~> log(A)
log(4)
log(A)
log(A)
log(A)
+
log(A) +
log(A A)
log(A x
log(/
A A AXA
log(A) log(A)
log(A A)
log(2, xA)
+ xq
logúr, A)
log(x,) + log(A)
log(x, x.))
reward-0.8, visits- rewards=0.8, visits+=10
Figure 2: The EGG-MCTS pipeline consists of: (a) Starting at the root node, MCTS selects the child with the highest UCT score (in equation[2 2 until reaching leaf. (b) The selected leaf produces new child nodes by applying all applicable production rules. (c) For each child, run several rollouts to complete the expression template by sampling additional rules. The resulting expressions are fitted to the data to estimate their coefficients. (d) Rewards and visit counts from the selected leaf are back-prop prop-prop to the root. In addition to updating the selected path (blue), we also update those equivalent paths (orange) identified by our EGG module.
Expansion. When reaching a leaf node s, expand the search tree by generating its child nodes using all production rules. (3) Simulation. Perform several rollouts for each child to evaluate the average reward of node s. In each rollout, generate valid expression ø by randomly applying production rules until completion. Then, estimate the optimal coefficients in & and evaluate its reward. A common reward function 1/(1 + NMSE())). (4) Backpropagation. Update the reward estimates and visit counts for node and all its parents up to the root node. After the final iteration, MCTS returns the expression with the highest reward encountered during training as its prediction.
EGG-based Backpropagation. Our backpropagation strategy is motivated by transposition ta- bles (Childs et al., 2008) Leurent & Maillard 2020), which use a table to cache identical nodes (e.g., via hashing) in search tree and share their statistics during training. This mechanism propa- gates information as if the search had visited all identical nodes. Such tables are effective domains such Go and Hearthstone, where nodes that identical can be easily determined. In symbolic regression, however, two nodes may be identical only up to symbolic equivalence induced by rewrite rules, so a hashing-based transposition table is not directly applicable. To address this, EGG used to identify equivalent paths and nodes.
Coneretely, the represenprnn partially completed ixpression--s first converted into an initial e-graph. The e-graph is then saturated by repeatedly applying the set of rewrite rules. From this saturated e-graph, we sample several distinct equivalent sequences and check if the tree contains corresponding paths. If so, we apply backpropagation to all of them. In this way, we avoid redundant exploration by sharing the rewards and visit counts of equivalent paths and nodes.
This modification in EGG-MCTS changes the interpretation of equation (2). visits(s) no longer counts how many times the specific tree node s appears on simulated paths; instead, counts visits to any representative within the associated equivalence class. Conceptually, this mirrors the trans- position table that shares statistics across identical tree nodes.
In Theorem we show that EGG-MCTS accelerates learning by reducing the search tree's ef- fective branching factor relative to standard MCTS. It prevents redundant exploration of equivalent subtrees and concentrates sampling genuinely distinct (and potentially near-optimal) paths. Example 3.2. Figure 2 shows an example execution pipeline of EGG-MCTS. Specifically, Fig- ure 2 d) highlights
distinct root-to-node paths in the search tree:
Path 1: (A- log A), + A A, - m1);
Node 81: log(æ; A).
Path 2: (A+44 A, 4 + log(A), zi log(A)),
Node 82: log(a;) log(A).
Here, each path is sequence of edge labels from the root to the leaf node s,. Based on the grammar definition in section 2 node 8ı corresponds to the partially completed expression log(æ; x A), while node 82 represents log(x:) + log(A). The nodes equivalent under the rewrite rule
5

---

Published as a conference paper at ICLR 2026
log(ab) ~ log log b. Consequently, their rewards, estimating the averaged goodness-of of-fiit of expressions on the training data, should be approximately equal:
reward(s1, a) reward(s2.a),
Va E the set of production rules
Standard MCTS would explore the subtrees rooted at 81 and 52 independently, because it is unaware of their equivalence. This results in redundant computation and slows down learning. With EGG- MCTS, the visit counts and reward estimates of both paths are updated simultaneously, eliminating the need for extra iterations on the orange leaf in Figure dd). See Example B.I for the case of other and a/ rewrite rules, e.g., sin=(a) + (a)
Embedding EGG into Deep Reinforcement I. Learning. DRL typically employs a neural sequential decoder to predict expression by sampling sequence of production rules from the model dis- tribution. The reward assigns higher values to expressions that better fit the training data (Petersen et al. 2021 Landajuela et al. 2022 Jiang et al. 2024 The pipeline of DRL and EGG-DRL is presented in Figure
At every step, the sequential decoder samples the next production rule from distribution over all available rules, conditioned on the previously generated sequence. The decoder thus induces a distribution (T) over the rule sequence т. The reward function is typically defined reward(r) 1/(1 + NMSE(()). where Φ is the expression constructed by following grammar definition (in section 2 The learning objective is to maximize the expected reward of generated expressions on the training data: Er~re [r) whose gradient is Er-p, [reward(r) logpe(T)] In practice, the gradient approximated via Monte Carlo. Sampling N sequences (T...... TN from the decoder, the policy gradient estimator computes:
N
(
=
Σ (reward(T.)) V log (o;;), N
(3)
where b is bascline used to reduce variance (Weaver & Tao 2001). Recent work (Petersen et al. 2021 further proposes using a top-quantile subset of samples, rather than the sample mean.
EGG-based Policy Gradient Estimator: For each sampled sequence т,, construct e-graph that compactly encodes all of its equivalent expressions. From this e-graph, we sample K equivalent sequences {T,
(2)
(K) We then revise the policy-gradee golicy-gradient estimator as
......7 Ti
Jogg (
(reward(T)) - b') Vo N
-b') log
Σ po(T!!t)
(4)
where Ti (1) is the original sequence Tr and is the corresponding baseline, and Σ 1= (T
aggregates the probabilities of all equivalent sequences that share the same reward. In Theorem 3.2
we show that EGG improves DRL training by yielding a lower-variance gradient estimator than
standard DRL (Petersen al.
2021
Embed EGG into Lange-Languuae Model. LLM is applied to search for optimal symbolic expres- sions with prompt tuning (Merler al. 2024 Shojace et al. 2025). The procedure consists of three key steps: (1) Hypothesis Generation: The LLM generates multiple candidate expressions based on a prompt describing the problem background and the definitions of each variable. (2) RaivvDriven Evaluation: Each candidate expression is evaluated based on its fitness on the training dataset. (3) Experience Management: In subsequent iterations, the LLM receives feedback in the form of pre- viously predicted expressions and their corresponding fitness scores, allowing it to refine future generations. High-fitness expressions are retained and updated over multiple rounds of iteration.
EGG-hased Feedback Prompt. Since LLMs typically generate Python functions rather than symbolic expressions directly, we introduce a wrapper that parses the generated Python code into symbolic expressions. These expressions are then transformed into e-graphs using set of rewrite rules. From each e-graph, we extract semantically equivalent expressions and summarize them into similar feedback message, which is incorporated into the prompt for the next round. This augmentation enables the LLM to observe a richer set of functionally equivalent expressions, potentially improving the quality and accuracy of predictions in future iterations.

---

Published as a conference paper at ICLR 2026
3.3 CONNECTION TO EXISTING METHODS
Prior work has explored alternative expression representations based on layer-wise symbolic net- works (SymNet) (Sahoo al.) 2018: Li et al., 2024), which are not directly compatible with our grammar- based formulation. Recent studies on SymNet further show that many learned coefficients can be aggregated or merged (Wu al. 2024). Extending this notion of coefficient equivalence to sub-expression equivalence within SymNet remains an interesting open problem.
For DRL-based approaches. several extensions of the original method (Petersen et al., 2021) have been proposed, including (Mundhenk et al., [202T] Landajuela et al.] 2022). An important open question whether symbolic-euuivalnnce can be integrated into these extensions in a compatible and effective manner, and whether doing so can further improve overall performance.
Finally, Kamienny al. (002)): [Shojaee et al. (202)) encode data directly with a Transformer and predict an expression traversal sequence end-to to- under cross-entropy objective. A natural way to incorporate EGG is to use during training to generate multiple equivalent, correct target se- quences. How to best leverage EGG at inference time, however, remains open problem.
3.4 THEORETICAL JUSTIFICATION ON EGG-SR ACCELERATING LEARNING
Theorem 3.1 shows that EGG-MCTS achieves asymptotically tighter regret bound than standard MCTS, as the effective branching factor satisfies Kec S K. Intuitively, by identifying symbolically equivalent nodes and sharing their search statistics, EGG prevents redundant exploration of equiva- lent subtrees and concentrates sampling on genuinely distinct (and potentially near-optimal) paths. After many iterations, EGG-MCTS concentrates more quickly on the near-optimal region of the search space, which is captured by smaller effective branching factor.
Also, Theorem 3.2 shows that embedding EGG into DRL produces unbiased gradient estimator while strictly reducing gradient variance, ensuring more stable and efficient policy updates.
Theorem 3.1. Consider embedding EGG into the MCTS framework. Given Definitions [ and (in appendix), let n denote the total number of learning iterations, 7 E (0, 1) the discount factor of the corresponding Markov decision process, k the near-optimal branching factor of standard MCTS, and Koo the corresponding branching factor of EGG-MCTS. Then the regret bounds satisfy
regret(n) ①
log(1/>>
regret egg (n) Ö
lox(1/T)
Jog
with Keo K.
Proof Sketch. Leurent & Maillard (2020) analyze MCTS a graph obtained by merging identical
tree nodes and sharing their statistics. Their analysis unrolls the graph into a tree that contains all graph-traversable paths. The search tree EGG-MCTS behaves identically the unrolled tree. Our final results follow their regret analysis on the unrolled tree. A detailed proof is in Appendix
Theorem 3.2. Consider embedding EGG into the DRL framework. Let T Pg denote trajectories sampled from the distribution Ps. and consider the two estimators defined in Equations 3 and (4). (I) Unbiasedness. The expectation of the standard estimator g(0) equals that of the EGG-based estimator Gagg (0): Er-po [9(0) = Er-pp Soge [0)] (2) Variance Reduction. The variance of the proposed estimator is smaller than that of the standard estimator:
War-~pa Iagg (0)] < Var [o(0)]
Proof Sketch. For (l), unbiasedness can be obtained by expanding the definitions of g()) and Begs (8). For (2), the key observation is that EGG groups together equivalent trajectories that share the same reward. Averaging over sequences with identical rewards reduces within-group variability, which yields smaller variance. A full proof is provided in Appendix A.3
4 RELATED WORKS
Knowledge-G Guided Scientific Discovery. Recent efforts have explored incorporating physical and domain-specific knowledge to accelerate symbolic discovery. Al-Feynman (Udrescu & Tegmark 2020 Udrescu et al. 2020 Keren et al. 2023 Cornelio al. 2023) constrained the search space to

---

Published as a conference paper at ICLR 2026
expressions that exhibit compositionality. additivity, and generalized symmetry. Similarly, Tenachi jet al. (002) encoded physical unit constraints into learning to eliminate physically impossible solu- tions. Other works further constrained the search space by integrating user-specified hypotheses and prior knowledge, offering a guided approach to symbolic regression (Bendinelli et al. 2023 Kami-
enny 2023 Shojaee et al.) 2025 Taskin et al. 2026: Zhang al., 2025). Our EGG-SR presents new idea in knowledge-guided learning that is orthogonal to existing approaches.
Symbolic Equivalence is a central concept in program synthesis and mathematical reason- ing (Willsey et al.] 202T). In SQL query optimization, it rewrites queries into time-efficient forms (Barbulescu et al. 2024). In hardware synthesis. supports cost-aware rewrites such as optimized matrix multiplication (Ustun et al. (2022). In formal methods, it accelerates automated theorem proving through normalization and equivalence checking (Kurashige al., 2024). In math- ematical reasoning, it is used to generate paraphrases of math expressions (Zheng et al. 2025
In symbolic regression, de França & Kronberger (2023) leverages e-graphs to mitigate over- parameterization in candidate expressions. de França & Kronberger (2055) de Franca & Kronberger (2255) further incorporates e-graphs into genetic programming (GP) to detect and eliminate redun- dant individuals, encouraging GP to explore novel expressions. A recent follow-up work (de França & Kronberger 2025) provides a richer API for interacting with GP. This study advances existing work by offering unified interface for encoding known mathematical equalities e-graphs, abling equivalence-awant learning across several modern symbolic regression algorithms, together with theoretical guarantees.
Equivalence-aware Learning. Equivalence and symmetry have long been recognized as crucial for improving efficiency in search and learning. In MCTS, transposition tables exploit equivalence by merging nodes that represent the same underlying state, avoiding redundant rollouts and accel- erating convergence (Childs al. 2008). More recent extensions explicitly leverage symmetries to prune symmetric branches of the search space (Saffidine et al. 2012; Leurent & Maillard 2020). In reinforcement learning, symmetries in the state-action space have been used accelerate con- vergence (Grimm et al., 2020). LLMs also benefit from equiaalence-wwarenee particularly in code generation (Sharma & David 2025).
EXPERIMENTS
We show that (1) EGG enhances existing learning algorithms discovering expressions with smaller Normalized MSEs. (2) In case studies, EGG consistently exhibits both time and space efficiency. The detailed experimental setups and datasets used in each comparison, are provided in Appendix
5.1 OVERALL BENCHIARRS
Impact of EGG MCTS. We conduct two analyses evaluate the impact of integrating EGG into standard MCTS: (1) the median normalized MSE of the Topk (K = 10) expressions identified the end of training, and (2) The growth of the search tree, measured by the number of explored nodes over learning iterations.
Table 1 shows that EGG-MCTS con- sistently discovers expressions with lower normalized quantile scores compared to standard MCTS. The dataset selected from Jiang & Xue (2023) as the expressions con- tain sin, cos operators, which contain many symbolic-equivalenne variants.
Size of Search Tree
1250
MCTS
EGG-MCTS (oius)
Estimated objective
1000
600
250
EGG-DRL (OILES)
DRL
0:
200
400
25
7.
195
Figure Left) illustrates that EGG- MCTS maintains a broader and deeper search tree, indicating ex- ploration of larger and more di- verse search space. Across vari- datasets, augmenting MCTS with
Learning Iterations
Learning Ineration
On the "sincos(3,2,29" dataset, show (left) search tree size over learning iterations for MCTS and EGG- MCTS, and also (right) empirical mean and standard devi- ation of the estimated quantity for DRL and EGG-DRL.
Figure 3:
8

---

Published as a conference paper at ICLR 2026
Table I: On Trigonometric datasets, median NMSE values of the best-predicted expressions found by all the algorithms. The 3-tuples at the top (:::-) indicate the number of free variables, singular terms, and cross terms in the ground-trum truth expressions generating the dataset. The set of operators is {sin, cos,
}. The best result in each column is underlined.
Noiseless Setting
Noisy Setting
(2, 1.
(3, 2, 2)
(4, 4,
(5.5.5) 5)
(2, 1, 1)
(3.2,
(4,4. 6)
(5. 5,
EGG-MTCS
< <1E-6
<IE-6
0.006
0.009
0.005
0.012
0.091
0.121
MTCS
0.006
0.033
0.144
0.147
0.015
0.007
0.138
0.150
EGG-DRL
0.020
0.161
2.381
2.168
0.07
0.35
5.09
5.67
DRL
0.030
0.277
2.990
2.903
0.09
0.44
2.46
14.44
Table 2: Comparison LLM, and EGG-LLM models on different scientific benchmark problems measured by the NMSE metric. The best result in each column is underlined.
Oscillation I
Oscillation
Bacterial growth
Stress-Strain
IID4
OOD,
IIDI
OOD
IIDI,
OODJ
IIDI
OODJ
EGG-LLM (GPT3.5)
<IE-6
0.0004
<IE-6
<1E-6
0.0121
0.0198
0.0202
0.0419
LLM-SR (GPT-3.5)
< IE-6
0.0005
< IE-6
3.81E-5
0.0214
0.0264
0.0210
0.0516
EGG-LLM (Mistral)
<E-6
0.0002
0.0021
0.0114
0.0101
0.0107
0.0133
0.0754
LLM-SR (Mistral)
1E-6
0.0002
0.0030
0.0291
0.0026
0.0037
0.0162
0.0946
EGG improves symbolic expression accuracy. This improvement is primarily due to the effective- ness of our rewrite rules, which cover rich set of trigonometric identities and enable efficient exploration of symbolic variants in trigonometric expression spaces.
Impact of EGG on DRL. Table reports the median NMSE values of the best-predicted expres- sions discovered by EGG-DRL and standard DRL, under identical experiment settings. Expressions returned by EGG-DRL achieve smaller NMSE value on noiseless and noisy settings. It shows that embedding EGG into DRL helps to discover expressions with better NMSE. In (i plot the estimated objective, defined as R(T;) log (og)) where each trajectory i; is sampled from the sequential decoder with probability po (T:) (see Equation 3). We plot the empirical mean and standard deviation of this objective over training iterations. The observed reduction in variance is primarily due to the symbolic variants generated via the e-graph, which enable averaging over multiple equivalent expressions and thus yield more stable gradients.
we
Impact of EGG on LLM. Following the dataset and experimental setup from the original pa- per (Shojaee et al. 2025). we summarize the results in Table 2 The result of LLM-SR directly uses the reported result in Shojace et al. (2025). The results show that integrating EGG enables the L.M to discover higher-quality expressions under the same experimental conditions, as with richer feedback prompts that incorporate equivalent expressions generated by EGG.
5.2
CASE ANALYSIS
Space Efficiency of EGG. We evaluate the space efficiency of the e-graph representation com- parison to a traditional array-based approach. We benchmark the memory consumption of storing all equivalent variants of input expressions under two settings: (1) o log(æ, X x... x,,), using the -r,) using the trigonometric identity sin(a + b) sin(a) cos(b) + sin(b) cos(a). Both settings yield 2 equivalent variants. The array-based method explicitly stores each expression variant as unique sequence, leading to exponential memory growth. contrast, the e-graph compactly encodes multiple equivalent ex- pressions by sharing common sub-expressions.
logarithmic identity log(ab) ~ log a +og log b, and (2) ø =in +..
Figure 4 reports memory consumption as a function the number of variables n. The results show that e-graphs use substantially less memory than the array-based representation. We also provide additional visualizations of the constructed e-graphs for n = 2, 3, 4: case (1) in Appendix Figure [4] and case (2) in Appendix Figure [5] It visualizes two representative e-graphs, illustrating how shared sub-expressions are stored once and reused across many variants, which underlies the space efficiency of EGG.

---

Published as a conference paper at ICLR 2026
Draw sequeenoce from decoder
BGG construction Policy gradieal update
Array-based EGG Module
165
Array-hased EGG Module
Fit expressions coellicients
Menory Cauge (KD)
Mensory Usago (K0))
Time Consunytion (ms))
30
201
38.
uP
#lnput Variables (n)
#lapal Variables (x1)
20
30
Learning Iteration
Learning Iteration
less memory than the array-based approach for two settings: (Left)
Figure 4: EGG
Figure 5: The EGG module is time efficient and introduces negligible time overhead, com- pared with four main computations in DRL. Left: LSTM. Right: Decoder-only Transformer.
log (21 x... [n.) rewritten using log(ab) log +og b. (Right) sin (21 +... + zn) rewrit-
ten using sin(a + b) mn sin a cos + sin cos
Time Efficiency of EGG with DRL. As shown in Figure 5 we benchmark the runtime of the four main computations EGG-DRL on the selected "sincos(3.2,2)" dataset: (1) sampling sequences of rules from the sequential decoder, (2) fitting coefficients in symbolic expressions the training data, (3) generating equivalent expressions via EGG, and (4) computing the loss, gradients, and updating the neural network parameters. We consider settings for the sequential decoder: 3-layer LSTM with hidden dimension 128, and decoder-only Transformer with 6 attention heads and hidden dimension 128.
The EGG module contributes minimal computational overhead relative to more expensive steps such coefficient fitting and neural network parameter updates. The runtime of EGG depends on the size of the rewrite-rule set. As more rules are included, the e-graphs maintain increasingly large sets of equivalent expressions. This highlights the practicality of incorporating EGG into DRL-based symbolic regression frameworks.
Additional Visualizations of E-graph Construction. To further demonstrate the effectiveness of the proposed EGG module, we present additional visualizations of e-graph construction generated with our API on selected complex expressions from the Feynman dataset (Udrescu & Tegmark 2020). Each visualization highlights different set of rewrite rules (see Appendix D.2). These examples further illustrate that EGG can simplify and transform complex scientific expressions in practical settings.
CONCLUSION
In this paper, we introduced EGG-SR, a unified framework that integrates symbolic equivalence into symbolic regression through equality graphs (e-graphs) to accelerate the discovery of optimal ex- pressions. Our theoretical analysis establishes the advantages of EGG-MCTS over standard MCTS and EGG-DRL over conventional DRL algorithms. Extensive experiments further demonstrate that EGG consistently enhances the ability of existing methods to uncover high-quality governing equa- tions from experimental data. Currently, many scientific publications use Ga-based symbolic regres- sion due to its ease of use. In future work, we plan to extend more sophisticated solver, EGG-SR, to scientifically grounded problem settings, improving the community's s computational toolkit.
Ethics Statement. All authors have read and commit to adhering to the ICLR Code of Ethics. This work uses only publicly available datasets and open-source models, and does not involve human subjects or human subjects data.
Reproducibility Statement. Appendix B describes the proposed EGG module, and the Ap- pendix A.3 and A.2 include detailed proots of theoretical justification. Appendix gives the ex- perimental setting. Appendix[Djcoleect extra experimental results.
Acknowledgements. We thank the reviewers for their constructive feedback, well as Fabricio Olivetti de França for his public comments. This research was supported by TACC (CCR25054) and the U.S. Department of Energy, Office of Fusion Energy Sciences (DF-SC0024583).
10

---

Published as a conference paper at ICLR 2026
REFERENCES
Miltiadis Allamanis, Pankajan Chanthirasegaran, Pushmeet Kohli, and Charles Sutton. Learning continuous semantic representations of symbolic expressions. In ICML, volume 70, pp. 80-88. PMLR, 2017.
George-Octir OrtgeeOOttvvin Barbulescu, Taiyi Wang, Zak Singh, and Eiko Yoneki. Learned graph rewrit- ing with equality saturation: A new paradigm in relational query rewrite and beyond. CoRR, abs/2407. 110000.127994 12794, 2024.
Zachary Bastiani, Robert M Kirby, Jacob Hochhalter, and Shandian Zhe. Diffusion-based symbolic regression. arXiv preprint arXiv:2505. 24776, 2025.
Tommaso Bendinelli, Luca Biggio, and Pierre-Alexandee Kamienny. Controllable neural symbolic regression. In ICML, volume 202, pp. 2063-2077. PMLR, 2023.
Jure Brence, Ljupco Todorovski. and Saso Dzeroski. Probabilistic grammars for equation discovery. Knowl. Based Syst., 224:107077 2021.
George Casella and Christian P. Robert. Rao-blackwellisation of sampling schemes. Biometrika, 83 (1):81-94, 1996.
William G. La Cava, Patryk Orzechowski, Bogdan Burlacu, Fabrício Olivetti de França, Marco Virgolin, Ying Jin, Michael Kommenda, and Jason H. Moore. Contemporary symbolic regression methods and their relative performance. In NeurlPS Dalasets and Benchmarks, volume 1, 2021.
Benjamin E. Childs, James H. Brodeur, and Levente Kocsis. Transpositions and move groups in monte carlo tree search. In CIG, pp. 389-395, IEEE, 2008.
Junyoung Chung, Caglar Gulcehre, KyungHyun Cho, and Yoshua Bengio. Empirical evaluation of gated recurrent neural networks on sequence modeling. arXiv preprint arXiv:1412.3555, 2014.
Cristina Cornelio, Sanjeeb Dash, Vernon Austel, Tyler Josephson, Joao Goncalves, Kenneth Clarkson, Nimrod Megiddo, Bachir HI Khadir, and Lior Horesh. Combining data and theory for derivable scientific discovery with ai-descartes. Nature Communications, 14(1):1777, 2023.
Ryan Cory-Wright, Cristina Cornelio, Sanjeeb Dash, Bachir Khadir, and Lior Horesh. Evolving scientific discovery by unifying data and background knowledge with ai hilbert. Nature Commu- nications, 15(1):5922, 2024.
Fabrício Olivetti de França and Gabriel Kronberger. Reducing overparameterizzaton of symbolic regression models with equality saturation. In GECCO, pp. 1064-1172. ACM, 2023.
Fabrício Olivetti de França and Gabriel Kronberger. Improving genetic programming for symbolic regression with equality graphs. In GECCO, pp. 989-998. ACM, 2025.
Fabricio Olivetti de Franca and Gabriel Kronberger. Equality graph assisted symbolic regression.
arXiv preprint arXiv:2511.01009 2025.
Fabricio Olivetti de França and Gabriel Kronberger. reggression: an interactive and agnostic tool for the exploration of symbolic regression models. In GECCO, pp. 42. Association for Computing Machinery, 2025.
Wei Deng, Qi Feng. Georgios Karagiannis, Guang Lin, and Faming Liang. Accelerating conver- gence of replica exchange stochastic gradient MCMC via variance reduction. In ICLR. OpenRe- view.net, 2021.
Roger Fletcher. Practical methods of optimization. John Wiley & Sons, 2000.
Steven Ganzert, Josef Guttmann, Daniel Steinmann, and Stefan Kramer. Equation discovery for model identification in respiratory mechanics of the mechanically ventilated human lung, In Discovery Science, volume 6332, pp. 296-310. Springer,2011
Amir Kafshdar Goharshady, Chun Kit Lam. and Lionel Parreaux. Fast and optimal extraction for sparse equality graphs. Proc. ACM Program, Lang., 3000PSLA2):2551-255 2024.

---

Published as a conference paper at ICLR 2026
Klaus Greff, Rupesh K Srivastava, Jan Koutník, Bas R Steunebrink, and Jürgen Schmidhuber. Lstm: A search space odyssey. IEEE transactions on neural networks and learning systems, 28(10): 2222,223,, 2016.
Christopher Grimm, André Barreto, Satinder Singh, and David Silver. The value equivalence prin- ciple for model-based reinforcement learning. In NearIPS, volume 33, pp. 5541-5352, 2020.
Gérard Huet and Derek C Oppen. Equations and rewrite rules: survey. Formal Language Theory, pp. 349-405, 1980.
Nan Jiang and Yexiang Xue. Symbolic regression via control variable genetic programming. In ECML/PKDD, pp. 178-195. Springer, 2023.
Nan Jiang, Md. Nasim, and Yexiang Xue. Vertical symbolic regression via deep policy gradient. In IJCAI, pp. 5891-5899. ijcai.org, 2024.
Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In NeurlPS, pp. 315-323, 2013.
Paul Kahlmeyer, Joachim Giesen, Michael Habeck, and Henrik Voigt. Scaling up unbiased search- based symbolic regression. In IJCAI, pp. 4264 4272. ijcai.org, 2024.
Pierre-Alexandre Kamienny. Efficient adaptation of reinforcement learning agents: from model-free exploration symbolic world models. Theses, Sorbonne Université, October 2023.
-ecre-Ale Kamienny, Stéphane Ascoli, Guillaume Lample, and François Charton. End-to- end symbolic regression with transformers. In NewrlPS, volume 35, pp. 10269-10281, 2022.
Pierre-Alexandre Kamienny, Guillaume Lample, Sylvain Lamprier, and Marco Virgolin. Deep gen- erative symbolic regression with wonte-carlo-tree-saard In ICML, volume 202. PMLR, 2023.
Liron Simon Keren, Alex Liberzon, and Teddy Lazebnik. A computational framework for physics- informed symbolic regression with straightforward integration of domain knowledge. Scientific Reports, 13(1):1249, 2023.
Levente Kocsis and Csaba Szepesvári. Bandit based monte-carlo planning. In ECML, volume 4212 of Lecture Notes in Computer Science, pp. 282-293. Springer, 2006.
Cole Kurashige, Ruyi Ji, Aditya Giridharan, Mark Barbone, Daniel Noor, Shachar Itzhaky, Ranjit Jhala, and Nadia Polikarpova. Cclemma: E-graph guided lemma discovery for inductive equa- tional proofs. Proc. ACM Program. Lang., (ICCF)):8188444 2024.
Kyle J. LaFollette, Janni Yuval, Roey Schurr, David Melnikoff, and Amit Goldenberg. Data-driven equation discovery reveals nonlinear reinforcement learning in humans. Proc. Natl. Acad. Sci., 122(31), 2025.
Mikel Landajuela, Chak Shing Lee, Jiachen Yang, Ruben Glatt, Cláudio P. Santiago, Ignacio Ar- avena, Terrell Nathan Mundhenk, Garrett Mulcahy, and Brenden K. Petersen. A unified frame- work for deep symbolic regression. In NeurIPS, volume 35, pp. 33985-33998, 2022.
Edouard Leurent and Odalric-Ambrym Maillard, Monte-carlo graph search: the value of merging similar states. In ACMI,, volume 129, pp. 577-592. PMIR, 2020.
Wenqiang LI, Weijun Li, Lina Yu, Min Wu, Linjun Sun, Jingyi Liu, Yanjie Li, Shu Wei, Yusong Deng, and Meilan Hao. neural-guided dynamic symbolic network for exploring mathematical expressions from data. In ICML,, volume 235, pp. 28222-28242 PMLR, 2024.
He Ma, Arunachalam Narayanaswamy, Patrick Riley, and Li Li. Evolving symbolic density func- tionals. Science Advances, 8(36), 2022.
Matteo Merler, Katsiaryna Haitsiukevich, Nicola Dainese, and Pekka Marttinen. In-context sym-
bolic regression: Leveraging large language models for function discovery. In ACL (Student Research Workshop), pp. 589-606. Association for Computational Linguistics, 2024.
12

---

Published as a conference paper at ICLR 2026
T. Nathan Mundhenk, Mikel Landajuela, Ruben Glatt, Claudio P. Santiago, Daniel M. Faissol, and Brenden K. Petersen. Symbolic regression via neural-guided genetic programming population 2021.
seeding. In NewrlPS, volume 34, pp.
Rémi Munos. From bandits to monte-carlo tree search: The optimistic principle applied to opti- mization and planning. Found. Trends Mach. Learn., 7(1):1-12, 2014.
Nico JD Nagelkerke et al. A note on a general definition of the coefficient of determination. Biometrika, 78(3):691-692, 1991.
Chandrakana Nandi, Max Willsey, Amy Zhu, Yisu Remy Wang, Brett Saiki, Adam Anderson, Adri- ana Schulz, Dan Grossman, and Zachary Tatlock. Rewrite rule inference using equality saturation. Proc. ACM Program. Lang., 5(00PSLA):1-28. 2021.
Matteo Papini, Damiano Binaghi, Giuseppe Canonaco, Matteo Pirotta, and Marcello Restelli. Stochastic variance-reduced policy gradient. In ICML, volume 80, pp. 4023-4032. PMLR, 2018.
Brenden K. Petersen, Mikel Landajuela, T. Nathan Mundhenk, Cláudio Prata Santiago, Sookyung Kim, and Joanne Taery Kim. Deep symbolic regression: Recovering mathematical expressions from data via risk-seeking policy gradients. In ICLR, 2021.
Kai Ruan, Yilong Xu, Ze-Feng Gao, Yang Liu, Yike Guo, Ji-Rong Wen, and Hao Sun. Discovering physical laws with parallel symbolic enumeration. Nature Computational Science, pp. 1-14, 2025.
Abdallah Saffidine, Tristan Cazenave, and Jean Méhat. UCD: Upper confidence bound for rooted directed acyclic graphs. Knowl. Based Syst., 34:26-33, 2012.
Subham S. Sahoo, Christoph H. Lampert, and Georg Martius. Learning equations for extrapolation and control. In ICML, volume 80, pp. 4439 4447. PMLR, 2018.
Hojjat Salehinejad, Sharan Sankar, Joseph Barfett, Errol Colak, and Shahrokh Valaee. Recent ad- vances in recurrent neural networks. arXiv preprint
2017.
Michael Schmidt and Hod Lipson. Distilling free-form natural laws from experimental data. Science, 324(5923):81-88) 2009.
Saul Shanabrook. Egglog python: A pythonic library for e-graphs, 2024.
Arindam Sharma and Cristina David. Assessing correctness in Ilm-based code generation via un- certainty estimation. arXiv preprini 2rXiv:2502.11622 2025.
Parshin Shojace, Kazem Meidani, Amir Barati Farimani, and Chandan K. Reddy. -ranse planning for symbolic regression. In NeurIPS, volume 36, pp. 45907-45919, 2023.
Parshin Shojace, Kazem Meidani. Shashank Gupta, Amir Barati Farimani, and Chandan K. Reddy. LLM-SR: scientific equation discovery via programming with large language models. In ICLR, 2025.
Fangzheng Sun, Yang Liu, Jian-Xun Wang, and Hao Sun. Symbolic physics learner: Discovering governing equations via monte carlo tree search. In ICLR, 2023.
Bilge Taskin, Wenxiong Xie, and Teddy Lazebnik. Knowledge integration for physics-informed symbolic regression using pre-trained large language models. Scientific Reports, 16(1):1614, 2026.
Wassim Tenachi, Rodrigo Ibata, and Foivos Diakogiannis. Deep symbolic regression for physics guided by units constraints: toward the automated discovery of physical laws. The Astrophysical Journal, 959(2):99, 2023.
Ljupco Todorovski and Saso Dzeroski. Declarative bias in equation discovery. In ICML, pp. 376- 384. Morgan Kaufmann, 1997. ISBN 1558604863.
Silviu-Marian Udreseu and Max Tegmark. Ai feynman: A physics-inspired method for symbolic regression. Science Advances, 6(16), 2020.
13

---

Published as a conference paper at ICLR 2026
Silviu-Marian Udrescu, Andrew K. Tan, Jiahai Feng, Orisvaldo Neto, Tailin Wu, and Max Tegmark. AI feynman 2.0: Pareto-optimal symbolic regression exploiting graph modularity. In NeurIPS, volume 33, pp. 1870-4871, 2020.
Ecenur Ustun, Ismail San, Jiaqi Yin, Cunxi Yu, and Zhiru Zhang. Impress: Large integer multipli- cation expression rewriting for FPGA HLS. In FCCM, pp. 1-10. IEEE, 2022.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. NeurlPS, volume 30, pp- 5998-6008, 2017.
Marco Virgolin and Solon P Pissis. Symbolie regression is NP-hard. TMLR, 2022. ISSN 2835-8856.
Uwe Waldmann, Sophie Tourret, Simon Robillard, and Jasmin Blanchette. A comprehensive frame- work for saturation theorem proving. J. Autom. Reason., 66(4):499-539, 2022.
Lex Weaver and Nigel Tao. The optimal reward baseline for gradient-based reinforcement learning.
In UAI, pp. 538-545. Morgan Kaufmann, 2001.
Max Willsey, Chandrakana Nandi, Yisu Remy Wang, Oliver Flatt, Zachary Tatlock, and Pavel Panchekha. egg: Fast and extensible equality saturation. Proc. ACM Program. Lang., 5(POPL): 1-29, 2021.
Min Wu, Weijun Li, Lina Yu, Wengiang Li, Jingyi Liu, Yanjie Li, and Meilan Hao. Prunesymnet: A symbolic neural network and pruning algorithm for symbolic regression. CoRR, abs/2401.15103, 2024.
Ziyu Xiang, Kenna Ashen, Xiaofeng Qian, and Xiaoning Qian. Graph-based symbolic regression with invariance and constraint encoding. In NeurIPS, volume 37, 2025.
Rose Yu and Rui Wang. Learning dynamical systems from data: An introduction to physics-guided deep learning. Proc. Natl. Acad. Sci., 121(27). 2024.
Hengzhe Zhang, Qi Chen, Bing Xue, Wolfgang Banzhaf, and Mengjie Zhang. RAG-SR: retrieval-
augmented generation for neural symbolic regression. In ICLR. OpenReview.net, 2025.
Hongbo Zheng, Suyuan Wang, Neeraj Gangwar, and Nickvash Kani. E-gen: Leveraging e-graphs to improve continuous representations of symbolic expressions. NAACL (Long Papers), pp. 11772-11788 Association for Computational Linguistics, 2025.
Zeyu Zheng, Junhyuk Oh, and Satinder Singh. On learning intrinsic rewards for policy gradient methods. In NeurlPS, volume 31, pp.
2018
14

---

Published as a conference paper at ICLR 2026
CONTENTS
Introduction
Preliminaries
3
Methodology
3.1
EGG: Equality graph for Grammar-base based Symbolic Expression
3.2
Embedding Symbolic Equivalence into Symbolic Regression via EGG
3.3
Connection to Existing Methods
3.4
Theoretical Justification on EGG-SR Accelerating Learning
Related Works
Experiments
5.1
Overall Benchmarks
5.2
Case Analysis
6
Conclusion
10
Theoretical Justification
16
A.I Necessary Definitions of Markov Decision Process.
16
Proof of T'heore 3.1
17
A.3 Proof of Theorem 3.2
19
Implementation Details
21
B.1
Visualization of Expression Construction Context-free Grammar
B
2
Implementation of Rewrite Rules
21
B.3
Implementation of B-Graph
22
B.4
Implementation of EGG-embedded Symbolic Regression
25
Experiment Settings
30
Baselines and lyper-parameters Configurations
30
Evaluation Metrics
D
Extra Experimental Results
32
Visualization of EGG Construction
32
D.2 Additional Visualization for Selected Expressions in Feynman Datasel
37
15

---

Published as a conference paper at ICLR 2026
Use of Large Language Models (LLMs). A large language model (LLM) used exclusively for language refinement, including improvements grammar, clarity, and readability. All research ideas, methodology. analyses, and conclusions entirely the authors' own. The authors have thoroughly reviewed the final manuscript and accept full responsibility for its content.
Availability of EGG, Baselines and Dataset. Please find code repository
https//ggtaabbcc///jaaggaauugggp
EGG. The implementation of our EGG module http//uualttyygrpppeee
located in the folder
Datasets. The list of datasets used in our experiments can be found in attcaetss/occcenncc//eeeeeeee//e
Baselines. The implementations of several baseline algorithms,, along with our adapted versions, provided in the a algorithhe tomstth//// folder. Execution scripts for running each algorithm are also included.
We also provide README md file with instructions for installing the required Python packages and dependencies.
We summarize the supplementary material as follows: Section provides implementation details of the proposed EGG module. Sections [A.2 and A.3 present detailed theoretical analysis of the proposed method. presents additional experimental results.
the experimental setup and configurations. Finally, Section D
A THEORETICAL JUSTIFICATION
A.1 NECESSARY DEFINITIONS OF MARKOV DECISION PROCESS.
Consider deterministic, finite-horizon Markov Decision Process (MDP) with state space S and action space A. At each stage | E {0, 1,...,HH H 1} the agent observes its current state E S, selects action a A, and deterministically transitions to the next state 8141 f(s,, ax) while receiving a bounded reward T E [0, 1]. Let H denote the maximum planning horizon. The total discounted reward over the Hl-tep horizon is Σit 7'rr, where y E (0, 1) is the discount factor. For any vate-actioo pair (s, a). the state-action value is defined as:
Q(s,a) = max E E
N'r 80 Σ 1=0
00
where π is any policy and r = (3g, ap. $H-1, 11 is a trajectory generated by following т. Because the MDP is deterministic, the expectation is taken only over the agent's policy-induced action sequence. The optimal value of a state s is:
((s) = max Q(s. AEAA
Extensions to Symbolic Regression. our symbolic regression setting, a state corresponds to sequence of production rules that define partially constructed expression, equivalently, to the class of mathematical expressions that can be generated by completing this partially-complete expression. An action represents the selection of an available production rule that extends the current expression. The state space is the set all possible expressions of maximum length H, and the action space is the set of production rules.
We further provide concrete instantiations of this MDP for our Monte Carlo tree search implemen- tation in Appendix B34.1 and for deep reinforcement learning in Appendix B.4.2
16

---

Published as a conference paper at ICLR 2026
A.2 PROOF OF THEOREM 3.1
A.2.1 PROBLEM SETTINGS
A planning algorithm any procedure that, given model of the MDP and a limited computa- tional budget, uses simulated rollouts to estimate the value of available actions and to recommend single action for execution. Suppose that after n simulations of a planning algorithm, the agent recommends an action On to execute at the current state s. Its estimated value is Q(ss an), obtained by evaluating the discounted return that results from first taking On and then following an optimal policy for the remaining steps. The simple regret of this recommendation is
regret(n) == ((s) Q(,
which quantifies the loss in discounted return incurred by choosing an instead of the truly opti- mal action. A smaller regret(n) indicates that the planning algorithm used its limited simulation Budget more effectively identify a near-optimal action.
Planning involves selecting promising transitions to simulate at each iteration, in order to recom- mend actions that minimize regret regret(n). A popular strategy the optimism in the face of uncertainty (OFU) principle, which explores actions by maximizing an upper confidence bound on the value function V.
In the context of symbolic regression, the planning task is therefore sequentially apply production rules so as to construct a complete expression whose predicted outputs best match the target data, while respecting the grammar and structural constraints of the search space.
Definition 1 (Difficulty measure). The near-optimal branching factor of an MDP is defined as
R = limsup [T 1/h E [],
(6)
h0000
where To = fa Aa - $ = is the set of near-optimal nodes at depth h.
In standard MCTS, the root the search tree corresponds to the initial state so E S. node at depth h represents action sequence (a1...., an) E AA, which leads terminal state s(a). The search tree at iteration n is denoted tree(T,), and its maximum expanded depth is d,,.
Historical research has shown that the UCT principle suffers from theoretical worst in which it difficult to derive meaningful regret bounds, making it unsuitable for analyzing the benefit of EGG over standard MCTS. Therefore, assume that MCTS operates under the Optimistic Planning for Deterministic Systems (OPD) framework (Leurent & Maillard 2020) rather than the UCT principle.
A.2.2 REGRET BOUND OF MCTS
Theorem A.I (Regret bound of MCTS Munos (0014), chapter 5)). Let regret(n) denote the simple regret after n iterations of OPD used in MCTS. Then, we have:
regret(n) Ö
leg(1/7) log
Here, the soft-O version of big- O notation for time complexity defined as: fn Ö(n -a) means that decays at least as fast as -a up polylog factor.
When is small, only limited number of nodes must be explored at each depth, allowing the algorithm to plan deeper, given budget of n simulations. The quantity x represents the branching factor of the subtree of near-optimal nodes that can be sampled by the OPD algorithm, serving an effective branching factor in contrast to the true branching factor K. Hence, λ directly governs the given MDP.
achievable simple regret of OPD (and its variants)
The theoretical analysis of EGG-MCTS is built on top of the analysis procedure in Leurent & Mail- lard (2020). Unlike their analysis, which requires unrolling the graph into a tree and addressing potentially infinite-length paths induced by cycles, our analysis starts from the unrolled tree derived from the graph in Leurent & Maillard (2020).
17

---

Published as a conference paper at ICLR 2026
Definition 2 (Upper and Lower bounds of the Value function). Let tree(() be the search tree after n expansions. Each node corresponds to an action sequence (ay, a1...., (H-1) from the root, and let denote the MDP state reached by executing this sequence from the root state so- The true value associated with this node is the optimal value of the reached state, denoted by V(s). A pair of functions (T.n: Un) is said to provide lower and upper boundy for V tree(T) if
Ln S V6) Un. for internal node in the tree(T)
Definition 3 (Finer Difficulty Measure). We define the near-optimal branching factor associated with bounds (Las Un) as
K(Las Un) = lim sup Th (Ln, Un) [], 1+000
where Th0 (I,U) = {a A - S S (U(a)
Since (Ln, Un) tighten with the sequence of bounds (Ln: Un) n20 is non-increasing, i.c.,
5 ... Ln-1 S L, S V S Un S Un-1 ... Vmax
they will finally converges to a limit Riso = lim ki (L,, Un).
A.2.3 REGRET BOUND EGG-MCTS
Theorem A.2 (Regret Bound of EGG-MCTS). Let 6n k(Ln, Un), and define Kip lim <(bm; Un) E K). Then EGG-MCTS achieves the regret bound
regret (n) Ō
log(1/7) log Mize
where Koc I
Proof. The analysis is similar to that of Leurent & Maillard (020) Theorem 16). In their approach, the graph is unrolled into a tree to leverage the analysis of Theorem A.I This unrolled tree contains every action sequence that can be traversed in G.. There would exist path of infinite length if the graph contains cycles. The behavior of the graph G, is therefore analyzed through its corresponding unrolled tree UnrollTree[TT,)
Our EGG-MCTS behaves almost identically to this unrolled tree, except that it contains no paths of infinite length, since algorithm cannot empirically generate or update along infinite action sequence. Transporting the graph-based value bounds (L,, U.. to the unrolled tree and applying the depth-regret argument Leurent & Maillard (2020) Appendix A.9) yields the rate in 9 The detailed derivation is therefore omitted here for brevity.
Remark 1. For a class of symbolic regression problems where a large set of mathematical iden- tities is applicable, the resulting overlaps among action paths can be extensive. In this case, the effective branching factor Rec can be much smaller than the nominal branching factor s, leading to substantially tighter regret guarantees.
18

---

Published as a conference paper at ICLR 2026
A.3 PROOF OF THEOREM 3.2
A.3.1 NOTATION AND ASSUMPTIONS
Let be sequence of production rules sampled from a sequential decoder with probability po(r). is the expression constructed by т following grammar definition. Let Sg S be the equivalence class (under the rewrite system R) of sequences that deterministically construct e or can be rewritten into @ by applying rewrite rules R. For notation simplicity and clarity, we define the probability the of sequences S
go(0) ΣPO(T). TES
PO(T).
(10)
A.3.2 PROOF OF UNBIASEDNESS
Lemma (Key identity). For any d E & with go > 0, Er Vo log po Va log (o
By the definition of conditional probability, PP(T(() Hence,
Proof.
po(r) for Sp and 0 otherwise. qu(o)
Vo Po( PO(T)
E
Vo loggo(()) Ø
Σ
Vopo(T) (o(0)
Vo Σ po(
(0( (Ø))) TES
rES.
TES.
Vogo(d)
go(0)
= Vo log qo (6).
Proposition 1 (Unbiasedness). Er-- [e(()] RrIpp [9cE2 (0)]
Proof. First, for the EGG-based estimator,
E Jegg (0) = Σ
(ew Vo log (0) pe(T)= = Σ Σ reward (6) Vo log (0)) pe (T)
rEll
ΦEO TES
Σ reward(o) Ve log (e)
Σ po(
dEΦ
TES
= go(d)
reward( Vogo(Ø)
d
V reward( (o)))
Φ
For the standard estimator,
E
[g(0)] = Σ reward(T) Vo (o()) po(T) = Σ reward(T) Vopo(T)
TENl
TEnl
= V reward(T)pe(?
7Ell
V reward Po(T)
dE4 rES,
V reward ()) go(d), (
6E
where we used invariinv of the reward and (10). This equals the expression obtained for Jegg proving unbiasedness.
19

---

Published as a conference paper at ICLR 2026
A.3.3 PROOF OF VARIANCE REDUCTION
Define the o-field generated by the expression (Ø)) Consider the random variable
Z reward(T) Ve log (T) reward + V po(T),
where the equality uses reward invariance within each Sg. By Lemma
E [Z reward(o) E VV Pog = reward の) Ve log go(() Jegs (0).
Thus, Segs (0) is the Rao-Blaacwellizzttoon of g(0) with respect to a (6) (Casella & Robert 1996).
Proposition 2 (Variance reduction). Varr Mage (0) I Varr~po [g()]]
Proof. By the law of total variance,
Var 2 Var(EElZ() [[Var(Z]o]] Var (E[Z]Ø)).
Substituting Z g() and (0) = Oegs (f) yields
Varr~pe (aaz (0)] S Varr [o(0]]
Combining Propositions proves Theorem 3.2
Remark on baselines. a baseline b(.) independent the sampled action (sequence) included, both estimators remain unbiased, and the Rao tlo-Blackwell argument applies to the centered variable as well, so the variance reduction still holds (and can be further improved by an appropriate baseline choice).
20

---

Published as a conference paper at ICLR 2026
B IMPLEMENTATION DETAILS
B. VISUALIZATION OF EXPRESSION CONSTRUCTION VIA CONTEXT-FREE GRAMMAR
Figure 6 further illustrates how an expression such as Φ ei log(z1) 1) can be constructed from the start symbol by sequentially applying grammar rules. We begin with the multiplication rule A - x A, which expands the initial symbol in Φ = A to yield & = A A. Continuing this process, each non-terminal symbol is recursively expanded using the appropriate grammar rules until we obtain the valid expression & = <i log(zi)
A AXA
A
A + log(A)
A +
A
AXA
C X A
Ci log(A)
cj log(x)
Figure 6: Transforming sequence of grammar rules into valid expression. each step, the first non-terminal symbol inside the squared box is expanded. The expanded parts are color-highlighted.
The next step is to determine the optimal coefficient ej in the expression ø ci log(z1). More gen- erally, suppose the expression contains m free coefficients. Given training data D {(x, y:) y:) we optimize these coefficients using gradient- method such as BFGS by solving
c²
arg min CER"M N
Σ ((((x, c),
where the loss function l typically the normalized mean squared error (NMSE), which is defined in Equation (12)
B.2 IMPLEMENTATION OF REWRITE RULES
The following snippet defines the Python implementation of a rewrite rule from a known mathemat- ical identity. The function rules es to s expr converts the input list representation into an internal symbolic expression tree:
class Rule:
"each rule is defined as: LHS Aleadsto RHS."
def init (self, 1hs, rhs):
self lhs cales_to_s_exet (Ihs) self.rhs rules_ jules_to_s_exp_ (rhs)
Each rule encodes one direction of applying a mathematical identity. Prior research (de França & Kronberger 2025) has primarily used rewrite rules simplify expressions, typically rewriting longer expression into shorter one. In contrast, our work considers both directions of each identity, enabling us to systematically generate the complete of symbolically equivalent expressions.
We define several types of rewrite rules based on well-known mathematical identities: Let a, b denote arbitrary variables, coefficients, or sub-expressions.
Commutative law, a+b b+ #b b*a will converted into rules: a+b b a+b b * a.
Commutative laws Rule (1hs= ('A>> (A+A) 'A->a', 'A->b"), rhs= (A-> (A+A) 'A->b', 'A->a'J) Rule (1hs- [AA-AAAA,, 'A->a', 'A->b"], rhs-['A->AtA) 'A->b", 'A->a']>
Distributive laws: (a 6)2 a 2ab 622
Factorization. Expressions can be decomposed into simpler components: a?-12 ~n -a-(aa (a-b)(a+b)) Exponential and logarithmic identities: exp(a + b) ~t exp(a) x exp(b), log(ab) mn log(a) + log(b), and also log(a") bloga,
21

---

Published as a conference paper at ICLR 2026
Table 3: The list of rewrite rules for trigonometrie functions, each derived from known trigono- metric law.
Category
rewrite rules
Sum-to to- Product Identities
sin(a) + sin(b) ~ 2sin
0+00
2
COS
cos(4) + cos(b) ~ 200s
A+0
Cos
sin(a) cos ~ 7 [sin(a + + sin a
b]]
Product-to-Sum Identities
cos(a) ~ [cos(a b + cos b)]
sin(a)ssin())
[cos(a b) cos(a + b)
sin(a ~ 2 (sin(a)cos(a)
Double Angle Formulas
cos(a coscooss
sin
cos(a ~- 2 cos (a)
cos(a +a ~ 1 - 2in (a)
tan(a ( ~+ t-tan=
2tan(
sin" cos (a) ~
Pythagorean Identities
sec²(a) tan itan2(e)
(a)
csc² (a) cot ~
sin" (
1-00s(0)
~ [+cos(a)
Half Angle Formulas
cos (g)
tan 2 (9)
1- nosfa)
I+cosla
sin(a a b) sin(a) cos 6) + cos((a)sin))))) sin(b)
Sum and Difference Formulas
cos a + b) ~- cos(a) cbs F sin(a) sin
tan
(tan(a) + tan(b)) (1 F tan(a) tan (b))
5. The rewrite rules for trigonometric identities are summarized in Table 3 For example, The rule sin(a + b) sin(a) cbs + sin(b) cos(a) () is implemented as follow:
Rule( 1hs= | 'A->sin (A) (A+A ', 'A->a', 'A->b'
rhs- (-s-['A-0 ('A-> "A-SA*A", 'A->sin (A) ', 'A->a', (A->cos (A) ', 'A->b',
'A->cos (A) ', 'A->a', (A) 'A->b'1>
visualization of this rule being applied to an expression shown Figure
For practical reasons, we did not introduce rewrite rules that could make the e-graph exponentially large. Rules such as a + 6 - b ~ a a--b+1 are omitted, since they lead to infinite symbolic variants. Such extreme cases are still beyond the capability of the current EGG module.
Note that each rewrite rule is well-defined only on its feasible domain and is not applicable in out-of- domain cases. our symbolic regression setting, such cases typically indicate that the completed expression does not fit the training data and will trigger numerical errors during evaluation. For example, the rule log(axb) log(a) (og()) is valid when a, b > 0, but undefined when or b < O. The expressions log(x;) + log(#²) and log(zf=3) evaluated on datasets containing negative inputs will yield oo floating-poin arithmetic, causing the NMSE evaluation to become Not-a- Number (NaN). This indicates that such candidate expressions are incompatible with the dataset. Systematically encoding and enforcing domain constraints for all rewrite rules requires careful study of the underlying mathematical identities, and leave this interesting direction for future work.
B.3 IMPLEMENTATION OF E-GRAPH
Here provide the implementation of the EGG data structure proposed in Section 3.1 consists of two core components: e-nodes and e-classes. The following snippet presents the skeleton structure of these two components:
An e-graph
class ENode: def init (self, operator: str, operands: list):
22

---

Published as a conference paper at ICLR 2026
self seli.cperator, self.operands operator, operands
def canonicalize (self))
Convert to the canonical form of this ENode
class EClassID:
def (set_ id): self.id id
self.parent None
def
find_parent (self):
Return the representative parent ID (using union-find algorithos (sel))
def return (e-class format (self.id)
The e-graph structure is implemented in the following class. The dictionary hashcons stores all the edges from an e-node to an e-class. The API supports the key operations (1) adding new expressions the e-graph by calling add_enode, and (2) merging e-classes into one by calling merge.
class EGraph:
hashcons: stores mapping from ENode to its corresponding ECiass hashcons: Dict [ENode, EClassID] ()
def edd_e (self, enode: ENede) Add an ENode into the e e-graph
def eclasses (self) -> Dict [RC1assID, List [RNode]]: Return all e-classes and their associated e-nodes
def merge (selÉ, EClassID, EClassID):
Merge two e-classes using the union-fing structure
def (Ssstttutosseff.. pattern: Node, ...) -> EClassID:
Construct a new expression in the e-graph from rule RHS
B.3.1 CONSTRUCTION
The e-graph is built by repeatedly applying a set of rewrite rules to the e-graph. Each rewrite rule consists of left-hand side (LHS) and a right-hand side (RHS) expression. The function apply_rewry wewply.rwriite.r...... teerteerreeee es determines which new subgraphs to construct and where to merge them within the existing e-graph.
Specifically, the LHS pattern of each rule is matched against the e-graph using the ematch func- tion, which identifies all subexpressions that match the pattern. For each match, the RHS in- stantiated using the extracted variable bindings, and the resulting expression is inserted into the function
e-graph and merged with the corresponding e-class. The equality.saturat vokes apply rewrite rules for a fixed number of iterations until saturation is reached.
def hoplyyrewriteerules (eg: EGraph, rules: List [Rule]); eclasses = oclaclass ()
matches = []
for rule in rules:
for eid, env in ematch (eclasses, rule. 1hs): matches append (rule, eid, env) for rule, eid, env in matches:
new new_eid eid suastiiie (rule. rhs, env) eg eg.merge (eid, new_eid) eg rebuild()
def
rules, max :xx
eg
s_expr (fn)
for it in range (max_iter):
23

---

Published as a conference paper at ICLR 2026
apply_rewrite rules (eg, rules)
We employ the Graphviz API to visualize the e-classes, e-nodes, and their connections. Several visualization example is shown in section D
B.3.2 EXPRESSION EXTRACTION
Cost-based extraction retrieves simplified expression by minimizing user-defined cost over operators, The procedure returns an expression tree with the lowest total cost, where the cost is computed across all operators. Each e-class is assigned cost equal to that of its cheapest e-node, and the cost of an e-node defined recursively as
cost(enode) cost(operator) +
E cost(child).
(11)
child e-classes
The algorithm iteratively updates costs for all e-nodes until convergence, i.e., when further changes occur. This strategy yields short, simplified expressions and has been used in prior work (de Franca Kronberger 2025, de França Kronberger 2025), which employed e-graphs to simplity overly complex expressions in genetic programming. It is consistent with the philosophical principle of Occam's razor, which favors simpler expressions over more complex ones.
Random walk-based sampling. which draws batch of expressions randomly from the e-graph. Starting from an e-class with no incoming edges, we randomly select an e-node within the current e-class and transition to the e-classes connected to that e-node. This process continues until an e- node with no outgoing edges reached. The obtained sequence of visited e-nodes corresponds to drawing valid expression from the constructed e-graph.
B.3.3 IMPLEMENTATION REMARK
Existing e- e-graph implementations are available in Rust (egg library, Willsey et al. (2021 Haskell (Hegg or srtree library), and Julia (Metatheory.ji), or wrappers for Python (egglog- python, [Shanabrook] (2024); de França & Kronberger (2025)). While these frameworks offer rich APIs for diverse use cases, none is directly tailored to grummar-based symbolic expressions.
While packages such as SymPy provide APIs like s simpli fy and factor, these functions map expressions to a fixed canonical form and do not support the richer class of rewrites and transfor- mations. These APIs return smaller set of symbolically equivalent expressions than our EGG framework. Hence, they are not used in our implementation.
Our implementation builds upon existing code snippe[" The most relevant prior implementation we identified available in Haskel the language in which e-graphs were originally developed. However, this choice complicates integration with Python-based environments, especially when in- terfacing with learning algorithms implemented in Python. A Python wrapper for Haskell egglog also exist& but its API is cumbersome and lacks clarity, limiting its usability for practical applica- tions.
http:://giithbb..com/rrraasssss egg ogglog-python
24

---

Published as a conference paper at ICLR 2026
B.4 IMPLEMENTATION OF EGG-EMBEDDED SYMBOLIC REGRESSION
B.4.1 IMPLEMENTATION OF EGG-MCTS
Markoy Decision Process Definition for MCTS. We model the search process finite-horizon Markov decision process (MDP). A state corresponds to partially constructed expression, and each node in the MCTS search tree represents one such state. An action corresponds to the application of a single production rule to the first non-terminal symbol in the current state. The transition dynamics deterministie: given state-action pair, the successor state is uniquely determined by the application of the selected production rule. Rewards are assigned only at terminal states (leaf the dataset according
nodes of the search tree). obtained by evaluating the completed expression to an evaluation metric. The episode length is thus equal to the number of applied production the discount factor 1. A trajectory is sequence of state-action transitions
rules, and corresponding to path from the root node to leaf node in the search tree, resulting in either a valid or invalid expression. The MDP horizon finite: each episode terminates when the path from the root corresponds to valid expression with no non-terminal symbols or when the maximum depth H is reached.
Example B.1. Figure 7 illustrates an example execution pipeline of EGG-MCTS. We focus two distinct root-to-leaf paths in the search tree:
Path 1: (A + A A,
sin (x2).
A
A
A cos (x2)).
Node 81: sin (x2) + cos? (x22 + A.
Path 2: (A + A + A, A - A/A, A + 21, A + x1),
Node s2: 21/21 + A.
Under the grammar Section 81 corresponds to the partially specified expression sin (2:2) + (1s2(12)) + A, whereas 82 corresponds to I1 /1/x1 + A. The two nodes are symbolically equivalent under the rewrite rules (ai + cos2(a) ~ 1, a/a ~ 1}, and both reduce to the same partially specified form 1 + A.
A
A A+A
log(A)
4+A
A sin
A - (A)(A)
sinr(xz) +1
(A)(()) +A
A - A
sin +
+
(a) It corresponds to underlying function 1 A, with the rewrite rule sin)(a) + ca)"(a)
A A Xi
(b) corresponds to an underlying function & = + A. with the rewrite rule: ala ~ 1.
sin + cos
x//+
Figure 7: Two distinct paths reach leaf nodes that represent the same underlying function & 1+ A, where A denotes an arbitrary sub-expression. This equivalence follows from the rewrite rules sin 2 (a) + cas ~ 1 and a/a ~ 1.
Consequently, their rewards-whin which estimate the average goodness-of-fi on the datasct-should be approximately identical. Exploring the subtrees rooted at s and s2 independently, therefore, incurs redundant computation. In contrast, EGG identifies their equivalence and jointly updates the visit counts and reward estimates along the two paths (blue and orange), eliminating the need further explore duplicate subtrees in subsequent iterations.
Connection to equivalence-aware learning in MCTS, In many applications, multiple action se- quences may lead to the same state, resulting in duplicate nodes within the search tree. To mitigate this redundancy, Saffidine et al. (2012) proposed the use of a transposition table in the context of Go, enabling the reuse of information from previous updates. Similarly, Leurent & Maillard (2020)
25

---

Published as a conference paper at ICLR 2026
introduced Monte Carlo Graph Search (MCGS), which replaces the search tree with graph that merges identical states. In MCGS, nodes correspond to unique states s E S and edges represent state transitions, with the root node corresponding to the initial state Sn- At iteration n, if executing action a from state a leads to a successor state s' that already exists in the graph, no new node is created.
Our EGG-MCTS adopts the same principle of detecting identical states during search, but avoids explicit graph construction. The constructed e-graph serves as a transposition table that stores and detects identical states. Following the same update rule used in a transposition table, EGG-MCTS simultaneously updates all paths in the tree that lead the selected state. This design preserves compatibility with standard MCTS implementations while achieving a theoretical acceleration com- parable to that of Leurent & Maillard 2020).
B.4.2 IMPLEMENTATION OF EGG-DRL
Markov Decision Process Formulation for DRL. We model this problem as RL agent that searches for the optimal sequence of grammar rules. At decoding step f, the agent samples a rule Tę conditioned on the previously selected rules 7i, ....... Tt-1- We define the state step t as the prefix of sampled rules 8 = (Ti,..., Tr-1), and the grammar rules in the output vocabulary constitute the action space for the RL agent. The sequential decoder, parameterized by 0, defines a stochastic policy
To (a = a' (s) = po = d'Im...... Tt-
The environment transition is deterministic: applying action ti in state 8, yields the next state 814-1 (Ti,....77) Te). Rewards are obtained by evaluating the completed expression on the dataset according to a chosen evaluation metric (e.g.. 1/(1 + NMSE(())). The MDP has a finite horizon: an episode terminates once the output sequence corresponds symbols, or when the maximum sequence length H is reached. The objective of the RL agent is to learn policy that selects sequences of grammar rules so as to maximize the expected reward.
valid expression with no non-terminal
Configuration of Sequential Decoder. The sequential decoder can be implemented using various architectures, such as RNNs (Salehinejad et al. 2017), GRUs (Chung et al., 2014). LSTMs (Greff et al. 2016), or decoder-only Transformers (Vaswani et al. (017)) The input and output vocabular- ies for the decoder consist of grammar rules that encode variables, coefficients, and mathematical operators. Figure a(a) illustrates an example of the output vocabulary.
At each time step, the model predicts a categorical distribution over the next rule, conditioned on the previously generated rules. At step I, the decoder (denoted as drequentialDecodee takes the previously generated rules (TI...., T(-1) and the hidden state h4-1, and computes
h, = Sequential (T:-1, hı-1),
Z: W.h; + bo.
(o(Te (1..7 = softmax(ze).
where W. E R/V is the output weight matrix, b, RIVI is the bias vector, and [V] is the size of the vocabulary. The next rule is then sampled from this distribution, Tı (T(TTTTI, Tt-1) and fed back into the decoder as input for the next step, until the sequence completed. After H steps, the full sequence (ri,..., TH) is generated with probability po(7) = -I (o(Ti/Ti,......... T--), with the convention that is special start symbol.
Each sequence т is then converted into an expression following the grammar definition Section 2 If the sequence terminates prematurely, grammar rules for variables or constants are appended at random to complete the expression. Conversely, a valid expression obtained before the sequence ends, the remaining rules are discarded. In both cases, the probability (T( is updated consistently with the applied modifications.
Finally, the model parameters are updated using gradient-basee based optimization (e.g., the Adam opti- mizer) with either the classic policy gradient estimator g8) or the proposed EGG-based estimator Iogg. (f). The whole pipeline is visualized in Figure 8
Connection to equivalence-aware learning in DRL. Several techniques have been introduced to reduce the variance of policy gradient estimates. One widely used approach is the control variate
26

---

Published as a conference paper at ICLR 2026
expression Φ = logg(f x x²) sampled from decoder
Output:
A log(A)
A
A x
A
~ X2
Index
Vocabulary of rules
0
- (A + A)
Categorial distribution
A - A X
2
A + log(A)
A - A²
Sequential
A A A"
decoder
5
A
6
Input:
A = log(A)
A - A XA
A A A²
A - x
A
7
(a) Predict expressions from the sequential decoder by sampling rules auto-regressively.
Equivalent expressions
New policy gradient estimator Bega
Sequential Decoder
Sampled expression
Equality Graphs
log(> + log(x;) log(x)) + log(x,)
Φ
log(x x x5)
Policy gradient estimator g(O)
(b) Learning pipeline of DRL (colored blue) and EGG-DRLL(coloeed blue and green).
Figure 8: Framework of DRL and our EGG-DRL. (a) The sequential decoder autoregressively sam- ples grammar rules according to the modeled probability distribution. (b) classic DRL, the sam- pled expressions are directly used to compute the policy gradient estimator g(0). While EGG-DRL constructs e-graphs from the sampled expressions, extracts symbolic variants, and computes the re- vised estimator Yagg (0).
method, where a baseline is subtracted from the reward to stabilize the gradient (Weaver & Tao 2001]. Another idea is Rao- Blackwellization (Casella Robert 1996). Other approaches, such as reward reshaping (Zheng et al.] 2018), modify rewards for specific state-action pairs. Inspired by stochastic variance-reduced gradient methods (Johnson Zhang 2013 Deng et al. 2021]. Papini
et al. (2188) proposed variance-reduction technique tailored for policy gradients.
Unlike these existing methods, our proposed EGG the first to reduce variance through the domain knowledge of the symbolic regression application, and show seamless integration into the learning framework and attain reduced variance.
B.4.3 IMPLEMENTATION OF EGG-LLM
Our EGG is adopted on top of the original LLM-SR (Shojaee et al. 2025).
(a) Hypothesis Generation. The LLM generates multiple candidate expressions based prompt describing the problem background and the definitions of each variable.
(b) Data-driven Evaluation. Each candidate expression evaluated based on its fitness on the training dataset.
(c) EGG-based Feedback. Inferring Equivalent Expressions. For case of integration with the e-graph system, we convert the generated Python functions into lambda expressions. This simplifies their manipulation and evaluation during equivalence analysis.
Original function format
def hypothesis (x1, x2, coeffs)
expr = x1 * cocffs[0] + x2 coeffs[0]
return expr
$ Converted into lambda format hypothesis lambda x1, x2, coetis: x1
coeffs
coeffs [C]
This conversion allows us to transform the hypothesized Python function into an expression
tree directly. For each fitted expression, we construct e-graph and apply predefined set of
27

---

Published as a conference paper at ICLR 2026
Predicted expression
</>
eqattion(x,, x2, coettais
2- Ange:
sprcsficction
posision, x2s veloeity
GctenttFic probles descriattor)
comffs: confficients expcession
</>
5.
evalustion
(Evaluotion
Prompt
LLM
y comftn(D) =p.xtt((somtfe]]]441
</>
sonlisoor dasping
Expertence donensi.notion
"equst Fon_ve"; score_va,
linear restoring
"equation.v1"" score.vl,
</>
coutia(1]
"equation_ score_y2,
zetuzn
(a) Hypothesis generation
LEG--base feedback
score
Fit coefficients using dataset
422
EGG Module
evaluate goodness-offfit
scor
N: score-
# No score
(c) EGG-based Feedback
Data-driven evaluation
Figure 9: Pipeline of EGG-LLM. (a) Hypothesis Generation. The LLM receives prompts derived from the problem specification and predicts multiple candidate expressions. (b) Data-Driven Eval- uation. The coefficients of each candidate are fitted the dataset and then evaluated on separate validation set to compute goodness-of score. (c) EGG-Base Based Feedback. The proposed EGG module generates symbolically equivalent variants, which are fed back into step (a) to guide the next round of hypothesis generation.
rewrite rules until reaching a fixed iteration limit. From the resulting e-graph, we sample K unique equivalent expressions. Each sampled expression is then converted back into Python function to facilitate further interaction with the LLM.
# obtained equivalent expression
equiv_seq, = ("A->log(A) (A) "A->A*A", "A->x1", "A->x2"]
d Converted function format def equiv squiv_hypethesis (x1, x2, coeffs): return
x2
In subsequent iterations, the LLM receives feedback consisting of previously generated ex- pressions along with their fitness scores. Our feedback enriched with both the original hy- potheses and their equivalent expressions derived via EGG module, enabling the model to refine future generations. niigh-performing expressions are retained and further updated over multiple rounds.
B.4.4 FINAL REMARK
The E2E-Trane Transfoasfrrm framework (Kamienny al. 2022) is structurally very similar to the neural network used in the DRL model, with the main difference being that it is trained using a cross- entropy loss function. straightforward way to integrate the EGG module into E2E-Transformer through data augmentation, where additional training examples are generated using EGG.
To date, only one work has explored the use of text-hased diffusion model for symbolic regres- sion (Bastiani et al. 2025). However, its implementation has not been released publicly. Moreover, the proposed pipeline relics on multiple interconnected components, which makes it difficult to re- produce or isolate for independent evaluation. For these reasons, do not include comparison between the text-based diffusion approach and EGG in this paper.
Several extensions of the baseline considered in this study offer empirical improvements but lack theoretical guarantees. For example, Tenachi et al. (2023) employ genetic programming to refine the predictions of the DRI. model, and Tenachi al. (023) introduce unit constraints in physical
28

---

Published as a conference paper at ICLR 2026
systems to eliminate infeasible expressions. Integrating EGG with these variants is an interesting direction that we leave for future investigation.
29

---

Published as a conference paper at ICLR 2026
C EXPERIMENT SETTINGS
C.I BASELINES AND TLYPER-PARAMETER CONFIGURATIONS
The representative baselines are selected as they all regard the search for the optimal expression as sequential decision-making process. A detailed description of each method is provided below:
MCTS. Sun et al. (2023) propose to use the Monte Carlo tree search algorithm to explore the space of symbolic expressions defined by context-free grammar (described in Section 2 find high-
performing expressions. Despite being implemented similarly, this method appears under various
names in previous works (Todorovski Dzeroski, 1997, Ganzert al. 2010 Brence et al. 2021
Sun et al. 2023 Kamienny et al. 2023). We choose the implementation from Sun et al. 2023 and serve as representative of this family of methods.
DRL. Petersen et al. (2021) propose to use a recurrent neural network (RNN) trained via (risk- seeking) reinforcement learning objective. The RNN sequentially generates candidate expressions and is optimized using risk-seeking policy gradient to encourage the discovery of high-qualit, We use three types sequential decoders for the time benchmark setting. The major configurations are listed in Table
expressions. We chose this implementation 5
Table Hyperparameters for the DRL Model with different types of neural network. This configu- ration is also used in Figure
General Parameters
max length of output sequence
20
batch size of generated sequence
1024
total learning iterations
200
Reward function
[NSSE
Optimizer
H Hyperparameters
optimizer learning rate entropy weight
Adam
0.009
0.03
entropy gamma
0.7
Decoder-relevant Hyperparameters
choice of decoder
LSTM
Decoder-only Transformer
num of layers hidden size
3
3
128
128
dropout rate number of head
0.5
/
6
LLM-SR. (Sojjaeee et al.) (2025) proposed to use pretrained large language models, such as GPT3.5, to generate symbolic expressions based on task-specifie prompts. The expressions are evaluated and iteratively refined over multiple rounds. We choose their implementation at
For each baseline, we adopted the most straightforward implementation. Only minimal modifica- tions were made to ensure that baselines use the same input data and problem configurations, and are compatible with the proposed EGG module. We also rename the abbreviation of each method, to clearly present the core idea in each method and uniformly present the adaptation of our EGG on top of these baselines.
Expresiion-related Configurations. When fitting the values of open constants in each expression, sample a batch of data with batch size 1024 from the data Oracle. The open constants in the expressions are fitted on the data using the BFGS optimizer" 2 We use multi- polliipprocessor library to fit multiple expressions using CPU cores in parallel. This greatly reduced the total training time.
www.e.iwimiiiiimmmmmm...mmm. zw-bzea.a........ html
30

---

Published as a conference paper at ICLR 2026
Table Hyper-parameter configurations for symbolic expression computation.
Expressions and
Dataset
training dataset size
2048
validation and testing dataset size
2048
coefficient fitting optimizer maximum allowed coefficients
BFGS
20
optimization termination criterion
error is less than 1e 6
An expression containing a placeholder symbol A or containing more than 20 open constants is not evaluated on the data; its fitness score is -00
To ensure fairness, we use an interface, called dataOracle, which returns a batch of (noisy) observations of the ground-truth equations. To fast evaluate the obtained expression is evaluated using the Sympy library, and the step for fitting open constants in the expression with the dataset uses the optimizer provided in the Scipy library
During testing, ensure that all predicted expressions are evaluated on the same testing dataset by configuring the dataOracle with fixed random seed, which guarantees that the same dataset returned for evaluation.
We further summarize all the above necessary configurations in Table
C.2 EVALUATION METRICS
We mainly consider two evaluation criteria for the learning algorithms tested in work: 1) the goodness-of-fh measure and 2) the total running time of the learning algorithms.
The goodness-of-fit indicates how well the learning algorithms perform in discovering unknown symbolic expressions. Given a testing dataset Drest = {x,,, })) generated from the ground- truth expression é, we measure the goodness-of-fr fit of predicted expression Ppred- by evaluating the mean-squared-error (MSE) and normalized-ment mean- -uuuraa-aee---dd--ee----- error (NMSE):
n
1 E. (v: Oprod (x;))
(x)))(x;))
MSE-
(yi Uprad (x:))²
NMSE n.
YI 1=1
(12)
RMSE
Wi (x:))3
NRMSE
(ys Uprod (x;))²
where the empirical variance By determination (R2²) metric (Nagelkerke et al. 1991 Cava al. therefore omitted in the experiments.
(y:
9A
Note that the coefficient of is equal to (1 NMSE) and
2021
htm
31

---

Published as a conference paper at ICLR 2026
D EXTRA EXPERIMENTAL RESULTS
D.1 VISUALIZATION OF EGG CONSTRUCTION
We summarize the list of example expressions, their symbolic-euuivalent variants, and the visualized EGG in Table G
Table Summary expressions, their symbolic-equivalent variants, and the visualized it visual- ization of more e-graphs obtained via EGG.
E-graph
ID
Original equation
Symbolic-cquivalent variant
visualization
1
1og(z{æ;)
log((z1) + 2og(
Figure 10
2
exp(c1a1 + x22
exp(c121) exp(x22
Figure
3
sin(21 + 22)
sin(x1) (0s(22) + ) sin(m))
Figure
12
4
log(z) X ... Fnn
log(a1) + +......op log(r)))
Figure
5
sin(21 + nn)
omitted
Figure
(a) Example symbolic regressions
E-graph
ID
Original equation
Symbolic-equivalent variant
visualization
L15.3x
2o 22 -
22
Figure 16
Veteive-ni
1.30.3
To (m2/2))
sin (21
sin(2122/2))
sin(ag/2)
Figure 17
1.44.4
e 2p 1og(22//33)
C1 (log(22 (22 log(53))
Figure
1.50.26
(o(cos(x) x22 + 3y cos (2))2))
Zo (
Iy cos (2)
Figure
15.
Bag
sin
sin(2m))
Figure
4n
8x
11.35.18
Zn
Figure 21
exp(21a2/53) Hopp:pp
2oshh2
11.35.21
T tanh(ar
T0
exp (2n / +1
22p 2g
Figure 22
(b) Selected complex symbolic regressions from Feynman Dataset.
32

---

Published as a conference paper at ICLR 2026
E-graph for log operator. Figure 10 illustrates the e-graph construction for the expression (0g())23) using rewrite rules for log operator: log(a x b) ~e log(a) + exp(b) and also log(a") ~ b log This visualization is based on the Graphviz API. We also label each e-class with a unique index for clarity. As shown in Figure TO the saturated e-graph grows significantly larger as more rewrite rules applied. In full implementation, we incorporate many additional rewrite rules beyond these basic logarithmic identities, resulting in substantially larger and more complex e- graphs.
claasal
C-clase7
A->logg (A)
A->1071A1
2-> (A+3)
erclaas6
e-classs
e-clesed
e-class9
A-5
A-DAPA
(->log(()
e-class2
emclass2
classs
(A)** (A)
A-> (A)**(AA **(A) (A)
(A)
e-cland0
c-classl
c-class3
c-clossi
e-clasaa o-classi
o-clased
A->X1
A->3
A->X2
A->2
A-XX1
A-33
A-
A->2
e-class10
A->log (B)
A- (A+A)
e-clasa12
e-class6
e-class14
A-PA+A
A->1og (A)
A-32+A
A->1og(A) (A)
e-ciasell
e-class2
e-class5
e-clase13
A->log (A)
A- (A) +Y
(-> YY
>->log (A)
Amolassa assll
emol a863
e-class3
e-c 9-c1ass4
A-93
A->X1
A-ンx2
A->2
Figure 10: (Top left) Initialized e-graphs for expression log(zf2z). (Top Right) The saturated graphs after applying one rewrite rule log(ab) ~4 log a + log b. (Bottom) The saturated e-graphs after applying two rewrite rules: log(ab) ~n log + log and log(a") bloga.
E-graph for exp operator. Figure illustrates the e-graph construction for the expression
exp(C1 + 22) using the exponential rewrite rule exp(a + b) ~ exp(a) x exp(b). The input pression exp(c) x I + x2) is represented as a sequence of production rules: (A - exp(A), A A A, A A A, A C1, A + F1, A x2))
33

---

Published as a conference paper at ICLR 2026
e-clasa5
c-class8
A-Poxp (A)
A-Pexp
Å->ArA
e-clased
e class
e e-olasad
e e-claas7
A-bexp (A)
A-3 [A+A]
A-Pexp (A)
e-clasa2
e-colas33
e-class2
e-class3
A->A+A
A-
A->A*A
X-2X2
e-clase0
e-classl
p-classd
e-classl
A->el
A-2x1
A-ba1
A-2x1
Figure 11: (Left)) Initialized e-graph for expression exp(e18) +22). (Right) The saturated e-graphs after applying one rewrite rule exp(a + b) ~* exp(a) exp(b).
E-graph for sin, cos operators. Figure 12 demonstrates the application of the trigonometric identity sa + b) we sin cos + sin b cos a to the input expression sin + x22). The input expression is represented by the sequence of production rules (A + sin( A A, T1, + x.2).
c-olass3
A-
A-3A-A
A (a)a
(A+B)
A-> (2m18)
A-7000 (X)
A-ooca IM
A-roin
A-bx1
R-xx2
Figure 12: Applying the rewrite rule (a ~ sin cos b+ sin b cos in an e-graph representing expression sin(x1 z2). Left: Initialized e-graph. Right: e-graph after applying the rewrite rule.
E-graph for 0/Or; operator. Figure 13 shows the application of the partial derivative commutativ- 82f
0² ity rule Bn.dny Bay0z, to the input expression 0² +w2) 8ar, A22
The derivation is represented by the following production rules: (A - 0(A)/Ox1. A + ((A)/0z) A + x2).
A- A-)8 (A) /axt
A- /8x1
A- /ax2
1-38 /2x2
A-08 (A) /8x2
X- (2) /8x1
R=5x14x2
A-
Figure 13: Applying the rewrite rule d2.
101 0x,
[8 U5.
in e-graph representing expression
Jzy
(ee
Left: Initialized e-graph. Right:
e-graph after applying the rewrite rule.
8n,0n,
34

---

Published as a conference paper at ICLR 2026
E-graph visualization for analysis in section 5.2
A (8)
A- (AIA)
e-claas4
erolasa2
e-classu
A->1og (8)
A->A*A
A->log (8)
claas0
e claass
A-2x1
X->x2
A->log
A-> (A+A)
e-classl1
e-olaas4
e-class7
(a11))
A->log
A-2a-a
A->1og (A)
e-clasa10
e-classs
e-llass2
e-clasa5
A->log (A)
A->1og (A)
A-
e-closal
e-clas50
A-5x2
A->x1
e-class10
A->log (8)
A-> (&+&)
e-class13
e-clasa6
e-class9
7-> (2+7)
A->log (2)
A->log (2)
e-class16
e-ciass12
e-classd
e-class5
A-> (A+A]
A->log (N)
A->log (2)
A-xx4
e-claas14
e-clasa15
e-clasa2
e-claas3
A->1og (8)
(->1og(A)
A-2x3
e-clasa0
e-clasal
A-xx1
A-
Figure 14:
Visualization of e-graphs for expression log(21 ... Ix), using the rewrite rule
log( (ab) ~4 log a + log b. The three figures correspond to n 2, 3, accordingly.
35

---

Published as a conference paper at ICLR 2026
ee aeslC
(->sin(A)
A-21-A
6-018867
e-clasa2
e-claas8
e-claast
A-boos (A)
A-54+A
(-
A-beinte)
A-
c-class0
e-classl
A-bx
A-2x2
e-class12
e-clanell
e-claral
A-AAAA
e"clezs10
enclaza?
enclaza?
enclazad
erclass19
A-2oint))
A-2000
A-
A-SA-X
e-class3
e-claso2
e-claso15
e-claso18
A+xx3
A-sAva
e-class14
e-classlt
Arogiin [A]
A-oosa
Aroeoa
Antual
ercleani4
A-haini
A-SAPA
Aeostniki
Arseos
Arscos
A-ssir
enclaso11
e-cles922
enclasse
erolanos
85878
exclace18 88
exclasslo
exclosol3
APARIA
A-50001A1
A-po0o CA1
evclazel
Figure 15: Visualization of e-graphs for expression sin(2] +.. xr,), using the trigonometric rewrite rule sin(a + sin(a) cos(b) sin(b) (as(a). The three figures correspond 2,33, 4.
36

---

illustrates the application of Published as a conference paper at ICLR 2026
D.2 ADDITIONAL VISUALIZATION FOR SELECTED EXPRESSIONS FEYNMAN DATASET
E-graph for equation ID 1.1.3xx in the Feynman dataset. Figure 16 illustrates the application of the rewrite rules Vab ~ /ayb and a² b² = (a (a+ ba(a b) to the input expression
enclassti
Iesagrt
erolease
erclospd
class4
clasat4
ciams13
claxatt
p-clsas0
e-clans]
exclanol
e-claza]
e-class?
A-3a0
Ansking
Jk-Ai
A-902
A-Pconst
Figure 16: (Left)) Initialized e-graph for the expression (ægg - 1 /2/22////// o 21. where the equation ID is I.1533x in the Feynman dataset. (Right) Saturated e-graph after applying the rewrite rule Vab my Vavb and a² - b² = (a + (a b).
E-graph for equation 1.30.3 in the Feynman dataset. Figure 17
the rewrite rule a 2/22 ~n (a/b)² to the input expression
sin sin 2)
20 sin (22/
classó
A-SAPA
A
e-clexst
A-oad
1-2 (o)
A-ss0
(-)
A-3 (2)
e-cleso2
c-olass?
A->
A- +2
(A)
1-11A))
enclasal
erclita3
c-classi
c-clase3
A-
Figure 17: (Left) Initialized e-graph for the expression 2n (xn/(2 where the equation ID is 1.30.3 in the Feynman dataset. (Right) Saturated e-graph after applying the rewrite rule log(a/b) log a log b.
sin' (arrr/2)
E-graph for equation ID L.44.4 in the Feynman dataset. Figure 18 illlustrates the application of the rewrite rule log(a/b) log log the input expression 614621 log(22/2ra).
37

---

Published as a conference paper at ICLR 2026
prolassd
e-claes12
A-bloplA)
emclusa2
unclass?
emclausd:
erclasso
enclass5
A-PH2
Figure 18: (Left) Initialized e-graph for the expression C1 log(22/ (23), where the equation ID 1.44.4 in the Feynman dataset. (Right) Saturated e-graph after applying the rewrite rule log(a/b) log a - log
E-graph for equation ID 1.50.26 in the Feynman dataset. Figure 19 illustrates the application of
the rewrite rule ab + a(b + c) to the input expression 20 20 +33 cos (x1122))
e-clasa6
b-clas56
e-clase0
e-clase9
A-2A+A
A->x0
7-> (8+A)
A-2a*A
e-classl
(-MA)
e-clase4
e-claas8
e-classi
A-PA*A
A-> (-+1)
A-SAP2
e-class3
e-class7
o-claas22
e-clasa3
A-> (8) **2
A=>a*a
A-Xx3
6-> (2)
c-class2
e-classl
(xl Fx2)
A->x3
A-200s (xI*x2)
Figure 19: (Left) Initialized e-graph for the expression (o(cos(2122)) + (x) )), where the equation ID is 1.50.26 in the Feynman dataset. (Right) Saturated e-graph after applying the rewrite rule a + ba? ~o a(ba- + 1).
E-graph for equation ID II.6.15b in the Feynman dataset. Figure 20 illustrates the application of the rewrite rule cos(a) sin(a) sin(2a) to the input expression exp(2182/23) /+ exxp 21122/0))
38

---

Published as a conference paper at ICLR 2026
e-class9
o-classe
A-SATA
A-SATA
e-olase?
A+> ( Go
A- 1- OAU
(M
anclesso
c-olansl
onclasse
c-ola667
erclenat
erclasa.
enclasoll
anclasa?
A-53
Auptopt
A-sana
A-3021k3
A-
A-Serp:
A-SA-A
A-3x2113
M-clased
M-cclasd
e-clased
e-class5
A-7000
A- (A)
(2
CnCloso3
Figure 20: (Left) Initialized e-graph for the expression 3n0 2 21 where the equation ID 11.6.15b in the Feynman dataset. (Right) Saturated e-graph after applying the rewrite rule (as(a) sin(a) m sin(2n)
4x
E-graph for equation ID II.35.18 in the Feynman dataset. Figure 21 illustrates the ap- plication of rewrite rule (exp(a) + exp(-a))/ ~y cosh a to the input expression =xplanes/sa)ooxp(nooe m120//))))))
e-cla8s5
e-class3
A-> (8)
(A)
p-class0
e-cles86
e-cl3aad
e-class4
A->x0
(A+A)
A->2 tooh (A)
A-
A- (AIAI
c-slass2
c-class3
onclasa2
o-closs3
A->exp(A) (A)
A-2exp (-A)
A->exp
e-classi
e-class1
xx2x3
A->x1*22/33
Figure 21: (Left)) Initialized e-graph for the expression exp(#182/25) tion ID II.35.18 18 the Feynman dataset. (Right) Saturated e-graph after applying the rewrite rule (exp(a) + exp(-a)) ~4 2 cosh a.
expp =xx) - ] where the equa-
E-graph for equation ID II.35.21 in the Feynman dataset. Figure 22 illustrates the application of the rewrite rule tanh exp(2e)-1 to the input expression To tanh 22/2)/3). exp(2a)+1
39

---

Published as a conference paper at ICLR 2026
DATA
e-class5
emclass2
erClase9
L-9
A-2A+A
e-clesed
e-claest
e-clase?
e-clazol
e-clas52
e-class4
M-11
A-SA*A
A-Stanh (A)
erelassé
X-bexg (2
e-clasa0
e-classl
e-class3
c-class3
h->x0
X-2x1
A->x1*x2/sx
Figure 22: (Left) Initialized e-graph for the expression Tn-1 tanh(r) /2/x3)) where the equation ID is 11.35.21 in the Feynman dataset. (Right) Saturated e-graph after applying the rewrite rule tanh a exp(2n)-1
exp(2a)41
40


Reviews:
[{"review_id": "43FaRtzgLb", "reviewer": "Reviewer_Yckw", "summary": "This paper introduces the Equality Graph (e-graph) into the symbolic regression (SR) framework to enable uniform rewards and loss assigned to the mathematical equivalent expressions, enabling a more efficient and robust SR search. The paper provides both theoretical analyses and experiments on several backend learning/search methods to support the claim.", "questions": "1. **Clarity** \n- In line 42, \"A promising yet underexplored direction for reducing the *effective* search space\", do you mean reducing the ineffective or redundant search space?\n- *Inconsistences*: In line 83, coefficients are denoted as $\\boldsymbol{c}$, then in line 93 they are denoted as $const$, and in line 213 $c$ is referred to constant to balance exploration and exploitation.\n- *Confusions*: In Fig.1 and lines 133, 134, 252, and 253, notations explaining the substitution rule for recursively constructing a closed-form expression all use a single notation $A$ for a place-holder subexpression, making it hard to distinguish their hierarchy structure and correspondence in the figure. Using a subscription to distinguish placeholders might be better for clarity.\n- *Missing Critical Definitions*: There are no formal definitions of states and actions in the Markov Decision Process (MDP) for both MCTS and DRL in the main context. There is also no clear definition of what a node $s$ represents in line 211 (I assume it should be the candidate expression $\\phi$ inferred from the example in line 252) and what a sequence $\\tau$ represents in line 272 (Is it the same as $\\phi$ for node $s$? How EGG is represented as a state here?).\n2. **EGG-based Backpropagation**: I have two major concerns about the EGG-based backpropagation based on my understanding, both of which arise from the backpropagation to all the equivalent sub-expressions in MCTS:\n\n- The EGG-based backpropagation seems to backpropagate the increasing visit counts to all the equivalent sub-expression generation paths (even if they are not explored at this stage). Does it mean that the visit counts are dependent on the number of equivalents a sub-expression has, so that visit counts of an expression with more equivalents will grow faster, leading to potentially under-explored UCT search?\n- Even if the above case is fine for the terminal nodes that are equivalent, the non-terminal nodes on the intermediate paths might not be equivalent. For example, two equivalent subexpression, their paths $sin^2(A_1)+cos^2(A_2) \\rightarrow sin^2(x)+cos^2(x)=1$ and $\\frac{B_1}{B_2} \\rightarrow \\frac{y}{y} = 1$  can have distinct intermediate expressions $sin^2(A_1)+cos^2(A_2)$ and $\\frac{B_1}{B_2}$ if the placeholders $A_i$ and $B_i$ are not further sampled to be the same variables respectively. In such a case, would the synchronization of the equivalent terminals' backpropagation regarding the visit counts also affect these non-equivalent intermediate nodes (i.e., more number of visits if they have equivalent terminals), so that they might have biased UCT selections?\n\nI'm happy to change my score if the above concerns and questions are properly addressed.", "limitations": "", "rating": 2, "confidence": 5, "soundness": 1, "presentation": 1, "contribution": 2, "strengths": "1. **Significance**: The paper focuses on an important and fundamental problem in symbolic regression (SR), and the introduced e-graph is reasonable for equivalence-aware SR frameworks.\n\n2. **Multiple Backends:** The paper conducts e-graphs on several learning/search methods (MCTS, DRL, and LLM) to show a universal advantage of capturing expression equivalences in SR methods.", "weaknesses": "1. **Novelty:** Though the e-graph is new in SR, similar ideas of using graph-based representations to capture expression equality have already been studied for SR. For example, Expression DAGs [1] include the same idea of sharing sub-expressions in DAGs for expression equality. The paper lacks a sufficient literature review on this topic to differentiate its novelty and contribution.\n\n2. **Potentially Biased UCT Search**: The proposed EGG back-propagation in MCTS might lead to biased UCT selections, see Question 2.\n\n3. **Experimental Soundness:** The whole experimental section can be regarded as an ablation study, which only focuses on implementing typical baselines with or without EGG on datasets with abundant equivalencies. However, benchmarkings on widely adopted general datasets (e.g., SRBench [2]) with relevant prevailing baselines (e.g., SPL [3] for MCTS and uDSR [4] for DRL) are missing, which cannot support the claim \"EGG-SR ... discovering equations with lower normalized mean squared error than *state-of-the-art* methods\" in the abstract. Especially, the *state-of-the-art* methods could include many transformer-based methods, such as TPSR[5], RAG-SR[6], and also DGSR [7], an E2E transformer model to encode expression equivalences.\n\n4. **Clarity:** There are some confusing definitions and notations, see Question 1.\n\n[1] Kahlmeyer, Paul, et al. \"Scaling up unbiased search-based symbolic regression.\" Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence. 2024.\n\n[2] La Cava, William, et al. \"Contemporary symbolic regression methods and their relative performance.\" Advances in neural information processing systems 2021.DB1 (2021): 1.\n\n[3] Sun, Fangzheng, et al. \"Symbolic Physics Learner: Discovering governing equations via Monte Carlo tree search.\" The Eleventh International Conference on Learning Representations.\n\n[4] Landajuela, Mikel, et al. \"A unified framework for deep symbolic regression.\" Advances in Neural Information Processing Systems 35 (2022): 33985-33998.\n\n[5] Shojaee, Parshin, et al. \"Transformer-based planning for symbolic regression.\" Advances in Neural Information Processing Systems 36 (2023): 45907-45919.\n\n[6] Zhang, Hengzhe, et al. \"RAG-SR: Retrieval-augmented generation for neural symbolic regression.\" The Thirteenth International Conference on Learning Representations. 2025.\n\n[7] Holt, Samuel, Zhaozhi Qian, and Mihaela van der Schaar. \"Deep Generative Symbolic Regression.\" The Eleventh International Conference on Learning Representations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "su2ia5Mh1m", "reviewer": "Reviewer_A6nL", "summary": "This paper presents EGG-SR, a unified framework that addresses the underexplored problem of symbolic equivalence in symbolic regression (SR). The core idea is to integrate equality graphs (e-graphs) to compactly represent equivalent expressions, thereby reducing redundant search. The authors demonstrate the versatility of EGG-SR by embedding it into three distinct SR paradigms: Monte Carlo Tree Search (MCTS), Deep Reinforcement Learning (DRL), and Large Language Models (LLMs). Theoretical analysis shows tighter regret bounds for MCTS and lower gradient variance for DRL. Empirically, the EGG module consistently enhances baseline performance across various benchmarks, leading to the discovery of expressions with lower normalized mean squared error.", "questions": "Concerns and questions are described in \"Weaknesses\".", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "**Novel and Important Problem Formulation**:​​ The paper successfully identifies and tackles the fundamental issue of symbolic equivalence, a significant source of inefficiency in SR that has been largely overlooked. This focus is timely and valuable.\n\n​**High Methodological Innovation**:​​ The primary strength is the proposal of a unified, plug-and-play framework (EGG-SR) rather than a single algorithm. Its applicability across diverse paradigms (MCTS, DRL, LLM) demonstrates remarkable generality and conceptual elegance.\n\n**​Strong Theoretical and Empirical Validation**:​​ The work is supported by non-trivial theoretical guarantees, which substantiate the method's benefits. The experiments are comprehensive, convincingly showing performance improvements across multiple baselines and datasets. The inclusion of efficiency analyses (time/space) and rich e-graph visualizations strengthens the empirical contribution.", "weaknesses": "**Dependence on Manually Defined Rewrite Rules**:​​ The effectiveness of EGG-SR currently relies on a pre-defined set of rewrite rules. The framework's power and generality could be further amplified by exploring methods to learn or automatically discover these rules from data, as noted by the authors in the conclusion.\n\n**Writings**: There is a significant distance between Figure 1 and the corresponding explanatory text (Section 3.1). To improve the reader's flow, I suggest moving the figure closer to its initial description or adding a cross-reference (e.g., \"as illustrated in Figure 1\") when it is first mentioned in the text. Plus, there appears to be an error in the reported minimum value for the second column under the \"noisy setting\" in Table 1.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "PKSUjdeLFC", "reviewer": "Reviewer_b8v3", "summary": "The paper introduces EGG-SR, a framework designed to improve the efficiency and effectiveness of Symbolic Regression (SR). The core problem addressed is that existing SR algorithms inefficiently explore the search space by treating syntactically different but semantically equivalent expressions as distinct candidates. EGG-SR integrates equality graphs (e-graphs) to compactly represent and manage these symbolic equivalences within a grammar-based SR setting.", "questions": "1. The framework's success depends on the manually curated set of rewrite rules. (a) How was the rule set for the trigonometric benchmarks in Table 1  selected? Was it designed specifically for those problems? (b) How does EGG-SR's performance degrade if key rewrite rules are omitted from the set?\n\n2. Regarding the time-efficiency in Figure 5, how does the \"EGG construction\" time scale with (a) the complexity (e.g., length or depth) of the initial expression and (b) the total number of rewrite rules in the system?\n\n3. For the EGG-LLM method, how are the equivalent expressions for the feedback prompt selected from the e-graph? Do you use cost-based extraction, random sampling, or some other heuristic? How many equivalent expressions are added, and how are they formatted in the prompt to effectively guide the LLM?\n\n4. Could you please clarify the result in Figure 3 (Left)? Why does EGG-MCTS, which is designed to avoid redundant exploration, result in a larger total search tree than standard MCTS? Does merging equivalent nodes (and sharing their visit counts/rewards) encourage a deeper, more focused search down promising paths, thus leading to a larger total node count even as redundant branches are eliminated?\n\nI am willing to raise my score if the authors can satisfactorily address all the concerns outlined in the weaknesses and questions above.", "limitations": "", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- **Originality**: While e-graphs and their application to SR are not entirely new (as noted in the related works ), this paper's contribution is a novel and highly general framework. Applying the equivalence concept systematically to MCTS (search pruning), DRL (variance reduction), and LLMs (prompt enrichment) is a creative and powerful combination of ideas. The DRL variance reduction and LLM feedback mechanisms are particularly original.\n\n- **Quality**: The paper is technically strong. The theoretical claims are well-supported by proofs in the appendix that build on established literature (e.g., Rao-Blackwellization for DRL variance ). The empirical evaluation is thorough and convincing. The authors test their claims across all three proposed algorithm variants and find consistent improvements. Crucially, they include practical analyses of memory and time overhead (Figures 4 and 5), which demonstrate the method's feasibility.\n\n- **Clarity**: The paper is exceptionally well-written. The problem is motivated with a clear, simple example ($log(x_{1}^{2}x_{2}^{3})$) 16 that is carried through the text. The methodology is explained clearly, with helpful diagrams for the e-graph construction (Figure 1) 17, the MCTS process (Figure 2) 18, and the LLM pipeline (Figure 8)19. The distinction between the baseline algorithms and their EGG-enhanced counterparts is sharp and easy to grasp.\n\n- **Significance**: This work addresses a fundamental and widely recognized source of inefficiency in symbolic regression. Because the EGG-SR framework is shown to be effective across diverse SR methods (search, DRL, LLM) and practical (low overhead), it has the potential for broad impact. It provides a \"drop-in\" enhancement that could benefit a wide range of existing and future SR systems.", "weaknesses": "- The process of building the e-graph, \"equality saturation\", involves iteratively applying all rules. While the storage is efficient (Figure 4), the construction time could become a bottleneck for very complex expressions or a very large set of rewrite rules. Figure 5  shows the overhead is negligible for one dataset, but it does not analyze how this construction time scales with expression complexity or the number of rules.\n- The claim for EGG-MCTS is that it \"prunes redundant subtree exploration\". However, Figure 3 (Left)  shows that EGG-MCTS explores a larger search tree (more nodes) than standard MCTS. The paper states this indicates exploration of a \"larger and more diverse search space\", but this seems to contradict the \"pruning\" claim and is confusing. A clearer explanation is needed.\n\n- The related work section (Section 4) is incomplete and overlooks several significant, recent advancements in symbolic regression. While the paper covers the main paradigms, it omits highly relevant work on generative and transformer-based SR models [2, 3, 4].\nA more critical omission is the lack of any discussion or comparison with DySymNet [1]. This method is highly relevant to the present work, as DySymNet also employs a policy gradient approach (similar to EGG-DRL) to dynamically construct symbolic networks and has demonstrated strong performance, particularly on high-dimensional problems. The paper would be significantly strengthened by:\n\n    - Including this and other recent works [2, 3, 4] to provide a more comprehensive and up-to-date overview of the field.\n\n    - Providing at least a detailed conceptual comparison, and ideally an empirical one, between EGG-DRL and DySymNet. This is necessary to properly contextualize the DRL-based contribution of EGG-SR.\n\n[1] Li W, Li W, Yu L, et al. A Neural-Guided Dynamic Symbolic Network for Exploring Mathematical Expressions from Data, ICML 2024\n\n[2] Holt S, Qian Z, van der Schaar M. Deep generative symbolic regression, ICLR 2023\n\n[3] Li W, Li W, Sun L, et al. Transformer-based model for symbolic regression via joint supervised learning, ICLR 2023\n\n[4] Shojaee P, Meidani K, Barati Farimani A, et al. Transformer-based planning for symbolic regression, NeurIPS 2023", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)