I'd expect that it's simply that the additional constraints implied by requiring deterministic behavior precludes certain optimizations that can lead to improve

I'd expect that it's simply that the additional constraints implied by requiring deterministic behavior precludes certain optimizations that can lead to improved running time. Iow, if you can never do X, then you cannot write any algorithm that may do X.