An Information Theory of Compute-Optimal Size Scaling, Emergence, and Plateaus in Language Models

## Abstract

Abstract Recent empirical studies show three phenomena with increasing size of language models: compute-optimal size scaling , emergent capabilities , and performance plateauing . We present a simple unified mathematical framework to explain all of these language model scaling phenomena, building on recent skill-text bipartite graph frameworks for semantic learning. Modeling the learning of concepts from texts as an iterative process yields an analogy to iterative decoding of low-density parity check (LDPC) codes in information theory. Thence, drawing on finite-size scaling characterizations of LDPC decoding, we derive the compute-optimal size scaling (Chinchilla rule) for language models. Further, using tools from random network theory, we provide a simple explanation for both emergence of complex skills and plateauing of performance as the size of language models scale. We see multiple plateaus.

## 1 Introduction

To optimally use computational resources when training language models, several recent studies have empirically investigated how model size and dataset size should scale with compute budget [, ], finding a certain *allometric rule* much like in mathematical biology [, ]. As the sizes of language models continue to increase, large improvements in performance have been observed in certain complex tasks with only a small improvement in the model’s loss [] (but see []). The larger language models are therefore said to exhibit *emergent capabilities*, a term drawn from statistical mechanics, where small changes in a macroscopic variable of the system (such as temperature) around a critical value cause an abrupt change—a phase transition or emergent behavior []—in its properties. More recently, there has been prevalent discourse in the AI community that further increases in language model size lead to *plateauing* of performance [, ]. Although, there have been attempts to explain one or two of these empirical phenomena, a unified mathematical framework that explains all three of these empirically observed phenomena is lacking.

Here we take an approach that builds on information and coding theory [] that does so, and also predicts multiple plateaus. In particular, we draw on mathematical ideas around low-density parity check (LDPC) codes (which achieve Shannon optimality) [, ] and random graph theory []. Though statistical language modeling and information theory were introduced in the same paper [], modern connections between the two are still fairly limited, cf. [].

To provide simple and insightful explanations of empirical phenomena, several abstract frameworks have been proposed [, , ], all based on a skill-text bipartite graph that operates at a semantic level and captures key real-world properties []. Arora and Goyal [] explain emergent phenomena by assuming a compute-optimal size scaling rule (Chinchilla allometry rule) []. Liao et al. [] also assume compute-optimal (Chinchilla) size scaling to explain emergence. Michaud et al. [] assume power-law scaling and that each text piece contains only one skill, which may be very different than real-world scenarios. Moreover, inverse polynomial loss scaling is interpreted as the average behavior of emergence at different scales. These existing frameworks explain neither the Chinchilla rule nor the plateau phenomenon. These three frameworks abstract the gradient dynamics of language model training []; an alternate mathematical framework considers dynamics to explain the Chinchilla rule and loss function plateaus but does not consider emergence[].

Our information-theoretic approach is inspired by skill-text bipartite graph frameworks of [, , ] and is closest to []. We make a small modification by separating notions of concepts and skills, as in well-established human cognitive architectures [] that have simple hierarchies [, , ]. In our framework, skills are not directly learned from text; rather, concepts are learned from texts and skills at different levels are learned from concepts (see Section 2 for a detailed description). That is, our framework takes on the notion of skill-quanta from [], and so the number of concepts a language model can learn is proportional to the model size.

The key difference in our work is to have much more detailed and expressive analysis using non-asymptotic techniques rather than asymptotic ones []. Indeed, such finitary analysis is necessary to even consider size scaling. Recall that [, ] assume Chinchilla scaling, whereas we derive it without it being built into our framework.

The main contributions of this paper are as follows.

- 1.
We propose a simple unified mathematical framework that considers a language model’s learning of concepts from texts and composition of skills from concepts.
- 2.
Using this framework and tools from non-asymptotic information theory, we deduce compute-optimal scaling in language models.
- 3.
With the help of random network theory, we provide a simple explanation for emergent abilities of language models in complex tasks when their sizes exceed a certain threshold.
- 4.
We show that plateauing of performance with size-scaling is just a consequence of diversity of skills required for a task. Moreover, plateauing indicates the possibility of multiple emergences as language models continue to scale further.

Our work takes a step in grounding empirical phenomena observed in size scaling of language models on a rigorous mathematical footing. Understanding the origin of these phenomena may yield insights into better architectures, better datasets, and the limitations of large-scale learning systems. Provable optimality of the Chinchilla rule (as in Proposition 1), however, may indicate that there are no gains from better scaling of data and compute remaining, cf. [, Appendix B]. Separately, our results may help policymakers develop regulatory policy by providing insight into the relationship between capabilities of concern and controllable resources such as data and compute [].

## 2 Graph-based framework

Our framework is based on the notion of learning as two levels. First, a set of concepts are learnt from a set of texts with each text involving one or more skills. Second, learning concepts enables the language model to acquire skills, and after encountering a sufficient number of texts with co-occurring pairs of skills, the model eventually acquires compositional abilities resulting in emergent phenomena in various complex tasks. The framework naturally leads to information-theoretic analysis in Section 3.

### 2.1 Texts, concepts, and skills

A set of tokens constitute a text piece from which a language model can learn a wide variety of concepts. This is modeled as a concept-text bipartite graph similar to the skill-text bipartite graph in []. In a given training session (single epoch training), a language model chooses to learn only a subset of concepts from a text piece. The total number of skills a model can learn depends on its size. Here we consider a hierarchy of skills: basic skills in the first layer and multiple layers of advanced skills. Basic skills are easily acquired from concepts, whereas acquiring advanced skills additionally requires certain prerequisite (less advanced) skills. We formalize these semantic learning notions in the sequel. Note that this bipartite graph formulation of learning is intimately related to graph-based approaches to data compression [] and associative memory []. Moreover, although this approach to abstract modeling has been tied to Transformer-based language modeling architectures [], it can describe a variety of quite different learning paradigms [].

### 2.2 Notation

Let $\mathcal{T}$ be a subset of text pieces from a set $\mathfrak{T}$, and let $\mathcal{R}$ be a subset of concepts from a set $\mathfrak{R}$. Let the model size $N$ (number of parameters) be proportional to the number of concepts $R=|\mathcal{R}|$, i.e., $N=\varsigma R$, for some $\varsigma>0$.(^1^11Here, a *concept* is similar to a *skill quantum* in [].) Similarly, let $\tau$ be the number of tokens in a text piece $t\in\mathcal{T}$ with $T=|\mathcal{T}|$, implying that the dataset size $D=\tau T$. For a given compute budget $C$,(^2^22Compute budget is measured in number of floating point operations or FLOPs [].) a language model of size $N$ can be trained using a dataset of size $D$ so the constraint $6ND\leq C$ is satisfied (see []).

Correspondingly, for a given compute budget, $G_{1}^{(C)}=(\mathcal{T}\cup\mathcal{R},E_{\mathcal{T}\mathcal{R}})$ denotes a concept-text bipartite graph, where an edge $e_{tr}\in E_{\mathcal{T}\mathcal{R}}$ indicates that the language model can learn concept $r$ from text $t$. Let the degrees of text pieces (number of skills required to understand a text) be binomially distributed with a fixed mean degree $d_{t}$, i.e., $P_{R}=\mbox{Binomial}(n,p)=\mbox{Binomial}(R,d_{t}/R)$. The corresponding generating function is $P_{R}(x)=\sum_{i}P_{i}x^{i}$. Let the degree distribution of concepts be $L_{T}=\mbox{Binomial}(T,d_{r}/T)$, where $d_{r}=d_{t}T/R$. Note that $d_{t}/R=d_{r}/T=:p$. There is an alternate point of view: If we assume that there exists an edge between a text piece and a concept with probability $d_{t}/T$, then a typical graph will have text and concept degree distributions close to $P_{R}$ and $L_{T}$, respectively. It is generally useful to view degree distribution from an edge-perspective, which is $\lambda_{T}(x)=L^{\prime}_{T}(x)/L^{\prime}_{T}(1)$ and $\rho_{R}(x)=P^{\prime}_{R}(x)/P^{\prime}_{R}(1)$ [].

Let $G_{2}=(\mathfrak{R}\cup\mathcal{S},E_{\mathfrak{R}\mathcal{S}})$ be a skill-concept graph, where $\mathcal{S}=\cup_{l}\mathcal{S}^{(l)}$ denotes a set of hierarchical skills, with finite number $S^{(l)}$ of skills in each level $l$. Each concept is connected to a unique skill at every level $l$, i.e., each concept enables learning of one skill at each level, and each skill $s^{(l)}$ is connected to $\sigma_{l}$ prerequisite skills at level $l-1$. Our unified framework is represented by the graph $G^{(C)}=G_{1}^{(C)}\cup G_{2}$ as shown in Figure 1.

Figure: Figure 1: A unified framework of learning concepts and skills by language models. The lower subgraph $G^{(C)}_{1}$ is a concept-text bipartite graph akin to a Tanner graph representation of an LDPC code. The upper subgraph $G_{2}$ shows concept-skill and skill-to-skill relationships, with multiple levels of skills denoted by $l$. Higher $l$ indicates more advanced skills.
Refer to caption: x1.png

### 2.3 Learning concepts from text pieces

Following the approach described in [], we assume that a language model learns concepts from text pieces as an iterative peeling process. For a self-contained explanation, let us briefly describe the peeling process here. Let $\mathcal{R}^{(u)}_{+}$ denote the set of concepts learnt, and $\mathcal{R}^{(u)}_{-}$ denote the set of concepts not learnt in peeling iteration $u$. Initially, all the concepts are unlearned, i.e., $\mathcal{R}^{(0)}_{-}=\mathcal{R}$ and $\mathcal{R}^{(0)}_{-}=\emptyset$. Next, a language model learns a concept $r\in\mathcal{R}^{(0)}_{-}$ if a text piece $t\in\mathcal{T}$ is uniquely connected to $r$ yielding $\mathcal{R}^{(1)}_{+}=\{r\}$ and $\mathcal{R}^{(1)}_{-}=\mathcal{R}^{(0)}_{-}\setminus\{r\}$. Before the next iteration, the edge $e_{tr}$ and concept node $r$ from the graph are removed. The next iteration starts by finding another text piece uniquely connected to a concept in $\mathcal{R}^{(1)}_{-}$, and this peeling process continues until there is either no more text piece/s connected to a unique concept in $\mathcal{R}_{-}$ or all the concepts are learnt, i.e., $\mathcal{R}_{+}=\mathcal{R}$.

### 2.4 Acquisition of skills and composition of skills

A skill $s^{(l+1)}$ at level $l+1$ is considered acquired when two conditions hold: 1) all the $\sigma_{l+1}$ prerequisite skills at the lower level $l$ are learnt, and 2) at least one concept associated with $s^{(l+1)}$ is learnt. A pair of concepts $(r_{1},r_{2})$ is considered connected (denoted by $r_{1}-r_{2}$) if there is a path $r_{1}-t-r_{2}$ through at least one text $t\in\mathcal{T}$. Then, for a fixed level $l$, a skill-graph $G_{2}^{(l)}=(\mathcal{S}^{(l)},E_{\mathcal{S}^{(l)}\times\mathcal{S}^{(l)}})$ is constructed as follows: A pair of skills $s_{1}$ and $s_{2}$ in $\mathcal{S}^{(l)}$ has a direct link (i.e., $e_{s_{1}s_{2}}\in E_{\mathcal{S}^{(l)}\times\mathcal{S}^{(l)}}$) if there are at least $\eta_{l}$ distinct paths $s^{(l)}_{1}-r_{1}-r_{2}-s^{(l)}_{2}$ (with at least $\eta_{l}$ distinct pairs of concepts $(r_{1},r_{2})$), and all the $2\sigma_{l}$ prerequisite skills required for both skills are acquired. The intuition behind this construction is that a pair of skills is connected (and therefore can be composed) if they co-occur sufficiently many times through distinct pairs of concepts in the training data, and all prerequisite skills of both skills are already acquired. Further, since more advanced skills are generally hard to learn, skills at higher levels (larger values of $l$) need larger values of $\eta_{l}$.

### 2.5 Defining emergence

In the context of neural language models, there are several definitions of skill emergence in the literature. In most existing frameworks, skills are directly associated with texts. In the skill-text bipartite graph framework of [], the fraction of text pieces in error (incorrect answers to cloze questions) is obtained from the Chinchilla rule, where the error fraction is smaller for larger model sizes. Emergence is defined in terms of the error rate of the skill-tuple, i.e., the fraction of edges to error-marked text pieces from $k$-tuple of skills, as follows: For a fixed target error threshold, with an increase in model size, emergence is defined as increase in the largest size of the skill tuple $k$ whose error rate is below the threshold. According to this definition of emergence, there is no phase transition and conforms to the notion that emergence is slow.

In [], emergence is defined as a function of the ratio of number of text pieces to skills: with increase in the ratio of number of texts to skills, emergence is defined as the increase in the size (normalized) of the largest connected component corresponding to the learnt skills. This definition of emergence exhibits a phase transition around a specific value of text-to-skill ratio. However, this definition of emergence as a function of text-to-skill ratio (not of model size) does not follow the definition of emergence, for example in []: “An ability is emergent if it is not present in smaller models but is present in larger models.”

A critical view of emergent abilities is given in [], arguing that emergence in performance (e.g. in terms of accuracy) is only a consequence of quantization of another metric (e.g. token edit distance) which shows gradual improvement with size scaling, and hence is only a mirage. Although this argument holds, we maintain a more optimistic view. How the performance of the model is measured is important, but corresponding to a performance metric, there is an abstract quantity such as the ability to compose multiple skills, which a language model gains when the model size exceeds a certain threshold to exhibit a true phase transition.

In our framework, advanced skills (larger $l$) are acquired from concepts and more basic skills, rather than directly from text pieces. To describe the composition of skills not seen in training, we begin by asserting transitivity of skill composition for a fixed skill level $l$: if the training data contains enough text pieces with composition of both pairs $(s^{(l)}_{1},s^{(l)}_{2})$ and $(s^{(l)}_{2},s^{(l)}_{3})$, then a language model is capable of composing skill $s^{(l)}_{1}$ and $s^{(l)}_{3}$. Consequently, a language model successfully performs a sub-task requiring a composition of a set of skills $\mathcal{S}_{\theta}^{(l)}\subseteq\mathcal{S}^{(l)}$ if there is a path between every pair of skills belonging to $\mathcal{S}_{\theta}^{(l)}$ in graph $G_{2}^{(l)}$.

For small compute budgets, dataset size corresponding to compute-optimal performance is small, in which case the training data contains composition of only a small number of skill pairs. As compute budget increases, the size of the training data increases, and therefore the number of composed skill pairs seen by the language model during training increases. Beyond a certain compute-budget threshold and due to skill composition transitivity, the ability of the language model to compose most skill pairs emerges, appearing as a phase transition around this compute-budget threshold. As we will see in Section 3.3, this phase transition is related to the appearance of a giant connected component (GCC) in random graphs with increasing edge probability. Our definition of emergence exhibits phase transition as empirically observed in language models, and our finitary analysis helps in conforming to the definition of emergence in [].

## 3 Explaining all three phenomena

Using the framework in Section 2, we aim to explain the compute-optimal (Chinchilla) scaling rule by applying non-asymptotic information-theoretic tools to the bipartite graph $G^{(C)}_{1}$ and to explain emergence and plateauing phenomena based on the density of connections in the skill-graphs $\{G_{2}^{(l)}\}_{l}$.

### 3.1 Compute-optimal scaling rule

Let $\mathcal{R}_{+}\subseteq\mathcal{R}$ denote the set of concepts learnt after the peeling process terminates. Note that the corresponding number of concepts $R_{+}=|\mathcal{R}_{+}|$ is a random variable. The goal of the language model is to learn as many concepts as possible from the text pieces under the compute budget constraint $C$, which yields the following constrained optimization problem.

$$ $\displaystyle\underset{R,T}{\mbox{maximize }}$ $\displaystyle\mathbbm{E}_{G^{(C)}_{1}\sim(\lambda_{T},\rho_{R})}[R_{+}]$ (1) s.t. $\displaystyle RT\leq C^{\prime},$ $$

where the number of model parameters $N=\varsigma R$, number of tokens in a text piece is $\tau$, $C^{\prime}=\frac{C}{6~{}\varsigma~{}\tau}$, and $(R^{*},T^{*})$ is the maximizer of the objective function in (1). It follows directly that the objective function in (1) can be rewritten as:

$$ $\mathbbm{E}_{G^{(C)}_{1}\sim(\lambda_{T},\rho_{R})}[R_{+}]=R(1-\Pr\{\mbox{$r \notin\mathcal{R}_{+}|R,T$}\})\mbox{.}$ (2) $$

For a bipartite graph sampled from a degree distribution pair $(\lambda_{T},\rho_{R})$, one may exactly compute the number of learned concepts using combinatorial arguments. However, the exact analysis becomes computationally expensive very quickly with increasing compute budget $C$ (equivalently $R$ and $T$). Moreover, since we are mainly interested in scaling behavior, the exact analysis may not be very insightful. Fortunately, observing that the peeling process is equivalent to iterative decoding of LDPC codes when the codeword symbols are corrupted by erasure, allows us to sidestep this difficulty. The trick is to construct a parent bipartite graph $\widetilde{G}^{(C)}_{1}$ with $(1-\epsilon)R/\epsilon$ additional concept nodes and degree distribution pair $\lambda_{T}$ and $\widetilde{\rho}_{R}$, such that the peeling process in this graph appears as belief propagation decoding of the $\epsilon$ fraction of erased codeword symbols (see Appendix A.2 for details), which yields

$$ $\Pr\{\mbox{$r\notin\mathcal{R}_{+}|R,T$}\}=\frac{P_{b,\lambda_{T},\widetilde{ \rho}_{R}}}{\epsilon},$ (3) $$

where $P_{b,\lambda_{T},\widetilde{\rho}_{R}}$ is the post-decoding bit erasure rate corresponding to $\widetilde{G}^{(C)}_{1}$.

Before providing an expression for $P_{b,\lambda_{T},\widetilde{\rho}_{R}}$ some notations are as follows: let $f(x,\epsilon)=\epsilon\lambda_{T}(1-\widetilde{\rho}_{R}(1-x))$, then the decoding threshold $\epsilon^{*}=\inf\{\epsilon\in[0,1]:x=f(x,\epsilon)\mbox{ has a solution in }x
\in(0,1]\}$, $x^{*}$ be a critical point satisfying $x^{*}=f(x^{*},\epsilon^{*})$, $\nu^{*}=\epsilon^{*}~{}L_{T}(1-\widetilde{\rho}_{\mathcal{R}}(1-x^{*}))$. Substituting for the post-decoding bit erasure rate $P_{b,\lambda_{T},\widetilde{\rho}_{R}}$, the objective function in (1) is given by (see Appendix A.2 for more details):

$$ $\mathbbm{E}_{G^{(C)}_{1}\sim(\lambda_{T},\rho_{R})}[R_{+}]\approx R\left(1- \frac{\nu^{*}}{\epsilon}Q\left(\sqrt{\frac{R}{\epsilon}}\frac{(\epsilon^{*}- \epsilon)}{\alpha}\right)\right),$ (4) $$

where $\alpha$ depends on the degree distribution pair $(\lambda_{T},\widetilde{\rho}_{R})$ (see Appendix A.2 for the closed-form expression), and $Q(\cdot)$ is the complementary Gaussian cumulative distribution function. In Figure 2, the objective function in (1) is plotted against the number of concepts $R$ for multiple compute budgets. In the left subfigure, each curve corresponds to a fixed compute budget. Note that smaller values of $R$ correspond to smaller language model sizes, in which case the dataset size (number of texts $T$) is more than necessary for the model to learn all the skills. Contrarily, for large model sizes, the smaller dataset size is insufficient to learn the concepts well. There is an optimum model size and dataset size pair (equivalently $R$ and $T$) such that the number of concepts learnt is maximized, as indicated by a solid black marker for each compute budget $C$. This figure is analogous to isoFLOP curves in [, Figure 2], where training loss is plotted against model size for different compute budgets.

Compute-optimal size scaling of model size and dataset size with increasing compute budget obtained by numerically solving (1) is shown Figure 3(a). The markers in the figure correspond to the empirically predicted model size and dataset size for compute-optimal performance of the Chinchilla model reported by [] when the compute budget is $5.76\times 10^{23}$. In the following proposition, we prove that the Chinchilla rule is optimal.

Figure: Figure 2: IsoFLOP curves: (left) Number of concepts learnt as a function of $R$ for different compute budgets (FLOPs); (right) Block erasure threshold as a function of the number of concepts $R$ for different compute budget. In both subfigures, solid black markers indicate the points corresponding to $R^{*}$.
Refer to caption: x2.png

###### Proposition 1 .

Compute-optimal scaling rule: For compute-optimal performance of a language model, the dataset size ($D$) and model size ($N$) must scale equally with the increasing compute budget $C$ (or FLOPs).

###### Proof.

The approach is to prove that neither $T/R=o(1)$ nor $R/T=o(1)$ maximizes the objective function in (1). This implies that $R/T$ must be a constant, i.e., $R$ and $T$ must scale equally with compute budget $C$.

Denote $\epsilon^{*}$ be the decoding threshold corresponding to the degree distribution pair $(\lambda_{T},\widetilde{\rho}_{R})$. From the matching condition [], we have

$$ $\epsilon^{*}\leq\frac{\int\widetilde{\rho}_{R}}{\int\lambda_{T}}=:\epsilon^{*} _{ub}$ $$

- (a)
If $\frac{T}{R}=o(1)$ (i.e., $\frac{T}{R}$ decays as $C\rightarrow\infty$), then
$\epsilon_{ub}^{*}-\epsilon\leq\epsilon\left(\left(1-e^{-d/\epsilon}+\frac{d^{2
}}{\epsilon R}\right)\left(\frac{1}{d}+\frac{T}{R}\right)-1\right)\xrightarrow
[]{C\rightarrow\infty}\epsilon\left(\frac{(1-e^{-d/\epsilon})}{d}-1\right)<0,$
which implies that $P_{b,\lambda_{T},\widetilde{\rho}_{R}}\rightarrow 1$. Therefore, number of skills learnt vanishes for large $C$.
- (b)
Consider $\frac{R}{T}=o(1)$.
From the fixed point characterization of decoding threshold of LDPC codes, we have
$\displaystyle f(x,\epsilon^{*})$
$\displaystyle=\epsilon^{*}\lambda_{T}(1-\widetilde{\rho}_{R}(1-x)),$
$\displaystyle=\epsilon^{*}(1-(1-xp)^{\frac{R}{\epsilon}-1}p)^{T-1},$
(5)
where $p=d_{t}/R$. Since $R/T=o(1)$, the number of text pieces $T$ grows strictly faster than $R$ with respect to compute budget $C$, implying that the second term in (5), i.e., $(1-(1-xp)^{\frac{R}{\epsilon}-1}p)^{T-1}\rightarrow 0$ for large $C$. Therefore, for a non-trivial solution, i.e., $x=f(x,\epsilon^{*})\in(0,1]$, the decoding threshold $\epsilon^{*}$ must be very large. As a result, the post-decoding bit erasure rate $P_{b,\lambda_{T},\widetilde{\rho}_{R}}$ vanishes for large $C$.
Suppose, $(R^{*}_{C},T^{*}_{C})$ such that $R^{*}_{C}/T^{*}_{C}=o(1)$ minimizes (1). Now, consider $\hat{R}_{C}=R^{*}_{C}(1+\delta)$ and $\hat{T}_{C}=T^{*}_{C}/(1+\delta)$. Note that $\hat{R}_{C}/\hat{T}_{C}=(1+\delta)^{2}R^{*}_{C}/T^{*}_{C}=o(1)$. Therefore, for any $\delta^{\prime}\in(0,\delta)$, there exists $C_{0}$ such that for all $C\geq C_{0}$ the bit erasure rate $\epsilon^{-1}P_{b,\lambda_{\hat{T}_{C}},\widetilde{\rho}_{\hat{R}_{C}}}\leq
\delta^{\prime}/(1+\delta^{\prime})$. Now consider the ratio of number of concepts learnt:
$\frac{\hat{R}_{C}(1-\epsilon^{-1}P_{b,\lambda_{\hat{T}_{C}},\widetilde{\rho}_{
\hat{R}_{C}})}}{R^{*}_{C}(1-\epsilon^{-1}P_{b,\lambda_{T^{*}_{C}},\widetilde{
\rho}_{R^{*}_{C}}})}\geq\frac{R^{*}_{C}(1+\delta)\left(1-\frac{\delta^{\prime}
}{1+\delta^{\prime}}\right)}{R_{C}^{*}}=\frac{1+\delta}{1-\delta^{\prime}}>1,$
(6)
where the first inequality is by substitution and using the fact that $\epsilon^{-1}P_{b,\lambda_{T^{*}_{C}},\widetilde{\rho}_{R^{*}_{C}}}$ is non-negative, and the second inequality is because $\delta^{\prime}<\delta$. Therefore, $(R^{*}_{C},T^{*}_{C})$ is not a maximizer, which is a contradiction. Therefore, $R/T$ cannot be $o(1)$.

Therefore, $R/T$ must asymptotically be a constant. In other words, the model size $N$ and dataset size $D$ must scale equally with compute budget $C$.

∎

Figure: Figure 3: (a) Model and dataset size pair $(N^{*},D^{*})$ that maximizes (1) as a function of compute budget $C$. The curves being parallel in logarithmic scale indicates that model size and dataset size must scale equally with $C$. In this subplot, we set $\varsigma=2\times 10^{5}$, $\tau=8\times 10^{5}$, and $d_{t}=6$. The markers indicate $(N,D)$ corresponding to the compute-optimal performance predicted by the Chinchilla rule [] when compute budget is $5.76\times 10^{23}$ (dashed vertical line); (b) Scaling of the lower bound of excess entropy in (8) compared with empirically observed scaling according to [] as a function of the model size $N^{*}$.
Refer to caption: x3.png

###### Proposition 1 .

###### Proof.

### 3.2 Scaling of excess entropy

Under finitary analysis, for every compute budget $C$, there is an associated error rate $P_{b,\lambda_{T},\widetilde{\rho}_{R}}/\epsilon$ which indicates a fraction of concepts are not learnt even after the peeling process is complete. Similar to [], we assume that cloze questions associated with text pieces connected to unlearnt concepts are incorrectly answered. Therefore, the training error is equivalent to the probability that a check node (text piece) is connected to the stopping set (unlearnt concepts) at least twice. Refer to [] on stopping sets. The training error corresponding to $(N,D)$ given a compute budget $C$ is (see Appendix B for the calculation):

$$ $P_{e,train}=1-\left(1-\frac{d_{t}P_{b}}{R}\right)^{R-1}-d_{t}P_{b}\left(1- \frac{d_{t}P_{b}}{R}\right)^{R-1}\approx 4d_{t}^{2}\epsilon^{-2}P_{b,\lambda_{ T},\widetilde{\rho}_{R}}^{2}.$ (7) $$

Using Pinsker’s inequality that relates Kullback-Leibler divergence to total variational distance as $D_{KL}(P||Q)\geq\frac{1}{2}||P-Q||_{1}^{2}$, and the equivalence between total variation distance and error rate on cloze questions [], we obtain the following lower bound on excess entropy:

$$ $\mbox{Excess entropy}\geq\frac{1}{2}P_{e,train}^{2}\approx 2d_{t}^{4}\epsilon^ {-4}P_{b,\lambda_{T},\widetilde{\rho}_{R}}^{4}.$ (8) $$

Empirically observed excess entropy scaling of transformer-based models and a lower bound according to our framework in (8) are depicted in Figure 3(b). The gap between them indicates the scope for either tightening theoretical lower bound or devising architectures that offer better empirical scaling or both.

### 3.3 Emergence

As the model size increases (along with the compute budget $C$) there is a sharp increase in performance (e.g. accuracy) of the language model on certain complex tasks which the model was not trained on. We aim to provide a simple explanation to this empirical phenomenon using random graph theory.

Figure: Figure 4: Accuracy of the language model sharply increases after the model size (equivalently $C$) exceeds a threshold, which is a consequence of the emergence of a GCC in a skill graph $G_{2}^{(l)}$. (a) Step increase in accuracy for a homogeneous task. (b) Skill level distribution $q(l)$ for unimodal and multimodal heterogeneous tasks. (c) Smooth emergence for unimodal heterogeneous task. (d) Plateauing phenomena as a consequence of a task requiring diverse skills according to multimodal distribution. In this subplot, we used the following values for the parameters: number of skill levels $L=100$, $S^{(l)}=10^{3}$, $\eta_{l}=\exp(7l/L)$, $\sigma_{l}=\log_{2}(l)$ for all $l\in\{1,\ldots,L\}$, $q(m)=1/6$ for all $m\in\{2,\ldots,7\}$, .
Refer to caption: x4.png

Let $p_{l}$ denote the probability there is a direct link between any two pairs of skills at level $l$. For a fixed $(R,T)$, $p_{l}$ evaluates as
(see Appendix C for the derivation):

$$ $p_{l}\geq\begin{cases}\left(1-g(R,p_{rr},\eta_{l})\right)\gamma_{l-1}^{2\sigma _{l}}&\mbox{if }\eta_{l}\leq\binom{R}{2}p_{rr}\\ \frac{1}{\sqrt{8\eta_{l}\left(1-\eta_{l}/\binom{R}{2}\right)}}g(R,p_{rr},\eta_ {l})\gamma_{l-1}^{2\sigma_{l}}&\mbox{otherwise,}\end{cases}$ (9) $$

where $g(R,p_{rr},\eta_{l})=\exp\left(-\binom{R}{2}D_{KL}\left(\frac{\eta_{l}}{\binom
{R}{2}}||p_{rr}\right)\right)$, $p_{rr}$ is the probability that a pair of concepts occur in at least one text piece, and $\gamma_{l-1}$ is the probability that a skill belongs to GCC of $G^{(l)}_{2}$ (which we show next). Recall the definition of emergence from Section 2.5 as the ability of a language model to compose all pairs of skills within a subset of skills in a given level $l$ required for a specific task. In this regard, note that the skill graph $G_{2}^{(l)}$ is equivalent to an Erdös-Rényi (ER) random graph with $S^{(l)}$ nodes and edge probability $p_{l}$. A pair of skills in level $l$ can be composed if there is a path between them in $G_{2}^{(l)}$, and the probability that there is a path between any pair of skills is bounded below by the probability that both skills are in GCC of $G_{2}^{(l)}$.

Suppose $\gamma_{l}$ is ratio of the size of GCC in $G_{2}$ to the total number of skills (number of nodes in $G^{(l)}_{2}$) at level $l$, i.e., $\gamma_{l}=S^{(l)}_{GCC}/S^{(l)}$. Note that $\gamma_{l}$ is equivalent to the probability that a skill at level $l$ is in GCC. From random graph theory [], for an ER graph with edge probability $p_{l}$, the solution to the following equation yields $\gamma_{l}$:

$$ $\gamma_{l}=1-\exp\left(-p_{l}S^{(l)}\gamma_{l}\right),$ (10) $$

where $p_{l}S^{(l)}$ is the mean degree of the ER skill graph. The solution is

$$ $\gamma_{l}=1+\frac{1}{p_{l}S^{(l)}}W_{0}\left(-p_{l}S^{(l)}\exp\left(-p_{l}S^{ (l)}\right)\right),$ (11) $$

where $W_{0}(\cdot)$ is the upper branch of the Lambert $W$ function. The ratio $\gamma_{l}$ has a phase transition at $p_{l}=1/S^{(l)}$. To see this, note that $W_{0}(xe^{x})=x$ for $x<-1$. Therefore, whenever $p_{l}<1/S^{(l)}$, $\gamma_{l}$ is identically zero. As $p_{l}$ increases beyond $1/S^{(l)}$, $|W_{0}(\cdot)|$ starts decreasing and consequently, $\gamma_{l}$ increases.

For a particular skill level $l$, $\gamma_{l}$ and $p_{l}$ can be computed recursively using (11) and (9), with the following initial conditions: $\gamma_{0}$ = 1 and $\sigma_{l}$ = 0 (observe that no prerequisite skill is required to learn basic skills, i.e., skills at $l=1$). Suppose a task requires $m$ skills at level $l$ (a homogeneous task), the model performs the task successfully only if there is a path between every pair of those skills in $G_{2}^{(l)}$. Therefore, a sufficient condition is that all skills required for the task are in GCC. The accuracy of the task is:

$$ Accuracy $\displaystyle=\Pr\{\mbox{Composition of $m$ skills in }\mathcal{S}^{(l)}\},$ $\displaystyle=\Pr\{\mbox{There exists a path between every pair among $m$ skills in }\mathcal{S}^{(l)}\},$ $\displaystyle\geq\Pr\{\mbox{All $m$ skills $\in$ GCC of $G_{2}^{(l)}$ }\}= \gamma_{l}^{m}.$ (12) $$

The accuracy curve in Figure 4 shows a step phase transition with increasing model size. This is a consequence of the homogeneous task requiring skills at only one level. However, empirically observed accuracy curves exhibit smoother phase transitions []. To demonstrate a smoother phase transition, consider a complex heterogeneous task that requires diverse skills at different levels, in particular consisting of subtasks requiring $m$ skills at level $l$ with probability $q(l,m)$. Task accuracy is:

$$ $\mbox{Accuracy}\geq\sum_{l,m}q(l,m)\gamma_{l}^{m}.$ (13) $$

The overall accuracy is therefore a weighted average of the emergence curves. To illustrate this using a numerical example, consider a skill graph $G_{2}$ with $L=100$ levels, let $q(m,l)=q(m)q(l)$ with $q(m)=1/6$ for $m\in\{2,\ldots,7\}$ and consider a binomial distribution, $\mbox{Binomial}(L,1/2)$, over the skill levels, i.e., $q(l)=\binom{L}{l}(\frac{1}{2})^{L}$ as shown in Figure 4(b). The corresponding accuracy according to (13) is shown in Figure 4(c). In general, a smooth single phase transition can be obtained by a unimodal distribution over skill levels with a sufficiently large variance.

### 3.4 Plateauing

According to our framework, plateauing in accuracy after encountering an emergent phenomenon (with scaling) occurs because of the greater diversity of skills (at multiple levels) required by the heterogeneous task under consideration. In particular, we observe plateauing when the skill levels required for a task follows a multimodal distribution. To illustrate this, consider a mixture of binomial distributions over the skill levels, i.e., $q(l)=\sum_{i}w_{i}\mbox{Binomial}(L,\pi_{i})$, with $(w_{i})_{i}\in(2/5,2/5,1/5)$ and $(\pi_{i})_{i}=(0.2,0.6,0.95)$ is shown in Figure 4(b). The corresponding accuracy according to (13) is shown in Figure 4(d). In general, a multimodal distribution over skill levels results in emergence at multiple scales and plateaus between them. Our framework yields an interesting trend associated with the plateauing of performance: plateauing indicates the possibility of one (or more) upcoming emergent phenomenon (phenomena), which one would encounter with further scaling.

## 4 Conclusion

We presented a simple unified framework to explain all three empirical phenomena observed with size scaling of language models. Existing frameworks assume a compute-optimal scaling rule and only then explain emergent phenomena. We use non-asymptotic information theory to explain both compute-optimal size scaling and emergent abilities of language models. Moreover, we explain the more recent empirical phenomenon of plateauing of performance using random network theory, and also predict that plateauing implies the possibility of multiple emergent phenomena with further size scaling.

There are some open questions and considerations worth exploring. We do not take training time into account in our framework. Therefore, we do not explain (or attempt to explain) empirical phenomena such as double descent or grokking []. Perhaps future work can either incorporate training epochs in our framework or propose a different novel framework to explain them. Even though the sequential learning of concepts through peeling process gives certain ordering to concepts, there is no inherent ordering of concepts and we do not consider concept hierarchies [, ]. One can explore the advantages of doing so. Evidently, the degree distribution of texts is related to the model’s architecture. Therefore, optimizing the degree distribution enables a language model to learn more concepts from text pieces. Further, the quality of the training data is related to text-to-concept edge deletions in sequential concept learning, which can be incorporated into our framework. Such optimization is a line of future work that has natural analogues in optimization of communication systems and fault-tolerant computation [].

## Acknowledgment

We appreciate discussion with and valuable suggestions from Razan Baltaji, Akhil Bhimaraju, and Moulik Choraria.

This work was supported in part by National Science Foundation grant PHY-2112890 and by DARPA grant “Modeling and Measuring Scientific Creativity”.

## Appendix A Solving ( 1 ): Maximizing concept learning under compute budget constraint

### A.1 A brief summary of belief propagation decoding of LDPC codes under erasure

Low-density parity check (LDPC) codes are a family of error-correction codes, whose noisy codewords can be decoded in a computationally efficient manner using belief propagation. Before getting into deriving the probability that a concept is learnt from text pieces, we provide a very short summary of belief propagation decoding of LDPC codes when codeword symbols are corrupted by erasure. An LDPC code can be graphically represented by a Tanner graph, which is a bipartite graph with a set of variable nodes (codeword symbols) and check nodes (parity checks). Each codeword satisfies all the parity checks. Given a degree distribution pair (for variable and check nodes), there is a channel noise threshold $\epsilon^{*}$ above which the decoder fails to decode the transmitted codeword. Consider a noisy version of a transmitted codeword with $\epsilon<\epsilon^{*}$ fraction of the symbols are erased. Belief propagation decoding starts by finding a check node where all except one symbol are recieved correctly (not erased). Then the erased symbol is determined as the one satisfying the parity. The next iteration starts by finding another check node with only one erased codeword symbol. This process continues until either all the codeword symbols are decoded or the decoder gets stuck with no parity checks containing only one erased symbol. The latter is declared as a decoding failure.

### A.2 Computing Pr ⁡ { r ∉ ℛ + | R , T } probability 𝑟 conditional subscript ℛ 𝑅 𝑇 \Pr\{\mbox{$r\notin\mathcal{R}_{+}|R,T$}\} roman_Pr { italic_r ∉ caligraphic_R start_POSTSUBSCRIPT + end_POSTSUBSCRIPT | italic_R , italic_T }

$$ $\displaystyle\widetilde{P}_{R}$ $\displaystyle=\mbox{Binomial}(R/\epsilon,p),\mbox{ and}$ (14) $\displaystyle\widetilde{L}_{T}=L_{T}$ $\displaystyle=\mbox{Binomial}(T,p),$ (15) $$

respectively. Here, for a compute budget $C$, we set $T=\frac{C}{6\varsigma\tau R}$.

Figure: Figure 5: Bipartite graph $\widetilde{G}_{1}$.
Refer to caption: x5.png

In belief propagation decoding (peeling) of a codeword affected by erasures, the post-decoding bit erasure rate depends only on the residual graph consisting only variable nodes corresponding to erased symbols, parity checks connecting those variable nodes, and edges between them. Therefore, the post-decoding bit erasure rate is invariant to the choice of $\epsilon$.(^3^33Here we choose $\epsilon=0.5$ (instead of close to 0 or 1) for numerical convenience.) Therefore, we can make the following equivalence between concept learning and bit erasure rate:

$$ $\Pr\{\mbox{$r\notin\mathcal{R}_{+}|R,T$}\}=\frac{P_{b,\lambda_{T},\widetilde{ \rho}_{R}}}{\epsilon},$ (16) $$

where $P_{b,\lambda_{T},\widetilde{\rho}_{R}}$ is the post-decoding bit erasure rate, and $\lambda_{T}(x)=\frac{L^{\prime}_{T}(x)}{L^{\prime}_{T}(1)}$ and $\widetilde{\rho}_{R}(x)=\frac{\widetilde{P}^{\prime}_{R}(x)}{\widetilde{P}^{
\prime}_{R}(1)}$ are variable and check node degree distributions from edge perspective, respectively. To compute $P_{b,\lambda_{T},\widetilde{\rho}_{R}}$ we need the following ingredients: degree distributions $\lambda_{T}$ and $\widetilde{\rho}_{R}$, decoding threshold $\epsilon^{*}$, and scaling factors $\nu^{*}$ and $\alpha$ which depend on degree distributions. Degree distribution of text pieces from the node perspective is

$$ $\displaystyle P_{R}(x)$ $\displaystyle=\sum_{i}\binom{R}{i}p^{i}(1-p)^{R-i}x^{i},$ (17) $\displaystyle\widetilde{P}_{R}(x)$ $\displaystyle=\sum_{i}\binom{R/\epsilon}{i}p^{i}(1-p)^{(R/\epsilon)-i}x^{i},$ (18) $$

which gives the following text degree distribution from the edge perspective:

$$ $\widetilde{\rho}_{R}(x)=\frac{\widetilde{P}^{\prime}_{R}(x)}{\widetilde{P}^{ \prime}_{R}(1)}=\frac{\sum_{i}i\binom{R/\epsilon}{i}p^{i}(1-p)^{(R/\epsilon)-i }x^{i-1}}{\sum_{i}i\binom{R/\epsilon}{i}p^{i}(1-p)^{(R/\epsilon)-i}}.$ (19) $$

Noting that $i\binom{R/\epsilon}{i}=R\binom{R/\epsilon-1}{i-1}$ we obtain the degree distribution of text pieces from edge perspective:

$$ $\displaystyle\widetilde{\rho}_{R}(x)$ $\displaystyle=\frac{\sum^{(R/\epsilon)-1}_{j=0}\frac{R}{\epsilon}p\binom{R/ \epsilon-1}{j}p^{i-1}(1-p)^{(R/\epsilon)-i}x^{i-1}}{\frac{R}{\epsilon}p}$ (20) $\displaystyle=(px+(1-p))^{\frac{R}{\epsilon}-1}.$ (21) $$

Similarly, the degree distribution of concepts (remains unchanged for a fixed $R$, $T$) from the edge perspective is

$$ $\lambda_{T}(x)=(px+(1-p))^{T-1}.$ (22) $$

Next the belief propagation decoding threshold $\epsilon^{*}$ is obtained from its fixed point characterization [, Section 3.12]:

$$ $\epsilon^{*}=\inf\{\epsilon\in[0,1]:x=f(x,\epsilon)\mbox{ has a solution in }x \in(0,1]\},$ (23) $$

where $f(x,\epsilon)=\epsilon\lambda_{T}(1-\widetilde{\rho}_{R}(1-x))$, and the critical point $x^{*}$ satisfies $x^{*}=f(x^{*},\epsilon^{*})$.

From finite-length scaling law of error rates in belief propagation decoding [, Section 3.23], we have the following (approximate) closed-form expression for post-decoding bit erasure rate:

$$ $P_{b,\lambda_{T},\widetilde{\rho}_{R}}\approx\nu^{*}Q\left(\sqrt{\frac{R}{ \epsilon}}\frac{(\epsilon^{*}-\epsilon)}{\alpha}\right),$ (24) $$

where $\nu^{*}=\epsilon^{*}~{}L_{T}(1-\widetilde{\rho}_{\mathcal{R}}(1-x^{*}))$, $Q(\cdot)$ is the complementary standard Gaussian cumulative distribution function, and the scaling parameter $\alpha$ is given by [, Section 3.23]

$$ $\displaystyle\alpha=$ $\displaystyle\left(\frac{\rho(\bar{x}^{*})^{2}-\rho((\bar{x}^{*})^{2})+\rho^{ \prime}(\bar{x}^{*})(1-2x^{*}\rho(\bar{x}^{*}))-(\bar{x}^{*})^{2}\rho^{\prime} ((\bar{x}^{*})^{2})}{L^{\prime}_{T}(1)\lambda_{T}(y^{*})^{2}\rho^{\prime}(\bar {x}^{*})^{2}}\right.+$ (25) $\displaystyle~{}\left.\frac{(\epsilon^{*})^{2}\lambda(y^{*})^{2}-(\epsilon^{*} )^{2}\lambda_{T}((y^{*})^{2})-(y^{*})^{2}(\epsilon^{*})^{2}\lambda_{T}^{\prime }((y^{*})^{2})}{L_{T}^{\prime}(1)\lambda(y^{*})^{2}}\right)^{1/2},$ (26) $$

where $x^{*}$ is the unique critical point, $\bar{x}^{*}=1-x^{*}$, and $y^{*}=1-\widetilde{\rho}_{R}(1-x^{*})$.

## Appendix B Calculation of P e , t ⁢ r ⁢ a ⁢ i ⁢ n subscript 𝑃 𝑒 𝑡 𝑟 𝑎 𝑖 𝑛 P_{e,train} italic_P start_POSTSUBSCRIPT italic_e , italic_t italic_r italic_a italic_i italic_n end_POSTSUBSCRIPT

Recall that the training error is equivalent to finding the probability that a text piece is connected to an unlearnt concept, i.e.,

$$ $\displaystyle P_{e,train}$ $\displaystyle=\Pr\left(|\{e_{tr}\in G_{1}^{(C)}\}_{r\in\mathcal{R}_{-}}|\geq 2 \right),\mbox{ for any $t\in\mathcal{T}$},$ (27) $\displaystyle=\sum_{k\geq 2}^{R}\Pr\left(\mbox{degree}(t)=k,\{|\{e_{tr}\in G_{ 1}^{(C)}\}_{r\in\mathcal{R}_{-}}|\leq 1\}^{c}\right),$ (28) $\displaystyle=\sum_{k\geq 2}^{R}\binom{R}{k}p^{k}(1-p)^{R-k}\left(1-(1-P_{b})^ {k}-kR(1-P_{b})^{k-1}\right),$ (29) $$

where the edge probability $p=d_{t}/R$ and $P_{b}=\epsilon^{-1}P_{b,\lambda_{T},\widetilde{\rho}_{R}}$. The last equation simplifies to:

$$ $P_{e,train}=1-\left(1-\frac{d_{t}P_{b}}{R}\right)^{R-1}-d_{t}P_{b}\left(1- \frac{d_{t}P_{b}}{R}\right)^{R-1},$ (30) $$

which is obtained by computing the expectation of each of the three terms within the summation in (29) and substituting $p=d_{t}/R$. Further using the approximations $(1-x)^{n}\approx 1-nx$ and $R-1\approx R$ for large $R$, the training error is approximately $P_{e,train}\approx 4d_{t}^{2}P_{b}^{2}$.

## Appendix C Calculation of p l subscript 𝑝 𝑙 p_{l} italic_p start_POSTSUBSCRIPT italic_l end_POSTSUBSCRIPT

Recall that $p_{l}$ is the probability that the composition of a pair of skills in level $l$ is seen at least $\eta_{l}$ times in the training data.
For a fixed pair of skills $(s_{1},s_{2})$, the probability there is a path between the pair of skills through some pair of concepts $(r_{1},r_{2})$ is

$$ $\displaystyle\Pr(s_{1}-r_{1}-r_{2}-s_{2})$ $\displaystyle=\Pr(s_{1}-r_{1},r_{1}-r_{2},r_{2}-s_{2}),$ $\displaystyle=\Pr(s_{1}-r_{1})\Pr(r_{1}-r_{2})\Pr(r_{2}-s_{2}),$ $\displaystyle=\frac{1}{S^{(l)}}\left(1-\left(1-\frac{d_{t}^{2}}{R^{2}}\right)^ {T}\right)\frac{1}{S^{(l)}}=:p_{rr},$ $$

where the second inequality is due to independence of $s_{1}-r_{1}$, $r_{1}-r_{2}$ and $r_{2}-s_{2}$.
Let $X$ be a random variable indicating the number of distinct paths $s_{1}-r_{1}-r_{2}-s_{2}$ between $s_{1}$ and $s_{2}$. Now, $\Pr\left(\mbox{composition of}(s_{1},s_{2})\mbox{ in training data}\right)=:p_
{l}$ is

$$ $\displaystyle p_{l}$ $\displaystyle=\Pr(X\geq\eta_{l},\mbox{all prerequisite skills of $s_{1}$ and $ s_{2}$ are acquired}),$ $\displaystyle\geq\Pr(X\geq\eta_{l})\Pr(\mbox{all prerequisite skills of $s_{1} $ and $s_{2}$ are acquired}).$ $$

Note that the total number of distinct paths between $s_{1}$ and $s_{2}$ equals the total number of concept pairs $(r_{1},r_{2})$ which is $\binom{R}{2}$, each with probability $p_{rr}$. Therefore, $X$ follows a binomial distribution, i.e., $\mbox{Binomial}\left(\binom{R}{2},~{}p_{rr}\right)$. From Chernoff’s bound for binomial distribution, we obtain the following lower bounds:

$$ $\Pr(X\geq\eta_{l})\geq\begin{cases}1-\exp\left(-\binom{R}{2}D_{KL}\left(\frac{ \eta_{l}}{\binom{R}{2}}||p_{rr}\right)\right)&\mbox{if }\eta_{l}\leq\binom{R}{ 2}p_{rr}\\ \frac{1}{\sqrt{8\eta_{l}\left(1-\frac{\eta_{l}}{\binom{R}{2}}\right)}}\exp \left(-\binom{R}{2}D_{KL}\left(\frac{\eta_{l}}{\binom{R}{2}}||p_{rr}\right) \right)&\mbox{otherwise.}\end{cases}$ (31) $$

The probability of acquiring prerequisite skills of both skills $s_{1}$ and $s_{2}$ is (assuming $R\gg\sigma_{l}$),

$$ $\displaystyle\Pr(\mbox{all prerequisite skills of $s_{1}$ and $s_{2}$ are acquired})$ $\displaystyle\geq\Pr(\mbox{all $\sigma_{l}$ prerequisites $\in$ GCC})^{2},$ $\displaystyle=\gamma^{2\sigma_{l}}_{l-1}.$ $$

## Peer Reviews

confidence: 4
contribution: 3
initial_rating: 8
presentation: 3
questions: *Some minor issues, in appendix C, should the value in equation 29 is only approximately equal to the value in equation 30? Also, the approximation $(1-x)^n = 1-nx$ should be tight with some additional conditions. In this case, this approximation is tight, only when $p_b$ is also small.
*In line 759, Chernoff's bounds have multiple forms. One reference should be given here.
soundness: 4
strengths: *The paper presents a creative way of using existing theories in low-density parity-check codes and random graphs to solve large language model analysis problems. 
*It is convincing that one theory can be used to explain multiple phenomenon in large language model scaling.
*The paper is of good quality, the theoretical analysis are solid.
*The paper is well-written. 
*The theory is of significance, because understanding the scaling laws of large language models may provide further guidance for future model training and scaling.
summary: This paper present a very interesting theory on large language model scaling laws using ideas from information theory, random graphs, and low-density parity-check codes. By drawing similarities between concept-text graphs, skill-concept graphs to Tanner graphs in low-density parity-check codes, the paper provides a theoretical explanations of the phenomenon observed in large language models, including compute-optimal scaling law, scaling law of excess entropy, emergence, and plateauing. The theoretical predicted scaling laws are compared with the empirical laws observed in real-world language models.
weaknesses: *I think one assumption the paper makes is that the peeling process has stopped after the model training. Nowadays, many language models are only trained with several epochs. Can we always assume that the peeling process have already stopped after the training? 
*Not necessary in this paper, but it would be good to have more numerical experiments that this peeling process indeed happens in training.
*The paper assumes that the graphs can be randomly generated, so that we have particular binomial degree distributions. Is it possible to verify indeed this is the case in the real-world. Do the theory in the paper also hold for other degree distributions.

---

confidence: 5
contribution: 1
initial_rating: 3
presentation: 2
questions: Simple questions as mentioned earlier:
1. How to define text, concepts, and skills, and given some test or bit sequence, how do we determine which category it falls into?
2. What experiments can be used to verify the theory?
soundness: 1
strengths: The goal of the paper is ambitious. A unifying theory that can help explain the scaling behavior will be quite nice.
summary: The authors proposed a theory for scaling in neural networks via a connection to LDPC code. The authors then claim that the theory leads to explanation of scaling, emergence, and plateaus in language models.
weaknesses: Though the effort is appreciated, and there might be some merit to the overall approach, I feel the overall theory is not set up in sufficiently rigorous manner.

1. Reading the paper gives me the feeling that authors are promising too much, but nothing has been theoretically established carefully. First of all, the framework is given in a very vague manner, with the basic definitions for text, concepts, and skills missing. Without rigorous definitions, we cannot come up with simple examples to verify the theory. For example, if I'm given a text sequence, how do I determine if it is a text, a concept, or a skill? Are they all limited by the representation and the length? The theory is shaky when we cannot even answer these basic questions.

2. There seems to be less connection to ML than to LDPC. If we simply replace the text, concept, and skill nodes in the graph with variable and factor nodes in the original LDPC, then the claim holds trivially. This is an extremely weak connection, in names only, without any deeper insights.

3. There are no relevant experimental results for language models at all in the paper. For a theory to hold, we must have some kind of verification with the ML models. The paper reads like this: there are some observations in ML, and it happens that similar effects also occur in other settings, so that theory will fit. This might be a good starting point to contemplate and develop deeper research, but scientific/engineering research cannot stop here.

4. The big concern for me is that the theory is so vaguely defined that it is impossible to come up with experiments to verify whether it is true or not. This is a rather dangerous territory, as it does not follow the standard scientific research approach, and is more like a belief/religion in its current form.

---

confidence: 3
contribution: 2
initial_rating: 3
presentation: 2
questions: Some suggestions:
Please specify in the setup that the skills graph obeys the  Erdos-Renyi random graph model, as you later claim in L346.

Paragraphs in Lines 210-215 are related to the high-level discussion of “what is a skill” and therefore should be part of the exposition. 

The study would have a much better case if the authors could show measurable quantities like accuracy and the number of learned skills obtained from the model side by side with those obtained from actual language models.
soundness: 2
strengths: Motivation: The framework seems reasonable and diverse enough to model learning and acquisition of new skills. As the authors mentioned, it may be possible to incorporate into the framework additional considerations such as the quality of training data. It would be interesting to discover what can we learn in the training of language models due to this analysis. 

The topic and theoretical framework are related to other recent works, hence it seems like this topic has created enough interest in the community. 

Using tools developed in coding theory and random graph theory in probability seems to have great potential in this context. The authors say “Our work takes a step in grounding empirical phenomena observed in size scaling of language models on a rigorous mathematical footing.” I would put it differently: ``The work proposes a graph-based model for learning skills from texts that appears relevant to the process of training a large language model. The dynamics of message passing under an asymptotic scaling of the model’s size experience phenomenon akin to those empirically observed in this training process of a large language model, such as the emergence of abilities and the plateauing of performance.’’
summary: The paper proposes an abstraction of the learning process of a large language model using graphs and analyze the behavior of certain dynamics on these graphs. The purpose is to draw a connection to certain observed phenomena of large language models such as the emergence of learned capabilities and the plateauing of performance with size-scaling. 

I found the topic and the framework interesting and worthy of a discussion. However, there are many weaknesses in writing, presentation, and technical issues that makes it difficult to evaluate the paper’s contributions.
weaknesses: Background and Motivation.
It is unclear what parts of the framework have been considered in previous works. For example, did other work also consider hierarchical skills? Did previous works also try to analyze message-passing dynamics but perhaps using different tools? How significant is the automatic selection of scaling law from the framework compared to previous works? What is the rationale that N (#of parameters) is proportional to R (# of skills)? What is the rationale for studying a limited computed budget and thus the tradeoff N T < C? Do we see such a tradeoff in training language models? 

Also, in the abstract and introduction, please be clear whether ‘size’ means the number of parameters or the size of training data. 

The connection to language models is not immediate and it appears that one can replace the language model with any form of a learning machine, like a human. Consequently, I’d expect in this line of work at least some discussions on studies on learning and education in general. Also related: Line 102 says that a language model “chooses to learn.” This seems like a poor choice of words because it is unclear what is the choosing mechanism. Another similar poor choice of word or issue with the motivation is L245: “The goal of the language model is to learn as many concepts as possible…” Of course, actual training in a language model does not directly involve the concept of “concepts”.

The authors say that they use tools from information theory but this is inaccurate because they use statistical mechanics ideas from graph-based coding (Richardson & Urbanke 2008) and random graph theory. The terms information theory and especially non-asymptotic information theory are misleading.  


Analysis. 
In general, I found it difficult to follow almost all technical derivations due to missing details. Examples:
What are the {Pi} s in L124? 
What is the “matching condition” in L316
What is r in Eq 2 ? I don’t see how this equation is equivalent to the problem in Eq 1.
What are r and epsilon in Eq 3? 
What is epsilon in Eqs 7 & 8?
What is the origin of the name “post-decoding bit erasure rate”?
What is “excess entropy”? Why do we care about bounding it from below?

The paper mentions compute-optimal scaling but I did not find a clear definition. 
The paper does not explain what the author calls the ``decoding process’’. 

Proposition 1 appears to be flawed. It is not true that if neither R/T = o(1) nor T/R = o(1) hold then R/T → constant (the text actually says “R/T must be a constant”, which is grossly incorrect). As a counterexample, take R = sin(C), T=cos(C). To my understanding, the author quotes this proposition as one of the main contributions of their work, so this needs correction. This proposition is also unclear because the notion of “compute-optimal performance of a language model” has not been well-defined earlier.

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 2
questions: The LHS of (4) is an expression that does not depend on $\epsilon$. However, the approximation expression in the RHS of (4) depends on $\epsilon$. How can we explain about this approximation? Can $\epsilon$ take arbitrary value as mentioned in the proof  in Appendix A.2?
soundness: 3
strengths: This paper has some strengths:

+ The authors can explain three phenomena mentioned above by using their unified framework. 
+ The trick to solve the optimisation problem (1) by considering the peeling process of learning concepts from texts to be identical to belief propagation decoding of an LDPC code when the channel noise is erasure is interesting.
summary: This paper provides an unified mathematical framework to explain three phenomena with increasing size of language models: compute-optimal size scaling, emergent capabilities, and performance plateauing. This framework is proposed based on the notation of learning as two levels: (1) a set of concepts are learnt from a set of texts;  (2) learning concepts enables the language model to acquire skills. The authors prove the compute-optimal (Chinchilla) scaling rule based on non-asymptotic information-theoretic tools to the bipartite graph between texts and concepts, and explain the emergence and plateauing phenomena based on the density of connections in the skill-graphs.
weaknesses: This paper contains some weaknesses:
+ Some mathematical approximations should be carefully re-thought (please see my question below).
+ The gap between empirical excess entropy and its lower bound are too big.

Meta-review: **Summary:**
This paper proposes a heuristic, phenomenological model which is claimed to be able to reproduce several scaling phenomena observed in language models. The model is inspired by peeling decoders of low-density parity-check (LDPC) error correcting codes applied on an erasure channel, as well as percolation on random graphs.

**Strengths:**
The topic is interesting and worthy of discussion. The objective posed in this paper is ambitious. The proposed model is successful in demonstrating three phenomena regarding scaling observed in large language models.

**Weaknesses:**
- The presentation in this paper rather heavily relies on other books and papers, so that the reader may face difficulty in understanding the arguments.
- As Reviewer 5UXU mentioned, the proposed model is phenomenological and defined only vaguely. Although it may reproduce some of the characteristics of language models, we remain unassured whether the model be valid. A good theory would be able to predict what will happen *quantitatively* and/or to produce a hypothesis which will be verifiable/falsifiable via carefully-designed experiments. It seems, however, that the proposed model in this paper would lack either of the properties that a good theory should have.
- The authors claim that the proposed model is a simple unified framework, and yet explaining several different aspects of language models. In my view the proposed model is a mere composition of peeling decoder for LDPC and percolation on random graphs, where the peeling decoder part would account for the scaling rule, whereas the percolation part would reproduce emergence and plateauing as a consequence of percolation phase transition. These two parts are somehow independent of each other, in the sense that the percolation part would function rather independently of what would take place in the peeling decoder part beyond what proportion of concepts are to be learnt, so that I do not really think the proposed model a *unified* one. 

**Reasons:**
Alghouth I think that this paper poses an ambitious goal and would be successful in putting a starting point for further elaboration, my evaluation on this paper is more aligned with the reviewers with negative evaluation, mainly because of the phenomenological and heuristic nature of the proposal, which would lack the ability to make a quantitative prediction or to pose a verifiable hypothesis for those three phenomena taken up in this paper.

Additional points:
- Line 127: $d_t/T$ → $d_r/T$
- Line 323: (the ratio of the) number of (skills → concepts) learnt
- Equation (6): The closing parenthesis in the numerator of the leftmost side should be made larger. $\frac{1+\delta}{1-\delta'}$ → $\frac{1+\delta}{1+\delta'}$.
- Line 454: note that $W_0(xe^x)=x$ for ($x<-1$ → $x\ge-1$)
- Line 458: $\sigma_l=0$ → $\sigma_1=0$
- Line 468: The phase transition mentioned here should be sharp but should not be discontinuous, so that saying it as "step" may be misleading.
- Figure 4 (a)(c)(d): It seems that the authors plot not the accuracy itself but the lower bounds of the accuracy given in equations (12) and (13).
- Independence of equation (4) of $\epsilon$: It would be true that the quantity of interest here is defined independently of $\epsilon$, and thus the end result (equation (4)) *should be* independent of $\epsilon$. On the other hand, the explicit formulas do not really appear so, so that it would be appreciated if a direct proof that the derived formula actually gives an $\epsilon$-independent quantity.

Decision: Reject