mlsanityData to 7 Oct 2026

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

arXiv 2406.14197 ↗First posted 20 Jun 2024cs.CL cs.FLcited by 26

On the map: LLM reasoning → Prompting and chain-of-thought reasoning

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.

Key facts. Cited by 26 papers in the map (data through 7 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.

Builds on

13 of 54 references.

Closest ancestors · 5

Same direction, newest first

  1. 2024Chain-of-Thought Reasoning Without Prompting15 Feb
  2. 2023The Expressive Power of Transformers with Chain of Thought11 Oct
  3. 2023Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspective24 May
  4. 2022Challenging BIG-Bench Tasks and Whether Chain-of-Thought Can Solve Them17 Oct
  5. 2022Large Language Models are Zero-Shot Reasoners24 May

Other references · 8

  1. 2022Emergent Abilities of Large Language Modelscited by 2,483
  2. 2021Show Your Work: Scratchpads for Intermediate Computation with Language Modelscited by 871
  3. 2022Sub-Task Decomposition Enables Learning in Sequence to Sequence Taskscited by 41
  4. 2019On the Computational Power of RNNscited by 35
  5. 2024Transformers Can Represent n-gram Language Modelscited by 31
  6. 2022Extracting Finite Automata from RNNs Using State Mergingcited by 17
  7. 2024Lower Bounds on the Expressivity of Recurrent Neural Language Modelscited by 4
  8. 2024On Affine Homotopy between Language Encoderscited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 6; 2025: 17; 2026: 3.

26 papers.

Sort:

By area:

  1. 2025LLM Post-Training: A Deep Dive into Reasoning Large Language Modelscited by 129
  2. 2025Towards System 2 Reasoning in LLMs: Learning How to Think With Meta Chain-of-Thoughtcited by 108
  3. 2025Self-Training Elicits Concise Reasoning in Large Language Modelscited by 97
  4. 2025PENCIL: Long Thoughts with Short Memorycited by 31
  5. 2024From Sparse Dependence to Sparse Attention: Unveiling How Chain-of-Thought Enhances Transformer Sample Efficiencycited by 28
  6. 2025Generative AI Act II: Test Time Scaling Drives Cognition Engineeringcited by 14
  7. 2025Characterizing the Expressivity of Fixed-Precision Transformer Language Modelscited by 14
  8. 2025A Formal Comparison Between Chain of Thought and Latent Thoughtcited by 14
  9. 2025Enhancing Latent Computation in Transformers with Latent Tokenscited by 13
  10. 2025Let Me Think! A Long Chain-of-Thought Can Be Worth Exponentially Many Short Onescited by 12
  11. 2024Can Transformers Learn n-gram Language Models?cited by 11
  12. 2025Unique Hard Attention: A Tale of Two Sidescited by 10
14 more
  1. 2025To CoT or To Loop? A Formal Comparison Between Chain-of-Thought and Looped Transformerscited by 10
  2. 2024Chain-of-Thought in Large Language Models: Decoding, Projection, and Activationcited by 6
  3. 2025Bridging Kolmogorov Complexity and Deep Learning: Asymptotically Optimal Description Length Objectives for Transformerscited by 6
  4. 2026Are Latent Reasoning Models Easily Interpretable?cited by 6
  5. 2025Beyond Memorization: Extending Reasoning Depth with Recurrence, Memory and Test-Time Compute Scalingcited by 4
  6. 2025Benchmarking graph construction by large language models for coherence-driven inferencecited by 2
  7. 2025Probability Distributions Computed by Autoregressive Transformerscited by 2
  8. 2024Representing Rule-based Chatbots with Transformerscited by 1
  9. 2024An L^* Algorithm for Deterministic Weighted Regular Languagescited by 1
  10. 2025From n-gram to Attention: How Model Architectures Learn and Propagate Bias in Language Modelingcited by 1
  11. 2025Analyzing the Power of Chain of Thought through Memorization Capabilitiescited by 1
  12. 2024Medal Matters: Probing LLMs' Failure Cases Through Olympic Rankingscited by 0
  13. 2026Position: The Turing-Completeness of Autoregressive Transformers Relies Heavily on Context Managementcited by 0
  14. 2026Rethinking the Role of Positional Encoding: Sliding-Window Transformers without PE Remain Turing Completecited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025Latent Chain-of-Thought? Decoding the Depth-Recurrent Transformer
  2. 2024Autoregressive + Chain of Thought = Recurrent: Recurrence's Role in Language Models' Computability and a Revisit of Recurrent Transformer
  3. 2024Understanding Hidden Computations in Chain-of-Thought Reasoning
  4. 2025Unlocking General Long Chain-of-Thought Reasoning Capabilities of Large Language Models via Representation Engineering
  5. 2025Reasoning Beyond Language: A Comprehensive Survey on Latent Chain-of-Thought Reasoning
  6. 2026Barriers to Universal Reasoning With Transformers (And How to Overcome Them)
  7. 2024Chain of Thought Empowers Transformers to Solve Inherently Serial Problems
  8. 2024Understanding Chain-of-Thought in LLMs through Information Theory