My impression is that the complex optimization happens during training but that the actual inference is using some kind of greedy algorithm like beam search. If the inference algorithm was using simulated annealing or something like that that would be different.