PaperlayerView exact revision on arXiv

Source-linked AI summary

Unveiling the Statistical Foundations of Chain-of-Thought Prompting Methods

Xinyang Hu, Fengzhuo Zhang, Siyu Chen, Zhuoran Yang

arXiv:2408.14511v2cs.AIcs.CLcs.LGmath.STstat.MLstat.TH

TL;DR

Despite CoT’s success on multi-step reasoning, its theoretical basis and comparison with vanilla ICL remain insufficiently understood. The paper analyzes CoT under a latent-variable model, finding that it approximately yields Bayesian estimation and that its statistical error separates into pretraining and prompting components.

  • Problem

    Despite CoT’s empirical success on multi-step reasoning, the theoretical basis of its effectiveness and its comparison with vanilla ICL remain insufficiently understood.

    Source: §1 · p. 4

  • Method

    The paper analyzes CoT in a multi-step latent-variable model, characterizing its estimator as Bayesian model averaging and decomposing its statistical error into pretraining and prompting errors.

    Source: §1 · p. 5

  • Results

    CoT prompting approximately produces a Bayesian estimator, and its statistical error separates into pretraining and prompting components, with prompting error decreasing exponentially as demonstrations increase.

    Source: §1 · p. 5, §8 · p. 46

  • Takeaways & Limitations

    The attention mechanism approximately encodes Bayesian model averaging in the transformer, while CoT’s expected advantage over vanilla ICL does not ensure gains for every task or prompt.

    Source: §1 · p. 5

    CoT need not outperform vanilla ICL on every task or prompt, particularly when intermediate reasoning paths are insufficiently informative.

    Source: §5.3 · p. 32

Abstract

from arXiv · show

Chain-of-Thought (CoT) prompting and its variants have gained popularity as effective methods for solving multi-step reasoning problems using pretrained large language models (LLMs). In this work, we analyze CoT prompting from a statistical estimation perspective, providing a comprehensive characterization of its sample complexity. To this end, we introduce a multi-step latent variable model that encapsulates the reasoning process, where the latent variable encodes the task information. Under this framework, we demonstrate that when the pretraining dataset is sufficiently large, the estimator formed by CoT prompting is equivalent to a Bayesian estimator. This estimator effectively solves the multi-step reasoning problem by aggregating a posterior distribution inferred from the demonstration examples in the prompt. Moreover, we prove that the statistical error of the CoT estimator can be decomposed into two main components: (i) a prompting error, which arises from inferring the true task using CoT prompts, and (ii) the statistical error of the pretrained LLM. We establish that, under appropriate assumptions, the prompting error decays exponentially to zero as the number of demonstrations increases. Additionally, we explicitly characterize the approximation and generalization errors of the pretrained LLM. Notably, we construct a transformer model that approximates the target distribution of the multi-step reasoning problem with an error that decreases exponentially in the number of transformer blocks. Our analysis extends to other variants of CoT, including Self-Consistent CoT, Tree-of-Thought, and Selection-Inference, offering a broad perspective on the efficacy of these methods. We also provide numerical experiments to validate the theoretical findings.

1 Introduction

The introduction frames CoT as an under-theorized approach to multi-step reasoning and develops a statistical account of its estimators, errors, and relation to ICL.

1 Introduction

  • The paper targets limited theoretical understanding of why CoT works, how it compares with vanilla ICL, and how reasoning steps and transformer architecture contribute.Source: §1 · p. 4
  • CoT prompting is modeled as Bayesian model averaging: demonstrations inform a posterior over the latent task, which is aggregated to generate the output.The model represents reasoning with H + 1 variables, including input, intermediate steps, and output.Source: §1 · p. 5
  • The CoT estimator’s statistical error separates into pretraining and prompting errors, with the pretraining component further divided into approximation and generalization errors.The paper analyzes prompting error for CoT variants using last-iterate and average-iterate errors.Source: §1 · p. 5
  • The attention mechanism approximately encodes BMA in the transformer, while the architecture also enters the analysis of approximation error.Source: §1 · p. 5
  • CoT is no worse than vanilla ICL in expectation across tasks, but it can perform worse for particular tasks when reasoning paths are insufficiently informative.The paper reports synthetic experiments illustrating this task-specific nuance.Source: §1 · p. 5

2 Related Works

The related-work section situates the paper among research on CoT, ICL, and Bayesian accounts of prompting, emphasizing the need for a statistical analysis of CoT’s pretraining and prompting stages.

CoT Prompting and its Variants

Existing Research on Understanding ICL

  • Empirical ICL studies examine transformer behavior and capability, while theoretical accounts include optimization-based and Bayesian explanations.Source: §2 · p. 7
  • Earlier Bayesian ICL analyses include restrictive HMM or idealized pretraining assumptions; this work extends the BMA framework to multi-step generation and analyzes both pretraining and prompting errors.The comparison is with Zhang et al. (2023a) and He et al. (2024).Source: §2 · pp. 7–8

Existing Research on Understanding CoT

  • Prior CoT research offers empirical insights and theoretical accounts of reasoning improvements and transformer mechanisms.Source: §2 · p. 8
  • The paper adopts a statistical perspective to characterize CoT’s properties across pretraining and prompting, addressing an area it describes as still limited in understanding.Source: §2 · p. 8

3 Background

The background defines autoregressive LLMs, transformer attention, and prompting, then describes ICL and CoT as ways to condition generation on examples and reasoning steps.

Autoregressive LLMs

  • Autoregressive LLMs generate tokens sequentially, conditioning each next-token prediction on the preceding prompt and generated tokens.Source: §3 · pp. 8–9

Transformers and Attention Mechanism

  • Transformer attention uses query-key similarities to weight value vectors, while multi-head attention aggregates outputs from parallel attention functions.Source: §3 · p. 9

LLM Training

  • LLM pretraining maximizes next-token likelihood on text sequences; post-training adapts the model using labeled examples or human feedback.Source: §3 · p. 10

In-Context Learning

  • ICL conditions a fixed-parameter LLM on input-output examples and a new query, allowing it to infer the demonstrated relationship from the prompt.Source: §3 · p. 10

Chain of Thought and its Variants

  • CoT adds intermediate reasoning steps to example prompts for multi-step tasks, and variants use majority voting, tree search, or stepwise selection.Source: §3 · pp. 10–11

4 A Latent Variable View of Multi-Step Reasoning

This section develops a latent-task-variable statistical view of multi-step reasoning and CoT prompting, characterizing CoT as Bayesian model averaging. It examines when transformer attention approximates this estimator and connects the result to kernel and ridge regression consistency.

4.1 A Multi-Step Latent Variable Model

  • The model treats the task as a latent concept that governs task-specific examples and autoregressive reasoning steps; Appendix A extends it beyond the i.i.d. demonstration assumption.Each reasoning step depends on previous steps and the latent task.Source: §4.1 · pp. 13–14

4.2 Pretrained LLM + CoT Prompting

  • CoT’s statistical error has pretraining and prompting components; prompting error depends on the number and informativeness of demonstrations and their alignment with the test query.The prompting error can be decomposed further into query error and in-context error.Source: §4.2 · p. 16

4.3 BMA Interpretation of CoT

  • With population pretraining, sufficient LLM capacity, and a prompt with nonzero pretraining-distribution density, CoT is equivalent to BMA over task-conditioned predictions.The LLM infers a posterior over tasks from the prompt, predicts for each task, then aggregates predictions over that posterior.Source: §4 · p. 11, §4.3 · pp. 16–17

4.4 Attention Approximately Parameterizes BMA

  • For a special feature-space linear dynamical model, transformer attention can encode BMA; under a Gaussian task prior, the task posterior is centered at a ridge estimator.The stated result relies on an invertible feature map and feature mappings that yield the simplified model.Source: §4.4 · pp. 17–18
  • The transformer represents CoT with a copy head, softmax attention, and a positionwise transformation, using demonstration keys and values to generate reasoning steps.Figure 4 illustrates the copy head and attention over demonstration-derived keys and values.Source: §4.4 · pp. 18–19, Figure 4 · p. 20
  • As n grows, the BMA estimator and transformer attention output coincide up to a scaling factor under the proposition’s assumptions.The feature mappings k and v are bounded, ∥v(z)∥2 = 1, and ϕ has finite dimension; λ = n^-2/3.Source: §4.4 · p. 19
  • The attention output is an exponential-kernel Nadaraya–Watson regressor, while the BMA estimator corresponds to ridge regression; both are consistent and converge to the same limit.The analysis extends a similar vanilla-ICL result to CoT’s multi-step autoregressive structure.Source: §4.4 · pp. 19–20

5 Statistical Errors of CoT Prompting

This section analyzes the statistical errors of CoT prompting, decomposing them into pretraining and prompting components and examining how demonstrations affect prompting error. It extends the analysis to variants including ToT and SI, compares CoT with ICL, and considers when intermediate reasoning helps.

5.1 Statistical Errors of Vanilla CoT

  • CoT’s statistical error is bounded by the sum of a pretraining error and a prompting error.The prompting error is defined for the population distribution and is independent of LLM pretraining.Source: §5.1 · pp. 21–22
  • Under task separation and prior coverage, prompting error decays exponentially with demonstrations toward an intrinsic pretraining error.The bound’s dependence includes the separation margin, reasoning depth H, the number of tasks outside the output-equivalent class, and prior coverage; better-covered tasks have smaller prompting error.Source: §5.1 · pp. 22–23
  • When distributions within each output-equivalence class are close, the bound depends on the number of classes rather than all outside tasks, at the cost of slower exponential decay.This refinement assumes within-class similarity alongside separation between classes.Source: §5.1 · pp. 23–24

5.2 Statistical Errors of Variants of CoT

  • The variant analysis assumes zero pretraining error and no query distribution shift, and covers Self-Consistency CoT, Tree-of-Thought, and Selection-Inference.The authors modify Theorem 5.5 to analyze these methods.Source: §5.2 · p. 24

Self-Consistency CoT (SC-COT)

  • SC-CoT draws K independent reasoning paths and returns the majority-vote answer, whose sample mode converges to the population mode as K grows.The method applies selection at the final step, and the paper’s discussion says this explains its effectiveness.Source: Self-Consistency CoT (SC-COT) · pp. 24–25
  • With sufficiently many demonstrations, SC-CoT’s wrong-output probability decreases exponentially in K, and K = Ω(log(|L|/δ)/ϵ) suffices for its sample mode to match the population mode with probability at least 1 − e^−λn/2 − δ.This guarantee assumes a unique population mode with a strictly positive gap ϵ to the second-largest probability mass.Source: Self-Consistency CoT (SC-COT) · pp. 24–25

Tree-of-Thought (ToT)

  • ToT selects reasoning paths using a task-specific value function; its breadth-first-search version samples K continuations per active history and retains the top B histories at each step.At the final step, it outputs the candidate with the highest value; its analysis requires sufficient coverage of optimal reasoning steps.Source: Tree-of-Thought (ToT) · pp. 26–27
  • Under Assumption 5.10 and for sufficiently large n, ToT with BFS and B = 1 has probability at least 1−e^(−nλ*/2) that its probability of outputting a suboptimal reasoning path decreases exponentially with K.Here λ* is the minimum of the stepwise separation values λ_h.Source: Tree-of-Thought (ToT) · p. 28

Selection-Inference (SI)

  • SI decomposes each reasoning step into selecting relevant facts and inferring the next step from those facts (Creswell et al., 2022).The analysis treats SI as a hierarchical extension of CoT.Source: Selection-Inference (SI) · pp. 28, 30
  • With finite Θ, a perfectly pretrained LLM, and Assumption 5.12, SI’s prompting error decays exponentially with n, with λSI = λS + λI + λq reflecting separation in selection and inference.The bound applies to the SI estimator’s output distribution for the test example.Source: Selection-Inference (SI) · p. 31
  • The analysis extends statistical-error results to SC-CoT, ToT, and SI with zero LLM pretraining error; the nonzero-pretraining-error case is deferred to Section 6.Source: Selection-Inference (SI) · p. 31

5.3 Vanilla CoT versus Vanilla ICL and Truncated CoT

  • For any n ≥ 0 with a perfectly pretrained LLM, CoT is at least as good as vanilla ICL on average over tasks and prompts, and including more reasoning steps helps on average.The comparison is an average guarantee, not a pointwise guarantee for every task.Source: §5.3 · p. 32
  • CoT can be worse than ICL for an individual task when intermediate steps are insufficiently informative; on CityEquation, irrelevant but true facts in PI CoT (b) sharply reduced accuracy.The passage reports PI CoT (b) at 2.5% accuracy and says it performed worse than vanilla ICL.Source: §5.3 · pp. 32–33
  • 81.5% accuracy went to informative CoT on CityEquation, while PI CoT versions (a)–(d) scored 70.5%, 2.5%, 66%, and 80%, respectively.The methods were evaluated with 10 demonstrations on 200 random test instances using GPT-4 at temperature zero.Source: §5.3 · p. 33

6 Statistical Errors of CoT with Pretraining Errors

Section 6 characterizes CoT’s statistical error by combining prompting and pretraining analyses, including approximation, generalization, and query-shift effects. It also gives conditions under which transformer approximation improves with depth and the overall error is controlled.

6.1 Setup of LLM Pretraining

  • The pretraining setup fits an autoregressive transformer by maximum likelihood on N trajectories, each containing T examples sampled under the latent-task model.The transformer maps reasoning-step sequences to distributions over the next reasoning step; the setup can be generalized to next-token prediction.Source: §6.1 · pp. 34–36

6.2 Pretraining Error Analysis

  • Pretraining error decomposes into approximation and generalization errors; the latter vanishes as N grows and depends on model complexity, with sequence length entering mildly through a logarithm.The bound assumes bounded reasoning steps and a lower-bounded conditional probability for next-step generation.Source: §6.2 · pp. 37–38

6.3 Transformers as Conditional Distribution Approximators

  • Approximation error decreases exponentially with transformer depth D under smoothness and expressivity conditions, and is independent of t by exploiting permutation invariance across examples.The construction uses separate subnetworks for reasoning steps, while attention leverages invariance to permutations of prior examples.Source: §6.3 · p. 38

6.4 Statistical Error of CoT with Out-of-Distribution Queries

  • The complete CoT error characterization combines prompting error, pretraining error, and query error from distributional shift, under assumptions including mild shift.For finite Θ and κ = O(1), the corollary gives a high-probability bound combining the prompting result with the pretraining bound.Source: §6.4 · p. 40

7 Experiments

Experiments on two-layer neural networks and decision trees show that CoT prompting reduces error with more demonstrations, with its advantage over vanilla ICL depending on the intermediate steps. The results support the paper’s error-decay analysis, while the conclusion summarizes its broader theoretical findings.

7.1 Experiment Settings

  • The experiments train separate transformers for CoT and ICL on sampled regression tasks, then evaluate predictions on new inputs using mean-squared error.Evaluation averages over 100 experiments per n and then over 10 task parameters.Source: §7 · p. 41, §7.1 · p. 42
  • The two tasks are two-layer neural networks and decision trees; their CoT demonstrations include an intermediate step, with NN variants exposing either ReLU(Wx) or v.Decision-tree reasoning steps are the four input coordinates used along the selected path.Source: §7.1 · pp. 41–42

7.2 Experiment Results

  • On both tasks, CoT error falls faster with demonstrations; CoT1 substantially beats ICL on two-layer NNs, while decision-tree CoT learns faster but reaches similar large-n accuracy.At n = 100, both decision-tree models have testing loss around 0.12.Source: §7.2 · pp. 42–43, Figure 11 · p. 43, Figure 12 · p. 44
  • For two-layer NNs, log-MSE is linear through n ≤20 before pretraining error dominates; for decision trees, the linear trend holds through n ≤65.The results describe exponential statistical-error decay up to a pretraining-error floor.Source: §7.2 · p. 43, Figure 11 · p. 43, Figure 12 · p. 44

7.3 Additional Details of Numerical Experiments

  • The numerical experiments use GPT-2-family transformers with a universal read-in and separate read-outs for inputs, intermediate steps, and outputs.For both tasks, the reported models have 12 layers, with task-specific head counts and embedding dimensions.Source: §7.3 · p. 45, Figure 13 · p. 45

8 Conclusion

  • The conclusion frames the work as a statistical analysis of CoT variants, including an error decomposition and exponential prompting-error decay, alongside theoretical and empirical comparisons with vanilla ICL.The paper also analyzes pretrained-LLM statistical error under PAC-Bayes and leaves broader prompting methods for future work.Source: §8 · p. 46

A A Generalized Multi-Step Latent Variable Model

The generalized model relaxes the i.i.d. assumption by representing task-specific reasoning through evolving latent variables. Under this model, perfectly pretrained LLMs perform Bayesian model averaging during CoT prompting when the prompt has positive density under the pretraining distribution.

A A Generalized Multi-Step Latent Variable Model

  • The generalized model removes the i.i.d. requirement and allows latent variables for each example to depend on the task and latent variables from earlier examples.This captures dependent demonstration structure while retaining multi-step reasoning.Source: A A Generalized Multi-Step Latent… · p. 54
  • Each reasoning step is generated through task-specific latent goals translated into natural-language steps, with the latent sequence determining the reasoning process.The model assumes the step-generation function does not itself involve the task parameter.Source: A A Generalized Multi-Step Latent… · p. 54

B Proofs of the Results in Section 4

B.1 Proof of Lemma 4.1 and Its Extension

  • For a CoT prompt with nonzero density under the pretraining distribution, a perfectly pretrained LLM performs Bayesian model averaging under the generalized model.The extension applies even though examples and the test query need not be i.i.d.Source: §B.1 · p. 59

B.2 Proof of Proposition 4.2

The proof connects the Bayesian model-averaging estimator to attention through a population estimator and convergence arguments. The following proof section separately establishes the CoT error decomposition into pretraining and prompting components.

B.2 Proof of Proposition 4.2

  • The proof relates attention and BMA through a population estimator, identifies that estimator as ridge regression on pooled reasoning steps, and shows attention converges to a conditional expectation as n grows.The argument handles dependence across steps by decomposing sums by step and applying concentration within each step.Source: §B.2 · pp. 60, 61, 64
  • The attention approximation proof assumes finite-dimensional features, while the authors state the argument extends to infinite-dimensional features using effective dimension.Source: §B.2 · p. 65

C Proofs and Additional Results of Section 5.1

C.1 Proof of Lemma 5.2

  • The CoT error bound separates pretraining error from prompting-related terms involving KL divergence between the true task distribution and the distribution induced by the prompt and pretrained model.The pretraining term compares the target distribution with the pretrained model’s distribution.Source: §C.1 · p. 67

C.2 Proofs of Theorems 5.5 and 5.7 and Extension

The proofs extend the CoT error bounds from finite task spaces to continuous ones, using covering arguments. Prompting error decays exponentially in the finite case, while continuous-space rates depend on covering complexity and equivalence-class assumptions.

C.2 Proofs of Theorems 5.5 and 5.7 and Extension

  • For continuous Θ, covering-number bounds incur discretization error, and the statistical rate is slower as task-space complexity increases.The covering precision α should be chosen so α·n converges to zero as n increases.Source: §C.2 · pp. 68, 71
  • The continuous-space extension discretizes Θ∁ with an α-cover under the log-likelihood metric and accounts for the resulting granularity error.The proof partitions the covered region into sets contained in neighborhoods of radius α.Source: §C.2 · pp. 67, 71
  • Assumption 5.6, which makes distributions within each equivalence class close, improves parameter-space dependence from Θ∁ to f Θ∁, despite slower exponential decay.For continuous f Θ∁, this result does not require Assumption 6.2.Source: §C.2 · p. 73
  • For finite Θ, prompting error decays exponentially under task separation and depends on the number of representatives of the incorrect-task classes.Theorem 5.7 gives dependence through |f Θ∁|; the earlier bound states the task-separation condition.Source: §C.2 · pp. 71, 75

D.1 Proof of Corollary 5.9

The appendices prove results for self-consistency, Tree-of-Thought, and Selection-Inference by separating how prompt examples shape model distributions from how candidate paths are selected. The analyses give distinct roles to demonstration count, candidate count, and task decomposition.

D.1 Proof of Corollary 5.9

  • Self-consistency uses n prompt examples to align the perfectly pretrained model’s population mode with the target, while K sampled paths approximate that mode.The proof combines these two steps to obtain the final statistical error result.Source: §D.1 · p. 77

D.2 Proof of Proposition 5.11

  • For ToT with breadth B = 1, the LLM-induced next-step probability approaches the true probability exponentially with n, while larger K helps sample and select the optimal trajectory.The proof combines these roles to bound statistical error with a perfectly pretrained LLM and finite discrete Θ.Source: §D.2 · pp. 79–81

D.3 Proof of Corollary 5.13

  • Selection-Inference splits each task into selection and inference components, and its finite discrete-Θ rate uses λSI = λS + λI + λq in place of λ.The proof adapts the vanilla-CoT analysis to the two-stage decomposition.Source: §D.3 · pp. 81, 83

E.1 Proof of a Generalized Version of Proposition 5.14

This section formalizes an average-case ordering of truncated CoT methods and analyzes pretraining error using a PAC-Bayes decomposition, error bounds, and uniform convergence. It also develops a transformer construction that represents feed-forward networks in transformer blocks and bounds approximation and depth-dependent intermediate-output growth.

E.1 Proof of a Generalized Version of Proposition 5.14

  • Under zero pretraining error and no query shift, Assumption E.1 makes truncated methods comparable via matching truncated pretraining data, with full CoT and vanilla ICL as endpoint cases.Full CoT corresponds to J = [H −1], while vanilla ICL corresponds to J = ∅.Source: §E.1 · p. 84

E.2 Proof of Corollary E.2

  • On average over tasks, retaining a superset of intermediate steps is no worse than using fewer steps for any n; thus CoT is no worse than vanilla ICL.The comparison is an average-case inequality with expectation over the task distribution.Source: §E.1 · p. 84, §E.2 · p. 85

F.1 Proof of Proposition 6.3

  • The PAC-Bayes proof decomposes pretraining error into fluctuation, approximation, and KL-divergence terms; it bounds fluctuation at O(1) and analyzes the other terms under Assumptions 6.1 and 6.2.The fluctuation terms arise from randomness in the model distribution; the approximation term measures discrepancy from the best approximator, and the KL term is between P and Q.Source: §F.1 · pp. 86, 90, 92
  • The pretraining-error rate combines bounds for three constituent errors with a uniform-convergence bound relating total-variation distances to their expectations.The derivation drops terms dominated by the remaining terms.Source: §F.1 · pp. 93–94

F.2 Formal Statement of Proposition 6.4

  • Under Assumptions 6.1, 6.2, and F.5, a transformer with O(D) blocks achieves approximation error that decays exponentially as D increases.The approximation concerns the target distribution and is established first for one-dimensional reasoning steps; the method can be generalized to higher dimensions.Source: §F.2 · pp. 94–96
  • The proposed construction extracts the desired reasoning-step index, applies step-specific distribution approximators, selects the matching approximation, and uses a softmax output layer.The architecture uses H + 1 approximation and selection modules.Source: §F.2 · p. 96

F.3 Proof of Proposition F.6

  • The proof generalizes the transformer structure with additional feed-forward bias terms and row-wise ℓ2 normalization, and treats a block as a four-layer neural network.The generalized structure can be accommodated in the generalization-error bound.Source: §F.3 · pp. 97–98
  • Scaling an attention or feed-forward layer's output to keep its row-wise norm at most one makes normalization inactive, while scaling the next layer's weights preserves the desired output.For attention, the construction scales the MHA parameters and compensates in the subsequent weight matrix; the feed-forward construction uses the same principle.Source: §F.3 · p. 98
  • An L-layer row-wise MLP with bounded intermediate outputs can be represented by an L-block transformer whose ℓ-th output is Xℓ/Bℓ.The construction assumes ∥(Xℓ)⊤∥2,∞ ≤ Bℓ for each layer, with Bℓ ≥ 1.Source: §F.3 · p. 99
  • For a fully connected network with L layers, maximum width d, maximum weight α, and maximum bias β, intermediate-output magnitude is bounded by B0 · (d · α)^ℓ + β · ((d · α)^ℓ−1)/(d · α −1).The proof states that intermediate-output magnitude can grow at most exponentially with d · α.Source: §F.3 · p. 99

F.3.1 Rigorous Proof of Proposition F.6

The proof constructs transformers that approximate target distributions for individual reasoning steps using indexed, per-step approximation and selection modules. It characterizes the constructions’ depth and approximation error, including a KL-divergence bound under the stated assumptions.

Input embedding

  • The input embedding stores each reasoning step’s content, its step index, and an indicator marking the final step.The positional coordinates identify the target index to extract from the last reasoning step.Source: §F.3.1 · p. 100

Proof construction

  • The construction combines index extraction, candidate approximation, index-based selection, a softmax output layer, and verification that the network belongs to PLLM.The five-step proof first builds the extraction, approximation, and selection modules, then combines them with softmax and checks the parameter constraints.Source: §F.3.1 · p. 100

Step 1: Extract and copy step index

  • Step 1 extracts the target index from the last reasoning step and copies it to all previous steps, with index error below 1/4.Four submodules implement the extraction; their product approximation is configured with ε = 1/4 and ε′ = 1/16.Source: §F.3.1 · pp. 100, 102, 103

Steps 2–3: Approximation and selection

  • Steps 2 and 3 chain candidate modules that approximate each indexed target function and pass along only the approximation whose module index matches the extracted step index.A matching module contributes its approximation to memory; nonmatching modules discard their output.Source: §F.3.1 · pp. 103–104

Step 2: Construct approximation module Geh

  • Under Assumptions 6.1, 6.2, and F.5, a transformer module Gh approximates each step’s target distribution, with approximation accuracy increasing exponentially in Dw.The module uses (Dw + Dψ + 2) transformer blocks; setting Dψ = O(Dw^2) makes the second term in the error bound negligible compared with the first.Source: §F.3.1 · pp. 104–105

Step 3: Construct selection module Feh

  • Each selection module checks whether its index matches the target step and writes the corresponding embedding into memory only when they match.It keeps the first three input components unchanged and uses the last component as memory.Source: §F.3.1 · p. 105

F.3.1 Rigorous Proof of Proposition F.6

  • Balancing the depths Dψ, Dw, and Dp makes the first term dominate the approximation-error bound for sufficiently large Dg.Dg characterizes the total number of transformer blocks in Geh and Feh together, and the actual total is O(Dg).Source: §F.3.1 · p. 110
  • The proof converts the ℓ1 approximation bound into a KL-divergence bound using a likelihood-ratio bound under the condition ε < c0/2.Here c0 comes from Assumption 6.2.Source: §F.3.1 · p. 110
  • Under Assumptions 6.1, 6.2, and F.5, a transformer exists with at most O(D) blocks and parameter ρ* ∈ PLLM, with the stated guarantee for any t ∈ [T] and 0 ≤ h ≤ H.Source: §F.3.1 · p. 111

F.4 Proof of Corollary 6.6

This section develops proof ingredients for Corollary 6.6, including separate pretraining and prompting error bounds under distribution shift and transformer implementations that approximate neural-network operations and target coordinates. It also relates prompt quality to posterior concentration and describes techniques for implementing attention while bypassing normalization.

F.4 Proof of Corollary 6.6

  • The expected pretraining error under shifted prompts is bounded by 2(3 + b∗)κπ(θ∗)−1T(H + 1)∆pre(N, T, δ) with probability at least 1−δ.The proof obtains this bound by decomposing pretraining error across reasoning steps and shifting the expectation from PCoT toward P.Source: §F.4 · pp. 111–113
  • The prompting-error analysis bounds likelihood ratios for competing tasks by an exponentially decreasing function of n, yielding an exponentially decreasing expected prompting error.The likelihood-ratio bound holds with probability at least 1−ξ; the resulting convergence rate is dominated by C(n)^1/2.Source: §F.4 · pp. 114–115
  • Under Assumptions 5.4 and 6.5, the combined error bound has a prompting term that decays as exp(−nλ/2) and a pretraining term proportional to ∆pre(N, T, δ), with probability at least 1−δ.The prompting and pretraining terms correspond to errprompt and errpre, respectively.Source: §F.4 · pp. 115–116

G.1 Additional Details about Pretraining

  • The pretraining description specifies a D-block transformer with positional and content embeddings, attention and feed-forward layers, and a softmax output trained by maximum likelihood on N trajectories of T examples.The blocks include residual connections and normalization; the pretraining dataset is generated under the generalized model.Source: §G.1 · pp. 117, 119

G.2.1 Proof of Proposition C.2

  • The proof of Proposition C.2 interprets its final KL term as integrated posterior contraction: better CoT prompts yield greater posterior concentration.The argument uses a posterior distribution over tasks supported on the equivalence class of the true task.Source: §G.2.1 · p. 120

G.3.1 Proof of Lemma F.2

  • The softmax layer and Assumption 6.2 yield the log-density upper bound b*, after which Hoeffding’s inequality and a union bound control all (t, h) pairs.The concentration argument applies across t ∈ [T] and 0 ≤ h ≤ H.Source: §G.3.1 · p. 122

G.3.2 Proof of Lemma F.4

  • The proof combines concentration, Pinsker’s inequality, and a union bound over all (t, h) pairs to derive a bound involving D̄, B̄, N, T, and H.The supplied passage gives the bound’s expression only partially.Source: §G.3.2 · p. 123

G.4.1 Proof of Proposition F.7

  • An L-block transformer reproduces an L-layer MLP up to intermediate scaling factors, which can be undone at the final output.The construction disables attention, uses feed-forward layers, and scales activations to satisfy normalization constraints.Source: §G.4.1 · pp. 123, 125

G.4.2 Proof of Lemma F.8

  • The feed-forward construction realizes NNJ,1, with its input and output magnitudes bounded by B2 + H2 + 1.The construction uses the identity x = ReLU(x) − ReLU(−x) and absorbs scaling factors into the weights.Source: §G.4.2 · p. 126

G.4.3 Proof of Lemma F.9

  • A product operation can be approximated with error at most ϵ′ by a network of depth at most Cp(log(H) + log(1/ϵ′)) and at most 5 hidden neurons.The construction is then implemented with transformer blocks and combined with a feed-forward layer that preserves the other input columns.Source: §G.4.3 · p. 127

G.4.4 Proof of Lemma F.10

  • A feed-forward layer realizes the stated linear operation exactly; the construction gives c′ = 1 when c = 0 and c′ = 1/2 when c = 1.The feed-forward layer can be represented by a single transformer block.Source: §G.4.4 · p. 128

G.4.5 Proof of Lemma F.11

  • An attention layer is constructed to approximate the selected state value while preserving its first coordinate, and the module is implementable with one transformer block.The attention parameter α controls the precision of the approximation.Source: §G.4.5 · p. 128
  • Choosing α so that (L′ −1) · max{e−α/2, e−α/4} < ϵ −2ϵ′ ensures |pt′h′ −h| < ϵ for all (t′, h′).Since L′ ≤ T · (H + 1), the scale can be chosen to satisfy this condition.Source: §G.4.5 · p. 130
  • The constructed attention layer can be implemented in one transformer block using a residual link and a feed-forward module that appends zeros.A scaling trick bypasses the normalization layer, changing the weight-matrix magnitudes by only a constant factor.Source: §G.4.5 · p. 130

G.4.6 Proof of Proposition F.12

This section presents supporting proof and construction material, including neural-network and transformer implementations with error bounds. It also includes auxiliary function implementations and example prompts that vary reasoning and information content.

G.4.6 Proof of Proposition F.12

  • A single-head attention layer with WQ = WK = 0 and WV = 1 realizes the averaging step because its attention scores are all 1/L′.Source: §G.4.6 · p. 132
  • Under Assumption F.5, MLPs approximate the component functions with at most 16 neurons per layer and depths Dψ and Dw, yielding controlled softmax approximation error.The proof uses smooth-function approximation and softmax Lipschitz continuity; the displayed error bound depends on the component approximation errors.Source: §G.4.6 · pp. 132–133
  • The same upper error bound applies uniformly for every reasoning-step index eh ∈ {0, . . . , H}.The argument relies on softmax Lipschitz continuity and the approximation errors, so substituting any eh preserves the bound.Source: §G.4.6 · pp. 133–134
  • The embedding is implemented within Gh using Dψ + Dw + 2 transformer blocks, preserving required input columns through augmented layers and a residual ReLU module.The resulting hidden-layer width is bounded by dF ≤ 16|L| + 4 + 2|L|.Source: §G.4.6 · pp. 134–136

G.4.7 Proof of Lemma F.13

  • A trapezoid-shaped function is implemented by one feed-forward layer of width at most 10 with weights bounded by H + 1.The construction writes the function as the sum of two triangular piecewise-linear functions, each expressible using ReLU functions.Source: §G.4.7 · pp. 137–138

G.5.1 Proof of Lemma F.14

  • The proof of Lemma F.14 uses the KL-divergence chain rule and data processing for test-sequence distributions conditioned on a fixed CoT prompt.The supplied passage identifies the combination of these steps as yielding the proof’s result.Source: §G.5.1 · pp. 138–139

G.5.2 Proof of Lemma G.1

  • A product network approximates each x_i y with error below ϵ at depth O(log M + log(1/ϵ)), hidden dimension at most 5r, and bounded intermediate weights.The construction targets f(x_1:r, y) ≈ (x_1y, …, x_ry); its final weight matrix has norm at most M^2.Source: §G.5.2 · pp. 139–140

G.5.3 Proof of Lemma G.2

  • For a selected column set J, the Lemma G.2 construction zeros unselected columns, then removes zero dimensions to produce the desired output using weights with 2|J| nonzero entries.The retained weight entries take values in {−1, 0, 1}.Source: §G.5.3 · p. 141

I Supplementary Information about Prompts

  • Appendix I provides supplementary examples for the area-code and CityEquation experiments, including two-shot prompts for five prompting methods.The methods are vanilla ICL, informative CoT, partially informative CoT-(a), partially informative CoT-(c), and uninformative CoT.Source: I Supplementary Information about… · p. 144, Example prompts · p. 145

Example prompts

  • The basic examples request answers to city-longitude addition problems, while the Paris + Beijing prompt asks for concise steps and an integer answer in the final sentence.The Mumbai + Sydney and New York + Seoul examples provide answer-only demonstrations; the Paris + Beijing prompt specifies the response format.Source: Example prompts · p. 145
  • Informative CoT examples explain the longitude mapping, negative western-hemisphere values, and rounding coordinates to the nearest integer before giving the answer.The shown solutions map Mumbai to 73 and Sydney to 151, and New York to -74 and Seoul to 127.Source: Example prompts · p. 145
  • Partially informative CoT-(a) gives one city’s longitude before the answer, without explaining the full calculation.The examples provide Mumbai’s longitude or New York’s longitude, respectively.Source: Example prompts · p. 146
  • Partially informative CoT-(b) supplies city demographic details without longitude values, while CoT-(c) adds one city’s longitude to those details.The Mumbai + Sydney and New York + Seoul examples provide population, ethnicity, and median-age information; the (c) examples additionally give Mumbai’s or New York’s longitude.Source: Example prompts · pp. 146–147
  • Partially informative CoT-(d) combines demographic details with both cities’ longitudes before giving the answer.Its Mumbai + Sydney and New York + Seoul examples provide both operands’ longitude values.Source: Example prompts · p. 147

I.1 Details of the Area Code Experiment in in Section 4.1

The area-code experiment compares vanilla ICL and CoT prompts for ChatGPT. Vanilla ICL gives an incorrect Japan answer, while the CoT output follows the demonstrations’ reasoning pattern; the next subsection provides details for a city arithmetic experiment.

I.1 Details of the Area Code Experiment in in Section 4.1

  • Vanilla ICL answers 100 for Japan, although the correct answer is 162.The experiment compares ChatGPT outputs under ICL and CoT prompts.Source: §I.1 · p. 144
  • With CoT, ChatGPT states Japan’s area code is 81 and gives the answer 162, following the demonstration pattern.The CoT examples show the US and France area codes alongside their answers.Source: §I.1 · p. 144

I.2 Details of the CityEquation Experiment

  • The city arithmetic experiment details correspond to the experiment discussed in Section 5.3.Source: §I.2 · p. 145
Loading 2408.14511v2…