LLMのコード生成に関する論文を読む
Yuku KotaniLLMコード生成の動向をキャッチアップする。
落合式メソッド で論文を読んでメモしていく
Yuku KotaniIterative Refinement of Project-Level Code Context for Precise Code Generation with Compiler Feedback [2024]
感想
Coding Agent に自律的にイテレーションさせるのではなく、ある意味ナイーブにイテレーションの型を規定するという感じか。それに加えて CodeQL によって文脈理解を安定させつつ RAG による意味検索で幅も持たせる挟み撃ちがキモっぽい。
CodeQL みたいな文脈理解ツールを与えた Coding Agent を自律的に動かすのと比較するとどうなんだろうなー。
degenerate solution への対策としては、やはりコンパイルエラーだけでなくユニットテストもフィードバックに加えるよさそう。
総じて静的に解析できることの価値を再確認できる。
サマリ
どんなもの？
COCOGEN（Compiler‐guided Code Generation）は、大規模言語モデル（LLM）が生成したコードをプロジェクト全体の文脈と突き合わせながらコンパイラエラーを手がかりに自動修正する手法です。静的解析で得たクラス／関数／変数の構造情報と意味情報をデータベース化し、エラーに応じて最適なコード片を検索してプロンプトに追加しつつ「生成→コンパイル→エラー解析→再生成」を繰り返します。
先行研究と比べてどこがすごい？
-
RepoCoderやReACCなど既存法もリトリーバル＋再生成を行いますが、COCOGENは
- コンパイラが吐く具体的なエラーメッセージを直接利用し、
- 構造検索（SQL／CodeQL）と意味検索（Dense Passage Retrieval）のハイブリッドで最適文脈を引く点が新しいです。
-
CoderEval-Pythonの「プロジェクト依存」課題で、GPT-3.5-Turbo利用時にPass@10を**21.7%→39.1%（+80%相対改善）**へ大幅向上させました。
技術や手法のキモはどこ？
-
プロジェクト構造抽出
- ASTを辿ってモジュール→クラス→メンバ関数/変数を階層保存し、各ノードのdocstringや定義位置ベクトルを事前計算。
-
エラー駆動検索
- 頻出11種のエラーコードは手作りSQLテンプレートで即検索、その他はLLMにSQL生成を任せる。
-
二段リトリーバル
- (a) 構造一致で候補を絞り、(b) エラー文やタスク文をクエリにした意味検索で類似コードを追加。
-
反復生成ループ
- 生成コードをコンパイル→エラー種判定→文脈追加→再生成。3周程度で効果が頭打ちになるが最大で約15 pt向上。
どうやって有効だと検証した？
-
データセット: CoderEval-Python（Class/File/Project runnable 各55/68/23問）、HumanEval、MBPP、CrossCodeEval。
-
モデル: GPT-3.5-TurboとCode Llama-13B。
-
指標: Pass@k（生成コードがテスト全通過）・C-EM/C-ES・I-EM/I-F1。
-
結果:
- Project runnable でPass@10: GPT-3.5直入力13.0%→COCOGEN 39.1%。
- File runnable でも36.8%→47.1%。
- CrossCodeEval でも識別子F1が+1.3 pt向上。
-
エラー解析: UNDEF/API/OBJECT系の66%を1回の反復で除去。
議論はある？
- 実行時エラー（FUNC）は対象外—コンパイルは通るがロジックが破綻するケースは残る。
- イテレーション効果は3回で飽和し、一部の複雑エラーは修正できない。
- SQL自動生成失敗やLLMの**退化解（degenerate solution）**が残存課題。
- 成功コンパイル≠安全実行なので、テスト・人手レビュー併用が必要、と著者も認めています。
次に読むべき論文は？
| 観点 | 推奨論文 |
|---|---|
| リトリーバル＋生成 | RepoCoder (ACL 2023) — 類似コードリトリーバルと再生成でリポジトリ補完 |
| プロンプト拡張 | ReACC (ACL 2022) — セマンティック検索で周辺コードをプロンプトに注入 |
| マルチレベル文脈 | A3-CodGen (arXiv 2023) — ローカル・グローバル・外部ライブラリ情報併用 |
| 評価ベンチマーク | ClassEval (ICSE 2024) ／ CrossCodeEval (NeurIPS 2023) |
| 自動デバッグ | Self-Edit (ACL 2023) — 実行結果で自己修正するgenerate-and-edit |
| 競技プログラミング | AlphaCode (Science 2022) — 大規模サンプリング＋クラスタリング＋テスト |
これらを通して「コード生成×フィードバック」の最新潮流を俯瞰できます。
Yuku KotaniType-Constrained Code Generation with Language Models [2025]
感想
先述の COCOGEN のように生成結果全体に対してフィードバックを与えるのではなく、トークン単位のデコーディングの段階で型チェックをして枝刈りすることで、より小さいイテレーションで方向修正ができる。面白い。top k から確率で選びま〜すで終わるわけがないよなと納得した。
まだ調べてないけど感覚的には、現状のコード生成でもSynchromesh相当の構文チェックはされている気がする。これを型チェックに拡張するのは正統進化そう。
今のところ限定的なTypeScriptのサブセットを実装しているから現実的な速度で実現できているっぽいけど、これを複雑な型計算などに対応させていくのはかなりチャレンジングそう。少なくとも現状のtscをトークン単位で実行できるわけがない。てかそもそも途中状態からの先読みをオートマトンでやってるのでtscのアーキテクチャとは根本的に異なりそう。ともかくツールチェインの速度が本当にクリティカルになることを再確認できる。
短絡的にはGoのような表現力の低い言語だと実現しやすそうに感じるが、実際にはランタイムエラーに寄せて握りつぶすことになりそうとも思う。それにしてもこのアプローチを進める上でTSの表現力は too much な直感はあり、どのくらいの塩梅がいいんだろうなー
サマリ
どんなもの？
大規模言語モデル（LLM）がソースコードを生成する際に「型が合わずコンパイルできない」問題を根本から抑え込む Type-Constrained Decoding を提案する論文です。
LLM がトークンを 1 文字ずつ出力するたびに、独自に構築した プレフィックス・オートマトン（prefix automaton） と 型到達性探索 を用いて「今の部分プログラムは最終的に型が整合する形まで完結できるか」を即座に判定し、不可能なトークンをサンプリング段階でマスクします。結果として、HumanEval / MBPP の TypeScript 版で コンパイルエラーを平均 50 %以上削減し、pass@1 を 3.5 – 5.5 %（修復タスクでは 30 %以上）向上 させました。
先行研究と比べてどこがすごい？
- 既存の制約付きデコーディングは 構文レベル（CFG やインデント）しか扱えず、実際のエラーの 6 % 程度しか捕捉できなかった。
- 本手法は 型システムまで直接組み込む ことで、LLM がもっとも苦手とする型エラー（評価では 94 % を占める）を抑制し、あらゆるモデル・タスクで一貫して大幅な改善を実証した。
技術や手法のキモはどこ？
-
プレフィックス・オートマトン
- 受理状態へ到達可能な状態のみ遷移できる “prefix property” を満たすオートマトンを構築し、部分プログラムが型的に完結可能かを高速判定。
-
型到達性（Type Reachability）探索
- 部分式の導出型から、演算子・メンバ呼び出し・関数呼び出しをグラフ探索して「要求される型」への到達可否を判定する。PSPACE 完全問題を深さ制限などで実用化。
-
サンプル＆チェック実装
- 1 トークンずつ「試す→検査」を繰り返す実装とすることで、99 % 以上のステップが 1 回のチェックで済み、全語彙を毎回走査する従来法より高速。
-
汎用言語設計
- まず simply-typed calculus 𝐿𝐵 で形式化し、その後 TypeScript の実用サブセットに拡張して効果を検証。
どうやって有効だと検証した？
| 観点 | 設定 | 主な結果 |
|---|---|---|
| ベンチマーク | HumanEval-TS (159) / MBPP-TS (384) | コンパイルエラーを –75.3 % (HumanEval) / –52.1 % (MBPP) 削減し、pass@1 を +3.5 〜 4.5 % 相対向上 |
| タスク | コード合成・Python→TS 翻訳・コンパイル失敗コードの修復 | 合成／翻訳でエラーを半減以上、修復タスクでは失敗コードの 約 1.5 倍 を追加修復。pass@1 は修復で +34 〜 40 % 相対改善 |
| モデル | Gemma 2 (2B/9B/27B)、DeepSeek-Coder 33B、CodeLlama 34B、Qwen 2.5 32B | すべてのモデルで一貫した効果。最小でも –57.3 % (HumanEval) / –31.6 % (MBPP) のエラー減少を達成し、モデルサイズや系列に依存しない改善 |
| 指標 | コンパイルエラー数・pass@1・実行時間 | 実行時間の中央値は +30 〜 50 %（平均 +44.5 %）のオーバーヘッドで、高い精度向上と妥当なトレードオフ |
| 結果概要 | – | コンパイルエラー: –53 %〜–88 %．pass@1: 合成 +3.5 %, 翻訳 +5 %, 修復 +37 %．実行時間: +39 % (HumanEval) / +52 % (MBPP) |
議論はある？
- 言語カバレッジ: 現状の TypeScript サブセット外（ジェネリック型推論や複雑な型演算）には未対応で、拡張は手動実装が必要。
- ブラックボックス API: 商用 API は次トークン分布を返さないため外部から適用しにくく、モデル提供側の統合が望ましい。
- デコーディング無限ループ: 厳しい制約下で LLM が同一トークンを繰り返しタイムアウトするケースが残る（実験ではごく少数）。
次に読むべき論文は？
- Synchromesh – 構文 CFG による信頼性向上 (ICLR 2022)
- Guiding LLMs The Right Way – 高速・非侵入型制約生成 (ICML 2024)
- Constrained Decoding for Fill-in-the-Middle – 左右クォーティングを用いた Python インデント制約 (ICSE 2024)
- XGrammar – 任意文法を高速に扱う汎用エンジン (arXiv 2024)
- Statically Contextualizing LLMs with Typed Holes – 型情報で穴埋め補完 (OOPSLA 2024)
これらを順に読むと「構文制約→高速制約→型情報活用」へと発展する流れを俯瞰できます。
Yuku KotaniGuiding LLMs The Right Way [2024]
感想
最初にウォームアップをしてスキャナとパーサの状態からトークンへの対応の確率表を作っておいて、それに基づいて確立の高い10トークン程度を先読みすることで、1回のフォワードパスで一気に生成することを狙うとのこと。この確率表が直感的に理解できなかった。
文字リテラルの中とかだと実質的に任意のトークンが来るから、あんまり重みをつけられないだろ、と思った。けどよく考えると、あくまで文法を守らせるための仕組みだからそれでいいんだね。{ "name": みたいなタイミングで次にちゃんとリテラルが来るようにできれば十分、と。これはJSONのような単純な文法で効果を発揮するのに納得。
事前に文法規則のツリーを作っておくので、静的な文法には効果的だけど、型チェックのような動的に規則が変わる場合には適用できないか。
サマリ
どんなもの？
- DOMINO という新しいデコーダを提案。DOMINO は大規模言語モデル (LLM) に対して正規表現・CFG (コンテキスト自由文法) などの厳格な出力制約を課しつつ、制約なし生成と同等かそれ以上の速度でテキストを生成できる。
先行研究と比べてどこがすごい？
| 手法 | 制約遵守率 | 速度 (無制約=1.0) | 特記事項 |
|---|---|---|---|
| テンプレート系 (GUIDANCE, LMQL) | 中 | 0.5–1.0 | トークン化固定で精度低下 |
| オンラインパーサ系 (PICARD, llama.cpp CFG) | 高 | 0.7–0.9 | 全語彙走査で遅い |
| DOMINO | 高 | 0.8–2.7 | 制約遵守を維持しながら高速化 |
技術や手法のキモはどこ？
-
語彙整合サブターミナル木
- オフラインで、各スキャナ状態に対し「そこから読める合法トークン集合」を木構造にまとめる。生成時はこの木だけを探索するため語彙全量走査を回避。
-
Opportunistic Masking
- 生成ステップごとに LLM が提案したトップ1トークンを即時検証し、合法ならマスク計算をスキップ。
-
状態付き Speculative Decoding
- 生成途中の スキャナ状態 (入力をどこまで読んだか) と パーサ状態 (文法規則のどの位置か) をキーに、オンラインで作成した簡易確率表
P(\text{token}\mid\text{状態}) - 閾値以上の確率がある間は最大 s 個 (例 6–10) のトークン列を下書きし、LLM 1 回のフォワードパスで一括検証。先頭一致部分をまとめて確定することで呼び出し回数を ≈ 1/s に削減。
- 生成途中の スキャナ状態 (入力をどこまで読んだか) と パーサ状態 (文法規則のどの位置か) をキーに、オンラインで作成した簡易確率表
どうやって有効だと検証した？
-
GSM8K (算数推論) と CoNLL-2003 (NER) を 5-shot JSON 出力で比較。
- Mistral-7B では DOMINO (k = ∞) が無制約と同等の精度で 最大 2.7 × のスループット向上。
-
JSON + Schema, XML, C など複数文法でも評価。JSON + Schema では 77 % 速度向上、C でも無制約比 0.78 × を維持。
議論はある？
- 先読み深さ
k - 文法が複雑で分布が広い言語 (例 C) では確率表の命中率が下がり、速度メリットが限定的。
- 出力ごとに文法が変わるケースではオフライン木の再生成コストが発生する。
次に読むべき論文は？
- PICARD (2021) – CFG 強制生成の先駆け
- SYNCHROMESH (2022) – トークンと文法ミスマッチ問題の詳細解析
- Grammar-Constrained Decoding (GCD) (2023) – 追加学習不要の CFG 制約
- Speculative Sampling (2023) – 小モデル下書き＋大モデル検品による高速化
- GUIDANCE / LMQL / OUTLINES – 正規表現・テンプレート型制約の代表実装