Why think step by step? Reasoning emerges from the locality of experience
Authors: Ben Prystawski
Michael Y. Li
Noah Goodman
Venue: NeurIPS 2023 oral (2023)
Keywords: chain-of-thought; language models; reasoning
TL;DR: Chain-of-thought reasoning is effective in autoregressive language models because of the local structure of the training data.

Abstract: Humans have a powerful and mysterious capacity to reason. Working through a set of mental steps enables us to make inferences we would not be capable of making directly even though we get no additional data from the world. Similarly, when large language models generate intermediate steps (a chain of thought) before answering a question, they often produce better answers than they would directly. We investigate why and how chain-of-thought reasoning is useful in language models, testing the hypothesis that reasoning is effective when training data consists of overlapping local clusters of variables that influence each other strongly. These training conditions enable the chaining of accurate local inferences to estimate relationships between variables that were not seen together in training. We prove that there will exist a "reasoning gap", where reasoning through intermediate variables reduces bias, for the simple case of an autoregressive density estimator trained on local samples from a chain-structured probabilistic model. We then test our hypothesis experimentally in more complex models, training an autoregressive language model on samples from Bayes nets but only including a subset of variables in each sample. We test language models’ ability to match conditional probabilities with and without intermediate reasoning steps, finding that intermediate steps are only helpful when the training data is locally structured with respect to dependencies between variables. The combination of locally structured observations and reasoning is much more data-efficient than training on all variables. Our results illustrate how the effectiveness of reasoning step by step is rooted in the local statistical structure of the training data.

Why think step by step? Reasoning emerges from the locality of experience
Ben Prystawski
Michael Y.
Department of Psychology Stanford University Stanford, CA 94305
Department of Computer Science
Stanford University Stanford, CA 94305
benpry@stanford edu
mi chaecylllll yyl iesttnn edu
Noah D. Goodman
Departments of Psychology and Computer Science Stanford University Stanford, CA 94305
agoodman@staanoorddoo
Abstract
Humans have a powerful and mysterious capacity to reason. Working through a set of mental steps enables us make inferences we would not be capable of making directly even though we get no additional data from the world. Similarly, when large language models generate intermediate steps (a chain of thought) before an- swering question, they often produce better answers than they would directly. We investigate why and how chain-of- -ff-thuugttttttttt reasoning is useful in language models, testing the hypothesis that reasoning is effective when training data consists of over- lapping local clusters of variables that influence each other strongly. These training conditions enable the chaining of accurate local inferences to estimate relationships between variables that were not seen together in training. We prove that there will exist "reasoning gap", where reasoning through intermediate variables reduces bias, for the simple case an autoregressive density estimator trained on local samples from a chain-structuree probabilistic model. We then test our hypothesis experimentally in more complex models, training an autoregressive language model samples from Bayes nets but only including subset of variables in each sample. We test language models' ability to match conditional probabilities with and with- out intermediate reasoning steps, finding that intermediate steps are only helpful when the training data is locally structured with respect to dependencies between variables. The combination of locally structured observations and reasoning is much more data-efficient than training on all variables. Our results illustrate how the effectiveness of reasoning step by step is rooted in the local statistical structure of the training data.
Introduction
The human mind is a ship - the immediate inferences we make from instinct keep us afloat, but reason is the compass that brings immediately solving math problems, planning vacations, understanding our relatives become much casier when we talk ourselves through reflective reasoning process. Likewise, by considering thought experiments or "intuition pumps" in science we can form strong beliefs such as that the rate at which an object falls should not depend its mass purely by thinking through set of steps
the shore of wisdom. Many tasks that we find hard to do
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

[2 It is not a priori obvious that step-by-step reasoning should be helpful. Reasoning does not give us any new data from the world, yet it can still improve our inferences. In investigating the origins of reasoning, we must thus ask, why does reasoning help at all?
Large language models have been shown capable of performing wide variety of tasks by immediately answering a question [3-6]. However, they struggle with some complex tasks like math word problems 77. A recent line of work has demonstrated that inducing language models to produce a "chain of thought" consisting of intermediate steps toward a solution, before giving an answer, leads to better performance than prompting them to produce an answer directly [1. Other work has built on these findings, showing that providing worked solutions in context is helpful across a broad array of tasks [2] and proposing methods augment language models' reasoning performance 16). These findings raise an important question: why is chain-of-thougeee reasoning useful? Exploring this question in language models may also provide insight into the origins of human reasoning.
We hypothesize that thain-of-though reasoning is useful in language models due to local structure in the training data. Human experience governed by our first-person perspective: we see and hear aspects of the world that are near to us in time and space. Yet our reasoning transcends these local bounds, supporting plans and conclusions that span distance and years. Similarly, language models are trained on documents in natural language, which are usually about a few closely interconnected When concepts co-occur frequently in experience or training data, estimating the effect of one on the other is easy to do directly with simple statistical estimators. However, when we need infer the effect of one piece of information on another but have not encountered them together, we must make a series of inferences that jump between pairs of concepts to connect what we reasoning becomes useful exactly
topics [17 18
know with what we want to infer. We posit that when the training data is structured locally, in the sense that observations tend to occur in partially overlapping neighborhoods of related concepts.
To illustrate, we may know the value of some variable A and want to know about another variable C. so we try to estimate P(C]A). However, if we need to estimate probabilities using observed samples from joint distributions and we have not often seen A and C' together. we would struggle to estimate P(CIA) directly. Instead, we might estimate it by reasoning through intermediate variables. If conditioning on an intermediate variable B renders A and C' independent of each other, we can compute the conditional probability by marginalizing over B, using the fact that P(CIA)= = Eg P(C (B)A). For an example in natural language, suppose that we want to answer question like "What is the climate of France's 's capital?" using a model trained on text from Wikipedia. Wikipedia pages for cities usually have information about the city's climate and Wikipedia pages for countries have information about capital cities, but pages for countries typically do not directly mention the climate of the capital city. It is possible that our model could succeed in answering the question directly, but would likely have more success if took the intermediate step of stating the capital of France. By introducing the step "the capital of France is Paris" before answering "Paris has an oceanic climate," an autoregressive model can better leverage the dependencies that are well-represented in its training data.
Our hypothesis is similar to that advanced by Chan et al. 19 to explain why in-context learning occurs (generalizing from examples shown in context). They show that "burstiness," the tendency of instances of class to occur close together, in the training data is important for language models to learn to infer tasks based on examples in the context window. Burstiness and locality are two different statistical properties of training data that could arise from topic structures in language models or from first-person perspective in humans. While burstiness concerns how a class is distributed over time, locality concerns which classes co-occur together. In datasets with local structure, concepts that strongly influence each other are also seen together frequently in the training set, whereas concepts that do not are seen together less frequently.
In this work, we investigate the properties of a model's 's training data that make generating intermediate variables useful for inference. We first formalize the problem mathematically and prove that reasoning through the right intermediate variables reduces bias in a model trained on local samples from a chain. We then train autoregressive transformers from scratch on synthetic data with different structures and evaluate the models' ability to match conditional probabilities for pairs of variables that were not observed together in training. Generating values for relevant intermediate variables enables models to match conditional probabilities more accurately, but only when the training data is locally structured. Allowing the model to select intermediate variables to reason through is similarly helpful to giving it
2

---

A
XI
XB
B
Training samples
X9
X7
(x1,000,000) ###
target: X16
XI
X12=0
X4=1
X11=1
X1+
X4
X16=0
Estimator
direct prediction
C
fize generation
#ed prediction larget: x5
Train condition
X12-0
Xt*
fully observed
local (goen)
4Ma free generation
X11=1
the reasoning gap
X3-0
X10+1
236405
sac-es Number tokens
X5
Figure Overview of our training and estimation setup. A: visualization of Bayes net. The pink variable is an example observed variable and the yellow variable is an example target variable. Gray variables are examples of useful intermediate variables for reasoning. Lines show examples of local neighborhoods from which training samples are drawn. B: format of the training samples. C: illustration of direct prediction and free generation estimators as prompts. We prompt the model to either immediately predict the target variable (direct prediction) or do so after generating intermediate variables and their values (free generation). We then compute mean squared errors between the estimated and true conditional probabilities. D: mean squared error by number of training tokens for each training condition and estimator. Ribbons indicate 95% confidence intervals.
the ideal intermediate variables to reason through. Our results suggest that chain-of-thougg reasoning useful for language models because 1) direct prediction is inaccurate for some inferences because the relevant variables are rarely seen together in training and 2) chain-of-thought reasoning improves estimation by incrementally chaining local statistical dependencies that are observed frequently in training. We also find that the combination of locally structured training data and reasoning with self-gent geffeeerrrted intermediate variables yields much greater data efficiency than training data containing all variables.
2
Task setup
Our theory and experiments take place in the context of conditional inference in joint distributions, as represented by Bayesian networks. In our framing, a learner sees samples from Bayes net and needs to accurately estimate conditional probabilities. However, the learner may not see all variables together, having access only to locally-structured observations instead.
We describe our framework formally. First, we assume there is some underlying Bayes net with random variables {Y:) taking support on a finite set X. We denote the distribution defined by the Bayes net as Pa, the data distribution. Our training data is sequence of variable indices i (I.... N) and variable values in E X. Variable values always follow variable indices.
2.1 Observation distribution
We create local structure in our task via an observation distribution Pobs, which is a distribution over subsets of the variable indices. Observation distributions take support on a set Voess S As consequence, our learner will only see samples from the joint distribution over certain subsets of random variables in the Bayes net. The generative process for our sequence consists of two steps. First, we sample set of variable indices ( according to Pabs These indices correspond to some set of random variables (Y, 1 in the Bayes net, which appear in random order in training. We
3

---

then sample the values {v,, | corresponding to the variable indices according to the distribution Pa(Y.,..... Yix) Together, Pa and Pobs define distribution p on training sequences.
We are particularly interested in local observation distributions as they enable models to learn strong dependencies and reflect some of the statistical structure of human experience. In local observation distributions, the learner observes a subset of variables that are close together in the Bayes net graph. Figure D shows several local neighborhoods in an example Bayes net.
2.2 Estimators
Given an autoregressive conditional probability estimation model that is trained to predict variable indices and values, we can use one of three different estimators for the conditional probabilities. The estimators differ in how a sequence of variables and values is produced before estimating the target variable. If we want to compute the conditional probability of a target variable Y, taking some value y/ given that we have observed variable Yj to be Mj, we can use one of the following estimators.
Direct prediction The direct prediction estimator is the baseline without any reasoning: the probability directly output by q-
(Y, y: Y, -,,) = ,Y, V v₁)
(1)
We simply use the model to directly estimate the conditional probability of the target variable.
Scaffolded generation The scaffolded generation estimator represents ideal reasoning if we know the best set of steps to work through. A scaffold is an ordered set S consisting of variables that were each observed together with the observed or target variable (or another scaffold variable) and collectively d-separate the observed variable from the target variable. In the case of a chain, the scaffold consists of all variables between Y; and Y, Variables are ordered by their distance from the observed variable in the Bayes net, increasing. We estimate each variable given the observed variable and previously generated scaffold variables using before estimating the target probability. We approximately marginalize over the scaffold variables' values using M Monte Carlo samples from the conditional distributions.
M
iY = y = yU) = M
Σ
q(x vill., = y 1 JoEs, Y, = -y))
(2)
where v/ qVv,/(Y, yi (k)
hesstt Y,= 4₁)
We will denote the distribution defined by the sampling procedure in 2 by qs.
Free generation The free generation estimator tests whether trained models spontaneously generate useful intermediate variables. It similar to scaffolded generation in that it generates intermediate variables before the target, but free generation uses the model to choose which variables to instantiate in addition to estimating their values. We simply sample variable indices and values from q until it generates the index of the target variable. At that point, we compute the probability of the target variable. We average over M such samples.
3 Theoretical results
In order to understand the range of situations in which reasoning might be useful, we study the condi- tions under which risk-minimizing sequence model benefits from reasoming through intermediate variables. We analyze simplified version of our task in which a model is trained on pairs of adjacent variables from a directed chain. In this setting, we prove that the minimizer of a risk consisting of cross entropy with entropy regularization exhibits a reasoning gap: the bias of direct conditional probability estimates between pairs of random variables that do not appear together is higher than indirect estimates that chain together conditional probabilities of intermediate random variables.
We assume that a risk minimizer q is trained on sequence of alternating variable indices i, (1...., N) and variable values Y, E X where the Y,'s take support in some finite set X. Variable values always follow variable indices. We assume that the joint distribution Pa over Yi, .2...., Yn

---

factorizes as Pa YN) Pa( Pa(Ye+1/V.). The observation distribution Pobs only assigns non-zero probability adjacent variable pairs. i.c. Pate(fi,j)) 0 if l -| and Pora (X) = if X * 2. The training set consists of i.i.d. samples from p. which is the distribution over complete sequences of variable indices and values defined by Pobs and pd-
We show that when our data has the locality structure as described, marginalizing over intermediate random variables using the learned conditional probabilities between adjacent variables leads to lower-bias estimates than using the learned estimate directly:
Theorem 3.1. Let S be the space of possible sequences consisting of variable indices followed by variable values. Let be the uniform distribution over S. Let H (p.9) q) denote the cross entropy between distributions and q. We consider the following risk:
R(g) = H(p,)) 1) + H(,
Let q" arg ming R(q) be a minimizer of the risk over all possible probability distributions. Then, for all non non-adjacent random variables Y; and y, reasoning through the intermediate variables has lower bias than direct prediction. That is, for any yr.9j 9j E X:
Egg [Y; (Y; = YY, = y,)l Pa(Y; = Yi Y, = =
< (0n = vulY, = uy) Pa(YY ya Y =);)1
Here, the expectation is over the randomness in the Monte Carlo samples of intermediate variables.
Proof sketch. We characterize 9* in terms of pa and u by analyzing the risk (Eq which decomposes into a sum of cross cross-entropy terms, either between q(-) and p(.) or between q(-) and t.
We consider two cases. For any adjacent pairs Y; and Y(+1, q" (Y++1 (Y)) will interpolate between the true conditional probability Pa(Y (Y.) and the uniform distribution. This is because the risk will con- tain term of the form - (Y -\)) (log (Y++)|X)) and a term of the form -E,, [og (Y [Y)]] The minimizer of the sum of these terms is mixture between Pa(Yi+al (+1 YY) and the uniform distribu- tion. On the other hand, for non -on-adjacent pairs Y; and Y,. (Y(,),))) = [ the observation distribution Pobs. Y, and Y, will never appear together. There will only be term of the form 1,, [log q(Y;)Y;)) in the risk. Therefore, minimizing the risk for Y, and Y, is equivalent to minimizing the entropy regularization term since the risk does not penalize q" (Y)(Y,) for not matching YY))
1. As a consequence of
Given q", we can calculate the bias of the scaffolded estimator Ωs. where we approximately marginal- ize out the intermediate random variables by sampling from the conditional probability distributions x" iY(Y+ilYY), Since these conditional distributions are mixture distributions, we can also show that the scaffolded estimator is mixture between p( ((Y))))) and with mixture weight À (0, 1). Therefore, 지 The second term in the product exactly the bias of the direct estimator and A)* < 1. The desired inequality immediately follows. Intuitively, the bias of the scaffolded estimator lower because it leverages the dependency structure of the data, chaining together local conditional probabilities of variables that appeared together in training to estimate conditional probabilities for unseen pairs.
its bias can be expressed as (1 - ({X
In practice, we find that density estimators tend to predict the marginal distributions for held-out pairs, ie., q (X, x p(X.). If we instead assume that the risk minimizer a mixture between the true conditional distributions and the marginal distributions, about the underlying data distribution. For further discussion, full details of the theorem, and proofs see Appendix A In the next section, explore whether the reasoning gap occurs in practice for transformer language models in situations with more complex dependency and observation structures.
can relax some assumptions
make
4 Experimental methods
We test the hypothesis that locally structured training data leads to reasoning gap by training a language model (i.e., an autoregressive density estimator with transformer architecture) and testing conditional inference accuracy. We manipulate the structure of the training data and measure the effectiveness of different estimators. The key question is whether there are training conditions under
5

---

which scaffolded or free generation outperfonms direct prediction. Code and data are available at https://githhu wtwp:/ww.....c..p../o.o.aaa.a coombbeprr//wyy-.. think- htwpaa----nninttt----------eeeee
As in our theoretical analysis, we are interested in understanding the bias of different estimators. In practice, we evaluate our estimators using Mean Squared Error (MSE), averaging over 10 Monte Carlo samples for estimators that include intermediate variables. Averaging over samples reduces variance, meaning that the remaining estimation error is primarily driven by bias.
4.1 Training data
The first step in generating our training data is to create Bayes nets. We generate a random topology for the networks, creating 100 variables and incrementally adding 100 random edges between pairs of variables. After generating a topology, we create conditional probability tables for each variable. We design the conditional probability tables and select among generated Bayes nets to create non-adjacent pairs of variables with high mutual information. The probability of a variable being 1 for each setting of its parents is randomly sampled from (eta( 5. 2). which favors moderately strong dependencies. If we did not favor strong dependencies, conditional probabilities would be very close to marginal probabilities for non non-adjace adjacent pairs of variables and a language model could come very close to matching true conditional probabilities without learning the relationships between variables. Strong dependencies are therefore an important precondition to the effectiveness of reasoning. We generate 100 Bayes nets according to this process, then compute the mutual information between each pair of variables. We select the 50 pairs of non-adjacent variables that have the highest mutual information, then randomly sample 25 of those pairs to hold out from the training set. Finally, we select the 10 Bayes nets, out of the initial 100, for which the 25 held-out pairs of variables have the highest mean mutual information. Pseudocode for Bayes net generation is shown in Algorithm of Appendix B
For each of the 10 selected Bayes nets, we generate a training set consisting of 1 million samples formatted as strings. The strings consist of the name of each variable followed by its value; variables are ordered randomly. Variable names are the letter 'X' followed by number from to 99. For example, if the variable 'X42' has value I, the string would include the line "X42=1". We mention the name of the last variable in the sample the beginning of the string and mark it with the word "target." We also include "###" before the sample to indicate where it begins. A schematic example of a formatted sample string is shown in Figure D and full example is shown in Appendix
Each sample includes only subset of all the variables in the Bayes net, chosen according to the observation distribution, which is a distribution over subsets of variables. Pseudocode for selecting subset of variables from an observation distribution is shown in Algorithm 2 in Appendix B At high level, observation distributions have three key properties:
Locality Observed samples contain only variables from a local neighborhood, consisting of a central variable along with all variables of distance at most le from it. To sample from the observation distribution, we sample the central variable uniformly randomly and then sample k from some distribution that controls the local neighborhood size. In our experiments, we draw & either from a geometric distribution with a parameter of 0.5 or a Zipfian distribution with parameter of 2.
Variable dropout Even within local subset of the world, we may not see everything at once. Certain variables may be missing or go unnoticed. We formalize this intuition with variable dropout. With some probability (0.2 in our experiments), variables are dropped from a local neighborhood and the learner does not see them. Variable dropout may also help model generalize to pairs of variables that were unseen in training as more subsets of variables appear the training set.
Held-out pairs
Finally, some pairs of variables are held out across all training data. If local neighborhood, after variable dropout, would include a pair of variables we decided to hold out, we randomly remove one of the two variables in the pair from the sample. We use the ability to match conditional probabilities for held-out pairs of variables, measured via mean squared error, as our main performance metric.
We also create two control conditions to compare against local observation distributions. As one control, we consider a training dataset in which the values of variables are sampled from one Bayes net, but the local neighborhoods are constructed with respect to the structure of a different Bayes net. This condition still has local co-occurrence structure, but the co-occurrences do not reflect

---

0.15-
Meen squerred enor
0.10-
Estimator
direct prochetion
negalive stalTelded
[ree geaeration
0.05
soafoolddd.
0.00
Fully observed
local (gesm)
local IZiph)
waung local (grom)) weung local (Zig()
Train condition
Figure 2: Mean squared error between estimated and true conditional probabilities for held-out pairs with high mutual information. Error bars denote 95% confidence intervals. Both free and scaffolded generation significantly outperform direct prediction when the training data is locally structured.
which variables influence each other. As another control, we use fully observed condition where each sample contains almost all of the variables in the Bayes net. One of the two variables in each held-out pair is randomly dropped, but all other variables are included. These controls enable us to test whether local structure in the training data drives the value of reasoning.
4.2 Estimation
Each of the estimators in Section 2.2 is implemented via sampling from and scoring with the language model. For instance, in free generation, the model is prompted with the target variable name and initial observation, then sampled from until the target variable name is generated. The probabilities for possible values of the target variable then examined. Figure IC illustrates how implement direct prediction and free generation as prompts and Appendix[Dcomee contains examples of each estimator. For estimators that rely Monte Carlo estimation, use 10 samples.
We also introduce negative scaffolded generation as control estimator that generates irrelevant intermediate variables. For each pair of variables, we select random set of variables equal in size to the scaffold, but which does not include any of the scaffold variables. We prompt the language model to generate values for the negative scaffolds in the same way in scaffolded generation.
4.3 Model architecture
use a smaller version the GPT-2 autoregressive transformer architecture [20], as implemented in the HuggingFace transformers library 21 Our model has 51 512-dimensional embeddings. 10 layers, and attention heads. Data tokenized via a Byte Pair Encoding tokenizer fit to data in our format 22] We trained this architecture with randomly initialized weights for 300, 000 gradient steps batches containing 3, 077 tokens each, for a total of 921, 600, 000 tokens of training. We trained models using the Adam optimizer 233 Each model's training set consisted of 1, 000, 000 samples from a single Bayes net. The models achieved near-perts perreeeffect performance on the training task. Further training details provided in Appendix E We also compare multiple different architectures in Appendix demonstrating that our results are robust across them.
Results
Each held-out pair gives four data points: we hold out the pair X1, X2 we can estimate p(X X
0), = 1), p( X 0), and p( X1 = 1). Pooling across the 10 Bayes nets we trained models on gives us 1, 000 data points per training condition and estimator. Figure shows main result: free generation performs better (lower MSE) than direct prediction and performs

---

Distance from target probability
0.75-
Training condition
0.50
local wrong local
fully observed
0.25-
0.00-
2
50
%
Number of intermediate variables
Figure 3: Number of intermediate variables generated in free generation vs. absolute distance between true and estimated conditional probabilities for each training condition. Lower dots indicate more accurate estimation, while dots further to the right indicate more intermediate variables generated.
Table 1:
Mean squared errors with 95% confidence intervals between direct prediction probabilities and either true or marginal probabilities for non-held-out pairs with high mutual information. In the local training conditions, direct prediction is close to perfect at matching conditional probabilities.
fully observed
local (geom)
local (Zipf)
wrong local (geom)
wrong local (Zipf)
true marginal
.013 1,010, .16]
.004 [003, .055]
.003 1.003, .004]
.052 [.045, .059
.066 [,049, .063]
.080 [.073, .86)
.114 [.106, 121]
.112 [.104..111]
.047 [,041, .052]
.033 [,029, .038]
well with less training when the data structured locally. The MSEs for all estimators and training conditions after 921.6 million tokens of training are shown in Figure 2
Appendix Ghoows how MSE varies with the number of Monte Carlo samples taken for each estimator. Estimation error is high for free and scaffolded generation for low numbers of samples due to high variance, but quickly decreases with the number of samples. Re-sampling the intermediate variables is akin to self-consistency prompting methods which involve re-sampling the chain of thought and taking the majority or average answer [4]
5.1 When reasoning helps
We find benefit to reasoning when the observation distribution has the correct locality structure. When the training data structured locally with respect to strong dependencies, both scaffolded and free generation perform significantly better than direct prediction. We call this difference the reasoning gap. Scaffolded and free generation also perform significantly better than negative scaffolded generation, indicating that relevant intermediate variables help in predicting the target variable, but irrelevant intermediate variables do not. Furthermore, the success of free generation demonstrates that model trained local subsets of Bayes net self- self-generate helpful intermediate variables.
In free generation, the model generates variables until it produces the target variable. This results in reasoning traces of varying lengths, including many long traces. One might expect long traces to distract the model, but this did not occur in practice: the length of the reasoning trace does not relate strongly to accuracy within training conditions, as is shown in Figure However, free generation does not outperform direct prediction substantially when the training data is fully observed.
It is also of note that training on locally structured data reduces the average length of reasoning traces (Fig. 3) In local training conditions, free generation usually produces set of variables that d-separates the observed variable from the target variable- - 70% of the time in the local neighborhood conditions. In contrast, the training conditions with the wrong locality structure only lead to d- separating reasoning traces 34% of the time. The fully observed training condition also usually creates d-separating reasoning traces (69%), likely because generates a large number of variables. d-separation is important because it ensures that the intermediate variables capture all the influence that the observed variable exerts on the target variable. These results suggest that training on local clusters of variables is valuable in part because it makes it easy for an autoregressive model to
8

---

Table 2: Mean squared errors between estimated conditional probabilities and marginal probabilities
of target variables with 95% confidence intervals. Lower values indicate closer matches.
fully observed
local (geom)
local (Zipt)
wrong local (geom)
wrong local (Zipf)
dircct prediction
.86 [.079. .093]
.115 [1108 [24]
.116 [1606,11112
.029 [,025, .033]
.022 [0019.025]
negative scaffolded
.089 [.082, .96]
.116 [108, .124]
.115 [,108, .133]
.066 (000)
006 [.022, .030]
free generation
.123 .132]
.124 [1117,11333
.127 [.120, .135]
.099 [,044, .05]
042 [0037, 048]
scaflolded
.110 [.102, .11]
[,16,, .142]
(.126,, .12]
.051 [,046, .077]
.043 (,03, 049]
naturally output useful intermediate reasoning steps. Still, chain-of-thought reasoning can be helpful even if the reasoning trace does not completely d-separate the two variables. In the local training conditions, the model does not generate a d-separating trace 30% of the time, yet there is virtually no performance difference between free and scaffolded generation.
5.2 Data complexity and reasoning
The combination of locally structured training data and step-by-step reasoning can also lead to accurate conditional probability estimates with much less training than would be required a model were trained on fully observed data. To demonstrate this difference, we run both direct prediction and free generation on checkpoints from our models that are saved after every 5000 gradient steps (15.3 million tokens) of training. Part D of Figure shows the results of this analysis.
When data is fully observed, direct prediction and free generation performances improve slowly but consistently. There is no reasoning gap, as both estimators perform almost identically. When the model is trained on data from geometrically sized local neighborhoods, direct prediction performance improves quickly, then plateaus. There is substantial reasoning gap where free generation outper- forms direct prediction. Free generation matches the true conditional probabilities very closely after about 120 million training tokens, achieving the best performance of any combination of training condition and estimator. Still, a sufficiently large transformer can eventually memorize the relation- ships in its training corpus with enough training. We evaluate the data complexity of direct learning by training language model of the same architecture on fully observed data without holding out any pairs. Direct prediction in this case takes over 3 times as much training to achieve the same performance as local training with free generation, despite the model seeing the relevant pairs in training (see Appendix H for detailed results). Training language models on datasets consisting of local neighborhoods with strong dependencies and performing chain-of-thought reasoning at inference time can therefore be more data-efficient than training on more complete datasets.
5.3 When reasoning is unnecessary
Table shows MSEs between direct prediction estimates and true probabilities for the 25 high- high-mutual- information variable pairs that were not held out from the training set. In the local training conditions (and to a lesser extent fully observed), direct prediction matches the true conditional probabilities al- most perfectly. This result indicates that our language models learn to match conditional probabilities directly when the observed and target variables co-occur in the training distribution. Observing these variables together frequently obviates the need for step-by-step reasoning.
5.4
When reasoning fails
We test the hypothesis that language models match the marginal probabilities of the target variables when they fail to predict the true conditional probabilities by comparing models' estimated conditional probabilities against the true marginal probabilities. The MSES between the estimated conditional probabilities and marginal probabilities of the relevant target variables are shown in Table We can see the opposite of the trend for true probabilities: the worse a training condition does at matching the true conditional probability, the better it matches the marginal. The language models trained on data with the wrong locality structure generated estimates that were particularly close to the marginal probabilities. When the variables that co-occur with each other frequently are not local in the Bayes net, they often have very little influence on each other. This means that the joint distribution over co- co-occuriing variables is usually very close to the product of the marginal probabilities, i.c.

---

P(X1, X(, = ((X for non-local X1. X3, Without the ability to estimate conditional probabilities accurately, there are no reliable 'steps' for step-by-step reasoning to use.
6 Discussion
Our theoretical and experimental results demonstrate that estimating conditional probabilities by reasoning through intermediate variables outperform direct prediction when the training data has local structure. When the training data includes all the variables, free generation does not lead to better performance than direct prediction. When the training data has the wrong locality structure, the models do not reliably learn conditional probabilities that can be chained together.
Our results provide minimal case in which chain-of- -haiiugh- reasoning is helpful and suggest conditions under which it is likely to be helpful in more naturalistic settings: we can expect chain-of- thought reasoning to help when model is tasked with making inferences that span different topics or concepts that do not co-occur often in its training data, but can be connected through topics or concepts that do. Re-sampling the chain of thought multiple times might be especially valuable in domains with moderately strong dependencies. In these settings, introducing intermediate steps increases the variance of estimation and re- remaaining multiple times reduces it. We have also shown that chain-of -fain-of-thought reasoning enables greater data efficiency: a model trained on locally structured data with chain-of-thought reasoning at inference time can accurately match conditional probabilities with less training than a model trained on all the data. This result can provide insight into why humans more data-efficient than language models. Since humans experience the world from first-person perspective, the information we encounter is structured in small clusters of entities that are tightly coupled with each other. This idea could also be relevant data curation for the training of language models. Constructing datasets with tightly correlated observation neighborhoods that collectively cover the space of relevant concepts may amplify language models' ability to perform Shain-of-thougee reasoning while reducing their data needs.
Future work should explore the structure of the observation distribution for human learners to understand how the information we observe facilitates reasoning. Using modern language models as toy models for the study of reasoning is promising direction for cognitive science address long-standing problems in reasoning and problem-solving. such as the value of thought experiments.
The role of abstraction in reasoning is another important direction for future work. Humans often abstract principles to reason rather than exclusively considering possible concrete states of the world (settings of observable variables). Likewise, the language corpora that language models are trained on contain abstract concepts expressed in natural language. Understanding how abstractions can arise and the effects they have reasoning would be helpful in connecting our setup to more naturalistic reasoning contexts. The possibility of taking abstract steps makes the problem of choosing useful reasoning steps much harder, reason more effectively through fine-tuning, in-context learning, and reinforcement learning.
plan to explore questions of how language models might learn to
Limitations Of the many forms of chain-of-thought prompting that exist in the literature, our findings are most relevant to zero-shot prompting [e.g.1] 9 where a model produces steps on the way to an answer without any other examples reasoning traces in its context window. It is less applicable to methods that involve giving the model examples of reasoning [c.g. [0]. Our results are also in the context of simple propositional worlds. Reasoning in rich, structured worlds may require more expressive languages with which to reason and specify hypotheticals. Our theoretical results do not explain the phenomenon observed in practice that transformers revert to the marginal distributions for held-out pairs. We leave future work explore how the inductive biases of transformers might induce this behavior on unseen data.
Acknowledgments and Disclosure of Funding
We thank members of the Computation and Cogniton Lab, the Causality in Cognition Lab, and the Stanford NLP Group for feedback on earlier versions of this work. particular, we thank Tobias Gerstenberg for advice on the importance of strong dependencies for reasoning and Eric Zelikman for feedback on the design of our figures. This work is supported by an NSF Expeditions Grant, Award Number (FAIN) 1918771.
10

---

References
[1] N. Shepard, "The step to rationality: The efficacy of thought experiments in science, ethics, and free will," Cognitive Science, vol. 32, no. 1, pp. 3-35, 2008.
[2] D. C. Dennett, Intuition pumps and other tools for thinking. WW Norton & Company, 2013.
[3] Brown, B. Mann, N. Ryder, M. Subbiah, J. D. Kaplan, P. Dhariwal, A. Neelakantan, Shyam, G. Sastry, A. Askell, et al., "Language models are few-shot learners," Advances in neural information processing systems, vol. 33, pp. 1877-1901, 2020.
[4] A. Chowdhery, S. Narang. J. Devlin, M. Bosma, G. Mishra, A. Roberts, Barham, H. W. Chung, C. Sutton, S. Gehrmann, et al., "Palm: Scaling language modeling with pathways," arXiv preprint arXiv:2204.02311, 2022.
[5] H. Touvron, T. Lavril, G. Izacard, X. Martinet, M.-A. Lachaux, T. Lacroix, B. Rozière, N. Goyal, E. Hambro, Azhar, al., "Llama: Open and efficient foundation language models," arXiv preprint arXiv: 13971, 2023.
[6] B. bench authors, "Beyond the imitation game: Quantifying and extrapolating the capabilities of language models," Transactions on Machine Learning Research, 2023.
[7] K. Cobbe, V. Kosaraju, M. Bavarian, M. Chen, H. Jun, L. Kaiser, M. Plappert, J. Tworek, J. Hilton, R. Nakano, et al., "Training verifiers to solve math word problems," arXiv preprint arXiv:21 10. 1416,, 2021.
[8] M. Nye. A. J. Andreassen, G. Gur-Ari, H. Michalewski, J. Austin, D. Bieber, D. Dohan, A. Lewkowycz, M. Bosma, D. Luan, et al., "Show your work: Scratchpads for intermediate computation with language models," arXiv preprint arXi::2112.0011 2021.
[9] T. Kojima, S.S. Gu, M. Reid, Y. Matsuo, and Y. Iwasawa, "Large language models are zero-shot reasoners," " arXiv preprini arXiv:2205. 1916, 2022.
[10] J. Wei, X. Wang, D. Schuurmans, M. Bosma, brian ichter, F. Xia, E. H. Chi, Q. V. Le, and D. Zhou, "Chain of thought prompting elicits reasoning in large language models," in Advances in Neural Information Processing Systems (A. H. Oh, A. Agarwal, D. Belgrave, and K. Cho, eds.), 2022.
[11] D. Dohan, W. Xu, A. Lewkowycz, J. Austin, D. Bieber, R. Lopes, Y. Wu, H. Michalewski, R. A. Saurous, J. Sohl- Sohl-dickstein, et al., "Language model cascades," arXiv preprint arXiv:2207. 10342, 2022.
[12] A. K. Lampinen, Dasgupta, S. C. Chan, K. Matthewson, M. H. Tessler, A. Creswell, J. McClelland, J. X. Wang, and F. Hill, "Can language models leam from explanations in context?," arXiv preprint arXiv:2204.02322 .20399,, 2022.
[13] E. Zelikman, Y. Wu, J. Mu, and N. Goodman, "STaR: Bootstrapping reasoning with reasoning," in Advances in Neural Information Processing Systems (A. H. Oh, A. Agarwal, D. Belgrave, and K. Cho, eds.), 2022.
[14] X. Wang. J. Wei, D. Schuurmans, Q. V. Le, E. H. Chi, S. Narang, A. Chowdhery, and D. Zhou, ssefs-consisteneyy improves chain of thought reasoning in language models," in The Eleventh International Conference on Learning Representations, 2022.
[15] D. Zhou, N. Schärli, L. Hou, J. Wei, N. Scales, X. Wang, D. Schuurmans, C. Cui, O. Bousquet, Q. Le, et al., "Leass-to-most prompting enables complex reasoning in large language models," arXiv preprint a00:v:2205./0625, 2022.
[16] S. Yao, D. Yu, J. Zhao, I. Shafran, T. L. Griffiths, Y. Cao, and K. Narasimhan, "Tree of thoughts: Deliberate problem solving with large language models," arXiv preprint arXiv:2305.I 10601, 2023.
[17) D. M. Blei, A. Y. Ng, and M. I. Jordan, "Latent dirichlet allocation," Journal of machine Learning research, vol. 3, no. Jan, pp. 993-1022, 2003.

---

[18] D. M. Blei and J. D. Lafferty. "A correlated topic model of Science," The Annals of Applied Statistics, vol. no. pp. 17 35. 2007.
[19] S.C. Chan, A. Santoro, A. K. Lampinen, X. Wang, A. Singh, H. Richemond, Mc- Clelland, and F. Hill, "Data distributional properties drive emergent in-context learning in transformers," in Advances in Neural Information Processing Systems (A. H. Oh, A. Agarwal, D. Belgrave, and K. Cho, eds.). 2022.
[20] A. Radford, J. Wu, R. Child, D. Luan, D. Amodei, and I. Sutskever, "Language models unsupervised multitask learners," 2019.
[21] T. Wolf, L. Debut, V. Sanh, J. Chaumond, C. Delangue, A. Moi, P. Cistac, T. Rault, R. Louf, M. Funtowicz, et al., "Transformers: State-of-the-art natural language processing," in Pro- ceedings of the 2020 conference on empirical methods in natural language processing: system demonstrations, pp. 38 45, 2020.
[22] R. Sennrich, B. Haddow, and Birch, "Neural machine translation rare words with sub- word units," in Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 1715-1725, 2016.
[23] D. P. Kingma and J. Ba, "Adam: A method for stochastic optimization." in Proceedings of the 3rd International Conference Learning Representations (ICLR), 2015.
12

---

A Theoretical analysis
In this section, we theoretically analyze chain-of-thoon -ftouughttt reasoning when the underlying data distri- bution can be represented as directed chain. We prove that any minimizer risk consisting of cross-entropy term and entropy regularization term will exhibit "reasoning gap" when the data has a particular locality structure.
A.1 Problem Setup
We assume that we observe a sequence of variable indices i, E {I,...,N N) and variable values Vt X for some finite set X. In the sequence, variable values always follow variable indices. Since our results concern estimators that are only ever conditioned on a single variable, it suffices to consider sequences of length two. However, our setup can be interpreted as assuming observe independent local neighborhoods of size 2 with token separators.
Factorization of data distribution We assume that the joint distribution Pa over Y1, Yz.... Yn factorizes as
N
Pa(Y Yy) = Pa(Yi) II Pa(Y++1\Xg)
j=1
and that Yi, .,, YN take support in some finite set X. Note that the variable indices index particular random variables in Pa-
Local observation distribution We will consider setting where only adjacent variables in the graphical model can appear adjacent in the sequence. More formally, let y refer to the set of all variable identifiers. Let Vobs be the of all allowed pairs of variable indices. Then, Vobs S P((I...., and Vots consists of pairs of the form (i, i + 1). We will define the distribution over these valid subsets of variable indices as Pobsi in particular, Pots takes support only on Yous and assigns equal probability to all of its pairs. The two distributions and Pobs define distribution over the sequence of variable indices and variable values.
That is, for any non-adjacent pairs Y, and Yj and for any variable values yi and y/j
p(1 U1 yi, i2
M)} =
(5)
For adjacent pairs Y1+1 and Y, and for variable values //+1 and yo-
p(i i, yi, 12 i + 1, = 11+1) x Pa(Y, = yi Y, =y;)
(6)
Intuitively, this property will imply that the risk minimizer only gets to see a small subset of local statistical dependencies in the graphical model. This key property of the observation distribution will induce reasoning gap.
A.2 Preliminaries
We begin with proposition that will be useful in the main theorem. The proposition concerns the minimizer of the sum of two cross-entropy terms.
Proposition 1. Let 0i 2 0, 02 2 0. Let R(g) = a EpE)) log ((x)] + a2 log (x)) Then q" = arg min R(g) = Pi,t,
+ a on (att)
Proof. We assume the probability distributions are discrete. The Lagrangian given by
Da) = a1 Σ (x) log + -02 Σ log + do ② g(x) - 1)
(7)
x
The first-order conditions are dc
P1 (I
P2 P2(x)
-0
+ - 02
Ag =0
(8)
0q(x)=
q(x)
g(x)
QC Σ 9(0) - 1
(10)
13

---

The first condition allows us to write g(z) (asp(a)
We can substitute this for g into the
other first order condition (i.e., normalizes) to obtain
a1Pi(z) + (2)2(())
A
This implies Ao = a1 + a2 and the desired result follows immediately.
A.3 Main Theorem
Our main result is that the minimizer of the risk q" under the distribution p defined by Pobs and pa and cross-entropy loss with entropy regularization will exhibit a "reasoning gap". We begin with a characterization of q" For simplicity, in the result below, we'll use ia denote elements of the sequence that correspond either to variable values
variable indices is.
Theorem A.1. Let be the uniform distribution. Let p be the distribution over variable indices and variable values defined by pobs and pa. Let (p, q) denote the cross entropy between distributions p and q. We consider the following risk:
R(g) = (p, q) + (u,
(11)
Then q- arg ming R(g) satisfies the following properties.
For all pairs of adjacent random variables Y; and Yi41, q (Yi(Y)) Apa(Ye+1 +
X) P for some 10.
For all pairs of non-adjacent random variables, q (Ya])))) = [lal-
Proof. We can write the risk as a sum across timesteps.
T
T
R(q)
2 E
log (ox
Em lollllloggaa0 gogg((s(zaaa))))
(12)
E=1
(13)
Let us consider the left sum. By the law of iterated expectations, we can decompose the fourth term in the sum where 24 variable value
B log log
(14)
E Ep v. ( 1 (02 (12,
(15)
E p (i
(16)
11
Σ
Σ
(17)
11
Importantly, notice that the outer sum over the variable indices i i2 is over Vote due to the observation distribution.
On the other hand, consider the right sum.
- (1 En(inan) [ mi]]
(18)
(19)
(20)
12
Σ
Σ
l u))((ii v1)
(21)
(ix.))))xx) 01
(22)
14

---

We consider two different cases. Suppose the variable indices are adjacent so that 12 = i + 1 and i i for some i. In addition, fix some value for V1. Then, we can take exactly two terms, one from the left and right sum.
E Peteaiiaam log ((12) 11:2 un (1((22 v1)
2
(23)
1 F Futelbaann log g /1 (0
2
The expectations that appear in Eq 23 are either 1) cross entropy between either ((Yi)y)))))))) and pa(Y)(X;) or 2) a cross entropy between ((Y,)X,) and the uniform distribution. By an application
of Proposition 1 the sum of these two terms minimized by taking q (Y(i))) = A p + (1
X.,))(())( for Az, = p( The result holds for any adjacent pairs.
x(112.21)
Finally, we consider non-adjacent pairs Y; and Yj. By construction, we can never have iz
i,ú jj in the left sum. We will only have one cross entropy term between q" (Y:)y,) and u (Y;)).
Therefore, minimizing the risk is equivalent to minimizing the entropy regularization term and taking 9" (Y()),, = [
In the following corollary, we will show that the squared bias of the scaffolded generation estimator, which explicitly marginalizes out intermediate variables, less than the squared bias of the direct estimator. For this result, we assume that the true conditional probabilities satisfy a doubly stochastic condition; that is, Ey, PV;; = y = yj) = 1 = Ey, P(Y; y = y3)- We discuss how to relax this assumption under different assumptions about the risk minimizer.
Theorem A.2. For all yr Vj E X with l j1 1,
(Y, Y w,)l p(y; = =vil, = =,,)1² < 10 - -olY= ツ;) - = Vily, = U,)1
Proof. First, we show that EY = v = yj)l = Ap(x, = u = y,) + + (1- 2) for some À E (0, 1). Here the expectation Is taken with respect y/ q" (Y: = 34-1), Vi-1 {Y(Y = 21- 1/++ ~ q" IY, - Mj). For conciseness, our notation, we omit the random variables that the expectation is taken with respect to.
We prove this by induction on İ - ÿ/. the distance between the nodes corresponding to Y, and Y, in the directed chain. We consider the base case j - - = 2.
1
E (Y's = ys Yi -1)] = E[(1 As.))(('s = ys Y22 = b2) + λ3.2 |
1
>3,2 |X|
+ (1 )s, = 82| Y2)l
>aa22 |
1
+ (1 - --a.2) Σ p(Ys = valY2 v2)((1 22,1)1(22 =/2(Yi = vii) + A2.1 X
1
Aa.22 X
+ (1 (1 - -2211) Ev(Y== -v1V22 = v2)x((2 v2/2i =
1
+ (1 - -222)2211
x P('s -y3lYs 122 = y22
1
A2. X
+ (1 11 - >2.1)1(3s valYi 91)
+ (1 - -1a,2))2.11 |2|
(1 - ))
+ Xp ys Y y1)
x
15

---

Here À (1- - A3.2)(1 - X2.1). Importantly. the expected value is strict convex combination of the uniform and conditional probabilities. For the induction step, we note that the expectations Elus (Y; yil 1 y;}l and IF (Y 1 = Uj]] are related as follows
Elis (Y; yil Y -y>)] = A X
(1 - A) Σ p(y wi|Yi = 11-1) x (Y = yi- |V, - k5)]
We now use this characterization of the scaffolded estimator mixture distribution to prove the desired inequality. The bias of direct estimator can be computed as पि p(Y; = yel X = =;)l By the previous results, EY; yリ Y = v:)l >p(Y))))) (1
for some À (0, 1).
4 (Y. y,)l p(y; = yı Y y
AAp(Y Vily, = リ,) + (1 -
p(y, = YY, = ,,)l²
- -Ay(Y = wilys = vi) + |21
> |
- p(;; = yb Y = 4/ 11
1((A - 1))(Y, = Y = 1U) + (1 - A) 1
X
= (1 - 1)3((
p(Y, = y1 YY, = y/)1
[2
p(Y; = YY, ,,)1
Interestingly, if we assumed that the risk minimizer interpolates between the marginals and the true conditionals, we could relax the doubly stochastic condition.
B Pseudocode for data generation
This section contains pseudocode for the algorithms we use to generate Bayes nets and select variables to include in given sample according to the observation distribution.
First, we use Algorithm to create Bayes nets. This algorithm takes in a number of nodes and edges to create and defines directed acyclic graph by randomly adding edges between pairs of nodes. Next, it assigns conditional probability tables to the nodes given the values of their parents to create a Bayes net.
For each sample, we only show subset of all the variables according to an observation distribution. Algorithm [ shows the procedure we use to select which variables to display in a given sample. We first sample central variable e (uniformly) and distance lt (according to geometric or Zipfian distribution), then get all the variables within distance k of in the graph. Next, we remove each variable with probability 0.2. If any of the held-out pairs remain, we randomly remove one variable from each pair. In the wrong locality structure training conditions, we use graph G that does not correspond the net from which our samples are drawn but has the same variable names, In the fully observed condition, we start with all variables, but still remove held-out pairs using the final for loop.
C Full sample of training data
The following is an example of a sample from local neighborhood of a Bayes net in string format, as used in training our models:
###
target: X5
X17=0
X92=0
X13=0
16

---

Algorithm Algorithm for generating Bayes net
Input: Number of nodes N, number of edges M G (E, V) empty graph
for i E {1,..... N} do
V <- V (Xi)
end for for i ,,, 3 do
U1, U2 f random pair of vertices E V
while 02) E (V1, U2) would create cycle do
U1, U2 <- random pair of vertices E V
end while
E UU {(01, x2)}
end for
T empty associative array for E TOPPLLOGICALSSOTTCC do
empty conditional probability table for E possible configurations of v's parents do
p (AMPLE }))
t|c p-p P end for T(u + end for
D < Bayesian network defined by graph G and conditional probability tables T
return D
Algorithm Algorithm for selecting variables include based on an observation distribution
Input:
Bayes net graph G = (V, E), set of held-out pairs P. size distribution D random variable E V
A + SAMPLE(D)
R + ())
for E V do
if is within distance in then
R + R J (w)
end if
end for for u E do if [SAMPLE(Bemoull, 0.2) 1 then
R R \ {2} end if end for
for (U1, 02) do
if e1 E R and un E R then
if SeMPLE(Beeoolll,, 0.5) then
R + R \ {ei}
else
R t R \ {22)
end if
end if
end for
return π
17

---

x
x24=1
X26=1
X91=0
X36=0
X34=0
X12=1
X20=0
X5=1
The full training set consists of 1, 1,000, 000 samples like this concatenated together.
D Formatting estimators as prompts
D.1 Direct prediction
In direct prediction, we use a simple prompt that specifies the label and value for the observed variable then states the name the target variable. For example, if wanted estimate p(X²| X1 = 0) we would use the following prompt:
###
target: X2
X1=0
X2=
We would then take the softmax of the log probabilities the language model assigns to '1' and '0' being the next token and use the resulting probability of '1' as the estimate.
D.2 Scaffolded generation
In scaffolded generation, we pre-compute sequence of intermediate variables, then use the language model to estimate their values. For example, if we wanted to estimate p(Xa|xX,) and we knew X₂ and X3 were scaffold variables, we would start with the following prompt:
###
target: X4
X1=0
x2=
We would then sample the next token (either or 1) from the language model and append it to the prompt, followed by the name of the next scaffold variable on new line. For example, if we got value of from the language model, we would give it the following prompt next:
###
target: X4
X1=0
X2=1
x3=
We repeat this process until all scaffold variables have values, then compute the probability assigned to the target variable the end, in the same way we do for direct prediction. The final prompt we use to estimate the probability might look like this:
###
target: X4
X1=0
X2=1
X3=0
x4=
18

---

We repeat this sampling process 10 times to produce a Monte Carlo estimate over the values of the scaffold variables and average the probabilities assigned to the target variable over samples.
D.3 Free generation
Free generation is similar to scaffolded generation, but we sample from the model to choose which intermediate variables to instantiate, rather than just their values. For example, if we were inferring p(Xa/Xi 0) we would first prompt the model like this:
###
target: X4 X1=0
We then sample the next two tokens from the model, which is exactly enough for one variable name. We add an equals sign, then sample the variable's 's value in the same way we do in other estimators. For example, our prompt might look like this after generating one intermediate variable and its value
###
target: X4
X1=0
X5=1
We repeat this process until the model outputs the name of the target variable. At that point, we have a prompt that might look like this
###
target: X4
X1=0
X5=1
X2=0
X7=0
X3=1
x4=
We then extract the probability of the target variable as in other estimators. Again, we average target variable probabilities over 10 samples of the intermediate variables.
E
Training details
The main architecture we used is smaller version of the GPT-2 architecture, with 512-dimensional embeddings, layers, and attention heads. has 32, 573, 440 parameters total. We fit a Byte Pair Encoding tokenizer data from our samples, which produced 356 unique tokens.
Our text was grouped into chunks of 1024 tokens and batches of 3, for total of 3072 tokens per gradient step. We used the Adam optimizer, with an initial learning rate of 10 and Beta values of and 0.999.
All models were trained on Nvidia Titan Xp GPUs. They were trained for 300, 000 gradient steps, which took approximately 20 hours each.
Comparison of reasoning gaps across different architectures
To ensure that our results are robust across different transformer architectures. compare mean squared eтror by estimator for four alternative architectures. We focus on training data consisting of geometrically-sizze local neighborhoods, Figure 4 mean squared error by architecture type trained on geometrically-stee architectures, except for the tiny architecture which fails to match the distribution at all.
local neighborhoods of variables. Results are very similar across all
We compare the original architecture to a smaller (4, 473, 600-parameter) architecture, a larger (86, 628, 964-parameter) architecture, and wider architecture with larger embeddings but fewer
19

---

0.15
Mean squaared extor on held-oloo hald-out pairs
0.10
Estimator
direct prodiction
negative scaffolded
free generalion
0.05-
scaffolded
0.00
original
smaller
larger A rchitecture
wider
tity
Figure 4: Mean squared enror by architecture type and estimator. All architectures were trained on same data consisting geometrically- local neighborhoods of data. Error bars indicate 95% confidence intervals.
Table 3:
Embedding size, number of layers, and number of attention heads for each of the five architectures used in the architecture comparison
Architecture type
Embedding Size
Layers
Attention Heads
original
512
10
8
smaller
256
5
4
larger
768
12
12
wider tiny
1024
3
8
4
2
2
layers (39, 887, 872 parameters). Finally, we compare against a tiny architecture that is too small to match the distribution of the true Bayes net (8, 644 parameters). Table shows the embedding sizes, numbers of layers, and numbers of attention heads for each architecture.
G Mean squared error by number of samples
As mentioned in the main text, the number of Monte Carlo samples taken over intermediate variables influences the variance of the scaffolded and free generation estimators. We demonstrate this computationally by reporting the results of each estimator for different numbers of samples for the model trained on geometrically-sizer local neighborhoods of variables. Figure [5) shows MSE by number of samples using each estimator that averages over samples, compared against the baseline of direct prediction. Free and scaffolded generation both have higher MSE than direct prediction with one or two samples due the increase variance. However, they achieve lower MSE when averaging over more than three samples. Negative scaffolded generation exhibits very similar performance to direct prediction for all numbers of samples, which suggests that the values of intermediate variables do not influence the final prediction for that estimator.
H Data efficiency of fully observed training with no held-out pairs
To supplement our efficiency analyses, we ran a version of the fully observed training condition without any held-out pairs. In this setting, the transformer can directly memorize the true conditional probabilities, but it takes long time for direct prediction to perform well as free generation with locally data. Figure compares the performance of direct prediction and free generation
20

---

squasuuan estornn hadd-dddu..
Estimator
0.04
begative scaffolded
free generalion
scaffolded
0.00-
2
3
4
10
number of samples
Figure 5: Mean squared error by number of Monte Carlo samples of intermediate variables for models trained on geometrically-sizer local neighborhoods of variables. The blue line indicates the MSE achieved by direct prediction. Ribbons indicate 95% confidence intervals.
0.100-
Estimator
direct prediction
Mean sqquared
0.073
free generation
Train condition
fully observed (no held-out pairs)
local (geom)
0.025
0.000-
0.0++00
255+08
5.0e-08 Number of tokens
7.56+08
Figure 6: Learning curves comparing mean squared error on held-out pairs, estimated using free and direct prediction for training data consisting either geometrically-sizee
local neighborhoods or the full set of variables. Unlike the version reported in the main text, no pairs of variables are held out in this fully observed condition. Even though the model is trained directly on the held-out pairs in the fully observed condition, there is substantial data efficiency advantage to using locally structured training data and free generation at inference time.
21

---

for locally structured training data with held-out pairs and fully observed training data with no held-out pairs. Direct prediction with fully observed training data can outperform free generation with bcally-structuree training data. However, it takes approximately 650 million tokens of training to reach the same performance that free generation with geometric locally-structure training data converges to after only about 200 million tokens of training.
22


Reviews:
[{"review_id": "1VPlFQ3J2Q", "reviewer": "Reviewer_jbx9", "summary": "This work investigates why and how chain-of-thought reasoning works in language models in the aspect of \n**local structure** in the training data. To this end, this work first proves the hypothesis that there exists a reasoning gap where reasoning through intermediate variables improves inference and then tests the hypothesis by training an autoregressive language model on samples from Bayes nets but only including\na subset of variables in each sample, considering the estimators including direct prediction, scaffolded generation, and free generation. The key findings are intermediate steps are only helpful when the training data is locally structured with respect to dependencies between variables and that the combination of locally structured observations and reasoning is much more data-efficient than training on all variables.\n\nThis work begins with the human practice of step-by-step reasoning and reviews the recent progress of a similar mechanism --- the intriguing chain-of-thought reasoning in large language models. Then the paper asks the question of why step-by-step reasoning helps, which may not only help understand how the large language models work but also provide insight into the origins of human reasoning. \n\nThe basic hypothesis is that chain-of-thought reasoning is useful in language models due to the local structure in the training data. Such a hypothesis is intuitive as human reasoning transcends local bounds, supporting plans and conclusions that span in time and space. The meaning of local structure may be interpreted as observations occurring in overlapping neighborhoods of concepts.\n\nTo verify the hypothesis, the authors conduct theoretical analysis and empirical experiments, finding that performing conditional inference by first generating intermediate variables improves the ability of a language model to match true conditional probabilities only when the training data is structured locally with respect to strong dependencies and the intermediate variables are relevant to the relationship between the variables of interest. Finally, the work also provides insights into three aspects: (i) when reasoning helps --- the observation distribution has the correct locality structure; (ii) when reasoning is unnecessary -- the observed and target variables co-occur in the training distribution; (iii) When reasoning fails --- data with the wrong locality structure.\n\nOverall, this work studies an important and timing research topic towards why and when step-by-step works in language models. This work provides comprehensive theoretical and experimental results to support the hypothesis. This work also provides useful insights into solving reasoning tasks, as well as dataset construction to amplify the capacity of large language models to perform step-by-step reasoning.", "questions": "Why does this work choose a smaller version of GPT-2 for experiments instead of a large language model? Scaling laws affect the step-by-step reasoning ability of language models. Small models may commonly fail at step-by-step reasoning compared with direct reasoning. In contrast, large language models may be the better backbone to verify the hypothesis of this work.", "limitations": "The authors have provided thoughtful descriptions of the limitations.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. The topic studied in this work is very important and has attracted increasing interest in the community. This kind of work is useful to advance our scientific understanding of why the intriguing chain-of-thought reasoning works (or fails on some tasks), and helps facilitate future studies on training dataset construction and prompting techniques to amplify the capacity of large language models to solve complex reasoning tasks.\n\n2. The theoretical part clearly formulates the problem. It also introduces effective approaches for estimation, followed by convincing experiments on a real-world language model (though with the smaller-scale GPT-2 instead of the real large language models).\n\n3. Many great insights can be found in the paper, after taking into account the influence of data complexity, when reasoning works, becomes unnecessary, and even fails. The findings basically align the real-world practice when applying chain-of-thought prompting in different reasoning tasks.", "weaknesses": "1. The paper can be improved by taking large language models as the backbone and verifying the hypothesis on real-world datasets where chain-of-thought prompting techniques are widely applied. It would be interesting if this work could provide effective ways to identify the locality of a dataset, which may answer the commonly found yet unresolved question of why chain-of-thought techniques work quite well in arithmetic tasks but fail at some standard natural language understanding tasks like simple classification.\n\n2. The connection and the difference with existing studies can be further clarified. In the introduction part, this work mentioned another jargon --- \"burstiness\" which is confusing. It is not clear how burstiness and locality differ from each other. Besides, the motivation for choosing locality as the research topic is not clear, either. It is interesting to see more elaborations on how the hypothesis is derived.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the detailed and thoughtful review, and are happy to see that the reviewer found our theoretical analysis and simulation results insightful. \n\nWe describe how we will address the second weakness in the general author rebuttal. We also respond to the question about the choice of architecture by showing that a similar reasoning gap appears for multiple different architectures."}, {"review_id": "2e6dQWgCCE", "reviewer": "Reviewer_fiMT", "summary": "This paper provides a theoretical analysis of situations in which chain-of-thought reasoning should be helpful. They do this by considering the task of predicting variable values in a Bayes net. Specifically, it is a Bayes net where child nodes are a nearly-deterministic function of their parents. During training, the network sees sets of nodes and is asked to predict the value of a target node. At evaluation time, the network is asked to predict a held-out target node based on another held-out node. \n\nThey compare three approaches: (a) direct prediction, where the target node is predicted immediately (b) scaffolded prediction, where the model is prompted to predict all the nodes between the source node and target node, and (c) free prediction, where the model chooses itself which intermediate nodes to generate. \n\nThey find that in Bayes nets where relevant local variables are observed near each other, scaffolded prediction and free generation outperform direct prediction. If the observations shown are not relevant to the task, all approaches do poorly. If observations are not locally structured, scaffolded generation does well, but we don't see a benefit from free generation.\n\nThey show theoretically that in this setting \"chain-of-thought\" (i.e. scaffolded generation) produce better predictions and back this up with empirical tests.", "questions": "In Section 3, line 189, should \"$p_{obs}$ only assigns non-zero probability to non-adjacent variable pairs\" say \"adjacent\" not \"non-adjacent\"?\n\nI'm not sure I fully understood the significance and takeaways of the analysis and experiments. I've summarized my understanding below, but please correct me if I'm misunderstanding:\n\nIn the theoretical analysis, my intuitive understanding of the result is that if your training data consists of only adjacent pairs, then when you try to evaluate on non-adjacent pairs a perfect estimator will be very wrong (since those samples are never seen, so it will default to a uniform prior).  On the other hand, if you predict probabilities of non-adjacent pairs by chaining a set of probabilities for adjacent pairs, then each term in the chain is in-distribution and you’ll get a better estimate.  Is that the correct intuition? If so, (a) is there any way to make the intuition behind the result clearer, and (b) could you maybe make a higher analogy with language (e.g. explaining what a “chain” of variables would look like in language, what it means for training data to consist mostly of adjacent pairs, etc.)\n\nIt seems like reasoning working well consists of two thing: (A) the model must be able to produce a reasoning trace which is relevant to the task at hand, and (B) the model must be able to use the reasoning to produce a better final answer. \n* It seems like the “scaffolded” condition checks if (B) is true, and the “free generation” condition checks if both (A) and (B) are true. The theoretical results suggest that (B) should is true but don’t touch on (A). Is there any theoretical reason to think (A) should be true primarily for locally-structured data? Or is the intuition just that locally-structured observations will bias the model towards generating intermediate variables easy to predict accurately b/c the model is conditioning on local context and are relevant to the task at hand?\n", "limitations": "Limitations are adequately addressed.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "Originality/significance: I am not familiar with theory in this area, but this appears to be a new and exciting result. It could be useful for the field by providing people with intuition about what types of datasets are promising candidates to use with chain of thought.\nQuality/clarity: They present theory and complementary empirical analysis. They consider a few different forms of reasoning and a few different types of observation frequency structures to confirm that their hypotheses hold across these conditions.", "weaknesses": "* It took a long time to understand the intuition behind how the theoretical and empirical results relate to the claims about reasoning in sequence models. Possibly this could be made clearer?\n* I wish there was an analysis of how accurate the intermediate reasoning steps were in the different conditions (scaffolded vs free generation).\n* The experiments look at conditions where each variable's value is nearly deterministic based on its parents. I wish there was either an analysis of what happens when this is not true or a discussion of whether the types of natural language tasks where chain of thought is most helpful share this nearly-deterministic property.\n* The experiments average over 10 Monte Carlo rollouts for the scaffolded and free generation cases. I wish there was an analysis of how chain of thought compares to direct prediction in the case of a single rollout, which is often the case being considered in language models.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their detailed review. We appreciate that the reviewer found the paper’s result new and exciting, and that they thought it provides useful intuition about when chain-of-thought is useful.\n\nWe respond to the weakness about variable values being nearly deterministic given parents in the general author response, as well as the comment about the experiments averaging over 10 Monte Carlo rollouts. We also respond to the remaining questions below.\n\n> In the theoretical analysis, my intuitive understanding of the result is that if your training data consists of only adjacent pairs, then when you try to evaluate on non-adjacent pairs a perfect estimator will be very wrong (since those samples are never seen, so it will default to a uniform prior). On the other hand, if you predict probabilities of non-adjacent pairs by chaining a set of probabilities for adjacent pairs, then each term in the chain is in-distribution and you’ll get a better estimate. Is that the correct intuition? If so, (a) is there any way to make the intuition behind the result clearer, and (b) could you maybe make a higher analogy with language (e.g. explaining what a “chain” of variables would look like in language, what it means for training data to consist mostly of adjacent pairs, etc.)\n\nYes, that is exactly the right intuition. The perfect estimator, with respect to the risk defined in the paper, will default to the uniform prior for non-adjacent pairs. When we chain the risk minimizer’s estimates of adjacent pairs, we indeed make use of “in-distribution” pairs and therefore can reduce bias.\n\nRegarding improving the clarity of the theoretical result, in the revised version of the paper, we can include a figure that illustrates the theoretical formulation more carefully.\n\n> It seems like reasoning working well consists of two thing: (A) the model must be able to produce a reasoning trace which is relevant to the task at hand, and (B) the model must be able to use the reasoning to produce a better final answer.\n\nWe do not have concrete theoretical results for (A). The intuition behind why (A) happens in practice in free generation is that the relevant variables to reason through tend to be close to the observed variable and the training set consists of local clusters. In practice, free generation generates several variables near the observed variable, only some of which are relevant but which are sufficiently relevant in aggregate. It might be possible to prove analogous theoretical results for (A) but we leave a thorough characterization of free generation for future work. \n"}, {"review_id": "C2uy8tvwnA", "reviewer": "Reviewer_tGUi", "summary": "The starting point of this paper is the observation that large language model benefit from chain-of-thought reasoning. Namely, when prompt with a reasoning task, LLMs benefit from generating intermediate steps before reaching the final answer. The paper investigates this phenomenon. The authors hypothesize that this is a result of local structures in the training data where variables that often appear together have strong influence on each other, thus a model can generate chains of local connections and by that obtain relations between remote variables that do often appear together in the training data. To explore this hypothesis, the authors train an LLM on samples from randomly generated Bayes nets and task the model with inferring the conditional probability of one variable in the bayes net given another. They show that when the model is trained on samples that only include a subset of local variables then generating a chain of conditional probabilities involving adjacent variables, \npredicts the conditional probability involving two remote variables whith much higher accuracy than a model that is tasked with predicting the remote relation directly. They refer to this phenomenon as the “reasoning gap”.  In contrast, when the model is trained either on the entire set of variables, or on a subset of variables from an irrelevant locality, that reasoning gap vanishes. They also prove a theoretical guarantee in the special case when the Bayes net is a simple chain of variables. \n", "questions": "Line 139 - shouldn't it be \"adjacent\" instead of \"non-adjacent\"?\nTheorem 3.1 - what is q^hat?", "limitations": "The authors adequately addressed the limitations.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The topic of chain-of-thought reasoning in LLMs has garnered a lot of attention in the community recently. It is important both from a theoretical as well as applicable standpoints to investigate the conditions under which chain-of-thought reasoning is useful. The authors suggest an interesting set of experiments to do that as well as some theoretical work. At least for the model that was used in the experiments, the results and the conclusions are convincing. The paper is well written. ", "weaknesses": "The authors ran extensive experiments, but the evaluation uses only one LLM architecture. To draw conclusions about chain-of-thought reasoning in LLMs in general, I would expect a larger set of model architectures to be part of the experiments. For example, it would be interesting to understand how the performance is influenced by the model’s size. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for raising the important issue of architecture choice. We also appreciate that the reviewer finds the topic of chain-of-thought reasoning important and finds our results convincing.\n\nWe have responded to the reviewer’s point about the choice of architecture, including new results with different architectures, in the main author rebuttal. We respond to other questions below.\n\n> Line 139 - shouldn't it be \"adjacent\" instead of \"non-adjacent\"?\n\nYes, this was a typo. Thank you for catching it.\n\n> Theorem 3.1 - what is q^hat?\n\n$\\hat{q}$ refers to estimators that are constructed from the raw predictions of the risk minimizer $q$. $\\hat{q}$ alone is not defined, but $\\hat{q}_D$ and $\\hat{q}_S$ are estimators we define. See Section 2.2 for definitions of these different estimators.\n"}, {"review_id": "Xv2bVRXLR1", "reviewer": "Reviewer_jyTS", "summary": "This paper aims to investigate in a control and toy setup why it is that zero-shot chain-of-thought reasoning (e.g. prompting a model with \"let's think step by step\" and letting the model output intermediate reasoning traces before generating the final answer) improves downstream performance of language models in reasoning tasks. The authors hypothesise that reasoning is useful (or even necessary) when there is a local structure in the training data. A local structure in the training data here refers to local clusters of variables that directly influence each other in a DAG are observed together. The high-level mapping of this onto real-world experience is that we perceive things that are physically and temporally close, but nonetheless can reason over things that are physically and temporally far away.\n\nThe setup in which the authors investigate this is a Bayes net. Imagine a directed acyclic graph (DAG) of variables, and the task is the predict the probability that one variable (the target) takes a value given that another variable (the input; physically separated from the target variable in the graph) has a certain value. The training setup is such that the learner does not see the target and the input variable together during training, but sees local clusters of variables from the graph. Importantly, these clusters overlap. So for each cluster there is at least one variable that is also in another cluster. The authors then show that a language model that is allowed to freely generate intermediate variables can better predict the target value probability than a model that directly predicts it, but only if the training data is structured in the local way described above. Intuitively, the learner achieves this by generating one of the overlapping variables and then moving between local clusters it has seen from training until it encounters the target variable. The authors also show that the learner's performance does not deteriorate with length of the intermediate variables generated, and that a learner that reasons freely is more data-efficient.\n\nThe authors take these results to conclude that we can expect zero-shot CoT reasoning to help when a learner has to make inferences over things (concepts, topics, you name it) that did not co-occur directly in training, but can be connected through things that did co-occur.", "questions": "Most important questions are listed in weaknesses. Other questions that are less important here:\n- Should line 138 say it only assigns non-zero probability to **adjacent** pars and not **non-adjacent** pairs as stated now?\n- I think the first control condition can benefit from some more explanation; are the values still from the right Bayes net and only the local structure is wrong? I.e. is it for example a Bayes net like in Figure 1A but the drawn lines of clusters are not actually local clusters, but the arrows and conditional probabilities are the same?\n- Random remark: Negative scaffolding intuitively seems to map onto this idea from LLM literature where people tried to test the hypothesis that CoT reasoning only works because it allows the model to output extra tokens. Tested with a control condition where they generate random tokens and then ask for the answer and then show that this works worse than CoT, meaning that the actual information the model outputs in its reasoning traces is important for performance.\n\n", "limitations": "The limitations are adequately addressed, but I think the authors should be more explicit about about how well this setup maps onto real language models and reasoning, focusing also on the requirement of overlapping clusters, and where the setup simplified things compared to real-world situations.", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper is written in an exceptionally clear way, it's a pleasure to read. Additionally, it's one of those rare papers that is able to convincingly connect a very theoretical, toy, controlled result to a real-world phenomenon that we, as of yet, understand poorly. I feel like I understand zero-shot CoT better after reading this paper, and am very excited about follow-up work in this direction.\n\nOther strengths:\n- the authors have a simple theoretical result that helps shape intuitions before diving into the experimental section\n- the authors convincingly apply control conditions to isolate the effect of the locality of the training experience, showing the same thing does not show up when there is no locality or the locality is \"wrong\" (clusters are from another DAG, meaning they are not actually local)\n- the results are very clear; there is a reasoning gap for direction prediction versus reasoning when there is a locality in the variables encountered during training\n- the authors additionally show benefits of this type of training data structure; data-efficiency\n- the authors' conclusion is convincing: reasoning can help when a learner needs to connect concepts that have not directly been seen during training, but those concepts are connected through other concepts that have been seen together", "weaknesses": "My main point of weakness with this paper is that the hypothesised connection to actual zero-shot CoT reasoning in SotA LMs, and with it, actual reasoning done by humans is not described explicitly enough. The authors cite Chan et al. (2022) here to be similar to their work (\"Data distributional properties drive emergent ..\"), but I found the connection between that toy setup and real language slightly more convincing because they use a Zipfian distribution (which the vocabulary in language also follows to trade-off the speaker and listener effort due to ambiguity). So my question here is; how exactly does your setup relate to real-world language; what kind of data might we find these local structures where variables are connected through intermediate variables but not directly co-occur; what do the variables refer to in language? Can you give an example? And if the example is topics, can you work that example out a bit more clearly? Don't get me wrong here, I find the connection convincing, but I think the paper can benefit from some explicit reasoning about the connection of the setup to real-world language. In a sense, the setup in the paper works because the model can just generate variables randomly until it encounters the target variable, whereas in real-world reasoning arguably the intermediate reasoning steps are connected through some high-level or abstract similarity.\n\nRelatedly, it seems like a very important factor for reasoning like presented in the paper here to work is the overlapping clusters; what happens if not every cluster overlaps, or if overlapping variables are dropped out more often? Do you think people can make \"reasoning jumps\" through language between clusters of variables that do not overlap? To put it differently; perhaps when humans (and language models) do not observe some variable as both a part of cluster 1 and cluster 2, they can still \"jump\" between those clusters due to some abstract similarity between the two (e.g. a latent variable connection instead of an actual overlapping cluster).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thoughtful and supportive review. We are glad that the reviewer found our paper to be a pleasure to read and that they feel they understand zero-shot chain-of-thought better having read it.\n\nWe have responded to the main weakness the reviewer identified, about the connection to actual CoT reasoning, in the main author rebuttal, but we also provide more specific responses below, along with responses to other points the reviewer brought up.\n\n> So my question here is; how exactly does your setup relate to real-world language; what kind of data might we find these local structures where variables are connected through intermediate variables but not directly co-occur; what do the variables refer to in language? Can you give an example? And if the example is topics, can you work that example out a bit more clearly? Don't get me wrong here, I find the connection convincing, but I think the paper can benefit from some explicit reasoning about the connection of the setup to real-world language. \n\nWe will revise the paper to include more discussion of the connection between real-world reasoning and our setting. We will consider a detailed example to make the effect of topic structure clearer. For example, Wikipedia articles tend to mention the capital cities of countries and the climate of cities, but few articles directly talk about the climate of a country’s capital. If we were to ask a model trained on Wikipedia “What is the climate of France’s capital?” it would likely fail to answer directly. However, “France,” “capital,” and “Paris” co-occur frequently in the training set and “Paris” and “Oceanic climate” co-occur. By working through the intermediate reasoning step “Paris is the capital of France”, the language model should be able to answer the question correctly. It might produce a chain of thought like “The capital of France is Paris. The climate of Paris is oceanic. So the climate of France’s capital is oceanic.”\n\n> In a sense, the setup in the paper works because the model can just generate variables randomly until it encounters the target variable, whereas in real-world reasoning arguably the intermediate reasoning steps are connected through some high-level or abstract similarity. \n\nWe agree with this point: locality is probably not the only factor making reasoning useful in natural language. Seeing examples of reasoning traces in the training corpus might lead the model to learn reasoning strategies that make use of high-level similarities between topics. Even more importantly, few-shot in-context-learning likely helps models generate relevant variables for CoT. (Here we studied only the 0-shot case.) This is an interesting direction for future research.\n\n> Relatedly, it seems like a very important factor for reasoning like presented in the paper here to work is the overlapping clusters; what happens if not every cluster overlaps, or if overlapping variables are dropped out more often? Do you think people can make \"reasoning jumps\" through language between clusters of variables that do not overlap? To put it differently; perhaps when humans (and language models) do not observe some variable as both a part of cluster 1 and cluster 2, they can still \"jump\" between those clusters due to some abstract similarity between the two (e.g. a latent variable connection instead of an actual overlapping cluster).\n\nYes, one major difference between natural language and our setting is that natural language allows us to make abstract statements which can connect concrete facts in novel and unexpected ways. For instance, statistical information about predicates may influence joint probabilities of a variety of propositions that include them. While the focus of this work was to find a minimal case in which outputting extra information between a “question” and “answer” helps to produce better answers, the question of how abstract knowledge might enable better reasoning is an interesting direction for future work. We will update the discussion to mention this direction.\n\n> I think the first control condition can benefit from some more explanation; are the values still from the right Bayes net and only the local structure is wrong?\n\nYes, that is correct. The values of the variables are still taken from the right Bayes net, but the local neighborhoods are based on a different Bayes net with a different structure. We will make this clearer in the paper.\n\n> Random remark: Negative scaffolding intuitively seems to map onto this idea from LLM literature where people tried to test the hypothesis that CoT reasoning only works because it allows the model to output extra tokens. Tested with a control condition where they generate random tokens and then ask for the answer and then show that this works worse than CoT, meaning that the actual information the model outputs in its reasoning traces is important for performance.\n\nGreat point! Simply outputting extra tokens is not helpful in our setting. Step-by-step reasoning only works when the steps are relevant to the prediction task at hand. We will make this connection in the revision.\n"}]

Author rebuttal:
We thank the reviewers for their thoughtful comments on this paper. These comments have informed additional analyses and clarifications.

# Architecture
Reviewers Jbx9 and tGUI ask about our choice of architecture. Jbx9 asks why we chose a smaller model given that models smaller than GPT-3 often fail at step-by-step reasoning, while reviewer tGUi identifies our use of only one architecture as a weakness.

To these points, we first point out that our theoretical analysis applies to any autoregressive empirical risk minimizer. We prove that a reasoning gap should exist between direct prediction and scaffolded generation regardless of the specific architecture (for simple world distributions). We can interpret our learning curve results as evaluating whether a reasoning gap exists at different levels of empirical risk, or equivalently perplexity. The simulated data we trained transformers on is much simpler than natural language, so it is expected that a smaller model is capable of learning the data well enough for reasoning to be beneficial. Figure 1 in the PDF shows the mean perplexity on a validation dataset across Bayes nets vs. the size of the reasoning gap for each checkpoint in the geometrically-sized local neighborhood model. These results show that a model must achieve a certain perplexity before the reasoning gap emerges, but it exists for a range of perplexities achievable by our architecture.

We have also run additional simulations in which we train different transformer architectures on geometrically-sized local neighborhoods from the same Bayes nets. We use a smaller model (4,473,600 parameters), a larger model (86,628,864 parameters, the base gpt-2 architecture) and model with a similar number of parameters, but larger embeddings and fewer layers (39,887,872 parameters). We also use a tiny model which is too small to learn the distribution of the data (8,644 parameters). All models except for the tiny model exhibit similar reasoning gaps, suggesting that our findings are not specific to one architecture. Performance across architectures and estimators is reported in Figure 2 of the PDF, which we will include in the appendix of the paper.

# Number of samples
Reviewer fiMT was interested in seeing results with a single Monte Carlo sample used in the scaffolded and free generation estimators. We have run this analysis for all numbers of samples between 1 and 10 and reported the results in Figure 3 of the PDF.

While we used the mean squared error as a practical measure of the error of a language model, we could decompose MSE into bias and variance. The free and scaffolded generation estimators have lower bias, but higher variance, than direct prediction. Free and scaffolded generation have higher MSE compared to direct prediction with one sample, but averaging over several samples (at least 3 in our setting) leads them to have lower MSE than direct prediction. This finding has bearing on when we should expect generating multiple chains of thought, as is done in confidence methods (e.g. Wang et al., 2022), to be valuable. The specifics of the bias-variance trade-off depend on the underlying stochasticity of the Bayes net, so different environments might call for different numbers of samples. We will discuss this result in the paper.

# Connection to real-world reasoning
Reviewers Jbx9, fiMT, and jyTS mentioned that the connection between our setting and real-world reasoning in humans and language models was not clear in the paper. We are ultimately interested in studying the improvement at answering questions resulting from generating intermediate information between a question and its answer. Our setting of inference for held-out pairs of variables in a Bayes net is a minimal case where this happens. For example, in a simple Bayes net with three variables, A: it rained last night, B: the grass is wet, and C: mowing the lawn will be difficult, reasoning through the intermediate variable B might be necessary if A and C have not been encountered together directly in training data. We will revise the introduction to make the connection clearer.

Reviewer fiMT asks about our choice to favor strong dependencies in generating Bayes nets. We chose to generate data this way to ensure that there are non-adjacent pairs of variables with high mutual information. If we sampled probabilities uniformly, mutual information would decay rapidly with distance and conditional probabilities for held-out pairs would be almost identical to marginal probabilities. Still, our Bayes nets have considerable randomness as the Beta distribution we use generates conditional probabilities between 0.1 and 0.9 32.7% of the time. We expect reasoning to be most useful in environments with strong dependencies, like in math word problems where truth values of statements are deterministic. An alternative way of looking at this is that strong long-range dependencies are themselves a precondition for reasoning – otherwise using the marginal frequency of the conclusion is enough.

# Clarifications
We will clarify the motivation behind our choice to study locality and how it differs from related ideas like burstiness. While burstiness concerns the distribution of a single class over time, locality is about which classes co-occur with each other. Co-occurrence patterns are relevant because reasoning connects different concepts.

We also thank reviewers fiMT and tGUi for identifying typos and unclear points in the paper. In particular, we have fixed the typo on line 138/139 where “non-adjacent” should be “adjacent”.

We once again thank the reviewers for taking the time to give detailed feedback on this work. Their comments have substantially improved this paper.

# References
Wang, X., Wei, J., Schuurmans, D., Le, Q. V., Chi, E. H., Narang, S., ... & Zhou, D. (2022, September). Self-Consistency Improves Chain of Thought Reasoning in Language Models. In The Eleventh International Conference on Learning Representations.

Meta-review: This paper aims to answer a very fundamental question -- in what situation chain-of-thought reasoning should be helpful. It explores this problem by considering the task of predicting variable values in a Bayes net, where child nodes are a nearly-deterministic function of their parents. The task is giving the values of a set of nodes and predicting the value of a target node. 
It also compares three approaches: (a) direct prediction, where the target node is predicted immediately (b) scaffolded prediction, where the model is prompted to predict all the nodes between the source node and target node, and (c) free prediction, where the model chooses itself which intermediate nodes to generate. 

The result shows that 
1. if relevant local variables are observed near each other, scaffolded prediction and free generation outperform direct prediction. 
2. If the observations shown are not relevant to the task, all approaches do poorly. 
3. If observations are not locally structured, scaffolded generation does well, but there is no benefit from free generation. Theoretically analysis shows that in this setting "chain-of-thought" (i.e. scaffolded generation) produces better predictions and empirical tests also confirms.


Strengths:
1. The result is significant in providing people with intuition about what types of datasets are promising candidates to use with chain of thought. 
2. The approach is novel, and the theory and complementary empirical analysis are solid.

Weaknesses:
1. lack of a practical way to measure the locality of a dataset
2. the experiment is based on the case where each variable's value is nearly deterministic based on its parents. It is not clear how that generalizes to real datasets (e.g. language tasks)
3. while theoretical arguments can often be made with smaller model sizes, the connection of these explanations to observed phenomenon on larger models seems like it would require actually experimenting with larger models.
Decision: Accept (oral)