A Formal Comparison Between Chain of Thought and Latent Thought — part 9/9
Cleaned-text code points [125071, 137425). Bibliography omitted here; source.md includes it.
The Edit Distance task requires computing the minimum number of edit operations needed to transform one string into another. The allowed operations are insertion, deletion, and replacement of a single character, and the objective is to predict the total edit distance given two input strings. To build the dataset, we follow ( Feng et al., 2023 ) . We first generate two strings over a randomly sampled alphabet. The first string has a fixed length, while the second string is produced in two possible ways: with probability 0.4 0.4 , it is drawn as a random string of nearly the same length (within ± 3 \pm 3 characters), and with probability 0.6 0.6 , it is derived from the first string by applying a given number of random edit operations. Each edit operation is chosen uniformly among deletion, replacement, and insertion. To avoid trivial cases, string pairs that are identical or whose lengths differ excessively are rejected and resampled. Finally, the shorter string is always placed first to maintain a consistent input format. An example instance in the format is shown below: s v d h s s e e … v e | s h d s s s s … e s e <sep> 20 Here, the two input strings are separated by the token “ | ”, “ <sep> ” marks the end of the inputs, and the final number “ 20 ” denotes the computed edit distance.
#### D.1.2 Training Configuration
##### Configuration of chain of thought
For CoT models, training is performed with supervision of step-by-step algorithms. (1) Word problem: for this task, the CoT algorithm proceeds by sequentially scanning the token sequence and producing at each prefix the evaluation result of the expression step by step. Thus, the overall length of the CoT sequence matches the input length. (2) Graph connectivity: Following Bavandpour et al. (2025) , the algorithm sequence is simply the trace of a breadth-first search (BFS) starting from the source s s . At each step, the model emits the incident edges of the currently expanded node in the order they are visited. The sequence terminates as soon as the target t t is discovered. To implement this algorithm, we maintain a list (“scratchpad”) initialized with a dummy marker and the source, ( N , s ) (\texttt{N},s) . We iterate through this list from left to right (i.e., queue order). Whenever the current node u u is expanded, we append to the end of the list all incident edges ( u , v ) (u,v) for neighbors v v , followed by a separator token ( u , N ) (u,\texttt{N}) . (3) Arithmetic expression evaluation: Following ( Feng et al., 2023 ) , the CoT takes the fully expanded expression and repeatedly evaluates one innermost subexpression, writing down the simplified expression at each step until only a single numeral remains. For example, 2 ∗ ( 0 + 1 ) / 2 → 2 ∗ 1 / 2 → 2 / 2 → 1 . 2*(0+1)/2\to 2*1/2\to 2/2\to 1. The overall CoT sequence has quadratic length. (4) Edit distance: Following ( Feng et al., 2023 ) , the CoT algorithm outputs the DP table entries in the same order they are computed, i.e., row by row from top-left to bottom-right (topological order). This yields a quadratic number of steps in the input length.
##### Optimization and model details.
We trained all models using the AdamW optimizer with a linear learning rate schedule. The initial learning rate was set to 1 × 10 − 4 1\times 10^{-4} with a weight decay of 0.01 0.01 , and a batch size of 256 256 . Training was continued until the training loss plateaued. For looped TFs, curriculum learning was applied to all tasks except edit distance: the input size was increased by 2 2 for the word problem task, and by 4 4 for the connectivity and arithmetic evaluation tasks. The model architecture was based on standard Transformers with an embedding dimension of 256 256 . We used 4 4 attention heads, and varied the number of Transformer layers depending on the task: two layers for word problems, a single layer for connectivity, and time-modulated ( Xu and Sato, 2025 ) model with a single layer for looped TF, to stabilize training, on both arithmetic evaluation and the edit distance task. For CoT, we use the same configuration of the Transformer block.
##### Uniform selection.
To estimate a lower bound on the number of reasoning steps required by CoT for each task, we first follow the procedure introduced in prior work ( Bavandpour et al., 2025 ) . Specifically, given a complete CoT trajectory consisting of T T intermediate reasoning steps, we construct shortened trajectories by uniformly selecting k k step indices from { 1 , … , T } \{1,\dots,T\} , i.e., by taking a uniformly spaced subsequence of the original trajectory. Only the selected intermediate steps are used, while the remaining steps are removed. We then evaluate task performance as a function of k k , as shown in Table 3 .
##### Stepwise internalization.
We adopt stepwise internalization proposed by ( Deng et al., 2024 ) , a curriculum-based training procedure that gradually removes CoT tokens and encourages the model to internalize intermediate reasoning within its hidden states. Starting from a model trained on full CoT trajectories, we progressively truncate intermediate reasoning tokens according to a predefined schedule and finetune the model at each stage. Specifically, when the CoT length is greater than 128 128 , we remove 16 16 tokens per stage until the remaining CoT length reaches 128 128 . We then continue removing 8 8 tokens per stage until the CoT length is reduced to 8 8 , training the model for 16 16 epochs at each stage. The results for each fundamental algorithmic reasoning task are shown in Fig. 10 .
### D.2 Approximate Counting and Approximate Sampling
#### D.2.1 Approximate Counting of DNF Formulas
To generate the dataset, we first construct a DNF formula F F by sampling m m clauses, each consisting of w w distinct literals over n n Boolean variables. Each literal is independently assigned to be either positive or negated. The formula is then serialized into a token sequence in which each clause is represented by its index together with variable–value pairs such as “ 2 = 2= + 1 +1 ” or “ 4 = 4= − 1 -1 ”. For looped TFs, we prepare 100,000 100{,}000 training samples and 1,000 1{,}000 test samples. For CoT models, we instead generate an online dataset with the following structure. To train the CoT models, we simulate a single trial of the randomized counting algorithm of Karp and Luby (1983) . The sequence concatenates the serialized formula, the sampled clause, the full assignment, and the verification outcome, separated by <sep> tokens and terminated by <eos> . CoT model is trained in an autoregressive manner, where prediction targets are defined by shifting the token sequence while masking out the formula description. We trained the models using the AdamW optimizer with a linear learning rate schedule. The initial learning rate was set to 1 × 10 − 4 1\times 10^{-4} , with a weight decay of 0.01 0.01 . We used a batch size of 256 256 (reduced to 32 32 for the 1000 1000 -loop setting) and trained for 10,000 10{,}000 iterations. For inference, we count the total number of iterations used for summing output tokens (steps) in CoT across trials, and the number of loop iterations in the looped TF.
#### D.2.2 Approximate Sampling of Graph Colorings
We consider the problem of approximately sampling a proper k k -coloring of a graph, also known as almost-uniform generation , a canonical randomized task closely related to # 𝖯 \#\mathsf{P} -hard counting problems. Given an undirected graph G = ( V , E ) G=(V,E) with n = | V | n=|V| vertices and maximum degree Δ \Delta , a proper k k -coloring is an assignment of colors from { 1 , … , k } \{1,\dots,k\} to vertices such that no adjacent vertices share the same color. Let Ω k ( G ) \Omega_{k}(G) denote the set of all proper k k -colorings of G G . We restrict attention to graphs of bounded degree and assume k ≥ 2 Δ + 1 . k\geq 2\Delta+1. Under this condition, classical results in approximate counting show that the number of proper k k -colorings admits a FPAUS ( Jerrum, 1995 ) . The approximation relies on Markov Chain Monte Carlo (MCMC) sampling using Glauber dynamics for graph colorings. Starting from an arbitrary proper coloring, the Markov chain repeatedly selects a vertex uniformly at random and proposes to recolor it with a randomly chosen color, accepting the update only if the resulting coloring remains proper. When k ≥ 2 Δ + 1 k\geq 2\Delta+1 , this Markov chain is known to be rapidly mixing, converging to the uniform distribution over Ω k ( G ) \Omega_{k}(G) in polynomial time. For our experiments, we generate an undirected Erdős–Rényi random graph, where each edge is included independently with probability p = 1.7 n , p=\frac{1.7}{n}, using a fixed random seed for reproducibility. For simplicity and ease of analysis, we focus on small graphs with n = 3 n=3 and set the number of colors to k = 5 k=5 .
Each sample is generated by running T T steps of Glauber dynamics on the space Ω k ( G ) \Omega_{k}(G) of proper k k -colorings. Starting from a greedy proper initialization, at each step we uniformly select a vertex and a color; the recoloring is accepted if and only if it preserves properness. The final state of the Markov chain is treated as an approximate sample from the uniform distribution over Ω k ( G ) \Omega_{k}(G) . In addition to the final coloring, we optionally record the entire sequence of proposals and accept/reject outcomes for CoT and use it as supervision, which is not included for latent thought. To train sequence models, we serialize the graph structure, the initial coloring, and either the MCMC history or the final coloring into a single token sequence. We evaluate the distribution of solutions generated by the model rather than only solution accuracy. Given an input x x , we draw N N independent samples from the model using ancestral decoding. Generation continues until an end-of-sequence (EOS) token is produced, and from each generated sequence we extract the final n n tokens immediately preceding the first EOS token, which encode a candidate solution. The resulting samples define an empirical distribution P ^ \hat{P} over generated solutions via normalized occurrence counts. For each instance, the task provides an exact enumeration 𝒴 \mathcal{Y} of all valid solutions. We define the reference distribution P true P_{\mathrm{true}} as the uniform distribution over this solution set, assigning probability 1 / | 𝒴 | 1/|\mathcal{Y}| to each y ∈ 𝒴 y\in\mathcal{Y} and zero otherwise. We quantify the discrepancy between the empirical distribution P ^ \hat{P} and the uniform reference distribution using the total variation distance 1 2 ∑ y ∈ 𝒴 ∪ 𝒴 ^ | P ^ ( y ) − P true ( y ) | . \frac{1}{2}\sum_{y\in\mathcal{Y}\cup\hat{\mathcal{Y}}}\left|\hat{P}(y)-P_{\mathrm{true}}(y)\right|. We trained the models using the AdamW optimizer with a linear learning rate schedule. The initial learning rate was set to 1 × 10 − 4 1\times 10^{-4} , with a weight decay of 0.01 0.01 . We used a batch size of 256 256 and trained for 5,000 5{,}000 iterations. For inference, we measure the average number of steps (loops) per generation. We generate N = 50,000 N=50{,}000 samples for CoT and N = 10,000 N=10{,}000 samples for looped TFs. The resulting histograms of CoT outputs over the target support are shown in Figure 11 .
## Instructions for reporting errors
We are continuing to improve HTML versions of papers, and your feedback helps enhance accessibility and mobile support. To report errors in the HTML that will help us improve conversion and rendering, choose any of the methods listed below:
Click the "Report Issue" ( ) button, located in the page header.
Tip: You can select the relevant text first, to include it in your report.
Our team has already identified the following issues . We appreciate your time reviewing and reporting rendering errors we may not have found yet. Your efforts will help us improve the HTML versions for all readers, because disability should not be a barrier to accessing research. Thank you for your continued support in championing open access for all.
Have a free development cycle? Help support accessibility at arXiv! Our collaborators at LaTeXML maintain a list of packages that need conversion , and welcome developer contributions .