03. Logarithms, bits and nats

Where this fits

Prerequisites: none. (We use the everyday idea of a probability — a number between 0 and 1 that says how likely something is; Chapter 1 makes it precise.) Used later by: Chapter 4 (language models), Chapter 6 (bits per token), Chapters 11–14 (the bound's complexity term and compressed model sizes), Chapter 16 (prediction smoothing) and Chapter 22 (entropy and arithmetic coding). Purpose: give you the logarithm — the tool that turns probabilities and file sizes into the units the paper uses — and teach you to convert and check those units.

The problem this chapter solves

Everything in this section is MY EXPLANATION unless tagged.

The paper measures three different things with logarithms. It moves between their units without saying so. Before we can check a single number in the paper, we need to know what those units are.

PAPER §4.3, p. 5 The paper's main loss is called bits per dimension (BPD). It is defined with base-2 logarithms of the probabilities that a language model gives to the text it must predict.

Two words in that sentence belong to later chapters. A language model is a program that reads some text and gives a probability to every possible next piece of text. Those pieces are called tokens; a token is roughly a word or part of a word. Chapter 4 makes both words precise. Chapter 6 defines BPD; for now, think of it as the model's average "cost" per token, counted in bits (the 0s and 1s of computer memory, defined below).

PAPER Fig. 2, p. 5; Fig. 3, p. 8 The sizes of the compressed models are reported in kilobytes (KB), a unit of file size defined below.

PAPER §4.1, p. 4 The central bound, Eq. (1), contains the expressions "log 1/P(h)" and "log 1/δ". The text then bounds "log 1/P(h)" by "C(h) log 2 + 2 log C(h)", where C(h) is a number of bits. The paper never says which logarithm "log" means.

PAPER Table 1, p. 6; §6.2, p. 7 Table 1 lists 15.62 as the BPD of random guessing. Section 6.2 says that random guessing scores \(\log_2 V\), where \(V\) is the number of tokens the model can choose from.

This chapter gives you the tools to read all of this. You will learn what a logarithm is, what bits and nats (a second unit for the same thing) are, how to convert between them, and how to check that a formula uses its units correctly. By the end you will reproduce the 15.62 yourself.

Intuition (and where the analogy breaks)

Everything in this section is MY EXPLANATION unless tagged.

Think of the game "twenty questions". I pick a whole number from 1 to 8. You may only ask yes/no questions. How many questions do you need?

The best strategy halves the candidates every time. "Is it 4 or less?" Say yes: four candidates remain. "Is it 2 or less?" Two remain. "Is it 1?" Now you know. Three questions always suffice, because 8 → 4 → 2 → 1.

With 1,024 numbers you need 10 questions. Each doubling of the range costs exactly one more question.

So the number of questions answers one question: "2 to what power gives N?" For N = 8 the answer is 3, because 2 × 2 × 2 = 8. That answer has a name, the base-2 logarithm of N, written \(\log_2 N\). The script for this chapter prints \(\log_2 8 = 3\) and \(\log_2 1024 = 10\).

The answer to one fair yes/no question is the smallest unit of information. It is called one bit. So naming one of N equally likely things takes \(\log_2 N\) bits.

The game's name is well chosen. Twenty questions can tell apart \(2^{20} = 1{,}048{,}576\) things. That is enough to find one number in a million, since \(\log_2 1{,}000{,}000 = 19.932\).

[SOURCE: nanoGPT prepare.py; authors' code default vocab_size = 50257] The GPT-2 models in the paper choose among \(V = 50{,}257\) tokens. The paper itself never prints this number.

Our script plays the game over all 50,257 tokens with the halving strategy. No token ever needs more than 16 questions. 15,279 tokens need 15 questions and 34,978 need 16. The average is 15.696 questions, just above \(\log_2 50{,}257 = 15.617\).

Where it breaks. The analogy fails in two places.

First, \(\log_2 N\) is usually not a whole number. For example \(\log_2 3 = 1.585\), but nobody can ask 1.585 questions. To pick one item out of 3 you need 2 questions.

The fraction becomes real only when many choices are named together. Five separate three-way choices have \(3^5 = 243\) combinations, and \(243 \le 256 = 2^8\). So 8 questions settle all five at once: 1.600 questions per choice. With 1,000 choices named together, the cost per choice drops to 1.585 — the logarithm itself.

The same holds for tokens. Naming 1,000 GPT-2 tokens together takes 15,618 bits; naming them one at a time takes 16,000 bits. So \(\log_2 N\) is the average cost per item over long sequences, not the cost of any single item. Chapter 22 shows a practical method that achieves it (arithmetic coding).

Second, the game assumes every number is equally likely. If I tend to pick 7, you should ask "is it 7?" first. Then likely answers cost fewer questions and unlikely ones cost more. The right measure of the cost of one outcome is its surprisal, defined below: an outcome of probability p costs \(\log_2(1/p)\) bits.

Precise definition

Everything in this section is MY EXPLANATION unless tagged.

Powers

Take a number b and a whole number n ≥ 1. The power \(b^n\) means b multiplied by itself n times. Here b is the base and n is the exponent. Example: \(2^3 = 2 \times 2 \times 2 = 8\).

Two rules follow from counting factors:

\[ b^{m}\, b^{n} = b^{m+n}, \qquad \left(b^{m}\right)^{n} = b^{mn}. \]

The first rule says: m factors of b followed by n more factors make m + n factors. The second says: n groups of m factors make mn factors.

We extend exponents beyond positive whole numbers so that the first rule keeps working. Setting \(b^0 = 1\) and \(b^{-n} = 1/b^n\) (for b ≠ 0) does it. For example, \(b^n\, b^{-n} = b^{0} = 1\).

For b > 0, fractional exponents also make sense. For example \(b^{1/2} = \sqrt b\), because \(b^{1/2}\, b^{1/2} = b^{1}\). In fact, for b > 0 the power \(b^x\) is defined for every real number x (see the deeper block below).

The number e and the exponential function

One base is special. It is the number

\[ e = 2.718281828\ldots \]

The function that sends x to \(e^x\) is called the exponential function. It is also written \(\exp(x)\).

What makes e special is how fast \(e^x\) grows. At every point, the slope of the graph of \(e^x\) equals its height. In calculus notation, \(\frac{d}{dx} e^x = e^x\). For any other base b, the slope of \(b^x\) is a constant times \(b^x\), and that constant is not 1. The number e is the one base for which the constant is exactly 1.

This is why e shows up whenever something changes in proportion to its own size. It is also why e shows up in the probability bounds of Chapter 9.

Three facts are used constantly. \(e^x\) is positive for every x. It increases as x increases. It takes every positive value exactly once.

Going deeper: building e^x, e, ln and real powers from scratch

MY EXPLANATION This block makes "the slope of \(e^x\) equals \(e^x\)" precise. It then shows that every fact we use about \(e^x\) and ln follows from it. We assume standard calculus: derivatives, the product and chain rules, the mean value theorem and the intermediate value theorem. We also use, without re-proving it, the theorem that a power series may be differentiated term by term inside its interval of convergence.

Step 1 — definition. For every real x define

\[ \exp(x) = \sum_{k=0}^{\infty} \frac{x^k}{k!} = 1 + x + \frac{x^2}{2} + \frac{x^3}{6} + \cdots \]

The series converges for every x. The ratio of term k + 1 to term k is \(|x|/(k+1)\), which tends to 0 (ratio test).

Step 2 — it is its own derivative. Differentiating term by term, \(x^k/k!\) becomes \(k x^{k-1}/k! = x^{k-1}/(k-1)!\), which is the previous term. So the differentiated series is the same series: \(\exp'(x) = \exp(x)\). Also \(\exp(0) = 1\).

Step 3 — a product that stays 1. Let \(f(a) = \exp(a)\exp(-a)\). By the product and chain rules,

\[ f'(a) = \exp(a)\exp(-a) - \exp(a)\exp(-a) = 0 . \]

A function whose derivative is zero everywhere is constant (mean value theorem). So \(f(a) = f(0) = 1\), that is, \(\exp(a)\exp(-a) = 1\). In particular \(\exp\) is never 0.

Step 4 — addition law. Fix b and let \(g(a) = \exp(a+b)\exp(-a)\). Then \(g'(a) = \exp(a+b)\exp(-a) - \exp(a+b)\exp(-a) = 0\), so \(g(a) = g(0) = \exp(b)\). Multiply both sides by \(\exp(a)\) and use Step 3:

\[ \exp(a+b) = \exp(a)\exp(b). \]

Step 5 — positive, increasing, onto all positive numbers. \(\exp\) is continuous, never 0, and \(\exp(0) = 1 > 0\). If it were negative somewhere, the intermediate value theorem would force a zero in between. So \(\exp(x) > 0\) for all x. Then \(\exp'(x) = \exp(x) > 0\), so \(\exp\) is strictly increasing. For x ≥ 0 every term of the series is ≥ 0, so \(\exp(x) \ge 1 + x\), which grows without bound. And \(\exp(-x) = 1/\exp(x)\) tends to 0 as x grows. By the intermediate value theorem, \(\exp\) takes every value in \((0,\infty)\). It takes each value only once, because it is strictly increasing.

Step 6 — e and ln. Define \(e = \exp(1) = 1 + 1 + \tfrac{1}{2} + \tfrac{1}{6} + \tfrac{1}{24} + \cdots\). The script prints \(e = 2.718281828\). By Step 4, \(\exp(n) = \exp(1)^n = e^n\) for whole n, and by Step 3, \(\exp(-n) = 1/e^n\). So writing \(e^x\) for \(\exp(x)\) agrees with ordinary powers. Because \(\exp\) is strictly increasing and onto \((0,\infty)\), it has an inverse function. For y > 0, \(\ln y\) is the unique x with \(e^x = y\).

Step 7 — powers with any real exponent. For b > 0 and real x define \(b^x = e^{x\ln b}\). For a whole number n, Step 4 gives \(e^{n\ln b} = \left(e^{\ln b}\right)^n = b^n\), so this agrees with repeated multiplication. The power laws follow from Step 4:

\[ b^{x+y} = e^{(x+y)\ln b} = e^{x\ln b}\, e^{y\ln b} = b^x\, b^y . \]

By the definition, \(e^{x\ln b} = b^x\), so \(\ln(b^x) = x\ln b\). Hence \((b^x)^y = e^{y\ln(b^x)} = e^{xy\ln b} = b^{xy}\).

Step 8 — why e is called natural. By the chain rule,

\[ \frac{d}{dx}\, b^x = \frac{d}{dx}\, e^{x\ln b} = (\ln b)\, b^x . \]

The growth rate is the current value times the factor \(\ln b\). That factor equals 1 exactly when b = e. For b = 2 it is \(\ln 2 = 0.693147\).

Step 9 — the slope of ln. Differentiate the identity \(e^{\ln x} = x\) with the chain rule: \(e^{\ln x}\cdot(\ln x)' = 1\), so \((\ln x)' = 1/x\) for x > 0. We use this in the proof of \(\ln x \le x - 1\).

Logarithms

Definition. Let the base b satisfy b > 0 and b ≠ 1, and let y > 0. The logarithm of y to base b, written \(\log_b y\), is the exponent you must put on b to get y:

\[ \log_b y = x \quad\iff\quad b^{x} = y . \]

Examples (all printed by the script):

• \(\log_2 8 = 3\), because \(2^3 = 8\).
• \(\log_2 1024 = 10\).
• \(\log_2 1 = 0\), because \(2^0 = 1\).
• \(\log_2 (1/2) = -1\), because \(2^{-1} = 1/2\).
• \(\log_{10} 1000 = 3\).
• \(\log_2 3 = 1.585\), because \(2^{1.585}\) is about 3.

A logarithm undoes a power, and a power undoes a logarithm: \(\log_b(b^x) = x\) and \(b^{\log_b y} = y\).

The logarithm of zero or of a negative number is not defined. The reason is that \(b^x\) is always positive. As y shrinks towards 0, \(\log_b y\) falls without limit (for b > 1). For example, \(\log_2\) of 1/2, 1/4, 1/8, … is −1, −2, −3, ….

Two bases matter in this explainer:

• The natural logarithm \(\ln y = \log_e y\). It is "natural" because its base is e.
• The base-2 logarithm \(\log_2 y\). It counts bits.

Notation rule. This explainer always writes \(\ln\) or \(\log_2\), never a bare "log". When the paper writes "log", we say which one it must mean and why.

The log rules

Take a base b (b > 0, b ≠ 1), positive numbers y and z, and any real number r.

Rule	Formula	Example (base 2)
Product	\(\log_b(yz) = \log_b y + \log_b z\)	\(\log_2(8 \times 4) = 3 + 2 = 5\), and \(8 \times 4 = 32 = 2^5\)
Quotient	\(\log_b(y/z) = \log_b y - \log_b z\)	\(\log_2(1/8) = 0 - 3 = -3\)
Power	\(\log_b(y^r) = r\,\log_b y\)	\(\log_2(8^{10}) = 10 \times 3 = 30\)
Change of base	\(\log_b y = \ln y / \ln b\)	\(\log_2 y = \ln y / \ln 2\)

One idea drives all four. Multiplying powers adds their exponents, and a logarithm is an exponent. So logarithms turn multiplication into addition.

That is why probabilities, which multiply, become sums of logarithms in Chapters 4 and 6. The script checked all four rules on 1,000 random pairs of numbers; the largest error was \(3.6\times10^{-15}\), which is the computer's rounding noise.

Going deeper: proofs of the four log rules

MY EXPLANATION Fix a base b > 0 with b ≠ 1, numbers y, z > 0 and a real number r. Write \(u = \log_b y\) and \(v = \log_b z\). By the definition of the logarithm, \(b^u = y\) and \(b^v = z\). Each proof rewrites a product, quotient or power of y and z as a single power of b, and then reads off the exponent.

Product rule. By the power law, \(yz = b^u\, b^v = b^{u+v}\). By definition, \(\log_b(yz)\) is the exponent that turns b into yz. So \(\log_b(yz) = u + v = \log_b y + \log_b z\).

Quotient rule. By the power law, \(b^{u-v}\, b^{v} = b^{u} = y\), so \(b^{u-v} = y/z\). Hence \(\log_b(y/z) = u - v\). With y = 1 (so u = 0) this gives \(\log_b(1/z) = -\log_b z\). The logarithm of a reciprocal is minus the logarithm. That is why \(-\log_2 p = \log_2(1/p)\).

Power rule. By the power law for real exponents (Step 7 of the previous block), \(y^r = (b^u)^r = b^{ur}\). So \(\log_b(y^r) = ru = r\log_b y\).

Change of base. Start from \(y = b^u\) and take ln of both sides. The power rule with base e gives \(\ln y = \ln(b^u) = u\ln b\). Since b ≠ 1 we have \(\ln b \ne 0\) (because \(\ln b = 0\) would mean \(b = e^0 = 1\)). So we may divide:

\[ \log_b y = u = \frac{\ln y}{\ln b}. \]

Consequences used later.

• \(\log_2 y = \ln y/\ln 2\) and \(\ln y = (\ln 2)\log_2 y\). This is the bits–nats conversion.
• For bases a, b (both positive and not 1), \(\log_b a \cdot \log_a b = \frac{\ln a}{\ln b}\cdot\frac{\ln b}{\ln a} = 1\).
• For b > 1, \(\log_b\) is strictly increasing. Reason: ln is the inverse of the strictly increasing function exp, so it is strictly increasing too, and dividing by the positive constant \(\ln b\) keeps the order. Consequence: a larger probability always has a smaller surprisal (defined below).

Bits

A bit (short for binary digit) is a symbol that is either 0 or 1. Computer memory stores everything as strings of bits.

A bit is also a unit of information. One bit is the information in the answer to one yes/no question whose two answers are equally likely, such as a fair coin flip.

How many different things can n bits name? One bit gives 2 strings: 0 and 1. Two bits give 4: 00, 01, 10, 11. Each extra bit doubles the count. So n bits can name \(2^n\) things.

Bits to name one of N things. Suppose each of N items gets its own string of exactly n bits. This is called a fixed-length code (Chapter 12 studies codes in general). We need at least N different strings, so \(2^n \ge N\). The smallest such n is

\[ n = \lceil \log_2 N \rceil , \]

where the ceiling \(\lceil x \rceil\) means "x rounded up to the nearest whole number". The same number is the worst-case count of questions in the twenty-questions game.

Example. For GPT-2's 50,257 tokens, \(2^{15} = 32{,}768\) is too few and \(2^{16} = 65{,}536\) is enough. So a token needs \(\lceil 15.617 \rceil = 16\) bits.

[SOURCE: nanoGPT prepare.py] This is exactly how nanoGPT stores the training text: every token id takes one unsigned 16-bit integer. A code comment notes that this works because the largest id, 50,256, is below \(2^{16}\).

Keep two numbers apart. 16 bits is the storage per token in a fixed-length code. \(\log_2 N = 15.617\) bits is the information in one token drawn uniformly at random. The gap, 0.383 bits per token, is what you lose by naming tokens one at a time.

Going deeper: exactly how many yes/no questions are needed

MY EXPLANATION Claim. To identify one of N ≥ 1 items with yes/no questions, every strategy needs at least \(\lceil\log_2 N\rceil\) questions for some item. Repeated halving never needs more. The same number of bits is necessary and sufficient for a fixed-length code.

A strategy is a tree. Draw the first question at the top. Each answer leads either to a final verdict ("it is item i") or to the next question. Every item must end at its own verdict, called its leaf. Two items cannot share a leaf, because then the strategy could not tell them apart. If the strategy never asks more than q questions, the tree has depth at most q.

A tree of depth at most q has at most \(2^q\) leaves. We use induction on q. For q = 0 there are no questions and exactly one verdict, and \(1 = 2^0\). For q ≥ 1, the first question splits the tree into a "yes" part and a "no" part. Each part has depth at most q − 1, so each has at most \(2^{q-1}\) leaves. Together they have at most \(2^q\).

Lower bound. N items need N different leaves, so \(N \le 2^q\). Take \(\log_2\) of both sides; this keeps the order because \(\log_2\) is increasing. We get \(q \ge \log_2 N\). Since q is a whole number, \(q \ge \lceil\log_2 N\rceil\).

Upper bound (halving). Let \(q = \lceil\log_2 N\rceil\), so that \(N \le 2^q\). Suppose S candidates are left and \(S \le 2^k\) for some k ≥ 1. Ask "is it among the first \(\lceil S/2\rceil\) candidates?". Either way, at most \(\lceil S/2\rceil\) candidates remain. Since \(S/2 \le 2^{k-1}\) and \(2^{k-1}\) is a whole number, \(\lceil S/2\rceil \le 2^{k-1}\). Start from \(S = N \le 2^q\) and repeat q times. At most \(2^0 = 1\) candidate is left, so the item is identified.

Fixed-length codes. There are exactly \(2^n\) bit strings of length n, since each of the n positions is 0 or 1 independently. Giving N items different strings requires \(2^n \ge N\), that is, \(n \ge \lceil\log_2 N\rceil\). And \(n = \lceil\log_2 N\rceil\) suffices: number the items 0, 1, …, N − 1 and write each number in binary with n digits. This works because \(N - 1 < 2^n\). For GPT-2, \(2^{15} = 32{,}768 < 50{,}257 \le 2^{16} = 65{,}536\), so n = 16.

Nats

A nat (short for natural unit) measures information with ln instead of \(\log_2\). If a quantity is computed as ln(something), it is in nats. If it is computed as \(\log_2\) of the same thing, it is in bits.

By the change-of-base rule, \(\ln y = (\ln 2)\log_2 y\) for every y > 0. So one and the same amount of information is written as follows in the two units:

\[ \text{amount in nats} = \text{amount in bits} \times \ln 2, \qquad \text{amount in bits} = \frac{\text{amount in nats}}{\ln 2}. \]

In numbers: 1 bit = \(\ln 2\) = 0.693147 nats, and 1 nat = \(1/\ln 2\) = 1.442695 bits.

Nats and bits are like centimetres and inches: the same quantity on two different rulers. Three habits keep units straight:

• Add bits to bits and nats to nats. Never add one to the other.
• Before you put a number into a formula, check which unit the formula expects.
• To convert, multiply or divide by \(\ln 2\). Nothing else is needed.

Surprisal

Let an event have probability p, with 0 < p ≤ 1 (Chapter 1 defines probability). Its surprisal, also called its information content, is

\[ \log_2\frac{1}{p} = -\log_2 p \ \text{ bits} \qquad\text{or equivalently}\qquad \ln\frac{1}{p} = -\ln p \ \text{ nats}. \]

The script prints these values:

Probability p	Surprisal (bits)	Surprisal (nats)
1	0.000	0.000
0.9	0.152	0.105
1/2	1.000	0.693
0.01	6.644	4.605
1/50,257	15.617	10.825

Read the table from top to bottom:

• A certain event (p = 1) carries no surprise: 0 bits.
• One outcome of a fair coin (p = 1/2) carries 1 bit. This matches the definition of a bit.
• One of N equally likely outcomes has p = 1/N and carries \(\log_2 N\) bits. This matches the twenty-questions answer.
• The rarer the event, the larger the surprisal. As p shrinks towards 0, the surprisal grows without limit. An event with p = 0 has no finite surprisal at all.

For independent events, probabilities multiply (Chapter 1). By the product rule, their surprisals therefore add. This is why information can be totalled like a length.

Why this matters for the paper: suppose a language model gives probability p to the token that actually came next. Its loss on that token is the surprisal \(-\log_2 p\) bits. Chapter 6 averages these losses to get BPD. A model that was 90 % sure of the right token pays 0.152 bits. A model that gave the right token only 1 % pays 6.644 bits.

Bytes and kilobytes

A byte is 8 bits.

A kilobyte (KB) has two conventions:

• Decimal: 1 KB = 1,000 bytes = 8,000 bits. Here "kilo" means 1,000, as in kilometre.
• Binary: 1 KB = 1,024 bytes = 8,192 bits, because \(1{,}024 = 2^{10}\). The standard name for this unit is kibibyte (KiB).

The two differ by a factor of 1.024, that is, by 2.4 %.

SOURCE: Lotfi et al. 2022, App. A, Table 3 caption The predecessor paper by the same group fixes the convention: 1 KB = 8192 bits.

PAPER Fig. 2, p. 5; Fig. 3, p. 8 The 2024 paper reports compressed model sizes in KB but never defines KB.

MY EXPLANATION This explainer follows Lotfi et al. (2022): 1 KB = 8192 bits.

Paper erratum E35: the unit KB is never defined

PAPER Fig. 2, p. 5; Fig. 3, p. 8 Figure 2 (left) plots "Compressed Size (KB)" and Figure 3 colours its points by "Compressed Model Size (KB)". The paper does not say whether 1 KB is 1,000 or 1,024 bytes.

MY EXPLANATION The two conventions differ by 2.4 %. No bound changes, because the bound uses C(h) in bits, not in KB. But a reader who converts a plotted KB value back into bits can be off by 2.4 %. The predecessor paper (Lotfi et al. 2022, App. A) states 1 KB = 8192 bits, and we follow it.

[SOURCE: nanoGPT prepare.py] Both conventions are in real use, sometimes side by side. nanoGPT stores the 9,035,582,198 OpenWebText training tokens at 2 bytes each. That is \(18.07\times10^{9}\) bytes, or \(16.83\times2^{30}\) bytes. The file's own comment calls it "~17GB", which matches the binary convention.

The inequality ln x ≤ x − 1

For every x > 0,

\[ \ln x \le x - 1 , \]

with equality only at x = 1. Its twin says that for every real number x,

\[ 1 + x \le e^{x}, \]

with equality only at x = 0. The two are the same fact in disguise: put \(x = e^t\) into the first and you get \(t \le e^t - 1\), which is the second.

Here is the picture. The straight line x − 1 touches the curve ln x at the point (1, 0), with the same slope there. The curve ln x bends downward everywhere, so it can never climb back above that line. The script checked both inequalities on more than 150,000 points each. The smallest gap was 0, reached at x = 1 (and at x = 0 for the twin).

Why we need it: this inequality is the key step in Chapter 22's proof that no code can beat a certain best average length (Gibbs' inequality). In the Going-deeper section below we also use it to prove that no yes/no strategy beats \(\log_2 N\) questions on average.

Going deeper: proof of ln x ≤ x − 1 and 1 + x ≤ e^x

MY EXPLANATION We use three facts from the block on e: \(\frac{d}{dx}e^x = e^x\), \(e^x\) is strictly increasing, and \(e^0 = 1\). We also use the mean value theorem: for a differentiable g and numbers a ≠ x, there is a ξ strictly between a and x with \(g(x) - g(a) = g'(\xi)(x - a)\).

Claim A. For every real x, \(e^x \ge 1 + x\), with equality only at x = 0.

Proof. Let \(g(x) = e^x - 1 - x\). Then \(g(0) = 0\) and \(g'(x) = e^x - 1\). Because \(e^x\) is strictly increasing and \(e^0 = 1\), we have \(g'(x) < 0\) for x < 0 and \(g'(x) > 0\) for x > 0.

• Take x > 0. The mean value theorem gives \(g(x) - g(0) = g'(\xi)\,x\) with \(0 < \xi < x\). Both factors are positive, so \(g(x) > 0\).
• Take x < 0. Again \(g(x) - g(0) = g'(\xi)\,x\), now with \(x < \xi < 0\). Both factors are negative, so their product is positive and \(g(x) > 0\).

So \(g(x) > 0\) for every x ≠ 0, and \(g(0) = 0\). ∎

Claim B. For every x > 0, \(\ln x \le x - 1\), with equality only at x = 1.

Proof. Let \(t = \ln x\). It exists because x > 0, and \(e^t = x\). Claim A at the point t gives \(x = e^t \ge 1 + t = 1 + \ln x\), that is, \(\ln x \le x - 1\). Equality needs t = 0, that is, \(x = e^0 = 1\). ∎

Conversely, Claim B at the point \(x = e^t\) gives back Claim A. So the two claims are one fact.

The tangent-line picture. The slope of ln at x = 1 is \(1/1 = 1\) (Step 9 of the block on e), and \(\ln 1 = 0\). So \(y = x - 1\) is the tangent line at (1, 0). The second derivative of \(\ln x\) is \(-1/x^2 < 0\), so the curve bends downward everywhere (it is concave). A curve that bends downward everywhere lies below each of its tangent lines. The proof above is the rigorous version of this picture.

Variants used later.

• Apply Claim B to 1/x: \(-\ln x \le 1/x - 1\), so \(\ln x \ge 1 - 1/x\). Together: \(1 - \frac1x \le \ln x \le x - 1\) for x > 0.
• In bits: \(\log_2 x = \frac{\ln x}{\ln 2} \le \frac{x-1}{\ln 2} = 1.442695\,(x-1)\).
• Claim A at the point −x gives \(1 - x \le e^{-x}\). For \(0 \le x \le 1\) both sides are ≥ 0, so raising both to a whole power n keeps the order: \((1-x)^n \le e^{-nx}\).

Units in the paper's formulas

MY EXPLANATION Here is a preview of Chapter 9. That chapter proves a guarantee whose failure probability has the form \(e^{-x}\), where x grows with the amount of training data. Suppose we allow the guarantee to fail with probability at most δ, a small number such as 0.05 chosen in advance (Chapter 11). Then we must solve \(e^{-x} = \delta\) for x.

Taking ln of both sides gives \(-x = \ln\delta\), so \(x = \ln(1/\delta)\). The base e in the guarantee forces ln in the answer. So the logarithms inside Eq. (1) are natural logarithms, and the quantity under its square root is measured in nats.

SOURCE: authors' code; Lotfi et al. 2022 — the paper does not state δ, erratum E31 The authors use δ = 0.05.

MY EXPLANATION With δ = 0.05, \(\ln(1/\delta) = 2.996\) nats. The same amount of information is 4.322 bits. But 4.322 does not solve \(e^{-x} = 0.05\); only the value in nats does.

PAPER §4.1, p. 4 The paper bounds the first logarithm in Eq. (1) by a chain of two inequalities: "log 1/P(h) ≤ K(h|A) log 2 ≤ C(h) log 2 + 2 log C(h)". Here P(h) is the probability the bound gives to the model h before seeing any data (the prior; Chapter 11). K(h|A) is the length in bits of the shortest program that outputs h (Chapter 13). C(h) is the number of bits of the compressed model (Chapter 14).

MY EXPLANATION Read every "log" as ln. By the change-of-base rule, \(2\ln C = 2(\ln 2)\log_2 C\). So

\[ C\ln 2 + 2\ln C = (\ln 2)\,\bigl(C + 2\log_2 C\bigr). \]

The bracket is a length in bits: the compressed model, plus a header of about \(2\log_2 C\) bits that announces how long the model is (Chapter 12 explains why such a header is needed). Multiplying by \(\ln 2\) converts this length to nats, which is what Eq. (1) needs. Everything fits.

Paper erratum E02: the base of 'log' is never stated

PAPER §4.1, p. 4; Eq. (1), p. 4; App. C, Algorithm 1, p. 15 Eq. (1) and the display in §4.1 write "log" with no base. Algorithm 1 line 6 sets "log 1/P(h)" equal to the output of a function whose last line (line 20) returns "message_size + 2 × log(message_size)", where message_size is a number of bits.

MY EXPLANATION Only one reading makes §4.1 and Eq. (1) consistent: every "log" there is ln. Three reasons:

1. Eq. (1) comes from a probability of the form \(e^{-x}\), and undoing e requires ln (see above).
2. With log = ln, \(C\ln 2 + 2\ln C = (C + 2\log_2 C)\ln 2\): a length in bits, converted to nats.
3. If "log" meant \(\log_2\), the factor "log 2" would equal 1, and there would be no reason to write it.

Algorithm 1 is different. Its line 20 works in bits, so its "log" must be \(\log_2\), and line 6 then calls a number of bits "log 1/P(h)".

[SOURCE: authors' code, sublora_bounds_bound_utils.py] The authors' code computes this length as message_len + 2 * np.log2(message_len), confirming \(\log_2\) for Algorithm 1.

MY EXPLANATION The corrected §4.1 display reads:

\[ \ln\frac{1}{P(h)} \le K(h \mid A)\ln 2 \le C(h)\ln 2 + 2\ln C(h) = \bigl(C(h) + 2\log_2 C(h)\bigr)\ln 2 . \]

(The middle step has separate issues, errata E01 and E12, discussed in Chapters 13 and 14.) If a number in bits is used where nats are needed, the bound becomes larger: looser, but never invalid (proof in "Going deeper" below). No reported number in the paper is made wrong by this. Chapter 14 measures how much looser the bound gets.

Worked example with real numbers

Everything in this section is MY EXPLANATION unless tagged. All numbers are printed by ch03_bits_nats.py (output at the end of the chapter).

Step 1 — random guessing over GPT-2's vocabulary. [SOURCE: nanoGPT prepare.py; authors' code] V = 50,257 tokens. A model that guesses uniformly at random gives every token probability 1/V. Its surprisal on every token is therefore \(\log_2 V = 15.617\) bits, so its average cost per token is also 15.617 bits.

PAPER Table 1, p. 6 The paper's "Random Guess" BPD is 15.62.

The difference is −0.003 bits, which is rounding. Rounding cuts both ways, though. Every V from 50,187 to 50,535 would also print as 15.62, so the table agrees with V = 50,257 but cannot pin it down.

Paper erratum E36: the vocabulary size V is never given as a number

PAPER §6.2, p. 7; Table 1, p. 6; App. A.2, p. 13 The paper writes \(\log_2 V\) and \(1 - k/V\) for the random-guess baselines and uses V in Theorem A.2, but it never prints the value of V.

[SOURCE: nanoGPT prepare.py; authors' code default vocab_size = 50257] GPT-2's tokenizer has 50,257 tokens.

MY EXPLANATION \(\log_2 50{,}257 = 15.617\) rounds to Table 1's 15.62, so no reported number is affected. But the reader must look the value up elsewhere, and the rounded table entry alone fits any V from 50,187 to 50,535.

Step 2 — the same amount in nats. \(\ln 50{,}257 = 10.825\) nats. Check by conversion: \(15.617 \times 0.693147 = 10.825\). ✓

Step 3 — a better guess. A model that gives the right token probability 0.01 pays \(-\log_2 0.01 = 6.644\) bits, which is \(-\ln 0.01 = 4.605\) nats. Even this model, only 1 % sure of the right answer, pays far less than the 15.617 bits of random guessing on that token.

Step 4 — a 20 KB model. With 8192 bits per KB, 20 KB is 163,840 bits, which is 113,565.2 nats. With 8000 bits per KB, 20 KB is 160,000 bits, which is 110,903.5 nats. The choice of convention changes the size by 2.4 %.

Step 5 — the paper's complexity expression. Take C = 163,840 bits, the 20 KB model.

• The length header: \(2\log_2 C = 34.644\) bits.
• In nats: \(2\log_2 C \times \ln 2 = 24.013\) nats, and directly \(2\ln C = 24.013\) nats. They agree, as the change-of-base rule promises.
• Every log read as ln: \(C\ln 2 + 2\ln C = 113{,}589.2\) nats.
• Bits first, then converted: \((C + 2\log_2 C)\times\ln 2 = 113{,}589.2\) nats. Identical.
• Every log read as \(\log_2\): \(C + 2\log_2 C = 163{,}874.6\). This is a number of bits. Put into Eq. (1) as if it were nats, it is 1.442695 times too large, so the bound would be looser but still valid.
• Mixed reading (first ln, then \(\log_2\)): 113,599.9. This adds nats to bits, so it has no meaningful unit.

The script also checked \(2\log_2(C)\ln 2 = 2\ln C\) for seven values of C. The largest relative error was \(1.9\times10^{-16}\), which is rounding noise.

Step 6 — the confidence term. With δ = 0.05 SOURCE: authors' code, \(\ln(1/\delta) = 2.996\) nats, or 4.322 bits.

Summary of the example:

Quantity	Bits	Nats
One token, uniform guess over V = 50,257 [SOURCE]	15.617	10.825
One token predicted with p = 0.01	6.644	4.605
A 20 KB model, 8192 bits per KB	163,840	113,565.2
That model's complexity, \(C + 2\log_2 C\)	163,874.6	113,589.2
\(\ln(1/\delta)\) with δ = 0.05 [SOURCE]	4.322	2.996

Going deeper

Everything in this section is MY EXPLANATION.

The proofs for this chapter sit next to the text they support:

• "Building e^x, e, ln and real powers from scratch" — under The number e and the exponential function.
• "Proofs of the four log rules" — under The log rules.
• "Exactly how many yes/no questions are needed" — under Bits.
• "Proof of ln x ≤ x − 1 and 1 + x ≤ e^x" — under The inequality ln x ≤ x − 1.

Two more blocks follow here, because they combine several of those results.

Going deeper: no strategy beats log2 N questions on average

MY EXPLANATION Claim. Let N items be equally likely. Let a yes/no strategy identify item i after \(q_i\) questions. Then the average number of questions satisfies

\[ \bar q = \frac1N\sum_{i=1}^{N} q_i \;\ge\; \log_2 N , \]

with equality only if every \(q_i = \log_2 N\), which is possible only when N is a power of 2. This is the precise sense in which "naming one of N things costs \(\log_2 N\) bits": no strategy does better on average.

Step 1 — weights. Use the tree picture from the block "Exactly how many yes/no questions are needed". Give the top of the tree weight 1. Let every question pass half of its weight to each of its two answers. Then the leaf of item i, reached after \(q_i\) questions, receives weight \(2^{-q_i}\).

Below any node of weight w, the leaves carry total weight at most w. This holds for a leaf. For a question node, each of its two branches carries at most w/2 (by induction from the bottom of the tree), so together at most w. Applied to the top node:

\[ \sum_{i=1}^{N} 2^{-q_i} \le 1 . \]

Chapter 12 proves this in general under the name Kraft inequality.

Step 2 — rewrite the gap. Since \(q_i = -\log_2 2^{-q_i}\), the product rule gives \(q_i - \log_2 N = -\log_2\bigl(N\,2^{-q_i}\bigr)\). Average over i:

\[ \bar q - \log_2 N = -\frac1N\sum_{i=1}^{N} \log_2\bigl(N\,2^{-q_i}\bigr). \]

Step 3 — use ln y ≤ y − 1. In bits the inequality reads \(\log_2 y \le (y-1)/\ln 2\), so \(-\log_2 y \ge (1-y)/\ln 2\). Apply it with \(y_i = N\,2^{-q_i}\):

\[ \begin{aligned} \bar q - \log_2 N &\ge \frac{1}{N\ln 2}\sum_{i=1}^{N}\bigl(1 - N\,2^{-q_i}\bigr) \\ &= \frac{1}{N\ln 2}\Bigl(N - N\sum_{i=1}^{N} 2^{-q_i}\Bigr) \\ &= \frac{1}{\ln 2}\Bigl(1 - \sum_{i=1}^{N} 2^{-q_i}\Bigr) \;\ge\; 0 , \end{aligned} \]

where the last step uses Step 1. ∎

Equality. Both inequalities must be tight. Equality in \(\ln y \le y - 1\) forces every \(y_i = 1\), that is, \(2^{q_i} = N\) for every i.

The numbers. For N = 50,257, halving needs 15.696 questions on average, against the floor \(\log_2 N = 15.617\). Halving puts every item at depth 15 or 16 (the script counts them), and it never wastes a branch, so the weights add up to exactly 1. Let a items sit at depth 15 and c at depth 16. Then a + c = N and \(a/2^{15} + c/2^{16} = 1\), that is, \(2a + c = 2^{16}\). Subtracting the first equation from the second gives \(a = 2^{16} - N = 65{,}536 - 50{,}257 = 15{,}279\), and then \(c = N - a = 34{,}978\). These are exactly the counts the script found.

Chapter 22 extends this argument to items with unequal probabilities.

Going deeper: where the ln in Eq. (1) comes from, and why bits in place of nats is safe

MY EXPLANATION This previews Chapters 9–11 only as far as needed to see where the logarithms come from. Symbols: h is one fixed model. m is the number of training examples, drawn at random. The loss of h on any example lies in an interval of width Δ. \(R(h)\) is the expected risk of h and \(\hat R(h)\) its empirical risk (Chapter 2). t > 0 is a margin.

The exponential tail. Chapter 9 proves Hoeffding's inequality:

\[ \Pr\bigl[R(h) - \hat R(h) \ge t\bigr] \le e^{-2mt^2/\Delta^2}. \]

The probability is over the random draw of the m training examples; h is fixed.

The budget. Chapter 11 gives each model h its own allowed failure probability \(P(h)\,\delta\), where P(h) is the prior and δ the overall failure level. We need the t at which the right-hand side equals \(P(h)\,\delta\).

Solving. Take ln of both sides of \(e^{-2mt^2/\Delta^2} = P(h)\,\delta\), using \(\ln(e^a) = a\):

\[ \begin{aligned} -\frac{2mt^2}{\Delta^2} &= \ln\bigl(P(h)\,\delta\bigr), \\ \frac{2mt^2}{\Delta^2} &= \ln\frac{1}{P(h)\,\delta} \qquad \text{by the quotient rule,} \\ &= \ln\frac{1}{P(h)} + \ln\frac{1}{\delta} \qquad \text{by the product rule,} \\ t &= \Delta\sqrt{\frac{\ln\frac{1}{P(h)} + \ln\frac{1}{\delta}}{2m}} . \end{aligned} \]

This t is exactly the extra term of Eq. (1). Both logarithms in it are ln, because the e in Hoeffding's bound put them there. The product rule is why the two terms appear as a sum.

Units. \(\ln(1/P(h))\) and \(\ln(1/\delta)\) are pure numbers; calling them "nats" records that base e was used. Dividing by 2m (a count) and taking the square root leaves a pure number. Multiplying by Δ gives t the unit of the loss: bits per token for BPD, or a fraction for an error rate.

Bits in place of nats is conservative. Suppose someone writes \(\log_2(1/P(h))\) where \(\ln(1/P(h))\) belongs. Because \(P(h) \le 1\), we have \(\ln(1/P(h)) \ge 0\), and so

\[ \log_2\frac{1}{P(h)} = \frac{\ln\bigl(1/P(h)\bigr)}{\ln 2} = 1.442695 \times \ln\frac{1}{P(h)} \;\ge\; \ln\frac{1}{P(h)} . \]

The square root is increasing, so the resulting margin t′ is at least t. Whenever \(R(h) \le \hat R(h) + t\) holds, \(R(h) \le \hat R(h) + t'\) holds too. So the statement keeps its probability guarantee; it only gets weaker. The same argument covers \(\log_2(1/\delta)\) in place of \(\ln(1/\delta)\). The reverse mistake is not safe: a number in nats used where a formula expects bits is too small by the same factor, and can make a statement false.

Common misconceptions

• Misconception: "log" without a base means base 10. — Actually: it depends on the field and the author. In this paper the logs of Eq. (1) must be ln, while Algorithm 1's must be \(\log_2\) (erratum E02). This explainer always writes ln or \(\log_2\).
• Misconception: bits and nats measure different things. — Actually: they measure the same quantity on two rulers. 1 bit = 0.693147 nats, and 1 nat = 1.442695 bits.
• Misconception: a file of n bits contains n bits of information. — Actually: "bit" is both a unit of storage and a unit of information, and storage can exceed information. A GPT-2 token is stored in 16 bits, but a uniformly random token carries 15.617 bits, and predictable text carries far less. Compression (Chapters 13, 21, 22) closes that gap.
• Misconception: since \(\log_2 3 = 1.585\) is not a whole number, three-way choices always cost 2 bits each. — Actually: one choice on its own costs 2 bits, but in blocks the cost per choice approaches 1.585 bits. Five choices fit in 8 bits (1.600 each), and 1,000 GPT-2 tokens fit in 15,618 bits instead of 16,000.
• Misconception: 1 KB is always 1,000 bytes (or always 1,024). — Actually: both conventions are in use, and they differ by 2.4 %. Lotfi et al. (2022) use 8192 bits; the 2024 paper does not say.
• Misconception: an impossible event merely has a very large surprisal. — Actually: \(-\log_2 0\) is not a number at all; the surprisal grows without limit as p shrinks to 0. A model that gives the true next token probability 0 has infinite loss. This is why the paper needs prediction smoothing — mixing a little equal probability for every token into the model's predictions (Chapter 16).
• Misconception: putting bits where the bound needs nats makes the bound invalid. — Actually: the number in bits is larger, so the bound only gets looser (see "Going deeper"). The reverse mistake would be unsafe.

Self-test

Q1. A model gives probability 1/8 to the token that actually came next. What is its surprisal in bits and in nats? How does it compare with uniform random guessing over GPT-2's 50,257 tokens?

Answer

\(-\log_2(1/8) = \log_2 8 = 3\) bits, because \(2^3 = 8\). In nats: \(3 \times \ln 2 = 2.079\) nats (the script's table prints 3.000 bits and 2.079 nats). Uniform guessing costs \(\log_2 50{,}257 = 15.617\) bits per token, so this prediction is far cheaper.

Q2. nanoGPT stores each GPT-2 token id in a fixed-length code. How many bits does it use, why not one fewer, and how much larger is that than the information in a uniformly random token?

Answer

It uses \(\lceil\log_2 50{,}257\rceil = \lceil 15.617\rceil = 16\) bits (2 bytes). One fewer is not enough: \(2^{15} = 32{,}768\) strings cannot give 50,257 tokens different names, while \(2^{16} = 65{,}536\) can. A uniformly random token carries \(\log_2 50{,}257 = 15.617\) bits, so the fixed-length code spends 0.383 extra bits per token, which is 2.4 % of 16. Naming tokens in long blocks removes almost all of that overhead (1,000 tokens: 15,618 bits instead of 16,000).

Q3. A colleague computes the extra term of Eq. (1) with \(\log_2(1/P(h))\) — a number of bits — instead of \(\ln(1/P(h))\). Is the resulting bound wrong?

Answer

It is still a valid bound, only looser. Eq. (1) needs nats, because its logarithms come from solving \(e^{-2mt^2/\Delta^2} = P(h)\,\delta\). Since \(P(h) \le 1\), \(\ln(1/P(h)) \ge 0\), and \(\log_2(1/P(h)) = 1.442695 \times \ln(1/P(h))\) is at least as large. A larger number under an increasing square root gives a larger margin. If the true expected risk is below "empirical risk + smaller margin", it is also below "empirical risk + larger margin". So the guarantee still holds with the same probability. The opposite swap — nats where bits are required — would shrink a number that must not be shrunk, and could make the statement false. This is the content of erratum E02's last paragraph.

Code for this chapter

Run it from the project root:

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

Source: ch03_bits_nats.py

"""Chapter 3 - Logarithms, bits and nats.

Reproduces / checks:
  * log2 V = 15.617 bits for the GPT-2 vocabulary V = 50,257 and that it rounds to the
    paper's "Random Guess" BPD of 15.62 (Table 1, p. 6); ln V in nats; 16-bit fixed-length ids.
  * bits <-> nats conversion factors (1 bit = ln 2 nats, 1 nat = 1/ln 2 bits).
  * surprisal -log2 p (bits) and -ln p (nats) for a few probabilities.
  * "twenty questions": binary search over N = 50,257 needs at most ceil(log2 N) = 16
    questions; the average over all targets is printed.
  * fractional bits: naming k items at once costs ceil(k log2 N)/k bits per item -> log2 N.
  * kilobyte conventions (8192 vs 8000 bits) for a 20 KB model, and the nanoGPT train.bin size.
  * the paper's section 4.1 expression C ln 2 + 2 ln C equals (C + 2 log2 C) bits converted
    to nats (erratum E02), and what the other readings of the bare "log" would give.
  * ln(1/delta) for delta = 0.05 (value from the authors' code, not the paper).
  * ln x <= x - 1 and 1 + x <= e^x on a grid (figure ch03_lnx.png) and a surprisal figure.

Units are printed on every line. Output: outputs/ch03_bits_nats.txt.
"""
from __future__ import annotations

import math
import sys
from pathlib import Path

import numpy as np
import matplotlib

matplotlib.use("Agg")
import matplotlib.pyplot as plt

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

OUT_TXT = HERE / "outputs" / "ch03_bits_nats.txt"
FIG_DIR = HERE.parent / "docs" / "assets" / "fig"
FIG_LNX = FIG_DIR / "ch03_lnx.png"
FIG_SUR = FIG_DIR / "ch03_surprisal.png"

lines: list[str] = []


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


def questions_binary_search(target: int, lo: int, hi: int) -> int:
    """Number of yes/no questions 'is it <= mid?' needed to pin down target in [lo, hi]."""
    q = 0
    while lo < hi:
        mid = (lo + hi) // 2
        q += 1
        if target <= mid:
            hi = mid
        else:
            lo = mid + 1
    return q


def main() -> None:
    LN2 = pb.LN2
    V = pb.V_GPT2  # 50,257 [SOURCE: nanoGPT prepare.py / authors' code default vocab_size]

    out("Chapter 3 - logarithms, bits and nats (ch03_bits_nats.py)")
    out("[1] Constants")
    out(f"  e                          = {math.e:.9f}")
    out(f"  ln 2   (nats in one bit)   = {LN2:.6f}")
    out(f"  1/ln 2 (bits in one nat)   = {1 / LN2:.6f}")
    ex = [("log2 8", math.log2(8)), ("log2 1024", math.log2(1024)), ("log2 1", math.log2(1)),
          ("log2(1/2)", math.log2(0.5)), ("log10 1000", math.log10(1000)), ("ln e", math.log(math.e)),
          ("log2 3", math.log2(3))]
    out("  examples: " + ", ".join(f"{k} = {v:.3f}".replace(".000", "") for k, v in ex))

    # ---- 2. GPT-2 vocabulary -------------------------------------------------
    log2V, lnV = math.log2(V), math.log(V)
    paper_rg = 15.62  # [PAPER Table 1, p. 6] Random Guess, Bits per Dimension Bound
    assert abs(pb.random_guess_bpd(V) - log2V) < 1e-12
    assert round(log2V, 2) == paper_rg
    v_lo = math.ceil(2 ** (paper_rg - 0.005))
    v_hi = math.floor(2 ** (paper_rg + 0.005))
    assert round(math.log2(v_lo), 2) == paper_rg and round(math.log2(v_hi), 2) == paper_rg
    assert round(math.log2(v_lo - 1), 2) != paper_rg and round(math.log2(v_hi + 1), 2) != paper_rg
    fixed = math.ceil(log2V)
    out("")
    out(f"[2] GPT-2 vocabulary, V = {V:,} tokens")
    out(f"  log2 V                     = {log2V:.3f} bits  (paper's Random Guess BPD: {paper_rg};"
        f" diff {log2V - paper_rg:+.3f})")
    out(f"  V with log2 V -> {paper_rg}     = {v_lo:,} ... {v_hi:,}  (all print as {paper_rg})")
    assert 2 ** (fixed - 1) < V <= 2 ** fixed
    out(f"  fixed-length id            = ceil(log2 V) = {fixed} bits = {fixed // 8} bytes"
        f"  (2^15 = {2 ** 15:,} < V <= 2^16 = {2 ** 16:,})")
    out(f"  storage overhead           = {fixed} - log2 V = {fixed - log2V:.3f} bits per token"
        f" ({100 * (fixed - log2V) / fixed:.1f} % of {fixed})")
    out(f"  ln V                       = {lnV:.3f} nats;  check: {log2V:.3f} bits x {LN2:.6f}"
        f" = {pb.bits_to_nats(log2V):.3f} nats")
    assert abs(pb.bits_to_nats(log2V) - lnV) < 1e-12

    # ---- 3. Surprisal ----------------------------------------------------------
    out("")
    out("[3] Surprisal of an event with probability p")
    out("  p            -log2 p (bits)   -ln p (nats)")
    for label, p in [("1", 1.0), ("0.9", 0.9), ("1/2", 0.5), ("1/8", 0.125),
                     ("0.01", 0.01), ("1/V", 1 / V)]:
        sb, sn = -math.log2(p) + 0.0, -math.log(p) + 0.0
        assert abs(sb * LN2 - sn) < 1e-12
        out(f"  {label:<10} {sb:>12.3f}   {sn:>12.3f}")

    # ---- 4. Twenty questions --------------------------------------------------
    qs = np.array([questions_binary_search(t, 1, V) for t in range(1, V + 1)])
    n15, n16 = int((qs == 15).sum()), int((qs == 16).sum())
    assert qs.max() == fixed and qs.min() == math.floor(log2V)
    assert n16 == 2 * (V - 2 ** 15) and n15 + n16 == V
    out("")
    out(f"[4] Twenty questions: binary search over N = {V:,} equally likely targets")
    out(f"  worst / best case          = {qs.max()} / {qs.min()} questions"
        f"  (= ceil / floor of log2 N)")
    out(f"  targets needing 15 / 16    = {n15:,} / {n16:,}")
    out(f"  average                    = {qs.mean():.3f} questions  (log2 N = {log2V:.3f})")
    assert qs.mean() >= log2V
    mil = 10 ** 6
    q_mil = max(questions_binary_search(t, 1, mil) for t in (1, mil // 3, mil // 2, mil))
    assert q_mil == math.ceil(math.log2(mil)) == 20 and 2 ** 19 < mil <= 2 ** 20
    out(f"  N = 1,000,000: log2 N = {math.log2(mil):.3f}, worst case {q_mil} questions"
        f"  (2^19 = {2 ** 19:,} < N <= 2^20 = {2 ** 20:,})")

    # ---- 5. Fractional bits ----------------------------------------------------
    out("")
    out("[5] Naming k items at once: ceil(k log2 N) bits in total, divided by k")
    total = {}
    for N in (3, V):
        row = []
        for k in (1, 3, 5, 10, 100, 1000):
            # exact integer test: smallest b with 2^b >= N^k
            b = (N ** k - 1).bit_length()
            assert 2 ** b >= N ** k > 2 ** (b - 1)
            total[(N, k)] = b
            row.append(f"k={k}: {b / k:.3f}")
        out(f"  N = {N:<6} " + ", ".join(row) + f"  -> log2 N = {math.log2(N):.3f}")
    out(f"  3^5 = {3 ** 5} <= 2^8 = {2 ** 8}, so 5 three-way choices fit in 8 bits")
    out(f"  1,000 GPT-2 tokens: {total[(V, 1000)]:,} bits named together vs"
        f" {1000 * fixed:,} bits one at a time")

    # ---- 6. Bytes and kilobytes -------------------------------------------------
    out("")
    out("[6] Bytes and kilobytes (1 byte = 8 bits)")
    kb = 20
    c_bin, c_dec = kb * 1024 * 8, kb * 1000 * 8
    out(f"  {kb} KB at 8192 bits/KB (Lotfi et al. 2022)  = {c_bin:,} bits"
        f" = {pb.bits_to_nats(c_bin):,.1f} nats")
    out(f"  {kb} KB at 8000 bits/KB (1 KB = 1000 bytes) = {c_dec:,} bits"
        f" = {pb.bits_to_nats(c_dec):,.1f} nats")
    out(f"  ratio of the two conventions             = {1024 / 1000:.3f}"
        f"  ({100 * (1024 / 1000 - 1):.1f} % apart)")
    toks = pb.OWT_TRAIN_TOKENS
    nbytes = 2 * toks
    out(f"  nanoGPT train.bin: {toks:,} tokens x 2 bytes = {nbytes / 1e9:.2f} x 10^9 bytes"
        f" = {nbytes / 2 ** 30:.2f} x 2^30 bytes")

    # ---- 7. Paper section 4.1 expression ------------------------------------------
    out("")
    C = c_bin
    lhs = C * LN2 + 2 * math.log(C)                 # C ln 2 + 2 ln C          (nats)
    rhs = pb.bits_to_nats(C + 2 * math.log2(C))     # (C + 2 log2 C) bits -> nats
    all_log2 = C * 1.0 + 2 * math.log2(C)           # every "log" read as log2 (bits)
    mixed = C * LN2 + 2 * math.log2(C)              # first log ln, second log2 (mixed)
    assert abs(lhs - rhs) < 1e-9 * lhs
    assert abs(lhs - pb.log_inv_prior_nats_from_bits(C)) < 1e-9 * lhs
    out(f"[7] Paper section 4.1: C log 2 + 2 log C, with C = {C:,} bits (the 20 KB model)")
    out(f"  2 log2 C                   = {2 * math.log2(C):.3f} bits")
    out(f"  2 log2 C x ln 2            = {2 * math.log2(C) * LN2:.3f} nats"
        f"   and   2 ln C = {2 * math.log(C):.3f} nats")
    out(f"  C ln 2 + 2 ln C            = {lhs:,.1f} nats   <- every log = ln")
    out(f"  (C + 2 log2 C) x ln 2      = {rhs:,.1f} nats   <- identical")
    out(f"  C + 2 log2 C               = {all_log2:,.1f} bits   <- every log = log2")
    out(f"  C ln 2 + 2 log2 C          = {mixed:,.1f} (mixed units) <- first ln, then log2")
    worst = 0.0
    for c in [2, 10, 1_000, 163_840, 10 ** 6, 10 ** 9, 123_456_789]:
        a, b = 2 * math.log2(c) * LN2, 2 * math.log(c)
        worst = max(worst, abs(a - b) / b)
    assert worst < 1e-14
    out(f"  identity 2 log2(C) ln 2 = 2 ln C on 7 values of C: max rel. error {worst:.1e}")

    # ---- 8. Why the bound speaks nats -------------------------------------------
    d = pb.DELTA  # 0.05 [SOURCE: authors' code; Lotfi et al. 2022] - not stated in the paper
    out("")
    out(f"[8] Solving e^(-x) = delta for x gives x = ln(1/delta); delta = {d} (authors' code)")
    out(f"  ln(1/delta)                = {math.log(1 / d):.3f} nats")
    out(f"  log2(1/delta)              = {math.log2(1 / d):.3f} bits  (same information, other unit)")
    assert abs(math.exp(-math.log(1 / d)) - d) < 1e-15

    # ---- 9. ln x <= x - 1 and 1 + x <= e^x ---------------------------------------
    x = np.arange(1, 200_001) * 5e-5          # (0, 10], contains x = 1 exactly
    gap = (x - 1) - np.log(x)
    y = np.arange(-100_000, 50_001) * 1e-4     # [-10, 5], contains x = 0 exactly
    gap2 = np.exp(y) - (1 + y)
    assert gap.min() >= 0 and gap2.min() >= 0
    out("")
    out("[9] ln x <= x - 1 on 200,000 points of (0, 10]; 1 + x <= e^x on 150,001 points of [-10, 5]")
    out(f"  min of (x - 1) - ln x      = {gap.min():.2e}  at x = {x[gap.argmin()]:.4f}")
    out(f"  min of e^x - (1 + x)       = {gap2.min():.2e}  at x = {y[gap2.argmin()]:.4f}")

    # log rules, numerically, on random positive numbers (fixed seed)
    rng = np.random.default_rng(0)
    a, b = rng.uniform(0.01, 100, 1000), rng.uniform(0.01, 100, 1000)
    r = rng.uniform(-5, 5, 1000)
    errs = [np.abs(np.log2(a * b) - (np.log2(a) + np.log2(b))).max(),
            np.abs(np.log2(a / b) - (np.log2(a) - np.log2(b))).max(),
            np.abs(np.log2(a ** r) - r * np.log2(a)).max(),
            np.abs(np.log2(a) - np.log(a) / np.log(2)).max()]
    assert max(errs) < 1e-12
    out(f"  log rules (product, quotient, power, change of base) on 1,000 random pairs:"
        f" max error {max(errs):.1e}")

    # ---- Figures -------------------------------------------------------------------
    FIG_DIR.mkdir(parents=True, exist_ok=True)
    plt.rcParams.update({"font.size": 12})
    fig, axes = plt.subplots(1, 2, figsize=(10.5, 4.2))
    ax = axes[0]
    xs = np.linspace(0.05, 4, 800)
    ax.plot(xs, xs - 1, color="#D55E00", lw=2, label="x - 1  (straight line)")
    ax.plot(xs, np.log(xs), color="#0072B2", lw=2, label="ln x")
    ax.fill_between(xs, np.log(xs), xs - 1, color="#56B4E9", alpha=0.25, lw=0,
                    label="gap = (x - 1) - ln x  >= 0")
    ax.plot([1], [0], "o", color="black", ms=8)
    ax.annotate("touch only at x = 1", xy=(1, 0), xytext=(1.6, -1.6),
                arrowprops=dict(arrowstyle="->", color="black"), fontsize=11)
    ax.axhline(0, color="0.6", lw=0.8)
    ax.set_xlabel("x (a positive number, no unit)")
    ax.set_ylabel("value (no unit)")
    ax.set_title("ln x never rises above x - 1")
    ax.set_ylim(-3.2, 3.2)
    ax.grid(alpha=0.25)
    ax.legend(loc="upper left", fontsize=10, frameon=False)

    ax = axes[1]
    ys = np.linspace(-3, 1.6, 800)
    ax.plot(ys, np.exp(ys), color="#0072B2", lw=2, label="e^x")
    ax.plot(ys, 1 + ys, color="#D55E00", lw=2, label="1 + x  (straight line)")
    ax.fill_between(ys, 1 + ys, np.exp(ys), color="#56B4E9", alpha=0.25, lw=0,
                    label="gap = e^x - (1 + x)  >= 0")
    ax.plot([0], [1], "o", color="black", ms=8)
    ax.annotate("touch only at x = 0", xy=(0, 1), xytext=(-2.8, 3.0),
                arrowprops=dict(arrowstyle="->", color="black"), fontsize=11)
    ax.axhline(0, color="0.6", lw=0.8)
    ax.set_xlabel("x (a real number, no unit)")
    ax.set_ylabel("value")
    ax.set_title("the twin: 1 + x never rises above e^x")
    ax.set_ylim(-2.2, 5.0)
    ax.grid(alpha=0.25)
    ax.legend(loc="upper left", fontsize=10, frameon=False)
    fig.tight_layout()
    fig.savefig(FIG_LNX, dpi=130)
    plt.close(fig)

    fig, ax = plt.subplots(figsize=(7.5, 4.4))
    ps = np.logspace(-5.2, 0, 600)
    ax.plot(ps, -np.log2(ps), color="#0072B2", lw=2, label="surprisal in bits, -log2 p")
    ax.plot(ps, -np.log(ps), color="#E69F00", lw=2, label="surprisal in nats, -ln p")
    for p, txt, off in [(0.5, "fair coin: 1 bit", (-30, 26)),
                        (0.01, f"p = 0.01: {-math.log2(0.01):.3f} bits", (8, 6)),
                        (1 / V, f"p = 1/{V:,}: {log2V:.3f} bits", (8, 6))]:
        ax.plot([p], [-math.log2(p)], "o", color="#0072B2", ms=8)
        ax.annotate(txt, xy=(p, -math.log2(p)), xytext=off, textcoords="offset points",
                    fontsize=10)
    ax.plot([0.01], [-math.log(0.01)], "o", color="#E69F00", ms=8)
    ax.annotate(f"{-math.log(0.01):.3f} nats", xy=(0.01, -math.log(0.01)), xytext=(-78, -24),
                textcoords="offset points", fontsize=10)
    ax.set_xscale("log")
    ax.set_xlabel("probability p of the event (log scale)")
    ax.set_ylabel("surprisal (bits or nats)")
    ax.set_title("Rarer events carry more surprisal")
    ax.set_ylim(0, 19)
    ax.grid(alpha=0.25, which="both")
    ax.legend(loc="upper right", fontsize=10, frameon=False)
    fig.tight_layout()
    fig.savefig(FIG_SUR, dpi=130)
    plt.close(fig)

    out("")
    out(f"Figures: {FIG_LNX.name}, {FIG_SUR.name}. All assertions passed.")

    OUT_TXT.parent.mkdir(parents=True, exist_ok=True)
    OUT_TXT.write_text("\n".join(lines) + "\n", encoding="utf-8")


if __name__ == "__main__":
    main()

Output:

Chapter 3 - logarithms, bits and nats (ch03_bits_nats.py)
[1] Constants
  e                          = 2.718281828
  ln 2   (nats in one bit)   = 0.693147
  1/ln 2 (bits in one nat)   = 1.442695
  examples: log2 8 = 3, log2 1024 = 10, log2 1 = 0, log2(1/2) = -1, log10 1000 = 3, ln e = 1, log2 3 = 1.585

[2] GPT-2 vocabulary, V = 50,257 tokens
  log2 V                     = 15.617 bits  (paper's Random Guess BPD: 15.62; diff -0.003)
  V with log2 V -> 15.62     = 50,187 ... 50,535  (all print as 15.62)
  fixed-length id            = ceil(log2 V) = 16 bits = 2 bytes  (2^15 = 32,768 < V <= 2^16 = 65,536)
  storage overhead           = 16 - log2 V = 0.383 bits per token (2.4 % of 16)
  ln V                       = 10.825 nats;  check: 15.617 bits x 0.693147 = 10.825 nats

[3] Surprisal of an event with probability p
  p            -log2 p (bits)   -ln p (nats)
  1                 0.000          0.000
  0.9               0.152          0.105
  1/2               1.000          0.693
  1/8               3.000          2.079
  0.01              6.644          4.605
  1/V              15.617         10.825

[4] Twenty questions: binary search over N = 50,257 equally likely targets
  worst / best case          = 16 / 15 questions  (= ceil / floor of log2 N)
  targets needing 15 / 16    = 15,279 / 34,978
  average                    = 15.696 questions  (log2 N = 15.617)
  N = 1,000,000: log2 N = 19.932, worst case 20 questions  (2^19 = 524,288 < N <= 2^20 = 1,048,576)

[5] Naming k items at once: ceil(k log2 N) bits in total, divided by k
  N = 3      k=1: 2.000, k=3: 1.667, k=5: 1.600, k=10: 1.600, k=100: 1.590, k=1000: 1.585  -> log2 N = 1.585
  N = 50257  k=1: 16.000, k=3: 15.667, k=5: 15.800, k=10: 15.700, k=100: 15.620, k=1000: 15.618  -> log2 N = 15.617
  3^5 = 243 <= 2^8 = 256, so 5 three-way choices fit in 8 bits
  1,000 GPT-2 tokens: 15,618 bits named together vs 16,000 bits one at a time

[6] Bytes and kilobytes (1 byte = 8 bits)
  20 KB at 8192 bits/KB (Lotfi et al. 2022)  = 163,840 bits = 113,565.2 nats
  20 KB at 8000 bits/KB (1 KB = 1000 bytes) = 160,000 bits = 110,903.5 nats
  ratio of the two conventions             = 1.024  (2.4 % apart)
  nanoGPT train.bin: 9,035,582,198 tokens x 2 bytes = 18.07 x 10^9 bytes = 16.83 x 2^30 bytes

[7] Paper section 4.1: C log 2 + 2 log C, with C = 163,840 bits (the 20 KB model)
  2 log2 C                   = 34.644 bits
  2 log2 C x ln 2            = 24.013 nats   and   2 ln C = 24.013 nats
  C ln 2 + 2 ln C            = 113,589.2 nats   <- every log = ln
  (C + 2 log2 C) x ln 2      = 113,589.2 nats   <- identical
  C + 2 log2 C               = 163,874.6 bits   <- every log = log2
  C ln 2 + 2 log2 C          = 113,599.9 (mixed units) <- first ln, then log2
  identity 2 log2(C) ln 2 = 2 ln C on 7 values of C: max rel. error 1.9e-16

[8] Solving e^(-x) = delta for x gives x = ln(1/delta); delta = 0.05 (authors' code)
  ln(1/delta)                = 2.996 nats
  log2(1/delta)              = 4.322 bits  (same information, other unit)

[9] ln x <= x - 1 on 200,000 points of (0, 10]; 1 + x <= e^x on 150,001 points of [-10, 5]
  min of (x - 1) - ln x      = 0.00e+00  at x = 1.0000
  min of e^x - (1 + x)       = 0.00e+00  at x = 0.0000
  log rules (product, quotient, power, change of base) on 1,000 random pairs: max error 3.6e-15

Figures: ch03_lnx.png, ch03_surprisal.png. All assertions passed.