LILO: Learning Interpretable Libraries by Compressing and Documenting Code
Authors: Gabriel Grand
Lionel Wong
Matthew Bowers
Theo X. Olausson
Muxin Liu
Joshua B. Tenenbaum
Jacob Andreas
Venue: ICLR 2024 poster (2024)
Keywords: program synthesis
language models
library learning
compression
refactoring
abstraction
documentation
neurosymbolic
Primary area: neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
TL;DR: We introduce a neurosymbolic framework for program synthesis that integrates language models with program compression to learn interpretable libraries of reusable function abstractions.

Abstract: While large language models (LLMs) now excel at code generation, a key aspect of software development is the art of refactoring: consolidating code into libraries of reusable and readable programs. In this paper, we introduce LILO, a neurosymbolic framework that iteratively synthesizes, compresses, and documents code to build libraries tailored to particular problem domains. LILO combines LLM-guided program synthesis with recent algorithmic advances in automated refactoring from Stitch: a symbolic compression system that efficiently identifies optimal lambda abstractions across large code corpora. To make these abstractions interpretable, we introduce an auto-documentation (AutoDoc) procedure that infers natural language names and docstrings based on contextual examples of usage. In addition to improving human readability, we find that AutoDoc boosts performance by helping LILO's synthesizer to interpret and deploy learned abstractions. We evaluate LILO on three inductive program synthesis benchmarks for string editing, scene reasoning, and graphics composition. Compared to existing neural and symbolic methods—including the state-of-the-art library learning algorithm DreamCoder—LILO solves more complex tasks and learns richer libraries that are grounded in linguistic knowledge.

A dual-system synthesis module, which searches for solutions to programming tasks using two priors, and Published as a conference paper at ICLR 2024
LILO: LEARNING INTERPRETABLE LIBRARIES BY COMPRESSING AND DOCUMENTING CODE
Gabriel Grand Lionel Wong'
Maddy Bowers
Theo X. Olausson
Muxin Liu
Joshua B. Tenenbaum 1.2 Jacob Andreas'
MITT CSAIL
MIT Brain and Cognitive Sciences
Harvey Mudd College
ABSTRACT
While large language models (LLMs) now excel at code generation, a key aspect of software development is the art of refactoring: consolidating code into libraries reusable and readable programs. In this paper, we introduce LILO, a neu- rosymbolic framework that iteratively synthesizes, compresses, and documents code to build libraries tailored to particular problem domains. LILO combines LLM-guided program synthesis with recent algorithmic advances in automated refactoring from STITCII: a symbolic compression system that efficiently identi- fies optimal X-abstractions across large code corpora. To make these abstractions interpretable, we introduce an auto uutto-documentttion (AutoDoc) procedure that in- fers natural language names and docstrings based on contextual examples of us- age. In addition to improving human readability, we find that AutoDoc boosts per- formance by helping LII.O's synthesizer to interpret and deploy learned abstrac- tions. We evaluate LILO on three inductive program synthesis benchmarks for string editing, scene reasoning, and graphics composition. Compared existing methods including the state-of-the-an library learning algorithm DreamCoder- LILO solves more complex tasks and learns richer libraries that are grounded linguistic knowledge.
INTRODUCTION
Large language models (LLMs) are growing highly adept at programming in many settings: com- pleting partially-written code (Chen al., 2021; Fried al., 2022; Li et., 2023), conversing with human programmers (Austin et al., 2021; ; Nijkamp et al., 2023), and even solving competition-level programming puzzles (Hendrycks
al., 2021; Li et al., 2022: Haluptzok et al., 2022: OpenAI, 2023). However, beyond solving the immediate task at hand, software engineers are concerned with building libraries that can be applied entire problem domains. To this end, a key aspect of software development is the art of refactoring (Brown et al., 1998; Abrahamsson et al., 2017): identifying abstractions that make the codebase more concise (consolidating shared structure), reusable (gen- eralizing to new tasks), and readable (intuitive to other programmers). Solving this multi-objective optimization will require broadening the scope of existing code completion tools are already used by millions of programmers to approach the problem of library learning.
In this paper, we combine language models with recent algorithmic advances in automated refactor- ing from the programming languages (PL) literature leam libraries of reusable function abstrac- tions. We introduce LILO, a neurosymbolic framework for Library Induction from Language Observations, which consists of three interconnected modules (Fig. 1):
distinct methods: LLM LaM-eddded search imbues the system with strong enumerative search enables the discovery of domain-specine expressions;
A compression module, which identifies useful abstractions from the existing solution set via STITCH (Bowers et al., 2023), high-performance symbolic compression system;
An auto-documentation (AutoDoc) module, which generates human-readable function names and docstrings, yielding better interpretability and improving downstream I.L.M- search.
Correspondence ggêmi edu. Code for this paper is available gi thub. com/ gaabgrand//ilo..

---

Published as a conference paper at ICLR 2024
(A) Language-guided program synthesis
How many red objects there?
s8 erpty (A
(ec. color red (query, color 51/
Rdd 51 50) 58)22)
y; 3
What shape is the object to the right of the green cylinder?
guiddd search over
(query shape (cer (relate (car fold
folld 50 exrptyy (X (2
<1f tea_shape cylinder (query_color 51)
(edd 52 56) 58))))
Y2= sphere
right 58)1))
you removed the purple objects, how many spheres would be left?
[count (difference (fold s3 expty (A
Enumerative search over program spoce
99) 583322 Equery_shage 511)
empty (A
(1f (eq,
(eq_eolor color purple (query color 51)
- Yy 0
(add 51 56) $821)3331
(D) Rewritten programs
(C) Library AutoDoc
(B) Stitch compression
(A (count
Filter by color
coler a cc)jess) >> (ab/ect)
fa_e (A. O (fold 50 eapty (A (eq_calor
(rittter_yy_cooo _yy_o red (8))
teuary_color $1) $3)
56) 59313333
(A (query_shape (car (relate (car (filter, by color green (fitter_ by_ shape cyLinder 58)))))
Filter.
shape >> (octenteect; >> (onject)
fe_1 18 (A. O (fold so enpty (query shape $3) 50) 593))3)}
(A
$8)))
renaiininn sarpiinnng.ooooo ects, bt.cyyyccccoo.... color..
(count, rew.eeinnaannnnnnn caaniingooffftte byy_color_and_ _nn_______sppeeee shape purple sphere)
phape
fn_2 (A O (A (count
Counc number el ofjectica spectied
(eifference (fn_ 80 52)1)13)
the after of
Simplified programs Interpretable
synthesise
Generates nomes documentation
A absstrcctiooss encopsulate logic
Figure 1: Overview of the LILO learning loop. (A) LILO synthesizes programs based natural language task descriptions using dual-system search model. To refactor compression algorithm called STITCH (B; Bowers et al., 2023) with -enerraed auto auto-documentation (C) to produce an interpretable library of >-abstractions. This searchhcompress-eeeee compress-document loop simplifics the structure of program solutions (A vs. D), making it easier to solve more complex tasks on future iterations.
program solutions, LILO integrates
Our architecture draws inspiration from DREAMCODER (Ellis al., 2021), iterative Wake-Sleep algorithm that alternates between searching for solutions to programming tasks (Wake phase) and refactoring shared abstractions into a library (Sleep phase) that in turn helps guide search. Unlike standard deep learning approaches, DreamCoder can make strong generalizations from just hand- ful of examples, and the model's conceptual knowledge is represented symbolically in the learned library. However, DreamCoder's search procedure is extremely computationally intensive, requiring more than two CPU-months just learn a single domain (see Ellis et al., 2021, Apx. J). Much of this search time is spent "getting off the ground": discovering a basic set of abstractions that human programmers typically already know, or might be able to grok quickly based on having solved prob- lems in other domains. Moreover, DreamCoder libraries not necessarily interpretable, requiring both domain expertise and knowledge lambda calculus to decipher.
To address these issues, LILO leverages LLMs in two novel ways: (1) expedite the discovery of program solutions during search, and (2) to improve the interpretability of learned libraries through documentation. We evaluate LILO against language-guider DreamCoder variant three chal- lenging program synthesis domains: string editing with regular expressions (Andreas et al., 2018), scene reasoning on the CLEVR dataset (Johnson et al., 2017), and graphics composition in the 2D Logo turtle graphics language (Abelson & diSessa, 1986). On all three domains, LILO solves more tasks than DreamCoder and learns empirically richer libraries containing abstractions that are intractable to discover with existing methods. For instance, LILO learns the concept of a vowel key stepping-stons in the string editing domain that would otherwise require searching over 26 possible disjunctions of character primitives. Unlike LLMMonly baselines which can solve similar tasks-LILO compresses this knowledge into symbolic abstractions that are useful for both traditional search methods and LLM-guided synthesis. Key to this neurosym- bolic integration is our AutoDoc module, which not only improves interpretability, but also helps the library more effectively. LILO illustrates how ideas and tools from the
(Fig. 2), which
the LLM synthesizer PL community can be integrated with recent breakthroughs in language models, representing a new evolution in long line of work in inductive program synthesis, which review below.
2

---

Published as a conference paper at ICLR 2024
2 PRELIMINARIES PROGRAM SEARCH AND LIBRARY LEARNING
Program synthesis. In inductive program synthesis (Gulwani al., 2017), we given a library of primitives & = { f2.... that forms domain-specific language (DSL). For a given pro- gramming task
{Iit specified as a of input-output pairs, the goal is to find a program : (z,) = Ye that correctly maps all inputs to outputs, denoted + t. However, a typical task admits many such solutions that will not necessarily generalize (for instance, a simple lookup table). To address this inherent under- snder-specification. concern is given to finding an optimal program Ā H t with respect to descriptive complexity (Solomonoft, 1 1964; Kolmogorov, 1965; Chaitin, 1966). This optimization is naturally framed in terms of probabilistic inference:
arg max p(T f,, f) arg max (logp(t 1)) + log | [)]
(1)
x
In a typical setting, the likelihood p(t x) _ 1 is computed via program execution, while the
prior p( L) & Is P(f L) is defined under a probabilistic context free grammar (PFCG; Johnson, 1998) that assigns a weight 0 < < 1 to each production rule. This is equivalent to a weighted description length prior, where longer programs have lower probability.
historically, approaches to Eq. have inevitably involved enumerative search through combinatoral space of programs. A range of techniques have been proposed to improve search tractability, including type-directed synthesis (Polikarpova
This formulation highlights the central challenge of program synthesis:
al., 2016), Monte Carlo approximation (Liang et al., 2010; Allamanis et al., 2018; Shin et al.. 2019), and neural network guidance (Gulwani et al., 2015; Balog et al., 2017: Parisotto et al., 2017: Devlin et al., 2017; Nye et al., 2019; Ellis et al., 2021). However, even with these methods, traditional program synthesis hinges critically on DSL design. Omission of key primitives can make complex tasks unsolvable, while inclusion of extraneous primitives can make search intractable. Consequently, DSL engineering is painstaking process that requires significant expertise to anticipate common patterns across tasks in a domain.
Library learning. While classical approaches focus synthesizing the best program for task specification given a fixed DSL (as in Eq. 1), programmers in the wild are typically concerned with solving entire problem domains. Given the difficulty of manual DSL engineering, natural evolution is to include C itself as part of the optimization problem. This is the main intuition behind library learning methods (Liang et al., 2010; Dechter et al., 2013; Lake et al., 2015; Shin et al., 2019; Lázaro-Gredilla et al., 2019; Ellis et al., 2018; 2021), which start with a collection of tasks T (4,, l2, and base library Lo. and jointly infer an expanded library L = Lo U (Ji,.... Sk) that includes additional abstractions fo built from Co (Fig. IB) and programs II = { 2 written terms of L:
arg max log PIII CT = arg max II,C
Σ LET
log p(t T)) + log p(T. 2) + p(c Lo) (2)
II,C
This objective carries over the program prior and likelihood from Eq. 1, but introduces distribution over libraries p(C | Co), typically also defined in terms of description length. Intuitively, Eq. 2 is optimized by inventing abstractions that are both reusable, simplifying the solutions multiple tasks in T; and concise, idcally building on one another hierarchically so as to share logic. Ellis et al. (2021) approximate Eq. via coordinate ascent, alternating between a search step, which holds the library fixed and searches for task solutions 11, and a refactoring step, which extracts common structure from the solution set to update L. The tractability of this approach hinges critically on the ability to do efficient refactoring, which we discuss further in $3.
Leveraging language guidance. Given the size of the search space, generic priors such as de- scription length are not always sufficient to solve Eq. 1; for this reason, a line of work considers natural language task descriptions de as an additional source of learning signal (Manshadi et al., 2013; Raza et al., 2015; Shin et al., 2019). Traditionally, making use of such descriptions has quired learning a domain-specifie semantic parsing model (Liang et al., 2011; Artzi & Zettlemoyer, 2013; Chen & Mooney, 2011). More recent work (Rahmani et al., 2021; Yin et al., 2022; Zelikman et al., 2022) uses LLMs, which excel when L resembles a common programming language that is well-represented in pretraining.
In library learning settings- where C is novel by construction it is currently less clear how to leverage language. In LAPS (Language for Abstraction and Program Search), Wong al. (2021)
3

---

Published as a conference paper at ICLR 2024
generalize Eq. condition dg by fitting inverted "program to-language" translation model. However, learning this mapping from scratch necessitates the use of a small alignment model (IBM Model 4; Brown et al., 1993) that makes strict token-to-token decomposition assumptions. In LILO, we take the opposite approach: we start with a large model that already has strong priors over the joint distribution of language and code; then, adapt the library to resemble this distribution by building up contextual examples and documentation. In contrast to simply picking a more common C (e.g., Python) work in, this procedure enables us to learn new L on-the-fly that is both optimized for the domain and grounded in natural language.
3 LILO: LIBRARY INDUCTION WITH LANGUAGE OBSERVATIONS
Our method, LII.O, aims combine the strong inductive search biases encoded by LLMs with the key ideas from classical methods in library learning learning-namelyy nnmelly the ability to discover new symbolic abstractions through refactoring. Algorithmically, LILO (Alg. 1) has a similar structure to existing approaches that optimize Eq. 2 via coordinate ascent, alternating between search and refactoring. However, unlike prior work, our use of LLMs for search necessitates an additional step-AutoDoc AuttDDoe- to render the learned abstractions legible to the synthesizer. We detail each of these modules below.
Dual-system program search (Fig. 1A). Inspired by dual process theories of cognition (Sloman, 1996; Evans, 2003; Kahneman, 2011), LILO is equipped with two distinct search procedures. We use a L.MM as a "fast" approximate search model in string space that leverages strong inductive biases learned in pretraining. After this first pass, we perform "slow" enumerative search in program space, using a task-conditioned PCFG inferred by a "recognition network" for guidance. We focus here on LLM-guided synthesis and refer to Ellis et al., 2021 (Apx. E and for details on enumeration.
Formally, we write (1 x) to denote the distribution over strings y produced by a language model prompted with string x. Then, for some target task i, our goal is to approximate the condi- tional distribution over programs
p(T+ C, II, d,) PLLM((TT)
(ffefeee (
II) (de)
lihrary
program examples
task desc.
where (...) and denote string serialization and concatenation, respectively. To sample from the distribution in Eq. 3, we procedurally construct few-shot prompts consisting of three parts: (1) A library description that enumerates the available primitives and any learned abstractions, (2) a set pairs (de, TT) ~ II sampled from the set of solved tasks, and (3) a description the target task dz. For each completion, we run parsing. type inference, and execution checks to identify valid programs that solve the target task. (Appendix A. illustrates the composition of a typical prompt; A.3 contains additional details on how examples are sampled.)
of exemplars consisting of description-solutee
Refactoring via Stitch compression (Fig. 1B). As the learner solves more tasks, the solution set will grow to contain many recurring program fragments that we wish to refactor into a set of reusable abstractions. In library learning systems that rely on enumeration, refactoring improves search ef- ficiency by avoiding the need to rediscover key building blocks for each new task. Analogously, in
Algorithm 1 Library learning loop with LILO
1: function LILOLEARNING(C..7 T)
2: + Lo
b Initialize librury with base DSL b Initialize task solution set
3:
II < [L: ()
4:
for I,...,N N do
5:
for E do
Run LLM Solver
6:
II. + II. ULLLM(TTSPPrompt(C.III de)) π U-TTTEEACCHCC
7:
b Run enumerative search (skipped in Search)
8:
(fi....,fe) fE) + COMPRESS II, C Lff
GGneraae new abstractions
9:
11 (I
11:
for a E (ff..... Jr.. do
b Document abstractions (skipped in '< AutoDoc)
- add_doca (ec_ddocs(_,coo (
return CT
Return final library and task solutions
4

---

Published as a conference paper at ICLR 2024
(A) Anonymouss abstraccions from Stitch
4n_42 1: tsubstr
(or 'a' for "e"l (er 's" (er 'o" (u1)333
4n 1: tfullstr +> tsubstr => tsubstr >> -fullstr
(A <A (A (flatton (иар (A (ff (match $1 $0) 92 9:)) (split enoty_soring 92)3)33>
fn_51 tsubstr <> toubstr tsullstr tfullstr
@ (fr 4
42333))
Pleese write huson-readoble nove description
(fn_42) vowel_regen reeeee 11 tsubstr
42, Here are sone excaptes of its usage:
Regular expression that matches any vowel ('a', fel, lo, V1 Used various functions identily and modily words based on vowel presence and position. for fa" for 'e" for 14' for to" 1u/1333
if there is yowel replace that with s
(h (fn_43 43 5o ts" fn_42))
(F there is consonant add s ofter that
(fn_43) replace, substr :: tfullstr -> tsubstr tsubstr -> tfullstr
(A (fn. 49 'sl (not fn_42) 50))
<r the word storts with vowel replace that with fn_4
Raplaces all instances agjven substring a fullstring 50 another substring 52..
0. (Mattee (Nap (A (motch 20) 50)) (aplit emply,str ing 9233)))3
Plecse write a husor-reodible nase and description for 4n_42, Here are sone exoxples of its usoge:
(fn_44) replace, ficst_occurrence
if there is replace that with
(A (fn_43 'y" (d"))
(fn_47) replace, 1f_ sf_eatch__ubstring
replace (A (fn_43 (concat 'kk 't!) "11))
if there
with
(fn_51) replace, wonsonant. sertonant.vith__.g
:: tsubstr >>
tsubstr >> tfullstr tfullstr
if there is consonent reploce that with (A (fn_43 50 'p' (not vowe regex)))
Replaces the first occurrence of consonant the begininggf given string with specified substrinn...
Please write Ausor-reodable noxe descrtatton.
521 (eot vonal (1g0))))3)
subetrinng Creplace, reserrncturrecc
(B) LILO AutoDoc prompt sequence
(C) Human-readoble library
Figure 2: LILO library auto-documentation (AutoDoc) workflow in the REGEX domain. For each Stitch abstraction (A), we prompt an instruction-tunee LLM with usage examples from solved tasks (B) to generate a human-rcadable name and description (C). The chat-style structure of AutoDoc allows naming choices to cas- cade sequentially; c.g., and other named abstractions in consistent and interpretable manner.
wwwettitthhhutttt wwthubsstring (fn_51) refers back to vowel_regex (fn_42)
LILO, refactoring makes the generation task easier: a LLM equipped with a library of abstractions can deploy entire blocks of code with just few tokens. Additionally, refactoring helps to mitigate LLM context window limits by minimizing the description length of the few-shot examples.
Various algorithms for refactoring have been proposed using combinatory logic (Liang et al., 2010), tree substitution grammars (Allamanis & Sutton, 2014; Allamanis et al., 2018; Shin et al., 2019). version spaces (Lau & Weld, 1998; Ellis et al., 2021), and e-graphs (Cao et al., 2023). In LILO, we cast refactoring as a compression problem over a corpus of programs
COMPRESS(II) arg min [/| + Σ |REWRITE(T)] L
f
EU(S)
wEIl
where the goal is to identify abstractions with minimal description length [f] that facilitate efficient rewriting of II. However, performing even a single round of compression as in Eq. 4 necessitates an efficient search strategy. In LII.O, leverage recent algorithmic advances from STITCH (Bowers et al., 2023): a symbolic compression system that uses branch-and-bound search to identify reusable abstractions in large datasets of lambda caleulus programs. While Bowers et al. demonstrate that Stitch is 1000-10000x faster and 100x more memory efficient than DreamCoder's compression algorithm, prior analyses were limited static corpora of ground truth programs. In LILO, we deploy Stitch for the first time in a synthesis loop and find it similarly performant, typically running in seconds on single CPU. These efficiency improvements enable us re-derive the entire library from Lo at every iteration (Alg. 1 line 9). While many abstractions remain stable across iterations, this "deep refactoring" allows LII.O to discard suboptimal abstractions discovered early in learning-
Library auto-documentation (Fig. 1C). Unlike traditional program synthesis methods, language models draw inferences about the semantics of programs from their lexical content. In other words, LLMs (like human programmers) care what functions are named. However, PL tools are typi- cally not equipped to write human- readable function names, instead outputting anonymous lambda abstractions (in Stitch, these are represented numerically; e.g., fn_42). In early experiments, observed that naively providing a LLM with Stitch abstractions measurably degraded its ability to solve tasks 1$4.1). We hypothesized that rewriting program examples in terms of these anonymous
5

---

Published as a conference paper at ICLR 2024
lambdas during the compression step (Eq. 4) was acting form of code abfuscation (Srikant et al., 2021: Zeng et al., 2022; Miceli-Barone et al., 2023).
Motivated by these findings, as part of LILO, introduce library nuto-documentattio (AutoDoc) procedure that writes humannreadable names and doestrings for abstractions generated by Stitch. AutoDoc leverages the fact that LLMs are naturally suited to code deobfuscation (Lachaux al., 2021; Sharma et al., 2022; Cambronero et al., 2023). During AutoDoc, we sequentially prompt an instruction-tuned LLM to produce a human-readable name and docstring for each abstraction in the library. Fig. gives an overview of this workflow (the full prompt is reproduced in A.2). In this ex- ample in the REGEX domain, the LLM has solved some problems that require vowel substitutions. During compression, Stitch pulls out the expression (or 'a' (or 'e' (or 'i' (or 'o' "u' )))))) for occurring commonly in the solution set and deñness it as an anonymous arity-O function (i.e., a constant). Subsequently, AutoDoc names this abstraction vowel_regex, which forms the basis for more complex expressions. For instance, consonant is expressed as (not vowel_ vowel_regex), which in turn supports an abstraction for consonant replacement. In $4, we explore how AutoDoc benefits downstream synthesis performance, yielding both richer and more interpretable libraries.
4 EXPERIMENTS AND RESULTS
Domains. Our goal is to build a system that can develop expertise in novel technical domains and leverage natural language guidance to bootstrap learning. We evaluate approach three induc- tive program synthesis domains: string editing (REGEX), scene reasoning (CLEVR), and graphics composition (LOGO). Detailed descriptions and metrics pertaining each domain are provided in B.I. These three domains were introduced in LAPS (Wong et al., 2021) as more challenging ver- sions of the domains evaluated in DreamCoder and our evaluations are directly comparable to prior results (B.3). Following Wong et al., we use synthetic ground truth task descriptions in our primary experiments and evaluate on noisier set of human language annotations in B.4.
Experiment setup. Our experiments are designed to simulate a "lifelong learning" setting where the learner starts from small seed set of simple examples that it must generalize to solve a broader set of training tasks that range in complexity. Performance is measured as the percentage of tasks solved from an i.i.d. test set. We sequentially perform two experiments that test different aspects of models' learning. First, in online synthesis, each model runs for a fixed number of iterations, continually updating its library (if applicable) and attempting to solve test tasks. These experiments serve general benchmark of aanguage-guides synthesis capabilities. Next, in offline synthesis, we freeze the final library C from each online synthesis run and perform enumerative search with no language guidance for a fixed time budget. (To compare against non-library learning baselines, we run STITCH to generate L post-hoc.) We hold the hyperparameters of the search fixed so that performance depends entirely Ls and not on the original model. Thus, the offline synthesis evaluations provide a controlled comparison of the off-the-shelf utility of different learned libraries in the absence of language guidance. Throughout, comparisons between models are expressed in terms of absolute percentage point changes in mean solve rates on the test set.
Implementation details. For LLM-guided search, we queried OpenAl's Codex model with up to 4 prompts per task, sampling 4 completions per prompt. For AutoDoc (which requires significantly fewer queries) we found that OpenAl's newer instruction- tuned models 3. 5-turbo and gpt-4) better adhered to the AutoDoc task and schema. Further implementation details can be found Appendices A.4-A.5.
4.1 EVALUATION OF SYNTHESIS PERFORMANCE
We compare LILO against two baseline models: language-guide DreamCoder variant from Wong et al. (2021) and a language model (LLM Solver) that does not perform library learning (Fig. 3). To study the effects of the different LILO components, we introduce ablated variants that remove the enumerative search and/or AutoDoc steps. To ensure fair comparison and improve overall runtimes, Stitch is used the compression module for all library learning models, including the DreamCoder baseline. Tab. 1 gives the full breakdown of task solution rates.
We accessed Codex through OpenAl's free beta program for researchers, which saved thousands of USD over the project lifetime (see C.1) and afforded higher rate limits than paid GPT models. To preserve repro- ducibility, make all LLM generations available at: gi thub, com/gabegrand/lliii

---

Published as a conference paper at ICLR 2024
CLEVR
LOGO
Tasks solved (%)
Split test
25
Model
LILO
0
3
6
9
12
15
0
3
6
9
0
6
LLM Solver
DreamCoder
100
Split
Tasks solved (%)
test
75
Split train
train
50
25
9 12 15 Iteration
Iteration
Iteration
Figure 3: Learning curves during online synthesis. Within each plot, the x-axis tracks the experiment iter- ation and the y-axis shows the percent of tasks solved (top test, bottom train). Error bars show standard deviation across randomly-seeded runs.
REGEX
CLEVR
LOGO
MODEL
TRAEEE
mico
std
std
maG
mea
sid
DreamCoder
45.60
43.93
1.53
97.09
94.50
2.44
36.94
28.53
13.79
LLM Solver
90.00
76.13
12.04
90.29
88.67
1.48
41.44
32.13
8.07
LLM Solver Search)
91.20
76.60
13.02
97.09
96.41
0.56
45.05
37.84
6.80
LILO (ie Search AutoDDoc)
59.40
53.20
5.38
93.20
85.76
9.72
45.05
21.02
20.88
LILO (>< Search)
63.80
62.93
1.50
94.17
88.03
8.26
30.63
21.02
9.46
LILO
93.20
77.07
14.14
99.03
96.76
3.12
73.87
48.95
22.15
Base DSL
22.00
22.00
0.00
29.13
29.13
0.00
0.90
0.90
0.00
DreamCoder
42.00
41.60
0.40
94.17
91.59
2.97
36.04
30.63
7.85
LLM Solver'
48.60
43.00
5.17
91.26
89.64
2.02
36.04
27.33
7.56
LLM Solver Search)
63.40
55.67
7.51
91.26
89.00
3.92
28.83
27.63
1.04
LILO (<r Search / AutoDoc)
60.80
50.73
95.15
93.85
2.24
51.35
30.63
18.22
LILO (>< Scarch)
57.60
56.20
2.25
96.12
95.79
0.56
28.83
26.13
3.25
LILO
71.40
64.27
6.31
96.12
92.56
6.17
50.45
41.14
8.66
Table 1: Task solution rates for online (upper) and offline (lower) synthesis experiments. We report the best (max), average (mean), and standard deviation (std) test solve rates across model runs. In each mean column, results within la of the best (bold) result underlined. *Asterisk indicates L, computed post-hoc.
LLMs facilitate effective search lambda calculus programs. Our first question is whether the LLM-based search procedure introduced $3 can match the accuracy of enumerative search. Compared to DreamCoder, we find that the LLM Solver, with no library learning, performs signif- icantly better on REGEX (+32.20)) slightly worse on CLEVR (-5.83), and comparably on LOGO (+3.60). The improvements on REGEX are primarily attributable LLMs' ability to generate expressions for concepts like vowel and consonant that invoke prior knowledge.
LILO achieves the strongest overall performance. As observed Fig. 3, LILO significantly outperforms DreamCoder on REGEX (+33.14) and LOGO (+20.42). It also achieves small im- provements on CLEVR (+2.26), though the DreamCoder baseline is already quite high for this domain (μr 94.50, = 2.44). Moreover, LILO also improves on the LLM Solver baseline by +0.94 (REGEX), +8.09 (CLEVR), and +16.82 (LOGO), key advantage of LILO is the ability to perform enumerative search, which aids in the discovery novel programs that differ structurally from existing solutions in the LLM prompts. To isolate the effects of search, we ran an ablation augmented baseline [LLM Solver Search]]. We find that enumerative
[LILO Search] as well search is most helpful on LOGO, which requires certain domain -omain-specific program structures (c.g., how to draw "snowflake" "staircase",, see Fig. 5) that are difficult to infer from language alone.

---

Published as a conference paper at ICLR 2024
REGEX
CLEVR
100
Model
UIO (No Search)
ULO (No Search AutoDDc)
40
60
30
Salver Search)
Taoks
20
40
20
20
10
Base DSL
DreamCader
Salver
Library
Learned
10
10 Search time (seconds))
100
10
10"
10"
10"
10a
10" Search time (seconds)
10"
10
Post-hac
Search time (seconds)
Figure 4: Evaluating library quality via offline synthesis. We run timed enumerative search (x-axis; note the log-scale) with the final library L, learned by each model online synthesis or inferred post-hoc. In this setting, LILO'S Ly expedites discovery of test task solutions (y-axis) even without language guidance.
Auto-documentation unlocks effective contextual usage of abstractions, Early experiments inter- facing the LLM Solver with Stitch [Tab. I, LILO (< Search AunoDoo]] revealed a puzzling finding: pro- viding the LLM with abstractions did not help-ann in some cases, significantly hurt- dort--donstteam synthesis performance. Relative to the LLM Solver baseline, we observed solution rate changes -30.60 (REGEX), 2291 (CLEVR), and -11.11 (LOGO) after introducing Stitch compression. Qualitative inspection found that GPT struggled to deploy anonymous abstractions in contextually- appropriate ways, which motivated ing AutoDoc [Tab. 1, LILO (x Searchi], we see mean improvements of +9.73 (REGEX) and +2.27 (CLEVR) over the naive condition. On LOGO, AutoDoc does not improve performance (--0.00). We attribute this to the occurrence of semantic errors, which we analyze further in $4.2.
exploration of de-obfuscation methods ($3). After introduc-
LILO rivals symbolic search in terms of computational efficiency. Compared enumerative search, we find that we are able to achieve faster overall wall clock runtimes with LLM-based search due orders of magnitude better sample efficiency (see C.I). Indeed, in terms of dollar cost, we estimate that one round of LLM synthesis is equivalent to 48 CPU-hours of DreamCoder search. Of course, L.LM-based and enumerative search are not mutually exclusive: our main LILO variant integrates both of these procedures and achieves the highest solve rates of all models we evaluated. Our findings make a strong case that LLMs can reduce the need for exhaustive search in synthesis domains where language annotations are available.
LILO libraries generalize well even in the absence of language. In our offline synthesis experi- ments, tested each model's final library Ly in an off shetthh-shelff setting with no language guidance. Fig. 4 shows the results of these evaluations (metrics are given in Tab. 1, lower). As the baseline for each domain, measure synthesis performance in Lo (Base DSL). As expected, we can sig- nificantly outperform Lo using library learning: DreamCoder's L, improves on the Lo solve rates by +19.6 (REGEX), +62.46 (CLEVR), and +29.73 (LOGO). Moreover, in each domain, LILO'S L improves further on DreamCoder, showing solution rate gains of +42.27 (REGEX), +63.43 (CLEVR), and 4-43.24 (LOGO) over Lo. LILO'S , also outperforms libraries derived post-hoc from the two LLM Solver baselines, highlighting the benefits of performing compression and docu- mentation in-the-loop. As these results demonstrate, LILO learns high-quality libraries that general- ize well to downstream synthesis tasks and can be used even in the absence of language guidance.
4.2 QUALITATIVE ANALYSIS OF LIBRARY ABSTRACTIONS
In all three domains, the libraries learned by LILO exhibit examples of compositional and hierar- chical reuse. For instance, in the LOGO library (Fig. and B.2.3), the top abstraction is a gen- eral method for drawing polygons that is invoked by several higher-level abstractions. Similarly, the CLEVR library (Fig. and B.2.2) contains two layers of abstractions: a lower layer imple- ments filter operations over size, color, shape, and material attributes that support higher layer of more specialized abstractions for counting and filtering. These examples showcase how LILO builds of the main strengths of DreamCoder the ability to bootstrap hierarchies of learned concepts-vve while improving the richness and interpretability of the learned libraries through auto- documentation.
While the GPT models do a remarkable job at inferring program semantics, we observe various cases where they produce unclear even incorrect documentation. For instance, in LOGO (Fig. 5),
8

---

Published as a conference paper at ICLR 2024
(fa_27) turtte_
3
Rapestedi move andiotaat by spectied angl, creating loop alaspeciicc
"a small triangle"
imoler
X Hover and intstecthens the a koep with each hevation doubling the length tfe tartie's moverrent
[fn 24) double, langth, Loop_nove, rotate 1: fnt turtte turtte
A
0
0
medium square"
(fn_33) [1] t'e snowt Il Lake, th,
turtle -> fet -> int -> tur surtle
X Intated sppeiiic anple
gaee which
up
"6-sided snovillke with medium triangles as amms"
robated incressee with
tteration ohe loop, creating an inmicate srowitlle pattern.
turtle_steircase
fet turtte
e stércss petter repettetlymovig
foword rotatingt spoci: deeluction rrganent.
4- 4-stepeed staircase"
agrial of seriagersity upaandy frowing pertagan and nnremnntnng ongle each side on each Reration Theaumber pertagors thee deterride by the fasccion nenee
(fe_25) tur turtle, Losp, dr www.tagennnnaa... spprrll X1 turtle -> int -> turtle
CDC
"6 small 5-gons In a row"
Figure 5: Qualitative inspection of LOGO library. Sclected examples of graphies abstractions learned by LIL.O Highlights indicate ambiguities (orange) and crrors (red) in naming and documentation that may affect code comprehension, which we discuss below.
the two polygon functions (fn_27 and fn_34) are assigned relatively uninformative names that em- phasize their implementation (looping move and rotate) but not their behavior (drawing polygons). Moreover, because AutoDoc works sequentially, it occasionally "doubles down" on particular state- ments that may be correct in one context but not another. For example, AutoDoc correctly notes that fn_27 works by "incrementing the angle of each side on each iteration." " but this idea is ambiguous in fn_31 (which angle?) and incorrect in fn_34 (the length is constant, not doubling). In addition to affecting interpretability, these semantic errors may also impact downstream synthesis performance in LLM- LLM-guided search. Future work could adopt self- colfisonsis and verification techniques (Wang et al., 2022; Dhuliawala et al., 2023) to improve the quality of AutoDoc generations.
5 DISCUSSION AND CONCLUSION
In this work, we introduced LILO, a neurosymbolic framework for learning interpretable libraries for program synthesis. In our experiments, we found that LILO performs favorably compared to both DreamCoder and an LLM-only baseline. Much of LILO'S advantage comes from synergy between neural and symbolic components: LLM-guided search enables LILO to learn concepts that are intractable to discover with enumerative search; compression allows LILO to consolidate these solutions into reusable abstractions available symbolic search; and finally, AutoDoc makes these abstractions legible for both humans and LLMS.
While LILO improves on prior library learning approaches, notably, the LLM-only baseline also demonstrates the ability to bootstrap its performance over time. This result aligns with recent suc- cesses in automated prompting (Zhou al., 2023; Yao et al., 2022), suggesting that transformer attention can be viewed as implementing a form of non-compressive library learning where task- relevant information is accumulated in the prompt. However, will scale to large software libraries: as context length grows, key information may be "lost in the middle" or ignored due to ordering effects (O'Connor Andreas, 2021; Lu et al., 2022; Liu al., 2023). Accordingly, an important line of research looks to develop new strategies for equipping LLMs with long-term memory through retrieval (Wu et al., 2022; Park et al., 2023), self-reflection (Shinn et al., 2023), or combinations of both that enable learning libraries of programmatic skills in embodied environments (Wang et al., 2023). Currently, these approaches face the common challenge of determining what information to preserve, leading to large space of ad hoc heuristics.
unclear whether this approach
LILO offers a principled approach to the consolidation of knowledge in a lifelong learning setting, adding program compression growing toolkit of LLM integrations with symbolic computation (Schick et al., 2023; Wolfram, 2023). Moreover, given the generality of Stitch's algorithmic ap- proach, extending LILO modern imperative languages (e.g.. Python) reduces to PL research problem that is both presently tractable and technically compelling. In contrast to the view that LLMs will subsume formal accounts of programming languages, LILO offers a blueprint for collab- oration between the ML and PL communities towards the longstanding goal of learning interpretable software libraries that enable solutions to novel problem domains.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
This work benefited greatly from discussions with colleagues in academia and industry, including Sam Acquaviva, Ekin Akyürek, Jacob Austin, Armando Solar-Lezama and Belinda Li. We are thankful Jack Feser for his OCaml wizardry. Finally, LILO owes a significant debt to ideas and infrastructure pioneered by Kevin Ellis, and we are deeply grateful for his feedback and guidance.
The authors gratefully acknowledge support from the MIT Quest for Intelligence, the MIT-IBM Watson AI Lab, the Intel Corporation, AFOSR, DARPA, and ONR. GG and MB are supported by the National Science Foundation (NSF) under Grant No. 2141064. GG was additionally supported by the MIT Presidential Fellowship. TXO is supported by the Herbert E. Grier (1933) and Dorothy Grier Fund Fellowship and the DARPA ASKEM program (award #HR001 12220042). GG, MB, TXO, and JA are supported by the National Science Foundation (NSF) and Intel through NSF Grant CCF:2217064. JA is supported by NSF Grant IIS -23-220. LW and JBT received support from AFOSR Grant 177A9550-19-1-025
the MIT--BM Watson AI Lab, ONR Science of Al and the DARPA Machine Common Sense program. Any opinions, findings, and conclusions or recommen- dations expressed in this material those of the author(s) and do not necessarily reflect the views of sponsors.
REFERENCES
Harold Abelson and Andrea diSessa. Turtle Geometry: The Computer Medium for Exploring Mathematics. The MIT Press, 1986. ISBN 9780262362740. doi: 10.755 0 01. URL https::/doi..rrr hrgp////.....////.. /mi tpress 001 .0001.
Pekka Abrahamsson, Outi Salo, Jussi Ronkainen, and Juhani Warsta. Agile software development methods: Review and analysis. ArXiv preprint, abs/1709.08439, 2017. URL https://arxiv.or
g/abs/1709.0844
Miltiadis Allamanis and Charles Sutton. Mining idioms from source code. In Proceedings of the 22nd ACM SIGSOFT International Symposium on Foundations of Software Engineering, FSE 2014, pp. 472-483, New York. NY, USA, 2014, Association for Computing Machinery. ISBN 9781450 7781450330565. doi: 10. 011144//2635868266559000 URL hwtph:tt///oooo org/10. 1145/263586.. 2635901.
Miltiadis Allamanis, Earl T. Barr, Christian Bird, Premkumar Devanbu, Mark Marron, and Charles Sutton. Mining Semantic Loop Idioms. IEEE Transactions on Software Engineering, 44(7): 651-668, 2018. ISSN 0098-5589, 1939- 3520. 2326-3881. doi: 10. 10.1109/SE.2201822555 288224444..
Jacob Andreas, Marcus Rohrbach, Trevor Darrell, and Dan Klein. Neural module networks. In 2016 IEEE Conference Computer Vision and Pattern Recognition, CVPR 2016, Las Vegas, NV, USA, June 27-30, 2016, pp. 39-48. IEEE Computer Society, 2016. doi: 10.1109/CVP..2116 12. URL https:://of org/ 10. 10V//CPR 2016.12 12.
Jacob Andreas, Dan Klein, and Sergey Levine. Learning with latent language. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Lin- guistics: Human Language Technologies, Volume I (Long Papers), pp. 2166 26666217,,,, New Orleans, Louisiana, 2018. Association for Computational Linguistics. doi: 10.18653/v 1/N11///////11111 1197. URL https://aclanthol http::/aacc.nttooooooo.or/////// org//N1--/1/91
Yoav Artzi and Luke Zettlemoyer. Weakly supervised learning of semantic parsers for mapping instructions to actions. Transactions of the Association for Computational Linguistics, 1:49-62, 2013. doi: 10. 20.116//aac_aa0000999 URL https::/aclaatthllllee
org/Q13-
Jacob Austin, Augustus Odena, Maxwell Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie Cai, Michael Terry. Quoc Le, et al. Program synthesis with large language models. ArXiv preprint, 0bs/2/00..0732..... 2021. URL https://arxiv org harg//bs//aa abs///08 2tt./218..000 07732.
Matej Balog, Alexander L. Gaunt, Marc Brockschmidt, Sebastian Nowozin, and Daniel Tarlow. Deepcoder: Learning to write programs. In Sth International Conference Learning Represen- tations, ICLR 2017, Toulon. France, April 24-26, 2017. Conference Track Proceedings. OpenRe- view.net, 2017. URL https: httt::://opeereveew wttp://ee/e/oooooo wwt..n/orormmi--yllddlrrlrrrrprp
10

---

Published as a conference paper at ICLR 2024
Matthew Bowers, Theo X. Olausson, Lionel Wong, Gabriel Grand, Joshua B. Tenenbaum, Kevin Ellis, and Armando Lozar-Lezama. Top-down synthesis for library learning. Proc. ACM Program. Lang., 7(POLL) 2023. doi: 10.1145/3571234, URL https:://dii.orrr 10. 1145/35713 3371234.
Peter F. Brown, Stephen A. Della Pietra, Vincent J. Della Pietra, and Robert L. Mercer. The math- ematics of statistical machine translation: Parameter estimation. Computational Linguistics, 19 (2):263-311, 1993. URL https://aclantiie
093/J93-200 290-2003.
William H Brown, Raphael C Malveau, Hays W "Skip" McCormick, and Thomas Mowbray. AntiPatterss: refactoring software, architectures, and projects crisis. John Wiley & Sons, Inc., 1998.
José Cambronero, Sumit Gulwani, Vu Le, Daniel Perelman, Arjun Radhakrishna, Clint Simon, and Ashish Tiwari. FlashFill++: Scaling Programming by Example by Cutting to the Chase. Pro- ceedings of the ACM on Programming Languages, 7(POPL):952-99) -98991, 2023. ISSN 2475-1421. doi: 10.1145/3571226.
David Cao, Rose Kunkel, Chandrakana Nandi, Max Willsey, Zachary Tatlock, and Nadia Polikar- pova. babble: Learning better abstractions with e-graphs and anti-unification. Proc. ACM Pro- gram. Lang., 7(P0PL))396-424, 2023. doi: 10.1 10.1145/3571207. URL https://doot wtw.ii.rr/1...0 114
5/3571207.
Gregory Chaitin. On the length of programs for computing finite binary sequences. Journal of the ACM (JACM), 13(4):547-569 1966.
David L. Chen and Raymond J. Mooney. Learning to interpret natural language navigation instruc- tions from observations. In Wolfram Burgard and Dan Roth (eds.), Proceedings of the Twenty- Fifth AAAI Conference Artificial Intelligence, AAAI 20/ I, San Francisco, California, USA, August 7-11, 201 AAAI Press, 2011. URL http: h/wt::/wwww. aaai org/ocs/ index. wwwp..ppp//.A.////// php/AAAI/AA /tt1/paper/iiew/3/// /wwe//vwww///// 3701.
Mark
Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, et al. Evaluating large language models trained code. ArXiv preprint, abs/2107.03374, 2021. URL https://arxiv. brg/abs/2108 07 03374.
Eyal Dechter, Jonathan Malmaud, Ryan Adams, and Joshua B. Tenenbaum. Bootstrap learning via modular concept discovery. In Francesca Rossi (ed.), IJCAI 2013, Proceedings of the 23rd International Joint Conference on Artificial Intelligence, Beijing, China, August 3-9, 2013, pp. 1302-1309. IICAI/AAAI, 2013. URL http:: hwwp://wwwwwww/ aaai 13/paper /vtee//wewww/////ee
www.a...rooooaooooooooaoooo www.oogg///ocoooooo http///ss/ind...c//////// Php/IICAI/IICAT
Jacob Devlin, Jonathan Uesato, Surya Bhupatiraju, Rishabh Singh, Abdel-rahman Mohamed, and Pushmeet Kohli. Robustfill: Neural program learning under noisy I/O. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW. Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pp. 990-998. PMLR, 2017. URL http::/pppppttt http://prooceddngs. mlr ptt...rrss/v///// devlin17a 7a. html.
Shehzaad Dhuliawala, Mojtaba Komeili, Jing Xu, Roberta Raileanu, Xian Li, Asli Celikyilmaz, and Jason Weston. Shaii-of-verificatton reduces hallucination in large language models. arXiv preprint arXiv:2309.1 /195, 2023.
Kevin Ellis, Daniel Ritchie, Armando Solar-Lezama, and Josh Tenenbaum. Learning to infer graph- ics programs from hand-drawn images. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett (eds.), Advances in Neural Infor- mation Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8. 2018. Montréal, Canada, pp. 6062 6071, 2018. URL https: / htt::////ooceennn..///m www.eeediiinnnnuuuiisseeee wwwrins......m cc cttppprrrrpppperpeeeeme/o paper 201 htt/hahhh/7887666. 0ba0314-Abstrad html.
4c83cedadbe6b

---

Published as a conference paper at ICLR 2024
Kevin Ellis, Catherine Wong, Maxwell Nye, Mathias Saylé-Meyer, Lucas Morales, Luke Hewitt, Luc Cary, Armando Solar-Lezama, and Joshua B Tenenbaum. Dreamcoder: Bootstrapping in- ductive program synthesis with wake-sleep library learning. In Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation, pp- 835-850, 2021.
Jonathan St.B.T. Evans. In two minds: dual-process accounts of reasoning. Trends in Cognitive Sciences, 7(10):454-459 2003. ISSN 1364-6613. doi:
ttt.::o....cs.......... 0..01.. URL hwtpp::pp/wwtt http:////wwwsssiinncee www.scecieceiieeeeee wttp://crcettccccccccccccceeeeee www.///cince//eeeieeoocoeoceceee htt.////c.eee//aaaaaaaa///////// 303002250.
Daniel Fried, Armen Aghajanyan, Jessy Lin, Sida Wang, Eric Wallace, Freda Shi, Ruiqi Zhong, Wen-tau Yih, Luke Zettlemoyer, and Mike Lewis. Incoder: generative model for code infilling and synthesis. ArXiv preprint, abs/2204.05999, 2022. URL https://arxiv. Saarg/abs/220 0 5999.
Nishad Gothoskar, Marco F. Cusumano-Tovee Ben Zinberg, Matin Ghavamizadeh, Falk Pollok, Austin Garrett, Josh Tenenbaum, Dan Gutfreund, and Vikash K. Mansinghka. 3DP3: 3D scene perception via probabilistic programming. In Marc Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan (eds.), Advances in Neural Information Processing Systems 34: Annual Conference Neural Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, pp. 9600-9612, 2021. URL https::/prooeediii s.neurips. cc/ cc/paper/ 2221 hhtp//aahh///t/ /fcp//ffc661111 o
html.
Sumit Gulwani, José Hernández-Orallo Emanuel Kitzelmann, Stephen Muggleton, Ute Schmid, and Benjamin Zorn. Inductive programming meets the real world. Communications of the ACM, 58(11):90-99) 99, 2015.
Sumit Gulwani. Oleksandr Polozov, and Rishabh Singh. Program synthesis. Foundations and Trends@ in Programming Languages, 4(1-2):1-119, 2017. ISSN 2325-1107. doi: 10.1561/ 2500000010. URL http://dx doi 100 1561 2500000000.
Patrick Haluptzok, Matthew Bowers, and Adam Tauman Kalai. Language models can teach them- selves to program better. ArXiv preprint, abs/2207.14502 2022. URL https://arxiv.org/. s/2207. 14502.
Dan Hendrycks, Steven Basart, Saurav Kadavath, Mantas Mazeika, Akul Arora, Ethan Guo, Collin Burns, Samir Puranik, Horace He, Dawn Song, et al. Measuring coding challenge competence with apps. ArXiv preprint, abs/2105 05.09938, 2021. URL httpp:::/aaai...rrrrrrr///
/ 0193899380.0..... 09938.
Ronghang Hu, Jacob Andreas, Marcus Rohrbach, Trevor Darrell, and Kate Saenko. Learning to
reason: End-to-end module networks for visual question answering. In IEEE International Con- ference Computer Vision, ICCV 2017, Venice Italy, October 22-29, 2017, pp. 804-813. IEEE Computer Society, 2017. doi: 10.1 200///...2017..9.. URL httpp:://oi....... http//oo..ogg//// 1tt///...110///1.1 110.1199/CCC .2017.93.
Justin Johnson, Bharath Hariharan, Laurens van der Maaten, Li Fei-Fei, C. Lawrence Zitnick, and Ross B. Girshick. CLEVR: A diagnostic dataset for compositional language and elementary visual reasoning. In 2017 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2017, Honolulu, HI, USA, July 21-26, 20/7, pp- 1988-1997. IEEE Computer Society, 2017. doi: 10. 10.1109/CVPR.2011..22 URL https: /ooi org/ 10. wwtp////...2.......
Mark Johnson. PCFG models of linguistic tree representations. Computational Linguistics, 24(4): 613-632, 1998. URL htt.h:tts//ccccaaee /tlL:ttt////alllnttloogy wttp:/llooyoooooo--///// org/J98-4004.
Daniel Kahneman. Thinking, fast and slow. Farrar, Straus and Giroux, New York, 2011. ISBN
9780374275631 0374275637.
Daniel Kersten, Pascal Mamassian, and Alan Yuille. Object perception as Bayesian inference. Annu. Rev. Psychol., 55:271-304, 2004.
David Knill and Whitman Richards. Perception as Bayesian inference. Cambridge University Press, 1996.
12

---

Published as a conference paper at ICLR 2024
Andrei Nikolaevich Kolmogorov. Three approaches for defining the concept of information quantity. Problemy peredaci informacii, 1:3-11, 1965.
Marie-Anne Lachaux, Baptiste Rozière, Mare Szafraniec, and Guillaume Lample. DOBF: A de- obfuscation pre-trate wre-trainin objective for programming languages. In Mare' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin. Percy Liang, and Jennifer Wortman Vaughan (eds.), Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Process- ing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, pp. 14967-14979, 2021. URL https: http::///ooccece.../.oo neur ieerrips... cc/paper ccb-Abstract. html.
Brenden M. Lake, Ruslan Salakhutdinov, and Joshua B. Tenenbaum. Human-level concept learning through probabilistic program induction. Science, 350(6266): 2015. doi: 10.1 126/sc ience.aab3050. URL https:/ /wwww/ wwwenceceee..c wwwp//o///aaeeoooooo //d/o///a//// /00. (126/sciences aciincc.aabb050.. aab3050.
Tessa A. Lau and Daniel S. Weld. Programming by demonstration: An inductive learning for- mulation. In Proceedings of the 4th International Conference on Intelligent User Interfaces,
pp. 145-152, Los Angeles California USA, 1998. ACM. ISBN 978-1-58113-098-0. doi: 10.1145/291080.2911
Miguel Eazaro-Gredill Dianhuan Lin, J Swaroop Guntupalli, and Dileep George. Beyond imi- tation: Zero-shot task transfer on robots by learning concepts as cognitive programs. Science Robotics, 4(26):eaav3150, 2019.
Tai Sing Lee and David Mumford. Hierarchical Bayesian inference in the visual cortex. JOSA A, 20(7):1434-144 2003.
Raymond Li, Loubna Ben Allal, Yangtian Zi, Niklas Muennighoff, Denis Kocetkov, Chenghao Mou, Mare Marone, Christopher Akiki, Jia Li, Jenny Chim, Qian Liu, Evgenii Zheltonozhskii, Terry Yue Zhuo, Thomas Wang, Olivier Dehaene, Mishig Davaadorj. Joel Lamy-Poirier, João Monteiro, Oleh Shliazhko, Nicolas Gontier, Nicholas Meade, Armel Zebaze, Ming-Ho Yee, Lo- gesh Kumar Umapathi, Jian Zhu, Benjamin Lipkin, Muhtasham Oblokulov. Zhiruo Wang, Rudra Murthy, Jason Stillerman, Siva Sankalp Patel, Dmitry Abulkhanov, Marco Zocca, Manan Dey, Zhihan Zhang. Nour Fahmy, Urvashi Bhattacharyya, Wenhao Yu, Swayam Singh, Sasha Luc- cioni, Paulo Villegas, Maxim Kunakov, Fedor Zhdanov, Manuel Romero, Tony Lee, Nadav Timor, Jennifer Ding. Claire Schlesinger, Hailey Schoelkopf, Jan Ebert, Tri Dao, Mayank Mishra, Alex Gu, Jennifer Robinson, Carolyn Jane Anderson, Brendan Dolan-Gavitt, Danish Contractor, Siva Reddy, Daniel Fried, Dzmitry Bahdanau, Yacine Jernite, Carlos Muñoz Ferrandis, Sean Hughes, Thomas Wolf, Arjun Guha, Leandro von Werra, and Harm de Vries. StarCoder: May the source be with you!. 2023. URL https: www.:o.rg//bb/bb. 2305. 2361106111........
Yujia Li, David Choi, Junyoung Chung, Nate Kushman, Julian Schrittwieser, Rémi Leblond, Tom Eccles, James Keeling, Felix Gimeno, Agustin Dal Lago, al. Competition- code generation with AlphaCode. Science, 39866624) 2022.
Percy Liang, Michael Jordan, and Dan Klein. Learning programs: A hierarchical Bayesian ap- proach. In Johannes Fürnkranz and Thorsten Joachims (eds.). Proceedings of the 27th Interna- tional Conference on Machine Learning (ICML-10), June 21-24, 2010, Haifa, Israel, pp. 639- 646. Omnipress, 2010. URL https: //ccml...mmmmm/mmm//mm//// wwtcooceeeecce//////ccccccccccce 201 0/ happpsppp//s///////ee//// 568. ..f...
Percy Liang, Michael Jordan, and Dan Klein. Learning dependency- compositional semantics. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, pp. 590-599, Portland, Oregon, USA, 201 Association for Computational Linguistics. URL
Jiachang Liu, Dinghan Shen, Yizhe Zhang, Bill Dolan, Lawrence Carin, and Weizhu Chen. What makes good in-context examples for GPT-3? In Proceedings of Deep Learning Inside Out (Dee- LIO 2022): The 3rd Workshop on Knowledge Extraction and Integration for Deep Learning Ar- chitectures, pp. 100-114, Dublin, Ireland and Online. 2022. Association for Computational Lin- guistics. doi: 18.18/ 1/2022. 1.10. URL https: httpss///claaaaoloaacaao www.ee.....////// wtg. -1. 10.
13

---

Published as a conference paper at ICLR 2024
Nelson F. Liu, Kevin Lin, John Hewitt, Ashwin Paranjape, Michele Bevilacqua, Fabio Petroni, and Percy Liang. Lost in the Middle: How Language Models Use Long Contexts, 2023. URL
.31722.
Yao Lu, Max Bartolo, Alastair Moore, Sebastian Riedel, and Pontus Stenetorp. Fantastically ordered prompts and where to find them: Overcoming few-shot prompt order sensitivity. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volune I: Long Pupers), pp. 8086-8098, Dublin, Ireland, 2022. Association for Computational Linguistics. doi: (ttp65//1//222aaclllllao
URL https: https::/aclaatbonne http:/aaaaaaatoooo..ooooo 202g/202..o2 acl- 556.
Mehdi Manshadi, Daniel Gildea, and James Allen. Integrating programming by example and natural language programming. Proceedings of the Sweety-Seventh AAAI Conference on Artificial Intelligence, AAAI'13, pp. 661-6617 AAAI Press, 2013.
Antonio Valerio Riceli-Barone Fazl Barez, loannis Konstas, and Shay B. Cohen. The Larger They Are, the Harder They Fail: Language Models do Recognize Identifier Swaps Python, 2023.
URL https: http/xxxvvvvoo// htrg/bbs/2300 15507.
Erik Nijkamp. Bo Pang, Hiroaki Hayashi, Lifu Tu, Huan Wang, Yingbo Zhou, Silvio Savarese, and Caiming Xiong. CodeGen: An open large language model for code with multi-turn program synthesis. In The Eleventh International Conference on Learning Representations, 2023. URL https://openren http://ew.pereeeeee....e.. deet/oorumiidiiaccKKe
Maxwell I. Nye, Luke B. Hewitt, Joshua B. Tenenbaum, and Armando Solar-Lezama. Learning to infer program sketches. Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference Machine Learning. ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pp. 4861- 4870. PMLR, 2019. URL http::/proccedingg/ mlr.. wwwppppssssseeeeeeppp.epppp.p /nyee 19..
Joe O' O'Connor and Jacob Andreas. What context features can transformer language models use? In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference Natural Language Processing (Volume 1: Long Papers), pp. 851-864, Online, 2021. Association for Computational Linguistics. doi: 10.18653/v1/202/ cl- cl-long.70 70. URL https:://aclaathollleee//////
wrg///21..... acl acl-long...... 70.
OpenAl. GPT-4 Technical Report, 2023. URL http:::/arxxivoog///b///// http//bbb22333... 08774.
Emilio Parisotto, Abdel-rahman Mohamed, Rishabh Singh, Lihong Li, Dengyong Zhou, and Push- meet Kohli. Neuro-symbolic program synthesis. In 5th International Conference on Learning Representations, ICIR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017. URL https:ttt//// httt::://opnreviieee wwtppeerrvieeeeeee/ooumiiliiiiie www.://ooooddddrro..00.00. cex.
Joon Sung Park, Joseph C. OrBrien, Carrie J. Cai, Meredith Ringel Morris, Percy Liang, and Michael S. Bernstein. Generative Agents: Interactive Simulacra of Human Behavior, 2023. URL
wtt./bs//////////oo/a https://axxiv.or//aa///0000 https://arxiv
03442.
Gabriel Poesia, Alex Polozov, Vu Le, Ashish Tiwari, Gustavo Soares, Christopher Meek, and Sumit Gulwani. Synchromesh: Reliable code generation from pre-trained language models. In The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net, 2022. URL
Nadia Polikarpova, Ivan Kuraj, and Armando Solar-Lezama. Program synthesis from polymorphic refinement types. ACM SIGPLAN Notices, 5 51(6):522-538, 2016.
Kia Rahmani, Mohammad Raza, Sumit Gulwani, Vu Le, Daniel Morris, Arjun Radhakrishna, Gus- tavo Soares, and Ashish Tiwari. Multi-modal program inference: marriage of pre-trained lan- guage models and component-based synthesis. Proceedings of the ACM on Programming Lan- guages, 5(00PSLA):1-2) 2021.
Mohammad Raza, Sumit Gulwani, and Natasa Milic-Frayling. Compositional program synthe- sis from natural language and examples. In Qiang Yang and Michael J. Wooldridge (eds.), Proceedings of the Twenty-Fourd International Joint Conference Artificial Intelligence, 1J- CAI 2015, Buenos Aires, Argentina, July 25-31, 2015, pp. 900-800. AAAI Press, 2015. URL http://ijcai. org/ wetiicci..rg/bbbtreeeeeee /bs//bbtttat///11...
14

---

Published as a conference paper at ICLR 2024
Timo Schick, Jane Dwivedi- Yu, Roberto Dessi, Roberta Raileanu, Maria Lomeli, Luke Zettlemoyer, Nicola Cancedda, and Thomas Scialom. Toolformer: Language models can teach themselves to use tools. ArXiv preprint, abs/2230.00471,, 2023. URL https://arxiv.orr httg//b///3000 04761.
Pratyusha Sharma, Antonio Torralba, and Jacob Andreas. Skill induction and planning with la- tent language. In Proceedings of the 60th Annual Meeting of the Association for Computa- lional Linguistics (Volume 1: Long Papers), pp. 1713-1726, Dublin, Ireland, 2022. Associa- tion for Computational Linguistics. doi: //aclanthology.. or wttp////.... acl-long. 120.
120. URL https:
Eui Chul Richard Shin, Miltiadis Allamanis, Mare Brockschmidt, and Alex Polozov. Program syn- thesis and semantic parsing with learned code idioms. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Buc, Emily B. Fox, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Pro- cessing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 10824- 10834, 2019. URL https: http:////oocceeeeeeeeeeee nenn ipeurips..o cc/paper/201 w//hshhccff44a3435555 7146522066aad17444f----oott httm.
Noah Shinn, Federico Cassano, Beck Labash, Ashwin Gopinath, Karthik Narasimhan, and Shunyu Yao. Reflexion: Language Agents with Verbal Reinforcement Learning, 2023. URL https:
// //arxiv. war.xi..orggab///33333 11366.
Steven A Sloman. The empirical case for two systems of reasoning. Psychological bulletin, 119(1):
3. 1996.
Ray Solomonoff. A formal theory of inductive inference. Part Information and control, 7(1):
1-22, 1964.
Shashank Srikant, Sijia Liu, Tamara Mitrovska, Shiyu Chang, Quanfu Fan, Gaoyuan Zhang, and Una-May O' O'Reilly. Generating adversarial computer programs using optimized obfuscations. In 9th International Conference on Learning Representattons, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021. URL https:://ppenreiieee http:///pppppeeeeeeeeeeeeorrrrra net/forummid-PHSPHHz
Thomas N. Theis and H.-S. Philip Wong. The end of Moore's 's law: A new beginning for information technology. Computing in Science Engineering, 19(2)411550, 2017. doi: M01 7.29.
Guanzhi Wang, Yuqi Xie, Yunfan Jiang, Ajay Mandlekar, Chaowei Xiao, Yuke Zhu, Linxi Fan, and Anima Anandkumar. Voyager: An Open- Ended Embodied Agent with Large Language Models, 2023. URL httpss//arxxv.. wttp://////.//eeeeeeeee 16291.
Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc Le, Ed Huai hsin Chi, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. ArXiv preprint, abs/2203.11171, 2022. URL
11171.
Stephen Wolfram. ChatGPT gets its "Wolfram Superpowers", 2023. URL htt.htts:://writingg. phenwolfram cwmccmmm/2//// 2ttp//2223////// http://////attt//teeeee wtwppttt-ggestttttsfrseeeeee superpowers/
Catherine Wong, Kevin Ellis, Joshua B. Tenenbaum, and Jacob Andreas. Leveraging language to learn program abstractions and search heuristics. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning. ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings Machine Learning Research, pp. 11193- 11204. PMLR, 2021. URL http:/ pwwpppeeing....ie.ee.e wtwp:inggs.....rrss//ee 39 http//oo22laa html.
Jiajun Wa, IIker Yildirim, Joseph J. Lim, Bill Freeman, and Joshua B. Tenenbaum. Galileo: Per- ceiving physical object properties by integrating a physics engine with deep learning. In Corinna Cortes, Neil D. Lawrence, Daniel D. Lee, Masashi Sugiyama, and Roman Gamett (eds.), Ad- vances in Neural Information Processing Systems 28: Anmual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec. Canada, pp. 127- 2015. cc/ paper http//////////aaeee wttt//////ba4115//////// http://990f441544422355555555633
URL https: wwtpppreiigs..neueee. wttp:ppcppppppccceee b5e35c3-Abstrant ietstract.ttte html.
15

---

Published as a conference paper at ICLR 2024
Jiajun Wu, Joshua B. Tenenbaum, and Pushmeet Kohli. Neural scene de-rendering. In 2017 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2017, Honolulu, HI. USA, July 21-26, 2017, pp. 7035-7043. IEEE Computer Society, 2017. doi: 10.1109/CVPR.2017..74. URL https:/ /toi. org/ 10. 1109/ 10//////CPPP CVPR. 2017..201... 2017.744
Yuhuai Wu, Markus Norman Rabe, DeLesley Hutchins, and Christian Szegedy. Memorizing trans- formers. In The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net, 2022. URL https: https:://ppenrewieww net wwtp://neffofmiieeecooe TrjbxzRenf-.
Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao. ReAct: Synergizing Reasoning and Acting in Language Models, 2022. URL https://arxiv... g/abs/2216 22122/699..0.
Kexin Yi, Jiajun Wu, Chuang Gan, Antonio Torralba, Pushmeet Kohli, and Josh Tenenbaum. Neural- symbolic VQA: disentangling reasoning from vision and language understanding. In Samy Ben- gio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Biance and Roman Garnett (eds.), Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, pp. 1039-1050, 2018. URL https: "5e388103a39) 3de 1oaa
wtwpeeeddinnn.eeuiiip..... Abstract html.
2opprr20112 20arr//211///// 8/hhshh
Ilker Yildirim, Mario Belledonne, Winrich Freiwald, and Josh Tenenbaum. Efficient inverse graphics in biological face processing. Science Advances, 6 6(10):eaxx5979 2020. doi: 10. 126/sciadv.ar aax 5979. URL httpp::/www.sc....cct science. org.oog///oooo /doo//as//// /126/sciady aax5979.
Pengcheng Yin, Wen-Ding Li, Kefan Xiao, Abhishek Rao, Yeming Wen, Kensen Shi. Joshua Howland, Paige Bailey, Michele Catasta, Henryk Michalewski, Alex Polozov, and Charles Sut- ton. Natural Language to Code Generation Interactive Data Science Notebooks, 2022. URL https://arxiv. org/abs/2212 09248.
Alan Yuille and Daniel Kersten. Vision as Bayesian inference: analysis by synthesis? Trends in cognitive sciences, 10(7):301-308, 2006.
Eric Zelikman, Qian Huang, Gabriel Poesia, Noah D. Goodman, and Nick Haber. Parsel: A (De- jcompositional Framework for Algorithmic Reasoning with Language Models, 2022. URL http s://arxiv. htt///xiv..rgg/bbbb/ otg/abs//22 2212. 10561.
Zhengran Zeng. Hanzhuo Tan, Haotian Zhang, Jing Li, Yuqun Zhang, and Lingming Zhang. An extensive study on pre-trained models for program understanding and generation. In Proceedings the 3/st ACM SIGSOFT International Symposium Software Testing and Analysis, pp. 39-51, Virtual South Korea, 2022. ACM. ISBN 1-4503-9379-9
doi: 10. 11/45533767.35343999
Yongchao Zhou, Andrei loan Muresanu, Ziwen Han, Keiran Paster, Silviu Pitis, Harris Chan, and Jimmy Ba. Large language models are human-level prompt engineers. In The Eleventh Intera- tional Conference on Learning Representations 2023. URL https: httpst://openeeeeeee /ttp:////p///i////ee/ee eiwnww net/forum ?id=92gvk82DE-.
16

---

Published as a conference paper at ICLR 2024
Appendix
Table of Contents
A Methods
18
A.1 LLM Solver Prompt
18
A.2 Auto-Docte Dottmmmoumnnttiinnn Prompt
19
A.3 Task Exampex Selection Methods
21
A.4 Implementation Details
22
A.5 Hyperparameters..
23
B Experiments and Results
24
B.I Domain Details
24
B.2 Learned Libraries and Graphical Maps
................................
26
B.3 Benchmark Comparison to Prior Work
39
B.4 Experiments with Human Language Descriptions.
40
Additional Experiments and Analyses
42
Computational Efficiency Analysis
C.2 Can LLMs Perform Compression?
45
17

---

Published as a conference paper at ICLR 2024
A METHODS
A.1
LLM SOLVER PROMPT
You are on expent prograsser workinng in Language based á colculus. Your gool ts that accomplish the spectfited the This is doratn-spect/te grophtes. artte prograes using the avoitable functions:
urtte
Language för Loge
logo unit ungo_ angle 1: tangle
1ogo_unit_1one
tlength
1ogo_zoro angla 1: tangle
Domain header & library functions
1ago_zero_ Tine 1: tlength
logo sepp_divide__. aagglaanggleea tangle int tangle
logo wtt.mniitllllanlll..l. tangle
tangle
sapo_divide_liee 1: tlength
tlength
logo_ nultiply_Him 1: tlength -> int tlength
loge_add add___ddd_gggss tangle tangle -> tangle
pagp_ssttract_anne
targle tangle tangle
1ogo 1ete__sft__pp___ pen 1: (tuetle turtle) >> turtle
loge_ pang__nov__ee pww_oooveeeeneeeeeeeeeeee hwwe_pen_forwedd_egg forwadd_ i: tlength -> tangle -> turtle -> turtle (turtle turtle) turtle tuetle
logo_ged sat___unction_pe
logo IFTY
:: tangle
logo epsilon line 1: tlength
bero_for__ie loop int (int turtle >> turtle) turtle turtle
Here are sore exaxple progroms:
smalt
(logo_rove penv_pen, pww_per__oooardd fonterd_rotaee rotate logo_unit, (logo, divide angle lopo_umit_aneae 8) (0))) $e)]
(logo_ foop
rediue metiomulltlll_leee Hine logo unit 2) (Logo divido angle logo, undt, angle 6) (0))) se))
(logo, for (A ( (logo_ forward retate
Example
task
5 small squares in row (logo loop logo angle 4) (logo for loop (A (logo pen, rotate logo
program
(logo
forward
1ine divide angle
pairs
isompled from solved tosks)
(logo_ divide_angla logo sanjuuntannne 4) $8))) $83))) $B))
vertical
(3ogo_ move_pon pen forward rotate logo_ zero (logo, divide angla logo_unit unit__ngle 4) line logo wew.eeppssannpeeeeee aagllon_angle $8)))
(logo, nove pen_ forward rotate Logo, unit Logo_
small
(logo_ For_loop logo_ IFTY ( (logo_ Bacp__ooo__ee___ ____-eeeoorrd_rrtteeee Togo_unit_line (logo_ (logo_divide divide_angle logo unst
logo_untt__ae anitt_angle> 9) 50))) 58))
cadditionnl exaeples fill context windows
Task
description
5 small triongles in row
(unsolved)
(A. (logo_for: Sagp__oo__ooop 7 (A (A (logo_rove wtwpeeoeeeeeeeeeeeeeeeeeee pew__oowarddroooeeeeeeeeee rotate logo_zero__11 Lingo_divide_ane logo
(logo_reve__g) seve__en_forwerd_rtaae logo_unit__ngle 50))) (0)))) 50))
3) (logo_for_
logo_unit_liree (logo (Iago_divide_ampl)
(A (logo, foop 5 (A (A (logo, for loop () (A. (logo, sove, pen, fortardd_rottteeeeee 50))) s0)))) 50))
LLM
1ogo_unit_lime (logo_divide_mmpge logo_unit_amgle
completions
(logo_for: for__for_ooop (A (A (logo_rove, pene_pee___eeeeeeeeeeeeeee oowweden_ rotate logo__ero__ing
(logo divide angle logo unit, angle 3) (lego for loop 5 (A (A (logo neve_ forward rotate 50))
solution
logo unit 1ine (logo, divide angle logo unit, aniteangle 50)))
valid
(logo for Loop 5 (A (A (logo nove pen forward rotate logo zero zine (logo_ divide, angle logo unit, angle 4) (lego_ for_for_ooooo loop 7 (A. (A. (loge reve_pen, fown_foowwrddrorec rotate (logo divide angle logo unst.
(e)))
Figure 6: Anatomy of LLM Solver prompt. (A) Each prompt begins with short domain description followed by an autogenerated list of the DSL primitives their type signatures. (B) randomly sample task solutions and their language descriptions to construct the prompt body. (C) The final line the prompt contains target task description for an unsolved task. (D) We sample and parse N completions from the LLM, filter out invalid programs, and check for task solutions.
18

---

Published as a conference paper at ICLR 2024
A.2 AUTO-DOCUMENTATION PROMPT
For reproducibility, we provide an example of the full text of an AutoDoc prompt sequence for the REGEX domain below. The prompt is composed of multiple pieces that messages to the ChatGPT interface. The sequence begins with a header message describing the DSL. For pedagogical clarity, we consider the case where every abstraction except the final one have already assigned names. Thus, the header contains a mostly-documented library with the final fn_51 remaining anonymous.
in serial as
are writing sof toft documentation, Your goal write human-readable names for the following library functions:
vowel_or tsubstr
(regex_or 'a' (regex_or 'e' (regex_or 'i' (regex_or 'o' 'u')))) (- Matches any single vowel character ('a', 'e', 'i', 'o', 'u') using 'regex_or" function. -}
tfullstr +> tsubstr -> tsubstr -> tfullstr (lambda (lambda (lambda flattenlatten (regex_map (lambda (regex_if tregex_match $0) $1 s0)) (regex_split $1 $2))))})
replace_and_ flatten -natttteen_
(- Replaces all instances of given substring with another substring, and returns the resulting string flattened into one string. The first argument is the input string, the second argument is the substring to be replaced, and the third argument is the substring use instead of the replaced substring. -}
<fn_44 fn.50 omitted for concision
fn_51 tfullstr -> tsubstr tsubstr tfullstr (lambda (lambda (lambda (regex_flaa ffattef (regex_cons $0 (regex_cons (regex_cdr spplit_stringjito_llls $2))))))))
We then send message prompting the LLM to document fn.51. At the end of the message, we quest that LLM encode the reply into a particular JSON format to facilitate downstream parsing.
Consider the following anonymous function:
fn_51 tfullstr -> tsubstr -> tsubstr -> tfullstr
(lambda (lambda (lambda (regex_flatted (regex_cons s0 (regex_cons $1 (regex_cdr
(split_string_into_lll $2))))))))
Here are some examples of its usage:
if the word starts with consonant any letter replace that with (lambda (regex_if (regex_match (regex_not vowel_or) (regex_car ioplit_string_ino__ie $0))) (fn_51 (regex_flatten (regex_cdr (split_string_into_iis $0))) 'd' 'v') s0))
-- if the word starts with any letter vowel add before that (lambda (regex_if (regex_match vowel_or (regex_car (regex_cdr (split_string list (0)))) (fn_51 so (regex_car ssplit_string_into...
s0)) 'q') s0))
if the word starts with vowel replace that with (lambda (regex_if (regex_match vowel_or (regex_car, (splittstringgiinoollss list S0))) (fn_51 (regex_flatten (splitt.trrin_iino___itt $0)) 'c' 'u') $0))
sadditional usage examples omitted for concision>
Please write human-readable and description for "fn.51" in the JSON format shown below.
Your "readable name should be underscore-separated and should not contain any spaces. It should also be unique (not existing in the function library above). If you cannot up with good name, please set "readable_name" to "null".
19

---

Published as a conference paper at ICLR 2024
"anonyyoous_ame"" "fn_51", "readable_nee :_mmle TODO,
"description": TODO
We encountered difficulties in coaxing Codex to perform the AutoDoc task: the resulting function names were variable in quality, did not reliably capture the function semantics, and were embed- ded in generations that did not always adhere to the desired output specification. Instead, we take advantage of OpenAl's instruction-tunee hered to the desired output JSON schema 100% of the time and never chose to return null for readable, _naee. We experimented with both gpt-3. 5-turbo and gpt-4 for AutoDoc and found both resulted in comparable synthesis performance on REGEX. However, GPT-4 was significantly slower: whereas gpt-3. 5-turbo averaged 10-20 seconds for iteration of AutoDoc, gpt-4 eraged upwards of 2 minutes per iteration. We therefore chose to use gpt-3. 5-turbo in the experi- ments reported in $4.
3o9t-3.5-ture and gpt-4 models, which we found ad-
Unlike for the LLM Solver, we do not provide any few-shot examples of the desired transformations; all of this behavior is zero-shot, making AutoDoc an extremely Comain-general technique that is easy to implement across a variety of settings.
20

---

Published as a conference paper at ICLR 2024
A.3
SELECTION METHODS
Our LLM-guided program synthesis method (Eq. 3) requires selecting a set of few-shot examples for prompting. As the set of solved tasks grows, the of possible examples exceeds the size of the LLM context window. This issue particularly affects non-compressive methods, such as the LLM Solver baseline. However, even with program compression-which substantially reduces the length of the program examples-LiLs still requires subsampling from the total set of possible examples.
We experimented with two different methods for task example selection: naive random sampling method and task-example selection method (Liu et al., 2022) based on cosine similarity between the task descriptions of the example dæ and the target de:
score (1,, d.) = dg df
||
In our implementation, used embeddings from eext-embedding-ada--eeee via the OpenAl API to pre-compute pairwise similarities between all task descriptions each domain. For both selection methods, we construct the prompt dynamically to fit as many examples as possible.
ran head-to-head comparison between the two sampling methods for our main LILO model. As Fig. 7 and Tab. show, did not observe significant improvement from the cosine similar- ity example selection method. though introducing determinism did have the effect of reducing the variance across runs in the REGEX domain. In absence of evidence justifying additional methods complexity, we chose to use random sampling for the results reported in $4.
It is possible that the of compression in LILO reduces the need for targeted example selection, since we are able to fit approx. 20-40 examples per prompt across all domains. We also noted a tendency for the cosine similarity sampling be oversensitive superficial lexical overlap in the task descriptions; e.g., two tasks might involve very different programs but both include the word "six" as an argument, resulting in high cosine similarity. Thus, methods that explicitly finetune model to infer similarity between (observed) example and (unobserved) target programs (i.e., Target Similarity Tuning from Poesia al., 2022) could offer clearer performance advantages.
REGEX
CLEVR
LOGO
100
Tasks solved (%)
50
3
9
12
15
0
3
6
9
0
3
6
9
Iteration
Iteration
Iteration
Sampling method
Random
Cosine Similarity
Figure 7: Head-to-head comparison between example selection methods for main LILO model.
TASKS SOLVED (%)
REGEX
CLEVR
LOGO
MODEL
meam
sid
sld
THCAN
sid
LILO (Random)
93.20
77.07
14.14
99.03
96.76
3.12
73.87
48.95
22.15 15
LILO (Similarity)
72.60
71.33
1.10
100.00
97.41
2.24
79.28
53.15
22.67
Table 2: Final performance of task example selection methods for the main LII.0 model.
21

---

so Published as a conference paper at ICLR 2024
A.4 IMPLEMENTATION DETAILS
We provide a brief summary of key implementation details relevant to the experiments that are not reported in $4, We ran all experiments AWS EC2 instances with machine specs tailored suit the computational workload of each experiment.
Enumerative search. For experiments involving enumerative search, which an embarrassingly parallel workload that scales linearly with the number of available CPUs, we ran on 96-CPU c5. 24xlarge instances. These machines have the highest CPU count in the c5 machine class. To take maximal advantage of the CPU parallelism, we set batch_size=9 for these experiments (i.e., each iteration searches for solutions for a subset of 96 tasks). A convenient consequence of this implementation choice is that each task is allocated to single, dedicated CPU, so the overall wall clock runtime of a single search iteration is equal to the per-task enumeration time budget. We set the enumeration budget (REGEX = 1000s, CLEVR 600s, LOGO 1800s). We ran DreamCoder until convergence on all domains. For CLEVR and LOGO, we performed 10 iterations of search, while for REGEX, observed that the solve rate was still increasing at iteration 10, so we used a higher search budget of 16 iterations for this domain. Following Wong et al. (2021) and based machine learning, we limited evaluation of the test set to every 3 iterations due to the computational cost of enumerative search.
per-domain basis using the timeouts from Wong al. (2021)
common practice in
GPT language models. For experiments in which GPT LLMs perform program search, the bulk of the computational workload is effectively offloaded to OpenAl's servers. Locally, the only re- quirements are that our machine is able to make API queries, process the results, and run compres- sion. Accordingly, these experiments are run on c5. 2x.2xl machines with 8 CPUs each. (For experiments involving combinations of GPT queries and DreamCoder search, we use the larger c5. 24xlarge machines.) To ensure comparability in solver performance between LLM-based and enumerative search-based experiments, we also run the LLM experiments with that the learning timelines are aligned.
Stitch. For compression, we make use of the Stitch Python bindings, which interface with a fast backend written in Rust (https: / seitthhhhbiiinng readthedocs. wt//e//taall/////////// Stitch exposes various hyperparameters, the most important of which are iterations, which governs the number of abstractions produced, and max arity, which governs the maximum number of argu- ments that each abstraction can take. For all experiments, and max-ar 3y=3. We note that Stitch will only produce an abstraction if it is compressive: i.e., appears in multiple programs, and rewriting the corpus in terms of the abstraction reduces the overall description length. For this reason, in rare cases early on in learning, when only handful of solved programs are available, the actual library size can be smaller than iterations. This behavior is beneficial in that it avoids introducing abstractions that have no utility and that might potentially negatively affect performance.
set these to constant iterations=10
A summary of hyperparameters can be found in A.5. For further implementation details, we refer to our codebase: gi thub. com/ ggbegranddlilll
22

---

Published as a conference paper at ICLR 2024
A.5 HYPERPARAMETERS
We provide a summary of all key hyperparameters used in each component of LILO.
DREAMCODER
Batch size:
96 tasks
Global iterations:
10 (CLEVR, LOGO), 16 (REGEX)
Search timcouts:
600s (CLEVR), 1000s (REGEX). 1800s (LOGO)
Neural recognition model:
10K training steps / ittration
STITCH
Max iterations:
10 (Controls max library size)
Max arity:
3 (Controls arity of abstractions)
LILO: LLM SYNTHESIZER
Prompts per task:
4
Samples per prompt:
4
GPT Model:
sode-davinci-088
Temperature:
0.90
Max completion tokens 3:
4.0x (Multiplier w/r/t the final prompt program.)
LILO: AUTODoC
Max usage examples:
GPT Model: gpt-3. 1ott-.5--uue S-turbo-0381 / gpt-4-0314
Top-P: 0.10
Max completion tokens: 256
23

---

Published as a conference paper at ICLR 2024
B EXPERIMENTS AND RESULTS
B.1 DOMAIN DETAILS
Language-annotated program synthesis domains
REGEX string editing
CLEVR scene reasoning
LOGO turile graphics
followers follwowersw
privater * prwivater
netal
add a w whenever a consonant followed by another consonant
sided snowflalie with small
pavings pavings enterprises onterprises
MMAM
It small pentagovis in row
rubber
the word begins with vowel replace that with b
There annther thing that the same color the
large rubber thing; what is made of?
stspppeed ststrcase
Figure 8: Overview of domains. We evaluate LILO on three lanquage-amnttated program synthesis domains: string editing with regular expressions, scene reasoning the CLEVR dataset, and graphics composition in the 2D Logo turtle graphics language.
#Tasks
Description length
String length
Domain
Train
Test
Train
Test
Train
Test
REGEX
491
500
38.95 + 26.11
41.03 + 27.02
276.47 + 179.92 361.62 + 182.06
262. 74 + 172.69 387.44 + 184.19
CLEVR
191
103
32.95 + 15.78
30.82 + 15.49
LOGO
200
111
24.65 + 8.71
27.79 8.19
250.98 + 92.75
287.17 + 89.65
Table 3: Summary statistics for the domains used in this paper. Description length the number termi- mals, lambda-abstractions and applications necessary to uniquely describe the ground truth program for each task; string length is the length of each program in terms of characters. Both are reported as the mean over the entire dataset plus/minus one standard deviation.
String editing. We evaluate on domain of structured string transformation problems-a classic task in inductive program synthesis (Lau & Weld, 1998). The dataset, originally introduced in Andreas al. (2018), contains procedurally-generaa
REGEX:
regular expressions that implement trans- formations on strings (e.g., if the word ends with a consonant followed by "s", replace that with b). Task examples consist of input/output pairs where the inputs are strings randomly sampled from an English dictionary and the outputs are the result of applying particular string transformation. Following prior work (Ellis et al., 2021; Wong et al., 2021), the base DSL in this domain contains functional various programming primitives for string manipulation (map, fold, cons, car, cdr, length, index) and character constants. Each example comes with a synthetic language description of the task, which was generated by template based on human annotations (Andreas al., 2018).
Scene reasoning. We extend our approach to a visual question answering (VQA) task based on the CLEVR dataset (Johnson et al., 2017). Following successful efforts in modeling VQA as program synthesis (Andreas et al., 2016; Hu et al., 2017), each synthesis task is specified by structured input scene and a natural language question. Outputs can be one of several types, including a number (how many red rubber things are there?), )). a boolean value (are there more blue things than green?), or another scene (what if all of the red things turned blue?). The dataset, designed by Wong et al. (2021), uses modified subset of the original CLEVR tasks and introduces new task types that require imagining or generating new scenes (e.g., how many metal things would be left if all the blue cylinders were removed?) that require learning new abstractions. The base DSL includes functional programming primitives similar to the regular expression domain, with domain-specific query functions and constants (e.g., get_color(x: (x); get_shape(x), blue; cube). Input scenes are specified symbolically as scene graphs consisting of an array of structured objects defined as a dictionary of their attributes, and programs designed to manipulate these structured arrays. Synthetic language annotations were generated based on the original high-level templates in Johnson et al. (2017) and human annotations were collected by Wong et al. (2021).
CLEVR:
24

---

Published as a conference paper at ICLR 2024
LOGO: Turtle graphics. Following in long tradition of modeling vision inverse graphics, (Knill & Richards, 1996; Kersten et al., 2004; Yuille & Kersten, 2006; Lee Mumford, 2003; Wu et al.,, 2015; Yildirim et al., 2020; Wu et al., 2017; Yi et al.. 2018: Gothoskar et al., 2021) evaluate on a domain of compositional drawing problems. The dataset, originally introduced in (Wong et al., 2021) and based simpler dataset from (Ellis et al., 2021), contains programs that generate shapes and designs in a vector graphics language. The DSL is based on Logo Turtle graphics (Abelson & diSessa, 1986), which originated from early symbolic AI research. Program expressions control the movement and direction of pen (classically represented as Turtle) on canvas and can involve complex symmetries and recursions (e.g., seven sided snowflake with a short line and small triangle as arms; small triangle connected by big spuce from small circle). The base DSL includes for loops, a stack saving/restoring the pen state, and arithmetic on angles and distances (Ellis et al., 2021). Synthetic language annotations were generated with high-level templates over the objects and relations in each task; human annotations were collected by Wong et al. (2021).
25

---

Published as a conference paper at ICLR 2024
B.2 LEARNED LIBRARIES AND GRAPHICAL MAPS
We generated graphical visualizations of the libraries learned by the best LILO model for each domain. Each graph includes the DSL primitives, the learned and named abstractions, and random sample of 3 solved tasks that invoke each abstraction. Arrows indicate direction of reference; i.e., fn_1 -> fn-2 indicates that fn_1 invokes fn-2, and analogously for the tasks.
26

---

Published as a conference paper at ICLR 2024
B.2.1
LIBRARY FOR REGEX
REGEX Library
Primitives
replace conconant, subs
replans pettrurrettterree
TUBSX
(oe avrd uas lord dlie bue
Vhe venticm with munt repict with
U'e ailh mord on like my for dut
Saroaa ancuse my Slon plore
Arroor cuet betor
sp Falletrirs
Ure wort iaso with to roter
and
spenirrevesse
No merr connent
ferer fetes will cherli
Oagan
reblas.nehhsesrriig
XM www.suttttingg... gratch
Vibe aper
oolace_oobste ifurach
Che repiee
andiant coseine aut
Bemoo emar the
Wh and lowe cemooeee by
Mon reyler
Figure 9: Graphical map of REGEX library learned by LILO. Named abstractions (turquoise) are hierar-
chically composed of other abstractions and ground out in the base DSL primitives (gray box).
27

---

Published as a conference paper at ICLR 2024
(fn_42) vowel_regex :: tsubstr (regex_or 'a' (regex_or 'e' (regex_or 'i' (regex_or 'o' ''')))>
(- Regular expression that matches any vowel ("a', 'e', 'i', 'o', '''). Used in various functions to identify and modify words based on vowel presence and position. -}
(- Example usages -}
-i there is consonant add s after that
(A saatce__subsrrin____meeeee
's' (regex_not vowel_regex) 50))
--if the word starts with vowel replace that with j
(A (regex_if (regex_match (regex_not vowel_regex) (regex_car (split_fullstring $0))) se $0 '1' 'J')))
--ff the word starts with vowel replace that with c
(A
stw..ifmaacchsuususrrett $0 (replace_ fictooorrreeeeeeeeeeeeee $0 'c' 'u') vowel_regex)
(fn_43) replace_substr :: tfullstr tsubstr tsubstr tfullstr
(A (A (A (regex_flatter (regex_map (A (regex_if (regex_match $1 so) $2 $0)) (regex_split empty_string $2))))))
(- Replaces all instances of given substring $1 in full string so with another substring $2. The substrings are separated by empty spaces. -}
(- Example usages -}
if there is replace that with
(A soplace_subbsee 50 'y' 'd'))
if there is replace that with
(A (replace_substrr so (regex_concat 'k' 't') 'i')
-i there is replace that with t
(A (replace_substr so (regex_concat 't' 'q') 's'))
(fn_44) ceatce__irsttoocurrree (A (A (A (regex_flatter (regex_cons 50 (regex_cons $1 (regex_cdr (regex_split '.' $2)))>>)))
:: tfullstr -> tsubstr -> tsubstr -> tfullstr
(- Replaces the first occurrence of substring in full string with another substring $2. The substrings are separated by periods. -}
(- Example usages -}
if the word starts with vowel replace that with
( (replace_if htf__aacc_substeeeeeeeetssssssee $0 (replace_first first_occurrenes $0 'b" 'q') vowel_regex))
if the word starts with consonant replace that with se empty_string '1')) iff the word starts with vowel replace that with
(A faatcc_ffrrtttccuure
(A (regex_if (regex_match (regex_not vowel_regex) (regex_car (split_fullstring $0))) se
'a' '1')))
tfullstr >> (tsubstr >> tsubstr) >> tfullstr (A (A (regex_flatten (regex_map $0 (regex_split ".' $1)))))
(fn_45) lastaae_eacc_uuusseee
(- Replaces each substring separated by periods in a given full string with substring. new substring can manipulated with a X function that takes each substring as input. -}
(- Example usages -}
--f there is replace that with $0 (A (regex_if (regex_match 't' $0) (regex_concat 'a' 'x')
(A saapllaceeach_ssusttee
$0))))
--if there is vowel replace that with f (A lalaaac_eecc_suusrriene $0 (A (regex_if (regex_match vowel_regex s0) (regex_concat
'a' 'f') (0))))
--f there is replace that with b.b.
(A rreplace_each_substre $0 (A (regex_if (regex_match 'c' $0) (regex_concat 'k' 'b')
)0))))
(fn_46)
:: tfullstr -> tfullstr tsubstr -> tfullstr
(A (A (A (regex_if (regex_mated _atch $2 (regex_car (regex_split '.' $2))) s1 $2)))) (- Replaces given substring $2 in full string $8 with another substring $1 if the beginning of the string matches the target substring. All substrings separated by periods. -)
28

---

Published as a conference paper at ICLR 2024
(- Example usages -}
--if the word starts with vowel add before that
(A pipplaaeif..aacchsuustttti
$8 feateenlattenn (regex_cons 'p' (split_fullstring
(0))) vowel_regex)
--if the word starts with consonant any letter replace that with $0 (regex_flateee (regex_cons 'f' (regex_cdr (regex_cdr (split_fullstri] s0))))) (regex_not vowel_regex))
(A sasplaceiif_macch_seee
--if the word starts with vowel any letter replace that with
(A treplace_if_maten maatcchsusttringggg.gg. $e (regex_flatten (regex_cons 'w' (regex_edr (regex_cdr (split_fullstrigg (0))))) vowel_regex))
(fn_47) add_new hww.ssbstring.tttt iifififa_hhh_/.eee tsubstr -> tsubstr tfullstr -> tfullstr (A (regex_if (regex_match $2 s0) (regex_concat $3
(A (A (A saclllac_eech_suuuteee
s0) $0))))))
(- Replaces each substring separated by periods in a given full string with a new substring, if specified substring is found. The new substring can be manipulated with À function that takes each substring input. -}
(- Example usages -}
if there is add w before that
(A
'w' 'g" s0))
--if if there is any letter add 1 before that
(A godd__ne_substring.tt _fattth '1' 50))
-- if there is add b before that
(A wwwpe/wwwwsrrinnnneeeeeee fuubstring_ff_matoo. _matcf 'b' 'r' s0))
(fn_48)
:: tfullstr tsubstr tfullstr (A (A (regex_flatten (regex_append s0 rregex_reverse_cde (regex_split '.' $1))))))
(- Appends a new substring to the end of the given full string and reverses the order of all substrings except for the last one (which is removed). -)
(- Example usages -}
if the word ends with consonant replace that with
(A aegpen__reverse_cdr so (regex_concat 'o' 'g')))
if the word ends with consonant replace that with
(A (regex_if (regex_match 'e' (regex_tail tail (split_fullstring $0)))
reppere
so (regex_concat 'n' 'a' 'a'))))
-f the word ends with any letter replace that with j
(A @append_reverse_cdd so (regex_concat 'o' 'J')))
(fn_49) replace_ wwwpssuuussstsf__meeeeee
tsubstr tsubstr tfullstr tfullstr (A (A (A preplace_each_substre $0 (A (regex_if (regex_match $2 s0) (regex_concat $0 $3) s0))))))
(- Replaces each substring separated by periods in given full string with new substring, if specified substring is found, using function that takes the current substring as input and replaces it with a new substring based on condition. -}
(- Example usages -)
-if there is vowel add i after that
(A (replace_substre) substring_iff ff_match 'i' vowel_regex $8))
if there is add e after that
(A
'e' 'c' s0))
-if there is add e after that
(A laraac__substring...
'e' 'n' s0))
(fn_50) split_fullstan fullstring :: tfullstr -> list(tsubstr)
(A (regex_split '.' $0))
(- Splits given full string into list of substrings separated by periods. -}
(- Example usages -}
-f the word ends with any letter any letter add after that
(A (regex_flatten (regex_append (regex_concat 'f" empty_string) (split_fullstring
)0))))
29

---

Published as a conference paper at ICLR 2024
--if the word starts with any letter replace with w
(A (regex_flatten (regex_cons (regex_concat 'w" 'i') (regex_cdr (sulit_fullstring (0)))))
--if there is any letter add after that
(A sreplace_each_suteee
$0 (A (regex_tail (regex_map (A (regex_concat 'v')) (split_fullstring $1)}))))
(fn_51) applace_consonant_wwe witps//wtthhhhhhinttnt tsubstr <> tsubstr -> tfullstr >> tfullstr $0 51 $2) (regex_not
(A (A (A
$0 (replace_first_occuree
rowel_regex))))
(- Replaces the first occurrence a consonant at the beginning of given full string with specified substring. The target substring can also be modified before replacement using another specified substring. -}
(- Example usages -}
-if the word starts with consonant replace that with
(A gopplace_consonant_wwa wiwhantttwihhsuusrrigg. 'i' 'q" s0))
--if the word starts with consonant replace that with d sighoanttwtthssuutrring 'g' 'd' $0))
if the word starts with consonant replace that with p
(A (replace_consongg coneooanttnnnntt..... wi tuusstrii 'p' 'b" $0))
30

---

Published as a conference paper at ICLR 2024
B.2.2 LIBRARY FOR CLEVR
CLEVR Library
Primitives
Mccoaa DOV ond cingiing mual
day
and
FLLEe CENECEE 30LLL 3128
cond gfai
diee
FLlber dbjacca by color
hor Mey
Fllber socercal
dennffrne
C/a brom spor
filer dejecta by rabker raturias
oleer
stive SEaNEEA
Figure 10: Graphical map CLEVR library learned by LILO. Named abstractions (uurquoise) are hicrar- chically composed of other abstractions and ground out in the base DSL primitives (gray box).
31

---

Published as a conference paper at ICLR 2024
(fn_54) filter_by_size :: tclevrsize 1ist(tclevrabject) List(tcleerobject) (A (A (clevr_fold s0 se (A (A (clevr_map (A (clevr_if (clevr_eq_size cclevr_query_size s0) $4) so $2)) $8))))))
(- Returns list of objects in the input list that have the specified size.
(fn_55) filter_b__color collor :: tclevrcolor lise(tclevoojject -> list(tclevrobject) (A (A (clevr_fold so clevr_empty (A (A (clevr_if (clevr_eq_color (clevr_query_colll
$1) $3) (clevr_add $1 s0) $0))))))
(- Returns list of objects in the input list that have the specified color. -}
( Example usages -}
--what color is the small metal thing behind the small purple metal thing (A (clevr_query_ query_color (clevr_car fillte_objfcce casists_bmmttrrraa httpr_obeetss_b_ssaalllase
(clevr_relate (clevr_car sillter_by_cole clevr_purple (filter_objects... bayaatersabymmttrrialllll [filter_objeetssbbysmallll bysasll____ymmmlsiii_e__ $0))))
$8) ))))
--what is the size of the gray thing (A (clevr_query_size (clevr_car (filter_by_colae clevr_gray $8))))
h-how many thing are red thing s large green thing
(A (clevr_count (clevr_union (filter_by_color clevr_red $8)
(filter__arge_ojjeetts byw.ebebesttssiiieee... bizsize (filter_by_colle clevr_green $8)))))
(fn_56)
:: tclevrmaterial >> list(tclewrobject) >>
(isevtclevoo)ject)
(A (A (clevr_fold clevr_empty (A (A (clevr_if (clevr_eg_materia (clevr_query_materiil $1) $3) (clevr_add $1 $0) 50))))))
(- Returns a list of objects in the input list that have the specified material. -}
(fn_57) filter_ ciiter_object__bycooo Listttelevoobject)
:: tclevrshape -> list(tclevrobject)
(A (A (clevr_fold se clevr_empty (A (A (clevr_if (clevr_eq_shape (clevr_query_shape
$1) $3) (clevr_add $1 s0) $0))))))
(- Filters list of objects to include only those with the specified shape. -}
- Example usages -}
- find the cube
a (filter_objects.. obwjecssby_shhpaeeeeeeeeeeeeeeee by__pp clevr_cube $0))
find the rubber cube
( (filter_objects_u) htrrttsbbbbuubbbemmeeeeeee
ceatter_bjject_bby clevr_cube $0)))
- if you removed the cylinder how many large thing s would be left
(A (clevr_count (clevr_difference (filter_large lyw.ar__oooettssby..ieee $0)
ffilter_objects_byyooo
clevr_cylinder $0))))
(fn_58) cilter_objects_by.co
:: tclevrcolor >> list(tclewrojject)
listtceleroobject)
(A (A (clevr_fold s0 se (A (A (clevr_map (A (clevr_if (clevr_eq_color
(clevr_query_cooee s0) $4) $0 $2)) $0))))))
(- Returns a list of objects in the input list that have the specified color. -}
(- Example usages -)
-- find the gray rubber thing
(A bbwerrs_bjeccbbb_e_eeee wwat is the thing that is front the brown thing made
www.bbr_mtterialll fiilter_objects. bytto_ clevr_gray $0)))
(A (clevr_query_n) www.mmateaaal....m. _uwrrrrmrmmmtteiaallll.. (clevr_car (clevr_relate (clevr_car (filtter.bjecct._yycom
clevr_brown s0)) clevr_front $0))))
--what number of small objects either metal cube red rubber thing
(A (clevr_count
(clevr_unio)
.ymtterial
(filter_ _esrtts__b__hppeee____ clevr_cube $0)) hiiiter_obeects.byyrbbber (filter_oojjects_byccollll clevr_red $8))))))
(fn_59) filter siiter.objects_b__naaa
list(tclevrabject) list(tclevrobject)
(A (filter_by_st clevr_small $0))
(- Returns a list of objects in the input list that are small in size. -}
Example usages -)
32

---

Published as a conference paper at ICLR 2024
--find the small red thing
(A (filter_objects.. obbjects_bb_ssmllssiiee (filterr_bjects__yycokkk clevr_red $0)))
--find the small thing
(A (filter_objects_b) jeyejett_bb_smal_iiie s0))
--what number of small objects either blue metal thing rubber thing
(A (clevr_count
(clevr_union
rubbeerrrbb.rrbbbrrrrrr.....rrer (fllte__object__byccllll clevr_blue (8))))))
$0) seterr/bbeetttbbmeterrrreee
(fn_60) Filter_objects_by_matee :: (ise(tceevrobjeet) 1ist(tclevoobject)
(A callter_b_mmaterice clevr_metal. $0))
(- Returns a list of objects in the input list that have the specified material. -)
(- Example usages -}
there a metal cylinder right the small purple metal thing (A (clevr_if (clevr Seteer_ee_shapppp clevr_cube (clevr Letevrr_uery_shappp (clevr_car (clevr_relad relate (clevr_car (clevr_union so caattr_objects_b__matee
size
$8))) clevr_right $0))))
clevr_small clevr_large)
--what if you removed (filter_objects_byy
blue metal thing
(A (clevr_differen)
clevr_blue hel.ttrr.obeets..yymtttteee
$0))))
--find the small metal cylinder
(A (filter_objecte peeeets_b_ssmal______ee_ clevr_cylinder 50))))
(filter_ooeecs_byymattriaa (filtter_objects_by_bhe)
(fn_61) count_ booiriingooeeeett....ooooooooo
1ist(tclevrobject) >> tclevrcolor
-> tclevrshape -> int
(A (A (A (clevr_count (clevr_differ) difffrencceeee hiilter_ojjects_by.sse $0 $2)
$1 $2))))))
(- Counts the number of objects that remain after removing objects of specified color and shape from the input list of objects. -}
(- Example usages -}
--f you removed the brown thing s how many sphere s would be left
s0 clevr_brown clevr_sphere) -if you removed the red cube how many cube would be left clevr_red clevr_cube))
(A
(A (count_remaining.uu wtwpeooeeeetteeooeeeeeeeee
if you removed the cyan cylinder s how many cylinder s would be left
(A
byy
$0 clevr_cyan clevr_cylinder)
(fn_62) silter_objects.o btwbbybbr__aaaaaaeeeeeeeeeeeeeee mat.riallalll... list(tclevrobject) Liseecceevoobject)
(A ffilter_by_materit dlevr_rubber $0))
(- Returns a list of objects in the input list that have rubber as their material. -}
(- Example usages -}
what number of sphere s small cyan metal thing s small rubber thing
(A (clevr_count (clevr_union (fillterobjeets_. byyttrial
www.robbbettbyssmaeeeee size sitteer_ojjeets_b__hheeeee clevr_sphere 50))))
(filter_by_color clevr_cyan htrpjjees__bbuuube_eeeeaeaeeeeee (filterr_bjectts__y_hhee clevr_sphere $0))))))
(filter_objects_uu obyjectst.byssmllssiie.
--what number of rubber objects are purple thing cylinder
(A (clevr_coum) bottter_bbjecs_bby https_errubbbbruueeeeeeeeeeeeeee
wtw.brrebattrrialllllllaaa _material (clevr_union
ciatter_bjjett_bby )0))))>
clevr_cylinder $0) Ffilter_objects.t
clevr_purple
--what number of cylinder either large rubber thing small blue rubber thing s0)
(A (clevr_coun) (clevr_intersed (filter_obh bybberttt.b. ciitter_bjjects_byghaaa clevr_cylinder $0))))
(fn_63) filter_ Laarr__rre__ojeeee srrectssby_siii list(tclewrobject) list(tclevrobject)
(A (filter_by_sias clevr_large $0))
(- Returns a list of objects in the input list that are large in size. -}
(- Example usages -)
find the large metal sphere
33

---

Published as a conference paper at ICLR 2024
(A (filter_large_okls htw.__aarrgeobeets..bb.. byjeccs_bb_siiee @filter_obfectss.bymmteeeer (filttrr.ojject__by.ll))) clevr_sphere s0))))
--there is a large thing front the small metal cube what is its shape
(A (clevr_query_shi)
(clevr_car (filter_large_obbe byrrgee__jecct_____e_e (clevr_relate (clevr_car
wtt.ooeeet.....maerrrriie. (filter__dbfects_yy.ee clevr_cube $8)))) clevr_front $0)))})
--what number of cylinder are either large rubber thing s or small blue rubber thing (A (clevr_couu [filter_objects__yy.
clevr_cylinder (clevr_union
Laalter_larg__bjjcttsbb. fiilter_hjectts___smmlllL (filter_by_coll clevr_blue (filter__bjects._ wubbrtrr_e_uubbbb_eaam $0)))))))
$8))
34

---

Published as a conference paper at ICLR 2024
B.2.3
LIBRARY FOR LOGO
LOGO Library
turcle smoue T www.vvtthaooe vith.rre
Fedestannfhle with eddist
Primitives
Toaki sakccaneeeee faie malh seall trangle
pnownIckc A13h, rotosing ams
sacuffll wot reuting eccaie)
logo www..iisk...oo anaie
Burkle www.lloo.pp...oooooo Jove aoow aww..rdaaa nolate
sendd Sgan
Zepu angla
divide Zune
hip.avztrect-amgge angika
turtll. turtle.stall stalrcase
Inpuastaangto
turtlo sn ahort,
lift
Fakd bren faie aot maalim una to anau
Has
Tresupprtto__ion
turtle_snall Bertle_saal__ineeeeee -ine.ciieee
Caxat gaxr. crow
Figure 11: Graphical map of LOGO library learned by LILO. Named abstractions (turquoise) are hierar- chically composed of other abstractions and ground out in the base DSL primitives (gray box).
35

---

Published as a conference paper at ICLR 2024
(fn_27) portle_loop_aae _oop__ovee_oottee :: turtle -> int -> tlength -> turtle
(A (A (A (logo_for_loop $1 (A (A dogg_move_pen_forrrrdd.mm ongo_unit_angle $3) $0))) $2))))
$2 (logo_divide_angLL
the turtle forward and rotate it by specified angle, creating (- Repeatedly
loop of specific number of sides with given line length. -}
(- Example usages
--a small square
(A Ccurtle__oop_oov__rrtet 50 logo_unit_line))
a small gon
(A Lurrtle_loop_mve_rotttee so (ogo_unit__lne))
- short line
(A (ture so logo_unit_linee
(fn_28) turtle_staircase :: turtle
turtle
(A (A (logo_for_loop se (A (A htt__ove_pe_ffrwarrree
aago_unit_lime
Llgg_divvid__nngu. oggo_unitaangle 4)
logo_unit_line
Llogossubrract_anglee ongo_unit_anglz (logo_divide_angll Logo_unit_angle 4)) 50))) $1)))
(- Creates a staircase pattern by repeatedly moving the turtle forward rotating at specific angle. The number of steps in the staircase is determined by the function argument. -}
(- Example usages -)
- 4 stepped staircase
(A surtle_staircan $0 4))
7 stepped staircase
(turtle_staircase 7))
-ma 4 stepped staircase
(A (turtle_staircase $0 4))
(fn_29) turtle_loop draw www._pentagon_ssiree :: turtle int turtle
(A (A fogo_for_loop se (A htt__ove_pee__orwrrdeee
logo_zero__inn bogo_epsilon_angle 8) (logo_for_loog 9 (A (A
logo_unit_line (logo_multiply_angl. logo_epsilon_angl. 8)
s0))) $0)))) $1)))
(- Creates a spiral of pentagons by repeatedly drawing pentagon and incrementing the angle each side on each iteration. The number of pentagons in the spiral is determined by the function argument. -)
(- Example usages -}
4 small gon in row
(A htw__ooppddraa_eettgaooooo
$0 4))
--3 small 5 gon in row
(A httpaaaloopddraa.eentagoooooo_e
$0 3))
small gon in row
(A htt.:/looop.rra..ettaaog..ss
$0 6))
(fn_30) turtle_squarerre
turtle -> int -> turtle
(A (A (logo_for_loop se (A (A tetg__mov__pe__frwarrdee
logo_zero_line
geso__dvide__ange_ logo_unit_angle
(logo_for_lee loop 7 (A
(logo_move move_pen_foore pen_forward_rotate logo_unit tnine sigo_divvid_anee logo_unit ung_unit_angle 4) (0))) $8)))) $1)))
(- Draws a row of small squares using repeated forward motion and rotation. The number of squares in the is determined by the function argument.
(- Example usages -}
- small square in a row
(A (turtle_square_row $8 4))
small square
(A (turtle_square_row $0 6))
-5 small square s in a row
(A (turtle_squrre_row $8 5))
36

---

Published as a conference paper at ICLR 2024
(fn_31)
th_arms :: turtle -> int
turtle
(A (A (A flogo_for_loop $0 (A (A low_le__ooo__ee_e_eeee_______eee htt.mme__eeefooweec
logo_zero__na __ne_
logo_unit_angle $2) $0)
$3 [Logomulttiply_ing
aego_unit_lee
2)))) $2))))
(- Draws snowflake shape with given number of arms, each made of line of speci length that is rotated at a specific angle. The angle by which the lines are rotated
increases with each iteration of the loop, creating an intricate snowflake pattern. -}
(- Example usages -}
sided snowflake with medium gon as arms
(A (turtle_snowflate wwwwfllakwwwthh witt_arms $0 5 7))
6 sided snowflake with medium triangle as arms
(A luutlle_snowflakeee wirkharmssss
ammt $0 6))
sided snowflake with medium triangle
(A (turtle_snowf]a wwwehowwwakwwwtttte wit__witt_aamss aarm $0 7))
(fn_32) wurtle_smallline_cireee
turtle -> int >> turtle
(A (A (logo_for_lode 1ogo_IFTY (A (A (logo_move_ppe ftw_pe__oorwwrrrrootttt (logo_muttiply line logo_ aego_epsilon_liee $2) oogo_epsilon_anee
$8))) $1)))
[- Moves the turtle forward and rotates it repeatedly to draw a small circle with a given line length. The number of iterations is determined by the function argument. -}
(- Example usages -)
small circle
(A fogo_for_loop (A (A (turtle_small_line_ciiii $0 1))) 50))
- big semicircle
(A line__iriieeecrrlelee s0 5))
big circle
(A (logo_for_loop (A (A Buurtl_small_lin____ee
$0 5))) s0))
(fn_33) snowflake waaeeeiith_rottttiee arms turtle -> int -> int >> turtle
(A (A for__por_loop (A (A (turtle__oop_move _otop_ wtw._ovveeee_foowrrrr
logo_zero_line (logo_divide_ange) logo_unit_angle $2) $0)
$3 Logo_unit_line)) $2))))
(- Draws a snowflake shape with given number of arms, each made of line of specified length that is rotated at specific angle. The angle by which the lines are rotated increases with each iteration of the loop, creating an intricate snowflake pattern.
(- Example usages -)
- sided snowflake with small 9 gon as arms
(A (snowflake http::twtwttttn__aaa_____
$0 7))
sided snowflake with small 7 gon as arms
( httpr/akewwithrotttiineee
$0 6))
8 sided snowflake with small triangle as arms
(A
$0 8))
(fn_3) loop_eeetthhooooeeeeeeeeeeeeeeee
:: turtle -> turtle
(A (A
$0 $1 (logo_muttiply_Iig logo_unit_line 2))))
(- Moves and rotates the turtle in loop, with each iteration doubling the length of the turtle's movement. -)
(- Example usages -}
a medium 5 gon
( Boubble_Jenghh_ooop_mvvrraaaaa 5 $8))
medium triangle
( ddobble_Jenggh_oooop_oveeetaaa 3 $8))
a medium 8 gon
(A doobble_eenggt_oooo_moeeertaaaa 8 S0))
(fn_35) Bitee_drawshhr_______ :: turtle int turtle
(A (A (logo_for_loop s0 (A (A herpr/ove_eee_foowrrdd.o.
logo_unit_ u
logo_umg aago_unit_angla $0))) $1)))
(- Draws specified number of short lines in row using repeated forward motion and rotation. -)
37

---

Published as a conference paper at ICLR 2024
(- Example usages -}
--5 short line s in a row
(A
50 5))
short line
(A (turtle_draw.short_linn so 4))
3 short line s in a row
(A [turcle_draw_short_iinss se 3))
(fn_36)
tlength -> turtle :: logo_unit_ang/e $1) logo_unit_line Logo_diivdd__agll ungo_unit_angle 2)
(A (A (A (logo_mon _ee____eeee______________ forward_rotate so bigo_divide_angll
move_pen_forward_mmm $2))))>
(- Moves the turtle forward and rotates it at given angle. Then the turtle forward again and rotates at half the angle, creating pivot point the turtle to change direction. The distance the turtle moves each time is determined by a given length parameter. -}
(- Example usages -}
a vertical short line
(A
$0 4 (ogo_zero_line)
short line
(A www.oorrddtttteeeeoeroeeeeeeeeee httpe//oee_eeeorwwrrrrrrttttttt s0 logo_unit_linee)
sided snowflake wi short 1ine as arms
(A (logo_for_lopp (A (A [ee.:foovarc..oaee.......eeooorr $0
logo_ (gg__uni__line)) S0))
38

---

Published as a conference paper at ICLR 2024
B.3 BENCHMARK COMPARISON TO PRIOR WORK
Langrage
Strtege Irour
Coaplics Chee
Selval
Salval (Boi)
Subooll (Mest)
R Subved (Cumi))
% Siéval (Mom)
Santh mainlei
DreunCede: (so laeguaze)
35.4
40.55
42. 64
07.80
73.9
Synth tnvertoo
Mullimodal (in groerttvve immiition model)
76.
76.90
40.5
$3,20
92.79
52.93
95.6
36.1
tnvinfent
LAPS exclusvity
57.00
$6.09
M01K
96.5
62.3
Synta tuintle
LAPS ME lazguaze propran compeession
$4.60
98.19
8198
95.6
95.9
Synth framnatmaa test
LAPS kaguuge prgran conpeession
58.00
$9.20
97.6
Elmm tranclummn
lasguge Ieguuge-nograa grogram compession
43.60
58.53
95.6
languege
No language insinhent
Onginnl DSI: Snumerative
8106
0180
87.8
No languass on mnanieess lang sod
DreanCede (bex libnay): Enumerative
27.2
41,44
53.6
thoa lirry:: Fummrrtiie
91.04
(est lhruryl: eumple only neard syathssi
52.4
95.6
Table 4: Percent held-out test-tasks solved for LAPS. Best reports the best model across replications; Mean averages across replications. (Reproduced from Wong et al., 2021.)
Soheed (0. 1006a
Dream Coder (no language)
Muliindaa geserativ))
LAPS sound sesech
LAPS mitual exclushiit
LAPS ME lang compresiio
Lourning Deration: (0 27)
Figure 12: Learning curves comparing baselines and LAPS models in Table 4, showing % heldout tasks solved on the graphics domain over random training task orderings. (Reproduced from Wong et al., 2021.)
Our results from $4 are directly comparable those from Wong al. (2021). The primary results from that work are reproduced in Tab. 4, where Strings corresponds to REGEX, Graphics corre- sponds to LOGO, and Scenes corresponds CLEVR. The DreamCoder baseline from our work, which uses the language-conditione
recognition model from Wong et al., is comparable to the "LAPS in neural search" condition in Tab. 4, with the key difference being that we do not use the IBM translation model component. (We also run on larger batch sizes to take full advantage of the available CPU parallelism on our cloud hardware.)
On REGEX (Strings), with the use of LLMs for search, our LLM Solver and LILO conditions perform significantly better (93.20 best vs. 57.00 best) than this prior work, even without explicitly computing language/progrant alignment via translation model. On CLEVR (Scenes), our models perform comparably to LAPS: the DreamCoder baseline already solves almost all of the tasks the test set (97.09 best), and LILO brings the best solve rate up to 99.03.
Finally, on LOGO (Graphies), our models generally underperform with respect to the results re- ported in LAPS (73.87 LILO best vs. 92.79 LAPS best). It is worth noting that the best run from LAPS on this domain appears to be an outlier (see Fig. 12, LAPS in neural search), so a comparison of average results (48.95 LILO mean vs. 52.93 LAPS mean) may be more appropriate. Moreover, even matching the 1800s search time, we were unable to obtain a DreamCoder run that matches their equivalent LAPS baseline this domain (28.53 DreamCoder (ours) vs. 42.64 DreamCoder (LAPS)). This finding suggests that the LOGO domain is particularly well-suited to the token-to- token assumptions made by the IBM translation model from Wong et al.. It also worth noting that only the DreamCoder and LILO conditions, which train CNN-guided neural recognition model as part of enumerative search, have the ability to condition on the LOGO drawings. In particular, the conditions that rely exclusively on LLM -LMdddddedd search must infer what to draw solely based on the task descriptions; an exceedingly difficult generalization task.
39

---

Published as a conference paper at ICLR 2024
B.4 EXPERIMENTS WITH HUMAN LANGUAGE DESCRIPTIONS
Each of our domains provides a default set of language task descriptions that were generated syn- chronously with the ground truth program(s) for each task. Following Wong al. (2021), these synthetic language annotations for our primary experiments, as these descriptions correspond closely and systematically the target programs. we also evaluated our methods on human language annotations sourced from Mechanical Turk. These were collected by Wong al. (2021), with the exception of the REGEX domain, for which the annotations were sourced from the original (Andreas et al., 2018).
test generalization real-world applications,
We ran experiments with key subset of model conditions compare performance on human vs. synthetic language. Fig. 13 and Tab. 5 summarize the results from these experiments. In general, synthesis performance with human language upper-bounded by performance with synthetic lan- guage. This is expected, the human language contains wide range of lexical and syntactie varia- tions. For instance, for an individual LOGO task involving drawing a snowflake, human annotations range from "3 sided snowflake with arms that are lines with semi circle at the end" to "3 candy cane shapes with spaces in them," " with one annotator simply stating, "boomerang." Compared to the more templated synthetic language, the broad variation present in the human annotations makes it more difficult to infer a mapping between the language and target programs.
Our experiments reveal that both search and library learning appear to be important achieving bust performance on human language. DreamCodes achieves remarkably consistent performance be- tween the two language types. In contrast, the LLM Solver baseline degrades markedly on CLEVR and LOGO with human descriptions, We see that adding search [LLM Solver ( Search]] helps to mitigate this gap. Introducing the full library learning pipeline [LIIO] further improves robustness to human language, while achieving better overall performance than DreamCoder.
DreamCoder
LLM Solver
LLM Solver (+ Search)
UIO
100
Tasks solved (%)
80
domain REGEX
40
20
12
15
100
Tasks solved (%)
domain CLEVR
60
40
20
3
0
3
3
6
100
Tasks solved (%)
80
Comeoo 0001 000
40
20
3
6
Iteration
Iteration
Iteration
Iteration
Language source
synthetic
human
Figure Learning curves illustrating performance select models on human vs. synthetic language annola- tions.
40

---

Published as a conference paper at ICLR 2024
SYNTHETIC LANGUAGE: TASKS SOLVED (%)
REGEX
CLEVR
LOGO
MODEL
mean
std
meon
std
mean
std
DreamCoder
45.60
43.93
1.53
97.09
94.50
2.44
36.94
28.53
13.79
LLM Solver
90.00
76.13
12.04
90.29
88.67
1.48
41.44
32.13
8.07
LLM Solver (+ Search)
91.20
76.60
13.02
97.09
96.44
0.56
45.05
37.84
6.80
LILO
93.20
77.07
14.14
99.03
96.76
3.12
73.87
48.95
22.15
HUMAN LANGUAGE
TASKS SOLVED (%)
DreamCoder
49.40
46.20
4.39
95.15
94.50
0.56
34.23
25.
7.85
I.LM Solver
68.60
68.00
0.60
66.02
63.11
4.23
8.11
8.11
LLM Solver (+ Search)
71.60
71.53
0.12
94.17
93.20
0.97
20.72
16.82
3.64
LILO
71.40
70.60
0.92
99.03
94.82
3.92
39.64
30.03
9.07
Table 5: Solution rates of select models on human vs. synthetic language annotations.
41

---

Published as a conference paper at ICLR 2024
C ADDITIONAL EXPERIMENTS AND ANALYSES
C.1 COMPUTATIONAL EFFICIENCY ANALYSIS
Given that program search is the most computationally expensive component of synthesis, we would like be able quantify and compare the compute costs LLM- and enumerative search. However, performing an poples-to-applees comparison is non-trivial because the source of these costs different between the two cases. As discussed A.4, enumerative search requires high degree of CPU parallelism, so the primary cost associated with running DreamCoder in our experiments is the on-demand CPU-hour cost renting suitably large machines from AWS. In contrast, LLM search is GPU-intensive, and (in our implementation) is performed external servers for which do not have access to exact specifications or cost metrics. In practice, OpenAl's API, charge fixed price per text token, the primary costs of LIL--style program search arise from the number of LLM queries, the length of the prompts, and the desired completion length.
models, such
In this section, we compare the computational efficiency of the two search approaches across three fronts. First, consider wall clock time, which-in addition being informative metric in its own right-also allows us to compute a cost basis for enumerative search. Next, we consider token usage, which allows us compute a cost basis for LLM search methods. These analysis culminate in to-oolr comparison that, while dependent on pricing schemes of third third-parties and the markets more generally, nevertheless offers the closest means of direct comparison.
CLEVR
Model
DreamCoder
test
LLM Search
LLM Solver (+ Search)
LIDD (No Search AutoDoc)
LILO Scarch)
LILO
train
Enumerative Searth
train
2000
4000
6080
250
500
750
1000
500
1000
1500 2000
Wall clock time (sec.)
Wall clock time (sec.)
Wall clock time (sec.)
Figure 14:
search procedures and domains. Each bar shows average runtime single iteration train/test program search (error bars indicate 95% confidence intervals). Even with network latency from interfacing with OpenAl servers, LLM search (top row), typically requires less exccution time than enumerative search (bottom row), which runs locally on a 96-CPU machine.
Comparison of wall clock runtimes
We start by analyzing observed ka. "wall clock") runtimes of our different models. Fig. 14 breaks these down by domain, where the x-axis corresponds to the average time to perform a single search iteration during training and test.² Overall, observe that even with network latency from inter- facing with OpenAl servers, round of LLM search typically runs more quickly than an equivalent round of enumerative search. This difference is especially pronounced on LOGO, which requires longer search times (the enumeration budget for the DreamCoder baseline is set on a per-domain basis using the timeouts from Wong al. (2021); see A.4 for more details). We do not observe
NNote that in Fig. 14, despite appearances, for a given model on given domain, per task search times between train and test splits are approximately equal. Any apparent within within-conditinn condition discrepancies between train and test are due to the fact that during training. we search minibatches of 96 tasks, whereas during test, search on the entire test set. Thus, for domains where the number of tasks is many multiples of the batch size (c.g., REGEX), there is larger discrepancy hetweeen train and test search times.
42

---

Published as a conference paper at ICLR 2024
1.4
Model
LLM Solver
LLM Solver Search)
ULO (No Search AuteDoc)
GPT tokens used per train iteration
1.2
ULO (No Search)
LILO
1.0
REGEX
LOGO
Domain
Figure 15: GPT token usage per training iteration. Token usage provides useful metric for assessing the computational costs of LLMedased program search. typical training iteration uses on the order of 0.8M- 1.2M GPT tokens between the prompt Boxes indicate quartiles of the distribution and whiskers extend to 1.5 inter-quartile ranges, with outliers shown as individual points.
completion. (Note the y-axis measures millions of tokens.)
major differences in runtimes within the different LLM Search conditions, though is worth noting that the LILO and LLM Solver Search) conditions require approximately 2x total runtime than the other models because they perform both LLM-based and enumerative search on each iteration.
Next, consider the token usage of the LLM solver conditions. Fig. 15 breaks these down by domain and model. A typical training iteration uses on the order of 0.8M-1.2M. GPT tokens between the prompt and the completion. For completeness. all models are shown separately, but we do not note any clear trends in token usage by model; all models empirically use similar token counts. This may be because token usage influenced by a complex interplay of several factors. Better- performing models will require fewer queries per task to discover solution, so they should use fewer tokens. (In practice, however, we cap Pprompps per task and all conditions must make least one query per task, so the number of queries is bounded fairly tightly.) Models that use Stitch for compression (i.e., everything except the LLM Solver models) will also tend to benefit from shorter program description lengths per task. In particular, the LILO Search AutoDoc) condition, which uses anonymous function names (c.g., fn 42), tends to use the fewest tokens per task. However, because "pack the prompt" with many examples influence token usage; though, as we discuss throughout, too much compression could affect token usage indirectly by obfuscating program semantics, therefore making the LLM solver require more queries to solve new tasks.
fit, per-task description length does not directly
Finally, in the spirit of providing apples-to-apples compute cost comparison, we combine our time cost and token cost analyses to estimate a dollar cost for each model per training iteration. For conditions that perform enumerative search, we compute CPU cost using the on-demand AWS EC2 instance price for a c5. 24xlarge machine in us us-east-2, currently priced at $4.08 hr. Mcanwhile, for conditions that involve LLM search (everything except DreamCoder), we compute L.M infer- ence cost using OpenAl's current API pricing. As discussed in $3, our experiments took advantage of OpenAl's Codex model beta for researchers-in other words, they were effectively free. Ac- cordingly, we estimate the cost of our queries using OpenAl's more recent gpt-3. 100-3.5-tuune 5-turbo model, which is available to the public and priced at $0.002 per 1K tokens (at the time of writing). For the choose not to factor in the cost of rumning "head node" to issue API
LLM solver cost analysis, queries, as this machine is an order of magnitude cheaper than the c5. 24xlarge. has no specific spec requirements, and could be arbitrarily downscaled
replaced with laptop.
43

---

Published as a conference paper at ICLR 2024
REGEX
CLEVR
LOGO
mean
std
mean
std
mean
std
LLM Search
LLM Solver
$1.65
$0.35
$1.66
$0.44
$2.19
$0.32
LLM Solver (+ Scarch)
$1.70
$0.33
$1.88
$0.29
$2.13
$0.30
LILO (>e Search AutoDoc)
$2.04
$0.39
$1.66
$0.47
$1.59
$0.24
LILO (>< Search)
$1.86
$0.30
$1.70
80.52
$2.03
$0.31
LILO
$1.77
$0.38
$1.87
$0.42
$2.01
$0.30
Enumerative
DreamCoder
$1.16
$0.01
$0.71
$0.01
$2.07
$0.01
Search
LLM Solver (+ Search)
$1.14
$0.00
$0.69
$0.00
82.11
$0.06
LII.0
$1.16
$0.00
$0.71
$0.00
$2.07
$0.00
Table 6: Dollar cost comparison between LLM-based and enumerative search. Each entry is the cost of running one training iteration of search, estimated based measured wall-clock time (for enumerative search) token usage (for LLM search). As rough heuristic, find that iteration of LILO'S LLM-amortized search scheme approximately equivalent an 1800-second enumerative search on CPUs or, about 48 CPU-hours- in terms of compute cost.
Tab. 6 summarizes the results of this analysis. Remarkably, despite the fact that LLM-based and enu- merative searches use very different compute platforms with prices set by two different third-party companies, the dollar costs per training iteration come out within the same order of magnitude- indeed, they are approximately comparable. In general, we find the tradeoff between LLM and enumerative search be closely tied the search time budget: domains with shorter enumeration timeouts (e.g., CLEVR) cost 2-2.5x less than L.M search, while domains with longer enumeration timeouts (e.g., LOGO) cost about the same. Therefore, as a rough heuristic, we can say that one iteration of LILO'S LLM-amortized search scheme is approximately equivalent to 1800-second enumerative search on 96 CPUs-or, about CPU-hours terms of compute cost.
Of course, this cost analysis is heavily tied to market factors that are subject to change-in particular, hardware, electricity, and logistics costs that AWS and OpenAl face in operating their compute platforms, as well the profit margins that their pricing schemnes bake in. Nevertheless, noteworthy that it is currently possible to implement a search scheme like LILO- sito-wwhich requires thousands of L.LM queries over millions of tokens per training iteration- generally achieving better solution rates, faster wall clock runtimes, and comparable dollar costs to enumerative search. Moreover, note that general-purpose cloud compute platforms like AWS have been available for many years; especially as Moore's Law is believed to be reaching its tail end (Theis & Wong, 2017), we are unlikely to see significant reductions in the cost of large-scale CPU compute. In constrast, the aL---ae---ervviee model is recent innovation; with increased scale, hardware optimizations, product maturation, and growing market competition, we are likely see the costs of LLM inference decrease dramatically in the coming years. We are particularly excited about the growing diversity of open source I.LM packages, which should make possible to implement LII.O in even more cost efficient manner and with increased control over cost-performance tradeoffs.
find
44

---

Published as a conference paper at ICLR 2024
C.2 CAN LLMS PERFORM COMPRESSION?
In $4, we found that a pre-trained LLM is able to successfully perform the role of a program syn- thesizer, generating programs expressed in lambda calculus to solve novel tasks. Accordingly, is natural to ask whether LLM can also assume the role of compression algorithm, generating useful and reusable abstractions to form the library. This question is central to the neurosymbolic claims of this work: if a LLM can be used for compression. then we could implement a version of LILO where all three modules in the framework are parametrized by LLMs.
Here, we set out to answer this question by benchmarking GPT-4's ability to generate useful abstrac- tions when prompted with set of programs. We began by constructing a procedurally generated prompt format (Fig. 18) that combines prompting techniques used for LLM-guided synthesis and AutoDoe, As with LLM-guided synthesis, context window limits require subsampling exemplars from the set of solved tasks. We explored two distinct subsampling methodologies:
1. Random sampling selects a fixed number of tasks without replacement. In our experi- ments, each prompt incorporated 30 program examples.
2. Clustered sampling divides the of solved tasks into k clusters of semantically-related tasks and attempts to generate at least one abstraction for each cluster. We first generated embeddings for all task descriptions using the text-embedding -nn-ada-002 from OpenAL. Next, we ran k-means clustering to group all solved tasks into a fixed number of clusters based on these embeddings. In our experiments, we set max(10, I 1 D). where N is the total number of solved tasks at particular iteration, to ensure each cluster contained at least examples. Finally, for each cluster, we subsampled a maximum of 30 examples to use in the prompt.
We evaluated our LLM Compressor against Stitch in a controlled compression experiment using both sampling methods on all three domains. At each iteration, we provided both compression procedures with an identical frozen set of programs solved by the LLM Solver in our online synthesis experiments from $4. Next, we rewrote the set of solved training programs using the generated abstractions to compute the compression ratio: a scalar value in [1.0, oo) that indicates the overall reduction in corpus length afforded by particular library.
Fig. 16 shows the primary results from these experiments. Across all three domains, Stitch achieved compression ratios in the 1.5-3.5x range, with performance generally improving as more solved
REGEX
CLEVR
4.0
4.0
35
3.5
3.5
Congrestion Rahin
3.0
3.9
Comercasion 8,00
3.0
2.5
2.5
2.5
2.0
2.0
2.0
1.5
1.5-
1.5-
1.0
1.0
1.-
0.5
0.5
0.5
Harution
Baration
GPI-4 frandom esammple)
GPT-4 Jelustered ecsmssie))
ST/CCH
Figure 16: Comparison of compression ratios achieved by GPT-4 vs. Stitch during online synthesis. Stitch produces abstractions that achieve 1.5-3.5x compression of the set of solved tasks, with performance generally improving over the course of learning. In contrast, GPT-4 struggles to generate abstractions that achieve mcaningful compressivity.
*As is generally the case when attempting to induce LLMs to perform novel task, this exercise required exploring a theoretically infinite space of possible prompts. Here, our standard is "best effort prompt engineer- ing": we set out to demonstrate positive result and spent a significant amount of time iterating on the prompt format, drawing on techniques developed for other components of I.I.o. Compared to the L.MM Solver prompt (Fig. 6), this task required significantly more prompt engineering effort and yielded only negative results.
45

---

Published as a conference paper at ICLR 2024
Anlly
02
20-
20
25
30
Afty Distribution
Longth Distribution
10-
20-
15
25
30
35
Arty Distribution for LOGO
Length Distribution for LOGO
50-
10-
20-
22
GPii4
Figure 17: Formal characteristies of abstractions produced by GPT-4 Stitch. Left: Comparison of abstraction arity (numher of arguments). Right: Comparison abstraction length (in terms of number of program primitives). Stitch is able to produce longer abstractions that encapsulate more reusable logic, while GPT-4 tends to generate trivial abstractions.
programs become available. contrast, the LLM Compressor struggled to produce abstractions that achieved meaningful compressivity, hovering around the 1.0x baseline. Moreover-ann unlike the LLM Solver-the LLM Compressor had difficulty producing syntactically well-formed expres- sions, with only 19.01% % (998 / 5250) of the generations across the three DSLs representing valid expressions (Tab. 7).
We also evaluated two formal characteristics of the generated abstractions: length and arity (Fig. 17). Length is the number of base DSL primitives used in the abstraction and arity is the number of arguments. We compare the dis- tribution of length and arity among all abstrac- tions generated using Stitch and the LLM Com- pressor. While both methods produce similar arity distributions, Stitch tend to be longer on average (Fig. 17, right). This metric reflects the fact that Stitch produces abstractions that meaningfully capture shared logic, while GPT-4 tended to produce trivial abstractions. Overall, these results led us to decide not to conduct further and more costly online synthesis experiments with the LLM Compressor, these abstractions appeared unlikely to aid in synthesis.
Valid
Generated
Valid %
REGEX CLEVR
561
2250
24.93%
363
1500
24.20%
LOGO
74
1500
4.93%
Overall
998
5250
19.01 %
abstractions produced by
Table 7: Validity of abstractions generated by LLM Compressor.
While claims of the form "GPT-X cannot perform compression" is unfalsifiable (see Footnote 3), these results nevertheless highlight the fact that current L.Ms are more readily-equipped to perform synthesis than compression. Intuitively, the complexity of generating valid abstraction is signif- icantly higher than the equivalent generation task for programs, as it requires reasoning formally about how the proposed abstraction will interact with the entire corpus of programs. These results reinforce the motivation of LILO neurosymbolic framework that uses LLMs for synthesis while delegating refactoring symbolic module that has been engineered to handle this more computa- tionally difficult task.
46

---

Published as a conference paper at ICLR 2024
You are about to undertake task focused on abstraction Learning. The objective is to generate functions derived froe existing to solve spectfic tasks. Here is an exaeple for producing reusable function for a steple nuneric donain.
functions will utilized
Input:
(lanbda (+ 3 ( (+ 4) 2)3)
(lanbda (nap (lambda (+ 3
(8)))) $1))
(lambda (* 2 (+ (* 50 (+ 1)))))
Domain- general example
Observation: ALL the input programs add to the result of nultiplication.
A
Function expression: (lambda (lanbda (+ 3 ( $0 $1))))
Now, Let's rewrite the input to use this function expression: (lambda (lanbda (lanbda (* $1)))) (+ 2)
"readoble =a "muttiply, and_add three", "function_expree expresston": "(Lambda (Lambda (+ (* $1))))",
"description": "Hultiplies the two argunents and adds three to the result."
Here, we are working in domotn-spectfic Longuage that includes the following Library functions:
DSL
regex jeetx_otttto
-> tsubstr
regex_or tsubstr => tsubstr tsubstr
functions
regex_ bigex_concatt/o ::
>>
exapples of solved tasks:
(lanbda (regex_flatee flatten (regex_nes (lambda (regex_if (regex_nates natch 't' 58) (regex_conce) 'a'
Example
'x') sB)) (regex, split empty_stres striitttnnggnmmoe $8))))
(lanbda (regex_ flatten (regex_come cons 'n' (regex_come cons 'a' (regex cdr (regex_spa) split '.' (8))))))
programs
(lanbda (regex_ flatten (regex_na) nap (larbda (regex_1f "rece__natch 'p' $8) (regex_concat
'w') 58)) (regex_splis '.' (S)))))
cadditional exapptes
sampling nethod>
Please write a conpact, reusable function hased on the prograus above. Find patterns in the prograws
nultiple tasks.
propose function.
Only use the functions avoilable to you to the Library provided.
Task
Make the abstraction balanced parentheses.
instruct-
Your response should the following 350N format.
ions
": nose": TOD0, "function expression": 7000, "description". TO00
Figure 18: Anatomy of LLM Compressor prompt. The prompt consists of (A) header demonstrating the abstraction task for general numeric domain, (B) a DSL. description enumerating the available library functions, (C) set of example programs sampled using either random cluster-based sampling (described ahove), and (D) footer specifying constraints and the desired output format. The ISON schema for the L.M Compressor output similar the AutoDoc prompt (A.2) with the addition of function expression field.
47

---

Published as a conference paper at ICLR 2024
Some of the graphical assets that appear this work were generated by the authors via Midjourney, third-party service provider. Subject to the Midjourney Terms of Service for Paid Users, all assets created with the services are owned by the authors to the extent possible under current law. The authors ucknowledge and respect the copyrights and trademarks held by the Walt Disney Company. Any likeness to characters or properties trademarked by Disney is considered Fair Use under US Transformative Use laws, which provide broad protections for commentary, criticism, parody, satire, education, research, and other forms of creative expression.
48


Reviews:
[{"review_id": "AltDr1oWpS", "reviewer": "Reviewer_oPbs", "summary": "LILO is a system for library learning that leverages large language models. It iterates through a series of modules that allow it to automatically discover a collection of interpretable and documented abstraction functions that help solve held-out tasks across three domains: string regexes, turtle graphics, and visual-question answering. First, given the current version of a DSL, LILO asks an LLM to infer programs that solve prompted input tasks (this step is augmented by an enumerative search). Then, an abstraction discovery algorithm (STITCH) is employed to identify and refactor common patterns of code use into abstraction functions that are added to the base DSL to form a new library. These abstractions are then presented to an LLM, so that they can be given interpretable names and a doc-string description. Compared with prior library learning techniques (DreamCoder) LILO is able to solve more held out tasks with its discovered abstractions.", "questions": "While I think the paper does a good job of validating that AutoDoc is really helpful in getting the LLM to be able to employ the discovered abstractions, I’m a bit curious to know more about how mistakes in documentation might affect performance (as a few mistakes from AutoDoc were noted). Would it be possible to compare AutoDoc generated documentation versus “oracle” documentation (e.g. expert provided)? Even if done just once, it could provide some useful insights into how close the AutoDoc module is to human performance, and whether the LLM solver that gets “expert” documentation would be any better than the one generated by AutoDoc.\n\n# Minor comments\n\nWhile I appreciate the goals of the system are to work for 'real-world’ domains, I would consider reframing the introductory statement of the results section, as I wouldn’t consider any of the domains studied in this work to match that description.\n\nI think a bit more effort should be made into clarifying that STITCH is not a contribution of this work – this is clear to a careful reader, but should be made obvious. Additional citations to STITCH in Figure 1 and the respective paragraph in Section 3 would seem appropriate. \n\nIt looks like Table 1 has a minor bolding issue in the CLEVR mean column, bottom half. More generally, I’m unsure if bolding only the highest number is the right thing to do in this table, when the standard deviations have a great deal of overlap in many cases.\n\nMaybe I’m misunderstanding this, but the standard inductive program synthesis problem statement at the beginning of Section 2, doesn’t seem to match the problem setting that LILO uses. Instead of being conditioned on a specification with a set of input/output examples that come from the same program, my understanding is that the LLM is conditioned on task-description/program examples (e.g. the in-context examples), and then is prompted with a single new task-description. Is there a reason for this disconnect?\n\nWhile the performance differences between LAPS and LILO are discussed in A.5, is there a reason that this comparison isn’t put directly into either Table 3 or Table 4?", "limitations": "", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper is well-written and proposes a compelling method for a difficult and important problem. The methodology employed is sound and clearly described, even without a reference implementation much of the system seems reproducible. On the whole, the experimental design is reasonable and comprehensive, modulo a few missing conditions (detailed in the next section). I was pleasantly surprised by the detailed computational efficiency analysis at the end of the appendix, it was a well-formulated and interesting addition to the paper.\n\nIn terms of contribution, the paper situates itself as a complete system that offers an improvement over DreamCoder across a varied collection of tasks; I think the evidence the paper presents on this point is compelling. There are two main insights/observations that support this improvement. (1) Given a task description, LLM’s can usefully solve inductive programming tasks and (2) the success of (1) is dependant on operating over a DSL with “good documentation”, e.g. without semantic names, even otherwise helpful functions can contribute to model obfuscation. However, in some ways the most surprising results from the paper are that, even without library learning, LLMs can solve these domain-specific tasks much better than prior works (e.g. for regex, comparing DreamCoder to and LLM Solver that infers with respect to a base DSL offers a large improvement).\n\nThe paper notes that invoking an LLM at inference time can actually be more computationally efficient than enumerative search, which is an interesting observation. That said, I think the strongest experimental evidence in favor of the proposed method is in the bottom half of Table 1, which shows that LILO produced libraries outperform other libraries when only enumerative search is used. This is a clever, although not perfect, way of evaluating how well-suited each discovered library is for a particular domain.", "weaknesses": "My main concern is that while LILO does offer an improvement over DreamCoder, I’m not convinced the claimed reasons for the improvement are conclusive based on the experimental design. \n\nFor instance, the version of LILO without enumerative search actually does worse than only using LLM solver for all three of the listed domains, even though LILO has access to an abstraction discovery method (i.e. STITCH). So then, is the evidence that LILO w/ search outperforms LLM Solver+search related to LILO’s use of LLMs (to infer programs and document abstractions) or its use of STITCH to identify common patterns of code-use. On this note, the comparisons between the LLM solver+search variant and LILO appear a bit more murky than the narrative reads; based on the listed standard deviation numbers it’s unclear if there are statistically significant differences in any of these cases. \n\nTo better separate out how the contributions of LILO (LLM program induction in the context of iterative library learning, along with auto-documentation of abstractions) affect system performance, I think the following conditions should be considered:\n\n- (A) Base DSL + STITCH\n- (B) LLM Solver+Search+STITCH\n\nCondition (A) would be an ablated version of LILO, where no LLM calls are made. “Wake” would be performed through enumerative search, and STITCH would still be used to generate new libraries. This would be similar to a DreamCoder + STITCH integration, where STITCH replaces DreamCoder’s sleep phase. From my perspective, this ablation condition is critical to supporting the claims of the paper – at present, its possible that the delta improvement between LILO and Dreamcoder is due entirely to LILO’s use of STITCH, and ablating out of the use of LLMs in this manner would provide a definitive answer on this point.\n\n\nCondition (B) would first employ the LLM Solver+Search for a set amount of iterations, and then would run STITCH over the final set of inferred programs to output a new library. This would be important to support the implicit claim of the method that library learning needs to be performed in the intermediate stages of the algorithm. If LILO outperforms this ablation on offline search performance (e.g. bottom half of Table 1), then it would be a strong mark in favor of the method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Et9GduOxzZ", "reviewer": "Reviewer_FkLi", "summary": "The paper introduces a neurosymbolic framework 'LILO' for learning interpretable libraries of reusable code abstractions. \n* A dual-system synthesizer that uses both LLM-guided search and enumerative search.\n* A compression module based on 'STITCH' that extracts common abstractions from synthesized programs.\n* An auto-documentation module that adds human-readable names/descriptions to make abstractions more interpretable.", "questions": "* Please address my concern in the above weakness section.\n* In Figure 10 caption D, the authors mentions LLM output are sampled without clearly specify the filtering/selection standard.  I advise the author can give a more detailed explanation.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "**Originality**:\n* The integration of LLMs and symbolic program compression is a novel approach toward library learning.\n* Propose auto-documentation for improving abstraction interpretability.\n\n**Quality**:\n* Well described architecture.\n* The analysis and experiments are comprehensive.\n* Comparision to multiple baselines on 3 program synthesis benchmarks demonstrate the advantages of the proposed framework.\n\n**Clarity**:\n* The overall framing and individual components of LILO are well motivated.\n\n**Significance**:\n* The proposed 'LILO' provides a generalizeable blueprint for integrating language models with formal program synthesis.", "weaknesses": "* In Table 1, the proposed 'LILO' framework has substantially higher standard deviation than the baseline across three domains. It indicates LILO's performance varies more widely across different runs, suggesting less stability in this field. \n* The dual-system search module combines LLM-guided and enumerative search, yet the tradeoff and relative contributions are not deeply analyzed.\n* The proposed 'LILO' is strongly based on LLM and it mentions using different models like Codex, gpt-3.5-turbo, gpt-4, but did not provide direct comparison of the their performance.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "AA7sPBZ3tJ", "reviewer": "Reviewer_NLqL", "summary": "The paper presented a dual strategy system utilizing LLM and symbolic systems for program synthesis. Unlike conventional programming synthesis models, which implicitly learn the common program fragment (library), the proposed LILO explicitly generates a library with human-readable function names. The code generator is informed with the library and is able to generate potentially more concise program. \n\nThe experimental results show its improvement against the straightforward LLM + search approach and the LLM free baseline, DreamCoder.", "questions": "1. Could the author elaborate on algorithm 1 and Dual-system program search? The relationship between the enumerate search and LLM-guided search is quite unclear. Are they parallel? cascaded? or combined in another manner?\n\n2. What does PCFG stand for? Could the author describe the input-output, architecture, and training of this multi-layer perceptron? Is this model pre-trained? DSL-specific? \n\n3. In the Table 1, only in LOGO, the LILO method significantly outperforms the LLM solver + search. Could the author explain the performance difference among the different DSLs? If the reason is that LLM is not pre-trained on only LOGO, it could be an interesting and promising observation about the generalization capability of both LLM and LILO.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "The work demonstrated a successful combination of LLM and symbolic tools to efficiently generate a library and set of programs given a DSL and program synthesis tasks.", "weaknesses": "As the author also mentioned, the pipeline needs an additional self-verification step for the auto-documentation. The validity and conciseness of the language-guided program synthesis is enforced by input-output pairs and the stitch compression, while the library auto-doc has no verification or feedback loop to update the LLM or other trainable part of the pipeline. \n\nThe application of the method is limited in functional programming with relatively simple DSL. Though it's almost a common limitation of program synthesis models/systems.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "a4xv5lXi0w", "reviewer": "Reviewer_dfJc", "summary": "The paper proposes a neuro-symbolic framework for learning \"code libraries\" for lambda-calculus code.\nThe idea is to iteratively synthesize code using an LLM, compress it using an existing approach (\"Stitch\") and then document it using an LLM.\nBy repeating this approach multiple times, the overall framework learns repetitive \"libraries\" that can be further useful in the next iteration.\n\nThe overall framework, called Lilo, is evaluated on three tasks: CLEVR (visual scene reasoning), REGEX (string editing with regular expressions), and LOGO (graphics composition in the 2D Logo graphics language), and shows improvements over a vanilla LLM and over DreamCoder (Ellis et al., 2021).", "questions": "### Questions\n\n1. What practical problems can the proposed approach be helpful for? Who is expected to use the proposed approach? \n2. Can the task be \"translated\" to Python, and then tested on an LLM?\n3. Can an LLM such as LLaMA be finetuned on the training examples, to better understand their language? Prompting an LLM with a language it was not trained on is a bit unfair.\n\n### Comments\n1. Regarding the AutoDoc module - more than *having* an auto-documentation module, the interesting part to me is that this generated documentation improve the next iteration, when fed to the LLM. That is, the self-improvement part (the fact that the LLM generated doc improves the LLM itself in the next iteration) is the interesting from an ML perspective, to me, while the paper mostly emphasizes the \"existence\" of this module to generate documentation, which is not significantly novel or interesting on its own.\n\n### Summary\nThe main weaknesses of the paper are its lack of practicality, the tasks are quite synthetic, and I believe that an LLM-based baseline can perform better than presented, if given fair chances.\nNonetheless, the paper proposes a simple approach (simpler than DreamCoder, which is good), it is well written, easy to follow, and the ideas are conceptually pleasing, and I thus vote for acceptance.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "1. The idea is interesting, combining both LLMs and traditional program synthesize.\n2. It is refreshing to see tasks and approaches in which using vanilla LLMs still works much worse than a clever approach.", "weaknesses": "1. The tasks are a quite contrived, and it feels like the problem definition is tailored exactly to this kind of solution. All the tasks are synthetic and based on lambda calculus. What practical problems can the proposed approach be helpful for? Who is expected to use the proposed approach? \n2. Evaluation - I am not sure that it is fair to compare that proposed approach to a *prompted* LLM as a baseline when this baseline is prompted with the lambda-calculus language, which it probably was not trained on. Since the task is defined in a domain-specific-language (DSL), a prompted LLM is expected to fail. Can the task be \"translated\" to Python? If the LLM would be allowed to use Python, that would be a more fair comparison. Alternatively, a more fair baseline could be fine-tuning an LLM on the language, rather than just prompting, since the proposed approach also does kind-of training within its compression step. \n3. Novelty - I am not familiar with the directly related work, and I am thus not sure about the novelty: the paper claims that the framework consists of three modules: \n    1. A synthesis module - which is a prompted LLM\n    2. A compression module (\"Stitch\"), which is adopted as is from [Bowers et al., 2023](https://mlb2251.github.io/stitch_jul11.pdf).\n    3. An \"auto-documentation module\" which uses a prompted LLM to document the resulting code pieces, for better interpretability and improvement of the next iteration.\n\n   It seems like steps (1) and (3) are standard code generation using LLM prompting, and the heavy lifting is done by the 2nd step. Since the 2nd step is identical to Bowers et al. (2023), I am not sure how novel is this paper compared to Bowers et al. (2023).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)