HTN과 진화적 탐색(Evolutionary Search)으로 계획하기

기호적 계획(symbolic planning)은 계획이 증명 가능하게 올바라야 하는 경우를 다룹니다. 진화적 코드 탐색(evolutionary code search)은 적합도 함수(fitness function)를 기계로 확인할 수 있는 경우를 다룹니다. ChatHTN(2025)과 AlphaEvolve(2025)는 각각을 LLM과 결합했을 때 무엇이 가능해지는지 보여줍니다.

유형: Build 언어: Python (stdlib) 선수 학습: Phase 14 · 02 (ReWOO와 Plan-and-Execute) 소요 시간: 약 75분

학습 목표

• 계층적 작업 네트워크(Hierarchical Task Network; HTN)를 설명합니다. 작업(task), 메서드(method), 연산자(operator), 전제조건(precondition), 효과(effect)를 포함합니다.
• ChatHTN의 하이브리드 루프를 설명합니다. 기호적 탐색에 LLM 대체 분해(LLM fallback decomposition)를 결합한 구조입니다.
• AlphaEvolve의 진화적 루프와, 이것이 프로그램 기반 평가자(programmatic evaluator)가 있을 때만 작동하는 이유를 설명합니다.
• 장난감 HTN 계획기(planner)와 장난감 진화적 탐색을 표준 라이브러리(stdlib)로 구현합니다.

문제

ReWOO(02강), Plan-and-Execute, ReAct는 대부분의 에이전트 계획을 다룹니다. 하지만 잘 다루지 못하는 두 경우가 있습니다.

1. 증명 가능한 정확성이 필요한 계획. 일정 관리(scheduling), 비행 경로 설정(flight pathing), 컴플라이언스 워크플로(compliance workflow)가 여기에 속합니다. 계획은 구조적으로 올바라야 하며, 가끔 단계를 환각(hallucination)하는 유창한 LLM 계획은 받아들일 수 없습니다.
2. 기계로 확인 가능한 적합도 함수가 있는 최적화. 행렬 곱셈(matrix multiplication), 스케줄링 휴리스틱, 컴파일러 패스(compiler pass)가 여기에 속합니다. 목표는 "올바른 계획"이 아니라 "가장 좋은 계획"입니다.

HTN 계획과 AlphaEvolve는 서로 다른 두 문제를 해결합니다. 둘 다 LLM을 대체물이 아니라 증폭기(amplifier)로 사용합니다.

개념

계층적 작업 네트워크(Hierarchical Task Networks)

HTN은 다음으로 구성됩니다.

• 작업(Tasks) — 분해해야 하는 복합 작업(compound task)과 직접 실행 가능한 원시 작업(primitive task)입니다.
• 메서드(Methods) — 전제조건이 충족될 때 복합 작업을 하위 작업으로 분해하는 방법입니다.
• 연산자(Operators) — 전제조건과 효과를 가진 원시 행동입니다.
• 상태(State) — 사실(fact)의 집합입니다.

계획(planning)은 목표 작업과 초기 상태가 주어졌을 때, 전제조건이 순서대로 만족되는 원시 연산자의 나열로 분해하는 과정입니다.

HTN은 LLM보다 오래된 방식이며, 증명 가능하게 올바른 계획이 필요할 때 여전히 기준점이 되는 접근입니다.

ChatHTN (Gopalakrishnan et al., 2025)

ChatHTN(arXiv:2505.11814)은 기호적 HTN과 LLM 질의를 다음과 같이 엮습니다.

1. 기존 메서드로 현재 복합 작업을 분해해 봅니다.
2. 적용 가능한 메서드가 없으면 LLM에게 묻습니다. "state s에서 task를 어떻게 분해하겠는가?"
3. LLM 응답을 후보 하위 작업(candidate subtask)으로 변환합니다.
4. 연산자 스키마(operator schema)에 비추어 검증하고, 잘못된 분해는 거부합니다.
5. 재귀적으로 반복합니다.

논문의 핵심 주장은 생성된 모든 계획이 증명 가능하게 건전(sound)하다는 것입니다. LLM 제안은 계획을 직접 수정하는 통로가 아니라 후보 분해로만 들어오기 때문입니다. 정확성은 기호 계층(symbolic layer)이 책임지고, LLM은 메서드 라이브러리를 확장합니다.

온라인 메서드 학습(Online method learning, OpenReview gwYEDY9j2x, 2025년 후속 연구)은 LLM이 만든 분해를 회귀(regression)로 일반화하는 학습기를 추가합니다. 이를 통해 LLM 질의 빈도를 최대 75%까지 줄입니다.

AlphaEvolve (Novikov et al., 2025)

AlphaEvolve(arXiv:2506.13131, DeepMind, 2025년 6월)는 결이 다른 접근입니다. Gemini 2.0 Flash/Pro 앙상블이 오케스트레이션하는 진화적 코드 탐색입니다.

루프는 다음과 같습니다.

1. 시드 프로그램(seed program)과 프로그램 기반 평가자(적합도 점수를 반환)를 준비합니다.
2. LLM 앙상블이 돌연변이(mutation)를 제안합니다.
3. 돌연변이를 평가자에 통과시킵니다.
4. 가장 좋은 결과만 남기고 다시 돌연변이시킵니다.

공개된 성과는 다음과 같습니다.

• 56년 만에 4x4 복소수 행렬 곱셈에서 Strassen 알고리즘을 넘어선 첫 개선입니다. 스칼라 곱셈 48회로 줄였습니다.
• Borg 스케줄링 휴리스틱(Borg scheduling heuristic)으로 구글 컴퓨트 자원의 0.7%를 회수했습니다.
• 프런티어 워크로드에서 FlashAttention 속도를 32% 높였습니다.

강한 제약은 적합도 함수를 기계로 확인할 수 있어야 한다는 점입니다. 산문 답변 위에서 돌리는 진화적 탐색은 수렴하지 않습니다.

무엇을 언제 쓸 것인가

이 패턴이 잘못되는 지점

• 연산자 없는 HTN. 전제조건/효과 스키마가 없으면 건전성 주장이 무너집니다. ChatHTN의 "LLM이 분해를 제안한다"는 방식은 스키마가 잘못된 결정을 거부할 수 있다는 전제 위에서만 성립합니다.
• 진짜 평가자 없는 AlphaEvolve. "LLM에게 코드가 더 나은지 물어보기"는 적합도 함수가 아닙니다. 평가자는 결정적이고 빠르게 동작해야 합니다.
• 과잉 엔지니어링. 대부분의 에이전트 작업에는 둘 다 필요하지 않습니다. 먼저 ReAct나 ReWOO를 고려하세요.

만들어보기

code/main.py는 두 가지 장난감 예제를 구현합니다.

• 표준 라이브러리만 사용하는 HTN 계획기입니다. 연산자, 메서드, 전제조건, 효과를 갖추고 있으며, 복합 작업에 맞는 메서드가 없을 때 작동하는 LLMFallback이 포함됩니다. 여기서 "LLM"은 오프라인 실행을 위해 미리 스크립트로 짜둔 분해기입니다.
• 산술 프로그램에 대한 표준 라이브러리 진화적 탐색입니다. 테스트 집합에서 |f(x) - target|을 최소화하는 식(expression)을 진화시킵니다. 평가자는 결정적입니다.

다음 명령으로 실행합니다.

python3 code/main.py

실행 추적은 HTN 계획기가 중간에 LLM 대체 분해(LLM fallback)를 사용해 복합 작업을 분해하는 모습을 보여줍니다. 이어서 진화적 루프가 목표 식으로 수렴하는 모습도 확인할 수 있습니다.

사용해보기

• HTN 계획기(HTN planners) — pyhop, SHOP3처럼 공개된 도구를 쓰거나, 도메인 특화 정책을 강제하기 위해 직접 구현한 계획기를 사용합니다.
• ChatHTN — 연구 코드 수준의 구현이지만, 그 패턴(기호적 계획 + LLM 대체 분해)은 어떤 HTN 계획기에도 깔끔하게 옮길 수 있습니다.
• AlphaEvolve — DeepMind 논문에 소개된 방식으로, 그 패턴(앙상블 + 평가자)은 재현할 수 있습니다. OpenEvolve와 비슷한 오픈소스 포크(fork)가 등장하고 있습니다.
• 에이전트 프레임워크(Agent frameworks) — 아직 HTN이나 AlphaEvolve를 일급 기능으로 제공하는 곳은 없습니다. 하위 에이전트(subagent)나 백그라운드 워커(background worker)로 직접 구성하세요.

산출물 만들기

outputs/skill-hybrid-planner.md는 LLM의 역할 범위를 명시적으로 정해 둔 하이브리드 계획기 스캐폴드(HTN 또는 진화적 탐색)를 생성합니다.

연습문제

1. (쉬움) HTN 계획기에 백트래킹(backtracking)을 추가하세요. 런타임에서 연산자의 사후조건(postcondition)이 실패하면 롤백하고 다음 메서드를 시도합니다.
2. (중간) ChatHTN에 LLM 메서드 캐시(LLM-method cache)를 추가하세요. LLM이 상태 패턴 P에서 작업 T를 분해하면 결과를 저장합니다. 다음 호출에서는 먼저 메서드 라이브러리를 다시 확인하도록 합니다.
3. (중간) 진화적 탐색의 평가자를 실제 테스트 스위트(test suite)로 바꾸세요. 20개 테스트 사례를 통과하는 정렬 함수를 진화시키고, 수렴까지 몇 세대가 걸렸는지 보고하세요.
4. (중간) AlphaEvolve의 평가자 설계 노트를 읽어보세요. 관심 있는 도메인(SQL 질의 최적화, 테스트 스위트 최소화, 배포 YAML)을 위한 평가자를 설계하세요.
5. (어려움) 결합해 보세요. HTN을 사용해 복합 작업을 하위 작업으로 분해하고, 각 하위 작업의 원시 연산자에 대해 진화적 탐색을 적용합니다. 어디에서 빛나고, 어디에서 과잉 엔지니어링이 되는지 정리해 보세요.

핵심 용어

더 읽을거리

• Gopalakrishnan et al., ChatHTN (arXiv:2505.11814) — 기호적 계획과 LLM을 결합한 하이브리드 계획기입니다.
• Novikov et al., AlphaEvolve (arXiv:2506.13131) — LLM 돌연변이를 사용하는 진화적 코드 탐색을 다룹니다.
• Anthropic, Building Effective Agents — 계획기와 단순 루프 중 무엇을 선택할지에 대한 기준을 제시합니다.