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

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

Source-linked AI summary

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

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

arXiv:2608.24480v1Aug 25, 2026cs.NEcs.DCcs.LG

TL;DR

ES-HyperNEAT’s adaptive quadtree creates variable-cardinality substrate outputs that block population-level GPU vectorization. The paper introduces JAX-ESHN and benchmarks it against PUREPLES across five tasks, finding that the scaling divergence persists across task types and under CPU-only control. The analysis identifies parent-gated hierarchical filtering as essential for preserving adaptive sparsity and motivates EMR-HyperNEAT’s eager static-grid reformulation.

Problem
ES-HyperNEAT lacks population-level static-shape vectorization because each CPPN discovers a unique substrate position set, leaving the scalability of adaptive substrate discovery unresolved.
Method
The paper implements JAX-ESHN with TensorNEAT and JAX, then benchmarks it against the CPU-based PUREPLES Baseline across XOR, Parity-3, circle, sine, and CartPole.
Results
Across five benchmarks, Baseline runtime grows steeply as solve rates collapse, while JAX-ESHN runtime grows far more slowly; CPU-vs-CPU control rules out GPU hardware as the cause.
Takeaways & Limitations
Scalable substrate discovery must preserve hierarchical parent-gated filtering while satisfying static-shape batching constraints; EMR-HyperNEAT provides the companion reformulation described here.
Takeaways & Limitations
The study uses cost-controlled toy-scale benchmarks rather than representationally deep domains, so higher-dimensional evaluation such as MNIST remains future work.

Abstract

from arXiv · show

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.

1 Introduction

ES-HyperNEAT’s adaptive quadtree enables task-tailored substrate discovery but creates a structural barrier to population-level static-shape vectorization. JAX-ESHN investigates this barrier through a GPU-targeted implementation and cross-task empirical evaluation.

ES-HyperNEAT evolves substrate topology through variance-driven quadtree subdivision, discovering sparse, task-appropriate neuron placements from CPPN-generated fields.
Each CPPN discovers a different number and arrangement of substrate positions, preventing population-level vmap under static-shape compilation.The same adaptivity that produces problem-tailored sparse substrates breaks the uniform-shape assumption required for batching.
JAX-ESHN combines TensorNEAT CPPN evolution with JAX-based substrate construction to test whether batching can overcome sequential quadtree discovery.
The paper contributes mechanistic and empirical evidence that adaptive quadtree discovery is structurally incompatible with static-shape compilation, while dynamic-shape GPU approaches remain theoretical.
Across five tasks, JAX-ESHN reaches near-100% solve rates at depths where the Baseline falls to 4.2%, although the comparison carries a NEAT-library confound.
The benchmarks use cost-controlled XOR, Parity-3, circle, sine, and CartPole tasks, while higher-dimensional evaluation such as MNIST remains future work.

2 Background and Related Work

ES-HyperNEAT extends coordinate-based indirect encoding by evolving substrate topology rather than requiring a predefined architecture. Existing GPU neuroevolution systems rely on fixed shapes, leaving variable-cardinality substrate discovery unresolved.

NEAT evolves topologies and weights, while HyperNEAT uses CPPNs to generate spatially organized connection weights for predefined substrates.
ES-HyperNEAT replaces the predefined substrate with adaptive quadtree discovery, placing neurons where CPPN output variance indicates information density.
The Baseline uses CPU-sequential neat-python evolution, whereas JAX-ESHN builds on TensorNEAT’s JAX/XLA CPPN-evolution infrastructure.
JAX jit and vmap require fixed, uniform tensor shapes, but ES-HyperNEAT produces variable-shape networks because each CPPN discovers a different substrate topology.
The generation loop batches CPPN sampling and transformation, then sequentially discovers substrates, builds networks, evaluates fitness, and returns fitnesses for selection.

3 Implementation Architecture

JAX-ESHN preserves the Baseline’s adaptive three-phase quadtree substrate-discovery algorithm while placing CPPN evolution and selected computations in JAX. Variance-gated recursion makes each CPPN’s discovered topology data-dependent.

JAX-ESHN uses TensorNEAT for CPPN evolution and JAX for substrate discovery, network construction, and evaluation within a two-level evolutionary system.
Depth denotes the maximum quadtree level, with depth d yielding 4^(d+1)-1 potential positions across the 2D substrate.
Each CPPN is processed sequentially after population-level transform batching because variable topology discovery prevents vectorizing the inner loop.
Substrate discovery has three phases: input-to-hidden, hidden-to-hidden expansion, and hidden-to-output connection discovery.
Every phase builds a variance-driven quadtree and extracts connections through band-detection pruning.
Variance-gated subdivision creates CPPN-dependent output cardinality: high-variance quadrants recurse, while surviving leaves can become hidden nodes after pruning.
The architecture places sequential per-CPPN substrate discovery between batched population ask and tell operations.

4 Optimizations

The optimizations batch work within each CPPN and accelerate evaluation, but they cannot remove the population-level barrier caused by variable-cardinality quadtree outputs. Consequently, measured gains plateau near 1.7×.

The unoptimized implementation retains population-level transform vmap but performs non-batched substrate queries, standard BFS cleaning, and sequential fitness evaluation.
O1 batches quadtree division queries across children at each level, reducing them to one vmap(QueryCPPN) call per coordinate list.
O2 batches pruning queries across leaves, issuing one mega-batch for 4N coordinates and computing band tests per leaf.
O3 vectorizes network evaluation over test inputs with vmap(ForwardPass), while O4 precomputes quadrant offsets for broadcasted child-position calculation.
1.73× is the best measured combination speedup over unoptimized JAX-ESHN at population 1000, with within-CPPN batching plateauing near 1.7×.
Per-CPPN variability still blocks population-level vectorization and keeps GPU utilization low in static-shape frameworks.
Padding preserves sequential traversal, static bounds replace adaptive discovery, and dynamic recompilation defeats JIT caching; eager shared-grid evaluation works by replacing traversal.

5 HSHG: An Attempted Solution to the Quadtree Bottleneck

HSHG replaces adaptive quadtree discovery with fixed-position, independently filtered arrays, enabling static-shape batching but losing hierarchical sparsity. This causes severe over-discovery and poor fitness on XOR.

HSHG design: HSHG pre-generates fixed positions at every depth and queries all corresponding CPPN weights in one mega-batch.At depth 3, this produces 85 positions before filtering.
HSHG design: Per-position variance filtering replaces both quadtree subdivision and band-detection pruning, eliminating parent-gated adaptive discovery.The quadtree subdivides only when a parent passes the variance threshold, producing sparse topology.
Failure mechanism: Overlapping HSHG neighborhoods can independently detect one CPPN feature, creating duplicate hidden nodes that the quadtree avoids.Two fixed neighborhoods intersecting one informative spike both pass the variance test, whereas adaptive subdivision creates one position.
XOR results: 29–63 HSHG hidden nodes versus 1–2 for the quadtree shows order-of-magnitude over-discovery across tested thresholds and grid depths.The probe used variance thresholds 0.03–0.5 and grid depths 2–4 across 50 CPPN evaluations.
XOR results: Best fitness was 0.746 with one discovered node, while 62-node solutions plateaued at 0.500, so parameter adjustment did not restore performance.The result indicates that fixed-position filtering fails to preserve the adaptive sparsity needed by ES-HyperNEAT.

6 Experimental Results

Experiments show that quadtree discovery creates a structural scaling bottleneck, while JAX-ESHN improves deep-substrate reliability and runtime predictability. CPU-vs-CPU controls reproduce the divergence across task types, separating implementation effects from GPU hardware.

6.3 Runtime and Solve Rate Comparison: JAX-ESHN achieves near-100% solve rates across D3–D7, while the Baseline falls from 62.5% at D3 to 4.2% at D7.At D7, the Baseline requires nearly 14 hours for 30 generations, whereas JAX-ESHN remains reliable under the tested budgets.
6.3 Runtime and Solve Rate Comparison: At D3–D5, the Baseline is 150–600× faster in wall-clock time, but at D7 it takes 824 minutes and solves at 4.2% versus JAX-ESHN’s 348 ± 157 minutes at 100%.Baseline runtime scales approximately 7× per depth level, with the sharpest solve-rate drop between D5 and D6.
6.3 Runtime and Solve Rate Comparison: Deep-substrate timing uses n = 3 seeds, so D5–D7 estimates have wide intervals and should be read as indicative of magnitude and direction.The projected D5 total is 1,618 minutes with a 95% t-interval of [213, 3,022], widening to [1,830, 5,251] at D7.
6.3 Runtime and Solve Rate Comparison: Depth significantly affects Baseline generation time and solve rate, while a polynomial model predicts generation time with R2 = 0.95.The reported effects are F = 87.04, η2 = 0.54, p < 10−71 for generation time and χ2 = 42.73, p ≈ 1.3 × 10−7 for solve rate.
6.4 Construction Overhead: Compilation Plus First Generation (JAX-ESHN): Construction overhead grows exponentially through moderate depths, then plateaus: per-level growth slows to 1.37× at D5→D6 and 1.18× at D6→D7.At Pop 1000, construction reaches 16 minutes at D3 and exceeds 3 hours at D6 before the plateau continues through D10.
6.4 Construction Overhead: Compilation Plus First Generation (JAX-ESHN): JAX-ESHN’s dominant cost is construction rather than search, with Pop ≥750 often solving during the construction generation at D4–D7.At Pop 50, mean generations-to-solve falls from 155.3 at D1 to 6.0 at D7.
6.4 Construction Overhead: Compilation Plus First Generation (JAX-ESHN): At Pop 1000, construction overhead is 18–23× that at Pop 50 across D3–D7, closely matching the 20× population ratio.The population-linear scaling arises from each CPPN’s unique substrate discovery, which prevents population-level vectorization.
6.5 Multi-Benchmark Validation: CPU-vs-CPU controls show the Baseline scaling 65–71× from D2 to D4 versus 4.8–5.1× for JAX-ESHN, isolating implementation effects from hardware.The quadtree’s per-generation cost, rather than GPU versus CPU choice, drives the steep divergence.

7 Discussion

The discussion identifies adaptive quadtree topology discovery as the scaling bottleneck and shows that preserving its parent-gated sparsity is essential. It also bounds the practical advantage of JAX-ESHN and motivates EMR-HyperNEAT as a structurally compatible solution.

Structural diagnosis: Adaptive quadtree topology uniqueness prevents static-shape population vectorization, while preserving adaptivity retains construction overhead rather than per-generation evolution cost.Each CPPN discovers different positions, preventing identical batch shapes; removing adaptivity destroys solve rates.
HSHG and alternatives: 0% solve rate across 120 HSHG runs shows that independently filtering pre-generated positions does not preserve ES-HyperNEAT’s adaptive sparsity.Failures were caused by bloated substrates or networks plateauing below threshold, requiring a redesign of node discovery rather than a simple data-structure swap.
Construction-overhead plateau: Construction-overhead growth remains approximately 1.2–1.4× across D5–D10, whereas Baseline runtime continues scaling at approximately 7× per depth level.This divergence makes JAX-ESHN competitive on deeper substrates despite its upfront compilation cost.
Practical regime: At D7 Pop 500, JAX-ESHN achieves 100% solve rate in 348 ± 157 minutes versus the Baseline’s 4.2% in 824 ± 528 minutes, but matched-budget throughput favors the Baseline.The retry-adjusted effective advantage is approximately 56×, while JAX-ESHN’s projected 30-generation total exceeds the Baseline’s by more than 4×.
Practical regime: JAX-ESHN is recommended for D6+ when Baseline reliability collapses, whereas the Baseline is preferred for shallow substrates and extended XOR evolution.The recommendation is workload-dependent because CPU multi-benchmark comparisons reverse the per-generation cost relationship.
From diagnosis to solution: EMR-HyperNEAT resolves the barrier by eagerly evaluating a static multi-resolution grid while retaining hierarchical parent-gated masking.Its fixed grid is viable because variance filtering preserves grouped pruning; under matched thresholds, it discovers a superset of quadtree positions.

8 Conclusion

The paper identifies adaptive quadtree substrate discovery as structurally incompatible with static-shape compilation and shows that the bottleneck is construction-bound rather than search-bound. Across five task types, JAX-ESHN scales more reliably than the Baseline, while a CPU-vs-CPU control indicates the divergence is not caused by GPU hardware.

JAX-ESHN construction cost plateaus beyond depth 5, while search becomes nearly trivial once a deep substrate is built.This locates the scalability limit in substrate construction rather than evolutionary search.
Near-100% solve rates for JAX-ESHN contrast with the Baseline’s 4.2% at deep substrates, although construction overhead dominates total runtime.The cross-implementation solve-rate comparison carries a NEAT-library confound.
Across XOR, Parity-3, circle, sine, and CartPole, Baseline runtime grows steeply as solve rates collapse, whereas JAX-ESHN runtime grows far more slowly.The tasks span Boolean, continuous, and control settings.
A CPU-vs-CPU control rules out GPU hardware as the cause of the observed scaling divergence.The comparison supports attributing the divergence to substrate-discovery implementation behavior.
Future evaluation on higher-dimensional problems such as MNIST is needed to strengthen the generality claim.The present benchmarks were selected for cost-controlled scaling behavior rather than representational depth.
The released repository includes implementations, benchmark configurations, raw per-seed results, and scripts that recompute the scaling and multi-benchmark tables.

A Reproducibility Details

The reproducibility record separates experimental campaigns by backend and sampling, documents shared and benchmark-specific configurations, and identifies the provenance of reported timings and solve rates. It also distinguishes measured timings from projected totals.

The appendix separates the two experimental campaigns because they differ in backend and sampling.
The Baseline ran on an Apple M4 Max CPU, while JAX-ESHN used NVIDIA RTX 2080 Ti hardware for GPU scaling and CPU runs for the multi-benchmark campaign.The scaling study spans multiple driver and CUDA versions, while later campaigns use a pinned environment.
Table 8 records shared parameters including division_threshold = 0.5, variance_threshold = 0.03, and max_weight values of 5.0 for PUREPLES and 8.0 for JAX-ESHN.Paired table cells are reported as Baseline/JAX-ESHN, and D denotes max_depth with initial_depth = 0.
JAX-ESHN timing entries use 10-generation forced reruns at depths D1–D7 with seeds 42/43/44, while solve rates come from a 300-generation campaign.The 30-generation Total in Table 2 is projected rather than measured wall-clock time.