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

Abstract: 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.

## introduction motivated by how humans solve complex problems by noting down intermediary results, wei et al. (2022b) introduced chain-of-thought (cot) reasoning. @xcite cot reasoning helps language models (lms) solve reasoning tasks by allowing them to store intermediary results in a scratch space that is not part of the final output. the empirical success of cot reasoning has made it an established component of modern neural lms (nye et al., 2021; wei et al., 2022a,b; suzgun et al., 2022; kojima et al., 2023; wies et al., 2023)-seemingly overnight. such empirical success motivates a thorough understanding of the abilities of cot-augmented lms. while existing theoretical treatments have shed light on some aspects of this framework, we are still far from a concrete theoretical understanding of cot (feng et al., 2023). probabilistic unrestricted languages unbounded precision transformers thm. 4.5 g gggggggggggg b f gggggggggggg g thm. 4.6 probabilistic turing machines e gggggggggggg g g gggggggggggg c thm. 4.4 unbounded precision elman rnns probabilistic regular languages probabilistic finite state automata fixed-precision elman rnns thm. 4.2 g gggggggggggg b f gggggggggggg g thm. 4.1 fixed-precision transformers d gggggggggggg g thm. 4.3 neural architecture with cot reasoning corresponding model of computation figure 1: a schematic overview of our main results, showing which neural language models extended with cot reasoning (left) correspond to which probabilistic models of computation (right). we address the first point by analyzing cotaugmented lms using probabilistic models of computation, which provide a convenient way of describing families of distributions over strings with standard models of sequential reasoning. to address the second point, we define a new type of relationship between language models, which we call regular reducibility. intuitively, an lm is regularly reducible into another one if the strings generated by the latter are sufficiently simple transformations of those generated by the former. an instance of such a transformation is the deletion of the intermediary computation steps of cot reasoning. formalizing cot reasoning in this framework, we find that it increases the computational power in both rnn and transformer lms. concretely, we find that cot-augmented constant-precision rnn lms are equivalent to probabilistic finitestate automata (pfsas). this is in contrast to the constant-precision rnn lms without cot reasoning, which are equivalent to deterministic pfsas (svete and cotterell, 2023). additionally, we show how turing-complete linear-precision rnn lms can be thought of as performing cot reasoning. finally, we show that both linearly bounded precision rnn lms and logarithmically bounded precision decoder-only transformer lms with cotreasoning can simulate any probabilistic turing machine. taken together, our results frame cot reasoning in pure language modeling terms and describe its intuitive and formal connections to probabilistic models of computation. ## preliminaries in our analysis, we assume rational (rather than real) arithmetic for all definitions and computations. ## cot reasoning and weak equivalence in this section, we argue that cot reasoning can be seen as a way of comparing the input language of a formal automaton with the output language of an autoregressive lm. we then introduce a formalization of cot reasoning that allows us to characterize the representational capabilities of cot-augmented lms in terms of their weak equivalence to wellstudied weighted automata. ## cot and representational capacity we now connect the notions introduced in §3 to the representational capacity of neural lms. we begin in §4.1 by showing how cot reasoning endows autoregressive lms with non-determinism by using scratch space to keep track of the current branch of execution. we then use similar principles to emulate probabilistic turing machines with elman rnns ( §4.2.1) and transformers ( §4.2.2).