Mist on the Shortest Path: How Far Do LLMs Really Generalize?

This post is a Chinese-language editorial review of the paper "Generalization in LLM Problem Solving: The Case of the Shortest Path" by Anej Svete, Yuxi Xie, Mike Zhang, Mrinmaya Sachan, and Ryan Cotterell (ETH Zurich, Singapore Management University, Microsoft Research; arXiv:2604.15306).

Why the Shortest Path?

The authors chose shortest-path planning as a testbed because it is a well-defined graph problem with known algorithms (Dijkstra, A*), is easily visualized as grids, and allows systematic control over two generalization axes:

• Spatial generalization — solving new grid layouts (larger grids, unseen obstacle distributions) after training on other layouts.
• Length generalization — solving instances whose optimal paths are longer than any seen during training.

The dataset comprised roughly 12.8 million training samples covering 5×5 to 15×15 grids, 0–40% obstacle density, and optimal path lengths of 2–30 steps, with test sets for in-distribution (ID), spatial OOD, length OOD, and full OOD conditions.

Key findings

• Spatial generalization has limits. Accuracy drops markedly when test grids exceed the training distribution — the post cites roughly 15% degradation on 7×7 grids after 5×5 training, ~35% on 10×10, and near-random performance on 15×15.
• Length generalization is a hard ceiling. When required paths exceed the longest training paths (e.g., training capped at 10 steps, tested at 12–15 steps), performance collapses toward random levels — even when the spatial layout is familiar.
• Scale is not a cure. Models from 1B to 70B parameters improve on in-distribution tasks with scale, but OOD generalization barely improves — more parameters appear to buy better memorization, not generalization.
• Map relabeling fragility. Small cosmetic changes to test maps (e.g., moving the start position) produce inconsistent performance, suggesting memorized spatial patterns rather than a learned path-finding algorithm.
• Knowing vs. executing. When taught Dijkstra in the prompt, models can recite the algorithm's steps but still fail to execute it reliably in multi-step iterations.

Interpretations discussed

1. Heuristics, not algorithms: models may learn rules like "head toward the goal" or "avoid obvious obstacles" that fail in complex detours. 2. Autoregressive limitations: step-by-step path generation loses track on long paths — though the failure of even 70B models weakens this explanation. 3. Statistical bias in training data: models may internalize frequent path patterns (e.g., near-straight paths) rather than general planning principles.

The post connects this to broader evidence of weak compositional generalization in LLMs across math reasoning, code generation, and logical reasoning.

Proposed remedies

• Explicit algorithm injection via neuro-symbolic architectures
• Structured training data covering wider length and spatial distributions (with acknowledged limits, since path lengths are unbounded)
• Program synthesis: have models write code that solves the problem rather than answer directly
• External tool calling: delegate planning to a dedicated solver

Takeaway

The review's central lesson for AI evaluation: high in-distribution accuracy does not demonstrate genuine understanding. Robust claims about capability require systematic out-of-distribution testing along compositional, length, and abstraction dimensions. LLMs may be extremely sophisticated pattern matchers rather than general reasoning engines — and recognizing that boundary is the starting point for responsible use and design of human–AI collaboration.

Reference

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.