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:
- Fuzzy tasks (e.g., travel planning) are intuitive but lack rigorous formalization and sound validators.
- 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.
- 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