Honest Library Search: Cross-Fitted Semantic Backpropagation for Symbolic Regression

Semantic backpropagation is a way of repairing a symbolic formula one piece at a time. You pick a subexpression inside the formula and algebraically invert everything above it to work out what values that piece should have produced on every training point. Then you search a stored library of small expressions for the one that best matches those desired values, and swap it in. Viewed from outside genetic programming, this search step has a familiar shape: it is post-hoc selection from a library of candidate models, scored on a fixed sample of data, with two free parameters (a slope and an offset) fitted per candidate. The ensemble-selection community has spent twenty years showing that this kind of best-of-many selection overfits the data it is scored on. The better the search, the worse the problem. Semantic backpropagation methods score candidates on the same training points that defined the target and accept any swap that lowers training error. They have not taken up that lesson.

This note proposes to import the ensemble-selection remedy into the inner loop of semantic backpropagation. We compute the desired values on one part of the training data. We choose the library replacement, and decide whether to accept it, using a disjoint part. Then we swap the roles and average, a scheme usually called cross-fitting. The claim is testable. The optimism of standard library search should grow with the logarithm of library size, shrink with sample size, and scale with noise variance. Cross-fitting should remove most of this optimism at little cost. The gain should appear on small, noisy regression problems and vanish on noiseless ones.

Why this intersection, and why not the obvious idea

The obvious bridge runs the other way: use semantic backpropagation to set post-hoc ensemble weights. It collapses on inspection. An ensemble output is a weighted sum. Inverting a sum for member $k$ just gives the residual of the other members divided by $w_k$, and matching that residual against a library of models is greedy forward selection. That is exactly Ensemble selection from libraries of models, or matching pursuit. No new mechanism appears, so a reviewer would rightly call it GES renamed.

The useful transfer goes the other way. Semantic backpropagation is where selection overfitting lives unexamined. The ensemble literature supplies both the diagnosis and the remedies. Q(D)O-ES replaced greedy selection with population-based search across 71 OpenML tasks. Its gains were significant on validation data but not on test data: more search capacity meant more exploitation of noise. TabArena found that models tuned heavily on validation folds receive inflated ensemble weights. Bagging Ensemble Selection for Regression removed hillclimb-set overfitting in regression by scoring candidates on out-of-bag points. Margin distribution and structural diversity guided ensemble pruning showed that optimizing different criteria on the same sample overfits, and that decoupling them across data splits fixes this. These papers motivate the proposal and supply its method.

On the semantic side, the relevant systems all score library candidates on the same training data. The local tree improvement of Memetic Semantic Genetic Programming and Greedy Semantic Local Search for Small Solutions does this. So does the random-desired-operator system with linear scaling inside library search in Linear scaling with and within semantic backpropagation-based genetic programming for symbolic regression, which turns every library entry into a two-parameter family and so enlarges the effective library. The memetic system of Memetic Semantic Genetic Programming for Symbolic Regression is the same, and so is its boosting extension Memetic semantic boosting for symbolic regression, which fits each small learner to training residuals with no held-out check. These papers supply the operator we modify. None of them measures how much of each accepted improvement is noise.

Core Claim

Consider one library-search step. The desired values $\tau \in \mathbb{R}^N$ come from inverting the tree on $N$ training points, and the library holds $M$ candidates, each fitted with an optimal slope and offset. Suppose the true improvement available from every candidate is zero. Then the best candidate's training-error reduction behaves like the maximum of $M$ roughly chi-square noise terms. That gives an expected optimism of roughly

$$\Delta_{\text{opt}} \approx \frac{2\sigma^2 \log M}{N},$$

where $\sigma^2$ is the noise variance of the target. The form follows from the expected maximum of $M$ chi-square variables with one degree of freedom, which grows like $2\log M$.

A memetic run performs thousands of such steps. Each step accepts any positive training gain, so the optimism compounds into trees that fit noise. This happens even though the trees stay small, which is why the problem hides behind the parsimony these methods are praised for.

Our fix splits the training data into two halves, $A$ and $B$. Write $\tau^{A}$ for the desired values computed on $A$, $s_m$ for the outputs of library candidate $m$, and $(\hat a_m^{A}, \hat b_m^{A})$ for the slope and offset fitted on $A$. The cross-fitted score is

$$\text{CF}(m) = \tfrac12\Big(\big\|\tau^{B} - \hat a_m^{A} - \hat b_m^{A} s_m^{B}\big\|^2 + \big\|\tau^{A} - \hat a_m^{B} - \hat b_m^{B} s_m^{A}\big\|^2\Big),$$

where the superscript on $\tau$ and $s_m$ indicates which half those values are evaluated on. Selection uses $\text{CF}(m)$ in place of in-sample error. The swap is accepted only if the whole tree's cross-fitted error also improves. All data is still used, and the scaling coefficients are refit on all points after acceptance.

Research Program

We will implement cross-fitted selection and acceptance as a drop-in change to three host systems: random-desired-operator search with linear scaling, the memetic system with analytical quotient, and semantic boosting. The library's precomputed outputs are simply indexed by fold, so each step costs about the same as before, not double.

We will also implement a bagged variant in the spirit of out-of-bag selection. Each step draws a bootstrap sample and scores candidates on the points left out. This lets us test whether the ensemble literature's two main remedies behave the same way here.

Near-singular inversions deserve separate treatment. When a divisor is close to zero, a few points get huge desired values and dominate in-sample matching. Cross-fitting should expose these points because their fits fail to transfer. We will log how often the accepted replacements were driven by such points, with and without cross-fitting.

The analysis side measures optimism directly. For every accepted step we record the training gain and the gain on an untouched test split. We then check whether their gap follows the $\log M / N$ scaling as library size, sample size, and injected noise vary.

Baselines

The naive reference is each host system run exactly as published. It accepts replacements on training error and applies the standard practice of choosing the final model on a validation split. It tells us how much overfitting the current field tolerates.

The strongest competitor on accuracy is the combined system with linear scaling both before inversion and inside library search from Linear scaling with and within semantic backpropagation-based genetic programming for symbolic regression. It reported the lowest median test normalized mean squared error on nearly all of its ten UCI datasets. However, no reported result found on Lacuna gives per-dataset values, so we will rerun it ourselves.

For the boosting setting, the strongest competitor is semantic boosting from Memetic semantic boosting for symbolic regression, with its shrinkage and number of rounds tuned on validation. No reported result found on Lacuna gives numeric test errors for it.

On Feynman recovery, the reference is the dimension-constrained method in Constraining Genetic Symbolic Regression via Semantic Backpropagation. It reports an average symbolic recovery rate of 44.27%, up from 30.3% for plain gene expression programming. We will add cross-fitting to that method and measure the change in recovery rate at each noise level.

Every comparison uses the same library, the same total training data, and the same wall-clock budget of 1000 seconds used by Virgolin et al. Where hyperparameters are tuned, all methods get equal tuning trials on the same validation split.

The key ablation is a half-data control. It runs the unmodified method on only half the training data, which separates the value of honest selection from the effect of simply using less data per decision. Two further ablations apply cross-fitting to selection only and to acceptance only.

Beating a baseline means a lower median test error across datasets, significant under a Wilcoxon signed-rank test, with tree size no larger than the baseline's. On Feynman, beating the reference means a higher recovery rate at the upper noise levels.

Why not just…?

Why not just choose the final model on a validation set, as everyone already does? Final selection chooses among finished trees. By then every candidate has absorbed thousands of noise-driven local swaps, so validation can only pick the least-damaged one. The naive baseline includes this practice. If cross-fitting does not beat it, the claim fails.

Why not just shrink the library or add parsimony pressure? A smaller library lowers $\log M$ but throws away the coverage that makes library search work, and coverage is already a known bottleneck. We will sweep library size for both methods. The baseline should show a U-shaped test error curve as the library grows, while the cross-fitted version should keep improving. If a well-chosen small library matches cross-fitting, that is a real threat and we will report it.

Why not just use shrinkage or a learning rate in boosting? This is the most serious alternative. Shrinkage damps how far each step moves, but it does not change which candidate wins, so a noise-chosen expression still enters the formula, only scaled down. Tuned shrinkage is part of our boosting baseline. If it closes the gap, we will conclude that the fix belongs to magnitude rather than choice. Checking which expressions appear in the final formulas on Feynman tasks, where the true formula is known, separates the two explanations.

Why not just use XGBoost or LightGBM? For raw accuracy it may win. Memetic semantic boosting for symbolic regression concedes as much, and TabArena ranks LightGBM among the top tabular model families. Our question is whether compact formulas can be made more trustworthy, not whether they beat tree ensembles. Gradient-boosted trees are reported only as a reference point.

Proposed Experiments and Decisive Checks

We use the ten UCI regression sets from the semantic backpropagation literature: Airfoil, Boston Housing, Concrete, Dow Chemical, Energy Cooling and Heating, Tower, both Wine Quality sets, and Yacht. These span a wide range of sizes, so the $1/N$ prediction can be tested across datasets. Each gets thirty random train, validation, and test splits. To test generality, we add the 42 UCI and StatLib regression sets used by Bagging Ensemble Selection for Regression. We also use the Feynman equations from SRBench with injected Gaussian noise from $\gamma = 0.001$ to $0.1$. There the true formula is known, so symbolic recovery rate measures whether noise-driven choices were avoided.

The metrics are test normalized mean squared error, tree size, the train–test gap, recovery rate, and the measured per-step optimism.

Three checks decide the claim. First, on noiseless Feynman tasks cross-fitting should give no gain and cost almost nothing, while its advantage should grow with noise level. Second, the measured per-step optimism of the baseline should rise roughly linearly in $\log M$ and fall roughly as $1/N$, and cross-fitting should flatten both trends. Third, the gains should concentrate on small datasets such as Yacht and Boston rather than large ones such as Tower and White Wine. If the half-data control matches the full method, or tuned shrinkage erases the boosting gains, the proposal's central claim is wrong and we will say so.