大規模言語モデルの探索型デコーディングは解答の精度を高めることができるが、現実には投入可能な計算予算が限られていることがある。既存手法は予算を探索方策に組み込まないため、固定予算での打ち切りと探索の優先度付けが噛み合わず、与えられた予算下での性能を最大化できない。本研究では、残予算に応じて探索の幅と深さを動的に制御し、所与の予算内で解答の精度を最大化する探索型デコーディング手法Budget-GuidedMCTSを提案する。数学推論タスク(MATH500/AIME)において、提案手法は予算制約下での解答の精度を向上させた。

大規模言語モデル(LLM)では、複数の生成を比較・統合することで解答品質を改善できる。最も素朴な反復サンプリングでは、複数の解答候補を多数決や評価器で選別する[1]。探索型デコーディングではMonteCarloTreeSearch(MCTS)等で生成経路や解を探索的に洗練する[2,3,4,5,6,7,8,9,10,11]。本研究では、実運用において各問題に投入できる計算予算（例：消費トークン数や計算時間）が限られている状況を考える。既存の探索型デコーディングの多くは、探索の反復回数・分岐数・幅・深さといった探索量に基づいて探索を進め、残予算を探索中の意思決定に組み込まない。そのため、予算枯渇による探索停止と探索方針が整合せず、固定予算下で性能を最大化しにくい。探索の早期打ち切りによりコスト削減を図る手法もあるが[12]、所与の予算に条件づけた探索資源の配分最適化は行わない。本研究では、所与の予算制約下で解答品質を最大化する探索型デコーディング手法Budget-GuidedMCTS(BG-MCTS)を提案する。BG-MCTSでは残予算に応じて探索幅と深さを適応的に制御する。こBudgetLeftRoot0%25%50%75%100%S10.730.200.94Gen0.750.54ExpandExpand0.840.230.13GenGenShallownodeischosen0.870.43Gen0%25%50%75%100%BudgetLeftRootS10.730.200.94GenS20.750.540.840.230.13GenGenS30.870.43GenDeepnodeischosenExpandExpand（上部）予算が潤沢に残っている際は浅い位置のノードを優先して選択を行い、（下部）予算が枯渇している際は深い位置のノードを優先して選択する。れにより、予算が潤沢な局面では探索を促し、枯渇が近い局面では解への到達を優先させる。なお、LLMの出力トークン数を予算の単位とする。10B規模のLLM(Llama-3.1-8B-Instruct[13]、Qwen-