On the Bias of Next-Token Predictors Toward Systematically Inefficient Reasoning: A Shortest-Path Case Study
Authors: Riccardo Alberghi
Elizaveta Demyanenko
Luca Biggio
Luca Saglietti
Venue: NeurIPS 2025 poster ()
Keywords: Reasoning
Chain-of-thought
Next-token prediction
Transformers
Algorithm
Shortest-Path
Primary area: deep_learning

Abstract: Recent advances in natural language processing highlight two key factors for improving reasoning in large language models (LLMs): (i) allocating more test-time compute tends to help on harder problems but often introduces redundancy in the reasoning trace, and (ii) compute is most effective when reasoning is systematic and incremental, forming structured chains of thought (CoTs) akin to human problem-solving. To study these factors in isolation, we introduce a controlled setting based on shortest-path tasks in layered graphs. We train decoder-only transformers on question–trace–answer triples using a custom tokenizer, comparing models trained on optimal bottom-up dynamic programming traces with those trained on longer, valid traces involving backtracking. Surprisingly, under the same training-token budget, the latter models generalize better to unseen graphs. This benefit is not due to length alone—injecting arbitrary redundancy into reasoning traces fails to help and can even hurt performance. Instead, we find that generalization correlates with the model's confidence in next-token prediction, suggesting that long, coherent, and locally incremental traces make the training signal easier to optimize.

On the Bias of Next-Token Predictors Toward Systematically Inefficient Reasoning: A Shortest-Path
Case Study
Riccardo Alberghi
Elizaveta Demyanenko
riccardo. albeerghisstudbocconi.
elizaveta, Eiizaretaademyynnnkooopppll demyanenkoo@phh unibocconi.it
Luca Biggio luca. luca. bigg.iouunibcccooi...
Luca Saglietti luca. meaa.aalllettttimmmmccc...
Abstract
Recent advances in natural language processing highlight two key factors for im- proving reasoning in large language models (LLMs)): (i) allocating more test-time compute tends to help on harder problems but often introduces redundancy in the reasoning trace, and (ii) compute is most effective when reasoning systematic and incremental, forming structured chains of thought (CoT's) akin to human problem- solving. To study these factors isolation, we introduce controlled setting based shortest-palt tasks in layered graphs. We train decoder-only transformers on question ceession-trace-asseee answer triples using a custom tokenizer, comparing models trained optimal bottom-up dynamic programming traces with those trained on longer, valid traces involving backtracking. Surprisingly, with the same training-token budget, models trained on inefficient traces generalize better to unseen graphs. This benefit is not due to length alone- hurt performance. Instead, find that generaliza- tion correlates with the model's confidence next-token prediction, suggesting that long, coherent, and locally incremental traces make the training signal easier to op- timize. The code is available at wittttt:: : //githtu.... http://caarrooaarrrr///00
traces fails to help and alone-injecting arbitrary redundancy into reasoning
Introduction
Modern LLMs have made remarkable strides in tasks requiring reasoning and multi-step problem Increasing evidence demonstrates that the performance of these models signifi- cantly improves when their reasoning unrolls in step-by-step fashion, following CoTs reminiscent of how humans build their internal cognitive processes 5 development of LLMs is represented by the test-time-computt paradigm [9 I0] 11, driven by the in- tuition that harder problems often require more computational budget and thus, longer CoTs. These insights have been central to the development of advanced reasoning agents capable of achieving unprecedented performance on complex tasks spanning mathematical problem solving I2] [3 [4], code generation 16), and scientific inquiry [8]. Despite such progress, reasoning remains an elusive concept difficult to define precisely and challenging to study the wild. How teach machines reason effectively, generalize across domains, and adapt novel problems continues to be a fundamental open question.
solving [ 1
Another milestone in the rapid
Motivated by the need for a well-defined and interpretable setting to characterize reasoning in transformers, and inspired by [99] we turn to controlled algorithmic task (see Fig 1 syn- thetic shortest-paii problem on layered graphs. Each problem instance- -posed as a question to transformer-com consists of source-to- to-taeet graph with integer edge costs; the model tasked with
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

answering with any minimum-cov cost path. While a bottom-up dynamic programming (DP) approach is the canonical optimal solution for this problem, several alternative strategies can also reach the correct answer. We design family of such strategies and train transformers to follow them. This playground allows us to (i) generate possibly unlimited problem instances of varying levels of difficulty; (ii) probe key properties of effective reasoning agents identified in the literature. In particular, through this framework, we investigate the following questions:
Q1. Can a model learn to find an optimal path directly, without seeing intermediate steps?
Q2. Do intermediate algorithmic trajectories (CoTs) simplify the task for the model?
Q3. Is the optimal dynamic programming strategy the best CoT option train the model?
Q4. When is increasing the number of CoT steps beneficial for the model?
Q5. Can different solution strategies have a more or less suitable structure for next-token prediction?
Our study suggests that, while globally optimal strategies may appear ideal for teaching transformers how to reason about the assigned problem, less efficient traces can be more in line with the inductive bias of next-token predictive architectures. Paradoxically, inefficient reasoning turns out to be more effective. In summary, we make the following contributions:
1. Controlled reasoning benchmark: We introduce synthetic layered- graph shortest path task with a custom language format, enabling rigorous experiments on reasoning trace efficiency. The task serves proof-of-concept environment for studying how LLMs learn algorithms when provided different intermediate solution traces.
2. Thinking step-by-step: We find that training transformers to produce intermediate steps between question (graph instance) and answer (optimal path) substantially improves perfor- mance, in line with the behavior of modern LLM on problem-solvine tasks.
3. Efficiency vs. effectiveness analysis: Through extensive experiments, we provide direct evidence that training on inefficient reasoning traces can improve model performance compared to training on optimal ones. This counterintuitive result holds even when trace lengths are equalized between conditions by adding redundant steps, highlighting that not merely the length of the reasoning trace, but its structure that matters.
4. Next-token predictors favor inefficient traces:
We motivate our findings by measuring the confidence of trained models in predicting the next token. We find that this metric is higher for models trained on longer but systematic and locally incremental reasoning traces and lower on globally optimal strategies.
2 Problem Setup
As testbed for reasoning experiments, consider synthetic shortest-path problem in layered directed acyclic graphs (DAGs) with integer edge costs. We generate random graph instances from a family with parameters {L, K, Ce respectively representing: the maximum number of layers, the maximum number of nodes per internal layer, the maximum edge cost, and the average connectivity between nodes in successive layers. For simplicity, the first and last layers contain exactly one node, the source and the destination of the sought path. We also ensure that no nodes are either completely disconnected from the previous layer have connections to the next one. Once the graph has been defined, we label the nodes in top-to-bottom and left-to-right order. See Fig I for an example of small problem instance.
Dynamic programming solution. The above-described task can be framed as a simple multi-step reasoning task, involving the successive solution of a set of sub-problems, i.e., the shortest path from the source node to all intermediate nodes. The goal of the reasoner to adopt an efficient strategy for completing all the required reasoning steps and building an optimal solution. Enumeration of all partial paths would entail a O (K2) computational cost, yet the cost can be cut down to (LK2) if the sub-problems are conveniently ordered and the partial solutions dynamic programming (DP) approach, which solves the sub-problems in layer order-from shorter to longer partial paths, yields an optimal shortest path with the minimum number of reasoning steps.
stored away. A bottom-up
2.1 Tokenization
We aim to solve the shortest-path problem with GPT-like model, trained from scratch on next-token prediction over set of question- rrace-answer examples. We define task-specific token dictionary,
2

---

1.0
1.00
Confidence
d1
0.90
0.0
0.85
0.4
0.80
0.75
Efficient Trxc
0.0
0.70
10
15
25
20
Epoch
(a)
(c)
(d)
Question
Raß [
13
Efficient trace
Bot n0 m2
m0 m1
10
n3
10
m2
m3
m1
m2
m3
md
BoT
Inefficient
BoT m0 m1 2 no
n3
no
nd
BoT
Answer
w2
Figure 1: Reasoning in the shortest-path problem. (a) Example of layered DAG with integer edge costs. 'he nodes are labelled top-to-botton left-to-right, 'n0' and 'n4' representing the source and the destination of the path. The nodes in the optimal path, with cumulative cost 1 + 2 are highlighted in grey. A human reading the graph would backtrack before discovering the cheaper 'n0->n2--3-- path-mirroring the strategy the model ultimately favors. (b) We introduce custom tokens to uniquely represent the graph structure (question), the trace (efficient/nnefficient trace examples), and the corresponding shortest-path solution (answer). (c) Generalization performance, measured in terms of the probability of returning an optimal path in the answer, of model trained optimally efficient (dynamic- Mlynamic-programmiin programming like) traces and model trained on inefficient (depth-first-seare like) traces, with a corpus of 200K question-trace-ansve examples. The inefficient reasoning traces roughly 75% longer than the efficient ones. Only the model trained on the inefficient traces robustly generalizes to unseen graphs. (d) Next-token confidence of models trained efficient vs inefficient traces, displaying an inductive bias of the transformer toward learning the latter.
4,
solver algorithm
with unique tokens representing: begin-sequent (BoS) and end-of-sequence EoS begin-of-the of-tin BoT and end-of-think EoT each possible layer label; each possible node label; each integer in the range of possible cumulative edge costs; separator token, two additional syntax tokens, [ and
Each part of the question-trace-assvee triples follows well-defined syntactic rules:
Opening with a BoS token, the question contains a complete token encoding of the graph. As the example in Fig.[[]), each layer of the graph represented by sequence tokens, opening with the layer label, followed by the corresponding edge list enclosed between [ tokens. Each edge is declared as pair of node labels, the corresponding cost, and a separator.
Question:
The reasoning trace, enclosed between BoT EoT tokens, contains a set of reasoning steps, each represented as succession of node labels, the cumulative cost of the associated path, and separator as shown in (b). In Sec. 3 we will describe in detail family of traces considered in this work and how we parametrically control their length and efficiency. Crucially, all training traces meet the following optimality criteria: i) The reasoning steps always contain correct path- cost statements; ii) Longer paths are built incrementally, adding single node to previously partial path; iii) Once better alternative found, sub-optimal partial paths are never considered as building blocks for longer paths; iv) All reasoning traces complete and deterministically allow the construction an optimal path. Note that, by writing down the intermediate shortest-path solutions, the reasoning trace can be problem, and can be leveraged to avoid the exponential computational cost in the number of graph layers.
Trace:
explicit tabulation of the optimal partial costs of the shortest path
The answer simply repetition of the optimal path found during the reasoning trace, and follows the same syntax: succession of nodes from source to destination nodes, the associated
Answer:

---

cost, and separator seen in Fig.
The generated sequence is then closed by a EoS token. An example can be
Experimental Setup
We leverage the controlled nature of our problem setting define a random generator of reasoning traces with a tunable degree of efficiency. These exact traces are then used to build a training corpus of question-trace-ansee
triples, and train next-token prediction model on the shortest-path task.
The efficiency level of the CoTs is uniquely determined by the exploration order according to which the model computes partial paths and costs and then composes them to build the optimal path. As the trace generator traverses the graph, maintains an exploration queue containing path continuations yet to be considered. The associated priority weights depend controlling whether shorter vs. longer partial paths should be explored first. When multiple partial paths of the same length can be continued, their relative order is fully randomized. The internal logic of the exploration algorithm and its dependence on can be seen in Fig.Da)) a).
temperature parameter, the efficiency n,
Thus, 1) can bias the underlying algorithm toward a layer-by-layer (positive 77) or depth-first (negative ?)) approach. This directly affects the number of reasoning steps, since previously explored paths will need revising if better route to an intermediate node is encountered. For this reason in the paper we refer to positive r) values as efficient (less total steps) and to negative 7) values as inefficient (more total steps). Note, however, that the trace optimality criteria described in section 2.1 guarantee that the number steps remains polynomial (worst-case OCCL2K" D, as evidenced from the table in Fig. (b).
Furthermore, we can inject reasoning redundancy. by artificially increasing the length of the trace via repetition of full reasoning steps. To study the importance of preserving the CoT structure, we consider two variants: a deterministic version, where each reasoning step is immediately repeated and then never revisited and randomized version, where completed reasoning steps are re-appended to the exploration queue with probability 1/2.
Types of reasoning traces. To simplify the interpretation of the results, we will consider a few prototypical settings for the reasoning trace generator:
r +5 (DP): at this temperature, the reasoning trace corresponds bottom-up DP trace, systematically exploring the graph in a layer-by-layer order.
7 = 0: the reasoning trace chooses the next path to be explored uniformly at random among
the available options, irrespective of the path length, and might include some backtracking.
7) -5 (DFS): the reasoning trace systematically prioritizes depth-first approach, requir- ing substantial backtracking.
17 = +5 (DR): each reasoning steps deterministically repeated twice row.
" = +5 (RR): each reasoning step, after completion, is re-added to the exploration queue with probability 1/2. Note that this implies that, in expectation, each reasoning path is repeated twice.
Note that, given the exponential law employed to sample the layer order, the efficiency values +5 are large enough to fully order the exploration protocol (effectively behaving as 1) =00 but avoiding numerical instabilities). As shown in Fig Fbg. the average length of the traces increases with lower values of the efficiency 17, changing by roughly 75% when switching from 7) +5 (DP) to 7j -5 (DFS). In the redundancy cases, the number of repetitions is matched between the randomized and deterministic versions. Examples of the different trace types are provided in the Supplementary Materials (SM).
Trained model. We train from scratch a Phi3 (20 small language model, with 3 layers, 12 attention heads, 768 hidden dimensions, and 28.5M total parameters, for the next-token prediction task on the procedurally generated training examples. During training, we mask out the question (i.c., the
'Given the structure of the exploration algorithm Fig 2 a), each one of the ((LK) nodes can be at most revisited OCL)) times, since a best cost improvement is needed to trigger backtracking.

---

1: Initialize empey quenu and weight lists, E and
2: Initialize best cost and best path dictionarics, C and P
3: layerl
4:
5: append( (zi0, n. 0]}: append, W. 1)
6: while & *
type
CoT steps
7: chouse( (sre, (orr.dt,,layer) from E. w.p oc W)
= +5
33 1
8:
path C(sre) + cost(sre,dst), P(sre) U It C(dst) then
9:
43 4 33
10:
Cidst,, PPdst) c. path for destnnatoon((ss) do
-5
58 1 54
11:
? +5 (RR)
65 1 41
12:
e, 4- Idyr, exp(-n( layer++))
7 = +5 (DR)
65 -
13:
i & & then append(E, e): append((WW
15:
end end for
16:
17:
18:
end while
(b)
Figure 2: Impact of the efficiency v)- (a) The exploration algorithm used for determining the shortest-path. The exploration order depends on the parameter (line 12). (b) The effect of r) on the distribution of number of reasoning steps (estimated on 100K independent samples).
graph information) and the PAD tokens from the loss function, so that the model only learns to predict traces and answers within the context of the question. We employ constant learning rate of 2 10-5, and batch size of ~ 16K tokens (excluding the PAD tokens for a fair comparison between efficiency levels). SM, we show how adding layers to the transformer architecture can impact performance and sample efficiency.
Given the low entropy of our custom language and the mathematical nature of the reasoning task, we default to zero-temperature generation, greedily choosing the maximum likelihood next token, unless otherwise stated.
Metrics and performance evaluation. We implement a parser able to evaluate the sequence of tokens produced by the model and return set of metrics the quality of the generated trace and answers. The accuracy of the answers and efficiency of the trained models are assessed via two main indicators:
answer accuracy, constructed by requiring the optimality of the path in the answer, i... the conjunction of: i) the path is possible, involving connected nodes; ii) the path has the expected length, i.e. the number of layers in the graph; iii) the declared cost minimal, as obtained with a DP solver; iv) the path and cumulative cost declarations are consistent.
number of reasoning steps, counting the number of well-formatted partial-pate statements.
We also check for multiple secondary metrics the quality of the reasoning steps in the trace, including: i) if they contain syntax errors; ii) if they are incremental; iii) if they only build upon optimal partial paths; iv) if the path-cost declaration is consistent; v) if the reasoning steps repeated. To simplify the exposition, the analysis of these metrics deferred to SM.
Finally, inspired by (11. we also measure the next-token confidence of the model along the reasoning trace and answer, i.e., the average sampled token probability. Note that here we find this metric to be equivalent to the min-margin metric suggested in [21] in agreement with footnote observation therein.
If not otherwise specified, the metrics are averaged over a test set containing new graphs with sizes in the training graph distribution, and reported with 1-sigma error bars across five random training seeds. The best generalization accuracies are denoted with a star symbol in the figures.
Results
We aim to characterise the impact of the presence the reasoning trace, and of its length and structure, on the performance of model unseen shortest-path problems. In the following, fix the parameter settings for the graph generator to {T. = 7, K = 6, C 5, p. = 0.6), and ensure that all graph examples in training and test sets unique.
5

---

Epoch
Epoch Epoch
1.0
Accuracy
0.8
0.8
opšimll
-04
0.2
graph depth
poth possible
graph depth
0.4
consistent
H02
groph depth?
sost optimal
12248
12344
12249
Epoch
Epech
Addend
(a)
(b)
(c)
Figure 3: Learning find the shortest path. (a) Generalization performance of models trained
on ~ 340K graphs, respectively without reasoning traces (dashed) and with the = +5 (DP) traces (full), over graphs with depths 3-5-7. (b) Progress intermediate training goals for the // +55 (DP) model. (c) Acquisition of the integer addition sub-task, during the = +5 (DP) training. The plot shows the probability of the model predicting the correct row column sums different epochs.
1.0
Answer Accuracy
0.8
Noxt- Noxt-Token Taken Confidence
0.9
Training loss
1.0
n=
5
0.8
0.8
0.8
Q
0.2
0.8
0.2
0
10
20
40
10
15
20
0
2
3
Epoch
Epoch
Epoch
(b)
(c)
Figure 4: Impact of trace efficiency. (a) Comparison of the generalization performance between models trained efficient 7) +5 (DP), intermediate 7) 0, and inefficient 1) -5 (DFS) traces, with a training token budget 32M (dashed) and 128M (full) tokens. (b) Next-token confidence measured on the test set of models trained on efficient アj +5 (DP), intermediate 7 O, and inefficient = 5 (DFS) traces with training token budget of 128M. (c) Training losses for different seeds of -5 (DFS), showing sudden jumps the beginning of the 2nd epoch, and of +5 (DP), where optimization is slower and more continuous.
Finding the shortest path with a next-token predictor (Q1/2). The first finding we report on, shown Fig. is that next-token predictor can learn to solve shortest- problems in moderate- sized graph instances, when sufficient training data is presented (here ~ 340K graph examples). However, good generalization the larger in-distribution graph instances only be achieved when the model is allowed to produce a reasoning trace before returning an optimal path: the solid curves show the performance, on
layer graphs, of model trained the dynamic programming limit +5 (DP). Instead, the dashed curves show that model trained on the question-answar task, with the same number of examples, is unable learn generalizable rule for solving previously unseen large problems.
In F(b, break down the learning process for the n +5 (DP) model, showing the pace at which intermediate learning goals are unlocked, such as proposing candidate solutions that are possible, or correctly associating paths and costs. In Fig cc). sub-task integer addition (here restricted to a small subset (CCT. of possible cumulative sums). In the figure, we measure the probability of the model assigning the maximum logit the correct sum token, and display the order in which the different additions are learned during training. Note that this subtask is not trivial [22 23), although the training set extensively covers the relevant range of cumulative costs (see SM), since the model has to understand where to pick up the partial costs to be added from the question and the previous steps in the trace.
study how the model acquires the

---

Impact of efficiency and structure of the reasoning trace 53 reasoning trace efficiency on model performance, at fixed token budget by comparing 32M tokens with 128M tokens. In Fig. aa. the best accuracy in predicting the shortest path is achieved by the ?) = -5 (DFS) model, with the longest reasoning traces and systematic backtracking, followed by the DP-like 7) = +5 (DP), and finally by the 1) = O models. Note that, since the token budget at training is fixed, the 17 = -5 (DFS) inefficient model sees about 1/3 fewer graph examples compared to the efficient one at 1) +5 (DP), yet absorbs the training set information more effectively. Moreover, as shown in Fig. 2(b), the traces for r) = 0 are longer than those of 7 = +5, yet the corresponding curves are sub-optimal- hob-optinal-highlgghhnnn highlighting that higher test-time compute, represented by longer traces, does not necessarily translate into better performance. In Fig. [[c), we also train the 17 = =5 models with equal number of graph examples (~ 200K, as in the 128M dataset for n -5), finding an even larger performance gap.
We explore the impact of the
In Fig. 4b), we find a plausible explanation of the effectiveness of r = -5 and the poor performance of v) = 0, looking at the next-token confidence [2I] of the three models. While the 1) = traces are longer than the 77 +5 (DP) ones, the associated flat distribution over the exploration order, mixing depth-first and layer-by-layer exploration, reduces the confidence of the model in predicting the next step. This, in turn, undermines the learning effectiveness of the model trained on this trace type.
We can precisely quantify the degeneracy of the exploration order for each value of r7. by computing the average surprisal S (i.e., the Shannon information) associated with the selection of the next path from the exploration queue. We obtain
S = 1.3262 + 0.0006,
S = 0.4821 + 0.0002,
S = 1.905 + 0.003,
confirming that for 17 = 0 the order of the reasoning steps is the most uncertain. On the other hand, both 7 = +5 (DP) and 1 = - (DFS) strategies share a deterministic approach in the layer exploration order, but the degeneracy of equivalent choices is higher for +5 (DP). A similar study of the gap in next-token confidence, but for fixed number of training graph examples, is shown in Fig. (d).
The effect of trace predictability can also be seen from the optimization trajectories, in Fig. 4c). The -5 (DFS) trajectories often exhibit a sudden jump in the training loss, occurring around the beginning of epoch 2, which highlights "eureka" transition in the interpretation of the reasoning trace examples. We hypothesize this sudden transition could be explained by the emergence of specific circuits within the model forward pass, similar those identified by [24 25 26 27 (28). We therefore see the mechanistic interpretability analysis of our trained model as an interesting avenue for future work.
jamde
Injecting redundacy into the reasoning traces Q4). To further explore the impact of increased test-time compute, in the absence of stochastic confounders that decrease the predictability of the trace, we compare the 1 = +3 (DP) baseline with a model trained on deterministically redundant 7 +5 (DR) traces. Since we repeat each reasoning step twice in row, in principle, the model can build a mechanism for choosing the next path that relies on this repetition for artificially increasing the test-time compute. Note that the elongated Co'Is have more steps than 7) -5 (DFS) on average. In 5ig. we show that artificially increasing the length of the reasoning traces, without a systematic change in the exploration strategy, induces a slight performance deterioration if trained with fixed token budget (128M). This aligns with recent research showing that CoT length is task-dependent 29 and that the global structure of the CoT is often more important than its content 30)
Bias towards longer CoTs (QS). In the previous experiments, a non-systematic structure in the reasoning trace- as in the case of 1) = O O-was associated with a reduced capability of the model to predict the next token, affecting both optimization and generalization performance. Structural perturbations to the reasoning traces can, in fact, strongly hinder performance [31). A similar effect can be seen if the redundancy is introduced in a randomized fashion. In Fig aa), we show the probability of producing correct shortest path solution for a model trained in the 7 +5 (RR) setting, at zero sampling temperature. Apart from the reduction in the model accuracy compared to the deterministic analogue, in Fig. b)b we also observe that the generated trace length initially diverges from the expected one: the model enters repetition loops that can elongate the CoT indefinitely. Longer training is required for regularizing this behavior and eventually attaining better accuracy.
similar bigb-verbosity tendency can be traced in the v) = 0 case, in Fig a).. At zero sampling temperature, the model initially gravitates towards the trace lengths of n -5 (DFS), gradually
7

---

lemperature
path optimality (%)
Coll steps
0.0
0.0
211
182
177
132
89
0.4
0.7
85
77 = 51
72
1.2
79
71 - 43
08
67 13
15
62
Epoch
(a)
(b)
Figure 5: Redundant traces. (a) Comparison of generalization performance between models trained
traces with efficiency `j +5 (DP), = (DR), and +5 (RR) (with sampling temperatures
T= 1 (dashed) and = 0 (full), trained with a 128M token budget. (b) Regularization effect of sampling temperature length converges to the expected one from training data at higher temperatures.
+5 (RR), where the answer accuracy improves and the average CoT
80
temperature
(%)
CoT stops
T=0
70
T-0.5
Fpoch
CoT steps
60
-
0.5
86
52
41
45
50
44
40
Epoch
30
0.5
87
50 1: 38
46
20
14
10
30
Epoch
(b)
(a)
Figure 6: Impact of sampling temperature. (a) The length of the CoT' produced by r) model (full) initially converges to the expected length of the inefficient traces, -5 (DFS), gradually recovering after many epochs. By sampling at positive temperature (dashed and dotted), the length converges to the expected one for 7 = 0. (b) While converging to the expected number of reasoning steps for the r strategy, the 17 model also achieves better answer accuracy non-zero temperatures.
recovering after many epochs. In both cases, the models display bias towards mechanisms that systematically induce longer traces. This finding is consistent with multiple works showing the bias of L.LMs for high verbosity 2 32 33
Sampling at non-zero temperature. To facilitate the imitation of stochastic behaviors for the v/ = and = +5 (RR) models, we try exploring the effect of raising the sampling temperature. Counter- intuitively, larger temperatures are found regularize the verbosity of the generated sequences instead of encouraging it, as already noted in [34]. In Fig. Fig.5)b) and Fig. Fog. the best performance of the two models is recorded when the reasoning trace lengths become more compatible with those of the corresponding training examples.
5 Related Work
Transformer- models such OpenAl-ol [ and DeepSeek-R1 2 have achieved state-of-the. art results on tasks involving mathematical reasoning and logical inference 10 35]. Much of their success is attributed to the use of CoT reasoning and compute scaling at inference time. The role and limitations these components have become active areas of empirical and theoretical investigation. Several studies have shown that including intermediate CoT steps significantly enhances transformer performance [3
10.
37 38 For instance, [ [8 demonstrate that the expressive power of decoder-
only transformers increases with the length of CoT sequences. Similarly, [37] finds that, in parity

---

problems, CoT's not only boost expressiveness but also improve sample efficiency. Our experiments corroborate these findings, showing that training with CoT generally improves performance. However, we also observe that not all CoTss are equally beneficial, and longer traces do not always yield better outcomes.
This work aims to explore reasoning in controlled yet nontrivial setting. Graph-based algorithmic tasks serve as an effective benchmark for evaluating whether models can learn structured reasoning
and generalize beyond the training distribution [39 40 41 42 43) For example, [39] train Graph
Neural Networks to replicate intermediate steps of classical algorithms. Meanwhile, 42 investigate transformer performance with respect to architecture parameters and the of scratchpad tokens 36.. Most relevant to our setting, [43] demonstrate that autoregressive transformers often struggle to generalize on the seemingly simple path-star task, frequently relying on heuristics such as the Clever Hans effect. In contrast, we find that introducing intermediate reasoning steps significantly enhances next-token prediction accuracy and confidence.
Our problem setup is motivated by recent work examining transformers' reasoning and planning capabilities through prediction of A" search dynamies [99 44 Like these studies, task models with generating both reasoning trace and a final answer, given a structured graph as input. While prior work has shown the benefits of CoT training in terms of sample efficiency, we further demonstrate that the structure of the CoT plays critical role in performance. We introduce a confidence- based heuristic to evaluate the robustness of generated traces. To develop this heuristic, we build on the findings of (21), who propose test-time decoding metrics based on top-token probability or the gap between the top two probabilities. We apply the former to show that some reasoning traces yield more confident next-token predictions. Our results align with [45], who use confidence scores to guide the compression of redundant CoT's Finally, recent studies show that transformers can learn to generate long CoT's via supervised learning [10] 30. Notably, [00 emphasize that CoT structure can be more important than content- a finding that supports our observation that models trained on structured but suboptimal algorithmic traces outperform those trained on optimal yet less interpretable ones.
6
Discussion
Our controlled study reveals three high-level takeaways: (i) Chain-of-thought is pivotal. When the model is forced to jump directly from question to answer, performance on larger graphs collapses, while well-structured trace restores strong generalisation. (ii) Structure beats global optimality. Training on longer depth-fire first traces that revisit nodes consistently outperforms training on globally optimal manamic-programinn
traces, despite seeing fewer unique graphs under the same token budget. (ii) Next-token confidence is a good proxy for learnability. Across all settings, higher average top-token probability along the trace correlates with answer accuracy, suggesting that "casicr-to- predict" reasoning signals drive sample-efficient learning. Our findings caution that what seems most sensible to teach-the shortest, globally optimal trace-is not what next-token predictors learn most readily; they favour systematic, locally incremental yet longer reasoning paths.
Limitations. The presented setting, deliberately minimalist, entails several caveats. Our exper- imental design is built around a synthetic algorithmic task expressed in a custom token language, and the extent which the observed biases transfer to natural- -angual- or multimodal problem settings remains to be investigated. Different algorithmic domains (sorting. SAT, theorem proving) could yield different optimal-inefficient trade-offs, and different model architectures might display inductive biases that lead to different conclusions compared to auto-regressive models. We believe the exploration of these themes is an exciting direction for future work.
Future work. A natural next step is to explore whether transformers can be steered toward more compact reasoning: curriculum schedules that progressively shorten traces, reinforcement-leariie objectives that penalize verbosity, might encourage the model to internalize a leaner algorithm without sacrificing accuracy. The benchmark's 's tunable difficulty and transparent structure also lend themselves to a mechanistic interpretability analysis; the attention patterns and hidden activations could reveal computational circuits that implement incremental cost aggregation versus backtracking. Finally, the efficiency-vente verrus-effecctieeeee trade-off merits further investigations in larger language models and natural- -atural-language tasks.

---

7 Broader Impact
Our work explores how the inductive biases of decoder-only transformer models influence their reasoning abilities in a fully controlled setting. As reasoning in large language models remains a critical and evolving area of research in modern AI, we aim for our findings to inspire further investigation and support efforts to better understand and steer the behavior of contemporary AI systems.
10

---

References
[1] OpenAI, :, Aaron Jaech, Adam Kalai, Adam Lerer, Adam Richardson, Ahmed El-Kishky, Aiden Low, Alec Helyar, Aleksander Madry, Alex Beutel, Alex Carney, Alex Iftimie, Alex Karpenko, Alex Tachard Passos, Alexander Neitz, Alexander Prokofiev, Alexander Wei, Allison Tam, Ally Bennett, Ananya Kumar, Andre Saraiva, Andrea Vallone, Andrew Duberstein, Andrew Kondrich, Andrey Mishchenko, Andy Applebaum, Angela Jiang, Ashvin Nair, Barret Zoph, Behrooz Ghorbani, Ben Rossen, Benjamin Sokolowsky, Boaz Barak, Bob McGrew, Borys Minaiev, Botao Hao, Bowen Baker, Brandon Houghton, Brandon McKinzie, Brydon Eastman, Camillo Lugaresi, Cary Bassin, Cary Hudson, Chak Ming Li, Charles de Bourcy, Chelsea Voss, Chen Shen, Chong Zhang, Chris Koch, Chris Orsinger, Christopher Hesse, Claudia Fischer, Clive Chan, Dan Roberts, Daniel Kappler, Daniel Levy. Daniel Selsam, David Dohan, David Farhi, David Mely, David Robinson, Dimitris Tsipras. Doug Li, Dragos Oprica, Eben Freeman, Eddie Zhang, Edmund Wong. Elizabeth Proehl, Enoch Cheung, Eric Mitchell, Eric Wallace, Erik Ritter, Evan Mays, Fan Wang. Felipe Petroski Such, Filippo Raso, Florencia Leoni, Foivos Tsimpourlas, Francis Song, Fred von Lohmann, Freddie Sulit, Geoff Salmon, Giambattista Parascandolo, Gildas Chabot, Grace Zhao, Greg Brockman, Guillaume Leclerc, Hadi Salman, Haiming Bao, Hao Sheng. Hart Andrin, Hessam Bagherinezhad, Hongyu Ren, Hunter Lightman, Hyung Won Chung, Ian Kivlichan, Ian O' Connell, Ian Osband, Ignasi Clavera Gilaberte, Ilge Akkaya, Ilya Kostrikov, Ilya Sutskever, Irina Kofman, Jakub Pachocki, James Lennon, Jason Wei, Jean Harb, Jerry Twore, Jiacheng Feng, Jiahui Yu, Jiayi Weng. Jie Tang, Jieqi Yu, Joaquin Quiñonero Candela, Joe Palermo, Joel Parish, Johannes Heidecke, John Hallman, John Rizzo, Jonathan Gordon, Jonathan Uesato, Jonathan Ward, Joost Huizinga, Julie Wang, Kai Chen, Kai Xiao, Karan Singhal, Karina Nguyen, Karl Cobbe, Katy Shi, Kayla Wood, Kendra Rimbach, Keren Gu-Lemberg, Kevin Liu, Kevin Lu, Kevin Stone, Kevin Yu, Lama Ahmad, Lauren Yang, Leo Liu, Leon Maksin, Leyton Ho, Liam Fedus, Lilian Weng. Lindden Li, Lindsay McCallum, Lindsey Held, Lorenz Kuhn, Lukas Kondraciuk, Lukasz Kaiser, Luke Metz, Madelaine Boyd, Maja Trebacz, Manas Joglekar, Mark Chen, Marko Tintor, Mason Meyer, Matt Jones, Matt Kaufer, Max Schwarzer, Meghan Shah, Mehmet Yatbaz, Melody Y. Guan, Mengyuan Xu, Mengyuan Yan, Mia Glaese, Mianna Chen, Michael Lampe, Michael Malek, Michele Wang. Michelle Fradin, Mike McClay, Mikhail Pavlov, Miles Wang. Mingxuan Wang, Mira Murati, Mo Bavarian, Mostafa Rohaninejad, Nat McAleese, Neil Chowdhury, Neil Chowdhury, Nick Ryder, Nikolas Tezak, Noam Brown, Ofrr Nachum, Oleg Boiko, Oleg Murk, Olivia Watkins, Patrick Chao, Paul Ashbourne, Pavel Izmailov, Peter Zhokhov, Rachel Dias, Rahul Arora, Randall Lin, Rapha Gontijo Lopes, Raz Gaon, Reah Miyara, Reimar Leike, Renny Hwang, Rhythm Garg, Robin Brown, Roshan James, Rui Shu, Ryan Cheu, Ryan Greene. Saachi Jain, Sam Altman, Sam Toizer, Sam Toyer, Samuel Miserendino, Sandhini Agarwal, Santiago Hernandez. Sasha Baker, Scott McKinney, Scottie Yan, Shengjia Zhao, Shengli Hu, Shibani Santurkar, Shraman Ray Chaudhuri, Shuyuan Zhang. Siyuan Fu, Spencer Papay, Steph Lin, Suchir Balaji, Suvansh Sanjeev, Szymon Sidor, Tal Broda, Aidan Clark, Tao Wang. Taylor Gordon, Ted Sanders, Tejal Patwardhan, Thibault Sottiaux, Thomas Degry. Thomas Dimson, Tianhao Zheng, Timur Garipov, Tom Stasi, Trapit Bansal, Trevor Creech, Troy Peterson, Tyna Eloundou, Valerie Qi, Vineet Kosaraju, Vinnie Monaco, Vitchyr Pong. Vlad Fomenko, Weiyi Zheng, Wenda Zhou, Wes McCabe, Wojeiech Zaremba, Yann Dubois, Yinghai Lu, Yining Chen, Young Cha, Yu Bai, Yuchen He, Yuchen Zhang, Yunyun Wang, Zheng Shao, and Zhuohan Li. Openai ol system card, 2024.
[2] DeepSeek-Al, AI, Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Ruoyu Zhang, Runxin Xu, Qihao Zhu, Shirong Ma, Peiyi Wang, Xiao Bi, Xiaokang Zhang, Xingkai Yu, Yu Wu, Z. F. Wu, Zhibin Gou, Zhihong Shao, Zhuoshu Li, Ziyi Gao, Aixin Liu, Bing Xue, Bingxuan Wang, Bochao Wu, Bei Feng, Chengda Lu, Chenggang Zhao, Chengqi Deng, Chenyu Zhang, Chong Ruan, Damai Dai, Deli Chen, Dongjie Ji, Erhang Li, Fangyun Lin, Fucong Dai, Fuli Luo, Guangbo Hao, Guanting Chen, Guowei Li, H. Zhang, Han Bao, Hanwei Xu, Haocheng Wang, Honghui Ding, Huajian Xin, Huazuo Gao, Hui Qu, Hui Li, Jianzhong Guo, Jiashi Li, Jiawei Wang, Jingehang Chen, Jingyang Yuan, Junjie Qiu, Junlong Li, J. L. Cai, Jiaqi Ni, Jian Liang, Jin Chen, Kai Dong, Kai Hu, Kaige Gao. Kang Guan, Kexin Huang, Kuai Yu, Lean Wang, Lecong Zhang, Liang Zhao, Litong Wang, Liyue Zhang, Lei Xu, Leyi Xia, Mingchuan Zhang, Minghua Zhang, Minghui Tang, Meng Li, Miaojun Wang, Mingming Li, Ning Tian, Panpan Huang, Peng Zhang, Qiancheng Wang, Qinyu Chen, Qiushi Du, Ruiqi Ge, Ruisong Zhang, Ruizhe Pan, Runji Wang, R. J. Chen, R. L. Jin, Ruyi Chen, Shanghao Lu, Shangyan
11

---

Zhou, Shanhuang Chen, Shengfeng Ye, Shiyu Wang, Shuiping Yu, Shunfeng Zhou, Shuting Pan, S. Li, Shuang Zhou, Shaoqing Wu, Shengfeng Ye, Tao Yun, Tian Pei, Tianyu Sun, T. Wang. Wangding Zeng, Wanjia Zhao, Wen I Liu, Wenfeng Liang, Wenjun Gao, Wenqin Yu, Wentao Zhang, W. I. Xiao, Wei An, Xiaodong Liu, Xiaohan Wang, Xiaokang Chen, Xiaotao Nie, Xin Cheng, Xin Liu, Xin Xie, Xingchao Liu, Xinyu Yang, Xinyuan Li, Xuecheng Su, Xuheng Lin, X. Q. Li, Xiangyue Jin, Xiaojin Shen, Xiaosha Chen, Xiaowen Sun, Xiaoxiang Wang, Xinnan Song, Xinyi Zhou, Xianzu Wang, Xinxia Shan, Y. K. Li, Y. Q. Wang. Y. X. Wei, Yang Zhang, Yanhong Xu, Yao Li, Yao Zhao, Yaofeng Sun, Yaohui Wang, Yi Yu, Yichao Zhang, Yifan Shi, Yiliang Xiong, Ying He, Yishi Piao, Yisong Wang, Yixuan Tan, Yiyang Ma. Yiyuan Liu, Yongqiang Guo, Yuan Ou, Yuduan Wang, Yue Gong, Yuheng Zou, Yujia He, Yunfan Xiong, Yuxiang Luo, Yuxiang You. Yuxuan Liu, Yuyang Zhou, Y. X. Zhu, Yanhong Xu, Yanping Huang, Yaohui Li, Yi Zheng. Yuchen Zhu, Yunxian Ma, Ying Tang. Yukun Zha, Yuting Yan, 7.. Z.. Ren, Zehui Ren, Zhangli Sha, Zhe Fu, Zhean Xu, Zhenda Xie, Zhengyan Zhang, Zhewen Hao, Zhicheng Ma, Zhigang Yan, Zhiyu Wu, Zihui Gu, Zijia Zhu, Zijun Liu, Zilin Li, Ziwei Xie, Ziyang Song, Zizheng Pan, Zhen Huang, Zhipeng Xu, Zhongyu Zhang, and Zhen Zhang. Deepseek-rl: Incentivizing reasoning capability in Ilms via reinforcement learning, 2025.
[3] Qwen Team. Qwq-32b: Embracing the power of reinforcement learning, March 2025.
[4] Jujie He, Jiacai Liu, Chris Yuhao Liu, Rui Yan. Chaojie Wang, Peng Cheng, Xi- aoyu Zhang, Fuxiang Zhang, Jiacheng Xu, Wei Shen, Siyuan Li. Liang Zeng, Tianwen Wei, Cheng Cheng, Bo An, Yang Liu, and Yahui Zhou. Skywork open reasoner series.
httpas//ccarrrccoos---ddggggneee Skywork-Open Open hrrpooeee-eeree---oooocaaaaasaa-
notion.site.......
2025.
Notion Blog.
[5] Jason Wei, Xuezhi Wang. Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Fd Chi, Quoc V. Le, and Denny Zhou. Chain-of-thought prompting elicits reasoning in large language models, arXiv preprint arXiv:2201. 2022.
[6] Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoe V. Le, Ed Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. arXiv preprint ar 2rXiv:200../177/ 2022.
[7] Edward Yeo. Yuxuan Tong, Morry Niu, Graham Neubig, and Xiang Yue. Demystifying long thtiuhtf- reasoning llms, 2025.
[8] Zhiyuan Li, Hong Liu, Denny Zhou, and Tengyu Ma. Chain of thought empowers transformers to solve inherently serial problems, 2024.
[9] Charlie Snell, Jaehoon Lee, Kelvin Xu, and Aviral Kumar. Scaling Ilm test-time compute optimally can be more effective than scaling model parameters, 2024.
[10] 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. arXiv preprint arXiv:2501.19399 2025.
[11] 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, 2025.
[12] OpenAl, :, Aaron Hurst, Adam Lerer, Adam P. Goucher, Adam Perelman, Aditya Ramesh, Aidan Clark, AJ Ostrow, Akila Welihinda, Alan Hayes, Alec Radford, Aleksander Mądry, Alex Baktr-Whiteomb, Alex Beutel, Alex Borzunov, Alex Carney, Alex Chow, Alex Kirillov, Alex Nichol, Alex Paino, Alex Renzin, Alex Tachard Passos, Alexander Kirillov, Alexi Christakis, Alexis Conneau, Ali Kamali, Allan Jabri, Allison Moyer, Allison Tam, Amadou Crookes, Amin Tootoochian, Amin Tootoonchian. Ananya Kumar, Andrea Vallone, Andrej Karpathy, Andrew Braunstein, Andrew Cann, Andrew Codispoti, Andrew Galu, Andrew Kondrich, Andrew Tul- loch, Andrey Mishchenko, Angela Baek, Angela Jiang, Antoine Pelisse, Antonia Woodford, Anuj Gosalia, Arka Dhar, Ashley Pantuliano, Avi Nayak, Avital Oliver, Barret Zoph, Behrooz Ghorbani, Ben Leimberger, Ben Rossen, Ben Sokolowsky, Ben Wang. Benjamin Zweig, Beth
12

---

Hoover, Blake Samic, Bob McGrew, Bobby Spero, Bogo Giertler, Bowen Cheng, Brad Lightcap. Brandon Walkin, Brendan Quinn, Brian Guarraci, Brian Hsu, Bright Kellogg, Brydon Eastman, Camillo Lugaresi, Carroll Wainwright, Cary Bassin, Cary Hudson, Casey Chu, Chad Nelson, Chak Li, Chan Jun Sher,, Channing Conger, Charlotte Barette, Chelsea Voss, Chen Ding, Cheng Lu, Chong Zhang, Chris Beaumont, Chris Hallacy, Chris Koch, Christian Gibson, Christina Kim, Christine Choi, Christine McLeavey, Christopher Hesse, Claudia Fischer, Clemens Winter, Coley Czarnecki, Colin Jarvis, Colin Wei, Constantin Koumouzelis, Dane Sherburn, Daniel Kappler, Daniel Levin, Daniel Levy, David Carr, David Farhi, David Mely, David Robinson, David Sasaki, Denny Jin, Dev Valladares, Dimitris Tsipras, Doug Li, Duc Phong Nguyen, Duncan Findlay, Edede Oiwoh, Edmund Wong. Ehsan Asdar, Elizabeth Prochl, Elizabeth Yang, Eric Antonow, Eric Kramer, Eric Peterson, Eric Sigler, Eric Wallace, Eugene Brevdo, Evan Mays, Farzad Khorasani, Felipe Petroski Such, Filippo Raso, Francis Zhang. Fred von Lohmann, Freddie Sulit, Gabriel Goh, Gene Oden, Geoff Salmon, Giulio Starace, Greg Brockman, Hadi Salman, Haiming Bao, Haitang Hu, Hannah Wong. Haoyu Wang. Heather Schmidt, Heather Whitney, Heewoo Jun, Hendrik Kirchner, Henrique Ponde de Oliveira Pinto, Hongyu Ren, Hui- wen Chang, Hyung Won Chung, Ian Kivlichan, Ian O' O'Connell, Ian O' O'Connell, Ian Osband, Ian Silber, Ian Sohl, Ibrahim Okuyucu, Ikai Lan, Ilya Kostrikov, Ilya Sutskever, Ingmar Kanitschei- der, Ishaan Gulrajani, Jacob Coxon, Jacob Menick, Jakub Pachocki, James Aung, James Betker, James Crooks, James Lennon, Jamie Kiros, Jan Leike, Jane Park. Jason Kwon, Jason Phang. Jason Teplitz, Jason Wei, Jason Wolfe. Jay Chen, Jeff Harris, Jenia Varavva, Jessica Gan Lee, Jessica Shich, Ji Lin, Jiahui Yu, Jiayi Weng, Jie Tang. Jieqi Yu, Joanne Jang, Joaquin Quinonero Candela, Joe Beutler, Joe Landers, Joel Parish, Johannes Heidecke, John Schulman, Jonathan Lachman, Jonathan McKay, Jonathan Uesato, Jonathan Ward, Jong Wook Kim, Joost Huizinga, Jordan Sitkin, Jos Kraaijeveld, Josh Gross, Josh Kaplan, Josh Snyder, Joshua Achiam, Joy Jiao, Joyce Lee, Juntang Zhuang, Justyn Harriman, Kai Fricke, Kai Hayashi, Karan Singhal, Katy Shi, Kavin Karthik, Kayla Wood, Kendra Rimbach, Kenny Hsu, Kenny Nguyen, Keren Gu-Lemberg, Kevin Button, Kevin Liu, Kiel Howe, Krithika Muthukumar, Kyle Luther, Lama Ahmad, Larry Kai, Lauren Itow, Lauren Workman, Leher Pathak, Leo Chen, Li Jing. Lia Guy, Liam Fedus, Liang Zhou, Lien Mamitsuka, Lilian Weng, Lindsay McCallum, Lindsey Held, Long Ouyang, Louis Feuvrier, Lu Zhang, Lukas Kondraciuk, Lukasz Kaiser, Luke Hewitt, Luke Metz, Lyric Doshi, Mada Aflak, Maddic Simens. Madelaine Boyd, Madeleine Thompson. Marat Dukhan, Mark Chen, Mark Gray, Mark Hudnall, Marvin Zhang, Marwan Aljuheh, Mateusz Litwin, Matthew Zeng, Max Johnson, Maya Shetty, Mayank Gupta, Meghan Shah, Mehmet Yathaz, Meng Jia Yang, Mengchao Zhong, Mia Glaese, Mianna Chen, Michael Janner, Michael Lampe, Michael Petrov, Michael Wu, Michele Wang, Michelle Fradin, Michelle Pokrass, Miguel Castro, Miguel Oom Temudo de Castro, Mikhail Pavlov, Miles Brundage, Miles Wang. Minal Khan, Mira Murati, Mo Bavarian, Molly Lin, Murat Yesildal, Nacho Soto, Natalia Gimelshein, Natalie Cone, Natalie Staudacher, Natalie Summers, Natan LaFontaine, Neil Chowdhury, Nick Ryder, Nick Stathas, Nick Turley, Nik Tezak, Niko Felix, Nithanth Kudige. Nitish Keskar, Noah Deutsch, Noel Bundick, Nora Puckett, Ofir Nachum, Ola Okelola, Oleg Boiko, Oleg Murk. Oliver Jaffe, Olivia Watkins, Olivier Godement, Owen Campbell-Moore, Patrick Chao. Paul McMillan, Pavel Belov, Peng Su, Peter Bak, Peter Bakkum, Peter Deng, Peter Dolan, Peter Hoeschele, Peter Welinder, Phil Tillet, Philip Pronin, Philippe Tillet, Prafulla Dhariwal, Qiming Yuan, Rachel Dias, Rachel Lim, Rahul Arora, Rajan Troll, Randall Lin, Rapha Gontijo Lopes, Raul Puri, Reah Miyara, Reimar Leike, Renaud Gaubert, Reza Zamani, Ricky Wang, Rob Donnelly, Rob Honsby, Rocky Smith, Rohan Sahai, Rohit Ramchandani, Romain Huet, Rory Carmichael, Rowan Zellers, Roy Chen, Ruby Chen, Ruslan Nigmatullin, Ryan Cheu, Saachi Jain, Sam Altman, Sam Schoenholz, Sam Toizer, Samuel Miserendino, Sandhini Agarwal, Sara Culver, Scott Ethersmith, Scott Gray, Sean Grove, Sean Metzger, Shamez Hermani, Shantanu Jain, Shengjia Zhao, Sherwin Wu. Shino Jomoto, Shirong Wu, Shuaiqi, Xia, Sonia Phene, Spencer Papay, Srinivas Narayanan. Steve Coffey, Steve Lec, Stewart Hall, Suchir Balaji. Tal Broda, Tal Stramer, Tao Xu, Tarun Gogineni, Taya Christianson, Ted Sanders, Tejal Patwardhan, Thomas Cunninghman, Thomas Degry, Thomas Dimson, Thomas Raoux, Thomas Shadwell, Tianhao Zheng, Todd Underwood, Todor Markov, Toki Sherbakov, Tom Rubin, Tom Stasi, Tomer Kaftan, Tristan Heywood, Troy Peterson, Tyce Walters, Tyna Eloundou, Valerie Qi. Veit Moeller, Vinnie Monaco, Vishal Kuo, Vlad Fomenko, Wayne Chang, Weiyi Zheng, Wenda Zhou, Wesam Manassra, Will Sheu, Wojeiech Zaremba, Yash Patil, Yilei Qian, Yongjik Kim, Youlong Cheng, Yu Zhang, Yuchen He, Yuchen Zhang, Yujia Jin, Yunxing Dai, and Yury Malkov. Gpt-4o system card, 2024.
13

---

[13] An Yang, Beichen Zhang, Binyuan Hui, Bofei Gao, Bowen Yu, Chengpeng Li, Dayiheng Liu, Jianhong Tu. Jingren Zhou, Junyang Lin, Keming Lu, Mingfeng Xue, Runji Lin, Tianyu Liu, Xingzhang Ren, and Zhenru Zhang. Qwen2.5-math technical report: Toward mathematical expert model via self-improvement, 2024.
[14] Zhihong Shao, Peiyi Wang, Qihao Zhu, Runxin Xu, Junxiao Song, Xiao Bi, Haowei Zhang, Mingchuan Zhang, Y. K. Li, Y. Wu, and Daya Guo. Deepseekmath: Pushing the limits of mathematical reasoning in open language models, 2024.
[15] Juyong Jiang, Fan Wang, Jiasi Shen, Sungju Kim, and Sunghun Kim. A survey on large language models for code generation, 2024.
[16] Binyuan Hui, Jian Yang. Zeyu Cui, Jiaxi Yang, Dayiheng Liu, Lei Zhang, Tianyu Liu, Jia- jun Zhang. Bowen Yu, Kai Dang, al. Qwen2. 5-coder technical report. arXiv preprint MeXi::240912288. 2024.
[17] Chris Lu, Cong Lu, Robert Tjarko Lange, Jakob Foerster, Jeff Clune, and David Ha. The AI Scientist: Towards fully automated open-ended scientific discovery. arXiv preprint arXiv:2408.066 06292, 2024.
[18] Bodhisattwa Prasad Majumder, Harshit Surana, Dhruv Agarwal, Bhavana Dalvi Mishra, Abhi- jeetsingh Meena, Aryan Prakhar, Tirth Vora, Tushar Khot, Ashish Sabharwal, and Peter Clark. Discoverybench: Towards data-driven discovery with large language models, 2024.
[19] Lucas Lehnert, Sainbayar Sukhbaatar, Paul Mcy,y, Michael Rabbat, and Yuandong Tian. Beyond a*: Better planning with transformers via search dynamics bootstrapping. arXiv preprint arXiv:2402.14006 2024.
[20] Marah Abdin, Jyoti Aneja, Hany Awadalla, Ahmed Awadallah, Ammar Ahmad Awan, Nguyen Bach, Amit Bahree, Arash Bakhtiari, Jianmin Bao, Harkirat Behl, Alon Benhaim, Misha Bilenko, Johan Bjorck, Séhastien Bubeck, Martin Cai, Qin Cai, Vishrav Chaudhary, Dong Chen, Dongdong Chen, Weizhu Chen, Yen-Chun Chen, Yi-Ling Chen, Hao Cheng, Parul Chopra, Xiyang Dai, Matthew Dixon, Ronen Eldan, Victor Fragoso, Jianfeng Gao, Mei Gao, Min Gao, Amit Garg, Allie Del Giorno, Abhishek Goswami, Suriya Gunasekar, Emman Haider, Junheng Hao, Russell J. Hewett, Wenxiang Hu, Jamie Huynh, Dan Iter, Sam Ade Jacobs, Mojan Javaheripi, Xin Jin, Nikos Karampatziakis, Piero Kauffmann, Mahoud Khademi, Dongwoo Kim, Young Jin Kim, Lev Kurilenko, James R. Lee, Yin Tat Lee, Yuanzhi Li, Yunsheng Li, Chen Liang, Lars Liden, Xihui Lin. Zeqi Lin, Ce Liu, Liyuan Liu, Mengehen Liu, Weishung Liu, Xiaodong Liu, Chong Luo, Piyush Madan, Ali Mahmoudzadeh, David Majercak, Matt Mazzola, Caio César Teodoro Mendes, Arindam Mitra, Hardik Modi, Anh Nguyen, Brandon Norick, Barun Patra, Daniel Perez-Becker, Thomas Portet, Reid Pryzant, Heyang Qin, Marko Radmilac, Liliang Ren, Gustavo de Rosa, Corby Rosset, Sambudha Roy, Olatunji Ruwase, Olli Saarikivi, Amin Saied, Adil Salim, Michael Santacroce, Shital Shah, Ning Shang, Hiteshi Sharma, Yelong Shen, Swadheen Shukla, Xia Song, Masahiro Tanaka, Andrea Tupini. Praneetha Vaddamanu, Chunyu Wang, Guanhua Wang, Lijuan Wang. Shuohang Wang, Xin Wang, Yu Wang, Rachel Ward, Wen Wen, Philipp Witte, Haiping Wu, Xiaoxia Wu, Michael Wyatt, Bin Xiao, Can Xu, Jiahang Xu, Weijian Xu, Jilong Xue. Sonali Yadav, Fan Yang, Jianwei Yang, Yifan Yang, Ziyi Yang, Donghan Yu, Lu Yuan, Chenruidong Zhang, Cyril Zhang, Jianwen Zhang, Li Lyna Zhang. Yi Zhang, Yue Zhang, Yunan Zhang, and Xiren Zhou. Phi-3 technical report: A highly capable language model locally on your phone, 2024.
[21] Xuezhi Wang and Denny Zhou, Chain-of-thought reasoning without prompting. arXiv preprint WxXi::2402.10200, 2024.
[22] Philip Quirke and Fazl Barez. Understanding addition in transformers, 2024.
[23] Neel Nanda, Lawrence Chan, Tom Lieberum, Jess Smith, and Jacob Steinhardt. Progress measures for grokking via mechanistic interpretability, 2023.
[24] Catherine Olsson, Nelson Elhage, Neel Nanda, Nicholas Joseph, Nova DasSarma, Tom Henighan, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, Tom Conerly, Dawn Drain, Deep Ganguli, Zac Hatfield-Dodae Danny Hernandez, Scott Johnston, Andy Jones, Jackson Kernion, Liane Lovitt, Kamal Ndousse, Dario Amodei, Tom Brown, Jack Clark, Jared Kaplan, Sam McCandlish, and Chris Olah. In-context learning and induction heads, 2022.
14

---

[25] Gouki Minegishi, Hiroki Furuta, Shohei Taniguchi, Yusuke Iwasawa, and Yutaka Matsuo. In-context meta learning induces multi-phase circuit emergence. In ICLR 2025 Workshop on Building Trust in Language Models and Applications, 2025.
[26]
Vivien Cabannes, Charles Amal, Wassim Bouaziz, Alice Yang, Francois Charton, and Julia Kempe. Iteration head: A mechanistic study of chain-of -f-hououtthhh.tt. 2024.
[27] Freya Behrens, Luca Biggio, and Lenka Zdeborová. Understanding counting in small trans- formers: The interplay between attention and feed-forward layers. In ICML 2024 Workshop on Mechanistic Interpretability.
[28] Jerome Garnier-Brun Marc Mézard, Emanuele Moscato, and Luca Saglietti. How transformers learn structured data: insights from hierarchical filtering, 2024.
[29] Yuyang Wu, Yifei Wang. Tianqi Du, Stefanie Jegelka, and Yisen Wang. When more is less: Understanding chain-of- length in Ilms, 2025.
[30] 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 reason from demonstrations structure, not content, is what matters!, 2025.
[31] Dacheng Li, Shiyi Cao. Tyler Griggs, Shu Liu, Xiangxi Mo. Eric Tang, Sumanth Hegde, Kourosh Hakhamaneshi, Shishir G Patil, Matei Zaharia, et al. Llms can easily learn to reason from demonstrations structure, not content, is what matters! arXiv preprint arXiv:2502.03374, 2025.
[32] Sania Nayab, Giulio Rossolini, Marco Simoni, Andrea Saracino, Giorgio Buttazzo, Nicolamaria Manes, and Fabrizio Giacomelli. Concise thoughts: Impact of output length on Ilm reasoning and cost, 2025.
[33] 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 Ilms, 2025.
[34] Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi. The curious case of neural text degeneration. arXiv preprint arXiv:1904.00 .9..0097111. 2019.
[35] Chujie Zheng, Zhennu Zhang, Beichen Zhang, Runji Lin, Keming Lu, Bowen Yu, Dayiheng Liu, Jingren Zhou, and Junyang Lin. Processbench: Identifying process errors in mathematical reasoning, 2024.
[36] 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. arXiv preprint / 14, 2021.
[37] Kaiyue Wen, Huaqing Zhang. Hongzhou Lin, and Jingzhao Zhang. From sparse dependence to sparse attention: Unveiling how chain-of-thought enhances transformer sample efficiency, 2025,
[38] William Merrill and Ashish Sabharwal. The expressive power of transformers with chain of thought, 2024.
[39] Petar Veličković, Rex Ying, Matilde Padovano, Raia Hadsell, and Charles Blundell. Neural exccution of graph algorithms,, 2020.
[40] Petar Veličkovié. Neural algorithmic reasoning. The Gradient, Oct 2023. Accessed: 2025-05-01.
[41] Petar Veličković and Charles Blundell. Neural algorithmic reasoning. Patterns, 207):300 July 2021.
[42] Clayton Sanford, Bahare Fatemi, Ethan Hall, Anton Tsitsulin, Mehran Kazemi, Jonathan Halcrow, Bryan Perozzi, and Vahab Mirrokni. Understanding transformer reasoning capabilities via graph algorithms. arXiv preprint arXiv:2405.18572 2024.
15

---

[43] Gregor Bachmann and Vaishnavh Nagarajan. The pitfalls of next-token prediction. In Proceed- ings of the 41st International Conference on Machine Learning. pages 2296-2318, 2024.
[44] DiJia Su, Sainbayar Sukhbaatar, Michael Rabbat, Yuandong Tian, and Qinqing Zheng. Du- alformer: Controllable fast and slow thinking by learning with randomized reasoning traces, 2025.
[45] Ziqing Qiao, Yongheng Deng. Jiali Zeng, Dong Wang, Lai Wei, Fandong Meng, Jie Zhou, Ju Ren, and Yaoxue Zhang. Concise: Confidence-gud compression in step-by-step efficient reasoning, 2025.
[46]
Marah Abdin, Jyoti Aneja, Hany Awadalla, Ahmed Awadallah, Ammar Ahmad Awan, Nguyen Bach, Amit Bahree, Arash Bakhtiari, Jianmin Bao, Harkirat Behl, Alon Benhaim, Misha Bilenko, Johan Bjorck, Sébastien Bubeck, Martin Cai, Qin Cai, Vishrav Chaudhary, Dong Chen, Dongdong Chen, Weizhu Chen, Yen-Chun Chen, Yi-Ling Chen, Hao Cheng, Parul Chopra, Xiyang Dai, Matthew Dixon, Ronen Eldan, Victor Fragoso, Jianfeng Gao, Mei Gao, Min Gao, Amit Garg, Allie Del Giorno, Abhishek Goswami, Suriya Gunasekar, Emman Haider, Junheng Hao, Russell J. Hewett, Wenxiang Hu, Jamie Huynh, Dan Iter, Sam Ade Jacobs, Mojan Javaheripi, Xin Jin, Nikos Karampatziakis, Piero Kauffmann, Mahoud Khademi, Dongwoo Kim, Young Jin Kim, Lev Kurilenko, James R. Lee, Yin Tat Lee, Yuanzhi Li, Yunsheng Li, Chen Liang, Lars Liden, Xihui Lin. Zeqi Lin, Ce Liu, Liyuan Liu, Mengchen Liu, Weishung Liu, Xiaodong Liu, Chong Luo, Piyush Madan, Ali Mahmoudzadeh, David Majercak, Matt Mazzola, Caio César Teodoro Mendes, Arindam Mitra, Hardik Modi, Anh Nguyen, Brandon Norick, Barun Patra, Daniel Perez-Becker, Thomas Portet, Reid Pryzant, Heyang Qin, Marko Radmilac, Liliang Ren, Gustavo de Rosa, Corby Rosset, Sambudha Roy, Olatunji Ruwase, Olli Saarikivi, Amin Saied, Adil Salim, Michael Santacroce, Shital Shah, Ning Shang, Hiteshi Sharma, Yelong Shen, Swadheen Shukla, Xia Song, Masahiro Tanaka, Andrea Tupini, Praneetha Vaddamanu, Chunyu Wang, Guanhua Wang, Lijuan Wang. Shuohang Wang, Xin Wang, Yu Wang, Rachel Ward, Wen Wen, Philipp Witte, Haiping Wu, Xiaoxia Wu, Michael Wyatt, Bin Xiao, Can Xu, Jiahang Xu, Weijian Xu, Jilong Xue, Sonali Yadav, Fan Yang. Jianwei Yang, Yifan Yang. Ziyi Yang, Donghan Yu, Lu Yuan, Chenruidong Zhang, Cyril Zhang, Jianwen Zhang, Li Lyna Zhang, Yi Zhang, Yue Zhang, Yunan Zhang, and Xiren Zhou. Phi-3 technical report: A highly capable language model locally on your phone, 2024.
[47] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Z. Yang, Zach Vito,o Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. CoRR, abs/ 0tts//992.0173.. 2019.
[48] Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, and Jamie Brew. Huggingface's transformers:
State-of-the-ae art natural language processing. CoRR, abs/1910.03771, 2019.
[49] Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng. Cody Hao Yu, Joseph E. Gonzalez, Hao Zhang, and Ion Stoica. Efficient memory management for large lan- guage model serving with pagedattention. Proceedings of the ACM SIGOPS 29th Symposium on Operating Systems Principles, 2023.
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]
The abstract and introduction point out all the main results of the numerical experiments presented in the paper.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in 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.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
Limitations are discussed in Section
Guidelines:
The answer NA means that the paper has no 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 their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect 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 is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to 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 fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [NA]
17

---

Justification:
The paper does not contain any theoretical result.
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 the statement of any theorems.
The proofs can either appear 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 of the paper to the extent that it 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: All the information needed to reproduce the experimental results are included in the supplementary material.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer to 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 novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If 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., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
18

---

Answer: [Yes]
Justification:
The code along with the config files will be open-sourced upon acceptance.
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 not be possible, so "No" 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 NeurlPS code and data submission guidelines (https
/
wwt.Suubmisiooooiiiooooooooo for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If 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 the paper) is 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:
All the details necessary are provided in the supplementary materials.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to a level detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: All the plots and tables have 1-sigma error bars. For each experiment 3 runs with different seeds has been performed. Each run has been evaluated on 10000 graphs not present in the train set.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall 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).
19

---

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 error rates).
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
All the details necessary are provided in the supplementary materials.
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, or 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 in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics httpppp:///oerrppssscppppl//////
Answer: [Yes]
Justification: authors have reviewed the NeurlPS Code of Ethics and verified their compliance.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a 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: While the paper does explicitly delineate societal impacts, the nature of the experimental setting-rooke in synthetic algorithmic tasks and abstract token lan- guages-limit, direct applicability to real-world contexts, leaving open questions about potential downstream effects, both beneficial and harmful, in broader deployment scenarios.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
20

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess 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 not tied partieular applications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out. For example, it is legitimate to point that 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 train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or 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 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 or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper addresses narrowly scoped algorithmic task busk-solving shortest path problems in DAGs with integer weights-uud using synthetic data, which significantly limits potential for misuse. As such, the authors reasonably conclude that specific safeguards for responsible release are not necessary this context.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a 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 to 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 is challenging, and many papers do not require this, but we 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: Our codebase relies on external libraries, e.g., HuggingFace and vLLM. We credit the authors of this libraries the supplementary material where we discuss our experimental setup.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
21

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperssi thood cww 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 is 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: [Yes]
Justification: The main asset provided is the code. It has been extensively commented and the parameters can be simply and clearly set using the configuration files.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question:
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in 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 NeurlPS 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 an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
22

---

Depending on 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.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to 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 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, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: An LLM has only been used for refining the writing style, editing, and formatting purposes.
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 (https://neuri)) http:e/r/eearrrgeccco///ooeeeeer hctpa///oooeeeeeeee////////..... for what should or should not be described.
23

---

sample its number of nodes uniformly from A Experimental details
A.1 Training and testing configuration
We run experiments on Phi3 [46] architecture. in consistent hyperparameter setting specified in Section 3 During training, we employ the AdamW optimizer, with weight decay of 0.1, constant learning rate 2 x 10-5, and momentum parameters 31 0.9 and B3 0.999. Training runs are terminated when the test loss exhibits consistent increase after plateauing in the minimum.
Batch sizes are defined in terms of total token count (excluding PAD tokens to ensure fair comparison across different efficiency levels 17), rather than by the number of samples, and are fixed at 16384 tokens per batch. The context length set to 4096 tokens for experiments involving reasoning traces, and to 256 tokens for standard question-ansee answer tasks.
The codebase uses the standard PyTorch and HuggingFace libraries 47 48
with all unspecified parameters set to their default values. Model performance is evaluated post-training using checkpoints saved the end of each epoch. All predictions are generated using the vI.IMM inference framework [49]
With precision being limited FP16, in a configuration with layers the memory footprint typically reaches approximately 14GB of GPU memory. Most training runs have been executed on hardware configurations featuring either an Nvidia A100 GPU with 80GB memory or an RTX4090 GPU with 24GB memory, each accompanied by 32 CPU cores.
A.2 Data generation
As described in in Section each datapoint represents a layered directed acyelic graph (DAG). Each graph instance is randomly sampled from distribution parameterized by the tuple (L, K, C, Pe where is the maximum number of layers (excluding the source), K is the maximum number of nodes in any internal layer, C' is the maximum possible edge cost (so that costs are integer-values and lie in (I,...,C)) and Pe controls the expected edge density between successive layers.
To generate a graph, we first sample the number of layers İ uniformly from the set {2...., ,.....,)) L}. The first and last layers contain exactly one node each, representing the source and the destination of the graph. For each internal layer & 1...., L K}.
Let V/8 be the set of nodes in layer f. For each consecutive pair (Ve, Ve+1) we construct a weighted adjacency matrix
A E |lWxive
With probability Pe, an entry Afy is assigned a cost drawn uniformly from {1, ......,Cy C}; otherwise +00.
After generating (49)--) in order to guarantee the existence of at least one valid path from the source to the destination, we enforce two simple connectivity constraints:
)==
1. Any node that is not in the final layer and has no outgoing edges is connected a random node in the next layer, with an edge cost drawn uniformly in [I....,.)..
2. Any node other than the source that has no incoming edges is connected to a random node in the previous layer, again with uniformly sampled cost.
Once the graph construction is finalized, it is serialized into a deterministic token sequence using custom tokenizer. In this way we generate set of unique sequences, ensuring that no graph instance is repeated while allowing for semantic graph similarities (e.g. instances that are identical up to permutation of nodes). Finally, the resulting corpus of tokenized sequences is split into training and test sets using 9:1 ratio.
24

---

A.3
Evaluation metrics
To track progress on intermediate training objectives, we compute range CoT- and answer-level metrics. While some of these were already introduced in Section Table provides complete description of all metrics used for performance evaluation.
Metric
Type
Category
Description
is possible
bool
Answer
Whether the path the answer contains valid nodes for each layer and follows the correct layer order.
cost consistent
bool
Answer
Whether the cumulative cost equals the sum of edge weights along the path.
is cost optimal
bool
Answer
Whether the reported cost equals the globally optimal one. Whether the path has exactly node per layer.
length is correct
bool
Answer
correct (or answer accuracy)
bool
Answer
Whether the answer satisfies all A-level criteria.
Number of steps
int
CoT
Number of reasoning CoTT steps (delimited by 1).
Repeated steps
CoT
Count CoT steps that repeat previously seen sub-path. Count of CoT steps that repre- sent valid sub-paths.
Possible sub-paths
int
CoT
Consistent steps
int
CoT
Count of CoT steps whose cost matches the sum the corre- sponding sub-path costs. Count of CoT steps that con- sider only current best sub- paths.
Subproblem optimal steps
int
CoT
Steps with skipped subproblem
int
CoT
Count of CoT steps that contain nodes to which current best cost is not known.
Syntax errors
int
Both CoT & Answer
Number structural or token- level errors.
Table 1: Evaluation metrics with their associated category (Answer, CoT, or both).
B
Additional results
B.1
Quality of model-generated reasoning traces
In the main text, focused the capability of our trained models provide correct answer the proposed shortest-path questions, and showed that with enough data they approach perfect accuracy. However, we have not analyzed the quality of the produced reasoning traces while this accuracy is attained. In Fig. we compare several CoT-level metrics between models trained on traces with efficiency 7 (DFS) and +5(DP). Overall, find that the models are able perfectly absorb the syntax and algorithmic logic of the training examples, mostly producing perfect traces (in correspondence the correct answers) with the expected systematic exploration order.
However, Fig. 7 (a) reveals a possible origin of the performance gap observed between v = +5(DP) and 77 5DFS) Inspecting the percentage of generated CoT steps that continue current optimal
25

---

1.0
0.5
1.0
02
0.
10
16
20
16
20
10 Epoch
16
Epoch
Epoch
(a)
(b)
(c)
0.029
2.5
2.0
0.015
0.010
0.005
0.0
Epoch
Epoch
Epoch
(d)
(f)
Figure 7: Reasoning steps metrics. Comparison of CoT-level metrics between models trained on traces with efficiency 7) = +5(DP) and = 5(FFS) Panels: (a) percentage of subproblem optimal steps, (b) percentage of repeated reasoning steps, (c) percentage of consistent steps, (d) percentage of possible sub-paths, (c) percentage of steps with a skipped subproblem, (f) average numbers of syntax errors.
sub-paths -a an optimality constraint that fulfilled by training traces-, we see that the inefficient 7) -(DFS) model learns more quickly to avoid unnecessary and suboptimal steps, while in the 7 = +5(DP) setting, this metric does not reach full convergence. This indicates that models trained efficient dynamic programming (DP) traces may still occasionally select suboptimal paths, possibly due to the random order in which same-level paths are explored in r7 = +5(DP), making their relative positions in the trace less predictable.
As an illustration, we show two correct traces below, produced for the same graph. While 7/ 5(DFS) builds trains-of-thought by chaining depth-first-search moves (here we highlight one in blue)
BoT ng n2
n0 n2 n5
4
n0
n2 m6 n8
n0
n2 n5 n8
n9
8
m0
m2 m5
m7
5
m0
m2 m6 m7 m9 6
02
n4 3 60
87
4
80 62
n7
n0
114
88
80
n2
69
88
60
no
m8
n5 2 60 n3
67
3
m0
m3 m5
n7
69
n0
m3
m5
m8
4
60 m3
m5
m8
m9
n0
m3
14
n0 m3 n4 m8 nó
m3
n4
n7
3
n0
m1 n0
m1
p6
n0
m1
n6
n8
n0
m6 m7 BaT m1
the succession of steps in the highlighted in red), reducing the auto-correlation the sequence steps:
5(DP) trace breaks the continuity of the path composition (here
BoT no
m1
m6
n0 m3
n0
n4 m3
m0 m5 4
no n5
n0
64
80
n5
68
n0
m3
n8 4 n3
07
ml
n7
n0
m3 n7
n0
n6
69
EoT
B.2 Additional statistics on CoTs
further analyze the effects of varying the efficiency temperature 7/ on Chain-of-Thousee (CoT)
length. Fig. 8 shows histograms of the number of CoT steps for +55. Notably, the distribution for
7) = (DFS) exhibits a broader range of step counts, suggesting intuitively that the v) = +5(DP)
traces should be casier fit.
26

---

30%
10%
20%
45
10%
200
400
800
50
100
CoT steps
CoT
(a)
(b)
Figure 8: Ground truth CoT length in tokens. (a) 1) 5(FSS) (b) 1 = +5((P)
n
12
log (count +
10
Addend
1)
12345
Addend
Figure 9: Distribution of integer addition.
Similarly, Fig. 9 iillustrates the distribution of integer additions encountered in typical training set for the two types of traces. While both models receive more than sufficient examples in the lower values of the matrix, where the bulk of the addition operations take place, it is clear that the model trained with v +5(PP) requires fewer addition operations learn compared to 1) 5(DFS), which would point to a simpler task acquisition for the efficient setting and, in principle, give the (DP) approach an advantage in terms of learnability.
These additional statistics further underscore the critical importance of reasoning trace structure for effective learning.
B.3 Impact of model size and data scale
The experiments presented in the main text considered a transformer architecture with 3 layers, and training datasets containing 32M-1281 tokens. In this section, explore the impact of switching training configurations by varying the number of model layers and dataset sizes. To facilitate training on larger architectures, in this comparison we adopt standard learning rate scheduler, linearly annealing starting learning rate of 5 x 10 10-4 down to 0 without warmup.
We report the results in the As shown Fig. TOja), the generalization of the 3-layer model (solid line) reaches a better peak performance compared to the fixed learning rate training, but incurs high variance. As expected, with increased computational power, the larger 6-layer model (dashed line) improves the best performance, reaching levels comparable to +5(DP), layers and 128M tokens, in Fig. Ta).
+5(PP) setting, exhibiting the largest performance variation.
27

---

1,0
Answer Accuracy
0.8
Answer Accuracy
0.8
0.4
0.4
0.
0.2
10
40
10
20
Epoch
Epoch
(a)
(b)
Figure 10: Ablation studies. (a) Comparison of the generalization performance between 3-layer model (full) and 6-layer model (dashed) trained on +-((PP with 32M tokens. (b) Comparison between 3-layer models trained on 16M (dash-dot) and a 32M (full).
We note that, while the addition of the scheduler introduces greater variance in the training runs, the relative advantage of the 1 -DDFS) model's generalization over the = +5(DP) model, presented in the main text, preserved.
Finally, in Fig. 10 b), we show the impact of halving the training budget to 16M, with a sensible 10% decrease of performance on average.
28


Reviews:
[{"review_id": "4I5F9wG20f", "reviewer": "Reviewer_RyFF", "summary": "The authors present a synthetic testbed to test how well transformers can learn to find the shortest path in a directed acyclic graph with different search strategies. They experiment with a less efficient depth-first-search-like strategy and a more efficient dynamic programming strategy. They find through extensive experiments involving training Phi3 models from scratch that transformers are able to better generalize to unseen graphs when they are trained on the less efficient search strategy.", "questions": "From Figure 2, it seems that the redundancy setting is not exactly comparable to the \\eta = -5 setting: The mean CoT length in the redundancy setting is 12% larger than that of \\eta = -5, and the variance is 25% smaller.\n\nLine 188: \"...good generalization on the larger graph instances can only be achieved when the model is allowed to produce a reasoning trace.\"\n  Since L = 7 (line 183), the model should have seen graphs with a maximum depth of 7, right? If so, then depth-7 graphs would not be \"larger graph instances.\" Or by \"larger graph instances\" did you mean the graphs with depths within the training distribution that are larger than other graphs from the training distribution? What is the distribution of graph depth of the training examples?\n\nThe analysis on the model's confidence of the next step prediction is unclear: For \\eta = 0 and \\eta = +5, isn't low confidence expected? If there are multiple valid next steps at a given point in the exploration, then the model should assign uniform probability to each of the valid next steps. In this sense, next token confidence would only be a good proxy for learnability _if the task is not too ambiguous._ How often do the exploration traces encounter points where there are more than one valid next steps (for \\eta = -5, 0, and +5)?\n\nLine 221: Why would it necessarily be the case that \"incremental steps [immediately building] upon previous steps\" would result in higher next-token confidence?\n\n\nThe paper does not make many grammatical errors, but the writing can be much improved. Some of sentences are difficult to read and can be made much clearer. I list (non-exhaustively) some of the issues below and I recommend the authors carefully re-read the paper and correct all such errors. The below list also contains some questions about the content:\n\nFigure 1: The edge costs are drawn as nodes which is misleading. I strongly suggest the authors draw the edge costs as labels rather than nodes.\n\nLine 81: Spurious hyphen?\n\nLines 87-89: (minor) These lines seem to be spaced much farther apart than other lines.\n\nFigure 2: I believe \"Effect of...on...\" rather than \"Dependency on...of...\" is closer to the intended meaning.\n\nLine 115: So does a larger or smaller value of \\eta produce more \"structurally efficient\" reasoning traces? It is not easy to understand the meaning \"structural efficiency\" if no precise definition is provided aside from the algorithm in Figure 2.\n\nLine 127: How are reasoning steps \"disregarded\"? Are they randomly removed from the reaoning trace? If so, they would have no effect on the subsequent generation of the transformer, won't they? For systematic redundancy: Is it only possible to increase the length of the CoT by an integer >= 2 (since *each* reasoning step is repeated)?\n\nLine 146: Is this the percent increase or decrease?\n\nLine 171: Duplicate \"iv)\".\n\nFigure 3a: This plot needs a legend. The colors are also somewhat random. I recommend using a gradient of three colors to better depict the sequence of 3, 5, and 7-depth graphs.\n\nLine 204: Does \"dashed\" and \"full\" refer to the plot in Figure 4a? The figure hasn't even been referenced yet, so you should avoid referring the line style in the plot here.\n\nLine 208: \"less\" -> \"fewer\"\n\nFigure 4: I strongly suggest that legends be added to the plots in this figure.\n\nLine 210: (minor) Use \"---\" or \\textemdash for em dash, and remove spaces around each dash.\n\nLines 215-218: This sentence is unclear and difficult to understand. What does \"understand\" mean here, in the context of \"harder to understand and mimic for the trained model\"? What does it mean for the model to understand an exploration order?\n\nLine 229: \"the model transitions from repeating the same reasoning steps from 20% to 3% of the times\" This is ambiguous. Does this mean that, prior to this transition point, the model is repeating steps in 20% of the validation examples? Training examples? Or are 20% of the reasoning steps repeated across all reasoning steps in all validation examples? (or training examples?)", "limitations": "See Weaknesses above. The authors acknowledge that their testbed is rather artificial and their findings may not necessarily generalize to real-world settings. However, I do believe it represents an interesting exploration in fundamental capabilities of transformers when trained with idealized data (therefore providing insight into the upper limits of transformer capabilities on this task).", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n - The testbed reveals interesting behavior where transformers learn to find the shortest task more generalizably using a less efficient search technique.\n - The paper represents an interesting exploration in fundamental capabilities of transformers when trained with idealized data (therefore providing insight into the upper limits of transformer capabilities on this task).\n\nWeaknesses:\n - The exploration is rather limited in terms of graph depth and it is unclear if the findings generalize to larger graphs/CoTs. It would be very interesting to explore the scaling trend of the inefficient vs efficient searching approaches on larger graphs.\n - Some claims are not supported by the experimental results. (see below)", "was_revised": true, "final_justification": "Overall, I do believe the paper could benefit greatly from another round of revision to improve the writing and to incorporate the proposed clarifications in the rebuttal.\n\nOne issue the authors resolved during the discussion is why they did not consider testing larger graph depths, as it is not clear whether/how their findings would generalize to larger graphs. They explain that this was due to the context limit of their model, which is 4096 tokens. They were not able to train larger models due to compute limitations. I found this explanation to be satisfactory.\n\nHowever, one issue that was not addressed was in the experiments comparing the model's accuracy with their next-token confidence. There is a potential confounder here in that the two tasks (DFS and DP) are fundamentally different: In DFS, the \"correct\" next token is often unique, whereas in DP, there are oftentimes many valid next steps. Thus, due to the difference in tasks, the model trained on DP would necessarily have lower next-token confidence, regardless of which model is more accurate. As a result, I chose not to increase my rating.", "rebuttal": "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.\n\n---\n\n**Weaknesses**\n\n- 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}$.  \n  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)).\n\n- The doubts on the validity of some claims (W2) are addressed together with the questions.\n\n---\n\n**Questions**\n\n> From Figure 2, it seems that the redundancy setting is not exactly comparable to the $\\eta = -5$ setting...\n\nIn 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.\n\n---\n\n> Line 188: \"...good generalization on the larger graph instances...\"\n\nWe 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.\n\n---\n\n> The analysis on the model's confidence of the next step prediction is unclear...\n\nWe 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:\n\n$$\n\\eta = +5 \\rightarrow 1.3262 \\pm 0.0006; \\\\\n\\eta = -5 \\rightarrow 0.4821 \\pm 0.0002; \\\\\n\\eta = 0 \\rightarrow 1.905 \\pm 0.003\n$$\n\nHowever, 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.\n\n---\n\n> Line 221: Why would it necessarily be the case that \"incremental steps...\"\n\nIn 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. \n\n---\n\n**Clarity and Stylistic Enhancements**\n\nWe greatly appreciate the reviewer’s careful attention to our work and we are going to implement all their recommendations. More specifically:\n\n---\n\n> I believe \"Effect of...on...\" rather than \"Dependency on...of...\" is closer to the intended meaning.\n\nWe 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$.\n\n---\n\n> It is not easy to understand the meaning \"structural efficiency\" if no precise definition is provided...\n\nWe 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:  \n“We define structural efficiency as the efficiency, in terms of cot length, given by varying the structure (exploration order) of the algorithm”\n\n---\n\n> How are reasoning steps \"disregarded\"?\n\nWe 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.\n\n---\n\n> Figure 3a: This plot needs a legend.\n\nWe 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).\n\n---\n\nWe agree that the sentence:\n\n> “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.”\n\nis 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.\n\n---\n\n> Lines 215-218: This sentence is unclear and difficult to understand...\n\nWe 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.\n\n---\n\nWe 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.\n\n**References**\n\n- Wang, Xuezhi, and Denny Zhou. \"Chain-of-thought reasoning without prompting.\" Advances in Neural Information Processing Systems 37 (2024): 66383-66409."}, {"review_id": "kyiHQVMiXy", "reviewer": "Reviewer_ocpL", "summary": "In a carefully controlled setting, the authors investigate the reasoning behavior of modern LLMs. By systematically altering the reasoning trajectories in training samples, they observe the models’ learning dynamics. They arrive at a surprising conclusion: LLMs are better at following structured, step-by-step reasoning, rather than finding creative shortcuts to solve problems.", "questions": "1.How was the graph data used in training and testing constructed? In particular, were there any rules governing how nodes were connected? I’m concerned the model may have learned node-connectivity patterns rather than actual reasoning rules.\n\n2.The study focuses solely on synthetic data. Do the authors expect their findings to hold on publicly available datasets? Have they tested whether the same bias appears there?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths:\n\n1.The custom tokenizer designed for the shortest-path problem, along with the experimental setup, is very novel.\n\n2.The study offers valuable insights into how Chain-of-Thought training data can be constructed in specialized scenarios.\n\nWeaknesses:\n\n1.The conclusions are based on a single synthetic dataset, which may be too narrow. The highly structured nature of the input makes the task closer to sequence prediction than genuine reasoning.\n\n2.The explanation for why structured but inefficient reasoning outperforms optimal strategies is not entirely convincing. The weaker performance of dynamic programming (DP) traces may result from limited coverage in training, as DP trajectories are less repetitive and harder to learn than DFS ones. The better results with DFS may simply reflect that such traces are more learnable for LLMs.", "was_revised": true, "final_justification": "The authors’ response resolved my confusion regarding the dataset generation process and also provided valuable insights into the interpretability of the experimental results. Although the work lacks some comparative validation on public datasets, I still consider it a solid piece of work.", "rebuttal": "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. \n\n**Weaknesses**\n\n1. 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. \n2. 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. \n\n**Questions**\n\n1. 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. \n2. 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.\n\nWe 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. \n\n\n**References**\n\n- Lehnert, Lucas, et al. \"Beyond a*: Better planning with transformers via search dynamics bootstrapping.\" arXiv preprint arXiv:2402.14083 (2024).\n- Su, DiJia, et al. \"Dualformer: Controllable fast and slow thinking by learning with randomized reasoning traces.\" arXiv preprint arXiv:2410.09918 (2024).\n- Bachmann, Gregor, and Vaishnavh Nagarajan. \"The pitfalls of next-token prediction.\" arXiv preprint arXiv:2403.06963 (2024)."}, {"review_id": "lAf5O6scz2", "reviewer": "Reviewer_JctD", "summary": "The authors build a sandbox in which a small decoder-only transformer (Phi-3) must solve shortest-path problems on layered graphs. The transformer is then trained on `question -> trace -> answer` triples and compare the effect of **efficient traces** (in which the traces are optimal bottom-up DP) vs. **inefficient traces** (in which the traces involve backtracking). Finding that the **inefficient traces** lead to better generalization, the authors argue that step-by-step backtracking better matches the inductive bias of autoregressive LMs.", "questions": "1. Have the authors tried the same experiment on another algorithmic benchmark, or on natural-language datasets (e.g., math)? Do the same trends hold?\n2. Have the authors tried the same experiment on varying model sizes? Is there a point at which inefficient traces stop being optimal?\n3. The eureka jump is intriguing. Have the authors inspected attention patterns / neuron activations before and after the jump for more insight?", "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**\n- The authors set up a clean, controlled experimental sandbox to study changes in trace structure and length.\n- By keeping the total token budget fixed, the authors are able to cleanly focus on changes in trace structure.\n- The paper is clear, well written, and original.\n\n**Weaknesses**\n- The biggest weakness of this paper is that the experiments are only done on one experimental setting (shortest-path in layered graphs), for one model (Phi3) that is **extremely** small. It is not clear if the inductive bias narrative transfers to models with B's of params and more emergent planning abilities. It is also not clear if the lesson about inefficient traces being more helpful would translate to other tasks.", "was_revised": true, "final_justification": "The authors addressed my concerns and questions; though I do think another round of revision would be valuable, I have raised my score from 4 to 5.", "rebuttal": "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. \n\n**Weaknesses**\n\nWe 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.  \nOur 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.  \nWe 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. \nRegarding 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. \n\n**Questions**\n\n1. 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. \n2. 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. \n3. 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. \n\n\nWe 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.\n\n**References**\n\n- Lehnert, Lucas, et al. \"Beyond a*: Better planning with transformers via search dynamics bootstrapping.\" arXiv preprint arXiv:2402.14083 (2024).\n- Su, DiJia, et al. \"Dualformer: Controllable fast and slow thinking by learning with randomized reasoning traces.\" arXiv preprint arXiv:2410.09918 (2024).\n- Bachmann, Gregor, and Vaishnavh Nagarajan. \"The pitfalls of next-token prediction.\" arXiv preprint arXiv:2403.06963 (2024)."}, {"review_id": "6fJDazbXCe", "reviewer": "Reviewer_Zh3k", "summary": "This work aims to understand how chain-of-thought reasoning traces and test-time compute aid reasoning performance. More specifically, they aim to understand the impact of the structure, efficiency, and length of reasoning traces on performance of a model trained from scratch on a shortest-path graph task. The authors make several observations: reasoning traces enable models to do this task at all for deeper graphs (directly outputting the shortest path works well only for short graphs). Then, inefficient depth-first search style reasoning traces work better than those reflecting an optimal dynamic programming solution. The authors attribute this to the fact that the reasoning steps follow each other more directly there, with less specific computation that has to be done for each step (each step easier to predict). They further study the impact of test-time compute through deterministic redundancy (if the model can predict where the redundancy occurs, it can use that to do additional computations). This does not help, meaning the actual steps you output matter. Finally, non-systematic structure in the reasoning traces works worst, again attributed to fact that the model cannot predict the next token accurately here (similarly for randomized redundancy). This indicates structure over content is more important in the reasoning trace.", "questions": "- The list of types of reasoning traces is a bit hard to follow, after continuing reading the paper I understood but perhaps you could already annotate which of each is the DP and DFS one (l133-l142)\n-  Line 210-211; to say that more test-time compute doesn't help, you would have to compare on graphs of the same length, do you do that? I don't see how you can get this conclusion from the $\\eta=0$ curves in fig 4.", "limitations": "Mostly properly addressed, but could discuss how training from scratch might give different results than test-time compute on pretrained models.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- Interesting and novel finding that inefficient reasoning works better than optimal reasoning traces, convincingly tied back to the fact that the intermediate steps in the inefficient traces follow more naturally from each other (each token easier to predict)\n- The paper is very clearly written, with good figures\n- Sound experimental setup,\n\nWeaknesses:\n- The results and findings would be stronger and tie more to real-world LLMs if experiments with pretrained models were done. For example through finetuning on the graph task with different style reasoning traces (essentially the same thing as done here but with pretrained models).\n- The findings would also be strengthened when an additional task would've been investigated. Right now it's unclear whether the findings would generalise beyond graph-based tasks where things like depth-first search are less obviously applicable (e.g. countdown).", "was_revised": true, "final_justification": "I remain of the opinion that we should accept this paper because the paper has interesting findings that contribute to our knowledge using a sound experimental setup. Particularly, that inefficient reasoning works better than efficient, tied to the fact that predicting the next token is easier there.", "rebuttal": "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. \n\n**Weaknesses**\n\nWe 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.  \n\nTo 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. \n\nIn 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.  \n\n**Questions**\n\n- 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. \n- 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. \n\n**On the limitations**\n\nWe 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. \n\nWe 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. \n\n\n**References**\n\n- Lehnert, Lucas, et al. \"Beyond a*: Better planning with transformers via search dynamics bootstrapping.\" arXiv preprint arXiv:2402.14083 (2024).\n- Su, DiJia, et al. \"Dualformer: Controllable fast and slow thinking by learning with randomized reasoning traces.\" arXiv preprint arXiv:2410.09918 (2024).\n- Bachmann, Gregor, and Vaishnavh Nagarajan. \"The pitfalls of next-token prediction.\" arXiv preprint arXiv:2403.06963 (2024)."}]

Author rebuttal:

Meta-review: The paper studies the efficiency of learning algorithmic reasoning tasks with auto-regressive transformers, using different types of reasoning traces. By considering a controlled setting involving shortest-path problems, the authors find that training with "inefficient" reasoning traces (i.e. resembling DFS-style strategies) can lead to better learning compared to "efficient" traces (e.g. using DP-style strategies, which lead to shorter traces), in the sense that the model learns more quickly and generalizes better to larger graphs. While the setting is somewhat narrow, and some of the claims could be strengthened in the final revision (in particular, see the comment on confidence metrics for DFS vs DP by reviewer RyFF), overall, the reviewers agreed that this is an interesting and important question, and that the experiments thoroughly validate this hypothesis. I thereby recommend acceptance.
Decision: Accept (poster)