Compute-Optimal LLMs Provably Generalize Better with Scale
Authors: Marc Anton Finzi
Sanyam Kapoor
Diego Granziol
Anming Gu
Christopher De Sa
J Zico Kolter
Andrew Gordon Wilson
Venue: ICLR 2025 Poster (2025)
Keywords: generalization bounds
language models
scaling laws
Primary area: learning theory
TL;DR: We construct a generalization bound for LLMs which gets better as the models get bigger.

Abstract: Why do larger language models generalize better? To explore this question, we develop generalization bounds on the pretraining objective of large language models (LLMs) in the compute-optimal regime, as described by the Chinchilla scaling laws. We introduce a novel, fully empirical Freedman-type martingale concentration inequality that tightens existing bounds by accounting for the variance of the loss function. The generalization bound can be broken into three contributions: the number of parameters per token, the loss variance, and the quantization error at a fixed bitrate. As language models are scaled up, the number of parameters per data point stays constant; however, both the loss variance and the quantization error decrease, implying that larger models should have \emph{smaller} generalization gaps. We examine why larger models tend to be more quantizable from an information theoretic perspective, showing that the rate at which they can integrate new information grows slower than their capacity on the compute optimal frontier. From these findings we produce a scaling law for the generalization gap, showing that our bounds decrease in a predictable way.

Published as a conference paper at ICLR 2025
COMPUTE-OPTIMAL LLMs PROVABLY GENERALIZE BETTER WITH SCALE
Mare Finzi Carnegie Mellon University
Sanyam Kapoor New York University
Diego Granziol PureStrength Al
Anming Gu Boston University
Christopher De Sa" Cornell University
J. Zico Kolter* Carnegie Mellon University
Andrew Gordon Wilson' New York University
ABSTRACT
Why do larger language models generalize better? To explore this question, we develop generalization bounds on the pretraining objective of large language models (LLMs) in the compute-optimal regime, as described by the Chinchilla scaling laws. We introduce novel, fully empirical Freedman-type martingale concentration inequality that tightens existing bounds by accounting for the variance of the loss function. This generalization bound can be decomposed into three interpretable components: the number of parameters per token, the loss variance, and the quantization error at fixed bitrate. As language models are scaled up, the number parameters per data point remains constant; however, both the loss variance and the quantization error decrease, implying that larger models should have smaller generalization gaps. We examine why larger models tend to be more quantizable from information theoretic perspective, showing that the rate which they can integrate new information grows slower than their capacity on the compute-optimal frontier. From these findings we produce scaling law for the generalization gap, showing that our bounds become stronger in predictable way.
INTRODUCTION
Large language models (LLMs) have demonstrated remarkable general purpose problem solving capacity across wide range of complex tasks, from classical NLU (Brown, 2020), forecasting (Gruver et al., 2023), mathematies (Trinh et al., 2024), spatial reasoning (Patel & Pavlick, 2022), and many other areas. For a large majority of individual tasks, model capabilities increase monotonically as the next token prediction loss from the pretraining objective decreases.
A conceptually useful story about the learning process involves the model accommodating predictive subprograms of progressively larger computational depth and complexity. During pretraining, shallow details like word frequencies, syntax, and grammar are absorbed first, followed by higher level structures such as facts, relations, and idioms, eventually giving way to yet higher level patterns. For reasons not yet well understood, this process manifests in the pretraining objective LLMS and other generative models on natural data. The frontier of best achievable performance given fixed computational budget C obeys predictable power law relationship L(C)) x C-7 over many orders of magnitude (Kaplan et al., 2020), varying considerably with the kind of data (Henighan et al., 2020) but only weakly with model architecture and training method (Bahri al., 2021).
power law for
Effort in quantifying what this relationship is in a given domain and how it varies as model size and dataset size traded off has been extremely valuable in guiding where resources spent in constructing more capable Al models (Brown, 2020; Besiroglu et al., 2024; OpenAl, 2023; Dubey al., 2024) and charting a path for the future. In this work, we target the why of scaling laws. While mathematically simple toy models toy data are valuable, we aim to study the why of scaling laws on real models and real data by focusing on one contribution the scaling law curve: the token-wise generalization gap. Constructing a generalization bound sensitive enough to capture the small differences between architectures and yet simple enough to write down in a short formula is
" Equul advising.

---

Published as a conference paper at ICLR 2025
likely impossible; however, even the broad strokes of behavior such as how generalization scales with compute have not been addressed. Thus, here we focus high level understanding rather than algorithmic intervention.
We can observe that in order for the generalization gap not to eventually dominate the contributions to the test loss (which has not yet been observed), it must be that the generalization gap decreases at least as fast as the approximation gap does. Deeply understanding the success of the pretraining scaling of LLMs paradigm requires being able to predict that this would be the case.
In order to construct the relevant generalization bounds, we introduce a novel empirical Freed- man concentration inequality (Freedman, 1975). Our generalization bound highlights three critical components- the ratio of parameters per token in compute-opting optimal scaling (which is roughly con- stant), the loken-wise loss variance (which decreases with model size), and the performance gap between quantized and unquantized models (which also decreases with model size). As an alternative to quantization, we bound the information transfer between dataset and the model, showing that the information content in the model grows sublinearly with model size, and thus the complexity decreases with model size. These components collectively contribute to a predictable reduction the generalization gap as models grow larger.
2 BACKGROUND
2.1
GENERALIZATION BOUNDS
At a high level, we are interested in the expected test error (population risk) Ext ( (BR(x)(X')) for a given model (hypothesis) depending on the training set but evaluated on a test set X' sampled from the data distribution pp. One conceptually convenient way of breaking down this quantity is into the irreducible error, approximation gap, and generalization gap:
Ex'=po
[R((x) ( = R. (X) (x)x)(X) - (X) + Ex' [R((X) (X') - RA(X)
Inreducible Error E
Approximation Gap A
Generalization Gap G3
The first term describes the entropy of natural text, e.g. the amount of truly random information content in the data, which cannot be further explained even when knowing the true data generating process. The second term describes the approximation gap, capturing the extent which the trained model is able to fit the training data. This term combines both model capacity, e.g. as described by universal approximation theorems (Cybenko, 1989), well as optimization via how well the training algorithm is able to find the given solution. Finally, we have the generalization gap, capturing the extent to which training and testing performance diverge on account of overfitting to the statistically irrelevant regularities in X. Though generalization bounds focus on the last term, all three quantities are of interest for understanding LLM behavior. Empirically, it has been observed that the generalization gap for LLMs (at least in the low epoch regime) tends to be extremely small compared to the other two terms and we aim to make sense of why this is the case.
Among the simplest generalization bounds is the finite hypothesis with prior generalization bound applied to IID data Shwlle-Shwartz& & Ben-David, 2014). With probability at least
log 1/ 1/P(h) log 1/8
Ex'opo -Rax) s /
2m
where m is the number of IID data points, A an upper bound on the range of values the risk can take, and P(h) is prior distribution over hypotheses in discrete hypothesis class H. With judicious choice of prior, log 1h)( can be related to the compressed size of the model measured in nats (Lotfi et al., 2022).
During text pretraining, the individual tokens are not sampled IID. Thus, a generalization bound requires treating entire documents (often thousands of tokens) as the elements the empirical risk is computed over. Note that modern language models have hundreds of times more parameters than
'We note this differs from the commonly referred to estimation approximation error breakdown (Bottou & Bousquet, 2007) or the bias-variance decomposition (Brown& & Ali, 2024); however, the train aror-generalization gap is more useful for our purposes.
2

---

Published as a conference paper at ICLR 2025
documents they were trained With the help of very extreme compression methods and using smoothing to bound A, it is possible to construct nonvacuous bounds (Lotfi et al., 2024a). However, the required compression (greater than 100 times) is severe that it cripples model performance.
In a recent work, Lotfi et al. (2024c) explore breaking down generalization into tokenwise gener- alization, e.g. how the loss varies with each individual predicted token being resampled under the distribution but keeping the context the same. Splitting up the training dataset X into the sequence of tokens [Xx]e= the authors bound
D E E[RA(X Xet) X<a] Rí (X),
T
where (Xg X<c) is the negative log likelihood for token given the context Xek. and the expectation is taken with respect to p (<<)) from the data distribution. The authors bound T
using Azuma's inequality arrive bound scaling Av log 1/P(h) Using novel empirical 2D
Freedman type inequality, we bound the same quantity T but improve upon this bound, reducing the leading term to A (/hh))(h)
2.2 CHINCHILLA SCALING LAWS
key insight from the current machine learning paradigm that the dataset should not considered fixed quantity. Rather than optimizing to find the best model for given dataset, one should instead try to find the best performing model and dataset for given computational budget. Hoffmann et al. (2022) describes the optimal allocation of resources for increasing the size of the model and increasing the size of the dataset under the assumption that data is plentiful relative to the computational budget.
Let N be the number of parameters and D be the number of training tokens. In the epoch regime of LLM pretraining, the negative log likelihood (NLL) loss is well-approximated by the power law
A
B
R(N, D) F.
No
D
where A, B empirically estimated constants, exponents 9 have similar values, and E is the irreducible error. Optimizing N (C) and D(C') under the constraint of fixed compute budget C' z D (Kaplan et al., 2020), one arrives
(C G(C/6)
D*(C)=
for constants G = (od) 1/(a+)) 3B
Bi(a B), and b = a/(a + 3). as derived in Hoffmann et al.
(2022).
Within the margin of statistical error, we have a b 0.5 the optimal alloca- tion of compute (Besiroglu et al., 2024). Therefore, the ratio of parameters per token, Gº, a fixed constant. Evaluating the constants from Besiroglu et al. (2024), have G ~ 1/20. We remark that many open source models optimize perfor- mance amortized over both training time and inference time compute (Sardana et al., 2023), which leads "smaller than Chinchilla optimal models," e.g. models with a ratio N/D G and similarly when repeating data in the data con- strained setting Muennighoff
N (C))D"(CC
al. (2024). In the context of this paper, we will assume the Chinchilla optimal scaling N/D G², and remark that any generalization bounds we construct would only be tighter if the ratio N/D is smaller.
1010
6x
Parameters
10
10
3x
2x
To test our theory, we use the open source Pythia model family (Biderman et al., 2023) ranging from 70 million to 12 billion parameters. Unlike other open source LLMs, we have full access to both the Pythia model checkpoints from training and the Pile dataset they were trained on (Gao al., 2020), which required for analysis. From these intermediate
10
10th
10a1
Training FLOPS
Figure 1: Pythia models and checkpoints chosen along the compute-optimal frontier (checkpoints given by the marked values).
3

---

Published as a conference paper at ICLR 2025
checkpoints, we choose the set of models along the compute-optimal frontier to match N/D G2 1 1/20, reflecting the choice for number of training steps and model size that one would have made optimizing only for performance at the given computational budget. The chosen checkpoints are plotted in the training frontier of these models in Figure 1.
3 GENERALIZATION BOUND
In this section, we build the components used in constructing our final generalization bound stated in Theorem 3.4. To capture the relevant behavior, derive new concentration inequality for martingales. We apply a prior weighted union bound to this concentration inequality so that we can apply to models in large hypothesis class, taking advantage of the low complexity inherent in compressible models. Bounding the worst case loss behavior using prediction smoothing, we apply this bound to LLMs.
At a high level, we can motivate the overall behavior of the bounds as follows. On account of the compute optimal scaling, as LLMs are scaled, the ratio of parameters to training tokens remains fixed constant, G x 1/20,, less than one. However as the models improve, the per token standard deviation of the loss decreases, and at predictable rate of approximately c 1/ /.N. If the per token variation small, then sufficiently sensitive concentration inequality will translate this into a tighter concentration around the mean. Simultaneously, the amount of information stored per parameter, and thus the compressed size of the model given a suitable compression scheme, appears to decrease with scale at the compute optimal frontier. Combining these observations, produce generalization bounds showing that the gap between train and test shrinks as these models are scaled up.
3.1 AN EMPIRICAL FREEDMAN'S CONCENTRATION INEQUALITY
Theorem 3.1. Let (X+) XI..... Xn and (Yx) be sequences of random variables adapted to the filtration (Fr)k=o where Xx is F2 measurable and Y2 is FR-1 measurable. Assume the difference between the two is bounded below: A = (Y*- Xx)) A > 1 for some A 2 Let K be any finite subset of (0, 1). Then, with probability at least 1 5 over the probability space (filtered by (Fo))
[B|X2 - Xx)) s AC+EVO.
(I)
where C == 1 log 8 and
[K]
A
== IC,,, XA)R K) min minnmiCCC -)/8++ vCn Σ (sAA)\/s
sEK
and u(x) x log(1 + 2).
The proof provided in Appendix A.I. This concentration inequality states that the sequence of random variables concentrates on their conditional means with a term Σ depending on the empirical variation of the loss value. We note that Σ can viewed as variance term. As we show in Appendix
A, using small K, the variance proxy can be upper bounded: S 2/ E Y2),, explic- itly related to the empirical variance but with the mean replaced by Yg. Although the minimization form above unwieldy, it produces significantly tighter estimates of (a factor of ~ 5x smaller). When the loss variation Σ is small, concentration to the mean happens at a rate linear in the complexity C' rather the slower V rate. The finite set K serves merely as device to control how finely is optimized, and can be set for example as uniformly spaced grid in (0, 1).
The concentration inequality we present here provides the core result for our generalization bounds, and to the best of our knowledge it is the first martingale concentration inequality to incorporate variance term which can be evaluated on the original data. We can view this bound as aiming to achieve the benefits that Freedman's 's inequality has over Azuma's 's inequality while being fully empirical, replacing the population variance with fully empirical proxy. Our approach is analogous to the fully empirical Bernstein bound derived in Maurer & Pontil (2009), but in the martingale rather than IID setting. Unfortunately, the proof technique of Maurer & Pontil (2009) does not carry
4

---

Published as a conference paper at ICLR 2025
the martingale case and instead we take different approach. We derive concentration inequality in Theorem A.5 making use of a proxy Y2 that is F but which can take the place of [[Xx [K-1] in the variance. In practice, choose this quantity to be the mean of the model NLL under resampling of the given token according to the model distribution in place of the data distribution.
3.2 EXTENDING A DISCRETE HYPOTHESIS CLASS
From the concentration inequality in equation 1, we derive the following discrete hypothesis class generalization bound.
Lemma 3.2. Let X Xn be a sequence of (possibly dependent) random variables. Let R (X& x denote the risk element Xx given the previous elements of the sequence for hypothesis h in countable hypothesis class H. Let ( xxx) be any (hypothesis dependent) distribution over X conditioned on dek- Consider prefix free coding of each h E HH and let L(h) be the length of that code measured nats. Let K be a finite subset of I Assuming RG (X Xee) - Ey,-p [Rg YY
X X= S for some A O, we have that simultaneousty for all h E H. with probability at least 6,
ΣΣ
(Xn
| Xen) S n1
Σ
Ra (Xx Xxx)) + AC +EVc,
(2)
71
where the complexity is given by
C:= L(h) + log K1/8
7
and (A)) K) K)& X<u)].
as Theorem 3.1 for Av = Rx Xxe) - Eraopn (Yr
We provide the proof in Appendix A.2.
3.3 WORST CASE BEHAVIOR AND SMOOTHING
The last component of our bounds is the smoothing to bound the worst case behavior of the model, which in general for the negative log likelihood can be arbitrarily large. We employ the prediction smoothing idea from Lotfi et al. (2024a), where the model is mixed with a uniform distribution over the tokens with given mixing parameter. Unlike application in previous work, we optimize this parameter analytically so that we can remove it from the bounds and evaluation entirely, instead of merely tool for constructing bounds while all evaluations with the unsmoothed model.
Lemma 3.3. For the categorical negative
log likelihood objective RR = - - (X (xc)) V classes and C E RR. there exists pre- diction smoothed model p.(.) = (1 (.) + a/V which has a worst case loss
A, supx,.Xea loggs (Xx Xxc) S log(V/oi), and the risk satisfies
R, + CA. RA Clogg V + V2C,
(3)
for some value a E (0,1) (approximately C/(1 C)).
We provide the proof in Appendix A.3.
3.4 GENERALIZATION BOUND FOR COMPUTE OPTIMAL LANGUAGE MODELS
Finally, we assemble these three components into generalization bound that we can empirically evaluate for language models. Combining the prediction smoothing bound with Theorem 3.2 applied to the smoothed quantized model produces our main result. Note that each term in the expression has an interpretable meaning.
Theorem 3.4. Let XI...., Xp be the sequence of D (possibly dependent) tokens formed from concatenating each sequence in the dataset together into single stream of tokens. Let Rd (Xx Xex) log PnlXa, xxx)) denote the NLL for element X given the previous elements for given model h and with vocabulary size V and N parameters. Let Rr 1. ED Ra(Xx. Xex)
5

---

Published as a conference paper at ICLR 2025
be the empirical risk and b for that model. Let be a finite subset of (0,1). For any given quantization q of h using b bits per parameter with expected risk Rg. there exists label smoothed and quantized model sq with ( X<x) = -1 o) Rg xxk) + o/V for fixed a E (0, which, with probability 1 6,
EiR,(Xx E Xxk) X<ck be the tokenwise expected risk
achieves a tokenwise population risk
Rag S RA +
Clog V
EVC
V2C Smoothing Cost
(Rug (Rg- RRn); Quantization Gap
Rondom Guess NLL
Loss Variation
where the complexity C is given by
|K| and Σ E(C, A, (A+JE-1 K) (defined in Theorem 3.2) can be upper bounded in terms of the empirical loss variance:
C- (#)blogg log
C
E
(R X²x) - Ey ~p (R Xxx)))
D
h=1
To make sense of the bound, let's consider the various terms. The bounded quantity the left hand side, Reg. is the expected tokenwise risk of the smoothed and quantized version hypothesis h. The bound is written in terms of the empirical risk of the original model h, with Ry R.g controlled by the smoothing cost and quantization gap. Typically, the largest contribution to the bound is C log V. e.g. the complexity times the negative log likelihood of random guessing. The loss variation relates to how spread the empirical loss and can be seen as a model realizability term. there existed a 0 loss model in the model class, then this term could be brought to O; however, given the nonzero entropy of natural text, this will not be the case. Note that as models improve and approach the irreducible error, so too will the empirical loss variation.
N In this setup, the complexity C is just the ratio of parameters to data points, D = G2, times the number of bits per parameter used in the quantization b, plus negligible additional term. The decreased complexity of using fewer bits for trades off with the quantization gap. and in principle this parameter should be optimized to achieve the best bound. As all terms in the expression can be evaluated empirically, we can determine how much of the empirical observation it can explain and how much remains to be understood.
To get a sense for the scale of the different terms, consider the following typical scenario in LLMs. The averaged negative log likelihood loss is measured nats per token, where nat is log, e bits. For simplicity, suppose we have vocabulary size V = 50000 (so log V R 11), quantization b = 3, and G2 1/20,, which yields C 1/9. Σ varies with model scale but is scale 1/10,, and the quantization gap is around 1/10. Evaluating these terms, we see that Rag Rr S 11/9 + 1/30 1.4/3 1/10 1.8 nats per token, and see that the random guess and smoothing terms contribute most the size of the bound. For perspective, the empirical risk R2, itself around 2 nats per token and the boundary between vacuous and nonvacuous bounds is at log V = 11 nats per token.
4 EMPIRICAL EVALUATION
As Theorem 3,4 is fully empirical, we simply need to empirically evaluate the loss variation term along with the quantization gap and we can evaluate the generalization bound. We compute these quantities on the given Pythia checkpoints on the Pile dataset on which they were trained and quantized using GPTQ (Frantar et al., 2023)
bits per parameter, and we evaluate the bounds with failure probability 5 0.01. The results are shown in Figure 2 for the Chinchilla compute-optimal checkpoints within the Pythia model family.
We compute Σ with K given by 1000 equally spaced points between [0, 1]. excluding the endpoints. We estimate the risk and loss variation on an IID subsample from the collection of token-context pairs in the training dataset of size 10 and bound the difference from the full training set evaluation and the 10 sized subsample with a simple Hoeffding bound. We note that largest 12B parameter model failed quantize properly (possibly due to the learning rate drop
the only checkpoint taken the

---

Published as a conference paper at ICLR 2025
Token))
Variation
N
0.7
1- + 63377 N
Bound Contribution (Nats/Tbken)
1.5
5
1.0
ClogV
Empirical Loss
Bounded Value
0.5
IVC
0.5
12G
3
0.4
RRo1
0.3
10a
10*
10*
10"
10a
102
10
Parameters
Parameters
Parameters
Figure 2: Left: A direct comparison of our evaluated generalization bound, and the empirical loss as a function of model scale. As the model is scaled up, our bound improves just like the empirical loss. Center: Loss variation Y entering into the generalization bound. As the loss deviation decreases, so does the largest term in our bound. Right: Comparison of the relative scale of the contributions to Theorem 3.4. Here we use a fixed bit quantization of the parameters.
end training) and so we removed from the evaluation. We must pick out the compute-optimal checkpoints from training runs that were not designed for this purpose. For the two smallest models (70m and 160m parameters) where the compute optimal training duration is early into the training run and thus sparsely sampled with checkpoints, and the closest models consistently have too small a value of N/D, biasing these two initial data points towards lower values. For these two points, we compute the relevant quantities D, E, R4, Rg. Σ by linearly interpolating using the parameter N/ with the target value of G².
In Figure 2, can observe several points. In Figure 2 (center), we see that the loss variation decreases with model size as 0.27 + N3..5 approximately 1/ 1/vN with a constant offset. As additional compute is spent model training, predictions narrow and the loss variation decreases. Like with the irreducible error E, it converges to a minimum value presumably related to the varentropy of the distribution. In Figure (right), we break down the individual contributions to the generalization bound. The quantization error and loss variance contributing fraction of nat per token and decrease with scale, while the C log V term and smoothing terms contribute the majority to the bounds and do not decrease with scale. Figure (left) shows the comparison with the bound value Rag and the empirical risk R₁.- The fact that the quantization gap at fixed number of bits decreases with model size has been observed to much greater extent in other work (Chee et al., 2024; Tseng al., 2024) with more advanced quantization methods and with fewer bits per parameter. This property suggests that if were able to be freely optimized in the bound, the complexity C would actually decrease with model size, and we explore evidence for and consequences of this idea in the following section.
5 COMPRESSIBILITY AND THE SUBLINEAR INFORMATION GROWTH IN LLMS
While not obvious from efficient quantization algorithms like GPTQ (Frantar et al., 2023), there good reasons to believe that the model complexity term L(h)/D decreases with model scale on the compute-optimal frontier.
5.1 QUANTIZABILITY FROM THE HESSIAN SPECTRUM AND QUIP
So far have split the compressed size of the model L(h) featured in the complexity term into the number of parameters times the number of bits per parameter used in the quantization L(h) < bN log2. 2. In this splitting, increased compressibility of model shows up in terms of requiring smaller number of bits b achieve given quantization gap R, Rr. In Appendix B, we provide a theoretical argument using the QulP quantization framework (Chee et al., 2024) for why we should expect that larger models can more easily quantized. the Hessian around the solution weights is positive semi-definite (PSD) and the spectrum decays sufficiently rapidly, then we should expect the quantization error to decrease with model size. In Section B.3, we investigate the Hessian spectrum empirically finding that it indeed decays sufficiently quickly (though not always PSD). Unfortunately, the version QulP needed to construct this argument cannot be run in practice due to the impractically large computational constraints. Empirically it has been observed that practical
7

---

Published as a conference paper at ICLR 2025
quantization algorithms also reveal that larger models are more quantizable (Tseng et al., 2024), though the effect is not very pronounced with the GPTQ algorithm we use here.
Alternatively, present more abstract cooommmtion-thooretii argument to provide evidence for the fact that L(h)/ decreases with model scale even if we do not have an explicit compression scheme to achieve it.
5.2 INFORMATION ACCUMULATION IN LLMS
At initialization, the information content in large neural network is extremely small, requiring only the model architecture and a random seed to be fully specified. As training progresses, information transfers incrementally from the dataset to the model weights. This transfer can be quantified using prequential coding (Rissanen, 1984; Dawid, 1984) and algorithmic information theory.
Let ((X) be the (prefix) Kolmogorov complexity of the dataset X (the length of shortest self- delimiting program producing X). From the symmetry of information property, K (X, (X h)
K K(h) - (x where e a small constant. Rearranging, K (h) kX, K [h) c measures the information content in h as the difference between the size of the smallest program that codes X and h jointly and the smallest program that codes X given
As described in Blier & Ollivier (2018); Voita & Titov (2020) and more specifically in Zhang et al. (2020), one can use prequential coding to provide an estimate for an upper bound on K (X, h)) - (x)
A prequential code (Rissanen, 1984; Dawid, 1984) provides means code the tuple of data and probability model (X, h) by using codes derived from intermediate snapshots of the model as processes and updates the sender and receiver each to have an identical copy of the model at initialization hu (along with the randomness seed if randomness is used in the training algorithm). From this model at initialization, the initialized probability model hg can be used to encode data in its domain with using arithmetic coding (or any entropy stream code) using log, Pho (X1) bits, which can be decoded by the receiver using hg. With the first data point X1 transmitted, both the sender and receiver train on this data point yielding identical models h1. From here the process can be repeated coding the subsequent data point with coded using hn and so forth until the entire dataset has been transmitted. Using an entropy code for the transmission, the entire code for the transmission need not be greater than
each successive data point in X during training. As setup, one considers
-h_ log, p (Xx)X bits, the area under the loss curve. With this transmission the receiver can reconstruct the entire dataset X = (X1, X2, Xp) and the sequence of models produced during training [h1, h2..... hi2....,,pl hp]. While this prequential code is not a prefix free code, it can be converted into with logarithmic extra bits (see Section A.2), merely small constant extra bits if the vocabulary size V and dataset size D are prespecified, which we will assume from now on. With the prequential code, K (XX,1 h) can be upper bounded for a generative model h in terms of the area under the loss curve, and notably this is true regardless of the number of parameters in h or the number of bits needed in a more direct coding scheme. Instead, the information in the model is determined by the information in the data.
While not a strict lower bound, K (X(A)) can be estimated from entropy coding of the data using the generative model as suggested in Zhang et al. (2020), and with this strategy the codelength for X D given h is Σb_ 1= log2 Pho (X&|X<k) the loss for the final model. Assembling the two together, up to small constant factors,
D K(h) log(2) S Σ Ran ,(x)X22)) - RAo (XxIXe)))
(5)
We evaluate this expression numerically for the Pythia models, however we can also gain some insight by examining the asymptotic scaling of this quantity with the size of the dataset. For reasonable approximation for the loss along the training trajectory. one can use the Chinchilla scaling
law R(N, D) = E AN + BD-3 Noting that Eh f(k) b J f(x)dx as D oc.
K(h) log(2) < E DR(N, D) +
B Dl = -
(6)
1-
8

---

Published as a conference paper at ICLR 2025
Information content
1011
Bound Contributtion (Nats/Token)
104
V
Generalization Gap
(Nats/Token)
Prequential based Quantization based
CYC
10t
1040
100
Prequential code K(h)
10a
5 10
(parameter counting)
N9.00
10-1
100
10*
10"
10
10a
10
10
10"
10
10
10
Parameters
Parameters
Parameters
Figure 3: Left: Information content contained in the model upper bounded by ((h) from the information transfer prequential coding approach vs parameter counting and quantization. Fitting power law the prequential K (/) yields 6 - NV..50011 While parameter counting gives better upper bound over the range of Pythia models, the sublinear scaling of the prequential bound means that it overtakes it eventually, somewhere around 30B sized models. Center: The contributions of the various terms to our generalization bounds when using prequential coding complexity, along with their power law fits. Right: Comparison of generalization bounds produced by the prequential vs quantization based approaches. While the prequential bounds are worse, they follow power law and improve substantially with scale.
From this we obtain an insightful result: the information content in the model grows sublinearly with training dataset size, with a coefficient depending the scaling law.
As shown in Figure (left), using the empirical loss curves to evaluate Σb Ek=11 RNE-1 (Xx)
(Xxl x<))] and fitting the results to power law, we get 105 N00.500.11 x 1).5. In contrast, from the asymptotics using the scaling law to approximate the loss 8 = 0.37 evaluating (Besiroglu et al., 2024) yields D 00.63 which is not far off. While the empirical values for the upper bound lie above the straightforward value gets from quantization and parameter counting bN over the range of Pythia models, the curves predict a crossover point at =: 20B parameter models.
x
5.3 IMPLICATIONS FOR GENERALIZATION BOUNDS
If apply this observation to upper bound the complexity featured in generalization bounds (Theorem 3.4) C L(k)+log Ki/6 K (h) log(2)/D + log |K// O(D-)), we see that the complexity will actually decrease with the size of the dataset even as the ratio with parameters is held constant. With this scaling, we can derive a version of the generalization bound Theorem 3.4 without needing to consider quantization or considering the number of explicit parameters in the model, provided that the Chinchilla scaling law holds.
We evaluate the non asymptotic generalization bound of Theorem 3.4 but using the complexity derived from empirical prequential coding bound in Figure (right) and break it down into the scaling of the individual terms (center), with the V term scaling law extrapolated from the fit in Figure 2. Like before, the C' log V term dominates; however, the /2C smoothing term threatens to overtake it with very large model sizes. We can see that the bounds based on the prequential coding are worse than their quantization counterparts; however, the bounds improve with scale and can be extrapolated with scaling laws. Considering only the asymptotics, the generalization gap of Theorem 3.4 will be dominated by the scaling of the smoothing term V2C: R. Rí O(D-8/2). To speculate, seems likely that with a more sophisticated approach for dealing with the unbounded loss, the VC ((23 could be removed, letting the ODD-9) shine through. If that were the case, then the tokenwise generalization gap could indeed be hidden within the D D-9 of the original scaling law.
ADDITIONAL RELATED WORK
Generalization Bounds. Historically, generalization bounds for neural networks have been limited by their large parameter count, though significant progress has been made in explaining generalization behavior (Dziugaite & Roy, 2017; Zhou et al., 2018; Arora et al., 2018; Lotfi et al., 2022), with PAC- Bayes providing convenient unifying framework (Catoni, 2007). Lotfi al. (2024a) constructed

---

Published as a conference paper at ICLR 2025
the first non-vacuous generalization bounds for LLMs using prediction smoothing and extreme compression with subspace LoRA (Hu et al., 2021).
While Lotfi et al. (2024a) focused on document-level bounds, Lotfi et al. (2024b) used Azuma's 's in- cquality for token-level martingale-biie bounds. We adopt this approach but improve the complexity from ((VC) to ((C) through loss variation. Related work has constrained context learning in LLMs (Li et al., 2023) and explored generalization in vision-language models (Akinwande et al., 2023).
Chugg et al. (2023) developed generalization bounds for both IID and martingale settings generalizing many previous results; however, these bounds are not fully empirical and thus can't be applied in the setting we require. Closest to our work, Maurer & Pontil (2009) derived a fully empirical Bernstein inequality, their technique doesn't extend non-IID martingale settings.
Post-Training Quantization. For hardware efficiency, significant research has explored reducing model precision post-training while preserving performance (Hassibi et al., 1993; Hubara et al., 2021: Yao et al., 2022; Dettmers et al., 2022). Empirically, 3-4 bits provide a reasonable compression- performance tradeoff, with recent work pushing to 1.58 bits per parameter (Ma et al., 2024) and even binary networks showing promise (Liu et al.. 2024).
For this work, we use GPTQ (Frantar et al., 2023) with 4-bit quantization, which achieves efficient extreme quantization through iterative weight column rounding. Alternative approaches include QulP (Chee et al., 2024), which uses incoherence in approximate Hessian estimation to suppress outliers, and its improved variant QulP# (Tseng et al., 2024). We leverage the analysis from these two papers in Appendix to shed some light on how the quantizability scales with model size due to the spectrum of the Hessian.
7 DISCUSSION
We have provided generalization theory to better explain why large language models trained in the compute-optimal regime generalize, with particular attention on how generalization changes with scale. For the term that contributes the most to the generalization bound, we are able to improve the scaling over previous work from vC log to Clog V, while remaining fully empirical. We explore two approaches for constraining model complexity in the generalization bounds, directly via quantization and parameter counting, and indirectly, via information transfer as quantified by prequential coding. While the quantization approach yields tighter bounds at Pythia model scale, the information transfer approach reveals that information in the model grows at a rate that is sublinear in the size of the dataset, and consequently the generalization gap must also decrease with scale.
While we believe that these insights help advance understanding, there are a number of limitations of our approach and many questions that remain unaddressed. As previously mentioned, the v/c smoothing term seems pessimistic and could likely be improved with a different approach. Addition- ally, while the information transfer argument provides evidence that the complexity of a model is low based the training curve, it falls short of explaining why the complexity is low. In principle, the training curve could look different if it did not follow the Chinchilla power law scaling, leading to different information transfer rate. Similarly, the Hessian based argument explains why larger models are more quantizable given the scaling of spectrum of the Hessian, but why the Hessian spectrum has this empirical behavior remains unexplained. Furthermore, it seems likely that the 1/VN in the loss variation term could be explained theoretically.
Even more broadly, our generalization bounds constrain only the loken-wise generalization gap. While it intuitive that generalizing well on next token prediction over the training contexts should imply generalization on the full sequences, we are not aware of work that does so, and this gap remains to be understood. Similarly, constraining generalization on the NLL objective over data drawn from the natural distribution may be less pertinent. Instead, it may be more relevant to constrain the gap between the quality metrics of model generations and natural data. Further removed, there is the question of why the training loss scales in the way that it does, and how does that relate to approximation theory and the architecture of the model? Though many questions remain, we hope that the techniques here can yield generalizable insights for tackling this broader set of problems.
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Victor Akinwande, Yiding Jiang, Dylan Sam, and J Zico Kolter. Understanding prompt engineering may not require rethinking generalization. arXiv preprint arXiv:2310.03395,, 2023.
Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via a compression approach. In International Conference on Machine Learning, pp. 254-263. PMLR, 2018.
Yasaman Bahri, Ethan Dyer, Jared Kaplan, Jaehoon Lee, and Utkarsh Sharma. Explaining neural scaling laws. Proceedings of the National Academy of Sciences of the United States of America, 121, 2021.
Tamay Besiroglu, Ege Erdil, Matthew Barett,, and Josh You. Chinchilla scaling: A replication attempt. arXiv preprint 1xXiv2244..0102,, 2024.
Stella Biderman, Hailey Schoelkopf, Quentin Gregory Anthony, Herbie Bradley, Kyle O'Brien, Eric Hallahan, Mohammad Aflah Khan, Shivanshu Purohit, USVSN Sai Prashanth, Edward Raff, et al. Pythia: A suite for analyzing large language models across training and scaling. In International Conference Machine Learning, pp. 2397-2430. PMLR, 2023.
Léonard Blier and Yann Ollivier: Information Processing Systems, 31, 2018.
The description length of deep learning models. Advances in Neural
Léon Bottou and Olivier Bousquet. The tradeoffs of large scale learning. Advances in neural information processing systems, 20, 2007.
Gavin Brown and Riccardo Ali. Bias/variance is not the same as approximation/essiaatiin. Transac- fions on Machine Learning Research, 2024.
Tom B Brown. Language models are few-shot learners. arXiv preprint arXiv:2005. 14/65, 2020.
Joël Bun, Jean-PPi Shan-Phllippe Bouchaud, and Mare Potters. Cleaning large correlation matrices: tools from random matrix theory. Physics Reports, 666:1-109, 2017.
Olivier Catoni. Pac-bayesian supervised classification: the thermodynamics of statistical learning. arXiv preprint arXiv:07 2007.
Jerry Chee, Yaohui Cai, Volodymyr Kuleshov, and Christopher M De Sa. Quip: 2-bit quantization of large language models with guarantees. Advances in Neural Information Processing Systems, 36, 2024.
Ben Chugg, Hongjian Wang, and Aaditya Ramdas. A unified recipe for deriving (time-uniform) pac-bayes bounds. Journal of Machine Learning Research, 24(372):1-61, 2023.
G. Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of Control, Signals and Systems, 303-3443 1989. doi: 10. 10.1007/BF02551227, URL https:/ //op::
A Philip Dawid. Present position and potential developments: Some personal views statistical theory the prequential approach. Journal of the Royal Statistical Society: Series A (General), 147(2): 278-290. 1984.
Tim Dettmers, Mike Lewis, Younes Belkada, and Luke Zettlemoyer. Llm.int80: 8-bit matrix multiplication for transformers at scale. ArXiv, 035/2208.07339 2022.
Kun Dong, David Eriksson, Hannes Nickisch, David Bindel, and Andrew G Wilson. Scalable log determinants for gaussian process kernel learning. Advances Neural Information Processing Systems, 30, 2017.
Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, et al. The lama 3 herd of models. ArXiv. abs/2407.21783,, 2024.
11

---

Published as a conference paper at ICLR 2025
Gintare Karolina Dziugaite and Daniel M Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. arXiv preprint arXiv:1703.11008, 2017.
Jack Fitzsimons, Diego Granziol, Kurt Cutajar, Michael Osbore, Maurizio Filippone, and Stephen Roberts. Entropic trace estimates for log determinants. In Machine Learning and Knowledge Dis- covery in Databases: European Conference, ECML PKDD 2017, Skopje, Macedonia, September 18-22, 2017, Proceedings, Part 1 10, pp. 323-338. Springer, 2017.
Elias Frantar, Saleh Ashkboos, Torsten Hoefler, and Dan Alistarh. Gptq: Accurate post-training quantization for generative pre-trained transformers, 2023.
David A. Freedman. On tail probabilities for martingales. 1975.
Leo Gao, Stella Biderman, Sid Black, Laurence Golding, Travis Hoppe, Charles Foster, Jason Phang, Horace He, Anish Thite, Noa Nabeshima, et al. The pile: An 800gb dataset of diverse text for language modeling. arXiv preprini arXiv:2101 00.00277 2020.
Behrooz Ghorbani, Shankar Krishnan, and Ying Xiao. An investigation into neural net optimization via hessian eigenvalue density. In International Conference on Machine Learning, pp. 2232-222
PMLR, 2019.
Diego Granziol, Xingchen Wan, Timur Garipov, Dmitry Vetrov, and Stephen Roberts. Mirg deep curvature: An open-source package to analyse and visualise neural network curvature and loss surface. stat, 2018.
Diego Granziol, Timur Garipov, Stefan Zohren, Dmitry Vetrov, Stephen Roberts, and Andrew Gordon Wilson. The deep learning limit: are negative neural network cigenvalues just noise? In ICML 2019 workshop on theoretical physics for deep learning, 2019.
Diego Granziol, Stefan Zohren, and Stephen Roberts. Learning rates function of batch size: A random matrix theory approach to neural network training. Journal of Machine Learning Research, 23(173):1-65 2022.
Nate Gruver, Marc Finzi, Shikai Qiu, and Andrew G Wilson. Large language mod- els are zero-shot time series forecasters. In A. Oh, T. Naumann, A. Glober- son, K. Saenko, M. Hardt, and S. Levine (eds.), Advances in Neural Informa- tion Processing 2023. URL Systems, volume 36, pp. 19622-19635. Curran Associates, Inc., www.inngn..nuussreeeeeee neurins popppreeepppppppppppppppprrr wwtprfffllssppeeeeeeeeeeeeeeseee wtt.f/////pepp//2/333333 .dff
Babak Hassibi, David G. Stork, and Gregory J. Wolff. Optimal brain surgeon and general network pruning. IEEE International Conference on Neural Networks pp. 293-299 vol. 1993.
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. 14701, 2020.
Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbl, Aidan Clark, Tom Hennigan, Eric Noland, Katie Millican, George van den Driessche, Bogdan Damoc, Aurelia Guy, Simon Osindero, Karen Simonyan, Erich Elsen, Jack W. Rae, Oriol Vinyals, and L. Sifre. Training compute-optinn optimal large language models. ArXiv, 1tt./2233315556, 2022.
Edward J. Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhi Zhu, Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu Chen. Lora: Low-rank adaptation of large language models. arXiv preprint arXiv:2106.09685, 2021.
Itay Hubara, Yury Nahshan, Yair Hanani, Ron Banner, and Daniel Soudry. Accurate post training quantization with small calibration sets. In International Conference on Machine Learning, 2021.
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B. Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeff Wu, and Dario Amodei. Scaling laws for neural language models. ArXiv, abs/2001 000661, 2020.
12

---

Published as a conference paper at ICLR 2025
Leon Gordon Kraft. device for quantizing, grouping, and coding amplittde-mouulate pulses. PhD thesis, Massachusetts Institute of Technology. 1949.
Yingcong Li, Muhammed Emrullah Iidiz, Dimitris Papailiopoulos, and Samet Oymak. Transformers as algorithms: Generalization and stability in in-context learning. In International Conference on Machine Learning, pp. 19555419594. PMLR, 2023.
James Liu, Guangxuan Xiao, Kai Li, Jason D. Lee, Song Han, Tri Dao, and Tianle Cai. Bitdelta: Your fine-tune may only be worth one bit, 2024.
Sanae Lotfi, Mare Finzi, Sanyam Kapoor, Andres Potapezynski, Micah Goldblum, and Andrew G Wilson. Pac-bayes compression bounds so tight that they can explain generalization. Advances in Neural Information Processing Systems, 35:31459-31477 2022.
Sanae Lotfi, Mare Finzi, Yilun Kuang, Tim G. J. Rudner, Micah Goldblum, and Andrew Gordon Wilson. Non-vacuous generalization bounds for large language models, 2024a.
Sanae Lotfi, Yilun Kuang, Brandon Amos, Micah Goldblum, Mare Finzi, and Andrew Gordon Wilson. Unlocking tokens data points for generalization bounds on larger language models. ArXiv, abs/2407. 01.4407.11555 18158, 2024b.
Sanae Lotfi Yilun Kuang, Brandon Amos, Micah Goldblum, Marc Finzi, and Andrew Gordon Wilson. Unlocking tokens as data points for generalization bounds on larger language models. arXiv preprint arXiv:2407. 181558..8888. 2024c.
Shuming Ma, Hongyu Wang. Lingxiao Ma, Lei Wang. Wenhui Wang, Shaohan Huang, Li Dong, Ruiping Wang, Jilong Xue, and Furu Wei. The era of 1-bit llms: All large language models are in 1.58 bits, 2024.
Andreas Maurer and Massimiliano Pontil. Empirical bernstein bounds and sample variance penaliza- tion. arXiv preprint arXiv:0907.3740, 2009.
Brockway McMillan. Two inequalities implied by unique decipherability. IRE Transactions on Information Theory, 2(4):115-116 1956.
Gérard Meurant and Zdenčk Strakoš. The lanezos and conjugate gradient algorithms in finite precision arithmetic. Acta Numerica, 15:471-547 2006.
Niklas Muennighoff, Alexander Rush, Boaz Barak, Teven Le Scao, Nouamane Tazi, Aleksandra Piktus, Sampo Pyysalo, Thomas Wolf, and Colin A Raffel. Scaling data-constrained language models. Advances in Neural Information Processing Systems, 36, 2024.
Markus Nagel, Rana Ali Amjad, Mart Van Baalen, Christos Louizos, and Tijmen Blankevoort. Up or down? adaptive rounding for post-training quantization, In International Conference on Machine Learning, pp. 7197-7206. PMLR, 2020.
OpenAl. Gpt-4 technical report. 2023.
Vardan Papyan. Mcasurements three-level hicrarchical structure in the outliers in the spectrum of deepnet hessians. arXiv preprint arXiv: 1901.0824, 2019.
Roma Patel and Ellie Pavlick. Mapping language models to grounded conceptual spaces. In International Conference Learning Representations, 2022.
Barak A Pearlmutter. Fast exact multiplication by the hessian. Neural computation, 6(1):147-160, 1994.
Andres Potapezynski, Mare Finzi, Geoff Pleiss, and Andrew Gordon Wilson. CoLA: Exploiting Compositional Structure for Automatic and Efficient Numerical Linear Algebra. arXiv preprint arXiv:2309.0308 03060. 2023.
Jorma Rissanen. Universal coding, information, prediction, and estimation. IEEE Transactions on Information theory, 30(4):629-66) 6666, 1984.
13

---

Published as a conference paper at ICLR 2025
Farbod Koosta-Khorassan and Uri Ascher. Improved bounds sample size for implicit matrix trace estimators. Foundations of Computational Mathematics, 15(5) 2015.
Nikhil Sardana, Jacob Portes, Sasha Doubov, and Jonathan Frankle. Beyond chinchilla-optimal: Accounting for inference in language model scaling laws. arXiv preprint arXiv:2401. 4444000448, 2023.
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
Tricu H. Trinh, Yuhuai Wu, Quoc V. Le, He He, and Thang Luong. Solving olympiad geometry without human demonstrations. Nature, 625:476 482, 2024.
Albert Tseng, Jerry Chee, Qingyao Sun, Volodymyr Kuleshov, and Christopher De Sa. Quip: Even better IIm quantization with hadamard incoherence and lattice codebooks, 2024.
Shashanka Ubaru, Jie Chen, and Yousef Saad. Fast estimation of tr(f(a)) via stochastic lanezos quadrature. SIAM Journal on Matrix Analysis and Applications, 38(4):1075 2017.
Jean Ville. Énude critique de la notion de collectif. 1939. URL http: www.eeuwwmo..o.eeeeeeeeeeeeeeeee /rc/ 192893.
Elena Voita and Ivan Titov, Information-theorrtie probing with minimum description length. arXiv preprint arXiv:2003. 12298, 2020.
Zhewei Yao, Reza Yazdani Aminabadi, Minjia Zhang, Xiaoxia Wu, Conglong Li, and Yuxiong He. Zeroquant: Efficient and affordable post-training quantization for large-scale transformers. ArXiv, abs/2206.01861, 2022.
Xiao Zhang, Xingjian Li, Dejing Dou, and Ji Wu. Measuring information transfer in neural networks. arXiv preprint arXiv:2009.07624 2020.
Wenda Zhou, Victor Veitch, Morgane Austern, Ryan Adams, and Peter Orbanz. Non-vacuous generalization bounds the imagenet scale: pac-bayesian compression approach. arXiv preprint arXiv:1804.05882,, 2018
14

---

Published as a conference paper at ICLR 2025
A PROOFS
A.1 A FULLYY EMPIRICAL MARTINGALE FREEDMAN CONCENTRATION INEQUALITY.
In this section, unless otherwise specified, log is used to denote the natural logarithm. We start with three technical lemmas.
Lemma A.1. Consider the function v(a)
log(1 + +a). Let pa R. For any random variable Z with E| Z = 0 that satisfies Z 1 > -1 we have
Elexp( 7 - v(zz - 1()) = =(1 - -u)e" 1
Proof. We see that
Ezexp(Z- v(Z [])] = e" e'Elexp(2 - - v(Z p))] c" (Z -+]]
As E[Z] know Elexp(Z - vl n))l (1 p)ee.. Additionally 1- μ S eM, we have
Elexp(Z Z - v(Z - μ)) S 1, as desired.
Lemma A.2. Consider the function v(a) = a log + a). For all a E (-1, we have v(a) - a² (1+
Proof. Let f(a) = which is a strictly negative function passing through 0 at = 0. As f(0) 0. we have f(a) 2 0 for all a 2 0. Note that lim (a) = +00, so f(a) must be positive on (-1,0). The claim follows.
v(a). By direct calculation, we see that f'(a) = a/(1 + d²),
For the following result, consider the filtered probability space (2, FFrs expectations with respect to I.
(FF (JE,, P), and we consider
Lemma A.3. Let XI.... Xn, be a sequence of Fa-measurable random variables. Let Yı.... Yn be any other sequence of F Fk-1-measurable random variables such that the difference is bounded above: A = Yv- Xx > - A for some A 2 0. Define C = 1/ log - and let B Ex (B[X FR-1] -x))). For any 0 < 1/2 A and simultaneously for all n, we have
uttak) 21-c
P LBSCH
Proof. Let v(a) = a - log(1 (1 + a). Define the random variable
M2 = exp (+(E(X& Fx-1] - Xx) - u(t(Yr. - Xx)))
Consider == = x F 1| - Xx) and μ = X F - Yx). By construction, we have
that E|Z F = 0 and Z μ t(Y2 - -xx) AA -. Thus, applying Lemma A. we have
E|M& F < 1.
Therefore Un II
M₁ is supermartingale. By Ville's inequality (Ville, 1939), we have
B < 1/e
sup sup
with probability at least - When this holds, using the definition of U and taking the log of both sides, we have for all n,
X Fa-1l - -x)) Σ ul(ly, Xx)) log
(8)
Defining B = Σ equation we obtain
E X Fk-1l -x)), C = log ! and A₁ = Yt- - Xxs, by rearrange
tB < C+ 1 Σ uttAu):
(9)
as desired.
15

---

Published as a conference paper at ICLR 2025
Corollary A.4. Let X1, X1..... Xn be sequence Fu-measurable random variables. Let Ye....... ....... be any other sequence of FK-1-measurad random variables such that the difference is bounded below: As- = (Y₁- xx) A for some A z O. Let K be finite subset of (0,1). 1). Then, with probability at least 6,
[B|X F Xx)) - AC+EVC.
(10)
where C == n log K1/6, and
A 1 VC (sAAk//s
IXC Yu Yklk=an
min AVC(A-/)//FF sEK
Proof. Let tA. Apply union bound Theorem A.3 over the different values of in K, and take the one that minimizes the bound. Rearrange and isolate terms yields the desired result. D
Theorem A.5. Let XI....,,, Xn be a sequence of - Fi-i-measurable random variables. Let Yn-1. be any other sequence of F₁-1 measurable sequence of random variables such that the
difference is bounded above: Xx Y& S A for some A 2 0. Define V = Ex Yx)² and let E (0,1). Then, with probability at least - ô, we have
1
X Fa-1l -x)) S AC 2VVC,
(11)
T2
where C S (nng 1/0 + 4 log log 6).
Proof. Starting from Lemma A.3, we apply Lemma A.2 of v(a) I a2 + a). For our convenience, here will define A& = Y4 Xg. We have
1
Σ
A
tB s C
1
+
LA
1
8 A3
< C
(12)
n
1-tA
where the second inequality follows from the assumption that A -A
Finally, by defining variance term V Σx A3 = Ex - Y2)² and rearranging equation 12, we see
0 0 (V + BA) (B AC)++C,
(13)
which we recall holds with probability at least c.
Inequality Sketch: This inequality is very close to what we need. The approach would be to optimize over f and then read off the constraint on B. The minimizer of the quadratic is t" B+AC
2(V)
Plugging in this value, one would arrive at
(B + AC)² (1/4)
(B+ AC)² + AA) (1/2)
+C20
(V + AB)
Rearranging,
1
z B + -BCC
1 (B- SVC
and finally,
BC VVV.
At a high level, this determines the overall form of Theorem A.5; however, some technical compli- cations arise from the fact that / must be deterministic and chosen ahead of time, e.g. it must not
16

---

Published as a conference paper at ICLR 2025
depend on the random variables B and C. Instead we will consider optimizing t over discrete set of possibilities (not depending on B or C),, and consider a union bound over the different possibilities.
Full derivation:
Consider the quadratic, equation 13. Its minimizer is given by
B + AC
t"
2(V + AB)
Consider two cases: tt 2 and t"
< A If 2 1.4 then rearranging and solving for B, we see
B S AC 2V/A
which is strictly less than the value AC + 2VVC. and we are done.
Therefore it suffices to consider the case 1 < 1/A, where we can apply Lemma A.3. Note that this result applies for a single i, so it cannot be directly applied to !². Instead, we will turn to quantization and apply union bound. Note that if B 0, using that V A we have t" AC C
22.
Therefore we only need to consider the range: 1" E 2 )
Drawing inspiration from floating point numbers, consider discrete set Q defined as
Q
12
2
k K
== 0, 1..., K 1,bENt
for some K N. Let
((a) = arg minlq - a/.
qEQ
From this, we can determine that the quantization error is bounded by
(4(a) a v
sup aET
K
Define prior over the values of Q:
P(K.,)) = P({)P(()) = 1
K 7(b + 2) + 2))²
By direct calculation, we see that = Ev, P(b) (Ei (b22 / S 1/7, therefore Z < 1.
Now we apply a union bound for Lemma A.3 over values of l E Q. For each Q, set ((t) = Pt)). We have
PP P (V + BA) (B AC. Ceto) <
P PL + BA)= (B + AC Cc(o < 0
< Σ (t) = Σ P(t)
tEQ
tEQ
Therefore, uniformly for all E Q, we have
CVV BA) - (B + AC Cety) 2 0
(14)
with probability at least 5. 8.
Now we plug in = q(t"). Note that 0 < b < loga 2
c so we have
K
log E(l)
log TP(()
< log
log(3 log, 1/C) 2 2og logg + log 1/C)
K
K
< log 8
+ + 2 log log I/C 5 log
+ + 2 log log n
(15)
z
17

---

Published as a conference paper at ICLR 2025
Plugging in this quantized value of t equation 14 and using the quantized error bound, equation 15, we have
(B AC)²
3 ( 1+ ) 1 ( 2C)²
SC+ +
4(V + AB)
K
K) 4 (V + AB)
C(1 +4/K),
(16)
where in the second line we chose a K 2 6 so that we have (1- 3 K (1+ k)) 31+ K. Solving equation 16 for B, we have the inequality
B S AC + 8/K) + (884 +4/K)
S AC(1 + 16/K) 22
(17)
where the second line follows from the fact that vz v vx + vy. Define C C(1 16/K). Choosing K = [16 log 1/6] (which > 6), we have
nC log 1/8 + 1 [log [16 log 1/6]) + 2 + log log n (1 1/ log(1/8))
(18)
Applying some simplifications to equation 17 and equation 18, we obtain
B AC+22/VV
with
C log 1/8 + 4 log n/6 6),
as desired.
A.2 GENERALIZATION BOUND
Converting to Prefix Free Codes Through Kraft-Memillan inequality (Kraft, 1949; McMillan, 1956) binary prefix free code exists if and only if the code lengths & for the different elements satisfy Σ, 2 < 1. Thus if we have L(h) the length of non prefix free code for each h, to find the length of valid prefix code just need find E(h) such that Σn 2 2-((k) < 1. Using ((h) = L(h), the sum would diverge. Instead, consider ((L) = L + 2 log2 (L) 1. Computing the sum, Σn (h)()) = Σ1=1 2-2-(( = Σl=1 21 = π 22/12 < 1. Thus we can convert any non prefix free code into a prefix free code with using L + log,
bits.
use the prior P(h) 132-<(h) A(h) for any countable hypothesis class, placing higher mass on elements with shorter descriptions, closely related to the Solomonoff prior.
Simultaneously,
If we know the length of the object ahead of time, then prefix free code. For a fixed number of parameters N and bits per parameter b, we know the length of the code, and thus can ((h) < 6N.
free to regular code in place of
X²x) with 8(h) <h) for each hypothesis individually, the probability that the bound is violated for arbitrary hypothesis constrained with union bound Σn eP(h) e, and therefore Theorem 3.2 holds with probability at least e (replacing d with in expression). The log 1/6 in Theorem A.5 becomes log 1/8 + log 1/ P(h) & log 1/5 + E(h) log 2.
Weighted Union Bound Applying Theorem 3.1 to the sequence Rs (Xx
A.3 PREDICTION SMOOTHING
Theorem A.6. For the categorical negative log likelihood objective Rs. - Σr k= log ph (Xx
X V classes and C Rt, there exists prediction smoothed model p. (-) = a pr
o/ with worst case loss sup X lologg logps(Xx,
Xx*) & A, that satisfies
R. + CA. R. + C'log V + V2C,
(19)
for some value af C, V) E (0, 1) (approximately C/(1 C)).
18

---

Published as a conference paper at ICLR 2025
Proof. We have
logg, Ps loo ((1 ah +a/V)
S - <-logpn log 11-1--0 a
Noting that Po <*)) 1 A, log(V/a), adding CA to both sides yields
R, CA. S Rs. log(1 a/V) Colog(V/a),
(20)
where the right-hand side is minimized at
VC
(V
+)(+
Note that a is deterministic quantity that we can compute ahead of time based on the model we bounding. Therefore we need not pay additional bits for a union bound over values of a. Substituting into equation 20, we have
R. Run CC, < log + + C'log (V (V-1)(++
C
$ C) + C) Colo(VV/C)
< Colog V + 22C
where the last line follows from (1+z) log(1+ log v 2r for >> 0. The claim follows.
B QUANTIZABILITY FROM THE HESSIAN
We have shown that the quantization gap tends to be quite small in practice, but why is this the case? more complete explanation of why LLMs generalize would need explain why they are readily quantizable, not just why they should achieve a small generalization gap if they are quantizable. In this section we attempt to shed light on why there should exist quantized models which achieve low quantization error using small number of bits per parameter for large models. Here, like in Section 5.2 we focus on demonstrating that these schemes exist, even they are difficult to find or computationally inefficient to in practice.
As starting point the analysis of many quantization schemes (Nagel et al., 2020), consider the Lagrange remainder form of the quadratic Taylor expansion of the loss around given solution of the weights 0, with 0 being our desired quantization. From this expansion we have
I(( T.)) + g T 0) (Ø 0) H O)
holding with equality for evaluated at 0 and the Hessian H evaluated at an unknown but fixed point & on the linear path between 9 and ê, and with no higher order terms. If we use a stochastic rounding algorithm that is unbiased, then the first order term can be neglected as
BBg (0 0)] 0,
and high dimensional vector 9 ensures the sum will concentrate around the expectation. This leaves the quadratic form with the Hessian. This quadratic form is what many adaptive rounding schemes minimize through the design of their algorithms and their analysis.
A key property for low precision quantization of the weights (while minimizing the quadratic quantization error) is that the scale of the individual components of the eigenvectors of H do not differ by large extent. If they do, then the quantization range must simultancously provide coverage over large range values. This criterion is formalized through the notion of incoherence, introduced in Chee et al. (2024), which we briefly present below with simplification of their more general analysis.
B. INCOHERENCE
Hessian p-incoherent if the eigenvectors in the decomposition QAQT Hl NNN satisfy
Vi, : 1uil S W/VN,
19

---

Published as a conference paper at ICLR 2025
and a parameter vector is j--incoherent if it satisfies Vj |8,| I plllll/V/. Intuitively this condition can be understood to be stating that the elements are not much more extreme in magnitude than that of equivalently sized Gaussian random matrix Gaussian random vector.
key insight from QulP (Chee et al., 2024) is that rather than quantizing the weights 6, one should look to quantize the weights after applying a random orthogonal transformation matrix P E RNN Even as the original weights 0 and eigenvectors Q may be more sharply peaked for certain dimensions, multiplying by a random matrix helps to spread these extreme values across dimensions leading to more similar range of values and more easy quantization.
Let w P and likewise
Pw. Applying this Gaussian random matrix, the Hessian is transformed: H. = PT H and likewise the cigenvectors Q from Hg = QAQ" are also multiplied Q + P. If we choose
random Gaussian matrix: (O, L/ N Q preserves the spherically symmetric distribution. Therefore, the eigenvectors Q P of H. are (0, I/N) N distributed. Applying union bound over the Gaussian tail probability of the N
xN applying rotation by
21og(2N3/8] with probability 1- â and
elements, the maximum absolute value entry of Q is at most
N
therefore incoherent with /2log(2 This level of incoherence after applying the random transformation makes for easy quantizability. and as we will see in the next section it has implications on how the quantizability changes with the number of parameters N in the neural network.
B.2 SCALAR LDLQ
QulP introduces the LDLQ quantization algorithm which quantizes weights sequentially and autore- gressively taking into account how previous quantized values impact the quadratic Taylor expansion of the loss. Applying LDLQ to the entire vector of weights w rather than block by block, one has the following relation the quantized weights w. Let L DL H be the LDL decomposition of H = P HoP, P, then we can express the quantization of the weights as
à Q(w (L 1)(w 1ou0-ii] -))
where Q quantizes the weights element- wise with nearest or unbiased stochastic rounding. As L is a lower triangular matrix, the full ú can be quantized sequentially in an autoregressive manner. With this quantization scheme, Tseng et al. (2024) prove that the error of the quadratic in the Taylor expansion satisfies
1²02 N (222,
(w -
()
(21)
where the pointwise quantization error of the scalar quantizer is assumed to be ([((())- - =x) 5 0² (see Theorem 4.1 of Chee al. (2024) applied to block size 1 and a single N x 1 weight matrix), where 0² is function of the bitrate. For example I E [0. 1]. then a uniform grid would achieve σ² = 2 26-2 for bits per parameter. The range of x is not [0. and constraining the number of bits required for more sophisticated schemes requires additional analysis, but for illustrative purposes we will use x² 2-26-2 Putting the pieces together, we have that the difference loss between the quantized model and unquantized model is
L(t)) - L(w)= < 2log(2N2/8)2 26-2
1222
N
for H evaluated at some point E on the linear path between á and w. Setting the acceptable quantization error Q = L(w) - L(w) we can solve for b, finding
(T(H)1/2 + (1/2) log, 1og(2N2/8) 1/2.
b < log2
VNQ
1/ VNQ
Here we see that the number of bits per parameter required depends most heavily on log,
If the spectrum of H is such that T/2) scales slower than V (such as if H were low rank or has a spectrum the decays sufficiently rapidly), then the number of bits required for quantization at fixed loss decreases with scale. In the following section we provide some empirical evidence that indeed this is the case, and hence why larger models become more quantizable (even the quantization scheme is impractical to implement).
20

---

Published as a conference paper at ICLR 2025
B.3 ESTIMATING Tr(H1/2)
To estimate the trace of the square root of the Hessian matrix, Tr(H1/3), we begin by assuming that the Hessian is positive semi-definite (i.e., contains no negative eigenvalues). The square root of the Hessian, denoted S, can be expressed as:
S E-Eo N
where X; and 6; represent the eigenvalues and corresponding eigenvectors of the Hessian, respectively, Consequently, the trace of the square root of the Hessian is:
12( Σ - p(A)VAdy
where p(A) is the spectral density function associated with the Hessian's eigenvalues.
direct computation of the full eigendecomposition to obtain Tr Tr(FF1/2 has a computational com- plexity of (nn²), which is infeasible for large models. Instead, we employ stochastic spectral density estimation techniques (Granziol et al., 2018; Papyan, 2019; Ghorbani et al., 2019), which scale linearly with the number of parameters. The key idea involves using the Pearlmutter trick (Pearlmutter, 1994) to efficiently compute Hessian- vector products:
V(VL Ho,
where random vector. This allows us approximate the trace by leveraging the identity:
Tr(H): Tr H)) E He).
assuming v has zero mean and unit variance. These stochastic methods are well-established in machine learning (Fitzsimons al., 2017; Dong al., 2017).
Building upon the work of Ubaru et al. (2017), we can derive an explicit bound on the estimation of Tr( using stochastic Lanczos quadrature (SLQ).
Theorem B.1. Let E Taxx be a symmetric positive definite matrix with eigenvalues ordered as (0,1), 1), if the SLQ parameters
A1 2 A2 2 2 An and condition number satisfy
As, For any c, (0,
X..
VK
K (Lanczos steps),
log
24
2
n, 2
log
(Rademacher vectors),
where K = (Amax Amin) Xmin)( 1)2 then the output T of stochastic Lanczos quadrature satisfies:
Tr Tr(VH) H - TrVHH)
Pr
< 21-n
The proof of this theorem is provided in Section B.6. However, we observe that the bound on the trace provided here is overly conservative for practical purposes. Therefore, we also establish result demonstrating self-averaging, which shows that the estimator converges to the true value based on single random vector.
Theorem B.2. For a single random vector the signal-to-non ratio of the trace estimator for matrix H E guxn, where the spectral moments of H do not depend on the matrix dimension, scales as:
Var( HU B Ho)
On
We utilize the CoLA (Potapezynski et al., 2023) library to compute the spectral approximation of the Hessian. This involves leveraging the relationship between the Lanczos matrix and Gaussian quadrature (Meurant & Strakoš, 2006; Granziol al., 2019). However, these concepts are highly
21

---

Published as a conference paper at ICLR 2025
Spectral Density P(X)
Spectral Density P(A)
Spectral Density P(A)
Qematoy
Eigenakiees
Eigerinties
Signnwalues
(a) Dataset Fraction 0.01
(b) Dataset Fraction 0.001
(c) Dataset Fraction 0.0001
Figure 4: Spectral density plots of the 70M parameter Pythia model trained varying fractions of the Pile dataset using the same data and random vector seed.
specialized and may not be familiar to all readers. Therefore, we provide high-level overview without delving into the intricate mathematical details.
Figure 4 illustrates the spectral density of a 70M parameter Pythia model trained on different subsets of the Pile dataset (Gao et al., 2020). Specifically, as we decrease the number of training samples-frow from 1 1% (Figure 4a) to 0.1% 1 (Figure 4b) and further to 0.01% (Figure 4c) observe an increase in the largest eigenvalue and an increase in the mass of negative spectral density. These phenomena are consistent with previous studies on ResNets and VGGs, where spiked Wigner random matrix theory models have been employed to understand such behaviors (Granziol et al., 2022).
Future work aimed at establishing tighter empirical bound could explore advanced random matrix theory techniques (Bun et al., 2017), potentially utilizing the variance of the Hessian (Granziol et al., 2022). In this study, adopt simpler approach by shifting the Hessian spectrum by the magnitude of the largest negative eigenvalue, thereby ensuring a positive semi-definite Hessian and providing a trivial upper bound.
From Figure 4b, we observe that the variance of each estimator remains low and that convergence is achieved with relatively few Lanezos iterations. Additionally, Figure 5 demonstrates that varying the random vector introduces minimal variance, while different data subsets do exhibit some variance, as indicated by the error bars computed over three different seeds (see Figure 5b). For clarity, Figure 5a provides another example of the spectrum with different seed vector on the same subsampled dataset, showing negligible differences compared to Figure 4a.
Spectral Density P())
Estimator Subsample 0.01
Estimator Value for Subsemple 0.01
1000
Eigensakuaa
Lanczee Iteration
Lancooa Iteration
(a) with Different Vector
(b) Convergence with Iterations
(c) with Fixed Data Subset
Figure 5: Comparison of spectral density and Tr(y H) estimations for different subsample sizes and configurations.
With confidence in the accuracy of our estimations for Tr(H and the Hessian spectrum, we can interpret the implications for model quantization. Despite the high dimensionality and the presence of many distinct eigenvalues, the Hessian spectrum decays rapidly in density. This indicates that 1/2) grows sublincarly with the model dimension, rather than exhibiting the worst-case lincar scaling. Consequently, as model size increases, the ratio I(hh) is expected to decrease, allowing for a more favorable tradeoff between the bitrate and the quantization gap. This supports the hypothesis that larger models on the compute-optimal frontier are more easily quantizable, thereby contributing to their improved generalization performance.
B.4 STOCHASTIC TRACE ESTIMATION IMPROVEMENT WITH MODEL SIZE
Here, we provide the proof that for spectrum independent of model dimension, the stochastic trace estimator has a bigger signal to noise ratio as a function of dimension.
Lemma B.3, Let u E IR' Px1 random vector, where u, is zero mean and unit variance and finite 4th moment E. E
m4. Then for H RR. PxP have
22

---

Published as a conference paper at ICLR 2025
(i) Blu" Hu Tr H (ii) Varlu Hu) S (2 + m4) Tr(H"H)
Proof. For the expectation, we see
P E| Elu Hu) = Σ
P
= Σ H. H,,
H - H.
For the variance, we have
BlI|u² Hu
12]
H H Eu u
H H (0 + d1,18 + 8e,b +mddijanl
k.l
= (Tr H)² (2 + m4 (
whence (ii) follows.
Let us consider the signal to noise ratio for some positive definite H > cl
Var u Hu
V m4
H
2 +
m4 P
(X2)
(22)
R Hu
T H
(A)
where we denote the mean eigenvalue (A) and the mean square eigenvalue similarly.
Remark B.4. Note that my is 3 for the Gaussian case and for the Hutchinson trace estimator where the entries are =1 with probability half, which justifies its use.
B.5 DERIVING THE IMPACT OF Low PRECISION LANCZOS
Consider a number taken from our Hessian matrix ai,, which can be represented as ( (-1)22"s. As the exponent for FP16 has 5 bits, it has a range of 25 1. Since the expoment always integer, there is no loss of information in the range. This means the error is in the significand, which has 6 bits after the 1. Thus, we have e = 10-7
Then, see that
[1.1 + N(0,e)) 02.
d,2(1++
a1 + N(0, e))
02 (2000)(((0ee)
0g (1 + ()),
H
00m,
(0,
am +N(0,c))
am (1 +N((0))))
a1,1N(0, c) a2 N2,
a1,2/(0,e)
a1 (0.e)
a2,2((0,e) a2 N(.
H +
Lam,1N (0,,)(
((,e))
Now under certain assumptions on the elements of the perturbation matrix (essentially the a,,j does not vary too wildly or have wild dependencies) this becomes a Gaussian orthogonal ensemble (GOE)
again. Then using the Frobdyenius Norm, we see that the spectral width will be of order ((x2). which depends on the square root of the average eigenvalue squared of H. Anything within this will be noise. This is because En, a = P()²). An obvious upper bound of this would be eλi but this will likely be super loose. Note that the vast majority of the already broadened spectrum is already very close zero, so we would expect this be even more extreme for the unbroadened version.
better strategy might be to sample the noisy version of of, perhaps using the diagonal approximation, and note that in expectations
expect the square be (1 c²) the size of its non noisy counter part, which gives an an estimation equation
Pe Pe N di
2(1+e)
23

---

Published as a conference paper at ICLR 2025
B.6 STOCHASTIC LANCZOS QUADRATURE PROOF
Theorem B.5. Consider a symmetric positive definite matrix A E R with eigenvalues enumer- ated in reverse order of size X1 Z 22...2 SLQ parameters satisfying
2 An and condition number &
d1. For E, E (0, 1) and An.
log,
V log Lanczos steps
(i) m 2 log v--1
(ii) nr 2 34 log d
Rademacher vectors,
where K = (Amaz Amin) (VK 1)?. The output I of stochastic lanczos quadrature is such that
A A)
r S 21-1
Pr
(23)
Proof. The proof follows trivially from Ubaru et al. (2017), where we simply take the more general proof and instead of the general function f(A), take f(x) vz. The second inequality for m is directly from the paper, but the tighter bound is also available just buried.
The proof sketch goes as follows. We bound the enror from the Gauss quadrature rule. We start with function analytic in the interval [-1, 1j. Knowing that the Gauss quadrature rule is exact for any polynomial up to degree 2m 1, we bound the sum from 2m + to infinity using Cauchy-Schwand We use results from Chebyshev coefficients, symmetry and the interval boundaries to get
AVA
(0² 1)
where is the sum of the major and minor axis of the Bernstein elipse. We shift the spectrum so that it is in the interval 1, 1]. c.g this implies the factor of Á= The shifted function is not analytic for
x² 1++1 so this will serve as our major axis. Now as a + ff= = and the focus is = Va² 62 x-1
where we take our major axis a in this case to be a. We then have our rate of convergence = a + through some algebra to be yx+1 /K-T" This gives the value of K. This is combined with the error of the trace estimator from Roosta- Ahooa-KKo Ascher (2015) and Cauchy-Schward obtain the final result.
24


Reviews:
[{"review_id": "FjNwKoFByy", "reviewer": "Reviewer_RfBZ", "summary": "This paper investigates why LLMs generalise better, using new theoretical bounds that quantify generalization in LLMs. Authors introduce an empirical Freedman-type martingale concentration inequality refining generalization sounds by considering the variance in the loss function, and influenced by 1) The parameters per token 2) The loss variance and 3) The quantisation error. They show that generalization gap decreases predictably as LLMs scale up. The bounds are empirically tested using Pythia model checkpoints on the Pile dataset, illustrating how loss variance and quantisation error decrease with scale. Last, they argue from an information theory perspective that information content in a model grows sublinearly with scale, allowing models to generalize better with fewer bits per parameters, hence improving quantizability.", "questions": "— Have you empirically tested the argument on quantizability from the Hessian spectrum and QuIP framework beyond GPTQ? \n— The information-theoretic argument using prequential coding is interesting but could benefit from further empirical support. Have you tested the information content predictions under varied trading or scaling setups? For instance, would be nice to understand how your complexity term $L(h)/D$ changes for models trained on different datasets or architectures\n— Are there any specific factors that you believe yolk affect the generalization bound accuracy? Eg. Dataset size, architecture choice", "limitations": "", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "The paper stands out for its ambition in taking down a complex question with originality, and its potential to inform future model scaling and generalisation research in LLMs. The use of a Freedman-type martingale concentration inequality, which incorporates the empirical variance of the loss function is both creative and original. The focus on optimal scaling through the chinchilla law, along with a brand new perspective (to my knowledge) on quantizability and information transfer, showcase originality. The authors well motivate the use of Freedman inequality by the need for higher bounds. The choice to base the empirical evaluation on the Pythia model also provides a reasonable foundation to explore the theoretical claims.", "weaknesses": "While the paper makes an ambitious attempt to understand generalization in LLMs, there are a few core weaknesses. The theoretical assumptions and methods could benefit from further grounding and justification. The empirical Freedman inequality and the notion of loss variance lack through derivation and validation across different settings, which may leave doubts about the generality of these bounds for LLMs in diverse applications. The empirical results, are limited to the single Pythia model architecture, constraining the scope of the findings (Paper would benefit expanding the evaluation to other widely-used LLMs eg. GPT, T5, BERT…). Moreover, some sections are overly technical without sufficient motivation, making presentation difficult to follow, especially for the proposed quantisation bound and its integration with the chinchilla scaling laws. Some of the notation is dense, and (if) introduced with minimal intuition. Examples:\n\n— $\\Sigma$: The term “loss variance” that is central is introduced without a clear mathematical definition or discussion. A clarification whether this variance refers to the empirical variance of the loss function over tokens or across model params would make it more understandable.\n— $C$ The complexity term is introduced with very limited intuition and authors do not explain how this is derived, or what aspects of model size, dataset, or quantisation contribute to it.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "xyncY34SgP", "reviewer": "Reviewer_JfkK", "summary": "This paper explains the high generalization performance of large language models (LLMs) by introducing a new Freedman-type concentration inequality and constructing a generalization bound based on the Chinchilla scaling law. The generalization bound is decomposed into three factors: the number of parameters in the model, the token-wise loss variance, and the performance gap associated with quantization. This bound quantitatively shows how the generalization gap reduces as the size of the LLM scales. In particular, it shows that the amount of information grows sublinearly with the LLM size, indicating that the resources required for the model to efficiently integrate information are reduced. This finding provides an information-theoretic explanation for why LLMs can improve generalization ability with computationally optimal scaling and point out a new relationship between the model size and information.", "questions": "* As shown in Eq.(6), for example, it is explained that $K(h)$ is scaled by $\\tilde{O}(D^{1-\\beta})$, with this exponent $\\beta$ coming from the Chinchilla scaling law. If this exponent $\\beta$ can take a non-trivial value, is it possible to constrain its value using the authors' theory?\n\n* The implications of the theoretical results are discussed in Sec.5.3, but I'm not entirely sure I understand the argument. I assume the authors focus on Pythia due to the availability of models with various parameter sizes; however, investigating other language models in the same way may be difficult. Given these limitations, how do the authors envision extending this type of analysis? Could they elaborate on potential insights or outcomes if similar analyses were feasible for other models?\n\n* Minors\n* The citation to the appendix on line 186 should be \"Appendix\" rather than \"Section.\" There are several similar cases.\n* Please check the ICLR format for citing equations.", "limitations": "", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The authors' approach to explaining LLM performance improvements by breaking down the generalization bound into three key components is particularly valuable. Furthermore, introducing a new inequality based on martingale concentration enables analysis specific to LLMs, where data is non-independent and identically distributed. It opens up a new path to theoretical understanding of generalization performance. This is a significant contribution to LLM research.", "weaknesses": "This paper contributes to the theoretical understanding of LLMs and confirms their validity using real LLM data. However, further verification is needed for practical applications. In particular, the merits of decomposing the generalization bound are unclear from the demonstrations in Fig.2(right) and Fig.3(center), for example.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "FqtJejoflb", "reviewer": "Reviewer_y45d", "summary": "This work provides a novel generalization bound for LLMs consisting of three components depending on the ratio of the number of parameters to tokens, loss variance, the performance gap from model quantization. The paper first provides a new martingale concentration inequality that can be evaluated empirically. The rest of the components of the bound come from loss variation, a smoothing constant, and quantization gap, all of which can be computed empirically. Experiments show that the obtained bounds are very close to evaluated loss functions in LLMs. The paper also provides an alternate bound based on information accumulation in LLMs using prequential coding, which is a less empirical bound. Nevertheless, gives insight on model complexity with changing model scale while keeping the ratio of dataset to parameters constant. Overall, the paper provides novel generalization bounds for LLMs with interesting insights to the working of LLMs and how they vary with scale.", "questions": "- A general question: Are the empirical bounds extendable to LLM performance with inference-compute scaling?, e.g. in [1]\n\n[1] Sardana, Nikhil, et al. \"Beyond chinchilla-optimal: Accounting for inference in language model scaling laws.\" arXiv preprint arXiv:2401.00448 (2023).", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper presents two interesting generalization bounds for LLMs, one of them can be empirically calculated and shows results close to actual loss obtained in experiments. The other bounds gives insight on generalization bounds in LLMs with increase in model size with constant data to parameters ratio.\n- For computing the first bound, the model derives a new concentration inequality based on the Freedman’s inequality that can be empirically computed and is likely to be of interest in future works.\n- The empirical evidence provided in the paper showing that it is close to the obtained bounds in interesting.", "weaknesses": "- It would be good to improve the readability of the paper a bit by distilling down the mathematics and giving an intuition for both the bounds in summary.\n- It would be better to provide the empirical evidence after both the bounds instead of providing it in between. E.g., some plots are provided in Sec. 5, whereas the empirical evidence is given in Sec. 4.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "HN8HsEYw8R", "reviewer": "Reviewer_wrVe", "summary": "The authors present a new upper bound on the single-token generalisation error of language models. Evaluations of this bound are compared with selected empirical data from the training history of a language model.\n\n\nEDIT: I have raised the score, on the understanding that the authors will amend the title as discussed and significantly clarify the exposition of the theorems, including to clearly state that the 'with probability 1- \\delta' refers to the sampling of both the X_k and Y_k.", "questions": "Please see the questions in the Weaknesses box.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "The authors' main result is interesting: an apparently novel generalisation bound which can be evaluated from data. The comparisons they make between their bound and empirical data is also of interest. Hopefully this bound will be useful in future for more efficiently guiding the development of AI models", "weaknesses": "1. I am left wondering whether this is really an appropriate venue for this work. Proving the results stated in the actual paper requires 10 pages of dense technical appendices introducing a wealth of additional lemmas, theorems and corollaries which are not reviewable in the timeframe. The results themselves do not appear to be standard, and I feel would benefit from a proper presentation in a format, such as a journal, which gives sufficient space for a detailed investigation of the technical details.\n2. The statement of several of the main results do not appear to be complete, and require extra clarification. In particular, the authors should take care to ensure that all notation is defined.\n    - Does the 'with probability $1 - \\delta$' in Theorems 3.1, 3.2, and 3.4 refer to the sampling of $X_k$, $Y_k$, or both? If both, the authors should clarify how their results on the *joint* probability of $X_k$ and the fictitious random variable $Y_k$ can be connected to standard generalisation bounds which look at the probability with respect to $X_k$. The random variables over which probabilities are being measured should be explicitly stated in all results.\n    - The random variables $Y_k$ implicitly appear in the result of Theorem 3.4 (through $\\Sigma$), but are not defined in the statement of the theorem.\n    - In Theorem 3.1, what is $\\mathcal{F}_k$? I expect this is some form of filtration, but it is undefined.\n    - In Theorem 3.1, ${X_{k}}$ are ${\\mathcal{F}{k}}$-measurable, while $Y_k$ are $\\mathcal{F}_{k-1}$-measurable. Given the ambiguities of the notation, it is unclear what this distinction actually refers to.\n    - The term 'NLL' is frequently used throughout, but is never defined.\n3. In Theorems 3.1, 3.2 and 3.4, the size of the finite set $K$ is a key component of the 'complexity' measure $\\mathcal{C}$. Yet, $K$ itself seems to be just a technical construction in the proof, rather than something fundamental to the model. The authors should clarify what role this set plays, and why it should be considered as part of the complexity of the model, rather than simply an artefact of the proof. They should also indicate how this set can be chosen in practice (since the bounds are supposed to be computable). I see from Section 4 that they use 1000 points, but offer no indication of why this choice was made.\n4. Additional random variables $Y_k$ are introduced and used in most of the main results. The authors state after Theorem 3.1 that they take this to be the mean of the model NLL, but I do not see what this can be guaranteed to satisfy the requirement that $Y_k - X_k > -\\Delta$ (and how is the value of $\\Delta$ chosen for this setup?). In fact, why not just take $Y_k = X_k - \\Delta + \\epsilon$ for some fixed value of $\\Delta$ and a small value of $\\epsilon > 0$? I do not see anything in the statement of the theorem preventing this, and it appears to optimise the bound.\n4. The authors only compare their computable bound to empirical data for selected so-called 'compute-optimal' checkpoints. Why is this choice made? How does the bound compare for other checkpoints? This does not appear to be a requirement of the theorems, and so the rationale should be made explicitly clear.\n5. I am not convinced that the results presented by the authors justify the claim in the title. It seems to me that, in fact, their results show that increasing the size of the model will in general *increase* their generalisation bound, by increasing the complexity term. In fact, the authors themselves appear to advocate for compressing and quantising models. The authors should explicitly justify such a strong claim in the paper, or change the title to better reflect the results they present.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "SGBwfKRTIz", "reviewer": "Reviewer_dkJs", "summary": "Building on an empirical version of Freedman's inequality - a concentration bound for martingales - the authors derive generic generalization bounds for large language models. These bounds are obtained in a PAC setting and do not take into account the training of the neural network considered or the model's precise architecture. They are empirical, meaning that they can be computed in practice with a limited computational budget, and are shown to hold for a single architecture and dataset. The authors then argue that these bounds get tighter as the number of parameters increases by analyzing information accumulation within the model.", "questions": "* Could you please provide supplementary thorough explanations of section 5 ? I am puzzled by the arguments made here. \n\n* In regard of this last question, could you consider including a supplementary part which gives more background on these ideas ? \n\n* Could you give mathematical details on how your proof techniques rely on the results of Lotfi et al. (2024a) ? In the worst case, if these results were to be false, would your analysis still hold ?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "**On the overall presentation of the paper.**\n\nOverall, the paper is well written. The contributions are explained in great detail and are not overstated. Most of the mathematical and theoretical background needed to understand the article is provided in the main text. Figures are clear and well designed. \n\n**On the empirical version of Freedman's inequality.**\n\nThis theorem and its consequences for empirical loss minimization are the central contributions of this article. I believe this concentration bound to be valuable and interesting, mostly because of its empirical variance part which can be approximated as the solution of an optimization problem on a discrete real-valued grid. \n\n**On the derived generalisation bounds.**\n\nThe authors combine this bound with the smoothing technique of the model of Lotfi et al. (2024a), which in a nutshell convolutes the model with a uniform distribution to smoothen the prediction function, hence incurring an error but providing an interesting proxy of the empirical unsmoothed loss. Theorem 3.4 then combines this technique with the empirical Freedman's inequality to obtain a quite generic (i.e. model and training independant) generalization bound.", "weaknesses": "**On the comparison with related work.**\n\nWhile the authors cite some related work on generalization bounds for deep models, their literature review lacks in my opinion a precise comparison with previous approaches. In particular, I would enjoy both a theoretical, mathematical and empirical comparison of the derived bounds with other bounds present in the literature - see their section 6. \n\n**On the tightness of the generalization bounds.** \n\nFrom what I understand, the generalisation bounds display a strong linear dependency in the number of parameters - at least in the form presented in theorem 3.4. The authors later on argue that this bound can be improved, by improving on the inequality $L(h) \\leq bN \\log 2$. While interpretable and empirical, these bounds display an extreme dependence in the number of parameters, which is undesirable in the case of LLMs. \n\n**On empirical evaluation.** \n\nThe validity of the author's claims is assessed on a single LLM on a given dataset. I am unsure whether this evaluation is sufficient. I have little experience in the evaluation and training of LLMs, hence my analysis of this part is limited. I will revise my judgement based on other reviews and discussions with the authors. \n\n**On Section 5.**\n\nMy principal concern lies in the arguments made in section 5. The authors argue that while their bound is linear in the number of parameters in the form presented in Theorem 3.4, one can refine this bound and obtain a bound which is independent of $N$ the number of parameters. This section is not clear and hard to understand --- I stress that I am not familiar with prequential coding and might hence not be the targeted audience here. In the end, I do not understand how the authors conclude from Equation $(6)$ that their generalization bound improves with the number of parameters. From what I understand, the authors claim that their bound improves as the number of parameters increases only if the size of the dataset increases as well. If this is the case, I believe that the significance of their results is overclaimed.  \n\n**Supplementary comment.**\n\nI also raise to the other reviewers and chairs attention that this article relies on the smoothing technique designed by Lotfi et al. (2024a). The validity of the results of this paper has been questioned during review (see https://openreview.net/forum?id=GY1fKFXG5i&noteId=s9ciWh5QAI) leading to a rejection of this paper at another conference. While I am unable to assess whether this interrogations are justified, and if the possible errors in this paper might carry over to the results exposed here, I believe that this information should be shared among reviewers and chairs.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)