Physics of Language Models: Part 2.1, Grade-School Math and the Hidden Reasoning Process — part 2/6
Cleaned-text code points [15291, 31282). Bibliography omitted here; source.md includes it.
Problem generation. The problem is articulated by describing the dependency graphs in English, one sentence for each instance parameter. 6 6 6 We use simple English sentence templates to describe the problem, and did not worry about grammar mistakes such as singular vs plural forms. There are other randomness besides the dependency graph, such as when parameter A A depends on B , C B,C it could be A + B A+B or A − B A-B . (Abstract parameters are not described because they are inherited by the structure graph.) We randomly permute the sentence ordering to further increase difficulty. A parameter is selected and asked with a question in the end (or at the beginning). Below is an easy example corresponding to Figure 1 ; a harder example is in Figure 11 . (Problem - Easy) The number of each Riverview High’s Film Studio equals 5 times as much as the sum of each Film Studio’s Backpack and each Dance Studio’s School Daypack. The number of each Film Studio’s School Daypack equals 12 more than the sum of each Film Studio’s Messenger Backpack and each Central High’s Film Studio. The number of each Central High’s Film Studio equals the sum of each Dance Studio’s School Daypack and each Film Studio’s Messenger Backpack. The number of each Riverview High’s Dance Studio equals the sum of each Film Studio’s Backpack, each Film Studio’s Messenger Backpack, each Film Studio’s School Daypack and each Central High’s Backpack. The number of each Dance Studio’s School Daypack equals 17. The number of each Film Studio’s Messenger Backpack equals 13. How many Backpack does Central High have? (2.1)
### 2.2 Step 2: Solution Construction (CoT)
Let solution be a sequence of sentences describing the necessary steps towards solving the given problem, where the sentences follow any topological order — also known as Chain-of-Thought, CoT. For each parameter necessary towards answering the final question, we assign to it a random letter among the 52 choices (a..z or A..Z), and use a sentence to describe its computation: 7 7 7 There are different ways to format the CoT solution. We noted that starting with “Define [param] as X” instead of [intermediate steps] improves the model’s accuracy, so we have adhered to this CoT format. Define [param] as X; [intermediate steps]; so X = … Throughout this paper, we consider arithmetics mod 23 23 to avoid errors from computation involving large numbers. It is perhaps the easiest to directly see a solution example (corresponding to ( 2.1 ) ), and a more involved example is in Figure 11 : (Solution - Easy) Define Dance Studio’s School Daypack as p; so p = 17. Define Film Studio’s Messenger Backpack as W; so W = 13. Define Central High’s Film Studio as B; so B = p + W = 17 + 13 = 7. Define Film Studio’s School Daypack as g; R = W + B = 13 + 7 = 20; so g = 12 + R = 12 + 20 = 9. Define Film Studio’s Backpack as w; so w = g + W = 9 + 13 = 22. Define Central High’s Backpack as c; so c = B * w = 7 * 22 = 16. Answer: 16. (2.2)
We emphasize that: • The solution only contain parameters necessary towards calculating the final query parameter.
• The solution follows the correct logical order: i.e. all the parameters used in the calculation must have appeared and been computed beforehand.
• We break computations to binary ops: g = 12 + 13 + 7 g=12+13+7 is broken into g = 12 + R g=12+R and R = 13 + 7 R=13+7 in the above solution. The number of semicolons “;” equals the number of operations . This reduces the arithmetic complexity of the solution, which is not the focus of this paper. 8 8 8 Even GPT-4 can make mistakes on calculating “3 * (4+10) + 12 * (5+6)” without using external calculator.
### 2.3 Difficulty Control
Although deferring all the pseudocode to Appendix D , we summarize below the main randomness used in the data generation process. This includes the random choice of a hierarchical categorization (i.e., the English part); a structure graph (i.e., the instance parameters); a dependency graph; arithmetic computations on the dependency graph; integer numbers (i.e., the 𝖱𝖭𝖦 \mathsf{RNG} ); problem sentence permutation; and the query parameter.
We use two parameters to control data’s difficulty: ip is the number of instance parameters, and op is the number of solution operations; the data’s difficulty is an increasing function over them. We call our dataset iGSM , to reflect the nature that such synthetic dataset can be of infinite size . We use iGSM op ≤ o p , ip ≤ i p \textsf{iGSM}^{\textsf{op}\leq op,\textsf{ip}\leq ip} to denote the data generated with constraint op ≤ o p \textsf{op}\leq op and ip ≤ i p \textsf{ip}\leq ip , and use iGSM op = o p , ip ≤ i p \textsf{iGSM}^{\textsf{op}=op,\textsf{ip}\leq ip} to denote those restricting to op = o p \textsf{op}=op . 9 9 9 We choose op non-uniformly; for instance, we let op = min { t 0 , t 1 } \textsf{op}=\min\{t_{0},t_{1}\} for two random draws t 0 , t 1 ∈ [ o p ] t_{0},t_{1}\in[op] . This ensures that the dataset has more easy data — which makes training faster. (See also similar behavior for arithmetics [ 13 ] .)
### 2.4 Train and Test Datasets
We consider two families of datasets. • In the iGSM-med data family we use ip ≤ 20 \textsf{ip}\leq 20 .
The training data is iGSM-med op ≤ 15 = def iGSM op ≤ 15 , ip ≤ 20 \textsf{iGSM-med}^{\textsf{op}\leq 15}\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle def}}}{{=}}\textsf{iGSM}^{\textsf{op}\leq 15,\textsf{ip}\leq 20} . We evaluate the pretrained model both in-distribution, on iGSM-med op ≤ 15 \textsf{iGSM-med}^{\textsf{op}\leq 15} and iGSM-med op = 15 \textsf{iGSM-med}^{\textsf{op}=15} , and out-of-distribution (OOD), on iGSM-med op = o p \textsf{iGSM-med}^{\textsf{op}=op} for o p ∈ { 20 , 21 , 22 , 23 } op\in\{20,21,22,23\} and iGSM-med op = o p , reask \textsf{iGSM-med}^{\textsf{op}=op,\textsf{reask}} . Here, reask denotes first generating a problem from iGSM-med op = o p \textsf{iGSM-med}^{\textsf{op}=op} and then resampling a query parameter. 10 10 10 Due to the topological nature of our data/solution generation process, reask greatly changes the data distribution and the number of operations needed. It provides an excellent OOD sample for evaluation. Details are in Appendix D .
• In the iGSM-hard data family we use ip ≤ 28 \textsf{ip}\leq 28 . The training data is iGSM-hard op ≤ 21 = def iGSM op ≤ 21 , ip ≤ 28 \textsf{iGSM-hard}^{\textsf{op}\leq 21}\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle def}}}{{=}}\textsf{iGSM}^{\textsf{op}\leq 21,\textsf{ip}\leq 28} . We evaluate the pretrained model both in-distribution, on iGSM-hard op ≤ 21 \textsf{iGSM-hard}^{\textsf{op}\leq 21} and iGSM-hard op = 21 \textsf{iGSM-hard}^{\textsf{op}=21} , and OOD on iGSM-hard op = o p \textsf{iGSM-hard}^{\textsf{op}=op} for o p ∈ { 28 , 29 , 30 , 31 , 32 } op\in\{28,29,30,31,32\} and iGSM-hard op = o p , reask \textsf{iGSM-hard}^{\textsf{op}=op,\textsf{reask}} .
Additionally, we use iGSM-med p q \textsf{iGSM-med}_{pq} to indicate placing the question after the problem and iGSM-med q p \textsf{iGSM-med}_{qp} the other way (similarly for iGSM-hard ). The difficulty of iGSM-med is already quite non-trivial to humans (at least not solvable with few-shot learning using GPT-4/4o, see Figure 2 ).
###### Proposition 2.2 .
Ignoring unused parameters, numerics, sentence orderings, English words, a-z and A-Z letter choices, iGSM-med op = 15 \textsf{iGSM-med}^{\textsf{op}=15} still has at least 7 7 billion solution templates , and iGSM-hard op = 21 \textsf{iGSM-hard}^{\textsf{op}=21} has at least 90 90 trillion solution templates . 11 11 11 A solution template is created by replacing all numbers with ‘0’, substituting variables (a-z or A-Z) with letters in their appearance order, and changing parameters to their types (instance or abstract). For instance, “Define Owl Forest’s Elephant as y; so y = 11. Define Parrot Paradise’s Raccoon as t; so t = y = 11.” becomes “Define Inst as a; so a = 0. Define Inst as b; so b = a = 0.” We use birthday paradox to estimate the number of solution templates. If M M randomly generated problems yield distinct templates, it suggests with good probability that the total number of templates exceeds Ω ( M 2 ) \Omega(M^{2}) .
No data contamination. A goal in synthetic math data generation is to prevent data contamination in internet-based math datasets, as noted in [ 22 ] . While it may be impossible to certify that models trained on internet data are free from contamination , in our setting, we can certify this : 1. We perform OOD evaluation such as on op ≥ 28 \textsf{op}\geq 28 while providing only op ≤ 21 \textsf{op}\leq 21 training samples.
2. We train with data whose hash value of solution template (see Footnote 11 ) is < 17 ( mod 23 ) <17\pmod{23} , and test with those ≥ 17 \geq 17 . This ensures no template-level overlap between training and testing .
## 3 Result 2-3: Summarize Model’s Behavior Process
We use the GPT2 architecture [ 18 ] but replacing its absolute positional embedding with rotary embedding [ 20 , 7 ] , yet still referring to it as GPT2 for short. 12 12 12 We also tested with Llama architecture (esp. with gated MLP layers) and did not see any benefit of using it. GPT2-rotary performs no worse than Llama/Mistral for knowledge tasks [ 4 ] . We are currently bounded by resources to repeat all experiments in this paper with other architectures that have minor differences from GPT2-rotary. We mostly stick to the 12-layer, 12-head, 768-dim GPT2 (a.k.a. GPT2-small) for experiments, but we explore larger models in Section 6 . We use a context length of 768 / 1024 for pretraining on iGSM-med / iGSM-hard \textsf{iGSM-med}/\textsf{iGSM-hard} and 2048 for evaluation. More details are in Appendix F .
Result 2: accuracy. After sufficient pre-training, we give the model a problem from the test set (without solution) and let it continue to generate (allegedly a solution followed by an answer). Because we have restricted ourselves to a fixed solution format, language models can learn the format easily, allowing us to write a solution parser to check if the solution is fully correct. 13 13 13 We check not only the correctness of the final answer 0..22 but also the calculations and parameter dependencies. Language models can learn very complex syntactics, see [ 1 ] and the references therein. Result 2 . Figure 3 shows that GPT2 performs well when pretrained using iGSM-med or iGSM-hard data, even when evaluated out-of-distribution on harder (i.e., larger op ) math problems. Thus, the model can truly learn some reasoning skill instead of memorizing solution templates. 14 14 14 Llama (of the same model size) gives similar performance, but we refrain from repeating all the experiments with another model. We are not interested in small model differences in this theoretical study; instead, we care more about the general behavior of (autoregressive) language models. This could be reminiscent of language models’ length generalization capability on arithmetic computations [ 23 , 13 ] ; however, in our case, op captures the “reasoning length” in grade-school math, and our model has never seen any training example of the same length as in test time. 15 15 15 Some others such as Anil et al. [6] start with a transformer pre-trained on internet data; while the transformer may not have seen the same task during training, it’s possible that the model has seen other tasks with the same (or even longer) length and learned to transfer from there.
Such accuracies also indicate that our iGSM data families are indeed good for pretraining purpose, allowing us to investigate how LLMs can solve grade-school math problems.
Result 3: solution redundancy. We examine whether GPT2 achieves high accuracy by • brute-forcedly computing all the parameters during generation (a “level-0” reasoning skill), or
• computing only necessary parameters to give shortest solutions (a “level-1” reasoning skill).
Recall our iGSM (pretrain) data only contains necessary solution steps (i.e., CoT) to simulate what we see in textbook solutions for math problems. For instance, if a problem describes X =3+2, E =3+X, Y =X+2 and asks for the value of Y, then a shortest solution would be “X =3+2=5 and Y =X+2 =7” without ever computing E.
Result 3 . Figure 4 shows that GPT2 predominantly solves the iGSM problems with a “level-1” reasoning skill, avoiding unnecessary computations, even when evaluated out-of-distribution. This finding is significant as it suggests that, unlike humans who usually rely on “backward reasoning” and a scratch pad to write down necessary parameters by backtracking the dependencies from the question [ 19 ] , the language model can directly generate shortest solutions without using a scratch pad. But, how does it achieve so? We shall investigate in the next section.
## 4 Result 4-5: Discover Model’s Mental Process
To understand how the model learns to solve math problems, we propose studying the following probing tasks, which align closely with human problem-solving strategies: • nece ( A ) \texttt{nece}(A) : if parameter A A is necessary for computing the answer.
• dep ( A , B ) \texttt{dep}(A,B) : if parameter A A (recursively) depends on parameter B B given the problem statement.
• known ( A ) \texttt{known}(A) : if parameter A A has already been computed.
• value ( A ) \texttt{value}(A) : the value of parameter A A (a number between 0-22, or 23 if known ( A ) = false \texttt{known}(A)=\mathrm{false} ).
• can_next ( A ) \texttt{can\_next}(A) : if A A can be computed in the next solution sentence (namely, its predecessors have all been calculated). Note that A A might not be necessary to answer the question.
• nece_next ( A ) \texttt{nece\_next}(A) : if parameter A A satisfies both can_next ( A ) \texttt{can\_next}(A) and nece ( A ) \texttt{nece}(A) .
For a model to generate the shortest solutions, it must identify nece ( A ) \texttt{nece}(A) for all A A ’s in its mental process. This is because whether nece ( A ) \texttt{nece}(A) is true directly corresponds to whether there is a solution sentence to compute A A . However, how early does the model recognize this, and how is it stored? Similarly, does it recognize dependencies between parameters ( dep )? If so, how early is this mental process completed? Moreover, in the middle of solution generation , does the model keep track of each parameter A A ’s value at all times ( value , known )? Does the model mentally know all possible parameters A A that are ready to compute in the next sentence ( can_next )? Or does it only focus on A A that is both ready and necessary ( nece_next )?
This section proposes probing technique to answer all of these questions.
### 4.1 V-Probing: A Nearly-Linear Probing Method
As illustrated in Figure 5 , we conduct probing at the end of the problem description for the dep task, and end of the question description nece task. 16 16 16 If the problem format is qp (question asked before the problem) then we probe nece and dep both after the problem description. For other tasks, we probe them at the end of every solution sentence (including the start of the first solution sentence).
Recall that standard linear probing involves freezing a pretrained language model and checking if a property is linearly encoded at a hidden layer (usually the last layer) for a given token position. This is done by introducing a trainable linear classifier on the hidden states and performing a lightweight finetuning task for this property (see [ 12 ] and references therein).
Our setting is more complex because the properties have one or two conditional variables, A A and B B , described in plain English. To handle this, we truncate the math problems to the probing position and append tokens [START] and [END] around the descriptions of A A (or A , B A,B ). We then probe from the token position of [END] to see if the property is linearly encoded at the last layer.