Adaptive Test-Time Compute Allocation via Learned Heuristics over Categorical Structure

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 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 textscMATH benchmark, our approach achieves higher accuracy than best-of-N, majority voting, and beam search while using 44% fewer verifier calls.