【論文解説】AIはプログラミングの「思考力」をどう評価する？動的計画法におけるLLMの採点能力を認知診断モデルで分析

1. はじめに：なぜAIのコード採点に「思考スキル」の診断が必要か？

近年、大規模言語モデル（LLM）はコード生成において目覚ましい進歩を遂げています。簡単なプログラミング問題であれば、まるで人間が書いたかのようなコードを生成する能力は、多くの人を驚かせました。しかし、より複雑なアルゴリズム問題、特に「動的計画法（Dynamic Programming, DP）」のような問題になると、その性能はまだ一貫性に欠けます。

現在のAIコード評価の主流は、多くの場合「pass@k」のようなブラックボックス的な指標に依存しています。これは、提出されたコードがテストケースをどれだけ通過したかを示すものであり、「正解か不正解か」という結果のみを評価します。しかし、プログラミング教育において重要なのは、単にコードが動くかどうかだけではありません。もしコードが失敗した場合、それが「なぜ」失敗したのか、どの「思考スキル」が欠けていたのかを理解することが、学習者にとっては非常に価値があります。

例えば、PythonやJavaScriptのコードで「タイムアウト」が発生した場合と、「誤った結果」が返された場合では、原因となる思考プロセスが全く異なります。タイムアウトは「最適化の欠如」、誤った結果は「ロジックの誤り」を示唆するかもしれません。AIが単に「不正解」とだけ返した場合、学習者は次に何を改善すべきか分かりにくいでしょう。このような背景から、本記事で紹介する論文は、AIがプログラミングコードの採点を通じて、学習者の「認知スキル」をどれだけ診断できるかを深く掘り下げています。

2. 紹介する論文の概要

研究の目的

この研究の主な目的は、言語モデル（LLMおよびSLM）がアルゴリズム問題、特に動的計画法（DP）に対して、単なる正誤判定を超えて、「推論」に基づいた診断的な評価を提供できるかを明らかにすることです。具体的には、以下の2つの問いに答えることを目指しています。

1. 現在のLLMやSLMは、アルゴリズム問題に対して推論しているのか、それとも単に記憶されたソリューションのパターンマッチングをしているだけなのか？
2. もし推論しているとすれば、その推論はどの程度まで及ぶのか？

特に、AIの評価における「推論と生成のギャップ」と「診断的評価の不足」という2つの課題に焦点を当てています。

研究の方法

本研究では、以下の4つの段階を経て、言語モデルの採点能力を詳細に分析しました。

1. データ準備とQ-Matrix設計：

   • 問題選定：AtCoderの動的計画法（DP）問題28問を選定。うち約29%は2024年以降のコンテストから抽出され、学習データ汚染（contamination）のリスクを低減しています。これらの問題は、線形DP、グリッド/ツリーDP、部分集合DP、確率DP、最適化DPの5つのカテゴリに分類されました。
   • Q-Matrixの構築：各問題に必要とされる5つの潜在的スキル（K1: 問題分解、K2: 状態表現、K3: 遷移ロジック、K4: 境界条件、K5: 時間/空間最適化）をマッピングしたQ-Matrixを手作業で作成しました。
   • 人間が書いた解答の収集：各問題について、正解（AC）10件と不正解（WA/TLE/MLE）10件のPythonによる人間解答を合計560件収集しました。

2. 実験グループの設定：

   • グループA（LLMを採点者として利用）：Claude Sonnet 4.6とGPT-5.5の2つのLLMに、人間の解答を採点させました。
   • グループB（SLMを採点者として利用）：Llama-3.1-8B、Granite-4.1-8B、Phi-4-mini-3.8Bの3つのSLMに、人間の解答を採点させました。
   • グループC（SLMをコード生成者として利用）：同じ3つのSLMに、28問のDP問題を解かせ（合計84件のAI生成コード）、それらのコードは人間が手動で採点しました。これにより、「推論」と「生成」の能力差を比較します。

3. 応答行列の生成：

   • 採点者モデルの評価（グループA, B）と、人間によるAI生成コードの評価（グループC）に基づき、各解答のスキル習得度を1（習得）または0（未習得）で示す応答行列を作成しました。

4. 認知診断モデル（DINA）の適用：

   • DINAモデル（Deterministic Input, Noisy "And" Gate）を用いて、各モデルの採点行動における「Slip（スキルを習得しているのに見落とす確率）」と「Guess（スキルを習得していないのに偶然正しく採点する確率）」を推定しました。
   • さらに、Grader Reliability Index (GRI)を導入し、モデルの信頼性を評価しました。特に幻覚的な習得（高いGuess）には強いペナルティを課す設定（k=5）が用いられました。

3. 研究結果のポイント3つ

この研究から、言語モデルのプログラミング採点能力に関して、以下の3つの重要なポイントが明らかになりました。

4. ADVANCEの現場から見た実感

堺市南区のプログラミングスクールADVANCEで実際にプログラミングを教えている講師としての意見は以下の三つです。

5. 保護者の方へ：家庭でできること

今回の論文で明らかになったAIの採点能力や、推論と生成の非対称性は、子どもたちのプログラミング学習にも重要な示唆を与えてくれます。ご家庭でできることとして、以下の3つのポイントを意識してみてください。

6. 参考文献

1. B. Liu, S. Bubeck, R. Eldan, J. Kulkarni, Y. t. Li, A. Nguyen, R. Ward, Y. Zhang, Tinygsm: Achieving >80% on gsm8k with small language models, arXiv preprint arXiv:2312.09241 (2023). URL: https://arxiv.org/abs/2312.09241.
2. N. Jain, K. Han, A. Gu, W.-D. Li, F. Yan, T. Zhang, S. Wang, A. Solar-Lezama, K. Sen, I. Stoica, Livecodebench: Holistic and contamination-free evaluation of large language models for code, arXiv preprint arXiv:2403.07974 (2024). URL: https://arxiv.org/abs/2403.07974.
3. C. Wang, J. Lin, K. R. Koedinger, Leveraging large language models for identifying knowledge components, arXiv preprint arXiv:2511.09935 (2025). URL: https://arxiv.org/abs/2511.09935.
4. H. Li, Q. Dong, J. Chen, H. Su, Y. Zhou, Q. Ai, Z. Ye, Y. Liu, Llms-as-judges: A comprehensive survey on llm-based evaluation methods, arXiv preprint arXiv:2412.05579 (2024). URL: https://arxiv.org/abs/2412.05579.
5. K. Wataoka, T. Takahashi, R. Ri, Self-preference bias in llm-as-a-judge, arXiv preprint arXiv:2410.21819 (2024). URL: https://arxiv.org/abs/2410.21819.
6. J. Moon, Y. Hwang, D. Lee, T. Kang, Y. Kim, K. Jung, Don’t judge code by its cover: Exploring biases in llm judges for code evaluation, arXiv preprint arXiv:2505.16222 (2025). URL: https://arxiv.org/abs/2505.16222.
7. Y. Song, H. Zhang, C. Eisenach, S. M. Kakade, D. Foster, U. Ghai, Mind the gap: Examining the self-improvement capabilities of large language models, in: International Conference on Learning Representations (ICLR), 2025. URL: https://openreview.net/forum?id=Hgv0tqgaiA.
8. J. Saad-Falcon, E. K. Buchanan, M. F. Chen, T.-H. Huang, B. McLaughlin, T. Bhathal, S. Zhu, B. Athiwaratkun, F. Sala, S. Linderman, et al., Shrinking the generation-verification gap with weak verifiers, arXiv preprint arXiv:2506.18203 (2025). URL: https://arxiv.org/abs/2506.18203.
9. B. W. Junker, K. Sijtsma, Cognitive assessment models with few assumptions, and connections with nonparametric item response theory, Applied Psychological Measurement 25 (2001) 258–272. doi:10.1177/01466210122032064.
10. J. de la Torre, The generalized dina model framework, Psychometrika 76 (2011) 179–199. doi:10.1007/s11336- 011- 9207- 7.
11. M. B. Garcia, M. Tian, M. Chen, Profiling the skill mastery of introductory programming students: A cognitive diagnostic modeling approach, Education and Information Technologies (2024). doi:10.1007/s10639- 024- 13039- 6.
12. Y. Shi, T. Schmucker, M. Chi, T. Barnes, T. Price, Kc-finder: Automated knowledge component discovery for programming problems, in: Proceedings of the 16th International Conference on Educational Data Mining (EDM), 2023. URL: https://educationaldatamining.org/edm2023/proceedings/.
13. Y. Shi, M. Chi, T. Barnes, T. Price, Code-dkt: A code-based knowledge tracing model for programming tasks, in: Proceedings of the 15th International Conference on Educational Data Mining (EDM), 2022. URL: https://arxiv.org/abs/2206.03545.
14. X. Chen, J. Zhang, T. Zhou, F. Zhang, Llm-cdm: A large language model enhanced cognitive diagnosis for intelligent education, IEEE Access 13 (2025) 47165–47180. doi:10.1109/ACCESS. 2025.3549309.