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