On the Query Complexity of Verifier-Assisted Language Generation

In the simplest form, called best-of-N, the language model generates N candidate responses, which are then scored by the verifier, and the highestscored candidate response is chosen as the output of the inference process (Cobbe et al., 2021; Nakano et al., 2022). If the verifier can score partial generations (sometimes called process reward), the space for inference-time algorithms gets much richer: e.g., the final answer can be generated incrementally, using the verifier to guide the process (e.g., by incremental (blockwise) best-of-N, or more complicated strategies like Monte-Carlo-Tree-Search (Browne et al., 2012; Hao et al., 2023)). Importantly, though a flurry of recent papers consider "scaling laws" of natural strategies, the algorithm design space of verifier-aided inferencetime algorithms is still opaque. In particular, the value of a verifier--and the relationship it needs to have to the generator is not well understood. In this paper, we show that a good verifier can substantially (both in theory and in practice) decrease the computational cost of natural generation tasks, using a pre-trained language model as an oracle. In particular, we show that: Even simple constrained generation tasks--where we are trying to generate a string in the support of a language oracle, subject to some structural constraint (e.g.