日本ソフトウェア科学会第 41 回大会 (2024 年度) 講演論文集∗

大規模言語モデルを用いたコード最適化の実用化に向けて
奥田 勝己, Saman Amarasinghe
大規模言語モデルは，コード最適化を含む様々なコーディングタスクにおいて有望である．しかし，生成された最適化コードにはしばしば誤りや性能の低下が見られることが実用化における障壁となっている．そこで，本論文では，環境からのフィードバックを用いてこの問題を解決するフィードバックループを備えたコード最適化フレームワークを提案する．本フレームワークでは，最適化済みのコードを実際に実行した結果を反復的にフィードバックとして利用し，正確かつ高性能なコードの生成を実現する．提案フレームワークを，コード生成ベンチマークである
HumanEval で実験し，最適化前後の比較で計算量の削減を伴う大幅な高速化を確認した．

点である．LLM は，様々な最適化のテクニックに関

1 はじめにする知識を有している．しかし，それらを適切に適用大規模言語モデル（LLM）は，プロンプトを介しできない場合がある．LLM はコンパイラが持つようて様々なタスクを実行することができる．プログラミなコストモデルを持たない．このため，LLM が最適ングタスクもその例外ではなく，コード生成 [1] やテ化したコードは，最適化されていないコードよりも遅スト生成 [4] などにも LLM は有用である．また，コーくなることがある．

ド生成の能力を応用したコードの最適化もその 1 つ

そこで，本研究ではこれらの問題を解決することをである．最適化されていないコードをプロンプトの目的としたコード最適化フレームワークを提案する．

一部として LLM に与えることで，LLM はコードを本フレームワークでは，事前に最適化前コードから最適化することができる．このため，LLM を用いてテストケースを生成し，最適化後コードを検証する．

コードの実行速度を向上させることが期待される．

このとき，テストケースの生成を行うのも LLM であしかし，現状の LLM を用いたコード最適化にはる．正しいテストケースが得られるまで，LLM 自体2 つの問題がある．1 つ目の問題は，LLM が生成すにテストケースを修正させることで，テストケースのるコードは常に正しいとは限らない点である．LLM品質を向上させる．また，テストカバレッジを LLMが最適化したコードは，構文エラーや意味エラーをにフィードバックすることで，最適化前コードを網羅含む場合がある．また，これらのエラーがなくても，するテストケースを生成する．

LLM が生成するコードが元のコードとは異なる振る

本フレームワークでは，生成済みのテストケースを舞いをする場合がある．2 つ目の問題は，LLM が最用いることで，機能的および性能的に最適化後コード適化したコードの性能が向上しているとは限らないを検証する．テストが通らなかった場合，テストの結果を LLM にフィードバックすることで，テストをパ∗ This is an unrefereed paper.

Copyrights belong tothe Authors.
Katsumi Okuda, マサチューセッツ工科大学 / 三菱電機株式会社, MIT / Mitsubishi Electric Corporation.
Saman Amarasinghe, マサチューセッツ工科大学, MIT.

スするコードを生成する．また，テスト実行時の性能情報を LLM にフィードバックすることで，LLM にコードの性能を改善させる．
提案フレームワークによる実験では，コード生

成用ベンチマークである HumanEval [1] に含まれる
1Python の関数を最適化し，性能向上率を測定した． 2
その結果，モデルに gpt-4o-mini を使用した場合で平34均 24.6 倍の速度向上を確認した．

52 LLM を用いたコードの最適化とその課題

def search ( arr , target ):for i in range ( len ( arr )):if arr [ i ] == target :return i
return -1

図1

最適化前コード（線形探索）

LLM はコード生成やテスト生成を行うことができる．インターネット上の膨大なデータで学習された

LLM は，さまざまな最適化のテクニックを知識とし12て有する．このため，適切なプロンプトを LLM に与3えることで，コードの最適化が可能である．本節で546は，LLM による最適化とその課題について説明する． 7892. 1 LLM によるコードの最適化

def search ( arr , target ):low = 0high = len ( arr ) - 1

1011

LLM をコード最適化に用いる意義は，従来の言語 12

while low <= high :mid = ( low + high ) // 2
if arr [ mid ] == target :return mid
elif arr [ mid ] < target :low = mid + 1else :high = mid - 1

13

処理系が行う最適化よりも抽象度の高い最適化を行 14

return -1

うことができる点にある．言語処理系によるコード最適化の多くは，コードのアルゴリズムを変更すること

図2

最適化後コード（二分探索）なく，コードの実行速度を向上させる．例えば，ループ最適化，DCE（Dead Code Elimination），CSEるとは限らないためである．LLM が最適化したコー（Common Subexpression Elimination）などが挙げ

ドは，構文エラーや意味エラーを含む場合がある．まられる．LLM を用いてもこれらの最適化は可能であ

た，元のコードとは異なる振る舞いをする場合がある．しかし，LLM は，コードの理解が必要となるよ

る．LLM を用いたコード最適化の実用化における課うな，より高度な最適化も可能である．LLM が行う

題は，これらの問題を解決することである．以下でことができる最適化には，アルゴリズムの変更，デーは，LLM を用いたコード最適化における問題の詳細

タ構造の変更を伴う最適化も含まれる．

を説明する．

例えば，図 1 のような線形探索を行うコードが与2. 2. 1 構文エラーや意味エラーえられたとき，LLM は，二分探索を行うコードを生LLM が生成するコードは，構文エラーを含む場合成することができる．LLM に最適化の指示を行うこがある．LLM で用いられるサンプリング手法では，とで，図 2 のような二分探索を行うコードに最適化生成されるコードの構文が正しいことが保証されなすることができる．この最適化により，線形探索の計

い．LLM で使用されるサンプリング手法としては，

算量 O(n) から，二分探索の計算量 O(log n) に削減

top-k sampling [2] や top-p sampling [3] などがある．

される．このため，LLM を用いることで，従来の言これらの手法は，Transformer [5] が生成する確率分

語処理系では達成できなかった大幅な速度向上を期待

布から次のトークンをランダムにサンプリングする．

できる．

このため，偶然に構文エラーが生成されることがある．例えば，閉じ括弧が不足しているなどの構文エ2. 2 LLM によるコード最適化の課題ラーが発生する場合がある．閉じ括弧の確率が高かっ

LLM を用いることで，大幅な速度向上を期待できたとしても，ランダムサンプリングでは，異なるトーるが，生成されたコードをそのまま利用することは難しい．これは，LLM が常に正しいコードを生成すクンを生成することがある．
構文エラーが発生しなかった場合でも，生成された1
2

def multiply (a , b ):return abs ( a % 10) * abs ( b % 10)

図3

1
2

最適化前コード（HumanEval/97）

def multiply (a , b ):return (( a % 10) + 10) % 10 * (( b %10) + 10) % 10

図4

最適化後コードが正しくない例（HumanEval/97）

コードが正しいとは限らない．型エラーなどの意味エラーが含まれる場合もある．これらのエラーは，言語処理系が検出することができるエラーである．

1

3

2. 2. 2 機能的正確性の問題
言語処理系で検出可能な構文エラーや意味エラー

from typing import List

24

def f i l t e r _ b y _ s u b s t r i n g ( strings :List [ str ] , substring : str ) ->List [ str ]:return [ x for x in strings if
substring in x ]が含まれない場合でも，最適化されたコードが正しいとは限らない．最適化されたコードが元のコードとは

図5

最適化前コード（HumanEval/7）

異なる振る舞いをする場合がある．

1

例として，HumanEval/97 [1] を gpt-4o-mini で最適きない場合がある．これは，性能に関するコストモデ化した例を示す．図 3 は，最適化前の HumanEval/97

ルを持っていないためである．LLM は，最適化の結のコードである．multiply 関数は，2 つの整数を入果どの程度速くなるかを正確に予測できない．このた力とし，それぞれの数の最右桁同士の積を返す関数でめ，最適化した結果が元のコードよりも遅くなる場合ある．これを gpt-4o-mini で最適化した結果，図 4 のが存在する．

コードが生成された．元のコードでは，abs 関数を用例として，HumanEval/7 を gpt-4o-mini で最適化いて負の数を正の数に変換しているが，最適化後コーした例を示す．図 5 は，最適化前の HumanEval/7 のドでは，abs 関数の呼び出しを回避することで，高速コードである．関数 filter_by_substring は，リス化を図っている．しかし，この最適化は，Python のトと文字列を入力とし，リストの要素の中から文字演算子の優先度が考慮されておらず，誤った結果を返列を含む要素のみを抽出する関数である．最適化前す場合がある．例えば，a=148，b=412 の場合，最コードでは，in 演算子で文字列がリストの要素に含右桁同士の積は 8*2=16 であるが，最適化後コードまれるかどうかを判定している．一方，gpt-4o-mini

では，結果が 6 となる．これは，%演算子と*演算子で最適化したコードの一例は，図 6 のようになる．最の優先度が等しく，左結合により，左から順に計算さ適化後コードでは，in 演算子の代わりに find 関数れるためである．すなわち，最適化後コードは，以下を用いている．LLM は，find 関数を用いることで高のように解釈される．

速化を図っていると考えられる．しかし，この最適化(((( a % 10) + 10) % 10) * (( b % 10) +10)) % 10は，元のコードよりも遅くなる場合がある．実際にこのように LLM は，最適化したコードが元のコードの処理系で実行すると，最適化後コードは最適化前とは異なる振る舞いをする場合がある．LLM を用いコードよりも遅くなる．

HumanEval に付属するテストコードを Python 3.11た最適化を実用化するためには，このような場合を回避する必要がある．

2. 2. 3 性能向上の不確実性

3 提案フレームワーク
提案フレームワークでは，LLM を用いて最適化し最適化されたコードが正しかったとしても，最適化たコードを単体テストを用いて機能的・性能的に検されたコードが元のコードよりも速くなるとは限ら証する．単体テストのためのテストケースも同様にない．LLM は，様々な最適化のテクニックを知識とLLM を用いて生成する．

して持っているが，それらを適切に適用することがで

図 7 に提案フレームワークの構成を示す．本フレー1from typing import List

2
3

4
5

def f i l t e r _ b y _ s u b s t r i n g ( strings :List [ str ] , substring : str ) ->List [ str ]:s u b s t r i n g _ l e n g t h = len ( substring )return [ x for x in strings ifx . find ( substring ) != -1]

認するためのコードである．アサーションがエラーを発生させる場合，LLM にエラーメッセージをフィードバックすることで，LLM にテストの修正を促す．
最適化前コードが全てのテストをパスすると，次にカバレッジを計算する．生成された単体テストを実行した後，最適化前コードに未到達の行がある場合，

図6

最適化後コードが遅くなる例（HumanEval/7）

それは単体テストが不十分であることを意味する．そこで，本フレームワークでは，未到達の行を LLM にムワークの入力は，非最適化コードであり，出力は単フィードバックすることで，LLM にテストケースの体テストと最適化済みコードである．単体テストは，追加を促す．

最適化前コードを網羅するテストケースを含む．ま

この処理フローをカバレッジが 100%になるか，最た，本フレームワークでは，生成した単体テストは大試行回数に達するまで繰り返す．最大試行回数で打最適化前コードが必ずパスするようにする．同様に，ち切った場合を除き，生成された単体テストは，最適生成した最適化後コードも単体テストをパスするよ

化前コードが必ずパスすること，および最適化前コーうにする．このため，単体テストの実行において，最ドの全ての行に到達することが保証される．

適化前後でのコードの等価性が保証される．さらに，本フレームワークでは，最適化済みコードが非最適化コードよりも単体テストの実行速度が向上することも保証する．
以下では，提案フレームワークのテストケース生成とコード最適化について詳細を説明する．

3. 2 コード最適化
コード最適化では，LLM に最適化前コードを高速化するように指示を与える．LLM が最適化したコー
ドには，構文エラーや意味エラーが含まれる可能性がある．最適化されたコードの構文エラーや意味エラーは，ビルドフェーズで検出される．エラーが検

3. 1 テストケースの生成出された場合，エラーメッセージを LLM にフィード

本フレームワークでは，最適化対象の関数ごとにバックすることで，LLM にエラーの修正を促す．なLLM を用いて単体テストを生成する．単体テストは，お，本来ビルドが不要なスクリプト言語の場合，ビル単体テストフレームワークを用いたプログラムの形ドフェーズでは構文チェックを行う．

式で生成される．LLM が生成した単体テストには，ビルドでエラーが検出されない場合，最適化された構文エラーや意味エラーが含まれる場合がある．図コードは，生成された単体テストを用いて実行され7 のビルドフェーズでは，言語処理系から得られるる．テストがアサーションエラーを発生させる場合，エラーメッセージを LLM にフィードバックすること

テストの結果を LLM にフィードバックすることで，で，LLM にエラーの修正を促す．なお，ビルドが不最適化後コードの修正を促す．

要な Python などのスクリプト言語の場合でも，ビルドフェーズでは構文チェックを行う．

最適化後コードがエラーを発生させなくなった後，テスト実行時のプロファイリング情報をもとに最適化

構文エラーがなくなると生成されたテストケースを前コードから速度向上率を計算する．この速度向上率実行する．生成されたテストが間違っている場合，エは，LLM にフィードバックされ，LLM はこの情報をラーが発生する．単体テストフレームワークは，期待もとにコードを最適化する．

値と実際の値を比較することで，テストが正しいかどうかを判断する．この確認は単体テストフレームワー

4 実験

クが提供するアサーションを用いて行う．アサーショ

提案フレームワークによるコード最適化の効果をンは，テストの結果が期待値と一致するかどうかを確確認するため，コード生成用のベンチマークである

テスト⽣成

⾮最適化
コード
テスト
⽣成

ビルド

カバレッジ
計測

実⾏

単体テスト

構⽂エラー
アサーションエラー
最適化済み
コード

未実⾏⾏

ビルド

最適化

構⽂エラー

テスト実⾏

アサーションエラー

プロファイル

速度改善⽐
3

コード最適化

図7

コード最適化フレームワーク

倍以上の速度向上を実質的な改善とみなし，その分布

を分析した．1.1 倍以上の速度向上を示したプログラ

ムは 149 個のうちの 74 個の 49.66%であった．





図 8 に速度向上率の分布を示す．速度向上を示したプログラムのうち，2 倍以上の速度向上を示したプ

ログラムは，45.95%であった．また，12.16%のプロ

グラムが 10 倍以上の速度向上を示することを確認し



た．平均速度向上率は 24.60 であり，最小速度向上率は 1.10，最大速度向上率は 1074.08 であった．

図8

速度向上率のヒストグラム(速度向上率が 1.1 以上に限定)

4. 2 最適化後コードの調査結果
速度向上率が 10 以上のプログラムについて，最適

HumanEval [1] を用いて実験を行った．HumanEval

化前後のコードを比較した．これらのプログラムでは，Python の関数シグネチャと docstring から関数は，計算量の変更を伴うアルゴリズムの変更が行わの実装を生成するタスクのデータセットである．デーれていた．これらは，計算量の変更を伴うアルゴリズタセットには，関数を検証するためのテストと正解とムの変更が行われたプログラムである．例えば，図 9なる関数実装が含まれている．本実験では，付属の関のコードは，最適化前コードでフィボナッチ数列を再数実装を最適化前コードとして扱い，提案フレーム帰的に計算するプログラムである．元々の時間計算量ワークによる最適化を行った．

は O(2n ) である．
図 10 のコードは，最適化後コードでフィボナッチ4. 1 実験結果

数列の計算にメモ化を用いたプログラムである．メモ

HumanEval に含まれる 164 個の Python の関数を化により，各 fib(n) が一度だけ計算され，その結果最適化し，最適化前後の実行時間を測定した．性能評が辞書 memo にキャッシュされる．この結果，各フィ価には，Python 3.11 の処理系を用い，M2 プロセッボナッチ数が 1 回だけ計算されるためため，時間計

サの macOS 14.0.1 上で実施した．

算量は O(2n ) から O(n) に削減される．また，辞書

164 個の関数のうち 10 回の最大試行回数で最適化

memo には，すべての計算結果が格納され，さらに再に成功したのは，149 個であった．本研究では，1.1

帰呼び出しのコールスタックの深さも最大で n にな123456def fib ( n : int ):if n == 0:
return 0
if n == 1:
return 1
return fib ( n - 1) + fib ( n - 2)

123
45678

図9最適化前コード
9def fib ( n : int , memo ={}):
if n in memo :return memo [ n ]if n == 0:
return 0
if n == 1:
return 1
memo [ n ] = fib ( n - 1 , memo ) + fib ( n- 2 , memo )return memo [ n ]る．メモ化によってすべての計算結果が保存されるため，空間計算量も O(n) である．この時の速度向上率

図 10

1 回目の最適化後コード

は，21.64 である．
この速度向上率をフィードバックして得られた最適1化は，図 11 のようになる．図 11 のコードは，最適2化済みでフィボナッチ数列の計算に反復処理を用い3て計算するプログラムである．反復処理によるアル

5

4def fib ( n : int ) -> int :if n == 0:
return 0
if n == 1:
return 1

6

ゴリズムでは，フィボナッチ数列を 1 つずつ順に計算するため，計算量は O(n) となる．すなわち，n 回

789a, b = 0, 1
for _ in range (2 , n + 1):
a, b = b, a + b

10のループでフィボナッチ数列を計算する．また，この 11

return bアプローチでは，必要な変数は 2 つの整数 a と b だ
けで，それらを用いて次々とフィボナッチ数を計算す

図 11

2 回目の最適化後コード

る．したがって，空間計算量は O(1) である．コールスタックや追加のメモリが不要である．この時の速度ワークでは，LLM を用いてテストケースを自動生成

向上率は，23.06 であり，1 つ前の最適化後コードよすることで，最適化されたコードの機能と性能を検りもさらに高速化されている．この改善は空間計算量証する．テストケースの生成では，カバレッジ情報をの削減によるものであると考えられる．

フィードバックすることで，網羅的なテストケースをこのように LLM を用いることで，計算量の変更を生成する．また，テスト実行時の性能情報をフィード伴う最適化を行うことができ，高速化が可能であるこバックすることで，LLM にコードの性能を反復的にとを確認できた．また，フィードバックを用いること改善させる．実験では，Python 用のコード生成タスで，LLM 自身が最適化したコードを反復的に改善すクセットである HumanEval を用いて，提案フレームることができることを確認した．なお，最大の速度向ワークの有効性を確認した．その結果，有意な速度向上率である 1074.08 のプログラムは，同様に計算量上が得られたコードでは最適化の前後で平均 24.6 倍の変更を伴うアルゴリズムの変更が行われたプログの速度向上を確認した．

3ラムであった．元のプログラムは，O(n ) の計算量を持つアルゴリズムであったが，最適化後のプログラム

参 考 文 献は，O(n) の計算量を持つアルゴリズムとなっている[1] Chen, M., Tworek, J., Jun, H., Yuan, Q.,
de Oliveira Pinto, H. P., Kaplan, J., Edwards, H.,
Burda, Y., Joseph, N., Brockman, G., Ray, A., Puri,R., Krueger, G., Petrov, M., Khlaaf, H., Sastry, G.,
Mishkin, P., Chan, B., Gray, S., Ryder, N., Pavlov,M., Power, A., Kaiser, L., Bavarian, M., Winter,C., Tillet, P., Such, F. P., Cummings, D., Plappert, M., Chantzis, F., Barnes, E., Herbert-Voss,A., Guss, W. H., Nichol, A., Paino, A., Tezak, N.,Tang, J., Babuschkin, I., Balaji, S., Jain, S., Saun-

ことを確認した．

5 まとめ
本研究では，LLM を用いたコード最適化の問題点を整理し，それを解決するフィードバック付きのコード最適化フレームワークを提案した．提案フレーム

ders, W., Hesse, C., Carr, A. N., Leike, J., Achiam,J., Misra, V., Morikawa, E., Radford, A., Knight,M., Brundage, M., Murati, M., Mayer, K., Welinder, P., McGrew, B., Amodei, D., McCandlish, S.,
Sutskever, I., and Zaremba, W.: Evaluating Large
Language Models Trained on Code, (2021).
[2] Fan, A., Lewis, M., and Dauphin, Y.: Hierarchical Neural Story Generation, Proceedings of the56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers),
Gurevych, I. and Miyao, Y.(eds.), Melbourne, Australia, Association for Computational Linguistics,

July 2018, pp. 889–898.
[3] Holtzman, A., Buys, J., Du, L., Forbes, M., andChoi, Y.: The Curious Case of Neural Text Degeneration, 2020.
[4] Schäfer, M., Nadi, S., Eghbali, A., and Tip,
F.: An Empirical Evaluation of Using Large Language Models for Automated Unit Test Generation, IEEE Transactions on Software Engineering,Vol. 50, No. 1(2024), pp. 85–105.
[5] Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit,J., Jones, L., Gomez, A. N., Kaiser, L., and Polosukhin, I.: Attention Is All You Need, 2023.