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

Riccardo Alberghi Elizaveta Demyanenko [email protected] [email protected] Luca Saglietti Luca Biggio [email protected] [email protected] · 2025

Read On the Bias of Next-Token Predictors Toward Systematically Inefficient Reasoning: A Shortest-Path Case Study by Riccardo Alberghi Elizaveta Demyanenko [email protected] [email protected] Luca Saglietti Luca Biggio [email protected] [email protected] (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-05362.txt.

Introduction

Riccardo Alberghi, Elizaveta Demyanenko, Luca Biggio, and Luca Saglietti study how training traces shape reasoning in language models, in a paper from 2025. More test-time compute helps hard problems but can add waste. Reasoning works best when it is systematic, step by step.

To isolate the effect, the team built shortest-path tasks on layered graphs. Small transformer models trained on neat, optimal solution traces faced models trained on longer traces with backtracking. Both groups saw the same training budget. Surprisingly, the messy-trace models generalized better to new graphs. The result questions the push for perfect training chains. Some wandering in training data may teach stronger search habits.

Catalog record

CREATORRiccardo Alberghi Elizaveta Demyanenko [email protected] [email protected] Luca Saglietti Luca Biggio [email protected] [email protected]
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE46 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-05362

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On the Bias of Next-Token Predictors Toward Systematically Inefficient Reasoning: A Shortest-Path Case Study Riccardo Alberghi Elizaveta Demyanenko [email protected] [email protected] Luca Saglietti Luca Biggio [email protected] [email protected] 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, with the same training-token budget, models trained on inefficient traces 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. 1 Introduction Modern LLMs have made remarkable strides in tasks requiring reasoning and multi-step problem solving [ 1 , 2 , 3 , 4 ] . Increasing evidence demonstrates that the performance of these models significantly improves when their reasoning unrolls in a step-by-step fashion, following CoTs reminiscent of how humans build their internal cognitive processes [ 5 , 6 , 7 , 8 ] . Another milestone in the rapid development of LLMs is represented by the test-time-compute paradigm [ 9 , 10 , 11 ] , driven by the intuition 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 [ 12 , 13 , 14 ] , code generation [ 15 , 16 ] , and scientific inquiry [ 17 , 18 ] . Despite such progress, reasoning remains an elusive concept—difficult to define precisely and challenging to study in the wild. How to teach machines to reason effectively, generalize across domains, and adapt to novel problems continues to be a fundamental open question. Motivated by the need for a well-defined and interpretable setting to characterize reasoning in transformers, and inspired by [ 19 ] , we turn to a controlled algorithmic task (see Fig 1 ): a synthetic shortest-path problem on layered graphs. Each problem instance—posed as a question to a transformer—consists of a source-to-target graph with integer edge costs; the model is tasked with answering with any minimum-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 a 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 to 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 a synthetic layered-graph shortest path task with a custom language format, enabling rigorous experiments on reasoning trace efficiency. The task serves as a 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 (problem instance) and answer (optimal path) substantially improves performance, in line with the behavior of modern LLM on problem-solving 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 it is 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 on the prediction of the next token given the context: 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. n0 n1 n2 n3 n4 2 1 3 2 1 (a) (a) (b) (c) (c) (d) Tokenization Question BoS l1 [ n0 n1 2 | n0 n2 1 | ] l2 [ n1 n3 3 | n2 n3 2 | ] l3 [ n3 n4 1 | ] Efficient trace BoT n0 n2 1 | n0 n1 2 | n0 n1 n3 5 | n0 n2 n3 3 | n0 n2 n3 n4 4 | EoT Inefficient trace BoT n0 n1 2 | n0 n1 n3 5 | n0 n1 n3 n4 6 | n0 n2 1 | n0 n2 n3 3 | n0 n2 n3 n4 4 | EoT Answer n0 n2 n3 n4 4 | EoS (d) (b) Figure 1: Reasoning in the shortest-path problem. (a) Example of a layered DAG with integer edge costs. The nodes are labelled top-to-bottom, left-to-right, ‘n0’ and ‘n4’ representing the source and the destination of the path. The optimal path, with a cumulative cost 1+2+1=4 , is highlighted in purple. A human reading the graph would backtrack before discovering the cheaper ‘n0 \to n2 \to n3 \to n4’ path—mirroring the strategy the model ultimately favors. (b) We introduce custom tokens to uniquely represent the graph structure (question), the trace of the solver algorithm (efficient/inefficient 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 a model trained on optimally efficient (dynamic-programming like) traces and a model trained on inefficient (depth-first-search like) traces, with a corpus of 200 K question-trace-answer examples. The inefficient reasoning traces are 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 on efficient vs inefficient traces, displaying an inductive bias of the transformer toward learning the latter. 2 Problem Setup As a testbed for our reasoning experiments, we consider a 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,C,p_{e}\} , respectively

Read the complete text