HackerPapers

arXiv:2310.07923cs.LG

The Expressive Power of Transformers with Chain of Thought

William Merrill, Ashish Sabharwal

Abstract

Recent theoretical work has identified surprisingly simple reasoning problems, such as checking if two nodes in a graph are connected or simulating finite-state machines, that are provably unsolvable by standard transformers that answer immediately after reading their input. However, in practice, transformers' reasoning can be improved by allowing them to use a "chain of thought" or "scratchpad", i.e., generate and condition on a sequence of intermediate tokens before answering. Motivated by this, we ask: Does such intermediate generation fundamentally extend the computational power of a decoder-only transformer? We show that the answer is yes, but the amount of increase depends crucially on the amount of intermediate generation. For instance, we find that transformer decoders with a logarithmic number of decoding steps (w.r.t. the input length) push the limits of standard transformers only slightly, while a linear number of decoding steps, assuming projected pre-norm (a slight generalization of standard pre-norm), adds a clear new ability (under standard complexity conjectures): recognizing all regular languages. Our results also imply that linear steps keep transformer decoders within context-sensitive languages, and polynomial steps with generalized pre-norm make them recognize exactly the class of polynomial-time solvable problems -- the first exact characterization of a type of transformers in terms of standard complexity classes. Together, this provides a nuanced framework for understanding how the length of a transformer's chain of thought or scratchpad impacts its reasoning power.

arXiv comments
9-page preprint. ICLR camera ready posted April 11
Journal reference
DOI
Subjects
cs.LGMachine Learning cs.CCComputational Complexity cs.CLComputation and Language cs.LOLogic in Computer Science

On Hacker News

Linked by 7 identifiable commenters in 18 comments across 16 threads, from Jun 2024 to Sep 2026. Found in 1 HN submission from Mar 2024 to Mar 2024. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments16 threads

  1. GPT-6 Astra, looped transformers, and hidden reasoning 1 comment

    • For the research focused, there are some references in my blogpost here on what kinds of computational problems minimally require how much CoT to solve: https://blog.wtf.sg/posts/2023-02-03-the-new-xor-problem/ Notably Will Merrill's work: https://arxiv.org/abs/2310.07923 As for…

      shawntanView on HNParent context

  2. Learning more about Claude's mathematical capabilities 1 comment

    • >why wouldn't that same model be able to find ways to improve it's own algorithms beyond that of the capabilities of human mathematicians / ML researchers Because algorithms have lower bounds, and the computational characteristics of LLMs are well-characterized by papers like…

      logicchainsView on HNParent context

  3. Why I don't think AGI is imminent 1 comment

    • Thanks for reading, and I really appreciate your comments! > who feed their produced tokens back as inputs, and whose tuning effectively rewards it for doing this skillfully Ah, this is a great point, and not something that I considered. I agree that the token feedback does…

      anonymidView on HNParent context

  4. Markov chains are the original language models 1 comment

    • The term for research on whether LLMs can learn and execute this or that algorithm of program synthesis? I guess there's none. If we do know the algorithm, it's better to teach LLM to write a program that outputs a program. If we don't know the algorithm, we can't reason whether…

      red75primeView on HNParent context

  5. The wall confronting large language models 1 comment

    • LLMs are not formally equivalent to Markov chains, they're more powerful; transformers with sufficient chain of thought can solve any problem in P: https://arxiv.org/abs/2310.07923.

      logicchainsView on HNParent context

  6. The bitter lesson is coming for tokenization 1 comment

    • We can be sure via analysis based on computational theory, e.g. https://arxiv.org/abs/2503.03961 and https://arxiv.org/abs/2310.07923 . This lets us know what classes of problems a model is able to solve, and sufficiently deep transformers with chain of thought have been shown…

      logicchainsView on HNParent context

  7. O1 isn't a chat model (and that's the point) 1 comment

    • Yes it is, because the post discussed this approach precisely because unrolling the actual chain of thought in interactive chat does not work. And it's doubly relevant because chain of thought let's transformers break out of TCO complexity and be UTM. This matters because TC0 is…

      inciampatiView on HNParent context

  8. 30% drop in O1-preview accuracy when Putnam problems are slightly variated 1 comment

    • When Can Transformers Count to n? https://arxiv.org/html/2407.15160v2 The Expressive Power of Transformers with Chain of Thought https://arxiv.org/html/2310.07923v5 Transformer needs to retrieve letters per each token while forced to keep internal representation still aligned in…

      IsinlorView on HNParent context

  9. Computing Inside an AI 1 comment

    • An LLM with chain of thought and unbounded compute/context can run any program in PTIME: https://arxiv.org/abs/2310.07923 , which is a huge class of programs.

      logicchainsView on HNParent context

  10. Byte Latent Transformer: Patches Scale Better Than Tokens 1 comment

    • > that we are not guaranteed to be able to replicate all traits of human intelligence by brute forcing. We know from complexity theory that transformers with chain of thought are guaranteed to be able to reproduce a significant fraction of human reasoning, anything in the…

      logicchainsView on HNParent context

  11. Something weird is happening with LLMs and chess 2 comments

    • I am aware of errors in computations that can be fixed by better tokenization (e.g. long addition works better tokenizing right-left rather than L-R). But I am talking about counting, and talking about counting words, not characters. I don’t think tokenization explains why LLMs…

      aithrowawaycommView on HNParent context

    • I think the more obvious explanation has to do with computational complexity: counting is an O(n) problem, but transformer LLMs can’t solve O(n) problems unless you use CoT prompting: https://arxiv.org/abs/2310.07923

      aithrowawaycommView on HNParent context

  12. Chain of Thought empowers transformers to solve inherently serial problems 2 comments

    • Theoretical results exist that try to quantify the number of CoT tokens needed to reach different levels of computational expressibility: https://arxiv.org/pdf/2310.07923 TL;DR: Getting to Turing completeness can require polynomial CoT tokens, wrt the input problem size. For a…

      shawntanView on HNParent context

    • >How would that be remarkable, when it is exactly what he Universal Approximation Theorem already states Only with infinite precision, which is highly unrealistic. Under realistic assumptions, fixed depth transformer without chain-of-thought are very limited in what they can…

      logicchainsView on HNParent context

  13. Ilya Sutskever's SSI Inc raises $1B 1 comment

    • The theoretical foundation of transformers is well understood; they're able to approximate a very wide family of functions, particularly with chain of thought ( https://arxiv.org/abs/2310.07923 ). Training them on next-token-prediction is essentially training them to compress…

      logicchainsView on HNParent context

  14. Inductive or deductive? Rethinking the fundamental reasoning abilities of LLMs 1 comment
  15. The illusion of state in state-space models 1 comment
  16. Simple tasks showing reasoning breakdown in state-of-the-art LLMs 1 comment

    • >For reasoning of any complexity, some sort of internal monologue and iteration is needed. From a formal perspective you're entirely correct. Transformers with chain-of-thought are strictly more powerful than transformers without it, and can efficiently solve classes of problems…

      logicchainsView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.