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

EMR-HyperNEAT: Replacing sequential quadtree subdivision with parallel eager evaluation for GPU-accelerated neuroevolution

Romain Claret; Michael O'Neill; Paul Cotofrei; Kilian Stoffel· 2026· DOI 10.48550/arXiv.2608.27612

The core problem

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

The experiments section validates 12-34\times on-device GPU speedup on XOR at depths 5-7, and empirically higher solve rates across benchmarks. This demonstrates that the eager reformulation not only accelerates computation but also improves evolutionary outcomes, likely due to the increased parallelism enabling larger population sizes or more generations within the same computational budget.

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

The shift from sequential quadtree subdivision to eager evaluation represents a fundamental trade-off: performing more CPPN queries in exchange for full parallelizability. This trade-off is favorable on modern GPU architectures where parallel throughput vastly exceeds sequential performance. The complexity reduction from \BigO (4^{D}) to \BigO (4^{D} / P) highlights the scalability potential for large-scale substrates. The connection type taxonomy enables recurrent configurations, broadening the applicability of HyperNEAT-based methods. Future work may explore adaptive filtering strategies to reduce redundant queries while preserving parallelism, and extend the approach to even higher depths and more complex benchmarks.

CS practitioners and researchers

Opening member content…