Seemingly Simple Planning Problems are Computationally Challenging: The Countdown Game

Michael Katz, Harsha Kokel, Sarath Sreedharan

Abstract

There is a broad consensus that the inability to form long-term plans is one of the key limitations of current foundational models and agents. However, the existing planning benchmarks remain woefully inadequate to truly measure their planning capabilities. Most existing benchmarks either focus on loosely defined tasks like travel planning or end up leveraging existing domains and problems from international planning competitions. While the former tasks are hard to formalize and verify, the latter were specifically designed to test and challenge the weaknesses of existing automated planners. To address these shortcomings, we propose a procedure for creating a planning benchmark centered around the game called Countdown, where a player is expected to form a target number from a list of input numbers through arithmetic operations. We discuss how this problem meets many of the desiderata associated with an ideal benchmark for planning capabilities evaluation. Specifically, the domain allows for an intuitive, natural language description for each problem instance, it is computationally challenging (NP-complete), and the instance space is rich enough that we do not have to worry about memorization. We perform an extensive theoretical analysis, establishing the computational complexity result and demonstrate the advantage of our instance generation procedure over public benchmarks. We evaluate a variety of existing LLM-assisted planning methods on instances generated using our procedure. Our results show that, unlike other domains like 24 Game (a special case of Countdown), our proposed dynamic benchmark remains extremely challenging for existing LLM-based approaches.

Introduction

Evaluating the planning capabilities of Large Language Models (LLMs) is a significant challenge in AI research. Existing benchmarks often suffer from fuzzy task definitions or data contamination, where models simply recall solutions from their training data. Researchers from IBM and Colorado State University propose the Countdown Game as a rigorous alternative. This arithmetic puzzle is easy to describe but computationally hard, providing a "Goldilocks" benchmark that tests genuine reasoning rather than memorization.

Theoretical Complexity and the State Space Explosion

The Countdown Problem involves reaching a target value using a set of input numbers and basic arithmetic operations (+, -, , /). The authors formally prove that this problem is NP-complete* by reducing it to the Subtraction Addition Problem (SAP). As the number of input values grows, the state space expands exponentially, making it a legitimate computational challenge for any planner.

The state space of the Countdown Game grows exponentially, surpassing the number of particles in the known universe at an input size of approximately 30.

The "Memorization" Smoking Gun

A key finding of the study is the evidence of memorization in current LLMs. Models like Llama 3.1 and DeepSeek V3 perform well on the standard "24 Game" (a common 4-input variant found online), but their accuracy drops by more than half when presented with novel Countdown instances of the same size. This suggests that LLMs are often "reciting" solutions rather than planning from scratch. Pure LLM prompting methods (Chain of Thought, Tree of Thoughts) failed almost entirely for input sizes larger than 4, scoring below 10% accuracy.

Key Results: The Planning Dip and Hybrid Success

The researchers discovered a unique difficulty transition in the Countdown Game. As input size increases, the problem moves from Easy (size 4-7) to Hard (size 8-20), and then back to Easy (size 20+). In the high-input regime, the astronomical number of possible arithmetic combinations actually increases the probability that a random search path will hit the target.

Accuracy @5 for hybrid AutoToS methods versus the symbolic ENHSP planner, illustrating the 'planning dip' and the eventual failure of symbolic planners at large scales.

To overcome the limitations of pure LLM reasoning, the authors evaluated a hybrid approach called AutoToS, where the LLM generates a symbolic search algorithm (e.g., Depth-First Search) to solve the problem. While pure symbolic planners like ENHSP failed at input sizes above 30 due to state space explosion, the LLM-generated search code maintained near 100% accuracy, demonstrating the power of combining LLM code generation with symbolic search.

Conclusion

The Countdown Game exposes the fragile nature of LLM planning. While hybrid LLM-symbolic methods show promise, the "planning dip" highlights a significant gap in autonomous reasoning. Future research may explore optimization variants of the game to further push the boundaries of AI planning capabilities.

Summary updated

Abstract

There is a broad consensus that the inability to form long-term plans is one of the key limitations of current foundational models and agents. However, the existing planning benchmarks remain woefully inadequate to truly measure their planning capabilities. Most existing benchmarks either focus on loosely defined tasks like travel planning or end up leveraging existing domains and problems from international planning competitions. While the former tasks are hard to formalize and verify, the latter were specifically designed to test and challenge the weaknesses of existing automated planners. To address these shortcomings, we propose a procedure for creating a planning benchmark centered around the game called Countdown, where a player is expected to form a target number from a list of input numbers through arithmetic operations. We discuss how this problem meets many of the desiderata associated with an ideal benchmark for planning capabilities evaluation. Specifically, the domain allows for an intuitive, natural language description for each problem instance, it is computationally challenging (NP-complete), and the instance space is rich enough that we do not have to worry about memorization. We perform an extensive theoretical analysis, establishing the computational complexity result and demonstrate the advantage of our instance generation procedure over public benchmarks. We evaluate a variety of existing LLM-assisted planning methods on instances generated using our procedure. Our results show that, unlike other domains like 24 Game (a special case of Countdown), our proposed dynamic benchmark remains extremely challenging for existing LLM-based approaches.
BibTeX
@misc{katz2025seemingly,
  author = {Michael Katz and Harsha Kokel and Sarath Sreedharan},
  title = {{Seemingly Simple Planning Problems are Computationally Challenging: The Countdown Game}},
  year = {2025},
  eprint = {2508.02900},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2508.02900},
}
Figure