27. The paper's own discussion: §8 and the Impact Statement¶

Where this fits

Prerequisites: Chapter 15 (documents as the i.i.d. unit, effective sample size, the population of a bound), Chapter 17 (the subsampling bound, Eq. 3), Chapter 20 (SubLoRA, nonlinear parameterization), Chapter 25 (Tables 1, 2, 4 and Figure 2) and Chapter 26 (Table 3, Figures 3–4, Tables 6–7). Used later by: Chapter 29. Purpose: read the authors' own list of limitations one item at a time, say what each means for the headline numbers, and put numbers on the two that can be quantified.

The problem this chapter solves¶

Everything in this section is MY EXPLANATION unless tagged.

A paper's discussion section is where the authors step back. They restate what they think they showed, and they list what they did not show. A reader who skips it tends to read the headline ("non-vacuous bounds for LLMs") more broadly than the authors meant.

PAPER §8, p. 9 The paper's discussion is short: one summary paragraph, six one-paragraph limitations, and a closing sentence hoping that future work addresses them. The Impact Statement (p. 10) adds one more caveat, about biases.

Each limitation is one or two sentences long. That is too short to tell a newcomer which ones are minor research directions and which ones change how to read the results. This chapter does that sorting. For each limitation we answer three questions:

What does it mean in plain words?
Does it change how we should read the headline claims?
Which chapter or demo of this explainer shows it?

Two limitations can be put into numbers with tools we already have: the first (documents versus tokens) and the fourth (models that write good text). The Impact Statement can be put into numbers too. The worked example does all three.

Intuition (and where the analogy breaks)¶

Everything in this section is MY EXPLANATION.

Think of a crash-safety certificate. An agency crashes a scale model of a car many times on one test track and certifies: "with 95 % confidence, the average damage to this scale model on tracks like this one is below X."

The paper's limitations map onto this picture:

Counting crashes, not metres. The agency counts each whole crash as one test. Each crash also produced thousands of sensor readings, but readings within one crash are tied together, so they cannot count as separate tests. (Limitation 1: documents, not tokens.)
Certifying the scale model, not the car you drive. The certificate covers the specially built scale model. The car on the road is a different object. (Limitations 2 and 4: the bounded model is trained from scratch in a compressed form and writes poor text.)
Only tracks like this one. The certificate says nothing about ice or gravel. (Limitation 6: beyond the training distribution.)
Only average damage. It says nothing about who gets hurt in the rare bad crash. (Impact Statement: biases.)

Where it breaks: a scale model is a smaller copy of the real car. The certified SubLoRA model is not a smaller copy of GPT-2. It has the same architecture, but its parameters are pinned to a tiny random subspace, and its predictions are much worse (validation BPD 10.53 against 4.35, Table 2). Also, the crash certificate is about a physical quantity anyone can measure later. The paper's certificate is about the expected loss on fresh documents from the same source, which nobody measures directly; that is why a bound is needed at all.

What the paper says, precisely¶

The summary claim¶

PAPER §8, p. 9 The authors say they showed that LLMs can "form highly compressed representations of distributions over text". With these compressed LLMs they computed what they call the first non-vacuous generalization bounds for LLM pretraining. They conclude that tighter compression bounds are a promising way to understand how and why language models generalize.

MY EXPLANATION Every word of this summary is supported by the bound for one specific object: a GPT-2-shaped network whose parameters are \(\theta = \theta_0 + \mathrm{LoRA}(\phi_0 + Pw)\) (erratum E10 adds \(\phi_0\)), with \(w\) quantized and arithmetic-coded, and with predictions smoothed with weight \(\alpha\). "Highly compressed" is accurate: 135,434 bits for the best model (printed by ch27_discussion.py below). "Representations of distributions over text" is accurate in the sense that the model assigns a probability to every document. But the distribution it represents is a poor one, as limitation 4 admits. Chapter 29 weighs the summary against each claim.

Limitation 1: non-i.i.d. token-level bounds¶

PAPER §8, p. 9 The bounds treat whole documents as the independent samples. Each document's loss is itself an average over many tokens that are not independent. The authors expect that this token structure could be used to raise the effective number of training samples a lot.

MY EXPLANATION In plain words: the bound's sample size is \(m\) = 8,009,762 documents (SOURCE: nanoGPT split, erratum E32), even though the training set contains about 9.04 billion tokens. Only the documents are assumed independent, so only they count (Chapter 15). Tokens inside one document are dependent, and Chapter 15's demo showed that pretending they are independent makes a Hoeffding bound fail far more often than \(\delta\) allows (20.88 % instead of at most 5 % for mildly sticky losses, printed by ch15_iid.py).

A token-level bound would be one that counts tokens, not documents, as its data points. That is what this limitation asks for, and it needs new mathematics because the tokens are dependent.

Does it change the headline? No. The published bound is valid as stated; it is just looser than it might be. The worked example below shows how much looser, at most.

Limitation 2: efficient bounds for already-pretrained models¶

PAPER §8, p. 9 The procedure requires training the LLM from scratch in SubLoRA form. The authors hope for a fast way to bound a model that has already been pretrained in the usual way, while still controlling its generalization error.

MY EXPLANATION In plain words: the bound is not about GPT-2 as released, or about any model trained the normal way. It is about a model that was trained, from the start, with only \(d \le\) 200,000 free numbers \(w\). A normally trained model has about 124 million free numbers, and its compressed size is far too large for a non-vacuous bound: Table 1's "Original Model" bound is 70.76 bits per token, above the random-guess level of 15.62 (Chapter 25).

Appendix D does bound models that start from a pretrained GPT-2, so the two can look contradictory. They are not. There, the pretrained weights play the role of \(\theta_0\): they are fixed before the fine-tuning data is seen, so they cost nothing in the prior, and the bound is about the fine-tuning task (QQP or CoLA). The pretraining step itself is not bounded (Chapter 26).

Does it change the headline? Yes, in scope. "Bounds for LLMs" means bounds for specially trained compressed LLMs.

Limitation 3: nonlinear parameterizations¶

PAPER §8, p. 9 Earlier bounds (Lotfi et al. 2022) used a linear parameterization; this paper's LoRA-based one is nonlinear and gives much better bounds. The authors suggest searching for richer nonlinear parameterizations that have few parameters but can still fit the training data.

MY EXPLANATION This is a research direction more than a limitation. A nonlinear parameterization (defined in Chapter 20) is a map from the stored numbers \(w\) to the network weights that is not of the form "matrix times \(w\)". In SubLoRA, the update is a product \(BA\) of two factors, and both depend on \(w\), so the update is quadratic in \(w\). Table 1 supports the claim: best BPD bounds 12.12 (SubLoRA), 13.09 (LoRA) and 14.59 (linear subspace) bits per token (printed by ch25_tables_audit.py).

Does it change the headline? No.

Limitation 4: bounds for models that generate high-quality text¶

PAPER §8, p. 9; App. F, p. 17; Tables 6–7, pp. 18–19 The authors show text sampled at temperature 0.8 from a GPT-2-style model trained the usual way (Table 6) and from one trained with SubLoRA (Table 7). The first writes sensible sentences; the second often writes ungrammatical text.

MY EXPLANATION "Often ungrammatical" understates Table 7: it is mostly word salad, with "the" repeated many times. The numbers agree. The SubLoRA model's validation BPD is 10.53 bits per token, a perplexity of about 1,479; the ordinary model's is 4.35, a perplexity of about 20 (printed by ch25_tables_audit.py). Our own mini replication shows the same split: the certified model writes letter salad, the uncertified one writes sentences (Chapter 28).

Does it change the headline? Yes, more than any other item. The bound certifies a model that nobody would use to generate text. The worked example below estimates how far a model of GPT-2's quality is from a non-vacuous bound.

Paper erratum E68: Tables 6–7 do not say which models were sampled

PAPER App. F, p. 17; Tables 6–7 App. F gives the temperature (0.8) and nothing else. It does not say which SubLoRA configuration produced Table 7 (\(d\), \(r\), \(L_q\), model size), whether the samples come from the quantized model, whether smoothing with weight \(\alpha\) was applied while sampling, or what prompt (if any) started each sample. For Table 6, §8 says only that the model was trained the usual way, and the caption calls it a pretrained 124-million-parameter GPT-2 small. That could mean OpenAI's released checkpoint or the authors' own nanoGPT run.

MY EXPLANATION No number changes. But the reader cannot check that Table 7 shows the same model whose bound is in Table 1. (Separately, Table 7's <|endoftext|> token is typeset as "¡—endoftext—¿"; erratum E42, logged by Chapter 4.)

Limitation 5: alternative ways of learning with LLMs¶

PAPER §8, p. 9 Modern LLMs allow new ways of using them, such as in-context learning and prompt tuning. These are widely deployed, and the authors say they deserve their own generalization theory.

MY EXPLANATION Two new terms, one sentence each. A prompt is the text given to a model before it starts generating. In-context learning is a model doing a new task from instructions or a few worked examples written into its prompt, with no change to its parameters. SOURCE: Lester et al. 2021, "The Power of Scale for Parameter-Efficient Prompt Tuning" Prompt tuning keeps every model weight frozen and trains only a short list of extra input vectors (a "soft prompt") that is placed in front of every input.

MY EXPLANATION Why the paper's bounds do not cover these: the bound is about one loss (next-token loss) on one population (random OpenWebText documents). In-context learning is judged by a different loss (for example, is the answer to the task correct?) on a different population (the task's questions), and its "training set" is the handful of examples in the prompt, which are not i.i.d. documents. Prompt tuning, in contrast, fits the paper's framework quite naturally: a soft prompt is a small set of trained numbers on top of a fixed pretrained model, much like the fine-tuning bounds of Appendix D.

Does it change the headline? No, but it marks a boundary: the bound says nothing about how well a model follows prompts.

Limitation 6: generalization beyond the training distribution¶

PAPER §8, p. 9 The authors cite three works on models doing well on data unlike their training data, and suggest generalization theory may help explain this:

PAPER §8 Goldblum et al. (2023): language models prefer low-complexity numerical sequences they were never trained on, even at random initialization. SOURCE: Goldblum et al. 2023, title and abstract; not checked against a file in this project's sources That paper argues that real-world data and neural networks share a bias toward low Kolmogorov complexity. (Goldblum is also an author of the present paper.)
PAPER §8 Hegselmann et al. (2023): LLMs generalizing to tabular data. SOURCE: Hegselmann et al. 2023, "TabLLM" They classify table rows by writing each row as text and giving it to an LLM with few or no labelled examples.
PAPER §8 Delétang et al. (2023): LLMs generalizing to images. SOURCE: Delétang et al. 2023, "Language Modeling Is Compression" They use LLMs with arithmetic coding as general-purpose compressors, including for image and audio data.

MY EXPLANATION The plain meaning: out-of-distribution generalization is doing well on data drawn from a different distribution than the training data. The paper's bound is silent about it by construction. Its population is "a document drawn the way the training documents were drawn" (Chapter 15). Chapter 15's filter demo made this concrete: a bound computed on documents of two topics failed in 100 % of runs as a statement about all topics (printed by ch15_iid.py).

Does it change the headline? Yes, in scope: "LLMs generalize" here means "to new OpenWebText-like documents".

The Impact Statement¶

PAPER Impact Statement, p. 10 The work aims to improve understanding and trustworthiness of LLMs. The authors note that many properties of LLMs, biases among them, may not be captured by generalization bounds.

MY EXPLANATION Here bias means a systematic, unfair tendency in a model's outputs, such as stereotypes it picked up from its training text. (This is unrelated to the "bias" vector added inside a linear layer, Chapter 5.) The caveat is correct and can be made sharper. A generalization bound says that the average loss on fresh documents is close to the average loss on training documents. If the training text is biased, a model that generalizes well reproduces the bias faithfully. And an average over all documents says almost nothing about a small group of documents. The worked example computes how little.

Follow-up work¶

SOURCE: Lotfi et al., "Unlocking Tokens as Data Points for Generalization Bounds on Larger Language Models", arXiv 2407.18158, NeurIPS 2024 The same group later proposed bounds that use tokens, rather than documents, as the data points, which is limitation 1's direction. This explainer has not studied that paper and does not report its results.

Worked example with real numbers¶

Everything in this section is MY EXPLANATION; the numbers are printed by ch27_discussion.py unless another script is named. δ = 0.05 SOURCE: authors' code, m = 8,009,762 documents and 9,035,582,198 tokens [SOURCE: nanoGPT prepare.py, erratum E32].

Limitation 1: how much could tokens help, at most?¶

Divide tokens by documents: \(9{,}035{,}582{,}198 / 8{,}009{,}762 = 1{,}128.07\) tokens per document. If every token were an independent sample, \(m\) would grow 1,128-fold.

In Eq. (3), \(m\) appears only in the first complexity term (the "m-term"), as \(1/\sqrt m\). So that term would shrink by \(\sqrt{1{,}128.07} = 33.59\). The second complexity term (the "n-term") comes from the subsample of \(n\) = 10,000 documents and does not depend on \(m\).

Take the paper's best model (Figure 2: compressed size 16.5325 KB = 135,434.26 bits, \(\alpha\) = 0.25, so the loss range is \(\Delta\) = 17.2020 bits per token, and subsampled empirical risk 10.5945 bits per token). Now suppose each document were worth \(k_{\text{eff}}\) independent samples:

independent samples per document	m-term (bits/token)	n-term (bits/token)	bound (bits/token)
1 (as published)	1.3171	0.2106	12.1222
10	0.4165	0.2105	11.2216
100	0.1317	0.2105	10.9368
1,128.1 (every token)	0.0392	0.2105	10.8443

The first row reproduces Table 1's 12.12. The last row is a hypothetical upper limit, not a valid bound: real tokens are positively dependent, so a document is worth fewer than 1,128 independent samples (Chapter 15's effective sample size). Even in that best case the bound only falls from 12.12 to 10.84. The reason is visible in the table: the empirical risk, 10.59, is most of the bound. Better token-level statistics cannot make a weak model look strong.

The n-term sets a floor: with infinitely many samples the bound could not go below \(10.5945 + 0.2106 = 10.8051\) bits per token, unless the subsample also grew.

Limitation 4: what would a GPT-2-quality model need?¶

Assume, for illustration, a model whose smoothed empirical risk equals GPT-2's validation BPD of 4.35 (Table 2) plus the largest possible smoothing premium, \(\log_2\frac{1}{1-\alpha}\). How large can its compressed size \(C\) be while Eq. (3) stays below the random-guess level \(\log_2 V = 15.617\)?

\(\alpha\)	smoothed risk (bits/token)	max size, documents as samples	max size, tokens as samples (hypothetical)
0.05	4.424	0.84 MiB	944.3 MiB
0.10	4.502	0.92 MiB	1,043.3 MiB
0.25	4.765	1.05 MiB	1,189.4 MiB
0.50	5.350	1.15 MiB	1,293.7 MiB

GPT-2 small stored as 32-bit floats is 471.8 MiB (123,689,472 parameters). So at the document level, a model as good as GPT-2 would have to fit in about 1.15 MiB, which is 0.078 bits per parameter, 411 times smaller than float32. The paper's best SubLoRA model uses 0.00109 bits per parameter but predicts far worse. In the hypothetical where every token counted as an independent sample, even uncompressed float32 GPT-2 would fit with room to spare (2.0–2.7 times its size). This is why limitations 1 and 4 belong together: a valid token-level argument is the most direct route to bounding models that write well. It is also why the follow-up work cited above went in that direction.

Impact Statement: what does the bound say about a small group?¶

Take any group of documents (say, documents on one topic, or in one dialect) that makes up a fraction \(f\) of the population. The headline result says the expected smoothed loss is at most 12.1222 bits per token. The smoothed loss is never below 0.4150 bits per token at \(\alpha\) = 0.25 (Theorem A.2's lower end). From these two facts alone, the group's expected loss is at most \((12.1222 - (1-f)\cdot 0.4150)/f\). Call this the subgroup ceiling:

group share \(f\)	guaranteed ceiling on the group's loss (bits/token)
100 %	12.12
90 %	13.42
50 %	23.83 (vacuous)
25 %	47.24 (vacuous)
1 %	1,171.13 (vacuous)

The ceiling is below the random-guess level only for groups larger than 77.0 % of all documents. In the other direction, a group of 1 % of documents whose loss is 5 bits per token worse than the rest moves the overall average by only 0.05 bits per token, much less than the bound's 1.53-bit complexity allowance. A good average guarantee is compatible with very poor performance on any minority of documents.

Going deeper¶

This hub collects the derivations behind the worked example. Everything below is MY EXPLANATION.

Going deeper: why the m-term shrinks by exactly the square root, and why 1,128 is an upper limit

MY EXPLANATION The m-term of Eq. (3) (Chapter 17) is

\[ t_m = \Delta\sqrt{\frac{\ln\frac{1}{P(h)} + \ln\frac{1}{s\delta}}{2m}}, \qquad s = \frac{n}{n+m}. \]

Here \(\Delta\) is the loss range in bits per token, \(\ln\frac1{P(h)}\) is the price of the model in nats, \(\delta\) is the failure probability and \(s\) is the share of \(\delta\) given to this term. The probability statement behind it is over the random draw of the \(m\) documents; the hypothesis \(h\) is fixed by the prior.

Replace \(m\) by \(km\). The numerator changes only through \(\ln\frac1{s\delta}\), because \(s = n/(n+km)\) gets smaller: \(\ln\frac{1}{s\delta}\) grows from about \(\ln\frac{m}{n\delta} = 9.68\) nats to \(\ln\frac{km}{n\delta}\). That is tiny against \(\ln\frac1{P(h)} \approx 135{,}434 \ln 2 \approx 93{,}900\) nats. So

\[ \frac{t_m(m)}{t_m(km)} = \sqrt{k}\cdot\sqrt{\frac{\ln\frac1{P(h)} + \ln\frac{m+n}{n\delta}}{\ln\frac1{P(h)} + \ln\frac{km+n}{n\delta}}} \approx \sqrt k , \]

and the script prints a ratio of 33.59 for \(k = 1{,}128.07\), equal to \(\sqrt k\) to two decimals.

Why \(k\) = tokens per document is an upper limit on the useful \(k\). Let a document have \(L\) tokens with per-token losses \(Z_1,\dots,Z_L\), each with variance \(\sigma^2\), and correlation \(\rho_{ij}\) between positions \(i\) and \(j\). The variance of the document's average loss is

\[ \operatorname{Var}\Big(\frac1L\sum_{i=1}^L Z_i\Big) = \frac{1}{L^2}\Big(\sum_i \sigma^2 + \sum_{i\ne j}\rho_{ij}\sigma^2\Big) = \frac{\sigma^2}{L}\Big(1 + \frac1L\sum_{i\ne j}\rho_{ij}\Big). \]

The effective sample size (Chapter 15) is the number \(k_{\text{eff}}\) of independent losses whose average has the same variance: \(\sigma^2/k_{\text{eff}}\) equals the expression above, so \(k_{\text{eff}} = L/(1 + \frac1L\sum_{i\ne j}\rho_{ij})\). When all correlations are \(\ge 0\), as they are for the losses of neighbouring tokens in real text, the bracket is \(\ge 1\) and \(k_{\text{eff}} \le L\). So treating every token as independent is the most optimistic case. Note also that a variance argument is not a tail bound; a valid token-level bound needs a different concentration tool (next block).

Going deeper: one tool for dependent tokens (Azuma–Hoeffding), and what it bounds

MY EXPLANATION This block shows why "use the tokens" is not a one-line change. It proves a standard inequality for dependent sequences and then shows that it bounds a different quantity.

Let \(Z_i \in [a, b]\) be the loss on token \(i\) and let \(\mathcal F_{i-1}\) stand for "everything up to token \(i-1\)" (the context). Define \(D_i = Z_i - \mathbb E[Z_i \mid \mathcal F_{i-1}]\), the surprise in the loss beyond what the context predicts. Each \(D_i\) has conditional mean 0 and lies in an interval of length \(b-a\) once the context is fixed.

Step 1 (Hoeffding's lemma, applied conditionally). Chapter 9 proved that a mean-zero variable in an interval of length \(b-a\) satisfies \(\mathbb E[e^{\lambda X}] \le e^{\lambda^2(b-a)^2/8}\). Given the context, \(D_i\) is such a variable, so \(\mathbb E[e^{\lambda D_i}\mid\mathcal F_{i-1}] \le e^{\lambda^2(b-a)^2/8}\).

Step 2 (peel one term at a time). With \(S_L = \sum_{i=1}^L D_i\), use the tower rule (Chapter 1) and the fact that \(S_{L-1}\) is fixed once \(\mathcal F_{L-1}\) is known:

\[ \mathbb E[e^{\lambda S_L}] = \mathbb E\big[e^{\lambda S_{L-1}}\,\mathbb E[e^{\lambda D_L}\mid\mathcal F_{L-1}]\big] \le e^{\lambda^2(b-a)^2/8}\,\mathbb E[e^{\lambda S_{L-1}}]. \]

Repeating \(L\) times gives \(\mathbb E[e^{\lambda S_L}] \le e^{L\lambda^2(b-a)^2/8}\).

Step 3 (Chernoff, as in Chapter 9). For any \(\lambda > 0\), Markov's inequality applied to \(e^{\lambda S_L}\) gives \(\Pr[S_L \ge Lt] \le e^{-\lambda Lt}\,\mathbb E[e^{\lambda S_L}] \le e^{-\lambda Lt + L\lambda^2(b-a)^2/8}\). The exponent is smallest at \(\lambda = 4t/(b-a)^2\), where it equals \(-4Lt^2/(b-a)^2 + 2Lt^2/(b-a)^2 = -2Lt^2/(b-a)^2\). So

\[ \Pr\Big[\frac1L\sum_{i=1}^L D_i \ge t\Big] \le e^{-2Lt^2/(b-a)^2}, \]

the same form as Hoeffding with \(L\) tokens as the sample size. This is the Azuma–Hoeffding inequality. Here the probability is over the random tokens of the text; the model is fixed.

What it bounds. The event is about \(\frac1L\sum_i (Z_i - \mathbb E[Z_i\mid\mathcal F_{i-1}])\): the gap between the observed losses and the losses expected given each token's actual context. The paper's risk \(R(h)\) is the expected loss on a fresh document, a different quantity. Turning a token-level statement into a statement about fresh documents, or deciding which of the two is the right target, is the real work. This explainer does not analyse how the follow-up paper does it.

Going deeper: the compression budget of a GPT-2-quality model

MY EXPLANATION We want the largest \(C\) (bits) with

\[ \hat{\hat R} + \Delta\sqrt{\frac{(C + 2\log_2 C)\ln 2 + \ln\frac{1}{s\delta}}{2m}} + t_n \le \log_2 V, \]

where \(\hat{\hat R}\) is the smoothed empirical risk (bits/token), \(t_n = \Delta\sqrt{\ln\frac{1}{(1-s)\delta}/(2n)}\) is the n-term, and the price \((C + 2\log_2 C)\ln 2\) nats is the paper's §4.1 form (Chapter 14). Move everything except the square root to the right, square, and solve:

\[ (C + 2\log_2 C)\ln 2 \le 2m\Big(\frac{\log_2 V - \hat{\hat R} - t_n}{\Delta}\Big)^2 - \ln\frac1{s\delta}. \]

At \(\alpha = 0.25\): \(\hat{\hat R} = 4.35 + \log_2\frac{1}{0.75} = 4.765\) (assumed), \(t_n = 0.2106\), \(\Delta = 17.2020\), so the bracket is \((15.617 - 4.765 - 0.2106)/17.2020 = 0.6186\). Its square times \(2m\) is about \(6.13\times10^6\) nats, i.e. about \(8.84\times 10^6\) bits after dividing by \(\ln 2\); the two small corrections (\(2\log_2 C \approx 46\) bits and \(\ln\frac1{s\delta}\) of about 9.7 nats) barely move it. The script solves the inequality exactly by bisection and prints 8,844,279 bits = 1.05 MiB. Replacing \(m\) by the token count multiplies the right side by about 1,128.

Why the smoothing premium is at most \(\log_2\frac1{1-\alpha}\): the smoothed probability is \(p_h = (1-\alpha)p_\theta + \alpha/V \ge (1-\alpha)p_\theta\) (Chapter 16), so \(-\log_2 p_h \le -\log_2 p_\theta + \log_2\frac1{1-\alpha}\) token by token.

Two assumptions are labelled, not hidden: 4.35 is a validation BPD standing in for a training risk (they differ by the generalization gap), and the paper does not state whether its BPDs are document or token averages (erratum E28).

Going deeper: the subgroup ceiling, and why it costs no extra confidence

MY EXPLANATION Let \(G\) be any set of documents, with population share \(\Pr[X\in G] = f\) (the probability is over one fresh random document \(X\)). Write \(R_G = \mathbb E[\ell(h,X)\mid X\in G]\) for the group's expected smoothed loss and \(R_{\bar G}\) for the rest. By the law of total probability for expectations (Chapter 1),

\[ R(h) = f\,R_G + (1-f)\,R_{\bar G} \ge f\,R_G + (1-f)\,\ell_{\min}, \]

because every smoothed loss is at least \(\ell_{\min} = \log_2\frac{V}{\alpha} - \Delta(\alpha) = 0.4150\) bits/token at \(\alpha = 0.25\) (Theorem A.2, Chapter 16). Rearranging,

\[ R_G \le \frac{R(h) - (1-f)\,\ell_{\min}}{f}. \]

On the event (probability at least 0.95 over the draw of the documents and the subsample) that \(R(h) \le\) 12.1222, this ceiling holds for every group at once: it is a deterministic consequence of one inequality, so no union bound is needed, and the group may even be chosen after looking at the model's errors. What must be used is the group's share \(f\) in the population, not its share in the training sample. The ceiling is below \(\log_2 V\) exactly when \(f > (R - \ell_{\min})/(\log_2 V - \ell_{\min}) = 0.770\). It also never needs to exceed \(\log_2\frac{V}{\alpha} = 17.6170\), since no smoothed loss can be larger; for \(f = 0.5\) the formula's 23.83 is already worse than that trivial cap.

A tight statement about a small group needs a bound computed on that group: its own \(m\) (documents of that group), so a much larger m-term.

Common misconceptions¶

Misconception: The §8 list covers everything that limits the results. — Actually: it omits several issues this explainer found: choosing \(\alpha\) and \(d\) on the same subsample used in the n-term (erratum E07), single runs without error bars for the scaling claims (Chapter 26), and the fact that the bound is about the smoothed, quantized model. Chapter 29 collects them.
Misconception: Token-level bounds would make the published bound about 34 times tighter. — Actually: only the m-term shrinks, and only in the impossible case of independent tokens. For the best model that takes the bound from 12.12 to 10.84 bits per token, because the empirical risk (10.59) is most of the bound and the n-term (0.21) does not shrink.
Misconception: A non-vacuous bound means the model is a good language model. — Actually: the certified model has perplexity about 1,479 and writes word salad (Table 7). Non-vacuous only means "better than uniform guessing over 50,257 tokens".
Misconception: "Already-pretrained models cannot be bounded" contradicts Appendix D, which starts from pretrained GPT-2. — Actually: Appendix D bounds fine-tuning, with the pretrained weights fixed before the fine-tuning data is seen. Limitation 2 is about bounding the pretraining itself.
Misconception: A model with a good generalization bound is fair or unbiased. — Actually: the bound controls an average over all documents; it guarantees nothing non-vacuous for any group under 77.0 % of documents, and a model that generalizes well reproduces whatever biases its training text has.

Self-test¶

Q1. Suppose each OpenWebText document were worth 100 independent samples. Using the best model's terms (m-term 1.3171, n-term 0.2106, subsampled empirical risk 10.5945, all in bits per token), estimate the new bound. Why does the n-term not change?

Answer

The m-term scales as \(1/\sqrt m\), so it becomes \(1.3171/\sqrt{100} = 0.1317\) bits per token. The bound is \(10.5945 + 0.1317 + 0.2105 = 10.9368\) bits per token (the script prints exactly this row; the n-term moves from 0.2106 to 0.2105 because \(s = n/(n+m)\) shrinks slightly). The n-term comes from the Hoeffding step over the \(n\) = 10,000 subsampled documents (Chapter 17); its sample size is \(n\), not \(m\), so making \(m\) larger does not shrink it. This is an illustration only: no theorem in the paper licenses counting 100 samples per document.

Q2. Of the six limitations, which one most changes how you should read the summary claim that LLMs "form highly compressed representations of distributions over text"? Explain in two or three sentences.

Answer

Limitation 4 (models that generate high-quality text). The compressed object is a real language model, but a weak one: validation BPD 10.53 (perplexity about 1,479) against 4.35 for the ordinary model, and its samples are word salad. So the claim is true of a highly compressed representation of a poor distribution over text, not of the distribution a useful LLM represents; the worked example shows a GPT-2-quality model would need to fit in about 1 MiB for a document-level bound. Limitation 2 is a close second, since it says the bounded model is not one trained the normal way.

Q3. The headline bound holds with probability at least 95 %. A critic says: "Then it also guarantees, with the same confidence, that the model's expected loss on documents written in a dialect that makes up 25 % of the data is below the random-guess level." Is the critic right?

Answer

No. The bound does give a guarantee for that group with no extra loss of confidence, since it follows deterministically from the one inequality \(R \le 12.1222\). But the guarantee is weak: \(R_G \le (12.1222 - 0.75 \times 0.4150)/0.25 = 47.24\) bits per token, far above \(\log_2 V = 15.617\). Only groups larger than 77.0 % of documents get a non-vacuous ceiling this way. (The probability is over the random draw of the training documents and of the subsample; the model and the group's population share are fixed numbers.)

Code for this chapter¶

Run it from the project root:

.venv/Scripts/python explainer/code/ch27_discussion.py

Source: ch27_discussion.py

"""Chapter 27 - the paper's own discussion (§8): putting numbers on the first and fourth limitations.

Claims illustrated (all [MY ANALYSIS] unless tagged):
  [1] §8 "Non I.I.D. token level bounds": documents are the sample unit, but each document holds many tokens.
      Tokens per document = 9,035,582,198 / 8,009,762 [SOURCE nanoGPT prepare.py; erratum E32].
  [2] What Eq. (3) would give for the paper's best model (Fig. 2: C = 16.5325 KB, alpha = 0.25, empirical risk
      10.5945 bits/token, read from the PDF by fig_extract.py) if each document were worth k_eff independent samples.
      k_eff = tokens per document is an ILLUSTRATIVE UPPER BOUND; it is NOT a valid bound (tokens are dependent, Ch. 15).
  [3] The m -> infinity floor: the subsample term (n = 10,000) does not shrink with m.
  [4] §8 "Bounds for models that generate high quality text": how small a model with GPT-2's validation BPD (4.35,
      Table 2) would have to be compressed for a non-vacuous document-level bound, and how much larger it could be if
      tokens counted as samples.  Uses the cap on the smoothing premium, log2(1/(1-alpha)).
  [5] Impact Statement (biases): what the headline bound implies about a subgroup that is a fraction f of documents.
      Since the smoothed loss is >= lo(alpha) > 0, E[loss | group] <= (R - (1-f) lo) / f; find the smallest f for
      which this is below log2 V.
Deterministic, no randomness; runtime < 1 s.
"""
from __future__ import annotations

import json
import math
import sys
from pathlib import Path

HERE = Path(__file__).resolve().parent
sys.path.insert(0, str(HERE))
import pacbound as pb  # noqa: E402

OUT_TXT = HERE / "outputs" / "ch27_discussion.txt"
OUT_TXT.parent.mkdir(parents=True, exist_ok=True)
DATA = json.loads((HERE / "outputs" / "fig_extract.json").read_text(encoding="utf-8"))

KB = 8192.0                       # bits per KB [SOURCE Lotfi et al. 2022; erratum E35]
M, N, DEL = pb.M_DOCS, pb.N_SUB, pb.DELTA
TOK = pb.OWT_TRAIN_TOKENS
LOG2V = pb.random_guess_bpd()

LINES: list[str] = []


def out(s: str = "") -> None:
    print(s)
    LINES.append(s)


def price(c_bits: float) -> float:
    """ln 1/P(h) in nats for a C-bit model (§4.1 form, no hyperparameter bits, as in Ch. 15 and 25)."""
    return pb.log_inv_prior_nats_from_bits(c_bits)


def width(alpha: float) -> float:
    return pb.smoothing_interval(alpha)[2]


out("Chapter 27 - numbers for the section 8 limitations (ch27_discussion.py)")
out(f"delta = {DEL} [SOURCE authors' code], m = {M:,} documents, OpenWebText train tokens {TOK:,} "
    f"[SOURCE nanoGPT], n = {N:,}")

# [1] tokens per document ------------------------------------------------------------------------
tpd = TOK / M
out()
out(f"[1] tokens per document = {TOK:,} / {M:,} = {tpd:,.2f} tokens (incl. end-of-text)")
out(f"    sqrt(tokens per document) = {math.sqrt(tpd):.2f}  (shrink factor of the m-term if every token were an "
    f"independent sample)")
assert abs(tpd - 1128.1) < 0.05

# [2] best model under different effective sample sizes -------------------------------------------
C_BEST = DATA["figure2"]["left"]["compressed_size_kb"][4]["value"] * KB
EMP = DATA["figure2"]["left"]["empirical_risk"][4]["value"]
A = 0.25
W = width(A)
t_m0, t_n0 = pb.eq3_terms(price(C_BEST), M, N, DEL, width=W)
b0 = EMP + t_m0 + t_n0
out()
out(f"[2] Best model (Fig. 2): C = {C_BEST:,.2f} bits = {C_BEST / KB:.4f} KB, alpha = {A}, Delta = {W:.4f} "
    f"bits/token, R^^ = {EMP:.4f} bits/token")
out(f"    Eq. (3) as published (documents): m-term {t_m0:.4f} + n-term {t_n0:.4f} -> bound {b0:.4f} "
    f"(paper 12.12; diff {b0 - 12.12:+.4f})")
assert abs(round(b0, 2) - 12.12) < 1e-9
out("    HYPOTHETICAL m = k_eff x documents (not a valid theorem; Ch. 15 shows tokens are dependent):")
out("      k_eff (indep. samples/doc) |  m used        |  m-term | n-term |  bound  | below random guess by")
for k in (1, 10, 100, tpd):
    mm = round(k * M)
    tm, tn = pb.eq3_terms(price(C_BEST), mm, N, DEL, width=W)
    out(f"      {k:>27,.1f} | {mm:>14,} | {tm:7.4f} | {tn:6.4f} | {EMP + tm + tn:7.4f} | {LOG2V - (EMP + tm + tn):6.3f}")
tm_tok, _ = pb.eq3_terms(price(C_BEST), TOK, N, DEL, width=W)
out(f"    m-term ratio documents/tokens = {t_m0 / tm_tok:.2f} (vs sqrt(tokens per doc) {math.sqrt(tpd):.2f})")

# [3] m -> infinity floor --------------------------------------------------------------------------
out()
out(f"[3] As m -> infinity the m-term -> 0 but the n-term stays {t_n0:.4f} bits/token "
    f"(Delta x sqrt(ln(1/delta)/(2n)) = {W * math.sqrt(math.log(1 / DEL) / (2 * N)):.4f}); "
    f"floor of the bound = {EMP + t_n0:.4f}")


# [4] high-quality text: compression a GPT-2-quality model would need -----------------------------
def max_c_bits(emp: float, m: int, alpha: float) -> float:
    """Largest C (bits) with Eq. (3) bound <= log2 V at mixing weight alpha (bisection on log C)."""
    lo, hi = 2.0, 1e14
    for _ in range(200):
        mid = math.sqrt(lo * hi)
        if pb.eq3_bound(emp, price(mid), m, N, DEL, width=width(alpha)) <= LOG2V:
            lo = mid
        else:
            hi = mid
    return lo


VAL_GPT2 = 4.35                       # [PAPER Table 2] validation BPD of the ordinary GPT-2 small model
D_SMALL = pb.gpt2_params(12, 768)     # nanoGPT count, Ch. 5
F32 = 32 * D_SMALL
out()
out(f"[4] ASSUMED smoothed empirical risk of a GPT-2-quality model = 4.35 (Table 2 validation BPD) + premium cap "
    f"log2(1/(1-alpha)); non-vacuous means bound <= log2 V = {LOG2V:.3f}")
out(f"    GPT-2 small: D = {D_SMALL:,} params; float32 size = {F32:,} bits = {F32 / 8 / 2**20:,.1f} MiB")
out("    alpha | smoothed R^ | max C, documents (m = 8.0M)   | max C, tokens as samples (m = 9.04e9)")
for a in (0.05, 0.1, 0.25, 0.5):
    emp = VAL_GPT2 + math.log2(1 / (1 - a))
    cd, ct = max_c_bits(emp, M, a), max_c_bits(emp, TOK, a)
    out(f"    {a:5.2f} | {emp:11.3f} | {cd:12,.0f} bits = {cd / 8 / 2**20:5.2f} MiB | "
        f"{ct:15,.0f} bits = {ct / 8 / 2**20:7.1f} MiB ({ct / F32:4.2f} x float32)")
best_doc = max(max_c_bits(VAL_GPT2 + math.log2(1 / (1 - a)), M, a) for a in pb.ALPHA_GRID)
out(f"    best over the paper's alpha grid, documents: {best_doc:,.0f} bits = {best_doc / D_SMALL:.3f} bits/param "
    f"({F32 / best_doc:,.0f}x smaller than float32)")
out(f"    paper's best SubLoRA model: {C_BEST:,.0f} bits = {C_BEST / D_SMALL:.5f} bits/param, validation BPD 10.53 "
    f"(Table 2)")

# [5] subgroups ----------------------------------------------------------------------------------
lo = pb.smoothing_interval(A)[0]
R_BOUND = b0
out()
out(f"[5] Subgroups (Impact Statement). Bound R <= {R_BOUND:.4f} bits/token (alpha {A}); smoothed loss >= lo = "
    f"{lo:.4f} and <= hi = log2(V/alpha) = {pb.smoothing_interval(A)[1]:.4f} bits/token")
out("    guaranteed ceiling on a subgroup's expected loss, (R - (1-f) lo)/f, for a subgroup with fraction f of documents:")
for f in (1.0, 0.9, 0.5, 0.25, 0.1, 0.01):
    out(f"      f = {f:4.2f}: {(R_BOUND - (1 - f) * lo) / f:9.2f} bits/token"
        + ("   (vacuous: above log2 V)" if (R_BOUND - (1 - f) * lo) / f > LOG2V else ""))
f_min = (R_BOUND - lo) / (LOG2V - lo)
out(f"    non-vacuous only if f > (R - lo)/(log2 V - lo) = {f_min:.3f}")
out("    a subgroup of 1 % of documents whose loss is 5 bits/token worse moves the average by 0.01 x 5 = "
    f"{0.01 * 5:.2f} bits/token")

# [6] numbers used in the chapter's derivations -----------------------------------------------------
s_doc = N / (N + M)
br = (LOG2V - (VAL_GPT2 + math.log2(1 / 0.75)) - t_n0) / W
out()
out(f"[6] Derivation checks: ln 1/P(best) = {price(C_BEST):,.0f} nats; ln(1/(s delta)) at m docs = "
    f"{math.log(1 / (s_doc * DEL)):.2f} nats; total complexity (m-term + n-term) = {t_m0 + t_n0:.4f} bits/token")
out(f"    budget at alpha 0.25: (log2 V - 4.765 - n-term)/Delta = {br:.4f}; 2 m x that^2 = {2 * M * br * br:,.0f} nats "
    f"= {2 * M * br * br / math.log(2):,.0f} bits; 2 log2 C at 8.84e6 bits = {2 * math.log2(8.844e6):.1f} bits")

OUT_TXT.write_text("\n".join(LINES) + "\n", encoding="utf-8")

Output:

Chapter 27 - numbers for the section 8 limitations (ch27_discussion.py)
delta = 0.05 [SOURCE authors' code], m = 8,009,762 documents, OpenWebText train tokens 9,035,582,198 [SOURCE nanoGPT], n = 10,000

[1] tokens per document = 9,035,582,198 / 8,009,762 = 1,128.07 tokens (incl. end-of-text)
    sqrt(tokens per document) = 33.59  (shrink factor of the m-term if every token were an independent sample)

[2] Best model (Fig. 2): C = 135,434.26 bits = 16.5325 KB, alpha = 0.25, Delta = 17.2020 bits/token, R^^ = 10.5945 bits/token
    Eq. (3) as published (documents): m-term 1.3171 + n-term 0.2106 -> bound 12.1222 (paper 12.12; diff +0.0022)
    HYPOTHETICAL m = k_eff x documents (not a valid theorem; Ch. 15 shows tokens are dependent):
      k_eff (indep. samples/doc) |  m used        |  m-term | n-term |  bound  | below random guess by
                              1.0 |      8,009,762 |  1.3171 | 0.2106 | 12.1222 |  3.495
                             10.0 |     80,097,620 |  0.4165 | 0.2105 | 11.2216 |  4.395
                            100.0 |    800,976,200 |  0.1317 | 0.2105 | 10.9368 |  4.680
                          1,128.1 |  9,035,582,198 |  0.0392 | 0.2105 | 10.8443 |  4.773
    m-term ratio documents/tokens = 33.59 (vs sqrt(tokens per doc) 33.59)

[3] As m -> infinity the m-term -> 0 but the n-term stays 0.2106 bits/token (Delta x sqrt(ln(1/delta)/(2n)) = 0.2105); floor of the bound = 10.8051

[4] ASSUMED smoothed empirical risk of a GPT-2-quality model = 4.35 (Table 2 validation BPD) + premium cap log2(1/(1-alpha)); non-vacuous means bound <= log2 V = 15.617
    GPT-2 small: D = 123,689,472 params; float32 size = 3,958,063,104 bits = 471.8 MiB
    alpha | smoothed R^ | max C, documents (m = 8.0M)   | max C, tokens as samples (m = 9.04e9)
     0.05 |       4.424 |    7,022,023 bits =  0.84 MiB |   7,921,482,342 bits =   944.3 MiB (2.00 x float32)
     0.10 |       4.502 |    7,758,343 bits =  0.92 MiB |   8,752,108,004 bits =  1043.3 MiB (2.21 x float32)
     0.25 |       4.765 |    8,844,279 bits =  1.05 MiB |   9,977,126,179 bits =  1189.4 MiB (2.52 x float32)
     0.50 |       5.350 |    9,620,267 bits =  1.15 MiB |  10,852,500,741 bits =  1293.7 MiB (2.74 x float32)
    best over the paper's alpha grid, documents: 9,620,267 bits = 0.078 bits/param (411x smaller than float32)
    paper's best SubLoRA model: 135,434 bits = 0.00109 bits/param, validation BPD 10.53 (Table 2)

[5] Subgroups (Impact Statement). Bound R <= 12.1222 bits/token (alpha 0.25); smoothed loss >= lo = 0.4150 and <= hi = log2(V/alpha) = 17.6170 bits/token
    guaranteed ceiling on a subgroup's expected loss, (R - (1-f) lo)/f, for a subgroup with fraction f of documents:
      f = 1.00:     12.12 bits/token
      f = 0.90:     13.42 bits/token
      f = 0.50:     23.83 bits/token   (vacuous: above log2 V)
      f = 0.25:     47.24 bits/token   (vacuous: above log2 V)
      f = 0.10:    117.49 bits/token   (vacuous: above log2 V)
      f = 0.01:   1171.13 bits/token   (vacuous: above log2 V)
    non-vacuous only if f > (R - lo)/(log2 V - lo) = 0.770
    a subgroup of 1 % of documents whose loss is 5 bits/token worse moves the average by 0.01 x 5 = 0.05 bits/token

[6] Derivation checks: ln 1/P(best) = 93,900 nats; ln(1/(s delta)) at m docs = 9.68 nats; total complexity (m-term + n-term) = 1.5276 bits/token
    budget at alpha 0.25: (log2 V - 4.765 - n-term)/Delta = 0.6186; 2 m x that^2 = 6,130,428 nats = 8,844,339 bits; 2 log2 C at 8.84e6 bits = 46.2 bits