EMNLP Findings2025
CodeComplex: Dataset for Worst-Case Time Complexity Prediction
Seung-Yeop Baik, Joonghyuk Hahn, Jungin Kim, Aditi, Mingi Jeon, Yo-Sub Han, Sang-Ki Ko
Abstract
Reasoning ability of large language models (LLMs) is a crucial ability, especially in complex decision-making tasks.One significant task to show LLMs' reasoning capability is code time complexity prediction, which involves various intricate factors such as the input range of variables and conditional loops.Current benchmarks fall short of providing a rigorous assessment due to limited data, language constraints, and insufficient labeling.They do not consider time complexity based on input representation and merely evaluate whether predictions fall into the same class, lacking a measure of how close incorrect predictions are to the correct ones.To address these dependencies, we introduce CodeComplex, the first robust and extensive dataset designed to evaluate LLMs' reasoning abilities in predicting code time complexity.CodeComplex comprises 4,900 Java codes and an equivalent number of Python codes, overcoming language and labeling constraints, carefully annotated with complexity labels based on input characteristics by a panel of algorithmic experts.Additionally, we propose specialized evaluation metrics for the reasoning of complexity prediction tasks, offering a more precise and reliable assessment of LLMs' reasoning capabilities.We release our dataset and baseline models publicly to encourage the relevant (NLP, SE, and PL) communities to utilize and participate in this research.Our code and data are available at https: //github.com/sybaik1/CodeComplex. OpenAI.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
Lineage
- UniXcoder: Unified Cross-Modal Pre-training for Code Representation cites CodeBERT: A Pre-Trained Model for Programming and Natural Languages
- UniXcoder: Unified Cross-Modal Pre-training for Code Representation cites GraphCodeBERT: Pre-training Code Representations with Data Flow
Builds on4
- CodeBERT: A Pre-Trained Model for Programming and Natural LanguagesZhangyin Feng, Daya Guo, Duyu Tang, Nan Duan et al.EMNLP Findings 2020 · 2,828 citations
- GraphCodeBERT: Pre-training Code Representations with Data FlowDaya Guo, Shuo Ren, Shuai Lu, Zhangyin Feng et al.ICLR 2021 · 1,644 citations
- Jigsaw: Large Language Models meet Program SynthesisNaman Jain, Skanda Vaidyanath, Arun Iyer, Nagarajan Natarajan et al.ICSE 2022 · 134 citations
- UniXcoder: Unified Cross-Modal Pre-training for Code RepresentationDaya Guo, Shuai Lu, Nan Duan, Yanlin Wang et al.ACL 2022
Related papers
- Reasoning Runtime Behavior of a Program with LLM: How Far are We?Junkai Chen, Zhiyuan Pan, Xing Hu, Zhenhao Li et al.ICSE 2025 · 5 citations
- NPHardEval: Dynamic Benchmark on Reasoning Ability of Large Language Models via Complexity ClassesLizhou Fan, Wenyue Hua, Lingyao Li, Haoyang Ling et al.ACL 2024 · 8 citations
- Do Language Models Have a Common Sense regarding Time? Revisiting Temporal Commonsense Reasoning in the Era of Large Language ModelsRaghav Jain, Daivik Sojitra, Arkadeep Acharya, Sriparna Saha et al.EMNLP 2023 · 17 citations
- When Do Program-of-Thought Works for Reasoning?Zhen Bi, Ningyu Zhang, Yinuo Jiang, Shumin Deng et al.AAAI 2024
- CodeCrash: Exposing LLM Fragility to Misleading Natural Language in Code ReasoningMan Ho Lam, Chaozheng Wang, Jen-Tse Huang, Michael R. LyuNeurIPS 2025 · 16 citations
