- 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
- The explicit state space and mutation neighborhoods make the search method easy to understand and analyze.
- The evaluation-count formulas and comparisons across mutation orders clearly show the cost-quality tradeoff.
- The train-test alignment analysis usefully shows that improving training rank does not always improve generalization.
Critical weaknesses
- 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.
- 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.
- 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
- 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?
- 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?
- How stable are the length-11-to-21 fronts across sampling seeds and caps?
2 comments
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 . Over 1,000 repetitions, traversal search exceeds the median random search result on 26 of 32 datasets with a median test gain of 0.038 (Wilcoxon ). The archived SRBench results were produced under the budgets set by SRBench, with median training times from 66 s to 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 and (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 than gplearn on 27 of the 32 datasets (Wilcoxon ) and a higher training 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 from to on at least 30 of the 32 datasets. Regenerating a list with a new seed would require fitting new expressions for every dataset and split, so two disjoint random halves of each sampled list, with 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 differ by a median of 0.003 , and the median ratio of this difference to each dataset's own gain is 7–8% (Table 6, panel B). The training front gives the highest training among library expressions of length at most . 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 for both fronts. Across caps, randomly capping every file at , or expressions lowers the 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 . Across 100 halves, the median gain spans 0.0427–0.0525 for the test oracle front and 0.0395–0.0469 for the training front, and with expressions per sampled list the test oracle gain exceeds 0.01 on at least 28 datasets (Table 6, panel A).
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 R2 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 R2 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.26) while evaluating a median of 0.11% of the library, and with s=10 starts (0.51% of the library) the difference falls below 10−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 R2 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.07 for the train selected gain). The gain is significant on the 24 datasets with more than 100 samples (17 improve, p=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=2 and R=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.