Hypothesis Search: Inductive Reasoning with Language Models

Thank you for your encouraging comments and insightful questions!

It would be nice to have a chart on the GPT-4 query number against the rate where it hit the correct hypothesis.

Great idea; we’ve added this to Appendix B.1. The number of tasks with correct hypotheses increases consistently as we sample more hypotheses from GPT-4.

It would be nice if there a statistical analysis on the failure case analysis.

Thanks for the excellent suggestion! For the human-selected evaluation, we’ve now added a simple failure case analysis - namely, we were curious about the following: for what subset of the questions did the model fail because it failed to generate a correct hypothesis, and for what subset did it fail because it failed to implement a correct hypothesis? We looked at the 100 sampled tasks and the human-selected correct generated hypotheses (though, we reiterate here that “correct” is both subjective and somewhat arbitrary without experiments in line with those conducted in LARC). For 49% of them, at least one correct hypothesis was identified as correct. Of those selected, 33 (67%) led to correct programs. However, when given all correct language (i.e., the Human-Written Hypothesis evaluation), the model successfully implements 45% correctly. Of these, only one task is solved by the human-selected pipeline that isn’t solved by the human-written pipeline. This may suggest that there is a relationship between the tasks that the model can propose a hypothesis for and the tasks for which it can implement that hypothesis.

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.

We strongly agree with this in principle, and have now highlighted this in our limitations section! However, we note that over time the best large language models do get better, cheaper, and faster, which will make our method more effective. Less than a month ago, a version of GPT-4 was announced that appears to be broadly improved, faster, is over two times less expensive, and (ostensibly) supports a 128k context window.

Thank you for your constructive comments. We appreciate the chance to clear up any points of confusion, but please do not hesitate to let us know if any further clarifications are needed.

while the proposed method doesn't outperform direct prompting on SyGuS.

We want to clarify that there is no direct prompting baseline in the SyGuS experiment. because there are no testing examples in SyGuS. Our method performs slightly worse than our program-only hypothesis. We note that on a new evaluation using gpt-4-0613, our full pipeline obtains the same performance with the program only hypothesis.

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.

First, we apologize for the misunderstanding. Self-debug does not explore inductive reasoning (that is, taking a collection of examples and identifying their underlying rule). Not only does it not “emphasize hypothesis search” - indeed, hypothesis search is not part of their method, and is our primary contribution.

In particular, we are (to our knowledge) the first to demonstrate that language models can effectively generate a collection of hypotheses to solve an inductive reasoning problem, and then select the right hypothesis by evaluating its ability to explain the inductive reasoning problem’s examples. We have added a discussion to the Introduction section to help clarify this.

While our paper does use the language model to revise its solutions in code, we also strongly agree that this idea is not one of our contributions. We have updated the paper to more clearly emphasize that our primary contribution is programmatic inductive reasoning pipeline via hypothesis generation, and have added additional citations to prior work on automated code repair [1,2,3,4] to help contextualize this work.

[1] "A Bidirectional LSTM Language Model for Code Evaluation and Repair" Rahman et al 2021
[2] "Neural Program Repair by Jointly Learning to Localize and Repair" Vasic et al 2019
[3] "Deep Learning for Code Repair" Pang 2018
[4] "Automated program repair through the evolution of assembly code" Schulte 2010

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.

Thank you for highlighting this aspect of our work. First we want to note that on SyGuS, we have reported the accuracy of a non-LLM baseline CrossBeam [5], which is outperformed by our methods. In our paper, we specifically concentrate on exploring inductive reasoning through the lens of language models, as indicated in our title. This focus is intentionally chosen to better understand the capabilities of LLMs in this context. Our main focus was on understanding the impact of generating various kinds of intermediate hypotheses when solving inductive reasoning tasks with language models, a type of reasoning that they have been known to struggle with. For some context, we’ve also now highlighted the special-purpose DSL-based state-of-the-art on ARC (according to [6]) in our text, which performs marginally worse than our results with human-written hypotheses, solving 43 of our 100 sampled tasks.

Experiments 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.

Could you please clarify this? Our results indicate a significant improvement over prior work on all of the datasets. Note that both the program-only and the full hypothesis search methods show significant improvement over prior work on SyGuS. We have now added the cognitive-science-inspired inductive reasoning dataset, List Functions, from “The Child as Hacker” [7] which is fairly different from any of the current three datasets. As on the ARC datasets, this shows a clear advantage with the natural language hypotheses.

Other points:

This paper also misses an important citation.

Thank you, we’ve added [8] to the related works. Note that this work focuses on solving program synthesis given natural language descriptions, while our work focuses on inductive reasoning tasks where we only observe a few input-output examples as the specification for programs.

Besides, it only uses 40 samples for inference and the variance of the performance is not reported.

Thanks for this great point. Originally, scaling this up was prohibitively expensive. However, we have now been able to access additional resources, allowing us to extend these results to 100 tasks for ARC, 1D-ARC and the new List Functions datasets. All the conclusions remain consistent with the previous results, which demonstrate the effectiveness of our proposed pipeline.

The contribution of this paper is not very clear.

Thank you, we’ve added a paragraph to the introduction to help clarify.

Is there any deeper connection between Hypothesis Search and the Bayesian learner mentioned in the introduction?

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 -- we’ve added a note about this to future work.

Why do you use 3 rounds of execution feedback here?

We have updated experiments to uniformly use 3 rounds of feedback.

How about the ability of GPT3.5 in generating hypotheses?

For ARC we noted that we observed GPT-3.5 to mostly generate meaningless hypotheses. However, motivated by this question, we ran additional experiments to understand the performance of GPT3.5-generated hypotheses on 1D-ARC, SyGuS and List Functions when using GPT3.5-generated hypotheses. Notably, on all of the datasets we evaluated besides ARC, natural language hypothesis search improved performance over both a direct prompting baseline, as well as a program-only hypothesis search. Surprisingly, in the case of 1D-ARC, the program-only GPT-3.5 results were actually slightly worse than its direct prompting results, while the full hypothesis search pipeline was better than both. We have added the following table to Appendix B.

Sec. 3.4. Why is there no table for this section?

We have updated the paper to summarize the results in a table.

Also the last sentence is an overclaim. It’s the improvement of GPT-4 over CrossBeam, not the proposed prompting technique.

We agree that the results are not directly comparable. We have revised the text accordingly. We provide the number for CrossBeam as for a reference of the state-of-the-art DSL-based method.

[5] "Crossbeam: Learning to search in bottom-up program synthesis," Shi et al. 2022
[6] "Large Language Models as General Pattern Machines," Mirchandani, et al. 2022
[7] "The Child as Hacker," Rule et al. 2020
[8] "Program synthesis with large language models." Austin, et al. 2021

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.

First, we agree: we have removed this sentence. For some context, this was intended as a relative statement, given the poor performance of the LLM-based alternatives. We have also added a more explicit we’ve now added a failure case analysis - namely, we were curious about the following: for what subset of the questions did the model fail because it failed to generate a correct hypothesis, and for what subset did it fail because it failed to implement a correct hypothesis? We looked at the 100 sampled tasks and the human-selected correct generated hypotheses (though, we reiterate here that “correct” is both subjective and somewhat arbitrary without experiments in line with those conducted in LARC). For 49% of them, at least one correct hypothesis was identified as correct. Of those selected, 33 (67%) led to correct programs. However, when given all correct language (i.e., the Human-Written Hypothesis evaluation), the model successfully implements 45% correctly. Of these, only one task is solved by the human-selected pipeline that isn’t solved by the human-written pipeline. This may suggest that there is a relationship between the tasks that the model can propose a hypothesis for and the tasks for which it can implement that hypothesis.

Can you evaluate the recall of model-generated hypotheses, either by some automatic metric or human evaluation?

We have included additional experiments in Appendix B.1 where we evaluate the recall of model-generated hypotheses on multiple datasets. On ARC, we measure the percentage of tasks with correct hypotheses (judged by human) when we increase the number of hypotheses. On 1D-ARC and List Funcctions, we measure the accuracy of our pipeline as we increase the number of hypotheses. Both experiments show that the recall steadily increases as the number of hypotheses increases.

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?

Although top-3 is indeed technically the “official” evaluation metric, top-1 has been the often-unstated convention in LLM-based papers (e.g. [3,4,5]). In general, we would argue that pass@1 makes more sense since we care about evaluating generalization. For some context, we’ve also now highlighted the special-purpose DSL-based state-of-the-art (according to [4]) in our text, which performs marginally worse than our results with human-written hypotheses, solving 43 of our 100 sampled tasks.

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?

In principle, we would argue this framework should be applicable for any inductive reasoning task that can be represented computationally — in practice, there are a few types of inductive reasoning tasks that are not currently supported in our framework.

For example, many more complex visual inductive reasoning tasks will require extending this implementation, such as using a compositional visual programming language to represent the program (e.g., VISPROG [6]). Moreover, if a task is truly unprogrammable, then we lose a core value of this work, namely the inductive bias and generalization that comes with a programmatic representation. Some challenges may also arise for models with a higher false-positive rate which we’ve now noted in the limitations.

In terms of tasks that cannot be solved by Python programs, in discussing future work, we’ve added discussion around more open-ended tasks like summarization where we might want to optimize a “soft” score (e.g., ROUGE [7]). In short, these problems are still approachable with Python but may require the language model to leverage another machine learning model.

Typo: Sec 3.1 "It contains Although simpler..." Thank you, this is now fixed!

[2] “Coder reviewer reranking for code generation,” Zhang et al. 2023 [3] “LLMs and the Abstraction and Reasoning Corpus: Successes, Failures, and the Importance of Object-based Representations,” Xu et al. 2023
[4] “Large Language Models as General Pattern Machines,” Mirchandani et al. 2023
[5] “Large Language Models Are Not Strong Abstract Reasoners,” Gendron et al. 2023
[6] “Visual Programming: Compositional visual reasoning without training,” Gupta and Kembhavi 2022
[7] “ROUGE: A package for automatic evaluation of summaries,” Lin 2004

Thank you for the thorough and very helpful questions!

Hypothesis generation slightly harms the performance on SyGuS where the inputs are strings…

Thank you for this point! We’d like to clarify that we don’t consider the SyGuS results as negative: indeed, our pipelines (both Program Only and Full) both perform significantly better than prior work, and we’ve added a table to Sec. 3.4 to help highlight this. However, we do find that the natural language hypotheses are not a useful additional abstraction in this dataset. This is likely because the SyGuS tasks are relatively simple so the Program Only ablation already achieves saturated performance.

However, we also introduce a new dataset to demonstrate the usefulness of natural language hypotheses on non-ARC tasks. Specifically, we now investigate the cognitive-science-inspired inductive reasoning dataset, List Functions, from “The Child as Hacker” [1] which is fairly different from any of the current three datasets. As on the ARC datasets, this shows a clear advantage with the natural language hypotheses.

Due to a change in our available resources, we also updated our results with a slightly newer version of gpt-4, gpt-4-0613. With the updated model, both pipelines correctly solve 94.3% of the examples.

[1] “The Child as a Hacker,” Rule et al. 2020

The main challenge of generating high-quality programs is largely unsolved.

We agree that there is still substantial work to be done before these difficult inductive learning tasks can be considered complete. On the other hand, our methods achieve large improvement over four datasets, which we believe is substantial. Our main contribution is showing how to approach inductive learning using program generation as a component, instead of tacking the program generation problem. Future improvements on generating high-quality programs can be expected to benefit our approach to induction reasoning tasks.

The technical novelty is limited

Novelty is, of course, a subjective quality. Some technical novelty derives from the extensive mathematical reasoning required. Other novelty derives from simple ideas which haven’t been previously noticed and yet have powerful implications. We believe our paper is an example of the latter. The ability to do inductive learning from a few examples has been a cornerstone ability of LLMs in recent years, and their failure in more complex inductive learning tasks (e.g. ARC) has been taken by a substantial subset of computer scientists as a condemnation of the enterprise. Thus finding that a structured approach to induction yields very large improvements, and that this depends on the right staging between natural and formal languages, is an important finding. To those who expected LLMs to make no progress on hard problems of induction it is a surprising, we’d say novel, one.

We sincerely thank you for this very in-depth and constructive review!

What is the performance with different number of hypotheses?

Thanks for this excellent question! We’ve performed additional experiments in Appendix B.1 to investigate the performance as the number of considered hypotheses changes and found that the accuracy of models increases consistently with more hypotheses from GPT-4.

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.

For hypothesis summarization, we agree that it is better and more rigorous to evaluate on all the tasks instead of a subset. Originally, a subset was used due to cost constraints, but we have now been able to access additional resources. We are currently running this experiment on the full 100 tasks and expect to have results before the end of the discussion period – please note, however, that we do not expect the final results on hypothesis summarization to meaningfully change.

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.

We will only keep the first correct hypothesis found for each task. So we are testing one hypothesis for each task in the human-selected experiment. We agree that selecting 8 hypotheses after filtering would be better for consistency; there are likely other clever oracles that one might use for filtering for this (e.g., using GPT-4 to find the most similar hypotheses to the ground truth), and we believe this would be a valuable exploration for future work.

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.

Great point! We have unified all of the experiments to have three feedback rounds.

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.

First, we apologize for the confusion - the table is actually showing GPT-4 results, but the caption was ambiguous. We have run an additional experiment using gpt-3.5-turbo-16k to generate 128 programs with human-written hypotheses on the 100 sampled ARC tasks and achieved an accuracy of 30%, which is a little bit higher than the accuracy of gpt-3.5-turbo (27%).

The findings on SyGuS are divergent from the main evaluation, as the best result is achieved with purely code generation.

Thank you for this point! We’d like to clarify that we don’t consider the SyGuS results as contradicting the overall result: indeed, our pipelines (both Program Only and Full) both perform significantly better than prior work. However, we do find that the natural language hypotheses are not a useful additional abstraction in this dataset. This is likely because the SyGuS problems are relatively easy.

We have also introduced a new dataset to demonstrate the usefulness of natural language hypotheses on non-ARC tasks. Specifically, we now investigate the cognitive-science-inspired inductive reasoning dataset, List Functions, from “The Child as Hacker” [1] which is fairly different from any of the current three datasets. As on the ARC datasets, this shows a clear advantage with the natural language hypotheses.

[1] “The Child as a Hacker,” Rule et al. 2020

Hi! We appreciate your patience -- we've now also completed the experiment where we evaluated all of the summarized hypotheses, not just the ones where the tasks had human-selected hypotheses. Including the problems without human-selected hypotheses solved two additional problems, bringing the summarized score up to 30% (from 28%). Notably, this suggests that the success rate for problems with a correct hypothesis before summarization was roughly 57% (28/49), while the success rate for the others was about 4% (2/51). We've updated all of the corresponding parts of the paper (Tables 1 and 2, the abstract, and Section 3.2).

For one of the newly solved problems, the summarized hypothesis is correct despite all of its corresponding hypotheses having mistakes. In this case, the summarization removes some incorrect details from the original hypotheses. For the other problem, the model solved it despite not having a correct hypothesis.

Thanks again for the great suggestions, and please let us know if you have any remaining questions!

Thank you for your detailed and insightful comments. We're happy to have the chance to clear up these points, but please let us know if anything is still unclear.

While the method of generating and implementing hypotheses as Python programs is innovative, it may pose scalability challenges.

This is an excellent point - indeed, we emphasize the high cost of this approach throughout the paper, as well as some strategies that we took to attempt to mitigate it (e.g., since the primary cost comes from implementing rather than generating hypotheses, our summarization approach substantially reduces the necessary costs). We highlight multiple approaches to improve the scalability by focusing on selecting or extracting a smaller set of hypotheses with the language model; on the other hand, our method can also provide a flexible trade-off between performance and cost by varying the number of hypotheses and programs to search for. This is unachievable by the baseline method that directly prompts the answer. Recent work makes the reduced performance from the current search-space-reduction approaches less surprising, emphasizing that even advanced language models struggle to evaluate their own generations without external feedback [1]. Furthermore, we would like to highlight the flexibility of Python code from a program synthesis perspective. Before LLMs, program synthesis typically required operating over a small DSL with a very restrictive grammar, e.g. regular expressions, string manipulations, or 3D graphics [2,3,4,5]. However, we agree that this is an important point. To emphasize it, we have added a section on limitations and future work, where we discuss this.

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

Thanks for this point! In response, we’ve added a new cognitive-science-inspired inductive reasoning dataset, List Functions, from “The Child as Hacker” [6] which is fairly different from any of the current three datasets. As on the ARC datasets, this shows a clear advantage with the natural language hypotheses.

We also agree that there are always more datasets that we could include. We’d like to note that datasets like 1D-ARC are designed to vary the complexity and structure of ARC, and SyGus is a very differently structured task. In terms of tasks that cannot be solved by Python programs, in discussing future work, we’ve added discussion around more open-ended tasks like summarization where we might want to optimize a “soft” score (e.g., ROUGE [7]). In short, these problems are still approachable with Python but may require the language model to leverage another machine learning model.

Also, the baselines are limited only with direct prompting and ablated baselines, with no baselines from related works

Thanks for raising this point. One of the reasons that we were excited to work on this direction is that there is not an extensive body of work that has explored inductive reasoning with language models. We will highlight that certain ablations can indeed be seen as corresponding to applying related works to the inductive reasoning task. For example, the program-only baseline without revisions can be seen as somewhat analogous to the “Program of Thoughts” prompting if applied to the inductive reasoning domain [8]. We’ve also added a language-only baseline that can be seen as analogous to a “Chain of Thoughts” baseline when applied to inductive reasoning [9]. We have also now modified our main text to incorporate this. We’ve also run the state-of-the-art DSL-based approach for ARC on our 100-task subset, finding that it performs slightly below the human-written score, solving 43 of the problems correctly. We’ve added this context in Section 3.2.

Thank you for your excellent questions!

The 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.

Thank you for this great point! We’ve added a short list of contributions to the introduction.

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.

Thanks again for the suggestion - we’ve now moved the GPT-3.5 experiments to the appendix.

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?

This is a great question. Because the problem sizes (in terms of the number of tokens necessary) and the tasks are easier for 1D-ARC, for the “Full” method, we evaluate all of the generated hypotheses. In contrast, a “Full” evaluation of all of the generated hypotheses for ARC would be prohibitively infeasible for us at the current cost of GPT-4. We’ve now clarified this in the text of the corresponding subsection. For the direct prompting method, we report the results from [2] for a direct comparison.

For negative results presented in Sec. 3.4, I suggest to summarize them in a table as well.

Thank you for this suggestion! We’ve added a table to Sec. 3.4, but we’d like to clarify that we don’t consider the SyGuS results as negative. Indeed, both the Program-Only and Full hypothesis search pipelines perform significantly better than prior work. However, we do find that the natural language hypotheses are not a useful additional abstraction in this dataset. Likely because the SyGuS tasks are simply easier. We also introduce a new dataset to demonstrate the usefulness of natural language hypotheses on non-ARC tasks. Specifically, we now investigate the cognitive-science-inspired inductive reasoning dataset, List Functions, from “The Child as Hacker” [1] which is fairly different from any of the current three datasets. As on the ARC datasets, this shows a clear advantage with the natural language hypotheses.

[1] “The Child as a Hacker,” Rule et al. 2020
[2] LLMs and the Abstraction and Reasoning Corpus: Successes, Failures, and the Importance of Object-based Representations. Xu et al. 2023