Let Me Think! A Long Chain of Thought Can Be Worth Exponentially Many Short Ones
Authors: Parsa Mirtaheri
Ezra Edelman
Samy Jelassi
Eran Malach
Enric Boix-Adserà
Venue: NeurIPS 2025 poster ()
Keywords: reasoning
chain-of-thought
test-time scaling
large language models
transformers
expressivity
Primary area: deep_learning
TL;DR: demonstrates reasoning settings where scaling the length of chain-of-thought offers an exponential advantage over parallel scaling and aggregation.

Abstract: Inference-time computation has emerged as a promising scaling axis for improving large language model reasoning. However, despite yielding impressive performance, the optimal allocation of inference-time computation remains poorly understood. A central question is whether to prioritize sequential scaling (e.g., longer chains of thought) or parallel scaling (e.g., majority voting across multiple short chains of thought). In this work, we seek to illuminate the landscape of test-time scaling by demonstrating the existence of reasoning settings where sequential scaling offers an exponential advantage over parallel scaling. These settings are based on graph connectivity problems in challenging distributions of graphs. We validate our theoretical findings with comprehensive experiments across a range of language models, including models trained from scratch for graph connectivity with different chain of thought strategies as well as large reasoning models.

Let Me Think! A Long Chain-of-Thought Can Be Worth Exponentially Many Short Ones
Parsa Mirtaheri'
Ezra Edelman" University of Pennsylvania ezrae@seas. upenn edu
Samy Jelassi
UC San Diego
Harvard University
parsaOuesd. edu
sjelassi@fas afas harvard.
Eran Malach
Enric Boix-Adserà University of Pennsylvania eboix@wharton. upenn edu
Harvard University emalach@g. hww.ard..eeeee..... edu
Abstract
Inference-time computation has emerged as promising scaling axis for improving large language model reasoning. However, despite yielding impressive perfor- mance, the optimal allocation inference-time computation remains poorly under- stood. A central question is whether to prioritize sequential scaling (e.g., longer chains of thought) or parallel scaling (c.g., majority voting across multiple short chains of thought). In this work, seek to illuminate the landscape of fest-time scaling by demonstrating the existence of reasoning settings where sequential parallel scaling. These settings
scaling offers exponential advantage based on graph connectivity problems in challenging distributions of graphs. We validate theoretical findings with comprehensive experiments across range language models, including models trained from scratch for graph connectivity with different chain of thought strategies well large reasoning models,
Introduction
Large Language Model (LLM) scaling has recently undergone paradigm shift toward increasing the amount of compute used during inference [1, 2], moving beyond traditional axes such as model size, training data, and pretraining compute [3, 4J. Scaling inference-time compute is particularly important for reasoning tasks, and key ingredient in OpenAl's o-series models [5], DeepSeek-Ri [6] among other frontier models [7, 8, 9, 10].
Despite the impressive performance of these systems, the central question of how to optimally allocate inference-time compute is not yet settled. The main challenge is that the space of strategies that use compute test time is large and diverse: wide variety of methods exist [2, 11, 12], each with its own empirical scaling law [1. 2]. Additionally, different methods can sometimes be combined, which further complicates any analysis.
In this paper, we seek fundamental and general principles that help clarify the landscape of inference- time compute. Since there is large range of inference-time methods, in order to make progress categorize methods into two classes [7]] (1) parallel scaling and (2) sequential scaling. We review these notions below.
'Equal contribution.
Currently at Apple.
Codee is available http://gittlb..oomeeeeep//////tt
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

(1) Parallel scaling refers to generating multiple independent responses in parallel, and ag- gregating them in some way output the final solution [13, 14. 15]. The most common aggregation technique is "best-of-n", where reward function (e.g. another language model task-specific verifier [14]) selects the single highest-scoring response as the output. Another widely used aggregation method is majority voting, which determines the final response by choosing the most frequent one among generated responses [13].
Sequential scaling encompasses all techniques that do not fall under parallel scaling. The flagship method in this category is Chain of Thought (CoT) [16, 17, 18], in which an LLM first outputs chain of reasoning tokens, before outputting its final answer. This may be achieved with one of several strategies to induce longer chains of reasoning in LLMs, such as adding prompt instruction to "think step by step" [18], or forcing longer chain of thought by replacing end-of-text tokens with "Wait" [7], or training with reinforcement learning objectives which can automatically induce longer chains of thought [6].
Consensus has yet be reached how balance both types of scaling most effectively. On the one hand, sequential scaling via long chains of thought has demonstrated particular promise for tackling challenging problems, such mathematics and coding benchmarks [19, 20, 21, 22, 6, 7]. On the other hand, the computational cost of inference grows quadratically in the context window for transformer-bat beased architectures [23], making sequential scaling more expensive per-token than parallel scaling. This motivates the main question addressed in this work:
Can we quantify the trade-off between sequential and parallel scaling for reasoning problems?
1.1
Our contributions
Our main contribution is to introduce reasoning task in which sequential scaling can be exponentially more powerful than parallel scaling. Namely, small decrease sequential scale necessitates large increase in parallel scale to achieve the same level of accuracy. This tradeoff is illustrated in Figure for transformer models evaluated on this task.
Parallel and Sequential Scaling of Transformer Trained Graph Reasoning Task
Parallel and Sequential Scaling of BaaSSekk-A--Dssill--wweees
64
1.0
1.0
0.9
0.9
Best Accuracy
Paralee Scale
Para tel Scale
32
16
8
1
0.5
0.5
4096
Sequential
Scall
Sequential Scale
Figure 1: Model accuracy with different combinations of parallel and sequential scaling graph reasoning task. The sequential scale is the length budget for the chain of thought, and the parallel scale is the number of independent chains of thought generated. Left: The performance of small transformer model trained for this task, where aggregation is with best-of-n. Right: The performance of the frontier DeepSeck-Ri R1-Distill-Quee Qwen-32B reasoning model [6], where aggregation is with majority vote. In both cases, there is a regime in which large increases to parallel scaling are required compensate for small decrease in sequential scaling; more details in Section 4.
Our reasoning task is a variant of the basic graph connectivity task. Solving requires determining whether pairs of vertices are connected by stepping through several edges, and thus it serves as a proxy task modeling multi-step reasoning with CoT on more naturalistic data. Details are in Section 2.
Reasoning task
Our task motivated by a growing theoretical literature on the limitations and capabilities of transformers graph reasoning tasks [24, 25, 26], which have found that graph connectivity is

---

challenging for bounded-dene depth transformers [27, 28, 29, 30, 30, The reason for this is that graph computation appears to be a sequential problem, yet the transformers' sequential computation is bounded by their depth, as proved in expressivity results [32, 33, 34).
Theoretical separations between sequential scaling and parallel scaling We consider bounded- depth, bounded- bounded-precisionn precision transformers on the connectivity problem, and we present two theoretical results that crystallize the intuition that graph connectivity requires sequential scaling which cannot be cost-effectively compensated by parallel scaling.
First, we prove that (a) sequentially scaling with one polynomial-length CoT can solve the connectivity problem, but contrast (b) parallel scaling by aggregating over polynomially-many O(1)-length Chains of Thought cannot succeed. The proof of this theorem leverages recent results the expressivity of transformers [32, 34]. and requires making complexity theoorttc assumptions; see Section 3.1.
Second, in order to obtain a more fine-graines picture of the landscape and understand the performance of chains of thought with greater than constant length, we abstract transformer computation on graph reasoning tasks with a "Vertex Query Model" of computation. This model of computation is inspired by known limitations of transformers for multi-hop reasoning [31]. The Vertex Query Model has the benefit that it is tractable to analyze. Thus, we use it to guide the construction of challenging distributions of "two-path" graphs and "bridge" graphs, for which we give evidence that there is an exponential gap between the performance of sequential and parallel scaling; see Section 3.2.
Experimental validation and exploration In Section 4, we empirically validate the challenging distributions of "two-path" and "bridge" graphs motivated by our Vertex Query Model. We use these tasks to test transformer-based language models trained to solve graph connectivity, and find that there is significant advantage to scaling sequential computation over scaling parallel computation. We then extend this empirical investigation to leading open-source reasoning models, evaluating their performance on the graph connectivity task as well as on the more complex AIME2024 [35] dataset. The results reveal consistent trend favoring sequential scaling over parallel scaling.
In Section 5, explore training transformers the graph connectivity problem with reinforcement learning (RL). We observe the emergent behavior that RL training gradually increases the length of the COT. This behavior mirrors the growth in CoT length that occurs when training DeepSeek-RI [6] with RL, and supports that the graph connectivity problems studied in this work are a rich enough task capture many interesting behaviors observed in practice.
2 Graph reasoning tasks
Motivated by recent work on the expressivity and limitations of constant-depth transformers [28, 32, 31, 24, 29, 30], we test models on a graph connectivity task that serves as a basic testbed for reasoning. The most canonical connectivity task that one could consider is (s, f)-connectivity, defined below.
Definition ((s, coonneciiyy problem). The (s, c--onnecctivy problem is: given a graph G and vertices t in this graph, return whether s and are connected.
One drawback of this task is that is asymmetric - in the case that and I. are connected, there is path certifying that they are connected. On the other hand, when and are in distinct components, there is no such path certificate. In order to ease our theoretical analysis and the experiments, we instead consider more symmetrical problem that we call (s, t1, tz) -onnnectvvv which captures the essence of the difficulty in graph connectivity. We define this problem below.
Definition 2 ((s, (2, connectivity problem). The (s, f1, (11122)--onnccetee connectivvv problem is: given graph G and vertices s, t1, and t2 in this graph, return whether s is connected to t or s is connected to t2, given the promise that exactly one of these two alternatives is true.
The benefit of this formulation of the problem is that in all cases, there is path certifying the correct solution. For example, in the case that s is connected to t, then the model can easily verify this in its chain of thought by finding a short path connecting 8 41
Our theoretical results and our experiments are for (s, 4,, (1,12))-oo -on-nnnneyy in the setting where G consists of two identical, disconnected components, one of the components contains and f;, and the
3

---

other component contains 1z-4. The task is inputted as a list of edges, followed by the IDs of f1. and 1z. See Figure 2 for an example of the input format.
3 Theoretical evidence for benefits of sequential over parallel scaling
We provide two main pieces of theoretical evidence for the benefits of sequential scaling over parallel scaling on these graph reasoning problems. We first prove result based on expressivity limitations of bounded-depth transformers. Next, we obtain more fine-grained picture based on an abstraction for CoT on graph reasoning problems that we call the vertex query model of computation.
3.1 Separation based on transformer expressivity limitations
We consider the (s, l,, (2) -oycnntncty problem on undirected graphs, as defined in Definition 1, where the size of the problem is given by the number of nodes in the graph. We study the most extreme case of parallel versus sequential scaling: many chains of constant length, compared to one long chain of polynomial length.
We leverage recent results on the expressive power of transformers with chain-of- -ftn--uttthhuutt to prove the following theorem. requires making the complexity theory assumption that TC Z L, which is explained in Appendix A.
Theorem 1 (Informal statement of Theorem 4). Assume the cumplexity-theoreti statement that TC" 2 Then the following is true for bounded-depth, mmited-precisson transformers.
Sequential scaling succeeds: There is constant >> 0 such that transformer with CoT of length S n² solves any t1, (,,1,,))-coome cconnectvvv problem.
Parallel sealing fails: For any constants C1, O, and any transformer architecture, majority vote over S. Tt independently-sampll CoTs of length S C2 has accuracy S (1) for t1, (2))ttt-cnnntiivii problems.
The above result may be rephrased as follows: parallel scaling requires at least a super-polynomin number of chains of thought of length O(1) in order simulate the computation achievable by sequentially scaling one chain of thought with polynomial length.
Proof ingredients In Appendix A we provide the formal statement of the theorem and the full proof of the theorem. For the positive result, the main ingredient is from [32], which implies that transformers with polynomial length CoT can implement any polynomial-time algorithm, and therefore can implement breadth-firss search which solves the connectivity problem. For the negative result, the expressivity bounds of [34, 33] imply that transformers with O(1)-lenghh chain-of-thought fall into the class of circuits TC Our main insight that aggregating multiple independently- sampled CoT's is also TC circuit, and therefore is unable solve (s, cooneecivy under the complexity-theoretic assumption. Finally, we reduce from the (s, -)cconecctivv problem to the (s, &1, f2) cconeectivity problem with TC reduction.
3.2 Evidence for separation based on the vertex query model
While the result in Theorem is based on expressivity limitations of transformers, it is crude in the sense that (1) it does not provide a polynomial versus exponential separation, and (2) the parallel scaling limitations apply only to CoT of length O(1). We now complement Theorem with more fine-grained lens on the tradcoff between sequential and parallel scale. order to achieve this fine-grained result, we make simplifying abstraction the dynamics of Chain of Thought called the Vertex Query Model (VQM). This computational model is more amenable to analysis than studying the TC circuit class.
Definition 3 (Vertex Query Model). An algorithm for t2)coccconetttiitt is implementable in the Vertex Query Model (VQM) if it takes as input $ t1, t2, and can only access the graph G through "neighborhood queries" NG, which given vertex output the set No(v) {u 3v, u) E).
We also define the Restricted Vertex Query Model (RVQM), where the algorithm can only initially query s, and subsequently can only query vertices in the sets returned by previous queries.

---

11
10
7
4
8
13
Input Prompt
Graph:
4) (a 12)
(11 5) (8 9)]
Task:
10 to or 6
2
14
3
12
Figure 2: Left: an example "two-path" graph task from Theorem 2. Right: the task input is list of edges in randomized order and with randomly permuted vertex IDs.
For the results in this section, we work under the simplifying abstraction that transformers with chain of thought are constrained to learning functions computable in the VQM with cost at most proportional the length of the chain of thought.
This simplifying abstraction is motivated by prior literature. First, constant-depth transformers are known to have limited range for multi-hop reasoning in graphs [31]. In chains of thought that output a sequence of nodes, it reasonable to expect that the next node outputted by a transformer should lie only in a constant-depth neighborhood of the previous nodes or be randomly-chosen node. These kinds of chains of thought correspond exactly to VQM algorithms. Second, the VQM is closely related to the previously proposed "globality barrier" for transformers learning to reason (Definition 3 of [28]). The "globality barrier" suggests that transformers with CoT can only efficiently learn functions such that each CoT step does local computation depending on constant number of entries in the previous chain of thought. The VQM corresponds to such algorithms where the local computations allowed are neighborhood queries.
While the above arguments for VQM capturing the power of chain of thought are only heuristic, now show that it useful abstraction because it motivates challenging families of graphs for the (s, 41, (2)) -eonnnnncttttt task. In Theorem below, we show that algorithms in the VQM fail on problems where the graph is given by two disjoint paths, unless a large number of queries proportional to the length of the path is taken (corresponding under our assumption to long chain of thought proportional the length of the path).
Theorem 2 (Minimum number of VQM queries needed for graph connectivity). Consider the graph G given by two disjoint paths of length 2 with randomly permuted vertex IDs. Suppose s, 21, t2 distinct endpoints of these paths such that and t; are the same path for exactly one i E {1, Then
(L) queries are sufficient: There is a VQM algorithm that executes L queries and solves the (s, (2,11,2)))ae -cocnnectyy problem with probability 1.
(L) queries are needed: For any VQM algorithm that executes q S (I. 2)/22/2 queries, the probability of correctness of the algorithm on (s, (1, -2-comectiiy is exactly 1/2.
The proof is deferred to Appendix B. An example two-path graph visualized in Figure 2. We experimentally validate in Figure 10 that, on frontier reasoning models, minimal amount of sequential scale is needed to solve this problem, below which parallel scaling with majority vote ineffective.
drawback of the above theorem that it proves limitations when the number of queries is smaller than the length of the shortest path between s and {f1, In those situations, it may be impossible connected. This raises the question:
for algorithms in the VQM model certify which and are there graphs where sequential scale is still beneficial even with more queries than the shortest path length? We provide one such example below, with the "bridge graph" construction. An example of this graph structure is illustrated in Figure 3.
Definition 4 (Bridge Graph). A bridge graph is an undirected graph parametrized by the non-negative integers dep th, short, long, and deadend. It is constructed follows:
Let U1 be the start node. Then, for each 1,... depth
1. Let 0it1 be the next "intersection"
2. Add two paths between and Vi+1, one of length short and the other long
3. Add path from v of length deadend (do not connect this to 1441)
5

---

Input Prompt
Graph: [C29 54) (15 2)
(47 9) (32 16)]
Taak: 15 to 8 or 1
Chain-of-thought
DPS:
Decision:
[1]
Figure 3: Left: Example "Bridge" graph task from Definition Top right: the task input is a list of edges in randomized order and with randomly permuted vertex IDs. Bottom right: examples of chain of thought strategies used to train the model in our experiments in Section
We now show that in the Restricted VQM, there is still gap between sequential and parallel scale, even in a regime where more queries are made than the length of the shortest path in the bridge graph. Namely, with
number of queries a constant fraction larger than the shortest path in this graph, any RVQM algorithm will be exponentially unlikely to succeed.
Theorem Consider an algorithm in the Restricted Vertex Query Model solving (s, bı, 12)- connectivity on the union of two identical copies of the Bridge(d, 1, 21, 0) graph, where is the starting node on one side of the graph, and i and 2/2 correspond to the copies in the two connected components of the end node the main path the other side. For any d (0, 1).
Sequential scaling succeeds: There exists an algorithm which makes (1 + 5)2ld queries and succeeds with probability least exp dd82
2. Parallel scaling fails: with probability at most + exp -- dd) Thus, parallel scaling with majority vote needs exp(S(d)) independent runs to succeed with probability 2 2/3.
Any algorithm which makes more than (1 (1-8) Id queries succeeds
We emphasize that the shortest path between the and 4 is of length 1d, and the theorem proves that any algorithm in the RVQM has exponentially poor advantage over random guessing even for number of queries a constant fraction larger than this shortest path. The intuition is that each time the model hits an intersection (that is, vertex with degree greater than two), it has to guess where to go next, and only has a constant probability per intersection of choosing the shortest path. The proof can be found in Appendix B.
4 Empirical evidence for benefits of sequential over parallel scaling
In this section, we experimentally study whether it is more efficient to parallelize multiple short CoTs to scale one CoT sequentially. We validate the theoretical evidence put forward in Section by (a) training transformer language models from scratch, and (b) evaluating leading open-source LLMs on the (s, 4 (2)41,2))ccmme connnettivv task with the "bridge graphs" of Theorem 3. Further experiments on the "two-path" graphs of Theorem 2 are available in Appendix C.
4.1 Chain of Thought strategies
In the transformers that train from scratch, we seek most efficiently use the chain-of-thoughh budget in order to best exhibit the full power of sequential scaling. In order to achieve this, we first train models on datasets generated by different CoT strategies, and then focus the CoT strategy that has the best performance.
The CoT strategies that we consider provide "proof" in the form of an exploration of the graph from the source to sink, such as path from the s to either ( or /2. This enables us implement best-of-n parallel scaling with a verifier for the proof. Even subject to the restriction of providing

---

proof, the CoT lengths can still be short enough that we find that models trained on them get only barely higher than trivial accuracy.
The strategy with the shortest CoT that we consider is Shortest- Path, where the training data consists of shortest paths from the source node the target node. Two other CoT strategies are derived from the trace of a Path CoT the path from the source node the target node in the DFS tree, and DFS CoT the list of DFS tree nodes ordered by when they are first visited in the DFS trace. The CoT and the final decision are appended an input prompt to form training example of the CoT strategy dataset (See Figure 3).
(DFS) starting from the source node and ending at the target node.
4.2 Evaluation metrics
Given task as input prompt, model trained with CoT strategy autoregressively generates sequence of tokens either by greedy decoding or by sampling with a temperature. We extract the CoT and the decision from the output and evaluate each separately using the following criteria:
1. Decision Criterion: This checks if the decision is equal to the reachable target node.
2. Evidence Criterion: This verifies that the CoT starts with the source node, ends with one of the target nodes, and for every node in the CoT other than the source node, at least one of its adjacent nodes appears earlier in the CoT.
Building on these, we consider the following aggregation methods for evaluating parallel scaling:
1. Majority Decision: This takes the majority over the decisions of the sampled outputs.
2. Best-of-n: This checks if any of the sampled CoTs meets the evidence criterion, and if finds one, outputs its corresponding decision. Otherwise, chooses one of the two target nodes at random as its decision.
We also define decision accuracy and evidence accuracy based on the decision and evidence criteria respectively, and evaluate models using them, over set of test tasks from the same distribution the training tasks. For parallel scaling evaluation, we compute decision accuracy for majority decision and best-of-n methods.
4.3 Experiment setup
In our experiments, we let short=3, long=5, deadend=3, and refer to Bridge (d,, 3, 5, 3) as Bridge (d). To construct a task of depth d, we generate two randomly labeled Bridge (d) graphs, select the first starting node of one of the graphs as the source node s, and the last ending nodes of the two graphs as the target nodes 1 and /2. Finally, to transform the task into sequence, we list the edges of the graphs in a random order, along with the labels of the source and target nodes as illustrated in Figure 3. For each CoT strategy and Bridge (d) task with depth from 1 to 5, we train Mistral causal language model [36, 37] with hidden layers, 4 attention heads, and intermediate size 128 with context length of 400 for 200 epochs. In the experiments of each task, we use the same number of training tokens for all CoT strategics, equal to the number of training tokens in 500,000 samples from the Shortest-Pi Path CoT strategy.
4.4 Results
We have found that models trained on DFS traces exploit a long CoT budget outperform models trained on short CoT's (those generated by Shortest-Path and Path). The models trained on short CoTs tie with the DFS trained ones on very short budgets (at relatively low accuracy), but fall behind and plateau when given higher token budget, as if they don't 't succeed early on, they don't know how to continue (which makes sense, since they have left their training distribution). The DFS model achieves perfect evidence and decision accuracy on the tasks, while the Path and Shortest- Path models struggle with the tasks when increasing the graph's depth; achieving 1. 16% and 0.0% evidence accuracies respectively the Bridge (5) task (See Figure 4).
How models trained on short CoTs behave. What scenarios inference time lead to the failure of models trained on short CoTs? Looking more closely the evidence accuracy of the models and
7

---

Evidence Accuracy of Strategies Bridge(d)
Sequential Scaling of CoT Strategies on Bridge(5)
1.0
0.9
0.9
0.8
0.8
Puldence Accuracy
DFS
0.6
Path
0.6
DFS
0.5
Shortest Path
0.5
Path
Shortest Path
Predktted Path
0.4
Lorgest Path
Preditted Shortest-Palt Patth
0.3
0.3
0.2
0.2
0.1
0.0
0.0
16
20
24
28
32
36
40
44
48
52
56
60
64
68
72
Depth of the Brioge Graph
Sequential Scale
Figure 4: (left) Evidence accuracy of CoT strategies on Bridge tasks of various depths compared to the probabilities of a DFS trace becoming the shortest path and a path respectively. (right) Evidence accuracy of CoT strategies with different sequential CoT budgets on Bridge (5) task. Models outputs are sampled with greedy decoding. Error bars represent 95% binomial confidence intervals.
their behavior in response to an input, we find that although the Shortest-Path model trained to take the short path from the starting node of each component to its end node, it cannot distinguish between the unexplored paths attached to the current node and gets into out-of tit---fddittibuttio scenarios by following the wrong paths and fails to recover from them. Therefore, given its limited CoT budget, its accuracy matches with the exponentially small probability P(DFS E D(Shortest-Pathi) = 3x4"-T of DFS trace that randomly chooses an unvisited adjacent node at each step, traversing the shortest path (See Figure 4). This supports the assumption that the model's limited expressivity limits its look-ahead ability, which motivated the Vertex Query Model (VQM) of Section 3.2. The Path model's accuracy follows similar trend, but it is slightly higher than the in-distribution exploration probability P(DFS& E D(Path)) = ex The Path model's more flexible CoT budget and its ability to follow edges allows it to recover from some of the out-of-distribution scenarios it gets into by backtracking from the deadend or backward paths.
Parallel scaling of models trained on short CoTs. Since Figure 4 shows that sequential scaling of one chain of thought increases the accuracy significantly, we now ask: can we aggregate multiple short CoTs (either with best-of-n or with majority voting) to achieve the same accuracy as one longer CoT? If so, how many short CoTs must aggregate? We experiment by generating many short CoTs with temperature 1.0 and measuring accuracy for both majority and best-of-n aggregation methods. For one run, decision accuracy is usually higher than evidence accuracy, because the model can both rely on its CoT to make a decision and the CoT is not a valid proof it can randomly guess between the two target nodes. This also makes decision accuracy less robust when the model's evidence accuracy is low (See Figure 13 for evidence of both behaviors in short CoT models). However, when parallel scaling, the best-of-n method that uses CoT's scales better than taking majority over the decisions (See Figure 7). Hence, we report the best-of-n accuracy for the experiments with parallel scaling. We find that the best-of-n accuracies of the Shortest-Path and Path models follow the probability that at least one of their n independent sampled CoTs succeed, with the success probability of each corresponding to the exponentially small probability of traversing the shortest path and a path respectively (See Figure 7). Therefore, we need to sample an exponential number of CoTs from these models achieve an accuracy on par with a single CoT of our models trained on long CoTs.
Sequential scaling of CoT models. Inspired by the observation that our short CoT models behave like the search models but with limited sequential CoT budget, we examine the evidence accuracy of each model with different sequential scales of CoT budget. We budget-force [7] the models by considering their CoTs of various maximum lengths, and find that at every sequential CoT budget, the DFS model achieves the highest evidence accuracy (See Figure 4). Then, to examine the best accuracy we could get with parallel scaling our models within fixed sequential budget, we parallel scale the DFS model of different sequential scales. We find that sequential scaling up to a certain threshold is more effective than exponential parallel scaling (See Figure 1). Even from that threshold,
8

---

Parallel and Sequential Scaling
Parallel and Sequential Scaling of
51-328
Qwen3-328
1.0
64
1.0
0.9
0.9
Paralle Scale
accuracy
Parallel
32
0.7
8-
0.6
16-
0.6
4-
818
1637 Sequential Scale
2456
3071
0.5
528 1056 1585 2113 2641 3170 3698
0.5
Sequential Scale tokens)
Figure 5: A comparison of parallel and sequential scaling for s1-32B [7] and qwen3-32B [9]. Note that the trend from Figure is repeated. Sequential scaling basically essential to get higher accuracy, and parallel scaling only becomes useful once sequential scaling has allowed for non-trivial performance.
scaling sequentially further is more efficient in terms of the number of tokens generated than parallel scaling (See Figure 8). In other words, for fixed total token budget, sequential scaling always beats parallel scaling.
4.5 Experiments with large language models
We measured the performance of various LLMs on the graph connectivity task, as well as on the AIME2024 [35] benchmark.
Specifically, we consider the graph connectivity task on a bridge graph with short=3, 1ong=9, deadend=O,, depth=2. Mirroring other experimental and theoretical results, LLMs only get trivial performance without a CoT, but when allowed a long CoT, they can achieve very high performance. We obtained similar trends with each of the three LLMs tested, Qwen3-32BI9 DeepSeek R1 Distill Qwen-32B[6], and S1-32B[7] (See Figure 1 and Figure 5). Note that it takes roughly thousand tokens of sequential scaling to get non-trivial accuracy, many of these tokens used up by the LLM describing what its general approach to the problem will be, before actually executing strategy.
We also conducted experiments with the s1-32B model [7] on the AIME2024 [35] dataset. The results show that sequential scaling cannot be efficiently replaced by parallel scaling for this mathematical task, supporting the generalizability of our findings to real-world scenarios (See Figure 11). While quantifying the exact trade-off between them for complex mathematical problems such as this is beyond the scope of our fundamental study, we observe that the results confirm our conclusion that sequential scaling is necessary.
5 Emergent sequential scaling with reinforcement learning
We observed that our models trained on short CoT' cannot look ahead to distinguish the correct and wrong paths and get into didtttribbutiinn scenarios. However, there are cases where the Path model recovers from the out- nut-of-distribution scenario and succeeds in generating a verified CoT followed by the correct decision. This results in verified CoTs that are longer than any CoT in the training data (See Figure 4), with behaviors such as backtracking that are not present in the training data. How does reinforcing the model on its own verified CoT's, including these -iit----tttriuttionn CoT's, affect the model's performance and reasoning behavior? In this section, we explore this using Self-Taught Reasoner (STaR) [38], an expert iteration RL method, to fine-tune the model on its verified CoTs.
Experiment setup We perform a few iterations of STaR, where at each iteration, we sample responses to 500, 000 examples of the Bridge (d) task from the Path model with temperature 1.0. Then fine-tune the model for 20 more epochs its verified CoTs.

---

(a) Evidence Accuracy
(b) Decision Accuracy
1.0
0.8
0.6
d=1
0.4
d=2
d=3
0.2
d=4
d-5
(c) Average Length of CoTs
(d) Average Length of Verified CoTs
60
50
COT Length
40
30
20
0
3
4
Iteration
RL Iteration
Figure 6: Path model's (a) Evidence accuracy, (b) Decision accuracy, and average length of (c) CoTs that follow the format, and (d) CoT' that verified Bridge tasks of various depths, before and after RL iterations. Error bars represent 95% binomial confidence intervals for accuracies, and 95% normal confidence intervals for CoT lengths.
Results We find that the model's accuracy on each task improves dramatically after few iterations; evidence accuracy of the model pre-trained on Bridge (3) task jumping from 21.16% to 92.02% after 4 iterations. At the same time, the average length of the model's valid CoT's and verified CoTs increases and the model learns to exploit increasingly longer CoTs after each RL iteration (See Figure 6). Moreover, we find that the model's accuracy improves at every sequential CoT budget (See Figure 9). This gives insight into the observed phenomena of long CoT emergence during RL on reasoning tasks [6, 39, 40). RI. can adapt the model's training to its expressivity for the task, by reinforcing its own computations that result in solving the task. In case, the model is not expressive enough to solve the task by following the CoT strategy it was trained on. However, after training on its successful generations during RL, its CoT scales scquentially to follow longer but more simple strategy it is expressive enough to adopt.
6 Discussion
Our results on graph connectivity demonstrate that there are settings in which sequential scaling is vastly more cost-effective than parallel scaling. However, our results are limited only to the setting that we study, and the optimal recipe for test-time compute may be wroblem-dependen lying in mixture of combining both parallel scaling and sequential scaling. Indeed, our experiments indicate that once the sequential scale becomes large enough, parallel scaling becomes a more cost-effective axis to scale due to diminishing returns to sequential scaling. Understanding that determine the optimal mix of parallel and sequential scaling for a given dataset is interesting direction for future study. Additional discussion of limitations beyond what presented in this section, well discussion of further related work, can be found in Appendix D and Appendix E.
general principles
10

---

Acknowledgments
This work was initiated while EB, EE, EM, and PM were visiting the Simons Institute for the Theory of Computing. EB was supported by the Simons Institute as Research Fellow at the Special Year on Large Language Models and Transformers, and also by NSF grant CCF-2106377. EE acknowledges gift from AWS AI to Penn Engineering's s ASSET Center for Trustworthy AI. PM acknowledges support from the National Science Foundation (NSF), the Simons Foundation for the Collaboration on the Theoretical Foundations of Deep Learning. and the Office of Naval Research through awards DMS-2031883, #81 #634, and ONR-N000142412631 Center of Mathematical Sciences and Applications. EM was supported by the Kempner Institute for the Study of Natural and Artificial Intelligence. which was made possible in part by a gift from the Chan Zuckerberg Initiative Foundation. This work used the Delta system at the National Center for Supercomputing Applications through allocation TG-CIS220009 from the Advanced Cyberinfrastructure Coordination Ecosystem: Services & Support (ACCESS) program, which is supported by National Science Foundation grants #2138259, #2138286, #2138307, #2137603, and #2138296 [41].
acknowledges funding support by the

---

References
[1] Charlic Victor Snell, Jachoon Lee, Kelvin Xu, and Aviral Kumar. Scaling LLM test-time com- pute optimally can be more effective than scaling parameters for reasoning. In The Thirteenth International Conference on Learning Representations, 2025.
[2] Yangzhen Wu, Zhiqing Sun, Shanda Li, Sean Welleck, and Yiming Yang. Inference scaling laws: An empirical analysis of compute-optimal inference for problem-solving with language models, arXiv preprint wrXiv:2408.00722 2024.
[3] Alec Radford, Karthik Narasimhan, Tim Salimans, llya Sutskever, et al. Improving language understanding by generative pre-training. 2018.
[4] Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models, arXiv preprint arXiv:2001.068 000361,,,,, 2020.
[5] OpenAl. Learning to reason with 1lms, September 2024.
[6] Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Ruoyu Zhang, Runxin Xu, Qihao Zhu, Shirong Ma, Peiyi Wang, Xiao Bi, al. DeepSeek-R1: incentivizing reasoning capability in LLMs via reinforcement learning. arXiv preprint arXiv:2501. /2948, 2025.
[7] Niklas Muennighoff, Zitong Yang, Weijia Shi, Xiang Lisa Li, Li Fei-Fei, Hannaneh Hajishirzi, Luke Zettlemoyer, Percy Liang, Emmanuel Candès, and Tatsunori Hashimoto. sl: Simple test-time scaling, 2025.
[8] Kimi Team, Angang Du, Bofei Gao, Bowei Xing, Changjiu Jiang, Cheng Chen, Cheng Li, Chenjun Xiao, Chenzhuang Du, Chonghua Liao, et al. Kimi k1. Scaling reinforcement learning with llms. arXiv preprint arXiv:2501.1233
2025.
[9] An Yang. Anfeng Li, Baosong Yang. Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chang Gao, Chengen Huang, Chenxu Lv, Chujie Zheng, Dayiheng Liu, Fan Zhou, Fei Huang, Feng Hu, Hao Ge, Haoran Wei, Huan Lin, Jialong Tang, Jian Yang, Jianhong Tu, Jianwei Zhang, Jianxin Yang, Jiaxi Yang. Jing Zhou, Jingren Zhou, Junyang Lin, Kai Dang, Keqin Bao, Kexin Yang, Le Yu, Lianghao Deng, Mei Li, Mingfeng Xue, Mingze Li, Pei Zhang, Peng Wang, Qin Zhu, Rui Men, Ruize Gao, Shixuan Liu, Shuang Luo, Tianhao Li, Tianyi Tang, Wenbiao Yin, Xingzhang Ren, Xinyu Wang, Xinyu Zhang, Xuancheng Ren, Yang Fan, Yang Su, Yichang Zhang, Yinger Zhang, Yu Wan, Yuqiong Liu, Zekun Wang, Zeyu Cui, Zhenru Zhang, Zhipeng Zhou, and Zihan Qiu. Qwen3 technical report, 2025.
[10] Qwen Team. Qwq-32b: Embracing the power of reinforcement learning, March 2025.
[11] Sasha Rush and Daniel Ritter. Speculations on test-time scaling, 2024.
[12] Sean Welleck, Amanda Bertsch, Matthew Finlayson, Hailey Schoelkopf, Alex Xie, Graham Neubig, Ili Kulikov, and Zaid Harchaoui. From decoding meta-generationn Inference-time algorithms for large language models. Transactions on Machine Learning Research, 2024. Survey Certification.
[13] Bradley Brown, Jordan Juravsky, Ryan Ehrlich, Ronald Clark, Quoe V. Le, Christopher Ré, and Azalia Mirhoseini. Large language monkeys: Scaling inference compute with repeated sampling, 2024.
[14] Wenjie Ma, Jingxuan He, Charlie Snell, Tyler Griggs, Sewon Min, and Matei Zaharia. Reasoning models can be effective without thinking, 2025.
[15] Xuezhi Wang. Jason Wei, Dale Schuurmans, Quoe V Le. Ed H. Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. In The Eleventh International Conference on Learning Representations, 2023.
[16] Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoe V Le, Denny Zhou, et al. Chain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems, 15:24824-24833 2022.
12

---

[17] Maxwell Nye, Anders Johan Andreassen, Guy Gur-Ari, Henryk Michalewski. Jacob Austin, David Bieber, David Dohan, Aitor Lewkowycz, Maarten Bosma, David Luan, Charles Sutton, and Augustus Odena. Show your work: Scratchpads for intermediate computation with language models, 2022.
[18] Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. Large language models are zero-shot reasoners, 2023.
[19] Kanishk Gandhi, Ayush Chakravarthy, Anikait Singh, Nathan Lile, and Noah D. Goodman. Cognitive behaviors that enable self-improving reasoners, or, four habits of highly effective stars, 2025.
[20] Edward Yeo, Yuxuan Tong, Xinyao Niu, Graham Neubig, and Xiang Yue. Demystifying long chain-of-thoue th-thh reasoning LLMs. In ICLR 2025 Workshop on Navigating and Addressing Data Problems for Foundation Models, 2025.
[21] Wenkai Yang, Shuming Ma, Yankai Lin, and Furu Wei. Towards thinking-optimal scaling of test-time compute for Ilm reasoning, 2025.
[22] Dacheng Li, Shiyi Cao, Tyler Griggs, Shu Liu, Xiangxi Mo, Eric Tang. Sumanth Hegde, Kourosh Hakhamaneshi, Shishir G. Patil, Matei Zaharia, Joseph E. Gonzalez, and Ion Stoica. Llms can easily learn to reason from demonstrations structure, not content, is what matters!, 2025.
[23] 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.
[24] Keyulu Xu, Jingling Li, Mozhi Zhang, Simon S. Du, Ken ichi Kawarabayashi, and Stefanie Jegelka. What can neural networks reason about?, 2020.
[25] Heng Wang, Shangbin Feng, Tianxing He, Zhaoxuan Tan, Xiaochuang Han, and Yulia Tsvetkov. Can language models solve graph problems natural language? In A. Oh, T. Naumann,
A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances in Neural Information Processing Systems, volume 36, pages 30840-30861. Curran Associates, Inc., 2023.
[26] Bahare Fatemi, Jonathan Halcrow, and Bryan Perozzi. Talk like a graph: Encoding graphs for large language models, 2023.
[27] Clayton Sanford, Bahare Fatemi, Ethan Hall, Anton Tsitsulin, Mchran Kazemi, Jonathan Halerow, Bryan Perozzi, and Vahab Mirrokni. Understanding transformer reasoning capabilities via graph algorithms. arXiv preprint arXiv:2405. 2024.
[28] Emmanuel Abbe, Samy Bengio, Aryo Lotfi, Colin Sandon, and Omid Saremi. How far can transformers reason? the globality barrier and inductive scratchpad. The Thirty-eighth Annual Conference Neural Information Processing Systems, 2024.
[29] Macicj Besta, Nils Blach, Ales Kubicek, Robert Gerstenberger, Michal Podstawski, Lukas Gianinazzi, Joanna Gajda, Tomasz Lehmann, Hubert Niewiadomski, Piotr Nyczyk, et al. Graph of thoughts: solving elaborate problems with large language models. In Proceedings of the AAAI Conference on Artificial Intelligence, 2024.
[30] Juno Kim, Denny Wu, Jason Lee, and Taiji Suzuki. Metastable dynamics of chain-of-thought reasoning: Provable benefits of search, rl and distillation, 2025.
[31] Clayton Sanford, Daniel Hsu, and Matus Telgarsky. Transformers, parallel computation, and logarithmic depth. Forty-First International Conference on Machine Learning, 2024.
[32] William Merrill and Ashish Sabharwal. The expressive power of transformers with chain of thought. In The Twelfth International Conference Learning Representations, 2024.
[33] William Merrill and Ashish Sabharwal. The parallelism tradeoff: Limitations of log-precision transformers. Transactions of the Association for Computational Linguistics, 2023.
13

---

[34] David Chiang. Transformers in uniform TC arXiv preprint urXhv:2409.13623) 2024.
[35] Mathematical Association of America. American invitational mathematics examination (aime) 2024. Hosted by the Mathematical Association of America, problems and solu- tions booklet, 2024. Accessed February 2024, pettss:/maa..on org.aathrgmmahh..ee competitions american- www.taaaioonl-maahmmtttttttootoe
wxw.inatiinni...e..e......eaee.t aime.
[36] Albert Q. Jiang, Alexandre Sablayrolles, Arthur Mensch, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Florian Bressand, Gianna Lengyel, Guillaume Lample, Lucile Saulnier, Lélio Renard Lavaud, Marie-Anne Lachaux, Pierre Stock, Teven Le Scao, Thibaut Lavril, Thomas Wang, Timothée Lacroix, and William El Sayed. Mistral 7b, 2023.
[37] Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, et al. Transformers: State- of-the-art natural language processing. Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations, pages 38-45, 2020.
[38] Eric Zelikman, Yuhuai Wu, Jesse Mu, and Noah Goodman. STar: Bootstrapping reasoning with reasoning. Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022.
[39] Weihao Zeng, Yuzhen Huang, Qian Liu, Wei Liu, Keqing He, Zejun Ma, and Junxian He. Simplerl-zoo: Investigating and taming zero reinforcement learning for open base models in the wild, 2025.
[40] Jiay Pan, Junjie Zhang. Xingyao Wang, Lifan Yuan, Hao Peng, and Alane Suhr. Tinyzero. 2025. Accessed: 2025-01-24.
[41] Timothy J. Boerner, Stephen Deems, Thomas R. Furlani, Shelley L. Knuth, and John Towns. ACCESS: Advancing Innovation: NSF's Advanced Cyberinfrastructure Coordination Ecosys- tem: Services & Support. In Proceedings of the Practice and Experience in Advanced Research Computing (PEARC 23), page 4, Portland, OR, USA, July 2023. ACM.
[42] Lena Strobl. Average-hard attention transformers are constant-depth uniform threshold circuits. arXiv preprint arXiv:2338 032 20233
[43] William Merrill and Ashish Sabharwal. A logic for expressing nog-precision transformers. Advances in Neural Information Processing Systems, 36, 2024.
[44] David Mix Barrington and Alexis Maciel. Lecture 5: The landscape of complexity classes. 2000.
[45] Ryan Williams. Some estimated likelihoods for computational complexity. Computing and Software Science: State of the Art and Perspectives, pages 9-26, 2019.
[46] Christos H Papadimitriou. Computational complexity. In Encyclopedia of computer science, pages 260-265. 2003.
[47] Omer Reingold. Undirected connectivity in log-space. Journal of the ACM (JACM), 55(4):1-24, 2008.
[48] Jorge PÂ@rez, Pablo BarcelĀ², and Javier Marinkovic, Attention turing-complete. Journal of Machine Learning Research, 22(75):1-35, 2021.
[49] Lena Strobl, William Merrill, Gail Weiss, David Chiang, and Dana Angluin. What formal lan- guages can transformers express? a survey. Transactions of the Association for Computational Linguistics, 12:543-560 561, 05 2024.
[50] Kaiyue Wen, Huaqing Zhang. Hongzhou Lin, and Jingzhao Zhang. From sparse dependence to sparse attention: unveiling how chain-of tifinoof-thuggh enhances transformer sample efficiency. arXiv preprint arXiv:2410.. 00.55559. 2024.
[51] Juno Kim and Taiji Suzuki. Transformers provably solve parity efficiently with chain of thought, 2025.
14

---

[52] Guhao Feng, Bohang Zhang, Yuntian Gu, Haotian Ye, Di He, and Liwei Wang. Towards revealing the mystery behind chain of thought: A theoretical perspective, 2023.
[53] Eran Malach, Auto-regressive next-token predictors are universal learners, 2024.
[54] Zhiyuan Li, Hong Liu, Denny Zhou, and Tengyu Ma. Chain of thought empowers transformers to solve inherently serial problems. arXiv preprint arXiv:2402.12875, 2024.
[55] Franz Nowak, Anej Svete, Alexandra Butoi, and Ryan Cotterell. On the representational capacity of neural language models with chain-of-thought reasoning, 2025.
[56] Amrith Setlur, Nived Rajaraman, Sergey Levine, and Aviral Kumar. Scaling test-time compute without verification rl is suboptimal, 2025.
[57] Daman Arora and Andrea Zanette. Training language models to reason efficiently, 2025.
[58] Noam Levi, simple model of inference scaling laws. arXiv preprint arXiv:2410. 16377, 2024.
[59] Runze Liu, Junqi Gao, Jian Zhao, Kaiyan Zhang, Xiu Li, Biqing Qi, Wanli Ouyang. and Bowen Zhou, Can lb Ilm surpass 405b 1lm? rethinking compute-optimal test-time scaling, 2025.
[60] Andy Jones. Scaling scaling laws with board games. arXiv preprint arXiv:2104.03/ 2021.
[61] Celine Lee, Alexander M. Rush, and Keyon Vafa. Critical thinking: Which kinds of complexity govern optimal reasoning length?, 2025.
[62] Xingyu Chen, Jiahao Xu, Tian Liang, Zhiwei He, Jianhui Pang, Dian Yu, Linfeng Song, Qiuzhi Liu, Mengfei Zhou, Zhuosheng Zhang. Rui Wang, Zhaopeng Tu, Haitao Mi, and Dong Yu. Do not think that much for 2+3=? on the overthinking of ol-like 1lms, 2025.
[63] Sania Nayab, Giulio Rossolini, Marco Simoni, Andrea Saracino, Giorgio Buttazzo, Nicolamaria Manes, and Fabrizio Giacomelli. Concise thoughts: Impact output length on 11m reasoning and cost, 2025.
[64] Yao Fu, Hao Peng, Ashish Sabharwal, Peter Clark, and Tushar Khot. Complexity-basee prompting for multi-step reasoning, 2023.
[65] Mingyu Jin, Qinkai Yu, Dong Shu, Haiyan Zhao, Wenyue Hua, Yanda Meng, Yongfeng Zhang, and Mengnan Du. The impact of reasoning step length large language models, 2024.
[66] Yuyang Wu, Yifei Wang, Tianqi Du, Stefanie Jegelka, and Yisen Wang. When more is less: Understanding chain-of-thoughh length in llms, 2025.
[67] Kanishk Gandhi, Denise Lee, Gabriel Grand, Muxin Liu, Winson Cheng, Archit Sharma, and Noah D Goodman. Stream of search (sos): Learning to search in language. arXiv preprint arXiv:24044 4444400663,,, 2024.
[68] Lucas Lehnert, Sainbayar Sukhbaatar, DiJia Su, Qinqing Zheng, Paul Mevay, Michael Rabbat, and Yuandong Tian. Beyond a Better planning with transformers via search dynamics bootstrapping. 2024.
[69] Seungyong Moon, Bumsoo Park, and Hyun Oh Song. Guided stream of search: Learning to better search with language models via optimal path guidance, 2024.
[70] Bilgehan Sel, Ahmad Al-Tawaha, Vanshaj Khattar, Ruoxi Jia, and Ming Jin. Algorithm of thoughts: Enhancing exploration of ideas in large language models, 2024.
[71] Anikait Singh, Kushal Arora, Sedrick Keh, Jean Mercat, Tatsunori Hashimoto, Chelsea Finn, and Aviral Kumar. Improving the efficiency of test-time search in LLMs with backtracking, 2025.
[72] Aviral Kumar, Vincent Zhuang, Rishabh Agarwal, Su, John D Co-Reyes, Avi Singh, Kate Baumli, Shariq lqbal, Colton Bishop, Rebecca Roelofs, Lei M Zhang, Kay McKinney, Disha Shrivastava, Cosmin Paduraru, George Tucker, Doina Precup, Feryal Behbahani, and Aleksandra Faust. Training language models to self-correct via reinforcement learning, 2024.
15

---

[73] Yingqian Min, Zhipeng Chen, Jinhao Jiang. Jie Chen, Jia Deng, Yiwen Hu, Yiru Tang. Jiapeng Wang, Xiaoxue Cheng, Huatong Song, Wayne Xin Zhao, Zheng Liu, Zhongyuan Wang. and Ji-Rong Wen. Imitate, explore, and self-improve: A reproduction report on slow-thinking reasoning systems, 2024.
[74]
Chenxiao Yang, Nathan Srebro, David McAllester, and Zhiyuan Li. Pencil: Long thoughts with short memory, 2025.
[75] Violet Xiang, Charlie Snell, Kanishk Gandhi, Alon Albalak, Anikait Singh, Chase Blagden, Duy Phung, Rafael Rafailov, Nathan Lile, Dakota Mahan, Louis Castricato, Jan-Philipp Franken, Nick Haber, and Chelsea Finn. Towards system 2 reasoning in Ilms: Learning how think with meta chain-of-thought, 2025.
[76] Bill Yuchen Lin, Ronan Le Bras, Kyle Richardson, Ashish Sabharwal, Radha Poovendran, Peter Clark, and Yejin Choi. Zebralogic: On the scaling limits of Ilms for logical reasoning, 2025.
[77] Audrey Huang, Adam Block, Qinghua Liu, Nan Jiang, Akshay Krishnamurthy, and Dylan J. Foster. Is best-of-n the best of them? coverage, scaling, and optimality in inference-time alignment, 2025.
[78] Lingjiao Chen, Jared Quincy Davis, Boris Hanin, Peter Bailis, Ion Stoica, Matei Zaharia, and James Zou. Are more Ilm calls all you need? towards scaling laws of compound inference systems, 2024.
[79] Amrith Sethur, Chirag Nagpal, Adam Fisch, Xinyang Geng, Jacob Eisenstein, Rishabh Agarwal, Alekh Agarwal, Jonathan Berant, and Aviral Kumar. Rewarding progress: Scaling automated process verifiers for Ilm reasoning, 2024.
[80] Zhenyu Hou, Xin Lv, Rui Lu, Jiajie Zhang, Yujiang Li, Zijun Yao, Juanzi Li, Jie Tang, and Yuxiao Dong. Advancing language model reasoning through reinforcement learning and inference scaling. arXiv preprint arXiv:2501.1165/1 2025.
[81] Zeyu Jia, Alexander Rakhlin, and Tengyang Xie. Do we need to verify step by step? rethinking process supervision from a theoretical perspective, 2025.
16

---

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: All claims made in our paper are supported by theoretical proofs rigorous empirical evaluations.
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 of the work performed by the authors?
Answer: [Yes]
We discuss the limitations of our results in Section 6. Also, we make sure to verify our theoretical assumptions in the context of our claims through our experiments.
Justification:
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 a 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 (c.g.. independence assumptions, noiseless settings, model sell-speciiiatiinn 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 on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be 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 low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to 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 faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an 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
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
17

---

Answer: [Yes]
Justification: Our appendix contains complete and correct proofs for both of our theoretical results, Theorem and Theorem along with the required assumptions. We provide intuition in the main paper.
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 to 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 fully explain the experimental setup in Section 4, with the details needed to reproduce the results included in Appendix C.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be 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 to make their results reproducible or 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 is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.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-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 reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
18

---

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: [No]
Justification: We plan to release the code after the supplementary application deadline and prior to publication. However, we believe our experiments are easy to reproduce with the provided information.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips cc/
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not 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:
/ //nips... //nips.cc/pppppp wttpcccccpppccpeeeeeeeeeeeceeeee pppppppgguddesssssppeppppppppaiu cttpguuudd//ooeeuubiiiiiiiii
CooeeSummii issionni ssssssoliccy for more details.
The authors should provide instructions 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 is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Necessary details are described in Section 4. The full details available in Appendix C.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the of the paper to level of 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, or as 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 include error bars on all plots where it makes sense. We discuss the sample sizes involved in the experiments in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emror bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
19

---

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 of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
This is included in the experiments details section in Appendix C.
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 :tttpp::///eurr /ttp:///eeui..eeeeeee cc cc/public//eieececcceecceeeeeeee httppppll/ttiieelliiiippp wtw.hhhhhhcieeeeeeee
Answer: [Yes]
Justification: We read the code of ethics its entirety and strongly believe that our research abides by the stated code.
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 or 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: As it is more foundational work, we do not identify any direct societal impact attributed it.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
20

---

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), faimess 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 does not pose 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 to 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: The creators of the assests, such as the models used properly credited in the paper.
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.
21

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
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:
We do not introduce any new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/codeemoode 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 work does not involve crowdsourcing 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 work does involve crowdsoureing or 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.
22

---

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: LLMs are not used as an important, original, or non-standard component of our work.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy thttps://nett http://eeeeuieeeeee http://eeris.cco/ooeeeeeeeeeeeee /ttp://p./...ooo.eeeeee///////// for what should or should not be described.
23

---

A Separation between exponential and sequential scaling based on expressivity
We prove Theorem 4, which is the formal version of the Theorem stated in the main text.
A.1 Preliminaries: expressivity of transformers
Before stating the theorem formally and proving it, let us first review known technical bounds on the expressivity of limited- preeidddrriiioon, bounded-depe transformers [42, 43, 34]. To present these, must first define the computational model of threshold circuits.
Definition 5 (TC computational model). TC circuit is a boolean circuit with AND, OR, NOT, and MAJORITY gates of potentially unbounded fan-in. A TC circuit family is a collection of circuits indexed by the input size n, such that for each input size the circuit has polynomial width and bounded depth.
It has recently been shown that constant-depth transformers can be well-approximated by the class of threshold circuits of constant depth.
Proposition 1 (Transformers are in TC,; implied by Theorem 14 of [34]). For any bounded- depth sofimax-attention transformer T E' - R and any polynomial p(n), there is function T R in TC that approximates T to 2 p(n) additive error inputs of length n.!
This implies limitations on the expressive power of transformers, under standard computational complexity assumptions. In particular, is common conjecture that TC circuits are unable to determine s-f connectivity in undirected graphs [44, 45], and this conjecture normally stated as L TC 2, because L is a complete problem undirected graph connectivity [46, 47]. Therefore. Proposition provides evidence that bounded-depth and poly-size transformers (without chain of thought) are not able directly determine whether two nodes are connected in an inputted graph.
A.2 Our result
Proposition has not been shown to imply a tradeoff between parallel and sequential scaling in transformers, which is the new contribution Theorem proved in this section.
Given function T E" + R | operating on a polynomial alphabet of tokens Σ, and an input prompt th we inductively define the autoregressive distribution
(r)
formed by sampling n tokens autoregressively from the transformer. DT,0 is the empty string with probability 1. For any n 2 1, the distribution Dr, is the distribution of [ZI,..., žn] where [Z1,..., 2n-1] ~ DI and 2n softmax(T ([2; Z1y..., 2n-1)) I])).
We first prove that the distribution of outputs from a transformer is close in total variation to one generated by iteratively applying TC circuit.
Lemma 1 (Approximating the autoregressive distribution of a transformer). Given a transformer
T: E + E and polynomials pr (n), (2()), there is a function T in TC such that for all x E Σ"
dry (Dr Dr.m) S 2-
for any m S P2)),, where drv denotes the total variation distance between distributions.
Proof. Let p(n) be a polynomial that we will fix later. Let 7 be TC circuit family such that f approximates 7 up 2 p(x)) additive error on inputs of length as guaranteed by Proposition 1. For
The TC circuit outputs R returned up to some number bits precision.
For directed graphs, which we will not use here, the relevant conjecture is NL TC

---

m 0, we have drv (Dr,(()) ( = 0 by definition. For any string of length 2 n, we have
1 exp(T(s)):
exp({())))
drv (Dr,(),))), Dj,
Ejer cxp(T(s),) ΣJEr exp(T(s),)
ies
< exp( + 1)2 p(n) - exp(-((X)) + 1)2 P()))
- 5 + 1)2
whenever n is large enough and 2 2- (|Σ) + 1) v 1. So combining with the data-processing inequality, for any m 1, we have
drv (Dr,(()) (x))
S drv (Dr,m- (I)), Dr m-1 (x)) (o P2, =[))]
<dvv (Dr.m-1(x). D + 5([z) + 1)2-P(N).
Applying this inductively yields
( (x)) - 5m( 1)2 -Pn)
5p2 (n) Pin).
Choosing p(n) large enough so that the right-hand side is < 2 (n) concludes the proof.
This allows us to consider the autoregressive distributions generated by TC circuits, which we will find easier to analyze than the autoregressive distributions generated by transformers.
We observe that, for constant-length chains thought, the autoregressive distribution is also directly sampleable by TC circuit with no chain of thought. This lemma was effectively claimed in Figure 1 of [32], but without proof.
Lemma 2 (Constant-length) CoT simulated by randomized TC³). Let C' be constant number of steps, and let T Σ- IR Σ be function in TC Define the distribution of the last token P(x) to be the law of za where ~ (T.)
Then for any polynomial pi (n), there is polynomial p2(n) and function T (E) + in T such that for all EB we have
drv (Pv))(x); P(x)) S (m)))
where P(x) is the law of Tf; where Unif 1) (m)) are random input bits.
In other words, one step T approximates C autoregressive steps of
Proof. For any polynomial p(n). there is TC² circuit that (given polynomial number of random bits), samples from step of the autoregressive distribution with / up to total variation error 2 pp(()) This is because first the circuit by TC circuits, proved in Theorem 14 of [34]. Concatenating this circuit C' times, we obtain randomized TC" circuit 7' that satisfies the lemma, as long as we take p(n) 2 Pi (n) (1/C).. O
compute Л, and then the softmax operation can be approximated
Now recall the folklore result that TC circuits can be derandomized.
Lemma 3 (Derandomization of TC folklore). Let p(n.) and p'(n) be polynomials and T :EE
(0, 1))* + Σ be TC function.
Then, there is TC function ī E' + E such that for any any x E l and a E Σ, we have
)(x) if ( ((xrr) = a) > 1/2 1/2'1/
Proof. Let pi (n) be polynomial that we will fix later. Consider the circuit T that upon
input [z; Fi (n)] where E n and Ti {0, ()(m), takes majority vote over
25

---

"ir (a)))) By a Chernoff bound, and a large enough polynomial P1 (n), we have that for any x E" and r (0, 1 p)(()) we have
P Prit) (T (p))()) = d) 2 1 - if (0.1)_)) (0.. (7 = 2 (/p
By union bound over all inputs x E |- for any n there is random seed /ii...., (mj) such that
T T (1())) = o, if I (o- (T(;;) = o) 2 1/2 + (n)
For any x E E", let (xx) = T" (x; (m)) which is in TC since the seed can be hardcoded into the circuit and is of polynomial length.
The final ingredient a TC reduction from (s, conneeiity to (s, (a..)a))nnnctiitty Lemma 4. Suppose that the function f(G, s,t1,22 solving (s, (2)coeetico instances is in TC". Then TC LL
Proof. We will show that if f is in TC then (s, co-onnnccyyvty is also TC The reduction is as follows. Create (u, v1, connencicyyy problem (H, u, U1, 02) by letting H = Gi Li G2 be disjoint union of two copies of G. Randomly choose E (1, 2), and u be the copy of 8 in G,. Let vi be the copy of t in G1 and let 02 be the copy of t in G2. Also, permute the labels and the order of the edges by some permutation a that we will choose randomly. Finally, compute a = fHH u. U1 U2) and return true if v and false otherwise. There
cases:
If and are connected in G, then (H, 01, U2) is well-formed (u, )2) connectiivt problem, so fH, u, U1, 02) will always output Us and so the final answer is "true".
If and are not connected G, then over the randomness of the label and edge permutations the probability that returns v is exactly 1/2 (because the component in which v resides and the component which v2 resides are indistinguishable.
Finally, repeat this procedure in parallel with (nly different random permutations, and return "true" if the answer for all repetitions is "true", and "false" otherwise. By a union bound, over the set of possible inputs, there a deterministic choice of poly(n) permutations such that this procedure correct on any size-n input (G, s, t). This overall procedure can thus be implemented in TC by hard-coding those permutations into the circuit for any n.
Thus, we have shown a TC circuit for (s, -)-connectivity. Recall that (s, -oonneeety is complete for the class under TC reductions (see e.g. [44, 45]), so L C TC concluding the proof.
With these preliminaries, we arrive at Theorem 4, which is the formal statement of Theorem 1, which in the main text. We assume that there are two output tokens yes, Σ,, and the transformer's final token in the chain of thought is its response either yes or no.
Theorem 4, We have the following results for t1, (2.t1,t))-commentt ccomncctiivy problems of size n and trans- formers.
Sequential scaling succeeds: There is a constant 0 such that log pree-rreciinnn transformer with a CoT of length n" solves any (s, t1, (9,tt,t2)-coneeet connneeccivvy problem.
Parallel scaling fails: Assume that L & TC Let C2 > 0 be constants, and let T --- (2l be a caayoomial-precissioo of chains of thought over which we take majority vote (breaking ties arbitrarily). Then there are infinitely-many n such that there a size-n (s, t2, cconeecvcyy graph problem (G. (,,s,t1,ta) with answer ans E {yes, no), such that
transformer. Let m(n) == na be the number
P Palmatminn Dr. (G.,.)) (ee (m(())))).).))). = ans] < < 1/n.
Le., majority vote over m(n) parallel chains of thought with length C1 is correct with probability at most 1/2 + o(1).
26

---

Proof. For the positive result that sequential scaling succeeds, it is sufficient to use Corollary 2.1 of [32], which implies that log precision transformers with -In)-length chain of thought can simulate Turing machines that run in time I.)). Since (s, (1, (1,12)- fo)cconncty is solvable in polynomial time (e.g. with breadth-first search), the first part of the theorem follows.
For the negative result that parallel scaling fails, we use the lemmas that we have developed above. Suppose by contradiction that for large enough nt, we have for all size-n problems (G, 5, 12, ans) that
P. Fm Pr, (G.a.t Majority(s1, 2,(a), ans] 1/2 1/n.
Then by Lemma with precision 1/n, and by triangle inequality, there is TC function Í such that for all large enough and all size-n problems (G, 8, (i, l2, ans), we have
P Pm Dr c (G,s.f1.42) (aj.rity(21.,,.......... ( = ans] 2 1/2 + 2/n.
By Lemma again with precision 1/n, and by a triangle inequality, there is TC function 7 that approximates the uutoregressively-appleee î, in the sense that there is a polynomial p such that for any size-n problem (G, t 12 ans)
P Fr..... Emtt (()) Majority T(; ans] > 1/2 + 3/n.
Since Majority is a gate, the circuit (ajority(T(::))).... e (IF is TC function and so it be derandomized by Lemma 3. Using this lemma, yields TC" function 7 such that for any size-n problem (G, 8, (1, 12, ans),
TGG, 8, t2, = ans
Using Lemma 4, this implies S TC which contradicts our assumption that g TC
B Evidence from vertex query model for sequential vs. parallel scaling separation
B.1 Separation in vertex query model, Proof of Theorem 2
In the VQM, we can prove the necessity of a minimum number of queries (corresponding minimum length for a chain of thought by our simplifying abstraction that the VQM models the capabilities of transformers with bounded chain-of-thought)..
Theorem 5 (Minimum number of VQM queries needed for graph connectivity; restatement of Theorem 2). Consider the graph G given by two disjoint paths of length 2 3 with randomly permuted vertex IDs. Suppose s, t t2 are distinct endpoints of these paths such that and t, are the same path for exactly one E [1,2]. Then
Q(L) queries needed: For any VQM algorithm that executes (L- 2)/2 queries, the probability of correctness of the algorithun on (s,t1, 12) (e)-cnnnectiviry is exactly 1/2.
(L) queries sufficient: There is VQM algorithm that executes the t,, (2) problem with probability 1.
queries and solves
Proof. For the positive result, consider the algorithm that queries s, then the neighbor of s, and so on, until it reaches the other end of the path. This takes at most L - 1 queries, and reaches either i or tz. at which point the algorithm has enough information to return the correct answer.
For the analysis of the negative result, let N....., denote the ordered vertices of the first path and let u1..... UL denote the ordered vertices of the second path. Let the algorithm run and make < (L- - 2)/2 queries. By the pigeonhole principle there must be an i E {1....,Z L 1} such that the algorithm has not queried u, Vi, Ui+1 and Vi+1. Now note that if we additionally reveal the neighborhoods of u1,... Mi-1 Mi+2. .., Mr, and ....... Vi U2+2,... ... with vertex queries then the algorithm still has probability success 1/2, since equally likely given its information that is connected to u+1 as it is for 2s to be connected to 1/+1-
27

---

Paral lei Scaling Majonty Decision
Parallel Scaling of Best-ofN
1.0
0.9
Acoursay
0.8
0.7
0.0
Shortest-Pkt
Predisted Predicted Shortec-Falt
0.5
16
22
64
128
2
16
32
64
128
Number of Sampled Outouts
Number Sampled Outputs
Figure 7: (left) Majority decision and (right) Best-of-n accuracy for parallel scaling of models trained with CoT strategies for Bridge(3) (3) task, compared to the accuracy predicted by each CoT independently meeting the evidence criteria with the probability of DFS trace becoming the shortest path and a path respectively.
B.2 Proof of Theorem 3
Proof. First we will show the lower bound.
Without loss of generality, assume that the model will explore from 8, and stop when it reaches 4 or l2 (note that because the vertex labels are uniformly random, there is other way of getting higher than 50% success rate than finding & or t2 when starting from s).
To get from to tb. the algorithm must explore each intersection (those vertices with degree greater than two). To get from the current intersection to the next one, the algorithm has no way to distinguish between the long and short path until it explores at least I vertices, and there is at most a 1/2 chance the model takes oracle calls to get to the next intersection, and at least 1/2 chance it takes 21 oracle calls (if it takes the long path for 7 vertices, then any node it has discovered is still 1 vertices away from the next intersection, so it must make at least / more calls). Since there are d intersections", standard Chernoff bound for iid Bernoulli random variables shows that the probability of finding Ia in at most (1 5) 3 ld oracle calls is at most exp (- == 2d). and we don't find l. then the best the algorithm can do is guess, and get a 1/2 probability of being correct, yielding the desired result.
For the upper bound, we will consider this algorithm: each time we reach a new intersection (including the start), choose an unexplored neighbor, and explore down that path for I vertices, and if the next intersection is not found, try one of the other unexplored paths from before.
At new intersection, the algorithm has three unexplored paths:
The short path to the next intersection
2. The long path to the next intersection
3. The path to the previous intersection it didn't take
So, notice that the algorithm defined has 1/3 chance of taking 1 oracle calls to reach the next intersection, a 1/3 chance of taking 27, and 1 1/3 chance of taking 31. Using Hoeffdings inequality, the probability the algorithm takes more than (1 8)2ld oracle calls is at most exp( mmp(_, ), so the algorithm succeeds with at least one minus this probability.
C Experimental details and further experiments
C.1
Training
For each CoT strategy and task, train Mistral causal language model [36, 37] with 4 hidden layers, attention heads, and intermediate size 128 with a context length of 400 for 200 epochs on NVIDIA A100 GPU with 40GB memory. We sweep through the learning rate values in (le-4, 3e-4,
Including for which the same logic applies when getting from to the next intersection.
28

---

Accuracy Across Sequential Scales
Accuracy
Token Budgets
0.9
0.9
Batt of Accurscy
0.8
0.8
Greedy
Best-of-2
Bezt
Best-of-2
Best of-4
Best.of-3
0.6
Best-of-a
0.6
Best-of4
Best-of-5
0.5
Best-of-32 32
0.5
Best-of-6
15
20
25
30
35
40
45
50
25
50
75
1000
125
150
175
200
Sequential Scale
Total CoT Talknn Budget
Figure 8: Best-of-N accuracy for parallel scaling of the model trained with DFS CoT strategy on Bridge(5) (5) task (left) across sequential scales (maximum CoT length) and (right) total CoT token budget. Outputs are sampled with temperature 1.0 for parallel scaling.
1e-3, 3e-3] and train the model for 200 epochs with batch size 1000. We have also experimented with different weight decay values and learning
schedules, but we found significant difference in the results and used 0.05 weight decay and a cosine learning rate schedule, with a 0.1 warm-up ratio. We use the same hyperparameters for RL iterations, except that fine-tune the model for 20 epochs at each iteration. Each pretraining experiment takes under 12 GPU hours, while fine-tuning for RL takes under 3 GPU hours. Additionally, debugging and hyperparameter tuning for each experiment took under 72 GPU hours.
C.2 Sequential scaling walk strategies
Experiment setup To study sequential scaling of CoTs in controlled setting, we also ran experi- ments with CoT strategy with tunable scale. A Walk-L CoT is generated by sampling a random visiting the target node within at most L steps.
walk that starts the source node, conditioned Hence, models trained with Walk-L strategies at different scales L are exposed to successful traces of random walk the task, but with different number of steps the walk allowed take reach the target. As I. increases, the CoT's become longer, less optimal, and more exploratory.
Sequential Scaling of RL Iterations of Path Model on Bridge(3)
1.0
Path
0.9
Path RL-1
0.8
Path RL-2
Evidence Accuracy
0.7
Path RL-3
Path RL-4
0.6
Longest Path
0.5
0.4
0.3
0.2
0.1
0.0
10
26
50
66
Sequential Scale
Figure 9: Evidence accuracy of Path model before and after RL iterations with different sequential CoT budgets on the Bridge (3) task. Error bars represent 95% binomial confidence intervals.
29

---

Devo/Geel Bt-eee-----i----eeeeeeee 1-0we-122
Qum11-178
2.0
<3-32h
16
Furde
86
16
86
1228
Setuertel
Sequertea
Figure 10: A comparison of parallel and sequential scaling for three LLMs tested the (s, t2)) connectivity problem for a graph that the disjoint union of two paths. Note the similar trend to Figure I.
Results After training models for the Bridge (5) task with Walk-L CoT strategies, we find that the accuracy of the models consistently increases with L, which shows that the models trained more exploratory and longer walks perform better (See Figure 14).
C.3 Experiment with a smaller transformer
Experiment setup We also ran experiments using smaller transformer models with hidden layers, and variant of DFS strategy called DFS-BT. In CoT of DFS-BT strategy, include the whole DFS trace, which is walk in the DFS tree including the backtracking steps.
Results We find that small models trained on DFS-BT CoTs solve the task consistently, while small models trained on DFS CoT's fail to solve the Bridge tasks of larger depths (See Figure 13), which be explained by the smaller model's more limited expressivity.
C.4 LLM experimental details
For the AIME2024 experiment, we used H200 GPUs. Each run took approximately 1.5 hours, for total of about 24 H200 GPU-hours. For the graph connectivity experiment, we used vllm and 2 A 100 GPUs (80 GB of memory each) for inference. The experiments make each plot took less than four hours each. Debugging and hyperparameter tuning took under 120 GPU hours. We constructed 32 random labelings of the bridge graph, and then, using prompts of the form Figure 12, create CoTs of 4096 tokens. Depending the model, we added the appropriate special tokens to make the input prompt from the user, and make the model use thinking mode during the COT. Each model recommended using temperature 0.6 for thinking, which we did. We used custom logit processor to make the model substitute the end thinking token and the eos token with the token for "wait", inspired by [7]. Then we truncate the CoT at intervals evenly spaced by tokens, and append the end of thinking token, and "Answer: Node [start node label] in the same connected component as node before using the model to find the logits for the next token. The model is considered correct if the logit for the correct node is higher than the logit for the incorrect node introduced in the initial prompt'. For parallel scaling,
generated up to 64 distinct CoTs for each graph, and analytically calculated the probability that a random subsample would vote for the correct or incorrect solution (or tic). All of the results have standard deviation of most 0.08.
C.5 LLM additional experiments
In Figure 10 also tested the LLMs setting closer the setting of Theorem 2, where the graph to be explored is two disjoint paths, and we once again confirm the theory, and see similar trends to those Figure 1.
'With some tie breaking when the logits are within 1e-8 8 of each other. We found that techniques weighting the confidence by the magnitude of the logits their difference did not significantly change any results.
30

---

Parallel and Sequential Scaling of S1-32B on AIME 2024
0.6
Parallel Scale (maj@k)
32
0.4
Accuracy
8-
0.3
0.2
2-
0.1
1-
0.5K
Sequential Scale (token budget)
Figure 11: A comparison of parallel and sequential scaling for s1-32B [7] AIME2024 [35]. For
parallel scaling, answers are sampled with temperature 1.0 and aggregated by majority vote.
D Further discussion
While we make an effort to find the best models for graph connectivity with chain-of of-thought (See Figure 4) our experiments, we not have guarantee that these are indeed the best models that deploy chain of thought. In future work, this could be addressed by studying models learned with RL, with penalty on the length of the chain of thought, encourage more optimal use of the sequential scaling budget.
Additionally, the Vertex Query Model that we propose to abstract the power of chain-of-the totouughttthhttttt in Section 3.2 is motivated by the globality barrier studied in [28], and is empirically validated, but does not have direct theoretical backing. An interesting future direction to prove that deuthed-depth transformers on graph connectivity tasks are indeed effectively restricted by this model.
E Further related work
Expressivity of transformers with CoT The representational power of transformers has been studied in several works [31, 24, 33, 48, 49]. Recent work also highlights the expressivity and sample efficiency gains of reasoning with chain-of-thoughts [50, 51, 52, 53, 32, 54, 55]. In particular, many studies use graph-based tasks testbed for studying multi-step reasoning with CoTs [28, 30, 27].
Test-time scaling Extensive work focused on scaling inference- difrrence-time compute optimally [12, 1, 56, 57], search of inference-time scaling laws [2, 58, 59, 60]. A line of work has focused on studying optimal sequential scaling [7, 21, 61, 62] by examining the role of CoT length [63, 64, 65, 66). The benefits of learning to search [67, 68, 69, 70] and problem-solving strategies like backtracking and self-correction [71, 19, 72] by scaling the CoT length have also been demonstrated [73, 74, 75], as well as the limits of these approaches [76, 14]. Another line of work has studied parallel scaling [15, 13]
Prompt format
Given the folloving list undiracted edgan graph (vith nodez labeled 0 through 33), in node 0 in the same component 10 as 27? (it is connected to exactly one of the tuo) Think step step.
(2, 3) (5, 6), 17), (10, 11). (3, 4), (31, 32), (18, 19), (19, 33), (30, 31), (20. 21), (2, 9), (24, 25).
(23,
(6, 7), (25, 17),
(e, 10), (2, 16),
(15, 16), (12, 13), (7, 8), (19, 20) (1, 2). (32, 53), (29, 50), (14, 15), (28. 29). (1, 0), (8.
0), (21, 22), (19, 26), (22, 23). (26, 27)
Figure 12: Example prompt from the LLM experiments. The prompt includes basic instructions for the task, along with the recommendation to think step by step (to avoid the model responding immediately with guess, and then spending the rest of the chain of thought trying to justify it).
31

---

Accuracy Bridge(5)
Accuracy Small Model Bridge(
1.0
Evidence Accuracy
1.0
Evidence Accuracy
Decision Accuracy
Decision Accuracy
0.8
0.8
0.6
Accuraol
0.5
Path
Shortesk-Path
DF5-0T
DF5
Path Shortest Path
Figure 13: Decision and evidence accuracy of (left) models trained CoT strategies for Bridge (5) task, and (right) models with 2 hidden layers trained on CoT strategies, including DFS-BT and DFS, for Bridge (5) task. Error bars represent 95% binomial confidence intervals.
Accuracy on Bridge(5)
1.0
Evidence Acturacy
Decision
Acc.rac
0.0
DPS
Whll-to
Wi k--
Walk-30
Walle25
Wwik-20
Path
Shortest-Path
Figure 14: Decision and evidence accuracy of models trained on Walk CoT strategies for Bridge (5) task. Error bars represent 95% binomial confidence intervals.
by examining the behavior of majority voting or a best-of-n method over diverse set of responses generated in parallel [77, 78]. Finally, the role of reinforcement learning [79, 80, 81] in advaneing reasoning by improving the CoT quality and scaling it naturally [6, 20, 22, 39, 40] has been explored.
32


Reviews:
[{"review_id": "7Pu63I7LJc", "reviewer": "Reviewer_Lhpt", "summary": "This paper explores the trade-off between sequential and parallel scaling of inference-time computation for reasoning tasks using Large Language Models (LLMs). It demonstrates theoretically and empirically that sequential scaling—achieved through long chains of thought (CoT)—can offer an exponential advantage over parallel scaling, such as majority voting or best-of-n sampling over multiple short CoTs. The task used is a graph connectivity problem inspired by complexity theory and graph reasoning literature, specifically focusing on structured \"bridge graphs\" designed to challenge multi-step reasoning.\n\nThe theoretical analysis introduces two key contributions:\n1.\tBounded-depth transformers with polynomial-length CoT can solve the connectivity problem efficiently.\n2.\tAggregating over polynomially many O(1)-length CoTs cannot achieve similar performance.", "questions": "- Would hybrid methods (e.g., iterative refinement of CoTs) narrow the gap?\n- Do other architectures (e.g., recurrent reasoning models, O3) exhibit similar limitations?", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths\n- The empirical section is comprehensive. The bridge graph dataset is carefully constructed to stress-test sequential reasoning abilities. The evaluation includes ablation studies across CoT lengths, architectures (from scratch-trained Mistral variants to frontier models), and aggregation methods.\n- Section 5’s exploration of reinforcement learning-induced growth in CoT length supports both theoretical findings and prior observations in frontier models. This strengthens the relevance and applicability of the results to real-world settings.\n- The use of synthetic \"bridge graphs\" allows precise control over the difficulty of reasoning via increasing depth, offering a reproducible benchmark for future multi-step reasoning research.\n\nWeaknesses\n- While the theoretical analysis centers around a specific formal reasoning problem (graph connectivity), its generalization to other types of reasoning remains speculative.  For instance, [1, 2, 3] have explored various graph problems and given a good example for this paper to follow, which should be cited in this paper.\n- Theoretical guarantees rely on unproven complexity-theoretic assumptions (TC⁰ ≠ L).\n- Empirical evaluation uses small transformers (e.g., 4 layers); implications for massive LLMs are underexplored.\n- The paper neglects to cite Can Language Models Solve Graph Problems in Natural Language?[2], which demonstrates that the sequential order of graph descriptions (e.g., BFS vs. DFS vs. PageRank-based orderings) significantly impacts LLM performance on graph reasoning tasks.\n\n\n[1] Can Language Models Solve Graph Problems in Natural Language?\n[2] Can Graph Descriptive Order Affect Solving Graph Problems with LLMs?\n[3] Talk like a Graph: Encoding Graphs for Large Language Models", "was_revised": true, "final_justification": "I have read the authors response. I would keep my score as boarderline accept.", "rebuttal": "Thank you for your thoughtful comments, additional references, and questions which suggest interesting future directions. We are glad that you found our empirical section comprehensive and our carefully constructed bridge graphs suitable as a reproducible benchmark for future multi-step reasoning research. Below we address your concerns.\n\n> While the theoretical analysis centers around a specific formal reasoning problem (graph connectivity), its generalization to other types of reasoning remains speculative.\n\nOur goal in this paper is to make a general and fundamental claim about tradeoffs between parallel and sequential scaling. Our understanding of these tradeoffs is at its infancy. Multiple papers in the literature have seemingly contradictory claims: some show large benefits from sequential scaling [1], while other papers claim that parallel scaling alone is sufficient [2].\n\nOur goal is to add clarity to the literature, by providing a controllable and analyzable task in which sequential scaling (theoretically & empirically) cannot be efficiently replaced by parallel scaling. Thus, our results yield the general conclusion that the parallel scaling recipes of papers such as [2, 3] cannot work for all types of problems.\n\nFurthermore, we propose the graph connectivity task because it is very natural and captures multi-step reasoning ability, which seems to be a key aspect of more complex reasoning tasks such as math problems. Reasoning on graphs has been considered in the literature as an ideal abstraction of complex reasoning tasks (see [4,5,6,7] for examples), which also isolates the reasoning ability from memorization. Motivated by that, we have designed the bridge graph connectivity task, to capture key aspects of multi-step reasoning. \n\nTo be clear, our claim is not that sequential scaling is always better than parallel scaling for all tasks. Rather, it is that there is a natural class of tasks where it is (empirically and theoretically) better. **We are the first to formally show such a gap for transformers in a natural setting that is a building block for more advanced multi-step reasoning tasks.** This is a conceptual contribution that we believe is helpful for thinking about more complex tasks. We will edit the introduction and abstract to be more clear on this point so as to avoid confusion.\n\nFinally, we have run some evaluations of s1 [1] on GPQA Diamond, and compared sequential and parallel scaling in that setting (we cannot include any plots due to the removal of the option to share a pdf). These experiments show sequential vs. parallel tradeoffs qualitatively similar to our experiments on the graph connectivity task. As argued above, we believe that these experiments are not core to our message and that the paper stands on its own without them. Nevertheless, we will include these experiments in the camera ready paper, since they support our claim that graph connectivity is a helpful benchmark to consider.\n\n> For instance, [1, 2, 3] have explored various graph problems and given a good example for this paper to follow, which should be cited in this paper.\n\nThank you for providing these references, which provide empirical studies of LLMs on graph reasoning benchmarks. They complement our theoretical and empirical analyses very nicely, and we will cite and discuss them thoroughly in the final version of our paper.\n\n> Theoretical guarantees rely on unproven complexity-theoretic assumptions ($\\textrm{TC}^0 \\neq \\textrm{L}$).\n\nThe assumption that $\\textrm{TC}^0 \\neq \\textrm{L}$ is a standard assumption (see [8,9]) commonly held by complexity theorists (similarly to the conjecture that $\\textrm{P} \\neq \\textrm{NP}$). We explicitly mention this assumption whenever we use it, and also have theoretical results (see Theorem 1) that do not rely on this assumption.\n\n> Empirical evaluation uses small transformers (e.g., 4 layers); implications for massive LLMs are underexplored.\n\nWe have accompanied our from-scratch trained experiments with small transformers with empirical evaluation on massive LLMs, discussed briefly in section 4.5, with results mostly in figures 1b, 5, and 8 (in the appendix). Specifically, we looked at three separate 32 billion parameter models, and tested the limits of parallel and sequential compute in our setting on these models. We will make sure to edit our abstract to make it more clear that the “large reasoning models” (line 12) we refer to are indeed LLMs. This important component of our results may not have been emphasized enough, so we will add more discussion about the LLM experiments, and emphasize it earlier on.\n\n> The paper neglects to cite Can Language Models Solve Graph Problems in Natural Language?[2], which demonstrates that the sequential order of graph descriptions significantly impacts LLM performance on graph reasoning tasks.\n\nThanks for the reference! We will cite this paper in the camera-ready.\n\n> Would hybrid methods (e.g., iterative refinement of CoTs) narrow the gap?\n\nThis is a very interesting question, which is definitely worthy of future research. With a variety of bottlenecks determining the efficiency of parallel and sequential computation in practice, it would not be surprising at all if hybrid methods could outperform both of the simple strategies discussed in the paper.\nWe do conjecture that any hybrid method that involves generating and $O(1)$ number of $O(1)$-length chains of thought for $O(1)$ rounds would fail at our graph reasoning tasks – the proof would rely on similar ideas to what we use for Theorem 1, but we would have to check the details more carefully before claiming such a statement.\n\n> Do other architectures (e.g., recurrent reasoning models, O3) exhibit similar limitations?\n\nThe State-Space Model (SSM) architecture was also shown to be in $\\textrm{TC}^0$ [10], so our first theorem on theoretical results on limitations of sequential scaling also applies to it. We will add a note of this in the paper, thank you for your suggestion! We can only speculate on the architecture in proprietary models such as O3, but it is possible that it is a transformer, or hybrid between transformer and SSM, in which case these results should also still apply. \n\nThank you again for your careful reading of the paper and thoughtful suggestions. We hope that we have addressed your questions sufficiently.\n\n[1] Muennighoff, Niklas, et al. \"s1: Simple test-time scaling.\" arXiv preprint arXiv:2501.19393 (2025).\n\n[2] Ma, Wenjie, et al. \"Reasoning models can be effective without thinking.\" arXiv preprint arXiv:2504.09858 (2025).\n\n[3] Brown, Bradley, et al. \"Large language monkeys: Scaling inference compute with repeated sampling.\" arXiv preprint arXiv:2407.21787 (2024).\n\n[4] Abbe, Emmanuel, et al. \"How far can transformers reason? the globality barrier and inductive scratchpad.\" Advances in Neural Information Processing Systems 37 (2024): 27850-27895.\n\n[5] Sanford, Clayton, et al. \"Understanding transformer reasoning capabilities via graph algorithms.\" Advances in Neural Information Processing Systems 37 (2024): 78320-78370.\n\n[6] Xu, Keyulu, et al. \"What can neural networks reason about?.\" arXiv preprint arXiv:1905.13211 (2019).\n\n[7] Kim, Juno, et al. \"Metastable dynamics of chain-of-thought reasoning: Provable benefits of search, rl and distillation.\" arXiv preprint arXiv:2502.01694 (2025).\n\n[8] Feng, Guhao, et al. \"Towards revealing the mystery behind chain of thought: a theoretical perspective.\" Advances in Neural Information Processing Systems 36 (2023): 70757-70798.\n\n[9] Merrill, William, and Ashish Sabharwal. \"The expressive power of transformers with chain of thought.\" arXiv preprint arXiv:2310.07923 (2023).\n\n[10] William Merrill, Jackson Petty, and Ashish Sabharwal. “The Illusion of State in State-Space Models”. ICML 2024."}, {"review_id": "hW4z8js3mm", "reviewer": "Reviewer_WjKT", "summary": "This paper focuses on inference-time computation and compares parallel scaling and sequential scaling to quantify the trade-offs between the two for reasoning tasks. The authors study the graph connectivity task and provide both theoretical analysis and empirical evidence to demonstrate that sequential scaling outperforms parallel scaling.", "questions": "1. The paper needs a more detailed analysis of why sequential scaling performs better than parallel scaling. For example, does longer generated text in sequential scaling contain more diverse or richer information, whereas parallel generation may suffer from repetition across outputs? Providing concrete examples or case studies would help readers intuitively understand the issue.\n2. More details about the training and evaluation data are needed—especially the nature of the context provided and the size of the test set.\n3. What specific strategy is employed to ensure that longer chains of thought are meaningful and not simply verbose or noisy?\n4. What is the comparison in actual time cost between sequential and parallel scaling under a fixed token budget?\n5. Does model size affect the performance gap between sequential and parallel scaling?", "limitations": "yes", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths：\n1. The paper clearly defines the problem of graph connectivity, investigates it thoroughly, and supports its claims with both theoretical analysis and empirical evidence, demonstrating that sequential scaling outperforms parallel scaling.\n2. The integration of reinforcement learning into the analysis adds technical depth and contributes to the novelty of the work.\n3. The paper is well-organized, with a logical and coherent structure that enhances clarity and readability.\n\nWeakness：\n1. The graph connectivity task is inherently sequential in nature. Could the observed performance gains be simply due to this sequential characteristic? In other words, is the task biased in favor of sequential scaling, and does that limit the generality of the conclusion?\n2. How does the proposed approach perform on other reasoning tasks, such as mathematical problem solving, which may involve different forms of reasoning?\n3. Since the paper focuses primarily on the graph connectivity task, it may be helpful to clarify this focus more explicitly in the title or abstract, to better manage reader expectations and highlight the scope of the study.", "was_revised": true, "final_justification": "The author's responses provide clarifications. While some of my concerns are resolved, I still concern about the novelty of the technique, as well as some experimental details. I will therefore maintain my original evaluation.", "rebuttal": "Thank you for your detailed response and thoughtful comments. We are glad that you found our paper well-organized and coherent, providing both theoretical analysis and empirical evidence that support our claims. Below we address your concerns.\n\n> The graph connectivity task is inherently sequential in nature. Could the observed performance gains be simply due to this sequential characteristic? In other words, is the task biased in favor of sequential scaling, and does that limit the generality of the conclusion?\n\nOur understanding of the tradeoffs between parallel and sequential scaling is at its infancy. Multiple papers in the literature have seemingly contradictory claims: some show large benefits from sequential scaling [1], while other papers claim that parallel scaling alone is sufficient [2].\n\nOur goal is to add clarity to the literature, by providing a task in which sequential scaling (theoretically & empirically) cannot be efficiently replaced by parallel scaling. Thus, **our results yield the general conclusion that the parallel scaling recipes of papers such as [2, 3] cannot work for all types of problems.** We propose the graph connectivity task because it is very natural and captures multi-step reasoning ability.\n\nTo be clear, our claim is not that sequential scaling is always better than parallel scaling for all tasks. Rather, it is that there is a natural class of tasks where it is (empirically and theoretically) better – and this class of tasks seems to capture key aspects of multi-step reasoning. We will edit the introduction and abstract to be more clear on this point so as to avoid confusion.\n\nFinally, we have run some evaluations of s1 [1] on GPQA Diamond, and compared sequential and parallel scaling in that setting (we cannot include any plots due to the removal of the option to share a pdf). These experiments show sequential vs. parallel tradeoffs qualitatively similar to our experiments on the graph connectivity task. As argued above, we believe that these experiments are not core to our message and that the paper stands on its own without them. Nevertheless, we will include these experiments in the camera ready paper, since they support our claim that graph connectivity is a helpful benchmark to consider.\n\n> How does the proposed approach perform on other reasoning tasks, such as mathematical problem solving, which may involve different forms of reasoning?\n\nOur paper’s goal is to improve our theoretical understanding of CoT scaling, instead of proposing a new approach. We are motivated by the empirical literature around sequential and parallel scaling [1, 2] and understanding the fundamental tradeoff between them for more complex tasks such as mathematical problem solving.\nWe agree that different specific tasks may have different tradeoffs and we do not claim that sequential scaling is always better than parallel scaling (see our response to the question above). Our study shows the non-trivial necessity of sequential scaling for a general multi-step reasoning problem, both theoretically (based on expressivity results), and empirically (through comprehensive controlled experiments). **We are the first to formally show such a gap for transformers in a natural setting that is a building block for more advanced multi-step reasoning tasks.** This is a conceptual contribution that we believe is helpful for thinking about more complex tasks.\n\n> It may be helpful to clarify the focus on the graph connectivity task more explicitly in the title or abstract.\n\nWe have mentioned in the abstract that our paper demonstrates the existence of settings where sequential scaling is necessary based on graph connectivity problems, but we will emphasize it more in the revision. \n\n> The paper needs a more detailed analysis of why sequential scaling performs better than parallel scaling. For example, does longer generated text in sequential scaling contain more diverse or richer information, whereas parallel generation may suffer from repetition across outputs? \n\nThank you for the helpful recommendation. We provide a theoretical explanation in the submission’s Lines 161-165: A limited depth model can only check connectivity for (relatively) nearby vertices, so to find the correct path it has to explore mostly “blind” until it stumbles upon the solution. In Lines 245-258, we corroborate this explanation by investigating how models trained on short CoT behave: the model has the same rate of success as if it were exploring blindly.\n\nYour comment helped us see that this is hard to follow because our theoretical arguments and empirical corroboration are in separate sections. We will unite these two paragraphs in the revision and add more detail to make it easier to understand.\n\n\n> More details about the training and evaluation data, the nature of the context provided and the size of the test set.\n\nFor the from-scratch training experiment, we include the details in sections 4.1, 4.2, and 4.3. An example prompt is in Figure 2. The test set size is 5,000, thanks for pointing out, it will be added to help supplement the already provided confidence intervals. For the LLM experiments, all of the details are in C.4, including an example prompt (Figure 10), size of the test set, and details of the CoT context length. For full transparency of our experiments and to aid with reproducing our results, our code was included in the supplementary details.\n\n> What specific strategy is employed to ensure that longer chains of thought are meaningful and not simply verbose or noisy?\n\nFor experiments on pretrained reasoning LLMs, the accuracy improves with sequential scale. For experiments on transformers trained from scratch, our training data consists of longer chains of thought.\n\nFor evaluation in the from-scratch training experiments, in addition to our decision criterion which checks the final result, we have an evidence criterion which verifies whether the chain-of-thought generated by the model contains a valid trace as a solution. We report the evidence accuracy metric based on this criterion to make sure the chains of thought are meaningful. \n\n> What is the comparison in actual time cost between sequential and parallel scaling under a fixed token budget?\n\nIn practice, this depends on the specific implementations, hardware constraints, and the setting. To make a fair comparison, one would have to optimize both techniques separately. That being said, we would be happy to add wallclock time comparisons for our experiments to the camera ready version of the paper.\nTheoretically, sequential scaling should be quadratic in the CoT budget (in the limit), while parallel should be linear. Since we show an exponential gap, this means that sequential scaling will always be favored in the limit. \n\n> Does model size affect the performance gap between sequential and parallel scaling?\n\nOur experiments with small transformers and LLMs show that the overall trends look similar across vastly different scales (though since there are a lot of other differences between the experiments, we would caution against quantitative take-aways). Theoretically, for any constant depth model, there will always be an exponential gap, but for deeper models, they are expressive enough to do more in one step, and so may need less sequential scaling.\n\nThank you again for your careful reading of the paper and thoughtful suggestions. We hope that we have addressed your questions sufficiently.\n\n[1] Muennighoff, Niklas, et al. \"s1: Simple test-time scaling.\" arXiv preprint arXiv:2501.19393 (2025).\n\n[2] Ma, Wenjie, et al. \"Reasoning models can be effective without thinking.\" arXiv preprint arXiv:2504.09858 (2025).\n\n[3] Brown, Bradley, et al. \"Large language monkeys: Scaling inference compute with repeated sampling.\" arXiv preprint arXiv:2407.21787 (2024).\n\n[4] Abbe, Emmanuel, et al. \"How far can transformers reason? the globality barrier and inductive scratchpad.\" Advances in Neural Information Processing Systems 37 (2024): 27850-27895.\n\n[5] Sanford, Clayton, et al. \"Understanding transformer reasoning capabilities via graph algorithms.\" Advances in Neural Information Processing Systems 37 (2024): 78320-78370.\n\n[6] Xu, Keyulu, et al. \"What can neural networks reason about?.\" arXiv preprint arXiv:1905.13211 (2019).\n\n[7] Kim, Juno, et al. \"Metastable dynamics of chain-of-thought reasoning: Provable benefits of search, rl and distillation.\" arXiv preprint arXiv:2502.01694 (2025)."}, {"review_id": "MkKPzNqfUb", "reviewer": "Reviewer_GJ4H", "summary": "This paper investigates the fundamental tradeoff between sequential scaling (longer chains of thought) and parallel scaling (multiple short chains with aggregation) in large language model reasoning. The authors demonstrate through both theoretical analysis and empirical validation that sequential scaling can offer exponential advantages over parallel scaling on graph connectivity problems. They introduce a \"bridge graph\" task based on graph connectivity and show that small decreases in sequential scale require large increases in parallel scale to maintain performance.", "questions": "Overall, this paper makes solid theoretical and empirical contributions to an important problem in current LLM research. However, the limited scope to graph connectivity problems and reliance on unproven complexity-theoretic assumptions prevent it from being a clear accept. The work provides valuable insights into inference-time scaling but needs broader validation to have significant impact.  If the authors can adequately address the concerns raised in the Limitations/Weaknesses part, I would be willing to increase my score.\n\n\n**Additional Questions**\n\n1. Limited Empirical Experiment Scope: Though adapting the theoretical analysis could be tough, the authors can easily conduct empirical analysis on sequential scaling and parallel scaling for other LLM reasoning tasks. This will help to better validate the effectiveness of the authors claims in more diverse settings.", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strengths and Contributions**\n\n1.\tNovel theoretical framework: The paper provides rigorous theoretical analysis using transformer expressivity limitations on graph reasoning tasks.\n\n2.\tSufficient empirical validation: Various models are assessed and consistently validate the theoretical predictions. \n\n3.\tPractical insights: The work addresses a fundamental question in inference-time scaling that is highly relevant to current LLM development.\n\n**Limitations / Weaknesses**\n\n1.\tLimited scope of tasks: The results are demonstrated only on graph connectivity problems. While the authors acknowledge this limitation, it's unclear how broadly these findings generalize to other reasoning domains. \n\n2.\tNoisy Empirical Results: In some plots of empirical results, including the right plot of Figure 1 and the two plots in Figure 5, the results are not visibly exponential. The curve type of the sequential-parallel tradeoff needs to be further determined. \n\n3.\tLimited exploration of hybrid approaches: The paper focuses primarily on pure sequential vs. pure parallel scaling, with less investigation of optimal combinations of both approaches.", "was_revised": true, "final_justification": "The authors have addressed my concerns, so I am inclined to raise my score.", "rebuttal": "Thank you for your thoughtful comments and helpful feedback! We are glad that you found our theoretical framework and its empirical validation novel and solid to address the fundamental tradeoffs in inference-time scaling and giving practical insights. \n\n> The results are demonstrated only on graph connectivity problems. While the authors acknowledge this limitation, it's unclear how broadly these findings generalize to other reasoning domains\n\nOur goal in this paper is to make a general and fundamental claim about tradeoffs between parallel and sequential scaling. Our understanding of these tradeoffs is at its infancy. Multiple papers in the literature have seemingly contradictory claims: some show large benefits from sequential scaling [1], while other papers claim that parallel scaling alone is sufficient [2].\n\nOur goal is to add clarity to the literature, by providing a controllable and analyzable task in which sequential scaling (theoretically & empirically) cannot be efficiently replaced by parallel scaling. Thus, our results yield the general conclusion that the parallel scaling recipes of papers such as [2, 3] cannot work for all types of problems.\n\nFurthermore, we propose the graph connectivity task because it is very natural and captures multi-step reasoning ability, which seems to be a key aspect of more complex reasoning tasks such as math problems. Reasoning on graphs has been considered in the literature as an ideal abstraction of complex reasoning tasks (see [4,5,6,7] for examples), which also isolates the reasoning ability from memorization. Motivated by that, we have designed the bridge graph connectivity task, to capture key aspects of multi-step reasoning. \n\nTo be clear, our claim is not that sequential scaling is always better than parallel scaling for all tasks. Rather, it is that there is a natural class of tasks where it is (empirically and theoretically) better. We are the first to formally show such a gap for transformers in a natural setting that is a building block for more advanced multi-step reasoning tasks. This is a conceptual contribution that we believe is helpful for thinking about more complex tasks. We will edit the introduction and abstract to be more clear on this point so as to avoid confusion.\n\n\n\nFinally, we have run some evaluations of s1 [1] on GPQA Diamond, and compared sequential and parallel scaling in that setting (we cannot include any plots due to the removal of the option to share a pdf). These experiments show sequential vs. parallel tradeoffs qualitatively similar to our experiments on the graph connectivity task. As argued above, we believe that these experiments are not core to our message and that the paper stands on its own without them. Nevertheless, we will include these experiments in the camera ready paper, since they support our claim that graph connectivity is a helpful benchmark to consider.\n\n>  In some plots of empirical results, including the right plot of Figure 1 and the two plots in Figure 5, the results are not visibly exponential.\n\nOur results only show that the tradeoff is at *least* exponential. In those plots, the contours of equal loss appear to possibly grow faster than exponential, so do not contradict our results. It is not too surprising that the LLM experiments don’t perfectly match the smaller scale ones, since LLMs are not trained on this specific task, so will spend tokens figuring out what solution they will try, and won’t make assumptions about the structure of the graph and therefore are likely to attempt suboptimal solutions. We will make sure to add more discussion and concrete examples of this observation to the paper.\n\n> The paper focuses primarily on pure sequential vs. pure parallel scaling, with less investigation of optimal combinations of both approaches.\n\nWe have done a grid search over combinations of sequential and parallel scaling (see Figures 1 and 5), showing how different combinations perform. In practice, the optimal tradeoff depends on the specific implementations, hardware constraints, and the setting. We believe that future works can use this work as a foundation to investigate the optimal combinations for specific settings. \n\n> Reliance on unproven complexity-theoretic assumptions.\n\nThe assumption that $\\textrm{TC}^0 \\neq \\textrm{L}$ is a standard assumption (see [8,9]) commonly held by complexity theorists (similarly to the conjecture that $\\textrm{P} \\neq \\textrm{NP}$). We explicitly mention this assumption whenever we use it, and also have theoretical results (see Theorem 1) that do not rely on this assumption.\n\nThank you again for your careful reading of the paper and thoughtful suggestions. We hope that we have addressed your questions sufficiently.\n\n[1] Muennighoff, Niklas, et al. \"s1: Simple test-time scaling.\" arXiv preprint arXiv:2501.19393 (2025).\n\n[2] Ma, Wenjie, et al. \"Reasoning models can be effective without thinking.\" arXiv preprint arXiv:2504.09858 (2025).\n\n[3] Brown, Bradley, et al. \"Large language monkeys: Scaling inference compute with repeated sampling.\" arXiv preprint arXiv:2407.21787 (2024).\n\n[4] Abbe, Emmanuel, et al. \"How far can transformers reason? the globality barrier and inductive scratchpad.\" Advances in Neural Information Processing Systems 37 (2024): 27850-27895.\n\n[5] Sanford, Clayton, et al. \"Understanding transformer reasoning capabilities via graph algorithms.\" Advances in Neural Information Processing Systems 37 (2024): 78320-78370.\n\n[6] Xu, Keyulu, et al. \"What can neural networks reason about?.\" arXiv preprint arXiv:1905.13211 (2019).\n\n[7] Kim, Juno, et al. \"Metastable dynamics of chain-of-thought reasoning: Provable benefits of search, rl and distillation.\" arXiv preprint arXiv:2502.01694 (2025).\n\n[8] Feng, Guhao, et al. \"Towards revealing the mystery behind chain of thought: a theoretical perspective.\" Advances in Neural Information Processing Systems 36 (2023): 70757-70798.\n\n[9] Merrill, William, and Ashish Sabharwal. \"The expressive power of transformers with chain of thought.\" arXiv preprint arXiv:2310.07923 (2023)."}, {"review_id": "b2VoXLqPzI", "reviewer": "Reviewer_2f9M", "summary": "This paper investigates how to optimally allocate computational resources during reasoning tasks. Through both theoretical analysis and empirical experiments, the authors demonstrate that sequential scaling (e.g., using longer Chain-of-Thought, or CoT) can offer exponential advantages over parallel scaling (e.g., majority voting or best-of-N strategies) in certain graph connectivity problems. \nThe main contribution of the work is the introduction of a reasoning task where slightly reducing the sequential budget requires a significant increase in the parallel budget to maintain the same level of accuracy.\nThe authors also explore the behavior of transformers trained with reinforcement learning (RL) on this task, observing that the length of the generated CoT increases gradually during training.", "questions": "See Weaknesses", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\n+ The paper not only presents a theoretical analysis of the differences between sequential and parallel scaling in reasoning tasks but also validates these predictions through experiments.\n+ The authors design a graph connectivity-based reasoning task that is both challenging and capable of simulating multi-step reasoning, offering an ideal testbed for studying the relative advantages of sequential scaling.\n\n**Weaknesses**\n\n+ This paper **mainly focuses on a graph connectivity task,** which is relatively simple and may not reflect the complexity of real-world reasoning scenarios. I believe deeper analysis should be conducted on more complex reasoning domains such as mathematical problem-solving (e.g., Math, AIME) or code generation (e.g. LivecodeBench) to better validate the generalizability of the findings.\n\n+ The claim that reinforcement learning leads to an increase in CoT length is questionable. In practical reasoning-enhancement training settings, such as those involving mathematics or coding, they often use supervised fine-tuning to extend the length of reasoning chains first, followed by RL to achieve distribution shifts. In this process, RL does not necessarily result in longer CoTs.\n\n+ The vertex query model abstracts graph access via an oracle $N_G$, limiting algorithms to querying only the neighbors of specific vertices. While useful for theoretical analysis, this abstraction may overlook the complex interactions and capabilities of models when processing graph-structured data.\n\n+ The paper **mainly introduced an observed phenomenon**—that increasing the model’s generation length significantly boosts reasoning performance. However, similar conclusions have been reported in the previous paper. For instance, methods such as process reward modeling or MCTS for parallel scaling are being increasingly abandoned due to high noise, with recent trends focusing instead on extending the length of reasoning chains with RL. \n\n+ In addition, I recommend that the paper should propose a new solution under specific scenarios, that is, **how to balance sequential and parallel scaling under constrained inference resources**. Addressing these points with concrete experiments would not only enhance the robustness of the findings but also increase the overall impact of the work.", "was_revised": true, "final_justification": "The authors have addressed most of my concerns. So I decide to raise my score to 4.", "rebuttal": "Thank you for the constructive feedback and thoughtful comments. We are glad that you found our graph connectivity task an ideal testbed for theoretical study of the tradeoffs between sequential and parallel scaling for reasoning models and validating it through controlled experiments. Below we address your concerns.\n\n> This paper mainly focuses on a graph connectivity task, which is relatively simple and may not reflect the complexity of real-world reasoning scenarios. \n\nOur goal in this paper is to make a general and fundamental claim about tradeoffs between parallel and sequential scaling. Our understanding of these tradeoffs is at its infancy. Multiple papers in the literature have seemingly contradictory claims: some show large benefits from sequential scaling [1], while other papers claim that parallel scaling alone is sufficient [2].\n\nOur goal is to add clarity to the literature, by providing a controllable and analyzable task in which sequential scaling (theoretically & empirically) cannot be efficiently replaced by parallel scaling. Thus, our results yield the general conclusion that the parallel scaling recipes of papers such as [2, 3] cannot work for all types of problems.\n\nFurthermore, we propose the graph connectivity task because it is very natural and captures multi-step reasoning ability, which seems to be a key aspect of more complex reasoning tasks such as math problems. Reasoning on graphs has been considered in the literature as an ideal abstraction of complex reasoning tasks (see [4,5,6,7] for examples), which also isolates the reasoning ability from memorization. Motivated by that, we have designed the bridge graph connectivity task, to capture key aspects of multi-step reasoning. \n\nTo be clear, our claim is not that sequential scaling is always better than parallel scaling for all tasks. Rather, it is that there is a natural class of tasks where it is (empirically and theoretically) better. **We are the first to formally show such a gap for transformers in a natural setting that is a building block for more advanced multi-step reasoning tasks.** This is a conceptual contribution that we believe is helpful for thinking about more complex tasks. We will edit the introduction and abstract to be more clear on this point so as to avoid confusion.\n\n\n\n> I believe deeper analysis should be conducted on more complex reasoning domains such as mathematical problem-solving (e.g., Math, AIME) or code generation (e.g. LivecodeBench) to better validate the generalizability of the findings.\n\nWe have run some evaluations of s1 [1] on GPQA Diamond, and compared sequential and parallel scaling in that setting (we cannot include any plots due to the removal of the option to share a pdf). These experiments show sequential vs. parallel tradeoffs qualitatively similar to our experiments on the graph connectivity task. As argued above, we believe that these experiments are not core to our message and that the paper stands on its own without them. Nevertheless, we will include these experiments in the camera ready paper, since they support our claim that graph connectivity is a helpful benchmark to consider.\n\n> The paper mainly introduced an observed phenomenon—that increasing the model’s generation length significantly boosts reasoning performance.\n\nIt is indeed known that increasing sequential scale can improve performance, see e.g. [1]. However, this is not the point of our paper. \n\nInstead, our paper studies the tradeoff between parallel and sequential scaling, which is much less understood. Some works argue that parallel scaling alone is enough to get very good performance [2, 3]. Our paper demonstrates that a tradeoff exists between parallel scaling and sequential scaling for a certain natural class of graph connectivity tasks. Thus, our paper pushes back against [2, 3], showcasing a simple setting where parallel scaling alone is not enough.\n\n\n> The claim that reinforcement learning leads to an increase in CoT length is questionable. \n\nWe agree that RL is not the only way to enable long CoT reasoning in practice and supervised fine-tuning first was the standard approach prior to the release of DeepSeek-R1 [8, 9]. However, DeepSeek-R1-Zero [10] and its replications [11, 12] showed that even scaling up RL on a base model without supervised fine-tuning can lead to increase in the model's CoT length and accuracy (see Figures 2 and 3 in [10], as well as Figure 1 and Section 4 in [11]). Our study gives one plausible explanation for this phenomena from an expressivity lens of view, demonstrating a clear example of how RL can improve model's accuracy by reinforcing long CoTs the model is expressive enough to compute. \n\n> The vertex query model abstracts graph access via an oracle, limiting algorithms to querying only the neighbors of specific vertices. While useful for theoretical analysis, this abstraction may overlook the complex interactions and capabilities of models when processing graph-structured data.\n\nThe vertex query model is an abstraction that we empirically certify works extremely well in our from-scratch training experiments (see Figure 4). If transformers had significantly more capabilities in this setting, one would expect them to be able to correctly learn the shortest path, but empirically the model can’t learn it non-trivially better than the vertex query model would suggest. Additionally, the results implied by the vertex query model hold well even with our LLM experiments.\nThe results with the vertex query model are complementary to Theorem 1 (which does not use the vertex query model). Theorem 1 tells us that the separation qualitatively holds, and the Vertex Query model allows us to get a much more fine-grained result in the setting of graph connectivity (albeit with more assumptions).\n\n> The paper should propose a new solution under specific scenarios, that is, how to balance sequential and parallel scaling under constrained inference resources.\n\nWe have done a grid search over combinations of sequential and parallel scaling (see Figures 1 and 5), showing how different combinations perform. In practice, the optimal tradeoff depends on the specific implementations, hardware constraints, and the setting. To make a fair comparison, one would have to optimize both techniques separately. That being said, we would be happy to add wallclock time comparisons for our experiments to the camera ready version of the paper.\nTheoretically, sequential scaling should be quadratic (with transformer architecture) in the CoT budget, while parallel should be linear. Since we show an exponential gap, this means that sequential scaling will always be favored in the limit. \nWe are identifying a natural setting where sequential scaling can not be efficiently replaced by parallel scaling, however different specific settings can have different tradeoffs, and in such settings the optimal balance would be different. We believe that future works can use this work as a foundation to investigate the optimal tradeoff for specific settings, constrained to specific computational resources.\n\nThank you again for your careful reading of the paper and thoughtful suggestions. We hope that we have addressed your questions sufficiently.\n\n[1] Muennighoff, Niklas, et al. \"s1: Simple test-time scaling.\" arXiv preprint arXiv:2501.19393 (2025).\n\n[2] Ma, Wenjie, et al. \"Reasoning models can be effective without thinking.\" arXiv preprint arXiv:2504.09858 (2025).\n\n[3] Brown, Bradley, et al. \"Large language monkeys: Scaling inference compute with repeated sampling.\" arXiv preprint arXiv:2407.21787 (2024).\n\n[4] Abbe, Emmanuel, et al. \"How far can transformers reason? the globality barrier and inductive scratchpad.\" Advances in Neural Information Processing Systems 37 (2024): 27850-27895.\n\n[5] Sanford, Clayton, et al. \"Understanding transformer reasoning capabilities via graph algorithms.\" Advances in Neural Information Processing Systems 37 (2024): 78320-78370.\n\n[6] Xu, Keyulu, et al. \"What can neural networks reason about?.\" arXiv preprint arXiv:1905.13211 (2019).\n\n[7] Kim, Juno, et al. \"Metastable dynamics of chain-of-thought reasoning: Provable benefits of search, rl and distillation.\" arXiv preprint arXiv:2502.01694 (2025).\n\n[8] \"Demystifying Long Chain-of-Thought Reasoning in LLMs\", Yeo et al. 2025\n\n[9] \"Kimi k1.5: Scaling Reinforcement Learning with LLMs\", Kimi Team 2025\n\n[10] \"DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning\", DeepSeek-AI 2025\n\n[11] \"SimpleRL-Zoo: Investigating and Taming Zero Reinforcement Learning for Open Base Models in the Wild\", Zeng et al. 2025\n\n[12] \"TinyZero\", Pan et al. 2025"}]

Author rebuttal:

Meta-review: This paper studies the question of sequential vs parallel inference time scaling for a graph connectivity task. At a high level, the paper shows that while sequentially scaling with one polynomial-length CoT can solve the connectivity problem, parallel scaling by aggregating over polynomially-many O(1) CoT fails. The reviews are mostly positive. The reviewers agree that this is an fundamental problem to study given the importance of inference time scaling. While there were minor concerns about the scope of the theoretical analysis and novelty, I think it is useful for the broader community to know about these results. I recommend acceptance of the paper.
Decision: Accept (poster)