This summary has some important errors in it. If you added each partial product in parallel, you would get O((log N)^2) delay, because each addition has O(log N) and there are O(log N) levels in the tree. The Wallace tree has total delay O(log N), which is smaller.

The way you learned in school is to add each number up in series, which doesn’t give the correct parallel structure to multiply numbers quickly in parallel.

For example,

      1234
    x 5678
   -------
      9872
     8638
    7404
   6170
   -------
   7006652

In school, you would add each part column by column, and keep track of a carry digit. This gives a fairly bad delay from right to left, since the result of a carry from the right-hand columns will affect the results of the left-hand columns, many operations later. If you add pairs of numbers in parallel, it will be faster, but you will still have to propagate carry from right to left.

The key insight in the Wallace tree is to reduce these numbers hierarchically, but only bitwise. Three bits in the same position are reduced to two bits in different positions, at each level. Eventually, there are only two levels left, and we do a single addition.

This process for addition is completely alien to the way humans do it.

> (for example by adding pairs of numbers first to make a list half as long).

That is absolutely not how it works. There is only one pair of numbers being added here—at the end, the very last two numbers are added together normally. If you try to add each pair of numbers in parallel, you will add more gate delay as the carry bit has to propagate all the way from the right side to the left at each level in the tree (instead of only once at the end).

With the Wallace tree, the carry bit only has to propagate the width of the numbers once, at the very end. This is much faster. At the beginning, again, bits are being added with full adders which shrinks the tree at a rate of 3:2 (not 2:1) where possible. You will notice that the height of the numbers goes from 8 to 6 (not 4), then 6 to 4, 4 to 3, and then 3 to 2. The final two numbers are then added normally.

Your explanation here is described in my original reply as "that adding 3 numbers to make two results is much faster in hardware than adding 2 numbers to make one result."

I initially typed a further explanation of "no carry chain is necessary, so each addition becomes constant time", but decided for most readers here, they either wouldn't be hardware experts and wouldn't see why a carry chain was relevant, or would be hardware experts in which case it's already obvious, since full adders are used in loads of things wired like this.

Thankyou for expanding in a lot more detail though.