{"id":"1e97131c-af5a-42c2-899d-fd4fd270c04b","arxiv_id":"2506.19537","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"A beam search over small expression DAGs, validated by functional dependence measures, reduces the variable count of symbolic regression problems and boosts recovery rates of existing algorithms.","lead":"Researchers built a preprocessing step for symbolic regression that finds combinations of variables and replaces them with a single new variable, shrinking the problem. Running several standard symbolic regression algorithms on the reduced problems improves how often they recover the true formula.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The beam search always transforms the problem using the highest-scoring candidate with no rejection threshold, while the reduction-rate metric filters candidates with ground truth, so false-positive substitutions are never measured; the claimed reliability of validity detection is therefore not…","rationale":"The reader's weakest assumption identifies the same underlying issue: the functional dependence score may not certify a true substitution, so the reduced problem may not be equivalent to the original. My stress-test sharpens this into a concrete failure mode that the paper's own evaluation cannot detect. The beam search always selects the highest-scoring substitution and applies it, even on problems where all candidates are invalid; there is no rejection threshold. The reduction-rate metric in Section 5 is computed after filtering with ground-truth SymPy checks, so it measures only whether valid substitutions are found, not whether the unlabeled pipeline would avoid invalid ones. The recovery-rate tables show net improvements, which is genuine evidence, but they do not rule out the possibility that false-positive substitutions hurt a subset of problems and are masked by large gains elsewhere. Because the central claim is explicitly about reliability of identifying valid substitutions and about boosting recovery when used with any symbolic regressor, this missing false-positive analysis is load-bearing. The reader's CONDITIONAL verdict already reflects the need for additional methodological support, so I do not propose changing it; the concrete test above would settle whether the concern lands. I mark agreement as partial because the reader's formulation was more general, whereas I emphasize the absence of a threshold and the oracle-filtering in the reduction-rate metric.","tokens_in":15928,"tokens_out":6034,"duration_ms":74914,"concrete_test":"For every problem in the Feynman and Wikipedia benchmarks, record the CODEC score of the substitution selected by beam size 1 and use SymPy to label whether that substitution is valid. Report precision and recall of the score as a validity classifier, and specifically the precision at the operating point used by the pipeline (best score per problem). Then rerun the recovery experiment with an oracle-veto control: when the selected substitution is invalid, fall back to running the base symbolic regressor on the original problem instead of the transformed one. If the oracle-veto control achieves substantially higher recovery than the reported beam pipeline, then false-positive substitutions are degrading the method and the claim that the validity test reliably identifies valid substitutions is not supported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 4 states that after the beam search 'the regression problems on the path that is leading to the highest scoring regression problem are passed on to an established symbolic regression algorithm.' There is no threshold on the functional dependence score: even if every candidate substitution is invalid, the method still selects the highest-scoring one and solves a transformed problem. The central claim that the method 'reliably identifies valid substitutions' depends on this score being a trustworthy validity test at that operating point. The reduction-rate experiments in Section 5 do not test this. They compute the reduction rate by running the beam search and then 'check the correctness of the selected substitutions' with SymPy ground-truth knowledge; invalid substitutions are ignored and contribute zero to the reduction rate. This metric therefore cannot reveal how often the unlabeled pipeline would select an invalid substitution and pass a wrong problem to the downstream symbolic regressor. The recovery-rate experiments average over many formulas, so a net improvement could coexist with frequent false-positive substitutions that hurt individual problems, especially where no valid substitution exists. Because the beam size is 1 and the best-scoring path is always used, the failure mode is not an edge case but the default behavior on every problem. Without measuring precision of the dependence score as a validity classifier, the paper does not establish that the reduced problem is equivalent to the original whenever the pipeline commits to it.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a dimension-reduction preprocessing step for symbolic regression. Candidate substitutions (input substitutions and out-input substitutions) are enumerated as small expression DAGs, scored with functional dependence measures (CODEC, KMAC), and organized in a beam search. The path with the highest-scoring reduced regression problem is then handed to a downstream symbolic regression algorithm, and the recovered expression is mapped back to the original variables. Experiments on the Wikipedia eponymous equations and Feynman benchmark suites report reduction rates around 34-49% and improved recovery rates for UDFS, DSR, TRANSF, PySR, OPERON, and polynomial regression.","tokens_in":16183,"tokens_out":7127,"duration_ms":83215,"significance":"If the central claim holds, the method is a broadly applicable plug-in preprocessing that improves symbolic recovery for many algorithm families, which would be a useful contribution. The paper is clearly written, the code repository is provided, and the empirical evaluation covers several conceptually different symbolic regressors and two established benchmark suites. The recovery gains are consistent across algorithms. However, the evaluation does not measure the false-positive rate of the unlabeled substitution test, and the recovery comparison includes extra model selection in the beam-search condition. The claim that the method 'reliably identifies valid substitutions' is therefore not yet supported by the experiments as reported.","major_comments":[{"comment":"The deployed pipeline and the reduction-rate evaluation use different validity criteria. Section 4 states that the regression problems on the path leading to the highest-scoring node are passed to a symbolic regression algorithm, with no rejection threshold on the functional dependence score. Section 5, however, computes the reduction rate by running the beam search and then checking the selected substitutions with SymPy against the known ground truth; the metric records the best dimension reduction obtained after this oracle check. This mismatch means the reported reduction rates measure what a perfect validity oracle could certify, not how often the unlabeled dependence score actually selects a valid substitution. Since the beam size is 1 and a path is always selected, invalid substitutions are not an edge case but the default operating point whenever no valid substitution exists. Please report the precision and recall of the dependence score as a validity classifier at the operating point used by the beam search, including problems that admit no valid substitution, and either specify a threshold or justify why rank-based selection is sufficient.","section":"Section 4 and Section 5 (Reduction rate)"},{"comment":"The recovery comparison conflates dimension reduction with additional model search. In the beam-search condition, the downstream symbolic regressor is run on each problem along the selected path, and the expression with the best model fit on the original data is returned (Supplementary Section A). The baseline, in contrast, runs the regressor once on the original problem. Multiple independent runs followed by selection on held-out fit can improve recovery by themselves, so the gains in Table 4 may be partly attributable to extra candidate expressions rather than to valid substitutions. Please add a control that gives the baseline the same number of independent regressor runs (or the same compute budget) with the same selection rule, and report the number of regressor calls per problem in both conditions.","section":"Section 4 and Supplementary Section A"},{"comment":"The finite-sample reliability of the functional dependence measures at the chosen operating point is not established. Section 3 presents asymptotic guarantees for Chatterjee's coefficient, CODEC, and KMAC, but the implemented validity test is a finite-sample score used only to rank candidates. The paper does not report score distributions for valid versus invalid substitutions under the sample sizes and noise levels of Section 5, nor does it show how the score behaves when no valid substitution exists. Without such calibration, the abstract's claim that the method 'reliably identifies valid substitutions' remains a statement about asymptotic behavior rather than about the implemented procedure. A calibration experiment (score histograms or ROC-style curves for true and false candidates) would directly address this and would also inform the threshold question raised above.","section":"Section 3 and Section 5"}],"minor_comments":[{"comment":"The complexity count for Washburn's formula is inconsistent: the text says the expression tree has 13 nodes, but later says the simplified tree is reduced from 12 to 9 nodes; please reconcile these numbers.","section":"Section 1"},{"comment":"The phrase 'in-output substitutions h' appears to be a typo and should read 'out-input substitutions h' to match the terminology used elsewhere.","section":"Section 4"},{"comment":"Tables 2 and 3 do not state the noise level at which the reduction rates are computed; please specify whether these results are for the noise-free setting or a particular noise level.","section":"Section 5"},{"comment":"The termination criterion of the beam search is not fully specified; please state the maximum number of levels or the stopping condition used in the experiments.","section":"Supplementary Section A"},{"comment":"The x-axis labels for the noise levels are cramped and hard to read; consider using a log-spaced axis with clearer tick labels.","section":"Figure 3"}],"recommendation":"major_revision","confidential_remarks":"The paper's main idea is sensible and the empirical results are encouraging, but the central reliability claim needs a direct evaluation of the unlabeled validity test. The comparison control described in major comment 2 is essential for attributing the recovery gains to dimension reduction rather than to extra model search. With those additions, the paper could become a solid contribution. The use of the authors' own UDFS and DAG enumeration is reasonable here, though the novelty relative to Kahlmeyer et al. (2024) should be stated more crisply."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Paul, here's my take on Kahlmeyer, Fischer, and Giesen.\n\nThe method is a natural and useful generalization of AIFeynman: instead of checking only a few fixed bivariate forms, the beam search enumerates small expression DAGs as candidate substitutions and uses CODEC/KMAC dependence scores to rank them. The out-input substitution idea—replacing a function of some inputs and the output—is new and it pays off empirically. Recovery-rate improvements are consistent across all five regressors on both benchmarks: DSR jumps from 0.37 to 0.66 on Feynman, and even the transformer goes from 0.01 to 0.11. The code is public, so the results are reproducible. This is a solid engineering contribution.\n\nThe soft spot is the reliability claim. The abstract says the method \"reliably identifies valid substitutions,\" but the experiments never measure false positives. In the reduction-rate evaluation (Section 5), each selected substitution is verified with SymPy against the known ground truth, and invalid ones are skipped. The actual pipeline has no ground truth and no rejection threshold: it always passes the highest-scoring transformed problem to the downstream regressor. So a dependence score that fires on noise will produce a wrong problem. The recovery-rate gains are averaged over many formulas and could coexist with frequent wrong transformations that hurt individual cases. This doesn't kill the idea, but it leaves a real gap between claim and evidence.\n\nSmaller issues: recovery rates are reported without error bars, hyperparameters were selected on the same test benchmarks, and the recovery experiment only uses beam size 1 despite the beam-size study showing some gains at larger sizes. The SymPy step for out-input substitutions (solving for y) is also taken for granted.\n\nWho this is for: symbolic regression researchers and practitioners who want a preprocessing step to bolt onto an existing algorithm. I'd send it to a serious referee. The authors should be asked to report precision/recall of the dependence score as a validity classifier on problems where no valid substitution exists, and to consider adding a threshold or a \"no substitution\" exit. With that, it would be a strong paper.","headline":"A useful, well-engineered extension of AIFeynman's substitution idea that shows real recovery gains, but the reliability claim outruns the evidence because the pipeline's false-positive rate is never measured.","tokens_in":16698,"tokens_out":3939,"would_cite":true,"duration_ms":40562,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Prepending a substitution-finding beam search to symbolic regression significantly improves the recovery of formulas from finite samples.","keywords":["symbolic regression","dimension reduction","functional dependence","substitution search","beam search","expression DAG","CODEC","KMAC"],"falsifier":"Take a ground-truth formula that contains no small substitution, sample it with increasing noise and decreasing sample size, and run the beam search. If the procedure still reports large reduction rates and high functional-dependence scores for candidate substitutions, then the validity test is accepting false substitutions and the method would send the regressor a reduced problem whose reconstruction does not equal the true formula.","tokens_in":15738,"feed_emoji":"🧮","tokens_out":8689,"duration_ms":82036,"temperature":0.7,"pith_summary":"Many natural formulas contain variables that appear only in fixed combinations, and symbolic regression algorithms lose their ability to recover such formulas as complexity grows. This paper proposes finding those combinations automatically by enumerating small candidate expressions and testing each candidate with a functional-dependence score; once a combination is confirmed, it can be replaced by a single new variable. The substitution search is organized as a beam search and can be prepended to any symbolic regression algorithm. The paper reports that this preprocessing reduces the number of variables by roughly half on the Feynman benchmark and by about a third on Wikipedia's eponymous equations, and that it substantially raises recovery rates for several very different regressors.","feed_headline":"Beam search finds hidden variable combos to boost symbolic regression","feed_subtitle":"Preprocessing with substitution search lifts recovery rates on Feynman and Wikipedia benchmarks","key_machinery":"The mechanism that carries the argument is an iterative substitution search over small expression DAGs, validated by a functional-dependence score. A candidate substitution transforms the original observations into a lower-dimensional data set; if the score for the transformed data is near 1, the candidate is treated as a valid reduction and becomes a node in a beam search. Two substitution types are used: input substitutions $g(x_I)$, which compress several input variables into one, and out-input substitutions $h(x_I, y)$, which create an auxiliary regression problem that can expose more complex input substitutions. The final formula is reconstructed by solving the transformed equations symbolically with a computer algebra system.","core_discovery":"The central claim is that symbolic recovery performance is significantly improved by reducing the dimension of a regression problem before handing it to a symbolic regressor. The reduction is achieved by finding valid substitutions: a function $g$ of a subset of the input variables (input substitution), or a function $h$ of some inputs together with the output (out-input substitution), that leaves the data functionally dependent. Candidate substitutions are generated as small expression DAGs, and a functional-dependence measure such as CODEC decides validity. The best-scoring substitutions are followed in a beam search, and a computer algebra system reconstructs the original formula from the substitutions on the chosen path. On the Feynman and Wikipedia eponymous equations benchmarks, the method cuts the variable count by about 50% and 35% respectively and improves recovery for all tested regressors; the authors conclude that combining this beam search with state-of-the-art symbolic regression algorithms significantly boosts their symbolic recovery performance.","pith_inferences":["The same reduction could serve as a feature-construction step for ordinary (non-symbolic) regression, turning discovered substitutions into interpretable derived variables; this is a natural extension the paper does not test.","Since the validity test is a statistical score on a finite sample, high noise or small samples could make the beam search commit to a substitution that is not a true symbolic identity; a conservative score threshold or a verification step on held-out data would address that risk.","A testable extension would be to enlarge the DAG search space beyond one intermediary and one output node; the paper keeps this space small for efficiency, and larger budgets might yield even higher reduction rates at higher computational cost."],"forward_implications":["Any symbolic regression algorithm can be preceded by this substitution-finding beam search without changing the algorithm itself, so the gain in recovery is portable across regressor families.","Benchmark formulas with known ground truth can be reduced by roughly half their variables, which makes the remaining regression problem easier for search, sampling, and genetic-programming methods alike.","Even when a formula is not fully recovered, the returned expression shares more subexpressions with the ground truth when the beam search is used, so the method improves partial interpretability, not just exact recovery.","The out-input substitution mechanism finds reductions that the four AIFeynman predicates miss, particularly on the Wikipedia data set, so the method covers a broader class of simplifications than previous predicate-based approaches."],"supporting_citations":[{"why":"Supplies the Wikipedia eponymous equations dataset of 880 formulas used for evaluation.","marker":"(Guimerà et al. 2020)"},{"why":"Provides the benchmark protocol, recovery definition, noise scheme, complexity measure, and Feynman data samples.","marker":"(La Cava et al. 2021)"},{"why":"Supplies the expression DAG enumeration framework and the UDFS regressor used in the experiments.","marker":"(Kahlmeyer et al. 2024)"},{"why":"Introduces the rank-based functional dependence coefficient that underlies the substitution validity test.","marker":"(Chatterjee 2021)"},{"why":"Defines CODEC, the multivariate functional dependence measure used to validate candidate substitutions.","marker":"(Azadkia and Chatterjee 2021)"},{"why":"Provides KMAC measures used as the alternative functional dependence test in the parameter study.","marker":"(Deb, Ghosal, and Sen 2020)"},{"why":"Defines the four simple AIFeynman substitutions that this paper generalizes and compares against.","marker":"(Udrescu et al. 2020)"},{"why":"Supplies SymPy, the computer algebra system used to verify substitutions and reconstruct formulas.","marker":"(Meurer et al. 2017)"},{"why":"Provides the Operon regressor, one of the tested baselines whose recovery improves with the beam search.","marker":"(Burlacu, Kronberger, and Kommenda 2020)"}],"fun_headline_variants":["Substitution search cuts variables for symbolic regression","Beam search reduces dimensions, improves symbolic regression","Preprocessing with substitution search boosts symbolic recovery","Hidden variable combos found by beam search aid symbolic regression"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The method assumes that a functional-dependence score close to 1 on the finite, noisy sample reliably means the candidate substitution is a true substitution, so the reduced problem is equivalent to the original one and the regressor is not being asked to solve a different problem.","fun_headline_variants_meta":{"raw":{"variants":["Substitution search cuts variables for symbolic regression","Beam search reduces dimensions, improves symbolic regression","Preprocessing with substitution search boosts symbolic recovery","Hidden variable combos found by beam search aid symbolic regression"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000849,"raw_usage":{"total_tokens":3660,"prompt_tokens":882,"completion_tokens":2778,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":498,"completion_tokens_details":{"reasoning_tokens":2719}},"tokens_in":498,"tokens_out":2778,"duration_ms":19646,"temperature":1.0,"reasoning_tokens":2719,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T23:06:25.200421+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a ground-truth formula that contains no small substitution, sample it with increasing noise and decreasing sample size, and run the beam search. If the procedure still reports large reduction rates and high functional-dependence scores for candidate substitutions, then the validity test is accepting false substitutions and the method would send the regressor a reduced problem whose reconstruction does not equal the true formula.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the benchmark protocol, recovery definition, noise scheme, complexity measure, and Feynman data samples."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the expression DAG enumeration framework and the UDFS regressor used in the experiments."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces the rank-based functional dependence coefficient that underlies the substitution validity test."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines CODEC, the multivariate functional dependence measure used to validate candidate substitutions."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides KMAC measures used as the alternative functional dependence test in the parameter study."},{"cited_title":"P.; Paprocki, M.; C ert\\' i k, O.; Kirpichev, S","cited_arxiv_id":null,"evidence_quote":"Supplies SymPy, the computer algebra system used to verify substitutions and reconstruct formulas."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the Operon regressor, one of the tested baselines whose recovery improves with the beam search."}],"review_version":1}