# Rethinking Optimal Verification Granularity for Compute-Efficient Test-Time Scaling arXiv: https://arxiv.org/abs/2505.11730 ยท HTML: https://mlsanity.com/paper/2505.11730/ ## 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 30 of its 44 references that are in the map. - First posted on arXiv 16 May 2025. ## 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, 30 of 30) - [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023) - [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024) - [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021) - [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025) - [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) - [Qwen2.5 Technical Report](https://mlsanity.com/paper/2412.15115/) (2024) - [Training Compute-Optimal Large Language Models](https://mlsanity.com/paper/2203.15556/) (2022) - [Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters](https://mlsanity.com/paper/2408.03314/) (2024) - [s1: Simple test-time scaling](https://mlsanity.com/paper/2501.19393/) (2025) - [Large Language Monkeys: Scaling Inference Compute with Repeated Sampling](https://mlsanity.com/paper/2407.21787/) (2024) - [L1: Controlling How Long A Reasoning Model Thinks With Reinforcement Learning](https://mlsanity.com/paper/2503.04697/) (2025) - [Demystifying Long Chain-of-Thought Reasoning in LLMs](https://mlsanity.com/paper/2502.03373/) (2025) - [From System 1 to System 2: A Survey of Reasoning Large Language Models](https://mlsanity.com/paper/2502.17419/) (2025) - [Alphazero-like Tree-Search can Guide Large Language Model Decoding and Training](https://mlsanity.com/paper/2309.17179/) (2023) - [Rewarding Progress: Scaling Automated Process Verifiers for LLM Reasoning](https://mlsanity.com/paper/2410.08146/) (2024) - [Training Language Models to Reason Efficiently](https://mlsanity.com/paper/2502.04463/) (2025) - [ReFT: Reasoning with Reinforced Fine-Tuning](https://mlsanity.com/paper/2401.08967/) (2024) - [A Survey on Test-Time Scaling in Large Language Models: What, How, Where, and How Well?](https://mlsanity.com/paper/2503.24235/) (2025) - [Will we run out of data? Limits of LLM scaling based on human-generated data](https://mlsanity.com/paper/2211.04325/) (2022) - [Can 1B LLM Surpass 405B LLM? Rethinking Compute-Optimal Test-Time Scaling](https://mlsanity.com/paper/2502.06703/) (2025) - [GenPRM: Scaling Test-Time Compute of Process Reward Models via Generative Reasoning](https://mlsanity.com/paper/2504.00891/) (2025) - [OpenR: An Open Source Framework for Advanced Reasoning with Large Language Models](https://mlsanity.com/paper/2410.09671/) (2024) - [Inference-Aware Fine-Tuning for Best-of-N Sampling in Large Language Models](https://mlsanity.com/paper/2412.15287/) (2024) - [Multi-Agent Verification: Scaling Test-Time Compute with Multiple Verifiers](https://mlsanity.com/paper/2502.20379/) (2025) - [When To Solve, When To Verify: Compute-Optimal Problem Solving and Generative Verification for LLM Reasoning](https://mlsanity.com/paper/2504.01005/) (2025) - [Heimdall: test-time scaling on the generative verification](https://mlsanity.com/paper/2504.10337/) (2025) - [Do We Truly Need So Many Samples? Multi-LLM Repeated Sampling Efficiently Scales Test-Time Compute](https://mlsanity.com/paper/2504.00762/) (2025) - [Towards Hierarchical Multi-Step Reward Models for Enhanced Reasoning in Large Language Models](https://mlsanity.com/paper/2503.13551/) (2025) - [Toward Adaptive Reasoning in Large Language Models with Thought Rollback](https://mlsanity.com/paper/2412.19707/) (2024) ## Built on by (most cited first, 5 of 5) - [FastTTS: Accelerating Test-Time Scaling for Edge LLM Reasoning](https://mlsanity.com/paper/2509.00195/) (2025) - [S3: Stratified Scaling Search for Test-Time in Diffusion Language Models](https://mlsanity.com/paper/2604.06260/) (2026) - [Granularity-Regulated Adaptive Computational Efficiency for Optimal Verification in Test-Time Scaling](https://mlsanity.com/paper/2606.19354/) (2026) - [More Rejective, Not More Discriminative: The Unit of Verification in Pre-Execution LLM Oversight](https://mlsanity.com/paper/2608.23941/) (2026) - [Enhancing Trustworthiness with Mixed Precision: Benchmarks, Opportunities, and Challenges](https://mlsanity.com/paper/2511.22483/) (2025) ## Abstract (arXiv) Test-time scaling (TTS) has proven effective in enhancing the reasoning capabilities of large language models (LLMs). Verification plays a key role in TTS, simultaneously influencing (1) reasoning performance and (2) compute efficiency, due to the quality and computational cost of verification. In this work, we challenge the conventional paradigms of verification, and make the first attempt toward systematically investigating the impact of verification granularity-that is, how frequently the verifier is invoked during generation, beyond verifying only the final output or individual generation steps. To this end, we introduce Variable Granularity Search (VG-Search), a unified algorithm that generalizes beam search and Best-of-N sampling via a tunable granularity parameter g. Extensive experiments with VG-Search under varying compute budgets, generator-verifier configurations, and task attributes reveal that dynamically selecting g can improve the compute efficiency and scaling behavior. Building on these findings, we propose adaptive VG-Search strategies that achieve accuracy gains of up to 3.1% over Beam Search and 3.6% over Best-of-N, while reducing FLOPs by over 52%. We will open-source the code to support future research.