HYSYNTH: Context-Free LLM Approximation for Guiding Program Synthesis
Authors: Shraddha Barke
Emmanuel Anaya Gonzalez
Saketh Ram Kasibatla
Taylor Berg-Kirkpatrick
Nadia Polikarpova
Venue: NeurIPS 2024 poster (2024)
Keywords: program synthesis
programming-by-example
domain-specific languages
guided search
large language models
Primary area: natural_language_processing

Abstract: Many structured prediction and reasoning tasks can be framed as program synthesis problems, where the goal is to generate a program in a \emph{domain-specific language} (DSL) that transforms input data into the desired output. Unfortunately, purely neural approaches, such as large language models (LLMs), often fail to produce fully correct programs in unfamiliar DSLs, while purely symbolic methods based on combinatorial search scale poorly to complex problems. Motivated by these limitations, we introduce a hybrid approach, where LLM completions for a given task are used to learn a task-specific, context-free surrogate model, which is then used to guide program synthesis. We evaluate this hybrid approach on three domains, and show that it outperforms both unguided search and direct sampling from LLMs, as well as existing program synthesizers.

HYSYNTH: Context-Free LLM Approximation for Guiding Program Synthesis
Shraddha Barke
Emmanuel Anaya Gonzalez
Saketh Ram Kasibatla UC San Diego San Diego, USA
UC San Diego
UC San Diego San Diego, USA
San Diego, USA
sbarke@ucsd.edt edu
fanayagonzzllezecsdd.ee
akasibatllagccsd.cmm edu
Taylor Berg- Kirkpatrick
Nadia Polikarpova
UC San Diego San Diego, USA
UC San Diego San Diego, USA npo npolikarpova@ucsd.o edu
tbergkkrrkpatrickkucss..c
Abstract
Many structured prediction and reasoning tasks can be framed as program synthesis problems, where the goal is to generate program in a domain-specific language (DSL) that transforms input data into the desired output. Unfortunately, purely neural approaches, such large language models (LLMs), often fail to produce fully correct programs in unfamiliar DSLs, while purely symbolic methods based on combinatorial search scale poorly to complex problems. Motivated by these limitations, we introduce a hybrid approach, where LLM completions for given task are used to learn a task saec-sp,,,fic, context-free surrogate model, which then used to guide program synthesis. We evaluate this hybrid approach on three domains, and show that outperforms both unguided search and direct sampling from LLMs, as well as existing program synthesizers.
Introduction
Large language models (LLMs) demonstrate impressive capabilities in various domains, but they continue to struggle with tasks that require precision-e.g. structured prediction, reasoning, counting. data transformation-wheer direct task examples
prevalent in their training data X 12 23
31
45) As one example, consider the Abstraction and Reasoning Corpus (ARC) 14), which was designed benchmark for human-like structured reasoning. ARC tasks are grid-based puzzles. such as one depicted in Fig. la This puzzle consists of three training examples, which are pairs of input and output grids; the goal is infer the transformation that maps the input to the output, and then apply this transformation to the test grid. The ARC benchmark's 's emphasis on generalization and few-shot learning has rendered challenging to solve with purely machine learning techniques: state-of offte-----hearr generative models like GPT-4 hardly solve more than 10% of the tasks in the dataset when asked predict the test output, even with the help of advanced prompting techniques 25
In fact, the leading entries in the ARC Kaggle competition tackle this task using Programming-by Example (PBE): instead of predicting the output directly, they search for program that captures the transformation occurring in the input-output examples. For example, the transformation in Fig. la might be represented the following program:
if color_of(self) GREY (seleiggborrself, other) size_ (other)) MIN
then update color(color of (f (1)
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Input Tensor:
in [[]5., 2.1,
Input Strings
Outputs
[1., 3.1,
10., -1.111
Output Tensor:
"ww.. www.domain.. com"
"com"
out = 5.1, 11, 11,,1.1,10 1..,
[[2. (12.,2.1, (1,,,
"mail.net" net"
"net"
Natural language description (optional) :):
?
amazon. co.uk
"uk"
"Index into the tensor"
(a) ARC
TENSOR
STRING
Figure 1:
Example problems from the three PBE domains we evaluate HYSYNTH on: grid-based puzzles (ARC), tensor manipulation (TENSOR), and string manipulation (STRING).
This particular program written a domain-specific language (DSL) inspired by the ARGA tool [44]. It consists of single rule of the form if filter then transform, which is applied to each object in the grid simultaneously; the filter holds for focus object self and another object other, then self undergoes the transform. In this case, the rule says that any grey object that has neighbor of the grid's 's minimum size (here, a single pixel) should be colored with the color of that neighbor.
Beyond grid puzzles, PBE is general paradigm for structured reasoning and data transformation tasks: for example, it can help spreadsheet users with systematic string manipulation [20), and help programmers use unfamiliar APIs [17 18
36
Fig. shows example PBE tasks from three domains.
Challenge: Harnessing the Power of LLMs for PBE
How can automatically learn programs
from the input-output examples like those shown in Fig. 1 The traditional program synthesis approach is based on combinatorial search 2 34 35 39], which works well for small programs and restrictive DSLs, but becomes infeasible as the program size and the DSL complexity grow. At the other end of the spectrum, purely neural approaches [I5 42 use a neural model to predict the program from input-output examples; unfortunately, even state-of-ar LLMs like GPT-4o [33 struggle to predict an entire program in an unfamiliar DSL: when we asked GPT-4o generate 10 programs for the running example above, none of them were entirely correct
In the past, the limitations of both program synthesis and neural techniques have motivated hybrid approach, where combinatorial search is guided by a learned probabilistic model ( 24 26] (2 [36 (37.. Existing hybrid techniques, however, tasks, which limits their generalization to new domains. With the advent of LLMs, can we now use single pre-trained model to guide program synthesis across wide range of domains?
domain-specific models trained on datasets of similar PBE
Interestingly, there some tension the hybrid approach between the efficiency the search algorithm and the power of the model: scarch algorithm is efficient when it factorizes the search space (i.e., merges many search states into one), which often makes it incompatible with powerful model that requires lot of context make a prediction. Specifically, used program synthesis techniques is bottom-up search (2] programming algorithm, whose efficiency relies reusing the work of constructing and evaluating subprograms in many different contexts. This essentially precludes using models with unlimited left-to-right context-like LLMs-to guide bottom-up search.
of the most widely 28 36 39], which is a dynamic
[1]
Context-Free LLM Approximation To bridge this gap and harness the power of LLMs to guide bottom-up search, we propose to approximate the LLM's conditional output distribution for a given task with context-free surrogate model. Recent work in NLP (46) has found that Hidden Markov Model (HMM) trained match LLM be used efficient surrogate
Our Solution:
A detailed analysis of GPT-4o's performance on this task is provided in Appendix A

---

LLM-generated programs
Prompt
Large language model (GPT3. Deepseek)
Surrogate Model (learned PCFG model using LLM programs)
I/O Examples Grammar
Candidate program
Bottom-up synthesizer (Enumerates programs order of increasing cost)
Execute Programs (Check If enumerated programs satisfy I/O
Solution
examples)
Figure 2: An overview of the hybrid program synthesis technique that uses context-free LLM approximation. Programs generated by LLM used learn PCFG, which guides bottom-up synthesizer generate programs until solution is found.
in style-controlled language generation. We extend this idea to program synthesis, replacing the HMM with probabilistic context-free grammar (PCFG). The benefits of using a PCFG are twofold: (I) PCFGs are context-free,, which makes them compatible with bottom-up search for PBE [1] 36), and (2) while a context-free model may make a poor approximation to an LLM's full joint, in a PBE setting it is able to reasonably approximate an LLM's conditional distribution for a given prompt. The overview of our approach is shown in Fig.
output programs
Evaluation We implemented this technique in tool HYSYNTH and evaluated it on 299 PBE tasks from three domains: ARC grid-based puzzles [14], tensor manipulation tasks from TFCODER [36]. and string manipulation tasks from the SYGUS benchmark [5] which are inspired by spreadsheet use cases. Example problems from these domains are shown Fig. Our evaluation shows that HYSYNTH outperforms both unguided search and LLMs alone, solving 58% of the tasks overall, compared to 40% for unguided search and 6% for LLMs without search. Our tool also outperforms baseline program synthesizers for these CammannsAAR... TFCODER, and PROBE [Л]] respectively; importantly, in the TENSOR domain, the guidance from the LLM not only speeds up the search, but also frees the from having to explicitly provide any otanstaddrd constants that the solution might use, thereby significantly improving the usability of the tool.
Contributions In summary, this paper makes the following contributions:
1. We propose a hybrid program synthesis approach that integrates LLMs with efficient bottom- up search via task-specific context-free approximation.
2. We implement this approach in tool HYSYNTH and instantiate it on three domains: grid- based puzzles (ARC), tensor manipulation (TENSOR), and string manipulation (STRING). While the latter two domains reuse off- the-shelf bottom-up synthesizers, for ARC implement a custom synthesizer that uses a divide-and-en -nnd--uuue strategy [6] to leverage the structure of the rule-based DSL to further speed up the search.
3. We evaluate HYSYNTH on the three domains and show that it outperforms both the LLM alone and existing baseline synthesizers, which are not guided by LLMs.
Background
2.1 Begraammnng-B-Exaampl
Programming by Example (PBE) 21 is the task of synthesizing programs that satisfy a given set of input-output output examples. To restrict the program space, the programs are typically drawn from domain-specifii language (DSL), which is specified by a context-fre grammar and an evaluation function. This section provides formal definition of these concepts.
Context-Free Grammars A context-free grammar (CFG) is quadruple = E,, R), where A set of non-terminal symbols, is a set terminal symbols, E N denotes the starting
The name stands for "HYbrid SYNTHesis" and pronounced like the flower "hyacinth".

---

Rule
if Filter then Transform
Color
-
color ( Obj)
GREY RED
Filter
Atom I not Atom Atom A Filter
Size
size.. of Obj) MIN
MAX
Atom
Color= Color Size=, Size
I...
Dir
dir.off Obj)
UP
DOWN
Transform
7
update_color( Color) move Dir)
Obj -
self x
Figure 3: A fragment from the context-free grammar of our ARC DSL.
non-terminal, and R. is the set of production rules. An example CFG is shown in Fig. 3 with RNN the set of all rules R E R. whose left-hand side N. A grammar defines a (leftmost) single-step derivation relation on sequences of symbols: sNa = 8,a if N + 3 E R, where & E Σn and o, B (NU ( "E)" The transitive closure of this relation = is called (leftmost) derivation.
We denote
Programs A program P E - is a terminal sequence derivable from some N E NN; we call a program whole if is derivable from S. The set all programs is called the language the grammar g: [(g) {s E Σ" N +' s}. The trace of program tr(P) is the sequence of production rules Ri.... R,, used in its derivation (N + 01 = ... = Qp-1 = P). The size of program P is the length of its trace. The semantics of a program P is defined by the evaluation function [P]: Val* Val, which maps the values of program variables to output value.
Problem Statement A PBE problem is defined by a DSL with a grammar 9 and an evaluation
function [.], as well set input-output examples (i. where Val", E Val. solution to the problem is program P L()) such that v(i, E E, [P] =o
2.2 Assigning Costs to Programs
Weighted Context-free Grammar A weighted context-free grammar (WCFG) Iw is a pair of a CFG 9 and a function we R - R+ that maps each production rule R R positive weight. Given a weighted grammar Gw. we can define the real cost of a program P as the sum of weights of all the productions in its trace: cost.g ()) ER.etr(P) wo (R.).
For the purposes of search, rounds weights up to the nearest integer: wxR)= = [ww [R)] The (discrete) cost of program P is defined as the sum of discrete production weights: cost P) = ERGetr(r) w(R)). Note that because of error accumulation, the discrete cost of a program can differ from its rounded real cost, but the difference can be made arbitrarily small by scaling all the costs by constant factor > 1.
convenient define discrete weight function w u Z+, which
Probabilistic Context-free Grammar popular way assign weights production rules is via a probabilistic context-free grammar (PCFG). A PCFG Gp is pair of a CFG G and a function p: R- [0, 1] that maps each production rule R R to its probability, such that probabilities of all the rules for given non-terminal N E A sum up to one: VN. ERER(N) p(R) = 1. A PCFG defines probability distribution on programs: p IRREE p(R:).
Given PCFG (G, p) we can derive WCFG Gue where wp (R) = log(p (R)); to make sure that all weights are finite and positive, we exclude rules with p(R) = 0 and inline rules with p(R) ) = 1. In this WCFG, the real cost of program related its probability: costs (Ps) log(p(()) ()))
2.3 Bottom-up Search
Bottom-up search is popular search technique in program synthesis (2 11 28, 36 39), which enumerates programs from the DSL in the order of increasing costs until it finds a program that satisfies the given examples. The search is implemented as a dynamic programming algorithm (see Alg. I}, which maintains a program bank B mapping discrete costs to programs of that cost. Starting with an empty bank and current cost level LVL 1, the search iteratively creates all programs of cost 1, 2, 3, and so on; to create complex programs, the algorithm reuses simpler programs already stored in the bank, and combines them using the production rules of the grammar.
For example, consider the CFG in Fig. 3. and assume a uniform weight function w(.) = 1. Then in the first iteration (cost level 1), the algorithm will enumerate programs consisting of single literal or

---

Algorithm Bottom-Up Search Algorithm
Input: Input-output examples &, WCFG G. = w)
Output: A program P consistent with & or failure (L)
I: procedure BOTTOM-UP-SS SETTO--U-SEARCH(O.... SEARCH(Cw,
LVL, B, B.E-- 1,0,0
D. Initialize state of search
3: while true do
4:
for P E NEW-PROGRAMS(G.. LVL, B) do
For all programs of cost LvL Evaluate on inputs from &
5:
EVAL (P)() (1, E E
6:
if (EvAL. E) then
return
fully satisfies &, solution found!
8:
else if (EVAL E E) then
9:
continue
b P is semantically equivalent another program in B D. Add to the bank, indexed by cost
10:
B[LVL] < U (P)
11:
E EVAL.
> Cache evaluation result
12:
LVI. 1vI+1
13: return
b Cost limit reached
14: procedure WwW.PRROGRMMSC... LVL, B)
15:
for R- SoN1s No. NLS do
R is production rule with & -en-telminals for (c....., ax) E I..LVL 1 E LV1 LVI w()) } do For all subexpression costs
17:
for (P (P....., Pa) E B[ca] x... B(c A, +" P. do
D. For all suhexpressions Substitute subexpressions into R's RHS
18:
yield solis1 Pisk
cariable-e.g. self, GREY, UP, etc-and store them [[]]. At cost level 2, it will enumerate unary operators applied to programs stored in [[]]: e.g. color of (self), move (UP), etc. More generally, at cost level LVL, the algorithm considers all available productions, and for each production, enumerates all combinations of arguments whose costs up to LvL
During search, each candidate expression evaluated see if it satisfies the examples (lines 5- 7). Importantly, the search maintains cache of all evaluation results E, and discards the newly constructed program if it observationally equivalent to program already the bank (line 8), iee. it evaluates to the same output for all inputs in the examples. This step is the key to the efficiency of the bottom-up search algorithm: allows the synthesizer factorize the search space by evaluation result, significantly reducing the number of programs explored at each cost level.
The HYSYNTH Approach
A key challenge in program synthesis is the astronomical size of the search space the synthesizer has to explore. For example, to find the program Eq. I the solution to the ARC task from the introduction, bottom-up search with uniform weight function has to enumerate around 450K programs (all programs of size < 16), which takes 4.5 minutes in our experiments.
On the other hand, sampling solutions to this task from an LLM yields programs that are close to the desired solution, even if not quite correct. As show in Appendix components update_colon color, color-of, and is_neighbor in nearly all of its solutions (usually missing some part of the filter or using the wrong color in the transform), and never uses irrelevant components like move or rotate. This suggests that the LLM generally has the right intuition about the components the solution needs to use; our insight to leverage this intuition to guide bottom-up search by assigning lower weights to the components that the LLM uses frequently.
GPT-4o uses relevant
3.1 Guiding Bottom-up Search with Context-Free LLM Approximation
The overview of our approach, HYSYNTH, is shown in Fig. 2 Given a PBE problem consisting of DSL with grammar G and a set of input-output examples &, HYSYNTH proceeds three steps.
Step 1: Sampling Solutions from an LLM HYSYNTH starts by creating an LLM prompt that
contains and E; the prompt can be optionally augmented with in-context examples if they are available for the given DSL. A complete prompt for the ARC running example can be found in Appendix B The L.MM then used sample a set [S.).N of completions; the choice of N trades off computational cost and the faithfulness of the approximation to the true LLM conditional.
5

---

Step 2: Learning a PCFG from LLM Solutions Next, HYSYNTH attempts to parse each comple-
tion S; into program P; using the grammar G. The resulting set of programs {Pr) (where N' < N) is used to learn PCFG 9p via maximum likelihood estimation: p(R) ERER count (R)+t(R))tar [x]] Here count(R ()) is the frequency of rule R in all the derivations of the programs in {P.) and a is smoothing parameter that ensures that every rule has a non-zero probability (typically set to 1).
co
Our experiments show that some models struggle to generate grammatical completions, leading to N' < N. To increase the sampling efficiency in those cases, HYSYNTH implements non-strict mode, where ungrammatical completions S; are not discarded. Instead the tool performs lexical analysis on S, to convert it into a sequence of terminals and approximates the frequency of each production R based on the frequency of its operator terminal, a designated terminal of R, which represents a DSL operator; e.g. count ( (Atom + not Atom) = count(not) 5
Step 3: Guiding Bottom-up Search with PCFG Finally, HYSYNTII uses the PCFG computed in the previous step to derive a weighted grammar Fur as explained in Sec. 2.2, and uses it to initialize the bottom-up search procedure in [lg.. 1| As a result, the search is guided by the insights from the the LLM. For example, the WCFG learned from the GPT-4o completions for the ARC task above gives the relevant transform operator update color weight 2, while all other Transform rules have weight 4; the relevant filter operators color of and is neighbor are similarly result, the search procedure only has to enumerate around 220K programs instead of 450K, achieving a 4x speedup, and solving the motivating example in just one minute with LLM guidance.
As a
3.2 Domain-Specific Instantiations
We now describe how the HYSYNTH approach is instantiated in three different domains: ARC grid puzzles, TENSOR manipulations, and STRING manipulations.
ARC Domain An example task from this domain is shown in Fig. aal has been used as a running example throughout this paper. There is no established DSL for ARC, and arguably, DSL design is the biggest challenge when attempting to solve ARC using a PBE approach, since it is hard to capture the wide variety of tasks in this domain. Our DSL is inspired by the rule-based language of ARGA 44), which we modified slightly to make it more compositional.
program in our DSL is a sequence of rules of the form if filter then transform. rule refers the current object self, which is modified by the transform if the filter is satisfied in the current state of the grid. The rule can also refer to other objects in the grid, such as other in [Eq. 1] This program is well-defined because its filter uniquely identifies the object other; if the filter is too weak to uniquely determine the effect of the transform, the program's 's output is considered undefined. The full grammar of our DSL can be found in Appendix H
we further optimize our synthesizer using a divide-and-conquee strategy inspired by [6], searching for filters and transforms separately. Specifically, HYSYNTH-ARC first searches for transforms that are correct on some objects in the grid; once it has found set of transforms that collectively describe all grid objects, it searches for filters that distinguish between the subsets of objects changed by each transform.
Instead of searching for complete program using Alg.
Consider once again our running example. When the transform synthesizer enumerates the expression update_color(cee color(color (other)), it detects that this transform works for all grey objects, because for each grey object self there exists a corresponding object other whose color can be copied. Now the goal of filter synthesis is to find boolean expression that holds exactly for those pairs of objects (self, other) that make the transform work. See Appendix K for more details about this algorithm.
TENSOR Domain This domain originates from the TFCODER synthesizer (36), which takes as input examples of a tensor transformation (with an optional natural language description) and synthesizes TensorFlow program that performs the transformation. An example task from this domain is shown in Fig. 1b] whose solution is: tf..gaterr...e nd (in1, tf tt.stack( (an,ck(inn,, in3), axiş=-1)). The main challenge, however, is that the TensorFlow grammar is very large (see Apppendix G), and most importantly, the programs are allowed to use an unbounded set of constants. The original TFCODER
TTypccally the operator terminal uniquely identifies R, but when this is not the case, we can normalize cR) by the number of rules in R that produce this terminal.

---

synthesizer requires the user to provide any non-standard constants that a task might require, and, according to their paper, this is the main barrier to the usability of their tool.
For program synthesis in this domain we use the TFCODER synthesizer off the shelf. TFCODER performs weighted bottom-up search, using combination of hand-tuned weights and weights derived by two custom-traine neural models. HYSYNTHH-ENSON replaces these weights entirely with weights computed by sampling from an LLM. Importantly, our version of the tool does not require the user to provide any constants; instead we extract constants from the LLM completions, whereby significantly reducing the burden on the user.
STRING Domain Our third domain involves string manipulation tasks from the SYGUS competi- tion [4. which are inspired by spreadsheet use cases. An example task, which requires extracting the top-level domain name from a URI., is shown in Fig. 1cl In this domain we use the PROBE [I1] synthesizer off the shelf. PROBE performs weighted bottom-up search, starting with a uniform grammar and updating the weights on the fly; HYSyNTH-STRR STRING instead initializes PROBE'S search with weights derived from an LLM, and disables the weight updates during search.
4 Experiments and Results
4.1 Experimental Setup
We evaluate HYSYNTH 299 PBE tasks from three different domains: ARC (160 tasks), STRING
(70 tasks) and TENSOR (69 tasks).
ARC Benchmark The 160 ARC tasks are taken from the testing set of ARGA 44
This object-
centric subset of the full ARC corpus is known as OBJECT-ARC ARC, and has been used to evaluate other ARC solvers (27) ARC specifications consist of 2-7 input-output training grids and testing grid. Correctness is based on whether the generated solution produces the correct output on the testing grid. Our ARC DSL has a total of 20 operations and 50 constants and variables across all types.
TENSOR Benchmark The 69 TENSOR tasks taken from TFCODER focus on tensor manipulation. 49 of them are sourced from StackOverflow inquiries, and 20 are from real-world scenarios faced by TensorFlow users at Google. The overall benchmark suite consists of 72 tasks. We use three of these tasks as in-context examples and evaluate the rest. The grammar for this domain consists of 134 Tensorflow operations, primitives like e, 1, -1, True and other task-specific constants.
STRING Benchmark The 70 STRING tasks are taken from testing set of PROBE, which is derived from the SYGUS benchmark (4). The number of examples ranges from 2 to 400. The original SYGUS benchmark have custom grammars for each task, but we use union of all the grammars to make the search more challenging: the union grammar has 16 operations and 59 constants.
Configurations Our main HYSYNTH configuration uses GPT40 as the LLM, with 100 samples per task to learn PCFG in non-strict mode (i.e. syntactically invalid completions are included in the PCFG learning process, as explained in Seec. 3. For each domain, we compare the performance of HYSYNTH with baseline synthesizer for that domain (ARG. PROBE, and TFCODER), as well as three ablations: (I) no search, i.e. using the 100 samples from the LLM directly, (2) unguided search, i.e. running the same synthesizer but with uniform weighted grammar, and (3) binary surrogate, running the synthesizer but with a binary PCFG, i.e. a CFG that includes the components present in the LLM samples with equal probabilities, and excludes all other components completely. We also analyze the performance of HYSYNTH with different number of samples used to learn the PCFG (10, 20, and 50), with other LLMs (GPT3.5 and DEEPSEEK (22)). D. as well as in strict mode (which discards syntactically invalid LLM completions). The timeout is set to 10 minutes for all experiments and includes the search time and time to sample L.LM completions (and compute PCFG). The average time to sample 100 solutions from GPT40 is 4 seconds, 12 seconds and 20 seconds per task for the STRING, ARC and TENSOR domains, respectively.
4.2 Results
How does HYSYNTH compare to baselines and ablations? We compare the time to solution for the main HYSYNTH configuration, baseline synthesizers, and the three ablations; the results
At the time of writing, ARGA is no longer state of the art on the OBJECT- ARC dataset; we explain in Sec. 5 why the comparison with ARGA is still relevant.
7

---

Number Problems Against
Problems Solved Against Time
:00
lotal lasks
Cumulatius Number of Probleme Solves
$20
Total Tasks
140
HySynthaARCC
PysyythhSTRRIN Birory
of Problemic
Binery
220
ARGA
Unguided
Unguided
100
GP140
GPT4p
40
(a) HIYSYNTH-ARC results with GPT40
(b) HYSYNTH STRING results with GPT40
Number Problems Solved
Cumdative Number Problems Salvee
Domain/Model
% Valid completions
TENSOR-GPT40 99.9%
HySSYnthTENSOOR
TENSOR-DEEPSHEE
92.8%
Binary
TFCoder
STRING-GPT40
37.5%
10-
Unguided
STRING-DREPSEEKK
0%
0
202
683
ARC-GPT40
78.4%
Time (Secandis)
(c) HYSYNTH-TENSEE results with GPT40
(d) Percentage of syntactically valid completions
Figure 4: (a,b.)) Number of benchmarks solved by HYSYNTH as function of time for the ARC, TENSOR, and STRING domains; timeout 10 min. (d) Percentage of syntactically valid completions per domain.
for the three domains are shown in Fig. 4a Fig. 4b and Fig. 4c Overall, HYSYNTH consistently outperforms both the baseline synthesizers and ablations, solving more tasks across all domains.
In more detail, direct LLM sampling performs very poorly on all domains, solving between and 14 tasks; this confirms hypothesis that LLMs struggle PBE tasks in domain-specift languages, which are not prevalent in their training data. Interestingly, despite not being able to solve any TeNSoR tasks by itself, GPT40 provides excellent guidance for HYSYNTH solve 96% of the total benchmark! On the other hand, synthesis guided by a binary surrogate model performs worse than HYSYNTH (and even unguided search in case of ARC and TENSOR) since the search excludes essential components from the grammar.
that domain, helping
In STRING and TENSOR domains, the baseline synthesizers predictably do better than unguided search, since both use the same search implementation, but with different weights. On ARC, however, custom synthesizer outperforms f even without LLM guidance; this speaks to the efficiency of the bottom-up search and the divide-and-com con-uue strategy we use, which are results of years of research in the program synthesis community.
To better understand how the number of samples affects the quality of PCFG guidance, we vary the number of GPT40 programs used in number tasks solved over time. The results are shown in Fig. 5a Fig. 5b) and Fig. 5c As expected, larger sample sizes generally lead to better performance, but the difference is minimal: in ARC and TENSOR, the difference between the best and worst performing versions of HYSYNTH is only 2 problems each, while in STRING, HYS Y solves fewer problems with 10 samples than with 100. Despite these differences. all versions of HYSYNTH still outperform the bascline and unguided search. This suggests that fewer samples are sufficient to effectively train a robust surrogate model, thereby optimizing costs.
How many samples are needed to learn PCFG?
PCFG learning
10, 20, 50, 100, and once again measure
4
report 57 tasks for ARGA but could only reproduce hardware with 10 minute timeout.

---

Number Problems Against
Against
200
trysynth ARC-100
Cumulativn Number of Problemn Solved
120
HySSynhh-STWWNG--- HySynch STRING-50 STRING
HySymth-ARC-5a
HySSythhAACC
MySSymthAARC-10
MySytnt--STINN--10
Number of Benchmarks
60
(Second()
(a) HYSYNTH-ARE with varied sample sizes
(b) HYSYNTH- STRING with varied sample sizes
Number of Problems Solved Against Time
Number Problems Solved
80
hySynth-ARK (NonStrict)
00-
HySyythhAASS (Strict)
Problems
Problems
70
60
60.
20-
50-
20
HySynth Senytth-ENNOR-1111 100
Cumuisatvv
NySyyth-TENNSOR-
10
HySymth-TEN5OR.22
HySSytth-ENNSO-R1 TENSOR-10
120
160
(Seconds)
(Seconds)
(c) HYSYNTH-TENSOR with varied sample sizes
(d) HYSYNTH-ARC with strict and non-strict modes
Figure 5: HYŠYNTH-ARC, HYSyNTH-TENSOR and HYSYNTH-STRING results guided by a PCFG learned from different number of GPT40 samples (n=10, 20, 50, 100).
Do our results generalize other models? To answer this question, we repeat our experiments on STRING and TENSOR domains with GPT3.5 and the open-source model deepseek-codet coder-33b--eoooo instruct (DREPSEEK) (22). The results with these models are detailed in Fig. in Appendix C and they corroborate the pattern observed with GpT40, where the guided versions outperform the baseline, unguided search, and direct sampling from the LLM.
How important is non-strict mode? Fig. 4d shows the percentage of syntactically valid comple- tions generated by GPr40 and DEEPSEEK (where applicable). You can see that while on TENSOR almost all completions are valid, this percentage falls to 78.4 78.4% for ARC and 37.5% for STRING; this is surprising, given that the former are TensorFlow programs, which the model has seen during training, while the latter two are custom DSLss In the STRING benchmark, the grammar is very restricted (e.g. only numeric constants allowed are 0-9), and the LLM has trouble adhering to this restricted grammar. But even if we were to relax the definition of syntactic validity, LLM solutions would achieve a syntactic validity of only 47%. Hence our non-strict mode proves especially helpful for low-resource domains, where otherwise completions. the same time, we find that given the same number of completions learn learnfrom PCFGs learned in non-strict mode are just effective as those learned in strict mode: shown in Fig. 5d HYSYNTH-ARE with the guidance from 100 GPT40 completions solves 58 tasks in either mode (with the difference that strict mode has sample more completions to get 100 valid ones).
would have to discard large proportion of
4.3 Limitations
The main limitation of our hybrid approach wrt. purely neural approaches is that requires imple- menting a synthesizer for each DSL of interest: although we have shown that the same bottom-up search can be used across different domains, some implementation effort still required. other hand, compared to purely symbolic approaches, our method requires sampling from an LLM, which is costly; additionally, the guidance provided by our approach only as good as the LLM'' completions: if they contain many irrelevant operators, our guided search can be slower than unguided

---

search. Finally, our experiments are subject to the usual threat that the LLMs might have seen our benchmarks in their training data; we do not consider it a major issue, however, given that our main result is the superior performance of guided search relative to using LLMs without search.
5 Related Work
Guiding Program Synthesis with Probabilistic Models The traditional approach to program synthesis is based on combinatorial search 77. augmented with pruning techniques based on program semantics (2 6 39. To further speed up the search, researchers have proposed guiding the search with learned probabilistic model. Most approaches to guided search use special-purpose pprpose models that have to be trained on domain-specific corpus of programs [26] or PBE tasks [9 32, 377. Although some of these models can trained on synthetic data, the training process is still expensive and requires manual tuning, which makes it hard to apply these techniques to new domains.
With the advent of pretrained Large Language Models (LLMs), it seems only natural use them to guide search-based program synthesis, thus alleviating the need for domain-specific training data. We are only aware of one other attempt to do this: concurrent work by Li et al. (29], which also extracts a PCFG from the LLM's samples, similarly to HYSYNTH. An important difference is that they use the PCFG to guide top-down A search, while we use to guide ppp search, which is known to be more efficient (they also evaluate their tool on synthesis from logical formulas as opposed to PBE).
Solving the Abstraction and Reasoning Corpus All state-of-the-art solvers for this benchmark Xu et al. [44] proposed the DSL we extend in our approach, and the OBJECT-ARC subset we evaluate on. Lei et al.
have relied on carefully curated DSLS for ARC 1 19 27 43
27 embed their DSL as subset of PDDL and use a Generalized Planning (GP) algorithm as their search component. They have the current best performance on OBJECT-ARC: however they encode more in the form of preconditions and per-abstraction restrictions on filters and transforms, to make GP viable. Our approach does not require this additional information.
[O] use DreamCoder [16], to perform execution-guie -guided search over DSL for grid manipulations, however they only provide proof-of-coneee evaluations. [8 41 also use an LLM to generate code given the spec of the task. Both of these approaches interact with the model across several rounds, while our technique uses the suggestions from the LLM only as a starting point. Our technique also performs a complete search guided by the LLM distribution, enabled by the structure of our DSL, whereas previous approaches only consider code directly generated by the LLM.
Conclusion and Future Work
Our approach introduces a robust technique for using both valid and invalid completions from an L.M to learn a surrogate model. By incorporating ungrammatical completions, we can extract useful insights that would otherwise be discarded. Overall, we provide an alternative to the conventional strategy of large-scale sampling from LLMs, proposing more effective use of the available comple- tions to guide the search process. An interesting future direction would be to guide search with more expressive context-dependent surrogate model.
References
[1] 2020. Are kaggle competition leaderboard Accessed: 2024-05-19.
[2] Aws Albarghouthi, Sumit Gulwani, and Zachary Kincaid. 2013. Recursive program synthesis. In International Conference on Computer Aided Verification, pages 934 950.. Springer.
[3] Simon Alford, Anshula Gandhi, Akshay Rangamani, Andrzej Banburski, Tony Wang. Sylee Dandekar, John Chin, Tomaso Poggio, and Peter Chin. 2022. Neural-guided bidirectional program search for abstraction and reasoning. In Complex Networks Their Applications X: Volume I, Proceedings of the Tenth International Conference on Complex Networks and Their Applications COMPLEX NETWORKS 2021 10, pages 657-668. Springer.
[4] Rajeev Alur, Rastislav Bodík, Garvit Juniwal, Milo M. K. Martin, Mukund Raghothaman, Sanjit A. Seshia, Rishabh Singh, Armando Lolar-Lezama, Emina Torlak, and Abhishek Udupa.
10

---

2013. Syntax-guided synthesis. In Formal Methods in Computer-Aided Design, FMCAD 2013, pages 1-8.
[5] Rajeev Alur, Dana Fisman, Rishabh Singh, and Armando Solar-Lezama. 2017. Sygus-comp 2017: Results and analysis. arXiv preprint arXiv: 1438.
[6] Rajeev Alur, Arjun Radhakrishna, and Abhishek Udupa. 2017. Scaling enumerative program synthesis via divide and conquer. In International Conference on Tools and Algorithms for the Construction and Analysis of Systems, pages 319-336. Springer.
[7] Rajeev Alur, Rishabh Singh, Dana Fisman, and Armando Solar-Lezama. 2018. program synthesis. Communications of the ACM, 61(12):84-93
[8] Xuefeng Bai, Jialong Wu, Yulong Chen, Zhongqing Wang, and Yue Zhang. 2023, Constituency parsing using llms. arXiv preprint arXiv:2310.1946.
[9] Matej Balog, Alexander L Gaunt, Mare Brockschmidt, Sebastian Nowozin, and Daniel Tarlow. 2016. Deepcoder: Learning write programs. arXiv preprint arXiv:1611.01989
[10] Andrzej Banburski, Anshula Gandhi, Simon Alford, Sylee Dandekar, Sang Chin, and tomaso a poggio. 2020. Dreaming with ARC In Learning Meets Combinatorial Algorithms at NeurIPS2020.
[11] Shraddha Barke, Hila Peleg, and Nadia Polikarpova. 2020. Just-in-time learning for bottom-up enumerative synthesis. Proceedings of the ACM on Programming Languages, 4(00PSLA)1- 29.
[12] Lukas Berglund, Meg Tong, Max Kaufmann, Mikita Balesni, Asa Cooper Stickland, Tomasz Korbak, and Owain Evans. 2023. The reversal curse: Lims trained on" a is b" fail to learn" b is a". arXiv preprint arXiv:2309.12 12288.
[13] Natasha Butt, Blazej Manczak, Auke Wiggers, Corrado Rainone, David W Zhang, Michaël Defferrard, and Taco Cohen. 2023. Codeit: Abstract reasoning with iterative policy-guided program synthesis.
[14] François Chollet. 2019. On the measure of intelligence. arXiv preprint arXiv: 191.01991
[15] Jacob Devlin, Jonathan Uesato. Surya Bhupatiraju, Rishabh Singh, Abdel-rahman Mohamed. and Pushmeet Kohli. 2017. Robustfill: Neural program learning under noisy i/o. In International conference on machine learning, pages 990-998. PMLR.
[16] Kevin Ellis, Catherine Wong, Maxwell Nye, Mathias Sable-Meyer, Lue Cary, Lucas Morales, Luke Hewitt, Armando Lolar-Lezama, and Joshua B Tenenbaum. 2020. Dreamcoder: Growing generalizable, interpretable knowledge with wake-sleep bayesian program learning. arXiv preprint arXiv:2006.08381
[17] Yu Feng, Ruben Martins, Osbert Bastani, and Isil Dillig. 2018. Program synthesis using conflict- driven learning In Proceedings of the 39th ACM SIGPLAN Conference Programming Language Design and Implementation, PLDI 2018, pages 420-435, New York, NY, USA. Association for Computing Machinery.
[18) Yu Feng, Ruben Martins, Yuepeng Wang, Isil Dillig, and Thomas W. Reps. 2017. Component- based synthesis for complex apis. In POPL.
[19] Raphael Fischer, Matthias Jakobs, Sascha Mücke, and Katharina Morik. 2020. Solving abstract reasoning tasks with grammatical evolution. In LWDA, pages 6-10.
[20] Sumit Gulwani. 2011. Automating string processing in spreadsheets using input-output exam- ples. ACM Sigplan Notices, 46(1):317-330
[21] Sumit Gulwani. 2016. Programming by examples (and its applications in data wrangling). In Javier Esparza, Orna Grumberg, and Salomon Sickert, editors, Verification and Synthesis of Correct and Secure Systems. IOS Press.

---

[22] Daya Guo, Qihao Zhu, Dejian Yang, Zhenda Xie, Kai Dong, Wentao Zhang, Guanting Chen, Xiao Bi, Wu, YK Li, et al. 2024. Deepseek-coder. When the large language model meets programming-the rise of code intelligence. arXiv preprint arXiv:2401. 0ww::2401.144999 14/96.
[23] Martin Josifoski, Marija Sakota, Maxime Peyrard, and Robert West. 2023. Exploiting asymmetry for synthetic training data generation: Synthie and the case of information extraction. arXiv preprint arXiv:2333.044 04.......
[24] Ashwin Kalyan, Abhishek Mohta, Oleksandr Polozov, Dhruv Batra, Prateek Jain, and Sumit Gulwani. 2018. Neural-ge gurded deductive search for real-time program synthesis from examples. arXiv preprint 11X4v:1804.01 186.
[25] Seungpil Lee, Woochang Sim, Donghyeon Shin, Sanha Hwang, Wongyu Seo, Jiwon Park, Seokki Lee, Sejin Kim, and Sundong Kim. 2024. Reasonnng abilities of large language models; In-depth analysis on the abstraction and reasoning corpus
[26] Woosuk Lee, Kihong Hco, Rajeev Alur, and Mayur Naik. 2018. Accelerating search-based program synthesis using learned probabilistic models. ACM SIGPLAN Notices, 53(4):436-449
[27] Chao Lei, Nir Lipovetzky, and Krista A. Ehinger. 2024. Generalized planning for the abstraction) and reasoning corpus
[28] Xiang Li, Xiangyu Zhou, Rui Dong, Yihong Zhang, and Xinyu Wang. 2024. Efficient bottom-up synthesis for programs with local variables) Proc. ACM Program. Lang., 8(POLL).
[29]
Yixuan Li. Julian Parsert, and Elizabeth Polgreen. 2024. Guiding enumerative program synthesis with large language models
[30] John McCarthy, 1960. Recursive functions of symbolic expressions and their computation by machine, part Commun. ACM, 184-1988
[31] R Thomas McCoy, Shunyu Yao, Dan Friedman, Matthew Hardy, and Thomas L Griffiths. 2023. Embers of autoregression: Understanding large language models through the problem they are trained solve. arXiv preprint arXiv:2309.138 13638.
[32] Augustus Odena, Kensen Shi, David Bieber, Rishabh Singh, Charles Sutton, and Hanjun Dai. 2020. Bustle: bottom-up program synthesis through sarming-guided exploration. arXiv preprint arXiv:2007.14330 14381.
[33] OpenAl. 2024. Hello gpt-4.0 Accessed: 2024-05-19.
[34] Peter-Michael Osera and Steve Zdancewic. 2015. Tyge-and-example-ddireeed program synthesis. ACM SIGPLAN Notices, 5066):619-630
[35] Andrew Reynolds, Haniel Barbosa, Andres Nötzli, Clark Barrett, and Cesare Tinelli. 2019. eve 4 sy: smart and fast term enumeration for syntax-guided synthesis. In International Conference on Computer Aided Verification, pages 74-83. Springer.
[36] Kensen Shi, David Bieber, and Rishabh Singh. 2022. Tf-coder: Program synthesis for tensor manipulations ACM Trans. Program. Lang. Syst., 44(2).
[37] Kensen Shi, Hanjun Dai, Kevin Ellis, and Charles Sutton. 2022. Crossheam: Learning to search in bottom-up program synthesis. arXiv preprint arXiv:2203. 10452.
[38] John Chong Min Tan and Mehul Motani. 2023. Large language model (1lm) as system of multiple expert agents: An approach to solve the abstraction and reasoning corpus (arc) challenge. arXiv preprint arXiv:2310.05146.
[39] Abhishek Udupa, Arun Raghavan, Jyotirmoy V Deshmukh, Sela Mador-Haim Milo MK Martin, and Rajeev Alur. 2013. Transit: specifying protocols with concolic snippets. ACM SIGPLAN Notices, 2876)26..
[40] Shubham Ugare, Tarun Suresh, Hangoo Kang, Sasa Misailovie, and Gagandeep Singh. 2024. Improving Ilm code generation with grammar augmentation. arXiv preprint arX1v:240..01632.
12

---

[41] Ruocheng Wang, Eric Zelikman, Gabriel Poesia, Yewen Pu, Nick Haber, and Noah D Good- man. 2023. Hypothesis search: Inductive reasoning with language models. arXiv preprint arXiv:2309.05660.
[42] Yeming Wen, Pengcheng Yin, Kensen Shi, Henryk Michalewski. Swarat Chaudhuri, and Alex Polozov. 2024. Grounding data science code generation with input-output specifications
[43] Johan Sokrates Wind, 2020. Are kaggle competition, 1st place
Accessed: 2024-05-19.
[44] Yudong Xu, Elias B Khalil, and Scott Sanner. 2023. Graphs, constraints, and search for the abstraction and reasoning corpus. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 4115-4122.
[45] Yudong Xu, Wenhao Li, Pashootan Vaezipoor, Scott Sanner, and Elias B Khalil. 2023. Lims and the abstraction and reasoning corpus: Successes, failures, and the importance of object-based representations. arXiv preprint arXiv:2305. 2..v::2305//334.
[46] Honghua Zhang, Meihua Dang, Nanyun Peng, and Guy Van den Broeck. 2023. Tractable control for autoregressive language generation. International Conference on Machine Learning, pages 11932-40944 PMLR.
13

---

// Solution 1, occurs 6 times
if color_of(self) = GREY A is other)
then podate.colorlcooor..fccccee
// Solution 2,
time
if is neighbor(self, other) A color of (fther) = GREY then update color(calor of (other))
// Solution 3, occurs time if color_of(self)) = GREY then
// Solution 4, occurs time
if not (sel)) GREY) A (s other) A of = GREY then update (FUCH(FU
// Solution 5, occurs time
if dize_of(selt = then (REer((DD)
if (self) = color_o((self) = GREY then
if size_of(self) A color_of(selt) BLUE then color (ORANGE ;
if ofze_f = color_of(self) = YELLOW then
Figure 6: Ten samples from GPT40 for the motivating example in Fig. la
A GPT40 Solutions for the Motivating Example
Recall the motivating example in Fig. la where the task is update the color of the grey objects to the color of their Longle-pxell neighbor. As reminder, the smallest correct solution to this task consists of the following rule:
if color_of(self)) GREY A is is.geig x) A size of MIN then update wow.o(color.ooooooooo (x))
Fig. 6/sows the programs we ohtained by deduplicating 10 samples from GPT4o for this task. The syntax of the solutions is slightly modified for readability; implementation uses LISP-style s-expression syntax 30 to simplify parsing.
As you can see, the most frequent solution is almost correct, except that it does not constrain the neighbor other to be of size 1; this leads to the constraint being ambiguous (since every grey object has multiple neighbors of different colors), in which case the program semantics is considered undefined. That said, you can observe that the model consistently uses relevant components, such color of, is neighbor, and update color, which enables to extract useful PCFG from these solutions.
When we increased the sample size to 125, GPT4o was able to produce one correct solution (which slightly larger than the minimal solution above):
if color_of(setf (selff GREY A is isggngggborsse... other) A not (color_of GREY) then coreeeooooolccoooo.oooooteee
14

---

You assistant chatbot with human- like perception, reasoning and learning capabilities. You can solve tasks concisely, efficiently, and moreover, correctly. Let's engage in perception and logic-based tasks.
You only output source code.
No explanations or any other text.
Figure 7: System prompt for ARC domain.
B
LLM Prompt for the ARC Grammar
B.1
System Prompt
The system prompt given to the LLM for ARC domain is shown in Pig.
B.2
User Prompt
The full user prompt for the ARC domain is shown in Fig. It contains the domain-specific language, four in-context examples and the query for the test task.
15

---

are an efficient assistant logical reasoning and code generation.
You will help me solve visual perception and reasoning task. I will first provide you with the definition of a Domain Specific Language you will use + for writing solution for the task.
I will then present you with the description of the task that you will be tested in. You will then respond to the queries make regarding the solution of the task.
This is the definition of the DSL you will to solve the task. It is given as a context-free grammar in the EBNF format used by the Lark parser generator, with some informative comments about the semantics. You will return a string that is parseable by the 'program' non-terminal of the grammar.
library: "(" program* ")"
// Rules are executed one after another, order they appear. // There could be no rules, in which case the program does nothing. program: "(" "do" rule. ")"
DSL IMPLEMENTATION IN LARK >>>>>>>>
Now we continue with the visual perception and reasoning task.
The input for the task is small number of pairs of grids of characters. The value of each of the cells of the grids are the colors defined in the DSL, so we can
4 think of grids images.
Each pair of images correspond to an output example for an unknown program P. For each pair, the program is evaluated the image grid and operates the objects
+ that appear in it.
The output of the program is then the output image. The objects in the images are easy and natural to identify for humans, so there is no need define them explicitly.
However you are able to abstract them correctly, and the DSL is interpreted with the same correct abstraction.
I will show you some demonstration tasks along with the output you would expected + to produce for each of them.
## DEMONSTRATION TASK 1
### INPUT
INPUT
GRID:
0 O 0
0
0
0
0 R
0
R R
O O O
O R R
O R R O
R
Figure 8: User prompt for ARC domain.
16

---

OUTPUT GRID:
0 0
Y
O Y
0
0 Y
ENCODING OF EXAMPLE PAIR 2 AND 3 OF DEMO TASK D
#*# EXPECTED OUTPUT
"nl description": "Recolor all objects to color Y", "code": << EXPECTED CODE DSL >>>
MORE DEMONSTRATION TASKS (4 IN TOTAL) >>>
Now follows task you will be evaluated
Output the solution as JSON object, which should contain both a natural language description of the solution and the solution written in the DSL. The code should be parseable by the DSL grammar.
The JSON must have the following structure:
"nl description" "TO. BE FILLED", "code": "O__EEFILLLE"
## TEST TASK
PAIR
INPUT GRID:
O O
R
O 0
0
O O
O 0
0 O O O
X X
O O
X
0 X X O
X
0 X X O
x
X
X X O O 0
0 X X 0
0
0 x x 0
0
X
0 X X 0
0 0 O 0
X X
OUTPUT GRID:
O O R O O F
0000000000
FOOOFFFFRR
OOOOF
O R R F F O
O
R
O R R O
O
O
R
O R R O
O O
REST OF THE I/O EXAMPLES OF TEST TASK
17

---

C Experimental results with LLMs DEEPSEEK and GPT3.5
Number Against
Number
Against
Cumulative Number of Problems Solved
Probe
Hy5ynth STRING
Cumulative Number of Problems Solved
Frobe
MySyrthh 51 NNNG 100
Unguided
SySth Sesyytt--STRNN-SSSS STRING-50
Ungulded
HySyythhSTaam RIG-50
DeepSeak
HySynth- Syyytt--TRIIG-200
HySSyshhSTaae RTG--20
HySyith STRNN-10
HySynth STRING-10
(a) HYS results with DEEPSEEK
(b) HYSYNTH-STRING results GPT3.5
Number of Problems Solved Againit Time
Number of Problems Solved Against Time
Cumuuctve Numbar of Probloms Solved
Cumuustive Number of Probt Solved
60
60
PWSymt-TENNSR-UUE 1000
HySynth TENSOR
HySymtl-TENSON-22
HySymB-TENSORLL
20
TFCoder
Ungudded
TENSOR
10
GPT35
100
200
300
4.00
500
603
1.00
200
300
600
500
600
Time
Time (s)
(c) HYSYNTH-TENSOR results with DEEPSEEK
(d) HISSYNTH-TENSON results with GPT3.5
Figure HYS STRRING-STRING HYS SYNTH TENSOR TENSSR evaluation results DEEPSEEK and GPT3.5.
18

---

You coding assistant. Be precise and terse.
You will be provided list of Lonsorflow operators, a task description, and some input/output examples.
Your task is to generate the body of python function that will transform the input to the output. Only use the operators provided in the list.
Your answer should
short possible while still being correct.
Make sure to only generate python code.
Figure 10: System prompt for TENSOR domain.
(TENSORFLOW OPERATORS]
appendix E >>>>
ITASK DESCRIPTION]
index into the tensor
[INPUTS]
II 5. 2.] I 1. 3.1
[ 0. -1.11
[OUTPUTS]
[[[ 5.]
[1. 1.]
0. 0.1]
2.1
3. 3.1
[-1. -1.11]
[PROGRAM]
def tran)))rminnl):
Figure 11: User prompt for TENSOR domain
D LLM Prompt for the TENSOR Grammar
The system and user prompt for TENSOR domain are in Fig. 10 and Fig. 11
19

---

You coding assistant. precise and terse.
You will be given a SyGus grammar, a natural language specification, and a set of input- output examples.
Your task is to complete the provided function definition with an implementation that is correct according to the grammar, specification, examples. Your answer should be as short as possible while still being correct. Make that your is valid s-expression.
Figure 12: System prompt for STRING domain
[GRAMMAR]
(synth-fun ((arg String)) String ((Start String (ntString)) (ntString String ( -arg_0 "BRD" "DRS" "LDS" "Branding" "Direct Response" "Leads" "=" "/" "in "g" "microsoft" "windows" "apple" "mac" "1" "2" "3" "4" "5" "6" "7" "8" "Q" "," "<" ">" "/n" "s" "b" "apple" "bananas" "strawberries" "oranges" "LLC" "Inc" "Corporation" "Enterprises" "Company" "(" ")" "+" "name" "," (str.++
ntString ntString) (str.replace ntString ntString ntString) (str.at ntString ntInt) tont.to.str ntint) (ite ntBool ntString ntString) (str.substr ntString
ntInt ntint))) (ntInt Int (-1 1 2 3 4
10000 -1 (+ ntInt ntInt) (-
ntInt ntInt) (str.len len ntString) istr.to.img int ntString) (ite ntBool ntInt ntInt). (
str.indexof ntString ntString ntInt))) (ntBool Bool (true false ntInt ntInt)
(str.prefixof ntString ntString) (str.suffixof ntString ntString) (str.contains
ntString ntString)))))
[NATURAL LANGUAGE SPECIFICATION]
http::///eecajj.....eefffo/////s http://etttto--eeeeeddddiaaaiil Level-domain-te
[EXAMPLES]
www. www.domiin.cmm com com - net
www.amazo.ccm co. uk -> uk
[SOLUTION]
(define-fun (_arg_0 String) String
Figure 13: User message for STRING
E LLM Prompt for STRING
The system and user prompt for STRING domain are in Fig. 12 and Fig. 13
F
The Full STRING Grammar
The full grammar for the STRING domain is detailed in Fig. 14
20

---

Start
S
arge argg
string variables string literals
lit-1 lit-2 ...
(replace S 5 S)
replace replaces first occurrence of in with
(concat S S)
concat x y concatenates x and y
(substr S I)
substr extracts substring of length from index
(ite S)
ite x y returns y if true, otherwise int to. to.str converts int to string
(int.to.str I)
(at S I)
x returns the character at index y string
B +
true false (-/1)
bool literals
y returns true if equals y contains returns true if contains
(contains S S)
(suffixor S)
suffixof returns true is the suffix of y prefixof returns true if x is the prefix of int variables
(prefixof S S)
I
arge arg1 ...
int literals lit-1 lit-2 ...
(str.to.int S)
str. to int converts string x a int
(+TT)
sums and y
(.II)
y subtracts from
(length S)
length x returns length of'x
(ite B 7 T)
y returns if is true, otherwise
(indexof S $5) I)
indexof y returns index of y in starting at index
Figure 14: The full SYGUS STRING grammar of the PROBE benchmark suite. Integer and string variables and constants change per benchmark. Some benchmark files contain reduced grammar,
21

---

G
The Full TENSOR Grammar
General TensorFlow functions:
(x)
tf. y) tf.audd
tf.argmax axis)
tf. tf.argminiinput, axis)
tf. a axis, stable=True)
tf. wargsorttvaluss axis, dLrection="DESCCENNNN 'DE'CENDING',, stable=True)
tf. boolean mask mask(tensor, mask)
tf. broadcast to(input, shape)
tf. cast dtype)
tf. bfyclii..y.valleett, clip_value.min, clip.value_max)
tf. (valuu,,,,,, axis)
tf. Cccoosttnttvaluu
tf cowooootttaalletaeoococooo dtype)
tf. dividiee
tx.equal(x, y)
(x)
tx.eap dims(input, axis)
tf. tf.eye(num rows)
tf.eye(num rows, num columns)
tf. row dtype)
tf. ff.fillddims, value)
tf. tf.gather(parrms,, indices)
tf tf.gather(params, indices, axis, batch.dims)
tf. (parrss indices)
tf (paaasss indices, batch-dims)
tf tf.ggeeter(x, y)
tf .f..geeter equal(x, y)
tf www.tt...bimmcmmmmm. batthbbincount((rrr) tf tf.math.ceil(x)
tf. mon
tf. www.aath.oouttnnnneeooonnno axis)
tf. wft.aatccussum(x.. axis)
wT..ath.cumsum(x axis, exclusive=True)
tf
y)
ff.math.floor(2
tf. tf.math.Log(x)
tf..mtt..neeeee .t..t...ggattie(
tf. www.att.reciipcaall...
w.f.math.reciprrcal..o
tf. tf.mathh.semeen..nxxdda.... segment_.dds ids)
tf.math tf.mathh.semmenttnnnnddatt segment_iid idd)
tf.math. if..math.segment.nnniee.. segment_idd ids)
tf tt.mtth.seeeenttproddddatt segment_ids)
tf tf.matth.semmenttssundddt... segment_ids)
tf. maatth-squrreddddffeeeencckk y)
tf. tf.math.tor k(input, k)
tf. .aatt.unsottedd..mm segment max (data, segment ids, segments)
tf iatt.uunootedd segment (eageent_meanfcieeee (data, segment ids, num num. segments)
tf. Betoorteddeement___noe_ segment_min (data, segment_ ids, num segments)
tf. math.unsorted
tf.math.
ciamment_prodddaae segment_ ids, num segments) segment_idd ids, num. segments)
Figure 1.:: List of TensorFlow operations as used in TFCODER.
22

---

tf. if.maatul(a, (a,
tf.maaximu (x, y)
tf.minimum(x, y)
tf. ww..mitppyyxx, y)
tf. tf.not_equallx,, y)
iff.one.hottimdiccs depth) tf.ones(shape)
tf..ones.luee(Input)
tf. tt.pad(tensor, paddings, mode= "OONSTNNNN
tf. (atpsor, paddings, mode= 'CONSTANT',
constant.values))
tf. ptentor, paddings, mode= 'REFLECT))))
tf. pad(ten,or, paddings, mode= 'SYMMERRIC")
tf. range(start)
tf. range(start, limit, delta)
tf. ree.ucee.nyyiinnttteennnee. axis)
tf. retdicee_aaxiinnttttessss)))
tf. resduucee_aaainnnttttennns, axis)
tf. reeduuee_mmammnnntttteessss
tf. redducee.mmannnnnnttteeeesr axis)
tf. redduceemiinninppttttenorr
tf. reduce min min(input tensor, axis)
tf. reduce (iodutn tensor, axis)
tf. reduce sum(input tensor)
tf. preducc_suuminputtteenssss
axis)
tf. reshapeettessoorr shape)
tf. reverse axis)
tf. rot.rolllnnng (input, shift, axis)
tf. (x)
tf sotarcchoortasssorteeeeequuuuu values, side='left values, side=' right')
tf. sesearchsortee(sstteeeeeuuuuuuue
tf. sequence mank(t))g
tf. sequence mang(hsn,,,, maxlen)
tf. shape(input)
tf. (x)
tf. tf.sortvvalues, axis)
to.souevvslues, axis, 1 tf.sqrt(x) tq.square(x)
tf (inueee
(inuet axis)
tf stauuuss axis)
tf subt y)
tf. tensordot b, axes)
tf. tileiiit,,,,, multiples) tf. transpos((()) tf. transpose(a,, perm)
tf. www.que_withhcoonnss//////
tf unatack(valle,, axis)
tf www.eeccodiiiaaeee
tf. www.herrecodiiioonn x, y)
tf. zeros (shape)
zeros Like (ikkei))
SparseTensor functions:
tf. Sparseeeesoo (indices, values, dense_ shape)
tf. sparse.add
tf www.spps..cccaattcccecp sp-intt tf. sparse. exparde.expand.c.om dims input, axis)
23

---

tf. sp.rse. from (ense(tensor)
tf.ssarse. (sx a, sp b)
tf. sparsse.minimum((p a, b)
rt..pprre.reeuuc...xxspppppppp axis, output_is_ sparse)
tf. ftrspprrss.rrdduees.ssstss....o axis, output_is
strspparee.reshhacccs..iiinntt shape)
tt.pperse.rettaansspppppptt te_ren)
t.sparrse_s3lceetsppppppp, start, size)
w..pparse..plltt(ppppppp.. num_split, axis)
tpaspase.t depsesspp input)
tp dense(sp input, default value)
tp.spare.. indicatorrsp input, vocab size)
tf. tf.sparse. ggparseetransposeess..... perm)
tf.
Python-syntax operations:
Indexxiggkiss00eeratton: argll: arg2]
andexiingpprrationn arg1(arg2]
PairGreattinnpeeration:: (argl, arg2)
Singlertootuoeeeeratttoeeerrrrsr (arg1,)
Slichinkkxt@@Borhhppraattt.oo a
Sticingkvris@eeetpperaaiin argl[arg2:]
Slccinngwiss@iighhhpprrattooo::n argl[:arg2]
SticingAwisslerrhppraatoooo argll:, arg2:arg3]
ShicingAvislleeftperrttonn argl(:, arg2:]
SlicingkkisRRiphhtperrttooo argll:, :arg2]
Tripleecreationpperatiinn (argl, arg2, arg3)
24

---

Rule + Filter then Transforms
Transforms
Transform Transform: ; Transforms
Filter
Atom not Atom Atom Filter Atom Filter
Atom
Color=c Color Size=; Size Degree = Degree Width- Width Height - Height
Shape Row= Row Column Column is neighbor ( Obj, Obj
Transform
update.color Color) move (ir)) move_max (ir)) ( Overlap) (Angl)))Aggee) rectanect Color, Overlap) hollow. rectangle Color)
mirror(Aziis) add border Color) flip(AAis) NoOp
Obj
self
|
Color
color of Obj) ) GREY RED BLACK BLUE YELLOW ORANGE
BROWN
GREEN
GREY FUCHSIA.
Dir
dir_of( Obj) UP DOWN LEFT RIGHT UPLEFT DOWNLEFT UPRIGHT DOWNRIGHT
Azis
oxis_ (bbj) VERTICAL HORIZONTAL
LEFTDIAGONAL RIGHTDIAGONAL
Overlap
TRUE
FALSE
Angle 90
180 270
Size
size_of Obj) MIN MAX
...
Degree
degree_ of Obj) MMN MAX
Width
oi Obj) MIN
MAX
Height
height_or of Obj) MIN MAX
Column
column_ of Obj)
MIN
MAX
Row
row_of ( Obj) MINN
MAX ....
Shape shape of Obj) ENCLOSED
SQUARE
Figure 16: The full grammar for our ARC DSL, object specific parameters like size, degree change per benchmark.
H The Full ARC DSL
The full grammar of our ARC DSL shown in Fig. 16
I Detailed Prompt Settings
For ARC, sample completions with temperature and 4000 max tokens. For TENSOR, temperature and 4000 max tokens. For SYGUS, we use temperature 0.5 and 4000 max tokens. We the same settings for all three LLMs. When prompting GPT40, we response. type JSON.
Broader Research Impacts
Our technique presents a powerful strategy for harnessing both syntactically valid and invalid outputs from an LLLM to learn a surrogate model. Incorporating hallucinatory outputs often erroneous generated by the model, allows approach mitigates the need for large-scale sampling of completions from LLMs, promoting more efficient and effective utilization of these models, saving resources. In addition improving the cost effectiveness of using LLMs, it also opens up new avenues for enhancing model robustness and adaptability across different domains.
extract insights that discarded in standard practices. Our
25

---

Algorithm 2 ARC Synthesis Algorithm
Input: A set of input-outpu example grids E, transform grammar G. and filter grammar Gr Output: A solution map M from each transform to the corresponding filter
I: procedure HYSYNNHI-RRCC,, Gp. Gc)
2: LvL. B 0,0
Initialize search state Sample solutions from the LLM Initialize both PCFGs using LLM solutions
Siim LLM(E)
4:
Gp. Gr + INIT(Sp, Sno), (NI
5:
while not timeout do
6:
O + MANSFORM--SARCHHE
Synthesize transforms that cover all objects Synthesize filters for the above transforms b Found filter cach transform > Return the complete solution
M FULTER-SEARCH(
itt, EM # then return
9:
Algorithm 3 Transform Synthesis Algorithm
Input: PCFG Gt and input-output grids &
Output: A map O from transforms to correctly changed objects
I: procedure TRANSFORMS SEARCH((,,
LVL, B, <- 0, 0,
Initialize search state
3: while LVL S LIM do
4:
for T' E NEW-TRANSFORRS/T
LVL., B) do EVAL (W.) (i E E, w: E
D For all transforms with cost LvL D Apply transform objects in input grids from E I covers subset objects Store the transform and objects covered
5:
EVAL nU (Wo Wa EO} + 0 then
7:
O EVAL
clse EVAL E then
9:
continue
T is observationally equivalent to another transform B > All objects are correctly transformed
10:
Ureo O[T] = Uniose (wo
wo E o) then
11:
return O
B[LVL] < B[LVL] U (T)
Add transform to bank, indexed by cost later search
13:
t EVAL
> Cache evaluation result
14:
LVL < LVL+11
return
Cost limit reached
K The ARC Synthesis Algorithm
Overall Synthesis Algorithm The overall synthesis algorithm takes as input a set of ouput- grids E, along with grammars G. and Gy. We sample candidate solutions from LLM by constructing a prompt using& &. These solutions are used to initialize the weights of production rules in the transform and filter grammars, G, and gy, respectively. We optimize the search by using divide and conquer approach: first, a TRANSFORM SEEEORRM--EACHH procedure searches for transforms, mapping each to its correctly transformed objects in O. Following this, search for filters is initiated using the FILTER- SEARCH procedure. If a filter is found for each transform. the algorithm terminates and returns M, which maps each transform to corresponding filter. The algorithm described above terminates after the first solution is found, but we keep searching for smaller set of transforms [
Transform Search Algorithm The transform synthesis algorithm in Algorithm taakes input PCFG G. and & enumerates transforms in the order of increasing discrete costs according to G.-
The algorithm starts with the following initial state: 1) cost level (LVI.) equal to O in order to keep track of the current cost during enumeration, 2) a program bank (B) that indexes the enumerated transforms by their cost for efficient retrieval, and 3) evaluation cache (E) that stores the result of all evaluated transforms within B. At each iteration, the algorithm explores the space of all new transforms generated by the NEW-TE TRANSFORMS procedure for the current cost level.
On line in Algorithm 3 the enumerated transform T is applied each object the input grids from E. If T correctly transforms subset of objects, T and the objects covered by it are stored in map O indexed by the transform (line 7). When the transforms in cover all grid objects, O returned (line 10-11). For transforms with objects bound by filter, such as in update. coriaate.cooorceeo color(cotor..oooo (other)), we consider all possible values (of color) that could be assigned and yield concrete transforms corresponding to each of those assignments.
26

---

Filter Search Algorithm The filter search algorithm takes as input filter PCFG Gj, E, and the map returned by the transform search Algorithm The filter search proceeds in similar manner as the transforms search wherein it enumerates filters in the order of increasing cost as per the PCFG 9y. It initiates new search to find filter for each transform in O. Each enumerated filter expression is evaluated on all objects in the input grids. If the objects for which the filter is 'rrue are the same as the objects covered by the transform, we have found a filter for this transform. Once filter is found for each of the transforms in O we return the solution map M.
27

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The main claims accurately reflect the paper's 's contributions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The authors have created separate "Limitations" section (4.3) included in the experiments section of the paper.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
28

---

Answer:
[NA]
Justification:
The paper does not include theoretical results.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: All the results presented in the paper can be reproduced using the LLM generations and synthesizers, both which are publicly available on GitHub.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path reproducing verifying the results. 5. Open access to data and code
29

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
The authors provide a detailed description the datasets. Instructions for reproducing the results, along with the actual results in the paper, are included in the supplemental material.
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cccppbbLic
SondesssCodeSbnnsssioooolicc for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/eetails
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The paper and Github repository provide all the necessary details to reproduce the experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: The non-deterministic component of our experiments is the LLM sampling and the results are validated by performing the experiments across different models and domains, and also for different number of LLM samples.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
30

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπτог rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The experimental setup details are provided in the experiments section.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics http:///wurrr...ccccubbb///tcccc lines!
Answer: [Yes]
Justification:
The research conducted in the paper conforms with the NeurIPS Code of
Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: The paper discusses the potential impacts of the work in the conclusion and the "Broader Impacts" section in the appendix.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
31

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
The authors reference all relevant papers related to existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
32

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, papprssi thcode. com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is not available online, the authors encouraged to reach out the asset's s creators.
13. New Assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The authors have included experimental results in the supplemental data and publicly released the ARC synthesizer on GitHub, complete with documentation.
Guidelines:
The answer NA means that the paper does not release assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
33

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
34


Reviews:
[{"review_id": "kOr5swkklr", "reviewer": "Reviewer_FZiE", "summary": "This paper introduces HySynth, an approach to program synthesis that combines (1) sampling programs from a large language model (LLM) to train a probabilistic context free grammar (PCFG) with (2) applying bottom-up enumerative search guided by the PCFG to solve programming by example tasks. It applies this approach to three domains: the abstract reasoning corpus (ARC), tensorflow expression synthesis, and string expressions (SyGuS). By learning the weights of the PCFG from the samples drawn from the LLM, HySynth produces state of the art results on all three domains, solving more problems in less wall-clock time. The main contribution is the use of an LLM to choose weights to guide a bottom-up enumerative program synthesis search system.", "questions": "Is the time to draw N samples from the LLM and construct the PCFG included in the plots in Figure 4a, 4b, 4c? If not, I would encourage doing so.\n\nWhy do you include few-shot examples when prompting for the tensor domain, but not for the string domain (or have I misread this?)? It seems more important for the string domain given that 0% of the LLM-generated programs in the string domain are valid completions.\n\nnit: Figure 2 suggests the I/O examples are provided as an input to the synthesizer, rather than just the PCFG. I don't believe this is correct or intended.\n\nIs it correct to state that the PCFG is reasonably approximating the LLM's condition distribution over output programs for a given prompt (line 65)? Though it is trained to approximate this, I expect it is quite a poor approximation. And then the approach does not sample from the PCFG, but rather enumerates from it, making it unclear to me that a good unbiased approximation of the LLM's conditional distribution is what is desired (certainly if the PCFG could perfectly mimic this distribution that would be great!, but perhaps there is better; beyond wanting to somewhat approximate the LLM's condition distribution, increased functional diversity over the 10m search period is also important.)", "limitations": "The limitations section (4.3) captures the main limitations of the system well and articulates them clearly. The Broader Research Impacts appendix (K) touches on the research, albeit not societal, impact of the work. This seems sufficient to me.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is the first (concurrent with Li et al [29]) to use pretrained LLMs to guide search-based program synthesis. The approach introduced by HySynth -- to sample programs from a pretrained LLM to learn the weights for a PCFG, and then to guide bottom-up enumerative search according to these weights -- is a natural and simple idea, and the paper demonstrates that it works well across a variety of domains. The simplicity of the approach is a strength, making it possible to apply to a range of domains -- wherever a CFG can describe the DSL used in the domain. The simplicity and generality of the approach make the contribution significant: it is quite likely that additional methods that learn to perform a fast search guided by an LLM will follow in future research, as program synthesis with LLMs is an important and growing area.\n\nThe experimental results are robust, showcasing the HySynth method across a good diversity of domains and yielding clear improvements in each. (See also Weakness 1 however.)\n\nThe paper is clearly written, including a robust and clear background section, a clear statement of the method and experimental results, and well contextualized in the context of the literature.", "weaknesses": "For the direct sampling baseline, there is either a clarity or methodological issue. It is unclear how many samples are drawn from the LLM in the direct sampling approach, and if the number of samples is more than 1, it is not clear what is done to produce diversity (i.e. setting the temperature during sampling, or sampling without replacement e.g. with unique randomizer [1]). From the horizontal lines in Figure 4a, 4b, and 4c, it seems overwhelmingly likely that only a single sample is drawn from GPT4o for the direct sampling baseline, which places this baseline at a disadvantage since >>1 samples can be drawn within 10 minutes. The disadvantage is compounded because direct sampling is trivially parallelizable, so the number of samples that could be drawn in this time is large. And as one further point in favor of drawing multiple samples for the direct sampling baseline, the HySynth approach itself uses as many as N = 100 samples from the LLM (line 273). I recognize this may be a costly baseline to run (I have not computed the cost), and suggest a reduced time limit if the cost is prohibitive for the 10m time limit.\n\n[1] Incremental Sampling Without Replacement for Sequence Models https://arxiv.org/pdf/2002.09067\n\nThe other weaknesses I observed are touched upon in the limitations section of the paper. The main limitation of the significance of the work is (as stated in the paper) that is requires a DSL, and particularly one that has a CFG, and so a custom synthesizer for each DSL, for the method to be applied. This requires meaningful work to apply HySynth to a new domain.\nAnother concern (also addressed in the limitations section) is the possibility of data leakage in the evaluations. I share the authors' view that this is not a major issue _provided_ they address the first weakness I state above for the direct sampling baseline.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed review and thoughtful comments. Please note our top-level comment with additional experimental results. Below we address specific comments and questions.\n\n**Q: For the direct sampling baseline, clarification about how many samples are drawn from the LLM in the direct sampling approach, and if the number of samples is more than 1, what is done to produce diversity?**\n\nThere has been a misunderstanding: the results of the direct sampling approach are based on 100 samples (see line 251), the same number that is used to learn the PCFG. We also report the temperature and other prompting settings in appendix J – we sample with a high temperature to get diverse solutions. Please see Global Response Q1 for why we decided to separate LLM sampling time from symbolic synthesis time.\n\n**Q: The main limitation of the work is that is requires a DSL, and particularly one that has a CFG, and so a custom synthesizer for each DSL, for the method to be applied. Can this be overcome?**\n\nOur approach does require a CFG for the DSL but a custom algorithm is optional. In this paper, for the String domain we use a generic synthesizer that takes a grammar (and an interpreter) for the DSL as an input.\n\n**Q: Is the time to draw N samples from the LLM and construct the PCFG included in the plots in Figure 4a, 4b, 4c?**\n\nSee Global Response Q1.\n\n**Q: Why do you include few-shot examples when prompting for the tensor domain, but not for the string domain? It seems more important for the string domain given that 0% of the LLM-generated programs in the string domain are valid completions.**\n\nSee Global Response Q2.\n\n**Q: Why are I/O examples provided as an input to the synthesizer, rather than just the PCFG?**\n\nThe I/O examples need to be provided as input to the synthesizer in order to test the correctness of generated programs and prune the search space based on observational equivalence (see lines 5, 6, and 8 in Algorithm 1).\n\n**Q: Is it correct to state that the PCFG is reasonably approximating the LLM's condition distribution over output programs for a given prompt?**\n\nYou are right that a PCFG is still a poor approximation (even for the conditional distribution). What we meant to say here is that, for a specific task, a PCFG is able to capture just enough signal from the LLM that it can guide enumerative search. We’re happy to update the phrasing!", "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": "pxdFPiuF5A", "reviewer": "Reviewer_XXbQ", "summary": "The paper introduces a new approach for solving structured prediction and reasoning tasks by leveraging the programming and planning capabilities of LLMs to enhance bottom-up search in program synthesis.\n\nSpecifically, HYSYNTH initially generates preliminary solutions directly from the LLM. Since direct LLM sampling performs poorly in unfamiliar DSLs, HYSYNTH does not use these samples directly but calculates the probabilities for a PCFG grammar from them, incorporating LLM guidance into the bottom-up search (CFG -> PCFG).\n\nExperiments show that HYSYNTH consistently outperforms both the baseline synthesizers and ablations, and is effective even with a smaller number of samples.", "questions": "The experiments show that HYSYNTH solves more problems within the same time limit. Does the time reported include the time taken for sampling from the LLM and training the surrogate model? What percentage of the total time does LLM inference take?\n\nFor GPT-4o's 0% performance on the percentage of syntactically valid completions in the STRING domain, can a more detailed analysis be provided? Could this be improved with a simple CoT strategy or other methods?", "limitations": "The authors have addressed the limitations of their work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The HYSYNTH method can be implemented directly on existing LLMs without additional model fine-tuning, allowing its performance to improve as the models advance.\n\nHYSYNTH performs well with fewer samples, consistently surpassing current methods, making it robust and efficient.\n\nExperiments demonstrate that HYSYNTH consistently outperforms both baseline synthesizers and ablations across various configurations.", "weaknesses": "The use of LLMs in HYSYNTH appears simplistic and seems not to fully leverage the capabilities of LLMs.\n\nHYSYNTH's performance depends on the LLM's capabilities, including additional inference time and prediction accuracy.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed review and thoughtful comments. Please note our top-level comment with additional experimental results.\n\n**Q: The experiments show that HySynth solves more problems within the same time limit. Does the time reported include the time taken for sampling from the LLM and training the surrogate model? What percentage of the total time does LLM inference take?**\n\nSee Global Response Q1.\n\n**Q: For GPT-4o's 0% performance on the percentage of syntactically valid completions in the STRING domain, can a more detailed analysis be provided? Could this be improved with a simple CoT strategy or other methods?**\n\nSee Global Response Q2.", "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": "tI7HjYcxDi", "reviewer": "Reviewer_MWWa", "summary": "This paper presents a hybrid program synthesis approach that strengthens the classic bottom-up search with an LLM-guided prior distribution, given as a probabilistic context-free grammar (PCFG). The focus of this paper is to solve complex PBE tasks where programs in unfamiliar DSL are difficult for LLMs to generate directly, and traditional combinatorial search is infeasible. The key insight is that LLM-predicted programs (although incorrect by themselves) can provide valuable intuition regarding which operator or component to use in the correct program. As such, HYSYNTH samples a set of full programs from LLM to train an approximation PCFG model. To perform the bottom-up synthesis, HYSYNTH uses an off-the-shelf or custom synthesizer for the specific domain.\nThe experimental results show its improvement against both vanilla LLM generators and non-LLM-based synthesizers.", "questions": "- Using PCFG as the approximation model seems too simple at first glance, but it works well in the evaluated benchmark. It is also surprising to see that only 10 samples can often achieve comparable performance as the full 100-sample approach (Appendix C). This leads me to wonder whether the model only captures very superficial patterns from the LLM samples, and whether an even simpler surrogate model could be used. For example, It is mentioned in line 151-157 that GPT-4o predicts the relevant components with high accuracy, and never uses irrelevant components in the example. If we directly remove such irrelevant components from the CFG and directly use the search algorithm, how would such a baseline perform?\n- I am not entirely convinced by the superior performance of HYSYNTH over using LLMs purely without search. For example, for the ARC task, the HYSYNTH approach uses a divide-and-conquer strategy; it would be interesting to see how the LLM baseline performs when it also applies such a strategy. Also, in the paper ExeDec, Section 5.2, the experiments show that presenting DSL programs as Python functions can enable the LLM to better leverage its general knowledge from pretraining and improve the result. I wonder if such a prompting technique would improve the performance of pure LLMs.\n\n[1] Shi, Kensen, et al. \"ExeDec: Execution Decomposition for Compositional Generalization in Neural Program Synthesis.\" The Twelfth International Conference on Learning Representations. (ICLR 2024)", "limitations": "The limitations are well addressed.", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- It proposes a promising hybrid approach that combines the efficiency of formal program synthesis and the power of LLMs.\n- Compared to training new models for every new DSL/domain, the proposed approach only needs to extract a small PCFG from a few LLM samples, which is lightweight and robust. \n- The approach is general; in particular it can be applied to various domains (reasoning about grid puzzles, tensor manipulations, and string manipulations) and with different LLMs. It can outperform baselines substantially according to the experiments.\n- The problem is well-motivated, and the limitations and related work are discussed in an insightful and thorough manner.", "weaknesses": "- The datasets are small and domain specific, and requires implementing a synthesizer. It is unclear whether such an approach can scale to more complex programs, for example to program with loops, or even general-purpose programs.\n- It mentions in the limitation section that sampling from LLM is costly, and it uses different models like GPT3.5, GPT-4, and DeepSeek, but did not provide a comparison of the costs.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed review and thoughtful comments. Please note our top-level comment with additional experimental results. Below we address specific comments and questions.\n\n**Q: The datasets are small and domain specific, and requires implementing a synthesizer. Can HySynth scale to more complex programs, for example to program with loops, or even general-purpose programs?**\n\nIt is true that we have not evaluated the approach on more complex programs with loops, but there is relevant work in the program synthesis community on extending bottom-up search to programs with local variables and loops [1,2].\n\n[1] LooPy: interactive program synthesis with control structures  https://dl.acm.org/doi/pdf/10.1145/3485530\n\n[2] Efficient Bottom-Up Synthesis for Programs with Local Variables https://dl.acm.org/doi/pdf/10.1145/3632894\n\n**Q: It mentions in the limitation section that sampling from LLM is costly, and it uses different models like GPT3.5, GPT-4, and DeepSeek, but did not provide a comparison of the costs.**\n\nThe inference cost of the LLMs is dependent on the API pricing; with GPT3.5 and DeepSeek being cheaper than GPT-4o and the number of samples drawn per LLM are roughly the same. We are happy to include a cost analysis across LLMs in an updated version of the paper.\n\n**Q: If we remove irrelevant components not present in LLM solutions from the CFG  and use the search algorithm, how would such a baseline perform?**\n\nThis is an interesting experiment and we have now performed it on the String and Tensor domains. More specifically, we evaluated an ablation, where the surrogate model is a “binary PCFG”, i.e. a CFG that only includes components mentioned by the LLM. \nYou can see the graph of the results in the pdf attached to the Global Response. It performs worse than HySynth because the search might exclude essential components from the grammar. This experiment further highlights the balance achieved by HySynth in terms of prioritization based on LLM guidance.\n\n**Q: for the ARC task, HySynth uses a divide-and-conquer strategy; how would an LLM baseline that also applies such a strategy perform?**\n\n If we understand correctly, the reviewer is suggesting to query the LLM for filters and transforms separately and then combine the results in some way. We argue, however, that such a  technique would not count as an LLM baseline, but rather as a different hybrid algorithm (only slightly less advanced than HySynth). Like HySynth, it would combine LLMs with a semantics-based pruning technique  originally proposed in the program synthesis community (in this case, divide-and-conquer synthesis [3]).\n\n[3] Scaling Enumerative Program Synthesis via Divide and Conquer\nhttps://www.cis.upenn.edu/~alur/Tacas17.pdf\n\n**Q: Will presenting DSL programs as Python functions enable the LLM to better leverage its general knowledge from pretraining and improve the results?**\n\nThis is an interesting suggestion that could perhaps improve the performance of LLMs. However, we consider non trivial prompting and fine tuning techniques as being orthogonal to our contribution, which focuses on *using existing LLM solutions* more effectively.", "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:
We thank the reviewers for their time, valuable comments, and encouraging feedback! In the global part of the response, we answer shared questions and provide a list of changes we plan to make in a revised version of the paper.

**Q1 (Reviewers FZiE and XXbQ): Does the time reported in Fig 4 include the time taken for sampling from the LLM and training the surrogate model? What percentage of the total time does LLM inference take? The LLM baseline is at a disadvantage because many more samples could be drawn within the timeout of 10 minutes.**

In our experiments, the results for both the LLM baseline and HySynth are based on 100 samples from the LLM. The time to draw those samples is excluded from the graphs in Fig 4.
Reviewer FZiE is right that many more samples could be drawn within 10 minutes. Indeed, one way to conduct our experiments would be to give all techniques the same amount of total time, which can be used towards either LLM sampling or symbolic synthesis. We thought such setup would not be fair for the following two reasons: 1) LLM sampling incurs not only time cost, but non-trivial monetary cost, while symbolic search is virtually free; 2) the time cost of LLM sampling depends on many incidental factors out of our control (e.g. network latency, server load). We chose instead to completely separate the sampling stage from the synthesis stage and to only report the synthesis times in the figures (which is why the LLM-only line is always horizontal, as the reviewer notes). 
That said, we did compute the time it took to sample 100 solutions, and it amounts to 285 secs for tensor domain and 268 secs for the string domain. Learning the PCFG takes less than 1 sec for all domains. We will report these times in the next version of the paper. 

**Q2 (Reviewers FZiE and XXbQ): Why does GPT-4o have 0% correctness and syntactic validity on the String domain? Could this be improved with more advanced prompting techniques? Why do we not provide in-context examples for this domain, like for Tensor?**

This is due to the specifics of the SyGuS benchmark, from which our String problems are drawn. In this benchmark, each problem comes with a custom restricted grammar; all grammars are subsets of the full SyGus grammar but purposefully impose additional restrictions on the solution (for example, the synthesizer is usually allowed only a handful of string constants, which excludes trivial solutions that simply reproduce the given output examples). In the experiments reported in the paper, we judge syntactic validity against these custom grammars (which is how the SyGus competition is also judged), and the LLMs turn out to be quite poor at following these syntactic restrictions, even though the grammar is given in the prompt.
Providing in-context examples is unlikely to help because these examples would have a different grammar, and only confuse the model.
If we were to relax the definition of syntactic validity, ignoring the custom grammars and allowing the full SyGuS grammar, LLM solutions would achieve a syntactic validity of 60.5% and solve 20/70 problems correctly (which is better than Unguided search but worse than Probe and HySynth.). We will include these additional results in the paper along with a detailed analysis.
 
**Change list**
1. We will report the time and monetary cost of sampling from the different LLMs in our experiments (as mentioned in Q1 above).
2. We will clarify why LLMs get 0% syntactic validity on the String domain and add the results of our new experiments with a relaxed notion of validity (as explained in Q2 above).
3. We will include the results of an ablation study using a simpler surrogate model, which simply excludes the components not used by the LLM (as suggested by Rev MWWa; preliminary results reported in the attached PDF).

Meta-review: This paper proposes performing bottom-up program synthesis search but using a PCFG derived from LLM-generated samples to guide the search, leading to improved performance in a variety of synthesis domains/datasets.

I recommend to **accept** this paper. Reviewers agreed that the approach is well-motivated and general, the experiments are convincing and thorough, and the writing is clear. The authors answered reviewers' questions and resolved their concerns in the rebuttal. All reviewers are in agreement about acceptance.

I am confident that this paper meets the bar for acceptance. However, I was on the fence about recommending poster or spotlight. On the positive side, the reviewers had a high average score (6, 7, 7) and I agree that the paper and underlying research were done very well. But after much thought, I am recommending a poster presentation because I feel the core idea is very simple and natural, which is a good thing when trying to replicate the work, but it also means the work is a bit more incremental than I would imagine for a spotlight paper. The authors cite multiple prior works which learn how to guide combinatorial program synthesis search by training a model on data in a particular domain, and this paper's contribution is using an LLM to provide this guidance instead, more generally (across multiple domains) and without training. This feels like an instance of a common pattern of generalist LLMs being used to replace specialist models trained from scratch. Under this lens, I am not so surprised that the approach works. Again, I still think the work was done very well and it is a valuable contribution to the AI-for-code research community to have solid confirmation that this approach does indeed work, but I would expect a spotlight paper to provide a bit more novelty.
Decision: Accept (poster)