Relocating Nonlinearity: How a Downstream Learner Reshapes What Genetic Programming Must Evolve
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: We're looking at the paper: "Relocating Nonlinearity: How a Downstream Learner Reshapes What Genetic Programming Must Evolve".
Paper summary: Tom: They argue that this shift means we're not just finding a solution anymore; we're finding a representation. The paper says the difficulty for genetic programming is how much nonlinearity the program has to build by combining basic operations.
Lu: Exactly. And they quantify this as the target’s order of nonlinearity, which they calculate exactly on Boolean domains using something called the Fourier degree >
Conclusion: Jane: So, when you look at what this paper actually claims about how attaching a learner changes things, it seems to suggest that the difficulty isn't just about the target anymore. It’s about which specific learner you pair with it.
Tom: The authors show that the amount of nonlinearity the program still has to build is decided by which learner is attached, and they say this can be measured directly on the programs themselves >
University of Vermont
cs.NE, cs.LO
Submitted: 2026-10-07
Updated: 2026-11-17
Comments: v2: major revision. Adds a matched-pair junta dissociation, a multi-feature experiment, the Nguyen suite, a three-step learner-selection diagnostic, worked examples for the propositions, and a real-data case study on two measured datasets. 20 pages
License: http://creativecommons.org/publicdomain/zero/1.0/
Importance score: 85/100
The gist: Genetic programming was conceived as a way of evolving solutions: the program is the answer, and fitness is the error of its own output The quantity to measure is therefore how much of a target’s…
Key concepts
- Order of Nonlinearity
- This measures how complex the target function's nonlinearity is. It's quantified by finding the lowest total polynomial degree required to approximate the target function with a specific error margin relative to its variance.
- Relocatable Order (ONLdecεV(y))
- This concept determines if a bounded, simple learner can recover the target's nonlinearity. It checks if there exists a simple function that, when composed with the program, gets close enough to the target based on its variance.
- Orthogonality of Difficulty and Learner
- The paper shows that difficulty in finding a solution and choosing an appropriate learner are independent factors. A powerful learner doesn't automatically make a program easier; the choice depends on whether the target allows for a low-order representation achievable by that specific learner.
Terminology
Summary
Genetic programming was conceived as a way of evolving solutions: the program is the answer, and fitness is the error of its own output The quantity to measure is therefore how much of a target’s nonlinearity a learner can take over 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
Pruning redundant reasoning tokens
The paper investigates how attaching a downstream learner to a genetic programming (GP) system reshapes the evolutionary requirements of the program The core idea is that fitness measures the learner’s output rather than the program’s output, which shifts the focus from finding an answer to finding a representation The difficulty for genetic programming is determined by how much nonlinearity the program must build by composing primitives This quantity is quantified as the target’s order of nonlinearity, which can be computed exactly on Boolean domains via the Fourier degree
How the training signal is built
The experimental design involves comparing canonical genetic programming with an arrangement where fitness measures a downstream learner's output rather than the program's output The setup fixes the primitive set, search parameters, and size limit while varying only the learner class F For continuous targets, fitness is defined as L(f ◦ g) = 1/m Σ f(g(xi)) − yi squared The order of nonlinearity is defined as the least total polynomial degree d for which some polynomial of degree d approximates h with squared error at most ε · Var(h)
Where the gains come from
The key finding is that a linear learner forces the evolved program to the target’s degree exactly, at one through six without a single exception over thirty runs per setting In contrast, tree ensembles succeed with far simpler programs and four times as often The advantage of an expressive learner is bounded, and the bound is informative because a 6-multiplexer control gains nothing at all from a nonlinear learner, showing that difficulty and the appropriate learner are orthogonal Furthermore, the more capable the learner, the less of the model is left legible in the program
Relocatable order of nonlinearity
The paper introduces the concept of relocatable order, ONLdecεV(y) = min ONLε(g): ∃f ∈ FV, f ◦ g − y2 ≤ ε Var(y) The claim tested is that ∆, and not ONL(y), decides whether an expressive learner is worth attaching Proposition 3 shows that Parity decomposes at order one, meaning ∆0,k(PARk) = k − 1 This suggests that the target’s order can be relocated by a bounded nonlinear learner
Conclusion
The usual account of a genetic programming system paired with a downstream learner is additive, but the measurements show this is not true because the order of nonlinearity evolution must supply changes from six to three on the same target when only the learner changes What a learner buys is a transfer of budget, and this transfer is visible directly on the evolved objects Difficulty and the appropriate downstream model are orthogonal, meaning an experimenter reading difficulty off a benchmark’s reputation will choose wrongly in both directions The choice depends on whether the target admits a low order representation from which a bounded learner can recover it, which is the quantity ∆ of Definition 2 Future work suggests that multidimensional feature construction systems should require less expressive downstream models than one-dimensional ones at equal accuracy
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Adaptive Downstream Learner Selection: The system can dynamically choose between different downstream learners based on a measurable property of the target, rather than relying on reputation for difficulty. This decision is based on the
order of nonlinearity of the program each run actually produced,
which showswhether the learner is contributing nothing or is carrying the model.
-
Order-Aware Program Evolution: The system can be designed to evolve programs that track what a specific downstream learner can absorb, rather than simply building whatever structure the target requires. This allows for
a diagnostic free to compute during any run, showing whether the learner is contributing nothing or is carrying the model.
-
Bounded Learner Capacity Utilization: When using an expressive learner, the system can be expected to use
far lower order
programs than might be required by a fixed benchmark, becausethe advantage of an expressive learner should scale with Delta rather than with ONL(y).
-
Decoupling Difficulty and Decomposability: The system can distinguish between target difficulty and decomposability by measuring the relocatable order of nonlinearity, Delta. This allows the system to determine if a low order representation is sufficient for a bounded learner to recover it, which
decides whether an expressive learner is worth attaching.
-
Controlling Genetic Assimilation: By tuning the downstream learner's capacity, the system can influence whether genetic assimilation occurs. Specifically, when using more capable learners (like tree ensembles),
the contribution of learning widens over evolutionary time,
meaningthe more capable the learner, the less of the model is left legible in the program.
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. Which learner to attach matters and depends on the problem, 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; any nonlinearity the learner supplies, the program is spared. 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. In 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. Where the target's structure is known, the learner can be chosen from that structure rather than from the target's reputation for difficulty: our control target has lower degree than the parity problems yet gains nothing from a nonlinear learner. Where it is not, the same quantities serve as diagnostics: the degree of the evolved program is free to compute during any run and shows whether the learner is contributing nothing or carrying the model; on two measured datasets the resulting procedure picks the right learner before any evolution is run. A warning follows: evolution internalises what the learner supplies in only four of sixty-three conditions and grows more dependent on it in forty-four. The more capable the learner, the less of the model is left legible in the program.
Related papers
- Evolutionary Ensemble of Agents
- EvoDR: Evolving Dispatching Rules via Large Language Model for Dynamic Flexible Assembly Flow Shop Scheduling
- RECAP: Local Hebbian Prototype Learning as a Self-Organizing Readout for Reservoir Dynamics
- Encoding and Decoding Temporal Signals with Spiking Bandpass Wavelets
- Design and Analysis of Temporal Representations in Neural Networks
- Evolutionary Computation: A Paradigm of Natural Generative AI and Creative Synthesis