Rethinking Fitting Error in Symbolic Regression through Local Taylor Consistency: Theory, Empirical Investigation, and a New Evaluation Framework

Symbolic regression aims to discover underlying mathematical expressions from data, and most existing methods rely on fitting error to evaluate candidate expressions and guide the search. However, we observe that symbolic regression algorithms often produce structurally diverse but incorrect expressions with low fitting errors. This observation motivates us to investigate whether structurally distinct low-error candidates are prevalent and how they affect fitting-error-driven search. Theoretically, we derive an upper bound on fitting error and show that structurally different candidate expressions can achieve low fitting errors over small sampling domains when they exhibit local Taylor consistency. Furthermore, infinitely many such candidates can be constructed by introducing different higher-order remainder terms, while free constants further increase the attainability of local Taylor consistency. These results suggest that low-error but structurally incorrect candidates may be widespread over small sampling domains. Empirically, we first introduce RDF-SR, a random non-repetitive symbolic regression algorithm, as an unguided-search baseline. For relatively low-complexity expressions, several fitting-error-driven methods achieve lower recovery rates than RDF-SR, suggesting that optimization landscapes induced by fitting error may hinder structural recovery. Our theoretical error bound further indicates that enlarging the sampling domain can reduce low-error spurious solutions. Motivated by this result, we conduct experiments across different sampling domains and show that larger domains improve recovery rates but may weaken fitting-error guidance, making low-error regions harder to reach. Based on these findings, we develop and apply a new evaluation framework comprising new datasets, evaluation metrics, and an unguided-search baseline to systematically assess the search effectiveness, fitting-error guidance, and structural recovery capabilities of symbolic regression algorithms.