PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Arvid Frydenlund, FuTe Wong, Katherine Lambert, Frank Rudzicz

arXiv:2610.31439v1cs.LGcs.CL

TL;DR

Can language models find shortest paths in unseen graphs, and why does learning become difficult as graphs scale? The paper analyzes supervision and tokenization, then reports that multi-token prediction and alternative tokenizations improve learning, with benefits that are orthogonal. Together, these methods support stable learning at larger scales.

  • Problem

    Prior work found that language models increasingly struggle to learn shortest-path search as graph size and path length scale.

    Source: §1 · p. 2

  • Method

    The paper analyzes multi-token prediction and develops alternative tokenizations, including structural annotation, to address supervision and tokenization issues.

    Source: §4 · p. 6, §7 · p. 9

  • Results

    MTP outperforms NTP on average across scales and methods, with the difference increasing as k and |N| grow; MTP and alternative tokenization address different issues.

    Source: §6 · p. 7

  • Takeaways & Limitations

    MTP’s supervision advantages and alternative tokenizations together support learning latent multihop graph search at scale.

    Source: §6 · p. 7, §7 · p. 9

    Path-star graphs can be solved under suitable conditions, so their results should not be treated as a generalizable limitation of NTP.

    Source: §7 · p. 10

Abstract

from arXiv · show

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.

1 INTRODUCTION

The paper uses shortest-path generation on unseen graphs to study whether language models can perform latent multihop computation, without semantic shortcuts. It investigates how supervision and tokenization contribute to the task’s scaling difficulty.

1 INTRODUCTION

  • Graph search models multihop reasoning as traversal through an unknown latent graph, with branching factor and path length shaping the search space.The controlled task aims to isolate structural computation from semantic shortcuts in natural-language data.Source: §1 · p. 1
  • Prior work found learning increasingly unstable beyond about 50 nodes, motivating investigation of supervision and tokenization as contributors to the scaling wall.The paper extends analysis of next-token prediction, then develops alternative tokenizations to address the problem.Source: §1 · p. 2

1.1 THE SHORTEST-PATH TASK

  • The task trains on shuffled edge lists and predicts a shortest path node by node, using semanticless synthetic graphs and evaluating on unseen graphs.This in-context setting excludes explicit scratchpads and inference-time search procedures.Source: §1.1 · p. 2

1.2 THE SEQUENTIAL SUPERVISION PROBLEM WITH NEXT-TOKEN PREDICTION

  • Under NTP, the Clever Hans Cheat can absorb supervision at non-choice nodes; MTP supplies denser, mixed-hop supervision, addressing both supervision density and hop difficulty.Mixed multihop training can also be created by sampling shorter paths or interior target nodes.Source: §1.2 · pp. 3–4

2 CHARACTERIZING SAMPLE EFFICIENCY WITH GENERAL TOPOLOGIES

Under NTP, only choice nodes on a path require latent multihop reasoning, so supervision depends on graph topology and sampled path. MTP adds future-token predictions that provide denser, mixed-hop supervision with nearly topology-independent advantages.

2 CHARACTERIZING SAMPLE EFFICIENCY WITH GENERAL TOPOLOGIES

  • NTP’s sequential sample efficiency is the number of choice nodes on the path, because the Clever Hans Cheat absorbs supervision at other nodes.A choice node has multiple unseen neighbors that could continue the path; in undirected graphs, interior nodes of degree at least three qualify.Source: §2 · p. 4
  • Multiple choice nodes implicitly provide mixed-hop subtasks, but NTP’s supervision and hop difficulty depend on the topology and sampled path.Branching at every step with d-ary trees can maximize supervision but requires graphs of size |N| = d^k.Source: §2 · p. 4

2.1 THE SEQUENTIAL SAMPLE EFFICIENCY OF MULTI-TOKEN PREDICTION

  • MTP’s skipped predictions require multihop computation even at non-choice nodes, increasing supervision beyond NTP for the same sampled path.The RITF implementation uses a dynamic future window and a Plackett-Luce loss.Source: §2.1 · pp. 4–5
  • MTP has optimal sample efficiency and hop mixture, with quadratic supervision terms dominating its residual linear topology dependence as path length grows.Its advantages are nearly topology-independent, unlike NTP’s strong topology dependence.Source: §2.1 · p. 5

3 THE CAUSAL CONSTRAINT, SPARSITY, AND FRAGMENTED ROUTING

Causal models must route information across shuffled edges in a sparse graph, but many disconnected components persist until most edges have been processed. The section proposes a node-list input as a consistent scaffold and tests whether it helps beyond bypassing routing constraints.

3 THE CAUSAL CONSTRAINT, SPARSITY, AND FRAGMENTED ROUTING

  • In sparse graphs with shuffled edges, fragmented routing defers information flow until most edges are processed, exhausting causal models’ sequential computation.The causal constraint permits attention only to prior tokens, compounding the routing challenge.Source: §3 · pp. 5–6
  • Adding a node list after the edge list provides a consistent scaffold that accumulates edge information, unlike simply repeating the edge list.The node list is ordered by each node’s first appearance in the shuffled edges.Source: §3 · p. 6
  • Comparing causal and prefix LMs with and without the node list tests whether its benefit extends beyond bypassing causal routing constraints.The experiments label node-list inputs “+ N” against the [Q, E] baseline.Source: §3 · p. 6

4 POSITIONAL EMBEDDINGS AND PERMUTATION SENSITIVITY

Positional embeddings distinguish repeated node tokens but compromise permutation invariance. The section introduces structural annotation, which uses unique structured tokens for edges and nodes without positional information in those inputs.

4 POSITIONAL EMBEDDINGS AND PERMUTATION SENSITIVITY

  • Positional embeddings distinguish recurring node IDs, but make edge-list representations sensitive to token ordering.Permutation invariance is a suitable inductive bias because edge ordering is irrelevant to the task.Source: §4 · p. 6
  • STAN replaces sequential edge annotation with structured edge tokens, using the edge marker instead of positional embeddings and node markers for node-list tokens.The query and target retain sequential positional embeddings for output generation.Source: §4 · p. 6
  • STAN reduces the sequential tokenization of the edge list to one-third its original length.The method changes how the input sequence is presented rather than primarily changing the model.Source: §4 · p. 6

5 METHODOLOGY

The experiments evaluate shortest-path learning across graph topologies and measure token-level, sequence-level, and task-level accuracy. Models use curriculum sampling over hop lengths and graph sizes, with small language models and repeated trials.

5 METHODOLOGY

  • Experiments cover Erdős–Rényi, Euclidean, and path-star graphs, with next-token prediction used during inference.Each experiment uses five trial seeds and evaluates 10,000 instances.Source: §5 · p. 6
  • Evaluation reports per-token accuracy, per-sequence accuracy, and task accuracy for generating any valid shortest path.Sequence accuracy requires all tokens to be correct; task accuracy allows non-unique shortest paths.Source: §5 · p. 6
  • Small models use 11 layers and learned positional embeddings, with curriculum sampling over hop lengths and graph sizes.Training runs up to 75,000 steps with batches of 1,000 and stops early above 95% task accuracy.Source: §5 · pp. 6–7
  • Non-sparse graphs are excluded because they support only tiny shortest paths, limiting scalability experiments over hop length.The section describes this as a constraint on investigating scalability with k.Source: §5 · p. 6

6 EXPERIMENTS, RESULTS, AND DISCUSSION

The experiments find that combining STAN with a node list improves learning and scaling, while multi-token prediction (MTP) provides additional gains that grow with graph scale. On path-star graphs, MTP enables learning across scales, while the hop-length mixture can affect whether models escape learning lockout.

6 EXPERIMENTS, RESULTS, AND DISCUSSION

  • Adding the node list has the largest ablation effect, while STAN reduces trial variance and restores the expected relationship between convergence and hop length.The node-list improvement also appears in prefix LMs, and STAN improves causal LMs despite their lack of true permutation invariance.Source: §6 · p. 7
  • STAN and node-list input let prefix LMs solve larger Erdős–Rényi graphs consistently in a fraction of the steps, with expected scaling behavior.The experiments extend graph sizes through 125 nodes; the corresponding prefix-LM results are shown in Figure 3.Source: §6 · p. 7, Figure 3 · p. 8
  • MTP outperforms next-token prediction on average across scales and methods, with the gap increasing as hop length and graph size grow.The results support MTP as complementary to the alternative tokenization methods.Source: §6 · p. 7

6.1 PATH-STAR GRAPHS

  • On path-star graphs, next-token prediction with STAN and a node list consistently scales to 65 nodes, but adding MTP makes learning trivial across the tested scales.Path-star graphs show the largest disparity between next-token and multi-token prediction, consistent with their adversarial structure for next-token prediction.Source: §6.1 · p. 8, Figure 5 · p. 9
  • Path-star learning difficulty rises sharply rather than gradually with hop length and graph size, as some seeds fail at k = 9 and d = 8.Three seeds learn and two fail; restricting mixed multihop training to k′ values from 6 through 9 causes all tested models to fail.Source: §6.1 · p. 8, Figure 6 · p. 9
  • The sharp learning transitions reflect lockout: once easier hop-length samples stop contributing loss, models can lose the mixture needed to generalize to larger tasks.The authors report that MTP induces an implicit mixed multihop training signal and does not lead to this lockout.Source: §6.1 · pp. 8–9
  • Even when path-star models reach high accuracy, fewer than 1% of targets may contribute to loss without meeting the task-accuracy threshold.The authors suggest these models may have failed to generalize and may be locked out of learning from easier samples.Source: §6.1 · p. 8

7 CONCLUSION AND LIMITATIONS

The paper finds that MTP improves supervision across graph topologies, while MTP combined with alternative tokenizations enables learning at much larger graph sizes. It cautions that path-star results are topology-specific and that the reasons the tokenization changes work remain open.

7 CONCLUSION AND LIMITATIONS

  • MTP improves supervision through increased supervision density, mixed-hop supervision, and better learning dynamics, with these benefits holding regardless of graph topology.The paper extends the path-star analysis to general topologies using a formal notion of choice nodes.Source: §7 · p. 9
  • MTP’s benefits also appear on Khops, Khops-Gen, and a BFS scratchpad variant, supporting—but not proving—the conjecture that they extend to multihop reasoning generally.The paper reports that MTP’s topology-independent benefits were unexpected.Source: §7 · p. 9
  • The BFS scratchpad is learnable, but its sequence length makes training impractical and it does not overcome the scaling wall.It also turns the latent solution graph into a linear chain, reducing the task to the multihop backtrack of Khops-Gen.Source: §7 · pp. 9–10
  • The authors motivate +N as a response to fragmented routing under causal constraints and STAN as a response to positional embeddings breaking permutation invariance.Ablations show gains from +N in prefix LMs and from STAN in causal LMs, countering those proposed explanations.Source: §7 · p. 10
  • The node list (+N) and structural annotation (STAN), together with MTP, enable consistent learning at graph sizes beyond prior limits, though why they work so well together remains open.A 2.5× increase in size was achieved with one-third as many training steps.Source: §7 · p. 10
  • Path-star graphs are an adversarial topology for NTP, so their results should not be treated as a generalizable NTP limitation or as a benchmark of arbitrary reasoning.The paper reports that NTP can learn at moderate scales under correct conditions, while MTP is more efficient and that efficiency matters at scale.Source: §7 · p. 10

AI USE STATEMENT

The authors report using generative AI tools for code, proof, illustration, and writing tasks, with human review of the AI-assisted work.

AI USE STATEMENT

  • LLMs assisted with coding in small sections at a time, and humans verified the code.LLMs also helped verify proofs, leading to improvements.Source: AI USE STATEMENT · p. 10
  • AI tools helped create illustrations, while plots were made manually to ensure integrity.Source: AI USE STATEMENT · p. 10
  • AI assistance and Grammarly were used for writing and proofreading, and the authors reviewed all AI-assisted work and accepted responsibility for the final content.Source: AI USE STATEMENT · p. 10

REPRODUCIBILITY STATEMENT

The reproducibility statement identifies the online dataset and PL-RITF cost function as the main engineering challenge. The appendix defines notation and distinguishes mixed multihop training from curriculum terminology.

REPRODUCIBILITY STATEMENT

  • The online dataset and PL-RITF cost function are the main engineering challenge; these components are released, with the complete repository to follow upon acceptance.Source: REPRODUCIBILITY STATEMENT · p. 10

A NOTATION AND ABBREVIATIONS

  • The notation defines graph, path, and vocabulary symbols, and abbreviations include NTP, MTP, SSE, and task-specific accuracy measures.SSE is the number of input-target supervision pairs contributing to learning in one instance; ACC, SACC, and TACC denote per-token, sequential, and task accuracy.Source: A NOTATION AND ABBREVIATIONS · pp. 31–32

A.1 A NOTE ON MMHT AND CURRICULUM TERMINOLOGY

  • The paper uses mixed multihop training (MMHT) as a general term for inner- and intra-sample data mixing, distinct from curriculum learning’s usual focus on sample order.The authors also use a true curriculum sampling algorithm for path lengths.Source: §A.1 · p. 32

B FURTHER DISCUSSION OF CONTRIBUTIONS, LIMITATIONS, AND SCOPE

The discussion attributes the scaling breakthrough to orthogonal contributions from MTP and alternative tokenizations, while clarifying which explanations remain unresolved. It frames graph search as a controlled model of multihop reasoning.

B FURTHER DISCUSSION OF CONTRIBUTIONS, LIMITATIONS, AND SCOPE

  • MTP attains optimal sequential sample efficiency and hop mixture; its residual topological dependence is linear, making it nearly topology-independent as k grows.The paper introduces a probabilistic listwise Plackett-Luce formulation of Ranking-into-the-Future.Source: B FURTHER DISCUSSION OF CONTRIBUTIONS,… · pp. 32–33
  • +N addresses fragmented routing by accumulating edge information, while STAN makes edges unique super-tokens to remove positional leakage.Fragmented routing arises from causal masking interacting with graph sparsity and edge-list shuffling; positional embeddings break task permutation invariance.Source: B FURTHER DISCUSSION OF CONTRIBUTIONS,… · p. 33
  • Stable learning reaches |N| = 125 in about 1/3 the steps; STAN and +N provide the largest empirical gains, with MTP adding orthogonal benefits.Prior work could not stably learn beyond 50 nodes; MTP beats NTP across scale, with the gap growing with k and |N|.Source: B FURTHER DISCUSSION OF CONTRIBUTIONS,… · p. 33
  • Across Khops, Khops-Gen, and BFS scratchpad tasks, MTP benefits extend beyond shortest-path search, while BFS scratchpads remain unscalable and collapse the reasoning graph into a linear chain.Mixed multi-length training is necessary for learning Khops-Gen.Source: B FURTHER DISCUSSION OF CONTRIBUTIONS,… · p. 33
  • Ablations show that +N and STAN help beyond their motivating hypotheses, but do not establish how much fragmented routing or permutation sensitivity explains their gains.The ablations establish tokenization as a cause of the scaling wall, while leaving open which tokenization property is responsible.Source: B FURTHER DISCUSSION OF CONTRIBUTIONS,… · p. 34
  • Out-of-distribution evaluation is beyond this in-domain scaling study; testing length generalization would require new models and could confound results through changes to embeddings or computation.The authors use learned embeddings to avoid adding inductive bias and note that static models cannot scale to arbitrary k.Source: B FURTHER DISCUSSION OF CONTRIBUTIONS,… · p. 35
  • Topology coverage focuses on cases supporting long paths, while other graph tasks raise tokenization choices that this work does not benchmark.Dense and small-world graphs mostly have short paths, and deep trees make long paths computationally prohibitive.Source: B FURTHER DISCUSSION OF CONTRIBUTIONS,… · p. 35

C GRAPH SEARCH AS A THEORETICAL MODEL OF MULTIHOP REASONING

  • The theoretical framing defines multihop reasoning through a graph induced by a world model and distinguishes two learning settings with different research questions.The section states and justifies the model's claims, then specifies additional assumptions for the study's setting.Source: C GRAPH SEARCH AS A THEORETICAL MODEL… · p. 37

C.1 DEFINING A MULTIHOP REASONING TASK

This section frames multihop reasoning as traversal of a latent reasoning graph, formalizes graph search, and distinguishes in-context from in-weights learning. It motivates controlled synthetic tasks and specifies assumptions to isolate structural traversal from shortcuts and other confounds.

C.1 DEFINING A MULTIHOP REASONING TASK

  • Multihop reasoning is a path from question q to answer a through a graph induced by W, whose topology may be latent and is not known in advance.The same definition supports in-context learning, where W varies across instances, and in-weights learning, where W is fixed and can be memorized.Source: §C.1 · p. 37

C.2 THE UNDERLYING CLAIMS

  • The paper’s five claims connect multihop tasks to reasoning graphs and traversal, identify search as one common traversal, and adopt graph search over arbitrary graphs as the theoretical model.The first two claims follow from the task definition, search is a type of traversal, and generality is required because W is arbitrary.Source: §C.2 · pp. 37–38

C.2.1 CLAIMS 1, 2, AND 3

  • Prior work supports reasoning graphs and traversal through explicit graph construction, graph-surfacing methods such as CoT, and direct search, though shortcut correlations can produce answers without traversal.The task requirement concerns what must be done, not necessarily how a model achieves the answer.Source: §C.2.1 · pp. 38–39

C.2.2 CLAIMS 4 AND 5

  • Graph search models arbitrary topology while isolating traversal because finding a path depends on graph connectivity, not node meaning; the paper makes these theoretical commitments explicit.This avoids confounding traversal with retrieval, entity resolution, or language generation, while allowing future work to state which claims it adopts.Source: §C.2.2 · pp. 39–40

C.3 OUR INSTANTIATION

  • The experimental setup requires latent single-pass traversal, shortest-path outputs, shuffled edges, semanticless nodes, and unique training graphs to rule out alternative solutions.Latent traversal excludes enumeration and scratchpad search; shortest paths constrain output length, shuffled edges prevent ordering cues, semanticless nodes remove semantic shortcuts, and unique graphs prevent memorization and spurious subgraph correlations.Source: §C.3 · pp. 40–41

C.4 THE IN-WEIGHTS MODEL

  • In-weights learning permits memorization and changes learning dynamics: Noroozizadeh et al. (2026) scaled path-finding to graphs with up to 5 × 104 nodes, with multihop composition amortized into inference-time lookup.This setting is distinct from the in-context task, and the paper notes that semanticless, unique-graph assumptions exclude the usual fixed knowledge-base QA setting.Source: §C.4 · p. 42
  • In-weights graphs may be stored so fully that inference needs no traversal, whereas unseen in-context graphs require their structure to be computed at inference.Thus, failure in an in-weights task may reflect failure to store structure rather than inability to traverse; the authors recommend distinguishing the settings because results support different conclusions.Source: §C.4 · pp. 42–43
  • Semantic representations are optional in in-weights tasks, but retaining semantics makes shortcut auditing necessary and has restricted cited studies to two hops.Wang et al. (2026a) found natural-language forms produced noisy scaling trends, while random identifiers yielded clear, reproducible trends, attributed to lexical information in entity and relation names.Source: §C.4 · p. 43
  • Zhong et al. (2025) found multi-token prediction improved in-weights path prediction over next-token prediction, especially for paths requiring more inference beyond training observations.They attribute the gain to a transfer layer learning adjacency-matrix powers; unlike the present unseen-graph setting, those powers reside in the weights for a single graph.Source: §C.4 · p. 43

D.1 GRAPHS AND LLMS

  • Because language models process sequences, graph tasks require linearization, but no canonical encoding exists and the chosen node order affects performance.Prior work also reports that models often ignore explicit topology in favor of node semantics, while Park et al. (2025) found in-context graph representations from random-walk encodings and Lepori et al. (2026) found models may then fail to use them downstream.Source: §D.1 · pp. 43–44

D.2 CONTROLLED SETTINGS AND SYNTHETIC DATA

  • Training models from scratch on varied synthetic graphs removes prior-knowledge and shortcut explanations, making structural traversal the only route to correct answers.The authors present this as a controlled environment for studying multihop reasoning, where success is evidence of latent structural computation.Source: §D.2 · p. 44
  • Yang et al. (2025b) and Balesni et al. (2024) illustrate how pretrained-model studies leave confounds and data limitations that constrain conclusions about latent multihop reasoning.Yang et al. (2025b) filtered co-occurrences using a proxy corpus and studied only one- and two-hop questions; Balesni et al. (2024) found fine-tuned models required one pretrained, non-synthetic fact to compose two synthetic facts.Source: §D.2 · pp. 44–45

D.3 EXPRESSIBILITY AND LEARNABILITY OF GRAPH AND OTHER COMPOSITIONAL TASKS

This section examines whether transformers can express graph-search solutions and whether training can learn them, relating these questions to model capacity, task and input design, and multi-token prediction. It also connects MTP to structured-prediction and masking approaches, describing how supervision, causal constraints, tokenization, and ranking loss shape graph search, with STAN and Plackett–Luce ranking as complementary design choices.

D.3 EXPRESSIBILITY AND LEARNABILITY OF GRAPH AND OTHER COMPOSITIONAL TASKS

  • Expressibility asks whether a model with specified resources can compute a task; learnability asks whether it acquires the solution under training conditions, so expressibility alone does not ensure learning.Sanford et al. (2024a) classify shortest path as a search task expressible with L=O(log N) and m=O(N^1/2+ϵ), without pause tokens.Source: §D.3 · p. 45

D.5 ALTERNATIVE INPUTS OR TOKENIZATIONS

  • STAN reuses ‘|’ across edges and ‘/’ across nodes; its edge-token reduction to one-third means its improvement cannot be explained solely by raw token count.The authors note that added node positions may change expressibility, while shortest path is also expressible without pause tokens given sufficient width.Source: §D.3 · p. 46, §D.5 · p. 49

D.3 EXPRESSIBILITY AND LEARNABILITY OF GRAPH AND OTHER COMPOSITIONAL TASKS

  • ≈6M-parameter models trained from scratch solve the harder in-context shortest-path task, whereas Sanford et al. (2024a)’s pre-trained 60M-parameter model only approached optimal performance.The comparison concerns shortest-path performance; the passage does not give a numerical score for either model.Source: §D.3 · p. 47
  • On path-star graphs, models fail to generalize across k′ because each k′ is a separate sub-skill, despite in-domain-only data and efforts to avoid spurious correlations.The passage contrasts this finding with explanations based on training-data correlations and distribution shifts.Source: §D.3 · p. 47

D.4 THE PATH-STAR TASK AND PATH-STAR GRAPHS

  • Because introducing MMHT or changing graph topology alters path-star learnability, the authors caution against using path-star as a benchmark for novel methods; its purpose is understanding task difficulty.The passage notes that some studies change these task conditions without considering their effects on learnability.Source: §D.4 · p. 48

D.6 MULTI-TOKEN PREDICTION

  • MTP creates multiple future-token targets per input; ordered Plackett-Luce ranking preserves sequence order unlike BoW, but requires a unique-target future window.The passage says repeated targets can be masked out to address this limitation.Source: §D.6 · pp. 49–50
  • Suleymanzade et al. (2026) use teacher-distilled reasoning traces and handcrafted weighted BoW losses, suggesting MTP's near-to-far token ordering may not be universal.The passage relates their problem to multi-label MTP and notes that Frydenlund et al. (2022) showed it can be converted to ranking, with no single weighting best in all situations.Source: §D.6 · p. 51

D.7 MASKING, NON-AUTOREGRESSIVE MODELS, AND DISCRETE DIFFUSION MODELS

  • MTP, masking, non-autoregressive models, and masked discrete diffusion can induce multi-hop supervision similarly, but matching cost terms does not establish equal expressibility or learnability.The passage relates NAR and MDM's masking-based losses and non-causal architectures to the paper's prefix-LM approach.Source: §D.7 · p. 51

E A VISUALIZATION OF THE SEQUENTIAL SUPERVISION PROBLEM UNDER NTP AND THE BENEFITS OF MTP

  • MTP induces dense supervision connections that restore non-choice nodes, unlike NTP, and this supervision is shown as topology-invariant.These latent connections are outside the source-side prefix, so they do not support the copy-head circuit and require multihop learning.Source: Figure 10 · p. 54, E A VISUALIZATION OF THE SEQUENTIAL… · p. 54

F A VISUALIZATION OF THE CAUSAL CONSTRAINT, SPARSITY, AND FRAGMENTED ROUTING

G A VISUALIZATION OF TOKENIZATION AND CAUSAL PARAMETERIZATION

  • STAN moves edge structure into the annotation channel, making each edge one position and reducing the edge-list length to one-third; with prefix-LM, it enables permutation invariance.Prefix attention lets the query attend to the whole graph, while only the path remains causally masked.Source: G A VISUALIZATION OF TOKENIZATION AND… · p. 56, Figure 12 · p. 56

H RANKING-INTO-THE-FUTURE WITH PLACKETT-LUCE

  • MTP naturally yields a listwise ordering of future tokens, and the paper uses a Plackett-Luce loss that renormalizes probabilities after each ranked token.The MTP head uses the second-to-last layer to model a sequential rather than semantic distribution, and is active only during training, leaving inference unchanged.Source: H RANKING-INTO-THE-FUTURE WITH… · pp. 57–59

I PROOF OF OPTIMAL MTP SEQUENTIAL SAMPLE EFFICIENCY

MTP loss terms correspond to non-trivial path segments, yielding optimal sequential sample efficiency and a skew toward shorter hop lengths. Masked discrete diffusion models (MDM) supervise a subset of those segments, with masking choices shaping their term count and hop coverage.

I PROOF OF OPTIMAL MTP SEQUENTIAL SAMPLE EFFICIENCY

  • MTP covers every non-trivial subpath, giving k(k + 1)/2 terms before excluding the trivially predicted final target.The full loss therefore has k(k + 1)/2 − 1 terms, versus k − 1 for its diagonal.Source: I PROOF OF OPTIMAL MTP SEQUENTIAL… · p. 60
  • The optimality result assumes autoregressive models and a tokenization where each token represents one hop.The authors state that the result applies to any task with MTP.Source: I PROOF OF OPTIMAL MTP SEQUENTIAL… · pp. 60–61
  • MTP terms distribute linearly toward shorter hops: hop length h appears k − h + 1 times, and length 1 is k times as frequent as length k.The authors suggest this skew may benefit learning but say they cannot isolate its effect empirically.Source: I PROOF OF OPTIMAL MTP SEQUENTIAL… · pp. 60–61

I.1 MASKED DISCRETE DIFFUSION MODELS SUPERVISE A SUBSET OF THE SUB-PATHS SUPERVISED BY MTP

  • The MDM comparison analyzes supervised subpaths under a Markovian assumption, not learnability; extra conditioning may compensate for fewer terms.The authors caution that they do not claim this analysis transfers to tasks where relevant information is distributed across many tokens.Source: §I.1 · pp. 61–63
  • Every MDM term maps to an MTP term for the same subpath, but MDM supervises at most k − 1 terms and has strictly worse sequential sample efficiency.MDM also conditions on the right boundary, unlike the corresponding MTP term.Source: §I.1 · p. 62
  • Full masking yields a uniform mixture of hop lengths 1 through k − 1, while MTP weights shorter subpaths more heavily.Full masking reaches the maximum MDM term count and hop length; partial masks reduce the longest attainable hop.Source: §I.1 · p. 62
  • Each additional observed interior node reduces MDM's term count by one, to k − 1 − r across r such nodes.Shorter masked blocks also restrict the hop lengths covered; their union may omit lengths from 1 through k − 1.Source: §I.1 · p. 62
  • The authors expect MDM to outperform NTP on multihop tasks because masking retains many of MTP's supervision benefits.They also connect this account to MDM's success on other symbolic multihop reasoning tasks.Source: §I.1 · p. 63

J EXTENDED EXPERIMENTAL DETAILS

This appendix details the model, training, graph-generation, and compute settings, then reports additional causal-LM and Euclidean-graph results. In Euclidean graphs, MTP improves learning only at the tested scale of 125 nodes.

J EXTENDED EXPERIMENTAL DETAILS

  • The experiments use 11-layer, 256-dimensional, four-head LMs and train on three graph topologies with sampled paths and graphs across specified size ranges.Training uses a curriculum for ERG and EG, but not PSG; it is smoothed to reduce catastrophic forgetting.Source: J EXTENDED EXPERIMENTAL DETAILS · p. 63

J.1 COMPUTATION

  • The study reports 2,900 experiments and estimates 34,800 GPU hours, or $13,572–$17,052.30 at the stated GPU prices.The authors say reduced variance across seeded trials could allow fewer trials in future work.Source: §J.1 · p. 64

K.1 FULL-PAGE VERSIONS OF THE MAIN RESULTS FIGURES

  • The appendix reproduces the main-results figures at full-page size without changing their data.Table 1 breaks down the main-experiment run counts by figure, without double-counting overlaps.Source: §K.1 · p. 64, Table 1 · p. 64

K.2 CAUSAL LM BASELINE

  • With causal LMs, STAN consistently outperforms the baseline, while the node list helps most at low k and not at high k compared with STAN.The authors report clearer trends for causal than prefix LMs and attribute the performance difference between model types to parameterization.Source: §K.2 · pp. 64, 70

K.3 RESULTS ON EUCLIDEAN GRAPHS

  • MTP improves learning on Euclidean graphs with prefix LMs only at 125 nodes.The authors expect this trend would continue on larger graphs.Source: §K.3 · p. 70

K.4 RESTRICTED MMHT PATH-STAR GRAPH EXPERIMENTS

Restricted hop-length mixtures fail on the tested path-star settings, while the auxiliary Khops experiments show that denser supervision and task-length mixtures matter in related multihop tasks. Khops-Gen provides a sequential-generation variant for directly applying MTP.

K.4 RESTRICTED MMHT PATH-STAR GRAPH EXPERIMENTS

  • All tested path-star models restricted to higher k′ values failed, unlike the full-MMHT trials where all d = 6 trials and some d = 8 trials solved the task.The restricted range was k′ ∈ [6, 9]; full MMHT used k′ ∈ [3, 9].Source: §K.4 · p. 70, Figure 22 · p. 71

L AUXILIARY MULTIHOP TASKS: KHOPS, KHOPS-GEN, AND BFS SCRATCHPADS

  • Across auxiliary tasks, MTP benefits extend beyond shortest-path search, while BFS scratchpads introduce tokenization and scaling difficulties and simplify the underlying computation.The scratchpad’s traversal order collapses latent search into a linear-chain traversal.Source: L AUXILIARY MULTIHOP TASKS: KHOPS,… · p. 71

L.1 KHOPS

  • Khops composes induction-head mappings for k hops and trains a causal language model to output the final k-hop label at each eligible sequence position.It is sequential labelling, with k supplied as part of the task description.Source: §L.1 · p. 71

L.1.1 CAUSAL LMS AND MIXED MULTI-LENGTH TRAINING

  • Causal Khops implicitly mixes task lengths because each position has a different amount of preceding context, yielding lengths from 1 to N.The task relies on causal left-to-right ordering and is not defined for prefix LMs.Source: §L.1.1 · p. 73

L.1.2 A SURROGATE FOR MTP ON KHOPS

  • The Khops ranking-loss surrogate supplies existing intermediate composition labels together per instance, increasing supervision density rather than adding new labels.This changes batch-level inter-supervision into instance-level intra-supervision.Source: §L.1.2 · p. 73

L.1.3 KHOPS EXPERIMENTS AND RESULTS

  • Without MMHT, Khops scales poorly; the ranking loss outperforms the baseline, while front noise makes learning harder, especially as k increases.The authors suggest disrupting causal Khops’ implicit MMLT may explain the front-noise effect.Source: §L.1.3 · p. 74, Figure 24 · p. 74

L.2 KHOPS-GEN

  • Khops-Gen generates a full compositional trace from one starting symbol, ordering targets from hardest to easiest to preserve the need for multihop reasoning.Unlike Khops, it lacks implicit MMLT, so the experiments explicitly sample different N′ values.Source: §L.2 · p. 75

L.2.1 KHOPS-GEN EXPERIMENTS AND RESULTS

Khops-Gen becomes harder as sequence length and hop count increase, but MTP improves learning at scale; explicit task-length mixtures also matter. BFS scratchpad experiments expose additional tokenization challenges and show that MTP helps on the partial backtracking task.

L.2.1 KHOPS-GEN EXPERIMENTS AND RESULTS

  • MTP significantly improves Khops-Gen learning at scale, while the task becomes harder as N and k increase.The experiments are reported in Figure 27, with a simplified version in Figure 28.Source: §L.2.1 · p. 76, Figure 27 · p. 77
  • Khops-Gen scales poorly without explicit MMLT; the authors suggest learned leftward transitions can shrink the effective state space, while uniform N′ sampling may not be optimal and nonuniform sampling remains untested.Hop depth and task length are distinct difficulty axes in this setting.Source: §L.2.1 · p. 76

L.3 BFS SCRATCHPAD

  • BFS-SP has two generation phases: produce a breadth-first-search scratchpad, then backtrack through it to generate the shortest path.The backtracking phase is nearly computationally equivalent to Khops-Gen.Source: §L.3 · pp. 76–77

L.3.1 TOKENIZATION MATTERS FOR SCRATCHPADS TOO!

  • A shared depth marker avoids failures caused by distinct depth markers, while reversing adjacency lists or adding the BFS queue prevents repetition mistakes at the cost of longer scratchpads.The final tokenization also orders exploration by edge-list appearance to make the scratchpad deterministic.Source: §L.3.1 · p. 78

L.3.2 BFS-SP EXPERIMENTS AND RESULTS

  • On the partial BFS-SP task, MTP makes learning easier at scale; on the full task, generating the scratchpad and path is learnable but takes nearly twice as many steps, and MTP does not outperform NTP.The partial task gives only the scratchpad and asks for the shortest path; the full task also requires generating the scratchpad.Source: §L.3.2 · p. 78

L.4 SCRATCHPADS SUBSTANTIALLY CHANGE THE SHORTEST PATH TASK AND BREAK THE THEORETICAL MULTIHOP REASONING MODEL

A BFS scratchpad supplies traversal structure that changes shortest-path search into backtracking on a linear chain, so success on that task does not establish that the original search problem was solved. The section also discusses k-lookahead and how multiple valid shortest paths affect training targets.

L.4 SCRATCHPADS SUBSTANTIALLY CHANGE THE SHORTEST PATH TASK AND BREAK THE THEORETICAL MULTIHOP REASONING MODEL

  • BFS-SP changes the task topology into a search tree and then a linear backtracking chain, replacing choices among graph continuations with traversal on a fixed structure.The authors characterize this as substituting a strictly simpler problem, not solving the original planning problem.Source: §L.4 · p. 79, Figure 31 · p. 81

M THE k-LOOKAHEAD ISSUE

  • A path’s length may overstate required search: in general graphs, the start may not be a choice node, so fewer than k hops can suffice.The authors note that general topologies do not permit the same controls used in the restricted path-star setup.Source: M THE k-LOOKAHEAD ISSUE · p. 82

N MULTIPLE SHORTEST PATHS AND SEMANTIC LABEL SMOOTHING

  • When multiple shortest paths exist, NTP’s single sampled target can cause training-loss spikes; multi-label cross-entropy treats every valid next node at a split as a target.The correction applies to NTP; the authors do not apply it to MTP, where conflicted targets are a smaller fraction of the loss.Source: N MULTIPLE SHORTEST PATHS AND SEMANTIC… · p. 82

O NOTES ON SOURCE-SIDE – FULL-SEQUENCE – TRAINING WITH NTP

The section argues that source-side full-sequence NTP may help models learn unseen path-star graphs by rewarding legal graph generation. The path-star constraints can supply multihop reasoning signals, though the authors expect this signal to be limited and not to scale.

O NOTES ON SOURCE-SIDE – FULL-SEQUENCE – TRAINING WITH NTP

  • Trainin et al. (2026) and the authors propose that source-side training may help on unseen path-star graphs by rewarding legal graph generation rather than graph-specific memorization.The authors identify legality, specifically, as the critical aspect of the proposed mechanism.Source: O NOTES ON SOURCE-SIDE – FULL-SEQUENCE… · p. 84
  • Noroozizadeh et al. (2026) studied in-weights learning on one graph, whereas Trainin et al. (2026) and this work study in-context learning on unique, unseen path-star graphs.For unseen graphs, memorizing a specific graph would induce spurious correlations; full-sequence NTP predicts the entire input, including the source-side prefix.Source: O NOTES ON SOURCE-SIDE – FULL-SEQUENCE… · p. 84
  • Path-star legality requires the start node to have degree d, arm-interior and arm-final nodes to have degrees 2 and 1, respectively, and each arm to contain k unique nodes.The setup fixes arm count d and arm length k, giving |N| = dk + 1.Source: O NOTES ON SOURCE-SIDE – FULL-SEQUENCE… · p. 84
  • Respecting arm-specific node counts or identifying a missing edge can require multihop traversal, unlike enforcing the total node budget, which requires only counting.For a missing edge (u, v), counting can detect that an edge is absent, while traversal identifies which edge is missing.Source: O NOTES ON SOURCE-SIDE – FULL-SEQUENCE… · p. 84
  • The authors expect this legality-based learning signal to be minimal and not to scale, while suggesting it may make path-star tasks learnable at limited scale.They describe the signal as a direction for future work.Source: O NOTES ON SOURCE-SIDE – FULL-SEQUENCE… · p. 84

Related papers

Loading 2610.31439v1…