CS Paper Radar

Runtime Analysis of Cartesian Genetic Programming on Max: A Proven Exponential Speedup

Duc-Cuong Dang, Roman Kalkreuth, Andre Opris

cs.LG cs.AIcs.NE ·submitted 2026-11-11 21:13 UTC · v2
publishedbenchmarktheory

Abstract

Genetic Programming (GP) is a search paradigm inspired from natural evolution for the automated discovery of expressions, functions, and computer programs. Cartesian GP (CGP) is a flavor of GP that uses a graph-based model to encode candidate programs, as contrasted to the conventional Tree-based GP (TGP). Since its inception two decades ago, CGP has predominantly been analyzed empirically, thus little is known regarding its theoretical performance guarantees. This paper analyzes CGP for the Max problem, which has been only rigorously studied for TGP with a proven expected runtime superlinear in the optimal program length $n$. We prove that the expected time for the ($1$+$1$) CGP employing common mutation operators to evolve an equivalent optimal of the same output is polylogarithmic in $n$, specifically at most $O(\log^9{n})$. This is remarkable, as it shows an exponential speedup by switching to CGP. Our results shed light on the benefit and the compactness of the graph-based representation for programs, and on how CGP can navigate its search and fitness spaces efficiently. This is a first proven performance guarantee for CGP on an established benchmark problem. Experiments complement our theoretical findings.

Comment
Accepted as a poster at NeurIPS 2026. To appear in the conference proceedings

Closest papers

Nearest neighbours by meaning across the whole index.

Galop: Billion-Scale Genetic Programming on a Single GPU

cs.NE ·2026-11-10 ·Xavier Hill Roy, Stephen Kelly
code/data similarity 0.65
Abstract · 16 pages, 6 figures. Submitted to EuroGP 2027

Genetic programming (GP) evolves populations of heterogeneous programs, whereas GPUs achieve their highest throughput when groups of threads execute the same instructions. To better align GP evaluation with GPU execution, we present Galop, a hybrid CPU-GPU linear GP system that assigns one individual to each CUDA warp, a group of 32 threads that execute the same instructions across different fitness cases. We compare Galop against EvoGP, a recent high-performance GPU-based tree GP system, on data-rich symbolic regression across two unique GPUs, varying population size and fitness-case count. Galop completes evolutionary runs faster than EvoGP in 27 of the 28 main comparisons, with speedups of up to 13.6 times. Solution quality comparisons favour EvoGP overall, although Galop remains competitive on several problems. Galop also completes a full generation with 2.15 billion individuals on a single H100 GPU, approximately 4.0 times the largest population achieved by any other tested GP system. All five runs at this population complete 100 generations, with a median wall-clock time of 2.23 hours. These results make it practical to study GP populations in the billions on a single GPU. Galop's source code, experimental data, and reproducibility scripts are publicly available at https://github.com/xavierhillroy/Galop.

0.31

Efficient Constant Optimization for Symbolic Regression with GPU-Accelerated Tree-Based Genetic Programming

cs.NE cs.DCcs.LGcs.MS ·2026-09-03 ·Hao Mao, Xu Tony Liu, Shuai Lu, Peng Zhao, Wenzheng Jiang +1 more
publishedbenchmarkcode/datahot direction similarity 0.65
Abstract · Accepted at the 30th Annual IEEE High Performance Extreme Computing Conference (HPEC 2026), 14-18 September 2026. To appear in IEEE Xplore

Constant optimization refines the numerical coefficients of candidate expressions in tree-based genetic programming for symbolic regression. But its per-generation cost has led modern GPU-accelerated frameworks to omit it or restrict it to lightweight forms. We present a GPU-resident, batched Levenberg--Marquardt solver that optimizes constants across a structurally heterogeneous population of expression trees using a fixed number of population-wide CUDA launches per iteration. Reverse-mode automatic differentiation assembles the per-tree Jacobian in one backward sweep, making the dominant per-iteration cost independent of the number of constants per tree, and a double-precision delivery guard guarantees that returned constants are never worse than their initial values. On early-generation populations, the solver sustains up to $5.1{\times}10^{5}$ trees per second on an NVIDIA A100; at a GPU-saturated benchmark configuration it delivers roughly $9.9{\times}$ the throughput of Operon running on a 64-core EPYC 7763, while matching fp64-reference quality. Integrated in-process into EvoGP, the solver enables end-to-end search to recover governing equations on $10$ of $18$ constructed problems versus 0 for stock EvoGP. Our code is at https://github.com/TensorConv/CuSR.

0.72

TSGP-2: On the Non-Linearity of Symbolic Regression Problems and How to Exploit It with Model-based Semantic Genetic Programming

cs.NE ·2026-11-12 ·Philipp Anthes, Alina Geiger, Martin Briesch, Franz Rothlauf
benchmark similarity 0.60
Abstract

Model-based variation operators such as the one used in Transformer Semantic Genetic Programming (TSGP) are affected by possible biases of their training data. TSGP is trained, in particular, on programs generated by Genetic Programming (GP) runs on linear target functions, which leads to a bias toward linear offspring. This bias can hinder search performance on problems that require non-linear solutions. This work has two goals: first, it investigates the linearity of standard test problems such as the Feynman and real-world benchmark problems. While most of the structure of real-world problems can be well approximated by linear structures, the Feynman problems exhibit varying levels of non-linear structure. Thus, a proper variation operator of a search method should be able to create both types of programs, linear as well as non-linear ones. Motivated by this observation, we propose TSGP-2, which follows the functionality of TSGP but uses as training data programs from GP runs on both linear and non-linear target functions. As a result, the training data includes a lower share of programs that behave linearly (the share drops from 83% to 37%). With a higher share of non-linear structures, TSGP-2 outperforms TSGP on problems with non-linear structure, while performing similarly on linear problems. In addition, TSGP-2 is less biased toward linear offspring and is able to propose a higher number of meaningful non-linear offspring earlier during search, which coincides with better solutions. The findings underscore the importance of training data for a learned variation operator and emphasize that the biases of search operators should be aligned with the problems they are applied to.

0.23

Relocating Nonlinearity: How a Downstream Learner Reshapes What Genetic Programming Must Evolve

cs.NE cs.LO ·2026-10-07 ·Nam H. Le
similarity 0.58
Abstract

Genetic programming was conceived as a way of evolving solutions: the program is the answer, and fitness is the error of its own output. A substantial line of work instead makes the program an input to a separate learner, so fitness measures the learner's output rather than the program's. Which learner to attach matters, with no account of what decides it. What makes a target hard for genetic programming is how much nonlinearity the program must build by composing primitives; whatever nonlinearity the learner supplies, the program need not. The quantity to measure is therefore how much of a target's nonlinearity a learner can take over, though on continuous benchmarks it can only be estimated. Here we show that how much the program must still build is decided by which learner is attached, and is measurable on the programs themselves. Moving to Boolean domains, where a target's nonlinearity is exactly its Fourier degree, we tune that degree from one to six with everything else fixed. Conditioned on success, a linear learner forces the evolved program to the target's degree exactly, at one through six without exception over thirty runs per setting, while tree ensembles succeed with far simpler programs and four times as often. This gives the field two things: a learner can be chosen from a target's structure instead of its reputation for difficulty, and the degree of the evolved program is a diagnostic free to compute during any run. Our control target has lower degree than the parity problems yet gains nothing from a nonlinear learner, while targets reducible to a simple statistic gain a great deal. The latter comes with a warning: evolution internalises what the learner supplies in only four of sixty-three conditions, and grows more dependent on it in forty-four, so the more capable the learner, the less of the model is legible in the program.

0.24

BiFE: Search-Efficient Discovery of CPU-Only Branching Policies via LLM-based Bi-Fidelity Evolution

cs.AI ·2026-09-29 ·Ce Zhang, Bin Zhang, Zhiwei Xu, Hao Chen, Xinyue Lu +3 more
similarity 0.57
Abstract

In branch-and-bound (B&B) for mixed-integer linear programming (MILP), branching variable selection critically impacts efficiency. Existing neural branching policies often require GPU inference, while CPU-efficient symbolic expressions lack the representational capacity for complex logic. Large Language Model (LLM)-generated code provides a flexible search space for designing lightweight branching rules with diverse algorithmic logic. To discover effective rules within LLM-based evolutionary frameworks, a core challenge arises: full B&B evaluation on real instances is prohibitively expensive, whereas offline imitation learning suffers from distribution shift. To address this, we introduce a Bi-Fidelity Evolutionary framework (BiFE). It employs low-fidelity imitation scores as a rapid pre-screener and selectively applies high-fidelity on-instance evaluation only to elite candidates, effectively balancing search efficiency with performance reliability. Experiments validate both the search efficiency of BiFE and the competitiveness of its discovered rules, which outperform the SCIP solver and other baselines on CPUs, and even surpass certain GPU-based neural policies.

0.31

DCL-GPGLS: Dynamic Curriculum Learning for Genetic Programming Guided Local Search in Large-Scale Vehicle Routing

cs.NE ·2026-09-21 ·Saining Liu, Yi Mei, Mengjie Zhang
similarity 0.57
Abstract · 14 pages, 3 figures

Genetic Programming Guided Local Search (GPGLS) uses genetic programming to evolve utility functions for guided local search in large-scale vehicle routing problems (LSVRPs). Evaluating every GP individual on every training instance at every generation is expensive, so GPGLS is usually trained on small instance batches. Existing curriculum-based GPGLS orders these batches mainly by instance size. Adaptive Curriculum Learning GPGLS (ACL-GPGLS) improves training efficiency by adapting when the search moves between fixed curriculum stages, but the instance difficulty order remains predefined. We propose DCL-GPGLS, which estimates the difficulty of each training instance from the current population's solution quality and updates the estimates during evolution. Each generation then receives a batch near a scheduled difficulty level, with a correction that limits repeated selection of the same instances. Experiments on a fixed training-test split of the CVRPLIB X set show that DCL-GPGLS achieves the best observed average rank and mean test cost among six training policies. It obtains the lowest mean cost on 36 of 65 unseen test instances and is significantly better than the static feedback-derived curriculum, matched in total evaluator calls, on 6 instances, with no significant difference on the remaining 59.

0.32

Understanding the Co-evolutionary Solution Exchange of the MOEA/D: Already the Smallest Communication Radius Gives the Best-Possible Speed-Up

cs.NE ·2026-10-26 ·Benjamin Doerr, Moaad Elmoutassim, Martin S. Krejca, Guy Mushiata Kibulu
benchmarktheory similarity 0.57
Abstract

Besides domination-based algorithms such as the NSGA-II, the decomposition-based MOEA/D is one of the most popular and successful optimization heuristic for multi-objective problems. It decomposes the problem into several, single-objective subproblems. By solving these in a co-evolutionary manner and archiving non-dominated solutions, it approximates or computes the Pareto front. Interestingly, so far no advantages from the co-evolutionary communication of subproblem solutions were proven. In this first mathematical runtime analysis addressing this research question, we investigate how the mutation-based MOEA/D solves the classic OneMinMax benchmark when solutions are exchanged among subproblems in different distances $r$. We show, for the first time, that the MOEA/D profits from an exchange of solutions, and that already very small communication radii $r$ are sufficient to maximally profit from this feature of the algorithm. More precisely, for all values $r \ge 1$ we prove a tight runtime guarantee of $Θ(n^2)$, where $n$ is the problem size. This is asymptotically faster than the known bound of $O(n^2 \log n)$ guarantee for $r=0$, which we complement with a matching bound of $Ω(n^2 \log n)$.

0.50

On the Slow Convergence to Trivial Solutions of Algorithms for Hard Optimization Problems

cs.LG cond-mat.dis-nncs.DMmath.PR ·2026-08-19 ·Ali Hussaini Umar, Jean Barbier, Matthieu Jonckheere, Manuel Sáenz
similarity 0.56
Abstract

Hard combinatorial optimization problems, many of which are NP-hard, present fundamental algorithmic challenges. Average-case analysis on random instances has emerged as a powerful framework for understanding typical algorithmic performance beyond worst-case guarantees. A substantial body of work has established negative results: for sufficiently hard instances (often controlled by the underlying graph connectivity/constraints density), no known polynomial-time algorithm can significantly outperform naive heuristics in the double asymptotic limit where both problem size and constraints density tend to infinity. We revisit this picture by studying the finite-size behavior of some optimization algorithms across easy, intermediate, and hard regimes. Through rigorous analysis of large-graph asymptotics combined with numerical experiments on canonical problems (maximum independent set and maximum $K$-SAT), we demonstrate that while algorithms do eventually converge to theoretically predicted bounds, this convergence can be remarkably slow. In the intermediate regime where instances are already highly constrained, local algorithms achieve solutions substantially better than their predicted performance in the high-constraint-density limit. This gap between finite-regime and asymptotic behavior has important practical implications: sophisticated algorithmic design remains crucial even when asymptotic theory predicts inevitable failure.

0.18