# On the Representational Capacity of Neural Language Models with Chain-of-Thought Reasoning

arXiv: https://arxiv.org/abs/2406.14197 · HTML: https://mlsanity.com/paper/2406.14197/

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- Placed in Prompting and chain-of-thought reasoning, one of 17 directions in LLM reasoning.
- Builds on 13 of its 54 references that are in the map.
- First posted on arXiv 20 Jun 2024.

## Placed in

- LLM reasoning / [Prompting and chain-of-thought reasoning](https://mlsanity.com/lr/prompting-and-chain-of-thought-reasoning/)

## Builds on (most cited first, 13 of 13)

- [Large Language Models are Zero-Shot Reasoners](https://mlsanity.com/paper/2205.11916/) (2022)
- [Emergent Abilities of Large Language Models](https://mlsanity.com/paper/2206.07682/) (2022)
- [Challenging BIG-Bench Tasks and Whether Chain-of-Thought Can Solve Them](https://mlsanity.com/paper/2210.09261/) (2022)
- [Show Your Work: Scratchpads for Intermediate Computation with Language Models](https://mlsanity.com/paper/2112.00114/) (2021)
- [Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspective](https://mlsanity.com/paper/2305.15408/) (2023)
- [Chain-of-Thought Reasoning Without Prompting](https://mlsanity.com/paper/2402.10200/) (2024)
- [The Expressive Power of Transformers with Chain of Thought](https://mlsanity.com/paper/2310.07923/) (2023)
- [Sub-Task Decomposition Enables Learning in Sequence to Sequence Tasks](https://mlsanity.com/paper/2204.02892/) (2022)
- [On the Computational Power of RNNs](https://mlsanity.com/paper/1906.06349/) (2019)
- [Transformers Can Represent n-gram Language Models](https://mlsanity.com/paper/2404.14994/) (2024)
- [Extracting Finite Automata from RNNs Using State Merging](https://mlsanity.com/paper/2201.12451/) (2022)
- [Lower Bounds on the Expressivity of Recurrent Neural Language Models](https://mlsanity.com/paper/2405.19222/) (2024)
- [On Affine Homotopy between Language Encoders](https://mlsanity.com/paper/2406.02329/) (2024)

## Built on by (most cited first, 26 of 26)

- [LLM Post-Training: A Deep Dive into Reasoning Large Language Models](https://mlsanity.com/paper/2502.21321/) (2025)
- [Towards System 2 Reasoning in LLMs: Learning How to Think With Meta Chain-of-Thought](https://mlsanity.com/paper/2501.04682/) (2025)
- [Self-Training Elicits Concise Reasoning in Large Language Models](https://mlsanity.com/paper/2502.20122/) (2025)
- [PENCIL: Long Thoughts with Short Memory](https://mlsanity.com/paper/2503.14337/) (2025)
- [From Sparse Dependence to Sparse Attention: Unveiling How Chain-of-Thought Enhances Transformer Sample Efficiency](https://mlsanity.com/paper/2410.05459/) (2024)
- [Generative AI Act II: Test Time Scaling Drives Cognition Engineering](https://mlsanity.com/paper/2504.13828/) (2025)
- [A Formal Comparison Between Chain of Thought and Latent Thought](https://mlsanity.com/paper/2509.25239/) (2025)
- [Enhancing Latent Computation in Transformers with Latent Tokens](https://mlsanity.com/paper/2505.12629/) (2025)
- [Characterizing the Expressivity of Fixed-Precision Transformer Language Models](https://mlsanity.com/paper/2505.23623/) (2025)
- [Let Me Think! A Long Chain-of-Thought Can Be Worth Exponentially Many Short Ones](https://mlsanity.com/paper/2505.21825/) (2025)
- [Can Transformers Learn n-gram Language Models?](https://mlsanity.com/paper/2410.03001/) (2024)
- [To CoT or To Loop? A Formal Comparison Between Chain-of-Thought and Looped Transformers](https://mlsanity.com/paper/2505.19245/) (2025)
- [Unique Hard Attention: A Tale of Two Sides](https://mlsanity.com/paper/2503.14615/) (2025)
- [Are Latent Reasoning Models Easily Interpretable?](https://mlsanity.com/paper/2604.04902/) (2026)
- [Chain-of-Thought in Large Language Models: Decoding, Projection, and Activation](https://mlsanity.com/paper/2412.03944/) (2024)
- [Bridging Kolmogorov Complexity and Deep Learning: Asymptotically Optimal Description Length Objectives for Transformers](https://mlsanity.com/paper/2509.22445/) (2025)
- [Beyond Memorization: Extending Reasoning Depth with Recurrence, Memory and Test-Time Compute Scaling](https://mlsanity.com/paper/2508.16745/) (2025)
- [Benchmarking graph construction by large language models for coherence-driven inference](https://mlsanity.com/paper/2502.13953/) (2025)
- [Probability Distributions Computed by Autoregressive Transformers](https://mlsanity.com/paper/2510.27118/) (2025)
- [Representing Rule-based Chatbots with Transformers](https://mlsanity.com/paper/2407.10949/) (2024)
- [An L^* Algorithm for Deterministic Weighted Regular Languages](https://mlsanity.com/paper/2411.06228/) (2024)
- [From n-gram to Attention: How Model Architectures Learn and Propagate Bias in Language Modeling](https://mlsanity.com/paper/2505.12381/) (2025)
- [Analyzing the Power of Chain of Thought through Memorization Capabilities](https://mlsanity.com/paper/2511.01190/) (2025)
- [Medal Matters: Probing LLMs' Failure Cases Through Olympic Rankings](https://mlsanity.com/paper/2409.06518/) (2024)
- [Position: The Turing-Completeness of Autoregressive Transformers Relies Heavily on Context Management](https://mlsanity.com/paper/2605.19514/) (2026)
- [Rethinking the Role of Positional Encoding: Sliding-Window Transformers without PE Remain Turing Complete](https://mlsanity.com/paper/2606.01532/) (2026)

## Abstract (arXiv)

The performance of modern language models (LMs) has been improved by chain-of-thought (CoT) reasoning, i.e., the process of generating intermediate results that guide the model towards a final answer. A possible explanation for this improvement is that CoT reasoning extends an LM's computational power, as RNNs and transformers with additional scratch space are known to be Turing complete. Comparing LMs to Turing machines, however, introduces a category error - Turing machines decide language membership, whereas LMs define distributions over strings. To bridge this gap, we formalize CoT reasoning in a probabilistic setting. We present several results on the representational capacity of recurrent and transformer LMs with CoT reasoning, showing that they can represent the same family of distributions over strings as probabilistic Turing machines.