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

arXiv:2610.09347 · cs.NE, cs.LO · Submitted 2026-10-07 · Read on arXiv

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

  1. 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 shows whether the learner is contributing nothing or is carrying the model.

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

  3. 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, because the advantage of an expressive learner should scale with Delta rather than with ONL(y).

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

  5. 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, meaning the 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