Complexity-Constraint Code Evaluation: A Benchmark for Time Complexity Compliance in LLM-Generated Code

Chen, Li-Guo

doi:10.1007/s11390-025-5518-5

Complexity-Constraint Code Evaluation: A Benchmark for Time Complexity Compliance in LLM-Generated Code

2026-05-01

1

PRE

AI

DOI：10.1007/s11390-025-5518-5

原文链接

原文求助

摘要

En 中文

在代码生成的大型语言模型（Code LLMs）能够生成功能正确的代码方面表现优异，但现有基准测试忽视了一个关键方面：对显式时间复杂度约束的遵守。我们提出了复杂度约束代码评估（C3E），一种新型基准测试，用于评估功能正确性和复杂度合规性，涵盖可行和不可行场景。C3E能够精确区分渐近复杂度类别，并测试模型在理论上不可能的约束下的鲁棒性。我们提出的复杂度对齐分数（CAS）将正确性和复杂度遵守整合为一个统一指标，通过理论分析而非昂贵的执行进行评估。实验结果表明，当前最优模型存在显著差距：GPT-4o达到81%的正确率，但仅31%的CAS，显示出较差的复杂度遵守能力。值得注意的是，除GPT-4o等先进模型外，大多数模型无法识别不可行约束。这些发现强调了复杂度感知评估的必要性，将C3E定位为推动Code LLMs现实世界编码可靠性进步的必要工具。C3E基准测试可在获取。

Keyword:

large language model for code (Code LLM)

code evaluation

benchmark dataset

time complexity constraint

Complexity-Constraint Code Evaluation: A Benchmark for Time Complexity Compliance in LLM-Generated Code

摘要

期刊

机构

引用论文