acceptodds
Under review as a conference paper at ICLR 2027

Multi-Token Prediction and Alternative Tokenization Improve Learning Latent Multi-Hop Graph Search at Scale

Abstract

Given an unseen graph, a start node, , and an end node, , can a language model generate the shortest path from to ? Prior work has found that models fail to learn this task as the graphs scale. We show that this failure has two causes: the supervision signal and the tokenization. First, we theoretically establish and empirically demonstrate the effectiveness of multi-token prediction (MTP), and show that the benefits of MTP are topologically agnostic. Second, we introduce alternative tokenizations and show that the two causes are orthogonal. Using these methods, we break through the scaling wall observed by prior work, consistently and stably learning to solve the task at scales far beyond previous limits.

Primary area:
interpretability and explainable AI
Keywords:
Language Models, Graph Search, Multi-Token Prediction, Multi-Hop Reasoning, Latent Reasoning, Training Objectives, Learning Dynamics, Controlled Setting, Synthetic Data, Path-Star Task, Tokenization, Transformers, Search

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_3fZvOpenReview ↗
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 nn future tokens. Please provide a sensitivity analysis of nn 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
AuthorsOpenReview ↗

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.

AuthorsOpenReview ↗

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.

Reviewer_pUtCOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies why transformer language models fail to scale on the controlled task of shortest-path graph search, which is used as a theoretical model of latent multihop reasoning. The authors generalize existing path-star analyses to general topologies, introduce choice nodes and sequential sample efficiency, and show that next-token prediction supervision is lost to topological shortcuts, which leaves sparse supervision that depends strongly on topology. They then propose multi-token prediction to increase supervision density, induce mixed-hop supervision, and improve learning dynamics. Theoretically, they prove that multi-token prediction covers all non-trivial subpaths, achieves optimal sequential sample efficiency, and that its topological dependence is dominated by a quadratic term as the number of hops grows, which makes it nearly topology-independent. The authors also identify routing problems caused by the causal constraint and the loss of permutation invariance caused by positional embeddings, and propose two tokenization modifications: a node list and structural annotation. Experiments use Erdős–Rényi, Euclidean, and path-star graphs with small models of eleven layers and two hundred fifty-six dimensions. The authors report stable learning extended from about fifty nodes to one hundred twenty-five nodes, and up to one hundred fifty-one nodes on path-star graphs. They also show that the advantage of multi-token prediction over next-token prediction grows with the number of hops and graph size. Auxiliary experiments cover Khops, Khops-Gen, and a BFS scratchpad. These show that the benefits of multi-token prediction are not limited to shortest-path search. The authors also argue that a BFS scratchpad reduces the latent reasoning graph to a linear chain and breaks the theoretical model.

Critical strengths
  1. The choice-node analysis extends earlier path-star-specific observations to general graph topologies and gives a concrete explanation of how effective NTP supervision depends on topology and the sampled path. The corresponding analysis of MTP provides a principled account of why future-token supervision can substantially improve learnability.

  2. The paper goes beyond small adversarial path-star examples and demonstrates stable learning at substantially larger graph sizes. The ablations also support an important distinction between improving the supervision objective and improving the graph representation/tokenization, with the two interventions providing complementary gains.

Critical weaknesses
  1. The mechanism behind the strongest tokenization interventions is not sufficiently isolated. The node-list augmentation is motivated by routing limitations caused by causal attention, while STAN is motivated by permutation sensitivity. However, the paper's own ablations show that the node list also helps prefix LMs, and STAN also helps causal LMs, which weakens these original explanations. STAN additionally changes token granularity and reduces the edge-sequence length by roughly a factor of three. The interventions clearly work, but it remains unclear which representational or computational property is responsible for most of the gain.

  2. The connection to general multi-hop reasoning should be stated more cautiously. The controlled graph-search setting is useful for isolating latent multi-hop computation, but several parts of the analysis rely on a close correspondence between output tokens and graph hops. The paper itself notes that this correspondence does not directly hold for natural-language reasoning. I therefore view the conclusions as strong for latent symbolic graph search, but only suggestive for multi-hop reasoning more broadly.

Questions for authors
  1. Can the authors more directly isolate the three coupled modifications in structural annotation: permutation invariance, reduction of sequence length to one third, and the structural annotation channel?
  2. Multi-token prediction on the shortest-path task has a natural alignment between each token and one hop, so the future window aligns with hops. How do the authors propose to design hop-aligned targets for natural language or other multihop tasks?
1 comment

We thank the reviewer for their review and time. We appreciate that they mentioned the extra tasks we explored (Appendix L), even though they are in the appendix, as they took a lot of effort. We also appreciate the reviewer pointing out that MTP and the tokenization are "two interventions providing complementary gains", as this is a very important point for the paper.

W1/Q1: We agree, and we state it as our most significant limitation (L.1731). Both issues stem from the causal constraint, and our use of causal and prefix LMs is an ablation designed to test the motivating hypotheses (L.1735–1744). The reviewer correctly points out that further isolation is hard: (a) performance is best with both +N and STAN, which we already ablate in isolation, and (b) we know of no way to ablate STAN itself further. Permutation invariance requires making each edge a single unique super-token, which we do in a minimal way via structural annotation, and this necessarily reduces the sequence length (L.1745). Thus, the three modifications are therefore intrinsically coupled. Even without a full explanation of why they work, the results clearly show their gains empirically, and they show that prior work did not account for an otherwise undiagnosed tokenization problem, which is significant to researchers working on this problem.

W2: As the reviewer correctly points out, we use graph search as a theoretical model of latent multihop reasoning. We inherit this from prior work and outline the connection in the introduction (L.037–050), but, due to space, this is only a brief outline. The full justification is in Appendix C (L.1879), especially C.3 (L.2079–2150), which states the five assumptions of our instantiation. Each assumption is made to prevent an alternative way of producing a correct answer without traversal, making it so that task performance is direct evidence of multihop search (L.2081–2087, L.2128–2130). Then, for the connection to natural language, we give an argument for why isolating traversal is informative about multihop search as a whole (L.2038–2043). If a model does better on natural language than on our isolated task, the gain cannot have come from traversal, so it came from bypassing it, i.e. a shortcut. If it does worse, the added natural-language aspects are the cause, which is a different question from the one we set out to study and is worth studying on its own. As you point out, we are also explicit that our theoretical results hold because of the correspondence between tokens and hops (L.1718–1721), and we point to prior work on non-contiguous windows (Liu et al., 2025; L.1720).

We agree that the first point should be explained better in the main paper, and we will use the extra page to state the above argument there (which is already in the appendix). We will also extend the conclusion to restate that these results are for a synthetic setting and point to the appendix for the various issues natural language introduces, just to reclarify our claims for readers.

Q2: We wish to purse this for future research and because we are in the age where people are using AI to autogenerate papers, we have to be a bit cagy about how we plan to approach this. The main thing is that MTP by itself is not limited to contagious windows, which we cite to former work. Thus, this correspondence is not an inherent issue with MTP, which we think is a sufficient statement for this paper itself.

AI disclosure: We drafted the rebuttal ourselves and used AI to clean up the reply and make it more succinct.

Reviewer_PWJdOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper investigates why small transformers hit a "scaling wall" when learning shortest-path search over unseen graphs — a controlled proxy for latent multihop reasoning. It attributes the failure to two separable causes. Auxiliary tasks verify MTP's benefits beyond shortest path.

Critical strengths
  1. The choice-node formalism cleanly generalizes the CHC beyond path-stars, and the sub-path coverage proof gives the clearest explanation to date of why MTP helps. The MDM-subset result is a nice bonus that unifies two literatures.

  2. The paper designs falsifiable ablations for its own motivating hypotheses and reports their falsification.

  3. Scale and rigor of empirical practice.

Critical weaknesses

1 The tokenization half of the paper is empirical without mechanism, and the confounds are acknowledged but not disentangled. The paper's own ablations falsify both motivating hypotheses, leaving STAN/+N's effectiveness unexplained. 2. No comparison among MTP instantiations, and the strongest claim (topological agnosticism → general multihop reasoning) is left untested.

  1. The theory's predictive grip on the observed baseline behavior is weaker than presented.
Questions for authors

Please see the weaknesses above.

1 comment

We thank the reviewer for their review and their understanding of the paper.

We especially appreciate the reviewer pointing out the scale and rigour of our empirical experiments, and taking the time to look at the MDM results (Appendix I.1), even though they are deep in the appendix.

W1: We agree, and we state it as our most significant limitation (L.1731). Three points: (a) This is the flip side of your second strength (Strength 2), as we designed the ablations to be falsifiable and reported the outcome rather than hiding it. (b) Both motivating hypotheses are theoretical properties of the setting, which we show hold (§3, §4), so the motivation is not merely "empirical". (c) By "falsify" we meant that the hypotheses do not fully account for the gains, which is very different from not accounting for them at all. Both hypotheses stem from the causal constraint, and prefix LMs clearly outperform causal LMs, so we do know the causal constraint hinders learning. Finally, even without a full explanation, the results clearly show that tokenization is a major cause of the scaling wall in prior work, which is important for researchers working on this problem.

W2: This is two separate points.

(a) The core scientific question is whether MTP improves learning compared to NTP. We answer yes: it halves the cost of learning on ER graphs (L.376) and makes path-star graphs trivial at all scales (L.411). Showing this requires only one MTP method that instantiates the theory (Eq. 3, L.231–233). Comparing different MTP methods would answer a different question, which is “what is the best MTP method?”, and would amount to benchmarking MTP variants on a single task (L.1828). That is outside our scope, and a meaningful comparison would need to span a wide body of tasks, which is well beyond this work. Thus, even though we introduce a novel MTP method, we do not need to compare to other ones.

(b) We explicitly label the extension to general multihop reasoning tasks as a conjecture that is left untested (L.242–245, L.1722). It follows directly from our theoretical analysis, and we explain why testing it is hard and requires its own work (L.244–245, L.1718–1721). We agree this is a strong and exciting outcome of this work, and we plan to pursue it in future work.

W3: We agree that SSE does not account for all aspects of learnability, and we state this in the paper (L.1774–1784). However, path-star graphs are an adversarial, extreme setting where these other variables matter little (due to only branching once). Our theory predicts that path-star graphs will show the largest gap between NTP and MTP (L.412), and this is what we observe. Our NTP scales well beyond prior work, and our MTP makes the task trivial at all scales (L.410–411). These results go well beyond prior work precisely because we fixed the tokenization, which shows that prior results were limited by an orthogonal source of error.

AI disclosure: We drafted the rebuttal ourselves and used AI to clean up the reply and make it more succinct.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Paper revision.

We again thank the reviewers for their time and work, and we truly appreciate the feedback.

A) Updated paper. We have uploaded a new version with the three clarifying modifications we mentioned in the rebuttals, all marked in blue: (1) the introduction further discusses the relation to the natural language setting, (2) the figures now clarify that each bar is a single seeded trial, and (3) the conclusion re-grounds the reader in the motivation of the paper. We have left extra space for any requested final changes, and otherwise we will use it to enlarge the figures.

B) Reviewer-meta phase. As this phase starts, we ask the reviewers to consider whether we have addressed their concerns. We feel like most of the concerns and questions were about scope, and we have explained why the scope needs to be limited as presented.

As Reviewers PWJd and pUtC pointed out, we do have one major limitation: we cannot fully explain the success of the tokenization methods we introduce, despite having valid motivating hypotheses and ablations designed specifically to test these hypotheses (and per PWJd's strength 2, we are candid about this). Despite this, our results show large empirical gains at scale compared to prior work. This in itself shows that tokenization was an otherwise undiagnosed problem in prior work, which future researchers need to consider.

We do not think this limitation is cause for rejection. We would ask reviewers to consider that currently the rates indicate a 'borderline accept ' and that the next step up in rating means a "clear accept", which does not mean that a work is perfect or free of limitations. If we have addressed your other concerns, we ask that you consider a change to your score.

Again, thank you for the reviews.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.