Reasoning by Superposition: A Theoretical Perspective on Chain of Continuous Thought
Authors: Hanlin Zhu
Shibo Hao
Zhiting Hu
Jiantao Jiao
Stuart Russell
Yuandong Tian
Venue: NeurIPS 2025 poster ()
Keywords: reasoning
chain of continuous thought
superposition
transformer
Primary area: deep_learning
TL;DR: We study the mechanism of chain of continuous thought on the graph reachability problem, and show it can reason by maintaining a superposition of multiple search traces both theoretically and empirically.

Abstract: Large Language Models (LLMs) have demonstrated remarkable performance in many applications, including challenging reasoning problems via chain-of-thought (CoT) techniques that generate ``thinking tokens'' before answering the questions. While existing theoretical works demonstrate that CoT with discrete tokens boosts the capability of LLMs, recent work on continuous CoT lacks a theoretical understanding of why it outperforms discrete counterparts in various reasoning tasks, such as directed graph reachability, a fundamental graph reasoning problem that includes many practical domain applications as special cases. In this paper, we prove that a two-layer transformer with $D$ steps of continuous CoT can solve the directed graph reachability problem, where $D$ is the diameter of the graph, while the best known result of constant-depth transformers with discrete CoT requires $O(n^2)$ decoding steps where $n$ is the number of vertices ($D<n$). 
In our construction, each continuous thought vector is a superposition state that encodes multiple search frontiers simultaneously (i.e., parallel breadth-first search (BFS)), while discrete CoT must choose a single path sampled from the superposition state, which leads to a sequential search that requires many more steps and may be trapped in local solutions.
We also performed extensive experiments to verify that our theoretical construction aligns well with the empirical solution obtained via training dynamics. Notably, encoding of multiple search frontiers as a superposition state automatically emerges in training continuous CoT, without explicit supervision to guide the model to explore multiple paths simultaneously.

Reasoning by Superposition: A Theoretical Perspective on Chain of Continuous Thought
Hanlin Zhu"
Shibo Hao* UCSD sóh
Zhiting Hu UCSD zhh019@ucsd. edu
UC Berkeley
hanl memlinnh@@berkkeeyccoo edu
Jiantao Jiao
Stuart Russell UC Berkeley
Yuandong Tian Meta Al
UC Berkeley j jiantaoberrkele..co
russell6cs. berkeley. edu
yuandongdmeta.cco com
Abstract
Large Language Models (LLMs) have demonstrated remarkable performance in many applications, including challenging reasoning problems via chain-of- thought (CoT) techniques that generate "thinking tokens" before answering the questions. While existing theoretical works demonstrate that CoT with discrete tokens boosts the capability of LLMs, recent work on continuous CoT lacks a theoretical understanding of why it outperforms discrete counterparts in various reasoning tasks, such as directed graph reachability, fundamental graph reasoning problem that includes many practical domain applications as special cases. In this paper, we prove that two-layer transformer with D steps of continuous CoT can solve the directed graph reachability problem, where 1) the diameter of the graph, while the best known result of constant-depth transformers with discrete CoT requires ((n?) decoding steps where n the number of vertices (D < n). our construction, each continuous thought vector is superposition state that encodes multiple search frontiers simultancously (i.e., parallel breadth-first search (BFS)), while discrete CoT must choose a single path sampled from the superposition state, which leads to a sequential search that requires many more steps and may be trapped in local solutions. We also performed extensive experiments verify that theoretical construction aligns well with the empirical solution obtained via training dynamics. Notably, encoding of multiple search frontiers superposition state automatically emerges in training continuous COT,, without explicit supervision to guide the model explore multiple paths simultaneously. Our code is available com foom/Ber666/ree rew.onins-onnnneeeee bussppprossiitio htt.a///////66////eeaaaiigggggg
Introductions
Large language models (LLMs) have shown strong performance in many reasoning tasks, especially
when empowered with chain-of-thouge (CoT) (Wei et al.) [022] (e.g.. hard problems like AIME and math proving). However, they also struggle with tasks that require more sophisticated reasoning capability [Kambhampati] 2024). e.g., reasoning and planning problems of increasing scales [Zheng
al. 2024
Xie et al. 2024]. even with CoT /Valmeekam et al. 2024 Zhou al. 2025
remains an open problem how to expand existing discrete CoT to solve more complex reasoning problems. Recently, Hao al. (2024) proposes COCONUT (chain-of--ommiinnuu--hh
that uses
Equal contributions.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

continuous latent thoughts for reasoning, showing empirical performance boost on synthetic tasks such as directed graph reachability (i.e., given a specification of a directed graph and one starting node, determine which candidate destination node is reachable), as well as strong performance on real-world math reasoning benchmarks such as GSM8K [Cobbe et al. (02T]. Interestingly, COCONUT shows preliminary results that continuous latent thought may store multiple candidate search frontiers simultancously, before the final answer is reached. This is in sharp contrast with discrete CoT, in which each discrete thought token has to be sampled (or "realized")) before feeding into LLMs in an autoregressive manner. However, the expressive power and the mechanism of continuous thought still remain elusive and lack a deep understanding.
In this work, we explore the mechanism of COCONUT for the problem of graph reachability, i.e.. whether there exists a path from given start and end nodes in directed graph. The problem setting is general (ee et al. 2024 (Hao et al.] 2024 /Zhou et al. 2025] and includes many important theoretical problems (e.g., Turing machine halting problem) and practical use cases (e.g., knowledge graph). Given this setting, we proved that a two-layer transformer with D steps of continuous thought can solve graph reachability for graphs of vertices, where D < is the graph's diameter (longest path length between two nodes). In contrast, for graph reachability, the best existing result on constant-depth transformers with discrete CoT requires (n²²) steps [Merrill and Sabharwal 2023a
Intuitively, in our construction, each latent thought vector is superposition of multiple valid search traces, and thus can perform implicit parallel search on the graph in each autoregressive step. The continuous thoughts can be regarded as "superposition states" in quantum mechanics [Böhm 2013). storing multiple search frontiers simultaneously, and thus enabling efficient breadth- first search (BFS). In contrast, discrete thought tokens can be viewed as "'ollapsed states" from superpositions. This forces the model to choose a branch deterministically. yielding either an incorrect greedy search or a depth-first style search with backtracking, which requires more computation. Unlike previous theoretical work that constructs positional encodings specifically for given problem even for given input length, our construction works for widely-used positional encodings in practice, such as sinusoidal positional encoding |Vaswani et al. 2017 and rotary position embedding (Su et al. 2024).
Moreover, we show that our theoretical construction can be achieved in gradient- based training. Specifically, a two-layer transformer with continuous CoT outperforms 12-layer one with discrete CoT on graph reachability. An inspection of attention patterns and their underlying representation demonstrates that the continuous thought indeed encodes multiple plausible search frontiers in parallel in superposition states. Notably, such superpositional representation automatically emerges from training only with the optimal path of graph reachability, without strong supervision that aligns the latent thought vectors with other plausible search traces.
1.1 Related works
LLM reasoning in text and latent spaces. L.M'' reasoning capability can be significantly boosted by chain-of-thouuht (CoT) (Wei et al. [202]], which allows L.MSs to explicitly output intermediate thoughts in text space before predicting the final answer. CoT includes prompt-only methods [Khot
ct al.
2022 Zhou et al. 2022 and training with samples containing intermediate thoughts (Yue et al.
2023
Yu et al. 2023 Wang et al. 2023b Shao et al. 2024]. Besides text-based CoT. many previous
works also study LLM reasoning in the latent space GGoyal et al., 2023 Wang et al. 2023c Pfau
(et al. 2024 Su et al. 2025] where the intermediate thoughts do not necessarily correspond to textual tokens. In particular, Hao et al. 2024 proposed to train LLMs to reason in a continuous latent space, which outperforms discrete CoTl on graph reasoning tasks, especially for graphs with high branching factors. Based on empirical case studies in Hao al. (2024), continuous thoughts are hypothesized to encode multiple plausible search frontiers simul Itneousl In this work, we formally study the mechanism and theoretically show that transformers equipped with continuous thoughts benefit from superposition states during reasoning.
Expressivity of transformers. There a long line of work studying the expressivity of transform-
ers (Yun et al. 2019 Bhattamishra et al., 2020a b) Pérez et al. 202 Likhosherstov et al.] 2021
Yao et al.) 2021 Edelman et al. 2022 Akyürek et al., 2022, Merrill and Sabharwal 2023b]. A
more recent line of work shows CoT can improve the expressivity of transformers [Liu et al. 2022
Feng et al. 2023) Merrill and Sabharwal 2023a Li et al. 2024]. For example, [Luu et al. 2022
studies low-depth transformer expressivity for semi-automata, of which the setting corresponds to

---

one CoT step. Feng et al. [2023] shows that constant-depth transformers with CoT can solve certain P-complete problems. Li et al. 2024] further provides constructions of constant-depth transformer for each problem in P/ ppoly with Co'I. Merrill and Sabharwal [2023a] studies the expressivity with different lengths of CoT,, showing that logarithmic steps of CoT in input length can expand the upper bound of constant-depth transformer expressivity from TC" to L, while a linear number of steps can further expand the upper bound to NC'mcoleee While these expressivity results mainly focus on discrete COT, theoretical studies on continuous CoT (Hao et al., (024) are rare, which our work is focused on. Gozeten et al. [2025] studies the expressivity of one-layer transformers with continuous CoT on the minimum non negative sum problem, demonstrating the superposition mechanism in the arithmetic domain, which complements our results on the graph reachability problem. While their construction requires an exponentially large embedding dimension, our theoretical construction requires only a linear embedding dimension the graph size. Moreover, unlike many previous works that construct problem-specific (or even length-specific) positional encodings, our construction applies to practical positional encodings, such as sinusoidal Vasswani et al. 2017 and RoPE (Su et al. 2024
Reasoning as graph problems. Graph problems are essential to understand LLM reasoning
capability since many reasoning problems can be abstracted computational graphs (Ye al.
2024
Zhou et al. 2025) where relational data fed into transformers can be modeled as edges [Wang
al.
2024a b Guo et al. 2025]. Many previous works have shown that pretrained LLMs can deal reasoning tasks in graphs. but may still have difficulties with more complicated tasks [Wang
with
al.
2023a Guo et al. 2023 Fatemi al., 2023 Sanford et al., 2024 Luo et al., 2024 Dai et al.
2024
Cohen et al. 2025] Other works study how transformers solve classic and fundamental graph
problems, such as graph reachability [Merrill and Sabharwal 2023a 2025]. shortest path [Cohen et al.,
2025). etc. For example, Cohen et al. [2025] shows that a two-layer transformer can leverage spectral decomposition of the line graph to predict the shortest path on small-scale undirected graphs. |Merrill and Sabharwal [2025] shows that log-depth transformer can solve directed graph reachability, which constant-depth transformers can not solve. For a constant-depth transformer, Merrill and Sabharwal [2023a] shows directed graph reachability can be solved with (n²) CoT steps where is the number of vertices, while it remains unclear whether a smaller number of discrete CoT steps can solve the task. On the contrary, our work shows that a two-layer transformer can solve graph reachability for D-diameter graph with D continuous thought steps.
2 Preliminaries
Basic notations. For any integer N > O, we use [N] to denote the set 21. N.. ). For any finite set X, let [ denote the cardinality of X. Let E be the set of real numbers. We use {-) to denote the indicator function. Without further clarification, we use lower-case bold letters (e.g., æ. 0) and upper-case bold letters (e.g., W. U) denote vectors and matrices, respectively. In particular, use Ia to denote a x d identity matrix, use 0mxn (or 0m) to denote an m x n zeto matrix (or an m- dimensional zero vector), and use e, to denote one-hot vector of which the i-th entry is one and other entries are all zero, where the dimension of e; can be inferred from the context. We also use || llo and ||. ||2 represent Too norm and La norm of vectors, respectively. For vectors E Rm and v E R. let v uv T _m denote their outer product. Also, for vectors u, v E Rdd let (u, v) u denote their inner product. For any vector x = (I1, (I1,...,, xra) ) E Rd, we define the softmax function SoftMax: Ed + gd as SoftMax(z); exp(a,) j= exp(z;)). and the layer normalization operator LayerNorm(z)) x/ / Moreover, for a sequence of vectors (æ1, .2,..., 2x)) E Rdxt, we abuse the notation Naree = (LayerNorm(z:)). LayerrNoooo.)) E ddx
Tokens and embeddings. For a fixed positive integer V > 0. let Voc = [V] denote a vocabulary of size V. For each token Voc, there is associated token embedding u, E Rd where d 0 is the embedding dimension. Assume d = 3dTE + dpE. We refer to the first dTE entries of a d-dimensional vector as its content, the subsequent dTE entries as its first buffer, the following drE entries as its second buffer, and the final dPE entries as its effective positional encoding. Formally, for a vector = 22,,,,....,. . T.)
(xI,,... .., I.dre) buffer (x) (Idje+1,... (2drre bufferz(x)) (I2d Izdre) ) and pos(x) (I3d zTa T. Let u content(u.)) E dRE for any E Voc. Assume for each u. only the first dTE entries are
Rd, we define content(x))
3

---

non-zero. Furthermore, let U = ر ü...... üv] E R and we assume that U = Iv, i...
the token embeddings are orthonormal.
Algorithm Transformer (TF)
Input: Parameters = (OPE, (1 1-1.Ht-1, (OML))))) 1=-)), input embeddings = (h (h),... h:) 11=0,1=0
1: h t- h; + PosEncodegsr (i), E (t)
> adding positional encoding
2: for = to L - do
3: (1++0.5) x- h()) + Σn= -H Attn edtn (h())
D self attention
4: h(+11) t LayerNorm (MLP
(h (h(+to.)))
>> MLP and layer normalization
5: end for Output: Embedding of the last layer at the last position h,4).
Transformer architectures. An L-layer autoregressive transformer receives a sequence of input embeddings h hig (h,, h2,...,, he) Rdxt and outputs (Fo Rd where TFa(-) is defined in Algorithm Let Wo Vxd be the decoding matrix. A traditional decoder will sample the next token Ur4+1 SoftMax W Wo TFa(h) and append its token embedding in position to autoregressively generate subsequent outputs. When using the chain
t ++ 1. i.e. h 1 of continuous thought (Hao et al., 2024). one skips the sampling step and directly appends the output of the transformer as the imput embedding of the next position, i.c., h1+1 = (h) The parameter & contains positional encodings OPg, L attention layers where each layer contains Hi heads (0(.)) 1-1.H1-1 11=0,h=0 and L MLP layers { 1--1 The definitions attention heads and MLPs are in Algorithm
Algorithm Causal Self-Attention (Attn) and (position-wise wise) Multilayer Perceptron (MLP)
Input: Attn (Q, K, V. O), OMLP ((W,)
{o:(.)
Lmp-1), "), input h (h1,-. ..... h2)
1: q. f Qh:, k; t Kh;
V: K Vi+-Vh, Vh,,
Vi
> compute queries, keys, values
2: for 1 to do
3: 8; 4- SoftMax (qi, ki)...... (q: k;)),
hatto + O 1E 1 SiyVj
4: 1MMPP W Lmp LeaF
W201 (W,h;)... )
5: end for Output: Attn (h) (hAttt hattt)) or MLP PULP (h) (hMLP
h MLP)
Positional encodings. Given an input sequence (h,...., hr) ). for each position i E [T], there is corresponding positional encoding p; = PosEncode (t) E Rd For each pt, we assume that only the last dpE entries non-zero and thus call dpE the effective positional encoding dimension. For notation convenience, we denote h, content(h.) Rh P; = pos(p:) dee for any E [7]. We use the widely used sinusoidal positional encoding for P: = (p.......,PP ) as defined below.
Definition 1 (Positional Encoding). Let dpE be even. We use positional encoding generated by sinusoidal functions Vaswani al. (2017]. Specifically, for any position 2 and any index j E /2) we have
P122-1 cos(i M 2j//dE),, PL.2 sin(i M 22/ddE),
where M is a large constant integer, e.g., M 10 as chosen in Vaswani et al. 2017]
Remark 1. We also discuss theoretical construction with RoPE Su et al. 2024 (Appendix B.6
3 Problem Formulations
Graph reachability. Let G (V, E) be directed graph, where V = {1i, ....... Un) is the set of vertices and & = (e1, (e1,62,-- e.. , Pm in the vocabulary, and thus we use i to represent both vertex and its corresponding token. Let
is the set of edges. Each vertex v; corresponds to token

---

Amxx > 0 denote the maximum possible number of vertices of a graph. Note that mama |ocl Each edge e, & is a tuple, where e, = (s,, t,) source node to the target node t.. Given a graph (i.e., all the edges of the graph), two candidate destination nodes ej and 62, and a root node r, the task identify which the two nodes can be reached by r. Note that we guarantee one and only one of and C2 is reachable by which we denote by C
V denotes there is directed edge from the
directed edge
special edge token
question token
reasoning token
<
$2
22
<E>
Sm
fm
<B>
<Q>
<R>
start token
source node
target node
candidate nodes
node
Figure 1:
Prompt format of the graph reachability problem.
Input structures. The prompt structure is illustrated in Figure 1 The prompt starts with the BOS (beginning of sentence) token 
. The subsequent 3m tokens represent m edges, where each edge represented by the source node 8,, target node t; and special edge token <e> that marks the end of an edge. Then there is a special question token <Q> followed by two candidate destination nodes C1 and Cg. Finally, there a special reasoning token <R> followed by a root node r. See Table 2 for the full list of token notations. Let to 3m + 6 be the length of the prompt, and let (h1 h2. ht,)) be the input embedding sequence where h, is the token embedding of the i-th token in the prompt.
Chain of continuous thought. We allow transformers to utilize continuous thoughts. Concretely,
for e = 1,2, ..., the transformer autoregressively generates ht = TFo -hoote-)) 1). For notation convenience, we use [t.] = ho to represent the continuous thought of step for 2 O. and thus [t,]] ur. To request the transformer to make the final prediction after steps of thoughts, one simply appends special answer token <A> at the end of the sequence, i.e., sets hy Uea> where T= + 1, and gets the prediction sampled from SoftMax Wo (b(rr)) or using greedy de-
coding arg max (F We denote TFe,c.Wo (h(to)) arg max,eVoc Wo (h(r))) as the output token of greedy decoding after generating C steps of continuous thoughts.
Position index. To present the position of each token or continuous thought in the sequence in a clear way. we use Idx(1) (v) to represent the position of token in the input sequence (c.g.. ldx(
) 1, Idx(s;) = 1, (dx(<QQ>=
3i + 1 to represent the position of the i-th <e> token in the prompt, and use Idx( [t,]) to + to represent the position of the continuous thought of step i. See Table (3 for the complete list of position indices.
3m + 2), use Idx (<e><<>>>))
In the following sections, we demonstrate that the chain of continuous thought can efficiently solve the graph reachability problem both theoretically (Section 4 and empirically (Section 5)
Theoretical Results
In this section, we theoretically prove that two-layer transformer with continuous thought can efficiently solve the graph reachability problem. We first introduce a basic building block, the attention chooser, in transformer constructions in Section 4.1 Then present the key result that continuous thought maintains a superposition state of multiple search traces simultancously in
Section 4
We show main theorem in Section 4.3 and make further discussion in Section 4.4
4.1 Attention chooser
We use the attention chooser as a building block in our construction, which will choose the appropriate positions to attend conditioned on the token in the current position. This allows to use the same parameter constructions for various input lengths. The proof is deferred to Appendix B.T
Lemma (Attention chooser, informal version of Lemma Under sinusoidal positional encoding as defined in Definition 7 for any token <α> Voc and relative position é > 0, there exists
5

---

construction of Kf Q
E R (22d)))xd, such that for any input sequence h that satisfying mild
assumptions (see Lemma 3
in Appendix B.2). it holds that for any position i E [T), it will pay almost
all attention to position
E) if h, Usz and pay most attention to position one otherwise.
Proof sketch. We define vector U Evevock foo) Uy TT the superposition of all token
embeddings in the vocabulary except for <x>. By the property of sinusoidal positional encoding,
there exists a rotation matrix R(4) in Lemma 4 in Appendix B.5 s.t. Pi+t R Then we can construct the query and key matrices as
P4+
vi 2 1.
Odpexdr [PI & Uss
0 Odexx2dr
LdrE Odee drs
Oddexxdde O x3dTE
n TII
Q
K
O ODe x 2dTE
where 1, 17 0 and thus the query and key vectors can be calculated as
P q: Q(; + P.) ((uG h.) k; - K(h: + +P:) =
[
(1)(0pp 17p;
npi+t
npp:
Now for any 1 S S S T, we have (q, kj) 17 (p:: Pi+e) + E(ico h.) Pj) Fix any i [T]. By the property of sinusoidal positional encoding, (p1, Pr)) is maximized when i' = i as in Lemma in Appendix [B.5 h, ulz, holds that (ūez, h,) 0 and thus (q,, ky) is determined by (p., P)-e), which is maximized at j L. If h, 전 Ucee, one can show that (ūeş> h.) 2 1 and thus (q: kj) is largely determined by (P1, Рạ) when & is large, and thus maximized at j = 1.
4.2 Continuous thought maintains superposition states
Recall that h hta denotes the input sequence defined in Section 3 We define V. the set of vertices that are reachable from within c steps. Below, we present our key lemma.
Lemma (Continuous thought maintains superposition states). We autoregressively generate [tcr1] TFo [t,].... [ta])for any 2 0. There exists construction of such that
[t = -hote
1
Σ
u
(1)
ViVal
wEV.
ie., the e-th continuous thought is the normalized superposition of all vertices that can be reached from T within e steps.
Lemma 2 precisely characterizes that each continuous thought is superposition of all reachable vertices. We provide proof sketch below and defer the complete proof to Appendix B.2
Proof sketch. We prove by induction. For O, by definition, Vo {x) and [t,] u, viv. Even, ug. Now we briefly show how to construct the two-layer transformer such that under
the induction assumption that holds for 0, O,....c, C, we can obtain that | also holds for c c 1.
First layer attention. The first attention layer contains five attention heads, and each head is an attention chooser as constructed in Lemma [ Let h4 (<x>, E) denote the k-th attention head that attends to position (i- E) when the i-th token is <x> and attends to the first token otherwise. We construct hg = <e>, 2), Yr (<e>, 1), h2 (<R>, 2), hıg = (<R>, 1). h4 = (<A>, 1). which is illustrated in Figure 2 For each head, the value matrix will read the value in the content space, and the output matrix will copy the value state to designated space.
Second layer attention. In the second layer, we only need one attention head. Note that after the first layer, for the i-th edge token <e>, we have buffer, (hidx(<e>.s) ūg and buffer, (hidx(<a>.)) By the induction assumption, the current thought [t.] is superposition of all vertices in V.. We construct the query and key matrices such that [t.] pays large attention to the i-th edge token <e> if s; E V. (roughly speaking, we can view qidx( [t.]) [t,], kidx(<e>,i) = Us, and their inner product is positive iff E V.). and add the target node t; stored in buffer 2 back to the current thought (see Figure 3). This exactly a one-step expansion of the currently explored vertices V. and thus the continuous thought at the next step (c + 1) will correspond to Ve+1.
ū..-

---

ombedding space
capy
buffer
[tc]
buffer
Fr
content
2
[c
positional
Psi-1
Pa
Pat+1
Pam+s
Pancta
Pames
Pr-1
Pr
encoding
attend
Figure 2: Illustration of the embedding space and first layer attention mechanism.
small attention s, @ V.
embedding space
large
if VV
Superposition of all nodes that can be reached within steps
buffer
$j
add large attention
<$>
<B>
<
[tc]]
[te]
V DEV
Figure 3: Illustration of second layer attention mechanism for thought generation. We omit positional encoding space since they are not used in the second layer.
MIP as filter for signals. Note that after the attention layer, the weight of each node in the current thought is not uniform, and the current thought might contain noise tokens since the normalized attention score to each position is non-zero. We use the MLP layer to filter out the noise token and adjust the weight of each node in Vo+1- Informally, for superposition state h Engvae Uy
want to eliminate noise tokens v where X, < E, and want to equalize the weights of other tokens.
By setting the first layer parameter Wi -u),.... uv nonlinearity (x) 1 far 8} and second layer as W2 WT. we have W2(o(W,h)) = Evevoe 1( 2 u, where W1 rotates
the basis {u,) } to the standard basis {e.}. (-) serves as coordinate-wist filter, and Wa rotates the basis back. After layer normalization, we can obtain that (T) also holds for c +
4.3 Measuring the superposition state prediction
Since the continuous thought [t,] is a superposition of all vertices Ve, as long as C;- can be reached by within C steps, the superposition state [t,] will contain c At the final prediction step, the answer token <A> will "measure" the superposition state [tc] using с₁ and and predict the token with the larger signal in [t,] as the output (see Figure iin Appendix B.2 for a pictorial illustration). We formalize our result in the following theorem, and defer the proof to Appendix B.4
Theorem 1 (Chain of continuous thought solves graph reachability). Fix Tmax > O. Assume the length of the input sequence (including the continuous thoughts and the special answer token <A>) does not exceed T max There exists a construction of a two-layer transformer parameters 0 and the readout matrix W E ||Voo (where d O(Vocc)) that are independent of graphs, such that for any directed graph candidate destination nodes c2 for any C exceeds the diameter of the graph, it holds that
E) with at most mmax nodes (Nmax |Voc)), root node r, two
TFe.c (hppi) Ci.
4.4 Discussions
Role of buffer spaces. The buffer spaces are subspaces of the embedding to store useful information. For clarity, our construction separates the "content" and the "buffer" spaces into different dimensions. In practice, they can be jointly projected into more compact and lower-dimensional space. For example, we can construct
Σe R (() e i where the column space of each (()) E ddd forms subspace. Different subspaces be (almost) orthogonal, and for each subspace, the column vectors of R can also be almost orthonormal.
7

---

Weights of different nodes in the superposition. In our construction, each superposition state maintains nodes with uniform weights. In practice, the weights of different nodes can vary due to factors such as training signals or the model's internal heuristic reach the final answer [Cohen et al., 2025]. Section 5 we show that in practice, the training signal could bias the superposition states towards the frontier nodes that can be reached with exactly i steps and the optimal nodes that can lead to the destination node.
which nodes are more likely to
Experiments
In this section, conduct extensive experiments to validate our theoretical results that COCONUT outperforms discrete CoT even with many fewer layers (.22) which is indeed due to superpo- sition states encoded in continuous thoughts during reasoning (Section 5.3
5.1 Training Setup
Model. We adopt a GPT-2 style decoder with two transformer layers, d 1 We train from scratch using Adam W (51 (3.9 0095, weight-decay 10-2) and a constant learning rate of 10
1.0
Coconut
Co
No CoT
Dataset. We construct a subset of ProsQA (Hao et al., 2024), with
Accuracy
questions whose solutions require 3-4 reasoning hops. Each node in the graph is injected as a dedicated token into the vocabulary. The split statistics are summarised in Table 4
0.8
0.7
Method. Following Hao et al. 2024], we adopt a multi-stage training strategy with the supervision from thahn-sf data. Stage teaches the model to use i continuous thoughts before pre- dicting the i-th node the given chain of thought as the next token. If the index of the training stage is larger than the CoT solution length the model is trained to output the final prediction after continuous thoughts and <A> We train the model for 25 epochs at each stage, and the whole training lasts 300 epochs in total. At each stage, we mix the data from the previous stage randomly with 0.1 probability, which helps improve performance in our early experiments.
0.5
Figure 4: The overall accuracy of COCONUT, COT, COT (12 lay- ers, Thhaads 12) and No CoT.
5.2 Overall Results
Extending the findings of Hao et al. (2024), we further show that a 2-layer transformer trained from scratch can effectively solve ProsQA when using COCONUT. As shown in Figure 4, COCONUT achieves near- sear-perfect accuracy, while both CoT and No CoT baselines solve only about 75% of the tasks (random guessing = 50%). Even with larger model of 12 layers and Theads 12, marked with in the figure, CoT improves 83% accuracy but still cannot solve the tasks reliably.
5.3 Visualising Latent Reasoning
We inspect both the attention pattern and the representation of the continuous thought learned by the model to validate our theoretical construction.
Layer 1 atfention. According our theoretical construction, the most important function of LAYER 1 attention heads is to copy the source and target node tokens of edge onto the corresponding edge token (e). Figure shows a representative attention map, confirming that the model has instantiated this copying mechanism in practice.
Layer 2 attention. LAYER responsible for node expansion: each continuous thought attends to all outgoing edges from nodes that are currently reachable. To quantify this behavior, we compute, when generating i-th continuous thought, the aggregated attention score received by each edge token triplet (s, <e>) across all heads. 4 kinds of edges exist: (1) Reachable: their source node is in the

---

reachable set at step i; (2) Not Reachable: source node not in the reachable set; (3) Frontier: a subset of reachable edges whose souree node on the current search frontier. i... exactly steps away from the root node; (4) Optimal: a subset of frontier edges that lead to the optimal reasoning chain.
Table 1 reports group-wise means and standard deviations averaged on the test set. The model sharply concentrates its attention on Reachable edges, as predicted by our theoretical construc- tion. Interestingly, there is an additional bias to- ward the Frontier subset. One possibility is that the training signal encourages the model pre- dict frontier node at each step, coupled with the decaying effects for previously explored nodes. We also find that the optimal edges receive more attention scores, likely due the supervision of multi-stage training from the CoT solution.
15
<cp
Input (Quenyl
16
Asturdia weight
cea
Representation of continuous thoughts. To verify that the continuous thought serves su- perposition states for the search, we compute the inner product between the continuous thought at step i, [t,], and each node embedding u, Similar to edge classification above, we classify nodes into Reachable, Not Reachable, Frontier, and Optimal. Figure g (top) plots the distri- bution segregated by the reasoning step i. As predicted, nodes within hops exhibit markedly higher similarity scores than distant nodes. Moreover, Frontier nodes are noticeably closer to [t,] than other reachable nodes, illustrating that the superposition emphasizes the candidate expansion fronts. Besides, the Optimal nodes are even closer to [tt]], also likely due to the training data always presenting the optimal path.
cep
Imput Thlenes (Key)
A representative example of Layer I attention map: the edge token <e> (y-axis) places nearly all its attention mass on its source and target nodes (z--axis), in line with the theorctical construction.
Figure 5:
Collectively, these analyses confirm that the intended superpositional search exists in trained models: Layer establishes the query context, Layer expands the frontier, and the latent vectors encode soft, parallel representation of reachable state sets, realizing the theoretical construction in Section We also show in Appendix C.2 random seeds.
that this search pattern is consistent across multiple experiments with
Continuous thought
thought
Continuzus thought
Continoous thought
eechhable
Opoimal 16.01
Opt mat H4.55
Optimal 10
Optimel 13 35
822
600
500
300
620
400
300
200
420
250
100
1440
Npr leachib (4:44)
Net leachabl (4:44)
600
Not karchabl (044)
300
Not kaachable (QA4)
1230
Optimal
hucllo 22)
hoddly t01
Needee 22
82
Cooru
400
200
630
420
300
420
200
100
220
230
225
2.5
3.0
-.0
0.2
5.0
Figure 6: The histogram inner product between the i-th continuous thoughts and the node embeddings. The mean value for each group is shown in the legend. Note that Frontier is a subset of Reachable nodes, and Optimal is a subset of Frontier nodes.
5.4 Exploration Priority

---

An interesting fact revealed by the visualizations Section [s3 is that the model allocates disproportion- ate attention to optimal edges and nodes, reminiscent of prioritized search strategy. One hypothesis is that this behavior is an artifact of our multi-stage curriculum, which explicitly guides the model the CoT solution at every step. To un- derstand the effect of this multi-stage guidance, we introduce an alternative supervision method CoCoNUT-BFS: at stage i, the supervision token is drawn uniformly at random from the fron- tier nodes exactly hops from the root, rather than the i-th node in the CoT' solution. All other hyperparameters are unchanged.
Table Layer 2 attention scores to different edge groups at step (mean + standard deviation).
Step
Step
Step
Step 4
Not Reachable
0.04
0.03
0,08
0,12
Reachable
2.12 +1.07
0.71 40.92
0.38 40.72
0.29 40.60
-Frontier -Optimal
2.12
1.00
0.67 10.87
0.61 10 .5
2.54:11.3
1112
1.67 21.20
2.23 #1:35
Our experiment results indicate that COCONUT-BFS also achieves near-perfect accuracy ProsQA, matching the original COCONUT. Figure compares the inner product distributions of the latent thoughts for both models. Remarkably, the two supervision methods converge to similar exploration strategies, even though there is no explicit guidance towards optimal nodes for COCONUT -FF.. Conversely, the original COCONUT, although trained exclusively optimal nodes during intermediate stages, still assigns elevated weight to non-optimal frontier nodes compared to other non conffrot nodes, implicitly performing breadth-firs expansion before honing in the solution. We leave explaining this behavior from the perspective of training dynamics as future work.
6 Conclusions
In this paper, we study how the focusing on the graph reachability problem. We provided a theoretical construction two-layer transformer that can efficiently solve graph reachability for an n-vertex D-diameter directed graph by D steps of continuous thoughts, while the best existing result on constant-depth transformers with discrete CoT requires On?²) steps. Our construction reveals that the superposition states that encode multiple search traces simultaneously are the key to the strong reasoning capability of COCONUT, and we conducted thorough experiments to validate that our theoretical construction matches the solutions obtained by training dynamics. Several interesting future directions include: (1) Deriving lower bound on the number of discrete CoT steps in the graph reachability problem to show strict separation of expressivity between CoT and COCONUT; (2) Theoretical understanding of the emergence of exploration behavior with only deterministic search trace demonstration via training dynamics; (3) Advantages of reasoning in a continuous space in more general settings.
boosts LLM's reasoning capability by
Acknowledgements
This work was partially supported by a gift from Open Philanthropy to the Center for Human- Compatible AI (CHAI) UC Berkeley and by NSF Grants IIS-1901222 and CCF-2211209,
References
Ekin Akyürek, Dale Schuurmans, Jacob Andreas, Tengyu Ma, and Denny Zhou. What learning algo- rithm is in-context learning? investigations with linear models. arXiv preprint mmXiv:2211.15611
2022.
Satwik Bhattamishra, Kabir Ahuja, and Navin Goyal. On the ability and limitations of transformers to recognize formal languages. arXiv preprint arXiv:2009. 1264, 2020a.
Satwik Bhattamishra, Arkil Patel, and Navin Goyal. On the computational power of transformers and its implications in sequence modeling. arXiv preprint arXivv2006.092880 2020b.
Arno Böhm. Quantum mechanics: foundations and applications. Springer Science Business Media, 2013.
10

---

Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, al. Training verifiers solve math word problems. arXiv preprini | / 10. 14168, 2021.
Andrew Cohen, Andrey Gromov, Kaiyu Yang, and Yuandong Tian. Spectral journey: How transform- ers predict the shortest path. arXiv preprint arXiv:2502.08794 2025.
Xinnan Dai, Haohao Qu, Yifen Shen, Bohang Zhang, Qihao Wen, Wenqi Fan, Dongsheng Li, Jiliaagg Tang, and Caihua Shan. How do large language models understand graph patterns? a benchmark for graph pattern comprchension. arXiv preprint arXiv:2410.05228. 2024.
Benjamin L Edelman, Surbhi Goel, Sham Kakade, and Cyril Zhang. Inductive biases and variable creation in self-attention mechanisms. In International Conference on Machine Learning, pages 5793-5831. PMLR, 2022.
Bahare Fatemi, Jonathan Halcrow, and Bryan Perozzi. Talk like a graph: Encoding graphs for large language models. arXiv preprint arXiv:2310.04560, 2023.
Guhao Feng, Bohang Zhang, Yuntian Gu, Haotian Ye, Di He, and Liwei Wang. Towards revealing the mystery behind chain of thought: theoretical perspective. Advances in Neural Information Processing Systems, 36:70757-70798, 2023.
Sachin Goyal, Ziwei Ji, Ankit Singh Rawat, Aditya Krishna Menon, Sanjiv Kumar, and Vaishnavh Nagarajan. Think before you speak: Training language models with pause tokens. arXiv preprint TrXiv:2310.02226. 2023.
Halil Alperen Gozeten, Emrullah Ildiz, Xuechen Zhang, Hrayr Harutyunyan, Ankit Singh Rawat, and Samet Oymak. Continuous chain of thought enables parallel exploration and reasoning. arXiv preprint arXiv:2505.2366 2025.
Jiayan Guo, Lun Du, Hengyu Liu, Mengyu Zhou, Xinyi He, and Shi Han. Gpt4graph: Can large language models understand graph structured data? an empirical evaluation and benchmarking. arXiv preprint 3rXiv:2305./5066 2023.
Tianyu Guo, Hanlin Zhu, Ruiqi Zhang, Jiantao Jiao, Song Mei, Michael I Jordan, and Stuart Russell. How do iims perform two-hop reasoning in context? arXiv preprint arXiv:2502.13913, 2025.
Shibo Hao, Sainbayar Sukhbaatar, DiJia Su, Xian Li, Zhiting Hu, Jason Weston, and Yuandong Tian. Training large language models to reason in continuous latent space. arXiv preprint arXiv:2412.06769 2024.
Subbarao Kambhampati. Can large language models reason and plan? Annals of the New York Academy of Sciences, 1534(1):15-18 2024.
Tushar Khot, Harsh Trivedi, Matthew Finlayson, Yao Fu, Kyle Richardson, Peter Clark, and Ashish Sabharwal. Decomposed prompting: A modular approach for solving complex tasks. arXiv preprint arXiv:2210.02406 2022.
Zhiyuan Li, Hong Liu, Denny Zhou, and Tengyu Ma. Chain of thought empowers transformers to solve inherently serial problems. arXiv preprint arXiv:2402.12873 1, 2024.
Valerii Likhosherstov, Krzysztof Choromanski, and Adrian Weller. On the expressive power of self-attention matrices. arXiv preprint arXiv:2106.033: 2021.
Bingbin Liu, Jordan T Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang, Transformers learn shortcuts to automata. arXiv preprint arXiv:2210.10749, 2022.
Zihan Luo, Xiran Song, Hong Huang. Jianxun Lian, Chenhao Zhang, Jinqi Jiang, and Xing Xie. Graphinstruct: Empowering large language models with graph understanding and reasoning capability. arXiv preprint Stt::2003.0448.. 2024.
William Merrill and Ashish Sabharwal. The expressive power of transformers with chain of thought. arXiv preprint arXhv:2310.07923 2023a.
11

---

William Merrill and Ashish Sabharwal. The parallelism tradeoff: Limitations of log- preciisiiion transformers. Transactions of the Association for Computational Linguistics, 11:531-545, 2023b.
William Merrill and Ashish Sabharwal. A little depth goes a long way: The expressive power of
log-depth transformers. arXiv preprint arXiv:2503.03900 2025.
Jorge Pérez, Pablo Barceló, and Javier Marinkovic. Attention is turing- Journal of Machine Learning Research, 22(75):1-35. 2021.
Jacob Pfau, William Merrill, and Samuel R Bowman, Let's think dot by dot: Hidden computation in transformer language models. arXiv preprint arXiv:2404.15758 2024.
Clayton Sanford, Bahare Fatemi, Ethan Hall, Anton Tsitsulin, Mehran Kazemi, Jonathan Halcrow, Bryan Perozzi, and Vahab Mirrokni. Understanding transformer reasoning capabilities via graph algorithms. Advances in Neural Information Processing Systems, 37:78320-783770 2024.
Zhihong Shao, Peiyi Wang, Qihao Zhu, Runxin Xu, Junxiao Song, Xiao Bi, Haowei Zhang, Mingchuan Zhang, YK Li, Y Wu, et al. Deepseekmath: Pushing the limits of mathematical reasoning in open language models. arXiv preprint arXiv:2402.03300, 2024.
DiJia Su, Hanlin Zhu, Yingchen Xu, Jiantao Jiao, Yuandong Tian, and Qinqing Zheng. Token assorted: Mixing latent and text tokens for improved language model reasoning. arXiv preprint arXiv:2502.03275. 2025.
Jianlin Su, Murtadha Ahmed, Yu Lu, Shengfeng Pan, Wen Bo, and Yunfeng Liu. Roformer: Enhanced transformer with rotary position embedding. Neurocomputing, 568: 127063, 2024.
Karthik Valmeckam, Kaya Stechly, and Subbarao Kambhampati. Lims still can't plan; can Irms? a preliminary evaluation of openai's 's ol on planbench. arXiv preprint arXiv:2409. 13373, 2024.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. Advances in neural information processing systems, 30, 2017
Boshi Wang, Xiang Yue, Yu Su, and Huan Sun. Grokked transformers are implicit reasoners: A mechanistic journey to the edge of generalization. arXiv preprint arXiv:2405.15071, 2024a.
Heng Wang, Shangbin Feng, Tianxing He, Zhaoxuan Tan, Xiaochuang Han, and Yulia Tsvetkov. Can language models solve graph problems in natural language? Advances Neural Information Processing Systems, 36:30840-30861. 2023a.
Peiyi Wang, Lei Li, Zhihong Shao, RX Xu, Damai Dai, Yifei Li, Deli Chen, Yu Wu, and Zhifang Sui. Math-shepherd: Verify and reinforce lims step-by-stee without human annotations. arXiv preprins arXiv:2312.000 08.9355, 2023b.
Xinyi Wang, Lucas Caccia, Oleksiy Ostapenko, Xingdi Yuan, William Yang Wang, and Alessan- dro Sordoni. Guiding language model reasoning with planning tokens. arXiv preprint arXiv:2310.05707. 2023c.
Xinyi Wang, Alfonso Amayuelas, Kexun Zhang, Liangming Pan, Wenhu Chen, and William Yang Wang. Understanding reasoning ability of language models from the perspective of reasoning paths aggregation. In International Conference on Machine Learning, pages 50026-50042. PMLR, 2024b.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al. Chain-of-though prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824 24837, 2022.
Jian Xie, Kai Zhang, Jiangjie Chen, Tinghui Zhu, Renze Lou, Yuandong Tian, Yanghua Xiao, and Yu Su. Travelplanner: A benchmark for real-world planning with language agents. arXiv preprint arXiv:2402.0/ 220.02222...... 622, 2024.
Shunyu Yao, Binghui Peng. Christos Papadimitriou, and Karthik Narasimhan. Self-attention networks can process bounded hierarchical languages. arXiv preprint arXiv:2105.11115. 2021.
12

---

Tian Ye, Zicheng Xu, Yuanzhi Li, and Zeyuan Allen-Zhu. Physics of language models: Part 2.1, grade-school math and the hidden reasoning process. In The Thirteenth International Conference on Learning Representations, 2024.
Longhui Yu, Weisen Jiang, Han Shi, Jincheng Yu, Zhengying Liu, Yu Zhang, James T Kwok, Zhenguo Li, Adrian Weller, and Weiyang Liu. Metamath: Bootstrap your own mathematical questions for large language models. arXiv preprint arXiv:2309. 12099,, 2023.
Xiang Yue, Xingwei Qu, Ge Zhang, Yao Fu, Wenhao Huang, Huan Sun, Yu Su, and Wenhu Chen. Mammoth: Building math generalist models through hybrid instruction tuning. arXiv preprint arXiv:2309.05633 2023.
Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank Reddi, and Sanjiv Kumar. Are transformers universal approximators of eequence-to-sequemee functions? arXiv preprint arXiv:1912.10077,200 2019.
Huaixiu Steven Zheng, Swaroop Mishra, Hugh Zhang, Xinyun Chen, Minmin Chen, Azade Nova, Le Hou, Heng-Tze Cheng, Quoc V Le, Ed H Chi, al. Natural plan: Benchmarking Ilms 2024.
natural language planning. arXiv preprint arXiv:2406.0453
Denny Zhou, Nathanael Schärli, Le Hou, Jason Wei, Nathan Scales, Xuezhi Wang, Dale Schuurmans, Claire Cui, Olivier Bousquet, Quoc Le, al. Least-to-most prompting enables complex reasoning in large language models. arXiv preprint arXiv:2205. /0625, 2022.
Yang Zhou, Hongyi Liu, Zhuoming Chen, Yuandong Tian, and Beidi Chen. Gsm-infinite: How do your Ilms behave over infinitely increasing context length and reasoning complexity? arXiv preprint arXiv:2502.052522 2025.
13

---

A
Notation Details
We provide detailed descriptions of different tokens in Table 2 and the position index of different tokens or continuous thoughts in Table 3
Tokens
Meanings


a special token denoting the beginning of the sentence the source node of edge i the target node of edge
S;
t;
<e>
special token marking the end of an edge special token followed by two candidate nodes
<Q>
C1, C2
two candidate destination nodes
<R>
a special token marking the start of reasoning the root node
[t;]
the i-th continuous thought (represented by a d-dimensional vector) special token driving the model make the final prediction
</>
Table 2: Meaning of each token.
Notations
Position indices
Idx(
)
Idx(s;)
3i
Idx(t;)
3i
ldx(<e>;1) 1)
3i +
ldx(<Q>)
3m +
(d)(c))
3m + 3
ldx(c2)
3m +
Idx (<<>>>>))))))))
3m + 5
Idx(r)
to to + i to +
3m
Idx( [t;])
Idx( <A>)
Table 3: Position indices of different tokens or continuous thoughts in the input sequence.
B
Missing Proofs
B.1
Formal version and proof Lemma
Lemma 3 (Attention chooser, formal version of Lemma 1. Fix any token <α> Voc, integer 2 O, and E (0, 1). Under sinusoidal positional encoding as defined in Definition 1 there exists a construction K, Q E (d2dF))xdd such that for any input sequence (hi...., .n) that satisfies
h Σ Au, where Xo, 2 0 Yu Voc,
X²,=1 (ie
vEVoe
vEVoc
and satisfies (uear, bu) E {0, 13 (t.e., each input embedding is either equal to the embedding of token <a> or orthogonal to and (u h.) 0 for i < (i.e., the first tokens are not <σ>), holds that for any i E [T].
if (h,, Ucw>) = then $t,51 > - E, otherwise 8,,1 > >11-,
where 8,, the attention score from the i-th token the j-th token defined in Algorithm 2 with the input sequence (h, .......,hy p
Proof. Note that 2 implies that each input embedding normalized superposition of token embeddings in the vocabulary. We aim to construct attention head such that when the i-th token is
14

---

<x>, it will pay almost all attention to the position i L, otherwise it will pay almost all attention to the BOS token 
 (known as the attention sink). Define vector Uno >veeoc (<x) u RR which is the superposition of all token embeddings in the vocabulary except for <x>. We define
Q
doe ddr & Uso
O X
x dre x
Idoe
E TR. (2dre))
(Pi
O doe x
doe
K OOdee
T/R(()) r/Idre
E (2ddre)
Odor d
Odve x dre
dre d
where E, > 0 will be specified later and R (6) is defined as in Lemma Therefore,
P: q: Qhb + +P: [(ucs h.)
k; K(h; +p,) = () p. 7/,
nii+t
n/:
Now for any 1 j Si < T, we have
(qi kj) ((D:. + E(ūcs h.) (PI, (p).
Now we fix i E [T]. We first consider the case where (h; uco) (which also implies > E). By and the assumption that token embeddings are orthonormal, we have
(h., ū.) = (hi, un) = O, Vo E Vock = (hi, úcso) = O.
Therefore, we have (q., kj) = =n/p; P)+e). By Lemma
we have
(q: k.) = (P:, P = n/.. rdppe/2
and
(q,, ky) (Pi, Dj+e) S n/pp/22 TJT Vj x -i-l
where er > is defined in Lemma This implies kg) is maximized when j = =i- - with non-zero gap nET, and therefore, we have
exp((qn,k 81 EjE(g exp( (q;,k);)) k,)) exp(ner) + +i ())
exp(nET)
Now consider the where (h,, Uco) = O. Again, by 2 and the orthonormal assumption of token embeddings, we have
(b. ūG))
Σ
(h, Up)
Σ
A
Σ
X =
DEVoel
eEVoct(so>
By Lemma 5 we can define ç =
2dps (p..ps)' and thus
PI.P1))
E((PI.P) PI) (PI,P;)) 2dpE.
Vj E f T).
Note that for any j {2, . T), have
(q. k1) (q:, k))
= (( hn:) ((p1, P1) (P1, ((p,, (p., p1++))
n (2dle dpE)
ddp..
Therefore,
exp(ndeE) Ejen exp( k,)) 2 exp(ydpE) + (i 1)
exp((q;, kz))
(4)
By choosing a sufficiently large 7, the lower bound of proof is complete.
and (4) will both exceed 1 and thus the
D
15

---

B.2 Proof of Lemma 2
Note that the proof sketch of Lemma 2 we showed how to prove the lemma by induction. Here, we use an alternative way that only requires a single forward pass of the transformer. Note that the continuous thoughts are generated
an autoregressive manner, i.e., for an input sequence hyr (hi...., hr), we have h ((4) = TFa (hb() where h, is defined in Algorithm [ with the input sequence h This means for sequence of length 6, appending additional vectors at the end of the sequence does not affect the computation of the first t positions. This means, instead of proving
the following property inductively for each
1. l........ 1:
[t = TFo( [t,]..... [t.])
where for each c, holds [tc]] = - EnEv, u, and hiso is defined as in Section 3 we can
v VV.l
instead prove by a single forward pass by setting the input embedding
hooe =
Σ
Uv:
E [C),
(S)
VIVel
VEV.
and additionally setting hy ho++++ = Ukas, and prove the hidden embedding in the last layer with input hyry satisfies
(L) to+e
Σ uus VO vosess.
Vi=+11
PEVS+1
In Appendix B.3
we construct the parameter for each component of the two-layer transformer.
Finally, Proposition B,4 precisely provides the result we desire.
B.3 Construction of transformer parameters
Proposition B.1 (First layer attention). For any fixed E E (0, 1/2), there exists a construction of key and query matrices for first layer attention heads (Q(0.,), ((.))) } h=0 h=0.... ...A s.t. for any input
embeddings h = (h....., h.) satisfying the format specified in Appendix B.2 the value of following terms exceed E for all i [t):
8 if h; Uses, and 8,1
(0.0)
otherwise; 81,-1 hf; = Uses and (0.1) 8, otherwise;
i,--2 h: u and (0.2) 1 otherwise; (0,3) s h, Uegs and 1, otherwise;
(0.2)
(3)
6ii-1 h: = uea and (0,4)
(0.4)
8,1 otherwise;
where 8, (0.A) SoftMax( (q. (N)
(a)) ..... ..
(h) k (1))))
IR' and k(t) K00.hh (b)
q
1 h h; + Pi.
(0)
(0)
Proof. Note that each of the attention heads an attention chooser as defined in Lemma Therefore, the proposition directly holds by constructing each attention head as described in Lemma
By Proposition B.I each edge token <e> will pay attention to its corresponding source node and target node. Also, the reasoning token <R> will pay attention two candidate destination nodes, and the answer token <A> will pay attention to the last continuous thought. When no token or position needs to be paid attention for some attention heads, it will dump attention to the BOS token 
, phenomenon known as attention sink. Since the attention after softmax cannot exactly be zero, there will be undesired tokens with noise-level magnitude copied to each position. The subsequent MLP layer will filter out the noise. We formalize the above statements rigorously in the following proposition.
Proposition B.2 (First layer MLP). When the input sequence hiz satisfies conditions in Appendix B.2 there exists a construction of 8 (0.h) h() (1) satisfies:
Ant for h E (0...., 4}. o such that the output of the first layer
16

---

h (2)
v3 [i iz 0, 0 dopel'
Wi [m]
(ix((
v3 (u Ogi (ūa, + ūcs)" 0 O lT
1
(isx(css) =
Pixx(ca>) = Vivel11 jūdo Evevo ü, 0 dTE 0 doE
(ix((tt.)) =
Vivi EvEN, u. Ofee Of Ob
Vi [C]
h = for other E [T].
Proof. We use the construction in Proposition B.1 for {Q K ) k=......4 For each position, after attending to the desired tokens, each attention head will copy the attended tokens one of the two buffer spaces. Formally, we provide the construction of value and output matrices for each head below. First, the value matrices are constructed as
((
[LTTE uحoة & u<a>>
Ou dd-d E Rd xd h 1 01=0..... 4.
By construction, we have (h) V(0.A) (0) content(h;) 1(i > 1] h: 1 1} for
i [T), h E 4).. This due to the input format specified Appendix B.2 which ensures that only h contains ueg..
Now we construct output matrices such that the h-th attention head copies the content of the attended token to buffer 1 for h = 0, 4, and to buffer for = 2, Formally, we construct
O (0.A) (Od x
Idre
Odrexdre
Odee ddee IT E R.xxdTE = 0,4,
O (0.A) O ddTE
OdfEx
Ldye
OágExdpE] 1 RdxddT, h = 1,
Therefore, it holds that O (0, (h) = 10 T h. -T-1 1 O dre doe IT for h = 0, 4 and O (0.
(M)
10 0TT 6. ii 1)
0 Tor! for = 1, 1,2,3, 3, and thus we have
Attn (0.1) (h (0))
(0.h)
( =
O
0..0 1
h
0
Ofe
0,4,
jjj
doe
j=1
j=2
rttm 10.10 (h (0))
Si.j
(0.h)
(0.M) (b)
O
O
8i
(0.h)
h
O
1,2,3,
where (0.4) is defined in Proposition B.1 layer is
Therefore, the output at position i of the first attention
(0.5) h
(0) h1
Attn (O.A) (h (h)))
h
Σ -=
Σ
(0.6)
(0.4) 8 hJ
pos(p:) T
h=0
Next, we construct the parameters of the MLP of the first layer. For notation convenience and decompose h,
by the input format in Appendix B.2
ΣV X
Ut (0)
where
x()) (0) ....... ALV
(0)
(0)
IR
Let
MLP MEP
(h
(h.5),),, - o
(0) (W w(
(y) (0.3)) E Rdd
which is two-layer neural network. Let w(") |diag( (UT, UT. U dee E R3Vxd Then
UT (0)
w (0) (0.5)
h
UU -ール E Sij
(0.0) 00)
= Σ 1= Σ ン== Sij
(0.4)
(0)
E 3V
U 1= E ij
(0.4)
(0.h) Σ Σラ 1.1
17

---

Let ot (.) be a coordinate-wise non-linearity such that (x) 1(x 2 of for E R. We choose E 2/n where n is the (maximum possible) number of vertices in the graph. We denote (1)) arg max (0.h)
i.e., f is the position that position pays the most attention within head
h. By Proposition B.1 we can construct key and query matrices such that (0.h)
(,45 > 1 - e/5 for any i
and h. Also, by the input format especially by (), Aik E (0.13 [n]]. which implies
that any non-zero Ait satisfies 1 E [2c, 1] and all non-zero entries of X (0) share the same value for any fixed i. Then by definition of oz (0) (.), we have of (0) (0)
1|
Now we analyze Σj i.s
(0.N)
(0) For any k E [V] we consider Σj=
(0.h) [J 3.k
If (K) = 1, then
we have
(0,8)
(0)
Σ (0.N) %ij
max (0)
j.k
S
25 J.k
< 1
/=2
1=2
If (1) > 1, we have
Σ
8/
(0. (0)
3.h
(0.1) (0)
8. j.k
(0.1) (0)
(,
(1)
1= (4)
When X (0) 1 *
O, we can obtain that
(0.4) (0)
(0.M) (0)
Σ
(0
10) 8
8i jik
jik S
8id
2515
max
5
2=
1= (h)
j=2,ト
(M)
When A (0) 1,,1, ,
> 0, we can obtain that
(0.h)
8
00.00 (0)
2 (1 - (1-5/) 25 2E.
j=2
Therefore, de A- 0.4 (0,A) (0)
(0)
Un (10>
(200)
0))} vk: (ia) &
[V]. Also, by Proposition
B.1 for any i E [T] and & E [V. there is at most one h 10, .....44)) 4]
such that ((A) > and A g00
0 hold simultaneously. Therefore, de (E Ej= 8 4 jik) =
(0.h) (0)
Ex=O,A 1f > 1] 1(x
0}. Ak E [V]. and thus we can write this compactly
(0) Ak
0
(0,h) (0) = Σ A.j
1 A=0,1
> 1(x
(0) Ov).
(m)
h=
122
Similarly, we have
(0)
0.
(0)
Σ
11 (M)
>1} 1(x (0)
(1) Ov}.
N=1j=2
h=1
Therefore,
X (0) / (0) 11.0
(
(w(
1
(0) (0.5)
h
En-o, 1 1(
(h) 1): 1(> (0)
> 0vl
E RR
Σi=1 1 (h) 1} 1(x (0)
> 0vl
(N)
18

---

Finally, we set : W Idiag( UT,
,UT ,,T, UT),
0 Xdre] T E RRx3V and thus
UX (0) / 0 1000
N= 1 > 13 1{x
(0)
> 0v}
MLP ( (h(0.));
[0]
E ER..
UΣ (
> 1} 1 1 (b)
> 0y)
doe
Now derive the output of the MLP for different positions i.
For: Idx(<e>, k) Idx(tx). Note that =(h) for h = 2,3, 4. Also, Aid((s)) East (0) are all V-dimensional one-hot vectors. Therefore, we have MLP
3/ + where k E [m]] have :!!)) = = Idx(sx) and (1 =i
(dx(te) ett and A = Eco>
(h (0.5)
)ld((ce, (h(0..))ldx(cee))) iu un up 0dw LT.
MLP
For i = Idx(<R>) = 3m + 5, we have i!22 = = 2 = Idx(ci) and i!!)) = = ldx(c2). Note that (h) for 0, 1, 4. Also, X Co, and 1 Eoz (0)) Eqp. Therefore, &x
MLP
(h (0.5) ( = [ OxTE (üe, + úc,)) 0d TT
100)
For ldx(<A>) to C + 1, we have (!4) i and 1 for 0 h 3. Note that A = eup, 1 = (0)
ldx([ta]) vive Evevo eu where Vc is the set of vertices reachable from
r within C' steps. Then we have
MLP
gloy (h )(xx(<)>)
Σ u
OoE
OdpE
veVo
For i ldx( [t.]) = to + e for e E [C], we have (!0h)
1 for all h and X (0)
v Evev. Cv.
and thus
MLP (o) (h (0.5)) [dx((tt)) [te])
Σ
u 0 dTE
0
0
dTE
dpE
LEEE
For remaining i, we have {())) for all and A (0) is one-hot.
MLP ((0) (h (0.5)
h 0 O O 0
h,
By applying layer normalization, we can obtain the final result.
Note that Proposition B.2 shows that after the first layer, each <e> token will copy its corresponding source and target token embeddings into its two buffer spaces, respectively. For the second layer, since it is the last layer, we only need to focus on positions for current thoughts Idx( [t,]] to + c and the position for the final prediction <xx<<>>)=<>) T. Since we only need one attention head for the second attention layer, we will omit the index for heads and only keep the index for layers.
Proposition B.3 (Second layer attention). Under the construction of Proposition B.2 and imput format specified in Appendix B.2 for any fixed E (0,1/2), there exists a construction of the second-layer attention parameters
8 Attn =Q(11, (())())) ((1) (()) s.t.
M ME By vV
h (1.5) [t,))
VIV.
E U,
Un(c)
Ve E (0) [C],
Oa-
0 Og
and
Vivel+1 üas + J (ūe + (oz)
UC(++
ldx( (1>)
(1.5)
Vivel+1 Evevo un
+
Odre
0 O
OcTE+trrE
where e(e) E V and (lo < for c (0) UCC
19

---

Proof. In the second attention layer, we aim to construct key and query matrices such that (1) the current thought [t,] will pay attention all edges the source node of the edge is contained in the superposition (see Figure 3): (2) the answer token <A> pays large attention to the reasoning token <R> which stores the two candidate destination tokens in buffer space (see Figure
embedding space
buffer
[tc]
add
buffer 2
C2
content
<Q>
G
C2
<R>
tcc
<A>
Figure 7: Illustration of the second layer attention mechanism for final prediction.
First, we construct
Q (1) = -Tde
Od xdre
Odrexdrel Odr
E Rddxxdd
K (1) -Irua>> & uæs
TLdTE O O E IR xd
where the value of r > 0 will be decided later.
We define Q (1) h1))) k; = k(0) and let
exp((qikk))
85.j Eys:
Note that we have T ldx(< to + + By the construction of the query and key matrices, we have q: = content(h; )),, E [T], kidx(e>>) = @ + Tüas and
(h()),
k; buffer (h(²) for other i. Now consider attention weights for i Idx( [tc])
to + c, Vc E (0} U [C] and = (dx(<A>) = T.
For i = Idx( [t,]) for any fixed {0) [0}U[C), we have q, -1
Vival Evev. u. By Proposition B.2 I üa for j E [m]] kidx(<0>) = rüka> and k, = for other j I i. Define
we have ()
v3
I. [Idx(<e>,)) sy Ve for j [m]]. Therefore,
(q: = 1(j
/3lv
Then we have
exp
[T//3//.]
1(j Iz}
1 $ Ic} Inl exp (T//3/V.l) +i [Ial)
$t.j
Inl exp (T//3/V/))
+ (i [I.))
For (x(()>>)=>)))))) T, note that qr vivo++ Then we have
uess Then (qr, ky) is non-zero only when
j = (dx(<<>>) and the inner product is
Vive+1
exp /c/++| 1{j = ldx(<R>)}
1 4 ldx(<R>))
STJ
exp T/ (T/VIV/l +1) + (T
exp f/v/Vcl+1) (TT-1)
By choosing a large enough т, we have that
Sldx((t.))J =( 1
Iz =c,) 1(j Ie) + E22 Ic) Ae (0) u UC,
STJ =(1 - -c011.) 1sj = ldx(<>>))) + 1(j * ldx(<R>)),
20

---

where E,, E (0,E/T), VO [C+ 1]. Now construct the value and output matrix where
v() OfTe xdrE
LaTE x RRdeedd ddde E Rdxdi.
OdrExdrE
O LLie
Then V; A
vO (1) bufferz(h,)) () e Ree reads from buffer space 2, and O
[buffer2(h]) ( 0 d-dm
T E IRd writes to the content space. Note that
E st Suybbfffer (h) (0)
Attn
(h
= Σ S O = 1=1
Arm
Od-dre
Since, h (1.18) = hn10) Attn (1)) (h())); we have
(L.5) [dx([te]) =
viva Evev. ü, + [
Ec,1) Ei
+ 6,2 EjeBota (1f)erz(h!")) v3
Od-
and
1
üas + +11 EEC+11)
+ + E buffer, (h!")
Vivo+1
v3
hy
(1.5)
Evevo
ur
vivel+1
0 doe+dre
Combining the fact that ( (1) v E Voc with norm less than 1, we can obtain the final result.
is either zero or equal to the superposition of ú, for some
After the second-layer attention, the current thought h 1,,55) now contains all vertices in V. and all vertices that can be reached within one step from Ve, which is Ve+1 by definition. The subsequent MLP layer will then equalize the weights of each vertex and climinate the noise in the continuous thought.
Proposition B.4 (Second layer MLP). Under the construction of Proposition B.3 and the input
format specified by Appendix B.2 there exists a construction of ((1) MLP such that the output of the
second-layer MLP satisfies:
(ex((tt.)) = ViVetil Ever Un Vc [C},
h ca>) = ViVe++5 (Ue + uo, uua + Evevo uv).
Proof. Similar Proposition B.2 we let
MLP (m (h (1.5),,, w
(1.3)) E Rd
where E > 0 and the (elementwise) non-linearity of ( will be specified later. We only consider
h (1.5) where i = to + e for 0 C 1. By Proposition B.3
we can decompose
(e
(n
h
(1.5)
OATE O
VcE [OJUIC],
hf
(1.5)
Un(2)
Od
where A (c) = (2(c)
x 11(1) = (m] .-..
,..." 1/ (2 = [m
.....//
(2)T
E CRV. Let
w
UT
O (vx(dre+dre)
E x2V)xd w
U
U
E Rdd((22)
UT
(dx
(dd-dre
21

---

and o8 (x) = 1x 2 e). Then
MLP (1 (h(1.5) late =W of! (W(" (2))))
(\(a)
-WI" U
(dre+
UT
Oy vx(dr
Odee
Odee
U
U
U UTU
(dd-TT)x
0 (d-dTE)
Oy
(A
OU-diE
and similarly,
MLP (h (1.6))
)r - (1) of " (W((()) hf
MLP
Un
- (1) oe
U
0 xvx x
Un!(2)
UT
Odr
U
(
U UU (1)
0 d (d
Un
1 (1)) + de ( 21)
Od-dre
Now we choose I where = [ is the number of vertices in the graph. By Proposition B.3 we
can make sure that ||E(0) oc < __ for all e u 1] where e(() is defined in Proposition B.3 [m]} which is the set of vertices that can be reached within one step from the currently explored vertex set Ve. By definition, we have Ve+1 V. U.A.. A.. We consider any fixed e E {0} u [C]. For e E V. U A., it holds that
16m
We define A. = {t, S, E Ve,
1
((0 2 /iift///V...
+
+ (0)
C.
2n
16n
4n
For other v,
100 S (c)) < <.
16n
Therefore, 06 (1()) = - U. 1(U E Vo+1). I. and thus we have
Eveven ün Od-dit
MLP Eu
(h (1.5)
1a-e
Vc (0) UCT]
Also, have Nj.
(1)
v3
coi
(C+1) (1)
nez
/3
1
+ Eoz
(C+1) (1)
Velti
(C+1) and m/ Eax
(1)
Lle E Vol. which implies oe (1) (nn = 1(u E Vol.
for other u E Voc. Moreover, t/p
Vive++
Then
[0o + úr + uas + Eveevo ün
MLP MLP
(h (1.)
0u-
Note that by our construction of the input sequence, one and only one of c; is in Vc, and thus ||MLP (h(1.)) lr = +
MLP
By applying layer normalization,
obtain the final result.
B.4 Proof of the main theorem
Proof of Theorem 7 We use the same construction of f as in Lemma 2 where the maximum input
length is T Tmax- By 2 we have hooe
vIv. Evey, u, for 0 < < C. Then (hı,..., hy)
22

---

satisfies the input format specified in Appendix
B.2 and by Proposition B.4
we have
(h hr) h
Vivel + uu + Uez + ukas +
Σ up)
"EVo
(2uc,- Ueg- + U<a>
+
Σ
up)
vivel +
vEVe\(E))
since c₁. Ve and c3-+- $ Vc by the property the graph reachability problem. We set Wo
[n, . uy] and then
Wo hT)
ViVo++5 (2 Cog-s' + e<a> +
1
Σ e.)
wEVo
TF (hroo) arg max WF hT) Cr. veVoc
B.5 Properties of sinusoidal positional encodings
Lemma 4, For any integer f 2 1, there exists a matrix R (6) E Rrdexdee, such that
Pite = R Dj, vi 2 1.
Proof. For any [dp construction two-dimensional rotation matrix
R coos(E E (())))))))))))))) sin(l w²)
sin(E w)) cos(e-ad w))
By definition of the rotation matrix, for any i 2 1, we have
R (e.)
Pi,2--1
R (f.5 coo (i w
[oos ((i + E)
Pete,2511
Pi.2j
sin i w²)
sin ((i + E) w/)
Pi+e,25
Then by setting ( diag R (6.1), (1,2) (e,ddoo/2)) E Rddor xdee we can obtain the desired result.
Lemma 5. For any integer T 2 1, there exists ET >> 0, s.t. Pp) S dpE/2 ET for any i.j E [T]
where # j. Also, (p., p.) dpE/ 2 for all [T'].
Proof. For any i,j E [T]. we have
dre
(p.. P,)
Ps.APj.
km
dre/2
(cos(i . cosc) wh) + sin(i sin(j w)
kml
dvg/2
= Σ
cos( - j)
k=1
Note that for j. directly obtain that (pi, Pp) dpE/2 / since cos((i (a(i-jjen j)w=*) cos 0 for i -j and any i [dpe/2]. Also, since (i j)w Mari/ee is not a multiplier of 2x for i + j. & E [dpe/2], we have cos((i- - )) < 1. Let cos((i j)w O, Vk E [dpE/2],
ET 1
and let er Ek=1
doE/2
ST 0. Therefore, for i + j. have
doe/2
dee/2
(p: p,)
Σ
cos((i j)w < Σ
(1 STM dpE/2 ET.
1
k=1
23

---

make our B.6 Implementing attention chooser under rotary position embedding
In this section, we discuss how to extend our constructions under sinusoidal positional encoding, widely used absolute positional encoding, to the rotary position embedding (RoPE) [Su et al. [222].. a widely used relative positional encoding, to solve graph reachability. Since in our construction, the positional encoding only functions in the first attention layer, and the building blocks of the first attention layers are attention choosers, we mainly focus on how to build the attention chooser block under RoPE.
Since RoPE is relative positional encoding, we don't use p; in computation and thus don't need the last dpE entries in the embedding vectors. Also, since the attention chooser only uses the information in the content space, we omit the two buffer spaces and only keep two dimensions construction clean and assume d = drE+ +2 in this section for the simplicity of the notation. Therefore, we have u [ O, 0] I2 for all Also, assume the input embedding of attention layers satisfies h, [ 1,0) E R.d. This can be achieved easily by adding a bias before the attention layer or modifying the (dTE + 1)-th entry of token embeddings.
Voc in this section, where {ū. VeVoc are orthonormal.
Recall the definition of RoPE below:
Definition (Rotary position embedding [Su et al. 2024 ). Let d be even. For any integer i and any index k E [d/2], we define
cos(1 wh)) sin(i w
sin(t wt) cos(i wh)
R (f.A)
Let
R (1) TE diag
R (1.1)
R
(1.2)
R ((idTE/22) E I dTEEET
and
R diag(R (4.)) R (+.2)
R ((d/22) Rddd
where M M-2/d and M 0 is large constant integer, e.g., M 10 as chosen in Su al. (2024y. We make one additional assumption that M 2 T where T is the maximum length of the input sequence. Then the query vector q, and key vector k; in Algorithm will be calculated as
q = R Qb;
k;
Kh,
Now we show the counterpart of Lemma 3 Junder RoPE below.
Lemma (Attention chooser under RoPE). Fix any token E Voc, integer E 2 O, and E (0, 1). Under rotary position embedding as defined in Definition / there exists a construction of K, Q E (2d)xx,, such that for any input sequence (hı,..., hT) that satisfies
h
Σ Ai, where Xi,0 20 0 Voc, Xx,=1, VVV
[T),
(6)
vEVoc
and satisfies (üce>, h4) {0, 1} (i.e., each input embedding is either equal to the embedding of token < or orthogonal to it) and (ū..,, h.) 0 f.r i E (i.e., the first e tokens not <α>), holds that for any i E (T).
if (h, úes)) = then 31,5-1 > --E, otherwise 8,,1 >1111
where 8i,j is the attention score from the i-th token to the j-th token as defined in Algorithm 2 2with the modification defined in Definition 2 with the input sequence (b....,,r)).
Proof. Note that 6 implies that each input embedding is a normalized superposition of token embeddings in the vocabulary (ignoring the last two entries). We aim construct an attention head such that when the i-th token is <x>, it will pay almost all attention to the position i L, otherwise it (known as the attention sink). We define vector ú, E Rd, which is the superposition of all token embeddings in the vocabulary except for <x>. Moreover, for any integer i, we define p. (pi,1 Pi,dTe) ) RdTTE and define TÉ p;
will pay almost all attention to the BOS token ü
Eve
Pd.) E RR, where for any [d/2], have
Pi,i-1 = cos (i ((-w)). Ptzj = sin (i- w.)
24

---

and w = M-2/dpe where M is defined in Definition 2
Now construct query and key matrices be
Q
Odrexdre
TE P0 @ 12
E Rddd
_ TE
Uoeo
02x2
K
Xdn
1
TE TE
(2)
(PD
TE
@ 12)
Radd
02xdre
7P @ 12
where E. will be specified later and R E IRdTEE R (TT../22) Ix2 defined in
Definition 2 and 1m denotes the all-one vector of dimension m. By Lemma 4 one can calculate that
R R TE
TEP:
TE Pitf:
R R
P
TE
TE Pitji
for any integers i,j.
Therefore.
Po TE
9: -R Qh, (R)
E(U
h.
k, =R Kh, (+)
TEPD nP
(E)
R(
[npTE]
TE
WPP
Then for any { S S T, we have
(q, ky) =1 (R TE -.TEP! TE) + E(Uci (.) (1) TE (1 pb TE)
p-
-1 (ID. (T + E(ūco, ha) (p.-j- Pb
Now we fix E [T]. We first consider the case where (h; úc (which also implies > E). By 6 and the assumption that token embeddings orthonormal, have
(h, ū.) = 0, Ve E Vocl
(h,, üæ.) = 0.
Therefore, have (qi, ky) n/D TE.). By Lemma 5 we have
(q, (() (P ((-0))+)) = 7/P.EE TE ...E) mdTEe/2 /2
TE
and
(g. = -ppp TE
(T) S ndTE/2 2 - nET, Vj + f.
where Er > This implies (q.,k; maximized when j l with a non-zero gap ner, and therefore, we have
exp((qi, k() 81,-- Ejeng exp( k,))
exp(nEr)
exp(nEт) + +i-
Now consider the where (h;, iio)) = O. Again, by (6 and the orthonormal assumption of token embeddings, we have
(h ūv)
d
Σ
x 11
ve oEVoc\f<x>
vEVoc)(<0>)
Note that for any j E (2...., i}
P Pi-j-T Po
= cos((i
- 2/23
T - (i - 5)
= cos
M
(i - 1)
< cos
M
TE (p. 1
TE
T- Po
25

---

where the inequality holds due to M 2 T and the cosine function decreases strictly in [0, 1].
Then, we can define Ç = maxigicisT (P--1---P Po )- 1P:-5-7-Po'' and thus
2drE
$ ( ((P.- Po TE, - (pi-j- (Pi-j-T.Po Po! 2 2dpE. 1A v <iST.
Note that for any j E . T) we have
,
(q, k1) (qi kj)
=1 ((ucc h₂) (PT- TE
(Pi-A-T,Po pot)) - ((Pr. Py+e) - (Pr. Pi+e)))
-P----T,PP
21/ (2dpE - dpE)
-ndPE
Therefore,
exp((q: k1})
exp(ndpE) exp(ridPe) + 1I
81,1 ΣjEn exp( (q: k,))
88)
By choosing a sufficiently large the lower bound of and (8) will both exceed 1 - and thus the proof is complete.
C Experiment Details
C.1 Dataset
Table 4: ProsQA statistics. Numbers are averaged over problem instances.
#Problems
V
[F]
Sol. Len.
Train
14785
22.8
36.5
3.5
Val
257
22.7
36.3
3.5
Test
419
22.7
36.0
3.5
The statistics of the ProsQA dataset is shown in Table 4]
C.2 Stability of the Representation
Table 5: The inner products between i-th continuous thoughts and nodes (3 runs with different random seeds).
Step
Step 2
Step 3
Step 4
Not Reachable -0.37, 0.27,00.55,40 -0.33
-0.26,-0.04.0..11
-0.09,-0.01.0002
-0.25,-0.22 -.20
Reachable
3.59.3.62.3.71
1.55,144,1.37
0.80.0.77.0.22
0.61,0.66.0.53
-Frontier
5.05.5.13.5.38 6.44,6.52.6.84
2.69,2.45,2663
2.11,1.95,2.01
1.27.2.122..0
-Optimal
4.78,4.67,5.11
6.00,5.44.6.443
9.48,8.98,9.58
To test whether CoCONUT always learn the desired superpositional search behavior, conduct multiple experiments with 3 random seeds. We report the mean inner products between continuous thoughts and each node group in Table following the setting in Figure 6 The results consistent across multiple runs.
C.3 Computing Resources
Each run of COCONUT takes about 24 hours on two Nvidia A100 80GB GPUs.
26

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We study hettt--o-cooiiuuuu-thouuge- on graph reachability problems both theoretically and empirically, stated in the abstract and introduction. The corresponding results are in Section and Section respectively.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: As discussed in Section our work mainly focuses graph reachability and the expressivity of transformers. Future work can study more general problems and analyze training dynamics.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
27

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: The main results are Lemma 1
Lemma 2
Theorem We provided proof
sketches in the main text and the full proof in the appendix. The assumptions are made in theorem statements and Sections 2nd
Guidelines:
The answer NA means that the paper does not include theoretical results,
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We describe the details needed for reproducing experiments in the experiment sections.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to model. In general. releasing code and data often one good way to accomplish this, but reproducibilityy can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open- open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibiliity In the case of closed-source models, it may be that access to the model is limited in
28

---

some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: The dataset used are opensourced, and the code is submitted in the supplementary materials.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.et
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
gededdeii///////e/eeeeeoesssssee CodeSubmiee ssi onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: They described in the experiment section and appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We provide standard deviation in Table and results with multiple random seeds in Table
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
29

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπτог rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
They are discussed in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https://neurrpps http:://wwwrrppsccppppubblba ctce/uubbic/Btiicccuieeeeeeeeee
Answer: [Yes]
Justification: The research conducted in the paper conforms, in every respect, with the NeurlPS Code of Ethics
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The paper mainly focuses on the theoretical understanding of the chain of continuous thoughts, which does not have direct negative societal impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
30

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best. faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We used ProsQA (Hao et al. 2024 in our experiments and properly cited it. It is under MIT license.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
31

---

If assets are released, the license, copyright information, and terms of use in the thcode has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssi
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: No assets released.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
32

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
We only use LLMs for grammar checking.
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy battps://neurrs http://arrrirecc/oooeeereee///// Cc/Coonferences/2225//LI. for what should or should be described.
33


Reviews:
[{"review_id": "iCbyF7i97A", "reviewer": "Reviewer_X4Dq", "summary": "This paper gives theoretical investigation of the expressivity and reasoning capability of LLMs when using continuous chains of thought (CoT), specifically, the COCONUT framework. The authors focus on the graph reachability problem and provide a theoretical construction showing that a two-layer transformer with D continuous latent steps (where D is the diameter of the graph) can solve the problem efficiently. This contrasts with discrete CoT methods, which require O(n^2) steps for graphs with n nodes. The key finding is that continuous latent thoughts act as \"superposition states\", representing multiple search frontiers simultaneously—akin to a parallel BFS—while discrete CoTs sequentially explore paths, leading to inefficiency and possible local minima.", "questions": "1. Generalization beyond graph reachability\nWhile the theoretical framework is very interesting, it focuses on the setup of graph reachability. Do you anticipate similar superposition-based representations to emerge for reasoning tasks that are not inherently graph-structured (e.g., algebraic reasoning, program synthesis)? Can your theoretical framework be extended or adapted to such domains?\n\n2. Superposition representation robustness\nHow robust are the emergent superposition representations to noise, adversarial graph perturbations, or imperfect supervision? Have you evaluated how the representations evolve when the graph has spurious or misleading edges?\n\n3. Interpretability of the continuous reasoning path\nWhile the superposition representation appears to be powerful, how interpretable is it in practice? Can individual paths or reasoning traces be extracted or disentangled from the latent vectors?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strengths\nNovel theoretical contribution: The work formalizes the intuition behind continuous CoT's advantage via a compelling superposition-based analogy and mathematical proof, which is a very innovative way of analyzing reasoning behaviors and has deep implications.\n\nWeaknesses\nLimited scope: The paper focuses specifically on the graph reachability problem, and While the problem is a representative benchmark, the theoretical findings are not yet generalized to broader reasoning tasks (e.g. arithmetic, planning, theorem proving).", "was_revised": true, "final_justification": "Overall a solid paper that definitely deserves more visibility and broader discussion.", "rebuttal": "We thank the reviewer for the insightful and helpful comments. Below are our responses.\n\n> 1. Generalization beyond graph reachability While the theoretical framework is very interesting, it focuses on the setup of graph reachability. Do you anticipate similar superposition-based representations to emerge for reasoning tasks that are not inherently graph-structured (e.g., algebraic reasoning, program synthesis)? Can your theoretical framework be extended or adapted to such domains?\n\nWe argue that our results can actually be applied to more general and complex settings:\n\n (1) **Graph reachability is already general and can be extended to more general problems such as the Turing machine halting problem.** Note that the graph reachability problem can capture general logical relations, and is an abstraction of many real-world problems involving planning, searching, logic deduction, etc. Specifically, it captures one of the most fundamental challenges in reasoning problems - deciding the correct branch among many plausible candidates. Moreover, our theoretical construction for graph reachability can be generalized to more general settings, such as Turing machines, where states of a Turing machine can be modeled as nodes in the graph and transition functions can be modeled as edges. Therefore, determining whether a state is reachable can be converted to determining whether a node can be reached in a directed graph. \n\n(2) Beyond graph reachability (which includes tasks that require planning), **our framework can also be extended to other domains such as arithmetic reasoning.**  For example, a recent theoretical work [1] showed that continuous thought also helps solve the minimum non-negative sum problem by parallel exploration and superposition, where the i-th thought can be viewed as a superposition of all possible (signed) sums generated by the first i numbers.\n\n(3) **Experimental results in real-world benchmarks conducted by [2] also show that continuous thought exhibits superposition** when solving math problems.  For example, when solving a GSM-8k problem, the first continuous thought can be decoded into tokens like “180”, “ 180” (with a space), and “9” where the corresponding reasoning trace could be 3 × 3 × 60 = 9 × 60 = 540, or 3 × 3 × 60 = 3 × 180 = 540. This is exactly a superposition of possible intermediate variables in the calculation, which corresponds to two possible reasoning traces.\n\n(4) Finally, we emphasize that **continuous thought can benefit reasoning in different ways** (e.g., might reduce the number of decoding steps since it does not need to output language tokens that are merely for language coherence), and **superposition is one of the most important mechanisms that we aim to study in this paper.**  Note that superposition is most salient and helpful in problems with large branching factors and requiring extensive search, and the graph reachability task captures this feature very well. We can anticipate that for tasks where the bottleneck goes beyond choosing the correct path among many possible candidates, continuous thoughts might benefit reasoning in other ways (such as reducing the number of decoding steps since it does not need to output language tokens only for coherence as mentioned above), instead of mainly relying on superposition. \n\n> 2. Superposition representation robustness How robust are the emergent superposition representations to noise, adversarial graph perturbations, or imperfect supervision? Have you evaluated how the representations evolve when the graph has spurious or misleading edges?\n\nNote that our theoretical constructions work for any directed graph (even a graph containing cycles). This means our main theorem holds even for the worst case, and thus our construction is robust to spurious or misleading edges.\n\n> 3. Interpretability of the continuous reasoning path While the superposition representation appears to be powerful, how interpretable is it in practice? Can individual paths or reasoning traces be extracted or disentangled from the latent vectors?\n\n**Interpretability of the continuous thoughts:** Note that the continuous thought is a superposition of reachable nodes, so it can be interpreted as a probability distribution over different tokens. As in our experiments, one can calculate the inner product of the current thought and different token embeddings (and possibly apply a softmax operation) to obtain a distribution over different nodes. Beyond the graph reachability problem we focused on in our paper, the superposition representation is also interpretable in real-world datasets. For example, when solving a GSM-8k problem, the experiments in [2] shows that the first continuous thought can be decoded into tokens like “180”, “ 180” (with a space), and “9” where the corresponding reasoning trace could be 3 × 3 × 60 = 9 × 60 = 540, or 3 × 3 × 60 = 3 × 180 = 540. The interpretations of the first thought happen to be the first intermediate variables in the calculation.\n\n**Decoding individual reasoning traces:** First, we want to emphasize that the continuous thought stores the reasoning paths very efficiently. According to our construction, the continuous thoughts only store all reachable nodes (and thus all frontier nodes), but not all trajectories. Note that there may exist an exponential number of trajectories for a given graph and a start-destination node pair (e.g., a 2-dimensional grid graph with k*k nodes. Then, for the start node (1,1) and the destination node (k,k), there can be C(2k-2,k-1) paths which is exponential in k). By only storing all frontier nodes, continuous thoughts **implicitly** store an exponential number of reasoning traces. This is in stark contrast to the discrete CoT, which can only **explicitly** store one reasoning trace and is much less efficient.  Since continuous thoughts maintain all possible reasoning traces, one should not anticipate extracting an individual path in the middle of the reasoning process. However, after the model obtains the final answer, one can use it to collapse the superposition of the continuous thought and extract the desired individual reasoning trace. For example, in our graph reachability task, given the final answer (the reachable destination node), one can decode the path using stored frontier nodes step-by-step “from right to left”.\n\nTo decode the reasoning trace for more general tasks, one possible method is to train a VAE (variational auto-encoder) to decode the continuous thoughts to obtain the discrete thoughts. As discussed above, the VAE should also receive the final answer as the input to extract a ``collapsed’’ reasoning trace conditioned on the final answer. Although it is beyond the scope of this paper to design algorithms to extract the reasoning traces for a given task, it is a very interesting and important future direction.\n\n**Reference:**\n\n[1] Gozeten HA, Ildiz ME, Zhang X, Harutyunyan H, Rawat AS, Oymak S. Continuous Chain of Thought Enables Parallel Exploration and Reasoning. arXiv preprint arXiv:2505.23648. 2025 May 29.\n\n[2] Hao S, Sukhbaatar S, Su D, Li X, Hu Z, Weston J, Tian Y. Training large language models to reason in a continuous latent space. arXiv preprint arXiv:2412.06769. 2024 Dec 9."}, {"review_id": "u7OFcrlVzo", "reviewer": "Reviewer_wcdH", "summary": "I am not very familiar with the underlying theoretical framework used in this paper. In my view, this paper develops a theoretical construction showing that two-layer transformers with continuous latent chains can solve directed graph reachability in a number of steps equal to the graph’s diameter, while discrete chains require quadratically more steps. The proofs use practical positional encodings, and experiments on synthetic and math tasks dshow similar behaviors emerge during training.", "questions": "- How practically useful is this theory for large-scale LLMs?  \n- Can the authors discuss in more details on how the proposed construction transfer to other domains beyond graph reachability?", "limitations": "Yes", "rating": 4, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "---\n**Quality (3)**  \n- Strengths:  \n    - Clear separation result between continuous and discrete chain-of-thought expressivity.  \n    - Proofs account for realistic positional encodings (sinusoidal, RoPE).  \n    - Empirical results align tightly with theory, with useful visualizations of latent states.  \n- Weaknesses:\n    - Relies on idealized assumptions (exact orthonormal embeddings, large embedding dimension).  \n    - Requires embedding size proportional to vocabulary, which may be impractical in real LLMs.\n\n---\n\n**Clarity (3)**  \n- Strengths: Overall, the paper is well formatted and has a clear introduction and literature review. \n- Weaknesses:\n    - Heavy notation and many indices make the paper hard to parse for someone new to transformer expressivity.  \n    - Key mechanisms (attention chooser, buffer/MLP filter) could be summarized more succinctly, with full details in the appendix.\n\n---\n\n**Significance (2)**  \n- Strengths: in general, understanding why (continuous) latent reasoning helps with theoretical insights is an important topic and can inspire many future works. \n- Weaknesses:\n    - The paper focused on a toy reachability problem. It is slightly unclear on how the proposed analysis can transfer to real-world reasoning tasks or larger LLMs.  \n    - Practical impact on real world benchmarks remains to be validated.\n\n--- \n\n**Originality (3)**  \n- Strengths: I believe the  theoretical link between continuous superposition and expressivity speedup is fresh. \n\n---", "was_revised": true, "final_justification": "The authors have addressed the questions, and I would maintain my score.", "rebuttal": "We thank the reviewer for the insightful and helpful comments. Below are our responses.\n\n> Weaknesses (Quality): Relies on idealized assumptions (exact orthonormal embeddings, large embedding dimension).\n    Requires embedding size proportional to vocabulary, which may be impractical in real LLMs.\n\nIt is a very common practice that embedding size is proportional to vocabulary in theoretical analysis such as previous works [1-5]. Note that this is a natural consequence of the assumption of orthonormal embeddings. While all previous work [1-5] assumed orthonormal embeddings (or even one-hot embeddings), our theory actually does not require that token embeddings are exact orthonormal, but only need to be approximately orthogonal as in practical scenarios. For example, If we assume that for two different nodes, the inner product of their embeddings are $\\varepsilon$ (e.g., $\\varepsilon = 0.1$) instead of 0 which is the ideal exact orthonormal setting, our theorem still holds since the attention mechanism can downweight the noise through softmax operation, and MLP will filter out the noise and keep only the useful signals. Our theoretical construction also works for the case where the inner product of different token embeddings is less than or equal to $\\varepsilon$ with a smaller $\\varepsilon$ and more fine-grained analysis. We adopted the orthonormal assumption to make the analysis and main message cleaner, and we will add the discussion and analysis of the more practical approximate orthogonal setting in the revision. We thank the reviewer for the suggestion.\n\n> Weaknesses (Clarity):\nHeavy notation and many indices make the paper hard to parse for someone new to transformer expressivity.\nKey mechanisms (attention chooser, buffer/MLP filter) could be summarized more succinctly, with full details in the appendix.\n\nWe thank the reviewer for the suggestions in writing. We will utilize the additional content page in the camera-ready version to make notations easier to read and key mechanisms more succinct, and add more details in the appendix.\n\n> Weaknesses (Significance):\nThe paper focused on a toy reachability problem. It is slightly unclear on how the proposed analysis can transfer to real-world reasoning tasks or larger LLMs.\nPractical impact on real world benchmarks remains to be validated.\n\nSee responses to the second question.\n\n> Question 1: How practically useful is this theory for large-scale LLMs?\n\nPrevious work shows experimental results that continuous thought outperforms discrete thought in certain types of reasoning tasks, but did not provide a fine-grained analysis of why continuous thoughts can reason more efficiently and what types of tasks benefit more from continuous thought. Our theory identifies and provides a rigorous analysis of one of the most important mechanisms, i.e., superpositions that enable parallel search, which makes continuous thoughts powerful. According to our analysis, superposition is more helpful for problems with large branching factors and requiring extensive search. Therefore, our theory can guide large-scale LLMs on whether to choose continuous thoughts to solve a given task.\n\n> Question 2: Can the authors discuss in more details on how the proposed construction transfer to other domains beyond graph reachability?\n\nBelow, we discuss how our results can be applied to more general and complex settings:\n\n(1) **Graph reachability is already general and can be extended to more general problems such as the Turing machine halting problem.** Note that the graph reachability problem can capture general logical relations, and is an abstraction of many real-world problems involving planning, searching, logic deduction, etc. Specifically, it captures one of the most fundamental challenges in reasoning problems - deciding the correct branch among many plausible candidates. Moreover, our theoretical construction for graph reachability can be generalized to more general settings, such as Turing machines, where states of a Turing machine can be modeled as nodes in the graph and transition functions can be modeled as edges. Therefore, determining whether a state is reachable can be converted to determining whether a node can be reached in a directed graph. \n\n(2) Beyond graph reachability (which includes tasks that require planning), **our framework can also be extended to other domains such as arithmetic reasoning.**  For example, a recent theoretical work [6] showed that continuous thought also helps solve the minimum non-negative sum problem by parallel exploration and superposition, where the i-th thought can be viewed as a superposition of all possible (signed) sums generated by the first i numbers.\n\n(3) **Experimental results in real-world benchmarks conducted by [7] also show that continuous thought exhibits superposition** when solving math problems.  For example, when solving a GSM-8k problem, the first continuous thought can be decoded into tokens like “180”, “ 180” (with a space), and “9” where the corresponding reasoning trace could be 3 × 3 × 60 = 9 × 60 = 540, or 3 × 3 × 60 = 3 × 180 = 540. This is exactly a superposition of possible intermediate variables in the calculation, which corresponds to two possible reasoning traces.\n\n(4) Finally, we emphasize that **continuous thought can benefit reasoning in different ways** (e.g., might reduce the number of decoding steps since it does not need to output language tokens that are merely for language coherence), and **superposition is one of the most important mechanisms that we aim to study in this paper.**  Note that superposition is most salient and helpful in problems with large branching factors and requiring extensive search, and the graph reachability task captures this feature very well. We can anticipate that for tasks where the bottleneck goes beyond choosing the correct path among many possible candidates, continuous thoughts might benefit reasoning in other ways (such as reducing the number of decoding steps since it does not need to output language tokens only for coherence as mentioned above), instead of mainly relying on superposition. \n\n**References:**\n\n[1] Tian Y, Wang Y, Chen B, Du SS. Scan and snap: Understanding training dynamics and token composition in 1-layer transformer. Advances in neural information processing systems. 2023 Dec 15;36:71911-47.\n\n[2] Tian Y, Wang Y, Zhang Z, Chen B, Du S. Joma: Demystifying multilayer transformers via joint dynamics of mlp and attention. arXiv preprint arXiv:2310.00535. 2023 Oct 1.\n\n[3] Chen L, Bruna J, Bietti A. Distributional associations vs in-context reasoning: A study of feed-forward and attention layers. arXiv preprint arXiv:2406.03068. 2024 Jun 5.\n\n[4] Nichani E, Damian A, Lee JD. How transformers learn causal structure with gradient descent. arXiv preprint arXiv:2402.14735. 2024 Feb 22.\n\n[5] Nguyen Q, Nguyen-Tang T. One-Layer Transformers are Provably Optimal for In-context Reasoning and Distributional Association Learning in Next-Token Prediction Tasks. arXiv preprint arXiv:2505.15009. 2025 May 21.\n\n[6] Gozeten HA, Ildiz ME, Zhang X, Harutyunyan H, Rawat AS, Oymak S. Continuous Chain of Thought Enables Parallel Exploration and Reasoning. arXiv preprint arXiv:2505.23648. 2025 May 29.\n\n[7] Hao S, Sukhbaatar S, Su D, Li X, Hu Z, Weston J, Tian Y. Training large language models to reason in a continuous latent space. arXiv preprint arXiv:2412.06769. 2024 Dec 9."}, {"review_id": "X76xCt4AQr", "reviewer": "Reviewer_BPy1", "summary": "This paper provides theoretical guarantees for this paper: *Training Large Language Models to Reason in a Continuous Latent Space.*", "questions": "According to Lemma 2, it seems the model must extend its reasoning one more “hop” in the graph at each step. To keep training stable, if we move a portion of the language-based reasoning into the latent space at every stage, doesn’t that mean that what used to be a single fine-tuning pass now requires many rounds? If I’ve understood correctly, wouldn’t this greatly increase the overall training cost?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths: This paper offers rigorous theoretical proofs and simulation experiments that demonstrate its effectiveness on reasoning tasks such as graph reachability. Although the article focuses on graph reachability as a case study, its theoretical analysis and constructions—enabling “relative‐offset” access—apply to any task, with the potential to extend to path search, planning, theorem proving, and other complex reasoning scenarios.\n\nI didn't find any obvious shortcomings in this paper.", "was_revised": true, "final_justification": "I am keeping my score unchanged.", "rebuttal": "We thank the reviewer for the insightful and helpful comments. Below are our responses.\n\n>According to Lemma 2, it seems the model must extend its reasoning one more “hop” in the graph at each step. To keep training stable, if we move a portion of the language-based reasoning into the latent space at every stage, doesn’t that mean that what used to be a single fine-tuning pass now requires many rounds? If I’ve understood correctly, wouldn’t this greatly increase the overall training cost?\n\n\nYes, the training cost is indeed higher compared to the cost of discrete thought since it involves multiple training stages. One possible method to reduce the training cost is to convert multiple steps (or tokens) from the language space to the latent continuous space at each stage, as in the original coconut paper [1]. However, there might be a tradeoff between training efficiency and stability, and we need to choose the number of steps/tokens moving from the language space to the latent space at each stage appropriately.  Although it is beyond the scope of this paper to design more efficient training methods in continuous space, we agree with the reviewer that it is a very important future direction.\n\n\n**References:**\n\n[1] Hao S, Sukhbaatar S, Su D, Li X, Hu Z, Weston J, Tian Y. Training large language models to reason in a continuous latent space. arXiv preprint arXiv:2412.06769. 2024 Dec 9."}, {"review_id": "8Q4ai1DpQn", "reviewer": "Reviewer_5d3n", "summary": "This paper provides a theoretical analysis and experiments on directed graph reachability to explain why Chain of Continuous (Coconut) Thought outperforms Chain of Thought (CoT, the discrete counterpart). The core idea is that CoT is working in a step-by-step manner; the thinking process can only contain one single reasoning path at a time, while Coconut implicitly traverses multiple reasoning paths in parallel within the continuous thought vector. The paper proves that a two-layer transformer with $D$ steps of continuous CoTs can solve the directed graph reachability problem of a graph with diameter $D$. The paper also provides experiments that show that a 2-layer transformer outperforms a 12-layer Coconut transformer with CoT.", "questions": "1. As described in the second weakness, can the viewpoint of this paper be generalized to more complex tasks? \n2. Do you need to increase the capacity of the continuous thought when the task gets more complex?\n3. In the graph reachability problem, can the capacity of the continuous thought reduce the steps needed to get the answer?\n4. As described the the third weakness, how would that affect your conclusions?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "**Strength**:\n1. The paper is well-written and well-motivated -- trying to understand why Coconut outperforms discrete CoT. \n2. The paper proposes an interesting perspective: Coconut performs multiple reasoning paths in parallel, and tries to prove it on the graph reachability task.\n3. The experimental results, including ablation studies, support the theoretical analysis.\n\n**Weakness**:\n1. The paper focuses solely on synthetic graph reachability tasks; it is unclear how well these proofs and findings can be generalized to most other natural language problems that LLMs face. While the paper aims to answer why Coconut outperforms its discrete counterparts in various reasoning tasks, however, this paper solely focuses on the graph problem and how the advantage can be generalized to other tasks are not discussed.\n2. The continuous thought vectors may saturate in more complex tasks. The graph reachability task is a relatively easy task where a simple reasoning path can be easily represented, and the inference of the next step is also easy (just traverse). However, when the task gets complicated, for example, the math reasoning problem. The continuous thought vectors may not be able to carry many more reasoning paths than the written thoughts in CoT.\n3. The theory part of this paper assumes that the token embeddings are orthonormal; however, this is not true in general LLM's embedding space. [1]\n\n[1] Mikolov, Tomas, et al. \"Efficient estimation of word representations in vector space.\" arXiv preprint arXiv:1301.3781 (2013).", "was_revised": true, "final_justification": "The authors have addressed some of my concerns, but my main concern remains about the practical value and applicability of the proposed approach for general-purpose reasoning in real-world scenarios. I will keep my score.", "rebuttal": "We thank the reviewer for the insightful and helpful comments. Below are our responses.\n\n>1. As described in the second weakness, can the viewpoint of this paper be generalized to more complex tasks?\n\nWe argue that our results can actually be applied to more general and complex settings:\n\n (1) **Graph reachability is already general and can be extended to more general problems such as the Turing machine halting problem.** Note that the graph reachability problem can capture general logical relations, and is an abstraction of many real-world problems involving planning, searching, logic deduction, etc. Specifically, it captures one of the most fundamental challenges in reasoning problems - deciding the correct branch among many plausible candidates. Moreover, our theoretical construction for graph reachability can be generalized to more general settings, such as Turing machines, where states of a Turing machine can be modeled as nodes in the graph and transition functions can be modeled as edges. Therefore, determining whether a state is reachable can be converted to determining whether a node can be reached in a directed graph. \n\n(2) Beyond graph reachability (which includes tasks that require planning), **our framework can also be extended to other domains such as arithmetic reasoning.**  For example, a recent theoretical work [6] showed that continuous thought also helps solve the minimum non-negative sum problem by parallel exploration and superposition, where the i-th thought can be viewed as a superposition of all possible (signed) sums generated by the first i numbers.\n\n(3) **Experimental results in real-world benchmarks conducted by [7] also show that continuous thought exhibits superposition** when solving math problems.  For example, when solving a GSM-8k problem, the first continuous thought can be decoded into tokens like “180”, “ 180” (with a space), and “9” where the corresponding reasoning trace could be 3 × 3 × 60 = 9 × 60 = 540, or 3 × 3 × 60 = 3 × 180 = 540. This is exactly a superposition of possible intermediate variables in the calculation, which corresponds to two possible reasoning traces.\n\n(4) Finally, we emphasize that **continuous thought can benefit reasoning in different ways** (e.g., might reduce the number of decoding steps since it does not need to output language tokens that are merely for language coherence), and **superposition is one of the most important mechanisms that we aim to study in this paper.**  Note that superposition is most salient and helpful in problems with large branching factors and requiring extensive search, and the graph reachability task captures this feature very well. We can anticipate that for tasks where the bottleneck goes beyond choosing the correct path among many possible candidates, continuous thoughts might benefit reasoning in other ways (such as reducing the number of decoding steps since it does not need to output language tokens only for coherence as mentioned above), instead of mainly relying on superposition. \n\n> 2. Do you need to increase the capacity of the continuous thought when the task gets more complex?\n\nAccording to our theory, the only requirement for the capacity of continuous thought is that the embedding dimension should be linear in the number of vertices of the graph, which is a relatively mild requirement and common practice used in many previous theoretical works (e.g., [1-5]).\n\n> 3. In the graph reachability problem, can the capacity of the continuous thought reduce the steps needed to get the answer?\n\nYes. In principle, if we allow the embedding dimension to be extremely large (e.g., exponential in graph size), it might even be possible to use only a constant number of steps to get the answer. In our paper, we use the common assumption that the embedding dimension is linear in the number of vertices of the graph (e.g., [1-5]), which is more practical.\n\n> 4. As described the the third weakness, how would that affect your conclusions?\n\nOur theory actually does not require that token embeddings are exact orthonormal, but only need to be approximately orthogonal as in practical scenarios. For example, If we assume that for two different nodes, the inner product of their embeddings are $\\varepsilon$ (e.g., $\\varepsilon = 0.1$) instead of 0 which is the ideal exact orthonormal setting, our theorem still holds since the attention mechanism can downweight the noise through softmax operation, and MLP will filter out the noise and keep only the useful signals. Our theoretical construction also works for the case where the inner product of different token embeddings is less than or equal to $\\varepsilon$ with a smaller $\\varepsilon$ and more fine-grained analysis. We adopted the orthonormal assumption to make the analysis and main message cleaner, and we will add the discussion and analysis of the more practical approximate orthogonal setting in the revision. We thank the reviewer for the suggestion.\n\n**References:**\n\n[1] Tian Y, Wang Y, Chen B, Du SS. Scan and snap: Understanding training dynamics and token composition in 1-layer transformer. Advances in neural information processing systems. 2023 Dec 15;36:71911-47.\n\n[2] Tian Y, Wang Y, Zhang Z, Chen B, Du S. Joma: Demystifying multilayer transformers via joint dynamics of mlp and attention. arXiv preprint arXiv:2310.00535. 2023 Oct 1.\n\n[3] Chen L, Bruna J, Bietti A. Distributional associations vs in-context reasoning: A study of feed-forward and attention layers. arXiv preprint arXiv:2406.03068. 2024 Jun 5.\n\n[4] Nichani E, Damian A, Lee JD. How transformers learn causal structure with gradient descent. arXiv preprint arXiv:2402.14735. 2024 Feb 22.\n\n[5] Nguyen Q, Nguyen-Tang T. One-Layer Transformers are Provably Optimal for In-context Reasoning and Distributional Association Learning in Next-Token Prediction Tasks. arXiv preprint arXiv:2505.15009. 2025 \nMay 21.\n\n[6] Gozeten HA, Ildiz ME, Zhang X, Harutyunyan H, Rawat AS, Oymak S. Continuous Chain of Thought Enables Parallel Exploration and Reasoning. arXiv preprint arXiv:2505.23648. 2025 May 29.\n\n[7] Hao S, Sukhbaatar S, Su D, Li X, Hu Z, Weston J, Tian Y. Training large language models to reason in a continuous latent space. arXiv preprint arXiv:2412.06769. 2024 Dec 9."}]

Author rebuttal:

Meta-review: The paper theoretical studies the power of continuous chain of thoughts for graph reachability problem. It provides a theoretical construction of a 2-layer Transformer that can solve the problem in $d$ steps where $d$ is the graph diameter (CoT would require $n^2$ steps where $n$ is the number of vertices.) It does so by encoding multiple search paths as a superposition. This shows the benefit of latent thoughts over discrete CoT based reasoning. Experiments are conducted to validate various aspects of the theory.

Reviewers were quite positive about the paper, highlighting the novel theoretical contribution, the superposition based analogy and the empirical validation. Some concerns were raised regarding the limited scope of the analysis (just the graph reachability problem) to which the authors responded that the problem is general enough to capture many interesting settings. Overall this paper makes a solid contribution towards understanding the strengths and limitations of continuous vs discrete CoT in a reasonably general problem of graph reachability.
Decision: Accept (poster)