Usage of "order of magnitude"

I consider the following to be correct...

"A" outperforms "B" by two orders of magnitude.

'orders of magnitude' in the above sentence is a noun, a quantity being specified and 'by' indicates the amount or size of a margin.

Similarly in the sentence

"The computer was orders of magnitude better than the abacus."

Orders of Magnitude is not an adverb, but a noun specifying a quantity. E.g.

X is 5 inches taller than Y

Replace '5 inches taller' with 'orders of magnitude better' and you would find no change in sentence structure.

You could say A outperforms B, but since you are adding the two orders of magnitude part, you should add the by.

Compare it with the word exceed, you could say A exceeds B, but when adding the latter part of your sentence (or any qualifier indicating by how much it exceeds), it is clearer when by is added.

A exceeds B by 20 meters

Therefore, in your case it would have to be:

A outperforms B by two orders of magnitude.