Catching Frozen Mistakes in Vertical Symbolic Regression

Symbolic regression means recovering an exact formula, such as $F = q_1 q_2 / (4\pi\epsilon r^2)$, from data. The most scalable current methods split the problem into levels. They first find how the output depends on one variable while holding the others fixed, lock that piece in place, and then free one more variable. This "vertical" strategy turns an exponential search into a sequence of small ones and reaches problems with dozens of variables. It has a structural weakness familiar from any layered pipeline: once a lower piece is locked, nothing later can fix it. If the first stage mistakes $\cos(x_1)$ for $1 - x_1^2/2$, which is easy on a narrow sampling range, every later stage has to absorb that error. The formula grows bloated and exact recovery fails.

This proposal argues that the later stages already contain the evidence needed to catch the mistake. Classical algebra predicts it. When the wrong reduced form is chosen, eliminating the remaining terms makes the rest of the expression more complicated, not simpler. We propose to measure that growth in complexity as it happens and use it to decide which locked piece to reopen, instead of backtracking blindly or keeping many hypotheses alive from the start. The method is a cheap diagnostic plus targeted unfreezing, bolted onto an existing vertical regressor. We test it on standard physics-formula benchmarks, with deliberately planted errors used to measure detection.

Core Claim

In Vertical Symbolic Regression and its policy-gradient successor Vertical Symbolic Regression via Deep Policy Gradient, each stage fits a reduced form $g(x_1;\mathbf{c})$. Here $\mathbf{c}$ are "summary constants": fitted numbers that stand in for sub-expressions involving variables that are still held fixed. When $x_2$ is freed, those constants become functions $c_j(x_2)$, and the method searches for their formulas while keeping $g$'s structure locked. These papers motivate our work, since they report large gains over non-hierarchical search. They also leave the gap we target, because frozen nodes are never revisited.

Our claim is that a wrong frozen form leaves two measurable signatures when the next variable is freed.

The first signature is loss of form invariance. If $g$ is correct, refitting $g$'s constants separately at each new value of $x_2$ leaves residuals in $x_1$ that are unstructured noise. If $g$ is a truncation or otherwise misspecified, those residuals share a systematic $x_1$-shaped pattern across $x_2$ values, and the pattern's size changes with $x_2$.

The second signature is swell in the summary-constant trajectories. Suppose $g$ is wrong. The best-fitting $c_j(x_2)$ must then partly compensate for the misspecification, so it needs more description length to express, and different constants become coupled in ways a correct factorization would not produce.

The second signature is the statistical counterpart of Bring's observation in Erland Samuel Bring's "Transformation of Algebraic Equations". That observation is that eliminating terms through a poorly chosen substitution forces the remaining conditions to higher degree. It also parallels the "reduced term" problem in Homogenization: Preparing Equations for Change of Unknown, where a bad choice of target sub-term makes the rest of the rewrite impossible. We borrow these as a lens, not as machinery. Complexity that grows downstream is evidence against an upstream choice.

We score each frozen node $v$ by how much reopening it simplifies the downstream stage:

$$ \Delta(v) = L_{\text{down}}(\text{frozen } v) - L_{\text{down}}(\text{reopened } v), $$

Here $L_{\text{down}}$ is the total description length, in bits, of the current stage's residuals plus the summary-constant formulas. We use the Mean Error Description Length criterion of AI Feynman 2.0 as the measuring stick. A node is reopened only when two conditions hold: the form-invariance test on held-out $x_2$ slices rejects it, and $\Delta(v)$ exceeds a threshold calibrated on planted-error data. Reopening searches that node's subtree again, using data pooled across all $x_2$ slices collected so far. Those slices span a wider effective range than the original stage had.

The key difference from keeping alternatives alive is timing. A beam of candidates, as in BeamAggR for multi-hop question answering, ranks hypotheses using only the evidence available when the choice is made. When the slice data cannot distinguish $\cos$ from its truncation, the true form need not be in the beam at all. Our method uses evidence that only exists later.

Research Program

The first component is the diagnostic itself, analyzed on controlled cases. We will derive, for the common failure classes, what residual pattern and what constant-trajectory swell each produces. The classes are Taylor truncation of a transcendental function, a missing operator approximated by a polynomial, and a wrong exponent. From these derivations we set how many $x_2$ slices the test needs, as a function of noise level.

The second component is blame localization. When the test fires at stage $t$, several frozen nodes from stages $1,\dots,t-1$ are candidates. We rank them by an approximation of $\Delta(v)$ obtained by locally relaxing each node into a flexible fitted function, which is cheap because nothing is searched symbolically. We then reopen only the top-ranked node. This mirrors the offender-identification step in homogenization, which finds the specific sub-terms that break the desired structure before rewriting.

The third component is integration into VSR-DPG under a fixed budget of oracle queries. We count every extra query spent on diagnosis and reopening against our method.

We will also study the observational regime. There the oracle is a trained neural network, and AI Feynman documents that fitting errors in such a proxy corrupt downstream structure tests. The question is whether the diagnostic can tell a proxy artifact from a genuinely wrong frozen form. It may be unable to, and that is a real risk. We will report it either way.

Baselines

The naive reference is VSR-DPG exactly as published, with greedy freezing and no revisiting. On 5-variable benchmarks it reports a 40–50% exact recovery rate while horizontal baselines score 0% (Vertical Symbolic Regression via Deep Policy Gradient). We rerun it ourselves on every split with its released settings, using the same oracle budget and grammar as our method.

The strongest competitor on the specific question of recovering from bad early commitments is beam-VSR: VSR-DPG keeping the top-$k$ frozen candidates at each stage and pruning by downstream fit. This is the mechanism BeamAggR used to gain an average 8.5% over ProbTree in question answering. We found no reported result on Lacuna for beam-style VSR, so we build it. Its $k$ is tuned under the same total oracle-query and wall-clock budget as our method, so neither side gets more search.

A second strong competitor is VSR followed by a final global re-search: after the full tree is built, every subtree is refit jointly on all data. This tests whether end-of-run cleanup suffices.

For cross-method context we report PruneSymNet, which recovers 42 exact solutions on the AI Feynman 2 benchmark versus 20 for DSR and 17 for GP (PruneSymNet). We also report AI Feynman 2.0, which solves all 100 Feynman equations. These are not hierarchical-freezing methods, so they frame absolute performance rather than isolate our idea.

Two ablations isolate the key ingredient. The first reopens a random frozen node when the test fires, which tests whether localization matters. The second reopens on the swell signal alone, without the invariance test, which tests the value of combining the two.

Beating the field means higher exact recovery than both beam-VSR and the global re-search at equal budget, on the stress split described below, with no loss on the standard splits.

Why not just…?

Why not just keep a beam of frozen candidates? This is the most serious alternative. Our argument against it is informational: when the early slice genuinely cannot separate the true form from its approximation, ranking at freeze time is close to arbitrary, and the true form may fall outside any modest beam. That is an argument, not evidence. The experiment settles it. On the planted-truncation split we record whether the true form was ever inside beam-VSR's top-$k$. If beam-VSR matches our method at equal budget, the diagnostic adds nothing and we will say so.

Why not just sample a wider range in each control experiment? With a controllable physical oracle, widening the range of $x_1$ often exposes a truncation directly. That makes this alternative a real threat in that regime. We include a wide-range VSR baseline at matched query count. We expect our advantage to hold mainly where widening is unavailable or unsafe, as with neural proxy oracles that are trustworthy only near the training data. If wide-range sampling closes the gap even with proxy oracles, the contribution shrinks to a diagnostic tool.

Why not just refit everything at the end? A final global refit adjusts constants but cannot easily change structure once a bloated tree has been built. The downstream stages were searched under a wrong premise, so the tree itself encodes the error. The global re-search baseline measures exactly this. We will report how often it recovers the true structure from a tree grown on a wrong frozen form.

Proposed Experiments

The benchmarks are the Feynman Symbolic Regression Database used by AI Feynman and VSR, the high-dimensional synthetic benchmarks of VSR-DPG (up to 50 variables), and Livermore2. On top of these we construct a stress split. It takes Feynman and synthetic equations with $\cos$, $\exp$, or $\sqrt{\cdot}$ inside an early-freed variable, and restricts first-stage sampling to ranges where a low-order polynomial fits within noise. This split creates the failure the paper is about in a measurable form.

The first decisive check is planted-error detection. We freeze known-wrong subtrees and measure the true-positive rate of the combined test against its false-alarm rate on correct frozen trees, across noise levels up to the 10% that AI Feynman 2.0 tolerates.

The second check is exact recovery rate, expression complexity, and oracle queries on all splits against every baseline above, at matched budget.

The third check repeats everything with a neural-network oracle trained on fixed observational samples. This tells us whether the diagnostic confuses proxy error with structural error.

The proposal is supported if our method raises exact recovery on the stress split beyond beam-VSR, wide-range VSR, and global re-search at equal query budget, and stays at parity on the standard splits. It is refuted if beam-VSR or wide-range sampling matches it. In that case the useful output would be the detection study alone.