技術要約：コスト校正されたフロンティア・ユーティリティによる予算を考慮したLLMディスカバリー

問題定式化

大規模言語モデル（LLM）は、推論時の探索を通じて、候補となる解を生成、評価、洗練させるプロセスを逐次的に行うことで、科学的およびアルゴリズム的な発見にますます採用されている。数学的最適化、アルゴリズム設計、実行可能プログラムの発見といった領域では、決定論的な評価器が再現可能な品質信号を提供する。しかし、既存の適応型ディスカバリー・コントローラーは、通常、スコアの進展のみに基づいて探索アクションにクレジット（功績）を割り当てており、アクションに伴うコストの不均一性を無視している。

トークンベースのAPI価格設定の下では、異なる探索アクションは極めて異なるコストを発生させる。短い洗練（refinement）は1回の参照生成分しかコストがかからない一方で、長いコンテキストを用いたガイダンス呼び出しや、無効なコードの再試行は、6倍以上のコストがかかる場合がある。コントローラーが、同じスコア向上をもたらしたとしても、高コストのアクションと低コストのアクションに対して等しくクレジットを与える場合、残りの予算の機会費用を考慮できていないことになる。本論文は、これを、実行可能な候補の離散空間における集団レベルの割り当て問題として定式化しており、実効的な探索ホライゾン（期間）は、固定された反復回数ではなく、累積された実現トークン予算によって定義される。

著者らは、（命題1において）アクションのコストが不均一なインスタンスでは、「コスト盲目的」なコントローラー（スコア履歴には依存するが実現コストには依存しないもの）は、探索フロンティアの数とコストの格差が増大するにつれて、最適な予算内目的関数の極めてわずかな割合しか達成できないことを証明している。

手法：CostAda

このギャップに対処するため、著者らは、明示的な探索側のトークン予算下でのLLMディスカバリー向けに設計された、コスト校正型の適応型コントローラーであるCostAdaを導入する。CostAdaは、進展のみに基づくクレジットを、**コスト校正されたフロンティア・ユーティリティ（cost-calibrated frontier utility）**に置き換える。これは、ローカルなフロンティアの進展、グローバルなベスト・ソー・ファー（暫定最高値）の改善、実現されたアクションコスト、および残りの予算を統合するものである。

コアとなるメカニズムは、以下の3つの結合された制御を通じて動作する：

1. コスト校正されたフロンティア・ユーティリティ:
   反復 $t$ におけるフロンティア $k$ のユーティリティ $u_t^{(k)}$ は以下のように定義される：
   $$u_t^{(k)} = \frac{\lambda_t g_t + (1 - \lambda_t) \delta_t^{(k)}}{d_t}$$
   ここで：

   • $g_t$ はグローバル・ゲイン（グローバル・ベスト・ソー・ファーに対する改善）である。
   • $\delta_t^{(k)}$ はローカル・ゲイン（フロンティアのローカル・アーカイブに対する改善）である。
   • $\lambda_t = 1 - \rho_t$ はグローバル重みであり、残りの予算比率 $\rho_t$ に条件付けられている。予算が減少するにつれ、コントローラーはローカルな発展からグローバルな改善へと焦点をシフトさせる。
   • $d_t = 1 + \lambda_t^c \phi_t$ は、正規化された実現ステップコストに基づくコスト除数である。これにより、高価なアクションから得られた同等の利得に対して、安価なものよりも少ないクレジットが与えられるようになる。

2. 予算を考慮した制御決定:

   • ローカル探索強度: フロンティア周辺のサンプリング幅は、平滑化されたユーティリティに基づいて調整される。高いユーティリティは低強度の洗練をもたらし、低いユーティリティはより広範な探索を誘発する。決定的なのは、残りの予算比率 $\rho_t$ が、予算が枯渇に近づくにつれて高価な探索を抑制することである。
   • フロンティア割り当て: コントローラーは、実現コストあたりのグローバル・ゲイン（$r_t^{(k)} = g_t / d_t$）に基づいて、将来の予算をフロンティアに割り当てる。弱いローカル・アーカイブに対してのみ改善を示すフロンティアには、割り当てクレジットは与えられない。上限信頼境界（UCB）ルールが、高パフォーマンスなフロンティアの活用（exploitation）と、サンプリングが不十分なものの探索（exploration）のバランスを取り、これらは残りの予算によって制限される。
   • 予算化されたタクティクス介入: 高次のガイダンス（例：「ガイド」または「タクティクス」呼び出し）は、特定の証拠述語が満たされた場合にのみ購入される：(1) 残りの予算が、ガイドとその後のテスト用のリザーブの両方を賄えること、(2) グローバルな進展の持続的な欠如（停滞）または蓄積された低収益の支出があること、(3) 集約ウィンドウ（consolidation window）がアクティブでないこと。これにより、厳密に必要でない限り、ホライゾン付近での高価な介入を防ぐ。

主な貢献

1. 問題の定式化と理論的境界: 本論文は、明示的な探索側のトークン予算の下でのLLMディスカバリーを定式化し、コストが不均一な設定において、コスト盲目的なクレジット戦略が予算内目的関数を損なうことを証明した。
2. コスト校正されたフロンティア・ユーティリティ: 著者らは、進展を実現されたアクションコストと残りの予算に条件付けるクレジット原理を導入し、各アクションの機会費用を明示的にしている。
3. CostAda コントローラー: 予算制限付きのローカル探索、コストを考慮したフロンティア割り当て、および予算化されたタクティクス介入を調整する、この原理の実装である。
4. 実証的検証: 8つのベンチマーク（幾何学的パッキング、極限幾何学、加法的組合せ論、および実行可能プログラムの最適化を網羅）において、2つのバックボーンモデル（GLM-5 および GPT-5.4）を用いて、CostAdaが最先端のベースラインと比較して優れた予算効率と最終的な解の品質を実現することを実証した。

実験結果

著者らは、8つのベンチマーク（幾何学的パッキング、極限幾何学、加法的組合せ論、および実行可能プログラムの最適化を網羅）において、2つのバックボーンモデル（GLM-5 および GPT-5.4）を用い、CostAdaを AdaEvolve（進展を考慮したベースライン）および EvoX（戦略進化コントローラー）と比較評価した。

• 効率性: 16組のベンチマーク–バックボーン・ペアのうち12組において、CostAdaは最強のベースラインが全予算で到達する品質に、最大でも半分の予算で到達した。
• 最終的な品質: 両方のバックボーンにおいて、CostAdaは8つのベンチマークすべてで最強の平均最終品質を達成した。
• 予算パス: 予算の4分の1の時点で、CostAdaの平均正規化スコアは、最強のベースラインの全予算平均を超えている。また、16組のベンチマーク–バックボーン・ペアのうち15組で最高の正規化AUC（曲線下の面積）を達成した。
• 安定性: CostAdaは、特にGLM-5における Circle Packing Rect のようなベンチマークにおいて、ベースラインと比較して結果の分散が低いことを示した。

意義と主張

本論文は、CostAdaがLLM駆動のディスカバリーにおけるリソース管理の方法を根本的に変えるものであると主張している。実現されたコストと残りの予算を、事後的な会計変数や単純な停止ルールとしてではなく、能動的な制御入力として扱うことで、CostAdaは探索戦略をトークンベースの価格設定という経済的現実に適合させている。

著者らは、彼らの手法が最終的な解の品質を維持しながら、予算効率を大幅に向上させると断言している。結果は、コストの不均一性を無視することが、単に進展信号を平滑化するだけでは回復できない最適ではないリソース割り当てを招くため、コスト校正がLLMディスカバリーのスケーリングにおいて不可欠であることを示唆している。この研究は、アクションの「コスト」が、それが生み出す「利得」と同様に変動する場合でも、コントローラーが探索と活用のトレードオフを効果的にナビゲートできることを示している。