acceptodds
Under review as a conference paper at ICLR 2027

Pareto Fronts for Symbolic Regression: Traversal Search towards the Frontier

Abstract

Symbolic regression (SR) seeks compact mathematical expressions that balance predictive accuracy and model complexity, but the combinatorial growth of the expression space makes effective search challenging. This work makes two contributions: (i) we find Pareto fronts for SR benchmarks extended up to length 21 and (ii) we leverage the results of the Pareto front generation to develop a structured traversal SR search framework over explicitly defined topology-conditioned symbolic landscapes. For the first contribution, we combine tree topology enumeration with capped sampling of node labels to construct longer expressions, extending empirical accuracy–complexity Pareto fronts to expression lengths up to 21. For the second contribution, we develop traversal search over expression states within tree topologies, using multistart n-mutation search and beam search to explore mutation neighborhoods. Our central novelty is an explicit formulation of expression states and mutation neighborhoods within tree topologies, enabling traversal strategies to be evaluated against reference ranks and empirical Pareto fronts while finding high quality expressions with a small fraction of the evaluations required for exhaustive search. On representative benchmarks, our approach identifies expressions close to the empirical reference fronts, achieving competitive predictive performance with lower complexity than many SR algorithms in SRBench. We perform systematic comparisons of traversal search configurations to provide insight into effective strategies for locating highly ranked expressions and the relationship between traversal search quality and evaluation efficiency. We further examine training–test alignment to complement the evaluation of traversal search performance. Together, these contributions extend empirical accuracy–complexity frontiers to larger expression spaces and show how the resulting topology-conditioned landscapes can be exploited for efficient traversal search. By establishing an empirical reference for what is attainable within the explored search space, we provide a concrete target for algorithm development, allowing algorithms to be evaluated by how effectively they approach known high quality solutions rather than only by comparison with existing algorithms.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
Symbolic regression, Pareto Fronts, Search Algorithms

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_AXF6OpenReview ↗
Rating
2
Confidence
4
Informativeness
1
Presentation
3
Soundness
1
Read review
Paper summary
  • The paper extends empirical accuracy-complexity fronts to expressions of length 21 on 32 PMLB datasets using exhaustive topology enumeration and capped label sampling.
  • It searches fixed tree topologies by changing node labels with multistart single/n-mutation search and beam search.
  • The experiments compare search quality, evaluation counts, train-test alignment, and archived SRBench results.
Critical strengths
  1. The explicit state space and mutation neighborhoods make the search method easy to understand and analyze.
  2. The evaluation-count formulas and comparisons across mutation orders clearly show the cost-quality tradeoff.
  3. The train-test alignment analysis usefully shows that improving training rank does not always improve generalization.
Critical weaknesses
  1. The reported test Pareto front selects the best test score among extremely large expression libraries. This repeatedly uses the test set for model selection and creates an optimistic test oracle, so it is not a valid reference for generalization or comparison with SRBench.
  2. The efficiency comparison counts cheap lookups in a precomputed vault but excludes candidate generation, simplification, constant fitting, and scoring. Comparing this count with SRBench's end-to-end 500,000-evaluation budget is therefore not fair.
  3. The fronts above length 9 are sampled rather than exhaustive, yet sampling uncertainty and sensitivity to the cap are not reported. The SRBench comparison also lacks matched budgets and statistical tests.
Questions for authors
  1. Can the authors rebuild the fronts using validation performance for selection and reserve the test set for one final evaluation? How much do the conclusions change?
  2. What are the complete compute and evaluation costs, including construction of the vault and optimization of constants, under a budget matched to the SRBench methods?
  3. How stable are the length-11-to-21 fronts across sampling seeds and caps?
2 comments
AuthorsOpenReview ↗

Response to Reviewer AXF6 (1/2)

We thank the reviewer for the careful assessment. The paper makes two contributions: 1). The resource contribution is the reference library up to length 21 with test oracle and train selected fronts for every dataset and a sampling stability analysis. 2). The new method contribution is traversal search, which evaluates a median of 0.11% of the length-9 library, exceeds a budget-matched random search in test R2R^2 on 26 of 32 datasets, and is significantly more accurate than 3 of the 14 SRBench methods while no method is significantly more accurate than it. In response to the reviewer's request, we also make a new generalization reference based on only the train set, please note that this is not the same as the test oracle front in the first contribution.

W1. We thank the reviewer and agree that the green curve, which selects by test score, is a test oracle rather than a generalization estimate. The revision renames it the test oracle front and keeps it as an upper bound for any method that selects from this library, whatever criterion the method selects by. In this role it supplements SRBench as a reference for the best accuracy attainable within the library. The revision also rephrases the word 'exceed' and instead refers to the front as a test oracle.

Q1. Continuing from W1, we also provide a new generalization reference as requested, where every dataset's figure adds a train selected front, which takes the expression with the highest training R2R^2 at each length limit and evaluates it once on the test set. At length 9 this front equals exhaustive training-based selection over the library. Traversal search shows no significant difference from it (median paired difference −0.003, Wilcoxon p=0.26p = 0.26) while evaluating a median of 0.11% of the library, and with s=10s = 10 starts (0.51% of the library) the difference falls below 10−410^{-4} in magnitude.

The added train selected front reserves the test set for one final evaluation and selects on the training data alone. Any search that maximizes training R2R^2 over the library returns this expression once it reaches the training optimum, so the front shows how well the best training fit generalizes. When selection uses no test data, the median gain from length 9 to 21 falls from 0.053 to 0.022 over all 32 datasets (Wilcoxon p=0.07p = 0.07 for the train selected gain). The gain is significant on the 24 datasets with more than 100 samples (17 improve, p=0.002p = 0.002). A validation selected front answers the complementary question of held-out model selection, which is also valuable, and we plan to add it to the benchmark.

W2 / Q2. We thank the reviewer. Table 3 reports the end-to-end runtime of our on-demand search alongside the archived SRBench training times. Over 3,200 runs (32 datasets, 10 splits and 10 seeds, with s=2s = 2 and R=10R = 10), traversal search performs 3,337 evaluations per run on average and evaluates a median of 0.11% of the length-9 library. With every constant fitted at run time, a run takes a median of 40 s of wall-clock time on one CPU core. The revision reports this evaluation count and the measured run time in place of the comparison with SRBench's limit of 500k evaluations. While running the on-demand variant, we noticed that the evaluation count in the submission counted a simplified skeleton again whenever it was reached through another raw expression or by another trajectory. The revision counts the distinct simplified skeletons with a valid fit in each run, and reports all evaluation counts on this basis.

AuthorsOpenReview ↗

Response to Reviewer AXF6 (2/2)

On the SRBench comparison raised in W3, the revision adds paired significance tests against the 14 SRBench methods (Table 3) and a random search baseline whose budget matches each run exactly. Two-sided Wilcoxon signed-rank tests over the 32 datasets, with Holm correction for the 14 comparisons, show that traversal search is significantly more accurate than BSR, MRGP and AIFeynman. No SRBench method is significantly more accurate than traversal search. Every SRBench method returns larger models in the median, from 9.25 nodes for DSR to 6,124.5 for MRGP, whereas traversal search returns expressions of at most 9 nodes by design. The budget-matched baseline pairs each run with a random search that draws the same number of expressions from the same length-9 library, 3,337 on average, and keeps the one with the highest training R2R^2. Over 1,000 repetitions, traversal search exceeds the median random search result on 26 of 32 datasets with a median test R2R^2 gain of 0.038 (Wilcoxon p=2.8×10−5p = 2.8 \times 10^{-5}). The archived SRBench results were produced under the budgets set by SRBench, with median training times from 66 s to 1.6×1051.6 \times 10^{5} s.

The 40 s per run reported above covers the whole search, namely candidate generation, simplification, constant fitting and training set scoring. Library construction adds nothing to this figure because the on-demand search reads no precomputed fit, so the library is a reusable benchmark asset rather than a component of the method. The length-9 library is the public POVE library (Fong & Motani, KDD 2025), which was computed once and serves every algorithm benchmarked on it. Lookups in the POVE library shorten the same search to a median of 1.5 s per run. The revision adds a comparison with gplearn (Appendix D). gplearn runs with a population of 100 for 70 generations, giving 7,000 evaluations per run. We chose this budget as a round number slightly above the largest number of evaluations used by any of the 3,200 runs of traversal search with s=2s = 2 and R=10R = 10 (6,787), so that gplearn never receives fewer evaluations than our search, 2.1 times as many on average. Traversal search attains a higher test R2R^2 than gplearn on 27 of the 32 datasets (Wilcoxon p=8.1×10−7p = 8.1 \times 10^{-7}) and a higher training R2R^2 on all 32.

W3 / Q3. We thank the reviewer and have added a new sampling stability analysis of the fronts above length 9 (Appendix B, Figures 8–9 and Table 6) as requested. The results show stability in the test oracle front. In every random half of the sampled lists, the test oracle front gains more than 0.01 R2R^2 from ℓ=9\ell = 9 to ℓ=21\ell = 21 on at least 30 of the 32 datasets. Regenerating a list with a new seed would require fitting 10710^{7} new expressions for every dataset and split, so two disjoint random halves of each sampled list, with 5×1065 \times 10^{6} expressions each, serve as a proxy for a new sampling seed. Because all datasets with the same number of features share the list at each length, each of 50 random partitions is applied jointly to all of them. Under this seed proxy, the test oracle and training fronts of the two halves at ℓ=21\ell = 21 differ by a median of 0.003 R2R^2, and the median ratio of this difference to each dataset's own 9→219 \to 21 gain is 7–8% (Table 6, panel B). The training front gives the highest training R2R^2 among library expressions of length at most ℓ\ell. The per-dataset median difference stays below 0.01 on 26 of 32 datasets. At every length from 11 to 21, the median difference between the two halves is at most 0.004 R2R^2 for both fronts. Across caps, randomly capping every file at 5×1065 \times 10^{6}, 2×1062 \times 10^{6} or 10610^{6} expressions lowers the ℓ=21\ell = 21 test oracle front by a median of 0.002, 0.009 and 0.013, respectively, so the effect of the cap shrinks as the cap approaches 10710^{7}. Across 100 halves, the median 9→219 \to 21 gain spans 0.0427–0.0525 for the test oracle front and 0.0395–0.0469 for the training front, and with 10610^{6} expressions per sampled list the test oracle gain exceeds 0.01 on at least 28 datasets (Table 6, panel A).

Reviewer_qYc1OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies accuracy–complexity reference fronts and traversal search for symbolic regression. It extends empirical expression libraries on 32 PMLB datasets to expression length 21 through topology enumeration and capped sampling of labels. It also defines search over fixed tree topologies and compares multistart single-node mutation, beam search, and joint mutations of multiple positions. Fitness is based on training R², with constants fitted on the training data and fitness values retrieved from a precomputed vault. The selected expression is subsequently evaluated on the test set. The reported traversal experiments use length 9. The paper investigates training–test rank alignment, search budgets, training-optimum recovery, and comparisons with archived SRBench results.

Critical strengths
  1. A useful resource and controlled experimental setting. Extending the empirical reference library to length 21 can help researchers assess accuracy–complexity tradeoffs beyond comparisons between a few heuristics. The study covers 32 datasets, multiple splits and search seeds, and presents all dataset fronts across the main paper and appendix. Holding the fitted expression scores fixed also provides a useful setting for investigating the query behavior of different search procedures.

  2. Careful attention to generalization and search tradeoffs. Section 4.1 distinguishes expression identity, cross-ranking, and actual test-score differences rather than assuming that the training optimum is also the best generalizing model. The paper reports cases of imperfect training–test alignment and nonmonotonic test-rank behavior with larger budgets. Table 5 further separates training-optimum recovery from evaluation cost and shows the diminishing efficiency of higher-order mutations. These analyses are useful even where the proposed variants do not uniformly improve performance.

Critical weaknesses

The central empirical comparisons do not yet establish the benefit of the traversal procedure under a fully specified, matched-budget protocol. Most critically, Section 4.3 derives the expected best rank for uniform sampling without replacement and correctly warns against treating a test ranking as an oracle-free baseline. However, the manuscript does not explain the complete procedure that produces the baseline test R² shown in Figures 1–6 and used for the 25/32 wins and median improvement of 0.0362. The expected best training rank alone does not determine the selected expression’s expected test score, and it also does not directly define the nested medians used for the search results. The selection probabilities, training-to-test expression correspondence, sampling unit, tie handling, and per-run budget need to be explicit. This remains an unresolved protocol issue; the implementation may preserve the required correspondence, but the manuscript does not provide enough detail to verify it. The efficiency comparison has a related limitation. The reported mean of 3,963 evaluations is compared with the historical SRBench limit of 500,000, while the present experiment retrieves already fitted scores. The exclusion of precomputation from the reported runtime is disclosed, and the setting is valuable for studying query efficiency. Nevertheless, actual vault queries and another method’s maximum fitness-evaluation allowance are not directly comparable computational costs. A budget-matched random/local-search comparison in the same space, with clear caching and fitting accounting, is needed to isolate the search benefit; a representative on-demand experiment would strengthen claims about practical computation. These issues also affect the assessment of the incremental contribution relative to the closest cited work. The additional benefit of random multistart traversal, beam search, and joint mutations needs to be isolated more clearly. Moreover, the reference library reaches length 21 while every traversal experiment remains at length 9. The contribution of the longer library is plausible, but the current results do not establish traversal scalability in that extended space.

Questions for authors

1、How exactly are the random-baseline test R² values in Figures 1–6 computed? Please specify N, K for each run/split, the sampling unit and tie handling, training-based selection, the mapping to the same expression’s test score, and the aggregation over repetitions and splits. Can you provide an empirical baseline with matched query budgets and the same selection/aggregation protocol, or a complete equivalent analytical construction?

2、What counts as one evaluation, including initial states, repeated raw states, duplicate simplified expressions, cache hits, and constant fitting? Which POVE fitting/preprocessing conventions are inherited by the current experiments and the new library? Please clarify the claim supported by comparison with the 500,000-evaluation cap; a small same-grammar, same-fitting, on-demand comparison would help assess practical cost.

3、Which conclusions go beyond the analysis in Fong and Motani, ICML 2025, Section 4.3 and Appendix I? Please distinguish the new reference resource from the search contribution. Can a representative length-11/13 study, including treatment of neighbors absent from the sampled vault, support the connection to the longer space, or should the scope of the traversal claims be restricted to length 9?

4、How consistent are the Table 5 improvements across datasets and splits, at comparable query budgets? Please provide paired per-dataset effects and suitable uncertainty estimates for recovery and efficiency. For Section 4.5, are starts/random streams shared across budgets, and how large are the corresponding test-R² changes?

3 comments
AuthorsOpenReview ↗

Response to Reviewer qYc1 (1/3)

Q1. We thank the reviewer for their comment. In our response, we clarify what the reviewer has asked and present a new empirical Monte Carlo baseline, as requested.

In the original submission, the Baseline in Figures 1–6 was a computed analytical aggregate value. For each run, KK was the run's recorded evaluation count and NN the number of expressions in the length-9 library (all expressions up to length 9), and the plotted value was the test R2R^2 of the expression at training rank round((N+1)/(K+1))\mathrm{round}\bigl((N+1)/(K+1)\bigr) in the library sorted by training R2R^2, with the median taken over 10 seeds and then over 10 splits, as for Ours. As the reviewer notes, the expected best training rank does not determine the expected test score of the selected expression, so the revision replaces this computed analytical aggregate with a fully specified empirical random search (protocol below) and applies the expected rank formula of Section 4.3 to training ranks, where it is exact. With the same number of evaluations, the formula gives a uniform random search an expected best training rank of 1,026 (median over datasets), whereas traversal search reaches a median training rank of 16. Grouped by the number of features, the expected best rank of the random search grows from 76 for 2 features to 4,684 for 7 features, whereas the median training rank of traversal search stays between 10.5 and 33.5 (Appendix Table 7).

The new Monte Carlo empirical random baseline uses the same budget, selection and aggregation as traversal search. The sampling unit is one row of the length-9 library, that is, one distinct simplified skeleton with its fitted constants. NN is the number of rows, which depends on the number of features dd alone and equals 110,849, 582,193, 2,014,469, 5,436,079, 12,434,549 and 25,278,681 for d=2d = 2 to 7. For each run (one split and one seed), KK equals the number of evaluations that traversal search performed in that run, 3,337 on average. The random search draws KK rows uniformly without replacement, returns the row with the highest training R2R^2, and reports the test R2R^2 of that same row, so selection never uses test data. Rows with non-finite training R2R^2 rank last, and ties in training R2R^2 are ordered by a random permutation drawn once per split. The best training rank Rmin⁡R_{\min} of such a draw follows the exact distribution P(Rmin⁡=r)=(N−rK−1)/(NK)P(R_{\min} = r) = \binom{N-r}{K-1} \big/ \binom{N}{K}, and the Monte Carlo procedure samples Rmin⁡R_{\min} directly from this distribution, which is equivalent to drawing the KK rows. Aggregation matches that of traversal search, with the median over the 10 seeds within each split followed by the median over the 10 splits. The procedure is repeated 1,000 times, and the baseline is the median of the 1,000 nested medians. Under this protocol, traversal search exceeds the baseline on 26 of 32 datasets with a median test R2R^2 gain of 0.038 (Wilcoxon p=2.8×10−5p = 2.8 \times 10^{-5}). The revision uses this baseline in Figure 1 and Figures 3–7, introduces it in Section 4.3 and states the full protocol in Appendix C.

AuthorsOpenReview ↗

Response to Reviewer qYc1 (2/3)

Q2. Thanks for the comment. We agree that lookups in a library of prefitted expressions and another method's allowance of fitness evaluations are not comparable computational costs. The revision now reports the actual number of evaluations and the measured run time instead. To this end, the revision adds an on-demand variant of traversal search that fits every constant at run time with the same grammar, data splits, standardization and BFGS fitting as the library. Over 3,200 runs with s=2s = 2 and R=10R = 10, traversal search performs 3,337 evaluations per run on average and evaluates a median of 0.11% of the length-9 library. With every constant fitted at run time, a run takes a median of 40 s of wall-clock time on one CPU core. The budget-matched comparison in the same space is the random search of Q1, which samples the same library of distinct skeletons that traversal search explores, using each run's actual number of evaluations, so caching and fitting are accounted for identically in both procedures. Under this comparison, traversal search wins on 26 of 32 datasets in test R2R^2 and reaches a median training rank of 16, against an expected best training rank of 1,026 for a uniform random search with the same number of evaluations. Comparisons among the local search variants at matched budgets appear in the response to Q4.

While running the on-demand variant, we noticed that the evaluation count in the submission counted a simplified skeleton again whenever it was reached through another raw expression or by another trajectory. The revision counts the distinct simplified skeletons with a valid fit in each run, and reports all evaluation counts on this basis. In this count, starting expressions are included, a skeleton reached again within the same run reuses its fit and is not counted again, and invalid skeletons, which divide by zero on the given split, are not counted. The experiments and the new library inherit all POVE fitting and preprocessing conventions.

Q3. Regarding Fong and Motani (ICML 2025), their Section 4.3, motivated in their Appendix I, starts from expressions two mutations away from an APO front expression and applies two greedy single-step mutations to test whether the front expression is recovered, with an average success rate of 23.7%. Our paper studies traversal as a complete search algorithm and evaluates it systematically, covering multistart traversal from random starting expressions, termination rules, beam and nn-mutation search within one framework, bounds on neighborhood sizes and evaluation counts, quality-cost tradeoffs under counted budgets (Table 5 and Section 4.5), training-test analysis of the search outputs, and statistical comparisons with a budget-matched random search and 14 SRBench methods.

The paper makes two contributions: 1). The resource contribution is the reference library up to length 21 with test oracle and train selected fronts for every dataset and a sampling stability analysis. 2). The new method contribution is traversal search, which evaluates a median of 0.11% of the length-9 library, exceeds a budget-matched random search in test R2R^2 on 26 of 32 datasets, and is significantly more accurate than 3 of the 14 SRBench methods while no method is significantly more accurate than it.

The revision adds on-demand traversal at lengths 11 and 13 on all 32 datasets in Appendix F, with the single-mutation setting of length 9 (s=2s = 2, R=10R = 10) and the expression length changed alone. Every visited expression is fitted at run time, so neighbors absent from a sampled list are fitted directly. At both lengths, the test R2R^2 of traversal search reaches the level of training-based selection on the library and shows no significant difference from the train selected front of the same length (median paired differences 0 and −0.0015, Wilcoxon p=0.99p = 0.99 and 0.20). Of the 3,200 runs at each length, 237 and 650 also return an expression absent from the library whose training R2R^2 exceeds that of every library expression up to that length. Traversal search therefore extends to longer expressions.

AuthorsOpenReview ↗

Response to Reviewer qYc1 (3/3)

Q4. The revision adds Wilcoxon tests across datasets and hierarchical bootstrap confidence intervals for the Table 5 comparisons to the appendix (Table 9), at comparable query budgets. Every comparison uses the same datasets, splits and seeds. Three pairs also start from identical expressions, namely beam search with (G,w)=(5,3)(G, w) = (5, 3) and single-mutation search with s=15s = 15, beam (5, 2) and single s=10s = 10, and 3-mutation and 2-mutation search with s=1s = 1, so the differences within these pairs reflect the search strategy itself. Beam (5, 3) and beam (5, 2) use 5.0% and 2.9% fewer evaluations than single s=15s = 15 and single s=10s = 10, and 2-mutation search with s=1s = 1 uses 0.1% fewer than single s=15s = 15, so these comparisons run at comparable budgets. At R=3R = 3, the gains of beam (5, 3) over single s=15s = 15 are consistent across datasets. Its p^1\widehat p_1 is 3.8 points higher (95% CI 2.0–5.6) and higher on 26 of 32 datasets (Wilcoxon p=1.7×10−4p = 1.7 \times 10^{-4}). Its mean training rank is better on 31 datasets (p=9.2×10−7p = 9.2 \times 10^{-7}) and in 254 of the 320 dataset-split cells. Its recovery efficiency Y1Y_1 rises by 23.0% (95% CI 14.3–35.4%) and is higher on 27 datasets (p=2.9×10−5p = 2.9 \times 10^{-5}). Beam (5, 2) raises p^1\widehat p_1 over single s=10s = 10 on 19 datasets (p=0.023p = 0.023) and Y1Y_1 by 13.5% (3.7–22.9%), with Y1Y_1 higher on 23 datasets (p=0.0022p = 0.0022). 2-mutation search with s=1s = 1 raises p^1\widehat p_1 over single s=15s = 15 on 21 datasets (p=0.0068p = 0.0068) and Y1Y_1 by 25.3% (7.8–53.4%), with Y1Y_1 higher on 24 datasets (p=5.4×10−5p = 5.4 \times 10^{-5}).

To separate the components at matched budgets, the revision compares the configurations within the budget range of single-mutation search with the envelope of all 18 single-mutation configurations at the same number of evaluations and lists the configurations above it in panel B of Appendix Table 9. The gain of random multistart traversal itself over random sampling appears in Q1. Four beam configurations exceed the single-mutation envelope at the same number of evaluations, namely beam (5, 2) with R=8R = 8 and R=10R = 10, beam (5, 4) with R=5R = 5 and beam (5, 3) with R=10R = 10, by 5.8, 9.6, 7.1 and 15.0 points of p^1\widehat p_1 (95% CIs 2.9–10.8, 5.9–16.7, 0.7–9.9 and 8.4–18.5). Single-mutation search would need 42% more evaluations to reach the p^1\widehat p_1 of beam (5, 2) with R=10R = 10, and the 60.5% of beam (5, 3) with R=10R = 10 exceeds every single-mutation configuration. nn-mutation search extends the frontier to the highest recovery rates in the study, 69.8% for 2-mutation search with s=5s = 5 and 75.1% for 3-mutation search with s=2s = 2 at R=10R = 10, with budgets above those of every beam and single-mutation configuration. The revised Table 5 reports evaluation counts and Y1Y_1 with evaluations counted as defined in Q2.

For Section 4.5, yes. The random generator is used for the starting expressions and nowhere else, and the search is deterministic thereafter, so all budgets share their starts and random streams, and a run with RR rounds is a prefix of the run with 10 rounds. Across the 12,800 pairs of adjacent budgets in Section 4.5 (32 datasets with 100 runs each and 4 adjacent pairs of round limits), the best training R2R^2 never decreases. The shared starts also pair the test-R2R^2 changes run by run. From 2 to 10 rounds, the test R2R^2 rises in 1,498 of 3,200 runs and falls in 778, with the remaining 924 unchanged (change within 10−610^{-6}). The median paired change is positive on 16 datasets, negative on 3 and unchanged on 13 (Wilcoxon p=0.0013p = 0.0013), ranging from −0.039 on 687_sleuth_ex1605 to +0.089 on 529_pollen. For example, the mean test R2R^2 of 557_analcatdata_apnea1 rises from 0.865 to 0.910, while that of 1027_ESL changes little after 4 rounds. Runs whose test R2R^2 falls reflect training-test misalignment (Section 4.1) rather than different random starts. The revision states the shared starts in Section 4.5 and adds these paired comparisons.

Reviewer_F1meOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper extends empirical accuracy–complexity Pareto fronts for symbolic regression to expressions of length 21 on 32 PMLB datasets. It also introduces a topology-conditioned traversal framework based on multistart single-/nn-mutation search and beam search.

Critical strengths

Strengths:

  1. The paper studies accuracy, expression complexity, and search cost jointly.

  2. The experiments cover 32 datasets and multiple train–test and search seeds.

  3. The training–test alignment analysis is useful and appropriately shows that better training ranks do not always imply better generalization.

  4. Candidate-evaluation counts make the comparison between search configurations relatively transparent.

Critical weaknesses

Weaknesses:

  1. The length-11-to-21 Pareto fronts are based on capped sampling, but their stability across different samples is not evaluated.
  2. The claim that all expressions below length 11 are retained is unclear given the potentially much larger raw search space; exact counts after simplification and deduplication are needed.
  3. The reported runtime excludes vault construction and constant optimization, so the end-to-end computational cost remains unclear.
  4. The reference fronts use test R2R^2 for selection and should only be treated as oracle references, not direct evidence of superiority over SRBench.
  5. Algorithm 1 does not explicitly consider the initial states when updating e⋆e^\star, and the evaluation bounds omit their cost.
Questions for authors

Please refer to the weaknesses.

4 comments
AuthorsOpenReview ↗

Response to Reviewer F1me (1/2)

We thank the reviewer for the careful assessment and for recognizing the joint study of accuracy, expression complexity and search cost, the training-test alignment analysis, and the transparency that evaluation counts bring to the comparisons. The paper makes two contributions: 1). The resource contribution is the reference library up to length 21 with test oracle and train selected fronts for every dataset and a sampling stability analysis. 2). The new method contribution is traversal search, which evaluates a median of 0.11% of the length-9 library, exceeds a budget-matched random search in test R2R^2 on 26 of 32 datasets, and is significantly more accurate than 3 of the 14 SRBench methods while no method is significantly more accurate than it.

W1. The revision adds a sampling stability analysis of the fronts above length 9 (Appendix B and Figures 8–9). Regenerating a list with a new seed would require fitting 10710^{7} new expressions for every dataset and split, so two disjoint random halves of each sampled list, with 5×1065 \times 10^{6} expressions each, serve as a proxy for a new sampling seed, with 50 such partitions drawn. Under this seed proxy, the test oracle and training fronts of the two halves at ℓ=21\ell = 21 differ by a median of 0.003 R2R^2, and the per-dataset median difference stays below 0.01 on 26 of 32 datasets. The training front gives the highest training R2R^2 among library expressions of length at most ℓ\ell. At every length from 11 to 21, the median difference between the two halves is at most 0.004 R2R^2 for both fronts. Across 100 halves, the median gain of the test oracle front from length 9 to 21 spans 0.0427–0.0525, against 0.0529 for the full library. With 10610^{6} expressions per sampled list, the test oracle front gains more than 0.01 on at least 28 of 32 datasets.

W2. For lengths below 11, the Library size column of Table 7 in Appendix C gives the exact number of distinct simplified expressions for each feature count. Expressions up to length 9, and up to length 11 for datasets with at most 3 features, come directly from the public POVE library, which enumerates them exhaustively and stores each simplified expression once (Fong & Motani, KDD 2025, Section 3.1), so the cap does not apply to them. Table 3 of that paper lists the exact number of expressions for every dataset, from 2.0×1062.0 \times 10^{6} to 2.5×1072.5 \times 10^{7}. Each longer length ℓ\ell adds one sampled list of 10710^{7} expressions generated from topologies of length ℓ\ell per number of features.

W3. We agree that runtimes measured with lookups do not show the end-to-end cost. The revision therefore adds an on-demand variant of traversal search that fits every constant at run time with BFGS. Over 3,200 runs at length 9 (32 datasets, 10 splits and 10 seeds, with s=2s = 2 and R=10R = 10), traversal search performs 3,337 evaluations per run on average. The on-demand variant takes a median of 40 s of wall-clock time per run on one CPU core. This time covers the whole search, namely candidate generation, simplification, constant fitting and training set scoring. Library construction adds nothing to this cost because the on-demand search reads no precomputed fit, so the library is a reusable benchmark asset rather than a component of the method. The length-9 library is the public POVE library (Fong & Motani, KDD 2025), which was computed once and serves every algorithm benchmarked on it. Lookups in the POVE library shorten the same search to a median of 1.5 s per run, which makes repeated comparisons of search strategies and hyperparameters inexpensive.

AuthorsOpenReview ↗

Response to Reviewer F1me (2/2)

W4. We agree that the reference front, which selects by test score, is a test oracle. We did not intend to demonstrate superiority over SRBench. The revision renames it the test oracle front and keeps it as an upper bound for any method that selects from this library. In this role it supplements SRBench as a reference for the best accuracy attainable within the library. The revision also rephrases the word 'exceed' and instead refers to the front as a test oracle. The abstract, Section 4.4, the figure captions and the conclusion are revised accordingly. SRBench methods are now compared with traversal search, which never accesses test data. Paired two-sided Wilcoxon signed-rank tests over the 32 datasets, with Holm correction for the 14 comparisons, show that traversal search is significantly more accurate than 3 of the 14 methods (Table 3) and that no method is significantly more accurate than it. Every dataset's figure also adds a train selected front, which takes the expression with the highest training R2R^2 at each length limit and evaluates it once on the test set. At length 9 this front equals exhaustive training-based selection over the library, and traversal search shows no significant difference from it (median paired difference −0.003, Wilcoxon p=0.26p = 0.26) while evaluating a median of 0.11% of the library.

W5. We thank the reviewer for pointing this out. In Algorithm 1, each trajectory first evaluates its starting expression, f←F(e)f \leftarrow F(e), and then moves to the best neighbor whenever it strictly improves ff and stops otherwise. The final (e,f)(e, f) of a trajectory is the state with the highest training R2R^2 among all states evaluated on it, including the start, and e⋆e^\star takes the maximum over all trajectories. A starting expression with no better neighbor therefore remains a candidate for e⋆e^\star. Single-mutation, nn-mutation and beam search all follow this rule in the implementation, and beam search initializes its historical best with the best starting expression. The revision adds two comments to Algorithm 1 and states this initialization in the description of beam search. While running the on-demand variant, we noticed that the evaluation count in the submission counted a simplified skeleton again whenever it was reached through another raw expression or by another trajectory. The revision counts the distinct simplified skeletons with a valid fit in each run, which gives 3,337 evaluations per run on average at s=2s = 2 and R=10R = 10, and reports all evaluation counts on this basis. This count includes the starting expressions, and the revision accordingly adds the start term to the bounds, giving E1cap=s∣Tℓ∣(1+RD1)E_1^{\mathrm{cap}} = s|\mathcal T_\ell|(1 + R D_1) and Encap=s∣Tℓ∣(1+RDn)E_n^{\mathrm{cap}} = s|\mathcal T_\ell|(1 + R D_n). The original form also holds for R≥2R \ge 2. On each trajectory the start costs at most one evaluation and the first round at most DnD_n, with n=1n = 1 for single-mutation search. From the second round on, the previous state lies in the current neighborhood and has already been evaluated, so each round adds at most Dn−1D_n - 1 evaluations. A run of s∣Tℓ∣s|\mathcal T_\ell| trajectories therefore performs at most s∣Tℓ∣(1+Dn+(R−1)(Dn−1))=s∣Tℓ∣(RDn−(R−2))s|\mathcal T_\ell|\bigl(1 + D_n + (R-1)(D_n-1)\bigr) = s|\mathcal T_\ell|\bigl(R D_n - (R-2)\bigr) evaluations, which is at most s∣Tℓ∣RDns|\mathcal T_\ell|R D_n for R≥2R \ge 2. All configurations reported in the paper use R≥2R \ge 2, so the original conclusions are unaffected. In Table 2 at s=10s = 10 and R=10R = 10 the evaluations reach 19.59%–38.33% of E1capE_1^{\mathrm{cap}}, and the cost of the initial states is fully counted.

Thanks for the detailed response. The library counts, runtime results including constant fitting, and clarification of the starting states address those concerns. Separating the test oracle fronts from training-based selection also helps.

My main remaining caveat is the sampling analysis: splitting the same candidate list is useful, but it is not the same as generating a new independent sample. Please keep that limitation clear and describe the fronts as references within the explored space.

With that qualification, most of my original concerns are addressed.

We thank the reviewer for the discussion. The revision now states this limitation more clearly in Appendix B, and the main text describes the fronts as references within the explored search space. We thank the reviewer for the time and hope that the reviewer can consider increasing the score if the rebuttal has addressed the concerns.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Response

We thank the reviewers for their constructive comments and summarize the new results below.

  • At length 9 with s=2s = 2 and R=10R = 10, traversal search performs 3,337 evaluations per run on average. The new on-demand variant fits during search and takes a median of 40 s per run on one CPU core. Table 3 reports this end-to-end search time alongside the archived SRBench training times.

  • Traversal search shows no significant difference in test R2R^2 from the new train selected front, which at length 9 equals exhaustive training-based selection (median paired difference −0.003-0.003, Wilcoxon p=0.26p = 0.26), while evaluating a median of 0.11% of the library.

  • Paired Wilcoxon tests with Holm correction show traversal search to be significantly more accurate than 3 of the 14 SRBench methods, with none significantly more accurate than it.

  • Traversal search exceeds the newly added budget-matched Monte Carlo random search baseline (Appendix C, Figs. 1,3,4,5,6,7) on 26 of 32 datasets (median test R2R^2 gain 0.038, Wilcoxon p=2.8×10−5p = 2.8 \times 10^{-5}).

  • In the newly added sampling stability analysis (Appendix B), the test oracle front at ℓ=21\ell = 21 differs by a median of 0.003 R2R^2 between two disjoint random halves of each sampled list.

  • The revision adds a comparison with gplearn using the same function set (Appendix D). gplearn uses 7,000 evaluations per run, 2.1 times as many as traversal search on average. Traversal search achieves higher test R2R^2 on 27 of 32 datasets and higher training R2R^2 on all 32.

  • The revision adds on-demand traversal experiments at lengths 11 and 13 (Appendix F). At both lengths, traversal search shows no significant difference in test R2R^2 from the train selected front. In 237 of 3,200 runs at length 11 and 650 of 3,200 at length 13, it returns an expression outside the library with higher training R2R^2 than any library expression up to that length.

  • We also update the description of the cap. The original manuscript states a cap of 10810^{8} expressions per sampled list, whereas each sampled list holds 10710^{7}. Lengths up to 9, and length 11 for the 9 datasets with at most 3 features, are exhaustive and never pass through the cap. The revision clarifies this description in Section 3.1. All reported results were computed on these lists of 10710^{7} expressions, so this update leaves all reported values unchanged.

  • The revision adds a comparison of 49 search configurations in Figure 2. At matched evaluation budgets, 4 beam search configurations exceed the single-mutation envelope by 5.8 to 15.0 percentage points in training-optimum recovery rate (Appendix E, Table 9B).

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.