Imagine you're teaching someone to navigate a city by having them recite turn-by-turn directions one intersection at a time. At each fork, they get graded only on the next immediate turn — not whether the full route actually reaches the destination. For small neighborhoods, this works fine. But scale up to a real city grid and the learner starts making locally plausible turns that lead nowhere, because the supervision signal never rewarded route-level coherence. That's the core problem this paper diagnoses and fixes for transformer models learning shortest-path search on graphs. The committed claim: prior work (notably Bachmann & Nagarajan, 2024) showed that standard next-token prediction (NTP) transformers hit a hard scaling wall when learning to output shortest paths on unseen graphs — accuracy collapses as graph size grows. Frydenlund et al. identify two independent causes of this failure and fix both. First, multi-token prediction (MTP) — predicting several future tokens simultaneously — provides a supervision signal that captures route-level structure rather than just local next-hop decisions. The authors give a theoretical argument grounded in information-theoretic reasoning: MTP's loss landscape has fewer degenerate optima because it forces the model to commit to longer lookahead windows. Second, they show that the standard tokenization (one token per node ID) is itself a bottleneck. By introducing alternative tokenizations — including digit-level and character-level encodings of node IDs — they reduce the vocabulary's collision surface and let the model distinguish structurally distinct nodes more easily. The key architectural insight is that these two fixes are orthogonal. MTP helps regardless of tokenization, and better tokenization helps regardless of whether you use NTP or MTP. The paper demonstrates this with a clean factorial design across tokenization schemes and prediction horizons. On Erdős–Rényi random graphs, Watts–Strogatz small-world graphs, and Barabási–Albert preferential attachment graphs, the combination of MTP + alternative tokenization consistently learns shortest-path generation at graph scales (100+ nodes, varying edge densities) where prior methods plateau near zero accuracy. Crucially, MTP's benefit is shown to be topologically agnostic — it doesn't lean on any particular graph structure to work. The baseline ladder is clear and honestly stated. The direct predecessor is Bachmann & Nagarajan (2024), which established the scaling wall. This paper doesn't just beat that wall — it explains why the wall exists and removes both of its load-bearing components. The models used are standard decoder-only transformers (GPT-style), not exotic architectures. The innovation is entirely in the training objective and input representation, which makes the result more portable. Integrity is solid for a synthetic-task paper. The graphs are procedurally generated with controlled parameters, so there's no data leakage. The factorial experimental design (MTP vs NTP × multiple tokenizations × multiple graph families × multiple scales) is clean and the ablations are genuine — you can see which factor does what. The limitation is inherent to the genre: this is a synthetic reasoning benchmark, not a deployment. The graphs are algorithmically generated, shortest paths are computed by BFS/Dijkstra for ground truth, and the models never touch real-world routing or knowledge graphs. The milestone question is where things get interesting. The paper breaks through to ~100-node graphs. Real-world graph reasoning tasks — knowledge graph completion, circuit routing, social network analysis — operate at 10K–1M+ nodes. The gap is at least two orders of magnitude. The key next number is whether MTP + tokenization tricks can reach 1K-node graphs with maintained accuracy, which would start to make the approach relevant for mid-scale practical problems. The authors don't make inflated claims about this. The obvious successor experiment the authors didn't run: testing on weighted graphs with non-uniform edge costs (i.e., actual Dijkstra problems, not just BFS). The paper restricts to unweighted shortest paths. The honest read is (a) — this is a scope decision to keep the contribution clean, and adding edge weights would complicate both the tokenization story and the theoretical argument. But it's the natural next step, and whether MTP's advantage survives weighted edges is not obvious.
