Seemingly Simple Planning Problems are Computationally Challenging: The Countdown Game

Michael Katz, Harsha Kokel, Sarath SreedharanSubmission to ICLR 2026 · Rejected

TL;DR

While large language models (LLMs) often excel at popular puzzle benchmarks like the "24 Game," this paper proves that the generalized Countdown Game is NP-complete and reveals that prior LLM successes likely stemmed from web data contamination. By introducing a new instance-generation method and evaluating symbolic, LLM-based, and reasoning-model planners, the authors show that standard LLM planning completely collapses on freshly generated instances once input sizes grow beyond four numbers.

What Problem Does This Paper Address?

Evaluating whether foundation models can form long-term sequential plans is currently bottlenecked by flawed benchmarks:

  1. Fuzzy tasks (e.g., travel planning) are intuitive but lack rigorous formalization and sound validators.
  2. Classical planning benchmarks (e.g., IPC domains translated to PDDL) were tailored to test legacy automated planners and often translate poorly to natural language prompts.
  3. Puzzles (like the 24 Game) have tiny state spaces (roughly 4,500 states) and rely on static datasets scraped from the internet, introducing significant risk of memorization.

The authors propose using the Countdown Game—where players must reach a target integer from a list of input integers using basic arithmetic operations ($+, -, \times, /$)—as an ideal planning benchmark that is mathematically formal, easy to describe in natural language, verifiable, and computationally hard.

Methods

  • Theoretical Complexity Analysis: The authors formally map Countdown to a state transition system and prove that the Countdown Decision Problem (CDP) is NP-hard via a polynomial-time reduction from the 3-Partition Problem (3-PP).
  • Target Generation Strategy: Rather than searching backward from a target (which scales exponentially) or picking random forward expressions (which yields dense, easily solvable targets), the authors sample random forward paths and select the least frequent target ($\tau$). This produces instances with drastically fewer valid solution paths, creating provably harder instances.
  • Symbolic Planning Baseline: The problem is formalized in PDDL2.1 and solved using ENHSP, an off-the-shelf numeric heuristic search planner.
  • LLM Evaluated Frameworks:
  • Standard prompting: Input/Output (IO) and Chain-of-Thought (CoT).
  • Search-based prompting: Tree of Thoughts (ToT).
  • Program synthesis: AutoToS, where the LLM writes a Python search algorithm once, which is then executed symbolically.
  • Evaluated models included standard open weights (Llama 3.1 405B, Qwen 2.5 72B, DeepSeek V3) and reasoning models (DeepSeek R1, Qwen3-30B-Thinking, GPT-OSS-120B).

Datasets

The authors compare four datasets (100 instances per size):

  • CD (Proposed): Dynamically generated Countdown instances with input sizes $n \in [4, 50]$, chosen via the least-frequent target heuristic.
  • RG: Countdown instances from Reasoning-Gym, generated via random operation walks.
  • SoS: Instances from Stream-of-Search, generated backward from targets (computationally bounded to $n \le 9$).
  • 24Game: The standard 100 internet-scraped instances of size 4 used in original Tree-of-Thought benchmarks.

Key Insights and Ideas

  • The Memorization Mirage: On the web-scraped 24 Game, Llama 3.1 405B with Tree-of-Thoughts achieves 90% accuracy@5. But on newly generated 4-number Countdown instances with arbitrary targets, accuracy plummets to 40% (and drops to just 12% mean accuracy). The strong performance reported in earlier literature was heavily inflated by pre-training contamination.
  • Two Phase Transitions: Symbolic solvers exhibit a non-monotonic difficulty curve. Instances transition from easy to hard around size 8 (combinatorial explosion outpaces heuristics), but then transition back from hard to easy around size 20. With 20+ numbers available, the density of reachable numbers is so immense that finding some valid arithmetic sequence becomes easy again for blind search algorithms.
  • Prompting Fails, Code Generation Wins: Pure direct prompting methods (IO/CoT/ToT) fail completely as problem sizes scale, scoring under 10% on sizes $>4$. In contrast, AutoToS—prompting an LLM to generate a symbolic depth-first search solver—solved small instances with 100% accuracy with zero prompt-token costs at test time.

Key Results

  • Performance Drop on Unseen Size-4 Tasks:
  • Llama-3.1-405B (ToT): Drops from 90% (24Game) to 40% (CD[4]) at acc@5.
  • Qwen-2.5-72B (ToT): Drops from 83% (24Game) to 28% (CD[4]) at acc@5.
  • DeepSeek-V3 (ToT): Drops from 77% (24Game) to 20% (CD[4]) at acc@5.
  • Scalability Beyond Size 4: Every direct LLM method (IO, CoT, ToT) scored $<10\%$ accuracy across all models on input sizes between 5 and 10.
  • Reasoning Models (LRMs): Explicit-reasoning models outperformed standard base LLMs on small inputs (Qwen3 CoT scored 42.6% mean accuracy at size 4 vs. Qwen 2.5's 0.4%), but also deteriorated rapidly on larger sizes (scoring 4.6% at size 10). DeepSeek R1 frequently timed out, and GPT-OSS-120B routinely exceeded maximum token limits.
  • Error Breakdown: The vast majority of LLM errors stemmed from format violations, using numbers not currently available in the state, and failing to reach the target number.

Limitations and Future Work

  • Incomplete Theory for Phase Transitions: The authors empirical identify the secondary "hard-to-easy" phase transition around size 20, but leave a formal theoretical explanation for future work.
  • Compute Bottlenecks: ToT was only evaluated up to size 10 because generating branching thoughts requires hundreds of expensive API calls per problem instance.
  • Future Directions: Expanding Countdown by evaluating variations that permit using a subset of numbers, adding non-uniform operation costs to study optimal (cost-minimizing) planning, and exploring additional arithmetic operations.

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