Physics of Language Models: Part 2.1, Grade-School Math and the Hidden Reasoning Process — part 4/6
Cleaned-text code points [46416, 61120). Bibliography omitted here; source.md includes it.
Note, if it were only a trainable linear head such probing would be called linear probing [ 12 ] . Unlike traditional linear probing, we are adding a small low-rank update on the model’s embedding layer. This is arguably the minimum change needed (to account for the task change, for special tokens like [START] [MID] [END] , etc.) in order to perform any non-trivial probing. This is related but different from the nearly-linear probing methods introduced in Allen-Zhu and Li [1] , Allen-Zhu and Li [3] , because they do not support taking variables as probing inputs. 21 21 21 In Allen-Zhu and Li [1] , Allen-Zhu and Li [3] , the authors are interested in probing the model’s behavior via fixed classification tasks (such as a 100-class classification task) given data that are identical or nearly-identical to the pretrain data. In this paper, we are interested in the model’s behavior with respect to given variables (such as parameter names, which can have ∼ 100 k \sim 100k possibilities); and we append such variable names to the input to make the training inputs appear very different from the original pretrain data.
Unbalanced probing tasks. Our probing accuracies for the six tasks were presented in Figure 7 . However, we notice that the dep and nece_next tasks have unbalanced labels — even guessing “all false \mathrm{false} ” would give 83% accuracy for dep ( A , B ) \texttt{dep}(A,B) and 92 % 92\% for nece_next ( A ) \texttt{nece\_next}(A) . For such reason, we also present their probing accuracies restricted to positives/negatives labels separately in Figure 12 .
## Appendix C Result 8 — Additional Figure
## Appendix D Result 1 Details — Math Data Generation
Our math data generation process consists of first generating the structure graph (see Figure 1 and 11 left), which defines the set of parameters we shall use; then generating the dependency graph (see Figure 1 and 11 right), which defines the arithmetic relationship between the parameters; and finally generating the English problem and solution descriptions.
Notations. In this section, to make the description concise, when we say “randomly sampling” in the pseudocode, we mean uniform random unless otherwise noted. Whenever we consider a (directed) graph G G , slightly abusing notation, we write a ∈ G a\in G to indicate that a a is a vertex in G G and ( a → b ) ∈ 𝖦 (a\to b)\in{\mathsf{G}} to indicate that there is an edge from a a to b b in G G .
### D.1 Generate Structure Graph
Recall the structure graph (see Figure 1 and 11 left) describes the set of possible items (nodes) and instance parameter (edges) that we shall rely on to construct our math problem.
We use G 𝗌 G_{\mathsf{s}} to denote such structure graph, and it is generated G 𝗌 = DrawStructure ( e , d , w 0 , w 1 ) G_{\mathsf{s}}=\mathtt{\hyperref@@ii[alg:structure-graph]{DrawStructure}}(e,d,w_{0},w_{1}) from a random distribution defined with hyperparameters e , d , w 0 , w 1 ∈ ℕ e,d,w_{0},w_{1}\in\mathbb{N} . At a high level, we construct G 𝗌 G_{\mathsf{s}} so that it has d d layers, e e edges, and each layer has between w 0 w_{0} and w 1 w_{1} items.
Specifically, suppose l i ∈ { w 0 , w 0 + 1 , … , w 1 } l_{i}\in\{w_{0},w_{0}+1,\dots,w_{1}\} represents the number of items for each layer i i . In this configuration, one must have at least e − = l 2 + ⋯ + l d e^{-}=l_{2}+\cdots+l_{d} edges to ensure the graph is “connected”, and at most e + = l 1 l 2 + ⋯ + l d − 1 l d e^{+}=l_{1}l_{2}+\cdots+l_{d-1}l_{d} edges. Using this formula, we first randomly choose a configuration ( l 1 , … , l d ) (l_{1},\dots,l_{d}) so that e − ≤ e ≤ e + e^{-}\leq e\leq e^{+} for the given parameter e e . Then, after the configuration is chosen, we randomly generate edges accordingly. Details are given in Algorithm 1 .
#### D.1.1 Attach English
As described in Section 2.1 , we have prepared 4 predefined hierarchical categorizations, each of them with 4 total layers of categories: ⬇
In each of the above 16 categories, we have prepared around 100 items (further decomposed into 5 sub-categories). Below is a showcase of them:
Now, given a constructed structure graph G 𝗌 G_{\mathsf{s}} , we first randomly pick one of the four categorizations, then randomly pick d ∈ { 2 , 3 , 4 } d\in\{2,3,4\} consecutive layers of categories, next randomly pick one of the five subcategories, and finally pick l i l_{i} random item names in this subcategory for each layer i i .
At this point, we have constructed G 𝗌 G_{\mathsf{s}} as well as added English names to each of its node, just like Figure 1 and 11 (left).
### D.2 Generate Dependency Graph
A structure graph G 𝗌 G_{\mathsf{s}} defines the set of possible parameters we consider, while a dependency graph defines how these parameters depend on each other. We use an edge a → b a\to b to indicate that parameter b b depends on a a ; there is a special vertex 𝖱𝖭𝖦 \mathsf{RNG} and it can happen that 𝖱𝖭𝖦 → b \mathsf{RNG}\to b . What an abstract parameter depends on is inherited from the structure graph G 𝗌 G_{\mathsf{s}} . For each instance parameter, we shall randomly add edges to indicate what parameters it depends on.
High-level plan. We shall use G 𝖽 G_{\mathsf{d}} to denote the dependency graph, we start from an empty graph and then add vertices/edges incrementally and randomly. Our process is as follows: • Generate a necessary dependency graph G 𝖽 𝗇𝖾𝖼𝖾 G_{\mathsf{d}}^{\mathsf{nece}} which covers all the vertices and nodes that are necessary for the computation of the query parameter. – Generate necessary abstract parameters (and add parameters they depend on); call this graph G 𝖽 𝗇𝖾𝖼𝖾𝟣 G_{\mathsf{d}}^{\mathsf{nece1}} .
– Generate necessary instance parameters and add them to G 𝖽 𝗇𝖾𝖼𝖾𝟣 G_{\mathsf{d}}^{\mathsf{nece1}} ; call this graph G 𝖽 𝗇𝖾𝖼𝖾𝟤 G_{\mathsf{d}}^{\mathsf{nece2}} .
– Generate a topological order for parameters G 𝖽 𝗇𝖾𝖼𝖾𝟤 G_{\mathsf{d}}^{\mathsf{nece2}} and ensure all of them are necessary towards computing the query parameter (which is the last one in this tropologic order). During this process, we shall add additional edges from G 𝖽 𝗇𝖾𝖼𝖾𝟤 G_{\mathsf{d}}^{\mathsf{nece2}} to create G 𝖽 𝗇𝖾𝖼𝖾𝟥 G_{\mathsf{d}}^{\mathsf{nece3}} .
– Generate additional necessary edges and add them to G 𝖽 𝗇𝖾𝖼𝖾𝟥 G_{\mathsf{d}}^{\mathsf{nece3}} ; call this graph G 𝖽 𝗇𝖾𝖼𝖾 G_{\mathsf{d}}^{\mathsf{nece}} .
• Add to G 𝖽 𝗇𝖾𝖼𝖾 G_{\mathsf{d}}^{\mathsf{nece}} all the remaining (unnecessary) parameters and edges to form G 𝖽 G_{\mathsf{d}} .
At a high level, our problem description shall solely depend on G 𝖽 G_{\mathsf{d}} — by describing each instance parameter in it using a sentence, and our solution description shall solely depend on G 𝖽 𝗇𝖾𝖼𝖾 G_{\mathsf{d}}^{\mathsf{nece}} — by describing the computation of each parameter in it using a sentence.
Before we proceed with the construction let us formally introduce:
###### Definition D.1 (operation) .
Given any dependency graph G 𝖽 G_{\mathsf{d}} , • For an (abstract or instance) parameter a ∈ G 𝖽 a\in G_{\mathsf{d}} that has in-degree t ≥ 0 t\geq 0 , we define 𝗈𝗉 G 𝖽 ( a ) = def max { 1 , t − 1 } \mathsf{op}_{G_{\mathsf{d}}}(a)\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle def}}}{{=}}\max\{1,t-1\} which is the number of operations needed to compute a a . 22 22 22 For instance, in Figure 1 , a = “Riverview High’s total number of Backpacks” a=\text{``Riverview High's total number of Backpacks''} is equal to i p 1 × a p 1 + i p 2 × a p 2 ip_{1}\times ap_{1}+ip_{2}\times ap_{2} for i p 1 = “Riverview High’s number of Dance Studios” ip_{1}=\textrm{``Riverview High's number of Dance Studios''} , i p 2 = “Riverview High’s number of Film Studios” ip_{2}=\textrm{``Riverview High's number of Film Studios''} , a p 1 = “each Dance Studio’s number of Backpacks” ap_{1}=\textrm{``each Dance Studio's number of Backpacks''} , a p 2 = “each Film Studio’ number of Backpacks” ap_{2}=\textrm{``each Film Studio' number of Backpacks''} , where i p 1 , i p 2 ip_{1},ip_{2} are instance parameters and a p 1 , a p 2 ap_{1},ap_{2} are abstract parameters. In this case, this abstract parameter depends on 4 other parameters, and requires 3 arithmetic operations.
• We use 𝗈𝗉 ( G 𝖽 ) = def ∑ a ∈ G 𝖽 ∖ { 𝖱𝖭𝖦 } 𝗈𝗉 G 𝖽 ( a ) \mathsf{op}(G_{\mathsf{d}})\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle def}}}{{=}}\sum_{a\in G_{\mathsf{d}}\setminus\{\mathsf{RNG}\}}\mathsf{op}_{G_{\mathsf{d}}}(a) to denote the total number of (arithmetic) operations needed to compute all the parameters in G 𝖽 G_{\mathsf{d}} .
###### Remark D.2 .
In our final design of G 𝖽 G_{\mathsf{d}} , we shall ensure that each parameter (except the special vertex 𝖱𝖭𝖦 \mathsf{RNG} ) has in-degree at least 1 1 ; however, during the construction process since we add edges incrementally, some (instance) parameter may temporarily have in-degree 0 0 . For notation simplicity, we still say 𝗈𝗉 G 𝖽 ( a ) = max { 1 , − 1 } = 1 \mathsf{op}_{G_{\mathsf{d}}}(a)=\max\{1,-1\}=1 in such a case.
Hyperparameters. We use hyperparameters 1 ≤ n ≤ m ≤ s 1\leq n\leq m\leq s to control the difficulty of G 𝖽 G_{\mathsf{d}} . • we shall ensure 𝗈𝗉 ( G 𝖽 𝗇𝖾𝖼𝖾𝟣 ) ≤ n \mathsf{op}(G_{\mathsf{d}}^{\mathsf{nece1}})\leq n and is as close as possible to n n ;
• we shall ensure 𝗈𝗉 ( G 𝖽 𝗇𝖾𝖼𝖾𝟥 ) = 𝗈𝗉 ( G 𝖽 𝗇𝖾𝖼𝖾𝟤 ) ≤ m \mathsf{op}(G_{\mathsf{d}}^{\mathsf{nece3}})=\mathsf{op}(G_{\mathsf{d}}^{\mathsf{nece2}})\leq m and is as close as possible to m m ;
• we shall ensure 𝗈𝗉 ( G 𝖽 𝗇𝖾𝖼𝖾 ) = s \mathsf{op}(G_{\mathsf{d}}^{\mathsf{nece}})=s is exact.
In other words, hyperparameter s s controls exactly how many operations are needed to compute the query parameter, which is the primary factor controlling the problem’s difficulty.
#### D.2.1 Construction of G 𝖽 𝗇𝖾𝖼𝖾𝟣 , G 𝖽 𝗇𝖾𝖼𝖾𝟤 G_{\mathsf{d}}^{\mathsf{nece1}},G_{\mathsf{d}}^{\mathsf{nece2}}
Given a structure graph G 𝗌 G_{\mathsf{s}} , recall its edges represent all the instance parameters we shall use. Its abstract parameters are those ones that describe quantities across 1 or multiple layers: for instance in Figure 1 , Central High ’s number of Classrooms is across 1 layer, and Central High ’s number of Backpacks is across 2 layers. We define this number as the difficulty level of abstract parameters.
With this notion, our construction of G 𝖽 𝗇𝖾𝖼𝖾𝟣 G_{\mathsf{d}}^{\mathsf{nece1}} and G 𝖽 𝗇𝖾𝖼𝖾𝟤 G_{\mathsf{d}}^{\mathsf{nece2}} are described together in Algorithm 2 .
At a high level, we try to incrementally and randomly add abstract parameters to G 𝖽 𝗇𝖾𝖼𝖾𝟣 G_{\mathsf{d}}^{\mathsf{nece1}} while maintaining 𝗈𝗉 ( G 𝖽 𝗇𝖾𝖼𝖾𝟣 ) ≤ n \mathsf{op}(G_{\mathsf{d}}^{\mathsf{nece1}})\leq n . We cannot make this exact equality because when adding a single abstract parameter requires also (recursively) adding all the other parameters it may depend on. We tried to prioritize adding abstract parameters with higher difficulty levels. Once we finish constructing G 𝖽 𝗇𝖾𝖼𝖾𝟣 G_{\mathsf{d}}^{\mathsf{nece1}} , we randomly add additional instance parameters from G 𝗌 G_{\mathsf{s}} to make it G 𝖽 𝗇𝖾𝖼𝖾𝟤 G_{\mathsf{d}}^{\mathsf{nece2}} .
#### D.2.2 Construction of G 𝖽 𝗇𝖾𝖼𝖾𝟥 G_{\mathsf{d}}^{\mathsf{nece3}}
Our goal next is to select a random 𝚚𝚞𝚎𝚛𝚢 \mathtt{query} parameter in G 𝖽 𝗇𝖾𝖼𝖾𝟤 G_{\mathsf{d}}^{\mathsf{nece2}} and construct a random topological ordering 𝚃𝚘𝚙𝚘 \mathtt{Topo} for all the parameters in G 𝖽 𝗇𝖾𝖼𝖾𝟤 G_{\mathsf{d}}^{\mathsf{nece2}} , so as to ensure that all the parameters are necessary towards the computation of 𝚚𝚞𝚎𝚛𝚢 \mathtt{query} .
We start with 𝚃𝚘𝚙𝚘 = [ 𝚚𝚞𝚎𝚛𝚢 ] \mathtt{Topo}=[\mathtt{query}] and append parameters to its left one by one. During this process, we may also introduce new edges randomly; we start with G 𝖽 𝗇𝖾𝖼𝖾𝟥 = G 𝖽 𝗇𝖾𝖼𝖾𝟤 G_{\mathsf{d}}^{\mathsf{nece3}}=G_{\mathsf{d}}^{\mathsf{nece2}} and add edges incrementally. This process may not always succeed — sometimes the created topological ordering cannot make all the parameters necessary towards the computation of the 𝚚𝚞𝚎𝚛𝚢 \mathtt{query} . If this happens we declare a failure. 23 23 23 The outside pseudocode, which comes later, shall go back to regenerate the structure graph and start again.
We introduce two notions (we use G 𝖽 𝗇𝖾𝖼𝖾𝟥 ∖ 𝚃𝚘𝚙𝚘 G_{\mathsf{d}}^{\mathsf{nece3}}\setminus\mathtt{Topo} to denote the set of vertices in G 𝖽 𝗇𝖾𝖼𝖾𝟥 G_{\mathsf{d}}^{\mathsf{nece3}} that are not in 𝚃𝚘𝚙𝚘 \mathtt{Topo} ): • 𝖭𝖾𝗑𝗍𝟣 G 𝖽 𝗇𝖾𝖼𝖾𝟥 ( 𝚃𝚘𝚙𝚘 ) = def { a ∈ G 𝖽 𝗇𝖾𝖼𝖾𝟥 ∖ 𝚃𝚘𝚙𝚘 ∣ ∃ ( a → b ) ∈ G 𝖽 𝗇𝖾𝖼𝖾𝟥 for some b ∈ 𝚃𝚘𝚙𝚘 } \mathsf{Next1}_{G_{\mathsf{d}}^{\mathsf{nece3}}}(\mathtt{Topo})\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle def}}}{{=}}\big\{a\in G_{\mathsf{d}}^{\mathsf{nece3}}\setminus\mathtt{Topo}\mid\exists(a\to b)\in G_{\mathsf{d}}^{\mathsf{nece3}}\text{ for some $b\in\mathtt{Topo}$}\big\}
Intuitively, if a ∉ 𝖭𝖾𝗑𝗍𝟣 ( 𝚃𝚘𝚙𝚘 ) a\not\in\mathsf{Next1}(\mathtt{Topo}) then we cannot immediately append a a to the front of 𝚃𝚘𝚙𝚘 \mathtt{Topo} , because it is not yet necessary towards the computation of 𝚚𝚞𝚎𝚛𝚢 \mathtt{query} .
• 𝖭𝖾𝗑𝗍𝟤 G 𝖽 𝗇𝖾𝖼𝖾𝟥 ( 𝚃𝚘𝚙𝚘 ) = def { a ∈ G 𝖽 𝗇𝖾𝖼𝖾𝟥 ∖ 𝚃𝚘𝚙𝚘 ∣ ∄ ( a → b ) ∈ G 𝖽 𝗇𝖾𝖼𝖾𝟥 for any b ∈ G 𝖽 𝗇𝖾𝖼𝖾𝟥 ∖ 𝚃𝚘𝚙𝚘 } \mathsf{Next2}_{G_{\mathsf{d}}^{\mathsf{nece3}}}(\mathtt{Topo})\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle def}}}{{=}}\big\{a\in G_{\mathsf{d}}^{\mathsf{nece3}}\setminus\mathtt{Topo}\mid\nexists(a\to b)\in G_{\mathsf{d}}^{\mathsf{nece3}}\text{ for any $b\in G_{\mathsf{d}}^{\mathsf{nece3}}\setminus\mathtt{Topo}$}\big\} Intuitively, if a ∉ 𝖭𝖾𝗑𝗍𝟤 G 𝖽 𝗇𝖾𝖼𝖾𝟥 ( 𝚃𝚘𝚙𝚘 ) a\not\in\mathsf{Next2}_{G_{\mathsf{d}}^{\mathsf{nece3}}}(\mathtt{Topo}) then we cannot immediately append a a to the front of 𝚃𝚘𝚙𝚘 \mathtt{Topo} , because some other parameter depends on it and is not yet added to 𝚃𝚘𝚙𝚘 \mathtt{Topo} . (Obviously we always have 𝖭𝖾𝗑𝗍𝟤 G 𝖽 𝗇𝖾𝖼𝖾𝟥 ( 𝚃𝚘𝚙𝚘 ) ≠ ∅ \mathsf{Next2}_{G_{\mathsf{d}}^{\mathsf{nece3}}}(\mathtt{Topo})\neq\varnothing unless G 𝖽 𝗇𝖾𝖼𝖾𝟥 ∖ 𝚃𝚘𝚙𝚘 = ∅ G_{\mathsf{d}}^{\mathsf{nece3}}\setminus\mathtt{Topo}=\varnothing so we are done.)
Our generation algorithm is now easy to describe: we keep adding parameters that are in 𝖭𝖾𝗑𝗍𝟣 G 𝖽 𝗇𝖾𝖼𝖾𝟥 ( 𝚃𝚘𝚙𝚘 ) ∩ 𝖭𝖾𝗑𝗍𝟤 G 𝖽 𝗇𝖾𝖼𝖾𝟥 ( 𝚃𝚘𝚙𝚘 ) \mathsf{Next1}_{G_{\mathsf{d}}^{\mathsf{nece3}}}(\mathtt{Topo})\cap\mathsf{Next2}_{G_{\mathsf{d}}^{\mathsf{nece3}}}(\mathtt{Topo}) to the front of 𝚃𝚘𝚙𝚘 \mathtt{Topo} ; and if we get stuck, we introduce new edges to G 𝖽 𝗇𝖾𝖼𝖾𝟥 G_{\mathsf{d}}^{\mathsf{nece3}} (or declare failure). The pseudocode is in Algorithm 3 .
###### Proposition D.3 .
Every instance parameter in G 𝖽 𝗇𝖾𝖼𝖾𝟥 G_{\mathsf{d}}^{\mathsf{nece3}} has in-degree ≤ 1 \leq 1 and thus 𝗈𝗉 ( G 𝖽 𝗇𝖾𝖼𝖾𝟥 ) = 𝗈𝗉 ( G 𝖽 𝗇𝖾𝖼𝖾𝟤 ) \mathsf{op}(G_{\mathsf{d}}^{\mathsf{nece3}})=\mathsf{op}(G_{\mathsf{d}}^{\mathsf{nece2}}) .
###### Remark D.4 .