AdaEvolve: 適応的 LLM 駆動ゼロ次最適化の技術的サマリー

本論文は、大規模言語モデル（LLM）を用いた自動プログラム生成・アルゴリズム発見の分野において、AdaEvolve という新しい適応的進化フレームワークを提案しています。従来の「ワンショット生成」や「静的なスケジュールに基づく探索」から脱却し、推論時の計算リソースを動的に最適化する階層的適応型最適化アプローチを確立しました。

以下に、問題定義、手法、主要な貢献、実験結果、および意義について詳細をまとめます。

---

1. 問題定義と背景

背景

LLM 研究のパラダイムは、トレーニングパラメータのスケールアップから、推論時の計算スケールアップへと移行しています。LLM を「意味的変異オペレーター」として進化ループに組み込むことで、離散・非微分可能な探索空間をナビゲートする手法（LLM 駆動進化アルゴリズム）が注目されています。

既存手法の課題

現在の LLM 駆動進化システム（例：OpenEvolve など）には、以下の重大な欠点があります。

• 静的なスケジュール: 探索強度、資源配分、プロンプトテンプレートなどが事前に固定されており、探索プロセスの非定常なダイナミクス（局所最適解への陥没や停滞）に対応できません。
• リソースの無駄遣い: 停滞している集団にリソースが均等に配分され続け、有望な領域が十分に探索されない。
• 手動チューニングの必要性: 問題ごとにハイパーパラメータ（変異率、集団サイズなど）を手動で調整する必要があり、柔軟性に欠ける。

これらは連続最適化における「適応的勾配法（Adam など）」の概念を、勾配が存在しない（ゼロ次）プログラム生成問題にどう適用するかという課題として提起されています。

---

2. 提案手法：AdaEvolve

AdaEvolve は、LLM 駆動進化を**「階層的適応最適化問題」として再定式化します。すべての適応判断を、過去の実績に基づいて計算された「蓄積された改善シグナル（Accumulated Improvement Signal, $G_t$）」**という単一の指標に基づいて統一的に行います。

このシグナルは、正規化された改善度の二乗の指数移動平均として定義され、探索の「勾配」に相当する役割を果たします。

3 つの適応レベル

AdaEvolve は、以下の 3 つのレベルで協調的に動作します。

Level 1: 局所適応（Local Adaptation）

• 目的: 個々の島（Island/部分集団）内での「探索（Exploration）」と「利用（Exploitation）」のバランスを動的に調整。
• メカニズム:
  • 改善シグナル $G_t$ が大きい場合（生産的）：探索強度を低下させ、現在の有望な解を精緻化する（利用重視）。
  • 改善シグナル $G_t$ が小さい場合（停滞）：探索強度を高め、局所最適解からの脱出を図る。
  • これにより、手動の再起動閾値なしに、停滞を検知して自動的に探索モードへ切り替えます。

Level 2: 大域的適応（Global Adaptation）

• 目的: 計算リソース（予算）を、最も生産的な「島」へ動的に配分。
• メカニズム:
  • 多腕バンディット問題としてモデル化。各島を「腕」と見なします。
  • 大域正規化報酬: 各島の局所的な改善ではなく、**大域的最善解（Global Best）**に対する改善度で報酬を評価します。これにより、低い基準点からの些細な改善にリソースが浪費されるのを防ぎます。
  • UCB（Upper Confidence Bound）アルゴリズム: 生産性の高い島にリソースを集中させ、停滞した島への配分を減らします。
  • 動的な島生成: 全島が停滞した場合、新しい島を自動的に生成し、多様性を確保します。

Level 3: メタガイダンス（Meta-Guidance）

• 目的: 数値的な適応（Level 1, 2）だけでは脱出できない「概念的な局所最適解」からの脱出。
• メカニズム:
  • 大域的停滞が検知された場合、LLM に「システム 2（分析的思考）」を働かせさせます。
  • 問題仕様、評価器、失敗した試行を分析し、**「解の戦術（Solution Tactics）」**を生成します（例：「貪欲法から動的計画法へ切り替える」「連続最適化アルゴリズム SLSQP を導入する」など）。
  • 生成された戦術をプロンプトに注入し、探索の方向性を質的に変化させます。

---

3. 主要な貢献

1. 適応的進化フレームワークの提案:
   • 探索強度、リソース配分、戦略生成を単一の適応型オプティマイザーで統合。従来のアドホックなヒューリスティックを排除し、一貫した適応メカニズムを実現。
2. 大域正規化された動的リソース配分:
   • 島ごとのローカル履歴ではなく、大域的最善解に対する相対的な改善度に基づいてリソースを配分するバンディットベースのスケジューラを提案。停滞した集団へのリソース浪費を防ぎます。
3. 強力な汎化性能:
   • 185 の異なる最適化・アルゴリズム発見問題（組合せ幾何、システム最適化、アルゴリズム設計）において、同一のハイパーパラメータ設定でベースラインを凌駕。
   • 特定の数学的最適化タスクやシステムベンチマークにおいて、人間や AlphaEvolve（プロプライエタリモデル）の最高記録に匹敵、あるいは上回る性能を達成。

---

4. 実験結果

AdaEvolve は、以下の 3 つの主要ベンチマークセットで評価されました。

4.1 数学的最適化ベンチマーク（6 課題）

• タスク: 円パッキング（Circle Packing）、Heilbronn 三角形問題など。
• 結果:
  • Circle Packing (Square, N=26): AdaEvolve は 2.636 を達成。これは人間の世界最高記録（2.634）および AlphaEvolve（2.635）を更新しました。
  • 固定ポリシーのベースライン（OpenEvolve, GEPA, ShinkaEvolve）が早期に停滞する問題において、AdaEvolve は顕著な改善を見せました。

4.2 ADRS システムベンチマーク（7 課題）

• タスク: 分散システム、クラウドストレージコスト最小化、トランザクションスケジューリングなど。
• 結果:
  • 7 課題すべてで、GPT-5 および Gemini-3-Pro の両バックボーンにおいて、他のオープンソースベースラインを凌駕しました。
  • 特に、スパースな報酬やバースト的な改善が見られるタスク（TXN など）で、適応性が有効に機能しました。

4.3 Frontier-CS ベンチマーク（172 課題）

• タスク: 開放的なコンピュータサイエンス問題（アルゴリズム設計から研究レベルのシステムタスクまで）。
• 結果:
  • 単一 LLM 呼び出し（GPT-5）の中央値スコアが 0 であるような難易度の高い問題において、AdaEvolve は平均スコアを 3 倍 向上させました。
  • 全体的に、他の進化アルゴリズムベースライン（OpenEvolve, ShinkaEvolve, GEPA）に対して一貫して優位な性能を示しました。

アブレーション研究

• Level 3（メタガイダンス）の重要性: 停滞時の戦術生成を無効化すると、性能が最も大きく低下しました。これは、数値的調整だけでは解決できない「概念的な壁」を越えるために不可欠であることを示しています。
• 動的島生成: 固定数の島を使用するよりも、停滞に応じて島を生成する方がリソース配分が効率的でした。

---

5. 意義と結論

AdaEvolve は、LLM 駆動のアルゴリズム発見において、「静的なルール」から「動的な適応」への転換を実現しました。

• 自動化の深化: ユーザーはモデル名と反復回数のみを指定すればよく、問題ごとの複雑なハイパーパラメータ調整が不要になりました。
• 計算効率の向上: 停滞している探索にリソースを割くことなく、有望な領域へ集中させることで、計算コストを削減しつつ解の質を最大化します。
• 人間を超える可能性: 円パッキング問題において、人間が数十年かけて到達した世界最高記録を更新したことは、LLM による推論時計算のスケールアップが、複雑なアルゴリズム発見において人間を超える能力を持ちうることを示唆しています。

本フレームワークは、ゼロ次最適化問題における適応制御の新たな標準となり、将来的により複雑な科学技術課題の解決に応用が期待されます。