SokoBench: Evaluating Long-Horizon Planning and Reasoning in Large Language Models
This work addresses the need for systematic assessment of planning abilities in AI models, particularly for researchers and developers in machine learning, though it is incremental as it builds on existing evaluation frameworks.
The paper tackled the problem of evaluating long-horizon planning in large language models by introducing SokoBench, a benchmark based on Sokoban puzzles, and found that performance degrades significantly when more than 25 moves are required, indicating a fundamental constraint on forward planning capacity.
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.