aiqbench analysis
This paper tests whether language models can learn shortest-path search on unseen graphs, a task where prior work reported failure as graph size grew. The authors attribute that failure to two separate factors, the training supervision signal and the tokenization scheme, and report that fixing both extends learnability well beyond earlier limits. For readers, the useful takeaway is the diagnostic approach and the claim that the two fixes are orthogonal. Results on a synthetic task still need to be checked for transfer to less structured, real-world reasoning problems.
Multi-Token Prediction and Alternative Tokenization Improve Learning Latent Multi-Hop Graph Search at Scale
arXiv:2610.31439v1 Announce Type: cross Abstract: Given an unseen graph, a start node, $s$, and an end node, $t$, can a language model generate the shortest path from $s$ to $t$? 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.
Abstract:Given an unseen graph, a start node, $s$, and an end node, $t$, can a language model generate the shortest path from $s$ to $t$? 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.
Machine Learning (cs.LG); Computation and Language (cs.CL)
arXiv:2610.31439 [cs.LG]
(or arXiv:2610.31439v1 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2610.31439 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 215 words
Related coverage
Language Models are not Equally Robust to Non-Canonical Tokenization across Languages
arXiv · Jul 30, 2026
Architecture Alignment With Sparse Priors in Tabular Foundation Models
arXiv · Sep 30, 2026
FlowBlock: Wavefront-Parallel Decoding for Self-Correcting Diffusion Language Models
arXiv · Jul 21, 2026
[AINews] LLMs can read & write neural network weights: "Weight Space Programming" cuts Autoresearch out of the RSI loop
Latent Space · Nov 3, 2026