ALGO: Synthesizing Algorithmic Programs with Generated Oracle Verifiers
Authors: Kexun Zhang
Danqing Wang
Jingtao Xia
William Yang Wang
Lei Li
Venue: NeurIPS 2023 poster (2023)
Keywords: Large Language Models
Code Generation
Code Intelligence
Automatic Verification
TL;DR: We propose an algorithm synthesis framework that leverages LLM-generated oracles to guide the creation of efficient algorithms and verify their correctness.

Abstract: Large language models (LLMs) excel at implementing code from functionality descriptions but struggle with algorithmic problems that require not only implementation but also identification of the suitable algorithm. Moreover, LLM-generated programs lack guaranteed correctness and require human verification. To address these challenges, we propose ALGO, a framework that synthesizes Algorithmic programs with LLM-Generated Oracles to guide the generation and verify their correctness. ALGO first generates a reference oracle by prompting an LLM to exhaustively enumerate all the combinations of relevant variables. This oracle is then utilized to guide an arbitrary search strategy in exploring the algorithm space and to verify the synthesized algorithms. Our study shows that the LLM-generated
oracles are correct for 88% of the cases. With the oracles as verifiers, ALGO can be integrated with any existing code generation model in a model-agnostic manner to enhance its performance. Experiments show that when equipped with ALGO, we achieve an 8× better one-submission pass rate over the Codex model and a 2.6× better one-submission pass rate over CodeT, the current state-of-the-art model on CodeContests. We can also get 1.3× better pass rate over the ChatGPT Code Interpreter on unseen problems. The problem set we used for testing, the prompts we used, the verifier and solution programs, and the test cases generated by ALGO
are available at https://github.com/zkx06111/ALGO.

ALGO: Synthesizing Algorithmic Programs with LLM--Gnerated Oracle Verifiers
Kexun Zhang' Danqing Wang'
Jingtao Xia'
William Yang Wang' Lei Li
UUnveesitty of California Santa Barbara Carnegie Mellon University
[kexum, danginwwan,g ingtaoxia, silliamm@ucstee @wc.b.uucbbbee.o. leiliScs. cmu, edu
Abstract
Large language models (LLMs) excel at implementing code from functionality descriptions but struggle with algorithmic problems that require not only implemen- tation but also identification of the suitable algorithm. Moreover, LLM-generated programs lack guaranteed correctness and require human verification. To address these challenges, we propose ALGO, framework that synthesizes Algorithmic programs with 4LM--Genrrate Oracles to guide the generation and verify their correctness. ALGO first generates a reference oracle by prompting LLM to exhaustively enumerate all the combinations of relevant variables. This oracle then utilized to guide an arbitrary search strategy in exploring the algorithm space and to verify the synthesized algorithms. Our study shows that the LLM-generated oracles are correct for 88% of the cases. With the oracles verifiers, ALGO integrated with any existing code generation model in model-agnostic manner enhance its performance. Experiments show that when equipped with ALGO, we achieve an 8x better one-submission pass rate over the Codex model and a 2.6x better muesimmissionn pass rate CodeT, the current of-th-of-the-rt model on CodeContests. We can also get 1.3x better pass rate over the ChatGPT Code Interpreter unseen problems. The problem set used for testing, the prompts we used, the verifier and solution programs, and the test cases generated by ALGO are available at httph::///// wtw.thhh...o.eeeeeeeeeeeeeeeeeee httpp:////ghhub.ccoooooo011111/ /ttp/////0x1100000000
1 Introduction
Large Language Models (LLMs) have demonstrated significant prowess in generating code from natural language descriptions. Models such as Codex [5] and CodeGen 233 can easily achieve over 30% pass @ accuracy on HumanEval, docstring-to-code dataset. However, these models struggle when faced with algorithmic problems akin to those encountered in CodeContests [17. Even with reasonable sample limits, achieving 10% accuracy rate remains considerable challenge 4 More recently, the GPT-4 model, despite being provided with problem descriptions and solution hints, managed pass@ @ accuracy of only 10.6% (3] LeetCode Hard problems.
The verifiability of LLM-based code generation presents another significant challenge. Without verifiability, code generation systems can hardly carn trust for production use. Users of GitHub Copilot (21), an Al assistant for programmers, reportedly spend over 20% of their time verifying the suggested code snippets. Existing approaches toward verification and reranking LLM-generated programs either rely neural models to predict confidence scores 22 32) require LLM-generated test cases to execute the programs 4 15). However, neural verifiers do not provide interpretable feedbacks and LLM--genrrted test cases often incorrect.
Traditional code synthesis techniques rely oracles for the verification of the synthesized code. These oracles are typically derived from formal specifications 20 25
29 They can also
be employed in program synthesis under the widely-used framework of oracle-guided inductive synthesis (OGIS) [14. Despite their widespread application code verification and synthesis, the
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Accepted
Time Limit Exceeded
Problem
Verifirr
Referance Orocie
Runtime Error
Wrong Answer
Orade Geniration
Prompt
Output
Inpul Generator
Problem
Coder
Potential Solution
57.1%
Soluton Generation
Code Output
Prompt
fast, mayōe incomeet
Figure 2: The reference oracle generated by ALGO correct for 88.5% of the problems in our benchmark. We consider oracle correct if gets Ac- cepted Time Limit Exceeded verdict LeetCode website and is checked by human ex- perts reasonable solution.
Var ficationn reaulls & fabled laal cases
Figure 1: The ALGO pipeline. The verifier LLM generates the probably correct but possibly slow reference oracle that solves the problem with an exhaustive search. The coder generates more efficient candidate program and refines the candidate program by comparing its output with the oracle's output. The coder can be any existing code generation model.
use of oracles often demands heavy human involvement, and the automatic generation of oracles is challenging. Existing strategies focus on generating oracles that can only detect crashes (safety oracle) or bugs introduced by future changes (regression oracle), rather than semantic bugs crucial for algorithmic programs [9 18 24).
Motivated by the potential benefits of oracles in traditional code synthesis, we introduce ALGO, framework that leverages oracles generated by large language models address the challenges in LLM-based code synthesis and verification. As illustrated in FFiuree I| ALGO incorporates two modules for algorithm synthesis. The verifier instructed to generate an exhaustive search algorithm regardless of time efficiency, thus acting as a reference oracle. Concurrently, the coder is asked to find more efficient solution with any prompts or search strategies. The candidate program's correctness is then evaluated by comparing its output with that of the oracle for given set of test inputs. The results of the verification, along with any cases where the candidate program falls short, are subsequently provided to the coder for code refinement.
We evaluated ALGO based on two key dimensions: the oracle's 's verification capability and its potential to enhance algorithm synthesis. Our experiments reveal that the reference oracles correct for 88.5% of the problems (as shown in Figure 2). Moreover, the oracles' verdicts are in agreement with the golden verdicts of the online judge 75% of the time. To examine the enhancement in accuracy offered by AI.GO, we integrated it with several existing code generation models including Codex (5). CodeT (4) PG-TD [31] and ChatGPT Code Interpreter We observed that ALGO significantly boosts their performance on CodeContests [17] and a collection of recent LeetCode problems. Our experiments show that ALGO notably enhances the performance of these models: in terms of one- submission pass rate, Codex's performance improved by a factor of 8, CodeT's s by 2.6, PG-TD's by 1.5, and ChatGPT Code Interpreter's ' by 1.3.
Our contributions can be summarized as follows:
We present ALGO, a novel framework for Algorithm synthesis that utilizes LLM- Generated reference Oracles as verifiers. It is model-agnostie framework that can be integrated with any code generation model verify candidate solutions with reliable test cases generated by reference oracles.
We conduct a comprehensive evaluation of synthesis accuracy and verifiability of ALGGO, utilizing several distinct code generation models in versatile, model-agnostic manner. Our results indicate that ALGO can generate high-quality oracles and test cases that lead to significant improvements in code generation.
'ChatGPT Code Interpreter is variant of GPT-3.5 with the code interpreter plugin. The version we evaluated, released on March 24th. utilizes the underlying model text-davinci -eaeniii-------0 000-00000eeeee000 It is now offline and replaced with -oote--cooe--oo wtt--ooode-inetetteeeeeee interpreterr.

---

Input
Idea
Code class Solaiiue: repatiarrsssett ranKs: (Lssiiinti
You ore given on integer arrey ronks represencing the ranks of some rechonicss ronks[]]] is the rark of the ith rechonic. techaric with ronk na2 ninates.
Iryy using binory search on the answer.
(Chekk whether for fixed all
while left = right: rid
LADA right wid
Algorithi Synthesis
cars
repaired.
also representing totel, woiting the garage be repaired. the minirux taken to repair all the cars.
inbeger
This be by summing lcan repoir in the given time.
else: left
number cans each rechanic
return left
Functionality Synthesis
iner VisAÇt: list) that returns the Input Implement a elesents increased by
return
in
Input
Code
Figure 3: Examples of algorithm synthesis (top) and functionality synthesis (bottom). The parts in solid boxes given by the problem, while the parts in dotted boxes should be inferred by the model. Functionality synthesis does not require the model to infer the idea, while algorithm synthesis does.
2 Algorithm Synthesis
Large language models excel at generating simple programs. For example, ChatGPT can easily achieve over 70% pass @1 1 accuracy the doestring- co-coeeetttoeeeeeeeeeeeeeeeeeeee dataset HumanEval. However, it still struggles with complex algorithmic problems such as CodeContests. We hypothesize that this is because algorithmic problems need efficient solutions rather than straightforward and brute-force ones. To test our hypothesis, we prompt ChatGPT in two different ways to see if they result in different success rates. One prompt directly describes the problem and asks the model to generate solution that meets the time limits. The other asks the model to ignore the time limit and to solve the problem in the most straightforward way. The prompts we used are listed in Appendix [A.2] We evaluate the correctness of the brute-forces and efficient solutions both manually and using official test cases without time limits so that correct yet inefficient program is also considered success.
Table I: The success rates when ChatGPT is prompted to generate efficient solutions and brute- force solutions and their relative differences. Generating brute-force solutions for LeetCode and CodeContests is much easier than generating efficient solutions.
LeetCode
CodeContests
HumanEval
Brute-force success
88.5%
72.0%
70.1%
Efficient solution success rate
41. 41.2%
7.90%
72.5%
Relative difference
1 114%
822%
-3%
The results in Table validate our hypothesis. For LeetCode and CodeContests, it is much easier to generate brute-forces than efficient solutions. But for HvmanEval, the two success rates are similar. This clearly indicates that problems in HumanEval and those in LeetCode and CodeContests are of two different types. The latter more difficult to solve because requires the application of algorithms. Based on that, we divide code synthesis into two categories: functionality synthesis and algorithm synthesis. Typically, functionality synthesis problems, such as those seen in HumanEval [5] and MBPP (.]. provide detailed description that can be readily translated into implementation. On the other hand, algorithm synthesis problems found in APPS [TT] and CodeContests [17] are more abstract and need efficient algorithms to solve. In this paper, focus on addressing algorithm synthesis rather than functionality synthesis. An algorithmic synthesizer, thus, has an additional task to that of functionality synthesizer-ins it needs to generate the solution idea, implicitly or explicitly, before synthesizing the code. We further clarify the contrast between the two by providing typical examples of each in Figure 3
Typically,functiinnliiy
Formal definition of algorithm synthesis and functionality synthesis. A code generation task can be defined as tuple (Q E e J. where Q is the problem description and P - Bool is the system judge. The system judge J evaluates if a program from the program space P solves the problem represented by Q. The goal of the synthesizer is to produce a program P E P that J (P) True. The system judge J is further composed of two components: Js : P + Bool and
3

---

Reference Oracle Generation Prompt
Reference Oracle Generated by LLM
Ppeess problum
class resorrCarstset,, ronks: Listiintt, corst inti ints
Ipleus tist it epeinst the exand le cases given onyy, de not generate your ovn tast (asees.iien comparing ortputs, please do not consider the
spaces.
nax rrechantce lent (en(rarks)
Fleatt'
rwske(]] ls the rank of the 2th rechanke, aechankc with rank con repair cars 272
representing
def generate a1locat iotoatontttllaettioo rensining.cemg cans):
(Rcrutes.
Lonta lontallocattann llocation) -un neshancc
If suncal ion) = cars:
integer representiog tng
vartingg
alloocation allocation
paragge to repaires,
for in sungetnuueeccmmisssl mintmanntine, mar_tame)
Return the sinimus time takes to repadi all the cars.
janr Exorples
retum rangstreaeining
12g
Hexaaples, oritted)
cairs resaliing generate_al weraateaallttttttaaeee peteratt_llccaaions111 return min_time
sescat location = ailotation a [ns_ccrr]]
corr
Insteed set inting your funrtion ton
class, cheoge your classnase to and brute-force a algoritte to so the alporatin, Do not cons ider any sffacuency issas,
loocation,
forcesolutionn
before,
sotution
solution Ih's What
very.
search that may afrect amoer and how you than trey can enuerrated?
long
think sare
Figure 4: The prompt we used for oracle generation and one oracle generated with it. The instructions are in blue. The correct solution solves the problem with binary search in polynomial time, while the generated oracle takes exponential time enumerate all possible work allocations.
: P -> Bool. Js checks the semantic correctness of the generated code, while Jr ensures that the efficiency of the generated code satisfies the requisite conditions. Intuitively, J(P) = (P)
Algorithmic Synthesis with LLM-Generated Oracles (ALGO)
As discussed in Section 2 generating brute-force solutions to algorithm synthesis tasks is much easier than generating efficient solutions; this huge gap in difficulty can be exploited. To solve algorithm synthesis, we propose Algorithmic Synthesis with LLM-Generated Oracles (ALgO). As shown in Figure I] the ALGO framework utilizes two components a coder and a verifier - to solve algorithmic problems. The coder takes the problem description Q and optionally, the verification results from its last generation and generates a program P that solves Q. The verifier generates a reference oracle whose outputs are used veriffy whether the candidate program generated by the coder is correct. For each problem, ALGO creates the verifier once and uses it to guide arbitrary coders, allowing ALGO to be model-agnostic.
3.1 Verification with Oracle
Oracle Generation The difference between reference oracle Po and actual solution Pa is that Po only needs to be semantically correct (i.e. (s(Po) = True) while Pa needs to be correct and efficient (i.e. J(Pc) (P&) A J1 (P&) True). We utilize this difference generate the oracle. When there is no time limit, most algorithmic problems can be solved with an exhaustive search 8 As depicted in Figure 4, we put the process of an exhaustive search algorithm (which is the same for every problem) in the prompt along with the problem description. I.LMs, which excel at implementing a program when provided with clear instructions, are then able generate reference oracles.
The Verification Process To handle a verification request, we must return verdict of True/ regarding P's correctness, and optionally, the inputs that cause P to fail. We utilize an input generator program to create random test inputs in line with problem constraints. These test inputs are then supplied to both the program under verification P, and the oracle Po. The test outputs of P are compared against those of Po. If they match, a True verdict returned. If they don't 't the failed test cases are returned to the synthesizer along with a False verdict.
3.2 Code Synthesis Strategies
ALGO's 's coder can use different strategies for code synthesis. The code synthesis process can either be one-time or iterative, depending on the used coder. During a one-time synthesis, the coder generates a batch of solutions to the problem, and these solutions are verified and ranked according to their verification results. During an iterative synthesis, the code generates solutions, gets their verification results (and optionally mistaken test cases), and then revises the solutions iteratively.

---

Other than the coder model itself, its strategy to search for and identify the suitable algorithm for the problem also affects the synthesis accuracy significantly. The coder's search strategy can be defined as a conditional distribution π (PIQ) of the program P conditioned on the problem description Q. To generate code is to sample programs from this distribution. To compute this distribution, we can define a space of latent variables I and marginalize over it, as denoted by
x (PIQ) = Σ (PPI)))(TIQ) JEZ
AL.GO is versatile framework that can incorporate variety of search strategies. A strategy may be implicit, with the variable / not specified, or explicit, specifying I, the space of 7, and the methodology to traverse this space. Here, we give three examples: an implicit searcher, an instruction enumerator, and an iterative searcher. However, it is crucial to note that these examples are representative, and there are numerous alternative search strategies in ALGO.
Implicit Searcher: An implicit searcher samples a program directly from the distribution determined by the underlying model, using the problem description. It solely relies on the ability of the code generation model and depends on the oracle to filter the generated programs post hoc.
Instruction Enumerator: An instruction enumerator is an explicit searcher where I is set of pre-defined instructions. Since the performance of instruction-tuned LLMs varies significantly based on the instructions they are given, it is natural to consider enumerating space of instructions to get the best result. An instruction enumerator first picks an instruction from a pre-defined instruction set I, and then synthesizes the program by instructing the language model with I. In our example of an instruction enumerator, we choose to be a set of high-level ideas of algorithms such as "Binary Search' and 'Sorting'. We first sample possible solution algorithms and then instruct the large language models to generate programs with the ideas given.
Iterative Searcher: A iterative searcher is explicit searcher that takes the signal from the verifier to refine its output. The searcher space I can be the token vocabulary of the model. It uses a search algorithm determine the next token during the decoding process by enumerating the vocabulary tokens given the problem description and the partial program in each generation step. Since the search space is exponentially large, it would be time-intensive. Usually, the searcher guided by some rewards from the verifier to prune the candidate space in each step.
Experiments
In this section, we implement ALGO with three code synthesis strategies, and evaluate it with two challenging algorithmic benchmarks to validate its flexibility and effectiveness. Moreover, investigate the verifier's performance by evaluating the quality of the generated reference oracle and test cases.
4.1 Experiment Setup
Verifier We employ ChatGPT Code Interpreter to create the verifier. is first prompted to generate the reference oracle and then the input generator. As mentioned in Section 3.1] this possible because the reference solutions to most algorithmic problems involve exhaustively going through all possible solutions to find a feasible or optimal one. We use temperature of 1.0 and resample the solution until it can pass all example cases. The prompt we used for generating the oracle is shown in Figure 4 For the verifier, we simply use zero-shot prompts to generate the input generator with an input validator since both of them are functionality syntheses and easy to generate. We set the maximum length of each input variable to 10 and skip out cases that raise the timeout exception and the recursion error when generating the output via the reference oracle. The prompts we used are listed in Appendix [A.2 with generation examples. Note that for each problem, we only need to create the verifier once, and it can be used to create arbitrary test cases and guide arbitrary models.
Code Synthesis Strategies We integrate the following baselines the coder with ALGO to evaluate its verification capability and synthesis accuracy:
Codex 5 and CodeT 4 Codex and CodeT are used as coders that utilize implicit searchers. Codex specialized language model, trained on publicly available code from GitHub. CodeT uses Codex generate both programs and test cases for a problem and uses their dual agreement to
5

---

filter and rank the programs generated. To evaluate ALGO, we use the exact same set of programs Codex generated, and rank them in three different ways: in a random manner. based on the dual agreement heuristics from Code'T, and according to the verification results provided by AL.GO. We then compare the top-ranked programs from each of these three rankings. Note that due to OpenAl's policy, the Codex model is no longer available so we directly use the Codex-generated programs provided by the CodeT paper]
ChatGPT Code Interpreter: ChatGPT Code Interpreter is used as a coder that utilizes instruction enumerators. It a variant of GPT-3.5 with the code interpreter plugin. The version we evaluated, released March 24th, utilizes the underlying model poxt-davinci-002 Interpreter is instruction- tunee, it can follow directives to solve a problem using a specific class of algorithms, such Binary Search'. This capability allows it to employ search strategy that iterates through a list of algorithm categories to identify a correct solution. Moreover, with the code interpreter plugin, it is able to run Python code and interpret its results, and automatically refine its output based on the program output. We use the default temperature of 1.0 and resample the code solution until it can pass the example cases in the problem descriptions reach the resample limit (N=5).
As the Code
PG-TD 31 PG-TD is used coder that utilizes iterative searchers. In contrast to CodeTT, which employs test cases post hoc, PG-TD incorporates them during the decoding process. It implements a tree search-based planning algorithm for decoding, utilizing the reward from test cases to estimate the value of the children nodes in the search tree. PG-TD uses GPT-2 [26] and GPT-NEO 2 as the underlying model. We implement two versions: PG-TD* is only based on the public test cases to generate programs, and PG-TD has access to both public test cases and the generated test cases by Li et al. [17]. Both are based on the GPT-2 fine-tuned on the APPS training dataset, which was released by Zhang et al. [31]. We integrate PG-TD into ALGO by substituting the generated test cases with the reward from the verifier.
Benchmarks We utilize the following benchmarks to evaluate ALGO:
We evaluate AL.O with Codex, CodeT and PG-TM on all 165 problems from CodeContests test set, which are collected from Codeforces, competitive programming website. All the three baselines we evaluate have been evaluated on CodeContests in their own paper, follow the exact same setting to ensure fair comparison.
CodeContests 17:
LeetCode: We evaluate ALGO with ChatGPT Code Interpreter on 35 recently released LeetCode problems. To avoid the influence of contamination and faithfully evaluate ALGO's ability in verification and guiding code synthesis, we made sure these problems are released concurrently or after the release of GPT-4. We manually annotate the algorithm categories for the solutions to these problems to evaluate the search strategy of enumerating algorithm categories. The list of problems and their corresponding categories is listed in Appendix A.3
to evaluate the accuracy of code synthesis. To compute n@ for a problem, a code synthesizer needs to generate candidate programs and select the top-n candidates to submit according to some reranking mechanism, which in our case the -.ge-reeee oracles and test samples. n@@ A: the proportion of problems that can be solved by any of the top-n submissions. Since some code synthesizers do not have reranking mechanisms, we define their n@kk as the proportion of problems solved with n submissions randomly sampled from A candidates. To ensure a fair comparison, we use the same sampling budget n under the same setting when evaluating the performance of ALGO and baselines.
Metric Following previous studies 31
we use the n @l metric [6 5
4.2 Synthesis Accuracy
CodeContests We present ALGO'S n @kk k accuracy for CodeContests in Table 2, of the table, Codex is used as an implicit searcher. Compared to Codex itself and CodeT which also heuristically evaluates the program Codex generates, ALGO consistently outperforms them at every value of n. The most significant performance enhancement by our method is observed at 1 @ k. yielding an 8x improvement over Codex, and a 2.6x improvement over CodeTT. As the value of k increases, the performance advantage diminishes. This trend is expected, as the chosen sample number n approaches the total sample count k. causing the pass rate to converge towards the ratio of correct programs within the total program set. The same phenomenon is also observed in the second
In the first part

---

Table Performance on CodeContests. Gain is the performance improvement compared with the baseline (the first line in each part). ALGO significantly outperforms other baselines, especially for 1 @@k. Note that k = 20 for ChatGPT-based settings, while 1000 for other settings.
Method
1@ k
Gain
2@k
Gain
10@k
Gain
100@
Gain
Codex- Based One- Time Synthesis (A: 1000)
Codex 3
0.70
1.20
3,00
7.50
CodeT 4
2.10
+1.40
2.30
+1.10
5.30
+2.30
9.90
+2.40
ALGO w/ Codex
5.60
+4.90
5.60
+4.40
7.70
+4.70
11.10
+3.60
GPsdd-Based Iterative Synthesis (k = 20)
PG-TD* PG-TD 3D
0.62
1.07
2.26
3.45
0.67
+0.05
1.12
+0.05
2.53
+0.27
3.81
+0.36
ALGO PG-TD
1.57
+0.95
2.44
+1.37
3.67
+1.41
4.06
+0.61
ChatGPT-Basee One-Time Synthesis
20)
ChatGPT
4.40
6.62
12.21
ALGO ChatGPT
12.00
+7.60
12.00
5.38
14.00
+1.79
and third part of Table 2] where PG-TD and ChatGPT are used as coders. ALGO is able achieve 2.5x improvement over PG-TD and a 2.8x improvement over ChatGPT at 1@k.
LeetCode We list ALGO'S one-submission pass rate on LeetCode problems in FFiuure 5] The instruction set we enumerate for each problem is a set with several algorithm categories, among which there is one correct category. ALGO's superior performance compared to ChatGPT and GPT-4 demonstrates the benefits of in- struction searcher that enumerates possible algo- rithms. It also demonstrates ALGO's ability to filter and select the correct algorithm category. Without the verifier, would not have been able to tell right from wrong.
ChatGPT
GPT-4
ALGO
rate
Figure 5: Performance on LeetCode. Code inter- preter integrated with ALGO surpass GPT-4's pass rate.
4.3 Verification Analysis
The verifier is critical to ALGO as it guides the creation of an efficient and accurate solution. In this section, we scrutinize the quality of the verifier from several perspectives.
-LM-generated oracles are usually correct. The correctness of LLM generated oracles is crucial to the correctness of ALGO's s test cases. We examine their correctness with both the system judge and human experts. We submitted LLM-generated oracles the online judges (Codeforces and LeetCode) where the problems came from, to get the system verdicts. Oracles with verdicts other than Accepted (AC), Time Limit Exceeded (TLE), and Runtime Error (RE) were directly considered incorrect. For those with TLE and RE verdicts that could potentially be semantically correct despite exceeding the time limit stack size, hired an experienced competitive programming contestant to examine if they were semantically correct and not efficient enough. For LectCode problems, as displayed in Figure 88.5% of the oracles semantically correct, including all those with TLE verdicts. For codecontests problems, 72% the oracles are semantically correct.
Oracle-generated test cases have better quality. We evaluate the quality of ALGO'S test cases generated by answering the following questions: (i) Do verification verdicts from generated cases agree more with the system judge than verdicts from only the public tests? (ii) the generated tests achieve higher statement coverage compared with public tests? In this context, we calculate two metrics: Agreement and Coverage. Agreement
consistency between the decision of the system judge and the test case set. For instance, candidates that fail the system judge should also fail on the generated test set, while those that can pass the judge should also succeed on all test cases. Coverage is the percentage of statements in code solution that executed by test cases. Following
7

---

40
Table 3: The quality of test case. Compared to the ex- ample cases given in the problem description, the test cases generated by ALGO's 's verifier detect more failures in the programs, agree better with the system judge J, and covers more lines in the generated code.
10
6
Dataset
Case
Agreement
Coverage
Example 57.39%
85.78%
4
CodeContests
10k
2@k
10gk
100@k
ALGO
94.78%
89.39%
Figure 6: The performance of different sizes of test cases on CodeContests.
Example ALGO
68.57%
90.32%
LectCode
74.29%
93.00%
Chen al. we use public coverage library to gather the coverage results. As demonstrated in Table 3] our generated test cases substantially improve the agreement with the standard judge (437.39% on CodeContests and +5.72% on LeetCode), indicating they can enhance the verification of candidates prior to submission. In addition, test cases of AL.G achieve higher coverage of the statements, implying that these cases can more effectively validate the functionality of the solution.
Better test cases lead to better results. The test cases generated by ALGO have better agree- ment and coverage. We check if they lead to better synthesis by comparing them to the other two sets of test cases - examples provided in the problem statement and test cases directly gener- ated by ChatGPT. We used the same coder with the exact same sample budget & = 20. As re- ported in (Tall 4] under the same setting, ALGO tests led to much better performance.
Table 4: Given the same coder, ALGO test cases lead to much better n @ k performance, indicating that better test cases do help in code synthesis.
1@20
3@20
7@21 20
Example Tests
4.4%
7.9%
12.2%
ChatGPT Tests
6.8%
8.2%
11.7%
ALGO Tests
12.0%
12.0%
14.0%
More test cases lead to better results. We examine the impact of the size of test cases the verifier generates on CodeContests for ALGO w/ Codex. Our verifier has the flexibility to create arbitrary number of cases and use test case sets of varying sizes to rank and guide the synthesis. As shown in Figure [6] when the size is fewer than 30, the increase in the size of test cases can significantly bolster performance for all n@k, indicating the effectiveness of our verifier in covering more corner cases with additional test cases. Notably, having sufficient number of test. cases is more critical for 1 @@k, which relies on test cases to select the optimal solution for one-time submission. However, this improvement diminishes when n is larger. This is because robust verifier is not strongly required when the chosen sample number n is large, as discussed in Section 4.2 Furthermore, there is very little additional performance gain with more than 30 test cases. We hypothesize that this is due the quality of our oracle and the generation range we have set for the verifier.
4.4 Case Study
We demonstrate the workflow of ALGO with a problem from our LeetCode benchmark This problem asks for the optimal allocation of cars to mechanics with varying efficiency mini- mize the total repair time, when the mechanics would work simultaneously. As depicted in Fig ure 7, the code generated using reference oracle prompt exhaustively enumerates all potential assignments of cars and selects the optimal one according to the problem description. Assuming len(ranks), m cars, this program exhibits exponential time complexity To m) = O(2"). making it an inefficient solution that is unable to pass the online judge. Nevertheless, despite this program's 's inefficient nature, this implementation remains valuable in terms of semantic correctness (i.e., (Po) = False and Js(Po) = True, where we can conveniently define (P) = "time complexity of P is at most (((n + m) log (n + m)) " without loss). This exam- ple demonstrates how ALGO can generate reference oracles for code synthesis.
8

---

Potential Greedy Solution System Judge:
Solut repairCars(self, ranks: Listlintl, inth: sarks)
Wrong Answer
Test Inputs Generated by ALGO
nax repair _ime titee
Test Input 4; banks=[4,,,3,,),ccar
assigned, cars =
testranks! cars 1] // (lenCranks) assigned_
rank ranks:
100
4
1
4
nue, cars = mintnux cars, cars cars) repair_ time rank sue cars nue cars rax_repair_tia repair time)
maxtrax_rgpair.ttte,
Reference Oracle Generated by LLM
class Bruteforcesolution
def repaircarstselt, ranks: List[int), cars: int)
assigred, cars nus. cars return repair_tiis
nui cars = mininur_cars, cars, cars carsp repair
X
antz
nun, sechantes lentraniss
rank sus cars nue cars ropair mas(ros_rqpai__tae
repair appir_ttiee
non local, nin, nin_tine tine
remsining_carsts
assigned cars to nur_cars return nax_repair_
if Len [a] aalllocation ion] - nux nus_rechanics:
1f suniall locaationn = cars:
16
times [ranks(1] allocation(1)
allocation(2]
rangeInan rechanicss]
Potential Binary Search Solution
min, min_tine minlmin_tiin time, ssx_tive)
nax_tine (anes)
class Solut
def repairsarstself, ranks: List (intl, cars: int)
sue_cars ranget remadninn_carr
return
reasining cars rewiining cars wtw.atlcttttoosseelllelaaa
allocatiion Inux_care
mar_cars
int:
for rank in ranks:
L
countCarttpairrdrratts ninutes):
generate allccations( cars)
res_rerainnngg.cn
total_cars return total_cars
n inti rank] *- 0.5)
return mir_time
left right naxtranks) cars cars
while left e right:
16
nid (left rightt //
if counttarsRepairddlrnnn nid) cars:
left
elses
System Judge: Accepted
right : mid
return left
Figure 7: ALGO is capable of verifying two candidate programs, in different algorithm categories: greedy and binary search. Using an input-output example provided by the reference oracle, ALGO able to deliver the verification result consistent with the system judgment.
we present how the reference oracle can verify the correctness of candidate programs generated by the coder LLM. We present two candidate programs generated with different algorithm categories: greedy and binary search. Specifically, the binary search candidate PB is generated with instructions on binary search and the greedy candidate Pg is generated without explicit guidance. The binary search algorithm is ideally suited for this problem, given that the indicator function, denoted as (t), which determines whether all cars can be repaired within i minutes, is monotonous. This makes it possible to apply binary search on the time i. and turn the optimization problem into a judgement problem. The binary search candidate represents an implementation of such algorithmic approach, which is an efficient and correct solution of time complexity T (n, m) = On log m)) and can pass the system judge (i.e., J(PB) = True). On the other hand, greedy algorithm is not suitable for this problem. Thus, even though the greedy candidate presented is of time complexity Ta(n, m) O(r), the semantic of this candidate is wrong (i.e., JT((P) = True and (P(Pa) = False). This example demonstrates that providing the correct instruction can lead to better code synthesis result.
In Figure 7.
In Figure 7 Pa failed with our verifier since Pa(1o) + Po(lo). Similarly. (1) = Po (In) indicates Pr (Tn) passed our verifier. This verification result is consistent with the system judge and demonstrates that ALGO--eneratee oracles can help to verify the programs generated. Furthermore, the verification results can help in finding the correct instruction (algorithm category).
5 Related Work
Reranking Techniques for LLM Code Generation. LLMs often need sample many candidates before finding a single correct solution. Therefore, reranking techniques for telling the correct programs among many candidates are crucial for better LLM coders. One line of work in reranking involves neural models that predict some form of confidence score for program candidates. This score can be the likelihood of the program ( the mutual information between the code and the problem description (32] or outputs from verifier models that are purposely trained to predict the correctness
of programs [22 [3]. However, their scores are just scalars and not interpretable. Both the oracles
and test results from ALGO are much easier to check and interpret.
Another line of work utilizes test cases and the programs' execution results to rerank them, which much more similar to ALGO'S approach. Shi et al. [27] and Li et al. [17] cluster different candidates

---

according to their execution results on example cases, creating a mechanism similar to majority voting. Chen al. [4] and Key et al. [T]] also cross-check programs and execution results, but they create more test cases with the coder models to make the tests stronger. However, L.L. ---eenertteed test cases for a single problem can contain both correct and incorrect ones, providing harmful feedback to the coder. ALGO has converted the task of checking Al-generated programs to checking Al-generated brute-forces, which is much easier.
Oracles in Program Synthesis and Software Testing. In the traditional program synthesis domain, automatic verification of a synthesized program is possible (29 28 because formal specifications,
including input-output examples [25] logical constraints (00). are explicitly provided. In contrast,
oracle generation using LLMs is challenging due to the ambiguous nature of text and lack of formal specifications, making difficult do verification. Efforts have been made to create formal specifications from text 6 15 IO], but reliability remains an issue. Meanwhile, in the software testing domain, test oracle generation existing work mainly focuses on generating regression tests, which are not intended for new bug detection. Moreover, many methods rely heavily on formatted documents or are designed for program crashes or basic functional properties, making them unsuitable for complex algorithmic problems.
18 24 a well-known and challenging task. However,
Self-Refining Language Models. Large language models (LLMs) have exhibited a remarkable capability for self-analysis and self-improvemmnt,, highlighted by numerous studies [9] 12 30)
Such reflection is also used to improve the quality of the generated programs. For instance, Chen
al. trains Large Language Models (LLMs) generate explanations for code and utilizes both
the explanation and the execution results as feedback to improve coding solutions. Self-Refine [19 prompts the LLM to provide feedback on the efficiency of its own code solutions and refine these solutions based on the feedback given. In this paper, we use the execution results of the reference oracle feedback and employ them guide the generation of programs.
Conclusion and Discussion
We proposed ALGO, an algorithm synthesis framework that leverages LLM-generated oracles as verifiers to synthesize algorithmic programs. ALGO consists of a coder and a verifier. The coder generates code solutions the problem and requests verification from the verifier to iteratively refine its idea and its code. The verifier employs LLM-generated oracles to generate test cases for verification. ALGO can employ different types of search strategies with different underlying code generation models. We introduced a method to synthesize the reference oracle with LLMs based on the ease to generate brute-force solutions for algorithmic problems.
We extensively evaluated ALGO'S performance two different datasets with three baselines. ALGO outperformed various baselines with different search strategies by a large margin. We also did detailed analysis of the reference oracles generated on their semantic correctness, and their verdict agreement with the system judge. The oracles in ALGO have a high accuracy and make highly consistent verification results with the system judge. The high quality of the oracles supports the performance of ALGO.
While ALGO is evaluated with several searchers we proposed in the paper, there can be more possibilities for applying different searchers in the ALGO framework. For example, the relferefinement studies large language models may be utilized for more complex interactions between the coder and the verifier. On the other hand, oracle-guided synthesis [14] is well-studied topic in the programming language community with techniques that can be applied in different branches of code synthesis. We believe that knowledge from both the natural language processing community and the software engincering community can inspire more future work in the framework of ALGO.
Acknowledgement
This work is partially supported by unrestricted gifts from IGSB and Meta via the Institute for Energy Efficiency.
10

---

References
[1] Jacob Austin, Augustus Odena, Maxwell Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie Cai, Michael Terry, Quoc Le, et al. Program synthesis with large language models. arXiv preprint vrXiv:2108.0770 2021.
[2] Sid Black, Leo Gao, Phil Wang, Connor Leahy, and Stella Biderman. GPT-Neo: Large Scale Autoregressive Language Modeling with Mesh-Tensorfloss March 2021. URL //doi.org 10. 0001/22e0112o 5297715 metadata.
If you use this software, please cite it using these
[3] Sébastien Bubeck, Varun Chandrasekaran, Ronen Eldan, Johannes Gehrke, Eric Horvitz, Ece Kamar, Peter Lee, Yin Tat Lee, Yuanzhi Li, Scott Lundberg, et al. Sparks of artificial general intelligence:
Early experiments with gpt-4. arXiv preprint urXiv:2303. 12712, 2023.
[4] Bei Chen, Fengji Zhang, Anh Nguyen, Daoguang Zan, Zeqi Lin, Jian-Guang Lou, and Weizhu Chen. Codet: Code generation with generated tests. The Eleventh International Con- ference Learning Representations, 2023. URL
net/ fertfformmidd
ktrw68Cmu9c
[5] 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. Evaluating large language models trained code. arXiv preprint arXiv:2107.03377 2021.
[6] Qiaochu Chen, Shankara Pailoor, Celeste Barnaby, Abby Criswell, Chenglong Wang, Greg Durrett, and Işil Dillig. Type-directed synthesis of visualizations from natural language queries. Proceedings of the ACM on Programming Languages, 6(00PSLA2):52-555, 2022.
[7] Xinyun Chen, Maxwell Lin, Nathanael Schärli, and Denny Zhou. Teaching large language models to self-debug. arXiv preprint vrXiv:230.005128 2023.
[8] Thomas H Cormen, Charles Leiserson, Ronald Rivest, and Clifford Stein. Introduction to algorithmms. MIT press, 2022.
[9] Elizabeth Dinella, Gabriel Ryan, Todd Mytkowicz, and Shuvendu K Lahiri. Toga: neural method for test oracle generation. In Proceedings of the 44th International Conference on Software Engineering, pp. 2130-2141, 2022.
[10] Alex Gu, Tamara Mitrovska, Daniela Velez, Jacob Andreas, and Armando Solar-Lezama. Obsynth: An interactive synthesis system for generating object models from natural language specifications. arXiv preprint arXiv:2210.114000 2022.
[11] Dan Hendrycks, Steven Basart, Sauray Kadavath, Mantas Mazeika, Akul Arora, Ethan Guo, Collin Burns, Samir Puranik, Horace He, Dawn Song, and Jacob Steinhardt. Measuring coding challenge competence with apps. NeurIPS, 2021.
[12] Jiaxin Huang, Shixiang Shane Gu, Le Hou, Yuexin Wu, Xuezhi Wang, Hongkun Yu, and Jiawei Han. Large language models can self-improve. arXiv preprint 1rXiv:2210.116100 2022.
[13] Jeevana Priya Inala, Chenglong Wang. Mei Yang, Andres Codas, Mark Encarnación, Shuvendu Lahiri, Madanial Musuvathi, and Jianfeng Gao. Fault-aware neural code rankers. Advances in Neural Information Processing Systems, 35:13419-1344 13432. 2022.
[14] Susmit Jha and Sanjit A Seshia, A theory of formal synthesis via inductive learning. Acta Informatica, 54:693-726. 2017.
[15] Darren Key, Wen-Ding Li, and Kevin Ellis. I speak, you verify: Toward trustworthy neural program synthesis. arXiv preprint arXiv:2210.00445 2022.
[16] Sumith Kulal, Panupong Pasupat, Kartik Chandra, Mina Lee, Oded Padon, Alex Aiken, and Percy S Liang. Spoc: Search-based pseudocode to code. Advances Neural Information Processing Systems, 32, 2019.

---

[17] 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- code generation with alphacode. Science, 37866624):1092-1097 2022.
[18] Shaoying Liu and Shin Nakajima. Automatic test case and test oracle generation based on functional scenarios in formal specifications for conformance testing. IEEE Transactions on Software Engineering, 48(2):691-712, 2020.
[19] 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. arXiv preprint S.Ki::2303.165511 2023.
[20] Zohar Manna and Richard Waldinger. deductive approach to program synthesis. ACM Transactions on Programming Languages and Systems (TOPLAS), 2(1):90-121, 1980.
[21] Hussein Mozannar, Gagan Bansal, Adam Fourney, and Eric Horvitz. Reading between the lines: Modeling user behavior and costs in ai assisted programming. arXiv preprint wrXiv2220.143000 2022.
[22] Ansong Ni, Srini Iyer, Dragomir Radev, Veselin Stoyanov, Wen-tau Yih, Sida Wang, and Xi Victoria Lin. Lever: Learning to verify language-to-code generation with execution. In International Conference on Machine Learning, pp. 26106-26128, PMLR, 2023.
[23] Erik Nijkamp, Bo Pang. Hiroaki Hayashi, Lifu Tu, Huan Wang, Yingbo Zhou, Silvio Savarese, and Caiming Xiong. Codegen: An open large language model for code with multi-turn program synthesis. In The Eleventh International Conference on Learning Representations, 2023. URL
https://openreviiet http:://pppaareeeeeeeee/e/rr/aaa hett://forrmmiidiaa......Y...B
[24] Lin Padgham, Zhiyong Zhang. John Thangarajah, and Tim Miller. Model-based test oracle gen- eration for automated unit testing of agent systems. IEEE Transactions Software Engineering, 39(9):1230-1244 2013.
[25] Oleksandr Polozov and Sumit Gulwani. Flashmeta: A framework for inductive program synthesis. In Proceedings of the 2015 ACM SIGPLAN International Conference on Object- Oriented Programming, Systems, Languages, and Applications, pp. 107-126, 2015.
[26] Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, llya Sutskever, al. Language models are unsupervised multitask learners. OpenAl blog, 1(8)9, 2019.
[27] Freda Shi, Daniel Fried, Marjan Ghazvininejad, Luke Zettlemoyer, and Sida Wang. Natural language to code translation with execution. In Proceedings of the 2022 Conference on Empirical Methods Natural Language Processing, pp. 3533-3546, 2022.
(28) Saurabh Srivastava, Sumit Gulwani, and Jeffrey S. Foster. From program verification to program synthesis. In Proceedings of the 37th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL '00 pp. 313-326, New York, NY, USA, 2010. Association for Computing Machinery. ISBN 978 1605584799,
doi: 10.
URL
nttps://doi.org: wttp://rrr/11111111111111511 11w.111111177999.111 7TT.77066999...6337777
[29] Saurabh Srivastava, Sumit Gulwani, and Jeffrey Foster. Cemplate-based program verification and program synthesis. International Journal on Software Tools for Technology Transfer, 15, 04 2013. doi: 000000//10000002--0200
[30] Danqing Wang and Lei Li. Learn from mistakes through cooperative interaction with study as- sistant. The 2023 Conference on Empirical Methods Natural Language Processing (EMNLP) 2022, 2023.
[31] Shun Zhang, Zhenfang Chen, Yikang Shen, Mingyu Ding, Joshua B. Tenenbaum, and Chuang Gan. Planning with large language models for code generation. In The Eleventh International Conference on Learning Representations, 2023.
Yd=Lr
[32] Tianyi Zhang, Tao Yu, Tatsunori Hashimoto, Mike Lewis, Wen-tau Yih, Daniel Fried, and Sida Wang- Coder reviewer reranking for code generation. In International Conference on Machine Learning, pp. 41832-41846 PMLR, 2023.
12

---

A Appendix
A.1 Examples of Algorithm Synthesis and Functionality Synthesis
We give examples of algorithm synthesis and functionality synthesis in Figure 8)
The upper part is instance of algorithm symthesis, where imput that describes the problem does not indicate the solution idea "binary search' in any way. To solve the algorithm synthesis program, the model needs to come up with the idea related to 'binary search' first either implicitly or explicitly before synthesizing the code.
The lower part an instance of functionality synthesis, where the input basically pseudo-code program described in natural language that can directly translate into Python code. The model does not need come up with the idea because the solution is already clearly stated in the input.
Input
Idea
Code
You are given on integer arrey ronks representing the ranks of some rechonics. rones[]] is the rank of the rechonic. techaric with rank ninutes.
class Solai Lans
Irry using binory search on the answer.
regai iarsssselt
Listisnti,
(heck whether for fixed all cars
white left right: rid
zight) right wid
Algorithm Synthesis
repaired.
representing
TThi maxisun number cans each nechanic
by summing
etsel
woiting the garage be repaired.
lann repoir in the given time.
return left
the minirus taken to repair all the cars.
Functionality
Ixplement a elesents increased by
iner ListÇt: list) returns the Input
return
Synthesis
Input
Code
Figure 8: Examples of algorithm synthesis (top) and functionality synthesis (bottom). The parts in solid boxes are given by the problem, while the parts in dotted boxes should be inferred by the model. Functionality synthesis does not require the model to infer the idea, while algorithm synthesis does.
A.2 Prompts in ALGO and Examples of Generated Programs
A.2.1 LeetCode Examples
We list the prompts we used to generate the solution candidates and the verifier components for LeetCode problems here.
Figure 9 lists the prompts and examples for generating the naive solution. FFiuure 10 lists the prompts
and examples for generating solutions guided by instructions that specify the algorithm category.
Figuree lists the prompts and examples for generating reference oracle. /Fiuure 12] lists input
validator example and its prompt. Figure 13 lists the prompt for the input generator that generates a single test input. Figure 14 lists the prompt for the batch input generator.
Candidiate Generation Prompt Soooee following problem with python and it ageinst eomple cases only.
Naive Candidate Generated by LLM
lclass Solution:
sef resairCarsfaeli runks: Listiint), cars: int) -s int:
Yoou gäven integer arrey ranks regresenting
rechanic. mechanic ranks of nechanics.
ranksfll
nax_rpparr_.
cars in n22 ninutes. Nechanics work in parallel.
asssgned cara
Yoo are also given an integer cars represent ing the total rumbr cars waiting in
for
repatred.
nan, perccara (cars Lenfranks) essigrentcrrs 131 (lentranss) ass:gned (ar5)
Returr the mintmur tine taken (Examstes: loritted)
the
nun_car's mintnus,comm cars, car's
Sosigned_cors)
Constraints: (omitced)
repair time rank nun_care nunucars
repoir aesigred cars rue. cars eec.reperr_ti
ssfurction detinitionns
RETLOATE min(nun_cere CATA, care exxignel rars) PALEGOAAL_AAEE - Rextigeed aaxieOLLeeaa Www.Leeaarr_tee 1ine, timc) return tiL.
class Solution:
del repeircarsiself, rankss List]int], carks int)
Figure 9: The naive prompt without instruction guidance and a candidate program generated with it. The instructions are blue. It a greedy method in linear time but is not suitable for this task. Even the naive candidate generated can pass the examples in the description, it fails both the system judge and ALGO verifier.
13

---

for Instruction Guided Generation Prompt
Binary Search Candidate Generated
Bisery fffter geterating the case, plaase test agaiest the eoople cases given in the detintt on. only use the eumple casss, don ase your cun text cases.
yclass Solution:
repairGarsfantl, rankar Lixt (int), carn: int ants wesaaggiidddlrees
ith rechanic, rechanic ranks of some Icars in n22 ninutes, Nechanies work in parallgl.
You gäeen integer array ranks rearesenting
total cars
Tranksf2l
incitninates / rark) en 6.51
L
are also given an integer cars represent ing the total numbr cars saiting
repaired.
Left -
reture toral_cers
Beturrn the minieur Fime taken
all the
Exauples: loritted)
white lett right:
Iconstraints: (omitsed)
#i2
renfunction
cont Carstaa pndpaandddrrarss mid) carss
left aid +1
cclass Solution:
right eld
def repai repat ff ranks: List [tnt], carso int) -> ints
return left
As 1 soid acfore, please rake sure use the bitory scarch nethod..
The prompt with instructions about the specific algorithm category (binary search). Binary search is the ideal algorithm used by human programmers for this task, with which the coder can generate both correct and efficient solutions. In general, right algorithm category can efficiently improve the quality of generated program.
Figure 10:
Reference Oracle Generation Prompt
Reference Oracle Generated by LLM
pplease
solve this probice with brute-force alporattn, After geserating cace, exceple casesuttion corparing estputs, please do not consider the Line breaks and spaces.
class Brateforcess luttoorrrestttior
num rechantes = len(ranks)
(int)
sinitins fleat'
is are given an integer array ranks representing ing the raries same mecherics. (1 wechandc
WiToaaionstatlaarntt reestning cars):
noilocal mis, tine
jarrutes.
sT (oliaaatiioonn = cars:
You are atso given an integer cars resresenting the totst, number of cars vasting in the parage
timss Trancafi) allocationnal allocationna)
eak nox moxitimes!
Return sinieus time repadr all the
mac_tim))
Jane Exaeplex
retuin for nex, cars range peglrrmmtnorru.cm allocation Inan_cers]
(es, oritted)
rox, rox_/enoirinng.ce carg resaliing cars fuu_cors generateuul wwwpeuttlttaattsttttttoo
Insteed of sefining your function in the Solution class, change your classnane to Bruse teressluttinn
location,
atgoritte shrrtte
said before, plause make sure you the nust atraight Forward The
Tnev. resaining, carst
generate
wtw.rrttt_llaaaiosssiii cors)
laake the solution as brute-farce, possible. It's okay for you cnuserste over a very!
variabbee that nay affect the anover and how to think they canl be etumerated?
Figure 11: The prompt we used for oracle generation and one oracle generated with it. The instructions in blue. The language model is instructed to generate the most straightforward solution by enumerating over a very large search space of all combinations of relevant variables. The generated oracle enumerates all the possible ordered partitions of work allocations to find out the optimal one.
Input Validator Generation Prompt
Input Validator Generated by LLM
You are gäven this lectcode pros len, Please help re by gentrating validator function boolean value ind:cating whether the tsput is valls ard follows the constralats in the problce suscraption. Please your date valinator by checking the holidity
der s__valid_irputtranigg Ligttintt, carst 1nt2 boot: 32
probten descriptior.
return not <- rank er 1831 returs
You are given an Integer array ronks represonting the ranks of sems aecharics, ronist]l jis me rank of the wethasie aethartc with rank can repair cars r m²2
paroilet.
if not cars 18 on
You are also given an integer cars ingresenting the total nuter of cars veiting in the
return Falne
ficturn the siniauy time takes to repair all the cars.
Ircemiies (ter)
ierfucction sofandtiores (onitted)
Figure 12:
The prompt is utilized to generate a input validator to verify the validity of the generated test input. ensuring it aligns with the constraints specified in the description. In practice, this validation task a funetionality synthesis task, which can be easily solved by LLM.
A.2.2 Codecontests Examples
We list the prompts we used to generate the solution candidates and the verifier components for Codecontests problems here. Figure 15 lists the prompts and examples for generating the reference oracle using an exhaustive search. Figure lists the prompt for generating the batch input generator.
14

---

Input Generator Generation Prompt
Input Generator Generated by LLM
Please hete as generating insut porerator functior gon Input" that candanly
se.relid__tppu hes_trpptirrrnn frances Lint, care: ant) boot:
The constra defired. your gen traus furct gererates text inpus which Insut" validating the gesernted rake |uucctonn should only generate lest insuts and not tes: sutpuis.
return False
You are given in Integer arry reets representing the rarés of seme aecharics, ranksi]] pacrutes. Nechanics vera in para: let.
neture Palse if
xe rank 1981
given an integer cars resnesenting total numter cars vacting larrage to repaired,
return False
Return the ainiers time takes to repadir all the cars.
grn, trear() -o tiples
constracnts: tomittedt
enFucction sofaniciones (onitted)
randoe.rordinttt 10 51
cangein2)
ddet t__.aatss.rrputinee (int), zars: int) beot: lonitted]
cars rensee. randirt(1, ee
Ls_ya irpats ramss coral:
Figure 13: The prompt is used to generate a data generator, to generate extra test cases when combined with the reference oracle. In practice, this generator generation task is functionality synthesis task, which can be easily solved by L.M.
Batch Generator Generation Prompt
Batch Generator Generated by LLM
You
nela
ph by generating randse inguta with the randos arges pentrator "gin_inact" You should tuples. You not
randon, testfeax ranks, length: ietal0 5,
testi?" Tupper Listt of the irpat retures test outputs, only generate trputs.
orguennts
LntwloM, marcturs:
Listituplels
soputt tuples white Truel
You are given integer the wcthaii. withente with lncrutes. Mechanies vork ill parailet.
ronks representing ranks eecharics, ronksfll
Parks - Irandos. (1, ainiree_rnnk_rele 1821 rangetni)
integer
recnesenting
vaiting
Igrrage to be repatned,
rendes. randint
sintowe,cars, 10 6))
ficturn (centted)
time takes to repair all the cars.
if 12 19ldd Japutt ranks, cars);
corsttraunts: romittedl
rantre Inpurs II
det gen. (eputt) -> tiple: (onttted)
randoa traaft..opendigee (nput()
refum rardes isputs
Figure 14: The prompt is used to generate a batch generator that employs the already generated sen_input to generate several input cases by calling it multiple times.
Since the test set problems in Codecontests are all from htttt::///odeforreee com/ they originally require standard input/output. However, we follow the setting in Codecontests by concatenating the entire standard input as a single string and asking the model to generate reference oracles that map a string to string.
Reference Oracle Generated by LLM
Reference Oracle Generation Prompt
Ide are dest ending coeparstorla, h):
leen text IT apainst the essecle cases given inlly de not generate your me test lisses.tionn can ing outputs, please do sot cossider the breats and spaces.
an runsef lental) if afal blal:
assigneent landi and Budi vere given the title string mimbered free (asch
tidy
books.
represented
etsT all] > bEll:
ench with length e. Andi really wents to sort the book testcographicall lascending,
raturn etif retumi
Budt wents sort Instegraniccalll descending. pewset/probtee
|htttps// //code///eeee /ttp///oooooooooooooooooooooeeee
renaining castced)
Lene Exoeples
return
(exaap oritted)
retura
ins fendoes str)
Hines stdin.strapll litch""
ppreese reed eveepte ieputs to the function ut eat shrting As said
petare,, please sure you the rost straiight forwart and brate-force digorttm the
books (ctitle, 10si for 1ide tittel
sigoritte. fooree as biee shat de you think are some var tables than ney affect the ansver wid
enunerate Lines starte
jeeyrrap key visla ass dsss_ onsing comparatorixiih
hovr you thank they can be anseeratee?
retum .jaintourpint
Figure 15: The prompt we used for oracle generation and one oracle generated with it. The instructions are in blue. The language model is instructed to generate the most straightforward solution by enumerating over very large search space of all combinations of relevant variables.
A.3 The List of Problems from LeetCode
We list the problems we collected from LeetCode as benchmarks to test ALGO in Table 5 among them are 10 easy problems, 18 medium problems, and 7 hard problems.
15

---

Batch Generator Generated by LLM
Batch Generator Generation Prompt
siven given assigreent tidy
gen, trpurin a_eaxt -o stri
n randon, randantan minle_aax, +
(asch represented
title striing mimbered
esch with lenghh a. Andi really wents to sort the book lestcographical lascending,
whule ientbokkttttles)
wonts cort texiographhial descending. pewsse//oooblee//tttt
caitced)
for
You should create
teput" teput" should take
tiftes.ardibont (wr.ppantbnkkttttee))
last of angunnnss to control the user lert of the irput and retur a single string
sorara (1(6) (a)sn'
srpv: problee constrolnts, gen, Ingut" should only generate test Inpots not test outputs.
represents
irouts
retern snput_atrang
"basch_aaee ger that bsall Listt
You stould then create on extra turction "aates gen, trgues" that takes one argament run gengangs: "otchh tires whouls
pde baict_gen http_unnutaatttttssssooo
Snouts in ranpettatch_s1ze1)
List:
strings represent tsputs.
of
irputs. prats.apparddin irppprll......ppel..... 1317
Figure 16:
The prompt is used to first generate function gen_ and then generate batch generator that employs the already generated gen_input to generate several input cases by calling multiple times.
Table 5: The Leetcode problems we use. We only pick problems that were released concurrently or after GPT-4 avoid contamination.
Problem ID
Problem Name
Level
2582
pass-the-pillow
casy
2583
kth htt-llagest-suum-i----bie
medium
2584
hard
2585
hard
2586
easy
2587
medium
2588
ofthhe--mmmroo--bbeeeeeeee beautiful-suubarayy
medium
2589
minimum teeeinn--imtt-----e toe-ttoooomepeeaallll -aassss-all-tasss
hard
2591
distribute- monou to maaximum-childeee
casy
2592
pexximize-rraatnesss---aae
medium
2593
fnd-score-of-an-eee
medium
2594
minimum-timm--o-rrppaee
medium
2595
easy
2596
check- Brrck-knight-oowd cour-configuration
medium
2597
the the-number-of aef--eettful--a-- subsess
medium
2598
smallest-missine non-
mnggativ-inteeer--ftteroooo
medium
2600
k- www-wwtttthhhiiimmmmeeee-
easy
2601
prime- weree-uubraacttn--eeeeeeeee -opertttiooo
medium
2602
medium
2603
collect-coins-in-1 in--ttree
hard
2609
easy
2610
convert- an-array-ine into-at 110-a-22 a-2d-aanna- ad-array-winn with-ywthhaeee withhconnitions
medium
2611
mice-and and-and-eee ind-cheese
medium
2612
minimum minimum-reverse geverss-operations
hard
2614
prime-in-diagonal
easy
2615
sum-of-distances
medium
2616
minimize-the-maximmme thee-mmaiimn-ddfffeee--------
medium
2617
minimum-
minimum-numberr-ff number-of ois-viiieddd-ellee cells-in-a--rri
hard
2639
find-th-wwidth-of
-f---gri
easy
2640
mad-the-score-ff-ee
-oloreoo--lll-prffieee---------e prefixes-of-an-aree
medium
2641
cousins-in -iiinn-----iintteeeeeee
medium
2643
row-with-maximum
casy
2644
find-the- maximum
2645
medium
2646
ceiimize-hh--otaa-ppicc-o-fff
hard
16


Reviews:
[{"review_id": "EPz1Abr7ZZ", "reviewer": "Reviewer_MLQT", "summary": "The paper tries to improve code generation ability. The main idea of the paper is as follows\n\n1. Use an LLM to generate a brute force solution to contest coding problems -- the idea being that the hard part for such problems is not solving them but solving them given the time and memory constraints.\n\n2. Have an test case input generator for the problem and get the corresponding output for the test case using the brute force solution in (1)\n\n3. Verify whether a solution is correct using the input/output pairs generated in (1) and return the failing test cases to the code synthesizer\n\nThey test their algorithm using CodeContests and LeetCode and using multiple code synthesizers showing significant performance improvements.", "questions": "In addition to questions in the Weaknesses section above, I also have the following questions -\n\n1. I can't find the value used for n (sampling budget) in the paper or the number of inputs generated using the oracle. That should be mentioned in the experimental section.\n\n2. How good are the oracle solutions for CodeContests?", "limitations": "N/A", "rating": 5, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "A simple but nice idea leveraging the insight that the hard part for contest coding is solving the problem in the time and space constraints. They do a good set of experiments demonstrating the performance improvements. They also have additional analysis on the quality of their brute force solutions (valid 88% of the time for LeetCode)", "weaknesses": "The main worry I have with this paper is the following :-\n\n*Baselines* \n\nThey use ChatGPT to generate the oracle verifier and show that using it can improve the performance of *weaker* models like Codex and GPT-Neo. However for CodeContests (their primary benchmark), they do not give the baseline of how good ChatGPT itself is at solving the problem. \n\nThis is an issue as it is expected that having a correct verifier is going to enable the selection of the best program out of a list of generated programs. In practice however, we will not have the luxury of having the correct verifier. We will have an LLM and the question before us would be whether generating a verifier using a strong LLM and using it to guide weaker LLMs (or the same strong LLM) is actually better than directly trying to use the strong LLM to generate a solution. Thus that baseline is critical but absent.\n\nFor LeetCode dataset, there is a ChatGPT baseline. However key experimental details are missing. In particular\n\na. What code synthesizer was used for ALGO?\nb. If it was ChatGPT with CodeInterpreter, was the ChatGPT baseline and GPT-4 matched in terms of sampling budget? (If selection of the the best answer out of multiple answers is an issue, then a strategy like CodeT can be used) What was the sampling budget?\n\n\nIn addition, there's a simple baseline that could be tried that is not present -- what if you asked ChatGPT to generate the test input/outputs directly instead of generating a brute force solution?\n\n\n*Temperature of generation*\n\nThere seems to be a temperature mismatch between CodeT and Algo w/ Codex. The results available online for the former from which the authors say they took their results are with temperature 0.8 whereas the authors results for Algo are with temperature 1. This could be putting the former method at a disadvantage as it has lower diversity in the generations.  In addition the temperature used for the other models is not mentioned. If the model does not have a filtering mechanism, then a low or 0 temperature should be used as otherwise the method is going to be at a disadvantage\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the thoughtful comments.\n\n## 1 ChatGPT baselines on CodeContests\nWe ran three experiments with ChatGPT as the coder on CodeContests: ChatGPT + sample tests, ChatGPT + ChatGPT-generated tests, ChatGPT + ALGO tests. The experiments were conducted on a 50-problem subset of CodeContests. The sample budget for each problem was 20 and we ranked the generated programs with different sets of tests. For each problem we picked the top-ranked program as its solution. We report the pass rates of the top-k-ranked programs (20@k) below.\n|  | 20@1 | 20@3 | 20@7 | \n|-|-|-|-|\n| ChatGPT + sample tests    | 4.4%    | 7.9%|12.2%|\n| ChatGPT + ChatGPT-generated tests | 6.8% | 8.2% | 11.7%|\n| ChatGPT + ALGO-generated tests |12.0%|12.0%|14.0%|\n\n**The results indicate that ALGO is able to significantly improve upon ChatGPT, and ALGO's test cases are better at discriminating correct solutions from incorrect ones.**\n## 2 Clarification for sample budget, temperature, and number of tests\n\n**Sample budget.** In the original experiments on LeetCode, ChatGPT and GPT-4 was given a sample budget of 5. Since ALGO was using instruction enumerator, each instruction was given a sample budget of 1 and the \"verifier\" was used to pick the best program among those generated from different instructions. We understand your concern that this may cause unfair comparison, so we re-ran the experiments by giving the baselines a larger sampe budget equal to the size of the instruction set (10). We report the new results in the following table. **ChatGPT+ALGO is still the best after we increase other baselines' sample budget.**\n\n|  | pass rate | \n| -------- | -------- |\n| ChatGPT (budget = 5) pass@1    | 37.1%     |\n| GPT-4 (budget = 5) pass@1 | 45.7% |\n| ChatGPT + ALGO (budget = 1 per instruction) 10@1 | **48.6%** |\n| ChatGPT (budget = 10) pass@1 | 39.6% |\n| GPT-4 (budget = 10) pass@1 | 46.4% |\n\n**Temperature.** There is no temperature mismatch between ALGO+Codex and CodeT. Codex, CodeT and ALGO + CodeX in Table 1 are all using the same set of CodeX-generated candidate programs provided by CodeT. The only difference is how these programs were reranked. The temperature 1.0 we mentioned on Line 160 was during the generation of the \"oracles\", not the solution programs. We will make it clear in the revision.\n\n**Number of tests.** For the main experiments (in Table 1 and Figure 4), the number of tests generated by ALGO was 20.\n\n## 3 Sample budget for oracle generation\nALGO used a sample budget of 3 to generate oracle for each problem.\n\n## 4 \"Oracle\" quality for CodeContests\n\nDue to the time limit, we sampled 50 problems from the CodeContests test set to manually check the correctness of the generated \"oracles\". **It turned out that 72% of them were correct.**\n\nWe thank you again for your time and kindly remind you to take a look at our global rebuttal and supplementary files if needed."}, {"review_id": "k49jztpCt1", "reviewer": "Reviewer_UrDq", "summary": "This paper presents ALGO which is a technique for generating programs for algorithmic challenges like LeetCode problems. To be successful, a code solution must be both correct and efficient enough. The core idea in ALGO is to first ask a code LLM to generate a slow brute force solution that is likely to be correct but too slow. This is used as an oracle verifier to check whether other program samples are correct for small test cases. Thus, an existing code generation system can propose solutions which are then filtered or reranked according to agreement with the verifier. The experiments show that ALGO’s technique of using a brute-force solution as a verifier leads to improvements on CodeContests and LeetCode.", "questions": "## Pass@k given n samples\n\nIn line 216, what does “the same sampling budget $n$ under the same setting” mean? What is the “setting”? What is the actual value of $n$?\n\nIs it really fair to compare pass@k given n samples, to a reranking approach returning the top k among n samples? If we increase n, pass@k does not change in expectation, but the top k approach would improve (assuming the reranking is accurate). For example, AlphaCode (https://arxiv.org/abs/2203.07814) distinguishes these metrics as “pass@k” vs “n@k” (but note that the AlphaCode paper swaps the meaning of n and k). These are different metrics that are not easily compared directly.\n\n\n## Comparison to other reranking approaches\n\nCan ALGO be compared to other code reranking approaches, such as CodeT and Coder-Reviewer (https://arxiv.org/pdf/2211.16490.pdf)? Then, all reranking approaches can use the same “k@n” metric -- whether a good solution exists in the best k among n samples. (I know CodeT is in Table 1, but I was hoping for a more extensive comparison.)\n\n\n## CodeContests vs LeetCode\n\nSome experiments are done with CodeContests and other experiments are done with LeetCode. Why are the main experiments (Table 1, Figure 4) not repeated for both CodeContests and LeetCode?\n\n\n## Verifier correctness\n\nIt is unclear why the “time limit exceeded” (TLE) verdict is counted as “correct” for the verifier. I would agree that TLE means the verifier is “likely correct”, but it would be a leap to assert that all TLE verdicts are “correct” as a key result highlighted in the abstract and throughout the paper. If I’m not misunderstanding, then I think this claim should be rephrased or qualified.\n\nThe “88.5% correct” number (Fig. 2 and throughout the text) is only for LeetCode. Is it possible to get an analogous number for CodeContests?\n\nLines 251 - 253 mention manually verifying whether TLE solutions are functionally correct. What is the result of this? The next sentence says “88.5%” again, but this is exactly the AC + TLE amount from Fig. 2. Does this imply that you manually verified that *every* TLE solution was functionally correct? Please clarify.\n\n\n## Generating inputs\n\nLine 162 says “generate the input generator with an input validator” -- are there examples of this? In particular, the input generator and input validator are both *programs*, which is different from the CodeT approach of hallucinating inputs as text directly from the model, right? If so, this is a main difference that should be explained more thoroughly.\n\nGenerating valid inputs seems tricky, especially when there are problem-specific constraints that could be difficult or annoying to check (e.g., that a solution exists or is unique, that a graph is connected or contains no cycles, etc.). Can you comment on how often the input generator/validator programs work correctly?\n\n\n## Applicability beyond algorithmic challenges\n\nOutside of algorithmic challenges, can the authors comment on other situations were a code LLM can predict a verifier that is correct but undesirable for some reason, which then helps a synthesis search find better solutions? Maybe if the verifier is a lengthy inelegant solution and we want to search for shorter elegant solutions which rely on assumptions/heuristics/invariants that might or might not hold? Maybe the verifier is in a popular language but a solution is desired in an uncommon language?\n\nDo you imagine the approach being applicable to improving efficiency of real-world code? If so, how would ALGO differ from existing approaches to that goal?\n\nHaving an example of something like this, even if not a full experiment, would make the paper seem much more applicable.\n\n\n## Minor suggestions\n\n* “Oracle” usually means something that is always correct. However, the oracles used in this paper are not actually always correct. The ALGO approach simply *assumes* they are correct and treats them *like* an oracle. This distinction was initially not clear to me and only became clear after reading further into the text. Please consider clarifying this in the abstract and introduction.\n* “ChatGPT Code Interpreter” does not come with a citation, so it is extra important to clearly describe what it is, preferably when it is first mentioned (e.g., Line 55). The description in Lines 181 - 187 is good, just move it earlier.\n\n* Line 55: missing space between “Interpreter” and “We”\n* Line 82: What does it mean for a program to be “capable of solving” a problem? The program either passes the judge or not, so it either solves the problem or not.\n* Line 84: “produce an program” -> “produce **a** program”\n* Figure 3 caption: “polynomial time. While” -> “polynomial time, while”\n* Line 127: “We use the variable $I$ to denote the **variable** that the coder **enumerates**” -- it is unclear what the bold “variable” refers to or how the enumeration works. Consider that the prompt from Figure 3 says “What do you think are some **variables** that may affect the answer and how do you think they can be **enumerated**?” but this is definitely a different kind of variable and enumeration. It gets confusing when the same terms are used to describe very different things.\n* Line 145: “A iterative” -> “**An** iterative”\n* Line 168: this sentence implies that the verifier can’t be arbitrary. Why not? Possibly the best verifier comes from Code Interpreter, but would the approach still work with a verifier generated by some other code LLM?\n* Lines 231 - 233: “ChatGPT Code Interpreter is used as an instruction enumerator along with GPT-4’s performance” -- I don’t know what this means\n* Line 322: “Oracle in Program Synthesis” -> “Oracle**s** in Program Synthesis”\n* Line 322: “In traditional” -> “In **the** traditional”\n* Line 325: “due to the ambiguity nature” -> “due to the **ambiguous** nature”\n* Line 327: “in software testing domain” -> “in **the** software testing domain”\n* Line 352: what does “similarity” mean here? Does it make sense to say “based on the ease of generating brute-force solutions to algorithmic problems”?\n* Line 359: “paper. There” -> “paper, there”", "limitations": "The paper is missing a limitations section.\n\nI think the main limitation is in the accuracy of the oracle solution. If the oracle solution is actually wrong, then the ALGO approach will hurt the overall synthesis performance. There doesn’t seem to be an easy way to identify when the oracle solution is wrong. Generating correct inputs also seems tricky and may be limited to problems with simple input formats and constraints.\n\nAnother limitation is in the general applicability of ALGO, since it only works on problems where an existing code LLM can produce (in only 1 sample) a functionally correct oracle solution.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Originality: A key observation is that current code LLMs can produce highly-accurate (but slow) brute-force solutions to tricky algorithmic questions. This was not previously obvious to me because one does not usually think about slow brute-force solutions. (I think the authors should emphasize this observation!) Then, assuming the existence of a slow but correct brute-force solution, the ALGO framework is a natural and straightforward application of using a verifier to aid program synthesis.\n\nQuality: The experiments test a variety of ways of using ALGO with different models on different datasets.\n\nClarity: The paper is well organized and easy to read.\n\nSignificance: Improving code generation is certainly significant.", "weaknesses": "Originality: The process of using a verifier to filter/rerank solutions is pretty straightforward.\n\nQuality: There are some concerns about comparing pass@k with reranking the top k among n samples. The experiments could also compare against other code reranking approaches on both CodeContests and LeetCode. See the Questions below.\n\nClarity: I have a few clarification questions below, but nothing major.\n\nSignificance: The paper only discusses this approach applied to algorithmic challenges, which has only moderate significance. In the Questions section below, I ask the authors to elaborate on how ALGO might be practically useful in other settings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful comments and inspiring questions.\n## 1 pass@k vs n@k\n**We followed CodeT's exact setting.** The \"setting\" in Line 216 means that we used ALGO to rerank the solution candidates (**n=1000** per problem) provided by CodeT, so our results is comparable to those in CodeT's Table 3.\n\n**CodeT directly compared pass@k and n@k,** because the pass@k for a coder without reranking is equivalent to the n@k for a coder whose reranker returns a uniformly random permutation. This is why CodeT \"use the unbiased definition of pass@k as [their] baseline\".\n\n**We understand your concern,** pass@k and n@k are not easily compared. But n@k's of two coders with reranking are, which is why we compared them in Table 1. We will clarify the difference between the two, and report pass@k only as metric for reference.\n## 2 Originality and comparison to other reranking approaches\nWe do not claim reranking as part of our novelty. We highlight that ALGO is fundamentally different from existing works in verifier quality. We compare ALGO with one more baseline, Coder-Reviewer here, and will include more extensive comparisons in the revision.\n\n**ALGO is more reliable.** LEVER, Coder-Reviewer and CodeT checks programs only with language models. On the contrary, ALGO offloads the symbolic reasoning to a program. This technique makes models' reasoning more reliable and is used by other works such as *PAL: Program-aided Language Models*.\n\n**ALGO is interpretable, existing works are not,** because they depend solely on neural models. ALGO provides test cases and \"oracles\" interpretable by human. If a user is not sure about ALGO's \"verification\", they can simply check if the brute-force \"oracles\" are right. When we manually checked \"oracles\" (Line 251 - 252), we found brute-force programs were much easier to check than actual solutions. In some sense, ALGO has converted the task of checking AI generated programs to checking AI generated brute-forces.\n\n**ALGO performs significantly better than Coder-Reviewer.** We used the officially released candidate programs of Coder-Reviewer. We replace their reranker with ALGO's and keep everything else the same. We report the results in the following table (same setting as Table 2 in Coder-Reviewer).\n||Coder-Reviewer|CodeT|ALGO|\n|-|-|-|-|\n|pass@100|66.9%|65.8%|82.3%|\n## 3 CodeContests vs LeetCode\n**We report the performance of ChatGPT and ChatGPT+ALGO on CodeContests (sample budget n=20).**\n||k=1|k=3|k=10|\n|-|-|-|-|\n|ChatGPT,pass@k|4.4%|7.9%|12.2%|\n|ChatGPT+ALGO,20@k|12%|12%|14%|\n\nALGO can achieve 12% even when k=1, indicating ALGO's superior ability to verify programs.\n\nCodeT cannot be run on LeetCode because its backbone CodeX is no longer accessible. Our experiments of PG-TD on LeetCode is still ongoing because it takes very long time. We will update the results as soon as possible.\n## 4 Verifier correctness\n**We did not assert that all TLE verdicts were correct.** We did manually verify that *every* TLE solution was functionally correct. We believe the misunderstanding about this \"assertion\" is caused by our writing. We will rephrase and clarify this issue in the revision.\n\n**ALGO's verifiers are correct for 72% of CodeContests problems.** Due to the time limit we were not able to verify all 165 problems. To make the samples representative, we sampled 4 contests with a total of 50 problems from CodeContests to manually check them. 64% of all oracles get AC/TLE verdicts. **72%** of all oracles are functionally correct. The extra 8% comes from oracles that get runtime errors because their deep search recursions exceeded stack memory.\n\n## 5 Generating inputs\n\n**All input generators/validators we used can be found** in supplementary files, along with the prompts we used to generate them. Examples of input generators and input validators can be found in the Appendix (Figures 11, 12, 13, 15).\n\n**ChatGPT can to produce input generators/validators that follow problem-specific constraints.** Some tricky but successful examples for codecontests (see supplemantary files) include: generating trees (1575I), primes (1603E), permutations (1622B). We provide two more examples by ChatGPT that generates bidirectional connected graphs and directed acyclic graphs.\n```\ndef generate_random_connected_graph(n, m):\n    if n < 2 or m < n - 1 or m > n * (n - 1) // 2:\n        return \"Invalid n and m.\"\n    # Step 1: Ensure the graph is connected by creating a tree\n    edges = []\n    nodes = list(range(n))\n    random.shuffle(nodes)\n    for i in range(1, n):\n        edges.append((nodes[i - 1], nodes[i]))\n    # Step 2: Add random edges to the graph.\n    while len(edges) < m:\n        u, v = random.randint(0, n-1), random.randint(0, n-1)\n        if u > v:\n            u, v = v, u\n        if u != v and (u, v) not in edges:\n            edges.append((u, v))\n    # Convert to the desired format.\n    result = f\"{n} {m}\\n\"\n    for edge in edges:\n        result += f\"{edge[0]} {edge[1]}\\n\"\n    return result\n```\n```\ndef generate_random_dag(num_nodes, num_edges):\n    if num_edges > num_nodes * (num_nodes - 1) / 2:\n        raise ValueError(\"Too many edges to form a DAG\")\n\n    edges = set()\n    while len(edges) < num_edges:\n        u = random.randint(1, num_nodes - 1)  # ensure u < v\n        v = random.randint(u + 1, num_nodes)\n        edges.add((u, v))\n\n    result = f\"{num_nodes} {num_edges}\\n\"\n    result += \"\\n\".join(f\"{u} {v}\" for u, v in edges)\n    return result\n```\n## 6 Applicability beyond algorithmic challenges\nWe are glad you asked this! The possibilities you mentioned are inspiring and captured the essense of our method: naive yet functionally correct programs that are easy to find.\n\nDue to the rebuttal's length limit, we kindly refer you to our global rebuttal, where we introduce an example of ALGO's application - SQL optimization and talk about other possibilities.\n\n## 7 Minor suggestions\nThank you for the detailed and comprehensive suggestions. We will address these in the revision."}, {"review_id": "MSAG9UUQCE", "reviewer": "Reviewer_MVRV", "summary": "The paper introduces a new approach that utilizes Language Models (LLMs) to generate an oracle program for a given task, which is a brute-force search algorithm that is likely correct but potentially suboptimal in terms of runtime. The oracle program is then used to rank candidate programs based on their equivalence to the oracle on set of sampled inputs. The approach is applied to improve the performance of Codex and ChatGPT models and achieves additional improvements compared to the CodeT approach, which generates test cases on the fly and ranks programs based on consistency with those test cases. The proposed method is evaluated on challenging tasks from CodeContest benchmark and on a new set of LeetCode problems.\n", "questions": "Please see the weaknesses section for questions and suggestions.", "limitations": "Discuss the limitations regarding the increased inference cost of the proposed approach.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "The paper presents an interesting idea by leveraging the fact that brute-force algorithm based oracles might be easy for LLMs to generate. \nMoreover, compared to neural rankers or the CodeT approach, an oracle-based ranker presents a straightforward and reliable way to check for correctness of the sampled programs by just executing both programs on a set of sample inputs and checking the output consistency.\nThe evaluation includes challenging tasks from CodeContests, providing a robust assessment of the proposed method.", "weaknesses": "- The paper should mention estimates of inference times for all the approaches, including inference times for oracle generation, test generation, and code generation. It is important to discuss the tradeoffs associated with these inference times. For example, if CodeT is given the same inference time budget as ALGO, how does the performance difference change? Additionally, the impact of using an expensive and more capable model (ChatGPT) for oracle generation should be addressed, as it may introduce unfairness in the comparison with other approaches like CodeT.\n\n\n- Please provide more details to enable reproducibility of the results. How many oracles need to be sampled before finding the correct one? What value of n is used for the various experiments? In Figure 4, what is the setup used for ChatGPT and GPT4? How many samples are drawn from each model? Are they are also sampled with different instructions? Including a Pass@k table for various k values would also be helpful for the experiment in Figure 4. \n\n\n- It is unclear from the paper if the failure cases are due to the model's inability to generate any correct program within the n samples or if the oracle is not a good discriminator. Some analysis on whether the \"top-ranked but incorrect programs\" satisfy the oracle or not would help. \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable comments!\n## 1 Inference cost estimation\nWe argue that ALGO is NOT significantly more expensive than the baselines. We compare ALGO's cost with the baselines in two aspects - generation and validation.\n\n**ALGO has the same generation cost.** ALGO is a code generation framework where any coder can fit in. It is combined with existing code generation models like CodeX and ChatGPT. We compare ALGO to the baselines by keeping ALGO's sample budget to be the same. In our main experiments on CodeContests, ALGO is used to filter and rerank the exact same set of programs provided by CodeT. So it has the same generation cost.\n\n**ALGO has similar or cheaper validation cost.** Validation cost comes from model inference and test execution. For each problem, ALGO uses less then 5 model inferences to generate the \"oracle\" and the \"verifier\". However, the number of inferences for CodeT is proportional to the number of test cases it needs (which is 1000 for CodeContests), so ALGO costs much less in model inference. ALGO also costs less in test execution because ALGO can get much better performance with much fewer test cases (20 per problem) than the baseline (1000 per problem).\n## 2 The impact of using a more capable model\nWe provide extra baselines to show that ChatGPT is not the only reason why ALGO works. Instead of using ALGO's oracles to generate outputs, we directly used ChatGPT to generate the outputs of ALGO's test inputs.\n\nWe use three different test sets to rerank ChatGPT candidates on CodeContests: ChatGPT + sample tests, ChatGPT + ChatGPT-generated tests, ChatGPT + ALGO tests. The sample budget for each problem was 20. For each problem we picked the top-ranked programs as its solution. We report the pass rates of the top-k-ranked programs (20@k) below.\n|  | 20@1 | 20@3 | 20@7 | \n|-|-|-|-|\n| ChatGPT + sample tests    | 4.4%    | 7.9%|12.2%|\n| ChatGPT + ChatGPT-generated tests | 6.8% | 8.2% | 11.7%|\n| ChatGPT + ALGO-generated tests |12.0%|12.0%|14.0%|\n\nAs the table shows, even when the test generation module is replaced with ChatGPT, ALGO is still able to significantly improve code generation ability.\n## 3 More details for reproducibility\nThe sample budget for oracle generation was 3.\n\nThe sample budget for CodeT was 1000. We directly took the candidates provided by CodeT without generating new candidates ourselves.\n\nThe sample budget for PG-TD was 256, which follows the setting in the original paper.\n\nThe sample budget for ChatGPT and GPT4 was 5.\n\nFor pass rates with different top-k algorithms, we refer you to the table in the second part of this rebuttal *The impact of using a more capable model*.\n\n## 4 When does ALGO fail?\n\n**Most of ALGO's failures come from the coder's inability to generate correct programs within n samples.**\n\n**This can be deduced from ALGO's performance gain on CodeContests.** For different coders, we use the same set of oracles and verfiers to guide their generation. For weak coders like Codex and GPT-2 (Table 1), ALGO's improvement on performance is significant even when k is as large as 100, indicating that as the sample budget gets larger and more correct solutions get generated, ALGO is able to discriminate the good from the bad. However, for a strong coder like ChatGPT (the table in *\"The impact of using a more capable model\"*), ALGO's improvement converges for a very small k, indicating that ALGO is already to accurately find the correct solution (even when only the top-1-ranked program is picked).\n\n**This can also be analyzed from the problems not solved by ALGO.** For the 7 hard-level problems in our leetcode dataset, ALGO's oracle was correct for 5 of them. However, only 1 of the 5 was correctly solved by at least one program. 4 out of 5 problems could have been solved and verified by ALGO if we had a stronger coder.\n\nThank you again for your time! We kindly refer you to our global rebuttal for some common issues and some remarks about ALGO's application beyond algorithmic challenges."}, {"review_id": "qD6wnR6yAc", "reviewer": "Reviewer_oqZ5", "summary": "This paper presents ALGO, a new method for code generation for LLMs. Given a problem description, ALGO first generates a brute-force implementation and dozens of test cases. Then, ALGO generates efficient implementations and ranks them by the agreement with the brute-force implementation on the generated test cases. The evaluation covers different LLMs, code generation techniques, and evaluation datasets. It shows that ALGO improves significantly over considered baselines.", "questions": "Please consider addressing the points raised in the “Weakness” section.", "limitations": "While the paper includes a brief discussion of future work at Lines 359-365, it is very vague and does not pinpoint any limitation of ALGO. I believe that ALGO’s limitations, such as high cost, should be stated more clearly.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper is easy-to-follow and has good experimental results. It also provides an interesting ablation analysis in Section 3.4.", "weaknesses": "### Terminology\nVerification refers to proving formal properties of programs. The “verifier” fails to do so in two ways: (i) the “verifier” itself can often be wrong, and (ii) the “verification” is done on limited test cases and is thus unsound. I would suggest replacing “verifier” with a more appropriate term, such as cross-check, etc.\n\n### Motivation\nLines 26-32 point out an issue of existing code generation approaches: lacking verifiability. However, I think ALGO suffers from the same issue, because the generated “verifier” can be wrong. The users still cannot have trust on the output of ALGO.\n\n### Algorithm and functionality synthesis\nI am not convinced by the difference between algorithm and functionality synthesis. The definition provided in the paper is very subjective and informal. For example, one can argue that the example of functionality synthesis in Figure 7 involves an idea of using a list comprehension instead of a for loop. In fact, both can be seen as standard text-to-code tasks. This makes me wonder how ALGO performs on HumanEval or MBPP.\n\n### Discussion and comparison with existing work\nThe paper lacks a discussion and comparison with the following existing works. The first work also learns to “verify” generated code with test cases, while the second uses a reviewer to rank generated code.\n\nLEVER: Learning to Verify Language-to-Code Generation with Execution. ICML 2023. https://arxiv.org/abs/2302.08468.\nCoder Reviewer Reranking for Code Generation. ICML 2023. https://arxiv.org/abs/2211.16490.\n\n### Cost analysis\nIt seems to me that ALGO can be significantly more expensive than the baselines. However, the paper does not include any cost analysis of ALGO.\n\n### Instructions\nWhat instructions do you use for the Instruction Enumerator at Line 137? It seems that the choices of instruction can significantly affect the performance.\n\n### Small Issue\nLine 55: InterpreterWe -> Interpreter. We\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the thoughtful comments.\n## 0. Terminology\nWe understand your concerns. We will replace the term *verifier* in the revision. To avoid confusion, we use the terms \"verifier\" and \"oracle\" with quotation marks in the rebuttal.\n## 1. Motivation and discussion about existing works\nWe highlight that ALGO is a step forward towards verifiability which is fundamentally different from existing works like LEVER, Coder-Reviewer, and CodeT.\n\n**ALGO's verdict agrees well with the system judge.** The first three rows in Table 1 indicate that by using ALGO instead of CodeT as reranker on the exactly same set of program candidates, the top-ranked programs perform significantly better. Table 2 of our paper indicates that ALGO's verdict has a high agreement with that of the system judge.\n\n**ALGO is more reliable.** LEVER, Coder-Reviewer and CodeT checks programs only with language models. On the contrary, ALGO offloads the symbolic reasoning to a program. This technique makes models' reasoning more reliable and is used by other works such as PAL [1] and PoT [2].\n\n**ALGO is interpretable, existing works are not,** because they depend solely on neural models. ALGO provides test cases and \"oracles\" interpretable by human. If a user is not sure about ALGO's \"verification\", they can simply check if the brute-force \"oracles\" are right. When we manually checked \"oracles\" (Line 251 - 252), we found brute-force programs were much easier to check than actual solutions. In some sense, ALGO has converted the task of checking AI generated programs to checking AI generated brute-forces.\n## 2. Comparison with existing work\n**LEVER has a different task setting, so it cannot be compared with ALGO.** To check a program, LEVER needs access to test-time system inputs. But ALGO doesn't. This makes things easier for LEVER since it only needs to focus on the correctness of this specific input. As they stated in limitations, LEVER is \"ideal for applications such as text-to-SQL and math reasoning where the users are only looking for answers to their questions\", but not as suitable for \"general programming tasks as MBPP\".\n\n**ALGO performs significantly better than Coder-Reviewer.** We used the officially released candidate programs of Coder-Reviewer. We replace their reranker with ALGO and keeping everything else the same. We report the results in the following table (same setting as Table 2 in Coder-Reviewer).\n||Coder-Reviewer|CodeT|ALGO|\n|-|-|-|-|\n|pass@100|66.9%|65.8%|82.3%|\n## 3. The scope of algorithm synthesis\nHere we define algorithm synthesis more formally and demonstrate its difference from functionality synthesis.\n\n**Algorithm synthesis.** Following the notations in Section 2.1, we use $J_S$ and $J_T$ to denote the system judges for semantic correctness and time efficiency. We denote all semantically correct programs with $P_S$, such that $J_S(P_i)=\\mathsf{True},\\forall P_i\\in P_S$. $P_S$ can further be divided into two subsets $P_S^0$ and $P_S^1$, such that $J_T(P_i^0)=\\mathsf{False},\\forall P_i^0\\in P_S^0$ and $J_T(P_i^1)=\\mathsf{True}, \\forall P_i^1\\in P_S^1$. In other words, $P_S^0$ is correct but slow, while $P_S^1$ is correct and efficient. A task belongs to *algorithm synthesis* when finding a program within $P_S^1$ is more challenging than within $P_S^0$.\n\n**LeetCode and CodeContests are algorithm synthesis, while HumanEval is not.** In the following table, we report the success rates for ChatGPT to generate a program in $P_S^0$ and $P_S^1$ when prompted to. A brute-force is in $P_S^0$ if it is manually checked to be right. An efficient solution is in $P_S^1$ if it passes all system tests in time. For LeetCode and CodeContests, it is much easier to generate brute-forces than efficient solutions. But for HumanEval, it's similarly easy. Therefore, HumanEval is not algorithm synthesis according to our definition. \n||LeetCode|CodeContests|HumanEval|\n|-|-|-|-|\n|$P_S^0$ (brute-force) succ. rate|88.5%|72.0%|70.12%|\n|$P_S^1$ (efficient) succ. rate|41.2%|7.9%|72.56%|\n|relative $\\Delta$|114%|811%|-3%|\n## 4. Cost analysis\nALGO is NOT significantly more expensive than the baselines. We compare ALGO's cost with the baselines in two aspects - generation and validation.\n\n**ALGO has the same generation cost.** ALGO is a code generation framework where any coder can fit in. It is combined with existing code generation models like CodeX and ChatGPT. We compare ALGO to the baselines by keeping ALGO's sample budget to be the same. In our main experiments on CodeContests, ALGO is used to filter and rerank the exact same set of programs provided by CodeT. So it has the same generation cost.\n\n**ALGO has similar or cheaper validation cost.** Validation cost comes from model inference and test execution. For each problem, ALGO uses less then 5 model inferences to generate the \"oracle\" and the \"verifier\". However, the number of inferences for CodeT is proportional to the number of test cases it needs (which is 1000 for CodeContests), so ALGO costs much less in model inference. ALGO also costs less in test execution because ALGO can get much better performance with much fewer test cases (20 per problem) than the baseline (1000 per problem).\n\nWe will include the above cost analysis in the revision.\n## 5. Instructions\nThe instructions we used are included in the supplementary files. We would like to emphasize here that while the instructions can significantly affect the performance, ALGO is able to improve the performance for different coders with different instruction sets (as demonstrated in our experiments).\n\n**Thank you again for your time. We kindly refer you to the global response for some common issues. Feel free to ask for further clarification.**\n## References\n[1] PAL: Program-aided Language Models\n\n[2] Program of Thoughts Prompting: Disentangling Computation from Reasoning for Numerical Reasoning Tasks"}]

Author rebuttal:
We thank the reviewers for their thoughtful reviews and comments. We would like to address some common issues mentioned in multiple reviews and clarify the main points of our paper. For reviewer-specific issues, we have responded in reviewer-specific rebuttals.
## 0. Reminders
**Terminology.** We understand several reviewers' concerns about the proper use of the terms *oracle* and *verifier*, and promise to use more appropriate alternates in the revision. To avoid confusion in the rebuttal, we will refer to the exhaustive search programs generated by language models as "oracles", and the program correctness checker as "verifiers", with quotation marks, throughout the rebuttal period.

**Supplementary files.** We kindly remind the reviewers that the characteristics of the "oracles" and "verifiers" we talk about can be examined in the supplementary files, which contain our prompts, input generators/validators, "oracles", test cases and candidate programs.
## 1. ALGO's "verifier" is fundamentally different from existing works.
We thank the reviewers for pointing out some existing works such as LEVER [1] and Coder-Reviewer [2]. We will cite them and discuss more in the revision. Here we argue that ALGO's "verifier" has fundamental differences compared to the existing works. These differences come from its neurosymbolic nature.

**ALGO provides more reliable feedback.** Neural "verifiers" [1,2] provide little feedback by only giving a "correctness" score. Previous test-based "verifiers" like CodeT [3] provide some feedback with their LM-generated test cases, whose correctness solely relies on the arithmetic and symbolic reasoning ability of language models. However, language models often make mistakes in arithmetic and symbolic reasoning, which is why they solve math problems better by generating programs rather than directly outputting the answer, as demonstrated in PAL [4] and PoT [5]. Therefore, the test cases generated by LMs for a SINGLE problem probably contain both correct and incorrect ones, providing harmful feedbacks to the coder. However, once we have a correct "oracle" for a problem (which we do for 88% Leetcode problems), ALGO guarantees that ALL test cases generated will be correct.

**ALGO is interpretable and easy to validate.** Unlike LEVER and Coder-Reviewer which use inexplainable neural models to score the correctness of a program, ALGO uses "oracles" in the form of exhaustive search programs. For a candidate program, there is no way of telling how a neural model comes to its "correctness" score and whether the score actually reflects correctness. But any programmer is able to tell if a brute-force "oracle" is correct. According to our hired human annotators, manually checking a brute-force program is much easier than checking an efficient one using advanced algorithms. Because efficient solutions are diverse and problem-specific, while brute-force programs are similar and mostly enumerating permutations, subsets and stepwise choices.

## 2. ALGO may be applicable to general algorithm synthesis scenarios beyond programming contests.
In this part, we address reviewers' doubts about the scope of *algorithm synthesis* and if ALGO can be applied beyond programming contests. In general, ALGO can be applied to scenarios where a naive, correct but less satisfactory oracle is much easier to find then a satisfactory solution. Language models can be used to find this naive solution, which can later be used to guide the search for a satisfactory solution.

**Now we give a concrete example on how ALGO can assist LLMs to using programming languages and frameworks that aren't well-represented in the training data.** Here, the naive yet less satisfactory oracle is a program that's written in a popular language/framework well-represented in the training set.

Consider a basic function that fetches a city's name from Google Maps API using GPS coordinates. This program needs to run on an embedded system with limited memory and storage, therefore requiring it to be written in C++ using the `neon` library.

**Directly prompting GPT-4 won't work.** It got us the following code snippet.

**[First link to code snippet that we sent to the AC]**

When we tested the above code using LLM-generated test cases, the generated cases were not correct.

```
User: Generate test cases for a program that fetches city name based on GPS coordinates.
Input: 33.798242689239636, 2.87416689773028
Output:

ChatGPT: Input: 33.798242689239636, 2.87416689773028
Expected Output: City Name: Al Qadarif
```

In the provided example, ChatGPT incorrectly recognizes the location as Al Qadarif, whereas it's actually Laghouat, a city 2000 miles away.

Instead of hinging upon LLM’s ability to map inputs to outputs, ALGO can develop a straightforward "verifier" utilizing popular solutions like Python's requests library to ensure its accuracy. We presented the GPT-4 generated "oracle" in Python below.

**[Second link to code snippet that we sent to the AC]**

The above "oracle" can then check and guide the generation of a more efficient solution in C++.

There are other scenarios where ALGO may be applied, including loop optimization, computation graph scheduling and parallel computing.

We would like to thank the reviewers and the chairs for their time and efforts!

## Reference
[1] LEVER: Learning to Verify Language-to-Code Generation with Execution

[2] Coder Reviewer Reranking for Code Generation

[3] CodeT: Code Generation with Generated Tests

[4] PAL: Program-aided Language Models

[5] Program of Thoughts Prompting: Disentangling Computation from Reasoning for Numerical Reasoning Tasks

Meta-review: This submission presents ALGO, a method for solving programming challenges. The challenges are usually made up from a natural language task description and some test cases. Correctness is judged based on (held-out) test cases and often imposes running time limits.
The presented idea is to first use a prompt asking the LLM to generate a simple, “brute-force” solution, independent of running time concerns. This is often easy in algorithmic programming challenges. Then, the LLM is also asked to generate an input generator, whose outputs are used to compare the “brute-force” solution and potential efficient solution. Failures can be used to inform the generation of an improved efficient solution.

Reviewers highlighted that the proposed idea is simple but insightful (MLQT, MVRV) and that the experiments are well-suited to illustrate the utility of the proposed method (MLQT, UrDq, MVRV, oqZ5). Concerns about details of the experiments were cleared up during the rebuttal phase.

However, reviewers voiced doubts about the applicability of the proposed method to the general setting (oqZ5, UrDq), as the basic assumption about the ease of generating brute-force solutions seems to only hold in the programming challenge setting. While the authors provided a further example in the global rebuttal (though in their reply to UrDq also referred to a SQL optimization example, which does not appear?), that example does not seem to support the hypothesis of generalizing to the more general setting. The “simplistic” and “full” solutions do not differ in algorithmic complexity - they are effectively the same, and the C++ variant fails because GPT-4 hallucinates libneon interfaces, not because of an algorithmic mistake. Fixing this just requires a model better at writing C++, and the "simplistic" solution as oracle doesn't really help.

Overall, this is a borderline case. The authors have made a convincing case for their idea in the competitive programming setting, but so far there's little hard evidence that the method would be useful in the more general program synthesis case. Nonetheless, I think this may inspire interesting follow-up work and hence should be presented to a wider audience at NeurIPS.
Decision: Accept (poster)