Source-linked AI summary
Induction and Inquiry via Probabilistic Reasoning over Language and Code
Wasu Top Piriyakulkij, Sam Acquaviva, Cassidy Langenfeld, Joshua Tenenbaum, Kevin Ellis
TL;DR
The paper asks how humans can learn and revise abstract knowledge efficiently from sparse, streaming, noisy experience while representing open-ended concepts and uncertainty. It introduces LLM-guided Bayesian inference over mental programs combining natural language and source code, and finds that this approach reproduces human inductive learning and active inquiry across behavioral studies. The results support a model in which many language-like and program-like hypotheses are revised through approximate Bayesian updates with tractable neural guidance.
Problem
Human induction and inquiry must be data-efficient, compute-efficient, uncertainty-sensitive, and flexible enough to represent an open-ended range of concepts.
Method
The model encodes symbolic knowledge as mental programs combining natural language and source code, then uses LLM-guided sequential Bayesian inference to update candidate hypotheses.
Results
Across inductive reasoning and inquiry tasks, the model fits human data and reproduces sequential phenomena including anchoring and garden-pathing.
Takeaways & Limitations
The results suggest that a language-of-thought representation between logic and language, combined with neurally guided sequential inference, can support flexible online induction and inquiry.
Takeaways & Limitations
It remains open whether symbolic hypotheses adequately represent difficult-to-formalize human concepts, and whether LLM chain-of-thought can ensure sound convergence.
Abstract
from arXiv · showhide
How humans grow and maintain abstract knowledge from the sparse, streaming noisy data of experience is a longstanding challenge in cognitive science. Any computational account must satisfy at least three desiderata: It must be (1) data-efficient and compute-efficient, (2) capture gradations of uncertainty to support intelligent inquiry and information gathering, and (3) be flexible enough to mentally represent the endless range of concepts people can learn and think about. Here we introduce a computational model that captures these three properties, by encoding symbolic knowledge as mental programs that combine natural language with source code, and sequentially inferring mental programs using LLM-guided Bayesian learning algorithms. Across a range of behavioral studies this model successfully reproduces quantitative signatures of human inductive learning and active inquiry, such as anchoring, garden-pathing, and other effects. In contrast, pure LLMs and classic Bayesian models either fail at the underlying task, or do not reproduce human behavior, or succeed only at exorbitant computational cost. These results suggest that one way humans continually grow their knowledge is by mentally representing many hypotheses spanning language-like and program-like representations, then revising those hypotheses to approximate Bayesian updates, while a bottom-up neural mechanism (an LLM) makes inference both tractable and learnable.
1 Introduction
The paper addresses how humans can perform efficient, uncertain induction and inquiry over flexible, open-ended concepts. It proposes sequential probabilistic reasoning over mental programs combining natural language and code, supported by LLMs, to reproduce human learning and inquiry phenomena.
- The challenge: Human induction requires learning from sparse, ambiguous evidence while revising beliefs and actively gathering information over time.Flexible hypothesis spaces increase uncertainty and computational cost, creating a challenge for efficient online reasoning.
- The proposal: The proposed account represents hypotheses as mental programs combining natural-language descriptions with computer source code.This representation is intended to be more malleable than rigid logical forms while remaining executable.
- Behavioral scope: LLM-guided sequential probabilistic reasoning reproduces human sequential phenomena including garden-pathing and anchoring.The models also capture gradations of uncertainty and scale to more complex concepts.
- Behavioral scope: The model extends induction into active inquiry by generating questions that alternate with inductive belief updating.This closes the sequential learning loop between induction and inquiry.
- Method comparison: Figure 2 contrasts traditional Bayesian inference, vanilla LLMs, and the proposed LLM-based Bayesian method.The caption characterizes the proposed method as tractable while maintaining consistent beliefs and optimal experiments.
2 Computational Model
The computational model maintains competing mental-program hypotheses and updates them sequentially as evidence arrives. LLMs propose candidate hypotheses, while Bayesian weighting and Sequential Monte Carlo make inference tractable and reduce the influence of hypotheses that fit the data poorly.
- Sequential inference: The model represents multiple competing hypotheses so that new evidence can revise, preserve, or eliminate explanations.Maintaining competing hypotheses also supports inquiry by identifying questions that optimally distinguish them.
- Mental programs: Each mental program combines a natural-language description with a Python implementation, using language priors and code likelihoods to define a posterior.Priors favor short descriptions, while likelihoods favor executions matching the evidence.
- Computational approximation: Because infinitely many hypotheses make exact posterior inference intractable, the model considers a small finite set of plausible hypotheses.This finite approximation is a computational assumption about what humans can plausibly consider.
- Hypothesis proposals: LLMs provide a data-driven proposal distribution that generates candidate hypotheses, whose weights are adjusted toward the posterior when they fit the evidence poorly.Reweighting is intended to mitigate LLM hallucinations rather than rely on LLM proposals alone.
- Sequential Monte Carlo: LLM-augmented Sequential Monte Carlo maintains particles representing candidate hypotheses and revises, reweights, and resamples them after new observations.The implementation proposes particles using a global view of the previous posterior and draws s proposals where s ≤ K.
- Neural and probabilistic components: The approach combines LLM-based associative proposal with top-down probabilistic reasoning instead of relying on LLMs or exhaustive sampling alone.The paper contrasts this with models that restrict the hypothesis space or require exorbitant sampling budgets.
3 Mental Algorithms from Sequential Observations
The model learns algorithms and number concepts from sequential examples by proposing few hypotheses and updating them over time. It reproduces human learning dynamics, including ordering and cognitive-load effects, while using far fewer proposals than a prior approach.
- 3.1 List functions: At a search budget of just 5 proposals, the model fits human accuracy on 250 algorithms better than HL given 500k proposals.Sequential Monte Carlo with LLM-guided proposals captures human performance with substantially less search than the custom HL model.
- 3.1 List functions: Processing examples sequentially matters: replacing Sequential Monte Carlo with Importance Sampling degrades model fit.The model also matches trial-by-trial learning curves best for 70/100 algorithms under MSE.
- 3.1 List functions: LLMs alone neither solve the algorithm-learning problems nor fit human data, whereas LLM-guided sequential Bayesian updates do both.Prior symbolic work required years of engineering and far greater search effort than humans plausibly perform.
- 3.2 Number concepts: In number-category learning, sequential inference reproduces human ordering effects such as anchoring and fits human data better at smaller compute budgets than Thaker et al.'s custom model.Reducing particle counts models cognitive load and replicates the stronger anchoring caused by a distractor task.
4 Resolving Uncertainty by Doing Experiments and Asking Questions
The model treats experiments and questions as ways to reduce uncertainty, selecting among candidate actions using approximate expected information gain. In Zendo and a shopping task, it reproduces human behavior and chooses more informative questions than baseline LLM prompting methods.
- 4 Resolving Uncertainty by Doing Experiments and Asking Questions: The model selects experiments that maximize expected information gain under particle-based approximate probabilistic beliefs.Exact computation is intractable, so an LLM proposes finitely many experiments that are then scored.
- 4 Resolving Uncertainty by Doing Experiments and Asking Questions: In Zendo, the model alternates experimentation and inference and fits human error patterns better than a custom Bayesian learner designed for the dataset.Zendo requires inferring a hidden binary category from constructions made with colored shapes and feedback on category membership.
- 4 Resolving Uncertainty by Doing Experiments and Asking Questions: Figure 8 compares average expected binary reward as the number of questions increases with average information gain at each question.The two panels track task reward and information gain across sequential questioning.
- 4 Resolving Uncertainty by Doing Experiments and Asking Questions: In the shopping task, the model asks natural-language questions optimized for information gain and gives customers a higher chance of discovering their preferred product than basic LLM prompts and ReAct.The model uses a finite product hypothesis space and can query a language model for question-answer likelihoods when Python programs are unsuitable.
5 Discussion
The discussion presents neurally guided sequential inference over language-and-code mental programs as a tractable account of flexible human induction and inquiry, while identifying representation and inference limits.
- 5 Discussion: The model uses code and language as mechanistic commitments for reasoning over open-ended hypothesis spaces.Code supports precise structure, while language supports fuzzier higher-level propositions.
- 5 Discussion: Across inductive reasoning problems, neurally guided sequential inference fits human data better than specialized models and supports alternating induction with inquiry.The authors connect this pattern to a possible unified account of online learning and acting.
- 5 Discussion: The model assumes hypotheses are definable in clear English, leaving open whether symbolic representations suit concepts such as “chair” or “dog walking.”This is presented as a scope boundary for the cognitive account.
- 5 Discussion: Bayesian priors may operate over language-like representations, while programs may better ground hypotheses to data through the likelihood function.The authors identify a unified representation serving both roles as an open direction.
- 5 Discussion: Chain-of-thought may not be sufficiently constrained to ensure sound convergence, unlike the Monte Carlo algorithms used by the authors.Whether future LLMs can implicitly learn sound inference patterns remains open.
- 5 Discussion: The approach complements LLMs by adding rational analysis that constrains and informs their training and use for induction and inquiry.The discussion suggests possible relevance to automated scientific discovery, forecasting and prediction, and embodied or digital agents.
A.1 LLM-SMC-S details
This section specifies implementation details for LLM-SMC-S, including its forward-kernel format, the hypothesis-generating function, and the main LLM used in experiments.
- A.1 LLM-SMC-S details: Algorithm 1 provides pseudocode for LLM-SMC-S.
- A.1 LLM-SMC-S details: The forward kernel q is defined using a common format across all domains in the paper.
- A.1 LLM-SMC-S details: B may be any deterministic, LLM-based function that outputs a set of hypotheses.
- A.1 LLM-SMC-S details: GPT-4 is used as the main LLM for the experiments.
A.2 Instantiations of the probabilistic model in each domain
The paper instantiates its probabilistic model across domains by specifying domain-specific priors and likelihoods, then applying sequential hypothesis reweighting and resampling. These choices include complexity-sensitive priors and explicit treatment of mislabeled examples.
- Domain-specific priors: List-function concepts use a prior proportional to 1/|h|, whereas number concepts use a prior proportional to e^-word_count(h).
- Likelihood specification: The likelihood models noisy labels through θ, the probability that an example is mislabeled.For one instantiation, θ is set to 1/100 and then fit to human data using 10-fold cross-validation.
- Likelihood specification: The Zendo instantiation extends the likelihood with false-positive and false-negative random variables.These variables are assigned truncated normal distributions over [0.5, 1], with separate means and standard deviations.
- Domain-specific priors: For Zendo, the hypothesis prior is proportional to (1/word_count(h))^2.
- Sequential inference: The model sequentially reweights and resamples hypotheses after observing the first data point and during subsequent rounds.The algorithm initializes from e1 = (x1, y1), computes weights, and resamples hypotheses before iterating over t = 2, ..., T.