Understanding LLM Behaviors via Compression: Data Generation, Knowledge Acquisition and Scaling Laws
Authors: Zhixuan Pan
Shaowen Wang
Liao Pengfei
Jian Li
Venue: NeurIPS 2025 spotlight ()
Keywords: Large Language Model
Scaling Law
Information Theory
Primary area: theory

Abstract: Large Language Models (LLMs) have demonstrated remarkable capabilities across numerous tasks, yet principled explanations for their underlying mechanisms and several phenomena, such as scaling laws, hallucinations, and related behaviors, remain elusive. In this work, we revisit the classical relationship between compression and prediction, grounded in Kolmogorov complexity and Shannon information theory, to provide deeper insights into LLM behaviors. By leveraging the Kolmogorov Structure Function and interpreting LLM compression as a two-part coding process, we offer a detailed view of how LLMs acquire and store information across increasing model and data scales -- from pervasive syntactic patterns to progressively rarer knowledge elements. Motivated by this theoretical perspective and natural assumptions inspired by Heap’s and Zipf’s laws, we introduce a simplified yet representative hierarchical data-generation framework called the Syntax-Knowledge model. Under the Bayesian setting, we show that prediction and compression within this model naturally lead to diverse learning and scaling behaviors of LLMs. In particular, our theoretical analysis offers intuitive and principled explanations for both data and model scaling laws, the dynamics of knowledge acquisition during training and fine-tuning, factual knowledge hallucinations in LLMs. The experimental results validate our theoretical predictions.

Understanding LLM Behaviors via Compression: Data
Generation, Knowledge Acquisition and Scaling Laws
Zhixuan Pan Shaowen Wang! Pengfei Liao" Jian Li
Institute for Interdisciplinary Information Sciences, Tsinghua University Schooo of Computer Science and Engineering, Beihang University panzx246mails tsinghua edu. en, wangsw23dmails, tsinghua. edu. 1iaopf228buaa. edu, cn, lapordge@gmail... com
Abstract
Large Language Models (LLMs) have demonstrated remarkable capabilities across numerous tasks, yet principled explanations for their underlying mechanisms and several phenomena, such scaling laws, hallucinations, and related behaviors, remain elusive. this work, we revisit the classical relationship between compres- sion and prediction, grounded in Kolmogorov complexity and Shannon information theory, to provide deeper insights into LLM behaviors. By leveraging the Kol- mogorov Structure Function and interpreting LLM compression coding process, we offer a detailed view of how LLMs acquire and store informa- tion across increasing model and data scales from pervasive syntactic patterns to progressively rarer knowledge elements. Motivated by this theoretical perspec- tive and natural assumptions inspired by Heap's and Zipf's laws, introduce a simplified yet representative hierarchical data-generation framework called the model. Under the Bayesian setting, show that prediction and compression within this model naturally lead to diverse learning and scaling behaviors of LLMs. In particular, our theoretical analysis offers intuitive and princi- pled explanations for both data and model scaling laws, the dynamics of knowledge acquisition during training and fine-tuning, factual knowledge hallucinations LLMs. The experimental results validate our theoretical predictions.
two-part
Syntax-Knowlld
Introduction
Large Language Models (LLMs) have emerged one of the most influential breakthroughs in modern artificial intelligence, achieving impressive performance across multitude of tasks, ranging from fluent text generation, translations, and summarization to answering factual queries, and even performing complex reasoning. Despite these remarkable achievements, theoretical understanding of what enables LLMs to generalize so effectively remains limited. Traditional learning theory frameworks have not yet fully explained why certain scaling laws hold, why in-context learning emerges, or when and why hallucinations arise in the output of these models.
One promising lens for gaining deeper insight into LLM behavior the intrinsic connection between prediction and compression. Kolmogorov complexity and Shannon information theory have long es- tablished that optimal prediction of data sequence is intimately tied the most efficient compression of that sequence (see e.g., [13] 44 55 34).. From this perspective. predictive model, particularly a large language model (L..M), can be viewed as practical approximation of the Kolmogorov compressor (see e.g., 69
16
48
of training data. See Appendix C Appendix B for more details.
Equull contribution.
Corresponding author.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Following this line of thought, we build upon the Kolmogorov structure function A47 61 and interpret LLM training as constructing a two-part ddata-to-moded code for the training data. The first part (the model compressor part) corresponds to the L.M itself, which adjusts its parameters to learn patterns and structural regularities for more efficient compression. The second part (the data part) is the compressed code of the data, generated by using the L.M as the compressor. | As already indicated by prior work on the structure function (see e.g. [71 61 46)), a model of low complexity captures only the most prominent regularities in the data, whereas allowing model of higher complexity captures more nuanced structures. In the context of compressing language corpus under capacity constraints, the most efficient LLM-based compressor should initially focuses on compressing frequently recurring regularities such as syntactic pattern,, then integrates relatively common knowledge, and eventually handles increasingly rare knowledge elements. Any "residual" (such as factual knowledge exceeding the model's 's capacity or unpredictable noise) must be left out of the model and explicitly encoded in the second part. See Appendix C for formal definition of Kolmogorov structure function and Figure Ja) for a schematic illustration.
Motivated by the insight from the study of Kolmogorov Structure Function and natural assumptions inspired by Heap's 's law (30) and Zipf"s 's law [76 (see Appendix [A] for more details), we propose the Tyntax-Knowleds
model, (simplified) hierarchical data- gelta-enerratie framework that decomposes the generation process into two components (see Figure ())).. The first component, a parametric Syntax Model, captures the syntactic structures of language, allowing for random syntactic variations. The second component, a Knowledge Model, encodes relevant world knowledge and is modeled using the nonparametric Pitman-Yon Yor Chinese Restaurant Process. This choice reflects the growing nature of human knowledge and captures the fact that certain pieces of information occur disproportionntely more frequently than others in the data. By examining how efficiently data generated by this model can be compressed (specifically, by minimizing perplexity, or equivalently coding redundancy), we clarify the learning behaviors of LLMs: highlighting that syntax model is learned first faster rate, and the (factual) knowledge elements are acquired according to the order of their frequency. Furthermore, we theoretically demonstrate how model performance scales with both data size and model capacity, thus providing intuitive explanations for the scaling laws observed in real-world LLM training. Our contributions are summarized as follows:
1. Kolmogorov Structure Function Perspective. By viewing LLM training as a two-part coding process the Kolmogorov Structure Function, we present a principled framework for viewing LLMs as compressors that distinguish between structural regularities of varying frequencies and residual randomness. See Appendix C
2. A Non-Parametric Hierarchical Data Generation Model. In Section 3
we introduce the Syntax-Knowledge model, a hierarchical generative framework that separates language syntax (captured by parametric model) from (factual) knowledge (represented by non- parametric Pitman-Xe Yor Chinese Restaurant Process). This design naturally accommodates the growing nature and power-law distributions of knowledge elements, motivated by Heap's 's law (30 and Zipf's s laws 777, reflecting their disproportionate frequency in real-world data.
3. Data Scaling Law. Within a Bayesian framework, we show that perplexity minimization applied to data generated by our laws observed in real world L.L.ss. In particular, the Bayesian redundancy is equal to the mutual information between the prior and the data, and we can bound the mutual information by Ô (Crmm/N' + Csya/N,, where N is the size of the training data, Cknw and Csyn are constants depending on the knowledge model and syntax model respectively, and a is the discount parameter of the Pitman-Yo Yor Chinese Restaurant Process employed in our knowledge model. See Section
model naturally leads to data scaling
4. Model Scaling Law. In Section we extend our theoretical models to account for model scaling laws, under a slightly different set of assumptions. As a consequence, we offer more fine-grained understanding of model scaling by decomposing the test loss according to the frequency of knowledge elements. This allows to accurately predict which knowledge elements LLMs can acquire under capacity constraints during training, and which ones they are more likely to hallucinate(even though the model may have encountered them many
3 For details on using an LLM or any auto-regressive predictor to compress data via Arithmetic coding, see 62 3 [6] or Appendix B.I

---

compotiants
LOSS nomponnants
202
0..9%
32%
79-1009%
75 100%
150
Vartatin 0000
Rredeoted Whiietee
6.8
125
1.00
64
022
52
023
0.0
6.8
8.5
56
5.9
6.3
6.6
1.
73
Midell Ra mameeees scnle)
Model Parameters Beg 1D soale)
Figure 1: Decomposition of validation loss knowledge tokens by frequency class, model size increases. (a) Empirical results on power- lower-law-distributed dataset: knowledge tokens are grouped into four frequency classes (from most least frequent) and colored accordingly. We observe the following trend: smaller models capture only the most frequent knowledge (the loss of the most frequent class decreases the first), while larger models gradually acquire less frequent knowledge. Each vertical dashed line marks the model size beyond which further loss reduction for given frequency class becomes negligible, indicating the irreducible part of the loss. (b) Theoretical prediction of the same loss decomposition (the optimal solution of the constrained optimization
problem (5) Section 4.3) with irreducible loss part (i.e., the (Pa) term (3), which reproduces this trequency-dependee acquisition order and plateauing behavior.
times) as demonstrated Figure 2 See Figure
T for both our theoretical prediction and the corresponding experimental results model scaling behaviors,
2 Background
In this section, review the necessary background information theory, coding, perplexity
minimization, and scaling laws in LLMs. Let V denote the set all possible tokens. We denote
(8) (t) (2)
the training corpus X1:N = X2, XN. where each X, ri x2 Lt, sentence
represented sequence of tokens, with each token x2) V.
Perplexity Minimization in LLMs. In LLMs, the cross-entropy loss (or log-loss) serves as the metric for measuring how well the model predicts a given sequence of tokens. A model M, which induces a predictive distribution PM, estimates the conditional probability of each token given the preceding context #1;-1 for each sentence. We assume that all sentences in the training corpus X are independently drawn from the source distribution P Poum- Given the training corpus XI:NS the training objective to minimize the empirical averaged cross-entropy loss:
1 N
1
C(M)
log PM (XiN))
log PM (X,) -E ExmP, log (X))
N
N
= -H(P = N
Σ
log PM (a (0)
(1)
where Pe is the empirical measure of the underlying source distribution Poun and (PI)Q)
Ex-p!-log Q(X) is the standard cross-entropy loss. The perplexity (PPL) is then defined as PPL == (xp) capturing the effective "number of choices" the model has at each token.
'We follow the experimental setting of 3 but use power law distribution of individuals. The experimental details can be found in Appendix
3

---

10
10-
0.9
0.8
0.7
Accuracy
0.6
0.5
Model Peremeters
0.4
0.3
123.6M
57.3M
0.2
1.0%
20.5M
50-75%
13.9M
25 25-52%
0.0
68-
0-23%
227
1139 2534 5726
3440
7.0M
11.201
20.301
20.441
57.20
325.0H
227.2M
Fresuue ny In Predraining
Model (Faramesers)
Figure (a) Aceuracy of sufficiently trained models with different sizes across varying input frequencies. When the frequency falls below model-specific threshold, small models inevitably hallucinate and fail learn the corresponding facts. (b) Accuracy different frequency classes (split into four quantiles) under varying model sizes. As model size increases, the model progressively learns the more frequent data first, while infrequent data becomes learnable only at larger scales.
Lossless Compression and Redundancy. The goal of lossless compression is to encode sequence of tokens X Fl:n (sampled from the source distribution Pa parametrized by () into binary sequence f1:m of minimal expected length, such that Di: can be recovered perfectly from ylam- We binary source code e: 3/- {0, 1}", which encodes each possible sequence 21:m into binary codeword c( of length ((c(11:)) bits. The objective is to minimize the expected code length
L(Q₂)= = EX~Ps [(((())) = 1 Qx(X)) (l
(2)
where Qo(x) 2 (-(((())) is the predictive probability corresponding to the code According to Shannon's 's source coding theorem [64), the average length of any lossless code is bounded below by the entropy (PPa), and one can design encoding scheme whose code length is ((Ps) + O(1)
Po is known. However, when the source distribution Pa is unknown, universal coding becomes necessary (see Appendix B.2 for more details). In this setting, the extra code length beyond (Pa). referred to as the redundancy of the code c, is defined as follows:
Red(Qe, Pa) = L(Q,)= - H(Pa) = H(P |l Q.) H(Ps) = DKL Qc).
(3)
where DKL(Ps (c.)) = Ex~PP [=g(P((=)/Qo(z)) is the Kullback-Lece Leibler (KL) divergence be- tween source distribution Po and predicted distribution Qc. Comparing equations ① and 2 reveals that obtaining a predictive model that minimizes perplexity (or cross-entropy loss) is essentially equivalent to finding code with minimal expected length. (See Appendix [or further details the equivalence between prediction and compression.) Moreover, one can see from (3) that (P))) constitutes the irreducible part of the loss, corresponding the minimum achievable code length under Shannon's 's source coding theorem. Therefore, the goal minimizing the expected code length essentially equivalent to minimizing the redundancy.
The performance of LLMs, particularly the cross-entropy loss L. has been observed to improve predictably with increases in model size, dataset size, and computational resources 42 [3 These empirical relationships are known scaling laws. A common formulation for the loss as a function of dataset size D (e.g., number of tokens) and model size M (e.g.. number of parameters) C(D, M) (D/Do) -a (M/M0) -3 +c. In these formulations, Do and Mo represent characteristic scales for the dataset and model size respectively. The exponents a > 0 and 3 > 0 determine how quickly the loss decreases the dataset size and model size increase. The term represents the irreducible loss, which is the minimum achievable loss that cannot be reduced by further scaling, potentially due to factors like the inherent entropy of the data.
Scaling Laws in LLMs.
3 Hierarchical Data Generation Model
In this section, we propose a hierarchical data generation model, called the syntax-knowled model. In this model, where each sentence in the training corpus is generated by syntax encoder that encode

---

a (factual) knowledge element, sampled from the knowledge model. The syntax model (encoder) is parameterized by Osyn. the knowledge model is denoted as Oknws and the entire data model denoted as Adata = (Qsm: (kaw))
In our model, the syntax model Asyn (e.g., a probabilistic CFG, an English/code grammar, or even a template-basee format) does not grow with the size of the dataset and can be modeled using a finite-dimensional parameterized model @syn. On the other hand, the knowledge model employs a non-parametric stochastic process to account for two empirically observed phenomena: 1) the unbounded growth of factual information as datasets grow (mirroring Heap's ' Law in lexical growth patterns [30), and 2) the long-tail tailed frequency distribution of factual occurrences, analogous to Zipf's law in natural language [76 777.
Motivated by the above idea, we leverage the nonparametric Fitman-Yor process (PYP) [56] for modeling the knowledge model kknw- A PYP is characterized by two real parameters, the discount parameter 0 v a < and the concentration parameter /3 > -O, and a base probability measure Tkow- We denote as PYP(a, B, Tkww). A sample from the Pitman-Yor process PYP(a, B, Tkow) is a random probability measure Ōknw Zim1 I p.og., which is a discrete distribution with count- ably infinite atoms, where p- (pl, [pI,P2,-. P2,...) are the weights generated by the Pitman-Yor Chinese Restaurant Process (PYCRP) (described below); each atom o; ~ Tknw is the i-th cluster parameter independently drawn from the base measure Tknw-
The weights p = (21.P2.....) are generated by the Pitman- Yor Chinese Restaurant Process (PYCRP), denote as p (p1. .2) ~ PYCRP(a, 33). PYCRP adopts a preferential attachment mechanism that naturally captures both the sublinear scaling of new factual discoveries and the power-law distributed frequencies of knowledge pieces (see Lemma H.2 in Appendix H..Ip PYCRP works as follows: Imagining restaurant where customers arrive sequentially, each choosing either to join an existing lively table or start their own. The first customer sits a new table. Consider the n-th customer who just come to the restaurant. Suppose N₂ is the number of customers already at table k. and K is the current number of occupied tables. The n-th customer either joins an existing table k or starts a new table with the following probabilities:
The n-th customer joins an existing table k with probability (Ny- 1 a)/(n- 1 + 3), or starts a new table with probability (8 + aK) /n/n/nn- 1 + 3). The weight p- = P2..Pa.... = lim (N1/n,N,) NN/n2, ...) are defined as the relative sizes of the tables
as the number of customers n + Co. More details of PYMM can be found in Appendix D.I
Hierarchical Data Model: In the Pitman-Yor Mixture Model, the Yor Process serves as prior defined over the set of mixture distributions. Recall that a sample from the Pitman- Yor Process a random probability measure of the form 6kow Σ i= p, where {p:} are the mixture weights and {Ør} are the atoms. This can be viewed as mixture distribution which the i-th cluster is chosen with probability Pt, and the corresponding model is parameterized by o. referred to as the i-th knowledge cluster (table).
The parameters 6; are drawn from a base measure Tknw, which acts as a prior over the cluster parameters. We assume kaw supported on a bounded parameter space 4F = (sb E Rddw ||0b < 1}, ensuring that each 6; E & for all i E N+
Now, it is ready to describe the Syntax-Knowledge model, which generates sentence X according to the following hierarchical framework:
1. We first independently sample the latent parameters of the knowledge and syntax models: Dxnw PYP(a, B, kkww), Psyn = [ (()
..., olyy) ).
( iid Aayn ~ ( where
Tyn is the prior distribution of @ and supported on a bounded parameter space P.yn = {o Ridg ||인1| < 1}. ensuring that each dkyn E syn for all sis < nl.. The value n, denotes the number of distinct syntax parameter vectors, indicating that different types of knowledge should be expressed through different syntactic patterns.
(6)
2. We generate the sentence from both Osyn and 6kaw In fact, we first sample an (abstract) knowledge clement k (corresponding to a customer) from a knowledge cluster (correspond-
(6) ing to table) in 6kow. use K to determine which syntax Φlyn (e.g.. which template or format) to use, and then use the syntax encoder to generate the corresponding sentence. See Appendix D for details and Figure 7 for the data model schematic.
5

---

Explaining Scaling Laws
4.1 A Bayesian Sequential Prediction Framework
In this section, we explain LLM scaling laws by adopting the Bayesian sequential prediction frame- work (also called online Bayesian coding game). This Bayesian setting has been studied extensively in information theory (especially related to universal coding), statistics and machine learning literature (see e.g.,
12 and more recent expositions 17 37). More details can be found in Appendix B.2.2
Given the data-gent matta-ennrattng distribution Pal... the redundancy of the model M (recall the definition from with respect to samples X1.N i..d. drawn from P Prssso is:
Red (M, (ddaa)
E
| -log log PM PMr(P (Xr(Xi:))
| log Porn (X
XI-N~Pean
XI:N~Poo
= DKL((1L)) dan PMr),
where the first term represents the cumulative cross-entropy of the model M, and the second term corresponds to the irreducible entropy of the ground ground-truth data distribution Odata
In Bayesian generative models, the data-generating parameter daa is treated random variable drawn from a prior distribution и. Let & dataa denote the parameter space. The Bayesian redundancy of model M is defined the expected redundancy under the prior
Red (M, & data) ==
π (Wdatt) Red (M, (danta) dohatt-
According to Lemma
B.3 in Appendix B.2.2 the optimal Bayesian redundancy is given by:
inf (T(daaa) Red (M, ) dodaa
TToddaa) DKL (PN 1[xx dd I[XI:N; @data),
where Qn = PNN ग ((daa)) dedata denotes the marginal distribution over X1:N obtained by first den
Lid.
sampling (dtata ~ and then drawing X1:N ~
Paran conditioned on diatt-
4.2 Data Scaling Law (under the Bayesian framework)
Under the Bayesian sequential prediction framework, we derive upper bound the optimal Bayesian redundancy (which is equal to the mutual information TI I[Xiis inN;; @dms) by Lemma B.3) of our hierarchical data model daaaa-
We make the following natural assumption of the knowledge model: the parameters of two knowledge clusters are close, the KL divergence between two induced distributions is small.
Assumption 4.1. The probability families 4 syn and & knnw satisfy the following: there exist positive
constants Tkow and Luyn such that for @kkw L knw and Psyn dayy 4syy: we have:
DKL (P P S Lkow (
(2) knw 11?, DKL
S Lyyall
1 (1)
12.
sym
The constants Lenw and Loyn may depend the concrete form of the parametrization of P Pera and Pogg. and are typically related to the Fisher information (See Lemma H.6 and Remark H.7 However, the particular form of the parametrization is not important for later development. The constants Laaw and Layn appear in logarithmic order in the upcoming Theorem 4.2 For the sake of clarity, we omit logarithmic terms in the statement of Theorem 4.2 Under the Bayesian setting and the above assumption, we can derive the following upper bound the optimal Bayesian redundancy.
Theorem 4.2. Under the Bayesian sequential prediction framework and Assumption 4.1 I the averaged optimal Buyesian redundancy (per sentence) of the hierarchical data model Qanio sutisfies:
inf
Red M, & daaa) = L(XENS Psooa) Ō M N
1 N
dkmw NI-a
nadleyn
N
where dinn and d'n are the parameter dimensions of the knowledge and syntax clusters, respectively. and is the number of distinct syntax clusters.

---

Veitte ove Tprinn (ln vrate)
143
0.20
120
6.17
010
Trained Tallens
0.43
0.03
Nowe-:22 -2.2
1005 (200)"-024
9-44)
0.50
0.71
Roserr: 53 (x/en"-See 61
PO
(030)"-0322 0222-022---
0.70
0.00
262.2N
521.3M
Uhfoom
130.0M
120.800
227.801
$43.200
217.30
751.491
199
1.795
19 42
09
304
422
917
1995
Theess Tainnd
Pretroising Frecuency
Figure 3: (a) Validation loss as a function of training data size. Models trained on data sampled from pretrained knowledge under various power-law distributions (i.e., p(i) (x + bjpower) show clear power-law scaling of loss with data size, while uniform sampling does not. more skewed data distribution leads to faster loss decay. (b) Loss decomposition by data frequency class: high fegh-frequency data is learned earlier, while lower- twwerffrequency data acquired later during training.
Using 3 we can obtain the following decomposition of the optimal Bayesian cross-entropy loss. Corollary 4.3. Suppose ı is the prior of Qdata- Under the same setting as Theorem 4.2 the averaged optimal Bayesian loss (per sentence) can be bounded as:
diaw
nadayyn
inf N
E
E Praass
[- PM (XIx)]] = (NT-aa
H(X ( ddna))
XI.N diswrr
N
where H(XI:N dota)
Rrri ~F [H (daaaa)] is the irreducible part of the loss.
Note that the optimal Bayesian redundancy bound in Theorem 4.2 consists of two distinct terms, responding respectively to the syntax and knowledge models. These two models exhibit significantly different learning behaviors: the redundancy for the syntax model decreases rapidly at a rate Ó(N-)), whereas the redundancy for the knowledge model decreases more slowly at a rate Ö Ö(Na-1). These differences highlight two distinct training phases: early stage dominated by syntax redundancy reduction, and a later stage dominated by knowledge redundancy reduction.
Such behavior is quite intuitive: Initially, the model primarily learns syntactic structures, since frequently recurring syntactic patterns yield substantial and immediate reductions in redundancy (and thus test tross-entropy loss). Moreover, the syntax model be captured by parametric model, its redundancy decreases rapidly the parametric learning rate Ō(N This is also consistent with standard Bayesian results for parametric models [60] [2]. As training progresses, the model gradually incorporates factual knowledge; however, knowledge elements with lower frequencies receive fewer training examples, resulting in a slower reduction in redundancy.
Finally, note that few recent studies have also derived the data scaling law from the power-law See Appendix for more discussions.
data distribution in various stylized settings 35
53
8
Experimental Validations: We validate Theorem 4.2 through experiments using datasets sampled
from pretrained knowledge following various power-law distributions as well as uniform distribution (See the experimental details in Appendix G In Figure we observe that models trained with power-law sampled data exhibit a strong power-law relationship between validation loss and data size, accurately captured by the regression form loss (z/ (z/xo))= + e. The fitted exponent increases in magnitude as the data distribution becomes more skewed, indicating faster loss decay, which is consistent with our conclusion in Theorem 4.2 In contrast, models trained with uniformly sampled data deviate significantly from this power-lay behavior. We note our theory does not cover such uniform distribution,
cannot arise from data modeling based the PYCRP.
Figure b) further decomposes validation loss by data frequency class over training steps. We find that during the initial training steps (from the topmost curve to the 2nd topmost curve), the loss reduces for data of all frequencies (although the loss reduction for higher frequency data is slightly larger). This indicates the syntax learning phase. Later, observe that high-frequency data achieves

---

more rapid loss reduction early in training, while medium- and low-frequency data improve later. This confirms frequency-dependent learning dynamic: the model first captures more common patterns and then gradually incorporates rarer knowledge as training progresses, which is consistent from the insight gained from Kolmogorov structure function (see Appendix Cp.
4.3 Model Scaling Law
In this section, we derive a power-law characterization for the model scaling law. Our theoretical results here are derived under slightly simplified assumptions (but retain essential insights). Specifi- cally, we focus exclusively on the knowledge model and omit the syntax model, motivated by our earlier findings in Theorem 4.2 where showed (and empirical observations confirm) that the syntax model is learned at a significantly faster rate.
We continue modeling the knowledge model Ōknw -' now make the following assumption on the mixing probabilities p..
===1 P: as an infinite mixture model but
Assumption 4.4. For the mixture model cknn = Σi p:dg,, the mixing probabilities p; follow power-law distribution: p; c(1/a)-1 where ((1/a) = E 1
In this section, we consider the optimal redundancy achievable by an omniscient model M under the constraint C. That is, we may construct the model Mc from the true data distribution ddma- The only constraint of 2 is that the model capacity is at most C' bits. Due to the finite capacity, the model M cannot memorize all the data nor the true distribution Powa. hence must apply lossy compression the true model. In particular, We denote by (mmm) the redundancy incurred by answering questions from knowledge cluster oi, and m, denotes the constraint of the mutual information between the model and Φ; (one may think it the memory allocated to compress o;). The minimal achievable redundancy under a given memory constraint can be characterized by distortion-rate function, and we make the following assumption of (mm,)) For the formal definition of Di (ms) and the justification of the assumption, see Appendix E.2
Assumption 4.5. We assume that the distortion rate function (R) satisfies
1. There exists c3 C4 such that for all E N R S c3, the distortion -rate function D.(R) 2 C1.
There exists Cmax, Imax such that for all E A the distortion rate function D; S Cmax
The redundancy minimization problem can be formulated as the following optimization problem:
minimize
E [x(D((m:)) = Σ (mii).
(5)
1=1
subject to I( Mt) SC m, = 10o Mc) 2 for all i e N
we further assume that di Φ_ M where 4_, (ò1...., 0i-1, dit....,,--1.. d++1,...). i..., o; is conditionally independent of the remaining cluster parameters given the model M In other words, conditional on the model M knowing & does not provide any additional information about oj for j # i. Under this natural assumption, the model capacity constraint can be simplified as: T(0;; M = 0o T( Mt) < C. See Appendix E.2 for the derivation. Let Red (C) denote the optimal value of the optimization problem in (5) representing the minimal achievable redundancy under the model capacity constraint.
where pp = (01, 02.....
Theorem 4.6. Under Assumption 4.5 and Assumption 4.4 the optimal value of the optimization
problem under the given model size constraint satisfies:
Red (C) = =((C-1/at1).
Moreover, if we further assume that (R = axbb R for some constant bmin S bb S Umax; Ominn S ag I amaxx the contribution of the k 's cluster is Pr Pt:D(mm)) = (minn(k- 1/a C-1/a)), where
m is the solution of the optimization problem (5)
Experimental Validation: In Figure D [). we show the empirical decomposition of validation loss by knowledge token frequency class as model size increases. Figure [bb) presents the corresponding
'This choice of exponent 1/a aligns with the asymptotic behavior of mixing weights in the Pitman-Ye Yor Process PaP 8, maa)) (see Lemma H.2
8

---

158
Madel Parameeers
123.6M
0.50
120
38-1H
0.000
Veleoeer coe Faeiein Dog vrale
4.40
0.35
0.9
7.2M
0.21
0.50
042
0.08
Unioorm
0.74
0.03
Rb: kXd) 0.38 0.59
Nowcre1.35
0.6
0.42
Ml: Ikenn 0.48 0:57
Power11.50
100K
303K
15H
5.5M
21.5M
02.5M
316.2M
6
12
22
-1
02
359
305
509
1131
2303
Model Size (parameters, log scale)
Pretrahinng Prequency
Figure 4: (a) Validation loss as a function of model size (excluding token embedding head). Re- gression analysis of model scaling: using the fitting form loss = (z/=a)==a + e, we find that when the data is generated from a power-law distribution, the loss decreases with model size following power-law trend. In contrast, the loss does not exhibit power-law scaling with model size when the data is generated from a uniform distribution. (b) Validation loss for different frequency classes: larger models are able better fit lower-frequency (rarer) data, while for fixed model size, more frequent data is learned more effectively.
theoretical prediction, derived from the optimal solution to the constrained optimization problem (5) The empirical results on power-law distributed data closely align with the theory: in both panels, high-ffrequenn classes exhibit loss reduction with smaller models, while low-frequency classes only begin improve as model capacity increases.
In Figure a), we present the model scaling law across different data distributions. Consistent with theoretical predictions, we observe that the more skewed the data distribution (i.e., the heavier the power-law tail), the larger the exponent in the fitted scaling law, indicating faster loss decay as model size increases. In contrast, for data generated from uniform distribution, the loss curve significantly deviates from a power law: the loss remains nearly flat until the model reaches a critical capacity threshold, after which it drops sharply, and then plateaus again. This pattern arises for the following reason: initially, none of the individual items stand out and are fully learned, resulting in a flat loss. As the model grows, it begins to capture a subset of properties for most individuals, causing rapid drop. Once all such properties have been learned, the loss flattens out again. A more detailed analysis of the learning dynamics for each property presented Appendix G.2 We also note that Allen-Zhu & Li 3 investigated factual knowledge acquisition using the bioS dataset consisting of uniformly distributed individuals, and one of their main findings that the amount of acquired knowledge (in bits) scales linearly with the model size. However, they did not examine the scaling behavior in terms of pross-entropy loss, which follows a very different scaling than power law (Figure a)).
Comparing the learning curves of uniformly distributed data with those of power-lawe -aw-issttute data (across both data scaling and model scaling) suggests that it can be advantageous have power- law-distributed data, because the model can gradually learn knowledge in the order of frequency, which is more effective than the uniform case, where one element stands out and the model lacks guidance on what to prioritize. Exploring how adjusting the frequency or mixing ratio of data can enhance (or accelerate) learning performance is an intriguing direction for future research (see 27 for recent study in this direction).
Our theorem also implies that for fixed model capacity C, if a knowledge element appears with frequency below a certain threshold, the model will choose not to learn it, despite that the model may have seen it many times during training. This aligns with our experimental findings: hallucination tends to occur when the total amount of knowledge exceeds the model's 's capacity, specifically, when figguecfrequency knowledge already saturates the model's 's capacity, fower-frequency elements ignored. As shown in Figure 2 for a 7.2M-sized model, knowledge that occurs fewer than 508 times consistently hallucinated, regardless of the number of pretraining epochs.

---

Concluding Remarks
There are several exciting directions to extend this work. First, while we focused on factual knowledge. real-world datasets encompass more diverse forms of knowledge. It would be interesting to integrate more knowledge structures, as well as compositional reasoning and inference mechanisms into theoretical model. Another interesting challenge is understanding how LLMs can approximate universal predictors (c.g.. the Solomonoff predictor, which is also based on Kolmogorov complexity) within practical computational constraints (see, e.g.. [25] 46)). Bridging these theoretical frameworks with real-world LLMs could deepen our understanding of their behaviors and pave the way for developing models that are more controllable and more reliable.
References
[1] James Aitchison. Goodness of prediction fit. Biometrika, 62(3):547-554 1975.
[2] Zeyuan Allen-Zhu. ICMI. 2024 Tutorial: Physics of Language Models, July 2024. Project page: https::/physics.. allen-zhhe com/
[3] Zeyuan Allen-Zhu and Yuanzhi Li. Physies of language models: Part 3.3, knowledge capacity scaling laws. ICLR 2025: International Conference on Learning Representations, 2024.
[4] Kevin Atteson. The asymptotic redundancy of bayes rules for markov chains. IEEE Transactions on Information Theory, 45(6)) 1999.
[5] Yasaman Bahri, Ethan Dyer, Jared Kaplan, Jaehoon Lee, and Utkarsh Sharma. Explaining neural scaling laws. Proceedings of the National Academy of Sciences, 121(27):6311887812) 2024.
[6] Andrew R Barron and Thomas M Cover. Minimum complexity density estimation. IEEE transactions on information theory, 37(4):0034-104, 1991.
[7] Kushagra Bhushan, Yatin Nandwani, Dinesh Khandelwal, Sonam Gupta, Gaurav Pandey, Dinesh Raghu, and Sachindra Joshi. Systematic knowledge injection into large language models via diverse augmentation for domain domain-specific rag. In Findings of the Association for Computational Linguistics: NAACL 2025, pp. 5922-59229999 -943,,93.440 2025.
[8] Ari Brill. Neural scaling laws rooted in the data distribution. arXiv preprint a1X1:22412.07942. 2024.
[9] Hoyeon Chang, Jinho Park, Seonghyeon Ye, Sohee Yang, Youngkyung Seo, Du-Seong Chang, and Minjoon Seo. How do large language models acquire factual knowledge during pretraining? In The eighth Annual Conference Neural Information Processing Systems, 2024.
[10] Sanyuan Chen, Yutai Hou, Yiming Cui, Wanxiang Che, Ting Liu, and Xiangzhan Yu. Recall and learn: Fine-tuning deep pretrained language models with less forgetting. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 7870-7881, 2020.
[11] Bertrand S Clarke and Andrew R Barron. Informmation-theoreticc asymptotics of bayes methods. IEEE Transactions on Information Theory, 36(3):453-471 1990.
[12] Bertrand S Clarke and Andrew R Barron. Jeffreys' prior is asymptotically least favorable under entropy risk. Journal of Statistical planning and Inference, 41(1):37-60, 1994.
[13] Thomas Cover and Joy Thomas. Elements of information theory. John Wiley & Sons, 2006.
[14] Majid Daliri, Zhao Song, and Chiwun Yang. Unlocking the theory behind scaling 1-bit neural networks. arXiv preprint arXiv:241 2024.
[15] Davisson, R McEliece, M Pursley, and Mark Wallace. Efficient universal noiseless source codes. IEEE Transactions Information Theory, 27(3):269-21) 1981.
10

---

[16] Gregoire Deletang, Anian Ruoss, Paul-Ambroise Duquenne, Elliot Catt, Tim Genewein, Christo- pher Mattern, Jordi Grau-Moya, Li Kevin Wenliang, Matthew Aitchison, Laurent Orseau, et al. Language modeling is compression. In The Twelfth International Conference on Learning Representations, 2023.
[17] John Duchi. Statistics and information theory. Book Drafi, 2024.
[18] Chris Dyer, Adhiguna Kuncoro, Miguel Ballesteros, and Noah A. Smith. Recurrent neural network grammars. Kevin Knight, Ani Nenkova, and Owen Rambow (eds.), Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 199-209, San Diego, California, June 2016. Association for Computational Linguistics.
[19] Meir Feder and Neri Merhav. Hicrarchical universal coding, IEEE Transactions on Information Theory, 42(5): 1354-1164, 1996.
[20] Péter Gács, John T Tromp, and Paul MB Vitányi. Algorithmic statisties. IEEE Transactions Information Theory, 2446:2444-24 2001.
[21] Robert G Gallager. Source coding with side information and universal coding. Laboratory for Information Decision Systems, MIT, Cambridge, MA, 1979.
[22] Sharon Goldwater, Thomas L Griffiths, and Mark Johnson. Producing power-law distributions and damping word frequencies with two-stage language models. Journal of Machine Learning Research, 12(7), 2011.
[23] Zixuan Gong, Jiaye Teng, and Yong Liu. Disentangling feature structure: A mathematically provable two-stage training dynamics transformers. arXiv preprint wxXiv2250.20068/ 2025.
[24] Aaron Grattafiori, Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Alex Vaughan, et al. The llama
3 herd of models. arXiv preprint arXiv:2407.21783. 2024.
[25] Jordi Grau-Moya, Tim Genewein, Marcus Hutter, Laurent Orseau, Gregoire Deletang, Elliot Catt, Anian Ruoss, Li Kevin Wenliang, Christopher Mattern, Matthew Aitchison, et al. Learning universal predictors. In Forty-first International Conference on Machine Learning, 2024.
[26] Peter Grünwald and Paul MB Vitányi. Kolmogorov complexity and information theory. Journal of Logic, Language and Information, 12:497-529, 2003.
[27] Xinran Gu, Kaifeng Lyu. Jiazheng Li, and Jingzhao Zhang. Data mixing can induce phase transitions in knowledge acquisition. arXiv preprint arXiv:2505. 18091, 2025.
[28] Kshitij Gupta, Benjamin Thérien, Adam Ibrahim, Mats Leon Richter, Quentin Gregory Anthony, Eugene Belilovsky, Irina Rish, and Timothée Lesort. Continual pre-training of large language models: How to re-warm your model? In Workshop Efficient Systems for Foundation Models@ 1CML,2023, 2023.
[29] Alex Havrilla and Wenjing Liao. Understanding scaling laws with statistical and approximation theory for transformer neural networks on intrinsically low-dimensional data. Proceedings of the 38th International Conference Neural Information Processing Systems, pp. 42162-42210 2024.
[30] H.S. Heaps. Information retrieval: Computational and theoretical aspects, 1978.
[31] Tom Henighan, Jared Kaplan, Mor Katz, Mark Chen, Christopher Hesse, Jacob Jackson, Heewoo Jun, Tom B Brown, Prafulla Dhariwal, Scott Gray, et al. Scaling laws for autoregressive generative modeling. arXiv preprint arXiv:2010. 10000.444700 14701, 2020.
[32] Jan Hoffbauer, Sylwester Sawicki, Marc Ulrich, Tolga Buz, Konstantin Dobler, Moritz Schnei- der, and Gerard De Melo. Knowledge acquisition through continued pretraining is difficult: A case study on raaskhistorians. Proceedings of the 1st Workshop on Towards Knowledgeable Language Models (KnowLLM 2024), pp. 96- 06-108. 2024.

---

[33] Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas. Lisa Anne Hendricks, Johannes Welbi, Aidan Clark, al. Training compute-optimal large language models. In Proceedings of the 36th International Conference on Neural Information Processing Systems, pp. 30016-30030, 2022.
[34] Marcus Hutter. Universal artificial intelligence: Sequential decisions based on algorithmic probability. Springer Science & Business Media, 2005.
[35] Mareus Hutter. Learning curve theory. arXiv preprint arXiv:2 2021.
[36] Adam Ibrahim, Benjamin Thérien, Kshitij Gupta, Mats Leon Richter, Quentin Gregory An- thony, Eugene Belilovsky, Timothée Lesort, and Irina Rish. Simple and scalable strategies to continually pre-train large language models. Transactions on Machine Learning Research, 2024.
[37] Hong Jun Jeon and Benjamin Van Roy. Information -eheoreticc foundations for neural scaling laws. NeurlPS 2024 Workshop on Mathematics of Modern Machine Learning. 2024.
[38] Hong Jun Jeon, Jason D Lee, Qi Lei, and Benjamin Van Roy. An information-theeorticc analysis of in-context learning. In Forty-first International Conference on Machine Learning, 2024.
[39] Keller Jordan, Jeremy Bernstein, Brendan Rappazzo, @fembeearbsky.sociil,, Boza Vlado, You Jiacheng, Franz Cesista, Braden Koszarsky, and @ @Grad62304977. modded-nanoge Speedrumning the nanogpt baseline, 2024. URL https://githut. com/KellerJordan modded-nanogpi
[40] Adam Tauman Kalai and Santosh S Vempala. Calibrated language models must hallucinate. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pp. 160-171, 2024.
[41] Katie Kang, Eric Wallace, Claire Tomlin, Aviral Kumar, and Sergey Levine. Unfamiliar finetuning examples control how language models hallucinate. In Proceedings of the 2025 Conference of the Nations of the Americas Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume I: Long Papers), pp. 3600-3612, 2025.
[42] Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprint ar arXiv:2001.0833 003361, 2020.
[43] loannis Konstas, Srinivasan Iyer, Mark Yatskar, Yejin Choi, and Luke Zettlemoyer. Neural amr: -equence-to-sequence models for parsing and generation. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp.
146-157, 2017.
[44] Matt Kusner, Brooks Paige, and José Miguel Hernández-Lobato. Grammar variational autoencoder. In International conference on machine learning, pp. 1945-1954. PMLR, 2017.
[45] Faisal Ladhak, Esin Durmus, Mirac Suzgun, Tianyi Zhang, Dan Jurafsky, Kathleen McKeown, and Tatsunori B Hashimoto. When do pre-training biases propagate to downstream tasks? case study in text summarization. In Proceedings of the /7th Conference of the European Chapter of the Association for Computational Linguistics, pp. 3206-3219, 2023.
[46] Yoonho Lee, Chelsea Finn, and Stefano Ermon. Relaxing the kolmogorov structure function for realistic computational constraints. In NeurIPS 2022 Workshop on Information Theoretic Principles in Cognitive Systems, 2022.
[47] Ming Li, Paul Vitányi, et al. An introduction to Kolmogorov complexity and its applications, volume 3. Springer, 2008
[48] Ziguang Li, Chao Huang, Xuliang Wang, Haibo Hu, Cole Wyeth, Dongbo Bu, Quan Yu, Wen Gao, Xingwu Liu, and Ming Li. Lossless data compression by large models. Nature Machine Intelligence, pp. 1 1-6, 2025.
[49] Xingyu Lu, Xiaonan Li, Qinyuan Cheng, Kai Ding, Xuan-Jing Huang, and Xipeng Qiu. Scaling laws for fact memorization of large language models. In Findings of the Association for Computational Linguistics: EMNLP 2024, pp. 1 11263-11282 2024.
12

---

[50] David JC MacKay. Information theory, inference and learning algorithms. Cambridge university press, 2003.
[51] Alex Mallen, Akari Asai, Victor Zhong, Rajarshi Das, Daniel Khashabi, and Hannaneh Ha- jishirzi. When not to trust language models: Investigating effectiveness of parametric and non-parametry memories. In Proceedings of the sl Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 9802-9822, 2023.
[52] Alexander Maloney, Daniel A Roberts, and James Sully. A solvable model of neural scaling laws. arXiv preprint arXiv:2210.16855 2022.
[53] Eric Michaud, Ziming Liu, Uzay Girit, and Max Tegmark. The quantization model of neural scaling. Advances in Neural Information Processing Systems, (6:28699-28772, 2023.
[54] Yixin Ou, Yunzhi Yao, Ningyu Zhang, Hui Jin, Jiacheng Sun, Shumin Deng, Zhenguo Li, and Huajun Chen. How do Ilms acquire knowledge? knowledge circuits perspective continual pre-training. arXiv preprint arXiv:2502.1 / 196, 2025.
[55] Jim Pitman. Combinatorial stochastic processes: Ecole d'eté de probabilités de saint-flour xxxi Springer Science & Business Media, 2006.
[56] Jim Pitman and Marc Yor. The two-parameter poisson-dirichlet distribution derived from stable subordinator. The Annuls of Probability, pp. 855-900, 1997.
[57] Samuel Rathmanner and Marcus Hutter. A philosophical treatise of universal induction. Entropy, 13(6):1076-1133) 2011. doi: 30.6396
[58] Jorma Rissanen. A universal data compression system. IEEE Transactions on Information Theory, 29(5):656-6644 1983.
[59] Jorma Rissanen. Universal coding, information, prediction, and estimation. IEEE Transactions on Information Theory, 30(4)622--636, 1984.
[60] Jorma Rissanen. Stochastic complexity and modeling. The annals of statistics, pp. 1080-1100, 1986.
[61] Jorma Rissanen and Ioan Tabus. Kolmogorov's structure function mdl theory and lossy data compression. Minimum, 2005.
[62] Jorma Rissanen. Generalized kraft inequality and arithmetic coding. IBM Journal of research and development, 198 2038 1976.
[63] Jonathan S Rosenfeld, Amir Rosenfeld, Yonatan Belinkov, and Nir Shavit. A constructive prediction of the generalization error across scales. In International Conference on Learning Representations, 2020.
[64] Claude E. Shannon. A mathematical theory of communication. Bell System Technical Journal, 27:379 423, 656, 1948.
[65] Utkarsh Sharma and Jared Kaplan. A neural scaling law from the dimension of the data manifold. arXiv preprint arXiv:2004.10880 10802, 2020.
[66] Herbert Simon. On class of skew distribution functions. Biometrika, 42(3/4):425 440, 1955.
[67] Ray J. Solomonoff. A formal theory inductive inference. part Information and Control, 7 (1):1-22, 1964.
[68] Ray J. Solomonoff. formal theory of inductive inference, part ii. Information and Control, 7 (2):224-254, 1964.
[69] Ilya Sutskever. An observation on generalization. Large Language Models and Transformers Workshop, Simons Institute, 2023,
13

---

[70] Yee Whye Teh. A hierarchical bayesian language model based on pitman yor processes. In Proceedings of the 21st International Conference on Computational Linguistics and 44th Anmual Meeting of the Association for Computational Linguistics, pp. 985-992, 2006.
[71] Nikolai K Vereshchagin and Paul MB Vitányi. Kolmogorov's structure functions and model selection. IEEE Transactions on Information Theory, 50(12))3265 -2900, 2004.
[72] An Yang. Baosong Yang. Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chengyuan Li, Dayiheng Liu, Fei Huang, Haoran Wei, al. Qwen2. 5 technical report. arXiv preprint 1511::2412.15155, 2024.
[73] Xinlu Zhang, Zhiyu Zoey Chen, Xi Ye, Xianjun Yang, Lichang Chen, William Yang Wang, and Linda Ruth Petzold. Unveiling the impact of coding data instruction fine-tuning on large language models reasoning. In Proceedings of the AAAI Conference on Artificial Intelligence, pp. 25949 25957,, 2025.
[74] Yuji Zhang. Jing Li, and Wenjie Li. Vibe: Topic-driven temporal adaptation for twitter classifi- cation. In 2023 Conference Empirical Methods in Natural Language Processing, EMNLP 2023, pp. 3340-3354. Association for Computational Linguistics (ACL), 2023.
[75] Yuji Zhang, Sha Li, Cheng Qian, Jiateng Liu, Pengfei Yu, Chi Han, Yi R. Fung, Kathleen McKeown, ChangXiang Zhai, Manling Li, and Heng Ji. The law of knowledge overshadowing: Towards understanding. predicting and preventing LLM hallucination. Association for Computational Linguistics: ACL 2025, pp. 23340-23358, July 2025. ISBN 979-8-89176-256-5.
Findings of the
[76] George Kingsley Zipf. The psycho-biology of language: An introduction to dynamic philology. Routledge, 2013.
[77] George Kingsley Zipf. Human behavior and the principle of least effort: An introduction to human ecology. Ravenio books, 2016.
[78] Jacob Ziv and Abraham Lempel. Compression of individual sequences via variable-rate coding.
IEEE transactions on Information Theory, 24(5):530-536, 1978.
14

---

A Discussions and Related Work
Prediction and Compression: The link between prediction and compression is fundamental in both Shannon's 's probabilistic information theory and Kolmogoroy' 's algorithmic information theory, forming the basis for efficient encoding and decoding of data [3 50, 47]. In particular, the better one can predict the distribution of next symbol, the better one can compress the data (via arithmatic The connection of Kolmogonov's ss theory to LLMs and artificial intelligence was outlined in Hutter's 's theory of universal intelligence [44] and Ilya Sutskever's s talk at Simons institute [69]. [6] advocate viewing language prediction as a compression problem and show that modern LLMs serve as powerful general- purpose compressors, outperforming traditional text compression tools such as gzip.
code) and vise versa |62
58
16 48
Heap's, Zipl"s Laws and Generative Models of Power Laws: Heap's Law [30 an empirical relationship stating that the vocabulary size grows sublinearly (x N for some between 0.4 and 0.7) with the size of a corpus .N, revealing that new words appear at a diminishing rate. Zipf"s Law 777, meanwhile, states that fr). the frequency of the rth frequent word, x y leading to a heavily skewed distribution dominated by leading terms. These complementary observations expose the disproportionate frequency of the words, especially "long tail" of rare words, and these long-tail effects are observed not only in linguistics but also in phenomena like city populations, animal populations, website traffic, etc.
One foundational theoretical model that produces power-law patterns is the classic Simon's model [66]. which posits that each new element more likely to replicate already-populas elements, thus creating tich--et-richer" effect. Bayesian nonparametric models, such as the Chinese Restaurant Process (CRP) and its generalization, the Pitman-Yor CRP (PYCRP), can also yield power-law distributions while benefiting from the property of exchangeability (the probability of any particular clustering remains unchanged by the order in which data points are observed).
Knowledge Modeling of Language: There is a body of literature that explicitly separates conceptually distinguishes syntax and knowledge models within language models. Here we only mention a few representive ones. 18 proposed a RNN-based model that learn syntactic structures (in the form of parse trees) alongside the generation of words. They did not explicitly incorporate a separate knowledge model. (3 models data as comprising disentangled two-type features, such as syntax and semanties. Then they analyze the Transformer's learning process, demonstrating that a two-stage dynamic emerges where the syntax component is learned first, which aligns with our 44 proposed Grammar Variational Autoencoder combining variational autoencoders (VAEs) with formal grammars to generate syntactically valid structured data, explicitly separates the syntactic and semantic elements. (43) proposed the neural Abstract Meaning Representation model that, in some pipelines, first generates a syntactic skeleton, then integrates semantic content from AMR.
Syntax-Knowledes
Theorem 4.2
The study of neural scaling laws began with the observation that the population loss of trained deep neural networks follows a power-law relationship with respect to dataset size and model parameters. Early work by (33 introduced a joint error function that captured these dependencies, laying the groundwork for empirical analyses. Henighan 3l) subsequently expanded scaling laws to a broader range of architectures and tasks, while Kaplan et al. (42) demonstrated their robustness at vastly larger scales, showing that the loss scales as L (N/Nmin, -a (D/ Dminn -ap where N is the number of parameters, D is the dataset size, and o.. O.D are scaling exponents. The Chinchilla study 33 later refined this framework by fitting their scaling law, and then identifying the compute-optimal frontier, showing that many prior models were undertrained, and demonstrating that scaling both parameters and data yields superior performance under fixed compute budgets. On the theoretical front, Bahri et al. [5) distinguished between mariance-limite and ioollutionlimitten regimes, identifying four distinct scaling behaviors. Sharma et [3.] then linked scaling exponents to the intrinsic dimension of data manifolds, highlighting the role of data geometry in performance. More recently, Havrilla al. [9 employed statistical and approximation theory to explain transformer scaling laws for low- now-dimeniional data, and Daliri et al. [14] established convergence guarantees for 1-bit quantized networks, extending scaling principles to extreme weight-preeision settings. Several works have also aimed to explain the origin of power-law behavior observed in scaling laws. Hutter 35 analyzed data scaling law under a stylized setting and showed that when the data distribution follows a power law, the resulting loss curve follows power-law decay, rather than the common
Scaling Laws:
15

---

1/N rate. Subsequent works [53 8 extended the setting in [55] and include aspects of model scaling, but still assumed a form for the loss on each data category, without considering the specifies of the learning algorithm. Maloney et al. 52 derived power-law form for data scaling of the loss using random matrix theory, linking it to the power-law structure the spectral properties of the data distribution. As in earlier studies, we also derive that power-law data distribution is the primary driver of the scaling law in our theoretical model. However, Our work differ in the following crucial aspects. First, we explicitly link LLMs to compression, and the scaling laws to the Kolmogorov structure function, a powerful view that can incorporate more complicated forms of language (rather than just facts). Second, enrich the -ata-gennration process with a syntax component, separating from underlying knowledge and yielding a more realistic model of language generation. Third, leveraging the coding/compression view, we rigorously quantify the redundancy for both Bayes-optimal models or any learning algorithm under mild regularity assumptions.
Bayesian Mixture Code: A common approach to constructing universal code is to employ the Bayesian mixture code. is well known that this Bayesian mixture code minimizes the Bayes risk/ redundancy [1] and the Bayes or minimax risk/redundancy can be characterized by the mutual information [(0; X), which is closely tied to channel capacity (1 (see also [17) ); the fixed- dimensional case, the worst
prior is the Jeffreys prior [12. Recently, Jeon et al. (38 derived a Bayes risk/redundancy upper bound for the family of deep transformers and
proposed Bayesian meta-learning model to explain in-context learning. [ Our data-generation
model draws inspiration from their meta-learning model but differs in two key aspects: we explicitly separate the syntax model from the knowledge model, and we model the growing and power-law nature of knowledge. Jeon and Roy (37 proposed to employ an infinitely wide neural network as a nonparametric iata-generation model to explain scaling laws, which is similar to modeling in
spirit. However, their theory predicts that the loss scales as ((L/M) and Ö(L/N), where M denotes the model size and N the data size, which does not capture the power-law scaling behavior observed in LLM practice (with exponents less than 1).
Knowledge Acquisition: Researchers have explored multiple mechanisms for external knowledge acquisition in LLMs, including pretraining on massive datasets [9]. which further reveals power- law relationship between training steps and the forgetting of memorization and generalization of factual knowledge, and shows that LLMs trained with duplicated training data are more prone to forgetting. In addition, recent studies find that continued pretraining contributes little to factual recall unless overfitting occurs [32), whereas targeted knowledge augmentation -via paraphrasing and diverse retrieval contexts-can more reliably inject domain-specific knowledge into LLMs for RAG applications 77. Mallen et al. [51] also suggests that LLMSs struggle to memorize less popular, long-tail facts even at large scales, and that retrieval augmentation can outperform much larger unassisted models while also improving efficiency. Recently, Gu al. (77 demonstrated that knowledge acquisition can exhibit phase transitions with respect to data mixing and model size. In particular, their findings indicate that data with mixing ratio below a certain threshold (depending on the model size) cannot be effectively learned, a result that is consistent in spirit with our model scaling law (see the proof of Theorem 4.6 in which there is a similar threshold). Furthermore, Ou al. [54] examined the internal representation of knowledge by introducing the concept of "knowledge circuits," " while addressing challenges related to ensuring factual accuracy and mitigating biases in scaled models. In addition, Allen-Zhu & Li 3 provide quantitative perspective by estimating the number of knowledge bits a model can store, showing that L.LMs are capable of storing up to 2 bits of factual knowledge per parameter and analyzing how architectural choices, training regimes, and data properties influence this capacity. Lu et al. (49] also discussed the relationship between fact knowledge capacity and model size and training epochs, finding they exhibit a linear and negative exponential law relationship.
Cause of Hallucination: While we focus on hallucinations arising from limited model capacity, prior work has identified a variety of causes. These include erroneous, outdated, or domain -inmainn data in the pretraining corpus (74); biased data distributions [45]; instruction fine-tuning on unfamiliar or underrepresented data 4T; and knowledge shadowing [75], J, where dominant knowledge within the model suppresses less prominent information, leading to the generation of fabricated or inaccurate
AAthhough their work did not mention universal coding explicitly, their main result can be interpreted in terms of universal coding and redundancy.
16

---

details. [40] propose distributional model (on facts) and prove that hallucinations must occur at certain rate if the model satisfies a statistical calibration condition.
Solomonoff's Universal Predictor:
We would like to mention that Solomonoff introduced a universal Bayesian mixture over all Ttring-computali predictors [67]6]] known the Solomonoff predictor, which is a major inspiration of the design of our knowledge model. is known that Solomonoff's predictor achieves universally optimal prediction and compression rates in expectation for any computable sequence-eeneration process [57]. The connection to LLMs and meta-learning is also alluded in [16] 25]. However, this predictor remains purely theoretical model and is not computable in practice. Exploring how modern LLMs might approximate the Solomonoff predictor (or constrained version of it) an intriguing direction for future research.
B
Prediction and Compression
B.1 LLMs as Compressors
For completeness, provide brief introduction arithmetic coding and explain how Large Language Models (LLMs) can serve as lossless data compressors using this method. More details be found in, e.g., 62
16 48
Suppose we have an autoregressive LLM M that predicts the next-token probability PM (Ir, -1:n-1). Arithmetic coding is popular method for lossless data compression, encoding each symbol (or token) based on its predicted probability. Specifically, arithmetic coding represents data sequence an interval within the real line between 0 and 1, sequentially refining this interval based on conditional probabilities. The process is as follows:
1. Initialization: Start with the interval [0, 1).
2. Subdivision: Divide the current interval into subintervals, each proportional to the probabil- ities assigned to symbols in the alphabet.
3. Encoding tokens: For each symbol in the input sequence, refine the current interval to the corresponding subinterval associated with that symbol.
4. Output: After processing the entire sequence, select the shortest binary number (base 2) that lies within the final interval as the encoded output.
Example B.1. Consider an alphabet with symbols A, B, and C, having probabilities 0.5, 0.3, and 0.2, respectively. The initial interval [0, 1) is divided as follows:
A: [0, 0.5), B [0.5.0.8) 0.8), C {
To encode the message " "AB", start with the interval [0, 1). First, narrow to A's range [0, 0.5). When processing the second symbol B, subdivide the interval 0.5) according to the conditional probabilities:
A [0, 0.25),
B 0..25,0.)).
C: 0..4.0.5).
Thus, the interval for "AB" is [0.25, 0.4). We select the number 0.25, whose binary representation is 0.01.
The efficiency of arithmetic coding directly relates to the predictive accuracy of the underlying L.M.M Formally, we have the following proposition (2] (see also 13 Ch. 13]).
Propasition B.2. Let PM be the probability distribution predicted by an LLM M for a data sequence Ti:n- Using arithmetic coding, the code length l(x1m)) required to encode the sequence Vian satisfies:
n
M(xIn) loog PM (f1mh) + 0(1)
Σ
log Par (2r x15-1)++ 0(1).
Consequently, viewing LLM M as compressor, the total description length of the data includes two parts: the complexity ((M) required to describe the model itself (architecture and parameters), and the data encoding length L(x), bounded in Proposition B.2
16 48 showed that modern L.LMs (such as Chinchilla 70B) can serve as powerful general-purpose compressors, significantly outperforming traditional text compression tools such as gzip and LZMA2.
17

---

B.2 Universal Coding and The Coding Game
In this appendix, we briefly introduce the concepts of universal coding and the coding game and how these concepts are connected to perplexity minimization in LLMs.
B.2.1 Universal Coding
The celebrate Shannon's source coding theorem 64
establishes fundamental limit achievable
code rates by stating that for any code, the average code length is at least H(P), where H()) =
(P)) = E - log2 P(x)] is the Shannon entropy of the source distribution P. Moreover, know the source distribution P, we can encode the source message with average code length approaching (P))
However, real-world data sources often cannot be fully characterized by single, known distribution. Designing coding schemes that adapt effectively to unknown distributions known as universal coding. Universal coding seeks single coding scheme that achieves near-optimal performance in terms of average code length over every distribution in a given family é (see e.g. [13 Ch. 13]). The
additional cost compared to the entropy H (P) is called the redundancy of the code suppose ((c(x))
is the length of the code e(x) and Qe(z) = 2- +(e(x)) is defined to be the predictive probability corresponding to code (Qe is a valid probability distribution by Kraft inequality). The redundancy
of code (or distribution Q²) is formally defined follows:
(Qc: P) = E. [((c(x))] (P)) En Pp log Qx(x)) - H(P)
H( || Q2) H()) (P
Hence, finding an efficient universal code that minimizes the redundancy is equivalent to finding predictive probability that minimizes the cross-entropy. A central goal in the study of universal coding to design efficient universal coding schemes that can achieve sublinear redundancy (Red o(n) for sequence of length n). Efficient universal coding schemes and tight redundancy bounds have been studied extensively the information theory literature for a wide variety distribution families (see,
for example, 13 59 12
78 15 19).
B.2.2 A Coding Game and the Bayesian (Mixture) Strategy
In this subsection, we introduce a coding game that has many connections to online learning, information theory and Bayesian statistics. We mostly follow the exposition in [17]
Consider the following online Bayesian coding game. Suppose Pa is distribution indexed by 0. Here the set of indices is θ and the prior distribution of is (0) defined over θ. The player's goal is model the distribution Po as well as possible using a distribution Q. The nature chooses the distribution Pe (according to the prior) and sample random variables ~ Pa sequentially. At step i, the player observes the history -1 chooses the distribution Q(x; 11 and suffers the log 11 The overall objective is to minimize the Bayesian log-loss as follow:
loss- log Qx;;
inf / e Zn Po
1
1
T())
E
log
d0 inf T())
E
log
Q(x; ( d0.
In view of Proposition B.2 the above objective can also thought as minimizing the Bayesian code length (hence the name of the game).
By Shannon's source coding theorem, we can see that the average code length cannot be smaller than
[ (0)
do = / = (P
E
log Pm (Itmm)
Here the superscript in PR indicates the distribution over a sequence of n random variables. Subtracting this lower bound, the objective becomes minimizing the Bayesian redundancy:
inf
(()) e
log
1
log
1
d0
Q
Pimn
Fim
Po
(21mm))
Pr (1mm))
/
inf
inf Q
n (0))Red("", PP), d0 A inf (Q, (7)
18

---

Bayesian Strategy: For probability family {Po)oee, common approach to constructing universal code employ the Bayesian strategy (also called Bayesian mixture code). We place some prior distribution defined over θ and consider the Bayesian mixture measure defined as
/ Po (x1:.) n (0) d0.
At time step the Bayesian strategy which uses the Bayes (posterior) estimator
(T1:k)
(xx = x T1
(21x-1)
as the next-token predictor. It is a classic result that this Bayesian mixture code minimizes the Bayesian redundancy Red, (Q
So DKL (Po Q) (0) do (.. In fact, the Bayes redundancy be characterized by the mutual information I(0; X), which is closely tied channel capacity For reader's convenience, we summarize the results as 21 12 13.. See also [17 Ch. 19] and 38
the following lemma.
Lemma B.3 (7)) The mininum Bayesian redundancy is attained by the Bayesian mixture code Qu, and is equal to the mutual information between random variable 0 (from the prior π over () and the data Zim-
inf (Q, = inf / ((B) (P [Q")) DK) = I(r1m;))) Q
Here, O ④ is sampled from the prior n, and 2i.. sampled from Py.
Proof. We provide a simple proof for completeness. The proof is given in the single-observation case. The exact same argument applies in the n-observation case, by replacing by Iin-- We first show that minimum Bayesian redundancy is attained by the Bayesian mixture code Qu. For any distribution Q. we can see that
Red,, (Q : +) Red,, (Q, 1 T(0) [Di(PP Qx) DKu(Po do
| m() Σ (o())) In Q(x) da E[ [n Q(z)
(x(x)) ] ((0) Po(x)d8
(x(z)
((x) DKal Q1 []Q) < 0.
Σ (x) In (x(x)
The second part is simply rewriting the the definition of mutual information, follows:
BBaT,XxPP In Px(X)
I(X:0) (x,
In
P(X
P(X)
(0') Per (X) do'
/ π T(0) / Po(X) In Pa(X) (x)
dX d0
n (0) DKL Pg Qx7 d0
Red (Q.. θ).
This proves the lemma.
C Kolmogorov Structure Function and LLMs
C.1 Basic Concepts
In this section, we briefly introduce the concepts of Kolmogorov complexity K(-) and Kolmogorov structure function (-) (see the classic book [47] for more details), and how these concepts connected to LLMs. Although (.)) and hx (-) are not computable, their properties directly motivate theoretical modeling in latter sections.
Kolmogorov complexity: The Kolmogorov complexity K(X) of a string X defined as the length of the shortest binary program p that outputs X when run universal Turing machine U. Formally:
19

---

(X) := minpfpp Up)) - =X} where U is fixed universal Turing machine, is binary program and [p] denotes the length of the program p in bits. When there is no confusion, we omit the subscript U. The Kolmogorov complexity (X) measures the information content of X and is sometimes referred to as the algorithmic complexity of X. K (XX) has been considered by many as the "ultimate" notion for the compression of X and modern L.Mss can be thought as approximations of the Kolmogorov compressor (e.g., Ilya Sutskever's talk (69]).
While Shannon entropy H (P)) defines the fundamental limit for the expected code length of se- quences drawn from a source Pa. (X) provides the ultimate, non-probabilistic compression limit for a specific sequence X. The two concepts are deeply linked: for a sequence X that is typical according to a source Pa. its Kolmogorov complexity K ((X) is asymptotically close to its Shannon code length - log Po (X)). Consequently, the expected Kolmogorov complexity over the source, Ex-P,, [K (X) approximates the Shannon entropy (P&) 1 26)
Two-part code description: One can describe the data X by two-part description: the model description, and the data-to-model code describing X using the model. In particular, for any given lossless compressor M, one can see that
(XX)= < K(M) LL 0(1),
(8)
where T.M[ (X) represents the compressed length of X when using a lossless compressor M. When viewing an LLM as the compressor, the two-part description of the data X consists of K ((M), the description of the LLM (the architecture and the parameters), and the data-to-moder code of length LM (X). Specifically, for an LLM that predicts the probability (M / 11:m-1) of the next token auto-regressively, the code length LM (X) can be bounded by - log PM (X) + ((1) since one can encode X token by token using this many bits (via Arithmetic coding 62 16 for details.
See Appendix B.
Then we briefly review Kolmogorov structure function and related concepts. See 47 71 61 for more details.
Ch 5.5] or
We treat set S containing X as model describing X. According to the two-part description framework introduced earlier, one can describe every binary string X by a two-part description: The model description in the form of a finite set S that contains X, and the data-to-model code describing X given S (using K (XX (SS) bits).
In Kolmogorov complexity, we say that binary string X of length n is random if its Kolmogorov complexity (X) n = (1) (i.e., it is impossible to compress X significantly). Extending this idea, one can define the randommess deficiency of X with respect to set S (such that X E S) as
8(X 5)= log |S|
K(X |S).
Definition C.1 (eest Fit" function). It is also called the minimal randomness deficiency function, which is defined as:
Bx(a) = ming (8x ()) S X; K(S) S a.}
We say X a rypical or random element of a finite set S, or S is fitting model for X, X E S and the randomness deficiency 5(X S) O(1). Basically, it says that to describe X in S, one essentially needs log |5| + (1) bits (meaning X is not very special in S). This definition parallels the concept of typical set in information theory [13] Ch. 3]. If 5(X SS is small enough, X satisfies all properties of low complexity with high probability for the elements of S (see 71 for the details).
Definition C.2 (Kolmogorov structure function). Formally, it is defined as:
(x) = ming (log [S] : S X; K(S) S a.}
candidate "typical set" for the data X. One may understand 5 as the model of X (the complexity of S, should be at most a) and the term log measures how many bits are needed to single out X within S.
for any a 0. The set can be viewed
From the two-part deseription, it is easy to see that K(X) & K(S) + log [S] + 0(1. Hence, we have that
K(X) S a + 1x (a) + O(1).
'Kolmogorov complexity is universal in the following sense: If U is a universal TM, for any other TM A. there is constant CA such that Kx & (x(X) + CA for all string X. See 47].
20

---

Locs
That Look
Vata--iatted relondency
K(K)
Model-rriated redundrncy
(1PP) 3,, [og pe)
Red m Dxu(PP] Fs)
Iraedtciide Laone
(F(P))
Pure Randsmmnnc
Model
Modele Minimal
Sufficieat
K(X) K((0)
Statistion
Figure 5: Kolmogorov Structure Function View of LLMs:
The x-axis represents model size, while the y-axis represents the loss of the model, corresponding to code length of data given the model. The anti-diagonal solid straight line is the sufficiency line (r + = K (X)), )), which is the lower bound of the code length of all possible two- larp codes. The upper solid curve represents hxx (ax. The dashed blue curve is the test loss of some LLM. See more details about the test loss curve in Figure (b) in Figure
Hence, (ax cannot be below the sufficiency line L L(a))aa= K(X) (by more than additive constant). For those a's such that (X) I a + we say the corresponding model sufficient statistics, and the smallest such the minimum sufficient statistics [20]. The notion of sufficient statistics here parallels the same notion in the probabilistic setting: a sufficient statistic for the data captures all essential and relevant information and suffices for answering any downstream questions. Any additional information beyond the sufficient statistic is treated as "random noise" with respect these tasks. For instance, the exact phrasing of fact may be irrelevant for any downstream tasks unless it is so widely quoted that the particular wording appears frequently in the data, in which case it belongs the the sufficient statistic, rather than the noise.
In this paper, we use the probabilistic extension of the above definition (see 26 himself pointed out, the finite set model class is equivalent (up small additive terms) the model class of probability density functions [0] X is genuinely "typical" under the model distribution PM (parametrized by M), then log] parallels the negative log-likelihood, log (X)(X) (which is the code length of X under model M, ignoring the integer constraint). Hence, we define
As Kolmogorov
hx (a) minmm log (x)(X): K(PM) S a.
The shape of the structure function (o:) has been studied by several authors 61 61 47]. A major results in this line of research is that hxx (a) can essentially assume all possible shapes as along as it satisfies monotonicity, (0) [X]. (xx)(()) 0 and above the sufficiency line (up to logarithmic additive terms).
C.2 Kolmogorov Structure Functions and L.LMs
Recall from Eq. ① that log PM (X) is the empirical cross-entropy loss, which is also code length of data X using predictive model (up to an additive constant). See Figure 5 and Figure for schematic diagram of Kolmogorov structure function in the context of LLMSs (or any probabilistic language models). We explain several key aspects that motivate our theoretical modeling in this paper.
1. Kolmogorov Structure Function and Scaling Laws:
The Kolmogorov Structure function measures the performance of an optimal compressor under given model-size constraint. It provides deep insights into the structure of the data from the compression perspec- tive as the complexity of compressor increases. Such relationship directly mirrors the model scaling laws observed in the context of LLMs, where the training cross-entropy loss
21

---

Chroolatee Loss
Averuee Lows
Test Los of Mode teeined with New
Miniual Sulliact Sparleiie
X(X)
Model
K(Xua)
0
Data Siee
Data Size
The red dashed curve in Data Size-Model Size place represents the minimal sufficient statistic, the blue dashed curve in Model Size-Loss place represents the test loss. (a) An overview of the relationship among data size, model size, and loss. (b) An additional illustration of test loss curve in Model Size-Loss place. We replace the cumulative loss with the average loss the loss axis to better align with the setting of scaling laws. The test loss of the model trained with i is approximately given by (x(X) where denotes the minimal sufficient statistics of X1:. and n' > n so that the average loss on Xim serves as good approximation of the test loss.
Figure 6:
(or perplexity) decreases as parameter count size grow 42 33,, and hx (ax) can be viewed a theoretical lower bound of the empirical scaling laws (for all possible LLM architectures).
2. Structure of the Data: From the perspective of the Kolmogorov structure function hx (a), the structure of data X (the regularities and randomness in X) gradually revealed as the model size a (or complexity) increases. Initially, with relatively small a, a simple model captures the most pervasive regularities such as syntax in linguistic dataset because such patterns recur across every sentences (and therefore yield the greatest immediate reduction in coding cost or cross- cross-entropy loss). As a grows, the model gains enough capacity to encode less frequent regularities, including widely shared factual knowledge that appears relatively frequently in the data, albeit less frequently than the universal syntax. Next, captures rarer forms of knowledge that appear in smaller subsets of the data. Finally, for very large exceeding the minimal sufficient statistics, the model starts to encode "random noise". We note that similar high-level ideas appeared in the study of the shape of the structure function [71 (7]..
3. Minimal Sufficient Statistics and Randomness:
The irreducible test loss (e.g., the entropy term in (3) or (4) corresponds to the lowest possible test loss, ideally achieved at the minimal suffcient statistics. Beyond this point, any further drop in training loss merely reflects memorizing only pure randomness, such as different re- re-phrasings of the same fact. In our data generation model (see Section 3). we adopt probabilistic syntax model to capture such pure randomness in the language.
4. Redundancy and Scaling Laws: A central quantity in Figure is the redundancy of H(P
ee... the code, given by the KL divergence DKL (KL(Po.... PM)) where PM denotes the distribution predicted by the model and Po.... the data distribu- tion. Hence, characterizing the redundancy curve DKL (P (Pon. PPM) (varying the description length of the model M) provides the idealized model scaling law.
dram PM H(Po.u))
5. Growing Knowledge Models: Imagine that the data (consisting of sentences) has been generated sequentially. As the data size increases, natural to assume that the minimal sufficient statistics also grows, reflecting the expansion of "world knowledge" (e.g., newly discovered species, proteins, facts etc.). See Figure 6 the appendix for a dimensional diagram (incorporating the K ((X) axis) to illustrate the shape of hx (a:) with increasing data sizes. This insight motivates our subsequent data model, in which the knowledge model grows as the data size (modeled using nonparametric model).
To better understand the power-law behavior observed in empirical scaling laws of L.Mss, an instructive question to consider is: What structure in the data X causes the redundancy to follow
22

---

a power-law shape? Indeed, as pointed out by [3], different data structures can lead to different learning curves. To build intuition, first consider the example below that naturally yield a staircase shape.
Example C.3. Suppose is a binary string composed of three segments: 1. A segment of alternating bits (c.g., '010101... repeated many times). 2. A segment with a more subtle pattern (c.g.. inserting a '1' in every prmbeerd position). 3. A purely random segment.
At low model complexities a, the best model only captures the obvious alternating pattern in the first segment, causing the first drop in log |S|. Beyond a certain threshold (the size of a Turing machine capable of generating prime numbers), the model learns the more nuanced pattern, resulting in second drop. Beyond this point, (x( meets the sufficiency line, and further increases in merely allow the model to memorize the random segment almost bit by bit.
Then we intuitively answer the question What structure in the data X causes the redundancy to follow power-law shape?. Figure illusstraes the Kolmogorov structure function in a classical, finite setting. In this setting, we consider finite-length sequence X and the model code length for X in its two-part code description is also finite. However, natural language exhibits a property where knowledge scales with data, compelling us to consider the case when model code length grows with the data size. To build intuition, we consider simplified scenario that satisfies the above condition: data generated by an infiniteddimensional mixture model. We also assume the components of this model are encoded independently (i.e., the code length for set of components is approximately the sum of their individual code lengths) for simplicity. We explore the intuition for model scaling in the asymptotic regime where data size grows infinitely large relative to the model size. Given model size sufficient to encode M components, the redundancy induced by this model size constraint corresponds the sum of the tail mixture probabilities (i.e., the sum of all mixture probabilities excluding the M largest). If the mixture probabilities of this model with infinite dimensions follow a power law, then the resulting redundancy (the sum of tail that also follows a power law) also follows a power law. Conversely, if the sum of the tail probabilities follows power law, we can also deduce that the mixture probabilities themselves follow power law. This bidirectional relationship provides the intuition for our model scaling theory in Appendix F.22 and it can also serve as a theoretical bridge connecting empirically observed phenomena in language, such as Zipf's s Law and Heaps' Law, with the model scaling observed in large language models.
We also note that Kolmogorov structure function is closely related to the rate-distortion function in Shannon's 's information theory. Specifically, the expected Kolmogorov structure function can be shown to be approximately equal to the rate-distortion function, see e.g.. 266 In our study of model scaling law in Appendix E.2
we leverage the concept of rate-distortion function as well.
As illustrated above, the Kolmogorov structure function provides insights into model scaling. In Figure [6] we extend this concept to incorporate the data scaling. Following the intuition provided carlier for the question What structure in the data X causes the redundancy to follow a power-law shape?, we consider that the data is generated from an dimens-aimeniionall power-law mixture model. In this case, the minimal sufficient statistics with respect to the model size also exhibit power law, as shown in the left panel of Figure G
The right panel of Figure Gillustrates the relationship between the Kolmogorov structure function and the test loss of an LLM training with finite data. Crucially, the test loss represents the expected loss of trained model on unseen data, effectively an average loss over an infinitely large test set. In the right panel, this is approximated using test set of size n' much larger than the training set size (i.e., n' >> n.). To maintain consistency with this approximation, the y-axis in the right panel of Figure represents average loss(h, (Xim)/n) rather than cumulative loss(h, (X1=)))
Intuitively, guided by the two-part code description and Kolmogorov structure function, the behavior of the test loss as a function of model size can be segmented into two phases around the minimal sufficient statistics. The connection is as follows: Before the model capacity reaches the minimal sufficient statistics for the training data X1m. the optimal test loss corresponds the average structure function evaluated on a much larger dataset X1.... As model size increases in this region, the test loss decreases because the model capturing more of the data's true, generalizable structure. However, once the model capacity surpasses the minimal sufficient statistics, it begins to overfit by memorizing pure noise specific to the training set X 1isn- At this point, further increases in model size no longer improve generalization, causing the optimal test loss to plateau.
23

---

Therefore, the optimal redundancy achievable given the training data X is equivalent to the redundancy obtained with infinite data, but under a model size constraint determined by the minimal sufficient statistics of X. We have previously established that for infinite data, the redundancy exhibits power-law relationship with the model size constraint. Furthermore, as we show in the left panel of Figure 6 and demonstrated before, the size of the data ((X]) and the size of its minimal sufficient statistics also follow a power-law relationship. Combining these two factors implies that the optimal redundancy for training data X also follows power-law relationship with respect to the size of X.
D Details of the Syntax-Knowledge Model
In this section, we propose hierarchical data generation model, called the syntax-knowledge model. In this model, where each sentence in the training set is generated by a syntax encoder that encode a (factual) knowledge element, sampled from the knowledge model. In our model, the syntax model (e.g., a probabilistic CFG or English grammar) does not grow indefinitely with the size of the dataset. Therefore, we assume that the distribution of the syntax model can be parametrized using finite- dimensional parameter Dsyn- On the other hand, the knowledge model employs a non-parametric stochastic process to account for two empirically observed phenomena: 1) the unbounded growth of factual information as datasets grow (mirroring Heap's 's Law in lexical growth patterns [30], and 2) the long-tailed frequency distribution of factual occurrences, analogous Zipf's 's law in natural language [76 77).
To operationalize this above idea, we leverage the Pitman-Yo Yor Mixture Model(PYMM, [56] for modeling the knowledge model. The preferential attachment mechanism in Pitman- Yor Process naturally captures both the sublinear scaling of new factual discoveries and the power-law distributed frequencies of knowledge pieces.
Notations:
We denote the conditional probability p(z +) as Pa (a(), where & is the latent variable that determines this probability distribution. The syntax model parameterized by Dyyn. the knowledge model is denoted as <kkm, and the entire data model is denoted as ddaa = {dsyn @kmw }-
The syntactic elements generated by the syntax model are denoted by &I,,, and the knowledge elements generated by the knowledge model are denoted by KI.N. The corpus consists of sentences XI.N. where each sentence X; is generated by the syntax model from a syntax-knowledge pair (E., H..) Now, we provide the details below.
D.1
The Non-Parametric Knowledge Model
We model the knowledge model as a Pitman- Yor Mixture Model (PYMM), which is a nonparametric Bayesian model. We first introduce the Pitman- Mor Process, from which the PYMM is constructed.
Pitman- Yor Process:
The Pitman- Yor Process (PYP), also known as the Pitman Yor awo-parameter GaisonnDiricche process, extends the Dirichlet Process (DP) and the Chinese Restaurant Process 56 It has been applied to model a growing number of topics in the literature of topic modeling A Pitman-Yo Yor Process (PYP) is characterized by two real-valued parameters: the discount parameter 0 S a and the concentration parameter B > aa, along with base probability measure Tkow- We denote the process PYP(a, 3, Tknw).
70
22
sample from the Pitman-Yor process PYP (a, 8, kkww random probability measure @knw x
1 Prog,, which is discrete distribution with countably infinite atoms, where:
Each atom di ~ Tkow is the i-th cluster parameter, independently drawn from the base measure Tkawi
6s. denotes the Dirac delta measure centered at dx;
p (P1.P2.... are the weights generated by the Pitman- Yor Chinese Restaurant Process (PYCRP) (described below).
Imagining a restaurant where customers arrive sequentially, each choosing either to join an existing lively table or start their own, resulting in naturally evolving clustering structure.
* The first customer sits at new table.
24

---

Suppose N₂ is the number of customers already at table k, and K is the current number of occupied tables. The n-th customer either joins an existing table is or starts new table with the following probabilities:
N
joining an existing table k.
71
1+
For the n-th customer:
8 + aK
if starting table,
As the number of customers oo, the relative sizes of the tables (i.e., the proportion of customers each table) converge in distribution to a random probability vector [5).L H..1) denoted as:
p (P1, P2....) lim "t/n,..., PYCRP(a:
This probability vector p (p1, .2....) asymptotically exhibits power-law distribution(see Lemma H.2
Pitman-Yon Yor Mixture Model (PYMM); In the Pitman- Yor Mixture Model, the Pitman-Yo Yor Process
PYP(a, 3, Tknw) serves as prior over the space of mixture distributions. particular, random probability measure @knw E P;og., sampled from PYP(a, B, Tanw), can be interpreted discrete mixture model: to generate knowledge element from Pknw- one first selects index E N with probability pt. then draws sample from the conditional distribution Po., where o, Tkaw is the i-th cluster parameter.
The knowledge elements generated by the knowledge model are abstract representations that capture the factual component underlying a sentence. We assume that the support of the knowledge element lies in a discrete set IK (i.e., each knowledge element K E IK. Although the cardinality [| may be potentially very large, we assume that log [K] is quite small (since log [K] roughly the number of bits or tokens required to encode the knowledge element), and particularly much smaller compared to No for any a >
We assume that the base measure Tknw, from which the knowledge cluster parameters d; are drawn, supported on the bounded parameter space kaw {drmw 1Rdum | ||2 < 1). Given the parameter spaces Penw. we define corresponding parametric families of probability distributions: Prr.. = (P(- @kow) Pknw E 4 kaw } where P(- @kow) denotes the conditional distribution the knowledge model given parameter @kow-
D.2 Parametric Syntax Model
The syntax model generates syntactic elements conditioned knowledge elements. Each knowledge element & E K deterministically selects an index E (1...., n,), corresponding to a latent variable
Ayy that parameterizes the conditional syntax model.
Conditioning the generation of syntax on a knowledge element thus equivalent to conditioning on the corresponding latent variable:
P( Osyn, R)) P(. ((())
Accordingly, the overall syntax model is parameterized as:
syn = {o (1)
(2)
(n.)
syn syn
The syntactic elements abstract representations capturing surface-level variation such word choice (e.g.. synonyms), phrase structure (e.g., active vs. passive voice), and other randomness that does not affect the underlying semantics.
We assume that the prior distribution syns from which the conditional syntax model parameters Øsyn are drawn, is supported on the bounded parameter space & syn {dsya E dd |/@syalle l2 S 1} for all < i < n,, Given the parameter spaces & Psyn= we define corresponding parametric families of probability distributions:
Pay (P(- @syn) Asyn E + syn)
where P(- |sya) denotes the conditional distribution of the syntax model given parameter dsyn-
25

---

Knowledge Model knnw (PYMM)
4
Knowledge e-PPa
Sentence
Payn
Paym
Syntax {~P day ( (k)
P
Syntax Model 42 syn
Figure 7: An illustration of the hierarchical Syytax-Knowlenn data model
D.3 Hierarchical Syntax-Knowledge Data Model
We propose that the Syntax-Knowledge model generates sentence according to the following hierarchical Bayesian framework (see Figure
1. Sample the latent variables for the knowledge and syntax models:
Ōknw ~ PYP(a, B, Tkow),
Osyn = (1) Osyn. Syn
}
d Tsya(dsya)
lid
2. Sample knowledge element k::
Pkx @kmw).
3. Sample syntactic element & conditioned on the sampled knowledge element
P(E Osyn, Ki).
4. The syntax encoder generates the sentence from the assume that the syntactic element & has already captured the randomness in the syntax, and there one-to-one mapping between sentence and the syntax-knowledge pair (E, k). Note that we do not assume the one-to-one mapping to be explicitly known or Icarnable. For the purpose our theoretical analysis, is sufficient to assume the existence of such mapping. which ensures identifiability of the observed sentence with respect to its underlying syntax and knowledge elements.
pair (E, k).. We
By independently repeating steps 2, 3, 4 for N times, obtain corpus X1.N consisting of N i.i.d. sentences generated from the Syntax- Knowledge model.
We now illustrate how our data model generates data through simple bioS dataset example. Note that our data model is not limited to such examples.
Example D.I. A concrete example is the generation of the bioS dataset designed in 3 For example, knowledge element & encodes the factual knowledge about an individual: [Person: Alice], [Event: Birth]. [Date: Jamuary 2000]. syntax element corresponding to sentence template. Conditioned on the knowledge element K, the syntax model chooses a syntax element &. such as "[Subject] was born on [Date]". By composing (E, k.), the resulting sentence is: "Alice was born on January 1, 2000." Alternatively, the syntax model may select different syntax element, "[Subject] entered the world on [Date]"' yielding the sentence: "Alice entered the world on January 1, 2000." Note that the choice of syntax element is dependent on the knowledge element; for instance, if the knowledge element pertains to an animal, different syntax element would be chosen.
E Explaining Scaling Laws
In Section 4.2 we established a data scaling law under the Bayesian setting for our Syntax-Knowledt model, showing that the optimal Bayesian redundancy decreases according to power law with
26

---

respect to data size, with an exponent larger than -1. Given our earlier results from Section 4.2) we know the syntax model is learned at significantly faster rate (also observed empirically), and thus the scaling law is primarily driven by the knowledge model. For simplicity, we ignore the syntax model in this section and focus exclusively on the knowledge model. this section, we derive a similar power-law behavior under slightly different set of assumptions. The key differentiating assumption is that knowledge is represented a seession-answering format, which ensures the identifiability of the mixture knowledge model. These assumptions greatly simplify the theoretical proof and allows us to derive both upper and lower bounds on redundancy, as long as the model satisfies Assumption E.3 (without requiring it to be optimal Bayesian predictor). The central insight of this section is that the empirically observed scaling laws primarily stem from the power-law-dee distribttb structure in the data. As result, the assumptions made here do not affect the validity of our main conclusion. We also provide the omitted details from the model scaling law part (Section 4.3 in the main text.
We continue modeling the knowledge model δknw Eis p:gg, as an infinite mixture model but now make the following assumption on the mixing probabilities p:.
Assumption E.1. For the mixture model cknw = =i= pióg.. the mixing probabilities p; follow power-law distribution: p: = (01l/a)-1;-1 where c(1/a) = - i-1/a is the Riemann zeta function.
Note that the choice of exponent 1/a aligns with the asymptotic behavior of mixing weights in the Pitman-Yon Yor Process PYP(a, 3, kkow) (see Lemma H.2
In this section, we represent knowledge as question-anseee pairs. We assume knowledge is given by pairs (sb, w), where s denotes the question description, and w is the answer of the question. Each knowledge cluster corresponds to set of question descriptions F; and generates knowledge pairs (1,ww) ~ Po. where & v We assume that the sets of question descriptions corresponding to different knowledge clusters are pairwise disjoint, i.e., V n ; = 0 for i * j.
Here, we are only concerned with whether the model can provide the corresponding answer given a specific question. Consequently, the redundancy of the model with respect to the i-th knowledge cluster is defined as follows:
Definition E.2. The redundancy of the model M associated with the i-th knowledge cluster and conditioned on knowledge being drawn from this cluster, is defined
Red (6) = Pap [DKL (Po. tb = q) Par(w | v = 4))],
where Pg. denotes the data distribution induced by the cluster-specific parameter di and PM is the predictive distribution defined by the model M.
The total expected redundancy of the model M under the prior over knowledge clusters is then given by:
Red == Σ P. -mo (+) 1=1
E.1 Data Scaling Laws
In this section, we derive the data scaling law under the assumption that there is no model capacity constraint. There are two key differences between this section and Section 4.2 First, analyze the redundancy of a potentially suboptimal model under certain assumptions, whereas Section 4.2 focuses on the optimal case. Second, we study the test redundancy, in contrast to the Bayesian redundancy considered in Section [.2] which corresponds to the averaged cumulative redundancy. Moreover, unlike Section 4.2 which provides only upper bound, this section establishes both upper and lower bounds. The effect of dataset size on (e) primarily arises from the number of occurrences of the question description g E V, in the training data. Accordingly, we express (ed as Red (t.,, where is the number of such occurrences in the training data. The expected redundancy under data size constraint is then given by
Red = E,,
Σ
P. Ead Tumn
[Red (1:)
27

---

where E denotes random variable representing the number of occurrences of the i-th knowledge cluster in a training dataset of size ...
Next, we present the assumptions on Red and derive the upper and lower bound for Red under these assumptions.
Assumption E.3. (I) The expected redundancy of unseen cluster of knowledge (i.e., to = 0) exceeds a certain constant C1, i.e., Eg Red (0) > c1 for all E N
(II) For all cluster of knowledge, there exists a constant C2 such that Es, Eo Riare for all i, EW
Red O (t) S ++1
C2
Assumption (I) posits that the model exhibits constant redundancy when encountering unseen knowledge, which we consider reasonable. We now turn to the validity of Assumption (II). During language model training, the objective is to minimize the negative log-likelihood, which equivalent to maximizing the likelihood function. When the model is viewed maximum likelihood estimator (MLE), the asymptotic normality of the MLE implies that the redundancy, in the asymptotic regime, is of the same order as specified in Assumption (II).
Lemma E.4 (Asymptotic Normality of MLE). Lei XI,x2,...,,X be i..dd samples drawn from distribution Pa-, and let 0,. arg maxg ((O) denote the maximum likelihood estimator. Then, as n + 0o, the MLE satisfies
va(0,,00 S J(0)-))
where J(0)) the Fisher information matrix evaluated at 0".
Combining this conclusion with the result in Lemma H.6, we conclude that, under the asymptotic
regime, the redundancy of the MLE matches the order assumed in Assumption (II). We assume that this order holds in all cases. Note that the assumption is stated with 1/(t + 1) instead of 1/t to include the case where t O.
Theorem E.S. Under (1) in Assumption E33 the total expected redundancy Red satisfies
(e) = -(NN1+0).
Under (II) in Assumption E.3
the total expected redundancy Red satisfies
= (
Proof of Theorem E.5
Denote ft(t,) = Eg Red D (t:)].
We begin by proving the first part of the theorem.
Red
Σ Pelle,,fattt
Σ
I
Pk 1+1 (1-1p))) pt) (1-b)) (MM) fu(l)
N> İ=u
(2)
Σ
pb(1 fa
fa
No
(3)
C
Σ k1/a (1- <(1/))N))) No
1 N
((1/a)
2c((1/a)
ki/a
= QQN -(N-1ta))
28

---

(1) is obtained by expanding the expectation; (2) corresponds to taking the term with = 0; and (3) is
derived by substituting the value of pk: (1//((1/a)
Next, we prove the second part. For all k E W we know that
(1 PW)N-1 (N) (?,) (u(1))
Ph.
Pk
N
1 1+1 (N+1)
Σ Pk
(1 pb)) N-1 pb)
fa(l)
N + 1 [1+1]
max(1 + (1)x(()
N Σ
11 pk) px)
(N-1(N+1 NN+N +1)
1+1 (1+1)
pk
N+1
1=0
max(I + 11)
N+1
N+1
(1) is obtained by expanding the expectation, and (2) is derived by utilizing
(1 Pa (x++) =
Σ 1+1 (1 pk) N ((++)) = 1.
Therefore,
Σ Pr
C2 No = 14N- N +11"
N
For h: > No, we have
N
(1)))-(()) (7) Sa(l)
Σ (A()))
Σ Σ
141 (1 - (1-Pk)***
Pk
R>
A3 1=0
N
11
Sa(l)
C(L/a)/J/a
h> No
1=0
N
N
Σ
Sx(1)
A1fa
N
7
No
1=0
N
fa(1)
kt/a
Z!
No
I=0
N
fk(()
Σ
1!
ki/a
1=0
No
1
Σ
1
< 2
(1
1)!
k1/a
1=0
Ni/a
S O2 Σ
1
1NN-)
kl/a
No
(1) is obtained by substituting Pk k1/a((1/a) and using the inequality (1 N-1 1 1: (2)
follows from the fact that ((1/a) and k N (3) uses the bound (M) s N'
!!
29

---

Therefore, we can see that
(e) Bk
Σ pafe(tte)
3 S(NN-tta)
This completes the proof.
E.2 Model Scaling Laws
In this section, we consider the optimal redundancy achievable by an omniscient model M under a model capacity constraint. (That is, the model M has access to the true data distribution (data)) Due to the finite capacity, the model M must apply lossy compression to each di resulting in (4) (m,). where m, denotes the constraint of the mutual information between the model and ø; (one may think it as the memory allocated to compress o,). The minimal achievable redundancy under a given memory constraint conditioned on a given cluster knowledge is characterized by the distortion-rate function:
corresponding redundancy Red
Egg-Po DKL (Po v = 9) PM; (w v = ])]]]
D.(R)= = min B
where 11(;;; M represents the information retained about Φ; after compression.
Furthermore, the omniscient model M allocates memory to each é; in manner that minimizes the expected redundancy. Formally, the memory allocation corresponds the solution of the following optimization problem:
minimize (mD)((m;)] = Σ piDi(m,).
i=1
subject I Mτ) S m, I(b M 2 0 for all i e N+
where Py = (01. ......) and I( Mc) $ C represents the model capacity constraint.
If we further assume that Φ; 1 + -- M i.e., é; is conditionally independent of the remaining cluster parameters given the model M where 4_ (øI,.... 0 0..1....). In other words, conditional on the model M knowing Φ; does not provide any additional information about Φ, for j * Under this assumption, the model capacity constraint can be decomposed as follows:
C' 2 Mc) = 11 M2) + +101; --1)
I(4-1:M2? +I(or:M²))
((0-2; + I(02; M + 1(:1: M
Σ I(a
Therefore, the optimization problem can be rewritten as:
minimize
p.Di(m)).
(9)
00 m; S C,
subject to
m 2 0 all N
Let Reda(() denote the optimal value of the problem in 9 representing the minimal achievable redundancy under the model capacity constraint.
In general, the distortion-ran rate function is hard to express analytically. Here, we make the following assumptions.
Assumption E.6. We assume that the distortion-rate function (R) satisfies
there exists positive constant c3, 64 such that for all e Nt, S c3. the distortion-rate function (R) 2 C1.
30

---

there exists positive constant Cmax: bmax such that for all i E EN,, the distortion rate function (R) I Cmax b
The first assumption states that when the rate small, the distortion cannot drop below threshold, which is natural property of rate-distortion theory for general sources.
The second assumptions can be formally justified within the framework of rate-distortion theory when the distortion function is the mean squared error (MSE) [33.. Although the distortion function in our setting is not MSE but rather the KL divergence between the probability distributions induced by the parameters, Lemma H.6 shows that the two distortion measures exhibit similar behavior in a local neighborhood.
Distortion Rate Function of Gaussian Distribution: Let X (O o²) be zero-mean Gaussian source, and let the distortion measure be the mean squared error (MSE). The distortion-rate function (RR defined the minimum achievable distortion under a given rate R:
D(R)
min p(x)))((x:
E[(X -
For the Gaussian source with MSE distortion, the closed-form solution is:
D(R) = .2.2-28 R20 0
Distortion-Ree Rate Upper Bound via Maximum Entropy of Gaussian Distribution Among real-valued random variables with fixed variance, the Gaussian distribution achieves the maximum differential entropy:
h(X)= 1
log log(2Tee²?)
with equality if and only X NoO. This implies that under fixed distortion constraint and mean squared error (MSE) as the distortion measure, the Gaussian source requires the highest rate among all sources with the same variance.
Therefore, the distortion-rate function of any real-valued source with variance o² must satisfy:
D(R) S 22.
R20 0,
with equality achieved only when the source is Gaussian. This provides a universal lower bound achievable distortion under MSE for given rate R.
Theorem E.7 (Resteatement of Theorem 4.6). Under Assumption 4.3 and Assumption 4.4 the optimal value of the optimization problem under the given model size constraint satisfies:
Red (C) = (CC))=@(C01) =O(C1/atl)
Moreover, if we further assume that (R) axbr for some constant Umin S bb S Umaxx Omnin S ag S amax the contribution of the k-th cluster is
Pk DxDD(mp) = (minn( 1/a c-1/a)).
where my is the solution of the optimization problem.
9
Proof of Theorem 4.6 We first provide a lower bound for the optimal value. By Assumption 4.5 we
have (x(m)) C4 whenever my c3. Since Σ my < C. there can be at most [C/ca] indices A A=1
such that (m())) < ca. Due to the monotonicity of Pk. we know that
pk (p(m))) >
P&ca ((C-1/+
(10)
C//al
31

---

Next, we solve the optimization problem (E.2 under assumption Dx(R) = oxbk
using KKT
condition. First consider the Lagrangian dual:
00
8
C(k, A.
Σ (mDx)(mx) +1
Σ
m&
C
pgm.
We list the KKT conditions below:
Stationarity: Pk: (m(g)) A M4 0,
Ak > 1.
(11)
Primal feasibility:
m SC
m 2 0,
A4 2 1.
(12)
Dual feasibility:
A2 O, Me 20,
Ak 1.
(13)
Complementary slackness:
A
Σ m C = 0,
pam =0, 0,
vk >
(14)
Due to monotonicity, we know that Σ
m
C. By the Stationary condition
we know that
k=1
A
Da
Pk
Due to the convexity of D [3], we know that Dj. is monotonically increasing. Therefore, the inverse of Dj exists, and we denote it as Jk-
For m > O, we have O, thus we know that
m
max
9h
0
Pk
Next, we estimate the value of A. Since we have assumed that (R(R) axbs for some Amin S
by < Umax, Qmin S I Omax so there exists ri, r2, d1, de such that
x/](dd I gx(-2) x) I - In(22)).
Then, we know that
1//=
d2h dzk-1/a 1/a
max 0, In
}
S m I max 0, In
A
A
where ri = r In r2
Assume 4 is the maximum integer such that d1t d14 Therefore, we have
1/a 11/a
A. We know that di (4 + 1) < X <
dik-1/a
-1/a 1/a
C 2 max
0, In
x =
In
k=1 A
k=1
k k-1/a
r
In
1/1 1/a
11
a
[nnt 1n/1
k=1
By Stirling's formula, know that In 1/ - -nnl (11). So we know that
C2 0(4) = 0(2a1/a).
Similarly, assume 1a the maximum integer such that d2lg 1/0 < d2tz 1/a Therefore, we have
A. We know that dz + d2(22+ 1)-1//a
s
dzk-
1-1/
C < max
0, r2 In
12
In
A
A
h: 1110 1/a
72 (In(le + 1)a+1 -l(z4))
< 12
In
(l2 + 1) 11/a
1/a
km
32

---

By Stirling's 's formula, we know that In 1/2 - In 1z! O(22). So we know that
C (12) ( (A)-
Since we know that ((4) = -(0 (l2)), we have that
C= @(1)) 0(6) ((1-1/a).
For S 4, we have that
0,r, ri In 1//-
21 d 1/a
mi 2 max
0.
A
For 12, we have that
m S max 0, In d2k
=0.
Thus m = 0 for k > 12. Hence, we have that
PaDa(m O(minkk 1/a 1//, c-1/ay).
Finally, we prove that Red (C) 2 0(M Since we have assumed that D&(R) = axbb for some bmin by bmax: Omin I a₁ 0max. we know that there exists constant d3, dg such that
d,D)((i, - Dz(mū) - d,D (m)))
Thus we know that
ph Du (m+)) 2 d3 Σx+
x C3
Σ Pk
k:12
= (111 = 1(M
(15)
Similarly,
pk D& S ds Σ X C4
Σ Pk
(16)
k5h
AS4
( 0(1 1ott///t))) O
(17)
Combining Equation
15) and Equation
16
together, we have that
8
Σ
PxDx(m))) O (/a+))
Note that the above solution carried out under a strong assumption D&(R) = o0 ogbb Thus under
Assumption 4.5 we have Red (C') & (CC-1/at1). Combining this and (10). we have that
Red (C) = (CC
F Fine-Tuning
Fine-tuning LLM is typically used for two broad purposes: (1) instruction-following (2) knowledge injection. Here, we focus on standard instruction fine-tuning scenario. Consider, for instance, in our experiment, model that has been pretrained bioS (multi+permute) dataset 3 and has already learned factual knowledge about specific individuals. During fine-tuning, our goal to fine-tune the model to be able to answer the questions about these individuals, and thus the fine-tuning dataset consists of question-antt -enstionn-answrr answer pairs with facts drawn from the same distribution as the pretraining data.
We view the generation of pretraining data and instruction fine-tuning data as a two-stage data generation process. The first stage, corresponding to the generation of pretraining data, follows the
33

---

data model introduced in Appendix D In the second stage, i.e., the instruction fine-tuning stage, the knowledge model and the generation process of knowledge elements in the data remain unchanged; however, the syntactic elements are produced by different syntax model (e.g., the question-answe -nnseer format), which we denote by @ins-
Let X denote the pretraining corpus, which is generated by (Osyn Qkow) and X N+NNN++ the instruction fine-tuning corpus, generated by (Cinss (knw). The full corpus denoted by X X1:N+2- Following the same reasoning as in Section 4.2 the Bayesian redundancy of the full corpus X X1N442 given by the mutual information
T(X i:N+ni Pkyn, Vins; (kow)
In the following, we present (somewhat heuristic) decomposition of the redundancy the full corpus. The se in the derivation below requires certain independence assumption, which may not hold exactly in real world, and bounding the approximation error is left as future work.
As in our data generation process, there is a one-to-one mapping between sentence X and its syntax knollx--nowwdggee element pair k).. Hence, using the chain rule of mutual information, we can write
I(X1:N Osya. Pins: (knw) I[K1:N +ni Psyn Pisss @kow) ) + 10I5 +nr Osya Pins Pknw
K1:N+t)
Also note that the first and second terms in the RHS can be decomposed
[1(NI:N+ti Osyns Pins: (kmw) = 1(111:N 1:N1:+++0 +ni @kaw) + [ Dsyn: Pins @knw);
((E1:44m) Osyn: Vinss kkow 11::4+)) = 11:N1 Psyn: ; chins kI:N+n)+ I:N Ckkw | Øsyn: Pins K. K1:N+n).
Note that IIN:1:N=.: Psyn: Clins @kkw) = O since the knowledge elements are generated independently of the syntax model, and II(E,, +n Okow Osyns Pins k1:N+n) O since Ōkow K & form a Markov chain. Hence, we can see that
I[ IINN4on Osyns Vinss (knw)
I[( (KI:N44 )kew))
+ II(E Iin Psyn thins (I:N+4)
I[( (Ki (knw)
+ I(EE I.N+ni Psyns Pans)
T( (Ki:N+ni kma))
+ T((I:Ni Psyns Pims) + T(EN+11N+4 Payns Pins E1:N)
( (rew))
+ I[EI:Ni Osyn) + I(EI:Ni i Pins Doyn)
+ II N nn Pim EI:N) + I(5N+1::N 1:N Osyn Pins: E E1:N)
T(( [TT[(1::++ (knw)
+ T(EI:N: (baya) + T(E +I:N+++ Pins)
In the above, approximation 2 relies on the assumption f1-N+n I KL:N+n. and requires EN+1:N+n Ei.N and &N+I:N+ dsyn Óins f1:N. both of which can be induced by the same assumption f1:N+n I KI:N+a- Under the same assumption, the redundancy of the pretraining corpus can also be decomposed as follows:
((NiN; Osyns (how)
= =KIiN Oayn, (kknw) + I(E1.N5 Psyn, Oknw (EEN))
-I((1:: (kew) 1iii Osyn K1:N)
<T11:: (kmnw) + I(EI.Ni (sym)
The redundancy of the instruction fine-tuning corpus can be written the difference between the redundancy the full corpus and the redundancy the pretraining corpus:
[[XX::N +ni Dsyns Dins; kkow) II( I(X1.N) 1:N; thyn: kkm)) RV [[N:::N4m
(kow) I(KI:NS (kow) + IIE II Vins)
Redum
Red...
The terms in the above equation correspond to the redundancy of knowledge elements Red and the redundancy of syntactic elements Redjos in the instruction fine-tuning corpus, respectively.
Following the same arguments in the proof of Theorem 4.2 we can see that [[(N; ckew) = Ô(N*), and hence for simplicity, we further assume that [[<:; x c/ for some constant c > 0. Then, the average redundancy of the instruction fine-tuning corpus satisfies:
(N + +2)"
N
Redknw [1 kkow) 11(M1::; (xnw)
O(Nv--),
71
1
Redins
@mn)) = Ō(n
34

---

where relies on the natural assumption that the size of pretrain corpus N is much larger than the size of instruction fine-tuning corpus n. Similar to Theorem 4.2 the primary effect of fine-tuning in this scenario is that the model learns the new syntax to reduce the fine-tuning loss (i.e., redundancy)
with fast rate Ö(n ) hence requiring relative fewer samples, while allowing the model to retain the factual knowledge it has already acquired (N is large and the redundancy for the knowledge elements O(N*-1) is quite small).
On the other hand, consider the setting where our objective is to inject new knowledge via fine-tuning. Suppose the fine-tuning data uses a drastically different syntax or format from that used in pretraining, as well completely new knowledge. Now, the Bayesian redundancy is equal
[ 1:NN Osyn: Pinss Sknw, Pnknw)
(18)
where Onknw is the new knowledge model. If the new syntax component very different from the original one, and the knowledge component is also quite new (i.e.. nearly independent from the pretraining), the mutual information (18) can be approximately decomposed into
[(NI:N+ Dsyn; Dins; Kknw, @nknw) Rd I(Xi:N;; Psyn (knw) + I[X I:NN+I:++ni Pins; Pnknw).
The first term corresponds to the redundancy of the pretraining phase, and the second term corresponds to finetuning and the redundancy (per sentence) can be bounded as (ct /////nn + C2 c2/n²=a) according to the same argument in Theorem 4.2 As is much smaller than N, can that the fine-tuning would experience a significant perplexity shift (even the entropy, which is the irreducible part of the loss, may also shift). Moreover, the additional syntax learning step not only slows down the learning. but also risks occupying the model's limited capacity, leading to forgetting of the pretrained knowledge, especially when the model's i'' capacity is constrained. See the experimental results in Appendix G.2, Therefore, two practical recommendations are in order (consistent with good practices in prior empirical works
When injecting new knowledge during fine-tuning, avoid drastically different formats syntaxes that deviate significantly from the original pretraining data, especially in the capacity constrained setting. By preserving familiar structures, the model can focus absorbing new facts rather than first learning an unfamiliar syntax. Moreover, it is beneficial to adopt a gradual approach that mixes the pretrained data with a portion of new knowledge during finetuning, which helps mitigate large perplexity shifts and makes the optimization more stable 28 36
Knowledge Injection:
Instruction Fine-Tuning. For instruction fine-tuning (e.g., adapting a model to ques- tion-answer formats), use knowledge set that closely aligns with the data distribution seen during pretraining. This ensures that most of the fine-tuning effort is spent on learning new syntax or style. Moreover, if we use completely a new set of knowledge in the SFT stage, the model only focuses on compressing the SFT dataset, which slows down the learning and may lead to forgetting of pretrained knowledge as well.
G Experimental Setting and Additional Experimental Results
G.1 Experiment Setting
Following the experimental setting from 3 generate profiles for 400,000 individuals. Each profile contains six attributes: date of birth, birth city, university, major, employer, and employer city. These attributes are used to populate a diverse set of templates (each type of informatiion/nnstrucion has 50 different templates), forming both pretraining and instruction fine-tuning datasets, as shown in Table [ In the instruction tuning, we use data instances with odd indices (e.g., 1, 3, 5, 7, ...) as the training set and those with even indices (e.g., 2, 4, 6, 8, ...) as the test set.
As discussed in our theoretical section, the occurrence frequency of individuals in the pretrain- ing/instruction fine-tume tuning dataset follows a power-law distribution, formulated as Equation 19:
(i + bias) -a
P(1)
(19)
Σ Σラ=1 (j + bias)
N
35

---

Table 1: Examples of Pretraining and Instruction Fine- Tuninn Data
Dataset Type
Example
Pretraining
"Gracie Tessa Howell was born in Camden, NJ. He stud- ied Biomedical Engineering and worked UnitedHealth Group. He entered the world on April 15, 2081, and is em- ployed in Minnetonka. He is an alumnus/alumna of Buena Vista College."
Instruction Fine-Tuning
"Q: What area of study did Gracie Tessa Howell focus on? A: Biomedical Engineer- ing"
where denotes the index of the individual, N is the total number of individuals, and a is the exponent parameter. Note that the frequency of data occurrence generated by power-law distribution exhibits asymptotic behavior similar to that produced by the PYCRP (YCRP(1/a, 3) (See Lemma H.2
We set bias 1000 and vary the parameter over {0, 1.05, 1.20, 1.35, 1.50). If not specified, choose a = 1.20. The final pretraining dataset contains 1.45B tokens (tokenized using the GPT-2 tokenizer), and the instruction fine-tuning dataset consists of 258M tokens. Pretraining is conducted for 4 epochs, totaling 5.8B tokens processed almost twice the amount suggested by the Chinchilla scaling law.
We conduct experiments with RoPE- GPT-like models 39 of various sizes. The model configurations are detailed Table
Model Configuration
Training Procedure For training, we use sequence length 512 and batch size of 128. We apply a warmup ratio of 0.05 and a warmdown ratio of 0.9. Pretraining runs for 4 epoch with a learning rate of 0.0003, while fine-tuning runs for epochs with a reduced learning rate of 0.00003. We employ weight decay of 0.1 and bfl6 precision. To enhance parallelism, multiple sequences are packed into 5 512-token sequences, but cross sequenee attention is masked out.
G.2 Experiment Results
Data Heterogeneity We evaluate the accuracy of various properties under two different data distributions and power-law-to examine the heterogeneous nature of model learning. For each setting, we train models of varying sizes and measure their accuracy across multiple properties, revealing how capacity constraints influence what types of knowledge are learned first.
As shown in Figure 8 both settings demonstrate that models with limited capacity exhibit selective learning behavior some properties are prioritized over others. Properties with lower entropy, such as Major, are easier to learn, as they contain less variability and thus can be compressed more efficiently by small models. In contrast, high-entropy properties require more capacity to capture and generalize. A notable example is the property company city. In both settings, this attribute starts with non-trivial accuracy of approximately 7%, even when other properties remain close to zero. This is due New York appearing with 7% frequency in the dataset. Small models, unable to generalize meaningfully. default to outputting the most frequent token-aa an effect more visible in the uniform setting where each person appears the same number of times in the pretraining corpus, i.c. person is inherently easier.
However, the dynamics of this heterogeneity differ across the two distributions. Under the power- law setting (right), model accuracy for each property increases gradually as capacity grows. This suggests a smooth transition in learning, where dominant and compressible properties are acquired first, followed by rarer or more complex ones as capacity permits. In contrast, the uniform setting (left) reveals more abrupt phase transition: most properties remain near-zero in accuracy until the model reaches a critical capacity threshold, after which multiple properties are rapidly acquired. This implies that, for sapacity-constrainee models, structuring knowledge injection with skewed
36

---

Seritary
0.6
Accuracy
Property
Proprtty
Company City
Company City
Date
Birth Date
Birth City
University
Employer
Nagor
Empleyer
Major
2.49
5.24
7.00
8.38
18,00
20.54
$2.5M
57
123
227 PM
252
344
5,38
7,08
8.2M
11 9M
16 gld
00.56
33
39 d1d
50 pta
57 7.224
2n9 4M
123 dM
202 227 227.74
SM
25.88
Parraeterry
Modal She (Pa amaters)
Figure 8: Accuracy of different properties across varying model sizes. The left panel shows the results under the uniform setting, while the right panel corresponds the power-law setting. In both cases, model accuracy across properties exhibits heterogeneity -ie.., models prioritize certain properties over others. However, the trend differs: under the power-law setting, accuracy improves gradually across all properties as model size increases, whereas the uniform setting displays a sharp phase transition-accuraay remains low until critical model size is reached, after which it rapidly improves.
cnstibution-rattenn than uniform-ma may ensure partial acquisition of salient knowledge, rather than risking complete failure learn under uniform allocation.
Instruction Fine- Tunnng We investigate how different instruction tuning strategies affect knowl- edge retention and acquisition under varying model capacities. We use uniform distribution this experiment. Based on shared pretrained model, we inject new knowledge using both Supervised Fine-Tuning (SFT) and Continued Pretraining (CPT), mixing 80% of the original pretraining data to mitigate catastrophic forgetting following [10]. The underlying pretrained model is trained to 50%, 90%, 100%, and 120% of its maximum capacity.
101
knowledge
SFT new knowledge
Validation Loss
10a
1.5
2.0
3.5
Epoch
Figure 9: Training loss comparison between SFT and CPT. Due to format differences, SFT initially exhibits a higher loss.
While both SFT and CPT achieve perfect accuracy new knowledge across all settings, they differ how well they preserve prior knowledge. As shown in Table SFT suffers from more severe forgetting, particularly in models trained at or beyond capacity (100% and I 120%), where old accuracy drops significantly. This degradation is likely due format-induced syntactic overhead in SFT, which consumes model capacity and leads to abrupt loss spikes (Figure 9). In contrast, CPT introduces new
37

---

Table Accuracy on old and new knowledge after instruction tuning. New knowledge is learned equally well by both methods, but old knowledge is better retained with CPT, especially when the model near or beyond capacity.
Accuracy Old Knowledge (%)
50%
90%
100%
120%
SFT (on old)
100.0
93.25
89.9
78.5
SFT (on new)
100.0
100.0
100.0
100.0
CPT (on old) 99.6
96.5
94.5
85.1
CPT (on new)
100.0
100.0
100.0
100.0
knowledge more seamlessly, resulting in more stable loss and better retention previously learned content. Interestingly. for under-capacity models (e.g., 50%), the difference is negligibe--uuggsstnng that forgetting primarily emerges when the model's capacity is saturated.
Table Model Configurations with Parameter Counts
Model Size
Layers
Heads
Emb Dim
Params (M)
6xs2
64
3.4
6xs
80
4.3
5xs
4
96
5.2
5xs2
112
6.1
5xsl
3
4
128
7.0
4xs
128
7.2
4xs2
4
4
144
8.2
4xsl
192
11.4
3xs
4
192
11.9
3xs2
224
14.3
3xsl
4
256
16.8
XXS
256
17.6
XXS3
288
20.5
XXS2
352
26.6
XXS4
416
33.4
XXSl
8
448
37.0
448
39.4
Xs3
8
448
41.8
xs2
512
50.9
xsl
8
512
54.1
10
512
57.2
s3
10
704
94.9
s2
768
109.4
sl
11
12
768
116.5
base
12
768
123.6
m5
12
16
896
160.7
m4
1024
202.5
m3
13
16
1024
215.1
m2
14
1024
227.7
ml
15
16
1024
240.3
m
16
1024
252.8
G.3 Real-world Data Validation
To validate the applicability of our theoretical framework to real-world scenarios, we conducted a series of experiments. We employed the same model architecture used in the synthetic data experiments and pre-trained our models on the large-scale Fineweb-edu dataset. We then analyzed and fitted the data scaling law and model scaling law observed during training. Furthermore, we evaluated the models' grasp of factual knowledge using the PopQA dataset, popular question-
38

---

180
311
330
3.00
342
0.0
022
040
033
036
033
333
30.M 301M 20
18,80
04,30
67 12 3.5
24
Figure 10: Experimental validation on real-world data. (a) Data scaling law on Fineweb-edu: Validation loss as function of training data size. The fit indicates a power-law relationship, consistent with a power-law distribution of knowledge in the dataset. The estimated exponent for this power-law distribution of knowledge is between 1.35 and 1.5. (b) Model scaling law on Fineweb-edu: Validation loss as a function of model size. The plot shows a power-law decrease in loss with increasing model parameters, and also suggests a substantially larger irreducible loss component for natural language compared to synthetic data. (c) Knowledge cutoff on PopQA: Model performance (e.g., accuracy) on PopQA questions, categorized by the frequency of the underlying knowledge in the Fineweb- edu training set. Smaller models exhibit a clear inability to answer questions about low-frequency knowledge, while larger models demonstrate improved performance on rarer knowledge, effectively lowering the frequency cutoff for knowledge acquisition.
answering benchmark focusing on long-tail knowledge. In our PopQA experiments, we used the object popularity (o-pop) of a knowledge item in the training set proxy for its frequency.
By comparing the empirical exponents from the data and model scaling laws on Fineweb-edu against those from our synthetic experiments (which were generated using knowledge distributions with varying underlying power-lay exponents, see discussions surrounding Figure 3 and Figure 4 we infer that the knowledge distribution in Fineweb-edu is effectively characterized by a power-law exponent between 1.35 and 1.5. This observation provides potential estimate for the exponent range of real-world knowledge distributions and is consistent with the priors in our theoretical model (e.g.. Assumption 4.4). When fitting the model scaling law, we observed that the inherent irreducible loss for real human language (English, in this case) is considerably larger than that observed for synthetic language. This is intuitive, as the complexity and inherent stochasticity of natural language far exceed the synthetic setting, Note that the irreducible loss values derived from the model scaling law and the data scaling law differ due to our finite model and dataset sizes. In practice, the observed loss can be expressed as L = (D/D)) fixing data size), the estimated irreducible term effectively includes the data- data-dependent component, i.e., (D/Do) Do) + e; similarly, when fitting the data scaling law, the irreducible loss includes the model-dependent term, MM) + In other words, the discrepancy in irreducible loss arises from the limited model size or data size in each respective setting.
+ (M/Mu) -8 E, so when fitting the model scaling law (by
Tests on the PopQA dataset further illuminated the characteristics of knowledge acquisition in real models. Consistent with findings from our synthetic data experiments (see Figure b) and discussion around Figure we observed a "knowledge cutoff" phenomenon in real models as well. Specifically, even with sufficient training, smaller models struggle to learn knowledge that appears with low frequency in the training data. As model size increases, they become capable of learning knowledge at progressively lower frequencies.
H Omitted Proofs
H.1 Properties of Pitman-Yoo Mixture Model
Lemma H.1 (Theorem 4.3 in (55). The mixing weights p = (p1, P2....) PYCRP(a, B) can be represented as a stick-breaking process:
j-1
Pj = W, II WT).
i=1
where Ws are independent and W,- Beta(1 3 1 ia).
39

---

Lemma H.2 (Theorem 3.13 in (551). Let p
(pI.P2....) ~ PYCRP(a, B) be the sequence of
mixing weights drawn from a Pitman Yor process. Then, the following limit almost surely exists:
Sa,
lim 11/op:
1-000
Lemma H.3. Denote the remaining stick length of the stick-breaking process in Lemma H.1
3
Len: = II W;)
Σ
Pe.
1=1
i=
Then the expectation of the remaining stick length satisfies:
E[Len,] = O(n'-1/110
Proof. Since W Beta(1 a, B ia), know that
3 ia
B 1+ 3+ 1)-1)a
Morcover, W2 are independent. Thus we have
5 + ia
I (3 + +ia)
E[Lenn]
+
B
+
(i
1)a
T + 8 (i- 1)a)
1=1
at
(2 +i
1' + 1 +
1+8
α² I
1+0 +1)
+
12 + 1+0
r
n + 1+ -
r
1+8
C.
where C=
n 1+8
r (1
Then by Stirling's ss approximation, know that that B(Len,) (n 11/a).
H.2 KL.-divegencce of Mixtures
Lemma H.4. Let Φ Σ Pro0,, 0 Σ g:ó0; be two mixtures. Then we have
DKL (Po(:)))lPP(()
Σ Pt log Pt
qi
Proof. By the log-sum inequality, we know that
Σn PiPo
DN((P()))(P((E))
Σ
Σ pr Po.
log
Ei= (x)
PiPo. (z) qiPo (x)
PiPo. (x)
log
1=1
Pi + Σ (Po, (x)
P4 log
4i
H.3 KL-divergence and Fisher Information
Definition H.5 (Fisher Information). Let X be random variable with probability density function (PDF) (x). The Fisher information given by:
(c0 log Po(x)) 27
0 00
82
J(Ø) = Ex
= -Exx
log Po Px
Ogg
40

---

Lemma H.6 (Exercise 11.7 in [3]). For a parametric family {Po(z)} that
DKL 00 0'yz J(0)(0
lim
2
Proof. We provide proof for completeness. We perform a second-order Taylor expansion of the KL divergence with respect to its second argument 6', around the first term B.
(o(x)
DKL DKL (PollP6)) Lo
log
Po (x)
Pg (0- V'Vo log P
-0 0''² log Po 0¹) + 617²)
Ep [00 - 0') V log Po|
2 Ea Po [00 '' log Po(0 - 0'] + o(10 0'
(0 8' 1 Pa. Vo log Po]
2 Ez V Po| (0 0') o 8'2²)
(0 0' Ti Vo log Po]
(0 0²)²² J()) o(10 0
The first-order term (0- D' Vo log Po] since the KL divergence attains its minimum value of zero at 0' = 0.
Thus know that
DKL Poo
lim
(0 0') J(0) -0)
Remark H.7. The conclusion of this lemma indicates that the Assumption 4.1 essentially analogous to requiring the Fisher Information of the distribution common in related literature. For instance, Conditions I and 4 in (T7) impose similar requirements. Notably, MT also points out that these assumptions are widely satisfied within a class of exponential family distributions.
to be bounded. Such assumptions are
H.4 Proofs of Section 4.2
Theorem H.8 (Restatement of Theorem 4.2 Under the Bayesian sequential prediction framework and Assumption 4.1 the averaged optimal Bayesian redundancy (per sentence) of the hierarchical data model Adan satisfies:
= I(XINN; Pdana) = 6 dkmw
1
ngdleyn
inf M N
Red (M, & ddma)
N
NI-a
N
Proof. We use the index of resolvability approach similar to 6 to prove the theorem, by constructing a covering the parameter space in terms of KL-divergence. However, we cannot directly apply the conclusion, as we are unable to explicitly construct a KL-divergence covering for P Pow.. Instead, we can construct set of probability distributions Q such that, for every specific diata E & there exists Q @ satisfying DKL (Pama (Q) I ((oau), where f ((esa) is a value dependent on Odaua-
Define the KL-covering number of the probability family P and the La norm covering number of the parameter space & as:
Na(e, P) = inf n E I3Qi i= I..... n, sup min Da(PIIQ.) s }
PEP
NL. ②) == inf
n EEE i 1.... n. sup min 11 2s1l2 Se
o
41

---

We first construct KL-divergence coverings for the probability families Pa... and P..... as well as KL-divereence covering for the n-dimensional discrete simplex. We subsequently construct point-wise approximate covering set Q for Pa based on these coverings. By Assumption 4.1 we know that
Ma,c, Po..) S N Tuyn: Pynn) and Na Po ) &NL /egle///ama kkow):
Then we consider the 1.2 norm covering number of the parameter space 4 Psyn- We simply divide each
coordinate into 220yg dhin equal parts. It is easy to that this results in Le covering of the parameter space with a resolution of approximately
Lugn
Thus we know that
dag
2T dayn
Nale, Pann) S (L Layn: syn S
Similarly, we know that
Nii Pa k v dxaw
deru
Next, we consider a KL-covering the n-dimensional simplex.
Denote Pn = {(PI.- ... Pnnl:Pi 2
0,
Σ
pi
=1. Consider the discretization of the simplex
1=1
On,e = ((g..... (n/ell/ee]e/ q. e N
qi = 1}.
prove that Qn is an 2 K-LL-coveiing Then any (p1, ... ,P)) Pus there exists
(gr.""" .nn) 2n such that lp: - 4: S Therefore, we know that
Pi log
Pe q.
(ps 9:)
2
111 4i
Note that simple upper bound for 12nel is 1nnel S 1n/22 For notational simplicity, we denote
Tlan 2Lyy dayn
dyn
2knk v dkow
dume
as upper bounds on the e e-LL-covgiing numbers of P and Parmm. respectively. Assume that distributions
{Ql)) (E)..... Qayn (E))
form an <-KL-covering P pay. and distributions
(Q (L) (K) (m (x))
form an e- e-KL-coveeing of P mm Let m [ denote the truncation point used subsequently in
the truncated estimation of P a joint distributions over knowledge element & and syntax element ş. A distribution Q {) E Q if and only it satisfies all of the following conditions:
Then we construct the covering of P Denote by the set of
There exist q (qi,..., 4m)+) Qm+ 1,e and indices ki,..., kim such that
Q(k)
Σ gi Ahh + 4m++1Qu Q
(ks)
where Qu is the uniform distribution over the support of knowledge element IK.
There exist indices 81,..... 8n,, such that for each E [1,...,,..)
Q K E K,) = (+.)
where K, is the set of knowledge corresponding to the syntax model 6sy..
42

---

Next we prove that, for any Prima E Pa we have that
min DKL (Ka(Pan (K., ())))((,,)) S Lenm log |K| + 36 QEQ
where Leny Σ
Pj is the remaining stick length of kknw (See Lemma H.3 1
We rewrite kknw as:
Σ p.og, Len
knw
where d' Lenm i=m+1
Σ p.o By the definition of Q, there exists distribution Q" Q such that
(*)x)= = Σ
v Q + tm+
(K;)
Q' K K.) = Quy
and Q* satisfies the following three conditions:
-DKL (Po, (x))( (kt) S 22 for all 1 sis m.
(k)))
Ep.
Ps log P: + Len log
Lenm < 2 am+1
1=1
(K ca (4) (E)) S e for all S S n..
Then by the chain rule of Kl.-divergence and Lemma
H.4 we know that
DKL (P (Porm (rs, E)1 (k., E)) =DKL (P dumn (m=]ll²(<x)) + Ex [KLL (Pon (EIx))))))))
Pi Σ ps log
Lenm log
Lenm + amm
Σ
DrDKL (1))))))) (m))
i=1
+ Lenn DKL (Par (Q((k)))))
Σ
P(x E K.) (Poce (0)) (E)) (E))
<e² + Die Lenm log [K| +
P(N E K2:)²²
i=1
<3e² Lenn log
K
Subsequently, we derive an upper bound for the associated covering number. We know that Q s
Qm I nh That is to say
log Q < log 1mm- + log Tkkow + log Plyn
m
+ mdxaw log Laww + n.dyn log Laya
< 2m log =
43

---

Finally, we prove the conclusion in this theorem. Consider Qo = [Q. redundancy follows:
E Q. We can bound the
QEO
inf Red N (M, d dama
<Red (Qo,
Panta)
P(odtna) DKL (P (hem
11
M
P. QN
P(odata I
log
+ log QQI
d
4aau
QEQ
PN Pida
< <lgg| [2] +
P(odaul) )E
log
depaat
max QN QEQ
P Poran
< <log [2] + N
P( min
log
dodma
QEO
= =log| |2] + N
P(oaau) min DKL (Poau (laall1))dee dQQ)a QEO
< log [2] + N
(Len log |K| + 2
Pan
= log Q + 3 + NE( log |K
Plugging in the bound of [ and K, we can see the above is upper bounded by
[e[ log K + 3Ne 2m log m +
2md2aw log L + nyddyn log
Lyy
Choosing = N-1 and applying the result in Lemma H.3 we know that
inf Red [M, Pdtta) S O5NN M
K + (log N + log Lkww + log daaw)) )))
+ On, (log Lyyn + log dayn + log N)).
Therefore, we know that
1 I(XI:N: Paau)) =ō danw
n. nydayn
inf N Red (M, Pdnaa)
(Ni-a N
N
This completes the proof.
44

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: In this paper, derive theoretical results corresponding the empirical
scaling laws. Experimental validations further support our theoretical findings.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: See Section 5
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
45

---

Justification:
See Appendix
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: All theoretical results are supported by detailed experimental validation.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
46

---

reproducible, they Answer: [Yes]
Justification: This paper provides a thorough theoretical analysis, complemented by exten- sive empirical validation conducted under standard settings. The complete source code will be released publicly to ensure full reproducibility.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (ittpss//nips.cem cc/
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
7 7/nips. http://ubbccggg.dde/deeeeeeiiiie
sssoobiiiiiioooooocoococo for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: Our experimental setups described in detail in the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Standard experimental methods are used, with detailed descriptions provided in the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
47

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors Is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: While our work is primarily theoretical and the computational demands modest, all experiments were conducted on single machine equipped with 8 NVIDIA GeForce RTX 3090 GPUs, each with 24GB of memory. The entire experimental process took approximately two weeks, with each individual experiment taking about hours on average.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https::/neurrpp.. wwwpeeurrrss.cpp.uoeoooe http://ppppp.ppopuoo/occcccaaaaa
Answer: [Yes]
Justification: The research conducted in the paper conforms, in every respect, with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
See Section
S
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
48

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our work is primarily theoretical.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We provide experimental details and properly credit the original creators owners of all assets.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
49

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, datasets.paperssiii wwwppppppttthhhooo thcode www.coo//aaaaao datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: Our work is primarily theoretical.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our work is primarily theoretical.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: Our work is primarily theoretical.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
50

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: LLM is used only for writing, editing, formatting purposes this paper.
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https: httppp//eearrrssscc/o//eeeeeeeep cc/COonferrnnnee/2225LLLL for what should or should be described.
51


Reviews:
[{"review_id": "fQY8Vop1rv", "reviewer": "Reviewer_Da6R", "summary": "This paper presents a theoretical framework to understand the behavior of Large Language Models (LLMs) under computational constraints. It introduces a Bayesian model that separates syntax and factual knowledge learning, explaining how LLMs scale with data size and model capacity. The paper also derives scaling laws for knowledge acquisition, redundancy reduction, and loss decomposition, supported by empirical experiments on synthetic and real-world datasets.", "questions": "1. How realistic are the assumptions of conditional independence between knowledge clusters given the model? Are there empirical studies or experiments supporting this?\n2. While the paper includes experiments on real-world data (e.g., PopQA), how well do the theoretical predictions hold when applied to more diverse or complex tasks beyond fact-based QA?\n3. Given the focus on large-scale models and data, what are the computational implications of the proposed framework? Can it be efficiently implemented or approximated in practice?", "limitations": "yes", "rating": 4, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strength：\n1. The paper offers a novel Bayesian perspective on LLM learning dynamics.\n2. The theoretical results are backed by extensive experiments on both synthetic and real-world datasets (e.g., PopQA).\n3. The paper is well written and organized.\n\nWeakness:\n1. While theoretically insightful, the paper lacks concrete guidance on how these findings can be applied to improve practical LLM training or deployment strategies.", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the positive feedback and valuable suggestions! We are very glad to address the questions and suggestions raised by the reviewer, which we believe will help further refine our work. Below are our responses to the questions and suggestions raised by the reviewer.\n\n[**W1**] While theoretically insightful, the paper lacks concrete guidance on how these findings can be applied to improve practical LLM training or deployment strategies.\n\n[**R1**] We thank the reviewer for the constructive feedback regarding the practical applicability of our theoretical insights. Our theoretical framework provides a more nuanced characterization of scaling behaviors than existing scaling laws (e.g., Chinchilla). Specifically, we establish frequency-specific loss predictions across model scales and reveal size-dependent learning bottlenecks related to knowledge frequency(Figure 1 and Figure 2). These theoretical contributions can yield implications for model size-aware data curation strategies. More specifically, our findings imply two strategies for optimizing pre-training data curation: First, for fixed model capacity, data with frequency below a model-size-dependent threshold is fundamentally unlearnable. Our theoretical analysis proves such patterns cannot be learned regardless of training duration, making this computationally wasteful. Second, for high-frequency data sources, strategic downsampling can improve computational efficiency, as high-frequency patterns are learned quickly and provide diminishing returns, freeing up FLOPs for a broader range of knowledge. However, consistent with our paper's primary focus on fundamental insights, we defer operational aspects of training improvement to future work.\n\n[**Q1**] How realistic are the assumptions of conditional independence between knowledge clusters given the model? Are there empirical studies or experiments supporting this?\n\n[**A1**] We thank the reviewer for the rigorous examination of our data model's conditional independence assumption. We would like to clarify that the conditional independence assumption pertains specifically to our knowledge model, which generates factual knowledge (such as personal information like birthdates, birthplaces, etc. in our synthetic data experiments). We maintain that this assumption is well-justified for factual knowledge representations. As acknowledged in the ”Concluding Remarks“ section, we also have stated the limitations of factual knowledge representations and outlined potential extensions like \"compositional reasoning and inference mechanisms\" (Lines 324-327). \n\n[**Q2**] While the paper includes experiments on real-world data (e.g., PopQA), how well do the theoretical predictions hold when applied to more diverse or complex tasks beyond fact-based QA?\n\n[**A2**] We thank the reviewer for the excellent question regarding the generalizability of our theory. We hypothesize that our core findings would extend to other knowledge-intensive tasks, such as those in benchmarks like MMLU, where the acquisition of concepts can also be modeled as a process of compressing information with power-law frequency distributions. However, for tasks that rely heavily on complex, multi-step reasoning or mathematical logic, our current model would likely be insufficient. These domains involve procedural and compositional knowledge that cannot be captured by our current assumptions. As we state in our conclusion, integrating more complex structures like \"compositional reasoning and inference mechanisms\"  into our theoretical model is a crucial and exciting direction for future work.\n\n[**Q3**] Given the focus on large-scale models and data, what are the computational implications of the proposed framework? Can it be efficiently implemented or approximated in practice?\n\n[**A3**] We thank the reviewer for the inquiry regarding computational implications. To clarify, our work does not propose a new training framework. Rather, our work adopts a data-centric perspective, using information-theoretic tools  to characterize the power-law properties of data distributions. Within this framework, we analyze the redundancy bound of the Bayesian optimal predictor—abstracting away model architectures and optimization algorithms to isolate how data structure fundamentally drives scaling behaviors. Our insights into computational implications are also based on data curation, which we have already presented in R1."}, {"review_id": "aZ6RHosUPS", "reviewer": "Reviewer_VRwY", "summary": "This paper provides a theoretical framework for understanding LLM behaviors through the lens of compression and Kolmogorov complexity. The authors interpret LLM training as a two-part process using the Kolmogorov Structure Function, where models first learn frequent syntactic patterns then gradually acquire rare knowledge. They introduce the Syntax-Knowledge model, a hierarchical data generation framework that separates the language syntax (ie. rules, parametric model) from factual knowledge (non-parametric Pitman-Yor Chinese Restaurant Process). Under Bayesian assumptions, the paper derives both data and model scaling laws: data scaling follows O(N^(α-1)) for knowledge and O(N^(-1)) for syntax, while model scaling shows that larger models progressively learn lower-frequency knowledge. The theory predicts that models will hallucinate knowledge below frequency thresholds due to capacity constraints. Experiments on power-law distributed synthetic datasets validate these predictions, and the authors make predictions on adequate data distributions.", "questions": "Q1: Is it possible to literally show the scaling law plots (loss vs flops(compute) to see if the scaling laws actually work?\nQ2: The paper doesn't rely much on the transformer architecture. *imaging* llms were just dense mlps, when would these findings hold? Does the finding assume that the architecture is \"good enough\" to \"implement\" this two part coding process?", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "S1: This paper is very well written. Despite the theoretical complexity of the data and their model, everything is very clearly described and easy to follow.\n\n\nS2: This paper demonstrates a very clean model explaining neural scaling laws established in language models. There have been past efforts to model neural scaling laws with synthetic data, but most of them didn’t fit the single epoch online nature, or didn’t explicitly include complexities from syntax and knowledge. This paper beautifully integrates both parts and makes clean predictions.\n\n\nS3: Nice juxtaposition of theory and experiments. The paper cleanly displays theoretical findings and experimental validation.\n\n\nS4: The paper makes a prediction based on their analysis that “it can be advantageous to have power law distributed data” for a well justified reason.\n\n---\n\nW1: While neural scaling laws are discussed, it would be nice to literally show the scaling law plots of compute vs loss predicted by theory and ran by experiments. This, for me, is the main asset missing.\n\n\nW2: The data generation process can be better illustrated visually to help understanding.\n\n\nW3: It would be good if the paper could be further grounded to the real LLM world, explicitly mention what kind of data distributional choices can be made: e.g. English vs other languages in pretraining, etc.", "was_revised": true, "final_justification": "The authors rebuttals were satisfactory!\n\nI will maintain my positive score of 5.", "rebuttal": "We sincerely thank the reviewer for the positive feedback and valuable suggestions! We are very glad to address the questions and suggestions raised by the reviewer, which we believe will help further refine our work. Below are our responses to the questions and suggestions raised by the reviewer.\n\n[**W1**]While neural scaling laws are discussed, it would be nice to literally show the scaling law plots of compute vs loss predicted by theory and ran by experiments. This, for me, is the main asset missing. \n\n[**R1**]We thank the reviewer's suggestion regarding compute-optimal scaling plots. First, we would like to recall that the scaling law takes the form $L=L_0+AN^{-\\alpha}+BM^{-\\beta}$. Because our theoretical analysis is asymptotic, the multiplicative constants A and B cannot be precisely quantified. While we can derive approximate compute-optimal configurations of data size N and model size M in the asymptotic regime, ignoring the practical significance of constants A and B would risk substantial prediction errors. We therefore find empirical characterization more meaningful for studying compute-optimal scaling laws. Moreover, we include the experimental part of this question in our answer to Q1.\n\n[**W2**] The data generation process can be better illustrated visually to help understanding.\n\n[**R2**] We thank the reviewer for the valuable suggestion. We would like to highlight that Figure 7 in Appendix D provides a schematic visualization of the data generation process, supplemented by concrete implementation examples (Example D.1). Space constraints required moving the schematic visualization to the appendix, and we will integrate it into the main text if revision space becomes available and refine the visualization to include more details.\n\n[**W3**]It would be good if the paper could be further grounded to the real LLM world, explicitly mention what kind of data distributional choices can be made: e.g. English vs other languages in pretraining, etc.\n\n[**R3**]We thank the reviewer for this valuable suggestion, as our framework offers direct insights into data curation. Our findings imply two strategies for optimizing pre-training: First, for fixed model capacity, data with frequency below a model-size-dependent threshold is fundamentally unlearnable(Figure 2). Our theoretical analysis proves such patterns cannot be learned regardless of training duration(Theorem 4.6), making this computationally wasteful. Second, for high-frequency data sources, strategic downsampling can improve computational efficiency, as high-frequency patterns are learned quickly and provide diminishing returns, freeing up FLOPs for a broader range of knowledge.\n\n[**Q1**] Is it possible to literally show the scaling law plots (loss vs flops(compute) to see if the scaling laws actually work?\n\n[**A1**] We thank the reviewer for this suggestion. While the current rebuttal rules preclude adding new figures, we will gladly include a direct loss versus compute (FLOPs) plot in the camera-ready version to make this relationship explicit. For now, we wish to clarify that the necessary components of the scaling law are already presented. Figures 3 (loss vs. tokens trained) and 4 (loss vs. model parameters) are generated from the same set of model training runs. Since the number of tokens trained is directly proportional to computational flops, these two figures jointly confirm that our experimental results align with established data and model scaling laws.\n\n[**Q2**] The paper doesn't rely much on the transformer architecture. imaging llms were just dense mlps, when would these findings hold? Does the finding assume that the architecture is \"good enough\" to \"implement\" this two part coding process?\n\n[**A2**] We thank the reviewer for the thoughtful question about architecture-agnostic implications in our methodology. Our theoretical analysis operates under the optimal predictor framework,  abstracting away from implementational constraints like specific architectures (Transformer/MLP) or optimizers (Adam/SGD). Analyzing training dynamics under fully realistic settings(incorporating data distributions, model architectures, and optimizers) is intractable. We posit that data's power-law structures fundamentally drive scaling laws' behaviors, as empirically substantiated in Figures 3 and 4. Consequently, we employ a data-centric theoretical framework, analyzing the redundancy bound of the optimal predictor. We hope that future work can systematically incorporate these implementation-level considerations."}, {"review_id": "SROqe7Qsg9", "reviewer": "Reviewer_dW7Z", "summary": "Motivated by classical theory results, the paper presents an abstract model for language models that can be used to explain how and what models learn, why scaling laws exist, and hallucinations. They provide both theory (with various assumptions, including on how the data is sampled) and experiments to verify the theory.", "questions": "1. In figure 3a, I worry a little that the uniform data seems to follow a (admittedly steep) power law curve for all but the two largest data points, so could it be the case that the power law predictions for the other data will break for large enough models in a similar fashion?\n2. In figure 4a, I noticed that the blue data seems to almost be subtly following a similar trend as the data for the uniform setting, have a slight plateau at the end. Is there a sense in which the uniform setting is the limit as the power goes to 1 (or is this just me reading too much into noise)? If so, could this be used to gain an understanding of the uniform setting?\n3. Could this framework be applied to non-language models? Should the results extend to, say, image models?", "limitations": "The paper could spend a little more time discussing the limits of the assumptions on the data, and possibly discuss the limitations of abstracting away architecture and optimization.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The paper gives a good balance of technical explanation and discussion of the results. It has robust theory and toy experiments to support its theory. The experiments do an adequate job at supporting the theory, validating predictions while showing that when assumptions are broken those predictions fail, which is decent evidence that the theory is meaningful.\n\nThe paper is rather dense on definitions and notation, but its unclear if this is possible to substantially improve.\n\nThe results apply in a somewhat limited setting, where the data must be constructed in a fairly artificial manner, and inductive biases/details of optimization are not considered. But considering the difficulty of theory in deep learning, these weaknesses are acceptable.", "was_revised": true, "final_justification": "The authors rebuttals are clear and address all of my questions. The paper provides more theoretical understanding of an important phenomena (like scaling laws) with experimental validation, a good contribution for deep learning theory.", "rebuttal": "We sincerely thank the reviewer for the positive feedback and valuable suggestions! We are very glad to address the questions and suggestions raised by the reviewer, which we believe will help further refine our work. Below are our responses to the questions and suggestions raised by the reviewer.\n\n[**Q1**]In figure 3a, I worry a little that the uniform data seems to follow a (admittedly steep) power law curve for all but the two largest data points, so could it be the case that the power law predictions for the other data will break for large enough models in a similar fashion?\n\n[**A1**]  We thank the reviewer for the sharp observation and apologize for the potential misunderstanding caused by the visualization in Figure 3a. A power-law relationship of the form loss $= A x^{-\\alpha} + \\epsilon$ appears as a straight line on a log-log plot only after the irreducible loss $\\epsilon$ is subtracted. The plot shows raw validation loss, and as the fitted equations in the legend indicate, the irreducible loss ε is different for each power-law distribution. This is why the curves are not perfectly linear. We can confirm the fits are statistically strong, with R² values exceeding 0.98 for all power-law regressions. In contrast, the data from the uniform distribution fundamentally deviates from this scaling behavior and cannot be fitted to a power law, which is the key distinction we aimed to illustrate.\n\n[**Q2**] In figure 4a, I noticed that the blue data seems to almost be subtly following a similar trend as the data for the uniform setting, have a slight plateau at the end. Is there a sense in which the uniform setting is the limit as the power goes to 1 (or is this just me reading too much into noise)? If so, could this be used to gain an understanding of the uniform setting? \n\n[**A2**] We thank the reviewer for the insightful question. The reviewer is correct to point out the subtle plateauing for the Power=1.20 data at the largest model sizes in Figure 4a. This effect, however, is an artifact of our experimental setting having a finite dataset, rather than an indication that the power-law scaling is converging to the uniform case. In this experiment, we fix the total data while increasing model size. As the model becomes sufficiently large relative to the fixed amount of knowledge in the dataset, it begins to saturate its ability to learn from that data, causing the loss reduction to plateau. In real-world, large-scale scenarios, the dataset is typically vast and scaled with the model, meaning the model rarely runs out of new information to learn from the data's long tail. Therefore, the uniform setting should be viewed as a qualitatively different regime, not as a limit of the power-law case in our framework.\n\n[**Q3**] Could this framework be applied to non-language models? Should the results extend to, say, image models?\n\n[**A3**] We thank the reviewer for the insightful question. Our theoretical framework's high-level guidance – the compression-prediction duality (Appendix B, C) – is model-agnostic. We focus on language models due to (i) empirically validated power-law structures (e.g., Zipf's and Heap's laws) in natural language, and (ii) this domain's established scaling law research foundation. If image data exhibits power-law structures resembling those in natural language, similar scaling behaviors may emerge. However, modeling these structures in visual domains currently poses significant challenges beyond our theoretical scope. This possibility remains an interesting direction for future work.\n\n\n[**L1**] The paper could spend a little more time discussing the limits of the assumptions on the data, and possibly discuss the limitations of abstracting away architecture and optimization.\n\n[**R1**] We thank the reviewer for the constructive suggestion regarding the discussion of limitations. As acknowledged in ​​the” Concluding Remarks“ section, we have stated the limitations of our data model and outlined potential extensions like \"compositional reasoning and inference mechanisms\" (Lines 324-327).  ​​Our work adopts a data-centric perspective, using information-theoretic tools to characterize the power-law properties of data distributions. Within this framework, we analyze the redundancy bound of the Bayesian optimal predictor—abstracting away model architectures and optimization algorithms to isolate how data structure fundamentally drives scaling behaviors. We will add a discussion of this data-centric perspective in the camera-ready version to further clarify its implications."}, {"review_id": "HU7XWwR2pJ", "reviewer": "Reviewer_wrDk", "summary": "This work proposes an interpretation of LLM compression as a two-part coding process. Grounded with information theory concepts, the authors propose a syntax-knowledge model as a synthetic data generation model, and derive that the lower bound of the averaged optimal Bayesian loss follows a power-law scaling with respect to the data size. The authors also provide a theoretical analysis of model scaling laws, providing insights into LLM behaviors on factual knowledge acquisition.", "questions": "Please see the questions in the weakness section.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n- S1: The newly proposed syntax-knowledge model provides a synthetic testbed for understanding factual knowledge acquisition dynamics, which can be adopted for other studies\n- S2: The framework explains several widely observed phenomena very well, and the predicted trends are verified with solid and large-scale experiments. The insights on the connection between information theory concepts and power-law scaling is impressive\n- S3: The core claims are supported with mathematical rigor, and the concepts are explained in great detail (although I'm not very familiar with advanced information theory concepts, and I couldn't verify the correctness of the derivations and proofs)\n\nWeaknesses\n- W1: Although natural language is compositional, and the proposed syntax model itself doesn't inform how different syntactic structures are correlated or interact. As shown in Table 1, the generated synthetic dataset consists mainly of 'simple' statements, which can be essentially reduced to the (entity1, relation, entity2) format. Hence, the logical connection between the theoretical explanation of the scaling law and practical observations is limited to the acquisition of simple factual knowledge. Another point is that PYMM is one of many possible algorithms that can lead to a Zipfian pattern, which might significantly differ from natural language.\n- W2: The central theme of 'LLMs are compressors' itself is not completely novel, although I believe the novel conceptual contributions are clear (e.g., the prediction of scaling laws). I think this can be more sharply discussed in the main text (e.g., comparison with Tishby's information bottleneck analysis on NNs and how this framework distinguishes from former analyses).\n- W3: While the high-level flow is clear, I think some details should be more clarified in the main text (although some of them are resolved in the appendix): (1) $d_{knw}$ and $d_{syn}$ are used without definition in L215-217. What do they mean? (2) In Figure 3a (4a) and 3b (4b), the x- and y-axis labels and ticks are confusing. Although all axes seem to be on a log scale, it is specified in the axes label only in 3a (4a). (3) $\\zeta$ is not defined in L262. (4) It is unclear exactly how the syntax model is constructed to give the actual dataset in Table 1. (5) Although the Kolmogorov structure function perspective is highlighted in the introduction section as one of the main contributions, the intuition is not discussed in the main text.\n- W4: The trendline for Fig.3(a) does not seem to be a linear fit on the log-log plane (which should be linear, either the authors fitted the raw data with or without linearization), although the authors claim the experimental results follow a power-law trend.", "was_revised": true, "final_justification": "The authors have clarified most of my questions and concerns, including (1) the clarification of this work's main contribution (2) the choice of PYMM for modeling the factual knowledge aspects in natural language, and (3) technical sides on paper presentation. I believe this work provides a valuable theoretical foundation for understanding the dynamics of factual knowledge acquisition in LLMs, which have not been fully explored in the field yet. I am happy to increase the score by 1, recommending acceptance.", "rebuttal": "We sincerely thank the reviewer for the positive feedback and valuable suggestions! We are very glad to address the questions and suggestions raised by the reviewer, which we believe will help further refine our work. Below are our responses to the questions and suggestions raised by the reviewer.\n\n[**W1**] Although natural language is compositional, and the proposed syntax model itself doesn't inform how different syntactic structures are correlated or interact. As shown in Table 1, the generated synthetic dataset consists mainly of 'simple' statements, which can be essentially reduced to the (entity1, relation, entity2) format. Hence, the logical connection between the theoretical explanation of the scaling law and practical observations is limited to the acquisition of simple factual knowledge. Another point is that PYMM is one of many possible algorithms that can lead to a Zipfian pattern, which might significantly differ from natural language.\n\n[**R1**]We thank this critique regarding our modeling choices. We acknowledge that we focus exclusively on factual knowledge acquisition, and the syntax model represents some templates in our current synthetic data experiment. However, our syntax model is a general parametric framework capable of representing probabilistic context-free grammars and other syntactic structures. The whole data model is more general than the examples in the synthetic data experiment: it generates abstract knowledge elements, which a syntax model then encodes into sentences. Crucially, we only require a theoretical one-to-one mapping between each sentence and its (knowledge elements, syntax elements) pair to preserve information—without needing to specify the actual encoding process(Appendix D, Figure 7 and Example D.1). We also recognize the importance of extending this framework to handle compositional structures as a significant future direction(Lines 324-327). Our theoretical analysis intentionally employs the PYMM framework, and the direct Zipfian pattern assumption remains valid and methodologically efficient for studying data scaling. The choice of PYMM stems from PYMM's inherent \"preferential attachment\" mechanism for table(cluster) formation, which we believe is more representative of fundamental natural language phenomena than  Zipfian distributions. Actually, the fact that the data generated by PYMM exhibits Zipfian pattern properties is what we use to substantiate that PYMM conforms to natural language rules.\n\n[**W2**] The central theme of 'LLMs are compressors' itself is not completely novel, although I believe the novel conceptual contributions are clear (e.g., the prediction of scaling laws). I think this can be more sharply discussed in the main text (e.g., comparison with Tishby's information bottleneck analysis on NNs and how this framework distinguishes from former analyses).\n\n[**R2**] We thank the reviewer for the constructive suggestion regarding the discussion of additional related work. We acknowledge that the perspective of \"LLMs as compressors\" serves as our foundational framework, though our primary contributions reside in: (1) introducing a novel modeling approach for natural language data characterized by power-law frequency structures, and (2) utilizing information-theoretic tools to theoretically analyze LLM behaviors (particularly scaling laws), rather than claiming originality in the \"LLMs as compressors\"  argument itself. We have discussed related work on \"LLMs as compressors\"  in Appendix A   and provided corresponding citations. The main difference between our analysis and the former analysis is that we employ a data-centric framework. Specifically, our analysis focuses on our proposed power-law structured data framework. Consequently, it yields distinct theoretical implications compared to prior studies combining information theory with neural networks – a divergence empirically evidenced by the markedly different uniform distribution curves in Figures 3 and 4. Regarding the reviewer's reference to Tishby's information bottleneck analysis on NNs, we acknowledge that both approaches utilize similar information-theoretic tools like compression, MDL principle, etc.. We will add a detailed discussion in the camera-ready version. However, our work takes a data-centric perspective, which is novel in its focus on isolating how power-law data structures fundamentally drive scaling behaviors.\n\n[**W3**] While the high-level flow is clear, I think some details should be more clarified in the main text (although some of them are resolved in the appendix): (1)  and are used without definition in L215-217. What do they mean? (2) In Figure 3a (4a) and 3b (4b), the x- and y-axis labels and ticks are confusing. Although all axes seem to be on a log scale, it is specified in the axes label only in 3a (4a). (3)  is not defined in L262. (4) It is unclear exactly how the syntax model is constructed to give the actual dataset in Table 1. (5) Although the Kolmogorov structure function perspective is highlighted in the introduction section as one of the main contributions, the intuition is not discussed in the main text.\n\n[**R3**] We thank the reviewer's careful review of technical details. We moved certain elaborations to the appendix due to page constraints and will integrate them into the main text if space allows:\n(1) $d_{knw}$ and $d_{syn}$ were introduced in Lines 170 and 177 respectively. We will add the corresponding explanation in the theorem in the revised version.\n(2) We apologize for the inconsistent labeling. We will revise the axis labels in all relevant figures to explicitly state \"(log scale)\" in the camera-ready version to ensure clarity and consistency.                  \n(3) $\\zeta$ was explicitly defined in Line 262.\n(4) In our experiments, the \"knowledge model\" is instantiated as a database of 400,000 individual profiles whose sampling follows a power-law distribution. The \"syntax model\" is then implemented as a large collection of sentence templates—50 for each type of information—that render these facts into varied linguistic expressions. For the example in Table 1, a biography template is populated with a person's profile for pre-training, while a question-answer template is used for instruction tuning. In this way, the syntax model provides the linguistic structure and variation for the factual content supplied by the knowledge model.\n(5) The full discussion of Kolmogorov structure functions appears in Appendix C due to strict page constraints. This perspective forms important high-level guidance for our theoritical framework. However, the non-computability of Kolmogorov complexity makes rigorous theoretical analysis intractable, and since explaining its abstract structure function requires significant space, we placed related insights and definition details in the appendix due to page constraints. Should space allow during revision, we will prioritize moving this content to the main text.\n\n[**W4**] The trendline for Fig.3(a) does not seem to be a linear fit on the log-log plane (which should be linear, either the authors fitted the raw data with or without linearization), although the authors claim the experimental results follow a power-law trend. \n\n[**R4**] We thank the reviewer for their careful analysis of Figure 3(a) and apologize if the visualization was misleading. The reviewer is correct that the trendlines are not perfectly linear on the log-log plot. This is because a power-law relationship of the form loss = $A  x^{-\\alpha} + \\epsilon$ only becomes linear on a log-log scale when plotting the loss after subtracting the irreducible error, $\\epsilon$. Our figure plots the raw validation loss, and as the fitted equations in the legend show, the irreducible loss. $\\epsilon$ is different for each of the power-law distributions. Because these varying baselines are not subtracted in the plot, the curves appear non-linear. However, we can confirm that the power-law model is an excellent statistical fit, with R-squared values for our regressions all exceeding 0.98. This is in stark contrast to the uniform setting, which cannot be reasonably fitted to a power-law model, highlighting the fundamental difference in scaling behavior."}]

Author rebuttal:

Meta-review: This paper presents a theoretical framework for understanding LLM behaviors through the lens of compression and Kolmogorov complexity. To study this formally, the authors introduce a Syntax-Knowledge model, a hierarchical data-generation framework that separates language syntax (i.e., rules, parametric model) from factual knowledge (non-parametric Pitman–Yor Chinese Restaurant Process), allowing the derivation of both data and model scaling laws. The theory further predicts that models will hallucinate knowledge below frequency thresholds due to capacity constraints.

Overall, the paper is well written and all reviewers recommend acceptance. The introduction of data modeling enables a formal characterization of power-law scaling, providing new theoretical insights into the view of “LLMs as compressors.” While questions were raised regarding the contribution relative to prior work on this theme, the authors have addressed them during the rebuttal.
Decision: Accept (spotlight)