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

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

## Key facts

- Cited by 5 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 17 of its 21 references that are in the map.
- First posted on arXiv 3 Feb 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, 17 of 17)

- [Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks](https://mlsanity.com/paper/2005.11401/) (2020)
- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Judging LLM-as-a-Judge with MT-Bench and Chatbot Arena](https://mlsanity.com/paper/2306.05685/) (2023)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Measuring Mathematical Problem Solving With the MATH Dataset](https://mlsanity.com/paper/2103.03874/) (2021)
- [Toolformer: Language Models Can Teach Themselves to Use Tools](https://mlsanity.com/paper/2302.04761/) (2023)
- [Let's Verify Step by Step](https://mlsanity.com/paper/2305.20050/) (2023)
- [Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters](https://mlsanity.com/paper/2408.03314/) (2024)
- [Solving Quantitative Reasoning Problems with Language Models](https://mlsanity.com/paper/2206.14858/) (2022)
- [Improving language models by retrieving from trillions of tokens](https://mlsanity.com/paper/2112.04426/) (2021)
- [Program of Thoughts Prompting: Disentangling Computation from Reasoning for Numerical Reasoning Tasks](https://mlsanity.com/paper/2211.12588/) (2022)
- [Math-Shepherd: Verify and Reinforce LLMs Step-by-step without Human Annotations](https://mlsanity.com/paper/2312.08935/) (2023)
- [Lexically Constrained Decoding for Sequence Generation Using Grid Beam Search](https://mlsanity.com/paper/1704.07138/) (2017)
- [Fast Lexically Constrained Decoding with Dynamic Beam Allocation for Neural Machine Translation](https://mlsanity.com/paper/1804.06609/) (2018)
- [Atom of Thoughts for Markov LLM Test-Time Scaling](https://mlsanity.com/paper/2502.12018/) (2025)
- [When is Tree Search Useful for LLM Planning? It Depends on the Discriminator](https://mlsanity.com/paper/2402.10890/) (2024)
- [Teaching LLMs to Ask: Self-Querying Category-Theoretic Planning for Under-Specified Reasoning](https://mlsanity.com/paper/2601.20014/) (2026)

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

- [Walking Through Uncertainty: An Empirical Study of Uncertainty Estimation for Audio-Aware Large Language Models](https://mlsanity.com/paper/2604.25591/) (2026)
- [Not All Errors Are Equal: Consequence-Aware Reasoning Compute Allocation](https://mlsanity.com/paper/2606.04402/) (2026)
- [Adaptive Generate-Rank-Verify: Inference-Time Search with Costly Verification](https://mlsanity.com/paper/2605.17609/) (2026)
- [Think Again or Think Longer? Selective Verification for Budget-Aware Reasoning](https://mlsanity.com/paper/2606.19808/) (2026)
- [CoVeR: Coverage-Based Routing of Verifier Calls in Agentic Retrieval](https://mlsanity.com/paper/2609.26086/) (2026)

## Abstract (arXiv)

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.