Adaptive Generate-Rank-Verify: Inference-Time Search with Costly Verification
Shaddin Dughmi, Mahdi Haghifam, Yusuf Hakan Kalayci · 2026
Read Adaptive Generate-Rank-Verify: Inference-Time Search with Costly Verification by Shaddin Dughmi, Mahdi Haghifam, Yusuf Hakan Kalayci (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-17609.txt.
Introduction
Dughmi, Haghifam and Kalayci frame pipelines pairing cheap rewards with an expensive verifier as active search: a policy samples options and pays for labels until one passes. For one prompt, generator and reward induce a score distribution. With both known, optimal policy follows from dynamic programming. With both unknown, ADAP raises samples and verifications. Under monotonicity, higher scores pass no less often, so ADAP costs stay near optimum. Lower bounds via a star number show score-label assumptions matter. Experiments on math and programming validate the advantage over fixed baselines.
Catalog record
| CREATOR | Shaddin Dughmi, Mahdi Haghifam, Yusuf Hakan Kalayci |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 95233 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.17609
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Adaptive Generate-Rank-Verify: Inference-Time Search with Costly Verification Thanks: Authors listed in alphabetical order. Shaddin Dughmi, Mahdi Haghifam, Yusuf Hakan Kalayci Abstract Many inference-time language-model pipelines combine a cheap reward signal with an expensive verifier, such as exact answer checking in mathematical reasoning or hidden-test execution in code generation. We formalize this setting using a learning-theoretic lens as generative active search : a cost-sensitive first-positive search problem in which a policy adaptively samples candidates from an unknown distribution, observes cheap scores, and pays for verifier labels until it finds a positive example. For a fixed prompt, the generator and reward model induce two unknown objects: a distribution over reward scores and a score-conditioned success function. When these quantities are known, we characterize the distribution-aware optimal policy using a dynamic programming approach. In the realistic and practical setting where both the score distribution and success function are unknown, we propose ADAP, a shellwise adaptive generate-rank-verify algorithm that progressively increases the number of sampled responses and top-ranked verifications. Under the monotonicity assumption that higher reward scores are no less likely to pass verification, we show that ADAP achieves expected cost within a constant factor of the distribution-aware optimum. We complement this result with learning-theoretic lower bounds, based on a centered star number, showing that structural assumptions on the score–label relationship are necessary. Experiments on mathematical reasoning and competitive programming validate the predicted advantage over both fixed non-adaptive policies and difficulty-adaptive baselines. 1 Introduction State-of-the-art large language models (LLMs) increasingly rely on inference-time search : they generate multiple candidate solutions, use a cheap but noisy reward signal to triage them, and reserve an expensive verifier for the few candidates that may be correct. This paradigm underlies recent progress on difficult reasoning tasks, including competitive programming and mathematical Olympiad exams [ Goo25 , Ope24 ] , where verification may take the form of hidden-test execution, exact answer checking, or proof verification. Because each additional generation, reward score, and verifier call incurs cost —in wall-clock latency, GPU compute, or API spend—these systems face a basic compute-allocation problem at inference time. In a nutshell: given an LLM, a cheap but noisy reward model, and a costly verifier, how should one use reward scores to decide when to keep sampling and when to spend verification calls, in order to find a verified-correct response with minimal total cost? This question has motivated a growing line of work on test-time compute allocation and adaptive inference-time search [ Sne+25 , Dam+25 , Zha+26 , RAK25 , KRD25 , Wan+25a , Qu26 ] . The challenge is not merely that inference-time compute is costly; it is that the right allocation is inherently prompt-dependent. A natural non-adaptive baseline fixes a pair (N_{\text{rew}},N_{\text{ver}}) : generate N_{\text{rew}} candidate responses, rank them by reward score, and verify the top N_{\text{ver}} . However, no single choice of (N_{\text{rew}},N_{\text{ver}}) is appropriate across all prompts. As shown in Fig. 1 , the per-prompt optimal choice varies widely. Easy instances may require only a small candidate pool and one verification call, while hard instances may require orders of magnitude more generation and several verification attempts. Similar prompt-dependent variation in the value of test-time compute has also been observed in recent studies [ Sne+25 , Dam+25 , Zha+26 , RAK25 , HMZ26 ] . Thus, any fixed policy must either overspend on easy prompts or under-search on hard ones. One natural response is to learn a predictor of per-prompt difficulty from historical data and use it to choose the inference-time budget [ Sne+25 , Dam+25 ] . Such approaches can be effective when the deployment prompt distribution is stable and the learned predictor remains well calibrated. However, this assumption can fail under distribution shift: the mix of prompts may change over time, and the relationship between reward scores and verifier acceptance may vary across prompts or domains. In such settings, historical tuning or a single global calibration rule may not transfer reliably. This motivates online, prompt-dependent policies that adapt using only the reward scores and verification outcomes observed on the current prompt. These observations lead to the central question we aim to answer in this paper: Can an online policy use an uncalibrated reward model, adapt to prompt difficulty, and achieve near-optimal cost relative to a distribution-aware policy that knows the score distribution and reward–verifier relationship? We answer this question by formulating generate–rank–verify inference as a cost-sensitive search problem and by developing an adaptive algorithm with provable and empirical guarantees across various cost regimes. Figure 1 : Per-problem optimal non-adaptive choices (\overline{N_{\text{rew}}^{\star}},\overline{N_{\text{ver}}^{\star}}) on LiveCodeBench ( 100 permutations each). For each problem, N_{\text{rew}}^{\star} is the number of generated candidates and N_{\text{ver}}^{\star} is the number of top-ranked candidates verified. Color encodes total cost; faint diagonals are iso-cost contours. The wide spread shows that fixed (N_{\text{rew}},N_{\text{ver}}) policies can over-spend on easy problems and under-spend on hard ones. Figure 2 : The plot shows average cost ratios of two baselines—Difficulty Adaptive Policy ( \textsc{DAP}_{k} ) and SampleAware Policy—relative to Adap . SampleAware retroactively picks the minimum-cost generation count N_{\text{rew}} and verification count N_{\text{ver}} such that verifying the N_{\text{ver}} highest-reward samples among N_{\text{rew}} finds a correct answer. \textsc{DAP}_{k} estimates problem difficulty from the fraction of successful samples, partitions them into k classes optimally, and assigns each the cheapest uniform strategy ensuring 100\% success. 1.1 Contributions We study inference-time generate–rank–verify pipelines, where candidate responses are sampled from a language model, scored by a cheap reward model, and checked by an expensive verifier. Motivated by the compute-allocation question above, we formalize this setting as a cost-sensitive sequential decision problem, which we call active search . Let c_{\text{rew}}>0 denote the cost of generating one candidate response and scoring it with the reward model, and let c_{\text{ver}}>0 denote the cost of one verifier call. For each prompt x , the generator and reward model induce an unknown distribution \mathcal{D}_{x}\in\Delta(\mathbb{R}) over reward scores. The verifier induces an unknown score-conditioned success function h_{x}^{\star}:\mathbb{R}\to[0,1] , where h_{x}^{\star}(r) is the probability that a candidate with reward score r passes verification. A sound policy adaptively generates candidates, observes their reward scores, and chooses which candidates to verify. It pays J=c_{\text{rew}}N_{\rm rew}+c_{\text{ver}}N_{\rm ver}, where N_{\rm rew} is the number of generated-and-scored candidates and N_{\rm ver} is the number of verifier calls, and it may stop only after observing a positive verifier label. This formulation captures the central tension from the introduction: the policy must decide, online and prompt-by-prompt, when to spend cost on more reward-scored samples and when to spend cost on verification. 1. Optimal Distribution-Aware Benchmark. We first study the idealized setting in which the prompt-specific score distribution and reward–verifier relationship are known. This gives the benchmark for online adaptation and clarifies the ideal compute-allocation rule. We show that the optimal policy has a simple threshold form: it verifies a candidate exactly when its probability of passing the verifier is high enough to justify the verification cost ( Theorem 3.2 ). 2. A prompt-dependent online policy: Adap . In practice, the policy does not know \mathcal{D}_{x} or h^{\star}_{x} , and therefore cannot implement the distribution-aware policy directly. We propose Adap , a shellwise online algorithm that searches over dyadic generation and verification scales ( Algorithm 1 ). Adap progressively enlarges the candidate pool and verifies