Aspects of the disclosure relate to validating autonomous control software for operating a vehicle autonomously. For instance, the autonomous control software is run through a driving scenario to observe an outcome for the autonomous control software. A validation model is run through the driving scenario a plurality of times to observe an outcome for the model for each of the plurality of times. Whether the software passed the driving scenario is determined based on whether the outcome for the software indicates that a virtual vehicle under control of the software collided with another object during the single time. Whether the validation model passed the driving scenario is determined based on whether the outcome for the model indicates that a virtual vehicle under control of the model collided with another object in any one of the plurality of times. The software is validated based on the determinations.