Hypothesis Search: Inductive Reasoning with Language Models
Authors: Ruocheng Wang
Eric Zelikman
Gabriel Poesia
Yewen Pu
Nick Haber
Noah Goodman
Venue: ICLR 2024 poster (2024)
Keywords: Inductive reasoning
large language models
Primary area: neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)

Abstract: Inductive reasoning is a core problem-solving capacity: humans can identify underlying principles from a few examples, which can then be robustly generalized to novel scenarios. Recent work has evaluated large language models (LLMs) on inductive reasoning tasks by directly prompting them yielding "in context learning." This can work well for straightforward inductive tasks, but performs very poorly on more complex tasks such as the Abstraction and Reasoning Corpus (ARC). In this work, we propose to improve the inductive reasoning ability of LLMs by generating explicit hypotheses at multiple levels of abstraction: we prompt the LLM to propose multiple abstract hypotheses about the problem, in natural language, then implement the natural language hypotheses as concrete Python programs. These programs can be directly verified by running on the observed examples and generalized to novel inputs. To reduce the hypothesis search space, we explore steps to filter the set of hypotheses to be implemented as programs: we either ask the LLM to summarize them into a smaller set of hypotheses, or ask human annotators to select a subset. We verify our pipeline's effectiveness on the ARC visual inductive reasoning benchmark, its variant 1D-ARC, and string transformation dataset SyGuS. On a random 40-problem subset of ARC, our automated pipeline using LLM summaries achieves 27.5% accuracy, significantly outperforming the direct prompting baseline (accuracy of 12.5%). With the minimal human input of selecting from LLM-generated candidates, the performance is boosted to 37.5%. Our ablation studies show that abstract hypothesis generation and concrete program representations are both beneficial for LLMs to perform inductive reasoning tasks.

Published as a conference paper at ICLR 2024
HYPOTHESIS SEARCH:
INDUCTIVE REASONING WITH LANGUAGE MODELS
Ruocheng Wang': Eric Zelikman', Gabriel Poesia', Yewen Pu², Nick Haber', Noah D. Goodman'
1 Stannood University, 2 Autodesk Research
ABSTRACT
Inductive reasoning is a core problem-solving capacity: humans can identify under- lying principles from a few examples, which robustly generalize to novel scenarios. Recent work evaluates large language models (LLMs) on inductive reasoning tasks by directly prompting them yielding "in context learning." This works well for straightforward inductive tasks but performs poorly on complex tasks such as the Abstraction and Reasoning Corpus (ARC). In this work, we propose to improve the inductive reasoning ability of LLMs by generating explicit hypotheses at multiple levels of abstraction: we prompt the LLM to propose multiple abstract hypotheses about the problem, in natural language, then implement the natural language hy- potheses as concrete Python programs. These programs can be verified by running on observed examples and generalized novel inputs. To reduce the hypothesis search space, we explore steps to filter the set of hypotheses to implement: we either ask the LLM summarize them into a smaller set of hypotheses or ask human an- notators to select subset. We verify our pipeline's 's effectiveness on the ARC visual inductive reasoning benchmark, its variant ID-ARC, string transformation dataset SyGuS, and list transformation dataset List Functions. On a random 100-problem subset of ARC, our automated pipeline using L.LM summaries achieves 30% accuracy, outperforming the direct prompting bascline (accuracy of 17%). With the minimal human input of selecting from LLM --M-generated candidates, performance is boosted 33%. Our ablations show that both abstract hypothesis generation and concrete program representations benefit LLMs on inductive reasoning tasks.
INTRODUCTION
Inductive reasoning- the ability infer general principles from specific examples and apply them to novel situations is a core aspect of human intelligence (Peirce, 1868). Recently, large-scale pre-trained language models have received significant interest for their performance across diverse range of reasoning tasks such as commonsense, arithmetic and symbolic reasoning (Rajani et al., 2019; Shwartz et al., 2020; Nye al., 2021; Wei et al., 2022; Marasović et al., 2021; Lampinen et al., 2022; Zelikman et al., 2022; Zhou et al., 2022). There has been extensive discussion of language models' impressive "in-context learning" capabilities, form of inductive reasoning. However, other work suggests that in-context learning of these models has highly limited capacity to perform inductive reasoning tasks where precise behavior is required (Chollet, 2019; Johnson et al., 2021).
The Abstraction and Reasoning Corpus (ARC) is particularly challenging inductive reasoning bench- mark (Chollet, 2019). For each task in ARC, models are given a set of training input-output pairs with shared transformation rule, and the goal is to predict the corresponding output(s) given the novel test input(s), as illustrated Fig 2 (a). ARC interesting because the answers are fairly natural for humans yet require complex and precise transformation. Evaluations of LLMs on ARC (Xu et al., 2023b; Mirchandani et al., 2023; Gendron et al., 2023) have directly prompted LLMs to predict outputs by in-context learning, finding poor performance relative to humans (Chollet, 2019; Johnson et al., 2021).
We instead take inspiration from Bayesian models of human inductive reasoning (Tenenbaum et al., 2006; Goodman et al., 2008). That research frames inductive reasoning posterior prediction: an ideal Bayesian learner assumes a large hypothesis space of possible rules, uses Bayes' rule to form posterior distribution over hypotheses from examples, then responds accordingly with posterior- predictive posterior-predictive
distribution. Studies of human inductive learning have found that people likely
'These authors contributed equally this work

---

Published as a conference paper at ICLR 2024
Train Examples
Generate Hypotheses
Select
Implement
Validate
Example
find the Highest sumbzered value in the inpul grid and then, starting from the top- left corner, replace zero with the next rumber in counten-llodwwie direction unill you reach the hightst numbareed valuze in the grid..
Example x Example 2 o/ Pasmpl 3 x
Example
grisigridl
Example Example Example 3:
alide the non- black cella each column down to fi lany black ia belo them as the colored numbers were falling to the bottom of the gnd due grovity, Keep the positions of colored numbers in their inttal column.
17
prid terill est goid fur oul caupeity ctsppep))
Example
25h0 (prte)
cchck the elemeni at row 1, corumre 4 input grd. and then updase the diagonal that passes through this cel witt the same color Staet from the bottom-belt corner and contirue to the topiright corerr in the diggonal
gridl cnd Einistt- oil to if les pacoal tut_arinn---eeee os pecca aet_
Bamole 2 Exmmle 3 v
Damole! of
An overview of our pipeline. From left to right, starting from a task in the dataset, a language model 1) generates a set of candidate hypotheses, 2) selects a subset, 3) implements each hypothesis in code as a function, and 4) validates the implementations against the training examples.
Figure 1:
approximate the full posterior with just a few hypotheses (Vul et al., 2014). Furthermore, people often represent hypotheses of the world at multiple levels of abstraction (Tenenbaum et al., 2011), with more abstract hypotheses guiding the search for more specific ones (Goodman et al., 2011).
We thus propose an approach that improves the inductive reasoning ability of LMs by decomposing the task via hypothesis formation at two levels of abstraction: first by generating hypotheses in natural language and then by realizing these as specific programs that are used for making predictions. Natural language provides abstract representations that uncover key features but are difficult to verify and potentially ambiguous. Programmatic hypotheses are directly verifiable on examples via execution and can naively generalize to new inputs but involve many implementation details that can be distracting to language model. In other words, we use particular programmatic implementations to act precise, generalizable representation of given inductive hypothesis formulated in natural language. Our pipeline thus disentangles inductive reasoning tasks primarily into two capabilities; the ability propose accurate natural language hypotheses and the ability to formalize them as programs.
However, in practice L.MSs are yet able to find good hypothesis with one try. Sampling multiple hypotheses and multiple programs per hypothesis turns out to be sufficient, but can be extremely costly, Thus, we also investigate approaches to reduce the number of hypotheses that must be considered. First, we use an LLM to summarize multiple hypotheses into a smaller number of hypotheses. Second, we experiment with querying human oracle go through all hypotheses and indicate which can be ignored. The latter can be viewed as lower bound on performance that would be achieved by our approach without filtering, because we also find that programs which are correct on all examples almost always generalize correctly, an interesting feature of complex inductive reasoning domains.
We conduct experiments on four inductive reasoning datasets: the Abstraction and Reasoning Corpus (ARC), the one-dimensional variant of ARC (ID-ARC), the Syntax- Guided Synthesis (SyGuS) dataset, and the List Functions dataset. Our results indicate that explicit hypothesis formation substantially improves performance over the direct prompting (ICL) approach. Ablation studies suggest both levels of abstraction natural-language hypothesis generation and programmatic hypothesis representations - are beneficial to performing inductive reasoning tasks.
Syntax-Guided
Contributions. We summarize the contributions of our paper as follows:
We propose pipeline that uses language models solve inductive reasoning tasks by generating and testing hypotheses in natural languages and code.
We conduct experiments to demonstrate our pipeline achieves significant improvement over basclines on four inductive reasoning tasks across different domains.
We explore and analyze techniques for reducing the hypothesis search space.
2 METHOD
2.1
PROBLEM STATEMENT
We consider inductive reasoning tasks that require discovering an underlying transformation rule given onput-output examples that follow this unknown rule. More formally, we given set of training examples (æ), y1), (I2, y ., (Ia.9) where each y; = f (xx) for some unknown function f. Our goal is for the model to infer the outputs Vi. V2, - 1/2 for list of novel inputs a1, 2/2 -.. .
2

---

Published as a conference paper at ICLR 2024
Algorithm I: Implementing Python Program from a Natural Language Hypothesis
Input:
Training examples ((1 (01,81),--e ..., (Fis Bn)), natural language hypothesis L, maximum number of feedback iterations Needhnukk initial LLM prompt template m, number of programs per hypothesis K
Output: A Python program p that is expected to be consistent with the training examples and hypothesis L
P LLM m. formao(mma(///mm L. {(11, ((21,11),.. y1),.... (Fn 3n. ))), K) // Generate K programs foreach program p E P do if (12 U6) {(11, U1),),,,.. ..... (n)) p(x.)) yi then
return // If a program succeeds on all examples, return it.
for i = to Neetback do foreach program p do for (1;, Ms) E ((11,,1),, ............ (In, Un)) do
CatchExceppion((((::))
if e # null then
// Add caught exception the prompt else if p(x;) + y, then
m.append(p.e break
m.append(pp p, wi, yi, p(x:)) break
// Add failed example to prompt
p + (LM(()
// Generate one revised program (x,))) y: then
(Dn, yn)) if (2 v.) (121,,))..... (In,
return p'
p p-11 p'
return arg m (( 91) p(z,) y and CatchExxeepion((((z.)) null
that captures the transformation f. This formulation applies to all four datasets consider in the experiment settings, as shown in Figure 2. This task is widely studied in program synthesis literature (Acquaviva et al., 2022: Odena et al., 2020; Ellis al., 2023; Xu al., 2023a), where Jomain-Speciife Language (DSL) is used to represent the
program written in a transformation, which applied the test inputs obtain the predicted outputs. Recently, there are also multiple works (Webb et al., 2022; Xu et al., 2023b; Mirchandani et al., 2023; Gendron et al., 2023) that do not predict the rule explicitly. Instead, large language models are used to predict the output for novel input examples directly given the training input-output pairs.
2.2 OVERVIEW
As illustrated in Figure 1, in our pipeline, we first prompt an LLM to generate hypotheses about the transformation rule shared across the input-output pairs in natural language. We then filter out a smaller set of hypotheses, using either an LLM or human annotator - the goal of this step is simply reduce the computational cost of later steps. The filtered hypotheses are used to prompt an LLM to generate programs that take in an input example and output the transformed result. These programs are then tested against the initial training examples. Note that, in these domains, we observed that programs that successfully generated outputs for training pairs almost always generalized to test items.
2.3 GENERATING HYPOTHESES
The first step in our pipeline is to prompt language model to generate natural language hypotheses for inductive reasoning problems. For each problem, provide GPT-4 with description of the task setup and the problem-specific input-output examples and prompt it to generate hypotheses about possible underlying rules or patterns that could explain the transformation in the given examples. We also provide two problems with human-annotated hypotheses as few-shot demonstrations in the prompt. More precisely, when doing an ARC task, we provide GPT-4 with the input-output examples in the form of grid of numbers and specify the corresponding colors for each number as part of the prompt, with the exact prompt included in the Appendix A. We sample multiple responses from GPT-4, with a temperature of 1.0, as the hypothesis candidates.
2.4 REDUCING NUMBER OF CANDIDATE HYPOTHESES
Ideally, we would like to directly test all the generated hypotheses by implementing them as Python programs. However, given potentially large number of hypotheses, testing all of them can be expensive. Thus, we investigate several methods to identify the most promising hypotheses from of proposals. For end-to-end approach, investigate using L.MSs to summarize the full set
3

---

Published as conference paper at ICLR 2024
1
[c=#/usrr//daee/hhotuttddb
1,,,,,
'shotcut.xl'
[6, 9, 8,
/'==/usrs/dave//neee table.xis]]
87,8,0,
pivot table.xls
[7. 8, 6]
['==/sers/ httprr///aa///toouaaaaa.l
[4, 2,
fors
(a) ARC
(b) ID-ARC
(c) SyGuS
(d) List Functions
Figure 2: Example problems in each of our four evaluation datasets.
of hypotheses into smaller number of hypotheses. Specifically, we directly present GPT-4 with all candidate hypotheses and ask produce a smaller number of hypotheses summarizing the given can- didate hypotheses. In addition, to help estimate a lower bound on performance if we were to test all hy- potheses, we ask a human annotator to go through candidate hypotheses and select correct ones, if any.
2.5 IMPLEMENTING PYTHON PROGRAMS FROM H HYPOTHESES
The pseudocode for this stage is presented in Algorithm 1. After obtaining set of candidate hypothe- ses for each problem, we individually use each hypothesis as the input for GPT-4 and prompt it to generate multiple Python programs that implement the described transformation. Then, we run these programs against the problem's 's original input-output examples (while still holding out the test exam- ples), determining whether they yield correct outputs for each case. code implementation correctly generates the outputs for each of the training examples, it is selected for generating the prediction on the test input example. If implementation passes all of the training examples, we repeatedly ask GPT-4 to revise the implementations according to the execution results on the training set, including er- ror messages and desired outputs, similar to Chen al. (2023). This leverages research on code repair spanning multiple decades (Schulte al., 2010; Pang, 2018; Vasic et al., 2019; Rahman et al., 2021, 1, in- ter alia). If we cannot achieve program that passes all the training examples after preset number of feedback rounds, select the program that passes the most examples for generating the prediction.
EXPERIMENTS AND RESULTS
3.1 DATASETS
We evaluate our approach on four distinct datasets: the Abstraction and Reasoning Corpus (ARC), the one-dimensional variant of ARC (ID-ARC), BUSTLE's Syntax-Guided Synthesis (SyGuS) dataset and List Functions dataset. These datasets offer diverse and challenging reasoning tasks in the domains of 2D grids, number sequences and strings, enabling us to thoroughly assess the inductive reasoning capabilities of our method. We provide examples of tasks in these datasets in Figure 2.
ARC. The Abstraction and Reasoning Corpus (ARC), proposed by Chollet (2019), designed to assess models' generalizable reasoning capabilities. It is a dataset of 400 training and 400 evaluation problems. Each problem consists set input-output 2D grids that capture a specific underlying rule pattern such geometric transformation and object counting. Each example is grid with 1 to 30 x 30 pixels of any of ten colors note that the input and output grid need not have the same shape. To effectively analyze this task despite the high cost of GPT-4, in our paper, randomly select subset of 100 problems from the 400 training problems as the evaluation dataset.
dataset
ID-ARC. ID-ARC is one-dimensional adaptation of the original ARC dataset proposed in (Xu et al., 2023b). Although simpler than the two-dimensional ARC problems, ID-ARC offers a more controlled setting to investigate the inductive reasoning abilities of language models they trained to handle sequential data. We once again select a random subset for evaluation, this time randomly choosing 6 tasks from each of ID-ARC's 18 categories for total of 108 problems.
SyGuS. The SyGuS dataset in the BUSTLE paper contains 89 tasks that require representing a mapping between pairs of strings
program (Odena et al., 2020). This task represents the kinds of problems solved by FlashFill (Gulwani, 201 I), feature in Excel that has been widely cited as an influential real-world example of program synthesis (Lee al., 2017).
4

---

Published as a conference paper at ICLR 2024
List Functions. The List Functions dataset proposed in Rule et al. (2020) is cognitive-science inspired inductive reasoning benchmark that involves mapping a list of numbers to another list of numbers. The transformation covers basic list operations like duplication, and removal, as well as more complex combinations of recursive, conditional, and numerical reasoning (e.g.. sorting, computing difference). The dataset has 250 tasks, each with 8 train and 8 test examples.
3.2 ARC
Settings. We measure the performance of different methods by computing the accuracy of models' prediction on the test input cases'. Although the input-output examples are typically visually presented in 2D pixel grids, we convert them to a text format the style of NumPy arrays. We include the prompt templates in Appendix A.
3.2.1 MAIN RESULTT
Method
Accuracy (%)
We compare the direct prompting baseline to different variants and ablations of our pipeline.
Direct
17
Program Only
23
Direct Prompting. As done in previous work (Xu et al.,
Summarized Hypo.
30
2023b; Mirchandani et al., 2023; Gendron et al., 2023), we provide training examples a prompt and ask GPT- 4 to directly infer novel test inputs' output grids.
Human-Selecter Hypo.
33
Human- Written Hypo.
45
Table 1: Results of the baseline and variants of our method on the randomly selected 100 ARC tasks. Our method outperforms base- lines with or without human supervision.
Program Only. In this ablation, we directly prompt GPT-4 to output Python programs for training examples. We generate 64 programs per task, selecting one pass- ing the most training examples to generate test outputs.
Summarized Hypotheses. For each problem, we first use GPT-4 to generate 64 candidate hypotheses and then ask GPT-4 to summarize 8 hypotheses from the 64 candidates. We then generate 8 programs for each hypothesis, resulting in 64 candidate programs per problem. This is followed by 3 rounds of execution feedback. Note that during our experiments, we found that GPT-4 only generates correct hypotheses for 49 tasks, according to human annotators. Of the 30 tasks solved with summarized hypotheses, 28 had correct hypothesis before summarization.
Seleced Hypotheses. We first prompt GPT-4 to generate 64 hypotheses and then ask a hu- man to manually select a correct one of them for each task, if any exist. Then we generate 8 programs for each hypothesis, followed by up to 3 rounds of execution feedback. As we observe low false- positive rate, this is approximately a lower-bound to evaluating all hypotheses. Here, we only generate programs for the 49 tasks with selected hypotheses. Of these, 33 (67%) led to correct programs.
Human-Written Hypotheses. For this version, we leverage the human language annotations from the LARC dataset (Acquaviva et al., 2022) as golden hypotheses. We then generate programs for each hypothesis, followed by 3 rounds of execution feedback. We treat these human-writter hypotheses as oracle solutions in order for us to better understand the extent to which this pipeline separately bot- tlenecked by hypothesis generation as opposed to program generation. The main results are shown in Table 1. Using a programmatic representation already boosts the performance over the direct prompt- ing baseline by a large margin, from 17% to 23%. Leveraging the summarized hypotheses is also helpful, improving the performance from 23% to 30%. We obtain the best accuracy 33% when gen- erating programs using numan-selected hypotheses. This is par with the version where directly leverage the golden human-generater hypotheses. For reference, we also evaluated the method from Icecuber (2020), which is the current DSL-based state-of-the-art approach (Mirchandani et al., 2023). Although it does not use a language model. it provides useful context. We found that it answered 43% of our 100 sampled items correctly, slightly underperforming the numan-writter results.
3.2.2 QUALITATIVE RESULTS
We show an example of generated hypotheses and the corresponding programs generated from the considered methods in Fig. 3. We observe that many of the correct hypotheses generated by GPT-4 are similar to the numan--ritted hypotheses in terms of their specificity, although often less concise. Summarized hypotheses can often become vague and ambiguous, which is potentially the reason for degraded performance. Sometimes the correct hypothesis is omitted from the summarized hypotheses. Note, because we prompt GPT-4 to treat the grids as NumPy (Harris et al., 2020) arrays, we observe that GPT-4 tends to leverage various NumPy functions to perform the desired transformation.
'The ARC challenge officially uses top-3 accuracy, checking if any of three model outputs are correct, but we consider 1 accuracy, like most related works (Xu et al., 2023b; Gendron al., 2023; Mirchandani al., 2023).
5

---

Published as a conference paper at ICLR 2024
?
Summarized Hypothesis and its Corresponding Generated Program
To make the output, extract the colored shape(s) from the input grid, expand or duplicate them according to the specified pattern, and place the resulting shape(s) into the output grid.
def tsranfoorruggi in Hospar grid: ndareay) > ng.ndarryy:
Franiier up, uniqqu Linpptt.giiin
curput_ grid np, zeros (13, 6), dtype-int)
for number in uniiqae que numbers:
number -- 0;
cont inoe
DURR_ munuiels = ap, where (ingul.geiz NON, san nia (iannrrr coas), mas (oun_
number)
min col, maxe col mininun cols), maxt inum, pols) shape ingut grid inin, rowinax now output..r- grridgg tashashe...aae shapw Ozshage
10
min co) tmax nol
11
[1]) shape
12
uutpat_ gr is hatae.. shappe (0), 3:3 shape [hhaew11]] alaae
13
alapp a acapp [0] <
14
output_ggela ieddddssan ishape.shape SD) shape. sh)pe(0), sshapo.shagell shape
15
output gri dllhhpeee... shape (0) :2 shape shape 3:3 shepe-aneppl (1]] shage
16
recurn out output_..re grid
Human- Human-Sclected Selected Hypothesis and its Corresponding Generated Program
input. you should see black grid with an 8x8 size. The grid contains one colored shape (either teal, red, or blue), which a 2x2 square with corner missing. The output grid size should 3x6. To make output, you have to extract the colored shape, and then expand horizontally by duplicating the entire shape. The result will be colored shape that is twice wide as the original onc.
der cranssorn grid grid Himpot_ grid: rp.ndarray) ng. ndarrayy
import numpy as rp
nor zero elementa and their indices
non_aweo, indluws ag.arggdee (iopatt..i...ii
min_rox, min_col rpumin zere www_rrrrrreieeeeeeeeeeee indices, axis=() max rox, max col rg-nex (non_rere, sero_indices. axig=() Fist the ool ared shape
shape wrppt...riddii............. wtw.i//oooooonnnnonrooooo Expand the shape borisontally aspanded_ssaaee ag.hatack (sshae, shaps)) recurn exganded_ ehape
min_col smex_ool
Figure 3: An ARC example of generated hypotheses using different methods and their corresponding generated programs. The summarized and human-selected hypotheses from LLM-generated candi- dates both yield correct programs. Note, these are gpt 1ppt--100 4-031 4-generated and we omit empty lines.
3.2.3 MORE ABLATION STUDIES
Chain of Thought (Wei et al., 2022). For this ablation, we wanted to understand the effect of the intermediate language without programs. We found GPT-4's performance dropped 19%, regardless of whether it generated the intermediate hypothesis or whether human-written hypotheses were used.
Execution Feedback. The results of models using different numbers of execution feedback iterations are summarized in Table 2. Execu- tion feedback plays an important role regard- less of how hypotheses are generated. However, the performance gain plateaus as the number of feedback iterations increases.
# feedback iterations
Method
0
1
2
Summarized Hypo.
24
28
28
30
Heman-Selected Hypo.
26
31
33
33
Human- Marnn-ritteen Hypo.
38
44
45
45
Table 2: Accuracy (%) of GPT-4 ARC using
3.3 ID-ARC
different numbers feedback iterations.
In contrast to the ARC experiments, GPT-4's
performance on ID-ARC was notably higher. We observed reasonably correct hypotheses by simply generating 16 hypothesis candidates. Thus, we do not need to obtain subset of hypotheses to reduce the cost of implementing programs, but instead evaluate on all the hypotheses generated. We compare the direct prompting baseline with our method, with and without natural language hypotheses.

---

Published as a conference paper at ICLR 2024
Method
Accuracy (%)
Direct Prompting For this experiment, report the accuracy direct prompting results from Xu et al. (2023b) on the selected 108 tasks.
Direct (Xu et al.)
39.6
Program Only (Ours)
61.1
Full (Ours)
73.1
Program Only. We directly prompt GPT-4 to output Python programs given the training examples. We gen- erate 80 programs for each task and select the program that passed most training examples.
Table 3: Experimental results ID-ARC. Program and hypothesis generation both con- tribute performance improvements.
Full. We first generate 16 different language hypothe-
ses, then generate 4 programs for each, resulting in 64 programs per problem.
We summarize our results in Table 3. Generating hypotheses and implementing programs significantly improves the performance on ID-ARC compared with the direct prompting method.
3.4 SYGUS
Settings. We evaluate all 89 tasks from the SyGuS dataset. Unlike ARC and ID-ARC datasets, we follow the convention in the program synthesis literature and treat all examples training. Accuracy is computed by whether program passes all training examples.
Method
Accuracy (%)
CrossBeam (Shi et al.) Program Only (Ours)
74.8
94.3
Full (Ours)
94.3
Table 4: Experiment results on SyGuS. Our directly generated programmatic hypotheses and natural--anguage-condiii matic hypotheses perform similarly.
Results. We find that GPT-4 can generate correct pro- grams for 94.3% of the SyGuS tasks using programs with two rounds of feedback without hypothesis generation, demonstrating strong performance in a direct program generation approach. Of the five remaining tasks, we find that three of the tasks have mistakes in their examples. As a result, when using natural language hypotheses to guide the code generation process, GPT-4's performance does not meaningfully change, achieving the same performance 94.3% by generating 4 hypotheses and implementing 2 program for each hypothesis. As a comparison, the state-of-the-att program induction approach CrossBeam (Shi et al., 2022) can solve 74.8% of the dataset using a the state-of sfate-of-the-an
program-
language with 50K program candidates. For reference, the-art art DSL-b baseline CrossBeam only achieves an accuracy of 74.8 on this dataset.
3.5 LIST FUNCTIONS
Method
Accuracy (%)
For this dataset, we sample 100 tasks from it for eval- uation. Empirically we found that on this dataset, a correct language hypothesis almost always leads a correct Python implementation. therefore our Full pipeline will generate 64 hypotheses and implement one Python program for each hypothesis. And the program only ablation will generate 64 programs for each task. The results summarized in Table 5, Our method consistently outperforms baselines.
Direct
31
Program Only (Ours)
Full (Ours)
69
Table 5: Experiment results on List Func- tions. Code and language generation both contribute to performance improvements.
DISCUSSION
4.1 FAILURE CASES
Currently, there are two types of failures our pipeline. First, the model may be unable to generate correct and sufficiently precise natural language hypothesis. Second, the model can still generate incorrect programs given correct hypothesis.
Hypothesis Generation. Hypothesis generation is especially chal- lenging for the ARC dataset involves recognizing visual patterns in 2D grids. While we observe that GPT-4 has primitive ability to recognize points, lines, and rectangles, and to identify repetition and symmetry relationships, it has trouble understanding more complex shapes and visual relationships like translation, scaling, and contain- ment. This is unsurprising GPT-4 is trained primarily as text in our experiments. Furthermore, we observe that GPT-4 has difficulty proposing reasonable hypotheses for very large grids, possibly due to the limited context length. In contrast, GPT-4 was
Tisk 44480108
Tack 353442o0
Figure 4: Two examples where GPT-4 has difficulty implementing programs even with correct hypotheses.
text corpora, and the visual grid is input
7

---

Published as a conference paper at ICLR 2024
quite good at hypothesis generation on ID-ARC. While the concepts may be easier for this dataset it is certainly the case that the visual encoding is easier. We thus tentatively suggest that current LMs are non-trivially capable of hypothesis generation for inductive learning and anticipate that vision-language models (Driess et al., 2023) may close the remaining gap for visual tasks like ARC.
Program Generation. Even with correct hypotheses, difficulties may arise when the task hard to implement in Python. For example, task 44 444811d8 180188 shown in Figure 4 was one where the language model failed when given a correct hypothesis. The task is difficult to solve programmatically. even for humans, as it requires identifying an irregular shape and then filling it according an irregular pattern. This suggests a limitation of using generic Python programs for solving visual inductive reasoning tasks. Natural language hypotheses may also contain ambiguous concepts that mismatch the biases of the program generator. The human-written hypothesis for task 3 36344 444444 2ee in Figure 4 is: "In the input, you should see color pattern on the left side and blue squares on the right. The output grid size same size as the input. To make the output, you have to use the blue square as the middle square and recreate the same pattern replacing the blue square with the same color in the middle as the pattern." GPT-4 is unable to understand what "color pattern" refers to and generates an incorrect program by treating the first three columns as the pattern. On the other hand, GPT-4's generated hypothesis mentions that "In the input, you should see 3x3 colored square on the left side...", ", which yields the correct Python implementation. Thus a good match is needed between hypothesis generator and program synthesis, suggesting dircetions for future work.
4.2 CONSIDERING EVERY CANDIDATE HYPOTHESIS.
Currently, our pipeline does not consider many candidate hypotheses; we note that this is not a theoretical limitation of our method. In our experiments, we found that when the generated program passes all training cases, it almost always passed the test case (we only observe single task that is an exception). Therefore, the performance of human-selected hypotheses can reasonably be treated as a lower bound for the performance if we consider every candidate hypothesis. However, we need to sample large number of (64) hypotheses to have reasonable hit rate of correct ones, and testing a single candidate hypothesis can take up to 1.55 (8 programs with two rounds of feedback) - leading us evaluate summarizing and human filtering. This suggests that the effectiveness of our method will improve automatically as the inference cost of language models decreases.
4.3 COMBINATORIAL SEARCH WITH PARSEL
We also explore the application of Parsel, an efficient compositional program generation method (Zelikman et al., 2023), in combination with GPT-4 to enhance the model's ability to generate and evaluate code implementations. This approach aims to capitalize on the benefits of compositional reasoning in problem-solving by first decomposing a solution, generating multiple implementations of each part of the solution, and then searching over combinations of the implementations. This allows for many more programs to be tested with fewer LLM calls. For human- -written hypotheses, this improved performance to 47.5%, but for language-model moollgge-mdll--gnertteeedd hypotheses it had the reverse effect. Details can be found in Appendix B.
5 RELATED WORKS
Inductive Reasoning. Techniques to allow automatic inductive reasoning have been widely studied by the artificial intelligence community as well as the program synthesis community. Given a set of observations, these efforts aim to computationally infer the underlying rules for a set of observations that can be generalized to novel scenarios. Traditional methods usually rely on programs written in manually designed domain-specific languages to represent the rule space and perform searching on the space to obtain the desired program. A number of heuristics have been proposed to speed up the search process. BUSTLE (Odena al., 2020) proposes a neural search algorithm that takes the intermediate results of partial programs into account during the search process. Dreamnoder (Ellis et al., 2023) introduces a wake-sleep algorithm that will dynamically build library functions on top of the primitive operations for solving more complex tasks with less running time. These methods typically require training on a corpora of related tasks, and cannot generalize across different domains due to the limited DSL. Earlier work in this area showed that introducing linguistic knowledge and selecting relevant language descriptions allows for better classifiers (Andreas et al., 2018). Recently, multiple works (Mirchandani et al., 2023; Gendron et al., 2023) tried to evaluate large language models on inductive reasoning tasks. These works directly prompt models to predict the output given the novel input as well training examples, which leads poor performance. Our work draws inspiration
8

---

Published as a conference paper at ICLR 2024
from previous program synthesis literature use programs as representations of the underlying rules. But we instead leverage a general programming language Python, which makes our method applicable to wide range of different domains such as grid transformation and string transformation.
Reasoning with Programs. There has been consistent effort to introduce program representations into different types of reasoning tasks such as visual reasoning (Andreas et al., 2016; Mao et al., 2019) and question answering (Dong& & Lapata, 2016; Zhong et al., 2017). Naturally, these programmatic reasoning works build on prior work on generating programs with language models (Jacob & Tairas, 2010; Schulam et al., 2013; Kushman, 2015; Desai et al., 2016; Chen et al., 2021; Austin et al., 2021; Jain et al., 2022). Programs provide various advantages over end-to-end methods, such as interpretability. generalizability, and efficiency. Mainstream approaches have focused on learning to parse natural language questions into programs of domain-specific languages that can be executed to obtain the answer; a program executor often jointly learned to execute primitive functions (Andreas et al., 2016; Mao et al., 2019).
Recently, LLMs have been shown to be capable of generating programs written in general-purpont programming languages. This inspired multiple works leverage L.MMs reason with programmatic representations. Gao et al. (2022) introduced Program-Aided Language models (PAL), and Chen et al. (2022) proposed the "Program of Thoughts" (PoT) prompting, both of which prompt large language models to solve step-by-step math and symbolic reasoning tasks by proposing programs and offload the computation to Python interpreter. Visprog (Gupta Kembhavi, 2023) and ViperGPT (Surís et al., 2023) generated programs that can be executed using pretrained perception modules to tackle visual reasoning tasks. These approaches are superior in performance and require minimal data for in-context learning without the need for any training. Notably, the code generated by the models in these papers has primarily served as a computational aid, not a general task representation. In our case, programs serve testable hypotheses for solving inductive reasoning tasks.
Lastly, Clement et al. (1986) investigated the correlation between analogical reasoning ability and the programming skills of high school students, indicating significant relationship between the ability to perform analogical reasoning and write compositional programs. Given previously observed parallels between language model behavior and cognitive psychology experiments (c.g.. Dasgupta et al. 2022; Aher et al. 2022), language models may exhibit a similar trend.
6 LIMITATIONS AND FUTURE WORK
Currently, our method requires multiple LLM queries, which may be costly depending on the complexity of tasks. But, with the rapid improvement and decreasing costs, this allows for increasingly complex tasks to be solved at a given cost. There are also several promising directions for future work building these results. First, some tasks and objectives are inherently stochastic or challenging to express explicitly as a program - for these, supporting objectives besides exact match is essential (c.g.. ROUGE (Lin, 2004)) and may benefit from leveraging from code that leverages other machine learning models (e.g., VisProg (Gupta & Kembhavi, 2023) for visual tasks). However, Python is already notably more expressive than the DSLs that were standard prior work on program synthesis (Devlin et al., 2017; Ellis et al., 2019; Sharma et al., 2017; Guu et al., 2017).
Lastly, although we observed a low false-positive rate on our datasets (i.e., if a working program was found, it almost always generalized), other inductive reasoning tasks may require further work to avoid calst-oossivves. Under the assumption of a low false-positive rate, which we empirically observed. our method is approximately the same as importance sampling in a hierarchical Bayesian model, where the importance distribution is that of the language model conditioned on the examples. This could potentially guide future work toward more efficient algorithms.
7 CONCLUSIONS
In this work, we propose a pipeline that facilitates better inductive reasoning in large language models. The core idea is to first prompt LLMs to generate hypotheses of the underlying rule in natural language, to then implement the hypotheses as Python programs, and to search for programs which can be verified on the training examples and executed on novel inputs for inference. We evaluate the effectiveness of our pipeline on four challenging datasets Abstraction and Reasoning Corpus (ARC), its variant ID-ARC, a string transformation dataset SyGuS, and List Functions dataset. Our pipeline outperforms the baseline methods by large margin all four datasets.

---

Published as a conference paper at ICLR 2024
8 ACKNOWLEDGEMENTS
This work supported in part by the Microsoft Accelerate Foundation Models Research program, National Science Foundation Grant No. 2302701, and NSF Expeditions Grant No. 1918771. Gabriel Poesia is supported by Stanford Interdisciplinary Graduate Fellowship.
REFERENCES
Sam Acquaviva, Yewen Pu, Marta Kryven, Theodoros Sechopoulos, Catherine Wong, Gabrielle Ecanow, Maxwell Nye, Michael Tessler, and Josh Tenenbaum. Communicating natural programs to humans and machines. Advances in Neural Information Processing Systems, 35:3731-3743, 2022.
Gati Aher, Rosa I Arriaga, and Adam Tauman Kalai. Using large language models to simulate multiple humans. arXiv preprint arXiv:2208. 10264, 2022.
Jacob Andreas, Marcus Robrbach, Trevor Darrell, and Dan Klein. Learning to compose neural networks for question answering. In NAACL, 2016.
Jacob Andreas, Dan Klein, and Sergey Levine. Learning with latent language. ACI., 2018.
Jacob Austin, Augustus Odena, Maxwell Nye. Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie Cai, Michael Terry, Quoe Le, et al. Program synthesis with large language models. arXiv preprint arXiv: 077332, 2021.
Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, et al. Evaluating large language models trained on code. arXiv preprint arXiv:2/07.03377 2021.
Wenhu Chen, Xueguang Ma, Xinyi Wang, and William W Cohen. Program of thoughts prompt- ing: Disentangling computation from reasoning for numerical reasoning tasks. arXiv preprint arXiv:2211. 12588, 2022.
Xinyun Chen, Maxwell Lin, Nathanael Schärli, and Denny Zhou. Teaching large language models to self-debug, arXiv preprint arXiv:2304.05128, 2023.
François Chollet. On the measure of intelligence. arXiv preprint arXiv: 19X1v:1911.01547, 2019.
Catherine A Clement, D Midian Kurland, Ronald Mawby, and Roy D Pea. Analogical reasoning and computer programming. Journal of Educational Computing Research, 2(4):473-486, 1986.
Ishita Dasgupta, Andrew K Lampinen, Stephanie CY Chan, Antonia Creswell, Dharshan Kumaran, James L McClelland, and Felix Hill. Language models show human-like content effects on reasoning. arXiv preprint arXiv:2207.0705/ 2022.
Aditya Desai, Sumit Gulwani, Vineet Hingorami, Nidhi Jain, Amey Karkare, Mark Marron, and Subbajit Roy. Program synthesis using natural language. In Proceedings of the 38th International Conference on Software Engineering, pp. 345-356, 2016.
Jacob Devlin, Jonathan Uesato, Surya Bhupatiraju, Rishabh Singh, Abdel-rahman Mohamed, and Pushmeet Kohli. Robustfill: Neural program learning under noisy i/o. In International conference on machine learning. pp. 990-998. PMLR, 2017.
Li Dong and Mirella Lapata. Language logical form with neural attention. In ACL., 2016.
Danny Driess, Fei Xia, Mehdi SM Sajjadi, Corey Lynch, Aakanksha Chowdhery, Brian Ichter, Ayzaan Wahid, Jonathan Tompson, Quan Vuong, Tianhe Yu, et al. Palm-e: An embodied multimodal language model. In ICML, 2023.
Kevin Ellis. Maxwell Nye, Yewen Pu, Felix Sosa. Josh Tenenbaum, and Armando Solar-Lezama Write, execute, assess: Program synthesis with repl. Advances in Neural Information Processing Systems, 32, 2019.
10

---

Published as a conference paper at ICLR 2024
Kevin Ellis, Lionel Wong, Maxwell Nye, Mathias Sable-Meyer, Luc Cary, Lore Anaya Pozo, Luke Hewitt, Armando Gelar-Lezama, and Joshua B Tenenbaum. Dreamcoder: growing generalizable, interpretable knowledge with wake-sleep bayesian program learning. Philosophical Transactions of the Royal Society A, (2.11225)) 2023.
Luyu Gao, Aman Madaan, Shuyan Zhou, Uri Alon, Pengfei Liu, Yiming Yang, Jamie Callan, and Graham Neubig. Pal: Program-aided language models. arXiv preprint urXiv:2211. 1.:/22/11.0444 10435, 2022.
Gaël Gendron, Qiming Bao, Michael Witbrock, and Gillian Dobbie. Large language models are not abstract reasoners. arXiv preprini arXiv:2305. 2023.
Noah D Goodman, Joshua B Tenenbaum, Jacob Feldman, and Thomas L Griffiths. A rational analysis of rule-based concept learning, Cognitive science, 32(1):108-155) 2008
Noah D Goodman, Tomer Ullman, and Joshua B Tenenbaum. Learning a theory of causality. Psychological review, 11 10, 2011.
Sumit Gulwani. Automating string processing in spreadsheets using input-output examples. ACM
Sigplan Notices, 46(1): 46(1):317-330, 2011.
Tanmay Gupta and Aniruddha Kembhavi. Visual programming: Compositional visual reasoning
without training. CVPR, 2023.
Kelvin Guu, Panupong Pasupat, Evan Liu, and Percy Liang. From language to programs: Bridging reinforcement learning and maximum marginal likelihood. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics ( (Volume I: Long Papers), pp. 1051-1062, 2017.
Charles R. Harris, K. Jarrod Millman, Stéfan J. van der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathamiel J. Smith, Robert Kern, Matti Picus, Stephan Hoyer, Marten H. van Kerkwijk, Matthew Brett, Allan Haldane, Jaime Fernández del Río, Mark Wiebe, Pearu Peterson, Pierre Gérard-Marchanl Warren Weckesser, Hameer Abbasi, Christoph Gohlke, and Travis E. Oliphant. Array programming with NumPy, Nature, 585(7825) September 2020. doi: 10.
Kevin Sheppard, Tyler Reddy,
URL https::////.. //oi
1038/ 41586 020-6-00002222222222222222229990
Icecuber. Abstraction and rasoning challenge 1st place solution. 2020. URL https:// :// www. www.kagggll....... wtt.:/occcccoooo http://tttttttiioooocoeeooootttt www.:/oonn.asstttattt.caoe and reasoning-chhllleggee
discussicn/15455 1545977.
Ferosh Jacob and Robert Tairas. Code template inference using language models. In Proceedings of the 48th Annual Southeast Regional Conference, pp. 1-6, 2010.
Naman Jain, Skanda Vaidyanath, Arun Iyer, Nagarajan Natarajan, Suresh Parthasarathy, Sriram Rajamani, and Rahul Sharma. Jigsaw: Large language models meet program synthesis. In Proceedings of the 44th International Conference on Software Engineering, pp. 1219-1231, 2022.
Aysja Johnson, Wai Keen Vong, Brenden Lake, and Todd Gureckis. Fast and flexible: Human program induction in abstract reasoning tasks. In Proceedings of the Annual Meeting of the Cognitive Science Society, 2021.
Nate Kushman. Generating computer programs from natural language descriptions. PhD thesis, Massachusetts Institute of Technology, 2015.
Andrew K Lampinen, Ishita Dasgupta, Stephanie CY Chan, Kory Matthewson, Michael Henry Tessler, Antonia Creswell, James L McClelland, Jane X Wang, and Felix Hill. Can language models learn from explanations in context? arXiv preprint arXiv:2204.02322 2022.
Vu Lc, Daniel Perelman, Oleksandr Polozov, Mohammad Raza, Abhishek Udupa, and Sumit Gulwani. Interactive program synthesis. arXiv preprint arXiv: TXXiv:/703.035555 03539, 2017.
Chin- Yew Lin. Rouge: A package for automatic evaluation of summaries. Text summarization branches out, pp. 74-81, 2004.
11

---

Crossbeam: Learning search in Published as a conference paper at ICLR 2024
Jiayuan Mao, Chuang Gan, Pushmeet Kohli, Joshua B Tenenbaum, and Jiajun Wu. The neuro- symbolic concept learner: Interpreting scenes, words, and sentences from natural supervision. In ICLR, 2019.
Ana Marasović, Beltagy, Doug Downey, and Matthew E Peters. Few-shot self-rationalization with natural language prompts. arXiv preprini arXiv:2111.088 2021.
Suvir Mirchandani, Fei Xia, Pete Florence, Brian Ichter, Danny Driess, Montserrat Gonzalez Arenas, Kanishka Rao, Dorsa Sadigh, and Andy Zeng. Large language models as general pattern machines. arXiv preprint MNNi::337.0072// 2023.
Maxwell Nye, Anders Johan Andreassen, Guy Gur-Ari, Henryk Michalewski, Jacob Austin, David Bieber, David Dohan, Aitor Lewkowycz, Maarten Bosma, David Luan, al. Show your work: Scratchpads for intermediate computation with language models. arXiv preprint arXiv:2112.00114, 2021.
Augustus Odena, Kensen Shi, David Bieber, Rishabh Singh, Charles Sutton, and Hanjun Dai. Bustle: Bottom-up program synthesis through learning-guidee guided exploration. arXiv preprint arXiv:2007.14388 2020.
Nancy Pang. Deep learning for code repair. University of British Columbia, 2018.
Charles Peirce. Questions concerning certain faculties claimed for man. The Journal of Speculative Philosophy, 2(2):103-114, 1868.
Md Mostafizer Rahman, Yutaka Watanobe, and Keita Nakamura. A bidirectional Istm language model for code evaluation and repair. Symmetry, 13(2):247, 2021.
Nazneen Fatema Rajani, Bryan McCann, Caiming Xiong, and Richard Socher. Explain yourself! leveraging language models for commonsense reasoning. ACL, 2019.
Joshua S Rule, Joshua B Tenenbaum, and Steven T Piantadosi. The child hacker. Trends in cognitive sciences, 24(1 (4(11))900-911 2020.
Peter Schulam, Roni Rosenfeld, and Premkumar Devanbu. Building statistical language models of code. 2013 1st International Workshop on Data Analysis Patterns Software Engineering (DAPSE), pp. 1-3. IEEE, 2013.
Eric Schulte, Stephanie Forrest, and Westley Weimer. Automated program repair through the evolution of assembly code. In Proceedings of the 25th IEEE/ACM International Conference on Automated Software Engineering, pp. 313-316, 2010.
Gopal Sharma, Rishabh Goyal, Difan Liu, Evangelos Kalogerakis, and Subhransu Maji. Csgnet: Neural shape parser for constructive solid geometry. 2018 ieee. In CVF Conference on Computer Vision and Pattern Recognition, pp. 5515-5523 2017.
Kensen Shi, Hanjun Dai, Kevin Ellis, and Charles Sutton. bottom-up program synthesis. In ICLR, 2022.
Vered Shwartz, Peter West, Ronan Le Bras, Chandra Bhagavatula, and Yejin Choi. Unsupervised commonsense question answering with self-talk. In EMNLP, 2020.
Didac Surís, Sachit Menon, and Carl Vondrick. Vipergpt: Visual inference via python exccution for reasoning. arXiv preprint arXiv:2303.08128 2023.
Joshua B Tenenbaum, Thomas I. Griffiths, and Charles Kemp. Theory-based bayesian models of inductive learning and reasoning. Trends cognitive sciences, 10(7):309-318 2006.
Joshua B Tenenbaum. Charles Kemp, Thomas L Griffiths, and Noah D Goodman. How to grow mind: Statistics, structure, and abstraction. science, 33 13166)2)):129911135 2011.
Marko Vasic, Aditya Kanade, Petros Maniatis, David Bieber, and Rishabh Singh. Neural program repair by jointly learning to localize and repair. arXiv preprint arXiv: /904.0/720 2019.
12

---

Published as a conference paper at ICLR 2024
Edward Vul, Noah Goodman, Thomas L Griffiths, and Joshua B Tenenbaum. One and done? optimal decisions from very few samples. Cognitive science, 38(4):599 637,,,,996,, 2014.
Taylor Webb, Keith J Holyoak, and Hongjing Lu. Emergent analogical reasoning in large language models. arXiv preprint arXiv:2212.09196 2022.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Ed Chi, Quoc Le, and Denny Zhou. Chain of thought prompting elicits reasoning in large language models. arXiv preprint arXiv:2201.11900 2022.
Yudong Xu, Elias B Khalil, and Scott Sanner. Graphs, constraints, and search for the abstraction and reasoning corpus. In AAAI, 2023a.
Yudong Xu, Wenhao Li, Pashootan Vaezipoor, Scott Sanner, and Elias B Khalil. Lims and the abstrac- tion and reasoning corpus: Successes, failures, and the importance of object base representations. arXiv preprint arXiv:2305.
2023b.
Eric Zelikman, Yuhuai Wu, Jesse Mu, and Noah Goodman. Star: Bootstrapping reasoning with reasoning. In NeurlPS, 2022.
Eric Zelikman, Qian Huang, Gabriel Poesia, Noah D. Goodman, and Nick Haber. Parsel: Algorithmic reasoning with language models by composing decompositions, 2023.
Tianyi Zhang, Tao Yu, Tatsunori Hashimoto, Mike Lewis, Wen-tau Yih, Daniel Fried, and Sida Wang. Coder reviewer reranking for code generation. In ICML, 2023.
Victor Zhong, Caiming Xiong, and Richard Socher. Seq2sql: Generating structured queries from natural language using reinforcement learning. arXiv preprint arXiv:1709.00/00: 2017.
Hattie Zhou, Azade Nova, Hugo Larochelle, Aaron Courville, Behnam Neyshabur, and Hanic Sedghi. Teaching algorithmic reasoning via in coneont learning. arXiv preprint 1.Xiv:2211.09066 2022.
13

---

Published as a conference paper at ICLR 2024
A EXPERIMENT DETAILS
Prompts and Hyperparameters. For hypothesis generation, The prompts are shown in Figure A.8, Figure A. 10 and Figure A.11. We set the temperature to be 1.0 and the maximum number of tokens in response to be 200. For program generation and execution feedback, ture of 0.7 and set the maximum number of tokens to be 1000. Throughout the experiments, we opt-4-0613 and gpt-3. wwuuubo-031111 Earlier results used gpt-4-031 which include in Appendix C.
tempera-
80
Fill
Prog Only
Prog Only
70
Acc (%)
Acc (3)
55-
40
2
10
144
16
8
24
32
40
56
644
Programs per Hypothesis)
Progr per Hypothesis]
(a) Results on ID-ARC
(b) Results on Functions.
Figure A.5: Accuracy of our methods with varying numbers of hypotheses and programs.
Execution Feedback. After obtaining programs from language models, we directly execute them on training examples. If there are no programs passing all training examples, we prompt the language model again with the first example that the program fails pass, and ask correct the program. To save cost for experiments on ARC where we generate more than 64 programs, we do not run execution feedback on every program. Instead, we cluster programs by their output on the training examples. Only one program is selected from each cluster for feedback execution.
B ADDITIONAL RESULTS AND DISCUSSIONS
B. MORE ABLATIONS
Ablation on the Number of Hypotheses & Programs. First, we show the percentage of tasks that have correct hypothesis when we increase the number of samples in Figure A. Increasing the sample size will lead to steady improvement, although the slope is flattening. We also report how the accuracy changes when vary the number of hypotheses for each task on ARC-ID and List Func, fixing the number of programs for each hypothesis. For both datasets, our pipeline and the program-only ablation will steadily gain performance improvement as the number of samples increases, as shown in Figure A.5.
with hpputhisss
0.40
6:35
0.30
Number Sam Eppotheses
Figure A.6: Percentage of tasks with correct hypothesis when we increase the number of hypotheses sampled for the ARC experiment.
Zero-shot Hypothesis Generation. Here, we explore the effect of examples for hypothesis generation. On ID-ARC, we remove all the example tasks in the prompt while still generating 16 hypotheses and programs for each hypothesis. This gives an accuracy of 71.3%.
which is little worse than the performance with two-shot prompting 73.1 73.1%. 1%.
B.2 GPT-3.5
In this ablation, we leverage GPT-3.5 instead GPT-4 in our pipeline.
ARC. Compared with GPT-4, find GPT-3.5 mostly generates meaningless hypotheses given the inputs from ARC. We then test GPT-3.5's ability to generate program implementations when given the humtn-written hypotheses. Because GPT-3.5's context length is only 4096 tokens (GPT-4, which
14

---

Published as a conference paper at ICLR 2024
ID-ARC
SyGuS
List Func
Direct
25.9
N/A
16
Program Only (Ours)
23.1
80.9
46
Full (Ours)
26.9
86.5
57
Table A.I: Accuracy GPT-3.5 on ID-ARC, SyGuS and List Functions datasets.
for most of our experiments, has context length of 8192), only 33 tasks can fit into the prompt. Therefore, we treat the problems that do not fit in the context window as incorrect and do not leverage execution feedback. GPT-3.5 achieves accuracy of 27% with 128 programs when given human-written hypotheses. Using a 1 16384 context length version of GPT 3.5 boosts the performance 30%. This is still worse than GPT-4, but GPT-3.5 is approximately 20 times cheaper than GPT-4, This shows a trade-off between the performance and cost when choosing base models.
Other datasets. We continue to evaluate GPT-3.5 on other three datasets, where we found that GPT-3.5 have reasonable performance for both hypothesis generation and program generation. Therefore we keep the same setting and rerun all experiments with gpt 1ontt-3.52 5-5-613 The results are summarized in Table A.I. For ID-ARC, each hypothesis: for SyGuS, we generate hypotheses and implement 2 programs for each hypothesis with two rounds of feedback; for List Functions, we generate 64 hypotheses and program for each hypothesis. All program-only ablation generates the same number of programs in total. We can observe that our method also effective on GPT-3.5 on wide range of domains.
generate 16 hypotheses and implement 8 programs for
B.3 PARSEL FOR PROGRAM GENERATION
To enhance the performance of program generation, we also adapt a recently proposed method Parsel (Zelikman et al., 2023) to our settings. Instead of directly generating programs, we first generate an intermediate pseudocode program written in Parsel language from given hypothesis, as shown in Figure A.7. The Parsel language specifies the functions needed to be implemented by specifying the function name, arguments and its desired behavior in natural language. Then the Parsel program is passed to language model for implementing individual functions.
To allow functions to be implemented with knowledge of their context, unlike the original Parsel paper, we implement all functions needed in a single API call. We then sample multiple trials and extract multiple implementations of each function specified in the Parsel program. Then we will recombine every implementation each function to generate multiple programs. Using human- written hypotheses,
achieve accuracy of 47.5% the 40 randomly selected questions from ARC by generating 4 Parsel Programs for each hypothesis and 8 programs for each Parsel program without any feedback, surpassing the 37.5% accuracy obtained by directly generating programs from hypotheses. However, we found that this yields worse performance with -.L--reeerttdd hypotheses: on the 13 selected tasks that GPT-4 can generate correct hypotheses, directly generating programs with round of execution feedback yields an accuracy of 92% while Parsel programs x 8 python programs with round of feedback only yields an accuracy 69%. We suspect that this is due to Parsel introducing new level of abstraction into our pipeline: given that error might accumulate during the transformation between different levels of abstraction, Parsel increases the probability of generating incorrect final programs. We believe leveraging better code generation techniques is promising direction to improve our pipeline.
B.4 PILOT EXPERIMENTS AND HON-SYSTEMATIC FINDINGS
Specifying the Python Types of Matrices for Grids in ARC. In the prompt we use for ARC, we in- dicate the grids are represented NumPy arrays using Python type hint (numpy .ndarray [int]] The typing hint plays an important role in generating programs from language hypotheses, since it encourages LLMs to leverage NumPy functions that are suited for grid transformation, such as flipping, 2D iodexnng. If we change the typing hint to List [List [int]] J. LLMs will no longer error-prone.
leverage this library function, which makes the program longer and more error- prone. Using human- written hypotheses, programs and one round of execution feedback. GPT-4 can only achieve 32.5%, compared with the 37.5% performance the using NumPy array signature.
15

---

Published as a conference paper at ICLR 2024
Using LLMs to Rank Hypotheses. We also explore use LLMs to rank language hypotheses to throw away bad hypotheses. This is inspired by Zhang et al. (2023), which reranks code generated from description based its probability of generating the description. Because GPT-4 does not expose the log-probabilities of its generated items, and there is no clear way to extract the GPT-3 rerank the hypotheses generated by GPT-4 by looking at their probabilities of generating the input-output examples, given the hypothesis. We evaluate this ranking method on the 21 tasks where GPT-4 is able generate correct language hypothesis from 64 candidates. After the ranking, there are only 10 tasks where the correct hypotheses are placed in the top candidates. This prevents from reducing the hypotheses needed to implement without sacrificing the overall performance.
log-probabilities of the hypotheses,
instead
High-Levve Representations of ARC Grids. We observed that many for many tasks in ARC, it is easy for L.MSs come up with reasonable hypotheses if the grids are parsed into useful geometric representation, such irregular shapes, diagnoal lines. As result, explored the possibility of using alternative geometric representations, similar to concurrent work (Xu et al., 2023b). In particular, we attempted to treat each grid the result of sequence of shape placements, for example:
Blue Rectangle: (0, 2) size: (4, 5)
Black Line: (2, 4) 4)-> (5,
Red Points: (7,, 4), (8, 4), (9, 4)
We implemented an algorithm to identify the shortest possible sequence of shape placements that would result the observed grid. While we observed that this allowed the model to propose more reasonable hypotheses for subset of the problems, it harmed performance more of them. This is due in part to the inherent difficulty of proposing a useful general representation for ARC tasks.
Potential Data Memorization. While large language models have shown remarkable performance numerous benchmarks, there recurring concerns about whether these models have simply memorized the answers due to observing the problems during training, instead of actually solving the desired tasks. This is particularly true for closed-source models where details of the training set are not publicly available, such as GPT-4. Since the ARC (as well as the LARC dataset with human--ritte hypotheses) and SyGuS datasets are publicly available on the internet, there is possibility that GPT-4's 's training data contains these datasets, which might affect how we interpret these results. While differentiating between memorization and generalization for these close-sourced models remains an open problem, there are few pieces of evidence that show the effectiveness of our method. First, as far Python programs. Second, we tried prompting GPT-4 with some examples in a task and asked it to output other examples the same task, and GPT-4 failed to so. Third, the substantial boost of our full pipeline over the direct prediction bascline cannot be simply explained by data memorization.
know, there are no public attempts to solve ARC or SyGuS datasets with
16

---

Published as a conference paper at ICLR 2024
C RESULTS WITH GPT-4-0314
We initially
experiments with GPT-4-0314. Later, due partially to its deprecation, and partially due to a change in our available compute resources, we reran our experiments with GPT -4-0613. 3. We include the original result tables here for reference. All the conclusions remain consistent when we scale up the experiments.
Method
Accuracy (%)
Direct
12.5
Program Only
17.5
Summarized Hypo.
27.5
Hypo.
37.5
Human-W Written Hypo.*
37.5
Table A.2:
Results of the baseline and variants of our method on the randomly selected 40 tasks from ARC. Our method outperforms baselines with without human supervision.
Method
Accuracy (%)
Direct (Xu et al.)
38.8
Program Only (Ours)
58.3
Full (Ours)
77.8
Table A.3: Experiment results on ID-ARC. Program and hypothesis generation both con- tribute to performance improvements.
Method
Accuracy (%)
CrossBeam (Shi al.)
74.8
Program Only (Ours)
94.3
Full (Ours)
93.2
Table A.4: Experiment results SyGuS, Our directly generated programmatic hypotheses and natural-lan language wegggaagenniiiioneedeeeeeeeeeeed program- matic hypotheses perform similarly.
17

---

Published as a conference paper at ICLR 2024
Summarized Hypothesis and its Corresponding Generated Parsel Program and Python Program
To make the oulput, extract the colored shape(s) from the input grid, expand duplicate them according
specified pattern, and place resulting shape(s) into the output grid.
transform grwatinpct Extract Eiqure from input geid and create outpuc grid
--xxcsact figure (inpat_ at orid): Identity the non-zero eiemente in the iapuz grid and their pesition -crcato_outpur_griiee iriaitgurr Create 3x6 grid and copy the riquze two times into it
extract Higure Hapur -
positione np.erguhere (ingut. grld
return inpat_ grid zero positions.a in (exiaw)) [0] snon, posit fone mexiaxi x-03 [0] non_zero_poxt ions.nin (axis=0) [3] zerro lons max moweeaiii s-0) [1] 1]
del cooll_oouputggraadiig
grid rp.rerosi b1, stspe=int)
grid ifigure.shapp 11] = figure
output_grrid griddgr s, Stggiuueeeee
Figure
10
reluen dulpu geid
11 del CzanaCorn indaaaa-rdi
12
extracted, Eigare extract, Higure Hipput grid)
13
create output gext raxted Figure!
14
return output_grid
Figure A.7: An ARC example of generated hypotheses using Parsel (Zelikman et al., 2023) using the same task as Figure 3.
18

---

Published as a conference paper at ICLR 2024
Prompt Hypothesis Generation
[Role: system]
You will be given a input-output pairs. Each input and output a grid numbers representing representing a visual grid. There a SINGLE pattern that transforms each input grid to the correpondingg output grid.
The pattern may involve counting sorting objects (e.g. sorting by size), comparing numbers (c.g. which shape symbol appears most? Which is the largest object? Which objects the same size?), or repeating pattern for fixed number time.
There are other concepts that may be relevant.
Lines, rectangular shapes
Symmetries rotations, translations.
Shape upscaling or downscaling, elastic distortions.
Containing being contained being inside or outside of perimeter.
Drawing lines, connecting points, orthogonal projections.
Copying, repeating objects.
You should treat black cells empty cells (backgrounds).
The number
input grid can mapped the following colors:O:black; 1:blue: 2:red; 3:green;
4:yellow; S:gry; 6:fuschia; 7:orange; 8:teal; 9:brown Output the language description of the transformation.
[Role: user]
Case 0:
Input:
[[3 8]
[3 7 0]
OJ]
Output:
[[O SJ
[0 3]
[8
Case I:
Input:
[[S 5 2]
[1 01
[000]]
Output:
[[O 0
[001] 1]
5]
[Role: assistant]
Describing the input grid: In the input, should see a black grid with a colored shape Describing the size of the output grid: The output grid size the same the input grid
Describing how to transform the grid: make the output, you to rotate the whole grid two times. Imagine that the entire grid has been flipped vertically and horizontally.
[Role: user]
Case 0:
Input:
[[O 0
[0001] 1]
[1010]
[0001]
[4444]
[02022]
[0002
[
[2 2 0]]
Output:
IIO 0
[0000]
[0033]
[3 3.333
Figure A.8: The prompt used to generate the hypotheses. Continued in Figure A.9. We use the Chat completions API, where every prompt consists of list of messages representing a conversation. Each message contains text and role indicating the agent producing the text.

---

Published as a conference paper at ICLR 2024
Case I:
Input:
[[1 [00]
0]000
[110]
[0 0]
44444]
[0
[2002]]
[2 [
2]]
Output:
[[3 0 3]
[0
[00
330
Case 2:
Input:
[[O 0
[101]]
[1 1110
[I 11101
[444]
10000]
[0202]
[2 21
[02 O]]
Output:
[3 3 0]
[O O 3
[3 0 03]
Case 3:
Input:
[[1 0 1]
[000 1]
[1 [1100]
[0011]
44444
[0222]
[0222]
[2
[
Output: [[3 0
[0 3
[0 3333
[3 0
[Role: assistant]
Describing the imput grid: In the input, you should 4x4 square of blue and black boxes top of yellow line. Below the yellow line 4x4 square red and black boxes.
Describing the size of the output grid: The output grid size should be 4x4. Describing how to transform the grid: To make the output, you have to compare the squares in the top and bottom 4x4 square. If they match (both black both color) make the output square black. they do not match, make the output square green.
[Role: user]
Case 0:
<Training examples the task to solved>
Figure A.9: The prompt used to generate the hypotheses (First half Figure A.8).
20

---

Published as a conference paper at ICLR 2024
Prompt for Program Implementation
[Role: User]
Example 0:
Input:
[00000000]]
1088000001
100800000]
108880000]
[00000000]
[00000000]
[00000000]
[00000000]
Output:
[[8 [8880880
00
88888888 811
Example I:
Input:
[00000000]]
[00000000]
[00000000]
[00000000]
[00000000]
[00020000]
[00222000]
[00220000]]
Output:
[
2222 2]
[2 2 2 0]]
Example 2:
Input:
[00000000]]
[00000110]
[00001000]
[00000100]
[00000000]
[00000000]
[00000000]
1000000001
Output:
[101101)
[100100]
[010010]]
Now, please write a python program transform grid(input grid: np.ndarray(int) -> np.ndarray [in]] that transforms the input grid to the corresponding output grid.
Hint: You may want to use the following guidance to implement the function:
Hint: You may want to use the following guidance to implement the function:
To make the output, extract the colored shape(s) from the input grid, expand or duplicate them according to the specified pattern, and place the resulting shape(s) into the output grid.
The number in the input grid can mapped the following colors:O:black; 1:blue; 2:red; 3:green;
4:yellow; S:grey; 6:fuschia; 7:orange; S:teal: 9:brown
Just reply with the implementation of transform grid(input grid: np.ndarraylnnt) in Python and nothing else, each cell in the output should only be numbers from 0 to 9.
Figure 1010: The prompt used generate the program given the hypothesis (bold in the text) for the same task as Figure 3.
21

---

Published as a conference paper at ICLR 2024
Prompt Hypothesis Summarization
[System]
You are genius solving language puzzles. [User]
Given a list of rules, categorize them into cight distinct categories based on their similaritics. For cach category, synthesize the rules into single, specific rule that combines the ideas of all rules in that category, while clearly differentiating from the other categories. The new rule should as specific as possible, following the format of the given rules. The new rule should be applicable without any information from the original rules i.c. it should be standalone.
Rules:
(Eypothesis 1
[Rypothesis 2
Figure A.11: The prompt used to summarize 8 hypotheses from 64 generated hypotheses.
22


Reviews:
[{"review_id": "t8tn2VO2W6", "reviewer": "Reviewer_qtss", "summary": "This paper proposes a pipeline to solve abstraction and reasoning tasks. The pipeline prompts LLMs to propose hypothesis about the problem, convert the hypothesis into executable programs, which is later validated against the ground truth outputs given inputs. Experiments on ARC, 1D-ARC, and SyGus demonstrates that the proposed pipeline is effective.", "questions": "- In Table 3, why are the names of the methods different from Table 1. Does \"Full\" in Table correspond to any method in Table 1?\n- For negative results presented in Sec. 3.4, I suggest to summarize them in a table as well.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The ablation studies are quite extensive. The authors dissect the effect of each component in the pipeline by, for example, skipping the program generation, skipping generation of natural language hypothesis. The performance improvement of the full pipeline is also clear.\n- The abundant technical details contribute to the reproducibility of the work.", "weaknesses": "- Which part of the pipeline is novel is not quite clear from the paper writing\n\nThe paper introduces every part the proposed pipeline in intensive details - but it is not quite clear which part of the pipeline is novel. I feel compared to earlier works like program-of-thoughts, the novel part is generating natural language hypothesis before program generation and a verification step to verify the correctness of hypothesis. I suggest adding a paragraph in introduction to highlight which parts are novel and the contributions of the work.\n\n\n- I feel some experiments, such as comparing the performance of GPT 3.5 and GPT 4 is not relevant to the main contribution of the paper. The numbers of these experiments can be moved to appendix to avoid distraction.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "AezMgMjCMI", "reviewer": "Reviewer_SPJ6", "summary": "The paper addresses the challenge of inductive reasoning in large language models (LLMs). Directly prompting by in-context learning may not be able to solve complex tasks. The authors propose a novel approach inspired by the Bayesian rule that involves generating explicit hypotheses in natural language and then translating them into concrete Python programs, which can be verified. This approach, tested on tasks like ARC, 1D-ARC, and SyGuS, significantly improves LLMs' performance. By combining abstract reasoning with programmatic logic, and filtering hypotheses through LLM summaries or human annotators, the method demonstrates substantial improvements, achieving up to 37.5% accuracy on ARC, compared to a 12.5% baseline. The paper highlights the synergy between natural language processing and programmatic approaches in enhancing LLM inductive reasoning.", "questions": "- Is there potential for the proposed method to be generalized across a broader array of tasks beyond those presented in the paper?\n- How might this method perform tasks that are inherently difficult or perhaps impossible to encapsulate within a programmable framework?\n- Could the authors clarify the missing elements in the appendix that might be pertinent to the paper's methodology or findings?\n- Regarding the ARC tasks, what is the average duration, and why do most exceed the 4096 token limit imposed by many LLMs?\n- The Direct Prompting baseline, is it just few-shot prompting or Chain-of-thought prompting?", "limitations": "", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The paper introduces a novel method of enhancing inductive reasoning in LLMs by generating explicit hypotheses and translating them into Python programs. This approach creatively combines the strengths of natural language processing and programmatic logic, offering a unique solution to the challenge of inductive reasoning in complex tasks.\n2. The paper stands out for its robust methodology and the quality of its experimental results. The authors thoroughly test their approach on challenging datasets like ARC, demonstrating significant improvements in LLM performance. The ablation studies further substantiate the quality of the research, clarifying the contributions of each component of the proposed method.\n3. The presentation is good with clarity, presenting complex ideas and methodologies in a comprehensible manner. This clarity enhances the paper's accessibility to a broad audience, which is crucial for disseminating innovative ideas.", "weaknesses": "1. While the method of generating and implementing hypotheses as Python programs is innovative, it may pose scalability challenges. For instance, generating a large number of hypotheses for complex problems could be computationally intensive and time-consuming. Moreover, the filtering process—whether automated or human-assisted—might not efficiently narrow down to the most effective hypotheses. To improve, the authors could explore more sophisticated algorithms for hypothesis generation that prioritize efficiency and scalability, possibly through more advanced heuristics or machine learning techniques.\n2. The paper demonstrates success in specific datasets like ARC, 1D-ARC, and SyGuS, but it's unclear how well this method generalizes to other types of inductive reasoning tasks, particularly those with differing structures or complexity levels, or even cannot be solved with python programs. Also, the baselines are limited only with direct prompting and ablated baselines, with no baselines from related works. In other words, the range of experimental tasks presented is somewhat limited, potentially restricting the scope of the paper’s conclusions.\n3. The hypothesis proposal and selection process is essentially a search problem. The proposed iterative sampling and verification process is costly and inefficient from the perspective of search. The authors could consider more advanced search methods, such as DFS/BFS/MSTC, etc. Get some inspiration from the recent tree search prompting literature, like Tree-of-thoughts, reasoning-via-planning, etc.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "rNfYkBo65M", "reviewer": "Reviewer_PFzt", "summary": "This paper presents the hypothesis search approach for inductive reasoning. Specifically, hypothesis search first generates multiple hypotheses on the shared transformation rule for the given input-output pairs. Afterward, a subset of hypotheses is selected by humans, or summarized by the LLM. Finally, the LLM generates the Python program given a hypothesis, and the program is executed on the input-output pairs to verify the correctness. They evaluate their approach on ARC, 1D-ARC and SyGuS. Using GPT-4, their approach outperforms the baselines that directly generate the answer or the Python program without hypothesis generation. In particular, they demonstrate that using hypotheses generated by GPT-4 achieves the same performance as using human-written hypotheses.", "questions": "1. What is the performance with different number of hypotheses?\n\n2. Make the comparison of sample size and token size among different methods clearer. Specifically, for hypothesis summarization, it is better to uniformly require the model to generate 8 programs for each of the 8 hypotheses for all problems, instead of only applying to 21 tasks, so that the sampling size is more comparable to the program prompting. Similarly, for human-selected hypotheses, it is unclear how many hypotheses are kept after filtering. It is better to always keep 8 hypotheses after filtering. In addition, it is unclear why the number of execution rounds varies for different methods. It is better to unify the setup for a fair comparison.\n\n3. For Table 2, have you tried gpt-3.5-turbo-16k, which has a longer context length? The performance may further improve.\n\n4. Please provide a quantitative analysis on the failure mode; i.e., the percentage of error cases where none of the hypothesis is correct, and the percentage of error cases caused by the wrong generated programs.\n\n5. Please provide the full prompt including the few-shot demonstrations. The appendix only contains the zero-shot prompt. What is the performance of zero-shot prompting? How much does adding 1 or 2 problems in the prompt affects the performance?\n\n6. The evaluation sets of ARC and 1D-ARC are too small. It is better to include at least 100 tasks.", "limitations": "", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. Inductive reasoning is an important and challenging problem. This work achieves a notable improvement on ARC and 1D-ARC, showing that combining both abstract hypothesis and concrete code is beneficial.\n\n2. The approach of hypothesis summarization is interesting. Also, it is an interesting finding that using GPT4-generated hypotheses achieves the same performance as using human-written hypotheses, demonstrating the promise of LLMs for generating high-quality hypotheses for inductive reasoning.", "weaknesses": "While the overall results are promising, a lot of important ablations and details are missing in the draft.\n\n1. What is the performance with different number of hypotheses? Specifically, in Table 1, it is important to know the performance with fewer number of initial generated hypotheses, such as 8. Comparing hypothesis summarization with directly generating 8 initial hypotheses can validate the importance of the hypothesis summarization stage.\n\n2. In Table 1, the comparison of sample size and token size among different methods is unclear. Specifically, for hypothesis summarization, it is better to uniformly require the model to generate 8 programs for each of the 8 hypotheses for all problems, instead of only applying to 21 tasks, so that the sampling size is more comparable to the program prompting. Similarly, for human-selected hypotheses, it is unclear how many hypotheses are kept after filtering. It is better to always keep 8 hypotheses after filtering. In addition, it is unclear why the number of execution rounds varies for different methods. It is better to unify the setup for a fair comparison.\n\n3. From Table 2, it is interesting to see that the final performance of GPT-3.5 is comparable to GPT-4. Have you tried gpt-3.5-turbo-16k, which has a longer context length? The performance may further improve.\n\n4. The findings on SyGuS are divergent from the main evaluation, as the best result is achieved with purely code generation.\n\n5. Please provide a quantitative analysis on the failure mode; i.e., the percentage of error cases where none of the hypothesis is correct, and the percentage of error cases caused by the wrong generated programs.\n\n6. Please provide the full prompt including the few-shot demonstrations. The appendix only contains the zero-shot prompt. What is the performance of zero-shot prompting? How much does adding 1 or 2 problems in the prompt affects the performance?\n\n7. The evaluation sets of ARC and 1D-ARC are too small. It is better to include at least 100 tasks.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "GEZ8MfiuHT", "reviewer": "Reviewer_Bu26", "summary": "This paper prompts LLMs to generate Python programs to solve symbolic pattern recognition problems. This may be better than letting the model directly predict answers. On Abstraction and Reasoning Corpus (ARC) where the inputs are 2D or 1D pixel grids, letting GPT-4 generate natural language hypotheses to then guide program generation improves the result. Hypothesis generation slightly harms the performance on SyGuS where the inputs are strings.", "questions": "1. Sec 3.2.2 says summarized hypotheses can often become vague and ambiguous. Will the hypotheses used to guide program generation be of higher quality if you let the model rank the hypotheses? You could analyze the recall@k, i.e., whether top k hypotheses contain a correct one.\n1. ARC: In Table 2, using human written hypotheses only has 37.5 accuracy. Does that mean LLM fails to write programs based on correct hypotheses? The statement at the end of page 5 that \"GPT-4 is pretty good at both generating hypotheses and realizing them as programs\" requires some more evidence or explanation.\n1. ARC: In Table 2, the accuracy with human-selected and human-written hypotheses are both 37.5. Does this mean model-generated hypotheses for each task almost always contain a correct one? Or is it the case that model-generated hypotheses sometimes have mistakes but, when correct, leads to better programs, and thus both 37.5? Can you evaluate the recall of model-generated hypotheses, either by some automatic metric or human evaluation?\n1. For ARC, why do you only consider top-1 accuracy but not top-3 as in the official evaluation? Can you compare your method with state-of-the-art methods on the task?\n1. What are the types of tasks that (1) program generation and (2) hypotheses search can be helpful? Can you summarize the features of such tasks? \"Inductive reasoning tasks\" is too general and abstract. To begin with, is it true that the method is applicable only to symbolic pattern recognition tasks?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper proposed to let GPT-4 generate programs to solve symbolic pattern recognition tasks. It shows that using natural language hypotheses to guide the program generation can be helpful on ARC, on which letting the model directly generate programs results in bad programs.\n1. The paper reports the limitation that on SyGuS where the model can directly generate programs, hypothesis guidance is not helpful.\n1. The presentation is clear and several findings are interesting.", "weaknesses": "1. The technical novelty is limited and the main challenge of generating high-quality programs is largely unsolved.\n2. The effectiveness of the proposed method of using hypotheses to guide program generation has unclear applicability. (1) GPT-3.5 fails to generate meaningful hypotheses. (2) GPT-4 hypotheses are not helpful on SyGuS where GPT-4 can directly generate good programs. (3) GPT-4 hypotheses are helpful on ARC, but ARC results are still only 37.5 with the hypotheses. Practitioners will have to develop alternative models that can better understand 2D geometry to solve the task and then natural language hypotheses may no longer be helpful as in SyGuS. (4) Model-generated hypotheses hurt the performance of Parsel, a compositional program generation method that can significantly  improve the performance when model-generated hypotheses are not used.\n3. Multiple questions need to be clarified; some requires experimental results. Please refer to Questions.\n4. Typo: Sec 3.1 \"It contains Although simpler...\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "HqOP4S5bJ1", "reviewer": "Reviewer_7fhN", "summary": "This paper proposes a new program synthesis framework for solving inductive reasoning problems based on large language models and prompting techniques. The idea is to first generate hypotheses based on the training samples, and then select a few hypotheses to realize their implementations. The implementations are verified on the training samples and the best implementation is selected to perform inference on the test samples. Experiments on ARC and 1D-ARC verify the effectiveness of the proposed method, while the proposed method doesn't outperform direct prompting on SyGuS.", "questions": "Questions:\nIs there any deeper connection between Hypothesis Search and the Bayesian learner mentioned in the introduction?\nSec. 2.4. “a lower bound” -> It is not very clear to me why it is a lower bound before I read the experiment section. May rewrite the last sentence.\nSec. 3.1. “It contains” -> incomplete sentence.\nSec. 3.2.1. perf -> per\nSec. 3.2.1. Human-Selected Hypotheses. Why do you use 3 rounds of execution feedback here? The other experiments are based on 2 rounds.\nSec. 3.2.3. How about the ability of GPT3.5 in generating hypotheses? Why is there no table for this section?\nSec. 3.4. Why is there no table for this section? Also the last sentence is an overclaim. It’s the improvement of GPT-4 over CrossBeam, not the proposed prompting technique.", "limitations": "", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "This paper shows that large language models can generate natural language hypotheses based on the training samples. The generated hypothesis can improve the performance of program synthesis on inductive reasoning benchmarks.\nThe paper conducts experiments on ARC, which is a challenging benchmark for inductive reasoning.", "weaknesses": "The overall prompting framework in this paper is very similar to self-debug[1] , except that self-debug focuses on iterative refinement, while this paper emphasizes hypothesis search. If this is the point, the authors should provide a deeper analysis of the generated hypotheses. Algorithm 1 has a similar high-level idea of Figure 3 from the self-debug paper. So this paper is more like revisiting self-debug from a different perspective, which limits its novelty and contribution. This paper also misses an important citation[2].\nExperiments results are not sufficient to justify the significance of the method. Of the 3 datasets used in the paper, the proposed method only works on ARC and 1D-ARC, which are very similar. Besides, it only uses 40 samples for inference and the variance of the performance is not reported. It is likely the observation in this paper may be overestimated due to variance in performance and model selection.\nThe contribution of this paper is not very clear. From the intro, it looks like the authors try to solve the inductive reasoning problem. From the experiments, there is no comparison with non-LLM baselines, and it looks more like an ablation study of using natural language hypotheses in program synthesis.\n\n[1] Chen, et al. Teaching large language models to self-debug. arXiv 2023.\n[2] Austin and Odena, et al. Program synthesis with large language models. arXiv 2021.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Nsv06MhRwM", "reviewer": "Reviewer_e7wF", "summary": "The authors propose to use large language models (LLM) to generate hypothesis for abstraction and reasoning corpus (ARC). \nGiven a task in ARC, the LLM first propose a set of hypothesis, then either a language model or a human in the loop can select a subset hypothesis for generating a program that satisfy the hypothesis as the specification. \nThe automated pipeline which uses the LLM to perform the selections has 27.5% accuracy, and with human in the loop has 37.5%.", "questions": "It would be nice if there a statistical analysis on the failure case analysis.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Originality: 5/5 \nThe idea of using the LLM to generate hypotheses and then synthesizing the downstream Python program is novel and interesting. The experimental result gives positive feedback that the natural language is capable of representing human intuition in this low data in-context learning environment. \n\nQuality: 3/5\nThe experimental result shows promising improvement in the methodology. However, it seems still quite expensive and not reliable enough to generate 64 different hypotheses for the language model by setting the temperature to 1.0. It would be nice to have a chart on the GPT-4 query number against the rate where it hit the correct hypothesis. \n\nClarity: 3/5\nThere are quite a lot of details that are necessary to help understand the work in the supplementary material, for example, the GPT-4 prompts. \n\nSignificance: 4/5\nThis work is important to the program synthesizing community in how to synthesize a natural and intuitive program, instead of synthesizing a functionally correct but not necessarily generalizable program.", "weaknesses": "See strength.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)