# Granularity-Regulated Adaptive Computational Efficiency for Optimal Verification in Test-Time Scaling

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

## Key facts

- Cited by 1 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 21 of its 38 references that are in the map.
- First posted on arXiv 28 Apr 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, 21 of 21)

- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Let's Verify Step by Step](https://mlsanity.com/paper/2305.20050/) (2023)
- [Large Language Models Cannot Self-Correct Reasoning Yet](https://mlsanity.com/paper/2310.01798/) (2023)
- [Is Best-of-N the Best of Them? Coverage, Scaling, and Optimality in Inference-Time Alignment](https://mlsanity.com/paper/2503.21878/) (2025)
- [Multi-Agent Verification: Scaling Test-Time Compute with Multiple Verifiers](https://mlsanity.com/paper/2502.20379/) (2025)
- [Sleep-time Compute: Beyond Inference Scaling at Test-time](https://mlsanity.com/paper/2504.13171/) (2025)
- [MM-Verify: Enhancing Multimodal Reasoning with Chain-of-Thought Verification](https://mlsanity.com/paper/2502.13383/) (2025)
- [Dynamic Scaling of Unit Tests for Code Reward Modeling](https://mlsanity.com/paper/2501.01054/) (2025)
- [MM-PRM: Enhancing Multimodal Mathematical Reasoning with Scalable Step-Level Supervision](https://mlsanity.com/paper/2505.13427/) (2025)
- [Soft Best-of-n Sampling for Model Alignment](https://mlsanity.com/paper/2505.03156/) (2025)
- [AURORA:Automated Training Framework of Universal Process Reward Models via Ensemble Prompting and Reverse Verification](https://mlsanity.com/paper/2502.11520/) (2025)
- [Uncertainty-Aware Step-wise Verification with Generative Reward Models](https://mlsanity.com/paper/2502.11250/) (2025)
- [Thinking Slow, Fast: Scaling Inference Compute with Distilled Reasoners](https://mlsanity.com/paper/2502.20339/) (2025)
- [Hard2Verify: A Step-Level Verification Benchmark for Open-Ended Frontier Math](https://mlsanity.com/paper/2510.13744/) (2025)
- [When Does Verification Pay Off? A Closer Look at LLMs as Solution Verifiers](https://mlsanity.com/paper/2512.02304/) (2025)
- [Linking Process to Outcome: Conditional Reward Modeling for LLM Reasoning](https://mlsanity.com/paper/2509.26578/) (2025)
- [T1: Tool-integrated Verification for Test-time Compute Scaling in Small Language Models](https://mlsanity.com/paper/2504.04718/) (2025)
- [Rethinking Optimal Verification Granularity for Compute-Efficient Test-Time Scaling](https://mlsanity.com/paper/2505.11730/) (2025)
- [A Theory of Inference Compute Scaling: Reasoning through Directed Stochastic Skill Search](https://mlsanity.com/paper/2507.00004/) (2025)
- [Re-FORC: Adaptive Reward Prediction for Efficient Chain-of-Thought Reasoning](https://mlsanity.com/paper/2511.02130/) (2025)
- [What If We Allocate Test-Time Compute Adaptively?](https://mlsanity.com/paper/2602.01070/) (2026)

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

- [More Rejective, Not More Discriminative: The Unit of Verification in Pre-Execution LLM Oversight](https://mlsanity.com/paper/2608.23941/) (2026)

## Abstract (arXiv)

Test-time scaling (TTS) has emerged as a powerful paradigm for improving the reasoning performance of large language models (LLMs) by investing additional compute at inference time. A central component of TTS is the verifier, which selects or scores candidate solutions to guide the search process. While prior work has explored the benefit of verification, a fundamental question remains underexplored: what is the optimal granularity of verification under a given compute budget? Coarse-grained outcome reward models (ORMs) and fine-grained process reward models (PRMs) represent two extremes, yet neither alone achieves compute-optimality across all regimes. In this paper, we establish a unified theoretical framework, called GRACE (underlineGranularity-underlineRegulated underlineAdaptive underlineComputational underlineEfficiency), that characterizes the optimal verification granularity as an explicit function of problem difficulty, verifier accuracy, and compute budget. We prove that there exists a phase transition: fine-grained verification dominates when either the compute budget is large or the problem is hard, whereas coarse-grained verification is preferred in the low-budget, easy-problem regime. Our theory unifies Best-of-N, beam search, and step-level MCTS within a single Pareto-optimality framework, and motivates an adaptive granularity strategy that provably achieves the compute-performance Pareto frontier. Empirical results on MATH-500, GSM8K, and AIME benchmarks corroborate all four theoretical claims, with our adaptive strategy outperforming fixed-granularity baselines by up to 3.1% accuracy at matched compute.