Can Language Models Solve Olympiad Programming?

Authors: quan  shi
michael  tang
karthik  narasimhan
shunyu  yao
  cow
🐮  guernsey
🐄  holstein
Venue: colmweb_org_COLM_2024_Conference
Published: 2024-03-22 20:59:40

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.

Main paper: 
 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 methods (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 is a natural fit for this pursuit, as it 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 a task to solve in a fictional scenario, along with some example tuples of inputs, outputs, and explanations. Solving these problems not only require a 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 a zero-shot pass@1 solve rate of 8.7% using zero-shot chain-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 Figure 1 : Example USACO problem description, formatting instructions, and illustration (problem id: 1275 bronze leaders). Solving this problem requires a 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 a novel human study where humans interact with LMs in a conversational "tutoring" setup by pointing out errors and giving minimal hints. To our surprise, on a 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 programming with high quality test cases, problem analyses, and auxiliary resources.• For the first time, we construct and test LM inference methods for Olympiad programming, 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 to automatic experiments based on execution success. We find that only certain models can successfully incorporate feedback, uncovering latent differences between models 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 a 94% solve rate on HumanEval (Zhou et al., 2023) , indicating a need for harder, more complex, yet self-contained coding tasks to probe the upper limit of code reasoning. Competitive programming questions have thus been proposed as a more difficulty 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 et al., 2021; Li et al., 2022) . However, these problems largely do not contain quality problem analyses, comprehensive correctness-defining 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.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 et 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. Sumers et al. (2022) investigates agent learning from human provided feedback under synthetic tasks. Macina et al. (2023) aims to provide a tutoring ruleset to effectively engage LMs in dialogue math problem solving. In this paper we adopt a similar setup to code, applying a specified interaction ruleset to gauge the ability of models to respond to feedback. 
the usaco benchmark: 
 The USACO benchmark consists of 307 high-quality expert-written problems from past USA Computing Olympiad contests (https://usaco.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-written 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 or outputs, but can receive information on how many tests a given solution has passed.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, problemsHumanEval (Chen et al., 2021) APPS (Hendrycks et al., 2021) CodeContests (Li et al., 2022) 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. We collect 484 problems from https://usaco.org detailing materials on contests hosted between 2011 and 2023 using a custom HTML parser, and use regular expressions to extract wall clock time and memory constraints from problem descriptions. which are manually verified using solutions with correct and incorrect asymptotics.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, as well as a 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 on the given constraints.We begin by evaluating zero-shot performance of models representing state-of-the-art coding performance as a baseline: this includes GPT-3.5 (gpt-3.5-turbo-1106), GPT-4 (gpt-4-1106-preview), Claude-3-sonnet, (claude-3-sonnet-20240229), CodeLlama2-Instruct-7B, and Deepseek-Coder-Instruct-7B (Roziere et al., 2023; Guo et al., 2024; OpenAI 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 6 for full prompts. Following previous work on competitive programming (Li et al., 2022; Hendrycks et al., 2021) , we evaluate primarily based on the unbiased pass@k metric defined in (Chen et al., 2021) .Solve rates near zero for gold difficulty and above. We find that USACO presents a strong challenge to current generation models. Weaker models like GPT-3. 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 a small selection of 36 problems released after training cutoff dates. We find that solve rate drops to 0 for all models. However, we do note that USACO questions are well known to increase in difficulty every year, making this likely an 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 on 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, we adapt self-reflection and retrieval techniques widely successful in other domains to USACO.Self-reflection techniques aims to allow models to iteratively improve generations by conditioning future output on execution feedback of previous attempts. We primarily experiment with Reflexion (Shinn et al., 2023) , a representative technique that additionally maintains an episodic buffer of past attempts to induce better reasoning in future trials.The model is first prompted to 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 as the contents of a buffer of past solve attempts. After each iteration, the previous attempt as well as the execution results is added to the buffer. This loop iterates until a maximum number of debugging steps is reached. We set this hyperparameter i = 3 as we observe no empirical gains in solve rate past 3 rounds of debugging: see Appendix C.5.Retrieval augmented generation (RAG) has similarly proven to reduce hallucinations and improve reasoning capabilities in a variety of 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 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, or 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 as a competitive programming textbook, and the episodic knowledge store as the bank of USACO problems and solutions not currently being solved.We use the cp-algs textbook (https://cp-algorithms.com), which contains 30 human-written chapters on 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.We simulate a setup where the model has seen all other problems in the USACO set except for the current one it is solving, simulating a k-fold evaluation that holds out one problem at a 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, as 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 = 2 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 containing code and english explanation. This allows accurate retrieve relevant algorithm descriptions from the underlying retrieval corpus, as solely utilizing the problem descriptions 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 description, is fed into a BM25 retrieval function, and the highest ranking document is inserted into the context to aid the real solving process. Prompts can be found in Appendix C.7. We additionally note that retrieval-based methods and reflection methods are orthogonal and can be sequentially applied. Thus, we test settings combining various combinations of retrieval types, as well as retrieval combined with reflection. Evaluation All methods are evaluated Pass@1.For self-reflection, we 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.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 an emergent property of stronger models, consistent with (Shinn et al., 2023; Chen et 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, on 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 are also newly solved by episodic retrieval. It provides one possible explanation as 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.2Performance gains are not due to memorization. A competing hypothesis for the success of retrieval is 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 no significant overlap in generated and official published solutions. Full experiment details can be found in Appendix C.1.We focus our qualitative analysis on the improvements of retrieval, our individually strongest inference-time technique. Here, we isolate 3 examples of problems newly solvable with RAG in figure 4 .Figure 4 : Three examples of problems previously unsolved, but solved with retrieval.Example 1: 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-only 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 can 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 on 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 chapter indicated that the chapter was short and light on details, thus receiving a low retrieval score. This highlights the flexibility of the retrieval query to adapt to low quality documents, finding suitable replacements. 
human-in-the-loop 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."Setup A human provided with problem solutions engages in a 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, a maximum of 5 code generations to limit conversation length, and a total of 3 attempts per problem. Results Surprisingly, we find that on a small set of 15 problems1 on which GPT-3.5 and GPT-4 achieve zero pass rate using all of the above inference-time methods, the human-in-the-loop setup raises GPT-4 performance from 0% to 86.7% (13 problems solved) while not improving GPT-3.5 performance from 0%. Qualitatively, GPT-3.5 consistently hallucinates fixes irrelevant to feedback, while GPT-4 pinpoints accurate algorithmic fixes in response to minimalistic feedback. A sample trajectory is provided in Appendix D.2.We found that GPT-4 was more responsive to blanket feedback that its algorithm or understanding 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 correct overall solution strategy after being instructed to not use a heap in "Hungry Cow," and similarly after being instructed not to use DP in "The Lost Cow." In "Photoshoot," it suffices to ask GPT-4 "Is there any way we can use the inherent ordering of the cows and directly calculate the number of steps necessary?" to correct it from a 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 specific fixes, unlike GPT-3.5. For example, on "The Lost Cow," GPT-4 tends to calculate the next position using the current position instead of the initial position -if given this fact, it produces the correct implementation.2 Discussion Our human-in-the-loop 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 fundamentally 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 to generate such feedback. 
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 at basic coding tasks like HumanEval (Chen et al., 2021) perform poorly zero-shot in these more challenging scenarios, but that providing models with task-specific knowledge stores can well over double zeroshot performance. We hope that our evaluation of current models' limitations and findings on the effectiveness of semantic and episodic knowledge help lay groundwork for its integration into future models and language agents alike. 
 
 Appendix: As described in Section 4.2, our episodic retrieval evaluation setting involves holding out one problem at 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. Nonetheless, we re-ran the majority of the inference-time techniques against a setting with a more standard train-test split. We standardize problem difficulty by generating the same difficulty distribution as the entire USACO set. As shown in Figure A , as 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.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-interpretable generations, making qualitative analysis greatly simplified. It is also beneficial for utilization in retrieval queries, as it contains more algorithmic keywords. However, it does not boost the performance significantly: the choice to prompt it to do the extra steps for zero-shot performance evaluation is more for interpretability benefits. 13 bronze, 1 silver, 1 gold. We focused on bronze problems since models performed poorly on harder difficulties.See https://benshi34.github.io/blog/2024/human-in-the-loop/ for more trajectories and analysis for different difficulty levels. 


Decision: 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.

Reviews: review: paper_summary: paper_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. 

In 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. 

They 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.
strength_weakness: strength_weakness: 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: questions: 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)?

2) 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?
paper_summary: paper_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.
strength_weakness: strength_weakness: 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?

Along 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: questions: 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.

How 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.

The 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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: questions: 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.

References:
[1] Stop Uploading Test Data in Plain Text: Practical Strategies for Mitigating Data Contamination by Evaluation Benchmarks. EMNLP 2023
[2] NLP Evaluation in trouble: On the Need to Measure LLM Data Contamination for each Benchmark. EMNLP 2023
[3] Competition-level code generation with alphacode. Science 2022
[4] DS-1000: A Natural and Reliable Benchmark for Data Science Code Generation. ICML 2023

Comments: comment: Thanks for the response! Your strategy makes sense to me, I would strongly encourage maintaining an ever updating benchmark in the current world of LLMs!
Thanks for the response. I think the authors addressed some of my concerns. I will keep my score at 8.
Thank you for the discussion. The content does not fundamentally alter my assessment of the work, so I'll keep my 7/10 score.