BigO(Bench) -- Can LLMs Generate Code with Controlled Time and Space
  Complexity?
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.
67dbd897a3b9c06eb0b6988e
Pierre Chambon
extracted_pending
2025-03-20T08:58:00.216Z
65e8c0e40a099ee0c1302e57
/avatars/3905f563be224c0c296dc5c942329d8d.svg
Pierre Chambon
user
pierrechambon
67dbd897a3b9c06eb0b6988f
Baptiste Roziere
admin_assigned
2025-03-21T13:09:01.044Z
62d063dac375d0c84255b9a1
/avatars/de0fc34bad8c761210c0895ebfa4feba.svg
Baptiste Roziere
user
broz
67dbd897a3b9c06eb0b69890
Benoit Sagot
admin_assigned
2025-03-21T13:09:08.259Z
602ba2a739515f8d31237967
/avatars/ef534712ca682bf74ec7eef17d3d1b5f.svg
Benoît Sagot
user
sagot
67dbd897a3b9c06eb0b69891
Gabriel Synnaeve
admin_assigned
2025-03-21T13:09:15.204Z
630eac7931970d1cd4fbacf2
/avatars/b7ccbddfa745db854dc342be1327cd53.svg
Gabriel Synnaeve
user
gsynnaeve
BigO(Bench) -- Can LLMs Generate Code with Controlled Time and Space
  Complexity?
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.
BigO(Bench) evaluates generative language models' ability to understand and generate code with specific time and space complexities.
generative language models coding benchmark algorithmic complexity complexity framework token-space reasoning