Let Me Think! A Long Chain of Thought Can Be Worth Exponentially Many Short Ones

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.

This paper mainly focuses on a graph connectivity task, which is relatively simple and may not reflect the complexity of real-world reasoning scenarios.

Our 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].

Our 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.

Furthermore, 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.

To 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.

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.

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.

The paper mainly introduced an observed phenomenon—that increasing the model’s generation length significantly boosts reasoning performance.

It is indeed known that increasing sequential scale can improve performance, see e.g. [1]. However, this is not the point of our paper.

Instead, 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.

The claim that reinforcement learning leads to an increase in CoT length is questionable.

We 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.

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.

The 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. The 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).

The paper should propose a new solution under specific scenarios, that is, how to balance sequential and parallel scaling under constrained inference resources.

We 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. Theoretically, 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. We 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.

Thank you again for your careful reading of the paper and thoughtful suggestions. We hope that we have addressed your questions sufficiently.

[1] Muennighoff, Niklas, et al. "s1: Simple test-time scaling." arXiv preprint arXiv:2501.19393 (2025).

[2] Ma, Wenjie, et al. "Reasoning models can be effective without thinking." arXiv preprint arXiv:2504.09858 (2025).

[3] Brown, Bradley, et al. "Large language monkeys: Scaling inference compute with repeated sampling." arXiv preprint arXiv:2407.21787 (2024).

[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.

[5] Sanford, Clayton, et al. "Understanding transformer reasoning capabilities via graph algorithms." Advances in Neural Information Processing Systems 37 (2024): 78320-78370.

[6] Xu, Keyulu, et al. "What can neural networks reason about?." arXiv preprint arXiv:1905.13211 (2019).

[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).

[8] "Demystifying Long Chain-of-Thought Reasoning in LLMs", Yeo et al. 2025

[9] "Kimi k1.5: Scaling Reinforcement Learning with LLMs", Kimi Team 2025

[10] "DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning", DeepSeek-AI 2025

[11] "SimpleRL-Zoo: Investigating and Taming Zero Reinforcement Learning for Open Base Models in the Wild", Zeng et al. 2025

[12] "TinyZero", Pan et al. 2025

Thank you for your response. Considering that you do not conduct experiments on many common real-world reasoning scenarios (i.e. AIME 24, AIME 25), we think that this paper has limitations. So I decide to maintain my score.

Dear Reviewer 2f9M, Perhaps you did not see our "Official comment" since we posted it as a response to all reviewers. We have pasted its contents below here so that you can more easily see it. The experiments that we have run on AIME support our theoretical results.

--

In response to the reviewers’ feedback, we conducted additional experiments with the s1‑32B model [1] on AIME‑2024. For parallel scaling, we sample with temperature 1.0 and aggregate by majority vote over final answers. For sequential scaling, we limit the model’s thinking‑token budget and force a final answer once the limit is reached. In the ‘wait’ variant [1], we ignore the model’s first output and append the ‘wait’ token to induce further reasoning before the final answer. The experiments used ≈24 H200 GPU‑hours. Since PDF attachments are not supported here, we present the results in the table below.

The results show that sequential scaling can not be efficiently replaced by parallel scaling for this mathematical task, supporting the generalizability of our findings to real-world scenarios. 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, and challenge claims from other works [2] that it can be entirely replaced by parallel scaling.

To further examine this observation, we break down the results by individual question (out of the 30 total). The table below reports the number of correct responses out of 64 attempts for each question.

One notable takeaway is that there exist questions (e.g. 1, 10, 25) for which parallel scaling at low token budgets will never succeed, but a single shot with a higher token budget is very likely to succeed. This shows the necessity of sequential scaling for achieving the highest possible score on this task. We hope this further clarifies the generalizability of the insights offered by our work.

[1] Muennighoff, Niklas, et al. "s1: Simple test-time scaling." arXiv preprint arXiv:2501.19393 (2025).

[2] Ma, Wenjie, et al. "Reasoning models can be effective without thinking." arXiv preprint arXiv:2504.09858 (2025).

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.

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

Our 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].

Our 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.

Furthermore, 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.

To 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.

Finally, 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.

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.

Our 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.

The paper focuses primarily on pure sequential vs. pure parallel scaling, with less investigation of optimal combinations of both approaches.

We 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.

Reliance on unproven complexity-theoretic assumptions.

The 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.

Thank you again for your careful reading of the paper and thoughtful suggestions. We hope that we have addressed your questions sufficiently.

[1] Muennighoff, Niklas, et al. "s1: Simple test-time scaling." arXiv preprint arXiv:2501.19393 (2025).

[2] Ma, Wenjie, et al. "Reasoning models can be effective without thinking." arXiv preprint arXiv:2504.09858 (2025).

[3] Brown, Bradley, et al. "Large language monkeys: Scaling inference compute with repeated sampling." arXiv preprint arXiv:2407.21787 (2024).

[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.

[5] Sanford, Clayton, et al. "Understanding transformer reasoning capabilities via graph algorithms." Advances in Neural Information Processing Systems 37 (2024): 78320-78370.

[6] Xu, Keyulu, et al. "What can neural networks reason about?." arXiv preprint arXiv:1905.13211 (2019).

[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).

[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.

[9] Merrill, William, and Ashish Sabharwal. "The expressive power of transformers with chain of thought." arXiv preprint arXiv:2310.07923 (2023).

Thank you for your valuable feedback. To further assess the generalizability of our conclusions to more complex reasoning tasks, such as mathematical reasoning, we conducted additional experiments on AIME-2024 and posted the results as an official comment. We are also running experiments with other models, such as Qwen3-32B, and other mathematical tasks, such as MATH-500 for the camera-ready version, to make the empirical study more comprehensive, and further clarify the generalizability of the insights offered by our work.

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.

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?

Our 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].

Our 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.

To 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.

Finally, 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.

How does the proposed approach perform on other reasoning tasks, such as mathematical problem solving, which may involve different forms of reasoning?

Our 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. We 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.

It may be helpful to clarify the focus on the graph connectivity task more explicitly in the title or abstract.

We 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.

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?

Thank 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.

Your 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.

More details about the training and evaluation data, the nature of the context provided and the size of the test set.

For 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.

What specific strategy is employed to ensure that longer chains of thought are meaningful and not simply verbose or noisy?

For 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.

For 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.

What is the comparison in actual time cost between sequential and parallel scaling under a fixed token budget?

In 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. Theoretically, 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.

Does model size affect the performance gap between sequential and parallel scaling?

Our 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.

Thank you again for your careful reading of the paper and thoughtful suggestions. We hope that we have addressed your questions sufficiently.

[1] Muennighoff, Niklas, et al. "s1: Simple test-time scaling." arXiv preprint arXiv:2501.19393 (2025).

[2] Ma, Wenjie, et al. "Reasoning models can be effective without thinking." arXiv preprint arXiv:2504.09858 (2025).

[3] Brown, Bradley, et al. "Large language monkeys: Scaling inference compute with repeated sampling." arXiv preprint arXiv:2407.21787 (2024).

[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.

[5] Sanford, Clayton, et al. "Understanding transformer reasoning capabilities via graph algorithms." Advances in Neural Information Processing Systems 37 (2024): 78320-78370.

[6] Xu, Keyulu, et al. "What can neural networks reason about?." arXiv preprint arXiv:1905.13211 (2019).

[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).

We hope our review addressed your concerns to your satisfaction, sufficiently for you to consider raising your score! We are happy to hear any remaining concerns, confusions, or feedback about the paper.

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.

While the theoretical analysis centers around a specific formal reasoning problem (graph connectivity), its generalization to other types of reasoning remains speculative.

Our 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].

Our 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.

Furthermore, 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.

To 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.

Finally, 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.

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.

Thank 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.

Theoretical guarantees rely on unproven complexity-theoretic assumptions ($\textrm{TC}^0 \neq \textrm{L}$).

The 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.

Empirical evaluation uses small transformers (e.g., 4 layers); implications for massive LLMs are underexplored.

We 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.

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.

Thanks for the reference! We will cite this paper in the camera-ready.

Would hybrid methods (e.g., iterative refinement of CoTs) narrow the gap?

This 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. We 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.

Do other architectures (e.g., recurrent reasoning models, O3) exhibit similar limitations?

The 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.

Thank you again for your careful reading of the paper and thoughtful suggestions. We hope that we have addressed your questions sufficiently.

[1] Muennighoff, Niklas, et al. "s1: Simple test-time scaling." arXiv preprint arXiv:2501.19393 (2025).

[2] Ma, Wenjie, et al. "Reasoning models can be effective without thinking." arXiv preprint arXiv:2504.09858 (2025).

[3] Brown, Bradley, et al. "Large language monkeys: Scaling inference compute with repeated sampling." arXiv preprint arXiv:2407.21787 (2024).

[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.

[5] Sanford, Clayton, et al. "Understanding transformer reasoning capabilities via graph algorithms." Advances in Neural Information Processing Systems 37 (2024): 78320-78370.

[6] Xu, Keyulu, et al. "What can neural networks reason about?." arXiv preprint arXiv:1905.13211 (2019).

[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).

[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.

[9] Merrill, William, and Ashish Sabharwal. "The expressive power of transformers with chain of thought." arXiv preprint arXiv:2310.07923 (2023).

[10] William Merrill, Jackson Petty, and Ashish Sabharwal. “The Illusion of State in State-Space Models”. ICML 2024.

We hope our review addressed your concerns to your satisfaction, sufficiently for you to consider raising your score! We are happy to hear any remaining concerns, confusions, or feedback about the paper.