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.
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.
The 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.
The 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?
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 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.
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.