On the Bias of Next-Token Predictors Toward Systematically Inefficient Reasoning: A Shortest-Path Case Study

We thank the reviewer for their constructive feedback. We are pleased that they found our research novel and interesting, the paper clearly written, and the experimental setup sound. Below we address their concerns in detail.

Weaknesses

We agree that exploring the applicability of our findings to real-world LLMs is a compelling direction. We chose not to fine-tune pretrained models for this study due to several challenges: 1) Lack of control over pretraining data: pretrained models may have been exposed to similar algorithmic problems, introducing confounding factors and biases toward particular solutions (DP algorithm in this case, since it is optimal for this problem); 2) such models have their own tokenizer which necessarily differs from ours; 3) the fine-tuning process would be quite expensive on a large model considering that our models necessitate a rather large training corpus (roughly 250K training traces) to learn the task syntax and generalize reasonably.

To overcome at least the latter limitation, few shot learning could be a possible alternative. However, considering the diversity of the graphs in the dataset, various examples per graph depth need to be incorporated in the context. Given that the average length for a $\eta=-5$(DFS) example with graph depth 7 is 1228, and 849 for depth 6, the context length utilized by the few-shots grows fast. This may give rise to various issues as information retrieval and understanding is known to get harder as the size of the context increases.

In our work, we decided to contribute to the research line established by recent works (Lehnert et al. (2024), Su et al. (2025), Bachmann et al. (2024)) employing algorithmic tasks to train transformers from scratch to elucidate some fundamental properties of these models. Exploring non-DP algorithmic tasks is certainly a valuable direction that we intend to explore in the future. However, extending our framework to novel algorithmic problems is not immediate as it would require the design of brand-new tokenizers and corresponding metrics to assess the quality of the trained models, and a new recipe for controlling the trace efficiency. In the spirit of a proof-of-concept, the choice of our tasks was driven by the necessity to identify a framework that was well-aligned with the research question we intended to probe, i.e. the controlled exploration of the dependency of next-token-predictors on the structure and efficiency of CoT traces.

Questions

• We acknowledge that the clarity of the list of reasoning types can be improved. Following the reviewer’s suggestion, we have modified our manuscript to make the link between the $\eta$ parameter and the corresponding algorithmic strategy clearer and more explicit from the beginning of the paper.
• We apologise to the reviewer for the confusion. As can be observed from Fig 2(b), $\eta=0$ training traces are longer on average than those for $\eta=+5$(DP). Nevertheless, the model trained with $\eta=+5$(DP) outperforms the one trained with $\eta=0$ traces, thus allowing us to conclude that “more test-time compute –here the length of the trace– does not necessarily imply better test performance”. We are going to rephrase it to improve clarity.

On the limitations

We acknowledge that training from scratch differs from inference-time manipulation of pretrained models. While we briefly mention this, we will expand the discussion to emphasize the potential implications of this difference.

We thank the reviewer for the time spent reading and reviewing our manuscript. We remain available to further discuss any remaining questions/doubts the reviewer may have.

References

• Lehnert, Lucas, et al. "Beyond a*: Better planning with transformers via search dynamics bootstrapping." arXiv preprint arXiv:2402.14083 (2024).
• Su, DiJia, et al. "Dualformer: Controllable fast and slow thinking by learning with randomized reasoning traces." arXiv preprint arXiv:2410.09918 (2024).
• Bachmann, Gregor, and Vaishnavh Nagarajan. "The pitfalls of next-token prediction." arXiv preprint arXiv:2403.06963 (2024).

We thank the reviewer for their valuable feedback. We are glad they found our experimental testbed clean and controllable and that the paper has been judged well-written and original. In the following, we address the reviewer’s concerns.

Weaknesses

We emphasize that our work is a focused case-study, and we acknowledge its limitations in terms of generality (see Limitations, section 6). The choice of our experimental setting was mainly motivated by our quest for better understanding how relatively simple transformers develop their reasoning process, and which traces such models ultimately privilege. To probe these research questions, we designed an ad-hoc tokenizer and introduced a tunable parameter $\eta$ allowing us to carefully control the level of efficiency and redundancy of the reasoning traces. The proposed setting is intentionally kept as simple as possible to focus on the above research questions and factor out eventual confounding effects stemming from complex tasks’ syntax (e.g. math) and eventual biases and leakages inherited from the pretraining of large models.
Our work fits within the research line established by several recent works studying how transformers behave when tasked to learn and reproduce specific well-known algorithmic routines as proxies of reasoning traces (Lehnert et al. (2024) and Su et al. (2025), Bachmann (2024)). Our results align with these works in terms of the usefulness of learning to produce intermediate reasoning steps as opposed to tasking the model to directly solving the task without any CoT. In addition to that, our specialized setting allows us to investigate how the structure of the CoTs influences performance, an aspect that was not explored in detail in prior works.
We agree with the reviewer that extending our framework to other (non-DP) tasks represent an interesting research direction. However, such an extension is not immediate as it would require finding similar mechanisms to control the efficiency of the trace and it would necessitate the development of a brand-new tokenizer and synthetic data generator along with specialized metrics to evaluate the models’ quality. For the sake of clarity, we decided to focus on a single task as we believe it nicely encapsulates all the properties we needed to probe. Regarding the model size, we selected a minimal working configuration, as is common in many similar studies. Given the training context length, we focused on graphs for which all types of algorithmic traces would fall within the token limit, and then on a model size sufficient to observe good generalization with the Q-CoT-A approach, but not in the Q-A approach. In essence, we chose the smallest model that still allowed the key phenomena to be clearly observed while keeping the experiments lightweight. Nonetheless we trained models as big as 235M parameters using both Phi3 and GPT2 architectures (see answer to Question 2 below for more details) with no substantial dependency on the architectural details in terms of the final results. While no testing has been performed on models with billions of parameters, it can be observed, from reasoning-oriented LLMs such as Deepseek-R1, that even at these large sizes LLMs typically exhibit highly inefficient reasoning traces. This observation was one of the main motivations of our study, i.e. characterizing the relationship between next-token-predictors and the efficiency of the traces they are trained on.

Questions

1. The core motivation of our work is to investigate how the structure and efficiency of reasoning traces influence learning dynamics in next-token prediction. To isolate these factors, we chose a task that offers precise and continuous control over trace efficiency through a single tunable parameter ($\eta$). This level of control is difficult to replicate in natural language or math benchmarks, where answer formats tend to be standardized and optimized for clarity—often featuring a single, highly efficient solution per question. In such domains, generating multiple semantically equivalent but structurally different reasoning traces (with varying efficiency levels) at scale would require significant manual effort or sophisticated paraphrasing/generation pipelines, which may introduce confounds such as semantic drift or unnatural phrasing. Similarly, algorithmic tasks beyond shortest paths (and where DP is not applicable) would require careful task selection and potentially the development of new tokenizers and evaluation metrics to enable comparable experimental control, as well as a new recipe for controlling the trace efficiency. That said, we agree that extending the study to additional algorithmic domains or natural language settings would be a valuable next step. We see this as a promising direction for future work and believe that our methodology could help inspire ways to structure and probe reasoning traces in more complex environments.
2. We thank the reviewer for their question. Yes, we ran experiments comparing $\eta=-5$ (less efficient traces) and $\eta=+5$ (more efficient traces) across different model sizes and graph complexities. We observed that as model capacity increases relative to task difficulty (e.g., larger models on simpler graphs), both models eventually achieve 100% test accuracy. However, models trained with $\eta=−5$ consistently converge faster than their $\eta=+5$ counterparts across the board. Our hypothesis is that the layer-by-layer exploration (of the more efficient traces $\eta=+5$) induces a higher degeneracy in the exploration order and requires a more flexible internal circuit tasked to identify the partial path to be continued, since the relative positions of different path continuations are less predictable. To your question about whether there's a point where inefficient traces stop being optimal: in our experiments, we did not find a reversal where more efficient traces became better even in terms of convergence speed. However, at higher capacities both trace types eventually perform equally well at convergence. We believe investigating whether a crossover point, where efficiency becomes favourable exists, is an interesting direction for future work.
3. We also find the jump very intriguing! We have confirmed this behaviour on more runs per experiment, increasing the number of seeds from 3 to 5. Our current smallest model has 3 layers, 12 heads and ~28M parameters. Our plans for future work is to reduce the size of the model further to facilitate mechanistic interpretability and see if some circuits emerge right after the loss transition point.

We sincerely thank the reviewer for the time spent reading our paper. We would be happy to further discuss any remaining concerns and would be grateful if the reviewer would consider adjusting their score should our responses satisfactorily resolve their questions.

References

• Lehnert, Lucas, et al. "Beyond a*: Better planning with transformers via search dynamics bootstrapping." arXiv preprint arXiv:2402.14083 (2024).
• Su, DiJia, et al. "Dualformer: Controllable fast and slow thinking by learning with randomized reasoning traces." arXiv preprint arXiv:2410.09918 (2024).
• Bachmann, Gregor, and Vaishnavh Nagarajan. "The pitfalls of next-token prediction." arXiv preprint arXiv:2403.06963 (2024).

We thank the reviewer for the provided feedback. We are glad to hear that the originality of our approach has been appreciated and that our framework offers a valuable setup to generate CoT data for controlled experimental analysis. In the following we address the points raised by the reviewer.

Weaknesses

1. Multiple definitions of reasoning exist, as there is no universally accepted technical definition. We believe our task (finding the shortest path in a graph) falls within the scope of reasoning. When a transformer is given a structured description of a layered graph and asked to identify the shortest path, it must: (i) integrate information across layers and develop a high-level strategy to solve the task (ii) simulate a traversal process akin to DFS or dynamic programming, gradually building up the path leading to the final answer and involving the solution of intermediate subtasks (iii) compare and evaluate alternative paths. These requirements would be commonly associated with reasoning tasks in the community. We also point out that using algorithmic traces to model reasoning in transformers represents a strategy adopted by other recent works in the community (Lehnert et al. (2024) and Su et al. (2025), Bachmann (2024)). Our framework introduces multiple possible algorithmic reasoning strategies to solve the considered task and studies which one of them is more aligned with the inductive bias of transformers, hence providing insights into the mechanisms behind the development of CoTs in such models.
2. We agree that different coverage between $\eta=+5$ and $\eta=-5$ could have undermined our findings. However, in section B2 in the supplementary material we show that $\eta=+5$ (DP) has actually more coverage than $\eta=-5$ (DFS), as the former setting implies learning fewer additions and the associated sample length distribution is more concentrated compared to $\eta=-5$ (DFS). This should, in principle, give the $\eta=+5$ (DP) approach an advantage in terms of learnability. In addition, when the two approaches are compared at a fixed token budget, $\eta=+5$ (DP) has more training samples than $\eta=-5$ (DFS), as the former is generally characterized by shorter CoTs. Nevertheless, the DFS trace setting consistently demonstrates better generalization. We will make sure to better highlight these points in the main body of the revised version of the paper.

Questions

1. Graphs are generated by sampling uniformly the number of layers and nodes in each layer. For every possible edge between two nodes in consecutive layers, the edge is added to the graph with a probability $p$ and its cost is sampled uniformly. We point the reviewer to section A2 of the supplementary material for more details on the graph generation. A lower bound estimate of the number of unique graphs possible in our setting is $5^{180}$. As such, we don’t believe node-connectivity can be robustly used in our setting to solve the task. In addition, graph generation is independent on the $\eta$ parameter, hence the different generalization performance shown across $\eta$ values are comparable and $\eta=-5$ (i.e. DFS-like traces) emerges as a clear winner.
2. We emphasize that our work is a focused case-study and we acknowledge its limitations in terms of generality (see Limitations, section 6). Nevertheless, our work fits into a recent research line aimed at studying reasoning in language models in controlled settings where training data can be programmatically generated and the performance of the model easily assessed. Some of our results are aligned with the findings of other works (e.g., Lehnert et al., 2024; Su et al., 2025), such as the importance of intermediate reasoning steps as opposed to directly predicting the answer, hence providing further evidence to existing research. Besides this, our setting allows us to introduce an additional degree of freedom which is the efficiency (and, indirectly, the length) of the reasoning trace (modulated via the parameter $\eta$). This element of novelty introduced by our setup is not trivial to incorporate in other non-DP settings. Furthermore, we note that extending our analysis to other tasks would require non-trivial changes to the framework (e.g. a novel ad-hoc tokenizer and efficiency knob) hence incurring in the risk of reducing clarity. Finally, existing benchmarks and publicly available datasets do not have the same degree of controllability as our synthetic setup. In addition, they are typically intended for fine-tuning pre-trained LLMs or for use in a few-shot setting. Since such models have been exposed to vast and opaque pre-training corpora, we cannot rule out the possibility that algorithmic strategies such as dynamic programming were already internalized by the model during training. This lack of control introduces confounding factors that our synthetic setup explicitly avoids.

We sincerely thank the reviewer for the time spent reading our paper. We would be happy to further discuss any remaining concerns, and we would appreciate if the reviewer could consider raising their score in case our responses address their questions adequately.

References

• Lehnert, Lucas, et al. "Beyond a*: Better planning with transformers via search dynamics bootstrapping." arXiv preprint arXiv:2402.14083 (2024).
• Su, DiJia, et al. "Dualformer: Controllable fast and slow thinking by learning with randomized reasoning traces." arXiv preprint arXiv:2410.09918 (2024).
• Bachmann, Gregor, and Vaishnavh Nagarajan. "The pitfalls of next-token prediction." arXiv preprint arXiv:2403.06963 (2024).

We thank the reviewer for taking the time and effort to carefully evaluate our work. We are glad they found our main result interesting and our analysis helpful to study fundamental properties of transformers. In the following, we discuss the raised points.

---

Weaknesses

• Across our experiments we use graphs with depth sampled uniformly from 2 to 7 (included). Together with the other graph generation parameters, the total number of unique graphs that can be sampled is above $5^{180}$.
  We restricted our analysis to a dataset and model size where the difference between $\eta = +5$ (DP) and $\eta = -5$ (DFS) was apparent. We experimented with other model sizes and dataset difficulty levels. In the biggest tested setting, model-size 235M and graph depth ranging from 2 to 9 (included), we observe that models converge to a generalization accuracy of 100%, nevertheless we still observe the superiority of $\eta = -5$ (DFS) in terms of faster convergence. This trend can also be observed from the comparison between $\eta = +5$ and $\eta = -5$ when both are trained with 128M tokens (Fig 4(a)).

• The doubts on the validity of some claims (W2) are addressed together with the questions.

---

Questions

From Figure 2, it seems that the redundancy setting is not exactly comparable to the $\eta = -5$ setting...

In the paper, we mainly compare $\eta = +5$ with $\eta = +5$ with redundancy at equal number of tokens in the dataset. The goal of this analysis is to check whether more raw test-time compute (here artificially injected via repetitions) is beneficial. We observe that $\eta = +5$ with redundancy is inferior to $\eta = +5$ without redundancy. This suggests that more test-time compute only cannot explain the performance gain of $\eta = -5$. Note that the runs of $\eta = +5$ with redundancy have both more samples and on average longer CoTs than the $\eta = -5$ runs shown in Figure 1. Nevertheless $\eta = -5$ is still superior.

---

Line 188: "...good generalization on the larger graph instances..."

We apologize to the reviewer for the unclear phrasing. In line 188 by “larger graph instances” we refer to graphs that are still within the training distribution. The graph depth in the dataset is sampled uniformly from 2 to 7 included. For further details on the graph generation strategy, we refer the reviewer to section A2 in the supplementary material.

---

The analysis on the model's confidence of the next step prediction is unclear...

We agree with the reviewer that our confidence metric has a clear interpretation at a path level, and this was intended. In all of the trace types multiple exploration orders are equally likely and indeed expected that higher degeneracy would ultimately result in reduced predictability in the CoTs. To support this, we report the Shannon’s surprise of the path continuation choice, averaged over the $\eta = -5,+5,0$ datasets:

$$\eta = +5 \rightarrow 1.3262 \pm 0.0006; \\ \eta = -5 \rightarrow 0.4821 \pm 0.0002; \\ \eta = 0 \rightarrow 1.905 \pm 0.003$$

However, the next-token confidence metric was not introduced ad-hoc by our study but is borrowed from Xuezhi Wang et al. (2024) where it is used as a heuristic to establish the quality of an LLM answer. They observe that by sampling multiple answers to a given question, picking the one with higher next-token confidence improved the accuracy compared to randomly picking an answer from the sampled ones. Our goal is to interpret the findings of Xuezhi Wang et al. (2024) in what we believe to be a better controlled environment for their metric. Furthermore, even if the considered metric has a clear interpretation at a path-level, it is not immediately obvious how it translates to the token-level as it can be affected by the next-token prediction steps inside a path.

---

Line 221: Why would it necessarily be the case that "incremental steps..."

In the case of $\eta = -5$ (DFS), incremental steps have a high next-token confidence as the exploration order prioritises path continuations that directly extend the last seen partial path.

---

Clarity and Stylistic Enhancements

We greatly appreciate the reviewer’s careful attention to our work and we are going to implement all their recommendations. More specifically:

---

I believe "Effect of...on..." rather than "Dependency on...of..." is closer to the intended meaning.

We are going to split the caption into 2 parts, one for (a) and the other for (b). In (a) there is a dependency on $\eta$, as shown in the algorithm, while in (b), in line with the reviewer’s suggestion, there is an effect of $\eta$.

---

It is not easy to understand the meaning "structural efficiency" if no precise definition is provided...

We agree with the reviewer that the paragraph is not clear and an explicit definition of it is needed. We plan to add the following to the main body:
“We define structural efficiency as the efficiency, in terms of cot length, given by varying the structure (exploration order) of the algorithm”

---

How are reasoning steps "disregarded"?

We apologize for the confusion. By “disregarding with some probability” we mean that, with probability $\geq 0$, we do not remove the sampled step from the queue (while it is added to the trace). As a result, the step can be sampled again in future iterations (possibly multiple times). We will revise the phrasing to improve clarity. The reviewer is right; with the systematic redundancy the length of the CoT can be increased by an integer factor.

---

Figure 3a: This plot needs a legend.

We are going to add legends to the plots in Fig. 3 and Fig. 4, improve the colors and fix the “full” and “dashed” reference before referring to Fig. 4(a).

---

We agree that the sentence:

“While also the $\eta = 0$ traces are longer than the $\eta = +5$ ones, the associated flat distribution over the exploration order, mixing depth-first and layer-by-layer exploration, is harder to understand and mimic for the trained model.”

is unclear. We intended to say that in the $\eta = 0$ setting the associated flat distribution over the exploration order, that mixes depth-first and layer-by-layer exploration, reduces the confidence of the model in predicting the next step, undermining the learning effectiveness. We will revise it accordingly.

---

Lines 215-218: This sentence is unclear and difficult to understand...

We agree that the sentence: “The model transitions from repeating the same reasoning steps from 20% to 3% of the times” is ambiguous. We intended to refer to the average proportion of repeated steps per reasoning trace across all validation samples. We will rephrase it to improve clarity.

---

We sincerely thank the reviewer for the valuable feedback, which has significantly contributed to enhancing the clarity of our paper. We hope our responses adequately address the raised concerns, particularly regarding the claims perceived as lacking sufficient evidence (W2). We would be grateful if the reviewer could consider revising their score considering these clarifications.

References

• Wang, Xuezhi, and Denny Zhou. "Chain-of-thought reasoning without prompting." Advances in Neural Information Processing Systems 37 (2024): 66383-66409.

We thank the reviewer for their continued engagement in this process.

Ah, so how many tokens are generated for ...

For the largest graphs (7 layers and 6 nodes in each layer, generated with a probability ~10^(-5)), the $\eta=-5$ traces have an average length of ~2.7K tokens, with large fluctuations for different exploration orders. In our experiments, the maximum training context length we could employ with our computational resources was 4096. Notice that, in this regime, to include hundreds of thousands of CoT examples, we are already training over several million tokens.

This still seems like a potential confounding factor ...

We never argued that next-token confidence, the number of correct next steps, and the accuracy are independent variables. Quite the opposite, we are showing that there is a clear correlation between them in our experiments. We agree with the reviewer that, apart from the different degrees of degeneracy in the exploration order, other factors could influence the model confidence, and some of them might be uncontrollable. However, we tried to control for the particular example of spurious effect proposed in the reply above: we are employing the same stopping criterion in all runs, i.e., selecting the checkpoint that achieves the maximum validation accuracy. In the mentioned single-path task, the lower model confidence for the second trained model would need to be caused by a different stopping criterion (as the reviewer said, training "to predict the correct token with lower confidence"), since nothing would prevent the model from becoming as confident as the former one without overfitting. While we cannot claim a causal link between next-token predictability and training effectiveness, we believe their relationship provides a reasonable and intuitive explanation of the observed inductive bias.