TL;DR & Key Takeaways
- DPPM(Decompose → Plan in Parallel → Merge), LLM based planning이 겪던 ① heavy constraints · ② cascading errors를 해결하는 모듈 제안
- 여행 · 실무 프로젝트처럼 예산·일정·선호가 얽힌 작업을, constraints 단위로 적절히 쪼개서 각 Agent가 병렬로 sub-plan을 만든 뒤 verification-merge 단계에서 통합·수정하는 방식
- 여행계획 분야에서 TravelPlanner / ChinaTravel-M 등 기존 모듈보다 Final Pass Rate 최대 64 pp → 87 pp, 기존 SOTA 방법(LLM-Modulo) 보다 최대 +40 pp.
- SEMO WBS generate 모듈에 반영하면, ① Constraint-aware Task Decomposition -> ② Local Plan Generation -> ③ Incremental Merge 만으로 WBS의 생성속도와 품질을 동시에 높일 가능성이 있음.
논문 선정 이유
아직 preprint 단계의 논문이지만 SEMO에 바로 적용하여 실험해 볼 만한 방법론을 담은 내용인 것 같아 리뷰해 보았습니다.
1. 기존 LLM 기반 Planning의 한계
LLM 기반 Planning에서 기존 Sequential Methods, Interleaved Methods는 ① , ② 문제가 있었습니다.
① heavy constraints
기존 LLM 기반 계획 방식은 작업을 분해할 때 사용자가 제시한 Constraints을 고르게 배분하지 못해 특정 sub-task에 과도한 제약이 집중되는 문제가 있습니다. 현행 LLM은 한 번에 많은 제약을 처리하면 할루시네이션 발생 가능성이 높아지므로, 이러한 서브태스크에서 실패가 잦아집니다.
② cascading errors
각 서브태스크 수행 계획의 정확성이 이전 단계 결과에 전적으로 의존하기 때문에, 초기 단계에서 발생한 작은 오류가 이후 단계로 연쇄적으로 전달되어 전체 계획이 무너질 위험이 큽니다. 이렇게 ‘연쇄 오류’가 발생하면 부분적 수정만으로는 전체 계획을 복구하기 어렵습니다.
2. DPPM Methodology
저자는 해당 문제를 개선한 DPPM을 제안하였고, 모식도는 다음과 같습니다.
| Local Plan Generation (Parallel) | 네 개 LLM Agent가 Parllel하게 sub-plan을 생성. 프롬프트에 Global Constraint Instruction을 삽입해 예산 등 전역 Constraint 위반을 예방 |
| Incremental Merge | 후보 서브플랜을 Cartesian Product로 조합→ 가장 많은 Constraint를 충족하는 플랜 선정 |
| Verification & Refinement Loop | Critic 함수로 Constraint 위반 검출→ LLM에게 self-refine 프롬프트 전달 (최대 10회) |
3. Experiments
3.1 실험 절차
① Benchmark Dataset
논문은 TravelPlanner와 ChinaTravel-M 두 가지 공개 벤치마크를 사용했습니다.
- 두 벤치마크 모두 “다중 제약을 가진 현실 여행 일정”을 테스트베드로 삼아, LLM이 복잡한 Constraints를 얼마나 잘 만족하며 일정을 짜는지를 정량화합니다.
- TravelPlanner는 국제 여정을, ChinaTravel-M은 중국 국내 여정을 다루며, 3·5·7 일 일정 × 난이도(Easy/Medium/Hard) 조합으로 총 1225개 질문이 준비돼 있습니다.
- 각 질문을 풀 때 에이전트는 6종 검색 DB(항공·숙소·식사 등 약 400 만 건)와 대응 API, 그리고 NotebookWrite 기능만 사용할 수 있는 샌드박스 안에서 실행됩니다.
→ 실제 서비스 환경과 가장 흡사한 “복합 제약+제한된 툴” 조건을 만들어 LLM의 기획 능력을 검증하려는 의도입니다.
② 백본 모델(Backbone Models)
실험에는 Qwen-2.5-32B·72B와 DeepSeek-V3·R1, 총 4종 대형 모델을 채택했습니다.
- 크기가 서로 다른 Qwen-32B·72B를 넣어 “모델 규모가 커지면 얼마나 더 잘 계획하나?”를 확인했습니다.
- DeepSeek 시리즈는 중국어·다국어 튜닝이 강점이라 중국 여행 벤치마크에서 유리할 수 있습니다.
→ 서로 다른 계열·사이즈를 섞어 DPPM이 특정 모델에 종속되지 않고 일관된 효과를 내는지 검증하려는 목적입니다.
③ 비교군(Baselines) 설정
아래는 DPPM 방법론과 비교할 기존 방법론들입니다.
- Direct — 레퍼런스만 주고 한 번에 일정 생성
- CoT(Chain-of-Thought) — “생각 과정”을 단계별로 출력하며 문제 분해
- LLM-Modulo — “생성→제약 검증→수정” 루프를 도입한 기법
④ 반복 횟수(Verification Loop Budget)
검증·정제 루프는 최대 10회로 제한했습니다.
- 반복 횟수를 늘리면 성능이 오르지만 LLM 호출 비용·지연 시간도 함께 상승합니다.
- 실험적으로 10회에서 성능·비용 균형점이 확인돼, 모든 기법에 동일하게 적용했습니다.
→ 실제 서비스 적용 시에도 이 정도 반복이면 품질과 비용을 모두 수용할 만하다는 근거가 됩니다.
3.2 📏 평가지표
① Delivery Rate – 모델이 타임아웃이나 포맷 오류 없이 계획을 “일단” 출력했는지를 확인합니다.
② Commonsense Pass – 상식적 제약(예: ‘아침은 오전’ · ‘도착 도시에 숙박’)을 얼마나 지켰는지 측정합니다. Micro는 제약 항목별 비율, Macro는 한 샘플이 모든 상식 제약을 전부 만족했을 때만 1점으로 잡습니다.
③ Hard Pass – 예산·기간·최소 숙박일처럼 반드시 지켜야 하는 강제 제약을 같은 방식(Micro/Macro)으로 평가합니다.
④ Final Pass Rate – 상식과 강제 제약을 동시에 모두 충족한 경우에만 성공으로 집계합니다. 실제 서비스에서 “바로 쓸 수 있는 일정” 비율을 보여 주므로 논문에서 가장 중요한 지표로 사용되었습니다.
Micro는 여러 제약을 항목별로 합산해 ‘몇 % 나 지켰나’를 보는 부분점수이고,
Macro는 플랜 단위로 모든 제약을 전부 만족했을 때만 인정하는 비율입니다.
3.3 📊 결과 해설
① Table 1 (TravelPlanner 백본 별 성능)
네 가지 모델(Qwen-32B·72B, DeepSeek-V3·R1) 모두에서 Delivery Rate 100 %는 동일하지만, Final Pass는 Direct 2.8 ∼ 17.8 %, CoT 0.6 ∼ 25 %, LLM-Modulo 36.7 ∼ 57.8 %에 그칩니다. 반면 DPPM은 58.9 ∼ 87.2 %로 항상 1위이며, Macro 관점에서도 상식·강제 제약을 70 ∼ 90 % 이상 충족합니다. 즉 백본 규모·계열이 바뀌어도 DPPM이 꾸준히 ~20 ∼ 70 %포인트 앞서는 모델과 관계없이 우위를 입증합니다.
② Table 2 (ChinaTravel-M 난이도 별 성능)
중국 국내 시나리오에서도 패턴이 동일합니다. Easy 레벨에서 Direct 16.2 % → DPPM 87.1 %, Medium 6.0 % → 70.7 %, Hard 9.9 % → 52.5 %. 난도가 높아질수록 다른 방법은 급락하지만 DPPM은 여전히 절반 이상(Hard) 완전 통과하며, Macro 지표도 63 ∼ 92 % 까지 유지됩니다. 이는 복잡 제약·언어 환경이 달라져도 작업 분해·병렬 계획·검증 루프 구조가 강인하게 작동함을 보여 줍니다.
③ Figure 4 (제약 개수 별 누적 통과 샘플)
가로축은 “몇 개 제약을 동시에 통과했나”, 세로축은 그 이상을 만족한 누적 샘플 수입니다. Direct(파란 점선)는 5개 제약에서 급격히 떨어지고 12개 전부를 지킨 샘플은 0. LLM-Modulo(빨간 점선)는 10개 이후 급락해 12개 통과 샘플이 15개 정도. DPPM(초록 점선)은 10개 이후에도 완만히 감소, 12개 제약을 모두 충족한 샘플이 32개로 경쟁 대비 2배 이상입니다. 제약이 많아질수록 DPPM만이 ‘버티는’ 모습이 Heavy-Constraint 문제에 대한 성능을 보여줍니다.
④ Figure 5 (Self-Refinement Iterations)
파란 선(DPPM)은 첫 “0회”에서도 42.8 % Final Pass를 기록하며, 10회 정도에서 58 ∼ 59 %로 수렴합니다. 빨간 선(LLM-Modulo)은 0회 때 4.4 %로 출발해 5회쯤 30 % 대, 9회 이후 36.7 %에서 멈춥니다. 즉 DPPM은 출발선도 높고 학습 곡선도 가팔라서 5 회까지만 돌려도 LLM-Modulo의 최대치(36.7 %)를 추월하며, 반복을 늘려도 더 높은 ‘천장’을 보여 줍니다. 자체 Verification & Refinement loop의 효율성과 성능 여유를 동시에 확인할 수 있는 그래프입니다.
4. 결론 및 SEMO에 적용한다면?
- DPPM은 “제약 기반 분해 + 병렬 계획 + 반복 검증”이라는 단순 구조로, 다중 제약 환경에서 확실한 품질·속도 이득을 입증했습니다.
- 세모 WBS 모듈은 이미 “Clarifier → Search → Decomposer” 파이프라인을 보유하고 있어, Verification & Merge 모듈만 추가하면 자연스럽게 DPPM을 적용하여 테스트할 수 있습니다. 여력이 된다면 실험을 해보려고 합니다.
References
[1] Lu, Z., Lu, W., Tao, Y., Dai, Y., Chen, Z., Zhuang, H., et al.
“Decompose, Plan in Parallel, and Merge: A Novel Paradigm for Large Language Models-based Planning with Multiple Constraints.” arXiv preprint arXiv:2506.02683, 2025. DOI: 10.48550/arXiv.2506.02683
