ES-HyperNEAT (Risi & Stanley, 2012) decides where to put hidden neurons by evaluating its CPPN at the \(2^n\) sub-cells of every cell it looks at. That’s why its search slows down exponentially as the substrate gains dimensions. But to first order those \(2^n\) samples only measure one thing, the squared gradient of the weight field, and a gradient costs one forward and one backward pass whatever the dimension.
So I swapped the test. The gradient version made the same split decision as sampling 98.7% of the time, and found equally good networks in about a sixth of the search time on a 3D substrate. A smarter sampler closes some of that gap, and the tree itself still grows exponentially.
Epistemic status: the equivalence is derived and checked numerically. The training comparison is 8 paired runs on one toy task, which is enough to rule out big differences in performance but not small ones.
Part 1 introduced ES-HyperNEAT and the steering task used here. The short version: HyperNEAT computes each weight from the coordinates of the two neurons it connects, \(w = f(\mathbf{p}, \mathbf{q})\), using a small network called the CPPN, and ES-HyperNEAT puts hidden neurons wherever \(f\) varies, finding those places with a quadtree.
Part 1 found that matching the substrate’s dimension to the problem helps, and that each extra dimension multiplies the cost of that quadtree search.
1. To first order, the 2ⁿ samples measure one gradient
The quadtree splits a cell when the CPPN’s weights at its \(2^n\) sub-cell centres vary by more than a threshold \(\tau\). Variance across a small cell is a measure of how fast the weight field changes there, which is what a gradient tells you.
Take a cell centred at \(c\) with half-width \(r\). Its sub-cell centres are \(c + \tfrac{r}{2}\sigma\), where \(\sigma\) runs over every pattern of \(\pm 1\) signs. Near \(c\) the field is roughly linear:
\[w\!\left(c + \tfrac{r}{2}\sigma\right) \approx w(c) + \tfrac{r}{2}\, \sigma \cdot \nabla w(c)\]Over the \(2^n\) sign patterns each \(\sigma_i\) is \(+1\) half the time and \(-1\) half the time, independently of the others, so \(\mathbb{E}[\sigma_i] = 0\), \(\mathbb{E}[\sigma_i^2] = 1\) and \(\mathbb{E}[\sigma_i \sigma_j] = 0\) for \(i \neq j\). The constant \(w(c)\) drops out of the variance, which leaves
\[\operatorname{Var}_{\text{sub-cells}}(w) \;\approx\; \left(\tfrac{r}{2}\right)^{2} \sum_{i=1}^{n} \left(\frac{\partial w}{\partial x_i}\right)^{2} \;=\; \left(\tfrac{r}{2}\right)^{2} \lVert \nabla w(c) \rVert^{2}\]So the tree, the threshold and everything else can stay as they are. Only one line changes:
\[\text{split if } \operatorname{Var}(2^n \text{ samples}) > \tau \quad\longrightarrow\quad \text{split if } \left(\tfrac{r}{2}\right)^{2}\lVert \nabla w(c)\rVert^{2} > \tau\]Numerically it holds up well. On random CPPNs the gradient’s estimate is within 5–15% of the sampled variance on the biggest cells, and indistinguishable from it on small ones.
The gradient is cheap because of reverse-mode automatic differentiation (backpropagation). It gets all \(n\) partial derivatives in one backward pass, for a small constant multiple of the forward cost, however big \(n\) is. The chain rule works back from the single output and reuses each intermediate value from the forward pass once, so a test costs one forward and one backward pass instead of \(2^n\) forward passes.
The tree itself doesn’t change, though. A cell the gradient marks as varying still splits into \(2^n\) new cells, so each test gets roughly \(2^n/2\) times cheaper while all \((2^n)^m\) cells are still there.
2. The two tests almost always agree
The approximation breaks when the field is far from linear across a cell. A saddle centred exactly on a cell has zero gradient at the one point the test looks at, so the gradient test thinks the cell is flat and never splits it; the Blind spot button below builds one. Sampling has its own blind spots. A bump centred on a cell gives four identical samples.
Compare outlines the cells where the two tests disagree.
How often does this matter in practice? We rebuilt trees for random CPPNs in 2 to 7 dimensions and scored every cell with both tests. They agreed on 98.7% of 2,580 split decisions. In 32 of the 34 disagreements the gradient split a cell that sampling left alone, and only 2 went the other way.
That lean matches section 1: on big cells the gradient’s estimate runs a little high, which tips borderline cells over the threshold. An extra split costs a bit of compute. A missed split loses detail, and those were rare.
3. The saving grows with dimension, but a better sampler narrows it
Against sampling as published, the gradient test needs 2× fewer CPPN passes in 2D and 61× fewer in 7D, and the search time follows the same curve.
One depth-2 tree, median over 10 random CPPNs with 4 inputs and 4 outputs. A backward pass counts as one pass; the corner-cache sampler is counted, not run.
| n | sampling | corner cache | gradient | time: sampling | time: gradient |
|---|---|---|---|---|---|
| 2 | 416 | 144 | 208 | 1.1 ms | 0.75 ms |
| 3 | 3,136 | 784 | 784 | 3.9 ms | 1.2 ms |
| 4 | 24,704 | 4,096 | 3,344 | 27 ms | 2.9 ms |
| 5 | 24,832 | 4,540 | 2,576 | 27 ms | 2.4 ms |
| 6 | 786,944 | 67,112 | 27,152 | 873 ms | 24 ms |
| 7 | 6,358,016 | 275,476 | 103,440 | 8.8 s | 0.10 s |
It isn’t quite a fair fight, though. The published algorithm samples sub-cell centres, and none of those samples ever get reused. A variant that samples cell corners instead, and caches them, can reuse each corner in every cell that touches it. On the same trees that makes sampling 3× cheaper in 2D and 16× cheaper in 7D.
Against that version the gradient test is actually more expensive in 2D, level in 3D, and only 2.7× cheaper in 7D. Both still climb steeply, because both still build a \(2^n\)-way tree.
4. It finds equally good networks with less search
Last, back to part 1’s steering task, on both the 3D substrate and the 2D map projection. The two versions share every line of code except the split test: same tree, thresholds, network, task, evolutionary algorithm and settings. They also share random seeds, so each gradient run starts from the same CPPN and gets the same random perturbations as its sampling twin. The two only drift apart once the tests first disagree about a split.
Top: mean ±1 standard error over 8 paired runs. Bottom: each seed; a dot inside its ring means both tests did equally well.
| 3D sampling | 3D gradient | 2D sampling | 2D gradient | |
|---|---|---|---|---|
| mean final score (8 runs) | 0.737 | 0.728 | 0.551 | 0.570 |
| runs reaching 0.68 | 8 / 8 | 7 / 8 | 4 / 8 | 4 / 8 |
| neuron-placement time per genome | 79 ms | 14 ms | 11.5 ms | 5.0 ms |
| one full training run | 5.9 min | 1.7 min | 1.2 min | 0.7 min |
Timings on an AMD Ryzen 7 7840HS, 15 runs in parallel. A genome is one candidate CPPN.
Performance came out the same. In 3D the mean final scores differ by less than 0.01, slightly in sampling’s favour (95% confidence interval for the difference: −0.027 to +0.002), and each version won four of the eight pairs. Most of that gap is one gradient run that was still improving when training stopped.
In 2D the gradient version is slightly ahead on average (95% confidence interval: −0.042 to +0.089), but it only won three of the eight pairs, with one tie. Its lead comes from two big wins. The 2D runs that succeeded were the same four seeds under both tests, so a run’s outcome is set by its starting CPPN and the substrate, not by the split test.
All 8 runs of each version, one per chase. Sampling and gradient panels always show the same seed.
Where they differ is time. Placing neurons took about a sixth as long in 3D and under half as long in 2D, so a full 3D training run finished 3.5× sooner. Going from 2D to 3D multiplied sampling’s placement cost by 7 and the gradient’s by 3, because sampling pays for both the bigger tree and the doubled cost of each test, while the gradient only pays for the bigger tree.
5. Caveats
This is a simplified ES-HyperNEAT written from scratch, with a fixed-shape CPPN trained by an evolution strategy instead of NEAT. Both versions share all of it, so the comparison is fair, but the absolute numbers would come out differently in the reference implementation.
It’s one toy task with 8 paired runs per substrate, which rules out big differences but not small ones. Part 1 describes the fixes that were needed before anything learned at all. Code and raw results are in /experiments/es-hyperneat/, and the two versions differ only in the function complexity() in eshn.py.
6. What a 5-dimensional creature looks like
Swapping the quadtree’s \(2^n\) samples for one gradient leaves the split decisions, and the networks that come out of them, almost unchanged, and it takes the exponential cost out of each test. The tree still branches \(2^n\) ways, so higher dimensions aren’t free. But 5, 6 and 7-dimensional substrates are now cheap enough to try, which raises the question of what a 5-dimensional task actually looks like.
In a life simulation, more of them than you might expect. A cell that senses which way the food is lives in 3D, but one that also cares which way it’s facing has three more axes, for six. A member of a swarm reacting to its neighbours’ positions and velocities lives in the same six. A creature that grows adds time to its 3D body, and a cellular automaton whose cells carry several chemical signals gets an axis for each one on top of its grid.
Outside artificial life it’s the same story. A drone’s controls depend on both its position and its orientation. A robot arm’s state lives in the six or seven dimensions of its joint angles. Medical scans are 3D volumes that change over time, and so is the weather. Whenever a task’s inputs and outputs come with a natural geometry of more than three dimensions, a substrate that matches it might make the right network simple, the way the 3D substrate did for the swimming cell.
Finding out no longer gets exponentially more expensive with every dimension, and I’d love to see what turns up.