- Rating
- 4
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
This work provides a novel approach for generating domain-independent planning heuristics by combining LLMs and genetic algorithms. It builds on recent works, such as AlphaEvolve, using LLM-driven evolutionary algorithms for generating novel code and algorithms. This paper can be seen as an application of the paradigm above to the field of Automated Planning.
Overall, my impression of the paper is very positive, and I strongly lean towards paper acceptance. Still, the paper has some issues, which I comment in the following sections. Regardless, domain-independent heuristics have a longstanding tradition in Automated Planning, and are key to solving tasks efficiently. Showing, as this paper does, that LLM-based approaches can come up with interesting, domain-independent heuristic designs is a significant contribution to the field of Automated Planning and, more broadly, to the study of reasoning capabilities of LLMs.
The proposed approach (LLMs + genetic algorithms) is sound and aligns with existing research on LLM-guided evolution of programs (e.g., AlphaEvolve). Also, the authors perform extensive experimentation, showing that LLM-generated heuristics span both slow but powerful heuristics (akin to lmcut) and the opposite case of fast but inaccurate heuristics (akin to goalcount). Moreover, LLM-generated heuristics are evaluated on well-known planning benchmarks (IPC and Autoscale tasks) spanning a diverse set of tasks (although scope is limited to satisficing and not optimal planning, as the authors themselves note). Results are very positive, showing that LLM-generated heuristics are competitive with existing handcrafted heuristics and even better in some cases. Finally, they analyze some of the LLM-generated heuristics, showing that many are very similar to the existing FF heuristic but others propose truly novel ideas beyond implementation improvements and heuristic combinations. Consequently, I believe in its current form the paper is already novel, sound and provides a significant contribution to the Automated Planning community and the AI community in general. Despite this, some things should be improved (more information below).
Critical strengths
In my opinion, this paper "ticks all the boxes" towards acceptance in a major AI conference/journal. The major strenghts can be summarized as follows:
-
The paper shows that LLM-based approaches (+ genetic algorithms) can generate domain-independent heuristics that rival, and even sometimes outperform, those created by humans. This contribution is novel and clearly significant, given the longstanding tradition of domain-independent heuristics in the field of Automated Planning.
-
The authors perform extensive experimentation to support their claims. They use well-known benchmarks (IPC + the newer Autoscale) comprising a large and wide variety of tasks, focused on satisficing instead of optimal planning. Additionally, they analyze some of the LLM-generated heuristics. Altogether, results are conclusive and their findings are well-supported: LLMs are clearly capable of generating powerful domain-independent heuristics.
Critical weaknesses
I believe the paper exhibits some weaknesses and points for improvement, although I do not believe any of them to be critical. My criticism can be summarized in two points:
-
Overall, the paper is somewhat dense and some parts are hard to follow. The general approach (LLM+MAP-elites) is well-explained. However, other parts, especially regarding experimental results, are dense and need to be read several times in order to be understood. Some examples: "kernel-density estimate of improvement events" (caption of Fig. 3), what is this "kernel-density of events"?; explanation of algorithm 3 is hard to understand, especially for readers unfamiliar with DTG and CG); "exact two-sided permutation tests over all 48 620 relabelings of the 18 runs find no significant difference in training-score means (p = 0.60), group maxima (p = 0.21) or dispersion (Brown–Forsythe, p = 0.17)" (lines 267-270), what is meant by "two-sided permutation tests over relabelings"? As I commented previously, the experimentation of the paper is very exhaustive, which is good. However, this should not result in the paper being hard to read.
-
Although Section 4.2 provides insight into the LLM-generated heuristics, I would like to see an even deeper analysis. Although it is important than LLM-generated heuristics are competitive with handcrafted heuristics, I believe it is even more interesting to understand the type of approaches LLMs come up with, and how novel these are. I would think of three main categories of "LLM-based contributions", in increasing significance: (A) LLMs improving the low-level, C++ implementation of existing heuristics; (B) LLMs selecting configuration parameters of existing heuristics and combining approaches that already exist (akin to planning portfolios); (C) LLMs coming up with novel approaches that do not exist in the related literature. In Section 4.2, you provide examples of (A) and (B) (e.g., evolved-blind-medium-1 combining FF with dead-end checks), whereas evolved-blind-none-3 would fall between (B) and (C) (does it simply combine DTG and CG-based heuristics, or did it discover a truly novel approach?) I understand this question may be hard to answer, but such an analysis would prove immensely useful for the Automated Planning community.
Questions for authors
I have three main points for improvement, the first two already described above.
The first is to improve the overall clarity of the paper, especially regarding experiment results. Also, Figures 1 and 2 are a little confusing due to the large amount of different symbols, so I would clearly differentiate between LLM-generated heuristics and handcrafted heuristics. Additionally, I would explain what a "kernel-density estimate of improvement events" in Fig. 3 is or, else, use a different metric for measuring the number of improvements per iteration.
The second is to extend the analysis of LLM-generated heuristics in Section 4.2. As a reader, I would like Section 4.2 to answer the following question: what type of approaches (i.e., heuristics) can LLMs come up with, and how novel are these? This analysis could be framed in terms of the three categories (A), (B), (C) I proposed above (or some others). Regardless, I would like to know whether LLMs can only combine and incrementally improve existing heuristics or whether they can design truly novel approaches. The heuristic evolved-blind-none-3 seems to be in this direction, but to me it is unclear how much of Algorithm 3 is truly novel, and how much of it is an integration of DTG + CG + some "parameter tuning". I would like to emphasize that, even if current LLM-based approaches can only achieve (A) and (B) (which they do), that is already significant, so I believe the paper should be accepted regardless of the extend to which current LLMs achieve (C). Also, I acknowledge that performing such an analysis may be complicated, and the results may depend on the actual LLMs used (e.g., it is possible that frontier models would not converge so much to FF and discover truly novel heuristics). Still, performing additional analysis on the heuristics generated by the current system would provide useful insight into this question of "heuristic novelty".
The third point regards the training artifact for experiments on medium and low reasoning effort (see lines 254-257). If the exhaustion of API credits interfered with the metrics used to guide evolution and, thus, with the results of Figure 3, then that is not acceptable and the experiments should be ran again. In general, results should not depend on the compute load of the nodes used to run the experiments (this effect should be removed or accounted for).
Below, I provide some minor points:
- Can you provide some more information about the heuristic API LLMs have access to? It would be interesting to know if they only have access to low-level planning data-structures or if they also have access to high-level procedures, e.g., a function to compute delete-relaxation, justification graph of lmcut, etc.
- Have you analyzed the impact of prompting the LLM, when mutating a heuristic, with the best individuals of the island (current approach) vs not doing so? Providing the best individuals as context may help the LLM but also harm diversity.
- There is one aspect of your MAP-elites implementation that should be clarified. On the one hand, island cells correspond to different combinations of informedness and speed. However, your fitness function combines both into coverage (+ agile score). How do both play together? For instance, what happens with island cells c-i that are dominated (i.e., are worse in both informedness and speed) by another cell c-j? I would expect every heuristic in c-i to have worse fitness than c-j, so keeping c-i would mean keeping low-fitness individuals. Do you maintain these cells or is only the pareto frontier kept?
3 comments
Official Comment by Authors Continued
evolved-blind-none-2:301(iteration 301 ofevolved-blind-none-2). This heuristic precomputes parent-conditioned DTG distances. Standard DTG distances ignore preconditions on other variables, and this heuristic attempts to add the most important cross-variable constraints back. For each goal variable, it identifies its most influential parent goal in the causal graph and precomputes DTG distances conditioned on each possible value of that parent (using only actions compatible with that parent value). When evaluated, if the parent goal is not yet satisfied, the heuristic uses the DTG distance conditioned on the parent's current value if larger than ordinary distance. This can be viewed as a fast, precomputed single-parent approximation of a causal-graph heuristic.
While our previous cluster was decommissioned, we benchmark these two new heuristics against FF, LM-Count and evolved-blind-medium-1 (the best performing heuristic from the paper) on our new cluster:
| Heuristic | IPC Cov (/720) | Autoscale Cov (/1920) | Total Cov (/2640) |
|---|---|---|---|
FF | 353 | 1,105 | 1,458 |
LM-Count | 317 | 1,194 | 1,511 |
evolved-blind-medium-1 | 355 | 1,178 | 1,533 |
evolved-blind-medium-1:159 | 357 | 1,243 | 1,600 |
evolved-blind-none-2:301 | 318 | 1,052 | 1,370 |
Interestingly, evolved-blind-medium-1:159 outperforms all these heuristics on both IPC and Autoscale, indicating that it likely would have outperformed all heuristics also on the original cluster.
As you suggest, we also expect that SoTA LLMs would be more capable of and prone to generate novel heuristics in categories C and D.
We used the one page CRC extension to include the above discussion and tables in the paper as Section 6.
Training Artifacts
To remove this effect from Figure 3, we have truncated the plot in the main paper at iteration 210, which is the earliest point at which any run was resumed after credit exhaustion (keeping the full 320-iteration plot in the Appendix C.1, Figure 5). Across all 18 runs, 81% of iterations ran before any resumption, and truncating at iteration 210 still preserves all the trends and conclusions we discuss in Section 4.1.
We also checked how large the score difference actually was on the remaining 19% of iterations.
In 9 of the 11 resumed runs, the LLMs generated an identical C++ heuristic both before and after resumption and using these regenerated programs, we found the mean score drops ( for blind-seeded runs and for FF-seeded runs).
We then post-hoc compensated for these changes in Appendix C.1 (Figure 6), further indicating continual progress across all generations.
However, we note that this is a coarse-grained measure with few samples (7 and 12 pairs respectively).
All test-set results in Section 5 were evaluated separately and with interleaving, and are as such unaffected.
Minors
Heuristic API: A complete description of the heuristic API, the same as given to the LLMs, is given in appendix B.2. To summarize, it consists of all the tools available to a human writing heuristics for Scorpion, including high level DTG-, CG- and relaxation-tools.
Prompting impact: We have not conducted any evaluations on this, as our ability to perform ablations was limited by compute and cost. However, we agree that this and other ablations would make interesting directions for future work.
MAP-Elite Cells: You're correct that cell c-i almost certainly would have worse fitness than c-j. However, as c-i might have made interesting architectural choices, we keep both in the archive. While this means that c-i can be sampled as a parent, we only select the top heuristics from the island as further inspiration which will (likely) not include c-i. In this way, c-i can remain to as a diversity source when sampled as a parent, while only having the pareto frontier act as inspiration. As such, our system implicitly gives more weight to c-j and the pareto front. Keeping only the pareto frontier would however, again, be interesting to explore in future work.
Thank you very much for your answers and clarifications. All my points have been addressed. I find especially interesting your extended novelty analysis which shows that, despite impressive LLM results, no truly novel heuristic is found by LLMs. These results align with existing research on limitations of current LLM systems. Still, I agree that future LLMs may come up with class D heuristics.
I keep my score of 4, and will fight for paper acceptance.
Congratulations to the authors.
Thank you for the insightful review.
Clarity
Thanks also for your remarks on clarity and presentation. We have gone over these and made improvements in the updated version, especially in the discussion of the results. In particular, in Figure 3 we replaced the normalized KDE of improvement events with a 20-iteration rolling average of new-best-score discoveries per run, analysis remains unchanged, and in Figures 1 and 2 we colored evolved heuristics in orange (
blind-seeded) and red (FF-seeded) against a green-to-blue spectrum for the baselines so they are immediately distinguishable.Further novelty analysis
We first categorise the 18 final heuristics from the paper into five categories:
The results are:
evolved-ff-*)evolved-blind-*)So, all but one of the best performing heuristics from each evolution fall in categories A and B. All FF-seeded heuristics fall into categories A and B1, with the B1 cases all adding the relaxed-plan length to the FF cost. The blind-seeded heuristics fall mostly into B1 and B2, with the exception of
evolved-blind-none-3in category C.Since heuristics in categories C or D may have been evolved during search but pruned due to not being the best performing on the training set, we further audited all intermediate C++ programs generated across the blind-seeded evolutions using three coding agents (medium effort Opus 5.5, Argon and Astra). Each agent first reviewed the full corpus independently, the agents then cross-reviewed each other's findings. None of the agents found a heuristic they classified in category D. All three independently ranked the mechanism of
evolved-blind-none-3as the most novel. After cross-review, all three also agreed on the next two and their orders (most novel first):evolved-blind-none-3(from the paper). While we did not manage to make this very clear in the paper, this heuristic changes standard DTG distance calculations by iteratively penalizing transitions that disturb other goals. Specifically, when a transition's precondition requires another goal variable to take a non-goal value, it adds the DTG distance required to restore that variable back to its goal (rather than the cost of achieving the precondition from the current state). As this is largely independent of the current state, the evaluation of the heuristic consists of table lookups and arithmetic, compared to repeated Dijkstra searches in standardCGheuristics. We have updated the paper to clarify this, and also include a more formal description there.evolved-blind-medium-1:159(iteration 159 ofevolved-blind-medium-1). This heuristic adds a search-history action-reuse penalty toFF. It maintains a per-action counter u[a] across state evaluations during search, weighting each action a in an extracted relaxed plan by 1+min(⌊u[a]/10⌋,2) before incrementing u[a]. Penalizing frequently selected relaxed-plan actions encourages exploration at the action level, whereas novelty in planning is usually defined over state features. The closest work we are aware of is Tuisov & Katz (HSDIP 2021), which prunes preferred operators by "novelty", defined as actions not previously resulting in heuristically better states than the current one; this form of novelty is correlated withevolved-blind-medium-1:159's usage penalty, but clearly distinct from it.