PaperlayerView exact revision on arXiv

Source-linked AI summary

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

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

arXiv:2608.27612v1cs.NEcs.AIcs.LG

TL;DR

ES-HyperNEAT’s adaptive quadtree limits batching and JAX compilation at larger depths. EMR-HyperNEAT evaluates static multiresolution grids eagerly, enabling parallel filtering and higher solve rates, with 12–34× GPU speedups on XOR; the approach trades extra queries and memory for parallelism and is less favorable at low depth with few generations.

  • Problem

    ES-HyperNEAT’s quadtree forces sequential, irregular evaluation that resists batching and conflicts with JAX static shapes at depths exceeding 5.

  • Method

    EMR-HyperNEAT evaluates all positions across resolutions up front, batch-parallelizes CPPN queries, and filters them hierarchically by variance.

  • Results

    EMR-HyperNEAT yields higher solve rates across benchmarks and 12–34× on-device GPU speedup on XOR at depths 5–7.

  • Takeaways & Limitations

    Eager bottom-up evaluation recovers substrate positions missed by top-down traversal and makes recurrent substrate configurations computationally feasible.

  • Takeaways & Limitations

    EMR-HyperNEAT requires adapted thresholds, incurs redundant CPPN queries and substantial memory growth, and is less advantageous at low depth with few generations.

Abstract

from arXiv · show

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.

1 Introduction

ES-HyperNEAT adaptively discovers hidden-node locations, but its quadtree structure limits tensorization and JAX compilation. EMR-HyperNEAT reformulates discovery eagerly so CPPN evaluations can run in parallel.

  • 1 Introduction: ES-HyperNEAT uses CPPN output variance to recursively subdivide space and discover hidden nodes without manual substrate specification.This extends fixed-grid HyperNEAT through indirect encoding from a compact genome.
  • 1 Introduction: The quadtree forces sequential evaluation because each depth depends on parent variance, while CPPN-specific subdivision patterns prevent batching.Variable leaf counts also conflict with JAX’s static-shape requirement for JIT compilation.
  • 1 Introduction: EMR-HyperNEAT evaluates all positions at all resolutions before filtering them with the same variance criterion.This eager reformulation performs extra CPPN queries but makes them independent and parallelizable across cores and population members.
  • 1 Introduction: EMR-HyperNEAT reduces complexity from O(4^D) to O(4^D/P) across P parallel cores.The experiments validate 12–34× on-device GPU speedup on XOR at depths 5–7 and report higher solve rates across benchmarks.

2 Background

ES-HyperNEAT removes the need for a predefined substrate by using quadtree searches over CPPN-generated connectivity, but sequential queries become increasingly costly and resist tensor batching.

  • 2 Background: HyperNEAT uses a CPPN to map source and target spatial coordinates to connection weights, allowing compact genomes to specify large networks.ES-HyperNEAT further adaptively places hidden nodes through quadtree subdivision.
  • 2 Background: ES-HyperNEAT performs separate quadtree traversals for input-to-hidden and hidden-to-hidden discovery.The hidden-to-hidden phase performs sequential queries for each discovered hidden position.
  • 2 Background: Each additional depth roughly quadruples generation time because traversal cost grows as 4^D.The passage describes this growth for the sequential quadtree approach.
  • 2 Background: Quadtree traversal resists tensor batching because subdivision patterns vary, children depend on parent variance, and leaf counts are variable.These properties also conflict with JAX’s static-shape requirement for JIT compilation.

3 EMR-HyperNEAT Algorithm

EMR-HyperNEAT replaces sequential quadtree traversal with static multiresolution grids, batched CPPN evaluation, and hierarchical variance filtering. Its eager evaluation supports superset discovery and parallel complexity, but requires threshold adaptation and incurs memory and query costs.

  • 3 EMR-HyperNEAT Algorithm: EMR-HyperNEAT precomputes static multiresolution grids, batch-evaluates CPPN queries with vmap, and applies hierarchical variance filtering.These three stages replace the sequential quadtree with tensor-compatible operations.
  • 3.1 Hierarchical Grid and Batch Query: The complete grid covers depths 0 through D, making all position arrays static and compatible with JIT compilation.The total position count grows from 1,364 at depth 4 to 87,380 at depth 7 and 358M at depth 13.
  • 3.1 Hierarchical Grid and Batch Query: Independent CPPN queries run in parallel as O(N/P) wall-clock work, with population parallelization evaluating all genomes simultaneously.Figure 1 contrasts this eager process with ES-HyperNEAT’s sequential subdivision and filtering.
  • 3.2 Variance Filtering and Active Mask: Variance is computed bottom-up from children to parents while the active mask propagates top-down and filters each parent’s four children as a block.This preserves parallel filtering across the hierarchy.
  • 3.2 Variance Filtering and Active Mask: Under identical variance and band thresholds, EMR-HyperNEAT discovers a superset of ES-HyperNEAT’s positions and produces identical connection sets when the position sets match.Eager evaluation recovers high-variance children inside parents that top-down pruning would otherwise discard.
  • 3.3 Threshold Adaptation: Eager evaluation requires adapted thresholds because variance is computed over all positions rather than only already-accepted regions.The original ES-HyperNEAT thresholds produce no solutions under eager evaluation.

4 Connection Type Taxonomy

EMR-HyperNEAT makes recurrent substrates computationally feasible by classifying connections into directional and self-referential primitives. Experiments show that connection type materially affects convergence across tasks.

  • 4 Connection Type Taxonomy: The taxonomy classifies connections as Forward, Backward, Lateral, or Self-loop using source and target Y coordinates.These correspond respectively to forward, feedback, same-layer, and self-connections.
  • 4 Connection Type Taxonomy: Enabling or disabling connection primitives yields six available substrate configurations.Table 2 denotes Forward, hidden-to-hidden, Backward, Lateral, and Self components with F, H, B, L, and S.
  • 4 Connection Type Taxonomy: 100% convergence on XOR is achieved by Backward and Lateral connections, compared with 20% for Feedforward connections.The comparison uses depth 5, population 300, and 10 replications.
  • 4 Connection Type Taxonomy: On Visual Discrimination, Backward connections achieve 100% convergence while Lateral and Self connections hurt performance.Table 3 reports cross-problem convergence rates by connection type with Fisher’s exact testing against Feedforward.

5 Experimental Evaluation

Experiments compare EMR-HyperNEAT with ES-HyperNEAT on XOR and financial data, showing significant GPU speedups, tighter runtime variance, higher solve rates, and favorable deeper-scaling behavior.

  • Experiments used XOR across depths 1–7, populations 50–1000, 30 generations, and 504 total runs, comparing JAX EMR-HyperNEAT against PUREPLES ES-HyperNEAT.
  • Scaling and Speedup: Across 30-generation runtime scaling, depth 7 approached a ∼100× cumulative-runtime IQR median, while depth 13 widened because disk I/O dominated costs.
  • Scaling and Speedup: At depths ≥5, EMR-HyperNEAT GPU achieved significant speedups versus ES-HN with p< .001, Cliff’s δ≥0.99, and large effects after Holm-Bonferroni correction.
  • Scaling and Speedup: At depth 7, estimated runtime standard deviation was 3.6h for ES-HN, 31min for EMR CPU, and 1.9min for EMR GPU, producing a 114× tighter bound.
  • Solution Quality: At depth 6, EMR-HyperNEAT solved XOR in 100% of runs versus 33% for ES-HyperNEAT, while both reached identical maximum fitness above 0.99 when successful.
  • Real-World Benchmark: On 94,464-observation CRSP/Compustat data, EMR-HyperNEAT was 5.5× faster at depth 6 despite streaming deeper layers from CPU RAM.

6 Discussion

Discussion identifies threshold adaptation and resource scaling as important boundaries: eager evaluation can require different thresholds, while memory and I/O costs grow rapidly at extreme depths.

  • EMR-HyperNEAT requires adapted thresholds because eager variance computation includes all positions rather than only regions already accepted by ES-HyperNEAT.
  • At low depth with few generations, ES-HyperNEAT remains preferable because EMR-HyperNEAT’s JIT overhead is not sufficiently amortized.
  • Memory scales as 4^D, reaching ∼10 GB at depth 7 with population 500 and 358M positions at depth 13 with population 300.
  • At depth 13, disk-stored weight arrays dominate both JIT time at ∼5.3 h and per-generation cost at ∼5.8 h.

7 Conclusion

EMR-HyperNEAT is presented as the first massively parallel adaptive substrate discovery algorithm, with speedups increasing with depth. It also broadens practical substrate discovery through higher solve rates and tractable recurrent configurations.

  • EMR-HyperNEAT is presented as the first massively parallel adaptive substrate discovery algorithm.
  • Significant speedups grow with depth across the reported evaluations.
  • Bottom-up evaluation discovers a superset of substrate positions and yields higher solve rates in practice.
  • The connection type taxonomy makes recurrent substrates computationally tractable.
  • The reformulation makes previously unreachable substrate configurations accessible at new depth and population scales.
Loading 2608.27612v1…