The Impact of Randomness in CoT: Addressing Stochasticity in Formal Models

Chain-of-Thought (CoT) has proved to be a highly effective method to improve the accuracy of Large Language Models (LLMs). Although there are intuitive explanations for its effectiveness and ongoing efforts to formalize its power, its limits remain unclear. One approach to understanding CoT is grounded on computational complexity theory and relies on modeling LLMs with CoT as a family of shallow circuits equipped with a mechanism to do recursion. Such formalizations yield upper bounds on the power of bounded CoT, as well as lower bounds on the required number of steps necessary to solve particular problems such as parity or reachability. However, many of these abstractions ignore the stochastic component of CoT: in practice, LLMs can sample from a probability distribution over the next token at each step, rather than selecting it deterministically, as assumed by previous formal models. In this paper we address this limitation by introducing a more realistic model that includes the stochastic components of LLMs. We show that the complexity classes associated to this model are robust and well-behaved. Moreover, we adapt existing theoretical results on upper and lower bounds for deterministic models of LLMs to our setting. Finally, we show how deterministic and stochastic models relate to one another and with Turing Machines. These results suggest a framework for assessing when a stochastic abstraction of LLMs is necessary and when a deterministic abstraction is sufficiently faithful for the question under study. By extending previous theoretical findings to the stochastic setting, our work provides a stronger theoretical foundation for the experiments reported in prior work.