A Formal Comparison Between Chain of Thought and Latent Thought โ€” part 2/9

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

size โก ( G n ) โˆˆ ๐—‰๐—ˆ๐—…๐—’ โก ( n ) \mathrm{size}(G_{n})\in\mathsf{poly}(n) .

###### Assumption 3.4 (Poly-efficient approximation, cf. ( Feng et al., 2023 ) ) .

Each node function of G n G_{n} can be approximated by a log-precision feedforward network whose parameter size is polynomial in the input length and the inverse of the approximation error. We denote by ff โ€‹ _ โ€‹ param โ€‹ ( G n ) \mathrm{ff\_param}(G_{n}) an upper bound such that every f โˆˆ โ„ฑ f\in\mathcal{F} admits such a network with at most ff โ€‹ _ โ€‹ param โ€‹ ( G n ) \mathrm{ff\_param}(G_{n}) parameters.

Under these assumptions, we show that CoT can simulate computation by sequentially decoding nodes, where intermediate tokens serve as a scratchpad allowing the evaluation of each node once all its predecessors have been computed.

###### Theorem 3.5 (CoT for DAGs) .

Let { G n } n โˆˆ โ„• \{G_{n}\}_{n\in\mathbb{N}} be a family of computation graphs that satisfy Assumptions 3.3 and 3.4 . Then, for each n โˆˆ โ„• n\in\mathbb{N} , there exists a log-precision CoT with parameter size bounded by O โก ( ff โ€‹ _ โ€‹ param โ€‹ ( G n ) ) O(\mathrm{ff\_param}(G_{n})) , such that for every input x โˆˆ ฮฃ n x\in\Sigma^{n} , the model outputs F G n โ€‹ ( x ) F_{G_{n}}(x) with steps proportional to the โ€œsizeโ€ of the graph, i.e., O โก ( size โก ( G n ) ) O(\mathrm{size}(G_{n})) .

###### Proof sketch.

At each step, the attention layer retrieves the outputs of predecessor nodes from previously generated tokens, and a feed-forward layer then computes the node function, whose output is generated as the next token. โˆŽ

In contrast, latent thought can operate in parallel, layer by layer, where all nodes at the same depth are computed simultaneously, provided that the model has sufficient size.

###### Theorem 3.6 (Latent thought for DAGs) .

Let { G n } n โˆˆ โ„• \{G_{n}\}_{n\in\mathbb{N}} be a family of computation graphs that satisfy Assumptions 3.3 and 3.4 . Then, for each n โˆˆ โ„• n\in\mathbb{N} , there exists a log-precision Coconut and looped TF with parameter size O โก ( ff โ€‹ _ โ€‹ param โ€‹ ( G n ) โ‹… size โก ( G n ) ) O(\mathrm{ff\_param}(G_{n})\cdot\mathrm{size}(G_{n})) , such that for every input x โˆˆ ฮฃ n x\in\Sigma^{n} , it computes F G n โ€‹ ( x ) F_{G_{n}}(x) with iterations proportional to the โ€œdepthโ€ of the graph G n G_{n} , i.e., O โก ( depth โก ( G n ) ) O(\mathrm{depth}(G_{n})) .

###### Proof sketch.

The role assignment of each layer is based on ( Li et al., 2024 ) , as shown in Figure 9 . An attention layer aggregates its inputs into a single hidden state. Unlike discrete tokens, continuous latent states allow the simultaneous encoding of the outputs of multiple nodes, enabling the feed-forward layer to compute node functions in parallel. โˆŽ

##### Remark.

Illustrations are provided in Fig. 2 , with formal proofs deferred to Appendix B . These results reveal distinct characteristics: CoT can utilize intermediate steps as scratchpad memory and perform computations sequentially, whereas latent thought can leverage structural parallelism to achieve greater efficiency with sufficient resources.

### 3.3 Separation in Polylogarithmic Iterations

In this section, we shift to formal decision problems to precisely characterize the computational power of each reasoning paradigm, clarify what cannot be achieved, and use these limitations to derive rigorous separations. We begin by defining their complexity classes, as in ( Li et al., 2024 ) .

###### Definition 3.7 (Complexity Classes ๐–ข๐—ˆ๐–ณ \mathsf{CoT} , ๐–ข๐–ณ \mathsf{CT} and ๐–ซ๐—ˆ๐—ˆ๐—‰ \mathsf{Loop} ) .

Let ๐–ข๐—ˆ๐–ณ โก [ T โก ( n ) , d โก ( n ) , s โก ( n ) ] \mathsf{CoT}[T(n),d(n),s(n)] , ๐–ข๐–ณ โก [ T โก ( n ) , d โก ( n ) , s โก ( n ) ] \mathsf{CT}[T(n),d(n),s(n)] , and ๐–ซ๐—ˆ๐—ˆ๐—‰ โก [ T โก ( n ) , d โก ( n ) , s โก ( n ) ] \mathsf{Loop}[T(n),d(n),s(n)] denote the sets of languages โ„’ : { 0 , 1 } โˆ— โ†’ { 0 , 1 } {\mathcal{L}}:\{0,1\}^{*}\to\{0,1\} for which there exists a deterministic CoT, Coconut, and looped TF, respectively, denoted by M n M_{n} for each input size n n , with embedding size O โก ( d โก ( n ) ) O(d(n)) and O โก ( s โก ( n ) ) O(s(n)) bits of precision, such that for all x โˆˆ { 0 , 1 } n x\in\{0,1\}^{n} , the final output token after O โก ( T โก ( n ) ) O(T(n)) iterations equals โ„’ โก ( x ) {\mathcal{L}}(x) .

Boolean circuits serve as a standard formal model of computation, where processes are defined by the evaluation of DAGs with well-established complexity measures.

###### Definition 3.8 (Informal) .

A Boolean circuit is a DAG over the alphabet ฮฃ = { 0 , 1 } \Sigma=\{0,1\} , where each internal node (gate) computes a Boolean function such as AND, OR, or NOT. ๐–ฒ๐–จ๐–น๐–ค โก [ s โก ( n ) ] \mathsf{SIZE}[s(n)] and ๐–ฃ๐–ค๐–ฏ๐–ณ๐–ง โก [ d โก ( n ) ] \mathsf{DEPTH}[d(n)] denote the class of languages decidable by a non-uniform circuit family { C n } \{C_{n}\} with size O โก ( s โก ( n ) ) O(s(n)) and depth O โก ( d โก ( n ) ) O(d(n)) , respectively.

First, we formalize the results of the previous section to show that latent thought iterations can represent circuit depth, whereas CoT corresponds to circuit size.

###### Theorem 3.9 ( Li et al., 2024 ) .

โˆ€ T โก ( n ) โˆˆ poly โก ( n ) , \forall T(n)\in\mathrm{poly}(n), ๐–ฒ๐–จ๐–น๐–ค โก [ T โก ( n ) ] โŠ† ๐–ข๐—ˆ๐–ณ โก [ T โก ( n ) , log โก n , 1 ] . \mathsf{SIZE}[T(n)]\subseteq\mathsf{CoT}[T(n),\log{n},1].

###### Theorem 3.10 .

For any function T โก ( n ) โˆˆ poly โก ( n ) T(n)\in\mathrm{poly}(n) and any non-uniform circuit family { C n } \{C_{n}\} , it holds that ๐–ฃ๐–ค๐–ฏ๐–ณ๐–ง โก [ T โก ( n ) ] \displaystyle\mathsf{DEPTH}[T(n)] โŠ† ๐–ซ๐—ˆ๐—ˆ๐—‰ โก [ T โก ( n ) , size โก ( C n ) , 1 ] , \displaystyle\subseteq\mathsf{Loop}[T(n),\mathrm{size}(C_{n}),1], ๐–ฃ๐–ค๐–ฏ๐–ณ๐–ง โก [ T โก ( n ) ] \displaystyle\mathsf{DEPTH}[T(n)] โŠ† ๐–ข๐–ณ โก [ T โก ( n ) , size โก ( C n ) , 1 ] . \displaystyle\subseteq\mathsf{CT}[T(n),\mathrm{size}(C_{n}),1].

Boolean circuits serve as a formal model of parallel computations that run in polylogarithmic time using a polynomial number of processors ( Stockmeyer and Vishkin, 1984 ) .

###### Definition 3.11 .

For each k โˆˆ โ„• k\in\mathbb{N} , the classes ๐–ญ๐–ข k \mathsf{NC}^{k} , ๐– ๐–ข k \mathsf{AC}^{k} , and ๐–ณ๐–ข k \mathsf{TC}^{k} consist of languages decidable by non-uniform circuit families of size ๐—‰๐—ˆ๐—…๐—’ โก ( n ) \mathsf{poly}(n) and depth O โก ( log k โก n ) O(\log^{k}n) , using bounded-fanin Boolean gates, unbounded-fanin ๐– ๐–ญ๐–ฃ \mathsf{AND} / ๐–ฎ๐–ฑ \mathsf{OR} gates, and threshold gates, respectively.

We then characterize the exact computational power of latent thought in the parallel computation regime.

###### Theorem 3.12 .

For each k โˆˆ โ„• , k\in\mathbb{N}, it holds that ๐–ซ๐—ˆ๐—ˆ๐—‰ [ log k n , ๐—‰๐—ˆ๐—…๐—’ ( n ) , 1 (resp. log n ) ] \displaystyle\mathsf{Loop}[\log^{k}n,\,\mathsf{poly}(n),\,1\ \textup{(resp.\ }\log n)] = ๐–ข๐–ณ [ log k n , ๐—‰๐—ˆ๐—…๐—’ ( n ) , 1 (resp. log n ) ] \displaystyle=\mathsf{CT}[\log^{k}n,\,\mathsf{poly}(n),\,1\ \textup{(resp.\ }\log n)] = ๐– ๐–ข k โ€‹ ( resp. โ€‹ ๐–ณ๐–ข k ) . \displaystyle=\mathsf{AC}^{k}\ (\textup{resp.\ }\mathsf{TC}^{k}).

###### Proof sketch.

The inclusion from circuits to latent thought follows from Theorem 3.10 . For the converse inclusion, we build on the arguments of prior work ( Merrill and Sabharwal, 2023 ; Li et al., 2024 ) , which show that a fixed-depth Transformer block under finite precision is contained in ๐– ๐–ข 0 \mathsf{AC}^{0} (or ๐–ณ๐–ข 0 \mathsf{TC}^{0} under logarithmic precision). We extend their analysis to the looped setting, which can be unrolled into a ๐–ณ๐–ข k \mathsf{TC}^{k} circuit by composing a ๐–ณ๐–ข 0 \mathsf{TC}^{0} block for log k โก n \log^{k}n iterations. โˆŽ

Moreover, we establish an upper bound on the power of CoT in the parallel computation regime. This limitation arises from the inherently sequential nature of CoT.

###### Lemma 3.13 .

For each k โˆˆ โ„• , k\in\mathbb{N}, it holds that ๐–ข๐—ˆ๐–ณ โก [ log k โก n , ๐—‰๐—ˆ๐—…๐—’ โก ( n ) , log โก n ] โŠ† ๐–ณ๐–ข k โˆ’ 1 . \mathsf{CoT}[\log^{k}{n},\mathsf{poly}(n),\log{n}]\subseteq\mathsf{TC}^{k-1}.

###### Proof.

The total log k โก n \log^{k}n steps can be divided into log k โˆ’ 1 โก n \log^{k-1}n blocks, each consisting of log โก n \log n steps. Since ๐–ข๐—ˆ๐–ณ โก [ log โก n , ๐—‰๐—ˆ๐—…๐—’ โก ( n ) , log โก n ] โŠ† ๐–ณ๐–ข 0 \mathsf{CoT}[\log n,\mathsf{poly}(n),\log n]\subseteq\mathsf{TC}^{0} ( Li et al., 2024 ) , each block with the previous blockโ€™s outputs fed as inputs to the next block can be simulated in ๐–ณ๐–ข 0 \mathsf{TC}^{0} ; iterating this over log k โˆ’ 1 โก n \log^{k-1}n layers yields a circuit in ๐–ณ๐–ข k โˆ’ 1 \mathsf{TC}^{k-1} . โˆŽ

These results lead to a separation in expressive power under standard complexity assumptions, as illustrated in Figure 3 .

###### Theorem 3.14 .

For each k โˆˆ โ„• k\in\mathbb{N} , if ๐–ณ๐–ข k โˆ’ 1 โŠŠ ๐–ญ๐–ข k \mathsf{TC}^{k-1}\subsetneq\mathsf{NC}^{k} , then ๐–ข๐—ˆ๐–ณ โก [ log k โก n , ๐—‰๐—ˆ๐—…๐—’ โก ( n ) , log โก n ] \displaystyle\mathsf{CoT}[\log^{k}n,\mathsf{poly}(n),\log{n}] โŠŠ ๐–ซ๐—ˆ๐—ˆ๐—‰ โก [ log k โก n , ๐—‰๐—ˆ๐—…๐—’ โก ( n ) , 1 ] , \displaystyle\subsetneq\mathsf{Loop}[\log^{k}n,\mathsf{poly}(n),1], ๐–ข๐—ˆ๐–ณ โก [ log k โก n , ๐—‰๐—ˆ๐—…๐—’ โก ( n ) , log โก n ] \displaystyle\mathsf{CoT}[\log^{k}n,\mathsf{poly}(n),\log{n}] โŠŠ ๐–ข๐–ณ โก [ log k โก n , ๐—‰๐—ˆ๐—…๐—’ โก ( n ) , 1 ] . \displaystyle\subsetneq\mathsf{CT}[\log^{k}n,\mathsf{poly}(n),1].

###### Theorem 3.15 .

For each k โˆˆ โ„• k\in\mathbb{N} , if ๐–ณ๐–ข k โˆ’ 1 โŠŠ ๐–ณ๐–ข k \mathsf{TC}^{k-1}\subsetneq\mathsf{TC}^{k} , then ๐–ข๐—ˆ๐–ณ โก [ log k โก n , ๐—‰๐—ˆ๐—…๐—’ โก ( n ) , log โก n ] \displaystyle\mathsf{CoT}[\log^{k}n,\mathsf{poly}(n),\log n] โŠŠ ๐–ซ๐—ˆ๐—ˆ๐—‰ โก [ log k โก n , ๐—‰๐—ˆ๐—…๐—’ โก ( n ) , log โก n ] , \displaystyle\subsetneq\mathsf{Loop}[\log^{k}n,\mathsf{poly}(n),\log n], ๐–ข๐—ˆ๐–ณ โก [ log k โก n , ๐—‰๐—ˆ๐—…๐—’ โก ( n ) , log โก n ] \displaystyle\mathsf{CoT}[\log^{k}n,\mathsf{poly}(n),\log n] โŠŠ ๐–ข๐–ณ โก [ log k โก n , ๐—‰๐—ˆ๐—…๐—’ โก ( n ) , log โก n ] . \displaystyle\subsetneq\mathsf{CT}[\log^{k}n,\mathsf{poly}(n),\log n].

##### Remark.

The claims follow directly from Theorem 3.12 and Lemma 3.13 . The established separations of the complexity classes, as summarized in Fig. 3 , show that latent thought reasoning enables efficient parallel solutions more effectively than CoT, which is inherently sequential.

## 4 CoT Enables Approximate Counting

In the previous section, we showed that for decision problems, latent thought can yield more efficient solutions than CoT. This naturally raises the question of whether latent thought is universally more powerful than CoT. While prior work has shown that CoT can be simulated by looped Transformer models for deterministic decision problems under deterministic decoding ( Saunshi et al., 2025 ) , we found that this result does not directly extend to probabilistic settings with stochastic decoding. Accordingly, we shift our focus from efficiency in terms of the number of reasoning steps to expressive capability under polynomially many iterations.

### 4.1 Preliminaries

##### Approximate counting.

Formally, let ฮฃ \Sigma be a finite alphabet and let R โŠ† ฮฃ โˆ— ร— ฮฃ โˆ— R\subseteq\Sigma^{*}\times\Sigma^{*} be a relation. For an input x โˆˆ ฮฃ โˆ— x\in\Sigma^{*} , define R โก ( x ) := { y โˆˆ ฮฃ โˆ— โˆฃ ( x , y ) โˆˆ R } , R(x):=\{\,y\in\Sigma^{*}\mid(x,y)\in R\,\}, and the counting problem is to determine | R โก ( x ) | |R(x)| . A wide class of natural relations admits a recursive structure, which allows solutions to be constructed from smaller subproblems.

###### Definition 4.1 (Informal: Self-reducibility ( Schnorr, 1976 ) ) .

A relation R R is self-reducible if there exists a polynomial-time procedure that, given any input x x and prefix y 1 : k y_{1:k} (with respect to a fixed output order), produces a sub-instance ฯˆ ( x , y 1 : k ) \psi(x,y_{1:k}) such that every solution z z of ฯˆ ( x , y 1 : k ) \psi(x,y_{1:k}) extends y 1 : k y_{1:k} to a solution of R โก ( x ) R(x) (and conversely), i.e., R ( ฯˆ ( x , y 1 : k ) ) = { z โˆฃ concat ( y 1 : k , z ) โˆˆ R ( x ) } . R\bigl(\psi(x,y_{1:k})\bigr)=\{z\mid\ \mathrm{concat}(y_{1:k},z)\in R(x)\,\}.

While exact counting is intractable, there exist efficient randomized approximation algorithms ( Karp and Luby, 1983 ) .

###### Definition 4.2 (FPRAS) .

An algorithm is called a fully polynomial-time randomized approximation scheme (FPRAS) for a function f f if, for any ฮต > 0 \varepsilon>0 and ฮด > 0 \delta>0 , it outputs an estimate f ^ โ€‹ ( x ) \hat{f}(x) such that Pr [ ( 1 โˆ’ ฮต ) f ( x ) โ‰ค f ^ ( x ) โ‰ค ( 1 + ฮต ) f ( x ) ] โ‰ฅ 1 โˆ’ ฮด , \Pr\!\left[(1-\varepsilon)f(x)\leq\hat{f}(x)\leq(1+\varepsilon)f(x)\right]\geq 1-\delta, and runs in time polynomial in | x | |x| , 1 / ฮต 1/\varepsilon , and log โก ( 1 / ฮด ) \log(1/\delta) .

The class of counting problems that admit an FPRAS is denoted by ๐–ฅ๐–ฏ๐–ฑ๐– ๐–ฒ \mathsf{FPRAS} . Although randomized algorithms provide only probabilistic guarantees, they are often both more efficient and simpler than their deterministic counterparts, denoted by ๐–ฅ๐–ฏ๐–ณ๐– ๐–ฒ \mathsf{FPTAS} ( Definition C.11 ). For example, counting the number of satisfying assignments of a DNF formula admits an FPRAS based on Monte Carlo methods ( Karp et al., 1989 ) , whereas no FPTAS is known for this problem. Moreover, probabilistic analysis enables us to capture algorithmic behavior on typical instances arising in real-world applications ( Mitzenmacher and Upfal, 2017 ) .

##### Probabilistic models of computation.

In contrast to the deterministic models considered in the previous section, we now study probabilistic models that define a conditional distribution over output strings y = ( y 1 , โ€ฆ , y m ) โˆˆ ฮฃ โˆ— y=(y_{1},\ldots,y_{m})\in\Sigma^{*} . We consider autoregressive next-token prediction of the form p โก ( y โˆฃ x ) = โˆ i = 1 m p โก ( y i โˆฃ x , y < i ) , p(y\mid x)=\prod_{i=1}^{m}p(y_{i}\mid x,y_{<i}), where the model is allowed to perform additional reasoning steps before producing each output token y i y_{i} . This formulation was first used to formalize CoT for language modeling by Nowak et al. (2024) . We also allow stochastic decoding for latent reasoning at the token level: reasoning iterations are performed entirely in hidden space and no linguistic tokens are sampled except for the output token y i y_{i} , as illustrated in Fig. 4 . This definition is consistent with practical implementations ( Csordรกs et al., 2024 ; Bae et al., 2025 ) . Within this framework, we define complexity classes of probabilistic models, denoted by ๐—‰๐–ข๐—ˆ๐–ณ \mathsf{pCoT} , ๐—‰๐–ข๐–ณ \mathsf{pCT} , and ๐—‰๐–ซ๐—ˆ๐—ˆ๐—‰ \mathsf{pLoop} , respectively. Formal definitions are in Section C.1 .

### 4.2 Separation in Approximate Counting

We first analyze the expressivity of the token-level conditional prediction at each step, p โก ( y i โˆฃ x , y < i ) p(y_{i}\mid x,y_{<i}) , and show that CoT is strictly more expressive than latent thought in this setting. The key distinction is whether intermediate computation permits sampling. CoT explicitly samples intermediate reasoning tokens, inducing stochastic computation and enabling the emulation of randomized algorithms. In contrast, latent thought performs only deterministic transformations in latent space, resulting in deterministic computation.

###### Lemma 4.3 (Informal) .

Assume that ๐–ฅ๐–ฏ๐–ณ๐– ๐–ฒ โŠŠ ๐–ฅ๐–ฏ๐–ฑ๐– ๐–ฒ \mathsf{FPTAS}\subsetneq\mathsf{FPRAS} for self-reducible relations. There exists a self-reducible relation R R and an associated function f : ฮฃ โˆ— ร— ฮฃ โˆ— โ†’ โ„• f:\Sigma^{*}\times\Sigma^{*}\to\mathbb{N} defined by f โก ( x , y < i ) โ‰” | { z โˆˆ ฮฃ โˆ— : ( x , y < i โ€‹ z ) โˆˆ R } | f(x,y_{<i})\coloneqq|\{\,z\in\Sigma^{*}:(x,y_{<i}z)\in R\,\}| such that CoT with polynomially many steps admits an FPRAS for f f . Whereas, no latent thought with polynomially many iterations admits the same approximation guarantee.

###### Proof sketch.

For self-reducible relations, approximating the counting function f f on subproblems is polynomial-time inter-reducible with approximating | R โก ( x ) | |R(x)| ( Jerrum et al., 1986 ) . If latent thought with polynomially many iterations admitted an FPTAS for f f , then it would induce a deterministic FPTAS for | R โก ( x ) | |R(x)| , contradicting the assumption.โˆŽ

### 4.3 Separation in Approximate Sampling