Granularity-Regulated Adaptive Computational Efficiency for Optimal Verification in Test-Time Scaling
Quick Answer
This paper shows that The GRACE framework optimizes verification granularity in test-time scaling for large language models, demonstrating that fine-grained verification excels under high compute budgets or difficult problems, while coarse-grained is better for low budgets and easier tasks.
Quick Take
Empirical results show a 3.1% accuracy improvement over fixed strategies on benchmarks like MATH-500 and GSM8K.
Key Points
- GRACE framework defines optimal verification granularity based on problem difficulty and compute budget.
- Fine-grained verification is preferred for high-complexity tasks with sufficient compute resources.
- Coarse-grained verification is more effective for low-budget, simpler problems.
- Empirical tests on MATH-500, GSM8K, and AIME validate theoretical claims.
- Adaptive strategies outperform fixed-granularity approaches by up to 3.1% in accuracy.
Paper Resources
📖 Reader Mode
~2 min readAbstract: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 \emph{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: \emph{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 \textbf{GRACE} (\underline{G}ranularity-\underline{R}egulated \underline{A}daptive \underline{C}omputational \underline{E}fficiency), 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.
| Subjects: | Computation and Language (cs.CL); Machine Learning (cs.LG) |
| Cite as: | arXiv:2606.19354 [cs.CL] |
| (or arXiv:2606.19354v1 [cs.CL] for this version) | |
| https://doi.org/10.48550/arXiv.2606.19354 arXiv-issued DOI via DataCite |
Submission history
From: Luan Vejsiu [view email]
[v1]
Tue, 28 Apr 2026 18:19:16 UTC (156 KB)
— Originally published at arxiv.org
Want this in your inbox every morning?
Daily brief at your local 8am — bilingual EN/中文, free.
More from arXiv cs.CL
See more →TriAgent: Divergence-Aware Committees for Cost-Efficient Financial Sentiment Analysis
TriAgent introduces a cost-efficient multi-agent system for financial sentiment analysis, combining VADER, FinBERT, and Qwen2.5. It achieves an F1 score of ~0.87 with significant savings of $9.3M/year at a 10M-user scale compared to GPT-4o-mini, while also detecting hallucinations with an AUC of 0.90.