🤖 machine learning

LLM Program Optimization via Retrieval Augmented Search

本論文では、LLMが生成する自然言語による記述とアトミックな編集を活用することで、C++およびPythonプログラムの最適化において最先端の戦略を大幅に上回り、かつ解釈性を高め、コードの変更を最小限に抑える、新規のブラックボックス適応手法であるRetrieval Augmented Search (RAS) および AEGIS を導入する。

原著者： Sagnik Anupam, Alexander Shypula, Osbert Bastani

公開日 2026-06-25

📖 1 分で読めます☕ さくっと読める

CC BY 4.0

原著者： Sagnik Anupam, Alexander Shypula, Osbert Bastani

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

非常に才能はあるが経験の浅いシェフ（大規模言語モデル、以下LLM）が、料理を作ろうとしている場面を想像してください。目標は、単に料理を美味しくすることではなく、味を変えずに、より「速く」調理することです。

この論文は、このシェフがより賢く働くための2つの新しい方法を提示しています。それは、「過去のレシピのライブラリ」（低速なコードと高速なコードのデータセット）を用いて、シェフを導くというものです。

問題点：シェフが行き詰まっている

通常、もしシェフにレシピを高速化するよう頼んだとしても、シェフはランダムに推測したり、一度にすべてを書き換えようとしたりします。彼らが失敗するのは、どのようにすれば速くなるのかという具体的な「コツ」を十分に見てこなかったからです。彼らには、具体的なテクニックを教えるコーチが必要です。

手法1：RAS (Retrieval Augmented Search / 検索拡張探索)

比喩：「スマートな司書」 vs 「キーワード検索」

シェフがインスピレーションを得るために、膨大なライブラリから似たようなレシピを見つける必要があると想像してください。

従来の方法 (Code Retrieval / コード検索): シェフは現在の料理の「材料リスト」（実際のコード）を見て、ライブラリの中から似たような材料を持つレシピを探します。これは、「小麦粉と卵」で検索して、実際にはスープのレシピが必要なのに、たまたま小麦粉を使っているケーキのレシピが返ってくるようなものです。あまりにも字義通りすぎます。
新しい方法 (Contextual Retrieval / 文脈的検索): シェフはまず、司書にその料理の「要約」を書かせます（例：「これは野菜の風味を引き出すために煮込むスープである」）。その後、司書は特定の材料に関係なく、その料理と「同じことをしている」他の料理をライブラリから探します。
- なぜ機能するか: 特定の材料が同じものを見つけるのではなく、同じ「問題」を解決しているレシピを見つけ出すからです。

探索プロセス (Beam Search / ビームサーチ):
レシピを一度の大きな飛躍で修正させるのではなく、RASはそれを細分化します。

シェフが小さな改善を行う。
司書が、その「新しいバージョン」に基づいた、より関連性の高い新しい例を見つける。
シェフはその新しい例を用いながら、再度試行する。
これを繰り返すことで、まるで山を一段ずつ登るように、常に最も早く登れる経路を選び取っていきます。

結果: この手法により、C++プログラムは従来の最良の手法よりも最大2倍速くなり、Pythonプログラムの速度も大幅に向上しました。

手法2：AEGIS (Atomic Edit Guided Search / アトミック編集による誘導探索)

比喩：「レゴマスター」 vs 「解体作業員」

スマートな司書がいても、シェフは依然としてレシピに対して、非常に大きく混乱を招くような変更（例えば、調理法そのものを丸ごと入れ替えるなど）をしてしまうかもしれません。これは理解しにくく、リスクが高いものです。

AEGISは、ライブラリそのものを変えます。単なる「低速なレシピ vs 高速なレシピ」のペアを保存するのではなく、それらを**アトミックな編集（最小単位の編集）**へと分解します。

プロセス: システムは低速なレシピと高速なレシピを取り上げ、専門家にその違いを極めて小さなステップごとに説明させます。
- ステップ1: 「木のスプーンから金属のスプーンに替える（熱伝導を速めるため）」。
- *ステップ2:キノコを細かく刻む（調理時間を短縮する）」。
- *ステップ3: 蒸気を閉じ込めるために蓋を使う」。
汎用化: そして、これらのステップを一般的なルール（例：「高温では金属製の道具を使う」）へと書き換えます。これにより、特定の料理だけでなく、あらゆるレシピに適用できるようになります。

どのように役立つか: シェフが新しい料理を最適化する必要があるとき、システムは「ここに新しいレシピがあります」と言うのではありません。「ここに、特定の小さなコツがあります：『金属のスプーンに替える』。これを試してください」と言うのです。シェフはその小さなコツを一つ適用し、結果を確認し、次のステップへ進みます。

結果:

変更をより小さく、理解しやすくします（城を再構築するのではなく、レゴのブロックを一つ入れ替えるようなものです）。
前述の手法と比較して、変更のサイズを17%から30%削減しました。
プログラムを高速化する能力については、最初の手法よりはわずかに劣るものの、より高い制御性と明快さを実現しました。

結果のまとめ

RASは、一連の賢明かつ情報に基づいたステップを通じてあなたを導き、より高速なプログラムへの最善の経路を見つけ出す「スマートなコーチ」のようなものです。これは、C++において従来の手法を2倍上回り、Pythonの速度を平均で**10%**向上させました。
AEGISは、問題を小さな、扱いやすいレゴブロックへと分解してくれる「コーチ」のようなものです。これは、効率性の面で1.37倍優れたものとし、変更をより小さく安全なものにすることで、高速化を図る過程でプログラムが壊れないように保証します。

要するに、AIのコードを高速化するためには、単に「推測」させるのではなく、コードの「物語」を理解する司書（文脈的検索）を与え、小さく安全な改善を一つずつ行うための、具体的で微細なツール（アトミック編集）を与えるべきである、ということをこの論文は教えてくれます。

技術要約：検索拡張探索によるLLMプログラム最適化

問題提起

大規模言語モデル（LLM）はコード生成において顕著な可能性を示しているが、プログラムの最適化については、そのままでは苦戦する。従来の学習データセットにはプログラムの性能に関するデータが不足しており、直接的な適応が困難である。近年の研究（Shypulaら、2024年）は、「性能向上エディット（PIE）」ベンチマークを導入し、動的なコード検索（コード埋め込みの類似性に基づいて低速・高速なプログラムのペアを検索すること）が性能を向上させることを示した。しかし、既存のアプローチは依然として「エンドツーエンド」である。それらは、少数の例に基づき、LLMに対してプログラムの最適化されたバージョンを直接出力させるものである。これは、一連の増分的なパスを通じてプログラムを系統的に修正する現代のコンパイラとは対照的である。さらに、エンドツーエンドのアプローチは、しばしば大規模で解釈が困難な変更を生み出す。

手法

本論文は、これらの限界に対処するために、主に2つの手法、Retrieval Augmented Search (RAS) と Atomic Edit GuIded Search (AEGIS) を提案している。

1. Retrieval Augmented Search (RAS)

RASは、候補となる最適化案に対してビームサーチを実行するブラックボックス適応手法であり、動的な検索を改善するための2つの重要な洞察を統合している。

コンテキスト化された検索 (Contextual Retrieval): 生のソースコードに基づいて例を検索するのではなく、RASはLLM ( $F_{context}$ ) を使用して、プログラムの核心となるアルゴリズムとデータ構造の自然言語による記述を生成する。この記述は、最も関連性の高い低速・高速な学習ペアを検索するために埋め込み（ $\psi$ ）として使用される。著者らは、この抽象化により、システムが表面的な構文上の類似性ではなく、「意図」と「ロジック」に基づいて例を検索できると仮定している。
反復的ビームサーチ (Iterative Beam Search): 固定された例のセットを一度だけ取得するのではなく、RASは「検索・最適化・評価」のループを実行する。各ステップ $i$ において、現在のプログラム $p_{i-1}$ が与えられると、システムは（コンテキスト化された埋め込みに基づき）最も類似した上位 $k$ 個の学習ペアを検索する。その後、LLM ( $F_{opt}$ ) が $k$ 個の候補となる最適化案を生成する。システムは最も高速で正しいプログラムを $p_i$ として選択し、このプロセスを $m$ ステップ繰り返す。

2. Atomic Edit GuIded Search (AEGIS)

大規模でモノリシックな変更という解釈性の問題に対処するため、AEGISは学習例を「アトミックなエディット（原子的な編集）」へと分解する前処理を導入している。

分解 (Decomposition): LLM ( $F_{decomp}$ ) は、低速・高速なプログラムのペア $(p, p')$ を分析し、その変換を、特定の増分的な変更とその性能上の根拠を説明する一連の自然言語記述 $[s_1, ..., s_r]$ へと分解する。
生成と一般化 (Generation and Generalization): システムは、各記述 $s_i$ を低速なプログラムに順次適用して中間プログラムを生成するために、LLM ( $F_{edit}$ ) を使用する。次に、一般化LLM ( $F_{gen}$ ) が、各特定の編集記述を、より幅広いプログラムに適用可能な一般的な「アトミックなエディット」 $e_i$ へと書き換える。
アトミックなエディットによる探索 (Search with Atomic Edits): 得られるデータセット $\Pi_{atomic}$ は、タプル $(e_i, (p_{i-1}, p_i))$ で構成される。その後、RASがこのデータセットに対して実行される。検索ステップでは最も関連するアトミックなエディットが見つけられ、LLMはその特定の増分的なエディットを現在のプログラムに適用するように促される。これにより、最適化プロセスをより増分的かつ解釈可能に強制する。

主な貢献

コンテキスト化された検索の優位性: 本論文は、LLMによって生成された自然言語の記述に基づいて例を検索することが、生のソースコードの埋め込みに基づく検索よりも大幅に優れた性能を示すことを実証している。これは、アルゴリズムの意図を抽象化することが、効果的なフューショット学習において極めて重要であることを示唆している。
RASフレームワーク: 著者らは、コンテキスト化された検索と反復的ビームサーチを組み合わせたRASを提案している。このアプローチは、最適化を単一ステップの生成タスクではなく、逐次的な探索問題として扱う。
解釈性のためのAEGIS: 本論文は、学習データをアトミックで一般化可能なエディットへと蒸留する手法であるAEGISを導入している。これにより、大幅な性能低下を招くことなく、より小さく解釈可能なステップで最適化を行うことが可能になる。
包括的な評価: これらの手法は、動的検索、指示のみのプロンプティング、および人間によるパフォーマンスを含む最先端のベースラインと比較して、PIEベンチマーク（C++）およびMercuryベンチマーク（Python）で評価されている。

結果

C++ 最適化 (PIE ベンチマーク)

RASの性能: Qwen3-Coderを使用した場合、RASは平均 8.70倍 の高速化を達成した。これは、以前の最先端である動的検索ベースラインの 4.23倍 に対し、2.06倍 の向上である。
AEGISの性能: GPT-4oを使用したAEGISは、平均 6.08倍 の高速化を達成した。特定のモデルを用いたフルRASによる高速化にはわずかに及ばないものの、AEGISは大幅に小さなエディットを生成した。
エディットサイズ: AEGISは、RAS（GPT-4o使用）と比較して平均エディットサイズ（編集距離で測定）を 17% 削減し、探索プロセスの最初のエディットのみを考慮した場合では 30% 削減した。
正確性: GPT-4oを用いた実験において、RASは 99.5% の正確性（すべてのテストケースを通過するプログラム）を維持した一方、AEGISは 100% を達成した。DeepSeek 3.2の出力のサブセットに対してCBMCを用いた形式検証を行った結果、10件中8件で意味的な等価性が確認され、残りの2件は改行などの軽微なフォーマットの違いのみであった。

Python 最適化 (Mercury ベンチマーク)

Qwen2.5-7B-Instructを用いたRASを使用した場合、平均実行時間パーセンタイル指標（Beyond@1）はベースラインと比較して 10.27 改善し、このモデルとより大規模な推論モデルとの間の性能差を大幅に縮小させた。

重要性と主張

本論文は、プログラムの最適化を増分的なステップに分解することで、LLMのプログラム最適化能力が大幅に向上することを主張している。著者らは、コンテキスト化された検索（自然言語による記述の使用）が、コードベースの検索を凌駕するための決定的な要因であることを強調している。さらに、AEGIS は、大幅な性能向上を犠牲にすることなく、増分的な変更を強制することで、LLMによる最適化をより解釈可能かつ安全にするための実行可能な道筋を提供すると主張している。本研究は、これらのブラックボックス適応戦略を、既存の低速・高速なペアの学習データセットを活用してプログラム最適化における最先端の結果を達成できる、ファインチューニングに代わる実用的な代替手段として位置づけている。