🙌

【論文紹介】SakanaAIのShinkaEvolveを読む

に公開
paper
LLM
Agent
evolution
tech

論文：ShinkaEvolve: Towards Open-Ended And Sample-Efficient Program Evolution

リンク：https://arxiv.org/pdf/2509.19349

※ 本ページの図は特筆がない限り全て本論文から引用しています。

執筆者：EQUES 武藤 雅裕 Lead Engineering Manager

論文紹介の動機

私はEQUESでAI Agentを利用した進化計算やグラフ探索を利用したLLMアプリケーションの構想を練っているときに、この論文に出会いました。特に遺伝アルゴリズムはオープンエンドな探索として昨今注目を浴びている中で、この論文に大変興味を持ちました。

導入 / 背景：なぜこの問題が重要か

LLM を“変異器（mutation operator）”として利用し、コードやアルゴリズムを世代交代で改良していく進化的エージェントは、最適化・競技プログラミング・数理推論などで成果を出し始めています。しかし多くの既存手法はサンプル効率が低い（数千〜数万評価が必要）うえ、非公開実装が多く再現性・拡張性が課題でした。ShinkaEvolve はこの2点（効率・公開性）を正面から解決しようとします。

進化探索・自動発見系手法の可能性と課題

  • 可能性：LLM を組み合わせた進化探索は、ドメイン横断で“構造的な改良”を重ねられる（最適化、エージェント設計、学習ロス設計など）。
  • 課題：
    1. サンプル効率の悪さ（ナイーブな探索で無駄打ちが多い）
    2. 既存システムのクローズド化（再現・検証が難しい）

LLM を探索提案器として使う流れとその落とし穴

LLM による差分編集・全置換・交叉で候補プログラムを量産→評価→次世代…という流れは強力ですが、類似案の乱発やモデル選択の固定化がボトルネックになります。ShinkaEvolve はここを拒否サンプリングと動的アンサンブル制御で抑え込みます。

ShinkaEvolveの全体的な構成

1. Task Evaluator（外部評価器）

  • 役割：プログラム候補を評価する“審判”であり、ShinkaEvolveの外に存在します。
  • タスク依存の実装：
    • Circle Packing では「円の配置をシミュレートして半径総和を計算」
    • AIME 数学推論では「テスト問題を解かせて正解率を算出」
    • MoE 訓練では「モデルを数エポック訓練して損失やバランスを測定」
  • ポイント：ShinkaEvolve は評価関数を自前で持たず、タスク側からスコアを返してもらうため、汎用的にどんな最適化問題にも接続可能。

評価器のコストがボトルネックになりやすいため、ShinkaEvolve はサンプル効率を改善することで総計算量を削減しているのが特徴です。

2. LLM Offspring Generator（LLMによる子個体生成）

親プログラムをもとに LLM が子世代のプログラム（offspring）を提案します。

単なる書き換えではなく、3種類の「変異オペレータ」を備えています。

3つの変異手法

  1. 差分編集（diff-based edit）
    • 親コードの一部のみを修正し、小さな改善を狙う。
    • 安定した進化を保つために使われる局所探索的な手法。
  2. 全書き換え（full rewrite）
    • 親コード全体を再構築し、アルゴリズム構造ごと刷新する。
    • 大きな飛躍（イノベーション）を起こす役割。
  3. 交叉（crossover）
    • 2つ以上の親の部分的なロジックを組み合わせ、新しい子を作る。
    • 島モデルにおける多様性保持と知識再利用を兼ねる。

実装では、親コードの不変部分を保護する EVOLVE-BLOCK タグを用意し、不要な破壊的編集を防止しているのも特徴です。

3. Sample Parent & Context（親選択と文脈抽出）

次に、どの親プログラムを子世代生成に使うかを決めます。

ShinkaEvolve は従来の単純なランク選択ではなく、探索（exploration）と利用（exploitation）のバランスを最重要視しています。

  • Power-law Sampling：順位 rrr に対して pi∝r−αp_i \propto r^{-\alpha}pi∝r−α で確率を割り当て、上位解を優遇しつつ下位解も一定確率で残す。
  • Weighted Sampling：性能スコアと**新奇性（子孫数の逆数）**を組み合わせ、系統の多様性を維持。

さらに選ばれた親の設計方針・コメント・評価履歴などを抽出し、次の LLM 変異器に文脈として渡すことで、より情報を活かした子案生成を実現します。

4. Novelty Filtering（新奇性フィルタリング）

生成された子候補の中には、既存の個体とほぼ同じ案も多く含まれます。

これらを評価すると計算コストの無駄になるため、新奇性フィルタで事前に弾きます。

  • 第1段階：埋め込み類似度フィルタ

    コードを埋め込み空間に変換し、類似度が閾値以上なら棄却。

  • 第2段階：LLM による Novelty Judge

    類似度が閾値付近で微妙な場合は LLM に判断を委ね、意味的に新しいかどうかを確認。

これにより、無駄な評価を削減しつつ意味的にユニークなアイデアは逃さない仕組みになっています。

5. Evaluate Program（候補プログラムの評価）

新奇性フィルタを通過した候補は、改めて Task Evaluator に渡されて実行・評価されます。

  • 単一スコア（例：目的関数値）だけでなく、複数の副次的メトリクスやテキストフィードバックを記録。
  • 一部の実験では、スカラー適合度と説明的メトリクスを組み合わせる多目的評価が導入されています。

この結果は次のアーカイブ更新に反映され、親選択・バンディット報酬の計算にも利用されます。

6. Feedback Archiving（結果の保存・履歴管理）

最後に、評価結果を アーカイブ（Archive） に保存します。

ShinkaEvolve のアーカイブは 島モデル（Island Model） 構造を持ち、以下の特徴があります。

  • 各島が独立して進化を回すことで並列性と多様性を確保。
  • 定期的に優秀な個体を他の島へ移民させることで、局所最適への陥り込みを防ぐ。
  • アーカイブは単なる倉庫ではなく、親選択や新奇性判定の参照元としても活用される。

ShinkaEvolve が目指す方向性を提示

著者らは、(1) 親選択の設計、(2) コード新奇性の拒否サンプリング、(3) バンディットに基づく LLM アンサンブル選択、という3つの柱でオーダー改善のサンプル効率を実現し、汎用ベンチでの有効性とオープンソース実装を示しています。

オープンソースの実装については、第二回のブログ記事で解説予定です。

https://github.com/SakanaAI/ShinkaEvolve

ShinkaEvolve の主要アイデア（3 つの柱）

1) 親選択の工夫：探索/利用バランス（Power-law & Weighted Sampling）

Power-law : 順位 r に対し p_i \propto r^{-\alpha}。 \alpha = 0 は一様分布、 \alpha \to \inftyはヒルクライミング。

親プログラムをランクr_iに応じて選択する確率分布は

p_i = \frac{r_i^{-\alpha}}{\sum_{j=1}^n r_j^{-\alpha}}

r_i ：個体 r_i の順位（1 が最良）

α：探索／活用バランスを決めるハイパーパラメータ

Weighted：性能（シグモイド）× 新奇性（子孫数の逆数）を重み化し、良解の活用と分岐の維持を両立。

F(P_i)：個体 P_i の評価スコア
α_0：スコアの中央値

λ：シグモイドの鋭さを制御するパラメータ

N(P_i)：その親が既に生成した子個体の数（多いほど重みが下がる）

2) 変異 + 新奇性拒否サンプリング（Novelty Rejection）

  • 変異は差分編集・全書換え・交叉の3種を併用。保護区間（EVOLVE-BLOCK）で不変部を維持。
  • 埋め込み類似度で可変部を比較し、類似度が閾値超えなら却下。閾値付近は LLM を“Novelty Judge” として問い合わせ、意味的な新規性を判断しています。

3) LLM 選択の動的制御 + メタ知識活用

  • UCB1 によるバンディット制御で、各 LLM の「相対改善」に基づいて選択確率を更新。小改良より大改善を適切に評価する報酬整形（exp & ReLU）も導入。
  • Meta-Scratchpad：一定世代ごとに成功パターン/設計原則を要約し、次のプロンプトに高次の指針として注入します。図4参照。

進化ループ（Evolutionary Loop）」 の模式化

※武藤が作成

応用例と成果紹介（4領域）

領域 何をやったか 成果／工夫
Circle Packing 26円を単位正方形に非重複で配置し半径総和を最大化。 ~150評価で SOTA を発見。進化木の分岐を可視化し、スパイラル初期化→制約配慮→焼きなまし再加熱→勾配的微調整といったハイブリッド戦略が進化。図5参照。
AIME（数学推論） 10回以内の LLM 呼び出し制約下で、エージェント足場（プロンプト構造/役割分担/検証）の設計を進化。 75世代で汎化性の高い足場（専門家役割・批評・統合）を獲得。Pareto 前線で呼び出し回数×精度を最適化。
ALE-Bench（AtCoder 系） 10課題の LITE を対象に、既存 ALE-Agent を初期解として改良。 平均 約+2.3% 改善。特定課題（ahc039）で公的順位相当の大幅改善。
MoE 訓練（LBL） Mixture-of-Experts の負荷分散損失を進化（新項を含む LBL を発見）。 既存 LBL を上回る挙動。Dead expert 回避に効く安全網的項で過正則化を避けつつバランス改善。/

将来展望・研究的インパクト

  • Open-Ended 拡張：システム自身が問いを立てる方向（真のオープンエンド）。
  • 自動タスク設計・メタ学習統合：目的関数や探索戦略の自己最適化。
  • 他モデルとの統合：進化的探索 × 生成/検証モデル（Verifier・シミュレータ）連携の高度化。

まとめ：ShinkaEvolve の技術的インパクト

背景

  • LLMを用いたプログラム自動進化は有望だが、従来はサンプル効率が低く評価コストが高い。
  • ShinkaEvolve は「進化アルゴリズム＋LLM」で効率を改善し、OSSとして再現性も確保。

コア技術（3本柱）

  1. 親選択の最適化：Power-law / Weighted Samplingで上位解と多様性を両立。
  2. 新奇性フィルタ：埋め込み類似度＋LLM判定で重複案を削減。
  3. LLMアンサンブル＋Meta-Scratchpad：UCB1でモデルを切替え、成功知識を次世代へ注入。

実験成果

  • Circle Packing：150回程度でSOTA達成。
  • AIME数学推論：75世代で汎化性の高いエージェント設計を自動発見。
  • ALE-Bench競技プログラミング：平均+2.3％改善。
  • MoE訓練：新しいLBL損失を発見し精度向上。

強みと課題

  • 高いサンプル効率と汎用性、OSS公開で拡張容易。
  • ただし評価関数やハイパーパラメータはタスク依存で、LLMクエリコストは依然必要。

展望

  • Open-Ended化による自律探索、
  • 自動タスク設計・メタ学習統合、
  • 検証器・形式手法との連携でより安全で持続的な進化へ。

ShinkaEvolve は少ない試行で構造的な改善を導く“進化ループ”フレームワーク

として、ヒューリスティック探索・エージェント設計・学習戦略発見に有用です。

次回の記事では公式GitHubコードを使った実験・解説を予定しています。

おわりに

EQUESでは引き続き、「最先端の機械学習技術をあやつり社会の発展を加速する」をミッションに研究開発と社会実装に取り組んでいきます。一緒に事業を創出する仲間を募集しています。詳しくは以下をご覧ください。

https://www.wantedly.com/companies/company_6691299

Discussion