acceptodds
Under review as a conference paper at ICLR 2027

Seemingly Simple Planning Problems are Computationally Challenging: The Countdown Game

Abstract

Current foundation models and agents struggle with long-term planning, yet existing benchmarks fail to adequately assess this limitation. 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. The game called Countdown, in which a player forms a target number from a list of inputs through arithmetic operations, has recently been adopted as a planning benchmark in several works, yet its computational properties and instance-space structure remain poorly understood. To address this gap, we provide the first systematic study of Countdown as a planning benchmark and propose a procedure for generating challenging instances. We argue this problem meets many of the key planning benchmark desiderata including intuitive natural language description, computationally challenging (NP-complete), and a rich instance space that avoids memorization. We provide a theoretical complexity analysis, show our instance generation outperforms public benchmarks, and evaluate existing LLM-based planners on these instances. Our results show that, unlike other domains like the 24 Game (a special case of Countdown), our proposed dynamic benchmark remains extremely challenging for existing LLM-based approaches. A key finding is the discovery of two phase transitions in problem difficulty as input size grows: a natural easy-to-hard transition, and a surprising hard-to-easy transition at larger sizes. The second transition means that naively scaling input size can overestimate a system’s planning capabilities rather than stress-test them, with important implications for how Countdown-based evaluations should be designed and interpreted.

Primary area:
datasets and benchmarks
Keywords:
Planning benchmark, Planning with Language Models

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_Ww5BOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

To examine whether models genuinely possess planning ability rather than rely on memorization of training data, the authors study the suitability of the Countdown arithmetic game as a planning benchmark and provide a computational complexity analysis. They then construct the CD dataset by sampling random arithmetic trajectories from a given set of input numbers and selecting the least frequently observed outcome as the target, and compare it with other datasets, including Reasoning-Gym (RG). Finally, they evaluate symbolic planning and LLM planning methods, observing two phase transitions in difficulty and finding that AutoToS and symbolic search methods perform best overall.

Critical strengths
  1. The authors highlight limitations of existing benchmarks in evaluating models and LLM agents on long-horizon, sequential, multi-step tasks. They show that solving larger instances does not necessarily indicate stronger planning ability, as those instances may simply be easier to solve.

  2. The paper provides a computational complexity analysis of Countdown to support its suitability as a planning benchmark, together with an instance-generation procedure that enables evaluation on fresh instances. It also reveals a non-monotonic relationship between input size and task difficulty, offering important insights for benchmark design and the interpretation of evaluation results.

Critical weaknesses
  1. The paper evaluates multiple models and prompting methods, but its error categories do not clearly distinguish misunderstanding the task rules, arithmetic errors, and difficulty finding the correct sequence of operations. It therefore remains unclear to what extent Countdown accuracy reflects planning ability rather than arithmetic proficiency and rule following.

  2. The authors attribute the hard-to-easy transition to the increased availability of intermediate zero values, but this explanation lacks direct experimental validation. Does the pattern persist when intermediate zero values are disallowed or the input-number range and instance-generation procedure are changed? The effects of instance distribution, search procedure, and resource limits remain unresolved, limiting the generality of the claimed difficulty pattern.

Questions for authors
  1. Could the models’ better performance on the 24 Game dataset simply reflect easier instances than those in CD, rather than prior exposure to the static dataset? To distinguish these explanations, could the authors compare performance on instances matched as closely as possible in input-number range, target value, and number of solutions?

  2. Could the error analysis more clearly distinguish arithmetic errors, failures to track which numbers remain available, and difficulty finding the correct sequence of operations?

3 comments
AuthorsOpenReview ↗

Helpful comments and suggestions

We thank the reviewer for the detailed comments and for the two concrete experiments suggested, both of which we ran and which sharpened our understanding of the domain. We hope that we can now alleviate your concerns and we welcome further discussion.

W2. "hard-to-easy transition":

We ran this experiment: we forbid the operations that let leftover numbers be absorbed, namely no operation may take 0 as an operand and no number may be multiplied or divided by 1 (equivalently, no intermediate 0 is created, since it could never be used afterwards). We ran the same blind DFS twice on the CD instances, under the same time and memory limits as in Figure 4: once with the standard rules and once with the restricted ones. Under the restricted rules, the hard-to-easy transition disappears:

Input size4-910-1213-1617-2021-3031-50
DFS, standard rules100%56.3%47.8%68.5%83.2%94.9%
DFS, no 0 and no multiplication/division by 199.0%40.0%6.0%2.5%0.7%0.2%

With the standard rules, DFS shows the same pattern as AutoToS in Figure 4: easy, then hard, then easy again. With the restricted rules, small instances are barely affected (99% at sizes 4-9; the 6 unsolved instances have no solution under the restricted rules, which we verified by exhaustive enumeration), but coverage keeps falling with size instead of recovering: 0.6% (21 of 3,400) at sizes 17-50, against 88.4% with the standard rules. Consistently, 2,992 of the 3,004 standard-rule solutions at sizes 17-50 pass through an intermediate 0. This confirms that intermediate 0 values are behind the second phase transition.

The mechanism, however, may be more subtle than our original explanation suggests: we counted the solutions exhaustively for sizes 4-7 and estimated them for sizes 8-20 using Knuth's estimator of search-tree size (Knuth, 1975), and according to these estimates the restriction removes only a moderate fraction of the solutions (the median fraction removed grows from about 10% at size 8 to about 40% at size 20), which may not be enough to explain the collapse of the search on its own. Understanding why the remaining solutions become so much harder to find deserves its own investigation. The revision will report this experiment in Section 8, and will revise our explanation accordingly. We use the restricted definition as a diagnostic, not as a proposed rule change; under the standard rules, our recommendation to evaluate on sizes 4-10 stands.

On generality: the pattern is not specific to one instance distribution or one search procedure. It appears on three datasets created by different generation procedures (our CD, Reasoning Gym, and Stream-of-Search; Figure 4), and with two different search procedures (blind DFS in AutoToS and heuristic GBFS in ENHSP; Figure 3), at around the same input sizes. Regarding resource limits: all runs use the same limits (30 minutes and 3.5 GB per run, Section 6), and the two planners fail for different reasons, ENHSP by running out of time and DFS by running out of memory (Section 6.1), yet both show the transition at around the same sizes, so it is not tied to one particular limit. The experiment above was run under the same limits, and only the restriction removed the recovery.

References

D. E. Knuth. Estimating the efficiency of backtrack programs. Mathematics of Computation, 29(129):121-136, 1975.

Q1. On better performance on the 24 Game dataset:

Thank you for this suggestion. We ran the comparison. We generated new size-4 instances matched to the 24 Game instances pair by pair: the same input-number range (1-13) and the same number of solutions, differing only in the target (never 24). We also evaluated Reasoning Gym instances of size 4, which are unseen and have many more solutions than the 24 Game. On the matched instances, the LLM planning methods perform as well as on the 24 Game, and on Reasoning Gym they perform better. Accuracy thus seems to be better correlated with the number of solutions of the instances than with their prior availability. The reviewer is right that the gap we reported is likely explained by instance difficulty, not by exposure during training. We will revise the corresponding claims in the contributions (Section 1), in Section 6.2 and in the conclusion accordingly. We believe this strengthens the case for our generation procedure: by selecting rarely reached targets, it produces instances with far fewer solutions than existing collections, and these instances are much harder for all tested LLM planning methods.

Q2. On error analysis:

Thank you, this is a useful suggestion. Two of the three are already separate categories: failures to track which numbers remain available are "Unknown Number Used", and difficulty finding the correct sequence of operations is "Not Target Number". Arithmetic errors were not a separate category in the submitted version, they were absorbed into Unknown Number Used and Not Target Number. We will add an "Arithmetic Error" category (a step whose stated result differs from the true value, allowing for rounding of fractions) and report it for IO, CoT and ToT. Re-running the analysis on our logs, arithmetic errors are rare compared to the other two. The table below gives, for each LLM and method, the number of errors of each category and its share of all errors (700 CD instances of sizes 4-10, 5 attempts each; an attempt can contain several errors):

All errorsArithmetic errorUnknown number usedNot target number
Qwen2.5 IO9,8977 (0.07%)3,658 (36.96%)791 (7.99%)
Qwen2.5 CoT6,75466 (0.98%)1,176 (17.41%)455 (6.74%)
Qwen2.5 ToT3,91382 (2.10%)274 (7.00%)3,358 (85.82%)
DeepSeek V3 IO8,15732 (0.39%)3,162 (38.76%)535 (6.56%)
DeepSeek V3 CoT8,38545 (0.54%)2,170 (25.88%)659 (7.86%)
DeepSeek V3 ToT5,0728 (0.16%)385 (7.59%)3,110 (61.32%)
Llama 405B IO5,3361 (0.02%)1,196 (22.41%)60 (1.12%)
Llama 405B CoT5,2425 (0.10%)761 (14.52%)121 (2.31%)
Llama 405B ToT4,004125 (3.12%)272 (6.79%)3,328 (83.12%)

Arithmetic errors account for at most 3.12% of all errors. Arithmetic can only be checked where the model states the result of a step: ToT does so for 96-100% of steps and CoT for 26-83%, while IO outputs mostly list operations without results (2-38% of steps), so the IO numbers are lower bounds. For ToT, Not Target Number is by far the largest category (61-86% of all errors): ToT executes steps correctly but fails to find a sequence that reaches the target, which is a search failure rather than an arithmetic or rule-following one. The remaining errors fall into the other categories of the paper (mostly Incorrect Format for IO and CoT). In the revision, Figure 6 will show the full breakdown over all categories as stacked bars, and the appendix will give it per input size.

As the discussion period ends soon, we would like to briefly follow up on our response. Following your suggestions, we ran both experiments you proposed: (1) Disallowing intermediate 0 values and multiplication or division by 1 removes the hard-to-easy phase transition (W2). (2) On size-4 instances matched to the 24 Game in input range and number of solutions, the LLM planning methods perform as well as on the 24 Game, so the gap we reported is likely explained by instance difficulty rather than exposure (Q1). We also added a separate Arithmetic Error category to the error analysis (Q2).

We have uploaded a revised version of the paper. It reports experiment (1) in Section 8 (Table 3), with the open question of why search collapses under the restricted rules discussed as future work in Section 9. It also removes the claims attributing the gap on the 24 Game to memorization (Section 1, Section 6.2 and the Conclusions). Section 7 has the new Arithmetic Error category, with the full breakdown in Figure 6, and Appendix B gives the error counts per input size.

Your suggestions and the resulting experiments have strengthened the paper: they sharpened our understanding of the hard-to-easy transition and clarified what drives the gap on the 24 Game. Since both suggested experiments were run and the revised paper reflects their outcomes, we would be grateful if you would consider updating your assessment. We are happy to clarify anything further in the remaining time.

Reviewer_Ryu8OpenReview ↗
Rating
4
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper provides the first systematic study of Countdown as a planning benchmark and proposes a procedure for generating challenging instances. Countdown is a sequential arithmetic puzzle where a player forms a target number from a list of input numbers, and it turns out to be a rigorous benchmark for evaluating the long-term planning capabilities of foundation models and LLM-based agents. The papers establishes Countdown's formal complexity, proposes a robust instance-generation procedure, evaluates several LLM-based planning methods, and analyzes their types of errors.

The paper has five main contributions:

  1. it proves that the Countdown problem is NP-complete.
  2. it proposes a scalable instance-generation procedure that minimizes the number of solutions, thus avoiding memorization risks.
  3. it formulates Countdown in PDDL, thus enabling the use of domain-independent numeric planners as baselines.
  4. it discovers a surprising dual phase transition phenomenon in problem difficulty as input size grows.
  5. it evaluates representative LLM-assisted planners, revealing poor scaling and clear performance drop compared to earlier evaluations in the 24 Game, which is a simplified version of Countdown

The empirical validation is performed across multiple datasets and instances / size. The authors test a variety of language models and symbolic solvers with strict time and memory bounds.

Critical strengths
  1. It establishes computational complexity by proving that Countdown is NP-complete. This places the LLM planning evaluation on firm theoretical foundations, replacing fuzzy or heuristic task domains with a rigorous benchmark.

  2. It identifies a dual-phase transition that prevents us from falsely overestimating an agent's planning capabilities by naively scaling input sizes.

Critical weaknesses
  1. Even though the authors' argument for using open weights models is valid, adding to the evaluation a few state of the art closed models would have shed additional light onto the strengths and weaknesses of today's most powerful LLMs (with a clear understanding that those results may not be reproducible)
  2. The authors hypothesize that the hard-to-easy phase transition at larger sizes is driven by the ease of generating intermediate zero values (which nullifies input usage constraints), they leave this explanation largely as an untested conjecture.
Questions for authors

Could you please expand the brief section 8 with a more in-depth discussion covering:

  1. whether the hard-to-easy phase transition is in any way biased by the current problem definition? For example,what happens if you do not allow the spurious use of 0 and 1 values?
  2. how could you extend the instance generator to domains that incorporate state-dependent resource costs or non-numeric symbolic constraints?
2 comments
AuthorsOpenReview ↗

Insightful comments and practical suggestion

We thank the reviewer for the insightful comments, and in particular for the suggestion to test the phase-transition hypothesis by disallowing 0 and 1, which helped us better understand the domain.

On closed models (W1):

The submission includes IO and CoT results for two frontier models, GPT 5.5 and Claude Sonnet 4.6 (Section 6.2.3, Table 2), with the reproducibility caveat you mention.

Q1. what happens if you do not allow the spurious use of 0 and 1 values?

We ran this test, which Reviewer Ww5B also suggested, and the second phase transition is indeed tied to intermediate 0 values and multiplication/division by 1: when they are disallowed, it disappears, while small instances are barely affected. Interestingly, according to our estimates using Knuth's estimator of search-tree size (Knuth, 1975), the restriction removes only a moderate fraction of the solutions, so the reason the search collapses may be more subtle than a reduction in the number of solutions and deserves its own investigation. Please see our answer to Reviewer Ww5B (W2) for the detailed description of the experiment outcome. The revision will report your suggested experiment in Section 8.

Q2. On extending the instance generator:

The generation procedure extends naturally to non-uniform operator costs and to applicability or trajectory constraints. The modifications would touch three places: the action applicability definition, the rejection of invalid trajectories, and the statistics collected for generated targets (which, with costs, would also record the cost of reaching each target). The choice of target will then depend not solely on its frequency, but also account for the observed total cost. The restricted definition from Q1 (no intermediate 0, no multiplication or division by 1) is an example of such an applicability constraint: generating instances for it only requires sampling the random trajectories with the restricted operations, which guarantees that every generated instance is solvable under the new rules. We will add this discussion to Section 9.

References

D. E. Knuth. Estimating the efficiency of backtrack programs. Mathematics of Computation, 29(129):121–136, 1975.

Reviewer_Ryu8OpenReview ↗

Thank you for your comments. After carefully reading all reviews and rebuttals, I maintain may original rating.

Thank you for your comments. After carefully reading all reviews and rebuttals, I maintain may original rating.

Reviewer_k8ZVOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
3
Soundness
1
Read review
Paper summary

This paper shows that the countdown game can be formulated as a planning problem and introduces a simple method for generating data. Using this, the authors evaluate various types of models and also conduct an error analysis.

Critical strengths

The authors show that the countdown game can be viewed as a simple planning problem and introduce straightforward yet effective methods for easily generating data points. The proposed planning benchmark desiderata are also useful, as other researchers will find it useful assessing and designing planning tasks for their own benchmarks.

Critical weaknesses
  • I am not fully convinced of the significance of performing well on this particular task. Most real-world planning tasks are quite different from the countdown game. For this paper to have broader implications, I think the authors should show either that the findings transfer to other planning tasks commonly used in real-world use cases, or that the countdown game can serve as a useful training signal that improves general planning capabilities.

  • As it stands, the results on this alone do not provide much insight into LLMs' general planning capabilities or have clear implications for real-world planning applications.

  • Furthermore, error analysis is less informative. Most of the identified error types seem to reflect general instruction-following issues, while the evaluation only includes open models that may have relatively weaker instruction-following capabilities. It is therefore unclear whether these errors are specific to planning or reflect limitations in instruction following of the models.

Questions for authors

See Critical Weaknesses

3 comments

We thank the reviewer for their comments.

On "real-world planning tasks" (W1):

Countdown intentionally abstracts away real-world complexity to isolate planning from perception, language understanding, domain knowledge, and other confounding capabilities. As such, we argue that the focus on a problem whose primary challenge is planning is a strength as opposed to a weakness.

On "LLMs' general planning capabilities" (W2):

The paper's contribution is not to infer general planning capability from Countdown, but to show why such inferences can be hard or even invalid. For example, the hard-to-easy phase transition means that strong results on larger instances need not reflect stronger planning. This is one of our main messages, in addition to establishing the properties of the dataset itself.

On "error analysis is less informative" (W3):

First, our evaluation is not limited to open models: Table 2 also reports results for two frontier models, Claude Sonnet 4.6 and GPT 5.5. Second, formatting errors are indeed instruction-following failures, and we report them as a separate category for that reason. The other dominant categories, using a number that is no longer available and reaching a number other than the target, are failures of action applicability and goal achievement, which are the defining elements of planning. Arithmetic errors, by contrast, are rare: they account for at most 3.12% of all errors (see our response to Reviewer Ww5B, Q2). The purpose of the analysis is to characterize how generated plans fail, not to claim that every error is uniquely attributable to planning.

On Informativeness and soundness scores:

The informativeness and soundness scores are difficult to reconcile with the review. The paper establishes previously unknown computational complexity and phase-transition results, including the counterintuitive finding that larger instances can become easier and thereby distort conclusions about planning ability. Moreover, the review identifies no flaw in the theoretical results, methodology, experiments, or analysis. Its concerns address scope and significance, not soundness.

Thank you for the response! LLMs are highly sensitive to subtle changes in tasks and environments, and even small variations can lead to substantially different behaviors. So, even if the current task is framed as a planning task and the paper provides a behavioral analysis of LLMs on this specific task, I'm not convinced yet, what these actually mean or what implications they have for the evaluation or development of LLMs. It'd be helpful for authors to share how to better articulate the significance of this work.

Thank you for your reply. Your comment appears to focus on the significance and implications of the work; we understand that the technical results themselves are not in dispute. If that understanding is incorrect, we would appreciate clarification on any remaining technical concern.

We believe four points are important here. First, Countdown is not merely framed as planning: it is a numeric planning domain with explicitly defined states, actions, transitions, initial states, goals, and sequential plans (Section 4), with a PDDL formulation solved by a domain-independent numeric planner (Section 6.1). Section 2 discusses how it satisfies the standard desiderata of a planning benchmark.

Second, Countdown and its special case, the 24 Game, are already used as planning benchmarks by ToT, Stream-of-Search, Reasoning Gym, and subsequent work, as discussed in the Introduction. Yet, despite this growing use, very little was previously understood about the domain's computational properties and instance-space structure.

Third, we show that this lack of understanding can directly distort LLM evaluation: because Countdown's difficulty is non-monotonic in instance size, naively increasing instance size can make the task easier and lead to overestimating planning capabilities.

Fourth, the sensitivity of LLMs that you point out strengthens, rather than weakens, this motivation: if behavior changes with seemingly small variations of a task, then results on a benchmark can only be interpreted once it is known which properties of its instances drive difficulty. Our analysis identifies such properties. Instance size is not a valid proxy for difficulty, and the experiment suggested by Reviewer Ww5B shows that the accuracy of the LLM planning methods follows the number of solutions of the instances. Concretely, this implies that Countdown evaluations should report results in the hard range of input sizes or by number of solutions, and should use instances generated with controlled difficulty rather than static collections.

Thus, our contribution is not to claim that one domain characterizes planning in its entirety. It is to provide the scientific understanding required to design and correctly interpret evaluations on a planning domain already used by the community.

We sincerely believe that the systematic study of an actively used but poorly understood planning benchmark is, in itself, a meaningful and worthwhile research objective. If you agree, we respectfully invite you to reconsider your original assessment.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Rebuttal Revision Updated

The additional experiments, analyses, and clarifications described in this response have been incorporated into the rebuttal revision. All corresponding additions and modifications in the revised manuscript are highlighted in blue for ease of review. We thank the reviewers for their suggestions, which helped improve both the analysis and presentation of the paper.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.