# Seemingly Simple Planning Problems are Computationally Challenging: The Countdown Game

arXiv: https://arxiv.org/abs/2508.02900 · HTML: https://mlsanity.com/paper/2508.02900/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 28 references that are in the map.
- First posted on arXiv 4 Aug 2025.

## Builds on (most cited first, 13 of 13)

- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [TravelPlanner: A Benchmark for Real-World Planning with Language Agents](https://mlsanity.com/paper/2402.01622/) (2024)
- [PlanBench: An Extensible Benchmark for Evaluating Large Language Models on Planning and Reasoning about Change](https://mlsanity.com/paper/2206.10498/) (2022)
- [Stream of Search (SoS): Learning to Search in Language](https://mlsanity.com/paper/2404.03683/) (2024)
- [REASONING GYM: Reasoning Environments for Reinforcement Learning with Verifiable Rewards](https://mlsanity.com/paper/2505.24760/) (2025)
- [NATURAL PLAN: Benchmarking LLMs on Natural Language Planning](https://mlsanity.com/paper/2406.04520/) (2024)
- [ACPBench: Reasoning about Action, Change, and Planning](https://mlsanity.com/paper/2410.05669/) (2024)
- [Thought of Search: Planning with Language Models Through The Lens of Efficiency](https://mlsanity.com/paper/2404.11833/) (2024)
- [Automating the Generation of Prompts for LLM-based Action Choice in PDDL Planning](https://mlsanity.com/paper/2311.09830/) (2023)
- [ACPBench Hard: Unrestrained Reasoning about Action, Change, and Planning](https://mlsanity.com/paper/2503.24378/) (2025)
- [Automating Thought of Search: A Journey Towards Soundness and Completeness](https://mlsanity.com/paper/2408.11326/) (2024)

## Built on by (most cited first, 9 of 9)

- [RAGEN-2: Reasoning Collapse in Agentic RL](https://mlsanity.com/paper/2604.06268/) (2026)
- [BeyondBench: Contamination-Resistant Evaluation of Reasoning in Language Models](https://mlsanity.com/paper/2509.24210/) (2025)
- [Mechanistically Eliciting Latent Behaviors in Language Models](https://mlsanity.com/paper/2606.29604/) (2026)
- [Mind the Gap Between Spatial Reasoning and Acting! Step-by-Step Evaluation of Agents With Spatial-Gym](https://mlsanity.com/paper/2604.09338/) (2026)
- [Planning in the LLM Era: Building for Reliability and Efficiency](https://mlsanity.com/paper/2605.21902/) (2026)
- [The Confidence Shortcut: A Reasoning Failure Mode of Masked Diffusion Models](https://mlsanity.com/paper/2605.29123/) (2026)
- [Beyond Memorization: Testing LLM Reasoning on Unseen Theory of Computation Tasks](https://mlsanity.com/paper/2601.13392/) (2026)
- [Tropical Reinforcement Learning](https://mlsanity.com/paper/2610.02478/) (2026)
- [Dynamic Minimax Regret Optimization for Robust LLM Post-Training](https://mlsanity.com/paper/2610.06329/) (2026)

## Abstract (arXiv)

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.