TLDR: This research paper introduces the Countdown game as a new, challenging benchmark for evaluating the planning abilities of AI models, especially large language models (LLMs). It proves Countdown is NP-complete and proposes a new instance generation method to avoid data memorization. Experiments show that while a method called AutoToS performs well, other popular LLM planning techniques like Chain of Thought and Tree of Thoughts struggle significantly on these new, unseen problems, suggesting previous high performance on benchmarks like the 24 Game might have been due to memorization. The paper also identifies surprising phase transitions in problem difficulty.
The ability of artificial intelligence, particularly large language models (LLMs), to formulate long-term plans remains a significant hurdle in developing truly autonomous agents. Despite this, current benchmarks designed to measure these planning capabilities are often inadequate. Some focus on loosely defined tasks like travel planning, which are difficult to formalize and rigorously evaluate. Others rely on problems from international planning competitions, originally designed to test traditional automated planners, and may not be suitable for assessing the unique strengths and weaknesses of LLMs.
A popular benchmark, the ’24 Game,’ while simple to describe, is limited in scope and raises concerns about data memorization by LLMs, as many instances are scraped from the internet and might have been part of the models’ training data.
Introducing the Countdown Game as a New Benchmark
To address these shortcomings, researchers propose a new planning benchmark centered around the game called Countdown. In Countdown, players are given a list of input numbers and must use arithmetic operations (addition, subtraction, multiplication, division) to reach a specific target number. This game is a direct generalization of the 24 Game, making it a more versatile and challenging testbed.
The Countdown game meets several key criteria for an ideal planning benchmark:
- It allows for an intuitive, natural language description for each problem instance.
- It is computationally challenging, proven to be NP-complete, meaning the difficulty grows rapidly with problem size.
- The instance space is rich and dynamic, significantly reducing concerns about models simply memorizing solutions.
Key Findings and Contributions
The research paper, titled “Seemingly Simple Planning Problems are Computationally Challenging: The Countdown Game,” delves deep into the nature and complexity of Countdown. The authors, Michael Katz, Harsha Kokel, and Sarath Sreedharan, highlight several crucial contributions:
- They formally establish that the Countdown problem is NP-complete, providing a rigorous theoretical analysis of its computational complexity.
- They introduce a novel procedure for generating challenging Countdown problem instances. This method aims to create problems with fewer possible solutions, making them inherently harder to solve compared to instances generated by other approaches.
- They developed a formulation of Countdown in PDDL (Planning Domain Definition Language), enabling the use of existing numeric planners as a baseline for comparison.
- They conducted an extensive experimental evaluation of various LLM-assisted planning methods on their newly generated dataset.
Surprising Discoveries in Problem Difficulty
One of the most unexpected findings was the observation of two ‘phase transitions’ in the Countdown game’s difficulty as the input size increases. The first transition is from easy to hard instances, which is intuitive. However, a second, surprising transition occurs from hard back to easy instances. This non-monotonic performance was consistent across different datasets, suggesting it’s an inherent characteristic of the Countdown game. This phenomenon implies that testing models on a range of input sizes, particularly between 4 and 10, is sufficient to capture both easy and hard instances.
LLMs Struggle with Unseen Planning Problems
The study revealed a significant performance gap between traditional symbolic planners and most LLM-based planning methods. While AutoToS, a method that uses LLMs to generate a symbolic solver, performed remarkably well, other popular LLM planning approaches like Input/Output (IO), Chain of Thought (CoT), and Tree of Thoughts (ToT) struggled considerably. Their accuracy on the Countdown dataset, especially for instances larger than size 4, was often below 10%.
A critical comparison was made between the performance on the 24 Game dataset (often scraped from the internet) and the newly generated Countdown instances of the same size. The dramatic drop in accuracy for LLMs when moving to the unseen Countdown instances strongly suggests that the high performance reported on the 24 Game might have been due to data memorization rather than genuine planning capabilities. This underscores the importance of dynamic, non-memorizable benchmarks like the one proposed.
The researchers also performed an analysis of the errors made by LLM-based planners. The most common errors included incorrect output formatting, attempting to use numbers not available at a given step, and failing to reach the target number.
Also Read:
- AI’s Next Leap in Problem Solving: Crafting Diverse Heuristic Sets
- Streamlining LLM Reasoning: Compressing Thought Chains with Step Entropy
The Future of AI Planning Benchmarks
In conclusion, the Countdown game is presented as a robust and valuable benchmark for evaluating the planning abilities of AI models and agents. Its intuitive description, precision, and computational challenge make it an ideal domain for this purpose. The findings highlight that while methods like AutoToS show promise, many existing LLM-based planning approaches are currently inadequate for solving previously unseen planning problems. This research paves the way for future work, including exploring extensions to Countdown with additional operations or different cost structures, further challenging the capabilities of advanced AI systems. You can read the full research paper here.
