CS Paper Radar

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

Nam H. Le

cs.NE cs.LO ·submitted 2026-10-07 03:08 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Flawed in Nature, Perfect through Evolution

cs.LG cs.AIcs.NE ·2026-08-31 ·J. M. Diederik Kruijssen
publishedtheory similarity 0.60
Abstract · 32 pages, 16 figures; appeared in ADI (September 2026)

The performance of artificial intelligence (AI) and machine learning (ML) models degrades when the problem they were trained on drifts. This is a near-universal feature of real-world problems, which often change unpredictably. Biological evolution has achieved intelligence by overcoming this obstacle through natural selection acting on heritable variation. AI/ML techniques have long incorporated forms of natural selection, but it has been challenging to maintain model diversity as optimization naturally drives convergence. Here we show that a swarm of AI/ML models subjected to deliberate mutations of their model coefficients away from optimality can reliably and sustainably improve performance in changing environments by acting as a statistical hedge against non-stationarity. We call this mechanism 'Flawed in Nature, Perfect through Evolution', reflecting that the collective performance gain goes at the expense of individual performance. We prove via four theorems that the resulting regret reduction is guaranteed under general conditions, establishing the Flawed-in-Nature mechanism as a generalizable design principle for AI/ML systems. We validate these results on synthetic linear regression tasks, demonstrating that the mutated swarm delivers the best model in $\sim80\%$ of environment changes and that inference synthesis successfully translates this individual advantage into a collective one. The mechanism proves to be most effective when the mutation drift rate matches the drift rate of the environment. We outline a simple, adaptive controller that enables practical applications by tuning the mutation drift rate to match the unknown drift rate of the environment. The close analogy of the Flawed-in-Nature mechanism to biological evolution suggests it may have been a critical missing ingredient for the organic discovery of AI forms that more closely mimic biological intelligence.

0.36

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.29

Algorithm Modelization: Transforming Optimization Algorithms into Evolvable Intelligence

cs.AI cs.NE ·2026-10-16 ·Jian Yao, Zhiyao Zhang, Yichen Li, Xingyu Wu, Kay Chen Tan
similarity 0.59
Abstract

Can algorithms be learned and evolved as models, rather than repeatedly redesigned as programs? We explore this question by introducing Algorithm Modelization, a new paradigm that turns iterative algorithms into trainable models. Its central idea is to regard algorithm execution trajectories as computational experience: by learning how algorithmic states evolve over iterations, a model can internalize the knowledge embodied in existing algorithms, reproduce their computational behaviors, and further evolve beyond them through training. As a first realization of this paradigm, we modelize iterative optimization as an autoregressive process, where preceding generations constitute the computational context for generating the next population. We develop a dimension-independent population-temporal architecture to capture both population interactions and iterative dynamics, together with an imitation-to-surpassing learning framework that first acquires algorithmic knowledge from heterogeneous teachers and then improves the resulting optimizer directly through optimization feedback. The modelized optimizer consequently goes beyond reproducing individual algorithms: it consolidates heterogeneous search knowledge into a single trainable model, achieves stronger optimization capability through subsequent improvement, and generalizes its acquired knowledge across problems and substantially larger unseen dimensions. More fundamentally, Algorithm Modelization makes algorithmic capability accumulable through learning, where new algorithms and problem-solving experience can become training resources for progressively improving the model. Our results establish a promising path from manually designed algorithms toward general algorithm models that learn, generalize, and evolve from computational experience.

0.13

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

cs.LG cs.AIcs.NE ·2026-11-11 ·Duc-Cuong Dang, Roman Kalkreuth, Andre Opris
publishedbenchmarktheory similarity 0.58
Abstract · Accepted as a poster at NeurIPS 2026. To appear in the conference proceedings

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.

0.44

Adapting the Process of Adaptation: Darwinian, Lamarckian, and Agent-Directed Evolution in AI

cs.AI ·2026-11-04 ·Andrew W. Lo, Chaoyi Zhao
similarity 0.57
Abstract

Evolution has shaped intelligence for billions of years. Artificial intelligence (AI) now raises a striking possibility: intelligence may begin to direct its own evolution. As AI agents become capable of modifying and evaluating their own behavior, how quickly could they improve, and how can that improvement remain safe? We develop a theoretical framework comparing Darwinian, Lamarckian, and agent-directed evolution following environmental change. Darwinian evolution relies on natural selection, Lamarckian evolution adds inherited learning, and agent-directed evolution allows agents to generate and evaluate behavioral variants and choose how extensively to search. When learning is sufficiently effective, these mechanisms exhibit progressively faster adaptation. Generating more variants accelerates adaptation, while optimal search effort depends on learning ability, problem difficulty, and experimentation costs. However, an agent's ability to direct its improvement does not ensure that improvements are evaluated against the intended objective. When the evaluation target is misspecified, additional search accelerates convergence toward the wrong behavior, even as measured performance improves. In recursive self-improvement, such errors may persist across generations, posing challenges for AI safety. Independent evaluation and oversight must keep pace with autonomous AI development. The central challenge is not simply to accelerate the evolution of intelligence, but to preserve humanity's ability to guide its direction, limit its speed, and intervene when necessary.

0.07

Compiling Learning Problems into Adaptation Programs for Language Models

cs.CL cs.AI ·2026-09-29 ·Rebecca Ramnauth, Brian Scassellati
similarity 0.57
Abstract

Model adaptation is typically governed by a fixed recipe, even though different update programs can produce substantially different behavioral outcomes. We introduce adaptation compilation, which reframes where, how, and to what extent a model should adapt as a joint prediction and decision problem. Rather than searching over candidate programs anew for each learning episode, a compiler learns from prior adaptations to predict a vector-valued counterfactual response surface over candidate programs---their expected effects on acquisition, transfer, boundedness, and preservation---and selects a program before adaptation begins. Because this predicted geometry captures multiple behavioral consequences rather than a single winner or scalar score, it can be reused under different downstream priorities without retraining. Across five learning types, preferred programs vary meaningfully across episodes, and this variation is predictable from pre-adaptation information. On Llama-3.1-8B, compiler-selected programs approach exhaustive search while outperforming global and objective-specific defaults. Replication on Gemma-2-9B preserves program heterogeneity and selection headroom, but shows that exploiting this headroom requires accounting for uncertainty when departing from strong defaults. Together, these results show that adaptation search can be amortized across related learning problems, turning prior adaptation experience into a basis for deciding how future learning should occur.

0.27

Evolutionary Ensemble Search: Council-Guided Program Evolution with Persistent Memory

cs.NE cs.AI ·2026-09-11 ·Juan P. Madrigal-Cianci, Eshan Chordia
similarity 0.56
Abstract

Evolutionary Ensemble Search (EES) constructs machine-learning procedures through expert-guided program evolution. A role-specialized council turns task evidence and experimental results into structured search directions. An orchestrator allocates these directions to execution specialists and an evolutionary engine. The engine selects measured parents, diagnoses their errors, and produces descendants through code mutation, structured pipeline edits, and crossover. Each child must execute and acquire its own validation evidence. Population archives retain useful alternatives, while compatible predictions compete in a validation-gated ensemble stage. Search adapts through parent-relative operator credit, session memory, and problem-indexed lessons retrieved across runs. We specify these mechanisms, distinguish their execution profiles, and define the contracts required to compare candidates as their computations change. A public MLE-bench Lite development ledger records medal-threshold artifacts on 19 of 22 tasks (86.36\%), with best outcomes of 11 gold, five silver, and three bronze. The procedures span text, images, tables, audio, scientific geometry, and deterministic transformations. The campaign includes grade feedback between runs, external-source routes, and mixed confirmation procedures; its aggregate is an achieved development result, not a blind autonomous-agent success rate. The report contributes a concrete architecture for cumulative executable search and a versioned account of its cross-modal development outcomes.

0.08

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.56
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