技術要約：LLM支援型アルゴリズム発見のための対照的概念ツリー探索（CCTS）

問題提起

大規模言語モデル（LLM）によるアルゴリズム発見は、LLMが候補となるプログラムを提案し、外部の評価器がタスクへのフィードバックを提供する、反復的なブラックボックス最適化プロセスとして機能する。近年のパラダイム（例：FunSearch、AlphaEvolve）は、組合せ問題（Erdős型の問題など）に対して解の再発見や改善に成功しているが、これらは主に適合度（fitness）に基づいた進化的な更新に依存している。これらの既存システムにおいて、親の選択はプログラムの生のパフォーマンス（適合度）によって決定され、探索はパフォーマンス順に並べられたプログラムの系譜の上を歩む形で進行する。

このアプローチの決定的な限界は、プログラム空間が弱く構造化されたままであることである。LLMによって制約されている場合でも、生成されたアルゴリズムには、探索アルゴリズムが活用できるような明確な局所性、滑らかな変化、あるいは構成的構造が欠けていることが多い。その結果、ガイダンスは、アルゴリズムのどの意味論的コンポーネントが実際に有用であるかという明示的に学習された理解からではなく、主に生の適合度信号とLLMの暗黙的な事前知識から導出される。本論文は、探索の効率性と解釈性を向上させるために、プログラム空間のLLM内部表現をいかに最大限に活用できるかという未解決の問いに取り組むものである。

手法：対照的概念ツリー探索（CCTS）

著者らは、探索のガイダンスを生の適合度から、学習された階層的な意味的概念空間へとシフトさせるフレームワークである**対照的概念ツリー探索（Contrastive Concept-Tree Search: CCTS）**を導入する。核心となる仮説は、アルゴリズムは、ノードが概念を表し、エッジが洗練または特化をエンコードする階層構造として組織化された、潜在的な意味的概念空間によって記述できるというものである。

1. 概念表現とツリー構築

• 特徴抽出: 各候補プログラム $x$ は、LLMに適切な概念のリストを生成させるプロンプトを用いることで、意味的特徴表現 $b = \Phi(x)$ にマッピングされる。
• 階層構造: これらの概念は、根を持つ概念ツリーに組織化される。概念ベクトル $b$ は、活性化が祖先閉鎖的（ある子概念の活性化は、そのすべての祖先の活性化を意味する）であるインジケーターベクトルである。このツリーは動的であり、探索中に新しい概念が発見されるにつれて成長する。

2. 概念の有用性の対照学習

CCTSは、単にプログラムの適合度スコアのみに基づいて親を選択するのではなく、どの概念が経験的に高いパフォーマンスに関連しているかを対照的なアプローチを通じて学習する。

• 分割: 評価されたアーカイブを、パフォーマンスの閾値 $\tau_t$ に基づいて、「良」 ($y_i \ge \tau_t$) と「悪」 ($y_i < \tau_t$) のサブセットに分割する。
• モデル適合: 「良」および「悪」のそれぞれの特徴分布に対して、2つの確率モデル $\hat{p}_{\eta^+}(b)$ および $\hat{p}_{\eta^-}(b)$ を適合させる。著者らは、階層的なベルヌーイモデルを用いた**ツリー構造のパレンゼン・エスティメータ（TPE）**スタイルの手法を利用している。このモデルは、階層内の親に対する条件付き独立性を仮定している。
• 尤度比スコアリング: 各プログラムに対して、尤度比スコア（対数概念有用性）が計算される：
  $$\log w(b) = \log \hat{p}_{\eta^+}(b) - \log \hat{p}_{\eta^-}(b)$$
  このスコアは、特定の概念の組み合わせが、高パフォーマンスの解と低パフォーマンスの解をどの程度強く区別するかを定量化する。

3. 親の選択と探索ダイナミクス

• バイアス付きサンプリング: アーカイブから、尤度比スコアに比例した確率で親が選択される。これにより、探索は、改善と経験的に関連付けられている概念の組み合わせを含むプログラムへと偏向される。
• 探索メカニズム: 早期収束を防ぎ、新しい概念の発見を促進するために、CCTSは軽量な探索メカニズムを組み込んでいる。これには以下が含まれる：
  • ベータ事前分布: 新しく発見された概念がゼロの確率にならないよう、カウントを平滑化する。
  • 新規性バイアス: 頻繁に試行された概念の重みを下げ、探索されていない領域を優先する。
  • 混合戦略: 搾取（学習された対照モデルに基づく）と探索（新規性に基づく）の混合が、子生成のためのLLMへのプロンプトに注入する概念の選択をガイドする。

主な貢献

1. 明示的な意味構造: 本論文は、標準的な進化アルゴリズムで使用される非構造化プログラム空間を超え、階層的な概念ツリーを学習することで、アルゴリズム空間の潜在的な構造を明示的にすることを提案している。
2. 対照的ガイダンス: 単にどのプログラムが最も優れたパフォーマンスを示すかを追跡するのではなく、どの概念を優先すべきか、そして極めて重要なことに、どの概念を避けるべきかを学習する、対照的な統計的フレームメントを導入している。
3. 解釈可能性: 本手法は、探索中に探索された意味的構造を明らかにする、解釈可能なタスク固有の概念ツリーを生成し、発見されているアルゴリズム戦略への洞察を提供する。
4. 合成検証: 著者らは、「教師」概念ツリーと真の有用性を持つ制御された合成環境を構築した。これにより、CCTSが基礎となる意味構造を回復すること、および観察された探索ダイナミクスが特定のLLMのアーティファクトではなく、概念の有用性の学習によって駆動されていることを検証できる。

実験結果

著者らは、円充填（circle packing）、算術カケヤ予想（Arithmetic Kakeya conjecture）、ハイロンの三角形問題（Heilbronn's triangle problem）、正方形の中の正方形（squares-in-square）問題を含む、オープンなErdős型の組合せ問題のベンチマークでCCTSを評価した。

• 性能向上: CCTSは、複数のタスクにおいて、ベースライン戦略（Uniform、Greedy、および $k$-elite選択）と比較して、一貫して高いスコアとより速い改善を達成した。
• 改善のメカニズム: 分析により、性能向上は主にどの概念を避けるべきかを学習することによって駆動されていることが明らかになった。成功した実行は、失敗した実行と同様の高有用性概念のセットを特定したが、低有用性（有害な）概念を抑制する能力が著しく高いことを示した。これは、CCTSが、LLMの初期の事前知識による誤解を招く相関関係によって引き起こされる不生産的な探索を減少させることで、探索を安定させていることを示唆している。
• 合成検証: 合成環境において、学習された概念の有用性は、真の教師有用性と強い相関（$r=0.94$）を示し、本手法が意味のある表現を効果的に回復していることを裏付けた。
• 構造依存性: 探索と搾取の最適なバランスは、基礎となる概念ツリーの構造（例：分岐比）に依存することが判明した。これは、探索戦略が問題空間のトポロジーに適応すべきであることを示唆している。

意義と主張

本論文は、CCTSが現在のLLM支援型アルゴリズム発見における根本的な不一致に対処していると主張している。すなわち、高スコアのアルゴリズムが必ずしも強力な子孫を生成するわけではないのは、構造化が弱い空間では適合度が進化可能性（evolvability）の優れた代理指標にならないためである。探索を生の適合度から改善のセマンティックな証拠へとシフトさせることで、CCTSは、距離、再結合、および探索方向が意味を持つ概念空間において探索を行うことを可能にする。

著者らは、本研究を、より信頼性が高くスケーラブルなアルゴリズム発見に向けた方法論的な進歩として位置づけている。彼らは、現在の結果が特定のベンチマークにおけるベースラインに対する相対的な改善を示していることを認めつつも、主要な貢献は、明示的で人間と互換性のある意味的概念構造がいかに自動発見をより透明で、制御可能で、効率的にできるかを示すことにあると強調している。この研究は、将来のシステムが、ブラックボックス的な適合度信号だけに頼るのではなく、潜在的な意味的階層を学習し、活用することに焦点を当てるべきであることを示唆している。