ACPBench Hard: Unrestrained Reasoning about Action, Change, and Planning
Authors: Harsha Kokel
Michael Katz
Kavitha Srinivas
Shirin Sohrabi
Venue: ICLR 2026 Poster (2026)
Keywords: Planning
Dataset and Benchmark
Large Language Models
Primary area: datasets and benchmarks
TL;DR: A dataset of generative, open‑ended reasoning tasks that underlie reliable planning.

Abstract: We introduce ACPBench Hard, a dataset of generative, open-ended questions which LLM models needs to answer in order to plan. Models that perform well on these tasks could in principle be integrated into a planner or be used directly as a policy. We discuss the complexity of these tasks as well as the complexity of validating the correctness of their answers and present validation algorithms for each task. Equipped with these validators, we test the performance of a variety of models on our tasks and find that for most of these tasks, the performance of even the largest models is still subpar.  The models do not possess even the most basic capability of identifying which actions can be performed in a given state.   No model outperforms any other on our proposed tasks and, with a few exceptions, all tested language models score below 65\%, indicating that even the current frontier language models as well as so-called reasoning models have a long way to go before they can reliably reason about planning.

ACPBench Hard collection is publicly available, see [https://ibm.github.io/ACPBench](https://ibm.github.io/ACPBench).

ACPBENCH HARD: ABOUT ACTION, CHANGE, AND PLANNING
UNRESTRAINED REASONING
Harsha Kokel,
Michael Katz, Kavitha Srinivas & Shirin Sohrabi
IBM Research
IBM Thomas J. Watson Research Center
San Jose, California 95141, USA Ha aarahaa.o Kokel@ hmm. com
Yorktown Heights, New York 10598, USA [Mi chael Katzl, Kavith Sr Srinivas (immmmm...... com, s sschrablus. 1.m. com
ABSTRACT
We introduce ACPBench Hard, dataset of generative, open-ended questions which LLM models needs to answer in order to plan. Models that perform well these tasks could in principle be integrated into a planner be used directly as policy. We discuss the complexity of these tasks as well as the complexity of validating the correctness of their answers and present validation algorithms for each task. Equipped with these validators, we test the performance of a variety of models on our tasks and find that for most of these tasks, the performance of even the largest models is still subpar. The models do not possess even the most basic capability of identifying which actions can be performed a given state. No model outperforms any other
proposed tasks and, with a few exceptions, all tested language models score below 65%, indicating that even the current fron- tier language models as well as so-called reasoning models have long way go before they can reliably reason about planning.
INTRODUCTION
The ability to reason and plan in large language models (LLMs), is a major focus in the field. For reasoning, the majority of work focuses on the mathematical reasoning (Cobbe et al., 2021 and logical inference (Saparov & He 2023). For planning, most work focused on the ability to produce validate a plan (Valmeekam al.) 2023a Stein et al., 2026).. The downside of focusing the end-to-end planning datasets is the inability to pinpoint the reason for a black-box planner, such as an LLM-based one, to not be able to produce a solution.
To tackle this gap, ACPBench (Kokel et al., 2025) introduced a benchmark for testing the reasoning abilities about action, change, and planning, separating the planning process into the atomic reason- ing tasks performed by planners. Tasks in these benchmarks are boolean or have multiple choice. However, in real applications planners do not typically have shortlisted options. Planners need to generate the actions from significantly larger action space. For instance, the applicability task in ACPBench either asks about applicability of given action in the boolean case or chooses an ap- plicable action among 4 variants. Even if we make the assumption that the model can answer such questions with high precision, it is not clear how this capability can efficiently exploited for the task of generating all applicable actions in given state.
In this work, we create a generative version of ACPBench to alleviate these limitations. We devise open-ended, generative versions of questions for the same tasks, and add new challenging task of finding an action that takes us closer to the goal, a task that corresponds to the ability to perform optimal planning (Bylander 1994). For each of these tasks, we introduce evaluator, which scores a possible answer to the onen-ended questions. We generate an evaluation set of questions based on wide collection of 13 Planning Domain Definition Language (PDDL) (McDermott) 2000 domains from ACPBench, which we call ACPBench Hard. The core idea is to evaluate the LLMs' ability produce reliable components for automated planners, as LLMs that perform well on these tasks could be integrated into planner or be used directly as policy (Kambhampati et al. 2024).
ACPBeench Hard collection is publicly available, httph:t////// hmm. gi thub. o A/ACCRench

---

For all tasks, we discuss their computational complexity, well as the complexity of validating their solutions. We devise validators for each task, based on the symbolic description of the questions. With the help of these validators, we test the performance of collection of modern LLMs of various sizes on ACPBench Hard. We find that the performance of language models, even the largest ones, is still insufficient to be reliably used in planners, see Figure T We observe that there is no single model that outperforms all other models on all tasks of the ACPBench Hard dataset. Further, on half of the tasks, namely "reachability" (reach), "action reachability" (areach), "landmarks" (land), and "applicability" (app), all tested language models exhibit a very low accuracy. All tested models score below 65% on most tasks, indicating that even the current frontier language models have a long way to go before they can reliably reason about planning. Further, even the so-called reasoning models ol perform poorly on half of these tasks. The ol -preview model achieves 89% on the "progression" (prog) task and 80% on the "next action" (nexta) task, with the rest of the results being 66% and below, and the smaller o ol-mini model outperforms it only on the "plan validation" (val) task with 78% accuracy. The much higher computational effort of the reasoning models compared to the language models do not seem to justify the somewhat moderate increase in accuracy.
just
BACKGROUND
land
areach
We consider planning tasks II (F. so, s.) in the STRIPS formalism (Bylander 1994). In such task, F set of Boolean propositions. Each subset 8 S F is called state, and S = 2 is the state space of II. The state so is the initial state of II. The goal 8, C F is a set of propositions, where state is a goal state if 8, 8. The set A is finite set of actions. Each action a E A has an associated set of preconditions pre(a) S F, add effects add(a) S F and delete effects del(a) F.
0.6 6
0.4 0.4
nexta
app
prog
val
reach
The semantics of STRIPS planning as follows. An ac- tion a is applicable in the state if pre(a) S s. Applying A
Mixtral Bx22B
Liama 3.1 70B
GPT-4o mini
DeepScck V3
in s results in the state s|a]] == (s) sequence of actions x (a), (a....., a.) is applicable in there exists a sequence of states 8 81...., 8441 such
Llama 3.1 405B
GPT-4o
Figure 1: Task-wise accuracy of large size language models.
that for each 1 < i < state 8; and applying results in the state 8,41- If it ex- ists, such sequence is uniquely defined, and its end state sn is denoted by s s[m] An applicable action sequence is a plan for if a a[T] is a goal state. A plan for s with minimal length is called optimal. The perfect heuristic for s, denoted by h² (s), is the cost of optimal plan for The objective of (optimal) planning is to find an (optimal) plan for the state sp.
have a, is applicable in the
RELATED WORK
The most relevant to our work is the ACPBench dataset (Kokel et al. 2025), which we build upon. It features 7 core reasoning tasks about planning. ACPBench does not capture the decisions that the automated planners need to make, as these decisions are generative in their nature. In this work, therefore, we present the generative form of these tasks, requiring LLM to produce precisely the answers that automated planners produce and consume. Additionally, we present a new task, not considered by previous work, requiring to produce an action that takes us closer to the goal.
Other notable work in similar direction includes Textual Reasoning about Actions and Change (TRAC) (He et al. 2023), featuring tasks: projection, execution, planning, and goal recognition, as well as PlanBench (Valmeekam et al., (023b), with 8 planning tasks including plan generation, reasoning about plan execution, and plan verification. Both benchmarks focus on a small number of planning domains (mostly BlocksWorld and variants). Both use templates to generate natural language text; similar to ours. AutoPlanBench (Stein et al. 2025) alleviates the dependence on tem- plates, leveraging LLMs to generate these natural language template and hence were able to scale up the dataset to 12 domains. While scaling the number of domains, they limit their focus on planning task including plan and next-action generation.
2

---

Another notable dataset is ActionReussoinggenndd (Handa et al. 2025). tracking, state tracking, action executability, effects of actions, numerical RAC, and composite ques- tions. These tasks reason about action sequences and hence two of the tasks overlap with three of the tasks we consider: Specifically, action executability deals with questions that fall under applicability and validation tasks in our case. On one hand, this creates complicated reasoning question, on the other, it makes it harder to pinpoint the source of an error. The effiects-of-actionn task is somewhat similar our progression task, applied repetitively. Further, ActionReasoningeenct uses large- language model for evaluation of the generative questions, which is not quite robust. We develop dedicated symbolic validators to evaluate each of the generative task introduced. Table 4 in the Appendix compares and contrasts ACPBench Hard with related planning benchmarks. Research on planning abilities of agents (Liu et al. 2022 Ma et al. (024) also relevant. our experiments, we focus on the planning abilities of individual models instead of agents. However, the "next action" prediction task does takes us in direction of agents.
featuring six tasks: fluent
4 UNDERLYING REASONING TASKS
We focus on the core reasoning capabilities that symbolic planners routinely deploy when decid- ing how actions interact with states and how plans progress toward goals. These capabilities span action-level, state-level and plan-level reasoning. The tasks range from identifying what actions possible right now, to anticipating future possibilities, to validating multi-step plans. Each task probes a different facet of an agent's ability to reason about actions, state transitions, and goal achievement.
At the action level, applicability tests whether a model identifies all actions that are valid and appli- cable in current state. Failure in this reasoning often surface as LLMs hallucinating non-existent tools/parameters (Lin et al. 2025). pick objects that are not present, move through blocked
spaces (Raman et al. 2024).
Progression checks all the state updates are predicted for an applicable action; typical errors in this reasoning include missing/deleting the wrong facts, tracking failures like forgetting IDs, assuming deleted entities persist, or ignoring side effects (c.f. tracking objects task in Suzgun et al. (2023)). ).
At state-level, Reachability evaluates the ability to determine which facts could eventually become true and which facts can never become true along any valid trajectory from the current state; failures arise when models attempt to achieve structurally impossible facts or invent intermediate states.
Action reachability evaluates the ability to determine which actions could eventually become appli- cable and which actions can never become applicable in any state reachable from the current state; failures occur when models propose actions whose preconditions can never co-occur, leading them to explore permanently unreachable or irrelevant branches, or supplying invalid arguments to actions that make it inapplicable in any reachable state (Xu et al. 2023
At the plan level, validation checks whether plan is executable and identifies the earliest inapplica- ble action; failure in this reasoning leads to the model missing unmet preconditions and erroneously deeming infeasible steps as valid.
Justification tests whether a plan can be simplified by removing redundant actions; failure in this reasoning leads to an unnecessarily elaborate plan with redundant steps or an overly compressed plan that removes necessary actions and breaks plan validity.
Landmarks require identifying facts that must inevitably hold along every valid solution path; fail- ure in this task can manifest model skipping mandatory subgoals or collapsing multi-step depen- dencies required for achieving the goal.
Finally, next-action selection evaluates whether the model can chose an action that meaningfully reduces goal distance; errors include drifting toward irrelevant or harmful actions, or selecting steps that do not improve the optimal cost.
5 DATASET CONSTRUCTION
Building upon ACPBench (okeel et al. 2025), we keep the same 13 planning domains and create generative dataset. For each task, we describe the data stored in order to enable speed up the
3

---

Context:
There are sevaral ci:les, each containing sevezal locations, sone of which are airports. There sirplanes,
fly becaven aisporis. The goal is get sone packacus from various locations to various nea locations. There are trucks and i atzplane, as well as 4 packages. There are 4 lecations accoss 2 cities. The locazions are in cilies follows: 11 1 and 11 0 are in el; 10 and 10 0 are in cb. Cuzsenily, pž, LI, pl, p3, 40, and 11-0, to at 10-1. The available propositions (ir Tob51 tobj21 Pobj1 in 7ob5?.
Lrucks, shich
withir single city,
Jab1 21oc) 2ob; is Noo
Inputa: Break down the outcones of parforning the action "Load dbject p3 into tzuck =I at location 11-0" proposit iors
neget ive effects. Positive offects falsw the curzent state but will becone Loue aftes per forning Lhe act iun. Negat effwela are the propositions that aze trve in the cuerent state and will becone false after parformina the action.
into two lists, positive effects
Figure 2: Example of question for the progression task in ACPBench Hard. (Also see examples in Appendix.)
evaluation of the correctness of a potential answer. Often, the PDDL planning task IT = (F, A, 8, 8+) is needed for evaluation, and therefore store it per question, with the current state 8 as the initial state. Plans, whenever needed, are computed with a classical planner. We first attempt to run a top-quality planner (Katz& & Lee. 2023b), producing plans of best possible quality, and use a diverse planner (Katz & Sohrabi| (0200 as a backup mechanism if no top quality plans were found. The We use template- based approach to high-level construction workflow is illustrated in the Figure 7 convert the PDDI. to NI..
1. Applicability (App) The first task deals with identifying which actions are applicable in a state. For an action to be applicable, its preconditions must hold in the state. Given a state 8 and the set of actions A, the subset of applicable actions would be A(s) = {a E A pre(a) S s). easily computable by iterating over the actions. The complexity of such iterative algorithm is O(FFIIA), since |F] is a theoretical upper bound on the precondition size. In practice, planning problems typically have small preconditions size. Thus, can create generative question by simply asking the model to produce all applicable actions in a given state. For practical reasons, impose bound on the number of applicable actions in a state, generating questions only in cases when [A()) is under that bound. We can keep all applicable actions names in the dataset for validating the answer. The number of applicable actions for all instances is < 10, except for Swap and Alfword domains (ref. Table 5 in the Appendix).
2. Progression (Prog) The next task evaluates LLMs ability understand how the world state changes by action application. Performing an action changes the state in the following manner: The delete effects will no longer hold and the add effects will hold. Everything else remains unchanged. Given a state and an action the next state is L (s \ del(a)) U add(a). The complexity of the straightforward computation is O(F)) worst case, but in practice the add and delete effects of planning problems are typically small. We construct a single generative question, asking what propositions are false in the current state but will become true after performing the action and asking which ones are true and become false. The first set is & \ and the second one is t. We maintain both of these sets in the answers. Figure shows an example of a progression question.
3. Reachability (Reach) The reachability task evaluates if specific fact can eventually become true by taking (possibly multiple consecutive) actions in the given state. This is a multi-step reasoning task that can help avoid exploring unfeasible options. The generative version of this question is quite simple: what proposition can never hold in any potentially reachable state. If no such propositions PSPACE-hard
exist, we instruct to reply None. Reachability 1994) for partial states, so we only focus on reachability of a specific fact. We can generate some unreachable facts by either finding groundings of static predicates (unchanged by any action) that do not hold in the given state, or by (under haproxiiappo the reachability with poly-time computable delete-relaxed reachability (Hoffmann & Nebel, 2001). For practical reasons, we keep a subset of generated unreachable facts, N, for speeding up answer validation. We generate question only in states where we either know at least one unreachable fact or we know that all facts are reachable. In case of doubt, we skip generating questions for that state.
answer in general (Bylander)
4. Action Reachability (AReach) The action reachability task is closely related to the (atom) reach- ability, checking whether there is reachable state where the action is applicable. Computationally, this problem is PSPACE-hard, for the same reason as (atom) reachability. The generative version of the question is: what action can never become applicable, in any state reachable from the current state? Here as well, we generate question only in states where we either know at least one unreach- able action or know that all actions are reachable. In case of doubt, we skip the state. For answer
4

---

validation, as in the previous case, we keep set of example unreachable actions U. Set U is empty when all actions are reachable.
5. Validation (Val) The validation task aims checking whether the specified sequence of actions t is a plan. In other words, whether π is valid, applicable, and successfully achieves the intended goal from the given state The generative version of this question aims at identifying where the plan fails. In other words, we ask to identify the first inapplicable action in a given sequence of actions. To generate such sequence, we start with a valid plan and randomly choose an action to replace with an inapplicable one. For validation purposes, we keep the index of such action.
6. Justification (Just) Action justification (Fink & Yang 1992 Salerno al. 2023) deals with the question of whether a given plan can be simplified by removing some actions. The generative version of the justification task question asks to simplify the plan by removing one or two consecutive actions and to produce the resulting simplified plan. To produce such a sequence, we start with plan for the initial state. We check whether the plan can be simplified by removing a single or two consecutive actions. If not, we try to extend the plan by adding such an action resulting sequence a plan. For answer validation, we keep the action or pair of actions that can be removed, together with the appearance number, for actions that appear more than once on the plan.
pair of actions, keeping the
Landmarks (Land) Landmarks task tests L.M''s s ability to identify subgoals that are necessary to achieve the goal. In the planning literature such subgoals are often called landmarks (Porteous) ctt al. (001T. Landmarks are facts that must become true sometime along every plan. While check-
ing whether proposition is landmark is PSPACE-hard (Porteous al. 2001), there several
methods that can find a subset of landmarks (Keyder et al. 2010 Hoffmann et al. 2004 Richter
al. 2008 Zhu & Givan 2003). We use the so-called RHW method (Richter al. 2008). Further,
negative evidence can be obtained from a collection of plans a proposition that does not appear on
a plan is not a landmark. We keep the sets of facts that are known be landmarks and of facts that are known to be non-landmart for speeding up answer validation.
8. Next Action (NextA) An additional task that does not appear in ACPBench is the next action task. This generative question asks what is the next action that takes us towards the goal. This task closely related to optimal planning, since optimal plans can be produced by iteratively obtaining such actions. While even non-optimal planning is PSPACE- hard (Bylander] 1994). modern planners can often quickly find collections of optimal plans (Katz et al. 2020; Katz & Lee 2023a). Clearly, the first actions of these plans would be correct answers. Further, the cost of these optimal plans can be used to check other applicable actions in the state, by producing an optimal plan for the states obtained by applying these actions in the question state. We keep the sets of actions that correct answers and of actions that are known to not take us closer to the goal for speeding up answer validation. Further, we store the optimal cost h (s) of achieving the goal from the current state.
ANSWER EVALUATION
Evaluating answers to boolean or multiple-choice questions simply amounts to looking up the cor- rect answer and comparing. Evaluating open-ended answers, on the other hand, might not be as easy. This is due to the fact that sometimes, there is not one single correct answer that can be stored with the question. Looking at the tasks at hand, while in some cases we can store the complete correct answer, in other we must resort to performing some computation in order to evaluate whether the returned answer is correct. In what follows, we describe how the answer evaluated for each task.
1. Applicability (App) In this task, we store all applicable action names per question. The answer evaluation therefore amounts to simple comparison between the given answer and the correct one. Since we ask for all applicable actions, we chose to assign score 1 if the set of all actions in the answer equals to the set of all applicable actions. Otherwise, we assign O. The complexity of validating the answer is therefore ((1) if we impose constant threshold the number of applicable actions when the question is created, otherwise it is O([A)).
2. Progression (Prog) Here, we store both correct sets of propositions (t' \ and f) per question. An answer validation amounts to a simple comparison between the given answer and the correct one. Since we test the ability to produce all action effects, score if both all positive and all negative effects were correctly identified. Otherwise, we give the score O. The complexity of validating the answer is therefore O(FI))
5

---

3. Reachability (Reach) The set of unreachable facts N being empty is indication that there no unreachable facts. Hence, if the answer P is None, we assign score of when N = 0; otherwise, the score is O. If the answer P is not None and P E N. we assign the score of 1. If P is not None but the set N is empty, the score is O. In the remaining case, where P is not part of N, we need to solve a planning task II' = (F, A, So: { (P)), where the goal is to achieve the atom P and the rest as in the planning task in the question. We can use any off-the-shelf planner to generate a plan for this task. If plan exists, we score the answer otherwise 1. Therefore, the evaluation problem in this case is PSPACE--omplete.
4. Action Reachability (AReach) As in the previous case, when the set of unreachable actions U is empty. all actions are reachable. Hence, if the answer is None, we assign score of when U = 0; otherwise the score O. For an action a as answer, if U = then the score O. If E U. the score is 1. In the remaining case, where U * 0 and a É U, we construct planning task IT' = (F, A, so: pre(a)) with the goal being the preconditions of the action a, and the rest as the planning tasks in the question. We run planner this task, checking if a plan exists. If yes, we score the answer O, otherwise 1. The evaluation is, therefore, PSPACE-complete in this case as well.
5. Validation (Val) In this case, we only need to compare the index in the answer to the correct index of the first inapplicable action. We give a 0/1 score based on that comparison. The complexity of validating the answer is therefore ((1).
6. Justification (Just) To check whether the returned sequence is correct, we slightly relaxed the constraint in the question. We check whether it is proper subsequence of the provided plan and whether it is a plan. If both are true, we give a score of 1, otherwise, we score the answer O. The complexity of validating the answer therefore (( [F)) for the plan n.
7. Landmarks (Land) Invalid propositions are scored 0. A proposition p E 80 U 8+ is a trivial landmark and is also scored 0. Given a valid proposition p E F \ (so U 8+), if is known not to be a landmark (e.g., there cxists a plan that does not traverse any state in which p holds), we assign it score of 0. Otherwise, in order check if p is a non-trivial landmark, we construct planning task 11' = (F". A', sy, s'{) as follows. The set of propositions is extended with a proposition Poch that intended to indicate that p was never achieved along a sequence of actions. F' F U {Pnach) Thus, for each action E A such that p E add(a), we construct a new action with extended delete effect to include Prach. Formally, for an action a, is defined as follows. pre(a') = pre(u), (a)) add(a), and del(a')
del(a) U [Pnach) } if E add(a). otherwise del(a') = del( The extended action set is therefore A' = {a') a E A. Finally, both the initial state and the goal extended with Pnach: % = so U {peach): }. S 8. [proch). indicating that are interested in plans that do not achieve p along their path, as any action that achieves p will delete Puach from the state, making the goal not reachable. We use off-the-shell planner to check if there is plan for II', If there is one, it corresponds to a plan for II that does not make p true and therefore p is not landmark, and we assign the score of O. If II' is found unsolvable, then p is a landmark and we assign the score of 1. The answer validation is therefore PSPACE-complete in this case as well.
8. Next Action (NextA) For action a, if it is in the set of kept correct answers, score it 1 and if it is in the set of known incorrect answers, we score it O. Otherwise, if it is applicable. we apply it the current state and obtain the state t. We find the optimal plan costs h² (s)s)) and h" (t) for these two states with the help of an optimal planner and score the answer 1 if h" (s) - hh" ht)(t)
1. Otherwise, we score it O. The answer validation is therefore PSPACE-complete this case as well.
7 EXPERIMENTS
7.1 BENCHMARKING PERFORMANCE
Following ACPBench, we generated 10 open-ended questions per domain for each of the 8 tasks, a total of 1040 questions. We evaluated 15 language/reasoning models, with the aim to cover small, medium, and large models, Small size: Granite 3.1 8B (Team) 2024) and Llama 3.1 8B Dubey et al. 2024); medium size: DeepSeek coder 33B (Guo et al. 2024) and Granite 34B code Mishra et al. 2024); Large size: Mixtral 8x22B [MistralAl 2024). Llama 3.1 70B and Llama 3.1 405B (Dueey et al. 2024). DeepSeek V3 (DeepSeek-A) Al et al. (0256). GPT-4o mini, GPT-4o (OpenAl et al." 2024a); Reasoning DeepSeek R1 (DeepSeek-Al et al. 2025a), ol mini, ol op-preveew

---

priserss
swrd
100
moc
log cal
80
Necowo id
6702
00
afwordd
task
Figure 3: Domain-wind wise accuracy of GPT-4o.
Figure 4:
Comparison of prediction error for GPT-4o
on different question formats.
OOpenAl et al. 2024b). and recent ween-weight reasoning models from OpenAl GPT OSS 20B and 120B (OpenAl et al. 2025).
All models were either accessed using API or hosted locally using hugging face transformer library on machines with A100 80 GB GPU. It is important to note that there significant difference in the energy consumption and evaluation cost between various models. While smaller models are relatively cheap, the larger language models such as Llama 3.1 405B and GPT-4o are prohibitively expensive to be used as planner components. The reasoning models such ol and even the cheaper DeepSeeek RI are even more expensive than the language models. Therefore, our experiments with these reasoning models are intended mostly for providing a frame of reference.
For each task, we evaluated a 2-shot prompting with static examples from outside the evaluation set. The two examples are from the grid and logistics domains, one each per task. This allows to exemplify the expected response format. Additionally, we instructed the language models to produce their response in particular format. Still, the tested models do not necessarily adhere to the instructions or the example format. Hence, to be able to extract the answer from the response, we developed a lenient grammar based parser, which would discard tokens if they did not fit expected token values. Figure g (Appendix) shows the grammar used for parsing the responses for our 8 tasks. For example, in the progression task, the response is "progression one for the positive effects and one for the negative effects. The response for the justification task is a "action list", which a list actions (or the updated plan) and the response for the validation task is an "index" which is the index of the first inapplicable action. Using the grammar with a parser that discards tokens not consistent with the grammar helps significantly in post-processing these open-ended responses. The post-processed results are then evaluated according to the procedures described in Section 6 Our evaluation code provided in the supplementary.
which is two lists,
Focusing first on the small and medium size language
Model
app areach just land nexta prog reach
val
models, Table [ shows the accuracy of these mod- els on the 8 tasks in our dataset. A conclusion we can draw from the figure is that there are three cate- gories tasks according model performance. First, progression seems to be the easiest tasks among the 8 tasks. Even so, the highest accuracy reached is 43% by Granite 34B code. The second category is the hard tasks of applicability and action reachability. In fact, none of these models could score above 2% for these two tasks. The third category includes the other 5 tasks with average performance between 8.8% and 28.8%. Hence, ACPBench Hard seems to be difficult dataset for the small and medium size language models.
Granite 3.1 8B
0.00
0.00
0.21 0.08 0.22
0.36 0.33
0.09
Llama 3.1 8B
0.00
0.00
0.22 0.06
0.25
0.40
0.33
0.13
DeepSeek coder 33B
0.02
0.02
0.21 0.10
0.17
0.42
0.18 0.15
Granite 34B code
0.02
0.00
0.17 0.11 0.18
0.43
0.28 0.12
Table 1: Small/medium size models performance, best results bolded.
Moving to large size models, Table shows the accuracy of the tested large language and rea- soning models. Looking first at the language models, the top part of the table, we observe that there no single model that outperforms all other models. GPT-44 is the top performer, with best results

---

in 5 out of 8 tasks, but is outperformed by 5% by Mixtral 8x22B on the reachability task, and by DeepSeek V3 on the action reachability task by 4% and on the justification task by 11%. Among the large reasoning models (bottom part) the ol-preveww model performs the best. Surprisingly, on the justification task the DeepSeek V3 language model remains the top performer. In all of our ex- periments we capped the maximum number of generated tokens at 1,000. For the GPT OSS models, however, we had to raise this limit to 4,000 because their reasoning chains were longer. Despite the higher token count and the resulting increase in inference cost, this did not translate into per- formance boost. Similar to the small and medium size language models, there are tasks such as progression that is relatively easy for all models, and there are tasks such as action reachability that is difficult for all models, and even ol -preview achieves only 12%. For other tasks, some models do better than others. Our third observation is that with the exception of what seems to the easiest for these models progression task, there are only three scores above 65%, and all of them are of reasoning models, indicating that the ACPBench Hard dataset is difficult even for large models.
look into the performance of the best performing LLM, GPT-40, across different domains. Figure F presents the performance of the top-performing language model GPT-4o on various tasks, across the existing domains. For other models performance we refer to the supplementary material. Observe that GPT-4o ex- hibits high performance on the progression task across most domains, showing somewhat lower accuracy in satellite, alfworld, and floortile. Action reachability and landmarks tasks, on the other hand, pose significant challenges to the model. The model consistently generated accurate answers for the visitall and grid domains across most tasks. In the remaining domains the performance varied across tasks, indicating that none of these domains are particularly easy for the models.
Going deeper.
Model
app
areach
just
land
nexta
prog reach val
Mixtral 8x22B
0.10
0.02
0.31
0.26
0.32
0.68
0.37
0.23
Llama 3.1 70B
0.12
0.02
0.44
0.20
0.42
0.65
0.28
0.20
LLMS
GPT-4o mini
0.07
0.01
0.14
0.04
0.35
0.59
0.22
0.27
Llama 3.1 405B
0.14
0.04
0.59
0.15
0.48
0.74
0.26
0.48
GPT-4o
0.25
0.01
0.54
0.29
0.55
0.78
0.32
0.62
DeepSeek V3
0.21
0.05
0.65 0.12 0.47
0.76
0.32
0.56
ol mini
0.38
0.06
0.44 0.38
0.64
0.70
0.60
0.78
GPT OSS 20B
0.03
0.09
0.14 0.47
0.62
0.72
0.50
0.14
LRMs
GPT OSS 120B
0.00
0.13
0.05 0.49 0.78
0.79
0.68
0.70
ol-preview DeepSeek R1
0.44
0.12
0.46 0.56
0.80
0.89
0.66 0.26
0.05
0.01
0.52 0.20 0.36
0.77 0.24 0.53
Table 2: Accuracy of Larger LLMs (top) and LRMs (bottom). Bold entries indicate the best overall model, while the underlined entries indicate the best among language moonreeasonng) models.
Finally, we evaluate the hardness of our proposed open-ended variants by comparing the perfor- mance of GPT-40 on these questions (gen) the two formats from ACPBench: boolean (bool) and multiple choice (meq). Figure the comparison in terms of model errors, the complement of the accuracy. As can be seen, model error in generative format of the task is significantly higher than bool and meq except for the validation task. Note, we are showing results from one of the largest models for this analysis. The gap in performance even more prolonged other models.
7.2 OBSERVATIONS AND INSIGHTS
The 2-shots seemed to be sufficient for the language models to mostly follow the instructions on the answer syntax. The number of parsing errors was typically negligible, with single exception of Llama 3.1 8B on the applicable actions task, where in 4 cases the model made up objects that did not follow the naming convention in the question and in 5 cases the model ran out of context generating the same actions over and over again.
While atom and action reachability are very much related tasks, the latter seems to be much harder for the tested models. It is not surprising, as action reachability requires an additional reasoning step about the atoms in the action preconditions and their reachability. Further, while reachability focuses on single atoms, action reachability requires reasoning about the entire precondition, that often consists of multiple atoms. The reasoning should now account for their interplay, as they need to hold in the same reachable state. In fact, action reachability seems to be consistently the most difficult task across the tested models. Here, the models needed to provide an action that can never become applicable, in any reachable state or None if there no such actions. Interestingly, only
8

---

the OpenAl models were able to correctly identify the latter case, and these were the majority of their correct answers. For instance, 9 out of 16 correct answers of ol ol-preveww and all the 8 correct answers of ol mini were None. Most of the other correct answers recognized that block cannot be (un)stacked on itself, which accounts for 5 out of 6 correct answers for DeepSeek V3, 4 out of 5 for Llama 3.1 405B, and 4 out of 16 for ol-preview.
Surprisingly, the second hardest task is action applicabilityy While one of the core tasks in plan- ning, it seems to be quite challenging even for the reasoning models, the largest of which scored 44%, while DeepSeek RI scoring only 5%. The smaller language models fail on this task, with only DeepSeek coder 33B and Granite 34B code showing performance slightly above O. Even the largest language models barely reach 25%. One reason for that is the strict requirement for produc- ing precisely the set of all applicable actions. While missing actions can hinder completeness and cause missing existing solutions, extra made up actions can lead to producing incorrect solutions, which arguably worse, Interestingly, if we only required not to make up actions, but allowed producing subsets of real answers, scoring according to Jaccard similarity, the score of the best per- forming model ol preview would go up to 57%. The largest absolute increase would be for Mixtral, going from 10% to 38%. Using such action generation in planner would correspond to loosing completeness, while keeping the soundness of the planner.
Looking at the landmarks task, among the smaller models, the best performing is Granite 34B. It gives quite uniform answers. Most of its correct answers are in the ferry domain, where it correctly identifies the ferry location landmark. In logistics, it recognizes package need to be in the truck in the goal city before it can be delivered. The best performing large language model GPT-4o achieves 29% accuracy, producing a diverse set of answers. In ferry, sometimes correctly identifies ferry being empty as a landmark, sometimes the need for a car to be onboard, and sometimes a ferry location was identified as a landmark. In logistics, trucks or packages at particular locations were identified as landmarks. In grid, it was more uniform, reporting in most cases holding a key as a landmark. In goldminer, all correctly identified landmarks were some locations being clear. The best performing reasoning model o1 -prevviww achieves 56% accuracy. It correctly reports twice in satellite and 6 times in swap the absence of non- convtrivial landmarks. The model that is best at recognizing that is ol mini, with 3 cases in visitall, 4 cases in satellite, 5 in swap, and once in alfworld. The only other model that can identify such cases is Mixtral 8x22B, with 3 cases in visitall.
The justification task is among the few tasks where the best among the language models is not GPT-40, but DeepSeek V3, which performs better than even the reasoning models. The second best performer is Llama 3.1 405B. Interestingly, in multiple cases, Llama produces a valid plan, which is shorter than the given plan, but not its subsequence, and hence not a correct answer. In some cases, Llama produced valid plan that changes the order of the given plan actions. Note, the aim of the justification task is not to produce valid plan, but to recognize unnecessary actions on a sequence.
The validation task requires an index to be returned, which makes it harder to investigate the source of the mistakes made. Most language models do not perform well on this task, with only the largest models go above 30%. Interestingly, the reasoning model ol op-priww scores much lower than ol mini (26% vs 78%). To investigate the source of its mistakes, we check the absolute difference between the given answer and the correct one. In 86% of the cases that ol o1-preview incorrectly answered the question, it errored by 1. It is important to note that it was mistaken in both directions, giving both lower and higher than the correct indices. Note that several models favor the answers 1, 10, and 100. For the majority of smaller models, most their answers are one of these three numbers.
The progression task is mostly simple for the reasoning model ol oprreeie which reaches 89%, but even this model makes mistakes. For example, it does not recognize reasonable positive effects, such as stacking a block on top of another block makes the top block clear. Not surprisingly, it misses less negative effects, such as taking a picture with rover camera makes the camera not calibrated. Surprisingly, it invents unreasonable effects such as communicating the rock data from rover to the lander would empty the rover's 's store and delete the effect of rocks being analyzed at the waypoint.
7.3 REPRESENTATION
In all the experiments presented so far, our prompt included only the natural language representation of the domain and the problem as part of the context, "NL". Here, we experiment with two addi- tional representations of the context: "PDDL." where the context included only the PDDL domain

---

and the PDDL problem, "PDDL+NL", where the context included both the natural language rep- resentation of the domain and problem as well as the PDDL representations. Table 3 presents the performance of DeepSeek V3. The results indicate that incorporating the PDDL domain alongside the natural language representation significantly improves performance. However, when the PDDL. files available, using traditional planner may be more appropriate, rendering the use of LLM unnecessary.
We look the model performance on one of the computationally hardest tasks, the new next action task with the mixed PDDL+NL representation, where the model shows higher than expected accuracy. To better un- derstand the phenomena, Figure [ shows the per-domain accuracy of DeepSeek V3 as a function of dis- tance goal. Note, the accuracy is not uniform across domains. While, as expected, the accuracy decreases with the distance, we note some domains like ferry and satellite, where there is increase for larger distances. The chances of randomly choosing a correct answer in these domains are low (See Table 7 Appendix).
app
areach
just land nexta prog reach
avg
NL
0.21
0.05 0.65
0.12 0.47 0.76 0.32
0.56
0.39
PDDL
0.31
0.74
0.21 0.53
0.87
0.33
0.55
0.44
PDDLANI
0.32
0.09 0.68 0.19 0.60 0.88 0.37
0.61
0.47
Table 3: DeepSeek V3 comparison of prompt representa-
tions: "NL", "PDDL", "PDDL+NL".
8 CONCLUSIONS, LIMITATIONS, SOCIETAL IMPACT, AND FUTURE WORK
We have created ACP- Bench Hard, a benchmark of open-ended questions that reflect precisely the questions answered by symbolic planners during the planning process.
logistics
0.8
blocksworld
grid
0.6
Tloortie
Accuracy
grippers
rovers
We therefore believe that ACPBench Hard good benchmark for testing reasoning abilities that required for planning. Based on an empirical in- vestigation of collection of large language models conclude that the largest and the best performing models have a very long way to hefore they can reliably plan.
0.4
Visitall
depot
geldminer
0.2
sateilite
altworld
0.0
Distance to goal
Figure 5: Domain-wise accuracy of DeepSeek V3 on next action, large evaluation set.
There are few limitations to our work. First, the benchmark only captures subset of planning problems. Second, our lenient evaluation only evaluates the first answer in the output. Third, we do not evaluate the reasoning process; only the final answers.
Improving the planning abilities of autonomous agents can have both positive and negative societal impact. Among the positive impact factors are increased efficiency and productivity of our society, which can also lead to negative factors such job displacement and economic inequality. Being aware of these impact factors the first step towards being able to exploit the positive impacts while mitigating the negative ones.
Creating training data for generative questions with chain of thought, would promising area of future research, because for planning problems instructive chain of thought is often not obvious. Another avenue for future research would be extending the benchmark to additional tasks such as object counting in current state.
10

---

REFERENCES
Tom Bylander. The computational complexity of propositional STRIPS planning, Artificial Intelli- gence, (9(1-2):155-244, 1994.
Karl Cobbe. Vincet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek. Jacob Hilton, Reiichiro Nakano, Christopher Hesse, and John Schulman. Training verifiers to solve math word problems. 10. [cs.LG] 2021.
DeepSeek-AL, Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, et al. DeepSeek-RI: In- centivizing reasoning capability LLMMs via reinforcement learning. arXiv:2501. 12944 [cs.CL.], 2025a.
DeepSeek-AL, Aixin Liu, Bei Feng, Bing Xue, Bingxuan Wang, Bochao Wu, al. DeepSeek-V technical report. arXiv:2412.19433 [cs.CL.], 2025b.
Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Amy Yang, Angela Fan, Anirudh Goyal, et al. The llama 3 herd of models. arXiv:2407.21783 [cs.Al], 2024.
Eugene Fink and Qiang Yang. Formalizing plan justifications. In Proceedings of the Ninth Confer- ence of the Society for Computational Studies of Intelligence, pp. 9-14, 1992.
Leo Gao, Jonathan Tow, Baber Abbasi, Stella Biderman, Sid Black, Anthony DiPofi, Charles Fos- ter, Laurence Golding, Jeffrey Hsu, Alain Le Noac'h, Haonan Li, Kyle McDonell, Niklas Muen- nighoff, Chris Ociepa, Jason Phang, Laria Reynolds, Hailey Schoelkopf, Aviya Skowron, Lintang Sutawika, Eric Tang, Anish Thite, Ben Wang, Kevin Wang, and Andy Zou. The language model evaluation harness, 07 2024. URL
zenodo. org/ rwc. rww wwwocrdd///10000000 126086022222
Daya Guo, Qihao Zhu, Dejian Yang. Zhenda Xie, Kai Dong, Wentao Zhang, Guanting Chen, Xiao Bi, Y. Wu, Y. K. Li, Fuli Luo, Yingfei Xiong, and Wenfeng Liang. DeepSeek-Coder: When the large language model meets programming - the rise of code intelligence. arXiv:2401.14196 [cs.SE]], 2024.
Divij Handa, Pavel Dolin, Shrinidhi Kumbhar, Chitta Baral, and Tran Cao Son. ActionReasoning- Bench: Reasoning about actions with and without ramification constraints. In Proceedings of the Thirteenth International Conference on Learning Representations (ICLR 2025). OpenReview.net, 2025.
Weinan He, Canming Huang, Zhanhao Xiao. and Yongmei Liu. Exploring the capacity of pretrained language models for reasoning about actions and change. Anna Rogers, Jordan Boyd-Graber and Naoaki Okazaki (eds.), Findings of the Association for Computational Linguistics: ACI. 2023, pp. 4629 4643. Association for Computational Linguistics, 2023.
Jörg Hoffmann and Bernhard Nebel. RIFO revisited: Detecting relaxed irrelevance. In Amedeo Cesta and Daniel Borrajo (eds.), Proceedings of the Sixth European Conference on Planning (ECP 200/), pp. 127-135. AAAI Press, 2001.
Jörg Hoffmann, Julie Porteous, and Laura Sebastia. Ordered landmarks in planning. Journal of Artificial Intelligence Research, 22:215-278, 2004.
Subbarao Kambhampati, Karthik Valmeekam, Lin Guan, Mudit Verma, Kaya Stechly, Siddhant Bhambri, Lucas Paul Saldyt, and Anil Murthy. Position: LLMs can't plan, but can help planning in LLM-modulo frameworks. In Proceedings of the 41st International Conference Machine Learning (ICML 2024). JMLR.org. 2024.
Michael Katz and Junkyu Lee. K* search over orbit space for top-k planning. In Edith Elkind (ed.), Proceedings of the 32nd International Joint Conference on Artificial Intelligence (IJCAI 2023). IJCAI, 2023a.
Michael Katz and Junkyu Lee. K* and partial order reduction for top-quality planning. In Roman Barták, Wheeler Ruml, and Oren Salzman (eds.), Proceedings of the 16th Annual Symposium on Combinatorial Search (SoCS 2023). AAAI Press, 2023b.

---

Michael Katz and Shirin Sohrabi. Reshaping diverse planning. In Vincent Conitzer and Fei Sha (eds.), Proceedings of the Thirty-Fourr Fourth AAAI Conference on Artificial Intelligence (AAAI 2020),
pp. AAAI Press, 2020.
Michael Katz, Shirin Sohrabi, and Octavian Udrea. Top-quality planning: Finding practically useful sets of best plans. In Vincent Conitzer and Fei Sha (eds.). Proceedings of the Thirty-Forr Fourth AAAI Conference on Artificial Intelligence (AAAI 2020), pp. 9900-9907. AAAI Press, 2020.
Emil Keyder, Silvia Richter, and Malte Helmert. Sound and complete landmarks for and/or graphs. In Helder Coelho, Rudi Studer, and Michael Wooldridge (eds.). Proceedings of the 19th European Conference on Artificial Intelligence (ECAI 2010), pp. 335-340, IOS Press, 2010.
Harsha Kokel, Michael Katz, Kavitha Srinivas, and Shirin Sohrabi. ACPBench: Reasoning about action, change, and planning. In Julie Shah and Zico Kolter (eds.), Proceedings of the Thirty-Ninth AAAI Conference on Artificial Intelligence (AAAI 2025). AAAI Press, 2025.
Xixun Lin, Yucheng Ning, Jingwen Zhang, Yan Dong, Yilong Liu, Yongxuan Wu, Xiaohua Qi, Nan Sun, Yanmin Shang, Kun Wang, Pengfei Cao, Qingyue Wang. Lixin Zou, Xu Chen, Chuan Zhou, Jia Wu, Peng Zhang, Qingsong Wen, Shirui Pan, Bin Wang, Yanan Cao, Kai Chen, Songlin Hu, and Li Guo. LL.M-based agents suffer from hallucinations: A survey of taxonomy, methods, and directions. ar arxiv:2509.1 18970
[Is. 2025.
Xiao Liu, Hao Yu, Hanchen Zhang, Yifan Xu, Xuanyu Lei, Hanyu Lai, Yu Gu, Hangliang Ding, Kaiwen Men, Kejuan Yang. Shudan Zhang, Xiang Deng, Aohan Zeng. Zhengxiao Du, Chenhui Zhang, Sheng Shen, Tianjun Zhang, Yu Su, Huan Sun, Minlie Huang, Yuxiao Dong, and Jie Tang. AgentBench: Evaluating LLMs as agents. Proceedings of the Twelfth International Conference on Learning Representations (ICLR 2024). OpenReview.net, 2024.
Chang Ma, Junlei Zhang. Zhihao Zhu, Cheng Yang, Yujuu Yang, Yaohui Jin, Zhenzhong Lan, Ling- peng Kong, and Junxian He. AgentBoard: An analytical evaluation board of multi-turn LLM agents. 1311:22401.3317 [cs.CL], 2024.
Drew McDermott. The 1998 AI Planning Systems competition. Al Magazine, 21(2):35-55 2000.
Mayank Mishra, Matt Stallone, Gaoyuan Zhang, Yikang Shen, Aditya Prasad, et al. Granite code models: A family open foundation models for code intelligence. arXiv:2405.0432. 04424 [cs.Al], 2024.
MistralAI. Mixtral 8x22B.
2024.
OpenAI, :, Aaron Hurst, Adam Lerer, Adam P Goucher, Adam Perelman, et al. OpenAl GPT-4o system card. arXiv:2410.21276 [cs.CL], 2024a.
OpenAI, : Aaron Jaech, Adam Kalai, Adam Lerer, Adam Richardson, et al. OpenAl ol system card. arXiv:2412.16720 [cs.AI], 2024b.
OpenAI, :, Sandhini Agarwal, Lama Ahmad, et al. gpt-oss- 120b & gpt-oss-20b model card. arXiv:2508. 10925 [cs.CL], 2025.
Julie Porteous, Laura Sebastia, and Jörg Hoffmann. On the extraction, ordering, and usage of land- marks in planning. Amedeo Cesta and Daniel Borrajo (eds.), Proceedings of Sixth European Conference Planning (ECP 2001), pp. 174-182. AAAI Press, 2001.
Shreyas Sundara Raman, Vanya Cohen, Ifrah Idrees, Eric Rosen, Raymond Mooney, Stefanie Tellex, and David Paulius. CAPE: Corrective actions from precondition errors using large language models. In Proceedings of the 2024 IEEE International Conference on Robotics and Automation (ICRA 2024), pp. 14070-14077. IEEE, 2024.
Silvia Richter, Malte Helmert, and Matthias Westphal. Landmarks revisited. In Proceedings of the Twenty-Thin AAAI Conference on Artificial Intelligence (AAAI 2008), pp. 775-982, AAAI Press, 2008.
12

---

Mauricio Salemno, Raquel Fuentetaja, and Jendrik Seipp. Eliminating redundant actions from plans using classical planning. In Pierre Marquis, Tran Cao Son, and Gabriele Kern-Isberne (eds.), Proceedings of the Twentieth International Conference Principles of Knowledge Representa- fion and Reasoning (KR 2023), pp. 774-778. IJCAI Organization, 2023.
Abulhair Saparov and He He. Language models are greedy reasoners: A systematic formal anal- In Proceedings of the Eleventh International Conference on Learning
ysis of serin-of--houuee Representations (ICLR 2023). OpenReview.net, 2023.
Katharina Stein, Daniel Fišer, Jörg Hoffmann, and Alexander Koller. Automating the generation of prompts for LLM-based action choice in PDDL planning. In Nir Lipovetzky, Sebastian Sar- dina, Daniel Harabor, and Miquel Ramirez (eds.), Proceedings of the Thirty-Fifth International Conference on Automated Planning and Scheduling (ICAPS 2025). AAAI Press, 2025.
Katharina Stein, Nils Hodel, Daniel Fišer, Jörg Hoffmaan, Michael Katz, and Alexander Koller. Improved generalized planning with LLMs through strategy refinement and reflection. In Pro- ceedings of the Thirty-Sixth International Conference on Automated Planning and Scheduling (ICAPS 2026). AAAI Press, 2026.
Mirac Suzgun, Nathan Scales, Nathanael Schärli, et al. Challenging BIG-Bench tasks and whether Chain-of-Thought can solve them. In Anna Rogers, Jordan Boyd-Graber, and Naoaki Okazaki (eds.), Findings of the Association for Computational Linguistics: ACL 2023, pp. 13005-13051. Association for Computational Linguisties, 2023.
IBM Granite Team. Granite 3.0 language models, October 2024, URL URLhtttps://itthbbcco
1.m 1bmm-gran gww.gggtgraaanteeeeeeeeerrr 3. 3awp:itteee.o--anuuuaeeeeeeeee modelee 1s/
Karthik Valmeekam, Matthew Marquez, Alberto Olmo, Sarath Sreedharan, and Subbarao Kamb- hampati. PlanBench: An extensible benchmark for evaluating large language models on planning and reasoning about change. In Proceedings of the Thirty-Seventh Annual Conference on Neural Information Processing Systems (NeurIPS 2023) Track on Datasets and Benchmarks, pp. 38975- 38987, 2023a.
Karthik Valmeekam, Matthew Marquez, Sarath Sreedharan, and Subbarao Kambhampati. On the planning abilities of large language models A critical investigation. In Proceedings of the Thirty-Seventh Annual Conference on Neural Information Processing Systems (NeurIPS 2023), pp. 75993-76005, 2023b.
Qiantong Xu, Fenglu Hong, Bo Li, Changran Hu, Zhengyu Chen, and Jian Zhang. On the tool manipulation capability of open-source large language models. arXiv:2305.16500 [cs.CL], 2023.
Lin Zhu and Robert Givan. Landmark extraction via planning graph propagation. In ICAPS 2003 Doctoral Consortium, pp. 156-160, 2003.
13

---

9 APPENDIX
A TECHNICAL APPENDICES AND SUPPLEMENTARY MATERIAL
A.1 RELATED WORK
Table presents comparison of ACPBench Hard with other PDDL-based Planning Benchmarks. Existing benchmarks either focus on few tasks or few domains. For example, PlanBench has only 3 domains but 8 tasks, where as AutoPlanBench has 13 domains but only I task. Ac exception to this is Action Reasoning Bench which has reasonable number of domains and tasks, but they lack systematic evaluation of the generative questions. With addition of ACPBench Hard, the ACPBench dataset contains all three formats of questions: generation, boolean and multi-choice questions. Most importantly, Table presents the coverage of different tasks in the existing literature. As can be seen while the Action Applicability, Progression and Validation have some coverage in TRAC and ActionReasoningBennde Landmark, and Next Actions are not really covered by existing benchmarks.
the tasks like Reachability, Action Reachability, Justification,
Dataset
PlanBench
AutoPlanBench
TRAC
ARB
ACPBench
ACPBench Hard
Tasks
8
1
4
6
7
Domains
3 (+variants)
13
1
8
13
13
NL templates
X
V
Evaluation
Question Format
Generative
Boolean
X
MCQ
X
Tasks
Applicability
X
X
Progression
Reachability
X
Action Reachubility
X
Validation
XX
Justification
X
X
Landmark
X
Next Action
X
Table 4: Comparison of ACPBench-hard with existing Planning Benchmarks. Evaluations either
using string matching (+), symbolic tools ( ) or using another L.M ( (LLM).
14

---

Action level
Applicability
Progression
Identify all actions that can be performed now, in a given state
Predict everything that changes after a particular action is taken.
Failures: Hallucinated tools, blocked moves
Failures: missing effects, Ignored side-effects
State level
Reachability
Action Reachability
What could possibly happen
Determine which actions could become possible and which will never be
and what is impossible from current state
Fail: attempt impossible goals, invent states
Fail: invalid arguements actions
Plan level
Validation
Justification
Does the plan work?
Simply the plan.
Where does it break first?
Remove redundancy
Fail: misxed unmet pre-condition
Fail: Redundant plan, over-compression
Landmark
Next Action
Which milestones can not be skipped?
Pick step that moves you closer to the goal
Fail: skip requisites, collapse dependencies
Fail: irrelevant drift
Figure 6: Summary of 8 reasoning tasks included in ACPBench- Hard
15

---

A.2 DATASET
Figure 6 summarizes the 8 tasks included in the ACPBench Dataset. Below, we provide one sample question for each of the task.
APPLICABILITY
Listing Example of Applicability
"id": -5674255044118000688
"group":
"context"; "This is a ferry domain, where the task is to tzansport cars from their start to their goal locations, using a ferry. Each location is accessible by ferry from each other location. The cars can be debarked or boarded, and the ferry can carry only one car at time. AnThere are 2 locations and 20 cars, numbered consecutively. AnCurrently, the ferry is at 10, with the car c2 board. The cars are at locations as follows: c0, c3, c15, c10, c8, c6, and c9 are at 10; clB, c17, c16, c4, c19, c5, c13, c7, cl, c12, c14, and cll are at 11. The available actions are: (sail ?from ?to) travel by sea from location ?from to location ?to, (board ?car ?loc) load the car ?car location ?loc on to the ferry, and (debark ?car ?loc) unload the car ?ear from the ferry location ?loc.",
"question": "Generate the list of all ground actions that are applicable in this state.", " "answer":
"debark c2 10)", " "sail 10 11)"
"WDDL_domain"; "(dffine (domain ferry) \n (:requirements
strips :typing) \n (:types car location - object) \n
(:predicates (at car ?1 location) (at-ferry ?1
location) (empty-ferry) (not-eg ?x ?y) (on ?o car)) An :parameters (?car car ?loc :precondition (and (at ?car Ploc)
(:action board location) \n (at-ferry ?loc) (empty-ferzy)) ?car) (not (at ?car ?loc)) (not (empty-ferry)
:effect (and (on
An
(:action debarkln location) An
:parameters (?car car ?loc :precondition (and (on ?car)
(at-ferry ?loc) An (empty-ferry) (not (on ?car)) \n sailin location) \n (at-ferry ?from) (not (at-ferry ?from))) :effect (and (at-ferry ?to) \n)"
:effect (and (at ?ear ?loo)
(:action :parameters (?from location ?to :precondition (and (not-eq ?from ?to)
"PDDI_problem"; "deffine (problem ferry-12-c20) \n ferry) \n (:requirements :strips :typing) In (robjects c0 el c10 cll c12 c13 c14 c15 cl6 c17 c18 c19 c3 c4 c5 e6 c7 c8 69 car 11 location) An (:init (at c0 10) (at el 11) (at c10 10) (at cll 11) (at
(:domain
c12 11) (at c13 11) (at c14 11) (at c15 10) (at c16 11)
(at c17 11) (at c18 11) (at c19 11) (at c3 10) (at c4 11)
(at e5 11) (at a6 10) (at c7 11) (at c8 10) (at 6s 10)
(at-ferry 10) (not-eq 10 11) (not-eq 11 10) (on en)
(:goal (and (at c0 10) (at el 11) (at c2 11) (at c3 10)
(at c4 11) (at c5 11) (at c6 11) (at c7 11) (at c8 11)
16

---

(at 69 10) (at c10 10) (at cll 11) (at c12 11) (at c13
10) (at c14 11) (at c15 10) (at c16 11) (at c17 11) (at
c18 11) (at
c19 \n)
PROGRESSION
Listing Example of Progression
"id": 29744016040685545,
"group": "progression_ge" _en"", "context"; "This is a ferry domain, where the task is to tzansport cars from their start to their goal locations, using a ferry. Each location is accessible by ferry from each other location. The cars can be debarked or boarded, and the ferry are 2 locations and 10 cars, numbered consecutively.
carry only one
at time. \nThere
InCurrently, the ferry is at 11, with the car c2 board. The cars are at locations as follows: c5, c9, and c4 are at 11; c3, c0, cl, c6, c7, and c8 are 10. The available propositions are: (at-ferry ?1) The ferry is ?l location, (at 7c ?1) Car is at location ?l, (empty-ferry) The ferry is empty, and (on ?0) Ferry has car ?c on board.", "question": "Break down the outcomes of performing the action \"debark car
to location from the ferry)" into two lists, positive effects and negative effects. Positive effects are the propositions that are false in the current state but will become true after performing the action. Negative effects are the propositions that are true in the current state and will become false after performing the action.", "answer":
"pos":
" "eempyy- "(empty-ferry)
" (at c2 11)"
"neg": [
" "(n c2)
}.
TIDDL_domain!! (define (domain ferry) \n
(:requirements
strips :typing) \n (:types car location object) \n
(:predicates (at ?e car ?1 location)
(at-ferry ?1
location) (empty-ferry) (not-eq ?x ?y) (on 7c car) An :parameters (?car car ?loc :precondition (and (at ?car ?loc)
(:action board\n location) An (at-ferry ?loc) (empty-ferzy)) An ?car) (not (at ?car ?loc)) (not (empty-ferry)))
reffect (and (on
in
(:action debarkIn location) \n
:parameters (?car car ?loc :precondition (and (on ?car)
sat-ferry ? An tempty-ferry. (not (on ?car))) \n
:effect (and (at ?car ?loc)
(:action :parameters (?from location ?to :precondition (and (not-eq ?from ?to) reffect (and (at ?to)
sailin location) \n (at-ferry ?from) \n (not (at-ferry ?from)))
)n))
17

---

"(define (problem ferry-12-c10) \n
(:domain
ferry) In (:requirements :strips :typing) \n
(:objects c0 el c2 e3 c4 c5 c6 c7 c8 c9
10
11
location) \n
(:init (at c0 10) (at cl 10) (at c3 10)
(at 64 11) (at c5 11) (at c6 10) (at c? 10) (at c8 10)
(at c9 11) (at-ferry 11) (not-eg 10 11) (not-eq 11 10)
(on in
(:goal (and (at c0
10) (at 10) (at c2
11) (at c3 11) (at c4 10) (at c5 10) (at c6 10) (at c7
10) (at c8 10) (at c9 11))) An)
REACHABILITY
Listing 3: Example of Reachability
"id": 6900550407010230,,
"group": "reachable "reachable_atom__e" _tte__ttto______________e
"context"; "This is ferry domain, where the task is transport cars from their start to their goal locations, using a ferry. Each location is accessible by ferry from each other location. The cars can be debarked or boarded, and the ferry can carry only one car at a time. \nThere are 2 locations and 5 cars, numbered consecutively.
AnCurrently, the ferry is at 10, with the car c2 on board. The cars are at locations as follows: c3, c0, and al are at 10; c4 at 11. The available propositions
are: (at-ferry ?1) The ferry is at ?1 location, (at ?c ?1) Car ?o is at location ?1, (empty-ferry) is empty, and (on ?c) Ferry has car ?o board.", "question"; "What proposition can never hold in any potentially reachable state?",
The ferry
"answer": [],
"PDDI_domaing " "defiin (domain ferry) \n (trequirements :
strips :typing) An
(:predicates (at (:types car location - object) \n
car ?1 location) (at-ferry ?1
location) (empty-ferry) (not-eq ?x ?y) (on ?o car) An :parameters (?ear car ?loc :precondition (and (at 7car Ploc)
(:action board location) \n (at-ferry ?loc) (empty-ferry) ?car) (not (at ?car ?loc)) (not (empty-ferry))
:effect (and (on
An
(:action debarkin location) \n (at-ferry )
:parameters (?car car ?loc :precondition (and (on ?ear)
:effect (and (at ?ear ?loc)
(empty-ferry) (not (on ?car)) An sailin location) \n (at-ferry 2from))\nn (not (at (at-ferry ?from))) :effect (and (at-ferry ?to)
(:action
:parameters (?from location ?to
:precondition (and (not-eq ?from ?to)
\n)
"PDDI_problem": "definn (problem ferry-12-c5) \n ferry) \n (:requirements :strips :typing) \n (:objects c0 cl c2 c3 c4 car 10 11 location) An
(:domain
(sinit (at c0 10) (at el 10) (at c3 10) (at c4 11)
(at-ferry 10) (not-eq 10 11) (not-eq 11 10) (on c2) ) An (:goal (and (at co 11) (at el 10) (at c2 11) (at c3 10) (at c4 10))) \n)
18

---

ACTION REACHABILITY
Listing 4: Example of Action Reachability
"id": -2553164389902888,
"group": "reachable_action___e
"context": "This is a ferry domain, where the task is to transport cars from their start to their goal locations, using a ferry. Each location each other location. The cars can be debarked or boarded, and the ferry can carry only one car at a time. \nThere are 2 locations and 20 cars, numbered consecutively. AnCurrently, the ferry is at 10, with the car c2 on board. The cars are at locations as follows: c12, c18, c5, c4, c14, c19, c16, cll, cl, and 67 are at 11; c13, c6, c10, c17, c9, c3, ca, cO, and c15 are 10. The available actions are: (sail ?from ?to) - travel by sea from location ?from to location ?to, (board ?car ?loc) board the car ?car at the location ?loc, and (debark ?ear ?loc) debark the car 7car to location ?loc from the ferry.",
accessible by ferry from
"question": "What action can never become applicable, any state reachable from the current state?", "answer":
"sail 10 10)"
"PDDL_ :omain"; " "define (domain ferry) \n (:requirements strips :typing) \n (:types car location - object) \n
(:predicates (at ?e car ?1 location) (at-ferry ?1 location) (empty-ferry) (not-eq ?x ?y) (on 7c car)) An
(:action board\n location) An (at-ferry ?loc) (empty-ferzy)
:parameters (?ear car ?loc :precondition (and (at ?car ?loc)
reffect (and (on ?car) (not (at ?ear ?loc)) (not (empty-ferry))
in
:parameters (?car car ?loc (at (at-ferry ?loc) In :precondition (and (on ?car)
(:action debarkIn location) An
:effect (and (at ?car ?loc)
(empty-ferry) (not (on ?car))) \n sailln location) \n (at-ferry ?from)
(:action :parameters (?from location ?to
:precondition (and (not-eq ?from ?to) (not (at-ferry ?) :effect (and (at-ferry ?to) In)"
"PDDL_problen"" "(effine (problem ferry-12-c20)1 \n ferry) \n (:requirements :strips :typing) \n (:objects c0 el c10 cll c12 c13 c14 c15 c16 c17 c18 c19 e3 e4 c5 c5 c7 c8 69 car 11 locationn In
(:domain
(rinit (at c0 10) (at el 11) (at e10 10) (at cll 11) (at
e12 11) (at e13 10) (at c14 11) (at c15 10) (at e16 11)
(at e17 10). (at c18 11) (at c19 11) (at c3 10). (at c4 11) (at c5 11) (at c6 10) (at c7 11) (at c8 10) (at 69 10)
(at-ferry 10) (not-eq 10 11) (not-eq 11 10)
(on en))
(:goal (and (at co 10) (at el 11) (at c2 11) (at c3 10)
(at c4 11) (at c5 11) (at c5 11) (at c7 11) (at c8 11)
(at 69 10) (at c10 10) (at cll 11) (at c12 11) (at c13
10) (at c14 11) (at c15 10) (at c16 11) (at cl7 11) (at
c18 11) (at c19 i1)))
19

---

VALIDATION
Listing 5: Example of Validation
"id": 48969603189355153,
"group": "validation_gen"
"context": "This is ferry domain, where the task is transport cars from their start to their goal locations, using a ferry. Each location is accessible by ferry from each other location. The cars can be debarked or boarded, and the ferry can carry only one car at a time. \nThere are 2 locations and 5 cars, numbered consecutively.
\nCurrently, the ferry is at location and is empty. The cars are at locations are at 10; c4 is at 11. The goal is to reach a state where the following facts hold: Car c3 is at location 10, Car c4 is at location 10, Car cl is at location 10, Car e0 is at location 11, and Car c2 is at location 11. The available actions are: (sail ?from ?to) sail from location ?from to location ?to, (board ?car ?loc) board the car ?car at the location ?loc, and (debark ?car ?loc) debark the car ?car from the ferry to location ?loc.", "question": "What is the first inapplicable action in the next sequence
follows: c3, cl, cO, and c2
actions: (board c2 10) (debark c2 10) (board c2 10) (sail 10 11) (board c2 11) (board c4 11)
(sail 11 10) (debark c4 10) (board c0 10) (sail 10 11)
(debark c0 11) (sail 11 10) \??"
"answer": 4, "PDDL HWDDL_domain", "(dffine (domain ferry) In (:requirements strips :typing) \n (:types car location object) \n
(:predicates (at car ?1 location) (at-ferry ?1
location) (empty-ferry) (not-eq ?x ?y) (on ?c car)) An :parameters (?ear car ?loc :precondition (and (at ?car ?loc)
(:action board\n location) An (at-ferry ?loc) (empty-ferzy) ?car) (not (at ?car ?loc)) (not (empty-ferry) :parameters (?car car ?loc :precondition (and (on ?ear)
:effect (and (on
in
(:action debarkIn location) \n
(at-ferry ?loc) \n Sempty-ferry (not (on ?car))) )n sailln location) \n (at-ferry ) (not (at-ferry )n \n)
:effect (and (at ?car ?loc)
(:action :parameters (?from location ?to
:precondition (and (not-eq ?from ?to)
:effect (and (at-ferry ?to)
"Ppnt_problem": "deffine (problem ferry-12-c5) \n ferry) \n (:requirements :strips :typing) \n (:objects c0 cl c2 c3 c4 - car 10 11 - location) An
(:domain
(:init (at e0 10) (at el 10) (at c2 10) (at c3 10) (at
11) (at-ferry 10) (empty-ferry) (not-eq 10 11) (not-eq 11 )n (:goal (and (at co 11) (at el 10) (at c2 11) (at c3 10) (at c4 An)
JUSTIFICATION
Listing 6: Example of Justification
20

---

"id": -12195596766188255
"group": action_jjstification _en__geen,,,
"context"; "This is ferry domain, where the task is to transport cars from their start to their goal locations, using a ferry. Each location is accessible by ferry from each other location. The cars can be debarked or boarded, and the ferry can carry only one car at a time. \nThere are 2 locations and 2 cars, numbered consecutively.
\nCurrently, the ferry is at location and is empty. The cars are at locations as follows: cl and c0 are at 10. The available actions are: (sail ?from ?to) sail from location ?from to location ?to, (board ?car ?loc) board the car ?car at the location ?loc, and (debark ?car ?loc) debark the car ?car to location ?loc from the ferry. The goal is to reach a state where the following facts hold: Car el is at location 11 and Car c0 is at location 11.",
"question": "Simplify the plan (board cl 10) (sail 10 11) (sail 11 10) (sail 10 11) (debark cl 11) (sail 11 10)
(sail 10 11) (sail 11 10) (board 10) (sail 11)
(debark e0 11) (board el 11) (debark el 11) by removing either a single action or a pair of consecutive actions, while still maintaining a valid plan. Provide the resulting simplified plan.", "answer":
" (sail 10 11)", (sail 11 10) " "-1"
1,
(sail 11 10)", " (sail 11)", "-1"
" (sail 11 10)", " (sail 10 11)", ", "-1"
" (sail 10 11)", "saill 11 10)" " "_1"
(board el 11)", " (debark cl 11)",
"PDDL_domaing "define (domain ferry) \n strips styping) \n (:types car location object) An
(:zequirements :
(:predicates (at ?c car ?1 location) location) (empty-ferry) (not-eq 7x ?y) :parameters (?ear car ?loc :precondition (and (at ?car ?loc)
(at-ferry ?1
(on 76 car)) An
(:action board location) \n (at-ferry ?loc) (empty-ferry) An ?car) (not (at ?ear ?loc)) (not (empty-ferry)))
:effect (and (on
) in
21

---

(:action debark\n location) \n
:parameters (?car car ?loc :precondition (and (on ?car)
(at-ferry ?loc)) \n
:effect (and (at ?ear ?loc)
(empty-ferry) (not (on ?car))) \n
(:action :parameters (?from location ?to
sailin location) \n
:precondition (and (not-eq ?from ?to)
(at-ferry ?from) ) (not (at-ferry ) An \n)
:effect (and (at-ferry ?to)
"PDDL_problem"; "definn (problem ferry-12-c2) \n ferry) \n (:requirements :strips :typing) \n
(:demain
(:objects c0 cl car 10 11 location) In c0 10) (at el 10) (at-ferry 10) (empty-ferry) (not-eq 10 11) (not-eq 11 1n (:goal (and (at c0 11) (at cl An)
(:init (at
LANDMARK
Listing 7: Example of Landmark
"id": 5196771102924997,,
"group": "Landmarks_gen",
"context": "This is ferry domain, where the task is transport cars from their start to their goal locations, using a ferry. Each Location accessible by ferry from each other location. The cars can be debarked or boarded, and the ferry can carry only one car at a time. \nThere are 2 locations and 10 cars, numbered consecutively. AnCurrently, the ferry is at 11, with the car c6 on board. The cars c2 are at 11; cl, c7, e3, co, c5, and c8 are at 10. The goal is to reach state where the following facts hold: Car 69 is at location 11, Car a4 is at location 10, Car c6 is at location 10, Car el is location 10, Car c7 is at location 10, Car c2 is at location 11, Car c3 is at location 11, Car is at location 10, Car is at location 10, and Car c8 is at location 10. The available propositions are: (at-ferry ?1) The ferry at ?1 location, (at ?o ?1) - Car ?0 is at location 71, (empty-ferry) The ferry is empty, and (on ?c) Car ?o is on board the ferry.",
at locations
follows: c9, c4, and
"question": "Generate a non-trivial fact landmark, one that does not hold in the initial state or goal.", "answer":
"yes":
"(nn c3)",
" "on "
"(at-ferry 10) ", " (empty-ferry) "
"no": [
" "(t c2 10)", "(at c5 11)", " "(at cl 11)",
"(t c8 11)",
" "(at c6 11)", (on cl)" "
(at c0 11)",
22

---

" "(on c5) n
(on c9)
"on c2)
(on c7)
" ((at c7 11)
"on c0)
" (on c
" "(a c9 10)
}
"PDDI_domain": "deffine (domain ferry) An strips styping) \n (:types car location object) An (:predicates (at ?c car ?1 location)
(trequirements
(at-ferry ?1
location) (empty-ferry) (not-eg ?x ?y) (on ?o car) \n :parameters (?ear car ?loc :precondition (and (at ?car Ploc)
(:action board location) 'n (at-ferry ?loc) (empty-ferry) ?car) (not (at ?car ?loc)) (not (empty-ferry)
:effect (and (on
i'
(:action debarkin location) \n (at- ) (empty-ferry) (not (on 2car))) In
:parameters (?car car ?loc :precondition (and (on ?car)
:effect (and (at ?ear ?loc)
(:action
sailln location) \n
:parameters (?from location ?to :precondition (and (not-eq ?from ?to)
(at-ferry ?from) \n (not (at-ferry )) :effect (and (at-ferry ?to)
\n)",
PPDDL_problem": "definn (problem ferry-12-c10) \n ferry) in
(:domain
(:requirements :strips :typing) \n (:objects e0 el c2 c3 e4 c5 c6 c7 c8 c9
10 11
location) An
(:init (at c0 10) (at cl 10) (at c2 11)
(at c3 10) (at 04 11) (at
10) (at 67 10) (at c8 10)
(at c9 11) (at-ferry 11) (not-eq 10 11) (not-eq 11 10)
(on in
(:goal (and (at 10) (at 10) (at c2
11) (at c3 11) (at c4 10) (at c5 10) (at c5 10) (at c7
10) (at c8 10) (at 69 11))) \n)
NEXT ACTION
Listing 8: Example of Next Action
"id": -6005458063915523
"group": "goai_closer_ge""
"context": "This is a ferry domain, where the task is to transport cars from their start to their goal locations, using a ferry. Each location is accessible by ferry from each other location. The cars can be debarked or boarded, and the ferry can carry only one car at a time. AnThere are locations and cars, numbered consecutively.
\nCurrently, the ferry is at 11 location and it is empty. The cars are at locations as follows: c0, c4, and el are at 10; c3 and c2 are at 11. The goal is to reach a state where the following facts hold: Car o0 is at location 11, Car c4 is at location 10, Car cl is at location 10, Car c3 is at location 10, and Car c2 is at location 11. The available actions are: (sail ?from ?to) travel by sea from location ?from to location ?to, (board ?car ?loc) board the Pear the location ?loc, and (debark ?ear
23

---

?loc) debark the car ?car from the ferry to location ?loc.",
"question": "What is the next action that takes towards the goal?", "answer":
"yes": " (board c3 11)
"ne": [
"(board c2 11)",
" "(sal 11 10)
"maybe": [],
"opt": "6"
"PDDL "iDDL_dommin"; "defiine (domain ferry) \n
(:requirements
strips :typing) An (:predicates (at (:types car location object) An
car ?1 location)
(at-ferry ?1
location) (empty-ferry) (not-eq ?x ?y) (on ?o car) An :parameters (?ear car ?loc :precondition (and (at ?car ?loc)
(:action board)n location) An (at-ferry ?loc) (empty-ferzy)) ?car) (not (at ?ear ?loc)) (not (empty-ferry)
reffect (and (on
in
(:action debarkin location) An (at-ferry ?loc) \n (empty-ferry) (not (on ?car)) )n sailin location) \n (at-ferry ?from) (not (at-ferry )f
:parameters (?car car ?loc :precondition (and (on ?car)
:effect (and (at ?ear ?loc)
(:action :parameters (?from location ?to
:precondition (and (not-eq ?from ?to) :effect (and (at-ferry ?to)
\n)"
"PDDL_prodee problempoolemm: "defiine (problem ferry-12-c5) \n ferry) (:requirements :strips :typing) In (:objects e0 cl c2 c3 c4 car 10 11 location) An
(:domain
(:init (at c0 10) (at cl 10) (at c2 11) (at c3 11) (at c4 10) (at-ferry 11) (empty-ferry) (not-eq 10 11) (not-eq 11 An (:goal (and (at c0 11) (at al 10) (at c2 11) (at e3 10) (at c4 \n)
A.3 GENERATION PROCESS
Figure iillustrates the overall generation process of the ACPBench- Hard dataset.
APPLICABILITY
While constructing the action applicability dataset, we impose a bound on the number of applicable actions in state. We only keep the states when [A(s) is < 100. While the bound is high, in most cases the number of applicable actions are < 10. Table presents the Max and Mean number of Applicable Actions.
EVALUATION
Table 6 show the complexity of evaluating an answer per task.
A.4 GRAMMAR FOR PARSING THE MODEL. RESPONSE
Figure shows the grammar used for parsing the responses for 8 tasks.
24

---

Problem/Domain Generator
PDDL Domain and
Problem File
(:d)
(:a)
A <
sample
Hi
(:p)
Generate Task
Find plans
Sample
Translation to NL
Question and
ACPBench Hard Instance
States or Plans
Answer
Figure 7: High-level Workflow of Generating ACPBench Hard Dataset. 1. We use the Problem/- Domain Generator when available to generate PDDL Problem and Domain Files. For Alfworld domain, skip this step and directly the PDDL Domain and Problem file made available in the Alfworld repo. 2. Given a PDDL Problem and Domain File, we use a top-K K planner (Katz et al. 2020) to find multiple plans. Depending the task, either sample plans from the obtained plans or sample intermediate states on these plans. 4. We generate question and answer for the task symbolically. 5. Translate the Symbolic task to Natural Language using Templates. Save the Natural Language question and the information needed to evaluate the answer to the ACPBench
Hard Dataset
Applicable Actions
Domain
Max
Mean
ferry
10
5.00
logistics
10
9.50
blocksworld
4.60
grid
6
4.00
floortile
10
9.50
grippers
9
6.10
rovers
10
7.90
visitall
4
2.80
depot
10
9,70
goldminer
2.80
satellite
8
8.00
swap
37.80
alfworld
99
66.20
Table 5: Number of correct applicable actions in the Applicability task dataset.
25

---

Task
Complexity
Applicability (App)
O((A)
Progression (Prog)
O(F)
Reachability (Reach)
PSPACE-Come PSPACE-complete PSPACE c-omplet
Action Reachability (AReach)
Validation (Val)
((1)
Justification (Just)
O | FI)
Landmarks (Land)
PSPACH-complets PSPACE-comples
Next Action (NextA)
Table 6: Computational complexity of answer evaluation per task.
KAME:/le-sh-E, [a-zh-t0-9-_j+/
UPAR:*
*)*
\m//
"SPAR:";"
COHSS:""
actton
actior_name: 1PAR NIS (MS KANE) REAR
set: action_name actior_none notion_llitt lon
KE?1
proz_list: ascion_namee (COME action_nansi:
progression_ list: LSPAR piog_lis: RSPAR LSPAR list REPAR [ndax://0-33++00-9114
Figure 8: Grammar used for parsing the model response.
A.5 EXPERIMENTAL SETUP
All our experiments were carried our using temperature for replicability. We leverages LM Evalua- tion Hareess (Gao et al. 2024) framework for our experiments and use default configurations for the experiments. The YAML config file for our experiments is provided in the supplemental material. We highlight the most important hyperparameters below.
We only focused on 2-shot prompting in this work for two reasons: 1. LRMs used in our experiments generate Chain-of- Thought (COT), so specialized prompt is not required for that. The previous work (see Fig. of (Kokel et al. 2025)) did not show much advantage of COT prompts, only in-context examples showed real advantage. We did not include hybrid approaches because the primary goal of this work to propose a challenging benchmark for natural language tasks for Language Models.
num fewshhtt:
generation kwargs:
until:
"(n)ninnn"
"(n'n"
"*s D
"** Question:**" -Q:" do sample false
max gen_toks: 1000
temperature: 0.0
A.6 NEXT ACTION, SPLIT BY DOMAIN
One of the tasks, specifically the new next action task shows a higher than expected accuracy for such computationally hard task. To better understand the phenomena, Table 7 shows the per-domain split. The bolded and underlined values depict the top accuracy values per domain across the tested models. Note, the accuracy is not uniform across domains. Some more complex domains such as depot shows better performance across models than easy domains such as grippers, which hard for all models. There are domains, such logistics and ferry that are hard for some models
26

---

Model
depot goldminer satellite swap alfworld femry logistics blocks grid
floortile grippers rovers
visitall
Mixtral 8x22B
0.4
0.2
0.4
0.8
0.1
0.3
0.4
0.3
0.3
0.1
0.2
0.4
0.3
Llama 3.1 70B
0.6
0.4
0.5
0.7
0.1
0.2
0.4
0.5
0.5
0.4
0.3
0.3
0.5
GPT-4o mini
0.4
0.4
0.0
0.5
0.3
0.5
DeepSeek V3
0.5
0.2
1.0
0.2
0.7
0.8
0.6
0.0
0.1
0.5
0.5
Llama 3.1 405B
0.6
0.4
0.4
1,0
0.4
0.4
0.6
0.2
0.6
0.0
0.3
0.6
0.7
GPT-4o
0.6
0.5
0.4
0.7
0.6
0.7
0.1
0.2
0.8
DeepSeck RI
0.4
0.5
0.2
0.9
0.0
0.4
0.6
0.5
0.4
0.0
0.1
0.2
0.5
ol mini
0.9
0.8
0.5
0.9
0.5
1.0
0.4
0,6
0.9
0.3
0.2
0.4
0.9
ol-preview
0.8
0.9
0.8
0.9
1.0
0.8
0.9
0.8
0.1
0.9
0.8
random (full set)
0.11
0.43
0.04
0.21
0.03
0.19
0.14
0.39
0.36
0.22
0.20
0.26
0.49
Table 7: Accuracy of large size models the next action task, split by domain. Bold entries indicate the best overall model, while the underlined entries indicate the best language model. Last row indicates the ratio of the actions that are correct answers among the applicable actions, the performance of random selector among applicable actions.
polmeer
srop
sgrsce
laggn
Medowwrtd
biclnnork
cooo
Aypert
ctxct
Just
223
(a) Granite 3.1 8B base
(b) Granite 3.1 8B.
(c) Llama 3.1 8B.
Figure Domain-wise accuracy of small size language models.
pirall
Tacc ouand
Town
aPrend
10//0
reach
2kg
(a) DeepSeek coder 33B.
(b) Granite code 34B.
Figure 10: Domain-wise accuracy of small and medium size language models.
and easy for other. There are domains like floortile and alfworld that are very hard for almost all models.
A.7 DOMAIN-WISE ACCURACY OF TESTED MODELS
Figures 9 and 10 show the domain-wise accuracy of tested small and medium language models,
while Figure presents the disain-wise accuracy of tested large language and reasoning models.
27

---

E12347
Expot
AX3
(a) Mixtral 8x22B.
(b) GPT-4o mini
(c) Llama 3.1 70B.
g0l8n
1001
rov2r
alord
Noo Sile
Foorthe
+ prog
Peach
-
(d) GPT-4o.
Llama 3.1 405B.
(f) DeepSeek V3.
pabra
by
escovers
sher
Hoottic
Coartle
Nomdt
Sora
p5g
rede
p130
DeepSeek RI.
(h) ol mini
ol preview.
EveE
Jarry
revers
alloodd
hhord
Toutto
Add Rt
reach
renta
pind)
2017
GPT-OSS 20B.
(k) GPT-OSS 120B.
Figure 11: Domain wise accuracy of large language and reasoning models.
A.8 LESS STRICT EVALUATION
Our evaluation of applicability and progression tasks expect complete correct answers. This is be- cause, partially correct answers in the progression task result in incorrect resulting state, which is
28

---

detrimental to reliable planning. Partially correct applicability task. the answer includes incorrect actions, can result in unsound solutions pro- duced. However, if the answer is incomplete, the result is a loss of completeness, which makes still possible to produce a sound solution. In such cases, we can have a less strict evaluation metric.
somewhat possible only in the action
So in addition the exact match metric, less-strict metric like Jaccard similarity
also be leveraged. Table 8 provide domain-wise comparison of both metrics for the best-performing
model ol prevview.
Domain alfworld blocksworld
Exact Match
Jaccard Score
0
0.20
depot
0.3
0.54
ferry
0.5
0.5
floortile
0.2
0.73
goldminer
0.9
0.9
grid
1
grippers
0
logistics
0.2
0.2
rovers
0.2
0.57
satellite
0.2
0.29
swap
0.3
0.63
visitall
0.9
0.9
Mean
0.44
0.57
Table 8: Comparison of two exact-match metric with less strict metric, Jaccard Similarity, for O1-Preview on Applicability task.
A.9
LIMITATIONS
Our work aims to propose a reliable benchmark the evaluates LLM's ability to reason about action, change and planning. However, there are few limitations work.
Captures subset of planning problems: classical domains closed world, deterministic dynamics, full observability, described in standard planning language PDDL.
Requires specifying the corresponding natural language mapping of facts and actions per domain.
Generation and validation are both computationally challenging and therefore time con- suming. The validation makes use of lenient grammar, resulting possibly capturing wrong part of the answer, when multiple answers are given in one response.
Evaluating generated output hard, while we counted on the model to not produce multiple conflicting answers, LLMs are known to do
The evaluations only measures the final answer and do not evaluate the reasoning process LLMs.
We use same of prompts to evaluate all the LLM. Having different prompts and ap- proaches might result in different performance on the benchmark.
29


Reviews:
[{"review_id": "tNmvRnvFa0", "reviewer": "Reviewer_2qTa", "summary": "The paper introduces ACPBench Hard, a benchmark dataset for evaluating LLMs ability to perform generative reasoning tasks related to automated planning. Building upon the existing ACPBench, the authors create open-ended, generative versions of 7 existing tasks plus one new task. The benchmark spans 13 PDDL planning domains and includes symbolic validators for each task. The authors conduct an extensive empirical evaluation of 15 LLMs and reasoning models, revealing that even state-of-the-art models perform poorly on most tasks, with many scores below 65%.", "questions": "* What would results look like under less strict metrics? \n* What is the dataset size per task? For each task, can you include more information such as some data examples, example input/output, failure cases?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "* The paper addresses a significant problem by requiring generative responses rather than classification, which better reflects real-world planner requirements.\n* The paper tests 15 models across different scales and types, providing empirical coverage\n* The description of different tasks in the paper is clear and structured. The discussion of the computational complexity for each task is thorough.", "weaknesses": "* The evaluation only considers the first answer provided by the model. This might underestimate a model's capabilities if it generates a correct answer later in its output.\n* The model needs to produce all actions’ effects correctly to be scored. This evaluation is strict. Partial credits may be considered as other evaluation metric. \n* The baselines of the evaluation are not comprehensive enough. Only 2-shot prompting is included. No CoT prompting or hybrid approaches with solvers are included. \n* The paper is text heavy. More illustrations can be added to aid understanding. The high level workflow looks simple and clear but is not in the main texts.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "X7E41CxwF9", "reviewer": "Reviewer_UptW", "summary": "This paper introduces ACPBench Hard, a benchmark specifically designed for evaluating the Reasoning about Actions and Change (RAC) capabilities of Large Language Models (LLMs). Compared to existing RAC benchmarks (such as TRAC, ActionReasoningBench, and ACPBench), ACPBench Hard features a richer set of tasks and transforms reasoning tasks into generative questions. Furthermore, the authors designed dedicated symbolic validation mechanisms for each tasks to avoid the uncertainties associated with using LLMs for evaluation. Then, the authors conducted a comprehensive evaluation of 15 LLMs and reasoning models of varying scales using this benchmark. The experimental results clearly demonstrate that even SOTA models perform poorly on these fundamental RAC tasks, indicating that current LLMs are not yet capable of being reliably used as components in symbolic planners or as standalone planners.", "questions": "Q1: There is an inconsistency in task names. Line 381 mentions \"atom reachability\" - does this refer to Task 3 \"reachability\"?\n\nQ2: Using symbolic solvers to verify generative answers usually requires a formalization process. I am curious whether using only a grammar parser is sufficient to accomplish this translation, given the diversity of LLM responses. Do parsing failures occur during evaluation? If so, have you considered adopting LLM-based evaluation as a backup strategy when parsing fails?\n\nQ3: During evaluation, did you set specific temperature parameters for the LLMs, or were default values used throughout?\n\nQ4: NextA is an interesting task. How exactly did you compute the heuristic value h*(s) for states?", "limitations": "", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. Compared to other RAC datasets, the ACPBench Hard dataset features more challenging tasks and provides rigorous formal definitions for each task.\n\n2. The use of symbolic solvers for answer evaluation avoids potential information loss that might occur when relying solely on LLMs for assessment.\n\n3. The paper goes beyond evaluating end-to-end planning capabilities and delves into underlying, atomic-level reasoning. The authors accurately analyze and pinpoint specific reasons for LLM failures in these tasks (for example, LLMs cannot even reliably list all executable actions in a given state).\n\n4. The evaluation is comprehensive, covering models of different sizes, both LLMs and LRMs, as well as open-source and proprietary models. The domains used in the benchmark are also extensive.", "weaknesses": "1. The evaluation employed a 2-shot prompting strategy. It remains unclear whether this prompting approach is optimal for eliciting planning and reasoning capabilities in models. More sophisticated strategies (such as ToT and GoT, SC, etc) might yield different outcomes. Besides, it is not clear whether using examples from the target domain would help.\n\n2. The generative vs. mcq comparison is limited. Figure 4 only compares the GPT-4o model, making it uncertain to determine whether the increased difficulty is a universal phenomenon or specific to certain models.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7xQzWfxCbg", "reviewer": "Reviewer_wXMk", "summary": "This paper introduces ACPBench Hard, a benchmark designed to evaluate LLMs on open-ended questions about planning. It builds upon the prior ACPBench work which only included boolean and multiple-choice questions, with the difference being that this benchmark requires models to generate complete answers that automated planners would produce during the planning process. Specifically, the benchmark includes eight reasoning tasks across thirteen planning domains: applicability, progression, reachability, action reachability, validation, justification, landmarks, and next action. The authors develop symbolic validators for each task and evaluate fifteen models ranging from 8B to 405B parameters, including reasoning models like o1. Their central finding is that even frontier language models perform poorly, with most scoring below 65% on most tasks, indicating substantial gaps in planning reasoning capabilities.", "questions": "1. Concerning natural language generation, how exactly were PDDL problems translated to natural language? I understand you're extending the previous ACPBench, but was this process automated using templates, manually created, or some combination?\n\n2. What hyperparameter values, i.e., temperature and top-p, were used in the experiments? How sensitive are results to different hyperparameter values? Were multiple independent runs conducted to assess variance?\n\n3. Did you experiment with alternative prompting strategies such as explicit CoT reasoning, task decomposition, or providing worked examples for multi-step reasoning?\n\n4. Can you quantify how often the grammar-based parser failed to extract answers versus models providing incorrect answers? Did you manually inspect a sample of parsing failures to ensure the parser is not rejecting valid answers? \n\n5. Can you provide more detailed analysis of why providing PDDL helps? Does it reduce ambiguity, provide structure that models can pattern-match, or serve a different function?", "limitations": "", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper makes an important advance in evaluating the planning/reasoning abilities of LLMs and LRMs by shifting from discriminative to generative evaluation, which more faithfully represents the actual decision-making processes that (symbolic) planners perform. This transition is non-trivial because generative tasks require models to produce answers from large action spaces rather than selecting from pre-curated options, making the benchmark more realistic for assessing practical planning capabilities.\n\nUsing symbolic validators is also a substantial strength of the benchmark. Unlike other approaches that use other LLMs for evaluation (which introduces noise and potential biases), these validators provide deterministic and theoretically grounded correctness verification. The authors thoughtfully discuss computational complexity for both the tasks themselves and their validation procedures, with several tasks being PSPACE-complete.\n\nThe empirical evaluation is comprehensive, testing fifteen models including small (8B), medium (33-34B), large (70B-405B), and reasoning models (o1, DeepSeek R1), providing good coverage of the current model landscape. The inclusion of recent reasoning models is particularly valuable for understanding whether extended inference computation translates to improved planning reasoning.\n\nThe qualitative analysis also provides insights into specific failure modes, such as models recognizing blocks cannot be stacked on themselves but struggling with more subtle applicability constraints, or o1-preview's systematic off-by-one errors in the validation task. These concrete observations are more informative than aggregate statistics alone.\n\nThe investigation of representation formats, i.e., combinations of NL and PDDL descriptions, is a good additional experiment. Maybe not surprisingly, the PDDL+NL representation substantially improves performance, which may have some implications for how planning problems should be presented to LLMs.", "weaknesses": "One of the immediate weaknesses I notice in the paper is on the evaluation side. Namely:\n\n- The main paper lacks details about exact prompts used, model hyperparameters (temperature, top-p,), random seeds, and how many independent runs were conducted. The paper states a maximum of 1,000 tokens was used (4,000 for GPT-OSS models) but does not specify whether models used greedy decoding or sampling with what parameters. Given the stochastic nature of LLMs, these details are essential for reproducibility.\n\n- The paper employs only 2-shot prompting without exploring alternative prompting strategies. Given the complexity of these tasks, this seems limiting. The paper does not investigate whether chain-of-thought prompting, task decomposition, or additional examples might improve performance. The reasoning models presumably use some form of extended reasoning internally, but the regular LLMs were not given explicit instructions to reason step-by-step in the prompts. At least, that's what can be inferred from the main paper. Additionally, the \"lenient grammar-based parser\" that discards non-conforming tokens may reject valid answers expressed in unexpected formats. The paper acknowledges evaluating only the first answer when models might produce multiple, but does not quantify how often parsing failures occur versus genuine incorrect answers.\n\n- The representation experiment reveals that PDDL+NL substantially improves performance (at least for DeepSeek V3). But why does providing PDDL help? Is it because the structured representation reduces ambiguity? Do models pattern-match on PDDL syntax? Does this suggest LLMs are better at parsing structured representations than natural language descriptions? This result might have implications for prompt engineering and practical deployment, meaning that a deeper analysis including ablations and attention visualization will be beneficial (however, one can argue this is beyond the scope of this paper).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Kvr5dyvREG", "reviewer": "Reviewer_Zfe9", "summary": "The paper describes and novel dataset on planning tasks which are supposed to be harder. The paper describes the creation and details the included task. It contains 13 planning task with each 8 examples if I read the paper correctly. They describe that none of the datasets can be solved by the best models and reach about up to 60% . The task are in natural language translated from pddl.", "questions": "1. Could you provide per planning problem 1000 samples? Or is this too much effort in case can you explain why? I think this would be ideal.\n2. It would be nice to try with the latest thinking models using NL and PDDL and evaluate both. Would strengthen the claim that these models can not solve those for some time. \n3. Could you provide the statistics about the models in a table, e.g. how much planning steps in average, how distributed, how many samples, etc.", "limitations": "", "rating": 4, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "1. New and harder planning dataset. \n2. Detailed evaluation on a larger set of models for small to large LLMs.\n3. Detailed analysis of results.", "weaknesses": "The datasets is seems too small per task to obtain good confidence intervals. I would prefer per task much more examples, via the automatic process they describe, you could produce per planning problems thoustands of samples automatically. I would strongly suggetest to provide more. These seem expensive to run but per tokens prices fall and for small models they run the costs a very small. You could define subsets. \n\nThe task should be provide as both NL and PDDL. The models understand PDDL well. NL is not anymore needed. The translation is per template and needs backtranslation for testing.\n\nValmeekam et al. used thinking models and solved many of these task. Blocksworld with 20+ blocks can be now solved by these models. Even Valmeekam used not the latest models of the thinking models now a year ago at Neurisp and the newer once might solve all the provided problems, I guess. The authors could have tried these with GPT-5 or Gemini 2.5 thinking models. These experiments seem missing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)