Can Language Models Solve Olympiad Programming?
Authors: Ben Shi
Michael Tang
Karthik R Narasimhan
Shunyu Yao
Venue: COLM (2024)
Keywords: coding, LLM, memory, retrieval
TL;DR: We present a new challenging benchmark of olympiad-level programming problems, evaluate existing and newly enabled inference methods that boost performance, and provide insights on the different capabilities of models on USACO.

Abstract: Olympiad programming is one of the hardest reasoning challenges for humans, yet it has been understudied as a domain to benchmark language models (LMs). In this paper, we introduce the USACO benchmark with 307 problems from USA Computing Olympiad contests, along with high-quality unit tests, reference code, and official analysis for each problem. These resources enable us to construct and test a range of LM inference methods beyond zero-shot prompting for competitive programming. We find state-of-the-art models in code generation, such as GPT-4, achieve only a 8.7\% pass@1 accuracy with zero-shot chain-of-thought prompting, with our best inference method almost \textit{doubling} zero-shot accuracy using a novel combination of retrieval augmentation and self-reflection. However, this is still far from solving the benchmark. To better understand the remaining challenges, we perform 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 thus serve as an initial step towards LMs with grounded, creative, and algorithmic reasoning.

Published as a conference paper at COLM 2024
Can Language Models Solve Olympiad Programming?
Quan Shi", Michael Tang", Karthik Narasimhan, Shunyu Yao Princeton Language and Intelligence (PLD), Princeton University {qbshi,
edu
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 intro- duce 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 8.7% pass@1 accuracy with zero-shot chain-of-thought prompting, and our best inference method improves it 20.2% using 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 novel human-in-the-loog 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.
1 Introduction
Code generation has become an important domain to evaluate and deploy language models (LMs). However, with the scaling of LMs and the development of new inference meth- ods (Wei et al., 2022; Shinn et al., 2023; Chen et al., 2023; Zhou et al., 2022), many popular coding benchmarks such as HumanEval (Chen et al., 2021) and MBPP (Austin et al., 2021) have been saturated with solve rates above 90%. To drive further progress, we need more challenging benchmarks that reveal limitations of existing models and inference methods, and provide actionable insights for improving LM's algorithmic reasoning.
Competitive programming
natural fit for this pursuit, as has been designed to rigorously evaluate the human ability to reason about complex scenarios and create novel algorithms. However, previous explorations of competitive programming lack exhaustive unit test suites, lack problem analyses, or lack enough problem diversity to comprehensively evaluate algorithmic reasoning (Li et al., 2022; Hendrycks et al., 2021; Jain et al., 2024).
We thus introduce USACO, a carefully crafted coding benchmark with 307 challenging problems from past USA Computing Olympiad (USACO) competitions. As shown in Figure 1, each problem describes task to solve in fictional scenario, along with some example tuples of inputs, outputs, and explanations. Solving these problems not only require wide range of algorithmic, mathematical, and commonsense knowledge, but also grounded and creative reasoning: unlike previous program synthesis benchmarks, successful models must reason over ad hoc environments, creating novel algorithms tailored to each problem scenario. On USACO, even the best LM (GPT-4) only reaches zero-shot pass@1 solve rate of 8.7% using zero-shot thain-of-thought prompting.
To study more advanced inference-time methods on competitive programming, for the first time, our benchmark also collects high-quality unit tests, reference code solutions, and
"quual contribution. Code, data, examples: https://princetonnnll httpp..ttbb.......p.ppppppp....p Cttlub.o//UsS io/USCCBeechh/
1

---

Published as a conference paper at COLM 2024
Farmer John how N (2 N s (d%). Each has beved that onchre Guernay Hostein. ottes the sumbrred this order.
SAMPLE INPUTY
SAMPLE OUTPUT
stunding
DREO
day, ooe contains the range cows stazting heeself (oow 5) to incluring cow R; (2 S R, S. N).
list cows. Specthoally.
I'l has recently disoovered that cach treed of cow has exactly one distiact Jeader. F3l doos not know who the lndeers are, but be knows that each lender muse huve a list that includee all the cows of their beeed, or the other breed's leader (or both).
Help FJ coue the mumberr
conos that could be lenders It is guaranteed
that leass possible
Problem
Cow
2
3
Key:
contains N. second string length N. with the charatee denoting the trwed the rth cow (G meening Guerzzey and It meoning licistenn). it is guacentoed that there is at lesse one Guernsey and our Hristein, The third live contrics E, ... Ex..
INPUT FORMAT:
The
Guernsey
Holstein
Only possible
Cow cows bread (*t)
OUTPUT FORMAT: Output the mimber of possible psins of leaders.
Cow lat has the other breed's leader (cow
Format
Example
Figure 1: Example USACO problem description, formatting instructions, and illustration (problem id: 1275 bronze leaders). Solving this problem requires combination of grounded reasoning about the concept of leaders, creative thinking to precisely count different cases of leader pairs, and algorithmic reasoning to perform these ad hoc operations in linear time.
official analysis for each problem, along with corresponding instructional texts in the form of competition programming textbooks. Based on these resources, we construct a range of baseline methods based on retrieval (Gao et al., 2023), self-reflection (Shinn et al., 2023; Chen et al., 2023), and their combinations. We find that combining retrieval over similar problems and solutions and self-reflection maximizes performance gains, well over doubling the zero-shot solve rate of GPT-4. However, all methods are still far from solving the benchmark above bronze level, the easiest difficulty tier.
To further understand the limitations and potentials of LM reasoning toward competitive programming, we perform novel human study where humans interact with LMs in conversational "tutoring" setup by pointing out errors and giving minimal hints. To our surprise, subset of 15 problems where GPT-3.5 and GPT-4 can never solve using any inference methods, such a human-in-the-loop setup leads to GPT-4 solving 13 out of 15 problems, whereas GPT-3.5 solves none. This indicates the emergent potential of stronger LMs to incorporate high-quality feedback, the need to develop new methods that can generate such human-level corrective feedback, and a re-thinking of the right metric for measuring model capabilities beyond the overly strict execution success.
To summarize, our contributions of our work are:
We propose the USACO benchmark, the first benchmark based on olympiad pro- gramming with high quality test cases, problem analyses, and auxiliary resources.
For the first time, we construct and test LM inference methods for Olympiad pro- gramming, such as self-reflection and retrieval. Our results indicate a combination of retrieval and self-reflection can significant boost performance, but is still far from solving the benchmark.
We conduct a novel human-in-the-loop study to characterize the capabilities and limitations of LMs for Olympiad programming, complementary automatic experi- ments based on execution success, We find that only certain models can successfully incorporate feedback, uncovering latent differences between models
Related Work
Code Generation Benchmarks Language model performance on simple program synthe- sis has been thoroughly explored (Yu et al., 2018; Chen et al., 2021; Austin et al., 2021; Zan
2

---

Published as a conference paper at COLM 2024
et al., 2022), with HumanEval being the general standard for benchmarking new models on code synthesis. However, current models, aided by inference techniques, can achieve up to 94% solve rate HumanEval (Zhou et al., 2023), indicating need for harder, more complex, yet self-contained coding tasks to probe the upper limit of code reason- ing. Competitive programming questions have thus been proposed evaluation metric, with most problems coming from online platforms such as Codeforces, Atcoder, Kattis...(Li et al., 2023b; Huang et al., 2023; Jain et al., 2024; Hendrycks al., 2021; Li al., 2022). However, these problems largely do not contain quality problem analyses, comprehensive sorrectnes-deffiing test cases, with many problems being presented purely symbolically. This means that it can only weakly evaluates the model's ability to creatively reason in grounded problem environments, a crucial ability of well-rounded reasoners.
more difficulty
Inference Time Methods for LMs Inference time methods have seen significant success in improving reasoning capabilities by conditioning generations on environment feedback, task-specific knowledge, natural language reflections, and planned summaries (Shinn al., 2023; Chen et al., 2023; Madaan et al., 2023; Yao et al., 2022; Zelikman et al., 2022; Zhou et al., 2023; Gao et al., 2023; Le et al., 2022). However, their utility on code domains has only previously been explored on simple program synthesis tasks such as HumanEval and MBPP (Chen et al., 2021; Austin et al., 2021). In this paper, we additional provide insights on their performance in competitive programming, a much more difficult domain. Our instantiation of retrieval augmented generation additionally takes inspiration from cognitive architectures for humans reasoning (Sumers et al., 2023) and classical case-based reasoning literature (Aamodt & Plaza, 1994; Schank, 1983), mirroring the types of information humans find useful for problem solving.
Human Model Interaction Sumers al. (2022) investigates agent learning from human provided feedback under synthetic tasks. Macina et al. (2023) aims to provide tutoring ruleset to effectively engage LMs in dialogue math problem solving. In this paper we adopt similar setup to code, applying a specified interaction ruleset to gauge the ability of models to respond to feedback.
3 The USACO Benchmark
The USACO benchmark consists of 307 high-quality expert-written problems from past USA Computing Olympiad contests (https:/ https://uaco. org)). Each problem consists of a problem description with instructions for reading and writing from standard input and output; 0-2 sample tests; 10-17 hidden tests verifying solution correctness; time and memory limits verifying solution complexity; and an official human- problem analysis explaining the solution in detail with corresponding Python code.
Problem Difficulty Problems are divided into tiers of increasing difficulty consisting of bronze, silver, gold, and platinum. At all levels, solutions typically require ad hoc algorithmic reasoning and, unlike interview-level problems, rarely follow directly from well-known algorithms. Gold and platinum problems may additionally require knowledge of known algorithms and data structures, often using them in unorthodox ways.
Task Formulation A model is given the problem description, including any available samples, and time and memory limits. The model must then produce a code solution, which is run by the judge and accepted if it produces the expected outputs on all hidden tests under the given limits, enforcing both correctness and the desired asymptotic efficiency. Note that the model cannot get access to hidden test inputs outputs, but can receive information on how many tests a given solution has passed.
Task Features We find several features of USACO that make it an effective LLM evaluator. Firstly, USACO problems contain detailed problem environments encouraging grounded, creative reasoning. Problem narratives are high quality, and avoid purely symbolic coding questions such as many presented on platforms like LeetCode or Kattis. Thus, problems
3

---

Published as a conference paper at COLM 2024
Exhaustive Unit Tests
Expert- Expert-Written Problem Analyses
Non-Symbolic Environments
Benchmark
HumanEval (Chen et al., 2021)
APPS (Hendrycks et al., 2021)
x
CodeContests (Li et al., 2022)
X
USACO (ours)
Table 1: The USACO benchmark features high-quality problem environments with grounded creative reasoning, complete hidden tests, and expert-written problem analyses with both gold solution reasoning and Python code.
focus on a model's ability to reason creatively and ground insights and algorithmic designs to the details of a given scenario. Furthermore, problems are tiered in difficulty (see Table 3), with bronze tier problems serving as an effective test of pure reasoning, requiring no formal knowledge of data structures and algorithms. At higher tiers, problems go beyond basic implementation of algorithms,, instead requiring creative, grounded algorithm design specific to the desiderata and constraints of the given scenario. Finally, the USACO benchmark includes expert-written problem analyses containing both natural language and gold Python solutions to all problems, enabling development of rich inference-time techniques and nuanced evaluation beyond unit test execution.
Difficulty
Core Skills Evaluated
Bronze
simulation, complete search, sorting, greedy
Silver
binary search, comparators, graphs, trees, floodfill, prefix sums, bitwise operators
Gold
dynamic programming, disjoint set union, spanning trees, Euler tour, combinatorics
Platinum
segment tree, range queries, binary jumping, sweep line, convex hull, flows
Table 2: Core skills evaluated at each tier of USACO, from /
Problems We collect 484 problems from https:/ org detailing mate- rials on contests hosted between 2011 and 2023 using custom HTML parser, parser, and use regular expressions extract wall clock time and memory constraints from problem descriptions. which are manually verified using solutions with correct and incorrect asymptotics.
Construction:
Construction: Problem analyses To assist the development of rich inference- time methods and evaluations, we select the 307 problems out of 484 with full problem analyses. We parse an English-only analysis without code, well as ground truth standalone Python 3 code snippet. For the majority of problems where Python code is unavailable, we prompt GPT-4 to translate the code to Python 3 and validate that all code solutions pass hidden tests the given constraints.
3.1 Baseline Results
We begin by evaluating zero-shot performance of models representing state-of-the-art coding performance as baseline: this includes GPT-3.5 (gpt-3.5-turrb--1006) GPT-4 (gpt-4- 1106-preview), Claude-3-sonnet, (caude-3-somnee-222403 Deepseek-Coder Coder-Instruct-7B (Roziere et al., 2023; Guo et al., 2024; OpenAl et al., 2023). This is summarized in Table 3. Unless otherwise indicated, models were prompted with chain of thought (Wei et al., 2022), refer to figure for full prompts. Following previous work on competitive programming (Li et al., 2022; Hendrycks et al., 2021), evaluate primarily based on the unbiased pass@k metric defined in (Chen et al., 2021).
CodeLlama2-Instruct77 and
Solve rates near zero for gold difficulty and above. We find that USACO presents strong challenge to current generation models. Weaker models like GPT-3.5, CodeL.lama,
4

---

Published as a conference paper at COLM 2024
Statistics
USACO
Model
Pass@1
Number of problems
307
CodeLlama (7B)
0.19
Avg words per problem
452.9
DeepSeek Coder (7B)
1.04
Avg words per problem analysis
1107.8
GPT-3.55
0.59
Bronze problems
123
Claude-3-Sonnet
2.61
Silver problems
100
GPT-4
8.7
Gold problems
63
Human Average
35.83
Platinum problems
21
Table 3: Statistics and zero-shot pass@1 performances USACO. Human performance
estimated through past contest performance.
and DeepSeeker cannot solve any problem above silver difficulty, while newer models like GPTT4 have near-zero pass rates for gold difficulty problems and above. For full per-difficulty solve rates, refer to Appendix B.3.
For stronger models, most errors are algorithmic. Other than CodeLlama, we find that no model errors are significantly due compilation errors. We detail full results in Appendix B.2. This shows at the very least, models are effective in generating syntactically correct code, and indicates more nuanced issues in generations such as problem misunderstandinns. We document some samples of problems and their errors in Appendix 7 and perform brief qualitative analysis.
Problem release date impacts performance. We test temporal effects by additionally evaluating models on small selection of 36 problems released after training cutoff dates. We find that solve rate drops to for models. However, we do note that USACO questions are well known to increase in difficulty every year, making this likely effect of difficulty increases, inclusion of reasoning in pre-training data, as well as small sample size. Despite this, the overall performance is still quite poor.
Inference Time Techniques for Better Reasoning
Past work has demonstrated that curated prompting and retrieval strategies can significantly improve performance various tasks across natural language processing, multi-task QA, and embodied intelligence (Yao et al., 2022; Wang et al., 2023; Madaan et al., 2023). To investigate the effectiveness of such inference-time methods, adapt self-reflection and retrieval techniques widely successful in other domains to USACO.
4.1 Self-Reflection
Self-reflection techniques aims to allow models to iteratively improve generations by condi- tioning future output on execution feedback of previous attempts. We primarily experiment with Reflexion (Shinn et al., 2023), representative technique that additionally maintains an episodic buffer of past attempts induce better reasoning future trials.
Setup The model is first prompted solve the problem, generating a code solution as well as an explanation of the code. For each iteration of reflection, the model is prompted to first reflect on what went wrong previously, then fix the previous code, given the the execution output of the previous solution, the previous solution itself, as well the contents of a buffer of past solve attempts. After each iteration, the previous attempt as well the execution results is added to the buffer. This loop iterates until maximum number of debugging steps is reached. We set this hyperparameter = as we observe no empirical gains in solve rate past rounds of debugging: see Appendix C.5.
4.2 Retrieval Augmented Generation
Retrieval augmented generation (RAG) has similarly proven to reduce hallucinations and improve reasoning capabilities in a variety domains. (Gao et al., 2023; Su et al., 2024; Shypula et al., 2023). However, it has seen limited usage in coding domains as it is difficult

---

Published as a conference paper at COLM 2024
Retrieval Query
Program def Dy Pyymiiooeeg mnrmoog
Problem Description
Problem Description
Probiemm Descriptions "Bussie wents beles of han,, and needs to optimize...
Propesed English Solution: shoulc cynamic programming...
LLM
Program def Dynamkcargd)
LLM
Proposed Code: del Snnamuihogrammmigggoooo op in [arge(() Perge]
LLM
(ergge
Semantic Knowledge
Episodic Knowledge
Execution Feedback:
Program
Texthook Chaptara: Dynamic Programming...
Past Solved Preblems problem, Dynamic...
Judge
Wrong Ans: test
Self-Reflection
Retrieval
Figure 2: Overview of inference methods tested: self-reflection (left) prompts the model to review execution feedback to revise its generation; retrieval (right) uses the problem and a draft solution to query relevant semantic and episodic knowledge to generate a more informed final solution.
to pinpoint what types of knowledge is useful in aiding code generation. We note that when solving problems, humans tend to recall either task-specific, established algorithms, facts, and concepts about the domain, past experiences and generalizations from solving previous, similar problems relative to the problem at hand. This represents semantic knowledge, and episodic knowledge respectively (Sumers et al., 2023). Inspired by this, we curate two setups we aptly name semantic retrieval and episodic retrieval, and instantiate the semantic knowledge store competitive programming textbook, and the episodic knowledge store as the bank of USACO problems and solutions not currently being solved.
Semantic Knowledge Store We use the cp-algs textbook /tctpss:/cc-alpeee thms. com), which contains 30 human-written chapters algorithmic concepts specifically targeted to the USA Computing Olympiad. Chapters contain English text as well as code snippets. Entire chapters barely fit within the context limit of GPT-4: therefore when lower context models (like GPT-3.5), or multiple types of knowledge are incorporated, we truncate the retrieved chapter to fit within the context length.
Episodic Knowledge Store We simulate setup where the model has seen all other prob- lems in the USACO set except for the current one it solving, simulating a k-fold evaluation that holds out one problem at time: this allows us to maximally investigate the potential of retrieval on the relatively small dataset (we obtain similar results with a more traditional train-test split, detailed in Appendix A. For each "seen" problem, its corresponding problem description, english solution, and python solution code is concatenated together to form documents to retrieve over. We tune over the number of problems to retrieve, p, and find that p is optimal for GPT-4, and p = 1 is optimal for GPT-3.5 and thus report these numbers. Full details can be found in Appendix C.5.
Retrieval Query Ablations on retrieval queries indicate that the most effective retrieval query utilizes the current problem description, as well as an initial solution attempt con- taining code and english explanation. This allows accurate retrieve relevant algorithm descriptions from the underlying retrieval corpus, as solely utilizing the problem descrip- tions does not allow retrieval over algorithmic keywords. We do not count this initial generation as an attempt as it does not get evaluated by our local judge. Additional details on ablation experiments can be found in Appendix C.3.
Setup Models are prompted with the problem description, and first generate an initial solution to be used in the retrieval query. This initial solution, along with the problem de- scription, is fed into BM25 retrieval function, and the highest ranking document is inserted into the context to aid the real solving process. Prompts can found in Appendix C.7. We additionally note that retrieval-based methods and reflection methods orthogonal and can be sequentially applied. Thus, we test settings combining various combinations of retrieval types, as well retrieval combined with reflection.

---

Published as a conference paper at COLM 2024
Technique
GPT-3.5
GPT-4
Zero-shot
0.59
8.70
Reflexion
0.97
12.38
Semantic Retrieval
2.04
10.26
Episodic Retrieval
5.49
14.33
Semantic + Episodic
6.76
12.54
Semantic Reflexion
2.64
11.82
Episodic + Reflexion
8.79
20.20
Semantic Episodic Reflexion
7.52
18.05
Figure 3: Pass@1 Performance of Reflexion and Retrieval based methods on USACO.
Evaluation All methods are evaluated Pass@1.For self-reflection, adapt methodology in Shinn et al. (2023), and provide only the execution results of the exposed sample test cases for models to reflect over. GPT-3.5 and GPT-4 were used for initial experiments: future work will involve expanding results on open source models.
4.3 Results
We summarize model performances under each setting in table 4.2. Combining episodic retrieval and reflexion maximizes performance gains by well over doubling the performance of zero-shot GPT-4. We condense key findings below:
Episodic Retrieval works across model sizes, unlike Reflexion. We find that the ability to self-reflect effectively is emergent property of stronger models, consistent with (Shinn et al., 2023; Chen al., 2023). However, both semantic and episodic retrieval are still effective, with episodic retrieval even causing GPT-3.5 to approach GPT-4's zero-shot performance. This is likely because self-reflection relies on the internal model's strength to reason over sparse, binary reward signals. Retrieval, the other hand, allows models to reference existing reasoning and code snippets, requiring less intrinsic model capabilities. Our findings thus corroborate Li et al. (2023a), where LMs can understand much more complex competitive programming solutions than they can produce.
Episodic Retrieval and Reflexion have strong synergy. Episodic Retrieval reaches new maximums when combined with Reflexion, but not with Semantic Retrieval. We find that for GPT-4, 70.2% of newly solved problems (relative to zero-shot) with semantic retrieval also newly solved by episodic retrieval. It provides one possible explanation to why combining the two may decrease performance: the additional knowledge provided by our implementation of semantic retrieval trades off against its long contexts, which current LLMs are known to be struggle with (Liu et al., 2024). In contrast, only 45.9% of newly solved problems with Reflexion overlap with episodic retrieval, pointing to better synergy.
Platinum problems remain unsolved. Although solve rates on gold problems grow significantly, platinum problems remain unsolved, posing an open challenge for future inference techniques and foundation models. For more details, refer to Appendix C.2
Performance gains are not due to memorization. A competing hypothesis for the success of retrieval that adding retrieved solutions increases memorization effects for the problem currently being evaluated, rather than the model critically engaging with the content of the retrieved content itself. To test for this, we remove critical sections of retrieved solutions and find significant drops in performance. In addition, qualitative analysis indicates significant overlap in generated and official published solutions. Full experiment details can be found in Appendix C.1.
4.4 Qualitative Analysis
We focus qualitative analysis the improvements of retrieval, individually strongest inference-time technique. Here, we isolate examples problems newly solvable with RAG in figure
7

---

Published as a conference paper at COLM 2024
Example Sample Bronze Problem: 187 bronze find the cow!
Perhapa the xirplext definition ta that
Iterate though grass string fron... for in range(len(grass)-1 -1, -13: if grass(1:512] "I]":
for in range(3, len(grassil: grass(s] '('
total cambez any
yo very
and grass[i-1] m 141
count_frott_eeg ea
back_lepsscoont elif gress
17.. For eaarpia, the celloving
elif grass[1:i-2] - "(C":
aiaudiga aaw all Iulanted:
beuntteessite count_front_lege
and grass[1-1] = ") possibll_llcctionnn
D 10) (
back_legs_count
Incorrect zero=shot solution
Correct Solution with Problem Memory
Memory: 188 bronze typo
Example 2: Sample Silver Problem: 210 silver milk routing
def routinnn,,, e, x, pipes):
def dijkstralgraph, source, it, capacity): time_ taken [flost ('inf"] '1 (n-1) sane__takennnoee [source]
def dijkstrain, edges, source, destination....
graph [i: II for 1 in rargett, n-11)
dist [rloat("Snt" [n-1) visited sourcel] hespg-heoptfttesstteed (ssurce) while
for
graphli)..apeeddii
nin_hese hesp 10, sourcel
graphii apgendt & el)
while hin_heap:
visited = (11 for 1 in rangell, m=1)> while
Incorrect zero-shot solution
Correct Solution Problem Memory
Memory: 989 gold milk pumping
Example Sample Gold Problem: 400 gold roadblock
def rwin(1:
def msisifieles, pathways):
cuozy Ioan 9.u,, ancestor
graph, N, read_ input()
for fieless)
disttece shortest_path dijkstral..
b, length in pathways:
dws, node that the ront node, thes lsee the path fron 9e6 to the roct node, and it there are mulcipla nodes we plok the one chat is fwrthwatt away from the root. node.
rax sor_inceesee- = 8
graphin] length
i.e. ve want
shartest_path:
graph(b][a [e] length
the path from
original, length leenth graphtul [v] a=
[xsph[q]
shortest_path, ain_dist dijkstralgraphh...
aac_eeceesee
rargell, tenishortest_ pathl)
Incorrect zero-shot solution
Correct Solution with Semantic
Memory: LCA Algorithma
Figure 4: Three examples of problems previously unsolved, but solved with retrieval.
Example Models can borrow reasoning about similar problem environments Here, both the central problem and the most relevant retrieved problem requires models to parse and operate over parenthesis-oni, strings. The retrieved solution code thus provides models with sample reasoning over this tricky and mistake-prone problem environment, allowing models to generate more accurate code.
Example 2: Models adopt existing code structure and algorithms In this example, both problems require the use of Dijkstra's shortest path algorithm. However, the initial implementation contains many small, nuanced bugs due to its attempts to push the entire solution into a single function. This not only makes the code less modular, but it also leaves greater room for error. With episodic retrieval, we see the model grounding itself in the retrieved content, borrowing significant code structure and algorithmic reasoning of the retrieved problem.
Example 3: Models can utilize algorithmic concepts and reasoning from texts The given problem here requires finding a shortest path within a grid containing roadblocks. We see that the model fetches a textbook chapter lowest common ancestor algorithms, which covers tangentially applicable graph traversal techniques to the problem. Interestingly enough, it does not fetch the chapter on Dijkstra's algorithm for shortest paths, the algorithm utilized in the official problem analysis. Visual inspection of the Dijkstra's aaat chapter indicated that the chapter was short and light on details, thus receiving low retrieval score. This highlights the flexibility of the retrieval query to adapt to low quality documents, finding suitable replacements.
Human-in-the-loog Guidance
In benchmark evaluations, we found a wide diversity in the distribution of model errors: from problem misunderstandings, to subtle off-by-one implementation issues. To further examine how far a model is from solving a given problem, we perform a human study via an interactive "tutoring setup."
8

---

Published as a conference paper at COLM 2024
Setup A human provided with problem solutions engages in multi-turn exchange with a model, at each step providing feedback on mistakes under a specified ruleset. Notably, the human is not allowed to provide specific fixes rather only general instructions (e.g., "you are using the wrong algorithm" " or "this code may result in index out of bounds"). The full interaction ruleset is detailed in Appendix D.1. The model is then prompted to fix its mistakes: we allow a maximum of 1 code execution to simulate a pass@1 setup, maximum of 5 code generations to limit conversation length, and total of 3 attempts per problem.
Results Surprisingly, we find that on a small set of 15 problems' on which GPT-3.5 and GPT-4 achieve zero pass rate using all of the above inference-time methods, the
Desoription
Draft 1 Cefoonnni
LLM
human-in-the-lopp setup raises GPT-4 performance from
Feedback Noddy cat
0% to 86.7% (13 problems solved) while not improving GPT-3.5 performance from 0%. Qualitatively, GPTI-3.5 con- sistently hallucinates fixes irrelevant feedback, while GPT-4 pinpoints accurate algorithmic fixes in response to minimalistic feedback. A sample trajectory is provided in Appendix D.2.
Human
Draft ok, Ownemitgargs)
Judge
o
Feedback 2 feter You heve on inde
Human
Problem-level Analysis We found that GPT-4 was more responsive to blanket feedback that its algorithm or un- derstanding of an environment concept was incorrect, and more capable of landing on the correct strategy in its second attempt, whereas GPT-3.5's retries are typically similarly unhelpful. For example, GPT-4 lands on the cor- rect overall solution strategy after being instructed not use a heap in "Hungry Cow," and similarly after being instructed not to use DP in "The Lost Cow." In "Photo- shoot," it suffices to ask GPT-4 "Is there any way we can use the inherent ordering of the cows and directly calcu- late the number of steps necessary?" ?" to correct it from simulation to a precomputed parity-counting approach; explaining this to GPT-3.5 does not yield any progress. Similarly, GPT-4 is also able to follow instructions on spe- cific fixes, unlike GPT-3.55. For example, on "The Lost Cow," GPTT4 tends to calculate the next position using the current position instead of the initial position - given this fact, it produces the correct implementation. 2
Interactive Tutoring
Model
% Solved
GPT-3.5
0%
GPT-3.5 tutoring
0%
GPT-4
0%
GPT-4 tutoring
86.7%
Figure 5: Human-in-the-loop in- teractive "tutoring" setup: GPT- 4 successfully incorporates feed- back while GPT-3.5 does not.
Discussion Our human-in-the-loww results highlight that the full capabilities of models may not be captured by solve rate; among two models failing on a given problem, one may be one correction away from a fully correct solution, whereas the other may funda- mentally misunderstand the problem scenario. This motivates better evaluation metrics beyond execution success (pass@k). Another perspective on our results is that GPT-4 has further reasoning capabilities that may be "unlocked" by human-level corrective feedback, highlighting the need for better methods generate such feedback.
6 Conclusion
In this paper, we introduce the USACO benchmark for rigorously evaluating code language models on tasks involving grounded ad hoc reasoning and novel algorithmic thinking, We observe that foundation models previously shown to excel basic coding tasks like HumanEval (Chen et al., 2021) perform poorly zero-shot in these more challenging scenarios,
113 bronze, silver, 1 gold. We focused on bronze problems since models performed poorly on harder difficulties.
"See https: / /bens/iee/// 34, htt.b//.o//logg/////mmmmn in- tthe-loop/ / for more trajectories and anal- ysis for different difficulty levels.

---

Published as a conference paper at COLM 2024
but that providing models with task-specific knowledge stores well over double zero- shot performance. We hope that our evaluation of current models' limitations and findings the effectiveness of semantic and episodic knowledge help lay groundwork for its integration into future models and language agents alike.
7 Reproducibility
We release all data and code at http:://priinttrrrrppgggooooooo well as human in the loop trajectories at https://benshi4 htgpsehi....i.hhhh wtt.liooooll///e /024// humen-in-the-lop/ We advise others to isolated execution environments when repro- ducing experiments as the generated code is not validated before execution.
References
Agnar Aamodt and Enric Plaza. Case-based reasoning: foundational issues, issues, methodological variations, and system approaches. Al Commun., 7(1):39-59, mar 1994. ISSN 0921-7126.
Jacob Austin, Augustus Odena, Maxwell Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen liang, Carrie Cai, Michael Terry, Quoc Le, et al. Program synthesis with large language models. Xiv preprint ar orXiv:218.00732) 2021.
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. Evalu- ating large language models trained on code. ar Xiv preprint ar arvi:22007.0333 033744, 2021.
Xinyun Chen, Maxwell Lin, Nathanael Schärli, and Denny Zhou. Teaching large language models to self-debug, Xiv preprint ar Xrio:2304.05128, 2023.
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. Xiv preprint ar axXiv:2312.10997 2023.
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-tie rise of code intelligence. arv preprint arXio:2401.14196 2024.
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.
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 effective 1lm evaluators. arxiv preprint ar arxi:2312.002143 2023.
Naman Jain, King Han, Alex Gu, Wen-Ding Li, Fanjia Yan, Tianjun Zhang, Sida Wang, Ar- mando Solar-Lezama, Koushik Sen, and lon Stoica. Livecodebench: Holistic and contami- nation free evaluation of large language models for code. arXiv preprint arXiv:2403.07974, 2024.
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-21326 2022.
Jierui Li, Szymon Tworkowski, Yingying Wu, and Raymond Mooney. Explaining competitive-level programming solutions using 1lms. arxiv preprint ar arXioo2307.052. 053333777 2023a.
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. arviv preprint XXXt:2312.14887 2023b.
10

---

Published as a conference paper at COLM 2024
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, 37866224; 2022.
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.
Jakub Macina, Nico Daheim, Sankalan Pal Chowdhury, Tanmay Sinha, Manu Kapur, Iryna Gurevych, and Mrinmaya Sachan. Mathdial: A dialogue tutoring dataset with rich peda- gogical properties grounded in math reasoning problems. arviv preprint Stt::2305.15366 2023.
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. ar Xiv preprint ar Xrtx:2303.176511 2023.
OpenAL, :, Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Iige Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, Red Avila, Igor Babuschkin, Suchir Balaji, Valerie Balcom, Paul Baltescu, Haim- ing Bao, Mo Bavarian, Jeff Belgum, Irwan Bello, Jake Berdine, Gabriel Bernadett-Shaping Christopher Berner, Lenny Bogdonoff, Oleg Boiko, Madelaine Boyd, Anna-Luisa Brak- man, Greg Brockman, Tim Brooks, Miles Brundage, Kevin Button, Trevor Cai, Rosie Campbell, Andrew Cann, Brittany Carey, Chelsea Carlson, Rory Carmichael, Brooke Chan, Che Chang, Fotis Chantzis, Derek Chen, Sully Chen, Ruby Chen, Jason Chen, Mark Chen, Ben Chess, Chester Cho, Casey Chu, Hyung Won Chung, Dave Cummings, Jeremiah Currier, Yunxing Dai, Cory Decareaux, Thomas Degry, Noah Deutsch, Damien Deville, Arka Dhar, David Dohan, Steve Dowling, Sheila Dunning, Adrien Ecoffet, Atty Eleti, Tyna Eloundou, David Farhi, Liam Fedus, Niko Felix, Simón Posada Fishman, Juston Forte, Isabella Fulford, Leo Gao, Elie Georges, Christian Gibson, Vik Goel, Tarun Gogineni, Gabriel Goh, Rapha Gontijo- Jonathan Gordon, Morgan Grafstein, Scott Gray, Ryan Greene, Joshua Gross, Shixiang Shane Gu, Yufei Guo, Chris Hallacy, Jesse Han, Jeff Harris, Yuchen He, Mike Heaton, Johannes Heidecke, Chris Hesse, Alan Hickey, Wade Hickey, Peter Hoeschele, Brandon Houghton, Kenny Hsu, Shengli Hu, Xin Hu, Joost Huizinga, Shantanu Jain, Shawn Jain, Joanne Jang, Angela Jiang, Roger Jiang, Haozhun Jin, Denny Jin, Shino Jomoto, Billie Jonn, Heewoo Jun, Tomer Kaftan, Lukasz Kaiser, Ali Kamali, Ingmar Kanitscheider, Nitish Shirish Keskar, Tabarak Khan, Logan Kilpatrick, Jong Wook Kim, Christina Kim, Yongjik Kim, Hendrik Kirchner, Jamie Kiros, Matt Knight, Daniel Kokotajlo, Lukasz Kondraciuk, Andrew Kondrich, Aris Konstantinidis, Kyle Kosic, Gretchen Krueger, Vishal Kuo, Michael Lampe, Ikai Lan, Teddy Lee, Jan Leike, Jade Leung, Daniel Levy, Chak Ming Li, Rachel Lim, Molly Lin, Stephanie Lin, Mateusz Litwin, Theresa Lopez, Ryan Lowe, Patricia Lue, Anna Makanju, Kim Malfacini, Sam Manning, Todor Markov, Yaniv Markovski, Bianca Martin, Katie Mayer, Andrew Mayne, Bob Mc- Grew, Scott Mayer McKinney, Christine McLeavey, Paul McMillan, Jake McNeil, David Medina, Aalok Mehta, Jacob Menick, Luke Metz, Andrey Mishchenko, Pamela Mishkin, Vinnie Monaco, Evan Morikawa, Daniel Mossing, Tong Mu, Mira Murati, Oleg Murk, David Mély, Ashvin Nair, Reiichiro Nakano, Rajeev Nayak, Arvind Neelakantan, Richard Ngo, Hyeonwoo Noh, Long Ouyang, Cullen O'Keefe, Jakub Pachocki, Alex Paino, Joe Palermo, Ashley Pantuliano, Giambattista Parascandolo, Joel Parish, Emy Parparita, Alex Passos, Mikhail Pavlov, Andrew Peng, Adam Perelman, Filipe de Avila Belbute Peres, Michael Petrov, Metroe,Petrov, Henrique Ponde de Oliveira Pinto, Michael, Pokomny Michelle Pokrass, Vitchyr Pong, Tolly Powell, Alethea Power, Boris Power, Elizabeth Proehl, Raul Puri, Alec Radford, Jack Rae, Aditya Ramesh, Cameron Raymond, Francis Real, Kendra Rimbach, Carl Ross, Bob Rotsted, Henri Roussez, Nick Ryder, Mario Saltarelli, Ted Sanders, Shibani Santurkar, Girish Sastry, Heather Schmidt, David Schnurr, John Schulman, Daniel Selsam, Kyla Sheppard, Toki Sherbakov, Jessica Shieh, Sarah Shoker, Pranav Shyam, Szymon Sidor, Eric Sigler, Maddie Simens, Jordan Sitkin, Katarina Slama, Ian Sohl, Benjamin Sokolowsky, Yang Song, Natalie Staudacher, Felipe Petroski Such, Natalie Summers, llya Sutskever, Jie Tang, Nikolas Tezak, Madeleine Thompson, Phil Tillet, Amin Tootoonchian, Elizabeth Tseng, Preston Tuggle, Nick Turley, Jerry Tworek, Juan Felipe Cerón Uribe,
11

---

Published as a conference paper at COLM 2024
Andrea Vallone, Arun Vijayvergiya, Chelsea Voss, Carroll Wainwright, Justin Jay Wang, Alvin Wang, Ben Wang, Jonathan Ward, Jason Wei, CJ Weinmann, Akila Welihinda, Peter Welinder, Jiayi Weng, Lilian Weng, Matt Wiethoff, Dave Willner, Clemens Winter, Samuel Wolrich, Hannah Wong, Lauren Workman, Sherwin Wu, Jeff Wu, Michael Wu, Kai Xiao, Tao Xu, Sarah Yoo, Kevin Yu, Qiming Yuan, Wojciech Zaremba, Rowan Zellers, Chong Zhang, Marvin Zhang, Shengjia Zhao, Tianhao Zheng, Juntang Zhuang, William Zhuk, and Barret Zoph. Gpt-4 technical report, 2023.
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. or arvi preprint ar Xir::3i::012222 0it.220000.1190, 2023.
Roger C. Schank. Dynamic Memory: A Theory of Reminding and Learning in Computers and People. Cambridge University Press, USA, 1983. ISBN 0521248582.
Noah Shinn, Beck Labash, and Ashwin Gopinath. Reflexion: an autonomous agent with dynamic memory and self-reflection. arXiv preprint ar arXio:2303.11366, 2023,
Alexander Shypula, Aman Madaan, Yimeng Zeng, Uri Alon, Jacob Gardner, Milad Hashemi, Graham Neubig, Parthasarathy Ranganathan, Osbert Bastani, and Amir Yazdanbakhsh. Learning performanccimmproinng code edits. arXiv preprint arXiv:2302.07867, 2023.
Hongjin Su, Howard Yen, Mengzhou Xia, Weijia Shi, Niklas Muennighoff, Han yu Wang, Haisu Liu, Quan Shi, Zachary S. Siegel, Michael Tang, Ruoxi Sun, Jinsung Yoon, Ser- can O. Arik, Danqi Chen, and Tao Yu. Bright: A realistic and challenging benchmark for reasoning-intensive retrieval, 2024. URL //atxi: www.oogg//////..ooooooooo...s// hrggabs/2407, 12883.
Theodore Sumers, Robert Hawkins, Mark K Ho, Tom Griffiths, and Dylan Medlil How to talk so will learn: Instructions, descriptions, and autonomy. Advances in neural information processing systems, 35:34762 2022.
Theodore R Sumers, Shunyu Yao, Karthik Narasimhan, and Thomas L Griffiths. Cognitive architectures for language agents. arXiv preprint ar Xix:2239.00427, 2023.
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. Xiu preprint ar arXiv:2305.1629, 2023.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al. Chain-offthoughh prompting elicits reasoning in large language models. Advances in Neural Information Processing Syslems, 35:24824-24837, 2022.
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.06629 2022.
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 2018.
ar
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. aiv preprint axXiv:222..09420, 2022.
Eric Zelikman, Qian Huang, Gabriel Poesia, Noah D Goodman, and Nick Haber. Parsel: A unified natural language framework for algorithmic reasoning. arXiv preprint arXiv:221..10661, 2022.
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 ar Xiv:23100004406, 2023.
Shuyan Zhou, Uri Alon, Frank F Xu, Zhiruo Wang, Zhengbao Jiang, and Graham Neubig. Docprompting: Generating code by retrieving the docs. arxiv preprint Rtt:::207.00985)
2022.
12

---

Published as a conference paper at COLM 2024
A Evaluating with train-test split
As described in Section 4.2, our episodic retrieval evaluation setting involves holding out one problem a time (i.e., retrieves from the solutions of all other test problems), with the intention of maximally capturing the effect of retrieval on the relatively small dataset available. We expect that this does not lead to any significant dataset leakage across evaluation, as problems are highly independent and ad hoc, with little solution logic shared by even problems of the same algorithm type.
Technique
GPT-3.5
GPT-4
Zero-Shot (7B)
0.795
8.87
Reflexion (7B)
0.89
11.92
Episodic Retrieval
2.65
9.93
Reflexion Episode Retrieval
4.64
14.57
Table 4:
A standard train-test split shows similar results across inference-time techniques, compared to our leave-one-out episodic retrieval setting.
Nonetheless, re-ran the majority of the inference-time techniques against setting with a more standard train-test split. We standardize problem difficulty by generating the same difficulty distribution the entire USACO set. As shown in Figure A, expected, the standard split (train n=200, test n=107) yields similar conclusions with slightly reduced retrieval effectiveness. This is because the amount of problems retrieved over is reduced, thus on average decreasing problem similarity between retrieved problems and the problem currently being solved. Additionally, we re-tune p (number of retrieved passages) on this train set only, and recover the same optimal values as the leave-one-out setting.
B USACO Details
B.1 USACO Zero-Shot Prompt
Please reply with Python solution to the belex problam. Make wrap your code in en "python' and eos Markdown dalinitara, and include exantly black of cade the entire solution fin final code step).
through problem
step by step, Specifically:
Restate preblem plain English
Conceptuslize solution
plain English
Nrise preudacode solution
Cutput final Python solution your steps in ccmments.
libraries are allowed
[BEGIN PROBCEM)
(INSERC PROBLEM HERE)
[BND PROBLEX]
Figure 6: USACO zero-shot prompt. We find that asking the model to describe its reasoning + pseudocode first lead to more parse-able and human-interpretablee generations, making qualitative analysis greatly simplified. is also beneficial for utilization in retrieval queries, as it contains more algorithmic keywords. However, it does not boost the performance sig- nificantly: the choice prompt it to do the extra steps for zero-shot performance evaluation is more for interpretability benefits.
13

---

Published as a conference paper at COLM 2024
B.2 USACO Zero-Shot Error Breakdown
Model
Wrong Ans.
TLE
MLE
Runtime
Syntax + Other
CodeLlama (7B)
61.10
5.05
0
9.89
23.85
DeepSeek Coder (7B)
80.62
10.04
0
6.82
1.86
Claude-3-Sonnet
55.70
24.42
0
14.66
2.61
GPT-3.5
77.42
7.02
0
13.37
1.82
GPT-4
44.15
38.20
0
10.41
1.18
Table 5: Error distributions zero-shot, in %. TLE indicates time limit exceeded, and MLE indicates memory limit exceeded. "Other" generally represents errors stemming from models outputting incorrectly formatted code.
B.3 USACO Zero-Shot Performance By Difficulty
Model
Bronze
Silver
Gold
Platinum
CodeLlama (7B)
0.41
0
0
DeepSeek Coder (7B)
2.30
0
0
GPT-3.5
1.46
0
0
Claude-3-Sonnet
5.69
1.00
0
GPT-4
19.11
3.10
0.16
Table 6: Zero-shot performance of models by difficulty
14

---

Published as a conference paper at COLM 2024
B.4 USACO Qualitative Analysis
Problem ID
Problem overview
GPT-4 error
@177_bronze_mov moo_oppeatioon
Perform string operations change string to "MOO"
(problem understanding)
s
Arbitrarily manipulates letters,
doesn't progress toward target
1300_bronze_stamp_ce
Check if copies of a 2D array can be "stamped" to produce larger 2D array
(format issue)
Doesn't account for empty input
1275_bronze_leaders
Count number of "leaders" a list, following definition
(problem understanding)
Arbitrarily counts, doesn't adhere definition
1301 bbaboonz__watchnng_mmoo
Choose cost-minimizing days to buy subscriptions
(wrong approach) Implements faulty dynamic
programming instead of sorting and iterating
Move a pattern along 1D number line until colliding with a target
(problem understanding) Forgets to jump back to the beginning after each pattern iteration
Figure 7: An overview of some common, general errors on bronze problems, easier problems generally have only 1-2 points of failure and is simpler to analyze.
15

---

Published as a conference paper at COLM 2024
B.5 Sample Generation
pyython
Restating the problen in plein English:
Parmer John is at position and Bossie is the saso 1ine
Farmer dosen't know share Seesie is find walking back forth.
opposi dizection. The tack to calculate the total distance Farmor John will walk until be finde Reesse.
leg jouzney taloe long the peevious
Concuptualizing solution firot in plain English:
John alternates directions,
thes oubtranting adding poaition
2.
We need to take into account both the distance to reverde dizeations and the dietance valked towards
Ne'll incrusent
that atarts and doublea each alteraatin addition
subtraction.
Pawudocode aclution:
1. Initielize total distance and ouxpent, poontion to 0.
2. Initialize direction to 1 (ac Parmer John firet noves to position x+1)
Initielize to
Inoroment total,
etop.
Opdata cureent position by adding step.
c. Change direction (Lf it was 1, make it -1, othervise make it 1).
Double the step value and multiply it disection for the next iteration.
5. Since Farrer John would
add the dtatance fron
whaze pazend.
Ostgut the finst Python solution with solution stops in commente.
3, map (1st, ssput split())
distance Total distance traveled
surrent_pcsstion
direction Direction
moving, right,
stop step sise, will double each time
Continus zig-sagping until Farrar John passes Dessin's position
(direction
(direction
current_positionn
by
step
total dirtance stap
update the cureent position
current position an stop
Ravezes the direction for the naxt
step
stap
Pareer John walked past Ressie's position, so siberact the overehoot diatance coarahoot abe posittion
Output the total distanoe traveled (tont) diacance)
Figure 8: Sample zero-shot generation by GPT-4
16

---

Published as a conference paper at COLM 2024
C
Inference Time Methods
C.1 Addressing Memorization
We address memorization by performing ablations on the corpus in table C.1: retrieved problem solutions were spurring regurgitation of memorized solutions to the current prob- lem, removing core parts the retrieved solutions should not dwindle this effect. However, we find that it does: utilizing solely the problem description only retains 3.18% of the performance, suggesting that models are truly utilizing the reasoning of similar problems provided in context to inform their generations.
Retrieval Content
% of maximum performance
PD PD Code English Solution
3.18
100
Table 7: Ablations on episodic corpus content. PD represents problem description.
C.2
Per Difficulty Pass Rates
Model
Bronze
Silver
Gold
Platinum
Reflexion
24.39
4.76
0
Semantic Retrieval
19.72
1.98
0
Episodic Retrieval
26.22
9.5
3.6
0
Episodic Retrieval + Reflexion
35.77
14.0
6.35
Table 8: GPT-4 Pass@1 rates for inference methods per difficulty: We report incrementally superior methods.
C.3 Retrieval Query Ablations
Query Content
Performance
PD
13.36
PD + Attempted Code Solution PD + Attempted English Code Solution
14.33
14.98
Table 9: Ablations on retrieval query, PD represents problem description. Performance measured in pass@1. We find that generally most retrieval queries are somewhat effective, however, including code attempts as well as english solution performs the best, as allows the maximum matching of relevant keywords between compared documents.
17

---

Published as a conference paper at COLM 2024
C.4 Environment duplicates
esta man mnatia))
wowpoiaaaaaa..... 2015 COE PaRce!
U21,
1783 Frem
vind 743
1011 romm
(131 slwe setanglen, seeen, fiale retumbin?
1130 Moue Saame J0e ws tare wa' aiteer dus shoupratoo
M0
140 yiiwe,, toate resectinn
mom lepatocs wilh los't
24 bow.o.
102 Steaee 3ass, arine..
fant)
123
ant wilh
belense seringsf
de Scaos
1122 2123 201L, EN Jeimnt 1922 SedEos SiCaa,
0t
1121) www.aoa pedieees 1201
LI mil code0s 110 2000s, sitea' stiee mesuids
38
Mullia pacclleces 48 ailk mactloee
12B alule
ALLAL TE3
s00000 Seaais shac.
apptica" 1100 Jonnns) whher momklerk anld Kieett
te vihter
Figure 9: A list of problems that were not originally solved zero-shot, but is solved with episodic retrieval, as well as a list of the relevant problems retrieved by problem id, listed in decreasing order of relevancy.
Problem environment duplicate retrieval We want to quickly point out here that USACO reuses problem environments occasionally. For example, there exists both gold and platinum versions of the problem "pareidolia," " both asking users to develop different algorithms regarding to strings. Although the problems utilize the same problem environment, the algorithms and reasoning behind the solutions differ greatly, making it still nontrivial task to solve the problem even given the solutions to the alternate problem. Additionally, we find that only 33% of newly solved problems contain one or more retrieved content that fall into this category: the full list can be found in figure 9. The rest retrieve problems that are completely separate.
C.5 Hyperparameter Tuning
Problems Retrieved
Pass@1
p 1
13.03
p =
14.33
p 3
13.11
p
12.38
Table 10: Episodic retrieval hyperparameter tuning: Here we tune over how many problems to retrieve over on the USACO307 dataset. GPT-4-turbo-110 was used in all experiments here. We see that p = is optimal in pass@1. did not test resampling for greater numbers of p to conserve budget as performance in pass@1 was already dropping.
18

---

Published as a conference paper at COLM 2024
Reflexion Iterations
Pass@i
8.7
1
10.75
2
12.28
3
12.38
= 4
12.38
12.40
Table 11: Reflection iteration tuning: Here we tune over how many times to iterate. All experiments were done with GPT-4. 0 indicates the original solve rate without any reflection. We see that solve rates remain relatively static after 3 iterations.
C.6 Reflexion Prompt
You were previously solving coding problems.
the problen that you were solving:
(problam dict[query] "preblem id']l[ 'ddscriptionn)
And here are all past attempts, as well how your code fared on the unit tests for the problem: (query[ ('reflection buffer'])
you went wrong your went wrong. Then, given your insights, try to fix the solution, outputting block of correct python3 code to executed evaluated again. Make aure to wrap your code in "python' and Markdown daliniters.
Think carefully
outputting why you think
Figure 10: Reflexion prompt
C.7
Retrieval Prompts
Flease reply with Python 3 solution the below problen. Make sure wrap your code in 'python' and Markdown
and include exectly bleck code entice solutico
atep).
given sultiple sozewhat problens,
sinilar problens. Feel free to use those problens to aid your problen solving process.
Reason through the problen and:
Restate the problen plain English
Conceptaslise aolusion
plain Eoglish
pseudocode
4. Output the final Python solution with your solution steps in comment.
No outside libraries are allowed.
(quasy I' culeiieal bext']) (Sinilar peoblus problun goes harw)
[EXD SINIIAR PROBLEMS]
Now Bere the problen solve:
[problen, diet(quary| petouuaylpyppaaann.er id' [][ description'') (Descripticn problem goea bere)
[EXD P90818M]
Figure 11: Episodic Retrieval Prompt
19

---

Published as a conference paper at COLM 2024
Plaase zeply with Python solution belov problen. Make aure weap your code python' and Markdown
del inii beze, and include exactlly block of code with the entire solution
final code
will
texthook relevant
Peel free
your problem solving process.
Reason through the problen and:
1. Bestate the problen in plain English
2. Conceptualine soluzion first in plain English
psendecode solution
Output
Python
your steps
No outxide are
[BBGIN RELEVANT TEXTBOOK SECEION]
wwetrreeeaaaeeeeeeeeee (Textbook [EX
6BCTION)
Now it a your turn. Bere is the problen you aze to solve:
[BSGIN PROBLEM)
pproblon diet[quryt' ppppellanndddd desccription')) (Desoription [EXD PROBLaM
Figure 12: Semantic Retrieval Prompt
You were previously solving coding problems. llere the problen that you were solving:
(problan diet[query| pproblen id'll 'dascription']1
You were also given couple of similar problems to the problen above along with their solutions to sid you in solving the problem at hand. llere are the similar problems you were given:
(quary('zetriev) "wetrieval_teereeeee
And here was your original respense.
(queryl foriginal, response '])
Bare
reault
solution:
(queryl weweeeeteeereeppppppeeeee response')
Think carefully about where you went wrong. Then, try to fix the solution, outputting a block
python3 executed evaluated again. wrap your code .... "python' and Karkdown delimiters.
Figure 13: Reflexion Retrieval Prompt
20

---

Published as a conference paper at COLM 2024
D Human-in-the-loop
D.1 Human-in-the-loop Prompt
Human Tutoring Instructions
You to interact with given model to try to solve given coding question. problem solving session ends whenever the model has generated code times. Between code generations you may speak to the model conversation as many times as you would like. However, the way you interact with the model must be very specific: your goal is to act akin to tutor and guide the model towards the right answer, without giving away any underlying details about the true solution the problems.
You MAY NOT provide the models with:
The correct algorithm fix their initial solution
Exact lines of code where they went wrong
Explanations of the problem or explanations of misunderstandings
You MAY provide the models with:
General concepts/data structures that may be useful for solving the problem
Walking through sample input output of the problem to better verify problem understanding
Short concise general directions on where the code went wrong
Here examples of correct trajectories:
The prompt given to human tutors when interacting with the model. We manually inspect trajectories to ensure rules were followed. To limit the amount of conversation, we only allow the model to generate code times: however, the code is only allowed be executed once to simulate pass@1 setup.
Figure 14:
D.2 Human-in-the-loop sample trajectory
21

---

Published as a conference paper at COLM 2024
Please reply with Python solution to the beion probiem. Make sure to wrap your code
aclution. "Markdownn deliviters, and include
oode with
block seluaion
code
Mock with exp applonatory text before andjor after however you will only be euilussted on the correctness
[BEGIN PROBLEM) Ferner John has lest his prize cow Bessi,, and he noods to finditert
Fammer
Fortunanely, there only one long path nunning scroen the farm, and farmer John lonowa that think of
Sesce
cuncetly pocitionn
ourrently or pocition
Farmor
Johno, farmer John only knnw where Bossle was locuted, he could walk direcily hes,
traveling distance Unfortumately, dark outide and Farmer John can't arything way hor positio.
forth undilihe eventuolly
Lest soeetst tst, y1 146) 1981 directionn
start postttis
drtntlddttttnee.co traveted
Trust
destinatian atart, etractiin
distance, traveled abolstert, posiitionn destinttias)
einsstarr__sssttinn, testtnatton) eoc (atssatttttttttttte
This cade not cornec. There several code, but think importent verily your undentanding the problem. Let's make sure you undersland problem correctly Let's through the sample case together, whore the farmor starts at and
round,
Farmer John starts position in move, to position 30im4, Then changes direction and moves twice distance moved his previcus
moves
position and up in position 2-22 postiit 2, hos traveled total of units- unitooo the righ unit the left.
aft
understand, where fould
again
the prrvicur the right from cusmet pandit on of endiup position 1-4 This sound covers tutall distarce of units. So alter Brounds, hhe should be
The cornect. should actuaity poaition What masing undentanding the
moszakk inricundertood the direction changer and distance increments unted
position: mowe relution starting praition, round, cherlidance moves coublles magaibudee and itematte in direction.
sarting position Knnwing this, you implementt code that exhibits theintuitinn we described above?
+
def tast_cowee cowte: tnt,, (itt) vo frtt:
current
directios #
Lotel ttr.ossttttttreroooo traeeltreelll
white Truez
Rove pastetin relotive starctng pasiction
nest_position dfrection
Accumolate traveled
total_
pasitions,
nest_josttlen ce maxtesrrent, sest_posttion)
tstal distance traveled abainext poaition y)) break
Fresore nest Eteration
Figure 15: Sample human tutoring trajectory on the problem 786 bronze the lost. cow
22


Reviews:
[{"review_id": "vxYW94ilWU", "reviewer": "Reviewer_hsvi", "summary": "The paper contributes an important benchmark of challenging problems from the USA Computing Olympiad. These questions are shown to be quite challenging for the current state of the art LLMs including some that for meant specifically for code generation. In addition to the questions, the USACO corpora that is contributed also contains other very useful resources that can help improve the LLM capabilities like exhaustive unit tests and expert written problem analysis. \n\nIn addition to the corpora, the also explore improving the zero-shot performance of the LLMs through various different techniques, like (1) Self-reflexion, (2) Retrieval augmentation, both semantic and episodic; and their combinations. They found that looking at it's own output and execution feedback helps a lot. They also see that combining them with episodic augmentation helps the most. \n\nThey further showed how the model can improve significantly by a human in the loop framework. This very interesting as it suggests that with the right set of reasoning guidance the model can actually get the answers correctly.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your encouraging comments and suggestions! We address and give relevant clarifications for each of your questions/concerns below:\n\n## 1. Clarification on human-in-the-loop trajectories\n\nWe appreciate the interest in the details of the human-in-the-loop experiment!\n\nSince models showed poor pass@1 performance on difficulties harder than bronze, we focused on bronze problems for the human-in-the-loop experiments, choosing a distribution of **13 bronze, 1 silver, and 1 gold**.\n\n(The strongest model, GPT-4, achieved 19.1% on bronze, 3.1% on silver, and only 0.16% on gold) \n\n## 2. Keeping the benchmark updated\n\nThank you for pointing out the \"time machine problem\" -- the need to make benchmarks resistant to test set leakage into new models' training data.\n\nOverall, we are optimistic that the **ongoing nature** of the USA Computing Olympiad contests will help make the USACO benchmark leakage-resistant by allowing us to continuously update the benchmark with new contest problems. \n\nWe (1) hope to release updated versions of the benchmark that include newer contest problems (2) have designed our benchmark to be easy to use in ways that both reveal and resist leakage, including standardized problem and solution formats that simplify supporting new and custom problems, as well as easy-to-use and efficient batch evaluation infrastructure that can reveal temporal effects by comparing performance on subsets of the benchmark data. \n\nAs an example of the second point, in the paragraph of Section 3.1 in the paper entitled \"Temporal effects are strong,\" we discuss an experiment that additionally evaluates on a subset of 36 problems released after training cutoffs and find that solve rates reduce, pointing to potential contamination in current models, even while they perform poorly on the vast majority of the benchmark.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "This paper makes a significant contribution by contributing an important benchmark of challenging programming questions. These evaluations help present gaps in the code understanding the reasoning capabilities. \n\nThe authors also do extensive study on how to do well at these tasks and by sharing these approaches it helps get insights into understanding what could potentially be lacking in LLMs and how these capabilities can be enhanced. \n\nThe paper is also clearly written and well presented. Including the appendix section which helps the reader understand how the models were prompted.", "reasons_to_reject": "My biggest concern is how to handle the time machine problem. As the models get trained with more recent data the benchmarks has the potential to become not so useful. It would be great to get a sense of how the authors are planning on keeping the benchmark updated.", "questions_to_authors": "1) Among the 15 questions that were chosen for the human trajectory, and used to solve with GPT-4 and GPT-3.5 what was distributions of the 13 questions GPT-4 got right( #s of gold, silver and bronze)?\n\n2) Have you thought about how are you planning on keeping the benchmark updated? As I understand as there are more training runs, it's possible that these benchmarks get consumed in the LLM training. What measures do the authors plan to take to mitigate that?", "extra_scores": {}}, {"review_id": "j8Vb4nKTfh", "reviewer": "Reviewer_hDmn", "summary": "The authors present a new benchmark with 300 competitive programming exercises, which unlike prior benchmarks combines high-quality unit tests (for automatic evaluation), expert-written analyses of the problems (for high-level analysis), a wide range of highly-applied problem statements (to stress the ability of LMs to write code that adapts to novel problem settings). The nature of these competitive programming exercises lends them well to evaluation: by design, each problem is assigned a (human) difficulty level from bronze to platinum as well as realistic limits on run time and memory constraints. The authors evaluate several LMs within different prompt pipelines, and find that they struggle with almost all questions, and generally answer very few of the highest-difficulty questions, despite producing runnable code. The authors conduct several insightful analyses, including a simple human-in-the-loop in which GPT-4 can consistently learn from human interactions to correct its mistakes, while GPT-3.5 can never productively leverage similar feedback.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We highly appreciate the thoroughness of the review given! We address your concerns below:\n\n## 1. Evaluation setting\nThe retrieval setup is based on:\n\n(1) Qualitatively, problems are indeed **very independent** with little solution logic shared by even problems of the same algorithm type.\n\n(2) Our goal is to **maximally** showcase the effect of retrieval on a relatively *small* dataset using a k-fold-type evaluation that holds out one problem at a time.\n\nFor verification, we have added a traditional train (n=200) and test set (n=107), achieving similar conclusions with slightly reduced retrieval effectiveness:\n| Tech. | GPT-3.5 | GPT-4 |\n| -------- | ------- | ------- |\n| Zero-Shot |  0.795 | 8.87 |\n| Reflexion | 0.89 | 11.92 |\n| Episodic | 2.65 | 9.93  |\n| Reflexion + Episodic | **4.64** | **14.57** |\n\n(Certain settings omitted for concision)\n\nWe also re-tuned p (num retrieved passages) on this train set only, and got the same values as the original.\n\n## 2. Reporting Pass@1\nWe ran additional experiments replicating Figure 3 **entirely in pass@1**, following the suggested setup of pass@1 Reflexion. The choice of pass@k does not affect our key findings.\n| Tech. | GPT-3.5 | GPT-4 |\n| -------- | ------- | ------- |\n| Zero-Shot |  0.59 | 8.70 |\n| Reflexion | 0.97 | 12.38 |\n| Episodic | 5.49 | 14.33  |\n| Reflexion + Episodic | **8.79** | **20.20** |\n\n## 3. Human-in-the-loop setup\nThe non-uniform distribution across problem difficulties reflects our **focus on bronze problems** which have relatively higher solve rate yet overwhelmingly remain unsolved using current techniques.\n\nFurther experiments show pass@k for k=10 improves performance across models, making differences less interpretable. We will update the paper to make this more clear!\n\n## 4. Time-sensitivity\nWe found that even with pass@k for k=4 on bronze problems, performance **still** drops to zero for the set of 36 new problems we tested.\n\nWe are indeed concerned about any data contamination. However, it is also useful to keep in mind that:\n\n(1) USACO problem difficulty increases **substantially** year-over-year. Through community difficulty labels (https://codetiger.me/project/usaco/) we see some recent bronze problems compare with the difficulty of old gold problems!\n\n(2) Our benchmark is sufficiently challenging to remain almost entirely unsolved despite potential contamination.\n\nWe also hope supporting the continuous addition of new USACO problems can further mitigate contamination.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "The benchmark is well-motivated, well-described, and well-constructed, and I can see it becoming a standard evaluation testbed after other existing coding (and other) benchmarks in this space have been saturated and lost much of their original power to distinguish the best LMs.\n\nThe authors do a great job laying out how the unique properties of their data (some by nature of their source; others by construction) allow for a deeper level of investigation into LM abilities, e.g. the difficulty level from bronze to platinum, realistic limits on run time and memory constraints, covering a wide range of highly-applied problem statements.\n\nThe findings of LM failures are well-explored and are likely to motivate real and near-term advancements in LM systems that outperform the current generation of systems.", "reasons_to_reject": "The authors' own evaluation methodology is ambiguous at best. For example, some of their evaluations consider \"retrieval\" (from *every other* problem-solution pair) to solve problems. It's unclear that this is a reasonable setting, unless the level of independence between problems is very high. Could the authors instead have divided the data by competition year into dev/test for example, and held the test data out to a higher standard?\n\nAlong similar lines but perhaps more confusing are the following. Quite a few explorations like Episodic Knowledge Store (e.g., perhaps most egregiously parameter p's tuning in Table 8) are evaluated directly on the 300-example test set in a way that will quickly reduce the shelf-life of this data, and is reminiscent of essentially tuning on the test set. Are some of these meant to represent some sort of oracle settings? I understand the need to explore some hyperparameters, and that's why I advise the authors to dedicate some data explicitly for tuning/development. Of course, this all challenges the usage of \"zero-shot\" prompts, since some data is now more explicitly available for tuning.", "questions_to_authors": "The reporting of pass@1 and pass@4 are inconsistent and justified in an unclear way. The authors say they switch from pass@1 to pass@4 in Figure 3 \"fairly compare to the setup only utilizing reflection memory, whose pass-rates stabilize past 3 inclusions of previous attempts\". Is such Reflexion getting exposed to any hidden test data? If not, then the system can realistically do as many internal trials as it wants while only \"submitting\" once, making this arguably just pass@1.\n\nHow was the set of 15 problems for the human-in-the-loop study chosen? They appear non-uniform, i.e. 13 bronze, 1 silver, 1 gold. In any case, the authors use their human-in-the-loop study to suggest that we need \"better evaluation metrics beyond the overly strict execution success\", but as far as I can tell it's plausible that we just need to evaluate pass@K for larger K or possibly Reflexion-like methods, which appear to expose the difference between LMs better than pass@1, alleviating most of this concern. If this is not true, I don't think the current discussions make that clear.\n\nThe authors report an intriguing and useful figure: they evaluate LMs on 36 problems released after training cutoff dates and \"find that solve rate drops to 0 for all models\", noting that \"USACO questions are well known to increase in difficulty every year, making this likely an effect of both difficulty increases as well as inclusion in pre-training data\". Dropping to zero is concerning. What about pass@4 for the best LM systems tested, for the new \"bronze\" (easy) questions. Is it still at zero? **If** so, and unless there's a very dramatic increase in difficulty in the competitions, with redefinition of the notion of \"bronze\" to make them much harder in the new 36 problems, this suggests a very serious amount of leakage in practice to LM training data. That would not be the authors' fault in any way, but it does pose problems for the utility of this data as an ideal benchmark.", "extra_scores": {}}, {"review_id": "cZPG1tJVgR", "reviewer": "Reviewer_mWB9", "summary": "This paper introduces USACO, a coding benchmark with 307 challenging problems from past USA Computing Olympiad competitions. These problems require a wide range of algorithmic, mathematical, and commonsense knowledge, as well as grounded reasoning. Even the best LLM (i.e. GPT-4) only achieves a zero-shot pass@1 solve rate of 8.7% on USACO, indicating the need for better models and inference methods. To address this, high-quality unit tests, reference code solutions, and official analysis for each problem, along with instructional texts in the form of competition programming textbooks are collected.  Baseline methods based on retrieval and self-reflection, and combined are proposed to improve performance. However, all methods still fall short of solving the benchmark above the bronze level. To gain further insights, a human-in-the-loop study where participants interact with the language models in a tutoring setup is further conducted. The study highlights the potential of incorporating high-quality feedback and the need to develop methods for generating human-level corrective feedback.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your encouraging and thoughtful comments!\n\nRegarding your question about potential data contamination: We are optimistic that the **ongoing** nature of the USA Computing Olympiad contests will help make the USACO benchmark leakage-resistant by allowing us to continuously update the benchmark with new contest problems. We (1) hope to release updated versions of the benchmark that include newer contest problems (2) have designed our benchmark to be easy to use in ways that both reveal and resist leakage, including standardized problem and solution formats that simplify supporting new and custom problems, as well as easy-to-use and efficient batch evaluation infrastructure that can reveal temporal effects by comparing performance on subsets of the benchmark data. \n\nAs an example of the second point, in the paragraph of Section 3.1 in the paper entitled \"Temporal effects are strong,\" we discuss an experiment that additionally evaluates on a subset of 36 problems released after training cutoffs and find that solve rates reduce, pointing to potential contamination in current models even while they perform poorly on the vast majority of the benchmark.\n\nOn problem rewriting: the high difficulty of USACO problems makes them relatively infeasible to rewrite compared to DS-1000 [1]. Simultaneously, though, that same difficulty leads models to struggle on even potentially-leaked older problems. Thus, **beyond mitigating leakage by updating with new problems, we expect the current benchmark to be resistant to effects from leakage and remain a useful, challenging code evaluation.**\n\n[1] DS-1000: A Natural and Reliable Benchmark for Data Science Code Generation. ICML 2023", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "I think this is a nice resource paper. The proposed benchmark USACO has the potential to become a valuable tool for advancing research in program synthesis with LLMs.\n\n- Well-written and organized: The paper is clear and easy to follow, with a logical structure that guides the reader through the research.\n- Motivation: This paper effectively highlights the limitations of existing benchmarks and the need for a more challenging and realistic evaluation of LLM capabilities. The proposed USACO addresses this critical gap in existing function-level code generation benchmarks, which are saturated and may not accurately reflect the real program synthesis abilities of LLMs.\n- Comprehensive experiments: This paper presents extensive experiments on the USACO dataset, exploring various inference-time LM methods and conducting a human-in-the-loop study to gain deeper insights into the capabilities and limitations of LLMs for Olympiad programming. The human-in-the-loop study provides valuable insights into the strengths and weaknesses of LLMs for program synthesis, complementing the quantitative results obtained through automatic experiments.", "reasons_to_reject": "I do not have any major concerns about this paper, but I do have a few questions about the dataset construction and data contamination  (see below).", "questions_to_authors": "I am wondering if you have any measures to alleviate the data contamination issue, as the problems and the ground-truth solution are collected from the public-facing pages [1][2]. Researchers may also crawl the problems and the corresponding solutions from these websites to pre-train or instruction tune the LLMs. Prior efforts adopted different measures to deal with this case. For example, DS1000 rewrote problems and reference solutions. Another one is codecontests, all training data in CodeContests was publicly released on or before 2021/07/14. The test set contains problems published after 2021/09/21.\n\nReferences:\n[1] Stop Uploading Test Data in Plain Text: Practical Strategies for Mitigating Data Contamination by Evaluation Benchmarks. EMNLP 2023\n[2] NLP Evaluation in trouble: On the Need to Measure LLM Data Contamination for each Benchmark. EMNLP 2023\n[3] Competition-level code generation with alphacode. Science 2022\n[4] DS-1000: A Natural and Reliable Benchmark for Data Science Code Generation. ICML 2023", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper introduces a new, very challenging benchmark based on USA Computing Olympiad contest questions. I am recommending acceptance based largely on the fact that this seem like it is a valuable new challenge task for LLMs.

I do have on lingering concern: reviewer hDmn raised a question about evaluation. The authors reported new experiments in their response, and they claim that the experiment doesn't fundamentally alter anything. However, this seems too simple. Their new results show a significant drop in performance once they introduce a train/test split. This could indicate that different splits would yield radically different result, or that the previous results were based on too much information from the test set. We just don't know. The qualitative results *were* impacted, though.

I think the above concern does not warrant rejecting the paper, but I would encourage the authors to think carefully about how to use their benchmark as a reliable tool for assessment and comparison.
Decision: Accept