Training Nonlinear Transformers for Chain-of-Thought Inference: A Theoretical Generalization Analysis

Hongkang Li, Meng Wang, Songtao Lu, Xiaodong Cui, Pin-Yu Chen

While Large Language Models (LLMs) have demonstrated an empirical mastery of "thinking out loud" through Chain-of-Thought (CoT) prompting, the theoretical understanding of how gradient-based training leads to these capabilities has remained limited. Most existing research focuses on the expressive power of Transformers—proving they can represent reasoning chains—rather than the dynamics of how they learn to do so.

A recent paper accepted at ICLR 2025, "Training Nonlinear Transformers for Chain-of-Thought Inference: A Theoretical Generalization Analysis," bridges this gap. The authors provide the first rigorous theoretical proof that standard gradient-based training can successfully teach a nonlinear Transformer to perform CoT reasoning, quantifying the sample complexity and iterations required for success.

Theoretical Framework: Learning to Filter Context

The researchers analyzed a one-layer, single-head attention-only Transformer utilizing a nonlinear softmax attention mechanism. To model the reasoning process, they introduced a framework where context examples in a prompt can be "noisy," containing errors or irrelevant steps.

One of the paper's primary contributions is the discovery of a two-stage training theory. During the first phase, the model learns to attend to the correct reasoning step. In the second phase, it refines its focus to the specific input patterns relevant to the query. This results in a "filtering mechanism" where the model identifies context examples that share the same reasoning trajectory as the current query.

Figure 2: The filtering mechanism in action, where the model learns to assign high attention weights to context examples that match both the reasoning step and the input pattern (TSR) of the query.

As shown in the figure above, a well-trained model eventually concentrates nearly 100% of its attention weight on context columns that align with the current reasoning step and query pattern, effectively ignoring irrelevant or noisy data.

Why CoT Outperforms In-Context Learning (ICL)

A critical question in LLM research is why CoT succeeds in complex reasoning tasks where standard In-Context Learning (ICL)—which provides only the final answer—fails. The authors argue that CoT is fundamentally more robust to noise and distribution shifts.

In ICL, the model attempts to map an input directly to an output. If the prompt contains many examples where the same input leads to different outputs (noise), the signal is diluted. In contrast, CoT breaks the task into intermediate steps. By focusing on individual transitions, the model ensures that at each step, the "correct" next token remains statistically dominant.

Figure 1: Visualization of step-wise transition matrices where thick arrows represent dominant reasoning paths and dashed arrows represent noise.

This step-wise approach allows the model to maintain high accuracy even when some context examples are incorrect. The authors validated this theory with GPT-4 experiments on arithmetic tasks, finding that CoT remained 100% accurate even with erroneous examples that caused ICL performance to drop significantly.

Key Results and Generalization

The study provides explicit mathematical bounds for training convergence and generalization:

  • Convergence Bounds: The number of iterations required scales with $O(\alpha^{-2}K^3)$, where $K$ is the number of reasoning steps and $\alpha$ is the fraction of relevant examples.
  • Guaranteed Generalization: The authors proved that after a specific number of iterations, the model achieves near-zero generalization error on unseen tasks, even those with a distribution shift from the training data.
  • Sample Complexity: The required number of training samples is inversely proportional to the fraction of relevant examples in the training data ($\alpha^{-1}$).

Limitations and Future Directions

While this work provides a foundational theoretical framework, it focuses on a one-layer Transformer and simplified functional composition tasks. Future research is needed to extend these proofs to multi-layer, multi-head architectures and to account for the nuances of natural language commonsense reasoning. Additionally, the authors suggest investigating how LLMs might be trained to generate better self-correcting prompts.

Paper Citation: Li, H., Lu, S., Chen, P.-Y., Cui, X., & Wang, M. (2025). Training Nonlinear Transformers for Chain-of-Thought Inference: A Theoretical Generalization Analysis. Published as a conference paper at ICLR 2025.

Summary updated

BibTeX
@inproceedings{li2025training,
  author = {Hongkang Li and Meng Wang and Songtao Lu and Xiaodong Cui and Pin-Yu Chen},
  title = {{Training Nonlinear Transformers for Chain-of-Thought Inference: A Theoretical Generalization Analysis}},
  booktitle = {International Conference on Learning Representations},
  year = {2025},
  url = {https://openreview.net/forum?id=n7n8McETXw},
}
Figure