大模型
arxiv.org ·
BigO(Bench)：LLM 能否生成具有受控时间和空间复杂度的代码？
该论文提出 BigO(Bench)，用于评估生成式语言模型理解和生成指定时间与空间复杂度代码的能力，填补现有评测忽视计算复杂度约束的空白。基准包含从 profiling 测量推断任意 Python 函数算法复杂度的工具，以及 3,105 道编程题、1,190,250 个来自 Code Contests 的解答，附带推断（合成）的时间与空间复杂度标签及多输入规模下的运行时间和内存占用数据。作者评测了多个前沿语言模型，发现 token-space 推理模型在代码生成上表现突出，但在复杂度理解上并非如此，暗示其可能难以泛化到训练时未获奖励的任务。
AI推荐理由 arXiv 论文（v3，2026-09-22 修订），作者含 Meta 的 Baptiste Roziere、Gabriel Synnaeve 等，事实明确、信息密度高。核心新信息是 BigO(Bench)：一个评估 LLM 生成具有指定时间/空间复杂度代码能力的基准，含从 profiling 测量推断 Python 函数算法复杂度的工具，以及 3,105 道题、1,190,250 个 Code Contests 解答并标注推断（合成）复杂度标签和不同输入规模下的运行时间/内存数据。摘要指出 token-space 推理模型在代码生成上领先但在复杂度理解上并非如此，提示其可能难以泛化到训练时未给奖励的任务。局限：复杂度标签为推断的合成标签，非人工验证；摘要未给出具体模型分数。
82
正文
Computer Science > Computation and Language
arXiv:2503.15242 (cs)
[Submitted on 19 Mar 2025 (v1), last revised 22 Sep 2026 (this version, v3)]
Title:BigO(Bench): Can LLMs Generate Code with Controlled Time and Space Complexity?
Authors:Pierre Chambon, Baptiste Roziere, Benoit Sagot, Gabriel Synnaeve
View a PDF of the paper titled BigO(Bench): Can LLMs Generate Code with Controlled Time and Space Complexity?, by Pierre Chambon and 3 other authors
View PDF
HTML (experimental)
Abstract: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.
Subjects:
Computation and Language (cs.CL); Artificial Intelligence (cs.AI); Computational Complexity (cs.CC)
Cite as:
arXiv:2503.15242 [cs.CL]
(or
arXiv:2503.15242v3 [cs.CL] for this version)
https://doi.org/10.48550/arXiv.2503.15242
Focus to learn more
arXiv-issued DOI via DataCite
Submission history
From: Pierre Chambon [view email]
[v1]
Wed, 19 Mar 2025 14:19:57 UTC (2,796 KB)
[v2]
Thu, 20 Mar 2025 17:58:17 UTC (2,791 KB)
[v3]
Tue, 22 Sep 2026 16:48:58 UTC (5,258 KB)
Full-text links:
Access Paper:
View a PDF of the paper titled BigO(Bench): Can LLMs Generate Code with Controlled Time and Space Complexity?, by Pierre Chambon and 3 other authors
View PDF
HTML (experimental)
TeX Source
view license
Current browse context:
cs.CL
new
|
recent
| 2025-03
Change to browse by:
cs
cs.AI
cs.CC
References & Citations
NASA ADS
Google Scholar
Semantic Scholar
export BibTeX citation
Loading...
BibTeX formatted citation
×
loading...
Data provided by:
Bookmark
Bibliographic Tools
Bibliographic and Citation Tools
Bibliographic Explorer Toggle
Bibliographic Explorer (What is the Explorer?)
Connected Papers Toggle
Connected Papers (What is Connected Papers?)
Litmaps Toggle
Litmaps (What is Litmaps?)
scite.ai Toggle
scite Smart Citations (What are Smart Citations?)
Code, Data, Media
Code, Data and Media Associated with this Article
alphaXiv Toggle
alphaXiv (What is alphaXiv?)
Links to Code Toggle
CatalyzeX Code Finder for Papers (What is CatalyzeX?)
DagsHub Toggle
DagsHub (What is DagsHub?)
GotitPub Toggle
Gotit.pub (What is GotitPub?)
Huggingface Toggle
Hugging Face (What is Huggingface?)
ScienceCast Toggle
ScienceCast (What is ScienceCast?)
Demos
Demos
Replicate Toggle
Replicate (What is Replicate?)
Spaces Toggle
Hugging Face Spaces (What is Spaces?)
Spaces Toggle
TXYZ.AI (What is TXYZ.AI?)
Related Papers
Recommenders and Search Tools
Link to Influence Flower
Influence Flower (What are Influence Flowers?)
Core recommender toggle
CORE Recommender (What is CORE?)
Author
Venue
Institution
Topic
About arXivLabs
arXivLabs: experimental projects with community collaborators
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Which authors of this paper are endorsers? |
Disable MathJax (What is MathJax?)