A Formal Comparison Between Chain of Thought and Latent Thought — part 3/9

Cleaned-text code points [31710, 47035). Bibliography omitted here; source.md includes it.

We then move from token-level conditional distributions p ⁡ ( y i ∣ x , y < i ) p(y_{i}\mid x,y_{<i}) to the full sequence-level distribution p ⁡ ( y ∣ x ) p(y\mid x) . Beyond approximate counting, we establish a separation for approximate sampling problems. Specifically, we construct target distributions for which the complexity of each conditional can be reduced to approximate counting.

###### Theorem 4.4 .

Assume that 𝖥𝖯𝖳𝖠𝖲 ⊊ 𝖥𝖯𝖱𝖠𝖲 \mathsf{FPTAS}\subsetneq\mathsf{FPRAS} for self-reducible relations. There exists a distribution p ⁡ ( y ∣ x ) p(y\mid x) over y ∈ Σ ∗ y\in\Sigma^{*} and x ∈ Σ n x\in\Sigma^{n} such that a CoT with a polynomial number of steps, whose induced output conditionals are denoted by q ⁡ ( y i ∣ x , y < i ) q(y_{i}\mid x,y_{<i}) , admits an FPRAS for approximating the conditional probabilities p ⁡ ( y i ∣ x , y < i ) p(y_{i}\mid x,y_{<i}) for all x ∈ Σ n x\in\Sigma^{n} , indices i ≥ 1 i\geq 1 , and prefixes y < i ≔ ( y 1 , … , y i − 1 ) y_{<i}\coloneq(y_{1},\ldots,y_{i-1}) . In contrast, no latent thought with polynomially many iterations admits the same approximation guarantee.

###### Proof sketch.

Define the target distribution p p to be the uniform distribution supported on the solution set R ⁡ ( x ) R(x) . We rely on the classical result that approximate sampling from the uniform distribution over solutions, captured by the class 𝖥𝖯𝖠𝖴𝖲 \mathsf{FPAUS} , is polynomial-time inter-reducible with approximate counting for self-reducible relations ( Jerrum et al., 1986 ) . Let U ( ⋅ ∣ x ) U(\cdot\mid x) denote the uniform distribution over solutions of a self-reducible relation R ⁡ ( x ) R(x) . This distribution admits an autoregressive factorization U ⁡ ( y ∣ x ) = ∏ i = 1 m p ⁡ ( y i ∣ x , y < i ) , U(y\mid x)\;=\;\prod_{i=1}^{m}p(y_{i}\mid x,y_{<i}), where each conditional probability is given by p ( y i ∣ x , y < i ) = | { z ∈ Σ ∗ : ( x , y 1 : i + 1 z ) ∈ R } | | { z ∈ Σ ∗ : ( x , y 1 : i z ) ∈ R } | . p(y_{i}\mid x,y_{<i})=\frac{\bigl|\{\,z\in\Sigma^{*}:(x,y_{1:i+1}z)\in R\,\}\bigr|}{\bigl|\{\,z\in\Sigma^{*}:(x,y_{1:i}z)\in R\,\}\bigr|}. We show that each conditional probability, expressed as a ratio of subproblem counts, reduces to approximate counting. Then, applying Lemma 4.3 to these conditionals yields the desired separation for approximate sampling. ∎

Consequently, we obtain the following separations in favor of CoT, as also shown in Fig. 5 .

###### Theorem 4.5 .

Assuming 𝖥𝖯𝖳𝖠𝖲 ⊊ 𝖥𝖯𝖱𝖠𝖲 \mathsf{FPTAS}\subsetneq\mathsf{FPRAS} for self-reducible relations, it holds that ∀ ℳ ∈ { 𝗉𝖢𝖳 , 𝗉𝖫𝗈𝗈𝗉 } , ℳ ⁡ [ 𝗉𝗈𝗅𝗒 ⁡ ( n ) ] ⊊ 𝗉𝖢𝗈𝖳 ⁡ [ 𝗉𝗈𝗅𝗒 ⁡ ( n ) ] . \forall\,\mathcal{M}\in\{\mathsf{pCT},\mathsf{pLoop}\},\quad\mathcal{M}[\mathsf{poly}(n)]\subsetneq\mathsf{pCoT}[\mathsf{poly}(n)].

## 5 Experiments

In this section, we provide empirical validation of our theoretical results on tasks with well-characterized complexity. Specifically, we study parallelizable tasks to empirically validate the efficiency of latent thought predicted in Section 3 , and approximate counting and sampling tasks to demonstrate the effectiveness of CoT as shown in Section 4 .

### 5.1 Experimental Setting

##### Fundamental algorithmic reasoning tasks.

We use four problems. (1) Word problems for finite non-solvable groups: given a sequence of generators, the task is to evaluate their composition, which is 𝖭𝖢 1 \mathsf{NC}^{1} -complete ( Barrington, 1986 ) , also studied for Looped TF ( Merrill and Sabharwal, 2025a ) . (2) s s – t t connectivity (STCON): given a directed graph G = ( V , E ) G=(V,E) and two vertices s , t ∈ V s,t\in V , the task is to decide whether t t is reachable from s s , which belongs to 𝖳𝖢 1 \mathsf{TC}^{1} ( Gibbons and Rytter, 1989 ) . (3) Arithmetic expression evaluation: given a formula consisting of + , × , − , / +,\times,-,/ operations on integers, the task is to evaluate it. This problem is 𝖳𝖢 0 \mathsf{TC}^{0} -reducible to Boolean formula evaluation ( Feng et al., 2023 ) , which is 𝖭𝖢 1 \mathsf{NC}^{1} -complete ( Buss, 1987 ) . (4) Edit distance: given two strings x x and y y , the task is to compute the minimum cost to transform x x into y y . By reducing the dynamic programming formulation to shortest paths, this problem is in 𝖳𝖢 1 \mathsf{TC}^{1} ( Apostolico et al., 1990 ) .

##### Approximate counting tasks.

We consider DNF counting and uniform sampling of graph colorings, both of which admit fully polynomial randomized approximation schemes for counting and sampling (FPRAS and FPAUS). Specifically, DNF counting admits an FPRAS via Monte Carlo sampling ( Karp et al., 1989 ) , while approximate counting and sampling of graph colorings admit an FPAUS based on rapidly mixing Markov chain Monte Carlo under suitable degree and color constraints ( Jerrum, 1995 ) .

##### Training strategy.

Since our primary objective is to study expressive power, we allow flexibility in optimization and training strategies. For CoT models, training is performed with supervision from explicit sequential algorithms. For fewer CoT steps, we compare two strategies: uniformly selecting steps from the indices of the complete trajectory ( Bavandpour et al., 2025 ) , and stepwise internalization (distillation) methods ( Deng et al., 2024 ) . For latent thought, we observe that looped TF is easier to train than Coconut, and therefore adopt looped TF as our instantiation of latent thought, with curriculum learning applied to certain tasks.

### 5.2 Results

Table 2 reports results on parallelizable tasks, comparing latent thought and CoT under varying numbers of iterations. Latent thought solves the problems with fewer iterations than CoT requires to reach comparable performance. These empirical results are consistent with our theoretical analysis: latent thought supports efficient parallel reasoning, in contrast to the inherently sequential nature of CoT.

We also evaluate the relationship between performance, input size, and the number of iterations, as in prior studies ( Sanford et al., 2024b ; Merrill and Sabharwal, 2025a ) . Figure 6 presents our results for looped TFs, illustrating that as the input size n n increases, the number of loops required to maintain high accuracy grows only logarithmically, supporting our theoretical claim in the (poly-)logarithmic regime.

Figure 7 shows the results on the approximate counting or sampling tasks. For approximate counting, CoT performs Monte Carlo estimation: the effective number of samples is given by the product of the number of reasoning steps per trial and the number of independent trials. The probability mass plot illustrates how the empirical distribution over valid colorings compares to the target uniform distribution. We observe that CoT produces a distribution that is closer to uniform, whereas the looped model concentrates probability mass on a smaller subset of solutions. This indicates that CoT achieves more uniform coverage of the valid colorings.

## 6 Conclusion

We formally analyze the computational capabilities of chain-of-thought and latent thought reasoning, providing a rigorous comparison that reveals their respective strengths and limitations. Specifically, we show that latent thought enables efficient parallel computation, whereas CoT enables randomized approximate counting.Our results provide practical guidance for selecting between reasoning paradigms: latent reasoning is more suitable for problems that can be solved efficiently, whereas CoT is more effective for more complex problems. For future work, an important direction is to investigate whether techniques such as distillation can reduce the number of iterations without compromising computational power. Another promising avenue is to extend our analysis to diffusion language models, which possess both parallelizability and stochasticity. Moreover, extending the analysis to realistic downstream tasks remains an important direction.

## Impact Statement

This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.

## Appendix A Formal Definitions

### A.1 Notation

Vectors are written in lowercase bold letters (e.g., 𝒙 {\bm{x}} ) and matrices in uppercase bold letters (e.g., 𝑾 {\bm{W}} ). The i i -th entry of a vector 𝒙 {\bm{x}} is 𝒙 i {\bm{x}}_{i} , the vector from the i i -th to the j j -th entry is denoted by 𝒙 i : j {\bm{x}}_{i:j} , and the ( i , j ) (i,j) -th entry of a matrix 𝑾 {\bm{W}} is 𝑾 i , j {\bm{W}}_{i,j} . We use the symbol ∗ * to denote a “don’t care” value (or block of values). For n ∈ ℕ + n\in\mathbb{N}^{+} , let [ n ] ≔ { 1 , 2 , … , n } [n]\coloneq\{1,2,\ldots,n\} . We sometimes write column vectors horizontally, e.g., 𝒙 = ( x 1 , … , x n ) {\bm{x}}=(x_{1},\ldots,x_{n}) , for brevity. The Hadamard (element-wise) product is ⊙ \odot . 𝒆 i ∈ { 0 , 1 } d {\bm{e}}_{i}\in\{0,1\}^{d} is the i i -th standard basis vector, 𝟏 d ∈ ℝ d {\bm{1}}_{d}\in\mathbb{R}^{d} (or 1 d 1_{d} ) the all-ones vector, and 𝟎 d ∈ ℝ d {\bm{0}}_{d}\in\mathbb{R}^{d} the zero vector. 𝑰 d ∈ ℝ d × d {\bm{I}}_{d}\in\mathbb{R}^{d\times d} denotes the d × d d\times d identity matrix, and 𝟎 m × n ∈ ℝ m × n \mathbf{0}_{m\times n}\in\mathbb{R}^{m\times n} the m × n m\times n zero matrix. The indicator function is 𝟏 ​ [ ⋅ ] {\bm{1}}[\cdot] , and ⨁ \bigoplus denotes block-diagonal concatenation. Functions on scalars or vectors are written in upright letters (e.g., FFN \mathrm{FFN} ), while functions on matrices are boldface (e.g., 𝐀𝐓𝐓𝐍 \mathbf{ATTN} ). Boldface is also used when scalar- or vector-level functions are extended to sequence level and applied independently to each token (e.g., 𝐅𝐅𝐍 \mathbf{FFN} ). Finally, 𝗉𝗈𝗅𝗒 ⁡ ( n ) \mathsf{poly}(n) denotes the set of functions growing at most polynomially: 𝗉𝗈𝗅𝗒 ( n ) ≔ { f : ℕ → ℕ | ∃ k ∈ ℕ , ∃ c > 0 , ∀ n ∈ ℕ , f ( n ) ≤ c ⋅ n k } . \mathsf{poly}(n)\coloneq\left\{f:\mathbb{N}\to\mathbb{N}\;\middle|\;\exists k\in\mathbb{N},\;\exists c>0,\;\forall n\in\mathbb{N},\;f(n)\leq c\cdot n^{k}\right\}.

### A.2 Transformer Block

We define the computational components of a Transformer block using the notation of ( Merrill and Sabharwal, 2025a ) . Let 𝔽 s \mathbb{F}_{s} denote the set of s s -bit floating-point numbers with truncated arithmetic ( Definition B.1 ).

###### Definition A.1 (Transformer) .

A Transformer consists of the following components: 1. A word embedding function WE : 𝒱 → 𝔽 s m \mathrm{WE}:{\mathcal{V}}\to\mathbb{F}_{s}^{m} , where 𝒱 {\mathcal{V}} denotes the vocabulary set.

2. A positional embedding function PE : ℕ → 𝔽 s m \mathrm{PE}:\mathbb{N}\to\mathbb{F}_{s}^{m} .

3. A multi-head self-attention layer 𝐒𝐀 : 𝔽 s m × N → 𝔽 s m × N \mathbf{SA}:\mathbb{F}_{s}^{m\times N}\to\mathbb{F}_{s}^{m\times N} for arbitrary sequence length N N , parameterized by a matrix 𝑶 : 𝔽 s s × H → 𝔽 s m {\bm{O}}:\mathbb{F}_{s}^{s\times H}\to\mathbb{F}_{s}^{m} and, for each head h ∈ [ H ] h\in[H] with head size s s , matrices 𝑸 h , 𝑲 h , 𝑽 h : 𝔽 s m → 𝔽 s s {\bm{Q}}_{h},{\bm{K}}_{h},{\bm{V}}_{h}:\mathbb{F}_{s}^{m}\to\mathbb{F}_{s}^{s} . Given an input 𝒙 i ∈ 𝔽 s m {\bm{x}}_{i}\in\mathbb{F}_{s}^{m} for each position i ∈ [ N ] i\in[N] , it computes the query 𝐪 i , h = 𝑸 h ​ 𝒙 i \mathbf{q}_{i,h}={\bm{Q}}_{h}{\bm{x}}_{i} , key 𝒌 i , h = 𝑲 h ​ 𝒙 i {\bm{k}}_{i,h}={\bm{K}}_{h}{\bm{x}}_{i} , and value 𝐯 i , h = 𝑽 h ​ 𝒙 i \mathbf{v}_{i,h}={\bm{V}}_{h}{\bm{x}}_{i} , and outputs 𝑶 ⋅ ( 𝒂 i , 1 , … , 𝒂 i , H ) , {\bm{O}}\cdot({\bm{a}}_{i,1},\ldots,{\bm{a}}_{i,H}), where each attention output 𝒂 i , h {\bm{a}}_{i,h} is defined, for softmax function, as: 𝒂 i , h = ∑ j = 1 c ⁡ ( i ) exp ⁡ ( 𝐪 i , h ⊤ ​ 𝒌 j , h ) Z i , h ⋅ 𝐯 j , h , Z i , h = ∑ j = 1 c ⁡ ( i ) exp ⁡ ( 𝐪 i , h ⊤ ​ 𝒌 j , h ) , {\bm{a}}_{i,h}=\sum_{j=1}^{c(i)}\frac{\exp(\mathbf{q}_{i,h}^{\top}{\bm{k}}_{j,h})}{Z_{i,h}}\cdot\mathbf{v}_{j,h},\quad Z_{i,h}=\sum_{j=1}^{c(i)}\exp(\mathbf{q}_{i,h}^{\top}{\bm{k}}_{j,h}), (1) with c ⁡ ( i ) = i c(i)=i for causal attention and c ⁡ ( i ) = N c(i)=N for full attention. For the saturated hardmax attention ( Merrill et al., 2022 ) , each attention output 𝒂 i , h {\bm{a}}_{i,h} is defined as: 𝒂 i , h = ∑ j ∈ M i , h 1 | M i , h | ​ 𝐯 j , h , M i , h = { j ∈ [ c ⁡ ( i ) ] | 𝐪 i , h ⊤ ​ 𝒌 j , h = max j ′ ⁡ 𝐪 i , h ⊤ ​ 𝒌 j ′ , h } . {\bm{a}}_{i,h}=\sum_{j\in M_{i,h}}\frac{1}{|M_{i,h}|}\,\mathbf{v}_{j,h},\quad M_{i,h}=\left\{j\in[c(i)]\;\middle|\;\mathbf{q}_{i,h}^{\top}{\bm{k}}_{j,h}=\max_{j^{\prime}}\mathbf{q}_{i,h}^{\top}{\bm{k}}_{j^{\prime},h}\right\}. (2)

4. A feedforward layer FF : 𝔽 s m → 𝔽 s m \mathrm{FF}:\mathbb{F}_{s}^{m}\to\mathbb{F}_{s}^{m} with parameter 𝑾 1 : 𝔽 s m → 𝔽 s w {\bm{W}}_{1}:\mathbb{F}_{s}^{m}\to\mathbb{F}_{s}^{w} , 𝑾 2 : 𝔽 s w → 𝔽 s m {\bm{W}}_{2}:\mathbb{F}_{s}^{w}\to\mathbb{F}_{s}^{m} , and 𝒃 ∈ 𝔽 s m {\bm{b}}\in\mathbb{F}_{s}^{m} , where w w is the hidden dimension. Given an input 𝒙 i ∈ 𝔽 s m {\bm{x}}_{i}\in\mathbb{F}_{s}^{m} , it outputs 𝑾 2 ​ ReLU ​ ( 𝑾 1 ​ 𝒙 i + 𝒃 ) {\bm{W}}_{2}\mathrm{ReLU}({\bm{W}}_{1}{\bm{x}}_{i}+{\bm{b}}) , where ReLU ⁡ ( 𝒙 ) = ( max ⁡ { 0 , 𝒙 1 } , … , max ⁡ { 0 , 𝒙 m } ) ⊤ \mathrm{ReLU}({\bm{x}})=(\max\{0,{\bm{x}}_{1}\},\ldots,\max\{0,{\bm{x}}_{m}\})^{\top} .

5. An output function 𝐎𝐔𝐓 : 𝔽 s m → 𝔽 s | 𝒱 | \mathbf{OUT}:\mathbb{F}_{s}^{m}\to\mathbb{F}_{s}^{|{\mathcal{V}}|} , parameterized as a linear transformation.

### A.3 Chain of Thought

###### Definition A.2 (CoT) .

Let the Transformer be defined as the composition: TF dec ≔ 𝐎𝐔𝐓 ∘ ( id + 𝐅𝐅 L ) ∘ ( id + 𝐒𝐀 L ) ∘ ⋯ ∘ ( id + 𝐅𝐅 1 ) ∘ ( id + 𝐒𝐀 1 ) ∘ ( 𝐖𝐄 + 𝐏𝐄 ) , \mathrm{TF}_{\mathrm{dec}}\coloneq\mathbf{OUT}\circ(\id+\mathbf{FF}_{L})\circ(\id+\mathbf{SA}_{L})\circ\cdots\circ(\id+\mathbf{FF}_{1})\circ(\id+\mathbf{SA}_{1})\circ(\mathbf{WE}+\mathbf{PE}), (3) where 𝐒𝐀 ℓ \mathbf{SA}_{\ell} and 𝐅𝐅 ℓ \mathbf{FF}_{\ell} denote the causal attention and the feedforward layers at depth ℓ ∈ [ L ] \ell\in[L] , respectively, and id \id denotes the identity function. The input tokens are first embedded via the word embedding function 𝐖𝐄 \mathbf{WE} and the positional encoding 𝐏𝐄 \mathbf{PE} , and the final output is produced by a linear projection 𝐎𝐔𝐓 \mathbf{OUT} . Given an input sequence x = ( x 1 , … , x n ) ∈ 𝒱 n x=(x_{1},\dots,x_{n})\in{\mathcal{V}}^{n} , we define the initial sequence as: f cot 0 ​ ( x ) ≔ x . f_{\mathrm{cot}}^{0}(x)\coloneq x. Then, the CoT computes recursively as: f cot k + 1 ​ ( x ) ≔ f cot k ​ ( x ) ⋅ Dec ⁡ ( TF dec ​ ( f cot k ​ ( x ) ) ) , f_{\mathrm{cot}}^{k+1}(x)\coloneq f_{\mathrm{cot}}^{k}(x)\cdot\mathrm{Dec}\,(\mathrm{TF}_{\mathrm{dec}}(f_{\mathrm{cot}}^{k}(x))), (4) where ⋅ \cdot denotes concatenation, and Dec ⁡ ( ⋅ ) \mathrm{Dec}(\cdot) is a decoding function that maps the output logits to a token in 𝒱 {\mathcal{V}} : in the deterministic model, Dec ⁡ ( z ) ≔ arg ⁡ max i ∈ [ | 𝒱 | ] ⁡ z i \mathrm{Dec}(z)\coloneq\arg\max_{i\in[|{\mathcal{V}}|]}z_{i} ; in the stochastic model, Dec ⁡ ( z ) ∼ Multinomial ⁡ ( z i / ∑ j z j ) \mathrm{Dec}(z)\sim\mathrm{Multinomial}({z_{i}}/{\sum_{j}z_{j}}) , assuming z i > 0 z_{i}>0 for all i i . The final output of the CoT model after T ⁡ ( n ) T(n) steps is defined as the last output length m m tokens of f cot T ⁡ ( n ) ​ ( x ) f_{\mathrm{cot}}^{T(n)}(x) .

### A.4 Continuous Thought

###### Definition A.3 (Coconut) .