mlsanityData to 14 Oct 2026

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

arXiv 2601.20856 ↗First posted 28 Jan 2026cs.AIcited by 2

On the map: LLM reasoning → Reasoning for agents, planning and code

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.

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.

Builds on

18 of 55 references.

Closest ancestors · 2

Same direction, newest first

  1. 2024OpenAI o1 System Card21 Dec
  2. 2022PlanBench: An Extensible Benchmark for Evaluating Large Language Models on Planning and Reasoning about Change21 Jun

Other references · 16

  1. 2016OpenAI Gymcited by 1,736
  2. 2025gpt-oss-120b & gpt-oss-20b Model Cardcited by 1,386
  3. 2025Kimi k1.5: Scaling Reinforcement Learning with LLMscited by 1,210
  4. 2025The Illusion of Thinking: Understanding the Strengths and Limitations of Reasoning Models via the Lens of Problem Complexitycited by 302
  5. 2025PlanGenLLMs: A Modern Survey of LLM Planning Capabilitiescited by 83
  6. 2025lmgame-Bench: How Good are LLMs at Playing Games?cited by 55
  7. 2025Less is More: Recursive Reasoning with Tiny Networkscited by 45
  8. 2023Understanding the Capabilities of Large Language Models for Automated Planningcited by 34
  9. 2025Holistic Evaluation of Multimodal LLMs on Spatial Intelligencecited by 29
  10. 2025Solving a Million-Step LLM Task with Zero Errorscited by 19
  11. 2024Planning in a recurrent neural network that plays Sokobancited by 18
  12. 2025ReCAP: Recursive Context-Aware Reasoning and Planning for Large Language Model Agentscited by 13
4 more
  1. 2025Reasoning LLMs are Wandering Solution Explorerscited by 6
  2. 2025End-to-end PDDL Planning with Hardcoded and Dynamic Agentscited by 5
  3. 2025CharBench: Evaluating the Role of Tokenization in Character-Level Taskscited by 3
  4. 2025On the Limits of Innate Planning in Large Language Modelscited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 2.

2 papers.

  1. 2026TopoBench: Benchmarking LLMs on Hard Topological Reasoningcited by 3
  2. 2026The Complexity Ceiling Benchmark: A Multi-Domain Evaluation of Sequential Reasoning Under Depth Scalingcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024Exploring and Benchmarking the Planning Capabilities of Large Language Models
  2. 2024Thinking Forward and Backward: Effective Backward Planning with Large Language Models
  3. 2026Revisiting the Travel Planning Capabilities of Large Language Models
  4. 2024On the Self-Verification Limitations of Large Language Models on Reasoning and Planning Tasks
  5. 2026PlanningBench: Generating Scalable and Verifiable Planning Data for Evaluating and Training Large Language Models
  6. 2025Large Language Models for Planning: A Comprehensive and Systematic Survey
  7. 2026Analysis of Optimality of Large Language Models on Planning Problems
  8. 2026PPA-Plan: Proactive Pitfall Avoidance for Reliable Planning in Long-Context LLM Reasoning