Sample, Scrutinize and Scale: Effective Inference-Time Search by Scaling Verification

Much attention has been recently (and rightfully) been given to scaling test-time compute by extending the length of reasoning chains (e.g., o1, r1). This paper focuses on two other old-school axes of test-time compute scaling, sampling and verification, that provide fundamentally important knobs for massive and embarassingly parallel scaling and are complementary with other test-time compute scaling strategies (e.g., use of long-COT reasoning models).

TLDR: This paper studies scaling trends along the sampling and verification axes of test-time compute, showing that:

1. Even just by naviely sampling a lot of responses and asking models to self-verify, blackbox (public API-only) queries to our 2024-era (non-reasoning) Gemini models are enough to exceed o1-Preview reasoning capabilities.
2. The self-verification accuracy of frontier models counterintuitively improves on its own the more that you sample due to an implicit scaling phenomenon.
3. Frontier models are poor at self-verification out-of-the-box, but you can fix this by expending more compute and following two basic principles. 1) Optimal writing styles for generation (i.e., COT) are not optimal for verification, so always have models expend compute to rewrite their outputs. 2) Models are bad at finding errors and hallucinations unless you give their locations---but you can fix this by sampling a lot and having models compare between different output samples, since their diffs narrow down where errors/hallucinations may lie.