From Heuristic Selection to Automated Algorithm Design: LLMs Benefit from Strong Priors

本論文は、LLM による自動アルゴリズム設計において、高品質なアルゴリズムコードの例（事前知識）をプロンプトに組み込むことで、擬似ブール最適化や黒箱最適化の性能を大幅に向上させる手法を提案し、ベンチマーク研究の統合が LLM 駆動型最適化の効率性と堅牢性を高めることを示しています。

要約

この論文は、**「AI（大規模言語モデル）が新しいアルゴリズム（計算のレシピ）を自分で作れるようになる研究」**について書かれています。

でも、ただ「作らせて」終わりではなく、**「どうすれば AI がもっと上手に、効率的に新しいレシピを考え出せるのか？」**という疑問に答えた、とても面白い研究です。

以下に、専門用語をできるだけ使わず、日常の例え話を使って解説します。

---

🍳 料理人の AI と「名シェフのレシピ本」の話

想像してください。
**「AI（大規模言語モデル）」**は、天才的な料理人ですが、まだ経験が浅い新人シェフだとしましょう。
**「黒箱最適化（Black-box Optimization）」**とは、中身が見えない謎の料理（問題）に対して、どんな材料を使えば一番美味しいか（一番良い答え）を見つける作業です。

1. 従来のやり方：「言葉だけで指示する」

これまでの研究では、AI 料理人に「新しい料理を作って！」と言葉（プロンプト）だけで指示していました。
「もっと工夫して」「新しいアイデアを出して」と言っても、AI は「えーと、何を作ればいいの？」と迷ってしまい、失敗したり、同じような料理しか作れなかったりします。
これは、**「レシピも何もないのに、ただ『美味しい料理を作って』と言うだけ」**のような状態です。

2. この論文の発見：「言葉より『実例』が重要！」

著者たちは、AI がどんな言葉に反応しているかを詳しく分析しました（これを「トークン単位の分析」と言います）。
すると、驚くべきことが分かりました。

• **「料理のコンセプトを説明する文章」**は、あまり重要ではない。
• **「実際に使われている、優秀な料理人のレシピ（コード）」**こそが、AI の思考を最も強く導く！

つまり、**「言葉で指示するより、良いレシピ本を渡して『これを参考にしてください』と言う方が、AI は劇的に上手になる」**という発見です。

3. 提案した方法：「BAG（ベンチマーク支援ガイド付き進化）」

この発見を活かして、著者たちは新しい方法**「BAG」**というやり方を提案しました。

• 従来の方法： 何もない状態から AI に「新しい料理を考えて」と言っていた。
• BAG の方法：
  1. まず、**「過去の料理コンテストで優勝した名シェフのレシピ（ベンチマークアルゴリズム）」**を 5 種類ほど AI に見せます。
  2. AI に「この 5 つのレシピの中から一つ選んで、それを少し改良して、もっと美味しい料理を作って」と言います。
  3. 改良した料理が美味しければ、それを次の基準にします。
  4. 時々、また別の優勝レシピを見せて、「今度はこっちをベースに改良して」と指示します。

これを**「名シェフのレシピを『先入観（強い事前知識）』として与える」と言います。
AI は「ゼロからゼロ」で考えるのではなく、「優秀な先輩のアイデアを土台にして、そこから少しだけ進化させる」**という作業をするので、無駄な失敗が減り、早く最高の料理（最適解）にたどり着けるのです。

🏆 実験結果：「名シェフのレシピ」を使うと最強になる

この方法を、2 つの有名な料理コンテスト（PBO と BBOB というベンチマーク）で試しました。
結果は圧巻でした。

• 他の AI 料理人たち（EoH や LLaMEA など）が必死に考えても、**「BAG（名シェフのレシピあり）」**には勝てませんでした。
• 特に、**「改良（Refine）」**という作業に特化して、良いレシピをベースに微調整を繰り返すのが最も効果的でした。

💡 結論：何が変わるの？

この研究が教えてくれることはシンプルです。

「AI に新しいことをさせたいなら、まずは『良いお手本』を見せてあげなさい」

これまでは、AI に「自由に考えて」と言ったり、複雑な言葉で指示したりしていましたが、「過去の成功例（ベンチマーク）」を AI の頭に入れることで、AI のパフォーマンスが格段に向上することが証明されました。

これは、AI が問題を解決するだけでなく、**「人間が蓄積してきた知恵（過去のアルゴリズム）を AI がどう活かすか」**という、新しい時代の「AI と人間の協力関係」のヒントになる素晴らしい研究です。

---

一言でまとめると：
「AI に新しいレシピを考えさせるなら、ただ『頑張って』と言うのではなく、『過去の優勝レシピ本』を渡して、それを改良させるのが一番速くて上手にできるよ！」というのがこの論文のメッセージです。

技術概要

論文「From Heuristic Selection to Automated Algorithm Design: LLMs Benefit from Strong Priors」の技術的サマリー

この論文は、大規模言語モデル（LLM）を用いた自動化アルゴリズム設計（AAD）において、「高品質な事前知識（ベンチマークアルゴリズム）の提供」が LLM の性能を劇的に向上させることを示した研究です。従来の LLM 駆動型最適化が直感的なプロンプト設計に依存していたのに対し、本論文は LLM の内部動作を解析し、コード例の重要性を定量的に証明した上で、それを活用した新しい手法「BAG（Benchmark-assisted Guided evolutionary approach）」を提案しています。

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

---

1. 背景と問題設定

• 背景: 進化計算の分野では、膨大な数のヒューリスティック最適化アルゴリズムが開発されています。しかし、実務家は「どの最適化器を選ぶか（AAS）」や「どのように専用アルゴリズムを構築するか（AAD）」という課題に直面しています。近年、LLM を用いてアルゴリズムコードを直接生成・進化させる手法（FunSearch, EoH, LLaMEA など）が注目されています。
• 課題: 既存の LLM 駆動型アプローチは、主に言語的な指示（プロンプト）に基づいて検索戦略を設計していますが、そのプロンプトのどの部分が LLM の出力にどの程度影響を与えているのか、そのメカニズムは不明瞭でした。また、ブラックボックス最適化（BBO）の文脈では、問題の内部構造が不明なため、既存のベンチマーク知識をどう活用するかが課題となっていました。

2. 手法と分析アプローチ

A. プロンプトのトークンごとの寄与分析（AttnLRP の活用）

まず、LLM がどのようにコードを生成するかを理解するため、AttnLRP（Attention-aware Layer-wise Relevance Propagation）というアテンション可視化手法を適用しました。

• 分析対象: プロンプト内の各トークン（タスク記述、戦略指示、親ヒューリスティックのコード、フィットネス値など）が、生成されたアルゴリズムコードに与える寄与度（Relevance Score）を計算しました。
• 発見: 分析の結果、**「コードそのもの（例示コード）」と「そのコードに対する戦略指示（Refine/Generate など）」**が、生成されるアルゴリズムに最も強い影響を与えることが判明しました。一方、タスクの言語的記述や親アルゴリズムのスコア（フィットネス値）の影響は比較的小さいことが示されました。

B. 提案手法：BAG (Benchmark-assisted Guided evolutionary approach)

上記の知見に基づき、事前のベンチマークアルゴリズムを「強い事前知識（Strong Priors）」として LLM に提供し、探索領域を誘導する手法 BAG を提案しました。

• 基本戦略: (1+1) elitist 探索戦略を採用。各イテレーションで、現在の最良アルゴリズムを改良するか、新規アルゴリズムを生成するかを確率的に選択します。
• ベンチマークの活用:
  • 初期化: 事前のベンチマークセット（$A_{bench}$）から有望なアルゴリズムコードを選択し、初期プロンプトの例示コードとして使用します（ランダムサンプリングではなく）。
  • 適応（Adaptation）: 一定間隔（$q$ 回ごと）で、ベンチマークセットからランダムに選ばれた別のアルゴリズムを例示コードとして提示し、LLM にその改良を指示します。これにより、単一のアルゴリズムパターンに陥るのを防ぎつつ、有望な探索領域を維持します。
• 特徴: 既存手法（EoH, LLaMEA など）が主に「戦略（Strategy）」部分のプロンプト設計に依存するのに対し、BAG は**「コードそのもの」をプロンプトの核心として利用**し、探索空間を効果的に制限・誘導します。

3. 主要な貢献

1. プロンプト設計の定量的分析: LLM 駆動型最適化において、プロンプトのどの要素がコード生成に最も重要かを初めて AttnLRP を用いて体系的に分析し、「コード例」の重要性を実証しました。
2. 探索領域の制御可能性の証明: 特定の例示コード（強い事前知識）を提供することで、LLM の探索行動を特定の領域に誘導（制約）できることを示しました。
3. BAG 手法の提案と実証: 事前ベンチマーク知識を統合した新しいガイド付き進化手法を提案し、2 つの主要なブラックボックス最適化ベンチマーク（pbo と bbob）において、既存の最先端手法を上回る性能を達成しました。

4. 実験結果

• ベンチマーク:
  • pbo (Pseudo-Boolean Optimization): 23 種類の離散最適化問題。
  • bbob (Black-Box Optimization): 24 種類の連続最適化問題。
  • 各問題で 5 つのインスタンスを使用し、合計 235 の問題インスタンスで評価。
• 比較対象: EoH, LHNS, LLaMEA, MCTS-AHD, ReEvo の 5 つの SOTA 手法。
• 使用モデル: Gemini 2.0 Flash, GPT 5 Nano, Qwen3 Coder Flash の 3 種類の LLM。
• 評価指標: 実行時間に対する累積分布関数（ECDF）の面積（AUC）。
• 結果:
  • pbo _suite: Gemini と Qwen では BAG が全手法を凌駕し、GPT でも EoH に次ぐ 2 位（僅差）となりました。
  • bbob_suite: 3 つの LLM すべてにおいて、BAG は 2 位手法よりも平均で14% 高い AUCを達成し、顕著な優位性を示しました。
  • 収束性: 図 5 に示されるように、ベンチマークアルゴリズムの定期的な導入（改良指示）が、探索の多様性を保ちつつ性能を向上させることが確認されました。また、CodeBLEU による解析では、新しいベンチマークコードが導入された直後に生成されたアルゴリズムが、それ以前のコードとは異なる構造を持つことが示されました。

5. 意義と結論

• 実用的意義: LLM 駆動型最適化において、単なる言語指示だけでなく、「高品質なコード例（事前知識）」をプロンプトに埋め込むことが、効率性とロバスト性を大幅に向上させることが実証されました。
• 学術的意義:
  • LLM のブラックボックス性を、アテンション可視化技術を用いて解明し、その振る舞いを制御する新たな指針を提供しました。
  • 古典的な自動化アルゴリズム設計（AAS/AAD）と、最新の LLM 駆動アプローチを、ベンチマーク知識を通じて統合する可能性を示しました。
• 今後の展望: 本手法は (1+1) 戦略に基づいていますが、これを集団ベース（Population-based）のフレームワークに統合することで、さらに多様で効率的な探索が可能になると予想されています。また、Nevergrad などの大規模アルゴリズムコレクションをベンチマークとして活用する可能性も示唆されています。

総じて、この論文は「LLM は強力な事前知識（特にコード例）を与えられることで、より効果的にアルゴリズムを設計できる」という重要な知見を提供し、ブラックボックス最適化の分野における LLM 応用の新たな方向性を示唆しています。