自己改善エージェントを多腕バンディットで解く ― Huxley-Gödel Machine を読む

TL;DR

• Huxley-Gödel Machine（HGM） は、自分自身のコードを書き換えて強くなる「自己改善コーディングエージェント」の研究である。
• 先行研究のDarwin Gödel Machine（DGM）は「ベンチマークスコアの高いエージェントを優先して改変する」戦略を取るが、これは Metaproductivity-Performance Mismatch（短期の性能と、長期の自己改善能力のズレ）を見落とす。
• HGMは自己改善を ツリー探索＝無限腕バンディット問題 として定式化し、個体スコアではなく CMP（Clade-Metaproductivity、子孫まで含めた系統の到達能力） を基準にノードを選ぶ。
• ノード選択には Thompson Sampling と UCB-Air を組み合わせ、SWE-bench Verified / Polyglotで人間レベルのコーディング性能を達成した。
• この記事では、論文のキモである「性能の罠」を体感できるインタラクティブな可視化を用意した。

背景：自己改善エージェントと「性能の罠」

LLMエージェントが自分のコードを書き換えてより賢くなる、という自己改善（self-improvement）の系譜があります。HGMを理解するには、まずこの系譜の前提と限界を押さえておきたいところです。

Gödel Machine ― 理論的に最適だが実装できない

オリジナルの Gödel Machine（Schmidhuber, 2003）は、「期待長期効用を確実に増加させると 証明できた 場合に限り、自分自身を書き換える」という原則に基づく自己改善機械です。証明という保証があるため理論的には最適ですが、現実の問題で改変の効果を形式的に証明するのは難しく、そのままでは実装できません。

Darwin Gödel Machine / SICA ― 高スコア偏重という近似

そこで近年のDGMやSICAは、証明の代わりに 経験的なベンチマークスコア を頼りにします。具体的には、エージェントのアーカイブを保持し、「ベンチマークスコアの高いエージェントから優先的に自己改変を試す」という進化的な探索をします。証明は要らず実用的ですが、ここに落とし穴があります。

Metaproductivity-Performance Mismatch とは

問題は、いまのスコアが高いことと、そのエージェントが将来どれだけ強い子孫を生めるかは別物 だという点にあります。論文はこれを Metaproductivity-Performance Mismatch と呼びます。

• スコアの高いエージェントが、改変してもなかなか伸びない（生産性の低い）子孫しか生まないことがある。
• 逆に、いまはスコアが低いエージェントが、改変を重ねると一気に化ける有望な系統の起点になることがある。

DGMのように「いま高い個体」だけを追いかけると、後者のような有望だが地味な系統を取り逃します。これが「性能の罠」です。HGMの貢献は、この罠を 定量化 し、それを避ける選択基準を与えたことにあります。

自己改善を多腕バンディットとして定式化する

HGMはまず、自己改善のプロセスをツリー探索として整理します。

アーカイブ・アクション空間・ポリシー

反復 $t$ におけるエージェントのアーカイブ（探索木）を $\mathcal{T}_t$ とします。各反復でポリシー $\pi$ は、次のどちらかのアクションを選びます。

• $\mathcal{M}_t = \{ m_a : a \in \mathcal{T}_t \}$ … 既存エージェント $a$ を 改変（expand） して新しい子ノードを作る。
• $\mathcal{V}_t = \{ v_a \}$ … 既存エージェント $a$ を 追加評価（evaluate） して、そのスコア推定を精密化する。

つまり「新しい枝を伸ばす」か「いまある枝の良し悪しを見極める」かを毎ステップ選ぶ構造になっています。

なぜ「無限腕バンディット」なのか

この選択は多腕バンディットそのものです。各エージェントが「腕」で、改変・評価が「腕を引く」行為にあたります。ただし改変によって新しいエージェント（＝新しい腕）がいくらでも増えるため、腕の数が固定されない 無限腕バンディット（infinite-armed bandit） になります。

ここでのトレードオフは、バンディットの王道である探索と活用の対立そのものです。

• 活用（evaluate）: いま有望に見えるエージェントを評価して、確信を深める方向。
• 探索（expand）: まだ見ぬ子孫を作りに行く方向。

古典的バンディットポリシーの整理

HGMの選択則を読む前に、土台となる古典的なバンディットポリシーを簡単に整理しておきます。腕 $a$ の推定報酬を $\hat{\mu}_a$、選択回数を $n_a$、総ステップを $t$ とします。

• $\varepsilon$-greedy: 確率 $1-\varepsilon$ で $\arg\max_a \hat{\mu}_a$ を選び、確率 $\varepsilon$ でランダムに探索する。単純だが探索が無方向になりやすい。
• UCB1: 不確実性を上積みした上限 $\hat{\mu}_a + \sqrt{\frac{2 \ln t}{n_a}}$ が最大の腕を選ぶ。「あまり引いていない腕」ほどボーナスが大きく、原理に基づいて探索する。
• Thompson Sampling: 各腕の報酬分布を事後分布として持ち、そこから1サンプルを引いて最大の腕を選ぶ。ベルヌーイ報酬なら事後分布は $\mathrm{Beta}(1 + \text{成功}, 1 + \text{失敗})$ になる。

HGMはこのうちThompson SamplingとUCB系の発想を、後述するように使い分けます。

CMP：系統（clade）で測る自己改善能力

ここからが本題です。HGMは「個体のスコア」ではなく「系統の到達能力」でエージェントを評価します。

GMP と CMP の定義

まず比較対象として、最終的に選ぶエージェントの効用そのものを測る Global Metaproductivity（GMP） を定義します。$\mathcal{T}_B$ は予算 $B$ を使い切ったときの最終的な探索木、$U(\cdot)$ は効用（最終的なベンチマーク性能）です。

HGMが実際に使うのは CMP（Clade-Metaproductivity） です。$C(\mathcal{T}_B, a)$ は「エージェント $a$ とその全子孫」、すなわち clade（系統） を指します。

ポイントは $\max_{a' \in C(\mathcal{T}_B, a)}$ の部分です。エージェント $a$ 自身のスコアではなく、$a$ に投資し続けたときに、その系統全体から最終的に得られる最良のエージェントの性能 を評価しています。DGMの「いまの個体スコア」とは見ている対象が根本的に違います。

推定器

もちろん未来の子孫の性能は事前にはわかりません。そこでHGMは、clade内で蓄積した成功・失敗の試行回数からCMPを推定します。

ここで $n^{C}_{\mathrm{success}}(a) = \sum_{a' \in C(a)} n_{\mathrm{success}}(a')$ のように、成功・失敗のカウントを clade 全体で合算 します。子孫がベンチマークを解けば、その手柄は祖先にも遡って加算される、という直感です。これにより「いまは弱いが有望な子孫を生んだ祖先」が正しく高く評価されます。

論文のTable 1では、DGM/SICAが使う推定器と経験的CMPの相関が0.28〜0.44と弱いのに対し、HGMの推定器は0.51〜0.78を達成しており、Mismatchを実際に緩和できていることが示されています。

インタラクティブに体感する：CMP vs 個体スコア

言葉だけだとピンと来づらいので、実際に触れる図を用意しました。自己改善ツリー上で、各エージェントの 個体スコア $U$（DGMが見る値）と、clade の最良到達点 CMP（HGMが推定する値）を対比しています。

• 青い点線のリング … DGM流（個体スコア最大 のノードを選ぶ）
• 橙の実線のリング … HGM流（CMP 最大 のノードを選ぶ）
• 薄いノード … 投資して初めて現れる子孫（決定時には見えない潜在的な到達点）

ノードをクリックするとスコアを編集できます。DGM流とHGM流が別々のノードを選び、最終的な到達点に差（リグレット）が生まれる様子を確かめてみてください。

「Mismatchシナリオ」では、高スコアの $B$（$U=0.80$）に投資するDGM流が頭打ちになる一方、一見弱い $C$（$U=0.25$）に投資するHGM流は、子孫 $C2$（$U=0.95$）という当たりを引き当てます。性能だけを見ると、最も有望な系統を取り逃してしまうわけです。スコアを動かして「整合シナリオ」と見比べると、Mismatchが常に起きるわけではなく、両者がズレる構造があるときにこそCMPが効く、という点も見えてきます。

HGM のポリシー設計

CMPという指標が決まれば、あとはそれを使って探索木を効率よく育てるだけです。HGMは3つのポリシーを組み合わせます。$\tau$ はスケーリング係数です。

拡張ポリシー：clade の Beta 分布による Thompson Sampling

どのエージェントを 改変（expand） するかは、cladeのカウントに基づくBeta分布からのThompson Samplingで決めます。cladeの成功・失敗を使うので、CMPの高い系統が選ばれやすくなります。

評価ポリシー：個体の Beta 分布による Thompson Sampling

どのエージェントを 追加評価（evaluate） するかは、cladeではなく 個体 の成功・失敗を使います。個々のエージェントのスコア推定を精密化するのが目的なので、こちらは個体の統計が適切です。

選択ポリシー：拡張するか評価するか

新しい枝を伸ばす（expand）か、既存の枝を見極める（evaluate）かは、無限腕バンディットの定石である UCB-Air に従って決めます。具体的には、これまでの拡張回数 $N_t^{\alpha}$ がアーカイブのサイズ $|\mathcal{T}_t|$ 以上になったら拡張します（$\alpha = 0.6$）。

アーカイブが大きくなるほど新規探索のペースを抑え、いまある腕の評価に資源を回す、というバランスを取っています。

最終エージェント選択

予算を使い切ったあと、最終的にどのエージェントを成果物として返すか。この段階で見るのは、cladeの統計ではなく個体の信頼度です。正規化不完全ベータ関数 $I_\epsilon$ を使い、スコアの上側 $\epsilon$ パーセンタイル信頼度が最大のエージェントを選びます。

探索中は「化けそうな系統」をCMPで攻めつつ、最後の納品では「確実に強い個体」を保守的に選ぶ、という役割分担になっています。

理論的裏付け：CMP オラクルと Gödel Machine

HGMは単なるヒューリスティクスではなく、理論的な裏付けを持ちます。論文のTheorem 1は、ある仮定（Assumption 1）の下で 「CMP のオラクルにアクセスできれば、それは Gödel Machine を実装するのに十分である」 ことを示しています。

直感的には、CMPは「この系統に投資し続けたとき到達できる最良性能」だから、CMPが最大のノードを選び続ければ、原理的には最適な自己改善経路をたどれます。HGMはこのオラクルをcladeレベルの統計で近似することで、実装不可能だったGödel Machineに現実的な形で迫っている、という構図です。名前の由来（進化を強調するDarwinに対し、HGMはハクスリーを冠する）もここにあります。

成果と所感

HGMはSWE-bench VerifiedとPolyglotの両ベンチマークで従来手法を上回り、人間レベルのコーディング性能を達成しました。さらに、得られたエージェントが他のコーディングデータセットへもうまく転移したと報告されています。

個人的に面白いと感じたのは、「目の前のスコアを最大化する」という一見まっとうな戦略が、自己改善という多段の文脈では局所最適に陥る、という指摘です。これは強化学習における近視眼的な貪欲方策の失敗とまったく同じ構図で、それを「個体ではなくcladeを信用割り当ての単位にする」という発想で解いている点が鮮やかです。子孫の成功を祖先に遡って加算するCMPの推定器は、モンテカルロ木探索（MCTS）の価値バックアップを系統樹に一般化したものとも読めます。

一方で、CMPの推定はあくまで蓄積した試行回数に依存するため、探索初期のサンプルが乏しい段階での推定の不安定さや、計算コスト（多数のエージェント候補を評価し続ける必要がある）は、実運用では効いてきそうです。このあたりは元論文の実験設定を当たってみたいところです。

終わりに

HGMは「自己改善エージェントの探索を、無限腕バンディット上のclade単位の信用割り当て問題として定式化する」という、問題の捉え直しが本質の研究でした。多腕バンディットやMCTSに馴染みがある人ほど、CMPの発想はすっと入ってくると思います。

この記事の可視化は、論文Figure 1が伝えたい「性能の罠」を手元で動かして確かめられるよう、自前のSVGで実装しました。スコアを動かして、DGM流とHGM流の選択が分かれる構造を体感してもらえたら幸いです。

• 論文: Huxley-Gödel Machine: Human-Level Coding Agent Development by an Approximation of the Optimal Self-Improving Machine（arXiv:2510.21614）