技術要約：ImprovEvolve：Basin-HoppingとLLMによる進化型探索の融合

問題提起

本論文は、複雑な数学的最適化問題（パッキング問題、関数不等式、球面符号など）、特に険しく非凸かつ非平滑なランドスケープを持つ問題に対して、大規模言語モデル（LLM）を用いる際の課題に取り組んでいる。AlphaEvolveのような先行研究では、候補解を直接出力するモノリシックなプログラムを進化させることに成功したが、著者らはこのアプローチがLLMに過度な認知的負荷を強いていると主張している。モデルは、初期化スキーム、探索戦略、および終了条件を同時に設計しなければならない。その結果、生成されたプログラムは、特定の制約や非凸性を効果的に処理できない既製のルーチン（L-BFGS-Bなど）に依存しがちである。その結果、LLMが生成した解は、数学的な洞察とヒューリスティクスを融合させたものにとどまり、厳密に最適化タスクを解決することには失敗し、未知の問題サイズへの汎用性や、専門家が構築した解を上回る能力に欠けることが多い。

手法：ImprovEvolve

著者らは、最適化タスクを専門化されたサブルーチンへと分解し、Basin-Hopping（盆地探索）というグローバル最適化技術とLLMによる進化型探索を効果的に統合するアルゴリズム的代替案として、ImprovEvolveを提案している。

コアとなる分解

単一の関数を進化させて解を出力させるのではなく、ImprovEvolveは以下の3つの異なるオペレータを実装するPythonクラスを進化させる。

1. generate_config(seed): ランダムなシードから実行可能な解を初期化する。
2. improve(x): 配置 $x$ を局所的に最適化して洗練させ、少なくとも $x$ と同等以上の適応度を持つ解 $x'$ を返す。
3. perturb(x, \sigma): 特定の強度 $\sigma$ で探索空間をランダムに探索する。

検証スキーム（Basin-Hopping）

進化させたクラスは、Monotonic Basin-Hopping（$T=0$）を模倣した2段階の検証スキーム（アルゴリズム1）内で利用される。

• ステージA（初期化）: 複数の初期配置を生成し、improve を通じて洗練させる。最も優れた結果を始点 $x^*$ として選択する。
• ステージB（反復探索）: 摂動（perturbation）と改善（improvement）の $R$ ラウンドの試行を行う。各ラウンドにおいて、摂動の強度 $\sigma$ は $\sigma_{max}$ から $\sigma_{min}$ へと幾何級数的に減少する。プロセスは以下の通りである：
  1. 現在の最良解を摂動させる：$x' = \text{perturb}(x^*, \sigma)$。
  2. 摂動させた解を洗練させる：$x'' = \text{improve}(x')$。
  3. 単調受理（Monotonic Acceptance）: 適応度が厳密に改善された場合にのみ、$x^*$ を $x''$ に更新する。

この分解により、LLMのタスクはエンドツーエンドの最適化器を設計することから、初期化、局所探索、および探索のためのドメイン固有のヒューリスティクスをエンコードすることへと移行し、それらは古典的なBasin-Hoppingフレームワークによってオーケストレーションされる。

進化フレームワーク

システムは、MAP-Elitesループを備えたGigaEvoフレームワークを利用する。候補プログラムの適応度は、完全な2段階検証スキームを実行することによって決定される。LLM（初期化にはGemini 3 Pro、進化にはGemini 3 Flash）は、適応度のフィードバックと系統の知見に基づき、Improv クラスのコードを変異させる。

主な貢献と結果

1. 六角形パッキング（HEX $n$）

• タスク: $n$ 個の正六角形を、最小の包含正六角形の中にパッキングする。
• 結果:
  • $n=11$ において、ImprovEvolveは一辺の長さ $L=3.9245$ という新しいSOTA（最先端）のパッキングを発見した。これはAlphaEvolveの $3.9301$および従来の人間による記録である$3.9434$ を上回るものである。
  • 進化させたプログラムは、再進化なしで未知の問題サイズ（$11 \le n \le 24$）に汎用し、$n=12, 15, 16$ において新たなSOTAパッキングを見出した。
  • ImprovEvolve+E: 軽微な人間による編集（最適化器の変更、ペナルティ重みの調整）を加えることで、システムは $n=14, 17, 23$ において新たなSOTAパッキングを見出し、$n=25-30$ のように事前の結果が存在しない領域に対しても構造化されたパッキングを提供した。
• 比較: ImprovEvolveは、オーバーラップエラーにより $n > 11$ への汎用性に失敗したGigaEvoのベースラインを大幅に上回った。

2. 第二自己相関不等式（ACI 2）

• タスク: 不等式 $\|f * f\|_2^2 \le C_2 \|f * f\|_1 \|f * f\|_\infty$ において定数 $C_2$ を最大化する非負関数 $f$ を見つける。
• 結果:
  • ベースとなるImprovEvolveプログラムは $C(f) = 0.9512$ を達成し、オープンソースのベースラインを上回ったが、AlphaEvolveの $0.96102$ には及ばなかった。
  • ImprovEvolve+E: AlphaEvolveの解から最適化を再開し、（プログレッシブな解像度スケーリング（最大1.6Mステップまで）や下限クリッピングの除去といった）人間によるガイド付きの編集を適用することで、システムは $C(f) = 0.96258$ という新たなSOTA下限を達成した。
• 意義: これは、本フレームワークが、専門家や他のモデルから提供された高品質な既存の解を洗練できる能力を持つことを示しており、これはモノリシックなLLMアプローチが苦戦する能力である。

3. 球面符号

• タスク: 最大のペア間内積（コヒーレンス）を最小化するように、単位球面 $S^{d-1}$ 上に $N$ 個の点を配置する。
• 結果:
  • Cohnのカタログにある90の多様な構成（$d \in [8, 16]$）に対して評価を実施。
  • ImprovEvolve++（複数の次元にわたって較正された汎用的なインプルーバー）は、90の構成のうち53個において最大余弦（maximum cosine）を厳密に低下させ、平均相対改善率 0.1765% を達成した。
  • これは、最良の既存プログラム（ImprovEvolve）と比較して 2.35倍 の改善である。
  • 診断（UMAPおよび内積分布）によれば、ImprovEvolve++は点の局所的な調整だけでなく、グローバルな構造的再配置を行い、点を探索空間内の異なる領域へと移動させていることが示された。

統計的堅牢性

マルチラン研究により、ImprovEvolveによる改善がGigaEvoベースラインに対して統計的に有意（$p < 0.05$）であることが確認され、モジュール化された分解がモノリシックな最適化器よりも再現可能な優位性を持つことが検証された。

意義と主張

本論文は、最適化タスクをモジュール化されたサブ問題へと分解することが、LLM主導の発見における重要な原則であると主張している。

• 認知的負荷の軽減: 初期化、局所的改善、および摂動を分離することで、LLMは全探索プロセスをオーケストレートすることではなく、数学的構造とヒューリスティクスのエンコードに集中できる。
• 人間とLLMの協調: モジュール化されたインターフェースにより、ドメインエキスパートがターゲットを絞った最小限の編集（例：最適化器の変更、解像度スケジュールの調整）を適用して性能を大幅に向上させることが可能となり、LLMが生成したコードとエキスパートレベルのチューニングとの間の溝を埋めることができる。
• 汎用性: improve/perturb インターフェースにより、進化させたプログラムは未知の問題サイズに汎用でき、また専門家が提供した解から最適化を再開することが可能となり、モノリシックなエンドツーエンドプログラムの脆弱性を克服している。

著者らは、本研究をLLMによる数学的発見をスケールアップするためのステップとして位置づけており、将来のシステムは、このようなカスタマイズされた分解と、どのモジュールを洗練すべきかを自律的に決定するエージェンティックなワークフローを組み合わせるべきであると示唆している。なお、定量的な評価は現在これら3つの特定の最適化ドメインに限定されているため、広範な汎用性に関する記述は控えめとなっている。