PaperlayerView exact revision on arXiv

Source-linked AI summary

Hypothesis Search: Inductive Reasoning with Language Models

Ruocheng Wang, Eric Zelikman, Gabriel Poesia, Yewen Pu, Nick Haber, Noah D. Goodman

arXiv:2309.05660v2cs.LGcs.AIcs.CL

TL;DR

Language models struggle with precise inductive reasoning on complex tasks such as ARC. The paper generates abstract natural-language hypotheses, implements them as verifiable Python programs, and filters candidates; across four datasets, explicit hypothesis formation improves performance over direct prompting, with both representation levels contributing.

  • Problem

    Language models have limited capacity for precise inductive reasoning, especially on complex benchmarks such as ARC.

  • Method

    The pipeline generates multiple natural-language hypotheses, implements them as Python programs, verifies them on training examples, and filters hypotheses with an LLM or human annotator.

  • Results

    Explicit hypothesis formation improves performance over direct prompting across ARC, 1D-ARC, SyGuS, and List Functions, and both abstraction levels are beneficial.

  • Takeaways & Limitations

    Separating abstract hypothesis proposal from precise program formalization provides a useful approach for inductive reasoning tasks across multiple domains.

  • Takeaways & Limitations

    The pipeline requires multiple LLM queries, which can be costly, and generic Python programs can be difficult to use for some visual reasoning tasks.

Abstract

from arXiv · show

Inductive reasoning is a core problem-solving capacity: humans can identify underlying 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 hypotheses as concrete Python programs. These programs can be verified by running on observed examples and generalized to novel inputs. To reduce the hypothesis search space, we explore steps to filter the set of hypotheses to implement: 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, string transformation dataset SyGuS, and list transformation dataset List Functions. On a random 100-problem subset of ARC, our automated pipeline using LLM summaries achieves 30% accuracy, outperforming the direct prompting baseline (accuracy of 17%). With the minimal human input of selecting from LLM-generated candidates, performance is boosted to 33%. Our ablations show that both abstract hypothesis generation and concrete program representations benefit LLMs on inductive reasoning tasks.

1 INTRODUCTION

The paper addresses the limited inductive reasoning of language models on precise tasks by decomposing hypothesis formation across natural-language and programmatic representations. It evaluates this approach across four inductive reasoning datasets and studies ways to reduce hypothesis-search costs.

  • Motivation: LLMs can perform in-context inductive reasoning, but prior work finds limited capacity on tasks requiring precise behavior, including ARC.ARC provides training input-output pairs sharing a transformation rule, with novel outputs required at test time.
  • Approach: The pipeline first generates natural-language hypotheses, then realizes them as executable programs that can be verified and generalized.Natural language captures abstract features but may be ambiguous, while programs provide precise, executable representations.
  • Approach: The method reduces search costs by summarizing multiple hypotheses with an LLM or selecting promising hypotheses through human annotation.These filtering strategies address the expense of sampling and implementing multiple hypotheses and programs.
  • Evaluation: Experiments cover ARC, 1D-ARC, SyGuS, and List Functions, spanning visual grids, number sequences, strings, and lists.The four datasets provide diverse inductive reasoning tasks across different domains.
  • Findings: Ablations indicate that both natural-language hypothesis generation and programmatic hypothesis representations benefit inductive reasoning performance.The paper frames these as separate capabilities: proposing accurate hypotheses and formalizing them as programs.

2 METHOD

The method formulates inductive reasoning as discovering a transformation from input-output examples, then searches over natural-language hypotheses and executable programs. Candidate programs are tested on training examples, while hypothesis filtering reduces the computational cost of this search.

  • 2.1 PROBLEM STATEMENT: The task is to infer an unknown transformation f from training pairs (x_i, y_i) and predict outputs for novel inputs.Each observed output satisfies y_i = f(x_i), while the corresponding outputs for novel inputs are held out.
  • Program Generation: A program that passes all training examples is returned; otherwise, execution feedback is used to revise candidate programs.The implementation procedure supports multiple programs per hypothesis and repeated feedback iterations.
  • Program Selection: The search retains the program that correctly handles the greatest number of training examples when no candidate passes them all.The selection score counts examples satisfying both correct outputs and absence of execution exceptions.
  • 2.2 OVERVIEW: The pipeline generates natural-language hypotheses, filters them, implements each selected hypothesis as Python programs, and validates the programs on training examples.Filtering can use either an LLM or a human annotator before program generation.
  • 2.4 REDUCING NUMBER OF CANDIDATE HYPOTHESES: To reduce implementation cost, GPT-4 summarizes candidate hypotheses into fewer hypotheses, while human selection estimates performance with broader candidate consideration.The paper also describes the four evaluation datasets through examples in Figure 2.
  • Program Generation: For each hypothesis, GPT-4 generates multiple Python programs, which are executed against the original input-output examples while test examples remain held out.The implementations are checked for correct outputs on every training case.

3 EXPERIMENTS AND RESULTS

Experiments evaluate the pipeline across ARC, 1D-ARC, SyGuS, and List Functions using direct prompting and program- or hypothesis-based variants. Results show benefits from explicit hypotheses, program representations, and execution feedback, although hypothesis summarization can introduce ambiguity.

  • The evaluation spans ARC, 1D-ARC, SyGuS, and List Functions, covering 2D grids, number sequences, strings, and list transformations.
  • ARC: ARC experiments compare direct prompting with program-only, summarized-hypothesis, and human-selected-hypothesis variants.The pipeline generates multiple hypotheses or programs and selects implementations using training examples.
  • ARC: Top-1 accuracy is used for ARC evaluation rather than the challenge’s official top-3 accuracy.
  • ARC ablations: 19% accuracy was achieved by Chain of Thought, regardless of whether intermediate hypotheses were model-generated or human-written.
  • ARC ablations: Execution feedback improves performance across hypothesis-generation methods, but gains plateau as feedback iterations increase.
  • 1D-ARC: On 1D-ARC, generating hypotheses and implementing programs significantly improves performance over direct prompting.The full variant generates 16 language hypotheses and four programs per hypothesis.
  • SyGuS: 94.3% accuracy was achieved on SyGuS both without hypothesis generation and with natural-language-conditioned program generation.The direct approach used eight programs with two feedback rounds; the hypothesis-conditioned approach used four hypotheses and two programs per hypothesis.
  • List Functions: On List Functions, the evaluated method consistently outperforms baselines across a 100-task sample.A correct language hypothesis almost always leads to a correct Python implementation on this dataset.

4 DISCUSSION

The discussion identifies failures in both hypothesis generation and program implementation, while noting that expanding candidate search may improve performance as inference costs fall.

  • Hypothesis Generation: GPT-4 struggles with complex visual relationships and very large grids when generating hypotheses for ARC.It handles points, lines, rectangles, repetition, and symmetry more readily than translation, scaling, containment, or large-grid reasoning.
  • Hypothesis Generation: GPT-4 generates hypotheses more successfully on 1D-ARC, partly because its visual encoding is easier.The authors suggest vision-language models may help close the remaining gap on visual tasks such as ARC.
  • Program Generation: Correct hypotheses can still yield incorrect programs when visual tasks require difficult implementations or ambiguous concepts.Examples include irregular-shape filling and misinterpreting a phrase such as “color pattern.”
  • Considering Every Candidate Hypothesis: The pipeline currently samples 64 hypotheses because a large candidate set is needed for a reasonable hit rate of correct hypotheses.A single candidate can take up to 1.5$ to test, motivating hypothesis summarization and human filtering.
  • Program Generation: Parsel is explored with GPT-4 to decompose solutions, generate multiple component implementations, and search over their combinations.This approach aims to improve code generation and evaluation through compositional program generation.

5 RELATED WORKS

The work connects inductive reasoning and program synthesis while using general-purpose Python programs rather than manually designed domain-specific languages.

  • Inductive Reasoning: Program synthesis methods infer rules from observations and generalize them to novel scenarios, often using manually designed domain-specific languages.The paper instead draws on this literature while broadening the representation choice.
  • Inductive Reasoning: The paper uses Python to represent underlying rules, making the method applicable across grid and string transformation domains.This contrasts with prior reliance on domain-specific languages.
  • Reasoning with Programs: Program representations have been applied to visual reasoning and question answering, alongside work on generating programs with language models.The paper situates its approach within this broader programmatic-reasoning literature.
  • Reasoning with Programs: Prior research found a significant relationship between analogical reasoning ability and compositional programming skills in high school students.The authors suggest language models may exhibit a similar trend given parallels between language-model behavior and cognitive experiments.

6 LIMITATIONS AND FUTURE WORK

The method requires multiple LLM queries and may be costly, while future work must address stochastic objectives, program expressivity, and false positives beyond the evaluated tasks.

  • Limitations: Multiple LLM queries may be costly depending on task complexity.The authors anticipate that improving capabilities and decreasing costs could enable increasingly complex tasks at a given cost.
  • Future Work: Tasks that are stochastic or difficult to express explicitly as programs may require objectives beyond exact match.The paper suggests metrics such as ROUGE and code using other machine-learning models as possible directions.
  • Limitations: Although the method showed a low false-positive rate on the evaluated datasets, other inductive reasoning tasks may require additional work to avoid false positives.The conclusion depends on the assumption of a low false-positive rate observed empirically in these datasets.

7 CONCLUSIONS

The paper presents a hypothesis-generation and program-search pipeline for inductive reasoning and reports improvements over baselines across four challenging datasets.

  • 7 CONCLUSIONS: The pipeline generates natural-language hypotheses, implements them as Python programs, verifies them on training examples, and executes them on novel inputs.It is evaluated on ARC, 1D-ARC, SyGuS, and List Functions.
  • 7 CONCLUSIONS: The pipeline outperforms baseline methods by a large margin on all four evaluated datasets.The datasets span visual, one-dimensional, string-transformation, and list-transformation tasks.

A EXPERIMENT DETAILS

The experiments use specified prompting settings and execution feedback to generate and evaluate hypotheses and programs.

  • Hypothesis generation uses temperature 1.0 with responses capped at 200 tokens, while program generation and execution feedback use temperature 0.7 with 1,000-token responses.
  • The study uses GPT-4-0613 and GPT-3.5-turbo-0301 throughout its experiments.Earlier results used GPT-4-0314 and are included in Appendix C.
  • Execution feedback runs generated programs on training examples and requests corrections using the first failed example when no program passes all examples.

B.1 MORE ABLATIONS

The ablations examine sampling, prompting, model choice, and Parsel-based program generation, showing that additional hypotheses help while model capability and representation affect performance.

  • Ablation on the Number of Hypotheses & Programs: Increasing hypothesis samples steadily raises the percentage of ARC tasks with a correct hypothesis, although the improvement slope flattens.
  • Zero-shot Hypothesis Generation: 71.3% accuracy without hypothesis-generation examples was slightly below the 73.1% achieved with two-shot prompting on 1D-ARC.
  • GPT-3.5: GPT-3.5 reached 27% accuracy with 128 programs from human-written hypotheses, rising to 30% with a 16,384-token context but remaining below GPT-4.GPT-3.5 was approximately 20 times cheaper than GPT-4.
  • Parsel for Program Generation: Using human-written hypotheses, the Parsel adaptation achieved 47.5% accuracy on 40 ARC questions, compared with 37.5% for direct prompting.

B.4 PILOT EXPERIMENTS AND NON-SYSTEMATIC FINDINGS

Pilot experiments test representation and ranking choices, finding that type hints help program generation while alternative grid representations can harm performance.

  • Python Types of Matrices for Grids in ARC: Using numpy.ndarray[int] type hints encourages ARC programs to use NumPy operations suited to grid transformations.
  • Using LLMs to Rank Hypotheses: The study also explores using GPT-3 to rerank GPT-4-generated hypotheses because GPT-4 does not expose usable generation probabilities.
  • High-Level Representations of ARC Grids: A shape-placement representation produced more reasonable hypotheses for some ARC problems but harmed performance on more problems.The authors attribute this partly to the difficulty of proposing a useful general ARC representation.
  • Potential Data Memorization: The authors note that publicly available ARC and SyGuS data may have appeared in GPT-4 training data, complicating interpretation of the results.

C RESULTS WITH GPT-4-0314

The appendix reports earlier GPT-4-0314 results and states that conclusions remain consistent after rerunning experiments with GPT-4-0613.

  • Experiments were initially run with GPT-4-0314 and later rerun with GPT-4-0613 because of deprecation and compute-resource changes.
  • The rerun preserved all conclusions when the experiments were scaled up.
  • Table A.2 compares baselines and method variants on 40 randomly selected ARC tasks, with the method outperforming baselines with or without human supervision.
  • Table A.3 reports 1D-ARC results showing that both program generation and hypothesis generation contribute to performance improvements.
  • Table A.4 reports SyGuS results in which directly generated and natural-language-conditioned programmatic hypotheses perform similarly.
Loading 2309.05660v2…