探索と進化

前三章では、誰が、何を、どの実行結果にもとづいて変えるかを整理した。次に必要なのは、複数の更新候補（candidate）をどの順で試し、結果を見て何を試すかを決めることである。プロンプト、ワークフロー、コードは小さな変更でも挙動が大きく変わり、評価には費用とばらつきがある。本章では、更新候補をどの順で評価し、どの履歴を残し、予算をどこへ配るかで探索法を整理する。

\(N\)個から選ぶ方法を基準にする

最も単純な最適化器（optimizer）は、\(N\)個の更新候補を独立に生成し、開発用データ（development data）のスコアが最大のものを選ぶ。

この基準手法は重要である。複雑な探索アルゴリズムが勝っても、単に多くの更新候補やトークンを使っただけかもしれない。比較では次を揃える。

• 更新候補数
• 更新候補一つあたりの提案トークン
• 更新候補を実行する事例数
• 対象モデル（target model）と最適化器モデル
• 昇格用検証データ（promotion validation）への照会数
• 並列実行による経過時間

スコアに雑音があると、\(N\)を増やすだけで偶然高い更新候補を選びやすくなる。Best-of-\(N\)の改善には、成果物（artifact）の質と選択雑音の両方が含まれる。

履歴をプロンプトへ入れる探索

APEはタスク例から指示候補を生成し、部分集合でスコアを付けて再選択する (Zhou ほか 2023年)。OPROは過去の更新候補とスコアをメタプロンプトへ並べ、大規模言語モデル（large language model, LLM）である最適化器に次の更新候補を生成させる (Yang ほか 2024年)。数値勾配を使わず、LLMが履歴のパターンを読む。

この方法では、メタプロンプトが探索状態（search state）である。過去の更新候補をすべて入れるとコンテキストが増え、上位の更新候補だけにすると探索履歴を失う。さらに、OPROの報告表には各設定でテスト正解率が最高の指示を掲載する分析が含まれる。手法の探索機構と、汚染のない保留選択による効果量を分けて読む必要がある。

LLMが更新候補を生成するだけでは、LLM自体が最適化器とは限らない。更新候補の記録、評価、選択、停止を含む外側ループ（outer loop）が最適化器である。

近傍探索とビーム探索

近傍探索は現行版（incumbent）の近傍を編集する。プロンプト\(p_t\)に対する編集演算子（edit operator）を\(M\)とすると、

\[ \mathcal{C}_t = \{M(p_t,z_j)\}_{j=1}^{m} \]

として近傍の更新候補を作る。\(z_j\)は誤答、批評、変異指示などである。

ProTeGiはミニバッチ誤差からテキスト勾配（textual gradient）を作り、プロンプトの言い換えと編集をビームへ追加する。ビーム内の更新候補へ評価予算を割り当てるためにバンディット選択も使う (Pryzant ほか 2023年)。スカラー限定探索より失敗の方向を利用できる一方、局所批評が誤っていればビーム全体が同じ方向へ進む。

ProTeGiの一次論文は、反復が進むと学習性能が上がる一方でテスト性能が悪化する例も示す。また主要結果の一部は、最終ビームの複数プロンプトをテスト時に最大値プーリングする。したがって、単一プロンプトの永続改善、探索時選択、テスト時アンサンブルを分離して比較する。

TextGradは計算グラフ上のテキスト変数へ自然言語フィードバックを伝播し、局所編集を繰り返す (Yuksekgonul ほか 2025年)。グラフが固定されている場合は局所パラメータ探索であり、ワークフロートポロジー自体を探索する方法とは異なる。

木探索

木探索（tree search）は、更新候補をノード、編集をエッジとして履歴を分岐させる。AFlowはコードで表したワークフローをノードとし、モンテカルロ木探索（Monte Carlo tree search, MCTS）で新しいワークフローを生成・評価する (Jiayi Zhang ほか 2025年)。

MCTSでは、既知スコアが高い分岐だけを深掘りすると局所解へ偏る。未知分岐の探索と既知分岐の活用を均衡させる選択規則（selection rule）が必要である。ただし、ワークフロー評価の分散が大きい場合、ノード値の差が成果物の差かサンプリング雑音か分からない。

手法間比較では、最終ワークフローの推論コストだけでなく、木全体の探索コストも含める。AFlowの各ベンチマークで個別に探索した結果は、同じワークフローが別環境へ転用（transfer）できる証拠ではない。

予測器で評価を節約する

更新候補をすべて完全ロールアウトで評価できない場合、少数評価から性能を予測する代理モデル（surrogate）を使う。

MIPROは多段言語モデルプログラムの組合せをベイズ最適化（Bayesian optimization）で選び、AgentSquareはコンテキスト内性能予測器でワークフロー更新候補を絞る (Opsahl-Ong ほか 2024年; Shang ほか 2025年)。予測値だけで選択すると代理モデルの盲点へ探索が偏るため、最終候補と不確実性が高い更新候補を実際のロールアウトで評価し、予測誤差も報告する。

候補群を進化させる

進化探索（evolutionary search）は複数の更新候補を母集団として保持し、選択、変異、交叉を繰り返す。

EvoPromptはLLMを遺伝的アルゴリズム（genetic algorithm）または差分進化（differential evolution）の演算子として使い、自然言語の指示を進化させる (Guo ほか 2024年)。Promptbreederはタスクプロンプトだけでなく、タスクプロンプトを変異させる変異プロンプトも共進化させる (Fernando ほか 2024年)。これは「自己改善」一般ではなく、固定タスク適応度に基づく具体的なプロンプト進化である。

母集団の利点は、一つの現行版に探索を固定しないことである。一方、適応度を同じ開発用データ集合で繰り返し測ると、母集団全体がその集合へ適合する。母集団多様性は保留汎化を保証しない。

複数の強みを履歴に残す

一つの平均スコアでは、特定事例に強い更新候補を早く捨てる。GEPAは検証事例ごとに最良となる更新候補の和集合をパレート候補集合（Pareto archive）へ残し、その更新候補から反射的変異（reflective mutation）を作る (Agrawal ほか 2026年)。

パレート候補集合と多目的な採用は別である。GEPAの候補集合は主に事例別スコアの強みを残す。品質、コスト、安全性を同時に満たす更新候補を採用するには、別の評価記録と採否規則（acceptance rule）が必要である。

コード候補集合とオープンエンド探索

ADASのMeta Agent Searchは、評価済みエージェントコードの候補集合をコンテキスト内例としてコーディングエージェントへ渡し、新しいエージェントシステムを生成する (Hu ほか 2025年)。DGMはさらに、候補集合内の複数の親からコードベースを変更し、スコアが直ちに上がらない踏み石も系譜として残す (Jenny Zhang ほか 2026年)。

DGMの候補集合選択は同じコーディングベンチマークの反復評価を使うため、最適化期間（campaign）自体は観測済みタスクへの適応（transductive optimization）である。別ベンチマークでの転用結果とは分けて読む。

図 1: DGMの候補集合木（左）と最終最良エージェントへ至る系譜上の改善（右）。分岐候補集合は、直ちに最高スコアでない更新候補も後続改善の踏み石として保持する。出典: (Jenny Zhang ほか 2026年) Figure 3（CC BY 4.0、二つのパネルを原論文の配置に合わせて結合・ラスタライズし余白を切り抜き）

「オープンエンド」は、評価なしに任意の方向へ進むことを意味しない。DGMでは更新候補コードを実行し、ベンチマークスコアで候補集合へ追加する。探索空間が広く、単調改善を要求しないことと、評価目的が存在しないことは別である。

選択バイアスを測る

開発用データのスコアで多数の更新候補を比較すると、偶然高い雑音を含む更新候補を選びやすくなり、最大値は上方に偏る。同じデータを繰り返し使う選択バイアスは通常のモデル選択でも知られている (Cawley と Talbot 2010年)。

対策は、単にシードを増やすことではない。

• 開発用データで提案を作る
• 昇格用検証データで昇格（promotion）候補を選び、照会回数を記録する
• 最終候補を確定してから封印テスト（sealed test）を一度評価する
• 現行版も同じシードと事例実行（case-run）で再評価する
• Best-of-\(N\)基準手法と同じ予算で比較する
• 平均だけでなく更新候補分布を報告する

公開順位表を検証用に繰り返し使う場合、そのスコアは探索フィードバックである。最終テストとは呼べない。

停止規則

探索を「改善が止まったら」終了すると、どの集合上の改善かが問題になる。検証停滞を何度も確認すると、停止時点自体が昇格用検証データへ適合する。

次のいずれかを事前に固定する。

• 更新候補評価数
• 事例実行数
• 対象モデル / 最適化器のトークン予算
• 経過時間予算
• 昇格用検証データへの照会回数
• 改善閾値と忍耐回数
• 安全性またはコスト上限への到達

予算を使い切る前に有意な更新候補がなければ、現行版を維持する。「最良更新候補を必ず採用する」は停止規則（stopping rule）ではない。

要点

探索法の差は、LLMを使うかではなく、探索状態、提案演算子（proposal operator）、評価予算、選択、候補集合にある。Best-of-\(N\)、近傍/ビーム、木、代理モデル、母集団、パレート、コード候補集合を同じ予算と保留プロトコルで比較する。母集団や候補集合は探索多様性を保つが、汎化や性能退行なしの昇格を自動的には保証しない。

参考文献

Agrawal, Lakshya A., Shangyin Tan, Dilara Soylu, ほか. 2026年. 「GEPA: Reflective Prompt Evolution Can Outperform Reinforcement Learning」. International Conference on Learning Representations. https://arxiv.org/abs/2507.19457.

Cawley, Gavin C., と Nicola L. C. Talbot. 2010年. 「On Over-fitting in Model Selection and Subsequent Selection Bias in Performance Evaluation」. Journal of Machine Learning Research 11: 2079–107. https://jmlr.org/papers/v11/cawley10a.html.

Fernando, Chrisantha, Dylan Sunil Banarse, Henryk Michalewski, Simon Osindero, と Tim Rocktäschel. 2024年. 「Promptbreeder: Self-Referential Self-Improvement via Prompt Evolution」. Proceedings of the 41st International Conference on Machine Learning, 13481–544. https://proceedings.mlr.press/v235/fernando24a.html.

Guo, Qingyan, Rui Wang, Junliang Guo, ほか. 2024年. 「EvoPrompt: Connecting LLMs with Evolutionary Algorithms Yields Powerful Prompt Optimizers」. International Conference on Learning Representations. https://arxiv.org/abs/2309.08532.

Hu, Shengran, Cong Lu, と Jeff Clune. 2025年. 「Automated Design of Agentic Systems」. International Conference on Learning Representations. https://arxiv.org/abs/2408.08435.

Opsahl-Ong, Krista, Michael J. Ryan, Josh Purtell, ほか. 2024年. 「Optimizing Instructions and Demonstrations for Multi-Stage Language Model Programs」. Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing. https://aclanthology.org/2024.emnlp-main.525/.

Pryzant, Reid, Dan Iter, Jerry Li, Yin Lee, Chenguang Zhu, と Michael Zeng. 2023年. 「Automatic Prompt Optimization with 『Gradient Descent』 and Beam Search」. Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, 7957–68. https://doi.org/10.18653/v1/2023.emnlp-main.494.

Shang, Yu, Yu Li, Keyu Zhao, ほか. 2025年. 「AgentSquare: Automatic LLM Agent Search in Modular Design Space」. International Conference on Learning Representations. https://arxiv.org/abs/2410.06153.

Yang, Chengrun, Xuezhi Wang, Yifeng Lu, ほか. 2024年. 「Large Language Models as Optimizers」. International Conference on Learning Representations. https://arxiv.org/abs/2309.03409.

Yuksekgonul, Mert, Federico Bianchi, Joseph Boen, ほか. 2025年. 「Optimizing Generative AI by Backpropagating Language Model Feedback」. Nature 639: 609–16. https://doi.org/10.1038/s41586-025-08661-4.

Zhang, Jenny, Shengran Hu, Cong Lu, Robert Lange, と Jeff Clune. 2026年. 「Darwin Gödel Machine: Open-Ended Evolution of Self-Improving Agents」. International Conference on Learning Representations. https://arxiv.org/abs/2505.22954.

Zhang, Jiayi, Jinyu Xiang, Zhaoyang Yu, ほか. 2025年. 「AFlow: Automating Agentic Workflow Generation」. International Conference on Learning Representations. https://arxiv.org/abs/2410.10762.

Zhou, Yongchao, Andrei Ioan Muresanu, Ziwen Han, ほか. 2023年. 「Large Language Models Are Human-Level Prompt Engineers」. International Conference on Learning Representations. https://arxiv.org/abs/2211.01910.