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

Authors: Anuj K. Nayak, Lav R. Varshney
Primary area: other topics in machine learning (i.e., none of the above)
Keywords: Language models, scaling law, emergence, plateauing, Low-Density Parity Check codes, sequential concept learning, composition of skills.

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.

Decision: reject
Reviewer scores: 8, 3, 5, 6

Reviews and discussion:
<thread>
creation date:
1729525661216

thread_type:
official_review

<thread_object>
creator: reviewer_ket7

<content>
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.

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.

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.

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?
</content>
</thread_object>

</thread>
<thread>
creation date:
1729588639309

thread_type:
official_review

<thread_object>
creator: reviewer_tzyr

<content>
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.

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.’’

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.

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.
</content>
</thread_object>

</thread>
<thread>
creation date:
1729990787564

thread_type:
official_review

<thread_object>
creator: reviewer_5uxu

<content>
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.

strengths:
The goal of the paper is ambitious. A unifying theory that can help explain the scaling behavior will be quite nice.

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.

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?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730321316528

thread_type:
official_review

<thread_object>
creator: reviewer_x1em

<content>
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.

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.

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.

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.
</content>
</thread_object>

</thread>


Metareview:
metareview:
**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.