論文の概要: Provable Test-Time Scaling for Beam Search in LLM Reasoning

• arxiv url: http://arxiv.org/abs/2609.38672v1
• Date: Tue, 29 Sep 2026 23:56:06 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-01 18:57:26.854378
• Title: Provable Test-Time Scaling for Beam Search in LLM Reasoning
• Title（参考訳）: LLM推論におけるビーム探索のための確率的テスト時間スケーリング
• Abstract要約: 一般的に使用されているビームサーチフレームワークの試験時間計算保証について検討する。 CF-Beamの後悔は稀な故障発生の確率によって上界にあることを示す。 本結果は,シーケンスレベルの推論法よりもビームサーチの基本的な利点を浮き彫りにしている。
• 参考スコア（独自算出の注目度）: 62.83768341138575
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Beam-search-based test-time methods provide an effective way to improve large language model (LLM) performance on long-horizon generation by pruning invalid reasoning paths early, leading to significantly improved reasoning efficiency and more favorable test-time cost scaling. Despite strong empirical success, the theoretical understanding of beam search remains limited. In this paper, we study the test-time compute guarantee of the commonly used beam search framework that uses the model's internal log-likelihood for intermediate scoring, while relying on an external reward model only after a complete response is generated. We first establish a lower bound for vanilla beam search, showing that at least $Ω(C^\star(x)^2)$ samples are required for the optimal response to survive, where $C^\star(x)$ is the token-level coverage coefficient for prompt $x$. This motivates our modified confidence-filtered beam search (CF-Beam), which reduces the sufficient coverage dependence from quadratic to nearly linear under prefix competitiveness, for fixed horizon, gap, and target accuracy. We then show that the regret of CF-Beam is upper-bounded by the probability of rare failure events and the reward estimation error scaled by a path-level coverage coefficient, where the rare-failure term vanishes as per-step sampling increases. Our results highlight a fundamental advantage of beam search over sequence-level inference methods such as Best-of-N and Best-of-Majority. While the guarantees of these approaches typically involve coverage coefficients that grow exponentially with the horizon $L$, CF-Beam controls the dominant search-induced term through a token-level coverage coefficient that scales polynomially with $L$. Our numerical experiments further confirm that beam search is more robust on hard instances and under increasing reasoning horizons.
• Abstract（参考訳）: ビームサーチに基づくテストタイム法は,不確定な推論経路を早期にプルーニングすることで,大規模言語モデル(LLM)の性能向上に有効な方法を提供する。 経験的成功にもかかわらず、ビーム探索の理論的理解は依然として限られている。 本稿では,完全応答発生後のみ外部報酬モデルに頼りながら,モデルの内部ログを中間スコアリングに使用する一般的なビームサーチフレームワークの試験時間計算保証について検討する。 まず、バニラビームサーチの下位境界を定め、少なくとも$Ω(C^\star(x)^2)$サンプルは生存のための最適応答に必要であり、$C^\star(x)$は$x$をプロンプトするためのトークンレベルカバレッジ係数であることを示す。 これは修正された信頼度フィルタビームサーチ(CF-Beam)を動機付け、固定地平線、ギャップ、目標精度に対して2次からほぼ線形に十分なカバレッジ依存性を減少させる。 そこで, CF-Beam の後悔は, 異常事象の発生確率と, 経路レベルカバレッジ係数でスケールした報酬推定誤差によって上界し, ステップごとのサンプリングで希少な障害項が消滅することを示す。 この結果は,Best-of-NやBest-of-Majorityといったシーケンスレベルの推論手法よりもビームサーチの基本的な利点を強調した。 これらの手法の保証は通常、水平線$L$で指数関数的に増加するカバレッジ係数を含むが、CF-Beamは、$L$で多項式的にスケールするトークンレベルのカバレッジ係数によって、支配的な検索誘起項を制御する。 我々の数値実験により、ビームサーチはハードインスタンス上でより堅牢であり、推論の地平線が増大していることが確認される。

関連論文リスト

• Theoretical Limits of Language Model Alignment [9.45142272392467]
  言語モデル(LM)アライメントは、ベースモデルの能力を保ちながら、人間の好みを反映するモデル出力を改善する。 最も一般的なアライメントアプローチは、(i)強化学習であり、KL分割制約の下で期待される報酬を最大化する。 固定KL分割予算に対する最大期待報酬利得を導出することにより、KL正規化アライメントの情報理論的限界を特徴づける。
  論文  参考訳（メタデータ） (2026-05-08T01:32:22Z)
• $\nabla$-Reasoner: LLM Reasoning via Test-Time Gradient Descent in Latent Space [71.23672814629448]
  $nabla$-Reasonerは、トークンログに対する差別化可能な最適化をデコードループに統合する反復生成フレームワークである。 $nabla$-Reasonerは、挑戦的な数学的推論ベンチマークで20%以上の精度の向上を実現している。
  論文  参考訳（メタデータ） (2026-03-05T08:42:54Z)
• BEAR: Towards Beam-Search-Aware Optimization for Recommendation with Large Language Models [8.738350030995894]
  BEAR(Beam-Search-Aware Regularization)は、トレーニング中のビーム探索動作を明示的に考慮した、新しい微調整目標である。 4つの実世界のデータセットにわたる実験において、強力なベースラインを著しく上回る。
  論文  参考訳（メタデータ） (2026-01-30T12:45:02Z)
• $\texttt{SPECS}$: Faster Test-Time Scaling through Speculative Drafts [55.231201692232894]
  $textttSPECS$は、投機的デコードにインスパイアされた遅延対応のテスト時間スケーリングメソッドである。 我々の結果は、$textttSPECS$matchはビームサーチの精度を上回り、最大$sim$19.1%のレイテンシを削減していることを示している。
  論文  参考訳（メタデータ） (2025-06-15T05:50:05Z)
• Supervised Optimism Correction: Be Confident When LLMs Are Sure [91.7459076316849]
  教師付き微調整とオフライン強化学習の間には,新たな理論的関係が確立されている。 広く使われているビームサーチ法は、許容できない過度な最適化に悩まされていることを示す。 本稿では,トークンレベル$Q$-value推定のための簡易かつ効果的な補助的損失を導入したSupervised Optimism Correctionを提案する。
  論文  参考訳（メタデータ） (2025-04-10T07:50:03Z)
• Self-Evaluation Guided Beam Search for Reasoning [61.523627290397556]
  我々は,Large Language Model (LLM) の推論プロセスのガイドと校正を行うための段階的自己評価機構を導入する。 本稿では,ビームサーチによる自己評価ガイダンスを統合した復号アルゴリズムを提案する。 我々のアプローチは、GSM8K、AQuA、StrategyQAにおいて、対応するCodexバックボンドベースラインをわずかに精度6.34%、9.56%、および5.46%で上回る。
  論文  参考訳（メタデータ） (2023-05-01T02:37:59Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。