The Compositional Boundary: Why LLMs Fail to Scale Sequential Reasoning

The question of whether large language models can achieve systematic generalization remains one of the most contested issues in artificial intelligence research. While these models demonstrate impressive performance on reasoning benchmarks, it remains unclear whether they learn underlying algorithmic principles or merely interpolate from memorized patterns. In "Generalization in LLM Problem Solving: The Case of the Shortest Path," published at ICLR 2026, Tong et al. introduce a rigorous controlled framework that disentangles these factors through the lens of shortest path planning. Their work reveals a striking asymmetry: models generalize robustly across spatial configurations yet fail catastrophically when asked to compose solutions across longer horizons. This finding carries profound implications for the limits of compositional reasoning in autoregressive systems.

The Two Axes of Generalization

The authors construct their investigation around composable sequential optimization problems (SOPs), where solving a task requires composing locally valid decisions into a globally optimal sequence. Formally, an SOP is defined by a state space, action space, transition rule, goal set, and global objective. Shortest path planning serves as an ideal testbed because it satisfies the composability property: the optimal path from node i to node j equals the concatenation of optimal subpaths through any intermediate node k. This mathematical structure allows precise measurement of whether models learn to compose solutions or merely memorize specific trajectories.

They evaluate generalization along two orthogonal axes. Spatial transfer tests whether models apply learned mobility rules to entirely unseen grid maps with novel start and end positions. Here, models exhibit strong generalization, successfully navigating new spatial configurations not present in training. This suggests that LLMs can indeed extract and apply abstract structural rules when the underlying problem complexity remains constant.

However, length scaling presents a different picture. When tested on paths requiring more steps than seen during training, models fail due to what the authors term recursive instability. Unlike spatial transfer, which tests structural novelty within fixed complexity bounds, length scaling tests compositional capacity: can the model recursively apply the same decision rule across an extended horizon? The answer appears to be no. Errors compound as the path length increases, indicating that autoregressive generation lacks the iterative stability required for extended sequential reasoning. The authors identify this recursive instability as the primary barrier to systematic generalization in sequential tasks.

Disentangling Training Dynamics and Inference Strategies

The paper’s controlled setup enables precise attribution of these limitations to specific stages of the learning pipeline. Regarding training data, the authors find that capability limits are determined primarily by coverage of distinct questions rather than the number of solutions per question. More significantly, training examples featuring broader primitive coverage prove more valuable than those offering diverse combinations of the same primitives. For length scaling specifically, models require exposure to slightly longer training examples to handle extended horizons, suggesting that out of distribution length generalization does not emerge naturally from shorter sequence training.

The comparison between supervised fine tuning (SFT) and reinforcement learning (RL) yields particularly nuanced results. While RL improves training stability and reduces variance, it does not surpass the performance ceiling established by SFT. Both paradigms exhibit similar error patterns, indicating that RL’s policy optimization does not induce novel algorithmic capabilities beyond what SFT extracts from the data. This challenges the assumption that RL, through exploration and reward shaping, might discover compositional strategies not present in the supervised dataset. The authors further observe that RL appears to restrict the effective solution space compared to SFT, potentially limiting the diversity of solutions the model considers.

Inference time scaling strategies, including advanced search and sampling methods, enhance performance for both training paradigms but cannot rescue length scaling failures. This suggests that the limitation is not merely one of inference time computation or search efficiency, but rather a fundamental constraint in how the model represents and executes sequential decision processes. The gap between intrinsic capability and expressed performance can be narrowed through better inference strategies, yet the intrinsic capability itself remains bounded by the training distribution’s horizon.

Your Take: The Architecture of Composition

These findings illuminate a fundamental tension in current language model architectures. The success on spatial transfer indicates that transformers can learn abstract relational rules, at least when the reasoning depth remains bounded. However, the failure under length scaling suggests that autoregressive next token prediction lacks the iterative stability required for unbounded compositional reasoning.

I interpret the recursive instability as evidence that LLMs do not truly implement dynamic programming or recursive algorithms internally. Instead, they approximate solution surfaces through pattern matching. When the pattern extends beyond training horizons, the approximation error accumulates multiplicatively rather than additively. This aligns with theoretical work suggesting that transformers, while capable of simulating algorithms in principle, lack the mechanism to enforce computational consistency across unbounded steps.

The equivalence between RL and SFT ceilings is particularly telling. If RL cannot discover novel compositional strategies beyond the training distribution, this implies that the bottleneck lies not in the optimization landscape but in the representational capacity of the architecture itself. The policy gradient updates appear to refine existing behavioral patterns rather than induce new algorithmic structures. This suggests that current RL techniques, at least in their standard implementations, cannot compensate for insufficient training data coverage.

This research also raises questions about the role of chain of thought reasoning. The authors use a direct answer setting, requiring complete path generation without intermediate steps. While the paper does not explicitly compare this to chain of thought methods, the recursive instability finding suggests that even with explicit reasoning steps, the fundamental limitation of error accumulation across long horizons would persist. The issue is not merely the expression of reasoning but the stability of the underlying computation.

Limitations and Future Directions

The study’s synthetic environment, while methodologically necessary for controlled analysis, necessarily abstracts away the semantic richness of natural language reasoning. Shortest path problems have unambiguous optimal solutions and easily verifiable rewards, unlike many real world reasoning tasks where correctness criteria are fuzzy. Whether these findings generalize to linguistic reasoning tasks remains an open empirical question.

Furthermore, the paper focuses on deterministic environments. Many real world planning tasks involve stochastic transitions or partial observability, which might introduce additional failure modes or, paradoxically, force the development of more robust planning mechanisms through training. The authors also evaluate models in isolation; real world deployment often involves tool use or external verification that might mitigate recursive instability.

Conclusion

Tong et al. provide compelling evidence that current language models possess a fragmented form of systematic generalization. They can abstract and transfer structural rules across spatial configurations, yet they cannot compose these rules across extended temporal horizons. This compositional boundary appears robust across training paradigms and inference strategies, suggesting that overcoming it may require architectural innovations rather than scale or data improvements alone.

The research leaves us with a critical question: can we design architectures that maintain the representational flexibility of transformers while incorporating the iterative stability of symbolic systems? Until then, the recursive instability identified in this work defines a hard limit on the depth of reliable reasoning we can expect from autoregressive language models. Future work might explore hybrid approaches that explicitly separate planning from generation, or investigate whether test time training on specific problem instances can temporarily overcome these horizon limitations. The shortest path may be simple to define, but for current LLMs, extending that path remains unexpectedly difficult.