Accuracy, precision and determinism are completely different things. Lossless compression reduces precision, and by that also accuracy, but it doesn't become undeterministic.
That said, my point is that determinism is incidental to how current generation of compression algorithms work, not an explicitly desired quality. And even that isn't strictly true, because e.g. x264 in certain multithreaded configurations already produces non-deterministic results that look as good as single-threaded encoding. For this use case - and thousands of others - losing determinism when switching to AI-based solutions really isn't a big deal.
Determinism is not incidental, it's the whole reason to invent formal systems and computing engines, including the current electronic ones.