Can LLMs Truly Plan? A Comprehensive Evaluation of Planning Capabilities

Multi-Plan: a travel-planning benchmark in Korean, English and mathematically structured form for evaluating LLM planning

Findings of EMNLP 2025

Gayeon Jung†, HyeonSeok Lim§, Minjun Kim§, Joon-ho Lim, KyungTae Lim‡,*, Hansaem Kim†,*

†Yonsei University §Seoul National University of Science and Technology Tutorus Labs ‡Korea Advanced Institute of Science and Technology (KAIST)

*Corresponding authors

Paper (ACL Anthology) PDF Dataset

Abstract

The existing assessments of planning capabilities of large language models (LLMs) remain largely limited to single-language or specific representation formats. To address this gap, we introduce the Multi-Plan benchmark comprising 204 multilingual and multi-format travel planning scenarios. In experimental results obtained with state-of-the-art LLMs, the Multi-Plan benchmark effectively highlights the performance disparities among models, notably showing superior results for reasoning-specialized models. Interestingly, language differences exhibited minimal impact, whereas mathematically structured representations significantly improved planning accuracy for most models, underscoring the crucial role of the input format. These findings enhance our understanding of planning abilities of LLMs, offer valuable insights for future research, and emphasize the need for more sophisticated AI evaluation methods. This dataset is publicly available at huggingface.co/datasets/Bllossom/Multi-Plan.

Keywords LLM planning Planning benchmark Travel / itinerary planning Constraint satisfaction Reasoning models Multilingual evaluation Korean Mathematical representation

The Multi-Plan Benchmark

Existing planning benchmarks use formal languages such as PDDL or English-only natural language. Multi-Plan, inspired by Natural Plan, poses the same practical travel-planning problems in three forms so that language and input format effects can be separated:

  1. Korean. Three annotators wrote 204 Korean travel-planning requests with templates for city selection, durations and constraints, designed so that each scenario has a unique optimal plan, balanced over 3–6 cities and over Europe, Asia and the Americas.
  2. English. The Korean requests were translated with DeepL and reviewed by annotators.
  3. Math. Claude 3.5 Sonnet (few-shot) rewrote each request into variables, constraints and flight connections, keeping context in natural language; the outputs were reviewed by humans.

Models are prompted with one randomly selected solved example and must output the itinerary in the same format. A plan is counted as correct only if the visited cities, date ranges, stay durations and flights extracted by regular expressions exactly match the answer.

Table 1. One Multi-Plan scenario in its English and mathematically structured forms (the Korean form states the same request), with the correct plan. (Example from Table 1 in the paper.)
English requestMath request
I am planning to visit three European cities over a total of 14 days. When traveling between cities, I will use only non-stop flights. Each transfer can be completed within a single day, and the flights do not reduce the time spent in any city. I would like to stay in Florence for 6 days and meet a friend there sometime between day 9 and day 14. I also want to spend 5 days in Barcelona and 5 days in Helsinki. Direct flights are available on the following routes: Barcelona ↔ Florence and Helsinki ↔ Barcelona. Using only these direct flights, please create a 14-day itinerary that covers all three cities. Variable definitions: H: Helsinki, B: Barcelona, F: Florence; aH, dH: arrival and departure date in Helsinki (likewise for B and F).
Constraints: dH − aH + 1 = 5, dB − aB + 1 = 5, dF − aF + 1 = 6, max(dH, dB, dF) − min(aH, aB, aF) + 1 = 14, [aF, dF] ∩ [9, 14] ≠ ∅.
Direct flights: (B ↔ F), (H ↔ B). Travel between cities takes at most one day and does not affect the duration of stays. Plan an itinerary visiting all three cities using direct flights.
Correct plan: Days 1–5: Visit Helsinki for 5 days; Day 5: Fly from Helsinki to Barcelona; Days 5–9: Visit Barcelona for 5 days; Day 9: Fly from Barcelona to Florence; Days 9–14: Visit Florence for 6 days.

Main Results

  • Reasoning models lead. o3-mini and Gemini-2.5-Pro average 82.03% and 83.01% exact-match accuracy, Claude-3.7-Sonnet thinking 50.16%, while no general (non-reasoning) closed model exceeds about 37%.
  • Language matters little. English scenarios are only about 0.71% more accurate than Korean on average, and most models differ by less than 2% between the two languages.
  • Mathematical structure helps. 9 of 11 closed models are more accurate with mathematically structured inputs than with Korean, with gains above 8% for GPT-4o, Claude-3.7-Sonnet thinking and Gemini-2.0-Flash.
  • Open-source models lag. Most small open models score near 0%; Qwen3-32B is the strongest (25.98% Korean, 46.57% English, 26.47% Math), close to Claude-3.7-Sonnet standard.
  • More cities, more errors. All models are most accurate on three-city itineraries, and seven models are least accurate on Asian itineraries.
Table 2. Exact-match accuracy of closed-source models on Multi-Plan for the Korean, English and mathematically structured versions. “Reasoning” marks models prompted with a reasoning-oriented instruction. (Table 2 in the paper; open-source results are in Table 3.)
ModelReasoningKoreanEnglishMath
o3-mini✓82.84%82.84%80.39%
GPT-4o✗3.43%3.43%14.22%
GPT-4-turbo✗10.78%10.78%17.65%
GPT-4✗15.20%15.20%21.08%
Claude-3.7-Sonnet thinking✓46.57%48.53%55.39%
Claude-3.7-Sonnet standard✗29.41%30.39%37.27%
Claude-3.5-Haiku✗8.33%8.33%11.27%
Claude-3-Opus✗27.45%27.45%25.00%
Gemini-2.5-Pro✓82.35%83.82%82.84%
Gemini-2.0-Flash✗11.76%9.80%21.08%
Gemini-1.5-Pro✗6.37%11.76%7.84%

BibTeX

@inproceedings{jung-etal-2025-llms,
    title = "Can {LLM}s Truly Plan? A Comprehensive Evaluation of Planning Capabilities",
    author = "Jung, Gayeon  and
      Lim, HyeonSeok  and
      Kim, Minjun  and
      Lim, Joon-ho  and
      Lim, KyungTae  and
      Kim, Hansaem",
    editor = "Christodoulopoulos, Christos  and
      Chakraborty, Tanmoy  and
      Rose, Carolyn  and
      Peng, Violet",
    booktitle = "Findings of the {A}ssociation for {C}omputational {L}inguistics: {EMNLP} 2025",
    month = nov,
    year = "2025",
    address = "Suzhou, China",
    publisher = "Association for Computational Linguistics",
    url = "https://aclanthology.org/2025.findings-emnlp.702/",
    doi = "10.18653/v1/2025.findings-emnlp.702",
    pages = "13069--13084",
    ISBN = "979-8-89176-335-7"
}
More projects from KAIST MLP Lab →