Adaptive Test-Time Compute Allocation via Learned Heuristics over Categorical Structure
This work addresses the bottleneck of expensive verification in reasoning systems, which is a problem for researchers and practitioners aiming to improve efficiency in large language model applications, though it is incremental as it builds on existing verification methods.
The paper tackles the problem of inefficient verification in test-time computation for large language model reasoning by proposing a state-level selective verification framework that allocates verification effort to the most informative intermediate states. On the MATH benchmark, it achieves higher accuracy than methods like best-of-N while using 44% fewer verifier calls.
Test-time computation has become a primary driver of progress in large language model (LLM) reasoning, but it is increasingly bottlenecked by expensive verification. In many reasoning systems, a large fraction of verifier calls are spent on redundant or unpromising intermediate hypotheses. We study reasoning under a \emph{verification-cost-limited} setting and ask how verification effort should be allocated across intermediate states. We propose a state-level selective verification framework that combines (i) deterministic feasibility gating over a structured move interface, (ii) pre-verification ranking using a hybrid of learned state-distance and residual scoring, and (iii) adaptive allocation of verifier calls based on local uncertainty. Unlike solution-level best-of-$N$ or uniform intermediate verification, our method distributes verification where it is most informative. On the \textsc{MATH} benchmark, our approach achieves higher accuracy than best-of-$N$, majority voting, and beam search while using 44\% fewer verifier calls.