Unlocking Tokens as Data Points for Generalization Bounds on Larger Language Models
Authors: Sanae Lotfi
Yilun Kuang
Marc Anton Finzi
Brandon Amos
Micah Goldblum
Andrew Gordon Wilson
Venue: NeurIPS 2024 spotlight (2024)
Keywords: Large language models
generalization bounds
generalization
compression
Primary area: generative_models
TL;DR: We compute token-level generalization bounds for large language models at the scale of LlaMa2 70B.

Abstract: Large language models (LLMs) with billions of parameters excel at predicting the next token in a sequence. Recent work computes non-vacuous compression-based generalization bounds for LLMs, but these bounds are vacuous for large models at the billion-parameter scale. Moreover, these bounds are obtained through restrictive compression techniques, bounding compressed models that generate low-quality text. Additionally, the tightness of these existing bounds depends on the number of IID documents in a training set rather than the much larger number of non-IID constituent tokens, leaving untapped potential for tighter bounds. In this work, we instead use properties of martingales to derive generalization bounds that benefit from the vast number of tokens in LLM training sets. Since a dataset contains far more tokens than documents, our generalization bounds not only tolerate but actually benefit from far less restrictive compression schemes. With Monarch matrices, Kronecker factorizations, and post-training quantization, we achieve non-vacuous generalization bounds for LLMs as large as LLaMA2-70B. Unlike previous approaches, our work achieves the first non-vacuous bounds for models that are deployed in practice and generate high-quality text.

Unlocking Tokens as Data Points for Generalization Bounds on Larger Language Models
Sanae Lotfi !
Yilun Kuang
Brandon Amos
Micah Goldblum
Marc Finzi*
Andrew Gordon Wilson'
New York University Meta AI
Columbia University
*Caregie Mellon University
Abstract
Large language models (LLMs) with billions of parameters excel at predicting the next token in sequence. Recent work computes non-vacuous compression- generalization bounds for LLMs, but these bounds are vacuous for large models at the billion-pann parammetrrrtterrreeeee scale. Moreover, these bounds are obtained through restrictive compression techniques, bounding compressed models that generate low-qualing text. Additionally, the tightness of these existing bounds depends on the number of IID documents in training set rather than the much larger number of non-III constituent tokens, leaving untapped potential for tighter bounds. this work, we instead use properties of martingales to derive generalization bounds that benefit from the vast number of tokens in LLM training sets. Since a dataset contains far more tokens than documents, our generalization bounds not only tolerate but actually benefit from far less restrictive compression schemes. With Monarch matrices, Kronecker factorizations, and post-training quantization, non-vacuous generalization bounds for LLMs as large as LLaMA2-70B. Unlike previous approaches, work achieves the first non-vacuous bounds for models that are deployed in practice and generate high-quality text.
achieve
Introduction
Despite the impressive empirical performance of large language models (LLMs), our theoretical understanding of their performance is lacking. PAC-Bayes and the related finite hypothesis general- ization bounds [5] [77 offer a compelling framework for understanding this good performance through the lens of compression. These bounds tell us that model will provide good generalization is capable of fitting its training data while simultaneously being compressible relative to the size of its training set. The generalization bounds literature includes many techniques for achieving tighter bounds on image classification problems, ranging from improved bounds themselves to new compression methods [53 14
18 38 31.
Recent work presented the first non-vacuous generalization bounds for large language models, con- sidering training points to be independent and identically distributed (IID) documents [32] The authors compute generalization bounds for the expected bits-per-dimension (BPD) loss, defined for document X composed of k tokens and a language model h as the average negative log proba- bility BPD(h, X) - > log, Pa (I: (r))). These bounds are only non-vacuous for compressed
"qqual contribution, order decided by coin flip. Correspondence to: Sanae Lotfi <s18 1s18160@nyy.ccm nyu.edu>, Yilun Kuang <yilun kuang @ nyu.edu>, Andrew Gordon Wilson <andrewgw @ww.w..mmmmuuu....m fec.es..y...uu.. AMeta-afiilatte author was involved only in an advisory role. All experimentation and data processing were conducted at NYU.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

GPT2 variants [39 that output un grammatical text. The term vacuous refers to the random guess performance on next token prediction, which is log, for BPD where V is the vocabulary size.
Compression-based generalization bounds at the document level suffer from three primary limitations: (1) the number of documents in training set is limited, and this small sample size leads to loose bounds; (2) due to the small sample size, non-vacuous generalization bounds can only be achieved using compression techniques which significantly modify the LLM pretraining routine. This limitation also applies to state-of-the-an generalization bounds for image classification, which heavily alter the training procedure to optimize the bounds [53] 38 31;; (3) as a result, the models which produce non-vacuous bounds generate low-quality text, so it is unclear what these bounds can tell us about more performant language models.
In this work, we address the above limitations and use our bounds to derive insights about the generalization properties and limitations of L.MMs. Namely, we make the following contributions:
In Section we derive a new generalization bound that considers each sample to be an individual token. Even though tokens within document not independent, we use properties of martingales to obtain a valid bound that benefits from the number of tokens in language model's pretraining dataset.
In Sections 5 and G we explore several expressive model compression techniques such as Monarch matrices, Kronecker factorizations, and post-training quantization and show that bounding the performance at the token-level favors less restrictive compression strategies.
Our work is the first to compute non-vacuous generalization bounds for models compressed only through post-training quantization and without altering the pretraining procedure at all. Consequently, we obtain generalization bounds for massive pretrained LLMs like LLaMA2-70B, shown in Figure Left) and Section 6 which generate high-quality text.
Our experiments in Section 6 indicate that the chat versions of LLaMA have looser gener- alization guarantees, demonstrating that fine-tuning these models for dialogue negatively affects their performance on the next token prediction task.
In Section 6.4
we demonstrate that GPT2 models that are restricted to only seeing k tokens in their context for training and evaluation obtain significantly better bounds than k-th order Markov chains for high values of k, reflecting the remarkable ability of transformer-base models in capturing longer range correlations.
We show in Section 6.5 that a model's 's ability to recall memorized facts from its pretraining data deteriorates faster than its ability to recognize structured patterns as we decrease the size of the model through compression, distinguishing between compressible tasks where generalization is possible and incompressible tasks that correspond to sheer memorization.
We make our code available here
2 Background
In this section, we review the different components of compression-basee generalization bounds, which we build upon with our method in Sections and 5
Finite hypothesis compression bounds. Let R(h, x) E [a, a + A] be a bounded risk and H be a hypothesis drawn from finite hypothesis space with prior P(h). A classic finite hypothesis
generalization bound 4 states that for any 6 >> with probability
/lg 1/P(h) + log 1/6
R(h) < R((A) + +
2m
where the empirical risk is defined as f((h) = 1 Em R(h, x;)) with {x))²= being IID and
vn
R(h) = R.h).. The complexity term depends on the prior log probability log 1/h().. We use the Solomonoff prior P(h) < 2 2-)(M) 45), where K(h) is the prefix Kolmogorov complexity of
defined as the length of the shortest program that produces h for a fixed programming language
23 Consequently, our prior favors models h that have small minimum compressed length. While the Kolmogorov complexity is incomputable, it can be bounded as log 1/P(h) I ((h) log 2 S
C(hh) log 2 + 2 log C(h), where ((h) is the compressed size of the model according to pre-specified

---

LLaMA1
LoRA
LLaMA2
Train BPD Loss
3.0
Validation Loss
Kronecker
LLaMA2-Chat
Monarch
2.8
BPD
2.6
10
10
10"
10"
10
10"
Compressed Model Size (MB)
Compressed Model Size (MB)
Trainable Parameters
Figure 1: Non-vacuous bounds for LLMs that scale up to 70B parameters. Left: Bits per dimen- sion (BPD) bounds on the Amber dataset [29] which contains 1.2 trillion tokens for different LLMs from the LLaMA family ranging scale from 7 billion to 70 billion parameters [47]. All of these models are quantized to 2-bits, 3-bits and 4-bits per-weight using QulP# and are publicly available 48. The different quantization precisions are accounted for in the compressed model size. The trade-off between the empirical performance and the model complexity in our bounds favors models with smaller compressed size general, though we observe that across different architectures we can find larger models yielding better bounds. Middle: The BPD training loss for different models from the LLaMA family- the legend shared with the figure on the left. Overall, we observe that larger models yield lower BPD while having higher compressed size. Right: Validation negative log- likelihood loss as a function of the total number of trainable parameters for different nonlinear parametrization; namely low rank adaptation (LoRA), the Kronecker decomposition of dense matrices and Monarch matrices. The x-axis is in the log scale. As we vary the number of trainable parameters, there are different optimal compression techniques.
compressor. Therefore, we can find the right trade-off between the empirical risk and the compressed size of the model by tuning the extent of compression, hence the different compression techniques we explore this work.
Compression bounds for LLMs. When constructing document-level bounds for language, the em- pirical risk is defined over entire document X R(h, X) log, Ph (x)(()))))))))))))() (X)/T, where pa pa (X) is de- [x1 22, 22. ... ] as po (X) II (xs
fined auto-regressively on the sequence tokens X
where Jzz denotes #1, 222. -I,-1
Prediction smoothing. Since the bound in Equation [ only applies to bounded risk. it is not valid for the biss-eerdimmenioon loss that is unbounded. In this case, one can introduce prediction smoothing probability to the predictive model such that the generative probability distribution becomes a mixture between the next token probability according to the auto-regressive model f() with parameters 0 and uniform distribution over the vocabulary of size as follows: Pa(r; (x, (1 a)Pa (x))) + a/V. With this construction, R(h, X) can be bounded in an aVV/a) The optimal hyperparameter determined via a grid
interval of size = log,
search in Lotfi et al. [32]
Compressing LLMs with SubLoRA. To achieve the extreme compression level necessary obtain non-vacuous document-level bounds, Lotfi et al. (32) propose SubLoRA, a non- lon-linear subspace parametrization of an LLM's weights 0. Using SubLoRA, these weights can be written 8o + LoRA(Pw).. Here On E R² are the model weights at random initialization and LoRA(Pw) combines low-rank adaptation (LoRA) 19] with subspace training [31] via the projector P E Dxd The LoRA decomposition parameterizes dense matrix W E Raxb as the product of two low-rank matrices A E R B E Rrxb with a small rank r. As for the linear subspace parametrization Pw, the projection matrix P defined a Kronecker product P Q1 Q2 produced by orthogonalizing
Q1, Q2 ~ N00, / via a QR decomposition.
In practice, selected subset of the dense matrices in an LLM are parameterized using LoRA's low rank matrices, then the concatenation LoRA's matrices projected into the subspace parameters w using P. The model is therefore effectively trained via the weights E IRd As a result, the model can be coded via random seed that reproduces the fre-fixed initialization Og and projection matrix P. and coding of w which is performed using arithmetic coding (25). The dimension d of w can
3

---

be varied to achieve the best trade-off between empirical risk and complexity, and these degrees of freedom are accounted for in the coding of the hypothesis h.
3 Related Work
Generalization bounds for neural networks. Deep neural networks are challenging to understand using generalization theory due to their many parameters [5T]. However, over the past years, there has been success in constructing meaningful bounds covering for image classification models [13], vision- laioonlanguage models []. and tabular data [17], often through the methodology of compression generalization bounds to the LLM setting, and obtain non-vacuous bounds at the document level. Li et al. (27 explore generalization in few-shot learning, establishing bounds based on in-context examples while maintaining a fixed pretrained model. In contrast, we investigate pretraining generalization bounds to understand why models do overfit training time, despite the increased dataset complexity.
[3 BJ Lotfi et al. [32 extend compression-
Non-IID Generalization bounds. Ralaivola et al. [4 analyze the dependence graph of the random variables, deriving a bound based on the graph coloring number, fitting into broader line of work making use of properties of the dependence graph [52]. Unfortunately for text data, the dependencies unknown assumed to follow the triangular autoregressive dependency structure for all pairs in the sequence. A related line of work has been to explicitly estimate coefficients which quantify the extent that random variables relate to each other, [e.g.. 33 24]. However, it is unclear how best to apply these methods to neural networks. Martingale tail bounds are sometimes used online learning and reinforcement learning, e.g., for establishing regret bounds 4O). Chugg al. (7] present large collection of generalization bounds both in the IID and martingale settings, including generalization bounds which could be used the token level such the one derive. Their results extend and generalize many existing bounds. We view our contribution as orthogonal to these efforts since we focus on constructing the components necessary generate practical bounds for LLMss, rather than abstractly innovating on concentration inequalities.
Large language models and compression. Parameter-efficient finetuning methods, such as LoRA 19). parametrize weight matrices as products of two trainable low-rank matrices on top of frozen pretrained weights. QLoRA uses 4-bit NormalFloat (NF4) and double quantization, enabling single- GPU finetuning for a 65B parameter LLM without performance degradation [10] [ Post-training quantization approaches, such as GPTQ [16), rely second-order information and quantize each row of weight matrices independently. QulP uses adaptive rounding and incoherence processing of second-order Hessian matrices, enabling 2-bit quantization of L.LMs (6. Other compression techniques for I.LMs include replacing most of the 16-bit operations with 8-bit matrix multiply (10) using data-free distillations (28), designing custom kernels and sub-4-bit integer quantization [22 36).
and compressing embeddings as low-rank matrix-product state [50].
4 Token-Level Generalization Bounds
In order to unlock a deeper understanding of L.LM generalization, it is not sufficient to consider the training data at the level of entire documents. In fact, token-level performance is arguably what we care about most when evaluating& a model's generalization on its next token prediction pretraining task. Moreover, simplifying the bounds to meet the IID assumption over sampled documents restricts our ability to capture the dependencies between individual tokens. In this section, we derive novel bounds at the token level through a simple yet powerful application of Azuma's 's inequality that allows to use the properties of martingales to go beyond the IID setting. Then, we discuss the interpretation of our bounds and demonstrate their ability to predict downstream generalization. Finally, we introduce a new optimization strategy for tuning the prediction smoothing hyperparameter.
4.1 A Novel Non-IID Token-Level Generalization Bound
In deriving token-level bounds, one might consider applying Equation (I) to the finite dataset D (( J composed of input and output pairs. this scenario, model training can be performed on a random subset S C D of m pairs, which differs from how training is usually performed via contiguous sequences. Then, we could use the performance on S to bound the average performance on D since S is constructed an IID sample from D. While these bounds are valid,

---

they require fundamentally altering the training procedure, and they only pertain to the held out pairs which must be collected advance and separated from their naturally occurring context.
To avoid these limitations, we construct a novel bound that naturally accommodates the non-llI) structure of the tokens as they oceur in documents as follows:
Theorem 4.1. With probability at least - over the randomness in a sampled sequence
(x1, F2...., Jmm, if the negative log likelihood of model h & H can be bounded log2 ph (-(or-2))
(a, a + Ail, then the negative log likelihood of the data for model satisfies
1
log2 Ph (m)g)) + V log L/P(h) log 1/0
E
log, Ph (X/|==)))<e))
(2)
m
m
2m
where Å process, and P(h) is any normalized prior over discrete hypothesis space H. that does not depend on {x; m 1im1-
m E A7 the expectation is taken over X; ~ p(X; from the data generating
We provide proof sketch as well as the full proof in Appendix A.1
On the right-hand side of the bound is the conventional empirical risk: - loga Ph (1 E, logz (r,)((r<<)) the measured sequence and complexity term log P()). We describe in detail how we sample sequence Izm and compute the empirical risk in Section [4.2 The quantity which we are bounding on the left-hand side the expected next token negative log-likelihood under resampling from the data generating process, averaged over the different contexts that have been encountered in the training set. The bound ensures generalization on contexts seen at training when the next tokens are resampled, but not on data with contexts that are different. However, given how diffuse the distribution over next tokens is, e.g., at the beginning of new sentence, our bounds remain predictive of generalization and achieving non-vacuous bound requires generalization. We provide further interpretation of the bounds, including protein application, in Section 6
4.2 Sampling and Empirical Risk Evaluation
In this section, we more precisely define the sequence Fsm for which we compute the empirical risk in Equation (2). We construct sample zgmm from the stochastic process Pdatu by first sampling independent and identically distributed documents, e.g., the documents that form the Open Web dataset. Then, we concatenate these documents deterministically using end of text (EOT) tokens. Consequently, the ground truth stochastic process has the following property:
= Paau(2; [2k I;-1):
where zg is the previous EOT token. This equality holds exactly due to how the stochastic process implemented.
On the other hand, it would not be guaranteed that a generative model ps (4)) satisfies the property in Equation (3) apriori if the model were allowed to attend to tokens T<ck even when the data generating process has this property. However, we explicitly prohibit our generative model from attending to tokens I<c through the attention mask, as we have the flexibility to do so in defining our hypothesis class and model family. Therefore, our model pt. that we bound also satisfies this property Pa (2; 2x) = Ps "e..,,....... (r./=),...,,,;;... exactly, and not approximately.
In conclusion, the empirical risk for our generative model h and sequence Igmm sampled from the stochastic process defined above can be written as follows:
log2 ph (# 771
1
logz pa (x:(<r)))
--1
m Σ logz ph (ril x;-1),
171
where Zg is the nearest EOT token occurring before x,. Given the large size of the WebTet and Amber datasets, containing 9 billions and 1.2 trillion tokens respectively, we use subsampling for the evaluation of the empirical risk. More details can be found in Appendix A.2
4.3 Token-level Bounds Are Predictive of Generalization
Token-level vs. document-level bounds. contrast to document-level bounds, our token-level bounds increase the number of samples, driving down the size of the complexity term, and do
5

---

30000
5.0
120
Bound Objective (BPI)
BPD
4.8
Entropy 69
Frequency
80
-4.6
4.4
10000
PPL
40
4.2
20
0
512
768
1023
2
10"
10"
Entropy
Token Index
Trainable Parameters
Figure 2: Our bounds analyze quantity that is meaningful and predictive of generalization. Left: Using LLaMA2-7B, we compute the entropy of p(zy(r<<) where the context Ieşi is fixed and sampled from the Amber training dataset. The distribution over next tokens given fixed context from the training data is indeed diffuse and characterized by high entropy values. Middle: Entropy of p(æ; as a function of the token index shown the x-axis for context length L 1024. The average entropy has decreasing trend but remains high overall; note that the average entropy for 768 as high the average entropy for 128. Right: On the left y-axis, we plot the average zero-shot accuracy (ACC) and perplexity (PPL) achieved by GPT2 models ranging in scale from 117M to 1.5B averaged over downstream datasets, as reported in Radford et al. [39 On the right y-axis, we plot an approximation of the conditional BPD expectation that we bound in Equation (2) where we resample I; from a LLaMA2-7B given fixed training contexts I<i from the Amber dataset. The approximation of the BPD objective that we bound achieves 97.9% and 99.1 1% correlation with the accuracy and perplexity, respectively.
not require the IID assumption. Whereas the number of samples previously would be the number of documents, it is now simply the number of tokens in the dataset, far higher number. As a consequence of decreasing the complexity term, the empirical risk will be a more significant contributor our bounds compared to document-level bounds. Therefore, we achieve non-vacuous bounds for much larger and more performant models that generate high-quality text. This development brings our theoretical bounds much closer aligning with empirical generalization.
Interpretation of token-level bounds. It is important to note the difference between the quantity that m. - E[ log2 Ph (X, (. which is conditioned contexts seen training, and
bound 1 the expected risk E| - log, Ph [x))] under resampling from the data generating process where new contexts can be sampled from this process. However, the resampled next tokens xy 03| not necessarily from the training set, and to the extent that the distribution over next tokens is entropic, we are measuring a different quantity than the empirical training performance of the hypothesis h. Moreover, we know that the distribution over next tokens is often indeed diffuse; for instance, many words have common synonyms. The distribution over next tokens is especially diffuse when we start a new sentence, for example. We demonstrate how diffuse the distribution p(æ; [r=;) is for fixed contexts x'zi from the publicly available Amber training dataset (29) (see Appendix [.77) by sampling F; |r=s using LLaMA2-7B to approximate the generative process. Figure Left) shows that, indeed, the distribution p(a; ( is characterized by high entropy for a large number of tokens. In Figure 2] Middle), we plot the entropy of p( (ee)) for each index in a context of length 1024. This figure confirms our intuition that the next token distribution is particularly diffuse the beginning of sentence, while it decreases for later tokens but remains relatively high. Given how diffuse the distribution is and the large number of possible sentences, is broadly infeasible to make predictions on new resampled tokens from the empirical distribution alone.
Our bounds are predictive of downstream performance. We compute an approximation of the quantity that we bound in Equation (2) by sampling next tokens 2; using LLaMA2-7B given fixed contexts Jei from the Amber dataset. We plot this quantity on the right y-axis of Figure Right,, and show on the left y-axis the performance of GPT2 models of varying sizes on downstream datasets as reported in Radford et al. [39] see Appendix [apeedix|B.4]1 for more details. Not only does the approximation of the BPD objective show the same trend as the downstream performance for different GPT2 variants, but it also achieves 97.9% and 99. 1 % correlation 4 with downstream task accuracy and perplexity metrics, respectively. Moreover, we show in Appendix C.33 that our token-level BPD bounds are also predictive of downstream generalization and achieve 98.9% and 99.4% correlation with downstream perplexity and error, respectively.

---

In short, our bounds go significantly beyond the observation that the empirical distribution converges to the true distribution, and are predictive of generalization on downstream tasks. Achieving non-vacuous token-level bound requires generalization.
4.4 Token-Level Prediction Smoothing
Rather than using a single label smoothing a for all data points, we propose to use the network itself to determine which tokens warrant more confidence and which ones require more smoothing to limit their worst-case behavior. We perform token-level prediction smoothing by adding linear head to the LLM that outputs the probability a for each token, such that ph (T<)) = (1
(x (p (2. ( + arp(t<<//V. The training objective corresponds to the upper bound in Equation (2) rather than the empirical risk alone, where the parameter factors into the bound via the interval size A; = log, (1 + (1- ax( (/less))//oo /////22 (z<<)). Therefore, the values of ogg (Z<+) are adjusted to achieve the best trade-off between the empirical risk and the compressed model size. We perform this optimization post-training using a subset of the training dataset.
V/aa
We demonstrate in Figure 4 Left) that using this token-dependent significantly improves the value of the bounds. In Figure 4 (Middle), we compare to the setting where the optimal a is obtained through grid search, and in F Right) we examine the distribution of a produced by the model.
5 Compressing LLMs to Minimize Complexity
In shifting from document-level to token-level bounds, the number of data points increases considerably, and thus we can afford to pay significantly more bits in the complexity of the compressed model. In this new regime, the SubLoRA compression technique becomes very restrictive.
5.1 Efficient Nonlinear Parametrizations
In addition to LoRA, we explore two expressive nonlinear parametrizations s(0) that make efficient use of the parameter space: Kronecker structures (I5) and Monarch matrices [9]. We can use these nonlinear parametrizations directly, or in conjunction with subspace compression, parametrizing the full parameters as = 0o + (Pw) for a projection matrix P R Dxd, After training, the parameters quantized as in and coded using arithmetic coding. We describe these structures below.
LoRÁ. With LoRA 19). the weight matrices of linear layers are parametrized via low rank updates. Each weight matrix W E Raxb is parametrized W = W, + AB for A E Raxr, B E Rgrxb with small rank r, where Wo is given by the initialization and A, B form the trainable parameters each layer. Rather than considering only self-attention layer weights [19 32
we extend SubLoRA to all linear layers in the model and compress the biases and layernorm weights in the subspace projection.
We can represent W as Kronecker product W = A @ B, where & is the Kronecker product, A E Rai xb, B gbg and 0j42 a, b162 which reduces the parameters over the dense layer. This approach has been used in recent work for parameter-efficiee finetuning 15 and as an alternative structure for pretraining.
Kronecker Product.
Monarch Matrices. We also consider Monarch matrices 99, which employ two block diagonal matrices A, and B typically with A and B formed by Va blocks of size va x vT and reshape or permutation operation R: W ARB. The matrix multiplication is implemented by reshaping the input axis a into (Va, /a), applying matrix A as a batched matrix multiply on one axis, and then applying B the other axis by permuting the axes. Monarch matrices have shown considerable promise as an expressive and hardware-efficient replacement for linear layers.
5.2 QulP 2-Bit Quantization of LLM
In addition to pretraining LLMs in efficient nonlinear subspaces, we explore recent post-training quantization methods reduce the model complexity. Quantization with Incoherence Process (QulP) compresses LLM weights to a smaller number of bits while preserving model performance [6].
Adaptive Rounding. For weight matrix W E Baxb QulP minimizes the proxy quadratic objective ((W) [[][(W 3) ur((W- W) ( W) where W. gaxb are the quantized
7

---

Compression Approach
BPD Bound
Top-1 Error
Top-10 Error
Top-100 Error
SubLoRA 32
10.49
90.44
71.33
49.77
Enhanced SubLoRA (Ours)
10.44
89.38
69.54
49.84
Enhanced LoRA (Ours)
7.85
78.15
52.48
31.64
Monarch Only (Ours)
7.65
75.87
47.47
28.34
Kronecker Only (Ours)
8.03
80.80
52.77
30.14
Kronecker + Subspace (Ours)
10.02
88.75
67.91
47.14
Random Guess
15.62
99.99
99.98
99.80
Table I: Non-vacuous generalization bounds using different compression techniques for GPT2 pretraining. We find that with the larger complexity budget afforded by the token-level bounds, subspace compression is no longer necessary or even beneficial for the bounds. Of the structures we consider, the Monarch parametrization performs best.
weights, x R is a vector drawn randomly from a calibration set, and H the second moment matrix of these vectors used proxy Hessian [6]
Incoherence Processing. Based on the observation that incoherences between the weights W and the proxy Hessian H benefit quantization, QulP further applies incoherence post-processing using Kronecker products of random orthogonal matrices U E Raxa V E Raxb such that H t- VHV W + UWV Here = U1 @ @ Us and V = Vi Ø ... @ Vz.
Subsequent work like QulP# improves upon QulP by using randomized Hadamard transform and vector quantizations [48]. To compute the compressed size (hh
qulf-quantized models, we use gzip [12] to compress the quantized model checkpoint and obtain the term C(h) the bits required for the storage afterwards.
Vacuous Bounds for LLMs with Billions of Parameters
We compute generalization bounds for: (i) models that are trained through non-linear subspace compression in the form of LoRA, Kronecker product or Monarch matrices on the OpenWebTexx WebText dataset, then quantized using the same setup Lotfi et al. (2), or (ii) models that are pretrained on a dataset other than the OpenWebTee dataset or on datasets that might have the WebTWttText as a subset- and made publicly available. For the pretrained models, we either apply aggressive quantization, which is the case for GPT2, or use QulP 2-bit, 3-bit and 4-bit publicly-availate quantized models, which is the case for LLaMA. In the pretrained LLMs setting, we evaluate our bounds for both the OpenWebTert (9B tokens) and Amber (1.2T tokens) datasets. In both settings, obtain highly compressed models that lead to non-vacuous generalization bounds. We also compute token-level generalization bounds for antibody design, task where conditioning on contexts from the training dataset arises naturally. Finally, we investigate the effect aggressive compression on memorization vs. reasoning in LLMs. We provide all the experimental details in Appendix B
6.1 Token-level Bounds via Nonlinear Parametrizations
we experiment with LoRA in addition the Kronecker and Monarch subspace parametrizations order to train compressed versions of GPT2 small (124M parameters). Compared to previous work, we enhance both LoRA and SubLoRA by not only applying the low-rank decomposition to the attention layers and the linear head, but to all the fully-connected layers in the LLM. Additionally, we train all the bias and layer normalization parameters instead of keeping them fixed at their values initialization. We also rotary position embeddings [46] to directly encode the positional information into the LLM. Combined with our proposed loken-level optimization of the label smoothing probability a, significantly improve upon the LoRA subspace compression, as shown in Table I It worth noting the LoRA alone led to vacuous BPD document-level bounds in Lotfi et al. 32 while our version is non-vacuous.
As discussed in Section 5.1
Among subspace compression strategies that we explore in Table I Monarch without subspace leads to the tightest teven-level bound. In fact, the substantial scale of our dataset, comprising billion tokens, significantly changes the trade-off between the empirical risk and the compressed model size compared to previous work, since the compressed size factor in the bound is divided by the

---

Top-1
Top-100
Top-1
Top-100
Model
BPD
Model
BPD
Error (%)
Error (%)
Error (%
Error (%)
GPT2 (124M)
7.61
74.82
26.98
LLaMA2-7B
4.28
47.50
12.56
GPT2 (355M)
8.50
79.19
32.72
LLaMA2-131
4.51
47.85
14.44
GPT2 (774M)
10.47
89.50
44.23
LLaMA2-70B
6.39
58.26
25.04
Random Guess
15.62
99.99
99.80
Random Guess
14.97
99.99
99.68
Table 2: Pretrained GPT2 models achieve non- vacuous bounds for next token prediction WebText through post-traing test-training quantiza- tion only and without altering the pretraining.
Table 3: Pretrained LLaMA2 models achieve
non-vacuous token-level bounds for next token prediction on the Amber dataset via 2-bit post- training QulP quantization only.
size of the dataset. Consequently, we have greater flexibility in selecting larger models that achieve an improved empirical risk. this setting, the Monarch parametrization achieves the best trade-off between the empirical risk and the compressed size of the model as shown in Table [] followed by LoRA and Kronecker. Monarch and Kronecker also perform best in terms the validation loss, as shown in Figure [ightt. The new trade-off between the empirical risk and the compressed size of the model also explains why subspace compression is no longer beneficial obtaining tighter bounds compared previous work, further reducing the number of trainable parameters through linear subspace projection leads to a worse trade-off between the empirical performance of the compressed model and its compressed size.
6.2 non-vacuous Bounds for Pretrained LLMs: GPT2, LLaMA1 and LLaMA2
Intensive quantization is another way we can achieve model compression, and therefore tighter generalization bounds. We explore the setting where only apply post-training quantization to pretrained LLMs and compute the corresponding token-level generalization bounds.
Pretrained GPT2 models. We apply the post-training quantization 31 to the publicly available GPT2 models (39] of sizes 124M (GPT2 small), 354M (GPT2 medium), and 773M (GPT2 large) parameters that were pretrained on the WebText dataset and report the numbers in Table 2 We find that GPT2 small not only yields non-vacuous bounds, but these bounds are quite comparable to those obtained using aggressive compression techniques in Table [ GPT2 medium and large also achieve non-vacuous bounds despite having almost a billion parameters.
Pretrained LLaMA models. In this set of experiments, we use pretrained and pre-quantized models publicly available LLaMA1, LLaMA2 and LLaMA2-Char modells and plug their empirical risk and compressed size directly into our token-level bounds. We report the bounds obtained for 2-bit ILaMA2 in Table The full set of results reported in Table The bounds are computed for the next token prediction task on the Amber dataset, which contains T.2T tokens. We obtain non-vacuous bounds for these models despite their large scale, ranging from billion to billions parameters. Our experiments show that the LLaMA2-Chat models achieve worse generalization bounds reported Table g and Figure Left) demonstrating that fine-tuning Chat models for dialogue use cases hurts their generalization performance next token prediction. Although we do not know what data was used to pretrain the LLaMA models, our bounds remain valid since they do not require for the models to be trained on the same data that the empirical risk is evaluated on.
High-quality text generation. significant limitation of document-leve bounds is that the SubLoRA model achieving the best document-level bound generates un-grammatical, low-quality text as demonstrated by Lotfi et (32 and shown Table g In contrast, our top-performing model in terms of token-level BPD bounds on the OpenWebText WebText dataset, which is the quantized GPT2 small model, generates high-quality text, ensuring a unique combination practical usefulness and tight guarantees the population risk.
6.3 Token-Level Generalization Bounds on Antibody Sequences
In addition to natural languages, our token-level generalization bounds are particularly descriptive of antibody design in biology. An antibody sequence is usually composed of 20 different amino acid tokens to bind to target of interest. In therapeutic antibody design, biologists propose mutations to existing antibody sequences by changing the amino acid tokens specific positions in the sequence.

---

Recent works have shown that LLMs pretrained on large antibody datasets can be used to propose mutations conditioned on starting antibody sequences [4 2]. Our token-level generalization bounds match the settings by bounding the expected next amino acid token negative log likelihood averaged over training contexts that serve as starting sequences for iterative mutations. Table 7 that language models based on the Mistral 7B architecture pretrained on processed subset of the Observed Antibody Sequences (OAS) from scratch achieves non-vacuous token-leved generalization
we show
bounds [20 35 2]
Details of these experiments can be found in Appendix B.9
6.4
Contextualizing GPT2 Bounds Against Markov Chains
The best token-level bound that we achieve for BPD on the OpenWeb- Text dataset is 7.6. But what does this value exactly mean? One might con- sider the possibility that our bounds describing only the simplest com- ponents of fitting the data that exist in the model, such as the predictions of a Oth or 1st order Markov chain (34]
Training Context Length
0
2
4
1024
GPT2-S-Quantized Markov Chain
13.9
11.1
9.0
7.9
7.6
11.3
10.5
15.3
22.4
Table 4: Our LLM bounds provide much stronger statement than what would be explained by low order Markov models.
In Table 4 we show that this is not the case, by explicitly training sparse k-th order Markov chain on OpenWebTexx WebText and computing our token-level bounds for the result. Sweeping over different numbers of n-grams to for the Markov chains, our bounds for these models cap out at 10.5 BPD and rapidly degrade with higher order as more statistics need to be stored. We also train and compress versions of GPT2 that are restricted to only seeing k tokens as context, mirroring the restrictions of the Markov chains. We find that for the simple O and 1st order Markov chains, our compression via the transformer is slightly worse. However, the LLM performs much better for higher orders.
6.5 Memorization vs. Reasoning
LLMs are capable of memorizing facts from their pretraining data, but they also can learn highly structured patterns. As we compress model more and more, it must lose its ability to recall memorized facts, but it may still remember patterns, since they are compressible. In this section, examine the difference between memorization and reasoning by measuring the ability of LLMs to compress structured and unstructured sequence data. To generate structured sequences, we first short binary expression trees generate numerical sequences of integers [17]. These sequences are highly compressible as they are generated using short and deterministic programs. To generate unstructured sequences, we collect the set of all unique integers from the structured sequences and form random sequences composed of IID samples from the set of unique integers (see Appendix [B.6] for details). We train standard GPT2 models from scratch on structured and random sequences separately. In Figure 3, we show the integer prediction training accuracy with varying degrees of post-training quantization. We observe that as models are quantized more aggressively, i.e. the number of quantization levels decreases, they forget unstructured sequences far faster than structured sequences. These results parallel the findings of Jin al. (2I] who show that smaller models can retain in-context learning capabilities but lose their ability to recall facts.
7 Conclusion
In this work, we introduced novel token-level generalization bounds for LLMSs which are able to accommodate the non-IID nature of the tokens within the training corpus. Combined with different compression techniques, we achieve non-vacuous generalization bounds for LLMs with up to 70 billion parameters. The compressed models for which we construct our bounds are capable of producing high quality text, unlike those in prior work. While there is still have gap to close between the typical validation BPD and the constraint of our bounds, our bounds are predictive of generalization and provide insights into model behaviour.
In future work, one could envision constructing new bounds that make use of the independence structure between documents and then the non-independent structure within documents to achieve the best of both. It would also be exciting to further explore the development of these bounds for new downstream predictive tasks, in the vein of the antibody design task we briefly consider here.
10

---

Acknowledgements
We thank Alan Amin for helpful discussions and anonymous reviewers for helpful feedback. This work at NYU is supported by NSF CAREER IIS-2145492, NSF CDS&E-MSS 2134216, NSF HDR-2118310, BigHat Biosciences, Capital One, and an Amazon Research Award.
References
[1] V. Akinwande, Y. Jiang, D. Sam, and J. Z. Kolter. Understanding prompt engineering may require rethinking generalization. arXiv preprint arXiv:2310.03957, 2023.
[2] Anonymous. Bayesian optimization of antibodies informed by generative model of evolving sequences. Manuseript, 2024.
[3] K. Azuma. Weighted sums of certain dependent random variables. Tohoku Mathematical Journal, Second Series, 19(3):557-367, 1967.
[4] J. Benesty, J. Chen, Y. Huang. and I. Cohen. Pearson correlation coefficient. In Noise reduction in speech processing, pages 37-40. Springer, 2009.
[5] O. Catoni. Pac-bayesian supervised classification: the thermodynamics of statistical learning. arXiv preprint arXiv:0712.0248, 2007.
[6] Chee, Y. Cai, Kuleshov, and C. D. Sa. Quip: 2-bit quantization of large language models with guarantees, 2024.
[7] B. Chugg, H. Wang, and A. Ramdas. A unified recipe for deriving (time-uniform) pac-bayes bounds. Journal of Machine Learning Research, 24(372):1-61, 2023.
[8] T. Computer. Redpajama: an open dataset for training large language models, 2023. URL
https://gittutt: wwt.///o////// httpa//..woooggggeeeeeeerpeeeeee
[9] Dao, B. Chen, N. Sohoni, A. Desai, M. Poli, J. Grogan, A. Liu, A. Rao, A. Rudra, and C. Ré. Monarch: Expressive structured matrices for efficient and accurate training, In International Conference on Machine Learning, pages 4690-4721 PMLR, 2022.
[10] T. Dettmers, M. Lewis, S. Shleifer, and L. Zettlemoyer. 8-bit optimizers via block-wise quantization, 2022.
[11] T. Dettmers, S. Shmitchell, A. Roberts, K. Lee, T. B. Brown, D. Song, and C. Raffel. Qlora: Efficient finetuning quantized Ilms. arXiv preprint arXiv:2305. 14314, 2023.
[12] P. Deutsch. Rfc1952: Gzip file format specification version 4.3, 1996.
[13] G. K. Dziugaite and D. M. Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. arXiv preprint arXiv:1703.1 1008, 2017.
[14] G. K. Dziugaite, K. Hsu, W. Gharbieh, G. Arpino, and D. Roy. On the role of data in pac-bayes bounds. In International Conference on Artificial Intelligence and Statistics, pages 604-612. PMLR, 2021.
[15] A. Edalati, M. Tahaei, I. Kobyzev, V. P. Nia, J. J. Clark, and M. Rezagholizadeh. Krona: Parameter efficient tuning with kronecker adapter. arXiv preprint arXiv:2212.10651 2022.
[16] Z. Frantal, A. Gruslys, and D. Kiela. Gptq: Accurate post-training quantization for generative pre-trained transformers. arXiv preprint arXiv:2210.17323 2022.
[17] M. Goldblum, M. Finzi, K. Rowan, and A. G. Wilson. The no free lunch theorem, kol- mogorov complexity, and the role of inductive biases in machine learning. arXiv preprint 2rX2:22304.05366, 2023.
[18] Hayou, B. He, and G. K. Dziugaite. Probabilistic fine-tuning of pruning masks and pac-bayes self-bounded learning. arXiv preprint arXiv:2 10. 18804, 2021.

---

[19] E. J. Hu. Y. Shen, P. Wallis, Z. Allen-Zhie Zhu, Y. Li, S. Wang, L. Wang. and W. Chen. Lora: Low-rank adaptation of large language models. arXiv preprint arXiv:2106.09685, 2021.
[20] A. Q. Jiang, A. Sablayrolles, A. Mensch, C. Bamford, D. S. Chaplot, D. d. I. Casas, F. Bressand,
G. Lengyel, G. Lample, L. Saulnier, et al. Mistral 7b. arXiv preprint arXiv:2310.0668 2023.
[21] T. Jin, N. Clement, X. Dong, V. Nagarajan, M. Carbin, Ragan-Kelley, and G. K. Dziugaite. The cost of down-scaling language models: Fact recall deteriorates before in-context learning. arXiv preprint arXiv:2310.0468// 2023.
[22] J. Kim, J. H. Lee, S. Kim, J. Park, K. M. Yoo, S. J. Kwon, and D. Lee. Memory-efficient fine-tuning of compressed large language models via sub-4-bit integer quantization. arXiv preprint arXiv:2305. 14152, 2023.
[23] A. N. Kolmogorov. On tables of random numbers. Sankhyā: The Indian Journal of Statistics, Series A, pages 369-376, 1963.
[24] V. Kuznetsov and M. Mohri. Generalization bounds for non-stationary mixing processes. Machine Learning, 106(1):93-117, 2017.
[25] G. G. Langdon. An introduction to arithmetic coding. IBM Journal of Research and Development, 28(2):135-149, 1984.
[26] R. Li, L. B. Allal, Y. Zi. N. Muennighoff, D. Kocetkov, C. Mou, M. Marone, C. Akiki, J. Li,
J. Chim, Q. Liu. E. Zheltomozhskii, T. Y. Zhuo, T. Wang. O. Dehaene, M. Davaadorj. J. Lamy-
Poirier, J. Monteiro, O. Shliazhko, N. Gontier, N. Meade, A. Zebaze, M.-H. Yee, L. K. Umapathi,
J. Zhu, B. Lipkin, M. Oblokulov, Z. Wang, R. Murthy, J. Stillerman, S. S. Patel, D. Abulkhanov,
M. Zocca, M. Dey, Z. Zhang, N. Fahmy, U. Bhattacharyya, W. Yu, S. Singh, S. Luccioni,
P. Villegas, M. Kunakov, F. Zhdanov, M. Romero, T. Lee, N. Timor, J. Ding, C. Schlesinger, H. Schoelkopf. J. Ebert, T. Dao, M. Mishra, A. Gu, Robinson, C. J. Anderson, B. Dolan-Gavitt, D. Contractor, S. Reddy, D. Fried, D. Bahdanau, Y. Jernite, C. M. Ferrandis, S. Hughes, T. Wolf, A. Guha, L. VON Werra, and H. de Vries. Starcoder: may the source be with you!, 2023.
[27] Li, M. E. Ildiz, D. Papailiopoulos, and S. Oymak. Transformers algorithms: Generalization and stability in in-context learning. In International Conference on Machine Learning, pages 19565-19599 PMLR, 2023.
[28] Y. Liu, Q. Xu, W. Xu, and Zhu. Llm-qat: Data-free quantization aware training for large language models. arXiv preprint arXiv:2305, 17888, 2023.
[29] Z. Liu, A. Qiao, W. Neiswanger, H. Wang. B. Tan, T. Tao, J. Li, Y. Wang, S. Sun, O. Pangarkar, R. Fan, Y. Gu, V. Miller, Y. Zhuang, G. He, H. Li, F. Koto, L. Tang, N. Ranjan, Z. Shen, X. Ren, R. Iriondo, C. Mu, Z. Hu, M. Schulze, P. Nakov, T. Baldwin, and E. P. Xing. Llm360: Towards fully transparent open-source Ilms, 2023.
[30] I. Loshchilov and F. Hutter. Decoupled weight decay regularization. arXiv preprint arXiv:1711.05101, 2017.
[31] Lotfi, M. Finzi, S. Kapoor, A. Potapczynski, M. Goldblum, and A. G. Wilson. Pac-bayes com- pression bounds tight that they can explain generalization. Advances in Neural Information Processing Systems, 35:31459-31473, 2022.
[32] S. Lotfi, M. Finzi, Y. Kuang, T. G. Rudner, M. Goldblum, and A. G. Wilson. Non-vacuous generalization bounds for large language models. arXiv preprint 12X1:233,..17733, 2023.
[33] M. Mohri and A. Rostamizadeh. Stability bounds for non-iid processes. Advances in Neural Information Processing Systems, 20, 2007.
[34] J. R. Norris. Markov chains. Number 2. Cambridge university press, 1998.
[35] T. H. Olsen, F. Boyles, and C. M. Deane. Observed antibody space: A diverse database of cleaned, annotated, and translated unpaired and paired antibody sequences. Protein Sci., 31(1): 141-146, Jan. 2022.
12

---

[36] G. Park, J. Kim, J. Kim, E. Choi, S. Kim, S. Kim, M. Lee, H. Shin, and J. Lee. Lut- Lut-gemm: Quantized matrix multiplication based on luts for efficient inference in large-scale generative language model. arXiv preprint ar arXiv:2206.095577 2022.
[37] G. Penedo, Q Malartic, D. Hesslow, R. Cojocaru, A. Cappelli, H. Alobeidli, B. Pannier, E. Almazrouei, and Launay. The refinedweb dataset for falcon Ilm: Outperforming curated corpora with web data, and web data only, 2023.
[38] M. Pérez-Ortiz, O. Rivasplata, J. Shawe-Taylos and C. Szepesvári. Tighter risk certificates for neural networks. Journal of Machine Learning Research, 22(227):1-40, 2021.
[39] A. Radford, J. Wu, R. Child, D. Luan, D. Amodei, I. Sutskever, et al. Language models are unsupervised multitask learners. OpenAl blog, 1(8):9, 2019.
[40] A. Rakhlin and K. Sridharan. On equivalence of martingale tail bounds and deterministic regret inequalities. In Conference on Learning Theory, pages 1 1704-1722, PMLR, 2017.
[41] L. Ralaivola, M. Szafranski, and G. Stempfel. Chromatic bac-bayes bounds for non-iid data: Applications to ranking and stationary 8-mixing processes. The Journal of Machine Learning Research, 1 11:1927-1956. 2010.
[42] C. RelaxML. Quip#: Quip with lattice codebooks. Rernell-RRllxMMMuuuui-----
httpa://githun com/
2024.
[43] S. Shalev-Shwartz and S. Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
[44] R. W. Shuai, A. Ruffolo, and J. Gray. Generative language modeling for antibody design. bioRxiv, pages 2021-12, 2021.
[45] R. J. Solomonoff. A formal theory of inductive inference, part i. Information and control, 7(1): 1-22, 1964.
[46] J. Su, M. Ahmed, Y. Lu, S. Pan, W. Bo, and Y. Liu. Roformer: Enhanced transformer with rotary position embedding. Neurocomputing, 568: 167:127063, 2024.
[47] H. Touvron, L. Martin, K. Stone, Albert, A. Almahairi. Y. Babaei, N. Bashlykov, Batra, P. Bhargava, S. Bhosale, D. Bikel, L. Blecher, C. C. Ferrer, M. Chen, G. Cucurull, D. Esiobu, J. Fernandes, Fu, W. Fu, B. Fuller, C. Gao, V. Goswami, N. Goyal, A. Hartshom, S. Hosseini, R. Hou, H. Inan, M. Kardas, V. Kerkez, M. Khabsa, I. Kloumann, A. Korenev, P. S. Koura, M.-A. Lachaux, T. Lavril, J. Lee, D. Liskovich, Y. Lu, Mao, X. Martinet, Mihaylov. Mishra, I. Molybog, Y. Nie, A. Poulton, J. Reizenstein, R. Rungta, K. Saladi, A. Schelten, R. Silva, E. M. Smith, R. Subramanian,
F. Tan, Tang, R. Taylor, A. Williams, X. Kuan, P. Xu, Z. Yan, I. Zarov, Y. Zhang, A. Fan, M. Kambadur, S. Narang, A. Rodriguez, R. Stojnic, S. Edunov, and Scialom. Llama 2: Open foundation and fine-tuned chat models, 2023.
[48] A. Tseng, J. Chee, Q Sun, V. Kuleshov, and C. De Sa. Quip#: Even better Ilm quantization with hadamard incoherence and lattice codebooks. arXiv preprint arXivx2402.04396, 2024.
[49] K. Wang, X. Hu, and Zhang. Fast clonal family inference from large-scale cell repertoire sequencing data. Cell Rep Methods, 30000, Oct. 2023.
[50] Q. Xu, W. Xu, and J. Zhu. Tensorgpt: Efficient compression of the embedding layer in llms based on the consor-trinn decomposition. arXiv preprint arXiv:2307.0088 2023.
[51] C. Zhang, S. Bengio, M. Hardt, Recht, and O. Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107-115, 2021.
[52] R.-R. Zhang and M.-R. Amini. Generalization bounds for learning under graph-dependence: A 2022.
survey. arXiv preprint
[53] W. Zhou, V. Veitch, M. Austern, R. P. Adams, and P. Orbanz. Non-vacuous generaliza- tion bounds at the imagenet scale: pac-bayesian compression approach. In International Conference on Learning Representations, 2019.
13

---

A Token-Level Martingale Bound
A.1 Proof of the Main Theorem
Theorem A.I. With probability at least 1 over the randomness in a sampled sequence
11, 22, ................................ Fmn the negative log likelihood of a model h E H can be bounded - -ogg ph (-)(r-z)) [a, aa+t + for some D (possibly a function of h), then the negative log likelihood of the data of given hypothesis h satisfies
m
log 1/P(h) + log 1/0
logz PM (X (X1(
log2 (= + Av
m71
m
2m
where å process, and P(h) is any normalized prior over discrete hypothesis space H. that does not depend on {x; n 1im1-
m Ex= 27 the expectation is taken over X; ~ p(X:(aes)) from the data generating
Proof sketch. The proof of Theorem 4.1 is application of Azuma's inequality 3 and can be broken down into the following steps:
Construct martingale difference sequence from the difference between the NLL on token F;, and its expectation given the tokens Tęs. From the boundedness of NLL one can show that the differences are bounded.
Apply Azuma's 's inequality for each hypothesis, choosing failure probability proportional to the chosen prior P(h).
Perform union bound of the failure probabilities over all hypotheses. If all of the hypotheses satisfy the bound simultancously, then so does the data dependent hypothesis h².
Proof. Given the autoregressive predictions R(h, Tiy F2))) == logg Ph (2a( where Nei {21, .g....,,I.. 11 Let {2,} denote the actual values of the sequence that were found empirically, and (X.) be the random variables for these quantities.
The collection of random variables (indexed by i) Z = TE| R(h, X,, R(h, X,, 2<s) form a Martingale difference sequence with respect to Tei-- Note here that the expectation is over the distribution X; ~ xxx)) From the construction, E [ZZ,[(=<
and the sequence is bounded: < Z: < A; E[R(h, X,, x a [ a = B,, with B; A; A,
A; = E[ X,, x [
A; may depend r>i but only through it's dependence on the hypothesis h({=))/= For fixed we may conclude that Σ Z: is bounded difference Martingale sequence (with respect to (x<)) ) ) and we can apply Azuma's inequality derive that for any >
P
Z: > mt) S exp ( 2m²
Σ A?)
1=1
1=1
m
P(
Z, > t) < exp 2mt2 (oae/A?) /
m
Judiciously choosing
log 1/P(h) log 1/8
t(h) AV
2m
we have that ( Em Z, 1(1) P(h)6.
Applying a union over the events UnEr [ Em Z((h) t(h)]. we have
P 1 Σ Z 2 1(h)) s Σ
P(h)ō = 6,
1=1
h
14

---

therefore P( Ei=1 Zi S t(h))
i=
> 1- - 5. Unpacking the definition of Zi, we have that with
probability least 1
m Σ m
1
1 & m
Σ R(,, 24, x,, VV
log 1/P(h) + log 1/6
2m
Expressed in terms of the log likelihood, we can write this as:
172
log, Ph (X,] E
1 m
loga Ph (Zigm) + AV
log 1/P(h) log 1/6
m
2m
A.2 Empirical Risk Subsampling
We evaluate bounds for the Open WebText and Amber datasets which contain 9 billion and 1.2 trillion tokens, respectively. Computing the exact empirical risk for these datasets would be prohibitively expensive. Therefore, use subsampling for the evaluation of the empirical risk to accelerate bound computation. In Equation (2), we use the following inequality which holds with probability least 1 d2:
loga Pn (T S
Σ loga Pa (To + A
log 1/62 2n
(5)
m
for a subsample of size n where a is a random permutation. We choose ō1 in Equation 2 with respect overall failure probability to be 61 ón/(n ( m) and choose 82 dm m)) so that the overall failure probability is still 6. The proof is simple and similar to that provided in Lotfi al. (32)
B Experimental Details
B.1 Pretraining with Nonlinear Parametrizations
To achieve the necessary model compression level for computing non-vacuone vacuous bounds, we pretrain GPT2 Small with 124 million parameters on the Open WebText dataset based on the nanoGPT implementation 39 We parametrize the linear layers of CausalSelfAttent on, MLP, and the LinearHead of the GPT2 models with our nonlinear compression techniques (LoRA, Kronecker, Monarch), where we use a bias vector except for the LinearHead layer. For LoRA and Kronecker, we use weight tying between the token embedding and the final LinearHead layer parameterized by nonlinear compression techniques. We also train the layer norm parameters in addition to of the nonlinear projection parameters applied to the linear layers. For Monarch, we only train the linear layers parameterized by Monarch matrices. We also combine the three nonlinear parametrizations with linear subspace projection, where all the trainable parameters are projected into a subspace of parameters w using a projection matrix P, such that do + Pw. We vary the dimension of w as a hyperparameter in the bound evaluation.
For all the pretraining experiments, we use batch size of 8, a sequence length 1024, and standard AdamW W optimizer [30] with learning rate of 0.0002. We perform a learning rate warm-up for 500 iterations, and we apply rotary embedding to all three nonlinear parametrizations.
B.1.1 Hyperparameter Sweeps for LoRA
LoRA. We sweep over LoRA rank values r E {1,4, 16, 32, 64, 128, 256}. We choose a learning rate of 0.0002 with a LoRA dropout value of 0.1 and LoRA alpha value of 32.
SubLoRA. We report the rank r and the corresponding subspace dimension values that we sweep over for SubLoRA in Table
15

---

Rank
Subspace Dimension d
25000
4
50000
8
50000
16
50000
32
10000, 750000
64
25000,, 2000000
128
7000000, 15000000
Table 5: Hyperparameter sweep for SubLoRA. For all the SubLoRA pretraining experiments, a learning rate of 0.0002, LoRA dropout value of 0.1, and a LoRA alpha value of 32.
B.1.2 Hyperparameter Sweeps for Kronecker
For the Kronecker factorization W A Ø B, we choose the matrices and B such that Raixb, B E [Re2xb2 where 0142 and by b1 = b. We sweep over all possible combinations of [2) and (bi,b) by performing prime factorizations with multiplicity on the numbers o, b and enumerating all possible combinations. All of our Kronecker pretraining experiments use learning rate 0.0002.
B.1.3 Hyperparameter Sweeps for Monarch
For the Monarch parametrization, we relax the restriction for the number of blocks to be strictly va and instead by number divisible by a to sweep over different numbers of blocks. We also perform experiments for Monarch where using absolute position encodings and experiments where are only applying the Monarch factorization the attention layers and the linear classification heads.
B.2 Quantization
Quantization. Following Lotfi et al. 31 we apply post-training quantization of the trainable weights that correspond the subspace parameters and/or the LoRA, Kronecker, Monarch parameters along with layer norm weights depending pretrained weights into significantly smaller number of quantization clusters. The quantized vector A = [w,,.. [ (ia) can be constructed from the original weights vector w [w]..... Wa] by assigning these weights to different clusters c = [ct,...ci, Cr.,, where w; = Gq such that g = argming ww; cxl- The quantization clusters are learned alongside w, such that we optimize the empirical risk and the compressed size of the model as well.
the compression setup. In this case, map the
Experiments on QulP-quantized Models. We compute token-level bounds pretrained LLaMAI and LLaMA2 models [47] quantized with QuIP with publicly-availabl checkpoints [42]. Although we do not know what data was used to pretrain these models, we can evaluate the generalization bound on the Amber dataset and consider other tokens used in training as data-dependent prior.
B.3 Bounds Evaluation
In the sequence of text, we use end of text tokens (EOT) which separate the documents. In this way, consider concatenating many documents together to form one long sequence. As result of the EOT tokens and the structure of the text, the distribution p( (eee)) can be simplified into p(x,//x T..+1. ..... 24-1) where & is the index of the most recent EOT token because the documents are sampled independently. In the evaluation of the LLM we likewise have no dependence on tokens outside the given document in question.
To compute token-level bounds, we evaluate all of our generalization bounds with failure probability 5 0.05 and subsample size of 10, 0000 tokens from the Wex training dataset of size m = 9 billion tokens or the Amber dataset size m 1.2 trillion tokens.
Evaluation metrics. In addition to reporting generalization bounds for the diiieeerdiimnnsoon (BPD) loss, we also report the bounds that we obtain for the Top-1, Top- and Top-100 error. The Top-k error refers to the 0-1 error in predicting the next token among the top- predictions of the
16

---

model. For instance, the Top-1 error for token 2; is defined as 1 [argmaax, p(æ Iess =x = z.}. where argmax operates over tokens z; across the vocabulary. We extend this definition to the Top-k error and define it as 1 [2; E argmaxx,, ( <<<i)], where the argmax operator here selects the top-k tokens predicted by the model according to next token probability distribution p(Zylate = F...) Our bound in Equation (2) applies not only to the log likelihood but to any bounded risk, and therefore can be computed for the Top-k error since it is bounded between and 1. We call Top-k error bound vacuous when the bound is larger than the random guess top-k error equal to k/V, where is the vocabulary size.
B.4 Correlation with Downstream Performance
We retrieve the downstream task performance difference GPT2 variants ranging in scale from 117M to 1.5B averaged over the downstream datasets as shown in Table To obtain approximation of the conditional BPD expectation that we bound Equation 2 we resample v, from a LLaMA2-7B given fixed training contexts I<i from the Amber dataset. We use sample size equal to 10, 000 samples.
Model Size
LAMBADA (PPL)
LAMBADA (ACC)
CBT-CN (ACC)
CBT-NE (ACC)
WikiTex12 (PPL)
PTB
WikiText103 (PPL)
1BW
(PPL)
(PPL)
117M
35.13
45.99
87.65
83.4
29.41
65.85
37.50
75.20
345M
15.60
55.48
92.35
87.1
22.76
47.33
26.37
55.72
762M
10.87
60.12
93.45
88.0
19.93
40.31
22.05
44.575
1542M
8.63
63.24
93.30
89.05
18.34
35.76
17.48
42.16
Table 6: Zero-shot downstream task performance for GPT2 models with different model sizes as reported in Radford et al. [39].
B,5 Markoy Chain Comparison
For training the Markov chains, we reuse the Byte Pair Encoding (BPE) tokenization to separate out the effect the tokenizer. We apply prediction smoothing at level = 0.1 the Markov models to give them nonzero probability to ngrams that have not been seen in the training data and limit the worst case NI.I. of a single token.
For constructing generalization bounds with the Markov chain, we upper bound the complexity term log (() similarly the large language models by performing quantization and compression. We store and update the Markov chains sparsely, which becomes necessary when considering the high order variants. In storing the model, we a dictionary mapping each prefix concatenated with the following token to a count. The counts can then be converted into probabilities by normalizing by the count containing just the prefix. We quantize the counts and store them in 16 bits, and we store the keys using a basic encoding. For training, we train on a subsample of 10 tokens from the training corpus, sufficient for the performance of the Markov chains to converge.
B.6 Memorization Experiment
Following Goldblum et al. [17), we select a complexity value of which reflects the difficulty the task, and sequence length of 30 and generate 984 sequences as the training dataset for structured sequences. To build our baseline random sequences, we collect all unique integers in the generated sequences into set. We then sample integers IID from uniform distribution over the set of unique integers from the structured sequences build the baseline dataset. Our vocabulary size 12 as we only have integers, the beginning of text token, and an additional delimiter token. The delimiter tokens are placed between distinct numbers during our tokenization process. use a GPT-2 Small model with 124M parameters and train it on the structured and random sequences separately with a learning rate of 0.0001 for 1000 epochs. Our quantization procedure the same as described in Appendix B.2
We show the results for this experiment in Figure 3
17

---

Accuracy (%)
0.6
0.2
Structured Sequences
Random Sequences
25
75 Quantization Levels
50
100
Figure 3: As language models are compressed, they retain their understanding of patterns, but they forget highly random and unstructured data rapidly. Experiments performed on GPT-2 models with datasets created detailed in Section 6.5 Compression performed via post-training quantization where lower quantization levels reflect more aggressive compression..
B.7 Amber Dataset
We use a subset of the pretraining dataset for Amber 7B LLM 29 for our bound evaluations. This dataset contains RedPajama VI [8] (arxiv, C4, GitHub, StackExchange, Wikipedia), StarCoder [26] (The Stack), RefinedWeb (37] (CommonCrawl) with around 1.2 trillion tokens. We tokenize the entire dataset using LLaMA tokenizer and then sample tokens from uniform distribution over the tokenized dataset.
B.8
Compute Budget
For all our pretraining experiments with the three proposed compression techniques, run each experiment for 5 days on GPUs parallel that are of type A A100sor RTX8000. For the bound computation experiments, we use single GPU of any type and subsample size of 10, 000 samples. The rumming time varies between to hours depending on the model and the dataset. All other experiments performed single GPU of any type.
B.9 Bounds on Antibody Sequences
B.9.1 Datasets
An antibody consists of both the light chain and the heavy chain amino acid sequences. Among these sequences, there are collections of sequences called the clonal family that our immune systems developed to bind targets. For our experiments, we select all human heavy chain amino acid sequences from the Observed Antibody Space (OAS) and keep all the clonal families with at least 25 sequences using the FastBCR filtering technique following 335 49 The processed dataset contains around 908 thousand heavy chain clonal families. A single example in our dataset is thus clonal family looking like [sequence 1, sequence 2, ..., sequence N] where 2 25.
There are in total 29 different tokens with 20 of them corresponding to 20 different amino acids. Let [CUSep] be separator token between sequences in clonal family. We process our input example by forming the string "sequence 1 [C1Sep) sequence [CtSep) ... (CLSep) sequence N" following 2 This input example is tokenized and given language model using the next token prediction training objective.
B.9.2 Language Models
We use language model architectures that are based on the Mistral 7B architecture 20 We scale down the Mistral architecture using 24 layers with a varying hidden state size of (1024, 768, 512). resulting in our Mistral 377M, Mistral 212M, and Mistral 94M models, respectively following (2]. With vocabulary size of 29 and a maximum context length of 2048, we train each of our models using NVIDIA 1100s for 48 hours and perform post-training quantization following Lotfi al. 31
18

---

Compression Approach
Bits Per Dimension
Top-1 Error
Top-10 Error
Validation Loss
Mistral 377M
2.41
31.60
26.46
0.28
Mistral 212M
2.06
26.25
21.07
0.30
Mistral 94M
1.62
19.40
14.59
0.30
Random Guess
4.86
96.56
65.51
1.46
Table 7: Models pretrained antibody sequences achieve non-vacuous token-level general-
ization bounds. Language models pretrained on antibody sequences achieve non-vacuous bounds for next token prediction on a processed subset of Observed Antibody Sequences (OAS) through post-training quantization only. The vocabulary size of an antibody LLM is 29.
C Additional Results
C.1 Token-Levvl Prediction Smoothing Optimization
we show the bounds we obtain with and without optimizing the prediction smoothing probability for different numbers trainable parameters. We observe that post-training optimization of a at the token-level yields significantly better bounds.
In Figure 4
10.5
Grid Search
Token-Dependent
Emplfical I Distribution
2000
Bound Loss
1500
1000
BPD
Before Optimization Optimization
500
8.5
10"
10"
10
10
10"
10"
Trainable Parameters
Prediction smoothing (a)
Prediction smoothing (at
Figure Token-level prediction smoothing improves our bounds. Left: optimize a conservative upper bound on the generalization bound that we would get from Equation ( with respect the a head parameters. Doing so yields a noticeable reduction in the value of
After training, we
bound. Middle: BPD generalization bound as function of single global parameter chosen from
discrete number of values vs. the generalization bound for the token-dependent after optimization. Right: Histogram of the values taken by ax over different inputs.
C.2 LLaMA Bounds on Amber
In Table 8 we have the complete bounds computation results for LLaMAI, LLaMA2, LLaMA2 Chat with 2-bit, 3-bit, and bit-quantization on the Amber dataset. The best bound is achieved by LLaMA2 model with 2-bit quantization.
C.3 Token-Level Bounds Are Predictive of Downstream Performance
We compute the direct correlation between our bounds and the downstream performance on the tasks reported in Table In Figure (Left y-axis), we plot the average zero-shot eгror (Error), defined as the accuracy, and the perplexity (PPL) achieved by GPT2 small, medium and large on the downstream tasks in Table On the right y-axis, we plot the token-level bounds achieved by the GPT2 models with different sizes on the WebText dataset that they were partially trained on. Our token-level BPD bounds achieve 98.9% and 99.4% correlation with the downstream perplexity and error, respectively, and are indeed predictive of generalization on downstream tasks.
C.4 Generated Text
In Table we show the generated text by the model achieving the best bounds: the quantized GPT2 model that achieves the best token-level bounds on the Open WebText dataset in our work, and the GPT2 model trained with SubLoRA that achieves the best document-level bounds in Lotfi et al. [32
19

---

Bits per Dimension
Top-1
Top-10 Error (%)
Top-100
Model
Error (%)
Error (%)
bits
LLaMA1-7B
4,29
48.08
22.82
12.83
LLaMA 1-13B
4.60
48.87
24.23
14.59
LLaMA1-3000
5.37
52.91
28.06
19.14
LLaMA 1-55B
6.10
56.63
32.29
24.14
LLaMA2-7B
4.28
47.55
22.48
12.56
LLaMA2-Chat-7B
4.54
49.10
24.18
13,50
LLaMA2-13B
4.52
47.85
23.54
14.44
LLaMA2-Chat-l C3B
4.77
49.82
24.95
15.10
LLaMA2-70B
6.14
56.24
32.61
24.32
LLMMA2-Chat-708
6.40
58.26
34.16
25.04
bits
LLaMA1-7B
4.37
47.42
22.87
13.63
ILaMA
4.80
48.97
25.23
16.14
LLaMA1- 1-30B
5.70
53.54
29.91
21.63
LLaMAl-6SB
6.73
59.56
36.14
28.08
LLaMA2-7B
4.35
47.15
22.75
13.62
LLaMA2-Chat-77
4.65
48.84
24.23
14.24
LLaMA2-132
4.76
48.45
24.67
15,95
LLaMA2- 1-AAA2C-ht-113B
5.06
50.90
26.26
16.66
LLaMA2-70B
6.77
59.35
36.27
28.56
LLaMA2-Chat-70n
7.08
61.66
38.00
29.30
bits
LLaMA1-7B
4.50
47.52
23.53
14.52
LLaMA1-13B
5.02
49.96
26.46
17.47
LLaMA 1-30B
6.05
55.55
32.09
23.93
LLaMA
7.27
62.56
39.38
31,54
ILaMA2-7B
4.49
47.64
23.64
14.53
LLaMA2-Chat-P
4.83
49.49
25.15
15.12
LLaMA2-13B
4.96
49.46
25.67
17.21
LLaMA2-Chat-125
5.27
51.61
27.23
18.12
LLaMA2-700
7.33
62.53
39.89
32.11
SLaMAA-Chat-P77
7.68
65.32
41.59
32.87
Random Guess
14.97
99.99
99.96
99.68
Table 8: Non-vacuous token-level generalization bounds for open-source pretrained LLM checkpoints the Amber dataset. All of these models quantized post-training using QulP# to different numbers of bits as shown above. All the bounds are non-vacuone compared to random guess performance.
The text generated by the model achieving the best generalization bounds in our work is visibly more coherent and grammatically correct. By switching from document-level token-level bounds, obtaining non-vacuous bounds requires less restrictive compression techniques and therefore can be achieved for highly performant models that generate high-quality text and can deployed in practice.
20

---

PPL
Error
100
Token-leve BPD Bound
BPD
11.2
PPL / Error (%)
75
50
11.0
25
0
10.8
10
10
Trainable Parameters
Figure 5: Our bounds are predictive of generalization on downstream tasks. On the left y-axis, we plot the average zero-shot error (Error) and the perplexity (PPL) achieved by GPT2 small, medium and large models pretrained with SubLoRA on downstream tasks reported in Table 6 of the original manuscript. On the right y-axis, we plot the the bounds achieved by GPT2 models on Open WebText. Our bounds achieve 98. 98.9% and 99. 4% correlation with the perplexity and error, respectively.
Generated Text
GPT2 (124M) Quantized (BPD Bound: 7.61)
The study, published in Proceedings of the National Academy of Sci- ences, examined the relationships between brain activity, gene expression and inflammation diseases including Alzheimer's 's disease, dementia, Parkinson's 's disease, glioblastoma and Alzheimer's disease. "Our study demonstrates that omega-3 fatty acids play a role in the link between inflammation and brain function," said lead author Dr Richard Collins. PhD, of Duke University's Duke Center for Bioethomics and Bioengi- neering. After controlling for.
GPT2 (124M) SubLoRA 32
th he the startedt at its., the more be power and- by. S and, of of -'s on. The UK The, are the on the the under, but the then the day.. The. The. It for the! a.. M an they first the the speak have times. cover that illegal In the day where I The who when and In We "[[" As she I WeP spirituality. The all And one which more says thought the other (ed 15: And P It as/ T But We The The theah It who the full of that to was 'The they (It As We A and each The It- We The M I
Table 9: The best non-vacuous token-level bounds correspond models that generate high quality text. Examples of generated text from the GPT2 small quantized model that achieves the best token-level bounds compared to the SubLoRA-pretraine GPT2 small model Lotfi et al. [32]. In contrast to the text generated by the best performing model in terms of BPD bounds by Lotfi al. [32], our quantized GPT2 small generates significantly higher-quality text while simultaneously achieving the best BPD and fop-1/10/ 100 error bounds.
21

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and precede the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No] or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the
relevant information is Not Available.
Please provide short (1-2 sentence) justificatin right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation.
While "[Yes] " is generally preferable to "[No]" ", is perfectly acceptable to answer "[No] "provided proper justification is given (e.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). ). general, answering "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS paper checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only the provided macros for your answers.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: For each one of the contributions stated in the introduction, which mainly reflect the contributions stated in the abstract, we include reference for where it can be found the main text and justify fully in the corresponding section.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
22

---

Justification: We discussed the limitations of our bounds both when we introduced them in Section 3 and again in the conclusion. We provided empirical evidence for how these limitations do not render our bounds meaningless.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiscless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: We described all the assumptions that we make on the hypothesis space h, the risk, and prior ..ete, in both the main text in the appendix. We provide the full proof of the main theorem in the appendix.
Guidelines:
The answer NA means that the paper does include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
23

---

Justification: We describe the experimental setup both in the main text and in the appendix. We clearly indicate cases where we use the same experimental setup as other papers.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
The Open WebText dataset as well as the Amber dataset are publicly available and can be accessed easily. For the memorization experiment, we describe our sampling procedure for the random sequence and refer to another work's code reproduce the data for the structured sequences.
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/
public/gume Soaieeeee/CoSSuumiisicee
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https //nips http:///wwpp.//eeeeee/////eeeaaa
for more details.
24

---

The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments should state which ones are omitted from the script and why.
reproducible, they
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We described all the experimental details to the best of our ability in the main text and in the appendix. Additional details can also be found in the code that attach as supplementary material.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: (iight.)
We provide error bars over the accuracy and perplexity values in Figure
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
25

---

Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification: We added subsection in the appendix where we detail wall time, numbers of GPUs and types of GPUs that were required to run our experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
The research conducted the paper does indeed conform in every respect with the NeurIPS Code of Ethics.
Justification:
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is no societal impact of the work performed.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
26

---

If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks. mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Does not apply.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual- dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
We cite all assets that we in this work.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswi thcode. com datasete has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
No new assets created.
Guidelines:
The answer NA means that the paper does not release new assets.
27

---

Researchers should communicate the details of the dataset/codeemmodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
28


Reviews:
[{"review_id": "yTQwNyes4p", "reviewer": "Reviewer_iy2E", "summary": "This paper presents a novel approach that computes non-vacuous compression-based generalization bounds for LLMs at the billion-parameter scale. Prior works could only achieve vacuous bounds for these large-scale models and rely on the assumption of IID documents. By leveraging the vast number of tokens in LLM training sets and properties of martingales, the authors derive non-vacuous bounds for LLMs that generate high-quality texts. Further, they showcase the tightness of the bounds by examining compression schemes including Monarch matrices and Kronecker factorizations, and post-training quantization techniques.", "questions": "Stated in the prior part.", "limitations": "The authors note the limitations of the current work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper tackles an important problem that aims to give guarantees on the generalization abilities of LLMs, which are getting more powerful but the good performance is extremely hard to interpret and assess. \n2. Prior works compute non-vacuous bounds on LLMs but rely on assumptions of IID documents and therefore can only be applied to those that generate poor text quality. This work presents a novel approach based on properties of martingales and gives much tighter bounds on LLMs of much more practical capabilities. Further, it does not require altering the pretraining pipeline of the LLMs being analyzed.\n3. It investigates the generalizations by examining compression schemes including Monarch matrices and Kronecker factorizations, and post-training quantization techniques. The results also give interesting insights for practitioners.", "weaknesses": "1. Since the utilization of martingales is one main theoretical contribution of the work, I feel some background and proof sketch on how they are being used would be better included in the main text. \n2. The main models being examined are of the LLaMA and GPT-2 family of models. In particular, the experiment on the chat version of LLaMA is interesting as the generalization gets worse from the supervised finetuning. It would be interesting to see if this is generally true and why this is the case. More experiments on other finetuned LLMs would provide more evidence.\n3. From table 2 and 3, it seems that given larger model sizes, the derived bounds get closer to random guess performance. Why is this the case and does it mean the bound would potentially be no-longer meaningful if the model gets large enough? Maybe I misunderstood something and would appreciate some clarification on this point.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your thoughtful and supportive feedback! We respond to your questions below.\n\n**Effect of finetuning on downstream task performance:** \n\nAs per your suggestion, we run additional experiments where we finetune the GPT2 large model (774M parameters) – pretrained on the WebText dataset – on multiple downstream tasks: grade school math, stack exchange and planning. These datasets are publicly available on HuggingFace. We report the results in the table below. While finetuning visibly improves the model’s performance on the downstream task, it negatively affects the performance on the pretraining dataset and hence leads to a worse upstream bits-per-dimension (BPD) bound since the compressed size of the model remains approximately constant. \n\n| Model | Compressed Size (MB) | Downstream Empirical Risk | Upstream Empirical Risk | Upstream BPD Bound  |  \n|  ---    |               ---              |             ---             |                 ---              |               ---                   | \n| Pretrained GPT2 Large  | 424.07 | 3.44 (on planner); 4.56 (on stackexchange) ; 0.45 (on grad school math) | **4.65** | **10.47** | \n| GPT2 large finetuned on grade school math    | 420.65 | **0.016**  (on grad school math) | 6.92  | 12.72  |  \n| GPT2 large finetuned on Stack Exchange      | 424.06 | **0.14**  (on stackexchange)   | 4.80 | 10.62 |  \n| GPT2 large finetuned on Planning       | 424.07  | **0.001** (on planner) | 4.78  | 10.56  | \n\n**Trade-off between the empirical risk and the compressed size of the model:** \n\nOur generalization bounds, as described by Equation 2, can be conceptually written as:\n\n$$\\text{Expected Risk} \\leq \\text{Empirical Risk} + \\sqrt{\\text{Compressed Model Size} / \\text{Train Data Size}}.$$\n\nTherefore, the trade-off between the empirical risk and the compressed model size heavily depends on the compression approach and the size of the dataset. Having a dataset that contains a higher number of tokens puts a bigger emphasis on the empirical risk compared to the compressed model size, and vice versa. Likewise, if the compression approach is very aggressive, it will significantly reduce the compressed model size while potentially causing a deterioration of the empirical performance. The rate at which each element of the bound changes dictates whether the bound will increase or decrease for larger models. We demonstrate this effect in Figure 2 in the attached Rebuttal PDF, where we see that an aggressive compression scheme for the GPT2 models consisting of pretraining them in restricted SubLoRA spaces with 25k parameters only then quantizing them leads to an improvement in the token-level bounds as we increase the size of the original model. In contrast, quantizing the LLaMA2 models using QuIP# maintains a good empirical performance but does not reduce the compressed size significantly compared to an approach like SubLoRA, therefore the bounds deteriorate as the models become larger. If the Amber dataset contained more tokens, one would expect that the bounds would improve for larger models given the improvement in the empirical risk. \n\n\n**An intuitive application of our bounds:** \n\nIn addition to the above experiments, we ran additional experiments for the antibody design downstream task to provide more intuition on the quantity that we bound .In fact, biologists propose mutations to existing antibody sequences by _changing the amino acid tokens at specific positions in the sequence_. Recent works have shown that LLMs pretrained on large antibody datasets can be used to propose mutations _conditioned on starting antibody sequences_. **Our token-level generalization bounds match the antibody design setting by bounding the expected next amino acid token negative log likelihood averaged over training contexts that serve as starting sequences for iterative mutations.** We provide results in the general response showing that these bounds are non-vacuous. \n\n**Background and proof sketch of the main theorem:** \n\nWe provide a sketch of the proof in Appendix B.1, and it consists of three components: set up the empirical loss as the average of a martingale difference sequence, apply Azumas inequality for each hypothesis assigning failure probability proportional to the prior p(h), and then apply a union bound to relate the concentration around the many for individual hypotheses to any given hypothesis that can depend on the training data. We take your point that it would be beneficial to have this summary and some additional background in the main text, to provide additional context for the bounds we use. We will update the paper accordingly.\n\nWe provide additional experiments in the general response showing that not only is the quantity we bound predictive of downstream performance, but the bounds themselves positively correlate with downstream performance. \n\nThank you again for your supportive feedback. We made a significant effort to address your comments and run several new experiments inspired by your feedback, which we believe have improved our paper. We would appreciate it if you would consider raising your score in light of our response. We would be happy to engage in additional discussion if there are further questions.", "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": "vThg7Mmor7", "reviewer": "Reviewer_mAFv", "summary": "This paper develops nonvacuous generalization bounds for modern language models. Specifically, this paper proves a token-level generalization bound, and applies different techniques (LoRA, 2 Kronecker Product, Monarch Matrices, and post-training quantization) to control the capacity of model class.", "questions": "Figure 2 (right) claims that the left-hand side of eq. (2) is correlated with downstream performance. Specifically, the left y-axis plots accuracies of GPT-2 models, while the y-axis uses samples from the LLAMA model; if I understand correctly, the LLAMA model is treated as an oracle model here, since we do not know the true data-generation process. However, I feel this is a little indirect; can you instead compare downstream performance with your generalization bound (i.e., right-hand side of eq. (2)) for the same model? If this also works, then we can claim that not only the quantity we try to bound is meaningful, but the bound itself is also meaningful.", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "This paper is well-written: Theorem 3.1 is clean, and many compression techniques (parameter-efficient tuning, post-training quantization,etc.) and modern language models (GPT, LLAMA, etc.) are analyzed. I believe these are nice contributions.", "weaknesses": "The main weakness in my opinion is the left-hand side of eq. (2), since it uses contexts from the training data. I agree it is still a meaningful result, but it is also a little hard to interpret. Line 190 claims that \"This figure confirms our intuition that the next token distribution is particularly diffuse at the beginning of a sentence, while it decreases for later tokens but remains relatively high. Given how diffuse the distribution is and the large number of possible sentences, it is broadly infeasible to make predictions on new resampled tokens from the empirical distribution alone.\" I am not fully convinced by this, since we can add some fixed prompt and only measure generalization error for the generated part.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We really value your thoughtful and supportive feedback! We provide several additional results inspired by your comments. \n\n**An intuitive application of our bounds to downstream tasks:**\n\nInspired by your comments, we provide another intuitive application of our bounds. In this case, to a downstream scientific task. Our token-level generalization bounds are particularly descriptive of antibody design in biology. An antibody sequence is usually composed of 20 different amino acid tokens to bind to a target of interest. In therapeutic antibody design, biologists propose mutations to existing antibody sequences by changing the amino acid tokens at specific positions in the sequence. Recent works have shown that LLMs pretrained on large antibody datasets can be used to propose mutations conditioned on starting antibody sequences. **Our token-level generalization bounds match the antibody design setting by bounding the expected next amino acid token negative log likelihood averaged over training contexts that serve as starting sequences for iterative mutations.** In the table below, we show that language models based on the Mistral 7B architecture pretrained on a processed subset of the Observed Antibody Sequences (OAS) from scratch achieves non-vacuous token-level generalization bounds: \n\n|    Compression Approach    |    BPD Bound   |   Top-1 Error Bound   |   Validation Loss  |\n|               ---                           |          ---            |           ---                     |             ---             | \n|         Mistral 377M                |       2.41            |           31.60               |             0.28          | \n|         Mistral 212M                |        2.06           |           26.25               |             0.30          | \n|         Mistral 94M                  |        **1.62**     |           **19.40**          |             0.30         | \n|         Random Guess            |        4.86          |            96.56               |             1.46        | \n\n\n**Correlation between our bounds and the performance on downstream tasks:** \n\nFollowing your suggestion, we compute the direct correlation between our bounds and downstream performance on the tasks reported in Table 6 of the paper. In Figure 1(left y-axis) reported in the attached Rebuttal PDF, we plot the average zero-shot error (Error), defined as 1 - the accuracy, and the perplexity (PPL) achieved by GPT2 small, medium and large on downstream tasks, as reported in Radford et al. [1]. On the right y-axis, we plot the token-level bounds achieved by the GPT2 models with different sizes on the OpenWebText dataset that they were partially trained on. Our token-level BPD bounds achieve **98.9%** and **99.4%** correlation with the downstream perplexity and error, respectively, and are indeed predictive of generalization on downstream tasks. Given the significance of these results, we included them in our revised manuscript. \n\n**The distribution over next tokens being diffuse:** \n\nAs you mentioned and as shown in Figure 2 (middle), the average entropy of the next token distribution conditioned on fixed contexts decreases for later token positions compared to the beginning of text token. Therefore, if we have a fixed prompt, this distribution might be less diffuse for the first token that we predict given the prompt. However, the main takeaway from this experiment actually pertains: even for later token positions, the distribution does not collapse entirely and the entropy is non-zero. For instance, if the prompt is composed of 127 tokens, then the average entropy for the next token is equal to 3 bits after transformation to the logarithm base 2, which corresponds to 8 choices for the next tokens. The number of choices is far greater than a single predetermined token, which implies that it is infeasible to make predictions on new resampled tokens from the empirical distribution alone. Therefore, non-vacuous token-level bounds are indicative of generalization beyond the training data. \n\nThank you again for your detailed review. We put a significant effort into our response and would appreciate it if you could consider raising your score. \n\n______\nReferences:\n\n[1] A. Radford, J. Wu, R. Child, D. Luan, D. Amodei, I. Sutskever, et al. Language models are 454 unsupervised multitask learners. OpenAI blog, 1(8):9, 2019.", "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": "juizcQNYZZ", "reviewer": "Reviewer_4zMP", "summary": "The paper proposes token-level generalization bounds for large language models (LLMs), such as LLaMA2-70B, using less restrictive compression techniques like Monarch matrices, Kronecker factorizations, and post-training quantization. The authors argue that traditional document-level bounds are vacuous at this scale and introduce a method leveraging martingales for deriving tighter bounds, which not only hold theoretically but are also demonstrated through empirical validation.", "questions": "Can the generalization bounds proposed be integrated into the training regimen to enhance model generalization directly?", "limitations": "The paper lacks intuitive explanations for the proposed bounds, which might hinder understanding for readers not familiar with advanced statistical concepts in machine learning.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. **Originality**: The paper introduces a novel approach to computing generalization bounds at the token level, which is a significant departure from the document-level bounds prevalent in prior works.\n2. **Technical Soundness**: The use of martingales and non-restrictive compression methods to derive generalization bounds is both innovative and robust, providing a solid theoretical framework backed by empirical results.\n3. **Significance**: The ability to provide non-vacuous generalization bounds for LLMs as large as 70 billion parameters is highly significant, as it pushes the boundary of what is understood about LLM generalization in practical settings.\n4. **Clarity**: The paper is well-written, with clear explanations of the methods and their implications, making it accessible to readers who may not be experts in the specific sub-field of machine learning.", "weaknesses": "No major weaknesses", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks for your encouraging and thoughtful feedback! We respond to your questions below.\n\n**An intuitive application of our bounds to downstream tasks:** \n\nInspired by your comments, we provide another intuitive application of our bounds. In this case, to a downstream scientific task. Our token-level generalization bounds are particularly descriptive of antibody design in biology. An antibody sequence is usually composed of 20 different amino acid tokens to bind to a target of interest. In therapeutic antibody design, biologists propose mutations to existing antibody sequences by changing the amino acid tokens at specific positions in the sequence. Recent works have shown that LLMs pretrained on large antibody datasets can be used to propose mutations conditioned on starting antibody sequences. **Our token-level generalization bounds match the antibody design setting by bounding the expected next amino acid token negative log likelihood averaged over training contexts that serve as starting sequences for iterative mutations.** In the table below, we show that language models based on the Mistral 7B architecture pretrained on a processed subset of the Observed Antibody Sequences (OAS) from scratch achieves non-vacuous token-level generalization bounds:\n\n|    Compression Approach    |    BPD Bound   |   Top-1 Error Bound   |   Validation Loss  |\n|               ---                           |          ---            |           ---                     |             ---             | \n|         Mistral 377M                |       2.41            |           31.60               |             0.28          | \n|         Mistral 212M                |        2.06           |           26.25               |             0.30          | \n|         Mistral 94M                  |        **1.62**     |           **19.40**          |             0.30         | \n|         Random Guess            |        4.86          |            96.56               |             1.46        | \n\n**Using generalization bounds for model optimization:** \n\nIt is indeed possible to integrate the elements of our bounds directly into the training regimen to enhance model generalization directly. One example is quantization-aware training, which we in fact already use for post-training quantization of all pretrained models except the LLaMA models. In this scenario, we wish to map the pretrained weights of the neural networks into a significantly smaller number of quantization clusters. The quantized vector $\\hat{w} = [\\hat{w}_1,\\dots,\\hat{w}_d]$ can be constructed from the original weights vector $w = [w_1,\\dots,w_d]$ by assigning these weights to different clusters $c = [c_1,\\dots c_L]$, where $\\hat{w}_i =c_q$ such that ${q= \\operatorname{argmin}_k |w_i-c_k|}$. The quantization clusters $c$ are learned alongside $w$, such that we optimize the empirical risk and the compressed size of the model as well. We will add more details about our quantization-aware training procedure in the appendix. The focus of our work however is to compute non-vacuous generalization bounds that we can use to understand when and why LLMs generalize and provide a prescription for how to design better models in practice. \n\nWe provide additional experiments in the general response showing that not only is the quantity we bound predictive of downstream performance, but the bounds themselves positively correlate with downstream performance. We also demonstrate that the trade-off between the empirical risk and the compressed size of the model highly depends on the compression scheme and the size of the training data. The additional figures can be found in the Rebuttal PDF. \n\nInspired by your feedback, we also made sure to include additional intuitive explanations and details throughout the revised manuscript to make sure that the paper's content is accessible to readers.\n\nThank you again for your supportive and positive review. We made a significant effort to revise our paper and run additional experiments in light of your feedback. We would appreciate it if you would consider raising your score in light of our response. Please let us know if you have any additional questions or comments.", "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:
We thank all the reviewers for their very supportive and helpful feedback. Inspired by the reviewers’ comments, we now report additional results that highlight the following contributions: (i) we complement our other understanding-oriented experiments through an antibody design setting where the task itself naturally matches the definition of the expected risk in our bounds since one would use LLMs pretrained on large antibody datasets to propose mutations **conditioned on starting antibody sequences from the training dataset**; (ii) we run additional experiments to further investigate the effect of finetuning models on their upstream performance and upstream generalization guarantees; (iii) we show that our bounds are predictive of downstream performance, achieving 98.9% and 99.4% correlation with downstream perplexity and error, respectively; (iv) we empirically demonstrate that the trade-off between the empirical risk and the compressed size of the model depends on the size of the dataset and the compression approach. The new figures and table can be found in the attached Rebuttal PDF.

We have also incorporated reviewer feedback to provide additional background on Martingale bounds as well as a proof sketch in the main text in the revised manuscript.

We begin with a general response and then address reviewers individually as separate posts.

**Intuitive interpretation of our bounds for antibody design:**

We provided several experiments in our submission that help interpret the bounds. We thought it would also be especially exciting to consider a downstream task beyond next-word prediction. We believe this is the first time generalization bounds for language models have been used in such a way — to guarantee downstream performance on a scientific problem.

Our token-level generalization bounds are particularly descriptive of antibody design in biology. An antibody sequence is usually composed of 20 different amino acid tokens to bind to a target of interest. An example of an antibody sequence from the Observed Antibody Space (OAS) database is the following: “SETLSLTCTVSGGSMSSY…” [1]. In therapeutic antibody design, biologists propose mutations to existing antibody sequences by changing the amino acid tokens at specific positions in the sequence. In our example sequence, a mutation is introduced if we change one or many amino acid tokens. The next-token prediction task in language modeling thus has a natural interpretation of predicting mutations at position i conditioned on positions <i. Recent works have shown that LLMs pretrained on large antibody datasets can be used to propose mutations conditioned on starting antibody sequences. **Our token-level generalization bounds match the antibody design setting by bounding the expected next amino acid token negative log likelihood averaged over training contexts that serve as starting sequences for iterative mutations.** In the table below, we show that language models based on the Mistral 7B architecture pretrained on a processed subset of the Observed Antibody Sequences (OAS) from scratch achieves non-vacuous token-level generalization bounds:

| Compression Approach|BPD Bound|Top-1 Error Bound|Validation Loss|
| ---| ---| --- | --- |
|Mistral 377M |2.41|31.60|0.28|
|Mistral 212M|2.06|26.25|0.30|
|Mistral 94M|**1.62**|**19.40**|0.30|
|Random Guess| 4.86| 96.56|1.46|

**Further investigating the effect of finetuning LLMs on upstream performance:**

In our work, we show that chat versions of the LLaMA models obtain worse bounds on the Amber dataset. We extend these experiments to GPT2 models finetuned for different purposes, namely to answer grade school math questions, coding questions, and to do planning. These downstream datasets are publicly available on HuggingFace. We report the results for pretrained GPT2 Large (774M) in Table 1 of the attached Rebuttal PDF. While finetuning visibly improves the model’s performance on the downstream task, it negatively affects the performance on the pretraining dataset and hence leads to a worse upstream bits-per-dimension (BPD) bound since the compressed size of the model remains approximately constant.

**Correlation between our bounds and the performance on downstream tasks:**

Following the suggestion of reviewer mAFv, we compute the correlation between our bounds and downstream performance. In particular, we compute token-level bounds for GPT2 small, medium, and large pretrained with SubLoRA with an intrinsic dimensionality of 25,000 and a LoRA rank of 4 on the OpenWebText dataset. In Figure 1(left y-axis) reported in the attached Rebuttal PDF, we plot the average zero-shot error (Error) and the perplexity (PPL) achieved by GPT2 models on downstream tasks, as reported in Table 6 of the original submission. On the right y-axis, we plot token-level bounds achieved by GPT2 on OpenWebText. Our token-level BPD bounds achieve **98.9%** and **99.4%** correlation with the downstream perplexity and error, respectively, and are indeed predictive of generalization on downstream tasks.

**Trade-off between the empirical risk and the compressed size of the model:**

We demonstrate in Figure 2 in the attached Rebuttal PDF that the trade-off between the empirical risk and the compressed model size heavily depends on the compression approach.

**Summary:**

We are thankful for the supportive feedback from the reviewers and believe that their input has made a positive impact on our paper. We make a significant contribution in our work by computing non-vacuous bounds at the LLaMA-70B scale and use our bounds to derive insights about generalization in LLMs, highlighting the remarkable ability of transformer models in capturing longer range correlations, and distinguishing between memorization and reasoning.
___
Reference:

[1] Olsen TH, Boyles F, Deane CM. Observed Antibody Space: A diverse database of cleaned, annotated, and translated unpaired and paired antibody sequences. Protein Science. 2022; 31: 141–146.

Meta-review: The paper proposes a new approach for computing generalization bounds for large language models (LLMs). All the reviewers found the paper to be interesting, as it tackles an important problem. Meanwhile, the approach is novel as it "is a significant departure from the document-level bounds prevalent in prior works". There were some concerns on the clarity of the paper and also the lack of necessary background knowledge, while the authors did a good job on addressing that. So I would recommend accepting this paper.
Decision: Accept (spotlight)