PaperlayerView exact revision on arXiv

Source-linked AI summary

Why think step by step? Reasoning emerges from the locality of experience

Ben Prystawski, Michael Y. Li, Noah D. Goodman

arXiv:2304.03843v3cs.AIcs.CLcs.LG

TL;DR

The paper asks why chain-of-thought reasoning helps language models when it adds no new data. It formalizes and tests whether locally structured training observations let models chain intermediate dependencies to estimate relationships not seen together, finding that reasoning helps specifically under those conditions and can improve data efficiency.

  • Problem

    The paper addresses why step-by-step reasoning improves inference despite providing no additional data, focusing on whether local training-data structure explains the benefit.

  • Method

    The authors prove a reasoning gap for autoregressive estimators trained on local samples from chains and test transformers trained on partial observations from Bayes nets.

  • Results

    Intermediate reasoning improves conditional-probability estimation when training data is locally structured, whereas it does not improve performance when all variables are included or locality is wrong.

  • Takeaways & Limitations

    Reasoning is most useful for connecting concepts that rarely co-occur directly but are linked through dependencies represented locally in training data.

  • Takeaways & Limitations

    The theory and experiments are framed around conditional inference in Bayesian networks with learners that may observe only locally structured variable subsets.

Abstract

from arXiv · show

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.

1 Introduction

The paper asks why step-by-step reasoning improves inference despite adding no new data, proposing that its value comes from local structure in training data. It combines theory and experiments to show that intermediate variables help when relevant dependencies are learned locally.

  • Motivation: The paper investigates why generating intermediate variables can improve language-model inference despite providing no additional information from the world.The motivating question is why reasoning helps at all when it does not add new data.
  • Hypothesis: The authors hypothesize that reasoning works because training data contains local clusters of frequently co-occurring, strongly dependent concepts.Natural-language documents typically concern a few closely interconnected topics, paralleling local structure in human experience.
  • Mechanism: Reasoning through an intermediate variable can estimate P(C|A) by chaining local relationships when A and C are rarely observed together.For example, stating that France’s capital is Paris can connect country–capital and city–climate relationships.
  • Approach: The paper formalizes the problem, proves a reasoning gap for local samples from a chain, and evaluates autoregressive transformers trained on structured synthetic data.The experiments compare conditional-probability estimation with and without intermediate reasoning for variable pairs not observed together in training.
  • Findings: Reasoning improves estimation when training data is locally structured, while locally structured data combined with self-generated intermediate variables is more data-efficient than training on all variables.The results connect reasoning effectiveness to the statistical organization of training observations.

2 Task setup

The task models learning conditional probabilities from partial observations of a Bayes net. Models are trained on locally selected variable subsets and evaluated using estimators that either predict directly or generate intermediate variables first.

  • Underlying model: The framework assumes an underlying Bayes net whose variables take values from a finite support.Training sequences contain variable indices followed by their corresponding values.
  • Training data: An observation distribution selects subsets of variables, so training samples expose the learner to only particular joint subsets rather than all variables together.The selected variables appear in random order, and their values are sampled from the Bayes-net distribution.
  • Training data: Local observation distributions select variables that are close together in the Bayes-net graph, enabling the model to learn strong local dependencies.This setup is intended to reflect statistical structure in human experience.
  • Estimators: Direct prediction estimates the target conditional probability immediately from the model and serves as the baseline without reasoning.It uses the probability directly output by the autoregressive model.
  • Estimators: Scaffolded generation supplies an ordered set of intermediate variables, estimates them sequentially, and approximately marginalizes over their values before estimating the target.The scaffold variables collectively d-separate the observed variable from the target variable.
  • Estimators: Free generation lets the model choose intermediate variable indices and values, sampling until it generates the target variable.It tests whether useful reasoning steps emerge spontaneously from the trained model.

3 Theoretical results

The paper proves that, under local training observations from a chain, reasoning through intermediate variables can yield lower-bias conditional estimates than direct prediction. The result depends on chaining learned local dependencies, while practical estimators may default toward marginal distributions for unseen pairs.

  • Assumptions: Local observations contain only adjacent variable pairs, so non-adjacent conditional relationships are not directly represented in training.The observation distribution assigns nonzero probability only to adjacent pairs.
  • Theoretical result: The risk-minimizing model exhibits a reasoning gap: indirect estimates through intermediate variables have lower bias than direct estimates for non-adjacent variables.The proof applies to a sequence model trained on adjacent variable pairs from a directed chain.
  • Proof strategy: For adjacent pairs, the risk minimizer interpolates between the true conditional distribution and the uniform distribution, whereas non-adjacent estimates equal the uniform distribution.This characterization follows from cross-entropy terms involving the data distribution and uniform regularization.
  • Theoretical result: Scaffolded estimation reduces bias by chaining learned conditional probabilities across intermediate variables and marginalizing over them.The scaffolded estimator is a mixture of the true non-adjacent conditional and the uniform distribution, with mixture weight λ ∈ (0, 1).
  • Scope: In practice, density estimators may approximate held-out conditional distributions with marginal distributions, limiting the theorem’s idealized assumptions.The paper relaxes some assumptions by considering risk minimizers that mix true conditionals with marginals.

4 Experimental methods

The experiments train transformer density estimators on synthetic Bayes-net data whose observation structure varies in locality, dropout, and held-out pairs. They compare direct, free, scaffolded, and negative-scaffolded inference using conditional-probability MSE.

  • Experimental design: The study tests whether locally structured training data determines when scaffolded or free generation outperforms direct prediction.Models are evaluated on conditional inference for variable pairs not observed together during training.
  • Evaluation: Mean squared error is averaged over 10 Monte Carlo samples for estimators using intermediate variables, reducing variance so residual error primarily reflects bias.The estimators include direct, free, scaffolded, and negative-scaffolded generation implemented through language-model sampling.
  • Training data: Training samples contain subsets of Bayes-net variables selected from observation distributions rather than complete assignments.The observation process is defined over subsets and is designed to model partial views of the variables.
  • Training data: Locality is implemented by sampling a central variable and including variables within distance k, with k drawn from geometric or Zipfian distributions.This creates neighborhoods whose sizes vary across samples.
  • Training data: Variable dropout removes local variables with probability 0.2, while held-out pairs are prevented from co-occurring across the training data.Held-out-pair accuracy is measured by mean squared error between estimated and true conditional probabilities.
  • Controls: The experiment compares local observation structure against mismatched-neighborhood and fully observed controls to test whether co-occurrence reflects dependency structure.The fully observed control includes nearly all variables except one randomly dropped member of each held-out pair.
  • Results: Both free and scaffolded generation significantly outperform direct prediction for held-out high-mutual-information pairs under locally structured training.Figure 2 reports mean squared error with 95% confidence intervals.
  • Implementation: The transformer is trained from random initialization for 300,000 gradient steps on 921,600,000 tokens.The architecture uses 512-dimensional embeddings, 10 layers, and 8 attention heads.

5 Results

Reasoning improves conditional-probability estimation when training observations preserve the dependencies’ local structure. Under these conditions, self-generated intermediate variables create a reasoning gap and can substantially reduce the training required for accurate estimates.

  • 5 Results: Free and scaffolded generation have high estimation error with few Monte Carlo samples, but error quickly decreases as samples increase.Resampling intermediate variables parallels self-consistency methods that resample reasoning traces and aggregate answers.
  • 5.1 When reasoning helps: Free generation outperforms direct prediction when training data has the correct locality structure, while irrelevant intermediate variables provide less benefit.Both scaffolded and free generation significantly outperform direct prediction under locally structured observations, and relevant intermediate variables outperform negative scaffolding.
  • 5.1 When reasoning helps: Free generation does not substantially outperform direct prediction when training data is fully observed.With fully observed data, both estimators improve slowly and perform almost identically.
  • 5.1 When reasoning helps: 70% of locally trained free-generation traces d-separate the observed variable from the target, compared with 34% under incorrect locality structure.Fully observed training also produces d-separating traces 69% of the time, likely because it generates many variables.
  • 5.2 Data complexity and reasoning: Free generation matches true conditional probabilities after about 120 million tokens, while fully observed direct prediction requires over 3 times as much training for comparable performance.Local training with free generation achieves the best reported performance, although sufficiently large transformers can eventually memorize relationships from fully observed data.
  • 5.1 When reasoning helps: Direct prediction is nearly perfect when variable pairs co-occur frequently, whereas poor conditional estimates can instead track target marginals.These results indicate that frequent co-occurrence can remove the need for intermediate reasoning, while non-local variables lack reliable conditional steps.

6 Discussion

The paper argues that chain-of-thought reasoning improves conditional-probability estimates when training observations have local dependency structure, while its scope is limited across prompting methods and simple propositional worlds. The theoretical setup formalizes local neighborhoods and proves a reasoning gap under particular locality conditions.

  • Chain-of-thought reasoning can outperform direct prediction when training data has local structure, but not when locality is wrong or all variables are observed together.Models do not reliably learn chainable conditional probabilities under the wrong locality structure.
  • Locally structured data combined with intermediate reasoning can achieve accurate conditional-probability matching with less training than exposure to all variables.
  • Understanding human observation structure and abstraction remains future work, including how abstract reasoning steps can be selected and learned.
  • The findings primarily apply to zero-shot chain-of-thought prompting and simple propositional worlds, while richer structured reasoning may require more expressive languages.
  • The paper’s theoretical analysis proves a reasoning gap for risk minimizers trained on local samples from a directed chain.The result concerns a cross-entropy objective with entropy regularization.
  • The formal setup observes independent local neighborhoods of size two, with variable values following their indices.
  • Only adjacent variables may appear together in the local observation distribution, restricting the model to a subset of graphical-model dependencies.This observation property is identified as the source of the reasoning gap.

A.3 Main Theorem

The theorem characterizes the risk minimizer for locally observed adjacent variables and shows a reasoning gap: indirect estimates through intermediate variables can have lower bias than direct estimates for non-adjacent variables.

  • Main result: The risk minimizer q∗ exhibits a “reasoning gap” under cross-entropy loss with entropy regularization.The result is established for the distribution induced by the observation and data distributions.
  • Adjacent pairs: For adjacent variables, q∗ interpolates between the true conditional distribution and the uniform distribution.This follows from combining cross-entropy terms against the data conditional and the uniform distribution.
  • Non-adjacent pairs: For non-adjacent variables, q∗ predicts the uniform distribution because those variables never appear together in the observation distribution.The risk therefore contains only the entropy-regularization contribution for their direct conditional.
  • Bias comparison: Reasoning through intermediate variables has lower bias than direct prediction for non-adjacent variables under the theorem’s local-observation setting.The scaffolded estimator explicitly marginalizes over intermediate variables using learned adjacent conditional probabilities.
  • Bias comparison: The proof characterizes scaffolded estimates as strict convex combinations of true conditionals and the uniform distribution.For the distance-two case, the mixture coefficient is λ = (1 −λ3,2)(1 −λ2,1).
  • Assumptions: The doubly stochastic assumption can potentially be relaxed if the risk minimizer interpolates between marginal and true conditional distributions.This is presented as an alternative assumption for extending the bias result.

B Pseudocode for data generation

The data-generation procedure first constructs random Bayes nets, then samples local neighborhoods while selectively removing variables to create partially observed training examples.

  • Bayes-net construction: Algorithm 1 creates a directed acyclic graph by randomly adding edges while avoiding cycles, then assigns conditional probability tables.The resulting graph and tables define the Bayes net used for data generation.
  • Variable selection: Algorithm 2 samples a central variable and a distance, then selects variables within that graph neighborhood.The distance is drawn from a geometric or Zipfian distribution.
  • Variable selection: Each selected variable is independently removed with probability 0.2 before held-out pairs are enforced.If both variables in a held-out pair remain, one is randomly removed.

C Full sample of training data

Training examples are serialized subsets of Bayes-net variables, while evaluation prompts estimate target probabilities either directly or by sampling intermediate variables.

  • Training samples: A sample is generated from a local neighborhood of a Bayes net and represented in string format for model training.The full training set contains 1,000,000 concatenated samples.
  • Bayes-net construction: The Bayes-net generator creates N vertices, adds M cycle-free edges, and assigns conditional probability tables in topological order.The resulting tables and graph define the Bayesian network distribution.
  • Variable selection: Variable-selection pseudocode retains nodes within a sampled distance of a central variable and removes selected held-out variables.The procedure operationalizes the observation distribution used for local samples.
  • Direct prediction: Direct prediction prompts the model with an observed variable and target variable, then converts the target token’s softmax probability into an estimate.For binary targets, the probability assigned to the token ‘1’ is used.
  • Scaffolded generation: Scaffolded generation samples values for precomputed intermediate variables before estimating the target probability.The process averages target probabilities over 10 sampled scaffold assignments for a Monte Carlo estimate.
  • Free generation: Free generation samples both intermediate variable names and their values until the target variable is produced.Target probabilities are again averaged over 10 intermediate-variable samples.

E Training details

The experiments use a compact GPT-2-style transformer, trained with Adam on fixed-length token batches for 300,000 gradient steps.

  • Architecture: The model has 512-dimensional embeddings, 10 layers, 8 attention heads, and 32,573,440 parameters.A Byte Pair Encoding tokenizer fitted to the samples contains 356 unique tokens.
  • Optimization: Training uses 1024-token chunks, batches of 3, and 3072 tokens per gradient step.Adam uses an initial learning rate of 10^-3 with beta values 0.9 and 0.999.
  • Training budget: Models train for 300,000 gradient steps on Nvidia Titan Xp GPUs, requiring approximately 20 hours each.

F Comparison of reasoning gaps across different architectures

Across alternative transformer architectures trained on geometrically sized local neighborhoods, reasoning-gap results are broadly consistent, while an undersized model fails to match the distribution.

  • Results are very similar across the alternative architectures, except the tiny architecture, which fails to match the distribution.The comparison covers smaller, larger, wider, and tiny architectures alongside the original model.
  • The architecture comparison measures mean squared error by architecture type and estimator on the same local-neighborhood training data.Error bars indicate 95% confidence intervals.
  • Five architectures are compared using embedding size, layer count, and attention-head count.Table 3 reports these three architectural dimensions for each model.
  • With one or two Monte Carlo samples, free and scaffolded generation have higher mean squared error than direct prediction.The comparison concerns models trained on geometrically sized local neighborhoods.

H Data efficiency of fully observed training with no held-out pairs

Fully observed training can eventually outperform locally structured training with reasoning, but local structure reaches comparable performance with substantially less training.

  • In the fully observed condition, the transformer can directly memorize the true conditional probabilities.Despite this access, direct prediction takes longer to match free generation trained on locally structured data.
  • Figure 6 compares mean squared error learning curves for direct and free prediction under locally structured and fully observed training conditions.The fully observed condition contains no held-out pairs.
  • 650 million tokens are needed for direct prediction with fully observed training to reach the performance free generation reaches after about 200 million tokens on geometric local neighborhoods.Direct prediction with fully observed data can ultimately outperform free generation with locally structured data.
Loading 2304.03843v3…