Can LLMs Generate High-Quality Test Cases for Algorithm Problems? TestCase-Eval: A Systematic Evaluation of Fault Coverage and Exposure

生成日: 2026-05-24 02:20

# Can LLMs Generate High-Quality Test Cases for Algorithm Problems? TestCase-Eval: A Systematic Evaluation of Fault Coverage and Exposure

- TestCase-Eval は、Codeforces の 500 問と人間が書いた 100,000 件の解答を用い、LLM が競技プログラミングのテストケースを作れるかを測るベンチマークである。
- 評価は、広く誤答を検出する Fault Coverage と、特定の誤った実装を狙って失敗させる Fault Exposure の二つからなる。
- 最良の Qwen3-32B でも Fault Exposure は 43.8% にとどまり、人間の上級者による 93.3% とは大きな差が残った。

## Abstract（日本語訳）

本論文では、LLM によるテストケース生成を体系的に評価するための新しいベンチマーク、TestCase-Eval を導入する。TestCase-Eval は、Codeforces プラットフォームから得た 500 件のアルゴリズム問題と、人間が作成した 100,000 件の解答を含む。このベンチマークは二つの重要なタスクに焦点を当てる。第一は Fault Coverage であり、LLM が生成したテスト集合が多様な入力状況をどの程度調べ、広い範囲の潜在的な失敗モードを覆えるかを測る。第二は Fault Exposure であり、LLM が特定の誤ったコード実装を露呈させるように調整されたテスト入力を作成できるかを評価する。TestCase-Eval 上で、オープンソースおよびプロプライエタリの最先端 LLM 19 種を包括的に評価し、アルゴリズム問題に対して有効なテストケースを生成する際の強みと限界について知見を示す。

## 論文の面白いところ

この論文の面白さは、テストケース生成を「それらしい入力を作る」問題ではなく、「実際に誤った提出を落とせるか」という基準で測る点にある。通常の Line Coverage や Branch Coverage は、コードの行や分岐が実行されたかを測るが、競技プログラミングの誤りはそれだけでは見えにくい。たとえば、全ての分岐を通っても、境界条件や計算量の見積もりを誤った実装は正解にならない。TestCase-Eval は、Codeforces に実際に提出された誤答を評価対象にするため、作り物のバグだけを扱うより現実に近い。著者らは、問題文だけから広く誤答を検出する能力と、問題文に加えて誤ったコードを読んで狙い撃ちする能力を分けて測る。この分離により、LLM が単に変わった入力を出しているのか、コードの欠陥を読んで入力を設計しているのかが見えやすくなる。結果として、現在の強いモデルでも後者はかなり難しいことが示された。コード生成支援で LLM を使う場合、生成コードの検査を LLM に任せきれるかという実務上の問いにもつながる。

## 問題設定

対象は、アルゴリズム問題に対するテスト入力の生成である。問題文には、入力形式、出力形式、制約、例が含まれ、モデルはそれを読んで有効な入力を作る。著者らは Codeforces の 2024 年のコンテストから 500 問を集め、special judge を必要とする問題は除いた。これは、一つの入力に複数の正解出力があり得る問題では、オフライン評価が不安定になるためである。各問題について、C++、Python、Java の人間による不正解提出を収集し、最終的に 100,000 件の解答を評価に用いた。誤答には Wrong Answer、Runtime Error、Time Limit Exceeded、Memory Limit Exceeded などの判定が付いている。誤りの難しさは、Codeforces で最初に失敗したテスト番号をもとに Easy、Medium、Hard に分けられる。早いテストで落ちる提出は見つけやすく、後半のテストまで通る提出は、より細かい条件を突く入力が必要になる。

## 提案手法

TestCase-Eval は、二つの評価タスクで構成される。Fault Coverage では、モデルに問題文だけを与え、N 個のテスト入力を生成させる。各入力を多数の誤った提出に対して実行し、少なくとも一つの入力で落とせた誤答の割合を Coverage@N として測る。N は 1、5、10、20 で評価され、入力を増やしたときにどれだけ多くの故障パターンを覆えるかを見る。Fault Exposure では、問題文と一つの誤ったコードをモデルに与え、その実装を失敗させる単一の入力を作らせる。これは Codeforces の hacking phase に近く、相手の解法を読んで反例を作る能力を測る。生成された入力は ExecEval の sandbox 環境で実行され、正しいコードと誤ったコードの出力が異なるか、または誤ったコードが実行時エラーなどを起こすかで判定される。実験では Direct Output prompt と Chain-of-Thought prompt の両方を用い、19 種のモデルを同じ枠組みで比べている。

## 結果

結果は、現在の LLM にとってこの課題がまだ難しいことを示している。Fault Exposure では、人間の上級者二名の平均が 93.3% であるのに対し、最良の Qwen3-32B は 43.8% だった。GPT-4.1 は 36.5%、GPT-4o は 31.7% であり、プロプライエタリモデルが一貫して優位という結果ではなかった。Fault Coverage では、Qwen3-32B が Coverage@1 で 50.8、Coverage@20 で 95.7 を記録し、広くテストを出す能力では比較的高い値を示した。ただし、人間は Coverage@20 で 97.2 まで達しており、単純な入力生成でも差は残る。推論向けモデルは全体に強く、Qwen3 系や R1-Distill-Qwen-32B が Fault Exposure でも上位に来た。Chain-of-Thought prompt は Direct Output prompt より有効で、特に欠陥を狙って入力を作る場面で差が出た。誤りの種類別には、モデルは Wrong Answer や Runtime Error を露呈させるのが比較的得意で、Time Limit Exceeded や Memory Limit Exceeded のような資源制約型の誤りは苦手だった。これは、論理的な反例を作る能力と、計算量やメモリ使用量を破綻させる入力を設計する能力が同じではないことを示している。

## 具体例

たとえば、配列を並べ替えて条件を満たす組の数を数える問題があるとする。問題文には、配列の長さ、値の範囲、複数テストケースの形式が与えられている。Fault Coverage では、モデルは問題文だけを読み、空に近い配列、同じ値だけの配列、最大値と最小値が交互に出る配列などを一つの入力にまとめて出す。期待されるのは、そうした入力が、境界条件を忘れた解法や重複値を誤って扱う解法をまとめて落とすことである。Fault Exposure では、さらに誤った C++ コードが与えられる。もしそのコードが、同じ値が複数ある場合に組を二重に数えてしまう実装なら、モデルは重複値を多く含む短い配列を作る必要がある。正しいコードはその入力に対して一つの答えを返し、誤ったコードは異なる答えを返す。間違えやすい点は、入力としては有効でも、与えられた誤りを実際には突けていないケースである。単に大きな値やランダムな列を並べるだけでは、特定の実装上の欠陥に届かないことが多い。

Can LLMs Generate High-Quality Test Cases for Algorithm Problems? TestCase-Eval: A Systematic Evaluation of Fault Coverage and Exposure

TestCase-Eval は、Codeforces の 500 問と人間が書いた 100,000 件の解答を用い、LLM が競技プログラミングのテストケースを作れるかを測るベンチマークである。
評価は、広く誤答を検出する Fault Coverage と、特定の誤った実装を狙って失敗させる Fault Exposure の二つからなる。
最良の Qwen3-32B でも Fault Exposure は 43.8% にとどまり、人間の上級者による 93.3% とは大きな差が残った。

Abstract（日本語訳）

本論文では、LLM によるテストケース生成を体系的に評価するための新しいベンチマーク、TestCase-Eval を導入する。TestCase-Eval は、Codeforces プラットフォームから得た 500 件のアルゴリズム問題と、人間が作成した 100,000 件の解答を含む。このベンチマークは二つの重要なタスクに焦点を当てる。第一は Fault Coverage であり、LLM が生成したテスト集合が多様な入力状況をどの程度調べ、広い範囲の潜在的な失敗モードを覆えるかを測る。第二は Fault Exposure であり、LLM が特定の誤ったコード実装を露呈させるように調整されたテスト入力を作成できるかを評価する。TestCase-Eval 上で、オープンソースおよびプロプライエタリの最先端 LLM 19 種を包括的に評価し、アルゴリズム問題に対して有効なテストケースを生成する際の強みと限界について知見を示す。

論文の面白いところ

この論文の面白さは、テストケース生成を「それらしい入力を作る」問題ではなく、「実際に誤った提出を落とせるか」という基準で測る点にある。通常の Line Coverage や Branch Coverage は、コードの行や分岐が実行されたかを測るが、競技プログラミングの誤りはそれだけでは見えにくい。たとえば、全ての分岐を通っても、境界条件や計算量の見積もりを誤った実装は正解にならない。TestCase-Eval は、Codeforces に実際に提出された誤答を評価対象にするため、作り物のバグだけを扱うより現実に近い。著者らは、問題文だけから広く誤答を検出する能力と、問題文に加えて誤ったコードを読んで狙い撃ちする能力を分けて測る。この分離により、LLM が単に変わった入力を出しているのか、コードの欠陥を読んで入力を設計しているのかが見えやすくなる。結果として、現在の強いモデルでも後者はかなり難しいことが示された。コード生成支援で LLM を使う場合、生成コードの検査を LLM に任せきれるかという実務上の問いにもつながる。

問題設定

対象は、アルゴリズム問題に対するテスト入力の生成である。問題文には、入力形式、出力形式、制約、例が含まれ、モデルはそれを読んで有効な入力を作る。著者らは Codeforces の 2024 年のコンテストから 500 問を集め、special judge を必要とする問題は除いた。これは、一つの入力に複数の正解出力があり得る問題では、オフライン評価が不安定になるためである。各問題について、C++、Python、Java の人間による不正解提出を収集し、最終的に 100,000 件の解答を評価に用いた。誤答には Wrong Answer、Runtime Error、Time Limit Exceeded、Memory Limit Exceeded などの判定が付いている。誤りの難しさは、Codeforces で最初に失敗したテスト番号をもとに Easy、Medium、Hard に分けられる。早いテストで落ちる提出は見つけやすく、後半のテストまで通る提出は、より細かい条件を突く入力が必要になる。

提案手法

TestCase-Eval は、二つの評価タスクで構成される。Fault Coverage では、モデルに問題文だけを与え、N 個のテスト入力を生成させる。各入力を多数の誤った提出に対して実行し、少なくとも一つの入力で落とせた誤答の割合を Coverage@N として測る。N は 1、5、10、20 で評価され、入力を増やしたときにどれだけ多くの故障パターンを覆えるかを見る。Fault Exposure では、問題文と一つの誤ったコードをモデルに与え、その実装を失敗させる単一の入力を作らせる。これは Codeforces の hacking phase に近く、相手の解法を読んで反例を作る能力を測る。生成された入力は ExecEval の sandbox 環境で実行され、正しいコードと誤ったコードの出力が異なるか、または誤ったコードが実行時エラーなどを起こすかで判定される。実験では Direct Output prompt と Chain-of-Thought prompt の両方を用い、19 種のモデルを同じ枠組みで比べている。

結果

結果は、現在の LLM にとってこの課題がまだ難しいことを示している。Fault Exposure では、人間の上級者二名の平均が 93.3% であるのに対し、最良の Qwen3-32B は 43.8% だった。GPT-4.1 は 36.5%、GPT-4o は 31.7% であり、プロプライエタリモデルが一貫して優位という結果ではなかった。Fault Coverage では、Qwen3-32B が Coverage@1 で 50.8、Coverage@20 で 95.7 を記録し、広くテストを出す能力では比較的高い値を示した。ただし、人間は Coverage@20 で 97.2 まで達しており、単純な入力生成でも差は残る。推論向けモデルは全体に強く、Qwen3 系や R1-Distill-Qwen-32B が Fault Exposure でも上位に来た。Chain-of-Thought prompt は Direct Output prompt より有効で、特に欠陥を狙って入力を作る場面で差が出た。誤りの種類別には、モデルは Wrong Answer や Runtime Error を露呈させるのが比較的得意で、Time Limit Exceeded や Memory Limit Exceeded のような資源制約型の誤りは苦手だった。これは、論理的な反例を作る能力と、計算量やメモリ使用量を破綻させる入力を設計する能力が同じではないことを示している。

具体例

たとえば、配列を並べ替えて条件を満たす組の数を数える問題があるとする。問題文には、配列の長さ、値の範囲、複数テストケースの形式が与えられている。Fault Coverage では、モデルは問題文だけを読み、空に近い配列、同じ値だけの配列、最大値と最小値が交互に出る配列などを一つの入力にまとめて出す。期待されるのは、そうした入力が、境界条件を忘れた解法や重複値を誤って扱う解法をまとめて落とすことである。Fault Exposure では、さらに誤った C++ コードが与えられる。もしそのコードが、同じ値が複数ある場合に組を二重に数えてしまう実装なら、モデルは重複値を多く含む短い配列を作る必要がある。正しいコードはその入力に対して一つの答えを返し、誤ったコードは異なる答えを返す。間違えやすい点は、入力としては有効でも、与えられた誤りを実際には突けていないケースである。単に大きな値やランダムな列を並べるだけでは、特定の実装上の欠陥に届かないことが多い。