Physics of Language Models: Part 3.3, Knowledge Capacity Scaling Laws — part 8/8

Cleaned-text code points [110104, 121161). Bibliography omitted here; source.md includes it.

Name part. For the name part, construct P i P_{i} for i ∈ [ N ] i\in[N] following the approach from the “value-only” warmup example. Specifically, let R i R_{i} be fresh randomness, and define P i = s P_{i}=s if F ⊤ ​ ( W ⁡ ( { Z } ) , R i ) F^{\top}(W(\{Z\}),R_{i}) matches the s s -th element in 𝒩 0 ∖ { n 1 , … , n i − 1 } \mathcal{N}_{0}\setminus\{n_{1},\dots,n_{i-1}\} , or an arbitrary symbol ∅ \varnothing if it falls within { n 1 , … , n i − 1 } \{n_{1},\dots,n_{i-1}\} . 29 29 29 Importantly, P i P_{i} may depend on n 1 , … , n i − 1 n_{1},\dots,n_{i-1} ; however, since Lemma F.1 permits P i P_{i} to depend on Q 1 , … , Q i − 1 Q_{1},\dots,Q_{i-1} , this is acceptable. Adopting the analysis from the “name-only” warmup example, we obtain ∑ i ∈ [ N ] log 𝐏𝐫 P i [ P i = Q i ] = − N 𝐥𝐨𝐬𝐬 n ​ a ​ m ​ e ( 𝒵 ) . \textstyle\sum_{i\in[N]}\log\operatornamewithlimits{\mathbf{Pr}}_{P_{i}}[P_{i}=Q_{i}]=-N\mathbf{loss}_{name}(\mathcal{Z})\kern 5.0pt. (F.2)

Diversity Part. For the diversity component, we construct the P i P_{i} ’s as follows. For each a ′ ∈ [ K ] a^{\prime}\in[K] , let a a denote the a ′ a^{\prime} -th attribute in 𝒜 \mathcal{A} . We form P N + ( a ′ − 1 ) ​ D + i P_{N+(a^{\prime}-1)D+i} by initially calculating F ⊥ ​ ( W ⁡ ( 𝒵 ) , n , a , R i ) F^{\bot}(W(\mathcal{Z}),n,a,R_{i}) , where n ∈ 𝒩 n\in\mathcal{N} is selected uniformly at random. 30 30 30 Importantly, P N + ( a ′ − 1 ) ​ D + i P_{N+(a^{\prime}-1)D+i} depends on 𝒩 \mathcal{N} ; however, since Lemma F.1 permits P i P_{i} to depend on Q 1 , … , Q i − 1 Q_{1},\dots,Q_{i-1} , and since 𝒩 \mathcal{N} is uniquely determined by Q 1 , … , Q N Q_{1},\dots,Q_{N} , this is acceptable. Subsequently, if F ⊥ ​ ( W ⁡ ( 𝒵 ) , n , a , R i ) F^{\bot}(W(\mathcal{Z}),n,a,R_{i}) corresponds to the s s -th element in 𝒯 L ∖ { w 1 , … , w i − 1 } \mathcal{T}^{L}\setminus\{w_{1},\dots,w_{i-1}\} , then set P N + ( a ′ − 1 ) ​ D + i = s P_{N+(a^{\prime}-1)D+i}=s ; otherwise, set P N + ( a ′ − 1 ) ​ D + i = ∅ P_{N+(a^{\prime}-1)D+i}=\varnothing . 31 31 31 Importantly, P N + ( a ′ − 1 ) ​ D + i P_{N+(a^{\prime}-1)D+i} depends on w 1 , … , w i − 1 w_{1},\dots,w_{i-1} ; however, since Lemma F.1 permits P i P_{i} to depend on Q N + ( a ′ − 1 ) ​ D + 1 , … , Q N + ( a ′ − 1 ) ​ D + i − 1 Q_{N+(a^{\prime}-1)D+1},\dots,Q_{N+(a^{\prime}-1)D+i-1} , this is acceptable.

Now, let a a be the a ′ a^{\prime} -th element in 𝒜 \mathcal{A} . Consider Q Q as fixed, with randomness arising solely from the calculation of P i P_{i} ’s. Note that Q Q establishes an order of elements in 𝒟 a \mathcal{D}_{a} , denoted by w 1 , … , w D w_{1},\dots,w_{D} . We have ∑ i ∈ [ D ] log 𝐏𝐫 P N + ( a ′ − 1 ) ​ D + i [ P N + ( a ′ − 1 ) ​ D + i = Q N + ( a ′ − 1 ) ​ D + i ] \displaystyle\sum_{i\in[D]}\log\operatornamewithlimits{\mathbf{Pr}}_{P_{N+(a^{\prime}-1)D+i}}[P_{N+(a^{\prime}-1)D+i}=Q_{N+(a^{\prime}-1)D+i}] = ∑ i ∈ [ D ] log 𝔼 n ∈ 𝒩 𝐏𝐫 R [ [ F 1 ⊥ ( W ( 𝒵 ) , n , a , R ) = w i ] ] \displaystyle=\sum_{i\in[D]}\log\operatornamewithlimits{\mathbb{E}}_{n\in\mathcal{N}}\operatornamewithlimits{\mathbf{Pr}}_{R}\Big[\big[F^{\bot}_{1}(W(\mathcal{Z}),n,a,R)=w_{i}\big]\Big] = ∑ w ∈ 𝒟 a log 𝔼 n ∈ 𝒩 𝐏𝐫 R [ [ F 1 ⊥ ( W ( 𝒵 ) , n , a , R ) = w ] ] = : ♠ a \displaystyle=\sum_{w\in\mathcal{D}_{a}}\log\operatornamewithlimits{\mathbb{E}}_{n\in\mathcal{N}}\operatornamewithlimits{\mathbf{Pr}}_{R}\Big[\big[F^{\bot}_{1}(W(\mathcal{Z}),n,a,R)=w\big]\Big]=:\spadesuit_{a}

Let us denote by 𝒩 w , a \mathcal{N}_{w,a} the set of n ∈ 𝒩 n\in\mathcal{N} so that v ⋆ ​ ( n , a ) = w v^{\star}(n,a)=w . We have ♠ a \displaystyle\spadesuit_{a} = ∑ w ∈ 𝒟 a log ∑ n ∈ 𝒩 𝐏𝐫 R [ F 1 ⊥ ( W ( 𝒵 ) , n , a , R ) = w ] − D log N \displaystyle=\sum_{w\in\mathcal{D}_{a}}\log\sum_{n\in\mathcal{N}}\operatornamewithlimits{\mathbf{Pr}}_{R}\big[F^{\bot}_{1}(W(\mathcal{Z}),n,a,R)=w\big]-D\log N ≥ ① ∑ w ∈ 𝒟 a log ∑ n ∈ 𝒩 w , a 𝐏𝐫 R [ F 1 ⊥ ( W ( 𝒵 ) , n , a , R ) = w ] − D log N \displaystyle\overset{\text{①}}{\geq}\sum_{w\in\mathcal{D}_{a}}\log\sum_{n\in\mathcal{N}_{w,a}}\operatornamewithlimits{\mathbf{Pr}}_{R}\big[F^{\bot}_{1}(W(\mathcal{Z}),n,a,R)=w\big]-D\log N = ∑ w ∈ 𝒟 a log 1 | 𝒩 w , a | ∑ n ∈ 𝒩 w , a 𝐏𝐫 R [ F 1 ⊥ ( W ( 𝒵 ) , n , a , R ) = w ] − D log N + ∑ w ∈ 𝒟 log | 𝒩 w , a | \displaystyle=\sum_{w\in\mathcal{D}_{a}}\log\frac{1}{|\mathcal{N}_{w,a}|}\sum_{n\in\mathcal{N}_{w,a}}\operatornamewithlimits{\mathbf{Pr}}_{R}\big[F^{\bot}_{1}(W(\mathcal{Z}),n,a,R)=w\big]-D\log N+\sum_{w\in\mathcal{D}}\log|\mathcal{N}_{w,a}| ≥ ② ∑ w ∈ 𝒟 a 1 | 𝒩 w , a | ∑ n ∈ 𝒩 w , a log 𝐏𝐫 R [ F 1 ⊥ ( W ( 𝒵 ) , n , a , R ) = w ] − D log N + ∑ w ∈ 𝒟 log | 𝒩 w , a | \displaystyle\overset{\text{②}}{\geq}\sum_{w\in\mathcal{D}_{a}}\frac{1}{|\mathcal{N}_{w,a}|}\sum_{n\in\mathcal{N}_{w,a}}\log\operatornamewithlimits{\mathbf{Pr}}_{R}\big[F^{\bot}_{1}(W(\mathcal{Z}),n,a,R)=w\big]-D\log N+\sum_{w\in\mathcal{D}}\log|\mathcal{N}_{w,a}| Above, ① uses monotonicity of the log function and ② uses convexity of the log \log function. Using simple Chernoff bound, one can see that as long a N ≥ Ω ⁡ ( D ​ log ⁡ N ) N\geq\Omega(D\log N) , with high probability | 𝒩 w , a | ≥ ( 1 − o ⁡ ( 1 ) ) ​ N D |\mathcal{N}_{w,a}|\geq(1-o(1))\frac{N}{D} for all w ∈ D w\in D . Thus, we know with high probability ♠ a \displaystyle\spadesuit_{a} ≥ ( 1 + o ( 1 ) ) D ∑ w ∈ 𝒟 a 1 N ∑ n ∈ 𝒩 w , a log 𝐏𝐫 R [ F 1 ⊥ ( W ( 𝒵 ) , n , a , R ) = w ] − D log D − o ( D ) \displaystyle\geq(1+o(1))D\sum_{w\in\mathcal{D}_{a}}\frac{1}{N}\sum_{n\in\mathcal{N}_{w,a}}\log\operatornamewithlimits{\mathbf{Pr}}_{R}\big[F^{\bot}_{1}(W(\mathcal{Z}),n,a,R)=w\big]-D\log D-o(D) = ( 1 + o ( 1 ) ) D 1 N ∑ n ∈ 𝒩 log 𝐏𝐫 R [ F 1 ⊥ ( W ( 𝒵 ) , n , a , R ) = v ⋆ ( n , a ) ] − D log D − o ( D ) \displaystyle=(1+o(1))D\frac{1}{N}\sum_{n\in\mathcal{N}}\log\operatornamewithlimits{\mathbf{Pr}}_{R}\big[F^{\bot}_{1}(W(\mathcal{Z}),n,a,R)=v^{\star}(n,a)\big]-D\log D-o(D) Thus, summing up over all the diversity part, we have (recall we are fixing Q Q and thus fixing 𝒵 \mathcal{Z} ) ∑ i ∈ [ K ​ D ] log 𝐏𝐫 P N + i [ P N + i = Q N + i ] \displaystyle\hskip 10.00002pt\;\sum_{i\in[KD]}\log\operatornamewithlimits{\mathbf{Pr}}_{P_{N+i}}[P_{N+i}=Q_{N+i}] ≥ ( 1 + o ( 1 ) ) D 1 N ​ K ∑ n ∈ 𝒩 , a ∈ 𝒜 log 𝐏𝐫 R [ F 1 ⊥ ( W ( 𝒵 ) , n , a , R ) = v ⋆ ( n , a ) ] − K D log D − o ( K D ) \displaystyle\geq(1+o(1))D\frac{1}{NK}\sum_{n\in\mathcal{N},a\in\mathcal{A}}\log\operatornamewithlimits{\mathbf{Pr}}_{R}\big[F^{\bot}_{1}(W(\mathcal{Z}),n,a,R)=v^{\star}(n,a)\big]-KD\log D-o(KD) = − ( 1 + o ⁡ ( 1 ) ) ​ D ​ 𝐥𝐨𝐬𝐬 v ​ a ​ l ​ u ​ e ​ 1 ​ ( 𝒵 ) − K ​ D ​ log ⁡ D − o ⁡ ( K ​ D ) . \displaystyle=-(1+o(1))D\mathbf{loss}_{value1}(\mathcal{Z})-KD\log D-o(KD)\kern 5.0pt. (F.3)

Value part. For the value part, we construct P N + K ​ D + 1 , … , P N + K ​ D + N ​ K P_{N+KD+1},\dots,P_{N+KD+NK} as follows. For P N + K ​ D + ( n ′ − 1 ) ​ K + a ′ P_{N+KD+(n^{\prime}-1)K+a^{\prime}} , letting n n be the n ′ n^{\prime} -th name in 𝒩 \mathcal{N} and a a be the a ′ a^{\prime} -th attribute in 𝒜 \mathcal{A} . Let us compute F ⊥ ​ ( W ⁡ ( 𝒵 ) , n , a , R ) F^{\bot}(W(\mathcal{Z}),n,a,R) and find the corresponding s 1 , … , s C ∈ [ D ] s_{1},\dots,s_{C}\in[D] such that F i ⊥ ​ ( W ⁡ ( 𝒵 ) , n , a , R ) F_{i}^{\bot}(W(\mathcal{Z}),n,a,R) is the s i s_{i} -th element in 𝒟 a \mathcal{D}_{a} for each i ∈ [ C ] i\in[C] . If not found, we define P N + K ​ D + ( n ′ − 1 ) ​ K + a ′ = ∅ P_{N+KD+(n^{\prime}-1)K+a^{\prime}}=\varnothing ; otherwise, define P N + K ​ D + ( n ′ − 1 ) ​ K + a ′ = ( s 1 , … , s C ) ∈ [ D C ] P_{N+KD+(n^{\prime}-1)K+a^{\prime}}=(s_{1},\dots,s_{C})\in[D^{C}] . 32 32 32 Again, importantly, we can do so because P N + K ​ D + ( n ′ − 1 ) ​ K + a ′ P_{N+KD+(n^{\prime}-1)K+a^{\prime}} depends on 𝒩 , 𝒟 a \mathcal{N},\mathcal{D}_{a} but they can be computed using the values of Q 1 , … , Q N + K ​ D Q_{1},\dots,Q_{N+KD} .

Following the same simple argument as the “value-only” warmup example, we have ∑ i ∈ [ N ​ K ] log 𝐏𝐫 P N + K ​ D + i [ P N + K ​ D + i = Q N + K ​ D + i ] = ∑ n ∈ 𝒩 , a ∈ 𝒜 𝐏𝐫 [ F ⊥ ( W ( 𝒵 ) , n , a , R ) = v ⋆ ( n , a ) ] \displaystyle\sum_{i\in[NK]}\log\operatornamewithlimits{\mathbf{Pr}}_{P_{N+KD+i}}[P_{N+KD+i}=Q_{N+KD+i}]=\sum_{n\in\mathcal{N},a\in\mathcal{A}}\operatornamewithlimits{\mathbf{Pr}}\Big[F^{\bot}(W(\mathcal{Z}),n,a,R)=v^{\star}(n,a)\Big] = − N ​ K ​ 𝐥𝐨𝐬𝐬 v ​ a ​ l ​ u ​ e ​ ( 𝒵 ) \displaystyle=-NK\mathbf{loss}_{value}(\mathcal{Z}) (F.4)

Summing ( F.2 ) ( F.3 ) and ( F.4 ) , and applying Lemma F.1 , we have log | 𝒲 | ≥ 𝔼 𝒵 [ N ​ log ⁡ N 0 − N e 𝐥𝐨𝐬𝐬 n ​ a ​ m ​ e ​ ( 𝒵 ) + N ​ K ​ log ⁡ D C e 𝐥𝐨𝐬𝐬 v ​ a ​ l ​ u ​ e ​ ( 𝒵 ) + K ​ D ​ log ⁡ T L − D D ​ e ( 1 + o ⁡ ( 1 ) ) ​ 𝐥𝐨𝐬𝐬 v ​ a ​ l ​ u ​ e ​ 1 ​ ( 𝒵 ) − o ⁡ ( K ​ D ) ] . \displaystyle\log|\mathcal{W}|\geq\operatornamewithlimits{\mathbb{E}}_{\mathcal{Z}}\Big[N\log\frac{N_{0}-N}{e^{\mathbf{loss}_{name}(\mathcal{Z})}}+NK\log\frac{D^{C}}{e^{\mathbf{loss}_{value}(\mathcal{Z})}}+KD\log\frac{T^{L}-D}{De^{(1+o(1))\mathbf{loss}_{value1}(\mathcal{Z})}}-o(KD)\Big]\kern 5.0pt. This finishes the proof of Theorem 3.2 . ∎

## Appendix G Missing Remark

###### Remark G.1 .

Due to the significant overlap among textbooks, especially those designed for PreK-12 education, estimating the total amount of knowledge contained within all English-language textbooks can be challenging. However, we attempt to do so as follows.

According to a 2023 article, Pearson Education, a UK-based educational publisher, reported the highest revenue in 2021, with Wiley and McGraw Hill being the top two US-based educational publishers in terms of revenue. 33 33 33 https://wordsrated.com/education-book-publishing-companies-statistics/ , accessed March 2024.

• Pearson’s official website lists fewer than 2,100 textbooks. 34 34 34 https://www.pearson.com/en-us/pearsonplus/search.html for their full list of eTextbooks and http://www.mypearsonstore.com/bookstore/browse.asp for their full list of hard copy books, both accessed March 2024.

• Wiley’s official website lists fewer than 69,000 textbooks. 35 35 35 https://www.wiley.com/en-us/subjects , accessed March 2024. We wrote a code to sum up all the books in all of their subcategories; our code may double count books, so this is only a safe upper bound. We used this number instead of the “21,000” online books mentioned on https://www.wiley.com/learn/librarysolutions/online-books-purchase.html , accessed March 2024.

• McGraw Hill lists fewer than 22,000 textbooks for PreK-12 education, many of which have significant content overlap (as many are tailored for one of the 50 US states). 36 36 36 https://www.mheducation.com/search.html?searchQuery=&page=1&sortby=title_desc&order=desc&bu=seg&TYPE=Products&PRODUCT_TYPE_PATH=_Student+Materials , accessed March 2024. They list fewer than 2,000 textbooks for higher education.

Taking these figures into account, it seems reasonable to estimate that the content of all English-language textbooks could be condensed into no more than 100,000 textbooks. Assuming an average of 160,000 words per book (e.g., 400 pages with 400 words each), this would amount to a total of 16 billion words.