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

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

Regarding complexity, each of the m m calls to the FPRAS for Ext R \mathrm{Ext}_{R} runs in time poly ⁡ ( n , ( r − 1 ) − 1 , log ⁡ ( m / δ ) ) \mathrm{poly}(n,(r-1)^{-1},\log(m/\delta)) . Substituting r − 1 = ε / 2 ​ m r-1=\varepsilon/2m , the runtime per call is poly ⁡ ( n , m / ε , log ⁡ ( m / δ ) ) \mathrm{poly}(n,m/\varepsilon,\log(m/\delta)) . Since m = p ⁡ ( n ) m=p(n) is a polynomial in n n , the total running time is poly ⁡ ( n , 1 / ε , log ⁡ ( 1 / δ ) ) \mathrm{poly}(n,1/\varepsilon,\log(1/\delta)) , which satisfies the requirements for an FPRAS. ∎

We have shown that approximate counting reduces to approximating the extension counting function . For a general relation R R , however, the connection between the extension counting function and the original counting problem for R R remains unclear. This gap is bridged by the notion of self-reducibility : for self-reducible relations, the extension counting function can be reduced back to the original counting problem for R R .

###### Definition C.15 ( Schnorr, 1976 ) .

A relation R ⊆ Σ ∗ × Σ ∗ R\subseteq\Sigma^{*}\times\Sigma^{*} is self-reducible if: 1. There exists a polynomial-time computable function g ∈ Σ ∗ → ℕ g\in\Sigma^{*}\to\mathbb{N} s.t., ( x , y ) ∈ R ⇒ | y | = g ⁡ ( x ) ; (x,y)\in R\Rightarrow|y|=g(x);

2. There exists a polynomial-time Turing machine that decides membership in R R .

3. There exist polynomial-time computable functions ψ ∈ Σ ∗ × Σ ∗ → Σ ∗ \psi\in\Sigma^{*}\times\Sigma^{*}\to\Sigma^{*} and σ ∈ Σ ∗ → ℕ \sigma\in\Sigma^{*}\to\mathbb{N} s.t. σ ⁡ ( x ) \displaystyle\sigma(x) = O ⁡ ( log ⁡ | x | ) , \displaystyle=O(\log|x|), (88) g ⁡ ( x ) > 0 \displaystyle g(x)>0 ⇒ σ ⁡ ( x ) > 0 ∀ x ∈ Σ ∗ , \displaystyle\Rightarrow\sigma(x)>0\quad\forall x\in\Sigma^{*}, (89) | ψ ⁡ ( x , w ) | \displaystyle|\psi(x,w)| ≤ | x | ∀ x , w ∈ Σ ∗ , \displaystyle\leq|x|\quad\forall x,w\in\Sigma^{*}, (90) and such that, for all x ∈ Σ ∗ x\in\Sigma^{*} , y = y 1 ​ … ​ y n ∈ Σ ∗ y=y_{1}\dots y_{n}\in\Sigma^{*} , ⟨ x , y 1 , … , y n ⟩ ∈ R ⇔ ⟨ ψ ⁡ ( x , y 1 ​ … ​ y σ ⁡ ( x ) ) , y σ ⁡ ( x ) + 1 , … , y n ⟩ ∈ R . \langle x,y_{1},\dots,y_{n}\rangle\in R\iff\langle\psi(x,y_{1}\dots y_{\sigma(x)}),y_{\sigma(x)+1},\dots,y_{n}\rangle\in R. (91)

For example, SAT is self-reducible: by fixing a prefix of variables and applying the reduction map ψ \psi , the problem is simplified to a smaller instance whose solutions extend the chosen prefix. Consider the Boolean formula F = ( x 1 ∨ x 2 ) ∧ ( ¬ x 1 ∨ x 3 ) ∧ ( ¬ x 2 ∨ ¬ x 3 ) , F=(x_{1}\vee x_{2})\ \wedge\ (\neg x_{1}\vee x_{3})\ \wedge\ (\neg x_{2}\vee\neg x_{3}), and suppose we fix the first variable to x 1 = 1 x_{1}=1 . The residual instance is obtained by applying ψ ⁡ ( F , ( 1 ) ) \psi(F,(1)) , which substitutes x 1 = 1 x_{1}=1 and simplifies the formula by deleting satisfied clauses and removing falsified literals: ψ ⁡ ( F , ( 1 ) ) = ( x 3 ) ∧ ( ¬ x 2 ∨ ¬ x 3 ) . \psi(F,(1))\;=\;(x_{3})\ \wedge\ (\neg x_{2}\vee\neg x_{3}). The unit clause ( x 3 ) (x_{3}) forces x 3 = 1 x_{3}=1 , which in turn simplifies ( ¬ x 2 ∨ ¬ x 3 ) (\neg x_{2}\vee\neg x_{3}) to ¬ x 2 \neg x_{2} , yielding x 2 = 0 x_{2}=0 . Hence the unique residual assignment is ( x 2 , x 3 ) = ( 0 , 1 ) (x_{2},x_{3})=(0,1) , and together with the prefix x 1 = 1 x_{1}=1 , we obtain the satisfying assignment ( x 1 , x 2 , x 3 ) = ( 1 , 0 , 1 ) . (x_{1},x_{2},x_{3})=(1,0,1).

For self-reducible relations, the extension counting function is no harder to approximate than the original counting problem.

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

Let R R be self-reducible. If there exists an FPRAS for N R N_{R} , then there exists an FPRAS for Ext R \mathrm{Ext}_{R} .

###### Proof.

By the definition of self-reducibility, the extension function Ext R ​ ( x , w ) \mathrm{Ext}_{R}(x,w) , which counts the number of strings y y such that ( x , w ​ y ) ∈ R (x,wy)\in R , can be mapped to the counting problem of a modified instance. Specifically, for any prefix w w where | w | ≤ σ ⁡ ( x ) |w|\leq\sigma(x) , there exists a polynomial-time computable mapping ψ \psi such that: Ext R ​ ( x , w ) = | { y ∈ Σ σ ⁡ ( x ) − | w | : ( x , w ​ y ) ∈ R } | = N R ​ ( ψ ⁡ ( x , w ) ) . \mathrm{Ext}_{R}(x,w)=|\{y\in\Sigma^{\sigma(x)-|w|}:(x,wy)\in R\}|=N_{R}(\psi(x,w)). (92) Since R R is self-reducible, the instance x w = ψ ⁡ ( x , w ) x_{w}=\psi(x,w) can be constructed in polynomial time relative to | x | |x| . By the hypothesis, there exists an FPRAS for N R N_{R} , which provides a randomized ( 1 ± ϵ ) (1\pm\epsilon) -approximation of N R ​ ( x w ) N_{R}(x_{w}) in time polynomial in | x w | |x_{w}| and 1 / ϵ 1/\epsilon . Consequently, this algorithm serves as an FPRAS for Ext R ​ ( x , w ) \mathrm{Ext}_{R}(x,w) , as it runs in polynomial time and satisfies the required approximation guarantees. ∎

### C.4 Proof for Theorem 4.3

###### Lemma C.17 (Formal Statement of Lemma 4.3 ) .

Assume that 𝖥𝖯𝖳𝖠𝖲 ⊊ 𝖥𝖯𝖱𝖠𝖲 \mathsf{FPTAS}\subsetneq\mathsf{FPRAS} for self-reducible relations. There exists a self-reducible relation R R and an associated function Ext R : Σ ∗ × Σ ∗ → ℕ \mathrm{Ext}_{R}:\Sigma^{*}\times\Sigma^{*}\to\mathbb{N} defined by Ext R ​ ( x , y < i ) ≔ | { z ∈ Σ ∗ : ( x , y < i ​ z ) ∈ R } | \mathrm{Ext}_{R}(x,y_{<i})\coloneqq|\{\,z\in\Sigma^{*}:(x,y_{<i}z)\in R\,\}| such that language models with CoT using polynomially many reasoning steps, which output a distribution for a given input ( x , y < i ) ∈ Σ n × Σ ∗ (x,y_{<i})\in\Sigma^{n}\times\Sigma^{*} by using a linear head for the last hidden state before emitting the output token, admit an FPRAS for Ext R \mathrm{Ext}_{R} , whereas no latent thought with polynomially many iterations admits the same approximation guarantee using a linear head for the last hidden state before emitting the output token.

###### Proof.

By Lemma C.6 , CoT can simulate any probabilistic Turing machine running in polynomial time; thus, it can implement an FPRAS for N R N_{R} . By Proposition C.16 , the existence of an FPRAS for N R N_{R} further implies the existence of an FPRAS for the extension function Ext R \mathrm{Ext}_{R} . On the other hand, latent thought consisting of a polynomial number of iterations can always be simulated by a deterministic polynomial-time Turing machine, provided that all state transitions in the latent computation are deterministic. Consequently, if such a latent thought process were to admit an FPRAS for Ext R \mathrm{Ext}_{R} , it would effectively yield a deterministic polynomial-time approximation scheme. By Proposition C.16 , the existence of such a scheme for Ext R \mathrm{Ext}_{R} would imply the existence of an FPTAS for N R N_{R} . However, under the standard complexity-theoretic assumption that 𝖥𝖯𝖳𝖠𝖲 ⊊ 𝖥𝖯𝖱𝖠𝖲 \mathsf{FPTAS}\subsetneq\mathsf{FPRAS} for self-reducible relations, there exists a self-reducible relation R R whose counting function admits an FPRAS but no FPTAS. This yields a contradiction. ∎

### C.5 Proof for Theorem 4.4

###### Definition C.18 (FPAUS) .

Uniform generation asks to sample an element y y uniformly at random from R ⁡ ( x ) R(x) . A fully polynomial almost uniform sampler (FPAUS) for R R is a randomized algorithm that, given an input x ∈ Σ ∗ x\in\Sigma^{*} and an accuracy parameter ε > 0 \varepsilon>0 , runs in time polynomial in | x | |x| and log ⁡ ( 1 / ε ) \log(1/\varepsilon) , and outputs a distribution q ( ⋅ ∣ x ) q(\cdot\mid x) such that ∥ q ( ⋅ ∣ x ) − U ( R ( x ) ) ∥ TV ≤ ε , \bigl\|q(\cdot\mid x)-U(R(x))\bigr\|_{\mathrm{TV}}\;\leq\;\varepsilon, where U ⁡ ( R ⁡ ( x ) ) U(R(x)) denotes the uniform distribution over the set R ⁡ ( x ) R(x) , and ∥ ⋅ ∥ TV \|\cdot\|_{\mathrm{TV}} denotes total variation distance.

For self-reducible relations, the following holds.

###### Theorem C.19 ( Jerrum et al., 1986 ) .

Let R R be a self-reducible relation. There exists an FPRAS for approximating | R ⁡ ( x ) | |R(x)| if and only if there exists an FPAUS for sampling uniformly from R ⁡ ( x ) R(x) .

###### Proof of Theorem 4.4 .

The target uniform conditional distribution is defined as follows: p ⁡ ( y i ∣ x , y < i ) := EXT R ⁡ ( x , y < i ​ y i ) ∑ u ∈ Σ EXT R ⁡ ( x , y < i ​ u ) ( y i ∈ Σ ) . p(y_{i}\mid x,y_{<i})\;:=\;\frac{\operatorname{EXT}_{R}(x,y_{<i}y_{i})}{\sum_{u\in\Sigma}\operatorname{EXT}_{R}(x,y_{<i}u)}\qquad(y_{i}\in\Sigma). (93) Assume an FPRAS 𝒜 ⁡ ( x , ε , δ ) \mathcal{A}(x,\varepsilon,\delta) exists for the self-reducible relation | R ⁡ ( x ) | |R(x)| . By Proposition C.16 , the existence of an FPRAS for | R ⁡ ( x ) | |R(x)| implies the existence of an FPRAS for the extension function EXT R \operatorname{EXT}_{R} . We construct a CoT that samples y ∈ R ⁡ ( x ) y\in R(x) by sequentially approximating these conditional probabilities. For each step i ∈ { 1 , … , m ⁡ ( n ) } i\in\{1,\dots,m(n)\} , the CoT computes ( 1 ± ε ) (1\pm\varepsilon) -accurate estimates EXT ^ R ​ ( x , y < i ​ u ) \widehat{\operatorname{EXT}}_{R}(x,y_{<i}u) for all u ∈ Σ u\in\Sigma using 𝒜 \mathcal{A} , and induces the following distribution: π ⁡ ( y i ∣ x , y < i ) := EXT ^ R ​ ( x , y < i ​ y i ) ∑ u ∈ Σ EXT ^ R ​ ( x , y < i ​ u ) . \pi(y_{i}\mid x,y_{<i})\;:=\;\frac{\widehat{\operatorname{EXT}}_{R}(x,y_{<i}y_{i})}{\sum_{u\in\Sigma}\widehat{\operatorname{EXT}}_{R}(x,y_{<i}u)}. (94) Conditioned on the event that all estimates in Equation 94 are ( 1 ± ε ) (1\pm\varepsilon) -accurate, the multiplicative error is bounded by: 1 − ε 1 + ε ≤ π ⁡ ( y i ∣ x , y < i ) p ⁡ ( y i ∣ x , y < i ) ≤ 1 + ε 1 − ε . \frac{1-\varepsilon}{1+\varepsilon}\leq\frac{\pi(y_{i}\mid x,y_{<i})}{p(y_{i}\mid x,y_{<i})}\leq\frac{1+\varepsilon}{1-\varepsilon}. (95) To ensure the cumulative approximation error remains within ( 1 ± ε ′ ) (1\pm\varepsilon^{\prime}) , we set the local precision to ε ≤ ε ′ 2 + ε ′ \varepsilon\leq\frac{\varepsilon^{\prime}}{2+\varepsilon^{\prime}} , which yields 1 + ε 1 − ε ≤ 1 + ε ′ \frac{1+\varepsilon}{1-\varepsilon}\leq 1+\varepsilon^{\prime} and 1 − ε 1 + ε ≥ 1 − ε ′ \frac{1-\varepsilon}{1+\varepsilon}\geq 1-\varepsilon^{\prime} . To ensure the failure probability is at most δ ′ \delta^{\prime} , we apply a union bound over the m ⁡ ( n ) m(n) generation steps and the | Σ | |\Sigma| calls per step. By setting the local confidence to δ ≤ δ ′ m ​ ( n ) ​ ( | Σ | + 1 ) \delta\leq\frac{\delta^{\prime}}{m(n)(|\Sigma|+1)} , the joint success event holds with probability at least 1 − δ ′ 1-\delta^{\prime} . Under this event, the CoT correctly simulates an FPRAS for p ⁡ ( y i ∣ x , y < i ) p(y_{i}\mid x,y_{<i}) in total time poly ​ ( n , 1 / ε ′ , log ⁡ ( 1 / δ ′ ) ) \text{poly}(n,1/\varepsilon^{\prime},\log(1/\delta^{\prime})) . Finally, since CoT can represent an FPRAS by Lemma 4.3 , it satisfies the requirements for the construction.

On the other hand, we show that latent thought cannot compute such an approximation. Suppose, for contradiction, that the model could compute the conditional distribution π ⁡ ( y i ∣ x , y < i ) \pi(y_{i}\mid x,y_{<i}) to within a ( 1 ± ε ) (1\pm\varepsilon) relative error in a single step. We define the estimator for the total count Z ⁡ ( x ) = | R ⁡ ( x ) | Z(x)=|R(x)| as: Z ^ ​ ( x ) ≔ ( ∏ i = 1 m ⁡ ( n ) π ⁡ ( y i ∣ x , y < i ) ) − 1 . \widehat{Z}(x)\;\coloneq\;\Biggl(\prod_{i=1}^{m(n)}\pi(y_{i}\mid x,y_{<i})\Biggr)^{-1}. (96) Since the true distribution satisfies p ⁡ ( y ∣ x ) = 1 / | R ⁡ ( x ) | = ∏ i p ⁡ ( y i ∣ x , y < i ) p(y\mid x)=1/|R(x)|=\prod_{i}p(y_{i}\mid x,y_{<i}) , the relative error of Z ^ ​ ( x ) \widehat{Z}(x) is governed by the product of local errors: ( 1 + ε ) − m ⁡ ( n ) ​ | R ⁡ ( x ) | ≤ Z ⁡ ( x ) ≤ ( 1 − ε ) − m ⁡ ( n ) ​ | R ⁡ ( x ) | , (1+\varepsilon)^{-m(n)}|R(x)|\leq Z(x)\leq(1-\varepsilon)^{-m(n)}|R(x)|, (97) By setting ε ≤ ε ′ 2 ​ m ​ ( n ) \varepsilon\leq\frac{\varepsilon^{\prime}}{2m(n)} , we apply Proposition C.14 and the properties of multiplicative error: ( 1 + ε ) − m ⁡ ( n ) ≥ 1 − m ⁡ ( n ) ​ ε ≥ 1 − ε ′ / 2 > 1 − ε ′ , (1+\varepsilon)^{-m(n)}\geq 1-m(n)\varepsilon\geq 1-\varepsilon^{\prime}/2>1-\varepsilon^{\prime}, (98) and for sufficiently small ε \varepsilon , ( 1 − ε ) − m ⁡ ( n ) ≤ 1 + 2 ​ m ​ ( n ) ​ ε ≤ 1 + ε ′ . (1-\varepsilon)^{-m(n)}\leq 1+2m(n)\varepsilon\leq 1+\varepsilon^{\prime}. (99) Substituting these into Equation 96 , we obtain: ( 1 − ε ′ ) ​ | R ⁡ ( x ) | ≤ Z ^ ​ ( x ) ≤ ( 1 + ε ′ ) ​ | R ⁡ ( x ) | . (1-\varepsilon^{\prime})|R(x)|\leq\widehat{Z}(x)\leq(1+\varepsilon^{\prime})|R(x)|. (100) This implies that if the model could compute π \pi accurately, Z ^ ​ ( x ) \widehat{Z}(x) would constitute an FPTAS for | R ⁡ ( x ) | |R(x)| . However, under the standard complexity-theoretic assumption that 𝖥𝖯𝖳𝖠𝖲 ⊊ 𝖥𝖯𝖱𝖠𝖲 \mathsf{FPTAS}\subsetneq\mathsf{FPRAS} for self-reducible relations, this yields a contradiction. ∎

## Appendix D Experimental Details

### D.1 Fundamental Algorithmic Reasoning Tasks

#### D.1.1 Task Settings

##### Word Problem

We define a sequence prediction task based on finite groups such as the symmetric group S 5 S_{5} . Given a sequence of group elements of length k k , the model is required to output the cumulative products obtained by scanning the sequence from left to right. Formally, for an input sequence ( g 1 , g 2 , … , g k ) (g_{1},g_{2},\ldots,g_{k}) , the target sequence is ( g 1 , g 1 g 2 , g 1 g 2 g 3 , … , g 1 g 2 ⋯ g k ) . (g_{1},\;g_{1}g_{2},\;g_{1}g_{2}g_{3},\;\ldots,\;g_{1}g_{2}\cdots g_{k}). We follow the setting of ( Merrill and Sabharwal, 2025b ) .

##### Connectivity

To ensure that the reachability labels are approximately balanced, we generate undirected graphs according to the Erdős–Rényi model ( Erdos and Renyi, 1959 ) G ⁡ ( n , p ) G(n,p) , where n n is the number of vertices and each possible edge is included independently with probability p p . In the supercritical regime ( p ​ n = c > 1 pn=c>1 ), a single “giant” connected component emerges, occupying a fraction s ∈ ( 0 , 1 ) s\in(0,1) of the vertices, which satisfies s = 1 − e − c ​ s . s=1-e^{-cs}. Consequently, the probability that two uniformly random vertices are both in this component—and hence mutually reachable—is approximately s 2 s^{2} . To target a reachability probability of 1 / 2 1/2 , we set s ≈ 1 2 ≈ 0.707 , c ≈ − ln ⁡ ( 1 − s ) s ≈ 1.74 , s\approx\sqrt{\tfrac{1}{2}}\approx 0.707,c\approx\tfrac{-\ln(1-s)}{s}\approx 1.74, and thus p = c n ≈ 1.7 n . p=\tfrac{c}{n}\approx\tfrac{1.7}{n}. In practice, for each graph of size n n we fix p = 1.7 / n p=1.7/n , which empirically yields Pr ⁡ [ reachable ] ≈ 50 % \Pr[\text{reachable}]\approx 50\% for n ∈ [ 50,100 ] n\in[50,100] . We follow the encoding scheme of Sanford et al. (2024a) . The input to the model is serialized as a flat token sequence consisting of three parts: v 0 v 1 ⋯ v n − 1 e 1 e 2 ⋯ e m s , t v_{0}\,v_{1}\,\cdots\,v_{n-1}\;e_{1}\,e_{2}\,\cdots\,e_{m}\;s,t where each vertex is denoted by a token v i v_{i} , each edge is represented as a pair “ u,v ” with u < v u<v , and the final token “ s,t ” specifies the source–target pair for the reachability query.

##### Arithmetic Expression Evaluation

Following ( Feng et al., 2023 ) , we generate expressions over integers modulo r r using the four operations + , − , × , ÷ {+,-,\times,\div} , where multiplication and division are defined via precomputed modular tables. To guarantee that each expression evaluates to a specific target value, we grow expressions backwards : starting from a sampled number, we iteratively replace it with a binary sub-expression that preserves its value under modular arithmetic. Different from ( Feng et al., 2023 ) , we fix the modulus to r = 3 r=3 , as our focus lies in evaluating the reasoning over expressions rather than exploring the properties of each modular arithmetic system.

##### Edit Distance