On Scaling Coordinate-Based Neuroevolution: The Quadtree Bottleneck in ES-HyperNEAT

Romain Claret; Michael O'Neill; Paul Cotofrei; Kilian Stoffel

cs.NEAug 25, 2026

On Scaling Coordinate-Based Neuroevolution: The Quadtree Bottleneck in ES-HyperNEAT

Authors: Romain Claret, Michael O'Neill, Paul Cotofrei, Kilian Stoffel

Organizations: University of Neuchâtel, Information Management Institute, Neuchâtel, Switzerland · University College Dublin, Natural Computing Research & Applications Group, Dublin, Ireland

Abstract

ES-HyperNEAT evolves substrate topology through adaptive quadtree subdivision; to our knowledge, no implementation with full population-level GPU parallelization exists. We present JAX-ESHN, a JAX-based implementation targeting GPU parallelization with batched CPPN queries, and benchmark it against the CPU-based PUREPLES Baseline across five tasks: XOR, Parity-3, circle classification, sine regression, and CartPole. The core limitation is structural: each CPPN discovers a unique set of substrate positions, preventing population-level vectorization via vmap. On XOR, the CPU Baseline's runtime scales exponentially with depth while JAX-ESHN's construction cost on GPU (compilation plus first-generation evaluation) plateaus at deep substrates, so JAX-ESHN solves reliably where the Baseline rarely succeeds, with lower runtime variance. A CPU-vs-CPU multi-benchmark control reproduces the same scaling divergence across Boolean, continuous, and control task types, confirming it is a property of the substrate-discovery implementation, not of GPU hardware. An alternative data structure (Hierarchical Spatial Hash Grid) fails not because it precomputes positions but because it applies the variance test independently per position, discarding the quadtree's parent-gated filtering and with it the adaptive sparsity essential to ES-HyperNEAT. These findings define the structural constraints any substrate-discovery method must satisfy to scale coordinate-based neuroevolution; the companion EMR-HyperNEAT reformulation, which replaces adaptive subdivision with eager evaluation of a static multi-resolution grid, satisfies them and resolves the bottleneck this paper characterizes.

Figures & tables

Panel of Figure 1 — Figure 1: JAX-ESHN system architecture. TensorNEAT evolves CPPN genomes (left); each is processed by substrate discovery (center) to build a network via quadtree subdivision; fitness scores (right) drive selection. The bottleneck: substrate discovery runs sequentially per CPPN, between the batched ask and tell , because each CPPN’s topology differs (Section 1 ).

Panel of Figure 2 — Figure 2: Quadtree subdivision for hidden-node discovery. High-variance regions ( $\sigma^{2}>\tau$ ) are recursively subdivided; the hatched region (H) indicates where a hidden node may be discovered during pruning. Because the subdivision pattern depends on each CPPN’s output field, different CPPNs terminate at different leaves, producing the per-CPPN variable-cardinality position sets at the root of the vectorization barrier.

Optimization	Speedup
Unoptimized JAX-ESHN	1.00 $\times$
O1 Batched division queries	1.09 $\times$
O2 Batched pruning queries	1.23 $\times$
O3 vmap substrate evaluation	1.30 $\times$
O4 Precomputed coordinate offsets	1.01 $\times$
O2 $+$ O3 (best measured combination)	1.73 $\times$

Table 1: Per-generation speedup of the batched optimizations over unoptimized JAX-ESHN (XOR, depth 2). O1–O3 are measured individually against the unoptimized implementation at population 1000; O4 is measured against the O2

+

O3 configuration; the combination row is the best we measured. These come from separate campaigns with different reference configurations and are not a cumulative ladder; they were recorded during development, and per-run files for them did not survive into the released archive. The

{\sim}1.7\times

ceiling on within-CPPN batching is the empirical signature of the structural barrier: with population-level vectorization blocked, only within-CPPN work can be batched.

Panel of Figure 3 — Figure 3: Why HSHG over-discovers positions. Top: a CPPN with one informative feature (spike). Middle: HSHG pre-generates fixed positions (A–E), each checking CPPN variance independently in its own zone; positions B and C both detect high variance because their zones overlap the spike, so both pass and discover two positions for one feature. Bottom: the quadtree subdivides toward variance, creating exactly one position at the feature. The contrast is independent per-position filtering (HSHG) versus hierarchical, parent-gated filtering (quadtree); the latter is what EMR-HyperNEAT preserves (Section 7.5 ).

	Baseline		JAX-ESHN
D	Time	Solve%	Total	Solve	Solve%
3	$0.3\pm 0.1$	62.5	$180\pm 6$	$12\pm 3$	100
4	$1.2\pm 0.6$	37.5	$434\pm 47$	$39\pm 14$	91.7
5	$11\pm 4$	33.3	$1{,}618\pm 462$	$128\pm 17$	100
6	$110\pm 80$	8.3	$2{,}500\pm 521$	$215\pm 58$	100
7	$824\pm 528$	4.2	$3{,}540\pm 562$	$348\pm 157$	100

Table 2: XOR runtime (minutes) and solve rate at Pop 500, depths D3–D7. The JAX-ESHN Total is projected over 30 generations as construction overhead plus 29 further generations at the measured post-construction per-generation rate, since generation 1 is already inside construction overhead (

n=3

forced reruns; see Appendix 0.A ). Solve is the analogous projection to the solve generation rather than to generation 30, so a run that solves in generation 1 costs exactly its construction overhead. Solve rates aggregated across 8 population sizes (168 trials per implementation across D1–D7, 24 per depth, of which the 120 for D3–D7 are shown; 300-generation budget for JAX-ESHN, 30-generation for the Baseline).

Panel of Figure 4 — Figure 4: XOR benchmark: total runtime comparison (log scale). Shaded bands (D1–D7): interquartile range (IQR) for Baseline CPU (orange), JAX-ESHN 30-gen total (blue), construction overhead only (green). Solid lines (Pop 1000, D1–D10): construction overhead (circles), Baseline solve time (triangles), JAX-ESHN solve time (squares). Dashed line separates D1–D7 multi-population data from D8–D10 Pop-1000-only (separate measurement campaigns). Baseline D6 is omitted from the solve line (no Pop-1000 seed solved); every remaining Baseline point averages in a seed that hit the 30-generation cap without solving (2 of 3 seeds solved at D1–D5, 1 of 3 at D7), so all of them are lower bounds on the Baseline’s true solve time. JAX-ESHN’s D1 solve point combines the 300-generation campaign’s mean solve generation ( ${\sim}13$ ) with this campaign’s per-generation rate; at D2–D7, 16 of 18 seeds solve during the construction generation itself, so those points sit at or barely above the construction line, which is why the solve curve dips from D1 to D2.

D	Pop 50	Pop 150	Pop 300	Pop 500	Pop 1000
3	$0.9\pm 0.0$	$2.5\pm 0.1$	$4.4\pm 0.1$	$7.7\pm 0.1$	$16.3\pm 1.0$
4	$2.5\pm 0.2$	$7.3\pm 0.3$	$12.4\pm 0.5$	$23.7\pm 0.7$	$51.8\pm 1.8$
5	$7.3\pm 1.3$	$22.1\pm 1.5$	$36.7\pm 1.4$	$74.4\pm 0.8$	$166.4\pm 10.5$
6	$11.8\pm 1.8$	$33.4\pm 1.8$	$52.1\pm 0.5$	$100.4\pm 0.3$	$228.3\pm 5.9$
7	$12.3\pm 1.8$	$35.0\pm 1.8$	$55.5\pm 0.6$	$105.9\pm 0.4$	$269.2\pm 30.3$

Table 3: JAX-ESHN construction overhead (compilation

+

first-generation evaluation; minutes, mean

\pm

std) by depth and population (

n=3

seeds).

	Depth 2		Depth 3		Depth 4
Task	%	Time	%	Time	%	Time	d2 $\to$ d4
Parity-3	76.7	$194\pm 126$	100	$953\pm 741$	96.7	$3.8\pm 4.8$ h	71 $\times$
Circle	0	$291\pm 60$	0	$2{,}225\pm 804$	0	$5.2\pm 5.5$ h	65 $\times$
Sine	0	$245\pm 57$	0	$1{,}971\pm 626$	0	$4.5\pm 5.9$ h	67 $\times$

Table 4: Baseline multi-benchmark results (Pop 150,

n=30

, 100 gen). Solve rate (%) and mean

\pm

std time per seed (D2–D3 in seconds, D4 in hours). The d2

\to

d4 column is the D4/D2 mean-time ratio.

	Depth 2		Depth 3		Depth 4
Task	%	Time	%	Time	%	Time	d2 $\to$ d4
Parity-3	13.3	$23\pm 2$ m	23.3	$47\pm 6$ m	16.7	$1.9\pm 0.4$ h	4.9 $\times$
Circle	0	$28\pm 2$ m	0	$57\pm 12$ m	0	$2.3\pm 0.7$ h	4.8 $\times$
Sine	96.7	$23\pm 2$ m	100	$47\pm 7$ m	100	$1.9\pm 0.5$ h	5.1 $\times$

Table 5: JAX-ESHN multi-benchmark results (JAX CPU backend; see Section 6.5 ). Same config as Table 4 . Times (mean

\pm

std) include construction overhead (compilation

+

first generation); D2–D3 in minutes, D4 in hours. The d2

\to

d4 column is the D4/D2 mean-time ratio.

Panel of Figure 5 — Figure 5: Per-generation cost distributions at depth 4 (Pop 150, $n=30$ seeds), both implementations on CPU. Per-generation cost is measured per implementation as each one’s steady-state rate: total runtime over generations executed for the Baseline, and the post-construction rate for JAX-ESHN, so JAX-ESHN’s one-time construction overhead is excluded here. Amortizing it in would raise JAX-ESHN’s medians by only 4–6% (to 68.1, 77.8, and 62.2 s), leaving the contrast unchanged. Boxes show the interquartile range and median; whiskers span the full min–max range. JAX-ESHN’s distributions are tight (coefficient of variation $0.22$ – $0.31$ ), while the Baseline’s are right-skewed and bimodal (CV $0.90$ – $1.30$ ): most seeds finish quickly, but a long upper tail grinds through many expensive quadtree generations. This predictability gap is the distributional counterpart to the scaling contrast, and uses the same per-generation metric (Section 6.6 ) to neutralize the implementations’ differing stopping behavior.

	Solve%	D2 (s/gen)	D3 (s/gen)	D4 (s/gen)	D2 $\to$ D4
Baseline (CPU)	100	$6.6\pm 2.2$	$56.2\pm 32.5$	$1{,}175.7\pm 732.2$	177 $\times$
JAX-ESHN (CPU)	100	$312.6\pm 107.6$	$476.7\pm 118.5$	$964.9\pm 348.7$	3.1 $\times$

Table 6: CartPole (RL control) per-generation cost; both implementations on CPU (

n=30

, depths 2–4, Pop 150). Per-generation time isolates compute cost from the implementations’ differing stopping behavior (Baseline early-stops at solve, median 4–6 generations; JAX-ESHN runs the full 100-generation budget). Both solve 100% at every depth.

Task	Depth	Quadtree	HSHG
XOR	2	30/30 (100%)	0/30 (0%)
XOR	3	30/30 (100%)	0/30 (0%)
Parity-3	2	23/30 (76.7%)	0/30 (0%)
Sine	2	0/30 (mean fit 0.737)	0/30 (0%)

Table 7: Task performance through the full evolutionary pipeline: Quadtree vs. HSHG (

n=30

per condition). HSHG ran at Pop 50 with a 50-generation cap; the quadtree reference ran at Pop 150 throughout with a 100-generation cap, because the harness used for these particular runs takes its population from the neat-python configuration rather than from the run parameter. The comparison is therefore unmatched on population as well as on budget, in the quadtree’s favor. HSHG records a 0% solve rate in every condition. This negative result supports the structural-incompatibility claim (Section 1 ) and is a third contribution, not the headline.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Setting	XOR (scaling)	Parity-3 / circle / sine	CartPole
Depths $D$	1–7 (8–10 expl.)	2–4	2–4
Population	50–1000 (8/10 sizes)	150	150
Generations	10 (timing) / 30/300 (solve)	100	100
Seeds ( $n$ )	3 (42,123,456 / 42,43,44)	30 (0–29)	30 (0–29)
Fitness threshold	0.99 / 0.98	0.975 (circle, Parity-3)	0.95
		0.95 (sine)

Appendix

Table 8: Per-benchmark configuration.

D

denotes max_depth at initial_depth

=0

. Shared across all: division_threshold

=0.5

, variance_threshold

=0.03

, iteration_level

=1

, band_threshold

=0.3

, substrate activation sigmoid, CPPN activation pool

\{

tanh, sin, gauss

\}

. max_weight is

5.0

(PUREPLES) and

8.0

(JAX-ESHN), one of the implementation-default differences discussed in Section 7.4 . Paired cell values read Baseline/JAX-ESHN. The XOR campaigns used different fitness thresholds and disjoint seed sets, so the Baseline was held to the stricter bar; re-scoring every Baseline run at

0.98

changes a single D3 trial (

62.5\%\rightarrow 66.7\%

) and leaves every other depth cell in Table 2 unchanged, D7 included. Seeds control the JAX-ESHN runs throughout. On the Baseline side they control the XOR scaling campaign, but not the multi-benchmark and CartPole campaigns: that harness seeds NumPy’s generator whereas neat-python 0.92 draws from Python’s random module, so those Baseline seeds label runs without determining them.

Explore similar work

Tensor-Accelerated Eager Multi-Resolution Grids for Evolving Large-Scale Substrates
Aug 27, 2026Romain Claret, Michael O'Neill, Paul Cotofrei +1Neuroevolution Hypernetworks
University of Neuchâtel Neuchâtel, Switzerland · University College Dublin Dublin, Ireland
Early-Stopping Thresholds for ES-HyperNEAT: A Data-Driven Approach from Fitness Dynamics
Sep 11, 2026Romain Claret, Arthur Gygax, Michael O'Neill +2Early Stopping Evolutionary Optimization
University of Neuchâtel, Switzerland · Information Management Institute · Computer Science Department +1
Breaking the Central Bias: Spatially Partitioned Experts for Coordinate-Based Neuroevolution
Sep 10, 2026Romain Claret, Arthur Gygax, Michael O'Neill +3Neural Network Optimization Image Classification
University of Neuchâtel, Neuchâtel, Switzerland · University College Dublin, Ireland

Aug 27, 2026J/K move · Enter open · S save

Tensor-Accelerated Eager Multi-Resolution Grids for Evolving Large-Scale Substrates

Romain Claret, Michael O'Neill, Paul Cotofrei, Kilian Stoffel

University of Neuchâtel Neuchâtel, Switzerland · University College Dublin Dublin, Ireland

Neuroevolution Hypernetworks

Open paper AskPDF arXiv

In neuroevolution, indirect encoding generates neural network connectivity from a compact genome rather than specifying each connection. ES-HyperNEAT automatically discovers where to place hidden nodes by examining CPPN output patterns: it recursively subdivides space using a quadtree, expanding regions where CPPN outputs show high variance. This adaptive approach discovers network topology without manual substrate specification, extending the fixed-grid HyperNEAT framework built on NEAT. However, the quadtree resists tensorization. Each depth level depends on the parent's variance, forcing sequential evaluation. Different CPPNs produce different subdivision patterns, preventing batching. And variable leaf counts are incompatible with JAX's static shape requirement for JIT compilation. Our prior work confirmed these limits at depths exceeding 5, and a JAX reimplementation of the quadtree yielded only marginal speedup despite batched optimizations, motivating the eager reformulation presented here. We present EMR-HyperNEAT, which evaluates all positions at all resolutions up front, then filters using the same variance criterion: ES-HyperNEAT's subdivide_if(var >

θ

) becomes eval_all(); filter(var >

θ

). This performs more CPPN queries than necessary, but all queries become independent and parallelizable across both cores and population members, reducing complexity from \BigO(

4^D

) to \BigO(

4^D/P

) across

P

parallel cores. Recurrent substrate configurations become feasible through a connection type taxonomy. The experiments section validates 12-34

\times

on-device GPU speedup on XOR at depths 5-7, and empirically higher solve rates across benchmarks.

Abstract

Explore similar work

Tensor-Accelerated Eager Multi-Resolution Grids for Evolving Large-Scale Substrates

Early-Stopping Thresholds for ES-HyperNEAT: A Data-Driven Approach from Fitness Dynamics

Breaking the Central Bias: Spatially Partitioned Experts for Coordinate-Based Neuroevolution