ICML 2026 LM4Plan

Formal Planning · Hierarchical Reasoning · World Models · Verification

Planning in the Era of Large Language Models

LM4Plan 2026의 28편 논문군을 형식계획, 계층적 추론, world model, 도구계획, 운영최적화, multi-agent coordination, test-time compute와 heterogeneous routing의 관점에서 통합한다.

중심 명제

미래의 LM planner는 자연어로 그럴듯한 행동목록을 쓰는 모델이 아니라, 모호한 목표를 구조화하고 search·simulation·formal verification을 통과한 행동만 선택하는 폐루프 의사결정시스템이다.

28채택 논문

6구두발표

8핵심 연구축

17미래 방향

전체 연구 지형

Formal Planning

VeryTraceLM-LandmarksCompilation

Hierarchy

HiPERHi-CoTReTreVal

World Models

ICPRLOrigamiBenchStateFactory

Hybrid Policies

LaGOPACT

Tool & Web

QueryWeaverBaRA

Operations Research

PortfoliosHub PlanningFlight Planning

Multi-Agent

Joint planningSkill coordination

Compute & Routing

Beam calibrationAgentRouter

Goal→Grounding→State→Search→Verification→Execution→Observation→Replanning

Reliable LM Planning = Semantic Grounding + Structured State and Search + Hierarchical Execution + World-Model Feedback + Formal Verification + Adaptive Compute

Definition

계획 문제

Π=⟨S,A,T,s₀,G,C⟩로 표현하며, 초기상태에서 목표상태로 이동하는 실행 가능하고 저비용인 행동열을 찾는다.

LM 기반 계획

언어모델을 목표 grounding, subgoal·landmark 생성, search heuristic, world model, verifier, replanner로 사용한다.

추론과 계획

추론은 주어진 지식에서 결론을 도출하지만 계획은 행동이 환경상태를 바꾸는 결과를 함께 고려한다.

Neuro-Symbolic Planner

LM의 의미해석과 classical planner·solver·simulator의 형식적 보장을 결합한다.

계획 Landmark

모든 유효한 계획이 반드시 만족하거나 실행해야 하는 사실·행동·하위목표다.

계층적 계획

장기목표를 하위목표와 skill·action으로 분해해 horizon과 credit-assignment 난도를 낮춘다.

World Model

현재상태와 행동으로 다음 상태를 예측해 후보계획을 simulation한다.

Reward Model

현재상태와 목표상태의 구조적 거리를 이용해 계획 진행도를 평가한다.

Verifier

전제조건, invariant, resource, safety, causal consistency와 목표달성을 확인한다.

Plan Portfolio

서로 다른 가정·목적함수·위험선호를 가진 복수 후보를 유지한다.

Problem Definition

Language–State Grounding Gap

자연어 요구에서 상태, 행동, 비용, 숨은 제약과 uncertainty를 완전하게 추출하기 어렵다.

Plan Validity Gap

문법적으로 자연스러운 계획이 실제 실행 가능하거나 안전하다는 보장은 없다.

Long-Horizon Credit Assignment

최종 reward를 planner의 subgoal 결정과 executor의 action에 어떻게 분배할지 어렵다.

Plan–Execution Drift

초기 선언계획과 실제 reasoning·실행이 장기과정에서 점차 달라진다.

World-Model Gap

행동결과를 잘못 예측하면 search, simulation과 replanning이 모두 왜곡된다.

Reactive–Deliberative Gap

빠른 policy와 느린 LM planner를 언제 전환할지 결정해야 한다.

Tool-Composition Gap

여러 application과 tool의 dependency, branch, side effect를 안전하게 구성해야 한다.

Exploration–Coverage Gap

웹·open-world planning에서 깊이와 coverage를 제한된 budget 안에서 균형화해야 한다.

Single-Candidate Reliability

하나의 LM-generated plan이나 optimization model을 신뢰하기 어렵다.

Multi-Agent Coordination

개별적으로 좋은 plan도 자원·시간·belief 충돌로 joint failure를 만들 수 있다.

Search–Compute Allocation

sample, beam, search depth, verifier, model size에 compute를 어떻게 배분할지 결정해야 한다.

Core Concepts

Plan–Execute–Verify Loop

목표해석→상태구성→계획→simulation·verification→실행→관찰→replanning을 반복한다.

Semantic Front-End, Symbolic Back-End

LM은 의미를 해석하고 symbolic planner·solver는 correctness를 담당한다.

Planning as Search

상태 또는 partial plan을 node로, action·reasoning step을 edge로 보는 탐색문제다.

Hierarchical Temporal Abstraction

장기행동을 subgoal, skill, macro-action으로 묶어 horizon을 줄인다.

Factorized World State

비구조화 observation을 object와 attribute로 분해해 state transition과 reward를 추적한다.

Simulation-Verified Planning

후보 plan을 simulator에서 실행해 safety, feasibility, completeness를 검사한다.

Causal Planning

관찰상관이 아니라 action intervention이 결과를 바꾸는 구조적 mechanism을 모델링한다.

Verification-Aware Test-Time Scaling

더 많은 search보다 proposal diversity, verifier accuracy와 compute의 조합이 중요하다.

Model Routing

step 난이도에 따라 frontier LM, small LM, tool, solver를 배정한다.

Human-in-the-Loop Planning

정성적 가치와 위험선호는 portfolio와 human review로 처리한다.

Motivation and Background

자연어–형식계획 연결

실제 요구는 문서·대화·multimodal observation으로 주어지지만 planner는 명확한 PDDL·MILP·HTN model을 요구한다.

긴 CoT의 한계

긴 reasoning은 탐색량을 늘리지만 중복, plan drift, 초기오류 전파와 검증부담도 증가시킨다.

환경모델의 필요

정적 언어지식만으로 action의 물리적 결과와 장기상태를 정확히 예측하기 어렵다.

정량목적과 정성선호

비행·물류·운동·workforce 계획은 비용·시간뿐 아니라 preference와 risk를 포함한다.

역할분리의 필요

하나의 frontier LM이 generation, verification, retrieval, formatting을 모두 담당하면 비용과 오류상관이 커진다.

Key Applications

Classical Planning

BlocksWorld, Towers of Hanoi, PDDL, landmarks, HTN, action-schema induction, plan validation.

Interactive Web Agent

Cross-application query, browser navigation, web collection, tool dependency resolution.

Embodied·Robotic Planning

Physical puzzle, object manipulation, origami, visual control, continuous control, avatars.

물류·운영계획

Hub capacity, job-shop, workforce scheduling, resource allocation, MILP, flight routing.

Human-Centric Mission Planning

Pilot preference, running safety, risk tolerance, negotiation, theory of mind.

Multi-Agent Enterprise Workflow

분업, routing, orchestration, skill discovery, joint scheduling, conflict resolution.

Reasoning·수학 문제해결

Trace verification, hierarchical CoT, tree search, tool refinement, beam calibration.

Open Problems

Natural-Language-to-PDDL

숨은 assumption, negative precondition, conditional effect와 continuous variable의 안정적 변환.

Soundness와 Semantic Completeness

형식적으로 유효하지만 사용자 의도를 놓치는 계획을 방지해야 한다.

Verifier Independence

동일 LM proposer–verifier의 공통오류를 줄여야 한다.

Thinking Trace Faithfulness

출력 trace가 실제 model computation을 반영하는지 불명확하다.

Long-Horizon World Models

짧은 예측은 가능해도 rollout에서 오차가 누적된다.

Unknown Dynamics

환경전이가 바뀌는 상황에서 online system identification이 필요하다.

Hierarchy Discovery

사람이 정의한 subgoal 없이 reusable skill을 발견해야 한다.

Cross-Domain Skill Transfer

새 object·action vocabulary로 landmark와 skill이 전이되는지 불명확하다.

Multi-Agent Causal Responsibility

Planning, verification, communication 실패의 책임을 분리해야 한다.

Dynamic Human Preference

사용자 선호가 실행 중 변화하거나 상충될 수 있다.

Constraint Evolution

규정, resource, deadline, safety constraint가 실행 중 변경될 수 있다.

Search–Verifier Co-Adaptation

Planner가 verifier의 약점을 이용하는 reward hacking을 막아야 한다.

Compute-Aware Guarantees

주어진 token·latency budget에서 성공률과 안전성을 보장해야 한다.

Benchmark Contamination

유명 planning puzzle의 pretraining 포함으로 generalization을 과대평가할 수 있다.

Reality Gap

Synthetic environment가 실제 불확실성과 irreversible action을 충분히 반영하지 못한다.

Recovery and Rollback

Irreversible action에서는 단순 replanning으로 복구할 수 없다.

Causal Generalization

환경변화에도 유효한 plan을 만들려면 causal mechanism이 필요하다.

Planning Model Collapse

LM-generated trajectory 반복학습으로 rare strategy와 diversity가 소실될 수 있다.

Introduction

Stage 1 — Natural-Language Plan Generation

LLM이 행동목록을 직접 생성하지만 hallucination, constraint 누락, state error가 크다.

Stage 2 — Tool-Augmented Planning

검색기, calculator, simulator, planner, code executor를 사용한다.

Stage 3 — Structured Planning

Graph, tree, DSL, PDDL, HTN, MILP, factorized state로 변환한다.

Stage 4 — Verified Planning

Symbolic planner, deterministic solver, simulation과 verifier가 후보를 검사한다.

Stage 5 — Adaptive Agentic Planning

실행결과를 관찰하고 memory, reflection, replanning을 수행한다.

Stage 6 — Resource-Aware Multi-Agent Planning

여러 agent와 model을 비용·시간·신뢰성에 맞게 배정한다.

Stage 7 — Causal and Certified Planning

환경변화, intervention, uncertainty와 formal guarantee까지 처리한다.

Challenges

도전과제	핵심 문제	연구방향
State grounding	자연어·영상에서 완전한 상태 추출이 어려움	Factorized state와 uncertainty
Action validity	존재하지 않는 행동과 전제조건 위반	Action schema와 constrained decoding
Long horizon	오류와 credit assignment 누적	Hierarchical planning
Plan–execution drift	실행이 선언한 plan에서 이탈	Receding-horizon replanning
World-model error	행동결과 예측 부정확	Interactive learning과 simulator
Verification cost	모든 후보를 강하게 검증하기 어려움	Cascaded verifier
Trace faithfulness	Thinking trace가 실제 계산과 불일치	Executable trace와 intervention
Partial observability	현재 observation만으로 상태를 알 수 없음	Belief state와 memory
Dynamic environment	실행 중 상태·규칙·목표 변화	Online planning
Multi-agent conflict	계획과 자원·belief 충돌	Joint constraint solving
Tool dependency	실행순서와 data dependency 오류	Execution graph
Safety	Probabilistic plan이 hard rule 위반	Deterministic constraint layer
Compute allocation	Sample, beam, verifier budget 선택	Calibration-based search
Model cost	모든 step에서 frontier LM 사용	Step-level routing
Causal generalization	환경변화에서 관찰상관이 붕괴	Structural causal model

Research Questions

RQ1

언어모델은 planner인가, heuristic인가, compiler인가?

RQ2

자연어 목표를 형식상태와 행동모델로 정확히 변환할 수 있는가?

RQ3

LM이 생성한 landmark의 soundness를 어떻게 보장할 것인가?

RQ4

Reasoning trace는 계획검증의 증거로 사용할 수 있는가?

RQ5

고정 subgoal taxonomy 없이 reusable hierarchy를 자동학습할 수 있는가?

RQ6

Planner와 executor에 credit을 어떻게 분배할 것인가?

RQ7

물리적 직관은 언어사전학습과 interaction 중 어디에서 학습되는가?

RQ8

Reactive policy와 deliberative planner를 언제 전환해야 하는가?

RQ9

State–goal distance만으로 reward를 zero-shot 일반화할 수 있는가?

RQ10

여러 tool을 graph로 완전하게 표현할 수 있는가?

RQ11

단일 plan보다 portfolio가 언제 유리한가?

RQ12

Multi-agent joint plan의 충돌을 어떻게 해결할 것인가?

RQ13

동일 LM proposer–verifier의 오류상관을 어떻게 보정할 것인가?

RQ14

각 step에 가장 저렴한 model을 어떻게 배정할 것인가?

RQ15

환경변화와 intervention 아래에서도 plan의 인과적 유효성을 보장할 수 있는가?

Approaches / Methods

formal

VeryTrace

자연어 reasoning trace를 DSL로 변환해 dependency, 계산, constraint를 deterministic하게 검사한다.

formal

LM-Landmarks

LM이 landmark 후보를 제안하고 classical planner가 soundness를 검증한다.

hierarchy

HiPER

High-level planner와 low-level executor를 분리하고 두 시간척도에서 advantage를 계산한다.

hierarchy

Hi-CoT

Instruction과 execution block을 번갈아 생성해 reasoning drift를 줄인다.

hierarchy

ReTreVal

Adaptive reasoning tree, typed failure, backtracking, cross-problem memory를 결합한다.

world

ICPRL

Interactive control에서 action–outcome 관계를 학습해 physical intuition을 구축한다.

world

OrigamiBench

기하제약과 순차 folding plan을 통해 물리적 causal reasoning을 평가한다.

world

StateFactory

Object–attribute 상태와 목표상태의 의미적 거리로 reward를 예측한다.

policy

PACT

빠른 RL policy와 비동기 SLM planner를 결합하고 simulation을 통과한 plan만 실행한다.

policy

LaGO

LM action recommendation을 RL policy의 latent prior로 사용한다.

tools

QueryWeaver

자연어 질의를 tool-dependency graph로 변환하고 deterministic DFS로 실행한다.

tools

BaRA

Bounded BFS와 history reflection으로 웹수집 coverage와 budget을 균형화한다.

formal

SafeRun

LM의 soft preference 해석과 deterministic hard constraint enforcement를 분리한다.

operations

FRAMe

Planner LM, RAG memory, multimodal coach로 flight plan에 operator preference를 반영한다.

operations

Hub Capacity Planning

LLM decision table과 two-stage optimization feedback을 폐루프로 결합한다.

operations

Robust Optimization Portfolios

단일 수학모델 대신 다양한 candidate model portfolio와 evaluator를 사용한다.

compute

Calibrate Once, Choose the Beam

Calibration precision으로 적정 beam width와 search compute를 예측한다.

compute

AgentRouter

각 trajectory step을 적절한 model tier에 배정해 비용과 품질을 공동최적화한다.

Future Directions

1. Planning Operating System

Goal·constraint compiler, belief-state manager, hierarchical planner, solver, verifier ensemble, execution controller, failure ledger를 통합한다.

2. Planner–Verifier Separation

Symbolic verifier, simulator, constraint solver, learned verifier, human review를 서로 다른 inductive bias로 결합한다.

3. Causal World-Model Planning

sₜ₊₁=f_causal(sₜ,do(aₜ),uₜ) 형태로 intervention과 환경변화를 모델링한다.

4. Executable Reasoning Traces

자연어 trace를 typed state-transition program으로 compile하고 invariant violation을 국소화한다.

5. Landmark and Skill Compiler

성공 trajectory에서 공통 predicate를 추출하고 형식검증을 거쳐 reusable skill로 만든다.

6. Uncertainty-Aware Planner Switching

익숙한 상태에서는 reactive policy, 중간 uncertainty에서는 SLM, 고위험에서는 frontier LM+search를 호출한다.

7. Belief-State Planning

부분관측환경에서 observed facts, hypothesis, confidence, contradiction, possible worlds를 구조화한다.

8. Transactional Plan Execution

Precondition check, dry run, commit, postcondition, rollback·compensation을 database transaction처럼 적용한다.

9. Plan Portfolio with Diversity Guarantees

가정·목적·위험선호가 다른 후보의 품질 coverage와 diversity를 공동최적화한다.

10. Adaptive Test-Time Planning Curves

계획성능을 sample, beam, depth, verifier call, latency, token, energy의 함수로 평가한다.

11. Plan Risk Certificate

목표해석, 상태증거, assumption, constraint, simulated outcome, uncertainty, contingency와 validity scope를 기록한다.

12. Planning Digital Twin

실세계 실행 전에 trajectory, resource bottleneck, conflict, rollback 가능성을 sandbox에서 검증한다.

13. Multi-Agent Joint Plan Graph

Subgoal, dependency, resource, communication edge에 owner, verifier, deadline과 fallback을 할당한다.

14. Cost-Aware Heterogeneous Planning

각 step에서 model, tool, solver, human review를 비용 최소화와 end-to-end 품질 제약으로 선택한다.

15. Planning Failure Memory

실패한 plan, critical assumption, verifier evidence, recovery action, reuse condition을 축적한다.

16. Human Preference as Dynamic Constraint

사용자 선호를 고정 reward가 아니라 feedback에 따라 갱신되는 constraint로 모델링한다.

17. LM4Plan Standard Evaluation

Grounding, validity, optimality, robustness, world model, recovery, safety, calibration, efficiency와 reproducibility를 표준화한다.

Conclusion

자유형 계획 → 구조화된 계획

Plan은 prose가 아니라 graph, tree, DSL, state transition, PDDL, HTN, optimization model이 된다.

LM 단독 Planner → Neuro-Symbolic System

LM은 의미와 후보를 담당하고 planner·solver·simulator가 correctness를 담당한다.

Flat CoT → Hierarchical Plan–Execute

Subgoal과 skill 구조가 coherence, credit assignment, efficiency를 개선한다.

정적 지식 → Interactive World Model

Action–outcome feedback에서 causal intuition을 학습한다.

단일 후보 → Verified Portfolio

다양한 후보를 생성하고 solver·verifier·human이 선택한다.

무제한 Reasoning → Calibrated Compute

Search depth, beam, sample, verifier budget을 calibration한다.

동일 Frontier Model → Heterogeneous Stack

Step 난이도에 따라 small LM, frontier LM, tool, solver를 배정한다.

상관적 예측 → Causal Planning

환경변화와 intervention에서도 plan이 유효하도록 mechanism을 학습한다.

계획의 핵심은 언어모델이 더 오래 생각하게 만드는 것이 아니라, 의미해석·탐색·검증·실행·복구를 서로 다른 책임계층으로 분리하고 폐루프로 연결하는 데 있다.

Sources