技術要約: LLaMEA-SAGE

問題提起

大規模言語モデル（LLM）を用いた自動アルゴリズム設計（Automated Algorithm Design: AAD）は、自然言語のプロンプトから最適化アルゴリズムを直接発見するための有望なパラダイムとして台頭している。しかし、LLaMEAのような既存のLLMベースのアプローチは、進化的な探索を導くために、ほぼ排他的にフィットネス・フィードバック（ベンチマークにおける性能）に依存している。この「ブラックボックス」的なフィードバックループは、生成されたコード内に存在する膨大な情報を活用できていない。その結果、探索戦略は、大規模で不均質なコード空間において探索（exploration）と活用（exploitation）のバランスを取ることに苦慮し、早期の停滞や高価なLLMクエリの非効率な利用を招くことが多い。さらに、初期生成後のLLM生成アルゴリズムをどのように系統的に改善すべきか、また、それらの改善が制御されたベンチマーク下で最先端（SOTA）の手法とどのように比較されるかについての理解も限られている。

手法: LLaMEA-SAGE

本論文は、構造化された説明可能なAI（XAI）フィードバックをLLaMEAの進化型アルゴリズム設計プロセスに統合するフレームワーク、LLaMEA-SAGEを提案する。コアとなるメカニズムは、候補アルゴリズムのコードから構造的特徴を抽出し、それを用いて後続の突然変異を誘導することである。

1. 構造的特徴抽出

各候補アルゴリズムは、実行可能なPythonコードとして表現される。システムはコードを**抽象構文木（AST）**へと解析し、有向グラフを構築する。このグラフから、システムは以下の豊富な特徴量セットを抽出する：

• グラフ理論的統計量: ノード数/エッジ数、次数統計（平均、分散、エントロピー）、木の深さ、クラスタリング係数、およびパスベースの指標（直径、平均最短経路）。
• 複雑性の指標: 循環的複雑度（Cyclomatic complexity）、関数トークン数、および関数全体にわたって集計されたパラメータ数。

2. アーカイブに基づくサロゲートモデリング

進化プロセス中、評価されたすべての解、そのフィットネス・スコア、および抽出されたコード特徴量はアーカイブに保存される。最小アーカイブサイズに達すると、コード特徴量と観測されたフィットネスとの関係を近似するために、**勾配ブースティング決定木モデル（XGBoost）**が学習される。このサロゲートモデルは、アルゴリズムの構造と性能の間の非線形な関係を学習する。

3. 指針のための説明可能なAI（SHAP）

指示を実用的なものにするため、システムは学習済みサロゲートモデルに**SHAP（SHapley Additive exPlanations）**を適用する。SHAP値は、予測フィットネスに対する各特徴量の寄与度を定量化する。最も絶対値が大きい属性を持つ特徴量が選択され、そのSHAP値の符号によって、性能を向上させるために特徴量の値を増やすべきか減らすべきかが決定される。

4. 指導付き突然変異プロンプティング

構造的なガイダンスは、標準的な突然変異プロンプトに付加される自然言語の指示へと翻訳される。例えば、循環的複雑度を高めることが性能向上に相関しているという分析結果が得られた場合、プロンプトは次のように修正される："アーカイブ分析に基づき、ソリューションの総循環的複雑度を高めるように試みてください。"
極めて重要な点は、このガイダンスが、LLMの表現力を維持するために、厳格な構文的制約や定義済みのテンプレートを課すことなく、LLMの生成を経験的に有益な構造領域へと偏らせる点である。

主な貢献

1. LLaMEA-SAGEフレームワーク: ASTと複雑性分析から派生した特徴量駆動型のフィードバックを、サロゲートモデルとSHAP分析を介して、特徴量駆動の進化型アルゴリズム設計を誘導する新しいメカニズムの提案。
2. 系統的なベンチマーク: SOTAのLLMベースのヒューリスティック設計手法、具体的には MCTS-AHD（モンテカルロ木探索によるアルゴリズム・ヒューリスティック設計）および LHNS（LLM駆動型ヒューリスティック近傍探索）、ならびにバニラなLLaMEAベースラインとの包括的な実験比較。
3. 実証的検証: コード進化グラフ（CEG）と統計的テストを用いた広範な分析に裏付けられた、構造的ガイダンスがアルゴリズムの品質と堅牢性を向上させることの証明。

実験結果

著者らは、IOH-BLADEベンチマーク・ツールボックスを用いて、2つの主要な実験を通じてLLaMEA-SAGEを評価した。

実験1: 制御された比較 (SBOX-COST)

• 設定: SBOX-COSTスイートのサブセット（10次元、5インスタンス）において、バニラなLLaMEAとLLaMEA-SAGEを比較。
• 知見: LLaMEA-SAGEは、特に進化プロセスの初期段階において、バニラなLLaMEAよりも高速に優れた性能を達成した。両手法とも予算内で同様の最終性能に到達したが、誘導型のアプローチは実行間の分散が小さかった。
• 統計的有意性: LLaMEA-SAGEは、平均11.1の収束曲線下面積（AUC）ユニットの改善を示し、大きな効果量（Cliff's $\delta$ = 0.60）を得た。しかし、独立した実行回数が限定的であったため（5シード）、差は統計的有意性には達しなかった（$p=0.44$）。
• 行動分析: コード進化グラフは、ガイダンスが構造的探索を正常に偏らせたことを明らかにした。特筆すべきは、「refine（洗練）」プロンプトはガイダンスに従ってコードの複雑度を高めたのに対し、「random new（新規ランダム）」プロンプトはしばしばガイダンスを無視するか、あるいはより低い複雑度をもたらした点である。

実験2: 大規模ベンチマーク (MA-BBOB)

• 設定: GECCOコンペティションの標準であるMany Affine BBOB (MA-BBOB) スイートにおいて、LLaMEA-SAGEをバニラなLLaMEA、MCTS-AHD、およびLHNSと比較評価。
• 知見: LLaMEA-SAGEは、SOTAであるMCTS-AHDやLHNSを含むすべてのベースラインを一貫して上回った。バニラなLLaMEAがフル評価予算を使い切っても到達できなかったフィットネスレベルに到達した。
• 効率性: トークン使用量の観点では、LLaMEA-SAGEはバニラなLLaMEAよりもわずかに高価であったが、1つの解に対してLLMを複数回呼び出すMCTS-AHDよりも大幅に効率的であった。
• 汎用性: 未知のインスタンス（異なる次元および問題インスタンス）に対する最終検証では、LLaMEA-SAGEによって発見された最良のアルゴリズムは、10次元および20次元のタスクにおいて、他の自動設計アルゴリズムおよび2025年MA-BBOBコンペティションの勝者を上回った。ただし、最適化対象として特別に調整された5次元のタスクにおいては、チューニング済みのコンペティション勝者を凌駕することはできなかった。

重要性と主張

本論文は、LLaMEA-SAGEが、自動アルゴリズム設計におけるコード構造と人間が理解可能な性能フィードバックの間のギャップを埋めることに成功したと主張している。構造的信号を自然言語に変換することで、本手法はLLMの創造的な能力を制限することなく、データ駆動型の帰納バイアスを提供し、LLM駆動の進化を導く。

著者らは、コード特徴量から得られる不完全でノイズの多い相関であっても、AADの初期段階において探索を有利に偏らせるには十分であることを強調している。本研究は、コードから得られる信号がアルゴリズム発見の効率と安定性を効果的に向上させ得ることを示しており、既存のヒューリスティック中心のアプローチに対する、スケーラブルでテンプレートフリーな代替案を提示している。

限界と今後の課題

著者らは、いくつかの限界についても謙虚に述べている：

• LLMへの依存性: 実験は単一のLLMバックエンド（GPT-5-mini）で行われたが、Geminiを用いた予備的なアブレーション解析でも一貫した傾向が示された。
• 範囲: 評価は、中程度の次元における連続的なブラックボックス最適化に限定されており、高次元、ノイズの多い、あるいは根本的に異なる問題クラスへの汎用性は依然として未解決の課題である。
• 静的解析: 現在の機能セットは静的な構造特性のみを捉えており、最適化実行中の動的な実行挙動や相互作用効果は無視されている。

今後の課題として、構造的特徴と実行時記述子の結合、適応的なマルチ特徴量ガイダンスの探索、および他のLLMベースのAADフレームワークへのこのメカニズムの統合が提案されている。