Physics of Language Models: Part 2.1, Grade-School Math and the Hidden Reasoning Process β part 5/6
Cleaned-text code points [61120, 76962). Bibliography omitted here; source.md includes it.
In Line 11 and Line 15 of Algorithm 3 , when randomly selecting πππππ 1 \mathtt{param}_{1} from a set, instead of doing so uniformly at random, to improve the algorithmβs success rate and the problemβs difficulty level, we introduce a discursion that that biases slightly towards abstract parameters and parameters already in ππΎπππ£ G π½ ππΎπΌπΎπ₯ β ( ππππ ) \mathsf{Next1}_{G_{\mathsf{d}}^{\mathsf{nece3}}}(\mathtt{Topo}) . 24 24 24 For those who are interested, abstract parameters are the keys to cause the generation process to fail, because once they become πππππ 0 \mathtt{param}_{0} we cannot add edges πππππ 1 β πππππ 0 \mathtt{param}_{1}\to\mathtt{param}_{0} ; so we had better select them earlier than later (thus put them at the back of ππππ \mathtt{Topo} ). On the other hand, for πππππ 1 \mathtt{param}_{1} that is already in ππΎπππ£ G π½ ππΎπΌπΎπ₯ β ( ππππ ) \mathsf{Next1}_{G_{\mathsf{d}}^{\mathsf{nece3}}}(\mathtt{Topo}) , adding this edge πππππ 1 β πππππ 0 \mathtt{param}_{1}\to\mathtt{param}_{0} does not further change it; this can help us create a problem whose solution βdepthβ is higher. Specifically, we first generate g βΌ π© β‘ ( 0 , 1 ) g\sim\mathcal{N}(0,1) a random Gaussian, then define π πππππ β‘ ( a ) = ( π a is abstract + π a β ππΎπππ£ G π½ ππΎπΌπΎπ₯ β ( ππππ ) ) β
| g | \mathtt{weight}(a)=\big(\mathds{1}_{\text{$a$ is abstract}}+\mathds{1}_{a\in\mathsf{Next1}_{G_{\mathsf{d}}^{\mathsf{nece3}}}(\mathtt{Topo})}\big)\cdot|g| , and then sample a a with a probability β e π πππππ β‘ ( a ) \propto e^{\mathtt{weight}(a)} .
#### D.2.3 Construction of G π½ ππΎπΌπΎ G_{\mathsf{d}}^{\mathsf{nece}}
So far we have created G π½ ππΎπΌπΎπ₯ G_{\mathsf{d}}^{\mathsf{nece3}} and ππππ \mathtt{Topo} with the property that every instance parameter in G π½ ππΎπΌπΎπ₯ G_{\mathsf{d}}^{\mathsf{nece3}} has in-degree β€ 1 \leq 1 . In the next step, we add additional dependency edges to make in-degree to be a random number between 1 1 and 4 4 . We do so by introducing additional edges; and we also introduce an additional vertex π±ππ¦ \mathsf{RNG} . This is our final necessary dependency graph G π½ ππΎπΌπΎ G_{\mathsf{d}}^{\mathsf{nece}} .
Our pseudocode is given in Algorithm 4 . In this step, we shall make sure ππ β‘ ( G π½ ππΎπΌπΎ ) = s \mathsf{op}(G_{\mathsf{d}}^{\mathsf{nece}})=s is exact (and declare failure if this is not possible). We do so to precisely control the solutionβs difficulty (so that when we evaluate the model, we can choose to evaluate it on problems with a fixed value of s s ).
#### D.2.4 Construction of G π½ G_{\mathsf{d}}
Finally, once we have G π½ ππΎπΌπΎ G_{\mathsf{d}}^{\mathsf{nece}} the necessary dependency graph, we are left to add unnecessary dependency edges (and unnecessary parameters) to form the complete G π½ G_{\mathsf{d}} .
During this process, we shall add all the remaining instance parameters from G π G_{\mathsf{s}} into G π½ G_{\mathsf{d}} . When adding each of them, we randomly select the parameters that it shall depend on from all the previously known parameters. 26 26 26 In fact, we do slightly smarter than the most naive approach. If one simply lets each newly added unnecessary parameter to depend, randomly among all the parameters that have already been added to G π½ G_{\mathsf{d}} , then those unnecessary parameters will likely appear towards the end of the topological order. For such reason, we give it 0.5 probability to depend only on a set πΈπππ»πππ \mathtt{IndList} , which consists of newly-added, unnecessary parmaeters, that do not depend on G π½ G_{\mathsf{d}} . This way, the unnecessary parameters can also appear to the front of the tropologic order. Note that during this process, we may also introduce new, unnecessary abstract parameters, see the full pseudocode in Algorithm 5 .
###### Remark D.5 .
G π½ G_{\mathsf{d}} consists of all the instance and query parameters in G π G_{\mathsf{s}} and the abstract parameters they may (recursively) depend on. There may exist abstract parameters that can be described in G π G_{\mathsf{s}} that are not present in G π½ G_{\mathsf{d}} ; but all the instance parameters in G π G_{\mathsf{s}} shall be present in G π½ G_{\mathsf{d}} .
### D.3 Generate English: Problem, Question and Solution
At this point, we have constructed a dependency graph G π G_{\mathsf{s}} where each instance parameter a β G π a\in G_{\mathsf{s}} may depend on between 1 and 4 other vertices (could be abstract, instance parameters or π±ππ¦ \mathsf{RNG} ). We have not yet introduced how a a should be computed, and we do this using a random process πΆππππππππππ β‘ ( G π½ , a ) \mathtt{GenSentence}(G_{\mathsf{d}},a) in Algorithm 6 .
Problem description. The problem description simply consists of listing over all instance parameters a β G π½ a\in G_{\mathsf{d}} and call πΆππππππππππ β‘ ( G π½ , a ) \mathtt{GenSentence}(G_{\mathsf{d}},a) . We then randomly shuffle the sentences to make the problem hard. Please note the descriptions of abstract parameters are not present in the problem description, because they are inherited from the hierarchical categorization. This is our attempt to make our math data also capture some English meaning, that is the model also needs to learn what items are in each category, and which category is above another category, etc. This is some knowledge that cannot be learned by reading one problem β it must be learned after reading sufficiently many data.
Question description. Our query parameter can be either an instance or abstract parameter, and it is the last element in ππππ \mathtt{Topo} . We use a single sentence to ask for its value βHow manyβ¦ doesβ¦ have?β and we put this question either at the front or at the end of the problem description (depending on the data type).
Solution description. We generate the solution text, by going over all the (instance or abstract) parameters in ππππ \mathtt{Topo} in its correct order , and generate a single sentence to compute each parameter. This process is straightforward but notationally heavy, we describe it below by examples.
β’ Given any instance parameter a β ππππ a\in\mathtt{Topo} , suppose for instance a a is 7 times the sum of parameters b , c , d b,c,d . Because of the topological order, the parameters b , c , d b,c,d must have already defined with variable names, denoted as v β a β r b , v β a β r c , v β a β r d var_{b},var_{c},var_{d} . Then we define solution string of a a as β Define [name of a] as v β a β r 0 ; v β a β r 1 = v β a β r b + v β a β r c = β― ; v β a β r 2 = v β a β r 1 + v β a β r d = β― ; so v β a β r 0 = 7 Γ v β a β r 2 = β― .β \text{``{Define} [name of a] {as} $var_{0}$; $var_{1}=var_{b}+var_{c}=\cdots$ ; $var_{2}=var_{1}+var_{d}=\cdots$; }\\ \text{{so} $var_{0}=7\times var_{2}=\cdots$.''} Here, the arithmetic computation is decomposed into 2-ary operations step by step separated with semicolons (so ππ G π½ β ( a ) \mathsf{op}_{G_{\mathsf{d}}}(a) is exactly the number of semicolons). The v β a β r 0 , v β a β r 1 , v β a β r 2 var_{0},var_{1},var_{2} are three new (but distinct) random variables and their names are between a-z or A-Z and have 52 possible random choices. The β β― \cdots β ignores the math calculations.
β’ Given an abstract parameter a β ππππ a\in\mathtt{Topo} , suppose for instance a = b Γ c + d Γ e + f Γ g a=b\times c+d\times e+f\times g then we similarly define its solution text as β Define [name of a] as v β a β r 0 ; v β a β r 1 = v β a β r b Γ v β a β r c = β― ; v β a β r 2 = v β a β r d Γ v β a β r e = β― ; β v β a β r 3 = v β a β r f Γ v β a β r g = β― ; v β a β r 4 = v β a β r 1 + v β a β r 2 = β― ; so v β a β r 0 = v β a β r 3 + v β a β r 4 = β― .β \text{``{Define} [name of a] {as} $var_{0}$; $var_{1}=var_{b}\times var_{c}=\cdots$ ; $var_{2}=var_{d}\times var_{e}=\cdots$; }\\ \text{``$var_{3}=var_{f}\times var_{g}=\cdots$ ; $var_{4}=var_{1}+var_{2}=\cdots$; }\text{{so} $var_{0}=var_{3}+var_{4}=\cdots$.''} Above, once again v β a β r 0 , v β a β r 1 , v β a β r 2 , v β a β r 3 , v β a β r 4 var_{0},var_{1},var_{2},var_{3},var_{4} are new (but distinct) random variable names from a-z or A-Z, and we break down the computation into 2-ary operations.
With the above examples in mind, and combining those with real examples in Figure 11 , it should be very clear how the solution texts are generated.
###### Remark D.6 .
ππ β‘ ( G π½ ππΎπΌπΎ ) \mathsf{op}(G_{\mathsf{d}}^{\mathsf{nece}}) is equal to the total number of semicolons in the solution text, because it represents the total (and minimum!) number of arithmetic operations needed to compute the final query parameter.
### D.4 Putting Altogether
We put together our data generation process for the structure graph G π G_{\mathsf{s}} and the dependency graph G π½ G_{\mathsf{d}} (along with G π½ ππΎπΌπΎ , ππππ G_{\mathsf{d}}^{\mathsf{nece}},\mathtt{Topo} ) in Algorithm 7 .
In particular, we use global parameters ip max \textsf{ip}_{\max} and op max \textsf{op}_{\max} : the former controls the maximum number of instance parameters, and the latter controls the maximum number of solution operations. We select n , m , s n,m,s based on op max \textsf{op}_{\max} (to ensure that 1 β€ n β€ m β€ s β€ op max 1\leq n\leq m\leq s\leq\textsf{op}_{\max} ), and d , e , w 0 , w 1 d,e,w_{0},w_{1} based on ip max \textsf{ip}_{\max} and s s . We also provide a boolean switch f β o β r β c β e force and when πΏπππΌπΎ = true \mathsf{force}=\mathrm{true} , we shall force s = op max s=\textsf{op}_{\max} so that the generated math problem will have its solution to be of exactly op max \textsf{op}_{\max} operations.
We define datasets β’ iGSM op β€ op max , ip β€ ip max \textsf{iGSM}^{\textsf{op}\leq\textsf{op}_{\max},\textsf{ip}\leq\textsf{ip}_{\max}} as the process of invoking DrawAll β ( op max , ip max , πΏπππΌπΎ = false ) \mathtt{\hyperref@@ii[alg:dependency-graph]{DrawAll}}(\textsf{op}_{\max},\textsf{ip}_{\max},\mathsf{force}=\mathrm{false}) .
β’ iGSM op = op max , ip β€ ip max \textsf{iGSM}^{\textsf{op}=\textsf{op}_{\max},\textsf{ip}\leq\textsf{ip}_{\max}} as the process of invoking DrawAll β ( op max , ip max , πΏπππΌπΎ = true ) \mathtt{\hyperref@@ii[alg:dependency-graph]{DrawAll}}(\textsf{op}_{\max},\textsf{ip}_{\max},\mathsf{force}=\mathrm{true}) .
Using this language: β’ The training data iGSM-med is iGSM op β€ 15 , ip β€ 20 \textsf{iGSM}^{\textsf{op}\leq 15,\textsf{ip}\leq 20} ;
β’ The eval data of iGSM-med additionally includes iGSM op = o β p , ip β€ 20 \textsf{iGSM}^{\textsf{op}=op,\textsf{ip}\leq 20} for o β p β { 15 , 20 , 21 , 22 , 23 } op\in\{15,20,21,22,23\} ;
β’ The training data iGSM-hard is iGSM op β€ 21 , ip β€ 28 \textsf{iGSM}^{\textsf{op}\leq 21,\textsf{ip}\leq 28} ;
β’ The eval data of iGSM-hard additionally includes iGSM op = o β p , ip β€ 28 \textsf{iGSM}^{\textsf{op}=op,\textsf{ip}\leq 28} for o β p β { 21 , 28 , 29 , 30 , 31 , 32 } op\in\{21,28,29,30,31,32\} .
###### Remark D.7 .
During training (regardless of pretrain or finetune for probing tasks), we only use those data whose hash value of their solution template (see Footnote 11 ) is < 17 ( mod 23 ) <17\pmod{23} , and during evaluation we only use those whose hash value is β₯ 17 ( mod 23 ) \geq 17\pmod{23} . This ensures a strict separation between train and test data (even in terms of their solution templates).
###### Remark D.8 .
In Algorithm 7 , we chose s = min β‘ { t 0 , t 1 } s=\min\{t_{0},t_{1}\} , where t 0 t_{0} and t 1 t_{1} are two random integers between 1 1 and op max \textsf{op}_{\max} . This choice encourages more easier math problems in the pretrain data, which we found improves the modelβs learning.
## Appendix E Data Details: Probing Data Preparation
We describe here how we prepare the probing data. We generate math data according to Appendix D .
For each problem and each probing task (such as nece β ( A ) \texttt{nece}(A) , dep β ( A , B ) \texttt{dep}(A,B) , etc), we need to specify two things: at which position to probe and what parameters A A (or A , B A,B ) to probe. β’ For nece and dep , the probing always takes place at the end of the problem (and question) description, so there is no choice to be made; for value , can_next , nece_next tasks, the probing can take place at the end of each sentence in the solution for (including the beginning of the first solution sentence), and we uniformly at random make such choices.
β’ Each parameter A A (or B B ) can be uniformly at random chosen from the set of all (instance or abstract) parameters in our dependency graph G π½ G_{\mathsf{d}} (with the only requirement that A β B A\neq B ).
In the end, we make sure for each problem and each probing task, we make at most 10 such random choices (over the position and the choice of parameters) and sample without replacement.
Just like in the pretrain data, we prepare our probing data so that only problems with hash values of their solution template (see Footnote 11 ) where the hash < 17 ( mod 23 ) <17\pmod{23} are included in the training set, and the rest are used for testing.
## Appendix F Experiment Details
Model. We use the GPT2 architecture [ 18 ] , replacing its absolute positional embedding with modern rotary positional embedding [ 20 , 7 ] , still referred to as GPT2 for short. (We also played with the Llama architecture (especially with gated MLP layers) aand did not see any benefit of using it. This GPT2 performs comparably to Llama/Mistral at least for knowledge tasks [ 4 ] .)
Let GPT2- β \ell - h h denote an β \ell -layer, h h -head, 64 β h 64h -dim GPT2 model. We primarily use GPT2-12-12 (a.k.a. GPT2-small) in this paper, but in Section 6 we explore larger models with different widths and depths. Our size-1 models are GPT2-4-21, GPT2-8-15, GPT2-12-12, GPT2-16-10, GPT2-20-9, roughly the same size as GPT2-small. Our size-2 models are GPT2-4-30, GPT2-8-21, GPT2-12-17, GPT2-16-15, GPT2-20-13, roughly twice the size of GPT2-small. We use a context length of 768/1024 for language model pretraining on iGSM-med / iGSM-hard \textsf{iGSM-med}/\textsf{iGSM-hard} and a context length of 2048 for evaluation.
Data size. For both pretraining and finetuning, we did not limit the amount of training data; we generated new data on-the-fly. We do not explore sample complexity in this paper, such as the number of math problems needed to achieve a certain level of accuracy, as it would complicate the main message of this paper.
### F.1 Pretrain Experiment Details
Pretrain parameters. We used the AdamW optimizer with mixed-precision fp16, Ξ² = ( 0.9 , 0.98 ) \beta=(0.9,0.98) , cosine learning rate decay (down to 0.01x of peak learning rate in the end), and 1000 steps of linear ramp-up. We used a mixture of V100/A100 GPUs, but the GPU specifications are not relevant here. 27 27 27 A 128-GPU job with batch size 1 each would be identical to a 32-GPU job with batch size 4 each. For all of our pretrain experiments: β’ On the iGSM-med datasets, we used a (peak) learning rate 0.002 0.002 , weight decay of 0.05 0.05 , batch size of 512, context length of 768, and trained for 100,000 100,000 steps.
β’ On the iGSM-hard datasets, we used a (peak) learning rate 0.002 0.002 , weight decay of 0.03 0.03 , batch size of 256, context length of 1024, and trained for 200,000 200,000 steps.
Our pretrain data is constructed by randomly generating math problems (and solutions), concatenating them together, and truncating them (in the right) to fit within the 768 or 1024-sized context window. If a problem is longer than the context window size, we discard it (this happens very rarely).
Test-time parameters. When evaluating on test data, we use context length 2048 for both iGSM-med and iGSM-hard . We use either beam=1 and dosample=False (greedy) or beam=4 and dosample=True (beam-search multinomial sampling) to present test accuracies. We discover it is better to keep dosample=False while beam=1 and dosample=True while beam=4 . We also tried larger beam sizes and found no further improvements.