# Adaptive Generate-Rank-Verify: Inference-Time Search with Costly Verification

arXiv: https://arxiv.org/abs/2605.17609 · HTML: https://mlsanity.com/paper/2605.17609/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning.
- Builds on 28 of its 44 references that are in the map.
- First posted on arXiv 17 May 2026.

## Placed in

- LLM reasoning / [Test-time compute and efficient thinking](https://mlsanity.com/lr/test-time-compute-and-efficient-thinking/)

## Builds on (most cited first, 28 of 28)

- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [Let's Verify Step by Step](https://mlsanity.com/paper/2305.20050/) (2023)
- [Competition-Level Code Generation with AlphaCode](https://mlsanity.com/paper/2203.07814/) (2022)
- [Qwen2.5-Coder Technical Report](https://mlsanity.com/paper/2409.12186/) (2024)
- [Qwen2.5-Math Technical Report: Toward Mathematical Expert Model via Self-Improvement](https://mlsanity.com/paper/2409.12122/) (2024)
- [Math-Shepherd: Verify and Reinforce LLMs Step-by-step without Human Annotations](https://mlsanity.com/paper/2312.08935/) (2023)
- [Generative Verifiers: Reward Modeling as Next-Token Prediction](https://mlsanity.com/paper/2408.15240/) (2024)
- [The Lessons of Developing Process Reward Models in Mathematical Reasoning](https://mlsanity.com/paper/2501.07301/) (2025)
- [CodeT: Code Generation with Generated Tests](https://mlsanity.com/paper/2207.10397/) (2022)
- [Rewarding Progress: Scaling Automated Process Verifiers for LLM Reasoning](https://mlsanity.com/paper/2410.08146/) (2024)
- [LEVER: Learning to Verify Language-to-Code Generation with Execution](https://mlsanity.com/paper/2302.08468/) (2023)
- [Process Reward Models That Think](https://mlsanity.com/paper/2504.16828/) (2025)
- [Is Best-of-N the Best of Them? Coverage, Scaling, and Optimality in Inference-Time Alignment](https://mlsanity.com/paper/2503.21878/) (2025)
- [Learning How Hard to Think: Input-Adaptive Allocation of LM Computation](https://mlsanity.com/paper/2410.04707/) (2024)
- [Minimax Analysis of Active Learning](https://mlsanity.com/paper/1410.0996/) (2014)
- [Dynamic Scaling of Unit Tests for Code Reward Modeling](https://mlsanity.com/paper/2501.01054/) (2025)
- [Taming Imperfect Process Verifiers: A Sampling Perspective on Backtracking](https://mlsanity.com/paper/2510.03149/) (2025)
- [Derailer-Rerailer: Adaptive Verification for Efficient and Reliable Language Model Reasoning](https://mlsanity.com/paper/2408.13940/) (2024)
- [AdaBoN: Adaptive Best-of-N Alignment](https://mlsanity.com/paper/2505.12050/) (2025)
- [Adaptive Test-Time Compute Allocation for Reasoning LLMs via Constrained Policy Optimization](https://mlsanity.com/paper/2604.14853/) (2026)
- [Optimal Bayesian Stopping for Efficient Inference of Consistent LLM Answers](https://mlsanity.com/paper/2602.05395/) (2026)
- [Optimal Stopping vs Best-of-N for Inference Time Optimization](https://mlsanity.com/paper/2510.01394/) (2025)
- [BEACON: Bayesian Optimal Stopping for Efficient LLM Sampling](https://mlsanity.com/paper/2510.15945/) (2025)
- [When to Trust the Cheap Check: Weak and Strong Verification for Reasoning](https://mlsanity.com/paper/2602.17633/) (2026)
- [On Learning Verifiers and Implications to Chain-of-Thought Reasoning](https://mlsanity.com/paper/2505.22650/) (2025)
- [Adaptive Test-Time Compute Allocation via Learned Heuristics over Categorical Structure](https://mlsanity.com/paper/2602.03975/) (2026)
- [Verify to Amplify: Improving Reasoning via Learned Chain-of-Thought Verification](https://mlsanity.com/paper/2603.03538/) (2026)

## Built on by (most cited first, 2 of 2)

- [Best-of-Evidence: Best-of-N Selection under Partial Verification](https://mlsanity.com/paper/2607.20950/) (2026)
- [ROUTEAUDIT: Interaction-Aware Identification for Budgeted Multi-Verifier Routing](https://mlsanity.com/paper/2610.02808/) (2026)

## Abstract (arXiv)

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.