acceptodds
Under review as a conference paper at ICLR 2027

LLM-Evolved Domain-Independent Heuristics for Symbolic AI Planning

Abstract

AI planners rely on heuristic functions that estimate the cost from a state to the goal. The strongest heuristics have been hand-engineered over decades, and while large language models can now synthesize heuristics for a single domain, one heuristic that works on *any* symbolic planning task has remained out of reach. We address this with an evolutionary search over C++ heuristics: LLMs propose code mutations, a MAP-Elites archive keyed by informedness and evaluation speed maintains diversity, and fitness blends coverage with solving time. Benchmarked against nineteen hand-engineered heuristics, our evolved heuristics are both the most informative and among the fastest. On held-out domains they are competitive with the strongest baselines, and our best one outperforms all of them. Further, seeding evolution from the trivial `blind` heuristic yields a similar mean but a higher spread and ceiling compared to seeding from the state-of-the-art `FF` heuristic, and even the `FF` variants it creates beat those evolved from `FF` itself. The evolved programs are ordinary C++ that inherit the soundness and completeness of the underlying search and can be integrated into existing planners. Combining two evolved heuristics inside LAMA solves 50 more held-out tasks, yields a 1.11× speedup to the first plan and improves its aggregate plan-quality score.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
Large Language Models, Automated Planning, Heuristic Search

Reviews

Among:
Shape:
1234this paper, Top 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.67 over 3 reviews, above 99% of the others.
Reviewer_kTsVOpenReview ↗
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

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:

  • A. Implementational tweaks of existing heuristics (e.g. changing data structures or caching strategies in FF)
  • B1. Minor modifications of existing heuristics (e.g. changing FF to return length instead of cost)
  • B2. Combinations of existing heuristics, similar to portfolios (e.g. weighted summation of FF and LM-cut)
  • C. Major modifications to existing heuristics (e.g. changing FF to exclude conflicting actions in relaxed plans)
  • D. A truly novel heuristic, with a mechanism not seen in the literature (e.g. red-black planning at the time of its publication)

The results are:

CategoryFF-seeded (evolved-ff-*)Blind-seeded (evolved-blind-*)Total (/18)
A. Implementational tweaksnone-2, none-3, low-1, low-2, medium-2, medium-3medium-37
B1. Minor modificationsnone-1, low-3, medium-1none-2, low-1, medium-1, medium-27
B2. Combinations--none-1, low-2, low-33
C. Major modifications--none-31
D. Truly novel heuristics----0

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-3 in 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-3 as the most novel. After cross-review, all three also agreed on the next two and their orders (most novel first):

  1. 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 standard CG heuristics. We have updated the paper to clarify this, and also include a more formal description there.
  2. evolved-blind-medium-1:159 (iteration 159 of evolved-blind-medium-1). This heuristic adds a search-history action-reuse penalty to FF. It maintains a per-action counter u[a]u[a] across state evaluations during search, weighting each action aa in an extracted relaxed plan by 1+min⁡(⌊u[a]/10⌋,2)1 + \min(\lfloor u[a] / 10 \rfloor, 2) before incrementing u[a]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 with evolved-blind-medium-1:159's usage penalty, but clearly distinct from it.
AuthorsOpenReview ↗

Official Comment by Authors Continued

  1. evolved-blind-none-2:301 (iteration 301 of evolved-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:

HeuristicIPC Cov (/720)Autoscale Cov (/1920)Total Cov (/2640)
FF3531,1051,458
LM-Count3171,1941,511
evolved-blind-medium-13551,1781,533
evolved-blind-medium-1:1593571,2431,600
evolved-blind-none-2:3013181,0521,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 (0.0290.029 for blind-seeded runs and 0.0480.048 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.

Reviewer_6WjgOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates LLM-driven evolution of domain-independent heuristics for symbolic AI planning. Building on OpenEvolve, the framework uses LLMs to mutate and repair C++ heuristic implementations, with a multi-island MAP-Elites archive maintaining diversity in search informedness and evaluation speed. Candidates are evaluated using greedy best-first search and a fitness function combining coverage with an agile runtime score. Across two held-out benchmarks, the evolved heuristics are competitive with 19 hand-engineered baselines. Integrating two evolved heuristics into LAMA solves 50 additional tasks and achieves a 1.11× speedup to the first plan. The paper also examines initialization and LLM reasoning effort, finding greater outcome diversity from blind initialization and improved code-generation success, but limited quality gains, from increased reasoning effort.

Critical strengths
  1. Challenging objective and reusable artifacts. The paper targets domain-independent heuristics rather than domain-specific solutions. The resulting C++ implementations transfer to held-out domains and require no LLM calls during planning.

  2. Practical benefits beyond standalone evaluation. The evaluation includes 19 hand-engineered baselines and integration into LAMA. Combining two evolved heuristics solves 50 additional tasks and provides a 1.11× speedup to the first plan, demonstrating practical utility.

  3. Useful analysis of performance trade-offs. The paper separately examines search informedness and evaluation speed, showing how evolved heuristics improve performance through different mechanisms. Their complementary strengths also motivate integration into multi-heuristic planners.

Critical weaknesses
  1. Unclear contribution beyond optimizing FF. Two highlighted heuristics closely resemble FF, and the paper does not sufficiently isolate gains from unit-cost estimates, dead-end detection, and implementation optimizations. Controlled FF baselines incorporating these changes would clarify whether evolution discovers substantively new heuristic designs.

  2. Insufficient ablation of the evolutionary framework. The contributions of MAP-Elites, multiple islands, and the LLM pool are not adequately established. Comparisons with simpler LLM-based iterative refinement under matched computational budgets are needed to justify the framework’s complexity.

  3. Limited methodological novelty. The framework largely combines established components—LLM-driven code evolution, MAP-Elites, island-based search, and a weighted fitness objective—within OpenEvolve. Its main novelty therefore appears to lie in applying these techniques to domain-independent planning heuristics rather than introducing a substantially new optimization method. Moreover, two highlighted heuristics remain close to FF, leaving the extent of genuinely new algorithmic discovery unclear.

Questions for authors

Could you please address the concerns raised in the Weaknesses section?

2 comments

Thanks for your review and comments.

FF Ablations

We conducted an ablation study to understand the impacts of the three main components of evolved-blind-medium-1, i.e.:

  1. The Unit-Cost Costs (u-cost)
  2. Dead End Detection (ded)
  3. Optimization of the calculations (opt)

We compared every combination of these components by either adding unit cost or dead end detection to ff (opt = ff), or removing them from our evolved heuristic (opt = bl-m-1). The results are shown in the table below. However, we note that our original cluster was decommissioned, so the results below are not directly comparable to the results in the paper.

optu-costdedIPC Cov (/720)IPC GM Time (s)Autoscale Cov (/1920)Autoscale GM Time (s)
ffNoNo3530.2431,1060.343
ffYesNo3530.2391,1780.270
ffNoYes3530.2361,1020.344
ffYesYes3540.2361,1780.273
bl-m-1NoNo3560.1941,1060.301
bl-m-1YesNo3580.1991,1790.241
bl-m-1NoYes3540.1981,1060.299
bl-m-1YesYes3550.1961,1780.243

Here, we see that the largest coverage gain comes from the unit cost component on Autoscale, gaining 73.25 more solves on average (p < 1e-10). On IPC, all domains are already unit cost, so the u-cost component makes no noticeable difference. The dead end detection shows no effect. The optimization of the calculations (opt) has a minor impact on coverage, adding only 3.75 more solves on average (p < 0.05). However, it has a significant impact on the time to solution, giving an average speed up in solution time of 1.21x on IPC and 1.13x on Autoscale for commonly solved instances (p < 1e-3 each respectively).

All p-values calculated with one-sided Wilcoxon signed-rank test, with the null hypothesis that the two heuristics are equal.

Further Ablations

We agree that further ablations and simpler approaches would be beneficial, but it was not economically or computationally feasible in our initial study. Further, due to the cluster decommission, we are unable to run additional ablations at this time.

Methodological & Heuristic Novelty

While we agree that the core components of our approach are based on existing tools, especially on OpenEvolve, we are to our knowledge the first to show that LLMs can optimize for tasks that are this broad using these methods. The previous works had looked at more specific tasks, such as generating heuristics exclusively for binpacking, the equivalent of a single planning domain. Designing domain-independent heuristics is a much more challenging task.

To enable this, we introduced planning-specific choices we believe are novel and will be widely useful for future work, including:

  1. a tunable score function to balance between coverage and speed,
  2. a repair step suitable for the complex C++ code base, and
  3. the first explicit benchmark of evaluation speed and informedness of heuristics.

For a more extensive discussion of the novelty for evolved heuristics themselves, please see Further novelty analysis in our response to reviewer kTsV below.

Thank you for your efforts in addressing my concerns. All of my concerns have been satisfactorily resolved, and I have decided to raise my score to 3.

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

The paper introduces an LLM-powered evolutionary framework to discover domain-independent heuristic functions for symbolic AI planning. The approach uses LLMs to propose code mutations that are stored in a MAP-Elites archive keyed by informedness and speed. The framework generates deterministic C++ code that preserves the soundness and completeness of the underlying search.

Contributions

  1. Establishes the first LLM-driven evolutionary pipeline capable of producing general-purpose, domain-independent heuristics that generalize across diverse planning domains.
  2. Formulates a fitness metric that combines task coverage with an agile score to reward both solving more problems and finding solutions faster.
  3. Creates a comparative benchmark evaluating nineteen diverse hand-engineered heuristics across the Pareto frontier of evaluation speed vs informedness.
  4. Demonstrates impressive empirical results

Validation

  1. Benchmarked extensively across the 2023 International Planning Competition Learning Track and held-out domains from the AutoScale.
  2. Compared against nineteen hand-engineered, domain-independent heuristics from Scorpion
Critical strengths
  1. It addresses a major limitation of prior LLM-based work by creating domain-independent heuristics that generalize across domains
  2. It integrates seamlessly into existing planners like Fast Downward
  3. It provides a thorough empirical evaluation against 19 hand-engineered baselines across thousands of diverse tasks.
Critical weaknesses
  1. The evolved heuristics do not provide admissibility guarantees, rendering them unsuitable for cost-optimal planning.
  2. Due to the high computational demands (14,600 CPU hours) the authors were restricted to only three runs per configuration, leaving some comparisons susceptible to variance and stochastic noise from the underlying LLM APIs.
  3. It would have been informative to compare (at least) a subset of the current results against one SOTA closed-model LLM
Questions for authors

n/a

2 comments

Thank you for the kind review.

Reviewer_phszOpenReview ↗

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

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

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.