title: Rethinking Optimal Verification Granularity for Compute-Efficient
    Test-Time Scaling
summary: 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.
paper_authors._id: 682e032304c8bebe87d6e2bf
paper_authors.name: Hao Mark Chen
paper_authors._id: 682e032304c8bebe87d6e2c0
paper_authors.name: Guanxi Lu
paper_authors._id: 682e032304c8bebe87d6e2c1
paper_authors.name: Yasuyuki Okoshi
paper_authors._id: 682e032304c8bebe87d6e2c2
paper_authors.name: Zhiwen Mo
paper_authors._id: 682e032304c8bebe87d6e2c3
paper_authors.name: Masato Motomura
paper_authors._id: 682e032304c8bebe87d6e2c4
paper_authors.name: Hongxiang Fan
paper_title: Rethinking Optimal Verification Granularity for Compute-Efficient
    Test-Time Scaling
paper_summary: 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.
paper_ai_summary: Variable Granularity Search improves test-time scaling of large language models by optimizing verification frequency, enhancing performance and compute efficiency.
paper_ai_keywords: 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