Classical Planning with LLM-Generated Heuristics: Challenging the State of the Art with Python Code
Authors: Augusto B. Corrêa
André Grahl Pereira
Jendrik Seipp
Venue: NeurIPS 2025 poster ()
Keywords: automated planning
planning
heuristic search
search
Primary area: reinforcement_learning
TL;DR: We use LLMs to create state-of-the-art AI planners.

Abstract: In recent years, large language models (LLMs) have shown remarkable performance in many problems. However, they fail to plan reliably. Specialized attempts to improve their planning capabilities still produce incorrect plans and fail to generalize to larger tasks. Furthermore, LLMs designed for explicit "reasoning" fail to compete with automated planners while increasing computational costs, which reduces one of the advantages of using LLMs. In this paper, we show how to use LLMs to always generate correct plans, even for out-of-distribution tasks of increasing size. For a given planning domain, we ask an LLM to generate several domain-dependent heuristic functions in the form of Python code, evaluate them on a set of training tasks with a greedy best-first search, and choose the best one. The resulting LLM-generated heuristic functions solve substantially more unseen out-of-distribution test tasks than end-to-end LLM planning, particularly for non-reasoning LLMs. Moreover, they also solve many more tasks than state-of-the-art domain-independent heuristics for classical planning, and are competitive with the strongest learning algorithm for domain-dependent planning. These results are impressive given that our implementation is based on a Python planner and the baselines all build upon highly optimized C++ code. In some domains, the LLM-generated heuristics expand fewer states than the baselines, showing that they are not only efficiently computable but also more informative than the state-of-the-art heuristics. Overall, our results show that sampling a set of planning heuristic functions can significantly improve the planning capabilities of LLMs.

Classical Planning with LLM-Generated Heuristics: Challenging the State of the Art with Python Code
Augusto B. Corrêa University of Oxford United Kingdom
André Pereira
Jendrik Seipp Linköping University Sweden
Federal University of Rio Grande do Sul Brazil
Abstract
In recent years, large language models (LLMs) have shown remarkable perfor- mance in many problems. However, they fail to plan reliably. Specialized attempts improve their planning capabilities still produce incorrect plans and fail gen- eralize to larger tasks. Furthermore, L.MSs designed for explicit "reasoning" fail compete with automated planners while increasing computational costs, which reduces one of the advantages of using LLMs. In this paper, we show how to use LLMs always generate correct plans, even for out-of-distribution tasks increasing size. For a given planning domain, we ask an LLM to generate several domain- -eeendde heuristic functions in the form of Python code, evaluate them on a set of training tasks with a greedy best-first search, and choose the best one. The resulting LLM-generated heuristic functions solve substantially more unseen out-of-distribution test tasks than end-to-end LLM planning, particularly for non- reasoning L.Ms. Moreover, they also solve many more tasks than state-of-the-an domain-independee heuristics for classical planning, and are competitive with the strongest learning algorithm for domain-dependent planning. These results are impressive given that our implementation is based on Python planner and the baselines all build upon highly optimized C++ code. some domains, the LLM-generated heuristics expand fewer states than the baselines, showing that they are not only efficiently computable but also more informative than the state-of -he-he- art heuristics. Overall, results show that sampling set of planning heuristic functions can significantly improve the planning capabilities of LLMs.
Introduction
Classical planning is a fundamental problem in Artificial Intelligence (AI), with applications ranging from robotics to computational chemistry (25). Given the initial state of the world, a description of the goal, and a set of deterministic actions that can be executed in a fully-observable environment, the task is to find sequence of actions transforming the initial state into state that satisfies the goal. Nowadays, most classical planners rely on heuristic search algorithms to find plans 39 35 55 45 75 65). The efficiency of these planners depends on the quality of the heuristic functions that estimate the cost of reaching the goal from a given state. Traditionally, these heuristics have been either domain independent, offering generality at the expense of accuracy; manually crafted for specific domains, requiring significant human effort and expertise; or learned on per-domain basis, incurring costs for training new heuristic whenever we want to use a new domain.
In this work, we propose a new way of producing heuristics: we use LLMs to automatically generate domain-dependent heuristic functions for classical planning. Our hypothesis that LLMs, given sufficient context and examples, can generate heuristic functions that outperform generic domain- independent heuristics.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Problem Prompt PDDL Bles; esample domains; planner code; checklist
instructios::
LLM
Heuristic
Training PDDL Tasks
Selected Heuristic (e.g.
Heuristic Pr..
Step Generation
Step Evaluation
Step 3: Selection best heuristic based on performance on the truining set
Generati mullipp
Run GBBS with each candidate
candiciate houristic functions
heuristic on a set of training tasks
Figure I:
Our pipeline for generating domain domain-dependent heuristics with LLMs: we prompt the LLM times to generate candidate heuristics, evaluate each of these heuristics set of training tasks and choose the strongest one.
Our overall pipeline is much simpler than previous work: we simply pass to an LLM the domain description, example planning tasks, example comain-dependemt heuristics for other domains, and the relevant planner code. Then request that the LLM generates a hcuristic for the given domain. We specifically request that the LLM generates the code, in Python, to compute the heuristic. We execute the same prompt times obtain a pool of candidate heuristics, evaluate each of them a training set, and select the best one. Figure shows the overall pipeline. This discards the necessity of back-and-forth communication between the planner and the LLM, making the overall procedure straightforward. Our approach generates a constant number of heuristics per domain, and then uses the selected heuristic for any task of this domain. This drastically reduces the costs for LLM inference compared to invoking an I.LM for each task in a domain.
We implement our pipeline top of Pyperplan [ proof of concept, and then evaluate the generated heuristics on the domains of the Learning Track the International Planning Competition (IPC) 2023 773. The LLM-generated heuristic functions solve significantly more tasks than LLMs prompted to generate plans end-to-end, and this difference is especially pronounced for non-reasoning LLMs. The heuristics also outperform state-of-the-as heuristies, such as AFF 39 in terms of solved tasks and are competitive in the number of required state expansions. Although Pyperplan is much due to its Python implementation,
slower than oftte-of-theaat planners B5 45 63
method still outperforms FF even when using the standard C++ implementation available Fast Downward [5], well the strongest learning-haid based domain-dependent planner [11, which is also built Fast Downward. This is an impressive result, as this implementation cornerstone of most of the state-of-the-arr planners in the literature.
2
Background
We consider classical planning, where single agent applies deterministic actions in fully- observable, discrete environment. Classical planning tasks are usually described using the Planning Domain Definition Language (PDDL) [47 33). To understand work, informal description of fragment of PDDL is sufficient. We introduce it alongside examples from a simple Logistics domain.
A PDDL task consists of set of objects (e.g., representing vehicles, packages, locations); a set of predicates representing relations between these objects (e.g., using the at predicate, the ground atom (at carl city2) represents that object car1 is at city2); a set of actions that change the relations (e.g., driving car changes its location); an initial state which a set of ground atoms (e.g., where all packages and vehicles are initially and which locations are connected) and a goal description that lists the ground atoms that must hold at the end of a plan (c.g., the desired locations of all packages). Applying an action changes the current state of the environment by removing or adding ground atoms. PDDL tasks are commonly separated into a domain and an task part, where the domain part holds the common actions and predicates, while the task part describes the specific objects, initial state and the goal. The two parts are typically represented as two separate files.
The objective of a planner is to find sequence of actions, called plan, that leads from the initial state to state where goal atoms hold. Most planners nowadays use state-space search to find plan. The search is usually guided by a heuristic function h which maps each state s to value h(s)) E (R oc that estimates the cost reaching a goal state from [TT] heuristic search
algorithms-aee such as A 32), weighted-A' [52] and greedy best-first search [19 this heuristic

---

guides the search towards promising states and thereby reduces the search effort. The performance of planner is heavily influenced by the accuracy and computational efficiency of the heuristic function.
In our work, we assume that all actions have cost one, and we consider satisficing planning, where any plan is acceptable, irrespective of its length cost. We focus on planners that greedy best-first search (GBFS), While there are lots of search improvements that one could evaluate on top of GBFS (e.g.. 39 45 54 57 we limit ourselves to "pure" GBFS planners as this is the most commonly used
version in the classical planning literature [e.g.. 18 22
3 Using LLMs to Generate Heuristics for Classical Planning
In our pipeline, we give as input to an LLM the PDDL description of our target domain together with some additional information (described below). Then we ask the LLM for a domain-dependent heuristic function for the given domain, implemented in Python, which we then inject into the Pyperplan planner [T] We choose Python because LLMs generate correct code for Python more often than for other languages [44), and because code injection is simple in Python.
We send n identical requests to the LLM with the same prompt, collect all returned heuristic functions .i..... hn, and then evaluate them on the training tasks. Then, we automatically select the best heuristic Abs E {hi,.... hn and use it in the test set evaluation (see below for details on this selection). [Toows the graphical representation of our method.
When used for planning, LLMs often produce incorrect plans 77 80). In contrast, our pipeline ensures that all found plans correct: the greedy best-first search algorithm only produces correct plans, and the heuristic created by the LLM only influences how efficiently such a solution is found.
Our prompt instructs the LLM to generate a domain-dependent heuristic for a given domain D and provides some advice, such as that the heuristic should minimize the number of expanded states and balance accuracy with computational efficiency. It then includes the following file contents:
Prompt
1. the PDDL domain file of domain D
2. the smallest and the largest PDDL tasks of domain D in the training set
3. for each of the two example domains Gripper and Logistics [47]: the PDDL domain file, task file and a domain -omain-deeendent heuristic implemented in Pyperplan
4. an example of how a state of domain D is represented in Pyperplan
5. example of how the static information of domain D is represented in Pyperplan
6. the Python code from Pyperplan for representing planning task and an action
7. a checklist of common pitfalls
Items 1 and 2 provide the context about the domain D that we are interested in. Item 3 illustrates the Python implementation of nomain-dependee heuristics using Pyperplan's 's interface. For Gripper, we provide a Python function computing the perfect heuristic as input, while for Logistics, we encode the simple "single visit and load/unload counting heuristic" by Paul et al. [50]. These functions show the LLM what a heuristic could do and illustrate how to manipulate the available data. Items 4-6 give more context about Pyperplan. Last, the checklist consists of tips based on our own observations of L.L. responses. Appendix A shows the complete prompt used for the Blocksworld domain [47].
Heuristic Function Selection We prompt the model n times with the input above to generate n heuristics. For each task in the training set, we then run the n heuristics within GBFS for at most five minutes. Then, we select the heuristic that solves the largest number of tasks from the training set. If there is tie, choose the minimizing the accumulated agile score over the training set. We use the term training set to follow IPC terminology. However, our approach does not involve any training. We merely use this set of tasks to evaluate the generated heuristics and select the best one.
'The agile score is common metric from IPCs and awards heuristics that lead finding plans quickly. the search needs less than second, then the score is 1. If the search runs out of time (in our case, 300 seconds) the score is O. Intermediate values are interpolated with the logarithmic function log(300) time (in seconds) of the search. The accumulated score is the over all training tasks.
log(t) where is the run
3

---

Table I: Size of training and testing tasks for each domain based on their main parameters. Parameters by domain: n blocks in Blocksworld, e children in Childsnack, t tiles in Floortile, passengers in Miconic, r rovers in Rovers, b boxes in Sokoban, & spanners in Spanner, and v vehicles in Transport.
Domain
Training
Testing
Blocksworld
n E [2. 29
n [5, 488
Childsnack
CE [1, 10
c C [4, 292
Floortile
LE [2.30]
E [12, 980
Miconic
E 10
P (8,
Rovers
r [1,4
r E [1,30]
Sokoban
be [1,4
b E 79.
Spanner
8 10
n E [1, 487
Transport
[1,7
E [3.50]
4 Experimental Results
For running our experiments, we use Downward Lab [64 on AMD 7742 processors running at 2.25 GHz. As mentioned, we Pyperplan [1] for all our configurations. This allows to evaluate the different heuristics (domain-independent and .LL--generated ones) in a single framework. We use PyPy 7.3.9 to run Pyperplan, as it proved to be slightly faster than CPython. The source code and experimental data are publicly available online [4].
In the training phase, we limit each run to 5 minutes and 8 GiB. In the testing phase, each run is limited to 30 minutes and 8 GiB, following recent International Planning Competitions [73 To diversify the pool of generated heuristics, we increase the temperature parameter of the models to 1.0
We use the domains and training/test tasks from the IPC 2023 Learning Track to generate and evaluate heuristics. However, since Pyperplan does not support two of these ten domains (Ferry and Satellite), we exclude them from our experiments. The resulting test set has 90 tasks for each of the 8 domains. The distribution of tasks in the training and test sets differs a lot: the test tasks are generally much larger than the training ones. Table [ shows the distributions of parameters. In addition to size differences, tasks may also vary in structure. For example, Sokoban mazes can arranged in different layouts. The full details about the task sets are available online (62).
We also include experiments on novel domains that were not seen during the training of the LLMs. This helps us to identify whether our method is robust to new domains, and also addresses the potential concern that the LLMs are retrieving memorized heuristics instead of generating them by reasoning about the domain description.
Generating Heuristics To generate the heuristics, we two families of LLMs: Gemini 27 28 with the models Gemini 2.0 Flash (stable release 001) and Gemini 2.0 Flash Thinking (version 01 01-21); and DeepSeek 17). with the models DeepSeek V3 (version 0324), DeepSeck R1 Distill Qwen 14B, and DeepSeek R1. We include the distilled version to Qwen 14B [3] to evaluate the impact of smaller models in our pipeline. We had free API access Gemini 2.0 models and ran R1 Distill locally. The total API costs for generating all V3 and RI heuristics were $0.25 and $6. (USD).
We prompt the LLM times and receive different heuristic functions. But how large should be? We ran an experiment with Gemini 2.0 Flash to evaluate this. For domains, the biggest increase in average coverage (i.e., number of solved tasks) results from going from 1 to 5 heuristics, and after that, we see diminishing returns. In six of the eight domains, using π = 25 is enough to consistently find heuristics solving the entire training set. In two domains, Childsnack and Floortile, coverage increased for n > 25, but only slightly. Due to these results, we set n = 25 for all experiments below.
"W used a disjoint set of ten domains from the Autoscale benchmark set [76] for exploratory experiments while developing our pipeline. This split allowed us to test different prompts, hyperparameters, and models without the risk of overtitting to the IPC 2023 benchmark causing some LLM APIs to cache prompts.

---

Table Number of solved tasks when using LLMs for end-to-end planning compared a greedy best-fire search within Pyperplan using the blind heuristic h h and our LLM LLM-generated generated heuristics.
End-to-End
Pyperplan
Gemini 2.0
DeepSeek
Gemini 2.0
DeepSeek
Domain
Think.
V3
R1
h
FF
Think.
V3
R1
D.
RI
Blocksworld (90)
2
40
2
17
24
35
37
45
34
66
Childsnack (90)
3
59
12
40
9
17
32
14
55
16
22
Floortile (90)
0
0
8
4
Miconic (90)
6
21
10
24
30
74
90
88
64
30
90
Rovers (90)
0
0
10
12
28
32
39
34
32
32
Sokoban (90)
14
0
8
31
32
24
30
Spanner (90)
6
39
21
47
30
30
30
30
69
30
70
Transport (90)
24
3
28
29
57
45
59
Sum (720)
19
202
48
174
120
243
296
305
343
214
373
Comparisons to Domain-Indeeenden Heuristics in Pyperplan We now compare the LLM- generated heuristics to two baselines: breadth-firs search (h"), which uses no heuristic guidance and GBFS with the h heuristic [39]. which is of the most commonly used heuristics for satisficing planning [e.g., 13 26
These two baselines are also implemented in Pyperplan, which allows evaluate exactly the impact of the generated heuristics. As the right part of Table shows, all -.L--gerrrtted heuristics outperform
and FFF regarding total coverage, except for the distilled version of DeepSeek RI. In all but one domain (Floortile), the best performing heuristic is an LLM-generated one.
DeepSeek RI heuristics have the highest coverage with 373 solved tasks, while DeepSeek V3 places second with 343 solved tasks. Gemini 2.0 Flash Thinking solves 68 fewer tasks (total 305). The best baseline FF solves only 234 tasks. The selected DeepSeek RI heuristic is particularly impressive in the Blocksworld domain, where solves almost 40% more tasks as the second best heuristic (DeepSeek V3).
The non-reasoning models Gemini 2.0 Flash and DeepSeek V3 perform worse than their reasoning counterparts. DeepSeek R1 Distill Qwen 14B heuristics the only LLM-based models that underperform in comparison to FF However, this is mostly due to low coverage in the Miconic domain. In fact, DeepSeek R1 Distill Qwen 14B outperforms FF in 3 domains, while being outperformed in This shows that the smaller distilled models might be competitive with existing heuristics in some domains.
Figure 2a compares the plan lengths obtained with FF and the heuristics generated by DeepSeek RI. In general, the two methods yield plans with similar lengths. The only domains where one approach has a clear edge are Blocksworld, where the DeepSeek RI plans are consistently shorter, and Míconic, where DeepSeek R1 plans get longer than FF plans as the tasks get larger.
Last, we compare the informativeness of the traditional and the LLM-generated heuristics in- specting the number of states expanded during the search. Ideally, a heuristic only expands states traversed by plan. Figure 2b compares expansions between FF and DeepSeek RI heuristics. The results vary by domain: DeepSeck R1 has an edge in Blocksworld, Spanner, Transport and in most of the Childsnack tasks, whereas h FF is more informative Floortile, Rovers and Sokoban. In all the domains where DeepSeek RI expands fewer states than hFF, it also solves many more tasks than F.F On the flip side, the only domain where JFF expands fewer states and solves many more tasks than DeepSeek R1 is Floortile. In the Rovers domain, DeepSeek RI has higher coverage than AFF while Sokoban FF solves only two more tasks. This indicates that despite being less informed in these two domains, the heuristics generated by DeepSeek R1 perform better because they are more efficient to compute.
'This is identical to running GBFS with the blind heuristic Ao, where (((s) = 0 iff is goal state and n (s) = otherwise.
5

---

300
uns.
XX XX
Blocksworld
R (DeepSeek R1)
10
Childsnack
200
X Floortile
10a
Miconic
A
Rovers
100
103
Sokoban
Spanner
10a
Transport
0
100
200
300
10
10a
10
107 uns.
RF
hFF
(a) Plan length.
(b) Expansions.
Figure 2: Comparison of plan length and expansions for FF and the heuristics generated by DeepSeek
R1. We only show plan lengths up to 300 (only plans in Miconic exceed this limit).
Comparisons to End-to-End Plan Generation with LLMs We also analyze the end-to-end plan generation capabilities of LLMs. We prompt the LLMs with general instructions, the PDDL files for the domain and the specific task, and a checklist of common pitfalls. To guide the model, the prompt also includes two examples: PDDL task and PDDL domain for Gripper and Logistics (the same ones used in our prompt to generate heuristics), along with a complete optimal plan for each of the two tasks. The LLM is then asked to generate plan, which is subsequently validated using the automated plan validation tool VAL [40]. Appendix Shows an example of our end-to-end prompt for the smallest Blocksworld task in our test set.
The left part of Table [ooles shows that DeepSeek RI solves 174 tasks and Gemini 2.0 Flash Thinking solves 202 tasks, both outperforming GBFS with the blind heuristic (h") in Pyperplan. However, both LLMS solve fewer tasks than
--g-ereee heuristics in Pyperplan, including the small DeepSeek R1 Distill Qwen 14B. With the end-to-end plan generation, the cost of using the LLMs also increases significantly. The cost for using V3 increases from $0.25 to $2.79, while the cost of increases from $6.12 12 to $13.62. The end-to-end experiment requires 720 LLMM calls (one for each of the 90 tasks across domains), compared to 200 calls when generating 25 heuristics per domain. In the case of DeepSeek RI, the end-to-end experiment takes several days to complete, while the heuristics can be generated a few hours. Furthermore, heuristics are reusable for solving new tasks, versatile and cost-effective approach.
whereas end-to-end plans are not, making heuristics
We now compare the performance of the same LLM when used to solve two different problems: end- to-end planning versus heuristic generation. For the reasoning models Gemini 2.0 Flash Thinking and DeepSeek RI, using them for heuristic generation increases the number of solved tasks from 202 and 174 (end-to-end) to 305 and 373 (heuristic generation), respectively. The increase in total coverage is even more significant for non-reasoning models: with Gemini 2.0 Flash, the number of solved tasks jumps from 19 (end-to-end) to 296 (heuristic generation), and with DeepSeek V3 it increases from 48 (end-to-end) to 343 (heuristic generation). This shows that our heuristic generation approach can bridge the performance gap between expensive reasoning models and cheaper non-reasoning ones, while also increasing the overall number of solved tasks.
Comparison to State-of-the-Art Heuristics Implemented in C++ Our experimental setup has an obvious caveat: we are using Pyperplan, which is an educational, unoptimized Python planner, while all state-of-thh-aar planners are implemented in compiled languages such as C++. For example,
the winners of all tracks of the last IPC, 2023, are implemented in C++ 773 Moreover, all of these planners are implemented on top of the Fast Downward planning system Python is slower than C++ and uses more memory, we compare our best method, GBFS Pyperplan using DeepSeek RI heuristics, to GBFS in Fast Downward using the many satisficing heuristics implemented in the planner: the goal-count heuristic /, GC 23]; the landmark count heuristic lme
35 Even though
(56] : the C++ implementation of the FF heuristic FF
39 the context-enhanced additive heuristic
pes [36]: the causal graph heuristic s 34 and the additive heuristic add (6) We also compare WLF [T]] which uses Gaussian Process Regression
to GPR
(53] over features derived with the Weisfeiler-

---

Table Coverage for different heuristics implemented in Fast Downward, and in Pyperplan. Heuris- ties h V3 and h indicate the heuristics generated by DeepSeek V3 and by DeepSeek RI.
Fast Downward (C++)
Pyperplan
Domain
GCC
Ime
FF
heea
h
h
h
WLF GGP
hFF
h. V3
hR1
Blocksworld (90)
32
39
27
40
34
44
72
24
45
66
Childsnack (90)
23
13
25
29
29
29
31
17
55
22
Floortile (90)
12
10
14
2
10
4
Miconic (90)
90
90
90
79
90
90
90
74
64
90
Rovers (90)
38
41
34
36
39
33
37
28
34
32
Sokoban (90)
42
43
36
33
35
33
38
31
31
30
Spanner (90)
30
30
30
30
30
30
70
Transport (90)
36
36
41
49
54
51
28
29
42
59
Sum (720)
294
295
295
306
318
324
371
243
343
373
Leman algorithm 669 to learn domain--ependent heuristics, and is considered the state-of-the-art in classical planning for heuristic learning. /GP is also implemented on top of Fast Downward.
From now on, denote the heuristics generated by DeepSeek V3 as h V3 and the ones by DeepSeek RI as h RI, Table shows that GBFS in Pyperplan with v3 and with h RI solves more tasks in total than any of the traditional Fast Downward hearistics. Moreover, R is also competitive with the suute-of-the-ary WLF /GPR, and achieves slightly higher total coverage. This is quite an unexpected engineered and receives little attention compared to Fast Downward.
result, Pyperplan is It indicates that the heuristics generated by DeepSeck R1 are indeed powerful. being capable of surpassing the performance gap between Python and C++ implementations. Additionally, shows that even the non-reasoning model DeepSeek V3 can outperform classical planners with our method.
Ablation Study We now analyze the impact of the different components in our prompt in an ablation study. For this, we use Gemini 2.0 Flash Thinking to generate 25 heuristics for several variants of our prompt, each of which alters or removes single component of the original prompt. To reduce the effects of randomness, we run all generated heuristics on the test set, instead of selecting only the single best heuristic. We limit each GBFS run in this experiment to minutes.
Table 4 shows the results. For the first ablation (second column in the table), we replace the long instructions at the beginning of the prompt by simple request generate heuristic function, omitting details such as the request to minimize expansions. For the "Heuristics" ablation, we replace the provided domain-dependent example heuristies with domain-independern heuristics available in Pyperplan, namely the goal-count heuristic and four heuristics based on delete-relaxatin I For all other ablations, we remove the corresponding component from the prompt.
Comparing the heuristics with the best coverage score among all ablations, we see that the original prompt (solving 423 tasks) outperforms all other ablations. This score is 38.7% higher than the one obtained by using our method of selecting heuristics based on performance on the training set (see Table 2). and it even surpasses RR This shows that while enough to outperform ffte-of-the--as art planners, is still not the optimal selection strategy. We leave the challenge of devising better selection strategies for future work.
heuristic selection method is good
Focusing on the worst possible coverage and the average coverage, our original prompt performs worse than other ablations. This result is be expected: as our method aims to have very diverse pool by generating multiple heuristics at a high temperature, we expect a great variance in performance. This is supported by the large standard deviation in results. To obtain more consistent results, one could simply use a lower temperature, for example. However, this is not desirable: it is much better to have single well-performing heuristic than several average ones.
'We do so because completely removing the example heuristics yields a coverage of 0 for all generated heuristics in all domains.
7

---

Table 4: Ablation study the impact of different prompt components using Gemini 2.0 Flash Thinking. Components are ordered according to the original prompt. The symbol "-" indicates that the component removed, and the symbol "="" indicates that the component replaced with weaker version (see text for details). A failed heuristic is a heuristic that solves no tasks.
Original Prompt
IIsttucctonn
PDDL Domain
PDDL Tasks
Heuristics
State Repr.
Statie Repr.
Pyperplan Code
-Checklist
Best Coverage
423
359
368
401
404
402
404
401
382
Worst Coverage
114
138
118
90
126
133
92
110
63
Avg. Coverage
267.0
242.5
237.3
261.5
263.2
253.7
243.8
270.0
260.0
Std. Deviation
+94.3
+.596
+70.4
+86.8
+87.3
+85.0
+95.0
-9744
+87.8
Failed Heuristics
64
57
42
68
97
For average coverage, we exclude heuristics that fail by crashing or not solving any task in our analysis. In this analysis, most of the components of our prompt are beneficial, with the most impactful component being the PDDL domain description. The only component whose removal actually slightly increases the average coverage is the Pyperplan code. However, its removal also increases the number of heuristies (out of 200) that fail by almost 50%. These results show that all prompt components are important for generating high-quality heuristics.
Examples of M-M-Grrrrteed Heuristic Functions We illustrate the heuristic functions generated by DeepSeek RI using Blocksworld and Spanner (see Appendix B). Both domains have polynomial algorithms [30]. In Blocksworld, n blocks are rearranged by moving blocks from stacks. The selected the heuristic value plus 2 for each block B on top of A. using an auxiliary function for stack traversal. In Spanner, an agent traverses one-way corridor to pick spanners (each used once) and tighten n nuts; moving without a required spanner can lead to an unsolvable state. The Spanner heuristic greedily assigns the closest available spanner to each loose nut. The cost calculation depends on whether the spanner is already picked up (agent-to-nur distance 1) or not (agent-to-spanner spanner-to-nut distances + 2), with large penalty for unassigned nuts. This heuristic precomputes all-pairs shortest paths using breadth-first search during initialization. We describe and analyze the generated heuristics for the remaining domains Appendix B
heuristic identifies misplaced goal blocks A, adding
Memorization vs. Reasoning verify whether our method robust to new domains, we run three additional experiments testing if the LLMs retrieve memorized heuristics reason over the provided PDDL domain. Each experiment introduces a new PDDL domain.
We begin with a qualitative experiment: a variant of the Spanner domain. In the original Spanner domain, an agent traverses one-way corridor toward a gate while picking up spanners. It must tighten n nuts to open the gate, and spanners break after single use. Consequently, the agent must collect at least n spanners. In this variant, spanners no longer break after use. If the LLM merely recalled standard Spanner heuristic, it would likely ignore this change and produce longer plans. Instead, the generated heuristic adapts to the new semantics. The best LLM-ggnerated heuristic perfect for this modified domain, yielding optimal plan lengths for all states. This suggests the L.M reasoned about the given domain rather than retrieving a memorized solution.
Next, we obfuscate Blocksworid following Valmeekam et al. [78): all symbols (action names, predi- cate symbols, objects) are renamed to random strings. We refer to this as Obfuscated Blocksworld. In this experiment, h FF (in Fast Downward) solves a similar number of tasks in both versions, 27 for Blocksworld and 28 for Obfuscated Blocksworid. This is expected, as FF does not rely on the semantics of the PDDL names. In contrast, RI (in Pyperplan) solves 66 tasks in Blocksworld but only in Obfuscated Blocksworld. This indicates that while semantic cues from the PDDL names are useful, the L.M can still reason about the domain's 's logical structure without token semantics. We note that this is a highly adversarial setting for I.MMs, which are trained to exploit token semantics rather than operate on random identifiers.
8

---

Finally, we use a completely new domain, Rod- Rod-Rings, which has not been released online nor exposed to an LLM. The domain features sticks with stacks of rings and a single "held" ring. Two moves are allowed: (a) place the held ring at the bottom of a stick (swapping with the current top ring), or (b) place the held ring at the top of stick (swapping with the bottom ring). The goal is to arrange specified rings on specified sticks in defined order. To avoid leakage, we use an OpenAl model (o3) via their API for this experiment. For BoddRRnng,, /13 guiding a GBFS in Pyperplan solves 58 tasks, nearly matching Fast Downward with h (59 tasks) This suggests the LLM reasons about this unseen domain.
Together, these three experiments indicate that the success of our method is due to the LLMs' ability to generate domain-dependent heuristic functions by reasoning about the logical structure of the domain.
5 Related Work
The combination of planning and learning to create heuristic functions has a long tradition [6
12] 660 22.. There are two main paradigms for learning heuristic functions in classical planning: [68 [7] [I]. In this paper, we consider the
task dusk-dependent (20 21 4 and domain-dependen second paradigm. Currently, the strongest approach in domain-dependent heuristic learning is GGPPR
11. which we compare to above.
Recently, LLMs entered the picture. Yet, Valmeekam et al. 778 show that LLMs cannot reliably solve even small classical planning tasks when used for end-to-end plan generation. Moreover, techniques such as supervised fine-tuning and chain-of-thought (43 fail to generalize to outrof-distribution tasks 5 72). This holds even when using more advanced prompting techniques such as Tree of Thoughts 81 or Algorithm of Thoughts (AoT) [66]. While the strongest variant of this line of work, AoT+ [67]. finds valid plans for up to 82% of the tasks in their Blocksworld benchmark set, the largest task in their set only has 5 blocks (78). In contrast, our RRl heuristic solves tasks with up to 216 blocks and never yields incorrect plans. As seen in our experiments, even LLMs explicitly designed for reasoning tasks are not competitive with state-of- ofie--ff-the -teth-rrt planners.
Nonetheless, Rossetti al. (59) and Huang et al. 41 show that LLMs trained to plan can achieve competitive performance when training and test sets share the same distribution. Furthermore, LLMs can also help to solve classical planning tasks when combined with other techniques. For example, there is an extensive body of work exploring the potential of LLMs to convert problems described in natural language into PDDL tasks [c.g., 29 48 46).
The most closely related approaches to ours are those that use LLMs to generate code for solving planning tasks. Katz et al. (42) highlight the high computational cost of using LLMs for end-to-end plan generation, particularly when multiple inferences are required. They propose to use LLMs to generate Python code for successor generation and goal testing, which are then used with standard search algorithms. While more efficient than end-to-end LLM planning. their method requires human feedback for incorrect code and is limited to small tasks due to its reliance on uninformed search. Our approach could address this scalability issue by providing heuristic for an informed search algorithm.
Silver et al. (70) also use LLMs to generate Python code for solving classical planning tasks. However, they focus on generalized planning, where the aim is find a strategy that efficiently solves any task of a given domain. In their approach, an LLM generates a "simple" Python program that does not rely on search. The key difference to our approach is that they address different problem: there are many planning domains, such as the Sokoban domain we use above, for which no simple strategy exists to efficiently produce plans. For such domains, heuristic functions can be useful.
The work by Tuisoy et al. 77 is the most similar to ours, and we draw inspiration from their work. They also use L.MMs to generate heuristic function code for automated planning, though, their focus is on numeric planning. Their approach differs from ours in three main ways. First, they require a manual translation of each PDDL domain into Rust, including the implementation of successor generator and a goal test. The cost of translating domains to Rust prevents easy comparisons on all IPC domains. In contrast, our approach generates heuristies directly from the PDDL description with the resulting code integrated into an off-the-shell planner. Second, their heuristics are task dependen,,,,,,
OOn the eight IPC 2023 domains, 03 heuristics solve 354 tasks, 19 fewer than l (373 tasks).

---

requiring new LLM inferences for each task, while ours are domain dependent and reusable, reducing costs. Finally, while their approach outperforms all domain comain-independern heuristics they compare against, their -.L--genrrtedd heuristics result in fewer expansions for only one task. This suggests that while their heuristics may be computationally faster, they are not necessarily more informative. In our experiments, the L.L--generate heuristics are often more informative than the traditional domain-independent ones.
Beyond PDDL planning, Romera-Paredes et al. 588 use search in function space to solve combina- torial problems. Their algorithm, FunSearch, samples different initial programs, similar our set of candidate heuristics. However, FunSearch feeds the best initial candidates back into the LLM to improve them. contrast, our pipeline never feeds the functions back into the LLM. Although our results are already positive, this feedback loop could further strengthen our results.
6 Limitations
Our approach, while effective, has limitations. One such limitation is its dependency on a formal PDDL description. This dependence makes our method less general than end-to-end LLM planning approaches that can use natural language. However, recent approaches translate natural language into PDDL represettttoo [e.g.. 24 [4, and can bridge this gap.
A second limitation is that our method, which selects the heuristic, is itself heuristic. This selection does not guarantee that the chosen heuristic generalizes the out-of-disrrbution test set. However, our empirical results indicate that the selected heuristic consistently outperforms other approaches, indicating its robustness.
The effectiveness our methods also depends on multi-comppnent prompt. Our ablation study confirmed that while the method is robust, the best performance indeed requires all components of the prompt.
Finally, our current implementation is a proof-of-concept that uses Pyperplan, an educational planner which is significantly slower and less memory-efficient than state-of-the-art C++ planners like Fast Downward. This implementation difference means that C++ implementation would be necessary to conduct a direct performance comparison and verify the full potential of the L.LM-generated heuristics. For example, Appendix (Errnndxx[sshwwww shows that Fast Downward expands up to 669 times more states per second than Pyperplan in certain domains.
7 Conclusions
In this paper, we show how to use LLMs to generate domain-dependent hcuristic functions for classical planning domains. Our approach uses LLMs to produce pool of candidate heuristics, which we then evaluate on a training set in order to choose the best heuristic from the pool. The selected heuristic is then used to solve unseen out-of-distributio test tasks.
We provide proof- concccept implementation of this pipeline in Pyperplan, an educational classical planner written in Python. We show that our LLM-generated heuristics outperform directly using LLMs end-to-end prompted to produce plans. This difference is particularly noticeable when using non-reasoning I.IMss. Comparing the Python-based heuristics, we see that our I.L L.L--genertted heuristics outperform state-of-the-a domain- independent hcuristics in most of the domains of our benchmark set. In particular, heuristics generated by reasoning LLMs such as DeepSeek R1 show significant improvement compared to the domain- induenneindeeedeent heuristic.
We show that Pyperplan equipped with the heuristics from DeepSeek V3 (hv3) and DeepSeek R1 RI outperform heuristics implemented in Fast Downward [35], a ofate-of-the-ar planner written in C++. Moreover, RI is also competitive with WLF [1], the state-of-the af- in heuristic learning for classical planning implemented on top of Fast Downward. These results are surprising, as Pyperplan is much less optimized than Fast Downward, and DeepSeek R1 is not trained for a specific domain, while & WLF is. Our results show the potential of LLM -eeeerrtd heuristics in classical planning as an efficient and effective approach to improve the planning capabilities of LLMs.
GPP
10

---

Acknowledgments
We thank Elliot Gestrin for designing the Rod-Rings domain, and Malte Helmert for giving us access to the cluster of the Al group at the University of Basel.
Jendrik Seipp was supported by the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation. André G. Pereira acknowledges support from FAPERGS with project 21/2551 11/2551-0000741-9 This study was financed in part by the Coorlenação de Aperfeiçoamento de Pessoal de Nivel Superior - Brasil (CAPES) Finance Code 001.
References
[1] Yusra Alkhazraji, Matthias Frorath, Markus Grützner, Malte Helmert, Thomas Liebetraut, Robert Mattmüller, Manuela Ortlicb, Jendrik Seipp. Tobias Springenberg, Philip Stahl, and Jan Wülfing. Pyperplan. hhtpps: //otps://oo... wttp://o.........//ooooooooo
2020.
[2] Shahab J. Arfaee, Sandra Zilles, and Robert C. Holte. Learning heuristic functions for large state spaces. Artificial Intelligence, 175:2075-2098, 2011.
[3] Jinze Bai, Shuai Bai, Yunfei Chu, Zeyu Cui, Kai Dang, Xiaodong Deng. Yang Fan, Wenbin Ge, Yu Han, Fei Huang, Binyuan Hui, Luo Ji, Mei Li, Junyang Lin, Runji Lin, Dayiheng Liu, Gao Liu, Chengqiang Lu, Keming Lu, Jianxin Ma, Rui Men, Xingzhang Ren, Xuancheng Ren, Chuanqi Tan, Sinan Tan, Jianhong Tu, Peng Wang. Shijie Wang. Wei Wang. Shengguang Wu, Benfeng Xu, Jin Xu, An Yang, Hao Yang, Jian Yang, Shusheng Yang, Yang Yao, Bowen Yu, Hongyi Yuan, Zheng Yuan, Jianwei Zhang, Xingxuan Zhang, Yichang Zhang. Zhenru Zhang, Chang Zhou, Jingren Zhou, Xiaohuan Zhou, and Tianhang Zhu. Qwen technical report. [cs.Cl.]. 2023.
arXiv:2309. 166699
[4] Rafael V Bettker, Pedro Minini, André G Pereira, and Marcus Ritt. Understanding sample generation strategies for learning heuristic functions in classical planning. Journal of Artificial Intelligence Research, 80:243-271, 2024.
[5] Bernd Bohnet, Azade Nova, Aaron T Parisi, Kevin Swersky, Katayoon Goshvadi, Hanjun Dai, Dale Schuurmans, Noah Fiedel, and Hanie Sedghi. Exploring and benchmarking the planning capabilities of large language models. arXiv:2406. 130994 [cs.CL], 2024.
[6] Blai Bonet and Héctor Geffner. Planning as heuristic search. Artificial Intelligence, 129(1): 5-33, 2001.
[7] Bradley Brown, Jordan Juravsky, Ryan Ehrlich, Ronald Clark, Quoe V. Le, Christopher Ré, and Azalia Mirhoseini. Large language monkeys: Scaling inference compute with repeated sampling. NiVW:2407.217881 [cs.L.G), 2024.
[8] Clemens Büchner, Remo Christen, Augusto B. Corréa, Salomé Eriksson, Patrick Ferber, Jendrik Seipp, and Silvan Sievers. Fast Downward Stone Soup 2023. In IPC-10 Planner Abstracts, 2023.
[9] Clemens Büchner, Salomé Eriksson, Thomas Keller, and Malte Helmert. Landmark progression in heuristic search. In Proc. ICAPS 2023, pages 70-79, 2023.
[10] Dillon Z. Chen, Sylvie Thiébaux, and Felipe Trevizan. Learning domain-independent heuristics for grounded and lifted planning. In Proc. AAA/ 2024, pages 20078-20086, 2024.
[11] Dillon Z. Chen, Felipe Trevizan, and Sylvie Thiébaux. Return to tradition: Learning reliable heuristics with classical machine learning. In Proc. ICAPS 2024, pages 68-76. 2024.
[12] Jens Christensen and Richard E Korf. unified theory of heuristic evaluation functions and its application to learning. In Proc. AAAI /986, pages 148-15 152, 1986.
[13] Augusto B. Corrêa, Guillem Francès, Markus Hecher, Davide Mario Longo, and Jendrik Seipp. Scorpion Maidu: Width search in the Scorpion planning system. IPC-10 Planner Abstracts, 2023.

---

[14] Augusto B. Corrèa, André G. Pereira, and Jendrik Seipp. Code and experiment data from the NeurIPS 2025 paper "Classical planning with LLM-generated heuristies: Challenging the state of the art with Python code".
http://....8811//10 zenodo. 17400964 2025.
[15] Joseph C. Culberson. Sokoban is PSPACE-complete. Technical Report TR 97-02, Department of Computing Science, The University of Alberta, Edmonton, Alberta, Canada, 1997.
[16] DeepSeek-AI, Aixin Liu, Bei Feng, Bing Xue, Bingxuan Wang. Bochao Wu, Chengda Lu, Chenggang Zhao, Chengqi Deng, Chenyu Zhang, Chong Ruan, Damai Dai, Daya Guo, Dejian Yang. Deli Chen, Dongjie Ji, Erhang Li, Fangyun Lin, Fucong Dai, Fuli Luo. Guangbo Hao, Guanting Chen, Guowei Li, H. Zhang, Han Bao, Hanwei Xu, Haocheng Wang, Haowei Zhang. Honghui Ding, Huajian Xin, Huazuo Gao, Hui Li, Hui Qu, J.L. Cai, Jian Liang, Jianzhong Guo, Jiaqi Ni, Jiashi Li, Jiawei Wang, Jin Chen, and Jingchang Chen et al. Deepseck-Vi technical [cs.CL], 2024.
report. urXiv:2412.19433
[17] DeepSeek-AI, Daya Guo, Dejian Yang. Haowei Zhang, Junxiao Song, Ruoyu Zhang, Runxin Xu, Qihao Zhu, Shirong Ma. Peiyi Wang, Xiao Bi, Xiaokang Zhang, Xingkai Yu, Yu Wu, Z.F. Wu, Zhibin Gou, Zhihong Shao, Zhuoshu Li, Ziyi Gao, Aixin Liu, Bing Xue, Bingxuan Wang, Bochao Wu, Bei Feng, Chengda Lu, Chenggang Zhao, Chengqi Deng, Chenyu Zhang, Chong Ruan, Damai Dai, Deli Chen, Dongje Ji, Erhang Li, Fangyun Lin, Fucong Dai, Fuli Luo, Guangbo Hao, and Guanting Chen et al. Deepseek-R1. Incentivizing reasoning capability in LLMs via reinforcement learning. arXiv:2501. 19448 [cs.CL], 2025.
(18) Carmel Domshlak, Jörg Hoffmann, and Michael Katz. Red-black planning: A new systematic approach to partial delete relaxation. Artificial Intelligence, 221:73-114, 2015.
[19] James E. Doran and Donald Michie. Experiments with the graph traverser program. Proceedings of the Royal Society A, 294:235-259, 1966.
[20] Patrick Ferber, Malte Helmert, and Jörg Hoffmann. Neural network heuristics for classical planning: A study of hyperparameter space. In Proc. ECAI 2020, pages 2346-2353 2020.
[21] Patrick Ferber, Florian Geißer, Felipe Trevizan, Malte Helmert, and Jörg Hoffmaann. Neural network heuristic functions for classical planning: Bootstrapping and comparison other methods. In Proc. ICAPS 2022, pages 583-587, 2022.
[22] Maximilian Fickert and Jörg Hoffmann. Online relaxation
refinement for satisficing planning: On partial delete relaxation, complete hill-climbing, and novelty pruning. Journal of Artificial Intelligence Research, 73:67-115, 2022.
[23] Richard E. Fikes and Nils J. Nilsson. STRIPS: A new approach to the application of theorem proving to problem solving. Artificial Intelligence, 2:189-201 208, 1971.
[24] Elliot Gestrin, Marco Kuhlmann, and Jendrik Seipp. NI.PPlan: Robust LLM--riven planning from minimal text descriptions. In ICAPS Workshop on Human-Aware and Explainable Planning, 2024.
[25] Malik Ghallab, Dana Nau, and Paolo Traverso. Automated Planning: Theory and Practice. Morgan Kaufmann, 2004.
[26] Daniel Gnad, Álvaro Torralba, and Alexander Shleyfman. DecStar-2023 In IPC-10 Planner Abstracts, 2023.
[27] Gemini Team Google, Rohan Anil, Sebastian Borgeaud, lean-Baptiste Alayrac, Jiahui Yu, Radu Soricut, Johan Schalkwyk, Andrew M. Dai, Anja Hauth, Katie Millican, David Silver, Melvin Johnson, loannis Antonoglou, Julian Schrittwieser, Amelia Glaese, Jilin Chen, Emily Pitler, and Timothy Lillicrap al. Gemini: A family of highly capable multimodal models. arXiv:2312.1 1805 [cs.CL] 2023.
[28] Gemini Team Google, Petko Georgiev, Ving Ian Lei, Ryan Burnell, Libin Bai, Anmol Gulati, Garrett Tanzer, Damien Vincent, Zhufeng Pan, Shibo Wang, Soroosh Mariooryad, Yifan Ding, Xinyang Geng, Fred Alcober. Roy Frostig, Mark Omernick, Lexi Walker, Cosmin Paduraru, Christina Sorokin, Andrea Tacchetti, Colin Gaffney, Samira Daruki, Olcan Sercinoglu, Zach Gleicher, and Juliette Love al. Gemini 1.5: Unlocking multimodal understanding across millions of tokens of context. arXiv:4403.05530 [cs. CLJ, 2024.
12

---

[29] Lin Guan, Karthik Valmeekam, Sarath Sreedharan, and Subbarao Kambhampati. Leveraging pre-trained large language models construct and utilize world models for model-based task planning, In Proc. NeurlPS 2023, pages 79081-79094 2023.
[30] Naresh Gupta and Dana S. Nau. On the complexity of blocks-world planning. Artificial Intelligence, (012-3)22332544 1992.
[31] Mingyu Hao, Felipe Trevizan, Sylvie Thiébaux, Patrick Ferber, and Jörg Hoffmann, Guiding GBFS through learned pairwise rankings. In Proc. IJCAI 2024, pages 6724-6732. 2024.
[32] Peter E. Hart, Nils J. Nilsson, and Bertram Raphael. A formal basis for the heuristic determi- nation of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2): 100-107, 1968.
[33] Patrik Haslum, Nir Lipovetzky, Daniele Magazzeni, and Christian Muise. An Introduction to the Planning Domain Definition Language, volume 13 of Synthesis Lectures Artificial Intelligence and Machine Learning. Morgan & Claypool, 2019.
[34] Malte Helmert. A planning heuristic based on causal graph analysis. In Proc. ICAPS 2004, pages 161-170, 2004.
[35] Malte Helmert. The Fast Downward planning system. Journal of Artificial Intelligence Research, 26:191-244 2006.
[36] Malte Helmert and Héctor Geffner. Unifying the causal graph and additive heuristics. In Proc. ICAPS 2008, pages 140-147, 2008.
[37] Malte Helmert, Robert Mattmüller, and Gabi Röger. Approximation properties of planning benchmarks. In Proc. ECAI 2006, pages 585-589, 2006.
[38] Manuel Heusner, Thomas Keller, and Malte Helmert. Understanding the search behaviour of greedy best-first search. In Proc. SoCS 2017, pages 47-55, 2017.
[39] Jörg Hoffmann and Bernhard Nebel. The FF planning system: Fast plan generation through heuristic search. Journal of Artificial Intelligence Research, 14:253-300 2001.
[40] Richard Howey and Derek Long. VAL's progress: The automatic validation tool for PDDL2.1 used in the International Planning Competition. In ICAPS 2003 Workshop on the Competition, 2003.
[41] Sukai Huang, Trevor Cohn, and Nir Lipovetzky. Chasing progress, not perfection: Revisiting strategies for end-to-end LLM plan generation. arXiv:2412.10673 [cs.CL), 2024.
[42] Michael Katz, Harsha Kokel, Kavitha Srinivas, and Shirin Sohrabi. Thought of search: Planning with language models through the lens of efficiency. In Proc. NeurIPS 2024, pages 138491- 138568, 2024.
[43] Takeshi Kojima, Shixiang (Shane) Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. Large language models are zero-shot reasoners. In Proc. NeurIPS, volume 35, pages 22199- 22213, 2022.
[44] Yujia Li, David Choi, Junyoung Chung, Nate Kushman, Julian Schrittwieser. Rémi Leblond, Tom Eccles, James Keeling, Felix Gimeno, Agustin Dal Lago, Thomas Hubert, Peter Choy, Cyprien de Masson d' Autume, Igor Babuschkin, Xinyun Chen, Po-Sen Huang, Johannes Welbl, Sven Gowal, Alexey Cherepanov, James Molloy, Daniel J. Mankowitz, Esme Sutherland Robson, Pushmeet Kohli, Nando de Freitas, Koray Kavukcuoglu, and Oriol Vinyals. Competition-level code generation with AlphaCode. arXiv:2203.078 14 [cs.PL]. 2022.
[45] Nir Lipovetzky and Hector Geffner. Best-first width search: Exploration and exploitation in classical planning. In Proc. AAAI 2017, pages 3590-3596, 2017.
[46] Bo Liu, Yuqian Jiang, Xiaohan Zhang, Qiang Liu, Shiqi Zhang, Joydeep Biswas, and Pe- ter Stone. LLM+P: Empowering large language models with optimal planning proficiency.
arXiv:2304.1144 1477 [cs.CL], 2023.
13

---

[47] Drew McDermott. The 1998 AI Planning Systems competition. Al Magazine, 21(2):35-55, 2000.
[48] James T. Oswald, Kavitha Srinivas, Harsha Kokel, Junkyu Lee, Michael Katz, and Shirin Sohrabi. Large language models as planning domain generators. In Proc. ICAPS 2024, pages 423-431, 401,4312220 2024.
[49] Stefan O'Toole, Miquel Ramirez, Nir Lipovetzky, and Adrian R. Pearce. Sampling from pre- images to learn heuristic functions for classical planning (extended abstract), In Proc. SoCS 2022, pages 308-310, 2022.
[50] Gerald Paul, Gabriele Röger, Thomas Keller, and Malte Helmert. Optimal solutions to large logistics planning domain problems. In Proc. SoCS 2017, pages 73-81, 2017.
[51] Judea Pearl. Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison- Wesley, 1984.
[52] Ira Pohl. First results on the effect of error in heuristic search. In Bernard Meltzer and Donald Michie, editors, Machine Intelligence 5, pages 219-236. Edinburgh University Press, 1969.
[53] Carl Edward Rasmussen. Gaussian processes in machine learning. In Summer school machine learming, pages 63-71. Springer, 2003.
[54] Silvia Richter and Malte Helmert. Preferred operators and deferred evaluation in satisficing planning. In Proc. ICAPS 2009, pages 273-280, 2009.
[55] Silvia Richter and Matthias Westphal. The LAMA planner: Guiding cost-based anytime planning with landmarks. Journal of Artificial Intelligence Research, 39:127-177, 2010.
[56] Silvia Richter, Malte Helmert, and Matthias Westphal. Landmarks revisited. In Proc. AAAI 2008, pages 975- 982, 2008
[57] Gabriele Röger and Malte Helmert. The more, the merrier: Combining heuristic estimators for satisficing planning. In Proc. ICAPS 2010, pages 246-249 2010.
[58) Bernardino Romera-Paredes, Mohammadamin Barekatain, Alexander Novikov, Matej Balog, M. Pawan Kumar, Emilien Dupont, Francisco R. Ruiz, Jordan S. Ellenberg, Pengming Wang, Omar Fawzi, Pushmeet Kohli, and Alhussein Fawzi. Mathematical discoveries from program search with large language models. Nature, 625(7995):468 475, 2024.
[59] Nicholas Rossetti, Massimiliano Tummolo, Alfonso Emilio Gerevini, Luca Putelli, Ivan Serina, Mattia Chiari, and Matteo Olivato. Learning general policies for planning through GPT models. In Proc. ICAPS 2024, pages 500-508, 2024.
[60] Mehdi Samadi, Ariel Felner, and Jonathan Schaeffer. Learning from multiple heuristics. In Proc. AAAI 2008, pages 357-362, 2008
[61] Arthur L Samuel. Some studies in machine learning using the game of checkers. IBM Journal of research and development, 1959.
[62] Javier Segovia and Jendrik Seipp. Benchmark repository of IPC 2023 - learning track. httppa 2023.
/ //gihub. collbb/ooom//aaa -
[63] Jendrik Seipp. Dissecting Scorpion: Ablation study of an optimal classical planner. In Proc. ECAI 2024, pages 39 42, 2024.
[64] Jendrik Seipp. Florian Pommerening, Silvan Sievers, and Malte Helmert. Downward Lab. https://aoi.org// wttp:////......./.reeeeeeee 790461 2017.
[65] Jendrik Seipp, Thomas Keller, and Malte Helmert. Saturated cost partitioning for optimal classical planning. Journal of Artificial Intelligence Research, 67:129-167. 2020.
[66] Bilgehan Sel, Ahmad Al-Tawaha, Vanshaj Khattar, Ruoxi Jia, and Ming Jin. Algorithm of thoughts: enhancing exploration of ideas in large language models. In Proceedings of the 4 ss International Conference on Machine Learning. JMLR.org, 2024.
14

---

[67] Bilgehan Sel, Ruoxi Jia, and Ming Jin. LLMs can plan only if we tell them. arXiv preprint arX1v:2501.13545, 2025.
[68] William Shen, Felipe Trevizan, and Sylvie Thiébaux. Learning domain-independdnt planning heuristics with hypergraph networks. In Proc. ICAPS 2020, pages 574-584, 2020.
[69] Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mehlhorn, and Karsten M Borgwardt. Weisfeiler-Lehnn graph kernels. Journal of Machine Learning Research, 12(9), 2011.
[70] Tom Silver, Soham Dan, Kavitha Srinivas, Josh Tenenbaum, Leslie Pack Kaelbling, and Michael Katz. Generalized planning in PDDL domains with pretrained large language models, In Proc. AAAI 2024, pages 20256-20264, 2024.
[71] Simon Ståhlherg, Blai Bonet, and Hector Geffner. Learning general optimal policies with graph neural networks: Expressive power, transparency, and limits. In Proc. ICAPS 2022, pages 629 637, 2022.
[72] Kaya Stechly, Karthik Valmeekam, and Subbarao Kambhampati. Chain of thoughtlessness? an analysis of CoT in planning. In Proc. NeurlPS 2024, pages 29106-29141, 2024.
[73] Ayal Taitler, Ron Alford, Joan Espasa, Gregor Behnke, Daniel Fišer, Michael Gimelfarb, Florian Pommerening, Scott Sanner, Enrico Scala, Dominik Schreiber, Javier Segovia- and Jendrik Seipp. The 2023 International Planning Competition. Al Magazine, 45(2):280-296,
2024. doi: 10. 1000//aaiiil.... 12669.
[74] Marcus Tantakoun, Christian Muise, and Xiaodan Zhu. LLMs as planning formalizers: A survey for leveraging large language models construct automated planning models. Findings of the Association for Computational Linguistics: ACL 2025.
[75] Álvaro Torralba, Carlos Linares López, and Daniel Borrajo. Symbolic perimeter abstraction heuristics for cost-optimal planning. Artificial Intelligence, 259:1-31, 2018.
[76] Álvaro Torralba, Jendrik Seipp, and Silvan Sievers. Automatic instance generation for classical planning, In Proc. ICAPS 2021, pages 376-384, 2021.
[77] Alexander Tuisov, Yonatan Vernik, and Alexander Shleyfman. LLM-ggnerated heuristics for AI planning: Do we even need domain-inddeeendenee anymore? arXiv:2501.18788 [cs.Al], 2025.
[78] Karthik Valmeekam, Matthew Marquez, Sarath Sreedharan, and Subbarao Kambhampati. On the planning abilities of large language models critical investigation. In Proc. NeurlPS 2023, pages 75993-76005, 2023.
[79] Karthik Valmeckam, Sarath Sreedharan, Matthew Marquez. Alberto Olmo Hernandez, and Sub- barao Kambhampati. On the planning abilities of large language models (A critical investigation with proposed benchmark). arXiv:2305.15771 [cs.A[], 2023.
[80] Karthik Valmeekam, Kaya Stechly, Atharva Gundawar, and Subbarao Kambhampati. Planning strawberry fields: Evaluating and improving the planning and scheduling capabilities of LRM ol. arXiv:2410.021 [cs.CL.], 2024.
[81] Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Tom Griffiths. Yuan Cao, and Karthik Narasimhan. Tree thoughts: Deliberate problem solving with large language models. Ad- vances in neural information processing systems, 36: 11119-111822 2023.
15

---

A Heuristic Generation Prompt: Blocksworld
Below we show our prompt used for heuristic generation in the Blocksworld domain. The only parts of the prompt that change between domains are the names of the domain and heuristic, and the domain-file, instance-file walleeexample-111e and mestance-fieeeexmmpll reduce the number of pages, we do not display the entire domain and instance files, but just the beginning each. The complete domain and instance files can be found online [4
sections. To
<problem-des -mddeccrrpprrioon
You highly-skilled professor AT planning and proficient Python + programmer creating a comain-dependent heuristic function for the PDDL domain The heuristic function you create will be used to guide greedy best-first search to solve instances from this domain. Therefore, the heuristic does not need be admissible. For given state, the heuristic function should estimate the required number of actions reach + a goal state as accurately as possible, while remaining efficiently computable. The name of the heuristic should be blocksworldlleerristicc The heuristic should be efficiently computable, and it should minimize the number of expanded nodea during the search. Next, you will receive sequence file contente to help you with your task and to show you the definition of the blocks world domain. </problem description>
- boomaipblookksworlk/ooooaaai
the PDDL domain file of blocksworld domain, for which you need to + create a domain- deeendent heuristic: <domain-file> (define (domain blocksworld) [...]
</domain-file?
10
This is an example of a PDDL instance file of the blocksworld domain: <instance file example 1>
(define (problem blocksworld 01)
[...]
15
e/instance-file-eeeae
This is second example of PDDL instance file the blocksworld domain: <instance www--fffleellleeeee example 2>
19
(define (problem blocksworld-99 (:domain blocksworld)
[...]
24
This is the PDDL domain file of another domain, called Gripper, which serves as example:
<gripper domain file>
27
(define (domain gripper strips) [...]
28
e/gripper-domain-tiie domain--iei
This an example of instance file from the Gripper domain:
32
instinnnttttiiieee Saaace-file-se file-fiiaaaaeeeeeee exxeeeappee
(define (problem strips-en taaipp--rripee-x--22 x-20 [...]
</gripper instance
example>
36
37
This is an erample of a domain-dependent heuristic for Gripper: (code--ile--euuistii.. from fnmatch import fnmatch
from heuristics ceattics.heuristc... www.iisiiiibbbaee import Heuristic
41
class httppprrfeerrssiiceeeeieeeee
16

---

domain-dependent heuristic for the Gripper domain.
Summary
This heuristic estimates the number of actions needed to transport all balls from "rooma" to "roomb".
Asaurptions:
The robot has two grippers, alloving to carry up to two balls per trip. The robot must return to rooma after each trip, except for the final trip. If the robot starts in roomb, it must move to rooma first.
52
Heuristic Initialization Implicitly assume that all balls must be 'roomb" at the end.
# Step By-Step Thinking for Computing Heuristic
1. Identify the number of balls still in "rooma" that need to be transported.
2. Determine if the robot currently carrying balls (it may start with or
- 2 already).
3. Check whether the robot is in "rooma" or "roomb": If in room B, it may need to drop the carried balls first before moving A.
room A, it can immediately begin planning the transport.
64
4. Handle the case where the robot starts with balls in the grippers:
If carrying 2 balls, it should move to в, drop them, and return to A. If carrying 1 ball and odd number remains in "rooma", it may pick up another ball before moving.
67
If carrying i ball and an even number remains, it transports the single - ball first.
5. Compute the number of full two balb trips needed: This "balls_in_ // (since up Each full two-ball trip costa actions (except for the last trip).
balls are moved per trip).
6. Handle the last remaining ball (if the total number of balls is odd):
If one ball is left, the robot moves to A, picks it up, moves to B, and drops it.
74
def (self, task):
"""Initialize the heuristic by extracting goal conditions and static facta. unn The set facts that must hold in goal states. We assume that balls - must be in "roomb' at the end.
self goals = task.goals
Static facts not needed for this heuristic.
factic ttatic
def (self, node):
"""Estimate the minimum cost to transport all remaining balls from room A B. -u. state mode.state
85
def (fact, +args): ann
Utility function check if PDDL matches a given pattern.
''factt The fact as a string (e.g., "(at ball1 r)oma)").
"args': The pattern to match (e.g., "at", "*", "rooma").
Returns 'True" if the fact matches the pattern, "False" otherwise.
parts fact[1:-1] :a:::=]]spplle s)
Remove parentheses
split into
+ individual elements. return all (fumatch(part, arg) for part, arg in zip (parts, args))
Count how many balls currently gaall__inrrom_____ sum(1 for fact state if match(fact, "at", "*", "rooma"))
97
17

---

Count the number of balls currently held the robot. balla_ balla_in_grippe in.gripeerr sum(1 for fact in state if match "carry", "*", "*"))
101
102
Check if the robot is in room A. robot_in_ room__ = "(at robby rooma)" in state
105
Define the cost each individual action for readability. coae_coat = # Moving between rooms.
106
107
pick cost # Picking up a ball. drop_cose cost Dropping ball.
109
110
total_cost
Initialize the heuristic cost.
111
Handle cases where the robot is already carrying balls. if robot_in_rrom_a.
114
balls_ giill__iegrripers
115
Both grippers are full, so move to room B and drop both balls.
116
total_cost += move_cost + 2 * drop_cost
elif balle__inggrippers == 1 and balls_in, Pick one more ball fill both grippers, then move and drop both.
== 1:
118
119
total_cost += pick_coat + move_cost 2 drop_cost balls__n__rom_ - # Since we moved one extra ball.
elif iallieen.grippers == 1 and balls_in_
Nove with one ball and drop aoom__ leaving an even number of balls.
0:
122
125
total_cost += move_cost + drop_cost
124
else:
If the robot is in room B, it must drop any carried balls. tost balls_in griippers drop_cost
127
128
if halla_in__oom__r > 0:
Move back to room A to continue transporting balls. total_cost += cost
131
132
Compute the number of trips with two balls.
133
num_tvo havo_ball_ttrppp halla_in_room__ //
B, drops and back total_cost + num_ son_two__bat tro_ball__rripe (2 pick_cost move_cost
Each trip includes: picks, (except for the last trip).
136
drop_cost + move_cost) -
138
there's 's single ball left after the two ball trips, go + and move the ball by itself.
139
if balls_in_room r 2 == 1: total_cost += move_cost + pick_cost move_cost drop_cost
142
Return the estimated cost to goal state.
143
return tosal_cost
144
</code- file heuristic-1>
This the PDDL domain file of another domain, called Logistics, as 4 second example:
147
segiittice-dmain-fffe
148
(define (domain logistice-strips) (:requirementa :stripa)
150
(:predicates
(OBJ ?obj)
151
(TRUCK ?truck)
152
(LOCATION ?loc)
(AIRPLANE ?airplane)
(CITY ?city)
155
(ATRPDRT ?airport)
156
(at ?obj ?loc)
157
(in 7obj1 ?obj2)
18

---

158
(in-city ?obj Pcity))
160
(:action LOAD-TRUCK
161
:parameters
162
(?obj
?truck
?loc)
165
-precondition
166
(and (OBJ ?obj) (TRUCK ?truck) (LOCATION ?loc)
167
(at ?truck ?loc) (at ?obj ?loc))
:effect
169
(and (not (at ?obj ?loc)) (in ?obj ?truck)))
170
[...]
171
fogisstiee-dmmai--ilee
This is example of instance file from the Logistics domain: sesssice-innttnn--illl---ee-
174
175
(define (problem stripe-log-y-5)
176
(: d:momiin logistics strips)
(:objects package5 package4 package3 package2 packagel city8
178
city7 city6 city5 city4 city3 city2 cityl truck15 truck14
179
truck13 truck12 truck11 truck10 truck9 truck8 truck7 truck6
180
truck5 truck4 truck3 truck2 trucki plane1 city8-2 city8-1
city7-2 city7-1 city6-2 city6-1 city5-2 city5-1 city4-2
city4-1 city3-2 city3-1 city2-2 2 city2-1 cityl-2 cityl-1
183
city8-3 city7-3 city6-3 city5-3 city4-3 city3-3 city2-3
184
cityl-3)
185
(:init (obj package5)
(obj package4)
[...]
188
189
This is example of domain-dependent heuristic for Logistica: <code file heuristic 2> from fnmatch import fnmatch
192
193
from heuristics hwwristic. import Heuristic
194
def get_parta(factt)
197
"."Extract the components PDDL fact by removing parentheses and splitting the string." """ return fact[1:-1].st splitt)
198
200
201
def match (fact, +args):
202
203
Check if PDDL fact matches given pattern.
205
'fact" The complete fact as string, e.g., "(in-city airport1 cityl)".
205
"args:: The expected pattern (vildcards allowed). Returns "True" if the fact matches the pattern, else 'False"
207
parts get.parts return all (fnmatch(part, arg) for part, arg in zip(parts, args))
210
211
class LogisticaHeuristic (Herristii::
214
215
domain dependent heuristic for the Logistics domain.
216
Summary
The heuristic estimates the number of necessary actions (load, unload, and traneport) in order transport each package to its goal based on its current atate.
219
19

---

220
Assunttions
Packages be the ground, in truck, in plane. Trucks move within a city, while planes move between cities. If a package is already at the goal, no extra actions are needed.
222
223
224
Heuristic Initialization
Extract the goal locations for each package and the static facts (e.g., 'in-city" relationehipe and airport locations) from the task.
227
228
Step Step Thinking for Computing the Heuristic Value
Below is the thought process for computing the heuristic for given state:
230
231
1. Extract Relevant Information:
232
Identify the current location of every package. Identify whether package is inside vehicle (truck plane), and if so, find the physical location of that vehicle.
234
235
2. Distinguish Between Intra-city and Inter-city Transport:
236
Determine the current city and goal city for each package by checking its location to city mapping.
237
If current city the same as the goal city, follow intra city package movement rules.
238
If the current city is different from the goal city, follow the inter-city package movement rules.
240
3. Handle Intra-city Transport:
241
If the package is already at its goal location, no action is required.
242
If the package is in a plane, it must be unl oaded.
If the package is not in truck and not already its goal, it must be loaded into truck.
244
truck or not yet at its final location, it must be - unloaded from the truck at the goal.
If the package is
245
4. Handle Inter city Transport:
247
Step Move the package to airport in the current city,
248
If the package is not inside a truck and not at an airport, it must be
+ loaded into a truck.
If the package is not an airport or inside truck, it must be umloaded from the truck the airport.
250
Step Fly the package
the destination city.
251
If the package is not in plane, it must be loaded into a plane.
252
The package must always be unloaded from the plane at the airport of the destination city.
253
Step the package from
airport to final location. If the goal location is not an airport, the package must be loaded into truck at the airport.
254
255
Finally, the package must be unloaded from the truck at the goal location.
256
257
5. Summing the Actions:
258
The total heuristic value is the sum of all necessary actions. Loading and unloading costs counted exactly based the required actions.
260
Transport movements (trucks or pl anes) are counted only when necessary.
261
262
def _nint task):
264
...
265
Initialize the heuristic by extracting:
266
Goal locations for each package.
Static facts ('in city' relationships and airport locations).
um
269
gell. task. task.goale goals Goal conditions.
270
static facta = task.static # Facts that are not affected by actions.
271
20

---

Map locations to their respective cities using "in-city" relationships.
self www.tloootttooooooooooeoooo city
274
eet_parts(factt [1]: get_parts(fact) [2]
275
for fact in static_facts if match(fact, "in city", "*", "+")
276
279
Identify airport locations. self self.airports = ={
280
281
pet_parts(fact) [1]
for fact in static_facts match(fact, "airport", "*")
283
284
285
Store goal locations for each package. self. gocaa_olcaoo for goal in self.goals:
288
289
predicate, *arga get_parta(goal)
290
if predicate == "at":
package, location args
292
self
location
293
294
def call__ (self, node):
295
Computt an estimate of the minimal number of required actions. state node state # Current world state.
297
298
Track where packages and vehicles are currently located. current_locatio = ()
299
for fact in state:
301
predicate, *args get_parts(fact) predicate in ["at", "in"l: Track both direct location and inside vehicle.
902
303
obj, location = args
current_locations [obj] location
305
306
tosal_cost Initialize action cost counter.
307
308
for package, _oal_location in self geal_locations.ieen
Get the current location of the package (could be city location, truck or plane).
310
current_location
current_locations (packagge]
311
Check if the package is inside vehicle. in_ vehicle current,location in self location
313
214
315
if in. vehicle:
Identify type of vehicle (truck or plane).
in-plane current_location poocatton.startarith""""""" startavith("plane"" truck current_location. prtpratt_ooattiinssstttttttttts startsuith("""ruc"""" assert in_plane in truck, f I"Invalid state: (ourrent_locationn)
318
319
320
Retrieve the physical location the vehicle. current_location horrmtt__occatioosscareettl
323
elae:
374
inlpaane False
325
truck False
327
Get the city of the package's current location goal. current_city wolff.ocation.to.ccoo citl = self locationnto_ciieeeee.eoo [ location)
328
329
Intra-city Transport (Same City)
332
current_city goal_city:
339
if in-plane:
334
total_cost += 1 Unload from the plane.
21

---

335
if cortein_ != goal_location and in truck: cosal_cost Load into truck.
337
338
339
if locttio_ != goal_location or in truck:
total_cost += 1 Unload from the truck.
342
Inter-city Transport (Different Cities)
343
alae:
344
Step 1: Nove to the airport in the current city, if current_ locatin not in self airports and not in truck: total_cost
346
Load into truck.
347
348
if current_location not in self airports or in_truck: total_cost += 1 Unload from the truck the airport.
351
Step 2: Fly the destination city. if not in-plane:
352
353
tosal_cost += 1 Load into a plane.
355
cost
Unload from the plane.
356
357
Step 3: Transport from airport to the goal (if required). if goal_location not in self airportss total_cost += 1 Load into truck destination airport. total_cost
360
Unload at the destination.
361
362
return tosal_cost </code- file hele-hhurisiic-2
364
365
This how an example state from the blocksworld domain represented internally < by the planner. Note that PDDL facta are represented as strings, for example '(predicate_nat object1 object2)'. <state>
367
frozenset ((' (on table b9)', '(on b9) (on table b2) '(n b10 b2) '(nn b11 + b10) (on b4 b8)", '(on b6 b11)', '(on b5 b6)', '(nn b14 b5) '(n b13 b4) '(on b12 b '(on b1 b12)', (on b7 b1)', (cleaa b3)", *on b3 b7) 'hholiing b15) (clear b)4)
+
</atate>
369
370
This is an example for how the static information is represented internally by the planner:
371
<static>
372
frozenset()
373
</static>
374
This is the source code for representing operators and tasks in the planner: <code-file-taak>
377
unn
378
Classes for representing a STRIPS plamning task
379
381
382
class Operator:
383
384
The preconditions represent the facts that have to be true before the operator applied. effectt are the facts that the operator makes true. offects are the facts that the operator makes false.
386
387
388
def __init__ (self, name, preconditions, add_effects, del_effects):
391
self name name self. seff-preconiiiins frozenset (preconditions) self eff_efs frozenset (add_ effects)
192
393
22

---

394
self del_effects frozenset frozensetddel__eeee (del_effects)
396
def applicable(self, state):
397
unn
398
Operators are applicable when their set of preconditions is subset of the facts that true in "state",
4n1
@return True if the operator's preconditione subset of the state, False othervise
401
403
return self preconditions state
405
405
def apply(self, state):
407
Applying operator means removing the facts that made false by the operator from the set of true facts in state and adding the facts made true.
410
411
112
Note that therefore it is possible to have operands that make fact both false and true. This results in the fact being true at end.
114
415
416
@param atate The state that the operator should be applied to @return new state (set of facts) after the application of the operator
419
u.. assert self app.aaapcaaaeeesttatee
420
421
assert (ypate)) in (frozenset, set) return (state self self.del_effects) I self eddffas
423
424
def (seff, other)
425
return
self name other name and self www.pprrooniioonoonoo. == other, preconditions and self add_ other. acherraddd_efe effects and deflfdel_feeee
128
129
o other. otherrdel_ effects
430
)
431
def (seff)
433
return hash (sseff name, self preconditions, self add effects, self. del_eeeeeee.ooo del_esfects))
434
def - sstr_(seelf"
436
"Asin" X self name for group, facts in [ ("PRE", self preconditions), ("ADD", self add_adddceff) ("DEL" self fif.ddel_effecte
437
438
441
for fact in facts: ]:
442
443
+= 0: for.formttggroup fact)
return
445
def ..erep_..
447
return "<0p Ya>" % self name
448
450
class Task:
451
152
A STRIPS planning task аее
455
def init__(self. name, facts, initial_state, goals, operators, static):
456
457
@param name The task's 's name
23

---

@param facts A set of all the fact names that are valid in the domain at the beginning
set of fact @param goals A set of fact names that must true to solve the problem @param operators set of operator instances for the domain @param static_info A set of facts that are true in every state
@param imitial_state
that
460
461
462
self.
465
self. facts facte self. www.iiintlsaaattteeee initiall_tattee self goals = goals
466
467
self.operators operators
469
self.static static
470
471
def real state):
ann
The goal has been reached if all facts that in "goals" are true in "state".
474
475
476
0return True if all the goals are reached, False otherwise
178
return self goals state
479
480
def stteeaccesorrrttttteeeeeeeeeeeee (self, state):
481
@return list with (op, new_state) pairs where "op" is the applicable operator and "new_state" the state that results when "op" applied in state "state".
483
484
485
return [(op, op. (staaes)) for op in self operators if op.appl applicable(sstate))
487
488
def str str_ (self)
"Task {0)'n Vars: {iAn Init: (2An return f.rrrmt
Goals: {3An
Dps: {4]
191
self .nme,
692
". ".join(solf.
493
holf.imitial_atate
self. "\n" "In" jon..joinmapp(rppp: self self oll.oopert,rr)),
496
)
497
def __repr__ (self):
string = "<Task (0), vars: (1), operators: (2)>" return string. format (self. name, (enself.facts) len(self .ooeel..oorrrtors)
500
501
code file task>
502
Provide only the Python code of the domain-dependent heuristic for the blocksworld domain. Here is checklist help you with your code:
504
1) The code for extracting objects from facts remembers to ignore the surrounding
+ brackets.
505
2) The heuristic is 0 only for goal states.
3) The heuristic value is finite for solvable states.
507
4) All used modules imported.
508
5) The information from static facts is extracted into suitable data structures in the constructor.
509
6) Provide detailed docstring explaining the heuristic caloulation. For this,
divide the docatring into sections "Summary", "Assumptions", "Heuristic
Initialization! and "Step-By-Ste Thinking for Computing Heuristic".
B Generated Heuristics (Selection)
present the selected DeepSeek heuristics from our experiments. We provide descriptions and source code for the Blocksworld and Spanner domains, and only the descriptions for the rest.

---

B.1 DeepSeek RI Heuristic for Blocksworld
In the Blocksworld domain, stacks of n. blocks must be rearranged from an initial state to a goal condition. The available actions move blocks that are on top of stack onto a different stack or the table. Blocksworld is 2- 2-approximable [30]: simply "destroy" all stacks (by placing their blocks onto the table) and then build the goal stacks.
The best heuristic generated by the LLM does not use this method though. It first computes for each block A mentioned in the goal whether A is misplaced and, if so, adds the heuristic value for each block B on top of A, plus 1. For this, the heuristic uses auxiliary function that traverses the stack on top of A. is easy to see that this heuristic can overestimate the optimal plan length.
from fnmatch import fnmatch
from collections import defaultdict
3
from heuristics wwt.sstiics.eurstii..... import Heuristic
class
tomain-dependenn heuristic for the Blocksworld domasn.
8
Summary
Thés heuristic estimates the number of actions required to achseve the goal by considering the number of blocks that need be moved and the blocks above them in the current state. For each block not
goal position, + is 2 times the number of blocks above it plus 2. Held blocks not in the goal posútion add 1 to the cost.
cost
Assumptions
The goal specifies the required 'on" and table' predicates for certasn blocks.
Blocks not mentioned in the goal do not affect the heuristic. Noving block requires unstacking all blocks above it first. The arm can only carry one block time.
18
Heuristic Initialization
Estract the goal conditions to determine the target positions for each block.
Store the goal parent (block or 'table') for each block mentioned the goal.
Steep-yy Step Thinking for Computing Heuristic
1. Parse the current state de dermmneee the current parent (block 'table")
~ and children (blocks on top) for each block.
24
2. Check if any block is currently ly being held.
3. For each block mentioned in the goal:
If the block is held and not in the goal position, add 1 action (putdown or stack).
27
b. If the block is not held and not in the goal position, calculate the number of blocks above it and add 2 actions per block (unstack and putdown) plus 2 actions for the block itself.
4. Sum all calculated costs to get the heuriatic value. hum
30
def init__(self., task):
"n"Tnitialize the heuristic by eatracting goal conditions. 1w.
self.goal celf.goal-parent ()
34
for goal in task.goals:
parta goal[i:-1] if [0] = 'on':
block, parent parta[1], [arts[2]
self self.goall.arent [block] [bloct parent
39
elif [0] 'on table':
block parts [1]
self self.goal_par garet [block]
'table'
25

---

def -_call__ node):
"#"Compute the heuristic value for the given state. .M. state node. state
45
current_parent O
current_children defaultdict(list) held_block None
Parse current state for fact in state: parts -act[i:-1l.spla: parts 'on':
child, parent partsfil, parts[2]
(urrent.parent(childl] parent
perrenttcchlldremmppaentt append(child)
elif parts[O] 'on-table';
block parts[i]]
59
current_parent [bloc_ [block] = 'table'
elif parts [0] 'holding':
held_block parts[1]
Calculate cost coat = 0
64
Check held blokk
belckblock not None held_block self goal_parent: current_pos 'held'
68
goal = self self.goal. goa._parent (held_bohhe held block is not in goal posstion, add 1 action (goal_pos 'table' and current.pos 'table') (goal_pos 'table' coat +=
72
current_pos goal_pos)
Process each block in the goal for block self self.goale goal_parent: if block held_block: continue $ Already handled
77
78
cuurent_parent_blle current_parent. (block,, 'table') goal poal.parent.block self goal_pareetttloo
82
if carrent_parent_blood ! goal_parent_block.
Calculate number of blocks above the current b block def count_aboveex)::
86
ent stack = [x]
while stack:
current stack p))
90
for child in current_children cettreenneettuuurrreeeeee (])
91
ent +*
stack (child)
return cnt
95
above count_above (blovkk
cost += 2 (above 1)
return coat
B.2 DeepSeek RI Heuristic for Spanner
In the Spanner domain, agent must move through corridor, pick up spanners, and tighten nuts at the gate, using each picked-up spanner most once. The agent can move the direction of the gate but not backwards. Thus, moving without first picking up required spanner, results in
26

---

unsolvable state. Optimal plans can be computed in polynomial time by simply pick up exactly the first n spanners and then tighten the nuts the gate.
However, this not the strategy the LLM uses to implement the heuristic function. The heuristic greedily assigns each loose nut (in fixed order) the closest spanner still available. If the spanner has already been picked up, the cost of tightening the nut is the distance from the agent to the nut location plus 1. If not, then the cost is the distance from the agent the location the spanner plus the distance from the location of the spanner to the location of the nut plus 2. Each spanner can be used most once, so if nut has no assigned spanner, the heuristic adds a large number the cost of the state. The heuristic performs breadth- first search during the initialization phase to compute the shortest path between all locations. This can also overestimate the optimal plan length. Arguably. the LLM could have created simpler heuristic the implicit assumptions of the domain were explicit: the PDDL. domain allows for arbitrary connections between locations, but all instances assume one-way corridor.
from fnmatch import fnmatch from collections import defaultdict, deque from heuristice heuristic_base import Heuristic
claes spamer100feuristic (Herrissiit
domain dependent heuristic for the Spanner domasn.
10 Summary
Rstimates the number of actions required tighten all loose nuts by considering the minimal path to collect usable spanners and reach each nut 's location.
12
Issumptions
13
The man (bob) can carry multiple spanners, but each spanner can be used only once.
The shortest path between locations is precomputed using static link information.
The man't name is 'bob' as per the problem ezamples
16
Heuristic Instialization
Estracts static link facts build directed graph of locations. Precomputes shortest paths between all pairs of locations using BFS.
20
Step- Baap-By-B B----B--eeee Step Thinking for Computing Heuristic
1. Identify the man current location.
2. Collect all loose
and their locations.
3. Identify all usable spanners (carried or on the ground).
4. For each loose nut, compute the minimal cost to tighten it using the beat
available spanner.
5. Assign spanners to nuts greedily, marking used spanners to avosd reuse. minimal costs for all nuts to get heuristic value.
6.
28
unn
def iset__ task)
self.goals taak. goals
self.static_links (efaultdicctList) for fact in static:
33
parts f if parts[O] = 'link":
start, (ataaticcc.iiilsssssaaaapeeeeeee append
parts[l], parts[2]
sttfissatic_ [start]
38
Precompute ahortest paths between all locations
self whortest.pathe +0
all_ set(se1f.statiic linkktic_iink..... keys
for ends in welf.statii_.lnns..te values))
42
all all_locations (edate
all_iocations = list (all__oacoasnoo for loc in all_
27

---

distances = floc: 0}
queue deque [[occ]
while queue:
48
current queue q popleft()
for neighbor in self static_links (cturrrnn (]):
if neighbor not in distances:
distances [neighbor] [istances(current] queue append (neighbor) (neighoo))
aelf www.teett.path [loc] distances
def - cal.aall_ (self, node):
state node. state
Find man 's location (assumed be 'bob man man_location = None
for fact in state:
if startaatrt (at bob ');
parts fact[1:-1] splitt
man_location parts [2] break
if not man_location: return ('iat('inf')) Invalid state
Collect loose nuts and their locations
loose_muts [] nut loc_locctioons for fact in state:
if fact. startsvitts (loose 1):
parts = loose_muts (a..uttssppppndppattt[[]]]]
elif fact. startswith ') and 'nut' fact:
parts
76
obj, loc part=[1]]]]]] [i]] parts [2]
mut_locations [obj] loc
Collect usable spanners their locations staable_spannee [
80
carried_ []
spanner_locations = Q
for fact in state:
stat.start (usable (usaall 1):
parts fact [lpl:tt:=l..ss)
hwtpppaeerr..pppddppppppppppp [i])
if fact ("tartssithh"(aarrryr
bob 1):
parts fact sp.sptt
carried_spammer..appoo append (2])
if fact sect.startsvith('1 (at !) and 'spanner' in fact:
parts = fact[1: = spanner_ [pamer_tocatioonspppprrfffff
[arta[[]
94
Prepare available spanners (carried or on ground)
wrailable_spannee
for spanner in usable_spammers:
if spanner in sarried_spanners:
98
available_spammerz .ws.ppannrs.ppeendde....... (oppend(sppnnes) man_location, True))
elif spanner in spanner_location available_spanners httpeeeeepaeeeeeppeeeeeeeeeeeeee False))
spanner laanair_occatonne [spanner],
101
102
Ássign spanners to nuts greedily
103
total_ = upan_ee = set()
for nut loose_nuta:
106
nut_loc nut_locations. get (nut)
107
if not nut_loc:
108
continue # Skkip of nut location not found
28

---

109
mon_ float('inf')
111
best_spanner None for spanner_info in available.spammrss
112
113
spanner, s_loc, is_carried spanner_
if spanner in spaneer:::
continue
116
117
if is_ carried:
118
distance self haw..sshottttttttttee coan_location get (nut_loc, float('inf'))
119
cost distance +
120
elae:
121
d1 wolf.shortest.paee [man_location] float('inf'))
oi ggt (s_loc,
d2 self www.teattppaahsaeeeeeeeeeeee [s_lc] (ooocl.geemtut___aieoeee float (loat(inf")
123
cost d1 float('inf elae float ( ('inf')
d1 != float ('inf") d2
124
if cost min_cost:
126
cost cost best_spanner spanner
127
128
if best_spanner is not None:
total_cost += mos_
131
used_spanners add(besttspannez
132
else:
133
total_cost += 1000000 Penalize for missing spanner
135
return total_cost
B.3
Childsnack
In Childsnack, one must prepare and deliver sandwiches to children, some of whom are allergic to gluten. Ingredients are stored the kitchen and consumed when a sandwich is made. both ingredients are gluten-free, the resulting sandwich is gluten-free. Sandwiches must be placed on trays the kitchen, which can be moved between locations, while the children wait at specific locations. The objective is to serve every child by producing sandwiches that respect their allergies.
In the initialization step, the generated heuristic counts the total numbers of allergic and non-allergic children. Then, it counts the unserved allergic and non-allergic children and the number of available gluten-free and regular sandwiches. Next, estimates the cost produce and place the missing sandwiches and the cost to move trays to each waiting location. The heuristic value is the sum of all these costs. Because ignores tray reuse and that gluten-free sandwiches can be served to non-allergic children, it can overestimate the optimal plan length.
B.4 Floortile
In the Floortile domain, robots must paint grid of tiles with specific colors. Robots may move only onto clear tiles, and moving onto tile painting it makes that tile "not clear". Each robot holds a single color and can change to any available color. Painting is performed from an adjacent tile above or below tile while holding the target color. The objective is to paint all required tiles without blocking access to unpainted tiles that need painting.
The DeepSeek R1 heuristic identifies all required unpainted tiles and their target colors. For each such tile, calculates the Manhattan distance every robot and selects the closest ones as candidates. The cost for that tile is estimated as this minimum distance, plus one if none of the candidate robots hold the required color, and another one the paint action. The total heuristic value is the sum of these costs over all these tiles. This heuristic can overestimate the optimal plan length because considers tiles independently. Furthermore, by ignoring the blocking constraints that arise from painted tiles, it fails to identify dead-end states.
29

---

B.5
Miconic
The Miconic domain models an elevator transporting passengers between floors. This domain is 2-approximable 377.
The selected heuristic first builds an undirected graph of the floors and precomputes all all-s shortest paths using tradthhfirst search. Then, for each unserved passenger, it estimates the remaining cost. If a passenger is already on board, the cost is the distance from the floor of the elevator to its destination plus one (for the depart action). If passenger is waiting, the cost is the distance from the floor of the elevator to its origin, plus the distance from its origin to its destination, plus two (for the board and depart actions). The total heuristic value is the sum of these costs. Because it ignores that the elevator could serve multiple passengers at once, this heuristic can overestimate the optimal plan length.
B.6
Rovers
In the Rovers domain, a team of rovers explores the surface of planet to collect data and communicate it back lander. Data be soil or rock samples, images. Rovers have specific equipment for each task. To collect a sample, a rover must travel to a waypoint, have the right equipment, and an empty storage unit. To take an image, a rover with a camera must first calibrate it at specific location and then move to a waypoint from which the objective is visible.
During initialization, the selected heuristic processes static information, such as waypoint visibility, builds a traversal graph for each rover, and records their equipment. When evaluating a state, the heuristic iterates through each unachieved goal and estimates the cost achieve it. If the data has already been collected, the cost the shortest path for that rover to a waypoint visible from the lander, plus one for the communication action. If the data has not been collected, the cost is estimated by finding an equipped rover that can achieve the goal with minimum cost. This cost includes moving to the goal location, performing the collection imaging action, moving and communicating. For images, the cost of calibration is also included. Distances are computed on-the-fly using a breadth-first search. The total heuristic value is the sum of these costs over all unachieved goals. This heuristic can also overestimate the optimal plan length.
communication waypoint,
B.7 Sokoban
Sokoban is a classic PSPACE-complete problem [3 where an agent must push boxes to specific goal locations within a grid. The agent move between adjacent empty locations. To push box, the agent moves to an adjacent location occupied by a box, and the box is pushed to the next location in the same direction, which must be clear. Since the agent can only push boxes, never pull them, Sokoban has dead-end states.
The heuristic first precomputes all-pairs shortest paths between locations using breadth-fisst search. When evaluating a state, it sums the shortest-pathe distances from each box to its goal location. To this sum, it adds the shortest-path distance from the agent to the closest box not yet at its goal. This heuristic cannot overestimate the optimal plan length, but it ignores push constraints and box interactions and thus fails to identify dead-end states.
B.8 Transport
In the Transport domain, vehicles must deliver packages between locations connected by road network. Vehicles can move between connected locations, pick up packages, and drop them. The key constraint is that each vehicle has limited capacity. Picking up a package consumes and dropping frees one unit of capacity. The objective is to transport all packages to their specified goal locations.
The selected heuristic first precomputes all- pairs shortest paths between locations using breadth- first search on the road network. When evaluating a state, iterates through each package not yet at its goal. If package is already in vehicle, the cost is the shortest-pate distance from the current location of the vehicle to the goal of the package, plus one for the drop action. If the package is at a location, the heuristic greedily assigns it to vehicle that minimizes the cost, which is calculated as the sum of the travel distance the vehicle to the package, the travel distance of the package from its current location to its goal, and two actions for pick-up and drop. The total heuristic value is the sum
30

---

of these costs for all packages. This heuristic can overestimate the optimal plan length because it does not account for one vehicle delivering multiple packages.
C End-to-End Plan Generation Prompt: Blocksworld
Below show prompt used for end-to-end plan generation for the smallest task in the test of the Blocksworld domain. The parts of the prompt that change for different tasks and domains are the name the domain, the domain-files and instance-file pages, we do not display the entire domain and instance files, but just the beginning of each. We also show only the first few actions of each example plan.
As before, reduce the number of
You highly-skilles professor in AI planning searching plan for PDDL task cesooockkkoorld/ddmaiiii You will given the PDDL + domain and the PDDL instance, and you need to return the plan in the format shown below. Next, you will receive a sequence of examples for your task and finally the definition of the blocksworld domain. /pprbblemddeaccrpttion
+
domain
This is the PDDL domain file of the blockaworld domain: <domain file>
(define (domain blocksworld) [...] </domain-fin file>
10
This is the PDDL instance file, for which you need find plan
<instance-file-t>
13
(define (problem blocksworld-01) [...]
14
</instance file 1>
This the PDDL domain file of another domain, called Gripper, which serves as an + example:
18
<gripper--omainn-file
(define (domain gripper-strips) [...]
</gripper-dood moman--file
22
This is an example of an instance file from the Gripper domain: peripper-instance folnnce-flleeeeee fixe-exapleeeee>> (define (problem strips- caaipp--rrippe---ee x-2) [...]
27
This is plan for the Gripper instance above: <plan gripper>
31
(pick bal19 rooma right) (move rooma roomb) (drop bal19 roomb right)
32
(move roomb rooma) [...]
36
</plan-gripper>
This is the PDDL domain file of another domain, called Logistics, to serve as + second example: <logistics-dome file> (define (domain logistice-strips) [...]
</logietice-domain-iiiee
44 This is an example of an instance file from the Logistics domain: Clogistics-ine instane instance- file example> (define (problem strips log
31

---

[...] </logiatica-instaree exampel
50
This is plan for the Logistics instance above: <plan logistics>
(load truck package2 truck12 city5 2) (drive-truck truck12 city5-2 city5-1 city5) [...]
</ pllan-logiatice>
Provide only the plan for the given instance. Here is checklist help you with
+ your task:
58
1) The plan must be the same format as the examples above.
2) Use the tags gollan>..<</pammy around the plan.
3) The actions in the plan must be from the set of actions in the domain
blocksworld, that is, they must
the
and number
parameters as one the action echemas.
4) The plan muat be valid, that is, each action must be applicable in the state it is applied in and the plan must end in goal state.
D Ablation Study: Simplified Prompt Instructions for Blocksworld
Below we show the simplified instruction component used the Blocksworld domain within our ablation study. This simplified version replaces the standard detailed instructions, while other parts of the prompt are retained. Only the modified instructions are shown below.
<problem description>
Create Python domain-dependent heuristic function for the PDDL domain The heuristic function you create will used + to guide a greedy best-first search to solve instances from this domain. The name of the heuristic should be blocksworldfouriistic. Nert, you will receive sequence of file contents help you with your task and show you the definition of the blocksworld domain.
+ ddoominnhllokkeerlkk//daaaa
3
erpobllmm -esdcccriptiin>
E Runtime Comparison of FF in Pyperplan and Fast Downward
Table reports reports expansions per second for the FF heuristic with GBFS in the Python planner (Pyperplan) and the C++ planner (Fast Downward) on the subset tasks solved by both. The "Pyperplan" and "Fast Downward" columns report the total number of state expansions divided by the total search time (in seconds) taken to solve the tasks in each domain. This does not include preprocessing time (e.g., for grounding). The "Performance Increase" column "Fast Downward" divided by "Pyperplan".
Table 5: Expansions per second for GBFS with FF in Pyperplan and Fast Downward.
Domain (ff Tasks)
Pyperplan
Fast Downward
Performance Increase
Blocksworld (24)
111.96
8 $59.94
76.46
Childsnack (17)
893.26
15 890.78
17.79
Floortile (10)
2758.31
87 77681.02 1,02
31.79
Miconie (74)
829,57
669,00
Rovers (27)
109.04
28710.18
263.30
Sokoban (31)
149.45
20059.83
134.22
Spanner (30)
1 3355.35
3255.00
2.37
Transport (29)
3.11
305.49
98.23
32

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
The claims are supported by the extensive discussion our experimental results. We define the scope to be classical planning already in the abstract.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The paper discusses the limitations of the proposed approach in Section 4 Specifically, we discuss the impact of different LLMs used our experiments, the generated heuristics' limitations, and the limitations of the specific prompt approach used with the ablation study.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
33

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [NA]
Justification:
We do not present theoretical results in the paper.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: The paper fully discloses all information necessary to reproduce the main experimental results. This includes: the complete prompt with instructions; the domain- dependent heuristics developed; specifications of the planning software and large language models used; and a detailed description of the experimental setup. To further ensure reproducibility, the complete source code, execution logs, and all generated heuristics are also provided.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
34

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: All code, the prompt, generated heuristics, execution logs, and scripts required to reproduce our main experimental results are provided as supplemental material. A README file contains detailed instructions. Upon acceptance, these materials will be made available in public repository.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (httpa://nips.co cc/
httpli///guidee//oeeeubbbe http://oeeeiiiiiiioooooooooooooo ssionoliccy for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (httpp:
tetips.cc/pub..
gu des/ Cooeeubmissii ossiiiooicccyy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We specify the data used (from IPC 2023), the hyperparameters used by the LLMs, the hardware used, and the experimental setup in Section
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
35

---

The paper does not report error bars or formal statistical significance tests for the primary experimental results (e.g,, coverage on test sets). Our evaluation focuses on metrics such as tasks solved (coverage), plan length, and state expansions. Once a heuristic is generated by the L.LM and selected through our described process, performance on given planning task is deterministic. While the heuristic generation involves L.M sampling, the main reported results are for single, deterministically chosen heuristic per approach. This evaluation methodology, emphasizing direct comparison of performance metrics like coverage on benchmark tasks, is standard practice the planning community, Moreover, Table reports the averages and standard deviations for all generated heuristics with the best method.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
show in tables or
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Section 4 reports this information.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics
http:///pww..eettt.ccccciiiaaaaa ines?
Answer: [Yes]
Justification: Our work used publicly available datasets. No harms were caused by this research, and there are foreseen potential harmful impacts from results.
Guidelines:
36

---

The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is no direct societal impact from our results. Our work is situated more foundational level (i.e., how to plan using LLMs) and does not address specific uses of
it.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative socictal impacts include potential malicious unintended uses (c.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The LLMS and the datasets we use are already publicly available and widespread, and they already have their safeguards in place.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
37

---

12. Licenses for existing assets
Question:
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: All assets which were not created by available online and are credited in the paper.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of in the package should be provided. For popular datasets, (papeetttsppppraaaee pappr wnthhowie thcode com/dataseta
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided. this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer:
[Yes]
Justification:
The created assets (code) are documented and explained.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
38

---

15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/teview based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing. editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [Yes]
Justification: The paper describes the usage of LLMs the core methodology, specifically for generating heuristics for classical planning. The paper also discusses the limitations of the generated heuristics and the impact of different LLMs on performance.
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https: //ner://uuurpu ips. cc /c/Connereccccs//// 2025//022/22///// for what should or should be described.
39


Reviews:
[{"review_id": "DYS689fpml", "reviewer": "Reviewer_2xoe", "summary": "This work showed sampling a set of planning heuristic functions can significantly improve the planning capabilities of LLMs. More specifically, for a given planning domain, LLM generates several domain-dependent heuristic functions in the form of Python code, evaluates them on a set of training tasks with a greedy best-first search, and chooses the best one. They showed that the LLM-generated heuristic functions solve more tasks than LLMs prompted to generate plans end-to-end, and this difference is especially pronounced for non-reasoning LLMs.", "questions": "please take a look at weakness and questions ablove.", "limitations": "yes", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n- The paper uses LLM to generate heuristics for the problem which seems interesting and showing that these heuristics may outperform the existing planner is surprising.\n\n- The paper provide comparison against existing planner \n\nWeaknesses/Questions:\n\n- It seems the LLM itself is not solving the planning problems and it produces the heuristics that still need the solver to find the plan. Also the paper mentioned that these heuristics outperforms existing planners which I don’t understand because if there exists a better heuristic then we should be able to design a better approximate algorithm. For example, for the blocksworld, there is a known 2-approx algorithm. Does that mean the generated heuristic by LLMs does better? If yes, is there any evidence for that?\n\n- The paper mentioned that LLM-generated heuristic functions solve more tasks than LLMs prompted to generate plans end-to-end. But it is not LLM that eventually executes the heuristics. Also I am wondering if the generated heuristics are executable or they still need human check!\n\n- In a more general case, the complexity of classical planning problems varies from polynomial to the Pspace. Does that mean LLMs are able to give us a reasonable approximate solution for np-complete, Pspace problems? \n\n- h^{FF} is referred to in the paper but never explained what the heuristic is. Especially when saying LLM's heuristics outperform state-of-the-art heuristics, such as h^{FF}. There should be some examples and justification. Also there are other heuristics mentioned in the paper which need to be explained for better understanding of LLMs’ heuristics. \n\n- The paper should discuss the details on datasets distribution on size, etc. They only mentioned an example like this: In Blocksworld, for example, the largest training task contains 29 146 blocks, while the largest test task has 488 block", "was_revised": true, "final_justification": "Some of my concerns are discussed in the rebuttal and it also highlight some of the issues I was pointing out. Since the heuristics are generated by LLMs they might not be reliable and also the search over them can be expensive. This need to be studied more thoroughly since the search is part of the planning itself.", "rebuttal": "Thank you for your review and for your suggestions! We clarify your questions below.\n\n> It seems the LLM itself is not solving the planning problems and it produces the heuristics that still need the solver to find the plan. Also the paper mentioned that these heuristics outperforms existing planners which I don’t understand because if there exists a better heuristic then we should be able to design a better approximate algorithm. For example, for the blocksworld, there is a known 2-approx algorithm. Does that mean the generated heuristic by LLMs does better? If yes, is there any evidence for that?\n\nRegarding the comparison to approximation algorithms, it is important to clarify the research context. The goal in automated planning is to *develop domain-independent planners that work sufficiently well for any domain*. These planners use domain-independent heuristic functions that reason about the general PDDL structure without any built-in knowledge of \"Blocksworld\" or any other domain.\n\nAn approximation algorithm, like the 2-approximation for Blocksworld, is a specialized algorithm for a single domain. Comparing a general planner to a specialized algorithm is not a standard evaluation practice as their objectives are different.\n\nYou are correct that in our approach the LLM does not solve the planning tasks directly. In our paper, we show that using LLMs for end-to-end plan generation is less effective (solving 202 tasks) than a planner guided by a domain-independent heuristic function (solving 324 tasks). However, we also show that we can use LLMs to generate domain-dependent heuristic functions that outperform the state-of-the-art domain-independent heuristics (solving 373 tasks).\n\n> The paper mentioned that LLM-generated heuristic functions solve more tasks than LLMs prompted to generate plans end-to-end. But it is not LLM that eventually executes the heuristics.\n\nThank you for pointing this out!\nWhen we say that LLM-generated heuristic functions solve more tasks than LLMs prompted to generate plans end-to-end, we mean that *greedy best-first search guided by the LLM-generated heuristic function* solves more tasks. We will clarify this.\n\n> Also I am wondering if the generated heuristics are executable or they still need human check!\n\nThere are *no human checks* in our approach. Instead, the process is fully automated.\n\nWe prompt the LLM to generate heuristic functions as Python code. These generated functions are then automatically evaluated on a set of training tasks. The best-performing heuristic is automatically selected and the Python code is then directly injected into the planner and executed to solve the unseen test tasks.\n\n> Does that mean LLMs are able to give us a reasonable approximate solution for np-complete, Pspace problems?\n\nLLMs can give us heuristic function that provide reasonable estimates for NP-hard problems, but we still need to run a search algorithm to find the solution. This search can still, in the worst case, expand an exponential number of states.\n\nHowever, a good heuristic can make the search much more efficient in practice by guiding it toward promising states and pruning large parts of the search space that do not lead to a solution. Our results show that LLM-generated heuristics can be very effective and often outperform state-of-the-art heuristic functions.\n\n> h^{FF} is referred to in the paper but never explained what the heuristic is. Especially when saying LLM's heuristics outperform state-of-the-art heuristics, such as h^{FF}. There should be some examples and justification. Also there are other heuristics mentioned in the paper which need to be explained for better understanding of LLMs’ heuristics.\n\nThank you for the suggestion! We will use the additional content page of the camera-ready version to describe the domain-independent heuristics mentioned in the paper.\n\n> The paper should discuss the details on datasets distribution on size, etc.\n\nGood idea! We will include additional details about the dataset. Below you can find the size distribution of the the most significant parameters for training and test set tasks:\n\n| domain      | Training size | Testing size |\n|-------------|---------------|--------------|\n| Blocksworld | n ∈ [2, 29]   | n ∈ [5, 488] |\n| Childsnack  | c ∈ [1, 10]   | c ∈ [4, 292] |\n| Floortile   | t ∈ [2, 30]   | t ∈ [12, 980]|\n| Miconic     | p ∈ [1, 10]   | p ∈ [1, 485] |\n| Rovers      | r ∈ [1, 4]    | r ∈ [1, 30]  |\n| Sokoban     | b ∈ [1, 4]    | b ∈ [1, 79]  |\n| Spanner     | s ∈ [1, 10]   | n ∈ [1, 487] |\n| Transport   | v ∈ [1, 7]    | n ∈ [3, 50]  |\n\nMost significant parameter for each domain: n blocks in Blocksworld, c children in Childsnack, t tiles in Floortile, p passengers in Miconic, r rovers in Rovers, b boxes in Sokoban, s spanners in Spanner, v vehicles in Transport."}, {"review_id": "snp5gS5f6w", "reviewer": "Reviewer_K8zo", "summary": "This paper proposes a novel method to improve classical planning by leveraging large language models (LLMs) to generate domain‐dependent heuristic functions from PDDL domain descriptions. Instead of relying on end-to-end plan generation by the LLM, the method “induces” heuristics in the form of Python code that guide a greedy best-first search. The approach involves prompting the LLM multiple times with a detailed and multi-component prompt (including PDDL domain files, sample tasks, example heuristics, and even a checklist of pitfalls), collecting diverse candidate heuristics, evaluating their performance on a training set of planning tasks, and finally selecting the best performing heuristic to tackle out-of-distribution test tasks. The paper includes extensive experiments comparing the LLM-generated heuristics with traditional domain-independent heuristics (e.g., FF) and state-of-the-art learning-based planners. Ablation studies on prompt components further illustrate the impact of various parts of the prompt. Overall, the work demonstrates that LLM-generated heuristics can significantly enhance planning performance and even overcome performance gaps between Python-based prototypes and C++ implementations in existing planners.", "questions": "- How sensitive is the overall performance to changes in the prompt formulation? Could more concise prompts yield similar performance, or is the detailed multi-component prompt essential?\n- How do variations in the underlying LLM (e.g., reasoning vs. non-reasoning models or model scale) affect the quality of the generated heuristics? Is there a clear trade-off between computational cost and heuristic performance? The LLMs in the paper are very strong.\n- Maybe worth discuss the LLM domain induction works on PDDL for better position the paper.", "limitations": "I don't see a separate limitation section. Not clearly discussed in Section 4 as well.", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n- The paper presents an original idea of using LLMs to “induce” domain-dependent heuristics, circumventing the drawbacks of end-to-end plan generation and manual heuristic design.\n- A thorough experimental evaluation is provided, with comparisons against well-known baselines and state-of-the-art methods; the experiments on IPC domains, ablation studies, and runtime comparisons add credibility to the results.\n- The paper carefully explains the heuristic generation pipeline, including prompt design, candidate generation, evaluation, and selection. Supplementary material provides detailed prompts and example code, which aids reproducibility and transparency.\n- Although demonstrated on classical planning with PDDL, the approach has potential to be extended to other planning or combinatorial task settings.\n\nWeaknesses:\n- The method appears highly sensitive to the design and length of the prompt. The appendix shows an extremely long and intricate prompt—raising questions about scalability and whether the approach would still work as effectively with shorter or less detailed instructions.\n- The process of selecting the “best” heuristic from a generated set is somewhat heuristic itself, and additional discussion on the sensitivity of this selection mechanism and its potential failure modes would strengthen the work.", "was_revised": true, "final_justification": "It’s clear from the rebuttal that the current version of the paper overlooks several important aspects. The next draft should incorporate missing components such as the small model experiments, detailed ablation studies, a discussion of limitations, and potentially a more thorough review of related work.\n\nOverall, the paper would benefit from another round of careful revision and editing to address these gaps.", "rebuttal": "Thank you for your review and for your suggestions! We answer your questions below.\n\n> How sensitive is the overall performance to changes in the prompt formulation? Could more concise prompts yield similar performance, or is the detailed  multi-component prompt essential?\n\nOur ablation study (page 7, line 245) analyzes the sensitivity of our method to the prompt formulation. As detailed in Table 3, the performance ceiling for the original prompt is much higher than for all cases where components are individually removed, which shows that all components strengthen our method.\n\nAt the same time, the ablation study also shows that while all components strengthen our method, most can be removed individually without a significant drop in performance. This suggests that the prompt is quite robust to changes.\n\n> How do variations in the underlying LLM (e.g., reasoning vs. non-reasoning models or model scale) affect the quality of the generated heuristics?\n\nTable 1 shows that reasoning models (DeepSeek R1 and Gemini Thinking) outperform their non-reasoning versions (DeepSeek V3 and Gemini).\n\nHowever, it is interesting to notice that the gap between their performances is not that large. This is in contrast to the end-to-end plan generation, where the reasoning models are vastly superior to their non-reasoning counterparts. In other words, *our method can reduce the performance gap between reasoning and non-reasoning models, allowing us to use the non-reasoning and cheaper models to obtain a similar performance*.\n\n> Is there a clear trade-off between computational cost and heuristic performance? The LLMs in the paper are very strong.\n\nWe ran a local experiment with Qwen3 4B using a NVIDIA GeForce RTX 4090 with 24GB of VRAM. This is a popular GPU that is commonly used in personal computers. To generate 25 heuristics sequentially, we need 4h33m on average. (One could generate two heuristics in parallel with the available VRAM, but we stick to a single process.)\n\nWe repeat the exact experiment of the paper with these new heuristics, and the results are as follows:\n\n| Domain       | Qwen3 4B |\n|--------------|----------|\n| Blocksworld  |       27 |\n| Childsnack   |       12 |\n| Floortile    |        3 |\n| Miconic      |       90 |\n| Rovers       |       31 |\n| Sokoban      |       26 |\n| Spanner      |       30 |\n| Transport    |       44 |\n| Total        |      263 |\n\n\nThis shows that a \"small LLM\" can already outperform the FF heuristic in Pyperplan. It has strictly higher coverage in 4 out of the 8 domains, and it ties with FF in another domain.\n\n> Maybe worth discuss the LLM domain induction works on PDDL for better position the paper.\n\nDo you suggest discussing the literature on extracting PDDL domains from natural language? Yes, we're happy to do that. This has the benefit of showing that our method can be used in conjunction with such methods, providing an end-to-end solution for planning on natural language tasks, via PDDL.\n\n> I don't see a separate limitation section. Not clearly discussed in Section 4 as well.\n\nWe will add a limitation section in the camera-ready version.\n\n> The process of selecting the “best” heuristic from a generated set is somewhat heuristic itself, and additional discussion on the sensitivity of this selection mechanism and its potential failure modes would strengthen the work.\n\nThank you for the suggestion. We will add a discussion on the sensitivity of the selection mechanism in the camera-ready version. We already ran two additional experiments to analyze this further. We used two different subsets of tasks from the training set to select the best R1-generated heuristic: six tasks distributed over the training set (including the smallest and the largest task), and two tasks (only the smallest and the largest task). The results are shown in the table below:\n\n| Training Subset                     | Tasks Solved |\n|-------------------------------------|--------------|\n| Smallest, Largest and 4 Random Tasks| 374          |\n| Smallest and Largest Task           | 361          |\n| All Training Tasks                  | 373          |\n\nAs shown in the table, the selection mechanism is quite robust to the choice of the training tasks. The Table shows that *using only two tasks* (the smallest and the largest) *still results in a good performance*. This suggests that the selection mechanism is robust to the choice of training tasks. We have chosen to use all training tasks to select the best heuristic to obtain the simplest approach possible. However, our method allows using a smaller set of tasks to select the best heuristic if the computational resources are limited."}, {"review_id": "VtTI2ID8Oc", "reviewer": "Reviewer_VEfu", "summary": "The paper investigates the usage of LLM for solving classical planning tasks defined in PDDL. Instead of generating an end-to-end plan, the authors propose generating domain-dependent heuristics that are used in a greedy best-first search. The method consists of choosing a best-of-n heuristic by the score on the training set. The experiments include 8 classic planning environments. Results demonstrate that generated heuristics outperform domain-independent baselines and show competitive performance to the domain-dependent one.", "questions": "The paper requires redirecting, as the general problem that the authors are trying to solve is unclear. Is it proposing the new SOTA LLM-based method for classical planning? If so, the results should be SOTA, and perhaps the paper is a better fit for a planning conference. Is it a new hybrid method for planning, applicable to the general natural text planning problems? Then, such applications and results should be shown and compared to the suitable baselines.", "limitations": "Yes", "rating": 2, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 1, "originality": 1, "strengths_and_weaknesses": "Strengths:\n - The paper is well-written and easy to follow, with enough background information provided.\n\nWeaknesses:\n - The PDDL environments are often used to benchmark the LLM's planning abilities in general, which is why the plans are generated in full, end-to-end. While the models are known to fail on larger, out-of-distribution tasks, the key here is that the model can be applied to general-case planning for problems not defined in PDDL (e.g., agentic and robotics tasks). Although in the related work section, the authors discuss the possibility of incorporating their heuristic generation method into the pipeline where natural text problems are translated into PDDL, they do not attempt it, making the comparison unfair.\n - Overall, the method is a very simplistic BoN, with no modifications made to make it specific for the planning problems. Since the results are comparable to the only one provided domain-dependent baseline (371 $h^{WLF}_{GPR}$ vs. 373 $h^{R1}$), I would expect either a much greater margin, which would indeed demonstrate surprising abilities of the model to generate domain-specific heuristics, or some modifications/training specific for planning.\n- The statement of the baselines being state-of-the-art is questionable, since IPC 2023 shows the winners of GOFAI & HUZAR, which are not used in the comparison.\n- The possible contamination issue is not addressed. Though unlikely, there is a possibility of such heuristics present in the training set of R1 & Gemini (which were released after the IPC 2023).\n - Ablation study shows large deviations, which makes the statistical significance questionable.", "was_revised": true, "final_justification": "The proposed method shows results **comparable** to SOTA in PDDL-formalized environments, and there could be more effort put into developing (e.g., fine-tuning) the method to outperform the baseline, considering the focus of the paper only on the PDDL-like tasks. If the method is still considered an alternative to general end-to-end planning (as one of the baselines), then the FLOPs-controlled experiments on **non-PDDL environments** (e.g., the proposed scheme of problem formalization -> heuristic generation -> solution) should be conducted.\nI appreciate the author's efforts in rebuttal; however, I am inclined to keep my score due to the aforementioned concerns.", "rebuttal": "Thank you for your review and for identifying some issues with the presentation!\n\n> The paper requires redirecting, as the general problem that the authors are trying to solve is unclear.\n\nWe respectfully disagree with the reviewer. The problem we address is the well-documented limitation of LLMs to reliably solve problems that require reasoning (Valmeekam et al., 2023; Stechly et al., 2024; Shojaee et al., 2025).\n\nWe propose a novel approach to this well-known problem: instead of using LLMs end-to-end, we use them to generate domain-dependent heuristic functions that guide a search algorithm. This approach can be understood as using LLM for program synthesis.\nAs shown in Table 1, our method dramatically improves performance. For example, for the non-reasoning model Gemini 2.0, our approach increases the number of solved tasks from 19 to 296. \n\n> Is it proposing the new SOTA LLM-based method for classical planning? If so, the results should be SOTA [...] The statement of the baselines being state-of-the-art is questionable, since IPC 2023 shows the winners of GOFAI & HUZAR, which are not used in the comparison.\n\nThis seems to be a misunderstanding. Our results are indeed state-of-the-art for the problem we are solving.\n\nOur approach generates heuristic functions to guide a GBFS. Consequently, we compare our method against several domain-independent heuristics available in the Fast Downward planner and against the best learning-based method for domain-dependent heuristics, $h^{WLF}\\_{GPR}$. Notably, $h^{WLF}\\_{GPR}$ is far superior to any other heuristic in the IPC 2023 Learning Track. All these baseline heuristics also guide a GBFS, ensuring a fair comparison.\n\nGOFAI and HUZAR are not heuristic functions. They are complete planning systems that incorporate several advanced techniques that make them incomparable to a single heuristic function guiding a simple GBFS.\n\nInvestigating how to use our techniques as one of the components within such a planning system is an interesting direction for future work.\n\nWe agree that some of our statements regarding state-of-the-art performance (e.g., on lines 240 and 260) could be clearer. We will reword them to be more precise in the final version. Thank you for pointing this out!\n\n> Since the results are comparable to the only one provided domain-dependent baseline (371 $h^{WLF}\\_{GPR}$ vs. 373 $h^{R1}$)...\n\nWe could compare our method to other domain-dependent baselines if the reviewers agree. However, to the best of our knowledge, $h^{WLF}\\_{GPR}$ is currently the strongest domain-dependent heuristic for classical planning.\n$h^{WLF}\\_{GPR}$ is the culmination of decades of research into how to learn domain-dependent heuristics. Our results show that LLMs can often generate domain-dependent heuristics that are competitive with $h^{WLF}\\_{GPR}$ running inside the C++ planner Fast Downward, even if we execute them in an educational Python planner.\n\n> .. the paper is a better fit for a planning conference.\n\nWe respectfully disagree and believe our paper is an excellent fit for NeurIPS. The NeurIPS community has shown a significant and growing interest in topics central to our work, such as planning, reasoning, and program synthesis using LLMs.\n\nTo illustrate this, we provide a non-exhaustive list of recent papers on LLMs for planning that were published at NeurIPS or raised a lot of interest in the ML community:\n\n- Zhao et al.: Improving Large Language Model Planning with Action Sequence Similarity. ICLR 2025.\n\n- Katz et al.: Thought of Search: Planning with Language Models Through The Lens of Efficiency. NeurIPS 2024.\n\n- Stechly et al.: Chain of Thoughtlessness? An Analysis of CoT in Planning. NeurIPS 2024.\n\n- Valmeekam et al.: On the Planning Abilities of Large Language Models - A Critical Investigation. NeurIPS 2023.\n\n- Guan et al.: Leveraging Pre-trained Large Language Models to Construct and Utilize World Models for Model-based Task Planning. NeurIPS 2023.\n\n- Shojaee et al.: The Illusion of Thinking: Understanding the Strengths and Limitations of Reasoning Models via the Lens of Problem Complexity. 2506.06941 Apple 2025\n\n> The PDDL environments are often used to benchmark the LLM's planning abilities in general [...] the authors discuss the possibility of incorporating their heuristic generation method into the pipeline where natural text problems are translated into PDDL, they do not attempt it, making the comparison unfair.\n\nResearch on improving the capabilities of LLMs to solve problems that require reasoning is ongoing.\n\nWe believe that building a complete pipeline from natural language to a correct plan should involve multiple steps. The research community is tackling these challenges through various modular approaches, such as the ones focusing on translating the problem into a formal representation (Gestrin et al., 2024; Katz et al., 2024; Tantakoun et al., 2025). \n\nOur work focuses specifically on the plan generation component, assuming a formal PDDL model is already available. \n\nWhile an end-to-end system is a long-term goal, we believe that focusing on and improving individual components is a crucial step in advancing the field.\n\n- Tantakoun et al.: LLMs as Planning Formalizers: A Survey for Leveraging Large Language Models to Construct Automated Planning Models. ACL (Findings) 2025.\n\n- Gestrin et al.: NL2Plan: Robust LLM-Driven Planning from Minimal Text Descriptions. 2405.04215 2024.\n\n> Overall, the method is a very simplistic BoN, with no modifications made to make it specific for the planning problems.\n\nSimplicity is an advantage and not a problem. Our method shows that even a straightforward method can already be useful to create classical planning heuristics. We agree that adding layers of modifications tailored to planning can bring even further benefit.\n\n> Ablation study shows large deviations, which makes the statistical significance questionable.\n\nThe large deviation in the ablation study is an expected and desired outcome of our method. Our goal is not to generate heuristics that are good on average, but to ensure that we have a diverse pool of heuristic to select from. The high variance is a direct consequence of sampling with a high temperature to maximize diversity. To obtain more consistent results, one could simply use a lower temperature. However, this is not desirable. We ran preliminary experiments with lower temperatures resulting in lower deviation but also lower coverage.\n\n> The possible contamination issue is not addressed. Though unlikely, there is a possibility of such heuristics present in the training set of R1 & Gemini.\n\nTo address the concern of potential data contamination, we ran three additional experiments designed to test whether the LLMs are retrieving memorized heuristics or reasoning about the provided PDDL domain.\n\n1. Domain Modification (Spanner): We modified the Spanner domain so that spanners are not consumed after use. If the LLM had merely memorized a known heuristic for Spanner, it would fail to account for this change. However, the generated heuristic for the modified domain correctly adapted to the new semantics. The best generated heuristic is indeed *perfect* for this modified domain, and thus produces optimal plan costs for all states. This suggests the LLM reasoned about the given domain rather than retrieved a memorized solution.\n\n2. Obfuscation (Blocksworld): We created an obfuscated version of the Blocksworld domain where all component names were replaced with random strings as done by Valmeekam et al. We translated the Blocksworld tasks used in the paper and ran an experiment with the exact same setup as in the paper. The results are shown in the table below:\n\n| domain                 | Fast Downward FF | Pyperplan R1 |\n|------------------------|------------------|--------------|\n| Blocksworld            | 27               | 66           |\n| Obfuscated Blocksworld | 28               | 40           |\n\nThe performance of Fast Downward with FF remained stable (modulo noise), as expected. The performance of the R1-generated heuristic degraded but still outperformed the FF baseline. This indicates that while semantic cues in predicate names are helpful, the LLM is still capable of reasoning about the logical structure of the domain. We note that this experiment is a highly adversarial setting for LLMs, because they are trained to take into account the semantics of the tokens and not operate on random strings.\n\n3. Novel Domain (Rod-Rings): We designed a new domain, Rod-Rings, which has never been made available online nor fed to an LLM. It features sticks with stacks of rings and a single \"held\" ring. Two moves are allowed: (a) place the held ring at the bottom of a stick, swapping it with the top ring, or (b) place the held ring on top of a stick, swapping it with the bottom ring. The goal is to arrange specific rings on specific sticks in a defined order.\n\nTo ensure the domain remains novel, we used an OpenAI model (O3) via their API, which guarantees that API data is not used for model training nor stored. We also provide results for O3-generated heuristic on the domains used in the paper.\n\n| domain                       | Fast Downward FF | Pyperplan O3 |\n|------------------------------|------------------|--------------|\n| Rod-Rings                    | 59               | 58           |\n| Paper Domains (IPC Learning) | 295              | 354          |\n\nOn this new domain, the O3-generated heuristic guiding a GBFS solves 58 tasks, almost as many as Fast Downward guided by FF which solves 59 tasks. This suggest that the LLM reasons about this unseen domain.\nThe results for the other domains for the O3-generated heuristics are inferior to the R1-generated heuristics which solve 373 tasks.\n\nTogether, these experiments indicate that the success our method is not due to contamination but to the LLMs' ability to generate domain-dependent heuristic functions by reasoning about the logical structure of the domain."}, {"review_id": "IC97RKiQL9", "reviewer": "Reviewer_MPk1", "summary": "This paper shows how LLMs can be used to generate domain-dependent heuristics which can be integrated off-the-shelf into Pyperplan, a python based planner developed with educational purposes in mind, not performance. The methodology prompts an LLM providing the PDDL representation of the target domain, with the smallerst and largest instance. The prompt is complemented with two examples of planning domains, their models, their solution in python, their static domain and state representation in Pyperplan along with a checklist of common errors. A sample of heuristics are generated, n=25, and the best performing one over the training instances from the learning competition in the International Planning Competition (IPC)  is selected given the agile score of the IPC, with a five minutes timeout.\n\nThe experimental results strongly suggest that this approach to derive a heuristic function is competitive with state-of-the-art domain-independent heuristics, as well as other learning approaches to develop domain-dependent heuristic based on Gaussian models. Overall, the generated heuristic yields better coverage with similar expansion rates and plan length, meaning that the increase in coverage doesn't come with a cost of computation time, as a function of expanded nodes, and plan quality. \n\nOverall, it doesn't only outperform planners developed for performance considerations and well known domain-independent heuristics, it also shows how it substantially increases the performance of LLMs without reasoning capabilities.", "questions": "- What is the speed factor difference when you try to solve a task with a highly engineered planner in C++ vs a planner written in python with educational purposes? This result can help the reader understand the impact of table 2. It could be measured by expansion time running breadth first search, or running the same LLM heuristic and greedy best first search, one written in python, the other one adapted by the authors in C++.\n\n- Can you clarify further on the issues raised above with respect to understanding what general strategies the heuristic is following, and how different it is from work published in the literature?", "limitations": "N/A", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "# Quality\n\nThe paper develops a sound methodology following the style of papers aiming to understand how to prompt an LLM for coding purposes. It evaluates in depth how to assess the value of the approach by comparing the generated pipeline with existing approaches in the planning literature. Several metrics are used, baselines are provided using different LLMs, planning codebases, domain-independent heurstics and learnt heuristics, and the approach seems to be easily reproducible following the appendix. \n\nOn the flip side, a minor comment is that I missed having more details on the computation time to create the heuristic, as well as computation time to evaluate the heuristic. It is only mentioned in text with as a few hours. See question below. \n\nI also missed a deeper analysis of the strategies used by the LLM to develop their heuristics. The paragraph before section 5 is really insightful, but I was left wanting to know more, which per se it is a good outcome of a paper, but can also be a negative one. In trying to understand and relate the heuristics to theory, or to general strategies in planning, as a reviewer I was left wondering if all heuristics would follow the structure of the heuristics developed by correlation complexity [1], using weighted linear combinations of state variables, or other general strategies in the literature similar to relaxations, decomposition, etc. Having a deeper dive on what the heuristic \"looks like\" would make the paper more insightful. \n\nNo mention was added with respect of testing problems that have already been used for training the LLM. The paper cited below contains heuristics which are very similar to the one produced by the LLM in Blocksworld, as well as well known strategies to solve blocksworld suboptimally. Understanding how novel the new heuristics are (in terms of general strategies for problem solving) could address this issue, as well as devising new domains. \n\n[1] Jendrik Seipp, Florian Pommerening, Gabriele Röger, and Malte Helmert. 2016. Correlation complexity of classical planning domains. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence (IJCAI'16). AAAI Press, 3242–3250.\n\n# Clarity\nThe experimental design follows well accepted performance metrics by the Planning community, which is essential to convey the results. The text is well written and easy to follow. \n\nMinor suggestions:\n- move footnote 4 to the main text, it's an important observation.\n- Table 3, clarify number of failed heuristics out of how many? The table could also be more informative if shown as a figure.\n  \n# Significance\n\nIn the context of how to make LLMs to plan, this represents a promising approach to lift their performance closer to state-of-the-art symbolic planners, and at the same time, it provides a way forward to integrate LLMs within symbolic planning systems. This has been proved to be a very difficult task, with all the literature so far showing how far LLMs are in their planning capabilities when faced with planning problems specified in PDDL.\n\nThe results in this paper clearly motivate an active research direction developing this methodology further for other planning formalisms, improving LLMs planning ability and the integrations of LLMs in the development of symbolic planners.\n\n# Originality\n\nThis approach is not novel, i.e. programming a heuristic as noted by the authors has been tried before, but it has never been shown to perform so well on satisficing classical planning, a problem that so far has been proved to be extremely challenging for LLMs.", "was_revised": true, "final_justification": "The authors addressed my questions properly. I think they also addressed criticisms from other reviewers. This paper provides valuable insights and the experimental results are strong.", "rebuttal": "Thank you for your comments and suggestions! We clarify some of your points below.\n\n> What is the speed factor difference when you try to solve a task with a highly engineered planner in C++ vs a planner written in python with educational purposes? This result can help the reader understand the impact of table 2. It could be measured by expansion time running breadth first search, or running the same LLM heuristic and greedy best first search, one written in python, the other one adapted by the authors in C++.\n\nBelow we show a table with the number of expansions per second for the FF heuristic in Pyperplan (implemented in Python) and Fast Downward (implemented in C++) for the subset of tasks solved by both planners (shown in parentheses). The table shows the difference in performance between the two planners using the same search algorithm (GBFS) and the same heuristic (FF).\n\n| Domain (Tasks)        | Python   | C++       | Performance Increase |\n|-----------------------|----------|-----------|----------------------|\n| Blocksworld (24)      | 6964.21  | 142621.78 | 20.48                |\n| Childsnack (17)       | 14495.45 | 190385.84 | 13.13                |\n| Floortile (10)        | 27486.89 | 229067.58 | 8.33                 |\n| Miconic (74)          | 4878.33  | 37715.63  | 7.73                 |\n| Rovers (27)           | 3410.42  | 63064.41  | 18.49                |\n| Sokoban (31)          | 1350.62  | 37400.46  | 27.70                |\n| Spanner (30)          | 25312.26 | 44137.59  | 1.74                 |\n| Transport (29)        | 1162.04  | 8559.27   | 7.37                 |\n\nPlease also note because of the different *grounding techniques* used by Pyperplan and Fast Downward there are tasks where Pyperplan fails in the grounding phase and cannot start the search while Fast Downward succeeds and can start the search.\n\nPyperplan fails in 162 tasks during grounding, while Fast Downward fails only in 65. These are tasks that we cannot solve, regardless how good the heuristics are. So there is 2.5x more tasks that Pyperplan cannot possibly solve compared to Fast Downward.\n\n(Reviewer BKh1 asked a similar question, so it might be useful to read our answers to their questions as well.)\n\n> Can you clarify further on the issues raised above with respect to understanding what general strategies the heuristic is following, and how different it is from work published in the literature?\n\nWe will use the additional content page of the camera-ready version to add the description of the general strategies used by LLM-generated heuristics. In addition to Spanner and Blocksworld, we will also add a brief description of the main ideas of the R1-generated heuristics that where selected in our training phase.\n\nBelow we briefly summarize the general strategy used by these selected heuristics.\n\nThese LLM-generated heuristics *do not use general strategies common in the planning literature* such as linear combinations of state variables, correlation complexity, relaxations, or standard decomposition methods.\n\nIn most generated heuristics the general strategy is a domain-dependent decomposition of the problem. The heuristic identifies the remaining subgoals (packages to be delivered or tiles to be painted) and sums the estimated costs to achieve each one independently. This often involves calculating movement costs via shortest-path algorithms (precomputed or calculated on-demand) and adding costs for other necessary actions (picking up an object or painting a tile). The heuristics then offset the final value to take into account identified interactions between these subgoals.\n\n>  I missed having more details on the computation time to create the heuristic, as well as computation time to evaluate the heuristic.\n\nThe time to generate the heuristic depends on the limitations of the LLM API used. For the case of Gemini 2.0 Flash, we ask for three heuristics per minute, thus to generate the 200 heuristics we need 67 minutes. However, the limit of the API is 15 calls per minute, thus we could reduce the time to 13 minutes. In the case of DeepSeek models there is no limit for the number of calls, thus we can generate the 200 heuristics simultaneously. We generate the R1 heuristics in a longer period to monitor the process, but it could be done in parallel.\n\nRegarding the time to evaluate the heuristics. We have chosen to use all training tasks to select the best heuristic to obtain the simplest approach possible. However, our method allows using a smaller set of tasks to select the best heuristic if the computational resources are limited.\n\nWe ran two additional experiments to analyze this further. We used two different subsets of tasks from the training set to select the best R1-generated heuristic: six tasks distributed over the training set (including the smallest and the largest task), and two tasks (only the smallest and the largest task). We ran the experiment with the exact same setup as in the paper. The results are shown in the table below:\n\n| Training Subset                     | Tasks Solved |\n|-------------------------------------|--------------|\n| Smallest, Largest and 4 Random Tasks| 374          |\n| Smallest and Largest Task           | 361          |\n| All Training Tasks                  | 373          |\n\nAs shown in the table, using only six tasks we achieve performance similar to using all training tasks. In this case, the worst case time to evaluate the 25 heuristics per domain over the six tasks with a time limit of five minutes would be 25 * 6 * 5 = 750 minutes (twelve hours and thirty minutes), which is far less than the 24 hours available per domain during the IPC Learning Track 2023. We could further reduce this time by using only two tasks which would result in four hours and ten minutes.\n\n> Table 3, clarify number of failed heuristics out of how many? The table could also be more informative if shown as a figure.\n\nThank you for the suggestion! The number of failed heuristics is out of 200 (25 * 8). We will clarify this in the paper.\n\n> No mention was added with respect of testing problems that have already been used for training the LLM. The paper cited below contains heuristics which are very similar to the one produced by the LLM in Blocksworld, as well as well known strategies to solve blocksworld suboptimally.\n\nTo address the concern of problems used for the training the LLM, we ran three additional experiments designed to test whether the LLMs are retrieving memorized heuristics or reasoning about the provided PDDL domain.\n\n1. Domain Modification (Spanner): We modified the Spanner domain so that spanners are not consumed after use. If the LLM had merely memorized a known heuristic for Spanner, it would fail to account for this change. However, the generated heuristic for the modified domain correctly adapted to the new semantics. The best generated heuristic is indeed *perfect* for this modified domain, and thus  produces optimal plan costs for all states. This suggests the LLM reasoned about the given domain rather than retrieved a memorized solution.\n\n2. Predicate Obfuscation (Blocksworld): We created an obfuscated version of the Blocksworld domain where all components names were replaced with random strings as done by Valmeekam et al. 2023. We translated the Blocksworld tasks used in the paper and ran an experiment with the exact same setup as in the paper. The results are shown in the table below:\n\n| domain                 | Fast Downward FF | Pyperplan R1 |\n|------------------------|------------------|--------------|\n| Blocksworld            | 27               | 66           |\n| Obfuscated Blocksworld | 28               | 40           |\n\nAs shown in the table, the performance of the classical planner (Fast Downward with FF) remained stable (modulo noise), as expected. The performance of the R1-generated heuristic degraded but still outperformed the FF baseline. This indicates that while semantic cues in predicate names are helpful, the LLM is still capable of reasoning about the logical structure of the domain. We note that this experiment is a highly adversarial setting for LLMs, because they are trained to take into account the semantics of the tokens and not operate on random strings.\n\n3. Novel Domain (Rod-Rings): We designed a new domain, Rod-Rings, which has never been made available online nor fed to an LLM. It features sticks with stacks of rings and a single \"held\" ring. Two moves are allowed: (a) place the held ring at the bottom of a stick, swapping it with the top ring, or (b) place the held ring on top of a stick, swapping it with the bottom ring. The goal is to arrange specific rings on specific sticks in a defined order.\n\nTo ensure the domain remains novel, we used an OpenAI model (O3) via their API, which guarantees that API data is not used for model training nor stored. To be able to compare to the results of the paper, we also provide results for O3-generated heuristic on the domains used in the paper.\n\n| domain                       | Fast Downward FF | Pyperplan O3 |\n|------------------------------|------------------|--------------|\n| Rod-Rings                    | 59               | 58           |\n| Paper Domains (IPC Learning) | 295              | 354          |\n\nOn this new domain, the O3-generated heuristic guiding a GBFS solves 58 tasks, almost as many as Fast Downward guided by FF which solves 59 tasks. This suggest that the LLM reasons about this unseen domain.\nThe results for the other domains for the O3-generated heuristics are inferior to the R1-generated heuristics which solve 373 tasks.\n\nTogether, these experiments indicate that the success our method is not due to heuristics memorized during training but to the LLMs' ability to generate domain-dependent heuristic functions by reasoning about the logical structure of the domain.\n\n- Valmeekam et al.: On the Planning Abilities of Large Language Models - A Critical Investigation. NeurIPS 2023."}, {"review_id": "odvLauGzKo", "reviewer": "Reviewer_BKh1", "summary": "The paper proposes using LLMs to generate domain-dependent heuristic functions in Python and integrating them into the Pyperplan planner for PDDL domains. This pipeline outperforms pure LLM planning that does not use PDDL. Unlike prior work, which prompts the LLM to generate a plan or develops complicated pipelines for LLM-based planning, this paper takes a PDDL description as input and outputs a heuristic that can be directly integrated into an off-the-shelf planner. The results indicate that LLM-generated heuristics can solve more planning tasks than domain-independent heuristics while being competitive with learning algorithms for domain-dependent planning. The LLM-generated heuristics are generally efficient to compute and can even be more informative than state-of-the-art heuristics, resulting in fewer node expansions.", "questions": "- Could you run obfuscation experiments, where the domains, predicates, actions, etc., are completely renamed? This would help understand the drivers of performance and whether the LLM is fully utilizing the given PDDL specification to generate heuristics or if the LLM's behavior is similar to parametric retrieval based on the domain name. A small performance degradation could indicate that LLMs can generate heuristics for novel PDDL domains they have not encountered before.\n- Could you add more detailed reporting of the quantitative results (e.g., the runtime of heuristic functions in C++/Python, number of expansions, and plan length)? To make the results fully comparable and eliminate the impact of differences in frameworks, re-implementing a set of heuristics in Fast Downward would also be beneficial. A subset of the best R1-generated heuristics would already improve the paper.\n- An additional interesting experiment would be to fully adhere to the competition rules (32GB of RAM, no GPU, select suitable model & quantization) and see how far LLMs running on CPUs can be pushed. This would result in fully comparable performance metrics and help assess how close LLMs really are to the state of the art in this domain, considering that \"Challenging the State of the Art\" appears in the paper's title. This is a nice-to-have suggestion, not a requirement.", "limitations": "- There are no significant ethics concerns or potential negative social impact. Limitations are discussed interspersed throughout the text. The authors could point out that this method relies on PDDL. While the proposed method is significantly superior to purely LLM-based planning when the problem is easily expressible in PDDL, LLM-based planning does not have this dependency, which makes it a more general approach.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths\n- The paper tackles a relevant research question: How can LLMs be integrated into classical planning? The quality of the heuristic function is essential for efficient planning, so applying an LLM to improve it makes sense.\n- The paper is well-written and easy to follow.\n- The method is simple compared to complex LLM planning pipelines, which is a significant strength. The results are promising and consistent across domains. The computational efficiency gains over end-to-end LLM planning are significant, especially as the generated heuristics can be re-used for multiple tasks.\n- The difference between this work and prior work is discussed in detail.\n\nWeaknesses\n- The method uses LLMs to create domain-specific heuristics for well-known planning domains. Some of the domains are very well-known, and, to my knowledge, all of them have been published before. It is unclear whether the LLM is genuinely synthesizing novel heuristics based on the PDDL description or if it is simply performing retrieval, ensembling, and/or adaptation of known solutions for known problems. Prompting the LLM for 25 candidates could essentially be hill-climbing on memorized fragments.\n- A Python-based planner outperforming a C++-based Fast Downward is an impressive result. However, the paper could provide more details, such as average/median number of node expansions and plan length, to understand the significance of these results. Figure 2 gives some answers but is insufficient alone.\n- While the issue with memory limit for the training phase is documented (Lines 138-139), it is still a concern in terms of fairness. Furthermore, the IPC 2023 competition rules did not allow the use of GPUs. Considering the size of DeepSeek models and the lack of public details on Gemini models, only the Distill Qwen 14B is somewhat comparable to the baselines in terms of memory usage during inference. This model is outperformed by the domain-independent heuristic h^{FF}. On the other hand, recent work [1] has noted that successfully scaling up GPU compute in these tasks is a non-trivial problem, with neural network-based methods struggling to outperform classical ML methods. From this perspective, this paper suggests a promising solution.\n- In addition to FunSearch and Ling et al., which the paper cites, there is other recent work [2-5] doing LLM-based heuristic generation for non-PDDL tasks. In addition to LLM-based sampling of heuristics proposed by this paper, some of these papers include reflective evolution and search that utilizes diversity. On the other hand, the authors acknowledge the feedback loop as a direction for future work, and the paper achieves strong results in PDDL domains even without it.\n\n[1] Chen, D. Z., Trevizan, F., & Thiébaux, S. (2024). Return to tradition: learning reliable heuristics with classical machine learning. In Proceedings of the International Conference on Automated Planning and Scheduling (Vol. 34, pp. 68-76).\n\n[2] Dat, P. V. T., Doan, L., & Binh, H. T. T. (2025). Hsevo: Elevating automatic heuristic design with diversity-driven harmony search and genetic algorithm using llms. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 39, No. 25, pp. 26931-26938).\n\n[3] Ye, H., Wang, J., Cao, Z., Berto, F., Hua, C., Kim, H., ... & Song, G. (2024). Reevo: Large language models as hyper-heuristics with reflective evolution. NeurIPS 2024\n\n[4] Liu, F., Tong, X., Yuan, M., Lin, X., Luo, F., Wang, Z., ... & Zhang, Q. (2024). Evolution of heuristics: Towards efficient automatic algorithm design using large language model. ICML 2024\n\n[5] Zheng, Z., Xie, Z., Wang, Z., & Hooi, B. (2025). Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design. arXiv preprint arXiv:2501.08603.", "was_revised": true, "final_justification": "The authors' rebuttal addresses the main concerns of generalization to other PDDL domains, lack of detail in the description of the results, and experiments with smaller models. I think the paper can be accepted if these changes are incorporated. I believe the main remaining weaknesses are the somewhat incremental nature of the paper (using LLMs to generate heuristics has been proposed before), the somewhat narrow application area of PDDL planning, and the relative lack of generalizable insights to other problem areas.", "rebuttal": "Thank you for the suggestions and for your careful read of the paper! We address your concerns and present the requested experiments below.\n\n> Could you run obfuscation experiments, where the domains, predicates, actions, etc., are completely renamed? This would help understand the drivers of performance and whether the LLM is fully utilizing the given PDDL specification to generate heuristics or if the LLM's behavior is similar to parametric retrieval based on the domain name. A small performance degradation could indicate that LLMs can generate heuristics for novel PDDL domains they have not encountered before.\n\nTo address the concern of parametric retrieval based on the domain name, we ran three additional experiments designed to test whether the LLMs are retrieving memorized heuristics or reasoning about the provided PDDL specification.\n\n1. Domain Modification (Spanner): We modified the Spanner domain so that spanners are not consumed after use. If the LLM had merely memorized a known heuristic for Spanner, it would fail to account for this change. However, the generated heuristic for the modified domain correctly adapted to the new semantics. The best generated heuristic is indeed *perfect* for this modified domain, and thus  produces optimal plan costs for all states. This suggests the LLM reasoned about the given domain rather than retrieved a memorized solution.\n\n2. Predicate Obfuscation (Blocksworld): We created an obfuscated version of the Blocksworld domain where all domain, predicates, actions, etc... are completely replaced with random strings as done by Valmeekam et al. 2023. We translated the Blocksworld tasks used in the paper and ran an experiment with the exact same setup as in the paper. The results are shown in the table below:\n\n| domain                 | Fast Downward FF | Pyperplan R1 |\n|------------------------|------------------|--------------|\n| Blocksworld            | 27               | 66           |\n| Obfuscated Blocksworld | 28               | 40           |\n\nAs shown in the table, the performance of the classical planner (Fast Downward with FF) remained stable (modulo noise), as expected. The performance of the R1-generated heuristic degraded but still outperformed the FF baseline. This indicates that while semantic cues in predicate names are helpful, the LLM is still capable of reasoning about the logical structure of the domain. We note that this experiment is a highly adversarial setting for LLMs, because they are trained to take into account the semantics of the tokens and not operate on random strings.\n\n3. Novel Domain (Rod-Rings): We designed a completely new domain, Rod-Rings, which has never been made available online nor fed to an LLM. It features sticks with stacks of rings and a single \"held\" ring. Two moves are allowed: (a) place the held ring at the bottom of a stick, swapping it with the top ring, or (b) place the held ring on top of a stick, swapping it with the bottom ring. The goal is to arrange specific rings on specific sticks in a defined order.\n\nTo ensure the domain remains novel, we used an OpenAI model (O3) via their API, which guarantees that API data is not used for model training nor stored. To be able to compare to the results of the paper, we also provide results for O3-generated heuristic on the domains used in the paper.\n\n| domain                       | Fast Downward FF | Pyperplan O3 |\n|------------------------------|------------------|--------------|\n| Rod-Rings                    | 59               | 58           |\n| Paper Domains (IPC Learning) | 295              | 354          |\n\nOn this new domain, the O3-generated heuristic guiding a GBFS solves 58 tasks, almost as many as Fast Downward guided by FF which solves 59 tasks. This suggest that the LLM reasons about this unseen domain.\nThe results for the IPC Learning domains for the O3-generated heuristics are inferior to the R1-generated heuristics which solve 373 tasks.\n\nTogether, these experiments -- modifying an existing domain, obfuscating one domain and testing on a novel domain -- indicate that the success our method is not due to parametric retrieval based on the domain name but to the LLMs' ability to generate domain-dependent heuristic functions by reasoning about the logical structure of the domain.\n\n- Valmeekam et al.: On the Planning Abilities of Large Language Models - A Critical Investigation. NeurIPS 2023.\n\n> Could you add more detailed reporting of the quantitative results (e.g., the runtime of heuristic functions in C++/Python, number of expansions, and plan length)? To make the results fully comparable and eliminate the impact of differences in frameworks, re-implementing a set of heuristics in Fast Downward would also be beneficial. A subset of the best R1-generated heuristics would already improve the paper.\n\nYes, we will add a detailed report with the requested information in the appendix of the camera-ready version. Below you can find the a table with the number of expansions per second for the FF heuristic in Pyperplan and Fast Downward for the subset of tasks solved by both planners. The table shows the difference in performance between the two planners using the same search algorithm (GBFS) and the same heuristic (FF).\n\n| Domain (Tasks)        | Python   | C++       | Performance Increase |\n|-----------------------|----------|-----------|----------------------|\n| Blocksworld (24)      | 6964.21  | 142621.78 | 20.48                |\n| Childsnack (17)       | 14495.45 | 190385.84 | 13.13                |\n| Floortile (10)        | 27486.89 | 229067.58 | 8.33                 |\n| Miconic (74)          | 4878.33  | 37715.63  | 7.73                 |\n| Rovers (27)           | 3410.42  | 63064.41  | 18.49                |\n| Sokoban (31)          | 1350.62  | 37400.46  | 27.70                |\n| Spanner (30)          | 25312.26 | 44137.59  | 1.74                 |\n| Transport (29)        | 1162.04  | 8559.27   | 7.37                 |\n\nAs we can see, the C++ is significantly faster in general. In 7 out of the 8 domains, the C++ implementation is at least 7x faster and sometimes even 20x faster.\n\nWe used an LLM to directly translate the R1-generated heuristics for the two domains with the lowest coverage, Childsnack and Floortile, into C++ code for Fast Downward. The results are shown in the table below:\n\n| Domain      | Pyperplan R1 | Fast Downward R1 |\n|-------------|--------------|------------------|\n| Childsnack  |           22 |               26 |\n| Floortile   |            4 |                5 |\n\nThe results for \"Fast Downward R1\" should be taken with a grain of salt, as the translation from Python to C++ is very direct and not optimized in any way. Also, our method chooses the heuristic (among the 25 generated heuristics) that works best in Pyperplan, not in C++.\n\n> In addition to FunSearch and Ling et al., which the paper cites, there is other recent work doing LLM-based heuristic generation for non-PDDL tasks. In addition to LLM-based sampling of heuristics proposed by this paper, some of these papers include reflective evolution and search that utilizes diversity. On the other hand, the authors acknowledge the feedback loop as a direction for future work, and the paper achieves strong results in PDDL domains even without it\n\nThank you for the suggestions! We agree that adding to our approach techniques, such as reflective evolution and search that utilize diversity, could bring even further benefits. However, our method shows that even a straightforward method can already be useful to create classical planning heuristics.\n\n> An additional interesting experiment would be to fully adhere to the competition rules (32GB of RAM, no GPU, select suitable model & quantization) and see how far LLMs running on CPUs can be pushed. This would result in fully comparable performance metrics and help assess how close LLMs really are to the state of the art in this domain, considering that \"Challenging the State of the Art\" appears in the paper's title. This is a nice-to-have suggestion, not a requirement.\n\nWe ran a local experiment with Qwen3 4B using a NVIDIA GeForce RTX 4090 with 24GB of VRAM. This is a popular GPU that is commonly used also in personal computers. To generate 25 heuristics sequentially, we need 4h33m on average. (One could generate two heuristics in parallel with the available VRAM, but we stick to a single process.)\n\nThe results are as follows:\n\n| Domain       | Qwen3 4B |\n|--------------|----------|\n| Blocksworld  |       27 |\n| Childsnack   |       12 |\n| Floortile    |        3 |\n| Miconic      |       90 |\n| Rovers       |       31 |\n| Sokoban      |       26 |\n| Spanner      |       30 |\n| Transport    |       44 |\n| Total        |      263 |\n\n\nThis shows that a \"small LLM\" can already outperform the FF heuristic in Pyperplan. It has strictly higher coverage in 4 out of the 8 domains, and it ties with FF in another domain.\n\nAs LLMs are optimized for GPU used, running an experiment without GPUs is impractical. Moreover, it is not uncommon in the planning literature that methods use GPU during learning phase, and switch to CPU-only during planning. A few recent examples (including Chen et al., which introduce $h^{WLF}\\_{GPR}$ that we compared to):\n\n- Dillon Z. Chen, Sylvie Thiébaux, Felipe W. Trevizan: Learning Domain-Independent Heuristics for Grounded and Lifted Planning. AAAI 2024: 20078-20086\n- Dillon Z. Chen, Felipe W. Trevizan, Sylvie Thiébaux: Return to Tradition: Learning Reliable Heuristics with Classical Machine Learning. ICAPS 2024: 68-76\n- Simon Ståhlberg, Blai Bonet, Hector Geffner: Learning Generalized Policies without Supervision Using GNNs. KR 2022\n- Simon Ståhlberg, Blai Bonet, Hector Geffner: Learning General Policies with Policy Gradient Methods. KR 2023: 647-657\n\nWe could include this result as a new column in our Table 1, if the reviewers find it useful."}]

Author rebuttal:

Meta-review: # Meta Review

Please provide detailed and convincing justifications for your recommendation, including but not limited to
(a) Summarize the scientific claims and findings of the paper based on your own reading and characterizations from the reviewers.
(b) What are the strengths of the paper?
(c) What are the weaknesses of the paper? What might be missing in the submission?
(d) Provide the most important reasons for your decision to accept/reject. For spotlights or orals explain why the paper stands out (other than by high scores or popularity trends).
(e) Summarize the discussion and changes during the rebuttal period. What were the points raised by the reviewers? How were each of these points addressed by the authors? How did you weigh in each point in your final decision? (Do not mention reviewer names. Use their anon ids instead.)

# Summary 

The paper proposes an approach of leveraging LLMs for classical planning approaches. Specifically, the proposed approach is to   
1. Use LLMs to generate multiple domain-specific heuristics function as a python code
2. Then use the training set tasks with greedy bfs to compare the generated heuristics and select the best one
3. Finally, use the selected heuristics to tackle out-of-distribution test tasks. 

The experiments compare their heuristics  with traditional domain-independent heuristics as well as SOTA domain-specific heuristics. They also compare the proposed planning approach to LLM-based end-to-end planning. Their experiments show signigicant improvement in coverage of tasks with the LLM-generated heuristics.

# Strengths

- **Novelty**:  The paper situates itself well within the recent surge of LLM‑based planning research and is well motivated to contribute improvements to a key component---heuristics generation---in planning pipeline.
- **Comprehensive Evalations**: The paper reports comparison of the proposed LLM-generated heuristics with domain-dependent and domain-independent heuristics as well as it compares with ned-to-end LLM based approach. The ablation study provides sensitivity analysis for each component of the prompt. Finally, the discussion on generated heuristics provide good insight on the LLMs ability to be used for the such tasks.
- **Transparency & Reproducibility**:  Supplementary material provides detailed prompts and example code, which aids reproducibility and transparency. (quoting Reviewer K8zo)
- **Reliability**: Since the proposed approach uses LLMs for a well-defined component, the produced code can be verified and evaluated in a controlled manner. Promoting reliability of the proposed solution.


# Weakness

- **Limitation on natural-language planning problems**: One major concern is that the proposed approach is not evaluated on planning problems that are expressed in natural language. The experiments on the pipeline `NL -> PDDL -> Heuristic Generation -> Solve with Planner` would have addressed that. But authors mention it as future work. (Reviewer VEfu)
- **Limited Details on existing heuristics**: The paper lacks explanation of existing heuristics used in the baseline (Reviewer 2xoe)



# Reviewer concerns


- **Relevance to NeurIPS**: One major concern raised (by reviewer VEfu) is the fit for NeurIPS. As the paper proposes an approach specifically for planning problems described in PDDL, the paper might be a better fit for a planning conference. I tend to disagree. 
    1. The submission to NeurIPS are not restricted by the formal representation used by a paper. The call for papers in NeurIPS mention: 
> We invite submissions presenting new and original research on topics including but not limited to the following:[..] Reinforcement learning (e.g., decision and control, planning, hierarchical RL, robotics). 
    2. There is enough interest in planning and the PDDL representation at NeurIPS itself, as illustrated by authors.
- **Prompt Engineering**: Reviewer K8zo raises that the prompt used to generate the heuristics is long, has multiple components (including PDDL instance and domain files, two examples from another domains, and a checklist for instructions). However, their ablation study analyzes the sensitivity to prompts. Additionally, the baseline domain-dependent heuristics approaches get similar information as that mentioned in the prompt, so comparison is fair as well. 
- **Unfair end-to-end planning baseline comparison**: The paper proposed a heuristics generation approach that is used for planning problems described in PDDL. They compare it with SOTA domain-specific heuristics as well as end-to-end planning approaches. Reviewer VEfu highlights that comparison to end-to-end planning approaches is unfair for coverage and a comparison that is controlled for FLOPS and time would resolve the issue. The authors provide convincing evidence that even when controlled for FLOPS the heuristics generation out-performs end-to-end. Although this was trivial given heuristics generation is domain-specific and end-to-end is problem specific. Besides, End-to-end planning is one of the baselines. The paper also compares against domain-independent and domain-dependent heuristics
- **Small Gap from the best existing heuristics**: Reviewer VEfu highlights that the presented approach does not have significant improvement over $h^{WLF}_{GPR}$ and hence more exploration in terms of approaches should be done.   
    1. I believe the difference in the coverage is still significant given that $h^{WLF}_{GPR}$ was run in C++ and the LLM generated heuristic was generated
    2. While I agree that much more can be done to show more substantial gap, but the novelty of the approach is not undermined by lack of exploration of dufferent approaches..
- **Experiments with Smaller Models**: (Reviewer K8zo) The experiments uses large, strong models for heuristics generation. It is not clear if the approach would work with smaller models. The authors rebut this by providing results with smaller Qwen model (4B).
- **Retrieval from memory**: Reviewer  VEfu and MPk1 raised the concerns that the evaluated domains might already be part of pre-training data in LLM. The author rebuttal addresses this concern by providing experiment results with domain modification, obfuscation and introducing a novel domain. All of which makes the paper stronger.

# Recommendation Justification

The paper makes a solid contribution to using LLMs for planning besides extracting work-model or translating NL to PDDL, which has been explored by existing literatures. The thorough empirical envaluations and provided supplementary invokes confidence in the proposed approach.  The remaining concerns from the reviewer do not take away from the contribution of the paper; as I reflect in the reviewer concerns section above.
Decision: Accept (poster)