Another option is to do N sequential candidate tests for each fresh random candidate. Where N is something that gets you most of the speed advantage of doing all sequential tests. Maybe like N=16.

Nice write-up!