BigO(Bench): Can LLMs Generate Code with Controlled Time and Space Complexity?
Pierre Chambon, Baptiste Roziere, Benoit Sagot, Gabriel Synnaeve
cs.CL, cs.AI, cs.CC
2025-03-19
FAIR与Inria用运行时拟合，给3105道竞赛题和119万份解打上时空复杂度标签。Qwen3按指定时间复杂度生成All@1仅6.5%，R1 Llama 70B预测All@1为41.4%。
HumanEval、MBPP已经把短函数「写对」做到90%到95% pass@1，SWE-Bench把难度换到仓库级修issue。面试和线上事故还卡在另一层：这段代码的时间和额外空间是哪一档大O，以及能不能按给定、且可行的复杂度再写一版能过测试的解。
先前数据集多半停在五档时间复杂度分类，如CoRCoD、TASTY、CodeComplex；RACE大约100条测例，只比运行时间像不像人写的。绝对耗时又绑死硬件和那组测例。Meta FAIR与Inria的BigO(Bench)改成三件可执行的事：预测已有解的时空复杂度，按指定可行复杂度生成能过公开、私有和生成测试的解，再在同一类里把拟合曲线压得比人类提交更扁。
DeepSeek-R1在CodeForces上pass@1超过70%，指定复杂度生成时只剩4.8%。预测相对Llama 4 Maverick也只高6.8个点。写对和解对约束，不是同一项能力。
金标不是教材上的渐近证明，是CPython上的最坏增长。框架吃一段Python和一份样例输入，把各参数按随机、复制、恒等策略单独或联合放大，丢进Bubblewrap沙箱。Cprofiler记时间，tracemalloc记内存，非负最小二乘拟合O(1)、O(n)、O(n log n)、O(n²)以及多参数类。残差最小、再加简单性偏好的那一档当标签；同类里留下曲线系数，给「同样是O(n)、常数更小」排序。
相对人工理论标注，时间84%、空间82%吻合，各125条。二十次重复的自洽性91.9%与89.1%。约84%的题目失败率低于30%，4.5%的题失败率超过0.9，常见原因是输入解析失败或测试没盖到的边角。单副本跑完全输入范围只需十分之一算力，仍能复现96.6%的时间复杂度标签。
数据来自Code Contests的Python正确提交：8139题、1,485,888解滤到3105题、1,190,250解。时间测试集311题、640解、11类；空间308题、636解、5类，两集只重叠63题。线性时间占全部解38%，常数时间20%；空间更偏，O(n) 47%、O(1) 25%。要把原始输入流变成可缩放变量，Llama 3.1 405B的BckTr@10（解析后再打印必须还原）为58.1%，多解多遍后82%的题能用。
三个任务都先按复杂度类、再按题做宏平均。Pass@k按每一类单独计；Best@k只看该题最优类；All@k要求一道题所有类同时做对。All@1挡住「背过最优模板就过关」：人觉得次优更好写，模型死磕最优，很少用一句无用的sort把线性解变成线性对数。
14个常用代码与推理模型，instruct、零样本。o1-mini大量空回复被丢掉，分数是乐观上界。R1蒸馏版大约用了2倍节点、5倍墙钟和16倍生成token。
| 模型 | 任务 | 指标 | 结果 |
| Qwen3 32B | 时间复杂度生成 | All@1 | 6.5% |
| DeepSeek-R1 Llama 70B | 时间复杂度预测 | All@1 | 41.4% |
| DeepSeek-R1 Llama 70B | 时间复杂度生成 | All@1 | 4.8% |
| Llama 3.1 Nemotron-Ultra | 空间复杂度生成 | All@1 | 5.6% |
| 头部模型 | 时间预测 / 时间生成 | pass@1 | 64.2% / 33.5% |
| Qwen2.5-Coder 32B | 空间复杂度预测 | All@1 | 12.6% |
| o1-mini / R1 Llama / Nemotron | 空间复杂度预测 | All@1 | 8.1% / 10.4% / 10.3% |
预测相对「永远猜O(n)」的基线有分；生成的对照是同一套题、去掉复杂度约束的Llama 3.1 70B。提示里再加「尽量优化且满足复杂度」，时间生成All@1平均再掉12%，GPT-4o和o1-mini掉约30%。同一复杂度类里用曲线系数跟人比，Qwen3时间任务全程百分位44.0；只统计带星模型都写出过至少一解的子集，则到79.6。
空间预测上，Qwen2.5-Coder超过若干推理模型。后者会把「额外空间」想歪，即使prompt已经写清。推理模型从预测角度能认出一题的所有类，生成时却交不出次优类。
2000题、2万解（生成约2200万token，预测1800–1900万）对Llama 3.1 70B做10个epoch指令微调：预测几乎不涨，生成微调还略伤程序合成。标准SFT搬不动这层。推理模型把纯写对做成断层，复杂度任务上大家挤在一起。
多了一根比pass@1硬、又能在沙箱里复现的尺子，不必上仓库级agent评测的成本。代码、数据和榜已经公开。
对要控延迟、控内存的代码助手，结论很具体：把推理写在token里的模型把竞赛写对率拉得很高，训练时没为「按指定大O出解」给过奖励，这个能力不会顺便出现。
这是评测贡献，不是新的训练算法。相关工作里SwiftSolve拿它当评测床；作者把PPO和执行反馈强化学习写成未做的方向，这篇没有验证。
框架会错。最坏输入可能踩偏，CPU计时有噪声，作者提到虚拟核或许更稳。金标是经验曲线。题目全是Python竞赛题，C++与Java的常数、标准库差异没测。
Code Contests早于大多数被测模型，污染是作者点名的。测试集不用官方split，因为官方集区分度不够，也缺少「一题多类」。没有多轮prompt。完整实验约12,000 GPU小时加180,000 CPU小时，复现门槛高。
微调失败只说明再喂同类数据不够，推不出换强化学习就行。那句实验没做。