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

We thank the reviewer for insightful comments. The responses to reviewer's questions/concerns are provided below.

The gap between empirical excess entropy and its lower bound are too big.

We thank the reviewer for the observation. Indeed, this could suggest that either there is a significant scope for exploring better neural architectures, or the bound is loose, the investigation of which is left for future work. Please note that the excess entropy scaling is not the main message of the paper. A main contribution of our paper is obtaining the Chinchilla size scaling rule described in the previous subsection, i.e., Section 3.1.

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 take arbitrary value as mentioned in the proof in Appendix A.2?

We thank the reviewer for the question about technical detail. As the reviewer rightly pointed out, the right side of (4) should be invariant to $\epsilon$. This is true, but it is not very apparent. The argument is the following (which is provided in Appendix A.2): Consider an instance of bipartite graph $\tilde{G}_1$. At every peeling/decoding iteration, the final set of unlearned concepts (undetermined codeword bits after decoding) depends only on the residual graph (containing only the concepts yet to be learnt and adjacent text pieces) of that particular iteration. In the first peeling/decoding iteration, the residual graph is $G_1$. The choice of $\epsilon$ only affects the number of dummy variable nodes and associated edges; equivalently it only affects the constructed parent graph $\tilde{G}_1$, but not $G_1$ which is the original graph. Therefore, the probability that a concept is not learned after the peeling process (or equivalently, probability that a codeword bit is still erased after decoding conditioned on codeword bits erased before decoding) does not depend on the choice of $\epsilon$.

Note that the quantities $\epsilon^*$, $\alpha$, $\nu^*$ vary with the value of $\epsilon$ such that $\epsilon^{-1} P_{b, \lambda_T, \tilde{\rho}_R}$ is unchanged for a fixed $(R, T)$.

On a related note, a rigorous treatment of the evolution of degree distributions of residual graphs and iterative decoding as a Markov process is discussed in Amraoui et al.\ (2004) (https://arxiv.org/abs/cs/0406050).

We thank the reviewer for providing insightful feedback. We provide responses to reviewer's questions/concerns below and we have updated our manuscript accordingly.

Note: Due to character limit, we split our response into two cells.

did other work ... hierarchical skills?

One notion of hierarchical skills is considered in Liao et al (2024) in the context of fine-tuning a model. They consider two levels of skills - basic skills and domain-specific skills. To learn domain specific skills a language model needs domain-specific texts and basic skills. On the other hand, we do not consider fine-tuning. Instead, we modify/augment this graphical model with a hierarchy of skills inspired by cognitive architectures in Laird et al., 1987; Anderson 1993; Kieras and Meyer, 1997 (we discuss this between L059 to L066 in the introduction section of our paper), and skills are acquired from concepts and not directly from texts. To the best of our knowledge we are not aware of works discussing a graph-based model of hierarchy of skills and acquiring skills from concepts in the same form as in our paper.

Did previous works ... message-passing ... different tools?

Yes. Thinking of language model training as a peeling process (message-passing) is borrowed from Liao et al. 2024. In Liao et al. 2024, emergence is explained through asymptotic analysis (however, their notion of emergence is different from ours as summarized in Section 2.5 of our paper). We start from the same message-passing dynamics, but our contribution is finitary analysis; we first prove the optimality of the Chinchilla scaling rule, and then explain emergence.

How significant ... automatic selection of scaling law ...?

In previous works, the scaling law must be assumed a priori to explain emergence of skills. However, from our finite blocklength analysis, we prove the optimality of the Chinchilla compute-optimal size scaling. The goal is to first provide a mathematical explanation to the scaling law and then explain emergence of skills.

What ... rationale ... $N$ ... is proportional to $R$ (No. of skills)?

We borrow the notion of skill-quanta from Michaud et al. (2023), and so the number of concepts (R) a language model can learn is proportional to the model size (number of model parameters). The model size determines its capacity in terms of the number of concepts learnt. The paragraph ``parameter scaling" in Section 2 of Michaud et al. (2023) describes the relationship between skill quanta and number of model parameters.

What ... rationale ... $N T < C$ ... language models?

The tradeoff between number of parameters of language models and dataset size due to compute budget is empirically studied in papers such as Hoffmann et al. 2022, Kaplan et al., 2020, etc. The rationale is: for a fixed compute budget, one can either train a large model with small dataset size or a small model with a large dataset size. For a language model with a large number of parameters, large number of FLOPs are required for each gradient update. Studying the trends for smaller compute budgets provides a thumb rule to determine (model size, dataset size) pair for larger compute budgets.

Also, ... whether ‘size’ means ... data.

We have now indicated that model size means the number of model parameters in the introduction - ``so the number ... model size (number of model parameters)."

The connection to language models ... learning and education in general.

Agree. The framework is not restricted to transformer-based language models and may characterize other learning paradigms. In the introduction we highlight this generality: ``Moreover, although ... tied to Transformer-based language modeling architectures (Yu et al., 2023a), it can describe ... different learning paradigms (Yu et al., 2023b)." Note that the paper "Information Lattice Learning" by (Yu et al., 2023b), is itself a human-like learning approach, where lattice construction using universal priors resembling human innate cognition --- the Core Knowledge priors (Spelke and Kinzler, 2007), and learning within the lattice to find optimal rules that best explain the signal.

Also related: ... poor choice of words ...

We have modified the sentences in section 2.1 - ''A set of tokens ... a language model can learn a set of concepts ... Note that we consider ... Hoffmann et al. (2022)." We have modified the sentence in L245 to ``The goal ... under the compute budget constraint $C$".

The authors say ... non-asymptotic information theory are misleading.

Please note that we think of modern coding theory as a branch of information theory, rather than narrowly defining information theory as only Shannon theory. Indeed, Shannon theory is only one topic among many (including modern coding theory) that appear in venues such as the IEEE Transactions on Information Theory. In particular, all the main papers on LDPC codes and their analysis appear in the IEEE Transactions on Information Theory.

(continued)

Thank you for your response.

I have no further questions or comments.

I have increased my initial rating from 3 to 5 because the authors have partially addressed my concerns.

We thank the reviewer for feedback and we aim to provide clarity here. Please note that experimental validation for our basic theoretical model is, as detailed below, directly provided by prior work that we cite.\

We follow the definition of a text piece from Arora and Goyal, 2023 (https://arxiv.org/abs/2307.15936). The text piece is a set of tokens, for example, a fixed number of sentences or a fixed number of tokens.

We consider a concept to be an abstract quantity that a model learns. In transformer-based language models, concepts could be interpreted as clusters in self-attention dynamics according to Geshkovski et al.\ (https://neurips.cc/virtual/2023/poster/71198). On the other hand, in a more human-interpretable information lattice learning (Yu et al., 2023b), concepts could be interpreted as abstract hierarchical rules extracted from the data.

Skills can be enumerable human-interpretable notions according to Yu et al., 2023a (https://iclr.cc/virtual/2024/poster/18931). Some of the skills listed in the paper are: self serving bias, accident, complex question, red herring, metaphor, spatial reasoning, and modus ponens.

The paper "SKILL-MIX: A flexible and expandable family of evaluations for AI models" by Yu et al., 2023a (https://iclr.cc/virtual/2024/poster/18931) provides strong experimental results on the validity of text-pieces and skills. In that paper, a text piece is made up of 3 sentences, and they consider a set of 101 skills (some of which are listed above). However, the authors suggest that the number and definition of skills can be updated: "... adding new skills to our list, or by switching to more difficult or specialized skills, or to topics that are rarer or more specialized."

Designing experiments to test our framework is indeed feasible. For instance, taking inspiration from cognitive studies (Bloom's Taxonomy or cognitive hierarchy theory) one can enumerate and construct a hierarchy of skills. Then define tasks (for example, text generation, cloze questions, etc) involving a specific subset of skills from multiple skill levels. Next, use the SKILL-MIX framework to evaluate a language model's performance (for example quality of generated text, accuracy, etc) on the task. One can evaluate the performance for increasing compute budgets. To evaluate the learning of concepts, one could investigate how clustering behavior in self-attention dynamics evolves with scaling.

Since the mathematical underpinnings of empirical phenomena are not studied extensively, what we are doing is explaining several empirical observations using theoretical properties of experimentally-verified mathematical models.

We are glad the reviewer finds our theory to be very interesting! We thank the reviewer for insightful comments. The responses to reviewer's questions/concerns are provided below and we have updated our manuscript according to the comments.

I think one assumption... Can we always assume that the peeling process have already stopped after the training?

We thank the reviewer for the question. However, the physical meaning of continuing the peeling process after training is not very clear. We request the reviewer to clarify this question further.

Not necessary in this paper, but ... more numerical experiments ... peeling process indeed happens in training.

We thank the reviewer for the suggestion. We would like to highlight that the model training as a peeling process is borrowed from Liao et al.\ (https://arxiv.org/abs/2404.07009); our contribution is finitary analysis to prove the optimality of the Chinchilla size scaling rule (and also explaining true emergence and plateauing). Moreover, please note that one need not think that peeling directly models the LLM training processs; instead this is an abstraction operating at a semantic level similar to the textpiece-skill approach of Arora and Goyal 2023 (https://arxiv.org/abs/2307.15936) that is also an abstraction at the semantic level. We agree that numerical experiments on how LLMs learn during training could be an interesting separate line of work.

The paper assumes ... Do the theory in the paper also hold for other degree distributions.

The theory holds for other degree distributions too. However, computing the post decoding bit erasure rate $P_{b, \lambda_T, \tilde{\rho}_R}$ for general degree distributions is not straightforward (with reference to Appendix A.2). In particular, it is challenging to find the degree distribution $\tilde{\rho}_T$ of the parent graph $\tilde{G}_1$ such that the check nodes (text pieces) of the residual graph has the degree distribution $\rho_T$. Considering general degree distributions could be one of the potential future extensions. In fact optimizing degree distributions would describe the best kinds of training datasets or model architectures.

Some minor issues, in appendix C, ... when $p_b$ is also small.

Equation 30 is exactly equal to the Equation 29, which is obtained upon simplification. There were a couple of typos in Equation 29 and 30, which we have now corrected, apologies. As rightly pointed out by the reviewer, we can use the approximation only when $P_b$ is small. In our case, it turns out that $P_b$ is indeed very small, in particular $P_b \ll 1/d_t$. In the figures we have used $d_t = 6$ and . However, please note that in Figure~3(b) we plot the exact expression in Equation 30 (not the approximate expression in Equation 7 or 8).

In line 759, Chernoff's bounds have multiple forms. One reference should be given here.

We thank the reviewer for pointing out. We have added ``In deriving the above lower bounds, the following versions of Chernoff's bounds are used: ... Binomial(n,p)."