Parsel🐍: Algorithmic Reasoning with Language Models by Composing Decompositions
Authors: Eric Zelikman
Qian Huang
Gabriel Poesia
Noah Goodman
Nick Haber
Venue: NeurIPS 2023 spotlight (2023)
Keywords: reasoning
language models
code synthesis
decomposition
TL;DR: Language models can solve algorithmic reasoning tasks by decomposing them, solving subparts, and composing them.

Abstract: Despite recent success in large language model (LLM) reasoning, LLMs struggle with hierarchical multi-step reasoning tasks like generating complex programs. For these tasks, humans often start with a high-level algorithmic design and implement each part gradually. We introduce Parsel, a framework enabling automatic implementation and validation of complex algorithms with code LLMs. With Parsel, we automatically decompose algorithmic tasks into hierarchical natural language function descriptions and then search over combinations of possible function implementations using tests. We show that Parsel can be used across domains requiring hierarchical reasoning, including program synthesis and robotic planning. We find that, using Parsel, LLMs solve more competition-level problems in the APPS dataset, resulting in pass rates over 75\% higher than prior results from directly sampling AlphaCode and Codex, while often using a smaller sample budget. Moreover, with automatically generated tests, we find that Parsel can improve the state-of-the-art pass@1 performance on HumanEval from 67\% to 85\%. We also find that LLM-generated robotic plans using Parsel are more than twice as likely to be considered accurate than directly generated plans. Lastly, we explore how Parsel addresses LLM limitations and discuss how Parsel may be useful for human programmers. We release our code at https://github.com/ezelikman/parsel.

Parsel Algorithmic Reasoning with Language Models by Composing Decompositions
Eric Zelikman, Qian Huang, Gabriel Poesia, Noah D. Goodman, Nick Haber
Stanford University
fezelikman, qhwang, poesia, ngoodman, nhaber) edu
Abstract
Despite recent success in large language model (LLM) reasoning, LLMs struggle with hierarchical multi-step reasoning tasks like generating complex programs. For these tasks, humans often start with high-level algorithmic design and imple- ment each part gradually. We introduce Parsel, a framework enabling automatic implementation and validation of complex algorithms with code LLMs. With Parsel, we automatically decompose algorithmic tasks into hierarchical natural language function descriptions and then search over combinations possible func- tion implementations using tests. We show that Parsel can be used across domains requiring hierarchical reasoning, including program synthesis and robotic planning. We find that, using Parsel, LLMs solve more competition-levar problems in the APPS dataset, resulting in pass rates over 75% higher than prior results from di- rectly sampling AlphaCode and Codex, while often using smaller sample budget. Moreover, with automatically generated tests, we find that Parsel can improve the cate-of-theear pass performance on HumanEval from 67% 85%. We also find that M-g--rreetted robotic plans using Parsel are more than twice as likely to be considered accurate than directly generated plans. Lastly, addresses LLM limitations and discuss how Parsel may be useful for human pro- grammers. We release our code at https: h/gps:///gtttbb/ com/ ezel 1mman/ maneaanpparel..
explore how Parsel
Introduction
To a language model for code (as for human), each new token is new chance to break the program. Chen al. [12] highlighted this issue in a simple synthetic experiment: when asked to generate program with series of simple string transformations, the performance of their code language model, Codex, drops dramatically with the number steps. As they pointed out, human who can implement few building blocks should be able to compose these blocks with arbitrary length.
Unlike other token generators, human programmers have (mostly) learned to break down complex tasks into manageable parts that work alone (i.c.. are modular) and work together (i.c., are composi- tional). And, when genertte tokens cause functions break, the functions can ideally be rewritten independently of the rest of the program. In contrast, naively, we expect code language models generate token sequences that are correct their entirety. Motivated by this, we study how to leverage language models to decompose problems and assemble their compositional solutions.
We introduce Parsel, a framework that enables the decomposition, implementation, then composition of complex programs from natural language. The process consists of three main steps: 1) A language model generates Parsel program by decomposing natural language task into natural language function descriptions. 2) For each function description, a language model generates modular implementations. The Parsel synthesizer then builds up programs by testing minimal, combinatorial groups of implementations against sets of constraints (c.g. input-output examples).
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Task/Problem
Statement
Description
Function
Decompose
Problem
or
Description
or
Description
Function
Program
Synthesizer
Figure I: Parsel overview. human or LLM writes a task decomposition (in Parsel), which is split into its strongly-connected components (SCC), and then the Parsel synthesizer code LLM and a constraint solver to implement and compose each SCC. When all functions have constraints and there no recursion, each function its own SCC. We provide more detailed figure in Appendix H.
Thus, generating and implementing Parsel mirrors a pattern in human reasoning decomposing an abstract plan until it can be solved automatically [55] - and this compositional structure also benefits language models. We show that LLMs can generate Parsel with only few-shot prompting. Using their solutions as input to the Parsel synthesizer, we outperform prior work on competition-level problems in the APPS dataset [27], including AlphaCode [35] and both versions of Codex [12, 11]. We also show that with GPT-4 [44], not only can we generate Parsel zero-shot just by describing its format, but this allows it to substantially outperform GPT-4 alone HumanEval [12), with and without generated tests. By automatically generating and implementing Parsel, LLMS also propose robotic plans that are more accurate than in prior work on language models robotic planners [28]. Broadly, we formulate Parsel as a general-purpose algorithmic reasoning framework.
Methods
In this section, we provide an overview of the Parsel framework. First, we show how programs can be specified in Parsel. Afterward, we explain how language models can generate Parsel from task deseriptions. Finally, we present the Parsel synthesizer that allows us actually implement Parsel programs into runnable code. Specifically, we further discuss how we handle various challenges in solving the constraints, from recursion synthesizing Parsel program, which we explicate in this section. We visualize the details in Fig. and provide a high-level pseudocode in Fig. A.
test underspecification. There are several steps to
With Parsel, we balance two challenges. On one hand, function implementations must be modular to fully leverage combinatoriality, By requiring function signatures and descriptions be specified (or generated), we ensure functions can call others without specific implementation information. On the other hand, it must be possible to avoid combinatorial explosions. By factoring the dependency graph into coongly-coneetted components (SCCs), we ensure the complexity grows exponentially only component but the total number of functions.
with the size of the largest
2.1 Specifying Parsel Programs
To formally specify high-level algorithmic design, develop simple intermediate language, also called Parsel. It is designed to be accessible to programmers, code I.IMs,, and students, as discussed further in Appendix A, and inspired by many works (Section 4). In Parsel, each line contains a function description, a constraint, or reference to a description. They all obey scoping rules, with some nuances per target language. In short: descriptions specify what function does in natural language, optionally preceded by function name and its arguments (if not included, they are inferred): references indicate to the language model that function should call another function described elsewhere; constraints validate that function is implemented correctly (if not provided, they may be generated automatically using the language model). We elaborate on syntactic details in Appendix R. We provide some examples of Parsel programs in Figures 2 and 3. For example, Figure 2, task_plan() return a list of strings represents a description, while the call to collatz_ree collatz__ecursion by zecursion, rule reference.

---

reprasente an acntonn plan
frem ececston Jone ingost
task_plan(): return a 1ist of stringa that represents an action plan to put mug on the stall and bread the desk. "executable"
bread on the deak. def tark_plan()
acrtpe (tank.plsn())
zutize pas, objecs, oot
wartaain tual houe
stall") pur, pur_abgeec_oo
>>
return a 1isk of steiigg that
"aca2l")) "ececutahle"
pat_ebjact__nn (obbject,, place):
return 1ist S of stringe that represents an action
pat object in place.
ded put wkw.kkkatttttt wabpsctt_aabbbee aafoejectt place):
plan to put an object in a place. "mug", "stall" >> "executable"
"Zand_" deject.
Haslli your place.
object 'Lmau'
place
Figure i: Parsel to VirtualHome (robotic planning)
(nun, cur_liet=liet()): Calls + base_case if 1, othereise recursion_rule
recuraies rule
otherwtee
Add List, collute I tr and or / wrnn
[19, 58, 29, 88, 44, 11, 34, 17, + 26, 13, 40, 20, 10, 6, 16, 8, 4, 2, 1] base_case (num, cur, cur_liat): Returna the 1ist - with the nunber appended to it recursion_rule(nnn cur, _ur_]i Add num to list, collatz with 1 if add 2 1f evan colleta_recureion
3. def collara co cer_1les
sucuc socurvion,aa (aum, cut cur,liat):
zun reture bore..opeeCunn 1iet)
11 aus aependerrn
recursienntaa R, mir_1ee))
eloet
slves
Saturns 1158 with the nember
cur. lant)
aue) I. cur 1ist)
del luse caseluan, car 3iat::
appanded
68, 29, 88. 44, 20, 1t, 36. 13, 40, 25, 10,
append(ocn)
10
Figure ii: Parsel to Python
Figure 2: Examples using Parsel to compile programs for VirtualHome [50] procedures and Python. Note the columns on the generated examples are only there to allow them to fit compactly each program implementation is one contiguous solution. Colors for Parsel code on the left are used to indicate constraints and references. All other Parsel lines shown are definitions.
2.2 Generating Parsel Programs
We use a language model to generate Parsel programs from arbitrary natural language task descriptions as few-shot translation task (or zero-shot with GPT4 [44]). Explicitly writing out a preliminary plan can be helpful, so we first ask the model to (zero-shot) generate plan in natural language by thinking step-by-step (motivated by Kojima et al. [32]) and then prompt the model to translate the plan to Parsel. These steps correspond to the first and second arrows in Figure 3, respectively. In some domains, in particular for robotic planning, we find that this intermediate step is not necessary (while increasing cost) and can ask the language model to directly translate the task description to a Parsel solution.
2.3 Implementing Parsel Programs
Given the Parsel program, core technical challenge is how to implement it in a modular way (to fully leverage the advantage of decomposition). Here we propose the Parsel synthesizer: At a high level, to implement Parsel programs with the Parsel synthesizer, we first use language model to generate a set of candidate implementations of each of the functions based on their descriptions and then search over minimal sets of combinations of the functions to find ones that satisfy the provided constraints. The step described in this section corresponds to the rightmost arrow in Figure 3.
2.3.1 Implementing Functions
function is implemented by first aggregating descriptions and function signatures of its (potentially zero) children to form an LLM prompt (for Python, we generate a prompt as if the child functions are imported and use their descriptions as comments). Crucially, this facilitates easily changing child implementations. A code LLM is then queried using the description's 's text as a docstring and the description's 's function name and arguments for the signature; full prompts shown in Appendix K.
2.3.2 Searching Over Function Combinations
Sequential case. The most straightforward case is when all functions have constraints (e.g., unit tests), and no functions have recursive dependencies (e.g., Fig. A.9). We start by considering this case. This defines clear topological order on functions so they can be implemented sequentially. In this situation, Parsel implements functions with post-order traversal from function the root, generating implementations and finding one passing the specified constraints for each function. In
3

---

Tisk
High-lesel Sketch
Parsel Program
Progam
the gradd
Firt,ove and to figre oen haw to coleciee the sesirrenn of of pouch toe coth
of Jantatiope, strl: faturra the and uss saliet sherls raat
qenlly thre anous sild,
trquask
coupe tiu, the sas La remeed
Chear
slye progee progremiin typooich
paraa tepattinne, str): Thoms scrinn
dus volam of jevis slose
the sapua apus of his canerr Le
you
jendl and oitame
arte will repruree the mustur sunt
iise of krapact The vaacc ot cach cull in
We cenair oun dioennin and uno dir
repeevee
cattaces
kopeeck sires or the first lin,, the
slae,, and the jeatls
jemcs the wat Lires, and returns
our
of Jeuals, for start
hitihhhotoe toatttt Just teet TD" Mie
onter medicaa socad waket
jowels stee: ietures the masseu sue
We zay then nesse thrughh attop, maring
for each joelss that stalen
and
Claard has lnmerads of
tur pusri ETLL jestri jesti
wotee like
the
the cevii of volle an of poods that
undes lasaeaad sioe be sillng
jewels, Jewi): intures the
vocsen (rells slick
thit be riiden this
matimun salies Swatls that
the the provhnse cally saleraa
soie twer lass that casll tis. calue of Heals secs centery!
cwide shedf sepeett
the ouree jeod.
the meseram
atsy pes jevels that be undee for euch tospreck vonr We can thec
ta cutpes strr
the string of the nacima sas of values
infore of joats chen
jeeits that be stodis for sach
wappir thoe velere sravcr
Dreeliaed appendie)
stendy
Figure 3: Parsel pipeline. Overview of the full Parsel pipeline for an APPS example. Each step is performed by language model. We include the complete task, sketch, and program in Appendix S.
other words, without any cycles in the call graph, we can start by implementing the leaf functions first, then their parents, etc., until the program is implemented. However, in practice, many programs have more complex structures and constraints.
Recursion. Permitting mutual recursion (e.g. a function f that depends on g while g also calls f) introduces the need for joint implementation of functions. However, naively considering all possible implementations is intractable for large programs. Specifically, the number of possible implementations of program with & functions and n implementations per function is O(n*), exponential in the number of functions. We propose a more efficient solution, inspired by Cocke and Kennedy [16]. We reference the function call graph, identify its strongly-connecte components (SCCs), and for each SCC consider all possible sets of function implementations until one set satisties all constraints. For example, for possible implementations of functions f.g. forming an SCC of a call graph, with I (() corresponding to the manguage-moddl-ggneeaae implementations of f. we evaluate uniformly random samples without replacement from I(f) [(g) I(h).
Functions without constraints. For functions with no constraints, we can conveniently use the same approach above by reformulating the call graph as a "test dependency graph" and adding an edge from a test-less child to its parent. That is, if a function has no constraints, it depends on its parents to enforce constraints on its implementations. This could also allow to automatically introduce new children via automatic decomposition without needing to also generate constraints for those children (see Subsection R.3). Alternatively, we support automatic test generation, prompting the language model to generate tests. For generated tests, we select the best implementation based on CodeT score [11], as some generated tests could be incorrect. In practice, we use the first (dependency) approach for inner functions and the second (test generation) approach when the top-level function has no tests. Note an opposite extreme from the sequential case: if no function or only the top-level function has constraints, we simply implement each function some number of times and then test all combinations. More generally, if n functions with m implementations where the sizes of the SCCs are most c. partitioning reduces necessary evaluations from O(n")) O m
3 Experiments
We explore the ability of Parsel to generate programs for various tasks, including competitive coding, a standard coding benchmark, and robotic task planning. These three categories represent related but distinct kinds of algorithmic reasoning, with varying levels of abstractness and generalizability. Competitive programming represents one of the few benchmarks for evaluating code generation tools that benefits greatly from decomposition." By evaluating Parsel on this breadth of tasks, we hope to better understand its generality as framework for algorithmic reasoning.
"Unfortunately. benchmarks that evaluate language models on complex real-world programming tasks requiring thousands of lines of code do not currently exist. Developing such a dataset is an important direction for future work.

---

30%
30%
Competiionn Level APPS Paos Rate
Parsel (Ours)
8x16
Codex (Dineet)
AlphaCode 1B (Direet)
20%
8xc8
(Improved)
4x88
10%
10%
2x8
1000
5 5000
1x8
1000 (Original)
09
0%
1000
10000
100
1000
10000
100000
Sumple Budger (# of Complete Programs Tnferenced)
Total Evalations per Problem
Figure 4: Left: Competition-level problem pass rate. Comparison of Parsel's pass rate on competition-level APPS problems [27] against direct code generation with Codex [12, 11] and AlphaCode [35] Labels correspond to pass @n and pass@n x k. Sample budget is measured in effective number of complete programs generated by the code LLM. (These measures are further explained in Subsection 1.).) Right: Pass rate number of evaluations. Parsel generates and evaluates many programs with a small inference budget, by combinatorial composition. Though evaluation is cheap compared to generation, we examine to understand the effect of evaluation number. For evaluation budget analysis, we evaluate pass@8 x 16 on random 200- 100-problem competition- APPS subset, and sample combinations of function implementations random for given budget.
3.1 Python Code Generation
Solving competition-leve problems. We evaluated Parsel the competition-level subset of the APPS [27] dataset as follows: first, we zero-shot prompt GPT-3 (text-davinci-002) with the problem statement, requiring it first propose a high-level solution and explain why is correct, asking it to "think step by step to come up with clever algorithm" [32]. We then prompt Codex [12] to translate the generated solution into Parsel code, providing three examples of valid code. We then attempt to synthesize the Parsel code and evaluate inplementations to measure their pass rate, i.c., the proportion of solved problems. We report "pass @ x k", where semi-formal programs generated and k is the number of implementations per function. Prior work has emphasized performance as function of the L.LM sample/inference budget measured in complete programs generated [12, 35]; for Parsel, we use the effective number of complete programs generated from the LLM for comparison, which is n x k. We compare to directly generating solutions from Codex [12. 11] and AlphaCode [35]. We visualize the pass rate in Figure 4, finding that Parsel substantially improves over prior work [11], from 14.5% to 25.5%. We include full prompts and further evaluations in Appendix N and discuss the evaluation runtime costs in depth in Appendix T.8.
the number of Parsel (i.e. intermediate,
Since Parsel will mmix-and-match" function implementations, the number of distinct candidate programs available to test grows exponentially with k while the generation cost for the components is linear. Generating each program likely requires on the order of PetaFLOPs of compute [21], dwarfing the computational cost of testing complete programs. Yet when few functions have constraints (as in this evaluation) or there are complex recursive dependencies, it could become expensive to exhaustively evaluate all possible programs. Thus, we also explore the performance of Parsel as function of the number of evaluations, as shown in Fig. 4. We find that the performance improves log-linearly with the number of evaluations, justifying spending compute to evaluate all programs implied by generated function implementations. One can interpret this to suggest the number of Parsel programs and combined implementations play similar and important roles. Thus, one may compensate for implementation ability with Parsel-generate
ability and vice-versa (to a limit).
Ablating the Parsel synthesizer. We perform an ablation to explore the impact of the Parsel inter- mediate language: we provide the same high-level plans to Codex, but instead of translating them to Parsel and synthesizing programs as decribed, we translate them to Python directly. We match the code generation budget (effectively complete programs inferenced), generating 16 Python imple- mentations? per high-level plan on 100 randomly sampled problems, and find that the pass @S x 16
Sampling the longer solutions resulted hitting rate limit more frequently, even when using the same number of total tokens per prompt: full 128-solution comparison on 1000 problems would potentially take months.
5

---

performance drops to 6% from 25.5% for the full pipeline. Not only did this approach solve substan- tially fewer problems, but the problems that it did solve were strict subset of those which we were able to solve with Parsel. This indicates that for Parsel with Codex, the step-by-step decomposition provided by the high-level plan not by itself responsible for the observed improvements by Parsel.
We additionally perform an ablation to understand how Parsel's performance without high-level plan. On 200-problem competition-level APPS sample, we found that, without a high-level plan, the accuracy falls to 13% (from 25.5%, with the same configuration). This is better than the ablation where Parsel wasn't 't used, suggesting that Parsel plays larger role than the high-level plan on APPS, but both are necessary. Note part of this improvement is from the challenge of prompting Codex to generate Parsel, given long APPS problem statements.
HumanEval. We next tested Parsel on HumanFval(12], Because these problems are substantially simpler, they provide opportunity evaluate pass@1 by generating tests automatically. Fur- thermore, this smaller and simpler set of problems enables us to assess the (much more costly) GPT-4. We found significant improvement over the state-of-the-art pass performance- from 67% to 85%. We found that by describing the Parsel format (see Appendix O for details), noting the role of indentation in providing hierarchy and explaining the format of a description, GPT-4 was able to translate natural language plans into Parsel zero-shot. Moreover, the combination of Parsel and GPT-4 surpassed GPT-4 alone on HumanEval, both with and without generated tests, further emphasizing the importance of leveraging intermediate languages like Parsel for improved code generation performance in complex tasks.
The 85. 1% pass rate with generated tests, eval- uated based the CodeT score [1]], was ob- tained by sampling until three Parsel programs had one implementation passing generated test and then selecting the one passing the most tests. On average, this required 3.5 Parsel pro-
GPT4
Parud
Prn Roteoo Hammniial
grams per problem, with 8 implementations each (i.e. < 32 complete implementations on average). Parsel also outperforms GPT-4 with
Code'T alone on the same set of tests, and using a comparable 32 samples, which passes 81.1% % of the problems.
73%
pawejt (GudeT)
paidjayy (54 prograaa) panajaay (128 grograna)
Additionally, when evaluating performance in terms of pass@any (i.e., not filtering attempts by CodeTT, we discovered that by allowing up to Parsel programs (still with 8 iipplementations each), the pass rate increased to 91.5%. In contrast, when allowing up to 64 directly generated programs, the pass rate was only 82.3%. This difference becomes more pronounced when generating 128 programs (128 directly vs. 16 x 8 with Parsel), improving from 84.1 % to 93.9% (See Fig. 5).
Figure 5: Pass rates on HumanEval. We an- alyze the effect of using Parsel with GPT-4 [44] on HumanEval [12]. Given the same program in- ference budget, the pass rate with Parsel improves regardless of whether one filters by generated tests.
While there are still eight tasks that are never solved with or without Parsel, GPT-4 solves eighteen problems with Parsel that it cannot solve alone. For eight of these, the solution has six or more functions (excluding defined but unused functions). Of the problems Parsel solved, the ones GPT-4 could not solve itself required 4.2 functions on average, while those GPT-4 could solve required only 2.8 functions (sampled over 50 problems). We find GPT-4 alone solves two problems pass @any that The cccodeecyclic solutions match Chen et al. [12]'s Figure? 2 (but not the dataset's canonical solution) with minor comment differences. indicating possible contamination. In decimal_to sas____t_bbnarrrreeee the generated Parsel solutions often un- successfully rely on statefulness: for example,
GPT-4 with Parsel cannot: decimal_to to_ b_biinarr and decode_cycll
wtt____ttt_remmiiiie calls gelculaae_remaindd and 1ecima,,, but decimte cannot mutate an integer.
Most crucially, these experiments indicate that, even when given the same set of generated tests and program generation budget and selecting only one best solution, Parsel significantly increases the probability that the solution is correct on the ground-truth set of tests.

---

Comparison to human expert. In our fully automated pipeline, an LLM generates Parsel program, which Parsel attempts to synthesize into a solution. We also evaluated how well an expert Parsel user would perform by directly writing Parsel and interacting with the Parsel synthesizer. As a case study, one of our authors with significant prior experience competitive programming was presented with 10 randomly-selectter competition-level Codeforces problems from the APPS dataset, writing Parsel from scratch in order to solve the problems The participant successfully solved the problems within a 6-hour time frame.
In comparison, when GPT-3 generated Parsel solutions to these problems, it had a success rate of out of 10 problems with 8 attempts per problem (of course, in much shorter time-frame), This result suggests that, given suitable decomposition, the Parsel synthesizer can effectively generate complete correct solutions to hard problems thus, a major point for improvement in the fully automated pipeline lies in the first stage (Parsel generation). other words, improving the ability of models to decompose tasks into Parsel programs is key bottleneck and is an important direction for future work.
While the participant could solve problems that GPT-3 could not, the participant found some aspects of working with Parsel counterintuitive. For example, one of the most effective ways to provide additional details ensure working solution was write additional tests rather than to clarify the meaning in the function descriptions. Given the stochasticity of language model generation, there was concern that changing the description of child function could break its parent however, in practice, this seemed rare. We include the participant's 's solutions and the associated problems in Appendix Q.
Chained components. Chen et al. [12] high- light in their discussion of limitations that lan- guage models fail to produce code that requires the simple composition of building blocks. We replicate their experiment with Parsel, using the
100%
75%
same docstring and providing the same descrip-
Accuracy
tions as function descriptions. In Fig. 6, we
50%
visualize how Parsel solves this. We find that
as the number of required components grows, even interchanging the components of only two complete programs (1x2) solves more problems than Codex solves with 16 programs. This illus- trates a key point: assuming any independence, the complete set of combinatorial combinations of n implementations of program's functions is clearly more likely to be correct than sam- ples from that same set. Moreover, this suggests that framework like Parsel may support in- creasingly complex and abstracted programs as language models improve.
25%
0%
Number of Chained Components
1x16
1x8
1xc
Ix2
Ixl
Codex (Orig.)
Codex (Curs)
Codex (611)
Figure 6: ponents. Parsel performance is shown as 1xk where & the number of complete programs sam- pled. Orig and Curr are the original [12] and cur- rent Codex results, respectively. Codex (@ 16) cor- responds to the pass rate with 16 programs.
Pass rate vs number of chained com-
3.2 Robotic Planning in VirtualHome
We perform a study on VirtualHome [50] to demonstrate that Parsel can also be used for complex robotic planning. VirtualHome is simulation environment consisting of households with various interactive objects and agents. VirtualHome includes a small set of permissible actions with strict grammar- tasks like "paint ceiling" may require multiple levels of decomposition, e.g., finding and collecting specific painting supplies, finding and using a ladder, and using the painting supplies, each requiring further decomposition.
To test the effectiveness of Parsel in this domain, we investigate whether Parsel could generate programs to solve tasks in the VirtualHome environment, while using the environment to provide feedback on whether the plan is executable. Specifically, we use Parsel generate a Python program that can generate action plans in natural language similar to ones used in Huang et al. [28]. In each specified constraint, the produced natural language action plan is translated to formal VirtualHome instructions with minimal regex matching and tested executability. If the instructions can be successfully executed, they are considered valid- however, a potential enhancement could be the inclusion of object-relational constraints on the subsequent state of the world. We include an example of Parsel program that successfully executed and decomposed a task in VirtualHome in Figure 2. Note we also used a header describing a valid action plan, shown in Figure A.45,
7

---

However, as pointed out by [28], while it is easy to check plan executabilitty, it is harder to check correctness, because there are generally many valid ways of accomplishing realistic tasks. Thus, like Huang et al. [28], in order to evaluate the accuracy of the executable plans, we perform human study. Specifically, we ran two surveys on Prolific [45] where we asked 20 participants to make five rankings each, for total of 100 rankings per survey. In one survey, we asked participants to rank set of solutions by how accurately each solution accomplishes the task while in another we asked about how understandable the solution was. Two versions of distinct Parsel solutions were shown (where multiple executable Parsel solutions were available), one which included the indented function names used solve the tasks alongside their seep- solutions, and one which only included step-by- step output. We compared both Parsel solutions to an also-executable baseline solution, based on Huang et al. [28]. We include more details about the survey format and executability in Appendix P.
Humans ranked the Parsel solutions as more ac- curate than the baseline. In each ranking, both the indented and non-indented Parsel solutions were consistently ranked higher than the base- line. In accuracy, standard Parsel solutions (as well indented solutions) were identified as
80%
Codex
Parsel
Proferencn Probability
60%
more accurate than the baseline solutions in 69%
of comparisons, more than twice often as the baseline. In clarity, the standard Parsel solution was 70% more likely to be preferred over the baseline while the indented Parsel solution was 50% more likely to be preferred compared to the baseline. There was no notable difference between indented and non-indented Parsel solu- tions in either accuracy or clarity. Specifically, note that all of these comparisons are reported pairwise, and Figure 7 compares the rankings given the mon-hierarrchical Parsel-generated plan and the Codex- sedex--eeeeatedd solution.
40%
20%
0%
Accuracy
Clarity
Figure 7:
Robotic plan comparison. Parsel- generated robotic plans were consistently selected more accurate and clear when compared to a di- rect generation approach like in Huang et al. [28].
In essence, participants did not appear to pre- fer either Parsel plan format over the other, but given choice between one Parsel-generated plan and its corresponding be more accurate and clearer.
plan, they typically considered the Parsel-generated plan
4 Related Works
Step-by-step problem solving with LLMs. Many works show that step-by-step reasoning benefits LLM performance [51, 54, 42, 60, 37, 34] and correspondingly, that this performance can be improved with guidance and tool use [71, 68, 63, 59, 22]. Acquaviva al. [2] encouragingly showed that humans, when asked to explain how to solve problems in the Abstract Reasoning Corpus [14], tended to provide step-by-step hierarchical descriptions with many verification steps. Moreover, Wies et al. [61] presents theoretical argument showing problems that can be learned efficiently if decomposed but require exponentially many examples w.r.t. length not decomposed.
Program synthesis. Program synthesis the long-standing challenge of generating programs from high-level specifications [26], such input-output examples [7, 25] and/or natural language descriptions [52, 65, 19]. Program synthesizers typically search the exponentially large space of programs. Consequently, synthesizing large, complex programs remains an open challenge. Recently, library learning has shown way to make progress: even complex programs can be short in terms of the right high-level library. turn, this library can be progressively induced from solutions to simpler synthesis problems. This idea is embodied in DreamCoder [23, 9]. Library learning requires a rich distribution of related tasks so that patterns emerge from solutions to simple problems. Patterns are abstracted into useful library functions, enabling short solutions to more complex problems. Parsel also aims to synthesize complex programs by decomposing them. However, Parsel programs specify decompositions, so family of related tasks is not required.
8

---

033
03
APPS Comperiion Pass Haree
APPS Campersion Pars Rtaee
mx2
0.3
92
01
Son
0.
00 06
Bant
0.0
0.5
1.0
1.5
2.0
1.5
2.0
2.5
Log, Parsel Program Samples
Log Implemeenatton Sumples
Figure 8: Scaling performance. The probability of passing an APPS competition-level problem increases quadratically with respect to the log of the number of Parsel programs sampled (left) and the number of implementations sampled (right).
LLMs for formal environment multi-step planning. Also encouragingly, several existing works can be expressed in Parsel. For example, Huang et al. [28] and Brohan et al. [10] showed that language models can automatically generate step-by-step algorithms for robotic agents in language. In both cases, the generated language corresponds directly to pre-implemented low-level robotic abilities. This could be expressed by providing a task description and constraints evaluating that the high-level task was completed successfully. In addition, Jiang et al. [30] proposed framework to generate formal proof' in formal theorem- peroving languages from informal proofs by first generating an intermediate natural language proof sketch. This could be expressed in Parsel by generating each sketch step as a function and using formal verification for each lemma as the Parsel validation step.
Programming languages and frameworks incorporating language models. Other works have explored programming languages that incorporate language models. For example. Cheng et al. [13] explored the introduction of a magguage-model-baane evaluation function, which would allow f('loorh America?', ?U.S.") to automatically return 'yes' by referencing the knowledge of the language model, and showed that they could also generate programs using this tool with language model and Beurer-Kellner et al. [8] explored a related SQL-style LLM-querying language. In addition, Dohan et al. [20] presents an secrenccefocuseed framework for language models more broadly for probabilistic graphical models composed of language model actions. Unlike LM Cascades [20], we primarily focus the constrained generation of programs, instead of leveraging language models as functions within a particular program.
Testing code language model outputs. Related works have explored the capacity of assert statements to constrain the generation space of code LLMs on functions [6, 12, 35]. The automatic generation of unit tests in Chen et al. [11] allowed them to filter many programs before performing final evaluations, significantly improving the pass rate per evaluation. CodeT [11] applies a language model to generate large number of tests, presuming that some of them will be incorrect. However, instead of simply selecting the program passing the most tests as correct, CodeT groups together generated programs by the subset of the tests that they pass - it then returns any program from the group with the most tests passed in total [11]. Chen et al. [11] intuitively motivates this by the Anna Karenina principle: "Happy families are all alike; every unhappy family is unhappy in its own way."
Notably, both the number of final evaluations and the sample budget are important, and we find that combining Parsel with automatic test generation improves performance given fixed sample and evaluation budget. In addition, Merrill et al. [38] proves essential constraints on what can be learned from assertions alone and, more crucially, what cannot.
5 Discussion and Limitations
We note that Parsel has important limitations, largely stemming from its dependence on closed LLMs. First, LLMs naturally underperform on languages underrepresented in their training data, like Parsel, affecting the quality and reliability of the generated code, and these closed models do not offer a training API. In addition, reliance on Codex and GPT-4 introduces vulnerabilities due to potential abrupt changes in behavior since this project's start, access to Codex (which is free) has become much more limited and the much-better GPT-4 is also much more expensive. We unfortunately found a 2.7B CodeGen model [39], evaluated like Codex on APPS, solved no problems. However, we anticipate that improvements in open-source code LLMs will mitigate these issues.

---

Despite the limitations, elaborated in Appendix B, and the challenges of using a language model to generate a language that it has never seen before, the generated Parsel was able to implement robust algorithmic reasoning. There are a few natural questions that arise from this work. How robust Parsel to the language used to specify the problem? When solving hard problems, is it better to increase the number of Parsel programs sampled or the number of program implementations sampled? We visualize Parsel's performance on the explored subset of APPS in Figure 8 to try to investigate some of these questions. In general, it appears that the probability of passing increased quadratically (R² 20.99 for all curves) with respect to the log of both the number of Parsel programs sampled and the number of implementations sampled. Clearly, since the pass rate is bounded between 0 and 1, this trend cannot continue indefinitely. However, given the rate limit associated with calls to the Codex API (officially, 40,000 tokens 20 requests per minute, but in practice, we consistently ran into the rate limit with = 10% of that usage), we were not able to identify the inflection point. Li et al. [35] indicated the pass rate curves become log-linear, but cannot guarantee this holds for Parsel.
Furthermore, we highlight that the question we (and, in our view, most prior work) were looking at in our APPS experiments is, given hard problems and limited by one's generation budget, what is the chance finding a correct solution? However, if one instead views each test as a successive submission, where any failure is comparable to crash in production, one would likely take an approach like the one in our HumanEval test generation experiments, one that uses interpreter feedback to revise solutions, perhaps even one that uses the language model to simulate the result of tests. Both interpretations are important, but they highlight different concerns: even if one can guarantee success upon submission given trillion generated tokens, this has limited practical applicability. A method's ability to efficiently generate reasonable solutions in the first place is one key bottleneck, and assuming an imperfect model, the ability to identify them is another.
Finally, we highlight that Parsel is already capable of synthesizing larger, more complex programs. For reference, we include working Lisp interpreter in Appendix I, based on Norvig [41]. which we translated to Parsel with 21 functions. We make sure to include no explicit references to Lisp in the Parsel code and provide a header to tell Parsel to keep track of environments as dictionaries. However, this is clearly an imperfect substitute for a true oriented programming implementation, and we believe adding better object-oriented features to Parsel would be valuable future direction.
6 Conclusion
We hope that Parsel provides broadly useful framework for several groups: for programmers, Parsel should provide language for robust code generation without the need to evaluate the underlying code; for students, Parsel should allow the teaching of algorithmic reasoning with less emphasis on syntax and more emphasis on problcm-solving, similarly to a mathematics curriculum; for language models, Parsel should facilitate hierarchical task decomposition.
Ultimately, as we discuss in detail in Appendix C, Parsel has many natural extensions building on prior work in code synthesis from automatic test case generation [17, 12], reranking solutions by model-judged quality [69], more clever recursive decomposition [49], bootstrapping increasingly complex programs [4, 43, 68], generating language model prompts as part of target language [20, 31]. As we discuss in Appendix D, we also envision that Parsel may be useful for theorem proving. Thus, Parsel helps fill the gap between reasoning and execution, providing a new approach to complex, hicrarchical reasoning tasks for language models.
Acknowledgements
We would like to thank Jesse Mu, Tianyi Zhang, Rose E. Wang, Allen Nie, Ben Prystawski, Xindi Wu, Fan- Yun Sun, Isaac Kauvar, Xi Jia Zhou, John Thickstun, and Shikhar Murty for their helpful feedback, as well as Rishi Bommasani for highlighting highly relevant works. We also thank the Stanford HAI-Google collaboration for their Cloud Credit grant. Qian Huang is supported by an Open Philanthropy AI fellowship. Gabriel Poesia is supported by a Stanford Interdisciplinary Graduate Fellowship. addition, this work was partially supported by National Science Foundation Grant No. 2302701 and National Science Foundation Expeditions Grant No. 1918771.
10

---

References
[1] M. Abadi, A. Agarwal, Barham, Brevdo, Z. Chen, C. Citro, G. S. Corrado, A. Davis,
J. Dean, M. Devin, S. Ghemawat, I. Goodfellow, A. Harp, G. Irving, M. Isard, Y. Jia, R. Joze- fowiez, L. Kaiser, M. Kudlur, Levenberg, D. Mané, R. Monga, S. Moore, D. Murray, C. Olah, M. Schuster, J. Shlens, B. Steiner, Sutskever, K. Talwar, P. Tucker, V. Vanhoucke, V. Vasudevan, F. Viégas, O. Vinyals, Warden, M. Wattenberg, M. Wicke, Y. Yu, and X. Zheng. TensorFlow: Large-scale machine learning heterogeneous systems, 2015. URL https://www http://wwwwwt...r..teeeee tensorflos org/ Software available from tensorflow.org
[2] S. Acquaviva, Y. Pu, M. Kryven, T. Sechopoulos, C. Wong, G. E. Ecanow, M. Nye, M. H. Tessler, and J. B. Tenenbaum. Communicating natural programs to humans and machines.
NeurIPS, 2022.
[3] C. Anil, Y. Wu, A. Andreassen, A. Lewkowycz, V. Misra, V. V. Ramasesh, A. Slone, G. Gur- Ari, E. Dyer, and Neyshabur. Exploring length generalization large language models, In Advances in Neural Information Processing Systems.
[4] Anthony, Z. Tian, and D. Barber. Thinking fast and slow with deep learning and tree search. Advances in Neural Information Processing Systems, 30, 2017.
[5] B. Athiwaratkun, S. K. Gouda, Z. Wang, X. Li, Y. Tian, M. Tan, W. U. Ahmad, S. Wang, Q Sun, M. Shang, et al. Multi-lingual evaluation of code generation models. arXiv preprint arXiv:2210. 14866, 2022.
[6] Austin, A. Odena, M. Nye, M. Bosma, H. Michalewski, D. Dohan, E. Jiang, C. Cai, M. Terry, Q. Le, et al. Program synthesis with large language models. arXiv preprint arXiv:2 (iti::208.0073330 07732,
2021.
[7] M. A. Bauer. Programming by examples. Artificial Intelligence, 12(1):1-21, 1979.
[8] L. Beurer-Kellner, M. Fischer, and M. Vechev. Prompting is programming: A query language for large language models. arXiv preprint arXiv:22/2. 0it::22/2.00944 2022.
[9] M. Bowers, T. X. Olausson, C. Wong, G. Grand, J. B. Tenenbaum, K. Ellis, and A. Solar-Lezama. Top-down synthesis for library learning. POPL, 2023.
[10] A. Brohan, Y. Chebotar, C. Finn, K. Hausman, A. Herzog, D. Ho, J. Ibarz, A. Irpan, E. Jang, R. Julian, et al. Do as can, not as say: Grounding language in robotic affordances. In 6th Annual Conference Robot Learning, 2022.
[11] B. Chen, F. Zhang, A. Nguyen, D. Zan, Z. L.n, J.-G. Lou, and W. Chen. Codet: Code generation with generated tests. arXiv preprint ar Xrv:v:2207.1000 10397 2022.
[12] M. Chen, J. Tworek, H. Jun, Q. Yuan, H. P. d. O. Pinto, J. Kaplan, H. Edwards, Y. Burda, N. Joseph, G. Brockman, al. Evaluating large language models trained on code. arXiv
preprint arXiv:2107.03374 2021.
[13] Z. Cheng, T. Xie, P. Shi, C. Li, R. Nadkarni, Y. Hu, C. Xiong, D. Radev, M. Ostendorf, L. Zettle- moyer, et al. Binding language models in symbolic languages. arXiv preprint arXiv:2210.02877 2022.
[14] F. Chollet. On the measure of intelligence. arXiv preprint arXiv:
2019.
[15] K. Cobbe, Kosaraju, M. Bavarian, Hilton, R. Nakano, C. Hesse, and J. Schulman. Training verifiers to solve math word problems. arXiv preprint arXiv:2110. 14168, 2021.
[16] J. Cocke and K. Kennedy. An algorithm for reduction of operator strength. Communications of the ACM, 20(1 1):850 -8660-566,,00-- 1977.
[17] F. Daka and G. Fraser. A survey on unit testing practices and problems. In 2014 IEEE 25th International Symposium on Software Reliability Engineering, pages 201-211. IEEE, 2014.
[18) P. Denny, V. Kumar, and N. Giacaman. Conversing with copilot: Exploring prompt engineering for solving es1 problems using natural language. SIGCSE, 2022.
[19] A. Desai, S. Gulwani, V. Hingorani. N. Jain, A. Karkare, M. Marron, and S. Roy. Program synthesis using natural language. In Proceedings of the 38th International Conference on Software Engineering, pages 345-356, 2016.
[20] D. Dohan, W. Xu, A. Lewkowycz, J. Austin, D. Bieber, R. G. Lopes, Y. Wu, H. Michalewski, R. A. Saurous, Sohl-Dickstein, et al. Language model cascades. arXiv preprint 2022.
11

---

[21] N. Du, Y. Huang, A. M. Dai, S. Tong, D. Lepikhin, Y. Xu, M. Krikun, Y. Zhou, A. W. Yu, O. Firat, al. Glam: Efficient scaling of language models with mixture-of-ene -f-exterss In International Conference on Machine Learning, pages 5547-5569. PMLR, 2022.
[22] D. Dua, S. Gupta, S. Singh, and M. Gardner. Successive prompting for decomposing complex questions. arXiv preprint arXiv:2212. 040992............ 2022.
[23] K. Ellis, C. Wong, M. Nye. M. Sablé-Meyer. L. Morales, Hewitt, L. Cary, A. Solar-Lezama, and J. B. Tenenbaum. Dreamcoder: Bootstrapping inductive program synthesis with wake- sleep library learning. In Proceedings of the 42nd acm sigplan international conference on programming language design and implementation, pages 835-850, 2021.
[24] M. Games. The fantastic combinations of john conway's 's new solitaire game "life" by martin gardner. Scientific American, 223:120-122 1970.
[25] S. Gulwani. Programming by examples. Dependable Software Systems Engineering, 45(377):
3-15, 2016.
[26] S. Gulwani, O. Polozov, R. Singh, et al. Program synthesis. Foundations and Trends in Programming Languages, 4(1-2):1-119) 2017.
[27] D. Hendrycks, S. Basart, S. Kadavath, M. Mazeika, A. Arora, E. Guo, C. Burns, S. Puranik, H. He, D. Song, et al. Measuring coding challenge competence with apps. Advances in Neural Information Processing Systems, 2021.
[28] W. Huang, P. Abbeel, D. Pathak, and I. Mordatch. Language models as zero-shot planners: Extracting actionable knowledge for embodied agents. arXiv preprint arXiv:2201.072 002007, 2022.
[29] B. Ibarz, V. Kurin, G. Papamakarios, K. Nikiforou, M. Bennani, R. Csordás, A. Dudzik, M. Bošnjak, A. Vitvitskyi, Y. Rubanova, et al. A generalist neural algorithmic learner. LoG, 2022.
[30] A. Q. Jiang. Welleck, Zhou, W. Li, J. Liu, M. Jamnik, Lacroix, Y. Wu, and G. Lample. Draft, sketch, and prove: Guiding formal theorem provers with informal proofs. arXiv preprint arXiv:2210. 12283, 2022.
[31] O. Khattab, K. Santhanam, X. L. Li, D. Hall, P. Liang, C. Potts, and M. Zaharia. Demonstrate- search-predict: Composing retrieval and language models for knowledge-intensive nip. arXiv preprint Xrx: 140244 2022.
[32] Kojima, S. S. Gu, M. Reid, Y. Matsuo, and Y. Iwasawa. Large language models are zero-shot reasoners. arXiv preprint arXiv:2205. /9/16, 2022.
[33] S. Kulal, P. Pasupat, K. Chandra, M. Lee, O. Padon. A. Aiken, and P. S. Liang. Spoc: Search- based pscudocode to code. Advances in Neural Information Processing Systems, 32, 2019.
[34] A. K. Lampinen, I. Dasgupta, S. C. Chan, K. Matthewson, M. H. Tessler, A. Creswell, J. L.. McClelland, J. X. Wang, and F. Hill. Can language models learn from explanations in context? arXiv preprint arXiv:2204. 023399, 2022.
[35] Y. Li, D. Choi, J. Chung, N. Kushman, J. Schrittwieser, R. Leblond, T. Eccles, J. Keeling, F. Gimeno, A. Dal Lago, et al. Competition-level code generation with alphacode. Science, 378 (6624):1022-1097, 2022.
[36] P. Liang, R. Bommasani, T. Lee, D. Tsipras, D. Soylu, M. Yasunaga, Y. Zhang, D. Narayanan, Y. Wu, A. Kumar, et al. Holistic evaluation of language models. arXiv preprint arXiv:2211.09110 2022.
[37] A. Marasović, I. Beltagy, D. Downey, and M. E. Peters. Few-shot self-rationalization with natural language prompts. arXiv preprint arXiv:2111.08284 2021.
[38] W. Merrill, Y. Goldberg, R. Schwartz, and N. A. Smith. Provable limitations of acquiring meaning from ungrounded form: What will future language models understand? Transactions of the Association for Computational Linguistics, 9: 9:1047-1060, 2021.
[39] E. Nijkamp, B. Pang, H. Hayashi, L. Tu, H. Wang, Y. Zhou, S. Savarese, and C. Xiong. Codegen: An open large language model for code with multi-turn program synthesis. arXiv preprint ar XrXiv:2203.13477 2022.
[40] F. Nijkamp, B. Pang, H. Hayashi, L. Tu, H. Wang, Y. Zhou, S. Savarese, and C. Xiong. conversational paradigm for program synthesis. arXiv preprint arXiv:2203.13477 2022.
12

---

[41] P. Norvig. How to write a Lisp interpreter (in Python), 2010. URL http://norvigg com/ 1ispy .html.
[42] M. Nye, A. J. Andreassen, G. Gur-Ari, H. Michalewski, Austin, D. Bieber, D. Dohan,
A. Lewkowycz, M. Bosma, D. Luan, et al. Show your work: Scratchpads for intermediate computation with language models. arXiv preprint arXiv:2//2.00 14, 2021.
[43] A. Odena, K. Shi, D. Bieber. R. Singh, C. Sutton, and H. Dai. Bustle: Bottom-up program synthesis through learning guided exploration. ICLR, 2021.
[44] OpenAl. Gpt-4 technical report. arXiv, 2023.
[45] S. Palan and C. Schitter. Prolific. ac-a subject pool for online experiments. Journal of Behavioral and Experimental Finance, 17:22-27, 2018.
[46] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, 7. Lin,
N. Gimelshein, L. Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32, 2019.
[47] N. Perry, M. Srivastava, D. Kumar, and D. Boneh. Do users write more insecure code with ai assistants? arXiv preprint arXiv:2211.03622 2022.
[48] G. Poesia, A. Polozov, V. Le, A. Tiwari, G. Soares, C. Meek, and S. Gulwani. Synchromesh: Reliable code generation from pre-trained language models. In International Conference on Learning Representations, 2022.
[49] S. Polu and I. Sutskever. Generative language modeling for automated theorem proving. arXiv preprint arXiv:2009.08: 03393, 2020.
[50] X. Puig, K. Ra, M. Boben, J. Li, T. Wang. S. Fidler, and A. Torralba. Virtualhome: Simulating household activities via programs. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 8494-8502, 2018.
[51] N. F. Rajani, B. McCann, C. Xiong, and R. Socher. Explain yourself! leveraging language models for commonsense reasoning. ACI, 2019.
[52] M. Raza, S. Gulwani, and N. Milic-Frayllngg Compositional program synthesis from natural lan- guage and examples. In Eventy-Fourthh International Joint Conference on Artificial Intelligence, 2015.
[53] G. Sandoval, H. Pearce, T. Nys, R. Karri, B. Dolan-Gavitt, and S. Garg. Security implications of large language model code assistants: A user study. arXiv preprint arXiv:2208.09727, 2022.
[54] V. Shwartz, P. West, R. L. Bras, C. Bhagavatula, and Y. Choi. Unsupervised commonsense question answering with telk-talk. EMNLP 2020, 2020.
[55] H. A. Simon and A. Newell. Human problem solving: The state of the theory in 1970. American psychologist, 26(2): 145, 1971.
[56] I. Singh, V. Blukis, A. Mousavian, A. Goyal, D. Xu, J. Tremblay, D. Fox, J. Thomason, and A. Garg. Progprompt: Generating situated robot task plans using large language models. arXiv preprint arXiv:2209. 11302, 2022.
[57] A. Stuhlmüller, J. Reppert, and L. Stebbing. Factored cognition primer. https://primes: ought. org, 2022.
[58] M. Tabachnyk and S. Nikolov, MI-enhanced code completion improves developer productivity, 2022.
[59] J. Uesato, N. Kushman, R. Kumar, F. Song, N. Siegel, L. Wang, A. Creswell, G. Irving, and
I. Higgins. Solving math word problems with process-and outcome-based feedback. arXiv preprint arXiv:2211.14273 2022.
[60] J. Wei, X. Wang, D. Schuurmans, M. Bosma, E. Chi, Q. Le, and D. Zhou. Chain of thought prompting elicits reasoning large language models. arXiv preprint arXiv:2201.1 / 1903, 2022.
[61] N. Wies, Y. Levine, and A. Shashua. Sub-task decomposition enables learning in sequence to sequence tasks. arXiv preprini arXiv:2204.02889, 2022.
[62] F. F. Xu, U. Alon, G. Neubig, and J. Hellendoorn. A systematic evaluation of large language models of code. In Proceedings of the 6th ACM SIGPLAN International Symposium on Machine Programming, pages 1-10, 2022.
13

---

[63] S. Yao, J. Zhao, D. Yu, N. Du, I. Shafran, K. Narasimhan, and Y. Cao. React: Synergizing reasoning and acting in language models. arXiv preprint arXi::2210.3362,, 2022.
[64] A. Ye, C. Cui, T. Shi, and M. O. Riedl. Neural story planning, 2022. URL https://arxix: httg/abs/2212..7///
[65] Yin and G. Neubig, A syntactic neural model for general-purpose purpose code generation. ACL,
2017.
[66] P. Yin, B. Deng, E. Chen, B. Vasilescu, and G. Neubig. Learning to mine aligned code and natural language pairs from stack overflow. 2018 IEEE/ACM 15th international conference on mining software repositories (MSR), pages 476-486. IEFE, 2018.
[67] P. Yin, W.-D. Li, K. Xiao, A. Rao, Y. Wen, K. Shi, J. Howland, P. Bailey, M. Catasta, H. Michalewski, A. Polozov, and C. Sutton. Natural language code generation in inter- active data science notebooks, 2022. URL https: //an:v//////v////// wrgg/bs////tu//
[68] E. Zelikman, Y. Wu, J. Mu, and N. Goodman. STar: Bootstrapping reasoning with reasoning. In A. H. Oh, A. Agarwal, D. Belgrave, and K. Cho, editors, Advances in Neural Information Processing Systems, 2022. URL. httphttt///ppprreiieee net net/forum? idd= ateaummdddddd_d__dee____ _ELRdggsgI.
[69] Zhang, Yu, B. Hashimoto, M. Lewis, W.-t. Yih, Fried, and Wang. Coder reviewer reranking for code generation. arXiv preprint arXiv:2211. 16490,0169, 2022.
[70] K. Zheng, J. M. Han, and S. Polu. Minif2f: a cross- benchmark for formal olympiad-leve mathematics. ICLR, 2022.
[71] D. Zhou, N. Schärli, L. Hou, J. Wei, N. Scales, X. Wang, D. Schuurmans, O. Bousquet, Q. Le, and E. Chi. Least-to-most prompting enables complex reasoning in large language models. arXiv preprint arXiv:2205. 1002: 2022.
[72] H. Zhou, A. Nova, H. Larochelle, A. Courville, B. Neyshabur, and H. Sedghi. Teaching algorithmic reasoning via in-context learning. arXiv preprint arXiv2211.000666 2022.
14

---

select_ awrporrrttttii... cepertt_iiiiiscciitte roaadoaddssss city airroort_cost):; given matrix representing the of building road between any cities, and list representing the of building an airport a city (where any two cities with airports are connected), return a 1ist of the cities that should have sirports built in them to minimize the total cost of building roads and airports such that all cities are connected. The list should be - sorted in ascending order.
[[3,,,3], [3, [3,3,001, [0,0,0] [0,1,2]
(,0.3,3), [3,0,3], [3,3, (10,0)0.10.1001100
(10,10,3])
(t..),)......11........)....)... [1,4,5] >> [0.1] 2ky_ctty_.coxt(cityyrodddd
city_airport_coet) given list of liste representing the + cost of building road between any two cities, and list representing the of city, return new cost matrix with new node corresponding
building an airport <) to the sky.
[[1,2,3], [1,,,3], [1,,, [4,5,6] -> [[1,2,3,4] 21,2,3,51, (1,2,3,,) [4,5,6,0]] tree (cost_ given 1ist of lists representing the cost of each edge, return adjacency matrix correeponding
minimum spanning true.
[[0,1,3,4], [1,0,2,1000) (0,1,,,,,,11,,,,,,0000) [3,2,0,5],
100,5,0]]
< [[o, 100,1,0,1],, [1,0, (1,00,),,,,,,10 [0,1,0,0] (1,1,,,,,,11,,,,000
Linal_nodd__ae coneectonccctooeeeeeeoeeoooeeeee (adjacency_ mattrii) given list of lists representing adjacency matrix, return list of the nodes connected the final node. Houever, if only node, return an empty list. I00,1,0,11, [1,0,1,0], 10,1,0,01, 01,0,0,011 -> 0
connected
10
11
[1,0,1,0], 11.00,1000000..00000. [0.1.0.1], [10.1.0.11.11..11.00) (1.10. -> [0.2]
Figure A.9: A potential programming assignment focused on problem-solving rather than implemen- tation. The top-level function and asserts would be the assigned problem (which Codex [12] does not seem to be able to solve directly), while the other functions would be the student solution.
A Implications
Parsel natural language compiler framework that bridges the gap between natural language and programming language by allowing programmers to write high-level algorithmic designs in natural language and automatically compiling them into valid code. This has potential benefits for programmers, students, and code language models.
A.1
For Programmers
A.1.1 Current Limitations
First, programming generation language models like Codex continue be constrained primarily to individual functions, rarely exceeding few dozen lines in practice [12, 58). This is still dramatic shift from foundational earlier works, which focused on the association between one line of natural language pseudocode with one line of code [33] or line of text to StackOverflow snippet [66]. Yet, these models perform worse the more unusual the desired functions are, and recent research suggests that people using these language models are more likely to introduce buggy code [47], although this not yet conclusive [53].
A.1.2 Potential Benefits
On the other hand, results from Google and others indicate that professionals can write code more efficiently with large language models, and the benefits will likely only improve as they improve [58]. Since Parsel requires constraints that ensure functions behave as expected, this should encourage bug-free programs and avoid the need for manually checking that specific underlying functions are correct. Furthermore, a function written in Parsel likely be more resilient to breaking changes in the target language, especially syntactic changes (e.g. Python2 to Python3). In addition, natural extension would draw on work on automatic unit testing [17] to suggest additional constraints where behavior is ambiguous between implementations of function. However, for Parsel to be practically useful for real-world programmers, we expect multiple improvements to be necessary, including additional object-oriented features.
15

---

A.2 For Students
A.2.1 Current Limitations
In addition, these language models pose serious challenges for programming pedagogy existing introductory programming classes rely extensively on teaching syntax and how to implement algo- rithms over how to solve problems with them. Free language model-basee tools like Copilot can essentially solve many of these introductory assignments directly, function by function. Those which cannot be solved currently will be increasingly solved [18].
A.2.2 Potential Benefits
Many students currently introduced to programming struggle with learning syntax and debugging unclear compiler or interpreter errors. However, abstracting away these details with a natural-language coding language will likely make learning to code more accessible to students who are just beginning to code. In addition, stepping away from implementation-fooue higher-level problem-solving assignments earlier. These will allow for assignments that are more like those in mathematics. For example, for a problem like Figure A.9, instead of choosing between requiring students to manually implement a problem-solving focused question like the top-level description of, or requiring teaching assistants to manually evaluate the reasoning for correctness, one could ask them implement solution in Parsel.
assignments will allow a focus on
A.3 For Code Language Models
A.3.1 Current Limitations
Traditional programming languages result in some unique challenges for language models. For example, unlike natural languages, traditional programming languages are far less robust to slight variations in wording. In addition, traditional programming languages require many tokens for syntactic details and in some cases, may take many lines to express what can be expressed far more simply in language. For example, referring to shortest-path algorithm Conway's ' game of life takes far fewer tokens than actually implementing them. However, even with fairly nonstandard problems, LLMs have shown remarkable algorithmic generalization ability [36, 62, 3, 72]. One alternative that has been explored is conversational code generation [40, 67]. However, these approaches have primarily focused highly imperative programming structures. Moreover, they still require having the full program in context and do not clearly generalize to complex hierarchical programs with many functions.
A.3.2 Potential Benefits
Parsel allows code language models to stay closer natural language when generating code, which corresponds more closely to their primary source training data. Morcover, it allows complex but standard methods to be described concisely, requiring fewer tokens generate. One exciting additional benefit the potential to generate solutions recursively: if the Parsel compiler is unable to find a solution for set of functions, it should be possible prompt the model define new helper functions. In fact, we find that often the model attempts to reference undefined auxiliary functions when defining complex functions (e.g. "count living__neighbolt and as result support an optional argument where the model can attempt to resolve NameErrors automatically by attempting implement functions.
j)" Conway's 's game of life),
B Limitations
There are several limitations to the current implementation of Parsel. First, Parsel relies on code LLM to generate implementations of individual functions, and the quality of these implementations can vary depending on the specific model used and the complexity particular, Parsel may struggle to generate correct code for individual functions with complex behavior (i.e. functions that Codex cannot implement). However, this can mitigated by decomposing the complex functions into simpler ones that can be implemented more casily.
the function descriptions. In
16

---

The current implementation of Parsel may struggle to generate correct code when there are many functions with complex dependencies or without constraints. This is because the number of im- plementation combinations to consider grows exponentially with the size of the largest strongly connected components. As discussed, this can limit Parsel's performance on some programs. How- ever, approaches like Chen et al. [11] may be able to mitigate this.
Code LLMs, unfortunately, do not perform well on languages underrepresented in their training data- with few examples to learn from, LLMS may struggle to generate correct code in these languages [5]. However, some LLMs can learn new languages in context, allowing them to generate code in languages not in their training data [5]. These limitations can impact the quality and reliability of the code generated with Parsel. In addition, because code LLMs have never been trained on Parsel, this harms their ability to generate it. While we could wait for Parsel to gain widespread adoption, it should also be possible to translate many existing codebases to Parsel. We include proof-of-conepp study in Appendix I..
pmottranslation/eccomiiiaa
In addition, the best open-source code LLMs currently available e.g. PolyCoder [62] substantially underperform Codex, while Codex is competitive with other traditional LLMs on reasoning tasks [36]. However, this dependence on closed models creates a vulnerability, as the providers of closed LLMs can change behavior (e.g. rate limits or model implementations) without warning. Indeed, between the time we started working on Parsel and this version of the paper, OpenAl ended widespread access to Codex, now available only by request.
Because of this, evaluated 2.7B CodeGen model from Nijkamp et al. [39] with Parsel in the same configuration we used when evaluating APPS on Codex (in the 8x16 configuration). We found that it could solve none of the random 25 problems which evaluated it on. However, despite these limitations, the current Parsel implementation has shown promising results in generating correct code for a variety of functions and languages. Many limitations will likely be ameliorated as code LLMs improve.
C Future Work
In the future, we hope to more deeply integrate automatic unit test generation, especially in com- bination with user-provided tests [17, 11]. One method would be to identify edge cases and check whether the set of functions that successfully solve all existing tests disagree on any new tests. This could permit automatic decompasition without exponential growth in implementation combinations. Techniques like those proposed in Zhang et al. [69], which would allow us to rerank set of solutions, could also allow us to search the combinatorial space of solutions more quickly. Relatedly, for the robotic task planning, incorporating asserts at the execution level (e.g. checking whether the agent is close to the microwave, as in Singh et al. [56]) is a promising research direction. Furthermore, evaluating the examples this paper, we found that using the minimum CodeTT score across all consistently effective heuristic to identify good sets of functions. However,
generated functions generating unit tests for all functions when generating Parsel programs instead of generating unit tests for a shared top-level function increases the inference cost from linear in the number of tasks to also being linear in the number of functions and Parsel programs generated. Finding a way to balance this tradeoff would likely be valuable.
In addition, we plan to incorporate ways of varying the "confidence threshold" of the language model. Ensuring that the descriptions are straightforward and unambiguous is important for more critical programs and parts of programs. In addition, when teaching students simpler concepts, requiring them to decompose the task further may be useful.
We would like to integrate value functions allow dccomposition to be done more methodically where no verification is possible. Specifically, automatically decomposing all functions that have not yet been implemented in an SCC is suboptimal and could be improved with model of expected improvement due to expansion, as done for proof expansion in Polu and Sutskever [49]. In addition, when decomposing functions, we would like to permit the model to reference already-define functions (rather than to just define new ones). We might even use the code language model to determine which function to evaluate next. Further, we aim to support more general reward functions for function implementations where multiple may be valid but we rank implementations based on a desired feature. These "soft" constraints may also allow new Parsel uses, e.g. planning stories in natural language [64].
17

---

then 1imms 7.9.tiplsen_c.ffe q: Peop):
TONOENE: q. A Pu then P. A
9 5 A
intey b.
Lhe and upsrotor in commutative
and_ pad_conmuee (p q: Prop): the and operator commutative
cants with ba.
21. lecoa and, comessele qu Peop)-
A p) A. (g/A 27 (p A Q
scact hg. hp.
show (p A + q p) A (q P + A.P.A q)
P.q. i.q.inples__qu q_pppp qF Prop): 1I A 9, then
pe of Ubu
login
and anttts
9-p. a.p.implies.p_q(p q: Prop): if A P. then
A P
lrme 4.P Leplassssss...mm pueto 4: Peoph:
1f then
X Cuply p-y.inplowssup ),
appky s.p.teplies.s.4) )
+ A
A p 1p A)
bagic
splis, hiright,
12
Figure A.10 Parsel Lean (theorem proving)
Finally, we hope it would be possible to use Parsel as a framework for bootstrapping increasingly complex program generation (e.g. Anthony et [4], Zelikman al. [68], Odena al. [43]). That is, by 1) generating Parsel examples from a purely natural language specification and then reinforcing those which successfully compile, and 2) by reinforcing the model with each successfully compiled component, we would likely be able to iteratively improve performance with an arbitrarily large dataset of examples.
Another feature that would be valuable would be the ability to incorporate multiple base tools with different kinds of specialized models, inspired by Ibarz al. [29] and Dohan et al. [20]. That is, would be valuable to allow a model to determine which target language to use, possibly combining them. For example, for large parts of the Tensorflow and Py'Torch libraries, while their interfaces are written in Python, they depend heavily on large C++ codebases [46, 1J. Relatedly, Cobbe et al. [15] showed that giving language models access to a calculator allowed them to solve more complex math word problems. This, combined with the observation that Parsel could also compile programs by generating language model prompts to be used as part of the program, may potentially allow the automatic generation of task-specific language model cascades [20].
Another noteworthy addition would be the integration of Synchromesh [48]. ensuring that each new word or token generated by the model is actually possible within the grammar of the given formal language and does not violate other semantic constraints.
Ultimately, we hope that this specification for Parsel is a jumping-off point for a new way of thinking about programming and reasoning.
D Theorem Proving in Lean
With the same framework, we can generate proofs in formal theoren-proving languages such as Lean, as in Figure A.10. We include the translated version in the appendix. Note nuance of Lean and theorem-proving languages is that the ability to run Lean on proof with no errors/warnings indicates the proof is correct (but is not guarantee that the proof statement matches our claim in language). Thus, each function in a Lean Parsel proof has an "implicit constraint." This makes it straightforward to identify which informal parts of proof are most difficult explicate. Generally, believe Parsel can be powerful tool for theorem proving.
Yet, we observed important challenges in this context, which we believe are avenues for future work and can be resolved. For example, in datasets such as MiniF2F [70], many proofs require explicit calculations in intermediate steps. That is, many proofs are similar to "Find the minimum value of 9ar sin" x44 for < I < म. Show that it 012.* (from the informal MiniF22 introduced by Jiang et al. [30]). We believe that a dataset of proof statements (in natural and formal language), requiring complex proofs that are more abstract and less dependent on explicit calculations would allow us to better measure progress towards solving difficult theorems we leave this to future work.
2 g
18

---

parcel (progrip tazget, target_Janguae language): syntheeize prograa iron string specitying Parsel progras. paree, progrran(prrrrraa) parse the Farsel progran string to call graph
croate_rot__ode ro: parce parco_line (1ine, currect_node, current, indent) the definition, reference, constraint.
node the function_ for each step up in indentation, eet the current node
function sode, any constraints
its parenta. then,
sara.,dafisitimmllin create nas function node, carrent node.
shild currwnt node's parent, then assige it aa direct child
parse,
add
to ascestor
parse, coustraint (line): add constraint the mode's constroints.
get, Met..eepedency.pee (ranctttunntiioo grnction.graph) -> Hapandescy.gragke taking function. gruph, create copy where
without
asserts also depend on their parents inless the target language implicisly testa all fimetions.
ddetitty_ttrongly wow.ee/eedoccceeed.oooooo comneceed. (orpenttteeeeeeeeccy graph): return 500s of the dependency graph and edges between the 800s.
synthesizo, seclece, scc_groph): find implenestation
900, starting with depeadencier, then generating possible ixplenectations of Soc functions, then rinding an ixplementation conbination eatinfying the < functiona' conatreinta
syathssizo, chccdrennacc,, acc_graph): ayuthes ine any this dapands on syntheaise ise son
the isplometacion string.
12
u, children, intreniippllaaaationn atr:: each function the proupt language uodel generate a imp1 cxentations of each function starting with the implexontation string of the B001s children. tolvo.contraantee con.ernttttttssee in..pleeestattnnn)::
generate, suplemetacionate
14
the provided cometraints of function the evaluate
shuffled 1ist direct_ prrect.,rodact.. implemetaationott ixplenestattoone): return the direct product of the list of 1ists of
direct product ixplommtations with constraiata wiill one passes of thea
15
16
Cenarace_constranntaf (owstrainttahhhuaaia... mf:lle)) tranalate each of the constra inta into an avaluatiio atring idioratic to the targes Language and add these to the list of conbined tmplemmtationss
17
axa)_ inplanmntacion_aty) executor
avaluate an implemmntaaion including constrainta by ranning Barget-language
co_fail(ace, acc acc_graph): raise an ezror highlighting the acc shich could be syachesized
Figure A.1I: Pseudocode in the style of Parsel describing how Parsel synthesizes programs. A detailed version including automatic decomposition and automatic infilling is in Figure A.12 of Appendix G. Constraints are left out for clarity e.g. one could define a test function and validate the compilability (or lack thereof) of set of reference Parsel programs.
E
Optimizations
E.1
Caching
We cache responses from the language model with respect to the prompt and language model decoding parameters 1) to reduce the number of queries necessary and 2) to keep the programs generated mostly stable (i.e. a working function should continue working unless this end, when the number of desired implementations increases for a pre-existing query with all other arguments fixed (temperature, number of decoding tokens, etc), we append the additional ones to those already generated.
its children change). To
E.2 Automatic Function Infilling
Sometimes, function generated by a language model may call function that not yet implemented. In this case, we can (optionally) attempt to automatically generate and implement it based on its usage. The function is then incorporated into the call graph as a unit-test-less child of the function which calls it. To avoid infinite recursion and inefficient use of language model quota, we limit the number of times that this process can be applied function.
E.3 Multiprocessing
We use multiprocessing with a user-specified timeout to test many implementation sets in parallel to allow for many fast solutions to be tested alongside slower solutions".
F Parsel Pseudocode
G Parsel Pseudocode
We include longer-form Parsel pseudocode in the style of Parsel. Note this pseudocode does not include backtranslation.
As anticipating the number of steps that a solution will take universally is a version of the halting problem and thus intractable.
19

---

(progran target_languuae. allor, silor,sttofil--aae. aloo__utodecum-Faaee)) coapile progran from string specitying Parsol progras.
parse.progrun (progran); parse Parsel progran string to call graph
(reate_root_noee)) create root mode the current function noda, without mny constraints
parco parco_line(iton currest_node, current, indest) funetion.grap.: for each stop up in indentation, eet the current node parents. then, parss dafinition,
sareo_det:sationn11ee create new function node, make it child of the current node's parent, then aceign 1t az current node.
6
paree_line, to (i(ine) name, azge, description: extract the function naze, argusnts,, optionally returned variablex, and dexcription the form "nara(arge) reta: description" if raturn varishles are prasent wlas mare (arge): description'.
populato fo to_nodo(aare, args, rete, description): populato the nes node's nene, argunests, description, and optionally
parse_ www.rrecceeennne add reference az child of current mode if reference is an ancector a direct child of an ancestor
parae contt (aniintttiii line): add the conatraist to the current node'a constraints.
get_ wt..eeeddmey.grrape (function_graph) -> dependeccy.graph: taking the function graph, create copy where all noden without conetraints also dopend their parests unless target languago ixplicitly teste all functions,
11
strpittyystrrngy__ooomeee httpr//eooocccccooppptteeeee/eee grrph)))___ return B0Cs of the dependency graph and the edges between the
900e:
12
compile_scd coxpile_scc(sce, scc_graah, alourautofill, allov_ auoo_auuddccap): accumulate implexentation string shich colves the current
functios
13
corpill,_childrennenn, acc_graph, allox,antoffll,, :lloc_entot:ccorp): corpill 800x this 80C depanda on and add then to
the implerentation string.
14
coapile_ece
15
Stirect.rrofct___ srreettprodt..iiiieetttai (nptenentariossttn www.eaattrosssiiiiiittttaaaiiiia inplonmtations): return the direct product of the list of lists of
fo_isplereetations
16
generate, iaplenstaaioenssse,, n, children, auplasntation_ets) for each function is the BCC, generate implenestations
function starting with the implerestation string of So0ta childrmn.
17
in_inplanentation
18
fn. in__inpleeentttiin (tt_een node, n): prompt the language model to genorate implmmntations of a function argusente, and returns fodsode's
gonerate_ prerapeeprooptteee (fa_ first prepend string all descriptions,
direct children, is atyle idiouatic for the target language. then, add fn description and function signature.
20
cate_comttreiataaacc,, fa inpiioooonntiinn,, s, allow astoffll, allou, autodecup): taking the provided constraiate of each the direct product. of implemmtaaioon with the constrainta until
function the anc, evaluste abuffledd -)
tranclate each of the constroints into an evaluation string idionatic to the target all of then
21
generate_ www.trattttt language
22
eval_air (aco, inplametationn.ate antaffit)) avaluate an ixplametation including conatraints by running it in underined referance, atterpt
target--anggugg executor. allow,autofill the execution fails sstofill
23
wxec_tepl imnntation woc..teplemnttaiion
(wwpleentttiommmttt attr: run ixplemenaatio,, including cometratsta/tantts, in sarget-liguung specitic executor, returning whether euccesstul
24
srreapt_ sutofill(sce,, inpimetariios_ str, undefined fa. wet._soo_eeeee example): create new function node for the roferenced function, re-attespt
sutafill
25
add__mdafinee_ffffee implasenationnattr undafined_fnumme fnuolllrr, indefined_fn, fnwnddff__ueeeeepppppe create a new function tunction as of ieplenmtation string. prompt the language nodel with the usage axmppl ax the description to ganerate awt of implerentaiione. in.ixplenestatien
which calle
sec
26
27
eval_stz
28
(acc, grc_graph, allou_astaflll, autodeentoee:)pp) allosing autolecorpoiition, atteept decospose. othervise, raine an arror highlighting the nee which could not be compiled
29
atterpt, sutodecomppcc.c. scc_graph, allov, autofill, alles, sutoocccpc))) pronpt language xodel deconpose each eeeppleddnddd funchion node.
30
prompt_zodell ntn_n prompt the language model, acktng it to gonerate a "fn_nmmo(arg): desc" for each cubfunction necessary implement the function node. these functions the including possible legl ieplasmtationa for each.
31
fn_ixplamentetion
32
compile,nce
33
raice, ceror(occ): raise error that Parsel could compile the acc
Figure 12: Longer pseudocode of Parsel, including automatic infilling and automatic decomposi- tion.
20

---

Algorithm 1: Parsel program synthesis corresponds to short Parsel pscudocode.
Input: A string program specifying Parsel program and a harget_language-
Output: Synthesized program
Function Parsel (program, target, languege);
functionn garppphhhggphhhhhhhoo Paree)rogran(progrra)
dependency..ge graph gec +- GetDependencyôrappi www.tionnggraooo targef_language
sees, sen scn_ graph Ident. dddeendenog_rrpple
implementation 4-
foreach scc E PoutOrder/hwversallsccss//
implementathon +- smplementation Syntherize@@llace, http:/mnnneettn-ypttteieeeeloro sca_graph)
return smplementation
F Function SerseProgran(pprorrooe
root +- CreateRootNodeed
current_ _node +- root
current, indentation
foreach line program
line__ie indentation + IndeonationO((iiine))
while line_inden ion__indenaation current current_ surrent_imdentaaioon indentation
current, node current, cone---oddparrr.
current_ indentation == mode Farseline (line, current node)
Function ParseLine (line, carrent_node),
if IsDefattion((in)) then
current pode pode-childen children e Parsebeefnnttion(((nn)))
// Creates a new function node
if [sReference((ine) then
current children ? ArrseReforencellinn) else
Adds reference
current node constraints PareeConetreintt
Il Adds constraint to current node
Function www.DDDeeeeencyrraaapeee fuuntionnn groph, target_ prrget_languagee
# Convents function call graph into dependency graph.
dependency. grrpph +- CopyOlIf CopyOl[function unction_graphh:
foreach node dependency_gree
do forench child mode. chhiddeein do if ckslddaseerta
then AddDependency(chila node); return dependennwy_gragge
I/ Child without assents depends on parent
Function (ynthesizeSOO(nre,, scr_graph);;
impl implementation atr LernttaeeeeCliideemeeeeee scc_groph)
fn_implementaaionn Generatelnpleeeeteee (scc, smplemeenttiinn_ery
implementationn +- (slveConttrointtsseee,, fnr in_implementation if implementttionn valid then
return implementation
F Function Synthee Secheeiieehiine weweeehhhhrreeeeeeeeeeee berr
child imppeemnnttiinns
foreach child sec E soc, wer_ggraphheee. Saanh..GCChhadren((mn do
child child_implent inpd-mmmmmtetniions
otwpr//eeeeeec..eeeeeeeeeeeeeeee ace_ chsid_implementaatinn
return child implementations
Function Gemerate Inpl ementations n, imm.immmettttionntat))))
smpllem implemennations
foreach fn E scc do
on_implementations <- Cemerateiimpeemntttttonnn fn, implementation__er)
return sipllementations
Function SelveConstraintsssdde fn_iimllementations))
combinations +- Inppeerrr ceteiatttioonn__npppppppe Translate of the constraints evalustion string
(ii.impllmentattonn))
Gewersteeonetraaiine (scc)
foreach implementatioon__tr E combinations do
Eval EvalStrraappleeeeee (mmplttt(mmlleeenttttioo
constraints)
return implementation_ssr str;
If Return implementation posses constraints // none are found, raise error
OnPail(sce, scc_graph)
Function Gensraaeeonsttreittaaaaa))
constraints
foreach fn do
fn o__comstraints Ge(Constraintt(fn)
constraints.ctteod httpr//itnttttttoooooooooooooooo wwwpe/eteeeeooooeeneeeeeeoeeeeee /n_constroitnta)
return constroints
21

---

H Parsel Overview (Detailed)
We include more detailed figure outlining Parsel.
Task/Problem
Statement
or
O BBB
Decompose
Program
Natural Language Function Definitions
Parsel
References
Constraints
Language
Compose Solutions
Dependency
Program Smaller Parts (SCCs)
Graph
Dependencies
(intermediate
representation)
Code LM
Parsel Compiler (per SCC)
Combination
Possible Function implementations
Test Implementation
Solution
Figure A.13: Parsel overview (detailed).
I Lisp Interpreter
We include the Parsel code for a minimal Lisp interpreter.
22

---

any dictionary of ('warliva)) pairs, with link to outer anvironent mnv[__ntar'] procedure lambda expression, with body, shich calls eval_exp the body. tx1+t
prouute.roggusspeoggaaaa) Iuitialize standard resalt.
evaluate exprension,, returaing the final
equare
r))? "Cquuree
cpt_earppame,, argo, eny-Bome): Reture new car incide car with zapped to their correspoading azge, and ear the new enris outer etv.
D. ('_outer'; None)
['a"], [1] Paa:: 1, "_outer"; None)
standard, sev (ineliinddde ("rath', 'opa', "sispll__mtts))) anviranent
Schaza standerd procedurea. with
environment and updata it with standard functions.
("oonter::
11
get_oath:): Get dictiouary zapping xath Library function nanes to their functions.
get_ops(): Get dicticnary napping operator symbole to their finctions: +, 4, /, >, 6, 3-, <n
get_sinple__attle math(): det dictienary napping 'abs', "nin', key, arga_list): Return the value of fn,diet tn_diict.eneratrr ( Daay (rargo_liat) in
'not", "round" their functions.
14
apply_ro_dice katp_diict_kk(t__dee Setytt_niictggeeeeaate
standard_emm
15
get_math, 'eart', [d] 2.0 2.0
get_ops, [1,
17
got_sinplo_eata laba", [-1] +2
18
get.rath
got_opa
20
get, get_aispla,mach
expression, *(+ I (+ 2 s))", (r4t; (lanbda x, y: y), tw'; (laxbda + y), "_outer'; None) -> expl_ ear) Evaluate an expression envirocnent return result. Chock list, scring, or ti wwither, and call the corrwsponding function.
22
24
1, CLouter?: Bone)
find(anv,
the value of in inmermost chere appears.
26
Paaia, "Loutarl:Kan Konn)), lat ("outert: "Loster": (omme)),
28
(tat:3, Looueer:(("""de
:None)) 'a" ->
29
string_ env): Beturn find(env, x).
30
"a', ("a":4, "Louter'sMone find
31
list_cmaw(s, anv):
function specified first value Handle first value being quote, dafine, satl, lambda, or otharsize. Return the reaslt.
D'qazee,, 's', ('_oster:; Kone)
34
Pir', True, 1, 2), ('_ouber": None) >>
35
Dastine", f], ('_outer": Mone) Yone
36
get_procadur (parns, body, env): Return procedura which avaluatex body in anviroment with hound to the arge passed the proceduro (in the came order as parns). wal_prraedurw(garree body,
arga):
the avaluating proc(sarga)
Should not be called directly.
[r'), [1v], 'pi', [707, 'r', "r"]), (te7: x, y: y), "pi?: 'Jouter"; None), pooperoceuuee
39
get_enn
41
eval_exp
42
othervice_cared env): Get the procedure by eralusting the firet volue of x, Then, eraluate the argurests and apply
prosedurn
43
[14t, 1, 2], (ter: (lambda y), "_outer!: Hone) ->
eval_oxp
45
eval_exp
not, not__lixt_caaa came(x wnv): Raturn
47
1, 0
48
parco(progran): Read a Schoze expression from string.
te', tokemize(e):: Convert string into 1ist of tolons,, including parens. [211,
50
51
52
+ (2 3)" [*s*, 1el, =e, 12", tel, 137, })*]
53
mne_.fro_tokkmate (tokeen)): Translate tokens to their corresponding atons, using parwscheses for neating lists. PC, '1', 141, "O, 12', 1e", 19', 12?, 1) -> [1, '41, [2, 1e1, 333
54
35
ston(token): Nunbors become numbers; every other token is a scring.
57
58
59
Maste__ist__t__atreeee Convert nested list. into string with neating represented parwnthwasa.
60
*3"
61
[2. 1e, 3]] " 3))"
Figure A.14: Full Lisp interpreter implementation in Parsel, including constraints.
23

---

J Case Study
We include simple example function we could not generate with Codex [12] directly from the top- level description in Figure A.15. The corresponding Python code (included in the appendix) is exactly 58 won-whitespace lines of code, including 17 lines of comments corresponding the descriptions), 2 asserts, and 39 lines implementing the three functions described as well as an automatically generated get_number, of _f__aiivv__co sariiie___el__eeeeeeeeeeeeeeeeee _ew.ll_rround___...me atrs_arrrddd_elll cell function. In fact, using automatic decomposition, as discussed in Subsection R.3, it is not necessary to provide any of the function descriptions besides the top one. The model is (unsurprisingly) able to understand that game_ of life__ inreeiinveriion iteration can be broken down into invert arzay and game_ life iteration.
game _of _f______________ _il___ff_____ laife_inversion inverrsinn_itratiionn (array_ate attty_ttt_ttm_____tt _t)e__)) Takes a board and returns the next iteration of the game of life, but with all values flipped [[0.0.1] [1,0,0] [1,0,0]] [[1,1,1] [1,0,1], (1,,0,1,1111111 [10,1,,,0], 111.0000..1.1.....000000.0011110 10000000000000000000000000001110 game_of_ ttrp:feitttaattiooaaraaaaaattt.
(1.O:A.:)..0...00.111 (1110,.,,,..0.111,,,,,,,. array_at_ wtt.ttti_ttpptus___t._ae Takes a board with + active and inactive colls a list of lists and returns the next iteration of the game of life array_anvereion
inverted_arree array: Invert aquare array by flipping and Figure A.15: An example Parsel program for Python that takes in list of lists representing state of Conway's game of life [24] and returns the next state, with all the values inverted.
K Parsel Prompts
Description: gäven a list of lists representing the cost each edge, return an adjacency matrix corresponding to the minimum spanning true.
def Sinimun_spanningg (rotogstttoccoottttrrttt.
Figure A.16: Codex Prompt for an example leaf node
Description: gáven a list of lista representing the cost building road between any two cities, and a list representing the cost of building an airport in city, return a new cost matrix with a new node corresponding to the sky. Signature: sky_city_comt costy_coosttttt (city_road_ cost, city aity.airpott.cost) from helpers import sky_city_com
# Description: given a list of lists representing the cost of each edge, return an adjacency ) matrix corresponding to the minimum spanning true.
Signature: minimum_ catpruumpppninnggreeee wooattcottmaartii from helpers import minimum_spanning. tree
# Description:
given list of lists representing an adjacency matrix, return a list of the S nodes connected to the final node. Hovever, if only node connected the final node, return empty list.
10 Signature: bacaa_nnod_cconneett (ateettocrtdaaceecycmaaaataa
11 from helpers import
12
13 Description: given matrix representing
of building road between any two cities, and list representing the cost building an airport in city (shere any two cities with sirports are connected), return list the cities that should have airports built in them to minimize the total cost of building roads and airports such that all cities connected. The 1ist should be sorted in ascending order.
14 Uses: sky_city_cost, minimum_ watammppaannnnteeeeeeeee final_node_come node_comnectorrs city_alxport_coot):
15 babeet.arrorrccctieeccc...eeee
Figure A.17: Codex Prompt for example merge node
24

---

Reviever:
explain the function in with much detail possible.
your ene-sentence description, specify the range and domain your function precisely. # Your description should be clear enough that someone could reimplement the function from it.
Author:
Sounds good, here's my one-sentence explanation of {name):
[name)
Figure A.18: Prompt format to generate descriptions for backtranslation
25

---

L APPS Backtranslation
L.1 Backtranslation /decomilling.
We anticipate that there are many programs that LLMs can implement by first generating Parsel code. But, as Parsel is new framework, while language models can sometimes generate Parsel programs with few-shot prompts, it is not syntax they have previously encountered. Thus, we may want to use existing code other languages construct datasets of Parsel programs from other languages. This requires us to first extract the call graph from the code, generate descriptions for each of the functions, and then generate Parsel programs from the graph. This call graph representation is convenient, so is useful to have a bidirectional method to produce graph from Parsel code and to produce Parsel code from the graph.
We filter the dataset to problems with starter code (providing the name of the evaluated function) and unit tests (provided as input-oulput pairs). For those tasks, we select solutions that define and call at least three functions, with at least one over 4 lines long and none over 15 lines.
As proof of concept, show 10 Parsel solutions which could automatically generate from the APPS solutions. We generated the descriptions by prompting Codex to explain each function and its imputs and outputs. From this, Python. We then verify that they are correct by applying the original unit tests as constraints on the root function. As mentioned in Section the Parsel code is substantially shorter in terms of lines of code. We include these in Appendix I..
backtranslation attempt to implement these solutions in
L.2 Examples
We exclude the asserts in these examples for brevity- they correspond to those in the original dataset.
Longest_pallnddrmeeeee (a) Longest_palindron takes string and returns the longest pal padrome
same forwards and check(1i, ri, 8): check takes string a left index 11, and a right index ri, and returns the longest palindrome that starts at before 11 and ends after ri. is_palindrome
is.ppalindromm : is is_pallinrrmm returns True if the string <i backwards, and False otherwise.
Figure A919: Train Problem 1638, Solution 2
26

---

longest__pall longest.palindrome takes string and returns the longest palindrome in def nongest_pallndremeeee
(e)(s)
return
else:
longest =[0]
in range(1en(s))
for j in range (s))
if is_palindrome (check(i, J. s)) and (ch J. s)) len(longest): longest check(i, J, s)
10
11
longest
12
13 # is_palindrome returns True if the string 8 is the same forwards and backwards, and False
- othervise.
14 def is.palindrome(s):
15
len(s)
16
return True
17 elae:
18
return s(0] == s[-1] and is is_palindrome (s[1:-1)
19
20
index 1i, right index ri, returns the longest () palindrome that starts at or before 1i and ends at or after ri.
check takes string s,
21
def check(11, ri, e):
22
while 1i > and ri len(s) and s[1i] s[ri]:
23
25
return a[1i+1:ri]
Figure A.20: Train Problem 1638, Solution
case_id(c_str): case_id takes string and returns string that is either "kebab", "anake", "camel", "none" depending whether the input string is in kabab snake case, camel case, or none
is_snake(s): is_snake takes a string and returns True if the string is snake_case case and False othervise.
is (e_keebb((): is_kebab takes string and returns True if the string is kebab-case string, False othervise.
camee is_camel returns True if the string is not loxercase, does not contain dashes, and does not contain underacores.
Figure A.21: Train Problem 2892, Solution
27

---

case_id id takes string and returns string that is either "kebab", , "enake", "camel",
none" depending whether the input string is kebab case, snake caae, camel case, none of the above.
def case_id(c_str):
if is (s_sna)ecc_strr) == True:
return "snake"
elif (s_kebab(e_str))
return "kebab"
7
elif (c_samel(c_stz) True:
return "camel"
else:
10
return "none"
11
12 # is_snake takes string and returns True if the string is snake_case and False othervise.
13 def (s_))ake(s):
14
s[0] isalpha() and s[0] .illover)) and len(s) for char in s: if char isa..isappha(); if char ())pper(); False elif 1. pass
15
16
17
18
19
20
21
else:
22
return False
23
else:
25
return False
26
27
is_kebab takes string and True if the string kebab-case string, and False
otheruise.
28 is_kebab(s):
29
# if = is empty, False
30
if == ::;
31
False
32
# 8 not a string, False
33
if type(s) I= str:
34
return False
35
# s.lover():
lovercase, False
36
37
return False
38
# if s contains anything other than a-2 False
39
for in 8:
40
(c.isalpha()
1-?);
return False
42
s contains a at the beginning or end, False
43
if =[]] =- )-1 or s[-1] == 7.?;
44
return False
45
contains more
row, False
46
for in range (1en())-1):
47
1f [[i]
and s[i+1] 1-:;
48
return False
49
# othervise, True
return True
51
52
53 1s_camel returns True if the string is not lovercase, does not contain dashes, and does
contain underscores.
54 is_camel(s) (s)
55
return I= s.lower () and a. s.find('_)) == -1 and s. s.find('->) == -1
Figure A.22: Train Problem 2892, Solution
28

---

()) array that are different, and False all numbers the array are the same. find_ 2nd, largest find_2i 2_____d____ largest takes list of numbers and returna the second largest number the list.
filter_ filter_intaarz (arr): filter_int takes an array of integers returns an array integers. sec_ sec_big(a, b): sec_big takes two numbers and returns the smaller of the two.
cort()rr): sort takes an array of numbers and returns sorted array of numbers.
(adi)f((rrr): is_diff takes array of numbers and returns True if there are any two array the aame.
different, False all
array
Figure A.23: Train Problem 3090, Solution 9
# find 2nd_ 2nd_largest takes list of numbers and returns the second largest number in the list. def find_2nd 2ar__2nd___rrgee largest (arr):
if len(arr) -- 1:
arr fillterrinnttt (arr)
if len()rr) == 0:
return None
if len()rr)
return arr [0]
10
arr sort (arr)
11
if is_diff (arr) == False:
13 return None
12
arr (arz) 2]
14
return rea
15
16 filter_ing int takes array of integers and returns array of integers.
17 def filter_int
18
(lanbe type (x) int, arr))
19
20 a sec_big takes two numbers and returns the smaller of the tvo.
21 def sec_big(a, b):
22
return
24 clse:
25
return
26
27
array of numbers returns sorted array of numbers.
28 sort()
29
return sorted(arr)
30
31 is_diff takes array of numbers and True there any numbers in the
32
def is_diff (arr):
33
for in range (Ien(())))))) - 1):
34
if arr[i] arríi 1]:
35
True
return False
Figure A.24: Train Problem 3090, Solution 9
(oopy_aumbera()) (n): happy_numben takes a positive integer n and returns list of all the happy numbers between and n, inclusive.
(imappy_umbbr((( (number): _is_happy_mmin happy number, _umberr takes positive integer and returns True the otherwise.
ssw_ssuurreeaeeeeeeeeuue (aumber): sewu_uquaree takes a non-negative integer and returns the sum < the squares of ita digits.
Figure A.25: Train Problem 3140, Solution
29

---

happy_numbere takes a positive integer n and returns 1ist all the happy numbere - between 1 and n, inclusive.
def (uppy_numbers(n))
for range(1,
_is hww.ppp_umbbbrreeeeeeeppe (1)]
# _i __ htt__paapp_bbbbrrrreeee _number takea positive integer and returns True if the number is a happy number,
- False otheruise.
def sis_happy_number www.nnumerrrn (number): (nmbbrbr)
sure that the number is positive return False
want
number 0:
10
# We want make sure that the number is not 1 number
11
12
return
13
# We want to keep track of the numbers we have used ased_numbers -
14
15
# We want loop through the number
16
while
in seed_numbers,
17
# want to add the number to the list used numbers
18
ssed_aumbers append (number)
19
# We want to find the of the aquares of the digits of the number number __uu__suuree (number)
20
# vant to (number)
number one
22
if number == 1:
23
#t We want to return True return True
24
25
False
return False
27
28 # _ squares takes non-negative integer and returns the sum of the squares of its digits.
29 def _um_mm_ wuwuuuuuuuuuuueeeee (number):
30
raise ValueError
32
elae:
33
number str (number)
34
for in number:
36
sum += int int(i) ** 2 return sun
37
Figure A.26: Train Problem 3140, Solution
if prime between and 563, is-prime(n): is-prime takes a positive integer n and returns True if n is prime and False C) otherwise.
vilson(n): am_i_uilson
inclusive, and False otherwise.
factorial(n): factorial(n) returns the product of all integers from to n, inclusive.
Figure A.27: Train Problem 3229, Solution 26
30

---

It am (n) returns True if is a prime number between 2 and 563, inclusive, and False othervise.
def a
is_prime (n) and 2 n and n 563: return (1-1) 1) % (n*+2) =
clse:
False
1e_prime takes positive integer returns True if is prime and False otherwise.
def is-prime(n):
10
if n
11
True n
12
13
return True if n X -- 0: return False
14
15
16
17
return False
18
1 =
19
while i 20
n 0:
22
return False
23
1 +-
24
25
27
28 factorial (n) returns the product of all integers from to n, inclusive.
29
def factorial(n):
30
31 return
32 elae:
33
return (n-1))
Figure A.28: Train Problem 3229, Solution 26
i ____villl((a am_i_wilson takes positive integer and returns True if n is prime and (a -1)! 1 is divisible by a22, and False otherwise. fac(n): fac function that <) integers from 1 n.
positive integer and is.prime(n) is-prime takes a positive integer n and returns True if n is prime and False <) otherwise.
product all
Figure A.29: Train Problem 3229, Solution
31

---

# am w_winoon takes positive integer and returns True if is prime and (n-1)1 is O divisible by n²2, and False otherwise.
def an return is.prime(n)
(fac(n-1) % n**2
# fac is function that takes positive integer and returns the product of all integers - from 1 fn)
if n 0:
return
return (ac(n-1)
if is prime and False otherwise. 10 1s_prime takes positive integer
is.prime(n):
12
if n 2:
13
return True
14
elif
% 0:
15
False
16
for in range(3, int (n=+0.55++1 2):
17
if n X - 0:
18
return False
19
True
Figure A.30: Train Problem 3229, Solution 71
evil (n): evil(n) returns "It's Evil!" if is evil number, otherwise it returns "It's Odious!" The range of evil is the of all integers, and the domain is the of all strings.
evilomete((n): evilometer(s) is generator that yields n times if is even, and yields n // 2 times if n is odd.
Figure A.31: Train Problem 3321, Solution 33
evil(n) returns "It's Evil!" if is an evil number, otherwise it returns "It's Ddious!"
- The range of evil is the set of all integers, and the domain is the set of all strings. def evil(x):
gen evilometer (n)
sun(Listggen)) 2 0: return "It'sLEvil!"
else:
"It'a_ddious!"
evilometer (n) is a generator that yields n times n even, and yielda a 2 times m - 18 odd.
10
def evilemeter(n))
11
while
12
yield n
13
a X 2:
14
n //- 2
15
else:
16
Figure A.32: Train Problem 3321, Solution 33
circular_primeeee (number): sircular_prime takes number and True if it is circular prine, and False othervise.
rotate(1, n): rotate takes 1ist an integer and returns a new 1ist with the last n + elements of the original list moved to the front. is.prime(n): is is-prime returns True if is prime number, and False otherwise.
Figure A.33: Train Problem 3368, Solution
32

---

circular, ppine takea number and True if it is circular prime, and False otherwise.
def circular, prine (aumber):
if is-prime (number) (numbrr))
== False:
return False
for in range (st (number)) -1) number rotate (atr (number), 1) if is-prime (int (number)) = False:
7
return False return True 10
11
12 # rotate takes list and an integer and returns a new list with the last elements of the original 1ist moved the front.
13 rotate(1,
return 1[-n:] 1[:nn]
15
16 is_prime returns True if n is prime number, and False othervise.
17 def is.prime(n):
n 2:
19
return False for in (2nge int(n 0.5) + 1):
20
21
1f n % -- 0:
22
False
return True
Figure A.34: Train Problem 3368, Solution 5
True if is circular prime, and False circular, pecullr.prrimen): circular.prine(1
othervise.
is.prime(n): is-prime takes a number n and returns True if is prime and False if n is not ( prime.
circul_num(n, 1): circul_nus takes integer and integer 1, and returns the integer
that results from moving firet digit result with zeros until has length 1.
end n, padding the
Figure A.35: Train Problem 3368, Solution 6
33

---

circular_priin _priierrpriieee (n) returns True if is circular prime, and False otherwise. def circular, prcular..primen):
n a prime number.
if not is.prime(n): return False
elae:
Get the length of
length (enr (n))
# Get the first digit of n.
10
first_digit str (n) [0]
11
# Get the number of rotations.
12
rotations length # Rotate n.
13
14
while rotations > 0:
15
# Get the new number.
16
circul_num(e (n,,,, length)
17
# Check n a prime number.
18
if not is.prime (n):
19
return False
20
# Decrement the number of rotations. rotations
21
22
return True
23 it is_prime takes number and returns True if n is prime and False if is not prime.
24 def is_prime(n):
25
return True 27 if n % 2 =- or n 2: return False
28
29
for in range (3, int (11 2): only odd numbers
30
== 0:
return False
32
return True
33
34
circul_ takes integer and integer and returns the integer that results from
moving the first digit n to the n, and then padding result with zeros until has length 1.
35
def circul_num(n, 1):
36
str(n) digit n[0]
37
n a[1:] digit
39
n = m.ljust(1, "0")
40
return int (n)
Figure A.36: Train Problem 3368, Solution
List_equareddn, n): list_equared(s, n) returns list of lists of integers, where each sublist contains integer and squared divisors, and the integers the range [m, n] (inclusive).
divisors_list (num): divisors_list takes number and returns a list of all the divisors of < that number.
sum_squares (nuns): sum_squares takes list numbers and the of the squares those numbers.
ieSquarable (mus): isSquarable takes a number returns True if the number is perfect aquare, and False othervise.
Figure A.37: Train Problem 3393, Solution 35
34

---

Alat_squared (m, n) returns a list of lists of integers, where each sublist contains an <) integer and its sum of squared divisors, and the integers are in the range [m, n] inclusive).
(ist_squaredd,,
result 0
for num in range (m, + 1)::
divisors divisors_ (num)
cum_of__quaree aum squares
isSquarable :f_quaree::
result.append ([num, [num, sum_of _f_uueesss) return result
10 divisors_ _isst takes number and returns list of all the divisore of that number.
11 def divisore_listtnunn
12 divisors
13 for in range (1, num + 1):
14
if num i = O:
15
divisors.apperte divisors
16
17
18
19 sum_ _um_equeeeseeeeee takes list of numbers and returns the sum of the aquares of those numbers.
20 sum_aquarea (nums):
sum
22 for in range (1 (nums)):
23 sum += nuns [i]+*2
24
25
26 isSquarable takes number and returns True if the number is perfect square, and False
+ otherwise.
27
def isSquarable (num)
28
(1/2)
root % 0:
30 return True
31 clse:
32
return False
Figure A.38: Train Problem 3393, Solution 35
35

---

M Compiled Examples
36

---

Takes board and returns the next iteration of the game of life, but with all values flipped
game_of_ tame_of_life__e _if_llife______ ltt__ooffee_iveereee__ee
# Your code here
itt._iifeeterationiiieeeeee. aww.aaayarraaattttiie.... return invert_aaray
#return aramaeaaaaaaeerrtr (game_ life, itterttiottntttttet (array_at
Takea a board returne the next iteration of the game life def arrat__araayaararr at_me__t)
return [list (map (lambda 1-x, row)) for row in array_at_time_t) 10
returns the with all values flipped Takes a (araeitt
12 def game_of
13
# The array that will be returned
14
arrsy.at_.tiee...ple___
15
16
Iterate through the rows for in range(0, (0, len aatarray_ttttm__eee
array # The array that will contain the next row next_row []
17
18
19
20
21
# Iterate through the columns of the array for j in rOnge(O, len (em(array_at.ttme_((]] # The number of neighbors num num_neighbore
22
23
24
26
# Iterate through the neighbors of the cell for k in r-nge(-1, 2): for 1 in range (-1, 2):
27
28
29
cell itself
30
x and 0: continue
31
32
33
Check if the neighbor is valid
34
and j
b lan (anraryy_aat att.attttttttt)
35
# If the neighbor is alive, increment the number of neighbors if trmey_at_time_t(1 x] + 1] = num_neighbors
36
37
38
39
# If the cell is alive, check if it should die if array_at at__atmm_ett_t______________te__ = 1:
40
41
num neighorss 2 num_neighbors 3; next_rou. ap))edd
43
else:
44
row append (1)
45
# If the cell is dead, check if it should become alive else:
46
47
num_neighbore
48
next_row. append (1)
49
else:
50
next_row. row. append
52
# Add the next row to array bttiy__ttttmmet_lu_e (apluu__.ppp
53
54
55
Return the array
return array_at_time. www.eat_ttmmttt.. sime_t_plus_1
57
58 assert game_c of life._ leree_ivverioo.ccm
itrroiiitttaaaiiII...... 0, 1], [1, 0, 0], [1, 0, o11) - [[t, 1, 1], [t,
0, 1], [1, 131
assert game_ot ltllllffiiveeere inversion. wwwersiioniteeaaiinnnfe....
1, 0, 01, I1, 0, 01, [1, 0, [o, 1, 1,
011) [[1, o, 1. 11. [o, 1, o, 1). [0. 1, 1. 0]. [1. 6. 0. 11]
Figure A.39: Compilation of the program taking Conway's game of life [24] and returning the next state, with the values inverted. In this case, we use automatic decomposition to generate the two subfunctions of game_od life_ iteration.
37

---

Takes board with active and inactive cells and returna the next iteration of the of life, but with all the values flipped timett))
return htw.ee/.wwrreiio..tttttiaaoorrre
Takes board with active and inactive cells list of lists and returns the next iteration game
array_at_time_ ttt___ttm____pu__11___
for rou in range (Le.t(Brrsy_sttt_ine__)))
array_at_ wtt..ttmeet.ppu.......... for column range (ataeaaatrraaaattteee__eee
10
11
auray_at.timo.t.plueee. [app (Opend
12
for rou in range (laee(aarryyaaa__tinee..0.
13
for column in range (lagee((emaarrryyst_tiieeee (row])))
14
15
row, column) 2: array_at__tmest_.llue [row] [column] =
cautt_poigaborssrrrry.....t
16
17
elif buutt_noighborseerraaa Stt_ayy_____tt_tt______eeeeee
columm) 3:
18
array_at_timm,_
[row] [column] 0
19
20
array_ at time_tiim_____ ttt.tttteeee__eeeeeeeeeeee t.p.ss_tppuuuu_...... [row] [column] -
21
else:
22
(array_at, if count_neighborr (arrayy at__tt__tttttttttee row, column) == array_st_ wttpsmeeee________eeeeeeeeeeeeee [row] [column]
23
return array_at_ ttt.attttttetttplus_t_
25
26 # Invert square array by replacing all 0's with 1ss and vice versa
27 def array_ (arresss
28 inverted_art aarray-rrry
29
for in range (len (array)):
30 inverted_aree append (0)
31
for in range (aeray (i])):
32
inverted_arzer [1] append array[ll (j))
return anverted_array
34
35 4
36 def hww.inieigbborerrry..t......
column)
37
38
for in range (rou-1, row+2):
39
for in sange(colunn11 column+2):
40
if i == row and == column:
or
43
continue
44
if i > (array_aat atmetem__tmm or >- (er atmmeee__ttttme____eeeee [o]):
45
continue
46
array_at_time [[]]
47
count
48
return count
49
50
assert game_of wf_.offleeeeeeeeeee uff_iife_nnn ietg_ivvvrrionnttrattttt ([[O, 0, 1], [1, 0, 0], [1, 0, 011) [[1, 1, 1),
0, 10, [1, 1, 13] 52 assert game_o of_oof....f... life_ inversion_ inwersion_iteratioonn itteatiin ([[o, 1, 0, 0], [1, 0, 1, 01.
[1, 0, 0, 1], [0, 1, 1,
o11) - [[1, 1, 1], [o, 1, 0, 1], [o, 1, 1, 0], [1, 0, 0, 111
53
54 assert game_ot ies_life_tteration [[o, 0, 1), [1, 0), [1, 031) [[o, 0, 0], [0, 0], [0.
() 0, 0)]
55 assert game of f.f_11 lal.lliieeaaattt ittertiinn[[p [[o, 1, 0, 0], [1 o, 1, 0], 11 O. O, 13, [o, 1, 1, o]1)
[[o, o, 0], [1, 0, 1, 0], [1, 0, o, 11, to, 1, o]]
56
57 assert array_inversior ([[I]]) [[O]]
58 assert array Lnvayiinveriion([ 1), [1. 0]]) - [[1, 0]. [o. 113
Figure A.40: Compilation of the program taking Conway's game of life [24] and returning the next state, with the values inverted. In this case, we usg.uutomatic infilling to generate the nount_neighbors function.

---

base_case 1, recursion_rui 1f num == 1:
cur_list=list()):
return lase_case(nur _i_st)
elae:
return Docursion_rulecee (num, cur cur_list)
# Returns the list with the number appended to it def case_case(mus, cur cur_list):
10 cur_list.appr (pppdddd
return cur cur_list
12
13
14 Add list, collatz with if odd / if
15 recursion_rule (nue cur_list):
16 cur_list append
17 if num X 2 -= 0:
18
collatz_recurssionnuu 2, cur list)
19 elae:
20
return collata_recursson((3 num) 1, cur _istt
21
22
23
assert collatz, (19) [19, 58, 88, 44, 22, 34, 17, 52, 26, 40, 10,
5, 16, 8, 2,
Figure A.41: Compilation of the program generating a list corresponding to the Collatz conjecture.
39

---

if 9, then 9 A P lemma P-q. eeg_implies_geee pp Prop):
p P P
begin
intro h,
caaea h with hp hq,
split,
exact hq,
10
hp,
11
12
13 Description: if p V then q V
14 1f P. then p q
15 q.p.implies.pe.. pp q: Prop):
16
17
(q AA p) A
18
begin
19
intro h,
20
split,
21
exact highth
22 exact h.left,
23 end
25 /-
26 Theorem:
27
If P. then p A 9
28
29 -- the and operator is commutative
30 lmmm and and_ commute (p q: Prop):
31 (p A q l
32
begin
apply and. intro,
35 { apply imq_impless_ },
36 { apply i-p-impliss_p__
37 end
39 Description: 1f p A then
40 Signature: p_and_q. inw.iesipppsspppc q: Prop)
41
show (p q A p)
A
Figure A.42: Generated proof of and_commute. We trim the post-proof comments elsewhere.
40

---

given a list of liats reprosenting the cost of beilding road betveen any two citisa, and latt reprasenting the cost, of building as airport in a city, return ney cost natrix with a new node corresponding to the aky. def wowttt/oooocttyyooodddcooo
ddy..ixxort_coot)
:paran city sity_road_cn coat: 1ist of liats representing coat of road betseen any two citiea
:paran city_ stty_aipprr_comm 1ist zepresenting cost of airport in city node correganding the sky
:return:
add now node for sky to cost ratrix
nun citiin - Sen(etty.roaddcom costt)
aky_city_cost [[0 in range 1)] for rangeluus 1)]
for 5 in (ange(nm..cttee)):
12
for J in (ein_.sien
13
sby_city.cout [1] [j] (ity_rodd_ca::([[]
range(mm,ctt
aky.city.omeefi
"iity_irport_cootl]
16
sky_city_pom [-1] eityy.irrost_coot(]
17
return sky_city_cont
18
19
given a list of lists reprecenting the cost of each edge, return an adj acency natrix corresponding to the ninimux spanning
tron.
20 del minizun,spamiing Lrw((c)t
21
vertices that
added
vixited [0]
23
Thia is a list of the verticea that have not bean added to the NST
34
unvisited for range(t, (mn(oes_mtrrss) part the XST
adgex
26
edges
27
This 18 the adjacency natrix correrponding to the HS7
28
ad jdjacency _eatriz - [[o for in range (lan (lang (coit_ for in rampe((an(ane__aarrs)) while (nn(orreested)
Get the index of the ninimm edge did_adde_iddds - -1
31
32
sin_edgo_value ('intt)
range (lan(vintttee))
34
for 3 in range (len(wmrisited))
35
if pott..attrixvveett (atrrst(ttttteelll [unrassted[]]] [ < mtn..dge.rvliu
36
indde (vinitee[t], unvisitad[]))
poet_estrix/vtetttddee [urrsssdddd[[l[ddddddeeeed [uxvisteed[]]] Add the mintmun edge to our XST
38
39
edges appind indge_
Add unvicited vertex the 1ist of visited vertices visited. vieited.sppend append wtw.:iinneeeeeeeedrriil
42
Renovo the unvisited vertox fron the list of unvieited vertices unvicited www.eited.reeeeee rexeoeenninncn (11n__))e__2dde((1) Add
43
44
the adjacenc zatriz
odge odges:
46
adjacescy_matinn lattriioooge [0]] [odge[l]] [1]] -1
47
adjacency www.rmieeeeeeeeeeeeeoo.o [1]] Lodge [o]]
18
return adjaceacy_
50
given List of lists representing an adjacency natrix, return list of thhe nodes connected to the final node. Hovever,
- if only one mode is connected to the final node, return an capty list.
51
def tinal_nodo_co comectors(adjacoecyyy. ratriz);
52
final mode lou(adjacescy jaazzix)
33
final_ htt_:/oodddcccceeeee ceanectore
54
for
range Clen (adjacenyyyyccoooo.oo.oo .zatriz) 12:
35
1f adjaconcy satrricsaattiiiiii [x] [Xinal_node]
final_ nodo_ connecters. append(1)
37
1f Len(tinal_ connectrr)))) 1:
58
return () final,
39
61 # given a satrix represmnting the cost of boilding a road betveen any too cities, and a 1ist represonting the cost of building an airport in city (sbore any t2o cities with airports aze comeectd), return 11st of the cisiee that should have airporta connected. def aixpot, wtt.s/rrrrrt.ttttseecc...e ctt.eesctttssttccecooo. cost, aity.atxort..com cest cost_patrix sky_citty_ cost roadyyt city,etrport_com airport_coott)) adjacency_satee matrii xinimm spanning.trree wtw.://ggttettcttteeooeeeeeeeeee (aati_)) zwiurn finel, wood__comettoraaalllll aaaaaacctoraallececrraaatttii
ceat building roads aisporta such that all citiea list should sorted asconding order.
siainize
62
63
64
66
67 acsert repr(str(selees (str
(soeectttttcctcetr.t.... strport,cittes((C 3, 3) [3, 0. 3), [3, 3, 00) [o, 0, 0]))) - zepristz((O, 1, 2]>>
68 zepa Cata BabeettLirperL_cciieee((
3)
3, 0)) [10, 10, 10])3) (ape(ate(())
assert zops Cata (select, sireectsiioertccccteee((C 10, 2). [10, 0, 11), [3, 11, 011, IL, B))) (eps( 1}>>
70
71 sasert rups Cate (atr wyy.eeity_caat(C.. 2, a]. [1, a). [1. 2. 8)), (4. 5. 6)))) (atrt 2, B, 4). [t. 2, 3. 5), (1,
6). [4, 6, o]]>>
73 assert zupa Cate (winimmn wwwmiip..tteeeeeeeep tra.ttrrreeeo ((O, 1, 3, 4), [1, o, 2, 100), [3. 2, 6. 5). 14, 100, 5, o)}>)> - (pp 1, 0. bo 1). (1. C, 1, 0), (o, 1, 0, 0), [1, 0, 0, o]]))
744
assert zupa Cata (final podd_ consectora
1).
16.
B. o1)))
repe (O))
76
assort Cota (final, wode www.ecorro ((O, 1, 0, 1). (A, 0, 01, 10. 1. 9.
4).
0. 1, oD))
reps (otz( ))))
Figure A.43: Generated solution for pineet__rrpottttot
41

---

# chess_ takes a board and returns the winner of the game. def chess_ (board):
if weight(boarrs =- 0:
'Draw'
if weight (hoard) > 0: return "White' if (eight(board) 0:
'Black'
10 # seight takes a board and returns the weight of the board.
11 def weight (board):
12
weight
13
range (Ie
14
for col range (1en (row])):
15
if [rowd [col] 1= ?.?;
16
weight += Bright_helperr(ee (board, row, col, 0)
17
weight
18
19 beight__elppe takes a board, row, a column, and a weight and returns the weight of the
( board.
20
def weight_helper (board, row, col, weight):
21
[oard[row] [col] 1.7
22 return
23
elif [row][row] [col] - 'q"
24
return weight + 9
25
elif [oard[row] [col] 'R':
return weight
27
elif board[roo] [col] 'B":
28
return weight + 3
29
elif board[rou] [col] '11:
30
weight
elif board[row] [col] t
32
return weight +
33
elif board[rox] [col] == 'q':
34
weight
35
elif board[ros] [col] 'r!:
36
return weight
37
elif board[row] [col] tb':
38
return weight 3
39
elif [oard[row] [col] 'n':
40
return weight
41
elif [rowd [col] = t':
42
return weight
43
else:
return weight
45
46 assert repr (str (chess_ ............... .n..............................
Aa.
Aa
rk. ))) == repr ("White')
47
(chess, (str
game ('rmbggbar/uppppppee) repr (str
In.
() LPPeFPPPPAARNBOZIE
) repr (eep('Dan ('Draw')
48 assert repr (str (chess game gww.eammaaaaaaa wwrpppppprnn......
An....
In.............................. AnK...
....n.......... ....A............ .)). - repr(kBlack')
49 assert repr (str (chess_gael garelaaamme .a bq..k.KK. KAn.B. B.
An. P.. An.
An An. An...N.
\n... .a........ ))) ("Phitehite')
50
Figure A.44: Generated solution for Problem 368 of the APPS test set, identifying the leader of chess game from the board.
42

---

N APPS Decomposition Prompts and Evaluation Hyperparameters
We slightly loosen the requirements for Parsel programs generated by language models, treating redundant function definitions as references instead of raising errors. We sample everything with temperature=0.6, except the translations which we sample with 1emperature=0.2, presence penalty of 0.1, and logit bias to prevent it from generating the text "der", as Codex has a tendency to degenerate to producing Python even when prompted with Parsel examples. We allow at most 500 tokens per function, but in practice found that they typically used less than half of them.
For evaluation, we timeout of 0.04 seconds per solution and evaluate most 100,000 imple- mentations per generated Parsel program.
For the Codex-only ablation, allow it to generate most 1000 tokens, in large part due to the rate limit. In particular, there is heuristic rate limit that rejects any calls requesting more than 4,000 tokens. As result, any larger number of samples per problem would prevent batching more than samples at time.
"*"An action plan is a liat of strings that describes a sequence stepe to accomplish + task, To be correctly parsed, an action plan must be systactically correct and contain
only allowed actions and recognizable simple objecte. Alloved actious: "close" <argi>,
cut? <argi>, 'drink' <argi>, 'drop' <argi>, 'eat' <argi>, 'find' <argi>, 'grab' <argi>, grest? <argi>, 'lie on' <argi>, 'look <argl>, 'open' <argl>, 'plug in' <argi>, 'plug out' <argi>, 'point at' <argi>, 'pour' <argi> 'into' <arg2>, 'pull' <argi>, 'push? <arg1 'put? <argi> 'on' <arg2>, 'put' <argi> 'in' <arg2>, 'put back' <argi>, 'take off? < argi>, "put on" <argi>, 'read" <argi>, 'release", 'rinse" <argi>, 'run to? <argi>, scrub' <argi>, 'eit on" <argi>, 'sleep', 'aqueeze" <argi>, 'stand up', 'evitch off' <argi 'switch on <argl>, 'touch' <argl>, 'turn to' <argl>, 'type on' <argi>, 'vake up', walk to <argi>, 'vash' <argi>, 'watch' <argl>, 'wipe' <argi>, To satisfy the common- sense constraints, each action step in this action plan must not violate the set of its pre-conditions (e.g- the agent cannot grab milk from the fridge before opening it) and post-conditions (e.g. the state the fridge changes from "closed" to "open" after the agent opens it).
>,
>,
#*#**
task_plan(): return list of strings that represents action plan to put mug on the stall and bread on the desk. "executable"
crt_ojjsct_onoobject place): return a list of strings that represents an action plan to )) put object in place.
"mug", "stall" " -> "executable"
Figure A.45: Full Parsel program including header for Fig. example, with the #*### as the header seperator. Note that essentially just took the executability definition in [28] and added the list of available actions.
43

---

Hell.... Solution-
Propose a clever and efficient high-level solution for this problem. Consider all edge cases () and failure modes.
strategies include:
Constructive algorithme, Binary search, Depth-first search (DFS) similar elgorithme Dynamic programming, Bitmasks, Brute force, Greedy algorithme, Graphs, Two pointers,
S
Trees, Geometzy, Graph matchings, Hashing, Probabilities, Data structures, Sortings,
Games, Number theory, Combinatorice, Divide and conquer, Diajoint aet union (DSU),
Expression parsing
Write out your reasoning first, and then describe high-level solution and explain why it
b is correct. \"
10 Let think step by step to come up with clever algorithm.
Figure A.46: High-level sketch prompt for APPS programs
44

---

# Bara is at exepple caleslating the pectablisey of landing on the cane character in raadon shits of an teges string, beaed on the following
problem:
2 Vaaya Kilye play
with alaing, wiing the Jollowin siles, Initiall,, Tolys creaties aizing comsising of smill Englinh iviture, und untforsly randee chsones an totagar froe a saguet (b, laste) 1): talle Dagya this sering is thes shlees it Lettare to the the the integer k. To do cate, in sete knlza to tall iin the first intter of the and string, and sten, sfter ha cee ih, open ore more latter in Vayya cus choose. that be will win, but vents to kav the probubility of winzing, if plays optinully. Be
be
A Vaaya udeersaanly, that can't
coepeta this prababi the
Note tast
crelie shifto of that fit information Yeayu boonee layg lonas, of comra,, an mny roent of the guee Theys seree to wartiin the probabiliny of Me win.
geaarate chifte
oratte the sverage
of unigue charactare to the embetringe the string that start with each
charactar
string
congutn, Lan lester pinCingut.atr)) Geterasee the str ior l let and laster, por yerrs struarcrieber, list. 16 a les of Ixtepere this in uned stare the chiracter valure of impat atring. atx sumber 100T calue
charecter initinlzzed list of tvice the Length of the tapas steing. and
csloulated lecter ace a list of Lists, wies eact sublist cottaining the indioss as shics particalar characses sppeare is the iaput string. poa)
The
Galculaces l1s of lists, with each oublint containing She indicos vhich to longtt) this start with the cloroitor regrosested by letter.por
character appeare in the inpor string. atr sumber
1888 of tataparn that ia used to stere the character valonn of the inpot string
11 coepote enteuee charactera, for kic, k. atr nebeer 11st, lotter pos): Create counte 1ese of seece for axck of the 25 slptabetical characters. pcl Lscrement counts at stt.tt.
unntlyy wiblist of positions
hl. heturn the sumber counte whick
wt.ortpt_ (ann, str): Baturns a string reprasentation of anx divided by the length the tnport string.
14 1inse)
And Sare ie amspls idenstiyiigg the langatt binavy numter acconding to the follortng rilae:
The little Elephart has Lacegee a, seailes is the bisuey ustution, He vustu to sealy thes sumber on pivcr of paper. digis nambez tae vecard to that teo member appears, it conclate of the nessining hinary digits, critesn in the corseganding onder (poratble, with landing
19 little Staphant unnte the member ie
to geita dbvain after deleting esucily our binsey digis und peist it in the bintey uscatico.
Targe posxible. Relp hin find the wartrce neeerr that he can
31 largett bonarry /trtor c Recemm the languat blusey mither that can be rade by newwingg as wast mn digit froe the ieput atring.
pacce inpet Lappst stsl; temone Tives
a atxing and eecarns the Lapas steing
th
froe tager string.
24 20 cutput, ate (biggee stel: Betersa the bagger string.
26 lines)
format applled so iydesi virner of following 29 It is 20 bering in the surser holiday, isn't set do alice and Bob have inmented a new gase to play. The raiee are an follous. First, they get a ast following soven. ing move, elther curvent) Integees. and they tures free the such the doare't contain thate aboutute difference Ix yl. Then discanct integers 2his plaser alds Leöegee y1 to she ost Coo, the dise of the aes increases by soe). willd nesember that Aldce slcage coves stret.
Hero essplo
Feb tihe player turn
II
guse. question
will fimally the gane bush playero play optinally.
sdantsty stener (toper atto: Raturns staner
pacco, input Liapsi sic): Takeu alring contemning tau Jesgth un the firut Line and the intogees un the uscaud and revarus the liut of inllegeeo divesed by greasest comton
largeet almment
all alemant 19st,
Length of the 1sst.
all scalal beiszau the geveient comsa divisur clamutt the list
string 'alton" if the nember of norne ie and and "Doh" se the neaber of moves ix wnn
35
play. Today be playisg by destcoring block sowsca. Be built a soeers in zon, The 1-th sover is made b.j idensioal blocte. claviti ane plattre everything is deatseyed. 41 # Lizua will suprot the foliowing operotios neighaere,
Liaak is little sho
rightt) adjaceet Otheevise, block bundary. in operation Linis desteoya boundary blacks. His aze fust und be deatroya all these blocka at 43 Uiiak ready start. You tank
(trp,
hos sary operations will take his to destroy towers.
44 (eree
desteoy (tr))
momber sperations
destroy souern.
import (ispa, Takes string containing number of tovers the list beighte
first and the beightz the scwera the second snd returza
45
dentroy, fecn, lefcletde iist); Dopy the List and see each each slecent to the minseus of steels and one more thas the elenent to stx left, starting secord
49
deatroy reom, right (asde (ist):: Copy the 1is5 and not each each slement ststeen stante and one than the alenect tte right, plorting froe She secoad to last oloment
corpespoocing
31
se.auiput 21802: Boture the string epproontation 1inee)
element in Ube liot
trip bus Bull ciliso und fell badiice sonul zouds connec Ling Lbea, Alux liver in city futl and وnاtiااly located in To conpare disfarant csttee Aler aestiged each dity acore Bu.15 which higs as tetarreting city raene Alar.
36 Por vimplicaly lastu come thit
Alex
city lewa dity
our chocpe us the and cate in the teis any city csnnected with 3-8 by the cool, sncupt for the city BaF, that for city the score
any plan Alss been several times dur his
Bimple
61
panen inper (rrper, str): Taker soriig contxining the rumber of citles and ronds on one Tine, the scorne of the ctictin in the next Time, the yoads disy acores,
octronee)). the starsing aney de Tast Tine.
liss, and the stacting city.
gen maiggoonneeeee (edgadd: teteree dieriimary the neighhove of eath city, defunteing an cngty eat.
(sccluding the root). Tesove eesnn incoree anl ghigeeere dagrent, lowees riot): Dreate brinisialine ined dntaylssicn botal Lerter, and las of eax, extra. Pop levvns tonal, extra and mas extea based on the parent's total, extra ve the Leat's acore plza its total extra, vhicherez
64
unssi expty. Return setea.
65
pop-leaf pog.leaffowig Coightee,, dagreso, leavos, roos): Pop off leet- det pareet se aole seightor the leat and delato the leat feam the neighhore parent's
66
se,uuiput.ats atty (ocorres anightors, raot, mntral) Returno the string of the maxieus souce Alox cen ges, It the z00t lin's in neighbies, reture the scoce the zeet. Stterstee, this is the are the accren the ciesen lafe in neighhsee, piue the retorzed escountered max, Linru)
the
coot
68
30 2 Trunslate the Collowing volotion plan into the above Jocmmis
(entesson, attrr) cnstanton,eee tast)
21
TRAISLATE to Farzel.
75
Figure A.47: Translation prompt for APPS programs
45

---

HumanEval Prompts
We the same zero-shot prompt to encourage the high-level sketch in APPS. For translation use:
You will aim solve the following problem in Parsel: [question]
Translate the following solution plan into Parsel: Soluutioo.sarrryessuuttoooorrr
translate solution plan problem into Parsel. Each should contain a function description or function reference.
A function description should be of the form:
10 '..
function_nameaarg!! arg2): Description of the function
12
13
14 function reference should be of the form:
15 <<)
16 function_name
17
18
19 Use indentation indicate dependencies between functions. example, function calls
function B, then function B should be indented under function 20 Make sure that the top-level function matches the name of the function in the solution plan.
Figure A.48: Translation prompt for GPT-4
46

---

Robotic Plan Evaluation Details
P.1
Questionnaire
Our questionnaire closely follows that of Huang et al. [28]. We provide figure with the directions for the accuracy version of the survey in the first image of Fig A.49. We include an example question in the second image. Note that each participant was shown random 5 questions with their answers random order. The clarity survey instead asks "For every question below, evaluate how easy is to understand how the provided steps accomplish the task. Please rank the planned steps for each question from most understandable to least understandable (with as the best and 3 as the worst)." " In addition, for the clarity survey, each question text instead said "Rank the following plans based on which is the most understandable (1 most understandable, 3 least understandable)."
P.2 Executability
We find that the automated executability check is a less insightful metric than human evaluation, as doesn't 't meaningfully reflect the plan's 's likelihood successfully completing task. Unfortunately. the code to replicate the executability measure from Huang et al. [28] is unavailable. As an alternative, we developed our own executability checker using example code found on VirtualHome's 's GitHub repository, which evaluates if proposed plan is syntactically accurate and can be executed within the VirtualHome environment. By leveraging Codex to generate eight Parsel programs for each of the 88 tasks and subsequently compiling them using the Parsel compiler, our method successfully produced executable solutions for all tasks. Conversely, Huang et al. [28] managed executable plans for only 86 tasks. However, it is worth noting that our Parsel compiler explicitly incorporates this executability measure as a constraint, which explains the higher exccutability rates observed in our approach.
47

---

(and only) survey page, you be presented questions.
eacn quastion you everyday
a accomplish
detarmine whether the task be completed using the provided staps. In other words, decomposed
staps? simply restating not mean completing Please rank the pla planned stepa for each question from most woret).
question,
your
determine ne the anowers.
Pank the following plans based on how acounitely taey accemplish the bask (1 moat accurate, Heest sccurstej
Wush
meah bethroam
walk to mnnk
Enn faucot
touthbrush
toothoesto
grab locthperrs
put toothpaste
feath
rinse toothbbrsh
swilch off faucet
grat
toothbrush toothorush
gralo lootibrugh
toothiorash toothonalh holder walk bectoom
taok,
Jesth:
Ain toothbrssh
plug
sccubb teath toothin..sh
pour water into toothbrrsh
Kinse toot-ibush
plup
towel
wide teeth with towal
crop towel
Think Wiesh teeth
toottbruah
open toothorush
grzb toothbrush
bathromm
bathroom
foachoouah bathrom slnk
nalesae toothbnuah
put brack toohhrrah
Figure A.49: Screenshot of survey directions and example survey question. this figure, the first answer generated by the baseline, the second the indented Parsel version, and the third was the unindented Parsel version. However, note that the order randomized for each participant.
48

---

Human Case Study
main(input__taan (ntruttttttrr Takes
line. First, splits it at neuline, and stores the second line in variable and the third in Splita a parta the asterisk, and checks whether the string t starta with first part of and ends with the second part, Returns the string "YES" if that condition is met, otherwise "NO". Also, it should
alvays return "ND" if the length of t is smaller than the sum of the length of the
parts of
1o'ncoodeesancodeffrrce
"YES"
"6 10'acodeforces cecod "YES"
"6 (o'acode=morces waw.:roocccccooofooorreeeeeee -> "NO"
"6 10'ma=e'na" -> "NO"
"6 10'ns=alnaa" "NO"
Figure A.50: Solution to
maauttaaputsttrnng) Parsea the imput and returns the minimun area of the imput. "3\m10 1'n20 2\n30 3" -> 180
"3An3 1'n2 2\n4
21
Takes input line and first splits on newline. Ignores the <)) first line, and parses each of the remaining lines as tuple of two numbers, which + give a 1ist L of tuples. Returas L. "3/n10 1\a20 2\n30 3" -> [[10, 1], [20, 2], [30, 3]] space,
parse_line()): Splits
each element int, returns result + of converting the result a list.
"10 1" >> [10, 1]
nuunrrate_ubbett_st_.ooom
k): Returns all aubsets of with sizes ranging from 0 to
inclusive.
[1, 2, 31, 2 [O, [1], [2], [3], [1, 21, [1, 31, 3]]
10
cuumerate_suseetae (L, k): recusively enumerates the subsets of size k of the list L. + Base cases: if k 0, returns list containing the empty list. If k len (L)) returns the empty 1ist. Othersise, first construct the subsets that contain the first element, then those that not, and
their concatenation.
[1, 2, 3], 2 [[1, 2], [1, 3], [2, 3]]
12
minimum (wha) :ini)) First, calls enumerate_subeet wtt.suubbbtt_tossttte with whs and the aubset.
passing whs and half the <y length of whs rounded down. Returns the minimum result of calling compute_ares on the
list given by apply_inversee
13
[[10, 11, [20,
[30, 3]] [[3, 1J, [2, 2], [4, 3]] >> 21
14
15
enumerate, enumerate_subrett sateeeuuueeesssseeee at__ss____
16
(ampute_areauhs)) takes 1ist of pairs (width, height). Computes the sum of the the heights. Returns the product those numbers.
widtha
17
[[1, 2]. [3, 5]] -> 20
18
[[10, 10, [20, 2], [30, 3]] -> 180
19
ipply_inversions (whs, subset): Takes list of pairs of form (v, h) and subset of indices invert. Returns list where the elements whs whose index the subeet inverted (h,
the others appear given. [[1, 2], [3, 5]], [1] -> [[1, 2] [5, 3]]
20
21
[[1, 2], [3, 5]], D -> [[1, 2], [3, 5]]
Figure A.51: Solution to http:://coeeeerrr..cc///o/aaaaap /59//
49

---

mainninput);; Converts the input integer the value of
"2"
"3" -> 10
f(n): First pre-computes the Pascal triangle up n+1 using campute.pascal_tritn
Then,
the value of dp(a, pascal_triangle
1 1
2 -> 3
3 -> 10
matrix with < to "i choose k", i.e., Pascal triangle. computed using dynamic
pampute.pascal_ccm :ria
where m[i] corresponds
programming: m[i][j] m[i-1][j] [[-i-]][-11], All elements are modulo (10+49
= +)7) The 1-th row has only i columns.
10
2 [[i], [1, 11, [1, 2, 1]]
11
3 -> [[1], [1, 1]. [1, 2, 1], [1, 3, 3, 1]]
12
dp(n, pascal_ trrealle)) first creates a list with (n 1) zeroa called Then fills
( it in with the following dynamic programming relation: base case is L[0] = 1; then, L[i] sum (j in [1, il) pascal, triaaggeea-- pascal_triangle
L[i j]. Finally, (k in [1, nl) pascal_triangla [k] Lín x]. assiguments,
returns the following each
modulo 10+.9 avoid big numbers.
13
[[I], [1, 1]. [1. 2, 1]] >>
14
2. [[I], [1, 1], [1, 2, 1]] >>
15
3, [[],, [1, 11, [1, 2, 11. U1, 3, 3, 1]] -> 10
Figure A.52: Solution to https:/ccodeforcess ctc.eassccco/ooooo/oeo wwtppp/oooeeeee//roooo...oo
main (input): Reada the input 1ine and counts how many pairs of elements pass the test.
"4 21n2 3/a1 4'n1 4\n2 1" ->
"8 6'n55 6\n5 7\n5 8\u6 2\a2 1\n7 3'nt 3'at 4"
parse_ parse_input(ce (inppptt Splits input sequence of lines. Each line parsed list e) two space-separated integers. The first 1ine of input contains and P, the second to last lines are aggregated in list L. Returns list with three values: N, P and L.
"4 2\n2 3\m1 4'n1 4\n2 1" [4, [[2, 3], [t, 4], [1, 4], [2, 1]]] count_valid pairsst, p):
distinct pair (i, j) both ranging from of L, counte how many of those pairs have score least p in L given by + compute_papteeec paor_score.
length
[[2, 3], [1, 4], [1, 4], [2, 1]]. 2> ->
[[s, 6], [5, 7]. 8], 21. 1]. 3]. 3], [1, 4]]. compute_pain pwtpppaarrrrrpaaeeeep
D): receives two integers, a b, and list of pairs L.
Returns how many elements of L contain either a + or 1.
10
2, [[2, 3] [1, 4], [1, 4), [2, 1]]
->
11
[[2, 3], [1, 4], [1, 4], 12 1]]
->
12
1, [[2, al, [1, 4], [1, 4].
12, 1]]
13
4, 5, [[2, 3], 01 41 41 4], 12, 11] >>
Figure A.53: Solution to http:s://codfoooo
50

---

main(input)) parses the input as two space-separated integers, and m. Return 2 * f(n m)
modulo 10+49 + 7
"2 3"
"3 2" ->
f (a, m) computes fib(n) fib(m)
2, 3 4
fib(m) computes the m-th fibonacci number modulo 10**9 using dynamic programming starting [p[o] dp[1] 1, dp[n] (dp[n-1] dp[n-2]) (10+19
4 7)
+> 1
2 >> 2
3
10
4
11
5 -> 8
12
6 >> 13
Figure A.54: Solution to
51

---

R Parsel Language Nuances
R.1 Syntax
Descriptions. A function description is represented as a function name followed by comma-separated imput arguments in parentheses, and optionally arrow followed by what the function returns", then colon and text describing the function to be implemented. For example, as part of Conway's Game of Life, one might write
count count_living wtt.__vvvnnnneeghbrreeee.. (grid, 1, }): count the number of living neighbors of the cell at the > index (1,
function generated from a description can call either the functions defined directly below the description in the function graph (indicated with indentation) references directly below the description', both shown Fig. ii.
Constraints. A constraint is represented as function's input values comma-separated, optionally followed by an arrow and the expected output of the function. Constraints are provided at the same indentation as the preceding description. For example, after the definition of count soant_liingg.am neighbors _eiihggeeighhbrrs one can write
[[I, 0l, [o, 1]1, 0, 0 0,
[[1, 01, [o,
This indicates that count count_living neighboss should return when called with the arguments [[1, 0], to, 1]J. o, and 2 when called with [[1, o], [o, 1]]. o. Notably, apply complex constraints on functions, one can describe and constrain higher-order functions. For example:
type_fa__utpppeee tn_oututttfn, arge): returas the type the output of a function called with arge count htt._livinng_niihbbrs ([[1, 0], [o, 1]J, O, 0) -> int
This indicates that the function count soant_liiing_aaee living_neighbors neighbors should return an integer when called with the input arguments [[1, 01, [o, 1]1, 0, 0.
What means to satisfy constraints to validate a program varies from language to language: in Python, one can check that program passes certain assert statements by evaluating them; however, in theorem proving language like Lean, where the ability to run program (without skipping steps by using sorry or oops lines) shows that proof holds, one would instead represent the formal proof statement as the specified constraint (that is, that you are actually proving what you set out to prove). For languages where correctness can checked without any unit tests, their functions can be treated as also having implicit constraints.
oollata, recursion
Figure A.55: collatz_recuraion call graph. There a strongly connected component formed by collatz_recursion and recursion
References. A reference is simply the name of function defined in the current scope (see the next paragraph for details) within the function graph. A reference allows and encourages (via prompt) the parent function to use the referenced function. This allows for recursive function definitions and functions called by multiple functions. For example, one can define an (overly verbose) version of the Collatz conjecture (a well-known recursive open question in mathematics) shown in Figure ii, visualize the corresponding call graph and its strongly
where the final line is a reference. connected components (SCC) in Figure A.55. In the Collatz functions, case is implemented first SCC depends on it.
as the
NNtt that in Parsel, for Python a generator.
also indicate in the description that function should yield value
A nuance here is the optional ability for undefined/outtof-soom functions which are generated by the code LLM also be implemented automatically.
52

---

R.2 Headers
We also support program headers, allowing global contexts, used when implementing all new functions within a program. This is indicated by a line containing an optional string of special characters (e.g. "#*#*#") separating the body and the and is passed prefix all prompts.
R.3 Repeated Automatic Decomposition
As indicated by rapidly growing number of papers [10, 28], the task of decomposing task into steps in natural language one that language models are surprisingly capable of. As explored in concurrent work [57], using language models to automatically and recursively decompose difficult open-ended problems to arbitrary depth a powerful tool. Thus, we treat the ability to automatically decompose a Parsel function as key feature of Parsel. This is an optional flag that prompts language model generate Parsel code corresponding to any additional subfunctions necessary when Parsel fails to implement function. These proposed subfunctions are then added as child nodes to the decomposed function node. However, an additional consequence that Parsel can thus be used to recursively decompose tasks into steps, by repeatedly identifying descriptions that cannot be directly implemented and attempting decompose them.
R.4 Scope.
Scope in Parsel is defined by indentation. The scope S of a function f includes the set of functions that can be used as a reference for given function that is, all functions where the indentations between the current function to the referenced functtin are strictly decreasing.
R.5 Variations due to target language requirements.
Certain aspects of the implementation are still target-language specific. As discussed above, the meaning and representation constraint may vary by language. Moreover, every language has different evaluation function: executing Python is different than compiling and running C++ code, which is different than checking proof with Lean. Further, every language will likely require different prompt for the language model. Thus, we detail these particularities in language-specific configuration files.
53

---

Pipeline Figure Example
Question:
The grand just announced large exhibit jewelry from around the world. the hopes of his potential future prosperity, the world-renoweed thief master criminal Edward Terrenando has decided to atteupt the magnum opus of his career in thievery.
Edxard hoping to purloin large number of jevels from the exhibit the grand museum. must careful with jevels appropriate order to total value jewels stolen.
Edward has $ knapeacke of size 818, $2$. $38, $x8, and would like to know for each stolen. This way he can properly weigh size
the maximum of values jevels that
risk vs, reward when choosing how many jevels to steal. A knapsack
can hold items if the sum of sizes of those items is less than or equal to $a$. If you can figure out the best total value of jewels for each size of knapsack, you can help Edvard pull off the heist of the century!
-...-Input--....
Each input will consist of a single teat case, Note that your program may be run multiple S times different inputs. The first 1ine of imput will consist of two space-separated integers SuB and tk$, where fuš (81 Ale \le 1000000$) 1000008)
number of jewels the knapsack available Edvard. The next $nš lines each will describe a jevel. Each line will consist of two space-separated integers $s$ and $v$, where $s$ ($1 \le \le 300$) is the size of the jewel, and $v$ (81 \le Ale 10-98) is its value. Each jewel only be taken knapeack
exhibit,
($1
knapsack,
independent problem.
10
11
12 Output S&$ integers separated by whitespace. The first integer should be the maximum value of jevels that will fit in knapsack of $18. The second should be the maximum value of jevels knapsack of size $28, on.
13
14 --.-
-Examples---
15 Sample Input
16
17 2 8
18 1
19 3 4
20 5 100
21 Sample Output
22
100 101 108 109 109
23
24 Sample Input 2:
25 5
2 2
27 3 8
28 2 7
29 2
30 3
Sample Output 2:
32 0 7 11 15 16 19
Figure A.56: Pipeline Figure Task
54

---

First, we need to figure out how to calculate the maximum sum of values of jewels for each size of knapeack. To do this, we can use dynamic programming approach.
each row represents < different jevels and each column represents the different sizes of knapsack. The value > of each cell in the array will represent the maximum sum of values of jewels that can be
can create tro-dimensional array size
stolen for given knapsack size.
We can then iterate through the array, starting at the beginning. For each row, we can
+ calculate the maximum sum of values of jevels that can be stolen for each knapsack size
O by taking the marimum of the value of the current cell and the value of the previous cell plus value the current jewel.
At the end, ve will have an array that contains the maximum sum of values of jevels that can < be stolen for each knapsack size. We can then output these values as our ansuer
This algorithm
of values of jewels that can be stolen for each knapsack size by comparing the values of the curreat cell and + the previous cell plus the value of the current jevel. This ensures that we are taking
because
calculating the
the maximum value for each knapsack size.
Figure A.57: Pipeline Figure Sketch
55

---

Takes string containing the number of jewels knapaack the first line, the jewels on next lines, and returns the number of jevels, the knapsack sizes, and the jewels.
def crnpe___nputiinpt__eee
lines smput__trreellie(MMa
first_line limes [0] splitt
num_jevels int (nfirst__iieeO0) [0])
knapsack_sizee int @first__line [1])
jewels [[o. 0]] num_jewels
in range num_jenels
jewel lines [i] (i).spttt ")
10
jevels(i
(int(]eee int(jewel
11
return num_jewels, smapsackssizes jewels
12
13 Returns maximum
values of jevele stolen knapsack 14 def max max_sum_off wtw../eeweell.oor.eeeeedeedddedd (jevels, size, jeuel):
15
if size < 0:
16
return
17
elif jewel
18
return
19
elif jexel == 0:
20
return javel=[jexel] [1] if jexels[jevel][0 [0] <= size else 0
21
elif [eveel[jeve]] > size:
22
sax_sum_ oot_oofjjeellle htw.jeeell_forr.eeeeaad________ aee.e size, jeuel-1)
23
else:
24
return max (max_ssu sfeax__smmoo_.ee foweees_oorsiee__nniee
size, jewel-1),
25
max_sum sum of jewels_for www.ssiiinnnn.. and__jnwelllleeeeeeeeeeeeee_____ (jenels, size-jewels [jewel] [0], jevel-1)
jewels [jewel] [1])
26
27 Returns the maximum sum of values of jevels that can be stolen for each knapsack size.
28 def max max_sum_of__ for.:oof_.eeels_o..eiiees sieeeeee,,,e size):
29
result []
in range(1, 30 result of www.eeeeeeoreseeeeeaeeeee jte_ s, len(jexels) 1)]
32 return result
33
34
Returns the string the maximum values of jevels that be stolen each
knapsack
35 se_ouuput_ttrrexx__umm.o
36
return ".join (map(m,ssstr otw.sumoo_jeeee_tttte
37
38 Returns the maximum values of jevels that be stolen each knapsack
39 max_sum_of_jjeell (input_sttt))
40
41
>>> jax_sum_on _aan_of__eueelleee je 9\\n2 Bilnt 1ans 4\nn 100\in2)
42
'1 8 9 100 101 108 109 109
max_sux sum of ("5 7\ 2\n Nm2 7\222 4na 8\
'0 7
19*
45
46
number_od number_of_jewe _f_weele_ imapsack_sizes jevels parse_inppl (input_stz) to_ p__ouppu__atr (max_sum, sum_of, www.wl..ssle.e..e...e.....olllse for paz_sizaajeevlll saapsckksizees
47
49
50
assert compare_output (max_ sum_ _jjeels, *4 91n2 8/n1 1 4\n5 100", *1 8 100 101 108 109 109*)
compare_outpar
(oatputmmax___eeea (max_eum sum_ of of jewels, *s 2\n3 8\n2 7\n2 8
19a)
assert compare_output (max_ sum__tt je_eeeee,,, 22 6\n300 1\n300 2',
01)
Figure A.58: Pipeline Figure Sketch
56

---

T Other Details
T.1 Test Generation in HumanEval
For test generation in our HumanEval experiments, generated set of tests by prompting GPT- 4 to "Generate an assert-based teat for the following function. Answer with only a code block, and other text. Do wrap your and set-aggregating 100 completions.
function. \n" question and then collecting
T.2 Backtracking
also support backtracking for the Parsel implementation step, where we re-implement descendants by sampling new solutions for dependencies if a correct solution is not found for parent. This is necessary to improve the robustness of some of the Appendix examples such as Figure A.14.
T.3 Training Details
Although we do not train any models, all models used are discussed throughout the paper. See Appendix N for more details about sampling hyperparameters.
T.4 Error Bars
We estimate standard deviation of +1.4% for the best APPS result, given 1000 sampled problems.
T.5
Compute
The most computationally intensive part of this research, by far (in terms of FLOPS), was ablation using open-source CodeGen model, which required several- hendred A100 hours. The rest of the inference was done through API calls.
T.6 Generated Tokens
For the APPS evaluation, in terms of tokens generated, is hard compare the models directly: The CodeT paper does not specify the number of tokens decoded for their evaluation. Without more detail about their evaluations, it impossible to confidently estimate the tokens generated per program for the CodeT evaluation. The AlphaCode results sample at most 768 tokens per solution, but they do not report average statistics directly based on Figure 11 in the AlphaCode paper [35], the majority of its generated solutions are 150 350 tokens long after removing dead code and comments. The competition-lett problems (that we evaluate on) require more tokens on average. For their best reported results, their figures indicate they sample at least 20 billion tokens for the competition-level subset of APPS. On the other hand, for our best results, Parsel generates (on average) 491 tokens of Python code per program implementation, and because Python sixteen times (i.e. k 16 in our best n X k), we also sample on average 22 sketch tokens and 43 translation tokens per Python program implementation. Correspondingly, we sample roughly million tokens for our APPS evaluation.
implement each high-level sketch in
T.7 Reproducibility
While our contribution not a model or dataset, we have released our code.
T88
Evaluation Time
For similar API rate limit and evaluation time, we expect our longest-running evaluation runtime would be fairly comparable to the 1,000-program AlphaCode evaluation (despite performing 3x better) and several times faster than the 50,0000program AlphaCode evaluation. other words, we believe that generating 1,000 programs and evaluating them is not meaningfully faster than generating the 128 Parsel ones and then evaluating their combinations, even in the worst case. Our reasoning is follows:
57

---

Generation time. Because AlphaCode has no yublic-facing API, let us use the advertised rate limit for Codex (40,000 tokens per minute) as the generation speed. (This ignores the request per-minute limit and the number of input tokens in context.) For AlphaCode, assuming roughly 400 tokens per solution, generation would take 10 minutes plus the completion time (i.e., the latency from an API request to the result) of roughly 30 seconds. For Parsel, in our largest-scale experiment, we generate eight plans, their corresponding Parsel programs, and then each Parsel program's 's corresponding 16 implementations. At the same rate limit and program length, these generations would take about 1.5 minutes, plus three times the completion time, other words, generation should take about minutes for Parsel 10.5 minutes for AlphaCode.
Evaluation time. Let's consider three evaluation scenarios, maintaining the 0.04-second implementa- tion eval timeout used in the paper, run on single 16-core machine. 1,000 evaluations. If we run 1,000 programs for each method, under the same constraints, their evaluation runtime should be the same. As indicated by Fig. 4-right, the Parsel performance would be substantially higher despite being over 3x faster overall. 10,000 evaluations. If we assume programs take the maximum allowable runtime (the worst case for Parsel), then 10,000 evaluations takes 6.7 minutes for parsel, compared to 40 seconds for 1,000 AlphaCode program evals. Parsel still slightly faster, yet solves multiple times more problems. More evaluations. After this point, we run into the 2-minute per Parsel program limit (discussed previously). making Parsel slower than AlphaCode the worst case but also solving over 3x many problems.
Other nuances. With all this being said, this a difficult (potentially impossible) comparison make fairly for a few reasons. First, AlphaCode is worse than Codex, but likely faster, so it isn't clear which Parsel data point and which rate limit would make an appropriate comparison. Second, runtimes and problem lengths can vary substantially. For instance, we haven't It considered input tokens so far, but these penalize AlphaCode more than Parsel, as AlphaCode inferences many more programs. Note that APPS problems are fairly long (the longest competition-level problem requires over 1800 tokens) so the effect of re-processing the problem statement at each program inference substantial. Since the rate limit includes input tokens and there is hard limit of 4,000 generated tokens per query, this decreases the effective rate limit by third!
58


Reviews:
[{"review_id": "wj4pE6NYJZ", "reviewer": "Reviewer_LfRB", "summary": "This paper introduces Parsel—an intermediate programming language for large language model program synthesis. It decomposes a complex programming task into several strong-connected components and uses large language models to generate candidate code pieces for each component, combined with combinatorial search and test case generation. Evaluation on HumanEval and APPS demonstrate the method's outstanding performance when used with GPT-4 and Codex.", "questions": "See weakness. I have no additional questions.", "limitations": "The authors have addressed limitations in the current draft.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- I like the idea of combining language models for function generation and using combinatorial search to find valid programs. It is an approximate form of the fast-and-slow thinking of human problem-solving. The idea is intuitive enough, and the method works well.\n\n- The Parsel language is well-designed as an intermediate programming language in the program synthesis pipeline. It takes advantage of both modeling uncertainty of human language and deterministic descriptive language (IO-specs).\n\n- Experiment results on HumanEval, Apps and VirtualHome are good, reaching outstanding performance with a lower budget (large language model API budget) by trading some local computation cost (combinatorial search), which is something good to see in the LLM era.\n\n- Analysis of Parsel on HumanEval is also valid and persuasive for proving that Parsel can generate longer and more complex programs.\n", "weaknesses": "Overall, I like the paper. I have a few concerns about the weakness.\n\n- (minor) reproducibility: OpenAI is ending their public API service for Codex recently (I think it is before the submission of NeurIPS), resulting recent paper using Codex is hard to reproduce the experimental results after. I suggest using publicly available GPT-3.5 (text-davinci-003 or gpt-3.5-turbo) to give additional reproducible results.\n\n- Parsel design: I am thinking of if the Parsel language is expressive enough (for example, it may lack data structure design (which is something that makes APPS hard). Can Parsel generate data-structure specs?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the encouraging review!\n\n> Parsel design: I am thinking of if the Parsel language is expressive enough (for example, it may lack data structure design (which is something that makes APPS hard). Can Parsel generate data-structure specs?\n\nThank you for this excellent point. This is definitely a challenge. One approach which we’ve used is to manually apply a header (discussed in Appendix Q.2) for this - for example, you might specify that an object is a dictionary with certain keys. As we mention in like 356, for the lisp interpreter, we described the environment dictionary in the header. However, this is clearly an imperfect substitute for a proper object-oriented syntax. We’ll add this to the limitations of Parsel for programmers in Appendix A.1.1 and elaborate it in the main text.\n\n> (minor) reproducibility: OpenAI is ending their public API service for Codex recently (I think it is before the submission of NeurIPS), resulting recent paper using Codex is hard to reproduce the experimental results after. I suggest using publicly available GPT-3.5 (text-davinci-003 or gpt-3.5-turbo) to give additional reproducible results.\n\nAt the moment, OpenAI has (fortunately) extended researcher access to Codex. In the long term, we are optimistic that open-source language models (both for code in particular and code and natural language generally) will also become more competitive with these tools. We mention briefly that we attempted to apply these techniques on a 2.7B parameter Codegen model, but even with the same Parsel outlines, it was unsuccessful. "}, {"review_id": "fS9T1a6QZP", "reviewer": "Reviewer_PK3i", "summary": "This paper proposes Parsel, a code generation framework that decomposes a problem specification into subproblems specified in a intermediate pseudocode-like language (the Parsel language) and then searches over combinations of subproblem solutions. The experiments show that decomposing and searching over subproblems leads to gains on standard code generation benchmarks and a robotic planning task.\n", "questions": "- When you set a budget of number of evaluations, how do you decide what to evaluate?\n- The \"Functions without constraints\" section was dense.\n\t- How does the parent enforce constraints? \n- Human expert comparison: this was a cool experiment, but the setup wasn't clear to me: how was the expert using Parsel? Were they initialized with a Parsel-generated ?program and then revised from there, or was it more of an iterative process\n- l212-216: I wasn't clear on why this is the conclusion from the human expert results\n- nit Fig 4: it initially wasn't clear that 50 (Improved) was the Codex API and that this was the \"prior work\" you were referring to on line 145\n- nit Fig 4: what is 5@50000?\n- It'd be helpful to have an example of mutual recursion. I see this is possible in theory but couldn't think of when this would occur and how common it is - why would two function implementations depend on each other?\n- How often are child functions shared between parents / called between different parts of the program? In cases where it is shared, it seems like it'd be helpful for the child description to be generated conditioned on _all_ the caller descriptions (whereas from my understanding, the child description is currently generated conditioned on the description of the first caller). I could see this not being an issue for current code generation problems, but it seems like it'd be important in real-world programs.\n- Why is it sufficient to only consider strongly connected components?", "limitations": "Yes", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- Very well-written and motivated\n- Thorough experiments on performance gain + analysis of inference cost / scale\n", "weaknesses": "No major weaknesses, besides the minor questions on clarity below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your comments and questions! We intend to incorporate our responses into the revised paper.\n\n> When you set a budget of number of evaluations, how do you decide what to evaluate?\n\nWe consider a random subsample of the possible combinations.\n\n> The \"Functions without constraints\" section was dense. How does the parent enforce constraints?\n\nThe parents’ constraints are used to validate the children. If a child’s parent passes the parent’s constraints, it’s assumed that the functions it depends on are correct (which can, of course, be an incorrect assumption in many situations). In other words, if function $f$ calls function $g$ and $f$ has tests but $g$ doesn’t, then we generate implementations of both $f$ and $g$ and then aim to find a pair of implementations that satisfy $f$’s tests.\n\n> Human expert comparison: this was a cool experiment, but the setup wasn't clear to me: how was the expert using Parsel? Were they initialized with a Parsel-generated ?program and then revised from there, or was it more of an iterative process\n\nThey started from scratch, so did not use the Parsel generator. Instead, they solved the problem and wrote their solution in Parsel, which was then synthesized into Python. \n\n> l212-216: I wasn't clear on why this is the conclusion from the human expert results\n\nThere were a subset of problems that were hard, such that we were unable to generate Parsel solutions to them by prompting the language model directly. However, when asking a human to generate a Parsel solution, they were able to solve multiple new problems. This suggests that the language is not the primary \n\n> nit Fig 4: it initially wasn't clear that 50 (Improved) was the Codex API and that this was the \"prior work\" you were referring to on line 145\n\nThanks for the point! The prior work that that’s from is [11], but we’ll make this more clear.\n\n> nit Fig 4: what is 5@50000?\n\nn@k is how AlphaCode referred to the pass rates, so they used this to refer to selecting 5 from 50,000 samples, and this was their highest-reported number. \n\n> It'd be helpful to have an example of mutual recursion. I see this is possible in theory but couldn't think of when this would occur and how common it is - why would two function implementations depend on each other?\n\nWe have one example in Figure 1, e.g., the recursive Collatz conjecture. In practice, this is surprisingly common and almost all cases of recursion can be expressed this way. For example, in our lisp interpreter, get_procedure calls eval_procedure which itself calls get_procedure. Similarly, eval_exp depends on list_case which depends on eval_exp.\n\n> How often are child functions shared between parents / called between different parts of the program? In cases where it is shared, it seems like it'd be helpful for the child description to be generated conditioned on all the caller descriptions (whereas from my understanding, the child description is currently generated conditioned on the description of the first caller). I could see this not being an issue for current code generation problems, but it seems like it'd be important in real-world programs.\n\nCurrently, children do not get information about their parents in their implementations. This has the additional benefit of caching: if you change only a function’s description, you do not need to regenerate its children. However, if a function has multiple children (i.e., depends on multiple functions) then all of those functions are listed.\n\n> Why is it sufficient to only consider strongly connected components?\n\nThe strongly connected components correspond to the sets of functions whose behaviors are mutually dependent. If two functions depend on one another, they must be implemented together and they will be in the same strongly connected component. If the functions do not depend on one another, then either 1) neither depends on the other or 2) one depends on the other, in which case we can implement the dependency first."}, {"review_id": "jlGs7fW2v4", "reviewer": "Reviewer_fDT5", "summary": "This paper proposes Parsel, a framework for algorithmic reasoning with LLMs. Parsel can be seen as a kind of “programming language” that is implemented with mostly natural language which describes the functionality of the program -- that is, the algorithmic reasoning plan. Then, the Parsel synthesizer can translate the plans into corresponding languages like Python. Finally, the reasoning problem can be solved by executing the synthesized Python code. All the processes are completed by analyzing the Parsel program and prompting LLMs. Experiments show that Parsel can improve the LLM’s coding ability and generate preferred robotic plans.", "questions": "1. Baseline settings are not well explained in figure 4: What does “codex improved” mean? The improvement relative to this baseline is very marginal.\n2. Does Parsel use test generation in the evaluation? Do baselines use it?\n3. Figure 1 shows Parsels ability in multiple languages, but the main paper only showcased Python, making figure 1 overstated.\n4. The github link is 404.", "limitations": "Limitations are discussed well in the paper.", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "1. Parsel reveals the power of hierarchical planning and decomposition for complex reasoning tasks.\n2. Parsel is a step towards a new kind of programming paradigm. That is, people can program more naturally with Parsel which lowers the programming barrier.\n3. Parsel might be a new kind of prompting method for complex reasoning tasks. Users (or LLM) can write a Parsel program first and then the Parsel synthesizer can automatically decompose the Parsel program into small function pieces and prompt LLM with these pieces, and the synthesizer should compose these pieces to form a whole function.\n4. The result on code generation is promising, although I still have some questions about it.", "weaknesses": "1. Although Parsel can be generated by LLMs, the Parsel synthesizer is not reliable for human users. When coding with Parsel and the synthesized Python code is wrong, users do not know whether the LLM for synthesizer is not working correctly, or if there are bugs in the Parsel code they wrote themselves.\n2. Also, there are no debugging operations provided in Parsel. Users cannot locate the bugs in Parsel, and they cannot debug on Parsel.\n3. The correctness of Parsel synthesizer relies on IO constraints heavily: It seems that IO constraints are the only guarantee for the correctness generation. This is a little bit weird because the main part of Parsel is the natural language description, which is where users spend a lot of time. However, to debug Parsel and ensure the final result is correct, a more effective approach is to provide more detailed and fine-grained IO or allow the LLM to just regenerate to meet IO, rather than making modifications to the natural language or code structure.\n4. The main experiment on APPS (figure 4) doesn’t seem like a fair comparison: Parsel is provided with detailed plans generated with GPT-3 while baselines are not. Providing results like “plans generated by codex (if possible)” “baseline results on GPT-3/4” or just more results with different budget settings on the “ablating the Parsel synthesizer” part would be good.\n5. Experiment settings are not clear, see questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful comments – the use of Parsel by human users was a key motivation, so these questions are really useful!\n\n> Although Parsel can be generated by LLMs, the Parsel synthesizer is not reliable for human users. When coding with Parsel and the synthesized Python code is wrong, users do not know whether the LLM for synthesizer is not working correctly, or if there are bugs in the Parsel code they wrote themselves… Also, there are no debugging operations provided in Parsel. Users cannot locate the bugs in Parsel, and they cannot debug on Parsel.\n\nWe absolutely recognize and acknowledge that there are changes that could be made to improve the usability for human users. Indeed, this is a direction we are actively pursuing. However, there are some useful debugging features already present. For example, because users can write constraints/unit tests, and the program is implemented from the leaves up, it is often clear which parts of the program are failing and which unit tests they are failing on. In other words, it is often unambiguous when functions are somehow underspecified, whether in language or in constraints. In addition, due to caching, errors are not generally stochastic.\n\n> The main experiment on APPS (figure 4) doesn’t seem like a fair comparison: Parsel is provided with detailed plans generated with GPT-3 while baselines are not. Providing results like “plans generated by codex (if possible)” “baseline results on GPT-3/4” or just more results with different budget settings on the “ablating the Parsel synthesizer” part would be good.\n\nThank you for this point! There are two things worth noting here (and also worth highlighting in the paper). First, the GPT-3 model we used and Codex are both based on the same model, which makes it somewhat less likely that any improvements come from GPT-3 simply being better (though clearly not a guarantee). Second, since the ablation highlighted in the paper clearly indicates that the intermediate plan is not sufficient for the observed performance improvement, we felt it would also be valuable to test whether it was necessary. We thus conducted an additional experiment where we skipped the plan generation step and instead asked Codex to generate Parsel directly. We observed that on a sample of 200 random competition-level APPS problems, generating Parsel directly from the problem solved 13% of them. Given that this is a more substantial improvement than the Parsel ablation, this suggests that, on this dataset, Parsel plays a larger role than the high-level plan, but both are necessary. Note that we used three few-shot Parsel examples for this experiment, as we observed that including many few-shot Parsel translation examples would result in it disregarding the problem statement, which for APPS is often quite long (e.g., a page of plaintext).\n\n> Baseline settings are not well explained in figure 4: What does “codex improved” mean? The improvement relative to this baseline is very marginal.\n\nCodex (Improved) refers to the version of Codex used in [11]. Unfortunately, it’s hard to make a direct comparison here - from 10 to 50 solutions, their performance improves from 6.3% to 14.5%. They do not report more than 50 attempts; however, in their CodeContests results, there is little improvement from 50 to 100 attempts (7.1% to 8.8%). It is, of course, difficult to extrapolate, but a corresponding improvement here would only represent a change of 3.5% – even with 3x this improvement, this would still underperform our result. We attempted to replicate their APPS results with Codex, but could not because 1) they do not provide their few-shot prompt and 2) we found we were rate limited substantially more often than when using Parsel and each generation took longer. This is likely because we were generating longer completions each time. This made replicating their results at the same scale infeasible, especially after we were unable to split up evaluation between members of the team following the new restrictions on Codex.\n\n> Does Parsel use test generation in the evaluation? Do baselines use it?\n\nIn the HumanEval comparison, we include test generation when we comparing to CodeT pass@1, using the same generated tests for both. In the APPS eval, we do not include test generation.\n\n> Figure 1 shows Parsels ability in multiple languages, but the main paper only showcased Python, making figure 1 overstated.\n\nThe two examples in Figure 1 correspond to the programming and robotic planning sections of the paper. In addition, we include examples of Parsel generating Lean (formal theorem proving) in the appendix.\n\n> The github link is 404.\n\nWe anonymized the GitHub URL to maintain anonymity. However, we released our code (indeed, we already have, and it is actively being used by others outside our team, with over 300 stars). We would include the de-anonymized URL in a camera-ready version.\n\n[11]  CodeT: Code generation with generated tests. (Chen et al. 222)"}, {"review_id": "wJOrUXXfFj", "reviewer": "Reviewer_9Jji", "summary": "The paper presents a system called Parsel for program synthesis. First, a LLM predicts a Parsel program given a task specification or natural language plan. The Parsel program contains a hierarchy of functions which themselves might have functions inside. Each function is described with a function signature, a natural language description of what it does, and sometimes constraints (e.g., I/O examples) and references to other functions to call. Then, the Parsel synthesizer attempts to translate the Parsel program into a traditional program, e.g., a Python program. The LLM generates multiple implementations of each function and a combinatorial search is performed to find combinations of implementations that lead to passing the constraints. Overall, the Parsel approach is shown to outperform directly generating solutions with Codex and AlphaCode on the APPS dataset of competitive programming problems, when controlling for the number of complete programs generated. Other experiments are performed on HumanEval (simple Python programming problems) and VirtualHome (robotic planning).", "questions": "## About the algorithm\n\nIf there is a function with constraints where none of the k implementations of the function pass the constraints, then what happens? I assume this causes the entire Parsel program to be unsuccessful, but this is not explicitly stated in the text. Does this lead to a tradeoff where, if the decomposition is too detailed with many individual functions, then there is a higher likelihood of a single function having no correct implementation? And, intuitively it seems useful to include constraints for all functions where the LLM can predict constraints confidently, but then more functions with constraints also leads to a higher likelihood of a single function having the wrong constraints. Can you comment on this “weakest link” issue?\n\nThere is an exponential blowup in the number of function implementation combinations. I understand that SCCs of the call graph and test dependency graph are used to reduce the number of functions considered at once, but still the exponential blowup remains. Do you impose some upper limit on the amount of combinations tried? Line 113 mentions *samples* -- when do you sample versus try all combinations, and how many samples are used?\n\nDoes a Parsel program always define a single outermost function that serves as the solution to the problem specification? This would make sense given the rest of the algorithm but is not explicitly stated.\n\nOnce we find an implementation for a function (or SCC) passing its constraints, is the implementation “locked in” permanently or does the algorithm also consider other implementations/combinations later? In other words, do we end up with at most 1 complete implementation for each Parsel program, which is then checked against the problem specification (possibly with hidden test cases)? Or, might we continue to search for other implementations of the Parsel program and evaluate those on the hidden tests too?\n\nThe CodeT score is a core part of the approach in the case of generated tests and is referenced repeatedly for the HumanEval experiments. The paper should provide some background on CodeT.\n\nI know that Appendix F contains Parsel pseudocode in Parsel style, which might clear up some of the questions above. I did not read that pseudocode (Figure A.11 and A.12) carefully because it’s a full page long, and I hope the authors can write a more succinct version in a more traditional style in the main paper. I also think Parsel programs are not as clear as actual pseudocode, because they lack detail about how inner functions are used to implement the outer function. It’s as if one had to understand how a Python program worked, but only seeing the function signatures, docstrings, and call graph... many important details would be lost.\n\n## About the experiments\n\nWhat I/O examples are given in the problem specifications, and are there held out tests used to evaluate the correctness of synthesized programs? The description of the experiment setup is lacking these kinds of details.\n\nIs it expected that the LLM can predict *correct* constraints in terms of I/O examples for individual functions? It is commonly observed that LLMs are quite bad at executing code or even performing arithmetic. I would expect that many constraints would have subtle errors that lead to incorrect implementations being selected from the search over function combinations. For example, is the constraint in Figure 2 (ii) directly copied from the problem specification, or does the LLM generate it from scratch? Can multiple constraints be added to a single function?\n\nLine 150 mentions that using the LLM to generate programs is much more computationally expensive than running programs on a CPU. This is certainly true in general. However, it is unstated how many programs are actually run (considering the exponential number of implementation combinations being considered), and Figure 4 appears to have a datapoint close to 1 million program evaluations per problem. Because APPS is a dataset of competitive programming problems, I’d expect many programs to have long-running evaluations, either from implementation errors (infinite loops) or suboptimal algorithmic design. Even if only 1% of programs run until timeout, the time limit is set to 1 second (a small time limit in actual competitive programming competitions), and we assume that all other programs evaluate instantly, then 1 million programs would evaluate for 2.8 CPU-hours, per problem. Such an amount of compute cannot be swept under the rug and should be discussed! Certainly from an end-user perspective, waiting several seconds for an API call to GPT-4 feels much better than waiting for multiple CPU-hours of program executions. Appendix E.3 does mention parallelizing program executions but the resulting wallclock time per problem is not mentioned.\n\nFor the HumanEval experiment, the writing is less clear about what the main conclusion or takeaway should be. For example, could you summarize Lines 175 - 194 in 1 sentence? The writing would be improved by adding that sentence, and cutting back on some of the details. Similarly, Lines 199 - 204 contain many details that are not useful for readers who do not dig up Parsel’s solutions to the problems mentioned.\n\nFor the VirtualHome experiment, it is not clear how to interpret the numerical results. Does Figure 7 say that the Codex (baseline) plans were the *most preferred among the 3 plans* roughly 30% - 35% of time, which is actually not bad for the baseline? How exactly does the comparison work, considering that Parsel has 2 attempts but the baseline only has 1? Does “X is 70% more likely to be preferred over Y” (Line 283) imply P(X preferred) = 85% and P(Y preferred) = 15% such that 85% - 15% = 70%, or something else? Why not just report P(X preferred) directly? What exactly does “X preferred” mean: “one of the 2 Parsel programs was better than the baseline”, or “the indented Parsel program was better than the baseline”?\n\nOverall I am less excited about the VirtualHome experiments because of the lack of rigorous correctness checking (instead relying only on rankings of accuracy and clarity). The example in Figure A.49 does not alleviate my concerns as the Parsel solutions seem much worse than the baseline’s solution, which itself is not completely correct either. What is the main takeaway from the VirtualHome experiments that was not evident from the other experiments?\n\nI know it is hard to investigate contamination issues considering the opacity of some LLMs, but the potential issue should be discussed in greater detail. For example, is it possible that GPT-3 has seen solutions to the APPS problems while AlphaCode and Codex have not? For the Lisp example (Line 354), it seems likely that the code LLM has already seen example implementations of the Lisp interpreter, and it recognizes the general patterns even without any mention of the word “Lisp” in the Parsel program.\n\n\n## Minor questions and suggestions\n* Line 99: “Parsel implements functions with **a** post-order traversal from **the** function at the root”\n* Figure 4 caption: a period is missing after “AlphaCode [35]” \n* Figure 4 caption: “we examine to understand the effect of evaluation number” is awkward phrasing\n* Line 165: missing space between “HumanEval” and “[12]”\n* Line 319: missing some punctuation (comma or period) between “model” and “and”\n* Line 347: missing space between $\\ge$ and 0.99", "limitations": "One undiscussed limitation is that Parsel likely requires more expensive LLM calls for the same effective number of complete programs sampled, for three reasons:\n\n1. Each transformation from task specification to the high-level plan and then to the Parsel program requires an LLM call, accounting for many tokens that would not be needed by the Codex baseline.\n2. Each function is implemented separately which requires encoding a different prompt for each function with function-specific context.\n3. The decomposition of the entire solution into many functions might lead to more total code tokens sampled compared to a solution obtained without explicit decomposition.\n\nThe paper could use some discussion about these factors, potentially summing the total LLM cost per problem for Parsel versus Codex.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "Originality: The Parsel language and overall approach is quite novel and creative, and in my opinion this is the paper’s biggest strength. Parsel’s motivation is clear: we want to decompose problems into multiple functions or groups of functions, such that each group can be implemented independently. However, it was previously not clear how this goal should be achieved, as it requires a planning step that decides how the problem should be decomposed. The Parsel approach nicely resolves this by providing a natural outline of the hierarchical decomposition, containing just the right amount of information to facilitate synthesis of individual functions, while allowing different implementations to be explored.\n\nQuality: The Parsel approach makes a lot of sense from a technical perspective. The experiments explore various aspects of Parsel.\n\nClarity: The motivation, intuitions, and related work are well written.\n\nSignificance: These results are quite significant themselves, and the problem being tackled (program synthesis) is important too.", "weaknesses": "In my opinion, the paper’s main weakness is the lack of a deep analysis of *why* Parsel has its good performance. The approach has many parts and it is unclear which parts are the really important ones. Here are some potential reasons why Parsel is good, and potential experiments to gauge the importance of those reasons:\n\n1. Predicting a **high-level sketch or plan** helps the model gain an overall understanding of the problem in a chain-of-thought kind of way, leading to better downstream predictions.\n\n    * Reason 1 is partially analyzed in Lines 156 - 164 (when Codex is given the high-level plan, it performs much worse than Parsel given that plan). But I’m also interested in the other kind of ablation: how well does Parsel do without the high-level plan, going straight from the task specification to the Parsel program (on the APPS dataset)?\n\n2. The **Parsel program itself** makes synthesis easier, since it contains a good decomposition with just the right amount of information for easy synthesis of the individual functions.\n\n    * What if we replaced the Parsel program with a Codex prediction of the entire solution, which we then use as an outline? Specifically, we prompt Codex to implement a code solution that is decomposed into helper functions with docstrings. (If a function is not generated with a docstring, we can prompt an LLM to predict a docstring given the function and other relevant context from the task.) Then we take the function signatures, docstrings, and references (call graph) from the solution to serve as a replacement for the Parsel program. Thus, we sample new implementations of the individual functions and search for implementation combinations as usual.\n\n3. The approach enables **trying many combinations of implementations** with a low cost (effective number of complete programs sampled).\n\n    * What if we disallowed trying multiple combinations of implementations, i.e., only used pass@n x 1?\n\n4. The authors might identify other potential reasons that I didn’t think of.\n\nBy including these sorts of ablations, we would get a much more clear understanding of the relative importance between these factors. This could help readers gain a deeper intuition behind why Parsel works, so they may better adapt or extend the approach in future work. Even though my rating is positive right now, I *strongly encourage* the authors to perform these ablations, because I believe the paper will be much stronger (an amazing paper) with a deeper analysis of Parsel’s core ideas.\n\nAnother weakness of the paper is that the writing could be made clearer about the algorithm and experiments. Please see the questions below.\n\nPlease note: I will be happy to raise my score if I think these weaknesses are adequately addressed in a revision.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you so much for the thorough and helpful review. We sincerely appreciate the attention to detail and the encouraging and supportive framing. Note we are constrained to 6,000 characters here (a new rule…), but are happy to elaborate during discussion.\n> I’m also interested in the other kind of ablation: how well does Parsel do without the high-level plan?\n\nGreat suggestion! On a 200-problem competition-level APPS sample we found that, without a high-level plan, the accuracy falls to 13% (from 25.5%, w/ the same configuration). This is better than the ablation where Parsel wasn’t used, suggesting that Parsel plays a larger role than the high-level plan on APPS but both are necessary. Note part of this improvement is from the challenge of prompting Codex to generate Parsel, given long APPS problem statements. We’ll include the new prompt in the Appendix.\n> What if we replaced the Parsel program with a Codex prediction of the entire solution?\n\nThis is an insightful proposal; we explored something very related. There are some challenges that initially limit its generality, many of which are solvable but collectively likely an entirely new work. The main ones are 1) extracting a call tree across many kinds of Python solutions and 2) getting Codex to generate meaningful standalone function descriptions. This may be possible by backtranslating generated Python solutions to Parsel (which does not require Codex to know anything about Parsel) – see Appendix K – but for these reasons there are many functions where that doesn’t work.\n> What if we disallowed trying multiple combinations[?]\n\nWe touched on this in Fig. 8, but it should be much more clearly signposted. We interpret the results to suggest that the number of Parsel programs and the number of combined implementations play similar important roles. In other words, one can compensate for implementation ability with Parsel-generation ability and vice-versa (to a limit).\n> [What if] there is a function with constraints where none of the k implementations of the function pass? … Once we find an implementation … is [it] “locked in”?\n\nThere are a few things that happen, depending on flags and context. By default, if no implementation passes the provided constraints, this is a failure. But, we also support backtracking (see Appendix S.2) - if enabled, if a parent fails to pass its constraints, it can reattempt its children - otherwise child implementations are locked in. When generating all tests and using CodeT scoring, then aside from some naive heuristics (e.g. a function with no passed constraints), detecting failure is difficult.\n> Is it expected that the LLM can predict correct constraints in terms of I/O examples for individual functions?\n\nNot necessarily – CodeT found that one doesn’t need all-correct tests to identify correct functions. It’s motivated by the Anna Karenina principle (“All happy families are all alike; each unhappy family is unhappy in its own way”): if many functions pass the same tests, one is likely correct.\n> Line 150 mentions that using the LLM to generate programs is much more computationally expensive than running programs... Do you impose some upper limit on the amount of combinations tried?\n\nGood point! We sample and test up to 100,000 items with a timeout of 0.04 seconds each, and also have a per-problem two minute limit – noted in Appendix M but we’ll highlight it. Note, if we’d used LLM-level compute per problem, this evaluation would’ve been near-instant (also easier to speed up evaluations via parallelization vs LM generation). \n> For the HumanEval experiment, the writing is less clear about the takeaway… Could you summarize in 1 sentence?\n\nExcellent point; “Given the same set of generated tests and program generation budget, and selecting only one best solution, Parsel significantly increases the probability that it’s correct.”\n> For the VirtualHome experiment, it is not clear how to interpret the numerical results.\n\nYou’re right, this is confusing and we’ll clarify. Each comparison is pairwise (not best of three). Figure 7 compares only the (non-hierarchical) Parsel-generated plan and the Codex-generated solution. In other words, “the non-indented Parsel program was better than the baseline” (and note there was no preference on indentation). I.e. when people compared non-indented Parsel to the baseline, they said it was more accurate two thirds of the time. \n> What is the main takeaway from the [VH] experiments[?]\n\nThere are two: First, they show Parsel's flexibility in handling more open-ended tasks beyond traditional code generation on an increasingly relevant LM reasoning domain. Second, they offer a chance to evaluate if the Parsel-generated plans are more clear – the results suggest they are. However, we strongly agree more robust metrics are needed in this emerging domain of LLM-based robotic planning.\n> [Is] it possible [GPT-3] has seen solutions to the APPS problems while AlphaCode and Codex have not? [T]he code LLM has already seen examples of the Lisp interpreter\n\nThey’re based on one model so, while it’s sadly hard to know for sure, it’d be a bit surprising if code data was used to train the text version but not the code version. As for lisp, good point – we’ll add this. But note, many descriptions are not obviously Lisp-related.\n\n1. *Does a Parsel program always define a single outermost function?* Yep!\n2. *The paper should provide some background on CodeT.* We'll be happy to elaborate in the related works.\n3. *I hope the authors can write [the pseudocode in a] traditional style.* We’ll revise Figure A.11 - also allowing a useful comparison of Parsel to traditional pseudocode.\n4. *What I/O examples are given?* For APPS and HumanEval, there are public tests in problem statements and private tests for evaluation.\n5. *Parsel likely requires more expensive LLM calls.* It depends! It’s discussed in App. S.6 but we agree that highlighting this clearly and discussing these costs more would be good."}, {"review_id": "Qw3150hgsH", "reviewer": "Reviewer_AJpS", "summary": "The paper proposes Parsel, a framework that decomposes algorithmic reasoning problems into subparts, samples programs for each subpart and verify them. To decompose a problem, Parsel transforms it into an intermediate language that describes the functionality for each subpart and how the subparts depend on each other. To sample programs, Parsel uses existing language models trained on code. To verify the subparts and the whole program, Parsel analyzes their dependencies and use existing test generation techniques.\n\nParsel is able to improve the performance in solving code problems and virtual robot control.", "questions": "I would love to see the answers to the questions in the Weakness section. I may consider raising the score if they are well answered.", "limitations": "The authors have addressed the limitations of their work.", "rating": 6, "confidence": 4, "soundness": 1, "presentation": 3, "contribution": 2, "strengths": "1. The overall idea of divide-and-conquer and verifying subparts is reasonable and intuitive.\n2. Using an intermediate language makes both the reasoning and parsing easier.\n3. The idea for involving human programmers to help in the loop is inspirational for designing better code assistants.", "weaknesses": "### 1. The comparison between Parsel and Codex (codeT improved) is not fair.\n\nTherefore, the claim on L145 that Parsel “substantially improves over prior work, from 14.5% to 25.5%” does not hold.\n\nIf I understand correctly, this comparison is demonstrated in Figure 4, where the number 14.5% comes from the blue point labeled **“50 (improved)”** and the number 25.5% comes from the green point labeled **“8x16”**. In my opinion, this comparison is unfair because of two reasons.\n\n- **First, the sample budgets are different.**\n    As claimed on L142, the comparison uses an “effective number of complete programs” to represent the sample budget. So the “50 (improved)” setting has a sample budget of 50 while the “8x16” has 128 sample budget. On the own interpolated green curve in Figure 4, Parsel’s performance at sample budget 50 is similar to that of Codex.\n\n- **Second, Parsel uses significantly more evaluation budget.**\n    Even if we ignored the first issue and assumed “50 (improved)” and “8x16” had the same sample budget, the comparison would still be unfair because of significant differences in evaluation budgets. “50 (improved)” achieved a pass rate of 14.5% with **50 evaluations**. While ”8x16” achieved 25.5% with **10^6 evaluations**.\n    I do understand that one advantage of Parsel is the ability to increase the number of evaluations without more samples, but it’s still unfair to compare the result from 10^6 evaluations with that from 50 evaluations. Because arguably, evaluation budget is more important than sampling budget in code generation, as a failed evaluation would result in penalty in programming competitions and crashes in real production. No one would want a code generation system that gets the correct program after 10^6 failures. It’s both unrealistic and unfair.\n    From the reported data, a fairer pass rate for “8x16” would be 4% (when the evaluation budget is 100), which is much worse than “50 (improved)”. To give more idea about how large a 10^6 evaluation budget is and how much improvement it gets, AlphaCode achieves >35% pass rate on CodeContests (Figure 8 from https://arxiv.org/pdf/2203.07814.pdf) with 10^6 evaluations and 6% pass rate with 100 evaluations. Judging from CodeT’s results, CodeContests is harder than competition-level APPS problems.\n    \nBecause of these two reasons, I find the claim on Parsel’s ability to solve more competition-level problems not reliable.\n    \n### 2. Lack of details and analyses on how verification of decomposed functions helps.\nParsel emphasizes the importance of decomposition of the problem into modular functions (components) and the verification of these functions.\n\nWhile decomposition can be justified by the exponential evaluation budget (though it creates unfair comparison) and the dropping pass rates when the number of chained components is large, how verifying these decomposed functions separately can help is not sufficiently justified, leaving several questions unanswered, to name a few:\n\n- **How are constraints (unit tests) generated for different components generated?** I understand that the test cases for the entire program is generated using CodeT, but how different components are verified is not clear.\n- **How many components have unit tests?** The paper claims that for test-less component functions, they can be tested with the test cases for the entire program. I wonder how many components actually have unit tests or if most of them are test-less.\n- **Are unit tests mostly correct?** If not, what is the point of using them instead of just using the general test cases?\n- **Do testing components separately lead to better perfiormance?**\n- **Do components that pass unit tests always build up to a correct program?**\n- **How much does partitioning the function reference graph into SCCs help?** The paper claims that for mutually dependent functions, grouping them into SCCs can help save some sampling budget. Does it really?\n    \nTo me, the results reported look like they are mostly from enumerating different combination of functions and verifying them using global constraints. The claim in your TLDR that the problem is decomposed into subparts and solved by “verifying subparts, and then composing them” does not seem well supported. It’s more like “enumerating the combination of subparts and then verifying them as a whole”.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive review and helpful questions!\n\n> As claimed on L142, the comparison uses an “effective number of complete programs” to represent the sample budget. So the “50 (improved)” setting has a sample budget of 50 while the “8x16” has 128 sample budget. On the own interpolated green curve in Figure 4, Parsel’s performance at sample budget 50 is similar to that of Codex.\n\nOverall we agree that Codex 50 (Improved) shouldn’t be directly compared to Parsel 8x16. We believe the scaling properties of Parsel exceed those for Codex, but unfortunately it isn’t possible to verify this with, eg “Codex (Improved) 128”. Codex (Improved) refers to the version of Codex used in [11]. Unfortunately, it’s also hard to extrapolate a comparison here. They do not report more than 50 attempts; however, in their CodeContests results, there is little improvement from 50 to 100 attempts (7.1% to 8.8%). It is, of course, difficult to extrapolate, but a proportional improvement here would represent a change of 3.5% – even with 3x this, it would still underperform Parsel. We attempted to replicate their APPS results with Codex, but could not because 1) they do not provide their few-shot prompt and 2) we found we were rate limited substantially more often than when using Parsel and each generation took longer. (This is likely because we were generating longer completions each time. This made replicating their results at the same scale infeasible, especially given the new restrictions on Codex access.)\n\n> Second, Parsel uses significantly more evaluation budget. … Because arguably, evaluation budget is more important than sampling budget in code generation, as a failed evaluation would result in penalty in programming competitions and crashes in real production… From the reported data, a fairer pass rate for “8x16” would be 4% (when the evaluation budget is 100), which is much worse than “50 (improved)”.\n\nA key motivation behind this paper is the usefulness of tests in generating and identifying useful programs (i.e., test-driven development). Ultimately, whether evaluation or generation is more expensive will depend on use cases, but if the goal is to find a program passing standard unit tests, the compute necessary for generating hundreds of tokens from a large language model is many orders of magnitude more than evaluating an APPS program. There are many such problems where verification is far cheaper than generation. As you mention, given a similar evaluation budget, Parsel performs worse with Codex: this should come as no surprise when it is a format for representing algorithms that Codex has never been trained on. If anything, the fact that Parsel can overcome this gap is noteworthy.\n\n> How are constraints (unit tests) generated for different components generated? I understand that the test cases for the entire program is generated using CodeT, but how different components are verified is not clear… How many components have unit tests? The paper claims that for test-less component functions, they can be tested with the test cases for the entire program.\n\nThere are multiple ways to generate constraints. First, one can just generate top-level constraints based on the task, as done in the original CodeT paper. We did this in the HumanEval experiments to make sure that the comparison to CodeT was fair. Second, in the case of human-written Parsel solutions, humans can write tests for relevant components. Third, some of the case studies, like the problem-solving example (Figure A.9), can be solved by generating constraints for all functions and applying the heuristic where we aim to maximize the minimum CodeT score of any function in an implementation. \n\n> Are unit tests mostly correct? If not, what is the point of using them instead of just using the general test cases?\n\nWe plan to include more discussion of CodeT [11] in the paper, but one of the key findings was that one doesn’t need all-correct tests to identify correct functions. It’s motivated by the Anna Karenina principle (“All happy families are all alike; each unhappy family is unhappy in its own way”): if many functions pass the same tests, one is likely correct.\n[11]  Codet: Code generation with generated tests. (Chen et al. 222)\n\n> Do components that pass unit tests always build up to a correct program?\n\nNot necessarily - the provided unit tests may not be comprehensive. As mentioned in Appendix S.2, one can also enable a backtracking flag, where a parent component will consider other implementations of child components if a solution cannot be found. However, we did not use this in the large-scale coding experiments, as these relied on unit tests only for the top-level functions.\n\n> How much does partitioning the function reference graph into SCCs help? The paper claims that for mutually dependent functions, grouping them into SCCs can help save some sampling budget… Do testing components separately lead to better perfiormance?\n\nIf n functions with m implementations have no mutual dependencies, or if the sizes of the SCCs are no more than c, then partitioning takes it from O(n^m) to O(nm) or O((n^c)/c m). So, for whether it leads to better performance, the answer is certainly: for some Parsel programs like the lisp interpreter (Appendix H), they would be virtually impossible to synthesize without the decomposed testing. For complex programs with many functions, it is infeasible to consider combinations of all of their implementations at the same time.\n\n> The claim in your TLDR that the problem is decomposed into subparts and solved by “verifying subparts, and then composing them” does not seem well supported.\n\nThis is a reasonable point. Given that the primary focus of the paper is not on the verification, but rather on the composition and decomposition, we would be more than happy to update the TLDR to “Language models can solve algorithmic reasoning tasks by decomposing them, solving subparts, and composing them.”"}]

Author rebuttal:
We thank the reviewers for their thoughtful, positive, and constructive comments! Your suggestions have helped strengthen the work and clarify key points. Based on the reviews, here are some of the main changes: 
1. We conducted a new ablation study generating Parsel directly from problems, ablating the high-level plan, in addition to the earlier ablation where we ablated the Parsel synthesizer. This lowered performance to 13% from 25.5% (on a random 200 competition-level APPS problems), showing that both the plan and Parsel decomposition are important.
2. We will clarify details and bring key information which is currently in the appendix into the main text, such as the number of evaluations and the mechanism behind CodeT [11].
3. We will highlight more key takeaways for the sections. For example, for HumanEval, we will note that “Given the same set of generated tests and program generation budget, and selecting only one best solution, Parsel significantly increases the probability that the solution is correct.”

Once again, we really appreciate the supportive feedback and strongly believe that these reviews have strengthened the work.

[11]  CodeT: Code generation with generated tests. (Chen et al. 222)

Meta-review: This paper introduces Parsel which is a framework for designing and implementing complex programs. Parsel has an intermediate language that is aimed at decomposing the task into simpler ones at a very high level that includes function description and potential constraints/test cases. This allows sampling and verifying code for individual components separately while handling dependencies. As a result, Parsel enables a clever sampling that makes it more likely for the overall program to be correct. Authors demonstrate this on multiple known benchmarks. I really enjoyed reading the paper and all reviewers unanimously voted for acceptance. Therefore, I recommend acceptance.
Decision: Accept (spotlight)