💻 computer science

AlgoBench: Benchmarking Algorithmic Adaptation in Code Generation

本論文は、既存の競技プログラミングの課題を変換することで解の再利用を防ぎ、言語モデルが機能的な正当性を超えて真のアルゴリズム的推論能力を備えているかどうかを厳密に評価するための複雑性を考慮した指標を伴う、適応的なアルゴリズム問題を生成する新しいフレームワークであるALGOBENCHを導入するものである。

原著者： Xinyuan Song, Zekun Cai, Liang Zhao

公開日 2026-07-02

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

CC BY 4.0

原著者： Xinyuan Song, Zekun Cai, Liang Zhao

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

あなたは学生に数学の問題を解くよう訓練していると想像してください。あなたは練習テストを与え、その学生は満点を取ります。あなたは「わあ、この子は微積分を本当に理解しているんだな！」と思うかもしれません。しかし、もし彼らが実際に数学を学んでいなかったとしたらどうでしょう？もし、以前教科書で見た特定の質問に対する答えを、ただ暗記していただけだとしたら？

これは、コードを書くAIシステムである大規模言語モデル（LLM）に対して、論文ALGOBENCHが解決しようとしている問題そのものです。

問題点：「カンニングペーパー」効果

現在のAIモデルは、HumanEvalのような標準的なコーディングテストに合格することに長けています。しかし、この論文は、これらのテストが「汚染」されている可能性があると主張しています。これらの問題は公開されているため、AIはトレーニング中に全く同じ質問とその解答をすでに目にしている可能性が高いのです。

それは、教師が誤って解答用紙を机の上に置き忘れてしまったテストを受けている学生のようなものです。学生は天才だから満点を取ったのではなく、解答を暗記していたから満点を取ったのです。論文では、これは推論ではなく**記憶（memorization）**であると呼んでいます。AIは問題の「解き方」を導き出しているのではなく、単にその解決策が「どのようなものか」を思い出しているだけなのです。

解決策：ALGOBENCH（「ひねり」を加えたテスト）

これを解決するために、研究者たちはALGOBENCHを作成しました。これはAIに対する「ひねりテスト（Twist Test）」だと考えてください。

既知の問題を提示する代わりに、彼らは既知の問題に「魔法のひねり」を加えます。元の答えが機能しなくなる程度にルールを少しだけ変えるのですが、問題自体は一見すると馴染みのあるものに見えるようにします。

彼らが用いる「ひねり」は以下の通りです：

「スケールアップ」のひねり： もし元の問題が100個の数字をソートすることを求めていた場合、新しい問題では1,000,000個の数字をソートすることを求めます。古い「遅い」手法ではクラッシュしてしまい、AIはより速く、よりスマートな方法を編み出さなければなりません。
「動く標的」のひねり： もし元の問題が静的な数値リストに関するものだった場合、新しい問題では作業中に数値が変化するというルールを追加します。元の「読み取り専用」の解決策は失敗し、AIには動的な戦略が必要になります。
「罠」のひねり： 一般的なショートカット（強欲な推測など）が、最初はうまくいっているように見えるものの、隠れたトリッキーなケースでは失敗するようなシナリオを設定します。

もしAIが古い記憶に基づいた解決策を使おうとすれば、失敗します。合格するためには、思考を実際に適応させ、新しいアルゴリズムを生成しなければなりません。

「速度制限」チェック

論文はまた、私たちが通常AIを評価する方法における欠点も指摘しています。通常、私たちは単に「コードがエラーなしで実行されたか？」を確認します（合否判定）。

しかし現実の世界では、動作はするものの完了までに100年かかるような解決策は役に立ちません。ALGOBENCHは**複雑性検証器（Complexity Verifier）**を導入しています。これは、車が単にゴールラインを越えたかどうかだけでなく、どれくらいの速さで行ったかをチェックする審判のようなものです。

OPTT（最適時間）： AIは高速な解決策を書いたか？
OPTS（最適空間）： AIはコンピュータのメモリを使い果たさないような解決策を書いたか？

論文によれば、多くのAIモデルはテストには合格しますが、速度チェックには失敗することがあります。これらは小さな例題では動作するコードを書きますが、実際の制約に対しては遅すぎるのです。

分かったこと

7つの異なるAIモデルをこれらの「ひねり」を加えた問題でテストしたところ、驚くべき結果が得られました。

パフォーマンスの低下： 問題に「ひねり」を加えると、AIのスコアは大幅に低下しました。これは、AIが真の理解ではなく、記憶されたテンプレートに依存していたことを証明しています。
「検索」の罠： 研究者が元の問題を見せることでAIを助けた（検索による支援）場合、AIは適応するのがむしろ下手になりました。AIは、古い解決策を新しい問題に無理やり当てはめようとして、行き詰まってしまったのです。まるで、丸い穴に四角い杭を打ち込もうとするかのようです。
真の推論は困難： 失敗の多くは、タイポや小さなコーディングミスによるものではありませんでした。彼らは、必要とされる新しいロジックを理解できなかったために失敗したのです。新しい高速な手法が必要な場面で、古い低速な手法を使おうとしてしまったのです。

結論

ALGOBENCHは、AIが古い答えを暗記することで「カンニング」することを防ぐ、新しいAIテストの方法です。これは、AIが単に学校で学んだスクリプトを暗唱するのではなく、新しいルールにどのように考え、適応できるかを示すことを強制します。

論文は、AIはコードを書くことには長けてきていますが、ルールが変わったときに、コードの背後にあるアルゴリズムを真に理解することには依然として苦労していると結論付けています。AIはレシピに従うことは得意ですが、ゼロから新しい料理を作る方法をまだ学んでいる最中なのです。

技術要約: ALGOBENCH

問題提起

HumanEvalやLiveCodeBenchといった、コード生成に関する現在の大型言語モデル（LLM）ベンチマークは、高い合格率を示すことが多いが、それが必ずしも真のアルゴリズム的推論能力を反映しているとは限らない。主要な限界は**データ汚染（Data Contamination）**である。確立された問題文、解説、およびリファレンス・ソリューションは、公開されている学習コーパス内に広く存在している。その結果、モデルはアルゴリズムを制約から導出するのではなく、記憶された解法のパターンを想起することによって高いスコアを獲得している可能性がある。近年のベンチマーク（LiveCodeBench、ProBench、HLCEなど）は、より新しい、あるいはより困難な問題を使用することでこの問題を軽減しようと試みているが、これらは依然として静的である。一度リリースされると、その問題文とモデルが生成したソリューションは必然的に学習データへと入り込み、将来のモデルが推論能力の向上ではなく、露出を通じて改善することを可能にしてしまう。したがって、ソースとなる解法の記憶だけでは不十分であり、モデルにアルゴリズム戦略の適応を強制する、動的に問題を生成するベンチマークが必要とされている。

メソドロジー

コアフレームワーク: ALGOBENCH

著者らは、既知の競技プログラミングのソースから新しいアルゴリズム問題を自動構築するためのフレームワークであるALGOBENCHを提案する。その核心となる哲学は**制約シフト変換（Constraint-shifting transformation）**である。これは、元のリファレンス・アルゴリズムが失敗するようにソース問題を修正し、新しいアルゴリズム的アプローチや異なる漸近的計算量を必要とさせるものである。

1. 変換オペレータ (Transformation Operators)
本フレームワークは、ソース問題 ( $q$ ) からバリアント ( $q'$ ) を生成するために、10個のルールベースの変換オペレータを採用している。これらには以下が含まれる：

制約スケーリング (Constraint Scaling, CS): 入力境界の増加（例： $N \le 2000 \to N \le 2 \times 10^5$ ）。
静的から動的への変換 (Static-to-Dynamic, SD): 静的な問題を動的な問題へ変換（例：更新操作の追加）。
目的の摂動 (Objective Perturbation, OP): 最適化目標の変更。
グリーディ・トラップ注入 (Greedy-Trap Injection, GT): グリーディなヒューリスティックを無効にする制約の導入（例：動的計画法を必要とするようにする）。
その他のオペレータには、制約結合（Constraint Coupling）、エッジケース拡張（Edge-Case Expansion）、出力要件の変更（Output Requirement Change）、およびより広範な変換である実世界ラッピング（Real-World Wrapping）やグラフ構造の変化（Graph-Structure Change）が含まれる。

2. クオリティ・ゲート (Quality Gates)
妥当性を確保し、問題が些末なものになるのを防ぐため、生成された問題は4つの自動ゲートを通過しなければならない：

ゲート1 (旧ソリューション拒絶): 元のリファレンス・ソリューション ( $a^*$ ) が新しい問題に対して失敗すること（WA、TLE、またはMLEを出すこと）。
ゲート2 (新ソリューション検証): 新しいリファレンス・ソリューション ( $\hat{a}^*$ ) が、小さな入力に対するブルートフォース・オラクルによって検証されること。
ゲート3 (非パラフレーズ): 生成された記述がソースと十分に異なっていること（TextSim $< \tau_{text}$ ）。
ゲート4 (計算量認定): 新しいソリューションが目標とする時間および空間計算量を満たしていること。

3. 決定論的計算量検証器 (Deterministic Complexity Verifier)
提出されたソリューションを評価し、機能的な正当性とアルゴリズム的な最適性を区別するために、3層の検証器を用いる：

レイヤー1 (静的AST解析): コードを解析し、ループのネスト、再帰、データ構造に基づいて時間/空間計算量を推定する。
レイヤー2 (アルゴリズム・タグ検証): 期待されるアルゴリズム（例：セグメント木のための遅延伝搬）の構造的な証拠の有無、および禁止されたアルゴリズムの不在を確認する。
レイヤー3 (較正済みランタイム・スケーリング): 入力サイズを増加させてソリューションを実行し、ランタイムモデル $T(n) = cn^\alpha (\log n)^\gamma$ に適合させる。適合した指数がターゲットより0.15を超えて大きい場合、ソリューションはペナルティを受ける。

評価指標

標準的な pass@k に加え、ALGOBENCHは計算量を考慮した指標を導入している：

OPTT/OPTS: 正解であり、かつ目標の時間/空間計算量を満たしている提出の割合。
TRAPRATE: ソースのアルゴリズムを構造的に再利用している誤った提出の割合（「旧ソリューション・トラップ」を示す）。
GAPT (効率ギャップ): 適合させたランタイム指数とターゲット指数の間の差。
CONSENS: 制約の大きさが大きくなるにつれてのパフォーマンス低下を測定する。
$\Delta_{gen}$ : ソース問題から生成されたバリアントへのパフォーマンス低下。

主な貢献

フレームワーク: 追跡可能でありながらアルゴリズム的に異なる問題を生成するための自動パイプラインであるALGOBENCHの導入。
変換と検証: 10個の変換オペレータと、古いソリューションを拒絶し新しい計算量を要求することを保証する4つの品質管理システムのデザイン。
ベンチマーク・データセット: 300のソース問題（Codeforces, AtCoder, Kattis, LeetCode Hard）から派生した、メタデータ、リファレンス・ソリューション、およびブルートフォース・オラクルを完備した598個の受理されたバリアント（うち420個を主要実験に使用）の構築。
指標: 漸近的な適合性を評価する指標（OPTT, OPTS, TRAPRATE, GAPT, CONSENS）の提案。
実証的知見: 7つのLLMを6つのプロンプティング戦略で評価し、生成されたバリアントにおいて性能が著しく低下すること、および多くの「正しい」ソリューションが計算量の要件を満たしていないことを示した。

実験結果

パフォーマンスの低下と適応

汎化ギャップ: モデルは、ソース問題からALGOBENCHのバリアントに移行する際に、急激な性能低下を示す。古いモデルは、ソースにおける平均 85.1% のpass@1から、バリアントでは 53.6% へと低下した。最新のフロンティアモデル（GPT-5.4, Claude Opus 4.5）であっても、33.3% 低下した。
計算量のミスマッチ: pass@kとOPTTの間には大きな隔たりが存在する。例えば、GPT-4oはpass@5で72.7%を達成したが、OPTTは63.6%にとどまった。これは、合格したソリューションの多くが不適切なアルゴリズムを使用していたことを示している。
検索のリスク: ソース問題をコンテキストとして使用する検索拡張生成（RAG）は、しばしば TRAPRATE を上昇させた。Gemini 2.5 Flashにおいて、RAGはトラップ率を3.6%から30.0%へと上昇させ、検索がモデルを（現在は無効となった）元のソリューションに固定してしまうことを示唆している。

エラー分析

400件の失敗した提出の分析により、失敗は実装レベルではなく、主にアルゴリズム的なものであることが明らかになった：

旧ソリューション・トラップ (42.3%): モデルがソースのアルゴリズムを実装しており、公開されている例題には合格するが、隠されたトラップテストで失敗する。
低速すぎ (21.8%): モデルは正しいアプローチを特定しているが、必要な最適化（例： $O(N^2)$ から $O(N \log N)$ への切り替え）を見落としている。
実装上のバグ: 失敗のわずか 9.0% を占める。

感度と汚染

制約感度: 入力境界が増加する（例： $N=10K \to 5K$ ）につれて、性能は急激に低下した。これは、二次関数的な解法がタイムアウトする箇所と正確に一致している。
汚染効果: モデルは、新しい問題（2024年）よりも古いソース問題（2020年）において有意に高い性能を示しており、記憶を示唆している。しかし、ALGOBENCHのバリアントにおいては、ソース問題の公開年に関わらず一貫して困難であったため、この差は縮まった。

意義と主張

本論文は、ALGOBENCHが標準的なコードベンチマークとは異なる能力を評価していると主張している。それは、記憶されたテンプレートに頼るのではなく、未知の制約に対してアルゴリズム的推論を適応させる能力である。

機能的正当性を超えて: 本ベンチマークは、高い合格率が漸近的な適合性を保証しないことを示している。多くのモデルは、機能的には正しいがアルゴリズムとしては非効率なソリューションを生成している。
記憶への耐性: ソースの解法が失敗する問題を自動生成することで、ALGOBENCHは学習データの汚染リスクを軽減し、真のアルゴリズム的推論のより信頼できる尺度を提供する。
診断的価値: 本フレームワークは、従来のベンチマークでは隠されてしまう特定の失敗モード（例：グリーディからDPへの移行不能、あるいは動的な更新の処理失敗）を特定する。

著者らは、現在のLLMは馴染みのあるテンプレートが通用しない状況で苦戦しており、アルゴリズム的推論の将来の進歩には、パターンマッチングではなく、真の適応を要求するベンチマークが必要であると結論付けている。