SokoBench: Evaluating Long-Horizon Planning and Reasoning in Large Language Models

Sebastiano Monti, Carlo Nicolini, Gianni Pellegrini, Jacopo Staiano, Bruno Lepri

TL;DR

SokoBench introduces a highly simplified, linear-corridor Sokoban benchmark designed to isolate and evaluate the long-horizon planning capabilities of Large Reasoning Models (LRMs). The study reveals a sharp drop-off in performance when tasks require more than 25 moves, exposing fundamental architectural limitations in internal state tracking and sequential logic. Even when paired with external symbolic PDDL solvers in an "LLM-modulo" setup, models still struggle due to a lack of inherent spatial grounding.

What Problem Does This Paper Address?

Automated planning—generating a sequence of actions to achieve a goal—is a cornerstone of true artificial intelligence. While modern Large Reasoning Models (LRMs) show impressive capabilities in short-term reasoning and natural language understanding, their long-horizon planning remains weak.

Previous benchmarks often conflated planning depth with environmental complexity (such as high branching factors or complex state persistence). To pinpoint exactly why models fail, the authors of this paper strip away the noise. They ask a fundamental question: Can an LRM maintain a coherent plan over a long, structurally trivial sequence of actions without external memory or feedback?

Methods

The authors evaluate state-of-the-art reasoning models (including DeepSeek R1 and GPT-5 variants) using two distinct experimental setups:

  1. 1-shot Inference: The LRM relies entirely on its internal state representation. Given a single demonstration and an ASCII map, it must output the complete, optimal sequence of moves (e.g., Move Left, Push Up) inside text tags.
  2. LLM-Modulo Framework: To see if external tools can fix internal planning deficits, the authors build an agentic pipeline using the Model Context Protocol (MCP). Instead of solving the puzzle directly, the LRM generates a formal problem description in PDDL (Planning Domain Definition Language). This description is fed to an external symbolic planner (like Fast-Downward). If the planner encounters syntax or logical errors, the feedback is sent back to the LRM for up to three correction attempts.

To evaluate performance thoroughly, the authors look beyond binary success/failure, measuring Prefix Accuracy (how much of the initial plan was correct before a mistake occurred) and Manhattan Distance (how physically close the agent got to the goal).

Overview of the LLM-Modulo pipeline vs. standard puzzle representation

Datasets

The authors introduce SokoBench, a benchmark consisting of narrow, corridor-like Sokoban maps of width $\ell$ and height 1. Each map contains exactly one player, one box, and one goal arranged in a straight line.

Because the environment has only one degree of freedom, the corridor length $\ell$ serves as a direct proxy for difficulty: the longer the corridor, the longer the planning horizon. The dataset features map lengths ranging from 5 to 100 (in increments of 5). Each map is also evaluated across four rotations ($0^\circ, 90^\circ, 180^\circ, 270^\circ$) to mitigate pretraining memorization risks, resulting in 80 distinct evaluation configurations.

Key Insights and Ideas

  • LRMs as "Wanderers", Not Explorers: Qualitative analysis of the models' reasoning traces shows that they frequently exhaust token limits by repeating the exact same actions in loops. They lack a mechanism to track a "visited-state set," leading to aimless wandering rather than systematic state-space exploration.
  • The Counting Bottleneck: The primary driver of failure isn't logical complexity, but a basic inability to maintain accurate internal counts over long sequences. A tiny per-step probability of miscounting the map's dimensions compounds exponentially over long horizons.
  • Tool-Use Fragility: Offloading the planning to a symbolic solver sounds ideal, but tool-use itself proved highly fragile. Models like DeepSeek R1, Gemini 2.5 Flash, and Claude 3.5 Haiku struggled to consistently output valid PDDL syntax or manage the tool-calling loop, leaving GPT-5-mini as the only model capable of completing the LLM-modulo evaluation.

Key Results

  • The 25-Move Wall: In the 1-shot setting, all tested models suffered a catastrophic performance collapse when the corridor length required more than 25–30 moves.
Accuracy and reasoning token scaling for the 1-shot LRM experiments
  • High Variance in Failure: Successful completions were concise and consistent, but incorrect answers showed massive variability in token counts. When a model loses its place in the sequence, its reasoning derails unpredictably.
  • Symbolic Solvers Help, But Don't Cure: The LLM-modulo setup smoothed out the sharp performance drops and mathematically prevented illegal moves (like walking through walls). However, accuracy still degraded on longer maps because the LRM frequently miscounted the corridor length when writing the PDDL problem file.
LLM-Modulo performance results for GPT-5-mini
  • Orientation Bias: Surprisingly, models performed significantly worse on vertical corridors than horizontal ones, likely due to how newlines disrupt spatial tokenization.

Limitations and Future Work

The authors acknowledge that SokoBench represents a lower bound on planning ability; it tests sequential tracking rather than complex multi-box deadlocks or spatial branching. Furthermore, evaluating against a single exact reference plan is highly restrictive.

Future work will focus on expanding the benchmark to include obstacles and deadlocks, utilizing solver-based verification to accept alternative valid plans, and experimenting with alternative text encodings (like coordinate-numbered grids) to help models overcome their spatial tokenization blindness.

Summary updated

Abstract

Although the capabilities of large language models have been increasingly tested on complex reasoning tasks, their long-horizon planning abilities have not yet been extensively investigated. In this work, we provide a systematic assessment of the planning and long-horizon reasoning capabilities of state-of-the-art Large Reasoning Models (LRMs). We propose a novel benchmark based on Sokoban puzzles, intentionally simplified to isolate long-horizon planning from state persistence. Our findings reveal a consistent degradation in planning performance when more than 25 moves are required to reach the solution, suggesting a fundamental constraint on forward planning capacity. We show that equipping LRMs with Planning Domain Definition Language (PDDL) parsing, validation, and solving tools allows for modest improvements, suggesting inherent architectural limitations which might not be overcome by test-time scaling approaches alone.
BibTeX
@article{monti2026sokobench,
  author = {Sebastiano Monti and Carlo Nicolini and Gianni Pellegrini and Jacopo Staiano and Bruno Lepri},
  title = {{SokoBench: Evaluating Long-Horizon Planning and Reasoning in Large Language Models}},
  journal = {Trans. Mach. Learn. Res.},
  year = {2026},
}
Figure