- Rating
- 4(+1)
- Confidence
- 2
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper addresses a scaling bottleneck and training instability when training a language model in finding shortest paths on graphs. The authors establish theoretically and demonstrate empirically the effectiveness of multi-token prediction (MTP). They generalize the “Clever Hans” shortcut using choice nodes and show that MTP provides many more training signals. Importantly, the paper notes that MTP helps but does not resolve scaling on its own. To address the scaling problem, the authors propose adding a node list (+N) and STAN encoding, which stabilizes training and breaks through the existing scaling wall.
Critical strengths
-
The paper proposes MTP + STAN + N, which breaks through the scaling wall reported in prior work, a milestone for training language models on shortest-path finding.
-
It supports MTP, STAN, and +N with both empirical results and theoretical analysis.
-
The writing and organization are strong: the goal and the MTP / STAN / +N methods are clearly stated and explained in depth.
Critical weaknesses
-
Limited benchmark graph topologies. Although the authors argue that MTP is topology-agnostic, the empirical evaluation covers only three families: Erdős–Rényi (ERG), Euclidean (EG), and path-star (PSG), leaving other important topologies unexamined
-
Limited reflection on real-world application. The study trains small LMs on synthetic and semantic-free graphs at a scale that is modest relative to graph data in many real-world settings.
-
Limited baselines. Most experiments compare variants of the same baselines with and w/o MTP, STAN, and +N. In Appendix D.4, the authors listed many existing approaches for the path-star task, including diffusion methods, RL, and novel architectures, but none are included in a side-by-side comparison.
Questions for authors
-
In Figures 2–4, each group of horizontal bars includes a small vertical bar. Can the author clarify what they are for in the caption of each figure?
-
In Figure 2, some runs show Baseline + MTP failing to converge while Baseline alone succeeds. Can the authors analyze these failure cases and explain when MTP negatively impacts convergence?
-
In Figure 6, 2 out of 5 seeds fail to converge and remain at roughly 0.55–0.6 SACC. Can the author provide further analysis and explanation on this?
-
While MTP + STAN + N exceeds prior scaling limits (125 nodes on Erdős–Rényi, 151 on path-star), but training stability and collapse modes at larger scales are not discussed in depth. In fact, 125–151 nodes are far below typical real-world graph sizes. A deeper analysis of when and how training collapses (even with the full method) would help guide future work toward practical graph scales.
-
The authors state that shuffling the edge list avoids leaking structural information. How are node IDs assigned? If IDs follow generation or traversal order (e.g., order of first appearance or BFS from the start), could IDs themselves encode structure despite shuffled edges?
-
As described, MTP generalizes NTP to predict up to future tokens. Please provide a sensitivity analysis of on training stability across graphs with different properties (size, density, topology).
-
Lines 302–303, the paper uses ERG, EG, and PSG. Can the authors evaluate the MTP, + N and STAND on other common graph topology families, such as trees, small-world (Watts–Strogatz), or scale-free (Barabási–Albert)?
-
From a graph machine learning perspective, what remains unclear to me yet is why finding the shortest path is chosen as a task for LM:
- Classical methods such as Dijkstra’s, Bellman–Ford, and Floyd–Warshall already solve shortest-path problems and are typically more efficient and more interpretable than a learned LM. What distinct advantage does LM-based shortest-path learning offer in this setting?
- If the goal is to help LM gain structural understanding of graphs, how does learning shortest paths support standard graph learning tasks, such as edge/node/graph classification or regression, subgraph- and cluster-level problems, and eventual graph foundation models built on LMs?
Classifying the above questions would build a bridge between this line of research and graph learning, providing insight for future work to build a graph foundation model with LM.
2 comments
Rebuttal Part 2
Q1. Each vertical bar is a single-seeded trial, as stated at L.307 (5 trial seeds per experiment) and in the Fig. 2 caption (L.354, however, this not stated well). With the extra page, we will state this explicitly in each of the Fig. 2–4 captions.
Q2. Baseline results without the tokenization fix are very noisy (L.322, L.327). Both NTP and MTP models can get caught in plateaus that they have difficulty leaving, so a Baseline + MTP run can fail where a Baseline run happens to succeed. The tokenization methods strongly reduce such behaviour.
Q3. This is expected behaviour, and is easiest to explain with prior work. Bachmann & Nagarajan (2024) did not train on mixtures of arm lengths, i.e. they did not use MMHT. For a graph with, say, d = 5 arms, a model that fails to learn the task converges to guessing among the arms, giving 1/5 = 20% accuracy. The same thing is happening in Fig. 6. However, we train on a mixture of arm lengths and numbers of arms, so the failures do not fall on clean values such as 1/d but it will converge on a specific value based on a given mixture.
Q4. This is beyond the scope of this paper. We directly consider prior work, which failed at 50 nodes, and we go well beyond that.
Q5. Node IDs are randomly assigned. Nodes are sampled from a global node vocabulary and represented by one-hot IDs, so they carry no relationship to one another (L.083–086). This is justified in Assumption 4 (L.2124–2128). This is done specifically to avoid the potential issue you are describing.
Q6. This is a valid request, and one we wish we could have done such experiments. However, as with additional topologies, it would significantly increase the number of experiments, since each value of n would require training a new set of models. Instead, we developed an MTP method that allows n = k (L.310–312). This setting is the best for our main scientific question: how MTP improves over NTP. Window-size experiments would address a secondary question: how much the window size matters in practice. Since the differences between NTP and MTP depend on topology, we would also need to repeat such experiments across topologies to draw any conclusions.
Q7. Addressed above in our response to W1/Q7.
Q8. This goes back to the motivation of the paper. We ask why LMs struggle with this task, which is itself a surrogate for multihop reasoning (L.025–050). We are interested in it because it helps explain why multihop reasoning is hard to learn. For this reason, we study this graph task in particular, not graph tasks in general. The fact that classical algorithms solve it more efficiently is not relevant, since the goal is not to build a shortest-path solver (L.027–029).
We are glad that the reviewer is interested in how this bridges to graph learning and graph foundation models. We believe our results, particularly how MTP improves learning and how to improve tokenization, will interest such research, but building such models is well beyond the scope of this paper.
Again, we thank you for your review; we can tell you spent a lot of time on it, and we greatly appreciate it.
AI disclosure: We drafted the rebuttal ourselves and used AI to clean up the reply and make it more succinct.
Rebuttal Part 1
We thank the reviewer for their time and review, and we appreciate them pointing out that work breaks the scaling wall and stabilizes training, which were large issues with prior work. We also very much appreciate the engagement with work in terms of the question asked.
We think that several of the weaknesses and questions come from reading our paper as a traditional benchmarking paper, which it is not (L.027–029, L.1826–1830). Our purpose is to understand why a controlled task, which serves as a surrogate for multihop reasoning in language models, is hard to learn. We inherit this setting from prior work (L.043–050). The other two reviewers acknowledged this in their summaries, which we think accounts for the difference in the questions asked.
W2/W3/Q4 We think that your reading is a natural one for a reader not familiar with the prior work, so we want to be explicit about the impact of the paper independent of the listed weaknesses. We are solving a specific problem found in prior work, which is why we do not consider other tasks such as real-world applications. Bachmann & Nagarajan (2024) is highly cited as showing a limitation of NTP in an adversarial setting. Their results were empirical and striking, as NTP failed to learn the task at very small graph sizes. We show the limits of that limitation. Our theory shows exactly when to expect such failures in general topologies, and we show that once the tokenization issue is fixed, NTP learns path-star graphs well beyond what prior work reported (L.406–410), which is strong counterevidence to claims that NTP is insufficient to learn to plan. We then show that, once the tokenization is fixed, MTP makes the task trivial at all scales (L.411). For this reason, we explicitly argue that path-star graphs should not be used to benchmark novel methods (L.2495–2497). That is, we ask "why are path-star graphs difficult to learn?" instead of "what is the best method for learning them?", which turns out to be an uninformative question given the correct settings. As such, we do not treat other methods as baselines. Likewise, another work that we build on, Saparov et al. (2025), was published at ICLR under the title "Transformers Struggle to Learn to Search". We show that the struggle is largely due to tokenization. Our work therefore refines the conclusions of prior work, which is an important part of the scientific process. These do not require considering other methods for baselines or considering other tasks to demonstrate.
W1/Q7 (other topologies). We agree that additional topologies would be valid, but enumerating graph families is not feasible, and we think it would add little in terms of impact. We already consider three topologies in the main experiments, which is more than prior works. Our main inquiry is scale, specifically path length, since our object of study is multiple hops. Dense and small-world graphs are uninformative, since most paths in them are short (L.1814–1816). Trees are the best topology for learning under NTP, but they are unscalable, since long paths require exponentially many nodes (L.1816). Each of our ≈2900 experiments trains a model from scratch, which, in total, in a large cost (L.311; J.1). We do not believe any particular topology would be a counterexample to our theory, and without such a reason, there are strong diminishing returns in checking off topologies.
Note that these listed issues are contrary to reviewer PWJd, who listed the scale and rigour of our experiments as a main strength, which we believe holds within the setting we explore.
We expect other readers to have a similar reading, so to avoid this, we will restate the main motivation of the paper in the conclusion to better ground them with the additional page.