acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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.

Primary area:
learning theory
Keywords:
Chain Of Thought (CoT), Language modeling, Circuit complexity, Randomness

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_qBiMOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper formalizes bounded-error sampled CoT for constant-depth, constant-precision Transformers. It extends circuit upper bounds and sensitivity-based lower bounds to this setting, and relates polynomial-resource probabilistic CoT to P/poly in the nonuniform setting and BPP under uniformity.

Critical strengths

The overall framework is conceptually clean.

Critical weaknesses

I find the technical novelty somewhat limited: extensions from deterministic to randomized computation follow naturally from existing simulations and standard probabilistic techniques.

Questions for authors

The paper could more clearly identify the new technical ideas required beyond adapting the existing deterministic proofs.

2 comments
AuthorsOpenReview ↗

Response to Reviewer 3

The questions of Reviewer 3 coincide with those of Reviewer 2. Please see our response to Reviewer 2, Question 1, for a theorem-by-theorem comparison with previous results. Also, in the revised version we add a sentence before each result to separate our contribution from the techniques of previous work. For the question about fine-grained regimes, please see our response to Reviewer 1, Question 3, where we describe the new applications to primality testing and polynomial identity testing. Finally, regarding the claim of a "more realistic model", please see the end of our response to Reviewer 2: we modified the abstract and the conclusions to state precisely which aspect of LLMs our model incorporates and which assumptions remain.

Thanks for the responses. My concern largely remains. I keep my score.

Reviewer_Lq5dOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper extends complexity-theoretic models of transformers with bounded chain-of-thought from deterministic next-token selection to stochastic sampling. It defines the class BPCoT parameterized by CoT length and embedding dimension, establishes closure under Boolean operations and error reduction, and adapts several existing circuit upper and lower bounds to the probabilistic setting. In particular, it shows that logarithmically many CoT steps remain within AC0 under the stated constant-depth and constant-precision assumptions, gives simulations for polylogarithmic CoT, extends sensitivity-based lower bounds for parity and reachability, and characterizes polynomially bounded nonuniform probabilistic CoT as BPP/poly = P/poly. The paper also studies uniform families, where deterministic and probabilistic polynomial CoT correspond to P and BPP, respectively.

Critical strengths
  • The paper addresses a real mismatch in prior formal models of CoT: practical decoding may sample from the next-token distribution, while many circuit-complexity analyses assume deterministic argmax selection. The BPCoT definition provides a coherent framework for asking which upper and lower bounds survive bounded-error sampling.
  • At a high level, the main arguments are logically consistent. Constant-precision sampling uses a bounded number of random bits per step, logarithmic CoT permits enumeration together with approximate majority, and fixing the random seed allows deterministic sensitivity arguments to be transferred. The distinction between uniform and nonuniform families also makes clear why polynomial-resource stochastic and deterministic models have different interpretations even when their nonuniform classes collapse.
Critical weaknesses
  • The main conceptual contribution appears incremental. Many arguments follow the standard pattern of fixing or enumerating the random seed and then applying a deterministic transformer result, approximate majority, or Adleman's theorem. The paper collects a broad set of consequences, but it does not clearly identify which theorem requires a genuinely new idea caused by autoregressive token sampling. This distinction is particularly important because the paper already cites concurrent formal work on stochastic CoT.
  • The conclusions do not answer the practical question used to motivate the paper. Equality such as BPP/poly = P/poly at polynomial resources does not imply that deterministic and probabilistic transformers require the same number of CoT steps, that randomness provides no polynomial speedup, or that sampling is unimportant for a finite trained model. In addition, the formalism still assumes constant depth and precision, a fixed alphabet, no layer normalization, and in some results nonuniform advice. These are valid assumptions for a circuit-complexity theorem, but they make “a more realistic model of LLMs” an overstatement unless the claims are explicitly restricted to this abstraction.
Questions for authors
  1. Which theorem requires a new technical argument beyond conditioning on or enumerating the random seed and applying the corresponding deterministic result? A theorem-by-theorem comparison with Li et al., Chen et al., and Xu and Sato would materially change my assessment of novelty.
  2. Is there a fine-grained regime in the proposed framework where stochastic sampling provably changes the required number of CoT steps? The current polynomial-class equalities characterize eventual expressiveness but do not establish whether randomness changes reasoning efficiency.
1 comment
AuthorsOpenReview ↗

Response to Reviewer 2

Q1. Which theorem requires a new technical argument beyond conditioning on or enumerating the random seed and applying the corresponding deterministic result?

We agree with the reviewer that some of our results are incremental extensions of previous ones, and that the paper should state our contributions more precisely. In the revised version, we added a sentence before each result describing which parts of the proof follow previous work and how we extend them, and the introduction now lists our contributions explicitly. The main new technical arguments we want to highlight are the following:

  • Closure properties (Propositions 3.1–3.3). These had not been stated before, even for the deterministic classes of Li et al. The ideas are standard, but implementing them with constant-precision softmax attention requires new constructions.
  • Averaging argument (Theorem 4.5). In the sensitivity argument, to bound the sensitivity of the function computed with error ε\varepsilon, we run neighboring inputs with the same random bits, which yields the factor (1−2ε)(1-2\varepsilon).
  • Transfer along reductions (Proposition 4.1). We show how sensitivity-based CoT lower bounds transfer along AC0\mathsf{AC}^0 reductions. This tool is also new for deterministic transformers, and gives a lower bound for reachability in softmax transformers with constant precision (Corollary 4.4), previously shown only for hard attention.
  • Deterministic vs. stochastic decoding (Theorem 5.1). Although expected, this simulation is not immediate, since sampling from a distribution and taking its argmax may produce different tokens.
  • Applications (Section 4.4, Theorems 4.6 and 4.7). We apply our bounds to two problems that are easily solved with randomization. For primality testing, probabilistic transformers need only O~(n2)\widetilde O(n^2) CoT steps, compared with O~(n6)\widetilde O(n^6) for the best known deterministic construction. For polynomial identity testing, we combine the circuit simulation of Theorem 4.4 with the transfer of Proposition 4.1 to determine the number of CoT steps up to polylogarithmic factors. These results illustrate how randomness can reduce the best known number of CoT steps (see Q2).

As requested, the following table compares each result with previous work:

ResultPrevious workNew in this paper
Def. 3.1CoT[T,d]\mathsf{CoT}[T,d] (Li et al.)BPCoT[T,d]\mathsf{BPCoT}[T,d]
Props. 3.1–3.3—Closure properties for CoT and BPCoT
Lem. 4.1—We show that one sampling step can be done in BPAC0[1]\mathsf{BPAC}^0[1]
Thms. 4.1–4.2Li et al., Thm. 3.1 (for the deterministic case)We simply enumerate seeds and use a promise majority
Thm. 4.3Xu & Sato, Lemma 3.13 (for the deterministic case)We include the random bits as circuit inputs to their construction
Thm. 4.4Li et al., Thm. 3.3 (for the deterministic case)Idem previous row
Lem. 4.2Chen et al., proof of Thm. 4.2We apply their result to the function obtained after fixing the random bits
Thm. 4.5, Cor. 4.3Chen et al.We use an averaging argument on top of their result
Prop. 4.1, Cor. 4.4We use the classical parity reduction already considered in Amiri Bavandpour et al.The new result is a general lower bound transfer along AC0\mathsf{AC}^0 reductions, which gives a lower bound for reachability in the softmax regimme
Thms. 4.6–4.7—Upper bounds via Thm. 4.4 and matching lower bound via Prop. 4.1
Thm. 5.1—New (see the normal form in Appendix E)
Cors. 5.1–5.4, Thms. 5.2–5.3Li et al.This are just immediate consequences from previous results

Q2. Is there a fine-grained regime in the proposed framework where stochastic sampling provably changes the required number of CoT steps?

Please see our response to Reviewer 1, Question 3. In short, we added a new section (Section 4.4) that applies our results to primality testing and polynomial identity testing, two problems that are easily solved with randomized algorithms but for which no comparably efficient deterministic algorithm is known. For both problems, the best known CoT bounds for stochastic transformers are polynomially smaller than those for deterministic transformers.

On the claim of a "more realistic model". We agree with the reviewer. Our model addresses one aspect that previous formal models leave out (the randomness of next-token selection), and it keeps their other simplifying assumptions, such as constant depth and precision, a fixed alphabet, and no layer normalization. We modified the abstract accordingly: in it we simply state that we incorporate the stochastic component of decoding while keeping the other assumptions of previous formal models. The conclusions now list the remaining assumptions as directions for future work.

Reviewer_4KQ1OpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

The paper extends the constant-depth, constant-precision transformer model from deterministic decoding to stochastic next-token sampling. It introduces probabilistic CoT complexity classes, establishes that several upper and lower bounds from deterministic CoT carry over, and characterizes relationships among deterministic transformers, probabilistic transformers, and Turing machines.

Critical strengths

The motivation of the paper is clear. Existing analyses primarily study deterministic CoT, leaving open whether randomness increases expressivity. The paper develops a useful formal framework through the definition of BPCoT and its closure and error-reduction properties. Its distinction between uniform and nonuniform computation clarifies how constructibility assumptions affect the power of randomness. Extending sensitivity-based lower bounds to stochastic CoT is particularly interesting and provides a promising direction for understanding its limitations.

Critical weaknesses

Several results offer limited conceptual novelty. Theorem 5.1 and Corollary 5.1 formalize the inclusion of deterministic CoT within stochastic CoT, which is completely unsurprising. Other results such as Corollaries 5.2-5.3 build on simulation results and standard complexity-theoretic facts. Many proofs appear to adapt existing deterministic constructions. Overall, the contribution largely establishes that known characterizations and limitations persist under stochastic decoding, without identifying a task where BPCoT[T(n),d(n)]\mathsf{BPCoT}[T(n),d(n)] provably outperforms CoT[T(n),d(n)]\mathsf{CoT}[T(n),d(n)].

Two technical points also require clarification. First, the finite-precision softmax does not generally guarantee outputs that sum to one, whereas the sampling proofs assume a valid probability distribution. Second, the justification of uniformity is incomplete. Section 5.1 defines logspace-uniform families, but Corollary 5.4 invokes nonuniform characterizations and the existence of construction algorithms without establishing their logarithmic-space complexity. The conclusion’s reference to polynomial-time uniformity further obscures which guarantee is intended.

Questions for authors
  1. How is the finite-precision softmax output converted into a valid probability distribution, and does this conversion preserve the claimed simulation bounds?

  2. Can the authors explicitly establish that the constructions underlying Corollary 5.4 are computable in logarithmic space?

  3. Is there a concrete task, possibly under a stated complexity assumption, for which stochastic CoT provably requires fewer steps than deterministic CoT with comparable depth, precision, and embedding dimension?

2 comments
AuthorsOpenReview ↗

Response to Reviewer 1

Q1. How is the finite-precision softmax output converted into a valid probability distribution, and does this conversion preserve the claimed simulation bounds?

This was indeed a problem that we missed. In the revised version, the sampling step mimics what practical implementations do: the probabilities are renormalized by their total sum when defining the cumulative ranges of the tokens, the limits of these ranges are computed in the same finite-precision arithmetic, and the next token is selected by locating a uniformly random number, represented with a fixed number of bits (see Appendix G for the details). This conversion preserves all the simulation bounds.

Q2. Can the authors explicitly establish that the constructions underlying Corollary 5.4 are computable in logarithmic space?

The reviewer is right: the submission defined logarithmic-space-uniform families, while the arguments behind Corollary 5.4 only gave polynomial-time constructions, and the conclusion referred to polynomial-time uniformity. For clarity and simplicity, the revised version uses P\mathsf{P}-uniform families throughout. With this choice, all the uniform results have complete proofs.

We note that some of these proofs do not carry over to logarithmic space immediately. For instance, the construction of Li et al. needs the gates of the circuit in topological order, which can be computed in polynomial time but, as far as we know, not in logarithmic space in general. Although we believe that most results hold for logarithmic-space-uniform families, we do not think that this extension would add much to the current state of the paper. Nonetheless, we remark in the main text that the choice of uniformity is not essential.

Q3. Is there a concrete task, possibly under a stated complexity assumption, for which stochastic CoT provably requires fewer steps than deterministic CoT?

The other reviewers raised the same question, so we used the additional page of the revision to add applications of our upper and lower bounds (see Section 4.4). We consider two problems that are easily solved with randomization, but for which no comparably efficient deterministic algorithm is known: primality testing (through the Miller–Rabin test) and polynomial identity testing (through the Schwartz–Zippel lemma). For the former one, we give an upper bound much better than the best known upper bound for deterministic transformers (O~(n2)\widetilde O(n^2) versus O~(n6)\widetilde O(n^6) CoT steps). For the latter one we use both our upper and lower bound techniques to bound the CoT required for the task up to polylogarithmic factors.

Thank you for these updates. Unfortunately, my overall assessment of the paper remains largely unchanged.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Response

General response to all reviewers

We thank the reviewers for their careful reading and their constructive feedback. As they observed, our goal with this paper is to address the mismatch between most formal models of CoT (which assume deterministic next-token selection) and real models (which use sampling to select the next token). We have uploaded a revised version of the paper that addresses many of the reviewers' comments. Below, we answer the questions they posed one by one, and we summarize the changes at the end. All the references to the paper correspond to the new version. In the supplementary material we also attach a diff file to make it easier to see the differences.

Summary of changes

  • Sampling with finite precision (Lemma 4.1). We fixed the issue observed by Reviewer 1 that, with finite-precision arithmetic, the output of the softmax may not be a probability distribution. Now, as in practical LLM implementations, the probabilities are renormalized by their total sum before sampling, and the limits of the sampling ranges are computed in finite precision (so a constant number of random bits are still enough to select the token exactly).
  • Uniformity (Definition 3.2, Section 5.1). All uniform results now consistently use P\mathsf{P}-uniform families, which keeps the proofs complete and simple. We believe that most of the arguments can be extended to logarithmic-space-uniform families, but we decided to postpone such analysis for later work.
  • Contributions. We added a sentence before each result stating which parts of the proof follow previous work and which ideas are new, and the introduction now describes our contributions explicitly.
  • Scope of the model. We no longer claim a more realistic model of LLMs. The abstract now states that we incorporate the missing randomness of decoding while keeping the other simplifying assumptions of previous formal models. Also, the conclusions list many extensions as directions for future work.
  • Applications (new Section 4.4). We added applications of our upper and lower bounds to primality testing and polynomial identity testing. The resulting bounds for stochastic transformers improve on the best known bounds for deterministic transformers, and for polynomial identity testing they are tight up to polylogarithmic factors.

We believe that thanks to the reviews we were able to improve the quality of the paper and to properly place it in the context of other recent literature.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.