BuildPython

Planning with HTN and Evolutionary Search

Use symbolic planning when the plan has to be provably correct. Use evolutionary code search when a machine can score the result. ChatHTN and AlphaEvolve (both 2025) show what each one can do once an LLM is attached.

TIME: ~75 minutesPREREQUISITES: Phase 14 · 01 (The Agent Loop, ReAct), Phase 14 · 02 (ReWOO and Plan-and-Execute)

Learning Objectives

Explain Hierarchical Task Networks: tasks, methods, operators, preconditions, effects.
Describe ChatHTN's hybrid loop — symbolic search with LLM fallback decomposition.
Explain AlphaEvolve's evolutionary loop and why it only works with a programmatic evaluator.
Implement a toy HTN planner plus a toy evolutionary search in stdlib.

The Problem

ReAct, Plan-and-Execute, and ReWOO (Lesson 02) cover most agent planning. Two cases they handle badly:

Plans that must be provably correct. Scheduling, flight pathing, and compliance workflows need a plan that is sound by construction. A fluent LLM plan that occasionally invents a step is unacceptable here.
Optimization against a machine-checkable fitness function. Matrix multiplication, scheduling heuristics, and compiler passes don't want a correct plan. They want the best one.

HTN planning solves the first problem and AlphaEvolve solves the second. Both use the LLM to amplify a system that already works, not to replace it.

Warm-up0/2

1. An LLM writes a multi-step plan that an agent then executes. What is the main risk of running it unchecked?Warm-up

2. You want a program to improve automatically by trying many variants. What has to exist before that can work?Warm-up

Check: The Problem0/2

1. HTN planning and AlphaEvolve both put an LLM inside a larger system instead of letting it work alone. Why?Explain

2. Scheduling heuristics and compiler passes suit AlphaEvolve better than a planner. What is the reason?Explain

The Concept

Hierarchical Task Networks

A Hierarchical Task Network (HTN) planner turns a goal into executable steps by decomposing compound tasks into smaller tasks until only primitive actions remain. Four pieces make that work:

Tasks are either compound (to be decomposed) or primitive (directly executable).
Methods are ways to decompose a compound task into subtasks, each with preconditions.
Operators are primitive actions with preconditions and effects.
State is a set of facts.

Given a goal task and an initial state, the planner searches for a decomposition into primitive operators whose preconditions hold in sequence. HTN predates LLMs by decades and is still the reference approach for provably correct plans.

ChatHTN (Gopalakrishnan et al., 2025)

ChatHTN (arXiv:2505.11814) interleaves symbolic HTN planning with LLM queries. The loop:

Try to decompose the current compound task with the existing methods.
If no method applies, ask the LLM how it would decompose task in state s.
Translate the LLM's answer into candidate subtasks.
Validate the candidates against the operator schema and reject invalid decompositions.
Recurse.

The paper's central claim is that every plan it produces is provably sound. LLM suggestions only ever enter as candidate decompositions, never as direct edits to the plan. The symbolic layer owns correctness, and the LLM just grows the method library.

A 2025 follow-up on online method learning (OpenReview gwYEDY9j2x) adds a learner that generalizes the LLM's decompositions by regression. That cuts LLM query frequency by up to 75%.

AlphaEvolve (Novikov et al., 2025)

AlphaEvolve (arXiv:2506.13131, DeepMind, June 2025) is evolutionary code search: an ensemble of Gemini 2.0 Flash and Pro proposes mutations to a program, and a programmatic evaluator decides which ones survive. The loop:

Start with a seed program and an evaluator that returns a fitness score.
Let the LLM ensemble propose mutations.
Run each mutation through the evaluator.
Keep the best and mutate again.

Published wins:

The first improvement over Strassen for 4x4 complex matrix multiplication in 56 years (48 scalar multiplications).
0.7% of Google's compute recovered through a Borg scheduling heuristic.
A 32% FlashAttention speedup on a frontier workload.

The hard constraint is that the fitness function has to be machine-checkable. Evolutionary search over prose answers does not converge.

When to use which

Problem class	Use	Why
Scheduling with hard constraints	HTN + ChatHTN	Provable soundness
Compiler optimization	AlphaEvolve	Machine-checkable fitness
Multi-step task execution	ReAct / ReWOO	LLM in the loop, no formal guarantees
Code improvement with tests	AlphaEvolve	Tests are the evaluator
Policy-bound automation	HTN	Preconditions encode policy

Where this pattern goes wrong

HTN without operators. Strip the precondition and effect schemas and the soundness claim collapses. ChatHTN needs the schema to reject bad LLM suggestions.
AlphaEvolve without a real evaluator. Asking the LLM whether the code got better is not a fitness function. The evaluator must be deterministic and fast.
Over-engineering. Most agent tasks need neither approach. Start with ReAct or ReWOO.

Check: The Concept0/22

1. What is a Hierarchical Task Network (HTN) planner?Define

2. Which HTN element is a primitive, directly executable action with preconditions and effects?Define

3. What distinguishes a compound task from a method in an HTN?Define

4. What is ChatHTN?Define

5. What is AlphaEvolve?Define

6. What is a fitness function in an AlphaEvolve-style search?Define

7. What does the lesson say online method learning contributes to ChatHTN's LLM usage?Define

8. In an HTN, why does an operator carry effects as well as preconditions?Explain

9. How does ChatHTN preserve plan soundness while using an LLM?Explain

10. Why does ChatHTN try its existing methods before asking the LLM?Explain

11. What is the lesson's warning about AlphaEvolve without a real evaluator?Explain

12. AlphaEvolve found a 4x4 complex matrix multiplication using 48 scalar multiplications. Why is matrix multiplication a good target for it?Explain

13. Why does evolutionary search over prose answers not converge?Explain

14. When should you reach for ReAct or ReWOO instead of HTN or AlphaEvolve?Explain

15. What does the lesson's "HTN without operators" pitfall warn against?Explain

16. A team asks Gemini to rate each mutated program from 1 to 10. The same code gets different ratings on different runs, and the search wanders. Which requirement is missing?Analyze

17. A hybrid planner sends the same decomposition request to the LLM every day, and query costs keep growing. What is missing?Analyze

18. To evolve a sort function, a team scores each mutation with a test run that takes minutes and sometimes passes or fails at random. What is the problem?Analyze

19. Design A: an LLM writes a booking plan and a second LLM approves it. Design B: an LLM proposes decompositions and operator preconditions accept or reject them. Which is sound, and why?Analyze

20. A nightly job must produce a staffing schedule that never violates labor rules. Which approach fits best?Design

21. You must speed up a slow SQL query, and you have a benchmark that checks the results match and measures runtime. Which design fits?Design

22. A compliance workflow has strict rules, and new task types appear weekly. You want guaranteed soundness without hand-writing every decomposition. Which design fits?Design

Build It

code/main.py implements two toys:

A stdlib HTN planner with operators, methods, preconditions, and effects, plus a ScriptedLLM fallback that kicks in when no method matches a compound task. The "LLM" is a scripted decomposer, so the planner runs offline.
A stdlib evolutionary search over (a, b) pairs for the line a*x + b. It mutates the pairs to minimize the squared error against 3x + 7 over a test set, scored by a deterministic evaluator.

Run it:

python3 code/main.py

The trace shows the HTN planner decomposing a compound task, with an LLM fallback partway through, and then the evolutionary loop converging on the target line.

Check: Build It0/7

1. In the demo, the method library has one method for ship_change (needs logged_in). With state {"logged_in"}, what does plan("ship_change", state) do?Apply

2. The demo asks to plan ship_feature_with_migration, which has no method. The scripted LLM answers with four operator names. What happens?Apply

3. After that call succeeds, the demo plans ship_feature_with_migration again from the same state. How many new LLM calls does it make?Apply

4. In the demo, plan("ship_change", set()) runs with an empty state. What does it return?Apply

5. The scripted LLM suggests ("open_editor", "deploy_to_prod"), but deploy_to_prod is neither an operator nor a method. What does plan return?Apply

6. In main.py, the evolutionary demo evolves (a, b) pairs for the line a*x + b. evaluator(2, 7) sums squared errors against target 3x + 7 for x from -5 to 5. What does it return?Apply

7. Each generation of main.py's evolutionary demo keeps 3 surviving (a, b) pairs and makes 3 children from each. How many candidates are scored per generation, and how many are kept?Apply

Use It

HTN planners: pyhop and SHOP3 exist, or build your own for domain-specific policy enforcement.
ChatHTN: research code, but the pattern (symbolic planner with LLM fallback) ports cleanly to any HTN planner.
AlphaEvolve: a DeepMind paper, and the pattern (LLM ensemble plus evaluator) is reproducible. OpenEvolve and similar open-source forks are emerging.
Agent frameworks: none ship first-class HTN or AlphaEvolve yet. Build either one as a subagent or a background worker.

Ship It

outputs/skill-hybrid-planner.md generates a hybrid planner scaffold (HTN or evolutionary) with the LLM's role explicitly scoped.

Author's Note

Before you pick either technique, find where correctness comes from. In an HTN it's the operator schema. In AlphaEvolve it's the evaluator. If you can't point at one of those in your problem, you don't have a case for either, and a ReAct or ReWOO loop is the right tool. When you do have one, spend your effort there. A tight schema or a fast, deterministic evaluator will do more for you than a better prompt or a bigger model, because those two pieces are what let you trust whatever the LLM proposes.

Exercises

Extend the HTN planner with backtracking: when an operator's precondition no longer holds at execution time, roll back and try the next method.
Add an LLM-method cache to ChatHTN. When the LLM decomposes task T in state pattern P, store the result, and check the method library first on the next call.
Swap the evolutionary search evaluator for a real test suite. Evolve a sort function that passes 20 test cases and report generations to convergence.
Read AlphaEvolve's evaluator design notes, then design an evaluator for a domain you care about (SQL query optimization, test-suite minimization, deployment YAML).
Combine the two: use HTN to decompose a compound task into subtasks, then run evolutionary search on each subtask's primitive operator. Where does it shine, and where does it over-engineer?

Key Terms

Term	What people say	What it actually means
HTN	"Hierarchical planner"	Task decomposition with operators, preconditions, effects
Method	"Decomposition rule"	A way to break a compound task into subtasks
Operator	"Primitive action"	A concrete step with a precondition and an effect
ChatHTN	"LLM + HTN"	A symbolic planner that asks the LLM only when no method matches
AlphaEvolve	"Evolutionary code search"	An LLM ensemble mutates code and a deterministic evaluator selects
Fitness function	"Evaluator"	A deterministic, machine-checkable score over outputs
Online method learning	"Cached LLM decomposition"	Store and generalize LLM plans to cut query cost