# On formal concepts of random formal contexts

Taro Sakurai Department of Mathematics and Informatics, Graduate School of
Science, Chiba University, 1-33, Yayoi-cho, Inage-ku, Chiba-shi, Chiba,
263-8522 Japan<EMAIL_ADDRESS>
###### Abstract.

In formal concept analysis, it is well-known that the number of formal
concepts can be exponential in the worst case. To analyze the average case, we
introduce a probabilistic model for random formal contexts and prove that the
average number of formal concepts has a superpolynomial asymptotic lower
bound.

###### Key words and phrases:

asymptotic lower bound, average case analysis, formal concept analysis, formal
concepts, random formal contexts

###### 2010 Mathematics Subject Classification:

68T30 (06B99, 05C80, 60C05)

###### Contents

  1. 1 Introduction
  2. 2 Preliminaries
  3. 3 Random contexts
  4. 4 Average number of concepts
  5. 5 Asymptotic lower bound
  6. 6 Conclusions

##  1\. Introduction

How many formal concepts does a formal context have? This is one of the
fundamental problems in the theory of _formal concept analysis_ —an
application area of lattice theory which originates from Wille [6] to support
_data analysis_ and _knowledge processing_. In the graph-theoretic language,
the problem asks the number of maximal bicliques of bipartite graphs. The
problem of determining the number of formal concepts is proved to be
#P-complete by Kuznetsov [5, Theorem 1]. Even though the counting problem is
hard in general, it is of interest to get a general idea of how large the
number is.

It is well-known that the number of formal concepts can be exponential in the
worst case, and it can be one in the best case. Such extremal formal contexts
are obtained from contranomial scales and formal contexts defined by the empty
relation. Since these examples appear to be highly atypical, it is natural to
study the number of formal concepts in the _average_ case. To this end, we
introduce random formal contexts (Definition 3.2) and present an exact formula
for the average number of formal concepts (Proposition 4.1). Lastly, we prove
that the average number of formal concepts has a _superpolynomial_ asymptotic
lower bound (Theorem 5.1), which is the main result of this article. Our
theorem and its proof help to understand why a “typical” formal context has
numerous formal concepts.

##  2\. Preliminaries

###  2.1. Formal concept analysis

We recall basic notions in formal concept analysis which can be found in the
textbook by Ganter and Wille [2, Chapter 1]. A _( formal) context_ is defined
to be a triple $K=(G,M,I)$ consists of two sets $G$, $M$, and a subset $I$ of
$G\times M$. An element $g$ of $G$ is called an _object_ , an element $m$ of
$M$ is called an _attribute_ , and $I$ is called the _incidence relation_ of
the context $K$. An object $g$ is said to _have_ an attribute $m$ if a pair
$(g,m)$ belongs to $I$. A context is often represented by a _cross table_
whose rows and columns are indexed by objects and attributes, and the
incidence relation is indicated by crosses as in Figure 1.

${m}$ ${g}$ ${\times}$ Figure 1. The cross table of a context.

Let $A$ be a set of objects and let $B$ be a set of attributes. The set of
attributes that all objects in $A$ have in common is denoted by

$\displaystyle A^{\prime}$ $\displaystyle=\bigcap_{g\in A}\\{\,m\in
M\mid(g,m)\in I\,\\}.$ Similarly, the set of objects that have all attributes
in $B$ is denoted by $\displaystyle B^{\prime}$ $\displaystyle=\bigcap_{m\in
B}\\{\,g\in G\mid(g,m)\in I\,\\}.$

A pair $(A,B)$ is defined to be a _( formal) concept_ if $A^{\prime}=B$ and
$B^{\prime}=A$; the first and second components are called the _extent_ and
_intent_ of the concept. The set of concepts of a context $K$ is denoted by
$\mathfrak{B}(K)$.

###  2.2. Asymptotic analysis

We recall two useful notations in asymptotic analysis: the _little-oh
notation_ and the _Vinogradov notation_. Let $(x_{n})$ and $(y_{n})$ be real
sequences. For an arbitrary positive real number $\varepsilon$, if
$\lvert{x_{n}}\rvert<\varepsilon\lvert{y_{n}}\rvert$ for sufficiently large
$n$, then we write $x_{n}=o(y_{n})$. If there is some positive real number
$\gamma$ satisfying $\lvert{x_{n}}\rvert\leq\gamma\lvert{y_{n}}\rvert$ for
sufficiently large $n$, then we write $y_{n}\gg x_{n}$.

##  3\. Random contexts

In this section, we introduce a probabilistic model for random contexts.
Although we provide its measure-theoretic formalization later for
completeness, the randomness we consider might be best described by the
following informal manner.

Let $n$ be a positive integer and take an $n$-set, say $U=\\{1,2,\dotsc,n\\}$.
For each element of $U$, we regard it as an _object_ with probability $p$ and
as an _attribute_ with probability $1-p$, independently. Subsequently, for
each pair $(g,m)$ of an object $g$ and an attribute $m$, we regard an object
$g$ _has_ an attribute $m$ with probability $q$, independently. We add that
the probabilities $p$ and $q$ are not necessarily constants like $p=1/2$ and
may be functions of $n$ like $q=1-1/n$.

A similar probabilistic model with a fixed number of objects and attributes is
used by Kovács in [4, §2.1] to estimate the number of concepts. Those who
familiar with random graph theory would instantly recognize that this is very
much alike to the model for binomial random graphs [3, p. 2], which is also
known as the Erdős-Rényi model. In this article, we content ourselves with
this simplest model for random contexts. The readers may wish to skim through
the next notation and definition if they are comfortable with this informal
description of our probabilistic model.

Throughout this article, we use a convention to write random variables in
bold. For basic concepts of probability theory, we refer the readers to a work
by Bauer [1, Chapter I], for example.

######  Notation 3.1.

Let $n$ be a positive integer and let $p$ and $q$ be real numbers belonging to
the unit interval $[0,1]$. Set $U=\\{1,2,\dotsc,n\\}$. Write $\Omega$ for the
set of contexts $(G,M,I)$ with $G+M=U$ where $+$ denotes the disjoint union.
Define the probability measure $P=\kappa_{n,p,q}$ on the power set
$2^{\Omega}$ by

$P\\{(G,M,I)\\}=p^{\lvert{G}\rvert}(1-p)^{\lvert{M}\rvert}\,q^{\lvert{I}\rvert}(1-q)^{\lvert{G\times
M-I}\rvert}.$

The probability space $(\Omega,2^{\Omega},P)$ is our mathematical model for
random contexts.

######  Definition 3.2.

We call an $\Omega$-valued random variable $\bm{K}$ a _random context_ and
write $\bm{K}\sim\kappa_{n,p,q}$ if the distribution of $\bm{K}$ equals
$\kappa_{n,p,q}$.

For a real-valued function $f$ on $\Omega$ and a random context $\bm{K}$, we
write

$E(f\circ\bm{K})=\int f\,dP=\sum_{K\in\Omega}f(K)P\\{K\\}$

for the expectation.

##  4\. Average number of concepts

Based on the notion of random contexts that is introduced in the previous
section, we show an exact formula for the average number of concepts in this
section.

######  Proposition 4.1.

Let $\bm{K}$ be a random context with $\bm{K}\sim\kappa_{n,p,q}$. Then

(4.1)
$E(\lvert{\mathfrak{B}(\bm{K})}\rvert)=\sum_{(a,b,c,d)}\binom{n}{a\;b\;c\;d}\,p^{a+c}(1-p)^{b+d}\,q^{ab}(1-q^{a})^{d}(1-q^{b})^{c}$

where the sum is taken over all non-negative integers with $a+b+c+d=n$.

###### Proof.

Set $\bm{K}=(\bm{G},\bm{M},\bm{I})$. Let $A$ and $B$ be subsets of $U$. We
write $\bm{1}_{\\{(A,B)\in\mathfrak{B}(\bm{K})\\}}$ for the indicator variable
of an event that a pair $(A,B)$ is a concept of $\bm{K}$. By the linearity of
expectation and the law of total probability, we may reduce the problem as

$\displaystyle E(\lvert{\mathfrak{B}(\bm{K})}\rvert)$
$\displaystyle=\sum_{(A,B)}E(\bm{1}_{\\{(A,B)\in\mathfrak{B}(\bm{K})\\}})=\sum_{(A,B)}P\\{(A,B)\in\mathfrak{B}(\bm{K})\\}$
$\displaystyle=\sum_{(A,B,C,D)}P(\\{(A,B)\in\mathfrak{B}(\bm{K})\\}\cap\\{\bm{G}=A+C\\}\cap\\{\bm{M}=B+D\\})$

where the sums are taken over all tuples of subsets of $U$. Suppose that
$(A,B,C,D)$ is an ordered partition of the set $U$. From the reduction, it is
enough to show that

$\quad
P(\\{(A,B)\in\mathfrak{B}(\bm{K})\\}\cap\\{\bm{G}=A+C\\}\cap\\{\bm{M}=B+D\\})\hfill\\\
\hfill{}=p^{\lvert{A+C}\rvert}(1-p)^{\lvert{B+D}\rvert}\,q^{\lvert{A\times
B}\rvert}(1-q^{\lvert{A}\rvert})^{\lvert{D}\rvert}(1-q^{\lvert{B}\rvert})^{\lvert{C}\rvert}.\quad$

The cross table of a context in Figure 2 may help the readers to see why this
claim holds.

${B}$ ${D}$ ${A}$ ${\times}$ ${\vdots}$ ${C}$ ${\cdots}$ ${\ast}$ Figure 2.
When
$\\{(A,B)\in\mathfrak{B}(\bm{K})\\}\cap\\{\bm{G}=A+C\\}\cap\\{\bm{M}=B+D\\}$
occurs.

First, every element of $A+C$ must belong to $\bm{G}$ with probability
$p^{\lvert{A+C}\rvert}$ (row header), and every element of $B+D$ must belong
to $\bm{M}$ with probability $(1-p)^{\lvert{B+D}\rvert}$ (column header).
Second, every pair of $A\times B$ must belong to $\bm{I}$ with probability
$q^{\lvert{A\times B}\rvert}$ (upper-left corner). Next, every attribute in
$D$ must not be shared by all objects in $A$ with probability
$(1-q^{\lvert{A}\rvert})^{\lvert{D}\rvert}$ (upper-right corner), and every
object in $C$ must not have all attributes in $B$ with probability
$(1-q^{\lvert{B}\rvert})^{\lvert{C}\rvert}$ (lower-left corner). Last, the
rest entries (lower-right corner) do not affect the occurrence of the event.
The above argument establishes the claim and completes the proof. ∎

##  5\. Asymptotic lower bound

In this section, we study random contexts with constant probabilities
$p=q=1/2$ in detail and prove that the average number of concepts has a
superpolynomial asymptotic lower bound. The following is the main result of
this article.

######  Theorem 5.1.

Let $(\bm{K}_{n})$ be a sequence of random contexts with
$\bm{K}_{n}\sim\kappa_{n,\frac{1}{2},\frac{1}{2}}$. Then

$E(\lvert{\mathfrak{B}(\bm{K}_{n})}\rvert)>n^{\log n}$

for sufficiently large $n$. In particular,
$E(\lvert{\mathfrak{B}(\bm{K}_{n})}\rvert)\gg n^{\log n}$.

For a real number $x$, the integer part and fractional part of $x$ are denoted
by $[{x}]$ and $\\{{x}\\}$. To obtain a lower bound for the average number of
concepts of $\bm{K}_{n}$, we _single out_ the specific term

(5.1) $\displaystyle t_{n}$
$\displaystyle=\binom{n}{a_{n}\;b_{n}\;c_{n}\;d_{n}}\,p^{a_{n}+c_{n}}(1-p)^{b_{n}+d_{n}}\,q^{a_{n}b_{n}}(1-q^{a_{n}})^{d_{n}}(1-q^{b_{n}})^{c_{n}}$

in (4.1) for constant probabilities $p=q=1/2$ where

(5.2) $\displaystyle\begin{split}a_{n}&=\bigg{[}{\frac{\log n}{\log
2}}\bigg{]},\qquad b_{n}=\bigg{[}{\frac{\log n}{\log
2}}\bigg{]}+2\bigg{\\{}{\frac{n}{2}}\bigg{\\}},\qquad\text{and}\\\
c_{n}&=d_{n}=\bigg{[}{\frac{n}{2}}\bigg{]}-\bigg{[}{\frac{\log n}{\log
2}}\bigg{]}.\end{split}$

Although this is just one term in the summation, it turns out to be large
enough for our purpose. The asymptotic behavior of $t_{n}$ is described as
follows.

######  Lemma 5.2.

With notation in (5.1),

$\log t_{n}=\frac{\log^{2}n}{\log 2}\left(1+o(1)\right).$

To prove this asymptotic equivalence, we need some lemmas.

######  Lemma 5.3.

With notation in (5.2),

$\log\binom{n}{a_{n}\;b_{n}\;c_{n}\;d_{n}}=n\log 2+2\frac{\log^{2}n}{\log
2}+o(\log^{2}n).$

###### Proof.

By the Stirling formula and the Taylor formula,

$\displaystyle\log n!$ $\displaystyle=n\log n-n+o(\log^{2}n),$
$\displaystyle\log a_{n}!$ $\displaystyle=\log\left(\frac{\log n}{\log
2}-\bigg{\\{}{\frac{\log n}{\log 2}}\bigg{\\}}\\!\right)!=o(\log^{2}n),$
$\displaystyle\log b_{n}!$ $\displaystyle=\log\left(\frac{\log n}{\log
2}-\bigg{\\{}{\frac{\log n}{\log
2}}\bigg{\\}}+2\bigg{\\{}{\frac{n}{2}}\bigg{\\}}\\!\right)!=o(\log^{2}n),\qquad\text{and}$
$\displaystyle\log c_{n}!$ $\displaystyle=\log
d_{n}!=\log\left(\frac{n}{2}-\bigg{\\{}{\frac{n}{2}}\bigg{\\}}-\frac{\log
n}{\log 2}+\bigg{\\{}{\frac{\log n}{\log 2}}\bigg{\\}}\\!\right)!$
$\displaystyle=\log\left(\frac{n}{2}-\frac{\log n}{\log 2}+o(\log n)\right)!$
$\displaystyle=\left(\frac{n}{2}-\frac{\log n}{\log 2}+o(\log
n)\right)\log\left(\frac{n}{2}-\frac{\log n}{\log 2}+o(\log n)\right)$
$\displaystyle\qquad-\left(\frac{n}{2}-\frac{\log n}{\log 2}+o(\log
n)\right)+o(\log^{2}n)$ $\displaystyle=\left(\frac{n}{2}-\frac{\log n}{\log
2}\right)\log\left(\frac{n}{2}-\frac{\log n}{\log 2}+o(\log
n)\right)-\frac{n}{2}+o(\log^{2}n)$
$\displaystyle=\left(\frac{n}{2}-\frac{\log n}{\log 2}\right)\\!\left(\log
n-\log 2-\frac{2}{n}\frac{\log n}{\log
2}+o\left(\frac{\log^{2}n}{n}\right)\\!\right)-\frac{n}{2}+o(\log^{2}n)$
$\displaystyle=\frac{1}{2}n\log n-\frac{1}{2}(1+\log 2)n-\frac{\log^{2}n}{\log
2}+o(\log^{2}n).$

Therefore

$\displaystyle\log\binom{n}{a_{n}\;b_{n}\;c_{n}\;d_{n}}$
$\displaystyle\qquad\quad=n\log n-n-2\left(\frac{1}{2}n\log
n-\frac{1}{2}(1+\log 2)n-\frac{\log^{2}n}{\log 2}\right)+o(\log^{2}n)$
$\displaystyle\qquad\quad=n\log 2+2\frac{\log^{2}n}{\log 2}+o(\log^{2}n).\qed$

######  Lemma 5.4.

With notation in (5.2),

$\big{\lvert}{\log(1-2^{-a_{n}})^{d_{n}}(1-2^{-b_{n}})^{c_{n}}}\big{\rvert}<2.$

###### Proof.

We may assume that $n>2$. Note that $c_{n}=d_{n}\leq n/2$ and

$\displaystyle 1-2^{-b_{n}}\geq 1-2^{-a_{n}}=1-2^{-\frac{\log n}{\log
2}+\\{{\frac{\log n}{\log 2}}\\}}=1-\frac{2^{\\{{\frac{\log n}{\log
2}}\\}}}{n}>1-\frac{2}{n}.$

Hence

$\displaystyle\big{\lvert}{\log(1-2^{-a_{n}})^{d_{n}}(1-2^{-b_{n}})^{c_{n}}}\big{\rvert}$
$\displaystyle\qquad\qquad=-d_{n}\log(1-2^{-a_{n}})-c_{n}\log(1-2^{-b_{n}})<-n\log\left(1-\frac{2}{n}\right)\leq
2.\qed$

###### Proof of Lemma 5.2.

By Lemmas 5.3 and 5.4,

$\displaystyle\log t_{n}$
$\displaystyle=\log\binom{n}{a_{n}\;b_{n}\;c_{n}\;d_{n}}-\left(\frac{n}{2}-\bigg{\\{}{\frac{n}{2}}\bigg{\\}}\\!\right)\log
2-\left(\frac{n}{2}+\bigg{\\{}{\frac{n}{2}}\bigg{\\}}\\!\right)\log 2$
$\displaystyle\qquad-\left(\frac{\log n}{\log 2}-\bigg{\\{}{\frac{\log n}{\log
2}}\bigg{\\}}\\!\right)\\!\left(\frac{\log n}{\log 2}-\bigg{\\{}{\frac{\log
n}{\log 2}}\bigg{\\}}+2\bigg{\\{}{\frac{n}{2}}\bigg{\\}}\\!\right)\log 2$
$\displaystyle\qquad+\log(1-2^{-a_{n}})^{d_{n}}(1-2^{-b_{n}})^{c_{n}}$
$\displaystyle=n\log 2+2\frac{\log^{2}n}{\log 2}-\frac{n}{2}\log
2-\frac{n}{2}\log 2-\frac{\log^{2}n}{\log 2}+o(\log^{2}n)$
$\displaystyle=\frac{\log^{2}n}{\log 2}+o(\log^{2}n)=\frac{\log^{2}n}{\log
2}\left(1+o(1)\right).\qed$

###### Proof of Theorem 5.1.

By Proposition 4.1, we have $E(\lvert{\mathfrak{B}(\bm{K}_{n})}\rvert)\geq
t_{n}$. Set $\varepsilon=1-\log 2=0.306\dotsm\,$. It follows from Lemma 5.2
that

$\log E(\lvert{\mathfrak{B}(\bm{K}_{n})}\rvert)\geq\log
t_{n}>\frac{\log^{2}n}{\log 2}(1-\varepsilon)=\log^{2}n$

for sufficiently large $n$, which proves the theorem. ∎

$n$ | $10^{1}$ | $10^{2}$ | $10^{3}$ | $10^{4}$ | $10^{5}$ | $10^{6}$ | $10^{7}$ | $10^{8}$ | $10^{9}$ | $10^{10}$
---|---|---|---|---|---|---|---|---|---|---
$\delta_{n}$ | $1.467$ | $0.860$ | $0.646$ | $0.566$ | $0.477$ | $0.416$ | $0.386$ | $0.347$ | $0.316$ | $0.299$
Table 1. How large $n$ should be for the theorem?

In the end, we make a short comment on how large $n$ should be for the
theorem. Table 1 shows the rounded values of

$\delta_{n}=\bigg{\lvert}{\frac{\log t_{n}}{\log^{2}n/\log 2}-1}\bigg{\rvert}$

for $n=10^{1},\dotsc,10^{10}$. The proof indicates that $n>10^{10}$ would be
sufficient for the theorem.

##  6\. Conclusions

In this article, we addressed the problem of how large the average number of
concepts is. To this end, we introduced the distribution $\kappa_{n,p,q}$ for
random contexts and presented an exact formula for the average number
$E(\lvert{\mathfrak{B}(\bm{K})}\rvert)$ of concepts of a random context
$\bm{K}\sim\kappa_{n,p,q}$. To establish a superpolynomial asymptotic lower
bound, random contexts with constant probabilities $p=q=1/2$ were studied in
detail. For a sequence of random contexts $(\bm{K}_{n})$ with
$\bm{K}_{n}\sim\kappa_{n,\frac{1}{2},\frac{1}{2}}$, we proved that
$E(\lvert{\mathfrak{B}(\bm{K}_{n})}\rvert)\gg n^{\log n}$.

## Acknowledgments

The author would like to thank Ken’ichi Kuga for his understanding of the
preparation of this article. The author would also like to thank Manabu
Hagiwara for conducting several seminars on FCA and thank the participants:
Yuki Kondo, Hokuto Takahashi, and Hayato Yamamura.

## References

  * [1] H. Bauer, Probability Theory (de Gruyter, 1996, Berlin) MR 1385460, Zbl 0868.60001.
  * [2] B. Ganter and R. Wille, Formal Concept Analysis (Springer, Berlin, 1999) MR 1707295, Zbl 0909.06001.
  * [3] S. Janson, T. Łuczak, and A. Ruciński, Random Graphs (Wiley, New York, 2000) MR 1782847, Zbl 0968.05003.
  * [4] L. Kovács, ‘Efficient approximation for counting of formal concepts generated from formal context’, Miskolc Math. Notes 19 (2018) 983–996, doi:10.18514/MMN.2018.2529, MR 3915517, Zbl 1425.68400.
  * [5] S. O. Kuznetsov, ‘On computing the size of a lattice and related decision problems’, Order 18 (2001) 313–321, doi:10.1023/A:1013970520933, MR 1884424, Zbl 0991.06006.
  * [6] R. Wille, ‘Restructuring lattice theory: An approach based on hierarchies of concepts’, Ordered sets, Proceedings of the NATO Advanced Study Institute held at Banff, Canada, August 28 to September 12, 1981 (ed. I. Rival; Reidel, Dordrecht, 1982) 445–470, doi:10.1007/978-94-009-7798-3_15, MR 661303, Zbl 0491.06008.


# The semantic landscape paradigm for neural networks

Shreyas Gokhale
Department of Physics
Massachusetts Institute of Technology
Cambridge, MA 02139
<EMAIL_ADDRESS>

###### Abstract

Deep neural networks exhibit a fascinating spectrum of phenomena ranging from
predictable scaling laws to the unpredictable emergence of new capabilities as
a function of training time, dataset size and network size. Analysis of these
phenomena has revealed the existence of concepts and algorithms encoded within
the learned representations of these networks. While significant strides have
been made in explaining observed phenomena separately, a unified framework for
understanding, dissecting, and predicting the performance of neural networks
is lacking. Here, we introduce the semantic landscape paradigm, a conceptual
and mathematical framework that describes the training dynamics of neural
networks as trajectories on a graph whose nodes correspond to emergent
algorithms that are instrinsic to the learned representations of the networks.
This abstraction enables us to describe a wide range of neural network
phenomena in terms of well studied problems in statistical physics.
Specifically, we show that grokking and emergence with scale are associated
with percolation phenomena, and neural scaling laws are explainable in terms
of the statistics of random walks on graphs. Finally, we discuss how the
semantic landscape paradigm complements existing theoretical and practical
approaches aimed at understanding and interpreting deep neural networks.

_Keywords_ Artificial Intelligence $\cdot$ Machine Learning $\cdot$
Statistical Physics

##  1 Introduction

We live in an age in which the readers of this manuscript can never quite be
sure whether it was written by a human or a large language model111For the
record, this manuscript has been written in its entirety by a human named
Shreyas Gokhale.. This sobering fact at once highlights the stunning
technological advances in artificial intelligence (AI) in recent years, as
well as the urgent need to understand the inner workings of the deep neural
networks that made these advances possible. Understanding neural networks
requires us to know what the networks are capable of doing, how their
performance depends on various factors, and finally why they succeed or fail
in different circumstances. Over the last few years, researchers have begun to
answer these questions through an impressive set of experimental results as
well as theoretical ideas. Several studies have reported empirical
observations of power law scaling of the test loss as a function of network
size (number of parameters), dataset size (number of training examples),
compute budget as well as training time (Hestness et al. (2017); Rosenfeld et
al. (2019); Kaplan et al. (2020); Gordon et al. (2021); Zhai et al. (2022);
Hoffmann et al. (2022)). Subsequently, a number of distinct theoretical
proposals have been put forward to explain the observed power laws (Bahri et
al. (2021); Hutter (2021); Sharma and Kaplan (2022); Maloney et al. (2022);
Michaud et al. (2023)).

In addition to these ubiquitous power laws, which provide a precise account of
the improvement of model performance with scale, a number of studies have also
reported the sudden emergence of new capabilities in neural networks. New
capabilities can emerge either as a function of time, a phenomenon known as
grokking (Power et al. (2022); Thilak et al. (2022); Liu et al. (2022a)), or
as a function of the network size, which we will refer to in this paper as
‘emergence with scale’ (Wei et al. (2022); Ganguli et al. (2022)). Despite
their prevalence, the nature of emergent phenomena in deep neural networks
remains far from understood. While some works support the view that grokking
is associated with a phase transition (Žunkovič and Ilievski (2022); Liu et
al. (2022b)), others have contested that sudden emergence is only an illusion
stemming from the metric used for quantifying loss, and that the network’s
performance is in fact evolving gradually (Schaeffer et al. (2023)).
Furthermore, networks can make hidden progress before the clear manifestation
of emergence, that remains undetected in loss curves (Barak et al. (2022)).

A promising approach towards disentangling these seemingly contradictory
observations about the emergence is to look under the hood of the network, and
determine what the networks in question are actually learning to do. This line
of inquiry has led to some truly remarkable discoveries on the nature of
learned representations in neural networks. Using network dissection (Bau et
al. (2017)), Bau et al. (2020)) showed that individual neurons in
convolutional neural networks (CNNs) can represent concepts associated with
physical objects. By reverse engineering neural networks (Cammarata et al.
(2020)), a number of studies have shown that transformer language models can
learn a variety of algorithms for tasks including text prediction (Elhage et
al. (2021); Olsson et al. (2022)), modular addition (Nanda et al. (2023);
Zhong et al. (2023)), and group operations (Chughtai et al. (2023)).
Collectively, these findings establish the fact that deep neural networks are
capable of learning well-defined computations that confer enhanced prediction
capabilities. Based on this idea, (Michaud et al. (2023)) have recently
proposed the quantization model to explain scaling as well as emergence in
language models.

Owing to the preponderance of performance metric data and the growing
literature on mechanistic insights, several independent theoretical approaches
aimed at explaining various aspects of neural network phenomenology have been
proposed, as discussed in preceding paragraphs. While all of these approaches
are immensely valuable, they follow from distinct conceptual frameworks. This
makes it difficult to understand how different approaches are related to each
other, and if and when their domains of applicability intersect. A unified
conceptual framework that integrates quantitative neural network performance
metrics with the qualitative demands of interpretability is highly desirable,
as it will provide a common language for theoretical discourse, and direct
further developments in the field.

In the present work, we introduce such a unified conceptual framework by
defining a semantic landscape in the space spanned by internal algorithms
learned by neural networks, which we term heuristic models. We then proceed to
demonstrate how several distinct qualitative and quantitative aspects of
neural network phenomenology find a natural and consistent description in
terms of trajectories on the semantic landscape. The rest of the paper is
organized as follows: In Section $2$, we provide mathematical definitions for
key concepts associated with the semantic landscape. In Section $3$, we
illustrate how grokking and emergence with scale can be described in terms of
first passage and percolation phenomena on the semantic landscape. In Section
$4$, we derive scaling laws for test loss as a function of network size,
dataset size, and training time, for a particular choice of semantic landscape
topography. Finally, in Section $5$, we discuss how the semantic landscape
paradigm connects to existing approaches, how it can be developed further, and
what its implications are for future research.

##  2 The semantic landscape paradigm

###  2.1 From the loss landscape to the semantic landscape

At its core, neural network learning is an optimization problem with many
interacting degrees of freedom. This fact has long attracted the attention of
statistical physicists, as it enables them to apply their formidable
repertoire of theoretical tools to a challenging problem of tremendous
practical importance Mehta et al. (2019). In particular, the concept of a loss
landscape defined by the network loss as a function of neural weights plays a
central role in our understanding of neural networks, owing to its
similarities with well-studied objects such as energy landscapes in physics
(Debenedetti and Stillinger (2001)) and chemistry (Onuchic et al. (1997)), and
fitness landscapes in evolutionary biology (De Visser and Krug (2014)). In
particular, concepts such as scaling and the renormalization group (Geiger et
al. (2020); Bahri et al. (2021); Roberts et al. (2022)), glasses (Baity-Jesi
et al. (2018)), and jamming (Spigler et al. (2019)), have provided significant
insights into the nature of training dynamics. The loss landscape is immensely
useful, as it enables us to understand learning dynamics by analogy with well-
understood physical phenomena that we have much better intuition for. However,
recent studies on mechanistic interpretability (Nanda and Lieberum (2022);
Zhong et al. (2023)), have brought to light a significant gap in our
understanding of how neural networks function. Specifically, we do not yet
understand how dynamics on the loss landscape can produce outputs that look as
if they follow from a sequence of interpretable logical steps. To bridge this
gap, we need to develop a coarse-grained description that can on one hand
retain connections with loss landscapes, and on the other hand, take direct
cognizance of the emergent algorithms that are being discovered in a growing
number of studies. The purpose of this paper is to introduce such a
description in terms of the semantic landscape, and demonstrate that it can
consistently explain a number of disparate neural network phenomena within the
same conceptual framework.

###  2.2 Heuristic models

Understanding how neural networks function is synonymous with understanding
how information processing occurs between their input and output layers.
Mechanistic interpretability studies strongly suggest that this information
processing is analogous to the execution of emergent algorithms encoded within
the learned representations of neural networks. The semantic landscape
paradigm formalizes this notion with the help of the following conjecture

  * For every neural network, there exists at least one function that maps subsets of the set of network parameters to well formed formulas within a formal language.

A formal language $L$ is defined as a set of words formed using symbols from
an alphabet $\Sigma$, according to a given set of rules. A well-formed formula
$f$ within $L$ is defined as a finite sequence of symbols belonging to
$\Sigma$, that has been constructed using the rules of $L$. Thus, the formal
language $L$ can be identified with the set of all well-formed formulas in
$L$. We also note that the ‘formal language’ discussed here is associated with
internal representations of the neural network, and is not related in any way
to the programming language in which the neural network code is written.
Mathematically, the conjecture above can be expressed as follows:

  * C1: Given a neural network with a set of parameters $W=\\{w_{i}|i\in\mathbb{N}^{+},i\leq N\\}$, and a formal language $L$ containing the set of well formed formulas $\mathcal{S}_{F}=\\{f_{i}|i\in\mathbb{N}^{+},i\leq N_{L}\\}$, $\exists\mathcal{G}\neq\emptyset$, such that $\forall G_{i}\in\mathcal{G},\\\ G_{i}:W^{m}\mapsto\mathcal{S}_{F}$ for some $m\in\mathbb{N}^{+}$.

Why would such functions $G_{i}$ that map neural weights to well-formed
formulas be of interest? The reason is that it is always possible to uniquely
encode well-formed formulas in any language as numbers using schemes such as
Gödel numbering (Gödel (1931)). The functions $G_{i}$ would therefore ensure a
mathematical equivalence between the state of the neural network as described
by a set of neural weights, and the state of the neural network as described
by a set of well-formed formulas in a formal language. Since algorithms are by
definition, sets of well-formed formulas within a given formal language, C1
implies that the collective neural activity within all the hidden layers for a
fixed set of neural weights is mathematically equivalent to the execution of
an algorithm in some formal language $L$.

The conjecture C1 is strongly supported by empirical evidence across various
models and datasets in the form of concept neurons (Bau et al. (2020)),
induction heads (Elhage et al. (2021)), learned algorithms for mathematical
operations (Nanda et al. (2023); Chughtai et al. (2023); Zhong et al. (2023)),
and auto-discovered quanta (Michaud et al. (2023)). Indeed, these studies have
also shown that beyond the formulation of logical propositions, neural
networks are capable of integrating these propositions into emergent heuristic
algorithms that enable the network to generate correct outputs for a majority
of inputs. We use the term ‘heuristic’ to emphasize the fact that the
emergence of a logical procedure for determining the output need not imply an
innate knowledge or understanding of underlying mathematical or factual truths
on the network’s part. Within the semantic landscape paradigm, we formalize
the notion of emergence of such internal heuristic algorithms by defining the
concept of a heuristic model as follows:

  * Def. 1: A heuristic model $\mathcal{M}_{H}$ is an algorithm in $L$ composed of a finite sequence of well formed formulas $f_{i}\in\mathcal{S}_{F}$, that generates a unique conditional probability distribution $\mathcal{P}_{H}(y|x)$ over all possible outputs $y$, for every possible input $x$.

We refer to output distributions rather than unique outputs in Def 1, as for
some tasks such as natural language prediction, there may not be a unique
‘correct’ answer, and the range of appropriate responses will typically derive
from some distribution over the alphabet of that natural language. The
hierarchy of steps from weights to well formed formulas to heuristic models
detailed above, is shown schematically in Fig. 1a. Several comments about the
notion of heuristic models are in order. First, while heuristic models are
collections of well formed formulas in $L$, this does not necessarily imply
that they will make correct predictions for inputs, or result in low test
loss. In fact, in general, most heuristic models are likely to be bad
algorithms that result in high test loss. As training progresses, the network
keeps improving its performance by discovering increasingly better heuristic
models. A successfully trained network is one that has “found” a heuristic
model that is capable of generalizing over a large fraction of possible test
data. For instance, in the example of modular addition studied by Nanda et al.
(2023), the network initially uses a bad heuristic model that only memorizes
training data, but later finds a clever mathematical algorithm that can
generalize well across all inputs.

Figure 1: Constructing the semantic landscape:(a) Schematic illustration of
the coarse-graining from neural weights to well formed formulas, and their
subsequent combination into heuristic models, as proposed in conjecture C1.
(b) Schematic of the semantic landscape defined by the variation of
fallibility $\mathcal{F}$ over heuristic models in proposition space. At a
specific point in training, neural weights attain specific values, and the
network occupies a single node on the graph of heuristic models. At a later
time, the neural weights change, enabling the network to occupy a different
node on the graph of heuristic models.

Another important point to note is that a network of a fixed size will in
general not be able to formulate all possible heuristic models. This follows
directly from C1, because as we increase the number of parameters $N$, the
number of ways in which weights can be combined into well formed formulas also
increases. In colloquial terms, increasing the network size increases the
“vocabulary” of the network. We will see in Section $3$ that this increased
capacity for formulating algorithms with network size is crucial for the
emergence of new capabilities with scale.

###  2.3 Fallibility and the semantic landscape

Effectively, the foregoing discussion implies that the training dynamics of a
neural network can be viewed as dynamics on a graph whose vertices are
heuristic models. At a given point in training, the network occupies a single
node on the graph of heuristic models. As training progresses and neural
weights are adjusted, the network can adopt a different heuristic model, which
corresponds to a transition from one node to another. The transition rates to
move from one heuristic model to another are governed by a number of factors
including the network size and dataset size, data quality, and hyperparameters
associated with the network architecture and training algorithm. In principle,
one can adopt a bottom-up approach to compute these transition rates by
systematically coarse-graining over the network parameters, for specific
choices of network architecture and training algorithm. At present, however,
such a task is prohibitively difficult to accomplish. Instead, in this
introductory version of the semantic landscape paradigm, we implement a top-
down approach by making simplified choices for transition rates that are
motivated by, and consistent with, network performance measurements. In order
to make such choices, we need to quantify precisely how good or bad a given
heuristic model is. We do so by defining the fallibility $\mathcal{F}$ of a
given heuristic model $\mathcal{M}_{H}$ as

$\mathcal{F}(\mathcal{M}_{H})=\sum_{x\in\mathcal{I}}D_{KL}\big{(}\mathcal{P}_{GT}(y|x)\parallel\mathcal{P}_{H}(y|x)\big{)}$
(1)

where $\mathcal{P}_{GT}(y|x)$ is the ground truth probability distribution
over all possible outputs $y$ for input $x\in\mathcal{I}$, and
$D_{KL}(P\parallel Q)$ is the Kullback-Leibler divergence of $P$ from $Q$.
From this definition, it is clear that $\mathcal{F}(\mathcal{M}_{H})\geq
0\hskip 2.84526pt\forall\mathcal{M}_{H}$, and $\mathcal{F}(\mathcal{M}_{H})=0$
if and only if the output distribution generated by $\mathcal{M}_{H}$ is
indistinguishable from the ground truth for every $x\in\mathcal{I}$. Thus, the
lower the value of $\mathcal{F}$, the better the heuristic model is. It is
important to note that the fallibility of a model is defined over all possible
inputs, and not just those in the training and test datasets. It is therefore
distinct from the measured loss. However, if the training data quality is
good, measured test loss will be lower for models of low fallibility compared
to those of high fallibility. This can be seen explicitly by considering the
set of all possible inputs $\mathcal{I}$ as a union of the training dataset
$\mathcal{I}_{\rm{train}}$, test dataset $\mathcal{I}_{\rm{test}}$ and the
remaining unseen data $\mathcal{I}_{\rm{unseen}}$. Here,
$\mathcal{I}_{\rm{unseen}}$ refers to the set of inputs that the neural
network has not seen either during training or during testing.

$\mathcal{F}=\sum_{x\in\mathcal{I}_{\rm{train}}}\sum_{x\in\mathcal{I}_{\rm{test}}}\sum_{x\in\mathcal{I}_{\rm{unseen}}}D_{KL}\big{(}\mathcal{P}_{GT}(y|x)\parallel\mathcal{P}_{H}(y|x)\big{)}=\mathcal{F}_{\rm{train}}+\mathcal{F}_{\rm{test}}+\mathcal{F}_{\rm{unseen}}$
(2)

Thus, if the network has simply memorized the training dataset, it will have
low $\mathcal{F}_{\rm{train}}$, and hence, low measured training loss, but
will generally have high $\mathcal{F}_{\rm{test}}$, and therefore high
measured test loss. By contrast, a network that has successfully learned to
generalize over all inputs will yield low values for
$\mathcal{F}_{\rm{train}}$, $\mathcal{F}_{\rm{test}}$, as well as
$\mathcal{F}_{\rm{unseen}}$, and will therefore have low test loss. Defined in
this manner, fallibility of a heuristic model is analogous to the energy of an
excited state, measured with respect to the energy of the ground state. In
analogy with energy landscapes defined over the space of configurations for
glasses (Debenedetti and Stillinger (2001)) and proteins (Onuchic et al.
(1997)), or fitness landscapes defined over genomes (De Visser and Krug
(2014)), we can define the semantic landscape of neural networks in terms of
the variation of fallibility $\mathcal{F}$ in the space of well formed
formulas $f_{i}\in\mathcal{S}_{F}$, such that each “configuration”
$\\{f_{i}\\}$ corresponds to a particular heuristic model $\mathcal{M}_{H}$
(Fig. 1b). An immediate corollary of this definition is that the neural
network can potentially get trapped in local minima of the semantic landscape,
which prevent the network from improving its performance. This situation
implies that small changes to the heuristic model adopted by the network will
necessarily lead to worse predictions, and therefore higher loss. In order to
make accurate predictions over a majority of inputs, such a network would have
to make large changes to its heuristic model. Thus, improvement in performance
is only possible if the network is able to cross certain semantic barriers.
The notion of semantic barriers motivates a natural choice for transition
rates, analogous to thermally activated hopping across an energy barrier. We
therefore assume that the rate to transition from model $\mathcal{M}_{i}$ to
$\mathcal{M}_{j}$ assumes an Arrhenius-like form
$R_{ij}=R_{ij}^{0}\rm{exp}\left[-\beta(\mathcal{F}_{j}-\mathcal{F}_{i})\right]$.
These transition rates in turn imply an Arrhenius-like law for the waiting
time $\tau_{ij}$ for the transition from $\mathcal{M}_{i}$ to
$\mathcal{M}_{j}$, which is given by

$\tau_{ij}=\tau_{ij}^{0}e^{\beta(\mathcal{F}_{j}-\mathcal{F}_{i})}$ (3)

The constants $\beta$ and $\tau_{ij}^{0}$ can depend on the dataset size $D$,
number of parameters $N$, as well as hyperparameters of the neural network,
but the fallibilities themselves do not. In the interest of parsimony, we will
assume throughout the rest of the paper, that $\beta$ is independent of $D$
and $N$, and only $\tau_{ij}^{0}$ varies with these quantities. In the next
two sections, we will show that even under these relatively mild assumptions,
the semantic landscape paradigm can account for several empirical results on
scaling and emergence in deep neural networks.

##  3 Explaining emergent phenomena using semantic landscapes

###  3.1 Grokking

The term ‘grokking’ refers to a phenomenon in which neural networks exhibit
delayed generalization, i.e. the validation accuracy remains low during
training long after the training accuracy reaches 100%, before suddenly rising
at late times. Grokking was first observed by Power et al. (2022) on small
algorithmic datasets and has since been observed in a wide range of contexts
(Liu et al. (2022a); Murty et al. (2023)). A number of explanations for
grokking have been proposed, based on the behavior of weight norms during
training and testing. These include the slingshot mechanism(Thilak et al.
(2022)),the LU model (Liu et al. (2022a)), and competition between sparse and
dense subnetworks (Merrill et al. (2023)). Grokking has also been described as
a phase transition (Žunkovič and Ilievski (2022),Liu et al. (2022b)) within
the framework of representation learning. Nanda et al. (2023) have given a
fascinating account of the sequence of learning stages that consists of
memorization, circuit formation, and cleanup.

Within the semantic landscape paradigm, whether a given network will exhibit
grokking or not depends on the topography of the semantic landscape, which in
turn depends on the task that the network is required to perform. If there are
relatively few ways of performing the task correctly, and a large number of
ways of performing it incorrectly, the semantic landscape will be
characterized by one, or a few, very deep minima, surrounded by a sea of
relatively shallow ones corresponding to high fallibility, and separated from
them by semantic barriers. This type of semantic landscape topography is most
likely to result in observable grokking. This is because starting from any of
the high fallibility models, the network must be able to locate one of the few
solutions that lead to low fallibility (and hence low test loss), which would
generally take much longer than it takes to memorize the training data set.
This follows from the intuition that memorization is the easiest heuristic
model to adopt, as it requires only storage and retrieval of information with
no additional processing. For example if a neural network is tasked with
classifying dogs and pigeons, memorizing the training images would be easier
than developing heuristics that involve formulating meaningful concepts such
as "wings" or "legs" by extracting features from those images. This argument
provides a simple intuitive explanation for why grokking is more likely to be
observed on algorithmic datasets, and is supported by the finding that
grokking on realistic datasets, when present, is weaker than on algorithmic
ones (Liu et al. (2022a)). Furthermore, since finding solutions that
generalize well involves crossing semantic barriers, the semantic landscape
paradigm predicts that the test loss during grokking should transiently
increase with training steps before decreasing again, which has indeed been
observed in studies of grokking (Power et al. (2022); Nanda et al. (2023)).
The amount by which loss transiently increases contains information about the
height of semantic barriers, and is likely to play a crucial role in future
work aimed at connecting network weight norm dynamics to the heuristic models
discussed here.

An important observation regarding grokking is the presence of a critical
training dataset size (Power et al. (2022)) below which the network is unable
to generalize regardless of how long the training phase lasts. Can the
semantic landscape paradigm account for the presence of such a critical
datasize? To answer this question, we need to understand how training data
affect dynamics on the semantic landscape. To begin with, the presence of
training examples is what enables the network to hop between heuristic models
in the first place. Supplying more data enables the network to access more
models. Thus, the configuration space of heuristic models is a graph whose
vertices correspond to heuristic models, and whose connectivity is determined
by the training data. If multiple edges are present between two models, we can
interpret this as an increased propensity for transitions between those two
models. Conversely, if no edges are present between two models, it is
impossible to transition between them. In the simplest approximation, we can
think of the dataset size $D$ as being proportional to the average degree of
the graph of heuristic models.

Figure 2: Grokking as a percolation phenomenon: Schematic showing how grokking
emerges within the semantic landscape paradigm. Grokking corresponds to a
first passage process to reach model heuristic model $\mathcal{M}_{G}$
starting from $\mathcal{M}_{M}$ via intermediate semantic barriers
corresponding to models with higher $\mathcal{F}$, as indicated by the
colorbar. This process is possible only when a continuous path between
$\mathcal{M}_{M}$ and $\mathcal{M}_{G}$ exists (middle panel, thick blue
lines), which happens only if $D\geq D_{c}$. Increasing $D$ further leads to
faster grokking due to increased connectivity of the graph.

Let us assume that the network has adopted the heuristic model
$\mathcal{M}_{M}$ that corresponds to memorization of the training dataset.
For sufficiently large $D$, there is always a continuous path that connects
$\mathcal{M}_{M}$ to the model corresponding to the generalization solution
$\mathcal{M}_{G}$. However, as we reduce the dataset size, edges between
models are progressively removed until we reach a critical dataset size
$D_{c}$ below which the graph becomes disconnected, and it is no longer
possible to transition from $\mathcal{M}_{M}$ to $\mathcal{M}_{G}$ regardless
of how long we run the training (Fig. 2). This implies that the model is
incapable of generalization below a critical dataset size, as observed in
previous work (Power et al. (2022); Liu et al. (2022b)). Crucially,this simple
argument implies that that the phase transition associated with grokking is a
percolation transition on the graph of heuristic models. The semantic
landscape paradigm also successfully predicts the decrease of grokking time
with dataset size above the critical threshold. Since the number of edges of
the graph controls the probability of transitioning between nodes, the
grokking rate $\lambda_{g}$ is proportional to the “excess degree” of the
graph above the percolation threshold, i.e. $\lambda_{g}\propto(D-D_{c})$, and
therefore vanishes at $D=D_{c}$. Correspondingly, the grokking time
$t_{g}\propto 1/(D-D_{c})$. Quite remarkably, this scaling argument agrees
with theoretical predictions as well as experimental observations in (Liu et
al. (2022b)), suggesting a correspondence between the two frameworks.

###  3.2 Emergence of new capabilities with scale

While grokking refers to the emergence of new capabilities in time, several
studies have also reported the sudden emergence of new capabilities with
increasing model size, i.e. the number of model parameters $N$ (Brown et al.
(2020); Rae et al. (2021); Austin et al. (2021); Wei et al. (2022); Michaud et
al. (2023)). Like grokking, the unpredictable nature of emergence with scale
simultaneously makes it one of the most challenging, as well as the most
crucial problems in AI that need to be solved in the near future (Ganguli et
al. (2022)). Thus far, relatively few studies have offered an explanation for
abrupt emergence of new capabilities with scale. It has recently been proposed
that grokking and double descent, a particular form of emergence with scale,
might be related phenomena (Davies et al. (2023)). The most noteworthy effort
in this direction is the quantization model of neural scaling (Michaud et al.
(2023)) which explains emergence in terms of the sequential acquisition of
discrete computational capabilities called ‘quanta’. The semantic landscape
paradigm shares some interesting similarities with the quantization model,
which we discuss separately in Section $5$. To explain emergence with scale,
we need to understand how the semantic landscape is influenced by $N$. Let us
assume that the dataset size $D\gg D_{c}$, so that we are not bottlenecked due
to insufficient data. As discussed in Section $2$, increasing $N$ enhances the
capacity of the network to formulate new propositions, and hence formulate new
heuristic models. Thus, the effect of increasing $N$ is to increase the number
of nodes on the graph of heuristic models. If a particular node drops out of
the network, all edges connecting it must also drop out, even if the dataset
$D$ is infinitely large. Physically, this means that the network is incapable
of formulating that particular heuristic model, regardless of how many
training examples it sees. Thus, if we consider the configuration space as the
graph of all possible nodes for all $N$, the nodes corresponding to models
that can only be formulated for large $N$ will remain disconnected at small
$N$. With this insight in mind, it is easy to see that emergence with scale
corresponds to a percolation transition with increasing $N$, such that a
continuous path to models of low $\mathcal{F}$ opens up only for sufficiently
large $N$ (Fig. 3).

Figure 3: Emergence with scale as a percolation phenomenon: Left panel: For
small $N$, the network is incapable of formulating the heuristic models
$\mathcal{M}_{1}$,$\mathcal{M}_{2}$, and $\mathcal{M}_{3}$ (grey), and hence,
the associated paths (dashed grey lines) are forbidden. Right panel:
Increasing $N$ allows the network to formulate model $\mathcal{M}_{2}$, which
opens a path towards low fallibility models, (thick blue lines), and enables
the network to learn new capabilities.

Percolation can also account for the distinct behaviors of per token loss in
large language models (LLMs) observed by Michaud et al. (2023). Even if the
network finds a heuristic model of lower $\mathcal{F}$, particularly for
complex tasks such as language prediction, it is likely that the improved
model does significantly better on some but not all tokens. Some tokens may
require the network to perform several successive jumps to increasingly lower
$\mathcal{F}$ states for them to be predicted accurately. Michaud et al.
(2023) refer to these as “polygenic tokens”. For complex tasks such as
language prediction, the semantic landscape is likely to be rugged, consisting
of a large number of minima and saddle points, which provides a natural
explanation for the presence of polygenic tokens.

##  4 Explaining neural scaling laws using semantic landscapes

Apart from unpredictable emergent phenomena, neural networks also exhibit
predictable power law scaling with increasing $D$, $N$, as well as training
steps $S$, as mentioned in Section $1$. The first important experimental
observation to note is that neural network performance can be bottlenecked by
$D$ as well as $N$, leading to diminishing returns when the other parameter is
scaled (Kaplan et al. (2020)). This observation is already anticipated by the
semantic landscape paradigm, as seen in the previous section. Specifically, if
$D$ is a limiting factor, performance plateaus because the network is unable
to find paths to good heuristic models, even if it has the capacity to
formulate them (i.e. $N\to\infty$). If, on the other hand, $N$ is a limiting
factor, performance plateaus because the network is unable to formulate a good
heuristic model, even if the paths leading to it are in principle open (i.e
$D\to\infty$). In the following discussion, we will therefore assume that $D$
as well as $N$ are both sufficiently large, such that the graph of heuristic
models is always connected.

###  4.1 The semantic trap model

Figure 4: Schematic illustration of the semantic trap model.

To derive neural scaling laws within the semantic landscape paradigm, we have
to make assumptions about the topography of the semantic landscape. In the
case of LLMs, on which most of the work on neural scaling has focused, we
expect that the semantic landscape is very rugged, much like the energy
landscapes of disordered systems such as structural (Debenedetti and
Stillinger (2001)) as well as spin glasses (Mézard et al. (1987)). At low
temperatures, the ruggedness, or the preponderance of metastable energy minima
causes the dynamics on such landscapes to proceed sluggishly via activated
hops in a non-stationary manner, a process known as aging (Berthier and Biroli
(2011)). One would expect similar dynamics on the semantic landscape of LLMs,
as progress towards models with lower $\mathcal{F}$ would presumably be
impeded by a large number of semantic barriers. Taking inspiration from
Bouchaud’s trap model for glassy dynamics (Bouchaud (1992)), we define the
analogous semantic trap model for LLMs. We assume that dynamics on the
semantic landscape consists of activated hops across large semantic barriers
$\Delta\mathcal{F}_{i}$ to models with lower $\mathcal{F}$, interspersed with
excursions along relatively flat directions that don’t affect $\mathcal{F}$
significantly. We further assume that the fallibility $\mathcal{F}$ of the
network after $N_{b}$ barrier crossings is inversely proportional to $N_{b}$.
This model is schematically illustrated in Fig. 4. Analogous to the trap model
(Bouchaud (1992)), we assume that these large semantic barriers have an
exponential distribution

$\rho(\Delta\mathcal{F})=\beta\rho_{0}\rm{exp}\left(-\beta\mu\Delta\mathcal{F}\right)$
(4)

where $\rho_{0}$,$\beta$, and $\mu$ are constants. In the trap model,
$\mu=T/T_{g}$, where $T$ is the temperature, and $T_{g}$ is the glass
transition temperature. An exponential distribution of barrier heights is
known to emerge in a number of disordered systems (Monthus and Bouchaud
(1996)) and is thought to follow from extreme event statistics (Bouchaud and
Mézard (1997)). Together with the activated form for dynamics on the semantic
landscape (Eqn.3), Eqn.4 implies a waiting time distribution $\psi(\tau)$ that
has a power law tail for long waiting times of the form

$\psi(\tau)=\psi_{0}\tau_{0}^{\mu}\tau^{-(1+\mu)}$ (5)

where $\psi_{0}$ is a normalization constant (Bouchaud (1992)). As each
semantic barrier is crossed, the waiting time to cross that barrier is sampled
independently, and thus, the time taken to cross $N_{b}$ barriers is given by
$t(N_{b})=\sum_{i}^{N_{b}}\tau_{i}$, which results in the scaling
$t(N_{b})\propto\tau_{0}N_{b}^{1/\mu}$ (Bouchaud and Georges (1990)). Assuming
that time is measured in the number of training steps $S$, and using
$\mathcal{F}\propto 1/N_{b}$, we obtain the following scaling form of the
fallibility with training time

$\mathcal{F}(S)=\left(\frac{S_{0}}{S}\right)^{\mu}$ (6)

where $S_{0}$ is a constant. The inverse proportionality between $\mathcal{F}$
and $N_{b}$ marks a crucial difference between Bouchaud’s trap model and the
semantic trap model introduced here. Bouchaud’s model corresponds to a renewal
process in which the system loses memory completely following an activated
hop, and the energy of the new state is chosen randomly after every hop. By
contrast, the semantic trap model predictably reduces its fallibility by an
amount proportional to $1/N_{b}^{2}$ for the $(N_{b}+1)^{\rm{th}}$ activated
hop.

To obtain the scaling of fallibility with dataset size $D$ and number of
parameters $N$, first recall our assumption in Section $2$ that fallibility,
and therefore semantic barriers themselves, are independent of $D$ and $N$.
The scaling form is therefore determined by the dependence of $\tau_{0}$ on
$D$ and $N$. In the semantic trap model, $1/\tau_{0}$ is the attempt frequency
for activated hops towards lower $\mathcal{F}$, and $\tau_{0}$ therefore
corresponds to the time over which the network explores the sub-graph
associated with flat regions of the semantic landscape between hops
(horizontal rows of nodes in Fig. 4). From the discussion in Section $3.1$ as
well as Fig. 2, $D$ is proportional to the connectivity of the sub-graph.
Thus, the rate $\gamma$ at which the sub-graph is traversed increases with
$D$. From Section $3.2$ and Fig. 3, we see that $N$ increases the number of
heuristic models that the network can formulate. Thus, increasing $N$
increases the number of paths by which the network can find models with lower
$\mathcal{F}$. Thus, the typical distance $\ell$ between nodes on the sub-
graph that the network has to traverse before it can hop towards a model with
lower $\mathcal{F}$ decreases with $N$. For a dynamical process with exponent
$\alpha$ on the sub-graph, therefore, we have
$\ell(N)\propto(\gamma(D)t)^{\alpha}$. The exponent $\alpha$ characterizes the
nature of the process by which the network navigates the graph of heuristic
models. Thus, we have $\alpha=1$ for ballistic dynamics, $\alpha=0.5$ for
diffusive dynamics, $0<\alpha<0.5$ for sub-diffusive dynamics, and
$\alpha>0.5$ for super-diffusive dynamics. Since the network representation
takes a finite time to evolve even in the infinite data limit, we assume
$\gamma(D)=\gamma_{\infty}D/(D+D_{k})$. Similarly, not all models will lead to
lower fallibility even for an infinitely large network, and so we have
$\ell(N)=\ell_{0}/N^{1/d_{f}}+\ell_{\infty}$, where $d_{f}$ is the fractal
dimension of the sub-graph. This scaling form is motivated by the intuition
that if $n$ points are randomly distributed within a $d$ dimensional volume,
the typical distance between them scales as $n^{-1/d}$. Thus, as $D\to\infty$,
we have $\tau_{0}\propto N^{-1/(\alpha d_{f})}$. Furthermore, as
$\mathcal{F}\propto 1/N_{b}$, and $N_{b}\propto\tau_{0}^{-\mu}$, we have the
following scaling law as $D\to\infty$

$\mathcal{F}(N)=\left(\frac{N_{0}}{N}\right)^{\mu/(d_{f}\alpha)}$ (7)

where $N_{0}$ is a constant. Finally, as $N\to\infty$, we get $\tau_{0}\propto
1/D$, which yields the scaling law

$\mathcal{F}(D)=\left(\frac{D_{0}}{D}\right)^{\mu}$ (8)

where $D_{0}$ is a constant. Eqns. 7 and 8 hold as long as $D_{c}\ll D\ll
D_{k}$, and $N_{c}\ll N\ll(\ell_{0}/\ell_{\infty})^{d_{f}}$, which is
consistent with the range over which typical LLMs operate (Kaplan et al.
(2020)). Strikingly, from Eqns. 6 and 8, we see that the semantic trap model
predicts that the exponents for dataset scaling and training time scaling
should be identical, which is also predicted by the quantization model
(Michaud et al. (2023)) despite starting from a different set of assumptions,
which suggests intriguing connections between the two frameworks.

###  4.2 Interpretation of scaling exponents

While the semantic trap model is possibly the simplest choice that one can
make to describe learning on a rugged semantic landscape, it is certainly
possible to construct more sophisticated models. However, despite its
simplicity, the semantic trap model can recover a wide range of empirically
observed scaling laws (Villalobos ; Michaud et al. (2023)), as the exponents
for $D$ and $N$ scaling are independent. In the simplest case, if the
landscape is smooth and there are no semantic barriers to cross, the scaling
laws are independent of $\mu$. In this case, for ballistic motion $\alpha=1$
on a regular 2D graph with $d_{f}=2$, one recovers the variance limited
scaling for deep neural networks ($\mathcal{F}(D)\propto 1/D$ and
$\mathcal{F}(N)\propto 1/\sqrt{N}$), while $\alpha=1$, $d_{f}=1$ yields the
scaling for linear networks ($\mathcal{F}(D)\propto 1/D$ and
$\mathcal{F}(N)\propto 1/\sqrt{N}$) (Bahri et al. (2021)). We hope that future
works will explain this correspondence by systematically coarse-graining from
weights to propositions. Comparing $D$ scaling with that observed in large
language models (Kaplan et al. (2020)), we get $\mu\approx 0.1$. In the trap
model (Bouchaud (1992)), $\mu<1$ corresponds to temperatures lower than the
glass transition temperature, where dynamics are extremely sluggish and the
system exhibits aging. Curiously, molecular dynamics simulations of glasses
have reported that the lowering of potential energy with time is compatible
with a power law decay with a small exponent $\approx 0.144$ (Kob and Barrat
(1997)). Since the scaling exponent for $D$ and time is the same in the
semantic trap model, the similarities in the observed scaling in glassy
systems and the semantic trap model is quite suggestive, and merits further
exploration.

##  5 Discussion

In the preceding sections, we have introduced and formally defined the notions
of heuristic models, fallibility and the semantic landscape. We have
demonstrated that a wide range of neural network phenomena including grokking,
emergence with scale, and various forms of neural scaling, which have hitherto
been explained using disparate theoretical frameworks, find natural and
consistent explanations within the semantic landscape paradigm under fairly
general assumptions. The main advantage of invoking the semantic landscape
paradigm is that neural network phenomena can be recast in terms of well
studied problems in statistical physics, such as percolation, spin glasses,
and random walks on graphs. By construction, the semantic landscape paradigm
interpolates between top-down empirical observations on the high level
mechanistic interpretation of neural network function (Nanda et al. (2023);
Chughtai et al. (2023)) obtained via reverse engineering, and bottom-up
approaches based on coarse-graining over network parameters Roberts et al.
(2022). Naturally, at this incipient stage, a discussion of how the semantic
landscape paradigm can complement existing approaches, and how it can be
developed further, is is order. We therefore conclude this paper with a series
of comments that elaborate on these questions and their potential answers.

###  5.1 How can we tell whether a phenomenon is emergent or not?

Since much of this paper was devoted to explaining emergent phenomena, it is
worth addressing an interesting contrarian perspective on emergence that was
put forward by Schaeffer et al. (2023). The authors show that different loss
curve can show either smooth or abrupt evolution with network size depending
on the metric used for quantifying loss. Based on this, they argue that
emergence may not be a fundamental property of scaling neural network models.
We advocate the viewpoint that emergence must necessarily refer to the
emergence of new capabilities, and is therefore completely independent of loss
metrics. Some metrics could be sensitive to emergence, and others could be
insensitive. By contrast, an abrupt change in particular loss metrics doesn’t
by itself imply that a new capability has emerged. The only real way to
determine whether a new capability has emerged is to look under the hood and
figure out what has changed in the network’s learned representations. Such
mechanistic interpretability (Nanda et al. (2023)) analysis might be
complicated for complex tasks, not least because the network might be
acquiring several new capabilities simultaneously in a way that makes the
average loss curve appear smooth (Nanda and Lieberum (2022)). However, we
strongly believe that real progress on understanding emergence can only be
made via deciphering the logic developed within the network’s internal
representations during learning.

###  5.2 Semantic landscapes and the quantization model

The quantization model (Michaud et al. (2023)) is a theoretical framework that
is capable of explaining emergence as well as scaling in neural networks. It
begins with three hypotheses that can briefly be described as follows: QH1)
Neural networks learn a number of discrete computations called ‘quanta’ that
are instrumental in reducing loss. QH2) Quanta are learned in order of their
usefulness, with more important quanta being learned first. The priority order
for learning quanta can therefore be specified in terms of the ‘Q-sequence’.
QH3) The frequency with which quanta are used decays as a power law in the
quanta’s index in the Q-sequence, which ultimately explains neural scaling
laws. The semantic trap model has many interesting similarities, and also some
interesting differences with the quantization model. Since heuristic models
are algorithms in the network’s internal formal language, a heuristic model
with lower $\mathcal{F}$ will necessarily contain more quanta. The semantic
trap model assumes that $\mathcal{F}$ scales inversely with the number $N_{b}$
of hops that reduce $\mathcal{F}$. This effectively implies that more useful
quanta are learned earlier, as hypothesized in QH2. However, we note that for
the scaling relations in Eqn.6-8 to hold, the inverse relationship between
$\mathcal{F}$ and $N_{b}$ only needs to hold on average, and a weaker version
of QH2 that admits occasional disruptions of the Q-sequence should be
sufficient. Importantly, the semantic landscape paradigm provides a rigorous
definition of the “usefulness” of quanta. The “usefulness” of a quantum $q$ is
exactly equal to the reduction in $\mathcal{F}$ after $q$ has been learned,
which is in turn proportional to the number of additional tokens that can be
predicted with improved accuracy. This automatically explains why less useful
quanta are also ones that are less frequently used. In future work, it would
be exciting to ask whether the usefulness of a particular quantum depends on
the presence or absence of other quanta, akin to epistatic interactions
between mutations during evolution (Wolf et al. (2000)).

Unlike QH3, the semantic trap model does not explicitly assume power laws.
Instead, a power law waiting time distribution follows from the assumption of
an exponential distribution of semantic barriers. While this choice is still
purely phenomenological, it finds precedent in a variety of disordered systems
(Monthus and Bouchaud (1996)), and could potentially be quite prevalent due to
its origin in large deviations theory (Bouchaud and Mézard (1997)). Crucially,
neural scaling in the semantic landscape paradigm follows from the structure
of the semantic landscape, which is at least in principle, formally derivable
from network weights. Semantic landscapes therefore serve as a consistent
conceptual foundation for making controlled hypotheses in different settings,
and can be easily generalized to different network architectures and tasks.

###  5.3 Connecting loss landscapes to semantic landscapes

As noted earlier, the loss landscape picture has proved to be invaluable for
our current understanding of neural networks (Mehta et al. (2019); Spigler et
al. (2019); Baity-Jesi et al. (2018); Bahri et al. (2021); Roberts et al.
(2022)). From a theoretical perspective, loss landscapes will also prove to be
extremely valuable in the construction of semantic landscapes, via systematic
coarse-graining of neural weights. In particular, such studies will help
assess for which architectures and learning algorithms the assumption of
Arrhenius-like transition rates remains valid. However, we stress that several
predictions of the semantic landscape paradigm, including the existence of a
critical dataset size for grokking, the emergence of new capabilities with
scale, as well as power law scaling of loss with network size and dataset
size, are determined by the topology of the graph of heuristic models, and do
not rely on particular choices of transition rates. The Arrhenius form of
transition rates is primarily essential to obtain nontrivial exponents for
data scaling. Examining these findings through the lens of the loss landscape
will go a considerable way in developing and refining the semantic landscape
paradigm in the coming years.

###  5.4 Mechanistic interpretability and the semantic landscape paradigm

The semantic landscape paradigm provides a consistent and versatile conceptual
framework that will prove to be particularly useful for studies that aim to
gain mechanistic insights into the learning dynamics of neural networks.
Within the last couple of years, a growing number of studies have reverse
engineered neural networks to discover circuits that implement a series of
computations that enable the network to generalize beyond the training dataset
(Nanda and Lieberum (2022); Wang et al. (2022); Hernandez et al. (2022);
Chughtai et al. (2023); Lindner et al. (2023); Conmy et al. (2023); Zhong et
al. (2023)). As this burgeoning field grows and develops further, it would
benefit immensely from a framework that keeps track of the training process
not in terms of abstract functions of neural weights, but in terms of well-
defined and interpretable emergent algorithms. This is exactly what the
semantic landscape paradigm offers, by envisioning the training process as a
trajectory on the graph of learned algorithms. Furthermore, as emergent
algorithms must ultimately derive from weights, mechanistic interpretability
studies will be invaluable in developing the semantic landscape paradigm into
a more rigorous theory, as they can simultaneously keep track of the
microscopic as well as macroscopic aspects of learning. Studies that combine
theoretical ideas contained in the semantic landscape paradigm and empirical
approaches employed in mechanistic interpretability studies will prove to be
instrumental in elucidating the intricacies of neural network learning,
thereby paving the way for developing stronger and more efficient AI systems.

###  5.5 Is scale everything in AI?

Ganguli et al. (2022) have astutely noted that while the test loss of large
generative models improves with increased computing resources and loosely
correlates with improved performance on many tasks, specific capabilities
cannot be predicted ahead of time. Crucially, while the predictable aspects of
performance drive development and deployment of these models, the
unpredictable aspects make it difficult to anticipate the consequences of such
development and deployment. One could reasonably ask if this is necessarily
such a big problem. Indeed, one could argue that this problem might disappear
if we simply scale our neural networks up sufficiently, so that whatever
capabilities they are currently lacking will be discovered by their scaled up
versions. There is no doubt that quantitatively speaking, networks with more
parameters will acquire more capabilities. However, there is no guarantee that
the qualitative capabilities that we desire will be found by simply scaling
up. In glass physics, the potential energy of glassy states is only slightly
higher than that of the global free energy minimum corresponding to the
crystalline state (Debenedetti and Stillinger (2001)), and yet glasses differ
from crystals significantly in several important properties. Furthermore, it
is virtually impossible for glasses to ‘find’ the crystalline state, in the
absence of external intervention. If the semantic landscape of large
generative models resembles the energy landscape of a glass, they may very
well encounter a similar problem. As a corollary, the test loss alone may not
be the best indicator of the network’s performance. Scaling up the network may
not solve this problem because even if the larger network is capable of
discovering a solution that the smaller one could not, it may not be able to
‘find’ that solution during its training. Indeed, one may have to tune
hyperparameters, engineer prompts, or implement an entirely different, perhaps
brain-like (Liu et al. (2023)) learning algorithm for it to acquire the
desired capability. Ultimately, if we do not understand the algorithms that
the network is learning to implement, we would not be able to assess how the
network’s training process should be modified to achieve desired results. And
it is perhaps in solving this critical problem that the confluence of
mechanistic interpretability studies and the semantic landscape paradigm will
find its finest hour.

## Acknowledgements

The author thanks Jeff Gore, Sarah Marzen, Chih-Wei Joshua Liu, Yizhou Liu,
Jinyeop Song, Jiliang Hu, and Yu-Chen Chao for illuminating discussions and
feedback on the manuscript, as well as Amit Nagarkar and Satyajit Gokhale for
a critical reading of the manuscript. The author acknowledges the Gordon and
Betty Moore Foundation for support as a Physics of Living Systems Fellow
through Grant No. GBMF4513.

## References

  * Hestness et al. [2017] Joel Hestness, Sharan Narang, Newsha Ardalani, Gregory Diamos, Heewoo Jun, Hassan Kianinejad, Md Mostofa Ali Patwary, Yang Yang, and Yanqi Zhou.  Deep learning scaling is predictable, empirically.  _arXiv preprint arXiv:1712.00409_ , 2017.
  * Rosenfeld et al. [2019] Jonathan S Rosenfeld, Amir Rosenfeld, Yonatan Belinkov, and Nir Shavit.  A constructive prediction of the generalization error across scales.  _arXiv preprint arXiv:1909.12673_ , 2019.
  * Kaplan et al. [2020] Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei.  Scaling laws for neural language models.  _arXiv preprint arXiv:2001.08361_ , 2020.
  * Gordon et al. [2021] Mitchell A Gordon, Kevin Duh, and Jared Kaplan.  Data and parameter scaling laws for neural machine translation.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pages 5915–5922, 2021.
  * Zhai et al. [2022] Xiaohua Zhai, Alexander Kolesnikov, Neil Houlsby, and Lucas Beyer.  Scaling vision transformers.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 12104–12113, 2022.
  * Hoffmann et al. [2022] Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbl, Aidan Clark, et al.  Training compute-optimal large language models.  _arXiv preprint arXiv:2203.15556_ , 2022.
  * Bahri et al. [2021] Yasaman Bahri, Ethan Dyer, Jared Kaplan, Jaehoon Lee, and Utkarsh Sharma.  Explaining neural scaling laws.  _arXiv preprint arXiv:2102.06701_ , 2021.
  * Hutter [2021] Marcus Hutter.  Learning curve theory.  _arXiv preprint arXiv:2102.04074_ , 2021.
  * Sharma and Kaplan [2022] Utkarsh Sharma and Jared Kaplan.  Scaling laws from the data manifold dimension.  _The Journal of Machine Learning Research_ , 23(1):343–376, 2022.
  * Maloney et al. [2022] Alexander Maloney, Daniel A Roberts, and James Sully.  A solvable model of neural scaling laws.  _arXiv preprint arXiv:2210.16859_ , 2022.
  * Michaud et al. [2023] Eric J Michaud, Ziming Liu, Uzay Girit, and Max Tegmark.  The quantization model of neural scaling.  _arXiv preprint arXiv:2303.13506_ , 2023.
  * Power et al. [2022] Alethea Power, Yuri Burda, Harri Edwards, Igor Babuschkin, and Vedant Misra.  Grokking: Generalization beyond overfitting on small algorithmic datasets.  _arXiv preprint arXiv:2201.02177_ , 2022.
  * Thilak et al. [2022] Vimal Thilak, Etai Littwin, Shuangfei Zhai, Omid Saremi, Roni Paiss, and Joshua Susskind.  The slingshot mechanism: An empirical study of adaptive optimizers and the grokking phenomenon.  _arXiv preprint arXiv:2206.04817_ , 2022.
  * Liu et al. [2022a] Ziming Liu, Eric J Michaud, and Max Tegmark.  Omnigrok: Grokking beyond algorithmic data.  _arXiv preprint arXiv:2210.01117_ , 2022a.
  * Wei et al. [2022] 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_ , 2022.
  * Ganguli et al. [2022] Deep Ganguli, Danny Hernandez, Liane Lovitt, Amanda Askell, Yuntao Bai, Anna Chen, Tom Conerly, Nova Dassarma, Dawn Drain, Nelson Elhage, et al.  Predictability and surprise in large generative models.  In _Proceedings of the 2022 ACM Conference on Fairness, Accountability, and Transparency_ , pages 1747–1764, 2022.
  * Žunkovič and Ilievski [2022] Bojan Žunkovič and Enej Ilievski.  Grokking phase transitions in learning local rules with gradient descent.  _arXiv preprint arXiv:2210.15435_ , 2022.
  * 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.
  * Schaeffer et al. [2023] Rylan Schaeffer, Brando Miranda, and Sanmi Koyejo.  Are emergent abilities of large language models a mirage?  _arXiv preprint arXiv:2304.15004_ , 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.
  * Bau et al. [2017] David Bau, Bolei Zhou, Aditya Khosla, Aude Oliva, and Antonio Torralba.  Network dissection: Quantifying interpretability of deep visual representations.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 6541–6549, 2017.
  * Bau et al. [2020] David Bau, Jun-Yan Zhu, Hendrik Strobelt, Agata Lapedriza, Bolei Zhou, and Antonio Torralba.  Understanding the role of individual units in a deep neural network.  _Proceedings of the National Academy of Sciences_ , 117(48):30071–30078, 2020.
  * Cammarata et al. [2020] Nick Cammarata, Shan Carter, Gabriel Goh, Chris Olah, Michael Petrov, Ludwig Schubert, Chelsea Voss, Ben Egan, and Swee Kiat Lim.  Thread: Circuits.  _Distill_ , 2020.  doi:10.23915/distill.00024.  https://distill.pub/2020/circuits.
  * Elhage et al. [2021] Nelson Elhage, Neel Nanda, Catherine Olsson, Tom Henighan, Nicholas Joseph, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, Tom Conerly, Nova DasSarma, Dawn Drain, Deep Ganguli, Zac Hatfield-Dodds, Danny Hernandez, Andy Jones, Jackson Kernion, Liane Lovitt, Kamal Ndousse, Dario Amodei, Tom Brown, Jack Clark, Jared Kaplan, Sam McCandlish, and Chris Olah.  A mathematical framework for transformer circuits.  _Transformer Circuits Thread_ , 2021.  https://transformer-circuits.pub/2021/framework/index.html.
  * 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.
  * 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.
  * 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.
  * 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.
  * Mehta et al. [2019] Pankaj Mehta, Marin Bukov, Ching-Hao Wang, Alexandre GR Day, Clint Richardson, Charles K Fisher, and David J Schwab.  A high-bias, low-variance introduction to machine learning for physicists.  _Physics reports_ , 810:1–124, 2019.
  * Debenedetti and Stillinger [2001] Pablo G Debenedetti and Frank H Stillinger.  Supercooled liquids and the glass transition.  _Nature_ , 410(6825):259–267, 2001.
  * Onuchic et al. [1997] José Nelson Onuchic, Zaida Luthey-Schulten, and Peter G Wolynes.  Theory of protein folding: the energy landscape perspective.  _Annual review of physical chemistry_ , 48(1):545–600, 1997.
  * De Visser and Krug [2014] J Arjan GM De Visser and Joachim Krug.  Empirical fitness landscapes and the predictability of evolution.  _Nature Reviews Genetics_ , 15(7):480–490, 2014\.
  * Geiger et al. [2020] Mario Geiger, Arthur Jacot, Stefano Spigler, Franck Gabriel, Levent Sagun, Stéphane d’Ascoli, Giulio Biroli, Clément Hongler, and Matthieu Wyart.  Scaling description of generalization with number of parameters in deep learning.  _Journal of Statistical Mechanics: Theory and Experiment_ , 2020(2):023401, 2020.
  * Roberts et al. [2022] Daniel A Roberts, Sho Yaida, and Boris Hanin.  _The principles of deep learning theory_.  Cambridge University Press Cambridge, MA, USA, 2022.
  * Baity-Jesi et al. [2018] Marco Baity-Jesi, Levent Sagun, Mario Geiger, Stefano Spigler, Gérard Ben Arous, Chiara Cammarota, Yann LeCun, Matthieu Wyart, and Giulio Biroli.  Comparing dynamics: Deep neural networks versus glassy systems.  In _International Conference on Machine Learning_ , pages 314–323. PMLR, 2018.
  * Spigler et al. [2019] Stefano Spigler, Mario Geiger, Stéphane d’Ascoli, Levent Sagun, Giulio Biroli, and Matthieu Wyart.  A jamming transition from under-to over-parametrization affects generalization in deep learning.  _Journal of Physics A: Mathematical and Theoretical_ , 52(47):474001, 2019.
  * Nanda and Lieberum [2022] Neel Nanda and Tom Lieberum.  A mechanistic interpretability analysis of grokking.  In _Alignment Forum_ , 2022.
  * Gödel [1931] Kurt Gödel.  Über formal unentscheidbare sätze der principia mathematica und verwandter systeme i.  _Monatshefte für mathematik und physik_ , 38:173–198, 1931.
  * Murty et al. [2023] Shikhar Murty, Pratyusha Sharma, Jacob Andreas, and Christopher D Manning.  Grokking of hierarchical structure in vanilla transformers.  _arXiv preprint arXiv:2305.18741_ , 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.
  * 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.
  * Rae et al. [2021] Jack W Rae, Sebastian Borgeaud, Trevor Cai, Katie Millican, Jordan Hoffmann, Francis Song, John Aslanides, Sarah Henderson, Roman Ring, Susannah Young, et al.  Scaling language models: Methods, analysis & insights from training gopher.  _arXiv preprint arXiv:2112.11446_ , 2021.
  * Austin et al. [2021] Jacob Austin, Augustus Odena, Maxwell Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie Cai, Michael Terry, Quoc Le, et al.  Program synthesis with large language models.  _arXiv preprint arXiv:2108.07732_ , 2021.
  * Davies et al. [2023] Xander Davies, Lauro Langosco, and David Krueger.  Unifying grokking and double descent.  _arXiv preprint arXiv:2303.06173_ , 2023.
  * Mézard et al. [1987] Marc Mézard, Giorgio Parisi, and Miguel Angel Virasoro.  _Spin glass theory and beyond: An Introduction to the Replica Method and Its Applications_ , volume 9.  World Scientific Publishing Company, 1987.
  * Berthier and Biroli [2011] Ludovic Berthier and Giulio Biroli.  Theoretical perspective on the glass transition and amorphous materials.  _Reviews of modern physics_ , 83(2):587, 2011\.
  * Bouchaud [1992] Jean-Philippe Bouchaud.  Weak ergodicity breaking and aging in disordered systems.  _Journal de Physique I_ , 2(9):1705–1713, 1992\.
  * Monthus and Bouchaud [1996] Cécile Monthus and Jean-Philippe Bouchaud.  Models of traps and glass phenomenology.  _Journal of Physics A: Mathematical and General_ , 29(14):3847, 1996.
  * Bouchaud and Mézard [1997] Jean-Philippe Bouchaud and Marc Mézard.  Universality classes for extreme-value statistics.  _Journal of Physics A: Mathematical and General_ , 30(23):7997, 1997.
  * Bouchaud and Georges [1990] Jean-Philippe Bouchaud and Antoine Georges.  Anomalous diffusion in disordered media: statistical mechanisms, models and physical applications.  _Physics reports_ , 195(4-5):127–293, 1990.
  * [51] Pablo Villalobos.  Scaling laws literature review cite this post.
  * Kob and Barrat [1997] Walter Kob and Jean-Louis Barrat.  Aging effects in a lennard-jones glass.  _Physical review letters_ , 78(24):4581, 1997\.
  * Wolf et al. [2000] Jason B Wolf, Edmund D Brodie, and Michael John Wade.  _Epistasis and the evolutionary process_.  Oxford University Press, USA, 2000.
  * 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.
  * Hernandez et al. [2022] Danny Hernandez, Tom Brown, Tom Conerly, Nova DasSarma, Dawn Drain, Sheer El-Showk, Nelson Elhage, Zac Hatfield-Dodds, Tom Henighan, Tristan Hume, et al.  Scaling laws and interpretability of learning from repeated data.  _arXiv preprint arXiv:2205.10487_ , 2022.
  * Lindner et al. [2023] David Lindner, János Kramár, Matthew Rahtz, Thomas McGrath, and Vladimir Mikulik.  Tracr: Compiled transformers as a laboratory for interpretability.  _arXiv preprint arXiv:2301.05062_ , 2023.
  * Conmy et al. [2023] Arthur Conmy, Augustine N Mavor-Parker, Aengus Lynch, Stefan Heimersheim, and Adrià Garriga-Alonso.  Towards automated circuit discovery for mechanistic interpretability.  _arXiv preprint arXiv:2304.14997_ , 2023.
  * Liu et al. [2023] Ziming Liu, Eric Gan, and Max Tegmark.  Seeing is believing: Brain-inspired modular training for mechanistic interpretability.  _arXiv preprint arXiv:2305.08746_ , 2023.