pith. sign in

arxiv: 2606.02438 · v1 · pith:MAUM2I7Unew · submitted 2026-06-01 · 💻 cs.AI

LLM-Evolved Pattern Generators for Optimal Classical Planning

Windy Phung , Dominik Drexler , Arnaud Lequen , Jendrik Seipp This is my paper

Pith reviewed 2026-06-28 14:10 UTC · model grok-4.3

classification 💻 cs.AI
keywords classical planningadmissible heuristicspattern collectionssaturated cost partitioningLLM program synthesisevolutionary searchoptimal planningA* search
0
0 comments X

The pith

LLM-evolved programs generate pattern collections that induce admissible heuristics matching baseline coverage while evaluating states faster.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces the first method to learn domain-dependent heuristics for optimal classical planning that remain admissible by construction. Rather than training a direct state-to-value mapping, it evolves programs that output pattern collections for any task in a given domain. These collections are combined with saturated cost partitioning to guarantee admissibility and thus preserve A* optimality. The programs are discovered by an evolutionary synthesis loop driven by a large language model. When the approach succeeds, the resulting heuristics achieve the same coverage as strong domain-independent baselines on several domains but incur substantially lower evaluation cost per state.

Core claim

The central claim is that an LLM-driven evolutionary program-synthesis framework can produce, for each planning domain, a program that outputs a pattern collection for any task in that domain; when the resulting patterns are combined admissibly via saturated cost partitioning, the induced heuristics match the coverage of state-of-the-art domain-independent baselines while evaluating each state substantially faster and preserving optimality guarantees.

What carries the argument

An LLM-driven evolutionary program-synthesis framework that evolves programs producing pattern collections, which are then combined via saturated cost partitioning to form admissible heuristics.

If this is right

  • The learned programs encode interpretable domain-specific insights.
  • The heuristics incur negligible overhead at test time.
  • They match the coverage of state-of-the-art domain-independent baselines on several domains.
  • Each state is evaluated substantially faster than with the baselines.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same synthesis loop could be applied to other search settings that require admissible estimates, such as certain scheduling or verification tasks.
  • Because the programs are explicit, they might be inspected or edited by humans to inject additional domain knowledge.
  • Success on more domains would reduce dependence on hand-engineered domain-independent heuristics in planning systems.
  • Failure on a domain would point to limits in the current evolutionary operators or prompt design rather than in the admissibility guarantee itself.

Load-bearing premise

An LLM-driven evolutionary program-synthesis framework can reliably obtain, for each domain, a program that produces a pattern collection yielding competitive admissible heuristics.

What would settle it

Finding even one domain where the evolved programs produce heuristics with lower coverage than the baselines or that return non-admissible values on some tasks would falsify the central claim.

Figures

Figures reproduced from arXiv: 2606.02438 by Arnaud Lequen, Dominik Drexler, Jendrik Seipp, Windy Phung.

Figure 1
Figure 1. Figure 1: One iteration of OpenEvolve. Each island [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The evolutionary pipeline. The engine (blue) cre [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Combined score per iteration for all domains. [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figure 5
Figure 5. Figure 5: Total search time: h evo vs. each baseline. Points below the diagonal indicate tasks where h evo is faster. 4.3 Example Pattern Collection Generators In this section, we describe pattern collection generators synthesized for three representative domains and analyze their empirical behavior in more depth. Childsnack. In Childsnack, sandwiches must be assem￾bled and delivered to children waiting at tables, s… view at source ↗
Figure 6
Figure 6. Figure 6: Time per heuristic evaluation: h evo vs. each base￾line. Points below the diagonal indicate tasks where h evo evaluates each state more cheaply. their destination floors. Our generator produces three pat￾tern types: singleton state atoms (boarded or served, 1 atom each); lift floor patterns grouping lift-at atoms for adjacent or globally relevant floor pairs (1–19 atoms); and per-passenger journey patterns… view at source ↗
read the original abstract

Learned heuristics have recently become a competitive alternative to traditional domain-independent heuristics for satisficing planning. Existing approaches, however, focus on improving search guidance rather than guaranteeing admissibility, which makes them unsuitable for optimal classical planning. We present the first method for learning domain-dependent heuristics that are admissible by design and thus preserve the optimality guarantees of A* search. Instead of learning a direct mapping from states to heuristic values, we learn to construct abstractions that induce admissible heuristics. We use an LLM-driven evolutionary program-synthesis framework to obtain, for each domain, a program that produces a pattern collection for any task in that domain, and we combine the resulting patterns admissibly via saturated cost partitioning. Empirically, the learned programs encode interpretable domain-specific insights, run with negligible overhead at test time and yield heuristics that match the coverage of state-of-the-art domain-independent baselines on several domains while evaluating each state substantially faster.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper claims to introduce the first method for learning domain-dependent admissible heuristics for optimal classical planning. Instead of directly learning state-to-value mappings, it uses an LLM-driven evolutionary program-synthesis framework to discover, per planning domain, a program that generates a pattern collection for any task in that domain; the resulting patterns are then combined admissibly via saturated cost partitioning to yield a heuristic that preserves A* optimality. The abstract reports that the learned programs are interpretable, incur negligible test-time overhead, match the coverage of state-of-the-art domain-independent baselines on several domains, and evaluate states substantially faster.

Significance. If the empirical claims are substantiated, the work would be significant: it demonstrates a route to domain-dependent admissible heuristics that retain optimality guarantees while incorporating learned, interpretable structure. The evolutionary synthesis approach for generating pattern-collection programs is a distinctive technical contribution that could be extended beyond planning.

major comments (2)
  1. [Experiments] Experiments section: the manuscript states that the learned heuristics 'match the coverage of state-of-the-art domain-independent baselines on several domains while evaluating each state substantially faster,' yet supplies no description of the experimental protocol (domains, instance counts, number of independent runs, statistical tests for coverage or runtime differences, or failure modes). This information is load-bearing for assessing the central empirical claim.
  2. [Method] Method section: while admissibility of the final heuristic follows from the standard properties of pattern databases and saturated cost partitioning, the paper provides no formal argument or pseudocode establishing that the evolutionary search is guaranteed to terminate with a program that produces valid (i.e., well-formed) pattern collections for every task in the target domain.
minor comments (2)
  1. [Introduction] The abstract and introduction repeatedly use the phrase 'first method' without a precise comparison table or citation list that distinguishes the new contribution from prior work on learned admissible heuristics or evolutionary program synthesis in planning.
  2. [Method] Notation for the evolutionary fitness function and the saturated-cost-partitioning combination step is introduced without an explicit equation or algorithm listing, making it difficult to verify reproducibility from the text alone.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive feedback. We address each major comment below.

read point-by-point responses

  1. Referee: [Experiments] Experiments section: the manuscript states that the learned heuristics 'match the coverage of state-of-the-art domain-independent baselines on several domains while evaluating each state substantially faster,' yet supplies no description of the experimental protocol (domains, instance counts, number of independent runs, statistical tests for coverage or runtime differences, or failure modes). This information is load-bearing for assessing the central empirical claim.

    Authors: We agree that the current manuscript lacks a sufficient description of the experimental protocol. In the revision we will add a dedicated subsection detailing the domains and instance counts, the number of independent runs, the statistical tests applied to coverage and runtime results, and any observed failure modes. revision: yes

  2. Referee: [Method] Method section: while admissibility of the final heuristic follows from the standard properties of pattern databases and saturated cost partitioning, the paper provides no formal argument or pseudocode establishing that the evolutionary search is guaranteed to terminate with a program that produces valid (i.e., well-formed) pattern collections for every task in the target domain.

    Authors: The evolutionary procedure is stochastic and LLM-driven, so it does not admit a formal termination guarantee that every generated program will be valid. We will nevertheless add pseudocode for the full evolutionary loop together with a description of the validation and rejection steps that discard malformed programs. This clarifies the practical safeguards without claiming an absolute guarantee. revision: partial

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper's core derivation is that LLM-evolved programs generate pattern collections whose induced heuristics remain admissible because (a) projections preserve admissibility (standard PDB property) and (b) saturated cost partitioning preserves admissibility (standard operator). These properties are invoked from the planning literature rather than derived inside the paper or via self-citation chains. The evolutionary synthesis step is presented only as a discovery procedure whose output is then evaluated empirically on coverage and runtime; no equation defines a fitted parameter that is later renamed a prediction, and no uniqueness theorem or ansatz is smuggled in. The reported results are therefore falsifiable external measurements rather than algebraic identities of the method's own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the standard planning assumption that saturated cost partitioning of pattern collections yields admissible heuristics, plus the unverified premise that evolutionary search over LLM-generated programs will discover effective domain-specific generators.

axioms (1)
  • domain assumption Saturated cost partitioning of multiple pattern databases produces an admissible heuristic.
    This is a standard result in classical planning literature invoked to guarantee admissibility.

pith-pipeline@v0.9.1-grok · 5688 in / 1164 out tokens · 30129 ms · 2026-06-28T14:10:18.760237+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

300 extracted references · 1 canonical work pages

  1. [1]

    Communication, Simulation, and Intelligent Agents: Implications of Personal Intelligent Machines for Medical Education

    Clancey, William J. Communication, Simulation, and Intelligent Agents: Implications of Personal Intelligent Machines for Medical Education. Proceedings of the Eighth International Joint Conference on Artificial Intelligence (IJCAI-83)

  2. [2]

    Classification Problem Solving

    Clancey, William J. Classification Problem Solving. Proceedings of the Fourth National Conference on Artificial Intelligence

  3. [3]

    , title =

    Robinson, Arthur L. , title =. 1980 , doi =. https://science.sciencemag.org/content/208/4447/1019.full.pdf , journal =

    1980

  4. [4]

    New Ways to Make Microcircuits Smaller---Duplicate Entry

    Robinson, Arthur L. New Ways to Make Microcircuits Smaller---Duplicate Entry. Science

  5. [5]

    Clancey and Glenn Rennels , abstract =

    Diane Warner Hasling and William J. Clancey and Glenn Rennels , abstract =. Strategic explanations for a diagnostic consultation system , journal =. 1984 , issn =. doi:https://doi.org/10.1016/S0020-7373(84)80003-6 , url =

    work page doi:10.1016/s0020-7373(84)80003-6 1984

  6. [6]

    and Rennels, Glenn R

    Hasling, Diane Warner and Clancey, William J. and Rennels, Glenn R. and Test, Thomas. Strategic Explanations in Consultation---Duplicate. The International Journal of Man-Machine Studies

  7. [7]

    Poligon: A System for Parallel Problem Solving

    Rice, James. Poligon: A System for Parallel Problem Solving

  8. [8]

    Transfer of Rule-Based Expertise through a Tutorial Dialogue

    Clancey, William J. Transfer of Rule-Based Expertise through a Tutorial Dialogue

  9. [9]

    The Engineering of Qualitative Models

    Clancey, William J. The Engineering of Qualitative Models

  10. [10]

    2017 , eprint=

    Attention Is All You Need , author=. 2017 , eprint=

    2017

  11. [11]

    Pluto: The 'Other' Red Planet

    NASA. Pluto: The 'Other' Red Planet

  12. [12]

    Proc.\ AAAI 1991

    Proc.\ AAAI 1991. Proc.\ AAAI 1991. 1991

    1991

  13. [13]

    Proc.\ AAAI 1993

    Proc.\ AAAI 1993. Proc.\ AAAI 1993. 1993

    1993

  14. [14]

    Proc.\ AAAI 1994

    Proc.\ AAAI 1994. Proc.\ AAAI 1994. 1994

    1994

  15. [15]

    Proc.\ AAAI 1996

    Proc.\ AAAI 1996. Proc.\ AAAI 1996. 1996

    1996

  16. [16]

    Proc.\ AAAI 1997

    Proc.\ AAAI 1997. Proc.\ AAAI 1997. 1997

    1997

  17. [17]

    Proc.\ AAAI 1998

    Proc.\ AAAI 1998. Proc.\ AAAI 1998. 1998

    1998

  18. [18]

    Proc.\ AAAI 1999

    Proc.\ AAAI 1999. Proc.\ AAAI 1999. 1999

    1999

  19. [19]

    Proc.\ AAAI 2000

    Proc.\ AAAI 2000. Proc.\ AAAI 2000. 2000

    2000

  20. [20]

    Proc.\ AAAI 2002

    Proc.\ AAAI 2002. Proc.\ AAAI 2002. 2002

    2002

  21. [21]

    Proc.\ AAAI 2004

    Proc.\ AAAI 2004. Proc.\ AAAI 2004. 2004

    2004

  22. [22]

    Proc.\ AAAI 2005

    Proc.\ AAAI 2005. Proc.\ AAAI 2005. 2005

    2005

  23. [23]

    Proc.\ AAAI 2006

    Proc.\ AAAI 2006. Proc.\ AAAI 2006. 2006

    2006

  24. [24]

    AAAI 2006 Workshop on Learning for Search

    AAAI 2006 Workshop on Learning for Search. AAAI 2006 Workshop on Learning for Search. 2006

    2006

  25. [25]

    Proc.\ AAAI 2007

    Proc.\ AAAI 2007. Proc.\ AAAI 2007. 2007

    2007

  26. [26]

    Proc.\ AAAI 2008

    Proc.\ AAAI 2008. Proc.\ AAAI 2008. 2008

    2008

  27. [27]

    AAAI 2008 Workshop on Search in Artificial Intelligence and Robotics

    AAAI 2008 Workshop on Search in Artificial Intelligence and Robotics. AAAI 2008 Workshop on Search in Artificial Intelligence and Robotics. 2008

    2008

  28. [28]

    Proc.\ AAAI 2010

    Proc.\ AAAI 2010. Proc.\ AAAI 2010. 2010

    2010

  29. [29]

    Proc.\ AAAI 2011

    Proc.\ AAAI 2011. Proc.\ AAAI 2011. 2011

    2011

  30. [30]

    Proc.\ AAAI 2012

    Proc.\ AAAI 2012. Proc.\ AAAI 2012. 2012

    2012

  31. [31]

    AAAI 2012 Workshop on Problem Solving Using Classical Planners

    AAAI 2012 Workshop on Problem Solving Using Classical Planners. AAAI 2012 Workshop on Problem Solving Using Classical Planners. 2012

    2012

  32. [32]

    Proc.\ AAAI 2013

    Proc.\ AAAI 2013. Proc.\ AAAI 2013. 2013

    2013

  33. [33]

    Proc.\ AAAI 2013 Late-Breaking Papers

    Proc.\ AAAI 2013 Late-Breaking Papers. Proc.\ AAAI 2013 Late-Breaking Papers. 2013

    2013

  34. [34]

    Proc.\ AAAI 2014

    Proc.\ AAAI 2014. Proc.\ AAAI 2014. 2014

    2014

  35. [35]

    Proc.\ AAAI 2015

    Proc.\ AAAI 2015. Proc.\ AAAI 2015. 2015

    2015

  36. [36]

    AAAI 2015 Workshop on Planning, Search, and Optimization

    AAAI 2015 Workshop on Planning, Search, and Optimization. AAAI 2015 Workshop on Planning, Search, and Optimization. 2015

    2015

  37. [37]

    Proc.\ AAAI 2016

    Proc.\ AAAI 2016. Proc.\ AAAI 2016. 2016

    2016

  38. [38]

    Proc.\ AAAI 2017

    Proc.\ AAAI 2017. Proc.\ AAAI 2017. 2017

    2017

  39. [39]

    Proc.\ AAAI 2018

    Proc.\ AAAI 2018. Proc.\ AAAI 2018. 2018

    2018

  40. [40]

    Proc.\ AAAI 2019

    Proc.\ AAAI 2019. Proc.\ AAAI 2019. 2019

    2019

  41. [41]

    Proc.\ AAAI 2020

    Proc.\ AAAI 2020. Proc.\ AAAI 2020. 2020

    2020

  42. [42]

    Proc.\ AAAI 2021

    Proc.\ AAAI 2021. Proc.\ AAAI 2021. 2021

    2021

  43. [43]

    Proc.\ AAAI 2022

    Proc.\ AAAI 2022. Proc.\ AAAI 2022. 2022

    2022

  44. [44]

    Proc.\ AAAI 2023

    Proc.\ AAAI 2023. Proc.\ AAAI 2023. 2023

    2023

  45. [45]

    Proc.\ AAAI 2024

    Proc.\ AAAI 2024. Proc.\ AAAI 2024. 2024

    2024

  46. [46]

    Proc.\ AAAI 2025

    Proc.\ AAAI 2025. Proc.\ AAAI 2025. 2025

    2025

  47. [47]

    Proc.\ AAAI 2026

    Proc.\ AAAI 2026. Proc.\ AAAI 2026. 2026

    2026

  48. [48]

    Proc.\ AAMAS 2010

    Proc.\ AAMAS 2010. Proc.\ AAMAS 2010. 2010

    2010

  49. [49]

    Proc.\ AAMAS 2013

    Proc.\ AAMAS 2013. Proc.\ AAMAS 2013. 2013

    2013

  50. [50]

    Proc.\ AAMAS 2014

    Proc.\ AAMAS 2014. Proc.\ AAMAS 2014. 2014

    2014

  51. [51]

    Proc.\ AAMAS 2016

    Proc.\ AAMAS 2016. Proc.\ AAMAS 2016. 2016

    2016

  52. [52]

    Proc.\ AAMAS 2024

    Proc.\ AAMAS 2024. Proc.\ AAMAS 2024. 2024

    2024

  53. [53]

    Proc.\ AI 2013

    Proc.\ AI 2013. Proc.\ AI 2013. 2013

    2013

  54. [54]

    Proc.\ AIIDE 2015

    Proc.\ AIIDE 2015. Proc.\ AIIDE 2015. 2015

    2015

  55. [55]

    Proc.\ AIPS 1992

    Proc.\ AIPS 1992. Proc.\ AIPS 1992. 1992

    1992

  56. [56]

    Proc.\ AIPS 1996

    Proc.\ AIPS 1996. Proc.\ AIPS 1996. 1996

    1996

  57. [57]

    Proc.\ AIPS 2000

    Proc.\ AIPS 2000. Proc.\ AIPS 2000. 2000

    2000

  58. [58]

    AIPS 2000 Workshop on Analyzing and Exploiting Domain Knowledge for Efficient Planning

    AIPS 2000 Workshop on Analyzing and Exploiting Domain Knowledge for Efficient Planning. AIPS 2000 Workshop on Analyzing and Exploiting Domain Knowledge for Efficient Planning. 2000

    2000

  59. [59]

    AIPS 2000 Workshop on Model-Theoretic Approaches to Planning

    AIPS 2000 Workshop on Model-Theoretic Approaches to Planning. AIPS 2000 Workshop on Model-Theoretic Approaches to Planning. 2000

    2000

  60. [60]

    Proc.\ AIPS 2002

    Proc.\ AIPS 2002. Proc.\ AIPS 2002. 2002

    2002

  61. [61]

    Proc.\ AISTATS 2013

    Proc.\ AISTATS 2013. Proc.\ AISTATS 2013. 2013

    2013

  62. [62]

    Proc.\ AISTATS 2014

    Proc.\ AISTATS 2014. Proc.\ AISTATS 2014. 2014

    2014

  63. [63]

    Proc.\ ALENEX 2007

    Proc.\ ALENEX 2007. Proc.\ ALENEX 2007. 2007

    2007

  64. [64]

    Algorithmics of Large and Complex Networks

    Algorithmics of Large and Complex Networks. Algorithmics of Large and Complex Networks. 2009

    2009

  65. [65]

    Proc.\ ASE 2022

    Proc.\ ASE 2022. Proc.\ ASE 2022. 2022

    2022

  66. [66]

    Proc.\ ATVA 2009

    Proc.\ ATVA 2009. Proc.\ ATVA 2009. 2009

    2009

  67. [67]

    AVoCS 2004

    Proc. AVoCS 2004. Proc. AVoCS 2004. 2004

    2004

  68. [68]

    Proc.\ CAI 2018

    Proc.\ CAI 2018. Proc.\ CAI 2018. 2018

    2018

  69. [69]

    Proc.\ CAV 1992

    Proc.\ CAV 1992. Proc.\ CAV 1992. 1992

    1992

  70. [70]

    Proc.\ CAV 1993

    Proc.\ CAV 1993. Proc.\ CAV 1993. 1993

    1993

  71. [71]

    Proc.\ CAV 2000

    Proc.\ CAV 2000. Proc.\ CAV 2000. 2000

    2000

  72. [72]

    Proc.\ CAV 2002

    Proc.\ CAV 2002. Proc.\ CAV 2002. 2002

    2002

  73. [73]

    Proc.\ CAV 2008

    Proc.\ CAV 2008. Proc.\ CAV 2008. 2008

    2008

  74. [74]

    Proc.\ CAV 2009

    Proc.\ CAV 2009. Proc.\ CAV 2009. 2009

    2009

  75. [75]

    Proc.\ CAV 2010

    Proc.\ CAV 2010. Proc.\ CAV 2010. 2010

    2010

  76. [76]

    Proc.\ CAV 2021, Part II

    Proc.\ CAV 2021, Part II. Proc.\ CAV 2021, Part II. 2021

    2021

  77. [77]

    Proc.\ CAV 2025, Part I

    Proc.\ CAV 2025, Part I. Proc.\ CAV 2025, Part I. 2025

    2025

  78. [78]

    Proc.\ CIG 2008

    Proc.\ CIG 2008. Proc.\ CIG 2008. 2008

    2008

  79. [79]

    Proc.\ CoCoMile 2012

    Proc.\ CoCoMile 2012. Proc.\ CoCoMile 2012. 2012

    2012

  80. [80]

    1st CoRe Challenge: Solver and Graph Descriptions

    1st CoRe Challenge: Solver and Graph Descriptions. 1st CoRe Challenge: Solver and Graph Descriptions. 2022

    2022

Showing first 80 references.