# In-Context Learning Dynamics
with Random Binary Sequences

Eric J. Bigelow1,2 , Ekdeep Singh Lubana2,3,4, Robert P. Dick4,
Hidenori Tanaka2,3, Tomer D. Ullman1,2

1Psychology Department, Harvard University, Cambridge, MA, USA
2Center for Brain Science, Harvard University, Cambridge, MA, USA
3Physics & Informatics Laboratories, NTT Research, Inc., Sunnyvale, CA, USA
4EECS Department, University of Michigan, Ann Arbor, MI, USA
Correspondence to<EMAIL_ADDRESS>
###### Abstract

Large language models (LLMs) trained on huge corpora of text datasets
demonstrate complex, emergent capabilities, achieving state-of-the-art
performance on tasks they were not explicitly trained for. The precise nature
of LLM capabilities is often mysterious, and different prompts can elicit
different capabilities through in-context learning. We propose a Cognitive
Interpretability framework that enables us to analyze in-context learning
dynamics to understand latent concepts in LLMs underlying behavioral patterns.
This provides a more nuanced understanding than success-or-failure evaluation
benchmarks, but does not require observing internal activations as a
mechanistic interpretation of circuits would. Inspired by the cognitive
science of human randomness perception, we use random binary sequences as
context and study dynamics of in-context learning by manipulating properties
of context data, such as sequence length. In the latest GPT-3.5+ models, we
find emergent abilities to generate pseudo-random numbers and learn basic
formal languages, with striking in-context learning dynamics where model
outputs transition sharply from pseudo-random behaviors to deterministic
repetition.

##  1 Introduction

Large language models (LLMs) achieve high performance on a wide variety of
tasks they were not explicitly trained for, demonstrating complex, emergent
capabilities (Brown et al., 2020; Radford et al., 2019; Wei et al., 2022a;
2023; b; Lu et al., 2023; Bommasani et al., 2021; Wei et al., 2021; Kojima et
al., 2022; Pan et al., 2023; Pallagani et al., 2023; Li et al., 2022). In-
context learning (ICL) describes how task-specific patterns of behavior are
elicited in LLMs by different prompts (or contexts) (Brown et al., 2020; Wei
et al., 2022b; Dong et al., 2022; Zhou et al., 2022; Wang et al., 2023; Shin
et al., 2022; Min et al., 2022; Si et al., 2023; Xie et al., 2022; Zhang et
al., 2023b). Although no weight updates occur in ICL, different input contexts
can activate, or re-weight, different latent algorithms in an LLM, analogous
to updating model parameters to learn representations in traditional gradient
descent learning methods (Goldblum et al., 2023; Dai et al., 2023; Ahn et al.,
2023; Von Oswald et al., 2023; Akyürek et al., 2022; Li et al., 2023a). Two
seemingly equivalent prompts can, however, evoke very different behaviors in
LLMs (Si et al., 2023). ICL makes interpreting what representations in an LLM
are being evoked by a given input more challenging than interpreting
representations in task-specific language models, where the space of
capabilities is more restricted and well-defined. Our central motivation is to
interpret emergent capabilities and latent concepts underlying complex
behaviors in LLMs by analyzing in-context learning behavioral dynamics,
without directly observing hidden unit activations or re-training models on
varied datasets.

Inspired by computational approaches to human cognition (Tenenbaum, 1998;
Griffiths & Tenenbaum, 2003; Piantadosi et al., 2012; Spivey et al., 2009), we
model and interpret latent concepts evoked in LLMs by different contexts,
without observing or probing model internals. This approach, which we call
Cognitive Interpretability (see Fig. 1), is a middle ground between shallow
test-set evaluation benchmarks on one hand (Srivastava et al., 2022; Saparov &
He, 2022; Min et al., 2022; Lanham et al., 2023; Ganguli et al., 2023; Bowman
et al., 2022; Kadavath et al., 2022; Perez et al., 2022; Prystawski & Goodman,
2023; Turpin et al., 2023) and mechanistic neuron- and circuit-level
understanding of pre-trained model capabilities on the other (Nanda et al.,
2023; Goh et al., 2021; Geva et al., 2020; Belinkov, 2022; Li et al., 2022;
Wang et al., 2022; Chughtai et al., 2023; Gurnee et al., 2023; Foote et al.,
2023; Lubana et al., 2023; Lieberum et al., 2023; Barak et al., 2022; Liu et
al., 2022b; Zhong et al., 2023). The reliance on benchmarks loosely parallels
early behaviorist psychology, when theories of human and animal learning only
assumed stimulus-response associations, without positing theories about mental
processes or neural substrates (Gardner, 1987). Circuit-level mechanistic
interpretations of neural networks parallel neurobiology, which offers
physical models of information processing in biological neurons, but typically
does not account for the structure of high-level behavior. Cognitive
interpretability, like cognitive science, seeks to predict behavioral outcomes
over a potentially infinite space of possible tasks. It defines high-level
specifications of behaviors performed by LLMs, which, we argue, should be the
first step before a mechanistic understanding of model circuits is pursued.

Here, we focus on cognitive interpretability of LLMs in the domain of random
sequences of binary values. Random binary sequences are a minimal domain that
has been studied extensively in statistics, formal language theory, and
algorithmic information theory (Sipser, 1996; Chaitin, 1966; Li et al., 1997).
We use this domain to systematically test few-shot learning as a function of
context length $|x|$ across different binary token sequences $x$. We also test
zero-shot learning by having models generate sequences with no context
($|x|=0$), without relying on alternate prompt formats such as chain-of-
thought reasoning (Kojima et al., 2022; Wei et al., 2022b). Moreover, language
generation trajectories over binary sequences can also be analyzed and
visualized much more easily than typical user-chatbot interaction trajectories
(Zhang et al., 2023a; Berglund et al., 2023), since the token-by-token
branching factor is only two. Random binary sequences have also been a target
domain in cognitive science (specifically, subjective randomness), where
researchers have studied the mechanisms and concepts that underlie how people
generate random binary sequences or evaluate the randomness of given sequences
(Falk & Konold, 1997; Tversky & Gilovich, 1989; Griffiths et al., 2018).

Figure 1: Cognitive Interpretability in the context of prior work Cognitive
Interpretability studies in-context learning dynamics in LLMs, positing
theories of the latent concepts enabling behavioral capabilities. It is a
middle ground between behavioral benchmarks, which treat models as black boxes
and evaluate hit-or-miss accuracy, and mechanistic interpretability, which
studies toy models and training loss dynamics, analogous to how cognitive
science is a middle ground between behaviorist psychology and neurobiology.

Computational cognitive scientists have related algorithmic information theory
to human cognition, where mental concepts are viewed as programs, and
cognitive hypothesis search over concepts is viewed as Bayesian inference (or
Bayesian program learning) (Chater & Vitányi, 2003; Dehaene et al., 2022;
Piantadosi et al., 2012; Goodman et al., 2008; Ullman et al., 2012; Ullman &
Tenenbaum, 2020). In this vein, Griffiths & Tenenbaum (2003) and Griffiths et
al. (2018) model subjective randomness in human cognition as probabilistic
program induction, where a person must search over a space of non-random
programs to answer the question, “was this sequence generated by a random
process?” We argue that ICL can similarly be seen as under-specified program
induction, where there is no single “correct” answer; instead, an LLM should
appropriately re-weight latent algorithms. The domain of random sequences
reflects this framing, in contrast to other behavioral evaluation
methodologies, in that there is no correct answer to a random number
generation or judgment task (Fig. 3). If the correct behavior is to match a
target random process, then the best way to respond to the prompt Generate N
flips from a fair coin is a uniform distribution over the tokens Heads and
Tails, instead of a specific ground truth token sequence. If instead the
correct behavior is to match how humans generate random sequences, the LLM
must represent a more complex algorithm that matches the algorithm presumably
used by people. Overall, we make the following contributions in this work:

  * •

Evaluating ICL as Bayesian model selection in a practical setting. We find
evidence of in-context learning operating as Bayesian model selection in LLMs
in the wild, compared to prior work that trains smaller toy neural networks
from scratch.

  * •

Subjective Randomness as a domain for studying ICL dynamics. We introduce a
new domain, subjective randomness, which is rich enough to be theoretically
interesting, but simple enough to enable analysis of complex behavioral
patterns.

  * •

Sharp transitions in abilities to generate pseudo random numbers. We
systematically analyze in-context learning dynamics in LLMs without observing
or updating model weights, demonstrating sharp phase-changes in model
behavior. This is a minimal, interpretable example of how the largest and most
heavily fine-tuned LLMs can suddenly shift from one pattern of behavior to
another during text generation.

##  2 Preliminaries: Bayesian Inference and In-Context Learning

Figure 2: Overview of our modeling framework. Given a pre-trained Large
Language Model, we systematically vary input context prompts, in this case
$x=(001)^{n}$ with $n=\\{2,4\\}$ (001001, 001001001001). LLM outputs $y$
(Bottom) significantly as a function of $x$ (Top), based on some unknown
latent concept space embedded in the LLM. We model a subset of the algorithms
embedded in the LLM’s latent concept space $\mathcal{H}$ that are invoked by
ICL (Middle), to predict the LLM outputs $y$. With very little context (Left),
GPT-3.5+ generates subjectively random sequences, whereas with enough context
matching a simple formal language
($x=\texttt{001001001001}=(\texttt{001})^{4}$), it begins deterministically
repeating patterns in $x$.

A multi-layer neural networks may possess multiple distributed circuits
implementing computational primitives, such as basic mathematical operations
like addition and sequence copying (Olsson et al., 2022; Nanda et al., 2023;
Hanna et al., 2023; Zhong et al., 2023; Chan et al., 2022; Bietti et al.,
2023). In state-of-the-art LLMs with hundreds of billions (even trillions) of
parameters, there may be sub-networks implementing various computations, and a
wide variety of emergent behaviors corresponding to those computations. A
similar situation occurs in research focused on understanding the human brain,
where sub-networks of neuronal cells have been shown to localize specific
capabilities. In cognitive science, researchers study such aspects of
cognition without fully understanding the underlying neural circuitry, often
modeling behavior without observing brain activity. Analogously, we seek to
understand the structure of behaviors in LLMs in the wild, without a full
mechanistic understanding of their circuitry.

Bayesian inference is a key methodological tool of cognitive modeling, and
recent work has framed in-context learning as Bayesian inference over models
(Xie et al., 2022; Li et al., 2023b; Hahn & Goyal, 2023). Specifically, the
posterior predictive distribution $p(y|x)$ in these works describes how an LLM
produces output tokens $y$, given the context tokens, or prompt, $x$. The key
assumption is that a context $x$ will activate latent concepts $c$ within a
model according to their posterior probability $p(c|x)$, which the model
marginalizes over to produce the next token $y$ by sampling from the posterior
predictive distribution: $p(y|x)=\int_{c\in\mathcal{C}}p(y|c)\ p(c|x)$. This
Bayesian model selection takes place in network activation dynamics, without
changing model weights.

Following the framing above, in our experiments we assume a hypothesis space
$\mathcal{H}$ that approximates the latent space of LLM concepts used when
predicting the next token, i.e.,

$p(y|x)=\sum_{h\in\mathcal{H}}p(y|h)\ p(h|x),$

where $\sum_{h}$ can be changed to $\max_{h}$ to represent deterministic
greedy decoding with an LLM temperature parameter of 0. If we assume that an
LLM operates over next-token prediction only, then each generated token
$y_{t-1}$ will be appended to the context when the following token is sampled,
i.e. $y_{t}\sim p(y_{t}|x,y_{t-1})$. We specifically focus on Bernoulli
processes, regular languages, Markov chains, and a simple memory-constrained
probabilistic model as candidates for the hypothesis space $\mathcal{H}$ for
estimating LLM concepts in random binary sequences. These candidates capture a
variety of behavioral patterns with varying complexity: Bernoulli processes
serve as a baseline for a true random coin flip, where all elements in a
sequence are independent and identically distributed; Markov chains are
commonly used models that represent serial correlation patterns; the Gambler’s
Fallacy bias in cognitive science (described below) emerges from a simple
memory-limited model that draws the sequence towards a specified probability,
dependent based on previous samples; and regular languages are well studied in
theoretical computer science (Sipser, 1996; Chomsky, 1956), representing a
simple class of non-random programs with known mechanisms of finite state
automata (or, equivalently, finite state Markov processes). We use a subset of
regular languages $(x)^{n}$, where $(x)$ is a short sequence of values, e.g.,
$(\texttt{010})^{n}$, where $0$ maps to Heads and $1$ to Tails.

#### Learning Dynamics in Model Selection

Cognitive scientists have used Bayesian predictive and posterior distributions
to model learning dynamics in human adults and children, as well as in non-
human animals (Tenenbaum, 1998; Goodman et al., 2008; Ullman & Tenenbaum,
2020). A discrete hypothesis space in a probabilistic model can give clear and
meaningful explanations to learning patterns analogous to mode collapse and
phase transitions in deep learning. When behavior suddenly shifts from one
pattern, or mode, of behavior to another, this can be understood as one
hypothesis coming to dominate the posterior $p(h|x)$ as $x$ grows in scale
(Ullman et al., 2012). For example, children 3.5–5 years old learning to count
undergo a dramatic conceptual shift from knowing the meanings of only a few
number words (“one”, “two”) to a full inductive understanding of counting,
which can be modeled as Bayesian model selection with a simplicity prior over
models (Piantadosi et al., 2012). Such cognitive analysis of behavioral shifts
as generated from a shift in posterior probability between one hypothesis to
another parallels recent work on learning dynamics in training and prompting
LLMs. E.g., sharp phase changes have been observed when training neural
networks, corresponding to the formation of identifiable mechanisms such as
modular addition circuits or induction heads (Nanda et al., 2023; Olsson et
al., 2022; Zhong et al., 2023; Bai et al., 2023). ICL research has explored
how few-shot prompting can significantly boost LLM performance in various
domains, and how the particular exemplars provided in context determine its
overall effectiveness (Brown et al., 2020; Zhao et al., 2020; 2021; Min et
al., 2022; Lu et al., 2021; Zhou et al., 2022; Turpin et al., 2023). Work on
chain-of-thought reasoning in LLMs demonstrates how a few exemplars of
detailed solutions or even a simple prompt like “let’s think this through
step-by-step” can dramatically impact model performance (Wei et al., 2022b;
Kojima et al., 2022; Srivastava et al., 2022). For further discussion of
related work, see Appendix A.

##  3 Algorithmic and Subjective Randomness

Next, we describe the domain of randomness explored in this work, and provide
relevant background from computational cognitive science. To build intuition,
consider: which sequence of coin flips is more random, $\mathtt{TTHTHHTH}$ or
$\mathtt{HTTTTTTT}$? While the odds of a fair coin producing either sequence
are the same (1 in 256), most people say that the first sequence “looks more
random”. In a bias termed the Gambler’s Fallacy, people reliably perceive
binary sequences with long streaks of one value as less random, and judge
binary sequences with higher-than-chance alternation rates as being “more
random” than truly random sequences (Falk & Konold, 1997). In addition to not
using simple objective measures when judging the randomness of sequences,
people also have a hard time generating sequences that are truly random
(Oskarsson et al., 2009; Griffiths et al., 2018; Gronchi & Sloman, 2021;
Meyniel et al., 2016; Planton et al., 2021).

Figure 3:  Determining whether a sequence is random can be viewed as search
for a simple program that could generate that sequence. $\mathtt{HTTTTTTT}$
can be described with a short deterministic program $\mathtt{simpleSequence}$,
and has a higher $p(h)$ according to a simplicity prior, compared to
$\mathtt{TTHTHHTH}$ and $\mathtt{complexSequence}$. Both sequences can be
generated by $\mathtt{randomSequence}$, but with lower likelihood $p(x|h)$.

Cognitive scientists studying Subjective Randomness model how people perceive
randomness, or generate data that is subjectively random but algorithmically
pseudo-random, and have related this problem to algorithmic information
theoretic definitions of randomness. One way to study this is to ask people
whether a given data sequence was more likely to be generated by a Random
process or a Non-Random process (Fig. 3). $\mathtt{HTTTTTTT}$ might be
described with a shorter program—one H followed by seven Ts – than
$\mathtt{HTTHTHHT}$, which cannot be compressed as well—H followed by two Ts,
then one H, then one T, then two Hs, then one T. Viewing this task as program
induction, a natural prior $p(h)$ over program hypotheses assigns higher
weights to programs with shorter description lengths, or lower complexity.
Searching for the shortest program consistent with data $x$ is equivalent to
computing the Kolmogorov complexity of a sequence $K(x)$ (Li et al., 1997) and
has motivated the use of “simplicity priors” in a number of domains in
computational cognitive science Chater & Vitányi (2003); Goodman et al.
(2008); Piantadosi et al. (2012).

Following previous work (Griffiths & Tenenbaum, 2003; Griffiths et al., 2018),
here we define subjective randomness of a sequence as the ratio of likelihood
of that sequence under a random versus non-random model, i.e.,
$\mathtt{randomness}(x)=\log P(x|\mathtt{random})\ -\ \log
P(x|\mathtt{non}\text{-}\mathtt{random})$. The likelihood given a truly random
Bernoulli process will be $p(x|\mathtt{random})=2^{-|x|}$, since each of
$2^{|x|}$ binary sequences of length $|x|$ has equal probability. The non-
random likelihood $p(x|\mathtt{non}\text{-}\mathtt{random})=2^{-K(x)}$ denotes
the probability of the minimal description length program that generates $x$,
equivalent to Bayesian model selection:
$P(x|\mathtt{non}\text{-}\mathtt{random})=\max_{h\in\mathcal{H}}p(x|h)\ p(h)$.
In theory, the space $\mathcal{H}$ of non-random models encompasses every
possible computation; in this work, we study a small subset of this space that
includes formal languages and probabilistic models inspired by psychological
models of human concept learning and subjective randomness (Griffiths et al.,
2018; Nickerson, 2002; Hahn & Warren, 2009). For further background, see
Appendix H.

##  4 Experiments

Figure 4: Prompt templates and GPT-3.5 Randomness Judgments (Left) Prompt
templates used for the Randomness Generation (Top) and Judgment (Bottom)
tasks. $\\{\mathtt{sequence}\\}$ is substituted with a list of context flips
$x$, e.g. $\mathtt{Heads,\,Tails,\,Tails,\,Heads}$. $\\{\mathtt{p}\\}$ is
substituted with the probability of Tails, and $\\{\mathtt{1-p}\\}$ with the
probability of Heads. (Right) In Randomness Judgment tasks, we observe sharp
transitions in the predictive distribution $p(y=\mathtt{random}|x)$ for
GPT-3.5, from high-confidence in $x$ being generated by a random process, to
high confidence in a non-random algorithm, as additional data $x$ is provided
from the same concept.

#### Randomness Generation and Judgment Tasks

In order to assess text generation dynamics and in-context concept learning,
we evaluate LLMs on random sequence Generation tasks , analyzing responses
according to simple interpretable models of Subjective Randomness and Formal
Language Learning. In these tasks, the model generates a sequence $y$ of
binary values, or flips, comma-separated sequences of Heads or Tails tokens.
We also analyze a smaller set of randomness Judgment tasks, with the prompt:
Is the following sequence of coin flips generated by a random process with no
pattern, or are they generated by a non-random algorithm?. In both cases, $y$
is a distribution over tokens with two possible values. Outputs $y$ consist of
a single Random or Non token, indicating whether the sequence was generated by
a random process with no correlation, or some non-random algorithm. We analyze
dynamics in LLM-generated sequences $y$ simulating a weighted coin with
specified $p(\mathtt{Tails})$, with $|x|\approx 0$. An initial flip
‘$\mathtt{Heads}$’ is used so the model’s flips will be formatted
consistently. Prompt context in these experiments includes a specific
probability, shown in Fig. 4, where the last __ marks where the model begins
generating tokens $y$. We collect 200 output sequences $y$ for each LLM at
each $P(Tails)\in[.05,.1,.2,.3,.4,.49,.5,.51,.60,.70,.80,.90,.95]$, cropping
output tokens to $|y|=50$ to limit cost and for simplicity. Temperature
parameters are set to 1, and other parameters follow OpenAI API defaults; see
Appendix B for more details.

In the Judgment task, $x$ includes the prompt question and the full sequence
of flips. We systematically vary prompt context $x$ by varying the number of
flips, denoted $|x|$. We test few-shot learning in LLMs by evaluating output
behavior on specific bit sequences, for example $(\texttt{01})^{n}$ with
varying $n$ (e.g. “$\mathtt{Heads,\,Tails,\,Heads,\,Tails,\,\dots}$”), as well
as zero-shot language generation dynamics when $x$ is empty and $|x|=0$ (in
practice, we initialize $x$ with a single flip to help the LLM match the
correct format). Unlike typical cases of few-shot learning, where high-
variance samples (‘shots’) are drawn from a broad category such as “chain-of-
thought solutions” (Wei et al., 2022b; Brown et al., 2020), all data in a
sequence $x$ corresponds to a single unobserved program.

#### Subjective Randomness Models

We compare LLM-generated sequences to a ground truth “random” Bernoulli
distribution with the same mean ($\mu=\overline{y}_{\text{LLM}}$), to a simple
memory-constrained probabilistic model, and to Markov chains fit to model-
generated data $y$. The Gambler’s Fallacy is the human bias to avoid long runs
of a single value (‘Heads’ or ‘Tails’) consecutively in a row (Falk & Konold,
1997; Nickerson, 2002). Hahn & Warren (2009) theorize that the Gambler’s
Fallacy emerges as a consequence of human memory limitations, where ‘seeming
biases reflect the subjective experience of a finite data stream for an agent
with a limited short-term memory capacity’. We formalize this as a simple
Window Average model, which tends towards a specific probability $p$ as a
function of the last $w$ flips:
$p(y|x)=\max(0,\min(1,2p-\overline{x}_{t-w\ldots t}))$ .

#### Sub-Sequence Memorization and Complexity Metrics

Bender et al. (2021) raise the question of whether LLMs are ‘stochastic
parrots’ that simply copy data from the training set. We test the extent to
which LLMs generate pseudo-random sequences by arranging memorized patterns of
sub-sequences, rather than according to a more complex algorithm as our Window
Average model represents. To measure memorization, we look at the distribution
of unique sub-sequences in $y$. If an LLM is repeating common patterns across
outputs, potentially memorized from the training data, this should be apparent
in the distribution over length K sub-sequences. Since there are deep
theoretical connections between complexity and randomness (Chaitin, 1977;
1990), we also consider the complexity of GPT-produced sequences. Compression
is a metric of information content, and thus of redundancy over irreducible
complexity (MacKay, 2003; Delétang et al., 2023), and neural language models
have been shown to prefer generating low complexity sequences (Goldblum et
al., 2023). As approximations of sequence complexity, we evaluate the
distribution of Gzip-compressed file sizes (Jiang et al., 2022) and inter-
sequence Levenshtein distances (Levenshtein et al., 1966).

Figure 5: GPT-3.5 generates pseudo-random binary sequences that deviate from a
Bernoulli process. (Left) Empirical conditional probabilities for a third-
order Markov Chain fit to sequences $y$ generated by GPT-3.5 text-davinci-003,
a Bernoulli process centered at the mean of GPT sequence $\overline{y}$, and
our Window Average model ($w=5$). In the simulated Bernoulli process, edges
are fairly uniform; the conditional probabilities for GPT-3.5 and the Window
Average model demonstrate a similar non-uniform bias. (Right) Running averages
for flip sequences generated by each model, where $0$ denotes
‘$\mathtt{Heads}$’ and $1$ denotes ‘$\mathtt{Tails}$’. Compared to a Bernoulli
process (top), sequences generating using GPT (middle) and those of our Window
Average model (bottom) stay closer to the mean, repeating the same patterns
more often.

#### Formal Language Learning Metrics

In our Formal Language Learning analysis, $x$ is a subset of regular
expression repetitions of short token sequences such as
$x\in(\texttt{011})^{n}$, where longer sequences $x$ correspond to larger $n$.
This enables us to systematically investigate in-context learning of formal
languages, as $|x|$ corresponds to the amount of data for inducing the correct
program (e.g. $(\texttt{011})^{n}$) from Bernoulli processes, as well as the
space of all possible algorithms. A Markov chain of sufficiently high order
$k$ can implicitly represent a regular language in its weights. However, the
number of parameters required is exponential in Markov order $k$, and weights
are difficult to interpret. For example, a 3-order Markov chain fit to data
$x=(\texttt{011})^{n}$ will represent $(\texttt{011})^{n}$ corresponds to high
weights in the conditional probability distribution for
$p(\texttt{0}|\texttt{11})$, $p(\texttt{1}|\texttt{01})$,
$p(\texttt{1}|\texttt{10})$, and low values for other conditional
probabilities. We define the LLM predictive distribution $p(y|x)$ based on LLM
next-token prediction probabilities: $p(y_{0\ldots
T}|x)=p(y_{0}|x)\prod_{t}^{T}p(y_{t}|y_{0,\ldots t-1},x)$. In randomness
Judgment tasks, we assess formal concept learning dynamics in the predictive
distribution $p(y=\mathtt{random}|x=C^{|x|})$ as a function of context length
$|x|$. In randomness Generation tasks, we asses concept learning according to
the predictive $p(y|x)$ over binary sequence continuations. Given a space of
possible outputs $y$ with length $d$, $y\in\\{0,1\\}^{d}$, we estimate
$p(y|x)$ by enumerating all $y$ up to some depth $d$, and computing
$\hat{p}(y_{d}|x,y_{1,\ldots,d-1})=\frac{1}{N}\sum_{i}^{N}(y_{d}==1)^{(i)}$ as
the fraction of $N$ responses that are “Tails”. We use token-wise log
probabilities $p(y_{t}|y_{0\ldots t-1})$ from the OpenAI API where available
for cost efficiency and since this is equivalent to repeated token samples.
The probability table for $p(y_{t}|y_{0,\ldots t-1})$ is a weighted binary
tree with depth $d$, where edges represent the next-token probability
$p(y_{t}|y_{t-1})$, and paths represent the probability of a sequence of
tokens. We estimate the predictive probability $p(y_{t}\in
C|x,y_{0\ldots,t-1})$ assigned to a given regular language by computing the
total probability mass for all paths in $y_{0\ldots d}$ that exactly match
$C$. For example, with $C=(\texttt{011})^{n}$, there will be 3 paths
$y_{0\ldots d}$ that exactly match $C$, out of $2^{d}$ possible unique paths.

##  5 Results

###  5.1 Subjectively Random Sequence Generation

Figure 6: GPT-3.5 shows a Gambler’s fallacy bias of avoiding long runs. (Top)
Distribution of mean values of flip sequences ($\mu=\frac{1}{T}\sum_{t}y_{t}$)
generated by GPT-3.5 (text-davinci-003) with the specified $p(Tails)$,
compared with a Bernoulli process and our Window Average model with the same
mean as the GPT-3.5 flips. Flips generated by GPT approximately follow the
expected mean $p(Tails)$, but have lower variance than a Bernoulli
distribution. (Bottom) Length of the longest run for each sequence, where a
run is a sub-sequence of the same value repeating. In this case, we see a
clear bias in GPT-3.5 to avoid long runs, with a similar pattern across all
values of $p(Tails)$ despite the x-axis changing in scale.

In the GPT3.5 and higher (‘InstructGPT’) models — text-davinci-003, ChatGPT
(gpt-3.5-turbo, gpt-3.5-turbo-instruct) and GPT-4 — we find an emergent
behavior of generating seemingly random binary sequences (Fig. 5). This
behavior is controllable, where different $p(\mathtt{Tails})$ values leads to
different means of generated sequences $\overline{y}$. However, the
distribution of sequence means, as well as the distribution of the length of
the longest runs for each sequence, deviate significantly from a Bernoulli
distribution centered at $\overline{y}$, analogous to the Gambler’s Fallacy
bias in humans (see Fig. 6). Our Window Average model with a window size of
$w=5$ partly explains both biases, matching GPT-generated sequences more
closely than a Bernoulli distribution.

For brevity, in the following sections we primarily analyze the behavior of
text-davinci-003, referring to it simply as ‘GPT-3.5’, and GPT models
including this and more recent LLMs, as ‘GPT-3.5+’. Our cross-LLM analysis
shows that text-davinci-003 is controllable with $P(\mathtt{Tails})$, with a
bias towards $\overline{y}=.50$ and higher variance in sequence means (though
lower variance than a true Bernoulli process). Both versions of ChatGPT we
analyze (versions gpt-3.5-turbo-0301 and 0613) demonstrate similar behavior
for $P(\mathtt{Tails})<50\%$, but behave erratically with higher
$P(\mathtt{Tails})$ and the majority of sequences $y$ converge to repeating
‘$\mathtt{Tails}$’. Both versions of GPT-4 show stable, controllable
subjective randomness behavior, where sequence means $\overline{y}$ closely
follow the specified $P(\mathtt{Tails})$, but have even lower variances than
sequences generated by text-davinci-003. Earlier models do not show subjective
randomness behavior, with text-davinci-002 and text-davinci-001 being heavily
biased and uncontrollable, and text-curie-001 generates sequences with
$\overline{y}=.50$ regardless of $P(\mathtt{Tails})$. Also see Appendix E.

###  5.2 Sub-Sequence Memorization and Complexity

Figure 7: GPT repeats specific sub-sequences more often than chance. We find
that GPT-3.5 repeats certain sub-sequences more often than is predicted by our
Window Average model. While the Window Average model (green) generates fewer
unique sub-sequences than a Bernoulli process (red), this does not account for
the bias in GPT-3.5 (text-davinci-003, in blue) to repeat many of the same
sub-sequences. This disparity increases with longer sub-sequences (see Fig. 20
in Appendix).

We find significant differences between the distributions of sub-sequences for
GPT-3.5 -generated sequences and sequences sampled from a Bernoulli
distribution(see Fig. 7). This difference is partly accounted for with a
Window Average model with a window size $w=5$, although GPT repeats certain
longer sub-sequences, for example length-20 sub-sequences, that are far longer
than 5. However, the majority of sub-sequences have very low frequency, and
though further experiments would be required to conclude that all sub-
sequences are not memorized from training data, it seems unlikely that these
were in the training set, since we find thousands of unique length-k (with
varying k) sub-sequences generated at various values of $P(\mathtt{Tails})$.
This indicates that GPT-3.5 combines dynamic, subjectively random sequence
generation with distribution-matched memorization. We also note that with a
specification of $P(Tails)=50\%$, but not $49\%$, $51\%$ or other values,
sequences $y$ generated by GPT-3.5+ are dominated by repeating ‘Heads, Tails,
Heads, Tails, …’. This pattern is consistent across variations of the prompts
listed in Fig. 4, including specifying ‘fair’ or ‘unweighted’ instead of a
‘weighted coin’, and produces a visible kink in many cross-$p(\mathtt{Tails})$
metrics (Fig. 23, 22, 19). For this reason, in Fig. 6 we show results for
$P(Tails)=51\%$.

Across three metrics of sequence complexity — number unique sub-sequences,
Gzip file size, and inter-sequence Levenshtein distance (see Fig. 23, 22 in
Appendix) — we find that GPT-3.5+ models, with the exception of ChatGPT,
generate low complexity sequences, showing that structure is repeated across
sequences and supporting Goldblum et al. (2023); Delétang et al. (2023). By
the metrics of mean Levenshtein distance and number of unique sub-sequences,
ChatGPT generates higher complexity sequences than chance. We speculate that
this phenomenon might explained by a cognitive model that avoids sampling with
replacement.

Figure 8: With enough context, GPT-3.5 learns simple formal language concepts,
transitioning from generating pseudo-random numbers to only generating values
from the concept (Left) GPT-3.5 next-token predictive distribution $p(y|x)$
visualized as a binary tree, where red arrows correspond to Heads, blue arrows
to Tails, and nodes matching the target concept $C=(011)^{n}$ are green.
$p(y|x)$ changes with varying $|x|$, here $|x|=39$ and next-token predictions
strongly follow the concept $C$. Also see Fig 11, 12 in Appendix. (Right) In-
context learning dynamics for simple formal languages $x=(\texttt{HTH})^{n}$
(010) and $x=(\texttt{HTT})^{n}$ (011) as a function of context length
$n=|x|$. Prediction accuracy computed as the total probability mass assigned
to valid continuations of the formal language $x$, as a function of prediction
depth $d=|y|$ and context length $|x|$. Curves shown are for $d=6$, where only
3 out of 64 total paths $y$ match concept $C$. Solid lines correspond to text-
davinci-003 and dashed lines to gpt-3.5-turbo-instruct; note that learning
curves for 010 and 011 flip between the two models. Also see Fig. 9, 10 in
Appendix.

###  5.3 Distinguishing Formal Languages from Randomness

GPT-3.5 sharply transitions between behavioral patterns, from generating
pseudo-random values to generating non-random sequences that perfectly match
the formal language (Fig. 8). We observe a consistent pattern of formal
language learning in GPT-3.5 generating random sequences where predictions
$p(y|x)$ of depth $d\geq 4$ are initially random with small $|x|$, and have
low $p(y\in C|x)$ where $C$ is a given concept. This follows whether the
prompt describes the process as samples from “a weighted coin” or “a non-
random-algorithm”. We also find sharp phase changes in GPT-3.5 behavioral
patterns in Randomness Judgment tasks across 9 binary concepts (Fig. 4). These
follow a stable pattern of being highly confident in that the sequence is
Random (high $p(y=\mathtt{random}|x$) when $x$ is low, up to some threshold of
context at which point it rapidly transitions to being highly confident in the
process being non-random. Transition points vary between concepts, but the
pattern is similar across concepts (also see Fig. 13, 14 in Appendix).

##  6 Conclusion

We find strong patterns of random number Generation and Judgment in LLMs,
including an emergent ability to generate low-variance pseudo-random binary
sequences that can be partly explained with a memory-constrained moving window
model, and partly as memorization and compression. We also find striking
behavioral phase changes when GPT-3.5 learns to distinguish simple formal
language concepts from randomness. This supports theories of ICL as Bayesian
model selection and as under-specified program induction, and demonstrates how
LLM behavioral patterns can change non-linearly with ICL as a function of
context data. Future Cognitive Interpretability work may characterize concept
learning dynamics underlying other LLM capabilities, including those with
applications in usability and safety. If ICL is indeed analogous to hypothesis
search in human cognition (or, equivalently, under-specified program
induction) where new concepts can be learned in-context or computed in text
generation trajectories, with no changes to model weights, a compelling
research direction would be to further understand the features and limits of
in-context learning dynamics using theories and tools from computational
cognitive science.

## References

  * Ahn et al. (2023) Kwangjun Ahn, Xiang Cheng, Hadi Daneshmand, and Suvrit Sra.  Transformers learn to implement preconditioned gradient descent for in-context learning.  _arXiv preprint arXiv:2306.00297_ , 2023.
  * Akyürek et al. (2022) Ekin Akyürek, Dale Schuurmans, Jacob Andreas, Tengyu Ma, and Denny Zhou.  What learning algorithm is in-context learning? investigations with linear models.  _arXiv preprint arXiv:2211.15661_ , 2022.
  * Allen-Zhu & Li (2023) Zeyuan Allen-Zhu and Yuanzhi Li.  Physics of language models: Part 1, context-free grammar.  _arXiv preprint arXiv:2305.13673_ , 2023.
  * Bai et al. (2023) Yu Bai, Fan Chen, Huan Wang, Caiming Xiong, and Song Mei.  Transformers as statisticians: Provable in-context learning with in-context algorithm selection.  _arXiv preprint arXiv:2306.04637_ , 2023.
  * Barak et al. (2022) Boaz Barak, Benjamin Edelman, Surbhi Goel, Sham Kakade, Eran Malach, and Cyril Zhang.  Hidden progress in deep learning: Sgd learns parities near the computational limit.  _Advances in Neural Information Processing Systems_ , 35:21750–21764, 2022.
  * Belinkov (2022) Yonatan Belinkov.  Probing classifiers: Promises, shortcomings, and advances.  _Computational Linguistics_ , 48(1):207–219, 2022\.
  * Bender et al. (2021) Emily M Bender, Timnit Gebru, Angelina McMillan-Major, and Shmargaret Shmitchell.  On the dangers of stochastic parrots: Can language models be too big?  In _Proceedings of the 2021 ACM conference on fairness, accountability, and transparency_ , pp. 610–623, 2021.
  * Berglund et al. (2023) Lukas Berglund, Asa Cooper Stickland, Mikita Balesni, Max Kaufmann, Meg Tong, Tomasz Korbak, Daniel Kokotajlo, and Owain Evans.  Taken out of context: On measuring situational awareness in llms.  _arXiv preprint arXiv:2309.00667_ , 2023.
  * Bhattamishra et al. (2020) Satwik Bhattamishra, Kabir Ahuja, and Navin Goyal.  On the ability and limitations of transformers to recognize formal languages.  _arXiv preprint arXiv:2009.11264_ , 2020.
  * Bietti et al. (2023) Alberto Bietti, Vivien Cabannes, Diane Bouchacourt, Herve Jegou, and Leon Bottou.  Birth of a transformer: A memory viewpoint.  _arXiv preprint arXiv:2306.00802_ , 2023.
  * Bigelow & Piantadosi (2016) Eric Bigelow and Steven T Piantadosi.  Inferring priors in compositional cognitive models.  In _CogSci_ , 2016.
  * Bommasani et al. (2021) Rishi Bommasani, Drew A Hudson, Ehsan Adeli, Russ Altman, Simran Arora, Sydney von Arx, Michael S Bernstein, Jeannette Bohg, Antoine Bosselut, Emma Brunskill, et al.  On the opportunities and risks of foundation models.  _arXiv preprint arXiv:2108.07258_ , 2021.
  * Bowman et al. (2022) Samuel R Bowman, Jeeyoon Hyun, Ethan Perez, Edwin Chen, Craig Pettit, Scott Heiner, Kamile Lukosuite, Amanda Askell, Andy Jones, Anna Chen, et al.  Measuring progress on scalable oversight for large language models.  _arXiv preprint arXiv:2211.03540_ , 2022.
  * Brown et al. (2020) Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al.  Language models are few-shot learners.  _Advances in neural information processing systems_ , 33:1877–1901, 2020.
  * Chaitin (1966) Gregory J Chaitin.  On the length of programs for computing finite binary sequences.  _Journal of the ACM (JACM)_ , 13(4):547–569, 1966\.
  * Chaitin (1977) Gregory J Chaitin.  Algorithmic information theory.  _IBM journal of research and development_ , 21(4):350–359, 1977.
  * Chaitin (1990) Gregory J Chaitin.  _Information, randomness & incompleteness: papers on algorithmic information theory_, volume 8.  World Scientific, 1990.
  * Chan et al. (2022) Stephanie CY Chan, Adam Santoro, Andrew K Lampinen, Jane X Wang, Aaditya Singh, Pierre H Richemond, Jay McClelland, and Felix Hill.  Data distributional properties drive emergent few-shot learning in transformers.  _arXiv preprint arXiv:2205.05055_ , 2022.
  * Chater & Vitányi (2003) Nick Chater and Paul Vitányi.  Simplicity: a unifying principle in cognitive science?  _Trends in cognitive sciences_ , 7(1):19–22, 2003\.
  * Chomsky (1956) Noam Chomsky.  Three models for the description of language.  _IRE Transactions on information theory_ , 2(3):113–124, 1956.
  * Chughtai et al. (2023) Bilal Chughtai, Lawrence Chan, and Neel Nanda.  A toy model of universality: Reverse engineering how networks learn group operations.  _arXiv preprint arXiv:2302.03025_ , 2023.
  * Dai et al. (2023) Damai Dai, Yutao Sun, Li Dong, Yaru Hao, Shuming Ma, Zhifang Sui, and Furu Wei.  Why can gpt learn in-context? language models implicitly perform gradient descent as meta-optimizers.  In _ICLR 2023 Workshop on Mathematical and Empirical Understanding of Foundation Models_ , 2023.
  * Dehaene et al. (2022) Stanislas Dehaene, Fosca Al Roumi, Yair Lakretz, Samuel Planton, and Mathias Sablé-Meyer.  Symbols and mental programs: a hypothesis about human singularity.  _Trends in Cognitive Sciences_ , 2022.
  * Delétang et al. (2022) Grégoire Delétang, Anian Ruoss, Jordi Grau-Moya, Tim Genewein, Li Kevin Wenliang, Elliot Catt, Chris Cundy, Marcus Hutter, Shane Legg, Joel Veness, et al.  Neural networks and the chomsky hierarchy.  _arXiv preprint arXiv:2207.02098_ , 2022.
  * Delétang et al. (2023) Grégoire Delétang, Anian Ruoss, Paul-Ambroise Duquenne, Elliot Catt, Tim Genewein, Christopher Mattern, Jordi Grau-Moya, Li Kevin Wenliang, Matthew Aitchison, Laurent Orseau, et al.  Language modeling is compression.  _arXiv preprint arXiv:2309.10668_ , 2023.
  * Deutsch (1996) Peter Deutsch.  Gzip file format specification version 4.3.  Technical report, 1996.
  * Dong et al. (2022) Qingxiu Dong, Lei Li, Damai Dai, Ce Zheng, Zhiyong Wu, Baobao Chang, Xu Sun, Jingjing Xu, and Zhifang Sui.  A survey for in-context learning.  _arXiv preprint arXiv:2301.00234_ , 2022.
  * Falk & Konold (1997) Ruma Falk and Clifford Konold.  Making sense of randomness: Implicit encoding as a basis for judgment.  1997\.
  * Foote et al. (2023) Alex Foote, Neel Nanda, Esben Kran, Ioannis Konstas, Shay Cohen, and Fazl Barez.  Neuron to graph: Interpreting language model neurons at scale.  _arXiv preprint arXiv:2305.19911_ , 2023.
  * Ganguli et al. (2023) Deep Ganguli, Amanda Askell, Nicholas Schiefer, Thomas Liao, Kamilė Lukošiūtė, Anna Chen, Anna Goldie, Azalia Mirhoseini, Catherine Olsson, Danny Hernandez, et al.  The capacity for moral self-correction in large language models.  _arXiv preprint arXiv:2302.07459_ , 2023.
  * Gardner (1987) Howard Gardner.  _The mind’s new science: A history of the cognitive revolution_.  Basic books, 1987.
  * Geva et al. (2020) Mor Geva, Roei Schuster, Jonathan Berant, and Omer Levy.  Transformer feed-forward layers are key-value memories.  _arXiv preprint arXiv:2012.14913_ , 2020.
  * Goh et al. (2021) Gabriel Goh, Nick Cammarata, Chelsea Voss, Shan Carter, Michael Petrov, Ludwig Schubert, Alec Radford, and Chris Olah.  Multimodal neurons in artificial neural networks.  _Distill_ , 6(3):e30, 2021.
  * Goldblum et al. (2023) Micah Goldblum, Marc Finzi, Keefer Rowan, and Andrew Gordon Wilson.  The no free lunch theorem, kolmogorov complexity, and the role of inductive biases in machine learning.  _arXiv preprint arXiv:2304.05366_ , 2023.
  * Goodman et al. (2008) Noah D Goodman, Joshua B Tenenbaum, Jacob Feldman, and Thomas L Griffiths.  A rational analysis of rule-based concept learning.  _Cognitive science_ , 32(1):108–154, 2008.
  * Griffiths & Tenenbaum (2003) Thomas L Griffiths and Joshua B Tenenbaum.  From Algorithmic to Subjective Randomness.  _Neural Information Processing Systems_ , 2003.
  * Griffiths & Tenenbaum (2004) Thomas L Griffiths and Joshua B Tenenbaum.  Probability, algorithmic complexity, and subjective randomness.  _Proceedings of the Cognitive Science Society_ , 2004.
  * Griffiths et al. (2018) Thomas L. Griffiths, Dylan Daniels, Joseph L. Austerweil, and Joshua B. Tenenbaum.  Subjective randomness as statistical inference.  _Cognitive Psychology_ , 103:85–109, June 2018.  ISSN 00100285.  doi: 10.1016/j.cogpsych.2018.02.003.  URL https://linkinghub.elsevier.com/retrieve/pii/S0010028517302281.
  * Gronchi & Sloman (2021) Giorgio Gronchi and Steven A. Sloman.  Regular and random judgements are not two sides of the same coin: Both representativeness and encoding play a role in randomness perception.  _Psychonomic Bulletin & Review_, 28(5):1707–1714, October 2021.  ISSN 1069-9384, 1531-5320.  doi: 10.3758/s13423-021-01934-9.  URL https://link.springer.com/10.3758/s13423-021-01934-9.
  * Gurnee et al. (2023) Wes Gurnee, Neel Nanda, Matthew Pauly, Katherine Harvey, Dmitrii Troitskii, and Dimitris Bertsimas.  Finding neurons in a haystack: Case studies with sparse probing.  _arXiv preprint arXiv:2305.01610_ , 2023.
  * Hahn & Goyal (2023) Michael Hahn and Navin Goyal.  A Theory of Emergent In-Context Learning as Implicit Structure Induction, March 2023.  URL http://arxiv.org/abs/2303.07971.  arXiv:2303.07971 [cs].
  * Hahn & Warren (2009) Ulrike Hahn and Paul A Warren.  Perceptions of randomness: why three heads are better than four.  _Psychological review_ , 116(2):454, 2009.
  * Hanna et al. (2023) Michael Hanna, Ollie Liu, and Alexandre Variengien.  How does gpt-2 compute greater-than?: Interpreting mathematical abilities in a pre-trained language model.  _arXiv preprint arXiv:2305.00586_ , 2023.
  * janus (2022) janus.  Mysteries of mode collapse.  LessWrong, 2022.  URL https://www.lesswrong.com/posts/t9svvNPNmFf5Qa3TA/mysteries-of-mode-collapse.
  * Jiang et al. (2022) Zhiying Jiang, Matthew YR Yang, Mikhail Tsirlin, Raphael Tang, and Jimmy Lin.  Less is more: Parameter-free text classification with gzip.  _arXiv preprint arXiv:2212.09410_ , 2022.
  * Kadavath et al. (2022) Saurav Kadavath, Tom Conerly, Amanda Askell, Tom Henighan, Dawn Drain, Ethan Perez, Nicholas Schiefer, Zac Hatfield-Dodds, Nova DasSarma, Eli Tran-Johnson, et al.  Language models (mostly) know what they know.  _arXiv preprint arXiv:2207.05221_ , 2022.
  * Karpathy (2023) Andrej Karpathy.  A baby GPT with two tokens 0/1 and context length of 3, view[ed] as a finite state markov chain., 2023.  URL https://twitter.com/karpathy/status/1645115622517542913.
  * Kojima et al. (2022) Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa.  Large language models are zero-shot reasoners.  _Advances in neural information processing systems_ , 35:22199–22213, 2022.
  * Lanham et al. (2023) Tamera Lanham, Anna Chen, Ansh Radhakrishnan, Benoit Steiner, Carson Denison, Danny Hernandez, Dustin Li, Esin Durmus, Evan Hubinger, Jackson Kernion, et al.  Measuring faithfulness in chain-of-thought reasoning.  _arXiv preprint arXiv:2307.13702_ , 2023.
  * Levenshtein et al. (1966) Vladimir I Levenshtein et al.  Binary codes capable of correcting deletions, insertions, and reversals.  In _Soviet physics doklady_ , volume 10, pp. 707–710. Soviet Union, 1966.
  * Li et al. (2022) Kenneth Li, Aspen K Hopkins, David Bau, Fernanda Viégas, Hanspeter Pfister, and Martin Wattenberg.  Emergent world representations: Exploring a sequence model trained on a synthetic task.  _arXiv preprint arXiv:2210.13382_ , 2022.
  * Li et al. (1997) Ming Li, Paul Vitányi, et al.  _An introduction to Kolmogorov complexity and its applications_.  Springer, 1997.
  * Li et al. (2023a) Yingcong Li, M Emrullah Ildiz, Dimitris Papailiopoulos, and Samet Oymak.  Transformers as algorithms: Generalization and implicit model selection in in-context learning.  _arXiv preprint arXiv:2301.07067_ , 2023a.
  * Li et al. (2023b) Yingcong Li, M. Emrullah Ildiz, Dimitris Papailiopoulos, and Samet Oymak.  Transformers as Algorithms: Generalization and Stability in In-context Learning, February 2023b.  URL http://arxiv.org/abs/2301.07067.  arXiv:2301.07067 [cs, stat].
  * Lieberum et al. (2023) Tom Lieberum, Matthew Rahtz, János Kramár, Geoffrey Irving, Rohin Shah, and Vladimir Mikulik.  Does circuit analysis interpretability scale? evidence from multiple choice capabilities in chinchilla.  _arXiv preprint arXiv:2307.09458_ , 2023.
  * Liu et al. (2022a) Bingbin Liu, Jordan T Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang.  Transformers learn shortcuts to automata.  _arXiv preprint arXiv:2210.10749_ , 2022a.
  * Liu et al. (2023) Bingbin Liu, Jordan T Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang.  Exposing attention glitches with flip-flop language modeling.  _arXiv preprint arXiv:2306.00946_ , 2023.
  * Liu et al. (2022b) Ziming Liu, Ouail Kitouni, Niklas S Nolte, Eric Michaud, Max Tegmark, and Mike Williams.  Towards understanding grokking: An effective theory of representation learning.  _Advances in Neural Information Processing Systems_ , 35:34651–34663, 2022b.
  * Lu et al. (2023) Sheng Lu, Irina Bigoulaeva, Rachneet Sachdeva, Harish Tayyar Madabushi, and Iryna Gurevych.  Are emergent abilities in large language models just in-context learning?  _arXiv preprint arXiv:2309.01809_ , 2023.
  * Lu et al. (2021) Yao Lu, Max Bartolo, Alastair Moore, Sebastian Riedel, and Pontus Stenetorp.  Fantastically ordered prompts and where to find them: Overcoming few-shot prompt order sensitivity.  _arXiv preprint arXiv:2104.08786_ , 2021.
  * Lubana et al. (2023) Ekdeep Singh Lubana, Eric J Bigelow, Robert P Dick, David Krueger, and Hidenori Tanaka.  Mechanistic mode connectivity.  In _International Conference on Machine Learning_ , pp. 22965–23004. PMLR, 2023.
  * MacKay (2003) David JC MacKay.  _Information theory, inference and learning algorithms_.  Cambridge university press, 2003.
  * Merrill & Sabharwal (2022) William Merrill and Ashish Sabharwal.  Transformers implement first-order logic with majority quantifiers.  _arXiv preprint arXiv:2210.02671_ , 2022.
  * Merrill & Sabharwal (2023) William Merrill and Ashish Sabharwal.  The parallelism tradeoff: Limitations of log-precision transformers.  _Transactions of the Association for Computational Linguistics_ , 11:531–545, 2023.
  * Merrill et al. (2023) William Merrill, Nikolaos Tsilivis, and Aman Shukla.  A tale of two circuits: Grokking as competition of sparse and dense subnetworks.  _arXiv preprint arXiv:2303.11873_ , 2023.
  * Meyniel et al. (2016) Florent Meyniel, Maxime Maheu, and Stanislas Dehaene.  Human inferences about sequences: A minimal transition probability model.  _PLoS computational biology_ , 12(12):e1005260, 2016.
  * Min et al. (2022) Sewon Min, Xinxi Lyu, Ari Holtzman, Mikel Artetxe, Mike Lewis, Hannaneh Hajishirzi, and Luke Zettlemoyer.  Rethinking the Role of Demonstrations: What Makes In-Context Learning Work?, October 2022.  URL http://arxiv.org/abs/2202.12837.  arXiv:2202.12837 [cs].
  * Nanda et al. (2023) Neel Nanda, Lawrence Chan, Tom Liberum, Jess Smith, and Jacob Steinhardt.  Progress measures for grokking via mechanistic interpretability.  _arXiv preprint arXiv:2301.05217_ , 2023.
  * Nickerson (2002) Raymond S Nickerson.  The production and perception of randomness.  _Psychological review_ , 109(2):330, 2002.
  * Olsson et al. (2022) Catherine Olsson, Nelson Elhage, Neel Nanda, Nicholas Joseph, Nova DasSarma, Tom Henighan, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, et al.  In-context learning and induction heads.  _arXiv preprint arXiv:2209.11895_ , 2022.
  * Ortega et al. (2019) Pedro A Ortega, Jane X Wang, Mark Rowland, Tim Genewein, Zeb Kurth-Nelson, Razvan Pascanu, Nicolas Heess, Joel Veness, Alex Pritzel, Pablo Sprechmann, et al.  Meta-learning of sequential strategies.  _arXiv preprint arXiv:1905.03030_ , 2019.
  * Oskarsson et al. (2009) An T. Oskarsson, Leaf Van Boven, Gary H. McClelland, and Reid Hastie.  What’s next? Judging sequences of binary events.  _Psychological Bulletin_ , 135(2):262–285, 2009\.  ISSN 1939-1455, 0033-2909.  doi: 10.1037/a0014821.  URL http://doi.apa.org/getdoi.cfm?doi=10.1037/a0014821.
  * Pallagani et al. (2023) Vishal Pallagani, Bharath Muppasani, Keerthiram Murugesan, Francesca Rossi, Biplav Srivastava, Lior Horesh, Francesco Fabiano, and Andrea Loreggia.  Understanding the capabilities of large language models for automated planning.  _arXiv preprint arXiv:2305.16151_ , 2023.
  * Pan et al. (2023) Alexander Pan, Jun Shern Chan, Andy Zou, Nathaniel Li, Steven Basart, Thomas Woodside, Hanlin Zhang, Scott Emmons, and Dan Hendrycks.  Do the rewards justify the means? measuring trade-offs between rewards and ethical behavior in the machiavelli benchmark.  In _International Conference on Machine Learning_ , pp. 26837–26867. PMLR, 2023.
  * Perez et al. (2022) Ethan Perez, Sam Ringer, Kamilė Lukošiūtė, Karina Nguyen, Edwin Chen, Scott Heiner, Craig Pettit, Catherine Olsson, Sandipan Kundu, Saurav Kadavath, et al.  Discovering language model behaviors with model-written evaluations.  _arXiv preprint arXiv:2212.09251_ , 2022.
  * Piantadosi et al. (2012) Steven T Piantadosi, Joshua B Tenenbaum, and Noah D Goodman.  Bootstrapping in a language of thought: A formal model of numerical concept learning.  _Cognition_ , 123(2):199–217, 2012.
  * Planton et al. (2021) Samuel Planton, Timo van Kerkoerle, Leïla Abbih, Maxime Maheu, Florent Meyniel, Mariano Sigman, Liping Wang, Santiago Figueira, Sergio Romano, and Stanislas Dehaene.  A theory of memory for binary sequences: Evidence for a mental compression algorithm in humans.  _PLOS Computational Biology_ , 17(1):e1008598, January 2021.  ISSN 1553-7358.  doi: 10.1371/journal.pcbi.1008598.  URL https://dx.plos.org/10.1371/journal.pcbi.1008598.
  * Prystawski & Goodman (2023) Ben Prystawski and Noah D Goodman.  Why think step-by-step? reasoning emerges from the locality of experience.  _arXiv preprint arXiv:2304.03843_ , 2023.
  * Radford et al. (2019) Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al.  Language models are unsupervised multitask learners.  _OpenAI blog_ , 1(8):9, 2019.
  * Renda et al. (2023) Alex Renda, Aspen Hopkins, and Michael Carbin.  Can llms generate random numbers? evaluating llm sampling in controlled domains llm sampling underperforms expectations, 2023.  http://people.csail.mit.edu/renda/llm-sampling-paper.
  * Saparov & He (2022) Abulhair Saparov and He He.  Language models are greedy reasoners: A systematic formal analysis of chain-of-thought.  _arXiv preprint arXiv:2210.01240_ , 2022.
  * Shi et al. (2022) Hui Shi, Sicun Gao, Yuandong Tian, Xinyun Chen, and Jishen Zhao.  Learning bounded context-free-grammar via lstm and the transformer: Difference and the explanations.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 36, pp. 8267–8276, 2022.
  * Shin et al. (2022) Seongjin Shin, Sang-Woo Lee, Hwijeen Ahn, Sungdong Kim, HyoungSeok Kim, Boseop Kim, Kyunghyun Cho, Gichang Lee, Woomyoung Park, Jung-Woo Ha, et al.  On the effect of pretraining corpora on in-context learning by a large-scale language model.  _arXiv preprint arXiv:2204.13509_ , 2022.
  * Si et al. (2023) Chenglei Si, Dan Friedman, Nitish Joshi, Shi Feng, Danqi Chen, and He He.  Measuring inductive biases of in-context learning with underspecified demonstrations.  _arXiv preprint arXiv:2305.13299_ , 2023.
  * Sipser (1996) Michael Sipser.  Introduction to the theory of computation.  _ACM Sigact News_ , 27(1):27–29, 1996.
  * Spivey et al. (2009) Michael J Spivey, Sarah E Anderson, and Rick Dale.  The phase transition in human cognition.  _New Mathematics and Natural Computation_ , 5(01):197–220, 2009.
  * Srivastava et al. (2022) Aarohi Srivastava, Abhinav Rastogi, Abhishek Rao, Abu Awal Md Shoeb, Abubakar Abid, Adam Fisch, Adam R Brown, Adam Santoro, Aditya Gupta, Adrià Garriga-Alonso, et al.  Beyond the imitation game: Quantifying and extrapolating the capabilities of language models.  _arXiv preprint arXiv:2206.04615_ , 2022.
  * Tenenbaum (1998) Joshua Tenenbaum.  Bayesian modeling of human concept learning.  _Advances in neural information processing systems_ , 11, 1998.
  * Tenenbaum et al. (2011) Joshua B Tenenbaum, Charles Kemp, Thomas L Griffiths, and Noah D Goodman.  How to grow a mind: Statistics, structure, and abstraction.  _science_ , 331(6022):1279–1285, 2011.
  * Turpin et al. (2023) Miles Turpin, Julian Michael, Ethan Perez, and Samuel R Bowman.  Language models don’t always say what they think: Unfaithful explanations in chain-of-thought prompting.  _arXiv preprint arXiv:2305.04388_ , 2023.
  * Tversky & Gilovich (1989) Amos Tversky and Thomas Gilovich.  The “hot hand”: Statistical reality or cognitive illusion?  _Chance_ , 2(4):31–34, 1989.
  * Ullman & Tenenbaum (2020) Tomer D Ullman and Joshua B Tenenbaum.  Bayesian models of conceptual development: Learning as building models of the world.  _Annual Review of Developmental Psychology_ , 2:533–558, 2020.
  * Ullman et al. (2012) Tomer D Ullman, Noah D Goodman, and Joshua B Tenenbaum.  Theory learning as stochastic search in the language of thought.  _Cognitive Development_ , 27(4):455–480, 2012\.
  * Von Oswald et al. (2023) Johannes Von Oswald, Eyvind Niklasson, Ettore Randazzo, João Sacramento, Alexander Mordvintsev, Andrey Zhmoginov, and Max Vladymyrov.  Transformers learn in-context by gradient descent.  In _International Conference on Machine Learning_ , pp. 35151–35174. PMLR, 2023.
  * Wang et al. (2022) Kevin Wang, Alexandre Variengien, Arthur Conmy, Buck Shlegeris, and Jacob Steinhardt.  Interpretability in the wild: a circuit for indirect object identification in gpt-2 small.  _arXiv preprint arXiv:2211.00593_ , 2022.
  * Wang et al. (2023) Xinyi Wang, Wanrong Zhu, and William Yang Wang.  Large language models are implicitly topic models: Explaining and finding good demonstrations for in-context learning.  _arXiv preprint arXiv:2301.11916_ , 2023.
  * Wei et al. (2021) Jason Wei, Maarten Bosma, Vincent Y Zhao, Kelvin Guu, Adams Wei Yu, Brian Lester, Nan Du, Andrew M Dai, and Quoc V Le.  Finetuned language models are zero-shot learners.  _arXiv preprint arXiv:2109.01652_ , 2021.
  * Wei et al. (2022a) Jason Wei, Yi Tay, Rishi Bommasani, Colin Raffel, Barret Zoph, Sebastian Borgeaud, Dani Yogatama, Maarten Bosma, Denny Zhou, Donald Metzler, et al.  Emergent abilities of large language models.  _arXiv preprint arXiv:2206.07682_ , 2022a.
  * Wei et al. (2022b) Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al.  Chain-of-thought prompting elicits reasoning in large language models.  _Advances in Neural Information Processing Systems_ , 35:24824–24837, 2022b.
  * Wei et al. (2023) Jerry Wei, Jason Wei, Yi Tay, Dustin Tran, Albert Webson, Yifeng Lu, Xinyun Chen, Hanxiao Liu, Da Huang, Denny Zhou, et al.  Larger language models do in-context learning differently.  _arXiv preprint arXiv:2303.03846_ , 2023.
  * Weiss et al. (2021) Gail Weiss, Yoav Goldberg, and Eran Yahav.  Thinking like transformers.  In _International Conference on Machine Learning_ , pp. 11080–11090. PMLR, 2021.
  * Wen et al. (2023) Kaiyue Wen, Yuchen Li, Bingbin Liu, and Andrej Risteski.  (un) interpretability of transformers: a case study with dyck grammars.  2023\.
  * Xie et al. (2022) Sang Michael Xie, Aditi Raghunathan, Percy Liang, and Tengyu Ma.  An Explanation of In-context Learning as Implicit Bayesian Inference, July 2022.  URL http://arxiv.org/abs/2111.02080.  arXiv:2111.02080 [cs].
  * Yang & Piantadosi (2022) Yuan Yang and Steven T Piantadosi.  One model for the learning of language.  _Proceedings of the National Academy of Sciences_ , 119(5):e2021865119, 2022.
  * Zhang et al. (2023a) Muru Zhang, Ofir Press, William Merrill, Alisa Liu, and Noah A Smith.  How language model hallucinations can snowball.  _arXiv preprint arXiv:2305.13534_ , 2023a.
  * Zhang et al. (2023b) Yufeng Zhang, Fengzhuo Zhang, Zhuoran Yang, and Zhaoran Wang.  What and how does in-context learning learn? bayesian model averaging, parameterization, and generalization.  _arXiv preprint arXiv:2305.19420_ , 2023b.
  * Zhao et al. (2020) Mengjie Zhao, Yi Zhu, Ehsan Shareghi, Ivan Vulić, Roi Reichart, Anna Korhonen, and Hinrich Schütze.  A closer look at few-shot crosslingual transfer: The choice of shots matters.  _arXiv preprint arXiv:2012.15682_ , 2020.
  * Zhao et al. (2021) Zihao Zhao, Eric Wallace, Shi Feng, Dan Klein, and Sameer Singh.  Calibrate before use: Improving few-shot performance of language models.  In _International Conference on Machine Learning_ , pp. 12697–12706. PMLR, 2021.
  * Zhong et al. (2023) Ziqian Zhong, Ziming Liu, Max Tegmark, and Jacob Andreas.  The clock and the pizza: Two stories in mechanistic explanation of neural networks.  _arXiv preprint arXiv:2306.17844_ , 2023.
  * Zhou et al. (2022) Denny Zhou, Nathanael Schärli, Le Hou, Jason Wei, Nathan Scales, Xuezhi Wang, Dale Schuurmans, Claire Cui, Olivier Bousquet, Quoc Le, et al.  Least-to-most prompting enables complex reasoning in large language models.  _arXiv preprint arXiv:2205.10625_ , 2022.

##  Appendix A Related Work

Formal languages and transformers. A number of recent works explore how
transformers and other neural language models learng formal languages
(Delétang et al., 2022; Weiss et al., 2021; Shi et al., 2022; Allen-Zhu & Li,
2023; Bhattamishra et al., 2020; Wen et al., 2023; Liu et al., 2023; 2022a;
Merrill & Sabharwal, 2023; Merrill et al., 2023; Merrill & Sabharwal, 2022).
One common theme is that neural networks often learn ‘shortcuts’, degenerate
representations of formal languages that fail out-of-samples.

In-Context Learning as Bayesian inference A number of recent works frame ICL
as Bayesian model selection (Xie et al., 2022; Li et al., 2023b; Akyürek et
al., 2022; Hahn & Goyal, 2023; Bai et al., 2023). Two key differences in our
work are: first, we analyze state-of-the-art LLMs based on behaviors alone,
whereas prior work trains models from scratch on synthetic data and analyzes
model parameters directly. Second, we consider Bayesian inference as an
empirical modeling framework, as well as a theory, whereas these works only do
the latter.

Mechanistic interpretability of transformer models Prior work has
characterized specific circuit-level implementations of simple high-level
behaviors such as sequence copying, modular addition, and other primitive
computational operations (Nanda et al., 2023; Goh et al., 2021; Geva et al.,
2020; Belinkov, 2022; Li et al., 2022; Wang et al., 2022; Chughtai et al.,
2023; Gurnee et al., 2023; Foote et al., 2023; Lubana et al., 2023; Lieberum
et al., 2023; Barak et al., 2022; Liu et al., 2022b; Zhong et al., 2023). Our
work differs in that we model hypothetical algorithms to characterize LM
output behavioral patterns, without observing underlying activation patterns.
We see this as analogous to cognitive science complementing neuroscience in
the understanding of human cognition. We characterize the high-level
“cognitive” representations in LLMs as a step towards connecting low-level
explanations of neural circuits, such as induction heads, with sophisticated
high-level behaviors that are characteristic of LLMs.

Language model evaluations Our work resembles evaluation benchmarks such as
BIG-Bench (Srivastava et al., 2022) that use behavior alone to evaluate LM
understanding and reasoning. However, as described later, the domain of
subjective randomness is fundamentally different in that there is no “correct”
answer. Linguistic probing attempts to characterize the structure of LM
representations, but unlike our work, is a function of hidden unit activations
rather than output behavior.

LLM Text Generation Dynamics Work on chain-of-thought reasoning in LLMs
demonstrates how a few exemplars of detailed solutions or even a simple prompt
like “let’s think this through step-by-step” can dramatically impact model
performance (Wei et al., 2022b; Kojima et al., 2022; Srivastava et al., 2022),
but typically only the model’s final answer is analyzed, not the trajectory of
its intermediate steps. Our memory-constrained Window Average model, inspired
by Hahn & Warren (2009), is similar in spirit to the claim of Prystawski &
Goodman (2023), that ‘[chain-of-thought] reasoning emerges from the locality
of experience’. Zhang et al. (2023a) demonstrate that invalid reasoning can
snowball in LLMs, where hallucinations during intermediate steps lead to
hallucinations in the final answer.

Random number generation in LLMs Renda et al. (2023) explore random number
generation in LLMs, in addition to cursory explorations by (janus, 2022;
Karpathy, 2023). These investigations do not analyze dynamics of sequence
generation, nor do they ground their analysis, as we do, in theories of ICL as
Bayesian model selection and the cognitive science of subjective randomness.
Ortega et al. (2019) uses a similar domain as ours with random binary
sequences and has a similar binary tree visualization over possible sequences,
but they train models from scratch and analyze model hidden states, rather
than behavioral trajectories as we do.

Bayesian program learning in cognitive science Our work is inspired by
computational cognitive science work that theoretically treats concepts as
programs, and empirically uses structured Bayesian models to understand human
cognition in various domains (Tenenbaum, 1998; Tenenbaum et al., 2011; Ullman
et al., 2012; Ullman & Tenenbaum, 2020). We use models based on the cognitive
science of subjective randomness (Falk & Konold, 1997), drawing particularly
on the Bayesian program induction definitions of subjective randomness in
Griffiths & Tenenbaum (2003; 2004); Griffiths et al. (2018). Our method of
studying learning as probabilistic inference over formal languages with
varying $|x|$ is also similar to Goodman et al. (2008); Piantadosi et al.
(2012); Yang & Piantadosi (2022); Bigelow & Piantadosi (2016), who use more
sophisticated grammar-based models of concept learning.

##  Appendix B Additional Experimental Details

All calls were made with the OpenAI API, using default parameters including —
important to our analysis — a temperature parameter of $1.0$.

Since ChatGPT (not including gpt-3.5-turbo-instruct) and GPT-4 use a
ChatCompletions API instead of Completions, we re-formatted the prompts in
Fig. 4 to follow user/assistant/system prompt format. The following prompts
were used:

System |  Your responses will only consist of comma-separated "Heads" and "Tails" samples.
---|---
|  Do not repeat the userś messages in your responses.
User |  Generate a sequence of 1000 random samples from a weighted coin, with $\\{$1 - p$\\}$% probability of Heads and $\\{$ p $\\}$% probability of Tails.
Assistant |  [ $\\{$ sequence $\\}$

Although results are not shown here, for Randomness Judgment experiments, we
also tested text-davinci-003 with prompts other than the one in Fig. 4,
including specifying a non-random algorithm instead of a weighted coin, with
$\\{$ 1 - p $\\}$% probability …, and found similar results of concept
learning dynamics as in Fig. 4, 14.

##  Appendix C Formal Language Learning, by Depth

Figure 9: Predictive distributions $p(y|x)$ by each LLM for Concept
$(\texttt{010})^{n}$, at each prediction depth $d$. Colors correspond to
different prediction depths, also refer to Figure 8. Note: text-ada-001
results are not shown since results did not follow the required format
(‘Heads, Tails, …’) adequately to be analyzed.

Figure 10: Predictive distributions $p(y|x)$ by each LLM for Concept
$(\texttt{011})^{n}$, at each prediction depth $d$. Colors correspond to
different prediction depths, also refer to Figure 8.

Figure 11: Predictive distribution $p(y|x)$ trees with $d=6$ for concept
$C=(011)^{n}$ with $|x|\in\\{6,12,18\\}$. Since $|x|$ is increasing by the
same depth as the tree $\Delta_{|x|}=d=6$, the transition from generating
pseudo-random numbers to deterministically repeating $011$ is visibly
apparent. Also see Figure 8.

Figure 12: Predictive distribution $p(y|x)$ trees with $d=4$ for concept
$C=(011)^{n}$ with $|x|\in\\{1,9,18,24,39\\}$. Models shown are text-
davinci-002, text-davinci-003, and gpt-3.5-turbo-instruct. Also see Figure 8.

##  Appendix D Randomness Judgments

Figure 13: Randomness judgments across GPT models for 9 concepts Also see Fig.
4.

(Fig 13) text-davinci-003 shows a stable pattern of being highly confident
(high token probability) in the process being random up to some amount of
context $|x|$, at which point it rapidly transitions to being highly confident
in the process being non-random, with transition points varying substantially
between concepts. chat-gpt-3.5-instruct does not go through a stable high-
confidence random period like text-davinci-003, and stable high-to-low
confidence dynamics are observed for only a subset of concepts. The majority
of earlier GPT models (text-davinci-002, text-davinci-001, text-curie-001,
text-babbage-001) show no ’formal language learning’, at all. However,
surprisingly OpenAI’s smallest available GPT model text-ada-001 shows S-shaped
in-context learning dynamics, with the peak close to .5 instead of 1.0 as in
text-davinci-003. Additionally, the learning dynamics and transition points
for all concepts appear nearly identical, approximately at $|x|=50$, and some
concepts show less stable "non-random" patterns for larger $|x|$.

Figure 14: Randomness Judgment $p(y=\mathtt{random}|x)$ dynamics for each
concept tested, for text-davinci-003 and gpt-3.5-turbo-instruct

##  Appendix E Random Sequence Generation by GPT Model

Figure 15: 50 sequences sampled by each GPT model, for each $p(Tails)$. Color
is assigned according to specified $p(Tails)$. Red dotted lines are drawn for
each $p(Tails).$ Figure 16: 50 sequences sampled by text-davinci-003, for each
$p(Tails)$, compared with samples from Bernoulli and Window Average models fit
to $y_{LLM}$ for each $p(Tails)$. Color is assigned according to specified
$p(Tails)$.

Figure 17: Probability $p(\mathtt{Tails})$ bias across LLMs text-davinci-003
and GPT-4 models are least biased relative to the specified
$p(\mathtt{Tails})$ (x-axis). In the left figure, error bars represent the
maximum and minimum sequence means $\overline{y}$ for each
$p(\mathtt{Tails})$.

.

Fig. 15 and the left side of Fig. 17 demonstrate that text-davinci-003 and
GPT-4 models not only are more controllable, following the correct probability
more closely on average, but also have substantially lower variance than
ChatGPT, which is both less controllable and has more variability in its
distribution of responses. Further, GPT-4 is lower variance than text-
davinci-003, with sequences staying even closer to their means $\overline{y}$.

##  Appendix F Gambler’s Fallacy Metrics by GPT Model

Figure 18: Gambler’s Fallacy histograms for ChatGPT (Top) and GPT-4 (Bottom).
Also see Fig. 6.

ChatGPT shows no clear Gambler’s Fallacy bias, whereas GPT-4 does show this
pattern, but is less pronounced than text-davinci-003 (Fig. 18).

Figure 19: Comparing metrics of Gambler’s Fallacy across probabilities and
LLMs (Left) The mean longest run for each sequence $y$, at each specified
probability $p(\mathtt{Tails})$, where a run is a consecutive sub-sequence of
the same flip repeating multiple times in a row. (Right) The mean alternation
rate for each LLM, where alternation rate is the fraction of consecutive flips
that are not equal $p(y_{t}\neq y_{t-1})$.

.

In both plots of Fig. 19, we observe that text-davinci-003 shows a Gambler’s
Fallacy bias across $p(\mathtt{Tails})$, of higher-than-chance alternation
rates and shorter runs; ChatGPT (gpt-3.5-turbo-0613) produces more tails-
biased and higher-variance sequences $y$ when $p(\mathtt{Tails})>50\%$; GPT-4
and gpt-3.5-turbo-instruct interpolate between the two distinct trends of
text-davinci-003 and ChatGPT. The red dotted line represents a Bernoulli
process with mean $p(\mathtt{Tails})$.

It is unclear how the capabilities we identify are implemented at a circuit
level, or why they only seem to emerge in the most powerful and heavily tuned
GPT models. For the latter, one hypothesis is that internet corpora contain
text with human-generated or human-curating subjectively random binary
sequences, and fine-tuning methods such as instruction fine-tuning, supervised
fine-tuning, and RLHF make LLMs more controllable, enabling them to apply
previously inaccessible capabilities in appropriate circumstances. Another
hypothesis is that these fine-tuning methods bias LLMs towards non-
repetitiveness, or induce some other general bias that plays a role in the in-
context learning dynamics we observe in our particular domain. We hope that
future work in cognitive and mechanistic interpretability will shed further
light on these questions.

##  Appendix G Memorization, Compression, and Complexity

Figure 20: Distribution of unique sub-sequences for text-davinci-003 for
varying sub-sequence lengths Also see Fig. 7.

.

Figure 21: Distribution of unique sub-sequences for text-davinci-003, with
additional models, varying sub-sequence lengths MC-2, MC-5, and MC-10 are
Markov Chain models fit to GPT-3.5 flips, with orders $k=\\{2,5,10\\}$

.

In Fig. 21, we show that Markov chains of high order $k$ can account for the
sub-sequence distribution, but this only applies when $k<=w$ where $w$ is the
sub-sequence length, and the Markov chains can effectively memorizing the sub-
sequence distribution of $y$.

Figure 22: GPT-4 repeats the same sub-sequences more often than other GPT
models (Left) Number of unique length-10 and length-20 sub-sequences as a
function of specified probability $p(\mathtt{Tails})$, across all sequences
$y$ (note: $|y|=50$) generated by each GPT model. (Right) The same
distributions, with the y-axis normalized by dividing by the same metric
(appended Gzip size, or mean Levenshtein distance) for a Bernoulli
distribution centered at $\overline{y}$, to control for sequence compression
being correlated with probability, e.g. with $\overline{y}=0.99$, the same
sub-sequences of only ‘Tails’ flips will appear many times.

Across both unnormalized and normalized distributions of unique sub-sequences
(Fig. 22), we find that GPT-4 repeats the same length-10 sub-sequences
significantly more than the other models, and both ChatGPT-based models
(gpt-3.5-turbo-0613, gpt-3.5-turbo-instruct) follow different patterns for
$p(\mathtt{Tails})<50\%$ and $p(\mathtt{Tails})>50\%$, even when controlling
for sequence bias (Right). The only model that generates more unique sub-
sequences than chance (above dotted line) is ChatGPT (gpt-3.5-turbo-0613).

Figure 23: GPT-generated sequences have lower complexity than Bernoulli
sequences

As a coarse approximation of sequence complexity, we use Gzip file size of
appended sequences $gzip(y:y^{\prime}:y^{\prime\prime}:\ldots)$ and mean
Levenshtein distance between sequences $d(y,y^{\prime})$. Gzip (Deutsch,
1996), a common algorithm for file compression that is highly optimized for
compressing strings with redundancy into small file sizes, and Gzip file size
has been found to be an effective feature extractor for NLP (Jiang et al.,
2022). Levenshtein distance Levenshtein et al. (1966) is a measure of edit
distance between two strings.

Since sequence compression is highly correlated with probability, e.g. all
sequences with $\overline{y}=0.99$ will be highly compressible, we normalize
the distribution of both plots in Fig. 23 by dividing by the same metric
(appended Gzip size, or mean Levenshtein distance) for a Bernoulli
distribution centered at $\overline{y}$. For all GPT models except ChatGPT,
generated sequences have smaller Levenshtein distance than a Bernoulli
process. This is evidence that these LLMs are using memorized sub-sequences
(‘parroting’), since sequences have repeated structure. On the other hand,
ChatGPT produces more dissimilar sequences than chance, suggesting higher
complexity. In Gzip file size, however, we see a lower-complexity bias in all
LLMs (except for a few higher values of $p(\mathtt{Tails})$), to varying
degrees, produce data $Y$ that is more compressible than data from an equal
probability Bernoulli process.

##  Appendix H Background on Algorithmic and Subjective Randomness

Randomness of a sequence $x$, defined in terms of Bayesian model comparison
between the class of non-random models with the class of random models, can be
translated to be the difference between the sequence length $|x|$ and the
algorithmic complexity, or Kolmogorov complexity of the sequence $K(x)$.

$\displaystyle\text{randomness}(x)$ $\displaystyle=\log
P(x|\text{random})-\log P(x|\text{non-random})$ $\displaystyle=\log\
2^{-|x|}-\log\ 2^{-K(x)}$ $\displaystyle=K(x)-|x|$

The likelihood given a truly random Bernoulli process
$p(x|\text{random})=2^{-|x|}$ since sequences of equal length have equal
probability and there are $2^{|x|}$ binary sequences of length $|x|$. This can
be thought of as a uniform prior over programs, where every program is an
exact copy of the output string.

The likelihood of $x$ given the space of non-random processes marginalizes
over the posterior of all non-random programs (hypotheses) $\mathcal{H}$:

$p(x|\text{non-random})=\sum_{h\in\mathcal{H}}p(h)\ p(x|h)$

.

A natural prior for programs $p(h)$ is the description length of that program,
where common metrics used in software engineering such as lines of code or
number of functions can be seen as practical estimations of program
description length.

If we assume $p(x|h)$ is a binary likelihood, that is:

$p(x|h)=\begin{cases}1&\text{if }h\text{ generates }x\\\
0&\text{otherwise}\end{cases}$

and we simplify the problem to finding the maximum a-priori hypothesis $h$,
and set a prior over hypotheses (programs) proportional to their length
$p(h)=2^{-|x|}$, this equates to finding the program with lowest Kolmogorov
complexity $K(x)$:

$P(x|\text{non-random})\approx\max_{h}p(h)\ p(x|h)=2^{-K(x)}$

where Kolmogorov complexity $K(x)$ is defined as the description length of the
shortest program that generates $x$ as output:

$K(x)=\operatorname*{argmin}_{\\{p\in\Sigma^{*}|Evaluate(p)=x\\}}|p|$

The notation $p\in\Sigma^{*}$ is analogous to $h\in\mathcal{H}$, but refers to
a formal alphabet $\Sigma$ that programs are comprised of. In the general
case, Kolmogorov complexity $K(x)$ is uncomputable due to the halting problem,
since the expression $Evaluate(p)=x$ might run forever if $p$ has an infinite
loop.