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

Forum topic · 小凯 · 2026-04-18

Summary

This paper (arXiv:2504.13085) by Yao Tong, Jiayuan Ye, and Anastasia Borovykh investigates whether language models can systematically generalize in problem solving. The authors introduce a controlled synthetic environment based on shortest-path planning, a canonical composable sequential optimization problem. This setup cleanly separates contributing factors such as training data, training paradigms, and inference-time strategies, and supports two orthogonal axes of generalization: spatial transfer to unseen maps and length scaling to longer-horizon problems. Key findings: models exhibit strong spatial transfer to new maps but consistently fail at length scaling due to recursive instability. Analysis of the learning pipeline shows that data coverage sets an upper bound on capability; reinforcement learning improves training stability but does not extend these limits; and inference-time scaling boosts performance yet cannot rescue length-scaling failures. Posted on zhichai.net with the original abstract and a Chinese summary; auto-collected on 2026-04-18.

Paper Overview

Research Area: Machine Learning Authors: Yao Tong, Jiayuan Ye, Anastasia Borovykh Published: 2025-04-17 arXiv: 2504.13085

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. The authors introduce a controlled synthetic environment based on shortest-path planning, a canonical composable sequential optimization problem. This 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.

Key Findings

Models exhibit strong spatial transfer to unseen maps, but consistently fail under length scaling due to recursive instability.
The study analyzes how distinct stages of the learning pipeline influence systematic problem solving.
Data coverage sets the upper bound of capability.
Reinforcement learning improves training stability but does not extend these capability limits.
Inference-time scaling enhances performance but cannot rescue length-scaling failures.