テクニカル・サマリー：SuperCoder: 大規模言語モデルを用いたアセンブリプログラムのスーパー最適化

問題定義

本論文は、プログラムの入出力挙動を厳密に維持しながら、より高速なバリアントへと変換する「スーパー最適化（superoptimization）」の課題に取り組んでいる。従来のコンパイラ（例：gcc -O3）は数十年にわたり洗練されてきたが、これらはヒューリスティックな変換ルールに依存しており、最適性を保証するものではない。既存のスーパー最適化の研究は、非常に短い直線的なアセンブリプログラム（通常2〜15命令）に限定されており、ループを含まず、CPUベースの探索ヒューリスティックを用いるためスケーラビリティに欠けていた。

本研究では、大規模でループを含むアセンブリプログラムに対して、**大規模言語モデル（LLM）**がスーパーオプティマイザとして機能するかどうかを調査している。具体的なタスクは、業界標準のコンパイラが最高レベルの最適化（gcc -O3）を行った際の出力を上回るアセンブリコードを生成することであり、これは自然言語の仕様からコードを生成するよりもはるかに困難な挑戦である。

手法

1. データセットの構築

大規模なアセンブリデータセットの不足に対処するため、著者らは8,072個のアセンブリプログラム（訓練用7,872個、評価用200個）からなる新しいベンチマークを構築した。

• ソース: 競技プログラミングの提出物からなるCodeNetコーパスから派生。
• 選択基準: 複雑さと最適化の可能性を確保するため、gcc -O0とgcc -O3の間の相対的な速度向上率が高いプログラムをサンプリングした。
• 規模: 平均プログラム長は130行であり、これは15行未満に制限されていた従来のデータセットと比較して大幅な増加である。
• 検証: 元の提出物を実行することでテストスイートを再生成し、正当性を確保した。これにより、96.2%の行カバレッジと87.3%の分岐カバレッジを達成した。

2. タスク定式化

問題は、以下の要素を持つコンテキスト・マルチアームド・バンディット問題として定式化される：

• コンテキスト ($s$): ソースCプログラム、ベースラインとなるgcc -O3のアセンブリ、および一連のテストケース。
• アクション ($a$): 候補となるアセンブリプログラムの生成。
• 目的: ベースラインの実行時間と候補の実行時間の比として定義される**速度向上（Speedup）**を最大化すること。
• 制約: 候補は有効（コンパイル可能）かつ正確（すべてのテストケースに合格）でなければならない。候補がコンパイルに失敗するか、正当性を欠く場合は、デフォルトの速度向上率1.0（ベースラインへの回帰）が割り当てられる。

3. 強化学習（RL）フレームワーク

著者らは、正当性とパフォーマンスを共にエンコードする報酬関数を最適化するために、LLMの微調整に強化学習を採用している。

• アルゴリズム: 近似ポリシー最適化（PPO）およびグループ相対ポリシー最適化（GRPO）。
• 報酬関数:
  • プログラムがコンパイルに失敗するか、いずれかのテストケースに失敗した場合、$r = 0$。
  • プログラムがすべてのテストに合格した場合、$r = \text{speedup}$。
  • この設計により、モデルはハルシネーションや誤った最適化に対してペナルティを受け、有効でより高速なコードに対してのみ報酬を受ける。
• ベースモデル: 正当性のベースラインが強力であることから、Qwen2.5-Coder-7B-Instructが微調整用に選定された。

4. 推論時テクニック

性能をさらに向上させるため、以下の手法を評価している：

• Best-of-N サンプリング: 複数の候補を生成し、すべてのテストに合格したものの中で最も高い速度向上を実現したものを選択する。
• 反復的洗練（Iterative Refinement）: コンパイルエラーやテスト失敗のフィードバックをモデルのプロンプトに再度入力し、後続の生成をガイドする。
• 教師あり微調整（SFT）: Best-of-8 サンプリングから得られた最良の候補を、LoRA微調整のグランドトゥルースとして使用する。

主な結果

ベースライン評価

著者らは、23種類の最先端LLM（GPT-4o、DeepSeek-R1、Claude-3.7、および特化したコンパイラモデルを含む）を評価した。

• 性能の差: ほとんどのモデルは苦戦し、多くは1.00×の速度向上（改善なし）しか達成できなかったか、コンパイルに失敗した。
• トップのベースライン: Claude-opus-4が、51.5%のテスト通過率とgcc -O3に対する平均**1.43×**の速度向上を達成し、最高のベースライン性能を示した。
• 失敗モード: DeepSeek-R1のようなモデルは、実行可能なコードを生成できず（コンパイル率0%）、冗長な推論を出力することが多かった。GPT-4oは高いコンパイル率（81%）を達成したが、正当性は低く（5%）、最適化を追求するあまり、低レベルの慣習（スタックカナリ、呼出規約など）を頻繁に逸脱した。

RL微調整（SuperCoder）

RLを用いてベースモデル（Qwen2.5-Coder-7B-Instruct）を微調整した結果、大幅な改善が見られた：

• 正当性: **61.4%から95.0%**に向上。
• 速度向上: **1.10×から平均1.46×**に向上。
• 比較: RLで訓練されたモデルは、プロプライエタリなClaude-opus-4ベースラインを含む、評価された他のすべてのモデルを上回った。PPOとGRPOはほぼ同一の結果をもたらした。

推論時の利得

• Best-of-N: RL訓練済みモデルにBest-of-8サンプリングを適用することで、平均速度向上率はさらに**1.93×**に上昇した。
• 反復的洗練: エラーに関するフィードバックを提供することで、すべてのモデルにおいて性能が向上し、特にRL訓練済みモデルにおいて顕著な利得が観察された。

変形（Transformations）の分析

最適化されたコードの分析により、LLMがgcc -O3を上回った9つの変形カテゴリが明らかになった：

1. ループ構造の再構成（アンローリング、順序変更）。
2. 命令選択（popcntやcmovなどの特殊なCPU命令の使用）。
3. アルゴリズムの単純化（カスタムロジックを標準ライブラリのルーチンに置き換え）。
4. スタックカナリの除去（セキュリティチェックの排除）。
5. レジスタ割り当ての改善。
6. 分岐の排除（条件付きムーブの使用）。
7. アドレス計算の最適化。
8. 関数コールの最適化。
9. 算術最適化（例：除算をシフト演算に置き換え）。

意義と主張

本論文は、業界標準のコンパイラによって既に最適化されたアセンブリプログラムに対して、LLMをスーパーオプティマイザとして適用することに成功した最初の事例であると主張している。その主な貢献は以下の通りである：

1. 新しいベンチマーク: 従来のスーパー最適化研究のトイ・エグザンプルを超えた、大規模で現実的なデータセット（8,072プログラム、平均130行）の導入。
2. パフォーマンスのためのRL: 正当性と速度向上を明示的に統合した報酬関数を用いることで、強化学習がコードのパフォーマンス最適化に極めて有効であり、標準的な教師あり微調整やプロンプティング戦略を凌駕することを実証した。
3. 実現可能性: LLMが、標準的なコンパイラのヒューリスティックが見逃すパフォーマンス向上の発見が可能であることを確立し、gcc -O3に対して最大1.46×（Best-of-Nサンプリングでは最大1.93×）の速度向上を達成した。

著者らは、本研究を、従来のコンパイラ・ヒューリスティックの限界を超えたプログラム・パフォーマンス最適化の将来研究のための基礎として位置づけている。