Generalization in LLM Problem Solving: The Case of the Shortest Path

This post summarizes a paper by Anej Svete, Yuxi Xie, Mike Zhang, Mrinmaya Sachan, and Ryan Cotterell (ETH Zurich, Singapore Management University, Microsoft Research), arXiv preprint arXiv:2604.15306.

Key points

• Testbed: Shortest-path problems on grid maps, chosen because the problem is well-defined (Dijkstra, A*), easily visualized, and supports two measurable generalization dimensions: spatial generalization (new layouts) and length generalization (longer optimal paths).
• Dataset: ~12.8 million training samples covering grid sizes 5x5–15x15, obstacle densities 0–40%, and path lengths 2–30 steps, with in-distribution, spatial OOD, length OOD, and full OOD test sets.

Main findings

• Spatial generalization has limits: models trained with grid sizes up to a given maximum degrade sharply on larger grids — roughly 15% accuracy drop on 7x7, 35% on 10x10, and near-random on 15x15 for a 5x5-trained model.
• Length generalization is a hard ceiling: models fail on shortest paths longer than those seen in training (e.g., trained up to 10 steps, near-random at 15 steps). This persists even at 70B parameters.
• Scale is not a cure: more parameters improve in-distribution accuracy but barely help OOD generalization — better memory, not better reasoning.
• "Map relabeling" effect: shuffling spatial labels causes inconsistent performance across variants, suggesting memorized spatial patterns rather than a general path-finding algorithm.
• Knowing vs. executing: when prompted with Dijkstra's algorithm, models can recite the steps but still make execution errors in multi-step iteration.

Possible explanations

1. Models learn heuristics (head toward goal, avoid obstacles) rather than full algorithms. 2. Autoregressive generation limits — though the authors note even 70B models with sufficient context fail, weakening this hypothesis. 3. Statistical biases in training data (e.g., near-straight paths are more common), which models internalize instead of general planning principles.

Proposed directions

• Explicit algorithm injection via neuro-symbolic architectures.
• Structured training data covering wider length/spatial distributions (with acknowledged limits).
• Program synthesis: have the model emit code that solves the problem rather than the answer itself.
• External tool calls to a planner/solver when planning is required.

Takeaway

High in-distribution accuracy does not imply genuine understanding. Evaluation of LLMs should include systematic out-of-distribution tests for compositional, length, and abstract generalization. LLMs may be sophisticated pattern matchers rather than general reasoning engines — recognizing these limits is the starting point for responsible use and human-AI collaboration design.

References

• Svete, A., Xie, Y., Zhang, M., Sachan, M., & Cotterell, R. (2026). *Generalization in LLM Problem Solving: The Case of the Shortest Path*. arXiv preprint arXiv:2604.15306.
• Feng et al. (2024). *Towards Revealing the Mystery behind Chain of Thought*
• Wu et al. (2024). *Logic-LM: Empowering Large Language Models with Symbolic Solvers*
• Creswell et al. (2023). *Faithful Reasoning Using Large Language Models*