Seemingly Simple Planning Problems are Computationally Challenging: The Countdown Game

Michael Katz, Harsha Kokel, Sarath Sreedharan

TL;DR

This paper introduces a rigorous, dynamic planning benchmark for Large Language Models (LLMs) based on the arithmetic game Countdown. The authors prove that the problem is NP-complete and demonstrate that while LLMs appear to excel at simple instances found on the internet, their performance collapses on newly generated, uncontaminated data.

What Problem Does This Paper Address?

Evaluating the long-term sequential planning capabilities of foundational models is notoriously difficult. Current benchmarks generally fall into two flawed categories:

  1. Fuzzy tasks (like travel planning) that are described in natural language but are incredibly hard to formalize and verify automatically.
  2. Static classical planning domains (from International Planning Competitions) that are often poorly suited for natural language prompting and suffer from data contamination, meaning LLMs might simply memorize solutions from their training data.

To bridge this gap, the authors propose using the Countdown numbers game. In Countdown, a player is given a list of numbers and must use basic arithmetic operations ($+, -, \times, /$) to reach a specific target number. This domain is ideal because it is easy to describe in natural language, has a fully specified and verifiable state-action space, and scales computationally to challenge even the best planners.

Figure 1: The state space size for the Countdown problem.

Methods

The authors approach the problem from both a theoretical and practical perspective:

  • Complexity Analysis: They formally prove that the Countdown Decision Problem (CDP) is NP-hard via a polynomial reduction from the 3-Partition Problem (3-PP).
  • PDDL Formulation: They translate Countdown into the Planning Domain Definition Language (PDDL), allowing them to establish a baseline using a state-of-the-art classical numeric planner (ENHSP).
  • Dynamic Instance Generation (CD): To prevent LLM memorization, they design a novel generation algorithm. Instead of randomly combining numbers to find a target, their algorithm performs multiple random walks and selects the least frequent resulting target number, intentionally creating harder instances with fewer valid paths to the solution.

Datasets

The paper evaluates planning methods across four distinct datasets (each containing 100 instances per size):

  • CD (Countdown): The authors' newly proposed dataset, optimized for difficulty by minimizing solution paths.
  • RG (Reasoning-Gym): A baseline dataset that generates targets using random sequential operations.
  • SoS (Stream-of-Search): A dataset generated backwards from a target using breadth-first exploration.
  • 24Game: A static, widely used benchmark consisting of size-4 instances scraped directly from the internet.
Figure 2: Solution counts, various datasets.

Key Insights and Ideas

  • The Illusion of Competence (Data Contamination): LLMs like Llama 3.1 and Qwen 2.5 achieve up to 90% accuracy on the standard internet-scraped 24Game benchmark. However, when tested on the authors' CD dataset of the exact same size (4 input numbers), their accuracy plummets to under 10%. This strongly implies that previous high scores were artifacts of memorization rather than true planning capabilities.
  • The Double Phase Transition: When testing symbolic search methods, the authors discovered a fascinating non-monotonic difficulty curve. As the input size grows, the problem transitions from easy to hard (around size 8), but then surprisingly transitions from hard back to easy (around size 20).

Why does it get easy again? With more numbers available, it becomes statistically trivial to generate an intermediate value of 0. Once a 0 is created, the strict constraint of having to use every single input number effectively vanishes—any remaining unused numbers can simply be multiplied by 0 and added to the target without changing the result.

Figure 4: The accuracy of ENHSP and AutoToS for the Countdown problem, various datasets.

Key Results

  • Standard LLM Planning Fails: Traditional prompting methods—including Input/Output (IO), Chain of Thought (CoT), and Tree of Thoughts (ToT)—all scored below 10% accuracy on uncontaminated datasets for any input size greater than 4.
  • Reasoning Models Struggle Too: Advanced reasoning models (like Qwen3-Thinking and DeepSeek R1) showed marginal improvements on small instances but still failed to scale effectively as the input size increased.
  • Code Generation Wins: The best-performing method was AutoToS, a framework where the LLM is not asked to solve the math puzzle directly, but is instead tasked with writing a symbolic solver (like a Depth-First Search algorithm) in Python. This method achieved 100% accuracy on very small and very large instances, though it still suffered during the first phase transition (sizes 8–15).
Figure 5: Accuracy @5 of LLM planning meth- ods on CD.

Limitations and Future Work

While Countdown serves as an excellent benchmark, the authors note that the current formulation requires using all input numbers exactly once.

For future work, they propose exploring variations of the game, such as:

  • Allowing solutions to use only a subset of the provided numbers.
  • Introducing varying costs for different arithmetic operations (e.g., making division more "expensive" than addition) to force models to optimize for the lowest-cost plan rather than just any valid sequence.

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. From a world-model perspective, each instance induces a fully specified transition model (dynamics) over states and actions, enabling evaluation of planning with verifiable outcomes. 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