アーカイブ / LLM
残りの生成量に応じて解答探索の幅と深さを調整するBG-MCTS
Budget-Guided MCTS
概要
- BG-MCTSは各問題の残りトークン量を使い、新しい解答候補を増やす判断と、既存の候補を伸ばす判断を調整する。
- 著者らの評価では、MATH500レベル5、上限2万トークン、Llama使用時の正解率はBG-MCTSが0.465、通常のMCTSが0.406だった。
- 社内の計算問題への適用には、正解付き問題での比較に加え、途中過程の採点と最終答えの抽出が適切かの確認が要る。
補足：編集した模式図で仕組みを確認する
VISUAL EXPLAINER
図でつかむ、Budget-Guided MCTSの仕組み
- 01数学の問題文
- 02残量で枝を選択
- 03続きを生成・採点
- 04完成解答を選出
原論文の説明をもとにした模式図です。処理の細部は省略しています。
研究の背景
言語モデルに数学問題を解かせる際、途中まで作った解答から複数の続きを生成して探す方法がある。各問題で生成できるトークン、つまり文章を処理する単位の数に上限があると、終盤に新しい候補を作っても答えまで進められない場合がある。
一方、早く探索を止めれば使える生成量が残る。上限が決まっている状況では、別の解き方を探すことと、見つけた候補を完成させることに、生成量をどう配分するかが課題になる。
手法
BG-MCTSは、途中まで生成した解答を木の枝として管理する。MCTSは、枝の選択、続きの生成、評価、評価結果の反映を繰り返す探索法である。BG-MCTSは問題ごとの上限から探索全体で生成済みのトークン数を引き、残量の割合を計算して枝の選択に使う。
例えば数学問題では、序盤に複数の解き方を試し、残量が減ると評価の高い途中答案を深める。新しい枝を作る選択肢も既存の枝と点数で比べる。各枝の途中過程は評価モデルで採点し、探索後は有効な最終答えを含む候補のうち、評価点が最も高いものを返す。
新規性
BG-MCTSは、残りのトークン量を探索の終了判定だけでなく、既存の候補を伸ばすか、新しい候補を作るかの選択にも使う。序盤は複数の方針を調べ、終盤は有望な候補の完成へ探索を寄せる。
既存候補の選択では、残量が減るにつれて探索を促す点数を弱め、深い候補への補正を強める。新しい枝を作る選択肢の点数も残量に応じて下げ、終盤に浅い位置から候補を増やし続けることを抑える。
従来手法との違い
比較の中心は通常のMCTSである。MCTSは途中まで生成した解答を木の枝として管理し、候補の評価と探索を促す点数から次に伸ばす枝を選ぶ。示された通常の選択式には、残りのトークン量が入らない。
著者らは反復サンプリング、逐次改良、AB-MCTS-M、LiteSearchも評価した。生成を区切る単位や停止方法は手法によって異なるため、結果は論文で設定したモデル、採点方法、生成量の条件に沿って比較する必要がある。
実験結果
著者らはLlama-3.1-8B-InstructとQwen2.5-7B-Instructを使い、MATH500のレベル5とAIME24/25を評価した。途中過程の採点にはGenPRM-7Bを使用。各問題の上限は探索全体の出力トークン数で1万、2万、3万とし、表の正解率は3回の試行の平均である。
上限2万で、MATH500レベル5のLlamaの正解率はBG-MCTSが0.465、通常のMCTSが0.406だった。同じ上限のAIME24/25では、Qwenでそれぞれ0.189、0.167だった。著者らの結果は、これらの問題集と実験条件での比較を示している。
応用の可能性
編集上の応用案 · 論文が実証した用途とは区別しています。
編集上の応用案：社内の計算問題で、複数の解法を試して最終解答の候補を作る。入力は問題文と問題ごとの生成トークン上限、出力は完成した解答候補と探索全体の生成量とする。担当者が計算過程を確認して採否を決める。
初期試行では追加学習を前提とせず、評価用に過去の問題文と正解ラベルを用意する。センサー入力は不要。社内問題に合わせて入力形式、途中過程の採点方法、最終答えの抽出規則を定める必要があり、この用途での効果は未検証である。
応用先の候補からNauhに相談できます。
導入時の検証
導入時の検証案 · 対象データでの再評価が必要です。
導入時の検証案：正解ラベル付きの過去の計算問題を少数用意し、同じ言語モデル、途中過程の採点モデル、生成単位で通常のMCTSとBG-MCTSを比べる。複数の上限を設定し、正解率、完成解答が得られた割合、探索全体の出力トークン数を記録する。
初期検証のための追加学習データやセンサー入力は想定しない。問題文の入力形式、最終答えの抽出規則、途中過程の採点方法を社内問題に合わせて確認する。正解ラベルで採点できない問題は、この比較の対象から分ける。
限界と課題
確認できた本文の範囲では、著者の限界節の記述は確認できず、社内の計算業務へ移した性能も報告されていない。掲載された正解率は、指定の言語モデルと報酬モデル、問題集、生成トークン上限で得られた結果である。
編集上の検証事項は、途中過程の採点が社内問題にも通用するか、完成した答えを正しく抽出できるかである。さらに、答えに到達しない問題の扱いと、生成トークン数が実際の運用費用にどう結び付くかを確かめる必要がある。
出典
元のタイトル・要旨を確認する（英語）
Aligning Tree-Search Policies with Fixed Token Budgets in Test-Time Scaling of LLMs
Tree-search decoding is an effective form of test-time scaling for large language models (LLMs), but real-world deployment often imposes a fixed per-query token budget that varies across settings. Existing tree-search policies are largely budget-agnostic, treating the budget merely as a termination condition, thereby risking late-stage over-branching or premature termination. We propose Budget-Guided MCTS (BG-MCTS), a tree-search decoding algorithm that aligns its search policy with the remaining token budget: it starts with broad exploration, then prioritizes refinement and answer completion as the remaining budget decreases while reducing late-stage branching from shallow nodes. BG-MCTS consistently outperforms budget-agnostic tree-search baselines across inference budgets on mathematical reasoning benchmarks and an additional physics reasoning benchmark with open-weight LLMs.
論文本体の取得範囲に基づく解説。AIが作成した未校閲の記事です。性能の数値は著者の評価条件に依存します。応用例と検証計画は編集上の提案です。解説更新：2026-10-01