Elamur Research⌕
☰
home / papers / 2024 / Can Language Models Solve Olympiad Programming?

Can Language Models Solve Olympiad Programming?

Paper · 2024 · Quan Shi, Michael Tang, Karthik Narasimhan et al.

Summary

Widely used code benchmarks such as HumanEval and MBPP are now nearly saturated, so they no longer show where language models fall short in algorithmic reasoning. The authors build the USACO benchmark from 307 USA Computing Olympiad problems. Each problem comes with hidden unit tests, time and memory limits, an expert-written analysis and reference Python code. Competition-programming textbook material is also included for retrieval. The problems are set in narrative scenarios, so solving them requires reasoning tied to the story as well as new, problem-specific algorithms.

Using these resources, the authors test zero-shot prompting, self-reflection and retrieval. Retrieval draws on both similar solved problems (episodic) and textbook knowledge (semantic). Even the strongest model, GPT-4, struggles. Combining self-reflection with episodic retrieval more than doubles its score, yet it still rarely solves problems beyond the bronze tier. In a tutoring study, minimal human hints let GPT-4 solve most problems that no automatic method had cracked. This suggests that pass@k misses latent ability and that methods able to produce human-quality feedback are worth pursuing.

Key points

  • The authors collected 484 problems from contests held between 2011 and 2023. They kept the 307 with full official analyses, each having 10–17 hidden tests and tiers from bronze to platinum. Missing Python solutions were translated by GPT-4 and checked against the tests.
  • Models evaluated: GPT-3.5, GPT-4, Claude-3-sonnet, CodeLlama2-Instruct-7B and Deepseek-Coder-Instruct-7B, scored with the unbiased pass@k metric.
  • GPT-4 reaches 8.7% pass@1 with zero-shot chain-of-thought and 20.2% with self-reflection plus episodic retrieval.
  • With tutoring under strict hint rules, GPT-4 solved 13 of 15 previously unsolved problems (86.7%), while GPT-3.5 solved none. The 15 problems were 13 bronze, 1 silver and 1 gold.
  • Data and code are released at princeton-nlp.github.io/USACOBench.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓Princeton UniversityPrinceton · United States90 works · 39,109 citations

 Fields, topics and concepts

📚 Shelves 6The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksArts and Humanities · 16,039 worksLanguage and Linguistics · 15,891 worksInformation Systems · 1,437 worksComputer Science Applications · 102 works

🧭 Topics 1Research subjects and languages the work is about.Language models & pretraining · 3,320 works

Cite

Cite as Quan Shi, Michael Tang, Karthik Narasimhan and Shunyu Yao. 2024. Can Language Models Solve Olympiad Programming?. arXiv:2404.10952.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.2404.10952 · arXiv 2404.10952

@misc{shi2024can,
  title = {{Can Language Models Solve Olympiad Programming?}},
  author = {Quan Shi, Michael Tang, Karthik Narasimhan and Shunyu Yao},
  year = {2024},
  doi = {10.48550/arxiv.2404.10952},
  eprint = {2404.10952},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.2404.10952}
}

References

30 references, 15 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Agnar Aamodt and Enric Plaza. Case-based reasoning: foundational issues, methodological variations, and system approaches. AI Commun., 7(1):39–59, mar 1994. ISSN 0921-7126. find
  2. Jacob Austin, Augustus Odena, Maxwell Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie Cai, Michael Terry, Quoc Le, et al. Program synthesis with large language models. arXiv preprint arXiv:2108.07732, 2021.
  3. Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, et al. Evaluating large language models trained on code. arXiv preprint arXiv:2107.03374, 2021.
  4. Xinyun Chen, Maxwell Lin, Nathanael Schärli, and Denny Zhou. Teaching large language models to self-debug. arXiv preprint arXiv:2304.05128, 2023. find
  5. Yunfan Gao, Yun Xiong, Xinyu Gao, Kangxiang Jia, Jinliu Pan, Yuxi Bi, Yi Dai, Jiawei Sun, and Haofen Wang. Retrieval-augmented generation for large language models: A survey. arXiv preprint arXiv:2312.10997, 2023.
  6. Daya Guo, Qihao Zhu, Dejian Yang, Zhenda Xie, Kai Dong, Wentao Zhang, Guanting Chen, Xiao Bi, Y Wu, YK Li, et al. Deepseek-coder: When the large language model meets programming–the rise of code intelligence. arXiv preprint arXiv:2401.14196, 2024. find
  7. Dan Hendrycks, Steven Basart, Saurav Kadavath, Mantas Mazeika, Akul Arora, Ethan Guo, Collin Burns, Samir Puranik, Horace He, Dawn Song, and Jacob Steinhardt. Measuring coding challenge competence with apps, 2021.
  8. Yiming Huang, Zhenghao Lin, Xiao Liu, Yeyun Gong, Shuai Lu, Fangyu Lei, Yaobo Liang, Yelong Shen, Chen Lin, Nan Duan, et al. Competition-level problems are effective llm evaluators. arXiv preprint arXiv:2312.02143, 2023. find
  9. Naman Jain, King Han, Alex Gu, Wen-Ding Li, Fanjia Yan, Tianjun Zhang, Sida Wang, Armando Solar-Lezama, Koushik Sen, and Ion Stoica. Livecodebench: Holistic and contamination free evaluation of large language models for code. arXiv preprint arXiv:2403.07974, 2024.
  10. Hung Le, Yue Wang, Akhilesh Deepak Gotmare, Silvio Savarese, and Steven Chu Hong Hoi. Coderl: Mastering code generation through pretrained models and deep reinforcement learning. Advances in Neural Information Processing Systems, 35:21314–21328, 2022.
  11. Jierui Li, Szymon Tworkowski, Yingying Wu, and Raymond Mooney. Explaining competitive-level programming solutions using llms. arXiv preprint arXiv:2307.05337, 2023a. — [arXiv:2307.05337](https://arxiv.org/abs/2307.05337) find
  12. Rongao Li, Jie Fu, Bo-Wen Zhang, Tao Huang, Zhihong Sun, Chen Lyu, Guang Liu, Zhi Jin, and Ge Li. Taco: Topics in algorithmic code generation dataset. arXiv preprint arXiv:2312.14852, 2023b. find
  13. Yujia Li, David Choi, Junyoung Chung, Nate Kushman, Julian Schrittwieser, Rémi Leblond, Tom Eccles, James Keeling, Felix Gimeno, Agustin Dal Lago, et al. Competition-level code generation with alphacode. Science, 378(6624):1092–1097, 2022.
  14. Nelson F Liu, Kevin Lin, John Hewitt, Ashwin Paranjape, Michele Bevilacqua, Fabio Petroni, and Percy Liang. Lost in the middle: How language models use long contexts. Transactions of the Association for Computational Linguistics, 12:157–173, 2024.
  15. Jakub Macina, Nico Daheim, Sankalan Pal Chowdhury, Tanmay Sinha, Manu Kapur, Iryna Gurevych, and Mrinmaya Sachan. Mathdial: A dialogue tutoring dataset with rich pedagogical properties grounded in math reasoning problems. arXiv preprint arXiv:2305.14536, 2023.
  16. Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, et al. Self-refine: Iterative refinement with self-feedback. arXiv preprint arXiv:2303.17651, 2023. find
  17. OpenAI, :, Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, Red Avila, Igor Babuschkin, Suchir Balaji, Valerie Balcom, Paul Baltescu, Haiming Bao, Mo Bavarian, Jeff Belgum, Irwan Bello, Jake… — GPT-4 Technical Report
  18. Baptiste Roziere, Jonas Gehring, Fabian Gloeckle, Sten Sootla, Itai Gat, Xiaoqing Ellen Tan, Yossi Adi, Jingyu Liu, Tal Remez, Jérémy Rapin, et al. Code llama: Open foundation models for code. arXiv preprint arXiv:2308.12950, 2023.
  19. Roger C. Schank. Dynamic Memory: A Theory of Reminding and Learning in Computers and People. Cambridge University Press, USA, 1983. ISBN 0521248582. find
  20. Noah Shinn, Beck Labash, and Ashwin Gopinath. Reflexion: an autonomous agent with dynamic memory and self-reflection. arXiv preprint arXiv:2303.11366, 2023.
  21. Theodore Sumers, Robert Hawkins, Mark K Ho, Tom Griffiths, and Dylan Hadfield-Menell. How to talk so ai will learn: Instructions, descriptions, and autonomy. Advances in neural information processing systems, 35:34762–34775, 2022. find
  22. Theodore R Sumers, Shunyu Yao, Karthik Narasimhan, and Thomas L Griffiths. Cognitive architectures for language agents. arXiv preprint arXiv:2309.02427, 2023. find
  23. Guanzhi Wang, Yuqi Xie, Yunfan Jiang, Ajay Mandlekar, Chaowei Xiao, Yuke Zhu, Linxi Fan, and Anima Anandkumar. Voyager: An open-ended embodied agent with large language models. arXiv preprint arXiv:2305.16291, 2023. find
  24. Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al. Chain-of-thought prompting elicits reasoning in large language models. Advances in Neural Information Processing Systems, 35:24824–24837, 2022.
  25. Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao. React: Synergizing reasoning and acting in language models. arXiv preprint arXiv:2210.03629, 2022.
  26. Tao Yu, Rui Zhang, Kai Yang, Michihiro Yasunaga, Dongxu Wang, Zifan Li, James Ma, Irene Li, Qingning Yao, Shanelle Roman, et al. Spider: A large-scale human-labeled dataset for complex and cross-domain semantic parsing and text-to-sql task. arXiv preprint arXiv:1809.08887, 2018.
  27. Daoguang Zan, Bei Chen, Fengji Zhang, Dianjie Lu, Bingchao Wu, Bei Guan, Yongji Wang, and Jian-Guang Lou. Large language models meet nl2code: A survey. arXiv preprint arXiv:2212.09420, 2022. find
  28. Eric Zelikman, Qian Huang, Gabriel Poesia, Noah D Goodman, and Nick Haber. Parsel: A unified natural language framework for algorithmic reasoning. arXiv preprint arXiv:2212.10561, 2022. find
  29. Andy Zhou, Kai Yan, Michal Shlapentokh-Rothman, Haohan Wang, and Yu-Xiong Wang. Language agent tree search unifies reasoning acting and planning in language models. arXiv preprint arXiv:2310.04406, 2023. find
  30. Shuyan Zhou, Uri Alon, Frank F Xu, Zhiruo Wang, Zhengbao Jiang, and Graham Neubig. Docprompting: Generating code by retrieving the docs. arXiv preprint arXiv:2207.05987, 2022. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/shi-2024-language-models-solve-olympiad-programming/