Technical Summary: A Formal Comparison Between Chain of Thought and Latent Thought

Problem Statement

Large Language Models (LLMs) have demonstrated enhanced reasoning capabilities through Chain of Thought (CoT), which elicits reasoning by explicitly generating intermediate tokens. Conversely, Latent Thought paradigms (such as Chain of Continuous Thought/Coconut and Looped Transformers) operate directly in the continuous hidden state space, iterating without generating discrete linguistic tokens. While both approaches utilize iterative computation to enhance expressivity, the fundamental theoretical separation between their capabilities remains underexplored. Specifically, it is unclear whether latent thought is universally more expressive than CoT, or if there exist specific computational regimes where one paradigm strictly outperforms the other.

Methodology

The authors employ a formal complexity-theoretic analysis to compare the expressive power of CoT and latent thought. The methodology involves:

1. Formal Definitions: The paper defines CoT, Coconut, and Looped Transformers as iterative applications of Transformer blocks. CoT generates tokens autoregressively, while latent thought models (Coconut and Looped TF) update hidden states iteratively, either by feeding hidden states back as embeddings (Coconut) or by re-computing the entire sequence (Looped TF).
2. Computational Modeling:
   • Decision Problems: Reasoning is formalized as the evaluation of Directed Acyclic Graphs (DAGs), representing Boolean circuits. The authors analyze how the number of reasoning steps (for CoT) or iterations (for latent thought) scales with the input size $n$ to solve these problems.
   • Complexity Classes: The study maps these models to standard complexity classes, specifically $TC_k$ (threshold circuits of polylogarithmic depth) and classes related to approximate counting ($FPRAS$ vs. $FPTAS$).
   • Probabilistic Settings: The analysis extends to probabilistic models where CoT utilizes stochastic decoding to sample intermediate tokens, whereas latent thought is analyzed under deterministic transformations in the latent space.
3. Theoretical Proofs: The authors construct proofs demonstrating upper and lower bounds for each paradigm. They utilize reductions to Boolean circuits and properties of self-reducible relations to establish separations.
4. Empirical Validation: The theoretical claims are validated on fundamental algorithmic reasoning tasks (Word Problems, Graph Connectivity, Arithmetic Evaluation, Edit Distance) and approximate counting/sampling tasks (DNF Counting, Graph Coloring).

Key Contributions

1. Latent Thought Enables Efficient Parallel Reasoning

The paper establishes that latent thought is strictly more efficient than CoT for problems requiring parallel computation.

• Parallelism: Latent thought models can simulate the evaluation of a DAG layer-by-layer. If a computation graph has depth $d$, a latent thought model can solve it in $O(d)$ iterations.
• Sequential Limitation of CoT: In contrast, CoT must simulate the DAG node-by-node due to its autoregressive nature, requiring $O(\text{size}(G))$ steps.
• Formal Separation: Under polylogarithmic iterations ($O(\log^k n)$), latent thought (Coconut and Looped TF) exactly captures the power of the complexity class $TC_k$. However, CoT with the same number of steps is strictly bounded within $TC_{k-1}$. This proves that latent thought admits more efficient parallel computation than inherently sequential CoT.

2. CoT Enables Approximate Counting via Stochasticity

The paper identifies a regime where CoT strictly outperforms latent thought: approximate counting and sampling.

• Stochastic Decoding: CoT explicitly samples intermediate reasoning tokens. This stochasticity allows CoT to emulate randomized algorithms, specifically Fully Polynomial-Time Randomized Approximation Schemes (FPRAS).
• Deterministic Limitation: Latent thought, operating deterministically in the continuous space (without token-level sampling during reasoning), is limited to deterministic approximation schemes (FPTAS).
• Formal Separation: Assuming $FPTAS \subsetneq FPRAS$ for self-reducible relations (a standard complexity assumption), the authors prove that CoT can approximate counting problems and sample from target distributions that latent thought cannot. Specifically, CoT can generate distributions that latent thought fails to approximate, providing the first formal separation in favor of CoT.

3. Empirical Validation

Experiments confirm the theoretical separations:

• Parallel Tasks: On tasks like Graph Connectivity and Arithmetic Evaluation, Looped Transformers achieve high accuracy with significantly fewer iterations (logarithmic in input size) compared to CoT, which requires a number of steps proportional to the problem size.
• Counting/Sampling Tasks: On DNF counting and graph coloring sampling, CoT demonstrates the ability to produce distributions closer to the uniform target distribution (lower Total Variation distance) compared to Looped Transformers, validating its superior capability in stochastic approximation.

Results

• Expressivity Separation: There is a strict separation in expressive power. Latent thought is superior for depth-driven, parallelizable problems (polylogarithmic regime), while CoT is superior for problems requiring stochastic approximation and counting.
• Iteration Efficiency: Latent thought achieves comparable performance to CoT on parallel tasks with $O(\log n)$ iterations, whereas CoT requires $O(n)$ or $O(\text{size}(G))$ steps.
• Sampling Capability: CoT can approximate distributions that are inaccessible to deterministic latent thought models, specifically in the context of self-reducible counting problems.

Significance

The paper provides a rigorous theoretical framework for choosing between reasoning paradigms based on the nature of the task:

• Latent Reasoning is more suitable for problems that can be solved efficiently via parallel computation (e.g., graph algorithms, arithmetic evaluation), offering significant gains in iteration efficiency.
• Chain of Thought remains more effective for complex problems requiring randomized approximation, counting, or sampling, where the stochasticity of token generation is a computational asset rather than a liability.

The authors conclude that neither paradigm is universally dominant; rather, their strengths are complementary, dictated by the trade-off between parallelizability and stochasticity. This work offers practical guidance for model design and task selection, suggesting that future architectures might benefit from hybrid approaches or task-specific selection of reasoning mechanisms.