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

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

For the upper bound 𝖫𝗈𝗈𝗉 [ log k n , 𝗉𝗈𝗅𝗒 ( n ) , 1 (resp. log n ) ] ⊆ 𝖠𝖢 k (resp. 𝖳𝖢 k ) , \mathsf{Loop}[\log^{k}n,\,\mathsf{poly}(n),\,1\ \textup{(resp.\ }\log n)]\subseteq\mathsf{AC}^{k}\ \textup{(resp.\ }\mathsf{TC}^{k}), we follow the argument of ( Li et al., 2024 ) . Their key observation is that a restricted form of automaton can model iterative computation under constant precision: the rounding operation preserves monotonicity, and constant precision yields counter-free, restricted state spaces, which are therefore computable by 𝖠𝖢 0 \mathsf{AC}^{0} circuits. In the case of polynomial precision, prefix summation can be simulated by 𝖳𝖢 0 \mathsf{TC}^{0} , which also allows the detection and correction of rounding in floating-point arithmetic.

###### Theorem B.9 ( Li et al., 2024 ) .

For s ⁡ ( n ) ∈ 𝗉𝗈𝗅𝗒 ⁡ ( n ) s(n)\in\mathsf{poly}(n) , sum s ⁡ ( n ) : ( 𝔽 s ⁡ ( n ) ) n → 𝔽 s ⁡ ( n ) \mathrm{sum}_{s(n)}:(\mathbb{F}_{s(n)})^{n}\to\mathbb{F}_{s(n)} is computable by 𝖳𝖢 0 \mathsf{TC}^{0} circuits, and by 𝖠𝖢 0 \mathsf{AC}^{0} circuits when s ⁡ ( n ) s(n) is constant.

It has also been shown that gates can be efficiently simulated by feedforward layers.

###### Lemma B.10 ( Li et al., 2024 ) .

Unbounded-fanin and , 𝖮𝖱 \and,\mathsf{OR} (resp. 𝑂𝑃𝐸𝑁 𝖬𝖠𝖩𝖮𝖱𝖨𝖳𝖸 ) : { 0 , 1 } n → { 0 , 1 } \mathsf{MAJORITY}):\{0,1\}^{n}\to\{0,1\} can be simulated by a two-layer feedforward ReLU network with constant (resp. log ⁡ n \log{n} ) bits of precision constant hidden dimension and additional n n constant inputs of value 1 1 .

###### Proof for Theorem 3.12 .

𝖫𝗈𝗈𝗉 [ log k n , 𝗉𝗈𝗅𝗒 ( n ) , 1 (resp. log n ) ] ⊆ 𝖠𝖢 k (resp. 𝖳𝖢 k ) : \mathsf{Loop}[\log^{k}n,\,\mathsf{poly}(n),\,1\ \textup{(resp.\ }\log n)]\subseteq\mathsf{AC}^{k}\ \textup{(resp.\ }\mathsf{TC}^{k}): In Transformers, constant-depth computation is defined by Summation with Iterative Rounding (see Definition B.3 ), which by Theorem B.9 can be simulated in 𝖠𝖢 0 \mathsf{AC}^{0} (resp. 𝖳𝖢 0 \mathsf{TC}^{0} ). A looped TF simply stacks these computations vertically through iteration, and thus the result follows.

𝖠𝖢 k (resp. 𝖳𝖢 k ) ⊆ 𝖫𝗈𝗈𝗉 [ log k n , 𝗉𝗈𝗅𝗒 ( n ) , 1 (resp. log n ) ] : \mathsf{AC}^{k}\ \textup{(resp.\ }\mathsf{TC}^{k})\subseteq\mathsf{Loop}[\log^{k}n,\,\mathsf{poly}(n),\,1\ \textup{(resp.\ }\log n)]: Since Boolean circuits are DAGs, the claim follows directly from Theorem 3.10 together with Lemma B.10 . ∎

## Appendix C Deferred Proofs for Section 4

### C.1 Definition for Models of Computation

We model a language model as a probabilistic process that, given an input and a generated prefix, produces either an internal reasoning state or an output token. This process induces a probability distribution over final outputs. We first formalize CoT under this setting. We focus on the saturated hardmax attention as in ( Merrill et al., 2022 ; Nowak et al., 2024 ) .

###### Definition C.1 (Language model with CoT) .

Let 𝒱 {\mathcal{V}} be a vocabulary. Given an input x ∈ 𝒱 ∗ x\in{\mathcal{V}}^{*} , a language model with CoT stochastically generates a sequence of output blocks of the form ( r 1 , e , y 1 , e ′ , r 2 , e , y 2 , e ′ , ⋯ r m , e , y m , e ′ ) , \Big(r_{1},\,e,\,y_{1},\,e^{\prime},\;r_{2},\,e,\,y_{2},\,e^{\prime},\;\cdots\;r_{m},\,e,\,y_{m},\,e^{\prime}\Big), (80) where each r i ∈ 𝒱 ∗ r_{i}\in{\mathcal{V}}^{*} represents an explicit reasoning trace, y i ∈ 𝒱 y_{i}\in{\mathcal{V}} is an output token, and e , e ′ ∈ 𝒱 e,e^{\prime}\in{\mathcal{V}} are special delimiter tokens. The final output is the string y 1 ⋯ y m y_{1}\cdots y_{m} . Generation proceeds autoregressively: at iteration i i , the model generates a reasoning segment r i r_{i} followed by an output token y i y_{i} , conditioned on the input x x , the previously generated outputs y < i y_{<i} , and prior reasoning segments r < i r_{<i} . We denote by p ⁡ ( y ∣ x ) p(y\mid x) the resulting distribution over final outputs.

Then we define the language models with latent thought reasoning: Coconut and looped TF.

###### Definition C.2 (Language model with Coconut) .

Let 𝒱 {\mathcal{V}} be a vocabulary. Given an input x ∈ 𝒱 ∗ x\in{\mathcal{V}}^{*} , a language model with Coconut generates a sequence of blocks ( r 1 , y 1 , r 2 , y 2 , … , r m , y m ) , \Big(r_{1},\,y_{1},\,r_{2},\,y_{2},\,\ldots,\,r_{m},\,y_{m}\Big), (81) where each r i ∈ 𝔽 d ∗ r_{i}\in{\mathbb{F}^{d}}^{*} represents an internal continuous reasoning state, and each y i ∈ 𝒱 y_{i}\in{\mathcal{V}} is an output token.

Generation proceeds autoregressively. At each iteration, the internal continuous reasoning state r i r_{i} is generated deterministically as a function of the input x x , the previously generated outputs y < i y_{<i} , and the prior internal states r < i r_{<i} , while the output token y i y_{i} is generated stochastically. The decision of when to emit an output token is determined internally by the model.

For looped TF models, the computation proceeds through internally repeated iterations before producing any output tokens. The number of iterations is determined by the model as a function of the input.

###### Definition C.3 (Language model with looped TF) .

Given an input x ∈ 𝒱 ∗ x\in{\mathcal{V}}^{*} , a looped TF produces an output sequence autoregressively. At each iteration i ∈ [ m ] i\in[m] , the model internally performs a number of repeated transformation steps before emitting an output token y i y_{i} , conditioned on the input x x and the previously generated outputs y < i y_{<i} . The number of internal loop iterations required to generate each output token is determined internally by the model as a function of the input x x and the generated prefix y < i y_{<i} .

We define complexity classes corresponding to language models under different reasoning paradigms. In contrast to the non-uniform models typically used in parallel computation analysis, we adopt a uniform setting analogous to Turing machines: a single model with a fixed set of parameters is applied to all input lengths, while the number of reasoning steps is allowed to grow as a function of the input size n n . Following the convention in ( Merrill and Sabharwal, 2024 ) , we allow O ⁡ ( log ⁡ n ) O(\log n) bits of numerical precision to represent positional embeddings and internal activations. Furthermore, we extend the output space beyond simple binary decisions. Specifically, the model’s output is not restricted to Σ k \Sigma^{k} , but can be an arbitrary finite binary string in Σ ∗ \Sigma^{*} . This extension enables the model to represent functions of the form f : Σ ∗ → ℝ f:\Sigma^{*}\to\mathbb{R} , thereby capturing counting, probabilistic modeling, and approximation tasks.

###### Definition C.4 (Complexity Classes 𝗉𝖢𝗈𝖳 \mathsf{pCoT} , 𝗉𝖢𝖳 \mathsf{pCT} , and 𝗉𝖫𝖮𝖮𝖯 \mathsf{pLOOP} ) .

Let 𝗉𝖢𝗈𝖳 ⁡ [ T ⁡ ( n ) ] \mathsf{pCoT}[T(n)] , 𝗉𝖢𝖳 ⁡ [ T ⁡ ( n ) ] \mathsf{pCT}[T(n)] , and 𝗉𝖫𝖮𝖮𝖯 ⁡ [ T ⁡ ( n ) ] \mathsf{pLOOP}[T(n)] denote the classes of probabilistic computations that define an output distribution p : Σ ∗ × Σ ∗ → [ 0 , 1 ] p:\Sigma^{*}\times\Sigma^{*}\to[0,1] . A function f f belongs to such a class if there exists a language model ℳ \mathcal{M} , employing CoT, Coconut, or looped TF, respectively, such that for any input x ∈ Σ n x\in\Sigma^{n} , the model induces the distribution p ⁡ ( x , ⋅ ) p(x,\cdot) within O ⁡ ( T ⁡ ( n ) ) O(T(n)) steps using O ⁡ ( log ⁡ n ) O(\log n) bits of numerical precision.

### C.2 Lemma: Universality of Chain of Thought

###### Definition C.5 .

A probabilistic Turing machine M = ( Q , Σ , Γ , q 0 , q 1 , δ 1 , δ 2 ) M=(Q,\Sigma,\Gamma,q_{0},q_{1},\delta_{1},\delta_{2}) is defined as: • Q Q is a finite set of states,

• Σ \Sigma is the input/output alphabet,

• Γ \Gamma is the tape alphabet, with Σ ⊆ Γ \Sigma\subseteq\Gamma and a distinguished blank symbol ⊔ ∈ Γ \sqcup\in\Gamma ,

• q 0 ∈ Q q_{0}\in Q denotes the initial state, and q 1 ∈ Q q_{1}\in Q denotes the final state,

• δ 1 , δ 2 : Q × Γ → Q × Γ × ( Σ ∪ { ε } ) × { L , S , R } \delta_{1},\delta_{2}:Q\times\Gamma\to Q\times\Gamma\times(\Sigma\cup\{\varepsilon\})\times\{L,S,R\} are two transition functions.

At each step, M M chooses uniformly at random between δ 1 \delta_{1} and δ 2 \delta_{2} . Each transition δ i ​ ( q , a ) = ( q ′ , b , σ , D ) \delta_{i}(q,a)=(q^{\prime},b,\sigma,D) is interpreted as: writing b ∈ Γ b\in\Gamma on the work tape, writing σ ∈ Σ \sigma\in\Sigma on the output tape, where ε \varepsilon means that nothing is written, and moving the tape head in direction D ∈ { L , S , R } D\in\{L,S,R\} , where L L = left, R R = right, and S S = stay. The output of M M is defined to be the string remaining on the output tape when the machine halts.

Prior work has shown that probabilistic CoT can simulate any such PTM, thereby demonstrating its universality.

###### Lemma C.6 ( Nowak et al., 2024 ) .

Let M M be a PTM with input and output alphabet Σ \Sigma , and running time bounded by T ⁡ ( n ) T(n) on inputs of length n n . Then there exists a log-precision CoT model with stochastic decoding, denoted 𝖢𝗈𝖳 M \mathsf{CoT}_{M} , such that the induced output distribution of 𝖢𝗈𝖳 M \mathsf{CoT}_{M} coincides exactly with that of M M . Formally, for every input string x ∈ Σ ∗ x\in\Sigma^{*} and output string y ∈ Σ ∗ y\in\Sigma^{*} , Pr [ 𝖢𝗈𝖳 M ( x ) = y ] = Pr [ M ( x ) = y ] . \Pr\bigl[\mathsf{CoT}_{M}(x)=y\bigr]\;=\;\Pr\bigl[M(x)=y\bigr]. (82) Moreover, the number of reasoning steps of 𝖢𝗈𝖳 M \mathsf{CoT}_{M} is bounded by 𝗉𝗈𝗅𝗒 ⁡ ( | x | ) \mathsf{poly}(|x|) .

### C.3 Self-Reducibility and Complexity of Approximate Counting

Here, we provide the definitions of relation and associated counting problems.

###### Definition C.7 (Relation) .

A relation over an alphabet Σ \Sigma is a subset R ⊆ Σ ∗ × Σ ∗ . R\subseteq\Sigma^{*}\times\Sigma^{*}. For an input x ∈ Σ ∗ x\in\Sigma^{*} , we denote R ⁡ ( x ) := { y ∈ Σ ∗ : ( x , y ) ∈ R } . R(x):=\{\,y\in\Sigma^{*}:(x,y)\in R\,\}.

###### Definition C.8 (Counting) .

Given a relation R R , the associated counting function is defined as N R : Σ ∗ → ℕ , N R ​ ( x ) := | R ⁡ ( x ) | . N_{R}:\Sigma^{*}\to\mathbb{N},\qquad N_{R}(x):=|R(x)|.

###### Definition C.9 ( p p -relation) .

A relation R ⊆ Σ ∗ × Σ ∗ R\subseteq\Sigma^{*}\times\Sigma^{*} is called a p p -relation if • the membership ( x , y ) ∈ R (x,y)\in R can be decided in time polynomial in | x | |x| , and

• there exists a polynomial p p such that for all ( x , y ) ∈ R (x,y)\in R , we have | y | ≤ p ⁡ ( | x | ) |y|\leq p(|x|) .

###### Definition C.10 .

The extension counting function associated with a relation R ⊆ Σ ∗ × Σ ∗ R\subseteq\Sigma^{*}\times\Sigma^{*} is EXT R : Σ ∗ × Σ ∗ → ℕ , EXT R ⁡ ( x , w ) := | { z ∈ Σ ∗ : ( x , w ​ z ) ∈ R } | . \operatorname{EXT}_{R}:\Sigma^{*}\times\Sigma^{*}\to\mathbb{N},\qquad\operatorname{EXT}_{R}(x,w):=\bigl|\{\,z\in\Sigma^{*}:(x,wz)\in R\,\}\bigr|.

The complexity class # ​ 𝖯 \#\mathsf{P} consists of counting problems associated with p p -relations ( Valiant, 1979 ) . Then, we provide definitions of schemes for approximate counting. In the remainder of this paper, we say that an algorithm produces an output approximating f ⁡ ( x ) f(x) within ratio 1 + ε 1+\varepsilon if its output f ^ ​ ( x ) \hat{f}(x) satisfies ( 1 − ε ) ​ f ​ ( x ) ≤ f ^ ​ ( x ) ≤ ( 1 + ε ) ​ f ​ ( x ) , (1-\varepsilon)f(x)\leq\hat{f}(x)\leq(1+\varepsilon)f(x),

###### Definition C.11 (FPTAS) .

An algorithm is called a fully polynomial-time approximation scheme (FPTAS) for a function f f if, for any input x x and any ε > 0 \varepsilon>0 , it produces an output approximating f ⁡ ( x ) f(x) within ratio 1 + ε 1+\varepsilon , and runs in time polynomial in | x | |x| and 1 / ε 1/\varepsilon .

###### Definition C.12 (FPRAS) .

An algorithm is a fully polynomial-time randomized approximation scheme (FPRAS) for a function f f if, for any input x x and any ε > 0 \varepsilon>0 and δ > 0 \delta>0 , it produces an output approximating f ⁡ ( x ) f(x) within ratio 1 + ε 1+\varepsilon with probability at least 1 − δ 1-\delta , and runs in time polynomial in | x | |x| , 1 / ε 1/\varepsilon , and log ⁡ ( 1 / δ ) \log(1/\delta) .

The following proposition formalizes the relationship between approximate counting and the extension counting function.

###### Proposition C.13 ( Jerrum et al., 1986 ) .

Let R R be a p p -relation and let x ∈ Σ n x\in\Sigma^{n} . Let m = p ⁡ ( n ) m=p(n) and define r = 1 + ε 2 ​ m r=1+\frac{\varepsilon}{2m} . If there exists a FPRAS that approximates Ext R ​ ( x , w ) \mathrm{Ext}_{R}(x,w) within ratio r r for all prefixes w w with probability at least 1 − δ / m 1-\delta/m , then there exists an FPRAS that approximates N R ​ ( x ) N_{R}(x) within ratio 1 + ε 1+\varepsilon with probability at least 1 − δ 1-\delta .

This reduction transforms the global counting problem into a sequence of local estimation steps.

###### Proposition C.14 .

For any 0 < ε ≤ 1 0<\varepsilon\leq 1 and any integer m ≥ 1 m\geq 1 , it holds that ( 1 + ε 2 ​ m ) m < 1 + ε . \left(1+\frac{\varepsilon}{2m}\right)^{m}<1+\varepsilon. (83)

###### Proof.

We use the standard inequality 1 + x ≤ e x 1+x\leq e^{x} , which holds for all x ∈ ℝ x\in\mathbb{R} . Substituting x = ε 2 ​ m x=\frac{\varepsilon}{2m} , we have: ( 1 + ε 2 ​ m ) m ≤ ( exp ⁡ ( ε 2 ​ m ) ) m = e ε / 2 . \left(1+\frac{\varepsilon}{2m}\right)^{m}\leq\left(\exp\left(\frac{\varepsilon}{2m}\right)\right)^{m}=e^{\varepsilon/2}. (84) For 0 < ε ≤ 1 0<\varepsilon\leq 1 , we show that e ε / 2 < 1 + ε e^{\varepsilon/2}<1+\varepsilon . Let f ⁡ ( ε ) = 1 + ε − e ε / 2 f(\varepsilon)=1+\varepsilon-e^{\varepsilon/2} . Then f ⁡ ( 0 ) = 0 f(0)=0 and f ′ ​ ( ε ) = 1 − 1 2 ​ e ε / 2 f^{\prime}(\varepsilon)=1-\frac{1}{2}e^{\varepsilon/2} . Since e ε / 2 ≤ e 1 / 2 < 2 e^{\varepsilon/2}\leq e^{1/2}<2 for all ε ∈ [ 0 , 1 ] \varepsilon\in[0,1] , it follows that f ′ ​ ( ε ) > 0 f^{\prime}(\varepsilon)>0 . Thus, f f is strictly increasing on [ 0 , 1 ] [0,1] , implying f ⁡ ( ε ) > f ⁡ ( 0 ) = 0 f(\varepsilon)>f(0)=0 , or equivalently e ε / 2 < 1 + ε e^{\varepsilon/2}<1+\varepsilon . ∎

###### Proof for Proposition C.13 .

Let x ∈ Σ n x\in\Sigma^{n} and m = p ⁡ ( n ) m=p(n) . We express N R ​ ( x ) N_{R}(x) as a product of m m ratios. Let w = y 1 ​ y 2 ​ … ​ y m w=y_{1}y_{2}\dots y_{m} be a witness, and let w ( i ) w^{(i)} denote its prefix of length i i . We can write: N R ​ ( x ) = Ext R ​ ( x , λ ) = ∏ i = 1 m Ext R ​ ( x , w ( i − 1 ) ) Ext R ​ ( x , w ( i ) ) ⋅ Ext R ​ ( x , w ( m ) ) . N_{R}(x)=\mathrm{Ext}_{R}(x,\lambda)=\prod_{i=1}^{m}\frac{\mathrm{Ext}_{R}(x,w^{(i-1)})}{\mathrm{Ext}_{R}(x,w^{(i)})}\cdot\mathrm{Ext}_{R}(x,w^{(m)}). (85) In the standard self-reducibility framework, we estimate each ratio ρ i = Ext R ​ ( x , w ( i − 1 ) ) / Ext R ​ ( x , w ( i ) ) \rho_{i}=\mathrm{Ext}_{R}(x,w^{(i-1)})/\mathrm{Ext}_{R}(x,w^{(i)}) using the assumed approximation scheme. Let A i A_{i} be the estimator for the i i -th ratio such that: ℙ [ 1 r ≤ A i ρ i ≤ r ] ≥ 1 − δ m . \mathbb{P}\left[\frac{1}{r}\leq\frac{A_{i}}{\rho_{i}}\leq r\right]\geq 1-\frac{\delta}{m}. (86) By the union bound, the probability that at least one of these m m estimations fails to stay within the ratio r r is at most m ⋅ ( δ / m ) = δ m\cdot(\delta/m)=\delta . Therefore, with probability at least 1 − δ 1-\delta , all m m estimations are successful. Under this condition, the final estimate N ^ = ∏ i = 1 m A i \hat{N}=\prod_{i=1}^{m}A_{i} satisfies: 1 r m ≤ N ^ N R ​ ( x ) ≤ r m . \frac{1}{r^{m}}\leq\frac{\hat{N}}{N_{R}(x)}\leq r^{m}. (87) From Proposition C.14 , we have r m = ( 1 + ε 2 ​ m ) m < 1 + ε r^{m}=(1+\frac{\varepsilon}{2m})^{m}<1+\varepsilon . Furthermore, for 0 < ε ≤ 1 0<\varepsilon\leq 1 , it holds that 1 / r m > ( 1 + ε ) − 1 ≥ 1 − ε 1/r^{m}>(1+\varepsilon)^{-1}\geq 1-\varepsilon , ensuring a relative error of at most ε \varepsilon .