Rethinking Optimal Verification Granularity for Compute-Efficient
  Test-Time Scaling
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.
682e032304c8bebe87d6e2bf
Hao Mark Chen
682e032304c8bebe87d6e2c0
Guanxi Lu
682e032304c8bebe87d6e2c1
Yasuyuki Okoshi
682e032304c8bebe87d6e2c2
Zhiwen Mo
682e032304c8bebe87d6e2c3
Masato Motomura
682e032304c8bebe87d6e2c4
Hongxiang Fan
Rethinking Optimal Verification Granularity for Compute-Efficient
  Test-Time Scaling
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.
Variable Granularity Search improves test-time scaling of large language models by optimizing verification frequency, enhancing performance and compute efficiency.
test-time scaling (TTS) large language models (LLMs) verification reasoning performance compute efficiency generator-verifier configurations Variable Granularity Search (VG-Search) beam search Best-of-N sampling adaptive VG-Search strategies FLOPs