Hill Climbing, Backpropagation and NEAT on the Same XOR Problem
I expected backpropagation to learn XOR with the least work of the three methods I had built. It computes the direction every weight should move instead of guessing, so it seemed obvious. On a small network with 2 inputs, 3 hidden neurons and 1 output (a 2-3-1 network) it needed 9,268 to 11,124 network runs at learning rate 0.5. A hill climber that nudges every weight at random, and keeps the nudge only if the error drops, needed 1,512 to 1,648. Raising the learning rate to 2 brought backpropagation down to 3,028 to 3,372, still about twice the hill climber’s work. The order only flipped once the problem grew to a full adder with two outputs.
The setup
XOR as a learning problem is four examples: the inputs 00, 01, 10 and 11 should produce 0, 1, 1 and 0. It is the classic first test because no single neuron can learn it, so the network needs a hidden layer. Each neuron multiplies its inputs by weights, adds a bias, and squashes the sum through a sigmoid, an S-shaped curve that flattens out near 0 and 1. Learning means finding weights and biases that make the outputs match.
All three learners live in one Node.js project, which is a learning exercise and is not public. I wrote the network, the hill climber, the backpropagation and the NEAT implementation myself. Claude Code wrote the test suite I implemented against and the comparison script whose output is quoted below, so the numbers come from a harness I did not write but can rerun.
- Hill climbing: every round, add a random amount between -0.5 and +0.5 to every weight and bias. Run the four XOR cases, and restore the previous weights if the total error did not go down.
- Backpropagation: calculus tells each weight which way to move to reduce the error, and the learning rate sets how far it moves. The weights are updated after every example, on the same 2-3-1 network. One pass through the four examples is an epoch.
- NEAT: NeuroEvolution of Augmenting Topologies. A population of 150 networks, each described by a genome listing its connections, starts with no hidden nodes. Each generation, the better networks breed and mutate, adding weights, connections and nodes. Networks are grouped into species so that one with a freshly added node, which usually makes it worse at first, only competes with similar networks while its new weights get tuned.
Every method stops at the same target: total squared error below 0.04 over the four cases. (The two-output problem later on uses 0.08.) Work is counted in one unit that means the same thing for all three. A network run is one forward pass on one input. The hill climber spends one evaluation, four runs, per round. Backpropagation spends an evaluation plus one training pass per example, eight runs, per epoch. NEAT spends four runs per genome per generation.
Each configuration ran ten independent learners, and each figure is the median over the ones that reached the target. I ran each configuration three times, so a range is the spread of three medians.
XOR
| method | median network runs, three repeats | learners that reached the target |
|---|---|---|
| hill climbing, batch A | 1,512 to 1,648 | 9 or 10 of 10 |
| backpropagation, learning rate 0.5, batch A | 9,268 to 11,124 | 10 of 10 |
| NEAT, batch A | 64,800 to 67,800 | 10 of 10 |
| hill climbing, batch B | 1,340 to 1,544 | 10 of 10 |
| backpropagation, learning rate 2, batch B | 3,028 to 3,372 | 9 or 10 of 10 |
| NEAT, batch B | 65,400 to 69,000 | 10 of 10 |
Each batch is three repeats of all three methods, and the only setting that differs between them is backpropagation’s learning rate. The hill climber and NEAT rows in the two batches are the same method measured twice, which shows how much the figures move on their own.
The explanation I have is that the network is tiny. The 2-3-1 network has 13 parameters: three hidden neurons with two weights and a bias each, plus an output neuron with three weights and a bias. In 13 dimensions a random step has a fair chance of pointing downhill. A learner that tries a direction and throws it away when it is wrong gets there in surprisingly few evaluations.
Backpropagation never takes a step in the wrong direction; its steps were just small. At learning rate 0.5 it crawled across the flat regions of the sigmoids near 0 and 1, and took 1,158 to 1,390 epochs. Quadrupling the rate cut that to 378 to 421 epochs. The method was fine, and my setting of it was the problem.
The full adder
A full adder adds three bits and outputs a sum and a carry. That is eight cases and two outputs instead of four and one. Both fixed-shape learners used a 3-4-2 network, which has 26 parameters, and backpropagation kept learning rate 2.
| method | median network runs, three repeats | learners that reached the target |
|---|---|---|
| hill climbing | 10,064 to 12,120 | 9 or 10 of 10 |
| backpropagation | 3,640 to 3,928 | 10 of 10 |
| NEAT | 205,200 to 218,400 | 8 or 10 of 10 |
The order reversed. Backpropagation now needs about a third of the hill climber’s work. My explanation is the same one run backwards: a random step in 26 dimensions is far less likely to help than one in 13, while the gradient points downhill however many weights there are. I have not isolated that, though, since the full adder also doubled the cases and the outputs, and I tried only one learning rate on it. The dimension argument is the standard reason large networks are trained with gradients, and it is also why XOR is a poor place to see it.
What NEAT spends its extra work on
NEAT needed 64,800 to 69,000 network runs on XOR, 39 to 51 times the hill climber. It took 108 to 115 generations, and every generation evaluates all 150 networks. What that buys is the one thing the other two cannot do: it chooses the network’s shape.
The other two learners needed me to decide on three hidden neurons, or four for the full adder, before they started. The example NEAT solutions from the six XOR repeats had between 4 and 7 hidden nodes and 18 to 21 connections. On the full adder they ranged from 4 hidden nodes and 23 connections to 12 hidden nodes and 36. It did not choose a smaller shape than mine; its solutions were bigger. The cost is not worth paying when a person can choose a shape that works in advance. The rest of this series uses NEAT on Monopoly, where I had no idea what shape a good player’s network should have.
What the counts leave out
- A network run is not a unit of time. Backpropagation’s backward pass is real work that the count ignores, and so is the hill climber’s copying of weights. Wall-clock time is too noisy at this size to replace it: backpropagation at learning rate 2 took 4.4 to 18.3 ms for the same configuration across three runs.
- Medians exclude learners that failed. A run that got stuck and never reached the target counts only in the “reached the target” column, which is why that column is there. With an even number of successes, the script reports the upper of the two middle values.
- Three repeats is a small sample. The ranges are the spread I saw, not a confidence interval.
The part I expect to generalise is not which method won. A method’s reputation comes from the problems it is famous for, and on a small enough problem the naive method can win honestly. I only found out by counting the same unit of work for all three, at more than one setting of the knob the losing method depends on.