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

arXiv: https://arxiv.org/abs/2601.20856 · HTML: https://mlsanity.com/paper/2601.20856/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Placed in Reasoning for agents, planning and code, one of 17 directions in LLM reasoning.
- Builds on 18 of its 55 references that are in the map.
- First posted on arXiv 28 Jan 2026.

## Placed in

- LLM reasoning / [Reasoning for agents, planning and code](https://mlsanity.com/lr/reasoning-for-agents-planning-and-code/)

## Builds on (most cited first, 18 of 18)

- [OpenAI Gym](https://mlsanity.com/paper/1606.01540/) (2016)
- [gpt-oss-120b & gpt-oss-20b Model Card](https://mlsanity.com/paper/2508.10925/) (2025)
- [OpenAI o1 System Card](https://mlsanity.com/paper/2412.16720/) (2024)
- [Kimi k1.5: Scaling Reinforcement Learning with LLMs](https://mlsanity.com/paper/2501.12599/) (2025)
- [PlanBench: An Extensible Benchmark for Evaluating Large Language Models on Planning and Reasoning about Change](https://mlsanity.com/paper/2206.10498/) (2022)
- [The Illusion of Thinking: Understanding the Strengths and Limitations of Reasoning Models via the Lens of Problem Complexity](https://mlsanity.com/paper/2506.06941/) (2025)
- [PlanGenLLMs: A Modern Survey of LLM Planning Capabilities](https://mlsanity.com/paper/2502.11221/) (2025)
- [lmgame-Bench: How Good are LLMs at Playing Games?](https://mlsanity.com/paper/2505.15146/) (2025)
- [Less is More: Recursive Reasoning with Tiny Networks](https://mlsanity.com/paper/2510.04871/) (2025)
- [Understanding the Capabilities of Large Language Models for Automated Planning](https://mlsanity.com/paper/2305.16151/) (2023)
- [Holistic Evaluation of Multimodal LLMs on Spatial Intelligence](https://mlsanity.com/paper/2508.13142/) (2025)
- [Solving a Million-Step LLM Task with Zero Errors](https://mlsanity.com/paper/2511.09030/) (2025)
- [Planning in a recurrent neural network that plays Sokoban](https://mlsanity.com/paper/2407.15421/) (2024)
- [ReCAP: Recursive Context-Aware Reasoning and Planning for Large Language Model Agents](https://mlsanity.com/paper/2510.23822/) (2025)
- [Reasoning LLMs are Wandering Solution Explorers](https://mlsanity.com/paper/2505.20296/) (2025)
- [End-to-end PDDL Planning with Hardcoded and Dynamic Agents](https://mlsanity.com/paper/2512.09629/) (2025)
- [CharBench: Evaluating the Role of Tokenization in Character-Level Tasks](https://mlsanity.com/paper/2508.02591/) (2025)
- [On the Limits of Innate Planning in Large Language Models](https://mlsanity.com/paper/2511.21591/) (2025)

## Built on by (most cited first, 2 of 2)

- [TopoBench: Benchmarking LLMs on Hard Topological Reasoning](https://mlsanity.com/paper/2603.12133/) (2026)
- [The Complexity Ceiling Benchmark: A Multi-Domain Evaluation of Sequential Reasoning Under Depth Scaling](https://mlsanity.com/paper/2606.29278/) (2026)

## Abstract (arXiv)

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.