Simulated annealing is a well-established general purpose optimiser that is often used for simulation optimisation. Parallelising it is non-trivial, as the algorithm is inherently sequential. This paper revisits the idea of speculative computation, in which several iterations of simulated annealing are executed in parallel, each based on speculation on the outcome of the previous iterations, and backtracking if the speculation was wrong. The paper extends the idea to the case of stochastic problems, for which several replications of the simulation have to be run to obtain a reliable estimate of a solution’s quality. We show how to find optimal speculation policies via dynamic programming, and that the optimal policies can be different from those found with the typically used greedy heuristic. We also examine how the results depend on correctly estimating the acceptance probability. Empirical results demonstrate the speed-up that can be gained via speculative execution in different settings.