BFS-POとは？Best-First Searchで推論モデルのoverthinking問題を解消する新手法

• 大規模推論モデルが抱える「overthinking（過剰思考）」問題に対し、Best-First Search探索を活用した新しい強化学習手法BFS-POを提案
• 最大エントロピーのトークンを分岐点としてバックトラッキングし、最短の正解パスを効率的に発見する仕組みを実現
• DAPOに対し平均1.37倍の高速化と精度向上を同時に達成し、AIME'25では8.6%→13.6%と大幅な性能改善を確認

研究の背景

OpenAI o1やDeepSeek-R1に代表される大規模推論モデル（LRM）は、複雑な数学問題や論理的推論タスクで目覚ましい成果を上げています。しかし、これらのモデルには「overthinking（過剰思考）」と呼ばれる深刻な問題が存在します。必要以上に長い推論チェーンを生成してしまい、計算コストが膨れ上がるのです。

この問題は、GRPOやDAPOといった既存の強化学習アルゴリズムでさらに悪化する傾向があります。これらの手法では、質問に対して独立した複数の回答を並列に生成し、その結果で学習を進めます。しかし、正解さえ含まれていれば冗長な出力も「良い回答」として学習されてしまうため、モデルが不必要に長い推論を行う癖がつきやすくなるのです。

推論コストの削減は、LRMの実用化において最も重要な課題の一つでしょう。精度を維持しつつ推論を短縮する方法が強く求められていました。

提案手法：BFS-PO

本論文で提案されるBFS-PO（Best-First Search Policy Optimization）は、探索木を用いた新しい強化学習フレームワークです。従来手法が独立した回答を並列生成するのに対し、BFS-POは推論の途中で「分岐点」を見つけてバックトラッキング（後戻り）し、より短い正解パスを探索するという根本的に異なるアプローチを取ります。

BFS-POの核心は「最大エントロピーノード」に基づくバックトラッキング機構にあります。エントロピー（情報量の不確実性）が最も高いトークンは、モデルが次に何を出力するか最も「迷っている」地点です。つまり、推論の論理的な方向性を決定する重要な分岐点に該当します。BFS-POはこの地点まで戻り、そこから新たな推論パスを生成することで、より効率的な解法を見つけ出します。

具体的な学習プロセスは以下の通りです。

• まず質問に対してG個の初期回答を生成し、正解かつ最短のパスを選択する
• 選ばれたパス中で最もエントロピーが高いトークン（分岐点）を特定する
• その分岐点までの部分パスを条件として、G個の新しい回答を生成する
• このプロセスをK回（通常3回）繰り返し、探索木を構築する

最適化の段階では、「ブランチ・アドバンテージ」と呼ばれる独自の指標を用います。従来手法のようにグローバルな優位性ではなく、各サブツリー内での報酬をバックトラッキングノードの報酬と比較することで、局所的に最適な推論パスを学習させる仕組みです。

実験結果

BFS-POは、LLaMA-3.1-8B-Instruct、Qwen2.5-3B-Instruct、Qwen2.5-7B-Instructの3つのベースモデルを用いて評価されました。ベンチマークには、GSM8K、MATH-500（学習ドメイン内）に加え、AIME'25やMINERVA-MATHなどのドメイン外タスクも含まれています。

GSM8Kでは、Qwen2.5-3Bベースの場合、BFS-POが精度86.2%・平均出力長269トークンを達成しました。DAPOの精度85.6%・290トークンと比較して、精度向上と出力短縮を同時に実現しています。精度効率スコア（AES）も0.15から0.24へと大幅に改善されました。

特に注目すべきは、ドメイン外タスクでの汎化性能です。AIME'25（数学オリンピック級の難問30題を32回評価）では、DAPOの8.6%に対しBFS-POは13.6%と大幅に上回りました。学習データに含まれないタスクでもこれほどの差が出るということは、BFS-POが単なる暗記ではなく、より本質的な推論能力を育んでいることを示唆しています。

MATH-500では、LLaMA-3.1-8Bベースで精度50.6%（398トークン）、Qwen2.5-7Bベースで精度74.2%（463トークン）を記録しました。全体として、DAPOに対し平均1.37倍の高速化を達成しています。Composition-RL: 簡単な問題を組み合わせてLLMの推論力を伸ばす強化学習フレームワークのようなRL手法の研究が進む中、BFS-POは推論効率化という異なる切り口から重要な貢献を果たしているといえるでしょう。

まとめと今後の展望

BFS-POは、大規模推論モデルのoverthinking問題に対する効果的な解決策を提示しました。最大エントロピーノードを活用したバックトラッキングという発想は、人間が問題を解く際に「判断に迷った箇所まで戻って別のアプローチを試す」プロセスに通じるものがあります。

精度向上と推論コスト削減の両立という成果は、LRMの実用化に向けた大きな前進です。特に、API呼び出しごとにトークン数で課金されるサービスにとって、出力長の短縮は直接的なコスト削減につながります。

一方で、本研究の実験は3B〜8Bパラメータの比較的小規模なモデルに限定されています。著者らも認めるように、大規模モデルでのRL学習は計算コストが非常に高く、より大きなモデルでの検証は今後の課題として残されています。また、数学的推論以外のタスク（コード生成や自然言語推論など）への適用可能性も、今後の研究で明らかにされるべきポイントでしょう。

BFS-POが示した「探索木による効率的な推論パス発見」というアプローチは、推論モデルの次世代最適化において重要な方向性を示しています。overthinking問題の解決は、より多くのユーザーが高度な推論AIを手頃なコストで利用できる未来に直結する、実務的にも極めて重要な研究分野です。

論文情報 https://arxiv.org/abs/2602.14917