测试大模型能否写出有明确时间空间复杂度的代码
BigO(Bench) -- Can LLMs Generate Code with Controlled Time and Space Complexity?
- 构建可自动分析代码复杂度的评测工具与数据集
- 覆盖3105个编程题，超百万解法含复杂度标签
- 发现顶尖模型写代码强但理解复杂度能力弱
我们提出BigO(Bench)，一个新型编码评测基准，用于评估生成式语言模型在理解与生成具有指定时间与空间复杂度代码方面的能力。该基准填补了现有评估中忽视模型对计算复杂度认知能力的空白。BigO(Bench) 包含工具，可基于性能剖析数据自动推断任意Python函数的算法复杂度，包括人类或大模型生成的解答。该数据集包含3,105个编程问题和1,190,250个来自编程竞赛的解法，均标注了由复杂度框架推导出（合成）的时间与空间复杂度标签，以及大量输入规模下的运行时与内存占用值。我们对多个前沿语言模型在此基准上的表现进行了评估，揭示其在处理复杂度要求时的优势与不足。特别是，采用令牌-空间推理的模型在代码生成上表现出色，但在复杂度理解方面表现平平，暗示其可能无法泛化到训练阶段未获奖励的任务。
原文摘要 · Abstract (English)
We introduce BigO(Bench), a novel coding benchmark designed to evaluate the capabilities of generative language models in understanding and generating code with specified time and space complexities. This benchmark addresses the gap in current evaluations that often overlook the ability of models to comprehend and produce code constrained by computational complexity. BigO(Bench) includes tooling to infer the algorithmic complexity of any Python function from profiling measurements, including human- or LLM-generated solutions. BigO(Bench) also includes of set of 3,105 coding problems and 1,190,250 solutions from Code Contests annotated with inferred (synthetic) time and space complexity labels from the complexity framework, as well as corresponding runtime and memory footprint values for a large set of input sizes. We present results from evaluating multiple state-of-the-art language models on this benchmark, highlighting their strengths and weaknesses in handling complexity requirements. In particular, token-space reasoning models are unrivaled in code generation but not in complexity understanding, hinting that they may not generalize well to tasks for which no reward was given at training time.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。