# Doing Experiments and Revising Rules
with Natural Language and Probabilistic Reasoning

Top Piriyakulkij<EMAIL_ADDRESS>
Department of Computer Science
Cornell University Kevin Ellis<EMAIL_ADDRESS>
Department of Computer Science
Cornell University

###### Abstract

We build a computational model of how humans actively infer hidden rules by
doing experiments. The basic principles behind the model is that, even if the
rule is deterministic, the learner considers a broader space of fuzzy
probabilistic rules, which it represents in natural language, and updates its
hypotheses online after each experiment according to approximately Bayesian
principles. In the same framework we also model experiment design according to
information-theoretic criteria. We find that the combination of these three
principles—explicit hypotheses, probabilistic rules, and online updates—can
explain human performance on a Zendo-style task, and that removing any of
these components leaves the model unable to account for the data.

Keywords: induction; LLM; active learning

## Introduction

An important way that humans grow their knowledge of the world is by
experimentation, intervention, and other forms of active learning. This
process is most clearly present in the experimental sciences, but similar
processes of active inference contribute to human learning starting even in
infancy citep(Mendez et al., 2023; Cook et al., 2011; Carey, 1985; Schulz,
2012; Gopnik et al., 1999). Within everyday adult learning and thinking,
active experimentation helps us quickly learn to use new devices, web pages,
and other tools.

In this work, we aim to give a computational account of how people propose
experiments and revise their beliefs. We work within the context of a game
called Zendo, which is meant to be a microcosm of experimental science. In
Zendo, there is a secret logical rule which determines whether an assembly of
colored blocks is a positive example of a hidden concept (referred to as
‘having the zendo nature’). Players try to discover this rule by building
structures of colored blocks and asking if their structure obeys the hidden
logical rule. Each structure they build is analogous to an experiment designed
to probe the rule that determines if something ‘has the Zendo nature’. Players
both try to infer the rule and predict which new structures conform to the
rule. Studying the experiments and judgments that humans produce across a
variety of different hidden rules gives a rich domain for modeling, and we
will use human data from a study of Zendo citep(N. Bramley et al., 2018) in
which to test and develop different models of how humans propose experiments
and update their beliefs about hidden rules and regularities (Fig. 1).

Figure 1: Illustration from citeN. Bramley et al. (2018) of their Zendo setup,
which we use wholesale. Human participants build structures out of colored
cones of different sizes (left panel). Each structure is an experiment
designed to help the participant learn which structures have the ‘Zendo
nature,’ which this experiment equivalently described as ‘Emitting zeta
waves.’ After doing 8 experiments and receiving feedback on which structures
follow the hidden rule (top right panel), participants predicted which new
structures also obeyed the rule (bottom right panel).

Our model will start with simple core principles: Learners represent
hypotheses in an inner symbolic language-of-thought citep(Fodor, 1975;
Piantadosi et al., 2016), update their beliefs in approximately Bayesian ways
citep(Chater & Oaksford, 2008), and (try to) propose experiments that are
optimal in an information-theoretic sense citep(Settles, 2009). Informally,
having Bayesian beliefs means that the learner attaches a probability to every
possible rule, in light of all of the experiments that it has seen. Optimal
experiments are those which are most likely to cause large changes to these
beliefs. Within the context of zendo, this means an ideal Bayesian
experimenter would keep track of every possible rule (of which there are
infinitely many), consider every single experiment (again, infinite), and then
compute the expected belief change for each experiment to decide what to try
next (each of which involves considering infinitely many hypotheses).

Actual learners are bounded, and can only consider a small number of
hypotheses at a time. How then can they effectively approximate the above
ideal probabilistic reasoner? Our model uses two tricks, both of which we
believe have analogues in human thinking. First, our model considers fuzzy
probabilistic rules, despite knowing that the true rule is deterministic. A
probabilistic rule is equivalent to a distribution over deterministic ones, so
a small collection of fuzzy rules can stand in for a broader space of
deterministic hypotheses. Second, we assume that the learner generates a small
number of candidate hypotheses using a heuristic data-driven bottom-up
mechanism citep(Ullman et al., 2016), which are then re-analyzed in a more
properly Bayesian manner. This bottom-up proposal process helps focus the
learner on the subset of the hypothesis space which is actually likely,
instead of wasting computational effort on low-probability regions of the
hypothesis space.

Our model instantiates several other claims about how human learners make
experiments and revise beliefs. For example, the model updates its beliefs on-
the-fly by revising its previous hypothesis, instead of constructing its
beliefs all at once in a batch-style update, known as _online inference_.
Prior work citep(Thaker et al., 2017) has found that online inference helps
explain ordering effects such as anchoring citep(Kahneman, 2011; MacDonald,
1994). We also model the language-of-thought (the encoding of hypotheses) as
natural-language English text, which allows pretrained large language models
(LLMs) to act as bottom-up data-driven hypothesis generators. Recent work has
found that LLM-generated natural language hypotheses can predict certain
judgments of human learners, particularly when embedded in a Bayesian
framework citep(Ellis, 2023).

Our model accounts for the whole life cycle of a Zendo game, starting from
initial hypothesis formation, sequential experimentation, and predicting which
members of a test set ‘have the zendo nature’. In other words, it can actually
play Zendo and therefore can be compared head-to-head against people. We find
that the basic principles of the model—fuzzy rules, online inference, and
bottom-up natural language hypothesis generation—are all required to
accurately predict human behavioral data. This suggests that when humans
function as ‘intuitive experimentalists’, they might do so by constructing a
small number of fuzzy hypotheses, and then reasoning about them in ways that
roughly accord with the norms of probabilistic inference.

## Zendo Domain and Human Data

Zendo is a game where a player seeks to infer a hidden binary rule about
assemblies of colored blocks. The game starts by providing the player with a
positive scene that follows the hidden rule. Then, the player queries an
oracle as to a particular scene follows the rule or not, or makes a guess
about the secret rule. The game ends when they guess correctly.

citetN. Bramley et al. (2018) introduces a 2D version of the Zendo game shown
in Figure 1. The scenes consist of blocks, each with its own color (red, blue,
green) and size (small, medium, large). The blocks can have different
orientations and positions in a 2D scene. They may and may not touch each
other. The game starts with an initial phase where a rule-following scene is
given, followed by 7 rounds of active learning phase where the player gets to
query an oracle for ground truth prediction. At the end, the player enters a
prediction phase where they are asked to give predictions for 8 test scenes (4
rule-following and 4 not rule-following). citetN. Bramley et al. (2018) study
human gameplay on 10 rules, collecting data from 30 participants who each play
Zendo 10 times (once per rule). They use a cover story of an alien planet
where some arrangements of blocks emit radiation, and the task is to figure
out a rule predicting radiation emission.

Zendo is most naturally framed as a visual-physical concept learning problem.
For our model, however, we will work with discrete symbolic descriptions of
scenes. This makes that problem more compatible with the language-of-thought
paradigm, and also allows using LLMs to operationalize the language of
thought. We therefore modify citetN. Bramley et al. (2018)’s version of Zendo
by associating each block in a scene with discrete attributes instead. The
five attributes are color (red, blue, green), size (small, medium, large),
orientation (upright, left, right, strange), groundedness (grounded,
ungrounded), and touching (which blocks it touches). While this natural
language version of the game removes continuous attributes, such as $x,y$
position and orientation in 2D space, from its scene representations, these
five attributes still maintain the complexity of the game and are sufficient
for playing Zendo with 9 out of their 10 rules.111The 9 rules we use are
“there’s a red”, “all are the same size”, “nothing is upright”, “one is blue”,
“there’s a small blue”, “all are blue or small”, “a red is bigger than all non
reds”, “some touch”, “a blue and a red touch”, and “some pieces are stacked”.
The excluded rule is “some pieces are stacked”, as it requires reasoning about
the $x$-position of blocks.

Several prior works citep(N. Bramley et al., 2018; Fränken et al., 2022; N. R.
Bramley & Xu, 2023) have provided computational models that explain aspects of
how humans play Zendo. Within this literature, we contribute both new modeling
approaches and also a system that can play Zendo end-to-end. We also provide
the finding that online inference and fuzzy rules can offer good accounts of
human Zendo play, and provide a working demonstration of how pretrained
knowledge from language models can guide efficient inference and active
experimentation.

## Model

### Probabilistic Model

In order to have a unified mathematical language to describe both forming
hypotheses and doing experiments, we define a model that includes natural-
language hypotheses $h\in\Sigma^{*}$, experiments (Zendo scenes)
$x\in\mathcal{X}$, and feedback $y\in\\{0,1\\}$ (whether $x$ follows the
rule). We also equip $h$ with a real-valued parameter $\theta$ which controls
the ‘fuzziness’ of the rule $h$. As new experiments are proposed sequentially,
we index experiments and feedback with subscripts, i.e. $x_{t}$ and $y_{t}$
for the $t^{\text{th}}$ experiment and feedback, respectively.

We define a joint probability distribution over hypotheses and feedback, given
experiments, as

$p(h,y_{1:T},\theta|x_{1:T})=p(h)p(\theta)\prod_{1\leq t\leq
T}p(y_{t}|x_{t},h,\theta)$

In other words, we assume that there is a latent rule $h$ that existed prior
to any experiments, with a fixed fuzziness $\theta$, and that each label
$y_{t}$ is a result of rule $h$ and the experiment $x_{t}$. The prior beliefs
about $h$, written $p(h)$, are defined to be inversely proportional to the
number of words in $h$, which gives a bias toward shorter (simpler)
hypotheses:

$\displaystyle p(h)\propto\frac{1}{word\\_count(h)}$

The choice of $p(y|x,h)$ is one of the main ingredients of our model. Recent
work on inductive reasoning with LLM citep(Wang et al., 2023; Qiu et al.,
2023) opt for a deterministic likelihood model, meaning
$p(y|x,h)\in\\{0,1\\}$. Though a deterministic likelihood may seems natural,
given that $h$ is a “rule”, we observe, and will show that a hard all-or-none
likelihood model does not give a good fit to human behavior within Zendo.

We choose the likelihood based on the idea that while the secret rule of a
Zendo game is always deterministic, humans might internally represent
probabilistic rules, and might also assume that some of the examples are
occasionally mislabeled. Then, we define $p(y|x,h,\theta)$ as follows:

$\displaystyle p(y=1|x,h,\theta)=\;\left[\begin{array}[]{cc}\theta\text{, if
}f_{h}(x)=1\\\ \epsilon\text{, otherwise}\end{array}\right]$

where $\epsilon$ is a noise parameter modeling the small probability of an
example being mislabeled, and $f_{h}:\mathcal{X}\rightarrow\\{0,1\\}$ means
that $x$ obeys the rule $h$. We set $\epsilon=0.1$, and we evaluate $f_{h}(x)$
by prompting an LLM to translate $h$ into Python code, which can then be run
on $x$.

One way to understand the likelihood $p(y=1|x,h,\theta)$ is to view $h$ as a
necessary, but not sufficient, requirement. Consider $h=\texttt{there's a blue
block}$ as an example. If a scene has a blue, then $p(y=1|x,h,\theta)$ says
that the scene is likely, with a probability of $\theta$, to be positive, but
if a scene does not have a blue, $p(y=1|x,h,\theta)$ says that the scene is
almost certain to be negative, with probability $1-\epsilon$. The prior we
place on $\theta$ biases it toward more deterministic rules—generally,
$\theta$ should be close to 1, or at least much larger than $\epsilon$. We use
one such prior with these properties, defining $p(\theta)$ as a truncated
normal distribution with mean 0.6, stddev 0.1, truncated within the range
[0.5, 1].

Having now defined the mathematical components of the model, at least in the
abstract, we can now define the computational problems that the learner must
solve. First, the learner must form probabilistic posterior beliefs about the
rule (and its fuzziness), following Bayes:

$\displaystyle p(h,\theta|x_{1:T},y_{1:T})$ $\displaystyle\propto
p(h)p(\theta)\prod_{1\leq t\leq T}p(y_{t}|x_{t},h,\theta)$

Given a test structure $x_{\text{test}}$, an ideal learner uses the beliefs
above to predict a label $y_{\text{test}}$ following:

$\displaystyle p(y_{\text{test}}$
$\displaystyle|x_{\text{test}},x_{1:T},y_{1:T})=$ $\displaystyle\sum_{h}\int
p(y_{\text{test}}|h,\theta,x_{\text{test}})p(h,\theta|x_{1:T},y_{1:T})\text{d}\theta$

For the active learning phase, an ideal learner conducts an optimal
experimentation, which we will give more intuition for later, defined as:

$x^{*}=\operatorname*{arg\,max}_{x\in\mathcal{X}}\mathop{\mathbb{E}}_{p(y|x_{1:T},y_{1:T},x)}[D_{\mathrm{KL}}(p(h|x_{1:T},y_{1:T},x,y)||p(h|x_{1:T},y_{1:T}))]$

The above computations are intractable because they involve considering the
infinitely large set of all hypotheses and experiments. We will describe
approximation methods in the following sections.

### Revising Rules: Online Inference

Exact inference is not computationally tractable when the hypothesis space is
natural language. We introduce here a Sequential Monte Carlo (SMC) algorithm
citep(Doucet et al., 2001), which tracks a small pool of hypotheses that
evolve over time as new experiments are performed. This helps keep track of
those hypotheses that have high posterior, allowing us to perform approximate
predictions tractably. This part of our model should be seen within the
tradition of using SMC methods to give mechanistic, process-level accounts of
online learning citep(Griffiths et al., 2015a). Fig. 2 gives an overview of
how this process works, and the caption gives an in-depth walkthrough of a
single iteration of the algorithm: after each experiment, hypotheses are
reweighed in light of the new data, revised to better explain the latest
experiment, and last, a resampling stage multiplies high probability
hypotheses while eliminating low-likelihood hypotheses.

Figure 2: Sequential Monte Carlo method tracks a small number of hypotheses
(called particles), each of which is a natural language rule. Upon performing
a new experiment, the particles are reweighed according to how well they can
explain this new data, and then revised using a LLM to better fit the outcome
of the latest experiment (“rejuvenated”). There then stochastically
resampled—which kills off low-probability hypotheses—and the process repeats
for another iteration. This figure shows one full iteration of SMC when a
scene with a large red touching a medium blue is observed to be positive (has
the zendo nature).

At the beginning of the algorithm, when the first data point is observed, we
sample hypotheses $h_{1}^{(1)},...,h_{1}^{(n)}$ from an initial proposal
distribution $q(h)$ defined by an LLM. The hypotheses are treated as
particles, and $n$ is the number of particles. For simplicity, we assume
$q(h|x,y)$ is uniform, so we assign particle weights
$w_{1}^{(1)},...,w_{1}^{(n)}$ to be just the prior probability of each
hypothesis. The $\theta_{1}^{(1)},...,\theta_{1}^{(n)}$ associated with each
particle were set to their MAP estimate. A resampling technique is applied to
normalize the weights at the end.

Then, as a new observation $x_{t},y_{t}$ comes in from the active learning
phase, our algorithm first performs reweighting, then a rejuvenation step
(revising rules), and lastly resampling. Reweighting involves multiplying
$w^{(i)}$ with $p(y_{t}|x_{t},h_{t}^{(i)},\theta_{t}^{(i)})$ to incorporate
the new observation and additionally with
$\frac{p(X,Y,h_{t}^{(i)},\theta_{t}^{(i)})}{p(X,Y,h_{t}^{(i)},\theta_{t-1}^{(i)})}$
to account for the changing from $\theta_{t-1}^{(i)}$ to $\theta_{t}^{(i)}$.

After the reweighting step, we perform a rejuvenation step citep(Chopin, 2002;
Thaker et al., 2017) where we consider $k$ local moves proposed by a local
proposer $q(h_{evolved}|h_{original},x_{t},y_{t})$ defined by prompting an
LLM. We sample a batch of $k=15$ local moves for each of the 5 unique
particles with lowest weights. Then, all particles that share the same
hypothesis with these 3 unique particles are rejuvenated. Each particle only
performs a move if it will get a higher joint probability after the move. If
there are multiple moves that will result in higher joint probability, sample
one with probability proportional to the joint probabilities. We update the
weight with
$\frac{p(y_{t}|x_{t},h_{evolved},\theta_{evolved})}{p(y_{t}|x_{t},h_{original},\theta_{original})}$.
At the end, we perform the resampling step before the start of the next
iteration.

It should be noted that the effectiveness of this algorithm depends on the
quality of the initial and local proposers, $q(h|x,y)$ and
$q(h_{evolved}|h_{original},x,y)$. The recent success of LLMs helps enable our
algorithm: a properly prompted LLM can be a phenomenal hypothesis proposer
citep(Qiu et al., 2023). This is despite the well-known unreliability of LLMs,
because proposal distributions do not need to be fully reliable. Instead,
proposals merely need to (sometimes) generate good samples. Reweighing those
samples under the probabilistic model helps correct mistakes made by the LLM,
and it is fundamentally the cooperation of Bayes and the LLM that allows
models like ours to track beliefs with few particles citep(Ellis, 2023). For
example, in our experiments, we use only 25 particles, which we think is about
the same order of magnitude as what humans might track in their head. The
prompts used in our experiments can be founded in the appendix. Another
observation is the algorithm, in its current form, is heuristic and does not
provably target the true posterior. Modifications of the local proposer and
the rejuvenation step to ensure convergence guarantees are left for future
work.

### Doing Experiments: Active Learning

Figure 3: Comparing human and model accuracy on test scenes after 7 rounds of
experimentation. Each point is a different rule assessed either on structures
that follow or do not follow the rule ($\pm$RF). Removing even a single
component of the model significantly degrades its ability to predict human
accuracy.

To perform active learning, we need an experiment proposer and a measure of
informativeness of an experiment. The most informative experiment, among many
proposed candidates, is chosen to be conducted. In the context of Zendo, doing
an experiment corresponds to building a scene out of Zendo blocks, and the
outcome of the experiment is 0 or 1 depending on if the assembly has the zendo
nature.

Like our probabilistic inference strategy, we will propose experiments using
an LLM, bur then reassess those proposals under probabilistic criteria.
Particularly, we provide an LLM with the hypotheses we are keeping track of at
each iteration and ask it to generate experiments that support and falsify
each of the hypotheses. Empirically, this process yields a diverse pool of
experiments.

For the measure of informativeness, we opt for the standard metric commonly
used in the active learning literature citep(Settles, 2009): expected model
change. It is defined as follows:

$\mathop{\mathbb{E}}_{p(y|x_{1:T},y_{1:T},x)}[D_{\mathrm{KL}}(p(h|x_{1:T},y_{1:T},x,y)||p(h|x_{1:T},y_{1:T}))]$

This captures how much, in expectation, the posterior belief would change if
$x$ is queried for ground truth prediction. It can be argued that an
experiment is informative if it significantly changes belief, so in this
sense, the expected model change measures information gain.

We use GPT-4 Turbo for hypothesis generation/revision, while GPT-3.5
translates language to code citep(OpenAI, 2023).

## Results

Figure 4: Comparing human and model accuracy on the 8 test scenes after 7
rounds of experimentation with breakdowns for the 4 rule-following (RF) and 4
not rule-following (Not RF) test scenes. The rows and columns of the grid of
plots are the methods and the 9 rules respectively. Online inference with
fuzzy rules, presented in the last row, most closely matches the accuracy
breakdown observed in humans.

We run the model on the same Zendo games that human participants did, with the
goal of understanding the relative importance of fuzzy rules, symbolic
hypotheses, and online inference. For each of the 9 rules, we compare human vs
model accuracy on test structures that either obey the rule (Rule Following or
_RF_ condition) or violate the rule (Not Rule Following or _Not RF_
condition), for a total of 18 conditions ($\pm$RF, times 9 rules). In Fig.
Figure 3 we compare human-model accuracy across all 18 conditions. The full
model explains 66% of the variance in human accuracy ($R^{2}=.66$). This
result depends on all the core ingredients. Switching to hard rules from fuzzy
drops to $R^{2}=.09$; doing batch inference (instead of online) degrades fit
to $R^{2}=.15$; and having the LLM (GPT-4 Turbo) play Zendo directly without
explicitly forming hypotheses is only loosely correlated with human accuracy
patterns ($R^{2}=.12$). We note that these ablations actually correspond to
other architectures for inductive inference that have been proposed in the
literature. For example, citetKojima et al. (2022), which prompts the LLM to
think step-by-step, is similar in spirit to our direct LLM which asks the LLM
to give a quick summary of its thought before performing experiments. On the
other hand, citetWang et al. (2023); Qiu et al. (2023) propose and thoroughly
study batch inference (with and without refinement) with hard rules. Thus, our
results also demonstrate that, unlike our online inference with fuzzy rules
method, none of the existing LLM-based techniques for inductive reasoning
resemble human behavior well in the context of Zendo.

For a more fine-grained analysis, we noticed that across many rules, there was
a significant difference in human accuracy on RF and Not RF test structures,
with which condition people found easier depending on the underlying rule. One
possible explanation is that, for many rules, it is easy for human to learn
what _doesn’t_ follow the rule, but very hard to learn what _does_ follow the
rule (or vice versa). Fig. 4 illustrates this and compares it against what
each model thinks should be the easier condition. We again see that the full
model (online learning of fuzzy rules) can successfully predict the direction
of most of these trends, unlike its lesioned versions. This suggests the model
might be able to capture trends both across rules and also within rules.

## Discussion

### Active Inference as a Cognitive Testbed

We found that our model was surprisingly fragile: Removing a single piece
causes it to not merely degrade in fit, but to fail utterly. We suspect that
this may be because of the feedback loop between inference and experimentation
that occurs during Zendo—and indeed, which occurs during human development,
and in the history of science. Subpar inference causes poor experiments which
further degrades inference, creating a cascade of failures. Therefore,
studying the interplay of experimentation and hypothesis creation may be an
especially sensitive testbed in which to study the basics of how people build
new knowledge by experimenting with the world.

### Bounded Rationality and Approximate Inference

While we define the computational quantities a learner wants to calculate in
the previous section, it would be misleading to think that achieving exact
inference of these quantifies would result in a more human-like model. The
theory of bounded rationality citep(Simon, 1955) argue that humans do not
always perform the most rational action due to their limited cognitive
resources. Building on this concept of bounded rationality, research on
resource-limited analysis citep(Griffiths et al., 2012, 2015b; Lieder &
Griffiths, 2020) suggest that approximate inference algorithms may provide a
better account for human cognition. Our use of approximate inference model can
then be viewed as an implementation of these frameworks.

### Why probabilistic beliefs are necessary

One might ask if probabilistic beliefs are necessary: can we simply track of a
small list of hypotheses without attaching probabilities to them, or even just
track the single most likely hypothesis? We need probabilistic beliefs because
they are fundamental to experiment design: Good experiments tease apart
competing hypotheses, and the best contenders are those with high posterior
probability. Just tracking a single hypothesis would not give any guidance on
what experiment to do next, and failing to track the high-probability regions
of the posterior would end up performing experiments that test many bad
hypotheses while leaving the more likely ones uncontested. Consequently, the
learner would be unable to narrow down the correct rule.

### Limitations and open directions

The work presented is limited in important ways that suggest the next steps.
Most immediately the hypotheses considered by our work are simple and
stereotyped in form. Much of the promise of using natural language, or another
language of thought, is that it exposes a rich, expressive representation for
combining and creating new ideas. Hypothesis generation, both in science and
in everyday thinking, often involves conjecturing the existence of unseen
objects, not just unknown regularities. Consider for instance Mendel’s
discovery of alleles, or conjecturing the existence of an unknown intruder
upon discovering footprints in one’s house. These forms of abductive thinking,
which often go hand-in-hand with hypothesis formation, are absent from our
model.

### The model as an experimental scientist

The work here is most directly an account of human behavior within the context
of the game Zendo. However, our model is also more broadly inspired by the
mental activities of experimental scientists as they build theories and
models, weigh hypotheses, and design experiments. Two basic features of our
approach reflect scientific experimentation and theory building. First,
scientific theories apply only within a particular regime. For example, many
equations in physics only apply when objects are moving slowly, and many
thermodynamic equations only apply at equilibrium. Outside this regime, the
theory no longer applies, and no longer makes clear predictions. Similarly,
our model hypothesizes fuzzy probabilistic rules which can either predict a
category with high confidence, or outside the regime in which the rule
applies, they can fail to make a decisive prediction.

The second way in which this work reflects the practices of experimental
science is that it builds its hypotheses via an incremental evolutionary
process. In this way, our model is best thought of as performing what is
sometimes called ‘normal science’ — where one works within an existing
paradigm, and considers piecemeal evidence — and does not model paradigm
shifts citep(Kuhn, 1962) (what a scientific theorist might pursue) or deeper
conceptual changes citep(Carey, 1985) (what happens during child development),
both of which require deep reanalysis of ua broad batch of past data.

## References

  * N. Bramley et al. (2018) Bramley, N., Rothe, A., Tenenbaum, J., Xu, F., & Gureckis, T.  (2018).  Grounding compositional hypothesis generation in specific instances.  In _Proceedings of the 40th annual conference of the cognitive science society._
  * N. R. Bramley & Xu (2023) Bramley, N. R., & Xu, F.  (2023).  Active inductive inference in children and adults: A constructivist perspective.  _Cognition_ , _238_ , 105471.
  * Carey (1985) Carey, S.  (1985).  _Conceptual change in childhood_.  MIT Press.
  * Chater & Oaksford (2008) Chater, N., & Oaksford, M.  (2008).  _The probabilistic mind: Prospects for bayesian cognitive science_.  Oxford University Press, USA.
  * Chopin (2002) Chopin, N.  (2002).  A sequential particle filter method for static models.  _Biometrika_ , _89_(3), 539–552.
  * Cook et al. (2011) Cook, C., Goodman, N. D., & Schulz, L. E.  (2011).  Where science starts: Spontaneous experiments in preschoolers’ exploratory play.  _Cognition_ , _120_(3), 341-349.  Retrieved from https://www.sciencedirect.com/science/article/pii/S0010027711000916 (Probabilistic models of cognitive development)  doi: https://doi.org/10.1016/j.cognition.2011.03.003
  * Doucet et al. (2001) Doucet, A., De Freitas, N., & Gordon, N. (Eds.).  (2001).  _Sequential Monte Carlo Methods in Practice_.  Springer.
  * Ellis (2023) Ellis, K.  (2023).  Human-like few-shot learning via bayesian reasoning over natural language.  _NeurIPS_.
  * Fodor (1975) Fodor, J. A.  (1975).  _The language of thought_ (Vol. 5).  Harvard University Press.
  * Fränken et al. (2022) Fränken, J.-P., Theodoropoulos, N. C., & Bramley, N. R.  (2022).  Algorithms of adaptation in inductive inference.  _Cognitive Psychology_ , _137_ , 101506.
  * Gopnik et al. (1999) Gopnik, A., Meltzoff, A. N., & Kuhl, P. K.  (1999).  _The scientist in the crib: Minds, brains, and how children learn._ William Morrow & Co.
  * Griffiths et al. (2015a) Griffiths, T. L., Lieder, F., & Goodman, N. D.  (2015a).  Rational use of cognitive resources: Levels of analysis between the computational and the algorithmic.  _Topics in Cognitive Science_ , _7_(2), 217-229.  Retrieved from https://onlinelibrary.wiley.com/doi/abs/10.1111/tops.12142 doi: https://doi.org/10.1111/tops.12142
  * Griffiths et al. (2015b) Griffiths, T. L., Lieder, F., & Goodman, N. D.  (2015b).  Rational use of cognitive resources: Levels of analysis between the computational and the algorithmic.  _Topics in cognitive science_ , _7_(2), 217–229.
  * Griffiths et al. (2012) Griffiths, T. L., Vul, E., & Sanborn, A. N.  (2012).  Bridging levels of analysis for probabilistic models of cognition.  _Current Directions in Psychological Science_ , _21_(4), 263–268.
  * Kahneman (2011) Kahneman, D.  (2011).  _Thinking, fast and slow_.  macmillan.
  * Kojima et al. (2022) Kojima, T., Gu, S. S., Reid, M., Matsuo, Y., & Iwasawa, Y.  (2022).  Large language models are zero-shot reasoners.  _Advances in neural information processing systems_ , _35_ , 22199–22213.
  * Kuhn (1962) Kuhn, T. S.  (1962).  The structure of scientific revolutions.
  * Lieder & Griffiths (2020) Lieder, F., & Griffiths, T. L.  (2020).  Resource-rational analysis: Understanding human cognition as the optimal use of limited computational resources.  _Behavioral and brain sciences_ , _43_ , e1.
  * MacDonald (1994) MacDonald, M. C.  (1994).  Probabilistic constraints and syntactic ambiguity resolution.  _Language and cognitive processes_ , _9_(2), 157–201.
  * Mendez et al. (2023) Mendez, A. H., Yu, C., & Smith, L. B.  (2023).  Controlling the input: How one-year-old infants sustain visual attention.  _Developmental Science_ , e13445.
  * OpenAI (2023) OpenAI.  (2023).  _Gpt-4 technical report._
  * Piantadosi et al. (2016) Piantadosi, S. T., Tenenbaum, J. B., & Goodman, N. D.  (2016).  The logical primitives of thought: Empirical foundations for compositional cognitive models.  _Psychological review_ , _123_(4), 392.
  * Qiu et al. (2023) Qiu, L., Jiang, L., Lu, X., Sclar, M., Pyatkin, V., Bhagavatula, C., … Ren, X.  (2023).  Phenomenal yet puzzling: Testing inductive reasoning capabilities of language models with hypothesis refinement.  _arXiv preprint arXiv:2310.08559_.
  * Schulz (2012) Schulz, L.  (2012).  The origins of inquiry: Inductive inference and exploration in early childhood.  _Trends in cognitive sciences_ , _16_(7), 382–389.
  * Settles (2009) Settles, B.  (2009).  Active learning literature survey.
  * Simon (1955) Simon, H. A.  (1955).  A behavioral model of rational choice.  _The quarterly journal of economics_ , 99–118.
  * Thaker et al. (2017) Thaker, P., Tenenbaum, J. B., & Gershman, S. J.  (2017).  Online learning of symbolic concepts.  _Journal of Mathematical Psychology_ , _77_ , 10-20.  Retrieved from https://www.sciencedirect.com/science/article/pii/S002224961730010X doi: https://doi.org/10.1016/j.jmp.2017.01.002
  * Ullman et al. (2016) Ullman, T. D., Siegel, M. H., Tenenbaum, J., & Gershman, S.  (2016).  Coalescing the vapors of human experience into a viable and meaningful comprehension.  In _Cogsci._
  * Wang et al. (2023) Wang, R., Zelikman, E., Poesia, G., Pu, Y., Haber, N., & Goodman, N. D.  (2023).  Hypothesis search: Inductive reasoning with language models.  _arXiv preprint arXiv:2309.05660_.

##  Appendix A Appendix

### Prompts

The prompts used in all of our experiments can be found in Tables 1, 2, 3 and
4. In Table 1, we engineer the prompts for online inference so that they only
output simple rules; this approach helps the proposer output hypotheses with
higher priors, since our prior is defined by the number of words in the rule.
We cannot apply this trick to batch inference because, unlike online
inference, it does not evolve simpler rules into more complex ones.

Batch Inference (with and without Rule Refinement) with Hard Rules |  Given the following structures described with att_summary of blocks in the structures: text_c Please list num possible rules about the attributes in a structure that differentiate the good structures from the bad structures. Keep in mind that 1\. All bad structures must violate the rules. 2\. Orders of blocks in a structure do NOT matter. 3\. The rules are short, concise, single sentences. Please number them from 1-num and do not say anything else
---|---
Online Inference with Hard Rules |  Please list num possible rules about the att att_choices. Example 1: Structure: blue, blue Simple rules (Orders do NOT matter): 1\. There is a blue block 2\. There is no green block 3\. All blocks are blue Task 1: x Simple rules (Orders do NOT matter):
Batch Inferece with Fuzzy Rules |  Given the following structures described with att_summary of blocks in the structures: text_c Please list num possible rules about the attributes in a structure that differentiate the good structures from the bad structures. Keep in mind that 1\. All bad structures must violate the rules. 2\. Orders of blocks in a structure do NOT matter. 3\. Do NOT propose ”negative rules” such as ”there is no green block”. 4\. The rules are short, concise, single sentences. Please number them from 1-num and do not say anything else
Online Inference with Fuzzy Rules |  Please list num possible rules about the att. Example 1: Structure: blue, blue Simple rules (Orders do NOT matter): 1\. There is a blue block 2\. All blocks are blue Do NOT propose ”negative rules” such as ”there is no green block”. Do NOT propose rules with quantifier such as ”there are two blue blocks” Task 1: x Simple rules (Orders do NOT matter):
Table 1: Prompts used for the proposer $q(h|x,y)$ of each method A structure
has one or more blocks. Each block should contain the following attributes:
color (blue/red/green) size (small/medium/large) orientation
(upright/left/right/strange) groundedness (grounded/ungrounded), touching
(which other blocks they do and do not touch). Example of rule modifications:
Quantifier change: ’There must be a green block’ -¿ ’There are two green
blocks’ Additional attribute: ’There must be a green block’ -¿ ’There must be
a green block that is upright’ Attribute change: ’There must be a green block’
-¿ ’There must be a blue block’ These modifications are ”local”: only one
attribute/quantifier is changed or added for each modification. Please modify
the rule ’h’. Generate num rules for each type of modification (Quantifier
change, Additional attribute, Attribute change) so that the following
structure is text_y a good structure: x Note that the number of the blocks do
not matter. Make the format a numbered list (1., 2., …, 15.) Remember that the
new rules should be a ”local” modification from the rule ’h’. Do not use
attribute values that are not mentioned earlier. Do not say anything other
than the modified rules.
---
Table 2: Prompts used for the local proposer $q(h_{evolved}|h_{original},x,y)$
of online inferece methods A structure has one or more blocks. Each block
should contain the following attributes: color (blue/red/green) size
(small/medium/large) orientation (upright/left/right/strange) groundedness
(grounded/ungrounded), touching (which other blocks they do and do not touch).
Consider the following rule: ’h’ Given a structure, the output is yes if it
follows the rule (or is a good structure) and no if it does not (or is a bad
structure) The given rule gives incorrect output for the following structures:
feedback Based on the given rule, generate num new refined rules that fix the
outputs for all mentioned structures. The new rules may involve any of the
mentioned attributes (color, size, orientation, grounded, touching). Please
number them from 1-num and do not say anything else
---
Table 3: Prompts used for refinement (in batch inference with refinement with hard rules) Initial prompt |  You are playing an inductive game with me. I’ll be the moderator, and your task is to figure out the secret rule that I know by coming up with a structure of blocks to ask me whether it conforms with the secret rule or not. The structure has one of more blocks. Each block should contain the following attributes: color (blue/red/green) size (small/medium/large) orientation (upright/left/right/strange) groundedness (grounded/ungrounded), touching (which other blocks they do and do not touch). To give you a start, I’ll describe one structure that follows the rule: text_c Give a very short summary on what you currently think the secret rule is.
---|---
Follow-up prompt |  The verdict on whether the queried structure follows the rule is {verdict}. Give a very short summary on what you currently think the secret rule is.
Active learning (experiment) prompt |  Give one structure you want to test whether it follows the secret rule or not. Do not include anything other than the structure.
Table 4: Prompts used for vanilla, direct LLM method