Why Language Models Fail at Longer Problems: A Shortest Path Study

Paper: 2604.15306 Authors: Yao Tong, Jiayuan Ye, Anastasia Borovykh, Reza Shokri Categories: cs.AI, cs.LG

The Gap

We know LLMs can solve problems, but when they fail, we can’t tell why. Is it bad training data? Wrong training method? Poor inference strategy? Real-world tasks mix all these factors together, making diagnosis impossible. Prior work on generalization tests LLMs on messy, uncontrolled tasks where failure could mean anything.

This paper isolates the variables. It uses shortest-path planning—a clean, composable problem where you can separately control data coverage, training paradigm, and inference strategy. Two generalization axes emerge: spatial (new maps) and length (longer paths). The setup lets you ask: which stage of the pipeline breaks generalization?

Messy real-world task
         |
         v
    [Failure]
         |
         +---> Data? Training? Inference? (can't tell)

Controlled shortest-path setup
         |
         +---> Spatial axis: new maps
         +---> Length axis: longer paths
         |
         v
    [Failure]
         |
         +---> Recursive instability (isolated cause)

The Increment

One sentence: Before this paper, we knew LLMs sometimes fail to generalize but couldn’t separate data issues from architectural limits; after, we have evidence that length-scaling failure is a fundamental recursive instability, not fixable by more data or better training.

Core Mechanism

The method constructs grid-world maps with obstacles. Each problem: find the shortest path from start to goal. Models are trained on paths of certain lengths and map configurations, then tested on (1) unseen maps of similar length (spatial transfer) and (2) longer paths on similar maps (length scaling).

Training varies across three paradigms: supervised learning on optimal paths, reinforcement learning with reward shaping, and inference-time search (beam search, best-of-N sampling). Data coverage is controlled by varying how many map configurations and path lengths appear during training.

The key measurement: does the model’s error rate stay flat (generalization) or explode (failure) when you change the test condition? Spatial transfer tests whether the model learned the planning algorithm. Length scaling tests whether that algorithm remains stable when applied recursively over more steps.

Training:
  Maps: [M1, M2, ..., Mk]  (k configurations)
  Paths: length <= L
         |
         v
    [Model learns planning]
         |
         +---> Test on new map Mk+1, length L
         |     (spatial transfer)
         |
         +---> Test on map M1, length L+10
               (length scaling)

Think of it like teaching someone to navigate a neighborhood. Spatial transfer is: can they navigate a new neighborhood with the same skills? Length scaling is: can they plan a route that’s twice as long without getting lost? The paper finds people (models) handle new neighborhoods fine but consistently get lost on longer routes—not because they forgot the rules, but because small errors compound over more steps.

Key Concepts

• Recursive instability: When a model applies the same operation repeatedly (like planning one step, then another, then another), small errors at each step can accumulate. If the error grows faster than linearly with the number of steps, the process becomes unstable. In shortest-path planning, this means the model might correctly plan 5-step paths but fail catastrophically at 15 steps—not because it doesn’t know the rules, but because tiny mistakes in early steps derail later decisions. It’s like a rounding error in a calculator: fine for one calculation, disastrous after a thousand.

• Spatial transfer vs length scaling: These are orthogonal generalization axes. Spatial transfer asks: does the model understand the abstract algorithm (e.g., “avoid obstacles, move toward goal”) well enough to apply it in new environments? Length scaling asks: does that algorithm remain numerically stable when applied for more iterations? A model can ace spatial transfer (proving it learned the algorithm) while failing length scaling (proving the algorithm’s implementation is unstable). This separation is impossible in most real-world tasks.

Framework Shift

Before (mainstream approach):        After (this paper):

Test on complex real tasks           Test on synthetic controlled task
    |                                     |
    v                                     v
[Failure observed]                   [Failure observed]
    |                                     |
    +---> Blame: data? training?          +---> Spatial: success
          inference? (unclear)                  Length: failure
                                                     |
                                                     v
                                                Isolated cause:
                                                recursive instability

From “we see failures but can’t diagnose them” to “we isolate failure modes and trace them to specific causes,” the core shift is controlled experimentation over naturalistic observation.

Expert Assessment

Problem choice: Real gap. The field has been arguing about LLM generalization for years with no clean experiments. Shortest-path planning is a smart choice—simple enough to control, complex enough to matter. It sits at the intersection of reasoning research and systematic generalization, both hot topics.

Method maturity: Mostly solid experimental design. The separation of spatial vs length axes is elegant. However, the paper leans on grid-world maps, which may not capture the full complexity of real reasoning tasks. The recursive instability diagnosis is insightful but could use more theoretical grounding—why does this instability arise in transformers specifically?

Experimental integrity: Baselines are fair. The paper tests multiple training paradigms (supervised, RL, inference-time scaling) and shows none rescue length-scaling failures. One concern: the longest paths tested are still relatively short (20-30 steps). Would the pattern hold at 100+ steps? The numbers are believable, but the paper could benefit from error bars and more runs.

Writing quality: Clear overall, but Section 4 (results) is dense with figures. The paper front-loads too much setup and buries the key finding (recursive instability) in the discussion. Rewriting the intro to lead with “we find spatial transfer works but length scaling fails due to recursive instability” would sharpen the narrative.

Verdict: weak accept — Solid controlled experiment with a clear finding, but limited theoretical depth and narrow task scope prevent it from being a strong contribution.

Takeaways

If you’re building LLMs for multi-step reasoning, test length scaling separately from spatial transfer. Don’t assume that good performance on short problems means the model will handle long ones—recursive instability is real and won’t be fixed by scaling up data or compute.

For researchers: synthetic controlled environments like this are underused. When debugging generalization failures, isolate variables instead of throwing more data at the problem.

For practitioners: if your LLM-based system involves iterative planning or multi-step reasoning, add explicit stability checks. Consider hybrid approaches where LLMs generate candidate steps but a symbolic verifier catches compounding errors.