A lot of current compression techniques use prediction followed by some set of correction data to fix mis-predictions. If the prediction is more accurate, you c

A lot of current compression techniques use prediction followed by some set of correction data to fix mis-predictions. If the prediction is more accurate, you can have a smaller correction set. But you're right the predictor does need to be reproducible - the output must be exactly the same to match encoder and decoder behavior. While I don't think this is big focus right now for many, I don't think there's a fundamental reason why it couldn't be, though probably at the cost of some performance.