Research map / Large language models / Agents, code and math
Hypothesis Search: Inductive Reasoning with Language Models
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes generating multi-level hypotheses (natural language, then Python programs) with LLMs, filtered by summarization or human selection, to solve inductive reasoning tasks like ARC, 1D-ARC, SyGuS, and List Functions.
Problem
LLMs perform poorly on complex inductive reasoning tasks such as ARC when directly prompted to predict outputs via in-context learning.
Approach
Decompose induction into proposing abstract natural-language hypotheses with an LLM, filtering them (LLM summary or human selection), implementing each as a Python program, and verifying programs on training examples with execution feedback, then applying the verified program to test inputs.
Key results
- On a random 100-problem ARC subset, the pipeline with GPT-4 summarized hypotheses reaches 30% accuracy vs 17% for direct prompting; human-selected hypotheses reach 33%.
- On 1D-ARC (108 tasks), the full pipeline reaches 73.1% vs 39.6% for direct prompting.
- On SyGuS, GPT-4 programs reach 94.3% vs 74.8% for CrossBeam.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Generate natural-language hypotheses before programs (Full vs Program Only) (ablation) | GPT-4 pipeline · 1D-ARC | accuracy (%): +12.0 (61.1 to 73.1) | Helped |
| Generate natural-language hypotheses before programs (Full vs Program Only) (ablation) | GPT-4 pipeline · List Functions | accuracy (%): +10 (59 to 69) | Helped |
| Generate natural-language hypotheses before programs (Full vs Program Only) (ablation) | GPT-4 pipeline · SyGuS | accuracy (%): 0 (94.3 both) | No clear effect |
| Program-based representation instead of direct output prediction (ablation) | GPT-4 on ARC · ARC 100-problem subset | accuracy (%): +6 (17 to 23) | Helped |
| LLM-summarized hypotheses (8 of 64) before implementing programs | GPT-4 pipeline · ARC 100-problem subset | accuracy (%): +7 (23 to 30) | Helped |
| Human selection of correct hypotheses from 64 candidates | GPT-4 pipeline · ARC 100-problem subset | accuracy (%): +3 over summarized (30 to 33) | Helped |
| Execution feedback iterations (0 to 3) (ablation) | GPT-4 pipeline · ARC 100-problem subset | accuracy (%): Summarized 24 to 30; Human-selected 26 to 33; plateaus after 2 rounds | Helped |
| Chain-of-thought style natural-language intermediate without programs (ablation) | GPT-4 on ARC · ARC 100-problem subset | accuracy (%): 19 vs 23 program only and 30-33 full pipeline | Hurt |
| Parsel intermediate representation for program generation (ablation) | GPT-4 pipeline · ARC 40-problem subset (human-written hypotheses) and LLM-generated hypotheses | accuracy (%): Human hypotheses 37.5 to 47.5; LLM hypotheses worse (92% to 69% on 13 tasks) | Mixed |
| Replace NumPy array type hint with List[List[int]] in prompt (ablation) | GPT-4 program generation · ARC (human-written hypotheses, pilot subset) | accuracy (%): -5 (37.5 to 32.5) | Hurt |
| Ranking hypotheses with GPT-3 log-probabilities to prune candidates (ablation) | hypothesis filtering · ARC pilot (21 tasks) | number of correct hypotheses in top 16: only 10 of 21 kept in top 16 | Hurt |
| Remove example problems from hypothesis-generation prompt (zero-shot hypotheses) (ablation) | GPT-4 pipeline · 1D-ARC | accuracy (%): -1.8 (73.1 to 71.3) | Hurt |
Surprising findings
- Programs that pass all training examples almost always generalize to the test input, suggesting a low false-positive rate.
- Chain-of-thought style natural-language intermediate reasoning without programs dropped GPT-4 performance to 19% on ARC.
- Parsel-based intermediate decomposition hurt performance with LLM-generated hypotheses despite helping with human-written ones.
Limitations
- Requires many LLM calls per task, making the approach costly.
- Hypothesis generation struggles with visual patterns and large grids in ARC.
- Summarized hypotheses can become vague and lose the correct hypothesis.
Experimental setup
Datasets: ARC 1D-ARC SyGuS List Functions LARC
Benchmarks: ARC 1D-ARC SyGuS List Functions
Metrics: accuracy (top-1)
Baselines: Direct prompting (ICL) Program Only CrossBeam Human-Written Hypotheses
Builds on: Program of Thoughts Chain-of-thought Parsel CrossBeam BUSTLE
Closest papers by meaning
- Phenomenal Yet Puzzling: Testing Inductive Reasoning Capabilities of Language Models with Hypothesis Refinement (ICLR 2024 · similarity 0.93)
- MIRAGE: Evaluating and Explaining Inductive Reasoning Process in Language Models (ICLR 2025 · similarity 0.92)
- Meaningful Learning: Enhancing Abstract Reasoning in Large Language Models via Generic Fact Guidance (NeurIPS 2024 · similarity 0.90)
- Exploring the Limits of Sub-Billion Language Model Reasoners with Open Training Recipes (ICLR 2026 · similarity 0.89)
- Training Language Models to Reason Efficiently (NeurIPS 2025 · similarity 0.89)
- Reasoning Scaffolding: Distilling the Flow of Thought from LLMs (ICLR 2026 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.