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.

现代语言模型的性能已通过思维链推理得到改进，思维链推理扩展了语言模型的计算能力，但也引入了类别错误，为此我们在概率模型中形式化思维链推理，并通过对序列生成模型的表示能力进行研究，证明它们可以表示与概率图灵机相同的字符串分布。

神经语言模型的表示能力与思维链式推理

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

Finding "densely connected clusters" in a graph is in general an important
and well studied problem in the literature \cite{Schaeffer}. It has various
applications in pattern recognition, social networking and data mining
\cite{Duda,Mishra}. Recently, Ames and Vavasis have suggested a novel method
for finding cliques in a graph by using convex optimization over the adjacency
matrix of the graph \cite{Ames, Ames2}. Also, there has been recent advances in
decomposing a given matrix into its "low rank" and "sparse" components
\cite{Candes, Chandra}. In this paper, inspired by these results, we view
"densely connected clusters" as imperfect cliques, where imperfections
correspond missing edges, which are relatively sparse. We analyze the problem
in a probabilistic setting and aim to detect disjointly planted clusters. Our
main result basically suggests that, one can find \emph{dense} clusters in a
graph, as long as the clusters are sufficiently large. We conclude by
discussing possible extensions and future research directions.

本文基于凸优化和矩阵分解的最新成果，将 “密集连接群集” 视为不完美的团，利用概率性方法分析问题并旨在检测孤立的种植群集。我们的主要结论基本上是，只要群集足够大，就可以在图中找到密集的群集。