Generalization in LLM Problem Solving: The Case of the Shortest Path
Authors: Yao Tong
Jiayuan Ye
Anastasia Borovykh
Reza Shokri
Venue: ICLR 2026 Poster (2026)
Keywords: Compositional generalization
problem solving
Primary area: alignment, fairness, safety, privacy, and societal considerations

Abstract: Whether language models can systematically generalize remains actively debated. 
Yet empirical performance is jointly shaped by multiple factors such as training data, training paradigms, and inference-time strategies, making failures difficult to interpret.
We introduce a controlled synthetic environment based on shortest-path planning, a canonical composable sequential optimization problem. 
The setup enables clean separation of these factors and supports two orthogonal axes of generalization: ***spatial transfer*** to unseen maps and ***length scaling*** to longer-horizon problems.
We find that models exhibit strong spatial transfer but consistently fail under length scaling due to recursive instability.
We further analyze how distinct stages of the learning pipeline influence systematic problem-solving:
for example, data coverage sets capability limits; reinforcement learning improves training stability but does not expand those limits; and inference-time scaling enhances performance but cannot rescue length-scaling failures.

Published as a conference paper at ICLR 2026
GENERALIZATION IN LLM PROBLEM SOLVING: THE CASE OF THE SHORTEST PATH
Yao Tong' Jiayuan Ye!
Anastasia Borovykh Reza Shokri'.3
National University of Singapore
CCapital Fund Management GGoogle Research
I (yyotoong, jiayuan, reza } @comp. nus. aauu..du.... edu. sg Panastasia www..sww...ooo.........mmm com
ABSTRACT
Whether language models systematically generalize remains actively debated. Yet empirical performance is jointly shaped by multiple factors such as train- ing data, training paradigms, and inference-time strategies, making failures dif- ficult to interpret. We introduce a controlled synthetic environment based on shortest-path planning, a canonical composable sequential optimization problem. The setup enables clean separation of these factors and supports two orthogo- nal axes of generalization: spatial transfer to unseen maps and length scaling to longer-horizon problems. We find that models exhibit strong spatial transfer but consistently fail under length scaling due to recursive instability. We fur- ther analyze how distinct stages of the learning pipeline influence systematic problem-solving: for example, data coverage sets capability limits; reinforce- ment learning improves training stability but does not expand those limits; and inference-time scaling enhances performance but cannot rescue length-scaling failures. Code is available at htttt:://// htttts://github...tt wtwp:///.coooo/rraatttttttteeeee projjec__225__eeee 11mm
lms
INTRODUCTION
Despite rapid progress post-training methods (Tie et al./ [025 Guo al. 2025 Yao al. 2023
Peng et al. 2023 Wei et al. 2021) and reasoning benchmarks (Balunović et al., 2025 Rein et al.
2024
Jain et al.
2024 Jimenez et al. 2024), remains unclear and actively debated (Zhao et al.
2024 Lampinen al. 2025 Xu et al. 2024 Liu et al.) 2025b Xu et al. 2024 Ramesh et al. 2023
Dziri et al. 2023 whether language models can systematically generalize.
A central challenge is that performance reasoning benchmarks is jointly influenced by multiple factors, including training and testing data properties (Wold et al., 2025 Chang et al. (2025), training paradigms such as supervised fine-tuning (SFT) reinforcement learning (RL) Yue et al. 2025b
Wu et al.; Liu et al. 2025b a). and inference-time strategies (Wang et al. 2022 et al, 20236
Mudgal al. (023). Consequently, observed reasoning failures may arise from insufficient data coverage, training dynamics that fail to induce the underlying optimization rules, or inference pro- cedures that cannot effectively express capabilities already present in the model. Moreover, natural benchmarks often make it difficult to determine whether model truly generalizes, as the differences between training and evaluation settings are not cleanly controlled. For instance, it often unclear whether test tasks require genuinely new skills or can still be solved using patterns observed during training. and whether the training and test distributions are truly disjoint.
To address these challenges, we construct a controlled synthetic environment grounded in a well- defined class of problems: composable sequential optimization problems (SOPs). Many structured reasoning and planning tasks (e.g., problems solvable via dynamic programming) can be viewed as composable SOPs, where solving a task requires composing a sequence of locally valid decisions, each influencing subsequent decisions, such that the entire sequence satisfies a global objective. Among such tasks, shortest-path planning provides a canonical instantiation with globally verifi- able objective and unambiguous optimal solutions. We evaluate models in direct-answer setting, requiring them to generate the complete solution path given start and end nodes without intermediate reasoning steps. Based on this controlled synthetic environment, we ask three related questions:

---

Published as a conference paper at ICLR 2026
(1) Can language models systematically generalize composable SOPs?
(2) If a model can solve smaller instances, can it compuse them to solve larger-seale or struc- turally novel problems?
(3) How is such generalization capability shaped across different stages of the learning pipeline, including training data, training paradigms, and inference- scaling methods?
This environment naturally supports two axes of out-of- -f--isiibitttiionn generalization evaluation: spa- tial transfer, which tests whether the model can solve the task in entirely unseen maps, and length scaling, which evaluates the ability to handle Longer-horizon problems within the same map. Suc- cess under these settings provides direct operational test of whether the model systematically generalizes. This controlled setup makes possible to independently vary (i) training data proper- ties, (ii) training paradigms, including SFT and RL (enabled by the easily verifiable reward), and (iii) inference-time strategies. This separation enables us to isolate how different components of the learning pipeline shape distinct dimensions of generalization SOPs. The structured map en- vironment further supports direct analysis and visualization of characteristic failure modes, offering insight into the model's 's underlying behavior.
Through extensive controlled experiments, we obtain the following key findings:
Models can spatially transfer to entirely unseen maps, providing evidence of systematic structural generalization, but fail to generalize under length scaling, primarily due to recursive instability (Section 3
2. Training data primarily determines capability limits: allocating training budget to more distinct questions rather than more solutions yields better transfer generalization. Selecting questions with broader primitive coverage is more beneficial than more diverse primitive combinations. (Section
4 Length scaling requires exposure to slightly longer training examples. (Section(5)
3. Reinforcement learning stabilizes training but does not surpass the performance ceiling of pervised fine-tuning (SFT), and exhibits error patterns similar to SFT (Section (6) RL remains
below the best SFT performance even when stronger inference strategies are used better unlock intrinsic capability, and appears to restrict the effective solution space (Section 7
Advanced inference- time strategies can improve performance for both SFT and RL models but cannot rescue length scaling failures. (Section
We defer detailed discussions of research gaps and motivations to the beginning of each section, and related work can be found in Section
2 PRELIMINARIES AND EXPERIMENTAL SETUP
Sequential Optimization Problems. An SOP is specified by a state space S, an action space A, a transition rule T, a goal set and a global objective C.
Given an initial state 9o, the goal is to find an action sequence a1.7 = (a), aT) solving
[tt1 = T's,, az),
min C(so, a1:T) s.t.
(1)
8T EG
We say that an SOP is composable if, for any intermediate state Sy along an optimal trajec- tory, Opt sy) = Opt(si,8s) 8k) Opt(sk,8)) where denotes concatenation of two valid sub- trajectories. For example, in shortest-path planning, ShortestPath(i, = ShortestPath(i,, k) ShortestPath(k:.))
Spatial Transfer. Our notion of structural transfer aligns with established definitions of systematic generalization (Wiedemer al. 2023b; Fu al. 2024). where generalization is characterized as applying known rules to novel combinations of primitives outside the training support. Formally, and adjacency A. A mobility rule f(i,j G)) returns mobility path from node to node j under G. The training support is the set of ordered start-end node pairs used in training, supp (Drrnn)) S VVVV((( i)}. We evaluate transfer generalization of model 0 trained on Dirain as its performance in applying rule f to novel ordered pairs (i. Diest. where all node pairs the test set are disjoint from those in training, i.e., supp supp(Dres)) (Dres) Susp (Duain)) 0. In our case, Diest is drawn from disjoint novel map & (V, A) with V n V @ and Å + A, i.e., irrelevant G in nodes, edges, sparsity or size.
let G = AV AV, be a sparse grid map (i.e., with edges blocked) with node
2

---

Published as a conference paper at ICLR 2026
Such truly disjoint test space is rarely achievable in natural language, where systematicity is of- ten evaluated by holding out primitives within the same domain. This can yield overly optimistic estimates, since semantically similar primitives (e.g.. "run" vs. "walk") may lie close in embedding space. Our spatial setup therefore provides a more faithful measure of systematic generalization.
Length scaling. Similarly, we formalize horizon scaling following prior definitions of length gen- eralization (Sinha et al.] 2024] Cai et al. 2025). Within the same notation, it can be viewed as a constrained form of transfer, where novelty is enforced along the path-length axis. Let ((D) denote the set of path lengths for the mobility pairs in dataset D. Then, in addition to the disjointness con- dition supp (D n supp = 0, length scaling further requires max (Dania) S min (Dust), i.c., all test pairs must involve strictly longer paths than any seen in training.
Metric. Let fo G) denote the path predicted by the model 0. We measure generalization performance using the success rate (SR):
SR
Pr (k.))-Pas
[fo(i,) -
In our experiments, we adopt the shortest-pathe -atth rule for f. which makes path length precisely control- lable lable[[ou goal is study the properties of the data and training paradigm rather than the inherent learnability of the task itself, and shortest-path is a canonical path-finding problem that is (theoreti- cally) regarded learnable by language models (Cohen al. 2025 Dai et al. 2024). In shortest-path, fiijj G)) may return set of valid paths whenever multiple paths exist between and j. During evaluation in Equation 2). we deem fi G) successful if it belongs to the set fii G).
Empirical Setup. We trained 8-layer, 8-head Transformer models from scratch following the LLaMA architecture (AI@Metal 2024), which employs Rotary Positional Embeddings (RoPE) (Su) ct al. 202T) for position encoding. The models were pretrained on random-walk paths over all maps (G and G), simulating the autoregressive pretraining phase of large language models (LLMs). This pretraining exposes the model to the primitives (nodes) and their semantics, defined by their adjacency relationships. To prevent interference with downstream mobility learning tasks, we bias the pretraining distribution by constraining random-walk paths to have minimum length substan- tially longer than any path in the fine-tuning distribution. (We also validate this non- non-interen non-interference in Section D.3) This mirrors common practice in LLM pretraining, where models are exposed to much longer sequences than those used in fine-tuning or evaluation. Further pretraining details are provided in Section [.I]]
For evaluation, we fine-tune the models on shortest paths on the training map G = AV. We split the node set into training and test sets: the training sets contains 80% of the nodes (from which subset of nodes Vimin used to form Drnin is sampled) and the remaining 20% for length scaling evaluation. We test spatial transfer on different disjoint test maps G = AV.
Training paradigms and data format. We study two training paradigms: supervised fine-tuning (SFT) and reinforcement learning (RL). For SFT, each training sample is represented as sequence of the form 
 i j i E S E E start and end nodes, 
 and 
 are special tokens, and the path is encoded as sequence of movement directions (F, W, N. S). Using directions instead of node indices prevents the model from trivially memorizing n-gram sequences of node identifiers. The prompt prefix 
 i j which we refer to as the question such that the path itself is the answer, is excluded from the loss during SFT. At test time, we feed this prompt the model and evaluate the generated continuation, i.c., asking the question "what is the shortest path from i to j?"
N E S W W j 
, where i and j denote the
Our path setup also naturally lends itself to RL for two reasons. (1) The shortest paths are inherently verifiable: a generated sequence either forms a valid shortest path or not, allowing us to define a binary reward without additional heuristics; (2) Although the model not explicitly designed to "think", the path-generation process itself resembles step-by-step reasoning procedure, making RI. a natural training paradigm for this setting. We adopt the Dr.GRPO (Liu et al. (225c) algorithm (an unbiased variant of GRPO and the de facto standard in recent implementations of RL with LLMs), with a binary reward of 1 if the generated sequence forms a valid shortest path between i and j and 0 otherwise. The RL-traieed model is trained on the same prompt prefix 
 i :, and we vary the number of rollouts per prompt (4, 8, and 16) during training.
Many other common mobility rules, such DFS, yield unconstrained lengths.
3

---

Published as a conference paper at ICLR 2026
Length
Longer Length
Length groups
1.0
New Maps, Seen Length
Metrics
(20,30)
(30,40)
New Maps, Longer Length
Success Rate
0.8
Same Map, Longer Length
Pr(Long)
0.774
0,530
Pr(Sub)
0.920
0.893
Pr(Sub; A Subz)
0.846
0.796
0.4
Pr(Long Sub: A Suba)
0.811
0.589
Pr(Long, -Sub, A Subz))
0.082
0.061
00
Table 1:
Composition analysis of length scal- ing failure. The full-path success rate Pr(Long) can be decomposed into Pr(Long, Sub, A Suby) and Pr(Long, -(Subr A Sub2)). The degrada- tion is primarily driven by the drop in Pr( Pr(Long| Subı A Suby). indicating reduced stability under recursive application of learned rules.
Q1.10
(10. 20)
(20. 30)
(30, 49)
(40, so)
(s0, 6q)
(70. Bo)
(00.
Length Group
Figure 1: The model successfully transfers to un- seen test maps within the training length but fails to generalize to longer paths. The vertical dashed line denotes the boundary between training and longer lengths.
CAN LANGUAGE MODELS SYSTEMATICALLS GENERALIZE?
A model exhibits systematic generalization if it can apply learned rules compositionally beyond the specific configurations observed during training. This includes both solving problems built from disjoint primitives and solving problems that require deeper recursive application of the same rule. In our setting, this corresponds to generating valid shortest paths in previously unseen maps (spatial transfer) and generating valid shortest paths of greater lengths than those seen during training (length scaling). We begin by presenting the high-level generalization behavior under the strongest training configuration (Figure []. and defer detailed breakdown of training data and paradigm choices to later sections. Specifically, the model is evaluated on maps not used during shortest-path training to assess spatial transfer (blue bars). For length scaling, evaluate both the training map (red bars) and unseen maps (orange bars) on start-end pairs whose shortest paths are longer than those observed during training. We observe that language models achieve consistently high success rates (above 90%) on spatial transfer (blue bars), but performance degrades sharply under length scaling, regardless of whether spatial transfer is present (orange bars) or not (red bars).
This length scaling failure is surprising. Intuitively, if a model can reliably solve smaller problems (i.e., shorter paths), one might expect decompose larger problem into small segments to solve. We thus consider two possible explanations:
Hardness accumulation. As shorter paths are not perfectly solved (i.e., ID length success rate + 100%), longer paths may fail simply because they are more likely to contain difficult subproblems. Recursive instability. Even when shorter segments are individually solvable. the model may fail to stably compose them under longer recursive generation.
To disentangle these effects, we decompose long- success rates, Pr(Long). For each test path of length exceeding training length, we split it into two subpaths, Sub; and Suby, each within training length. Then, by the law of total probability,
Pr(Long) = Pr(Long Sub, A Suby) Pr(Sub, A Sub2) + Pr(Long, -(ub, A Subz)).
Here, Pr(Sub, ^ Sub2) is the probability that both subpaths are solved correctly, while Pr(Long Sub; A Suby) measures the probability of correctly generating the full path when both subpaths are individually solvable. Results in Tsho that the complementary term Pr(Long. -(Sub, ^ Sub2)) is small and relatively stable across length groups, compared to the dominant term Pr(Long| Sub, Subz) Pr(Sub; Subb). Focusing on the dominant term, we observe that Pr(Sub, A Subz) & Pr(Sub)². That is, hardness accumulation arises primarily as a multiplicative probability effect from imperfect subpath performance. Given the high subpath performance, the resulting decrease in Pr(Sub; A Subz) is modest as length increases (0.846 + 0.796). In contrast, the drop in Pr(Long Sub, A Sub2) is substantially larger (0.811 - 0.589), showing that length scaling failure is dominated by compositional instability.
Takeaway 1: Language models exhibit systematic spatial generalization on composable SOPs, but this success does not extend to length scaling: even if model can solve smaller instances, it struggles to stably compose them to solve larger ones.
4

---

Published as a conference paper at ICLR 2026
In the following sections, amalyze how training data, training paradigms, and inference strategies affect the generalization on composable SOPs.
EFFECTS OF DATA SELECTION ON SPATIAL TRANSFER
We start by analyzing the effects of data selection for the classic SFT paradigm. We ask: how to allocate fixed training budget of records to best support transfer? Should the budget go toward col- lecting diverse answers for each question, or toward covering as many distinet questions as possible (Section 4.1 ? What kinds of questions should be prioritized (Section
4.1 MORE QUESTIONS VS. MORE ANSWERS
In many domains of current interest (e.g., mathematics, program synthesis, navigation), a single problem naturally admits multiple valid solutions. This makes budget allocation an important con- sideration in SFT, especially since collecting high-quality solutions often requires significant ef- forts (Cobbe et al. 202I Hendrycks et al. 202T). The question is not trivial: the model requires sufficiently diverse questions capture the underfying rules; but if each problem is paired with only one solution, the model may overfit to surface patterns rather than acquiring the underlying rule, po- tentially harming transfer. We therefore investigate whether allocating budget to solution diversity improves spatial transfer generalization, or if prioritizing distinct questions is more effective.
Experiment Design. We consider five training budgets B E (5%, 10%, 20%, 60%, 80%} of the total possible training records, where the total is
Spatial Transfer SR vs. Unique Questions
Rate (SR)
SR 0.97
0.9
Spatial Transter Success Rate
determined by the maximum number of directed start-ent end pairs within the designated training region (80% of the nodes in the training map G, as illus- trated in Section [ We use a 50 x 40 sparse grid map with [V| = 2000 nodes as G. For each bud- get, we vary the number of distinct questions (unique start-end pairs) and the average number of answers per question (distinct valid shortest paths between each node pair), subject to the constraint Nquestions B Transfer capability is mea- sured by the success rate (SR, Equation (2)) on dis- joint test maps, restricted to paths within the train- ing length (i.e., excluding length-scaling). We eval- uate on three spatially disjoint maps of varying size (30 x 30, 40 x 40, 50 x 50), sparsity (25%-75%), and adjacency. We report the average SR across them.
0.8
Budget lovel
very low budget
low budget
less low budget
0.5
high budget
very high budget
10a
10
10
Number of Unique Questions (Bounded by Budget)
Nanswers per question
Figure 2: Spatial transfer success rate (SR) improves consistently with more budget allo- cated to unique questions (log scale). Curves show five budget levels (very low to very high: 5%, 10%, 20%, 60%, 80% of all possi- ble records). Dashed line marks the SR ceil.
Unique questions drive transfer. We first confirm that the model can spatial transfer: even when trained on a limited subset of the training map (e.g., 20% of the 80% training region, i.e., 16% of the full training map), it achieves an average success rate of 94% over three spatially disjoint test maps. As shown in Figure under fixed budget, training on more distinct questions consistently improves transfer. For example, with low budget, allocating all data to distinct questions with one solution each yields an SR of 94%, compared to only 82% when using fewer questions but 32 solutions per question. This pattern holds across all budget levels, showing that unique questions provide higher marginal value than unique solutions. (This does not imply that solutions are unimportant; rather, one high-quality solution per question appears sufficient under SFT.) However, the benefit of adding more questions quickly saturates: at very high budgets, training with hundreds of thousands of additional questions produces almost no gain over low budgets.
Takeaway 2: Spatial transfer is best supported by covering as many distinct questions as possi- ble. This makes the most of the training budget, especially when collecting solutions is expensive.
IIf a question admits fewer distinct solutions than required, we include all available solutions and allocate the remaining budget to other questions without repetition.
5

---

Published as a conference paper at ICLR 2026
4.2 COVERAGE VS. DIVERSITY IN QUESTIONS
If distinct questions matter more than multiple solutions, which kinds of questions should be pri- oritized? Prior work on generalization has long emphasized two training distribution properties, coverage and diversity. (Lake & Baroni, 2018; Bahdanau et al. 2018 Keysers et al. 2019 Lippl & Stachenfeld; Levy al. |023] Ahuja & Mansouri (024). While commonly believed to matter, their precise role remains unclear: Are higher coverage and diversity always beneficial? How do they interact? We next vary these two factors to examine their effect on systematic transfer. Following Chang et (2025) we define them in questions over node primitives:
(Local) Coverage, Coverage measures the fraction of unique nodes (i.e., primitives) in the local training map G = (V, that appear in the training set. Formally, following Section 2 let Viain S V denote the set of nodes included in Drain- We define = |Vaan//|V/ which ranges between 0 and 1.
Remark. We stress that coverage is defined only locally relative to the training map, not the global universe. Even c = 0.8 corresponds only to a tiny fraction of the universe of possible primitives. Since the model is expected (and observed) to spatially transfer to (infinitely) many disjoint maps C = (V, including nodes from all such maps in the denominator would only dilute the fraction and make coverage misleadingly small. For comparability, we therefore compute coverage solely with respect to the training map; any nodes in any disjoint map G are in fact uncovered.
Diversity.
Diversity measures how richly the observed nodes combined in training. Formally, recall from Section 2 that supp(Dmmin) denotes the set of ordered node pairs included in training. We define d |supp ininn) ////////// ///Viannl, which ranges from 1 to [V| 1. Intuitively, d corresponds to the average number of distinct endpoints j that each start node i E Virain is paired with. In practice, we control diversity explicitly by constraining, for each i, the number of distinct j's that appear in pairs (i,
Remark. Note that we intentionally do not normalize by |Vanal - 1, since |Vimil| = c|V this would couple diversity with coverage and prevent the two from being varied independently.
Experiment Design. To disentangle the roles of coverage and diversity, we design controlled ex- periments where one factor is varied while the other is fixed. Coverage is defined as = |Vinin/// | and is varied by linearly increasing the fraction of nodes included in the training questions from as low as 4% up to 80% of the nodes in the training map. Diversity d is varied by controlling how many distinct endpoints j each start node is connected to, ranging exponentially from 2 to 2 We control the total number of question-answer records to remain fixed across conditions. We use the same evaluation protocol as before, with one training map G and three independent and disjoint maps G, and report the average performance (measured by the success rate) over the three test maps.
Main Results. We summarize three selected obser-
Spatial Transfer SR
vations from Figure] 3 Marginal trends of each fac-
Coverage Levels (on Training Map G)
0.08
0.09
0.14
0.9
tor (see Figures 10 and IT and their individual anal-
0.12
0.31
0.37
0.36
0.40
0.8
ysis are deferred to Section D.5
0.14
0.7
(1) Coverage sets the ceiling of spatial transfer.
0.75
0.58
0.66
0.75
08
Across a wide range of diversity levels (from d = 2 to 27), the curves converge to similar maximum
0.38
0.72
0.78
0.76
0.5
0.47
0.64
0.50
0.87
0.4
SR once coverage is sufficiently high (e.g., R 0.90
0.63
0.78
0.81
0.56
0:90
0.90
0.94
0.3
for e Z 64%). When coverage low, even expo- nentially increasing diversity fails to achieve strong transfer. In contrast, high coverage can partially compensate for low diversity.
84%
0.70
0.82
088
0:90
0:92
0.95
0.96
0.96
0.
80%
0.78
0.56
0:92
0.44
0:96
0.95
(L96
0.98
270
211
2/2
2'3
244
2'5
2'6
277
Diversity Levels (Log Scale)
(2) Minimal diversity is required, but excessive diversity can hurt at low coverage. At very low diversity (d = 1, 2). SR grows slowly as coverage increases and saturates
Figure 3: Interaction between coverage and diversity on problem-solving transfer.
noticeably lower level. (e.g., d 2 2?) does coverage begin to unlock its full effect. However, excessively high diversity can sometimes reduce success rates when coverage is low (e.g., S 8%).
Only when diversity passes small threshold
(3) A resource-efficient regime (highlighted in red, Figure 12p is to target mid-to-high coverage 32%) with modest diversity (8-32) because diversity grows in cost exponentially.

---

Published as a conference paper at ICLR 2026
Table Performance different data regimes across MathQA categories.
probability (easy)
gain (medium)
physics (hard)
Qwen2.5-77-Instrucl
0.729
0.70
0.68
High Coverage
0.792
0.82
0.77
More questions
High Diversity 0.792
0.74
0.74
More solutions
0.771
0.72
0.70
Due to space constraints, present only the core findings in the main text. For complete and nuanced analysis of coverage coverage-diversity effects, including marginal and interaction results, readers strongly encouraged refer Section D.5
Takeaways 3-5 (Brief). Coverage determines the ceiling of spatial transfer. A minimal level of diversity required to approach this ceiling, but beyond small threshold, diversity yields diminishing returns and may even hurt when coverage is low. Insufficient coverage cannot be compensated by increasing diversity, Accordingly, the most cost-efficient regime combines mid- to-high coverage with modest diversity.
Mechanistic explanation for the success of spatial transfer. We observed strong generalization to disjoint maps, akin to how a language model, once having internalized a rule in English, can seamlessly apply the same rule other languages it already knows. This suggests that the model does not merely memorize surface-level node n-gram, but rather encodes structured latent operators that can be flexibly reused across domains-foo instance, "move adjacent node towards the end node" heuristic (which we probed in Section D.2). This interpretation aligns with recent theoretical progress framing attention as a hypernetwrr (Schug al. 2024). where attention scores serve as latent codes parameterizing reusable computations.
Practical insights. In real-world problem-solving, training can be viewed as teaching the model to construct directed acyclic graphs (DAGs) over sertrion-typ-sspeciff sets of elements, with rules defined on each set (conceptual skills). The element set can therefore be treated as the primitive shared across questions. Under this view, coverage measures how many distinct element sets ap- pear training, while diversity measures how many distinct directed structures are supported per element set. Takeaways 2-5 provide concrete guidance for dataset selection: to enable systematic transfer under limited budgets, one should prioritize broad coverage of clement sets in questions, combine it with only modest diversity in their structural realizations, and spend the least effort on solution diversity. concrete example in math provided below.
4.3 A CASE STUDY IN THE MATH DOMAIN
To examine whether the conclusions drawn from our controlled navigation environment generalize to more realistic setting, we conduct case study mathematical reasoning using the MathQA dataset (Amini et al., 2019). Each MathQA problem is annotated with a linearized operation pro- gram, which allows us extract the element by converting each program into unordered multiset of operations (i.e.. operation set). Different programs may share the same element set. See Section|EJoo exmaples. We then define coverage and diversity over these operation sets.
(Team 2024) on three representative cate- gories pacesssrrbbabii. bitbiillyyyy (easy), gain (medium), and physics (hard)-under under a strict data budget of roughly 1,000 samples per category (and only ~ 200 for probability due to its very small size). We use DeepSeek-RI (DeepSeek-A) Al et al., 2025) to generate high-quality chain-of-thought solutions for supervision. Following our earlier observations, we compare the following data allo- cation strategies (more details are provided in Section
Setup. We fine-tune Bive2.5-7B-Innsrree
More Questions: one solution per question, maximizing the number of distinct questions. This strategy has two variants:
High Coverage: maximize the number of distinct operation sets;
High Diversity: increase the number of questions per operation set (tenfold), and therefore operate under smaller coverage.
More Solutions: ten solutions per question and reducing the number of distinct questions.

---

Published as a conference paper at ICLR 2026
rollouseB
rolout-16
Success Rate at |= 30
0.9
/- J2
Oriinal
-O-
1-22
Spatial Transfer Success Rate
1.0
-C- 1=
- 1=80
0.8
0.9
0.7
0.8
0.6
0.5
0.7
0.4
0.3
0.01960.03%
0.13%6.2696
1.29%
12.93%
20%6
2596
40%
60%6
80%
Fraction of Added Training Paths Length
RL Starting Stage
Figure 4: Effect of adding paths of differ- Figure 5: RL does not further improve spatial
lengths on SR to length 30. A few transfer: performance bounded by the SFT base- line. Each group of bars corresponds to a differ- ent SFT checkpoint used to initialize RL. Blue bars denote one-pass RL and red bars denote multi-pass RL.
neighboring-and-lonn and-loger paths (e.g.. = 32, 34)
rescue performance, shorter ones
22, 24)
give little gain, and overly long ones (1 80) degrade Dashed line: no augmentation.
More questions consistently outperform more solutions. Across all three categories, both More Questions regimes (High Coverage and High Diversity) achieve better generalization than More So- lutions. Notably, these improvements appear under an extremely small training budget: roughly 1,000 samples for category gain and physics, and only ~ 200 for probability) Despite such limited supervision, allocating more budget to distinet questions still produces clear perfor- mance gains. For instance, in the gain category, accuracy rises from 0.70 to 0.82 under High Coverage, and similar increase appears in the harder physics category (0.68 + 0.77).
Coverage plays the dominant role. Within the More Questions group, High Coverage consistently outperforms High Diversity (e.g.. 0.82 vs. 0.74 in gain; 0.77 vs. 0.74 in physics). This suggests that encountering a broader range of conceptual skills matters more than exposing the model many different ways of applying or combining the seen skills. Taken together. these findings reinforce simple intuition: under realistic data budgets, breadth matters more than depth.
EFFECTS OF DATA SELECTION ON
SCALING
In addition to problem-solving transfer, fundamental dimension of extrapolation is problem-solving scaling (Sinha et al. 2024, Hupkes et al. 2020 Cai et al.) 2025). As shown Figure T even the strongest spatial transfer model exhibits severe length scaling failurd While generalization within the training length regime is nearly perfect, performance rapidly deteriorates once path length exceeds the training maximum. This raises key question: if the data conditions that enable spatial transfer (e.g., sufficient training questions and high primitive coverage) do not suffice for scaling under SFT, what additional data conditions are required?
-ranial-transfer
Rescuing with slightly longer paths. Surprisingly, we found that adding even a handful of training examples randomly sampled from lengths at or slightly above the target length can substantially res- cue performance, whereas adding shorter paths provides much less benefit. For instance, in Figure we evaluate performance on target length 30, where the model exhibits suboptimal generaliza- tion. Augmenting the training set with a very small fraction ( 1% of the training data) of slightly longer paths (e.g.. 1 = 32, 34) raises success rates to nearly 90%. By contrast, adding shorter paths (e.g., 22, 24) yields small gains-evee when added in large amounts (12%))wiile much longer paths (e.g.. = 80) confuse the model and degrade performance. These results suggest that, under SFT, curriculum-like exposure to slightly longer examples provides the critical adaptation signal that neither shorter nor excessively long paths can supply.
Takeaway 6:
Length generalization can be rescued by adding slightly longer paths; shorter ones give little benefit, and overly long ones can even harm performance.
We test scaling on node pairs requiring longer paths than those seen during training (details in Section D.6
8

---

Published as a conference paper at ICLR 2026
SFF
GRPO
1.0
More
1.0
More Steps
Step 400
Stap
Step 600
Step 600
Success Rates
Step 1000
Success Rates
Step 1000
Stop 1200
Stop 1200
Step
Step
Step 2400
Step 2400
04
3200
Stop
Stop 4000
Best SFT
02
02
80
an
(10, 2d)
(20. 30)
(30. 40)
(40, s0j
(se, so)
(80. 7a
(70. 8o)
10
(10 20)
(20, 3gj
(30, 40j
(40 soj
(s0, soj
(e0, 70
(70, aqj
Length Groups
Length Groups
Figure 6: Length scaling under extended training (I epoch = 400 steps). Left: SFT improves first
but quickly overfits with more epochs. Right: RL (GRPO) remains stable across epochs but never exceeds the best SFT bound (dashed line).
EFFECTS OF TRAINING PARADIGM ON PROBLEM-SOLVING
While the previous sections focus on how data properties shape problem-solving skills, another nat- ural question is whether the training paradigm itself can provide further gains. A recent line of work presents compelling empirical evidence that reinforcement learning (RL) can enable extrapolative
generalization beyond supervised fine-tuning (SFT) (Chu et al., [025 Chen et al.) 2025 Huang
al., 2025). At the same time, other studies argue that RL primarily unlocks capabilities already
present in SFT rather than introducing new ones (Yue el al. 2025a Ma et al. 2025). We therefore
test whether RL adds value on top of SFT for spatial transfer and length scaling.
Spatial transfer setup. As detailed in Section we train the RLVR model using an unbiased GRPO variant with binary reward of 1 if the generated sequence forms a valid shortest path, and 0 other- wise. The training data budget is set to high, under which the model is capable of spatially transfer- ring (see Figure RL is warm-started from different SFT checkpoints, ranging from 6% to 80% of SFT training progress. For each warm-start, we vary the number of rollouts per prompt in 4, 8, 16. We report two types of RL outcomes: (i) one-pass RL (blue bars), where the model is trained on the remaining data for a single pass; and (ii) multi-pass RL (red bars), where RL is allowed to repeatedly reuse the same remaining data. This disentangles the effects warm-start quality, data availability, and rollout compute.
RL does not improve spatial transfer. As shown in Figure 5 RL does not confer additional capabilities beyond what can be achieved by a fully trained SFT for spatial transfer: the best RL curves are always bounded by the SFT upper line. Early warm-starts perform poorly in one-pass RL. (blue bars), but multi-pass training (red bars) can recover the gap
Length scaling setup. To test whether RL can address the known weakness of SFT in length scaling under "unlimited" passes, we continue RI. training for up ~20 epochs the same dataset (rollout fixed at 8), with the model warm-started from an early SFT checkpoint (after I epoch, 400 steps). For comparison, we also extend SFT training for the same number of epochs.
RL stabilizes training but cannot exceed the best SFT. [ggure/@coopprc SFT and RL under the same 10-epoch progress and show a clear pattern: SFT initially improves with more steps but quickly overfits, leading to sharp degradation. RL curves, in contrast, remain tightly clustered across steps, indicating stable training even after many epochs. However, RL never exceeds the best SFT bound, confirming that additional training (whether SFT or RI.) cannot resolve the fundamental limitation in length scaling. Results for extended RI. training up to 20 epochs are provided Section D.7 and show the same stable trend.
Across both settings, RL primarily serves to stabilize training and mitigate overfitting during pro- longed optimization, rather than unlock new reasoning capabilities. Error-type analysis in Section G further supports this: SFT and RL exhibit nearly identical error types and distributions, indicating that RL cannot correct eтroтs inherent to the corresponding SFT model. Consequently, the perfor- mance ceiling is determined by the best SFT model. This behavior is consistent with recent analyses of generation-verifiaain gap (Swamy al. 2025): RL provides benefits when generating good

---

Published as a conference paper at ICLR 2026
continuations is difficult but verifying them is easy. In our setting, the optimal path can be computed explicitly, making generation nearly as easy as verification and effectively closing this gap. When data are sufficient and well-designed, SFT achieves higher efficiency, while RL functions a robust fallback that trades peak performance for stability.
Takeaway 7: RL stabilizes training and prevents overfitting but does not unlock new transfer or scaling capabilities. The performance ceiling is always set by the best SFT model. SFT is more efficient with sufficient, high-quality data, while RI. provides safer default when principled data selection is missing.
Remark. Our findings do not suggest that RL is useless. In practice, training data often noisy, heterogeneous, or subject to domain shifts, where SFT may overfit or struggle. In such settings, RL can generalize better by optimizing sequence-level rewards-not because it extends the capability frontier, but because it maintains robustness where SFT degrades.
7 EFFECTS OF INFERENCE-TINE STRATEGIES ON PROBLEM-SOLVIN
Recent work shows that reasoning performance can be substantially improved at inference time by allocating additional compute (test-time scaling), typically by generating and selecting among multiple reasoning trajectories, such as Self-Consistency (Wang et al., (022), best-of-N sampling (Brown et al. 2024), and structured search like Tree-of-Thoughh Yao et al. 2023). This raises the question of whether observed length-scaling failures stem from insufficient search (i.e., a failure to surface latent capabilities encoded in the model) rather than intrinsic model limitations.
To rule out this possibility, we consider two strate- gies in addition to greedy decoding: (1) majority- 10 sample 10 trajectories and select the most frequent output (corresponding to standard Self- Consistency procedure (Wang et al.] (2022); (2)
Length Scaling under Different Decoding Strategies
1.0
CIPO
GATO shotcallo-30 CITIO ragert----E
0.8
Success Rates
04
shortest-of-10: sample 10 trajectories and select the shortest one (an objective-guidet selection strategy that explicitly exploits knowledge of the task re- ward). For each length group, we evaluate both SFT and RL (GRPO) models under all three inference settings. All stochastic strategies use 10 independent samples with identical temperature.
04
02
Bad SFT greety
8P1 shwressat 30
(10 ag
Ga 30j
40
(40 sgj
(3R sg
(00. Ta|
(78.
Length Groups
Results.
As shown in Figure 7 stronger inference- Figure 7: Length scaling under different inference-time strategies. Inference-tina search improves SR but does not rescue scal- ing failures; RL remains below SFT and ap- pear to contract the effective solution space.
time strategies (c.g., Shortest-of-10) can improve empirical success rates for both SFT and RL mod- els. However, the overall degradation trend remains largely unchanged; enhanced test-time search shifts the performance curve upward but does not fundamentally alter the length scaling failure.
Moreover, RL models consistently underperform their SFT counterparts under each inference set- ting. Notably, even with the strongest objective-guided sampling (Shortest-of- 10), RI. models achieve performance comparable to SFT greedy decoding and remain substantially below SFT Shortest-of-10. This suggests that RL training may restrict the effective solution space, limiting the diversity of trajectories available for inference-time selection.
8 CONCLUSIONS
Our work studies systematic generalization in composable sequential optimization problems within controlled synthetic pathfinding environment. We reveal a clear asymmetry: models transfer struc- turally across unseen maps but fail under length scaling due to recursive instability. By disentangling systematically analyze the
training data, training paradigms, and inference-time strategies, tribution of each factor to generalization performance. Our findings offer a unified view how different stages of the learning pipeline shape generalization in language models.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENTS
Jiayuan Ye is supported by the Apple Scholars in AI/L PhD fellowship.
REFERENCES
Amirhesam Abedsoltan, Huaqing Zhang, Kaiyue Wen, Hongzhou Lin, Jingzhao Zhang, and Mikhail Belkin. Task generalization with autoregressive compositional structure: Can learning from tasks generalize to d(t) tasks? arXiv preprint arXiv:2502.0899) 2025.
Kartik Ahuja and Amin Mansouri. On provable length and compositional generalization. arXiv preprint arXiv:2402.048% 2024.
AI@Meta. Llama 3 model card. 2024. URL httpps://giituub.co//eeetttt
1 1lama3/blob/meet http://aann/MoEEL CARD md
Aida Amini, Saadia Gabriel, Shanchuan Lin, Rik
Yejin Choi, and Hannaneh Hajishirzi. MathQA: Towards interpretable math word problem solving with operation-based formalisms. In Proceedings of the 2019 Conference of the North American Chapter of the Associ- ation for Computational Linguistics: Human Language Technologies, Volume (Long and Short Papers), pp. 2357-2367, Minneapolis, Minnesota, June 2019. Association for Computational Lin- guistics. doi: 18.18653/v 1/N1////////1111/000 1245. URL URL https: /ttp:://claattt httttpps//cclanntollo....oooe ortpt/ooooooooo//119999 1245
Cem Anil, Yuhuai Wu, Anders Andreassen, Aitor Lewkowycz, Vedant Misra, Vinay Ramasesh, Am- brose Slone, Guy Gur-Ari, Ethan Dyer, and Behnam Neyshabur. Exploring length generalization in large language models. In Advances in Neural Information Processing Systems, volume 35, pp- 38546-38556, 2022.
Dzmitry Bahdanau, Shikhar Murty, Michael Noukhovitch, Thien Huu Nguyen, Harm de Vries, and Aaron Courville. Systematic generalization: what required and can it be learned? arXiv preprint arXiv:1811.12885 2018
Mislav Balunovié, Jasper Dekoninck, Ivo Petrov. Nikola Jovanović, and Martin Vechev. Math- arena: Evaluating ilms on uncontaminated math competitions, February 2025. URL https:
//matharena... aii/
Bradley Brown, Jordan Juravsky, Ryan Ehrlich, Ronald Clark, Quoe V Le, Christopher Ré, and Azalia Mirhoseini. Large language monkeys: Scaling inference compute with repeated sampling. arXiv preprint urXiv:2407.2 1787, 2024.
Francesco Cagnetta, Leonardo Petrini, Umberto M Tomasini, Alessandro Favero, and Matthieu Wyart. How deep neural networks learn compositional data: The random hierarchy model. Phys- ical Review X, 14(3):031001. 2024.
Ziyang Cai, Nayoung Lee, Avi Schwarzschild, Samet Oymak, and Dimitris Papailiopoulos. Ex- trapolation by association: Length generalization transfer in transformers. arXiv preprint
arXiv:2506.09251, 2025.
Hoycon Chang. Jinho Park, Hanseul Cho, Sohee Yang, Miyoung Ko, Hyeonbin Hwang, Seungpil Won, Dohaeng Lee, Youbin Ahn, and Minjoon Sco. The coverage principle: framework for understanding compositional generalization. arXiv preprint arXiv:2505.20278, 2025.
Hardy Chen, Haoqin Tu, Fali Wang, Hui Liu, Xianfeng Tang, Xinya Du, Yuyin Zhou, and Cihang Xie. Sft or rl? an early investigation into training rl-like reasoning large vasion-language models. arXiv preprint arXiv:2504. /468, 2025.
Tianzhe Chu, Yuexiang Zhai, Jihan Yang, Shengbang Tong, Saining Xie, Dale Schuurmans, Quoc V Le, Sergey Levine, and Yi Ma. Sft memorizes, rl generalizes: A comparative study of foundation model post-training arXiv preprint
2025.
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reñichiro Nakano, et al. Training verifiers to solve math word problems. arXiv preprint arXiv:21 10.
10.14468 14168, 2021.
11

---

Published as a conference paper at ICLR 2026
Andrew Cohen, Andrey Gromov, Kaiyu Yang, and Yuandong Tian. Spectral journey: How trans- formers predict the shortest path. arXiv preprint arXiv:2502.08794. 2025.
Róbert Csordás, Kazuki Irie, and Jürgen Schmidhuber. CtI++: Evaluating generalization on never- seen compositional patterns of known functions, and compatibility of neural representations. arXiv preprint arXiv:2210.06::00 2022.
Xinnan Dai, Qihao Wen, Yifei Shen, Hongzhi Wen, Dongsheng Li, Jiliang Tang, and Caihua Shan. Revisiting the graph reasoning ability of large language models: Case studies in translation, con- nectivity and shortest path. arXiv preprint arXiv:2408.005299 2024.
Verna Dankers, Elia Bruni, and Dieuwke Hupkes. The paradox of the compositionality of natural language: A neural machine translation case study. arXiv preprint arXiv:2108. 05885, 2021.
DeepSeek-AL, AI, Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Ruoyu Zhang, Runxin Xu, Qihao Zhu, Shirong Ma, Peiyi Wang. Xiao Bi, Xiaokang Zhang, Xingkai Yu, Yu Wu, F. Wu, Zhibin Gou, Zhihong Shao, Zhuoshu Li, Ziyi Gao, Aixin Liu, Bing Xue, Bingxuan Wang. Bochao Wu, Bei Feng. Chengda Lu, Chenggang Zhao, Chengqi Deng, Chenyu Zhang, Chong Ruan, Damai Dai, Deli Chen, Dongjie Ji, Erhang Li, Fangyun Lin, Fucong Dai, Fuli Luo, Guangbo Hao, Guanting Chen, Guowei Li, H. Zhang. Han Bao, Hanwei Xu, Haocheng Wang. Honghui Ding, Huajian Xin, Huazuo Gao. Hui Qu, Hui Li, Jianzhong Guo, Jiashi Li, Jiawei Wang, Jingchang Chen, Jingyang Yuan, Junjie Qiu, Junlong Li, J. L. Cai, Jiaqi Ni, Jian Liang, Jin Chen, Kai Dong, Kai Hu, Kaige Gao, Kang Guan, Kexin Huang, Kuai Yu, Lean Wang. Lecong Zhang, Liang Zhao, Litong Wang. Liyue Zhang, Lei Xu, Leyi Xia, Mingehuan Zhang, Minghua Zhang, Minghui Tang, Meng Li, Miaojun Wang, Mingming Li, Ning Tian, Panpan Huang. Peng Zhang. Qiancheng Wang. Qinyu Chen, Qiushi Du, Ruiqi Ge, Ruisong Zhang. Ruizhe Pan, Runji Wang, R. Chen, R. L. Jin, Ruyi Chen. Shanghao Lu, Shangyan Zhou, Shanhuang Chen, Shengfeng Ye, Shiyu Wang. Shuiping Yu, Shunfeng Zhou, Shuting Pan, S. S. Li, Shuang Zhou, Shaoqing Wu, Shengfeng Ye, Tao Yun, Tian Pei, Tianyu Sun, Wang. Wangding Zeng, Wanjia Zhao, Wen Liu, Wenfeng Liang, Wenjun Gao, Wenqin Yu, Wentao Zhang. W. L. Xiao, Wei An, Xiaodong Liu, Xiaohan Wang, Xiaokang Chen, Xiaotao Nie, Xin Cheng, Xin Liu, Xin Xie, Xingchao Liu, Xinyu Yang, Xinyuan Li, Xuecheng Su, Xuheng Lin, X. Q. Li, Xiangyue Jin, Xiaojin Shen, Xi- aosha Chen, Xiaowen Sun, Xiaoxiang Wang, Xinnan Song, Xinyi Zhou, Xianzu Wang. Xinxia Shan, Y. K. Li, Y. Q. Wang. Y. X. Wei, Yang Zhang, Yanhong Xu, Yao Li, Yao Zhao, Yaofeng Sun, Yaohui Wang, Yi Yu, Yichao Zhang, Yifan Shi, Yiliang Xiong, Ying He, Yishi Piao, Yisong Wang, Yixuan Tan, Yiyang Ma, Yiyuan Liu, Yongqiang Guo, Yuan Ou, Yuduan Wang, Yue Gong, Yuheng Zou, Yujia He, Yunfan Xiong, Yuxiang Luo, Yuxiang You, Yuxuan Liu, Yuyang Zhou, Y. X. Zhu, Yanhong Xu, Yanping Huang, Yaohui Li, Yi Zheng, Yuchen Zhu, Yunxian Ma, Ying Tang, Yukun Zha, Yuting Yan, Z. Z. Ren, Zehui Ren, Zhangli Sha, Zhe Fu, Zhean Xu, Zhenda Xie, Zhengyan Zhang, Zhewen Hao, Zhicheng Ma, Zhigang Yan, Zhiyu Wu, Zihui Gu, Zijia Zhu, Zijun Liu, Zilin Li. Ziwei Xie, Ziyang Song, Zizheng Pan, Zhen Huang, Zhipeng Xu, Zhongyu Zhang, and Zhen Zhang. Deepseek-rl: Incentivizing reasoning capability in llms via reinforce- ment learning, 2025.
htttttsss///iiiiieeeeepeeeetttte //tp:///aiii org/ abs abwa/b/s..1.0 2501 12948
Yann Dubois, Gautier Dagan, Dieuwke Hupkes, and Elia Bruni. Location attention for extrapolation to longer sequences. arXiv preprint arXiv: 2019.
Nouha Dziri, Ximing Lu, Melanie Selar, Xiang Lorraine Li, Liwei Jiang, Bill Yuchen Lin, Sean Welleck, Peter West, Chandra Bhagavatula, Ronan Le Bras, et al. Faith and fate: Limits of trans- formers on compositionality. Advances in Neural Information Processing Systems, 36:70293- 70332, 2023.
Ying Fan, Yilun Du, Kannan Ramchandran, and Kangwook Lee. Looped transformers for length generalization. arXiv preprint arXiv:2409.15647 2024.
Jingwen Fu, Zhizheng Zhang, Yan Lu, and Nanning Zheng. A general theory for compositional generalization. arXiv preprint arXiv:2405.1 1743, 2024.
Daniel Furrer, Mare van Zee, Nathan Scales, and Nathanael Schärli. Compositional generalization in semantic parsing: Pre-training vs. specialized architectures. arXiv preprint urXiv:2007.08977 2020.
12

---

Published as a conference paper at ICLR 2026
Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song. Ruoyu Zhang, Runxin Xu, Qihao Zhu, Shirong Ma, Peiyi Wang, Xiao Bi, et al. Deepseek-rl: Incentivizing reasoning capability in llms via reinforcement learning. arXiv preprint arXiv:2501. 2025.
Dan Hendrycks, Steven Basart, Saurav Kadavath, Mantas Mazeika, Akul Arora, Ethan Guo, Collin Burns, Samir Puranik, Horace He, Dawn Song, et al. Measuring coding challenge competence with apps. arXiv preprint arXiv:2105.09958 2021.
Wenxuan Huang, Bohan Jia, Zijie Zhai, Shaosheng Cao, Zheyu Ye, Fei Zhao, Zhe Xu, Yao Hu, and Shaohui Lin. Vision-rl: Incentivizing reasoning capability in multimodal large language models. arXiv preprint arXiv:2503.065 06749,, 2025.
Dieuwke Hupkes, Verna Dankers, Mathijs Mul, and Elia Bruni. Compositionality decomposed: How do neural networks generalise? Journal of Artificial Intelligence Research, 67:757-795, 2020.
Naman Jain, King Han, Alex Gu, Wen-Ding Li, Fanjia Yan, Tianjun Zhang, Sida Wang, Armando Solar-Lezama, Koushik Sen, and lon Stoica. Livecodebench: Holistic and contamination free evaluation of large language models for code. arXiv preprint arXiv:2403.074 07777777774 2024.
Samy Jelassi, Stéphane d' d'Acco,i, Carles Domingo-Enrich, Yuhuai Wu, Yuanzhi Li, and François Charton. Length generalization in arithmetic transformers. arXiv preprint arXiv:2306. 15400, 2023.
Carlos E Jimenez, John Yang, Alexander Wettig, Shunyu Yao, Kexin Pei, Ofir Press, and Karthik R Narasimhan. SWE-bench: Can language models resolve real-world github issues? In The Twelfth International Conference on Learning Representations, 2024. URL [tRLittts://opneiieee
net Www.oooiiooo....... 8yNOM66
Mason Kamb and Surya Ganguli. An analytic theory of creativity in convolutional diffusion models. arXiv preprint (rXiv:2422.20292 2024.
Amirhossein Kazemnejad, Inkit Padhi, Karthikeyan Natesan Ramamurthy, Payel Das, and Siva Reddy. The impact of positional encoding on length generalization in transformers. Advances in Neural Information Processing Systems, 06:24392-2922222 2023.
Daniel Keysers, Nathanael Schärli, Nathan Scales, Hylke Buisman, Daniel Furrer, Sergii Kashu- bin, Nikola Momchex, Danila Sinopalnikov, Lukasz Stafiniak, Tibor Tihon, et al. Measur- ing compositional generalization: A comprehensive method on realistic data. arXiv preprint arXiv: 2019.
Najoung Kim and Tal Linzen. Cogs: A compositional generalization challenge based semantic interpretation. arXiv preprint arXiv:2010.05465, 2020.
Brenden Lake and Marco Baroni. Generalization without systematicity: On the compositional skills of sequence-to-sequenec recurrent networks. In International conference on machine learning, pp. 2873-2882. PMLR, 2018.
Andrew K Lampinen, Arslan Chaudhry, Stephanie CY Chan, Cody Wild, Diane Wan, Alex Ku, Jörg Bornschein, Razvan Pascanu, Murray Shanahan, and James L McClelland. On the generalization of language models from in-context learning and finetuning: a controlled study. arXiv preprint (oXiv:2505.00611 2025.
Michael Lepori, Thomas Serre, and Ellie Pavlick. Break it down: Evidence for structural compo- sitionality in neural networks. Advances in Neural Information Processing Systems, 36:42623- 42660, 2023.
Itay Levy, Ben Bogin, and Jonathan Berant. Diverse demonstrations improve in-context composi- tional generalization. In Proceedings of the 61st Annual Meeting of the Association for Compu- tational Linguistics (Volume 1: Long Papers), pp- 1401-1422, 2023.
Martha Lewis, Nihal V Nayak, Peilin Yu, Qinan Yu, Jack Merullo. Stephen H Bach, and Ellie Pavlick. Does clip bind concepts? probing compositionality in large image models. arXiv preprint arXiv:2212 10537, 2022.
13

---

Published as a conference paper at ICLR 2026
Kenneth Li, Aspen K Hopkins, David Bau, Fernanda Viégas, Hanspeter Pfister, and Martin Watten- berg. Emergent world representations: Exploring a sequence model trained on a synthetic task. ICLR, 2023a.
Xiang Lisa Li, Ari Holtzman, Daniel Fried, Percy Liang, Jason Eisner, Tatsunori Hashimoto, Luke Zettlemoyer, and Mike Lewis. Contrastive decoding: Open-ended text generation optimization. In Proceedings the si amnual meeting of the association for computational linguistics (volume
I: Long papers), pp. 12286-12313 2023b.
Qiyao Liang. Daoyuan Qian, Liu Ziyin, and lla Fiete. Compositional generalization requires more than disentangled representations. arXiv e-prints, pp. arXiv-2501, 2025.
Samuel Lippl and Kim Stachenfeld. When does compositional structure yield compositional gener- alization? kernel theory. In The Thirleenth International Conference Learning Representa- tions.
Adam Liška, Germán Kruszewski, and Marco Baroni. Memorize generalize? searching for compositional rnn in a haystack. arXiv preprint arXiv:1802.0646) 2018.
Mingjic Liu, Shizhe Diao, Jian Hu, Ximing Lu, Xin Dong, Hao Zhang, Alexander Bukharin, Shaokun Zhang, Jiaqi Zeng, Makesh Narsimhan Sreedhar, et al. Scaling up rl: Unlocking di- verse reasoning in Ilms via prolonged training, arXiv preprint arXiv:2507.12507, 2025a.
Mingjie Liu, Shizhe Diao, Ximing Lu, Jian Hu, Xin Dong, Yejin Choi, Jan Kautz, and Yi Dong. Prorl: Prolonged reinforcement learning expands reasoning boundaries in large language models. arXiv preprint arXiv: 24864, 2025b.
Zichen Liu, Changyu Chen, Wenjun Li, Penghui Qi. Tianyu Pang, Chao Du, Wee Sun Lee, and Min Lin. Understanding rl-zero-like training: A critical perspective. arXiv preprint EXXiv:5533220883 2025c.
Joao Loula, Marco Baroni, and Brenden M Lake. Rearranging the familiar: Testing compositional 2018.
generalization in recurrent networks. arXiv preprint
Lu Ma, Hao Liang, Meiyi Qiang, Lexiang Tang, Xiaochen Ma, Zhen Hao Wong, Junbo Niu, Chengyu Shen, Runming He, Bin Cui, al. Learning what reinforcement learning can't: In- terleaved online fine-tuning for hardest questions. arXiv preprint arXiv:2506.07527 2025.
Sidharth Mudgal, Jong Lee, Harish Ganapathy, YaGuang Li, Tao Wang, Yanping Huang, Zhifeng Chen, Heng-Tze Cheng, Michael Collins, Trevor Strohman, et al. Controlled decoding from language models. arXiv preprint urXiv:2310. 17022 2023.
Benjamin Newman, John Hewitt, Percy Liang, and Christopher D Manning, The eos decision and length extrapolation. arXiv preprint arXiv:2010.07174. 2020.
Yaniv Nikankin, Anja Reusch, Aaron Mueller, and Yonatan Belinkov. Arithmetic without algo- rithms: Language models solve math with a bag of heuristics. arXiv preprint arX1v:2410.21272. 2024.
Maya Okawa, Ekdeep S Lubana, Robert Dick, and Hidenori Tanaka. Compositional abilities emerge multiplicatively: Exploring diffusion models synthetic task. Advances in Neural Information Processing Systems, 36:50173-50195. 2023.
Santiago Ontanon, Joshua Ainslie, Vaclav Cvicek, and Zachary Fisher. Making transformers solve compositional tasks. arXiv preprint arXiv:2108.04378 2021.
Baolin Peng, Chunyuan Li. Pengcheng He, Michel Galley, and Jianfeng Gao. Instruction tuning with g.t arXiv preprint arXiv:2304.03277 2023.
Jackson Petty, Sjoerd van Steenkiste, Ishita Dasgupta, Fei Sha, Dan Garrette, and Tal Linzen. The impact of depth on compositional generalization in transformer language models. arXiv preprint arXiv:2310. 19956, 2023.
14

---

Published as a conference paper at ICLR 2026
Philip Quirke and Fazl Barez. arXiv:2310.13121, 2023.
Understanding addition in transformers.
arXiv preprint
Philip Quirke, Clement Neo, and Fazl Barez. Arithmetic in transformers explained. arXiv preprint arXiv:2402.02619, 2024.
Qwen, An Yang. Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chengyuan Li, Dayiheng Liu, Fei Huang, Haoran Wei, Huan Lin, Jian Yang, Jianhong Tu, Jianwei Zhang. Jianxin Yang, Jiaxi Yang, Jingren Zhou, Junyang Lin, Kai Dang, Keming Lu, Kegin Bao, Kexin Yang, Le Yu, Mei Li, Mingfeng Xue, Pei Zhang, Qin Zhu, Rui Men, Runji Lin, Tianhao Li, Tianyi Tang, Tingyu Xia, Xingzhang Ren, Xuancheng Ren, Yang Fan, Yang Su, Yichang Zhang. Yu Wan, Yuqiong Liu, Zeyu Cui, Zhenru Zhang, and Zihan Qiu. Qwen2.5 technical report, 2025.
URL https: wwt.xxiivvcooo org/ abs 2412. 15115
Rahul Ramesh, Ekdeep Singh Lubana, Mikail Khona, Robert P Dick, and Hidenori Tanaka. Com- positional capabilities of autoregressive transformers: A study synthetic, interpretable tasks. arXiv preprint UrXiv:231..129%9 2023.
David Rein, Betty Li Hou, Asa Cooper Stickland, Jackson Petty, Richard Yuanzhe Pang, Julien Di- rani, Julian Michael, and Samuel Bowman. Gpqa: A graduate-level google-proof q&a bench- mark. In First Conference on Language Modeling, 2024.
Simon Schug, Seijin Kobayashi, Yassir Akram, João Sacramento, and Razvan Pascanu. Attention as hypernetorr. arXiv preprint arXiv:2406.058166 2024.
Sania Sinha, Tanawan Premsri, and Parisa Kordjamshidi. survey on compositional learning of ai models: Theoretical and experimental practices. arXiv preprint (rXiv:2406008787 2024.
Jianlin Su, Yu Lu, Shengfeng Pan, Bo Wen, and Yunfeng Liu. Roformer: Enhanced transformer with rotary position embedding. In Proceedings of the 59th Anmual Meeting of the Association for Computational Linguistics (ACL), pp. 115-124. Association for Computational Linguistics, 2021.
Gokul Swamy, Sanjiban Choudhury, Wen Sun, Zhiwei Steven Wu, and Andrew Bagnell. All roads lead to likelihood: The value of reinforcement learning in fine-tuning. arXiv preprint arXiv:2503.01067, 2025.
Qwen Team. Qwen2.5: A party of foundation models, September 2024. URLhtttps://qwenl1 github.io/blon wtwblogg///o////ooo hwtp://wwenn2..11
Guiyao Tie, Zeli Zhao, Dingjie Song, Fuyang Wei, Rong Zhou, Yurou Dai, Wen Yin, Zhejian Yang, Jiangyue Yan, Yao Su, et al. Large language models post-training: Surveying techniques from alignment reasoning. arXiv preprint wrXiv:2503.06077 2025.
Leandro von Werra, Younes Belkada, Lewis Tunstall, Edward Beeching, Tristan Thrush, Nathan Lambert, Shengyi Huang, Kashif Rasul, and Quentin Gallouédec. Trl: Transformer reinforcement learning. https://ggitt http://ttttubccoooo wtt.g/ab...ooo/gggggggg/////////
2020.
Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc Le, Ed Chi, Sharan Narang, Aakanksha Chowdh- ery, and Denny Zhou, Self-consistency improves chain of thought reasoning in language models. arXiv preprini arXiv:2203. 2022.
Yuxiang Wang, Xinnan Dai, Wenqi Fan, and Yao Ma. Exploring graph tasks with pure 1lms: A comprehensive benchmark and investigation. arXiv preprint arXiv:2502.1877, 2025a.
Zehong Wang, Zheyuan Liu, Tianyi Ma, Jiazheng Li, Zheyuan Zhang, Xingbo Fu, Yiyang Li, Zhengqing Yuan, Wei Song, Yijun Ma, al. Graph foundation models: A comprehensive survey. arXiv preprint 2505v: 25/5 16, 2025b.
Jason Wei, Maarten Bosma, Vincent Y Zhao, Kelvin Guu, Adams Wei Yu, Brian Lester, Nan Du, Andrew M Dai, and Quoc Le. Finetuned language models are zero-shot learners. arXiv preprint 1oXiv2210.001663 2021.
15

---

Published as a conference paper at ICLR 2026
Thaddäus Wiedemer, Jack Brady, Alexander Panfilov, Attila Juhos, Matthias Bethge, and Wieland Brendel. Provable compositional generalization for object-centric learning. arXiv preprint arXiv:2310.05337, 20233.
Thaddäus Wiedemer, Prasanna Mayilvahanan, Matthias Bethge, and Wieland Brendel. Composi- tional generalization from first principles. Advances in Neural Information Processing Systems, 36:6941-6960, 2023b.
Sondre Wold, Lucas Georges Gabriel Charpentier, and Étienne Simon. Systematic generalization in language models scales with information entropy. arXiv preprint arXiv:2505.13083 2025.
Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Remi Louf, Morgan Funtowicz, et al. Transformers: State-of-the-ar natural language processing. In Proceedings of the 2020 conference empirical methods in natural language processing; system demonsirations, pp. 38-45, 2020.
Fang Wu, Weihao Xuan, Ximing Lu, Zaid Harchaoui, and Yejin Choi. The invisible leash: Why rlvr may not escape its origin, 2025. URL https:/aarxiv org/abs/2507. 14843.
Zhuoyan Xu, Zhenmei Shi, and Yingyu Liang. Do large language models have compositional abil- ity? an investigation into limitations and scalability. arXiv preprint arXiv:2407.15720, 2024.
Shunyu Yao. Dian Yu, Jeffrey Zhao, Izhak Shafran, Tom Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. Ad- vances in neural information processing systems, 36: 1809-118222 2023.
Gilad Yehudai, Ethan Fetaya, Eli Meirom, Gal Chechik, and Haggai Maron. From local structures to size generalization in graph neural networks. In International Conference on Machine Learning, pp. 11975-1 1986. PMIR, 2021.
Yang Yue, Zhiqi Chen, Rui Lu, Andrew Zhao, Zhaokai Wang, Shiji Song, and Gao Huang. Does re- inforcement learning really incentivize reasoning capacity in ilms beyond the base model? arXiv preprint arXiv:2504. 13837, 2025a.
Yang Yue, Zhiqi Chen, Rui Lu, Andrew Zhao, Zhaokai Wang, Shiji Song, and Gao Huang. Does re- inforcement learning really incentivize reasoning capacity Ilms beyond the base model? arXiv preprint arXiv:2504.1334
2025b.
Tian Yun, Usha Bhalla, Ellie Pavlick, and Chen Sun. Do lasion-language pretrained models learn composable primitive concepts? arXiv preprint arXiv:2203. 17271, 2022.
Qifan Zhang, Nuo Chen, Zehua Li, Miao Peng, Jing Tang, and Jia Li. Improving 1lms' generalized reasoning abilities by graph problems. arXiv preprint arXiv:2507.17/668 2025.
Yizhuo Zhang, Heng Wang, Shangbin Feng. Zhaoxuan Tan, Xiaochuang Han, Tianxing He, and Yulia Tsvetkov. Can 11m graph reasoning generalize beyond pattern memorization? arXiv preprint arXiv:2406.1 15992. 2024.
Jun Zhao, Jingqi Tong, Yurong Mou, Ming Zhang, Qi Zhang, and Xuanjing Huang. Exploring the compositional deficiency of large language models in mathematical reasoning. arXiv preprint arXiv:2405.06680, 2024.
Hattie Zhou, Arwen Bradley, Etai Littwin, Noam Razin, Omid Saremi, Josh Susskind, Samy Bengio, and Preetum Nakkiran. What algorithms transformers learn? study in length generalization. arXiv preprint arXiv:2310. 16028, 2023.
16

---

Published as a conference paper at ICLR 2026
Appendix Contents
Limitations
18
LLM usage
18
Related works
18
Additional results
19
D.I
Implementation and licensing
19
D.2
Probing: Model tracks distance to the end node
19
D.3
Pretraining does not interfere with downstream shortest-pait -pttthpphhhhh learning
20
D.4
Training paths length distribution under varying coverage values
20
D.5
Extended analysis of coverage and diversity
21
D.6
Additional results for length scaling
24
D.7
RL performance for more training steps
25
Practical implication from math domain
25
Setup
25
E.2
Results analysis
27
Prompts used in the pipeline
27
Prompt for extracting primitive operations from word problems
27
Prompt for collecting cffin-of-thought reasoning traces
28
Prompt for Qwwen2.5-7B-Instruue
28
Qualitative analysis of navigation failure cases
29
17

---

Published as a conference paper at ICLR 2026
A LIMITATIONS
The primary limitation of our study is that most results are derived from a controlled synthetic testhed with relatively small models, which may raise concerns about practical relevance. This reflects an inherent trade-off: narrowing the problem scope enables rigorous and well-controlled analysis, but inevitably reduces realism. While large-scale practical benchmarks are abundant, they often make it difficult to isolate the source of generalization behavior. Our approach therefore prior- itizes control and interpretability over scale.
To partially address this limitation, we validate key findings on training data properties using math datasets on 7B-scale models and relate our RL observations to recent theoretical developments. Moreover, sequential optimization itself constitutes broad class of real-world tasks, and path-based data is closely connected to reasoning and mathematical problem solving.
B LLM USAGE
We use ChatGPT and Gemini to support writing and formatting, such as grammar and style refine- ment, polishing figure and table captions, and other surface-level edits. Some the code is written with the help of GitHub Copilot and Claude, for example, in code auto-completion and providing debugging suggestions.
C RELATED WORKS
Compositional and length generalization Our notion of extrapolative problem-solving closely tied to systematicity in compositional generalization (CG) and length generalization, sometimes referred to as productivity in CG. Compositional Generalization (CG) plays a central role in general- ization studies, which underpins the ability to extend learning unseen situations (?). Systematicityy the most common definition of CG, refers to the capacity to systematically recombine known primi- tives and rules (Dankers al. (021). While Systematicity has long been regarded as fundamental
challenge for neural networks (Liška et al. 2018 Lake & Baroni 2018 Loula et al.) 2018 Csor- dás et al. 2022; Ontanon et al., 202T; Keysers al. 2019; Lewis al.)
2022), recent work has increasingly provided evidence that modern generative models exhibit nontrivial Systematic CG abilities (Lepori et al. [223) Yun al.) 2022] Okawa al., 2023] Ramesh et al., 2023 AAbedsoltan
et al. 2025 Xu et al. 2024). Further progress in understanding Systematic CG comes from multiple
perspectives: the structural side (Lepori et al. 2023] (Shhug al. 2024| Quirke & Barez, 2023 Li
et al.. (023a), the task side (Abedsoltan et al. [025 Zhou et al. 2023). and the data side (Lippl
& Stachenfeld; Ahuja & Mansouri] 2024| Kamb & Ganguli] 2024; Chang et al.J 2025 Cagnetta
al. 2024). For example, (Schug et al. 2024) shows that multi-head attention can function hypernetwork supporting compositional behavior (e.g., encouraging learning functions as reusable components). From the data perspective, (Ahuja & Mansouri] 2024) derives provable guarantees for length and compositional generalization under sufficient training-set diversity, while (Chang et al.) 2025) frames training data coverage as key factor in a model's ability to generalize to unseen combinations.
Progress on compositionality in vision object learning has become increasingly well characterized, both empirically (Yun et al. (2022) and theoretically (Wiedemer et al. [2023b a). In language, how- ever, understanding remains fragmented: studies have pointed
variety of factors (e.g.. from model-side (Kazemnejad et al. 2023 Petty et al., 2023) to dita-side (Ahuja & Mansouri, [024 Chang et al. (025 ). but lacking an integrated account. Our work takes a data-centric perspective, unifying the recurring factors into coherent view of how they jointly shape the model's I's systematic extrapolation. Inspired by progress in vision, where disentangled primitives and rules have enabled clearer advances, and to avoid prior inconclusive results in language (Lake & Baroni 20188] Furrer ctt al.) 2020 Dziri et al. (003),, we design map-navin navigatioo tasks in which primitives (nodes) and rules (mobilities) cleanly disentangled, allowing us directly assess the influence of data properties on generalization performance (Liang et al.) (025).
Length generalization, or Productiviry, is another notion within the broader study of compositional
generalization (Sinha et al. (2024). It has been widely discussed as a central challenge (Dubois
et al. 2019 Newman al. 2020 Cai et al. 2025 Fan et al., 2024 Jelassi al. 2023 Anil et al.
18

---

Published as a conference paper at ICLR 2026
2022). and is sometimes framed as form of recursive composition extrapolation Kim & Linzen 2020); Hupkes et al.] (2020); Dziri et al. (2023). For instance, in natural language tasks, longer input sequences may correspond to recursive or nested structures of previously seen phrases Kim & Linzen (2020). In our setting, path length provides a directly controllable axis for studying this phenomenon: extrapolating to longer paths mirrors the core difficulty of length generalization, while allowing us to systematically manipulate the data properties and training paradigm to probe its limits.
Graph navigation and other capabilities While our work may appear related to prior studies that evaluate models' graph navigation abilities Zhang al. (2024); Wang et al. (2025a). build Ychudai et al. (2021). or use graph data to enhance LMs' reasoning Zhang et al. (025)) is in fact fundamentally different in both task setting and goal. First, rather than treating the graph as the task itself (i.e., providing the model with many small graphs in prompts and training to solve specific navigation task on future graphs), our work considers the large map and treats each map an independent vocabulary world. Instead of explicitly describing the graph structure, we require the model to learn the connections and the map itself, analogous to how LLMs acquire word semantics during pretraining. The map sufficiently complex that it cannot be memorized or learned within a single prompt. Second, our goal is not to test whether models can perform navigation tasks, nor to improve navigation performance by modifying architectures or training pipelines. Instead, we seek to understand models' conpositionaliyyxxttapaaaat varying data distributional properties. To ensure that our focus remains on distributional effects, we even restrict ourselves to tasks that are already proven to be learnable [Cohnn et al.] (2025); ); Dai et al.] (2024). Therefore, our work is also orthogonal to studies that examine whether models can perform specific capabilities with certain heuristics under narrowly defined tasks Quirke et al. 2024): Nikankin et al. (2024); Cohen et al. (2025).
powerful graph models Wang ct al. (Yeub):Yehudaii
under
D ADDITIONAL RESULTS
D.1 IMPLEMENTATION AND LICENSING.
Our LLaMA-style models are based on the standard implementations in the Hugging Face trans farmerrrers library (Apache 2.0 license) /Wolf et al. (2020). Reinforcement learning with Dr.GRPO is conducted using the GRPOTrainer from the Hugging Face TRL library (Apache 2.0
license)
vvn Werra al. 2020).
Pretrain Specifications. We pretrain the model on random- wwak trajectories to provide basic "map semantics" without leaking any shortest-pate information. The pretraining data consists of long random walks sampled uniformly across the grid.
We adopt a pretraining corpus of 10M random-walk trajectories (approximately 1.3B tokens), trained for 124,999 steps. This number was chosen based on preliminary runs with smaller datasets (2M, 5MM and 8M trajectories), where we observed that the model's valid-path rate increases steadily with data size and saturates at the 10M scale. As reported Table at this final budget, the pre- trained model achieves a valid-pati rate of 1.0 while retaining zero shortest-path capability, con- firming that pretraining captures structural map knowledge without imparting any optimal navigation behavior.
D.2 PROBING: MODEL TRACKS DISTANCE TO THE END NODE
We investigate whether the model encodes the remaining shortest-path distance to the end node, which would allow it to apply heuristics such as "move towards the goal". For probing, we apply 2-layer MLP, po (x+)) = softmax (W, Relr((22r)) where of denotes the hidden representation of the f-th token at the k-th layer. The probe outputs a probability distribution over discretized distance
classes (C = 10). Although we probe at fixed token position, the hidden state at this position already integrates information from all previous tokens, including the traversed path. We thus train a probe on paths of varied length from the training map for each layer, and test it on paths from disjoint map, grouping path lengths from 1 1-20 into 10 classes (gramularity of 2). As shown in Table 3 the nonlinear probe achieves high accuracy, especially in middle-to-late layers, supporting the hypothesis that the model encodes bestance-based heuristics reusable operators for spatial
19

---

Published as a conference paper at ICLR 2026
transfer. While linear probe would provide stronger conclusion, we have not yet identified one that performs well in this setting.
Table 3: Probe accuracy (%) across layers.
Layer
Accuracy (%)
0
35.94
1
32.78
2
57.85
3
76.58
4
83.14
5
86.29
6
85.77
7
81.55
D.3 PRETRAINING DOES NOT INTERFERE WITH DOWNSTREAM SHORTEST-PATH LEARNING
To ensure that our pretraining stage does not leak or overlap with the downstream shortest-path task, we evaluate pretrained models directly on shortest-path generation. Both the loss distribution analysis Figure X and generation performance Table 4 confirm that pretraining does not endow the model with shortest-path capabilities, thereby ruling out interference.
Distribution (Pretrain Finetune)
Finetune
Pretrain
Density
0.30
0.15
0.00
Per-sample Loss
Figure 8: Loss distributions of the pretrained and fine-tuned models on test (i.e. unseen) shortest paths. The distributions are completely disjoint, indicating that pretraining alone does not prepare the model with chortest-path generation capabilities.
D.4 TRAINING PATHS LENGTH DISTRIBUTION UNDER VARYING COVERAGE VALUES
To examine whether the shortest-pan path distance distribution shifts as coverage increases, potentially contributing to performance gains, we plot the shortest-pale length histograms for different coverage ratios (under fixed diversity). Figure reports the frequency distributions (x: path length, y: proportion of samples) for coverage values {0.01, 0.05, 0.1, 0.2, 0.6, 0.8} on the training map G.
Table 4: Performance shortest-path generation. Pretrained models cannot generate valid shortest paths, confirming that pretraining does not interfere with downstream learning. The Avg. Length Ratio measures the ratio between the true shortest-paie path length and the generated path length.
Model Trained
Valid Path Rate
Shortest Path Ratet
Avg. Length Ratio 0.0707
Pretrain
1.0
0.00
Finetune
1.0
0.9726
0.9983
20

---

Published as a conference paper at ICLR 2026
Train Data Distance Distribution by Coverage Ratio
Coverage 0.61
Coverage 0.05
Coverage 0.1
140
010
0.34
0.33
Distarc4
Dittaros
Didtarce
1.0
Sa 44h
1.0
6
0.34
0:44
0.31
0.3
090
0.0
2.5
$5.0
20.5
3.5
3.5
15.0
2.
13.0
Figure 9: Shortest-path lengths distribution under varying coverage ratios (fixed diversity). The distributions remain stable across settings, indicating that coverage does not alter distance exposure.
Although the total number of sampled start-end pairs increases with coverage, the shape of the path-length distribution remains highly stable across all settings. The mean shortest-path length is consistently around 13.25 with a standard deviation of approximately 4.85, and the proportion of samples near the maximum observed training length (Lmax = 20) shows minimal variation.
These statistics confirm that increasing coverage does not introduce systematic changes to the length distribution, ensuring that our analyses isolate the effect of coverage itself rather than incidental differences in distance exposure.
D.5 EXTENDED ANALYSIS OF COVERAGE AND DIVERSITY
If more distinct questions are more valuable, which kinds of questions should be prioritized? Prior work on generalization has long emphasized the importance of training distribution properties such as coverage and diversity. These factors have been discussed since early seq2seq RNN and CNN models (Lake & Baroni 2018: Bahdanau et al. 2018 Keysers et al., 2019). and continue to play a central role for decoder-only Transformers (Lippl & Stachenfeld Ahuja & Mansouri] 2024 Levy et al. 2023). However, while commonly believed to matter, their precise role remains unclear: Are higher coverage and diversity always beneficial? How do they interact? In this section, we empirically vary these two classic factors in a decoupled way to measure their effect on systematic transfer. We begin by defining these notions in our setting. Following Chang et al. (202)), we define coverage and diversity in questions over node primitives.
(Local) Coverage. Coverage measures the fraction of unique nodes (i.c., primitives) in the local training map G = (V,A) that appear in the training set. Formally, following Section let Viain S V denote the set of nodes included in D We define |Vrain/ //V which ranges between 0 and 1.
Remark. We stress that coverage is defined only locally relative to the training map, not the global universe. Even e 0.8 corresponds only tiny fraction of the universe of possible primitives. Since the model is expected (and observed) to spatially transfer to (infinitely) many disjoint maps Ó = (V) including nodes from all such maps in the denominator would only dilute the fraction and make coverage misleadingly small.
21

---

Published as a conference paper at ICLR 2026
Spatial Transfer SR (on Test Maps G) vs. Coverage Levels
Spatial Transfer (on Maps G) Diversity Levels
1.0
Spatial Transfer Success Rate (SR)
Spatial Transter Success Rate (SR)
Coverago
0.08
Diversity
0.8
0.12
0.16
2
0.4
0.6
2
08
0.32
2
2
0.64
0.4
04
0.80
2
25
28
2
0.0
0.0
0.1
0.2
0.5
0.6 0.7
088
2-
2
Coverage Levels (on Training Map G)
Diversity levels (log scale)
Figure 10: Spatial transfer success rate (SR) mea- Figure 11: Spatial transfer success rate (SR) sured on the disjoint maps as the nodes coverage ratio in question in the training map increases. Each curve corresponds to a fixed diversity level. curve corresponds to a fixed coverage ratio.
measured the disjoint maps as the node pair
composition diversity level increases. Each
For comparability, we therefore compute coverage solely with respect to the training map; any nodes in any disjoint map G are in fact uncovered.
Diversity. Diversity measures how richly the observed nodes are combined in training. Formally, recall from Section that supp(Pumin) denotes the set of ordered node pairs included in training. We define d (supp(() //nana which ranges from 1 to [V| average number of distinct endpoints j that each start node i E Virain is paired with. practice, we control diversity explicitly by constraining, for each i, the number of distinct j's that appear in pairs (i, j).
Intuitively, d corresponds to the
Remark. Note that intentionally do not normalize d by |Vuial - 1, since |Vanial c|V this would couple diversity with coverage and prevent the two from being varied independently
Experiment Design. To disentangle the roles of coverage and diversity, we design controlled ex- periments where one factor is varied while the other is fixed. Coverage is defined as c = |Vraanl// / and is varied by linearly increasing the fraction of nodes included in the training questions from as low as 4% up to 80% of the nodes in the training map. Diversity d is varied by controlling how many distinct endpoints each start node is connected to, ranging exponentially from 2 to 2?. We control the total number of question-answer records to remain fixed across conditions. We use the same evaluation protocol before, with training map G and three independent and disjoint maps G. and report the average performance (measured by the success rate) over the three test maps.
D.5.1 MARGINAL RFFECTS
We draw two key observations from Figure
10
(1) Coverage determines the ceiling of spatial transfer. Across wide range of diversity levels (from d = 2 to s²), the curves converge to similar maximum SR once coverage is high. This shows that coverage ultimately only influences how quickly, as coverage increases, this ceiling is approached.
the upper bound of systematic generalization, while diversity
unlock efficient use of coverage. However, at very low diversity (d = 1, 2), SR grows slowly and saturates at noticeably lower level. Only when diversity passes a small threshold (d 2 4 here) does coverage begin to unlock its full effect.
(2) Minimal diversity is required
(3) Threshold and plateau phenomenon. With sufficient diversity (d > 4). SR exhibits sharp inflection around mid-to-low coverage (<: 0.2)0. Beyond this point, additional coverage yields diminishing returns, whereas below it, generalization remains poor.
Takeaway 3: Coverage in question sets the ceiling of spatial transfer, but minimal diversity is required unlock it efficiently. Coverage also creates sharp inflection point in SR, indicating a cost-efficient region at low values.
We next vary diversity while keeping coverage constant. Results in Figure II show two main pat- terns:
22

---

Published as a conference paper at ICLR 2026
ID Length
Longer Length
1.0
New Maps, Seen Length
New Maps, Longer Longth
0.8
Same Map, Longer Length
Success
0.4
0,0
(1.30)
(10. 20]
(20 30)
(30. 40
(40 soj
(50 oc)
(80, 70
(70. eo)
Length Group
Figure 13: Spatial transfer success and length scaling failure.
(I) Log-linear gains at mid-to-high coverage. At mid-to-high coverage, performance grows roughly linearly in log(d), indicating that the marginal benefit of additional diversity decreases d grows. In other words, exposing the model to a few diverse combinations is highly beneficial, but each further doubling of diversity yields progressively smaller gains.
(2) High diversity can hurt when coverage is low. At low coverage, adding diversity sometimes reduces success rates. This likely occurs because exhaustively combining tiny set of primitives encourages memorization rather than rule abstraction. For example, if a model is trained on a very small set 1, 2,3 and exposed to possible addition combinations, can simply memorize the resulting facts without grasping the general rule of addition.
Takeaway 4:
Diversity can bring rapid early gains but quickly flattens out, and may even harm transfer when coverage is low.
D.5.2 DOVERAGE-DIVERSIIE INTERACTION
Spatial Transfer SR
Coverage Levels (on Training Map G)
0.9
Jointly analyzing coverage and diversity (Figure 12
0.8
reveals a clear interaction. At low coverage, even exponentially high diversity cannot rescue the per-
0.7
0.5
formance (e.g., SR rises only from 0.08 to 0.29 when coverage is 4%). By contrast, higher cover-
0.38
0.76
0.64
age (e.g., 32%), diversity strongly amplifies perfor-
0.63
0.81
0:90
mance (raising SR from 0.47 low diversity to 0.91
8656
0.70
0.82
0880
0:90
0.92
0.95
0.96
at high diversity). High coverage can partially com- pensate for low diversity (e.g., increasing SR from 0.08 to 0.78 when d = 1).
0.78
0:9
0.44
099
(L96
200
211
222
2'3
244
2'5
2'6
217
Diversity (Log Scale)
Because diversity grows in cost exponentially, resource-efficient regime (highlighted in red, Fig- ure 12) is to target mid-to-high coverage (2 32%) with modest diversity (8-32). This achieves strong performance at much lower computational cost than maximizing both dimensions. Beyond this regime, both coverage and diversity show di- minishing returns. Note that dataset size is approximately controlled across conditions by varying the number of answers, which actually makes lat--covrrag-low-dieeree settings relatively disad- vantaged (fewer distinct questions). That such settings still outperform woooeeage--igh-dvveeeeeee settings strengthens the conclusion.
Figure 12: Interaction between coverage and diversity on problem-solving transfer.
Takeaway Low coverage in question cannot be rescued even with extremely high diversity, but low diversity can be compensated by high coverage. Moderate-to-higg coverage with modest diversity achieves the best efficiency-performanc trade-off.
23

---

Published as a conference paper at ICLR 2026
Length Scaling Success Rates (within Training Map)
Success Rates (No Spatial Transfer)
1.0
Total Budgets
very budget
low budget
budget
high budget
very
02
0.0
(10, 20)
(20, 3g]
(30. 40)
(40, so)
(50, so)
(70, sq)
(1.
(00,
Length Groups
Figure 14: Length scaling performance of the best spatial-transfer model under different data bud- gets. All evaluations are conducted on holdout nodes within the training map (i.e., without spatial transfer). Despite variation in budgets, success rate (SR) consistently deteriorates as path length exceeds the training regime, showing that length scaling fails universally.
D.6 ADDITIONAL RESULTS FOR LENGTH SCALING
Implementation details and analysis of Figure 1 We report the length scaling performance of the strongest spatial- transferr model identified in Section (high-budget setting with all budget al- located to questions and high primitive coverage-diversity) Results for other budgets are provided in Section D.6.1
We measure success rate (SR) on both holdout nodes within the training map (No spatial transfer) and spatially disjoint maps (Spatial transfer). For each length group, evaluation conducted on 3,000 randomly sampled unseen node pairs.
The trends are nearly identical across the two settings: while the model achieves near-perfect gen- eralization within the training length regime (blue region), SR rapidly deteriorates once path length exceeds the training maximum (red region). This confirms that even when spatial transfer suc- ceeds, length scaling can fail.
D.6.1 LENGTH SCALING PERFORMANCE UNDER DIFFERENT BUDGETS
For completeness, we also evaluate length scaling across different data budgets (Figure 14). For each budget, we select the best-performing spatial-transfer model and report success rates (SR) on holdout node pairs with longer paths between them within the training map.
D.6.2 LENGTH SCALING UNDER A RELAXED FEASIBILITY METRIC
We additionally evaluate navigation under relaxed metric, valid rates, that counts any trajectory reaching the goal (without using invalid edges) as correct, rather than requiring shortest-path op- timality. As shown in Figure [5] feasibility remains near perfect for in-distribution lengths but still degrades substantially for longer paths. Relaxing the objective, therefore, does not remove the failure. Instead, the higher feasible-pant path rates relative shortest- path success sug- gest that the drop in performance arises from a combination of producing invalid trajectories and producing valid but non-optimal (non-shortest) ones.
24

---

Published as a conference paper at ICLR 2026
ID Length
Longer Length
1.0
Valid Rates
No Spetial Transfer
Success Valid Rate
Spatial Transfer
0.6
0.4
0.2
0.0
[0.10)
(10. 20)
(20. 30)
(30. 40)
50]
(50. 60)
(80. 70)
(70 80]
Length Group
Figure 15: Valid-path rates across length groups same length-scaling failure persists.
Although absolute performance improves, the
D.7
RL PERFORMANCE FOR MORE TRAINING STEPS
GRPO with Increasing Steps
Best SFT
8440
0.6
4890
0.4
02
1760
0.
200
10j
(10. 20)
(20, 30)
(40, 50)
(90 60)
(80, 20
(30.
(70.
Length Groups
Figure 16: Length scaling for RL under extended training for 20 epochs (1 epoch 400 steps).
E PRACTICAL IMPLICATION FROM MATH DOMAIN
To assess the practical relevance of our findings beyond the synthetic map-navigation setting, conduct a complementary study in the math domain. Specifically, we aim to examine whether, in more realistic setting, seeing more questions remains more impactful than seeing more solutions, and whether a question's 's coverage plays a more dominant role than its diversity.
E. SETUP
Dataset We select the MathQA dataset (Amini al. 2019) for evaluation because: (1) it con- tains six well-separated conceptual categories (gain, geometry, probability, physics, general, other), spanning range of difficulties and posing greater challenges commonly used 7B models than simpler math benchmarks such as GSM8K (Qwen et al., (002):; and (2) critically, it provides lin- earized operation programs. These programs provide direct way extract the primitives within questions.
For instance, the problem:
25

---

Published as a conference paper at ICLR 2026
"The ratio between the length and breadth of rectangular park is 2. A man cycles around the boundary at km/hr and completes one round 8 minutes. What is the area of the park?"
has the corresponding operation program:
d1vide(12. 60) mulliply((H,, 8) multiply(#1, 1000) I add(3, 2) multiply(2, #3) divide(#2, #4) I multiply(55, 3) multiply(#5, 2) rectangle_arca(ft #7)
Each operation program can be converted into an unordered multiset of operations, which cap- tures the reusable element set required by the problem (i.c., its primitive identity). This repre- sentation allows us define both coverage and diversity directly on mathematical problems. For datasets without human-prey -providdd formulas, we verify that a modern LLM can reliably extract the underlying operation sets from natural-language questions using a short instruction prompt (e.g. [" ("compute rectangle area", imultiply" ... A sample prompt-response pair is provided in Section
Definitions of terms We restate the core terms (questions, solutions, coverage, diversity) in the context of this math setting:
Questions: Each distinct math word problem.
Solutions:
For each question, multiple high-quality reasoning traces may exist, and each trace is counted as solution. We use DeepSeek-RI (DeepSeek-Al Al al. (025) to pro- duce such traces (i.e., explicit chain-of-thought outputs the form of "Let's think step-by- step.").
Coverage and diversity in the math domain. Each MathQA problem is paired with linearized operation program specifying the sequence of mathematical operations used to solve the problem. To align these programs with the coverage diversity framework intro- duced in our map-navigation setting, we decompose them into two orthogonal components:
Coverage. A single operation (e.g., add, multiply) is too coarse characterize mathematical problem types, as most problems reuse the same small set of basic op- erations. What distinguishes one problem type from another is the combination of operations required. Therefore, we treat the primitive operation-ser- multiset of operations appearing an operation program-as as the atomic semantic unit of mathematical problem. This operation set captures the underlying conceptual skill and serves as the minimal distinguishing signature of a problem type. Under this ab- straction, coverage measures how many distinct operation-sets the model encounters during training.
unordered
Diversity. In the map setting, diversity measures how many distinct composition pat- terns exist under the same primitive support-that is, how flexibly primitive par- ticipates in different relational structures. In the math domain, the analogous notion remains: the number of distinct program structures (operator orderings) that instanti- the same primitive operation-set. This measures how flexibly fixed operation set can be composed into different reasoning chains, without introducing new skills.
For example, the two operation programs below share the same primitive operation-set but differ in ordering; thus, they contribute to diversity but not coverage:
[divide, multiply, add, rectangle_arcal
[add, divide, multiply, rectangle_aren _aca]
We fine-tune 1rren2.5-7B-Instruee (Team 2024) across three representative difficulty categories in MathQA: probabilis bityy (easy), gain (medium), and physics (hard). For each category, we fix tight training budget of roughly 20% of its available samples (approximately 1,000 examples), except for the probabilin iitt split, which uses 50% due to its extremely small size. All models are evaluated on the test set corresponding to the same category. As described above, DeepSeek- RI to generate high-quality chain-of thain-of-thoughe of-thought traces for each question and construct three training regimes:
26

---

Published as a conference paper at ICLR 2026
Table 5: Performance of different data regimes across three MathQA categories.
probability
gain
physics
Qwen2.5-7B-Instee
0.729
0.70
0.68
High Coverage
0.792
0.82
0.77
More questions
High Diversity
0.792
0.74
0.74
More solutions
0.771
0.72
0.70
More Questions: each question is paired with exactly one solution, enabling a larger num- ber of distinct questions to be included under the same training budget. This includes two cases:
High Coverage: we include as many distinct primitive operation-sets as possible, resulting questions per set;
High Diversity: for each operation-set set we include 10n distinct questions, which in- creases structural diversity but necessarily reduces the number of covered operation- sets under the same training budget;
More Solutions: each question is paired with ten independently generated solutions;
E.2
RESULTS ANALYSIS
The results T demoontrate that the core principles identified in our controlled navigation set- ting apply the MathQA domain, even though these practical tasks contain heterogeneous natural- language formulations and lack clearly separable generalization axes (c.g., spatial or length extrap- olation).
More questions consistently outperform more solutions. Across all three categories (i.e., ga i probabi 1 ity, and physics both More Questions regimes (High Coverage and High Diver- sity) achieve better generalization than More Solutions. Notably, these improvements appear under an extremely small training budget: roughly 1,000 samples for category gain and physics, and only ~~ 200 for probability) Despite such limited supervision, allocating more budget dis- tinct questions still produces clear performance gains. For instance, the gain category, accu- racy rises from 0.70 0.82 under High Coverage, and similar increase appears in the harder physics category (0.68 - 0.77).
Coverage (operation-set variety) remains the dominant factor. Within the More Questions groups, High Coverage consistently outperforms High Diversity (e.g., 0.82 vs. 0.74 in gain, 0.77 vs. 0.74 physics). This suggests that the model gains more from being exposed to a broader set of conceptual skills than from seeing many different applications, orderings, or compositional variants of the same skill set. This echoes the threshold behavior observed in the nav- igation setting: once the model has seen the right set of conceptual skills, generalization improves sharply- even without extensive practice on each skill.
Taken together, these findings reinforce simple intuition: under realistic data budgets, breadth matters more than depth.
F PROMPTS USED IN THE PIPELINE
F.1 PROMPT FOR EXTRACTING PRIMITIVE OPERATIONS FROM WORD PROBLEMS
For natural-language math questions without human annotation, we can directly prompt an LLM to extract the underlying primitive operations. Below we provide an example prompt-response pair. The extracted operations are highly reasonable often comparable to, or even clearer than, the human-provided operation programs used in Section 4.3
27

---

Published as a conference paper at ICLR 2026
Prompt
You are an expert at breaking down math word problems into primitive mathematical operations.
Given math word problem, output only a list of short operation verbs (1-3 words) that describe the steps needed to solve it, such as: "add", "multiply", "divide", "use ratio", "convert units", "compute ares".
List them in the order they would be used. Do NOT show explanations or numbers. Cutput only the JSON list.
Model Response
('covvert minutes hours", "multiply", "divide", "use ratio", "multiply", "compute rectangle area"]
F.2 PROMPT FOR COLLECTING CHAIN-OF-THOUGH REASONING TRACES
To obtain high-quality chain-of-thow thought reasoning traces for each math question, prompt stronger LLM (DeepSeek-R) RI in our implementation) with an instruction that encourages explicit step-by-step reasoning followed by clearly formatted final answer. Below we provide the exact templates used our data construction pipeline.
System Prompt
You are helpful math tutor who explains things step-by-stop and always finishes with clearly formatted final answer.
User Prompt
Break down your reasoning process step by step, and show your thought process explicitly.
Separate each step using An\n.
At the end, conclude with single line in the exact format: The answer choice is: <option>.
Now solve the following multiplo-choice math problem:
[Question]
(question_text)
[Solution]
F.3 PROMPT FOR QWEN2.5-7B-INSTRER
We the prompt for finetuning and evaluation of -wen2.5-7B-Insstee and finetuned variants. In all cases, the model is instructed to first produce a step-by-step reasoning trace and then output clearly formatted final answer, as shown below.
System Prompt
You are heipful assistant.
User Prompt
Break down your reasoning process step by step, and show your thought process explicitly. Separate each step with AnAn.
Conclude with a single line in the exact format:
The answer choice is: [insert answer choice).
[Question] (question_text]
[Solution]
Chat template.
The human-readabe prompts described above correspond to the system and messages used during both fine-tuning and evaluation. In practice, all messages serialized
28

---

Published as a conference paper at ICLR 2026
Table 6: Error-type statistics for SFT and GRPO across length groups.
Length Group
Method
Non-Shortest
Not Reach
Invalid Move
(10, 20)
SFT GRPO
80.0%
20.0%
0%
(10, 20)
88.9%
11.1%
0%
(40, 50)
SFT
45.0%
49.0%
6.0%
(40, 50)
GRPO
43.0%
50.0%
7.0%
using Qwen2.5's official tokenizer chat template (via ensures that both fine-tuning and evaluation use the exact prompt format expected by Qwen2.5-7B- Instruct models, including all special tokens (e.g., <lim_start >) and role indicators required by the tokenizer.
function). This
G QUALITATIVE ANALYSIS OF NAVIGATION FAILURE CASES
To complement the quantitative results in the main text, we provide qualitative examples and systematic summary of failure modes for both SFT (coverage = 0.6, diversity = 64, and maximizing the number of questions) and the corresponding GRPO model (16 rollouts) across two representative length groups: (10, 20) (within the training-length regime) and (40, 50) (longer length regime). The model's 's prediction errors consistently fall into the following three categories; did not observe additional or unexpected behaviors (e.g.. producing no trajectory or starting from the wrong initial node):
Valid but non-shortest path
Did not reach target
Invalid move
Table 6 summarizes error statistics. Representative visualizations are presented in Figures Figures 17
to 20
These qualitative findings show that SFT and GRPO exhibit nearly identical failure modes, rein- forcing our conclusion that GRPO stabilizes training but does not surpass the performance ceiling established by the best SFT model.
29

---

Published as a conference paper at ICLR 2026
Figure 17: Representative failure cases (SFT) for the (10, 20) length group.
Case Langer Ronge 231 shorist puth Sharlen:: Preckdedd
incraatiie sirpi Cu Corr4
30
Fallure Case LLngth Ranon 130,
Shoftest: 15, Predicted: 33
beth daalee
75.3
605
30

---

Published as a conference paper at ICLR 2026
Figure 18: Representative failure cases (GRPO) for the (10, 20) length group.
120, phorted puth
FillurE Length Ckenn larget Starteet: 37 Rredkted
Pree cistPar (Pain)
2P CL)
31

---

Published as a conference paper at ICLR 2026
Figure 19: Representative failure cases (SFT) for the (40, 50) length group.
WITH That congth our so
SET Talkra Cass- Langth Range RO, 531 siortc AG Prodcod
ACCSSTIR ARD
32

---

Published as a conference paper at ICLR 2026
Figure 20: Representative failure cases (GRPO) for the (40, 50) length group.
GAPO Falure Case Length Sange (60, 10 Storteet: 60, Prodectdd 05
CENEPeY (rain)
Dicntt mechh target
Ralluillure Coso Length Range (40, 300 Stertee:: 40 Preicted 97
thed thated
20
33


Reviews:
[{"review_id": "JU0xuwmBVg", "reviewer": "Reviewer_UaSt", "summary": "This paper investigates compositional generalization in neural networks by introducing a controlled map-navigation testbed that cleanly separates two fundamental dimensions: spatial transfer (applying learned rules to entirely new environments) and length scaling (solving longer problems than seen during training). Using shortest-path navigation on 2D grid maps, the authors train small transformer models and systematically study how data selection and training paradigms affect extrapolative problem-solving. Their key findings show that spatial transfer is primarily enabled by maximizing the number of distinct training questions with high primitive coverage and only modest diversity, rather than collecting multiple solutions per question. In contrast, length scaling requires exposure to neighboring-but-longer examples and cannot be achieved through spatial transfer alone. Comparing supervised fine-tuning (SFT) and reinforcement learning (RL), they find that while RL provides training stability and prevents overfitting, it does not unlock capabilities beyond what the best SFT model can achieve—the performance ceiling is always set by SFT when data is sufficient and high-quality. These results provide principled insights into data-efficient training strategies for extrapolative problem-solving in language models.", "questions": "How sensitive are these findings to model scale? Would coverage versus diversity trade-offs shift dramatically with GPT-4-scale models that have vastly more capacity? Can the neighboring-but-longer insight be formalized into a curriculum learning strategy applicable beyond shortest paths? How do these findings relate to recent work on test-time compute scaling and chain-of-thought reasoning, where models might internally generate longer reasoning traces? Finally, would outcome-based RL (as tested here) versus process-based RL that rewards intermediate steps show different results for length scaling, given that shortest-path generation resembles step-by-step reasoning?", "limitations": "", "rating": 2, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The map-navigation testbed is cleverly constructed to provide truly disjoint test domains while maintaining control over primitives and rules, enabling causal analysis of data properties that is nearly impossible in realistic settings. The systematic experiments on coverage versus diversity provide actionable insights for data collection, with clear resource-efficiency guidelines showing that high coverage with modest diversity outperforms the reverse. The comparison between SFT and RL across both generalization dimensions is thorough and well-controlled, with multiple rollout configurations and warm-start conditions. The writing is clear, findings are well-supported by comprehensive ablations, and the practical takeaways are concrete.", "weaknesses": "The main limitation is generalizability. All conclusions are drawn from small (8-layer) transformers on synthetic shortest-path tasks, raising significant questions about whether these insights transfer to billion-parameter LLMs solving complex mathematical or coding problems. The testbed, while controlled, may oversimplify compositional reasoning by reducing it to spatial navigation, potentially missing critical aspects like nested recursion, abstract rule composition, or semantic understanding that characterize real problem-solving. The finding that RL doesn't surpass SFT contradicts recent work showing RL enables extrapolation in mathematical reasoning, though the authors acknowledge this may reflect differences in data quality rather than fundamental capabilities. The paper also lacks theoretical analysis explaining why coverage dominates diversity or why length scaling requires neighboring examples, relying primarily on empirical observations.\nAlso, I want you to compare offline planning line of works that also tries to enhance performance on maze tasks, and position how your work is better than existing works on offline planning in advance.\nHere are some example papers:\nYang et al, Chain of Thought Imitation with Procedure Cloning\nKim et al, How language models extrapolate outside the training data: A case study in Textualized Gridworld", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "lTSBy6lj3t", "reviewer": "Reviewer_7hks", "summary": "This paper introduces a controlled “map worlds” testbed to dissect extrapolative problem solving in Transformers along two axes of compositional generalization: spatial transfer (applying rules to disjoint environments) and length scaling (solving longer instances). Using 8-layer LLaMA-style models pretrained on random walks and fine-tuned (or RL-trained) to generate shortest paths, the authors show: (1) under fixed budget, allocating data to many distinct questions (start–end pairs) beats collecting many solutions per question; (2) coverage of primitives sets the transfer ceiling, unlocked by modest diversity, with a sharp SR inflection around 20–25% coverage; (3) diversity yields log-linear gains at moderate/high coverage but can hurt at low coverage; (4) length scaling generally fails unless training includes a small curriculum of neighboring-but-longer examples (+2–4 steps), while shorter or much longer examples help little or harm; and (5) RL (Dr.GRPO) stabilizes training and avoids overfitting but never exceeds the best SFT performance. The work offers practical data-design guidance (prioritize coverage and distinct questions; minimal solution diversity) and clarifies RL’s role as stabilizer rather than capability expander in this setting.", "questions": "- 1. **Pre-training**: Recent work suggests[1,2] that continued or mid-stage pretraining can substantially improve downstream RL gains, so it’s reasonable to worry that the findings here may be shaped by an underpowered pretraining phase. The paper pretrains on long random walks to impart “map semantics” and confirms this doesn’t leak shortest-path skills, but it does not report scale, steps, or convergence, nor ablate the pretraining budget. Without those controls, we can’t tell whether stronger pretraining would raise spatial-transfer ceilings, improve length scaling, or allow RL to surpass SFT. \n\n- 2. **Compute**: As mentioned in the paper that the budget is controlled by the percentage of possible records. Are experiments controlled with same amount of training compute? i.e. are experiments with fewer training data training on more epochs to match equal optimization steps?\n\n- 3. **Length statistic details**: The study carefully separates spatial transfer (within training-length regime) from length scaling (strictly longer than training), but it does not provide the actual path-length distributions for training or evaluation, nor how those distributions shift as coverage increases. Reporting histograms (x: path length, y: sample count) for each training setup and test split, along with Lmax per setup and the fraction of samples near Lmax, would reveal whether performance changes stem from coverage/diversity design or from incidental shifts in length exposure.\n\n- 4. **Long-to-short generalization**: The paper analyzes “short-to-long” length scaling but does not test the reverse direction. A simple control would train on a length band with relatively high minimum length and evaluate on shorter paths to see whether a long-to-short generalization effect exists.\n\n- 5. **Non-optimal navigation evaluation**: In some cases of real-world navigation tasks, people may only care about finding a feasible path rather than shortest. Is there evaluation results for this setting? Will generalization happen when training on navigating shortest paths while evaluating feasible paths?\n\n[1] Wang, Zengzhi, Fan Zhou, Xuefeng Li, and Pengfei Liu. \"Octothinker: Mid-training incentivizes reinforcement learning scaling.\" arXiv preprint arXiv:2506.20512 (2025).\n\n[2] Cen, Zhepeng, Yihang Yao, William Han, Zuxin Liu, and Ding Zhao. \"Behavior Injection: Preparing Language Models for Reinforcement Learning.\" arXiv preprint arXiv:2505.18917 (2025).", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- 1. Clear decomposition of generalization: The paper cleanly separates spatial transfer from length scaling in a controlled “map worlds” testbed, enabling precise causal insights that are hard to obtain in natural language settings.\n\n- 2. Controllable data design: The graph-based framework enables precise control over dataset factors, including node coverage (fraction of unique nodes appearing in training questions), pairing diversity (average number of endpoints per start node), and path-length regimes (via sampling constraints). This controllability supports principled ablations on how dataset composition, independent of total record count, shapes generalization.\n\n- 3.The paper systematically varies training budget as a percentage of the possible start–end records and studies trade-offs between the number of distinct questions and the number of solutions per question under approximately fixed total records. These ablations quantify data-efficiency regimes and clarify which allocations (e.g., higher question diversity vs. multiple solutions per question) most improve spatial transfer, though matching total optimization steps (compute) is not explicitly controlled.", "weaknesses": "- Synthetic scope and small models: Results are demonstrated on small LLaMA-style models and synthetic sparse grids. External validity to larger models, richer graph families, or open-domain language tasks is uncertain.\n- RL ceiling bounded by SFT without diagnosis: RL consistently fails to surpass the best SFT model, but the paper provides limited analysis of why (e.g., exploration limits, reward sparsity, credit assignment), and does not test alternative rewards (e.g., feasible-path rewards) or curricula beyond near-boundary lengths.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Yb6icIAVB1", "reviewer": "Reviewer_QLfE", "summary": "In this paper, the authors focus on the understanding of the generalization and problem solving abilities of state of the art machine learning models. The authors use the simple example of token based map navigation to study these questions. To this end, they explore a series of highly constrained evaluations in order to disentangle the effects of data coverage, diversity, and scaling.In addition, they look at the effects of reinforcement learning. A number of key findings are uncovered. Coverage is very important for spatial transfe, with diversity generally less important. Reinforcement improves optimization but does not improve transfer.", "questions": "1. Could the authors please elaborate on how the results could apply to other domains? The test-bed of navigation is quite narrow.\n\n2. Would it be possible to include any qualitative examples or failure cases to understand the difference in performance between various regimes?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. Generalization, and the understanding of what leads to generalization, is of fundamental importance in machine learning. \n\n2. Paper is well written and easy to understand.\n\n3. Although the problem and domain is quite narrow (token based navigation), evaluation is quite detailed and thorough, and the results are of interest to the community.", "weaknesses": "1. The domain used is a toy problem (token based navigation) and very narrow. It is unclear if the results in the paper hold in other domains or problems in machine learning.\n\n2. Qualitative results or a visualization of navigation capabilities (or failure cases) would strengthen the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "lAsgaSX3RG", "reviewer": "Reviewer_QYZU", "summary": "This paper introduces a map navigation benchmark based on 2D sparse grid navigation tasks, and uses it to evaluate transformer models with LLaMA-style architecture,\nThe authors analyze model performance on this benchmark using two dimensions: \n- Transfer (systematicity): solving the same class of problems in new environments, and \n- Scaling (productivity): solving harder problems after mastering simpler ones. \nThey consider two model training paradigms: (1) Supervised fine-tuning, with paths encoded as movement directions; model predicts continuation given start/end prompt. (2) Reinforcement learning, giving binary reward for valid shortest paths. They find that for supervised fine-tuning distinct questions drive transfer more than multiple solutions per question.\nTo determine which types of questions best support spatial transfer they focus on coverage (fraction of unique nodes in the training map included in training) vs diversity (average number of distinct endpoints each start node is paired with.) of training questions.", "questions": "N/A", "limitations": "", "rating": 2, "confidence": 4, "soundness": 2, "presentation": 1, "contribution": 1, "strengths": "The authors focus on defined generalization dimensions (transfer and scaling) and the experimental design appears to be sound, separating coverage vs diversity.\n\nOverall, this work clearly *intended as* a methodologically solid framework with careful experiments, however poor presentation makes this conceptual design very hard to understand and evaluate.", "weaknesses": "Presentation is very poor, making it hard to follow this paper. \n\nBeginning as early as the abstract, the writing is often superficially coherent, but conceptually incoherent - reflecting perhaps the lack of conceptual depth, or perhaps a last minute writing of work that is intended as well thought out, but obscured by poor presentation. For instance:\n\n\"_Someone who learns to walk shortest paths in New York can, upon receiving a map of Paris, immediately apply the same rule to navigate, despite never practicing there._\"\n\nSame rule (as in, the same heuristic) or same algorithm (as in, Djkstra's algorithm)? \nMuch of the field would not agree with this statement, as New York has a grid-like North American design, and Paris is an older city - meaning that different rules/heuristics and approximations will be optimal.\n\nThe next sentence then jumps topic to combining rules - \"_This ability to recombine known rules to solve novel problems exemplifies compositional generalization_..\" \nThere is no sense how this is related to the previous sentence, or the remainder of the abstract.\n\nI am unable to evaluate the paper, because I can not unearth the content from the ineffective presentation. I feel that this work is not yet ready for an archival publication, but after a careful revision it might be.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)