💻 computer science

Compute Allocation in Evolutionary Search: From Depth-Breadth to Multi-Armed Bandits

本論文は、LLM 誘導型進化探索の実証的規則性を分析し、基盤モデルやプロンプトを変更することなく、並列軌道間で計算リソースを動的に割り当てるマルチアームバンディットアルゴリズムである BaSE を提案するものであり、従来の深さ・広さ戦略と比較して平均適合度を 12.3% 向上させ、信頼性を高めることを可能にする。

原著者： Sixue Xing, Haoyu He, Kerui Wu, Zhuo Yang, Haozheng Luo, Tianfan Fu, Aarthy Nagarajan

公開日 2026-05-29

📖 1 分で読めます☕ さくっと読める

CC BY 4.0

原著者： Sixue Xing, Haoyu He, Kerui Wu, Zhuo Yang, Haozheng Luo, Tianfan Fu, Aarthy Nagarajan

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

あなたが、26 個の円を正方形に完璧にはめ込む、あるいは点の配置を工夫して点同士の距離を最大化するといった、非常に難しいパズルを解こうとしていると想像してください。あなたには（大規模言語モデル、LLM）という超優秀なアシスタントがいて、ピースの配置方法について新しい提案をしてくれます。しかし、アシスタントに提案を求めるために使える「エネルギー」や「予算」は限られています。

この論文は、そのエネルギーを最善の解を得るためにどう使うべきかを明らかにするものです。

課題：「質問」の予算をどう使うか？

過去、研究者たちは AI に限られた予算で質問をする際、主に 2 つの方法を試みました。

「深掘り」（Depth）: AI に 1 つのアイデアを提示し、それを改善させ、さらにその改良版を求め、その 1 つの道筋を長く掘り下げていきます。まるで 1 つの穴を非常に深く掘るようなものです。
「広範囲」（Breadth）: AI に 100 個の異なるランダムなアイデアを一度に生成させ、その中から最良のものを選び、そこで終了します。まるで網を広げて 1 匹だけ魚を上げるようなものです。

これまでの研究の多くは、数百もの異なる組み合わせを試した後に得られた「最良の結果」だけを報告していました。その結果がどの程度信頼できるのか、あるいは固定された予算でそれを一貫して得るにはどうすればよいのかについては、ほとんど語られていませんでした。

発見：それはパズルによる

著者たちは、異なる AI モデルと 3 種類のパズルを用いて数千回の実験を行いました。その結果、2 つの大きな規則が見つかりました。

「能力の天井」: AI が特定のパズルに対して十分に賢くない場合、予算の使い方をどう工夫しても、パズルは解けません。しかし、AI が十分に賢ければ、小さな AI と巨大な AI の違いは、実際の「計算作業量」を測る際にはしばしば消えてしまいます。
「解の形状」:
- パズル A（円のパッキング）: このパズルは、広く平坦な高原のようです。深く掘っても広く広げても、良い解が見つかる可能性が高いです。許容範囲が広いと言えます。
- パズル B（最小最大距離）: このパズルは、鋭い山稜のようです。深く掘ることと広く広げることの間の、正確なバランスを見つける必要があります。深く掘りすぎたり、広げすぎたりすると、頂点を見逃してしまいます。

解決策：BaSE（スマートな交通整理員）

著者たちは、単に「深掘り」か「広範囲」かを選ぶだけでは不十分だと気づきました。なぜなら AI は予測不可能だからです。単一の試行が悪いアイデアに陥り、またある試行では金脈を見つけることもあります。

彼らはBaSE（Bandit-based Self-Evolving：バンドットベースの自己進化）という新しい手法を開発しました。

アナロジー：スロットマシンの戦略
10 台のスロットマシン（それぞれがパズルを解こうとする 10 種類の AI「試行」）があるカジノにいると想像してください。あなたには限られた枚数のコイン（予算）しかありません。

従来の方法: 1 台のマシンを選び、コインがなくなるまでレバーを引き続けます。もしそのマシンが「外れ」なら、すべてを失います。
BaSE の方法: まず 10 台すべてのマシンを 1 回ずつ引き、どのマシンが最も多く払い出しているかを確認します。そして、外れのマシンへのコイン投入を止め、勝っているマシンに残りのコインをすべて注ぎ込みます。

BaSE はスマートな交通整理員のようです。AI の脳やパズルのルールを変えるわけではありません。ただ、どの「経路」が機能しているかを常に監視し、勝者へ予算をシフトさせ、敗者を放棄するだけです。

結果

一貫性の向上: BaSE を使用することで、既存の最良の方法と比較して、解の平均スコアが**12.3%**向上しました。
信頼性: 結果がはるかに信頼できるものになりました。100 回に 1 回という確率で幸運な「ジャックポット」が当たるのではなく、一貫して高スコアを獲得できるようになりました。
魔法はない: より賢い AI モデルや優れたプロンプトを使用したわけではありません。同じ金額をより賢く使っただけです。

結論

AI に難しい問題を解かせるための予算が限られている場合、1 つの道に固執したり、すべてを一度に投げかけたりしてはいけません。複数の試行を同時に監視し、実際に機能しているものへリソースを素早くシフトさせる戦略を用いるべきです。この論文は、計算資源をどう配分するかは、使用する AI モデルと同じくらい重要であることを証明しています。

技術的概要：進化探索における計算資源の割り当て

問題定義

大規模言語モデル（LLM）に導かれた進化探索システム（FunSearch、AlphaEvolve、CodeEvolve など）は、数学的発見や組合せ最適化において最先端の結果を達成している。しかし、既存の文献では、不特定数の実行から得られた単一の最良結果のみが報告される傾向にあり、実行ごとの分布は文書化されていない。さらに、報告される計算コストは桁違いに異なり、固定された予算下での単一実行の信頼性を評価することが困難である。

本稿で扱われる中核的な問題は計算資源の割り当てである：LLM 呼び出しの固定予算 $C$ が与えられたとき、この予算を深さ（単一の軌跡の逐次改善）と広さ（複数の軌跡の並列探索）の間にどのように配分すべきか？現在のシステムでは、これらのハイパーパラメータ（例えば、個体数と世代数）が、割り当てが期待される性能や信頼性にどのように影響するかという体系的な理解なしに固定されることが多い。

手法

1. 深さ - 広さ割り当ての実証的特徴付け

著者らは、3 つの幾何学的最適化タスク（円充填、MinMaxDist、Heilbronn 三角形）と 4 つのモデルサイズ（Qwen3-1.7B から 14B、および Llama-3.1-8B）にわたる体系的な実証研究を実施した。彼らは、予算 $C$ を $N$ 個の並列子孫を持つ $T$ 世代に分割する問題を割り当て問題として定義した（ $C = T \times N$ ）。

適合度 - 計算包絡線: 彼らは、達成可能な適合度と実効的な FLOPs（モデルサイズとキャッシュ効率を考慮したもの）の関係を分析した。その結果、呼び出し回数が等しい場合、より大きなモデルが優位である一方で、モデルとタスクの組み合わせが「能力がある」場合、実効 FLOPs に対して測定すると、その性能順序は大きく崩れることが観察された。
深さ - 広さの規則性: 彼らは適合度ランドスケープにパラメトリックな双線形モデルを適合させた：
$\log(1 - V) = \beta_0 + a \log T + b \log N + c \log T \log N$
ここで、 $V$ $V$ は適合度である。相互作用係数 $c$ $c$ は、最適割り当ての幾何学を決定する：
- コーナー最適解 ( $|c| \approx 0$ ): 円充填のようなタスクは、多くの割り当てが類似した結果をもたらす広い高原を示し、しばしば深さを優先する。
- 内部の尾根 ( $c < 0$ ): MinMaxDist のようなタスクは、最適な性能のために深さと広さのバランスの取れた混合を必要とする、鋭い尾根を示す。
- 能力ゲート: これらの規則性は、特定のタスクに対する能力閾値を越えたモデルに対してのみ成立する。能力の低いモデルは、構造化された深さ - 広さのトレードオフを示さない。

2. BaSE: バンディットベースの自己進化

LLM の変異プロセスにおける確率性により、同一の設定が広範に異なる最終適合度スコアを生み出すという実行結果の大きなばらつきに動機づけられ、著者らはBaSEを提案した。

メカニズム: BaSE は、進化探索を**多腕バンディット（MAB）**問題として扱う。全予算を単一の軌跡（Greedy）または固定された島セット（Island プロトコル）にコミットするのではなく、BaSE は $K$ 個の並列軌跡を維持する。
適応的割り当て: 各ステップで、バンディットアルゴリズム（UCB、EXP3.P、またはトンプソンサンプリング）が、次の LLM 呼び出しでどの軌跡を拡張するかを選択する。これにより、停滞している実行から有望な実行へと計算資源が動的に経路制御される。
直交性: BaSE は、基本モデル、プロンプト、または軌跡内の親サンプリングロジックを変更しない。それは厳密に軌跡間リソース割り当てのレベルで動作する。

主要な結果

1. 実証的規則性

能力の崩壊: 能力のあるモデルの場合、性能包絡線はモデルサイズのみではなく、実効 FLOPs によって決定される。
タスク依存の幾何学: 最適な深さ - 広さの分割は普遍的ではない。それはタスクの「アルゴリズムファミリー」（例えば、scipy のような特定のライブラリが必要か、特定の解析的構成が必要か）に依存する。
確率性: 固定された割り当てであっても、個々の実行は大きく変動する。いくつかの実行は高い適合度に収束するが、他の実行は最適でないアルゴリズムファミリーにロックされることで早期に停滞する。

2. BaSE の性能

平均適合度の改善: 8 つの（モデル、タスク）セルにわたって、BaSE はモデルやプロンプトを変更することなく、最強の島プロトコルベースライン（OpenEvolve、CodeEvolve、ShinkaEvolve など）に対して平均最良適合度を**12.3%**改善した。
信頼性の向上: 最も顕著な向上は、高ばらつき環境で観察された。例えば、Llama-3.1-8B を用いた Heilbronn 三角形タスクにおいて、BaSE 非採用の手法はしばしば有効な解（適合度 $\approx 0$ ）を生成できなかったのに対し、BaSE（トンプソンサンプリング）は平均適合度 0.4387 を達成した。
サンプル効率: BaSE は、Greedy や固定割り当てのベースラインよりも有意に速く（より少ない世代と FLOPs で）目標適合度閾値に到達した。例えば、MinMaxDist において、UCB は 92 世代で 0.95 の閾値に到達したが、Greedy ベースラインでは 485 世代を要した。
アブレーション: 適度なアームプールサイズ（ $K \in \{5, 10, 20\}$ ）が、多様性と改善深度の間の最良のトレードオフを提供した。

意義と主張

本論文は、計算資源の割り当てが、モデルのスケーリングやプロンプトエンジニアリングとは別に、LLM に導かれた進化探索を改善するための独立したかつ重要なレバーであると主張する。

割り当て対エンジニアリング: 著者らは、彼らの改善がより良いプロンプトやモデルによるものではないことを強調している。実際、彼らは、ShinkaEvolve のような一部のベースラインが、特定のタスクで高いスコアを達成した理由の一部が、scipy.optimize のような提案を含むプロンプト誘発的なヒントによるものであったと指摘するのに対し、BaSE は適応的リソース経路制御のみを通じて利益を達成している。
信頼性: 主な貢献は、「最悪の場合」の報告から「期待される」性能への焦点の移行である。BaSE は信頼性の向上を提供し、実務者が既に停滞している軌跡に固定予算を浪費する可能性を低減する。
相補性: BaSE は、親サンプリングのような既存のラン内メカニズムと相補的なものとして提示される。これは、既存のプロトコル（Greedy、Island）の上にレイヤリングされ、特に不安定または高ばらつき環境において性能をさらに向上させることができる。

本研究は、モデルの能力が達成可能ことの上限を設定する一方で、割り当てがその上限にどの程度効率的に近づくかを支配すると結論づけており、有限予算探索に対する適応的割り当て（バンディットによる）は堅牢な戦略である。