Rethinking Optimal Verification Granularity for Compute-Efficient
  Test-Time Scaling
Authors: name: Hao Mark Chen; name: Guanxi Lu; name: Yasuyuki Okoshi; name: Zhiwen Mo; name: Masato Motomura; name: Hongxiang Fan
Published: 2025-05-16 22:24:48

Abstract: 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.