Budgeted verifier-guided generation and best-of-N sampling

For a fixed prompt $q$, take the finite truncated response set $Y_q$, sampling policy ${\pi }_{\theta }(\cdot \mid q)$, verifier $A_q$, and selection score $u_q$ from the generation protocol. Given an integer budget $N\ge 1$, choose exactly one of the following modes. Response draws, verifier and score evaluations, and comparisons of real scores and of the supplied tie order are supplied terminating exact operations with finite per-call costs. Each draw returns a response from the specified policy support with the stipulated independent law; no construction of a random source is asserted.

1. Rejection search. Draw responses one at a time independently from ${\pi }_{\theta }(\cdot \mid q)$. Return the first response $y$ for which $A_q(y)=1$, together with status accepted. If no sampled response is accepted after $N$ draws, return failure and no response. Stop at the first acceptance or after the $N$th draw, whichever occurs first.

2. Best-of-$N$. Draw exactly $N$ responses independently from ${\pi }_{\theta }(\cdot \mid q)$. Return a response with maximal value of $u_q$; if several responses have maximal score, return the ${\prec }_q$-least one. Return status selected. This mode does not use the verifier to select its output and does not declare the selected response correct.

Its output law is the one induced by the specified prompt, finite response set, length budget, truncation marker, policy, verifier or score, and tie order.

Budgeted verifier generation terminates with bounded response and selection calls ↗: proves termination, the output rules, and the finite draw, evaluation and comparison bounds under the supplied-call model.

The finite response set, sampling law, correctness predicate, verifier, selection score, and deterministic tie order.