> That's far from O(1). Now you need to transfer the weights back and test them.

I think what matters most is that the verification is much, much cheaper than the calculation itself to prove that work was done, it doesn't explicitly have to be O(1), eg. the magnitude difference has to exceed a certain threshold to make proof of work viable.