Can Language Models Solve Olympiad Programming?
Quan Shi Michael Tang Karthik Narasimhan Shunyu Yao
Computing olympiads contain some of the most challenging problems for humans,
requiring complex algorithmic reasoning, puzzle solving, in addition to
generating efficient code. However, it has been understudied as a domain to
evaluate language models (LMs). In this paper, we introduce the USACO benchmark
with 307 problems from the USA Computing Olympiad, along with high-quality unit
tests, reference code, and official analyses for each problem. These resources
enable us to construct and test a range of LM inference methods for competitive
programming for the first time. We find GPT-4 only achieves a 8.7% pass@1
accuracy with zero-shot chain-of-thought prompting, and our best inference
method improves it to 20.2% using a combination of self-reflection and
retrieval over episodic knowledge. However, this is far from solving the
benchmark. To better understand the remaining challenges, we design a novel
human-in-the-loop study and surprisingly find that a small number of targeted
hints enable GPT-4 to solve 13 out of 15 problems previously unsolvable by any
model and method. Our benchmark, baseline methods, quantitative results, and
qualitative analysis serve as an initial step toward LMs with grounded,
creative, and algorithmic reasoning.