USACO: Can Language Models Solve Olympiad Programming?

USACO consists of 307 problems from the USA Computing Olympiad, complete with exhaustive test cases, problem analyses, and difficulty labels. Although zero-shot performance is poor, we find that we can well over double performance with a combination of retrieval and self-reflection.

Abstract

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.

Explorer

Baseline:

Problem:

All problems Unsolved by zero-shot models Unsolved by any baseline

▸ Problem Description

▸ Official Problem Analysis

▸ Official Solution Code

Official code loading...

Baseline's Code Submission

Code loading...

▸ Retrieved problem: Retrieved problem loading...

Execution result loading...

Note 1: For Episodic Retrieval, GPT-3.5 performed best given top 1 retrieved problem; GPT-4 performed best given top 2. (as shown)

Note 2: Unsolved problem lists are based on 10 zero-shot attempts and 1 Reflexion + Episodic Retrieval attempt per problem; aggregate statistics may differ slightly from paper due to nondeterminism.

Note 3: Some Official Solution Code entries underwent LLM-assisted translation into Python (e.g. from C++); they are verified to pass system tests under given time and memory constraints.

Benchmark Overview

Table of topics for each USACO difficulty tier

USACO's 307 problems span four difficulty tiers (bronze, silver, gold, platinum). At all levels, solutions typically require ad hoc algorithmic reasoning and, unlike interview-level problems, rarely follow directly from well-known algorithms. Silver and above problems may additionally require knowledge of known algorithms and data structures, often using them in unorthodox ways. The table of per-difficulty core skills summarizes information at usaco.guide.

Baseline Comparison

Table of baseline results on USACO, augmented with inference-time techniques

Past work has demonstrated that curated prompting and retrieval strategies can significantly improve performance on various tasks across natural language processing, multi-task QA, and embodied intelligence. We investigate the effectiveness of these methods on the challenging USACO task, and find that:

Errors are almost always algorithmic and often subtle. Other than CodeLlama, we find that no model errors are significantly due to compilation errors.
Inference-time techniques dramatically improve performance, more than doubling performance on USACO. Some methods, such as self-reflection, are more sensitive to the base reasoning capability of the model and work better with stronger models like GPT-4. Combining synergistic methods such as Episodic Retrieval + Reflexion can help maximize performance for a given base model.
Platinum problems remain unsolved, posing an open challenge for future inference techniques and foundation models. Without inference-time techniques, base models also remain in the single digits on USACO and get near-zero performance on difficulties gold and above.

Human-in-the-Loop Guidance

Table of human-in-the-loop USACO results

To further examine how far a model is from solving a given problem, we perform a human study via an interactive tutoring setup, in which a human provided with problem solutions engages in a multi-turn conversation with the model providing precise feedback on model errors while following a ruleset that prohibits giving away too much information.

Surprisingly, we find that human-in-the-loop feedback dramatically improves GPT-4 performance without helping GPT-3.5. On a small set of 15 previously-unsolved problems (by any method), human-in-the-loop guidance improves GPT-4 performance from 0% to 86.7% without improving GPT-3.5 performance at all.
Qualitatively, we find that models with stronger reasoning abilities such as GPT-4 are able to adapt to high-level feedback: for example, it suffices to tell GPT-4 not use a heap in "Hungry Cow" or ask it "Is there any way we can use the inherent ordering of the cows and directly calculate the number of steps necessary?" in "Photoshoot" to lead to a correct revised solution.

Overall, our human-in-the-loop results highlight that the full capabilities of models may not be captured by solve rate, motivating better evaluation beyond execution success (pass@k) as well as better methods to surface high-quality feedback and leverage this latent ability to adapt in models like GPT-4.

BibTeX


          @misc{shi2024language,
            title={Can Language Models Solve Olympiad Programming?}, 
            author={Quan Shi and Michael Tang and Karthik Narasimhan and Shunyu Yao},
            year={2024},
            eprint={2404.10952},
            archivePrefix={arXiv},
            primaryClass={cs.CL}
          }

Can Language Models Solve Competitive Programming?