If I remember correctly, the computation of the max itself is deterministic, but the backward pass can be implemented much more efficiently if you accept non-deterministic output (which is what cudnn is doing by default).